- 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>
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). stop reports how far the confirm reached, for the linearity backstop. Returns true and fills out_slots on a match at s. | |
| template<typename OutSlots > | |
| bool | run_inner_literal (std::string_view text, std::size_t start, OutSlots &out_slots, bool &abandon) |
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). On a match fills out_slots and returns true; on none returns false. Sets abandon (and returns false) when a linearity guard trips, so the caller retries the whole search on the core VM. 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. | |
Private Types | |
| using | list_type = std::remove_reference_t< decltype(std::declval< State & >().lists[0])> |
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 (OPT D1) — heap-backed for dynamic, compile-sized static_vec for static. The one capture-slot mechanism, both storages. | |
Private Member Functions | |
| void | ensure_immutables () |
Build the forward/reverse DFAs into the reusable state on first eligible use, or rebuild them if the state is now bound to a different program (its code pointer changed). The cache then persists across a whole find_iter (where it pays), and forward_end resets its per-search thrash flag itself. Instantiated only for the dynamic state (the one carrying the optionals). | |
| void | ensure_lazy_dfa () |
| Ensure this iterator's lazy DFA caches are warm for the current program. Builds the shared immutables first (ensure_immutables), then — only when the state is now bound to a different program — (re)creates the per-iterator forward and reverse lazy-DFA transition caches over the shared byte-program. The caches are mutable (they fill during a scan) and per-iterator, so this runs once per iterator, not per match, off the hot path. | |
| constexpr const std::uint8_t * | class_table (std::size_t class_index) |
Returns a flat 256-byte membership table for class class_index. | |
| 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 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). | |
| 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). Sizes the slots to the program's slot count. | |
| constexpr std::size_t | run_cascade_stop (std::string_view text, std::size_t from) const |
OPT-C 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+". | |
| 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<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. | |
| 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 > | |
| 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<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 > | |
| 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 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 > | |
| 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 | 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 (OPT D1). 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 (OPT D1). 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, a binary search of the class's range slice above. The class is already the effective set, so this is a plain positive membership test. | |
| constexpr void | add_thread (list_type &list, std::int32_t pc0, std::size_t pos, std::uint32_t initial_block) |
Adds pc0 and its whole epsilon closure to list — the one closure walk (OPT D1). 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 (OPT D1), 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 | 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. | |
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::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. | |
| 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 (OPT-C). Below it a run pays nothing extra, so a stop-dense stream of short runs stays at baseline cost; the crossover is measured. | |
The Pike VM, generic over the scratch-state container policy.
| State | A basic_pike_state instantiation (vector- or static-backed). |
|
private |
|
private |
The capture-block pool type of the bound State (OPT D1) — heap-backed for dynamic, compile-sized static_vec for static. The one capture-slot mechanism, both storages.
|
inlineconstexpr |
|
inlineconstexprprivate |
Adds pc0 and its whole epsilon closure to list — the one closure walk (OPT D1). 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_block | The block the walk starts on — the caller passes an already-owned ref. |
|
inlineconstexprprivate |
|
inlineconstexprprivate |
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. |
|
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). stop reports how far the confirm reached, for the linearity backstop. Returns true and fills out_slots on a match at s.
|
inlineconstexprprivate |
|
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 |
Tests a decoded code point against a klass_cp class: ASCII bitmap below 0x80, a binary search of the class's range slice above. 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.
|
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).
|
inlineprivate |
Build the forward/reverse DFAs into the reusable state on first eligible use, or rebuild them if the state is now bound to a different program (its code pointer changed). The cache then persists across a whole find_iter (where it pays), and forward_end resets its per-search thrash flag itself. Instantiated only for the dynamic state (the one carrying the optionals).
Build the per-regex immutables once, race-free: the Tier-A byte-program the DFAs run over (and its shared alphabet), plus the one-pass extractor. The extractor is built Tier-B (assertions kept as edge conditions), so one table serves both the search window (Tier-A patterns have empty assertion masks) and direct anchored match/fullmatch (Tier-B patterns). Needs no DFA, so the anchored path can call this without paying the DFA build.
|
inlineprivate |
Ensure this iterator's lazy DFA caches are warm for the current program. Builds the shared immutables first (ensure_immutables), then — only when the state is now bound to a different program — (re)creates the per-iterator forward and reverse lazy-DFA transition caches over the shared byte-program. The caches are mutable (they fill during a scan) and per-iterator, so this runs once per iterator, not per match, off the hot path.
|
inlineconstexprprivate |
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.
|
inlineconstexprprivate |
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.
| [in] | match_start | Byte offset where the match begins. |
| [out] | out_slots | Receives the group slots. |
|
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). Sizes the slots to the program's slot count.
|
inlineconstexprprivate |
|
inlineconstexprprivate |
|
inlineconstexprprivate |
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.
|
inlineconstexprprivate |
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.
|
inlineconstexprprivate |
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. |
|
inlineconstexprprivate |
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). |
|
inlineconstexprprivate |
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.
|
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 OPT-C memchr-cascade class-run variant (chosen once by the caller from stop_set_size, never per match). Off = the pre-OPT-C 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.
|
inlineconstexprprivate |
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.
|
inlineconstexprprivate |
OPT-C 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.
|
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.
| Cascade | Take the OPT-C 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 |
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.
|
inlineconstexprprivate |
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.
|
inlineconstexprprivate |
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.
|
inlineconstexprprivate |
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 |
|
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). On a match fills out_slots and returns true; on none returns false. Sets abandon (and returns false) when a linearity guard trips, so the caller retries the whole search on the core VM. 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.
|
inlineconstexprprivate |
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.
|
inlineconstexprprivate |
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. |
|
inlineconstexprprivate |
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. |
|
inlineconstexprprivate |
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.
|
inlineconstexprprivate |
|
inlineconstexprprivate |
|
inlineconstexprprivate |
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).
|
staticconstexprprivate |
|
staticconstexprprivate |
|
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 |
|
staticconstexprprivate |
|
private |
|
private |
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.
|
private |
|
private |
1.9.8