diff options
Diffstat (limited to 'actionpack/lib/action_controller/routing/recognition_optimisation.rb')
-rw-r--r-- | actionpack/lib/action_controller/routing/recognition_optimisation.rb | 158 |
1 files changed, 158 insertions, 0 deletions
diff --git a/actionpack/lib/action_controller/routing/recognition_optimisation.rb b/actionpack/lib/action_controller/routing/recognition_optimisation.rb new file mode 100644 index 0000000000..cf8f5232c1 --- /dev/null +++ b/actionpack/lib/action_controller/routing/recognition_optimisation.rb @@ -0,0 +1,158 @@ +module ActionController + module Routing + # BEFORE: 0.191446860631307 ms/url + # AFTER: 0.029847304022858 ms/url + # Speed up: 6.4 times + # + # Route recognition is slow due to one-by-one iterating over + # a whole routeset (each map.resources generates at least 14 routes) + # and matching weird regexps on each step. + # + # We optimize this by skipping all URI segments that 100% sure can't + # be matched, moving deeper in a tree of routes (where node == segment) + # until first possible match is accured. In such case, we start walking + # a flat list of routes, matching them with accurate matcher. + # So, first step: search a segment tree for the first relevant index. + # Second step: iterate routes starting with that index. + # + # How tree is walked? We can do a recursive tests, but it's smarter: + # We just create a tree of if-s and elsif-s matching segments. + # + # We have segments of 3 flavors: + # 1) nil (no segment, route finished) + # 2) const-dot-dynamic (like "/posts.:xml", "/preview.:size.jpg") + # 3) const (like "/posts", "/comments") + # 4) dynamic ("/:id", "file.:size.:extension") + # + # We split incoming string into segments and iterate over them. + # When segment is nil, we drop immediately, on a current node index. + # When segment is equal to some const, we step into branch. + # If none constants matched, we step into 'dynamic' branch (it's a last). + # If we can't match anything, we drop to last index on a level. + # + # Note: we maintain the original routes order, so we finish building + # steps on a first dynamic segment. + # + # + # Example. Given the routes: + # 0 /posts/ + # 1 /posts/:id + # 2 /posts/:id/comments + # 3 /posts/blah + # 4 /users/ + # 5 /users/:id + # 6 /users/:id/profile + # + # request_uri = /users/123 + # + # There will be only 4 iterations: + # 1) segm test for /posts prefix, skip all /posts/* routes + # 2) segm test for /users/ + # 3) segm test for /users/:id + # (jump to list index = 5) + # 4) full test for /users/:id => here we are! + + class RouteSet + def recognize_path(path, environment={}) + result = recognize_optimized(path, environment) and return result + + # Route was not recognized. Try to find out why (maybe wrong verb). + allows = HTTP_METHODS.select { |verb| routes.find { |r| r.recognize(path, :method => verb) } } + + if environment[:method] && !HTTP_METHODS.include?(environment[:method]) + raise NotImplemented.new(*allows) + elsif !allows.empty? + raise MethodNotAllowed.new(*allows) + else + raise RoutingError, "No route matches #{path.inspect} with #{environment.inspect}" + end + end + + def recognize_optimized(path, env) + write_recognize_optimized + recognize_optimized(path, env) + end + + def write_recognize_optimized + tree = segment_tree(routes) + body = generate_code(tree) + instance_eval %{ + def recognize_optimized(path, env) + segments = to_plain_segments(path) + index = #{body} + return nil unless index + while index < routes.size + result = routes[index].recognize(path, env) and return result + index += 1 + end + nil + end + }, __FILE__, __LINE__ + end + + def segment_tree(routes) + tree = [0] + + i = -1 + routes.each do |route| + i += 1 + # not fast, but runs only once + segments = to_plain_segments(route.segments.inject("") { |str,s| str << s.to_s }) + + node = tree + segments.each do |seg| + seg = :dynamic if seg && seg[0] == ?: + node << [seg, [i]] if node.empty? || node[node.size - 1][0] != seg + node = node[node.size - 1][1] + end + end + tree + end + + def generate_code(list, padding=' ', level = 0) + # a digit + return padding + "#{list[0]}\n" if list.size == 1 && !(Array === list[0]) + + body = padding + "(seg = segments[#{level}]; \n" + + i = 0 + was_nil = false + list.each do |item| + if Array === item + i += 1 + start = (i == 1) + final = (i == list.size) + tag, sub = item + if tag == :dynamic + body += padding + "#{start ? 'if' : 'elsif'} true\n" + body += generate_code(sub, padding + " ", level + 1) + break + elsif tag == nil && !was_nil + was_nil = true + body += padding + "#{start ? 'if' : 'elsif'} seg.nil?\n" + body += generate_code(sub, padding + " ", level + 1) + else + body += padding + "#{start ? 'if' : 'elsif'} seg == '#{tag}'\n" + body += generate_code(sub, padding + " ", level + 1) + end + end + end + body += padding + "else\n" + body += padding + " #{list[0]}\n" + body += padding + "end)\n" + body + end + + # this must be really fast + def to_plain_segments(str) + str = str.dup + str.sub!(/^\/+/,'') + str.sub!(/\/+$/,'') + segments = str.split(/\.[^\/]+\/+|\/+|\.[^\/]+\Z/) # cut off ".format" also + segments << nil + segments + end + + end + end +end |