vendor/rails/actionpack/lib/action_controller/routing/recognition_optimisation.rb

   1 module ActionController
   2   module Routing
   3     # BEFORE:   0.191446860631307 ms/url
   4     # AFTER:    0.029847304022858 ms/url
   5     # Speed up: 6.4 times
   6     #
   7     # Route recognition is slow due to one-by-one iterating over
   8     # a whole routeset (each map.resources generates at least 14 routes)
   9     # and matching weird regexps on each step.
  10     #
  11     # We optimize this by skipping all URI segments that 100% sure can't
  12     # be matched, moving deeper in a tree of routes (where node == segment)
  13     # until first possible match is accured. In such case, we start walking
  14     # a flat list of routes, matching them with accurate matcher.
  15     # So, first step: search a segment tree for the first relevant index.
  16     # Second step: iterate routes starting with that index.
  17     #
  18     # How tree is walked? We can do a recursive tests, but it's smarter:
  19     # We just create a tree of if-s and elsif-s matching segments.
  20     #
  21     # We have segments of 3 flavors:
  22     # 1) nil (no segment, route finished)
  23     # 2) const-dot-dynamic (like "/posts.:xml", "/preview.:size.jpg")
  24     # 3) const (like "/posts", "/comments")
  25     # 4) dynamic ("/:id", "file.:size.:extension")
  26     #
  27     # We split incoming string into segments and iterate over them.
  28     # When segment is nil, we drop immediately, on a current node index.
  29     # When segment is equal to some const, we step into branch.
  30     # If none constants matched, we step into 'dynamic' branch (it's a last).
  31     # If we can't match anything, we drop to last index on a level.
  32     #
  33     # Note: we maintain the original routes order, so we finish building
  34     #       steps on a first dynamic segment.
  35     #
  36     #
  37     # Example. Given the routes:
  38     #   0 /posts/
  39     #   1 /posts/:id
  40     #   2 /posts/:id/comments
  41     #   3 /posts/blah
  42     #   4 /users/
  43     #   5 /users/:id
  44     #   6 /users/:id/profile
  45     #
  46     # request_uri = /users/123
  47     #
  48     # There will be only 4 iterations:
  49     #  1) segm test for /posts prefix, skip all /posts/* routes
  50     #  2) segm test for /users/
  51     #  3) segm test for /users/:id
  52     #     (jump to list index = 5)
  53     #  4) full test for /users/:id => here we are!
  54     class RouteSet
  55       def recognize_path(path, environment={})
  56         result = recognize_optimized(path, environment) and return result
  57
  58         # Route was not recognized. Try to find out why (maybe wrong verb).
  59         allows = HTTP_METHODS.select { |verb| routes.find { |r| r.recognize(path, :method => verb) } }
  60
  61         if environment[:method] && !HTTP_METHODS.include?(environment[:method])
  62           raise NotImplemented.new(*allows)
  63         elsif !allows.empty?
  64           raise MethodNotAllowed.new(*allows)
  65         else
  66           raise RoutingError, "No route matches #{path.inspect} with #{environment.inspect}"
  67         end
  68       end
  69
  70       def segment_tree(routes)
  71         tree = [0]
  72
  73         i = -1
  74         routes.each do |route|
  75           i += 1
  76           # not fast, but runs only once
  77           segments = to_plain_segments(route.segments.inject("") { |str,s| str << s.to_s })
  78
  79           node  = tree
  80           segments.each do |seg|
  81             seg = :dynamic if seg && seg[0] == ?:
  82             node << [seg, [i]] if node.empty? || node[node.size - 1][0] != seg
  83             node = node[node.size - 1][1]
  84           end
  85         end
  86         tree
  87       end
  88
  89       def generate_code(list, padding='  ', level = 0)
  90         # a digit
  91         return padding + "#{list[0]}\n" if list.size == 1 && !(Array === list[0])
  92
  93         body = padding + "(seg = segments[#{level}]; \n"
  94
  95         i = 0
  96         was_nil = false
  97         list.each do |item|
  98           if Array === item
  99             i += 1
 100             start = (i == 1)
 101             final = (i == list.size)
 102             tag, sub = item
 103             if tag == :dynamic
 104               body += padding + "#{start ? 'if' : 'elsif'} true\n"
 105               body += generate_code(sub, padding + "  ", level + 1)
 106               break
 107             elsif tag == nil && !was_nil
 108               was_nil = true
 109               body += padding + "#{start ? 'if' : 'elsif'} seg.nil?\n"
 110               body += generate_code(sub, padding + "  ", level + 1)
 111             else
 112               body += padding + "#{start ? 'if' : 'elsif'} seg == '#{tag}'\n"
 113               body += generate_code(sub, padding + "  ", level + 1)
 114             end
 115           end
 116         end
 117         body += padding + "else\n"
 118         body += padding + "  #{list[0]}\n"
 119         body += padding + "end)\n"
 120         body
 121       end
 122
 123       # this must be really fast
 124       def to_plain_segments(str)
 125         str = str.dup
 126         str.sub!(/^\/+/,'')
 127         str.sub!(/\/+$/,'')
 128         segments = str.split(/\.[^\/]+\/+|\/+|\.[^\/]+\Z/) # cut off ".format" also
 129         segments << nil
 130         segments
 131       end
 132
 133       private
 134         def write_recognize_optimized!
 135           tree = segment_tree(routes)
 136           body = generate_code(tree)
 137
 138           remove_recognize_optimized!
 139
 140           instance_eval %{
 141             def recognize_optimized(path, env)
 142               segments = to_plain_segments(path)
 143               index = #{body}
 144               return nil unless index
 145               while index < routes.size
 146                 result = routes[index].recognize(path, env) and return result
 147                 index += 1
 148               end
 149               nil
 150             end
 151           }, '(recognize_optimized)', 1
 152         end
 153
 154         def clear_recognize_optimized!
 155           remove_recognize_optimized!
 156           write_recognize_optimized!
 157         end
 158
 159         def remove_recognize_optimized!
 160           if respond_to?(:recognize_optimized)
 161             class << self
 162               remove_method :recognize_optimized
 163             end
 164           end
 165         end
 166     end
 167   end
 168 end