Struct IncrementalMatcher 

pub struct IncrementalMatcher {
    nfa: Arc<Nfa>,
    skip: SkipMode,
    matched: Vec<SeqMatch>,
    frozen_count: usize,
    next_pos: usize,
    seq_index: Vec<Seq>,
    incomplete: bool,
    scan_cursor: usize,
    dead_upto: usize,
    matchless_upto: usize,
    freeze_truncated: bool,
}

Incremental wrapper around Nfa::find_matches_dynamic for append-only input.

Rows are fed in ORDER BY order via IncrementalMatcher::advance; their buffer position is implied by feed order and mapped back to a stable seq through seq_index. Everything before next_pos (the skip-resume point after the last frozen match) is immutable and never rescanned.

Fields

nfa: Arc<Nfa>

Shared compiled pattern: one matcher per partition (and a fresh one per full consumption), so holding the automaton by Arc instead of by value avoids a deep clone per instance — while still keeping this struct free of a lifetime the executor would have to thread through.

skip: SkipMode

AFTER MATCH SKIP strategy, shared with the batch path.

matched: Vec<SeqMatch>

All matches over the rows fed so far. matched[..frozen_count] are frozen (immutable under future appends); the rest is the provisional tail recomputed on every advance.

frozen_count: usize

Number of leading entries of matched that are frozen.

next_pos: usize

Buffer position where the next rescan begins: the skip-resume point after the last frozen match (0 while nothing is frozen). The suffix [next_pos, n_rows) is the only mutable region.

seq_index: Vec<Seq>

seq_index[pos] is the seq of the row fed at buffer position pos. Its length is the number of rows fed so far (the batch n_rows).

incomplete: bool

Whether the last rescan stopped on a spent budget, leaving matched’s provisional tail a (possibly empty) leftmost-PREFIX of the true match list rather than the full list. While set, absence of a match from provisional() is NOT evidence of absence: the executor must re-derive (fresh budget) before any decision that treats missing matches as decided — the WITHIN-deadline prune in particular would otherwise delete rows carrying a match the truncated scan never reached.

scan_cursor: usize

Absolute buffer position where a budget-truncated match scan will resume. Unlike matchless_upto, this may follow successful matches: the corresponding leftmost-prefix of matches remains in matched, and the next refresh appends matches found from this cursor. Reset whenever rows are appended or invalidated, because those changes can alter previously provisional matches and their skip-resume positions.

dead_upto: usize

Positions [next_pos, dead_upto) proven dead at the boundary by the freeze walks of this and earlier visits (next_pos <= matchless_upto <= dead_upto always). Deadness is monotone under appends — a walk reads only rows at or before its position (there is no forward navigation: NEXT inside DEFINE is rejected at bind and decode time), so a position no path can carry to the boundary stays that way as rows arrive — which lets a freeze that ran out of budget resume where it stopped instead of restarting at next_pos. Without this, freezing a match of L rows costs Θ(L²) steps in ONE visit (each of its L positions walks up to L rows), and once that exceeds the per-visit budget the region never freezes: the permanent, non-self-healing shape a long chain pattern (a{600}) otherwise degrades into. Reset to next_pos whenever the rows a verdict was computed over can change (truncation, eviction rebase).

matchless_upto: usize

Starts [next_pos, matchless_upto) proven MATCHLESS FOREVER by the finder: their walks found no accept and never reached the boundary, so they died entirely on immutable rows (see MatchScan::matchless_upto). The next rescan begins past them. This is the finder’s counterpart of dead_upto — and feeds it, since such a start is dead too: without it, a long run broken by one non-matching row costs Θ(r²) on EVERY rescan (each start walks to the break and dies), past the budget from r ≈ 840, and a partition in that state never completes a rescan again. Same resets as dead_upto.

freeze_truncated: bool

Whether the last freeze loop stopped on a spent budget with its region unfinished. The executor refreshes on this like on incomplete, so a truncated freeze resumes on the next watermark visit rather than only on the next arrival.

Implementations

impl IncrementalMatcher

pub fn new(nfa: Arc<Nfa>, skip: SkipMode) -> Self

pub fn reset(&mut self)

Reset to the freshly-constructed state, keeping the (shared) automaton and skip mode and reusing the collections’ allocations. Equivalent to a new matcher: used when a consumed prefix swallows the whole buffer, where reconstructing would re-clone the skip mode for nothing.

pub fn is_incomplete(&self) -> bool

Whether the last rescan was truncated by a spent budget — see the field doc. While true, provisional() is a leftmost-prefix under-approximation.

pub fn needs_refresh(&self) -> bool

Whether a visit’s rescan should be re-run with a fresh budget before deciding anything: the provisional tail is incomplete (IncrementalMatcher::is_incomplete), or the freeze stopped on a spent budget and has proven-dead progress to resume from.

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

Re-derive the provisional tail with a fresh budget, without feeding rows: the executor’s recovery valve for IncrementalMatcher::is_incomplete. Delegates to the same rescan advance performs.

pub fn resume_pos(&self) -> usize

The skip-resume position after the last frozen match — the left edge of the still-revisable region, in fed-position (= the executor’s buffer-index) terms. The executor’s emission gate re-checks gap liveness from here: a position in [resume_pos, match start) that is still alive at the boundary can produce an earlier, leftmost-preferred match and must hold the emission.

