Struct Nfa 

pub struct Nfa {
    states: Vec<Vec<Transition>>,
    start: usize,
    accept: usize,
    reach_accept: Vec<bool>,
    min_match_rows: usize,
    max_match_rows: Option<usize>,
}

A Thompson-construction NFA with a single start and single accept state.

Fields

states: Vec<Vec<Transition>>

start: usize

accept: usize

reach_accept: Vec<bool>

Per state: whether accept is reachable from it, with every predicate assumed satisfiable. This is the static half of Nfa::may_extend: a consuming transition at the row boundary whose target cannot reach accept can never contribute a longer match, no matter what rows arrive. Computed once at compile with one reverse BFS.

min_match_rows: usize

Fewest rows any accepting path consumes, with every predicate assumed satisfiable — the shortest match the pattern admits (0 when it accepts the empty match). A start with fewer rows than this before the boundary cannot complete, so the finder skips it without a walk (see Nfa::next_match). Computed once at compile with one 0-1 BFS.

max_match_rows: Option<usize>

Most rows any path from start consumes, when the automaton is acyclic (no *, + or unbounded range) — None when it has a cycle and a path can consume without bound. From a position with MORE rows than this before the boundary, no path can reach the boundary while still inside the automaton: the position is dead without a walk (see Nfa::reaches_boundary_alive). Computed once at compile with one DFS.

Implementations

impl Nfa

pub fn compile(pattern: &Pattern) -> Self

Compile a Pattern into an NFA.

pub fn max_match_rows(&self) -> Option<usize>

See the max_match_rows field.

fn compute_max_match_rows( states: &[Vec<Transition>], start: usize, ) -> Option<usize>

See the max_match_rows field: the longest path from start counting consuming edges, over ANY path (not only accepting ones — a path that dies still consumed its rows), or None if a cycle is reachable. One iterative DFS with a tri-state mark, so a 100k-state automaton does not recurse.

pub fn min_match_rows(&self) -> usize

See the min_match_rows field.

fn compute_min_match_rows( states: &[Vec<Transition>], start: usize, accept: usize, ) -> usize

See the min_match_rows field: shortest path from start to accept where ε-edges cost nothing and consuming edges cost one row (0-1 BFS, linear in states + transitions).

fn compute_reach_accept(states: &[Vec<Transition>], accept: usize) -> Vec<bool>

See the reach_accept field. Linear in states + transitions (one reverse BFS).

impl Nfa

pub async fn find_matches_dynamic( &self, n_rows: usize, matcher: &(impl CandidateMatcher + Sync), skip: &SkipMode, ) -> StreamExecutorResult<Vec<LabeledMatch>>

Like find_matches_labeled, but membership is decided by an async CandidateMatcher instead of precomputed satisfied-sets, so DEFINE predicates with row-pattern navigation can be evaluated against the running match. n_rows is the number of (sorted) rows to scan. This is the only matcher the streaming executor uses.

pub async fn next_match( &self, scan: &mut MatchScan, n_rows: usize, matcher: &(impl CandidateMatcher + Sync), skip: &SkipMode, budget: &mut ScanBudget, memoize: bool, ) -> StreamExecutorResult<Option<LabeledMatch>>

Pull the next match at or after scan’s cursor, advancing the cursor by the skip mode. Returns None once the cursor passes n_rows.

This is the streaming form of Nfa::find_matches_dynamic, which is a thin collect over it. The executor’s emit loop pulls instead of collecting so that stopping — at the first boundary match that must be held for maximality — stops the scan, not just the emission: nothing past the held match is computed (it would be recomputed from scratch on the next watermark anyway) and at most one match is resident at a time. Collecting is worst-case quadratic in live rows: under an overlapping skip mode a greedy (a+) over n qualifying rows yields n matches whose label vectors sum to O(n^2) strings, all materialized before the first one is examined.

pub async fn reaches_boundary_alive( &self, pos: usize, n_rows: usize, matcher: &(impl CandidateMatcher + Sync), budget: &mut ScanBudget, memoize: bool, ) -> StreamExecutorResult<bool>

Whether a match starting at pos is still live at the safe boundary n_rows: there exists a path that consumes the safe rows pos..n_rows and reaches the boundary while still inside the automaton (not yet accepted), so a future row could extend it into a complete match. Used to evict rows that can no longer be part of any match.

