Module dfa

Types and routines specific to lazy DFAs.

This module is the home of hybrid::dfa::DFA.

This module also contains a hybrid::dfa::Builder and a hybrid::dfa::Config for configuring and building a lazy DFA.

Structs

Builder

A builder for constructing a lazy deterministic finite automaton from regular expressions.

Cache

A cache represents a partially computed DFA.

Config

The configuration used for building a lazy DFA.

DFA

A hybrid NFA/DFA (also called a “lazy DFA”) for regex searching.

Lazy 🔒

A type that groups methods that require the base NFA/DFA and writable access to the cache.

LazyRef 🔒

A type that groups methods that require the base NFA/DFA and read-only access to the cache.

OverlappingState

Represents the current state of an overlapping search.

SearchProgress 🔒

Keeps track of the progress of the current search.

Enums

StateSaver 🔒

A simple type that encapsulates the saving of a state ID through a cache clearing.

Constants

MIN_STATES 🔒

The minimum number of states that a lazy DFA’s cache size must support.

SENTINEL_STATES 🔒

The number of “sentinel” states that get added to every lazy DFA.

Functions

minimum_cache_capacity 🔒

Based on the minimum number of states required for a useful lazy DFA cache, this returns a heuristic minimum number of bytes of heap space required.

minimum_lazy_state_id 🔒

Based on the minimum number of states required for a useful lazy DFA cache, this returns the minimum lazy state ID that must be representable.

skip_empty_utf8_splits_overlapping 🔒

Runs the given overlapping search function (forwards or backwards) until a match is found whose offset does not split a codepoint.

Type Aliases

StateMap 🔒

A map from states to state identifiers. When using std, we use a standard hashmap, since it’s a bit faster for this use case. (Other maps, like one’s based on FNV, have not yet been benchmarked.)