30#if ADA_INCLUDE_URL_PATTERN
32namespace ada::url_pattern_list_compiler {
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;
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;
64constexpr uint16_t pack_witness_plan(
const uint8_t* ids, uint32_t n_ids,
65 bool use_len)
noexcept {
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)
72 w =
static_cast<uint16_t
>(w |
static_cast<uint16_t
>(n_ids << 12));
74 w =
static_cast<uint16_t
>(w |
static_cast<uint16_t
>(1) << 14);
81constexpr uint64_t pack_window_le(
const char* p, uint32_t len,
82 uint32_t from)
noexcept {
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);
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;
102struct transient_node {
103 std::vector<std::pair<std::string_view, int32_t>> kids{};
105 int32_t wild_route = -1;
106 int32_t terminal = -1;
109constexpr unsigned ceil_log2(
size_t n)
noexcept {
111 while ((
size_t{1} << b) < n) {
119constexpr unsigned initial_slot_bits(
size_t n)
noexcept {
120 unsigned headroom = 1;
126 return ceil_log2(n) + headroom;
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;
138 for (
size_t i = 0; i < n; i++) {
139 const uint64_t s = (proj[i] * m) >> (64 - b);
148 bits_out =
static_cast<uint8_t
>(b);
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,
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++) {
170 url_pattern_list_detail::slot_of(proj[i], multiplier_out, bits_out)] =
171 static_cast<uint8_t
>(i);
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;
183 c[
static_cast<uint32_t
>(j)] == n - k +
static_cast<uint32_t
>(j)) {
189 c[
static_cast<uint32_t
>(j)]++;
190 for (uint32_t t =
static_cast<uint32_t
>(j) + 1; t < k; t++) {
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) {
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()),
211 std::sort(proj.begin(), proj.end());
212 for (
size_t i = 1; i < n; i++) {
213 if (proj[i] == proj[i - 1]) {
219 for (uint32_t k = 1; k <= max_reads && k <= n_alpha; k++) {
220 std::array<uint32_t, 3> c{0, 1, 2};
222 uint8_t ids[3] = {0, 0, 0};
223 for (uint32_t j = 0; j < k; j++) {
224 ids[j] = alphabet[c[j]];
226 const uint16_t wp = pack_witness_plan(ids, k,
true);
231 }
while (next_combination(c, k, n_alpha));
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) {
252 for (
const route_segment& ps : rt.segments) {
253 if (ps.kind == segment_kind::literal) {
255 for (
auto& kv : t[
static_cast<size_t>(cur)].kids) {
256 if (kv.first == ps.text) {
262 nxt =
static_cast<int32_t
>(t.size());
263 t[
static_cast<size_t>(cur)].kids.emplace_back(ps.text, 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());
272 cur = t[
static_cast<size_t>(cur)].param;
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);
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);
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]);
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;
309 rm.wild = rt.has_wildcard ? 1 : 0;
310 if (rt.mode == route_mode::regexp) {
311 rm.regexp_component = n_regexp++;
314 if (rt.mode != route_mode::trie) {
317 for (
size_t s = 0; s < rt.segments.size(); s++) {
318 if (rt.segments[s].kind == segment_kind::param) {
321 rm.param_positions[rm.n_params++] =
static_cast<uint8_t
>(s);
330std::vector<int32_t> layout_nodes(builder_tables& r,
331 const std::vector<transient_node>& t) {
332 std::vector<int32_t> order;
335 for (
size_t head = 0; head < order.size(); head++) {
336 const transient_node& tn = t[
static_cast<size_t>(order[head])];
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();
343 for (
size_t ci = 0; ci < tn.kids.size(); ci++) {
344 const std::string_view k = tn.kids[ci].first;
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);
356 for (
size_t ci = 0; ci < tn.kids.size(); ci++) {
357 order.push_back(tn.kids[ci].second);
360 nd.param_child =
static_cast<int32_t
>(order.size());
361 order.push_back(tn.param);
363 nd.has_alternative = (nd.param_child >= 0 || nd.wild_route >= 0) ? 1 : 0;
364 r.nodes.resize(order.size());
376bool build_root_index(builder_tables& r,
const transient_node& root) {
377 const size_t nk = root.kids.size();
381 std::array<uint16_t, 256> index{};
383 std::array<uint32_t, 256> run{};
384 for (
size_t ci = 0; ci < nk; ci++) {
385 if (root.kids[ci].first.empty()) {
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);
392 if (++run[b] > max_direct_children) {
396 r.root_index.assign(index.begin(), index.end());
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();
416 if (ni == 0 && build_root_index(r, tn)) {
420 if (nk <= max_direct_children) {
424 if (nk > max_dispatch_table_entries) {
431 constexpr uint8_t alpha_small[2] = {0, 8};
432 found = find_witness_plan(tn.kids, alpha_small, 2, 2, wp);
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);
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);
447 found = emit_slot_table(proj,
r.slots, h.multiplier, h.slot_bits,
456 nd.hash_index =
static_cast<uint32_t
>(
r.hashes.size());
457 r.hashes.push_back(h);
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;
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;
476 for (
auto& nd :
r.nodes) {
477 if (nd.param_child >= 0 && pure_leaf(nd.param_child)) {
479 -2 -
r.nodes[
static_cast<size_t>(nd.param_child)].terminal_route;
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) {
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());
503 r.segments.push_back(sr);
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};
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)) {
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) {
537 }
else if (ws.kind == segment_kind::literal &&
538 cs.kind == segment_kind::param) {
539 if (ws.text.empty()) {
542 }
else if (ws.kind == segment_kind::param &&
543 cs.kind == segment_kind::literal) {
544 if (cs.text.empty()) {
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));
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) {
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) {
582 rm.challenger_count =
583 static_cast<uint32_t
>(
r.aux.size()) - rm.challenger_first;
593tl::expected<compiled_routes, errors> pack_arena(builder_tables& r) {
594 compiled_routes out{};
595 r.blob.insert(
r.blob.end(), 8,
'\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);
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));
613 if (total > UINT32_MAX) {
614 return tl::unexpected(errors::type_error);
617 out.arena.assign(
static_cast<size_t>(total), 0);
618 const auto place = [&](uint32_t offset,
const auto& v) {
620 std::memcpy(out.arena.data() + offset, v.data(), v.size() *
sizeof(v[0]));
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;
638void compute_kind_sequence(route_info& route)
noexcept {
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);
644 route.kind_sequence = seq;
645 route.kind_length =
static_cast<uint8_t
>(n < 255 ? n : 255);
652bool classify_parts(
const std::vector<url_pattern_part>& parts,
653 std::vector<route_segment>& segments,
654 std::vector<std::string>& group_names) {
657 bool started =
false;
658 bool group_open =
false;
659 bool wildcard_seen =
false;
661 const auto close_segment = [&]() {
663 segments.push_back(route_segment{segment_kind::literal, literal});
668 const auto process_text = [&](std::string_view text) {
669 for (
const char c : text) {
680 if (!started || group_open) {
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)) {
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()) {
702 if (part.prefix ==
"/") {
708 }
else if (part.prefix.empty()) {
710 if (!started || group_open || !literal.empty()) {
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,
721 group_names.push_back(part.name);
723 wildcard_seen = is_wildcard;
731 return parts.empty();
737void finalize_route(route_info& route)
noexcept {
738 compute_kind_sequence(route);
739 route.all_literal =
true;
740 route.has_wildcard =
false;
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) {
754 route.has_wildcard =
true;
756 }
else if (s.text.size() > std::numeric_limits<uint16_t>::max()) {
757 literal_fits_edge =
false;
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 &&
765 route.mode = trie_safe ? route_mode::trie : route_mode::sequential;
768void approximate_kind_sequence(
const std::vector<url_pattern_part>& parts,
770 std::vector<uint8_t> kinds;
778 std::vector<route_segment> shape;
780 bool started =
false;
782 bool leading_slash =
false;
784 bool tail_known =
true;
788 const auto close = [&](
bool complete) {
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, {}});
803 const auto process_text = [&](std::string_view text) {
804 for (
const char c : text) {
809 leading_slash =
true;
826 const auto add_group = [&](uint8_t kind) {
832 current = current < kind ? kind : current;
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) {
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 ==
"/");
854 if (part.type == url_pattern_part_type::FIXED_TEXT) {
855 process_text(part.value);
857 if (part.type == url_pattern_part_type::REGEXP) {
860 process_text(part.prefix);
862 process_text(part.suffix);
867 for (
size_t j = 0; j < kinds.size() && j < 32; j++) {
868 seq |=
static_cast<uint64_t
>(kinds[j]) << (62 - 2 * j);
870 route.kind_sequence = seq;
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) {
878 route.has_wildcard =
true;
883 route.has_wildcard = !(exact && tail_known);
884 if (route.has_wildcard) {
887 while (n_prefix < shape.size() &&
888 shape[n_prefix].kind == segment_kind::literal) {
891 shape.resize(n_prefix);
893 route.segments = std::move(shape);
896tl::expected<compiled_routes, errors> compile_route_set(
897 std::vector<route_info>& routes) {
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);
904 build_segment_table(r, routes);
905 if (!build_aux_table(r, routes)) {
906 return tl::unexpected(errors::type_error);
908 auto out = pack_arena(r);
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;
923namespace ada::url_pattern_list_detail {
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);
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) {
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);
941 return tl::unexpected(part_list.error());
943 compiler::route_info route{};
944 if (compiler::classify_parts(*part_list, route.segments,
945 route.group_names)) {
946 compiler::finalize_route(route);
951 compiler::approximate_kind_sequence(*part_list, route);
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()),
963 routes.push_back(std::move(route));
965 auto compiled = compiler::compile_route_set(routes);
967 compiled->ignore_case = ignore_case ? 1 : 0;
976bool literal_equals(std::string_view s,
const char* text, uint32_t length,
977 bool fold_input)
noexcept {
978 if (s.size() != length) {
982 return s.size() == 0 || std::memcmp(s.data(), text, s.size()) == 0;
984 for (
size_t i = 0; i < s.size(); i++) {
985 const uint8_t c =
static_cast<uint8_t
>(s[i]);
987 static_cast<char>(c | ((c >=
'A' && c <=
'Z') ? 0x20u : 0u));
988 if (folded != text[i]) {
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;
1015 uint64_t control = 0;
1019 uint8x16_t lowest = vdupq_n_u8(0xFF);
1020 for (; i + 16 <= n; i += 16) {
1022 vminq_u8(lowest, vld1q_u8(
reinterpret_cast<const uint8_t*
>(p + i)));
1024 control = vminvq_u8(lowest) < 0x20 ? 1 : 0;
1027 for (; i + 8 <= n; i += 8) {
1028 control |= below_space(load8_le(p + i));
1031 control |= below_space(gather_le(p + i, n - i) |
1032 (spaces & ~low_bytes_mask(n - i)));
1037 for (uint32_t j = 0; j < n; j++) {
1038 if (p[j] ==
'\n' || p[j] ==
'\r') {
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) {
1054 if (pathname.empty() || pathname[0] !=
'/') {
1057 size_t seg_start = 1;
1058 for (uint32_t si = 0; si < rt.segment_count; si++) {
1059 if (seg_start > pathname.size()) {
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) {
1067 if (!literal_equals(s, blob + segs[si].text_offset, segs[si].text_length,
1071 }
else if (s.empty()) {
1074 seg_start = seg_end + 1;
1077 return rt.wild != 0 || seg_start == pathname.size() + 1;
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();
1094 if (pathname.empty() || pathname[0] !=
'/') {
1097 const bool wild = rt.wild != 0;
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)};
1105 result.captures_truncated =
true;
1109 size_t seg_start = 1;
1110 for (
size_t si = 0; si < n_fixed; si++) {
1111 if (seg_start > pathname.size()) {
1114 const size_t slash = pathname.find(
'/', seg_start);
1115 const size_t seg_end =
1116 slash == std::string_view::npos ? pathname.size() : slash;
1119 const std::string_view s(pathname.data() + seg_start, seg_end - seg_start);
1120 if (segs[si].kind == 0) {
1121 if (!literal_equals(s, blob + segs[si].text_offset, segs[si].text_length,
1129 add_capture(seg_start, s.size());
1131 seg_start = seg_end + 1;
1134 if (seg_start > pathname.size()) {
1138 if (pathname.find_first_of(
"\n\r", seg_start) != std::string_view::npos) {
1141 add_capture(seg_start, pathname.size() - seg_start);
1142 }
else if (seg_start != pathname.size() + 1) {
1145 result.capture_count = total_captures < max_captures_per_route
1147 : max_captures_per_route;
Main header for the Ada URL parser library.
state
States in the URL parsing state machine.
tl::expected< result_type, ada::errors > result
The url_pattern_list route-set compiler: pattern classification and the build-time table construction...