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