Struct regex_automata::nfa::thompson::literal_trie::Frame

struct Frame<'a> {
    chunks: StateChunksIter<'a>,
    transitions: Iter<'a, Transition>,
    union: Vec<StateID>,
    sparse: Vec<Transition>,
}

An explicit stack frame used for traversing the trie without using recursion.

Each frame is tied to the traversal of a single trie state. The frame is dropped once the entire state (and all of its children) have been visited. The “output” of compiling a state is the ‘union’ vector, which is turn converted to a NFA union state. Each branch of the union corresponds to a chunk in the trie state.

‘sparse’ corresponds to the set of transitions for a particular chunk in a trie state. It is ultimately converted to an NFA sparse state. The ‘sparse’ field, after being converted to a sparse NFA state, is reused for any subsequent chunks in the trie state, if any exist.

Fields

chunks: StateChunksIter<'a>

The remaining chunks to visit for a trie state.

transitions: Iter<'a, Transition>

The transitions of the current chunk that we’re iterating over. Since every trie state has at least one chunk, every frame is initialized with the first chunk’s transitions ready to be consumed.

union: Vec<StateID>

The NFA state IDs pointing to the start of each chunk compiled by this trie state. This ultimately gets converted to an NFA union once the entire trie state (and all of its children) have been compiled. The order of these matters for leftmost-first match semantics, since earlier matches in the union are preferred over later ones.

sparse: Vec<Transition>

The actual NFA transitions for a single chunk in a trie state. This gets converted to an NFA sparse state, and its corresponding NFA state ID should get added to ‘union’.

Implementations

impl<'a> Frame<'a>

fn new(state: &'a State) -> Frame<'a>

Create a new stack frame for trie traversal. This initializes the ‘transitions’ iterator to the transitions for the first chunk, with the ‘chunks’ iterator being every chunk after the first one.

Trait Implementations

impl<'a> Debug for Frame<'a>

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

Formats the value using the given formatter.