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
|
