Available on crate feature
nfa-thompson
only.Expand description
Defines a Thompson NFA and provides the PikeVM
and
BoundedBacktracker
regex engines.
A Thompson NFA (non-deterministic finite automaton) is arguably the central data type in this library. It is the result of what is commonly referred to as “regex compilation.” That is, turning a regex pattern from its concrete syntax string into something that can run a search looks roughly like this:
- A
&str
is parsed into aregex-syntax::ast::Ast
. - An
Ast
is translated into aregex-syntax::hir::Hir
. - An
Hir
is compiled into aNFA
. - The
NFA
is then used to build one of a few different regex engines:- An
NFA
is used directly in thePikeVM
andBoundedBacktracker
engines. - An
NFA
is used by a hybrid NFA/DFA to build out a DFA’s transition table at search time. - An
NFA
, assuming it is one-pass, is used to build a full one-pass DFA ahead of time. - An
NFA
is used to build a full DFA ahead of time.
- An
The meta
regex engine makes all of these choices for you based
on various criteria. However, if you have a lower level use case, you can
build any of the above regex engines and use them directly. But you must start
here by building an NFA
.
§Details
It is perhaps worth expanding a bit more on what it means to go through the
&str
->Ast
->Hir
->NFA
process.
- Parsing a string into an
Ast
gives it a structured representation. Crucially, the size and amount of work done in this step is proportional to the size of the original string. No optimization or Unicode handling is done at this point. This means that parsing into anAst
has very predictable costs. Moreover, anAst
can be roundtripped back to its original pattern string as written. - Translating an
Ast
into anHir
is a process by which the structured representation is simplified down to its most fundamental components. Translation deals with flags such as case insensitivity by converting things like(?i:a)
to[Aa]
. Translation is also where Unicode tables are consulted to resolve things like\p{Emoji}
and\p{Greek}
. It also flattens each character class, regardless of how deeply nested it is, into a single sequence of non-overlapping ranges. All the various literal forms are thrown out in favor of one common representation. Overall, theHir
is small enough to fit into your head and makes analysis and other tasks much simpler. - Compiling an
Hir
into anNFA
formulates the regex into a finite state machine whose transitions are defined over bytes. For example, anHir
might have a Unicode character class corresponding to a sequence of ranges defined in terms ofchar
. Compilation is then responsible for turning those ranges into a UTF-8 automaton. That is, an automaton that matches the UTF-8 encoding of just the codepoints specified by those ranges. Otherwise, the main job of anNFA
is to serve as a byte-code of sorts for a virtual machine. It can be seen as a sequence of instructions for how to match a regex.
Modules§
- backtrack
nfa-backtrack
An NFA backed bounded backtracker for executing regex searches with capturing groups. - pikevm
nfa-pikevm
An NFA backed Pike VM for executing regex searches with capturing groups.
Structs§
- An error that can occurred during the construction of a thompson NFA.
- An abstraction for building Thompson NFAs by hand.
- Compiler
syntax
A builder for compiling an NFA from a regex’s high-level intermediate representation (HIR). - Config
syntax
The configuration used for a Thompson NFA compiler. - A sequence of transitions used to represent a dense state.
- A byte oriented Thompson non-deterministic finite automaton (NFA).
- An iterator over all pattern IDs in an NFA.
- A sequence of transitions used to represent a sparse state.
- A single transition to another state.
Enums§
- A state in an NFA.
- Which
Captures syntax
A configuration indicating which kinds ofState::Capture
states to include.