diff options
Diffstat (limited to 'actionpack/lib/action_dispatch/journey/nfa')
4 files changed, 322 insertions, 0 deletions
diff --git a/actionpack/lib/action_dispatch/journey/nfa/builder.rb b/actionpack/lib/action_dispatch/journey/nfa/builder.rb new file mode 100644 index 0000000000..ee6494c3e4 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/builder.rb @@ -0,0 +1,76 @@ +require 'action_dispatch/journey/nfa/transition_table' +require 'action_dispatch/journey/gtg/transition_table' + +module ActionDispatch + module Journey # :nodoc: + module NFA # :nodoc: + class Visitor < Visitors::Visitor # :nodoc: + def initialize(tt) + @tt = tt + @i = -1 + end + + def visit_CAT(node) + left = visit(node.left) + right = visit(node.right) + + @tt.merge(left.last, right.first) + + [left.first, right.last] + end + + def visit_GROUP(node) + from = @i += 1 + left = visit(node.left) + to = @i += 1 + + @tt.accepting = to + + @tt[from, left.first] = nil + @tt[left.last, to] = nil + @tt[from, to] = nil + + [from, to] + end + + 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 + end + + @tt.accepting = to + + [from, to] + end + + 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) + + [from_i, to_i] + end + end + + class Builder # :nodoc: + def initialize(ast) + @ast = ast + end + + def transition_table + tt = TransitionTable.new + Visitor.new(tt).accept(@ast) + tt + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/nfa/dot.rb b/actionpack/lib/action_dispatch/journey/nfa/dot.rb new file mode 100644 index 0000000000..47bf76bdbf --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/dot.rb @@ -0,0 +1,36 @@ +# encoding: utf-8 + +module ActionDispatch + module Journey # :nodoc: + module NFA # :nodoc: + module Dot # :nodoc: + def to_dot + edges = transitions.map { |from, sym, to| + " #{from} -> #{to} [label=\"#{sym || 'ε'}\"];" + } + + #memo_nodes = memos.values.flatten.map { |n| + # label = n + # if Journey::Route === n + # label = "#{n.verb.source} #{n.path.spec}" + # end + # " #{n.object_id} [label=\"#{label}\", shape=box];" + #} + #memo_edges = memos.flat_map { |k, memos| + # (memos || []).map { |v| " #{k} -> #{v.object_id};" } + #}.uniq + + <<-eodot +digraph nfa { + rankdir=LR; + node [shape = doublecircle]; + #{accepting_states.join ' '}; + node [shape = circle]; +#{edges.join "\n"} +} + eodot + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/nfa/simulator.rb b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb new file mode 100644 index 0000000000..b23270db3c --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb @@ -0,0 +1,47 @@ +require 'strscan' + +module ActionDispatch + module Journey # :nodoc: + module NFA # :nodoc: + class MatchData # :nodoc: + attr_reader :memos + + def initialize(memos) + @memos = memos + end + end + + class Simulator # :nodoc: + attr_reader :tt + + def initialize(transition_table) + @tt = transition_table + end + + 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)) + end + + acceptance_states = state.find_all { |s| + tt.accepting?(tt.eclosure(s).sort.last) + } + + return if acceptance_states.empty? + + memos = acceptance_states.flat_map { |x| tt.memo(x) }.compact + + MatchData.new(memos) + end + + alias :=~ :simulate + alias :match :simulate + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb new file mode 100644 index 0000000000..e65f7238ab --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb @@ -0,0 +1,163 @@ +require 'action_dispatch/journey/nfa/dot' + +module ActionDispatch + module Journey # :nodoc: + module NFA # :nodoc: + class TransitionTable # :nodoc: + include Journey::NFA::Dot + + attr_accessor :accepting + attr_reader :memos + + def initialize + @table = Hash.new { |h,f| h[f] = {} } + @memos = {} + @accepting = nil + @inverted = nil + end + + def accepting?(state) + accepting == state + end + + def accepting_states + [accepting] + end + + def add_memo(idx, memo) + @memos[idx] = memo + end + + def memo(idx) + @memos[idx] + end + + def []=(i, f, s) + @table[f][i] = s + end + + def merge(left, right) + @memos[right] = @memos.delete(left) + @table[right] = @table.delete(left) + end + + def states + (@table.keys + @table.values.flat_map(&:keys)).uniq + end + + # 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. + def generalized_table + gt = GTG::TransitionTable.new + marked = {} + state_id = Hash.new { |h,k| h[k] = h.length } + alphabet = self.alphabet + + stack = [eclosure(0)] + + until stack.empty? + state = stack.pop + next if marked[state] || state.empty? + + marked[state] = true + + alphabet.each do |alpha| + next_state = eclosure(following_states(state, alpha)) + next if next_state.empty? + + gt[state_id[state], state_id[next_state]] = alpha + stack << next_state + end + end + + final_groups = state_id.keys.find_all { |s| + s.sort.last == accepting + } + + final_groups.each do |states| + id = state_id[states] + + gt.add_accepting(id) + save = states.find { |s| + @memos.key?(s) && eclosure(s).sort.last == accepting + } + + 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) + Array(t).flat_map { |s| inverted[s][a] }.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) + Array(t).map { |s| + inverted[s].keys.compact.find_all { |sym| + sym === a + }.map { |sym| inverted[s][sym] } + }.flatten.uniq + end + + def alphabet + inverted.values.flat_map(&:keys).compact.uniq.sort_by(&: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) + stack = Array(t) + seen = {} + children = [] + + until stack.empty? + s = stack.pop + next if seen[s] + + seen[s] = true + children << s + + stack.concat(inverted[s][nil]) + end + + children.uniq + end + + def transitions + @table.flat_map { |to, hash| + hash.map { |from, sym| [from, sym, to] } + } + end + + private + + 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 + + @inverted[from][sym] << to + } + } + + @inverted + end + end + end + end +end |