← Back to branch summary

~michaelforrest/use-case-mapper/trunk

« back to all changes in this revision

Viewing changes to vendor/rails/actionpack/lib/action_controller/routing/recognition_optimisation.rb

  • Committer: Richard Lee (Canonical)
  • Date: 2010-10-15 15:17:58 UTC
  • mfrom: (190.1.3 use-case-mapper)
  • Revision ID: richard.lee@canonical.com-20101015151758-wcvmfxrexsongf9d
Merge

Show diffs side-by-side

added added

removed removed

Lines of Context:
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, environment.merge(: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
 
            tag, sub = item
102
 
            if tag == :dynamic
103
 
              body += padding + "#{start ? 'if' : 'elsif'} true\n"
104
 
              body += generate_code(sub, padding + "  ", level + 1)
105
 
              break
106
 
            elsif tag == nil && !was_nil
107
 
              was_nil = true
108
 
              body += padding + "#{start ? 'if' : 'elsif'} seg.nil?\n"
109
 
              body += generate_code(sub, padding + "  ", level + 1)
110
 
            else
111
 
              body += padding + "#{start ? 'if' : 'elsif'} seg == '#{tag}'\n"
112
 
              body += generate_code(sub, padding + "  ", level + 1)
113
 
            end
114
 
          end
115
 
        end
116
 
        body += padding + "else\n"
117
 
        body += padding + "  #{list[0]}\n"
118
 
        body += padding + "end)\n"
119
 
        body
120
 
      end
121
 
 
122
 
      # this must be really fast
123
 
      def to_plain_segments(str)
124
 
        str = str.dup
125
 
        str.sub!(/^\/+/,'')
126
 
        str.sub!(/\/+$/,'')
127
 
        segments = str.split(/\.[^\/]+\/+|\/+|\.[^\/]+\Z/) # cut off ".format" also
128
 
        segments << nil
129
 
        segments
130
 
      end
131
 
 
132
 
      private
133
 
        def write_recognize_optimized!
134
 
          tree = segment_tree(routes)
135
 
          body = generate_code(tree)
136
 
 
137
 
          remove_recognize_optimized!
138
 
 
139
 
          instance_eval %{
140
 
            def recognize_optimized(path, env)
141
 
              segments = to_plain_segments(path)
142
 
              index = #{body}
143
 
              return nil unless index
144
 
              while index < routes.size
145
 
                result = routes[index].recognize(path, env) and return result
146
 
                index += 1
147
 
              end
148
 
              nil
149
 
            end
150
 
          }, '(recognize_optimized)', 1
151
 
        end
152
 
 
153
 
        def clear_recognize_optimized!
154
 
          remove_recognize_optimized!
155
 
          write_recognize_optimized!
156
 
        end
157
 
 
158
 
        def remove_recognize_optimized!
159
 
          if respond_to?(:recognize_optimized)
160
 
            class << self
161
 
              remove_method :recognize_optimized
162
 
            end
163
 
          end
164
 
        end
165
 
    end
166
 
  end
167
 
end