Debian Codegraph @

.cargo/vendor/regex-automata/src/dfa/mod.rs

raw
1 /*!
2 A module for building and searching with deterministic finite automata (DFAs).
3
4 Like other modules in this crate, DFAs support a rich regex syntax with Unicode
5 features. DFAs also have extensive options for configuring the best space vs
6 time trade off for your use case and provides support for cheap deserialization
7 of automata for use in `no_std` environments.
8
9 If you're looking for lazy DFAs that build themselves incrementally during
10 search, then please see the top-level [`hybrid` module](crate::hybrid).
11
12 # Overview
13
14 This section gives a brief overview of the primary types in this module:
15
16 * A [`regex::Regex`] provides a way to search for matches of a regular
17 expression using DFAs. This includes iterating over matches with both the start
18 and end positions of each match.
19 * A [`dense::DFA`] provides low level access to a DFA that uses a dense
20 representation (uses lots of space, but fast searching).
21 * A [`sparse::DFA`] provides the same API as a `dense::DFA`, but uses a sparse
22 representation (uses less space, but slower searching).
23 * An [`Automaton`] trait that defines an interface that both dense and sparse
24 DFAs implement. (A `regex::Regex` is generic over this trait.)
25 * Both dense DFAs and sparse DFAs support serialization to raw bytes (e.g.,
26 [`dense::DFA::to_bytes_little_endian`]) and cheap deserialization (e.g.,
27 [`dense::DFA::from_bytes`]).
28
29 There is also a [`onepass`] module that provides a [one-pass
30 DFA](onepass::DFA). The unique advantage of this DFA is that, for the class
31 of regexes it can be built with, it supports reporting the spans of matching
32 capturing groups. It is the only DFA in this crate capable of such a thing.
33
34 # Example: basic regex searching
35
36 This example shows how to compile a regex using the default configuration
37 and then use it to find matches in a byte string:
38
39 ```
40 use regex_automata::{Match, dfa::regex::Regex};
41
42 let re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}")?;
43 let text = b"2018-12-24 2016-10-08";
44 let matches: Vec<Match> = re.find_iter(text).collect();
45 assert_eq!(matches, vec![
46 Match::must(0, 0..10),
47 Match::must(0, 11..21),
48 ]);
49 # Ok::<(), Box<dyn std::error::Error>>(())
50 ```
51
52 # Example: searching with regex sets
53
54 The DFAs in this module all fully support searching with multiple regexes
55 simultaneously. You can use this support with standard leftmost-first style
56 searching to find non-overlapping matches:
57
58 ```
59 # if cfg!(miri) { return Ok(()); } // miri takes too long
60 use regex_automata::{Match, dfa::regex::Regex};
61
62 let re = Regex::new_many(&[r"\w+", r"\S+"])?;
63 let text = b"@foo bar";
64 let matches: Vec<Match> = re.find_iter(text).collect();
65 assert_eq!(matches, vec![
66 Match::must(1, 0..4),
67 Match::must(0, 5..8),
68 ]);
69 # Ok::<(), Box<dyn std::error::Error>>(())
70 ```
71
72 # Example: use sparse DFAs
73
74 By default, compiling a regex will use dense DFAs internally. This uses more
75 memory, but executes searches more quickly. If you can abide slower searches
76 (somewhere around 3-5x), then sparse DFAs might make more sense since they can
77 use significantly less space.
78
79 Using sparse DFAs is as easy as using `Regex::new_sparse` instead of
80 `Regex::new`:
81
82 ```
83 use regex_automata::{Match, dfa::regex::Regex};
84
85 let re = Regex::new_sparse(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
86 let text = b"2018-12-24 2016-10-08";
87 let matches: Vec<Match> = re.find_iter(text).collect();
88 assert_eq!(matches, vec![
89 Match::must(0, 0..10),
90 Match::must(0, 11..21),
91 ]);
92 # Ok::<(), Box<dyn std::error::Error>>(())
93 ```
94
95 If you already have dense DFAs for some reason, they can be converted to sparse
96 DFAs and used to build a new `Regex`. For example:
97
98 ```
99 use regex_automata::{Match, dfa::regex::Regex};
100
101 let dense_re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
102 let sparse_re = Regex::builder().build_from_dfas(
103 dense_re.forward().to_sparse()?,
104 dense_re.reverse().to_sparse()?,
105 );
106 let text = b"2018-12-24 2016-10-08";
107 let matches: Vec<Match> = sparse_re.find_iter(text).collect();
108 assert_eq!(matches, vec![
109 Match::must(0, 0..10),
110 Match::must(0, 11..21),
111 ]);
112 # Ok::<(), Box<dyn std::error::Error>>(())
113 ```
114
115 # Example: deserialize a DFA
116
117 This shows how to first serialize a DFA into raw bytes, and then deserialize
118 those raw bytes back into a DFA. While this particular example is a
119 bit contrived, this same technique can be used in your program to
120 deserialize a DFA at start up time or by memory mapping a file.
121
122 ```
123 use regex_automata::{Match, dfa::{dense, regex::Regex}};
124
125 let re1 = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
126 // serialize both the forward and reverse DFAs, see note below
127 let (fwd_bytes, fwd_pad) = re1.forward().to_bytes_native_endian();
128 let (rev_bytes, rev_pad) = re1.reverse().to_bytes_native_endian();
129 // now deserialize both---we need to specify the correct type!
130 let fwd: dense::DFA<&[u32]> = dense::DFA::from_bytes(&fwd_bytes[fwd_pad..])?.0;
131 let rev: dense::DFA<&[u32]> = dense::DFA::from_bytes(&rev_bytes[rev_pad..])?.0;
132 // finally, reconstruct our regex
133 let re2 = Regex::builder().build_from_dfas(fwd, rev);
134
135 // we can use it like normal
136 let text = b"2018-12-24 2016-10-08";
137 let matches: Vec<Match> = re2.find_iter(text).collect();
138 assert_eq!(matches, vec![
139 Match::must(0, 0..10),
140 Match::must(0, 11..21),
141 ]);
142 # Ok::<(), Box<dyn std::error::Error>>(())
143 ```
144
145 There are a few points worth noting here:
146
147 * We need to extract the raw DFAs used by the regex and serialize those. You
148 can build the DFAs manually yourself using [`dense::Builder`], but using
149 the DFAs from a `Regex` guarantees that the DFAs are built correctly. (In
150 particular, a `Regex` constructs a reverse DFA for finding the starting
151 location of matches.)
152 * To convert the DFA to raw bytes, we use the `to_bytes_native_endian` method.
153 In practice, you'll want to use either [`dense::DFA::to_bytes_little_endian`]
154 or [`dense::DFA::to_bytes_big_endian`], depending on which platform you're
155 deserializing your DFA from. If you intend to deserialize on either platform,
156 then you'll need to serialize both and deserialize the right one depending on
157 your target's endianness.
158 * Safely deserializing a DFA requires verifying the raw bytes, particularly if
159 they are untrusted, since an invalid DFA could cause logical errors, panics
160 or even undefined behavior. This verification step requires visiting all of
161 the transitions in the DFA, which can be costly. If cheaper verification is
162 desired, then [`dense::DFA::from_bytes_unchecked`] is available that only does
163 verification that can be performed in constant time. However, one can only use
164 this routine if the caller can guarantee that the bytes provided encoded a
165 valid DFA.
166
167 The same process can be achieved with sparse DFAs as well:
168
169 ```
170 use regex_automata::{Match, dfa::{sparse, regex::Regex}};
171
172 let re1 = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap();
173 // serialize both
174 let fwd_bytes = re1.forward().to_sparse()?.to_bytes_native_endian();
175 let rev_bytes = re1.reverse().to_sparse()?.to_bytes_native_endian();
176 // now deserialize both---we need to specify the correct type!
177 let fwd: sparse::DFA<&[u8]> = sparse::DFA::from_bytes(&fwd_bytes)?.0;
178 let rev: sparse::DFA<&[u8]> = sparse::DFA::from_bytes(&rev_bytes)?.0;
179 // finally, reconstruct our regex
180 let re2 = Regex::builder().build_from_dfas(fwd, rev);
181
182 // we can use it like normal
183 let text = b"2018-12-24 2016-10-08";
184 let matches: Vec<Match> = re2.find_iter(text).collect();
185 assert_eq!(matches, vec![
186 Match::must(0, 0..10),
187 Match::must(0, 11..21),
188 ]);
189 # Ok::<(), Box<dyn std::error::Error>>(())
190 ```
191
192 Note that unlike dense DFAs, sparse DFAs have no alignment requirements.
193 Conversely, dense DFAs must be be aligned to the same alignment as a
194 [`StateID`](crate::util::primitives::StateID).
195
196 # Support for `no_std` and `alloc`-only
197
198 This crate comes with `alloc` and `std` features that are enabled by default.
199 When the `alloc` or `std` features are enabled, the API of this module will
200 include the facilities necessary for compiling, serializing, deserializing
201 and searching with DFAs. When only the `alloc` feature is enabled, then
202 implementations of the `std::error::Error` trait are dropped, but everything
203 else generally remains the same. When both the `alloc` and `std` features are
204 disabled, the API of this module will shrink such that it only includes the
205 facilities necessary for deserializing and searching with DFAs.
206
207 The intended workflow for `no_std` environments is thus as follows:
208
209 * Write a program with the `alloc` or `std` features that compiles and
210 serializes a regular expression. You may need to serialize both little and big
211 endian versions of each DFA. (So that's 4 DFAs in total for each regex.)
212 * In your `no_std` environment, follow the examples above for deserializing
213 your previously serialized DFAs into regexes. You can then search with them as
214 you would any regex.
215
216 Deserialization can happen anywhere. For example, with bytes embedded into a
217 binary or with a file memory mapped at runtime.
218
219 The `regex-cli` command (found in the same repository as this crate) can be
220 used to serialize DFAs to files and generate Rust code to read them.
221
222 # Syntax
223
224 This module supports the same syntax as the `regex` crate, since they share the
225 same parser. You can find an exhaustive list of supported syntax in the
226 [documentation for the `regex` crate](https://docs.rs/regex/1/regex/#syntax).
227
228 There are two things that are not supported by the DFAs in this module:
229
230 * Capturing groups. The DFAs (and [`Regex`](regex::Regex)es built on top
231 of them) can only find the offsets of an entire match, but cannot resolve
232 the offsets of each capturing group. This is because DFAs do not have the
233 expressive power necessary.
234 * Unicode word boundaries. These present particularly difficult challenges for
235 DFA construction and would result in an explosion in the number of states.
236 One can enable [`dense::Config::unicode_word_boundary`] though, which provides
237 heuristic support for Unicode word boundaries that only works on ASCII text.
238 Otherwise, one can use `(?-u:\b)` for an ASCII word boundary, which will work
239 on any input.
240
241 There are no plans to lift either of these limitations.
242
243 Note that these restrictions are identical to the restrictions on lazy DFAs.
244
245 # Differences with general purpose regexes
246
247 The main goal of the [`regex`](https://docs.rs/regex) crate is to serve as a
248 general purpose regular expression engine. It aims to automatically balance low
249 compile times, fast search times and low memory usage, while also providing
250 a convenient API for users. In contrast, this module provides a lower level
251 regular expression interface based exclusively on DFAs that is a bit less
252 convenient while providing more explicit control over memory usage and search
253 times.
254
255 Here are some specific negative differences:
256
257 * **Compilation can take an exponential amount of time and space** in the size
258 of the regex pattern. While most patterns do not exhibit worst case exponential
259 time, such patterns do exist. For example, `[01]*1[01]{N}` will build a DFA
260 with approximately `2^(N+2)` states. For this reason, untrusted patterns should
261 not be compiled with this module. (In the future, the API may expose an option
262 to return an error if the DFA gets too big.)
263 * This module does not support sub-match extraction via capturing groups, which
264 can be achieved with the regex crate's "captures" API.
265 * While the regex crate doesn't necessarily sport fast compilation times,
266 the regexes in this module are almost universally slow to compile, especially
267 when they contain large Unicode character classes. For example, on my system,
268 compiling `\w{50}` takes about 1 second and almost 15MB of memory! (Compiling
269 a sparse regex takes about the same time but only uses about 1.2MB of
270 memory.) Conversely, compiling the same regex without Unicode support, e.g.,
271 `(?-u)\w{50}`, takes under 1 millisecond and about 15KB of memory. For this
272 reason, you should only use Unicode character classes if you absolutely need
273 them! (They are enabled by default though.)
274 * This module does not support Unicode word boundaries. ASCII word bondaries
275 may be used though by disabling Unicode or selectively doing so in the syntax,
276 e.g., `(?-u:\b)`. There is also an option to
277 [heuristically enable Unicode word boundaries](crate::dfa::dense::Config::unicode_word_boundary),
278 where the corresponding DFA will give up if any non-ASCII byte is seen.
279 * As a lower level API, this module does not do literal optimizations
280 automatically. Although it does provide hooks in its API to make use of the
281 [`Prefilter`](crate::util::prefilter::Prefilter) trait. Missing literal
282 optimizations means that searches may run much slower than what you're
283 accustomed to, although, it does provide more predictable and consistent
284 performance.
285 * There is no `&str` API like in the regex crate. In this module, all APIs
286 operate on `&[u8]`. By default, match indices are
287 guaranteed to fall on UTF-8 boundaries, unless either of
288 [`syntax::Config::utf8`](crate::util::syntax::Config::utf8) or
289 [`thompson::Config::utf8`](crate::nfa::thompson::Config::utf8) are disabled.
290
291 With some of the downsides out of the way, here are some positive differences:
292
293 * Both dense and sparse DFAs can be serialized to raw bytes, and then cheaply
294 deserialized. Deserialization can be done in constant time with the unchecked
295 APIs, since searching can be performed directly on the raw serialized bytes of
296 a DFA.
297 * This module was specifically designed so that the searching phase of a
298 DFA has minimal runtime requirements, and can therefore be used in `no_std`
299 environments. While `no_std` environments cannot compile regexes, they can
300 deserialize pre-compiled regexes.
301 * Since this module builds DFAs ahead of time, it will generally out-perform
302 the `regex` crate on equivalent tasks. The performance difference is likely
303 not large. However, because of a complex set of optimizations in the regex
304 crate (like literal optimizations), an accurate performance comparison may be
305 difficult to do.
306 * Sparse DFAs provide a way to build a DFA ahead of time that sacrifices search
307 performance a small amount, but uses much less storage space. Potentially even
308 less than what the regex crate uses.
309 * This module exposes DFAs directly, such as [`dense::DFA`] and
310 [`sparse::DFA`], which enables one to do less work in some cases. For example,
311 if you only need the end of a match and not the start of a match, then you can
312 use a DFA directly without building a `Regex`, which always requires a second
313 DFA to find the start of a match.
314 * This module provides more control over memory usage. Aside from choosing
315 between dense and sparse DFAs, one can also choose a smaller state identifier
316 representation to use less space. Also, one can enable DFA minimization
317 via [`dense::Config::minimize`], but it can increase compilation times
318 dramatically.
319 */
320
321 #[cfg(feature = "dfa-search")]
322 pub use crate::dfa::{
323 automaton::{Automaton, OverlappingState, StartError},
324 start::StartKind,
325 };
326
327 /// This is an alias for a state ID of zero. It has special significance
328 /// because it always corresponds to the first state in a DFA, and the first
329 /// state in a DFA is always "dead." That is, the dead state always has all
330 /// of its transitions set to itself. Moreover, the dead state is used as a
331 /// sentinel for various things. e.g., In search, reaching a dead state means
332 /// that the search must stop.
333 const DEAD: crate::util::primitives::StateID =
334 crate::util::primitives::StateID::ZERO;
335
336 #[cfg(feature = "dfa-search")]
337 pub mod dense;
338 #[cfg(feature = "dfa-onepass")]
339 pub mod onepass;
340 #[cfg(feature = "dfa-search")]
341 pub mod regex;
342 #[cfg(feature = "dfa-search")]
343 pub mod sparse;
344
345 #[cfg(feature = "dfa-search")]
346 pub(crate) mod accel;
347 #[cfg(feature = "dfa-search")]
348 mod automaton;
349 #[cfg(feature = "dfa-build")]
350 mod determinize;
351 #[cfg(feature = "dfa-build")]
352 mod minimize;
353 #[cfg(any(feature = "dfa-build", feature = "dfa-onepass"))]
354 mod remapper;
355 #[cfg(feature = "dfa-search")]
356 mod search;
357 #[cfg(feature = "dfa-search")]
358 mod special;
359 #[cfg(feature = "dfa-search")]
360 mod start;