Struct aho_corasick::nfa::noncontiguous::State

pub(crate) struct State {
    sparse: StateID,
    dense: StateID,
    matches: StateID,
    fail: StateID,
    depth: SmallIndex,
}

A representation of a sparse NFA state for an Aho-Corasick automaton.

It contains the transitions to the next state, a failure transition for cases where there exists no other transition for the current input byte and the matches implied by visiting this state (if any).

Fields

sparse: StateID

A pointer to NFA::trans corresponding to the head of a linked list containing all of the transitions for this state.

This is StateID::ZERO if and only if this state has zero transitions.

dense: StateID

A pointer to a row of N transitions in NFA::dense. These transitions correspond precisely to what is obtained by traversing sparse, but permits constant time lookup.

When this is zero (which is true for most states in the default configuration), then this state has no dense representation.

Note that N is equal to NFA::byte_classes::alphabet_len(). This is typically much less than 256 (the maximum value).

matches: StateID

A pointer to NFA::matches corresponding to the head of a linked list containing all of the matches for this state.

This is StateID::ZERO if and only if this state is not a match state.

fail: StateID

The state that should be transitioned to if the current byte in the haystack does not have a corresponding transition defined in this state.

depth: SmallIndex

The depth of this state. Specifically, this is the distance from this state to the starting state. (For the special sentinel states DEAD and FAIL, their depth is always 0.) The depth of a starting state is 0.

Note that depth is currently not used in this non-contiguous NFA. It may in the future, but it is used in the contiguous NFA. Namely, it permits an optimization where states near the starting state have their transitions stored in a dense fashion, but all other states have their transitions stored in a sparse fashion. (This non-contiguous NFA uses a sparse representation for all states unconditionally.) In any case, this is really the only convenient place to compute and store this information, which we need when building the contiguous NFA.

Implementations

impl State

pub(crate) fn is_match(&self) -> bool

Return true if and only if this state is a match state.

pub(crate) fn fail(&self) -> StateID

Returns the failure transition for this state.

pub(crate) fn depth(&self) -> SmallIndex

Returns the depth of this state. That is, the number of transitions this state is from the start state of the NFA.

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.