Trait regex_automata::dfa::remapper::Remappable

source · 
pub(super) trait Remappable: Debug {
    // Required methods
    fn state_len(&self) -> usize;
    fn stride2(&self) -> usize;
    fn swap_states(&mut self, id1: StateID, id2: StateID);
    fn remap(&mut self, map: impl Fn(StateID) -> StateID);
}
Expand description

Remappable is a tightly coupled abstraction that facilitates remapping state identifiers in DFAs.

The main idea behind remapping state IDs is that DFAs often need to check if a certain state is a “special” state of some kind (like a match state) during a search. Since this is extremely perf critical code, we want this check to be as fast as possible. Partitioning state IDs into, for example, into “non-match” and “match” states means one can tell if a state is a match state via a simple comparison of the state ID.

The issue is that during the DFA construction process, it’s not particularly easy to partition the states. Instead, the simplest thing is to often just do a pass over all of the states and shuffle them into their desired partitionings. To do that, we need a mechanism for swapping states. Hence, this abstraction.

Normally, for such little code, I would just duplicate it. But this is a key optimization and the implementation is a bit subtle. So the abstraction is basically a ham-fisted attempt at DRY. The only place we use this is in the dense and one-pass DFAs.

See also src/dfa/special.rs for a more detailed explanation of how dense DFAs are partitioned.

Required Methods§

source

fn state_len(&self) -> usize

Return the total number of states.

source

fn stride2(&self) -> usize

Return the power-of-2 exponent that yields the stride. The pertinent laws here are, where N=stride2: 2^N=stride and len(alphabet) <= stride.

source

fn swap_states(&mut self, id1: StateID, id2: StateID)

Swap the states pointed to by the given IDs. The underlying finite state machine should be mutated such that all of the transitions in id1 are now in the memory region where the transitions for id2 were, and all of the transitions in id2 are now in the memory region where the transitions for id1 were.

Essentially, this “moves” id1 to id2 and id2 to id1.

It is expected that, after calling this, the underlying value will be left in an inconsistent state, since any other transitions pointing to, e.g., id1 need to be updated to point to id2, since that’s where id1 moved to.

In order to “fix” the underlying inconsistent state, a Remapper should be used to guarantee that remap is called at the appropriate time.

source

fn remap(&mut self, map: impl Fn(StateID) -> StateID)

This must remap every single state ID in the underlying value according to the function given. For example, in a DFA, this should remap every transition and every starting state ID.

Object Safety§

This trait is not object safe.

Implementors§