Enum regex_automata::nfa::thompson::pikevm::FollowEpsilon

enum FollowEpsilon {
    Explore(StateID),
    RestoreCapture {
        slot: SmallIndex,
        offset: Option<NonMaxUsize>,
    },
}

Represents a stack frame for use while computing an epsilon closure.

(An “epsilon closure” refers to the set of reachable NFA states from a single state without consuming any input. That is, the set of all epsilon transitions not only from that single state, but from every other state reachable by an epsilon transition as well. This is why it’s called a “closure.” Computing an epsilon closure is also done during DFA determinization! Compare and contrast the epsilon closure here in this PikeVM and the one used for determinization in crate::util::determinize.)

Computing the epsilon closure in a Thompson NFA proceeds via a depth first traversal over all epsilon transitions from a particular state. (A depth first traversal is important because it emulates the same priority of matches that is typically found in backtracking regex engines.) This depth first traversal is naturally expressed using recursion, but to avoid a call stack size proportional to the size of a regex, we put our stack on the heap instead.

This stack thus consists of call frames. The typical call frame is Explore, which instructs epsilon closure to explore the epsilon transitions from that state. (Subsequent epsilon transitions are then pushed on to the stack as more Explore frames.) If the state ID being explored has no epsilon transitions, then the capturing group slots are copied from the original state that sparked the epsilon closure (from the ‘step’ routine) to the state ID being explored. This way, capturing group slots are forwarded from the previous state to the next.

The other stack frame, RestoreCaptures, instructs the epsilon closure to set the position for a particular slot back to some particular offset. This frame is pushed when Explore sees a Capture transition. Explore will set the offset of the slot indicated in Capture to the current offset, and then push the old offset on to the stack as a RestoreCapture frame. Thus, the new offset is only used until the epsilon closure reverts back to the RestoreCapture frame. In effect, this gives the Capture epsilon transition its “scope” to only states that come “after” it during depth first traversal.

Variants

Explore(StateID)

Explore the epsilon transitions from a state ID.

RestoreCapture

Reset the given slot to the given offset (which might be None).

Fields

slot: SmallIndex

offset: Option<NonMaxUsize>

Trait Implementations

impl Clone for FollowEpsilon

fn clone(&self) -> FollowEpsilon

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for FollowEpsilon

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

Formats the value using the given formatter.