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.

28 files changed, 2340 insertions, 1 deletions

diff --git a/actionpack/lib/action_dispatch.rb b/actionpack/lib/action_dispatch.rb
index d002babee3..938161dc69 100644
--- a/actionpack/lib/action_dispatch.rb
+++ b/actionpack/lib/action_dispatch.rb
@@ -63,6 +63,7 @@ module ActionDispatch
     autoload :Static
   end
 
+  autoload :Journey
   autoload :MiddlewareStack, 'action_dispatch/middleware/stack'
   autoload :Routing
 
diff --git a/actionpack/lib/action_dispatch/journey.rb b/actionpack/lib/action_dispatch/journey.rb
new file mode 100644
index 0000000000..ad42713482
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey.rb
@@ -0,0 +1,5 @@
+require 'action_dispatch/journey/router'
+require 'action_dispatch/journey/gtg/builder'
+require 'action_dispatch/journey/gtg/simulator'
+require 'action_dispatch/journey/nfa/builder'
+require 'action_dispatch/journey/nfa/simulator'
diff --git a/actionpack/lib/action_dispatch/journey/backwards.rb b/actionpack/lib/action_dispatch/journey/backwards.rb
new file mode 100644
index 0000000000..33f6976897
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/backwards.rb
@@ -0,0 +1,5 @@
+module Rack
+  Mount = ActionDispatch::Journey::Router
+  Mount::RouteSet = ActionDispatch::Journey::Router
+  Mount::RegexpWithNamedGroups = ActionDispatch::Journey::Path::Pattern
+end
diff --git a/actionpack/lib/action_dispatch/journey/core-ext/hash.rb b/actionpack/lib/action_dispatch/journey/core-ext/hash.rb
new file mode 100644
index 0000000000..fad5cdaa63
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/core-ext/hash.rb
@@ -0,0 +1,11 @@
+# :stopdoc:
+if RUBY_VERSION < '1.9'
+class Hash
+  def keep_if
+    each do |k,v|
+      delete(k) unless yield(k,v)
+    end
+  end
+end
+end
+# :startdoc:
diff --git a/actionpack/lib/action_dispatch/journey/formatter.rb b/actionpack/lib/action_dispatch/journey/formatter.rb
new file mode 100644
index 0000000000..873a73baf0
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/formatter.rb
@@ -0,0 +1,147 @@
+module ActionDispatch
+  module Journey
+    ###
+    # The Formatter class is used for formatting URLs.  For example, parameters
+    # passed to +url_for+ in rails will eventually call Formatter#generate
+    class Formatter
+      attr_reader :routes
+
+      def initialize routes
+        @routes = routes
+        @cache  = nil
+      end
+
+      def generate type, name, options, recall = {}, parameterize = nil
+        constraints = recall.merge options
+        missing_keys = []
+
+        match_route(name, constraints) do |route|
+          parameterized_parts = extract_parameterized_parts route, options, recall, parameterize
+          next if !name && route.requirements.empty? && route.parts.empty?
+
+          missing_keys = missing_keys(route, parameterized_parts)
+          next unless missing_keys.empty?
+          params = options.dup.delete_if do |key, _|
+            parameterized_parts.key?(key) || route.defaults.key?(key)
+          end
+
+          return [route.format(parameterized_parts), params]
+        end
+
+        raise Router::RoutingError.new "missing required keys: #{missing_keys}"
+      end
+
+      def clear
+        @cache = nil
+      end
+
+      private
+      def extract_parameterized_parts route, options, recall, parameterize = nil
+        constraints = recall.merge options
+        data = constraints.dup
+
+        keys_to_keep = route.parts.reverse.drop_while { |part|
+          !options.key?(part) || (options[part] || recall[part]).nil?
+        } | route.required_parts
+
+        (data.keys - keys_to_keep).each do |bad_key|
+          data.delete bad_key
+        end
+
+        parameterized_parts = data.dup
+
+        if parameterize
+          parameterized_parts.each do |k,v|
+            parameterized_parts[k] = parameterize.call(k, v)
+          end
+        end
+
+        parameterized_parts.keep_if { |_,v| v  }
+        parameterized_parts
+      end
+
+      def named_routes
+        routes.named_routes
+      end
+
+      def match_route name, options
+        if named_routes.key? name
+          yield named_routes[name]
+        else
+          #routes = possibles(@cache, options.to_a)
+          routes = non_recursive(cache, options.to_a)
+
+          hash = routes.group_by { |_, r|
+            r.score options
+          }
+
+          hash.keys.sort.reverse_each do |score|
+            next if score < 0
+
+            hash[score].sort_by { |i,_| i }.each do |_,route|
+              yield route
+            end
+          end
+        end
+      end
+
+      def non_recursive cache, options
+        routes = []
+        stack  = [cache]
+
+        while stack.any?
+          c = stack.shift
+          routes.concat c[:___routes] if c.key? :___routes
+
+          options.each do |pair|
+            stack << c[pair] if c.key? pair
+          end
+        end
+
+        routes
+      end
+
+      # returns an array populated with missing keys if any are present
+      def missing_keys route, parts
+        missing_keys = []
+        tests = route.path.requirements
+        route.required_parts.each { |key|
+          if tests.key? key
+            missing_keys << key unless /\A#{tests[key]}\Z/ === parts[key]
+          else
+            missing_keys << key unless parts[key]
+          end
+        }
+        missing_keys
+      end
+
+      def possibles cache, options, depth = 0
+        cache.fetch(:___routes) { [] } + options.find_all { |pair|
+          cache.key? pair
+        }.map { |pair|
+          possibles(cache[pair], options, depth + 1)
+        }.flatten(1)
+      end
+
+      # returns boolean, true if no missing keys are present
+      def verify_required_parts! route, parts
+        missing_keys(route, parts).empty?
+      end
+
+      def build_cache
+        root = { :___routes => [] }
+        routes.each_with_index do |route, i|
+          leaf = route.required_defaults.inject(root) do |h, tuple|
+            h[tuple] ||= {}
+          end
+          (leaf[:___routes] ||= []) << [i, route]
+        end
+        root
+      end
+
+      def cache
+        @cache ||= build_cache
+      end
+    end
+  end
+end
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
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
diff --git a/actionpack/lib/action_dispatch/journey/nodes/node.rb b/actionpack/lib/action_dispatch/journey/nodes/node.rb
new file mode 100644
index 0000000000..16d6cb8f0e
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/nodes/node.rb
@@ -0,0 +1,124 @@
+require 'action_dispatch/journey/visitors'
+
+module ActionDispatch
+  module Journey
+    module Nodes
+      class Node # :nodoc:
+        include Enumerable
+
+        attr_accessor :left, :memo
+
+        def initialize left
+          @left = left
+          @memo = nil
+        end
+
+        def each(&block)
+          Visitors::Each.new(block).accept(self)
+        end
+
+        def to_s
+          Visitors::String.new.accept(self)
+        end
+
+        def to_dot
+          Visitors::Dot.new.accept(self)
+        end
+
+        def to_sym
+          name.to_sym
+        end
+
+        def name
+          left.tr '*:', ''
+        end
+
+        def type
+          raise NotImplementedError
+        end
+
+        def symbol?; false; end
+        def literal?; false; end
+      end
+
+      class Terminal < Node
+        alias :symbol :left
+      end
+
+      class Literal < Terminal
+        def literal?; true; end
+        def type; :LITERAL; end
+      end
+
+      class Dummy < Literal
+        def initialize x = Object.new
+          super
+        end
+
+        def literal?; false; end
+      end
+
+      %w{ Symbol Slash Dot }.each do |t|
+        class_eval <<-eoruby, __FILE__, __LINE__ + 1
+          class #{t} < Terminal;
+            def type; :#{t.upcase}; end
+          end
+        eoruby
+      end
+
+      class Symbol < Terminal
+        attr_accessor :regexp
+        alias :symbol :regexp
+
+        DEFAULT_EXP = /[^\.\/\?]+/
+        def initialize left
+          super
+          @regexp = DEFAULT_EXP
+        end
+
+        def default_regexp?
+          regexp == DEFAULT_EXP
+        end
+
+        def symbol?; true; end
+      end
+
+      class Unary < Node
+        def children; [left] end
+      end
+
+      class Group < Unary
+        def type; :GROUP; end
+      end
+
+      class Star < Unary
+        def type; :STAR; end
+      end
+
+      class Binary < Node
+        attr_accessor :right
+
+        def initialize left, right
+          super(left)
+          @right = right
+        end
+
+        def children; [left, right] end
+      end
+
+      class Cat < Binary
+        def type; :CAT; end
+      end
+
+      class Or < Node
+        attr_reader :children
+
+        def initialize children
+          @children = children
+        end
+
+        def type; :OR; end
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/parser.rb b/actionpack/lib/action_dispatch/journey/parser.rb
new file mode 100644
index 0000000000..2489cd61eb
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/parser.rb
@@ -0,0 +1,206 @@
+#
+# DO NOT MODIFY!!!!
+# This file is automatically generated by Racc 1.4.9
+# from Racc grammer file "".
+#
+
+require 'racc/parser.rb'
+
+
+require 'action_dispatch/journey/parser_extras'
+module ActionDispatch
+  module Journey
+    class Parser < Racc::Parser
+##### State transition tables begin ###
+
+racc_action_table = [
+    17,    21,    13,    15,    14,     7,   nil,    16,     8,    19,
+    13,    15,    14,     7,    23,    16,     8,    19,    13,    15,
+    14,     7,   nil,    16,     8,    13,    15,    14,     7,   nil,
+    16,     8,    13,    15,    14,     7,   nil,    16,     8 ]
+
+racc_action_check = [
+     1,    17,     1,     1,     1,     1,   nil,     1,     1,     1,
+    20,    20,    20,    20,    20,    20,    20,    20,     7,     7,
+     7,     7,   nil,     7,     7,    19,    19,    19,    19,   nil,
+    19,    19,     0,     0,     0,     0,   nil,     0,     0 ]
+
+racc_action_pointer = [
+    30,     0,   nil,   nil,   nil,   nil,   nil,    16,   nil,   nil,
+   nil,   nil,   nil,   nil,   nil,   nil,   nil,     1,   nil,    23,
+     8,   nil,   nil,   nil ]
+
+racc_action_default = [
+   -18,   -18,    -2,    -3,    -4,    -5,    -6,   -18,    -9,   -10,
+   -11,   -12,   -13,   -14,   -15,   -16,   -17,   -18,    -1,   -18,
+   -18,    24,    -8,    -7 ]
+
+racc_goto_table = [
+    18,     1,   nil,   nil,   nil,   nil,   nil,   nil,    20,   nil,
+   nil,   nil,   nil,   nil,   nil,   nil,   nil,   nil,    22,    18 ]
+
+racc_goto_check = [
+     2,     1,   nil,   nil,   nil,   nil,   nil,   nil,     1,   nil,
+   nil,   nil,   nil,   nil,   nil,   nil,   nil,   nil,     2,     2 ]
+
+racc_goto_pointer = [
+   nil,     1,    -1,   nil,   nil,   nil,   nil,   nil,   nil,   nil,
+   nil ]
+
+racc_goto_default = [
+   nil,   nil,     2,     3,     4,     5,     6,     9,    10,    11,
+    12 ]
+
+racc_reduce_table = [
+  0, 0, :racc_error,
+  2, 11, :_reduce_1,
+  1, 11, :_reduce_2,
+  1, 11, :_reduce_none,
+  1, 12, :_reduce_none,
+  1, 12, :_reduce_none,
+  1, 12, :_reduce_none,
+  3, 15, :_reduce_7,
+  3, 13, :_reduce_8,
+  1, 16, :_reduce_9,
+  1, 14, :_reduce_none,
+  1, 14, :_reduce_none,
+  1, 14, :_reduce_none,
+  1, 14, :_reduce_none,
+  1, 19, :_reduce_14,
+  1, 17, :_reduce_15,
+  1, 18, :_reduce_16,
+  1, 20, :_reduce_17 ]
+
+racc_reduce_n = 18
+
+racc_shift_n = 24
+
+racc_token_table = {
+  false => 0,
+  :error => 1,
+  :SLASH => 2,
+  :LITERAL => 3,
+  :SYMBOL => 4,
+  :LPAREN => 5,
+  :RPAREN => 6,
+  :DOT => 7,
+  :STAR => 8,
+  :OR => 9 }
+
+racc_nt_base = 10
+
+racc_use_result_var = true
+
+Racc_arg = [
+  racc_action_table,
+  racc_action_check,
+  racc_action_default,
+  racc_action_pointer,
+  racc_goto_table,
+  racc_goto_check,
+  racc_goto_default,
+  racc_goto_pointer,
+  racc_nt_base,
+  racc_reduce_table,
+  racc_token_table,
+  racc_shift_n,
+  racc_reduce_n,
+  racc_use_result_var ]
+
+Racc_token_to_s_table = [
+  "$end",
+  "error",
+  "SLASH",
+  "LITERAL",
+  "SYMBOL",
+  "LPAREN",
+  "RPAREN",
+  "DOT",
+  "STAR",
+  "OR",
+  "$start",
+  "expressions",
+  "expression",
+  "or",
+  "terminal",
+  "group",
+  "star",
+  "symbol",
+  "literal",
+  "slash",
+  "dot" ]
+
+Racc_debug_parser = false
+
+##### State transition tables end #####
+
+# reduce 0 omitted
+
+def _reduce_1(val, _values, result)
+ result = Cat.new(val.first, val.last)
+    result
+end
+
+def _reduce_2(val, _values, result)
+ result = val.first
+    result
+end
+
+# reduce 3 omitted
+
+# reduce 4 omitted
+
+# reduce 5 omitted
+
+# reduce 6 omitted
+
+def _reduce_7(val, _values, result)
+ result = Group.new(val[1])
+    result
+end
+
+def _reduce_8(val, _values, result)
+ result = Or.new([val.first, val.last])
+    result
+end
+
+def _reduce_9(val, _values, result)
+ result = Star.new(Symbol.new(val.last))
+    result
+end
+
+# reduce 10 omitted
+
+# reduce 11 omitted
+
+# reduce 12 omitted
+
+# reduce 13 omitted
+
+def _reduce_14(val, _values, result)
+ result = Slash.new('/')
+    result
+end
+
+def _reduce_15(val, _values, result)
+ result = Symbol.new(val.first)
+    result
+end
+
+def _reduce_16(val, _values, result)
+ result = Literal.new(val.first)
+    result
+end
+
+def _reduce_17(val, _values, result)
+ result = Dot.new(val.first)
+    result
+end
+
+def _reduce_none(val, _values, result)
+  val[0]
+end
+
+    end   # class Parser
+    end   # module Journey
+  end   # module ActionDispatch
diff --git a/actionpack/lib/action_dispatch/journey/parser.y b/actionpack/lib/action_dispatch/journey/parser.y
new file mode 100644
index 0000000000..a2e1afed32
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/parser.y
@@ -0,0 +1,47 @@
+class ActionDispatch::Journey::Parser
+
+token SLASH LITERAL SYMBOL LPAREN RPAREN DOT STAR OR
+
+rule
+  expressions
+    : expressions expression  { result = Cat.new(val.first, val.last) }
+    | expression              { result = val.first }
+    | or
+    ;
+  expression
+    : terminal
+    | group
+    | star
+    ;
+  group
+    : LPAREN expressions RPAREN { result = Group.new(val[1]) }
+    ;
+  or
+    : expressions OR expression { result = Or.new([val.first, val.last]) }
+    ;
+  star
+    : STAR       { result = Star.new(Symbol.new(val.last)) }
+    ;
+  terminal
+    : symbol
+    | literal
+    | slash
+    | dot
+    ;
+  slash
+    : SLASH              { result = Slash.new('/') }
+    ;
+  symbol
+    : SYMBOL             { result = Symbol.new(val.first) }
+    ;
+  literal
+    : LITERAL            { result = Literal.new(val.first) }
+  dot
+    : DOT                { result = Dot.new(val.first) }
+    ;
+
+end
+
+---- header
+
+require 'action_dispatch/journey/parser_extras'
diff --git a/actionpack/lib/action_dispatch/journey/parser_extras.rb b/actionpack/lib/action_dispatch/journey/parser_extras.rb
new file mode 100644
index 0000000000..43f9beda12
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/parser_extras.rb
@@ -0,0 +1,23 @@
+require 'action_dispatch/journey/scanner'
+require 'action_dispatch/journey/nodes/node'
+
+module ActionDispatch
+  module Journey
+    class Parser < Racc::Parser
+      include Journey::Nodes
+
+      def initialize
+        @scanner = Scanner.new
+      end
+
+      def parse string
+        @scanner.scan_setup string
+        do_parse
+      end
+
+      def next_token
+        @scanner.next_token
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/path/pattern.rb b/actionpack/lib/action_dispatch/journey/path/pattern.rb
new file mode 100644
index 0000000000..e14168aeb2
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/path/pattern.rb
@@ -0,0 +1,195 @@
+module ActionDispatch
+  module Journey
+    module Path
+      class Pattern
+        attr_reader :spec, :requirements, :anchored
+
+        def initialize strexp
+          parser = Journey::Parser.new
+
+          @anchored = true
+
+          case strexp
+          when String
+            @spec         = parser.parse strexp
+            @requirements = {}
+            @separators   = "/.?"
+          when Router::Strexp
+            @spec         = parser.parse strexp.path
+            @requirements = strexp.requirements
+            @separators   = strexp.separators.join
+            @anchored     = strexp.anchor
+          else
+            raise "wtf bro: #{strexp}"
+          end
+
+          @names          = nil
+          @optional_names = nil
+          @required_names = nil
+          @re             = nil
+          @offsets        = nil
+        end
+
+        def ast
+          @spec.grep(Nodes::Symbol).each do |node|
+            re = @requirements[node.to_sym]
+            node.regexp = re if re
+          end
+
+          @spec.grep(Nodes::Star).each do |node|
+            node = node.left
+            node.regexp = @requirements[node.to_sym] || /(.+)/
+          end
+
+          @spec
+        end
+
+        def names
+          @names ||= spec.grep(Nodes::Symbol).map { |n| n.name }
+        end
+
+        def required_names
+          @required_names ||= names - optional_names
+        end
+
+        def optional_names
+          @optional_names ||= spec.grep(Nodes::Group).map { |group|
+            group.grep(Nodes::Symbol)
+          }.flatten.map { |n| n.name }.uniq
+        end
+
+        class RegexpOffsets < Journey::Visitors::Visitor # :nodoc:
+          attr_reader :offsets
+
+          def initialize matchers
+            @matchers      = matchers
+            @capture_count = [0]
+          end
+
+          def visit node
+            super
+            @capture_count
+          end
+
+          def visit_SYMBOL node
+            node = node.to_sym
+
+            if @matchers.key? node
+              re = /#{@matchers[node]}|/
+              @capture_count.push((re.match('').length - 1) + (@capture_count.last || 0))
+            else
+              @capture_count << (@capture_count.last || 0)
+            end
+          end
+        end
+
+        class AnchoredRegexp < Journey::Visitors::Visitor # :nodoc:
+          def initialize separator, matchers
+            @separator = separator
+            @matchers  = matchers
+            @separator_re = "([^#{separator}]+)"
+            super()
+          end
+
+          def accept node
+            %r{\A#{visit node}\Z}
+          end
+
+          def visit_CAT node
+            [visit(node.left), visit(node.right)].join
+          end
+
+          def visit_SYMBOL node
+            node = node.to_sym
+
+            return @separator_re unless @matchers.key? node
+
+            re = @matchers[node]
+            "(#{re})"
+          end
+
+          def visit_GROUP node
+            "(?:#{visit node.left})?"
+          end
+
+          def visit_LITERAL node
+            Regexp.escape node.left
+          end
+          alias :visit_DOT :visit_LITERAL
+
+          def visit_SLASH node
+            node.left
+          end
+
+          def visit_STAR node
+            re = @matchers[node.left.to_sym] || '.+'
+            "(#{re})"
+          end
+        end
+
+        class UnanchoredRegexp < AnchoredRegexp # :nodoc:
+          def accept node
+            %r{\A#{visit node}}
+          end
+        end
+
+        class MatchData
+          attr_reader :names
+
+          def initialize names, offsets, match
+            @names   = names
+            @offsets = offsets
+            @match   = match
+          end
+
+          def captures
+            (length - 1).times.map { |i| self[i + 1] }
+          end
+
+          def [] x
+            idx = @offsets[x - 1] + x
+            @match[idx]
+          end
+
+          def length
+            @offsets.length
+          end
+
+          def post_match
+            @match.post_match
+          end
+
+          def to_s
+            @match.to_s
+          end
+        end
+
+        def match other
+          return unless match = to_regexp.match(other)
+          MatchData.new names, offsets, match
+        end
+        alias :=~ :match
+
+        def source
+          to_regexp.source
+        end
+
+        def to_regexp
+          @re ||= regexp_visitor.new(@separators, @requirements).accept spec
+        end
+
+        private
+        def regexp_visitor
+          @anchored ? AnchoredRegexp : UnanchoredRegexp
+        end
+
+        def offsets
+          return @offsets if @offsets
+
+          viz = RegexpOffsets.new @requirements
+          @offsets = viz.accept spec
+        end
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/route.rb b/actionpack/lib/action_dispatch/journey/route.rb
new file mode 100644
index 0000000000..04d31cb580
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/route.rb
@@ -0,0 +1,94 @@
+module ActionDispatch
+  module Journey
+    class Route
+      attr_reader :app, :path, :verb, :defaults, :ip, :name
+
+      attr_reader :constraints
+      alias :conditions :constraints
+
+      attr_accessor :precedence
+
+      ##
+      # +path+ is a path constraint.
+      # +constraints+ is a hash of constraints to be applied to this route.
+      def initialize name, app, path, constraints, defaults = {}
+        constraints  = constraints.dup
+        @name        = name
+        @app         = app
+        @path        = path
+        @verb        = constraints[:request_method] || //
+        @ip          = constraints.delete(:ip) || //
+
+        @constraints = constraints
+        @constraints.keep_if { |_,v| Regexp === v || String === v }
+        @defaults    = defaults
+        @required_defaults = nil
+        @required_parts    = nil
+        @parts             = nil
+        @decorated_ast     = nil
+        @precedence        = 0
+      end
+
+      def ast
+        return @decorated_ast if @decorated_ast
+
+        @decorated_ast = path.ast
+        @decorated_ast.grep(Nodes::Terminal).each { |n| n.memo = self }
+        @decorated_ast
+      end
+
+      def requirements # :nodoc:
+        # needed for rails `rake routes`
+        path.requirements.merge(@defaults).delete_if { |_,v|
+          /.+?/ == v
+        }
+      end
+
+      def segments
+        @path.names
+      end
+
+      def required_keys
+        path.required_names.map { |x| x.to_sym } + required_defaults.keys
+      end
+
+      def score constraints
+        required_keys = path.required_names
+        supplied_keys = constraints.map { |k,v| v && k.to_s }.compact
+
+        return -1 unless (required_keys - supplied_keys).empty?
+
+        score = (supplied_keys & path.names).length
+        score + (required_defaults.length * 2)
+      end
+
+      def parts
+        @parts ||= segments.map { |n| n.to_sym }
+      end
+      alias :segment_keys :parts
+
+      def format path_options
+        path_options.delete_if do |key, value|
+          value.to_s == defaults[key].to_s && !required_parts.include?(key)
+        end
+
+        Visitors::Formatter.new(path_options).accept(path.spec)
+      end
+
+      def optional_parts
+        path.optional_names.map { |n| n.to_sym }
+      end
+
+      def required_parts
+        @required_parts ||= path.required_names.map { |n| n.to_sym }
+      end
+
+      def required_defaults
+        @required_defaults ||= begin
+          matches = parts
+          @defaults.dup.delete_if { |k,_| matches.include? k }
+        end
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/router.rb b/actionpack/lib/action_dispatch/journey/router.rb
new file mode 100644
index 0000000000..fcf16c1272
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/router.rb
@@ -0,0 +1,168 @@
+require 'action_dispatch/journey/core-ext/hash'
+require 'action_dispatch/journey/router/utils'
+require 'action_dispatch/journey/router/strexp'
+require 'action_dispatch/journey/routes'
+require 'action_dispatch/journey/formatter'
+
+before = $-w
+$-w = false
+require 'action_dispatch/journey/parser'
+$-w = before
+
+require 'action_dispatch/journey/route'
+require 'action_dispatch/journey/path/pattern'
+
+module ActionDispatch
+  module Journey
+    class Router
+      class RoutingError < ::StandardError
+      end
+
+      VERSION = '2.0.0'
+
+      class NullReq # :nodoc:
+        attr_reader :env
+        def initialize env
+          @env = env
+        end
+
+        def request_method
+          env['REQUEST_METHOD']
+        end
+
+        def path_info
+          env['PATH_INFO']
+        end
+
+        def ip
+          env['REMOTE_ADDR']
+        end
+
+        def [](k); env[k]; end
+      end
+
+      attr_reader :request_class, :formatter
+      attr_accessor :routes
+
+      def initialize routes, options
+        @options       = options
+        @params_key    = options[:parameters_key]
+        @request_class = options[:request_class] || NullReq
+        @routes        = routes
+      end
+
+      def call env
+        env['PATH_INFO'] = Utils.normalize_path env['PATH_INFO']
+
+        find_routes(env).each do |match, parameters, route|
+          script_name, path_info, set_params = env.values_at('SCRIPT_NAME',
+                                                             'PATH_INFO',
+                                                             @params_key)
+
+          unless route.path.anchored
+            env['SCRIPT_NAME'] = (script_name.to_s + match.to_s).chomp('/')
+            env['PATH_INFO']   = match.post_match
+          end
+
+          env[@params_key] = (set_params || {}).merge parameters
+
+          status, headers, body = route.app.call(env)
+
+          if 'pass' == headers['X-Cascade']
+            env['SCRIPT_NAME'] = script_name
+            env['PATH_INFO']   = path_info
+            env[@params_key]   = set_params
+            next
+          end
+
+          return [status, headers, body]
+        end
+
+        return [404, {'X-Cascade' => 'pass'}, ['Not Found']]
+      end
+
+      def recognize req
+        find_routes(req.env).each do |match, parameters, route|
+          unless route.path.anchored
+            req.env['SCRIPT_NAME'] = match.to_s
+            req.env['PATH_INFO']   = match.post_match.sub(/^([^\/])/, '/\1')
+          end
+
+          yield(route, nil, parameters)
+        end
+      end
+
+      def visualizer
+        tt     = GTG::Builder.new(ast).transition_table
+        groups = partitioned_routes.first.map(&:ast).group_by { |a| a.to_s }
+        asts   = groups.values.map { |v| v.first }
+        tt.visualizer asts
+      end
+
+      private
+
+      def partitioned_routes
+        routes.partitioned_routes
+      end
+
+      def ast
+        routes.ast
+      end
+
+      def simulator
+        routes.simulator
+      end
+
+      def custom_routes
+        partitioned_routes.last
+      end
+
+      def filter_routes path
+        return [] unless ast
+        data = simulator.match(path)
+        data ? data.memos : []
+      end
+
+      def find_routes env
+        req = request_class.new env
+
+        routes = filter_routes(req.path_info).concat custom_routes.find_all { |r|
+          r.path.match(req.path_info)
+        }
+        routes.concat get_routes_as_head(routes)
+
+        routes.sort_by!(&:precedence).select! { |r|
+          r.constraints.all? { |k,v| v === req.send(k) } &&
+            r.verb === req.request_method
+        }
+        routes.reject! { |r| req.ip && !(r.ip === req.ip) }
+
+        routes.map! { |r|
+          match_data  = r.path.match(req.path_info)
+          match_names = match_data.names.map { |n| n.to_sym }
+          match_values = match_data.captures.map { |v| v && Utils.unescape_uri(v) }
+          info = Hash[match_names.zip(match_values).find_all { |_,y| y }]
+
+          [match_data, r.defaults.merge(info), r]
+        }
+      end
+
+      def get_routes_as_head(routes)
+        precedence = (routes.map(&:precedence).max || 0) + 1
+        routes = routes.select { |r|
+          r.verb === "GET" && !(r.verb === "HEAD")
+        }.map! { |r|
+          Route.new(r.name,
+                    r.app,
+                    r.path,
+                    r.conditions.merge(:request_method => "HEAD"),
+                    r.defaults).tap do |route|
+                      route.precedence = r.precedence + precedence
+                    end
+        }
+        routes.flatten!
+        routes
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/router/strexp.rb b/actionpack/lib/action_dispatch/journey/router/strexp.rb
new file mode 100644
index 0000000000..268bb4602f
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/router/strexp.rb
@@ -0,0 +1,24 @@
+module ActionDispatch
+  module Journey
+    class Router
+      class Strexp
+        class << self
+          alias :compile :new
+        end
+
+        attr_reader :path, :requirements, :separators, :anchor
+
+        def initialize path, requirements, separators, anchor = true
+          @path         = path
+          @requirements = requirements
+          @separators   = separators
+          @anchor       = anchor
+        end
+
+        def names
+          @path.scan(/:\w+/).map { |s| s.tr(':', '') }
+        end
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/router/utils.rb b/actionpack/lib/action_dispatch/journey/router/utils.rb
new file mode 100644
index 0000000000..a21b570013
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/router/utils.rb
@@ -0,0 +1,59 @@
+require 'uri'
+
+module ActionDispatch
+  module Journey
+    class Router
+      class Utils
+        # Normalizes URI path.
+        #
+        # Strips off trailing slash and ensures there is a leading slash.
+        #
+        #   normalize_path("/foo")  # => "/foo"
+        #   normalize_path("/foo/") # => "/foo"
+        #   normalize_path("foo")   # => "/foo"
+        #   normalize_path("")      # => "/"
+        def self.normalize_path(path)
+          path = "/#{path}"
+          path.squeeze!('/')
+          path.sub!(%r{/+\Z}, '')
+          path = '/' if path == ''
+          path
+        end
+
+        # URI path and fragment escaping
+        # http://tools.ietf.org/html/rfc3986
+        module UriEscape
+          # Symbol captures can generate multiple path segments, so include /.
+          reserved_segment  = '/'
+          reserved_fragment = '/?'
+          reserved_pchar    = ':@&=+$,;%'
+
+          safe_pchar    = "#{URI::REGEXP::PATTERN::UNRESERVED}#{reserved_pchar}"
+          safe_segment  = "#{safe_pchar}#{reserved_segment}"
+          safe_fragment = "#{safe_pchar}#{reserved_fragment}"
+          if RUBY_VERSION >= '1.9'
+            UNSAFE_SEGMENT  = Regexp.new("[^#{safe_segment}]", false).freeze
+            UNSAFE_FRAGMENT = Regexp.new("[^#{safe_fragment}]", false).freeze
+          else
+            UNSAFE_SEGMENT = Regexp.new("[^#{safe_segment}]", false, 'N').freeze
+            UNSAFE_FRAGMENT = Regexp.new("[^#{safe_fragment}]", false, 'N').freeze
+          end
+        end
+
+        Parser = URI.const_defined?(:Parser) ? URI::Parser.new : URI
+
+        def self.escape_path(path)
+          Parser.escape(path.to_s, UriEscape::UNSAFE_SEGMENT)
+        end
+
+        def self.escape_fragment(fragment)
+          Parser.escape(fragment.to_s, UriEscape::UNSAFE_FRAGMENT)
+        end
+
+        def self.unescape_uri(uri)
+          Parser.unescape(uri)
+        end
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/routes.rb b/actionpack/lib/action_dispatch/journey/routes.rb
new file mode 100644
index 0000000000..f9c4cdbd4b
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/routes.rb
@@ -0,0 +1,77 @@
+module ActionDispatch
+  module Journey
+    ###
+    # The Routing table.  Contains all routes for a system.  Routes can be
+    # added to the table by calling Routes#add_route
+    class Routes
+      include Enumerable
+
+      attr_reader :routes, :named_routes
+
+      def initialize
+        @routes             = []
+        @named_routes       = {}
+        @ast                = nil
+        @partitioned_routes = nil
+        @simulator          = nil
+      end
+
+      def length
+        @routes.length
+      end
+      alias :size :length
+
+      def last
+        @routes.last
+      end
+
+      def each(&block)
+        routes.each(&block)
+      end
+
+      def clear
+        routes.clear
+      end
+
+      def partitioned_routes
+        @partitioned_routes ||= routes.partition { |r|
+          r.path.anchored && r.ast.grep(Nodes::Symbol).all? { |n| n.default_regexp?  }
+        }
+      end
+
+      def ast
+        return @ast if @ast
+        return if partitioned_routes.first.empty?
+
+        asts = partitioned_routes.first.map { |r| r.ast }
+        @ast = Nodes::Or.new(asts)
+      end
+
+      def simulator
+        return @simulator if @simulator
+
+        gtg = GTG::Builder.new(ast).transition_table
+        @simulator = GTG::Simulator.new gtg
+      end
+
+      ###
+      # Add a route to the routing table.
+      def add_route app, path, conditions, defaults, name = nil
+        route = Route.new(name, app, path, conditions, defaults)
+
+        route.precedence = routes.length
+        routes << route
+        named_routes[name] = route if name && !named_routes[name]
+        clear_cache!
+        route
+      end
+
+      private
+      def clear_cache!
+        @ast                = nil
+        @partitioned_routes = nil
+        @simulator          = nil
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/scanner.rb b/actionpack/lib/action_dispatch/journey/scanner.rb
new file mode 100644
index 0000000000..b45d72668b
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/scanner.rb
@@ -0,0 +1,60 @@
+require 'strscan'
+
+module ActionDispatch
+  module Journey
+    class Scanner
+      def initialize
+        @ss = nil
+      end
+
+      def scan_setup str
+        @ss = StringScanner.new str
+      end
+
+      def eos?
+        @ss.eos?
+      end
+
+      def pos
+        @ss.pos
+      end
+
+      def pre_match
+        @ss.pre_match
+      end
+
+      def next_token
+        return if @ss.eos?
+
+        until token = scan || @ss.eos?; end
+        token
+      end
+
+      private
+      def scan
+        case
+          # /
+        when text = @ss.scan(/\//)
+          [:SLASH, text]
+        when text = @ss.scan(/\*\w+/)
+          [:STAR, text]
+        when text = @ss.scan(/\(/)
+          [:LPAREN, text]
+        when text = @ss.scan(/\)/)
+          [:RPAREN, text]
+        when text = @ss.scan(/\|/)
+          [:OR, text]
+        when text = @ss.scan(/\./)
+          [:DOT, text]
+        when text = @ss.scan(/:\w+/)
+          [:SYMBOL, text]
+        when text = @ss.scan(/[\w%\-~]+/)
+          [:LITERAL, text]
+          # any char
+        when text = @ss.scan(/./)
+          [:LITERAL, text]
+        end
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/visitors.rb b/actionpack/lib/action_dispatch/journey/visitors.rb
new file mode 100644
index 0000000000..b3f4796607
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/visitors.rb
@@ -0,0 +1,188 @@
+# encoding: utf-8
+module ActionDispatch
+  module Journey
+    module Visitors
+      class Visitor # :nodoc:
+        DISPATCH_CACHE = Hash.new { |h,k|
+          h[k] = "visit_#{k}"
+        }
+
+        def accept node
+          visit node
+        end
+
+        private
+        def visit node
+          send DISPATCH_CACHE[node.type], node
+        end
+
+        def binary node
+          visit node.left
+          visit node.right
+        end
+        def visit_CAT(n); binary(n); end
+
+        def nary node
+          node.children.each { |c| visit c }
+        end
+        def visit_OR(n); nary(n); end
+
+        def unary node
+          visit node.left
+        end
+        def visit_GROUP(n); unary(n); end
+        def visit_STAR(n); unary(n); end
+
+        def terminal node; end
+        %w{ LITERAL SYMBOL SLASH DOT }.each do |t|
+          class_eval %{ def visit_#{t}(n); terminal(n); end }, __FILE__, __LINE__
+        end
+      end
+
+      ##
+      # Loop through the requirements AST
+      class Each < Visitor # :nodoc:
+        attr_reader :block
+
+        def initialize block
+          @block = block
+        end
+
+        def visit node
+          super
+          block.call node
+        end
+      end
+
+      class String < Visitor
+        private
+
+        def binary node
+          [visit(node.left), visit(node.right)].join
+        end
+
+        def nary node
+          node.children.map { |c| visit c }.join '|'
+        end
+
+        def terminal node
+          node.left
+        end
+
+        def visit_GROUP node
+          "(#{visit node.left})"
+        end
+      end
+
+      ###
+      # Used for formatting urls (url_for)
+      class Formatter < Visitor
+        attr_reader :options, :consumed
+
+        def initialize options
+          @options  = options
+          @consumed = {}
+        end
+
+        private
+        def visit_GROUP node
+          if consumed == options
+            nil
+          else
+            route = visit node.left
+            route.include?("\0") ? nil : route
+          end
+        end
+
+        def terminal node
+          node.left
+        end
+
+        def binary node
+          [visit(node.left), visit(node.right)].join
+        end
+
+        def nary node
+          node.children.map { |c| visit c }.join
+        end
+
+        def visit_SYMBOL node
+          key = node.to_sym
+
+          if value = options[key]
+            consumed[key] = value
+            Router::Utils.escape_path(value)
+          else
+            "\0"
+          end
+        end
+      end
+
+      class Dot < Visitor
+        def initialize
+          @nodes = []
+          @edges = []
+        end
+
+        def accept node
+          super
+          <<-eodot
+  digraph parse_tree {
+    size="8,5"
+    node [shape = none];
+    edge [dir = none];
+    #{@nodes.join "\n"}
+    #{@edges.join("\n")}
+  }
+          eodot
+        end
+
+        private
+        def binary node
+          node.children.each do |c|
+            @edges << "#{node.object_id} -> #{c.object_id};"
+          end
+          super
+        end
+
+        def nary node
+          node.children.each do |c|
+            @edges << "#{node.object_id} -> #{c.object_id};"
+          end
+          super
+        end
+
+        def unary node
+          @edges << "#{node.object_id} -> #{node.left.object_id};"
+          super
+        end
+
+        def visit_GROUP node
+          @nodes << "#{node.object_id} [label=\"()\"];"
+          super
+        end
+
+        def visit_CAT node
+          @nodes << "#{node.object_id} [label=\"○\"];"
+          super
+        end
+
+        def visit_STAR node
+          @nodes << "#{node.object_id} [label=\"*\"];"
+          super
+        end
+
+        def visit_OR node
+          @nodes << "#{node.object_id} [label=\"|\"];"
+          super
+        end
+
+        def terminal node
+          value = node.left
+
+          @nodes << "#{node.object_id} [label=\"#{value}\"];"
+        end
+      end
+    end
+  end
+end
diff --git a/actionpack/lib/action_dispatch/journey/visualizer/fsm.css b/actionpack/lib/action_dispatch/journey/visualizer/fsm.css
new file mode 100644
index 0000000000..50caebaa18
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/visualizer/fsm.css
@@ -0,0 +1,34 @@
+body {
+  font-family: "Helvetica Neue", Helvetica, Arial, Sans-Serif;
+  margin: 0;
+}
+
+h1 {
+  font-size: 2.0em; font-weight: bold; text-align: center;
+  color: white; background-color: black;
+  padding: 5px 0;
+  margin: 0 0 20px;
+}
+
+h2 {
+  text-align: center;
+  display: none;
+  font-size: 0.5em;
+}
+
+div#chart-2 {
+  height: 350px;
+}
+
+.clearfix {display: inline-block; }
+.input { overflow: show;}
+.instruction { color: #666; padding: 0 30px 20px; font-size: 0.9em}
+.instruction p { padding: 0 0 5px; }
+.instruction li { padding: 0 10px 5px; }
+
+.form { background: #EEE; padding: 20px 30px; border-radius: 5px; margin-left: auto; margin-right: auto; width: 500px; margin-bottom: 20px}
+.form p, .form form { text-align: center }
+.form form {padding: 0 10px 5px; }
+.form .fun_routes { font-size: 0.9em;}
+.form .fun_routes a { margin: 0 5px 0 0; }
+
diff --git a/actionpack/lib/action_dispatch/journey/visualizer/fsm.js b/actionpack/lib/action_dispatch/journey/visualizer/fsm.js
new file mode 100644
index 0000000000..d9bcaef928
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/visualizer/fsm.js
@@ -0,0 +1,134 @@
+function tokenize(input, callback) {
+  while(input.length > 0) {
+    callback(input.match(/^[\/\.\?]|[^\/\.\?]+/)[0]);
+    input = input.replace(/^[\/\.\?]|[^\/\.\?]+/, '');
+  }
+}
+
+var graph = d3.select("#chart-2 svg");
+var svg_edges = {};
+var svg_nodes = {};
+
+graph.selectAll("g.edge").each(function() {
+  var node  = d3.select(this);
+  var index = node.select("title").text().split("->");
+  var left  = parseInt(index[0]);
+  var right = parseInt(index[1]);
+
+  if(!svg_edges[left]) { svg_edges[left] = {} }
+  svg_edges[left][right] = node;
+});
+
+graph.selectAll("g.node").each(function() {
+  var node  = d3.select(this);
+  var index = parseInt(node.select("title").text());
+  svg_nodes[index] = node;
+});
+
+function reset_graph() {
+  for(var key in svg_edges) {
+    for(var mkey in svg_edges[key]) {
+      var node = svg_edges[key][mkey];
+      var path = node.select("path");
+      var arrow = node.select("polygon");
+      path.style("stroke", "black");
+      arrow.style("stroke", "black").style("fill", "black");
+    }
+  }
+
+  for(var key in svg_nodes) {
+    var node = svg_nodes[key];
+    node.select('ellipse').style("fill", "white");
+    node.select('polygon').style("fill", "white");
+  }
+  return false;
+}
+
+function highlight_edge(from, to) {
+  var node = svg_edges[from][to];
+  var path = node.select("path");
+  var arrow = node.select("polygon");
+
+  path
+    .transition().duration(500)
+    .style("stroke", "green");
+
+  arrow
+    .transition().duration(500)
+    .style("stroke", "green").style("fill", "green");
+}
+
+function highlight_state(index, color) {
+  if(!color) { color = "green"; }
+
+  svg_nodes[index].select('ellipse')
+    .style("fill", "white")
+    .transition().duration(500)
+    .style("fill", color);
+}
+
+function highlight_finish(index) {
+  svg_nodes[index].select('polygon')
+    .style("fill", "while")
+    .transition().duration(500)
+    .style("fill", "blue");
+}
+
+function match(input) {
+  reset_graph();
+  var table         = tt();
+  var states        = [0];
+  var regexp_states = table['regexp_states'];
+  var string_states = table['string_states'];
+  var accepting     = table['accepting'];
+
+  highlight_state(0);
+
+  tokenize(input, function(token) {
+    var new_states = [];
+    for(var key in states) {
+      var state = states[key];
+
+      if(string_states[state] && string_states[state][token]) {
+        var new_state = string_states[state][token];
+        highlight_edge(state, new_state);
+        highlight_state(new_state);
+        new_states.push(new_state);
+      }
+
+      if(regexp_states[state]) {
+        for(var key in regexp_states[state]) {
+          var re = new RegExp("^" + key + "$");
+          if(re.test(token)) {
+            var new_state = regexp_states[state][key];
+            highlight_edge(state, new_state);
+            highlight_state(new_state);
+            new_states.push(new_state);
+          }
+        }
+      }
+    }
+
+    if(new_states.length == 0) {
+      return;
+    }
+    states = new_states;
+  });
+
+  for(var key in states) {
+    var state = states[key];
+    if(accepting[state]) {
+      for(var mkey in svg_edges[state]) {
+        if(!regexp_states[mkey] && !string_states[mkey]) {
+          highlight_edge(state, mkey);
+          highlight_finish(mkey);
+        }
+      }
+    } else {
+      highlight_state(state, "red");
+    }
+  }
+
+  return false;
+}
+
diff --git a/actionpack/lib/action_dispatch/journey/visualizer/index.html.erb b/actionpack/lib/action_dispatch/journey/visualizer/index.html.erb
new file mode 100644
index 0000000000..6aff10956a
--- /dev/null
+++ b/actionpack/lib/action_dispatch/journey/visualizer/index.html.erb
@@ -0,0 +1,52 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title><%= title %></title>
+    <link rel="stylesheet" href="https://raw.github.com/gist/1706081/af944401f75ea20515a02ddb3fb43d23ecb8c662/reset.css" type="text/css">
+    <style>
+      <% stylesheets.each do |style| %>
+        <%= style %>
+      <% end %>
+    </style>
+    <script src="https://raw.github.com/gist/1706081/df464722a05c3c2bec450b7b5c8240d9c31fa52d/d3.min.js" type="text/javascript"></script>
+  </head>
+  <body>
+    <div id="wrapper">
+      <h1>Routes FSM with NFA simulation</h1>
+      <div class="instruction form">
+        <p>
+        Type a route in to the box and click "simulate".
+        </p>
+        <form onsubmit="return match(this.route.value);">
+          <input type="text" size="30" name="route" value="/articles/new" />
+          <button>simulate</button>
+          <input type="reset" value="reset" onclick="return reset_graph();"/>
+        </form>
+        <p class="fun_routes">
+          Some fun routes to try:
+          <% fun_routes.each do |path| %>
+             <a href="#" onclick="document.forms[0].elements[0].value=this.text.replace(/^\s+|\s+$/g,''); return match(this.text.replace(/^\s+|\s+$/g,''));">
+               <%= path %>
+             </a>
+          <% end %>
+        </p>
+      </div>
+      <div class='chart' id='chart-2'>
+        <%= svg %>
+      </div>
+      <div class="instruction">
+        <p>
+        This is a FSM for a system that has the following routes:
+        </p>
+        <ul>
+          <% paths.each do |route| %>
+            <li><%= route %></li>
+          <% end %>
+        </ul>
+      </div>
+    </div>
+    <% javascripts.each do |js| %>
+      <script><%= js %></script>
+    <% end %>
+  </body>
+</html>
diff --git a/actionpack/lib/action_dispatch/routing/route_set.rb b/actionpack/lib/action_dispatch/routing/route_set.rb
index eb9d4b24f1..b1959e388c 100644
--- a/actionpack/lib/action_dispatch/routing/route_set.rb
+++ b/actionpack/lib/action_dispatch/routing/route_set.rb
@@ -1,4 +1,4 @@
-require 'journey'
+require 'action_dispatch/journey'
 require 'forwardable'
 require 'thread_safe'
 require 'active_support/core_ext/object/to_query'