Enum aho_corasick::nfa::contiguous::StateTrans

enum StateTrans<'a> {
    Sparse {
        classes: &'a [u32],
        nexts: &'a [u32],
    },
    One {
        class: u8,
        next: u32,
    },
    Dense {
        class_to_next: &'a [u32],
    },
}

The underlying representation of sparse or dense transitions for a state.

Note that like State, we don’t typically construct values of this type during a search since we don’t always need all values and thus would represent a lot of wasteful work.

Variants

Sparse

A sparse representation of transitions for a state, where only non-FAIL transitions are explicitly represented.

Fields

classes: &'a [u32]

nexts: &'a [u32]

The transitions for this state, where each transition is packed into a u32. The low 8 bits correspond to the byte class for the transition, and the high 24 bits correspond to the next state ID.

This packing is why the max state ID allowed for a contiguous NFA is 2^24-1.

One

A “one transition” state that is never a match state.

These are by far the most common state, so we use a specialized and very compact representation for them.

Fields

class: u8

The element of this NFA’s alphabet that this transition is defined for.

next: u32

The state this should transition to if the current symbol is equal to ‘class’.

Dense

A dense representation of transitions for a state, where all transitions are explicitly represented, including transitions to the FAIL state.

Fields

class_to_next: &'a [u32]

A dense set of transitions to other states. The transitions may point to a FAIL state, in which case, the search should try the same transition lookup at ‘fail’.

Note that this is indexed by byte equivalence classes and not byte values. That means ‘class_to_next[byte]’ is wrong and ‘class_to_next[classes.get(byte)]’ is correct. The number of transitions is always equivalent to ‘classes.alphabet_len()’.

Trait Implementations

impl<'a> Clone for StateTrans<'a>

fn clone(&self) -> StateTrans<'a>

Returns a copy of the value.

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

Performs copy-assignment from source.