diff options
Diffstat (limited to 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb')
-rw-r--r-- | actionpack/lib/action_dispatch/journey/nfa/transition_table.rb | 166 |
1 files changed, 166 insertions, 0 deletions
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 |