Function regex_automata::util::determinize::next

pub(crate) fn next(
    nfa: &NFA,
    match_kind: MatchKind,
    sparses: &mut SparseSets,
    stack: &mut Vec<StateID>,
    state: &State,
    unit: Unit,
    empty_builder: StateBuilderEmpty,
) -> StateBuilderNFA

Compute the set of all reachable NFA states, including the full epsilon closure, from a DFA state for a single unit of input. The set of reachable states is returned as a StateBuilderNFA. The StateBuilderNFA returned also includes any look-behind assertions satisfied by unit, in addition to whether it is a match state. For multi-pattern DFAs, the builder will also include the pattern IDs that match (in the order seen).

nfa must be able to resolve any NFA state in state and any NFA state reachable via the epsilon closure of any NFA state in state. sparses must have capacity equivalent to nfa.len().

match_kind should correspond to the match semantics implemented by the DFA being built. Generally speaking, for leftmost-first match semantics, states that appear after the first NFA match state will not be included in the StateBuilderNFA returned since they are impossible to visit.

sparses is used as scratch space for NFA traversal. Other than their capacity requirements (detailed above), there are no requirements on what’s contained within them (if anything). Similarly, what’s inside of them once this routine returns is unspecified.

stack must have length 0. It is used as scratch space for depth first traversal. After returning, it is guaranteed that stack will have length 0.

state corresponds to the current DFA state on which one wants to compute the transition for the input unit.

empty_builder corresponds to the builder allocation to use to produce a complete StateBuilderNFA state. If the state is not needed (or is already cached), then it can be cleared and reused without needing to create a new State. The StateBuilderNFA state returned is final and ready to be turned into a State if necessary.