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.

3 files changed, 360 insertions, 0 deletions

diff --git a/actionpack/lib/action_dispatch/journey/gtg/builder.rb b/actionpack/lib/action_dispatch/journey/gtg/builder.rb
new file mode 100644
index 0000000000..10b53500fc
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/gtg/builder.rb
@@ -0,0 +1,161 @@
+require 'action_dispatch/journey/gtg/transition_table'
+
+module ActionDispatch
+  module Journey
+    module GTG
+      class Builder
+        DUMMY = Nodes::Dummy.new # :nodoc:
+
+        attr_reader :root, :ast, :endpoints
+
+        def initialize root
+          @root         = root
+          @ast          = Nodes::Cat.new root, DUMMY
+          @followpos    = nil
+        end
+
+        def transition_table
+          dtrans   = TransitionTable.new
+          marked   = {}
+          state_id = Hash.new { |h,k| h[k] = h.length }
+
+          start   = firstpos(root)
+          dstates = [start]
+          until dstates.empty?
+            s = dstates.shift
+            next if marked[s]
+            marked[s] = true # mark s
+
+            s.group_by { |state| symbol(state) }.each do |sym, ps|
+              u = ps.map { |l| followpos(l) }.flatten
+              next if u.empty?
+
+              if u.uniq == [DUMMY]
+                from = state_id[s]
+                to   = state_id[Object.new]
+                dtrans[from, to] = sym
+
+                dtrans.add_accepting to
+                ps.each { |state| dtrans.add_memo to, state.memo }
+              else
+                dtrans[state_id[s], state_id[u]] = sym
+
+                if u.include? DUMMY
+                  to = state_id[u]
+
+                  accepting = ps.find_all { |l| followpos(l).include? DUMMY }
+
+                  accepting.each { |accepting_state|
+                    dtrans.add_memo to, accepting_state.memo
+                  }
+
+                  dtrans.add_accepting state_id[u]
+                end
+              end
+
+              dstates << u
+            end
+          end
+
+          dtrans
+        end
+
+        def nullable? node
+          case node
+          when Nodes::Group
+            true
+          when Nodes::Star
+            true
+          when Nodes::Or
+            node.children.any? { |c| nullable?(c) }
+          when Nodes::Cat
+            nullable?(node.left) && nullable?(node.right)
+          when Nodes::Terminal
+            !node.left
+          when Nodes::Unary
+            nullable? node.left
+          else
+            raise ArgumentError, 'unknown nullable: %s' % node.class.name
+          end
+        end
+
+        def firstpos node
+          case node
+          when Nodes::Star
+            firstpos(node.left)
+          when Nodes::Cat
+            if nullable? node.left
+              firstpos(node.left) | firstpos(node.right)
+            else
+              firstpos(node.left)
+            end
+          when Nodes::Or
+            node.children.map { |c| firstpos(c) }.flatten.uniq
+          when Nodes::Unary
+            firstpos(node.left)
+          when Nodes::Terminal
+            nullable?(node) ? [] : [node]
+          else
+            raise ArgumentError, 'unknown firstpos: %s' % node.class.name
+          end
+        end
+
+        def lastpos node
+          case node
+          when Nodes::Star
+            firstpos(node.left)
+          when Nodes::Or
+            node.children.map { |c| lastpos(c) }.flatten.uniq
+          when Nodes::Cat
+            if nullable? node.right
+              lastpos(node.left) | lastpos(node.right)
+            else
+              lastpos(node.right)
+            end
+          when Nodes::Terminal
+            nullable?(node) ? [] : [node]
+          when Nodes::Unary
+            lastpos(node.left)
+          else
+            raise ArgumentError, 'unknown lastpos: %s' % node.class.name
+          end
+        end
+
+        def followpos node
+          followpos_table[node]
+        end
+
+        private
+        def followpos_table
+          @followpos ||= build_followpos
+        end
+
+        def build_followpos
+          table = Hash.new { |h,k| h[k] = [] }
+          @ast.each do |n|
+            case n
+            when Nodes::Cat
+              lastpos(n.left).each do |i|
+                table[i] += firstpos(n.right)
+              end
+            when Nodes::Star
+              lastpos(n).each do |i|
+                table[i] += firstpos(n)
+              end
+            end
+          end
+          table
+        end
+
+        def symbol edge
+          case edge
+          when Journey::Nodes::Symbol
+            edge.regexp
+          else
+            edge.left
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/gtg/simulator.rb b/actionpack/lib/action_dispatch/journey/gtg/simulator.rb
new file mode 100644
index 0000000000..fda14c8680
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/gtg/simulator.rb
@@ -0,0 +1,44 @@
+require 'strscan'
+
+module ActionDispatch
+  module Journey
+    module GTG
+      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 = [0]
+          while sym = input.scan(%r([/.?]|[^/.?]+))
+            state = tt.move(state, sym)
+          end
+
+          acceptance_states = state.find_all { |s|
+            tt.accepting? s
+          }
+
+          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/gtg/transition_table.rb b/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb
new file mode 100644
index 0000000000..b6812b6475
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb
@@ -0,0 +1,155 @@
+require 'action_dispatch/journey/nfa/dot'
+
+module ActionDispatch
+  module Journey
+    module GTG
+      class TransitionTable
+        include Journey::NFA::Dot
+
+        attr_reader :memos
+
+        def initialize
+          @regexp_states = Hash.new { |h,k| h[k] = {} }
+          @string_states = Hash.new { |h,k| h[k] = {} }
+          @accepting     = {}
+          @memos         = Hash.new { |h,k| h[k] = [] }
+        end
+
+        def add_accepting state
+          @accepting[state] = true
+        end
+
+        def accepting_states
+          @accepting.keys
+        end
+
+        def accepting? state
+          @accepting[state]
+        end
+
+        def add_memo idx, memo
+          @memos[idx] << memo
+        end
+
+        def memo idx
+          @memos[idx]
+        end
+
+        def eclosure t
+          Array(t)
+        end
+
+        def move t, a
+          move_string(t, a).concat move_regexp(t, a)
+        end
+
+        def to_json
+          require 'json'
+
+          simple_regexp = Hash.new { |h,k| h[k] = {} }
+
+          @regexp_states.each do |from, hash|
+            hash.each do |re, to|
+              simple_regexp[from][re.source] = to
+            end
+          end
+
+          JSON.dump({
+            :regexp_states => simple_regexp,
+            :string_states => @string_states,
+            :accepting     => @accepting
+          })
+        end
+
+        def to_svg
+          svg = IO.popen("dot -Tsvg", 'w+') { |f|
+            f.write to_dot
+            f.close_write
+            f.readlines
+          }
+          3.times { svg.shift }
+          svg.join.sub(/width="[^"]*"/, '').sub(/height="[^"]*"/, '')
+        end
+
+        def visualizer paths, title = 'FSM'
+          viz_dir   = File.join File.dirname(__FILE__), '..', 'visualizer'
+          fsm_js    = File.read File.join(viz_dir, 'fsm.js')
+          fsm_css   = File.read File.join(viz_dir, 'fsm.css')
+          erb       = File.read File.join(viz_dir, 'index.html.erb')
+          states    = "function tt() { return #{to_json}; }"
+
+          fun_routes = paths.shuffle.first(3).map do |ast|
+            ast.map { |n|
+              case n
+              when Nodes::Symbol
+                case n.left
+                when ':id' then rand(100).to_s
+                when ':format' then %w{ xml json }.shuffle.first
+                else
+                  'omg'
+                end
+              when Nodes::Terminal then n.symbol
+              else
+                nil
+              end
+            }.compact.join
+          end
+
+          stylesheets = [fsm_css]
+          svg         = to_svg
+          javascripts = [states, fsm_js]
+
+          # Annoying hack for 1.9 warnings
+          fun_routes  = fun_routes
+          stylesheets = stylesheets
+          svg         = svg
+          javascripts = javascripts
+
+          require 'erb'
+          template = ERB.new erb
+          template.result(binding)
+        end
+
+        def []= from, to, sym
+          case sym
+          when String
+            @string_states[from][sym] = to
+          when Regexp
+            @regexp_states[from][sym] = to
+          else
+            raise ArgumentError, 'unknown symbol: %s' % sym.class
+          end
+        end
+
+        def states
+          ss = @string_states.keys + @string_states.values.map(&:values).flatten
+          rs = @regexp_states.keys + @regexp_states.values.map(&:values).flatten
+          (ss + rs).uniq
+        end
+
+        def transitions
+          @string_states.map { |from, hash|
+            hash.map { |s, to| [from, s, to] }
+          }.flatten(1) + @regexp_states.map { |from, hash|
+            hash.map { |s, to| [from, s, to] }
+          }.flatten(1)
+        end
+
+        private
+        def move_regexp t, a
+          return [] if t.empty?
+
+          t.map { |s|
+            @regexp_states[s].map { |re,v| re === a ? v : nil }
+          }.flatten.compact.uniq
+        end
+
+        def move_string t, a
+          return [] if t.empty?
+
+          t.map { |s| @string_states[s][a] }.compact
+        end
+      end
+    end
+  end
+end