Line data Source code
1 : #include "route_tree.hpp"
2 : #include "route.hpp"
3 : #include "../../../util/logger.hpp"
4 : #include <algorithm>
5 :
6 : namespace thinger::http {
7 :
8 : using detail::path_matcher;
9 : using detail::pattern_token;
10 :
11 : namespace {
12 :
13 : using path_segment = std::vector<pattern_token>;
14 :
15 : // Parameter names, in order of their captures: empty for a repeated one
16 34196 : std::vector<std::string> capture_names(const std::vector<pattern_token>& tokens) {
17 34196 : std::vector<std::string> names;
18 73880 : for (const auto& token : tokens) {
19 39684 : if (!token.parameter) continue;
20 4880 : bool repeated = std::find(names.begin(), names.end(), token.text) != names.end();
21 4880 : names.push_back(repeated ? std::string{} : token.text);
22 : }
23 34196 : return names;
24 0 : }
25 :
26 : // The pattern as segments: the text between slashes
27 34184 : std::vector<path_segment> split_segments(const std::vector<pattern_token>& tokens) {
28 34184 : std::vector<path_segment> segments(1);
29 73835 : for (const auto& token : tokens) {
30 39651 : if (token.parameter) {
31 4865 : segments.back().push_back(token);
32 4865 : continue;
33 : }
34 34786 : for (size_t start = 0;;) {
35 77757 : size_t slash = token.text.find('/', start);
36 77757 : auto text = token.text.substr(start, slash == std::string::npos ? std::string::npos : slash - start);
37 115395 : if (!text.empty()) segments.back().push_back({false, std::move(text), {}});
38 77757 : if (slash == std::string::npos) break;
39 42971 : segments.emplace_back();
40 42971 : start = slash + 1;
41 120728 : }
42 : }
43 34184 : return segments;
44 37638 : }
45 :
46 : // The segments from `first` on, joined by slashes
47 1566 : path_segment join_segments(const std::vector<path_segment>& segments, size_t first) {
48 1566 : path_segment joined;
49 3501 : for (size_t j = first; j < segments.size(); ++j) {
50 2304 : if (j > first) joined.push_back({false, "/", {}});
51 1935 : joined.insert(joined.end(), segments[j].begin(), segments[j].end());
52 : }
53 1566 : return joined;
54 1107 : }
55 :
56 76798 : bool is_static(const path_segment& tokens) {
57 118944 : return std::none_of(tokens.begin(), tokens.end(), [](const auto& token) { return token.parameter; });
58 : }
59 :
60 9 : void warn_repeat(const route& added, const route& existing, std::string_view method_name) {
61 9 : LOG_WARNING("Route {} {} repeats route {} {} and will never match", method_name,
62 : added.get_pattern(), method_name, existing.get_pattern());
63 9 : }
64 :
65 : }
66 :
67 : struct route_tree::node {
68 : // A route matching the rest of the path from this node's segment on
69 : struct rest_route {
70 : std::unique_ptr<const path_matcher> matcher;
71 : leaf target;
72 : };
73 :
74 : // A child by a constrained segment, with the route that created it
75 : struct constrained_child {
76 : std::unique_ptr<const path_matcher> matcher;
77 : std::unique_ptr<node> child;
78 : const route* first;
79 : };
80 :
81 : // Children by the next segment, in order of priority
82 : std::map<std::string, std::unique_ptr<node>, std::less<>> statics;
83 : std::vector<constrained_child> constrained; // in creation order
84 : std::unique_ptr<node> parameter;
85 : std::vector<rest_route> rest; // catch-alls last
86 :
87 : // Route ending at this node
88 : std::unique_ptr<leaf> end;
89 :
90 71927 : node* static_child(const std::string& text) {
91 71927 : auto& child = statics[text];
92 71927 : if (!child) child = std::make_unique<node>();
93 71927 : return child.get();
94 : }
95 :
96 2768 : node* parameter_child() {
97 2768 : if (!parameter) parameter = std::make_unique<node>();
98 2768 : return parameter.get();
99 : }
100 :
101 : // The same constraints (whatever the parameter names) share a node
102 537 : node* constrained_child_for(std::unique_ptr<const path_matcher> matcher, const route& target,
103 : std::string_view method_name) {
104 537 : auto it = std::find_if(constrained.begin(), constrained.end(),
105 42 : [&](const auto& entry) { return entry.matcher->key() == matcher->key(); });
106 537 : if (it == constrained.end()) {
107 : // Different constraints are tried in creation order
108 549 : for (const auto& sibling : constrained) {
109 27 : if (sibling.matcher->may_overlap(*matcher)) warn_overlap(target, *sibling.first, method_name);
110 : }
111 1044 : constrained.push_back({std::move(matcher), std::make_unique<node>(), &target});
112 1044 : it = std::prev(constrained.end());
113 : }
114 1074 : return it->child.get();
115 522 : }
116 :
117 1566 : void add_rest(std::unique_ptr<const path_matcher> matcher, leaf added, std::string_view method_name) {
118 1566 : auto existing = std::find_if(rest.begin(), rest.end(),
119 378 : [&](const auto& r) { return r.matcher->key() == matcher->key(); });
120 1566 : if (existing != rest.end()) {
121 3 : warn_repeat(*added.target, *existing->target.target, method_name);
122 3 : return;
123 : }
124 : // Wildcards of the same kind are tried in registration order
125 1938 : for (const auto& r : rest) {
126 375 : if (r.matcher->is_catch_all() == matcher->is_catch_all() && r.matcher->may_overlap(*matcher)) {
127 12 : warn_overlap(*added.target, *r.target.target, method_name);
128 : }
129 : }
130 :
131 : // Catch-alls after the routes with more after their wildcard
132 1563 : auto position = rest.end();
133 1563 : if (!matcher->is_catch_all()) {
134 579 : position = std::find_if(rest.begin(), rest.end(), [](const auto& r) { return r.matcher->is_catch_all(); });
135 : }
136 3126 : rest.insert(position, {std::move(matcher), std::move(added)});
137 1563 : }
138 :
139 32630 : void set_end(leaf added, std::string_view method_name) {
140 32630 : if (end) {
141 6 : warn_repeat(*added.target, *end->target, method_name);
142 6 : return;
143 : }
144 32624 : end = std::make_unique<leaf>(std::move(added));
145 : }
146 : };
147 :
148 14297 : route_tree::route_tree() : root_(std::make_unique<node>()) {}
149 14297 : route_tree::~route_tree() = default;
150 0 : route_tree::route_tree(route_tree&&) noexcept = default;
151 0 : route_tree& route_tree::operator=(route_tree&&) noexcept = default;
152 :
153 34196 : void route_tree::insert(const route& target, std::string_view method_name) {
154 34196 : auto tokens = detail::parse_route_pattern(target.get_pattern());
155 34196 : auto names = capture_names(tokens);
156 :
157 : // A regex depending on its context is matched with the whole route on the whole path
158 34196 : bool whole = std::any_of(tokens.begin(), tokens.end(), [](const auto& token) {
159 39681 : return token.parameter && detail::regex_depends_on_context(token.regex);
160 : });
161 34232 : auto segments = whole ? std::vector<path_segment>{tokens} : split_segments(tokens);
162 :
163 34196 : node* current = root_.get();
164 109428 : for (size_t i = 0; i < segments.size(); ++i) {
165 76798 : const auto& segment = segments[i];
166 76798 : if (is_static(segment)) {
167 71927 : current = current->static_child(segment.empty() ? std::string{} : segment.front().text);
168 75232 : continue;
169 : }
170 4871 : if (segment.size() == 1 && segment.front().regex.empty()) {
171 2768 : current = current->parameter_child();
172 2768 : continue;
173 : }
174 2103 : auto matcher = std::make_unique<const path_matcher>(segment);
175 2103 : if (!whole && !matcher->may_match_slash()) {
176 537 : current = current->constrained_child_for(std::move(matcher), target, method_name);
177 537 : continue;
178 : }
179 : // A parameter that may match '/': the rest of the route matches the rest of the path
180 1566 : current->add_rest(std::make_unique<const path_matcher>(join_segments(segments, i)),
181 3132 : leaf{&target, std::move(names)}, method_name);
182 1566 : return;
183 2103 : }
184 32630 : current->set_end(leaf{&target, std::move(names)}, method_name);
185 37340 : }
186 :
187 30 : void route_tree::warn_overlap(const route& added, const route& existing, std::string_view method_name) {
188 30 : LOG_WARNING("Route {} {} may overlap with route {} {}; the first registered takes precedence",
189 : method_name, added.get_pattern(), method_name, existing.get_pattern());
190 30 : }
191 :
192 89016 : const route_tree::leaf* route_tree::find(std::string_view path, detail::route_captures& captures) const {
193 89016 : return match(*root_, path, 0, captures);
194 : }
195 :
196 198122 : const route_tree::leaf* route_tree::match(const node& current, std::string_view path, size_t position,
197 : detail::route_captures& captures) {
198 198122 : size_t slash = path.find('/', position);
199 198122 : bool last = slash == std::string_view::npos;
200 198122 : auto segment = path.substr(position, last ? std::string_view::npos : slash - position);
201 198122 : size_t mark = captures.size();
202 :
203 138127 : auto descend = [&](const node& child) -> const leaf* {
204 138127 : return last ? child.end.get() : match(child, path, slash + 1, captures);
205 198122 : };
206 :
207 198122 : if (!current.statics.empty()) {
208 186252 : if (auto it = current.statics.find(segment); it != current.statics.end()) {
209 127799 : if (auto* found = descend(*it->second)) return found;
210 : }
211 : }
212 140962 : for (const auto& entry : current.constrained) {
213 2505 : if (entry.matcher->match(segment, captures)) {
214 729 : if (auto* found = descend(*entry.child)) return found;
215 240 : captures.resize(mark);
216 : }
217 : }
218 138457 : if (current.parameter && !segment.empty()) {
219 9599 : captures.push_back(segment);
220 9599 : if (auto* found = descend(*current.parameter)) return found;
221 6333 : captures.resize(mark);
222 : }
223 135191 : if (!current.rest.empty()) {
224 4932 : auto rest = path.substr(position);
225 7986 : for (const auto& r : current.rest) {
226 5313 : if (r.matcher->match(rest, captures)) return &r.target;
227 : }
228 : }
229 132932 : return nullptr;
230 : }
231 :
232 : } // namespace thinger::http
|
