diff options
Diffstat (limited to 'actionpack/lib/action_dispatch/journey/nfa')
4 files changed, 325 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..720820accb --- /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 + module NFA + class Visitor < Visitors::Visitor + 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 + 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..6d2f851c2c --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/dot.rb @@ -0,0 +1,36 @@ +# encoding: utf-8 + +module ActionDispatch + module Journey + module NFA + module Dot + 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.map { |k, memos| + # (memos || []).map { |v| " #{k} -> #{v.object_id};" } + #}.flatten.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..9948213146 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb @@ -0,0 +1,47 @@ +require 'strscan' + +module ActionDispatch + module Journey + module NFA + class MatchData + attr_reader :memos + + def initialize memos + @memos = memos + end + end + + class Simulator + 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.map { |x| tt.memo x }.flatten.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..053ee4351a --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb @@ -0,0 +1,166 @@ +require 'action_dispatch/journey/nfa/dot' + +module ActionDispatch + module Journey + module NFA + class TransitionTable + 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.map(&:keys).flatten).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).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 + 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.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 + 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.map { |to, hash| + hash.map { |from, sym| [from, sym, to] } + }.flatten(1) + 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 |