Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
url_pattern_helpers.cpp
Go to the documentation of this file.
1#if ADA_INCLUDE_URL_PATTERN
3
4#include <algorithm>
5#include <array>
6#include <charconv>
7#include <cstddef>
8#include <cstdint>
9#include <optional>
10#include <ranges>
11#include <string>
12#include <string_view>
13#include <system_error>
14#include <tuple>
15#include <utility>
16#include <vector>
17
18#include "ada/character_sets.h"
19#include "ada/checkers.h"
20#include "ada/helpers.h"
21#include "ada/scheme.h"
22#include "ada/unicode.h"
23
24namespace ada::url_pattern_helpers {
25
26std::tuple<std::string, std::vector<std::string>>
27generate_regular_expression_and_name_list(
28 const std::vector<url_pattern_part>& part_list,
29 url_pattern_compile_component_options options) {
30 // Let result be "^"
31 std::string result = "^";
32 // Reserve capacity to reduce reallocations
33 result.reserve(part_list.size() * 16);
34
35 // Let name list be a new list
36 std::vector<std::string> name_list{};
37 name_list.reserve(part_list.size());
38
39 // Pre-generate segment wildcard regexp if needed (avoids repeated generation)
40 std::string segment_wildcard_regexp;
41
42 // For each part of part list:
43 for (const url_pattern_part& part : part_list) {
44 // If part's type is "fixed-text":
45 if (part.type == url_pattern_part_type::FIXED_TEXT) {
46 // If part's modifier is "none"
47 if (part.modifier == url_pattern_part_modifier::none) {
48 result.append(escape_regexp_string(part.value));
49 } else {
50 // (?:<fixed text>)<modifier>
51 result.append("(?:");
52 result.append(escape_regexp_string(part.value));
53 result.push_back(')');
54 result.append(convert_modifier_to_string(part.modifier));
55 }
56 continue;
57 }
58
59 // Assert: part's name is not the empty string
60 ADA_ASSERT_TRUE(!part.name.empty());
61 name_list.push_back(part.name);
62
63 // Use string_view to avoid copies where possible
64 std::string_view regexp_value = part.value;
65
66 if (part.type == url_pattern_part_type::SEGMENT_WILDCARD) {
67 // Lazy generate segment wildcard regexp
68 if (segment_wildcard_regexp.empty()) {
69 segment_wildcard_regexp = generate_segment_wildcard_regexp(options);
70 }
71 regexp_value = segment_wildcard_regexp;
72 } else if (part.type == url_pattern_part_type::FULL_WILDCARD) {
73 regexp_value = ".*";
74 }
75
76 // If part's prefix is the empty string and part's suffix is the empty
77 // string
78 if (part.prefix.empty() && part.suffix.empty()) {
79 // If part's modifier is "none" or "optional"
80 if (part.modifier == url_pattern_part_modifier::none ||
81 part.modifier == url_pattern_part_modifier::optional) {
82 // (<regexp value>)<modifier>
83 result.push_back('(');
84 result.append(regexp_value);
85 result.push_back(')');
86 result.append(convert_modifier_to_string(part.modifier));
87 } else {
88 // ((?:<regexp value>)<modifier>)
89 result.append("((?:");
90 result.append(regexp_value);
91 result.push_back(')');
92 result.append(convert_modifier_to_string(part.modifier));
93 result.push_back(')');
94 }
95 continue;
96 }
97
98 // If part's modifier is "none" or "optional"
99 if (part.modifier == url_pattern_part_modifier::none ||
100 part.modifier == url_pattern_part_modifier::optional) {
101 // (?:<prefix>(<regexp value>)<suffix>)<modifier>
102 result.append("(?:");
103 result.append(escape_regexp_string(part.prefix));
104 result.push_back('(');
105 result.append(regexp_value);
106 result.push_back(')');
107 result.append(escape_regexp_string(part.suffix));
108 result.push_back(')');
109 result.append(convert_modifier_to_string(part.modifier));
110 continue;
111 }
112
113 // Assert: part's modifier is "zero-or-more" or "one-or-more"
114 ADA_ASSERT_TRUE(part.modifier == url_pattern_part_modifier::zero_or_more ||
115 part.modifier == url_pattern_part_modifier::one_or_more);
116
117 // Assert: part's prefix is not the empty string or part's suffix is not the
118 // empty string
119 ADA_ASSERT_TRUE(!part.prefix.empty() || !part.suffix.empty());
120
121 // (?:<prefix>((?:<regexp value>)(?:<suffix><prefix>(?:<regexp
122 // value>))*)<suffix>)?
123 // Append "(?:" to the end of result.
124 result.append("(?:");
125 // Append the result of running escape a regexp string given part's prefix
126 // to the end of result.
127 result.append(escape_regexp_string(part.prefix));
128 // Append "((?:" to the end of result.
129 result.append("((?:");
130 // Append regexp value to the end of result.
131 result.append(regexp_value);
132 // Append ")(?:" to the end of result.
133 result.append(")(?:");
134 // Append the result of running escape a regexp string given part's suffix
135 // to the end of result.
136 result.append(escape_regexp_string(part.suffix));
137 // Append the result of running escape a regexp string given part's prefix
138 // to the end of result.
139 result.append(escape_regexp_string(part.prefix));
140 // Append "(?:" to the end of result.
141 result.append("(?:");
142 // Append regexp value to the end of result.
143 result.append(regexp_value);
144 // Append "))*)" to the end of result.
145 result.append("))*)");
146 // Append the result of running escape a regexp string given part's suffix
147 // to the end of result.
148 result.append(escape_regexp_string(part.suffix));
149 // Append ")" to the end of result.
150 result.append(")");
151
152 // If part's modifier is "zero-or-more" then append "?" to the end of result
153 if (part.modifier == url_pattern_part_modifier::zero_or_more) {
154 result += "?";
155 }
156 }
157
158 // Append "$" to the end of result
159 result += "$";
160
161 // Return (result, name list)
162 return {std::move(result), std::move(name_list)};
163}
164
165bool is_ipv6_address(std::string_view input) noexcept {
166 // If input's code point length is less than 2, then return false.
167 if (input.size() < 2) return false;
168
169 // Let input code points be input interpreted as a list of code points.
170 // If input code points[0] is U+005B ([), then return true.
171 if (input.front() == '[') return true;
172 // If input code points[0] is U+007B ({) and input code points[1] is U+005B
173 // ([), then return true.
174 if (input.starts_with("{[")) return true;
175 // If input code points[0] is U+005C (\‍) and input code points[1] is U+005B
176 // ([), then return true.
177 return input.starts_with("\\[");
178}
179
180std::string_view convert_modifier_to_string(
181 url_pattern_part_modifier modifier) {
182 switch (modifier) {
183 // If modifier is "zero-or-more", then return "*".
184 case url_pattern_part_modifier::zero_or_more:
185 return "*";
186 // If modifier is "optional", then return "?".
187 case url_pattern_part_modifier::optional:
188 return "?";
189 // If modifier is "one-or-more", then return "+".
190 case url_pattern_part_modifier::one_or_more:
191 return "+";
192 // Return the empty string.
193 default:
194 return "";
195 }
196}
197
198std::string generate_segment_wildcard_regexp(
199 url_pattern_compile_component_options options) {
200 // Let result be "[^".
201 std::string result = "[^";
202 // Append the result of running escape a regexp string given options's
203 // delimiter code point to the end of result.
204 result.append(escape_regexp_string(options.get_delimiter()));
205 // Append "]+?" to the end of result.
206 result.append("]+?");
207 // Return result.
208 ada_log("generate_segment_wildcard_regexp result: ", result);
209 return result;
210}
211
212namespace {
213// Unified lookup table for URL pattern character classification
214// Bit flags for different character types
215constexpr uint8_t CHAR_SCHEME = 1; // valid in scheme (a-z, A-Z, 0-9, +, -, .)
216constexpr uint8_t CHAR_UPPER = 2; // uppercase letter (needs lowercasing)
217constexpr uint8_t CHAR_SIMPLE_HOSTNAME = 4; // simple hostname (a-z, 0-9, -, .)
218constexpr uint8_t CHAR_SIMPLE_PATHNAME =
219 8; // simple pathname (a-z, A-Z, 0-9, /, -, _, ~)
220
221constexpr std::array<uint8_t, 256> char_class_table = []() consteval {
222 std::array<uint8_t, 256> table{};
223 for (int c = 'a'; c <= 'z'; c++)
224 table[c] = CHAR_SCHEME | CHAR_SIMPLE_HOSTNAME | CHAR_SIMPLE_PATHNAME;
225 for (int c = 'A'; c <= 'Z'; c++)
226 table[c] = CHAR_SCHEME | CHAR_UPPER | CHAR_SIMPLE_PATHNAME;
227 for (int c = '0'; c <= '9'; c++)
228 table[c] = CHAR_SCHEME | CHAR_SIMPLE_HOSTNAME | CHAR_SIMPLE_PATHNAME;
229 table['+'] = CHAR_SCHEME;
230 table['-'] = CHAR_SCHEME | CHAR_SIMPLE_HOSTNAME | CHAR_SIMPLE_PATHNAME;
231 table['.'] =
232 CHAR_SCHEME | CHAR_SIMPLE_HOSTNAME; // not pathname (needs normalization)
233 table['/'] = CHAR_SIMPLE_PATHNAME;
234 table['_'] = CHAR_SIMPLE_PATHNAME;
235 table['~'] = CHAR_SIMPLE_PATHNAME;
236 return table;
237}();
238} // namespace
239
240tl::expected<std::string, errors> canonicalize_protocol(
241 std::string_view input) {
242 ada_log("canonicalize_protocol called with input=", input);
243 if (input.empty()) [[unlikely]] {
244 return "";
245 }
246
247 if (input.ends_with(":")) {
248 input.remove_suffix(1);
249 if (input.empty()) [[unlikely]] {
250 return tl::unexpected(errors::type_error);
251 }
252 }
253
254 // Fast path: special schemes are already canonical
255 if (scheme::is_special(input)) {
256 return std::string(input);
257 }
258
259 // Fast path: validate scheme chars and check for uppercase
260 // First char must be alpha (not +, -, ., or digit)
261 uint8_t first_flags = char_class_table[static_cast<uint8_t>(input[0])];
262 if (!(first_flags & CHAR_SCHEME) || input[0] == '+' || input[0] == '-' ||
263 input[0] == '.' || unicode::is_ascii_digit(input[0])) {
264 return tl::unexpected(errors::type_error);
265 }
266
267 uint8_t needs_lowercase = first_flags & CHAR_UPPER;
268 for (size_t i = 1; i < input.size(); i++) {
269 uint8_t flags = char_class_table[static_cast<uint8_t>(input[i])];
270 if (!(flags & CHAR_SCHEME)) {
271 return tl::unexpected(errors::type_error);
272 }
273 needs_lowercase |= flags & CHAR_UPPER;
274 }
275
276 if (needs_lowercase == 0) {
277 return std::string(input);
278 }
279
280 std::string result(input);
281 unicode::to_lower_ascii(result.data(), result.size());
282 return result;
283}
284
285tl::expected<std::string, errors> canonicalize_username(
286 std::string_view input) {
287 // If value is the empty string, return value.
288 if (input.empty()) [[unlikely]] {
289 return "";
290 }
291 // Percent-encode the input using the userinfo percent-encode set.
293 input, character_sets::USERINFO_PERCENT_ENCODE);
294 if (idx == input.size()) {
295 // No encoding needed, return input as-is
296 return std::string(input);
297 }
298 // Percent-encode from the first character that needs encoding
299 return ada::unicode::percent_encode(
300 input, character_sets::USERINFO_PERCENT_ENCODE, idx);
301}
302
303tl::expected<std::string, errors> canonicalize_password(
304 std::string_view input) {
305 // If value is the empty string, return value.
306 if (input.empty()) [[unlikely]] {
307 return "";
308 }
309 // Percent-encode the input using the userinfo percent-encode set.
311 input, character_sets::USERINFO_PERCENT_ENCODE);
312 if (idx == input.size()) {
313 // No encoding needed, return input as-is
314 return std::string(input);
315 }
316 // Percent-encode from the first character that needs encoding
317 return ada::unicode::percent_encode(
318 input, character_sets::USERINFO_PERCENT_ENCODE, idx);
319}
320
321tl::expected<std::string, errors> canonicalize_hostname(
322 std::string_view input) {
323 ada_log("canonicalize_hostname input=", input);
324 if (input.empty()) [[unlikely]] {
325 return "";
326 }
327
328 // Fast path: simple hostnames (lowercase ASCII, digits, -, .) need no IDNA.
329 // The simple character set also covers IPv4-shaped hosts, which the slow
330 // path rewrites ("0" -> "0.0.0.0", "0x7f.1" -> "127.0.0.1"). Exclude those
331 // so the fast path can't return a non-canonical hostname.
332 //
333 // Pure-ASCII "xn--" labels are intentionally left on the fast path: with
334 // beStrict=false, domain-to-ASCII returns the lowercased ASCII input even
335 // when Unicode ToASCII would fail (e.g. invalid ACE "xn--a"). See
336 // https://url.spec.whatwg.org/#concept-domain-to-ascii
337 bool needs_processing = false;
338 for (char c : input) {
339 needs_processing |=
340 !(char_class_table[static_cast<uint8_t>(c)] & CHAR_SIMPLE_HOSTNAME);
341 }
342 if (!needs_processing && !checkers::is_ipv4(input)) {
343 return std::string(input);
344 }
345
346 // Let dummyURL be a new URL record.
347 // Let parseResult be the result of running the basic URL parser given value
348 // with dummyURL as url and hostname state as state override.
349
350 // IMPORTANT: The protocol needs to be a special protocol, otherwise the
351 // hostname will not be converted using IDNA.
352 auto url = ada::parse<url_aggregator>("https://dummy.test", nullptr);
353 ADA_ASSERT_TRUE(url);
354 // if (!isValidHostnameInput(hostname)) return kj::none;
355 if (!url->set_hostname(input)) {
356 // If parseResult is failure, then throw a TypeError.
357 return tl::unexpected(errors::type_error);
358 }
359 // Return dummyURL's host, serialized, or empty string if it is null.
360 return std::string(url->get_hostname());
361}
362
363tl::expected<std::string, errors> canonicalize_ipv6_hostname(
364 std::string_view input) {
365 ada_log("canonicalize_ipv6_hostname input=", input);
366 // TODO: Optimization opportunity: Use lookup table to speed up checking
367 if (std::ranges::any_of(input, [](char c) {
368 return c != '[' && c != ']' && c != ':' &&
369 !unicode::is_ascii_hex_digit(c);
370 })) {
371 return tl::unexpected(errors::type_error);
372 }
373 // Append the result of running ASCII lowercase given code point to the end of
374 // result.
375 auto hostname = std::string(input);
376 unicode::to_lower_ascii(hostname.data(), hostname.size());
377 return hostname;
378}
379
380tl::expected<std::string, errors> canonicalize_port(
381 std::string_view port_value) {
382 // If portValue is the empty string, return portValue.
383 if (port_value.empty()) [[unlikely]] {
384 return "";
385 }
386
387 // Remove ASCII tab or newline characters
388 std::string trimmed(port_value);
389 helpers::remove_ascii_tab_or_newline(trimmed);
390
391 if (trimmed.empty()) {
392 return "";
393 }
394
395 // Input should start with a digit character
396 if (!unicode::is_ascii_digit(trimmed.front())) {
397 return tl::unexpected(errors::type_error);
398 }
399
400 // Find the first non-digit character
401 auto first_non_digit =
402 std::ranges::find_if_not(trimmed, unicode::is_ascii_digit);
403 std::string_view digits_to_parse =
404 std::string_view(trimmed.data(), first_non_digit - trimmed.begin());
405
406 // Here we have a range of ASCII digit characters identified by
407 // digits_to_parse. It is non-empty. The port state of the URL parser reads
408 // it as an integer, so leading zeros are part of the number: "0080" is 80
409 // and "065535" is 65535, not a six-digit overflow. Only the significant
410 // digits count toward the 5-digit maximum, matching the fast path in
411 // implementation.cpp.
412 size_t first_significant = digits_to_parse.find_first_not_of('0');
413 if (first_significant == std::string_view::npos) {
414 // The value is all zeros, i.e. port 0.
415 return "0";
416 }
417 digits_to_parse.remove_prefix(first_significant);
418 // We want to determine whether it is a valid port number (0-65535).
419 // Clearly, if the length is greater than 5, it is invalid.
420 // If the length is 5, we need to compare lexicographically to "65535".
421 // Otherwise it is valid.
422 if (digits_to_parse.size() == 5) {
423 if (digits_to_parse > "65535") {
424 return tl::unexpected(errors::type_error);
425 }
426 } else if (digits_to_parse.size() > 5) {
427 return tl::unexpected(errors::type_error);
428 }
429 // It is valid! Most times, we do not need to parse it into an integer.
430 return std::string(digits_to_parse);
431}
432
433tl::expected<std::string, errors> canonicalize_port_with_protocol(
434 std::string_view port_value, std::string_view protocol) {
435 // If portValue is the empty string, return portValue.
436 if (port_value.empty()) [[unlikely]] {
437 return "";
438 }
439
440 // Handle empty or trailing colon in protocol
441 if (protocol.empty()) {
442 protocol = "fake";
443 } else if (protocol.ends_with(":")) {
444 protocol.remove_suffix(1);
445 }
446
447 // Remove ASCII tab or newline characters
448 std::string trimmed(port_value);
449 helpers::remove_ascii_tab_or_newline(trimmed);
450
451 if (trimmed.empty()) {
452 return "";
453 }
454
455 // Input should start with a digit character
456 if (!unicode::is_ascii_digit(trimmed.front())) {
457 return tl::unexpected(errors::type_error);
458 }
459
460 // Find the first non-digit character
461 auto first_non_digit =
462 std::ranges::find_if_not(trimmed, unicode::is_ascii_digit);
463 std::string_view digits_to_parse =
464 std::string_view(trimmed.data(), first_non_digit - trimmed.begin());
465
466 // Parse the port number
467 uint16_t parsed_port{};
468 // NOLINTNEXTLINE(bugprone-suspicious-stringview-data-usage)
469 auto result = std::from_chars(digits_to_parse.data(),
470 digits_to_parse.data() + digits_to_parse.size(),
471 parsed_port);
472
473 if (result.ec == std::errc::result_out_of_range) {
474 return tl::unexpected(errors::type_error);
475 }
476
477 if (result.ec == std::errc()) {
478 // Check if this is the default port for the scheme
479 uint16_t default_port = scheme::get_special_port(protocol);
480
481 // If it's the default port for a special scheme, return empty string
482 if (default_port != 0 && default_port == parsed_port) {
483 return "";
484 }
485
486 // Successfully parsed, return as string
487 return std::to_string(parsed_port);
488 }
489
490 return tl::unexpected(errors::type_error);
491}
492
493tl::expected<std::string, errors> canonicalize_pathname(
494 std::string_view input) {
495 if (input.empty()) [[unlikely]] {
496 return "";
497 }
498
499 // Fast path: simple pathnames (no . which needs normalization) can be
500 // returned as-is
501 bool needs_processing = false;
502 for (char c : input) {
503 needs_processing |=
504 !(char_class_table[static_cast<uint8_t>(c)] & CHAR_SIMPLE_PATHNAME);
505 }
506 if (!needs_processing) {
507 return std::string(input);
508 }
509
510 // Let leading slash be true if the first code point in value is U+002F (/)
511 // and otherwise false.
512 const bool leading_slash = input.starts_with("/");
513 // Let modified value be "/-" if leading slash is false and otherwise the
514 // empty string.
515 const auto modified_value =
516 (leading_slash ? std::string() : std::string("/-")) + std::string(input);
517 // The spec runs the basic URL parser with the path in state override, where
518 // '?' and '#' are ordinary path code points (percent-encoded) and leading or
519 // trailing C0 control or space is kept. Building a full URL string and
520 // parsing it (no state override) instead let '?' and '#' start the
521 // query/fragment, so the pathname was silently truncated at the first literal
522 // '?' or '#'. set_pathname runs the parser in path state override, matching
523 // how canonicalize_hostname uses set_hostname.
524 // The spec's "create a dummy URL" is "https://dummy.invalid/": a special
525 // URL, so the path parser turns "\\" into "/" as it does in a special URL.
526 // A non-special dummy kept a literal backslash, so a pattern such as
527 // "/a\\b" never matched "https://h/a/b".
528 auto url = ada::parse<url_aggregator>("https://dummy.invalid/", nullptr);
529 ADA_ASSERT_TRUE(url);
530 if (!url->set_pathname(modified_value)) {
531 // If parseResult is failure, then throw a TypeError.
532 return tl::unexpected(errors::type_error);
533 }
534 const auto pathname = url->get_pathname();
535 // If leading slash is false, then set result to the code point substring
536 // from 2 to the end of the string within result.
537 if (!leading_slash) {
538 // pathname should start with "/-" but path traversal (e.g. "../../")
539 // can reduce it to just "/" which is shorter than 2 characters.
540 if (pathname.size() < 2) {
541 return tl::unexpected(errors::type_error);
542 }
543 return std::string(pathname.substr(2));
544 }
545 return std::string(pathname);
546}
547
548tl::expected<std::string, errors> canonicalize_opaque_pathname(
549 std::string_view input) {
550 // If value is the empty string, return value.
551 if (input.empty()) [[unlikely]] {
552 return "";
553 }
554 // Opaque-path state: no authority and no dot-segment normalization.
555 std::string value(input);
556 helpers::remove_ascii_tab_or_newline(value);
557 return ada::unicode::percent_encode(
558 value, character_sets::C0_CONTROL_PERCENT_ENCODE);
559}
560
561tl::expected<std::string, errors> canonicalize_search(std::string_view input) {
562 // If value is the empty string, return value.
563 if (input.empty()) [[unlikely]] {
564 return "";
565 }
566 // A leading '?' is a valid query code point here: it is the caller (process a
567 // search) that removes a single delimiter, not this step, which mirrors the
568 // basic URL parser's query state.
569 std::string new_value(input);
570 // Remove ASCII tab or newline characters
571 helpers::remove_ascii_tab_or_newline(new_value);
572
573 if (new_value.empty()) {
574 return "";
575 }
576
577 // The spec's dummy URL is special, so use the special-query set.
579 new_value, character_sets::SPECIAL_QUERY_PERCENT_ENCODE);
580 if (idx == new_value.size()) {
581 // No encoding needed
582 return new_value;
583 }
584 // Percent-encode from the first character that needs encoding
585 return ada::unicode::percent_encode(
586 new_value, character_sets::SPECIAL_QUERY_PERCENT_ENCODE, idx);
587}
588
589tl::expected<std::string, errors> canonicalize_hash(std::string_view input) {
590 // If value is the empty string, return value.
591 if (input.empty()) [[unlikely]] {
592 return "";
593 }
594 // A leading '#' is a valid fragment code point here: it is the caller
595 // (process a hash) that removes a single delimiter, not this step, which
596 // mirrors the basic URL parser's fragment state.
597 std::string new_value(input);
598 // Remove ASCII tab or newline characters
599 helpers::remove_ascii_tab_or_newline(new_value);
600
601 if (new_value.empty()) {
602 return "";
603 }
604
605 // Percent-encode using FRAGMENT_PERCENT_ENCODE
607 new_value, character_sets::FRAGMENT_PERCENT_ENCODE);
608 if (idx == new_value.size()) {
609 // No encoding needed
610 return new_value;
611 }
612 // Percent-encode from the first character that needs encoding
613 return ada::unicode::percent_encode(
614 new_value, character_sets::FRAGMENT_PERCENT_ENCODE, idx);
615}
616
617tl::expected<std::vector<token>, errors> tokenize(std::string_view input,
618 token_policy policy) {
619 ada_log("tokenize input: ", input);
620 // Let tokenizer be a new tokenizer.
621 // Set tokenizer's input to input.
622 // Set tokenizer's policy to policy.
623 auto tokenizer = Tokenizer(input, policy);
624 // While tokenizer's index is less than tokenizer's input's code point length:
625 while (tokenizer.index < tokenizer.input.size()) {
626 // Run seek and get the next code point given tokenizer and tokenizer's
627 // index.
628 tokenizer.seek_and_get_next_code_point(tokenizer.index);
629
630 // Malformed UTF-8 must not stall tokenization: report an invalid-char
631 // token (lenient) or fail fast (strict), while always making progress.
632 if (tokenizer.had_invalid_code_point()) {
633 if (auto error = tokenizer.process_tokenizing_error(tokenizer.next_index,
634 tokenizer.index)) {
635 return tl::unexpected(*error);
636 }
637 continue;
638 }
639
640 // If tokenizer's code point is U+002A (*):
641 if (tokenizer.code_point == '*') {
642 // Run add a token with default position and length given tokenizer and
643 // "asterisk".
644 tokenizer.add_token_with_defaults(token_type::ASTERISK);
645 ada_log("add ASTERISK token");
646 // Continue.
647 continue;
648 }
649
650 // If tokenizer's code point is U+002B (+) or U+003F (?):
651 if (tokenizer.code_point == '+' || tokenizer.code_point == '?') {
652 // Run add a token with default position and length given tokenizer and
653 // "other-modifier".
654 tokenizer.add_token_with_defaults(token_type::OTHER_MODIFIER);
655 // Continue.
656 continue;
657 }
658
659 // If tokenizer's code point is U+005C (\‍):
660 if (tokenizer.code_point == '\\') {
661 // If tokenizer's index is equal to tokenizer's input's code point length
662 // - 1:
663 if (tokenizer.index == tokenizer.input.size() - 1) {
664 // Run process a tokenizing error given tokenizer, tokenizer's next
665 // index, and tokenizer's index.
666 if (auto error = tokenizer.process_tokenizing_error(
667 tokenizer.next_index, tokenizer.index)) {
668 ada_log("process_tokenizing_error failed");
669 return tl::unexpected(*error);
670 }
671 continue;
672 }
673
674 // Let escaped index be tokenizer's next index.
675 auto escaped_index = tokenizer.next_index;
676 // Run get the next code point given tokenizer.
677 tokenizer.get_next_code_point();
678 if (tokenizer.had_invalid_code_point()) {
679 if (auto error = tokenizer.process_tokenizing_error(
680 tokenizer.next_index, escaped_index)) {
681 return tl::unexpected(*error);
682 }
683 continue;
684 }
685 // Run add a token with default length given tokenizer, "escaped-char",
686 // tokenizer's next index, and escaped index.
687 tokenizer.add_token_with_default_length(
688 token_type::ESCAPED_CHAR, tokenizer.next_index, escaped_index);
689 ada_log("add ESCAPED_CHAR token on next_index ", tokenizer.next_index,
690 " with escaped index ", escaped_index);
691 // Continue.
692 continue;
693 }
694
695 // If tokenizer's code point is U+007B ({):
696 if (tokenizer.code_point == '{') {
697 // Run add a token with default position and length given tokenizer and
698 // "open".
699 tokenizer.add_token_with_defaults(token_type::OPEN);
700 ada_log("add OPEN token");
701 continue;
702 }
703
704 // If tokenizer's code point is U+007D (}):
705 if (tokenizer.code_point == '}') {
706 // Run add a token with default position and length given tokenizer and
707 // "close".
708 tokenizer.add_token_with_defaults(token_type::CLOSE);
709 ada_log("add CLOSE token");
710 continue;
711 }
712
713 // If tokenizer's code point is U+003A (:):
714 if (tokenizer.code_point == ':') {
715 // Let name position be tokenizer's next index.
716 auto name_position = tokenizer.next_index;
717 // Let name start be name position.
718 auto name_start = name_position;
719 bool invalid_name = false;
720 // While name position is less than tokenizer's input's code point length:
721 while (name_position < tokenizer.input.size()) {
722 // Run seek and get the next code point given tokenizer and name
723 // position.
724 tokenizer.seek_and_get_next_code_point(name_position);
725 if (tokenizer.had_invalid_code_point()) {
726 if (auto error = tokenizer.process_tokenizing_error(
727 tokenizer.next_index, name_position)) {
728 return tl::unexpected(*error);
729 }
730 invalid_name = true;
731 break;
732 }
733 // Let first code point be true if name position equals name start and
734 // false otherwise.
735 bool first_code_point = name_position == name_start;
736 // Let valid code point be the result of running is a valid name code
737 // point given tokenizer's code point and first code point.
738 auto valid_code_point =
739 idna::valid_name_code_point(tokenizer.code_point, first_code_point);
740 ada_log("tokenizer.code_point=", uint32_t(tokenizer.code_point),
741 " first_code_point=", first_code_point,
742 " valid_code_point=", valid_code_point);
743 // If valid code point is false break.
744 if (!valid_code_point) break;
745 // Set name position to tokenizer's next index.
746 name_position = tokenizer.next_index;
747 }
748
749 if (invalid_name) {
750 continue;
751 }
752
753 // If name position is less than or equal to name start:
754 if (name_position <= name_start) {
755 // Run process a tokenizing error given tokenizer, name start, and
756 // tokenizer's index.
757 if (auto error = tokenizer.process_tokenizing_error(name_start,
758 tokenizer.index)) {
759 ada_log("process_tokenizing_error failed");
760 return tl::unexpected(*error);
761 }
762 // Continue
763 continue;
764 }
765
766 // Run add a token with default length given tokenizer, "name", name
767 // position, and name start.
768 tokenizer.add_token_with_default_length(token_type::NAME, name_position,
769 name_start);
770 continue;
771 }
772
773 // If tokenizer's code point is U+0028 (():
774 if (tokenizer.code_point == '(') {
775 // Let depth be 1.
776 size_t depth = 1;
777 // Let regexp position be tokenizer's next index.
778 auto regexp_position = tokenizer.next_index;
779 // Let regexp start be regexp position.
780 auto regexp_start = regexp_position;
781 // Let error be false.
782 bool error = false;
783
784 // While regexp position is less than tokenizer's input's code point
785 // length:
786 while (regexp_position < tokenizer.input.size()) {
787 // Run seek and get the next code point given tokenizer and regexp
788 // position.
789 tokenizer.seek_and_get_next_code_point(regexp_position);
790 if (tokenizer.had_invalid_code_point()) {
791 if (auto process_error = tokenizer.process_tokenizing_error(
792 tokenizer.next_index, regexp_position)) {
793 return tl::unexpected(*process_error);
794 }
795 error = true;
796 break;
797 }
798
799 // TODO: Optimization opportunity: The next 2 if statements can be
800 // merged. If the result of running is ASCII given tokenizer's code
801 // point is false:
802 if (!unicode::is_ascii(tokenizer.code_point)) {
803 // Run process a tokenizing error given tokenizer, regexp start, and
804 // tokenizer's index.
805 if (auto process_error = tokenizer.process_tokenizing_error(
806 regexp_start, tokenizer.index)) {
807 return tl::unexpected(*process_error);
808 }
809 // Set error to true.
810 error = true;
811 break;
812 }
813
814 // If regexp position equals regexp start and tokenizer's code point is
815 // U+003F (?):
816 if (regexp_position == regexp_start && tokenizer.code_point == '?') {
817 // Run process a tokenizing error given tokenizer, regexp start, and
818 // tokenizer's index.
819 if (auto process_error = tokenizer.process_tokenizing_error(
820 regexp_start, tokenizer.index)) {
821 return tl::unexpected(*process_error);
822 }
823 // Set error to true;
824 error = true;
825 break;
826 }
827
828 // If tokenizer's code point is U+005C (\‍):
829 if (tokenizer.code_point == '\\') {
830 // If regexp position equals tokenizer's input's code point length - 1
831 if (regexp_position == tokenizer.input.size() - 1) {
832 // Run process a tokenizing error given tokenizer, regexp start, and
833 // tokenizer's index.
834 if (auto process_error = tokenizer.process_tokenizing_error(
835 regexp_start, tokenizer.index)) {
836 return tl::unexpected(*process_error);
837 }
838 // Set error to true.
839 error = true;
840 break;
841 }
842 // Run get the next code point given tokenizer.
843 auto escaped_index = tokenizer.next_index;
844 tokenizer.get_next_code_point();
845 if (tokenizer.had_invalid_code_point()) {
846 if (auto process_error = tokenizer.process_tokenizing_error(
847 tokenizer.next_index, escaped_index)) {
848 return tl::unexpected(*process_error);
849 }
850 error = true;
851 break;
852 }
853 // If the result of running is ASCII given tokenizer's code point is
854 // false:
855 if (!unicode::is_ascii(tokenizer.code_point)) {
856 // Run process a tokenizing error given tokenizer, regexp start, and
857 // tokenizer's index.
858 if (auto process_error = tokenizer.process_tokenizing_error(
859 regexp_start, tokenizer.index);
860 process_error.has_value()) {
861 return tl::unexpected(*process_error);
862 }
863 // Set error to true.
864 error = true;
865 break;
866 }
867 // Set regexp position to tokenizer's next index.
868 regexp_position = tokenizer.next_index;
869 continue;
870 }
871
872 // If tokenizer's code point is U+0029 ()):
873 if (tokenizer.code_point == ')') {
874 // Decrement depth by 1.
875 depth--;
876 // If depth is 0:
877 if (depth == 0) {
878 // Set regexp position to tokenizer's next index.
879 regexp_position = tokenizer.next_index;
880 // Break.
881 break;
882 }
883 } else if (tokenizer.code_point == '(') {
884 // Otherwise if tokenizer's code point is U+0028 (():
885 // Increment depth by 1.
886 depth++;
887 // If regexp position equals tokenizer's input's code point length -
888 // 1:
889 if (regexp_position == tokenizer.input.size() - 1) {
890 // Run process a tokenizing error given tokenizer, regexp start, and
891 // tokenizer's index.
892 if (auto process_error = tokenizer.process_tokenizing_error(
893 regexp_start, tokenizer.index)) {
894 return tl::unexpected(*process_error);
895 }
896 // Set error to true.
897 error = true;
898 break;
899 }
900 // Let temporary position be tokenizer's next index.
901 auto temporary_position = tokenizer.next_index;
902 // Run get the next code point given tokenizer.
903 tokenizer.get_next_code_point();
904 if (tokenizer.had_invalid_code_point()) {
905 if (auto process_error = tokenizer.process_tokenizing_error(
906 tokenizer.next_index, temporary_position)) {
907 return tl::unexpected(*process_error);
908 }
909 error = true;
910 break;
911 }
912 // If tokenizer's code point is not U+003F (?):
913 if (tokenizer.code_point != '?') {
914 // Run process a tokenizing error given tokenizer, regexp start, and
915 // tokenizer's index.
916 if (auto process_error = tokenizer.process_tokenizing_error(
917 regexp_start, tokenizer.index)) {
918 return tl::unexpected(*process_error);
919 }
920 // Set error to true.
921 error = true;
922 break;
923 }
924 // Set tokenizer's next index to temporary position.
925 tokenizer.next_index = temporary_position;
926 }
927 // Set regexp position to tokenizer's next index.
928 regexp_position = tokenizer.next_index;
929 }
930
931 // If error is true continue.
932 if (error) continue;
933 // If depth is not zero:
934 if (depth != 0) {
935 // Run process a tokenizing error given tokenizer, regexp start, and
936 // tokenizer's index.
937 if (auto process_error = tokenizer.process_tokenizing_error(
938 regexp_start, tokenizer.index)) {
939 return tl::unexpected(*process_error);
940 }
941 continue;
942 }
943 // Let regexp length be regexp position - regexp start - 1.
944 auto regexp_length = regexp_position - regexp_start - 1;
945 // If regexp length is zero:
946 if (regexp_length == 0) {
947 // Run process a tokenizing error given tokenizer, regexp start, and
948 // tokenizer's index.
949 if (auto process_error = tokenizer.process_tokenizing_error(
950 regexp_start, tokenizer.index)) {
951 ada_log("process_tokenizing_error failed");
952 return tl::unexpected(*process_error);
953 }
954 continue;
955 }
956 // Run add a token given tokenizer, "regexp", regexp position, regexp
957 // start, and regexp length.
958 tokenizer.add_token(token_type::REGEXP, regexp_position, regexp_start,
959 regexp_length);
960 continue;
961 }
962 // Run add a token with default position and length given tokenizer and
963 // "char".
964 tokenizer.add_token_with_defaults(token_type::CHAR);
965 }
966 // Run add a token with default length given tokenizer, "end", tokenizer's
967 // index, and tokenizer's index.
968 tokenizer.add_token_with_default_length(token_type::END, tokenizer.index,
969 tokenizer.index);
970
971 ada_log("tokenizer.token_list size is: ", tokenizer.token_list.size());
972 // Return tokenizer's token list.
973 return tokenizer.token_list;
974}
975
976namespace {
977constexpr std::array<uint8_t, 256> escape_pattern_table = []() consteval {
978 std::array<uint8_t, 256> out{};
979 for (auto& c : {'+', '*', '?', ':', '{', '}', '(', ')', '\\'}) {
980 out[c] = 1;
981 }
982 return out;
983}();
984
985constexpr bool should_escape_pattern_char(char c) {
986 return escape_pattern_table[static_cast<uint8_t>(c)];
987}
988} // namespace
989
990std::string escape_pattern_string(std::string_view input) {
991 ada_log("escape_pattern_string called with input=", input);
992 if (input.empty()) [[unlikely]] {
993 return "";
994 }
995 // Assert: input is an ASCII string.
997 // Let result be the empty string.
998 std::string result{};
999 // Reserve extra space for potential escapes
1000 result.reserve(input.size() * 2);
1001
1002 // While index is less than input's length:
1003 for (const char c : input) {
1004 if (should_escape_pattern_char(c)) {
1005 // Append U+005C (\‍) to the end of result.
1006 result.push_back('\\');
1007 }
1008 // Append c to the end of result.
1009 result.push_back(c);
1010 }
1011 // Return result.
1012 return result;
1013}
1014
1015namespace {
1016constexpr std::array<uint8_t, 256> escape_regexp_table = []() consteval {
1017 std::array<uint8_t, 256> out{};
1018 for (auto& c : {'.', '+', '*', '?', '^', '$', '{', '}', '(', ')', '[', ']',
1019 '|', '/', '\\'}) {
1020 out[c] = 1;
1021 }
1022 return out;
1023}();
1024
1025constexpr bool should_escape_regexp_char(char c) {
1026 return escape_regexp_table[(uint8_t)c];
1027}
1028} // namespace
1029
1030std::string escape_regexp_string(std::string_view input) {
1031 // Assert: input is an ASCII string.
1032 ADA_ASSERT_TRUE(idna::is_ascii(input));
1033 // Let result be the empty string.
1034 std::string result{};
1035 // Reserve extra space for potential escapes (worst case: all chars escaped)
1036 result.reserve(input.size() * 2);
1037 for (const char c : input) {
1038 if (should_escape_regexp_char(c)) {
1039 // Avoid temporary string allocation - directly append characters
1040 result.push_back('\\');
1041 result.push_back(c);
1042 } else {
1043 result.push_back(c);
1044 }
1045 }
1046 return result;
1047}
1048
1049std::string process_base_url_string(std::string_view input,
1050 url_pattern_init::process_type type) {
1051 // If type is not "pattern" return input.
1052 if (type != url_pattern_init::process_type::pattern) {
1053 return std::string(input);
1054 }
1055 // Return the result of escaping a pattern string given input.
1056 return escape_pattern_string(input);
1057}
1058
1059constexpr bool is_absolute_pathname(
1060 std::string_view input, url_pattern_init::process_type type) noexcept {
1061 // If input is the empty string, then return false.
1062 if (input.empty()) [[unlikely]] {
1063 return false;
1064 }
1065 // If input[0] is U+002F (/), then return true.
1066 if (input.starts_with("/")) return true;
1067 // If type is "url", then return false.
1068 if (type == url_pattern_init::process_type::url) return false;
1069 // If input's code point length is less than 2, then return false.
1070 if (input.size() < 2) return false;
1071 // If input[0] is U+005C (\‍) and input[1] is U+002F (/), then return true.
1072 // If input[0] is U+007B ({) and input[1] is U+002F (/), then return true.
1073 // Return false.
1074 return input[1] == '/' && (input[0] == '\\' || input[0] == '{');
1075}
1076
1077std::string generate_pattern_string(
1078 std::vector<url_pattern_part>& part_list,
1079 url_pattern_compile_component_options& options) {
1080 // Let result be the empty string.
1081 std::string result{};
1082 // Let index list be the result of getting the indices for part list.
1083 // For each index of index list:
1084 for (size_t index = 0; index < part_list.size(); index++) {
1085 // Let part be part list[index].
1086 // Use reference to avoid copy
1087 const auto& part = part_list[index];
1088 // Let previous part be part list[index - 1] if index is greater than 0,
1089 // otherwise let it be null.
1090 // Use pointer to avoid copy
1091 const url_pattern_part* previous_part =
1092 index == 0 ? nullptr : &part_list[index - 1];
1093 // Let next part be part list[index + 1] if index is less than index list's
1094 // size - 1, otherwise let it be null.
1095 const url_pattern_part* next_part =
1096 index < part_list.size() - 1 ? &part_list[index + 1] : nullptr;
1097 // If part's type is "fixed-text" then:
1098 if (part.type == url_pattern_part_type::FIXED_TEXT) {
1099 // If part's modifier is "none" then:
1100 if (part.modifier == url_pattern_part_modifier::none) {
1101 // Append the result of running escape a pattern string given part's
1102 // value to the end of result.
1103 result.append(escape_pattern_string(part.value));
1104 continue;
1105 }
1106 // Append "{" to the end of result.
1107 result += "{";
1108 // Append the result of running escape a pattern string given part's value
1109 // to the end of result.
1110 result.append(escape_pattern_string(part.value));
1111 // Append "}" to the end of result.
1112 result += "}";
1113 // Append the result of running convert a modifier to a string given
1114 // part's modifier to the end of result.
1115 result.append(convert_modifier_to_string(part.modifier));
1116 continue;
1117 }
1118 // Let custom name be true if part's name[0] is not an ASCII digit;
1119 // otherwise false.
1120 bool custom_name = !unicode::is_ascii_digit(part.name[0]);
1121 // Let needs grouping be true if at least one of the following are true,
1122 // otherwise let it be false:
1123 // - part's suffix is not the empty string.
1124 // - part's prefix is not the empty string and is not options's prefix code
1125 // point.
1126 // This compares the whole prefix: a prefix such as "/9" starts with the
1127 // prefix code point but is not it, and still needs grouping.
1128 bool needs_grouping =
1129 !part.suffix.empty() ||
1130 (!part.prefix.empty() && part.prefix != options.get_prefix());
1131
1132 // If all of the following are true:
1133 // - needs grouping is false; and
1134 // - custom name is true; and
1135 // - part's type is "segment-wildcard"; and
1136 // - part's modifier is "none"; and
1137 // - next part is not null; and
1138 // - next part's prefix is the empty string; and
1139 // - next part's suffix is the empty string
1140 if (!needs_grouping && custom_name &&
1141 part.type == url_pattern_part_type::SEGMENT_WILDCARD &&
1142 part.modifier == url_pattern_part_modifier::none && next_part &&
1143 next_part->prefix.empty() && next_part->suffix.empty()) {
1144 // If next part's type is "fixed-text":
1145 if (next_part->type == url_pattern_part_type::FIXED_TEXT) {
1146 // Set needs grouping to true if the result of running is a valid name
1147 // code point given next part's value's first code point and the boolean
1148 // false is true.
1149 if (idna::valid_name_code_point(next_part->value[0], false)) {
1150 needs_grouping = true;
1151 }
1152 } else {
1153 // Set needs grouping to true if next part's name[0] is an ASCII digit.
1154 needs_grouping = !next_part->name.empty() &&
1155 unicode::is_ascii_digit(next_part->name[0]);
1156 }
1157 }
1158
1159 // If all of the following are true:
1160 // - needs grouping is false; and
1161 // - part's prefix is the empty string; and
1162 // - previous part is not null; and
1163 // - previous part's type is "fixed-text"; and
1164 // - previous part's value's last code point is options's prefix code point.
1165 // then set needs grouping to true.
1166 if (!needs_grouping && part.prefix.empty() && previous_part &&
1167 previous_part->type == url_pattern_part_type::FIXED_TEXT &&
1168 !previous_part->value.empty() && !options.get_prefix().empty() &&
1169 previous_part->value.back() == options.get_prefix()[0]) {
1170 needs_grouping = true;
1171 }
1172
1173 // Assert: part's name is not the empty string or null.
1174 ADA_ASSERT_TRUE(!part.name.empty());
1175
1176 // If needs grouping is true, then append "{" to the end of result.
1177 if (needs_grouping) {
1178 result.append("{");
1179 }
1180
1181 // Append the result of running escape a pattern string given part's prefix
1182 // to the end of result.
1183 result.append(escape_pattern_string(part.prefix));
1184
1185 // If custom name is true:
1186 if (custom_name) {
1187 // Append ":" to the end of result.
1188 result.append(":");
1189 // Append part's name to the end of result.
1190 result.append(part.name);
1191 }
1192
1193 // If part's type is "regexp" then:
1194 if (part.type == url_pattern_part_type::REGEXP) {
1195 // Append "(" to the end of result.
1196 result.append("(");
1197 // Append part's value to the end of result.
1198 result.append(part.value);
1199 // Append ")" to the end of result.
1200 result.append(")");
1201 } else if (part.type == url_pattern_part_type::SEGMENT_WILDCARD &&
1202 !custom_name) {
1203 // Otherwise if part's type is "segment-wildcard" and custom name is
1204 // false: Append "(" to the end of result.
1205 result.append("(");
1206 // Append the result of running generate a segment wildcard regexp given
1207 // options to the end of result.
1208 result.append(generate_segment_wildcard_regexp(options));
1209 // Append ")" to the end of result.
1210 result.append(")");
1211 } else if (part.type == url_pattern_part_type::FULL_WILDCARD) {
1212 // Otherwise if part's type is "full-wildcard":
1213 // If custom name is false and one of the following is true:
1214 // - previous part is null; or
1215 // - previous part's type is "fixed-text"; or
1216 // - previous part's modifier is not "none"; or
1217 // - needs grouping is true; or
1218 // - part's prefix is not the empty string
1219 // - then append "*" to the end of result.
1220 if (!custom_name &&
1221 (!previous_part ||
1222 previous_part->type == url_pattern_part_type::FIXED_TEXT ||
1223 previous_part->modifier != url_pattern_part_modifier::none ||
1224 needs_grouping || !part.prefix.empty())) {
1225 result.append("*");
1226 } else {
1227 // Append "(" to the end of result.
1228 // Append full wildcard regexp value to the end of result.
1229 // Append ")" to the end of result.
1230 result.append("(.*)");
1231 }
1232 }
1233
1234 // If all of the following are true:
1235 // - part's type is "segment-wildcard"; and
1236 // - custom name is true; and
1237 // - part's suffix is not the empty string; and
1238 // - The result of running is a valid name code point given part's suffix's
1239 // first code point and the boolean false is true then append U+005C (\‍) to
1240 // the end of result.
1241 if (part.type == url_pattern_part_type::SEGMENT_WILDCARD && custom_name &&
1242 !part.suffix.empty() &&
1243 idna::valid_name_code_point(part.suffix[0], false)) {
1244 result.append("\\");
1245 }
1246
1247 // Append the result of running escape a pattern string given part's suffix
1248 // to the end of result.
1249 result.append(escape_pattern_string(part.suffix));
1250 // If needs grouping is true, then append "}" to the end of result.
1251 if (needs_grouping) result.append("}");
1252 // Append the result of running convert a modifier to a string given part's
1253 // modifier to the end of result.
1254 result.append(convert_modifier_to_string(part.modifier));
1255 }
1256 // Return result.
1257 return result;
1258}
1259} // namespace ada::url_pattern_helpers
1260
1261#endif // ADA_INCLUDE_URL_PATTERN
Declaration of the character sets used by unicode functions.
Declarations for URL specific checkers used within Ada.
#define ADA_ASSERT_TRUE(COND)
Definitions for helper functions used within Ada.
bool constexpr is_ascii(std::u32string_view view)
ada_really_inline size_t percent_encode_index(const std::string_view input, const uint8_t character_set[])
Definition unicode-inl.h:24
errors
Error codes for URL parsing operations.
Definition errors.h:17
template ada::result< url_aggregator > parse< url_aggregator >(std::string_view input, const url_aggregator *base_url)
tl::expected< result_type, ada::errors > result
URL scheme type definitions and utilities.
Definitions for all unicode specific functions.
Declaration for the URLPattern helpers.