aboutsummaryrefslogtreecommitdiffstats
path: root/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb
diff options
context:
space:
mode:
Diffstat (limited to 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb')
-rw-r--r--actionpack/lib/action_dispatch/journey/nfa/transition_table.rb163
1 files changed, 163 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..a3017aeea1
--- /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.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