pub fn dead_prefix_end(&self) -> usize

End of the prefix of fed positions proven dead at the boundary — every position below it can never again start a match (see the dead_upto field). The executor’s own liveness walks (the dead-prefix prune, the emission gate’s gap check) skip these positions instead of re-deriving a verdict the freeze already paid for.

pub async fn advance( &mut self, new_row_seqs: &[Seq], matcher: &(impl CandidateMatcher + Sync), budget: &mut ScanBudget, memoize: bool, ) -> StreamExecutorResult<()>

Feed rows appended in ORDER BY order. new_row_seqs are the seqs of the newly appended rows; their buffer positions are the next positions after the rows fed so far. An empty call is a no-op.

Rescans only the mutable suffix [next_pos, n_rows) via the budgeted, memoized pull scan (Nfa::next_match through an OffsetMatcher), replacing the provisional tail of matched. It then freezes the leading run of suffix matches whose entire scan region [cursor, skip-resume) is dead at the boundary per Nfa::reaches_boundary_alive, advancing next_pos to the last frozen match’s resume position. Checking the whole region — not just the match’s start — matters: a gap position before the match can be alive (a longer, higher-preference alternative still in flight) and a future row could then produce a match there that consumes past this one, so nothing behind that gap may freeze. Liveness is checked with the raw matcher at absolute positions (only the finder needs the offset adapter, because it always scans from 0).

async fn rescan( &mut self, matcher: &(impl CandidateMatcher + Sync), budget: &mut ScanBudget, memoize: bool, ) -> StreamExecutorResult<()>

Re-derive the provisional tail over the already-fed mutable suffix [next_pos, n_rows) without feeding new rows — the rescan half of IncrementalMatcher::advance, exposed for the one caller shape where a rescan must happen with nothing to feed: an over-feed rollback. When rows beyond the caller’s current window were fed (e.g. an emit-on-update whole-buffer feed followed by a watermark visit over just the safe prefix), IncrementalMatcher::truncate_from_seq at the first over-fed row rolls the tail back but also drops every provisional match over the retained fed suffix; those rows are still fed, so there is nothing to advance (re-feeding them would double-enter seq_index) and the dropped matches must be re-derived in place. After this call provisional() equals a from-scratch batch scan of the fed rows.

pub fn finalize_evicted_prefix(&mut self, boundary: Seq) -> Finalized

Finalize the evicted prefix in place, or report that the matcher must be rebuilt. The caller is evicting [.., boundary) rows from its buffer; boundary is the first row seq that is not evicted (an exclusive upper bound). On success the matches lying wholly within the evicted prefix leave the diffable set, the surviving matcher is rebased onto the surviving buffer, and IncrementalMatcher::provisional then returns only still-revisable matches. The finalized matches are not returned (see Finalized::Rebased); tests derive them by diffing provisional() before/after.

This owns the finalize-vs-rebuild decision the executor used to make itself. It returns Finalized::MustRebuild — leaving the matcher untouched — in the shapes where an in-place rebase is unsound, so the executor never needs to pre-check (and no debug assertion can trip nor next_pos -= final_pos underflow):

• Boundary never fed (only unfed/unsafe rows survive) or past the frozen prefix (final_pos > next_pos): finalization would reach into the open, still-revisable region.
• A frozen match straddles the boundary strictly inside the frozen prefix — it starts before final_pos and ends after, while final_pos < next_pos. This arises only under the overlapping skip modes (TO NEXT ROW/TO FIRST/TO LAST), whose resume precedes the match end so a frozen span can outrun its own resume; see the consume/keep walk below for why it is declined. It is not reachable through the executor’s eviction (which always lands the boundary at final_pos == next_pos, see below), only through a direct API call.

Why the overlapping skip modes now rebase (they previously always rebuilt): the executor evicts from the first row still live at the safe boundary. Every position in [0, next_pos) was liveness-checked dead when its region froze, and deadness is monotone in the boundary, so at the (same-or-later) eviction boundary [0, next_pos) is still dead and the first live row is >= next_pos. The check above bounds final_pos <= next_pos, so through the executor final_pos == next_pos exactly. At that boundary every frozen match starts before next_pos and is therefore consumed — none is retained — so next_pos rebases to 0 and the entire surviving suffix is re-derived from scratch as the provisional tail. provisional() then trivially equals a fresh scan over the survivors, regardless of skip mode, and no rebased scan cursor can skip a start a fresh matcher would find. PAST LAST ROW additionally tiles [0, next_pos) with non-overlapping spans (resume == end), so any boundary within the frozen prefix retains a suffix of frozen matches soundly.

On Finalized::Rebased the evicted rows physically leave the front of the logical buffer: seq_index drains its prefix and next_pos/frozen_count shift down. Only rows at positions >= final_pos survive, and rebasing is a uniform downward shift of those rows; paths forward from a surviving position consume only surviving (unchanged) rows, so the freezing-soundness argument (a frozen region is dead at its boundary) is preserved. Match spans are anchored by seq, so retained and returned SeqMatches keep their identities without adjustment.

pub fn provisional(&self) -> &[SeqMatch]

Current provisional matches over everything fed so far, as if input ended now.