Crate peepmatic_automata[−][src]
Expand description
Finitestate transducer automata.
A transducer is a type of automata that has not only an input that it accepts or rejects, but also an output. While regular automata check whether an input string is in the set that the automata accepts, a transducer maps the input strings to values. A regular automata is sort of a compressed, immutable set, and a transducer is sort of a compressed, immutable keyvalue dictionary. A trie compresses a set of strings or map from a string to a value by sharing prefixes of the input string. Automata and transducers can compress even better: they can share both prefixes and suffixes. Index 1,600,000,000 Keys with Automata and Rust by Andrew Gallant (aka burntsushi) is a topnotch introduction.
If you’re looking for a generalpurpose transducers crate in Rust you’re
probably looking for the fst
crate. While this implementation
is fully generic and has no dependencies, its feature set is specific to
peepmatic
’s needs:

We need to associate extra data with each state: the match operation to evaluate next.

We can’t provide the full input string up front, so this crate must support incremental lookups. This is because the peephole optimizer is computing the input string incrementally and dynamically: it looks at the current state’s match operation, evaluates it, and then uses the result as the next character of the input string.

We also support incremental insertion and output when building the transducer. This is necessary because we don’t want to emit output values that bind a match on an optimization’s lefthand side’s pattern (for example) until after we’ve succeeded in matching it, which might not happen until we’ve reached the n^th state.

We need to support generic output values. The
fst
crate only supportsu64
outputs, while we need to build up an optimization’s righthand side instructions.
This implementation is based on Direct Construction of Minimal Acyclic Subsequential Transducers by Mihov and Maurel. That means that keys must be inserted in lexicographic order during construction.
Structs
A finitestate transducer automata.
A builder for a transducer automata.
A builder for a new entry in a transducer automata.
A lowlevel query of an Automaton
.
A state in an automaton.
Traits
An output type for a transducer automata.