Struct regex_automata::nfa::thompson::literal_trie::State

struct State {
    transitions: Vec<Transition>,
    chunks: Vec<(usize, usize)>,
}

A state in a trie.

This uses a sparse representation. Since we don’t use literal tries for searching, and ultimately (and compilation requires visiting every transition anyway), we use a sparse representation for transitions. This means we save on memory, at the expense of ‘LiteralTrie::add’ being perhaps a bit slower.

While ‘transitions’ is pretty standard as far as tries goes, the ‘chunks’ piece here is more unusual. In effect, ‘chunks’ defines a partitioning of ‘transitions’, where each chunk corresponds to a distinct set of transitions. The key invariant is that a transition in one chunk cannot be moved to another chunk. This is the secret sauce that preserve leftmost-first match semantics.

A new chunk is added whenever we mark a state as a match state. Once a new chunk is added, the old active chunk is frozen and is never mutated again. The new chunk becomes the active chunk, which is defined as ‘&transitions[chunks.last().map_or(0, |c| c.1)..]’. Thus, a state where ‘chunks’ is empty actually contains one chunk. Thus, every state contains at least one (possibly empty) chunk.

A “leaf” state is a state that has no outgoing transitions (so ‘transitions’ is empty). Note that there is no way for a leaf state to be a non-matching state. (Although while building the trie, within ‘add’, a leaf state may exist while not containing any matches. But this invariant is only broken within ‘add’. Once ‘add’ returns, the invariant is upheld.)

Fields

transitions: Vec<Transition>

chunks: Vec<(usize, usize)>

Implementations

impl State

fn add_match(&mut self)

Mark this state as a match state and freeze the active chunk such that it can not be further mutated.

fn is_leaf(&self) -> bool

Returns true if and only if this state is a leaf state. That is, a state that has no outgoing transitions.

fn chunks(&self) -> StateChunksIter<'_>

Returns an iterator over all of the chunks (including the currently active chunk) in this state. Since the active chunk is included, the iterator is guaranteed to always yield at least one chunk (although the chunk may be empty).

fn active_chunk(&self) -> &[Transition]

Returns the active chunk as a slice of transitions.

fn active_chunk_start(&self) -> usize

Returns the index into ‘transitions’ where the active chunk starts.

Trait Implementations

impl Clone for State

fn clone(&self) -> State

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for State

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

Formats the value using the given formatter.

impl Default for State

fn default() -> State

Returns the “default value” for a type.