A lazy priority-preserving forward DFA over a Pike program (the kFirstMatch forward pass).
More...
|
| constexpr | lazy_dfa (std::span< const instr > code, std::span< const char_class > classes, std::size_t budget=state_budget, const lazy_byte_alphabet *shared_alpha=nullptr) |
| | Builds the (initially empty) lazy DFA over a Pike program.
|
| |
| bool | eligible () const |
| | Whether the program can be represented at all (no assertion, klass_cp or lookaround).
|
| |
| std::uint16_t | num_classes () const |
| | Width of one cached transition row.
|
| |
| std::uint32_t | start_state () const |
| | The state a scan starts in.
|
| |
|
void | begin_scan () |
| | Begin a search: clear the per-scan flush counter and the thrash flag. (No cache flush — the states carry over between searches on the same text, which is where the cache pays.)
|
| |
| bool | thrashing () const |
| | Whether this scan crossed thrash_flushes flushes — the cache is not paying for it.
|
| |
| const counters & | stats () const |
| | Cache-behaviour counters.
|
| |
| std::size_t | forward_end (std::string_view text) |
| | The end offset of the leftmost-first match in text (kFirstMatch), or real::npos.
|
| |
| anchored_result | anchored_end (std::string_view text, std::size_t start) |
| | The end offset of the leftmost-first match ANCHORED at start in text, or real::npos.
|
| |
| bool | is_match (std::uint32_t state) const |
| | Whether state accepts here (its ordered set contains a match PC).
|
| |
| std::uint32_t | step (std::uint32_t state, std::uint8_t byte) |
| | Transition state on byte to the next DFA state, computing and caching it on first use.
|
| |
|
|
static constexpr std::uint32_t | dead_state {0} |
| | The empty state: every transition from it stays here.
|
| |
|
static constexpr std::uint32_t | no_transition {0xFFFFFFFFU} |
| | A not-yet-computed cached transition.
|
| |
|
static constexpr std::uint32_t | no_match_idx {0xFFFFFFFFU} |
| | A state whose ordered set holds no accept.
|
| |
|
static constexpr std::size_t | state_budget {4096} |
| | Cached states before a flush (the memory cap).
|
| |
|
static constexpr std::size_t | thrash_flushes {2} |
| | Flushes within one scan that trip thrashing.
|
| |
|
| std::uint32_t | step_seeded (std::uint32_t state, std::uint8_t byte) |
| | Like step, but re-seeds: the unanchored-search variant appends pc 0's closure at the lowest priority, so a fresh thread starts at every position until a match is found. Cached in its own transition row (the pre-match state family).
|
| |
| std::uint32_t | cut (std::uint32_t state, std::uint32_t m) |
| | The priority-cut at an accept: intern the prefix of state's ordered pc-set before index m (dropping the accept and every lower-priority thread).
|
| |
| std::uint32_t | cut_cached (std::uint32_t state) |
| | The priority-cut of state at its own accept, memoized. cut is O(state size) — it rebuilds and re-interns the prefix — and a Unicode klass_cp byte-program makes states thousands of PCs wide, so recomputing it once per match (per find_iter step) dominated. Cached per state, it is computed once and then O(1). The state's accept index is fixed, so the cut is deterministic.
|
| |
| bool | consumes (std::int32_t pc, std::uint8_t byte) const |
| | Whether the instruction at pc is a consuming edge that accepts byte.
|
| |
| constexpr void | close_into (std::int32_t pc, std::vector< std::int32_t > &out, std::vector< char > &seen) const |
| | Append the ordered epsilon-closure of pc to out (split priority; save/jump crossed), collecting the consuming and match PCs. Uses seen to dedup within this closure.
|
| |
| constexpr std::uint32_t | intern (const std::vector< std::int32_t > &pcs) |
| | Intern an ordered pc-set into a state id (cached). Flushes the cache when the budget is hit.
|
| |
| constexpr std::uint32_t | intern_fresh (const std::vector< std::int32_t > &pcs) |
| | Append a new state for pcs: its two transition rows, its accept index and its empty cut memo.
|
| |
|
constexpr void | flush () |
| | Empty the cache back to the dead + start states (the eviction: bounded memory).
|
| |
|
|
std::span< const instr > | code_ |
| | The byte program, owned by the caller.
|
| |
|
std::span< const char_class > | classes_ |
| | Its byte classes, likewise borrowed.
|
| |
|
lazy_byte_alphabet | alpha_ |
| | Byte-to-class map; its count is the row stride.
|
| |
|
bool | eligible_ {false} |
| | compute_eligibility's verdict, fixed at construction.
|
| |
|
std::uint32_t | start_state_ {0} |
| | Id of the closure of pc 0, re-interned by each flush.
|
| |
|
std::vector< std::int32_t > | stack_ |
| | close_into's work stack, hoisted: it ran once per pc of the source state.
|
| |
|
std::vector< std::vector< std::int32_t > > | state_pcs_ |
| | state id -> ordered pc-set.
|
| |
|
std::vector< std::uint32_t > | trans_ |
| | flat [state*stride + class] -> next, unseeded (post-match); stride = alpha_.count.
|
| |
|
std::vector< std::uint32_t > | trans_seeded_ |
| | flat [state*stride + class] -> next, re-seeding (pre-match).
|
| |
|
std::vector< std::uint32_t > | state_match_idx_ |
| | state id -> index of its first accept, or no_match_idx.
|
| |
|
std::vector< std::uint32_t > | state_cut_ |
| | state id -> memoized priority-cut result (no_transition = not yet computed).
|
| |
|
pc_set_cache | cache_ |
| | pc-set -> state id, the memo behind intern.
|
| |
|
std::size_t | budget_ {state_budget} |
| | Cached states tolerated before a flush.
|
| |
|
counters | stats_ {} |
| | Live counters, exposed by stats.
|
| |
|
bool | thrashing_ {false} |
| | Set once this scan crossed thrash_flushes flushes.
|
| |
A lazy priority-preserving forward DFA over a Pike program (the kFirstMatch forward pass).
A DFA state is the ordered epsilon-closure of a set of program counters (the Pike thread list's PCs, in split priority). step transitions on a byte by consuming it from each PC and re-closing, then interns the resulting ordered set into a cached state — the subset construction, memoized on demand.
The cache is bounded: once it reaches state_budget states it is flushed and rebuilt (states are cheap to recompute; a bounded cache keeps memory flat). state_budget flushes crossed within one scan (see begin_scan) trips thrashing — the signal an eventual caller uses to abandon the DFA and finish that one search on the Pike VM, per-scan and linear, never re-attempting per position.
A program with an op no forward DFA can represent — a position assertion (\b, ^, $), a klass_cp, or a lookaround — is ineligible; this only builds the machinery, it does not decide policy.
| anchored_result real::detail::lazy_dfa::anchored_end |
( |
std::string_view |
text, |
|
|
std::size_t |
start |
|
) |
| |
|
inline |
The end offset of the leftmost-first match ANCHORED at start in text, or real::npos.
Identical walk to forward_end except it never re-seeds: a single thread is seeded once, at start (step, never step_seeded), so a match must begin exactly there. The caller already knows start is a valid candidate (a prefilter hit) – this skips the reverse pass forward_end normally needs to recover the start, since there is nothing left to recover. Eligible programs only (an ineligible one returns real::npos; the caller keeps the Pike VM). No captures: this reports the end only, exactly like forward_end.
Does NOT call begin_scan (unlike forward_end): a caller trying several candidates in a loop for one logical search calls begin_scan itself, ONCE, before the loop – resetting the thrash flag per CANDIDATE rather than per search would mask real thrashing across the loop.
The lean munch (A3): once find_iter has warmed a search up, the small state set a pattern like [a-z][a-z]+ actually visits is already fully cached – every (state, class) transition and every state's priority-cut already sit in trans_ / state_cut_. step and cut_cached exist to COMPUTE and cache those on a miss; paying their call overhead plus the "is this already
built?" branch on every byte, when the answer is essentially always yes post-warm-up, is exactly the residual cost profiling pinned here (step + cut_cached + this function itself). So the loop below inlines the two lookups directly – a flat class-then-transition read per byte, an accept check against a local, no function call at all in the common case – and falls back to the real (state-building, cache-filling, flush-aware) step / cut_cached only on an actual miss, which is rare once the small state set has been visited once. Same states, same tables, same memoization step / cut_cached would have produced – this is a leaner READ of them, not a different automaton. One accounting gap: the inlined hits do not increment counters::hits (that counter is a step()/cut_cached()-callers' bookkeeping aid, not behavior – thrashing and flush only ever move on an actual miss, which still goes through the real functions).
- Parameters
-
| [in] | text | The subject text. |
| [in] | start | Offset to anchor the match at (must be <= text.size()). |
- Returns
- The match end and the position the walk stopped at (anchored_result::scanned_to). On a miss (
end == real::npos), scanned_to == text.size() means the walk consumed the whole remaining haystack without a dead state pruning it – an unbounded reach (e.g. .* with no terminator ahead), as opposed to one the pattern's own structure bounded (a dead state hit before the end). A caller trying candidate after candidate (real::detail::pike_vm's A2 route) uses this to tell "this candidate's reach is bounded,
the next one is cheap too" apart from "every candidate from here will re-scan to the end" – the O(n^2) regime.
1.9.8