drop object allocation during routes setup

This commit introduces a functional Path AST visitor and implements
`each` on the AST in terms of the functional visitor.  The functional
visitor doesn't maintain state, so we only need to allocate one of them.

Given this benchmark route file:

```ruby
require 'action_pack'
require 'action_dispatch'

route_set = ActionDispatch::Routing::RouteSet.new
routes = ActionDispatch::Routing::Mapper.new route_set

ObjectSpace::AllocationTracer.setup(%i{path line type})

result = ObjectSpace::AllocationTracer.trace do
  500.times{|i|
    routes.resource :omglol
  }
end

result.find_all { |k,v| k.first =~ /git\/rails/ }.sort_by { |k,v|
  v.first
}.each { |k,v|
  p k => v
}
```

node.rb line 17 was in our top 3 allocation spot:

```
{["/Users/aaron/git/rails/actionpack/lib/action_dispatch/journey/nodes/node.rb", 17, :T_OBJECT]=>[31526, 0, 28329, 0, 2, 1123160]}
{["/Users/aaron/git/rails/actionpack/lib/action_dispatch/routing/mapper.rb", 2080, :T_IMEMO]=>[34002, 0, 30563, 0, 2, 1211480]}
{["/Users/aaron/git/rails/actionpack/lib/action_dispatch/routing/mapper.rb", 2071, :T_IMEMO]=>[121934, 1, 109608, 0, 7, 4344400]}
```

This commit eliminates allocations at that place.

2 files changed, 89 insertions, 44 deletions

diff --git a/actionpack/lib/action_dispatch/journey/nodes/node.rb b/actionpack/lib/action_dispatch/journey/nodes/node.rb
index 2b57c368dc..542e8c6577 100644
--- a/actionpack/lib/action_dispatch/journey/nodes/node.rb
+++ b/actionpack/lib/action_dispatch/journey/nodes/node.rb
@@ -14,15 +14,15 @@ module ActionDispatch
         end
 
         def each(&block)
-          Visitors::Each.new(block).accept(self)
+          Visitors::Each::INSTANCE.accept(self, block)
         end
 
         def to_s
-          Visitors::String.new.accept(self)
+          Visitors::String::INSTANCE.accept(self, '')
         end
 
         def to_dot
-          Visitors::Dot.new.accept(self)
+          Visitors::Dot::INSTANCE.accept(self)
         end
 
         def to_sym
diff --git a/actionpack/lib/action_dispatch/journey/visitors.rb b/actionpack/lib/action_dispatch/journey/visitors.rb
index 52b4c8b489..537c9b2f5c 100644
--- a/actionpack/lib/action_dispatch/journey/visitors.rb
+++ b/actionpack/lib/action_dispatch/journey/visitors.rb
@@ -92,6 +92,45 @@ module ActionDispatch
           end
       end
 
+      class FunctionalVisitor # :nodoc:
+        DISPATCH_CACHE = {}
+
+        def accept(node, seed)
+          visit(node, seed)
+        end
+
+        def visit node, seed
+          send(DISPATCH_CACHE[node.type], node, seed)
+        end
+
+        def binary(node, seed)
+          visit(node.right, visit(node.left, seed))
+        end
+        def visit_CAT(n, seed); binary(n, seed); end
+
+        def nary(node, seed)
+          node.children.inject(seed) { |s, c| visit(c, s) }
+        end
+        def visit_OR(n, seed); nary(n, seed); end
+
+        def unary(node, seed)
+          visit(node.left, seed)
+        end
+        def visit_GROUP(n, seed); unary(n, seed); end
+        def visit_STAR(n, seed); unary(n, seed); end
+
+        def terminal(node, seed);   seed; end
+        def visit_LITERAL(n, seed); terminal(n, seed); end
+        def visit_SYMBOL(n, seed);  terminal(n, seed); end
+        def visit_SLASH(n, seed);   terminal(n, seed); end
+        def visit_DOT(n, seed);     terminal(n, seed); end
+
+        instance_methods(false).each do |pim|
+          next unless pim =~ /^visit_(.*)$/
+          DISPATCH_CACHE[$1.to_sym] = pim
+        end
+      end
+
       class FormatBuilder < Visitor # :nodoc:
         def accept(node); Journey::Format.new(super); end
         def terminal(node); [node.left]; end
