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.

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