Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
url_pattern_list.h
Go to the documentation of this file.
1
26#ifndef ADA_URL_PATTERN_LIST_H
27#define ADA_URL_PATTERN_LIST_H
28
29#include "ada/common_defs.h"
30#include "ada/errors.h"
31#include "ada/expected.h"
32#include "ada/url_pattern.h"
33
34#include <array>
35#include <cstddef>
36#include <cstdint>
37#include <optional>
38#include <span>
39#include <string>
40#include <string_view>
41#include <vector>
42
43#if ADA_INCLUDE_URL_PATTERN
44namespace ada {
45
52namespace url_pattern_list_limits {
53
61inline constexpr uint32_t max_captures_per_route = 8;
62
68inline constexpr uint32_t max_fast_path_segments = 24;
69
75inline constexpr uint32_t max_fast_path_pathname_length = 4096;
76
82inline constexpr uint32_t max_trie_pattern_segments = 16;
83
88inline constexpr size_t max_routes = 65535;
89
94inline constexpr size_t max_aux_entries = 1u << 20;
95
96} // namespace url_pattern_list_limits
97
117struct url_pattern_list_match_result {
119 struct capture {
120 uint32_t offset = 0;
121 uint32_t length = 0;
122 };
124 int32_t route_index = -1;
126 uint32_t capture_count = 0;
128 bool captures_truncated = false;
131 bool regexp_route = false;
132 std::array<capture, url_pattern_list_limits::max_captures_per_route>
133 captures{};
135 std::vector<std::optional<std::string>> regexp_groups{};
136
137 [[nodiscard]] bool has_match() const noexcept { return route_index >= 0; }
138};
139
148namespace url_pattern_list_detail {
149
153struct node_record {
154 // First static edge (edges are laid out per node, contiguously).
155 int32_t first_child = 0;
156 // Child node index, -2 - route (pure-leaf shortcut), or -1.
157 int32_t param_child = -1;
158 // Route index of a "*" ending at this prefix, or -1.
159 int32_t wild_route = -1;
160 // Route ending exactly here, or -1.
161 int32_t terminal_route = -1;
162 uint16_t n_static = 0;
163 // 0 none, 1 direct compares, 2 projection, 3 linear scan, 4 first-byte
164 // index (root only).
165 uint8_t dispatch = 0;
166 // 1 if the node still has a param/wildcard alternative to backtrack to.
167 uint8_t has_alternative = 0;
168 // Index of the node's hash_record (dispatch == 2 only).
169 uint32_t hash_index = 0;
170};
171
173struct hash_record {
174 uint64_t multiplier = 0;
175 uint32_t slot_base = 0;
176 // Witness plan: 3 nibble ids | count << 12 | use_len << 14.
177 uint16_t witness_plan = 0;
178 // Slot table size == 1 << slot_bits.
179 uint8_t slot_bits = 0;
180 uint8_t reserved = 0;
181};
182
185struct edge_record {
186 // Key bytes [0, min(8, len)), little-endian, zero-padded.
187 uint64_t prefix = 0;
188 // Key bytes [max(0, len - 8), len), little-endian, zero-padded.
189 uint64_t suffix = 0;
190 // Child node index; negative values encode -2 - route pure-leaf shortcuts.
191 int32_t node = -1;
192 // Full key in the blob (read only when key_length > 16).
193 uint32_t key_offset = 0;
194 uint16_t key_length = 0;
195};
196
198enum class route_mode : uint8_t {
199 // Compiled into the trie fast path.
200 trie = 0,
201 // Safe static/":param"/"*" syntax beyond a fast-path build limit: matched
202 // by the sequential segment matcher.
203 sequential = 1,
204 // Needs URLPattern regexp semantics: matched through the regex provider.
205 regexp = 2,
206};
207
209struct route_record {
210 // Packed per-segment kinds, two bits per segment, most significant first;
211 // (kind_sequence, kind_length, route index) compared as a tuple is the
212 // specificity order.
213 uint64_t kind_sequence = 0;
214 // Sequential-mode routes: their segments in the segment table.
215 uint32_t segment_first = 0;
216 uint32_t segment_count = 0;
217 // Auxiliary routes that can outrank this route when it wins the fast
218 // path: a range of the aux table (usually empty).
219 uint32_t challenger_first = 0;
220 uint32_t challenger_count = 0;
221 // Ordinal among the regexp-mode routes, or -1.
222 int32_t regexp_component = -1;
223 uint8_t kind_length = 0;
224 route_mode mode = route_mode::sequential;
225 // Trie-mode routes: capture positions.
226 uint8_t n_params = 0;
227 uint8_t wild = 0;
228 std::array<uint8_t, url_pattern_list_limits::max_captures_per_route>
229 param_positions{};
230};
231
233struct segment_record {
234 uint32_t text_offset = 0;
235 uint32_t text_length = 0;
236 // 0 literal, 1 ":param", 2 "*".
237 uint8_t kind = 0;
238};
239
247struct compiled_routes {
248 std::vector<uint8_t> arena{};
249 std::vector<std::vector<std::string>> group_names{};
250 uint32_t nodes_offset = 0;
251 uint32_t hashes_offset = 0;
252 uint32_t edges_offset = 0;
253 uint32_t slots_offset = 0;
254 uint32_t blob_offset = 0;
255 uint32_t routes_offset = 0;
256 uint32_t segments_offset = 0;
257 uint32_t aux_offset = 0;
258 uint32_t root_index_offset = 0;
259 uint32_t n_routes = 0;
260 // All auxiliary routes (regexp mode and sequential mode) in insertion
261 // order: the aux table's first n_aux_all entries; challenger ranges
262 // follow.
263 uint32_t n_aux_all = 0;
264 uint8_t ignore_case = 0;
265
266 template <typename T>
267 [[nodiscard]] const T* section(uint32_t offset) const noexcept {
268 return reinterpret_cast<const T*>(arena.data() + offset);
269 }
270};
271
273struct engine_result {
274 using capture = url_pattern_list_match_result::capture;
275 int32_t route = -1;
276 uint32_t capture_count = 0;
277 // False when the input exceeded a fast-path limit and the caller must run
278 // the sequential fallback over the whole route set.
279 bool within_fast_path = true;
280 bool captures_truncated = false;
281 std::array<capture, url_pattern_list_limits::max_captures_per_route>
282 captures{};
283};
284
292tl::expected<compiled_routes, errors> compile_pathname_patterns(
293 std::span<const std::string> patterns, bool ignore_case);
294
303bool match_route_sequential(const compiled_routes& tables, uint32_t route,
304 std::string_view pathname, bool fold_input,
305 engine_result& result) noexcept;
306
318bool wildcard_tail_ok(const char* p, uint32_t n) noexcept;
319
328bool match_regexp_shape(const compiled_routes& tables, uint32_t route,
329 std::string_view pathname, bool fold_input) noexcept;
330
337constexpr bool outranks(uint64_t a_sequence, uint32_t a_length, size_t a_index,
338 uint64_t b_sequence, uint32_t b_length,
339 size_t b_index) noexcept {
340 if (a_sequence != b_sequence) {
341 return a_sequence < b_sequence;
342 }
343 if (a_length != b_length) {
344 return a_length < b_length;
345 }
346 return a_index < b_index;
347}
348
349} // namespace url_pattern_list_detail
350
351template <url_pattern_regex::regex_concept regex_provider>
352class url_pattern_list;
353
365template <url_pattern_regex::regex_concept regex_provider>
366ada_warn_unused tl::expected<url_pattern_list<regex_provider>, errors>
367parse_url_pattern_list(std::span<const std::string_view> pathname_patterns,
368 const std::string_view* base_url,
369 const url_pattern_options* options);
370
372template <url_pattern_regex::regex_concept regex_provider>
373ada_warn_unused tl::expected<url_pattern_list<regex_provider>, errors>
374parse_url_pattern_list(std::span<const url_pattern<regex_provider>> patterns);
375
414template <url_pattern_regex::regex_concept regex_provider>
415class url_pattern_list {
416 public:
417 url_pattern_list() = default;
418
425 [[nodiscard]] url_pattern_list_match_result match(
426 std::string_view pathname) const;
427
429 [[nodiscard]] size_t size() const noexcept { return patterns_.size(); }
430
433 [[nodiscard]] std::string_view pattern(size_t route_index) const
435 return patterns_[route_index];
436 }
437
443 [[nodiscard]] const std::vector<std::string>& group_names(
444 size_t route_index) const ada_lifetime_bound {
445 return compiled_.group_names[route_index];
446 }
447
449 [[nodiscard]] bool ignore_case() const noexcept {
450 return compiled_.ignore_case != 0;
451 }
452
453 friend tl::expected<url_pattern_list, errors>
454 parse_url_pattern_list<regex_provider>(
455 std::span<const std::string_view> pathname_patterns,
456 const std::string_view* base_url, const url_pattern_options* options);
457
458 friend tl::expected<url_pattern_list, errors> parse_url_pattern_list<
459 regex_provider>(std::span<const url_pattern<regex_provider>> patterns);
460
461 private:
464 static tl::expected<url_pattern_list, errors> create(
465 std::vector<std::string>&& pathname_patterns, bool ignore_case);
466
471 void consider_route(
472 uint32_t route_index, std::string_view pathname, std::string_view probe,
473 bool fold_input, url_pattern_list_detail::engine_result& best,
474 std::vector<std::optional<std::string>>& best_groups) const;
475
477 std::vector<std::string> patterns_{};
479 url_pattern_list_detail::compiled_routes compiled_{};
482 std::vector<url_pattern_component<regex_provider>> regexp_components_{};
483};
484
485} // namespace ada
486#endif // ADA_INCLUDE_URL_PATTERN
487#endif // ADA_URL_PATTERN_LIST_H
Cross-platform compiler macros and common definitions.
#define ada_lifetime_bound
#define ada_warn_unused
Definition common_defs.h:89
Error type definitions for URL parsing.
errors
Error codes for URL parsing operations.
Definition errors.h:17
ada::url_pattern_regex::std_regex_provider regex_provider
Definition url_pattern.cc:9
URLPattern API implementation.