Module nfa 

Row-pattern NFA for MATCH_RECOGNIZE.

A Pattern (the supported v1 subset of the SQL PATTERN clause) is compiled to a Thompson-construction NFA whose labelled transitions are pattern variables. The simulation consumes a sequence of rows, where each row is summarised by the set of pattern variables whose DEFINE predicate it satisfies, and finds the greedy longest match from a start position (ONE ROW PER MATCH + AFTER MATCH SKIP PAST LAST ROW).

Variable→predicate evaluation and the streaming/state layer live elsewhere; this module is pure and deterministic so it can be unit-tested without a cluster.

Structs

Fragment 🔒

A sub-NFA fragment with one entry and one exit state.

Frame 🔒

One frame of the explicit walk stack: the state under exploration at row pos, and how far through its transitions the walk has got.

LabeledMatch

A match span together with the pattern variable assigned to each matched row. labels[i] is the variable that rows[start + i] was matched as.

MatchScan

Cursor for Nfa::next_match: the next start position the scan will try. A fresh scan starts at 0; Nfa::next_match advances it by the AFTER MATCH SKIP mode on every match returned (or by one row past a non-matching start), so pulling repeatedly enumerates exactly the match sequence Nfa::find_matches_dynamic would collect.

Memo 🔒

Per-start (state, position) failure memo for the backtracking walkers.

Nfa

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

NfaBuilder 🔒

ScanBudget

Per-visit budget on NFA walk steps — predicate evaluations AND edges taken (row consumptions and ε-transitions) — shared by every walk of one partition visit (matching, eviction liveness, extension probing). ε-edges are charged deliberately: metering only predicate evaluations left ε-traversal free, so a large NFA could spend arbitrary CPU per metered evaluation and the budget was not actually a CPU bound.

Enums

Enter 🔒

A frame’s verdict on entry.

Goal 🔒

What a Nfa::walk is looking for. The three questions the executor asks of the automaton share one traversal and differ only in when a frame is a verdict and in what a consuming edge may do at the row boundary.

Pattern

The supported v1 subset of a row pattern.

Quantifier

A quantifier applied to a sub-pattern. Greedy semantics only (v1).

SkipDegradation

Why a variable-targeted AFTER MATCH SKIP could not resume where the query asked, and which weaker strategy the resume position fell back to. Returned by SkipMode::next_pos next to the position instead of being reported here: this module stays pure (no error reporter, no executor types), and the executor — which owns the actor’s EvalErrorReport — decides what to do with it.

SkipMode

Where the scan resumes after a match (the AFTER MATCH SKIP strategy).

Transition 🔒

Visited 🔒

Visited-state guard for one traversal position of the dynamic matcher. ε-transitions keep the position, so each consumed row starts a fresh set (see Nfa::walk); these sets are opened O(rows × branches) times per partition visit, so their allocation cost matters. The common case — an automaton with at most 64 states — is a single u64 bitmask (no allocation, membership is a bit test); larger automata (deep PERMUTE expansions) fall back to a HashSet.

Traits

CandidateMatcher

Decides whether the row at a physical position can be bound to a pattern variable, given the variables already bound to the earlier rows of the in-progress match. This is how DEFINE predicates are evaluated during matching: a predicate may reference the current row, its physical neighbours (PREV/NEXT), and the running values of other pattern variables (e.g. A.price), so membership cannot be precomputed independently of the match path.

Functions

permutations 🔒

All orderings of items. Only used for PERMUTE, which has a small arity in practice.

Type Aliases

StateId 🔒