Debian Codegraph @

.cargo/vendor/regex-automata/src/nfa/thompson/mod.rs

raw
1 /*!
2 Defines a Thompson NFA and provides the [`PikeVM`](pikevm::PikeVM) and
3 [`BoundedBacktracker`](backtrack::BoundedBacktracker) regex engines.
4
5 A Thompson NFA (non-deterministic finite automaton) is arguably _the_ central
6 data type in this library. It is the result of what is commonly referred to as
7 "regex compilation." That is, turning a regex pattern from its concrete syntax
8 string into something that can run a search looks roughly like this:
9
10 * A `&str` is parsed into a [`regex-syntax::ast::Ast`](regex_syntax::ast::Ast).
11 * An `Ast` is translated into a [`regex-syntax::hir::Hir`](regex_syntax::hir::Hir).
12 * An `Hir` is compiled into a [`NFA`].
13 * The `NFA` is then used to build one of a few different regex engines:
14 * An `NFA` is used directly in the `PikeVM` and `BoundedBacktracker` engines.
15 * An `NFA` is used by a [hybrid NFA/DFA](crate::hybrid) to build out a DFA's
16 transition table at search time.
17 * An `NFA`, assuming it is one-pass, is used to build a full
18 [one-pass DFA](crate::dfa::onepass) ahead of time.
19 * An `NFA` is used to build a [full DFA](crate::dfa) ahead of time.
20
21 The [`meta`](crate::meta) regex engine makes all of these choices for you based
22 on various criteria. However, if you have a lower level use case, _you_ can
23 build any of the above regex engines and use them directly. But you must start
24 here by building an `NFA`.
25
26 # Details
27
28 It is perhaps worth expanding a bit more on what it means to go through the
29 `&str`->`Ast`->`Hir`->`NFA` process.
30
31 * Parsing a string into an `Ast` gives it a structured representation.
32 Crucially, the size and amount of work done in this step is proportional to the
33 size of the original string. No optimization or Unicode handling is done at
34 this point. This means that parsing into an `Ast` has very predictable costs.
35 Moreover, an `Ast` can be roundtripped back to its original pattern string as
36 written.
37 * Translating an `Ast` into an `Hir` is a process by which the structured
38 representation is simplified down to its most fundamental components.
39 Translation deals with flags such as case insensitivity by converting things
40 like `(?i:a)` to `[Aa]`. Translation is also where Unicode tables are consulted
41 to resolve things like `\p{Emoji}` and `\p{Greek}`. It also flattens each
42 character class, regardless of how deeply nested it is, into a single sequence
43 of non-overlapping ranges. All the various literal forms are thrown out in
44 favor of one common representation. Overall, the `Hir` is small enough to fit
45 into your head and makes analysis and other tasks much simpler.
46 * Compiling an `Hir` into an `NFA` formulates the regex into a finite state
47 machine whose transitions are defined over bytes. For example, an `Hir` might
48 have a Unicode character class corresponding to a sequence of ranges defined
49 in terms of `char`. Compilation is then responsible for turning those ranges
50 into a UTF-8 automaton. That is, an automaton that matches the UTF-8 encoding
51 of just the codepoints specified by those ranges. Otherwise, the main job of
52 an `NFA` is to serve as a byte-code of sorts for a virtual machine. It can be
53 seen as a sequence of instructions for how to match a regex.
54 */
55
56 #[cfg(feature = "nfa-backtrack")]
57 pub mod backtrack;
58 mod builder;
59 #[cfg(feature = "syntax")]
60 mod compiler;
61 mod error;
62 #[cfg(feature = "syntax")]
63 mod literal_trie;
64 #[cfg(feature = "syntax")]
65 mod map;
66 mod nfa;
67 #[cfg(feature = "nfa-pikevm")]
68 pub mod pikevm;
69 #[cfg(feature = "syntax")]
70 mod range_trie;
71
72 pub use self::{
73 builder::Builder,
74 error::BuildError,
75 nfa::{
76 DenseTransitions, PatternIter, SparseTransitions, State, Transition,
77 NFA,
78 },
79 };
80 #[cfg(feature = "syntax")]
81 pub use compiler::{Compiler, Config, WhichCaptures};