aboutsummaryrefslogtreecommitdiffstats
path: root/actionpack/lib/action_controller/routing/recognition_optimisation.rb
blob: 6d54d0334c834f81e17dd5f969a243f73e886e54 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
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 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

      private
        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
    end
  end
end