regex_automata/dfa/
dense.rs

1/*!
2Types and routines specific to dense DFAs.
3
4This module is the home of [`dense::DFA`](DFA).
5
6This module also contains a [`dense::Builder`](Builder) and a
7[`dense::Config`](Config) for building and configuring a dense DFA.
8*/
9
10#[cfg(feature = "dfa-build")]
11use core::cmp;
12use core::{fmt, iter, mem::size_of, slice};
13
14#[cfg(feature = "dfa-build")]
15use alloc::{
16    collections::{BTreeMap, BTreeSet},
17    vec,
18    vec::Vec,
19};
20
21#[cfg(feature = "dfa-build")]
22use crate::{
23    dfa::{
24        accel::Accel, determinize, minimize::Minimizer, remapper::Remapper,
25        sparse,
26    },
27    nfa::thompson,
28    util::{look::LookMatcher, search::MatchKind},
29};
30use crate::{
31    dfa::{
32        accel::Accels,
33        automaton::{fmt_state_indicator, Automaton, StartError},
34        special::Special,
35        start::StartKind,
36        DEAD,
37    },
38    util::{
39        alphabet::{self, ByteClasses, ByteSet},
40        int::{Pointer, Usize},
41        prefilter::Prefilter,
42        primitives::{PatternID, StateID},
43        search::Anchored,
44        start::{self, Start, StartByteMap},
45        wire::{self, DeserializeError, Endian, SerializeError},
46    },
47};
48
49/// The label that is pre-pended to a serialized DFA.
50const LABEL: &str = "rust-regex-automata-dfa-dense";
51
52/// The format version of dense regexes. This version gets incremented when a
53/// change occurs. A change may not necessarily be a breaking change, but the
54/// version does permit good error messages in the case where a breaking change
55/// is made.
56const VERSION: u32 = 2;
57
58/// The configuration used for compiling a dense DFA.
59///
60/// As a convenience, [`DFA::config`] is an alias for [`Config::new`]. The
61/// advantage of the former is that it often lets you avoid importing the
62/// `Config` type directly.
63///
64/// A dense DFA configuration is a simple data object that is typically used
65/// with [`dense::Builder::configure`](self::Builder::configure).
66///
67/// The default configuration guarantees that a search will never return
68/// a "quit" error, although it is possible for a search to fail if
69/// [`Config::starts_for_each_pattern`] wasn't enabled (which it is
70/// not by default) and an [`Anchored::Pattern`] mode is requested via
71/// [`Input`](crate::Input).
72#[cfg(feature = "dfa-build")]
73#[derive(Clone, Debug, Default)]
74pub struct Config {
75    // As with other configuration types in this crate, we put all our knobs
76    // in options so that we can distinguish between "default" and "not set."
77    // This makes it possible to easily combine multiple configurations
78    // without default values overwriting explicitly specified values. See the
79    // 'overwrite' method.
80    //
81    // For docs on the fields below, see the corresponding method setters.
82    accelerate: Option<bool>,
83    pre: Option<Option<Prefilter>>,
84    minimize: Option<bool>,
85    match_kind: Option<MatchKind>,
86    start_kind: Option<StartKind>,
87    starts_for_each_pattern: Option<bool>,
88    byte_classes: Option<bool>,
89    unicode_word_boundary: Option<bool>,
90    quitset: Option<ByteSet>,
91    specialize_start_states: Option<bool>,
92    dfa_size_limit: Option<Option<usize>>,
93    determinize_size_limit: Option<Option<usize>>,
94}
95
96#[cfg(feature = "dfa-build")]
97impl Config {
98    /// Return a new default dense DFA compiler configuration.
99    pub fn new() -> Config {
100        Config::default()
101    }
102
103    /// Enable state acceleration.
104    ///
105    /// When enabled, DFA construction will analyze each state to determine
106    /// whether it is eligible for simple acceleration. Acceleration typically
107    /// occurs when most of a state's transitions loop back to itself, leaving
108    /// only a select few bytes that will exit the state. When this occurs,
109    /// other routines like `memchr` can be used to look for those bytes which
110    /// may be much faster than traversing the DFA.
111    ///
112    /// Callers may elect to disable this if consistent performance is more
113    /// desirable than variable performance. Namely, acceleration can sometimes
114    /// make searching slower than it otherwise would be if the transitions
115    /// that leave accelerated states are traversed frequently.
116    ///
117    /// See [`Automaton::accelerator`] for an example.
118    ///
119    /// This is enabled by default.
120    pub fn accelerate(mut self, yes: bool) -> Config {
121        self.accelerate = Some(yes);
122        self
123    }
124
125    /// Set a prefilter to be used whenever a start state is entered.
126    ///
127    /// A [`Prefilter`] in this context is meant to accelerate searches by
128    /// looking for literal prefixes that every match for the corresponding
129    /// pattern (or patterns) must start with. Once a prefilter produces a
130    /// match, the underlying search routine continues on to try and confirm
131    /// the match.
132    ///
133    /// Be warned that setting a prefilter does not guarantee that the search
134    /// will be faster. While it's usually a good bet, if the prefilter
135    /// produces a lot of false positive candidates (i.e., positions matched
136    /// by the prefilter but not by the regex), then the overall result can
137    /// be slower than if you had just executed the regex engine without any
138    /// prefilters.
139    ///
140    /// Note that unless [`Config::specialize_start_states`] has been
141    /// explicitly set, then setting this will also enable (when `pre` is
142    /// `Some`) or disable (when `pre` is `None`) start state specialization.
143    /// This occurs because without start state specialization, a prefilter
144    /// is likely to be less effective. And without a prefilter, start state
145    /// specialization is usually pointless.
146    ///
147    /// **WARNING:** Note that prefilters are not preserved as part of
148    /// serialization. Serializing a DFA will drop its prefilter.
149    ///
150    /// By default no prefilter is set.
151    ///
152    /// # Example
153    ///
154    /// ```
155    /// use regex_automata::{
156    ///     dfa::{dense::DFA, Automaton},
157    ///     util::prefilter::Prefilter,
158    ///     Input, HalfMatch, MatchKind,
159    /// };
160    ///
161    /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["foo", "bar"]);
162    /// let re = DFA::builder()
163    ///     .configure(DFA::config().prefilter(pre))
164    ///     .build(r"(foo|bar)[a-z]+")?;
165    /// let input = Input::new("foo1 barfox bar");
166    /// assert_eq!(
167    ///     Some(HalfMatch::must(0, 11)),
168    ///     re.try_search_fwd(&input)?,
169    /// );
170    ///
171    /// # Ok::<(), Box<dyn std::error::Error>>(())
172    /// ```
173    ///
174    /// Be warned though that an incorrect prefilter can lead to incorrect
175    /// results!
176    ///
177    /// ```
178    /// use regex_automata::{
179    ///     dfa::{dense::DFA, Automaton},
180    ///     util::prefilter::Prefilter,
181    ///     Input, HalfMatch, MatchKind,
182    /// };
183    ///
184    /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["foo", "car"]);
185    /// let re = DFA::builder()
186    ///     .configure(DFA::config().prefilter(pre))
187    ///     .build(r"(foo|bar)[a-z]+")?;
188    /// let input = Input::new("foo1 barfox bar");
189    /// assert_eq!(
190    ///     // No match reported even though there clearly is one!
191    ///     None,
192    ///     re.try_search_fwd(&input)?,
193    /// );
194    ///
195    /// # Ok::<(), Box<dyn std::error::Error>>(())
196    /// ```
197    pub fn prefilter(mut self, pre: Option<Prefilter>) -> Config {
198        self.pre = Some(pre);
199        if self.specialize_start_states.is_none() {
200            self.specialize_start_states =
201                Some(self.get_prefilter().is_some());
202        }
203        self
204    }
205
206    /// Minimize the DFA.
207    ///
208    /// When enabled, the DFA built will be minimized such that it is as small
209    /// as possible.
210    ///
211    /// Whether one enables minimization or not depends on the types of costs
212    /// you're willing to pay and how much you care about its benefits. In
213    /// particular, minimization has worst case `O(n*k*logn)` time and `O(k*n)`
214    /// space, where `n` is the number of DFA states and `k` is the alphabet
215    /// size. In practice, minimization can be quite costly in terms of both
216    /// space and time, so it should only be done if you're willing to wait
217    /// longer to produce a DFA. In general, you might want a minimal DFA in
218    /// the following circumstances:
219    ///
220    /// 1. You would like to optimize for the size of the automaton. This can
221    ///    manifest in one of two ways. Firstly, if you're converting the
222    ///    DFA into Rust code (or a table embedded in the code), then a minimal
223    ///    DFA will translate into a corresponding reduction in code  size, and
224    ///    thus, also the final compiled binary size. Secondly, if you are
225    ///    building many DFAs and putting them on the heap, you'll be able to
226    ///    fit more if they are smaller. Note though that building a minimal
227    ///    DFA itself requires additional space; you only realize the space
228    ///    savings once the minimal DFA is constructed (at which point, the
229    ///    space used for minimization is freed).
230    /// 2. You've observed that a smaller DFA results in faster match
231    ///    performance. Naively, this isn't guaranteed since there is no
232    ///    inherent difference between matching with a bigger-than-minimal
233    ///    DFA and a minimal DFA. However, a smaller DFA may make use of your
234    ///    CPU's cache more efficiently.
235    /// 3. You are trying to establish an equivalence between regular
236    ///    languages. The standard method for this is to build a minimal DFA
237    ///    for each language and then compare them. If the DFAs are equivalent
238    ///    (up to state renaming), then the languages are equivalent.
239    ///
240    /// Typically, minimization only makes sense as an offline process. That
241    /// is, one might minimize a DFA before serializing it to persistent
242    /// storage. In practical terms, minimization can take around an order of
243    /// magnitude more time than compiling the initial DFA via determinization.
244    ///
245    /// This option is disabled by default.
246    pub fn minimize(mut self, yes: bool) -> Config {
247        self.minimize = Some(yes);
248        self
249    }
250
251    /// Set the desired match semantics.
252    ///
253    /// The default is [`MatchKind::LeftmostFirst`], which corresponds to the
254    /// match semantics of Perl-like regex engines. That is, when multiple
255    /// patterns would match at the same leftmost position, the pattern that
256    /// appears first in the concrete syntax is chosen.
257    ///
258    /// Currently, the only other kind of match semantics supported is
259    /// [`MatchKind::All`]. This corresponds to classical DFA construction
260    /// where all possible matches are added to the DFA.
261    ///
262    /// Typically, `All` is used when one wants to execute an overlapping
263    /// search and `LeftmostFirst` otherwise. In particular, it rarely makes
264    /// sense to use `All` with the various "leftmost" find routines, since the
265    /// leftmost routines depend on the `LeftmostFirst` automata construction
266    /// strategy. Specifically, `LeftmostFirst` adds dead states to the DFA
267    /// as a way to terminate the search and report a match. `LeftmostFirst`
268    /// also supports non-greedy matches using this strategy where as `All`
269    /// does not.
270    ///
271    /// # Example: overlapping search
272    ///
273    /// This example shows the typical use of `MatchKind::All`, which is to
274    /// report overlapping matches.
275    ///
276    /// ```
277    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
278    /// use regex_automata::{
279    ///     dfa::{Automaton, OverlappingState, dense},
280    ///     HalfMatch, Input, MatchKind,
281    /// };
282    ///
283    /// let dfa = dense::Builder::new()
284    ///     .configure(dense::Config::new().match_kind(MatchKind::All))
285    ///     .build_many(&[r"\w+$", r"\S+$"])?;
286    /// let input = Input::new("@foo");
287    /// let mut state = OverlappingState::start();
288    ///
289    /// let expected = Some(HalfMatch::must(1, 4));
290    /// dfa.try_search_overlapping_fwd(&input, &mut state)?;
291    /// assert_eq!(expected, state.get_match());
292    ///
293    /// // The first pattern also matches at the same position, so re-running
294    /// // the search will yield another match. Notice also that the first
295    /// // pattern is returned after the second. This is because the second
296    /// // pattern begins its match before the first, is therefore an earlier
297    /// // match and is thus reported first.
298    /// let expected = Some(HalfMatch::must(0, 4));
299    /// dfa.try_search_overlapping_fwd(&input, &mut state)?;
300    /// assert_eq!(expected, state.get_match());
301    ///
302    /// # Ok::<(), Box<dyn std::error::Error>>(())
303    /// ```
304    ///
305    /// # Example: reverse automaton to find start of match
306    ///
307    /// Another example for using `MatchKind::All` is for constructing a
308    /// reverse automaton to find the start of a match. `All` semantics are
309    /// used for this in order to find the longest possible match, which
310    /// corresponds to the leftmost starting position.
311    ///
312    /// Note that if you need the starting position then
313    /// [`dfa::regex::Regex`](crate::dfa::regex::Regex) will handle this for
314    /// you, so it's usually not necessary to do this yourself.
315    ///
316    /// ```
317    /// use regex_automata::{
318    ///     dfa::{dense, Automaton, StartKind},
319    ///     nfa::thompson::NFA,
320    ///     Anchored, HalfMatch, Input, MatchKind,
321    /// };
322    ///
323    /// let haystack = "123foobar456".as_bytes();
324    /// let pattern = r"[a-z]+r";
325    ///
326    /// let dfa_fwd = dense::DFA::new(pattern)?;
327    /// let dfa_rev = dense::Builder::new()
328    ///     .thompson(NFA::config().reverse(true))
329    ///     .configure(dense::Config::new()
330    ///         // This isn't strictly necessary since both anchored and
331    ///         // unanchored searches are supported by default. But since
332    ///         // finding the start-of-match only requires anchored searches,
333    ///         // we can get rid of the unanchored configuration and possibly
334    ///         // slim down our DFA considerably.
335    ///         .start_kind(StartKind::Anchored)
336    ///         .match_kind(MatchKind::All)
337    ///     )
338    ///     .build(pattern)?;
339    /// let expected_fwd = HalfMatch::must(0, 9);
340    /// let expected_rev = HalfMatch::must(0, 3);
341    /// let got_fwd = dfa_fwd.try_search_fwd(&Input::new(haystack))?.unwrap();
342    /// // Here we don't specify the pattern to search for since there's only
343    /// // one pattern and we're doing a leftmost search. But if this were an
344    /// // overlapping search, you'd need to specify the pattern that matched
345    /// // in the forward direction. (Otherwise, you might wind up finding the
346    /// // starting position of a match of some other pattern.) That in turn
347    /// // requires building the reverse automaton with starts_for_each_pattern
348    /// // enabled. Indeed, this is what Regex does internally.
349    /// let input = Input::new(haystack)
350    ///     .range(..got_fwd.offset())
351    ///     .anchored(Anchored::Yes);
352    /// let got_rev = dfa_rev.try_search_rev(&input)?.unwrap();
353    /// assert_eq!(expected_fwd, got_fwd);
354    /// assert_eq!(expected_rev, got_rev);
355    ///
356    /// # Ok::<(), Box<dyn std::error::Error>>(())
357    /// ```
358    pub fn match_kind(mut self, kind: MatchKind) -> Config {
359        self.match_kind = Some(kind);
360        self
361    }
362
363    /// The type of starting state configuration to use for a DFA.
364    ///
365    /// By default, the starting state configuration is [`StartKind::Both`].
366    ///
367    /// # Example
368    ///
369    /// ```
370    /// use regex_automata::{
371    ///     dfa::{dense::DFA, Automaton, StartKind},
372    ///     Anchored, HalfMatch, Input,
373    /// };
374    ///
375    /// let haystack = "quux foo123";
376    /// let expected = HalfMatch::must(0, 11);
377    ///
378    /// // By default, DFAs support both anchored and unanchored searches.
379    /// let dfa = DFA::new(r"[0-9]+")?;
380    /// let input = Input::new(haystack);
381    /// assert_eq!(Some(expected), dfa.try_search_fwd(&input)?);
382    ///
383    /// // But if we only need anchored searches, then we can build a DFA
384    /// // that only supports anchored searches. This leads to a smaller DFA
385    /// // (potentially significantly smaller in some cases), but a DFA that
386    /// // will panic if you try to use it with an unanchored search.
387    /// let dfa = DFA::builder()
388    ///     .configure(DFA::config().start_kind(StartKind::Anchored))
389    ///     .build(r"[0-9]+")?;
390    /// let input = Input::new(haystack)
391    ///     .range(8..)
392    ///     .anchored(Anchored::Yes);
393    /// assert_eq!(Some(expected), dfa.try_search_fwd(&input)?);
394    ///
395    /// # Ok::<(), Box<dyn std::error::Error>>(())
396    /// ```
397    pub fn start_kind(mut self, kind: StartKind) -> Config {
398        self.start_kind = Some(kind);
399        self
400    }
401
402    /// Whether to compile a separate start state for each pattern in the
403    /// automaton.
404    ///
405    /// When enabled, a separate **anchored** start state is added for each
406    /// pattern in the DFA. When this start state is used, then the DFA will
407    /// only search for matches for the pattern specified, even if there are
408    /// other patterns in the DFA.
409    ///
410    /// The main downside of this option is that it can potentially increase
411    /// the size of the DFA and/or increase the time it takes to build the DFA.
412    ///
413    /// There are a few reasons one might want to enable this (it's disabled
414    /// by default):
415    ///
416    /// 1. When looking for the start of an overlapping match (using a
417    /// reverse DFA), doing it correctly requires starting the reverse search
418    /// using the starting state of the pattern that matched in the forward
419    /// direction. Indeed, when building a [`Regex`](crate::dfa::regex::Regex),
420    /// it will automatically enable this option when building the reverse DFA
421    /// internally.
422    /// 2. When you want to use a DFA with multiple patterns to both search
423    /// for matches of any pattern or to search for anchored matches of one
424    /// particular pattern while using the same DFA. (Otherwise, you would need
425    /// to compile a new DFA for each pattern.)
426    /// 3. Since the start states added for each pattern are anchored, if you
427    /// compile an unanchored DFA with one pattern while also enabling this
428    /// option, then you can use the same DFA to perform anchored or unanchored
429    /// searches. The latter you get with the standard search APIs. The former
430    /// you get from the various `_at` search methods that allow you specify a
431    /// pattern ID to search for.
432    ///
433    /// By default this is disabled.
434    ///
435    /// # Example
436    ///
437    /// This example shows how to use this option to permit the same DFA to
438    /// run both anchored and unanchored searches for a single pattern.
439    ///
440    /// ```
441    /// use regex_automata::{
442    ///     dfa::{dense, Automaton},
443    ///     Anchored, HalfMatch, PatternID, Input,
444    /// };
445    ///
446    /// let dfa = dense::Builder::new()
447    ///     .configure(dense::Config::new().starts_for_each_pattern(true))
448    ///     .build(r"foo[0-9]+")?;
449    /// let haystack = "quux foo123";
450    ///
451    /// // Here's a normal unanchored search. Notice that we use 'None' for the
452    /// // pattern ID. Since the DFA was built as an unanchored machine, it
453    /// // use its default unanchored starting state.
454    /// let expected = HalfMatch::must(0, 11);
455    /// let input = Input::new(haystack);
456    /// assert_eq!(Some(expected), dfa.try_search_fwd(&input)?);
457    /// // But now if we explicitly specify the pattern to search ('0' being
458    /// // the only pattern in the DFA), then it will use the starting state
459    /// // for that specific pattern which is always anchored. Since the
460    /// // pattern doesn't have a match at the beginning of the haystack, we
461    /// // find nothing.
462    /// let input = Input::new(haystack)
463    ///     .anchored(Anchored::Pattern(PatternID::must(0)));
464    /// assert_eq!(None, dfa.try_search_fwd(&input)?);
465    /// // And finally, an anchored search is not the same as putting a '^' at
466    /// // beginning of the pattern. An anchored search can only match at the
467    /// // beginning of the *search*, which we can change:
468    /// let input = Input::new(haystack)
469    ///     .anchored(Anchored::Pattern(PatternID::must(0)))
470    ///     .range(5..);
471    /// assert_eq!(Some(expected), dfa.try_search_fwd(&input)?);
472    ///
473    /// # Ok::<(), Box<dyn std::error::Error>>(())
474    /// ```
475    pub fn starts_for_each_pattern(mut self, yes: bool) -> Config {
476        self.starts_for_each_pattern = Some(yes);
477        self
478    }
479
480    /// Whether to attempt to shrink the size of the DFA's alphabet or not.
481    ///
482    /// This option is enabled by default and should never be disabled unless
483    /// one is debugging a generated DFA.
484    ///
485    /// When enabled, the DFA will use a map from all possible bytes to their
486    /// corresponding equivalence class. Each equivalence class represents a
487    /// set of bytes that does not discriminate between a match and a non-match
488    /// in the DFA. For example, the pattern `[ab]+` has at least two
489    /// equivalence classes: a set containing `a` and `b` and a set containing
490    /// every byte except for `a` and `b`. `a` and `b` are in the same
491    /// equivalence class because they never discriminate between a match and a
492    /// non-match.
493    ///
494    /// The advantage of this map is that the size of the transition table
495    /// can be reduced drastically from `#states * 256 * sizeof(StateID)` to
496    /// `#states * k * sizeof(StateID)` where `k` is the number of equivalence
497    /// classes (rounded up to the nearest power of 2). As a result, total
498    /// space usage can decrease substantially. Moreover, since a smaller
499    /// alphabet is used, DFA compilation becomes faster as well.
500    ///
501    /// **WARNING:** This is only useful for debugging DFAs. Disabling this
502    /// does not yield any speed advantages. Namely, even when this is
503    /// disabled, a byte class map is still used while searching. The only
504    /// difference is that every byte will be forced into its own distinct
505    /// equivalence class. This is useful for debugging the actual generated
506    /// transitions because it lets one see the transitions defined on actual
507    /// bytes instead of the equivalence classes.
508    pub fn byte_classes(mut self, yes: bool) -> Config {
509        self.byte_classes = Some(yes);
510        self
511    }
512
513    /// Heuristically enable Unicode word boundaries.
514    ///
515    /// When set, this will attempt to implement Unicode word boundaries as if
516    /// they were ASCII word boundaries. This only works when the search input
517    /// is ASCII only. If a non-ASCII byte is observed while searching, then a
518    /// [`MatchError::quit`](crate::MatchError::quit) error is returned.
519    ///
520    /// A possible alternative to enabling this option is to simply use an
521    /// ASCII word boundary, e.g., via `(?-u:\b)`. The main reason to use this
522    /// option is if you absolutely need Unicode support. This option lets one
523    /// use a fast search implementation (a DFA) for some potentially very
524    /// common cases, while providing the option to fall back to some other
525    /// regex engine to handle the general case when an error is returned.
526    ///
527    /// If the pattern provided has no Unicode word boundary in it, then this
528    /// option has no effect. (That is, quitting on a non-ASCII byte only
529    /// occurs when this option is enabled _and_ a Unicode word boundary is
530    /// present in the pattern.)
531    ///
532    /// This is almost equivalent to setting all non-ASCII bytes to be quit
533    /// bytes. The only difference is that this will cause non-ASCII bytes to
534    /// be quit bytes _only_ when a Unicode word boundary is present in the
535    /// pattern.
536    ///
537    /// When enabling this option, callers _must_ be prepared to handle
538    /// a [`MatchError`](crate::MatchError) error during search.
539    /// When using a [`Regex`](crate::dfa::regex::Regex), this corresponds
540    /// to using the `try_` suite of methods. Alternatively, if
541    /// callers can guarantee that their input is ASCII only, then a
542    /// [`MatchError::quit`](crate::MatchError::quit) error will never be
543    /// returned while searching.
544    ///
545    /// This is disabled by default.
546    ///
547    /// # Example
548    ///
549    /// This example shows how to heuristically enable Unicode word boundaries
550    /// in a pattern. It also shows what happens when a search comes across a
551    /// non-ASCII byte.
552    ///
553    /// ```
554    /// use regex_automata::{
555    ///     dfa::{Automaton, dense},
556    ///     HalfMatch, Input, MatchError,
557    /// };
558    ///
559    /// let dfa = dense::Builder::new()
560    ///     .configure(dense::Config::new().unicode_word_boundary(true))
561    ///     .build(r"\b[0-9]+\b")?;
562    ///
563    /// // The match occurs before the search ever observes the snowman
564    /// // character, so no error occurs.
565    /// let haystack = "foo 123  ☃".as_bytes();
566    /// let expected = Some(HalfMatch::must(0, 7));
567    /// let got = dfa.try_search_fwd(&Input::new(haystack))?;
568    /// assert_eq!(expected, got);
569    ///
570    /// // Notice that this search fails, even though the snowman character
571    /// // occurs after the ending match offset. This is because search
572    /// // routines read one byte past the end of the search to account for
573    /// // look-around, and indeed, this is required here to determine whether
574    /// // the trailing \b matches.
575    /// let haystack = "foo 123 ☃".as_bytes();
576    /// let expected = MatchError::quit(0xE2, 8);
577    /// let got = dfa.try_search_fwd(&Input::new(haystack));
578    /// assert_eq!(Err(expected), got);
579    ///
580    /// // Another example is executing a search where the span of the haystack
581    /// // we specify is all ASCII, but there is non-ASCII just before it. This
582    /// // correctly also reports an error.
583    /// let input = Input::new("β123").range(2..);
584    /// let expected = MatchError::quit(0xB2, 1);
585    /// let got = dfa.try_search_fwd(&input);
586    /// assert_eq!(Err(expected), got);
587    ///
588    /// // And similarly for the trailing word boundary.
589    /// let input = Input::new("123β").range(..3);
590    /// let expected = MatchError::quit(0xCE, 3);
591    /// let got = dfa.try_search_fwd(&input);
592    /// assert_eq!(Err(expected), got);
593    ///
594    /// # Ok::<(), Box<dyn std::error::Error>>(())
595    /// ```
596    pub fn unicode_word_boundary(mut self, yes: bool) -> Config {
597        // We have a separate option for this instead of just setting the
598        // appropriate quit bytes here because we don't want to set quit bytes
599        // for every regex. We only want to set them when the regex contains a
600        // Unicode word boundary.
601        self.unicode_word_boundary = Some(yes);
602        self
603    }
604
605    /// Add a "quit" byte to the DFA.
606    ///
607    /// When a quit byte is seen during search time, then search will return
608    /// a [`MatchError::quit`](crate::MatchError::quit) error indicating the
609    /// offset at which the search stopped.
610    ///
611    /// A quit byte will always overrule any other aspects of a regex. For
612    /// example, if the `x` byte is added as a quit byte and the regex `\w` is
613    /// used, then observing `x` will cause the search to quit immediately
614    /// despite the fact that `x` is in the `\w` class.
615    ///
616    /// This mechanism is primarily useful for heuristically enabling certain
617    /// features like Unicode word boundaries in a DFA. Namely, if the input
618    /// to search is ASCII, then a Unicode word boundary can be implemented
619    /// via an ASCII word boundary with no change in semantics. Thus, a DFA
620    /// can attempt to match a Unicode word boundary but give up as soon as it
621    /// observes a non-ASCII byte. Indeed, if callers set all non-ASCII bytes
622    /// to be quit bytes, then Unicode word boundaries will be permitted when
623    /// building DFAs. Of course, callers should enable
624    /// [`Config::unicode_word_boundary`] if they want this behavior instead.
625    /// (The advantage being that non-ASCII quit bytes will only be added if a
626    /// Unicode word boundary is in the pattern.)
627    ///
628    /// When enabling this option, callers _must_ be prepared to handle a
629    /// [`MatchError`](crate::MatchError) error during search. When using a
630    /// [`Regex`](crate::dfa::regex::Regex), this corresponds to using the
631    /// `try_` suite of methods.
632    ///
633    /// By default, there are no quit bytes set.
634    ///
635    /// # Panics
636    ///
637    /// This panics if heuristic Unicode word boundaries are enabled and any
638    /// non-ASCII byte is removed from the set of quit bytes. Namely, enabling
639    /// Unicode word boundaries requires setting every non-ASCII byte to a quit
640    /// byte. So if the caller attempts to undo any of that, then this will
641    /// panic.
642    ///
643    /// # Example
644    ///
645    /// This example shows how to cause a search to terminate if it sees a
646    /// `\n` byte. This could be useful if, for example, you wanted to prevent
647    /// a user supplied pattern from matching across a line boundary.
648    ///
649    /// ```
650    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
651    /// use regex_automata::{dfa::{Automaton, dense}, Input, MatchError};
652    ///
653    /// let dfa = dense::Builder::new()
654    ///     .configure(dense::Config::new().quit(b'\n', true))
655    ///     .build(r"foo\p{any}+bar")?;
656    ///
657    /// let haystack = "foo\nbar".as_bytes();
658    /// // Normally this would produce a match, since \p{any} contains '\n'.
659    /// // But since we instructed the automaton to enter a quit state if a
660    /// // '\n' is observed, this produces a match error instead.
661    /// let expected = MatchError::quit(b'\n', 3);
662    /// let got = dfa.try_search_fwd(&Input::new(haystack)).unwrap_err();
663    /// assert_eq!(expected, got);
664    ///
665    /// # Ok::<(), Box<dyn std::error::Error>>(())
666    /// ```
667    pub fn quit(mut self, byte: u8, yes: bool) -> Config {
668        if self.get_unicode_word_boundary() && !byte.is_ascii() && !yes {
669            panic!(
670                "cannot set non-ASCII byte to be non-quit when \
671                 Unicode word boundaries are enabled"
672            );
673        }
674        if self.quitset.is_none() {
675            self.quitset = Some(ByteSet::empty());
676        }
677        if yes {
678            self.quitset.as_mut().unwrap().add(byte);
679        } else {
680            self.quitset.as_mut().unwrap().remove(byte);
681        }
682        self
683    }
684
685    /// Enable specializing start states in the DFA.
686    ///
687    /// When start states are specialized, an implementor of a search routine
688    /// using a lazy DFA can tell when the search has entered a starting state.
689    /// When start states aren't specialized, then it is impossible to know
690    /// whether the search has entered a start state.
691    ///
692    /// Ideally, this option wouldn't need to exist and we could always
693    /// specialize start states. The problem is that start states can be quite
694    /// active. This in turn means that an efficient search routine is likely
695    /// to ping-pong between a heavily optimized hot loop that handles most
696    /// states and to a less optimized specialized handling of start states.
697    /// This causes branches to get heavily mispredicted and overall can
698    /// materially decrease throughput. Therefore, specializing start states
699    /// should only be enabled when it is needed.
700    ///
701    /// Knowing whether a search is in a start state is typically useful when a
702    /// prefilter is active for the search. A prefilter is typically only run
703    /// when in a start state and a prefilter can greatly accelerate a search.
704    /// Therefore, the possible cost of specializing start states is worth it
705    /// in this case. Otherwise, if you have no prefilter, there is likely no
706    /// reason to specialize start states.
707    ///
708    /// This is disabled by default, but note that it is automatically
709    /// enabled (or disabled) if [`Config::prefilter`] is set. Namely, unless
710    /// `specialize_start_states` has already been set, [`Config::prefilter`]
711    /// will automatically enable or disable it based on whether a prefilter
712    /// is present or not, respectively. This is done because a prefilter's
713    /// effectiveness is rooted in being executed whenever the DFA is in a
714    /// start state, and that's only possible to do when they are specialized.
715    ///
716    /// Note that it is plausibly reasonable to _disable_ this option
717    /// explicitly while _enabling_ a prefilter. In that case, a prefilter
718    /// will still be run at the beginning of a search, but never again. This
719    /// in theory could strike a good balance if you're in a situation where a
720    /// prefilter is likely to produce many false positive candidates.
721    ///
722    /// # Example
723    ///
724    /// This example shows how to enable start state specialization and then
725    /// shows how to check whether a state is a start state or not.
726    ///
727    /// ```
728    /// use regex_automata::{dfa::{Automaton, dense::DFA}, Input};
729    ///
730    /// let dfa = DFA::builder()
731    ///     .configure(DFA::config().specialize_start_states(true))
732    ///     .build(r"[a-z]+")?;
733    ///
734    /// let haystack = "123 foobar 4567".as_bytes();
735    /// let sid = dfa.start_state_forward(&Input::new(haystack))?;
736    /// // The ID returned by 'start_state_forward' will always be tagged as
737    /// // a start state when start state specialization is enabled.
738    /// assert!(dfa.is_special_state(sid));
739    /// assert!(dfa.is_start_state(sid));
740    ///
741    /// # Ok::<(), Box<dyn std::error::Error>>(())
742    /// ```
743    ///
744    /// Compare the above with the default DFA configuration where start states
745    /// are _not_ specialized. In this case, the start state is not tagged at
746    /// all:
747    ///
748    /// ```
749    /// use regex_automata::{dfa::{Automaton, dense::DFA}, Input};
750    ///
751    /// let dfa = DFA::new(r"[a-z]+")?;
752    ///
753    /// let haystack = "123 foobar 4567";
754    /// let sid = dfa.start_state_forward(&Input::new(haystack))?;
755    /// // Start states are not special in the default configuration!
756    /// assert!(!dfa.is_special_state(sid));
757    /// assert!(!dfa.is_start_state(sid));
758    ///
759    /// # Ok::<(), Box<dyn std::error::Error>>(())
760    /// ```
761    pub fn specialize_start_states(mut self, yes: bool) -> Config {
762        self.specialize_start_states = Some(yes);
763        self
764    }
765
766    /// Set a size limit on the total heap used by a DFA.
767    ///
768    /// This size limit is expressed in bytes and is applied during
769    /// determinization of an NFA into a DFA. If the DFA's heap usage, and only
770    /// the DFA, exceeds this configured limit, then determinization is stopped
771    /// and an error is returned.
772    ///
773    /// This limit does not apply to auxiliary storage used during
774    /// determinization that isn't part of the generated DFA.
775    ///
776    /// This limit is only applied during determinization. Currently, there is
777    /// no way to post-pone this check to after minimization if minimization
778    /// was enabled.
779    ///
780    /// The total limit on heap used during determinization is the sum of the
781    /// DFA and determinization size limits.
782    ///
783    /// The default is no limit.
784    ///
785    /// # Example
786    ///
787    /// This example shows a DFA that fails to build because of a configured
788    /// size limit. This particular example also serves as a cautionary tale
789    /// demonstrating just how big DFAs with large Unicode character classes
790    /// can get.
791    ///
792    /// ```
793    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
794    /// use regex_automata::{dfa::{dense, Automaton}, Input};
795    ///
796    /// // 6MB isn't enough!
797    /// dense::Builder::new()
798    ///     .configure(dense::Config::new().dfa_size_limit(Some(6_000_000)))
799    ///     .build(r"\w{20}")
800    ///     .unwrap_err();
801    ///
802    /// // ... but 7MB probably is!
803    /// // (Note that DFA sizes aren't necessarily stable between releases.)
804    /// let dfa = dense::Builder::new()
805    ///     .configure(dense::Config::new().dfa_size_limit(Some(7_000_000)))
806    ///     .build(r"\w{20}")?;
807    /// let haystack = "A".repeat(20).into_bytes();
808    /// assert!(dfa.try_search_fwd(&Input::new(&haystack))?.is_some());
809    ///
810    /// # Ok::<(), Box<dyn std::error::Error>>(())
811    /// ```
812    ///
813    /// While one needs a little more than 6MB to represent `\w{20}`, it
814    /// turns out that you only need a little more than 6KB to represent
815    /// `(?-u:\w{20})`. So only use Unicode if you need it!
816    ///
817    /// As with [`Config::determinize_size_limit`], the size of a DFA is
818    /// influenced by other factors, such as what start state configurations
819    /// to support. For example, if you only need unanchored searches and not
820    /// anchored searches, then configuring the DFA to only support unanchored
821    /// searches can reduce its size. By default, DFAs support both unanchored
822    /// and anchored searches.
823    ///
824    /// ```
825    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
826    /// use regex_automata::{dfa::{dense, Automaton, StartKind}, Input};
827    ///
828    /// // 3MB isn't enough!
829    /// dense::Builder::new()
830    ///     .configure(dense::Config::new()
831    ///         .dfa_size_limit(Some(3_000_000))
832    ///         .start_kind(StartKind::Unanchored)
833    ///     )
834    ///     .build(r"\w{20}")
835    ///     .unwrap_err();
836    ///
837    /// // ... but 4MB probably is!
838    /// // (Note that DFA sizes aren't necessarily stable between releases.)
839    /// let dfa = dense::Builder::new()
840    ///     .configure(dense::Config::new()
841    ///         .dfa_size_limit(Some(4_000_000))
842    ///         .start_kind(StartKind::Unanchored)
843    ///     )
844    ///     .build(r"\w{20}")?;
845    /// let haystack = "A".repeat(20).into_bytes();
846    /// assert!(dfa.try_search_fwd(&Input::new(&haystack))?.is_some());
847    ///
848    /// # Ok::<(), Box<dyn std::error::Error>>(())
849    /// ```
850    pub fn dfa_size_limit(mut self, bytes: Option<usize>) -> Config {
851        self.dfa_size_limit = Some(bytes);
852        self
853    }
854
855    /// Set a size limit on the total heap used by determinization.
856    ///
857    /// This size limit is expressed in bytes and is applied during
858    /// determinization of an NFA into a DFA. If the heap used for auxiliary
859    /// storage during determinization (memory that is not in the DFA but
860    /// necessary for building the DFA) exceeds this configured limit, then
861    /// determinization is stopped and an error is returned.
862    ///
863    /// This limit does not apply to heap used by the DFA itself.
864    ///
865    /// The total limit on heap used during determinization is the sum of the
866    /// DFA and determinization size limits.
867    ///
868    /// The default is no limit.
869    ///
870    /// # Example
871    ///
872    /// This example shows a DFA that fails to build because of a
873    /// configured size limit on the amount of heap space used by
874    /// determinization. This particular example complements the example for
875    /// [`Config::dfa_size_limit`] by demonstrating that not only does Unicode
876    /// potentially make DFAs themselves big, but it also results in more
877    /// auxiliary storage during determinization. (Although, auxiliary storage
878    /// is still not as much as the DFA itself.)
879    ///
880    /// ```
881    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
882    /// # if !cfg!(target_pointer_width = "64") { return Ok(()); } // see #1039
883    /// use regex_automata::{dfa::{dense, Automaton}, Input};
884    ///
885    /// // 700KB isn't enough!
886    /// dense::Builder::new()
887    ///     .configure(dense::Config::new()
888    ///         .determinize_size_limit(Some(700_000))
889    ///     )
890    ///     .build(r"\w{20}")
891    ///     .unwrap_err();
892    ///
893    /// // ... but 800KB probably is!
894    /// // (Note that auxiliary storage sizes aren't necessarily stable between
895    /// // releases.)
896    /// let dfa = dense::Builder::new()
897    ///     .configure(dense::Config::new()
898    ///         .determinize_size_limit(Some(800_000))
899    ///     )
900    ///     .build(r"\w{20}")?;
901    /// let haystack = "A".repeat(20).into_bytes();
902    /// assert!(dfa.try_search_fwd(&Input::new(&haystack))?.is_some());
903    ///
904    /// # Ok::<(), Box<dyn std::error::Error>>(())
905    /// ```
906    ///
907    /// Note that some parts of the configuration on a DFA can have a
908    /// big impact on how big the DFA is, and thus, how much memory is
909    /// used. For example, the default setting for [`Config::start_kind`] is
910    /// [`StartKind::Both`]. But if you only need an anchored search, for
911    /// example, then it can be much cheaper to build a DFA that only supports
912    /// anchored searches. (Running an unanchored search with it would panic.)
913    ///
914    /// ```
915    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
916    /// # if !cfg!(target_pointer_width = "64") { return Ok(()); } // see #1039
917    /// use regex_automata::{
918    ///     dfa::{dense, Automaton, StartKind},
919    ///     Anchored, Input,
920    /// };
921    ///
922    /// // 200KB isn't enough!
923    /// dense::Builder::new()
924    ///     .configure(dense::Config::new()
925    ///         .determinize_size_limit(Some(200_000))
926    ///         .start_kind(StartKind::Anchored)
927    ///     )
928    ///     .build(r"\w{20}")
929    ///     .unwrap_err();
930    ///
931    /// // ... but 300KB probably is!
932    /// // (Note that auxiliary storage sizes aren't necessarily stable between
933    /// // releases.)
934    /// let dfa = dense::Builder::new()
935    ///     .configure(dense::Config::new()
936    ///         .determinize_size_limit(Some(300_000))
937    ///         .start_kind(StartKind::Anchored)
938    ///     )
939    ///     .build(r"\w{20}")?;
940    /// let haystack = "A".repeat(20).into_bytes();
941    /// let input = Input::new(&haystack).anchored(Anchored::Yes);
942    /// assert!(dfa.try_search_fwd(&input)?.is_some());
943    ///
944    /// # Ok::<(), Box<dyn std::error::Error>>(())
945    /// ```
946    pub fn determinize_size_limit(mut self, bytes: Option<usize>) -> Config {
947        self.determinize_size_limit = Some(bytes);
948        self
949    }
950
951    /// Returns whether this configuration has enabled simple state
952    /// acceleration.
953    pub fn get_accelerate(&self) -> bool {
954        self.accelerate.unwrap_or(true)
955    }
956
957    /// Returns the prefilter attached to this configuration, if any.
958    pub fn get_prefilter(&self) -> Option<&Prefilter> {
959        self.pre.as_ref().unwrap_or(&None).as_ref()
960    }
961
962    /// Returns whether this configuration has enabled the expensive process
963    /// of minimizing a DFA.
964    pub fn get_minimize(&self) -> bool {
965        self.minimize.unwrap_or(false)
966    }
967
968    /// Returns the match semantics set in this configuration.
969    pub fn get_match_kind(&self) -> MatchKind {
970        self.match_kind.unwrap_or(MatchKind::LeftmostFirst)
971    }
972
973    /// Returns the starting state configuration for a DFA.
974    pub fn get_starts(&self) -> StartKind {
975        self.start_kind.unwrap_or(StartKind::Both)
976    }
977
978    /// Returns whether this configuration has enabled anchored starting states
979    /// for every pattern in the DFA.
980    pub fn get_starts_for_each_pattern(&self) -> bool {
981        self.starts_for_each_pattern.unwrap_or(false)
982    }
983
984    /// Returns whether this configuration has enabled byte classes or not.
985    /// This is typically a debugging oriented option, as disabling it confers
986    /// no speed benefit.
987    pub fn get_byte_classes(&self) -> bool {
988        self.byte_classes.unwrap_or(true)
989    }
990
991    /// Returns whether this configuration has enabled heuristic Unicode word
992    /// boundary support. When enabled, it is possible for a search to return
993    /// an error.
994    pub fn get_unicode_word_boundary(&self) -> bool {
995        self.unicode_word_boundary.unwrap_or(false)
996    }
997
998    /// Returns whether this configuration will instruct the DFA to enter a
999    /// quit state whenever the given byte is seen during a search. When at
1000    /// least one byte has this enabled, it is possible for a search to return
1001    /// an error.
1002    pub fn get_quit(&self, byte: u8) -> bool {
1003        self.quitset.map_or(false, |q| q.contains(byte))
1004    }
1005
1006    /// Returns whether this configuration will instruct the DFA to
1007    /// "specialize" start states. When enabled, the DFA will mark start states
1008    /// as "special" so that search routines using the DFA can detect when
1009    /// it's in a start state and do some kind of optimization (like run a
1010    /// prefilter).
1011    pub fn get_specialize_start_states(&self) -> bool {
1012        self.specialize_start_states.unwrap_or(false)
1013    }
1014
1015    /// Returns the DFA size limit of this configuration if one was set.
1016    /// The size limit is total number of bytes on the heap that a DFA is
1017    /// permitted to use. If the DFA exceeds this limit during construction,
1018    /// then construction is stopped and an error is returned.
1019    pub fn get_dfa_size_limit(&self) -> Option<usize> {
1020        self.dfa_size_limit.unwrap_or(None)
1021    }
1022
1023    /// Returns the determinization size limit of this configuration if one
1024    /// was set. The size limit is total number of bytes on the heap that
1025    /// determinization is permitted to use. If determinization exceeds this
1026    /// limit during construction, then construction is stopped and an error is
1027    /// returned.
1028    ///
1029    /// This is different from the DFA size limit in that this only applies to
1030    /// the auxiliary storage used during determinization. Once determinization
1031    /// is complete, this memory is freed.
1032    ///
1033    /// The limit on the total heap memory used is the sum of the DFA and
1034    /// determinization size limits.
1035    pub fn get_determinize_size_limit(&self) -> Option<usize> {
1036        self.determinize_size_limit.unwrap_or(None)
1037    }
1038
1039    /// Overwrite the default configuration such that the options in `o` are
1040    /// always used. If an option in `o` is not set, then the corresponding
1041    /// option in `self` is used. If it's not set in `self` either, then it
1042    /// remains not set.
1043    pub(crate) fn overwrite(&self, o: Config) -> Config {
1044        Config {
1045            accelerate: o.accelerate.or(self.accelerate),
1046            pre: o.pre.or_else(|| self.pre.clone()),
1047            minimize: o.minimize.or(self.minimize),
1048            match_kind: o.match_kind.or(self.match_kind),
1049            start_kind: o.start_kind.or(self.start_kind),
1050            starts_for_each_pattern: o
1051                .starts_for_each_pattern
1052                .or(self.starts_for_each_pattern),
1053            byte_classes: o.byte_classes.or(self.byte_classes),
1054            unicode_word_boundary: o
1055                .unicode_word_boundary
1056                .or(self.unicode_word_boundary),
1057            quitset: o.quitset.or(self.quitset),
1058            specialize_start_states: o
1059                .specialize_start_states
1060                .or(self.specialize_start_states),
1061            dfa_size_limit: o.dfa_size_limit.or(self.dfa_size_limit),
1062            determinize_size_limit: o
1063                .determinize_size_limit
1064                .or(self.determinize_size_limit),
1065        }
1066    }
1067}
1068
1069/// A builder for constructing a deterministic finite automaton from regular
1070/// expressions.
1071///
1072/// This builder provides two main things:
1073///
1074/// 1. It provides a few different `build` routines for actually constructing
1075/// a DFA from different kinds of inputs. The most convenient is
1076/// [`Builder::build`], which builds a DFA directly from a pattern string. The
1077/// most flexible is [`Builder::build_from_nfa`], which builds a DFA straight
1078/// from an NFA.
1079/// 2. The builder permits configuring a number of things.
1080/// [`Builder::configure`] is used with [`Config`] to configure aspects of
1081/// the DFA and the construction process itself. [`Builder::syntax`] and
1082/// [`Builder::thompson`] permit configuring the regex parser and Thompson NFA
1083/// construction, respectively. The syntax and thompson configurations only
1084/// apply when building from a pattern string.
1085///
1086/// This builder always constructs a *single* DFA. As such, this builder
1087/// can only be used to construct regexes that either detect the presence
1088/// of a match or find the end location of a match. A single DFA cannot
1089/// produce both the start and end of a match. For that information, use a
1090/// [`Regex`](crate::dfa::regex::Regex), which can be similarly configured
1091/// using [`regex::Builder`](crate::dfa::regex::Builder). The main reason to
1092/// use a DFA directly is if the end location of a match is enough for your use
1093/// case. Namely, a `Regex` will construct two DFAs instead of one, since a
1094/// second reverse DFA is needed to find the start of a match.
1095///
1096/// Note that if one wants to build a sparse DFA, you must first build a dense
1097/// DFA and convert that to a sparse DFA. There is no way to build a sparse
1098/// DFA without first building a dense DFA.
1099///
1100/// # Example
1101///
1102/// This example shows how to build a minimized DFA that completely disables
1103/// Unicode. That is:
1104///
1105/// * Things such as `\w`, `.` and `\b` are no longer Unicode-aware. `\w`
1106///   and `\b` are ASCII-only while `.` matches any byte except for `\n`
1107///   (instead of any UTF-8 encoding of a Unicode scalar value except for
1108///   `\n`). Things that are Unicode only, such as `\pL`, are not allowed.
1109/// * The pattern itself is permitted to match invalid UTF-8. For example,
1110///   things like `[^a]` that match any byte except for `a` are permitted.
1111///
1112/// ```
1113/// use regex_automata::{
1114///     dfa::{Automaton, dense},
1115///     util::syntax,
1116///     HalfMatch, Input,
1117/// };
1118///
1119/// let dfa = dense::Builder::new()
1120///     .configure(dense::Config::new().minimize(false))
1121///     .syntax(syntax::Config::new().unicode(false).utf8(false))
1122///     .build(r"foo[^b]ar.*")?;
1123///
1124/// let haystack = b"\xFEfoo\xFFar\xE2\x98\xFF\n";
1125/// let expected = Some(HalfMatch::must(0, 10));
1126/// let got = dfa.try_search_fwd(&Input::new(haystack))?;
1127/// assert_eq!(expected, got);
1128///
1129/// # Ok::<(), Box<dyn std::error::Error>>(())
1130/// ```
1131#[cfg(feature = "dfa-build")]
1132#[derive(Clone, Debug)]
1133pub struct Builder {
1134    config: Config,
1135    #[cfg(feature = "syntax")]
1136    thompson: thompson::Compiler,
1137}
1138
1139#[cfg(feature = "dfa-build")]
1140impl Builder {
1141    /// Create a new dense DFA builder with the default configuration.
1142    pub fn new() -> Builder {
1143        Builder {
1144            config: Config::default(),
1145            #[cfg(feature = "syntax")]
1146            thompson: thompson::Compiler::new(),
1147        }
1148    }
1149
1150    /// Build a DFA from the given pattern.
1151    ///
1152    /// If there was a problem parsing or compiling the pattern, then an error
1153    /// is returned.
1154    #[cfg(feature = "syntax")]
1155    pub fn build(&self, pattern: &str) -> Result<OwnedDFA, BuildError> {
1156        self.build_many(&[pattern])
1157    }
1158
1159    /// Build a DFA from the given patterns.
1160    ///
1161    /// When matches are returned, the pattern ID corresponds to the index of
1162    /// the pattern in the slice given.
1163    #[cfg(feature = "syntax")]
1164    pub fn build_many<P: AsRef<str>>(
1165        &self,
1166        patterns: &[P],
1167    ) -> Result<OwnedDFA, BuildError> {
1168        let nfa = self
1169            .thompson
1170            .clone()
1171            // We can always forcefully disable captures because DFAs do not
1172            // support them.
1173            .configure(
1174                thompson::Config::new()
1175                    .which_captures(thompson::WhichCaptures::None),
1176            )
1177            .build_many(patterns)
1178            .map_err(BuildError::nfa)?;
1179        self.build_from_nfa(&nfa)
1180    }
1181
1182    /// Build a DFA from the given NFA.
1183    ///
1184    /// # Example
1185    ///
1186    /// This example shows how to build a DFA if you already have an NFA in
1187    /// hand.
1188    ///
1189    /// ```
1190    /// use regex_automata::{
1191    ///     dfa::{Automaton, dense},
1192    ///     nfa::thompson::NFA,
1193    ///     HalfMatch, Input,
1194    /// };
1195    ///
1196    /// let haystack = "foo123bar".as_bytes();
1197    ///
1198    /// // This shows how to set non-default options for building an NFA.
1199    /// let nfa = NFA::compiler()
1200    ///     .configure(NFA::config().shrink(true))
1201    ///     .build(r"[0-9]+")?;
1202    /// let dfa = dense::Builder::new().build_from_nfa(&nfa)?;
1203    /// let expected = Some(HalfMatch::must(0, 6));
1204    /// let got = dfa.try_search_fwd(&Input::new(haystack))?;
1205    /// assert_eq!(expected, got);
1206    ///
1207    /// # Ok::<(), Box<dyn std::error::Error>>(())
1208    /// ```
1209    pub fn build_from_nfa(
1210        &self,
1211        nfa: &thompson::NFA,
1212    ) -> Result<OwnedDFA, BuildError> {
1213        let mut quitset = self.config.quitset.unwrap_or(ByteSet::empty());
1214        if self.config.get_unicode_word_boundary()
1215            && nfa.look_set_any().contains_word_unicode()
1216        {
1217            for b in 0x80..=0xFF {
1218                quitset.add(b);
1219            }
1220        }
1221        let classes = if !self.config.get_byte_classes() {
1222            // DFAs will always use the equivalence class map, but enabling
1223            // this option is useful for debugging. Namely, this will cause all
1224            // transitions to be defined over their actual bytes instead of an
1225            // opaque equivalence class identifier. The former is much easier
1226            // to grok as a human.
1227            ByteClasses::singletons()
1228        } else {
1229            let mut set = nfa.byte_class_set().clone();
1230            // It is important to distinguish any "quit" bytes from all other
1231            // bytes. Otherwise, a non-quit byte may end up in the same
1232            // class as a quit byte, and thus cause the DFA to stop when it
1233            // shouldn't.
1234            //
1235            // Test case:
1236            //
1237            //   regex-cli find match dense --unicode-word-boundary \
1238            //     -p '^#' -p '\b10\.55\.182\.100\b' -y @conn.json.1000x.log
1239            if !quitset.is_empty() {
1240                set.add_set(&quitset);
1241            }
1242            set.byte_classes()
1243        };
1244
1245        let mut dfa = DFA::initial(
1246            classes,
1247            nfa.pattern_len(),
1248            self.config.get_starts(),
1249            nfa.look_matcher(),
1250            self.config.get_starts_for_each_pattern(),
1251            self.config.get_prefilter().map(|p| p.clone()),
1252            quitset,
1253            Flags::from_nfa(&nfa),
1254        )?;
1255        determinize::Config::new()
1256            .match_kind(self.config.get_match_kind())
1257            .quit(quitset)
1258            .dfa_size_limit(self.config.get_dfa_size_limit())
1259            .determinize_size_limit(self.config.get_determinize_size_limit())
1260            .run(nfa, &mut dfa)?;
1261        if self.config.get_minimize() {
1262            dfa.minimize();
1263        }
1264        if self.config.get_accelerate() {
1265            dfa.accelerate();
1266        }
1267        // The state shuffling done before this point always assumes that start
1268        // states should be marked as "special," even though it isn't the
1269        // default configuration. State shuffling is complex enough as it is,
1270        // so it's simpler to just "fix" our special state ID ranges to not
1271        // include starting states after-the-fact.
1272        if !self.config.get_specialize_start_states() {
1273            dfa.special.set_no_special_start_states();
1274        }
1275        // Look for and set the universal starting states.
1276        dfa.set_universal_starts();
1277        Ok(dfa)
1278    }
1279
1280    /// Apply the given dense DFA configuration options to this builder.
1281    pub fn configure(&mut self, config: Config) -> &mut Builder {
1282        self.config = self.config.overwrite(config);
1283        self
1284    }
1285
1286    /// Set the syntax configuration for this builder using
1287    /// [`syntax::Config`](crate::util::syntax::Config).
1288    ///
1289    /// This permits setting things like case insensitivity, Unicode and multi
1290    /// line mode.
1291    ///
1292    /// These settings only apply when constructing a DFA directly from a
1293    /// pattern.
1294    #[cfg(feature = "syntax")]
1295    pub fn syntax(
1296        &mut self,
1297        config: crate::util::syntax::Config,
1298    ) -> &mut Builder {
1299        self.thompson.syntax(config);
1300        self
1301    }
1302
1303    /// Set the Thompson NFA configuration for this builder using
1304    /// [`nfa::thompson::Config`](crate::nfa::thompson::Config).
1305    ///
1306    /// This permits setting things like whether the DFA should match the regex
1307    /// in reverse or if additional time should be spent shrinking the size of
1308    /// the NFA.
1309    ///
1310    /// These settings only apply when constructing a DFA directly from a
1311    /// pattern.
1312    #[cfg(feature = "syntax")]
1313    pub fn thompson(&mut self, config: thompson::Config) -> &mut Builder {
1314        self.thompson.configure(config);
1315        self
1316    }
1317}
1318
1319#[cfg(feature = "dfa-build")]
1320impl Default for Builder {
1321    fn default() -> Builder {
1322        Builder::new()
1323    }
1324}
1325
1326/// A convenience alias for an owned DFA. We use this particular instantiation
1327/// a lot in this crate, so it's worth giving it a name. This instantiation
1328/// is commonly used for mutable APIs on the DFA while building it. The main
1329/// reason for making DFAs generic is no_std support, and more generally,
1330/// making it possible to load a DFA from an arbitrary slice of bytes.
1331#[cfg(feature = "alloc")]
1332pub(crate) type OwnedDFA = DFA<alloc::vec::Vec<u32>>;
1333
1334/// A dense table-based deterministic finite automaton (DFA).
1335///
1336/// All dense DFAs have one or more start states, zero or more match states
1337/// and a transition table that maps the current state and the current byte
1338/// of input to the next state. A DFA can use this information to implement
1339/// fast searching. In particular, the use of a dense DFA generally makes the
1340/// trade off that match speed is the most valuable characteristic, even if
1341/// building the DFA may take significant time *and* space. (More concretely,
1342/// building a DFA takes time and space that is exponential in the size of the
1343/// pattern in the worst case.) As such, the processing of every byte of input
1344/// is done with a small constant number of operations that does not vary with
1345/// the pattern, its size or the size of the alphabet. If your needs don't line
1346/// up with this trade off, then a dense DFA may not be an adequate solution to
1347/// your problem.
1348///
1349/// In contrast, a [`sparse::DFA`] makes the opposite
1350/// trade off: it uses less space but will execute a variable number of
1351/// instructions per byte at match time, which makes it slower for matching.
1352/// (Note that space usage is still exponential in the size of the pattern in
1353/// the worst case.)
1354///
1355/// A DFA can be built using the default configuration via the
1356/// [`DFA::new`] constructor. Otherwise, one can
1357/// configure various aspects via [`dense::Builder`](Builder).
1358///
1359/// A single DFA fundamentally supports the following operations:
1360///
1361/// 1. Detection of a match.
1362/// 2. Location of the end of a match.
1363/// 3. In the case of a DFA with multiple patterns, which pattern matched is
1364///    reported as well.
1365///
1366/// A notable absence from the above list of capabilities is the location of
1367/// the *start* of a match. In order to provide both the start and end of
1368/// a match, *two* DFAs are required. This functionality is provided by a
1369/// [`Regex`](crate::dfa::regex::Regex).
1370///
1371/// # Type parameters
1372///
1373/// A `DFA` has one type parameter, `T`, which is used to represent state IDs,
1374/// pattern IDs and accelerators. `T` is typically a `Vec<u32>` or a `&[u32]`.
1375///
1376/// # The `Automaton` trait
1377///
1378/// This type implements the [`Automaton`] trait, which means it can be used
1379/// for searching. For example:
1380///
1381/// ```
1382/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
1383///
1384/// let dfa = DFA::new("foo[0-9]+")?;
1385/// let expected = HalfMatch::must(0, 8);
1386/// assert_eq!(Some(expected), dfa.try_search_fwd(&Input::new("foo12345"))?);
1387/// # Ok::<(), Box<dyn std::error::Error>>(())
1388/// ```
1389#[derive(Clone)]
1390pub struct DFA<T> {
1391    /// The transition table for this DFA. This includes the transitions
1392    /// themselves, along with the stride, number of states and the equivalence
1393    /// class mapping.
1394    tt: TransitionTable<T>,
1395    /// The set of starting state identifiers for this DFA. The starting state
1396    /// IDs act as pointers into the transition table. The specific starting
1397    /// state chosen for each search is dependent on the context at which the
1398    /// search begins.
1399    st: StartTable<T>,
1400    /// The set of match states and the patterns that match for each
1401    /// corresponding match state.
1402    ///
1403    /// This structure is technically only needed because of support for
1404    /// multi-regexes. Namely, multi-regexes require answering not just whether
1405    /// a match exists, but _which_ patterns match. So we need to store the
1406    /// matching pattern IDs for each match state. We do this even when there
1407    /// is only one pattern for the sake of simplicity. In practice, this uses
1408    /// up very little space for the case of one pattern.
1409    ms: MatchStates<T>,
1410    /// Information about which states are "special." Special states are states
1411    /// that are dead, quit, matching, starting or accelerated. For more info,
1412    /// see the docs for `Special`.
1413    special: Special,
1414    /// The accelerators for this DFA.
1415    ///
1416    /// If a state is accelerated, then there exist only a small number of
1417    /// bytes that can cause the DFA to leave the state. This permits searching
1418    /// to use optimized routines to find those specific bytes instead of using
1419    /// the transition table.
1420    ///
1421    /// All accelerated states exist in a contiguous range in the DFA's
1422    /// transition table. See dfa/special.rs for more details on how states are
1423    /// arranged.
1424    accels: Accels<T>,
1425    /// Any prefilter attached to this DFA.
1426    ///
1427    /// Note that currently prefilters are not serialized. When deserializing
1428    /// a DFA from bytes, this is always set to `None`.
1429    pre: Option<Prefilter>,
1430    /// The set of "quit" bytes for this DFA.
1431    ///
1432    /// This is only used when computing the start state for a particular
1433    /// position in a haystack. Namely, in the case where there is a quit
1434    /// byte immediately before the start of the search, this set needs to be
1435    /// explicitly consulted. In all other cases, quit bytes are detected by
1436    /// the DFA itself, by transitioning all quit bytes to a special "quit
1437    /// state."
1438    quitset: ByteSet,
1439    /// Various flags describing the behavior of this DFA.
1440    flags: Flags,
1441}
1442
1443#[cfg(feature = "dfa-build")]
1444impl OwnedDFA {
1445    /// Parse the given regular expression using a default configuration and
1446    /// return the corresponding DFA.
1447    ///
1448    /// If you want a non-default configuration, then use the
1449    /// [`dense::Builder`](Builder) to set your own configuration.
1450    ///
1451    /// # Example
1452    ///
1453    /// ```
1454    /// use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
1455    ///
1456    /// let dfa = dense::DFA::new("foo[0-9]+bar")?;
1457    /// let expected = Some(HalfMatch::must(0, 11));
1458    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345bar"))?);
1459    /// # Ok::<(), Box<dyn std::error::Error>>(())
1460    /// ```
1461    #[cfg(feature = "syntax")]
1462    pub fn new(pattern: &str) -> Result<OwnedDFA, BuildError> {
1463        Builder::new().build(pattern)
1464    }
1465
1466    /// Parse the given regular expressions using a default configuration and
1467    /// return the corresponding multi-DFA.
1468    ///
1469    /// If you want a non-default configuration, then use the
1470    /// [`dense::Builder`](Builder) to set your own configuration.
1471    ///
1472    /// # Example
1473    ///
1474    /// ```
1475    /// use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
1476    ///
1477    /// let dfa = dense::DFA::new_many(&["[0-9]+", "[a-z]+"])?;
1478    /// let expected = Some(HalfMatch::must(1, 3));
1479    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345bar"))?);
1480    /// # Ok::<(), Box<dyn std::error::Error>>(())
1481    /// ```
1482    #[cfg(feature = "syntax")]
1483    pub fn new_many<P: AsRef<str>>(
1484        patterns: &[P],
1485    ) -> Result<OwnedDFA, BuildError> {
1486        Builder::new().build_many(patterns)
1487    }
1488}
1489
1490#[cfg(feature = "dfa-build")]
1491impl OwnedDFA {
1492    /// Create a new DFA that matches every input.
1493    ///
1494    /// # Example
1495    ///
1496    /// ```
1497    /// use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
1498    ///
1499    /// let dfa = dense::DFA::always_match()?;
1500    ///
1501    /// let expected = Some(HalfMatch::must(0, 0));
1502    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new(""))?);
1503    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo"))?);
1504    /// # Ok::<(), Box<dyn std::error::Error>>(())
1505    /// ```
1506    pub fn always_match() -> Result<OwnedDFA, BuildError> {
1507        let nfa = thompson::NFA::always_match();
1508        Builder::new().build_from_nfa(&nfa)
1509    }
1510
1511    /// Create a new DFA that never matches any input.
1512    ///
1513    /// # Example
1514    ///
1515    /// ```
1516    /// use regex_automata::{dfa::{Automaton, dense}, Input};
1517    ///
1518    /// let dfa = dense::DFA::never_match()?;
1519    /// assert_eq!(None, dfa.try_search_fwd(&Input::new(""))?);
1520    /// assert_eq!(None, dfa.try_search_fwd(&Input::new("foo"))?);
1521    /// # Ok::<(), Box<dyn std::error::Error>>(())
1522    /// ```
1523    pub fn never_match() -> Result<OwnedDFA, BuildError> {
1524        let nfa = thompson::NFA::never_match();
1525        Builder::new().build_from_nfa(&nfa)
1526    }
1527
1528    /// Create an initial DFA with the given equivalence classes, pattern
1529    /// length and whether anchored starting states are enabled for each
1530    /// pattern. An initial DFA can be further mutated via determinization.
1531    fn initial(
1532        classes: ByteClasses,
1533        pattern_len: usize,
1534        starts: StartKind,
1535        lookm: &LookMatcher,
1536        starts_for_each_pattern: bool,
1537        pre: Option<Prefilter>,
1538        quitset: ByteSet,
1539        flags: Flags,
1540    ) -> Result<OwnedDFA, BuildError> {
1541        let start_pattern_len =
1542            if starts_for_each_pattern { Some(pattern_len) } else { None };
1543        Ok(DFA {
1544            tt: TransitionTable::minimal(classes),
1545            st: StartTable::dead(starts, lookm, start_pattern_len)?,
1546            ms: MatchStates::empty(pattern_len),
1547            special: Special::new(),
1548            accels: Accels::empty(),
1549            pre,
1550            quitset,
1551            flags,
1552        })
1553    }
1554}
1555
1556#[cfg(feature = "dfa-build")]
1557impl DFA<&[u32]> {
1558    /// Return a new default dense DFA compiler configuration.
1559    ///
1560    /// This is a convenience routine to avoid needing to import the [`Config`]
1561    /// type when customizing the construction of a dense DFA.
1562    pub fn config() -> Config {
1563        Config::new()
1564    }
1565
1566    /// Create a new dense DFA builder with the default configuration.
1567    ///
1568    /// This is a convenience routine to avoid needing to import the
1569    /// [`Builder`] type in common cases.
1570    pub fn builder() -> Builder {
1571        Builder::new()
1572    }
1573}
1574
1575impl<T: AsRef<[u32]>> DFA<T> {
1576    /// Cheaply return a borrowed version of this dense DFA. Specifically,
1577    /// the DFA returned always uses `&[u32]` for its transition table.
1578    pub fn as_ref(&self) -> DFA<&'_ [u32]> {
1579        DFA {
1580            tt: self.tt.as_ref(),
1581            st: self.st.as_ref(),
1582            ms: self.ms.as_ref(),
1583            special: self.special,
1584            accels: self.accels(),
1585            pre: self.pre.clone(),
1586            quitset: self.quitset,
1587            flags: self.flags,
1588        }
1589    }
1590
1591    /// Return an owned version of this sparse DFA. Specifically, the DFA
1592    /// returned always uses `Vec<u32>` for its transition table.
1593    ///
1594    /// Effectively, this returns a dense DFA whose transition table lives on
1595    /// the heap.
1596    #[cfg(feature = "alloc")]
1597    pub fn to_owned(&self) -> OwnedDFA {
1598        DFA {
1599            tt: self.tt.to_owned(),
1600            st: self.st.to_owned(),
1601            ms: self.ms.to_owned(),
1602            special: self.special,
1603            accels: self.accels().to_owned(),
1604            pre: self.pre.clone(),
1605            quitset: self.quitset,
1606            flags: self.flags,
1607        }
1608    }
1609
1610    /// Returns the starting state configuration for this DFA.
1611    ///
1612    /// The default is [`StartKind::Both`], which means the DFA supports both
1613    /// unanchored and anchored searches. However, this can generally lead to
1614    /// bigger DFAs. Therefore, a DFA might be compiled with support for just
1615    /// unanchored or anchored searches. In that case, running a search with
1616    /// an unsupported configuration will panic.
1617    pub fn start_kind(&self) -> StartKind {
1618        self.st.kind
1619    }
1620
1621    /// Returns the start byte map used for computing the `Start` configuration
1622    /// at the beginning of a search.
1623    pub(crate) fn start_map(&self) -> &StartByteMap {
1624        &self.st.start_map
1625    }
1626
1627    /// Returns true only if this DFA has starting states for each pattern.
1628    ///
1629    /// When a DFA has starting states for each pattern, then a search with the
1630    /// DFA can be configured to only look for anchored matches of a specific
1631    /// pattern. Specifically, APIs like [`Automaton::try_search_fwd`] can
1632    /// accept a non-None `pattern_id` if and only if this method returns true.
1633    /// Otherwise, calling `try_search_fwd` will panic.
1634    ///
1635    /// Note that if the DFA has no patterns, this always returns false.
1636    pub fn starts_for_each_pattern(&self) -> bool {
1637        self.st.pattern_len.is_some()
1638    }
1639
1640    /// Returns the equivalence classes that make up the alphabet for this DFA.
1641    ///
1642    /// Unless [`Config::byte_classes`] was disabled, it is possible that
1643    /// multiple distinct bytes are grouped into the same equivalence class
1644    /// if it is impossible for them to discriminate between a match and a
1645    /// non-match. This has the effect of reducing the overall alphabet size
1646    /// and in turn potentially substantially reducing the size of the DFA's
1647    /// transition table.
1648    ///
1649    /// The downside of using equivalence classes like this is that every state
1650    /// transition will automatically use this map to convert an arbitrary
1651    /// byte to its corresponding equivalence class. In practice this has a
1652    /// negligible impact on performance.
1653    pub fn byte_classes(&self) -> &ByteClasses {
1654        &self.tt.classes
1655    }
1656
1657    /// Returns the total number of elements in the alphabet for this DFA.
1658    ///
1659    /// That is, this returns the total number of transitions that each state
1660    /// in this DFA must have. Typically, a normal byte oriented DFA would
1661    /// always have an alphabet size of 256, corresponding to the number of
1662    /// unique values in a single byte. However, this implementation has two
1663    /// peculiarities that impact the alphabet length:
1664    ///
1665    /// * Every state has a special "EOI" transition that is only followed
1666    /// after the end of some haystack is reached. This EOI transition is
1667    /// necessary to account for one byte of look-ahead when implementing
1668    /// things like `\b` and `$`.
1669    /// * Bytes are grouped into equivalence classes such that no two bytes in
1670    /// the same class can distinguish a match from a non-match. For example,
1671    /// in the regex `^[a-z]+$`, the ASCII bytes `a-z` could all be in the
1672    /// same equivalence class. This leads to a massive space savings.
1673    ///
1674    /// Note though that the alphabet length does _not_ necessarily equal the
1675    /// total stride space taken up by a single DFA state in the transition
1676    /// table. Namely, for performance reasons, the stride is always the
1677    /// smallest power of two that is greater than or equal to the alphabet
1678    /// length. For this reason, [`DFA::stride`] or [`DFA::stride2`] are
1679    /// often more useful. The alphabet length is typically useful only for
1680    /// informational purposes.
1681    pub fn alphabet_len(&self) -> usize {
1682        self.tt.alphabet_len()
1683    }
1684
1685    /// Returns the total stride for every state in this DFA, expressed as the
1686    /// exponent of a power of 2. The stride is the amount of space each state
1687    /// takes up in the transition table, expressed as a number of transitions.
1688    /// (Unused transitions map to dead states.)
1689    ///
1690    /// The stride of a DFA is always equivalent to the smallest power of 2
1691    /// that is greater than or equal to the DFA's alphabet length. This
1692    /// definition uses extra space, but permits faster translation between
1693    /// premultiplied state identifiers and contiguous indices (by using shifts
1694    /// instead of relying on integer division).
1695    ///
1696    /// For example, if the DFA's stride is 16 transitions, then its `stride2`
1697    /// is `4` since `2^4 = 16`.
1698    ///
1699    /// The minimum `stride2` value is `1` (corresponding to a stride of `2`)
1700    /// while the maximum `stride2` value is `9` (corresponding to a stride of
1701    /// `512`). The maximum is not `8` since the maximum alphabet size is `257`
1702    /// when accounting for the special EOI transition. However, an alphabet
1703    /// length of that size is exceptionally rare since the alphabet is shrunk
1704    /// into equivalence classes.
1705    pub fn stride2(&self) -> usize {
1706        self.tt.stride2
1707    }
1708
1709    /// Returns the total stride for every state in this DFA. This corresponds
1710    /// to the total number of transitions used by each state in this DFA's
1711    /// transition table.
1712    ///
1713    /// Please see [`DFA::stride2`] for more information. In particular, this
1714    /// returns the stride as the number of transitions, where as `stride2`
1715    /// returns it as the exponent of a power of 2.
1716    pub fn stride(&self) -> usize {
1717        self.tt.stride()
1718    }
1719
1720    /// Returns the memory usage, in bytes, of this DFA.
1721    ///
1722    /// The memory usage is computed based on the number of bytes used to
1723    /// represent this DFA.
1724    ///
1725    /// This does **not** include the stack size used up by this DFA. To
1726    /// compute that, use `std::mem::size_of::<dense::DFA>()`.
1727    pub fn memory_usage(&self) -> usize {
1728        self.tt.memory_usage()
1729            + self.st.memory_usage()
1730            + self.ms.memory_usage()
1731            + self.accels.memory_usage()
1732    }
1733}
1734
1735/// Routines for converting a dense DFA to other representations, such as
1736/// sparse DFAs or raw bytes suitable for persistent storage.
1737impl<T: AsRef<[u32]>> DFA<T> {
1738    /// Convert this dense DFA to a sparse DFA.
1739    ///
1740    /// If a `StateID` is too small to represent all states in the sparse
1741    /// DFA, then this returns an error. In most cases, if a dense DFA is
1742    /// constructable with `StateID` then a sparse DFA will be as well.
1743    /// However, it is not guaranteed.
1744    ///
1745    /// # Example
1746    ///
1747    /// ```
1748    /// use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
1749    ///
1750    /// let dense = dense::DFA::new("foo[0-9]+")?;
1751    /// let sparse = dense.to_sparse()?;
1752    ///
1753    /// let expected = Some(HalfMatch::must(0, 8));
1754    /// assert_eq!(expected, sparse.try_search_fwd(&Input::new("foo12345"))?);
1755    /// # Ok::<(), Box<dyn std::error::Error>>(())
1756    /// ```
1757    #[cfg(feature = "dfa-build")]
1758    pub fn to_sparse(&self) -> Result<sparse::DFA<Vec<u8>>, BuildError> {
1759        sparse::DFA::from_dense(self)
1760    }
1761
1762    /// Serialize this DFA as raw bytes to a `Vec<u8>` in little endian
1763    /// format. Upon success, the `Vec<u8>` and the initial padding length are
1764    /// returned.
1765    ///
1766    /// The written bytes are guaranteed to be deserialized correctly and
1767    /// without errors in a semver compatible release of this crate by a
1768    /// `DFA`'s deserialization APIs (assuming all other criteria for the
1769    /// deserialization APIs has been satisfied):
1770    ///
1771    /// * [`DFA::from_bytes`]
1772    /// * [`DFA::from_bytes_unchecked`]
1773    ///
1774    /// The padding returned is non-zero if the returned `Vec<u8>` starts at
1775    /// an address that does not have the same alignment as `u32`. The padding
1776    /// corresponds to the number of leading bytes written to the returned
1777    /// `Vec<u8>`.
1778    ///
1779    /// # Example
1780    ///
1781    /// This example shows how to serialize and deserialize a DFA:
1782    ///
1783    /// ```
1784    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
1785    ///
1786    /// // Compile our original DFA.
1787    /// let original_dfa = DFA::new("foo[0-9]+")?;
1788    ///
1789    /// // N.B. We use native endianness here to make the example work, but
1790    /// // using to_bytes_little_endian would work on a little endian target.
1791    /// let (buf, _) = original_dfa.to_bytes_native_endian();
1792    /// // Even if buf has initial padding, DFA::from_bytes will automatically
1793    /// // ignore it.
1794    /// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf)?.0;
1795    ///
1796    /// let expected = Some(HalfMatch::must(0, 8));
1797    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
1798    /// # Ok::<(), Box<dyn std::error::Error>>(())
1799    /// ```
1800    #[cfg(feature = "dfa-build")]
1801    pub fn to_bytes_little_endian(&self) -> (Vec<u8>, usize) {
1802        self.to_bytes::<wire::LE>()
1803    }
1804
1805    /// Serialize this DFA as raw bytes to a `Vec<u8>` in big endian
1806    /// format. Upon success, the `Vec<u8>` and the initial padding length are
1807    /// returned.
1808    ///
1809    /// The written bytes are guaranteed to be deserialized correctly and
1810    /// without errors in a semver compatible release of this crate by a
1811    /// `DFA`'s deserialization APIs (assuming all other criteria for the
1812    /// deserialization APIs has been satisfied):
1813    ///
1814    /// * [`DFA::from_bytes`]
1815    /// * [`DFA::from_bytes_unchecked`]
1816    ///
1817    /// The padding returned is non-zero if the returned `Vec<u8>` starts at
1818    /// an address that does not have the same alignment as `u32`. The padding
1819    /// corresponds to the number of leading bytes written to the returned
1820    /// `Vec<u8>`.
1821    ///
1822    /// # Example
1823    ///
1824    /// This example shows how to serialize and deserialize a DFA:
1825    ///
1826    /// ```
1827    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
1828    ///
1829    /// // Compile our original DFA.
1830    /// let original_dfa = DFA::new("foo[0-9]+")?;
1831    ///
1832    /// // N.B. We use native endianness here to make the example work, but
1833    /// // using to_bytes_big_endian would work on a big endian target.
1834    /// let (buf, _) = original_dfa.to_bytes_native_endian();
1835    /// // Even if buf has initial padding, DFA::from_bytes will automatically
1836    /// // ignore it.
1837    /// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf)?.0;
1838    ///
1839    /// let expected = Some(HalfMatch::must(0, 8));
1840    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
1841    /// # Ok::<(), Box<dyn std::error::Error>>(())
1842    /// ```
1843    #[cfg(feature = "dfa-build")]
1844    pub fn to_bytes_big_endian(&self) -> (Vec<u8>, usize) {
1845        self.to_bytes::<wire::BE>()
1846    }
1847
1848    /// Serialize this DFA as raw bytes to a `Vec<u8>` in native endian
1849    /// format. Upon success, the `Vec<u8>` and the initial padding length are
1850    /// returned.
1851    ///
1852    /// The written bytes are guaranteed to be deserialized correctly and
1853    /// without errors in a semver compatible release of this crate by a
1854    /// `DFA`'s deserialization APIs (assuming all other criteria for the
1855    /// deserialization APIs has been satisfied):
1856    ///
1857    /// * [`DFA::from_bytes`]
1858    /// * [`DFA::from_bytes_unchecked`]
1859    ///
1860    /// The padding returned is non-zero if the returned `Vec<u8>` starts at
1861    /// an address that does not have the same alignment as `u32`. The padding
1862    /// corresponds to the number of leading bytes written to the returned
1863    /// `Vec<u8>`.
1864    ///
1865    /// Generally speaking, native endian format should only be used when
1866    /// you know that the target you're compiling the DFA for matches the
1867    /// endianness of the target on which you're compiling DFA. For example,
1868    /// if serialization and deserialization happen in the same process or on
1869    /// the same machine. Otherwise, when serializing a DFA for use in a
1870    /// portable environment, you'll almost certainly want to serialize _both_
1871    /// a little endian and a big endian version and then load the correct one
1872    /// based on the target's configuration.
1873    ///
1874    /// # Example
1875    ///
1876    /// This example shows how to serialize and deserialize a DFA:
1877    ///
1878    /// ```
1879    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
1880    ///
1881    /// // Compile our original DFA.
1882    /// let original_dfa = DFA::new("foo[0-9]+")?;
1883    ///
1884    /// let (buf, _) = original_dfa.to_bytes_native_endian();
1885    /// // Even if buf has initial padding, DFA::from_bytes will automatically
1886    /// // ignore it.
1887    /// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf)?.0;
1888    ///
1889    /// let expected = Some(HalfMatch::must(0, 8));
1890    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
1891    /// # Ok::<(), Box<dyn std::error::Error>>(())
1892    /// ```
1893    #[cfg(feature = "dfa-build")]
1894    pub fn to_bytes_native_endian(&self) -> (Vec<u8>, usize) {
1895        self.to_bytes::<wire::NE>()
1896    }
1897
1898    /// The implementation of the public `to_bytes` serialization methods,
1899    /// which is generic over endianness.
1900    #[cfg(feature = "dfa-build")]
1901    fn to_bytes<E: Endian>(&self) -> (Vec<u8>, usize) {
1902        let len = self.write_to_len();
1903        let (mut buf, padding) = wire::alloc_aligned_buffer::<u32>(len);
1904        // This should always succeed since the only possible serialization
1905        // error is providing a buffer that's too small, but we've ensured that
1906        // `buf` is big enough here.
1907        self.as_ref().write_to::<E>(&mut buf[padding..]).unwrap();
1908        (buf, padding)
1909    }
1910
1911    /// Serialize this DFA as raw bytes to the given slice, in little endian
1912    /// format. Upon success, the total number of bytes written to `dst` is
1913    /// returned.
1914    ///
1915    /// The written bytes are guaranteed to be deserialized correctly and
1916    /// without errors in a semver compatible release of this crate by a
1917    /// `DFA`'s deserialization APIs (assuming all other criteria for the
1918    /// deserialization APIs has been satisfied):
1919    ///
1920    /// * [`DFA::from_bytes`]
1921    /// * [`DFA::from_bytes_unchecked`]
1922    ///
1923    /// Note that unlike the various `to_byte_*` routines, this does not write
1924    /// any padding. Callers are responsible for handling alignment correctly.
1925    ///
1926    /// # Errors
1927    ///
1928    /// This returns an error if the given destination slice is not big enough
1929    /// to contain the full serialized DFA. If an error occurs, then nothing
1930    /// is written to `dst`.
1931    ///
1932    /// # Example
1933    ///
1934    /// This example shows how to serialize and deserialize a DFA without
1935    /// dynamic memory allocation.
1936    ///
1937    /// ```
1938    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
1939    ///
1940    /// // Compile our original DFA.
1941    /// let original_dfa = DFA::new("foo[0-9]+")?;
1942    ///
1943    /// // Create a 4KB buffer on the stack to store our serialized DFA. We
1944    /// // need to use a special type to force the alignment of our [u8; N]
1945    /// // array to be aligned to a 4 byte boundary. Otherwise, deserializing
1946    /// // the DFA may fail because of an alignment mismatch.
1947    /// #[repr(C)]
1948    /// struct Aligned<B: ?Sized> {
1949    ///     _align: [u32; 0],
1950    ///     bytes: B,
1951    /// }
1952    /// let mut buf = Aligned { _align: [], bytes: [0u8; 4 * (1<<10)] };
1953    /// // N.B. We use native endianness here to make the example work, but
1954    /// // using write_to_little_endian would work on a little endian target.
1955    /// let written = original_dfa.write_to_native_endian(&mut buf.bytes)?;
1956    /// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf.bytes[..written])?.0;
1957    ///
1958    /// let expected = Some(HalfMatch::must(0, 8));
1959    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
1960    /// # Ok::<(), Box<dyn std::error::Error>>(())
1961    /// ```
1962    pub fn write_to_little_endian(
1963        &self,
1964        dst: &mut [u8],
1965    ) -> Result<usize, SerializeError> {
1966        self.as_ref().write_to::<wire::LE>(dst)
1967    }
1968
1969    /// Serialize this DFA as raw bytes to the given slice, in big endian
1970    /// format. Upon success, the total number of bytes written to `dst` is
1971    /// returned.
1972    ///
1973    /// The written bytes are guaranteed to be deserialized correctly and
1974    /// without errors in a semver compatible release of this crate by a
1975    /// `DFA`'s deserialization APIs (assuming all other criteria for the
1976    /// deserialization APIs has been satisfied):
1977    ///
1978    /// * [`DFA::from_bytes`]
1979    /// * [`DFA::from_bytes_unchecked`]
1980    ///
1981    /// Note that unlike the various `to_byte_*` routines, this does not write
1982    /// any padding. Callers are responsible for handling alignment correctly.
1983    ///
1984    /// # Errors
1985    ///
1986    /// This returns an error if the given destination slice is not big enough
1987    /// to contain the full serialized DFA. If an error occurs, then nothing
1988    /// is written to `dst`.
1989    ///
1990    /// # Example
1991    ///
1992    /// This example shows how to serialize and deserialize a DFA without
1993    /// dynamic memory allocation.
1994    ///
1995    /// ```
1996    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
1997    ///
1998    /// // Compile our original DFA.
1999    /// let original_dfa = DFA::new("foo[0-9]+")?;
2000    ///
2001    /// // Create a 4KB buffer on the stack to store our serialized DFA. We
2002    /// // need to use a special type to force the alignment of our [u8; N]
2003    /// // array to be aligned to a 4 byte boundary. Otherwise, deserializing
2004    /// // the DFA may fail because of an alignment mismatch.
2005    /// #[repr(C)]
2006    /// struct Aligned<B: ?Sized> {
2007    ///     _align: [u32; 0],
2008    ///     bytes: B,
2009    /// }
2010    /// let mut buf = Aligned { _align: [], bytes: [0u8; 4 * (1<<10)] };
2011    /// // N.B. We use native endianness here to make the example work, but
2012    /// // using write_to_big_endian would work on a big endian target.
2013    /// let written = original_dfa.write_to_native_endian(&mut buf.bytes)?;
2014    /// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf.bytes[..written])?.0;
2015    ///
2016    /// let expected = Some(HalfMatch::must(0, 8));
2017    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
2018    /// # Ok::<(), Box<dyn std::error::Error>>(())
2019    /// ```
2020    pub fn write_to_big_endian(
2021        &self,
2022        dst: &mut [u8],
2023    ) -> Result<usize, SerializeError> {
2024        self.as_ref().write_to::<wire::BE>(dst)
2025    }
2026
2027    /// Serialize this DFA as raw bytes to the given slice, in native endian
2028    /// format. Upon success, the total number of bytes written to `dst` is
2029    /// returned.
2030    ///
2031    /// The written bytes are guaranteed to be deserialized correctly and
2032    /// without errors in a semver compatible release of this crate by a
2033    /// `DFA`'s deserialization APIs (assuming all other criteria for the
2034    /// deserialization APIs has been satisfied):
2035    ///
2036    /// * [`DFA::from_bytes`]
2037    /// * [`DFA::from_bytes_unchecked`]
2038    ///
2039    /// Generally speaking, native endian format should only be used when
2040    /// you know that the target you're compiling the DFA for matches the
2041    /// endianness of the target on which you're compiling DFA. For example,
2042    /// if serialization and deserialization happen in the same process or on
2043    /// the same machine. Otherwise, when serializing a DFA for use in a
2044    /// portable environment, you'll almost certainly want to serialize _both_
2045    /// a little endian and a big endian version and then load the correct one
2046    /// based on the target's configuration.
2047    ///
2048    /// Note that unlike the various `to_byte_*` routines, this does not write
2049    /// any padding. Callers are responsible for handling alignment correctly.
2050    ///
2051    /// # Errors
2052    ///
2053    /// This returns an error if the given destination slice is not big enough
2054    /// to contain the full serialized DFA. If an error occurs, then nothing
2055    /// is written to `dst`.
2056    ///
2057    /// # Example
2058    ///
2059    /// This example shows how to serialize and deserialize a DFA without
2060    /// dynamic memory allocation.
2061    ///
2062    /// ```
2063    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
2064    ///
2065    /// // Compile our original DFA.
2066    /// let original_dfa = DFA::new("foo[0-9]+")?;
2067    ///
2068    /// // Create a 4KB buffer on the stack to store our serialized DFA. We
2069    /// // need to use a special type to force the alignment of our [u8; N]
2070    /// // array to be aligned to a 4 byte boundary. Otherwise, deserializing
2071    /// // the DFA may fail because of an alignment mismatch.
2072    /// #[repr(C)]
2073    /// struct Aligned<B: ?Sized> {
2074    ///     _align: [u32; 0],
2075    ///     bytes: B,
2076    /// }
2077    /// let mut buf = Aligned { _align: [], bytes: [0u8; 4 * (1<<10)] };
2078    /// let written = original_dfa.write_to_native_endian(&mut buf.bytes)?;
2079    /// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf.bytes[..written])?.0;
2080    ///
2081    /// let expected = Some(HalfMatch::must(0, 8));
2082    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
2083    /// # Ok::<(), Box<dyn std::error::Error>>(())
2084    /// ```
2085    pub fn write_to_native_endian(
2086        &self,
2087        dst: &mut [u8],
2088    ) -> Result<usize, SerializeError> {
2089        self.as_ref().write_to::<wire::NE>(dst)
2090    }
2091
2092    /// Return the total number of bytes required to serialize this DFA.
2093    ///
2094    /// This is useful for determining the size of the buffer required to pass
2095    /// to one of the serialization routines:
2096    ///
2097    /// * [`DFA::write_to_little_endian`]
2098    /// * [`DFA::write_to_big_endian`]
2099    /// * [`DFA::write_to_native_endian`]
2100    ///
2101    /// Passing a buffer smaller than the size returned by this method will
2102    /// result in a serialization error. Serialization routines are guaranteed
2103    /// to succeed when the buffer is big enough.
2104    ///
2105    /// # Example
2106    ///
2107    /// This example shows how to dynamically allocate enough room to serialize
2108    /// a DFA.
2109    ///
2110    /// ```
2111    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
2112    ///
2113    /// let original_dfa = DFA::new("foo[0-9]+")?;
2114    ///
2115    /// let mut buf = vec![0; original_dfa.write_to_len()];
2116    /// // This is guaranteed to succeed, because the only serialization error
2117    /// // that can occur is when the provided buffer is too small. But
2118    /// // write_to_len guarantees a correct size.
2119    /// let written = original_dfa.write_to_native_endian(&mut buf).unwrap();
2120    /// // But this is not guaranteed to succeed! In particular,
2121    /// // deserialization requires proper alignment for &[u32], but our buffer
2122    /// // was allocated as a &[u8] whose required alignment is smaller than
2123    /// // &[u32]. However, it's likely to work in practice because of how most
2124    /// // allocators work. So if you write code like this, make sure to either
2125    /// // handle the error correctly and/or run it under Miri since Miri will
2126    /// // likely provoke the error by returning Vec<u8> buffers with alignment
2127    /// // less than &[u32].
2128    /// let dfa: DFA<&[u32]> = match DFA::from_bytes(&buf[..written]) {
2129    ///     // As mentioned above, it is legal for an error to be returned
2130    ///     // here. It is quite difficult to get a Vec<u8> with a guaranteed
2131    ///     // alignment equivalent to Vec<u32>.
2132    ///     Err(_) => return Ok(()),
2133    ///     Ok((dfa, _)) => dfa,
2134    /// };
2135    ///
2136    /// let expected = Some(HalfMatch::must(0, 8));
2137    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
2138    /// # Ok::<(), Box<dyn std::error::Error>>(())
2139    /// ```
2140    ///
2141    /// Note that this example isn't actually guaranteed to work! In
2142    /// particular, if `buf` is not aligned to a 4-byte boundary, then the
2143    /// `DFA::from_bytes` call will fail. If you need this to work, then you
2144    /// either need to deal with adding some initial padding yourself, or use
2145    /// one of the `to_bytes` methods, which will do it for you.
2146    pub fn write_to_len(&self) -> usize {
2147        wire::write_label_len(LABEL)
2148        + wire::write_endianness_check_len()
2149        + wire::write_version_len()
2150        + size_of::<u32>() // unused, intended for future flexibility
2151        + self.flags.write_to_len()
2152        + self.tt.write_to_len()
2153        + self.st.write_to_len()
2154        + self.ms.write_to_len()
2155        + self.special.write_to_len()
2156        + self.accels.write_to_len()
2157        + self.quitset.write_to_len()
2158    }
2159}
2160
2161impl<'a> DFA<&'a [u32]> {
2162    /// Safely deserialize a DFA with a specific state identifier
2163    /// representation. Upon success, this returns both the deserialized DFA
2164    /// and the number of bytes read from the given slice. Namely, the contents
2165    /// of the slice beyond the DFA are not read.
2166    ///
2167    /// Deserializing a DFA using this routine will never allocate heap memory.
2168    /// For safety purposes, the DFA's transition table will be verified such
2169    /// that every transition points to a valid state. If this verification is
2170    /// too costly, then a [`DFA::from_bytes_unchecked`] API is provided, which
2171    /// will always execute in constant time.
2172    ///
2173    /// The bytes given must be generated by one of the serialization APIs
2174    /// of a `DFA` using a semver compatible release of this crate. Those
2175    /// include:
2176    ///
2177    /// * [`DFA::to_bytes_little_endian`]
2178    /// * [`DFA::to_bytes_big_endian`]
2179    /// * [`DFA::to_bytes_native_endian`]
2180    /// * [`DFA::write_to_little_endian`]
2181    /// * [`DFA::write_to_big_endian`]
2182    /// * [`DFA::write_to_native_endian`]
2183    ///
2184    /// The `to_bytes` methods allocate and return a `Vec<u8>` for you, along
2185    /// with handling alignment correctly. The `write_to` methods do not
2186    /// allocate and write to an existing slice (which may be on the stack).
2187    /// Since deserialization always uses the native endianness of the target
2188    /// platform, the serialization API you use should match the endianness of
2189    /// the target platform. (It's often a good idea to generate serialized
2190    /// DFAs for both forms of endianness and then load the correct one based
2191    /// on endianness.)
2192    ///
2193    /// # Errors
2194    ///
2195    /// Generally speaking, it's easier to state the conditions in which an
2196    /// error is _not_ returned. All of the following must be true:
2197    ///
2198    /// * The bytes given must be produced by one of the serialization APIs
2199    ///   on this DFA, as mentioned above.
2200    /// * The endianness of the target platform matches the endianness used to
2201    ///   serialized the provided DFA.
2202    /// * The slice given must have the same alignment as `u32`.
2203    ///
2204    /// If any of the above are not true, then an error will be returned.
2205    ///
2206    /// # Panics
2207    ///
2208    /// This routine will never panic for any input.
2209    ///
2210    /// # Example
2211    ///
2212    /// This example shows how to serialize a DFA to raw bytes, deserialize it
2213    /// and then use it for searching.
2214    ///
2215    /// ```
2216    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
2217    ///
2218    /// let initial = DFA::new("foo[0-9]+")?;
2219    /// let (bytes, _) = initial.to_bytes_native_endian();
2220    /// let dfa: DFA<&[u32]> = DFA::from_bytes(&bytes)?.0;
2221    ///
2222    /// let expected = Some(HalfMatch::must(0, 8));
2223    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
2224    /// # Ok::<(), Box<dyn std::error::Error>>(())
2225    /// ```
2226    ///
2227    /// # Example: dealing with alignment and padding
2228    ///
2229    /// In the above example, we used the `to_bytes_native_endian` method to
2230    /// serialize a DFA, but we ignored part of its return value corresponding
2231    /// to padding added to the beginning of the serialized DFA. This is OK
2232    /// because deserialization will skip this initial padding. What matters
2233    /// is that the address immediately following the padding has an alignment
2234    /// that matches `u32`. That is, the following is an equivalent but
2235    /// alternative way to write the above example:
2236    ///
2237    /// ```
2238    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
2239    ///
2240    /// let initial = DFA::new("foo[0-9]+")?;
2241    /// // Serialization returns the number of leading padding bytes added to
2242    /// // the returned Vec<u8>.
2243    /// let (bytes, pad) = initial.to_bytes_native_endian();
2244    /// let dfa: DFA<&[u32]> = DFA::from_bytes(&bytes[pad..])?.0;
2245    ///
2246    /// let expected = Some(HalfMatch::must(0, 8));
2247    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
2248    /// # Ok::<(), Box<dyn std::error::Error>>(())
2249    /// ```
2250    ///
2251    /// This padding is necessary because Rust's standard library does
2252    /// not expose any safe and robust way of creating a `Vec<u8>` with a
2253    /// guaranteed alignment other than 1. Now, in practice, the underlying
2254    /// allocator is likely to provide a `Vec<u8>` that meets our alignment
2255    /// requirements, which means `pad` is zero in practice most of the time.
2256    ///
2257    /// The purpose of exposing the padding like this is flexibility for the
2258    /// caller. For example, if one wants to embed a serialized DFA into a
2259    /// compiled program, then it's important to guarantee that it starts at a
2260    /// `u32`-aligned address. The simplest way to do this is to discard the
2261    /// padding bytes and set it up so that the serialized DFA itself begins at
2262    /// a properly aligned address. We can show this in two parts. The first
2263    /// part is serializing the DFA to a file:
2264    ///
2265    /// ```no_run
2266    /// use regex_automata::dfa::dense::DFA;
2267    ///
2268    /// let dfa = DFA::new("foo[0-9]+")?;
2269    ///
2270    /// let (bytes, pad) = dfa.to_bytes_big_endian();
2271    /// // Write the contents of the DFA *without* the initial padding.
2272    /// std::fs::write("foo.bigendian.dfa", &bytes[pad..])?;
2273    ///
2274    /// // Do it again, but this time for little endian.
2275    /// let (bytes, pad) = dfa.to_bytes_little_endian();
2276    /// std::fs::write("foo.littleendian.dfa", &bytes[pad..])?;
2277    /// # Ok::<(), Box<dyn std::error::Error>>(())
2278    /// ```
2279    ///
2280    /// And now the second part is embedding the DFA into the compiled program
2281    /// and deserializing it at runtime on first use. We use conditional
2282    /// compilation to choose the correct endianness.
2283    ///
2284    /// ```no_run
2285    /// use regex_automata::{
2286    ///     dfa::{Automaton, dense::DFA},
2287    ///     util::{lazy::Lazy, wire::AlignAs},
2288    ///     HalfMatch, Input,
2289    /// };
2290    ///
2291    /// // This crate provides its own "lazy" type, kind of like
2292    /// // lazy_static! or once_cell::sync::Lazy. But it works in no-alloc
2293    /// // no-std environments and let's us write this using completely
2294    /// // safe code.
2295    /// static RE: Lazy<DFA<&'static [u32]>> = Lazy::new(|| {
2296    ///     # const _: &str = stringify! {
2297    ///     // This assignment is made possible (implicitly) via the
2298    ///     // CoerceUnsized trait. This is what guarantees that our
2299    ///     // bytes are stored in memory on a 4 byte boundary. You
2300    ///     // *must* do this or something equivalent for correct
2301    ///     // deserialization.
2302    ///     static ALIGNED: &AlignAs<[u8], u32> = &AlignAs {
2303    ///         _align: [],
2304    ///         #[cfg(target_endian = "big")]
2305    ///         bytes: *include_bytes!("foo.bigendian.dfa"),
2306    ///         #[cfg(target_endian = "little")]
2307    ///         bytes: *include_bytes!("foo.littleendian.dfa"),
2308    ///     };
2309    ///     # };
2310    ///     # static ALIGNED: &AlignAs<[u8], u32> = &AlignAs {
2311    ///     #     _align: [],
2312    ///     #     bytes: [],
2313    ///     # };
2314    ///
2315    ///     let (dfa, _) = DFA::from_bytes(&ALIGNED.bytes)
2316    ///         .expect("serialized DFA should be valid");
2317    ///     dfa
2318    /// });
2319    ///
2320    /// let expected = Ok(Some(HalfMatch::must(0, 8)));
2321    /// assert_eq!(expected, RE.try_search_fwd(&Input::new("foo12345")));
2322    /// ```
2323    ///
2324    /// An alternative to [`util::lazy::Lazy`](crate::util::lazy::Lazy)
2325    /// is [`lazy_static`](https://crates.io/crates/lazy_static) or
2326    /// [`once_cell`](https://crates.io/crates/once_cell), which provide
2327    /// stronger guarantees (like the initialization function only being
2328    /// executed once). And `once_cell` in particular provides a more
2329    /// expressive API. But a `Lazy` value from this crate is likely just fine
2330    /// in most circumstances.
2331    ///
2332    /// Note that regardless of which initialization method you use, you
2333    /// will still need to use the [`AlignAs`](crate::util::wire::AlignAs)
2334    /// trick above to force correct alignment, but this is safe to do and
2335    /// `from_bytes` will return an error if you get it wrong.
2336    pub fn from_bytes(
2337        slice: &'a [u8],
2338    ) -> Result<(DFA<&'a [u32]>, usize), DeserializeError> {
2339        // SAFETY: This is safe because we validate the transition table, start
2340        // table, match states and accelerators below. If any validation fails,
2341        // then we return an error.
2342        let (dfa, nread) = unsafe { DFA::from_bytes_unchecked(slice)? };
2343        dfa.tt.validate(&dfa)?;
2344        dfa.st.validate(&dfa)?;
2345        dfa.ms.validate(&dfa)?;
2346        dfa.accels.validate()?;
2347        // N.B. dfa.special doesn't have a way to do unchecked deserialization,
2348        // so it has already been validated.
2349        for state in dfa.states() {
2350            // If the state is an accel state, then it must have a non-empty
2351            // accelerator.
2352            if dfa.is_accel_state(state.id()) {
2353                let index = dfa.accelerator_index(state.id());
2354                if index >= dfa.accels.len() {
2355                    return Err(DeserializeError::generic(
2356                        "found DFA state with invalid accelerator index",
2357                    ));
2358                }
2359                let needles = dfa.accels.needles(index);
2360                if !(1 <= needles.len() && needles.len() <= 3) {
2361                    return Err(DeserializeError::generic(
2362                        "accelerator needles has invalid length",
2363                    ));
2364                }
2365            }
2366        }
2367        Ok((dfa, nread))
2368    }
2369
2370    /// Deserialize a DFA with a specific state identifier representation in
2371    /// constant time by omitting the verification of the validity of the
2372    /// transition table and other data inside the DFA.
2373    ///
2374    /// This is just like [`DFA::from_bytes`], except it can potentially return
2375    /// a DFA that exhibits undefined behavior if its transition table contains
2376    /// invalid state identifiers.
2377    ///
2378    /// This routine is useful if you need to deserialize a DFA cheaply
2379    /// and cannot afford the transition table validation performed by
2380    /// `from_bytes`.
2381    ///
2382    /// # Example
2383    ///
2384    /// ```
2385    /// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
2386    ///
2387    /// let initial = DFA::new("foo[0-9]+")?;
2388    /// let (bytes, _) = initial.to_bytes_native_endian();
2389    /// // SAFETY: This is guaranteed to be safe since the bytes given come
2390    /// // directly from a compatible serialization routine.
2391    /// let dfa: DFA<&[u32]> = unsafe { DFA::from_bytes_unchecked(&bytes)?.0 };
2392    ///
2393    /// let expected = Some(HalfMatch::must(0, 8));
2394    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
2395    /// # Ok::<(), Box<dyn std::error::Error>>(())
2396    /// ```
2397    pub unsafe fn from_bytes_unchecked(
2398        slice: &'a [u8],
2399    ) -> Result<(DFA<&'a [u32]>, usize), DeserializeError> {
2400        let mut nr = 0;
2401
2402        nr += wire::skip_initial_padding(slice);
2403        wire::check_alignment::<StateID>(&slice[nr..])?;
2404        nr += wire::read_label(&slice[nr..], LABEL)?;
2405        nr += wire::read_endianness_check(&slice[nr..])?;
2406        nr += wire::read_version(&slice[nr..], VERSION)?;
2407
2408        let _unused = wire::try_read_u32(&slice[nr..], "unused space")?;
2409        nr += size_of::<u32>();
2410
2411        let (flags, nread) = Flags::from_bytes(&slice[nr..])?;
2412        nr += nread;
2413
2414        let (tt, nread) = TransitionTable::from_bytes_unchecked(&slice[nr..])?;
2415        nr += nread;
2416
2417        let (st, nread) = StartTable::from_bytes_unchecked(&slice[nr..])?;
2418        nr += nread;
2419
2420        let (ms, nread) = MatchStates::from_bytes_unchecked(&slice[nr..])?;
2421        nr += nread;
2422
2423        let (special, nread) = Special::from_bytes(&slice[nr..])?;
2424        nr += nread;
2425        special.validate_state_len(tt.len(), tt.stride2)?;
2426
2427        let (accels, nread) = Accels::from_bytes_unchecked(&slice[nr..])?;
2428        nr += nread;
2429
2430        let (quitset, nread) = ByteSet::from_bytes(&slice[nr..])?;
2431        nr += nread;
2432
2433        // Prefilters don't support serialization, so they're always absent.
2434        let pre = None;
2435        Ok((DFA { tt, st, ms, special, accels, pre, quitset, flags }, nr))
2436    }
2437
2438    /// The implementation of the public `write_to` serialization methods,
2439    /// which is generic over endianness.
2440    ///
2441    /// This is defined only for &[u32] to reduce binary size/compilation time.
2442    fn write_to<E: Endian>(
2443        &self,
2444        mut dst: &mut [u8],
2445    ) -> Result<usize, SerializeError> {
2446        let nwrite = self.write_to_len();
2447        if dst.len() < nwrite {
2448            return Err(SerializeError::buffer_too_small("dense DFA"));
2449        }
2450        dst = &mut dst[..nwrite];
2451
2452        let mut nw = 0;
2453        nw += wire::write_label(LABEL, &mut dst[nw..])?;
2454        nw += wire::write_endianness_check::<E>(&mut dst[nw..])?;
2455        nw += wire::write_version::<E>(VERSION, &mut dst[nw..])?;
2456        nw += {
2457            // Currently unused, intended for future flexibility
2458            E::write_u32(0, &mut dst[nw..]);
2459            size_of::<u32>()
2460        };
2461        nw += self.flags.write_to::<E>(&mut dst[nw..])?;
2462        nw += self.tt.write_to::<E>(&mut dst[nw..])?;
2463        nw += self.st.write_to::<E>(&mut dst[nw..])?;
2464        nw += self.ms.write_to::<E>(&mut dst[nw..])?;
2465        nw += self.special.write_to::<E>(&mut dst[nw..])?;
2466        nw += self.accels.write_to::<E>(&mut dst[nw..])?;
2467        nw += self.quitset.write_to::<E>(&mut dst[nw..])?;
2468        Ok(nw)
2469    }
2470}
2471
2472/// Other routines that work for all `T`.
2473impl<T> DFA<T> {
2474    /// Set or unset the prefilter attached to this DFA.
2475    ///
2476    /// This is useful when one has deserialized a DFA from `&[u8]`.
2477    /// Deserialization does not currently include prefilters, so if you
2478    /// want prefilter acceleration, you'll need to rebuild it and attach
2479    /// it here.
2480    pub fn set_prefilter(&mut self, prefilter: Option<Prefilter>) {
2481        self.pre = prefilter
2482    }
2483}
2484
2485// The following methods implement mutable routines on the internal
2486// representation of a DFA. As such, we must fix the first type parameter to a
2487// `Vec<u32>` since a generic `T: AsRef<[u32]>` does not permit mutation. We
2488// can get away with this because these methods are internal to the crate and
2489// are exclusively used during construction of the DFA.
2490#[cfg(feature = "dfa-build")]
2491impl OwnedDFA {
2492    /// Add a start state of this DFA.
2493    pub(crate) fn set_start_state(
2494        &mut self,
2495        anchored: Anchored,
2496        start: Start,
2497        id: StateID,
2498    ) {
2499        assert!(self.tt.is_valid(id), "invalid start state");
2500        self.st.set_start(anchored, start, id);
2501    }
2502
2503    /// Set the given transition to this DFA. Both the `from` and `to` states
2504    /// must already exist.
2505    pub(crate) fn set_transition(
2506        &mut self,
2507        from: StateID,
2508        byte: alphabet::Unit,
2509        to: StateID,
2510    ) {
2511        self.tt.set(from, byte, to);
2512    }
2513
2514    /// An empty state (a state where all transitions lead to a dead state)
2515    /// and return its identifier. The identifier returned is guaranteed to
2516    /// not point to any other existing state.
2517    ///
2518    /// If adding a state would exceed `StateID::LIMIT`, then this returns an
2519    /// error.
2520    pub(crate) fn add_empty_state(&mut self) -> Result<StateID, BuildError> {
2521        self.tt.add_empty_state()
2522    }
2523
2524    /// Swap the two states given in the transition table.
2525    ///
2526    /// This routine does not do anything to check the correctness of this
2527    /// swap. Callers must ensure that other states pointing to id1 and id2 are
2528    /// updated appropriately.
2529    pub(crate) fn swap_states(&mut self, id1: StateID, id2: StateID) {
2530        self.tt.swap(id1, id2);
2531    }
2532
2533    /// Remap all of the state identifiers in this DFA according to the map
2534    /// function given. This includes all transitions and all starting state
2535    /// identifiers.
2536    pub(crate) fn remap(&mut self, map: impl Fn(StateID) -> StateID) {
2537        // We could loop over each state ID and call 'remap_state' here, but
2538        // this is more direct: just map every transition directly. This
2539        // technically might do a little extra work since the alphabet length
2540        // is likely less than the stride, but if that is indeed an issue we
2541        // should benchmark it and fix it.
2542        for sid in self.tt.table_mut().iter_mut() {
2543            *sid = map(*sid);
2544        }
2545        for sid in self.st.table_mut().iter_mut() {
2546            *sid = map(*sid);
2547        }
2548    }
2549
2550    /// Remap the transitions for the state given according to the function
2551    /// given. This applies the given map function to every transition in the
2552    /// given state and changes the transition in place to the result of the
2553    /// map function for that transition.
2554    pub(crate) fn remap_state(
2555        &mut self,
2556        id: StateID,
2557        map: impl Fn(StateID) -> StateID,
2558    ) {
2559        self.tt.remap(id, map);
2560    }
2561
2562    /// Truncate the states in this DFA to the given length.
2563    ///
2564    /// This routine does not do anything to check the correctness of this
2565    /// truncation. Callers must ensure that other states pointing to truncated
2566    /// states are updated appropriately.
2567    pub(crate) fn truncate_states(&mut self, len: usize) {
2568        self.tt.truncate(len);
2569    }
2570
2571    /// Minimize this DFA in place using Hopcroft's algorithm.
2572    pub(crate) fn minimize(&mut self) {
2573        Minimizer::new(self).run();
2574    }
2575
2576    /// Updates the match state pattern ID map to use the one provided.
2577    ///
2578    /// This is useful when it's convenient to manipulate matching states
2579    /// (and their corresponding pattern IDs) as a map. In particular, the
2580    /// representation used by a DFA for this map is not amenable to mutation,
2581    /// so if things need to be changed (like when shuffling states), it's
2582    /// often easier to work with the map form.
2583    pub(crate) fn set_pattern_map(
2584        &mut self,
2585        map: &BTreeMap<StateID, Vec<PatternID>>,
2586    ) -> Result<(), BuildError> {
2587        self.ms = self.ms.new_with_map(map)?;
2588        Ok(())
2589    }
2590
2591    /// Find states that have a small number of non-loop transitions and mark
2592    /// them as candidates for acceleration during search.
2593    pub(crate) fn accelerate(&mut self) {
2594        // dead and quit states can never be accelerated.
2595        if self.state_len() <= 2 {
2596            return;
2597        }
2598
2599        // Go through every state and record their accelerator, if possible.
2600        let mut accels = BTreeMap::new();
2601        // Count the number of accelerated match, start and non-match/start
2602        // states.
2603        let (mut cmatch, mut cstart, mut cnormal) = (0, 0, 0);
2604        for state in self.states() {
2605            if let Some(accel) = state.accelerate(self.byte_classes()) {
2606                debug!(
2607                    "accelerating full DFA state {}: {:?}",
2608                    state.id().as_usize(),
2609                    accel,
2610                );
2611                accels.insert(state.id(), accel);
2612                if self.is_match_state(state.id()) {
2613                    cmatch += 1;
2614                } else if self.is_start_state(state.id()) {
2615                    cstart += 1;
2616                } else {
2617                    assert!(!self.is_dead_state(state.id()));
2618                    assert!(!self.is_quit_state(state.id()));
2619                    cnormal += 1;
2620                }
2621            }
2622        }
2623        // If no states were able to be accelerated, then we're done.
2624        if accels.is_empty() {
2625            return;
2626        }
2627        let original_accels_len = accels.len();
2628
2629        // A remapper keeps track of state ID changes. Once we're done
2630        // shuffling, the remapper is used to rewrite all transitions in the
2631        // DFA based on the new positions of states.
2632        let mut remapper = Remapper::new(self);
2633
2634        // As we swap states, if they are match states, we need to swap their
2635        // pattern ID lists too (for multi-regexes). We do this by converting
2636        // the lists to an easily swappable map, and then convert back to
2637        // MatchStates once we're done.
2638        let mut new_matches = self.ms.to_map(self);
2639
2640        // There is at least one state that gets accelerated, so these are
2641        // guaranteed to get set to sensible values below.
2642        self.special.min_accel = StateID::MAX;
2643        self.special.max_accel = StateID::ZERO;
2644        let update_special_accel =
2645            |special: &mut Special, accel_id: StateID| {
2646                special.min_accel = cmp::min(special.min_accel, accel_id);
2647                special.max_accel = cmp::max(special.max_accel, accel_id);
2648            };
2649
2650        // Start by shuffling match states. Any match states that are
2651        // accelerated get moved to the end of the match state range.
2652        if cmatch > 0 && self.special.matches() {
2653            // N.B. special.{min,max}_match do not need updating, since the
2654            // range/number of match states does not change. Only the ordering
2655            // of match states may change.
2656            let mut next_id = self.special.max_match;
2657            let mut cur_id = next_id;
2658            while cur_id >= self.special.min_match {
2659                if let Some(accel) = accels.remove(&cur_id) {
2660                    accels.insert(next_id, accel);
2661                    update_special_accel(&mut self.special, next_id);
2662
2663                    // No need to do any actual swapping for equivalent IDs.
2664                    if cur_id != next_id {
2665                        remapper.swap(self, cur_id, next_id);
2666
2667                        // Swap pattern IDs for match states.
2668                        let cur_pids = new_matches.remove(&cur_id).unwrap();
2669                        let next_pids = new_matches.remove(&next_id).unwrap();
2670                        new_matches.insert(cur_id, next_pids);
2671                        new_matches.insert(next_id, cur_pids);
2672                    }
2673                    next_id = self.tt.prev_state_id(next_id);
2674                }
2675                cur_id = self.tt.prev_state_id(cur_id);
2676            }
2677        }
2678
2679        // This is where it gets tricky. Without acceleration, start states
2680        // normally come right after match states. But we want accelerated
2681        // states to be a single contiguous range (to make it very fast
2682        // to determine whether a state *is* accelerated), while also keeping
2683        // match and starting states as contiguous ranges for the same reason.
2684        // So what we do here is shuffle states such that it looks like this:
2685        //
2686        //     DQMMMMAAAAASSSSSSNNNNNNN
2687        //         |         |
2688        //         |---------|
2689        //      accelerated states
2690        //
2691        // Where:
2692        //   D - dead state
2693        //   Q - quit state
2694        //   M - match state (may be accelerated)
2695        //   A - normal state that is accelerated
2696        //   S - start state (may be accelerated)
2697        //   N - normal state that is NOT accelerated
2698        //
2699        // We implement this by shuffling states, which is done by a sequence
2700        // of pairwise swaps. We start by looking at all normal states to be
2701        // accelerated. When we find one, we swap it with the earliest starting
2702        // state, and then swap that with the earliest normal state. This
2703        // preserves the contiguous property.
2704        //
2705        // Once we're done looking for accelerated normal states, now we look
2706        // for accelerated starting states by moving them to the beginning
2707        // of the starting state range (just like we moved accelerated match
2708        // states to the end of the matching state range).
2709        //
2710        // For a more detailed/different perspective on this, see the docs
2711        // in dfa/special.rs.
2712        if cnormal > 0 {
2713            // our next available starting and normal states for swapping.
2714            let mut next_start_id = self.special.min_start;
2715            let mut cur_id = self.to_state_id(self.state_len() - 1);
2716            // This is guaranteed to exist since cnormal > 0.
2717            let mut next_norm_id =
2718                self.tt.next_state_id(self.special.max_start);
2719            while cur_id >= next_norm_id {
2720                if let Some(accel) = accels.remove(&cur_id) {
2721                    remapper.swap(self, next_start_id, cur_id);
2722                    remapper.swap(self, next_norm_id, cur_id);
2723                    // Keep our accelerator map updated with new IDs if the
2724                    // states we swapped were also accelerated.
2725                    if let Some(accel2) = accels.remove(&next_norm_id) {
2726                        accels.insert(cur_id, accel2);
2727                    }
2728                    if let Some(accel2) = accels.remove(&next_start_id) {
2729                        accels.insert(next_norm_id, accel2);
2730                    }
2731                    accels.insert(next_start_id, accel);
2732                    update_special_accel(&mut self.special, next_start_id);
2733                    // Our start range shifts one to the right now.
2734                    self.special.min_start =
2735                        self.tt.next_state_id(self.special.min_start);
2736                    self.special.max_start =
2737                        self.tt.next_state_id(self.special.max_start);
2738                    next_start_id = self.tt.next_state_id(next_start_id);
2739                    next_norm_id = self.tt.next_state_id(next_norm_id);
2740                }
2741                // This is pretty tricky, but if our 'next_norm_id' state also
2742                // happened to be accelerated, then the result is that it is
2743                // now in the position of cur_id, so we need to consider it
2744                // again. This loop is still guaranteed to terminate though,
2745                // because when accels contains cur_id, we're guaranteed to
2746                // increment next_norm_id even if cur_id remains unchanged.
2747                if !accels.contains_key(&cur_id) {
2748                    cur_id = self.tt.prev_state_id(cur_id);
2749                }
2750            }
2751        }
2752        // Just like we did for match states, but we want to move accelerated
2753        // start states to the beginning of the range instead of the end.
2754        if cstart > 0 {
2755            // N.B. special.{min,max}_start do not need updating, since the
2756            // range/number of start states does not change at this point. Only
2757            // the ordering of start states may change.
2758            let mut next_id = self.special.min_start;
2759            let mut cur_id = next_id;
2760            while cur_id <= self.special.max_start {
2761                if let Some(accel) = accels.remove(&cur_id) {
2762                    remapper.swap(self, cur_id, next_id);
2763                    accels.insert(next_id, accel);
2764                    update_special_accel(&mut self.special, next_id);
2765                    next_id = self.tt.next_state_id(next_id);
2766                }
2767                cur_id = self.tt.next_state_id(cur_id);
2768            }
2769        }
2770
2771        // Remap all transitions in our DFA and assert some things.
2772        remapper.remap(self);
2773        // This unwrap is OK because acceleration never changes the number of
2774        // match states or patterns in those match states. Since acceleration
2775        // runs after the pattern map has been set at least once, we know that
2776        // our match states cannot error.
2777        self.set_pattern_map(&new_matches).unwrap();
2778        self.special.set_max();
2779        self.special.validate().expect("special state ranges should validate");
2780        self.special
2781            .validate_state_len(self.state_len(), self.stride2())
2782            .expect(
2783                "special state ranges should be consistent with state length",
2784            );
2785        assert_eq!(
2786            self.special.accel_len(self.stride()),
2787            // We record the number of accelerated states initially detected
2788            // since the accels map is itself mutated in the process above.
2789            // If mutated incorrectly, its size may change, and thus can't be
2790            // trusted as a source of truth of how many accelerated states we
2791            // expected there to be.
2792            original_accels_len,
2793            "mismatch with expected number of accelerated states",
2794        );
2795
2796        // And finally record our accelerators. We kept our accels map updated
2797        // as we shuffled states above, so the accelerators should now
2798        // correspond to a contiguous range in the state ID space. (Which we
2799        // assert.)
2800        let mut prev: Option<StateID> = None;
2801        for (id, accel) in accels {
2802            assert!(prev.map_or(true, |p| self.tt.next_state_id(p) == id));
2803            prev = Some(id);
2804            self.accels.add(accel);
2805        }
2806    }
2807
2808    /// Shuffle the states in this DFA so that starting states, match
2809    /// states and accelerated states are all contiguous.
2810    ///
2811    /// See dfa/special.rs for more details.
2812    pub(crate) fn shuffle(
2813        &mut self,
2814        mut matches: BTreeMap<StateID, Vec<PatternID>>,
2815    ) -> Result<(), BuildError> {
2816        // The determinizer always adds a quit state and it is always second.
2817        self.special.quit_id = self.to_state_id(1);
2818        // If all we have are the dead and quit states, then we're done and
2819        // the DFA will never produce a match.
2820        if self.state_len() <= 2 {
2821            self.special.set_max();
2822            return Ok(());
2823        }
2824
2825        // Collect all our non-DEAD start states into a convenient set and
2826        // confirm there is no overlap with match states. In the classical DFA
2827        // construction, start states can be match states. But because of
2828        // look-around, we delay all matches by a byte, which prevents start
2829        // states from being match states.
2830        let mut is_start: BTreeSet<StateID> = BTreeSet::new();
2831        for (start_id, _, _) in self.starts() {
2832            // If a starting configuration points to a DEAD state, then we
2833            // don't want to shuffle it. The DEAD state is always the first
2834            // state with ID=0. So we can just leave it be.
2835            if start_id == DEAD {
2836                continue;
2837            }
2838            assert!(
2839                !matches.contains_key(&start_id),
2840                "{:?} is both a start and a match state, which is not allowed",
2841                start_id,
2842            );
2843            is_start.insert(start_id);
2844        }
2845
2846        // We implement shuffling by a sequence of pairwise swaps of states.
2847        // Since we have a number of things referencing states via their
2848        // IDs and swapping them changes their IDs, we need to record every
2849        // swap we make so that we can remap IDs. The remapper handles this
2850        // book-keeping for us.
2851        let mut remapper = Remapper::new(self);
2852
2853        // Shuffle matching states.
2854        if matches.is_empty() {
2855            self.special.min_match = DEAD;
2856            self.special.max_match = DEAD;
2857        } else {
2858            // The determinizer guarantees that the first two states are the
2859            // dead and quit states, respectively. We want our match states to
2860            // come right after quit.
2861            let mut next_id = self.to_state_id(2);
2862            let mut new_matches = BTreeMap::new();
2863            self.special.min_match = next_id;
2864            for (id, pids) in matches {
2865                remapper.swap(self, next_id, id);
2866                new_matches.insert(next_id, pids);
2867                // If we swapped a start state, then update our set.
2868                if is_start.contains(&next_id) {
2869                    is_start.remove(&next_id);
2870                    is_start.insert(id);
2871                }
2872                next_id = self.tt.next_state_id(next_id);
2873            }
2874            matches = new_matches;
2875            self.special.max_match = cmp::max(
2876                self.special.min_match,
2877                self.tt.prev_state_id(next_id),
2878            );
2879        }
2880
2881        // Shuffle starting states.
2882        {
2883            let mut next_id = self.to_state_id(2);
2884            if self.special.matches() {
2885                next_id = self.tt.next_state_id(self.special.max_match);
2886            }
2887            self.special.min_start = next_id;
2888            for id in is_start {
2889                remapper.swap(self, next_id, id);
2890                next_id = self.tt.next_state_id(next_id);
2891            }
2892            self.special.max_start = cmp::max(
2893                self.special.min_start,
2894                self.tt.prev_state_id(next_id),
2895            );
2896        }
2897
2898        // Finally remap all transitions in our DFA.
2899        remapper.remap(self);
2900        self.set_pattern_map(&matches)?;
2901        self.special.set_max();
2902        self.special.validate().expect("special state ranges should validate");
2903        self.special
2904            .validate_state_len(self.state_len(), self.stride2())
2905            .expect(
2906                "special state ranges should be consistent with state length",
2907            );
2908        Ok(())
2909    }
2910
2911    /// Checks whether there are universal start states (both anchored and
2912    /// unanchored), and if so, sets the relevant fields to the start state
2913    /// IDs.
2914    ///
2915    /// Universal start states occur precisely when the all patterns in the
2916    /// DFA have no look-around assertions in their prefix.
2917    fn set_universal_starts(&mut self) {
2918        assert_eq!(6, Start::len(), "expected 6 start configurations");
2919
2920        let start_id = |dfa: &mut OwnedDFA,
2921                        anchored: Anchored,
2922                        start: Start| {
2923            // This OK because we only call 'start' under conditions
2924            // in which we know it will succeed.
2925            dfa.st.start(anchored, start).expect("valid Input configuration")
2926        };
2927        if self.start_kind().has_unanchored() {
2928            let anchor = Anchored::No;
2929            let sid = start_id(self, anchor, Start::NonWordByte);
2930            if sid == start_id(self, anchor, Start::WordByte)
2931                && sid == start_id(self, anchor, Start::Text)
2932                && sid == start_id(self, anchor, Start::LineLF)
2933                && sid == start_id(self, anchor, Start::LineCR)
2934                && sid == start_id(self, anchor, Start::CustomLineTerminator)
2935            {
2936                self.st.universal_start_unanchored = Some(sid);
2937            }
2938        }
2939        if self.start_kind().has_anchored() {
2940            let anchor = Anchored::Yes;
2941            let sid = start_id(self, anchor, Start::NonWordByte);
2942            if sid == start_id(self, anchor, Start::WordByte)
2943                && sid == start_id(self, anchor, Start::Text)
2944                && sid == start_id(self, anchor, Start::LineLF)
2945                && sid == start_id(self, anchor, Start::LineCR)
2946                && sid == start_id(self, anchor, Start::CustomLineTerminator)
2947            {
2948                self.st.universal_start_anchored = Some(sid);
2949            }
2950        }
2951    }
2952}
2953
2954// A variety of generic internal methods for accessing DFA internals.
2955impl<T: AsRef<[u32]>> DFA<T> {
2956    /// Return the info about special states.
2957    pub(crate) fn special(&self) -> &Special {
2958        &self.special
2959    }
2960
2961    /// Return the info about special states as a mutable borrow.
2962    #[cfg(feature = "dfa-build")]
2963    pub(crate) fn special_mut(&mut self) -> &mut Special {
2964        &mut self.special
2965    }
2966
2967    /// Returns the quit set (may be empty) used by this DFA.
2968    pub(crate) fn quitset(&self) -> &ByteSet {
2969        &self.quitset
2970    }
2971
2972    /// Returns the flags for this DFA.
2973    pub(crate) fn flags(&self) -> &Flags {
2974        &self.flags
2975    }
2976
2977    /// Returns an iterator over all states in this DFA.
2978    ///
2979    /// This iterator yields a tuple for each state. The first element of the
2980    /// tuple corresponds to a state's identifier, and the second element
2981    /// corresponds to the state itself (comprised of its transitions).
2982    pub(crate) fn states(&self) -> StateIter<'_, T> {
2983        self.tt.states()
2984    }
2985
2986    /// Return the total number of states in this DFA. Every DFA has at least
2987    /// 1 state, even the empty DFA.
2988    pub(crate) fn state_len(&self) -> usize {
2989        self.tt.len()
2990    }
2991
2992    /// Return an iterator over all pattern IDs for the given match state.
2993    ///
2994    /// If the given state is not a match state, then this panics.
2995    #[cfg(feature = "dfa-build")]
2996    pub(crate) fn pattern_id_slice(&self, id: StateID) -> &[PatternID] {
2997        assert!(self.is_match_state(id));
2998        self.ms.pattern_id_slice(self.match_state_index(id))
2999    }
3000
3001    /// Return the total number of pattern IDs for the given match state.
3002    ///
3003    /// If the given state is not a match state, then this panics.
3004    pub(crate) fn match_pattern_len(&self, id: StateID) -> usize {
3005        assert!(self.is_match_state(id));
3006        self.ms.pattern_len(self.match_state_index(id))
3007    }
3008
3009    /// Returns the total number of patterns matched by this DFA.
3010    pub(crate) fn pattern_len(&self) -> usize {
3011        self.ms.pattern_len
3012    }
3013
3014    /// Returns a map from match state ID to a list of pattern IDs that match
3015    /// in that state.
3016    #[cfg(feature = "dfa-build")]
3017    pub(crate) fn pattern_map(&self) -> BTreeMap<StateID, Vec<PatternID>> {
3018        self.ms.to_map(self)
3019    }
3020
3021    /// Returns the ID of the quit state for this DFA.
3022    #[cfg(feature = "dfa-build")]
3023    pub(crate) fn quit_id(&self) -> StateID {
3024        self.to_state_id(1)
3025    }
3026
3027    /// Convert the given state identifier to the state's index. The state's
3028    /// index corresponds to the position in which it appears in the transition
3029    /// table. When a DFA is NOT premultiplied, then a state's identifier is
3030    /// also its index. When a DFA is premultiplied, then a state's identifier
3031    /// is equal to `index * alphabet_len`. This routine reverses that.
3032    pub(crate) fn to_index(&self, id: StateID) -> usize {
3033        self.tt.to_index(id)
3034    }
3035
3036    /// Convert an index to a state (in the range 0..self.state_len()) to an
3037    /// actual state identifier.
3038    ///
3039    /// This is useful when using a `Vec<T>` as an efficient map keyed by state
3040    /// to some other information (such as a remapped state ID).
3041    #[cfg(feature = "dfa-build")]
3042    pub(crate) fn to_state_id(&self, index: usize) -> StateID {
3043        self.tt.to_state_id(index)
3044    }
3045
3046    /// Return the table of state IDs for this DFA's start states.
3047    pub(crate) fn starts(&self) -> StartStateIter<'_> {
3048        self.st.iter()
3049    }
3050
3051    /// Returns the index of the match state for the given ID. If the
3052    /// given ID does not correspond to a match state, then this may
3053    /// panic or produce an incorrect result.
3054    #[cfg_attr(feature = "perf-inline", inline(always))]
3055    fn match_state_index(&self, id: StateID) -> usize {
3056        debug_assert!(self.is_match_state(id));
3057        // This is one of the places where we rely on the fact that match
3058        // states are contiguous in the transition table. Namely, that the
3059        // first match state ID always corresponds to dfa.special.min_match.
3060        // From there, since we know the stride, we can compute the overall
3061        // index of any match state given the match state's ID.
3062        let min = self.special().min_match.as_usize();
3063        // CORRECTNESS: We're allowed to produce an incorrect result or panic,
3064        // so both the subtraction and the unchecked StateID construction is
3065        // OK.
3066        self.to_index(StateID::new_unchecked(id.as_usize() - min))
3067    }
3068
3069    /// Returns the index of the accelerator state for the given ID. If the
3070    /// given ID does not correspond to an accelerator state, then this may
3071    /// panic or produce an incorrect result.
3072    fn accelerator_index(&self, id: StateID) -> usize {
3073        let min = self.special().min_accel.as_usize();
3074        // CORRECTNESS: We're allowed to produce an incorrect result or panic,
3075        // so both the subtraction and the unchecked StateID construction is
3076        // OK.
3077        self.to_index(StateID::new_unchecked(id.as_usize() - min))
3078    }
3079
3080    /// Return the accelerators for this DFA.
3081    fn accels(&self) -> Accels<&[u32]> {
3082        self.accels.as_ref()
3083    }
3084
3085    /// Return this DFA's transition table as a slice.
3086    fn trans(&self) -> &[StateID] {
3087        self.tt.table()
3088    }
3089}
3090
3091impl<T: AsRef<[u32]>> fmt::Debug for DFA<T> {
3092    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3093        writeln!(f, "dense::DFA(")?;
3094        for state in self.states() {
3095            fmt_state_indicator(f, self, state.id())?;
3096            let id = if f.alternate() {
3097                state.id().as_usize()
3098            } else {
3099                self.to_index(state.id())
3100            };
3101            write!(f, "{:06?}: ", id)?;
3102            state.fmt(f)?;
3103            write!(f, "\n")?;
3104        }
3105        writeln!(f, "")?;
3106        for (i, (start_id, anchored, sty)) in self.starts().enumerate() {
3107            let id = if f.alternate() {
3108                start_id.as_usize()
3109            } else {
3110                self.to_index(start_id)
3111            };
3112            if i % self.st.stride == 0 {
3113                match anchored {
3114                    Anchored::No => writeln!(f, "START-GROUP(unanchored)")?,
3115                    Anchored::Yes => writeln!(f, "START-GROUP(anchored)")?,
3116                    Anchored::Pattern(pid) => {
3117                        writeln!(f, "START_GROUP(pattern: {:?})", pid)?
3118                    }
3119                }
3120            }
3121            writeln!(f, "  {:?} => {:06?}", sty, id)?;
3122        }
3123        if self.pattern_len() > 1 {
3124            writeln!(f, "")?;
3125            for i in 0..self.ms.len() {
3126                let id = self.ms.match_state_id(self, i);
3127                let id = if f.alternate() {
3128                    id.as_usize()
3129                } else {
3130                    self.to_index(id)
3131                };
3132                write!(f, "MATCH({:06?}): ", id)?;
3133                for (i, &pid) in self.ms.pattern_id_slice(i).iter().enumerate()
3134                {
3135                    if i > 0 {
3136                        write!(f, ", ")?;
3137                    }
3138                    write!(f, "{:?}", pid)?;
3139                }
3140                writeln!(f, "")?;
3141            }
3142        }
3143        writeln!(f, "state length: {:?}", self.state_len())?;
3144        writeln!(f, "pattern length: {:?}", self.pattern_len())?;
3145        writeln!(f, "flags: {:?}", self.flags)?;
3146        writeln!(f, ")")?;
3147        Ok(())
3148    }
3149}
3150
3151// SAFETY: We assert that our implementation of each method is correct.
3152unsafe impl<T: AsRef<[u32]>> Automaton for DFA<T> {
3153    #[cfg_attr(feature = "perf-inline", inline(always))]
3154    fn is_special_state(&self, id: StateID) -> bool {
3155        self.special.is_special_state(id)
3156    }
3157
3158    #[cfg_attr(feature = "perf-inline", inline(always))]
3159    fn is_dead_state(&self, id: StateID) -> bool {
3160        self.special.is_dead_state(id)
3161    }
3162
3163    #[cfg_attr(feature = "perf-inline", inline(always))]
3164    fn is_quit_state(&self, id: StateID) -> bool {
3165        self.special.is_quit_state(id)
3166    }
3167
3168    #[cfg_attr(feature = "perf-inline", inline(always))]
3169    fn is_match_state(&self, id: StateID) -> bool {
3170        self.special.is_match_state(id)
3171    }
3172
3173    #[cfg_attr(feature = "perf-inline", inline(always))]
3174    fn is_start_state(&self, id: StateID) -> bool {
3175        self.special.is_start_state(id)
3176    }
3177
3178    #[cfg_attr(feature = "perf-inline", inline(always))]
3179    fn is_accel_state(&self, id: StateID) -> bool {
3180        self.special.is_accel_state(id)
3181    }
3182
3183    #[cfg_attr(feature = "perf-inline", inline(always))]
3184    fn next_state(&self, current: StateID, input: u8) -> StateID {
3185        let input = self.byte_classes().get(input);
3186        let o = current.as_usize() + usize::from(input);
3187        self.trans()[o]
3188    }
3189
3190    #[cfg_attr(feature = "perf-inline", inline(always))]
3191    unsafe fn next_state_unchecked(
3192        &self,
3193        current: StateID,
3194        byte: u8,
3195    ) -> StateID {
3196        // We don't (or shouldn't) need an unchecked variant for the byte
3197        // class mapping, since bound checks should be omitted automatically
3198        // by virtue of its representation. If this ends up not being true as
3199        // confirmed by codegen, please file an issue. ---AG
3200        let class = self.byte_classes().get(byte);
3201        let o = current.as_usize() + usize::from(class);
3202        let next = *self.trans().get_unchecked(o);
3203        next
3204    }
3205
3206    #[cfg_attr(feature = "perf-inline", inline(always))]
3207    fn next_eoi_state(&self, current: StateID) -> StateID {
3208        let eoi = self.byte_classes().eoi().as_usize();
3209        let o = current.as_usize() + eoi;
3210        self.trans()[o]
3211    }
3212
3213    #[cfg_attr(feature = "perf-inline", inline(always))]
3214    fn pattern_len(&self) -> usize {
3215        self.ms.pattern_len
3216    }
3217
3218    #[cfg_attr(feature = "perf-inline", inline(always))]
3219    fn match_len(&self, id: StateID) -> usize {
3220        self.match_pattern_len(id)
3221    }
3222
3223    #[cfg_attr(feature = "perf-inline", inline(always))]
3224    fn match_pattern(&self, id: StateID, match_index: usize) -> PatternID {
3225        // This is an optimization for the very common case of a DFA with a
3226        // single pattern. This conditional avoids a somewhat more costly path
3227        // that finds the pattern ID from the state machine, which requires
3228        // a bit of slicing/pointer-chasing. This optimization tends to only
3229        // matter when matches are frequent.
3230        if self.ms.pattern_len == 1 {
3231            return PatternID::ZERO;
3232        }
3233        let state_index = self.match_state_index(id);
3234        self.ms.pattern_id(state_index, match_index)
3235    }
3236
3237    #[cfg_attr(feature = "perf-inline", inline(always))]
3238    fn has_empty(&self) -> bool {
3239        self.flags.has_empty
3240    }
3241
3242    #[cfg_attr(feature = "perf-inline", inline(always))]
3243    fn is_utf8(&self) -> bool {
3244        self.flags.is_utf8
3245    }
3246
3247    #[cfg_attr(feature = "perf-inline", inline(always))]
3248    fn is_always_start_anchored(&self) -> bool {
3249        self.flags.is_always_start_anchored
3250    }
3251
3252    #[cfg_attr(feature = "perf-inline", inline(always))]
3253    fn start_state(
3254        &self,
3255        config: &start::Config,
3256    ) -> Result<StateID, StartError> {
3257        let anchored = config.get_anchored();
3258        let start = match config.get_look_behind() {
3259            None => Start::Text,
3260            Some(byte) => {
3261                if !self.quitset.is_empty() && self.quitset.contains(byte) {
3262                    return Err(StartError::quit(byte));
3263                }
3264                self.st.start_map.get(byte)
3265            }
3266        };
3267        self.st.start(anchored, start)
3268    }
3269
3270    #[cfg_attr(feature = "perf-inline", inline(always))]
3271    fn universal_start_state(&self, mode: Anchored) -> Option<StateID> {
3272        match mode {
3273            Anchored::No => self.st.universal_start_unanchored,
3274            Anchored::Yes => self.st.universal_start_anchored,
3275            Anchored::Pattern(_) => None,
3276        }
3277    }
3278
3279    #[cfg_attr(feature = "perf-inline", inline(always))]
3280    fn accelerator(&self, id: StateID) -> &[u8] {
3281        if !self.is_accel_state(id) {
3282            return &[];
3283        }
3284        self.accels.needles(self.accelerator_index(id))
3285    }
3286
3287    #[cfg_attr(feature = "perf-inline", inline(always))]
3288    fn get_prefilter(&self) -> Option<&Prefilter> {
3289        self.pre.as_ref()
3290    }
3291}
3292
3293/// The transition table portion of a dense DFA.
3294///
3295/// The transition table is the core part of the DFA in that it describes how
3296/// to move from one state to another based on the input sequence observed.
3297#[derive(Clone)]
3298pub(crate) struct TransitionTable<T> {
3299    /// A contiguous region of memory representing the transition table in
3300    /// row-major order. The representation is dense. That is, every state
3301    /// has precisely the same number of transitions. The maximum number of
3302    /// transitions per state is 257 (256 for each possible byte value, plus 1
3303    /// for the special EOI transition). If a DFA has been instructed to use
3304    /// byte classes (the default), then the number of transitions is usually
3305    /// substantially fewer.
3306    ///
3307    /// In practice, T is either `Vec<u32>` or `&[u32]`.
3308    table: T,
3309    /// A set of equivalence classes, where a single equivalence class
3310    /// represents a set of bytes that never discriminate between a match
3311    /// and a non-match in the DFA. Each equivalence class corresponds to a
3312    /// single character in this DFA's alphabet, where the maximum number of
3313    /// characters is 257 (each possible value of a byte plus the special
3314    /// EOI transition). Consequently, the number of equivalence classes
3315    /// corresponds to the number of transitions for each DFA state. Note
3316    /// though that the *space* used by each DFA state in the transition table
3317    /// may be larger. The total space used by each DFA state is known as the
3318    /// stride.
3319    ///
3320    /// The only time the number of equivalence classes is fewer than 257 is if
3321    /// the DFA's kind uses byte classes (which is the default). Equivalence
3322    /// classes should generally only be disabled when debugging, so that
3323    /// the transitions themselves aren't obscured. Disabling them has no
3324    /// other benefit, since the equivalence class map is always used while
3325    /// searching. In the vast majority of cases, the number of equivalence
3326    /// classes is substantially smaller than 257, particularly when large
3327    /// Unicode classes aren't used.
3328    classes: ByteClasses,
3329    /// The stride of each DFA state, expressed as a power-of-two exponent.
3330    ///
3331    /// The stride of a DFA corresponds to the total amount of space used by
3332    /// each DFA state in the transition table. This may be bigger than the
3333    /// size of a DFA's alphabet, since the stride is always the smallest
3334    /// power of two greater than or equal to the alphabet size.
3335    ///
3336    /// While this wastes space, this avoids the need for integer division
3337    /// to convert between premultiplied state IDs and their corresponding
3338    /// indices. Instead, we can use simple bit-shifts.
3339    ///
3340    /// See the docs for the `stride2` method for more details.
3341    ///
3342    /// The minimum `stride2` value is `1` (corresponding to a stride of `2`)
3343    /// while the maximum `stride2` value is `9` (corresponding to a stride of
3344    /// `512`). The maximum is not `8` since the maximum alphabet size is `257`
3345    /// when accounting for the special EOI transition. However, an alphabet
3346    /// length of that size is exceptionally rare since the alphabet is shrunk
3347    /// into equivalence classes.
3348    stride2: usize,
3349}
3350
3351impl<'a> TransitionTable<&'a [u32]> {
3352    /// Deserialize a transition table starting at the beginning of `slice`.
3353    /// Upon success, return the total number of bytes read along with the
3354    /// transition table.
3355    ///
3356    /// If there was a problem deserializing any part of the transition table,
3357    /// then this returns an error. Notably, if the given slice does not have
3358    /// the same alignment as `StateID`, then this will return an error (among
3359    /// other possible errors).
3360    ///
3361    /// This is guaranteed to execute in constant time.
3362    ///
3363    /// # Safety
3364    ///
3365    /// This routine is not safe because it does not check the validity of the
3366    /// transition table itself. In particular, the transition table can be
3367    /// quite large, so checking its validity can be somewhat expensive. An
3368    /// invalid transition table is not safe because other code may rely on the
3369    /// transition table being correct (such as explicit bounds check elision).
3370    /// Therefore, an invalid transition table can lead to undefined behavior.
3371    ///
3372    /// Callers that use this function must either pass on the safety invariant
3373    /// or guarantee that the bytes given contain a valid transition table.
3374    /// This guarantee is upheld by the bytes written by `write_to`.
3375    unsafe fn from_bytes_unchecked(
3376        mut slice: &'a [u8],
3377    ) -> Result<(TransitionTable<&'a [u32]>, usize), DeserializeError> {
3378        let slice_start = slice.as_ptr().as_usize();
3379
3380        let (state_len, nr) =
3381            wire::try_read_u32_as_usize(slice, "state length")?;
3382        slice = &slice[nr..];
3383
3384        let (stride2, nr) = wire::try_read_u32_as_usize(slice, "stride2")?;
3385        slice = &slice[nr..];
3386
3387        let (classes, nr) = ByteClasses::from_bytes(slice)?;
3388        slice = &slice[nr..];
3389
3390        // The alphabet length (determined by the byte class map) cannot be
3391        // bigger than the stride (total space used by each DFA state).
3392        if stride2 > 9 {
3393            return Err(DeserializeError::generic(
3394                "dense DFA has invalid stride2 (too big)",
3395            ));
3396        }
3397        // It also cannot be zero, since even a DFA that never matches anything
3398        // has a non-zero number of states with at least two equivalence
3399        // classes: one for all 256 byte values and another for the EOI
3400        // sentinel.
3401        if stride2 < 1 {
3402            return Err(DeserializeError::generic(
3403                "dense DFA has invalid stride2 (too small)",
3404            ));
3405        }
3406        // This is OK since 1 <= stride2 <= 9.
3407        let stride =
3408            1usize.checked_shl(u32::try_from(stride2).unwrap()).unwrap();
3409        if classes.alphabet_len() > stride {
3410            return Err(DeserializeError::generic(
3411                "alphabet size cannot be bigger than transition table stride",
3412            ));
3413        }
3414
3415        let trans_len =
3416            wire::shl(state_len, stride2, "dense table transition length")?;
3417        let table_bytes_len = wire::mul(
3418            trans_len,
3419            StateID::SIZE,
3420            "dense table state byte length",
3421        )?;
3422        wire::check_slice_len(slice, table_bytes_len, "transition table")?;
3423        wire::check_alignment::<StateID>(slice)?;
3424        let table_bytes = &slice[..table_bytes_len];
3425        slice = &slice[table_bytes_len..];
3426        // SAFETY: Since StateID is always representable as a u32, all we need
3427        // to do is ensure that we have the proper length and alignment. We've
3428        // checked both above, so the cast below is safe.
3429        //
3430        // N.B. This is the only not-safe code in this function.
3431        let table = core::slice::from_raw_parts(
3432            table_bytes.as_ptr().cast::<u32>(),
3433            trans_len,
3434        );
3435        let tt = TransitionTable { table, classes, stride2 };
3436        Ok((tt, slice.as_ptr().as_usize() - slice_start))
3437    }
3438}
3439
3440#[cfg(feature = "dfa-build")]
3441impl TransitionTable<Vec<u32>> {
3442    /// Create a minimal transition table with just two states: a dead state
3443    /// and a quit state. The alphabet length and stride of the transition
3444    /// table is determined by the given set of equivalence classes.
3445    fn minimal(classes: ByteClasses) -> TransitionTable<Vec<u32>> {
3446        let mut tt = TransitionTable {
3447            table: vec![],
3448            classes,
3449            stride2: classes.stride2(),
3450        };
3451        // Two states, regardless of alphabet size, can always fit into u32.
3452        tt.add_empty_state().unwrap(); // dead state
3453        tt.add_empty_state().unwrap(); // quit state
3454        tt
3455    }
3456
3457    /// Set a transition in this table. Both the `from` and `to` states must
3458    /// already exist, otherwise this panics. `unit` should correspond to the
3459    /// transition out of `from` to set to `to`.
3460    fn set(&mut self, from: StateID, unit: alphabet::Unit, to: StateID) {
3461        assert!(self.is_valid(from), "invalid 'from' state");
3462        assert!(self.is_valid(to), "invalid 'to' state");
3463        self.table[from.as_usize() + self.classes.get_by_unit(unit)] =
3464            to.as_u32();
3465    }
3466
3467    /// Add an empty state (a state where all transitions lead to a dead state)
3468    /// and return its identifier. The identifier returned is guaranteed to
3469    /// not point to any other existing state.
3470    ///
3471    /// If adding a state would exhaust the state identifier space, then this
3472    /// returns an error.
3473    fn add_empty_state(&mut self) -> Result<StateID, BuildError> {
3474        // Normally, to get a fresh state identifier, we would just
3475        // take the index of the next state added to the transition
3476        // table. However, we actually perform an optimization here
3477        // that pre-multiplies state IDs by the stride, such that they
3478        // point immediately at the beginning of their transitions in
3479        // the transition table. This avoids an extra multiplication
3480        // instruction for state lookup at search time.
3481        //
3482        // Premultiplied identifiers means that instead of your matching
3483        // loop looking something like this:
3484        //
3485        //   state = dfa.start
3486        //   for byte in haystack:
3487        //       next = dfa.transitions[state * stride + byte]
3488        //       if dfa.is_match(next):
3489        //           return true
3490        //   return false
3491        //
3492        // it can instead look like this:
3493        //
3494        //   state = dfa.start
3495        //   for byte in haystack:
3496        //       next = dfa.transitions[state + byte]
3497        //       if dfa.is_match(next):
3498        //           return true
3499        //   return false
3500        //
3501        // In other words, we save a multiplication instruction in the
3502        // critical path. This turns out to be a decent performance win.
3503        // The cost of using premultiplied state ids is that they can
3504        // require a bigger state id representation. (And they also make
3505        // the code a bit more complex, especially during minimization and
3506        // when reshuffling states, as one needs to convert back and forth
3507        // between state IDs and state indices.)
3508        //
3509        // To do this, we simply take the index of the state into the
3510        // entire transition table, rather than the index of the state
3511        // itself. e.g., If the stride is 64, then the ID of the 3rd state
3512        // is 192, not 2.
3513        let next = self.table.len();
3514        let id =
3515            StateID::new(next).map_err(|_| BuildError::too_many_states())?;
3516        self.table.extend(iter::repeat(0).take(self.stride()));
3517        Ok(id)
3518    }
3519
3520    /// Swap the two states given in this transition table.
3521    ///
3522    /// This routine does not do anything to check the correctness of this
3523    /// swap. Callers must ensure that other states pointing to id1 and id2 are
3524    /// updated appropriately.
3525    ///
3526    /// Both id1 and id2 must point to valid states, otherwise this panics.
3527    fn swap(&mut self, id1: StateID, id2: StateID) {
3528        assert!(self.is_valid(id1), "invalid 'id1' state: {:?}", id1);
3529        assert!(self.is_valid(id2), "invalid 'id2' state: {:?}", id2);
3530        // We only need to swap the parts of the state that are used. So if the
3531        // stride is 64, but the alphabet length is only 33, then we save a lot
3532        // of work.
3533        for b in 0..self.classes.alphabet_len() {
3534            self.table.swap(id1.as_usize() + b, id2.as_usize() + b);
3535        }
3536    }
3537
3538    /// Remap the transitions for the state given according to the function
3539    /// given. This applies the given map function to every transition in the
3540    /// given state and changes the transition in place to the result of the
3541    /// map function for that transition.
3542    fn remap(&mut self, id: StateID, map: impl Fn(StateID) -> StateID) {
3543        for byte in 0..self.alphabet_len() {
3544            let i = id.as_usize() + byte;
3545            let next = self.table()[i];
3546            self.table_mut()[id.as_usize() + byte] = map(next);
3547        }
3548    }
3549
3550    /// Truncate the states in this transition table to the given length.
3551    ///
3552    /// This routine does not do anything to check the correctness of this
3553    /// truncation. Callers must ensure that other states pointing to truncated
3554    /// states are updated appropriately.
3555    fn truncate(&mut self, len: usize) {
3556        self.table.truncate(len << self.stride2);
3557    }
3558}
3559
3560impl<T: AsRef<[u32]>> TransitionTable<T> {
3561    /// Writes a serialized form of this transition table to the buffer given.
3562    /// If the buffer is too small, then an error is returned. To determine
3563    /// how big the buffer must be, use `write_to_len`.
3564    fn write_to<E: Endian>(
3565        &self,
3566        mut dst: &mut [u8],
3567    ) -> Result<usize, SerializeError> {
3568        let nwrite = self.write_to_len();
3569        if dst.len() < nwrite {
3570            return Err(SerializeError::buffer_too_small("transition table"));
3571        }
3572        dst = &mut dst[..nwrite];
3573
3574        // write state length
3575        // Unwrap is OK since number of states is guaranteed to fit in a u32.
3576        E::write_u32(u32::try_from(self.len()).unwrap(), dst);
3577        dst = &mut dst[size_of::<u32>()..];
3578
3579        // write state stride (as power of 2)
3580        // Unwrap is OK since stride2 is guaranteed to be <= 9.
3581        E::write_u32(u32::try_from(self.stride2).unwrap(), dst);
3582        dst = &mut dst[size_of::<u32>()..];
3583
3584        // write byte class map
3585        let n = self.classes.write_to(dst)?;
3586        dst = &mut dst[n..];
3587
3588        // write actual transitions
3589        for &sid in self.table() {
3590            let n = wire::write_state_id::<E>(sid, &mut dst);
3591            dst = &mut dst[n..];
3592        }
3593        Ok(nwrite)
3594    }
3595
3596    /// Returns the number of bytes the serialized form of this transition
3597    /// table will use.
3598    fn write_to_len(&self) -> usize {
3599        size_of::<u32>()   // state length
3600        + size_of::<u32>() // stride2
3601        + self.classes.write_to_len()
3602        + (self.table().len() * StateID::SIZE)
3603    }
3604
3605    /// Validates that every state ID in this transition table is valid.
3606    ///
3607    /// That is, every state ID can be used to correctly index a state in this
3608    /// table.
3609    fn validate(&self, dfa: &DFA<T>) -> Result<(), DeserializeError> {
3610        let sp = &dfa.special;
3611        for state in self.states() {
3612            // We check that the ID itself is well formed. That is, if it's
3613            // a special state then it must actually be a quit, dead, accel,
3614            // match or start state.
3615            if sp.is_special_state(state.id()) {
3616                let is_actually_special = sp.is_dead_state(state.id())
3617                    || sp.is_quit_state(state.id())
3618                    || sp.is_match_state(state.id())
3619                    || sp.is_start_state(state.id())
3620                    || sp.is_accel_state(state.id());
3621                if !is_actually_special {
3622                    // This is kind of a cryptic error message...
3623                    return Err(DeserializeError::generic(
3624                        "found dense state tagged as special but \
3625                         wasn't actually special",
3626                    ));
3627                }
3628                if sp.is_match_state(state.id())
3629                    && dfa.match_len(state.id()) == 0
3630                {
3631                    return Err(DeserializeError::generic(
3632                        "found match state with zero pattern IDs",
3633                    ));
3634                }
3635            }
3636            for (_, to) in state.transitions() {
3637                if !self.is_valid(to) {
3638                    return Err(DeserializeError::generic(
3639                        "found invalid state ID in transition table",
3640                    ));
3641                }
3642            }
3643        }
3644        Ok(())
3645    }
3646
3647    /// Converts this transition table to a borrowed value.
3648    fn as_ref(&self) -> TransitionTable<&'_ [u32]> {
3649        TransitionTable {
3650            table: self.table.as_ref(),
3651            classes: self.classes.clone(),
3652            stride2: self.stride2,
3653        }
3654    }
3655
3656    /// Converts this transition table to an owned value.
3657    #[cfg(feature = "alloc")]
3658    fn to_owned(&self) -> TransitionTable<alloc::vec::Vec<u32>> {
3659        TransitionTable {
3660            table: self.table.as_ref().to_vec(),
3661            classes: self.classes.clone(),
3662            stride2: self.stride2,
3663        }
3664    }
3665
3666    /// Return the state for the given ID. If the given ID is not valid, then
3667    /// this panics.
3668    fn state(&self, id: StateID) -> State<'_> {
3669        assert!(self.is_valid(id));
3670
3671        let i = id.as_usize();
3672        State {
3673            id,
3674            stride2: self.stride2,
3675            transitions: &self.table()[i..i + self.alphabet_len()],
3676        }
3677    }
3678
3679    /// Returns an iterator over all states in this transition table.
3680    ///
3681    /// This iterator yields a tuple for each state. The first element of the
3682    /// tuple corresponds to a state's identifier, and the second element
3683    /// corresponds to the state itself (comprised of its transitions).
3684    fn states(&self) -> StateIter<'_, T> {
3685        StateIter {
3686            tt: self,
3687            it: self.table().chunks(self.stride()).enumerate(),
3688        }
3689    }
3690
3691    /// Convert a state identifier to an index to a state (in the range
3692    /// 0..self.len()).
3693    ///
3694    /// This is useful when using a `Vec<T>` as an efficient map keyed by state
3695    /// to some other information (such as a remapped state ID).
3696    ///
3697    /// If the given ID is not valid, then this may panic or produce an
3698    /// incorrect index.
3699    fn to_index(&self, id: StateID) -> usize {
3700        id.as_usize() >> self.stride2
3701    }
3702
3703    /// Convert an index to a state (in the range 0..self.len()) to an actual
3704    /// state identifier.
3705    ///
3706    /// This is useful when using a `Vec<T>` as an efficient map keyed by state
3707    /// to some other information (such as a remapped state ID).
3708    ///
3709    /// If the given index is not in the specified range, then this may panic
3710    /// or produce an incorrect state ID.
3711    fn to_state_id(&self, index: usize) -> StateID {
3712        // CORRECTNESS: If the given index is not valid, then it is not
3713        // required for this to panic or return a valid state ID.
3714        StateID::new_unchecked(index << self.stride2)
3715    }
3716
3717    /// Returns the state ID for the state immediately following the one given.
3718    ///
3719    /// This does not check whether the state ID returned is invalid. In fact,
3720    /// if the state ID given is the last state in this DFA, then the state ID
3721    /// returned is guaranteed to be invalid.
3722    #[cfg(feature = "dfa-build")]
3723    fn next_state_id(&self, id: StateID) -> StateID {
3724        self.to_state_id(self.to_index(id).checked_add(1).unwrap())
3725    }
3726
3727    /// Returns the state ID for the state immediately preceding the one given.
3728    ///
3729    /// If the dead ID given (which is zero), then this panics.
3730    #[cfg(feature = "dfa-build")]
3731    fn prev_state_id(&self, id: StateID) -> StateID {
3732        self.to_state_id(self.to_index(id).checked_sub(1).unwrap())
3733    }
3734
3735    /// Returns the table as a slice of state IDs.
3736    fn table(&self) -> &[StateID] {
3737        wire::u32s_to_state_ids(self.table.as_ref())
3738    }
3739
3740    /// Returns the total number of states in this transition table.
3741    ///
3742    /// Note that a DFA always has at least two states: the dead and quit
3743    /// states. In particular, the dead state always has ID 0 and is
3744    /// correspondingly always the first state. The dead state is never a match
3745    /// state.
3746    fn len(&self) -> usize {
3747        self.table().len() >> self.stride2
3748    }
3749
3750    /// Returns the total stride for every state in this DFA. This corresponds
3751    /// to the total number of transitions used by each state in this DFA's
3752    /// transition table.
3753    fn stride(&self) -> usize {
3754        1 << self.stride2
3755    }
3756
3757    /// Returns the total number of elements in the alphabet for this
3758    /// transition table. This is always less than or equal to `self.stride()`.
3759    /// It is only equal when the alphabet length is a power of 2. Otherwise,
3760    /// it is always strictly less.
3761    fn alphabet_len(&self) -> usize {
3762        self.classes.alphabet_len()
3763    }
3764
3765    /// Returns true if and only if the given state ID is valid for this
3766    /// transition table. Validity in this context means that the given ID can
3767    /// be used as a valid offset with `self.stride()` to index this transition
3768    /// table.
3769    fn is_valid(&self, id: StateID) -> bool {
3770        let id = id.as_usize();
3771        id < self.table().len() && id % self.stride() == 0
3772    }
3773
3774    /// Return the memory usage, in bytes, of this transition table.
3775    ///
3776    /// This does not include the size of a `TransitionTable` value itself.
3777    fn memory_usage(&self) -> usize {
3778        self.table().len() * StateID::SIZE
3779    }
3780}
3781
3782#[cfg(feature = "dfa-build")]
3783impl<T: AsMut<[u32]>> TransitionTable<T> {
3784    /// Returns the table as a slice of state IDs.
3785    fn table_mut(&mut self) -> &mut [StateID] {
3786        wire::u32s_to_state_ids_mut(self.table.as_mut())
3787    }
3788}
3789
3790/// The set of all possible starting states in a DFA.
3791///
3792/// The set of starting states corresponds to the possible choices one can make
3793/// in terms of starting a DFA. That is, before following the first transition,
3794/// you first need to select the state that you start in.
3795///
3796/// Normally, a DFA converted from an NFA that has a single starting state
3797/// would itself just have one starting state. However, our support for look
3798/// around generally requires more starting states. The correct starting state
3799/// is chosen based on certain properties of the position at which we begin
3800/// our search.
3801///
3802/// Before listing those properties, we first must define two terms:
3803///
3804/// * `haystack` - The bytes to execute the search. The search always starts
3805///   at the beginning of `haystack` and ends before or at the end of
3806///   `haystack`.
3807/// * `context` - The (possibly empty) bytes surrounding `haystack`. `haystack`
3808///   must be contained within `context` such that `context` is at least as big
3809///   as `haystack`.
3810///
3811/// This split is crucial for dealing with look-around. For example, consider
3812/// the context `foobarbaz`, the haystack `bar` and the regex `^bar$`. This
3813/// regex should _not_ match the haystack since `bar` does not appear at the
3814/// beginning of the input. Similarly, the regex `\Bbar\B` should match the
3815/// haystack because `bar` is not surrounded by word boundaries. But a search
3816/// that does not take context into account would not permit `\B` to match
3817/// since the beginning of any string matches a word boundary. Similarly, a
3818/// search that does not take context into account when searching `^bar$` in
3819/// the haystack `bar` would produce a match when it shouldn't.
3820///
3821/// Thus, it follows that the starting state is chosen based on the following
3822/// criteria, derived from the position at which the search starts in the
3823/// `context` (corresponding to the start of `haystack`):
3824///
3825/// 1. If the search starts at the beginning of `context`, then the `Text`
3826///    start state is used. (Since `^` corresponds to
3827///    `hir::Anchor::Start`.)
3828/// 2. If the search starts at a position immediately following a line
3829///    terminator, then the `Line` start state is used. (Since `(?m:^)`
3830///    corresponds to `hir::Anchor::StartLF`.)
3831/// 3. If the search starts at a position immediately following a byte
3832///    classified as a "word" character (`[_0-9a-zA-Z]`), then the `WordByte`
3833///    start state is used. (Since `(?-u:\b)` corresponds to a word boundary.)
3834/// 4. Otherwise, if the search starts at a position immediately following
3835///    a byte that is not classified as a "word" character (`[^_0-9a-zA-Z]`),
3836///    then the `NonWordByte` start state is used. (Since `(?-u:\B)`
3837///    corresponds to a not-word-boundary.)
3838///
3839/// (N.B. Unicode word boundaries are not supported by the DFA because they
3840/// require multi-byte look-around and this is difficult to support in a DFA.)
3841///
3842/// To further complicate things, we also support constructing individual
3843/// anchored start states for each pattern in the DFA. (Which is required to
3844/// implement overlapping regexes correctly, but is also generally useful.)
3845/// Thus, when individual start states for each pattern are enabled, then the
3846/// total number of start states represented is `4 + (4 * #patterns)`, where
3847/// the 4 comes from each of the 4 possibilities above. The first 4 represents
3848/// the starting states for the entire DFA, which support searching for
3849/// multiple patterns simultaneously (possibly unanchored).
3850///
3851/// If individual start states are disabled, then this will only store 4
3852/// start states. Typically, individual start states are only enabled when
3853/// constructing the reverse DFA for regex matching. But they are also useful
3854/// for building DFAs that can search for a specific pattern or even to support
3855/// both anchored and unanchored searches with the same DFA.
3856///
3857/// Note though that while the start table always has either `4` or
3858/// `4 + (4 * #patterns)` starting state *ids*, the total number of states
3859/// might be considerably smaller. That is, many of the IDs may be duplicative.
3860/// (For example, if a regex doesn't have a `\b` sub-pattern, then there's no
3861/// reason to generate a unique starting state for handling word boundaries.
3862/// Similarly for start/end anchors.)
3863#[derive(Clone)]
3864pub(crate) struct StartTable<T> {
3865    /// The initial start state IDs.
3866    ///
3867    /// In practice, T is either `Vec<u32>` or `&[u32]`.
3868    ///
3869    /// The first `2 * stride` (currently always 8) entries always correspond
3870    /// to the starts states for the entire DFA, with the first 4 entries being
3871    /// for unanchored searches and the second 4 entries being for anchored
3872    /// searches. To keep things simple, we always use 8 entries even if the
3873    /// `StartKind` is not both.
3874    ///
3875    /// After that, there are `stride * patterns` state IDs, where `patterns`
3876    /// may be zero in the case of a DFA with no patterns or in the case where
3877    /// the DFA was built without enabling starting states for each pattern.
3878    table: T,
3879    /// The starting state configuration supported. When 'both', both
3880    /// unanchored and anchored searches work. When 'unanchored', anchored
3881    /// searches panic. When 'anchored', unanchored searches panic.
3882    kind: StartKind,
3883    /// The start state configuration for every possible byte.
3884    start_map: StartByteMap,
3885    /// The number of starting state IDs per pattern.
3886    stride: usize,
3887    /// The total number of patterns for which starting states are encoded.
3888    /// This is `None` for DFAs that were built without start states for each
3889    /// pattern. Thus, one cannot use this field to say how many patterns
3890    /// are in the DFA in all cases. It is specific to how many patterns are
3891    /// represented in this start table.
3892    pattern_len: Option<usize>,
3893    /// The universal starting state for unanchored searches. This is only
3894    /// present when the DFA supports unanchored searches and when all starting
3895    /// state IDs for an unanchored search are equivalent.
3896    universal_start_unanchored: Option<StateID>,
3897    /// The universal starting state for anchored searches. This is only
3898    /// present when the DFA supports anchored searches and when all starting
3899    /// state IDs for an anchored search are equivalent.
3900    universal_start_anchored: Option<StateID>,
3901}
3902
3903#[cfg(feature = "dfa-build")]
3904impl StartTable<Vec<u32>> {
3905    /// Create a valid set of start states all pointing to the dead state.
3906    ///
3907    /// When the corresponding DFA is constructed with start states for each
3908    /// pattern, then `patterns` should be the number of patterns. Otherwise,
3909    /// it should be zero.
3910    ///
3911    /// If the total table size could exceed the allocatable limit, then this
3912    /// returns an error. In practice, this is unlikely to be able to occur,
3913    /// since it's likely that allocation would have failed long before it got
3914    /// to this point.
3915    fn dead(
3916        kind: StartKind,
3917        lookm: &LookMatcher,
3918        pattern_len: Option<usize>,
3919    ) -> Result<StartTable<Vec<u32>>, BuildError> {
3920        if let Some(len) = pattern_len {
3921            assert!(len <= PatternID::LIMIT);
3922        }
3923        let stride = Start::len();
3924        // OK because 2*4 is never going to overflow anything.
3925        let starts_len = stride.checked_mul(2).unwrap();
3926        let pattern_starts_len =
3927            match stride.checked_mul(pattern_len.unwrap_or(0)) {
3928                Some(x) => x,
3929                None => return Err(BuildError::too_many_start_states()),
3930            };
3931        let table_len = match starts_len.checked_add(pattern_starts_len) {
3932            Some(x) => x,
3933            None => return Err(BuildError::too_many_start_states()),
3934        };
3935        if let Err(_) = isize::try_from(table_len) {
3936            return Err(BuildError::too_many_start_states());
3937        }
3938        let table = vec![DEAD.as_u32(); table_len];
3939        let start_map = StartByteMap::new(lookm);
3940        Ok(StartTable {
3941            table,
3942            kind,
3943            start_map,
3944            stride,
3945            pattern_len,
3946            universal_start_unanchored: None,
3947            universal_start_anchored: None,
3948        })
3949    }
3950}
3951
3952impl<'a> StartTable<&'a [u32]> {
3953    /// Deserialize a table of start state IDs starting at the beginning of
3954    /// `slice`. Upon success, return the total number of bytes read along with
3955    /// the table of starting state IDs.
3956    ///
3957    /// If there was a problem deserializing any part of the starting IDs,
3958    /// then this returns an error. Notably, if the given slice does not have
3959    /// the same alignment as `StateID`, then this will return an error (among
3960    /// other possible errors).
3961    ///
3962    /// This is guaranteed to execute in constant time.
3963    ///
3964    /// # Safety
3965    ///
3966    /// This routine is not safe because it does not check the validity of the
3967    /// starting state IDs themselves. In particular, the number of starting
3968    /// IDs can be of variable length, so it's possible that checking their
3969    /// validity cannot be done in constant time. An invalid starting state
3970    /// ID is not safe because other code may rely on the starting IDs being
3971    /// correct (such as explicit bounds check elision). Therefore, an invalid
3972    /// start ID can lead to undefined behavior.
3973    ///
3974    /// Callers that use this function must either pass on the safety invariant
3975    /// or guarantee that the bytes given contain valid starting state IDs.
3976    /// This guarantee is upheld by the bytes written by `write_to`.
3977    unsafe fn from_bytes_unchecked(
3978        mut slice: &'a [u8],
3979    ) -> Result<(StartTable<&'a [u32]>, usize), DeserializeError> {
3980        let slice_start = slice.as_ptr().as_usize();
3981
3982        let (kind, nr) = StartKind::from_bytes(slice)?;
3983        slice = &slice[nr..];
3984
3985        let (start_map, nr) = StartByteMap::from_bytes(slice)?;
3986        slice = &slice[nr..];
3987
3988        let (stride, nr) =
3989            wire::try_read_u32_as_usize(slice, "start table stride")?;
3990        slice = &slice[nr..];
3991        if stride != Start::len() {
3992            return Err(DeserializeError::generic(
3993                "invalid starting table stride",
3994            ));
3995        }
3996
3997        let (maybe_pattern_len, nr) =
3998            wire::try_read_u32_as_usize(slice, "start table patterns")?;
3999        slice = &slice[nr..];
4000        let pattern_len = if maybe_pattern_len.as_u32() == u32::MAX {
4001            None
4002        } else {
4003            Some(maybe_pattern_len)
4004        };
4005        if pattern_len.map_or(false, |len| len > PatternID::LIMIT) {
4006            return Err(DeserializeError::generic(
4007                "invalid number of patterns",
4008            ));
4009        }
4010
4011        let (universal_unanchored, nr) =
4012            wire::try_read_u32(slice, "universal unanchored start")?;
4013        slice = &slice[nr..];
4014        let universal_start_unanchored = if universal_unanchored == u32::MAX {
4015            None
4016        } else {
4017            Some(StateID::try_from(universal_unanchored).map_err(|e| {
4018                DeserializeError::state_id_error(
4019                    e,
4020                    "universal unanchored start",
4021                )
4022            })?)
4023        };
4024
4025        let (universal_anchored, nr) =
4026            wire::try_read_u32(slice, "universal anchored start")?;
4027        slice = &slice[nr..];
4028        let universal_start_anchored = if universal_anchored == u32::MAX {
4029            None
4030        } else {
4031            Some(StateID::try_from(universal_anchored).map_err(|e| {
4032                DeserializeError::state_id_error(e, "universal anchored start")
4033            })?)
4034        };
4035
4036        let pattern_table_size = wire::mul(
4037            stride,
4038            pattern_len.unwrap_or(0),
4039            "invalid pattern length",
4040        )?;
4041        // Our start states always start with a two stride of start states for
4042        // the entire automaton. The first stride is for unanchored starting
4043        // states and the second stride is for anchored starting states. What
4044        // follows it are an optional set of start states for each pattern.
4045        let start_state_len = wire::add(
4046            wire::mul(2, stride, "start state stride too big")?,
4047            pattern_table_size,
4048            "invalid 'any' pattern starts size",
4049        )?;
4050        let table_bytes_len = wire::mul(
4051            start_state_len,
4052            StateID::SIZE,
4053            "pattern table bytes length",
4054        )?;
4055        wire::check_slice_len(slice, table_bytes_len, "start ID table")?;
4056        wire::check_alignment::<StateID>(slice)?;
4057        let table_bytes = &slice[..table_bytes_len];
4058        slice = &slice[table_bytes_len..];
4059        // SAFETY: Since StateID is always representable as a u32, all we need
4060        // to do is ensure that we have the proper length and alignment. We've
4061        // checked both above, so the cast below is safe.
4062        //
4063        // N.B. This is the only not-safe code in this function.
4064        let table = core::slice::from_raw_parts(
4065            table_bytes.as_ptr().cast::<u32>(),
4066            start_state_len,
4067        );
4068        let st = StartTable {
4069            table,
4070            kind,
4071            start_map,
4072            stride,
4073            pattern_len,
4074            universal_start_unanchored,
4075            universal_start_anchored,
4076        };
4077        Ok((st, slice.as_ptr().as_usize() - slice_start))
4078    }
4079}
4080
4081impl<T: AsRef<[u32]>> StartTable<T> {
4082    /// Writes a serialized form of this start table to the buffer given. If
4083    /// the buffer is too small, then an error is returned. To determine how
4084    /// big the buffer must be, use `write_to_len`.
4085    fn write_to<E: Endian>(
4086        &self,
4087        mut dst: &mut [u8],
4088    ) -> Result<usize, SerializeError> {
4089        let nwrite = self.write_to_len();
4090        if dst.len() < nwrite {
4091            return Err(SerializeError::buffer_too_small(
4092                "starting table ids",
4093            ));
4094        }
4095        dst = &mut dst[..nwrite];
4096
4097        // write start kind
4098        let nw = self.kind.write_to::<E>(dst)?;
4099        dst = &mut dst[nw..];
4100        // write start byte map
4101        let nw = self.start_map.write_to(dst)?;
4102        dst = &mut dst[nw..];
4103        // write stride
4104        // Unwrap is OK since the stride is always 4 (currently).
4105        E::write_u32(u32::try_from(self.stride).unwrap(), dst);
4106        dst = &mut dst[size_of::<u32>()..];
4107        // write pattern length
4108        // Unwrap is OK since number of patterns is guaranteed to fit in a u32.
4109        E::write_u32(
4110            u32::try_from(self.pattern_len.unwrap_or(0xFFFF_FFFF)).unwrap(),
4111            dst,
4112        );
4113        dst = &mut dst[size_of::<u32>()..];
4114        // write universal start unanchored state id, u32::MAX if absent
4115        E::write_u32(
4116            self.universal_start_unanchored
4117                .map_or(u32::MAX, |sid| sid.as_u32()),
4118            dst,
4119        );
4120        dst = &mut dst[size_of::<u32>()..];
4121        // write universal start anchored state id, u32::MAX if absent
4122        E::write_u32(
4123            self.universal_start_anchored.map_or(u32::MAX, |sid| sid.as_u32()),
4124            dst,
4125        );
4126        dst = &mut dst[size_of::<u32>()..];
4127        // write start IDs
4128        for &sid in self.table() {
4129            let n = wire::write_state_id::<E>(sid, &mut dst);
4130            dst = &mut dst[n..];
4131        }
4132        Ok(nwrite)
4133    }
4134
4135    /// Returns the number of bytes the serialized form of this start ID table
4136    /// will use.
4137    fn write_to_len(&self) -> usize {
4138        self.kind.write_to_len()
4139        + self.start_map.write_to_len()
4140        + size_of::<u32>() // stride
4141        + size_of::<u32>() // # patterns
4142        + size_of::<u32>() // universal unanchored start
4143        + size_of::<u32>() // universal anchored start
4144        + (self.table().len() * StateID::SIZE)
4145    }
4146
4147    /// Validates that every state ID in this start table is valid by checking
4148    /// it against the given transition table (which must be for the same DFA).
4149    ///
4150    /// That is, every state ID can be used to correctly index a state.
4151    fn validate(&self, dfa: &DFA<T>) -> Result<(), DeserializeError> {
4152        let tt = &dfa.tt;
4153        if !self.universal_start_unanchored.map_or(true, |s| tt.is_valid(s)) {
4154            return Err(DeserializeError::generic(
4155                "found invalid universal unanchored starting state ID",
4156            ));
4157        }
4158        if !self.universal_start_anchored.map_or(true, |s| tt.is_valid(s)) {
4159            return Err(DeserializeError::generic(
4160                "found invalid universal anchored starting state ID",
4161            ));
4162        }
4163        for &id in self.table() {
4164            if !tt.is_valid(id) {
4165                return Err(DeserializeError::generic(
4166                    "found invalid starting state ID",
4167                ));
4168            }
4169        }
4170        Ok(())
4171    }
4172
4173    /// Converts this start list to a borrowed value.
4174    fn as_ref(&self) -> StartTable<&'_ [u32]> {
4175        StartTable {
4176            table: self.table.as_ref(),
4177            kind: self.kind,
4178            start_map: self.start_map.clone(),
4179            stride: self.stride,
4180            pattern_len: self.pattern_len,
4181            universal_start_unanchored: self.universal_start_unanchored,
4182            universal_start_anchored: self.universal_start_anchored,
4183        }
4184    }
4185
4186    /// Converts this start list to an owned value.
4187    #[cfg(feature = "alloc")]
4188    fn to_owned(&self) -> StartTable<alloc::vec::Vec<u32>> {
4189        StartTable {
4190            table: self.table.as_ref().to_vec(),
4191            kind: self.kind,
4192            start_map: self.start_map.clone(),
4193            stride: self.stride,
4194            pattern_len: self.pattern_len,
4195            universal_start_unanchored: self.universal_start_unanchored,
4196            universal_start_anchored: self.universal_start_anchored,
4197        }
4198    }
4199
4200    /// Return the start state for the given input and starting configuration.
4201    /// This returns an error if the input configuration is not supported by
4202    /// this DFA. For example, requesting an unanchored search when the DFA was
4203    /// not built with unanchored starting states. Or asking for an anchored
4204    /// pattern search with an invalid pattern ID or on a DFA that was not
4205    /// built with start states for each pattern.
4206    #[cfg_attr(feature = "perf-inline", inline(always))]
4207    fn start(
4208        &self,
4209        anchored: Anchored,
4210        start: Start,
4211    ) -> Result<StateID, StartError> {
4212        let start_index = start.as_usize();
4213        let index = match anchored {
4214            Anchored::No => {
4215                if !self.kind.has_unanchored() {
4216                    return Err(StartError::unsupported_anchored(anchored));
4217                }
4218                start_index
4219            }
4220            Anchored::Yes => {
4221                if !self.kind.has_anchored() {
4222                    return Err(StartError::unsupported_anchored(anchored));
4223                }
4224                self.stride + start_index
4225            }
4226            Anchored::Pattern(pid) => {
4227                let len = match self.pattern_len {
4228                    None => {
4229                        return Err(StartError::unsupported_anchored(anchored))
4230                    }
4231                    Some(len) => len,
4232                };
4233                if pid.as_usize() >= len {
4234                    return Ok(DEAD);
4235                }
4236                (2 * self.stride)
4237                    + (self.stride * pid.as_usize())
4238                    + start_index
4239            }
4240        };
4241        Ok(self.table()[index])
4242    }
4243
4244    /// Returns an iterator over all start state IDs in this table.
4245    ///
4246    /// Each item is a triple of: start state ID, the start state type and the
4247    /// pattern ID (if any).
4248    fn iter(&self) -> StartStateIter<'_> {
4249        StartStateIter { st: self.as_ref(), i: 0 }
4250    }
4251
4252    /// Returns the table as a slice of state IDs.
4253    fn table(&self) -> &[StateID] {
4254        wire::u32s_to_state_ids(self.table.as_ref())
4255    }
4256
4257    /// Return the memory usage, in bytes, of this start list.
4258    ///
4259    /// This does not include the size of a `StartList` value itself.
4260    fn memory_usage(&self) -> usize {
4261        self.table().len() * StateID::SIZE
4262    }
4263}
4264
4265#[cfg(feature = "dfa-build")]
4266impl<T: AsMut<[u32]>> StartTable<T> {
4267    /// Set the start state for the given index and pattern.
4268    ///
4269    /// If the pattern ID or state ID are not valid, then this will panic.
4270    fn set_start(&mut self, anchored: Anchored, start: Start, id: StateID) {
4271        let start_index = start.as_usize();
4272        let index = match anchored {
4273            Anchored::No => start_index,
4274            Anchored::Yes => self.stride + start_index,
4275            Anchored::Pattern(pid) => {
4276                let pid = pid.as_usize();
4277                let len = self
4278                    .pattern_len
4279                    .expect("start states for each pattern enabled");
4280                assert!(pid < len, "invalid pattern ID {:?}", pid);
4281                self.stride
4282                    .checked_mul(pid)
4283                    .unwrap()
4284                    .checked_add(self.stride.checked_mul(2).unwrap())
4285                    .unwrap()
4286                    .checked_add(start_index)
4287                    .unwrap()
4288            }
4289        };
4290        self.table_mut()[index] = id;
4291    }
4292
4293    /// Returns the table as a mutable slice of state IDs.
4294    fn table_mut(&mut self) -> &mut [StateID] {
4295        wire::u32s_to_state_ids_mut(self.table.as_mut())
4296    }
4297}
4298
4299/// An iterator over start state IDs.
4300///
4301/// This iterator yields a triple of start state ID, the anchored mode and the
4302/// start state type. If a pattern ID is relevant, then the anchored mode will
4303/// contain it. Start states with an anchored mode containing a pattern ID will
4304/// only occur when the DFA was compiled with start states for each pattern
4305/// (which is disabled by default).
4306pub(crate) struct StartStateIter<'a> {
4307    st: StartTable<&'a [u32]>,
4308    i: usize,
4309}
4310
4311impl<'a> Iterator for StartStateIter<'a> {
4312    type Item = (StateID, Anchored, Start);
4313
4314    fn next(&mut self) -> Option<(StateID, Anchored, Start)> {
4315        let i = self.i;
4316        let table = self.st.table();
4317        if i >= table.len() {
4318            return None;
4319        }
4320        self.i += 1;
4321
4322        // This unwrap is okay since the stride of the starting state table
4323        // must always match the number of start state types.
4324        let start_type = Start::from_usize(i % self.st.stride).unwrap();
4325        let anchored = if i < self.st.stride {
4326            Anchored::No
4327        } else if i < (2 * self.st.stride) {
4328            Anchored::Yes
4329        } else {
4330            let pid = (i - (2 * self.st.stride)) / self.st.stride;
4331            Anchored::Pattern(PatternID::new(pid).unwrap())
4332        };
4333        Some((table[i], anchored, start_type))
4334    }
4335}
4336
4337/// This type represents that patterns that should be reported whenever a DFA
4338/// enters a match state. This structure exists to support DFAs that search for
4339/// matches for multiple regexes.
4340///
4341/// This structure relies on the fact that all match states in a DFA occur
4342/// contiguously in the DFA's transition table. (See dfa/special.rs for a more
4343/// detailed breakdown of the representation.) Namely, when a match occurs, we
4344/// know its state ID. Since we know the start and end of the contiguous region
4345/// of match states, we can use that to compute the position at which the match
4346/// state occurs. That in turn is used as an offset into this structure.
4347#[derive(Clone, Debug)]
4348struct MatchStates<T> {
4349    /// Slices is a flattened sequence of pairs, where each pair points to a
4350    /// sub-slice of pattern_ids. The first element of the pair is an offset
4351    /// into pattern_ids and the second element of the pair is the number
4352    /// of 32-bit pattern IDs starting at that position. That is, each pair
4353    /// corresponds to a single DFA match state and its corresponding match
4354    /// IDs. The number of pairs always corresponds to the number of distinct
4355    /// DFA match states.
4356    ///
4357    /// In practice, T is either Vec<u32> or &[u32].
4358    slices: T,
4359    /// A flattened sequence of pattern IDs for each DFA match state. The only
4360    /// way to correctly read this sequence is indirectly via `slices`.
4361    ///
4362    /// In practice, T is either Vec<u32> or &[u32].
4363    pattern_ids: T,
4364    /// The total number of unique patterns represented by these match states.
4365    pattern_len: usize,
4366}
4367
4368impl<'a> MatchStates<&'a [u32]> {
4369    unsafe fn from_bytes_unchecked(
4370        mut slice: &'a [u8],
4371    ) -> Result<(MatchStates<&'a [u32]>, usize), DeserializeError> {
4372        let slice_start = slice.as_ptr().as_usize();
4373
4374        // Read the total number of match states.
4375        let (state_len, nr) =
4376            wire::try_read_u32_as_usize(slice, "match state length")?;
4377        slice = &slice[nr..];
4378
4379        // Read the slice start/length pairs.
4380        let pair_len = wire::mul(2, state_len, "match state offset pairs")?;
4381        let slices_bytes_len = wire::mul(
4382            pair_len,
4383            PatternID::SIZE,
4384            "match state slice offset byte length",
4385        )?;
4386        wire::check_slice_len(slice, slices_bytes_len, "match state slices")?;
4387        wire::check_alignment::<PatternID>(slice)?;
4388        let slices_bytes = &slice[..slices_bytes_len];
4389        slice = &slice[slices_bytes_len..];
4390        // SAFETY: Since PatternID is always representable as a u32, all we
4391        // need to do is ensure that we have the proper length and alignment.
4392        // We've checked both above, so the cast below is safe.
4393        //
4394        // N.B. This is one of the few not-safe snippets in this function,
4395        // so we mark it explicitly to call it out.
4396        let slices = core::slice::from_raw_parts(
4397            slices_bytes.as_ptr().cast::<u32>(),
4398            pair_len,
4399        );
4400
4401        // Read the total number of unique pattern IDs (which is always 1 more
4402        // than the maximum pattern ID in this automaton, since pattern IDs are
4403        // handed out contiguously starting at 0).
4404        let (pattern_len, nr) =
4405            wire::try_read_u32_as_usize(slice, "pattern length")?;
4406        slice = &slice[nr..];
4407
4408        // Now read the pattern ID length. We don't need to store this
4409        // explicitly, but we need it to know how many pattern IDs to read.
4410        let (idlen, nr) =
4411            wire::try_read_u32_as_usize(slice, "pattern ID length")?;
4412        slice = &slice[nr..];
4413
4414        // Read the actual pattern IDs.
4415        let pattern_ids_len =
4416            wire::mul(idlen, PatternID::SIZE, "pattern ID byte length")?;
4417        wire::check_slice_len(slice, pattern_ids_len, "match pattern IDs")?;
4418        wire::check_alignment::<PatternID>(slice)?;
4419        let pattern_ids_bytes = &slice[..pattern_ids_len];
4420        slice = &slice[pattern_ids_len..];
4421        // SAFETY: Since PatternID is always representable as a u32, all we
4422        // need to do is ensure that we have the proper length and alignment.
4423        // We've checked both above, so the cast below is safe.
4424        //
4425        // N.B. This is one of the few not-safe snippets in this function,
4426        // so we mark it explicitly to call it out.
4427        let pattern_ids = core::slice::from_raw_parts(
4428            pattern_ids_bytes.as_ptr().cast::<u32>(),
4429            idlen,
4430        );
4431
4432        let ms = MatchStates { slices, pattern_ids, pattern_len };
4433        Ok((ms, slice.as_ptr().as_usize() - slice_start))
4434    }
4435}
4436
4437#[cfg(feature = "dfa-build")]
4438impl MatchStates<Vec<u32>> {
4439    fn empty(pattern_len: usize) -> MatchStates<Vec<u32>> {
4440        assert!(pattern_len <= PatternID::LIMIT);
4441        MatchStates { slices: vec![], pattern_ids: vec![], pattern_len }
4442    }
4443
4444    fn new(
4445        matches: &BTreeMap<StateID, Vec<PatternID>>,
4446        pattern_len: usize,
4447    ) -> Result<MatchStates<Vec<u32>>, BuildError> {
4448        let mut m = MatchStates::empty(pattern_len);
4449        for (_, pids) in matches.iter() {
4450            let start = PatternID::new(m.pattern_ids.len())
4451                .map_err(|_| BuildError::too_many_match_pattern_ids())?;
4452            m.slices.push(start.as_u32());
4453            // This is always correct since the number of patterns in a single
4454            // match state can never exceed maximum number of allowable
4455            // patterns. Why? Because a pattern can only appear once in a
4456            // particular match state, by construction. (And since our pattern
4457            // ID limit is one less than u32::MAX, we're guaranteed that the
4458            // length fits in a u32.)
4459            m.slices.push(u32::try_from(pids.len()).unwrap());
4460            for &pid in pids {
4461                m.pattern_ids.push(pid.as_u32());
4462            }
4463        }
4464        m.pattern_len = pattern_len;
4465        Ok(m)
4466    }
4467
4468    fn new_with_map(
4469        &self,
4470        matches: &BTreeMap<StateID, Vec<PatternID>>,
4471    ) -> Result<MatchStates<Vec<u32>>, BuildError> {
4472        MatchStates::new(matches, self.pattern_len)
4473    }
4474}
4475
4476impl<T: AsRef<[u32]>> MatchStates<T> {
4477    /// Writes a serialized form of these match states to the buffer given. If
4478    /// the buffer is too small, then an error is returned. To determine how
4479    /// big the buffer must be, use `write_to_len`.
4480    fn write_to<E: Endian>(
4481        &self,
4482        mut dst: &mut [u8],
4483    ) -> Result<usize, SerializeError> {
4484        let nwrite = self.write_to_len();
4485        if dst.len() < nwrite {
4486            return Err(SerializeError::buffer_too_small("match states"));
4487        }
4488        dst = &mut dst[..nwrite];
4489
4490        // write state ID length
4491        // Unwrap is OK since number of states is guaranteed to fit in a u32.
4492        E::write_u32(u32::try_from(self.len()).unwrap(), dst);
4493        dst = &mut dst[size_of::<u32>()..];
4494
4495        // write slice offset pairs
4496        for &pid in self.slices() {
4497            let n = wire::write_pattern_id::<E>(pid, &mut dst);
4498            dst = &mut dst[n..];
4499        }
4500
4501        // write unique pattern ID length
4502        // Unwrap is OK since number of patterns is guaranteed to fit in a u32.
4503        E::write_u32(u32::try_from(self.pattern_len).unwrap(), dst);
4504        dst = &mut dst[size_of::<u32>()..];
4505
4506        // write pattern ID length
4507        // Unwrap is OK since we check at construction (and deserialization)
4508        // that the number of patterns is representable as a u32.
4509        E::write_u32(u32::try_from(self.pattern_ids().len()).unwrap(), dst);
4510        dst = &mut dst[size_of::<u32>()..];
4511
4512        // write pattern IDs
4513        for &pid in self.pattern_ids() {
4514            let n = wire::write_pattern_id::<E>(pid, &mut dst);
4515            dst = &mut dst[n..];
4516        }
4517
4518        Ok(nwrite)
4519    }
4520
4521    /// Returns the number of bytes the serialized form of these match states
4522    /// will use.
4523    fn write_to_len(&self) -> usize {
4524        size_of::<u32>()   // match state length
4525        + (self.slices().len() * PatternID::SIZE)
4526        + size_of::<u32>() // unique pattern ID length
4527        + size_of::<u32>() // pattern ID length
4528        + (self.pattern_ids().len() * PatternID::SIZE)
4529    }
4530
4531    /// Validates that the match state info is itself internally consistent and
4532    /// consistent with the recorded match state region in the given DFA.
4533    fn validate(&self, dfa: &DFA<T>) -> Result<(), DeserializeError> {
4534        if self.len() != dfa.special.match_len(dfa.stride()) {
4535            return Err(DeserializeError::generic(
4536                "match state length mismatch",
4537            ));
4538        }
4539        for si in 0..self.len() {
4540            let start = self.slices()[si * 2].as_usize();
4541            let len = self.slices()[si * 2 + 1].as_usize();
4542            if start >= self.pattern_ids().len() {
4543                return Err(DeserializeError::generic(
4544                    "invalid pattern ID start offset",
4545                ));
4546            }
4547            if start + len > self.pattern_ids().len() {
4548                return Err(DeserializeError::generic(
4549                    "invalid pattern ID length",
4550                ));
4551            }
4552            for mi in 0..len {
4553                let pid = self.pattern_id(si, mi);
4554                if pid.as_usize() >= self.pattern_len {
4555                    return Err(DeserializeError::generic(
4556                        "invalid pattern ID",
4557                    ));
4558                }
4559            }
4560        }
4561        Ok(())
4562    }
4563
4564    /// Converts these match states back into their map form. This is useful
4565    /// when shuffling states, as the normal MatchStates representation is not
4566    /// amenable to easy state swapping. But with this map, to swap id1 and
4567    /// id2, all you need to do is:
4568    ///
4569    /// if let Some(pids) = map.remove(&id1) {
4570    ///     map.insert(id2, pids);
4571    /// }
4572    ///
4573    /// Once shuffling is done, use MatchStates::new to convert back.
4574    #[cfg(feature = "dfa-build")]
4575    fn to_map(&self, dfa: &DFA<T>) -> BTreeMap<StateID, Vec<PatternID>> {
4576        let mut map = BTreeMap::new();
4577        for i in 0..self.len() {
4578            let mut pids = vec![];
4579            for j in 0..self.pattern_len(i) {
4580                pids.push(self.pattern_id(i, j));
4581            }
4582            map.insert(self.match_state_id(dfa, i), pids);
4583        }
4584        map
4585    }
4586
4587    /// Converts these match states to a borrowed value.
4588    fn as_ref(&self) -> MatchStates<&'_ [u32]> {
4589        MatchStates {
4590            slices: self.slices.as_ref(),
4591            pattern_ids: self.pattern_ids.as_ref(),
4592            pattern_len: self.pattern_len,
4593        }
4594    }
4595
4596    /// Converts these match states to an owned value.
4597    #[cfg(feature = "alloc")]
4598    fn to_owned(&self) -> MatchStates<alloc::vec::Vec<u32>> {
4599        MatchStates {
4600            slices: self.slices.as_ref().to_vec(),
4601            pattern_ids: self.pattern_ids.as_ref().to_vec(),
4602            pattern_len: self.pattern_len,
4603        }
4604    }
4605
4606    /// Returns the match state ID given the match state index. (Where the
4607    /// first match state corresponds to index 0.)
4608    ///
4609    /// This panics if there is no match state at the given index.
4610    fn match_state_id(&self, dfa: &DFA<T>, index: usize) -> StateID {
4611        assert!(dfa.special.matches(), "no match states to index");
4612        // This is one of the places where we rely on the fact that match
4613        // states are contiguous in the transition table. Namely, that the
4614        // first match state ID always corresponds to dfa.special.min_start.
4615        // From there, since we know the stride, we can compute the ID of any
4616        // match state given its index.
4617        let stride2 = u32::try_from(dfa.stride2()).unwrap();
4618        let offset = index.checked_shl(stride2).unwrap();
4619        let id = dfa.special.min_match.as_usize().checked_add(offset).unwrap();
4620        let sid = StateID::new(id).unwrap();
4621        assert!(dfa.is_match_state(sid));
4622        sid
4623    }
4624
4625    /// Returns the pattern ID at the given match index for the given match
4626    /// state.
4627    ///
4628    /// The match state index is the state index minus the state index of the
4629    /// first match state in the DFA.
4630    ///
4631    /// The match index is the index of the pattern ID for the given state.
4632    /// The index must be less than `self.pattern_len(state_index)`.
4633    #[cfg_attr(feature = "perf-inline", inline(always))]
4634    fn pattern_id(&self, state_index: usize, match_index: usize) -> PatternID {
4635        self.pattern_id_slice(state_index)[match_index]
4636    }
4637
4638    /// Returns the number of patterns in the given match state.
4639    ///
4640    /// The match state index is the state index minus the state index of the
4641    /// first match state in the DFA.
4642    #[cfg_attr(feature = "perf-inline", inline(always))]
4643    fn pattern_len(&self, state_index: usize) -> usize {
4644        self.slices()[state_index * 2 + 1].as_usize()
4645    }
4646
4647    /// Returns all of the pattern IDs for the given match state index.
4648    ///
4649    /// The match state index is the state index minus the state index of the
4650    /// first match state in the DFA.
4651    #[cfg_attr(feature = "perf-inline", inline(always))]
4652    fn pattern_id_slice(&self, state_index: usize) -> &[PatternID] {
4653        let start = self.slices()[state_index * 2].as_usize();
4654        let len = self.pattern_len(state_index);
4655        &self.pattern_ids()[start..start + len]
4656    }
4657
4658    /// Returns the pattern ID offset slice of u32 as a slice of PatternID.
4659    #[cfg_attr(feature = "perf-inline", inline(always))]
4660    fn slices(&self) -> &[PatternID] {
4661        wire::u32s_to_pattern_ids(self.slices.as_ref())
4662    }
4663
4664    /// Returns the total number of match states.
4665    #[cfg_attr(feature = "perf-inline", inline(always))]
4666    fn len(&self) -> usize {
4667        assert_eq!(0, self.slices().len() % 2);
4668        self.slices().len() / 2
4669    }
4670
4671    /// Returns the pattern ID slice of u32 as a slice of PatternID.
4672    #[cfg_attr(feature = "perf-inline", inline(always))]
4673    fn pattern_ids(&self) -> &[PatternID] {
4674        wire::u32s_to_pattern_ids(self.pattern_ids.as_ref())
4675    }
4676
4677    /// Return the memory usage, in bytes, of these match pairs.
4678    fn memory_usage(&self) -> usize {
4679        (self.slices().len() + self.pattern_ids().len()) * PatternID::SIZE
4680    }
4681}
4682
4683/// A common set of flags for both dense and sparse DFAs. This primarily
4684/// centralizes the serialization format of these flags at a bitset.
4685#[derive(Clone, Copy, Debug)]
4686pub(crate) struct Flags {
4687    /// Whether the DFA can match the empty string. When this is false, all
4688    /// matches returned by this DFA are guaranteed to have non-zero length.
4689    pub(crate) has_empty: bool,
4690    /// Whether the DFA should only produce matches with spans that correspond
4691    /// to valid UTF-8. This also includes omitting any zero-width matches that
4692    /// split the UTF-8 encoding of a codepoint.
4693    pub(crate) is_utf8: bool,
4694    /// Whether the DFA is always anchored or not, regardless of `Input`
4695    /// configuration. This is useful for avoiding a reverse scan even when
4696    /// executing unanchored searches.
4697    pub(crate) is_always_start_anchored: bool,
4698}
4699
4700impl Flags {
4701    /// Creates a set of flags for a DFA from an NFA.
4702    ///
4703    /// N.B. This constructor was defined at the time of writing because all
4704    /// of the flags are derived directly from the NFA. If this changes in the
4705    /// future, we might be more thoughtful about how the `Flags` value is
4706    /// itself built.
4707    #[cfg(feature = "dfa-build")]
4708    fn from_nfa(nfa: &thompson::NFA) -> Flags {
4709        Flags {
4710            has_empty: nfa.has_empty(),
4711            is_utf8: nfa.is_utf8(),
4712            is_always_start_anchored: nfa.is_always_start_anchored(),
4713        }
4714    }
4715
4716    /// Deserializes the flags from the given slice. On success, this also
4717    /// returns the number of bytes read from the slice.
4718    pub(crate) fn from_bytes(
4719        slice: &[u8],
4720    ) -> Result<(Flags, usize), DeserializeError> {
4721        let (bits, nread) = wire::try_read_u32(slice, "flag bitset")?;
4722        let flags = Flags {
4723            has_empty: bits & (1 << 0) != 0,
4724            is_utf8: bits & (1 << 1) != 0,
4725            is_always_start_anchored: bits & (1 << 2) != 0,
4726        };
4727        Ok((flags, nread))
4728    }
4729
4730    /// Writes these flags to the given byte slice. If the buffer is too small,
4731    /// then an error is returned. To determine how big the buffer must be,
4732    /// use `write_to_len`.
4733    pub(crate) fn write_to<E: Endian>(
4734        &self,
4735        dst: &mut [u8],
4736    ) -> Result<usize, SerializeError> {
4737        fn bool_to_int(b: bool) -> u32 {
4738            if b {
4739                1
4740            } else {
4741                0
4742            }
4743        }
4744
4745        let nwrite = self.write_to_len();
4746        if dst.len() < nwrite {
4747            return Err(SerializeError::buffer_too_small("flag bitset"));
4748        }
4749        let bits = (bool_to_int(self.has_empty) << 0)
4750            | (bool_to_int(self.is_utf8) << 1)
4751            | (bool_to_int(self.is_always_start_anchored) << 2);
4752        E::write_u32(bits, dst);
4753        Ok(nwrite)
4754    }
4755
4756    /// Returns the number of bytes the serialized form of these flags
4757    /// will use.
4758    pub(crate) fn write_to_len(&self) -> usize {
4759        size_of::<u32>()
4760    }
4761}
4762
4763/// An iterator over all states in a DFA.
4764///
4765/// This iterator yields a tuple for each state. The first element of the
4766/// tuple corresponds to a state's identifier, and the second element
4767/// corresponds to the state itself (comprised of its transitions).
4768///
4769/// `'a` corresponding to the lifetime of original DFA, `T` corresponds to
4770/// the type of the transition table itself.
4771pub(crate) struct StateIter<'a, T> {
4772    tt: &'a TransitionTable<T>,
4773    it: iter::Enumerate<slice::Chunks<'a, StateID>>,
4774}
4775
4776impl<'a, T: AsRef<[u32]>> Iterator for StateIter<'a, T> {
4777    type Item = State<'a>;
4778
4779    fn next(&mut self) -> Option<State<'a>> {
4780        self.it.next().map(|(index, _)| {
4781            let id = self.tt.to_state_id(index);
4782            self.tt.state(id)
4783        })
4784    }
4785}
4786
4787/// An immutable representation of a single DFA state.
4788///
4789/// `'a` corresponding to the lifetime of a DFA's transition table.
4790pub(crate) struct State<'a> {
4791    id: StateID,
4792    stride2: usize,
4793    transitions: &'a [StateID],
4794}
4795
4796impl<'a> State<'a> {
4797    /// Return an iterator over all transitions in this state. This yields
4798    /// a number of transitions equivalent to the alphabet length of the
4799    /// corresponding DFA.
4800    ///
4801    /// Each transition is represented by a tuple. The first element is
4802    /// the input byte for that transition and the second element is the
4803    /// transitions itself.
4804    pub(crate) fn transitions(&self) -> StateTransitionIter<'_> {
4805        StateTransitionIter {
4806            len: self.transitions.len(),
4807            it: self.transitions.iter().enumerate(),
4808        }
4809    }
4810
4811    /// Return an iterator over a sparse representation of the transitions in
4812    /// this state. Only non-dead transitions are returned.
4813    ///
4814    /// The "sparse" representation in this case corresponds to a sequence of
4815    /// triples. The first two elements of the triple comprise an inclusive
4816    /// byte range while the last element corresponds to the transition taken
4817    /// for all bytes in the range.
4818    ///
4819    /// This is somewhat more condensed than the classical sparse
4820    /// representation (where you have an element for every non-dead
4821    /// transition), but in practice, checking if a byte is in a range is very
4822    /// cheap and using ranges tends to conserve quite a bit more space.
4823    pub(crate) fn sparse_transitions(&self) -> StateSparseTransitionIter<'_> {
4824        StateSparseTransitionIter { dense: self.transitions(), cur: None }
4825    }
4826
4827    /// Returns the identifier for this state.
4828    pub(crate) fn id(&self) -> StateID {
4829        self.id
4830    }
4831
4832    /// Analyzes this state to determine whether it can be accelerated. If so,
4833    /// it returns an accelerator that contains at least one byte.
4834    #[cfg(feature = "dfa-build")]
4835    fn accelerate(&self, classes: &ByteClasses) -> Option<Accel> {
4836        // We just try to add bytes to our accelerator. Once adding fails
4837        // (because we've added too many bytes), then give up.
4838        let mut accel = Accel::new();
4839        for (class, id) in self.transitions() {
4840            if id == self.id() {
4841                continue;
4842            }
4843            for unit in classes.elements(class) {
4844                if let Some(byte) = unit.as_u8() {
4845                    if !accel.add(byte) {
4846                        return None;
4847                    }
4848                }
4849            }
4850        }
4851        if accel.is_empty() {
4852            None
4853        } else {
4854            Some(accel)
4855        }
4856    }
4857}
4858
4859impl<'a> fmt::Debug for State<'a> {
4860    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4861        for (i, (start, end, sid)) in self.sparse_transitions().enumerate() {
4862            let id = if f.alternate() {
4863                sid.as_usize()
4864            } else {
4865                sid.as_usize() >> self.stride2
4866            };
4867            if i > 0 {
4868                write!(f, ", ")?;
4869            }
4870            if start == end {
4871                write!(f, "{:?} => {:?}", start, id)?;
4872            } else {
4873                write!(f, "{:?}-{:?} => {:?}", start, end, id)?;
4874            }
4875        }
4876        Ok(())
4877    }
4878}
4879
4880/// An iterator over all transitions in a single DFA state. This yields
4881/// a number of transitions equivalent to the alphabet length of the
4882/// corresponding DFA.
4883///
4884/// Each transition is represented by a tuple. The first element is the input
4885/// byte for that transition and the second element is the transition itself.
4886#[derive(Debug)]
4887pub(crate) struct StateTransitionIter<'a> {
4888    len: usize,
4889    it: iter::Enumerate<slice::Iter<'a, StateID>>,
4890}
4891
4892impl<'a> Iterator for StateTransitionIter<'a> {
4893    type Item = (alphabet::Unit, StateID);
4894
4895    fn next(&mut self) -> Option<(alphabet::Unit, StateID)> {
4896        self.it.next().map(|(i, &id)| {
4897            let unit = if i + 1 == self.len {
4898                alphabet::Unit::eoi(i)
4899            } else {
4900                let b = u8::try_from(i)
4901                    .expect("raw byte alphabet is never exceeded");
4902                alphabet::Unit::u8(b)
4903            };
4904            (unit, id)
4905        })
4906    }
4907}
4908
4909/// An iterator over all non-DEAD transitions in a single DFA state using a
4910/// sparse representation.
4911///
4912/// Each transition is represented by a triple. The first two elements of the
4913/// triple comprise an inclusive byte range while the last element corresponds
4914/// to the transition taken for all bytes in the range.
4915///
4916/// As a convenience, this always returns `alphabet::Unit` values of the same
4917/// type. That is, you'll never get a (byte, EOI) or a (EOI, byte). Only (byte,
4918/// byte) and (EOI, EOI) values are yielded.
4919#[derive(Debug)]
4920pub(crate) struct StateSparseTransitionIter<'a> {
4921    dense: StateTransitionIter<'a>,
4922    cur: Option<(alphabet::Unit, alphabet::Unit, StateID)>,
4923}
4924
4925impl<'a> Iterator for StateSparseTransitionIter<'a> {
4926    type Item = (alphabet::Unit, alphabet::Unit, StateID);
4927
4928    fn next(&mut self) -> Option<(alphabet::Unit, alphabet::Unit, StateID)> {
4929        while let Some((unit, next)) = self.dense.next() {
4930            let (prev_start, prev_end, prev_next) = match self.cur {
4931                Some(t) => t,
4932                None => {
4933                    self.cur = Some((unit, unit, next));
4934                    continue;
4935                }
4936            };
4937            if prev_next == next && !unit.is_eoi() {
4938                self.cur = Some((prev_start, unit, prev_next));
4939            } else {
4940                self.cur = Some((unit, unit, next));
4941                if prev_next != DEAD {
4942                    return Some((prev_start, prev_end, prev_next));
4943                }
4944            }
4945        }
4946        if let Some((start, end, next)) = self.cur.take() {
4947            if next != DEAD {
4948                return Some((start, end, next));
4949            }
4950        }
4951        None
4952    }
4953}
4954
4955/// An error that occurred during the construction of a DFA.
4956///
4957/// This error does not provide many introspection capabilities. There are
4958/// generally only two things you can do with it:
4959///
4960/// * Obtain a human readable message via its `std::fmt::Display` impl.
4961/// * Access an underlying [`nfa::thompson::BuildError`](thompson::BuildError)
4962/// type from its `source` method via the `std::error::Error` trait. This error
4963/// only occurs when using convenience routines for building a DFA directly
4964/// from a pattern string.
4965///
4966/// When the `std` feature is enabled, this implements the `std::error::Error`
4967/// trait.
4968#[cfg(feature = "dfa-build")]
4969#[derive(Clone, Debug)]
4970pub struct BuildError {
4971    kind: BuildErrorKind,
4972}
4973
4974#[cfg(feature = "dfa-build")]
4975impl BuildError {
4976    /// Returns true if and only if this error corresponds to an error with DFA
4977    /// construction that occurred because of exceeding a size limit.
4978    ///
4979    /// While this can occur when size limits like [`Config::dfa_size_limit`]
4980    /// or [`Config::determinize_size_limit`] are exceeded, this can also occur
4981    /// when the number of states or patterns exceeds a hard-coded maximum.
4982    /// (Where these maximums are derived based on the values representable by
4983    /// [`StateID`] and [`PatternID`].)
4984    ///
4985    /// This predicate is useful in contexts where you want to distinguish
4986    /// between errors related to something provided by an end user (for
4987    /// example, an invalid regex pattern) and errors related to configured
4988    /// heuristics. For example, building a DFA might be an optimization that
4989    /// you want to skip if construction fails because of an exceeded size
4990    /// limit, but where you want to bubble up an error if it fails for some
4991    /// other reason.
4992    ///
4993    /// # Example
4994    ///
4995    /// ```
4996    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
4997    /// # if !cfg!(target_pointer_width = "64") { return Ok(()); } // see #1039
4998    /// use regex_automata::{dfa::{dense, Automaton}, Input};
4999    ///
5000    /// let err = dense::Builder::new()
5001    ///     .configure(dense::Config::new()
5002    ///         .determinize_size_limit(Some(100_000))
5003    ///     )
5004    ///     .build(r"\w{20}")
5005    ///     .unwrap_err();
5006    /// // This error occurs because a size limit was exceeded.
5007    /// // But things are otherwise valid.
5008    /// assert!(err.is_size_limit_exceeded());
5009    ///
5010    /// let err = dense::Builder::new()
5011    ///     .build(r"\bxyz\b")
5012    ///     .unwrap_err();
5013    /// // This error occurs because a Unicode word boundary
5014    /// // was used without enabling heuristic support for it.
5015    /// // So... not related to size limits.
5016    /// assert!(!err.is_size_limit_exceeded());
5017    ///
5018    /// let err = dense::Builder::new()
5019    ///     .build(r"(xyz")
5020    ///     .unwrap_err();
5021    /// // This error occurs because the pattern is invalid.
5022    /// // So... not related to size limits.
5023    /// assert!(!err.is_size_limit_exceeded());
5024    ///
5025    /// # Ok::<(), Box<dyn std::error::Error>>(())
5026    /// ```
5027    #[inline]
5028    pub fn is_size_limit_exceeded(&self) -> bool {
5029        use self::BuildErrorKind::*;
5030
5031        match self.kind {
5032            NFA(_) | Unsupported(_) => false,
5033            TooManyStates
5034            | TooManyStartStates
5035            | TooManyMatchPatternIDs
5036            | DFAExceededSizeLimit { .. }
5037            | DeterminizeExceededSizeLimit { .. } => true,
5038        }
5039    }
5040}
5041
5042/// The kind of error that occurred during the construction of a DFA.
5043///
5044/// Note that this error is non-exhaustive. Adding new variants is not
5045/// considered a breaking change.
5046#[cfg(feature = "dfa-build")]
5047#[derive(Clone, Debug)]
5048enum BuildErrorKind {
5049    /// An error that occurred while constructing an NFA as a precursor step
5050    /// before a DFA is compiled.
5051    NFA(thompson::BuildError),
5052    /// An error that occurred because an unsupported regex feature was used.
5053    /// The message string describes which unsupported feature was used.
5054    ///
5055    /// The primary regex feature that is unsupported by DFAs is the Unicode
5056    /// word boundary look-around assertion (`\b`). This can be worked around
5057    /// by either using an ASCII word boundary (`(?-u:\b)`) or by enabling
5058    /// Unicode word boundaries when building a DFA.
5059    Unsupported(&'static str),
5060    /// An error that occurs if too many states are produced while building a
5061    /// DFA.
5062    TooManyStates,
5063    /// An error that occurs if too many start states are needed while building
5064    /// a DFA.
5065    ///
5066    /// This is a kind of oddball error that occurs when building a DFA with
5067    /// start states enabled for each pattern and enough patterns to cause
5068    /// the table of start states to overflow `usize`.
5069    TooManyStartStates,
5070    /// This is another oddball error that can occur if there are too many
5071    /// patterns spread out across too many match states.
5072    TooManyMatchPatternIDs,
5073    /// An error that occurs if the DFA got too big during determinization.
5074    DFAExceededSizeLimit { limit: usize },
5075    /// An error that occurs if auxiliary storage (not the DFA) used during
5076    /// determinization got too big.
5077    DeterminizeExceededSizeLimit { limit: usize },
5078}
5079
5080#[cfg(feature = "dfa-build")]
5081impl BuildError {
5082    /// Return the kind of this error.
5083    fn kind(&self) -> &BuildErrorKind {
5084        &self.kind
5085    }
5086
5087    pub(crate) fn nfa(err: thompson::BuildError) -> BuildError {
5088        BuildError { kind: BuildErrorKind::NFA(err) }
5089    }
5090
5091    pub(crate) fn unsupported_dfa_word_boundary_unicode() -> BuildError {
5092        let msg = "cannot build DFAs for regexes with Unicode word \
5093                   boundaries; switch to ASCII word boundaries, or \
5094                   heuristically enable Unicode word boundaries or use a \
5095                   different regex engine";
5096        BuildError { kind: BuildErrorKind::Unsupported(msg) }
5097    }
5098
5099    pub(crate) fn too_many_states() -> BuildError {
5100        BuildError { kind: BuildErrorKind::TooManyStates }
5101    }
5102
5103    pub(crate) fn too_many_start_states() -> BuildError {
5104        BuildError { kind: BuildErrorKind::TooManyStartStates }
5105    }
5106
5107    pub(crate) fn too_many_match_pattern_ids() -> BuildError {
5108        BuildError { kind: BuildErrorKind::TooManyMatchPatternIDs }
5109    }
5110
5111    pub(crate) fn dfa_exceeded_size_limit(limit: usize) -> BuildError {
5112        BuildError { kind: BuildErrorKind::DFAExceededSizeLimit { limit } }
5113    }
5114
5115    pub(crate) fn determinize_exceeded_size_limit(limit: usize) -> BuildError {
5116        BuildError {
5117            kind: BuildErrorKind::DeterminizeExceededSizeLimit { limit },
5118        }
5119    }
5120}
5121
5122#[cfg(all(feature = "std", feature = "dfa-build"))]
5123impl std::error::Error for BuildError {
5124    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
5125        match self.kind() {
5126            BuildErrorKind::NFA(ref err) => Some(err),
5127            _ => None,
5128        }
5129    }
5130}
5131
5132#[cfg(feature = "dfa-build")]
5133impl core::fmt::Display for BuildError {
5134    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
5135        match self.kind() {
5136            BuildErrorKind::NFA(_) => write!(f, "error building NFA"),
5137            BuildErrorKind::Unsupported(ref msg) => {
5138                write!(f, "unsupported regex feature for DFAs: {}", msg)
5139            }
5140            BuildErrorKind::TooManyStates => write!(
5141                f,
5142                "number of DFA states exceeds limit of {}",
5143                StateID::LIMIT,
5144            ),
5145            BuildErrorKind::TooManyStartStates => {
5146                let stride = Start::len();
5147                // The start table has `stride` entries for starting states for
5148                // the entire DFA, and then `stride` entries for each pattern
5149                // if start states for each pattern are enabled (which is the
5150                // only way this error can occur). Thus, the total number of
5151                // patterns that can fit in the table is `stride` less than
5152                // what we can allocate.
5153                let max = usize::try_from(core::isize::MAX).unwrap();
5154                let limit = (max - stride) / stride;
5155                write!(
5156                    f,
5157                    "compiling DFA with start states exceeds pattern \
5158                     pattern limit of {}",
5159                    limit,
5160                )
5161            }
5162            BuildErrorKind::TooManyMatchPatternIDs => write!(
5163                f,
5164                "compiling DFA with total patterns in all match states \
5165                 exceeds limit of {}",
5166                PatternID::LIMIT,
5167            ),
5168            BuildErrorKind::DFAExceededSizeLimit { limit } => write!(
5169                f,
5170                "DFA exceeded size limit of {:?} during determinization",
5171                limit,
5172            ),
5173            BuildErrorKind::DeterminizeExceededSizeLimit { limit } => {
5174                write!(f, "determinization exceeded size limit of {:?}", limit)
5175            }
5176        }
5177    }
5178}
5179
5180#[cfg(all(test, feature = "syntax", feature = "dfa-build"))]
5181mod tests {
5182    use crate::{Input, MatchError};
5183
5184    use super::*;
5185
5186    #[test]
5187    fn errors_with_unicode_word_boundary() {
5188        let pattern = r"\b";
5189        assert!(Builder::new().build(pattern).is_err());
5190    }
5191
5192    #[test]
5193    fn roundtrip_never_match() {
5194        let dfa = DFA::never_match().unwrap();
5195        let (buf, _) = dfa.to_bytes_native_endian();
5196        let dfa: DFA<&[u32]> = DFA::from_bytes(&buf).unwrap().0;
5197
5198        assert_eq!(None, dfa.try_search_fwd(&Input::new("foo12345")).unwrap());
5199    }
5200
5201    #[test]
5202    fn roundtrip_always_match() {
5203        use crate::HalfMatch;
5204
5205        let dfa = DFA::always_match().unwrap();
5206        let (buf, _) = dfa.to_bytes_native_endian();
5207        let dfa: DFA<&[u32]> = DFA::from_bytes(&buf).unwrap().0;
5208
5209        assert_eq!(
5210            Some(HalfMatch::must(0, 0)),
5211            dfa.try_search_fwd(&Input::new("foo12345")).unwrap()
5212        );
5213    }
5214
5215    // See the analogous test in src/hybrid/dfa.rs.
5216    #[test]
5217    fn heuristic_unicode_reverse() {
5218        let dfa = DFA::builder()
5219            .configure(DFA::config().unicode_word_boundary(true))
5220            .thompson(thompson::Config::new().reverse(true))
5221            .build(r"\b[0-9]+\b")
5222            .unwrap();
5223
5224        let input = Input::new("β123").range(2..);
5225        let expected = MatchError::quit(0xB2, 1);
5226        let got = dfa.try_search_rev(&input);
5227        assert_eq!(Err(expected), got);
5228
5229        let input = Input::new("123β").range(..3);
5230        let expected = MatchError::quit(0xCE, 3);
5231        let got = dfa.try_search_rev(&input);
5232        assert_eq!(Err(expected), got);
5233    }
5234}