@@ -117,104 +156,110 @@ module ActionDispatch
       end
 
       # Loop through the requirements AST
-      class Each < Visitor # :nodoc:
-        attr_reader :block
-
-        def initialize(block)
-          @block = block
-        end
-
-        def visit(node)
+      class Each < FunctionalVisitor # :nodoc:
+        def visit(node, block)
           block.call(node)
           super
         end
+
+        INSTANCE = new
       end
 
-      class String < Visitor # :nodoc:
+      class String < FunctionalVisitor # :nodoc:
         private
 
-        def binary(node)
-          [visit(node.left), visit(node.right)].join
+        def binary(node, seed)
+          visit(node.right, visit(node.left, seed))
         end
 
-        def nary(node)
-          node.children.map { |c| visit(c) }.join '|'
+        def nary(node, seed)
+          last_child = node.children.last
+          node.children.inject(seed) { |s, c|
+            string = visit(c, s)
+            string << "|".freeze unless last_child == c
+            string
+          }
         end
 
-        def terminal(node)
-          node.left
+        def terminal(node, seed)
+          seed + node.left
         end
 
-        def visit_GROUP(node)
-          "(#{visit(node.left)})"
+        def visit_GROUP(node, seed)
+          visit(node.left, seed << "(".freeze) << ")".freeze
         end
+
+        INSTANCE = new
       end
 
-      class Dot < Visitor # :nodoc:
+      class Dot < FunctionalVisitor # :nodoc:
         def initialize
           @nodes = []
           @edges = []
         end
 
-        def accept(node)
+        def accept(node, seed = [[], []])
           super
+          nodes, edges = seed
           <<-eodot
   digraph parse_tree {
     size="8,5"
     node [shape = none];
     edge [dir = none];
-    #{@nodes.join "\n"}
-    #{@edges.join("\n")}
+    #{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
+          def binary(node, seed)
+            seed.last.concat node.children.map { |c|
+              "#{node.object_id} -> #{c.object_id};"
+            }
             super
           end
 
-          def nary(node)
-            node.children.each do |c|
-              @edges << "#{node.object_id} -> #{c.object_id};"
-            end
+          def nary(node, seed)
+            seed.last.concat node.children.map { |c|
+              "#{node.object_id} -> #{c.object_id};"
+            }
             super
           end
 
-          def unary(node)
-            @edges << "#{node.object_id} -> #{node.left.object_id};"
+          def unary(node, seed)
+            seed.last << "#{node.object_id} -> #{node.left.object_id};"
             super
           end
 
-          def visit_GROUP(node)
-            @nodes << "#{node.object_id} [label=\"()\"];"
+          def visit_GROUP(node, seed)
+            seed.first << "#{node.object_id} [label=\"()\"];"
             super
           end
 
-          def visit_CAT(node)
-            @nodes << "#{node.object_id} [label=\"○\"];"
+          def visit_CAT(node, seed)
+            seed.first << "#{node.object_id} [label=\"○\"];"
             super
           end
 
-          def visit_STAR(node)
-            @nodes << "#{node.object_id} [label=\"*\"];"
+          def visit_STAR(node, seed)
+            seed.first << "#{node.object_id} [label=\"*\"];"
             super
           end
 
-          def visit_OR(node)
-            @nodes << "#{node.object_id} [label=\"|\"];"
+          def visit_OR(node, seed)
+            seed.first << "#{node.object_id} [label=\"|\"];"
             super
           end
 
-          def terminal(node)
+          def terminal(node, seed)
             value = node.left
 
-            @nodes << "#{node.object_id} [label=\"#{value}\"];"
+            seed.first << "#{node.object_id} [label=\"#{value}\"];"
+            seed
           end
+          INSTANCE = new
       end
     end
   end