Integrate Journey into Action Dispatch

Move the Journey code underneath the ActionDispatch namespace so
that we don't pollute the global namespace with names that may
be used for models.

Fixes rails/journey#49.

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