aboutsummaryrefslogtreecommitdiffstats
path: root/actionpack/lib/action_dispatch/journey/nfa
diff options
context:
space:
mode:
authorFrancesco Rodriguez <lrodriguezsanc@gmail.com>2012-12-20 15:42:39 -0500
committerFrancesco Rodriguez <lrodriguezsanc@gmail.com>2012-12-20 15:42:39 -0500
commiteb493f5ac84f2d65fbd1666e1496f0a8deafa27f (patch)
tree6c8226f652f99648a1898c2cfa33f9aa13041925 /actionpack/lib/action_dispatch/journey/nfa
parent42b555dcf3d3dfc8c4b56e6bf903389f014bf05e (diff)
downloadrails-eb493f5ac84f2d65fbd1666e1496f0a8deafa27f.tar.gz
rails-eb493f5ac84f2d65fbd1666e1496f0a8deafa27f.tar.bz2
rails-eb493f5ac84f2d65fbd1666e1496f0a8deafa27f.zip
update AD::Journey to follow Rails coding conventions
Diffstat (limited to 'actionpack/lib/action_dispatch/journey/nfa')
-rw-r--r--actionpack/lib/action_dispatch/journey/nfa/builder.rb34
-rw-r--r--actionpack/lib/action_dispatch/journey/nfa/simulator.rb18
-rw-r--r--actionpack/lib/action_dispatch/journey/nfa/transition_table.rb61
3 files changed, 55 insertions, 58 deletions
diff --git a/actionpack/lib/action_dispatch/journey/nfa/builder.rb b/actionpack/lib/action_dispatch/journey/nfa/builder.rb
index 8ba48e097d..ee6494c3e4 100644
--- a/actionpack/lib/action_dispatch/journey/nfa/builder.rb
+++ b/actionpack/lib/action_dispatch/journey/nfa/builder.rb
@@ -5,23 +5,23 @@ module ActionDispatch
module Journey # :nodoc:
module NFA # :nodoc:
class Visitor < Visitors::Visitor # :nodoc:
- def initialize tt
+ def initialize(tt)
@tt = tt
@i = -1
end
- def visit_CAT node
- left = visit node.left
- right = visit node.right
+ def visit_CAT(node)
+ left = visit(node.left)
+ right = visit(node.right)
- @tt.merge left.last, right.first
+ @tt.merge(left.last, right.first)
[left.first, right.last]
end
- def visit_GROUP node
+ def visit_GROUP(node)
from = @i += 1
- left = visit node.left
+ left = visit(node.left)
to = @i += 1
@tt.accepting = to
@@ -33,14 +33,14 @@ module ActionDispatch
[from, to]
end
- def visit_OR node
- from = @i += 1
- children = node.children.map { |c| visit c }
- to = @i += 1
+ def visit_OR(node)
+ from = @i += 1
+ children = node.children.map { |c| visit(c) }
+ to = @i += 1
children.each do |child|
- @tt[from, child.first] = nil
- @tt[child.last, to] = nil
+ @tt[from, child.first] = nil
+ @tt[child.last, to] = nil
end
@tt.accepting = to
@@ -48,26 +48,26 @@ module ActionDispatch
[from, to]
end
- def terminal node
+ def terminal(node)
from_i = @i += 1 # new state
to_i = @i += 1 # new state
@tt[from_i, to_i] = node
@tt.accepting = to_i
- @tt.add_memo to_i, node.memo
+ @tt.add_memo(to_i, node.memo)
[from_i, to_i]
end
end
class Builder # :nodoc:
- def initialize ast
+ def initialize(ast)
@ast = ast
end
def transition_table
tt = TransitionTable.new
- Visitor.new(tt).accept @ast
+ Visitor.new(tt).accept(@ast)
tt
end
end
diff --git a/actionpack/lib/action_dispatch/journey/nfa/simulator.rb b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb
index c2dfec3e21..5b40da6569 100644
--- a/actionpack/lib/action_dispatch/journey/nfa/simulator.rb
+++ b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb
@@ -6,7 +6,7 @@ module ActionDispatch
class MatchData # :nodoc:
attr_reader :memos
- def initialize memos
+ def initialize(memos)
@memos = memos
end
end
@@ -14,29 +14,29 @@ module ActionDispatch
class Simulator # :nodoc:
attr_reader :tt
- def initialize transition_table
+ def initialize(transition_table)
@tt = transition_table
end
- def simulate string
- input = StringScanner.new string
- state = tt.eclosure 0
+ def simulate(string)
+ input = StringScanner.new(string)
+ state = tt.eclosure(0)
until input.eos?
sym = input.scan(%r([/.?]|[^/.?]+))
# FIXME: tt.eclosure is not needed for the GTG
- state = tt.eclosure tt.move(state, sym)
+ state = tt.eclosure(tt.move(state, sym))
end
acceptance_states = state.find_all { |s|
- tt.accepting? tt.eclosure(s).sort.last
+ tt.accepting?(tt.eclosure(s).sort.last)
}
return if acceptance_states.empty?
- memos = acceptance_states.map { |x| tt.memo x }.flatten.compact
+ memos = acceptance_states.map { |x| tt.memo(x) }.flatten.compact
- MatchData.new memos
+ MatchData.new(memos)
end
alias :=~ :simulate
diff --git a/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb
index c2bb513f01..4446a911b2 100644
--- a/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb
+++ b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb
@@ -16,7 +16,7 @@ module ActionDispatch
@inverted = nil
end
- def accepting? state
+ def accepting?(state)
accepting == state
end
@@ -24,20 +24,20 @@ module ActionDispatch
[accepting]
end
- def add_memo idx, memo
+ def add_memo(idx, memo)
@memos[idx] = memo
end
- def memo idx
+ def memo(idx)
@memos[idx]
end
- def []= i, f, s
+ def []=(i, f, s)
@table[f][i] = s
end
- def merge left, right
- @memos[right] = @memos.delete left
+ def merge(left, right)
+ @memos[right] = @memos.delete(left)
@table[right] = @table.delete(left)
end
@@ -45,11 +45,10 @@ module ActionDispatch
(@table.keys + @table.values.map(&:keys).flatten).uniq
end
- ###
- # Returns a generalized transition graph with reduced states. The states
+ # Returns a generalized transition graph with reduced states. The states
# are reduced like a DFA, but the table must be simulated like an NFA.
#
- # Edges of the GTG are regular expressions
+ # Edges of the GTG are regular expressions.
def generalized_table
gt = GTG::TransitionTable.new
marked = {}
@@ -80,28 +79,26 @@ module ActionDispatch
final_groups.each do |states|
id = state_id[states]
- gt.add_accepting id
+ gt.add_accepting(id)
save = states.find { |s|
@memos.key?(s) && eclosure(s).sort.last == accepting
}
- gt.add_memo id, memo(save)
+ gt.add_memo(id, memo(save))
end
gt
end
- ###
# Returns set of NFA states to which there is a transition on ast symbol
# +a+ from some state +s+ in +t+.
- def following_states t, a
+ def following_states(t, a)
Array(t).map { |s| inverted[s][a] }.flatten.uniq
end
- ###
# Returns set of NFA states to which there is a transition on ast symbol
# +a+ from some state +s+ in +t+.
- def move t, a
+ def move(t, a)
Array(t).map { |s|
inverted[s].keys.compact.find_all { |sym|
sym === a
@@ -113,10 +110,9 @@ module ActionDispatch
inverted.values.map(&:keys).flatten.compact.uniq.sort_by { |x| x.to_s }
end
- ###
# Returns a set of NFA states reachable from some NFA state +s+ in set
# +t+ on nil-transitions alone.
- def eclosure t
+ def eclosure(t)
stack = Array(t)
seen = {}
children = []
@@ -128,7 +124,7 @@ module ActionDispatch
seen[s] = true
children << s
- stack.concat inverted[s][nil]
+ stack.concat(inverted[s][nil])
end
children.uniq
@@ -141,26 +137,27 @@ module ActionDispatch
end
private
- def inverted
- return @inverted if @inverted
- @inverted = Hash.new { |h,from|
- h[from] = Hash.new { |j,s| j[s] = [] }
- }
+ def inverted
+ return @inverted if @inverted
+
+ @inverted = Hash.new { |h, from|
+ h[from] = Hash.new { |j, s| j[s] = [] }
+ }
- @table.each { |to, hash|
- hash.each { |from, sym|
- if sym
- sym = Nodes::Symbol === sym ? sym.regexp : sym.left
- end
+ @table.each { |to, hash|
+ hash.each { |from, sym|
+ if sym
+ sym = Nodes::Symbol === sym ? sym.regexp : sym.left
+ end
- @inverted[from][sym] << to
+ @inverted[from][sym] << to
+ }
}
- }
- @inverted
+ @inverted
+ end
end
- end
end
end
end