Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
parser.cpp
Go to the documentation of this file.
1#include "ada/parser-inl.h"
2
3#include <array>
4#include <bit>
5#include <charconv>
6#include <cstdint>
7#include <cstring>
8#include <limits>
9#include <optional>
10#include <ranges>
11#include <string>
12#include <string_view>
13#include <utility>
14
16#include "ada/checkers-inl.h"
17#include "ada/common_defs.h"
18#include "ada/implementation.h"
19#include "ada/log.h"
20#include "ada/scheme-inl.h"
21#include "ada/unicode-inl.h"
22#include "ada/unicode.h"
23#include "ada/url.h"
24#include "ada/url_aggregator.h"
26
27#if ADA_NEON
28#include <arm_neon.h>
29#elif defined(__SSSE3__)
30#include <tmmintrin.h>
31#define ADA_PARSER_SSSE3 1
32#elif (defined(__x86_64__) || defined(__amd64__)) && defined(__GNUC__) && \
33 !defined(_MSC_VER)
34// gcc/clang honor target("ssse3"). clang-cl and MSVC do not: they still
35// compile the function as SSE2, then reject always_inline _mm_shuffle_epi8.
36#include <tmmintrin.h>
37#define ADA_PARSER_SSSE3 1
38#define ADA_PARSER_NEED_SSSE3_TARGET 1
39#elif ADA_SSE2
40#include <emmintrin.h>
41#endif
42#ifndef ADA_PARSER_SSSE3
43#define ADA_PARSER_SSSE3 0
44#endif
45
46#ifdef ADA_PARSER_NEED_SSSE3_TARGET
47// Scan loops stay on the default ISA (SSE2 for generic x86-64). pshufb lives
48// in a noinline SSSE3 function so the CPU check is not inside a function the
49// compiler is free to compile entirely with SSSE3 instructions.
50#define ADA_PARSER_SIMD ada_really_inline
51#define ADA_PARSER_SSSE3_FN __attribute__((target("ssse3"), noinline))
52#else
53#define ADA_PARSER_SIMD ada_really_inline
54#define ADA_PARSER_SSSE3_FN ada_really_inline
55#endif
56
57#ifdef ADA_REGULAR_VISUAL_STUDIO
58#include <intrin.h>
59#endif
60
61namespace ada::parser {
62
63// Classification tables and 16-byte run scanners for the absolute-URL fast
64// path. Inspired by oven-sh/WebKit#452 and #454: scan 16 bytes at a time
65// (nibble-table pshufb/tbl when SSSE3 or NEON is available), and when the
66// path/query/fragment is not already canonical, keep the parsed host and
67// finish with the existing path helpers instead of re-parsing from scratch.
68namespace {
69
70// 0 = host byte, 1 = host delimiter (/ ? # :), 2 = reject
71constexpr std::array<uint8_t, 256> k_host_class = []() consteval {
72 std::array<uint8_t, 256> t{};
73 for (size_t i = 0; i < 256; ++i) {
74 t[i] = 2;
75 }
76 for (size_t i = 0x21; i <= 0x7E; ++i) {
77 t[i] = 0;
78 }
79 for (uint8_t c :
80 {'#', '/', ':', '<', '>', '?', '@', '[', '\\', ']', '^', '|', '%'}) {
81 t[c] = 2;
82 }
83 t[static_cast<uint8_t>('/')] = 1;
84 t[static_cast<uint8_t>('?')] = 1;
85 t[static_cast<uint8_t>('#')] = 1;
86 t[static_cast<uint8_t>(':')] = 1;
87 return t;
88}();
89
90// Path: 0 = copy, 1 = ?/#, 2 = needs work. Apostrophe is copyable in a path.
91constexpr std::array<uint8_t, 256> k_path = []() consteval {
92 std::array<uint8_t, 256> t{};
93 for (size_t i = 0; i < 256; ++i) {
94 t[i] = 2;
95 }
96 for (uint8_t c = 0x21; c <= 0x7E; ++c) {
97 t[c] = 0;
98 }
99 for (uint8_t c : {static_cast<uint8_t>('"'), static_cast<uint8_t>('<'),
100 static_cast<uint8_t>('>'), static_cast<uint8_t>('`'),
101 static_cast<uint8_t>('{'), static_cast<uint8_t>('}'),
102 static_cast<uint8_t>('^'), static_cast<uint8_t>('\\'),
103 static_cast<uint8_t>('%')}) {
104 t[c] = 2;
105 }
106 t[static_cast<uint8_t>('?')] = 1;
107 t[static_cast<uint8_t>('#')] = 1;
108 return t;
109}();
110
111// Special-query: 0 = copy, 1 = #, 2 = needs work. Apostrophe must be encoded.
112constexpr std::array<uint8_t, 256> k_query = []() consteval {
113 std::array<uint8_t, 256> t{};
114 for (size_t i = 0; i < 256; ++i) {
115 t[i] = 2;
116 }
117 for (uint8_t c = 0x21; c <= 0x7E; ++c) {
118 t[c] = 0;
119 }
120 for (uint8_t c : {static_cast<uint8_t>('"'), static_cast<uint8_t>('<'),
121 static_cast<uint8_t>('>'), static_cast<uint8_t>('\'')}) {
122 t[c] = 2;
123 }
124 t[static_cast<uint8_t>('#')] = 1;
125 return t;
126}();
127
128// Fragment: 0 = copy, 2 = needs work. '?' '#' '%' are copyable.
129constexpr std::array<uint8_t, 256> k_hash = []() consteval {
130 std::array<uint8_t, 256> t{};
131 for (size_t i = 0; i < 256; ++i) {
132 t[i] = 2;
133 }
134 for (uint8_t c = 0x21; c <= 0x7E; ++c) {
135 t[c] = 0;
136 }
137 for (uint8_t c : {static_cast<uint8_t>('"'), static_cast<uint8_t>('<'),
138 static_cast<uint8_t>('>'), static_cast<uint8_t>('`')}) {
139 t[c] = 2;
140 }
141 return t;
142}();
143
144// Nibble tables for pshufb / tbl classification (oven-sh/WebKit#454).
145// A byte is a stop when low[b & 0xF] & high[b >> 4] != 0. High nibbles whose
146// sixteen bytes share a stop pattern share a bit, so any set with at most
147// eight distinct patterns fits. Tables are built from the scalar class
148// arrays, so the vector and scalar paths cannot disagree.
150 alignas(16) uint8_t low[16]{};
151 alignas(16) uint8_t high[16]{};
152 bool fits{true};
153};
154
156 const std::array<uint8_t, 256>& cls) {
157 nibble_tables t{};
158 uint16_t patterns[16]{};
159 for (int hi = 0; hi < 16; ++hi) {
160 for (int lo = 0; lo < 16; ++lo) {
161 if (cls[static_cast<size_t>((hi << 4) | lo)] != 0) {
162 patterns[hi] = static_cast<uint16_t>(patterns[hi] | (1u << lo));
163 }
164 }
165 }
166 int bits_used = 0;
167 for (int hi = 0; hi < 16; ++hi) {
168 if (patterns[hi] == 0 || t.high[hi] != 0) {
169 continue;
170 }
171 if (bits_used == 8) {
172 t.fits = false;
173 return t;
174 }
175 const uint8_t bit = static_cast<uint8_t>(1u << bits_used++);
176 for (int other = hi; other < 16; ++other) {
177 if (patterns[other] == patterns[hi]) {
178 t.high[other] = static_cast<uint8_t>(t.high[other] | bit);
179 }
180 }
181 for (int lo = 0; lo < 16; ++lo) {
182 if ((patterns[hi] & (1u << lo)) != 0) {
183 t.low[lo] = static_cast<uint8_t>(t.low[lo] | bit);
184 }
185 }
186 }
187 return t;
188}
189
194static_assert(k_host_nibbles.fits);
195static_assert(k_path_nibbles.fits);
196static_assert(k_query_nibbles.fits);
197static_assert(k_hash_nibbles.fits);
198
199// WHATWG serializes a port as its decimal value with no leading zeros.
200ada_really_inline uint32_t port_decimal_digit_count(uint32_t port) noexcept {
201 uint32_t digits = 1;
202 while (port >= 10) {
203 port /= 10;
204 ++digits;
205 }
206 return digits;
207}
208
210 uint32_t port) {
211 buffer += ':';
212 char port_buf[5];
213 auto [ptr, ec] = std::to_chars(port_buf, port_buf + 5, port);
214 (void)ec;
215 buffer.append(port_buf, static_cast<size_t>(ptr - port_buf));
216}
217
218ada_really_inline int trailing_zeroes32(uint32_t input_num) noexcept {
219#ifdef ADA_REGULAR_VISUAL_STUDIO
220 unsigned long ret;
221 _BitScanForward(&ret, input_num);
222 return static_cast<int>(ret);
223#else
224 return __builtin_ctz(input_num);
225#endif
226}
227
228ada_really_inline int trailing_zeroes64(uint64_t input_num) noexcept {
229#ifdef ADA_REGULAR_VISUAL_STUDIO
230 unsigned long ret;
231 _BitScanForward64(&ret, input_num);
232 return static_cast<int>(ret);
233#else
234 return __builtin_ctzll(input_num);
235#endif
236}
237
238#if ADA_PARSER_SSSE3
239ADA_PARSER_SIMD __m128i nibble_load(const uint8_t* t) noexcept {
240 return _mm_load_si128(reinterpret_cast<const __m128i*>(t));
241}
242
243// Non-zero lanes are stops. Tables are passed in so the scan loops can hoist
244// the loads out of the 16-byte iteration.
245ADA_PARSER_SSSE3_FN int ssse3_nibble_mask(__m128i w, __m128i lo_tbl,
246 __m128i hi_tbl) noexcept {
247 const __m128i nibble = _mm_set1_epi8(0x0F);
248 const __m128i lo = _mm_and_si128(w, nibble);
249 const __m128i hi = _mm_and_si128(_mm_srli_epi16(w, 4), nibble);
250 const __m128i hit =
251 _mm_and_si128(_mm_shuffle_epi8(lo_tbl, lo), _mm_shuffle_epi8(hi_tbl, hi));
252 return _mm_movemask_epi8(_mm_cmpeq_epi8(hit, _mm_setzero_si128())) ^ 0xFFFF;
253}
254#endif // ADA_PARSER_SSSE3
255
256#if ADA_SSE2
257#if !ADA_PARSER_SSSE3
258// Signed < 0x21 matches 0x00-0x20 and 0x80-0xFF; 0x7F is checked separately.
259ada_really_inline __m128i sse2_ctrl_or_nonascii(__m128i w) noexcept {
260 return _mm_or_si128(_mm_cmplt_epi8(w, _mm_set1_epi8(0x21)),
261 _mm_cmpeq_epi8(w, _mm_set1_epi8(0x7F)));
262}
263
264ada_really_inline int sse2_host_stop(__m128i w) noexcept {
265 const __m128i ctrl = sse2_ctrl_or_nonascii(w);
266 const __m128i is_upper = _mm_and_si128(
267 _mm_cmpgt_epi8(w, _mm_set1_epi8(static_cast<char>('A' - 1))),
268 _mm_cmplt_epi8(w, _mm_set1_epi8(static_cast<char>('Z' + 1))));
269 const __m128i at = _mm_sub_epi8(w, _mm_set1_epi8('@'));
270 const __m128i at_through_caret =
271 _mm_cmpeq_epi8(_mm_min_epu8(at, _mm_set1_epi8('^' - '@')), at);
272 const __m128i at_not_upper = _mm_andnot_si128(is_upper, at_through_caret);
273 const __m128i spec = _mm_or_si128(
274 _mm_or_si128(_mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('#')),
275 _mm_cmpeq_epi8(w, _mm_set1_epi8('%'))),
276 _mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('/')),
277 _mm_cmpeq_epi8(w, _mm_set1_epi8(':')))),
278 _mm_or_si128(_mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('<')),
279 _mm_cmpeq_epi8(w, _mm_set1_epi8('>'))),
280 _mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('?')),
281 _mm_cmpeq_epi8(w, _mm_set1_epi8('|')))));
282 return _mm_movemask_epi8(
283 _mm_or_si128(_mm_or_si128(ctrl, at_not_upper), spec));
284}
285
286ada_really_inline int sse2_path_stop(__m128i w) noexcept {
287 const __m128i ctrl = sse2_ctrl_or_nonascii(w);
288 const __m128i spec = _mm_or_si128(
289 _mm_or_si128(_mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('"')),
290 _mm_cmpeq_epi8(w, _mm_set1_epi8('#'))),
291 _mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('%')),
292 _mm_cmpeq_epi8(w, _mm_set1_epi8('<')))),
293 _mm_or_si128(
294 _mm_or_si128(_mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('>')),
295 _mm_cmpeq_epi8(w, _mm_set1_epi8('?'))),
296 _mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('\\')),
297 _mm_cmpeq_epi8(w, _mm_set1_epi8('^')))),
298 _mm_or_si128(_mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('`')),
299 _mm_cmpeq_epi8(w, _mm_set1_epi8('{'))),
300 _mm_cmpeq_epi8(w, _mm_set1_epi8('}')))));
301 return _mm_movemask_epi8(_mm_or_si128(ctrl, spec));
302}
303
304ada_really_inline int sse2_query_stop(__m128i w) noexcept {
305 const __m128i ctrl = sse2_ctrl_or_nonascii(w);
306 const __m128i spec = _mm_or_si128(
307 _mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('"')),
308 _mm_cmpeq_epi8(w, _mm_set1_epi8('#'))),
309 _mm_or_si128(_mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('<')),
310 _mm_cmpeq_epi8(w, _mm_set1_epi8('>'))),
311 _mm_cmpeq_epi8(w, _mm_set1_epi8('\''))));
312 return _mm_movemask_epi8(_mm_or_si128(ctrl, spec));
313}
314
315ada_really_inline int sse2_hash_stop(__m128i w) noexcept {
316 const __m128i ctrl = sse2_ctrl_or_nonascii(w);
317 const __m128i spec =
318 _mm_or_si128(_mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('"')),
319 _mm_cmpeq_epi8(w, _mm_set1_epi8('<'))),
320 _mm_or_si128(_mm_cmpeq_epi8(w, _mm_set1_epi8('>')),
321 _mm_cmpeq_epi8(w, _mm_set1_epi8('`'))));
322 return _mm_movemask_epi8(_mm_or_si128(ctrl, spec));
323}
324#endif // !ADA_PARSER_SSSE3
325
326ada_really_inline int sse2_uppercase(__m128i w) noexcept {
327 return _mm_movemask_epi8(_mm_and_si128(
328 _mm_cmpgt_epi8(w, _mm_set1_epi8(static_cast<char>('A' - 1))),
329 _mm_cmplt_epi8(w, _mm_set1_epi8(static_cast<char>('Z' + 1)))));
330}
331#endif // ADA_SSE2
332
333#if ADA_NEON
334ada_really_inline uint64_t neon_nibble_bits(uint8x16_t matches) noexcept {
335 const uint8x8_t nib = vshrn_n_u16(vreinterpretq_u16_u8(matches), 4);
336 return vget_lane_u64(vreinterpret_u64_u8(nib), 0);
337}
338
339ada_really_inline uint64_t neon_table_stop(uint8x16_t w, uint8x16_t lo_tbl,
340 uint8x16_t hi_tbl) noexcept {
341 const uint8x16_t hit =
342 vandq_u8(vqtbl1q_u8(lo_tbl, vandq_u8(w, vdupq_n_u8(0x0F))),
343 vqtbl1q_u8(hi_tbl, vshrq_n_u8(w, 4)));
344 return neon_nibble_bits(vtstq_u8(hit, hit));
345}
346
347ada_really_inline uint64_t neon_uppercase(uint8x16_t w) noexcept {
348 return neon_nibble_bits(
349 vandq_u8(vcgeq_u8(w, vdupq_n_u8('A')), vcleq_u8(w, vdupq_n_u8('Z'))));
350}
351#endif // ADA_NEON
352
353// True when '@' appears in the authority before '/', '?', or '#'.
354// One 16-byte window covers typical userinfo (SetHref's "user:pass@").
355// Longer userinfo still misses inside the never_inline fast path. No
356// '@' is a single load + compare so the parse hot path stays cheap.
357ada_really_inline bool authority_has_at(const uint8_t* p, size_t host_start,
358 size_t n) noexcept {
359 const size_t rem = n - host_start;
360 if (rem == 0) {
361 return false;
362 }
363#if ADA_NEON
364 if (rem >= 16) {
365 const uint8x16_t w = vld1q_u8(p + host_start);
366 const uint64_t at = neon_nibble_bits(vceqq_u8(w, vdupq_n_u8('@')));
367 if (at == 0) {
368 return false;
369 }
370 const uint64_t delim = neon_nibble_bits(vceqq_u8(w, vdupq_n_u8('/'))) |
371 neon_nibble_bits(vceqq_u8(w, vdupq_n_u8('?'))) |
372 neon_nibble_bits(vceqq_u8(w, vdupq_n_u8('#')));
373 return delim == 0 || std::countr_zero(at) < std::countr_zero(delim);
374 }
375#elif ADA_SSE2
376 if (rem >= 16) {
377 const __m128i w =
378 _mm_loadu_si128(reinterpret_cast<const __m128i*>(p + host_start));
379 const uint16_t at = static_cast<uint16_t>(
380 _mm_movemask_epi8(_mm_cmpeq_epi8(w, _mm_set1_epi8('@'))));
381 if (at == 0) {
382 return false;
383 }
384 const uint16_t delim = static_cast<uint16_t>(
385 _mm_movemask_epi8(_mm_cmpeq_epi8(w, _mm_set1_epi8('/'))) |
386 _mm_movemask_epi8(_mm_cmpeq_epi8(w, _mm_set1_epi8('?'))) |
387 _mm_movemask_epi8(_mm_cmpeq_epi8(w, _mm_set1_epi8('#'))));
388 return delim == 0 || std::countr_zero(at) < std::countr_zero(delim);
389 }
390#endif
391 const size_t lim = host_start + rem;
392 for (size_t i = host_start; i < lim; ++i) {
393 const uint8_t c = p[i];
394 if (c == '@') {
395 return true;
396 }
397 if (c == '/' || c == '?' || c == '#') {
398 return false;
399 }
400 }
401 return false;
402}
403
404#if ADA_PARSER_SSSE3
405// True when this process can execute the SSSE3 scanners. When the binary was
406// built for SSSE3, the check is a constant. Otherwise it is cached from the
407// CPU and the scanners fall back to the scalar loops below.
408ada_really_inline bool parser_use_ssse3() noexcept {
409#ifdef ADA_PARSER_NEED_SSSE3_TARGET
410 static const bool supported = __builtin_cpu_supports("ssse3") != 0;
411 return supported;
412#else
413 return true;
414#endif
415}
416#endif
417
418// Returns false if a forbidden host code point is found. On success, *end is
419// the first / ? # or len. has_upper / has_x only count host bytes, not the
420// path/query bytes that may sit in the same SIMD window after the delimiter.
421ADA_PARSER_SIMD bool scan_plain_host(const uint8_t* b, size_t start, size_t len,
422 size_t& end, bool& has_upper,
423 bool& has_x) noexcept {
424 has_upper = false;
425 has_x = false;
426 size_t i = start;
427#if ADA_PARSER_SSSE3
428 if (parser_use_ssse3() && (len - start >= 16)) {
429 const __m128i lo_tbl = nibble_load(k_host_nibbles.low);
430 const __m128i hi_tbl = nibble_load(k_host_nibbles.high);
431 const __m128i x_splat = _mm_set1_epi8('x');
432 auto visit = [&](size_t at) noexcept -> bool {
433 const __m128i w =
434 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + at));
435 const int up = sse2_uppercase(w);
436 const int xs = _mm_movemask_epi8(_mm_cmpeq_epi8(w, x_splat));
437 const int mask = ssse3_nibble_mask(w, lo_tbl, hi_tbl);
438 if (mask == 0) {
439 if (up != 0) {
440 has_upper = true;
441 }
442 if (xs != 0) {
443 has_x = true;
444 }
445 return false;
446 }
447 const int hit = trailing_zeroes32(static_cast<uint32_t>(mask));
448 const int valid = (1 << hit) - 1;
449 if ((up & valid) != 0) {
450 has_upper = true;
451 }
452 if ((xs & valid) != 0) {
453 has_x = true;
454 }
455 end = at + static_cast<size_t>(hit);
456 return true;
457 };
458 for (; i + 32 <= len; i += 32) {
459 if (visit(i) || visit(i + 16)) {
460 return k_host_class[b[end]] == 1;
461 }
462 }
463 for (; i + 16 <= len; i += 16) {
464 if (visit(i)) {
465 return k_host_class[b[end]] == 1;
466 }
467 }
468 // Overlapping tail only after a full 16-byte step so the window cannot
469 // start before `start` (a prior '/' would otherwise look like a host stop).
470 if (i > start && i < len) {
471 if (visit(len - 16) && end >= i) {
472 return k_host_class[b[end]] == 1;
473 }
474 end = len;
475 return true;
476 }
477 }
478#elif ADA_SSE2
479 const __m128i x_splat = _mm_set1_epi8('x');
480 for (; i + 32 <= len; i += 32) {
481 for (size_t off = 0; off < 32; off += 16) {
482 const __m128i w =
483 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i + off));
484 const int up = sse2_uppercase(w);
485 const int xs = _mm_movemask_epi8(_mm_cmpeq_epi8(w, x_splat));
486 const int mask = sse2_host_stop(w);
487 if (mask != 0) {
488 const int hit = trailing_zeroes32(static_cast<uint32_t>(mask));
489 const int valid = (1 << hit) - 1;
490 if ((up & valid) != 0) {
491 has_upper = true;
492 }
493 if ((xs & valid) != 0) {
494 has_x = true;
495 }
496 end = i + off + static_cast<size_t>(hit);
497 return k_host_class[b[end]] == 1;
498 }
499 if (up != 0) {
500 has_upper = true;
501 }
502 if (xs != 0) {
503 has_x = true;
504 }
505 }
506 }
507 for (; i + 16 <= len; i += 16) {
508 const __m128i w = _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i));
509 const int up = sse2_uppercase(w);
510 const int xs = _mm_movemask_epi8(_mm_cmpeq_epi8(w, x_splat));
511 const int mask = sse2_host_stop(w);
512 if (mask != 0) {
513 const int hit = trailing_zeroes32(static_cast<uint32_t>(mask));
514 const int valid = (1 << hit) - 1;
515 if ((up & valid) != 0) {
516 has_upper = true;
517 }
518 if ((xs & valid) != 0) {
519 has_x = true;
520 }
521 end = i + static_cast<size_t>(hit);
522 return k_host_class[b[end]] == 1;
523 }
524 if (up != 0) {
525 has_upper = true;
526 }
527 if (xs != 0) {
528 has_x = true;
529 }
530 }
531#elif ADA_NEON
532 if (len - start >= 16) {
533 const uint8x16_t lo_tbl = vld1q_u8(k_host_nibbles.low);
534 const uint8x16_t hi_tbl = vld1q_u8(k_host_nibbles.high);
535 const uint8x16_t x_splat = vdupq_n_u8('x');
536 auto visit = [&](size_t at) noexcept -> bool {
537 const uint8x16_t w = vld1q_u8(b + at);
538 const uint64_t up = neon_uppercase(w);
539 const uint64_t xs = neon_nibble_bits(vceqq_u8(w, x_splat));
540 const uint64_t bits = neon_table_stop(w, lo_tbl, hi_tbl);
541 if (bits == 0) {
542 if (up != 0) {
543 has_upper = true;
544 }
545 if (xs != 0) {
546 has_x = true;
547 }
548 return false;
549 }
550 const size_t hit = static_cast<size_t>(trailing_zeroes64(bits)) >> 2;
551 const uint64_t valid = (hit == 0) ? 0 : (uint64_t{1} << (hit * 4)) - 1;
552 if ((up & valid) != 0) {
553 has_upper = true;
554 }
555 if ((xs & valid) != 0) {
556 has_x = true;
557 }
558 end = at + hit;
559 return true;
560 };
561 for (; i + 32 <= len; i += 32) {
562 if (visit(i) || visit(i + 16)) {
563 return k_host_class[b[end]] == 1;
564 }
565 }
566 for (; i + 16 <= len; i += 16) {
567 if (visit(i)) {
568 return k_host_class[b[end]] == 1;
569 }
570 }
571 if (i > start && i < len) {
572 if (visit(len - 16) && end >= i) {
573 return k_host_class[b[end]] == 1;
574 }
575 end = len;
576 return true;
577 }
578 }
579#endif
580 for (; i < len; ++i) {
581 const uint8_t c = b[i];
582 const uint8_t cls = k_host_class[c];
583 if (cls == 1) {
584 end = i;
585 return true;
586 }
587 if (cls == 2) {
588 return false;
589 }
590 if (c >= 'A' && c <= 'Z') {
591 has_upper = true;
592 } else if (c == 'x') {
593 has_x = true;
594 }
595 }
596 end = len;
597 return true;
598}
599
601 const uint8_t* b, size_t pos, size_t run_start,
602 bool& maybe_dot_segment) noexcept {
603 if (pos == run_start || b[pos - 1] == '/') {
604 maybe_dot_segment = true;
605 }
606}
607
608#if ADA_PARSER_SSSE3 || ADA_SSE2
609// valid_mask selects bytes in this 16-byte window that belong to the path
610// (bits after a stop are cleared). A '.' starts a possible dot-segment when
611// it is the first path byte or immediately follows '/'.
612ada_really_inline void note_dots_in_window(const uint8_t* b, size_t i,
613 size_t run_start, __m128i w,
614 int valid_mask,
615 bool& maybe_dot_segment) noexcept {
616 if (maybe_dot_segment || valid_mask == 0) {
617 return;
618 }
619 const int dots =
620 _mm_movemask_epi8(_mm_cmpeq_epi8(w, _mm_set1_epi8('.'))) & valid_mask;
621 if (dots == 0) {
622 return;
623 }
624 const int slashes =
625 _mm_movemask_epi8(_mm_cmpeq_epi8(w, _mm_set1_epi8('/'))) & valid_mask;
626 if (((dots & 1) != 0 && (i == run_start || b[i - 1] == '/')) ||
627 (dots & (slashes << 1)) != 0) {
628 maybe_dot_segment = true;
629 }
630}
631#endif
632
633#if ADA_NEON
634// Each NEON match nibble occupies 4 bits, so a '.' immediately after '/' is
635// (slashes << 4) rather than (slashes << 1).
636ada_really_inline void note_dots_in_window_neon(
637 const uint8_t* b, size_t i, size_t run_start, uint8x16_t w,
638 uint64_t valid_bits, bool& maybe_dot_segment) noexcept {
639 if (maybe_dot_segment || valid_bits == 0) {
640 return;
641 }
642 const uint64_t dots =
643 neon_nibble_bits(vceqq_u8(w, vdupq_n_u8('.'))) & valid_bits;
644 if (dots == 0) {
645 return;
646 }
647 const uint64_t slashes =
648 neon_nibble_bits(vceqq_u8(w, vdupq_n_u8('/'))) & valid_bits;
649 if (((dots & 0xF) != 0 && (i == run_start || b[i - 1] == '/')) ||
650 (dots & (slashes << 4)) != 0) {
651 maybe_dot_segment = true;
652 }
653}
654#endif
655
656// Advance i to the first path-class 1 or 2 character (or len).
657ADA_PARSER_SIMD void scan_path_run(const uint8_t* b, size_t& i, size_t len,
658 bool& maybe_dot_segment) noexcept {
659 const size_t run_start = i;
660#if ADA_PARSER_SSSE3
661 if (parser_use_ssse3() && (i + 16 <= len)) {
662 const __m128i lo_tbl = nibble_load(k_path_nibbles.low);
663 const __m128i hi_tbl = nibble_load(k_path_nibbles.high);
664 for (; i + 32 <= len; i += 32) {
665 const __m128i w0 =
666 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i));
667 const int m0 = ssse3_nibble_mask(w0, lo_tbl, hi_tbl);
668 if (m0 != 0) {
669 const int hit_bit = trailing_zeroes32(static_cast<uint32_t>(m0));
670 note_dots_in_window(b, i, run_start, w0, (1 << hit_bit) - 1,
671 maybe_dot_segment);
672 i += static_cast<size_t>(hit_bit);
673 return;
674 }
675 note_dots_in_window(b, i, run_start, w0, 0xFFFF, maybe_dot_segment);
676 const __m128i w1 =
677 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i + 16));
678 const int m1 = ssse3_nibble_mask(w1, lo_tbl, hi_tbl);
679 if (m1 != 0) {
680 const int hit_bit = trailing_zeroes32(static_cast<uint32_t>(m1));
681 note_dots_in_window(b, i + 16, run_start, w1, (1 << hit_bit) - 1,
682 maybe_dot_segment);
683 i += 16 + static_cast<size_t>(hit_bit);
684 return;
685 }
686 note_dots_in_window(b, i + 16, run_start, w1, 0xFFFF, maybe_dot_segment);
687 }
688 for (; i + 16 <= len; i += 16) {
689 const __m128i w =
690 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i));
691 const int mask = ssse3_nibble_mask(w, lo_tbl, hi_tbl);
692 if (mask != 0) {
693 const int hit_bit = trailing_zeroes32(static_cast<uint32_t>(mask));
694 note_dots_in_window(b, i, run_start, w, (1 << hit_bit) - 1,
695 maybe_dot_segment);
696 i += static_cast<size_t>(hit_bit);
697 return;
698 }
699 note_dots_in_window(b, i, run_start, w, 0xFFFF, maybe_dot_segment);
700 }
701 if (i > run_start && i < len) {
702 const __m128i w =
703 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + len - 16));
704 const int mask = ssse3_nibble_mask(w, lo_tbl, hi_tbl);
705 if (mask != 0) {
706 const size_t hit =
707 len - 16 +
708 static_cast<size_t>(trailing_zeroes32(static_cast<uint32_t>(mask)));
709 if (hit >= i) {
710 for (size_t j = i; j < hit; ++j) {
711 if (b[j] == '.') {
712 note_possible_dot_segment(b, j, run_start, maybe_dot_segment);
713 }
714 }
715 i = hit;
716 return;
717 }
718 }
719 for (size_t j = i; j < len; ++j) {
720 if (b[j] == '.') {
721 note_possible_dot_segment(b, j, run_start, maybe_dot_segment);
722 }
723 }
724 i = len;
725 return;
726 }
727 }
728#elif ADA_SSE2
729 for (; i + 16 <= len; i += 16) {
730 const __m128i w = _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i));
731 const int mask = sse2_path_stop(w);
732 if (mask != 0) {
733 const int hit_bit = trailing_zeroes32(static_cast<uint32_t>(mask));
734 note_dots_in_window(b, i, run_start, w, (1 << hit_bit) - 1,
735 maybe_dot_segment);
736 i += static_cast<size_t>(hit_bit);
737 return;
738 }
739 note_dots_in_window(b, i, run_start, w, 0xFFFF, maybe_dot_segment);
740 }
741#elif ADA_NEON
742 if (i + 16 <= len) {
743 const uint8x16_t lo_tbl = vld1q_u8(k_path_nibbles.low);
744 const uint8x16_t hi_tbl = vld1q_u8(k_path_nibbles.high);
745 for (; i + 32 <= len; i += 32) {
746 const uint8x16_t w0 = vld1q_u8(b + i);
747 const uint64_t bits0 = neon_table_stop(w0, lo_tbl, hi_tbl);
748 if (bits0 != 0) {
749 const size_t hit_off =
750 static_cast<size_t>(trailing_zeroes64(bits0)) >> 2;
751 const uint64_t valid =
752 (hit_off == 0) ? 0 : (uint64_t{1} << (hit_off * 4)) - 1;
753 note_dots_in_window_neon(b, i, run_start, w0, valid, maybe_dot_segment);
754 i += hit_off;
755 return;
756 }
757 note_dots_in_window_neon(b, i, run_start, w0, ~uint64_t{0},
758 maybe_dot_segment);
759 const uint8x16_t w1 = vld1q_u8(b + i + 16);
760 const uint64_t bits1 = neon_table_stop(w1, lo_tbl, hi_tbl);
761 if (bits1 != 0) {
762 const size_t hit_off =
763 static_cast<size_t>(trailing_zeroes64(bits1)) >> 2;
764 const uint64_t valid =
765 (hit_off == 0) ? 0 : (uint64_t{1} << (hit_off * 4)) - 1;
766 note_dots_in_window_neon(b, i + 16, run_start, w1, valid,
767 maybe_dot_segment);
768 i += 16 + hit_off;
769 return;
770 }
771 note_dots_in_window_neon(b, i + 16, run_start, w1, ~uint64_t{0},
772 maybe_dot_segment);
773 }
774 for (; i + 16 <= len; i += 16) {
775 const uint8x16_t w = vld1q_u8(b + i);
776 const uint64_t bits = neon_table_stop(w, lo_tbl, hi_tbl);
777 if (bits != 0) {
778 const size_t hit_off =
779 static_cast<size_t>(trailing_zeroes64(bits)) >> 2;
780 const uint64_t valid =
781 (hit_off == 0) ? 0 : (uint64_t{1} << (hit_off * 4)) - 1;
782 note_dots_in_window_neon(b, i, run_start, w, valid, maybe_dot_segment);
783 i += hit_off;
784 return;
785 }
786 note_dots_in_window_neon(b, i, run_start, w, ~uint64_t{0},
787 maybe_dot_segment);
788 }
789 if (i > run_start && i < len) {
790 const uint8x16_t w = vld1q_u8(b + len - 16);
791 const uint64_t bits = neon_table_stop(w, lo_tbl, hi_tbl);
792 if (bits != 0) {
793 const size_t hit =
794 len - 16 + (static_cast<size_t>(trailing_zeroes64(bits)) >> 2);
795 if (hit >= i) {
796 for (size_t j = i; j < hit; ++j) {
797 if (b[j] == '.') {
798 note_possible_dot_segment(b, j, run_start, maybe_dot_segment);
799 }
800 }
801 i = hit;
802 return;
803 }
804 }
805 for (size_t j = i; j < len; ++j) {
806 if (b[j] == '.') {
807 note_possible_dot_segment(b, j, run_start, maybe_dot_segment);
808 }
809 }
810 i = len;
811 return;
812 }
813 }
814#endif
815 for (; i < len; ++i) {
816 const uint8_t c = b[i];
817 const uint8_t cls = k_path[c];
818 if (cls != 0) {
819 return;
820 }
821 if (c == '.') {
822 note_possible_dot_segment(b, i, run_start, maybe_dot_segment);
823 }
824 }
825}
826
827// Advance i to the first class-table stop (or len). Query and hash share
828// this loop; path keeps its own copy because it also tracks '.' segments.
829#if ADA_PARSER_SSSE3
830#define ADA_SCAN_STOP_RUN(nibbles, cls, unused_sse2_stop) \
831 do { \
832 const size_t scan_start = i; \
833 if (parser_use_ssse3() && (i + 16 <= len)) { \
834 const __m128i lo_tbl = nibble_load((nibbles).low); \
835 const __m128i hi_tbl = nibble_load((nibbles).high); \
836 for (; i + 32 <= len; i += 32) { \
837 const __m128i w0 = \
838 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i)); \
839 const int m0 = ssse3_nibble_mask(w0, lo_tbl, hi_tbl); \
840 if (m0 != 0) { \
841 i += static_cast<size_t>( \
842 trailing_zeroes32(static_cast<uint32_t>(m0))); \
843 return; \
844 } \
845 const __m128i w1 = \
846 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i + 16)); \
847 const int m1 = ssse3_nibble_mask(w1, lo_tbl, hi_tbl); \
848 if (m1 != 0) { \
849 i += 16 + static_cast<size_t>( \
850 trailing_zeroes32(static_cast<uint32_t>(m1))); \
851 return; \
852 } \
853 } \
854 for (; i + 16 <= len; i += 16) { \
855 const __m128i w = \
856 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i)); \
857 const int mask = ssse3_nibble_mask(w, lo_tbl, hi_tbl); \
858 if (mask != 0) { \
859 i += static_cast<size_t>( \
860 trailing_zeroes32(static_cast<uint32_t>(mask))); \
861 return; \
862 } \
863 } \
864 if (i > scan_start && i < len) { \
865 const __m128i w = \
866 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + len - 16)); \
867 const int mask = ssse3_nibble_mask(w, lo_tbl, hi_tbl); \
868 if (mask != 0) { \
869 const size_t hit = len - 16 + \
870 static_cast<size_t>(trailing_zeroes32( \
871 static_cast<uint32_t>(mask))); \
872 if (hit >= i) { \
873 i = hit; \
874 return; \
875 } \
876 } \
877 i = len; \
878 return; \
879 } \
880 } \
881 for (; i < len; ++i) { \
882 if ((cls)[b[i]] != 0) { \
883 return; \
884 } \
885 } \
886 } while (0)
887#elif ADA_NEON
888#define ADA_SCAN_STOP_RUN(nibbles, cls, unused_sse2_stop) \
889 do { \
890 const size_t scan_start = i; \
891 if (i + 16 <= len) { \
892 const uint8x16_t lo_tbl = vld1q_u8((nibbles).low); \
893 const uint8x16_t hi_tbl = vld1q_u8((nibbles).high); \
894 for (; i + 32 <= len; i += 32) { \
895 const uint64_t bits0 = \
896 neon_table_stop(vld1q_u8(b + i), lo_tbl, hi_tbl); \
897 if (bits0 != 0) { \
898 i += static_cast<size_t>(trailing_zeroes64(bits0)) >> 2; \
899 return; \
900 } \
901 const uint64_t bits1 = \
902 neon_table_stop(vld1q_u8(b + i + 16), lo_tbl, hi_tbl); \
903 if (bits1 != 0) { \
904 i += 16 + (static_cast<size_t>(trailing_zeroes64(bits1)) >> 2); \
905 return; \
906 } \
907 } \
908 for (; i + 16 <= len; i += 16) { \
909 const uint8x16_t w = vld1q_u8(b + i); \
910 const uint64_t bits = neon_table_stop(w, lo_tbl, hi_tbl); \
911 if (bits != 0) { \
912 i += static_cast<size_t>(trailing_zeroes64(bits)) >> 2; \
913 return; \
914 } \
915 } \
916 if (i > scan_start && i < len) { \
917 const uint8x16_t w = vld1q_u8(b + len - 16); \
918 const uint64_t bits = neon_table_stop(w, lo_tbl, hi_tbl); \
919 if (bits != 0) { \
920 const size_t hit = \
921 len - 16 + (static_cast<size_t>(trailing_zeroes64(bits)) >> 2); \
922 if (hit >= i) { \
923 i = hit; \
924 return; \
925 } \
926 } \
927 i = len; \
928 return; \
929 } \
930 } \
931 for (; i < len; ++i) { \
932 if ((cls)[b[i]] != 0) { \
933 return; \
934 } \
935 } \
936 } while (0)
937#elif ADA_SSE2
938#define ADA_SCAN_STOP_RUN(nibbles, cls, sse2_stop) \
939 do { \
940 for (; i + 16 <= len; i += 16) { \
941 const __m128i w = \
942 _mm_loadu_si128(reinterpret_cast<const __m128i*>(b + i)); \
943 const int mask = sse2_stop(w); \
944 if (mask != 0) { \
945 i += static_cast<size_t>( \
946 trailing_zeroes32(static_cast<uint32_t>(mask))); \
947 return; \
948 } \
949 } \
950 for (; i < len; ++i) { \
951 if ((cls)[b[i]] != 0) { \
952 return; \
953 } \
954 } \
955 } while (0)
956#else
957#define ADA_SCAN_STOP_RUN(nibbles, cls, unused_sse2_stop) \
958 do { \
959 for (; i < len; ++i) { \
960 if ((cls)[b[i]] != 0) { \
961 return; \
962 } \
963 } \
964 } while (0)
965#endif
966
967ADA_PARSER_SIMD void scan_query_run(const uint8_t* b, size_t& i,
968 size_t len) noexcept {
969 ADA_SCAN_STOP_RUN(k_query_nibbles, k_query, sse2_query_stop);
970}
971
972ADA_PARSER_SIMD void scan_hash_run(const uint8_t* b, size_t& i,
973 size_t len) noexcept {
974 ADA_SCAN_STOP_RUN(k_hash_nibbles, k_hash, sse2_hash_stop);
975}
976
977#undef ADA_SCAN_STOP_RUN
978
979bool path_has_dot_segment(std::string_view path) noexcept {
980 if (path.empty()) {
981 return false;
982 }
983 // "." / ".." at the start, with or without a leading '/'.
984 const size_t i = (path[0] == '/') ? 1 : 0;
985 if (i < path.size() && path[i] == '.') {
986 const size_t after = i + 1;
987 if (after == path.size() || path[after] == '/' ||
988 (after < path.size() && path[after] == '.' &&
989 (after + 1 == path.size() || path[after + 1] == '/'))) {
990 return true;
991 }
992 }
993 static constexpr std::string_view slash_dot{"/.", 2};
994 size_t p = i;
995 while ((p = path.find(slash_dot, p)) != std::string_view::npos) {
996 const size_t after = p + 2;
997 if (after == path.size() || path[after] == '/' ||
998 (after < path.size() && path[after] == '.' &&
999 (after + 1 == path.size() || path[after + 1] == '/'))) {
1000 return true;
1001 }
1002 p = after;
1003 }
1004 return false;
1005}
1006
1007} // namespace
1008
1009template <class result_type>
1010ada_never_inline bool finish_simple_absolute_with_port(
1011 std::string_view input, result_type& out, ada::scheme::type scheme_type,
1012 uint32_t protocol_end, size_t host_start, size_t host_end, size_t host_len,
1013 bool has_upper) {
1014 constexpr bool is_ada_url = std::is_same_v<result_type, ada::url>;
1015 constexpr bool is_aggregator =
1016 std::is_same_v<result_type, ada::url_aggregator>;
1017 static_assert(is_ada_url || is_aggregator);
1018
1019 const size_t len = input.size();
1020 const auto* b = reinterpret_cast<const uint8_t*>(input.data());
1021 size_t p = host_end + 1;
1022 uint32_t port_value = 0;
1023 bool any_digit = false;
1024 while (p < len && b[p] >= '0' && b[p] <= '9') {
1025 any_digit = true;
1026 port_value = port_value * 10 + static_cast<uint32_t>(b[p] - '0');
1027 if (port_value > 65535) [[unlikely]] {
1028 return false;
1029 }
1030 ++p;
1031 }
1032 if (p < len && b[p] != '/' && b[p] != '?' && b[p] != '#') [[unlikely]] {
1033 return false;
1034 }
1035 uint32_t parsed_port = url_components::omitted;
1036 const uint16_t default_port = ada::scheme::get_special_port(scheme_type);
1037 if (any_digit && port_value != default_port) {
1038 parsed_port = port_value;
1039 }
1040 const size_t authority_end = p;
1041
1042 size_t i = authority_end;
1043 size_t path_start = host_end;
1044 size_t path_end = host_end;
1045 size_t query_start = std::string_view::npos;
1046 size_t hash_start = std::string_view::npos;
1047 bool has_path = false;
1048 bool maybe_dot_segment = false;
1049 bool rest_simple = true;
1050
1051 if (i < len && b[i] == '/') {
1052 has_path = true;
1053 path_start = i;
1054 ++i;
1055 scan_path_run(b, i, len, maybe_dot_segment);
1056 if (i < len) {
1057 const uint8_t cls = k_path[b[i]];
1058 if (cls == 1) {
1059 path_end = i;
1060 if (b[i] == '?') {
1061 query_start = i;
1062 ++i;
1063 goto scan_query;
1064 }
1065 hash_start = i;
1066 ++i;
1067 goto scan_hash;
1068 }
1069 rest_simple = false;
1070 for (; i < len; ++i) {
1071 if (b[i] == '?') {
1072 path_end = i;
1073 query_start = i;
1074 ++i;
1075 goto scan_query_boundary;
1076 }
1077 if (b[i] == '#') {
1078 path_end = i;
1079 hash_start = i;
1080 ++i;
1081 goto after_rest;
1082 }
1083 }
1084 path_end = i;
1085 goto after_rest;
1086 }
1087 path_end = i;
1088 } else if (i < len && b[i] == '?') {
1089 query_start = i;
1090 ++i;
1091 goto scan_query;
1092 } else if (i < len && b[i] == '#') {
1093 hash_start = i;
1094 ++i;
1095 goto scan_hash;
1096 }
1097 goto after_rest;
1098
1099scan_query:
1100 scan_query_run(b, i, len);
1101 if (i < len) {
1102 if (b[i] == '#') {
1103 hash_start = i;
1104 ++i;
1105 goto scan_hash;
1106 }
1107 rest_simple = false;
1108 goto scan_query_boundary;
1109 }
1110 goto after_rest;
1111
1112scan_query_boundary:
1113 for (; i < len; ++i) {
1114 if (b[i] == '#') {
1115 hash_start = i;
1116 ++i;
1117 goto after_rest;
1118 }
1119 }
1120 goto after_rest;
1121
1122scan_hash:
1123 scan_hash_run(b, i, len);
1124 if (i < len) {
1125 rest_simple = false;
1126 }
1127
1128after_rest:
1129 if (rest_simple && maybe_dot_segment) {
1130 const std::string_view path_body(input.data() + path_start,
1131 path_end - path_start);
1132 if (path_has_dot_segment(path_body)) {
1133 rest_simple = false;
1134 }
1135 }
1136
1137 // The slow path removes ASCII tab/newline anywhere in the input and trims a
1138 // trailing C0 control or space; this fast path does neither. A query or
1139 // fragment reaching the helpers below would keep those bytes percent-encoded
1140 // ("?a\nb" -> "?a%0Ab", "#f " -> "#f%20") instead of stripped, so hand such
1141 // inputs back to the slow path.
1142 if (!rest_simple && (unicode::is_c0_control_or_space(input.back()) ||
1143 unicode::has_tabs_or_newline(input))) {
1144 return false;
1145 }
1146
1147 out.type = scheme_type;
1148 out.is_valid = true;
1149 out.has_opaque_path = false;
1150 out.host_type = DEFAULT;
1151
1152 const uint32_t port_bytes = (parsed_port != url_components::omitted)
1153 ? (1 + port_decimal_digit_count(parsed_port))
1154 : 0;
1155
1156 if (!rest_simple) {
1157 const std::string_view path_view =
1158 has_path
1159 ? std::string_view(input.data() + path_start, path_end - path_start)
1160 : std::string_view{};
1161 auto apply_query_and_hash = [&]() {
1162 if (query_start != std::string_view::npos) {
1163 const size_t q_end =
1164 (hash_start != std::string_view::npos) ? hash_start : len;
1165 out.update_base_search(std::string_view(input.data() + query_start + 1,
1166 q_end - query_start - 1),
1168 }
1169 if (hash_start != std::string_view::npos) {
1170 out.update_unencoded_base_hash(std::string_view(
1171 input.data() + hash_start + 1, len - hash_start - 1));
1172 }
1173 };
1174 if constexpr (is_aggregator) {
1175 out.buffer.assign(input.substr(0, host_end));
1176 if (parsed_port != url_components::omitted) {
1177 append_canonical_port(out.buffer, parsed_port);
1178 }
1179 if (has_upper) {
1180 unicode::to_lower_ascii(out.buffer.data() + host_start, host_len);
1181 }
1182 out.components.protocol_end = protocol_end;
1183 out.components.username_end = protocol_end + 2;
1184 out.components.host_start = protocol_end + 2;
1185 out.components.host_end = static_cast<uint32_t>(host_end);
1186 out.components.port = parsed_port;
1187 out.components.pathname_start = static_cast<uint32_t>(out.buffer.size());
1188 out.components.search_start = url_components::omitted;
1189 out.components.hash_start = url_components::omitted;
1190 out.parse_path(path_view);
1191 apply_query_and_hash();
1192 } else {
1193 std::string host_str(input.substr(host_start, host_len));
1194 if (has_upper) {
1195 unicode::to_lower_ascii(host_str.data(), host_str.size());
1196 }
1197 out.host = std::move(host_str);
1198 if (parsed_port != url_components::omitted) {
1199 out.port = static_cast<uint16_t>(parsed_port);
1200 }
1201 out.parse_path(path_view);
1202 apply_query_and_hash();
1203 }
1204 return true;
1205 }
1206
1207 const bool insert_slash = !has_path;
1208 if constexpr (is_aggregator) {
1209 const size_t out_len =
1210 host_end + port_bytes + (insert_slash ? 1 : 0) + (len - authority_end);
1211 const bool omit_port_bytes = parsed_port == url_components::omitted;
1212 if (out_len == len && !insert_slash && !omit_port_bytes) {
1213 out.buffer.assign(input);
1214 } else {
1215 out.buffer.clear();
1216 out.buffer.reserve(out_len);
1217 out.buffer.append(input.substr(0, host_end));
1218 if (parsed_port != url_components::omitted) {
1219 append_canonical_port(out.buffer, parsed_port);
1220 }
1221 if (insert_slash) {
1222 out.buffer.push_back('/');
1223 }
1224 if (authority_end < len) {
1225 out.buffer.append(input.substr(authority_end));
1226 }
1227 }
1228 if (has_upper) {
1229 unicode::to_lower_ascii(out.buffer.data() + host_start, host_len);
1230 }
1231 const uint32_t pathname_start =
1232 static_cast<uint32_t>(host_end) + port_bytes;
1233 const int32_t tail_delta = static_cast<int32_t>(pathname_start) +
1234 (insert_slash ? 1 : 0) -
1235 static_cast<int32_t>(authority_end);
1236 out.components.protocol_end = protocol_end;
1237 out.components.username_end = protocol_end + 2;
1238 out.components.host_start = protocol_end + 2;
1239 out.components.host_end = static_cast<uint32_t>(host_end);
1240 out.components.port = parsed_port;
1241 out.components.pathname_start = pathname_start;
1242 out.components.search_start =
1243 (query_start != std::string_view::npos)
1244 ? static_cast<uint32_t>(static_cast<int32_t>(query_start) +
1245 tail_delta)
1247 out.components.hash_start =
1248 (hash_start != std::string_view::npos)
1249 ? static_cast<uint32_t>(static_cast<int32_t>(hash_start) +
1250 tail_delta)
1252 } else {
1253 std::string host_str(input.substr(host_start, host_len));
1254 if (has_upper) {
1255 unicode::to_lower_ascii(host_str.data(), host_str.size());
1256 }
1257 out.host = std::move(host_str);
1258 if (parsed_port != url_components::omitted) {
1259 out.port = static_cast<uint16_t>(parsed_port);
1260 }
1261 if (insert_slash) {
1262 out.path = "/";
1263 } else {
1264 out.path.assign(input.data() + path_start, path_end - path_start);
1265 }
1266 if (query_start != std::string_view::npos) {
1267 const size_t q_end =
1268 (hash_start != std::string_view::npos) ? hash_start : len;
1269 out.query.emplace(input.data() + query_start + 1,
1270 q_end - query_start - 1);
1271 }
1272 if (hash_start != std::string_view::npos) {
1273 out.hash.emplace(input.data() + hash_start + 1, len - hash_start - 1);
1274 }
1275 }
1276 return true;
1277}
1278
1279// Fast path for already-canonical special-scheme URLs of the shape
1280// scheme://host[/path][?query][#fragment]. When the host is a plain domain
1281// but the rest needs encoding or dot-segment normalization, the host is
1282// kept and the path/query/hash helpers finish the URL.
1283template <class result_type>
1284ada_never_inline bool try_parse_simple_absolute(std::string_view input,
1285 result_type& out) {
1286 constexpr bool is_ada_url = std::is_same_v<result_type, ada::url>;
1287 constexpr bool is_aggregator =
1288 std::is_same_v<result_type, ada::url_aggregator>;
1289 static_assert(is_ada_url || is_aggregator);
1290
1291 const size_t len = input.size();
1292 // Shortest accepted form is "ws://x" (6).
1293 if (len < 6) [[unlikely]] {
1294 return false;
1295 }
1296 const auto* b = reinterpret_cast<const uint8_t*>(input.data());
1297
1298 size_t pos = 0;
1300 uint32_t protocol_end = 0;
1301#if (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) || \
1302 defined(_M_X64) || defined(_M_IX86) || defined(_M_AMD64)
1303 // One 8-byte load + integer compare is a single cmp/jcc on x86-64.
1304 // Masked compares cover the shorter special schemes without extra loads.
1305 if (len >= 8) {
1306 uint64_t first8 = 0;
1307 std::memcpy(&first8, b, 8);
1308 if (first8 == 0x2f2f3a7370747468ull) { // "https://"
1309 pos = 8;
1310 scheme_type = ada::scheme::type::HTTPS;
1311 protocol_end = 6;
1312 } else if ((first8 & 0x00ffffffffffffffull) ==
1313 0x002f2f3a70747468ull) { // "http://"
1314 pos = 7;
1315 scheme_type = ada::scheme::type::HTTP;
1316 protocol_end = 5;
1317 } else if ((first8 & 0x0000ffffffffffffull) ==
1318 0x00002f2f3a737377ull) { // "wss://"
1319 pos = 6;
1320 scheme_type = ada::scheme::type::WSS;
1321 protocol_end = 4;
1322 } else if ((first8 & 0x0000ffffffffffffull) ==
1323 0x00002f2f3a707466ull) { // "ftp://"
1324 pos = 6;
1325 scheme_type = ada::scheme::type::FTP;
1326 protocol_end = 4;
1327 } else if ((first8 & 0x000000ffffffffffull) ==
1328 0x0000002f2f3a7377ull) { // "ws://"
1329 pos = 5;
1330 scheme_type = ada::scheme::type::WS;
1331 protocol_end = 3;
1332 } else {
1333 return false;
1334 }
1335 } else if (b[0] == 'w' && b[1] == 's') {
1336 if (b[2] == ':' && b[3] == '/' && b[4] == '/') {
1337 pos = 5;
1338 scheme_type = ada::scheme::type::WS;
1339 protocol_end = 3;
1340 } else if (b[2] == 's' && b[3] == ':' && b[4] == '/' && b[5] == '/') {
1341 pos = 6;
1342 scheme_type = ada::scheme::type::WSS;
1343 protocol_end = 4;
1344 } else {
1345 return false;
1346 }
1347 } else if (b[0] == 'f' && b[1] == 't' && b[2] == 'p' && b[3] == ':' &&
1348 b[4] == '/' && b[5] == '/') {
1349 pos = 6;
1350 scheme_type = ada::scheme::type::FTP;
1351 protocol_end = 4;
1352 } else if (len >= 7 && b[0] == 'h' && b[1] == 't' && b[2] == 't' &&
1353 b[3] == 'p' && b[4] == ':' && b[5] == '/' && b[6] == '/') {
1354 pos = 7;
1355 scheme_type = ada::scheme::type::HTTP;
1356 protocol_end = 5;
1357 } else {
1358 return false;
1359 }
1360#else
1361 // Big-endian / uncommon arches: byte-wise special-scheme match.
1362 if (len >= 8 && b[0] == 'h' && b[1] == 't' && b[2] == 't' && b[3] == 'p' &&
1363 b[4] == 's' && b[5] == ':' && b[6] == '/' && b[7] == '/') {
1364 pos = 8;
1365 scheme_type = ada::scheme::type::HTTPS;
1366 protocol_end = 6;
1367 } else if (len >= 7 && b[0] == 'h' && b[1] == 't' && b[2] == 't' &&
1368 b[3] == 'p' && b[4] == ':' && b[5] == '/' && b[6] == '/') {
1369 pos = 7;
1370 scheme_type = ada::scheme::type::HTTP;
1371 protocol_end = 5;
1372 } else if (b[0] == 'w' && b[1] == 's') {
1373 if (b[2] == ':' && b[3] == '/' && b[4] == '/') {
1374 pos = 5;
1375 scheme_type = ada::scheme::type::WS;
1376 protocol_end = 3;
1377 } else if (len >= 6 && b[2] == 's' && b[3] == ':' && b[4] == '/' &&
1378 b[5] == '/') {
1379 pos = 6;
1380 scheme_type = ada::scheme::type::WSS;
1381 protocol_end = 4;
1382 } else {
1383 return false;
1384 }
1385 } else if (b[0] == 'f' && b[1] == 't' && b[2] == 'p' && b[3] == ':' &&
1386 b[4] == '/' && b[5] == '/') {
1387 pos = 6;
1388 scheme_type = ada::scheme::type::FTP;
1389 protocol_end = 4;
1390 } else {
1391 return false;
1392 }
1393#endif
1394 if (pos < len && (b[pos] == '/' || b[pos] == '\\')) [[unlikely]] {
1395 return false;
1396 }
1397
1398 // Digit-led hosts are IPv4/numeric; '[' is IPv6. Skip before scanning.
1399 if (pos < len && ((b[pos] >= '0' && b[pos] <= '9') || b[pos] == '[')) {
1400 return false;
1401 }
1402
1403 const size_t host_start = pos;
1404 bool has_upper = false;
1405 bool has_x = false;
1406 size_t host_end = pos;
1407 if (!scan_plain_host(b, pos, len, host_end, has_upper, has_x)) {
1408 return false;
1409 }
1410 if (host_start == host_end) [[unlikely]] {
1411 return false;
1412 }
1413 const size_t host_len = host_end - host_start;
1414 if (host_len > 253) [[unlikely]] {
1415 return false;
1416 }
1417 {
1418 std::string_view hv(input.data() + host_start, host_len);
1419 char host_buf[256];
1420 if (has_upper) [[unlikely]] {
1421 std::memcpy(host_buf, input.data() + host_start, host_len);
1422 unicode::to_lower_ascii(host_buf, host_len);
1423 hv = std::string_view(host_buf, host_len);
1424 }
1425 if (ada::checkers::last_label_may_be_a_number(hv)) [[unlikely]] {
1426 return false;
1427 }
1428 // Punycode is "xn--...". The host scan already notes a lowercase 'x';
1429 // uppercase 'X' is covered by has_upper after the in-place lower.
1430 static constexpr std::string_view xn{"xn-", 3};
1431 if ((has_x || has_upper) && hv.find(xn) != std::string_view::npos)
1432 [[unlikely]] {
1433 return false;
1434 }
1435 }
1436
1437 if (host_end < len && b[host_end] == ':') [[unlikely]] {
1438 return finish_simple_absolute_with_port(input, out, scheme_type,
1439 protocol_end, host_start, host_end,
1440 host_len, has_upper);
1441 }
1442
1443 size_t i = host_end;
1444 size_t path_start = host_end;
1445 size_t path_end = host_end;
1446 size_t query_start = std::string_view::npos;
1447 size_t hash_start = std::string_view::npos;
1448 bool has_path = false;
1449 bool maybe_dot_segment = false;
1450 bool rest_simple = true;
1451
1452 if (i < len && b[i] == '/') {
1453 has_path = true;
1454 path_start = i;
1455 ++i;
1456 scan_path_run(b, i, len, maybe_dot_segment);
1457 if (i < len) {
1458 const uint8_t cls = k_path[b[i]];
1459 if (cls == 1) {
1460 path_end = i;
1461 if (b[i] == '?') {
1462 query_start = i;
1463 ++i;
1464 goto scan_query;
1465 }
1466 hash_start = i;
1467 ++i;
1468 goto scan_hash;
1469 }
1470 rest_simple = false;
1471 hash_start = input.find('#', i);
1472 query_start = input.substr(0, hash_start).find('?', i);
1473 if (query_start != std::string_view::npos) {
1474 path_end = query_start;
1475 } else {
1476 path_end = hash_start != std::string_view::npos ? hash_start : len;
1477 }
1478 goto after_rest;
1479 }
1480 path_end = i;
1481 } else if (i < len && b[i] == '?') {
1482 query_start = i;
1483 ++i;
1484 goto scan_query;
1485 } else if (i < len && b[i] == '#') {
1486 hash_start = i;
1487 ++i;
1488 goto scan_hash;
1489 }
1490 goto after_rest;
1491
1492scan_query:
1493 scan_query_run(b, i, len);
1494 if (i < len) {
1495 if (b[i] == '#') {
1496 hash_start = i;
1497 ++i;
1498 goto scan_hash;
1499 }
1500 rest_simple = false;
1501 goto scan_query_boundary;
1502 }
1503 goto after_rest;
1504
1505scan_query_boundary:
1506 hash_start = input.find('#', i);
1507 goto after_rest;
1508
1509scan_hash:
1510 scan_hash_run(b, i, len);
1511 if (i < len) {
1512 rest_simple = false;
1513 }
1514
1515after_rest:
1516 if (rest_simple && maybe_dot_segment) {
1517 const std::string_view path_body(input.data() + path_start,
1518 path_end - path_start);
1519 if (path_has_dot_segment(path_body)) {
1520 rest_simple = false;
1521 }
1522 }
1523
1524 // The slow path removes ASCII tab/newline anywhere in the input and trims a
1525 // trailing C0 control or space; this fast path does neither. A query or
1526 // fragment reaching the helpers below would keep those bytes percent-encoded
1527 // ("?a\nb" -> "?a%0Ab", "#f " -> "#f%20") instead of stripped, so hand such
1528 // inputs back to the slow path.
1529 if (!rest_simple && (unicode::is_c0_control_or_space(input.back()) ||
1530 unicode::has_tabs_or_newline(input))) {
1531 return false;
1532 }
1533
1534 out.type = scheme_type;
1535 out.is_valid = true;
1536 out.has_opaque_path = false;
1537 out.host_type = DEFAULT;
1538
1539 if (!rest_simple) {
1540 // Host is a plain domain. Finish path/query/hash with
1541 // the regular helpers
1542 // so percent-encoding and dot segments do not re-parse the authority.
1543 const std::string_view path_view =
1544 has_path
1545 ? std::string_view(input.data() + path_start, path_end - path_start)
1546 : std::string_view{};
1547 auto apply_query_and_hash = [&]() {
1548 if (query_start != std::string_view::npos) {
1549 const size_t q_end =
1550 (hash_start != std::string_view::npos) ? hash_start : len;
1551 out.update_base_search(std::string_view(input.data() + query_start + 1,
1552 q_end - query_start - 1),
1554 }
1555 if (hash_start != std::string_view::npos) {
1556 out.update_unencoded_base_hash(std::string_view(
1557 input.data() + hash_start + 1, len - hash_start - 1));
1558 }
1559 };
1560 if constexpr (is_aggregator) {
1561 out.buffer.assign(input.substr(0, host_end));
1562 if (has_upper) {
1563 unicode::to_lower_ascii(out.buffer.data() + host_start, host_len);
1564 }
1565 out.components.protocol_end = protocol_end;
1566 out.components.username_end = protocol_end + 2;
1567 out.components.host_start = protocol_end + 2;
1568 out.components.host_end = static_cast<uint32_t>(host_end);
1569 out.components.port = url_components::omitted;
1570 out.components.pathname_start = static_cast<uint32_t>(host_end);
1571 out.components.search_start = url_components::omitted;
1572 out.components.hash_start = url_components::omitted;
1573 out.parse_path(path_view);
1574 apply_query_and_hash();
1575 } else {
1576 std::string host_str(input.substr(host_start, host_len));
1577 if (has_upper) {
1578 unicode::to_lower_ascii(host_str.data(), host_str.size());
1579 }
1580 out.host = std::move(host_str);
1581 out.parse_path(path_view);
1582 apply_query_and_hash();
1583 }
1584 return true;
1585 }
1586
1587 const bool need_slash = !has_path;
1588 if constexpr (is_aggregator) {
1589 if (!need_slash) {
1590 // assign copies once. resize()+memcpy would value-init then overwrite.
1591 out.buffer.assign(input);
1592 if (has_upper) {
1593 unicode::to_lower_ascii(out.buffer.data() + host_start, host_len);
1594 }
1595 out.components.protocol_end = protocol_end;
1596 out.components.username_end = protocol_end + 2;
1597 out.components.host_start = protocol_end + 2;
1598 out.components.host_end = static_cast<uint32_t>(host_end);
1599 out.components.port = url_components::omitted;
1600 out.components.pathname_start = static_cast<uint32_t>(path_start);
1601 out.components.search_start = (query_start != std::string_view::npos)
1602 ? static_cast<uint32_t>(query_start)
1604 out.components.hash_start = (hash_start != std::string_view::npos)
1605 ? static_cast<uint32_t>(hash_start)
1607 } else {
1608 out.buffer.clear();
1609 out.buffer.reserve(len + 1);
1610 out.buffer.append(input.substr(0, host_end));
1611 out.buffer.push_back('/');
1612 if (host_end < len) {
1613 out.buffer.append(input.substr(host_end));
1614 }
1615 if (has_upper) {
1616 unicode::to_lower_ascii(out.buffer.data() + host_start, host_len);
1617 }
1618 out.components.protocol_end = protocol_end;
1619 out.components.username_end = protocol_end + 2;
1620 out.components.host_start = protocol_end + 2;
1621 out.components.host_end = static_cast<uint32_t>(host_end);
1622 out.components.port = url_components::omitted;
1623 out.components.pathname_start = static_cast<uint32_t>(host_end);
1624 out.components.search_start = (query_start != std::string_view::npos)
1625 ? static_cast<uint32_t>(query_start + 1)
1627 out.components.hash_start = (hash_start != std::string_view::npos)
1628 ? static_cast<uint32_t>(hash_start + 1)
1630 }
1631 } else {
1632 std::string host_str(input.substr(host_start, host_len));
1633 if (has_upper) {
1634 unicode::to_lower_ascii(host_str.data(), host_str.size());
1635 }
1636 out.host = std::move(host_str);
1637 if (need_slash) {
1638 out.path = "/";
1639 } else {
1640 out.path.assign(input.data() + path_start, path_end - path_start);
1641 }
1642 if (query_start != std::string_view::npos) {
1643 const size_t q_end =
1644 (hash_start != std::string_view::npos) ? hash_start : len;
1645 out.query.emplace(input.data() + query_start + 1,
1646 q_end - query_start - 1);
1647 }
1648 if (hash_start != std::string_view::npos) {
1649 out.hash.emplace(input.data() + hash_start + 1, len - hash_start - 1);
1650 }
1651 }
1652 return true;
1653}
1654
1655// Fast path for `/path`, path-relative (`foo`, `c/d?q`), `?query`, and
1656// `#fragment` against a special-scheme base. Scheme-relative (`//`) and
1657// scheme-like first segments (`foo:bar`) stay on the state machine.
1658template <class result_type>
1659ada_never_inline bool try_parse_simple_relative(std::string_view input,
1660 const result_type& base,
1661 result_type& out) {
1662 constexpr bool is_ada_url = std::is_same_v<result_type, ada::url>;
1663 constexpr bool is_aggregator =
1664 std::is_same_v<result_type, ada::url_aggregator>;
1665 static_assert(is_ada_url || is_aggregator);
1666
1667 if (!base.is_special() || base.type == ada::scheme::type::FILE ||
1668 base.has_opaque_path || input.empty()) {
1669 return false;
1670 }
1671 const auto* b = reinterpret_cast<const uint8_t*>(input.data());
1672 const size_t len = input.size();
1673 const uint8_t first = b[0];
1674 const bool path_relative = first != '/' && first != '?' && first != '#';
1675 if (first == '/' && len > 1 && (b[1] == '/' || b[1] == '\\')) {
1676 return false;
1677 }
1678 // A ':' before the first / ? # is a scheme, not a path segment.
1679 if (path_relative) {
1680 const size_t delim = input.find_first_of("/?#:");
1681 if (delim != std::string_view::npos && input[delim] == ':') {
1682 return false;
1683 }
1684 }
1685
1686 size_t i = 0;
1687 size_t path_start = 0;
1688 size_t path_end = 0;
1689 size_t query_start = std::string_view::npos;
1690 size_t hash_start = std::string_view::npos;
1691 bool has_path = false;
1692 bool maybe_dot_segment = false;
1693
1694 if (first == '/' || path_relative) {
1695 has_path = true;
1696 path_start = 0;
1697 if (first == '/') {
1698 i = 1;
1699 }
1700 scan_path_run(b, i, len, maybe_dot_segment);
1701 if (i < len) {
1702 const uint8_t cls = k_path[b[i]];
1703 if (cls == 2) {
1704 return false;
1705 }
1706 }
1707 path_end = i;
1708 if (i < len && b[i] == '?') {
1709 query_start = i;
1710 ++i;
1711 scan_query_run(b, i, len);
1712 if (i < len) {
1713 if (b[i] != '#') {
1714 return false;
1715 }
1716 hash_start = i;
1717 ++i;
1718 scan_hash_run(b, i, len);
1719 if (i < len) {
1720 return false;
1721 }
1722 }
1723 } else if (i < len && b[i] == '#') {
1724 hash_start = i;
1725 ++i;
1726 scan_hash_run(b, i, len);
1727 if (i < len) {
1728 return false;
1729 }
1730 } else if (i < len) {
1731 return false;
1732 }
1733 } else if (first == '?') {
1734 query_start = 0;
1735 i = 1;
1736 scan_query_run(b, i, len);
1737 if (i < len) {
1738 if (b[i] != '#') {
1739 return false;
1740 }
1741 hash_start = i;
1742 ++i;
1743 scan_hash_run(b, i, len);
1744 if (i < len) {
1745 return false;
1746 }
1747 }
1748 } else {
1749 hash_start = 0;
1750 i = 1;
1751 scan_hash_run(b, i, len);
1752 if (i < len) {
1753 return false;
1754 }
1755 }
1756
1757 if (has_path && maybe_dot_segment) {
1758 const std::string_view path_body(input.data() + path_start,
1759 path_end - path_start);
1760 if (path_has_dot_segment(path_body)) {
1761 return false;
1762 }
1763 }
1764
1765 out = base;
1766 out.is_valid = true;
1767 out.has_opaque_path = false;
1768
1769 const size_t q_end =
1770 (hash_start != std::string_view::npos) ? hash_start : len;
1771 const bool has_query = query_start != std::string_view::npos;
1772 const bool has_hash = hash_start != std::string_view::npos;
1773 const std::string_view query =
1774 has_query ? std::string_view(input.data() + query_start + 1,
1775 q_end - query_start - 1)
1776 : std::string_view{};
1777 const std::string_view hash =
1778 has_hash ? std::string_view(input.data() + hash_start + 1,
1779 len - hash_start - 1)
1780 : std::string_view{};
1781
1782 if constexpr (is_aggregator) {
1783 if (first == '/' || first == '?' || path_relative) {
1784 out.clear_hash();
1785 out.clear_search();
1786 }
1787 if (first == '/') {
1788 out.update_base_pathname(input.substr(path_start, path_end - path_start));
1789 } else if (path_relative) {
1790 const std::string_view base_path = out.get_pathname();
1791 const size_t slash = base_path.rfind('/');
1792 const std::string_view prefix = (slash == std::string_view::npos)
1793 ? std::string_view("/")
1794 : base_path.substr(0, slash + 1);
1795 const std::string_view rel(input.data() + path_start,
1796 path_end - path_start);
1797 std::string new_path;
1798 new_path.reserve(prefix.size() + rel.size());
1799 new_path.assign(prefix);
1800 new_path.append(rel);
1801 out.update_base_pathname(new_path);
1802 }
1803 if (has_query) {
1804 // Do not use update_base_search: it strips a leading '?' and would
1805 // collapse '??a=b' into '?a=b'.
1806 out.components.search_start = static_cast<uint32_t>(out.buffer.size());
1807 out.buffer += '?';
1808 out.buffer.append(query);
1809 }
1810 if (has_hash) {
1811 out.update_unencoded_base_hash(hash);
1812 }
1813 } else {
1814 if (first == '/' || first == '?' || path_relative) {
1815 out.hash.reset();
1816 }
1817 if (first == '/') {
1818 out.query.reset();
1819 out.path.assign(input.substr(path_start, path_end - path_start));
1820 } else if (path_relative) {
1821 out.query.reset();
1822 const size_t slash = out.path.rfind('/');
1823 if (slash == std::string::npos) {
1824 out.path = '/';
1825 } else {
1826 out.path.resize(slash + 1);
1827 }
1828 out.path.append(input.substr(path_start, path_end - path_start));
1829 }
1830 if (has_query) {
1831 out.query.emplace(query);
1832 }
1833 if (has_hash) {
1834 out.hash.emplace(hash);
1835 }
1836 }
1837 return true;
1838}
1839
1840template <class result_type, bool store_values>
1841result_type parse_url_impl(std::string_view user_input,
1842 const result_type* base_url) {
1843 // We can specialize the implementation per type.
1844 // Important: result_type_is_ada_url is evaluated at *compile time*. This
1845 // means that doing if constexpr(result_type_is_ada_url) { something } else {
1846 // something else } is free (at runtime). This means that ada::url_aggregator
1847 // and ada::url **do not have to support the exact same API**.
1848 constexpr bool result_type_is_ada_url = std::is_same_v<url, result_type>;
1849 constexpr bool result_type_is_ada_url_aggregator =
1850 std::is_same_v<url_aggregator, result_type>;
1851 static_assert(result_type_is_ada_url ||
1852 result_type_is_ada_url_aggregator); // We don't support
1853 // anything else for now.
1854
1855 ada_log("ada::parser::parse_url('", user_input, "' [", user_input.size(),
1856 " bytes],", (base_url != nullptr ? base_url->to_string() : "null"),
1857 ")");
1858
1859 result_type url{};
1860
1861 const uint32_t max_input_length = ada::get_max_input_length();
1862
1863 // Normalization (percent-encoding, IDNA) can push the serialized URL past
1864 // max_input_length even when the input fit under it. The check at the end of
1865 // the state machine covers URLs that run to completion, but several states
1866 // return early after appending a query or fragment, so run the same check on
1867 // those exits too. Without this, a query- or fragment-terminated URL such as
1868 // file://x/?<...> or https://user@x/?<...> is accepted while the equivalent
1869 // https://x/?<...> that takes the absolute fast path is rejected.
1870 const auto enforce_max_input_length = [&]() {
1871 if constexpr (store_values) {
1872 if (url.is_valid) {
1873 if constexpr (result_type_is_ada_url_aggregator) {
1874 if (url.buffer.size() > max_input_length) [[unlikely]] {
1875 url.is_valid = false;
1876 }
1877 } else {
1878 if (url.get_href_size() > max_input_length) [[unlikely]] {
1879 url.is_valid = false;
1880 }
1881 }
1882 }
1883 }
1884 };
1885
1886 // We refuse to parse URL strings that exceed the maximum input length.
1887 // By default, this is 4GB but can be configured via
1888 // ada::set_max_input_length().
1889 if (user_input.size() > max_input_length) [[unlikely]] {
1890 url.is_valid = false;
1891 }
1892 // Going forward, user_input.size() is in [0,
1893 // std::numeric_limits<uint32_t>::max). If we are provided with an invalid
1894 // base, or the optional_url was invalid, we must return.
1895 if (base_url != nullptr) {
1896 url.is_valid &= base_url->is_valid;
1897 }
1898 if (!url.is_valid) {
1899 return url;
1900 }
1901
1902 // Simple absolute / relative fast paths (before tabs/newline scan).
1903 if constexpr (store_values) {
1904 bool hit_fast_path = false;
1905 if (base_url == nullptr) {
1906 // IPv4/IPv6 and userinfo miss the fast path. Skip the never_inline
1907 // call so those URLs (including SetHref) do not pay for a miss.
1908 const auto* p = reinterpret_cast<const uint8_t*>(user_input.data());
1909 const size_t n = user_input.size();
1910 size_t host_start = 0;
1911 if (n >= 8 && p[4] == ':' && p[5] == '/' && p[6] == '/') {
1912 host_start = 7;
1913 } else if (n >= 9 && p[5] == ':' && p[6] == '/' && p[7] == '/') {
1914 host_start = 8;
1915 }
1916 const uint8_t host_first = host_start != 0 ? p[host_start] : 0;
1917 const bool skip_ip =
1918 host_first == '[' || (host_first >= '0' && host_first <= '9');
1919 // Only scan for userinfo when the host is not an IP literal, so
1920 // IPv4/IPv6 inputs skip the SIMD '@' check entirely.
1921 hit_fast_path =
1922 !skip_ip &&
1923 !(host_start != 0 && authority_has_at(p, host_start, n)) &&
1924 try_parse_simple_absolute(user_input, url);
1925 } else {
1926 hit_fast_path = try_parse_simple_relative(user_input, *base_url, url);
1927 }
1928 if (hit_fast_path) {
1929 if constexpr (result_type_is_ada_url_aggregator) {
1930 if (url.buffer.size() > max_input_length) [[unlikely]] {
1931 url.is_valid = false;
1932 }
1933 } else {
1934 // For a small absolute input, even worst-case normalization cannot
1935 // exceed the limit: percent encoding expands at most 3x and IDNA at
1936 // most 4.5x. Avoid traversing every stored component on the common
1937 // default-limit path.
1938 if ((base_url != nullptr ||
1939 user_input.size() > static_cast<size_t>(max_input_length) / 5) &&
1940 url.get_href_size() > max_input_length) [[unlikely]] {
1941 url.is_valid = false;
1942 }
1943 }
1944 return url;
1945 }
1946 }
1947
1949
1950 std::string tmp_buffer;
1951 std::string_view url_data;
1952 if (unicode::has_tabs_or_newline(user_input)) [[unlikely]] {
1953 tmp_buffer = user_input;
1954 // Optimization opportunity: Instead of copying and then pruning, we could
1955 // just directly build the string from user_input.
1956 helpers::remove_ascii_tab_or_newline(tmp_buffer);
1957 url_data = tmp_buffer;
1958 } else [[likely]] {
1959 url_data = user_input;
1960 }
1961
1962 // Leading and trailing control characters are uncommon and easy to deal with
1963 // (no performance concern).
1964 helpers::trim_c0_whitespace(url_data);
1965
1966 if constexpr (result_type_is_ada_url_aggregator && store_values) {
1967 // Most of the time, we just need user_input.size().
1968 // In some instances, we may need a bit more.
1970 // This is *very* important. This line should *not* be removed
1971 // hastily. There are principled reasons why reserve is important
1972 // for performance. If you have a benchmark with small inputs,
1973 // it may not matter, but in other instances, it could.
1975 // This rounds up to the next power of two.
1976 // We know that user_input.size() is in [0,
1977 // std::numeric_limits<uint32_t>::max).
1978 uint32_t reserve_capacity =
1979 (0xFFFFFFFF >>
1980 helpers::leading_zeroes(uint32_t(1 | user_input.size()))) +
1981 1;
1982 url.reserve(reserve_capacity);
1983 }
1984
1985 // Optimization opportunity. Most websites do not have fragment.
1986 std::optional<std::string_view> fragment = helpers::prune_hash(url_data);
1987 // We add it last so that an implementation like ada::url_aggregator
1988 // can append it last to its internal buffer, thus improving performance.
1989
1990 // Here url_data no longer has its fragment.
1991 // We are going to access the data from url_data (it is immutable).
1992 // At any given time, we are pointing at byte 'input_position' in url_data.
1993 // The input_position variable should range from 0 to input_size.
1994 // It is illegal to access url_data at input_size.
1995 size_t input_position = 0;
1996 const size_t input_size = url_data.size();
1997 // Keep running the following state machine by switching on state.
1998 // If after a run pointer points to the EOF code point, go to the next step.
1999 // Otherwise, increase pointer by 1 and continue with the state machine.
2000 // We never decrement input_position.
2001 while (input_position <= input_size) {
2002 ada_log("In parsing at ", input_position, " out of ", input_size,
2003 " in state ", ada::to_string(state));
2004 switch (state) {
2005 case state::SCHEME_START: {
2006 ada_log("SCHEME_START ", helpers::substring(url_data, input_position));
2007 // If c is an ASCII alpha, append c, lowercased, to buffer, and set
2008 // state to scheme state.
2009 if ((input_position != input_size) &&
2010 checkers::is_alpha(url_data[input_position])) {
2012 input_position++;
2013 } else {
2014 // Otherwise, if state override is not given, set state to no scheme
2015 // state and decrease pointer by 1.
2017 }
2018 break;
2019 }
2020 case state::SCHEME: {
2021 ada_log("SCHEME ", helpers::substring(url_data, input_position));
2022 // If c is an ASCII alphanumeric, U+002B (+), U+002D (-), or U+002E (.),
2023 // append c, lowercased, to buffer.
2024 while ((input_position != input_size) &&
2025 (unicode::is_alnum_plus(url_data[input_position]))) {
2026 input_position++;
2027 }
2028 // Otherwise, if c is U+003A (:), then:
2029 if ((input_position != input_size) &&
2030 (url_data[input_position] == ':')) {
2031 ada_log("SCHEME the scheme should be ",
2032 url_data.substr(0, input_position));
2033 if constexpr (result_type_is_ada_url) {
2034 if (!url.parse_scheme(url_data.substr(0, input_position))) {
2035 return url;
2036 }
2037 } else {
2038 // we pass the colon along instead of painfully adding it back.
2039 if (!url.parse_scheme_with_colon(
2040 url_data.substr(0, input_position + 1))) {
2041 return url;
2042 }
2043 }
2044 ada_log("SCHEME the scheme is ", url.get_protocol());
2045
2046 // If url's scheme is "file", then:
2047 // NOLINTNEXTLINE(bugprone-branch-clone)
2048 if (url.type == scheme::type::FILE) {
2049 // Set state to file state.
2051 }
2052 // Otherwise, if url is special, base is non-null, and base's scheme
2053 // is url's scheme: Note: Doing base_url->scheme is unsafe if base_url
2054 // != nullptr is false.
2055 else if (url.is_special() && base_url != nullptr &&
2056 base_url->type == url.type) {
2057 // Set state to special relative or authority state.
2059 }
2060 // Otherwise, if url is special, set state to special authority
2061 // slashes state.
2062 else if (url.is_special()) {
2064 }
2065 // Otherwise, if remaining starts with an U+002F (/), set state to
2066 // path or authority state and increase pointer by 1.
2067 else if (input_position + 1 < input_size &&
2068 url_data[input_position + 1] == '/') {
2070 input_position++;
2071 }
2072 // Otherwise, set url's path to the empty string and set state to
2073 // opaque path state.
2074 else {
2076 }
2077 }
2078 // Otherwise, if state override is not given, set buffer to the empty
2079 // string, state to no scheme state, and start over (from the first code
2080 // point in input).
2081 else {
2083 input_position = 0;
2084 break;
2085 }
2086 input_position++;
2087 break;
2088 }
2089 case state::NO_SCHEME: {
2090 ada_log("NO_SCHEME ", helpers::substring(url_data, input_position));
2091 // The fragment was pruned from url_data before the state machine ran,
2092 // so 'c is U+0023 (#)' holds exactly when a fragment was found and
2093 // nothing else remains in front of it.
2094 const bool c_is_hash =
2095 fragment.has_value() && input_position == input_size;
2096 // If base is null, or base has an opaque path and c is not U+0023 (#),
2097 // validation error, return failure.
2098 if (base_url == nullptr || (base_url->has_opaque_path && !c_is_hash)) {
2099 ada_log("NO_SCHEME validation error");
2100 url.is_valid = false;
2101 return url;
2102 }
2103 // Otherwise, if base has an opaque path and c is U+0023 (#),
2104 // set url's scheme to base's scheme, url's path to base's path, url's
2105 // query to base's query, and set state to fragment state.
2106 else if (base_url->has_opaque_path && c_is_hash) {
2107 ada_log("NO_SCHEME opaque base with fragment");
2108 url.copy_scheme(*base_url);
2109 url.has_opaque_path = base_url->has_opaque_path;
2110
2111 if constexpr (result_type_is_ada_url) {
2112 url.path = base_url->path;
2113 url.query = base_url->query;
2114 } else {
2115 url.update_base_pathname(base_url->get_pathname());
2116 if (base_url->has_search()) {
2117 // get_search() returns "" for an empty query string (URL ends
2118 // with '?'). update_base_search("") would incorrectly clear the
2119 // query, so pass "?" to preserve the empty query distinction.
2120 auto s = base_url->get_search();
2121 url.update_base_search(s.empty() ? std::string_view("?") : s);
2122 }
2123 }
2124 url.update_unencoded_base_hash(*fragment);
2125 enforce_max_input_length();
2126 return url;
2127 }
2128 // Otherwise, if base's scheme is not "file", set state to relative
2129 // state and decrease pointer by 1.
2130 // NOLINTNEXTLINE(bugprone-branch-clone)
2131 else if (base_url->type != scheme::type::FILE) {
2132 ada_log("NO_SCHEME non-file relative path");
2134 }
2135 // Otherwise, set state to file state and decrease pointer by 1.
2136 else {
2137 ada_log("NO_SCHEME file base type");
2139 }
2140 break;
2141 }
2142 case state::AUTHORITY: {
2143 ada_log("AUTHORITY ", helpers::substring(url_data, input_position));
2144 // most URLs have no @. Having no @ tells us that we don't have to worry
2145 // about AUTHORITY. Of course, we could have @ and still not have to
2146 // worry about AUTHORITY.
2147 // TODO: Instead of just collecting a bool, collect the location of the
2148 // '@' and do something useful with it.
2149 // TODO: We could do various processing early on, using a single pass
2150 // over the string to collect information about it, e.g., telling us
2151 // whether there is a @ and if so, where (or how many).
2152
2153 // Check if url data contains an @.
2154 if (url_data.find('@', input_position) == std::string_view::npos) {
2156 break;
2157 }
2158 bool at_sign_seen{false};
2159 bool password_token_seen{false};
2165 do {
2166 std::string_view view = url_data.substr(input_position);
2167 // The delimiters are @, /, ? \\.
2168 size_t location =
2169 url.is_special() ? helpers::find_authority_delimiter_special(view)
2170 : helpers::find_authority_delimiter(view);
2171 std::string_view authority_view = view.substr(0, location);
2172 size_t end_of_authority = input_position + authority_view.size();
2173 // If c is U+0040 (@), then:
2174 if ((end_of_authority != input_size) &&
2175 (url_data[end_of_authority] == '@')) {
2176 // If atSignSeen is true, then prepend "%40" to buffer.
2177 if (at_sign_seen) {
2178 if (password_token_seen) {
2179 if constexpr (result_type_is_ada_url) {
2180 url.password += "%40";
2181 } else {
2182 url.append_base_password("%40");
2183 }
2184 } else {
2185 if constexpr (result_type_is_ada_url) {
2186 url.username += "%40";
2187 } else {
2188 url.append_base_username("%40");
2189 }
2190 }
2191 }
2192
2193 at_sign_seen = true;
2194
2195 if (!password_token_seen) {
2196 size_t password_token_location = authority_view.find(':');
2197 password_token_seen =
2198 password_token_location != std::string_view::npos;
2199
2200 if constexpr (store_values) {
2201 if (!password_token_seen) {
2202 if constexpr (result_type_is_ada_url) {
2203 url.username += unicode::percent_encode(
2204 authority_view,
2206 } else {
2207 url.append_base_username(unicode::percent_encode(
2208 authority_view,
2210 }
2211 } else {
2212 if constexpr (result_type_is_ada_url) {
2213 url.username += unicode::percent_encode(
2214 authority_view.substr(0, password_token_location),
2216 url.password += unicode::percent_encode(
2217 authority_view.substr(password_token_location + 1),
2219 } else {
2220 url.append_base_username(unicode::percent_encode(
2221 authority_view.substr(0, password_token_location),
2223 url.append_base_password(unicode::percent_encode(
2224 authority_view.substr(password_token_location + 1),
2226 }
2227 }
2228 }
2229 } else if constexpr (store_values) {
2230 if constexpr (result_type_is_ada_url) {
2231 url.password += unicode::percent_encode(
2233 } else {
2234 url.append_base_password(unicode::percent_encode(
2236 }
2237 }
2238 }
2239 // Otherwise, if one of the following is true:
2240 // - c is the EOF code point, U+002F (/), U+003F (?), or U+0023 (#)
2241 // - url is special and c is U+005C (\‍)
2242 else if (end_of_authority == input_size ||
2243 url_data[end_of_authority] == '/' ||
2244 url_data[end_of_authority] == '?' ||
2245 (url.is_special() && url_data[end_of_authority] == '\\')) {
2246 // If atSignSeen is true and authority_view is the empty string,
2247 // validation error, return failure.
2248 if (at_sign_seen && authority_view.empty()) {
2249 url.is_valid = false;
2250 return url;
2251 }
2253 break;
2254 }
2255 if (end_of_authority == input_size) {
2256 if constexpr (store_values) {
2257 if (fragment.has_value()) {
2258 url.update_unencoded_base_hash(*fragment);
2259 }
2260 }
2261 enforce_max_input_length();
2262 return url;
2263 }
2264 input_position = end_of_authority + 1;
2265 } while (true);
2266
2267 break;
2268 }
2270 ada_log("SPECIAL_RELATIVE_OR_AUTHORITY ",
2271 helpers::substring(url_data, input_position));
2272
2273 // If c is U+002F (/) and remaining starts with U+002F (/),
2274 // then set state to special authority ignore slashes state and increase
2275 // pointer by 1.
2276 if (url_data.substr(input_position, 2) == "//") {
2278 input_position += 2;
2279 } else {
2280 // Otherwise, validation error, set state to relative state and
2281 // decrease pointer by 1.
2283 }
2284
2285 break;
2286 }
2288 ada_log("PATH_OR_AUTHORITY ",
2289 helpers::substring(url_data, input_position));
2290
2291 // If c is U+002F (/), then set state to authority state.
2292 if ((input_position != input_size) &&
2293 (url_data[input_position] == '/')) {
2295 input_position++;
2296 } else {
2297 // Otherwise, set state to path state, and decrease pointer by 1.
2299 }
2300
2301 break;
2302 }
2304 ada_log("RELATIVE_SCHEME ",
2305 helpers::substring(url_data, input_position));
2306
2307 // Set url's scheme to base's scheme.
2308 url.copy_scheme(*base_url);
2309
2310 // If c is U+002F (/), then set state to relative slash state.
2311 if ((input_position != input_size) &&
2312 // NOLINTNEXTLINE(bugprone-branch-clone)
2313 (url_data[input_position] == '/')) {
2314 ada_log(
2315 "RELATIVE_SCHEME if c is U+002F (/), then set state to relative "
2316 "slash state");
2318 } else if (url.is_special() && (input_position != input_size) &&
2319 (url_data[input_position] == '\\')) {
2320 // Otherwise, if url is special and c is U+005C (\‍), validation error,
2321 // set state to relative slash state.
2322 ada_log(
2323 "RELATIVE_SCHEME if url is special and c is U+005C, validation "
2324 "error, set state to relative slash state");
2326 } else {
2327 ada_log("RELATIVE_SCHEME otherwise");
2328 // Set url's username to base's username, url's password to base's
2329 // password, url's host to base's host, url's port to base's port,
2330 // url's path to a clone of base's path, and url's query to base's
2331 // query.
2332 if constexpr (result_type_is_ada_url) {
2333 url.username = base_url->username;
2334 url.password = base_url->password;
2335 url.host = base_url->host;
2336 url.port = base_url->port;
2337 // cloning the base path includes cloning the has_opaque_path flag
2338 url.has_opaque_path = base_url->has_opaque_path;
2339 url.path = base_url->path;
2340 url.query = base_url->query;
2341 } else {
2342 url.update_base_authority(base_url->get_href(),
2343 base_url->get_components());
2344 url.update_host_to_base_host(base_url->get_hostname());
2345 url.update_base_port(base_url->retrieve_base_port());
2346 // cloning the base path includes cloning the has_opaque_path flag
2347 url.has_opaque_path = base_url->has_opaque_path;
2348 url.update_base_pathname(base_url->get_pathname());
2349 if (base_url->has_search()) {
2350 // get_search() returns "" for an empty query string (URL ends
2351 // with '?'). update_base_search("") would incorrectly clear the
2352 // query, so pass "?" to preserve the empty query distinction.
2353 auto s = base_url->get_search();
2354 url.update_base_search(s.empty() ? std::string_view("?") : s);
2355 }
2356 }
2357
2358 url.has_opaque_path = base_url->has_opaque_path;
2359
2360 // If c is U+003F (?), then set url's query to the empty string, and
2361 // state to query state.
2362 if ((input_position != input_size) &&
2363 (url_data[input_position] == '?')) {
2365 }
2366 // Otherwise, if c is not the EOF code point:
2367 else if (input_position != input_size) {
2368 // Set url's query to null.
2369 url.clear_search();
2370 if constexpr (result_type_is_ada_url) {
2371 // Shorten url's path.
2372 helpers::shorten_path(url.path, url.type);
2373 } else {
2374 std::string_view path = url.get_pathname();
2375 if (helpers::shorten_path(path, url.type)) {
2376 url.update_base_pathname(std::move(std::string(path)));
2377 }
2378 }
2379 // Set state to path state and decrease pointer by 1.
2381 break;
2382 }
2383 }
2384 input_position++;
2385 break;
2386 }
2387 case state::RELATIVE_SLASH: {
2388 ada_log("RELATIVE_SLASH ",
2389 helpers::substring(url_data, input_position));
2390
2391 // If url is special and c is U+002F (/) or U+005C (\‍), then:
2392 // NOLINTNEXTLINE(bugprone-branch-clone)
2393 if (url.is_special() && (input_position != input_size) &&
2394 (url_data[input_position] == '/' ||
2395 url_data[input_position] == '\\')) {
2396 // Set state to special authority ignore slashes state.
2398 }
2399 // Otherwise, if c is U+002F (/), then set state to authority state.
2400 else if ((input_position != input_size) &&
2401 (url_data[input_position] == '/')) {
2403 }
2404 // Otherwise, set
2405 // - url's username to base's username,
2406 // - url's password to base's password,
2407 // - url's host to base's host,
2408 // - url's port to base's port,
2409 // - state to path state, and then, decrease pointer by 1.
2410 else {
2411 if constexpr (result_type_is_ada_url) {
2412 url.username = base_url->username;
2413 url.password = base_url->password;
2414 url.host = base_url->host;
2415 url.port = base_url->port;
2416 } else {
2417 url.update_base_authority(base_url->get_href(),
2418 base_url->get_components());
2419 url.update_host_to_base_host(base_url->get_hostname());
2420 url.update_base_port(base_url->retrieve_base_port());
2421 }
2423 break;
2424 }
2425
2426 input_position++;
2427 break;
2428 }
2430 ada_log("SPECIAL_AUTHORITY_SLASHES ",
2431 helpers::substring(url_data, input_position));
2432
2433 // If c is U+002F (/) and remaining starts with U+002F (/),
2434 // then set state to special authority ignore slashes state and increase
2435 // pointer by 1.
2436 if (url_data.substr(input_position, 2) == "//") {
2437 input_position += 2;
2438 }
2439
2440 [[fallthrough]];
2441 }
2443 ada_log("SPECIAL_AUTHORITY_IGNORE_SLASHES ",
2444 helpers::substring(url_data, input_position));
2445
2446 // If c is neither U+002F (/) nor U+005C (\‍), then set state to
2447 // authority state and decrease pointer by 1.
2448 while ((input_position != input_size) &&
2449 ((url_data[input_position] == '/') ||
2450 (url_data[input_position] == '\\'))) {
2451 input_position++;
2452 }
2454
2455 break;
2456 }
2457 case state::QUERY: {
2458 ada_log("QUERY ", helpers::substring(url_data, input_position));
2459 if constexpr (store_values) {
2460 // Let queryPercentEncodeSet be the special-query percent-encode set
2461 // if url is special; otherwise the query percent-encode set.
2462 const uint8_t* query_percent_encode_set =
2465
2466 // Percent-encode after encoding, with encoding, buffer, and
2467 // queryPercentEncodeSet, and append the result to url's query.
2468 url.update_base_search(url_data.substr(input_position),
2469 query_percent_encode_set);
2470 ada_log("QUERY update_base_search completed ");
2471 if (fragment.has_value()) {
2472 url.update_unencoded_base_hash(*fragment);
2473 }
2474 }
2475 enforce_max_input_length();
2476 return url;
2477 }
2478 case state::HOST: {
2479 ada_log("HOST ", helpers::substring(url_data, input_position));
2480
2481 std::string_view host_view = url_data.substr(input_position);
2482 auto [location, found_colon] =
2483 helpers::get_host_delimiter_location(url.is_special(), host_view);
2484 input_position = (location != std::string_view::npos)
2485 ? input_position + location
2486 : input_size;
2487 // Otherwise, if c is U+003A (:) and insideBrackets is false, then:
2488 // Note: the 'found_colon' value is true if and only if a colon was
2489 // encountered while not inside brackets.
2490 if (found_colon) {
2491 // If buffer is the empty string, validation error, return failure.
2492 // Let host be the result of host parsing buffer with url is not
2493 // special.
2494 ada_log("HOST parsing ", host_view);
2495 if (!url.parse_host(host_view)) {
2496 return url;
2497 }
2498 ada_log("HOST parsing results in ", url.get_hostname());
2499 // Set url's host to host, buffer to the empty string, and state to
2500 // port state.
2502 input_position++;
2503 }
2504 // Otherwise, if one of the following is true:
2505 // - c is the EOF code point, U+002F (/), U+003F (?), or U+0023 (#)
2506 // - url is special and c is U+005C (\‍)
2507 // The get_host_delimiter_location function either brings us to
2508 // the colon outside of the bracket, or to one of those characters.
2509 else {
2510 // If url is special and host_view is the empty string, validation
2511 // error, return failure.
2512 if (host_view.empty() && url.is_special()) {
2513 url.is_valid = false;
2514 return url;
2515 }
2516 ada_log("HOST parsing ", host_view, " href=", url.get_href());
2517 // Let host be the result of host parsing host_view with url is not
2518 // special.
2519 if (host_view.empty()) {
2520 url.update_base_hostname("");
2521 } else if (!url.parse_host(host_view)) {
2522 return url;
2523 }
2524 ada_log("HOST parsing results in ", url.get_hostname(),
2525 " href=", url.get_href());
2526
2527 // Set url's host to host, and state to path start state.
2529 }
2530
2531 break;
2532 }
2533 case state::OPAQUE_PATH: {
2534 ada_log("OPAQUE_PATH ", helpers::substring(url_data, input_position));
2535 // Opaque path, query, and fragment are structurally always valid:
2536 // the parser would just percent-encode whatever is there. When we
2537 // are not storing values (can_parse), we can return immediately.
2538 // We must set has_opaque_path = true before returning so that when
2539 // this URL is used as an internal base inside can_parse, NO_SCHEME
2540 // correctly rejects relative inputs against an opaque-path base
2541 // (e.g. can_parse("", &"W:") must return false).
2542 if constexpr (!store_values) {
2543 url.has_opaque_path = true;
2544 return url;
2545 }
2546 std::string_view view = url_data.substr(input_position);
2547 // If c is U+003F (?), then set url's query to the empty string and
2548 // state to query state.
2549 size_t location = view.find('?');
2550 if (location != std::string_view::npos) {
2551 view.remove_suffix(view.size() - location);
2553 input_position += location + 1;
2554 } else {
2555 input_position = input_size + 1;
2556 }
2557 url.has_opaque_path = true;
2558
2559 // This is a really unlikely scenario in real world. We should not seek
2560 // to optimize it.
2561 if (view.ends_with(' ')) {
2562 std::string modified_view =
2563 std::string(view.substr(0, view.size() - 1)) + "%20";
2564 url.update_base_pathname(unicode::percent_encode(
2566 } else {
2567 url.update_base_pathname(unicode::percent_encode(
2569 }
2570 break;
2571 }
2572 case state::PORT: {
2573 ada_log("PORT ", helpers::substring(url_data, input_position));
2574 std::string_view port_view = url_data.substr(input_position);
2575 input_position += url.parse_port(port_view, true);
2576 if (!url.is_valid) {
2577 return url;
2578 }
2580 [[fallthrough]];
2581 }
2582 case state::PATH_START: {
2583 ada_log("PATH_START ", helpers::substring(url_data, input_position));
2584 // Path, query, and fragment are structurally always valid: the
2585 // parser would just percent-encode whatever is there. When we are
2586 // not storing values (can_parse), we can return immediately since
2587 // no subsequent state can invalidate the URL.
2588 if constexpr (!store_values) {
2589 return url;
2590 }
2591
2592 // If url is special, then:
2593 if (url.is_special()) {
2594 // Set state to path state.
2596
2597 // Optimization: Avoiding going into PATH state improves the
2598 // performance of urls ending with /.
2599 if (input_position == input_size) {
2600 if constexpr (store_values) {
2601 url.update_base_pathname("/");
2602 if (fragment.has_value()) {
2603 url.update_unencoded_base_hash(*fragment);
2604 }
2605 }
2606 enforce_max_input_length();
2607 return url;
2608 }
2609 // If c is neither U+002F (/) nor U+005C (\‍), then decrease pointer
2610 // by 1. We know that (input_position == input_size) is impossible
2611 // here, because of the previous if-check.
2612 if ((url_data[input_position] != '/') &&
2613 (url_data[input_position] != '\\')) {
2614 break;
2615 }
2616 }
2617 // Otherwise, if state override is not given and c is U+003F (?),
2618 // set url's query to the empty string and state to query state.
2619 else if ((input_position != input_size) &&
2620 (url_data[input_position] == '?')) {
2622 }
2623 // Otherwise, if c is not the EOF code point:
2624 else if (input_position != input_size) {
2625 // Set state to path state.
2627
2628 // If c is not U+002F (/), then decrease pointer by 1.
2629 if (url_data[input_position] != '/') {
2630 break;
2631 }
2632 }
2633
2634 input_position++;
2635 break;
2636 }
2637 case state::PATH: {
2638 ada_log("PATH ", helpers::substring(url_data, input_position));
2639 // Path, query, and fragment are structurally always valid: the
2640 // parser would just percent-encode whatever is there. When we are
2641 // not storing values (can_parse), we can return immediately since
2642 // no subsequent state can invalidate the URL.
2643 if constexpr (!store_values) {
2644 return url;
2645 }
2646 std::string_view view = url_data.substr(input_position);
2647
2648 // Most time, we do not need percent encoding.
2649 // Furthermore, we can immediately locate the '?'.
2650 size_t locofquestionmark = view.find('?');
2651 if (locofquestionmark != std::string_view::npos) {
2653 view.remove_suffix(view.size() - locofquestionmark);
2654 input_position += locofquestionmark + 1;
2655 } else {
2656 input_position = input_size + 1;
2657 }
2658 if constexpr (store_values) {
2659 if constexpr (result_type_is_ada_url) {
2660 helpers::parse_prepared_path(view, url.type, url.path);
2661 } else {
2662 url.consume_prepared_path(view);
2663 ADA_ASSERT_TRUE(url.validate());
2664 }
2665 }
2666 break;
2667 }
2668 case state::FILE_SLASH: {
2669 ada_log("FILE_SLASH ", helpers::substring(url_data, input_position));
2670
2671 // If c is U+002F (/) or U+005C (\‍), then:
2672 if ((input_position != input_size) &&
2673 (url_data[input_position] == '/' ||
2674 url_data[input_position] == '\\')) {
2675 ada_log("FILE_SLASH c is U+002F or U+005C");
2676 // Set state to file host state.
2678 input_position++;
2679 } else {
2680 ada_log("FILE_SLASH otherwise");
2681 // If base is non-null and base's scheme is "file", then:
2682 // Note: it is unsafe to do base_url->scheme unless you know that
2683 // base_url_has_value() is true.
2684 if (base_url != nullptr && base_url->type == scheme::type::FILE) {
2685 // Set url's host to base's host.
2686 if constexpr (result_type_is_ada_url) {
2687 url.host = base_url->host;
2688 } else {
2689 url.update_host_to_base_host(base_url->get_host());
2690 }
2691 // If the code point substring from pointer to the end of input does
2692 // not start with a Windows drive letter and base's path[0] is a
2693 // normalized Windows drive letter, then append base's path[0] to
2694 // url's path.
2695 if (!base_url->get_pathname().empty()) {
2697 url_data.substr(input_position))) {
2698 std::string_view first_base_url_path =
2699 base_url->get_pathname().substr(1);
2700 size_t loc = first_base_url_path.find('/');
2701 if (loc != std::string_view::npos) {
2702 helpers::resize(first_base_url_path, loc);
2703 }
2705 first_base_url_path)) {
2706 if constexpr (result_type_is_ada_url) {
2707 url.path += '/';
2708 url.path += first_base_url_path;
2709 } else {
2710 url.append_base_pathname(
2711 helpers::concat("/", first_base_url_path));
2712 }
2713 }
2714 }
2715 }
2716 }
2717
2718 // Set state to path state, and decrease pointer by 1.
2720 }
2721
2722 break;
2723 }
2724 case state::FILE_HOST: {
2725 ada_log("FILE_HOST ", helpers::substring(url_data, input_position));
2726 std::string_view view = url_data.substr(input_position);
2727
2728 size_t location = view.find_first_of("/\\?");
2729 std::string_view file_host_buffer = view.substr(
2730 0, (location != std::string_view::npos) ? location : view.size());
2731
2732 if (checkers::is_windows_drive_letter(file_host_buffer)) {
2734 } else if (file_host_buffer.empty()) {
2735 // Set url's host to the empty string.
2736 if constexpr (result_type_is_ada_url) {
2737 url.host = "";
2738 } else {
2739 url.update_base_hostname("");
2740 }
2741 // Set state to path start state.
2743 } else {
2744 size_t consumed_bytes = file_host_buffer.size();
2745 input_position += consumed_bytes;
2746 // Let host be the result of host parsing buffer with url is not
2747 // special.
2748 if (!url.parse_host(file_host_buffer)) {
2749 return url;
2750 }
2751
2752 if constexpr (result_type_is_ada_url) {
2753 // If host is "localhost", then set host to the empty string.
2754 if (url.host.has_value() && url.host.value() == "localhost") {
2755 url.host = "";
2756 }
2757 } else {
2758 if (url.get_hostname() == "localhost") {
2759 url.update_base_hostname("");
2760 }
2761 }
2762
2763 // Set buffer to the empty string and state to path start state.
2765 }
2766
2767 break;
2768 }
2769 case state::FILE: {
2770 ada_log("FILE ", helpers::substring(url_data, input_position));
2771 std::string_view file_view = url_data.substr(input_position);
2772
2773 url.set_protocol_as_file();
2774 if constexpr (result_type_is_ada_url) {
2775 // Set url's host to the empty string.
2776 url.host = "";
2777 } else {
2778 url.update_base_hostname("");
2779 }
2780 // If c is U+002F (/) or U+005C (\‍), then:
2781 if (input_position != input_size &&
2782 (url_data[input_position] == '/' ||
2783 url_data[input_position] == '\\')) {
2784 ada_log("FILE c is U+002F or U+005C");
2785 // Set state to file slash state.
2787 }
2788 // Otherwise, if base is non-null and base's scheme is "file":
2789 else if (base_url != nullptr && base_url->type == scheme::type::FILE) {
2790 // Set url's host to base's host, url's path to a clone of base's
2791 // path, and url's query to base's query.
2792 ada_log("FILE base non-null");
2793 if constexpr (result_type_is_ada_url) {
2794 url.host = base_url->host;
2795 url.path = base_url->path;
2796 url.query = base_url->query;
2797 } else {
2798 url.update_host_to_base_host(base_url->get_hostname());
2799 url.update_base_pathname(base_url->get_pathname());
2800 if (base_url->has_search()) {
2801 // get_search() returns "" for an empty query string (URL ends
2802 // with '?'). update_base_search("") would incorrectly clear the
2803 // query, so pass "?" to preserve the empty query distinction.
2804 auto s = base_url->get_search();
2805 url.update_base_search(s.empty() ? std::string_view("?") : s);
2806 }
2807 }
2808 url.has_opaque_path = base_url->has_opaque_path;
2809
2810 // If c is U+003F (?), then set url's query to the empty string and
2811 // state to query state.
2812 if (input_position != input_size && url_data[input_position] == '?') {
2814 }
2815 // Otherwise, if c is not the EOF code point:
2816 else if (input_position != input_size) {
2817 // Set url's query to null.
2818 url.clear_search();
2819 // If the code point substring from pointer to the end of input does
2820 // not start with a Windows drive letter, then shorten url's path.
2821 if (!checkers::is_windows_drive_letter(file_view)) {
2822 if constexpr (result_type_is_ada_url) {
2823 helpers::shorten_path(url.path, url.type);
2824 } else {
2825 std::string_view path = url.get_pathname();
2826 if (helpers::shorten_path(path, url.type)) {
2827 url.update_base_pathname(std::move(std::string(path)));
2828 }
2829 }
2830 }
2831 // Otherwise:
2832 else {
2833 // Set url's path to an empty list.
2834 url.clear_pathname();
2835 }
2836
2837 // Set state to path state and decrease pointer by 1.
2839 break;
2840 }
2841 }
2842 // Otherwise, set state to path state, and decrease pointer by 1.
2843 else {
2844 ada_log("FILE go to path");
2846 break;
2847 }
2848
2849 input_position++;
2850 break;
2851 }
2852 default:
2853 unreachable();
2854 }
2855 }
2856 if constexpr (store_values) {
2857 if (fragment.has_value()) {
2858 url.update_unencoded_base_hash(*fragment);
2859 }
2860 }
2861 enforce_max_input_length();
2862 return url;
2863}
2864
2865template bool try_parse_simple_absolute<url>(std::string_view, url&);
2866template bool try_parse_simple_absolute<url_aggregator>(std::string_view,
2868template bool finish_simple_absolute_with_port<url>(std::string_view, url&,
2869 ada::scheme::type, uint32_t,
2870 size_t, size_t, size_t,
2871 bool);
2873 std::string_view, url_aggregator&, ada::scheme::type, uint32_t, size_t,
2874 size_t, size_t, bool);
2875template bool try_parse_simple_relative<url>(std::string_view, const url&,
2876 url&);
2877template bool try_parse_simple_relative<url_aggregator>(std::string_view,
2878 const url_aggregator&,
2880
2881template url parse_url_impl<url, true>(std::string_view user_input,
2882 const url* base_url = nullptr);
2884 std::string_view user_input, const url_aggregator* base_url = nullptr);
2886 std::string_view user_input, const url_aggregator* base_url = nullptr);
2887
2888template <class result_type>
2889result_type parse_url(std::string_view user_input,
2890 const result_type* base_url) {
2891 return parse_url_impl<result_type, true>(user_input, base_url);
2892}
2893
2894template url parse_url<url>(std::string_view user_input,
2895 const url* base_url = nullptr);
2897 std::string_view user_input, const url_aggregator* base_url = nullptr);
2898} // namespace ada::parser
Definitions of the character sets used by unicode functions.
Definitions for URL specific checkers used within Ada.
Cross-platform compiler macros and common definitions.
#define ADA_ASSERT_TRUE(COND)
#define ada_never_inline
Definition common_defs.h:86
#define ada_really_inline
Definition common_defs.h:85
User-facing functions for URL parsing and manipulation.
constexpr uint8_t QUERY_PERCENT_ENCODE[32]
constexpr uint8_t SPECIAL_QUERY_PERCENT_ENCODE[32]
constexpr uint8_t C0_CONTROL_PERCENT_ENCODE[32]
constexpr uint8_t USERINFO_PERCENT_ENCODE[32]
constexpr bool last_label_may_be_a_number(std::string_view view) noexcept
constexpr bool is_normalized_windows_drive_letter(std::string_view input) noexcept
constexpr bool is_windows_drive_letter(std::string_view input) noexcept
constexpr bool is_alpha(char x) noexcept
constexpr std::array< uint8_t, 256 > k_host_class
Definition parser.cpp:71
bool path_has_dot_segment(std::string_view path) noexcept
Definition parser.cpp:979
ADA_PARSER_SIMD bool scan_plain_host(const uint8_t *b, size_t start, size_t len, size_t &end, bool &has_upper, bool &has_x) noexcept
Definition parser.cpp:421
ADA_PARSER_SIMD void scan_query_run(const uint8_t *b, size_t &i, size_t len) noexcept
Definition parser.cpp:967
constexpr std::array< uint8_t, 256 > k_path
Definition parser.cpp:91
constexpr std::array< uint8_t, 256 > k_query
Definition parser.cpp:112
ada_really_inline int trailing_zeroes64(uint64_t input_num) noexcept
Definition parser.cpp:228
ada_really_inline int trailing_zeroes32(uint32_t input_num) noexcept
Definition parser.cpp:218
ADA_PARSER_SIMD void scan_hash_run(const uint8_t *b, size_t &i, size_t len) noexcept
Definition parser.cpp:972
ada_really_inline bool authority_has_at(const uint8_t *p, size_t host_start, size_t n) noexcept
Definition parser.cpp:357
constexpr nibble_tables k_query_nibbles
Definition parser.cpp:192
ADA_PARSER_SIMD void scan_path_run(const uint8_t *b, size_t &i, size_t len, bool &maybe_dot_segment) noexcept
Definition parser.cpp:657
ada_really_inline uint32_t port_decimal_digit_count(uint32_t port) noexcept
Definition parser.cpp:200
constexpr std::array< uint8_t, 256 > k_hash
Definition parser.cpp:129
consteval nibble_tables make_stop_nibble_tables(const std::array< uint8_t, 256 > &cls)
Definition parser.cpp:155
ada_really_inline void append_canonical_port(std::string &buffer, uint32_t port)
Definition parser.cpp:209
ada_really_inline void note_possible_dot_segment(const uint8_t *b, size_t pos, size_t run_start, bool &maybe_dot_segment) noexcept
Definition parser.cpp:600
Internal URL parsing implementation.
Definition parser-inl.h:18
template url parse_url< url >(std::string_view user_input, const url *base_url)
result_type parse_url(std::string_view user_input, const result_type *base_url=nullptr)
Definition parser.cpp:2889
template bool try_parse_simple_relative< url_aggregator >(std::string_view, const url_aggregator &, url_aggregator &)
template bool try_parse_simple_relative< url >(std::string_view, const url &, url &)
template url parse_url_impl< url, true >(std::string_view user_input, const url *base_url)
template bool try_parse_simple_absolute< url >(std::string_view, url &)
template url_aggregator parse_url_impl< url_aggregator, false >(std::string_view user_input, const url_aggregator *base_url)
template bool finish_simple_absolute_with_port< url >(std::string_view, url &, ada::scheme::type, uint32_t, size_t, size_t, size_t, bool)
template bool finish_simple_absolute_with_port< url_aggregator >(std::string_view, url_aggregator &, ada::scheme::type, uint32_t, size_t, size_t, size_t, bool)
template url_aggregator parse_url< url_aggregator >(std::string_view user_input, const url_aggregator *base_url)
template url_aggregator parse_url_impl< url_aggregator, true >(std::string_view user_input, const url_aggregator *base_url)
result_type parse_url_impl(std::string_view user_input, const result_type *base_url=nullptr)
Definition parser.cpp:1841
template bool try_parse_simple_absolute< url_aggregator >(std::string_view, url_aggregator &)
type
Enumeration of URL scheme types.
Definition scheme.h:43
@ NOT_SPECIAL
Definition scheme.h:45
constexpr uint16_t get_special_port(std::string_view scheme) noexcept
Definition scheme-inl.h:94
@ DEFAULT
Definition url_base.h:30
state
States in the URL parsing state machine.
Definition state.h:27
@ SPECIAL_RELATIVE_OR_AUTHORITY
Definition state.h:101
@ FILE_SLASH
Definition state.h:81
@ SCHEME
Definition state.h:41
@ SPECIAL_AUTHORITY_SLASHES
Definition state.h:96
@ FILE_HOST
Definition state.h:76
@ OPAQUE_PATH
Definition state.h:121
@ RELATIVE_SLASH
Definition state.h:66
@ NO_SCHEME
Definition state.h:51
@ PATH_START
Definition state.h:116
@ RELATIVE_SCHEME
Definition state.h:61
@ SPECIAL_AUTHORITY_IGNORE_SLASHES
Definition state.h:91
@ SCHEME_START
Definition state.h:36
@ AUTHORITY
Definition state.h:31
@ PATH_OR_AUTHORITY
Definition state.h:86
ada_warn_unused std::string_view to_string(encoding_type type)
uint32_t get_max_input_length()
void unreachable()
#define ADA_SCAN_STOP_RUN(nibbles, cls, unused_sse2_stop)
Definition parser.cpp:957
#define ADA_PARSER_SSSE3_FN
Definition parser.cpp:54
#define ADA_PARSER_SIMD
Definition parser.cpp:53
Definitions for the URL scheme.
Memory-efficient URL representation using a single buffer.
ada_really_inline constexpr bool is_special() const noexcept
bool is_valid
Definition url_base.h:58
bool has_opaque_path
Definition url_base.h:64
static constexpr uint32_t omitted
Represents a parsed URL with individual string components.
Definition url.h:64
std::string get_protocol() const
Definition url.cpp:565
constexpr std::string_view get_pathname() const noexcept
Definition url-inl.h:51
size_t get_href_size() const noexcept
Definition url-inl.h:283
std::string get_hostname() const
Definition url.cpp:587
ada_really_inline std::string get_href() const
Definition url-inl.h:196
Definitions for unicode operations.
Definitions for all unicode specific functions.
Declaration for the ada::url class.
Inline functions for url aggregator.
Declaration for the ada::url_aggregator class.