Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
url_pattern_list.cpp
Go to the documentation of this file.
1
16#include "ada.h"
18
19#include <algorithm>
20#include <array>
21#include <bit>
22#include <cstdint>
23#include <cstring>
24#include <limits>
25#include <span>
26#include <string_view>
27#include <utility>
28#include <vector>
29
30#if ADA_INCLUDE_URL_PATTERN
31
32namespace ada::url_pattern_list_compiler {
33
34namespace {
35
36using url_pattern_list_detail::compiled_routes;
37using url_pattern_list_detail::edge_record;
38using url_pattern_list_detail::hash_record;
39using url_pattern_list_detail::node_record;
40using url_pattern_list_detail::route_mode;
41using url_pattern_list_detail::route_record;
42using url_pattern_list_detail::segment_record;
43using url_pattern_list_limits::max_captures_per_route;
44using url_pattern_list_limits::max_trie_pattern_segments;
45
46// The tables under construction, one vector per section; packed into the
47// single arena of compiled_routes at the end of the build.
48struct builder_tables {
49 std::vector<node_record> nodes{};
50 std::vector<hash_record> hashes{};
51 std::vector<edge_record> edges{};
52 std::vector<uint8_t> slots{};
53 std::vector<char> blob{};
54 std::vector<route_record> routes{};
55 std::vector<segment_record> segments{};
56 std::vector<uint32_t> aux{};
57 std::vector<uint16_t> root_index{};
58 uint32_t n_aux_all = 0;
59};
60
61// Witness plan for single-string tables: nibbles 0..2 hold witness ids
62// (distinct ids first, remaining slots duplicating id 0 so the runtime
63// gather is fixed-shape and branch-free); bits 12..14 are metadata.
64constexpr uint16_t pack_witness_plan(const uint8_t* ids, uint32_t n_ids,
65 bool use_len) noexcept {
66 uint16_t w = 0;
67 for (uint32_t j = 0; j < 3; j++) {
68 w = static_cast<uint16_t>(
69 w | static_cast<uint16_t>((j < n_ids ? ids[j] : ids[0]) & 15u)
70 << (4 * j));
71 }
72 w = static_cast<uint16_t>(w | static_cast<uint16_t>(n_ids << 12));
73 if (use_len) {
74 w = static_cast<uint16_t>(w | static_cast<uint16_t>(1) << 14);
75 }
76 return w;
77}
78
79// Bytes [from, min(from + 8, len)) of a key, packed little-endian and
80// zero-padded; the build-time twin of the matcher's window load.
81constexpr uint64_t pack_window_le(const char* p, uint32_t len,
82 uint32_t from) noexcept {
83 uint64_t x = 0;
84 for (uint32_t j = 0; j < 8 && from + j < len; j++) {
85 x |= static_cast<uint64_t>(static_cast<uint8_t>(p[from + j])) << (8 * j);
86 }
87 return x;
88}
89
90// Deterministic RNG for the multiplier search (splitmix64).
91struct splitmix64 {
92 uint64_t state;
93 constexpr explicit splitmix64(uint64_t seed) noexcept : state(seed) {}
94 constexpr uint64_t next() noexcept {
95 uint64_t z = (state += 0x9E3779B97F4A7C15ull);
96 z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ull;
97 z = (z ^ (z >> 27)) * 0x94D049BB133111EBull;
98 return z ^ (z >> 31);
99 }
100};
101
102struct transient_node { // build-time trie (views into route segment storage)
103 std::vector<std::pair<std::string_view, int32_t>> kids{};
104 int32_t param = -1;
105 int32_t wild_route = -1;
106 int32_t terminal = -1;
107};
108
109constexpr unsigned ceil_log2(size_t n) noexcept {
110 unsigned b = 0;
111 while ((size_t{1} << b) < n) {
112 b++;
113 }
114 return b;
115}
116
117// Starting table size for n keys: load factor <= ~1/4, loosened as n grows
118// so the multiplier search still lands inside the budget.
119constexpr unsigned initial_slot_bits(size_t n) noexcept {
120 unsigned headroom = 1;
121 if (n > 64) {
122 headroom = 3;
123 } else if (n > 8) {
124 headroom = 2;
125 }
126 return ceil_log2(n) + headroom;
127}
128
129bool find_multiplier(const std::vector<uint64_t>& proj, unsigned b0,
130 uint64_t& multiplier_out, uint8_t& bits_out) {
131 const size_t n = proj.size();
132 for (unsigned b = b0; b <= 12; b++) {
133 std::vector<uint32_t> stamp(size_t{1} << b, 0);
134 splitmix64 rng(0x14C0FFEEull + b);
135 for (uint32_t t = 1; t <= 4000; t++) {
136 const uint64_t m = rng.next() | 1;
137 bool ok = true;
138 for (size_t i = 0; i < n; i++) {
139 const uint64_t s = (proj[i] * m) >> (64 - b);
140 if (stamp[s] == t) {
141 ok = false;
142 break;
143 }
144 stamp[s] = t;
145 }
146 if (ok) {
147 multiplier_out = m;
148 bits_out = static_cast<uint8_t>(b);
149 return true;
150 }
151 }
152 }
153 return false;
154}
155
156// Emits a perfect-hash slot table for `proj` at the end of `slots`. Returns
157// false if the search failed, in which case nothing was appended and the
158// caller demotes that table to a linear scan.
159bool emit_slot_table(const std::vector<uint64_t>& proj,
160 std::vector<uint8_t>& slots, uint64_t& multiplier_out,
161 uint8_t& bits_out, uint32_t& base_out) {
162 if (!find_multiplier(proj, initial_slot_bits(proj.size()), multiplier_out,
163 bits_out)) {
164 return false;
165 }
166 base_out = static_cast<uint32_t>(slots.size());
167 slots.resize(slots.size() + (size_t{1} << bits_out), 0xFF);
168 for (size_t i = 0; i < proj.size(); i++) {
169 slots[base_out +
170 url_pattern_list_detail::slot_of(proj[i], multiplier_out, bits_out)] =
171 static_cast<uint8_t>(i);
172 }
173 return true;
174}
175
176// Advances `c` to the next k-combination of {0..n-1} in lexicographic
177// order; false once the last one has been visited.
178template <size_t N>
179constexpr bool next_combination(std::array<uint32_t, N>& c, uint32_t k,
180 uint32_t n) noexcept {
181 int32_t j = static_cast<int32_t>(k) - 1;
182 while (j >= 0 &&
183 c[static_cast<uint32_t>(j)] == n - k + static_cast<uint32_t>(j)) {
184 j--;
185 }
186 if (j < 0) {
187 return false;
188 }
189 c[static_cast<uint32_t>(j)]++;
190 for (uint32_t t = static_cast<uint32_t>(j) + 1; t < k; t++) {
191 c[t] = c[t - 1] + 1;
192 }
193 return true;
194}
195
196// Witness-subset search over the given id alphabet, cost-ordered: fewest
197// distinct witness ids first (the length is always packed -- it is free).
198// The first injective subset wins.
199bool find_witness_plan(
200 const std::vector<std::pair<std::string_view, int32_t>>& kids,
201 const uint8_t* alphabet, uint32_t n_alpha, uint32_t max_reads,
202 uint16_t& plan_out) {
203 const size_t n = kids.size();
204 auto injective = [&](uint16_t wp) { // sort + adjacent compare
205 std::vector<uint64_t> proj(n);
206 for (size_t i = 0; i < n; i++) {
207 proj[i] = url_pattern_list_detail::project(
208 kids[i].first.data(), static_cast<uint32_t>(kids[i].first.size()),
209 wp);
210 }
211 std::sort(proj.begin(), proj.end());
212 for (size_t i = 1; i < n; i++) {
213 if (proj[i] == proj[i - 1]) {
214 return false;
215 }
216 }
217 return true;
218 };
219 for (uint32_t k = 1; k <= max_reads && k <= n_alpha; k++) {
220 std::array<uint32_t, 3> c{0, 1, 2};
221 do {
222 uint8_t ids[3] = {0, 0, 0};
223 for (uint32_t j = 0; j < k; j++) {
224 ids[j] = alphabet[c[j]];
225 }
226 const uint16_t wp = pack_witness_plan(ids, k, true);
227 if (injective(wp)) {
228 plan_out = wp;
229 return true;
230 }
231 } while (next_combination(c, k, n_alpha));
232 }
233 return false;
234}
235
236// ---- build stages ----------------------------------------------------------
237
238// Segment trie over the trie-mode routes. Priority is resolved here, at
239// build, into each node's fixed decision order (static children -> param ->
240// wildcard); a DFS in that order returns the match with the
241// lexicographically minimal kind sequence. Duplicate patterns collapse onto
242// one slot: an occupied slot is never overwritten, so the smallest route
243// index survives.
244std::vector<transient_node> build_trie(const std::vector<route_info>& routes) {
245 std::vector<transient_node> t(1);
246 for (size_t i = 0; i < routes.size(); i++) {
247 const route_info& rt = routes[i];
248 if (rt.mode != route_mode::trie) {
249 continue;
250 }
251 int32_t cur = 0;
252 for (const route_segment& ps : rt.segments) {
253 if (ps.kind == segment_kind::literal) {
254 int32_t nxt = -1;
255 for (auto& kv : t[static_cast<size_t>(cur)].kids) {
256 if (kv.first == ps.text) {
257 nxt = kv.second;
258 break;
259 }
260 }
261 if (nxt < 0) {
262 nxt = static_cast<int32_t>(t.size());
263 t[static_cast<size_t>(cur)].kids.emplace_back(ps.text, nxt);
264 t.emplace_back();
265 }
266 cur = nxt;
267 } else if (ps.kind == segment_kind::param) {
268 if (t[static_cast<size_t>(cur)].param < 0) {
269 t[static_cast<size_t>(cur)].param = static_cast<int32_t>(t.size());
270 t.emplace_back();
271 }
272 cur = t[static_cast<size_t>(cur)].param;
273 } else { // wildcard (classification guarantees final)
274 if (t[static_cast<size_t>(cur)].wild_route < 0) {
275 t[static_cast<size_t>(cur)].wild_route = static_cast<int32_t>(i);
276 }
277 cur = -1;
278 break;
279 }
280 }
281 if (cur >= 0 && t[static_cast<size_t>(cur)].terminal < 0) {
282 t[static_cast<size_t>(cur)].terminal = static_cast<int32_t>(i);
283 }
284 }
285 // The root's children are sorted by first byte so that the first-byte
286 // index can address each run of same-byte children as one contiguous
287 // block of edges.
288 std::stable_sort(
289 t[0].kids.begin(), t[0].kids.end(), [](const auto& a, const auto& b) {
290 const int ka = a.first.empty() ? -1 : static_cast<uint8_t>(a.first[0]);
291 const int kb = b.first.empty() ? -1 : static_cast<uint8_t>(b.first[0]);
292 return ka < kb;
293 });
294 return t;
295}
296
297// Per-route records: priority data, capture positions (so extracting params
298// at match time is a fixed walk over param_positions), regexp ordinals.
299void compile_route_records(builder_tables& r,
300 const std::vector<route_info>& routes) {
301 r.routes.resize(routes.size());
302 int32_t n_regexp = 0;
303 for (size_t i = 0; i < routes.size(); i++) {
304 const route_info& rt = routes[i];
305 route_record& rm = r.routes[i];
306 rm.kind_sequence = rt.kind_sequence;
307 rm.kind_length = rt.kind_length;
308 rm.mode = rt.mode;
309 rm.wild = rt.has_wildcard ? 1 : 0;
310 if (rt.mode == route_mode::regexp) {
311 rm.regexp_component = n_regexp++;
312 continue;
313 }
314 if (rt.mode != route_mode::trie) {
315 continue; // capture positions are only read for trie-answered routes
316 }
317 for (size_t s = 0; s < rt.segments.size(); s++) {
318 if (rt.segments[s].kind == segment_kind::param) {
319 // Classification guarantees n_params <= max_captures_per_route for
320 // trie-mode routes.
321 rm.param_positions[rm.n_params++] = static_cast<uint8_t>(s);
322 }
323 }
324 }
325}
326
327// BFS layout: assign final node ids breadth-first so each node's static
328// children occupy a contiguous block of edges[]. Returns the transient-node
329// id per final id.
330std::vector<int32_t> layout_nodes(builder_tables& r,
331 const std::vector<transient_node>& t) {
332 std::vector<int32_t> order; // transient id per final id
333 order.push_back(0);
334 r.nodes.resize(1);
335 for (size_t head = 0; head < order.size(); head++) {
336 const transient_node& tn = t[static_cast<size_t>(order[head])];
337 node_record nd{};
338 nd.wild_route = tn.wild_route;
339 nd.terminal_route = tn.terminal;
340 nd.first_child = static_cast<int32_t>(r.edges.size());
341 nd.n_static = static_cast<uint16_t>(tn.kids.size());
342 const size_t id_base = order.size(); // children take the next BFS ids
343 for (size_t ci = 0; ci < tn.kids.size(); ci++) {
344 const std::string_view k = tn.kids[ci].first;
345 edge_record e{};
346 e.key_length = static_cast<uint16_t>(k.size());
347 e.key_offset = static_cast<uint32_t>(r.blob.size());
348 r.blob.insert(r.blob.end(), k.begin(), k.end());
349 e.prefix = pack_window_le(k.data(), static_cast<uint32_t>(k.size()), 0);
350 e.suffix = pack_window_le(
351 k.data(), static_cast<uint32_t>(k.size()),
352 k.size() >= 8 ? static_cast<uint32_t>(k.size()) - 8 : 0);
353 e.node = static_cast<int32_t>(id_base + ci);
354 r.edges.push_back(e);
355 }
356 for (size_t ci = 0; ci < tn.kids.size(); ci++) {
357 order.push_back(tn.kids[ci].second);
358 }
359 if (tn.param >= 0) {
360 nd.param_child = static_cast<int32_t>(order.size());
361 order.push_back(tn.param);
362 }
363 nd.has_alternative = (nd.param_child >= 0 || nd.wild_route >= 0) ? 1 : 0;
364 r.nodes.resize(order.size());
365 r.nodes[head] = nd;
366 }
367 return order;
368}
369
370// Root first-byte index: a 256-entry table from the first byte of the
371// input's first segment to the first root child starting with it (the
372// children are sorted by first byte). Built for a root with at least three
373// children; a run of same-byte children longer than max_direct_children, or
374// an empty key, falls back to the regular ladder. Returns true when the
375// index was emitted.
376bool build_root_index(builder_tables& r, const transient_node& root) {
377 const size_t nk = root.kids.size();
378 if (nk < 3) {
379 return false;
380 }
381 std::array<uint16_t, 256> index{};
382 index.fill(0xFFFF);
383 std::array<uint32_t, 256> run{};
384 for (size_t ci = 0; ci < nk; ci++) {
385 if (root.kids[ci].first.empty()) {
386 return false; // an empty key has no first byte: regular ladder
387 }
388 const uint8_t b = static_cast<uint8_t>(root.kids[ci].first[0]);
389 if (index[b] == 0xFFFF) {
390 index[b] = static_cast<uint16_t>(ci);
391 }
392 if (++run[b] > max_direct_children) {
393 return false;
394 }
395 }
396 r.root_index.assign(index.begin(), index.end());
397 return true;
398}
399
400// Per-node dispatch ladder, chosen by static child count: 0 none, up to
401// max_direct_children direct compares, then projection over a restricted
402// alphabet (escalating to the full alphabet); linear demotion when a search
403// fails or when the fanout exceeds max_dispatch_table_entries. The root
404// gets the first-byte index when its fanout allows. Never incorrect, only
405// slower.
406void compile_dispatch(builder_tables& r, const std::vector<transient_node>& t,
407 const std::vector<int32_t>& order) {
408 for (size_t ni = 0; ni < r.nodes.size(); ni++) {
409 node_record& nd = r.nodes[ni];
410 const transient_node& tn = t[static_cast<size_t>(order[ni])];
411 const size_t nk = tn.kids.size();
412 if (nk == 0) {
413 nd.dispatch = 0;
414 continue;
415 }
416 if (ni == 0 && build_root_index(r, tn)) {
417 nd.dispatch = 4;
418 continue;
419 }
420 if (nk <= max_direct_children) {
421 nd.dispatch = 1;
422 continue;
423 }
424 if (nk > max_dispatch_table_entries) {
425 nd.dispatch = 3; // slot ordinals are 8-bit; linear scan stays correct
426 continue;
427 }
428 uint16_t wp = 0;
429 bool found = false;
430 if (nk <= 16) {
431 constexpr uint8_t alpha_small[2] = {0, 8}; // s[0], s[len - 1]
432 found = find_witness_plan(tn.kids, alpha_small, 2, 2, wp);
433 }
434 if (!found) { // full alphabet (also the escalation path for <= 16)
435 uint8_t alpha_full[16] = {0, 1, 2, 3, 4, 5, 6, 7,
436 8, 9, 10, 11, 12, 13, 14, 15};
437 found = find_witness_plan(tn.kids, alpha_full, 16, 3, wp);
438 }
439 hash_record h{};
440 if (found) {
441 std::vector<uint64_t> proj(nk);
442 for (size_t i = 0; i < nk; i++) {
443 proj[i] = url_pattern_list_detail::project(
444 tn.kids[i].first.data(),
445 static_cast<uint32_t>(tn.kids[i].first.size()), wp);
446 }
447 found = emit_slot_table(proj, r.slots, h.multiplier, h.slot_bits,
448 h.slot_base);
449 }
450 if (!found) {
451 nd.dispatch = 3; // demoted: correct, slower
452 continue;
453 }
454 nd.dispatch = 2;
455 h.witness_plan = wp;
456 nd.hash_index = static_cast<uint32_t>(r.hashes.size());
457 r.hashes.push_back(h);
458 }
459}
460
461// Pure-leaf edge encoding, last: a child that is a pure leaf (terminal
462// route only) is encoded as -2 - route directly in the edge, so the walk
463// finishes or dead-ends there without loading the leaf node. -1 keeps
464// meaning "absent" for param_child.
465void encode_leaf_shortcuts(builder_tables& r) {
466 auto pure_leaf = [&](int32_t ni) {
467 const node_record& nd = r.nodes[static_cast<size_t>(ni)];
468 return nd.n_static == 0 && nd.param_child < 0 && nd.wild_route < 0 &&
469 nd.terminal_route >= 0;
470 };
471 for (auto& e : r.edges) {
472 if (pure_leaf(e.node)) {
473 e.node = -2 - r.nodes[static_cast<size_t>(e.node)].terminal_route;
474 }
475 }
476 for (auto& nd : r.nodes) {
477 if (nd.param_child >= 0 && pure_leaf(nd.param_child)) {
478 nd.param_child =
479 -2 - r.nodes[static_cast<size_t>(nd.param_child)].terminal_route;
480 }
481 }
482}
483
484// Segment table: every non-regexp route's segments (kind plus literal text
485// in the blob), so the sequential fallback beyond the fast-path limits can
486// match any route without the compiler's types; for regexp routes, the
487// anchored literal prefix the matcher checks before running the provider.
488void build_segment_table(builder_tables& r,
489 const std::vector<route_info>& routes) {
490 for (size_t i = 0; i < routes.size(); i++) {
491 const route_info& rt = routes[i];
492 route_record& rm = r.routes[i];
493 rm.segment_first = static_cast<uint32_t>(r.segments.size());
494 rm.segment_count = static_cast<uint32_t>(rt.segments.size());
495 for (const route_segment& s : rt.segments) {
496 segment_record sr{};
497 sr.kind = static_cast<uint8_t>(s.kind);
498 if (s.kind == segment_kind::literal) {
499 sr.text_offset = static_cast<uint32_t>(r.blob.size());
500 sr.text_length = static_cast<uint32_t>(s.text.size());
501 r.blob.insert(r.blob.end(), s.text.begin(), s.text.end());
502 }
503 r.segments.push_back(sr);
504 }
505 }
506}
507
508// Could some pathname match both a fast-path route `w` (full segment
509// information) and route `c`? Conservative: true unless a literal conflict
510// or a segment-count conflict proves otherwise. For a regexp-mode `c`,
511// segments are what approximate_kind_sequence could certify (see there);
512// has_wildcard means the input needs at least segments.size() segments
513// rather than exactly that many.
514bool co_matchable(const route_info& w, const route_info& c) noexcept {
515 const bool c_regexp = c.mode == route_mode::regexp;
516 const size_t wn = w.segments.size();
517 const size_t cn = c.segments.size();
518 constexpr size_t unbounded = ~size_t{0};
519 // Segment counts each route accepts: [min, max].
520 const size_t w_max = w.has_wildcard ? unbounded : wn;
521 const size_t c_max = c.has_wildcard ? unbounded : cn;
522 if ((wn > cn ? wn : cn) > (w_max < c_max ? w_max : c_max)) {
523 return false;
524 }
525 // Positions both routes constrain (a safe wildcard segment constrains
526 // nothing; a regexp route's segments are all constraining).
527 const size_t w_fixed = w.has_wildcard ? wn - 1 : wn;
528 const size_t c_fixed = (!c_regexp && c.has_wildcard) ? cn - 1 : cn;
529 const size_t upto = w_fixed < c_fixed ? w_fixed : c_fixed;
530 for (size_t j = 0; j < upto; j++) {
531 const route_segment& ws = w.segments[j];
532 const route_segment& cs = c.segments[j];
533 if (ws.kind == segment_kind::literal && cs.kind == segment_kind::literal) {
534 if (ws.text != cs.text) {
535 return false;
536 }
537 } else if (ws.kind == segment_kind::literal &&
538 cs.kind == segment_kind::param) {
539 if (ws.text.empty()) {
540 return false; // params never bind an empty segment
541 }
542 } else if (ws.kind == segment_kind::param &&
543 cs.kind == segment_kind::literal) {
544 if (cs.text.empty()) {
545 return false;
546 }
547 }
548 }
549 return true;
550}
551
552// Auxiliary routes: those the trie cannot answer for (regexp mode and
553// sequential mode), in insertion order, followed by one challenger range per
554// trie route: the auxiliary routes that outrank it AND could match the same
555// input. After a fast-path hit only the winner's challengers are tested
556// (usually none). Fails past url_pattern_list_limits::max_aux_entries.
557bool build_aux_table(builder_tables& r, const std::vector<route_info>& routes) {
558 std::vector<uint32_t> aux_all;
559 for (size_t i = 0; i < routes.size(); i++) {
560 if (routes[i].mode != route_mode::trie) {
561 aux_all.push_back(static_cast<uint32_t>(i));
562 }
563 }
564 r.aux = aux_all;
565 r.n_aux_all = static_cast<uint32_t>(aux_all.size());
566 for (size_t w = 0; w < routes.size(); w++) {
567 const route_info& winner = routes[w];
568 if (winner.mode != route_mode::trie) {
569 continue; // never a fast-path winner
570 }
571 route_record& rm = r.routes[w];
572 rm.challenger_first = static_cast<uint32_t>(r.aux.size());
573 for (const uint32_t c : aux_all) {
574 if (route_outranks(routes[c], c, winner, w) &&
575 co_matchable(winner, routes[c])) {
576 if (r.aux.size() >= url_pattern_list_limits::max_aux_entries) {
577 return false;
578 }
579 r.aux.push_back(c);
580 }
581 }
582 rm.challenger_count =
583 static_cast<uint32_t>(r.aux.size()) - rm.challenger_first;
584 }
585 return true;
586}
587
588// Packs every table into one arena, each section 8-byte aligned, and
589// records the section offsets. The blob gets 8 bytes of zero padding so
590// short key windows can always be loaded whole. Fails when the arena does not
591// fit the uint32_t offsets, which also bounds every offset and count stored
592// in the tables.
593tl::expected<compiled_routes, errors> pack_arena(builder_tables& r) {
594 compiled_routes out{};
595 r.blob.insert(r.blob.end(), 8, '\0');
596 uint64_t total = 0;
597 const auto reserve = [&](size_t bytes) {
598 const uint64_t offset = total;
599 total += (bytes + 7) & ~size_t{7};
600 return static_cast<uint32_t>(offset);
601 };
602 const auto bytes_of = [](const auto& v) { return v.size() * sizeof(v[0]); };
603 out.nodes_offset = reserve(bytes_of(r.nodes));
604 out.hashes_offset = reserve(bytes_of(r.hashes));
605 out.edges_offset = reserve(bytes_of(r.edges));
606 out.slots_offset = reserve(bytes_of(r.slots));
607 out.blob_offset = reserve(bytes_of(r.blob));
608 out.routes_offset = reserve(bytes_of(r.routes));
609 out.segments_offset = reserve(bytes_of(r.segments));
610 out.aux_offset = reserve(bytes_of(r.aux));
611 out.root_index_offset = reserve(bytes_of(r.root_index));
612 // LCOV_EXCL_START
613 if (total > UINT32_MAX) {
614 return tl::unexpected(errors::type_error);
615 }
616 // LCOV_EXCL_STOP
617 out.arena.assign(static_cast<size_t>(total), 0);
618 const auto place = [&](uint32_t offset, const auto& v) {
619 if (!v.empty()) {
620 std::memcpy(out.arena.data() + offset, v.data(), v.size() * sizeof(v[0]));
621 }
622 };
623 place(out.nodes_offset, r.nodes);
624 place(out.hashes_offset, r.hashes);
625 place(out.edges_offset, r.edges);
626 place(out.slots_offset, r.slots);
627 place(out.blob_offset, r.blob);
628 place(out.routes_offset, r.routes);
629 place(out.segments_offset, r.segments);
630 place(out.aux_offset, r.aux);
631 place(out.root_index_offset, r.root_index);
632 out.n_routes = static_cast<uint32_t>(r.routes.size());
633 out.n_aux_all = r.n_aux_all;
634 return out;
635}
636
637// Fills route.kind_sequence / kind_length from route.segments.
638void compute_kind_sequence(route_info& route) noexcept {
639 uint64_t seq = 0;
640 const size_t n = route.segments.size();
641 for (size_t j = 0; j < n && j < 32; j++) {
642 seq |= static_cast<uint64_t>(route.segments[j].kind) << (62 - 2 * j);
643 }
644 route.kind_sequence = seq;
645 route.kind_length = static_cast<uint8_t>(n < 255 ? n : 255);
646}
647
648} // namespace
649
650// ---- compiler entry points -------------------------------------------------
651
652bool classify_parts(const std::vector<url_pattern_part>& parts,
653 std::vector<route_segment>& segments,
654 std::vector<std::string>& group_names) {
655 segments.clear();
656 group_names.clear();
657 bool started = false; // leading '/' consumed
658 bool group_open = false; // the open segment slot is a group
659 bool wildcard_seen = false; // a "*" segment was consumed (must stay last)
660 std::string literal;
661 const auto close_segment = [&]() {
662 if (!group_open) {
663 segments.push_back(route_segment{segment_kind::literal, literal});
664 }
665 literal.clear();
666 group_open = false;
667 };
668 const auto process_text = [&](std::string_view text) {
669 for (const char c : text) {
670 if (wildcard_seen) {
671 return false; // nothing may follow a "*" segment
672 }
673 if (c == '/') {
674 if (!started) {
675 started = true;
676 } else {
677 close_segment();
678 }
679 } else {
680 if (!started || group_open) {
681 return false; // text before '/', or suffix text after a group
682 }
683 literal += c;
684 }
685 }
686 return true;
687 };
688 for (const url_pattern_part& part : parts) {
689 if (part.type == url_pattern_part_type::FIXED_TEXT &&
690 part.modifier == url_pattern_part_modifier::none) {
691 if (!process_text(part.prefix) || !process_text(part.value) ||
692 !process_text(part.suffix)) {
693 return false;
694 }
695 } else if ((part.type == url_pattern_part_type::SEGMENT_WILDCARD ||
696 part.type == url_pattern_part_type::FULL_WILDCARD) &&
697 part.modifier == url_pattern_part_modifier::none &&
698 part.suffix.empty()) {
699 if (wildcard_seen) {
700 return false;
701 }
702 if (part.prefix == "/") {
703 if (!started) {
704 started = true;
705 } else {
706 close_segment();
707 }
708 } else if (part.prefix.empty()) {
709 // The group must occupy a whole, freshly opened segment slot.
710 if (!started || group_open || !literal.empty()) {
711 return false;
712 }
713 } else {
714 return false; // group not aligned on a '/' boundary
715 }
716 const bool is_wildcard =
717 part.type == url_pattern_part_type::FULL_WILDCARD;
718 segments.push_back(route_segment{
719 is_wildcard ? segment_kind::wildcard : segment_kind::param,
720 part.name});
721 group_names.push_back(part.name);
722 group_open = true;
723 wildcard_seen = is_wildcard;
724 } else {
725 return false; // regexp group or a "?" / "+" / "*" modifier
726 }
727 }
728 if (!started) {
729 // Only the empty pattern (zero parts) is representable without a leading
730 // '/': it matches exactly the empty pathname.
731 return parts.empty();
732 }
733 close_segment();
734 return true;
735}
736
737void finalize_route(route_info& route) noexcept {
738 compute_kind_sequence(route);
739 route.all_literal = true;
740 route.has_wildcard = false;
741 size_t n_params = 0;
742 // A trie edge keeps its literal segment length in edge_record::key_length, a
743 // uint16_t. A literal longer than that wraps around, so the trie would match
744 // a shorter, truncated length (e.g. a 65536-byte segment becomes length 0 and
745 // matches an empty segment). Keep such a route out of the trie and let the
746 // sequential matcher, which compares the whole segment, answer it.
747 bool literal_fits_edge = true;
748 for (const route_segment& s : route.segments) {
749 if (s.kind != segment_kind::literal) {
750 route.all_literal = false;
751 if (s.kind == segment_kind::param) {
752 n_params++;
753 } else {
754 route.has_wildcard = true;
755 }
756 } else if (s.text.size() > std::numeric_limits<uint16_t>::max()) {
757 literal_fits_edge = false;
758 }
759 }
760 const size_t n_captures = n_params + (route.has_wildcard ? 1 : 0);
761 const bool trie_safe = !route.segments.empty() &&
762 route.segments.size() <= max_trie_pattern_segments &&
763 n_captures <= max_captures_per_route &&
764 literal_fits_edge;
765 route.mode = trie_safe ? route_mode::trie : route_mode::sequential;
766}
767
768void approximate_kind_sequence(const std::vector<url_pattern_part>& parts,
769 route_info& route) {
770 std::vector<uint8_t> kinds;
771 // The route's segment shape, as far as it is known: literal segments carry
772 // their text, opaque ones (a ":name" group, alone or mixed with text) are
773 // params. Exact while every group is a ":name" segment wildcard, which
774 // cannot match '/': then the segment count and every literal position are
775 // certain. A custom "(...)" group, a "*" or a modifier can span segments,
776 // so from there on nothing is known and only the anchored literal prefix
777 // before it is kept.
778 std::vector<route_segment> shape;
779 std::string literal;
780 bool started = false;
781 bool open = false;
782 bool leading_slash = false; // the pattern is anchored at a '/'
783 bool exact = true; // no part can span a segment boundary
784 bool tail_known = true; // segments after the last closed one are known
785 uint8_t current = 0;
786 // Closes the open segment; `complete` is true only when a '/' of fixed
787 // text closed it, i.e. the segment is exactly what was accumulated.
788 const auto close = [&](bool complete) {
789 if (open) {
790 kinds.push_back(current);
791 if (complete || exact) {
792 shape.push_back(current == 0
793 ? route_segment{segment_kind::literal, literal}
794 : route_segment{segment_kind::param, {}});
795 } else {
796 tail_known = false;
797 }
798 open = false;
799 current = 0;
800 }
801 literal.clear();
802 };
803 const auto process_text = [&](std::string_view text) {
804 for (const char c : text) {
805 if (c == '/') {
806 if (started) {
807 close(true);
808 } else {
809 leading_slash = true;
810 }
811 started = true;
812 open = true;
813 current = 0;
814 } else {
815 if (!started) {
816 started = true;
817 }
818 if (!open) {
819 open = true;
820 current = 0;
821 }
822 literal += c;
823 }
824 }
825 };
826 const auto add_group = [&](uint8_t kind) {
827 if (!open) {
828 started = true;
829 open = true;
830 current = 0;
831 }
832 current = current < kind ? kind : current;
833 };
834 for (const url_pattern_part& part : parts) {
835 if (part.type == url_pattern_part_type::FULL_WILDCARD ||
836 part.modifier != url_pattern_part_modifier::none) {
837 // A greedy or modified group can span segments: treat the rest of the
838 // route as a wildcard tail and stop. A "/" prefix closes the previous
839 // segment only when this part must occur. An optional ("?") or
840 // zero-or-more ("*") part, prefix included, may be absent, so the text
841 // after it stays in the same segment ("/reports{/:id}?.json" matches
842 // "/reports.json"). Treating that "/" as a definite boundary certified
843 // a segment the input does not have, and the shape check rejected the
844 // match before the provider ran.
845 exact = false;
846 const bool must_occur =
847 part.modifier != url_pattern_part_modifier::optional &&
848 part.modifier != url_pattern_part_modifier::zero_or_more;
849 close(must_occur && part.prefix == "/");
850 tail_known = false;
851 kinds.push_back(2);
852 break;
853 }
854 if (part.type == url_pattern_part_type::FIXED_TEXT) {
855 process_text(part.value);
856 } else { // SEGMENT_WILDCARD or REGEXP, modifier none
857 if (part.type == url_pattern_part_type::REGEXP) {
858 exact = false; // a custom group may match '/'
859 }
860 process_text(part.prefix);
861 add_group(1);
862 process_text(part.suffix);
863 }
864 }
865 close(exact);
866 uint64_t seq = 0;
867 for (size_t j = 0; j < kinds.size() && j < 32; j++) {
868 seq |= static_cast<uint64_t>(kinds[j]) << (62 - 2 * j);
869 }
870 route.kind_sequence = seq;
871 route.kind_length =
872 static_cast<uint8_t>(kinds.size() < 255 ? kinds.size() : 255);
873 route.mode = route_mode::regexp;
874 route.all_literal = false;
875 route.segments.clear();
876 if (!leading_slash) {
877 // Not anchored at '/': nothing about the segments is known.
878 route.has_wildcard = true;
879 return;
880 }
881 // has_wildcard here means "the tail is unconstrained": the input needs at
882 // least segments.size() segments; otherwise exactly that many.
883 route.has_wildcard = !(exact && tail_known);
884 if (route.has_wildcard) {
885 // Keep only the anchored literal prefix.
886 size_t n_prefix = 0;
887 while (n_prefix < shape.size() &&
888 shape[n_prefix].kind == segment_kind::literal) {
889 n_prefix++;
890 }
891 shape.resize(n_prefix);
892 }
893 route.segments = std::move(shape);
894}
895
896tl::expected<compiled_routes, errors> compile_route_set(
897 std::vector<route_info>& routes) {
898 builder_tables r{};
899 const std::vector<transient_node> t = build_trie(routes);
900 compile_route_records(r, routes);
901 const std::vector<int32_t> order = layout_nodes(r, t);
902 compile_dispatch(r, t, order);
903 encode_leaf_shortcuts(r); // last: must not confuse the stages above
904 build_segment_table(r, routes);
905 if (!build_aux_table(r, routes)) {
906 return tl::unexpected(errors::type_error);
907 }
908 auto out = pack_arena(r);
909 if (!out) {
910 return out;
911 }
912 out->group_names.resize(routes.size());
913 for (size_t i = 0; i < routes.size(); i++) {
914 if (routes[i].mode != route_mode::regexp) {
915 out->group_names[i] = routes[i].group_names;
916 }
917 }
918 return out;
919}
920
921} // namespace ada::url_pattern_list_compiler
922
923namespace ada::url_pattern_list_detail {
924
925tl::expected<compiled_routes, errors> compile_pathname_patterns(
926 std::span<const std::string> patterns, bool ignore_case) {
927 if (patterns.size() > url_pattern_list_limits::max_routes) {
928 return tl::unexpected(errors::type_error);
929 }
930 namespace compiler = url_pattern_list_compiler;
931 std::vector<compiler::route_info> routes;
932 routes.reserve(patterns.size());
933 for (const std::string& pattern : patterns) {
934 // The pattern side goes through ada's own URLPattern machinery: the
935 // pattern parser tokenizes and canonicalizes exactly as a URLPattern
936 // pathname component would.
937 auto options = url_pattern_compile_component_options::PATHNAME;
938 auto part_list = url_pattern_helpers::parse_pattern_string(
939 pattern, options, url_pattern_helpers::canonicalize_pathname);
940 if (!part_list) {
941 return tl::unexpected(part_list.error());
942 }
943 compiler::route_info route{};
944 if (compiler::classify_parts(*part_list, route.segments,
945 route.group_names)) {
946 compiler::finalize_route(route);
947 } else {
948 // The pattern needs URLPattern regexp semantics: the caller compiles
949 // it as a pathname component through the provider; it participates
950 // in the priority order via its approximated kind sequence.
951 compiler::approximate_kind_sequence(*part_list, route);
952 }
953 if (ignore_case) {
954 // The compiled literals are ASCII-folded; the matcher folds the input
955 // the same way.
956 for (compiler::route_segment& s : route.segments) {
957 if (s.kind == compiler::segment_kind::literal) {
958 ascii_fold(s.text.data(), static_cast<uint32_t>(s.text.size()),
959 s.text.data());
960 }
961 }
962 }
963 routes.push_back(std::move(route));
964 }
965 auto compiled = compiler::compile_route_set(routes);
966 if (compiled) {
967 compiled->ignore_case = ignore_case ? 1 : 0;
968 }
969 return compiled;
970}
971
972namespace {
973
974// Literal-segment compare against the blob, folding the input on request
975// (the blob text is already folded).
976bool literal_equals(std::string_view s, const char* text, uint32_t length,
977 bool fold_input) noexcept {
978 if (s.size() != length) {
979 return false;
980 }
981 if (!fold_input) {
982 return s.size() == 0 || std::memcmp(s.data(), text, s.size()) == 0;
983 }
984 for (size_t i = 0; i < s.size(); i++) {
985 const uint8_t c = static_cast<uint8_t>(s[i]);
986 const char folded =
987 static_cast<char>(c | ((c >= 'A' && c <= 'Z') ? 0x20u : 0u));
988 if (folded != text[i]) {
989 return false;
990 }
991 }
992 return true;
993}
994
995} // namespace
996
997// Kept out of line on purpose: inlined into the walk, this loop cost the
998// static and ":param" paths, which never run it, about 5 ns through register
999// allocation; as a call it costs only wildcard hits. It lives in this
1000// translation unit rather than the header because MSVC's ada_never_inline
1001// expands to __declspec(noinline) with no inline linkage, so a definition in
1002// the header is emitted in every translation unit and the link fails.
1003//
1004// On AArch64 whole 16-byte blocks go through NEON (a running byte minimum);
1005// the rest is SWAR, 8 bytes per step: "some byte is below 0x20" ("hasless"
1006// of Bit Twiddling Hacks) is exact as a yes/no answer, because a borrow can
1007// only leave a lane that itself qualifies. Only a tail holding a control
1008// byte gets the exact byte check.
1009bool wildcard_tail_ok(const char* p, uint32_t n) noexcept {
1010 constexpr uint64_t spaces = 0x2020202020202020ull;
1011 constexpr uint64_t highs = 0x8080808080808080ull;
1012 const auto below_space = [](uint64_t x) noexcept {
1013 return (x - spaces) & ~x & highs;
1014 };
1015 uint64_t control = 0;
1016 uint32_t i = 0;
1017#if ADA_NEON
1018 if (n >= 16) {
1019 uint8x16_t lowest = vdupq_n_u8(0xFF);
1020 for (; i + 16 <= n; i += 16) {
1021 lowest =
1022 vminq_u8(lowest, vld1q_u8(reinterpret_cast<const uint8_t*>(p + i)));
1023 }
1024 control = vminvq_u8(lowest) < 0x20 ? 1 : 0;
1025 }
1026#endif
1027 for (; i + 8 <= n; i += 8) {
1028 control |= below_space(load8_le(p + i));
1029 }
1030 if (i < n) { // 1..7 bytes, padded with spaces
1031 control |= below_space(gather_le(p + i, n - i) |
1032 (spaces & ~low_bytes_mask(n - i)));
1033 }
1034 if (control == 0) {
1035 return true;
1036 }
1037 for (uint32_t j = 0; j < n; j++) {
1038 if (p[j] == '\n' || p[j] == '\r') {
1039 return false;
1040 }
1041 }
1042 return true;
1043}
1044
1045bool match_regexp_shape(const compiled_routes& r, uint32_t route,
1046 std::string_view pathname, bool fold_input) noexcept {
1047 const route_record& rt = r.section<route_record>(r.routes_offset)[route];
1048 const segment_record* segs =
1049 r.section<segment_record>(r.segments_offset) + rt.segment_first;
1050 const char* blob = r.section<char>(r.blob_offset);
1051 if (rt.segment_count == 0 && rt.wild != 0) {
1052 return true; // nothing is known about the route's shape
1053 }
1054 if (pathname.empty() || pathname[0] != '/') {
1055 return false; // a known shape always starts with '/'
1056 }
1057 size_t seg_start = 1;
1058 for (uint32_t si = 0; si < rt.segment_count; si++) {
1059 if (seg_start > pathname.size()) {
1060 return false; // fewer segments than the shape
1061 }
1062 const size_t slash = pathname.find('/', seg_start);
1063 const size_t seg_end =
1064 slash == std::string_view::npos ? pathname.size() : slash;
1065 const std::string_view s(pathname.data() + seg_start, seg_end - seg_start);
1066 if (segs[si].kind == 0) { // literal
1067 if (!literal_equals(s, blob + segs[si].text_offset, segs[si].text_length,
1068 fold_input)) {
1069 return false;
1070 }
1071 } else if (s.empty()) {
1072 return false; // a ":name" group, mixed or not, never binds ""
1073 }
1074 seg_start = seg_end + 1;
1075 }
1076 // An exact shape admits no further segments.
1077 return rt.wild != 0 || seg_start == pathname.size() + 1;
1078}
1079
1080bool match_route_sequential(const compiled_routes& r, uint32_t route,
1081 std::string_view pathname, bool fold_input,
1082 engine_result& result) noexcept {
1083 using url_pattern_list_limits::max_captures_per_route;
1084 result.capture_count = 0;
1085 result.captures_truncated = false;
1086 const route_record& rt = r.section<route_record>(r.routes_offset)[route];
1087 const segment_record* segs =
1088 r.section<segment_record>(r.segments_offset) + rt.segment_first;
1089 const char* blob = r.section<char>(r.blob_offset);
1090 const size_t n_pattern = rt.segment_count;
1091 if (n_pattern == 0) {
1092 return pathname.empty(); // the empty pattern matches only ""
1093 }
1094 if (pathname.empty() || pathname[0] != '/') {
1095 return false;
1096 }
1097 const bool wild = rt.wild != 0; // wildcard is always the last segment
1098 const size_t n_fixed = wild ? n_pattern - 1 : n_pattern;
1099 uint32_t total_captures = 0;
1100 const auto add_capture = [&](size_t offset, size_t length) {
1101 if (total_captures < max_captures_per_route) {
1102 result.captures[total_captures] = {static_cast<uint32_t>(offset),
1103 static_cast<uint32_t>(length)};
1104 } else {
1105 result.captures_truncated = true;
1106 }
1107 total_captures++;
1108 };
1109 size_t seg_start = 1;
1110 for (size_t si = 0; si < n_fixed; si++) {
1111 if (seg_start > pathname.size()) {
1112 return false; // the input has fewer segments than the pattern
1113 }
1114 const size_t slash = pathname.find('/', seg_start);
1115 const size_t seg_end =
1116 slash == std::string_view::npos ? pathname.size() : slash;
1117 // seg_start <= pathname.size() was checked above, so this is in range
1118 // (spelled without substr to keep the function provably non-throwing).
1119 const std::string_view s(pathname.data() + seg_start, seg_end - seg_start);
1120 if (segs[si].kind == 0) { // literal
1121 if (!literal_equals(s, blob + segs[si].text_offset, segs[si].text_length,
1122 fold_input)) {
1123 return false;
1124 }
1125 } else { // param: binds one non-empty segment
1126 if (s.empty()) {
1127 return false;
1128 }
1129 add_capture(seg_start, s.size());
1130 }
1131 seg_start = seg_end + 1;
1132 }
1133 if (wild) {
1134 if (seg_start > pathname.size()) {
1135 return false; // the wildcard still needs its (possibly empty) segment
1136 }
1137 // "(.*)" does not match a line terminator (see wildcard_tail_ok).
1138 if (pathname.find_first_of("\n\r", seg_start) != std::string_view::npos) {
1139 return false;
1140 }
1141 add_capture(seg_start, pathname.size() - seg_start);
1142 } else if (seg_start != pathname.size() + 1) {
1143 return false; // the input has more segments than the pattern
1144 }
1145 result.capture_count = total_captures < max_captures_per_route
1146 ? total_captures
1147 : max_captures_per_route;
1148 return true;
1149}
1150
1151} // namespace ada::url_pattern_list_detail
1152#endif // ADA_INCLUDE_URL_PATTERN
Main header for the Ada URL parser library.
state
States in the URL parsing state machine.
Definition state.h:27
tl::expected< result_type, ada::errors > result
The url_pattern_list route-set compiler: pattern classification and the build-time table construction...