Use a custom route vistor for optimized route generation

Using a Regexp to replace dynamic segments in a path string is fraught
with difficulty and can lead to odd edge cases like #13349. Since we
already have a parsed representation of the path it makes sense to use
that to generate an array of segments that can be used to build an
optimized route's path quickly.

Tests on a simple route (e.g. /posts/:id) show a speedup of 35%:
https://gist.github.com/pixeltrix/8261932

Calculating -------------------------------------
    Current Helper:       5274 i/100ms
    New Helper:           8050 i/100ms
-------------------------------------------------
    Current Helper:     79263.6 (±3.7%) i/s -     395550 in   4.997252s
    New Helper:        153464.5 (±4.9%) i/s -     772800 in   5.047834s

Tests on a more complex route show even an greater performance boost:
https://gist.github.com/pixeltrix/8261957

Calculating -------------------------------------
    Current Helper:       2367 i/100ms
    New Helper:           5382 i/100ms
-------------------------------------------------
    Current Helper:     29506.0 (±3.2%) i/s -     149121 in   5.059294s
    New Helper:         78815.5 (±4.1%) i/s -     398268 in   5.062161s

It also has the added benefit of fixing the edge cases described above.

Fixes #13349

4 files changed, 65 insertions, 31 deletions

diff --git a/actionpack/CHANGELOG.md b/actionpack/CHANGELOG.md
index 922fa949a9..35b9417b7d 100644
--- a/actionpack/CHANGELOG.md
+++ b/actionpack/CHANGELOG.md
@@ -1,3 +1,7 @@
+*   Use a custom route visitor for optimized url generation. Fixes #13349.
+
+    *Andrew White*
+
 *   Allow engine root relative redirects using an empty string.
 
     Example:
diff --git a/actionpack/lib/action_dispatch/journey/visitors.rb b/actionpack/lib/action_dispatch/journey/visitors.rb
index 9e66cab052..daade5bb74 100644
--- a/actionpack/lib/action_dispatch/journey/visitors.rb
+++ b/actionpack/lib/action_dispatch/journey/visitors.rb
@@ -77,12 +77,32 @@ module ActionDispatch
         end
       end
 
-      class OptimizedPath < String # :nodoc:
+      class OptimizedPath < Visitor # :nodoc:
+        def accept(node)
+          Array(visit(node))
+        end
+
         private
 
-        def visit_GROUP(node)
-          ""
-        end
+          def visit_CAT(node)
+            [visit(node.left), visit(node.right)].flatten
+          end
+
+          def visit_SYMBOL(node)
+            node.left[1..-1].to_sym
+          end
+
+          def visit_STAR(node)
+            visit(node.left)
+          end
+
+          def visit_GROUP(node)
+            []
+          end
+
+          %w{ LITERAL SLASH DOT }.each do |t|
+            class_eval %{ def visit_#{t}(n); n.left; end }, __FILE__, __LINE__
+          end
       end
 
       # Used for formatting urls (url_for)
diff --git a/actionpack/lib/action_dispatch/routing/route_set.rb b/actionpack/lib/action_dispatch/routing/route_set.rb
index 04faabef37..bbdcc7c5d3 100644
--- a/actionpack/lib/action_dispatch/routing/route_set.rb
+++ b/actionpack/lib/action_dispatch/routing/route_set.rb
@@ -163,9 +163,10 @@ module ActionDispatch
 
             def initialize(route, options)
               super
-              @path_parts   = @route.required_parts
-              @arg_size     = @path_parts.size
-              @string_route = @route.optimized_path
+              @klass          = Journey::Router::Utils
+              @required_parts = @route.required_parts
+              @arg_size       = @required_parts.size
+              @optimized_path = @route.optimized_path
             end
 
             def call(t, args)
@@ -182,42 +183,39 @@ module ActionDispatch
             private
 
             def optimized_helper(args)
-              path = @string_route.dup
-              klass = Journey::Router::Utils
+              params = Hash[parameterize_args(args)]
+              missing_keys = missing_keys(params)
 
-              @path_parts.zip(args) do |part, arg|
-                parameterized_arg = arg.to_param
+              unless missing_keys.empty?
+                raise_generation_error(params, missing_keys)
+              end
 
-                if parameterized_arg.nil? || parameterized_arg.empty?
-                  raise_generation_error(args)
-                end
+              @optimized_path.map{ |segment| replace_segment(params, segment) }.join
+            end
 
-                # Replace each route parameter
-                # e.g. :id for regular parameter or *path for globbing
-                # with ruby string interpolation code
-                path.gsub!(/(\*|:)#{part}/, klass.escape_fragment(parameterized_arg))
-              end
-              path
+            def replace_segment(params, segment)
+              Symbol === segment ? @klass.escape_fragment(params[segment]) : segment
             end
 
             def optimize_routes_generation?(t)
               t.send(:optimize_routes_generation?)
             end
 
-            def raise_generation_error(args)
-              parts, missing_keys = [], []
-
-              @path_parts.zip(args) do |part, arg|
-                parameterized_arg = arg.to_param
-
-                if parameterized_arg.nil? || parameterized_arg.empty?
-                  missing_keys << part
+            def parameterize_args(args)
+              [].tap do |parameterized_args|
+                @required_parts.zip(args) do |part, arg|
+                  parameterized_arg = arg.to_param
+                  parameterized_args << [part, parameterized_arg]
                 end
-
-                parts << [part, arg]
               end
+            end
+
+            def missing_keys(args)
+              args.select{ |part, arg| arg.nil? || arg.empty? }.keys
+            end
 
-              message = "No route matches #{Hash[parts].inspect}"
+            def raise_generation_error(args, missing_keys)
+              message = "No route matches #{args.inspect}"
               message << " missing required keys: #{missing_keys.inspect}"
 
               raise ActionController::UrlGenerationError, message
diff --git a/actionpack/test/dispatch/routing_test.rb b/actionpack/test/dispatch/routing_test.rb
index aac808afda..fad09d309a 100644
--- a/actionpack/test/dispatch/routing_test.rb
+++ b/actionpack/test/dispatch/routing_test.rb
@@ -3327,6 +3327,8 @@ class TestOptimizedNamedRoutes < ActionDispatch::IntegrationTest
       ok = lambda { |env| [200, { 'Content-Type' => 'text/plain' }, []] }
       get '/foo' => ok, as: :foo
       get '/post(/:action(/:id))' => ok, as: :posts
+      get '/:foo/:foo_type/bars/:id' => ok, as: :bar
+      get '/projects/:id.:format' => ok, as: :project
     end
   end
 
@@ -3349,6 +3351,16 @@ class TestOptimizedNamedRoutes < ActionDispatch::IntegrationTest
     assert_equal '/post', Routes.url_helpers.posts_path
     assert_equal '/post', posts_path
   end
+
+  test 'segments with same prefix are replaced correctly' do
+    assert_equal '/foo/baz/bars/1', Routes.url_helpers.bar_path('foo', 'baz', '1')
+    assert_equal '/foo/baz/bars/1', bar_path('foo', 'baz', '1')
+  end
+
+  test 'segments separated with a period are replaced correctly' do
+    assert_equal '/projects/1.json', Routes.url_helpers.project_path(1, :json)
+    assert_equal '/projects/1.json', project_path(1, :json)
+  end
 end
 
 class TestNamedRouteUrlHelpers < ActionDispatch::IntegrationTest