Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
implementation.cpp
Go to the documentation of this file.
2
3#include <array>
4#include <atomic>
5#include <cstdint>
6#include <cstring>
7#include <limits>
8#include <optional>
9#include <string>
10#include <string_view>
11
12#include "ada/checkers-inl.h"
13#include "ada/checkers.h"
14#include "ada/common_defs.h"
15#include "ada/parser.h"
16#include "ada/scheme.h"
17#include "ada/unicode-inl.h"
18#include "ada/url.h"
19#include "ada/url_aggregator.h"
20
21namespace ada {
22
23static std::atomic<uint32_t> max_input_length_{
24 std::numeric_limits<uint32_t>::max()};
25
26void set_max_input_length(uint32_t length) {
27 max_input_length_.store(length, std::memory_order_relaxed);
28}
29
31 return max_input_length_.load(std::memory_order_relaxed);
32}
33
34namespace {
35
36constexpr std::array<uint8_t, 256> clean_http_host_byte = []() consteval {
37 std::array<uint8_t, 256> result{};
38 for (size_t i = 0; i < result.size(); ++i) {
39 const auto c = static_cast<uint8_t>(i);
40 result[i] =
41 static_cast<uint8_t>((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') ||
42 c == '-' || c == '.' || c == '_' || c == '~');
43 }
44 return result;
45}();
46
47// SWAR: eight ASCII host bytes in [a-z0-9-._~] without 8 table lookups.
48// High bits must be clear first so the range subtracts cannot borrow
49// across bytes.
50// High-bit-cleared ASCII only. Subtracts cannot borrow across bytes because
51// each (hi|0x80) byte is >= 0x80 and each data byte is <= 0x7F. Do not use
52// has-zero (x-ones)&~x: a match followed by match^1 (e.g. "./" or "_^")
53// produces a false positive via borrow.
54ada_really_inline uint64_t swar_in_range(uint64_t w, uint8_t lo,
55 uint8_t hi) noexcept {
56 constexpr uint64_t k_ones = 0x0101010101010101ull;
57 constexpr uint64_t k_high = 0x8080808080808080ull;
58 const uint64_t ge_lo = (w | k_high) - (k_ones * lo);
59 const uint64_t le_hi = ((k_ones * hi) | k_high) - w;
60 return ge_lo & le_hi & k_high;
61}
62
64 const uint8_t* input) noexcept {
65 uint64_t w = 0;
66 std::memcpy(&w, input, 8);
67 constexpr uint64_t k_high = 0x8080808080808080ull;
68 if ((w & k_high) != 0) {
69 return false;
70 }
71 const uint64_t ok = swar_in_range(w, 'a', 'z') | swar_in_range(w, '0', '9') |
72 swar_in_range(w, '-', '-') | swar_in_range(w, '.', '.') |
73 swar_in_range(w, '_', '_') | swar_in_range(w, '~', '~');
74 return ok == k_high;
75}
76
77// Minimal front end for the overwhelmingly common already-canonical HTTP(S)
78// case. It deliberately handles fewer inputs than
79// try_can_parse_absolute_fast: anything requiring normalization or detailed
80// host parsing falls through to that broader validator.
81#if defined(_MSC_VER) || \
82 (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
83constexpr bool k_can_parse_little_endian = true;
84#else
85constexpr bool k_can_parse_little_endian = false;
86#endif
87
88std::optional<bool> try_can_parse_clean_http(std::string_view input) noexcept {
89 const auto* bytes = reinterpret_cast<const uint8_t*>(input.data());
90 const size_t length = input.size();
91 if (length < 7) {
92 return std::nullopt;
93 }
94
95 size_t authority_start;
96 if constexpr (k_can_parse_little_endian) {
97 if (length >= 8) {
98 uint64_t first8 = 0;
99 std::memcpy(&first8, bytes, 8);
100 if (first8 == 0x2f2f3a7370747468ull) { // "https://"
101 authority_start = 8;
102 } else if ((first8 & 0x00ffffffffffffffull) ==
103 0x002f2f3a70747468ull) { // "http://"
104 authority_start = 7;
105 } else {
106 return std::nullopt;
107 }
108 } else if (bytes[0] == 'h' && bytes[1] == 't' && bytes[2] == 't' &&
109 bytes[3] == 'p' && bytes[4] == ':' && bytes[5] == '/' &&
110 bytes[6] == '/') {
111 authority_start = 7;
112 } else {
113 return std::nullopt;
114 }
115 } else {
116 uint32_t first4{};
117 std::memcpy(&first4, bytes, 4);
118 if (first4 != 0x68747470u) { // "http"
119 return std::nullopt;
120 }
121 if (length >= 8 && bytes[4] == 's' && bytes[5] == ':' && bytes[6] == '/' &&
122 bytes[7] == '/') {
123 authority_start = 8;
124 } else if (bytes[4] == ':' && bytes[5] == '/' && bytes[6] == '/') {
125 authority_start = 7;
126 } else {
127 return std::nullopt;
128 }
129 }
130
131 if (authority_start >= length) {
132 return false;
133 }
134
135 size_t cursor = authority_start;
136 while (cursor + 8 <= length && eight_clean_http_host_bytes(bytes + cursor)) {
137 cursor += 8;
138 }
139 while (cursor < length) {
140 const uint8_t c = bytes[cursor];
141 if (c == '/' || c == '?' || c == '#') {
142 break;
143 }
144 if (!clean_http_host_byte[c]) {
145 return std::nullopt;
146 }
147 ++cursor;
148 }
149
150 const size_t host_length = cursor - authority_start;
151 if (host_length == 0) {
152 // Extra special-scheme slashes are normalization, not an empty host.
153 if (bytes[authority_start] == '/' || bytes[authority_start] == '\\') {
154 return std::nullopt;
155 }
156 return false;
157 }
158 if (host_length > 253 || bytes[cursor - 1] == '.') {
159 return std::nullopt;
160 }
161
162 const std::string_view host(input.data() + authority_start, host_length);
164 return std::nullopt;
165 }
166 if (host.find('x') != std::string_view::npos &&
167 host.find("xn-") != std::string_view::npos) {
168 return std::nullopt;
169 }
170
171 // Once a special URL has a valid host, path/query/fragment bytes cannot make
172 // it structurally invalid: the full parser percent-encodes them as needed.
173 return true;
174}
175
176// @private
177// Fast-path validator for can_parse.
178//
179// Validates absolute special (non-file) URLs without constructing any
180// url_aggregator object and without running the state machine.
181// Performs a single forward scan over the input bytes.
182//
183// Returns:
184// true -- URL is structurally valid
185// false -- URL is definitely invalid
186// nullopt -- edge case; fall through to the full parser
187// (credentials, IDNA, IPv4/6, tabs/newlines, relative URLs, ...)
188std::optional<bool> try_can_parse_absolute_fast(
189 std::string_view input) noexcept {
190 const uint8_t* b = reinterpret_cast<const uint8_t*>(input.data());
191 size_t len = input.size();
192
193 // -- Inline C0 whitespace trim (no allocation) --------------------------
194 // Note: \t (0x09), \n (0x0a), \r (0x0d) are all <= 0x20, so any
195 // leading/trailing tabs or newlines are correctly stripped here, matching
196 // the WHATWG spec's "remove leading/trailing C0 control and space" step.
197 while (len > 0 && b[0] <= 0x20) {
198 b++;
199 len--;
200 }
201 while (len > 0 && b[len - 1] <= 0x20) {
202 len--;
203 }
204 if (len == 0) return false;
205
206 // -- Scheme detection -----------------------------------------------------
207 // Fast path for HTTP and HTTPS (covers ~90%+ of real-world URLs).
208 // Avoids the general scheme loop, buffer copy, and perfect hash lookup.
209 // We know HTTP and HTTPS are special non-file schemes, so no further
210 // scheme_type checks are needed on the fast path -- only `pos` matters.
211 size_t pos;
212
213 if (len >= 7 && (b[0] | 0x20) == 'h' && (b[1] | 0x20) == 't' &&
214 (b[2] | 0x20) == 't' && (b[3] | 0x20) == 'p') {
215 if (b[4] == ':' && b[5] == '/' && b[6] == '/') {
216 pos = 7;
217 goto skip_extra_slashes;
218 }
219 if (len >= 8 && (b[4] | 0x20) == 's' && b[5] == ':' && b[6] == '/' &&
220 b[7] == '/') {
221 pos = 8;
222 goto skip_extra_slashes;
223 }
224 // Fall through: could be "httpe://", tabs in scheme, etc.
225 }
226
227 {
228 // General scheme detection for ws, wss, ftp, and edge cases.
229 if (!checkers::is_alpha(static_cast<char>(b[0]))) return false;
230
231 // Scan for ':' within the first 7 bytes. All special schemes are <= 5
232 // chars ("https"), so any URL whose first ':' is beyond byte 6 is either
233 // non-special or relative -- both require the full parser.
234 size_t colon_pos = 0;
235 for (size_t i = 1;; ++i) {
236 if (i >= 7 || i >= len) return std::nullopt;
237 const char c = static_cast<char>(b[i]);
238 if (c == ':') {
239 colon_pos = i;
240 break;
241 }
242 // Tabs/newlines in the scheme require the full parser to strip them.
243 if (c == '\t' || c == '\n' || c == '\r') return std::nullopt;
244 if (!unicode::is_alnum_plus(c)) return false;
245 }
246
247 // Lowercase scheme bytes inline and classify via the existing perfect
248 // hash.
249 char scheme_buf[6];
250 scheme_buf[0] = static_cast<char>(b[0] | 0x20);
251 for (size_t i = 1; i < colon_pos; ++i)
252 scheme_buf[i] = static_cast<char>(b[i] | 0x20);
253
254 const ada::scheme::type scheme_type =
255 ada::scheme::get_scheme_type({scheme_buf, colon_pos});
256
257 // Only handle special, non-file schemes.
258 if (scheme_type == ada::scheme::NOT_SPECIAL) return std::nullopt;
259 if (scheme_type == ada::scheme::FILE) return std::nullopt;
260
261 // Per WHATWG, special URLs don't require "//": "http:example.com" is valid
262 // (SPECIAL_AUTHORITY_IGNORE_SLASHES just skips leading slashes and
263 // proceeds to AUTHORITY). Defer to the inline fallback for any input
264 // without "://".
265 pos = colon_pos + 1;
266 if (pos + 2 > len || b[pos] != '/' || b[pos + 1] != '/') {
267 return std::nullopt;
268 }
269 pos += 2;
270 }
271
272skip_extra_slashes:
273 // SPECIAL_AUTHORITY_IGNORE_SLASHES: the full parser skips any additional
274 // leading '/' or '\' after the initial "//". Mirror that here so we don't
275 // mis-identify the host as empty when there are extra slashes.
276 while (pos < len && (b[pos] == '/' || b[pos] == '\\')) {
277 ++pos;
278 }
279
280 // Early IPv6 bail-out: if the authority starts with '[', it's an IPv6
281 // literal which requires the full parser. Checking here avoids scanning
282 // the entire bracketed address only to bail out afterward.
283 if (pos < len && b[pos] == '[') return std::nullopt;
284
285 // -- Merged authority + host scan ------------------------------------------
286 // A single forward pass over the authority bytes that simultaneously:
287 // - finds the authority end and port colon
288 // - validates host characters (forbidden domain code points)
289 // - tracks IPv4 indicators (all-decimal-dots, last non-dot char)
290 // - detects xn-- prefixes (IDNA punycode)
291 // - detects tabs/newlines (which require the full parser to strip)
292 // This replaces 4 separate scans over the host bytes.
293 const size_t auth_start = pos;
294 size_t auth_end = pos;
295 size_t port_colon = SIZE_MAX;
296 bool all_dec_dots = true;
297
298 for (; auth_end < len; ++auth_end) {
299 const uint8_t c = b[auth_end];
300
301 // Non-ASCII -> needs IDNA processing -> full parser.
302 if (c >= 0x80) return std::nullopt;
303
304 // Authority delimiters.
305 if (c == '/' || c == '?' || c == '#' || c == '\\') break;
306
307 // Port separator.
308 if (c == ':') {
309 if (port_colon == SIZE_MAX) port_colon = auth_end;
310 continue;
311 }
312
313 // Credentials or percent-encoding -> full parser.
314 if (c == '@' || c == '%') return std::nullopt;
315
316 // Tabs/newlines anywhere in the authority require the full parser to
317 // strip them before validation. Without this, a tab in the port (e.g.
318 // "http://host:8\t0/") would be mis-rejected by port validation.
319 if (c == '\t' || c == '\n' || c == '\r') return std::nullopt;
320
321 // Skip remaining host-specific checks for port bytes. Port digits are
322 // validated separately below, and no forbidden-domain-code-point check
323 // is needed on port characters.
324 if (port_colon != SIZE_MAX) continue;
325
326 // -- Host byte validation (inlined) ------------------------------------
327 // Forbidden domain code points that are not already caught above:
328 // C0 controls and space (0x00-0x20), DEL (0x7F), <, >, [, ], ^, |.
329 // At this stage, the input may still be userinfo or be normalized later
330 // (e.g., percent-encoded), so we do not reject here and defer to the
331 // parser. Characters already caught: >= 0x80 (non-ASCII), '/' '?' '#' '\\'
332 // (delimiters), ':' (port), '@' '%' (bail), '\t' '\n' '\r' (bail).
333 if (c <= 0x20 || c == 0x7F || c == '<' || c == '>' || c == '[' ||
334 c == ']' || c == '^' || c == '|') {
335 return std::nullopt;
336 }
337
338 // Track whether host is all decimal digits and dots (potential IPv4).
339 if (c != '.' && (c < '0' || c > '9')) all_dec_dots = false;
340
341 // Detect xn-- prefix inline (IDNA punycode -> needs full parser).
342 // Checking at every position mirrors the original behavior: any
343 // occurrence of "xn--" in the host (not just at label boundaries)
344 // triggers a bail-out to the full IDNA validator.
345 if ((c | 0x20) == 'x' && auth_end + 4 <= len &&
346 (b[auth_end + 1] | 0x20) == 'n' && b[auth_end + 2] == '-' &&
347 b[auth_end + 3] == '-') {
348 return std::nullopt;
349 }
350 }
351
352 const size_t host_end = (port_colon != SIZE_MAX) ? port_colon : auth_end;
353
354 // Empty host is invalid for special URLs.
355 if (auth_start == host_end) return false;
356
357 // -- IPv4 handling ---------------------------------------------------------
358 const char* host_ptr = reinterpret_cast<const char*>(b + auth_start);
359 const size_t host_len = host_end - auth_start;
360
361 if (all_dec_dots) {
362 // Host is all decimal digits and dots -> try the fast IPv4 parser.
363 if (checkers::try_parse_ipv4_fast({host_ptr, host_len}) !=
365 // Valid decimal IPv4 host. Do NOT return true yet: the port still
366 // needs to be validated below before we can declare the URL valid.
367 goto validate_port;
368 }
369 // Fast IPv4 parsing failed (e.g. host is ".", "..", "1.2.3.500").
370 // Such hosts may still be valid domain names; defer to the full parser.
371 return std::nullopt;
372 }
373
374 if (checkers::last_label_may_be_a_number({host_ptr, host_len})) {
375 return std::nullopt;
376 }
377
378 // -- Port validation -------------------------------------------------------
379validate_port:
380 if (port_colon != SIZE_MAX) {
381 const uint8_t* pp = b + port_colon + 1;
382 size_t pl = auth_end - port_colon - 1;
383 if (pl > 0) {
384 // Strip leading zeros: "0000001" == 1, "0000000000000" == 0, both valid.
385 // Only the significant digits count toward the 5-digit maximum.
386 while (pl > 0 && *pp == '0') {
387 ++pp;
388 --pl;
389 }
390 if (pl > 5) return false; // significant digits > 99999
391 uint32_t pv = 0;
392 for (size_t i = 0; i < pl; ++i) {
393 if (pp[i] < '0' || pp[i] > '9') return false;
394 pv = pv * 10 + (pp[i] - '0');
395 }
396 if (pv > 65535) return false;
397 }
398 }
399
400 // Path, query, and fragment are structurally always valid for can_parse --
401 // the parser would encode whatever is there.
402 return true;
403}
404
405} // namespace
406
407template <class result_type>
408ada_warn_unused tl::expected<result_type, errors> parse(
409 std::string_view input, const result_type* base_url) {
410 result_type u = ada::parser::parse_url_impl<result_type>(input, base_url);
411 if (!u.is_valid) {
412 return tl::unexpected(errors::type_error);
413 }
414 return u;
415}
416
417template ada::result<url> parse<url>(std::string_view input,
418 const url* base_url = nullptr);
420 std::string_view input, const url_aggregator* base_url = nullptr);
421
422std::string href_from_file(std::string_view input) {
423 // Match ada::parse / setters: refuse inputs that already exceed the limit.
424 // Path percent-encoding can still expand the result, so we also check the
425 // final href below.
426 const uint32_t max_length = ada::get_max_input_length();
427 if (input.size() > max_length) {
428 return {};
429 }
430
431 // This is going to be much faster than constructing a URL.
432 std::string tmp_buffer;
433 std::string_view internal_input;
434 if (unicode::has_tabs_or_newline(input)) {
435 tmp_buffer = input;
436 helpers::remove_ascii_tab_or_newline(tmp_buffer);
437 internal_input = tmp_buffer;
438 } else {
439 internal_input = input;
440 }
441 std::string path;
442 if (internal_input.empty()) {
443 path = "/";
444 } else if ((internal_input[0] == '/') || (internal_input[0] == '\\')) {
445 helpers::parse_prepared_path(internal_input.substr(1),
447 } else {
448 helpers::parse_prepared_path(internal_input, ada::scheme::type::FILE, path);
449 }
450 std::string result = "file://" + path;
451 if (result.size() > max_length) {
452 return {};
453 }
454 return result;
455}
456
457bool can_parse(std::string_view input, const std::string_view* base_input) {
458 // Must match parse().has_value(), including post-normalization max length.
459 // Percent-encoding expands a byte by at most 3x, but IDNA expands more: a
460 // 3-byte UTF-8 label such as U+337F becomes the 17-byte "xn--6oqv20b1zgzxr",
461 // so a dotted host sustains 4.5x. When the input (plus base, if any) fits in
462 // max_length/5, the normalized href cannot exceed max_length, so
463 // validation-only parsing (store_values=false) is safe.
464
465 // Hot path first: absolute special URLs, no base. Avoid loading max_length
466 // until we need it (common absolute-fast true/false cases).
467 if (base_input == nullptr) {
468 auto r = try_can_parse_clean_http(input);
469 if (!r.has_value()) {
470 r = try_can_parse_absolute_fast(input);
471 }
472 if (r.has_value()) {
473 if (!*r) {
474 return false;
475 }
476 // size <= max/5 => normalized href cannot exceed max (4.5x expansion).
477 // Check this first: default max is ~4GB so almost all URLs return true.
478 const uint32_t max_length = ada::get_max_input_length();
479 if (input.size() <= static_cast<size_t>(max_length) / 5) {
480 return true;
481 }
482 if (input.size() > max_length) {
483 return false;
484 }
486 nullptr)
487 .is_valid;
488 }
489 }
490
491 const uint32_t max_length = ada::get_max_input_length();
492 if (input.size() > max_length) {
493 return false;
494 }
495 if (base_input != nullptr && base_input->size() > max_length) {
496 return false;
497 }
498
499 // Relative resolution combines base + input; bound the sum so 4.5x expansion
500 // of either side cannot push the final href past max_length.
501 const size_t combined =
502 input.size() + (base_input == nullptr ? 0 : base_input->size());
503 const bool size_safe = combined <= static_cast<size_t>(max_length) / 5;
504
505 if (size_safe) {
506 // Validation-only: no buffer build, host still fully checked.
507 ada::url_aggregator base_agg;
508 ada::url_aggregator* base_ptr = nullptr;
509 if (base_input != nullptr) {
511 *base_input, nullptr);
512 if (!base_agg.is_valid) {
513 return false;
514 }
515 base_ptr = &base_agg;
516 }
518 base_ptr)
519 .is_valid;
520 }
521
522 // Near the limit: full parse so post-normalization length matches parse().
523 if (base_input == nullptr) {
525 nullptr)
526 .is_valid;
527 }
528 ada::url_aggregator base_agg =
530 nullptr);
531 if (!base_agg.is_valid) {
532 return false;
533 }
535 &base_agg)
536 .is_valid;
537}
538
540 switch (type) {
542 return "UTF-8";
544 return "UTF-16LE";
546 return "UTF-16BE";
547 default:
548 unreachable();
549 }
550}
551
552} // namespace ada
Definitions for URL specific checkers used within Ada.
Declarations for URL specific checkers used within Ada.
Cross-platform compiler macros and common definitions.
#define ada_warn_unused
Definition common_defs.h:89
#define ada_really_inline
Definition common_defs.h:85
constexpr std::array< uint8_t, 256 > clean_http_host_byte
std::optional< bool > try_can_parse_clean_http(std::string_view input) noexcept
ada_really_inline uint64_t swar_in_range(uint64_t w, uint8_t lo, uint8_t hi) noexcept
ada_really_inline bool eight_clean_http_host_bytes(const uint8_t *input) noexcept
std::optional< bool > try_can_parse_absolute_fast(std::string_view input) noexcept
constexpr bool last_label_may_be_a_number(std::string_view view) noexcept
constexpr uint64_t ipv4_fast_fail
Definition checkers.h:128
ada_really_inline uint64_t try_parse_ipv4_fast(std::string_view input) noexcept
constexpr bool is_alpha(char x) noexcept
result_type parse_url_impl(std::string_view user_input, const result_type *base_url=nullptr)
Definition parser.cpp:1841
constexpr ada::scheme::type get_scheme_type(std::string_view scheme) noexcept
Definition scheme-inl.h:111
type
Enumeration of URL scheme types.
Definition scheme.h:43
@ NOT_SPECIAL
Definition scheme.h:45
bool can_parse(std::string_view input, const std::string_view *base_input=nullptr)
template ada::result< url > parse< url >(std::string_view input, const url *base_url)
void set_max_input_length(uint32_t length)
static std::atomic< uint32_t > max_input_length_
std::string href_from_file(std::string_view path)
@ type_error
Definition errors.h:18
template ada::result< url_aggregator > parse< url_aggregator >(std::string_view input, const url_aggregator *base_url)
encoding_type
Character encoding types for URL processing.
ada_warn_unused std::string_view to_string(encoding_type type)
uint32_t get_max_input_length()
void unreachable()
tl::expected< result_type, ada::errors > result
ada_warn_unused ada::result< result_type > parse(std::string_view input, const result_type *base_url=nullptr)
Low-level URL parsing functions.
URL scheme type definitions and utilities.
Memory-efficient URL representation using a single buffer.
bool is_valid
Definition url_base.h:58
Definitions for unicode operations.
Declaration for the ada::url class.
Declaration for the ada::url_aggregator class.