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