Struct regex_automata::nfa::thompson::pikevm::ActiveStates

struct ActiveStates {
    set: SparseSet,
    slot_table: SlotTable,
}

A set of active states used to “simulate” the execution of an NFA via the PikeVM.

There are two sets of these used during NFA simulation. One set corresponds to the “current” set of states being traversed for the current position in a haystack. The other set corresponds to the “next” set of states being built, which will become the new “current” set for the next position in the haystack. These two sets correspond to CLIST and NLIST in Thompson’s original paper regexes: https://dl.acm.org/doi/pdf/10.1145/363347.363387

In addition to representing a set of NFA states, this also maintains slot values for each state. These slot values are what turn the NFA simulation into the “Pike VM.” Namely, they track capturing group values for each state. During the computation of epsilon closure, we copy slot values from states in the “current” set to the “next” set. Eventually, once a match is found, the slot values for that match state are what we write to the caller provided ‘Captures’ value.

Fields

set: SparseSet

The set of active NFA states. This set preserves insertion order, which is critical for simulating the match semantics of backtracking regex engines.

slot_table: SlotTable

The slots for every NFA state, where each slot stores a (possibly absent) offset. Every capturing group has two slots. One for a start offset and one for an end offset.

Implementations

impl ActiveStates

fn new(re: &PikeVM) -> ActiveStates

Create a new set of active states for the given PikeVM. The active states returned may only be used with the given PikeVM. (Use ‘reset’ to re-purpose the allocation for a different PikeVM.)

fn reset(&mut self, re: &PikeVM)

Reset this set of active states such that it can be used with the given PikeVM (and only that PikeVM).

fn memory_usage(&self) -> usize

Return the heap memory usage, in bytes, used by this set of active states.

This does not include the stack size of this value.

fn setup_search(&mut self, captures_slot_len: usize)

Setup this set of active states for a new search. The given slot length should be the number of slots in a caller provided ‘Captures’ (and may be zero).

Trait Implementations

impl Clone for ActiveStates

fn clone(&self) -> ActiveStates

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for ActiveStates

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

Formats the value using the given formatter.