11#ifndef ADA_URL_PATTERN_LIST_INL_H
12#define ADA_URL_PATTERN_LIST_INL_H
33#if ADA_INCLUDE_URL_PATTERN
34namespace ada::url_pattern_list_detail {
42 if constexpr (std::endian::native == std::endian::little) {
44 std::memcpy(&x, p, 8);
48 for (uint32_t j = 0; j < 8; j++) {
49 x |=
static_cast<uint64_t
>(
static_cast<uint8_t
>(p[j])) << (8 * j);
59 for (uint32_t j = 0; j < n; j++) {
60 x |=
static_cast<uint64_t
>(
static_cast<uint8_t
>(p[j])) << (8 * j);
66constexpr uint64_t low_bytes_mask(uint32_t n)
noexcept {
67 return ~0ull >> (64 - 8 * n);
73inline void ascii_fold(
const char* src, uint32_t n,
char* dst)
noexcept {
74 for (uint32_t i = 0; i < n; i++) {
75 const uint8_t c =
static_cast<uint8_t
>(src[i]);
76 dst[i] =
static_cast<char>(c | ((c >=
'A' && c <=
'Z') ? 0x20u : 0u));
90constexpr uint8_t length_byte(uint32_t len)
noexcept {
91 return len < 255u ? static_cast<uint8_t>(len) : static_cast<uint8_t>(255);
94constexpr uint8_t witness_byte(
const char* p, uint32_t len,
95 uint8_t
id)
noexcept {
98 uint32_t pos = (
id & 8u) ? len - 1u - o : o;
100 uint8_t v = len ?
static_cast<uint8_t
>(p[pos]) : static_cast<uint8_t>(0);
101 return in ? v :
static_cast<uint8_t
>(0);
104constexpr uint64_t pack_projection(uint8_t f0, uint8_t f1, uint8_t f2,
105 uint8_t f3)
noexcept {
106 return (
static_cast<uint64_t
>(f0) << 24) | (
static_cast<uint64_t
>(f1) << 16) |
107 (
static_cast<uint64_t
>(f2) << 8) |
static_cast<uint64_t
>(f3);
112constexpr uint64_t slot_of(uint64_t proj, uint64_t multiplier,
113 uint8_t b)
noexcept {
114 return (proj * multiplier) >> (64 - b);
119constexpr uint64_t project(
const char* p, uint32_t len,
120 uint16_t plan)
noexcept {
121 return pack_projection(
122 witness_byte(p, len,
static_cast<uint8_t
>(plan & 15u)),
123 witness_byte(p, len,
static_cast<uint8_t
>((plan >> 4) & 15u)),
124 witness_byte(p, len,
static_cast<uint8_t
>((plan >> 8) & 15u)),
146struct segment_emitter {
153 unsigned shift)
noexcept {
154 using url_pattern_list_limits::max_fast_path_segments;
157 base + (
static_cast<uint32_t
>(std::countr_zero(lanes)) >> shift);
158 if (nseg >= max_fast_path_segments) {
161 soff[nseg++] =
static_cast<uint16_t
>(start);
168 using url_pattern_list_limits::max_fast_path_segments;
169 if (nseg >= max_fast_path_segments) {
172 soff[nseg++] =
static_cast<uint16_t
>(start);
173 soff[nseg] =
static_cast<uint16_t
>(ulen + 1);
179 uint16_t* soff)
noexcept {
180 constexpr uint64_t slashes = 0x2F2F2F2F2F2F2F2Full;
181 constexpr uint64_t low7 = 0x7F7F7F7F7F7F7F7Full;
185 const auto zero_lanes = [](uint64_t x)
noexcept {
186 return ~(((x & low7) + low7) | x | low7);
188 segment_emitter out{soff};
190 for (; i + 8 <= ulen; i += 8) {
191 const uint64_t lanes = zero_lanes(load8_le(url + i) ^ slashes);
192 if (lanes != 0 && !out.emit(lanes, i, 3)) {
197 const uint64_t lanes = zero_lanes(gather_le(url + i, ulen - i) ^ slashes);
198 if (lanes != 0 && !out.emit(lanes, i, 3)) {
202 return out.finish(ulen);
207 uint16_t* soff)
noexcept {
209 const uint8x16_t slash = vdupq_n_u8(
'/');
212 const auto slash_lanes = [&](
const char* p)
noexcept {
213 const uint8x16_t v = vld1q_u8(
reinterpret_cast<const uint8_t*
>(p));
214 const uint64_t nibbles =
215 vget_lane_u64(vreinterpret_u64_u8(vshrn_n_u16(
216 vreinterpretq_u16_u8(vceqq_u8(v, slash)), 4)),
218 return nibbles & 0x1111111111111111ull;
220 segment_emitter out{soff};
222 for (; i + 16 <= ulen; i += 16) {
223 uint64_t lanes = slash_lanes(url + i);
227 if (lanes != 0 && !out.emit(lanes, i, 2)) {
232 const uint32_t off = ulen - 16;
233 const uint64_t lanes = slash_lanes(url + off) & (~0ull << ((i - off) * 4));
234 if (lanes != 0 && !out.emit(lanes, off, 2)) {
238 return out.finish(ulen);
243 uint16_t* soff)
noexcept {
246 return scan_segments_neon(url, ulen, soff);
249 return scan_segments_swar(url, ulen, soff);
268 const char* blob)
noexcept {
269 const uint32_t len = s.len;
270 if (len != e.key_length) {
277 return std::memcmp(s.p, blob + e.key_offset, len) == 0;
280 return ((load8_le(s.p) ^ e.prefix) |
281 (load8_le(s.p + len - 8) ^ e.suffix)) == 0;
283 const uint64_t x = s.avail >= 8 ? (load8_le(s.p) & low_bytes_mask(len))
284 : gather_le(s.p, len);
285 return x == e.prefix;
290 const node_record* nodes;
291 const hash_record* hashes;
292 const edge_record* edges;
293 const uint8_t* slots;
295 const uint16_t* root_index;
299 return table_view{
r.section<node_record>(
r.nodes_offset),
300 r.section<hash_record>(
r.hashes_offset),
301 r.section<edge_record>(
r.edges_offset),
302 r.section<uint8_t>(
r.slots_offset),
303 r.section<
char>(
r.blob_offset),
304 r.section<uint16_t>(
r.root_index_offset)};
312 const node_record& nd,
313 const segment_ref& s)
noexcept {
314 const edge_record* e = t.edges + nd.first_child;
315 switch (nd.dispatch) {
319 for (uint32_t j = 0; j < nd.n_static; j++) {
320 if (verify_edge(e[j], s, t.blob)) {
321 return static_cast<int32_t
>(j);
327 const hash_record& h = t.hashes[nd.hash_index];
328 const uint64_t proj = project(s.p, s.len, h.witness_plan);
330 t.slots[h.slot_base + slot_of(proj, h.multiplier, h.slot_bits)];
334 return verify_edge(e[ord], s, t.blob) ?
static_cast<int32_t
>(ord) : -1;
341 const uint8_t b =
static_cast<uint8_t
>(s.p[0]);
342 uint32_t j = t.root_index[b];
346 for (; j < nd.n_static &&
static_cast<uint8_t
>(e[j].prefix & 0xFFu) == b;
348 if (verify_edge(e[j], s, t.blob)) {
349 return static_cast<int32_t
>(j);
355 for (uint32_t j = 0; j < nd.n_static; j++) {
356 if (verify_edge(e[j], s, t.blob)) {
357 return static_cast<int32_t
>(j);
372 engine_result& out)
noexcept {
373 using url_pattern_list_limits::max_fast_path_pathname_length;
374 using url_pattern_list_limits::max_fast_path_segments;
375 out = engine_result{};
376 if (ulen == 0 || url[0] !=
'/' || ulen > max_fast_path_pathname_length) {
377 out.within_fast_path =
false;
380 const table_view t = view_of(r);
381 const route_record* routes =
r.section<route_record>(
r.routes_offset);
384 uint16_t soff[max_fast_path_segments + 1];
385 const uint32_t nseg = scan_segments(url, ulen, soff);
387 out.within_fast_path =
false;
390 const auto seg_len = [&](uint32_t i) {
391 return static_cast<uint32_t
>(soff[i + 1]) - soff[i] - 1u;
393 const auto seg_ref = [&](uint32_t i) {
394 const uint32_t off = soff[i];
395 return segment_ref{
url + off, seg_len(i), ulen - off};
404 enum alternative : uint16_t {
415 backtrack stack[max_fast_path_segments + 1];
419 uint32_t alt = alt_static;
421 uint32_t wild_from = 0;
424 const node_record& nd = t.nodes[
static_cast<size_t>(node)];
425 if (alt == alt_static) {
427 if (nd.terminal_route >= 0) {
428 route = nd.terminal_route;
433 const int32_t ord = dispatch_static(t, nd, seg_ref(i));
435 const int32_t nxt = t.edges[
static_cast<size_t>(nd.first_child) +
436 static_cast<size_t>(ord)]
439 if (nd.has_alternative) {
440 stack[sp++] = {node,
static_cast<uint16_t
>(i), alt_param};
457 if (alt == alt_param) {
458 const int32_t pc = nd.param_child;
459 if (pc != -1 && seg_len(i) > 0) {
461 if (nd.wild_route >= 0) {
462 stack[sp++] = {node,
static_cast<uint16_t
>(i), alt_wild};
479 if (alt == alt_wild) {
480 if (nd.wild_route >= 0 &&
481 wildcard_tail_ok(url + soff[i], ulen - soff[i])) {
482 route = nd.wild_route;
494 node = stack[sp].node;
496 alt = stack[sp].resume;
501 const route_record& rm = routes[
static_cast<size_t>(route)];
503 for (uint32_t k = 0; k < rm.n_params; k++) {
504 const uint32_t p = rm.param_positions[k];
505 out.captures[nc++] = {soff[p], seg_len(p)};
508 out.captures[nc++] = {soff[wild_from], ulen - soff[wild_from]};
510 out.capture_count = nc;
518template <url_pattern_regex::regex_concept regex_prov
ider>
519tl::expected<url_pattern_list<regex_provider>,
errors>
520url_pattern_list<regex_provider>::create(
521 std::vector<std::string>&& pathname_patterns,
bool ignore_case) {
522 url_pattern_list list{};
523 list.patterns_ = std::move(pathname_patterns);
524 auto compiled = url_pattern_list_detail::compile_pathname_patterns(
525 list.patterns_, ignore_case);
527 return tl::unexpected(compiled.error());
529 list.compiled_ = std::move(*compiled);
533template <url_pattern_regex::regex_concept regex_prov
ider>
534void url_pattern_list<regex_provider>::consider_route(
535 uint32_t route_index, std::string_view pathname, std::string_view probe,
536 bool fold_input, url_pattern_list_detail::engine_result& best,
537 std::vector<std::optional<std::string>>& best_groups)
const {
538 namespace detail = url_pattern_list_detail;
539 const detail::route_record* routes =
540 compiled_.section<detail::route_record>(compiled_.routes_offset);
541 const detail::route_record& candidate = routes[route_index];
543 if (best.route >= 0) {
544 const detail::route_record& current =
545 routes[
static_cast<size_t>(best.route)];
546 if (!detail::outranks(candidate.kind_sequence, candidate.kind_length,
547 route_index, current.kind_sequence,
549 static_cast<size_t>(best.route))) {
553 if (candidate.mode == detail::route_mode::regexp) {
556 if (!detail::match_regexp_shape(compiled_, route_index, probe,
564 const url_pattern_component<regex_provider>& component =
565 regexp_components_[
static_cast<size_t>(candidate.regexp_component)];
566 if (!component.fast_test(pathname)) {
569 auto groups = component.fast_match(pathname);
571 best = detail::engine_result{};
572 best.route =
static_cast<int32_t
>(route_index);
573 best_groups = std::move(*groups);
576 detail::engine_result scratch{};
577 if (detail::match_route_sequential(compiled_, route_index, probe,
578 fold_input, scratch)) {
579 scratch.route =
static_cast<int32_t
>(route_index);
586template <url_pattern_regex::regex_concept regex_prov
ider>
587url_pattern_list_match_result url_pattern_list<regex_provider>::match(
588 std::string_view pathname)
const {
589 namespace detail = url_pattern_list_detail;
590 using url_pattern_list_limits::max_fast_path_pathname_length;
594 if (patterns_.empty() || compiled_.arena.empty()) {
601 char folded[max_fast_path_pathname_length];
602 std::string_view probe = pathname;
603 bool fold_input =
false;
604 if (compiled_.ignore_case) {
605 if (pathname.size() <= max_fast_path_pathname_length) {
606 detail::ascii_fold(pathname.data(),
607 static_cast<uint32_t
>(pathname.size()), folded);
608 probe = std::string_view(folded, pathname.size());
613 detail::engine_result best{};
614 std::vector<std::optional<std::string>> best_groups{};
615 detail::match_compiled(compiled_, probe.data(),
616 static_cast<uint32_t
>(probe.size()), best);
617 const uint32_t* aux = compiled_.section<uint32_t>(compiled_.aux_offset);
618 if (!best.within_fast_path) {
622 best = detail::engine_result{};
623 for (
size_t i = 0; i < patterns_.size(); i++) {
624 consider_route(
static_cast<uint32_t
>(i), pathname, probe, fold_input,
627 }
else if (best.route >= 0) {
630 const detail::route_record& winner =
631 compiled_.section<detail::route_record>(
632 compiled_.routes_offset)[
static_cast<size_t>(best.route)];
633 for (uint32_t k = 0; k < winner.challenger_count; k++) {
634 consider_route(aux[winner.challenger_first + k], pathname, probe,
635 fold_input, best, best_groups);
639 for (uint32_t k = 0; k < compiled_.n_aux_all; k++) {
640 consider_route(aux[k], pathname, probe, fold_input, best, best_groups);
643 url_pattern_list_match_result
result{};
644 result.route_index = best.route;
645 if (best.route >= 0) {
646 const detail::route_record& winner =
647 compiled_.section<detail::route_record>(
648 compiled_.routes_offset)[
static_cast<size_t>(best.route)];
649 if (winner.mode == detail::route_mode::regexp) {
650 result.regexp_route =
true;
651 result.regexp_groups = std::move(best_groups);
653 result.capture_count = best.capture_count;
654 result.captures_truncated = best.captures_truncated;
655 result.captures = best.captures;
Cross-platform compiler macros and common definitions.
#define ada_really_inline
errors
Error codes for URL parsing operations.
tl::expected< result_type, ada::errors > result
Declaration for the URLPattern inline functions.
Declaration for the URLPattern helpers.
Declaration for the URLPattern helpers.
Compiled set-level matching over URLPattern pathname patterns.