- Generated by
1.9.8
|
REAL
Regular Expression Algorithmic Library — constexpr C++20 regex
|
The Pike VM, generic over the scratch-state container policy. More...
#include <pike.hpp>
Classes | |
| struct | cp_hi_cache_entry |
Cache entry for cp_hi_cached (thread-local, not on basic_pike_state). Keyed by a content fingerprint of the class (never a pointer into a program): programs die while this cache lives for the thread, and the allocator can recycle the same cp_ranges address for a different class — a pointer key then returns the wrong sparse table (false membership, e.g. emoji matching [\w€] after a prior high-range class was destroyed). Seen as a deterministic wrong-match on macos-clang CI after a long test binary has churned many classes (find_iter euro empty-alt pin). More... | |
| struct | cp_span |
One buffered cp_class_loop match: the whole-match span, which for this route is the whole answer (a capturing wrap mirrors it, and fill_span_slots reconstructs that). More... | |
| struct | slot_pair |
| A two-slot sink, for a filler that must call a route function expecting a slot container. More... | |
Public Member Functions | |
| constexpr | pike_vm (const program_view &prog, State &state) |
| Binds the VM to a program and caller-owned scratch state. | |
| template<bool Cascade = false, typename OutSlots > | |
| constexpr bool | run (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots, std::size_t forbid_empty_until=0, match_semantics sem=match_semantics::first) |
Runs the VM over text starting at start. | |
| template<bool Cascade = false, typename OutSlots > | |
| constexpr bool | run_general (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots, std::size_t *forward_stop=nullptr) |
The general Pike VM search loop (the match semantics), factored so the lazy-DFA routing can run it on the [s, e] window a two-pass DFA has located, and so the direct path can call it too. | |
| template<typename OutSlots > | |
| bool | confirm_at (std::string_view text, std::size_t s, OutSlots &out_slots, std::size_t &stop) |
Confirm a match anchored at s: find its end with the forward DFA and fill captures with the one-pass table — the same fast laddering the lazy-DFA route uses (§7.6/7.7), so the inner-literal confirm is not a raw Pike pass. Falls back to the anchored Pike when the pattern is not DFA/one-pass eligible, or when the forward DFA's leftmost match does not in fact begin at s (then the anchored Pike returns false and the caller advances). | |
| constexpr void | il_reset_on_new_haystack (std::string_view text) |
| Re-enables the inner-literal route and clears its density counters on a new haystack. | |
| template<typename OutSlots > | |
| bool | run_inner_literal (std::string_view text, std::size_t start, OutSlots &out_slots, bool &abandon, bool density_gate=true) |
The inner-literal search: memmem a required literal, reverse-match the prefix to the match start, forward-confirm — the reverse-inner protocol (regex-automata's ReverseInner). | |
| lookaround_scratch & | lookaround_state () |
| The lookaround sub-scratch, built on first use. | |
| template<bool Cascade, typename OutSlots > | |
| bool | run_class_loop_trailing_la (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
| Trailing-lookaround class+: body scan + longest end where lookaround holds. | |
| template<bool Cascade, bool WbEdge, bool WbKept> | |
| constexpr std::size_t | fill_class_spans (std::string_view text, std::size_t start, cp_span *out, std::size_t cap) |
Fills up to cap class_loop matches from start without leaving the route. | |
| constexpr std::size_t | fill_single_class_spans (std::string_view text, std::size_t start, cp_span *out, std::size_t cap) |
Fills up to cap bare single byte-class matches from start without leaving the route. | |
| template<bool WbEdge> | |
| constexpr std::size_t | fill_cp_class_spans (std::string_view text, std::size_t start, cp_span *out, std::size_t cap) |
Fills up to cap cp_class_loop matches from start without leaving the route. | |
| template<typename OutSlots > | |
| constexpr void | write_cp_span_slots (OutSlots &out_slots, std::size_t s, std::size_t e) |
| Writes a buffered span into a caller's slots exactly as the per-match path would. | |
| template<typename OutSlots > | |
| constexpr bool | run_cp_class_loop (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
Fast path for a whole-pattern code-point class klass_cp, optionally a greedy +. | |
| template<typename OutSlots , typename InClass , typename ScanEnd , typename LastWidth > | |
| constexpr bool | run_possessive_loop_generic (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots, const InClass &in_class, const ScanEnd &scan_end, const LastWidth &last_width) |
Shared driver: a possessive class+/++ loop, bare/suffixed (pattern_hints::possessive_prefix_size == 0) or delimited/"quoted" (non-zero) – the BODY's own class/cp-class membership test is supplied by in_class / scan_end so this one driver serves both the byte-class and the code-point-class runners below. | |
| template<typename OutSlots > | |
| constexpr bool | run_possessive_byte_loop (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
R2 (phase Raffinement): possessive literal-byte +/++ loop (byte_loop_possessive, e.g. a++) – the asymmetry class_ref's typing made natural to close: this opcode was already emitted and executed by the general VM, but had no dedicated recognizer or runner, so a++ fell back to the general VM despite the class/cp-class family already having one. See run_possessive_loop_generic for the shared algorithm. | |
| template<typename OutSlots > | |
| constexpr bool | run_possessive_class_loop (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
Possessive class+/++ loop over a BYTE class (klass_loop_possessive). See run_possessive_loop_generic for the shared algorithm. | |
| template<typename OutSlots > | |
| constexpr bool | run_possessive_cp_class_loop (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
Possessive class+/++ loop over a CODE-POINT class (klass_cp_loop_possessive). Mirrors run_cp_class_loop's decode/membership primitives, except that the scan predicate is now split by compiler (see in_class below): clang/MSVC read the ASCII table directly, gcc keeps the width round trip. Both directions are measured, and gcc's is the counter-intuitive one. See run_possessive_loop_generic for the shared algorithm. | |
| template<bool SkipSaves = false> | |
| constexpr std::size_t | match_byte_klass_run (std::string_view text, std::size_t pc, std::size_t s) const |
Matches the run of byte/klass instructions starting at pc. | |
| constexpr bool | wb_boundaries_ok (std::size_t s, std::size_t e) const |
O(1) lead/trail \b/\B check at match bounds [s, e). | |
| template<bool SkipSaves> | |
| constexpr std::size_t | match_fixed_body_wb (std::string_view text, std::size_t s) const |
Fixed-shape body match from pattern_hints::body_pc, then B1 \b/\B wrap. | |
| template<typename MatchAt , typename OutSlots > | |
| constexpr bool | fast_search (std::string_view text, std::size_t start, MatchAt match_at, OutSlots &out_slots) |
| Leftmost search by scanning candidate positions (first-byte hints). | |
| template<typename OutSlots > | |
| bool | run_pair_filtered_shape (std::string_view text, std::size_t start, OutSlots &out_slots) |
| Search route for a HETEROGENEOUS fixed shape: vector-prefilter two positions, verify each survivor with the ordinary fixed-body walk, hand the sub-block tail to fast_search. | |
| template<typename OutSlots > | |
| constexpr bool | run_fixed_shape (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
| Fast path for a whole-pattern fixed-width byte/klass sequence. | |
| template<typename OutSlots > | |
| constexpr void | fill_fixed_saves (std::size_t match_start, OutSlots &out_slots) const |
Fills the capturing-group slots of a fixed-shape match. Every consuming op is one byte wide, so each save sits at a constant offset from the match start; a single linear pass writes slot = match_start + offset. No-op when the pattern has no inner groups (slot_count 2). Not a re-match: the bytes were already verified. | |
| template<typename OutSlots > | |
| constexpr std::size_t | match_cp_shape (std::string_view text, std::size_t s, OutSlots &out_slots) const |
Verifies a fixed code-point shape forward from s, filling capture slots as it goes. | |
| template<typename OutSlots > | |
| constexpr void | fill_two_run_saves (std::size_t s, std::size_t h, std::size_t lit_end, std::size_t e, OutSlots &out_slots) const |
Fills capture slots for a class+ <literal> class+ match, by anchor rather than by offset. | |
| template<bool Cascade> | |
| constexpr std::size_t | fill_codepoint_class_spans (std::string_view text, std::size_t start, cp_span *out, std::size_t cap) |
Batched twin of run_codepoint_class — fills up to cap maximal spans in ONE call. | |
| template<bool Cascade, typename OutSlots > | |
| constexpr bool | run_codepoint_class (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
Fast path for . / a negated class, optionally a greedy +. | |
| template<typename OutSlots > | |
| bool | run_aho_corasick (std::string_view text, std::size_t start, OutSlots &out_slots) |
| Multi-literal search via the automaton ac_ready hands back, cached per regex in detail::regex_immutables. | |
| template<typename OutSlots > | |
| constexpr bool | run_alternation (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
| Fast path for an alternation of straight-line branches. | |
| constexpr std::size_t | fill_alternation_spans (std::string_view text, std::size_t start, cp_span *out, std::size_t cap) |
Fills up to cap fixed_alternation matches from start without leaving the route. | |
| std::size_t | fill_exact_literal_spans (std::string_view text, std::size_t start, cp_span *out, std::size_t cap) |
Fills up to cap exact-literal matches from start without re-entering the route gate. | |
| std::size_t | fill_inner_literal_spans (std::string_view text, std::size_t start, cp_span *out, std::size_t cap, bool &partial, bool &disarm) |
Fills up to cap inner-literal matches from start without re-entering the route gate. | |
| std::size_t | fill_lazy_dfa_spans (std::string_view text, std::size_t start, cp_span *out, std::size_t cap, bool &partial) |
Fills up to cap lazy-DFA matches from start without re-entering the route gate. | |
| constexpr bool | literal_at (std::string_view text, std::size_t cand, std::size_t len) const |
Tests whether the fixed literal prefix occurs at cand. | |
| template<typename OutSlots > | |
| constexpr bool | replay_literal (std::size_t cand, std::size_t len, OutSlots &out_slots) const |
Fills capture slots for a literal match at cand. | |
| template<typename OutSlots > | |
| bool | run_literal_one_search (std::string_view text, std::size_t start, std::size_t len, OutSlots &out_slots) |
| The whole exact-literal search in one find_prefix, for a pattern_hints::literal_one_search program (see run_exact_literal's own call site for why each per-match step of the general loop is redundant there). | |
| template<typename OutSlots > | |
| constexpr bool | run_exact_literal (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
| Fast path for a pure-literal pattern. | |
| constexpr std::size_t | next_candidate (std::string_view text, std::size_t pos, std::size_t start) const |
First position >= pos that could start a match, per the hints. | |
| constexpr bool | seed_viable (std::string_view text, std::size_t pos, std::size_t start) const |
Cheap pre-check before seeding a new thread at pos. | |
| constexpr bool | word_before (std::size_t pos, bool ascii_word) const |
Word-ness of the code point ending exactly at pos — the left side of a \b/\B/ \</\> boundary. False at the text start. In text mode it back-decodes the code point (up to three continuation bytes to the lead) and requires the sequence to end exactly at pos, so a malformed or misaligned run reads as non-word; bytes / re.A stay byte-level. This is the shared frontier notion (the same decode that codepoint alignment uses). | |
| constexpr bool | word_after (std::size_t pos, bool ascii_word) const |
Word-ness of the code point starting at pos — the right side of a boundary. False at the text end or on a malformed sequence; bytes / re.A stay byte-level. | |
| constexpr bool | assertion_holds (assert_kind kind, std::size_t pos, bool word_ness_flipped) const |
Evaluates a zero-width assertion at pos in the current text. | |
| template<typename OutSlots > | |
| constexpr void | step (list_type &clist, list_type &nlist, std::size_t pos, run_mode mode, bool &matched, OutSlots &out_slots) |
Advances every thread of clist by the byte at pos. | |
| constexpr void | tier1_capture_on_match (list_type &clist, std::size_t i, std::int32_t capture_start_slot, std::size_t start, std::size_t end) |
Tier 1's on-match capture write: if capture_start_slot is not -1, records [start, end) into thread i's capture block, in place. | |
| constexpr void | advance_thread (list_type &clist, list_type &nlist, std::size_t i, std::int32_t next_pc, std::size_t next_pos) |
Advances thread i of clist by one consumed byte, seeding its continuation's closure into nlist (COW). The closure takes its own reference on the thread's capture block — no slot copy; the block is shared until a save copies it on write. | |
| constexpr const std::size_t * | thread_slots (list_type &clist, std::size_t i) |
Pointer to thread i's slot_count capture values — its COW block's slots (COW). Used by the match case to read out the winner. | |
| constexpr bool | cp_class_matches (const detail::cp_class &cc, char32_t cp) const |
Tests a decoded code point against a klass_cp class: ASCII bitmap below 0x80; above, cp_member_hi when a class index is known at runtime (page + sparse hi table), else pure binary search of the class's range slice (constexpr / const paths). The class is already the effective set, so this is a plain positive membership test. | |
| constexpr bool | cp_class_matches_idx (std::size_t cp_index, char32_t cp) |
| Membership by class index (ASCII + European page + sparse hi / bsearch). | |
| constexpr void | add_thread (list_type &list, std::int32_t pc0, std::size_t pos, std::size_t initial) |
Adds pc0 and its whole epsilon closure to list — the one closure walk (COW). Each DFS frame carries a capture-block index (in eps_entry::block) rather than mutating a shared working array, so capture state is copy-on-write and there are no slot-restore entries: | |
| constexpr void | cow_release_blocks (list_type &list) |
| Releases the block references a list's threads hold (COW), before the list is reset or the run returns. This is the one decref site paired with the incref at each step→closure boundary — the classic double-free locus, kept single. | |
| constexpr bool | lookaround_holds (std::uint16_t sub_id, std::size_t pos) |
Evaluates a bounded lookaround at pos (true if the thread should proceed). | |
| constexpr bool | single_class_ahead (const instr &body, std::size_t pos) |
L1 peephole — does the single consuming op body match the code point / byte AT pos (ahead)? Mirrors the per-op logic of lookahead_matches for a one-instruction sub-program. | |
| constexpr bool | single_class_behind (const instr &body, std::size_t pos) |
L1 peephole — does body match the code point / byte ending EXACTLY at pos (behind)? The defining lookbehind trap: the match must END at pos, so the code point is the one whose aligned start s gives s + length == pos (byte mode: pos - 1). | |
| constexpr bool | lookahead_matches (const lookaround_sub &sub, std::size_t pos) |
Lookahead: does the sub-pattern match a prefix starting at pos? | |
| constexpr bool | lookbehind_matches (const lookaround_sub &sub, std::size_t pos) |
Lookbehind: does the sub-pattern match a window ENDING EXACTLY at pos? | |
| constexpr bool | sub_fullmatch_window (std::int32_t code_offset, std::size_t start, std::size_t pos) |
Reports whether the sub-program, run from start, reaches match EXACTLY at pos (a fullmatch of [start, pos)), on the isolated sub-scratch. | |
| constexpr void | sub_add_thread (thread_list &list, std::int32_t pc0, std::size_t pos, bool &matched) |
| Epsilon-closure for the lookaround sub-VM, on the isolated sub-scratch. | |
Static Public Member Functions | |
| static constexpr bool | exact_literal_is_the_route (const pattern_hints &hints) noexcept |
Is the exact-literal route the one run() would take, in its one-search subset? | |
| static constexpr bool | inner_literal_is_the_route (const program_view &prog) noexcept |
Is the inner-literal route the one run() would take for this program? | |
| static constexpr bool | lazy_dfa_is_the_route (const pattern_hints &hints) noexcept |
Is the lazy-DFA route the one run() would actually take for this program? | |
Static Public Attributes | |
| static constexpr std::size_t | lazy_dfa_min_input {512} |
| Below this input length the lazy-DFA routing is skipped (the two-pass setup does not amortise on a short subject — the Pike VM goes direct). A measured, documented threshold. | |
Private Types | |
| using | list_type = std::remove_reference_t< decltype(std::declval< State & >().list_a)> |
The concrete thread-list type taken from the bound State. | |
| using | pool_type = std::remove_reference_t< decltype(std::declval< State & >().pool)> |
The capture-block pool type of the bound State (COW) — heap-backed for dynamic, compile-sized static_vec for static. The one capture-slot mechanism, both storages. | |
Private Member Functions | |
| bool | ac_candidate_completes (std::string_view text, std::size_t at) |
Does a branch of the alternation COMPLETE at at? | |
| template<typename Dummy = void> | |
| bool | ac_density_favours_automaton (std::string_view text, std::size_t start) |
| Decides ONCE PER HAYSTACK whether the Aho-Corasick automaton should take this alternation's searches, by sampling candidate density at the search start. | |
| void | ensure_immutables () |
Build (or rebuild) the per-regex immutables, race-free: the Tier-A byte-program the DFAs run over (and its shared alphabet), plus the one-pass extractor. Invalidation is by program identity (regex_immutables::built_for == prog_.code.data()) — same pattern as state_type::dfa_program / il_prefix_for. Hot path is one atomic load; a spent once_flag would never rebuild after assign-onto-warmed (silent 0 matches). The extractor is Tier-B (assertions kept), so one table serves the search window and anchored match/fullmatch. Needs no DFA, so the anchored path can call this without the DFA build. | |
| void | ensure_op_table () |
| Build (or rebuild) the one-pass capture extractor, on top of ensure_immutables. | |
| void | ensure_slot_search_dfas_unlocked (detail::regex_immutables &immut, shared_dfa_slot &slot) |
Warm shared search DFAs for immut into slot (caller holds slot.mu). | |
| void | ensure_slot_il_prefix_rev_unlocked (detail::regex_immutables &immut, shared_dfa_slot &slot) |
Warm shared IL-prefix reverse DFA (caller holds slot.mu). | |
| template<typename Fn > | |
| bool | with_search_dfas (Fn &&fn) |
Run fn with the shared search DFAs under the slot lock. | |
| template<bool Cascade, typename OutSlots > | |
| std::optional< bool > | try_shared_lazy_dfa_search (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
Lazy-DFA search route on the shared confirm DFAs. noinline so its body cannot inflate run (x86 class-loop codegen neighbor — same shape as ac_ready). | |
| template<typename Dummy = void> | |
| const ac_automaton * | ac_ready () |
Build (or rebuild, on a program change) this iterator's Aho-Corasick automaton for a fixed_alternation program whose branch count has reached ac_branch_threshold. | |
| constexpr bool | row_key_stale (std::int32_t have, std::int32_t want) const |
Is the state's cached row key stale for want? | |
| void | verify_class_row (detail::regex_immutables &cache, std::size_t class_index) |
Verifies (and if needed fills) the byte row for class_index, then caches it in the state. | |
| constexpr const std::uint8_t * | derive_class_table (std::size_t class_index) |
| Derives the byte row into the VM state — the constant-evaluation path, where no per-regex cache exists. | |
| void | ensure_membership_rows (detail::regex_immutables &cache) const |
| Sizes the per-regex membership rows for this program, if they are not already. | |
| void | fill_class_row (detail::regex_immutables &cache, std::size_t class_index) const |
| Fills one byte-class row of the per-regex cache, once. | |
| void | fill_cp_ascii_row (detail::regex_immutables &cache, std::size_t cp_index) const |
| Fills one code-point-class ASCII row of the per-regex cache, once. | |
| void | fill_cp_page_row (detail::regex_immutables &cache, std::size_t cp_index) const |
| Fills one U+0080..U+07FF membership bitmap of the per-regex cache, once. | |
| constexpr const std::uint8_t * | class_table (std::size_t class_index) |
Returns a flat 256-byte membership table for class class_index. | |
| template<bool Cascade, typename OutSlots > | |
| constexpr bool | run_class_loop_anchored (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
Cold half of the class-loop route: everything a \A/^ or \Z/$ implies. | |
| template<typename OutSlots > | |
| constexpr bool | run_class_loop_end_anchored (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
X+$ / ^X+$ in search mode: the run that ENDS at the anchor, found by walking back. | |
| constexpr const std::uint8_t * | resolve_class_table (std::size_t class_index) |
| Cold half of class_table — the storage-mode resolution, and the only path that writes the state's row cache for a byte class. | |
| constexpr const std::uint8_t * | cp_ascii_table (std::size_t cp_index) |
Byte-indexed membership table for a cp_class's ASCII bitmap — the same one-load trick as class_table, for the klass_cp scan-loop fast path. Keyed negatively so it never collides with a class_table key (a whole-pattern shorthand has no byte-NFA classes, so the two never interleave for one pattern anyway). | |
| constexpr bool | cp_class_holds (const cp_class &cc, char32_t cp) const |
Stateless membership of cp in cc — no VM-state cache touched. | |
| constexpr const std::uint64_t * | cp_page_table (std::size_t cp_index) |
Builds (once, cached) and returns the cp_class's membership bitmap over [U+0080, U+07FF] — a one-load replacement for the range search on the common two-byte code points (see basic_pike_state::cp_page). | |
| constexpr bool | cp_member_page (std::size_t cp_index, char32_t cp) |
Page-bitmap membership for U+0080..U+07FF. Kept separate so class-loop lambdas can inline it without pulling the sparse-hi path into the European hot stream (\p{N}, accented). | |
| constexpr bool | cp_member_high (std::size_t cp_index, char32_t cp) |
| Membership for cp > U+07FF: sparse 2-stage hi table, else bsearch (small classes / constexpr). The table build is cold-outlined; the per-cp probe is last-hit + bit test. | |
| void | resolve_hi (std::size_t cp_index) |
Fills the state's sparse-hi memo for cp_index — the cold half of cp_member_high. | |
| constexpr bool | cp_member_hi (std::size_t cp_index, char32_t cp) |
| Non-ASCII membership: European page bitmap, then sparse 2-stage hi / bsearch. | |
| template<typename OutSlots > | |
| constexpr void | fill_span_slots (OutSlots &out_slots, std::size_t match_start, std::size_t match_end) const |
Writes a class-loop fast-path result into out_slots: the whole-match span in slots 0/1, and — for a pattern wrapped in one capturing group ((\w+), ([a-z]+)) — the same span mirrored into the group's slots (its span equals the whole match by construction, so no re-match is needed). | |
| constexpr std::size_t | run_cascade_stop (std::string_view text, std::size_t from) const |
The memchr-cascade run tail: the next stop byte at or after from, or the text end. Kept in its own function so the memchr-cascade never inlines into run_class_loop's hot per-byte loop (that bloat measurably slowed stop-dense short runs). Reached only once a run has already passed cascade_run_threshold accepted bytes, so the out-of-line call is free. | |
| template<bool Cascade, typename OutSlots > | |
| constexpr bool | run_class_loop (std::string_view text, std::size_t start, run_mode mode, OutSlots &out_slots) |
| Fast path for a whole-pattern "class+". | |
Static Private Member Functions | |
| static void | fill_byte_row (detail::regex_immutables &cache, std::size_t ready_index, const char_class &klass, std::uint8_t *row) |
Expands klass into one flat 256-byte membership row of the per-regex cache, once. | |
| static const cp_hi_table * | cp_hi_build (const program_view &prog, std::size_t cp_index, std::uint64_t key_fp, std::array< cp_hi_cache_entry, 8 > &cache, const cp_hi_table *&last_tab, std::uint64_t &last_fp) |
| Cold path: build a sparse hi table and install it in the thread-local cache. Outlined so the hot membership check never inlines the range-walk builder. | |
| static const cp_hi_table * | cp_hi_cached (const program_view &prog, std::size_t cp_index) |
Thread-local sparse hi tables, keyed by cp_class::fingerprint (set once at intern). Hot path: load uint64 + sticky compare (cheap, like the pre-poisoning pointer key) — never re-hash ranges per codepoint. Keeps basic_pike_state sizeof unchanged. | |
| template<typename OutSlots > | |
| static constexpr void | ensure_slot_size (OutSlots &out, std::size_t n) |
Size out without a full npos fill when already sized. | |
Private Attributes | |
| const program_view & | prog_ |
| The program being executed (borrowed; a stable lvalue that outlives the VM). | |
| State & | state_ |
| Borrowed reusable scratch state. | |
| std::string_view | text_ |
| The subject text for the current run. | |
| std::size_t | forbid_empty_until_ {} |
| Reject empty matches whose start is below this offset. | |
| match_semantics | sem_ {match_semantics::first} |
| Match semantics for the current run (match_semantics::first by default; match_semantics::longest is the experimental opt-in). Read by step and the fast-path routing. | |
Static Private Attributes | |
| static constexpr std::uint32_t | il_density_probe_candidates {8} |
| Density-gate sample size and threshold (inner-literal → core/DFA when candidate density is high). | |
| static constexpr std::size_t | il_density_milli_threshold {60} |
| Candidate density, in candidates per 1000 bytes, at or above which the IL route yields to the DFA. | |
| static constexpr std::size_t | ac_density_sample_bytes {256} |
| AC routing: sample window, and the candidate-work product at or above which the automaton beats the memchr cascade. | |
| static constexpr std::size_t | ac_density_min_span {64} |
| Shortest span an early verdict may rest on. | |
| static constexpr std::size_t | ac_density_work_threshold {550} |
Product (candidates per 1000 bytes) * branch_count at or above which the automaton wins, at or above ac_branch_threshold branches. | |
| static constexpr std::uint16_t | ac_branch_floor {4} |
| Fewest branches the automaton is ever considered for; below this nothing is measured. | |
| static constexpr std::size_t | ac_completion_pct {15} |
| Percentage of sampled candidates that may COMPLETE a branch and still leave the automaton ahead. Above it the cascade wins whatever the candidate density says. | |
| static constexpr std::size_t | ac_density_work_threshold_low {1400} |
| The same product for ac_branch_floor .. ac_branch_threshold branches, where the safe direction is reversed. | |
| static constexpr std::uint16_t | ac_branch_threshold {12} |
| Branch count of a pattern_hints::fixed_alternation at or above which a single Aho-Corasick automaton walk beats pattern_hints::small_set's 2..8-member memchr-cascade scan (which has no fast path at all past 8 distinct first bytes). Measured against the wired engine (through the route's own disable toggle) on two corpus shapes — mostly-non-matching prose and majority-matching text. Just below this count the automaton already wins on the match-heavy corpus while still LOSING on prose; at this count it wins on both with no measured regression. 12, not 11, so the gate matches its own contract — AC BEATS the VM-branch path at the threshold, not roughly ties it (measured; the the N=10 repro stays correctly below threshold either way, AC/VM=1.16x there against the standalone POC — inside the closed-gap target of <=~1.5x). | |
| static constexpr std::uint32_t | cp_page_max {0x7FFU} |
Highest code point covered by the cp_page bitmap (the 2-byte UTF-8 range). | |
| static constexpr int | max_loop_hops {8} |
| Cap on how far a jump chain is followed to a loop head (empty-iteration exit routing); a loop join reaches its split in one hop, so this is a generous bound, never a hot cost. | |
| static constexpr std::size_t | cascade_run_threshold {32} |
Accepted-byte count after which a class+ run switches from the per-byte advance to a memchr-cascade to the next stop byte. Below it a run pays nothing extra, so a stop-dense stream of short runs stays at baseline cost; the crossover is measured. | |
| static constexpr std::uint32_t | cp_hi_range_threshold {20U} |
| Below this many total ranges, high-cp membership stays on bsearch (small scripts). Re-measured after this value stood at 32 on the strength of a quasi-tie: at 32 the two classes that straddle it are NOT a tie, they pull opposite ways: the one just above wants the sparse table on both ISAs, the one just below wants bsearch. So the crossover lies between them, and this constant is that GAP rather than either measurement – raising it past the upper class costs that class, lowering it past the lower one costs the other. Dense classes sit far above and are unreachable by any value here; they are the control, flat across the change, which is what makes the gain readable as this decision's own. | |
The Pike VM, generic over the scratch-state container policy.
| State | A basic_pike_state instantiation (vector- or static-backed). |
| StateBoundToProgram | The caller guarantees this state is never used with a second program — it is either freshly constructed for this search or owned by a walk over one regex. The membership-row accessors then need no program-identity compare: a fresh state's table_class is already -1, so a row key matching is proof on its own. That compare is per run(), and run() is per MATCH on a walk (11 327 times over 64 KiB on [a-z]+), which measured 2.9 points of that walk. Defaults to false: an embedder holding a state across regexes (the Python binding, the meta-seam harness) must keep the compare. |
|
inlineconstexpr |
Binds the VM to a program and caller-owned scratch state.
| [in] | prog | The compiled program to execute. |
| [in,out] | state | Reusable scratch (borrowed; must outlive the VM). |
|
inlineprivate |
Does a branch of the alternation COMPLETE at at?
The gate's second quantity needs to tell a false start from a match, and a candidate is only a head byte until something is tried at it. This walks the split chain in source order and asks match_byte_klass_run for each branch, exactly as run_alternation and fill_alternation_spans do – one attempt per branch, no thread lists, no capture work.
A COPY of that walk rather than a call into one, for the reason fill_alternation_spans states about its own: both routes are measured and working, and relocating a hot body to share it risks a regression there that would cost more than this gate can win. Twelve lines, and the three copies agree by construction because they ask the same primitive in the same order.
| [in] | text | The subject. |
| [in] | at | A candidate position (a branch head byte occurs there). |
at.
|
inlineprivate |
Decides ONCE PER HAYSTACK whether the Aho-Corasick automaton should take this alternation's searches, by sampling candidate density at the search start.
Sticky, for the same reason pike_state::il_abandoned is: find_iter re-enters search() once per match, and on a match-dense subject each of those searches ends almost immediately, so a decision re-derived per search would never see the density that makes the automaton win – and would pay for the sample every time. Keyed on the subject's data pointer, like every other per-haystack guard in this file.
Sampling rather than an abandon predicate threaded through fast_search – the two designs measure the same quantity, but the abandon predicate has to cross fast_search, which has four call sites across the fixed-shape, class-loop and alternation routes, and the SIMD small_set block loop besides. This one touches nothing any other route executes. It reuses next_candidate, so "candidate" means exactly what it means to the cascade being measured – a second definition would be a second thing to keep true.
| [in] | text | Subject. |
| [in] | start | Where this search begins; the window is measured from here. |
true when the automaton should take over. Storages without the guard fields (the compile-time scratch) answer true unconditionally, preserving their behaviour.
|
inlineprivate |
Build (or rebuild, on a program change) this iterator's Aho-Corasick automaton for a fixed_alternation program whose branch count has reached ac_branch_threshold.
search(), so crossing ac_branch_threshold rebuilt the automaton on every call and made repeated search ~200x SLOWER rather than faster — orders of magnitude, with hundreds of heap allocations, against a 3-branch alternation below the gate on the same subject, and find_iter offered no rescue. Moving it here removed the rebuild and the allocations entirely. Its identity atomic is its own, never folded into built_for: only this route consults it, and that cache's history records what bundling a route-specific product into the shared flag cost every other route.The per-state build is KEPT as the fallback for a null prog_.immut — the compile-time storage and the meta-seam harness — and that is load-bearing rather than tidy. Declining the route instead would leave tests/engine/test_fastpath_seam_matrix.cpp's seam_run_aho_corasick agreeing with itself on the general-VM leg and exercising nothing: a green differential testing neither side, which is the failure this engine spent v2026.7.62 removing.
Reconnaissance for whoever builds it, so the shape is not re-derived. No static property can select correctly: AC's cost is flat while the cascade's swings by three orders of magnitude on the same pattern, so only the SUBJECT decides, and only at run time. The engine already has the right shape for that and it is not a threshold — the inner-literal route starts on memmem and ABANDONS mid-scan when candidate density betrays a bad haystack (pike_state::il_density_cands, pike_state::il_abandoned, sticky per subject, pinned by tests/engine/test_il_density_gate.cpp). Adapting that would delete ac_branch_threshold rather than retune it, which is the point: a threshold that gets adjusted is a threshold that will be adjusted again.
The obstacle is where the counter has to live. Alternation search has three scan paths, and the false-start regime measured above takes none of the obvious one: with a shared prefix the branches collapse to single_first, with 24 distinct heads to the first_bytes bitmap — both inside fast_search — and only 2..8 distinct heads reach the L-SIMD small_set block loop. fast_search verifies candidates through a callback that cannot return from its caller, and it has four call sites across the fixed-shape, class-loop and alternation routes. So the first step is to give it an OPTIONAL abandon predicate, unwired by default, leaving the other three routes unchanged by construction; then wire the counter to alternation alone, with a budget scaled to the subject (the automaton's flat per-byte rate against the cost of a missed candidate in the bad regime, which sets the order of magnitude); then re-run the full matrix on both platforms, since it is the matrix that has to validate the result.
| Dummy | Never named by a caller. A member TEMPLATE is instantiated only where it is actually called, and this one has a single if constexpr-gated call site — so the copies for pike_vm instantiations that never take the route are not emitted at all, instead of being emitted and counted as wholly uncovered. |
nullptr when this program has none — either it is not a fixed alternation past the threshold, or the build declined a pathological icase-fold expansion. The caller falls back to run_alternation, zero behaviour change. Declines (returns nullptr) if any branch's icase-fold expansion would exceed ac_max_branch_expansion — the caller falls back to the existing run_alternation, zero behavior change. Runs once per iterator/program, off the hot path, mirroring with_search_dfas's cache-by-program-pointer contract.noinline, deliberately NOT cold (round-2 x86 isolation A/B: neither the pattern_hints field alone nor the pike_state size growth alone regressed the non-alternation hot-corpus witnesses, isolating the cause to code called directly from run()'s own dispatch chain — a codegen-neighbor/inlining-bloat effect on run_class_loop, which shares the same translation unit and physically returns before ever reaching this call at runtime, so it's presence, not execution, doing the damage). cold would additionally deprioritize this function's OWN optimization — wrong here, since it (unlike the actual construction work in aho_corasick.hpp, already marked cold) is called on every AC-eligible search, not just once per program. noinline alone keeps it fully optimized while stopping the compiler from folding its body into run()'s.
|
inlineconstexpr |
Adds pc0 and its whole epsilon closure to list — the one closure walk (COW). Each DFS frame carries a capture-block index (in eps_entry::block) rather than mutating a shared working array, so capture state is copy-on-write and there are no slot-restore entries:
split shares (incref: one ref → the two pushed frames), jump transfers it;save — the ONLY write — copies-on-write first if the block is shared (capture_pool::cow_write);| [in,out] | list | The thread list to populate (its slots hold one block index per pc). |
| [in] | pc0 | The program counter to seed from. |
| [in] | pos | The current input position. |
| [in] | initial | What the seed carries: capture-free, group 0's START — full width, which is why this is a std::size_t and not the std::uint32_t an eps_entry field would have been. Otherwise the block the walk starts on, on which the caller passes an already-owned ref. |
|
inlineconstexpr |
Advances thread i of clist by one consumed byte, seeding its continuation's closure into nlist (COW). The closure takes its own reference on the thread's capture block — no slot copy; the block is shared until a save copies it on write.
| [in] | clist | Current list, holding the thread to advance. |
| [in,out] | nlist | Next list, receiving the continuation's closure. |
| [in] | i | Thread index within clist. |
| [in] | next_pc | Program counter the thread continues at. |
| [in] | next_pos | Text position the thread continues at. |
|
inlineconstexpr |
Evaluates a zero-width assertion at pos in the current text.
| [in] | kind | The assertion to evaluate. |
| [in] | pos | The position at which to evaluate it. |
| [in] | word_ness_flipped | For a word assert (\b \B \< \>), whether this instruction flips the program's default word-ness — set for a scoped (?a:...) / (?-a:...) island. |
true if the assertion holds there.
|
inlineconstexprprivate |
Returns a flat 256-byte membership table for class class_index.
Materializes the class bitmap into a byte-indexed table the first time it is requested, caching it in the shared scratch so a find_all-style walk builds it once. In a tight per-byte scan, table[b] (one load) replaces the bitmap's shift-and-mask — the byte-classification trick of DFA/JIT engines, measured ~2x faster on the class-scanning fast paths.
| [in] | class_index | Index into the program's interned classes. |
Forced inline, and the attribute is load-bearing: left to its own judgement the compiler emits this out of line, where the call frame alone costs more than the whole accessor does inlined — 6.2 M instructions against 0.85 M on a 64 KiB [a-z]+ walk. It only fits once derive_class_table is kept out of it, which is what that function's own attribute is for.
|
inline |
Confirm a match anchored at s: find its end with the forward DFA and fill captures with the one-pass table — the same fast laddering the lazy-DFA route uses (§7.6/7.7), so the inner-literal confirm is not a raw Pike pass. Falls back to the anchored Pike when the pattern is not DFA/one-pass eligible, or when the forward DFA's leftmost match does not in fact begin at s (then the anchored Pike returns false and the caller advances).
| [in] | text | Subject. |
| [in] | s | Candidate match start to confirm. |
| [out] | out_slots | Capture slots, filled on a match. |
| [out] | stop | How far the confirm reached, for the linearity backstop. |
s.
|
inlineconstexpr |
Releases the block references a list's threads hold (COW), before the list is reset or the run returns. This is the one decref site paired with the incref at each step→closure boundary — the classic double-free locus, kept single.
| [in] | list | List whose threads' block references are dropped. |
|
inlineconstexprprivate |
Byte-indexed membership table for a cp_class's ASCII bitmap — the same one-load trick as class_table, for the klass_cp scan-loop fast path. Keyed negatively so it never collides with a class_table key (a whole-pattern shorthand has no byte-NFA classes, so the two never interleave for one pattern anyway).
| [in] | cp_index | Index into the program's cp_classes. |
|
inlineconstexprprivate |
Stateless membership of cp in cc — no VM-state cache touched.
The cached paths (cp_member_page, cp_member_high) hold ONE class each in the state, which is right for a scan that stays on one class. The inner-literal reverse alternates with the confirm's classes on every candidate, so it reads the class directly: the ASCII bitmap for cp < 0x80 (the overwhelming case), and a binary search of the class's own range span above it.
| [in] | cc | The code-point class. |
| [in] | cp | The code point. |
true if cp is a member.
|
inlineconstexpr |
Tests a decoded code point against a klass_cp class: ASCII bitmap below 0x80; above, cp_member_hi when a class index is known at runtime (page + sparse hi table), else pure binary search of the class's range slice (constexpr / const paths). The class is already the effective set, so this is a plain positive membership test.
| [in] | cc | The code-point class (from prog_.cp_classes). |
| [in] | cp | The decoded code point. |
cp is a member.
|
inlineconstexpr |
Membership by class index (ASCII + European page + sparse hi / bsearch).
| [in] | cp_index | Index of the code-point class. |
| [in] | cp | The decoded code point. |
cp is a member.
|
inlinestaticprivate |
Cold path: build a sparse hi table and install it in the thread-local cache. Outlined so the hot membership check never inlines the range-walk builder.
| [in] | prog | Program owning the class. |
| [in] | cp_index | Index of the code-point class in prog.cp_classes. |
| [in] | key_fp | The class's content fingerprint, the cache key. |
| [in,out] | cache | Thread-local entries, one of which is overwritten. |
| [out] | last_tab | Sticky last-hit table pointer, set to the built table. |
| [out] | last_fp | Sticky last-hit fingerprint, set to key_fp. |
cache.
|
inlinestaticprivate |
Thread-local sparse hi tables, keyed by cp_class::fingerprint (set once at intern). Hot path: load uint64 + sticky compare (cheap, like the pre-poisoning pointer key) — never re-hash ranges per codepoint. Keeps basic_pike_state sizeof unchanged.
| [in] | prog | Program owning the class. |
| [in] | cp_index | Index of the code-point class in prog.cp_classes. |
|
inlineconstexprprivate |
Non-ASCII membership: European page bitmap, then sparse 2-stage hi / bsearch.
| [in] | cp_index | Index of the code-point class. |
| [in] | cp | Code point at or above U+0080. |
cp is a member.
|
inlineconstexprprivate |
Membership for cp > U+07FF: sparse 2-stage hi table, else bsearch (small classes / constexpr). The table build is cold-outlined; the per-cp probe is last-hit + bit test.
| [in] | cp_index | Index of the code-point class. |
| [in] | cp | Code point above cp_page_max. |
cp is a member.
|
inlineconstexprprivate |
Page-bitmap membership for U+0080..U+07FF. Kept separate so class-loop lambdas can inline it without pulling the sparse-hi path into the European hot stream (\p{N}, accented).
| [in] | cp_index | Index of the code-point class. |
| [in] | cp | Code point in U+0080..U+07FF; outside that range the bit index is meaningless. |
cp is a member.
|
inlineconstexprprivate |
Builds (once, cached) and returns the cp_class's membership bitmap over [U+0080, U+07FF] — a one-load replacement for the range search on the common two-byte code points (see basic_pike_state::cp_page).
| [in] | cp_index | Index into the program's cp_classes. |
cp - 0x80).
|
inlineconstexprprivate |
Derives the byte row into the VM state — the constant-evaluation path, where no per-regex cache exists.
The attribute is load-bearing, for the same reason as verify_class_row and more so: this is the body that holds the 256-iteration loop, so inlined back into class_table it is what makes that accessor too large to enter basic_match_iterator::advance. Splitting the function out without the attribute buys nothing — the compiler simply undoes it, and class_table is emitted out of line at 6.2 M instructions against 0.85 M inlined on a 64 KiB [a-z]+ walk.
| [in] | class_index | Index into the program's interned byte classes. |
|
inlineprivate |
Sizes the per-regex membership rows for this program, if they are not already.
Outlined and cold: it runs once per regex, behind an acquire load on the hot path.
| [in,out] | cache | The per-regex immutables. |
|
inlineprivate |
Build (or rebuild) the one-pass capture extractor, on top of ensure_immutables.
Split out of ensure_immutables because it is the expensive half and only some callers need it. On a first search over a capture pattern this half dominates the cache – more than the byte program and the lazy DFA together. Bundled, every route that wanted only the byte program paid all of it, including a capture-free pattern: a 2-slot twin with nothing to extract measured the same first search as its 6-slot original. So the split is not a micro-optimisation: it stops a search from building a capture extractor it cannot consult.
Guarded by its own regex_immutables::op_table_for, exactly as the membership rows are guarded by rows_for and for the same reason – an identity independent of built_for, because this is needed by a different subset of routes. ensure_immutables clears both the extractor and this flag when it rebuilds, so a reassigned regex cannot read one built for the previous program.
|
inlineprivate |
Warm shared IL-prefix reverse DFA (caller holds slot.mu).
| [in] | immut | Per-regex immutables naming the program to build for. |
| [in,out] | slot | Process-wide DFA slot to populate. |
|
inlineprivate |
Warm shared search DFAs for immut into slot (caller holds slot.mu).
| [in] | immut | Per-regex immutables naming the program to build for. |
| [in,out] | slot | Process-wide DFA slot to populate. |
|
inlinestaticconstexprprivate |
Size out without a full npos fill when already sized.
Production storage has ensure_size; seam tests pass std::vector (resize is enough — it does not re-fill existing elements).
| [in,out] | out | Slot storage to grow. |
| [in] | n | Minimum size required; out is never shrunk. |
|
inlinestaticconstexprnoexcept |
Is the exact-literal route the one run() would take, in its one-search subset?
Mirrors run()'s cascade for the same reason lazy_dfa_is_the_route does. Only three kinds of route sit ABOVE this one – the byte-class loop, the code-point class loop, and the three possessive loops – so the list is short; everything below it (inner literal, fixed shape, the DFAs) is territory this route already wins and must keep.
The literal_one_search bit carries the rest by itself: it is set only when the program has no capture, no assertion, no anchor, a literal of two bytes or more, and prefix_size == exact_literal_len. That is exactly the subset where the answer is find_prefix plus two stores, with nothing to confirm and no occurrence to retry.
| [in] | hints | The program's shape hints. |
|
inlineconstexpr |
Leftmost search by scanning candidate positions (first-byte hints).
Shared by the fast paths that verify a fixed shape at a position: it walks candidate starts via next_candidate and reports the first that match_at accepts.
| MatchAt | Callable std::size_t(std::size_t pos) returning the match end at pos, or npos. |
| OutSlots | Output slot container (already sized to two). |
| [in] | text | The subject text. |
| [in] | start | Index to begin at. |
| [in] | match_at | The per-position matcher. |
| [out] | out_slots | Receives the (start, end) span on success. |
true if a match was found.
|
inlineconstexpr |
Fills up to cap fixed_alternation matches from start without leaving the route.
The measurement that motivates it is recorded on run_alternation – holding the pattern and the bytes fixed and varying only how often a match must be emitted fits a per-match constant of return against a whole-subject scan cost that is negligible beside it. This route was even more return-dominated than the class routes the same filler treatment already rescued.
Scope is the SMALL-SET shape only (2..8 distinct branch first bytes, pattern_hints::small_set_size), which is what the mask scan below needs. An alternation outside that range takes run_alternation's fast_search fallback, and the caller declines to batch it rather than have this body grow a second scan – adding bodies to this translation unit is the change shape that charged unrelated rows repeatedly during the batching work (docs/MEASUREMENT.md §5.4).
The scan is deliberately a COPY of run_alternation's rather than a refactor of it. Both were available; the existing route is measured and working, and relocating its hot body risks a regression there that would be worse than this filler's whole gain. If the duplication proves costly on either instrument, the refactor is the fallback, not the other way round.
| [in] | text | The subject. |
| [in] | start | Where to begin. |
| [out] | out | Buffer for the spans found. |
| [in] | cap | Capacity of out; the walk stops there and resumes from the last end. |
|
inlinestaticprivate |
Expands klass into one flat 256-byte membership row of the per-regex cache, once.
The shared body of fill_class_row and fill_cp_ascii_row, which differed only in which char_class they read, which array they wrote, and the offset their ready-bit sits at. Both are noinline, cold and reached only through the once-per-class miss path, so collapsing them costs nothing at run time and stops a fix from landing on one of two copies. fill_cp_page_row is deliberately NOT folded in: it builds a 30-word bitmap over a code-point page from range pairs, sharing only the lock-and-ready-bit frame.
| [in,out] | cache | The per-regex immutables. |
| [in] | ready_index | Index of this row's ready bit. |
| [in] | klass | The membership set to expand. |
| [out] | row | Destination, 256 bytes. |
|
inlineprivate |
Fills one byte-class row of the per-regex cache, once.
| [in,out] | cache | The per-regex immutables. |
| [in] | class_index | Index into the program's interned byte classes. |
|
inlineconstexpr |
Fills up to cap class_loop matches from start without leaving the route.
The byte-class twin of fill_cp_class_spans, and it exists for the same measurement: this route emits a match every few bytes on word text ([a-z]+ over prose is 42 858 matches in a large subject) and the scan is a table lookup per byte. What is left is the per-match return, and it is the same return.
| Cascade | Whether the memchr stop-tail applies, chosen once per walk by the caller. |
| [in] | text | The subject. |
| [in] | start | Where to begin. |
| [out] | out | Buffer for the spans found. |
| [in] | cap | Capacity of out. |
./negated-class route was refused here once, then landed. The first attempt gained heavily on one toolchain and almost nothing on the other, where it took back most of what this filler had won (words 1.708 -> 3.155, digits 1.089 -> 1.933) — a translation-unit inline-budget effect, not a property of the scan (docs/design.dox §10.1). fill_codepoint_class_spans is the version that did land, and it disclosed its own residual cost on unrelated rows rather than hiding it. The lesson that survives is the measurement discipline, not the conclusion "two fillers is what fits": each added branch in refill_batch must be re-measured on BOTH ISAs against rows that never touch it.
|
inlineconstexpr |
Batched twin of run_codepoint_class — fills up to cap maximal spans in ONE call.
The ./negated-class shape was the only class scan without a batch filler, so it paid a full route entry PER MATCH where the byte- and code-point-class routes pay one per sixteen. Measured on their own fast paths: the code-point rows cost several times the byte-class one per match – and fields [^,]+ and . are the two weakest rows in docs/BENCHMARKS.md against PCRE2-JIT.
A NEW function rather than a flag threaded through the existing one: an earlier attempt to widen a shared scan lambda with one extra branch nearly doubled the property-class rows on the paths that did not even use it. Nothing here is on any other route's codegen.
Search semantics only, which is what the batched walk uses – basic_match_iterator excludes anchored shapes from batching, and run_mode::full keeps run_codepoint_class.
| Cascade | Select the memchr-cascade run scan, chosen once per walk. |
| [in] | text | The subject. |
| [in] | start | Byte offset to begin at. |
| [out] | out | Receives the spans. |
| [in] | cap | Capacity of out. |
|
inlineprivate |
Fills one code-point-class ASCII row of the per-regex cache, once.
| [in,out] | cache | The per-regex immutables. |
| [in] | cp_index | Index into the program's code-point classes. |
|
inlineconstexpr |
Fills up to cap cp_class_loop matches from start without leaving the route.
The route's per-match cost is not its scan. Holding the class and the bytes fixed and varying only how often a match must be emitted puts the inner scan several times below the same bytes emitted one code point at a time: MOST of such a row is the per-match return through run()'s dispatch, fill_span_slots and the iterator's re-entry, paid once every few bytes for a single-code-point pattern. Filling a buffer amortises all of it over cap matches and hoists asc once for the batch instead of once per match.
Narrow by construction, and the guard is the caller's (basic_match_iterator): search semantics, no \b/\B wrap, no {k,} minimum. Those shapes have bookkeeping this loop does not reproduce, and batching them would answer a different question than the one asked.
| [in] | text | The subject. |
| [in] | start | Where to begin. |
| [out] | out | Buffer for the spans found. |
| [in] | cap | Capacity of out; the walk stops there and resumes from the last end. |
|
inlineprivate |
Fills one U+0080..U+07FF membership bitmap of the per-regex cache, once.
| [in,out] | cache | The per-regex immutables. |
| [in] | cp_index | Index into the program's code-point classes. |
|
inline |
Fills up to cap exact-literal matches from start without re-entering the route gate.
REOPENS A DOCUMENTED REFUSAL, and the reason is recorded in run_literal_one_search — this filler was written, measured and refused once. It was never wrong – exhaustive-compat was byte-identical over 3 218 434 cases and a both-ways differential agreed on every span – and it read literal heavily at every paired draw. It was refused for what it charged elsewhere: five rows above their own floors at every draw, with nearly every row in the panel leaning positive. The mechanism was pinned by machine code rather than argued – no scan loop changed; refill_batch grew 379 -> 389 instructions and count_matches 610 -> 606, and count_matches is what every row measures – and the note closes by saying a reopening needs a filler that does not enlarge refill_batch.
What reopens it is not a cheaper flag but a CONTRARY MEASUREMENT: a fifth route was since added to refill_batch, enlarging it, and the judgement showed no cross-row toll at all (12 of 19 medians positive, p = 0.36). What charged the rows in that work was the shape of advance's HOT path – one extra comparison there cost most of the panel's rows at a significant p, and moving it into the branch reached once per walk removed it entirely. So "enlarging refill_batch charges every row" is not a law, and the original refusal deserves one re-test under the current shape.
NO PARTIAL STATE, unlike the lazy-DFA filler: find_prefix scans to the end of the subject, so an empty return means no occurrence remains anywhere ahead. Exhaustion is proven, and the caller's "empty buffer ends the walk" reading is correct here.
| [in] | text | The subject. |
| [in] | start | Where to begin. |
| [out] | out | Buffer for the spans found. |
| [in] | cap | Capacity of out; the walk stops there and resumes from the last end. |
|
inlineconstexpr |
Fills the capturing-group slots of a fixed-shape match. Every consuming op is one byte wide, so each save sits at a constant offset from the match start; a single linear pass writes slot = match_start + offset. No-op when the pattern has no inner groups (slot_count 2). Not a re-match: the bytes were already verified.
Starts at pattern_hints::body_pc, not a hardcoded 1: an optional leading \b/\B (hints.wb_lead) sits at pc 1, and starting the walk there instead of at the body's own first byte/klass/save hits the assert_position immediately, which matches neither the byte/klass nor the save arm below and so breaks on the FIRST instruction — silently filling zero capture slots. Found live: \B(\w){2} (plain greedy, no possessive quantifier involved) loses group(1) entirely, (\w){2} without the \B does not — confirmed by bisection, not assumed from reading the loop.
| [in] | match_start | Byte offset where the match begins. |
| [out] | out_slots | Receives the group slots. |
|
inline |
Fills up to cap inner-literal matches from start without re-entering the route gate.
The route bills one engine entry per match (1.001 on a prose corpus) where every batched route bills one per batch_cap, and the cost is that return rather than the scan: the per-match figure is flat across densities, which is what a per-match CONSTANT looks like, and at the dense end that constant is essentially the whole row.
IT CALLS run_inner_literal RATHER THAN COPYING IT, which is the opposite of what fill_alternation_spans chose, and for a reason that differs in kind: that filler's twin is a mask scan whose hot body relocating would risk the working route, while this route's per-call work is a linearity backstop, a density guard, a warm/cold size floor and a reverse confirm – four pieces of state whose duplication is exactly how a batched walk and a per-match walk come to disagree. The route is already written to be re-entered per match in a walk (its own comment calls start "the
finditer resume"), so calling it in a loop asks nothing new of it. The per-haystack reset is shared through il_reset_on_new_haystack for the same reason.
partial follows the lazy-DFA filler's contract, and this route needs it more: it ABANDONS – on the density guard, on the linearity backstop, on the size floor, or when there is no way to place a candidate's start – and every one of those leaves matches ahead that another route will find. Only a memmem that ran out of candidates proves exhaustion, and that is the one branch which clears it.
| [in] | text | The subject. |
| [in] | start | Where to begin. |
| [out] | out | Buffer for the spans found. |
| [in] | cap | Capacity of out; the walk stops there and resumes from the last end. |
| [out] | partial | True unless the subject was proven spent; see above. |
| [out] | disarm | Set when the route has ABANDONED this haystack, meaning every further attempt on it is wasted work. The caller must then stop calling this filler for the rest of the walk. Without it the walk pays one failed refill per match on top of the real work: measured 3634 attempts against 7 on the veto matrix's dense date cell, which took date dense from 2.617 to 2.883 – the route slower than the core it replaces, which is exactly what that cell vetoes. The sticky abandon was doing its job; the walk was not listening. |
|
inline |
Fills up to cap lazy-DFA matches from start without re-entering the route gate.
The fifth batched route, and the one the other four made conspicuous. A pattern whose branches are not all literals – [a-z]+|[0-9]+, the plain tokenizer idiom – matches none of the four shape recognizers and lands here, where it was billing ONE engine entry per match against a quarter of one for every batched route – and running an order of magnitude slower than a plain class loop for the same match count. The excess fits a per-match constant at two independent densities, which is the tell: the DFA scan is not the cost, the return is.
ONLY THE ANCHORED-FROM-CANDIDATE SUB-SCAN, deliberately. try_shared_lazy_dfa_search has a second sub-scan (forward_end then reverse_start) for when the first bytes do not carry the search, and reproducing it here would put a second body in this translation unit – the change shape that repeatedly charged unrelated rows during the batching work (docs/MEASUREMENT.md §5.4). Declining it costs nothing, because of partial.
WHY partial EXISTS, and why the other four fillers need no such thing. Returning zero spans is how a filler says "the subject is spent", and basic_match_iterator::advance ends the walk on it. For the four shape routes that is sound: their scan covers the whole subject, so nothing found means nothing there. This route can stop with matches still to come – the fallback sub-scan's territory, fewer than lazy_dfa_min_input bytes left, no shared DFAs built yet – and ending the walk there would drop them. So partial is set unless exhaustion was PROVEN (no candidate remains in the whole subject), and the caller resumes on the per-match path, which re-enters the full gate. Pessimistic by construction: only one branch clears it.
| [in] | text | The subject. |
| [in] | start | Where to begin. |
| [out] | out | Buffer for the spans found. |
| [in] | cap | Capacity of out; the walk stops there and resumes from the last end. |
| [out] | partial | True unless the subject was proven spent; see above. |
|
inlineconstexpr |
Fills up to cap bare single byte-class matches from start without leaving the route.
The unquantified sibling of fill_class_spans, and the reason it exists is the same one, in its sharpest form: [a-z] has no + to amortise anything over, so every single accepted byte is a full route entry – one per match – which makes it slower per byte than ., a pattern that matches at EVERY position, and several times slower than its own + form.
There is no run to coalesce and so no Cascade variant: one accepted byte is one match, spans are exactly one byte wide, and consecutive matches are consecutive positions. The accept test is class_table on pattern_hints::single_class — the SAME table the general route consults, not a second copy of the membership rule.
Narrow by construction, and the guard is the caller's (real::basic_match_iterator): search semantics, no anchor, no \b/\B wrap. The shape itself (a 4-opcode program) rules out capture groups and a {k,} minimum, so unlike its siblings this filler has no bookkeeping it could fail to reproduce.
| [in] | text | The subject. |
| [in] | start | Where to begin. |
| [out] | out | Buffer for the spans found. |
| [in] | cap | Capacity of out; the walk stops there and resumes from the last end. |
|
inlineconstexprprivate |
Writes a class-loop fast-path result into out_slots: the whole-match span in slots 0/1, and — for a pattern wrapped in one capturing group ((\w+), ([a-z]+)) — the same span mirrored into the group's slots (its span equals the whole match by construction, so no re-match is needed).
ensure_slot_size only (no npos fill). For no-capture and single greedy-group shapes this writer covers every slot the program has; a prior assign(slot_count, npos) was dead work on every find_iter match after the first (slots already sized, values overwritten).
| [out] | out_slots | Capture slots to write. |
| [in] | match_start | Whole-match start offset. |
| [in] | match_end | Whole-match end offset. |
|
inlineconstexpr |
Fills capture slots for a class+ <literal> class+ match, by anchor rather than by offset.
The two-run shape has no fixed widths, so fill_fixed_saves's running offset does not apply — but every save in it still lands on one of four positions, and which one is decided by where the save sits relative to the two loops and the literal. Walking the program once per MATCH is the same trick fill_fixed_saves uses, and the program is a dozen instructions.
| [in] | s | Match start (the prefix run's beginning). |
| [in] | h | The literal's own start. |
| [in] | lit_end | One past the literal. |
| [in] | e | Match end (the suffix run's end). |
| [out] | out_slots | Slots to fill. |
|
inlineconstexpr |
Re-enables the inner-literal route and clears its density counters on a new haystack.
ONE MECHANISM, not two: the route's guards are sticky per haystack (il_abandoned, and the density pair behind it), and both run()'s gate and fill_inner_literal_spans have to observe the same reset at the same moment. Written out in each place, a guard re-enabled in one and not the other is a silent behaviour difference between a batched walk and a per-match walk – the exact shape of defect the batching work has produced twice already.
| [in] | text | The subject being scanned. |
|
inlinestaticconstexprnoexcept |
Is the inner-literal route the one run() would take for this program?
Mirrors that route's own gate, and only the routes with their own run_* body above it in the cascade – the two class loops, the three possessive loops, the exact literal. A scan STRATEGY is not a route: that distinction is what the lazy-DFA predicate got wrong at first (see there), and nothing of the kind applies here anyway.
prefix_code is required non-empty unconditionally, which is conservative rather than exact: the gate requires it only where the state confirms by reverse, which is the dynamic storage. A static regex with an inner literal and no prefix program therefore keeps the per-match walk. Batching it is separate work with its own measurement, not a widening of this line.
| [in] | prog | The compiled program view. |
|
inlinestaticconstexprnoexcept |
Is the lazy-DFA route the one run() would actually take for this program?
MIRRORS run()'s CASCADE, and it has to: a batched walk bypasses run() entirely, so batching a shape that some EARLIER route claims does not merely fail to help, it takes the pattern off a faster route. Written first as "whatever the four shape recognizers did not claim", which cost an exact-literal row heavily, well above its own floor at every paired draw: a plain literal has no class loop and no fixed alternation, so it fell through to here and left its memmem behind. The conditions below are therefore stated positively, one per route that sits above the lazy DFA in the cascade, and NOT as a residue.
run() above the lazy DFA means adding its hint here. Nothing enforces that automatically; the failure mode is a silent slowdown on exactly the shape the new route was written for, and the only instrument that sees it is a per-row layout judgement on a row that exercises that shape.| [in] | hints | The program's shape hints. |
|
inlineconstexpr |
Tests whether the fixed literal prefix occurs at cand.
| [in] | text | The subject text. |
| [in] | cand | Candidate start offset. |
| [in] | len | Length of the literal (hints.exact_literal_len). |
true if text[cand : cand+len] equals the literal.
|
inlineconstexpr |
Lookahead: does the sub-pattern match a prefix starting at pos?
Forward Pike simulation from pos, bounded to l_max bytes, stopping at the first match (the sub is capture-free, so any reached match is a witness).
| [in] | sub | The lookaround sub-program. |
| [in] | pos | Position the lookaround is evaluated at. |
|
inlineconstexpr |
Evaluates a bounded lookaround at pos (true if the thread should proceed).
Dispatches on direction and applies the negation. Both directions run a self-contained Pike simulation of the sub-program region on a DEDICATED, isolated sub-scratch (state_.lookaround) — the main state_ (lists/working/stack) is never touched, so an in-flight match is unaffected (the isolation invariant) — and are bounded to l_max bytes (the source of strict linearity per position). The sub is capture-free; (?! / (?<! negate the result.
| [in] | sub_id | Index into prog_.lookarounds. |
| [in] | pos | The text position the assertion is evaluated at. |
true if the (possibly negated) assertion holds, so the thread proceeds.
|
inline |
The lookaround sub-scratch, built on first use.
Two thread lists and an epsilon stack with their own containers. A search() builds a fresh state, so constructing and destroying all of that landed on every search — for every pattern, including the overwhelming majority with no lookaround at all. Making it lazy pays on every single search, and a pattern that DOES use lookarounds is unchanged – the emplace happens once per state, not once per evaluation.
|
inlineconstexpr |
Lookbehind: does the sub-pattern match a window ENDING EXACTLY at pos?
The match must finish precisely at pos, not merely somewhere inside the window — the defining correctness trap of lookbehind. Candidate starts run from pos backward to pos - l_max (bytes, A1); in non-bytes mode a start may not fall on a UTF-8 continuation byte, which would split a codepoint (A9). The first start whose sub-pattern fullmatches [s, pos) is a witness.
| [in] | sub | The lookaround sub-program. |
| [in] | pos | Position the sub must end exactly at. |
pos.
|
inlineconstexpr |
Matches the run of byte/klass instructions starting at pc.
Shared by the fixed-shape and alternation fast paths. Consumes one text byte per instruction and stops at the first non-consuming op (a save, jump or match).
| [in] | text | The subject text. |
| [in] | pc | Index of the first instruction of the run. |
| [in] | s | Text offset to match from. |
|
inlineconstexpr |
Verifies a fixed code-point shape forward from s, filling capture slots as it goes.
The shape is a sequence of code-point atoms and literal bytes with no loop (pattern_hints::il_cp_shape_eligible), so one linear walk decides the whole match and every save lands on the position the walk has reached — no engine, and no separate capture pass.
| [in] | text | Subject. |
| [in] | s | Candidate match start. |
| [out] | out_slots | Receives the slots (untouched unless the walk succeeds). |
s.
|
inlineconstexpr |
Fixed-shape body match from pattern_hints::body_pc, then B1 \b/\B wrap.
| SkipSaves | Skip capture writes when the caller only needs the span. |
| [in] | text | Subject. |
| [in] | s | Candidate match start. |
|
inlineconstexpr |
First position >= pos that could start a match, per the hints.
The prefilter step: jumps over positions that provably cannot start a match (literal prefix search, unique first byte, line start, first-byte set). Returns pos itself when no skipping applies.
| [in] | text | The subject text. |
| [in] | pos | Current position. |
| [in] | start | The run's start offset (for one-shot anchored patterns). |
|
inlineconstexpr |
Fills capture slots for a literal match at cand.
Replays save instructions at their consumed offsets and checks any zero-width assertions in the chain at cand.
| OutSlots | Output slot container. |
| [in] | cand | Start offset of the literal match. |
| [in] | len | Length of the literal. |
| [out] | out_slots | Receives the capture slots. |
false (and clears out_slots) if an assertion fails here, so the caller tries the next occurrence; true otherwise.
|
inlineconstexprprivate |
Cold half of class_table — the storage-mode resolution, and the only path that writes the state's row cache for a byte class.
Outlined for the reason class_table has an attribute of its own — what has to stay inlined is the row-key compare and the return, and every byte of resolution beside it competes for the budget that lets the accessor enter basic_match_iterator::advance. Inlined back in, it charged the class-scan rows on one toolchain while helping the same rows on the other: the hot path was already right, and the cold path's SIZE was what decided the outcome.
| [in] | class_index | Index into the program's interned byte classes. |
|
inlineprivate |
Fills the state's sparse-hi memo for cp_index — the cold half of cp_member_high.
Outlined so the per-code-point path is a class-key compare and a bit test, with the threshold question, the fingerprint compare and cp_hi_cached's two thread_local reads behind the miss.
| [in] | cp_index | Index of the code-point class to resolve. |
|
inlineconstexprprivate |
Is the state's cached row key stale for want?
StateBoundToProgram is the whole point: when the caller guarantees this state never meets a second program, a matching key is proof on its own and the program-identity compare — a pointer chase through the view, per run(), so per MATCH on a walk — disappears entirely at compile time. Without the guarantee it is still required: a state carried across regexes would otherwise answer from the previous program's rows.
| [in] | have | The key the state last verified (table_class or cp_page_class). |
| [in] | want | The key wanted now. |
true if the row must be re-verified.
|
inlineconstexpr |
Runs the VM over text starting at start.
On success fills out_slots with byte offsets (npos for unset capture slots; slots 0/1 are the whole match).
| Cascade | Select the memchr-cascade class-run variant (chosen once by the caller from stop_set_size, never per match). Off = the plain hot path, byte for byte. |
| OutSlots | Output slot container (resized to the program's slot count). |
| [in] | text | The subject text. |
| [in] | start | Index to begin matching/searching from. |
| [in] | mode | Anchoring mode (run_mode). |
| [out] | out_slots | Receives the capture slots on success. |
| [in] | forbid_empty_until | Reject an empty match whose start is below this offset (the iterator sets it to the next codepoint boundary so a non-empty match may follow an empty one without re-yielding it — CPython 3.7+ rule). 0 means no restriction. |
| [in] | sem | Match semantics: match_semantics::first (default, leftmost-first) or the experimental match_semantics::longest (which forces the general loop, off every fast path). |
true if a match was found.align-loops does not fix it: the class-scan routes share one inlined loop body with different alignment optima, so any single value trades one route's regression for another's. Accepted as it stands.
|
inline |
Multi-literal search via the automaton ac_ready hands back, cached per regex in detail::regex_immutables.
Search mode only — the automaton's own leftmost-first scan already IS the candidate search (no separate memchr-cascade block scan). Non-constexpr by construction (needs a runtime scratch cache), so this is never instantiated for the static storage's State — guarded at the call site by if constexpr (requires(State& s) { s.ac_state; }).
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin at. |
| [out] | out_slots | Receives the matched span on success. |
true if some branch matched.noinline, deliberately NOT cold — same reasoning as ac_ready (called on every AC-eligible search, so it must stay fully optimized); only kept OUT of run()'s own body, which is what an isolation A/B on that ISA traced the negated-class regression finding to (neither the pattern_hints field nor the pike_state size growth alone regressed it — only the full dispatch/search code sharing run()'s translation unit did).
|
inlineconstexpr |
Fast path for an alternation of straight-line branches.
Each branch is a fixed-width byte/klass sequence, so at a candidate the branches are tried in source order (leftmost-first priority) and the first that matches wins — exactly the Pike VM's thread priority. The branch structure is read directly from the split chain in the program.
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin at. |
| [in] | mode | Anchoring mode. |
| [out] | out_slots | Receives the matched span on success. |
true if some branch matched.So the opportunity here is a BATCH FILLER, exactly as for the class routes, and the recoverable amount is the one the class routes actually recovered when batched – most of the per-match constant. Not attempted yet, and two things make it the heaviest item on that list rather than the obvious next one – the search body below is a SIMD block scan with a carried mask plus a scalar tail plus a non-SIMD fallback, so a filler reproduces all three; and a new filler body is the change shape that charged unrelated rows every time it was tried during the batching work (docs/MEASUREMENT.md §5.4, §5.5). Judge it on BOTH instruments if it is built.
|
inlineconstexprprivate |
The memchr-cascade run tail: the next stop byte at or after from, or the text end. Kept in its own function so the memchr-cascade never inlines into run_class_loop's hot per-byte loop (that bloat measurably slowed stop-dense short runs). Reached only once a run has already passed cascade_run_threshold accepted bytes, so the out-of-line call is free.
| [in] | text | Subject. |
| [in] | from | Offset to search from. |
text.size() when none remains.
|
inlineconstexprprivate |
Fast path for a whole-pattern "class+".
Matches a maximal run of class bytes with one scan loop — exactly the VM's greedy result, with no thread lists.
This function is the no-lookaround path only. Trailing-lookaround class+ is dispatched outside run (see real.hpp / find_iter) into run_class_loop_trailing_la. always_inline: must stay in the find_iter body on x86, where an out-of-line call costs a double-digit share of a match-dense walk).
| Cascade | Take the memchr-cascade run tail (chosen once per walk from stop_set_size). |
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin at. |
| [in] | mode | Anchoring mode. |
| [out] | out_slots | Receives the (start, end) span on success. |
true if a non-empty run was found.
|
inlineconstexprprivate |
Cold half of the class-loop route: everything a \A/^ or \Z/$ implies.
Outlined so the unanchored path pays exactly one branch. \A/^ is a MODE (a search becomes prefix anchoring, and a region beginning past 0 cannot hold the match at all); \Z/$ is a LIMIT, handled by run_class_loop_end_anchored. Both were peeled out of the program by the shape recognizers, so this is the only thing left enforcing them.
| Cascade | Whether the memchr stop-tail applies. |
| OutSlots | Output slot container. |
| [in] | text | The subject. |
| [in] | start | Region start. |
| [in] | mode | Anchoring mode as the caller asked for it. |
| [out] | out_slots | Receives the span on success. |
true on a match.
|
inlineconstexprprivate |
X+$ / ^X+$ in search mode: the run that ENDS at the anchor, found by walking back.
A trailing \Z/$ pins the end, so the leftmost match is the maximal class run that finishes exactly there – one backward walk from the limit, not a forward scan that finds runs and discards each one whose end is wrong – milliseconds on the general VM for a subject a scan crosses once.
The limit is where $ differs from \Z and from fullmatch, and getting it wrong is silent: $ (kind 2) also matches just before ONE final newline, which is why ^a+$ matches "aaa\n" while fullmatch(a+) does not. \Z (kind 1) is the strict end.
| OutSlots | Output slot container. |
| [in] | text | The subject. |
| [in] | start | Region start; the match may not begin before it. |
| [in] | mode | Anchoring mode: search, prefix or full. |
| [out] | out_slots | Receives the span on success. |
true when a run ends at the anchor.
|
inline |
Trailing-lookaround class+: body scan + longest end where lookaround holds.
Cold, noinline: must not share a function body or inlining unit with run_class_loop (the daily [a-z]+ path). Invoked from real.hpp / find_iter outside run so a pure class-loop run() carries none of its code. Dynamic-only.
| [in] | text | Subject. |
| [in] | start | Byte offset to begin at. |
| [in] | mode | Anchoring: full, prefix or search. |
| [out] | out_slots | Capture slots, filled on a match. |
|
inlineconstexpr |
Fast path for . / a negated class, optionally a greedy +.
Scans codepoints directly, mirroring the byte-level expansion the VM would run: an ASCII byte matches the ASCII set; a valid 2–4 byte UTF-8 sequence always matches (a negated ASCII class excludes only ASCII); anything else (lone continuation, bad lead, truncation) stops, exactly as the VM's lead/continuation branches would fail. Covers .+, [^,]+, ., [^,].
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin at. |
| [in] | mode | Anchoring mode. |
| [out] | out_slots | Receives the matched span on success. |
true if at least one codepoint matched.
|
inlineconstexpr |
Fast path for a whole-pattern code-point class klass_cp, optionally a greedy +.
Scans code points directly against the class predicate (ASCII bitmap below 0x80, range binary search above), advancing by the code point's byte width, with no thread lists — the analog of run_class_loop for a Unicode shorthand (\w+, \d+, \s+). A malformed sequence stops the run, exactly as the VM's klass_cp fails on it.
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin at. |
| [in] | mode | Anchoring mode. |
| [out] | out_slots | Receives the matched span on success. |
true if a non-empty run was found. Whether a class member starts at i — membership only, no width.
The leftmost scan below needs one bit per byte, and asking width for it built a three-field decode result, tested valid, re-branched on cp < 0x80 and mapped a length back to the bit asc[lead] already held. A strict decode of a byte below 0x80 is exactly {cp = lead, length = 1, valid = true}, so that table entry IS the answer — the same shape run_class_loop's own in_class has, which is why its scan costs a fraction of this one.
Kept separate from width rather than folded into it: extend_run needs the length, and one lambda returning a width cannot narrow to a bool for the scan. Measured with each pattern ALONE in its translation unit, the code-point rows gain substantially and the byte-class and literal rows are byte-identical. Isolating the scan on a corpus with NO member at all, this route cost several times the byte-class route for the same work before this.
|
inlineconstexpr |
Fast path for a pure-literal pattern.
The prefilter locates the fixed bytes; this replays saves directly, with no thread lists, epsilon stack or per-position stepping. A leading or trailing zero-width assertion (\b, ^, $ …) may make a given occurrence fail, so in search mode it scans successive occurrences until the assertions hold — the case a differential-fuzz finding (\B2 on "220") exposed.
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin at. |
| [in] | mode | Anchoring mode. |
| [out] | out_slots | Receives the capture slots on success. |
true if a match was found.e and [e] are the same language, and single_class is batched where this route is not, so the redirect looks free – the same argument that made the bare-possessive redirect a clear win. It is not free here, because which route wins depends on the SUBJECT, not the pattern: for a byte that occurs often the batched class wins by a wide margin, and for a byte that occurs rarely the literal wins – because memchr skips whole regions, which is worth more than batching when matches are rare. Sparse one-byte literals are at least as common as dense ones, so a blanket redirect would trade a large dense win for a real sparse loss.So the shape of the answer is a DENSITY GATE – what ac_density_favours_automaton already is for Aho-Corasick – not a recognition-time redirect. That is a design of its own, needing its own threshold measurement, and it is not attempted here.
|
inlineconstexpr |
Fast path for a whole-pattern fixed-width byte/klass sequence.
A straight-line program (no branches/assertions) has exactly one thread, so a match is a fixed-width sequence verified by a single walk: each byte/klass instruction consumes one text byte. There is no greedy/lazy ambiguity. Covers class{n} and mixed shapes like \d{4}-\d{2}-\d{2}.
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin at. |
| [in] | mode | Anchoring mode. |
| [out] | out_slots | Receives the matched span on success. |
true if the sequence matched.
|
inlineconstexpr |
The general Pike VM search loop (the match semantics), factored so the lazy-DFA routing can run it on the [s, e] window a two-pass DFA has located, and so the direct path can call it too.
| [in] | text | Subject. |
| [in] | start | Byte offset to begin at. |
| [in] | mode | Anchoring: full, prefix or search. |
| [out] | out_slots | Capture slots, filled on a match. |
| [out] | forward_stop | When non-null, receives how far the forward scan reached — the inner-literal route's linearity backstop. |
|
inline |
The inner-literal search: memmem a required literal, reverse-match the prefix to the match start, forward-confirm — the reverse-inner protocol (regex-automata's ReverseInner).
Search mode only, runtime only (the reverse DFA is not constexpr). Two guards keep it linear: the reverse is bounded below by min_match_start (the previous literal's end), and a literal starting before min_pre_start (the last confirm's forward reach) abandons the scan.
| [in] | text | Subject. |
| [in] | start | Byte offset to begin the scan at. |
| [out] | out_slots | Capture slots, filled on a match. |
| [out] | abandon | Set when a linearity guard trips, so the caller retries the whole search on the core VM. |
| [in] | density_gate | Whether to consult the candidate-density gate. False only for the batched filler: that counter is read before reverse/confirm, so it cannot tell a candidate that fails from one that completes, and the filler's stream is the latter. |
abandon set when the route gave up.
|
inline |
The whole exact-literal search in one find_prefix, for a pattern_hints::literal_one_search program (see run_exact_literal's own call site for why each per-match step of the general loop is redundant there).
noinline deliberately, and it is the hot path — not the usual cold-code reason. Keeping this body inside run_exact_literal grew that function, which shares an inlining unit with run and therefore with the class loops: [^,]+ (run_codepoint_class) measured a reproducible regression from the growth alone, the same front-end codegen-luck hazard documented on run and fixed the same way (run_class_loop_trailing_la, try_shared_lazy_dfa_search). Out of line, [^,]+ returns to its exact pre-change ns/B while this path keeps its win — the one measured cost is a 9-byte literal giving back ~3 points of a gain nearly intact – out of line it keeps almost all of what inlining bought, and one literal row is identical either way. Restoring a common route beats the last points of an uncommon one.
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin searching at. |
| [in] | len | The literal's length (hints.exact_literal_len, >= 2 by the hint). |
| [out] | out_slots | Receives [cand, cand + len] on success. |
true if the literal occurs at or after start.dog: 2001 entries against 2000 matches) where every batched route bills one per batch_cap, and this subset is the ideal candidate: the literal_one_search hint already excludes captures, assertions, anchors and one-byte literals, so a filler is find_prefix plus two stores, with no confirm and no retry. Correctness was never the problem — exhaustive-compat returned byte-identical counts (3 218 434 cases, 4 548 documented divergences, 0 serious) and a both-ways differential over the batch seam agreed on every span.The trade is what settles it, and it is lopsided in BOTH directions: one row gains heavily while most of the others lose a little, each above its own floor. The gain lands on a row already ahead of the backtracking references; the costs land on rows near parity with them, several of which are recent wins.
The mechanism was then pinned by comparing machine code rather than argued, and it is not the diffuse "per-unit inline budget" this note first blamed. Of 398 function bodies in the consumer unit, five changed and NONE of them is a scan loop: every filler, and advance, are byte-identical. What moved is refill_batch (379 → 389 instructions), the iterator's constructor, and count_matches (610 → 606) — and count_matches is what benchmarks/bench_minimal.cpp measures for every row. So the rows that "regressed" do not do more work; the shared entry point they all pass through was recompiled.
Two follow-ups were tried against that mechanism and both failed, which is why the refusal stood at the time rather than waiting on one more idea. Folding the flag away cannot help: the added bool lands in existing padding, sizeof the iterator is unchanged at 8664 either way. Replacing the dispatch chain with a switch on a dense enum does not help either — clang emits a branch tree rather than a jump table, and the variant reproduced the SAME 379 → 389 and 610 → 606 for no gain at all. Outlining the constructor's cold eligibility half (real::basic_match_iterator::decide_batching) kept count_matches byte-identical on its own but NOT with this filler on top, so the note closed by asking for a filler that does not enlarge refill_batch.
WHAT OVERTURNED IT. Not a cheaper flag: the diagnosis was right and the condition it named came true on its own. count_matches has since been cut from 610 instructions to 377 — its two cold halves were outlined (decide_batching, and the trailing-lookaround walk's counter) for unrelated reasons — and at that size the filler no longer moves it at all. Re-measured on the machine-code instrument first, as this note's own method requires: of 407 function bodies in the consumer unit, THREE change size — refill_batch 391 → 401, the cold decide_batching 160 → 187, and count_matches 377 → 377. Enlarging refill_batch was never the mechanism; recompiling the entry point every row measures was.
The layout judgement then agreed, 25 rows against recalibrated floors, 24 paired draws: the exact-literal row heavily at every paired draw, the ONLY row judged REAL, and the five rows the first attempt charged are now indistinguishable from zero — every one indistinguishable. No cross-row toll either: 13 of 21 medians positive, p = 0.38, against 14 of 15 leaning positive the first time. A fifth batched route had also been added to refill_batch shortly before, enlarging it, and charged nothing measurable — which is what made re-testing this defensible rather than hopeful.
|
inline |
Search route for a HETEROGENEOUS fixed shape: vector-prefilter two positions, verify each survivor with the ordinary fixed-body walk, hand the sub-block tail to fast_search.
**Its own route, dispatched from run — deliberately NOT a branch inside run_fixed_shape.** Hosting this block there was measured on callgrind to cost measurably more INSTRUCTIONS** on heterogeneous shapes that never enter it ([0-9]{2}:[0-9]{2}, which the rare_byte veto declines): not cycles, not layout luck — the block changed that function's optimization decisions and its scalar path paid. Two variants were tried inside it, inline and noinline; the noinline one halved the cost but also cut the win, so neither was clean. Out here, run_fixed_shape's body is byte-identical to before and only patterns that actually take this route see new code — the same isolation run_class_loop_trailing_la buys for the class loop.
noinline for the mirror reason: run's own body must not grow (the guard there is one compare). Search mode only — anchored modes have a single candidate and go straight to the walk.
| OutSlots | Output slot container. |
| [in] | text | The subject text. |
| [in] | start | Index to begin searching at. |
| [out] | out_slots | Receives the matched span on success, npos on failure (seam parity with run_fixed_shape's own fail()). |
true if the sequence matched.
|
inlineconstexpr |
R2 (phase Raffinement): possessive literal-byte +/++ loop (byte_loop_possessive, e.g. a++) – the asymmetry class_ref's typing made natural to close: this opcode was already emitted and executed by the general VM, but had no dedicated recognizer or runner, so a++ fell back to the general VM despite the class/cp-class family already having one. See run_possessive_loop_generic for the shared algorithm.
| [in] | text | Subject. |
| [in] | start | Byte offset to begin at. |
| [in] | mode | Anchoring: full, prefix or search. |
| [out] | out_slots | Capture slots, filled on a match. |
|
inlineconstexpr |
Possessive class+/++ loop over a BYTE class (klass_loop_possessive). See run_possessive_loop_generic for the shared algorithm.
| [in] | text | Subject. |
| [in] | start | Byte offset to begin at. |
| [in] | mode | Anchoring: full, prefix or search. |
| [out] | out_slots | Capture slots, filled on a match. |
|
inlineconstexpr |
Possessive class+/++ loop over a CODE-POINT class (klass_cp_loop_possessive). Mirrors run_cp_class_loop's decode/membership primitives, except that the scan predicate is now split by compiler (see in_class below): clang/MSVC read the ASCII table directly, gcc keeps the width round trip. Both directions are measured, and gcc's is the counter-intuitive one. See run_possessive_loop_generic for the shared algorithm.
| [in] | text | Subject. |
| [in] | start | Byte offset to begin at. |
| [in] | mode | Anchoring: full, prefix or search. |
| [out] | out_slots | Capture slots, filled on a match. |
|
inlineconstexpr |
Shared driver: a possessive class+/++ loop, bare/suffixed (pattern_hints::possessive_prefix_size == 0) or delimited/"quoted" (non-zero) – the BODY's own class/cp-class membership test is supplied by in_class / scan_end so this one driver serves both the byte-class and the code-point-class runners below.
A possessive run never gives back: once matched, it always advances maximally, so – unlike run_class_loop's whole-pattern shape, which has nothing AFTER the loop to fail against – this scan can hit a required literal SUFFIX (or, for the delimited shape, fail to find the closing SUFFIX after a required PREFIX) that does not follow. There is nothing to retry within one attempt (that is exactly what "possessive" means); in search mode the NEXT candidate is tried, and the retry skips straight to the failed attempt's own body end – provably safe and linear, not merely fast, PROVIDED the eligibility pattern_hints documents held at recognition time (prefilter.hpp): every candidate strictly between the attempt's start and its body end is guaranteed to fail identically (an unbounded possessive run has no shorter/longer variant to offer), so skipping them loses no leftmost match.
| InClass | bool(std::size_t) -> true if the body's class/cp-class accepts the byte/code point starting at that offset. |
| ScanEnd | std::size_t(std::size_t from) -> end of the maximal body run starting at from (== from itself when from is not a valid start – a zero-length run). |
| LastWidth | std::size_t(std::size_t end) -> width (in bytes) of the LAST atom consumed by a non-empty run ending at end – fixed at 1 for a byte or byte-class body, a backward UTF-8 decode for a code-point-class body (see codepoint_retreat). Only ever called with end strictly greater than the run's own start, so there is always at least one atom to measure. |
| [in] | text | Subject. |
| [in] | start | Byte offset to begin at. |
| [in] | mode | Anchoring: full, prefix or search. |
| [out] | out_slots | Capture slots, filled on a match. |
| [in] | in_class | Membership test, per InClass. |
| [in] | scan_end | Maximal-run scanner, per ScanEnd. |
| [in] | last_width | Last-atom width, per LastWidth. |
|
inlineconstexpr |
Cheap pre-check before seeding a new thread at pos.
Live threads may force the loop through positions the prefilter would have skipped; this avoids seeding where a match cannot start. It also enforces codepoint alignment: in non-byte mode a UTF-8 continuation byte is never a valid match start.
| [in] | text | The subject text. |
| [in] | pos | The candidate seed position. |
| [in] | start | The run's start offset. |
true if a fresh thread should be seeded at pos.
|
inlineconstexpr |
L1 peephole — does the single consuming op body match the code point / byte AT pos (ahead)? Mirrors the per-op logic of lookahead_matches for a one-instruction sub-program.
| [in] | body | The sub-program's single consuming instruction. |
| [in] | pos | Position the lookaround is evaluated at. |
body accepts what starts at pos; false at the text end.
|
inlineconstexpr |
L1 peephole — does body match the code point / byte ending EXACTLY at pos (behind)? The defining lookbehind trap: the match must END at pos, so the code point is the one whose aligned start s gives s + length == pos (byte mode: pos - 1).
| [in] | body | The sub-program's single consuming instruction. |
| [in] | pos | Position the lookaround is evaluated at. |
body accepts the atom ending at pos; false at the text start.
|
inlineconstexpr |
Advances every thread of clist by the byte at pos.
Survivors that consumed a byte land in nlist. A thread reaching match records its slots and cuts all lower-priority threads, so priority (leftmost-greedy) order is preserved.
| OutSlots | Output slot container. |
| [in,out] | clist | The current thread list (consumed). |
| [in,out] | nlist | The next thread list (receives survivors). |
| [in] | pos | The current input position. |
| [in] | mode | Anchoring mode (affects match acceptance). |
| [in,out] | matched | Set to true when a match is recorded. |
| [out] | out_slots | Receives the slots of an accepted match. |
|
inlineconstexpr |
Epsilon-closure for the lookaround sub-VM, on the isolated sub-scratch.
Parks consuming (byte/klass) program counters in list and sets matched on reaching the sub's match. A capture-free sub emits no save (handled defensively as epsilon) and no assert_lookaround (nesting is rejected at compile time). Touches only state_.lookaround->stack, never the main state_. Linearity: mark_seen dedups epsilon threads within a generation; once p advances, the same (pc,p) cannot recur, so each assert_lookaround is evaluated at most once per position → O(n·k·L). No memo table is needed (it would be redundant and break constexpr).
| [in,out] | list | The sub thread list to populate. |
| [in] | pc0 | The sub-program counter to seed from. |
| [in] | pos | The current input position (for assertions). |
| [in,out] | matched | Set to true if the sub's match is reachable here. |
|
inlineconstexpr |
Reports whether the sub-program, run from start, reaches match EXACTLY at pos (a fullmatch of [start, pos)), on the isolated sub-scratch.
A match reached before pos (a shorter window) is deliberately discarded — lookbehind requires the sub to end at pos. Touches only state_.lookaround.
| [in] | code_offset | Entry program counter of the sub-program. |
| [in] | start | Candidate start offset. |
| [in] | pos | Offset the sub must end exactly at. |
[start, pos) exactly.
|
inlineconstexpr |
Pointer to thread i's slot_count capture values — its COW block's slots (COW). Used by the match case to read out the winner.
| [in] | clist | List holding the thread. |
| [in] | i | Thread index within clist. |
|
inlineconstexpr |
Tier 1's on-match capture write: if capture_start_slot is not -1, records [start, end) into thread i's capture block, in place.
Called ONLY on a confirmed atom match — never speculatively before the test, which is what makes this safe: a possessive loop always attempts one more repetition after every success, so a save fired BEFORE knowing the next attempt succeeds would overwrite THIS successful iteration's start the moment the next (possibly failing) attempt began, corrupting the capture with a torn [next-attempt's-start, this-iteration's-end) pair. See program.hpp's opcode-family note.
| [in,out] | clist | The current thread list (whose slot this thread owns is updated). |
| [in] | i | Index of the thread in clist. |
| [in] | capture_start_slot | The start slot, or -1 for an uncaptured Tier 1 loop (a no-op). |
| [in] | start | Position before the atom was consumed. |
| [in] | end | Position after the atom was consumed. |
|
inlineprivate |
Lazy-DFA search route on the shared confirm DFAs. noinline so its body cannot inflate run (x86 class-loop codegen neighbor — same shape as ac_ready).
| [in] | text | Subject. |
| [in] | start | Byte offset to begin at. |
| [in] | mode | Anchoring: full, prefix or search. |
| [out] | out_slots | Capture slots, filled on a match. |
|
inlineprivate |
Verifies (and if needed fills) the byte row for class_index, then caches it in the state.
Must stay outlined: class_table has to remain small enough to inline into basic_match_iterator::advance, and this body inline is what pushes it over. Emitted out of line there instead, it costs a tenth of the instructions of a class-loop walk.
| [in,out] | cache | The per-regex immutables. |
| [in] | class_index | Index into the program's interned byte classes. |
|
inlineconstexpr |
O(1) lead/trail \b/\B check at match bounds [s, e).
Single verification helper for every wb-wrapping fast path (class-loop, cp-class, fixed-shape, literal, alternation). Hints 0/1/2 from pattern_hints::wb_lead / pattern_hints::wb_trail.
| [in] | s | Match start (lead assert position). |
| [in] | e | Match end (trail assert position). |
|
inlineprivate |
Run fn with the shared search DFAs under the slot lock.
| [in] | fn | Callable taking (lazy_dfa& fwd, reverse_dfa& rev). |
fn ran; false when the route must stay on the Pike VM (no immut / ineligible).
|
inlineconstexpr |
Word-ness of the code point starting at pos — the right side of a boundary. False at the text end or on a malformed sequence; bytes / re.A stay byte-level.
| [in] | pos | Boundary position. |
| [in] | ascii_word | Restrict word-ness to ASCII (re.A / bytes mode). |
true when the following code point is a word character.
|
inlineconstexpr |
Word-ness of the code point ending exactly at pos — the left side of a \b/\B/ \</\> boundary. False at the text start. In text mode it back-decodes the code point (up to three continuation bytes to the lead) and requires the sequence to end exactly at pos, so a malformed or misaligned run reads as non-word; bytes / re.A stay byte-level. This is the shared frontier notion (the same decode that codepoint alignment uses).
| [in] | pos | Boundary position. |
| [in] | ascii_word | Restrict word-ness to ASCII (re.A / bytes mode). |
true when the preceding code point is a word character.
|
inlineconstexpr |
Writes a buffered span into a caller's slots exactly as the per-match path would.
| [out] | out_slots | Slots to fill. |
| [in] | s | Match start. |
| [in] | e | Match end. |
|
staticconstexprprivate |
Percentage of sampled candidates that may COMPLETE a branch and still leave the automaton ahead. Above it the cascade wins whatever the candidate density says.
The second quantity the gate needed, and the reason it needed one is measured rather than argued (benchmarks/ac_regime.cpp's third sweep): candidate density counts positions where a branch HEAD occurs and cannot tell a false start from a match, yet those pull in OPPOSITE directions. A false start punishes the cascade – verify, reject, resume – and leaves the automaton indifferent; a match REWARDS the cascade, which stops there, and charges the automaton a per-match return. Holding candidate density fixed and varying ONLY the completed fraction, the verdict flips from one end of that sweep to the other – which is the proof that a single number could not have been arbitrating both.
The two ISAs place the balance point differently, and the constant takes the CONSERVATIVE one: below the true crossover on either, so it can decline where the automaton would still have won but never take it where the cascade wins. That is the same safety direction ac_density_work_threshold_low argues for and for the same reason – below ac_branch_threshold the automaton was historically never taken, so switching early regresses what ships while switching late only forfeits.
|
staticconstexprprivate |
AC routing: sample window, and the candidate-work product at or above which the automaton beats the memchr cascade.
The branch COUNT cannot decide this and ac_branch_threshold never could: the automaton scans at a flat rate whatever the subject, while the cascade it replaces spans two orders of magnitude on the SAME pattern and the same subject length. Only the haystack decides. What the haystack has to supply is candidate DENSITY, and benchmarks/ac_regime.cpp measures where that crosses over — including the part the reconnaissance did not predict, that the crossover MOVES with branch count, because the cascade tries branches in order while the automaton does not: more branches, and the cascade starts losing at a lower density.
So the rule is a PRODUCT, not a density: (candidates per 1000 bytes) * branch_count. That product is what stays roughly invariant across branch counts, and it is what this threshold is expressed in.
THIS QUANTITY CANNOT DECIDE ALONE, and the gate no longer asks it to. Candidate density counts positions where a branch HEAD occurs and cannot tell a false start from a completed match, and those two pull in OPPOSITE directions: a false start punishes the cascade (verify, reject, resume) and leaves the automaton indifferent, while a match rewards the cascade (it stops there) and costs the automaton a per-match return. One number was arbitrating two forces that oppose each other – the same argument the branch COUNT lost, now applying to what replaced it. A counter-example in the wild: a nine-branch alternation over ordinary prose runs about twice as slow on the automaton as on the cascade – on the side of the threshold that is supposed to be a win.
The gate therefore samples a SECOND quantity beside this one and takes the automaton only when BOTH agree – see ac_completion_pct , which carries the sweep that measures it, the derivation of its constant and the cost of asking. The two constants here were NOT retuned when that landed: retuning them against that sweep's tables would have moved the error rather than removed it.
The constant is the measured MINIMUM (588), not a mid-point, and that choice is a consequence rather than a taste. Today every alternation past ac_branch_threshold takes AC unconditionally, so switching too EARLY can never be worse than the behaviour being replaced, while switching too LATE forfeits a win that exists today. Rounding below the earliest crossover on either platform therefore cannot regress any subject, and the platforms' 1.7x disagreement about the constant stops being a tuning argument. On arm the product is not one level but two, with a step between the lower and upper branch counts – a real discontinuity, reproducible across rounds and unexplained. It does not affect the choice, since the minimum is on the other platform either way.
|
private |
Reject empty matches whose start is below this offset.
The CPython 3.7+ rule: after an empty match, the next match may not be empty at the same spot, letting a non-empty match start there. The iterator sets this to the next codepoint boundary so the skip stays UTF-8 aligned. 0 means no restriction (single match/search/fullmatch never restrict).
|
staticconstexprprivate |
Density-gate sample size and threshold (inner-literal → core/DFA when candidate density is high).
Candidate density is what decides: below the crossover the inner literal skips most of the subject, above it every candidate is a failed confirm and the core scan wins by a margin that grows with the density. The threshold sits just past the crossover. Threshold 60/1000 (dens 0.06) sits conservatively above crossover so sparse IL wins (dens ≪ 0.01) stay on IL. Capture-free only (slot_count ≤ 2): with groups, IL still beat forced DFA on dense (measured). Probe after K candidates across the haystack (sticky on pike_state::il_density_cands).
(?:\w+)_(?:\w+), whose fallback is the DFA. [0-9]{4}-[0-9]{2}-[0-9]{2} falls back to pattern_hints::fixed_shape instead, which is far cheaper – and on a date-dense corpus that route is modestly faster than the inner-literal one while the gate never fires, because - at ~32 candidates per 1000 bytes sits under the 60 calibrated for the other shape. On a sparse corpus the two are equal, so the gate is not wrong in general – its single threshold is.This is the same defect the Aho-Corasick gate had before 2026.8.0: one number where the crossover depends on what is being compared against. The AC fix keyed on a PRODUCT once the second variable was identified; the analogous variable here is the fallback route's cost, not the branch count.
Worth chasing because it sits on the engine's worst published row against the backtracking references. This does not close that gap, but it is the part of it that is understood.
|
staticconstexpr |
Below this input length the lazy-DFA routing is skipped (the two-pass setup does not amortise on a short subject — the Pike VM goes direct). A measured, documented threshold.
PUBLIC because real::basic_match_iterator reads it when deciding whether to batch this route: below this length the route is not taken, so its filler could only fail once per match. Paired with lazy_dfa_is_the_route, which is public for the same reason.
1.9.8