This is strictly stronger than “can pos begin the pattern”: for (a b) over [a, x] where x matches neither, the a can begin the pattern, but every path dies on x before the boundary, so the start is dead and must be evictable. A lone [a] (boundary right after a), in contrast, is kept because a future b may still complete it.

pub fn is_linear(&self) -> bool

Whether the automaton is a fixed-length linear chain: every state has at most one outgoing transition (plain concatenations like (a b c) — no alternation, no quantifiers, no PERMUTE). For such patterns an accepted match consumed the only path there is, so no more-preferred extension can exist and Nfa::may_extend is statically false — the emission gate can skip the probe entirely.

pub async fn may_extend( &self, start: usize, end: usize, matcher: &(impl CandidateMatcher + Sync), budget: &mut ScanBudget, memoize: bool, ) -> StreamExecutorResult<bool>

Whether the finder’s preferred result for the match starting at start could change if more rows arrived past the boundary end.

The finder (Nfa::next_match) returns the first accepting path in transition order: greedy quantifiers try their consume edge before their exit edge, reluctant ones the reverse, and ordered alternation tries branches as listed. A lower-priority path can therefore NEVER override an accepting higher-priority one, no matter what rows arrive — for PATTERN (A (B | B C)) the first-listed B alternative wins even if a C shows up later. So the question is not “could any NFA path consume more” but “could a path the finder prefers over the current result become accepting”.

This walk mirrors the finder’s own traversal exactly and stops at its first accept — the preferred result. It answers true iff, strictly before that accept in preference order, some consuming transition was blocked by the row boundary while its target can still reach accept (Nfa::reach_accept, unknown rows assumed satisfiable): exactly the paths that arriving rows could turn into a more-preferred accepting result. Everything explored after the accept is lower-priority and irrelevant.

false means the preferred result is terminal: it cannot change, so a boundary match is final and must be emitted — holding it would starve an idle partition forever (the frontier recompute finds neither a future row nor, without WITHIN, a deadline, and drops the partition). true means the standard maximality wait applies.

async fn walk( &self, goal: Goal<'_>, start_pos: usize, matcher: &(impl CandidateMatcher + Sync), budget: &mut ScanBudget, memo: Option<&mut Memo>, ) -> StreamExecutorResult<Option<(usize, Vec<String>)>>

The one traversal behind the finder, the liveness check and the extension probe: a depth-first search from self.start at row start_pos, in transition order, with DEFINE predicates evaluated over the running match (path, the labels bound so far, is threaded to the matcher). Returns the row position at which goal was met together with the labels of the path that met it; None is “no such path” — or, with budget.hit latched, “undecided”.

Iterative, over an explicit heap stack. The recursive walkers this replaced — boxed async_recursion frames, polled through the real thread stack once per consumed row and once per ε-edge — needed a hard depth cap to avoid overflowing it, and the cap made any match spanning more than a couple of hundred rows permanently undecidable: unlike the budget it did not reset between visits, so every refresh died at the same depth. Every push is charged to the budget, so the stack holds at most budget frames — at the executor’s 2^20 steps, about 32 megabytes of 32-byte frames in the worst case — and the budget is the only bound on a walk.

The discipline, identical for all three goals:

• transitions are tried in the order the builder emitted them, and the FIRST verdict wins — greedy quantifiers list their consume edge before their exit edge, reluctant ones the reverse, alternation as written;
• a Visited scope per row position cuts ε-cycles: ε-edges keep the position and the scope, a consumed row opens a fresh one, so distinct label assignments may reach the same state at the next row;
• the budget is charged once per predicate evaluation and once per edge taken, and a spent budget ends the walk without a verdict and without recording anything;
• failures are memoized only at consumption boundaries — a consumed frame starts with a fresh scope, so its outcome is context-free — and never for a budget-aborted walk, which would turn a transient abort into a permanent wrong verdict (see Memo).

fn pop_failed( stack: &mut Vec<Frame>, scopes: &mut [Visited], depth: &mut usize, path: &mut Vec<String>, memo: Option<&mut Memo>, budget: &ScanBudget, )

Pop the top frame as a failure: unmark its state in its scope, and if it was entered by consuming a row, close that scope, drop its label, and memoize the failure.

A budget-aborted walk never gets here — every latch site returns from walk directly — so the failure being recorded is always a proven one, by construction rather than by a guard.

Trait Implementations

impl Clone for Nfa

fn clone(&self) -> Nfa

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Nfa

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.