Struct aho_corasick::util::remapper::Remapper

pub(crate) struct Remapper {
    map: Vec<StateID>,
    idx: IndexMapper,
}

Remapper is an abstraction the manages the remapping of state IDs in a finite state machine. This is useful when one wants to shuffle states into different positions in the machine.

One of the key complexities this manages is the ability to correctly move one state multiple times.

Once shuffling is complete, remap must be called, which will rewrite all pertinent transitions to updated state IDs. Neglecting to call remap will almost certainly result in a corrupt machine.

Fields

map: Vec<StateID>

A map from the index of a state to its pre-multiplied identifier.

When a state is swapped with another, then their corresponding locations in this map are also swapped. Thus, its new position will still point to its old pre-multiplied StateID.

While there is a bit more to it, this then allows us to rewrite the state IDs in a DFA’s transition table in a single pass. This is done by iterating over every ID in this map, then iterating over each transition for the state at that ID and re-mapping the transition from old_id to map[dfa.to_index(old_id)]. That is, we find the position in this map where old_id started, and set it to where it ended up after all swaps have been completed.

idx: IndexMapper

A way to map indices to state IDs (and back).

Implementations

impl Remapper

pub(crate) fn new(r: &impl Remappable, stride2: usize) -> Remapper

Create a new remapper from the given remappable implementation. The remapper can then be used to swap states. The remappable value given here must the same one given to swap and remap.

The given stride should be the stride of the transition table expressed as a power of 2. This stride is used to map between state IDs and state indices. If state IDs and state indices are equivalent, then provide a stride2 of 0, which acts as an identity.

pub(crate) fn swap( &mut self, r: &mut impl Remappable, id1: StateID, id2: StateID, )

Swap two states. Once this is called, callers must follow through to call remap, or else it’s possible for the underlying remappable value to be in a corrupt state.

pub(crate) fn remap(self, r: &mut impl Remappable)

Complete the remapping process by rewriting all state IDs in the remappable value according to the swaps performed.

Trait Implementations

impl Debug for Remapper

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

Formats the value using the given formatter.