Line data Source code
1 : #include "route_pattern.hpp"
2 : #include <algorithm>
3 : #include <stdexcept>
4 :
5 : namespace thinger::http::detail {
6 :
7 : namespace {
8 :
9 47714 : bool is_name_start(char c) {
10 47714 : return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_';
11 : }
12 :
13 36763 : bool is_name_char(char c) {
14 36763 : return is_name_start(c) || (c >= '0' && c <= '9');
15 : }
16 :
17 60 : bool is_alnum(char c) {
18 60 : return is_name_char(c) && c != '_';
19 : }
20 :
21 : // Position of the parenthesis closing the one at `open`, skipping escaped characters
22 : // and character classes; npos if it is not closed
23 4947 : size_t closing_parenthesis(std::string_view text, size_t open) {
24 4947 : int depth = 0;
25 4947 : bool in_class = false;
26 27300 : for (size_t i = open; i < text.size(); ++i) {
27 27291 : char c = text[i];
28 27291 : if (c == '\\') {
29 84 : ++i;
30 27207 : } else if (in_class) {
31 6303 : if (c == ']') in_class = false;
32 20904 : } else if (c == '[') {
33 1425 : in_class = true;
34 19479 : } else if (c == '(') {
35 4980 : ++depth;
36 14499 : } else if (c == ')' && --depth == 0) {
37 4938 : return i;
38 : }
39 : }
40 9 : return std::string_view::npos;
41 : }
42 :
43 : // Capture groups of a regex: '(' not escaped, not in a class, not followed by '?'
44 57 : size_t capture_groups(std::string_view regex) {
45 57 : size_t groups = 0;
46 57 : bool in_class = false;
47 399 : for (size_t i = 0; i < regex.size(); ++i) {
48 342 : char c = regex[i];
49 342 : if (c == '\\') {
50 36 : ++i;
51 306 : } else if (in_class) {
52 66 : if (c == ']') in_class = false;
53 240 : } else if (c == '[') {
54 12 : in_class = true;
55 228 : } else if (c == '(' && (i + 1 == regex.size() || regex[i + 1] != '?')) {
56 9 : ++groups;
57 : }
58 : }
59 57 : return groups;
60 : }
61 :
62 : // Whether a regex may match '/'. Conservative: true unless it has none of the
63 : // constructs that may (any character, negated or POSIX classes, ranges including '/',
64 : // escapes of other characters...)
65 27 : bool regex_may_match_slash(std::string_view regex) {
66 27 : bool in_class = false;
67 267 : for (size_t i = 0; i < regex.size(); ++i) {
68 240 : char c = regex[i];
69 240 : if (c == '\\') {
70 12 : if (++i == regex.size()) return true;
71 12 : char escaped = regex[i];
72 12 : if (escaped == '/' || (is_alnum(escaped) && std::string_view("dwsbB").find(escaped) == std::string_view::npos)) {
73 0 : return true;
74 : }
75 228 : } else if (in_class) {
76 42 : if (c == ']') {
77 6 : in_class = false;
78 36 : } else if (c == '/' || c == '[') {
79 0 : return true;
80 36 : } else if (c == '-' && i + 1 < regex.size() && regex[i + 1] != ']') {
81 12 : auto low = static_cast<unsigned char>(regex[i - 1]);
82 12 : auto high = static_cast<unsigned char>(regex[i + 1]);
83 12 : if (high == '\\' || (low <= '/' && high >= '/')) return true;
84 : }
85 186 : } else if (c == '[') {
86 : // negated classes, and [] (empty in ECMAScript, a literal ']' elsewhere)
87 6 : if (i + 1 < regex.size() && (regex[i + 1] == '^' || regex[i + 1] == ']')) return true;
88 6 : in_class = true;
89 180 : } else if (c == '.' || c == '/') {
90 0 : return true;
91 : }
92 : }
93 27 : return false;
94 : }
95 :
96 : // Alternative words of a regex such as "properties|buckets|flows"; empty if it has
97 : // anything else than alternatives of literal characters
98 3258 : std::optional<std::vector<std::string>> regex_words(std::string_view regex) {
99 3258 : if (regex.find('|') == std::string_view::npos) return std::nullopt;
100 36 : std::vector<std::string> words(1);
101 201 : for (char c : regex) {
102 189 : if (c == '|') {
103 12 : words.emplace_back();
104 177 : } else if (c == '\0' || std::string_view(".^$()[]{}*+?\\").find(c) != std::string_view::npos) {
105 24 : return std::nullopt;
106 : } else {
107 153 : words.back() += c;
108 : }
109 : }
110 12 : return words;
111 36 : }
112 :
113 609 : std::bitset<256> char_range(int low, int high) {
114 1827 : std::bitset<256> chars;
115 8019 : for (int c = low; c <= high; ++c) chars.set(c);
116 609 : return chars;
117 : }
118 :
119 : // Characters of \d, \w and \s (and their complements \D, \W, \S), as std::regex
120 : // matches them on char in the default locale
121 45 : bool class_escape(char escape, std::bitset<256>& chars) {
122 45 : switch (escape) {
123 18 : case 'd': case 'D':
124 18 : chars = char_range('0', '9');
125 18 : break;
126 9 : case 'w': case 'W':
127 9 : chars = char_range('a', 'z') | char_range('A', 'Z') | char_range('0', '9');
128 9 : chars.set('_');
129 9 : break;
130 0 : case 's': case 'S':
131 0 : chars = char_range('\t', '\r');
132 0 : chars.set(' ');
133 0 : break;
134 18 : default:
135 18 : return false;
136 : }
137 27 : if (escape >= 'A' && escape <= 'Z') chars.flip();
138 27 : return true;
139 : }
140 :
141 : // Character class [...] starting at `i`; leaves `i` past it
142 507 : bool parse_class(std::string_view regex, size_t& i, std::bitset<256>& chars) {
143 507 : size_t j = i + 1;
144 507 : bool negated = j < regex.size() && regex[j] == '^';
145 507 : if (negated) ++j;
146 507 : if (j < regex.size() && regex[j] == ']') return false; // [] and [^]
147 :
148 1521 : std::bitset<256> set;
149 : while (true) {
150 1119 : if (j >= regex.size()) return false;
151 1119 : char c = regex[j];
152 1119 : if (c == ']') {
153 507 : ++j;
154 507 : break;
155 : }
156 612 : if (c == '[') return false; // POSIX classes
157 :
158 612 : int low = -1;
159 612 : if (c == '\\') {
160 0 : if (j + 1 >= regex.size()) return false;
161 0 : char escaped = regex[j + 1];
162 0 : if (is_alnum(escaped)) {
163 0 : std::bitset<256> escaped_chars;
164 0 : if (!class_escape(escaped, escaped_chars)) return false;
165 0 : set |= escaped_chars;
166 : } else {
167 0 : low = static_cast<unsigned char>(escaped);
168 : }
169 0 : j += 2;
170 : } else {
171 612 : low = static_cast<unsigned char>(c);
172 612 : ++j;
173 : }
174 612 : if (low < 0) continue;
175 :
176 : // Range low-high, unless '-' is the last character of the class
177 612 : if (j + 1 < regex.size() && regex[j] == '-' && regex[j + 1] != ']') {
178 : int high;
179 564 : char h = regex[j + 1];
180 564 : if (h == '\\') {
181 0 : if (j + 2 >= regex.size() || is_alnum(regex[j + 2])) return false;
182 0 : high = static_cast<unsigned char>(regex[j + 2]);
183 0 : j += 3;
184 564 : } else if (h == '[') {
185 0 : return false;
186 : } else {
187 564 : high = static_cast<unsigned char>(h);
188 564 : j += 2;
189 : }
190 564 : if (high < low) return false;
191 564 : set |= char_range(low, high);
192 : } else {
193 48 : set.set(low);
194 : }
195 612 : }
196 507 : chars = negated ? ~set : set;
197 507 : i = j;
198 507 : return true;
199 : }
200 :
201 : // Quantifier {n}, {n,} or {n,m} starting at `i`; leaves `i` past it
202 45 : bool parse_braces(std::string_view regex, size_t& i, uint32_t& min, uint32_t& max, uint32_t unbounded) {
203 75 : auto number = [&](size_t& j, uint32_t& value) {
204 75 : size_t start = j;
205 75 : uint64_t result = 0;
206 177 : while (j < regex.size() && regex[j] >= '0' && regex[j] <= '9') {
207 102 : result = result * 10 + (regex[j++] - '0');
208 102 : if (result >= unbounded) return false;
209 : }
210 75 : value = static_cast<uint32_t>(result);
211 75 : return j > start;
212 45 : };
213 45 : size_t j = i + 1;
214 45 : if (!number(j, min)) return false;
215 45 : max = min;
216 45 : if (j < regex.size() && regex[j] == ',') {
217 30 : ++j;
218 30 : max = unbounded;
219 30 : if (j < regex.size() && regex[j] != '}' && !number(j, max)) return false;
220 : }
221 45 : if (j >= regex.size() || regex[j] != '}' || max < min) return false;
222 45 : i = j + 1;
223 45 : return true;
224 : }
225 :
226 : // A text matched against a regex the matcher could not compile, with the groups to capture.
227 : // A text longer than this does not match, and is not run through std::regex: libstdc++
228 : // matches recursively, about one frame per byte, so a request target of up to 16 KiB could
229 : // overflow the stack (as the Host name, capped before host patterns). 2 KiB leaves a wide
230 : // margin on default thread stacks and is the URL length long held as portable. Every other
231 : // matcher still takes the whole target, within the 8000 octets RFC 9110 section 4.1
232 : // recommends for a URI
233 201 : bool match_regex(const std::regex& regex, const std::vector<size_t>& groups, std::string_view text,
234 : route_captures& captures) {
235 201 : constexpr size_t max_regex_text_size = 2048;
236 201 : if (text.size() > max_regex_text_size) return false;
237 189 : std::cmatch matches;
238 189 : if (!std::regex_match(text.data(), text.data() + text.size(), matches, regex)) return false;
239 87 : for (size_t group : groups) {
240 45 : const auto& capture = matches[group];
241 45 : captures.push_back(capture.matched ? std::string_view(capture.first, capture.length()) : std::string_view{});
242 : }
243 42 : return true;
244 189 : }
245 :
246 : } // namespace
247 :
248 69042 : std::vector<pattern_token> parse_route_pattern(std::string_view pattern) {
249 69042 : std::vector<pattern_token> tokens;
250 69042 : size_t i = 0;
251 616289 : while (i < pattern.size()) {
252 547256 : if (pattern[i] == ':' && i + 1 < pattern.size() && is_name_start(pattern[i + 1])) {
253 10951 : size_t end = i + 2;
254 41974 : while (end < pattern.size() && is_name_char(pattern[end])) ++end;
255 21902 : pattern_token token{true, std::string(pattern.substr(i + 1, end - i - 1)), {}};
256 10951 : if (end < pattern.size() && pattern[end] == '(') {
257 4947 : size_t close = closing_parenthesis(pattern, end);
258 4947 : if (close == std::string_view::npos) {
259 27 : throw std::invalid_argument("Unbalanced parentheses in route pattern: " + std::string(pattern));
260 : }
261 4938 : token.regex = pattern.substr(end + 1, close - end - 1);
262 4938 : end = close + 1;
263 : }
264 10942 : tokens.push_back(std::move(token));
265 10942 : i = end;
266 10942 : continue;
267 10951 : }
268 607277 : if (tokens.empty() || tokens.back().parameter) tokens.push_back({});
269 536305 : tokens.back().text += pattern[i++];
270 : }
271 69033 : return tokens;
272 70981 : }
273 :
274 4880 : bool regex_depends_on_context(std::string_view regex) {
275 4880 : bool in_class = false;
276 11834 : for (size_t i = 0; i < regex.size(); ++i) {
277 6966 : char c = regex[i];
278 6966 : if (c == '\\') {
279 36 : if (++i == regex.size()) return false;
280 36 : if (!in_class && (regex[i] == 'b' || regex[i] == 'B' || (regex[i] >= '1' && regex[i] <= '9'))) return true;
281 6930 : } else if (in_class) {
282 2256 : if (c == ']') in_class = false;
283 4674 : } else if (c == '[') {
284 507 : if (i + 1 < regex.size() && regex[i + 1] == '^') ++i;
285 : // [] and [^] end where they start in ECMAScript
286 507 : if (i + 1 < regex.size() && regex[i + 1] == ']') {
287 0 : ++i;
288 : } else {
289 507 : in_class = true;
290 : }
291 4167 : } else if (c == '^' || c == '$' || regex.substr(i, 3) == "(?=" || regex.substr(i, 3) == "(?!") {
292 3 : return true;
293 : }
294 : }
295 4868 : return false;
296 : }
297 :
298 3900 : std::string pattern_regex(std::span<const pattern_token> tokens) {
299 3900 : std::string regex;
300 9522 : for (const auto& token : tokens) {
301 5622 : if (token.parameter) {
302 4248 : regex += '(';
303 4470 : regex += token.regex.empty() ? "[^/]+" : token.regex;
304 4248 : regex += ')';
305 4248 : continue;
306 : }
307 5235 : for (char c : token.text) {
308 3861 : if (std::string_view(".^$|()[]{}*+?\\").find(c) != std::string_view::npos) regex += '\\';
309 3861 : regex += c;
310 : }
311 : }
312 3900 : return regex;
313 0 : }
314 :
315 3669 : path_matcher::path_matcher(std::span<const pattern_token> tokens)
316 3669 : : key_(pattern_regex(tokens))
317 : {
318 3669 : if (tokens.size() == 1 && tokens.front().parameter) {
319 3258 : words_ = regex_words(tokens.front().regex);
320 3258 : if (words_) {
321 12 : may_match_slash_ = std::any_of(words_->begin(), words_->end(),
322 24 : [](const std::string& word) { return word.find('/') != std::string::npos; });
323 3618 : return;
324 : }
325 : }
326 :
327 3657 : bool compiled = true;
328 8061 : for (const auto& token : tokens) {
329 4455 : if (!token.parameter) {
330 2436 : for (char c : token.text) {
331 4950 : atom literal;
332 1650 : literal.chars.set(static_cast<unsigned char>(c));
333 1650 : atoms_.push_back(literal);
334 : }
335 786 : continue;
336 786 : }
337 3669 : size_t first = atoms_.size();
338 3669 : if (token.regex.empty()) {
339 36 : atom any;
340 12 : any.chars.set();
341 12 : any.chars.reset('/');
342 12 : any.max = unbounded;
343 12 : atoms_.push_back(any);
344 3657 : } else if (!compile_regex(token.regex, atoms_)) {
345 51 : compiled = false;
346 51 : break;
347 : }
348 3618 : groups_.push_back({static_cast<uint16_t>(first), static_cast<uint16_t>(atoms_.size())});
349 : }
350 :
351 3657 : if (compiled && atoms_.size() <= max_atoms) {
352 7314 : may_match_slash_ = std::any_of(atoms_.begin(), atoms_.end(), [](const atom& a) { return a.chars['/']; });
353 3606 : catch_all_ = may_match_slash_ && atoms_.size() == 1 && groups_.size() == 1;
354 3606 : return;
355 : }
356 :
357 : // Fall back to std::regex
358 51 : atoms_.clear();
359 51 : groups_.clear();
360 51 : regex_.emplace(key_);
361 51 : size_t group = 1;
362 144 : for (const auto& token : tokens) {
363 93 : if (token.parameter) {
364 57 : regex_groups_.push_back(group);
365 57 : group += 1 + capture_groups(token.regex);
366 57 : may_match_slash_ = may_match_slash_ || regex_may_match_slash(token.regex);
367 : } else {
368 36 : may_match_slash_ = may_match_slash_ || token.text.find('/') != std::string::npos;
369 : }
370 : }
371 51 : catch_all_ = false;
372 0 : }
373 :
374 3657 : bool path_matcher::compile_regex(std::string_view regex, std::vector<atom>& atoms) {
375 3657 : size_t i = 0;
376 7332 : while (i < regex.size()) {
377 11178 : atom a;
378 3726 : char c = regex[i];
379 3726 : if (c == '[') {
380 558 : if (!parse_class(regex, i, a.chars)) return false;
381 3219 : } else if (c == '.') {
382 3108 : a.chars.set();
383 3108 : a.chars.reset('\n');
384 3108 : a.chars.reset('\r');
385 3108 : ++i;
386 111 : } else if (c == '\\') {
387 48 : if (i + 1 >= regex.size()) return false;
388 48 : char escaped = regex[i + 1];
389 48 : if (is_alnum(escaped)) {
390 45 : if (!class_escape(escaped, a.chars)) return false;
391 : } else {
392 3 : a.chars.set(static_cast<unsigned char>(escaped));
393 : }
394 30 : i += 2;
395 63 : } else if (c == '\0' || std::string_view("()|^$*+?{}]").find(c) != std::string_view::npos) {
396 33 : return false;
397 : } else {
398 30 : a.chars.set(static_cast<unsigned char>(c));
399 30 : ++i;
400 : }
401 :
402 : // Quantifier (greedy: lazy ones may change how captures split)
403 3675 : if (i < regex.size()) {
404 3675 : bool quantified = true;
405 3675 : switch (regex[i]) {
406 1572 : case '*': a.min = 0; a.max = unbounded; ++i; break;
407 2025 : case '+': a.min = 1; a.max = unbounded; ++i; break;
408 0 : case '?': a.min = 0; a.max = 1; ++i; break;
409 45 : case '{':
410 45 : if (!parse_braces(regex, i, a.min, a.max, unbounded)) return false;
411 45 : break;
412 33 : default: quantified = false;
413 : }
414 3675 : if (quantified && i < regex.size() && regex[i] == '?') return false;
415 : }
416 :
417 3675 : if (atoms.size() >= max_atoms) return false;
418 3675 : atoms.push_back(a);
419 : }
420 3606 : return true;
421 : }
422 :
423 61437 : bool path_matcher::match_atoms(size_t index, size_t position, std::string_view text, size_t* starts) const {
424 61437 : if (index == atoms_.size()) return position == text.size();
425 61437 : starts[index] = position;
426 61437 : const auto& a = atoms_[index];
427 :
428 : // Longest run of the atom characters, then backtrack down to its minimum (greedy)
429 61437 : size_t limit = std::min<size_t>(a.max, text.size() - position);
430 61437 : size_t run = 0;
431 172854 : while (run < limit && a.chars[static_cast<unsigned char>(text[position + run])]) ++run;
432 61437 : if (run < a.min) return false;
433 15543 : if (index + 1 == atoms_.size()) return position + run == text.size();
434 68028 : for (size_t count = run + 1; count-- > a.min;) {
435 57411 : if (match_atoms(index + 1, position + count, text, starts)) return true;
436 : }
437 10617 : return false;
438 : }
439 :
440 7818 : bool path_matcher::match(std::string_view text, route_captures& captures) const {
441 7818 : if (words_) {
442 6 : if (std::find(words_->begin(), words_->end(), text) == words_->end()) return false;
443 3 : captures.push_back(text);
444 3 : return true;
445 : }
446 :
447 7812 : if (regex_) return match_regex(*regex_, regex_groups_, text, captures);
448 :
449 : // A single atom, as a parameter with a character class: check length and characters
450 7611 : if (atoms_.size() == 1) {
451 3585 : const auto& a = atoms_.front();
452 3585 : if (text.size() < a.min || text.size() > a.max) return false;
453 116451 : for (char c : text) {
454 114393 : if (!a.chars[static_cast<unsigned char>(c)]) return false;
455 : }
456 2058 : if (!groups_.empty()) captures.push_back(text);
457 2058 : return true;
458 : }
459 :
460 : size_t starts[max_atoms + 1];
461 4026 : if (!match_atoms(0, 0, text, starts)) return false;
462 885 : starts[atoms_.size()] = text.size();
463 1776 : for (const auto& g : groups_) {
464 891 : captures.push_back(text.substr(starts[g.first], starts[g.last] - starts[g.first]));
465 : }
466 885 : return true;
467 : }
468 :
469 78 : std::bitset<256> path_matcher::first_chars() const {
470 234 : std::bitset<256> chars;
471 78 : if (words_) {
472 27 : for (const auto& word : *words_) {
473 18 : if (word.empty()) return std::bitset<256>().set();
474 18 : chars.set(static_cast<unsigned char>(word.front()));
475 : }
476 9 : return chars;
477 : }
478 69 : if (!regex_) {
479 48 : for (const auto& a : atoms_) {
480 45 : chars |= a.chars;
481 45 : if (a.min > 0) return chars;
482 : }
483 : }
484 : // Unknown, or the match may be empty
485 27 : return std::bitset<256>().set();
486 : }
487 :
488 39 : bool path_matcher::may_overlap(const path_matcher& other) const {
489 39 : return (first_chars() & other.first_chars()).any();
490 : }
491 :
492 : } // namespace thinger::http::detail
|
