dense.rs source code [crates/regex-automata-0.4.9/src/dfa/dense.rs]

1	/!*
2	Types and routines specific to dense DFAs.
3
4	This module is the home of [`dense::DFA`](DFA).
5
6	This 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")]
11	use core::cmp;
12	use core::{fmt, iter, mem::size_of, slice};
13
14	#[cfg(feature = "dfa-build")]
15	use alloc::{
16	collections::{BTreeMap, BTreeSet},
17	vec,
18	vec::Vec,
19	};
20
21	#[cfg(feature = "dfa-build")]
22	use crate::{
23	dfa::{
24	accel::Accel, determinize, minimize::Minimizer, remapper::Remapper,
25	sparse,
26	},
27	nfa::thompson,
28	util::{look::LookMatcher, search::MatchKind},
29	};
30	use 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.
50	const 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.
56	const 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)]
74	pub 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")]
97	impl 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(nklogn)` time and `O(kn)`*
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)]
1133	pub struct Builder {
1134	config: Config,
1135	#[cfg(feature = "syntax")]
1136	thompson: thompson::Compiler,
1137	}
1138
1139	#[cfg(feature = "dfa-build")]
1140	impl 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")]
1320	impl 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")]
1332	pub(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)]
1390	pub 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")]
1444	impl 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")]
1491	impl 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")]
1557	impl 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
1575	impl<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.
1737	impl<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
2161	impl<'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	// The following methods implement mutable routines on the internal
2473	// representation of a DFA. As such, we must fix the first type parameter to a
2474	// `Vec<u32>` since a generic `T: AsRef<[u32]>` does not permit mutation. We
2475	// can get away with this because these methods are internal to the crate and
2476	// are exclusively used during construction of the DFA.
2477	#[cfg(feature = "dfa-build")]
2478	impl OwnedDFA {
2479	/// Add a start state of this DFA.
2480	pub(crate) fn set_start_state(
2481	&mut self,
2482	anchored: Anchored,
2483	start: Start,
2484	id: StateID,
2485	) {
2486	assert!(self.tt.is_valid(id), "invalid start state");
2487	self.st.set_start(anchored, start, id);
2488	}
2489
2490	/// Set the given transition to this DFA. Both the `from` and `to` states
2491	/// must already exist.
2492	pub(crate) fn set_transition(
2493	&mut self,
2494	from: StateID,
2495	byte: alphabet::Unit,
2496	to: StateID,
2497	) {
2498	self.tt.set(from, byte, to);
2499	}
2500
2501	/// An empty state (a state where all transitions lead to a dead state)
2502	/// and return its identifier. The identifier returned is guaranteed to
2503	/// not point to any other existing state.
2504	///
2505	/// If adding a state would exceed `StateID::LIMIT`, then this returns an
2506	/// error.
2507	pub(crate) fn add_empty_state(&mut self) -> Result<StateID, BuildError> {
2508	self.tt.add_empty_state()
2509	}
2510
2511	/// Swap the two states given in the transition table.
2512	///
2513	/// This routine does not do anything to check the correctness of this
2514	/// swap. Callers must ensure that other states pointing to id1 and id2 are
2515	/// updated appropriately.
2516	pub(crate) fn swap_states(&mut self, id1: StateID, id2: StateID) {
2517	self.tt.swap(id1, id2);
2518	}
2519
2520	/// Remap all of the state identifiers in this DFA according to the map
2521	/// function given. This includes all transitions and all starting state
2522	/// identifiers.
2523	pub(crate) fn remap(&mut self, map: impl Fn(StateID) -> StateID) {
2524	// We could loop over each state ID and call 'remap_state' here, but
2525	// this is more direct: just map every transition directly. This
2526	// technically might do a little extra work since the alphabet length
2527	// is likely less than the stride, but if that is indeed an issue we
2528	// should benchmark it and fix it.
2529	for sid in self.tt.table_mut().iter_mut() {
2530	sid = map(sid);
2531	}
2532	for sid in self.st.table_mut().iter_mut() {
2533	sid = map(sid);
2534	}
2535	}
2536
2537	/// Remap the transitions for the state given according to the function
2538	/// given. This applies the given map function to every transition in the
2539	/// given state and changes the transition in place to the result of the
2540	/// map function for that transition.
2541	pub(crate) fn remap_state(
2542	&mut self,
2543	id: StateID,
2544	map: impl Fn(StateID) -> StateID,
2545	) {
2546	self.tt.remap(id, map);
2547	}
2548
2549	/// Truncate the states in this DFA to the given length.
2550	///
2551	/// This routine does not do anything to check the correctness of this
2552	/// truncation. Callers must ensure that other states pointing to truncated
2553	/// states are updated appropriately.
2554	pub(crate) fn truncate_states(&mut self, len: usize) {
2555	self.tt.truncate(len);
2556	}
2557
2558	/// Minimize this DFA in place using Hopcroft's algorithm.
2559	pub(crate) fn minimize(&mut self) {
2560	Minimizer::new(self).run();
2561	}
2562
2563	/// Updates the match state pattern ID map to use the one provided.
2564	///
2565	/// This is useful when it's convenient to manipulate matching states
2566	/// (and their corresponding pattern IDs) as a map. In particular, the
2567	/// representation used by a DFA for this map is not amenable to mutation,
2568	/// so if things need to be changed (like when shuffling states), it's
2569	/// often easier to work with the map form.
2570	pub(crate) fn set_pattern_map(
2571	&mut self,
2572	map: &BTreeMap<StateID, Vec<PatternID>>,
2573	) -> Result<(), BuildError> {
2574	self.ms = self.ms.new_with_map(map)?;
2575	Ok(())
2576	}
2577
2578	/// Find states that have a small number of non-loop transitions and mark
2579	/// them as candidates for acceleration during search.
2580	pub(crate) fn accelerate(&mut self) {
2581	// dead and quit states can never be accelerated.
2582	if self.state_len() <= `2` {
2583	return;
2584	}
2585
2586	// Go through every state and record their accelerator, if possible.
2587	let mut accels = BTreeMap::new();
2588	// Count the number of accelerated match, start and non-match/start
2589	// states.
2590	let (mut cmatch, mut cstart, mut cnormal) = (`0`, `0`, `0`);
2591	for state in self.states() {
2592	if let Some(accel) = state.accelerate(self.byte_classes()) {
2593	debug!(
2594	"accelerating full DFA state {}: {:?}",
2595	state.id().as_usize(),
2596	accel,
2597	);
2598	accels.insert(state.id(), accel);
2599	if self.is_match_state(state.id()) {
2600	cmatch += `1`;
2601	} else if self.is_start_state(state.id()) {
2602	cstart += `1`;
2603	} else {
2604	assert!(!self.is_dead_state(state.id()));
2605	assert!(!self.is_quit_state(state.id()));
2606	cnormal += `1`;
2607	}
2608	}
2609	}
2610	// If no states were able to be accelerated, then we're done.
2611	if accels.is_empty() {
2612	return;
2613	}
2614	let original_accels_len = accels.len();
2615
2616	// A remapper keeps track of state ID changes. Once we're done
2617	// shuffling, the remapper is used to rewrite all transitions in the
2618	// DFA based on the new positions of states.
2619	let mut remapper = Remapper::new(self);
2620
2621	// As we swap states, if they are match states, we need to swap their
2622	// pattern ID lists too (for multi-regexes). We do this by converting
2623	// the lists to an easily swappable map, and then convert back to
2624	// MatchStates once we're done.
2625	let mut new_matches = self.ms.to_map(self);
2626
2627	// There is at least one state that gets accelerated, so these are
2628	// guaranteed to get set to sensible values below.
2629	self.special.min_accel = StateID::MAX;
2630	self.special.max_accel = StateID::ZERO;
2631	let update_special_accel =
2632	\|special: &mut Special, accel_id: StateID\| {
2633	special.min_accel = cmp::min(special.min_accel, accel_id);
2634	special.max_accel = cmp::max(special.max_accel, accel_id);
2635	};
2636
2637	// Start by shuffling match states. Any match states that are
2638	// accelerated get moved to the end of the match state range.
2639	if cmatch > `0` && self.special.matches() {
2640	// N.B. special.{min,max}_match do not need updating, since the
2641	// range/number of match states does not change. Only the ordering
2642	// of match states may change.
2643	let mut next_id = self.special.max_match;
2644	let mut cur_id = next_id;
2645	while cur_id >= self.special.min_match {
2646	if let Some(accel) = accels.remove(&cur_id) {
2647	accels.insert(next_id, accel);
2648	update_special_accel(&mut self.special, next_id);
2649
2650	// No need to do any actual swapping for equivalent IDs.
2651	if cur_id != next_id {
2652	remapper.swap(self, cur_id, next_id);
2653
2654	// Swap pattern IDs for match states.
2655	let cur_pids = new_matches.remove(&cur_id).unwrap();
2656	let next_pids = new_matches.remove(&next_id).unwrap();
2657	new_matches.insert(cur_id, next_pids);
2658	new_matches.insert(next_id, cur_pids);
2659	}
2660	next_id = self.tt.prev_state_id(next_id);
2661	}
2662	cur_id = self.tt.prev_state_id(cur_id);
2663	}
2664	}
2665
2666	// This is where it gets tricky. Without acceleration, start states
2667	// normally come right after match states. But we want accelerated
2668	// states to be a single contiguous range (to make it very fast
2669	// to determine whether a state is* accelerated), while also keeping*
2670	// match and starting states as contiguous ranges for the same reason.
2671	// So what we do here is shuffle states such that it looks like this:
2672	//
2673	// DQMMMMAAAAASSSSSSNNNNNNN
2674	// \| \|
2675	// \|---------\|
2676	// accelerated states
2677	//
2678	// Where:
2679	// D - dead state
2680	// Q - quit state
2681	// M - match state (may be accelerated)
2682	// A - normal state that is accelerated
2683	// S - start state (may be accelerated)
2684	// N - normal state that is NOT accelerated
2685	//
2686	// We implement this by shuffling states, which is done by a sequence
2687	// of pairwise swaps. We start by looking at all normal states to be
2688	// accelerated. When we find one, we swap it with the earliest starting
2689	// state, and then swap that with the earliest normal state. This
2690	// preserves the contiguous property.
2691	//
2692	// Once we're done looking for accelerated normal states, now we look
2693	// for accelerated starting states by moving them to the beginning
2694	// of the starting state range (just like we moved accelerated match
2695	// states to the end of the matching state range).
2696	//
2697	// For a more detailed/different perspective on this, see the docs
2698	// in dfa/special.rs.
2699	if cnormal > `0` {
2700	// our next available starting and normal states for swapping.
2701	let mut next_start_id = self.special.min_start;
2702	let mut cur_id = self.to_state_id(self.state_len() - `1`);
2703	// This is guaranteed to exist since cnormal > 0.
2704	let mut next_norm_id =
2705	self.tt.next_state_id(self.special.max_start);
2706	while cur_id >= next_norm_id {
2707	if let Some(accel) = accels.remove(&cur_id) {
2708	remapper.swap(self, next_start_id, cur_id);
2709	remapper.swap(self, next_norm_id, cur_id);
2710	// Keep our accelerator map updated with new IDs if the
2711	// states we swapped were also accelerated.
2712	if let Some(accel2) = accels.remove(&next_norm_id) {
2713	accels.insert(cur_id, accel2);
2714	}
2715	if let Some(accel2) = accels.remove(&next_start_id) {
2716	accels.insert(next_norm_id, accel2);
2717	}
2718	accels.insert(next_start_id, accel);
2719	update_special_accel(&mut self.special, next_start_id);
2720	// Our start range shifts one to the right now.
2721	self.special.min_start =
2722	self.tt.next_state_id(self.special.min_start);
2723	self.special.max_start =
2724	self.tt.next_state_id(self.special.max_start);
2725	next_start_id = self.tt.next_state_id(next_start_id);
2726	next_norm_id = self.tt.next_state_id(next_norm_id);
2727	}
2728	// This is pretty tricky, but if our 'next_norm_id' state also
2729	// happened to be accelerated, then the result is that it is
2730	// now in the position of cur_id, so we need to consider it
2731	// again. This loop is still guaranteed to terminate though,
2732	// because when accels contains cur_id, we're guaranteed to
2733	// increment next_norm_id even if cur_id remains unchanged.
2734	if !accels.contains_key(&cur_id) {
2735	cur_id = self.tt.prev_state_id(cur_id);
2736	}
2737	}
2738	}
2739	// Just like we did for match states, but we want to move accelerated
2740	// start states to the beginning of the range instead of the end.
2741	if cstart > `0` {
2742	// N.B. special.{min,max}_start do not need updating, since the
2743	// range/number of start states does not change at this point. Only
2744	// the ordering of start states may change.
2745	let mut next_id = self.special.min_start;
2746	let mut cur_id = next_id;
2747	while cur_id <= self.special.max_start {
2748	if let Some(accel) = accels.remove(&cur_id) {
2749	remapper.swap(self, cur_id, next_id);
2750	accels.insert(next_id, accel);
2751	update_special_accel(&mut self.special, next_id);
2752	next_id = self.tt.next_state_id(next_id);
2753	}
2754	cur_id = self.tt.next_state_id(cur_id);
2755	}
2756	}
2757
2758	// Remap all transitions in our DFA and assert some things.
2759	remapper.remap(self);
2760	// This unwrap is OK because acceleration never changes the number of
2761	// match states or patterns in those match states. Since acceleration
2762	// runs after the pattern map has been set at least once, we know that
2763	// our match states cannot error.
2764	self.set_pattern_map(&new_matches).unwrap();
2765	self.special.set_max();
2766	self.special.validate().expect("special state ranges should validate");
2767	self.special
2768	.validate_state_len(self.state_len(), self.stride2())
2769	.expect(
2770	"special state ranges should be consistent with state length",
2771	);
2772	assert_eq!(
2773	self.special.accel_len(self.stride()),
2774	// We record the number of accelerated states initially detected
2775	// since the accels map is itself mutated in the process above.
2776	// If mutated incorrectly, its size may change, and thus can't be
2777	// trusted as a source of truth of how many accelerated states we
2778	// expected there to be.
2779	original_accels_len,
2780	"mismatch with expected number of accelerated states",
2781	);
2782
2783	// And finally record our accelerators. We kept our accels map updated
2784	// as we shuffled states above, so the accelerators should now
2785	// correspond to a contiguous range in the state ID space. (Which we
2786	// assert.)
2787	let mut prev: Option<StateID> = None;
2788	for (id, accel) in accels {
2789	assert!(prev.map_or(`true`, \|p\| self.tt.next_state_id(p) == id));
2790	prev = Some(id);
2791	self.accels.add(accel);
2792	}
2793	}
2794
2795	/// Shuffle the states in this DFA so that starting states, match
2796	/// states and accelerated states are all contiguous.
2797	///
2798	/// See dfa/special.rs for more details.
2799	pub(crate) fn shuffle(
2800	&mut self,
2801	mut matches: BTreeMap<StateID, Vec<PatternID>>,
2802	) -> Result<(), BuildError> {
2803	// The determinizer always adds a quit state and it is always second.
2804	self.special.quit_id = self.to_state_id(`1`);
2805	// If all we have are the dead and quit states, then we're done and
2806	// the DFA will never produce a match.
2807	if self.state_len() <= `2` {
2808	self.special.set_max();
2809	return Ok(());
2810	}
2811
2812	// Collect all our non-DEAD start states into a convenient set and
2813	// confirm there is no overlap with match states. In the classicl DFA
2814	// construction, start states can be match states. But because of
2815	// look-around, we delay all matches by a byte, which prevents start
2816	// states from being match states.
2817	let mut is_start: BTreeSet<StateID> = BTreeSet::new();
2818	for (start_id, _, _) in self.starts() {
2819	// If a starting configuration points to a DEAD state, then we
2820	// don't want to shuffle it. The DEAD state is always the first
2821	// state with ID=0. So we can just leave it be.
2822	if start_id == DEAD {
2823	continue;
2824	}
2825	assert!(
2826	!matches.contains_key(&start_id),
2827	"{:?} is both a start and a match state, which is not allowed",
2828	start_id,
2829	);
2830	is_start.insert(start_id);
2831	}
2832
2833	// We implement shuffling by a sequence of pairwise swaps of states.
2834	// Since we have a number of things referencing states via their
2835	// IDs and swapping them changes their IDs, we need to record every
2836	// swap we make so that we can remap IDs. The remapper handles this
2837	// book-keeping for us.
2838	let mut remapper = Remapper::new(self);
2839
2840	// Shuffle matching states.
2841	if matches.is_empty() {
2842	self.special.min_match = DEAD;
2843	self.special.max_match = DEAD;
2844	} else {
2845	// The determinizer guarantees that the first two states are the
2846	// dead and quit states, respectively. We want our match states to
2847	// come right after quit.
2848	let mut next_id = self.to_state_id(`2`);
2849	let mut new_matches = BTreeMap::new();
2850	self.special.min_match = next_id;
2851	for (id, pids) in matches {
2852	remapper.swap(self, next_id, id);
2853	new_matches.insert(next_id, pids);
2854	// If we swapped a start state, then update our set.
2855	if is_start.contains(&next_id) {
2856	is_start.remove(&next_id);
2857	is_start.insert(id);
2858	}
2859	next_id = self.tt.next_state_id(next_id);
2860	}
2861	matches = new_matches;
2862	self.special.max_match = cmp::max(
2863	self.special.min_match,
2864	self.tt.prev_state_id(next_id),
2865	);
2866	}
2867
2868	// Shuffle starting states.
2869	{
2870	let mut next_id = self.to_state_id(`2`);
2871	if self.special.matches() {
2872	next_id = self.tt.next_state_id(self.special.max_match);
2873	}
2874	self.special.min_start = next_id;
2875	for id in is_start {
2876	remapper.swap(self, next_id, id);
2877	next_id = self.tt.next_state_id(next_id);
2878	}
2879	self.special.max_start = cmp::max(
2880	self.special.min_start,
2881	self.tt.prev_state_id(next_id),
2882	);
2883	}
2884
2885	// Finally remap all transitions in our DFA.
2886	remapper.remap(self);
2887	self.set_pattern_map(&matches)?;
2888	self.special.set_max();
2889	self.special.validate().expect("special state ranges should validate");
2890	self.special
2891	.validate_state_len(self.state_len(), self.stride2())
2892	.expect(
2893	"special state ranges should be consistent with state length",
2894	);
2895	Ok(())
2896	}
2897
2898	/// Checks whether there are universal start states (both anchored and
2899	/// unanchored), and if so, sets the relevant fields to the start state
2900	/// IDs.
2901	///
2902	/// Universal start states occur precisely when the all patterns in the
2903	/// DFA have no look-around assertions in their prefix.
2904	fn set_universal_starts(&mut self) {
2905	assert_eq!(`6`, Start::len(), "expected 6 start configurations");
2906
2907	let start_id = \|dfa: &mut OwnedDFA,
2908	anchored: Anchored,
2909	start: Start\| {
2910	// This OK because we only call 'start' under conditions
2911	// in which we know it will succeed.
2912	dfa.st.start(anchored, start).expect("valid Input configuration")
2913	};
2914	if self.start_kind().has_unanchored() {
2915	let anchor = Anchored::No;
2916	let sid = start_id(self, anchor, Start::NonWordByte);
2917	if sid == start_id(self, anchor, Start::WordByte)
2918	&& sid == start_id(self, anchor, Start::Text)
2919	&& sid == start_id(self, anchor, Start::LineLF)
2920	&& sid == start_id(self, anchor, Start::LineCR)
2921	&& sid == start_id(self, anchor, Start::CustomLineTerminator)
2922	{
2923	self.st.universal_start_unanchored = Some(sid);
2924	}
2925	}
2926	if self.start_kind().has_anchored() {
2927	let anchor = Anchored::Yes;
2928	let sid = start_id(self, anchor, Start::NonWordByte);
2929	if sid == start_id(self, anchor, Start::WordByte)
2930	&& sid == start_id(self, anchor, Start::Text)
2931	&& sid == start_id(self, anchor, Start::LineLF)
2932	&& sid == start_id(self, anchor, Start::LineCR)
2933	&& sid == start_id(self, anchor, Start::CustomLineTerminator)
2934	{
2935	self.st.universal_start_anchored = Some(sid);
2936	}
2937	}
2938	}
2939	}
2940
2941	// A variety of generic internal methods for accessing DFA internals.
2942	impl<T: AsRef<[u32]>> DFA<T> {
2943	/// Return the info about special states.
2944	pub(crate) fn special(&self) -> &Special {
2945	&self.special
2946	}
2947
2948	/// Return the info about special states as a mutable borrow.
2949	#[cfg(feature = "dfa-build")]
2950	pub(crate) fn special_mut(&mut self) -> &mut Special {
2951	&mut self.special
2952	}
2953
2954	/// Returns the quit set (may be empty) used by this DFA.
2955	pub(crate) fn quitset(&self) -> &ByteSet {
2956	&self.quitset
2957	}
2958
2959	/// Returns the flags for this DFA.
2960	pub(crate) fn flags(&self) -> &Flags {
2961	&self.flags
2962	}
2963
2964	/// Returns an iterator over all states in this DFA.
2965	///
2966	/// This iterator yields a tuple for each state. The first element of the
2967	/// tuple corresponds to a state's identifier, and the second element
2968	/// corresponds to the state itself (comprised of its transitions).
2969	pub(crate) fn states(&self) -> StateIter<'_, T> {
2970	self.tt.states()
2971	}
2972
2973	/// Return the total number of states in this DFA. Every DFA has at least
2974	/// 1 state, even the empty DFA.
2975	pub(crate) fn state_len(&self) -> usize {
2976	self.tt.len()
2977	}
2978
2979	/// Return an iterator over all pattern IDs for the given match state.
2980	///
2981	/// If the given state is not a match state, then this panics.
2982	#[cfg(feature = "dfa-build")]
2983	pub(crate) fn pattern_id_slice(&self, id: StateID) -> &[PatternID] {
2984	assert!(self.is_match_state(id));
2985	self.ms.pattern_id_slice(self.match_state_index(id))
2986	}
2987
2988	/// Return the total number of pattern IDs for the given match state.
2989	///
2990	/// If the given state is not a match state, then this panics.
2991	pub(crate) fn match_pattern_len(&self, id: StateID) -> usize {
2992	assert!(self.is_match_state(id));
2993	self.ms.pattern_len(self.match_state_index(id))
2994	}
2995
2996	/// Returns the total number of patterns matched by this DFA.
2997	pub(crate) fn pattern_len(&self) -> usize {
2998	self.ms.pattern_len
2999	}
3000
3001	/// Returns a map from match state ID to a list of pattern IDs that match
3002	/// in that state.
3003	#[cfg(feature = "dfa-build")]
3004	pub(crate) fn pattern_map(&self) -> BTreeMap<StateID, Vec<PatternID>> {
3005	self.ms.to_map(self)
3006	}
3007
3008	/// Returns the ID of the quit state for this DFA.
3009	#[cfg(feature = "dfa-build")]
3010	pub(crate) fn quit_id(&self) -> StateID {
3011	self.to_state_id(`1`)
3012	}
3013
3014	/// Convert the given state identifier to the state's index. The state's
3015	/// index corresponds to the position in which it appears in the transition
3016	/// table. When a DFA is NOT premultiplied, then a state's identifier is
3017	/// also its index. When a DFA is premultiplied, then a state's identifier
3018	/// is equal to `index alphabet_len`. This routine reverses that.*
3019	pub(crate) fn to_index(&self, id: StateID) -> usize {
3020	self.tt.to_index(id)
3021	}
3022
3023	/// Convert an index to a state (in the range 0..self.state_len()) to an
3024	/// actual state identifier.
3025	///
3026	/// This is useful when using a `Vec<T>` as an efficient map keyed by state
3027	/// to some other information (such as a remapped state ID).
3028	#[cfg(feature = "dfa-build")]
3029	pub(crate) fn to_state_id(&self, index: usize) -> StateID {
3030	self.tt.to_state_id(index)
3031	}
3032
3033	/// Return the table of state IDs for this DFA's start states.
3034	pub(crate) fn starts(&self) -> StartStateIter<'_> {
3035	self.st.iter()
3036	}
3037
3038	/// Returns the index of the match state for the given ID. If the
3039	/// given ID does not correspond to a match state, then this may
3040	/// panic or produce an incorrect result.
3041	#[cfg_attr(feature = "perf-inline", inline(always))]
3042	fn match_state_index(&self, id: StateID) -> usize {
3043	debug_assert!(self.is_match_state(id));
3044	// This is one of the places where we rely on the fact that match
3045	// states are contiguous in the transition table. Namely, that the
3046	// first match state ID always corresponds to dfa.special.min_match.
3047	// From there, since we know the stride, we can compute the overall
3048	// index of any match state given the match state's ID.
3049	let min = self.special().min_match.as_usize();
3050	// CORRECTNESS: We're allowed to produce an incorrect result or panic,
3051	// so both the subtraction and the unchecked StateID construction is
3052	// OK.
3053	self.to_index(StateID::new_unchecked(id.as_usize() - min))
3054	}
3055
3056	/// Returns the index of the accelerator state for the given ID. If the
3057	/// given ID does not correspond to an accelerator state, then this may
3058	/// panic or produce an incorrect result.
3059	fn accelerator_index(&self, id: StateID) -> usize {
3060	let min = self.special().min_accel.as_usize();
3061	// CORRECTNESS: We're allowed to produce an incorrect result or panic,
3062	// so both the subtraction and the unchecked StateID construction is
3063	// OK.
3064	self.to_index(StateID::new_unchecked(id.as_usize() - min))
3065	}
3066
3067	/// Return the accelerators for this DFA.
3068	fn accels(&self) -> Accels<&[u32]> {
3069	self.accels.as_ref()
3070	}
3071
3072	/// Return this DFA's transition table as a slice.
3073	fn trans(&self) -> &[StateID] {
3074	self.tt.table()
3075	}
3076	}
3077
3078	impl<T: AsRef<[u32]>> fmt::Debug for DFA<T> {
3079	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3080	writeln!(f, "dense::DFA(")?;
3081	for state in self.states() {
3082	fmt_state_indicator(f, self, state.id())?;
3083	let id = if f.alternate() {
3084	state.id().as_usize()
3085	} else {
3086	self.to_index(state.id())
3087	};
3088	write!(f, "{:`06`?}: ", id)?;
3089	state.fmt(f)?;
3090	write!(f, "`\n`")?;
3091	}
3092	writeln!(f, "")?;
3093	for (i, (start_id, anchored, sty)) in self.starts().enumerate() {
3094	let id = if f.alternate() {
3095	start_id.as_usize()
3096	} else {
3097	self.to_index(start_id)
3098	};
3099	if i % self.st.stride == `0` {
3100	match anchored {
3101	Anchored::No => writeln!(f, "START-GROUP(unanchored)")?,
3102	Anchored::Yes => writeln!(f, "START-GROUP(anchored)")?,
3103	Anchored::Pattern(pid) => {
3104	writeln!(f, "START_GROUP(pattern: {:?})", pid)?
3105	}
3106	}
3107	}
3108	writeln!(f, " {:?} => {:`06`?}", sty, id)?;
3109	}
3110	if self.pattern_len() > `1` {
3111	writeln!(f, "")?;
3112	for i in `0`..self.ms.len() {
3113	let id = self.ms.match_state_id(self, i);
3114	let id = if f.alternate() {
3115	id.as_usize()
3116	} else {
3117	self.to_index(id)
3118	};
3119	write!(f, "MATCH({:`06`?}): ", id)?;
3120	for (i, &pid) in self.ms.pattern_id_slice(i).iter().enumerate()
3121	{
3122	if i > `0` {
3123	write!(f, ", ")?;
3124	}
3125	write!(f, "{:?}", pid)?;
3126	}
3127	writeln!(f, "")?;
3128	}
3129	}
3130	writeln!(f, "state length: {:?}", self.state_len())?;
3131	writeln!(f, "pattern length: {:?}", self.pattern_len())?;
3132	writeln!(f, "flags: {:?}", self.flags)?;
3133	writeln!(f, ")")?;
3134	Ok(())
3135	}
3136	}
3137
3138	// SAFETY: We assert that our implementation of each method is correct.
3139	unsafe impl<T: AsRef<[u32]>> Automaton for DFA<T> {
3140	#[cfg_attr(feature = "perf-inline", inline(always))]
3141	fn is_special_state(&self, id: StateID) -> bool {
3142	self.special.is_special_state(id)
3143	}
3144
3145	#[cfg_attr(feature = "perf-inline", inline(always))]
3146	fn is_dead_state(&self, id: StateID) -> bool {
3147	self.special.is_dead_state(id)
3148	}
3149
3150	#[cfg_attr(feature = "perf-inline", inline(always))]
3151	fn is_quit_state(&self, id: StateID) -> bool {
3152	self.special.is_quit_state(id)
3153	}
3154
3155	#[cfg_attr(feature = "perf-inline", inline(always))]
3156	fn is_match_state(&self, id: StateID) -> bool {
3157	self.special.is_match_state(id)
3158	}
3159
3160	#[cfg_attr(feature = "perf-inline", inline(always))]
3161	fn is_start_state(&self, id: StateID) -> bool {
3162	self.special.is_start_state(id)
3163	}
3164
3165	#[cfg_attr(feature = "perf-inline", inline(always))]
3166	fn is_accel_state(&self, id: StateID) -> bool {
3167	self.special.is_accel_state(id)
3168	}
3169
3170	#[cfg_attr(feature = "perf-inline", inline(always))]
3171	fn next_state(&self, current: StateID, input: u8) -> StateID {
3172	let input = self.byte_classes().get(input);
3173	let o = current.as_usize() + usize::from(input);
3174	self.trans()[o]
3175	}
3176
3177	#[cfg_attr(feature = "perf-inline", inline(always))]
3178	unsafe fn next_state_unchecked(
3179	&self,
3180	current: StateID,
3181	byte: u8,
3182	) -> StateID {
3183	// We don't (or shouldn't) need an unchecked variant for the byte
3184	// class mapping, since bound checks should be omitted automatically
3185	// by virtue of its representation. If this ends up not being true as
3186	// confirmed by codegen, please file an issue. ---AG
3187	let class = self.byte_classes().get(byte);
3188	let o = current.as_usize() + usize::from(class);
3189	let next = *self.trans().get_unchecked(o);
3190	next
3191	}
3192
3193	#[cfg_attr(feature = "perf-inline", inline(always))]
3194	fn next_eoi_state(&self, current: StateID) -> StateID {
3195	let eoi = self.byte_classes().eoi().as_usize();
3196	let o = current.as_usize() + eoi;
3197	self.trans()[o]
3198	}
3199
3200	#[cfg_attr(feature = "perf-inline", inline(always))]
3201	fn pattern_len(&self) -> usize {
3202	self.ms.pattern_len
3203	}
3204
3205	#[cfg_attr(feature = "perf-inline", inline(always))]
3206	fn match_len(&self, id: StateID) -> usize {
3207	self.match_pattern_len(id)
3208	}
3209
3210	#[cfg_attr(feature = "perf-inline", inline(always))]
3211	fn match_pattern(&self, id: StateID, match_index: usize) -> PatternID {
3212	// This is an optimization for the very common case of a DFA with a
3213	// single pattern. This conditional avoids a somewhat more costly path
3214	// that finds the pattern ID from the state machine, which requires
3215	// a bit of slicing/pointer-chasing. This optimization tends to only
3216	// matter when matches are frequent.
3217	if self.ms.pattern_len == `1` {
3218	return PatternID::ZERO;
3219	}
3220	let state_index = self.match_state_index(id);
3221	self.ms.pattern_id(state_index, match_index)
3222	}
3223
3224	#[cfg_attr(feature = "perf-inline", inline(always))]
3225	fn has_empty(&self) -> bool {
3226	self.flags.has_empty
3227	}
3228
3229	#[cfg_attr(feature = "perf-inline", inline(always))]
3230	fn is_utf8(&self) -> bool {
3231	self.flags.is_utf8
3232	}
3233
3234	#[cfg_attr(feature = "perf-inline", inline(always))]
3235	fn is_always_start_anchored(&self) -> bool {
3236	self.flags.is_always_start_anchored
3237	}
3238
3239	#[cfg_attr(feature = "perf-inline", inline(always))]
3240	fn start_state(
3241	&self,
3242	config: &start::Config,
3243	) -> Result<StateID, StartError> {
3244	let anchored = config.get_anchored();
3245	let start = match config.get_look_behind() {
3246	None => Start::Text,
3247	Some(byte) => {
3248	if !self.quitset.is_empty() && self.quitset.contains(byte) {
3249	return Err(StartError::quit(byte));
3250	}
3251	self.st.start_map.get(byte)
3252	}
3253	};
3254	self.st.start(anchored, start)
3255	}
3256
3257	#[cfg_attr(feature = "perf-inline", inline(always))]
3258	fn universal_start_state(&self, mode: Anchored) -> Option<StateID> {
3259	match mode {
3260	Anchored::No => self.st.universal_start_unanchored,
3261	Anchored::Yes => self.st.universal_start_anchored,
3262	Anchored::Pattern(_) => None,
3263	}
3264	}
3265
3266	#[cfg_attr(feature = "perf-inline", inline(always))]
3267	fn accelerator(&self, id: StateID) -> &[u8] {
3268	if !self.is_accel_state(id) {
3269	return &[];
3270	}
3271	self.accels.needles(self.accelerator_index(id))
3272	}
3273
3274	#[cfg_attr(feature = "perf-inline", inline(always))]
3275	fn get_prefilter(&self) -> Option<&Prefilter> {
3276	self.pre.as_ref()
3277	}
3278	}
3279
3280	/// The transition table portion of a dense DFA.
3281	///
3282	/// The transition table is the core part of the DFA in that it describes how
3283	/// to move from one state to another based on the input sequence observed.
3284	#[derive(Clone)]
3285	pub(crate) struct TransitionTable<T> {
3286	/// A contiguous region of memory representing the transition table in
3287	/// row-major order. The representation is dense. That is, every state
3288	/// has precisely the same number of transitions. The maximum number of
3289	/// transitions per state is 257 (256 for each possible byte value, plus 1
3290	/// for the special EOI transition). If a DFA has been instructed to use
3291	/// byte classes (the default), then the number of transitions is usually
3292	/// substantially fewer.
3293	///
3294	/// In practice, T is either `Vec<u32>` or `&[u32]`.
3295	table: T,
3296	/// A set of equivalence classes, where a single equivalence class
3297	/// represents a set of bytes that never discriminate between a match
3298	/// and a non-match in the DFA. Each equivalence class corresponds to a
3299	/// single character in this DFA's alphabet, where the maximum number of
3300	/// characters is 257 (each possible value of a byte plus the special
3301	/// EOI transition). Consequently, the number of equivalence classes
3302	/// corresponds to the number of transitions for each DFA state. Note
3303	/// though that the space* used by each DFA state in the transition table*
3304	/// may be larger. The total space used by each DFA state is known as the
3305	/// stride.
3306	///
3307	/// The only time the number of equivalence classes is fewer than 257 is if
3308	/// the DFA's kind uses byte classes (which is the default). Equivalence
3309	/// classes should generally only be disabled when debugging, so that
3310	/// the transitions themselves aren't obscured. Disabling them has no
3311	/// other benefit, since the equivalence class map is always used while
3312	/// searching. In the vast majority of cases, the number of equivalence
3313	/// classes is substantially smaller than 257, particularly when large
3314	/// Unicode classes aren't used.
3315	classes: ByteClasses,
3316	/// The stride of each DFA state, expressed as a power-of-two exponent.
3317	///
3318	/// The stride of a DFA corresponds to the total amount of space used by
3319	/// each DFA state in the transition table. This may be bigger than the
3320	/// size of a DFA's alphabet, since the stride is always the smallest
3321	/// power of two greater than or equal to the alphabet size.
3322	///
3323	/// While this wastes space, this avoids the need for integer division
3324	/// to convert between premultiplied state IDs and their corresponding
3325	/// indices. Instead, we can use simple bit-shifts.
3326	///
3327	/// See the docs for the `stride2` method for more details.
3328	///
3329	/// The minimum `stride2` value is `1` (corresponding to a stride of `2`)
3330	/// while the maximum `stride2` value is `9` (corresponding to a stride of
3331	/// `512`). The maximum is not `8` since the maximum alphabet size is `257`
3332	/// when accounting for the special EOI transition. However, an alphabet
3333	/// length of that size is exceptionally rare since the alphabet is shrunk
3334	/// into equivalence classes.
3335	stride2: usize,
3336	}
3337
3338	impl<'a> TransitionTable<&'a [u32]> {
3339	/// Deserialize a transition table starting at the beginning of `slice`.
3340	/// Upon success, return the total number of bytes read along with the
3341	/// transition table.
3342	///
3343	/// If there was a problem deserializing any part of the transition table,
3344	/// then this returns an error. Notably, if the given slice does not have
3345	/// the same alignment as `StateID`, then this will return an error (among
3346	/// other possible errors).
3347	///
3348	/// This is guaranteed to execute in constant time.
3349	///
3350	/// # Safety
3351	///
3352	/// This routine is not safe because it does not check the validity of the
3353	/// transition table itself. In particular, the transition table can be
3354	/// quite large, so checking its validity can be somewhat expensive. An
3355	/// invalid transition table is not safe because other code may rely on the
3356	/// transition table being correct (such as explicit bounds check elision).
3357	/// Therefore, an invalid transition table can lead to undefined behavior.
3358	///
3359	/// Callers that use this function must either pass on the safety invariant
3360	/// or guarantee that the bytes given contain a valid transition table.
3361	/// This guarantee is upheld by the bytes written by `write_to`.
3362	unsafe fn from_bytes_unchecked(
3363	mut slice: &'a [u8],
3364	) -> Result<(TransitionTable<&'a [u32]>, usize), DeserializeError> {
3365	let slice_start = slice.as_ptr().as_usize();
3366
3367	let (state_len, nr) =
3368	wire::try_read_u32_as_usize(slice, "state length")?;
3369	slice = &slice[nr..];
3370
3371	let (stride2, nr) = wire::try_read_u32_as_usize(slice, "stride2")?;
3372	slice = &slice[nr..];
3373
3374	let (classes, nr) = ByteClasses::from_bytes(slice)?;
3375	slice = &slice[nr..];
3376
3377	// The alphabet length (determined by the byte class map) cannot be
3378	// bigger than the stride (total space used by each DFA state).
3379	if stride2 > `9` {
3380	return Err(DeserializeError::generic(
3381	"dense DFA has invalid stride2 (too big)",
3382	));
3383	}
3384	// It also cannot be zero, since even a DFA that never matches anything
3385	// has a non-zero number of states with at least two equivalence
3386	// classes: one for all 256 byte values and another for the EOI
3387	// sentinel.
3388	if stride2 < `1` {
3389	return Err(DeserializeError::generic(
3390	"dense DFA has invalid stride2 (too small)",
3391	));
3392	}
3393	// This is OK since 1 <= stride2 <= 9.
3394	let stride =
3395	`1usize`.checked_shl(u32::try_from(stride2).unwrap()).unwrap();
3396	if classes.alphabet_len() > stride {
3397	return Err(DeserializeError::generic(
3398	"alphabet size cannot be bigger than transition table stride",
3399	));
3400	}
3401
3402	let trans_len =
3403	wire::shl(state_len, stride2, "dense table transition length")?;
3404	let table_bytes_len = wire::mul(
3405	trans_len,
3406	StateID::SIZE,
3407	"dense table state byte length",
3408	)?;
3409	wire::check_slice_len(slice, table_bytes_len, "transition table")?;
3410	wire::check_alignment::<StateID>(slice)?;
3411	let table_bytes = &slice[..table_bytes_len];
3412	slice = &slice[table_bytes_len..];
3413	// SAFETY: Since StateID is always representable as a u32, all we need
3414	// to do is ensure that we have the proper length and alignment. We've
3415	// checked both above, so the cast below is safe.
3416	//
3417	// N.B. This is the only not-safe code in this function.
3418	let table = core::slice::from_raw_parts(
3419	table_bytes.as_ptr().cast::<u32>(),
3420	trans_len,
3421	);
3422	let tt = TransitionTable { table, classes, stride2 };
3423	Ok((tt, slice.as_ptr().as_usize() - slice_start))
3424	}
3425	}
3426
3427	#[cfg(feature = "dfa-build")]
3428	impl TransitionTable<Vec<u32>> {
3429	/// Create a minimal transition table with just two states: a dead state
3430	/// and a quit state. The alphabet length and stride of the transition
3431	/// table is determined by the given set of equivalence classes.
3432	fn minimal(classes: ByteClasses) -> TransitionTable<Vec<u32>> {
3433	let mut tt = TransitionTable {
3434	table: vec![],
3435	classes,
3436	stride2: classes.stride2(),
3437	};
3438	// Two states, regardless of alphabet size, can always fit into u32.
3439	tt.add_empty_state().unwrap(); // dead state
3440	tt.add_empty_state().unwrap(); // quit state
3441	tt
3442	}
3443
3444	/// Set a transition in this table. Both the `from` and `to` states must
3445	/// already exist, otherwise this panics. `unit` should correspond to the
3446	/// transition out of `from` to set to `to`.
3447	fn set(&mut self, from: StateID, unit: alphabet::Unit, to: StateID) {
3448	assert!(self.is_valid(from), "invalid 'from' state");
3449	assert!(self.is_valid(to), "invalid 'to' state");
3450	self.table[from.as_usize() + self.classes.get_by_unit(unit)] =
3451	to.as_u32();
3452	}
3453
3454	/// Add an empty state (a state where all transitions lead to a dead state)
3455	/// and return its identifier. The identifier returned is guaranteed to
3456	/// not point to any other existing state.
3457	///
3458	/// If adding a state would exhaust the state identifier space, then this
3459	/// returns an error.
3460	fn add_empty_state(&mut self) -> Result<StateID, BuildError> {
3461	// Normally, to get a fresh state identifier, we would just
3462	// take the index of the next state added to the transition
3463	// table. However, we actually perform an optimization here
3464	// that premultiplies state IDs by the stride, such that they
3465	// point immediately at the beginning of their transitions in
3466	// the transition table. This avoids an extra multiplication
3467	// instruction for state lookup at search time.
3468	//
3469	// Premultiplied identifiers means that instead of your matching
3470	// loop looking something like this:
3471	//
3472	// state = dfa.start
3473	// for byte in haystack:
3474	// next = dfa.transitions[state stride + byte]*
3475	// if dfa.is_match(next):
3476	// return true
3477	// return false
3478	//
3479	// it can instead look like this:
3480	//
3481	// state = dfa.start
3482	// for byte in haystack:
3483	// next = dfa.transitions[state + byte]
3484	// if dfa.is_match(next):
3485	// return true
3486	// return false
3487	//
3488	// In other words, we save a multiplication instruction in the
3489	// critical path. This turns out to be a decent performance win.
3490	// The cost of using premultiplied state ids is that they can
3491	// require a bigger state id representation. (And they also make
3492	// the code a bit more complex, especially during minimization and
3493	// when reshuffling states, as one needs to convert back and forth
3494	// between state IDs and state indices.)
3495	//
3496	// To do this, we simply take the index of the state into the
3497	// entire transition table, rather than the index of the state
3498	// itself. e.g., If the stride is 64, then the ID of the 3rd state
3499	// is 192, not 2.
3500	let next = self.table.len();
3501	let id =
3502	StateID::new(next).map_err(\|_\| BuildError::too_many_states())?;
3503	self.table.extend(iter::repeat(`0`).take(self.stride()));
3504	Ok(id)
3505	}
3506
3507	/// Swap the two states given in this transition table.
3508	///
3509	/// This routine does not do anything to check the correctness of this
3510	/// swap. Callers must ensure that other states pointing to id1 and id2 are
3511	/// updated appropriately.
3512	///
3513	/// Both id1 and id2 must point to valid states, otherwise this panics.
3514	fn swap(&mut self, id1: StateID, id2: StateID) {
3515	assert!(self.is_valid(id1), "invalid 'id1' state: {:?}", id1);
3516	assert!(self.is_valid(id2), "invalid 'id2' state: {:?}", id2);
3517	// We only need to swap the parts of the state that are used. So if the
3518	// stride is 64, but the alphabet length is only 33, then we save a lot
3519	// of work.
3520	for b in `0`..self.classes.alphabet_len() {
3521	self.table.swap(id1.as_usize() + b, id2.as_usize() + b);
3522	}
3523	}
3524
3525	/// Remap the transitions for the state given according to the function
3526	/// given. This applies the given map function to every transition in the
3527	/// given state and changes the transition in place to the result of the
3528	/// map function for that transition.
3529	fn remap(&mut self, id: StateID, map: impl Fn(StateID) -> StateID) {
3530	for byte in `0`..self.alphabet_len() {
3531	let i = id.as_usize() + byte;
3532	let next = self.table()[i];
3533	self.table_mut()[id.as_usize() + byte] = map(next);
3534	}
3535	}
3536
3537	/// Truncate the states in this transition table to the given length.
3538	///
3539	/// This routine does not do anything to check the correctness of this
3540	/// truncation. Callers must ensure that other states pointing to truncated
3541	/// states are updated appropriately.
3542	fn truncate(&mut self, len: usize) {
3543	self.table.truncate(len << self.stride2);
3544	}
3545	}
3546
3547	impl<T: AsRef<[u32]>> TransitionTable<T> {
3548	/// Writes a serialized form of this transition table to the buffer given.
3549	/// If the buffer is too small, then an error is returned. To determine
3550	/// how big the buffer must be, use `write_to_len`.
3551	fn write_to<E: Endian>(
3552	&self,
3553	mut dst: &mut [u8],
3554	) -> Result<usize, SerializeError> {
3555	let nwrite = self.write_to_len();
3556	if dst.len() < nwrite {
3557	return Err(SerializeError::buffer_too_small("transition table"));
3558	}
3559	dst = &mut dst[..nwrite];
3560
3561	// write state length
3562	// Unwrap is OK since number of states is guaranteed to fit in a u32.
3563	E::write_u32(u32::try_from(self.len()).unwrap(), dst);
3564	dst = &mut dst[size_of::<u32>()..];
3565
3566	// write state stride (as power of 2)
3567	// Unwrap is OK since stride2 is guaranteed to be <= 9.
3568	E::write_u32(u32::try_from(self.stride2).unwrap(), dst);
3569	dst = &mut dst[size_of::<u32>()..];
3570
3571	// write byte class map
3572	let n = self.classes.write_to(dst)?;
3573	dst = &mut dst[n..];
3574
3575	// write actual transitions
3576	for &sid in self.table() {
3577	let n = wire::write_state_id::<E>(sid, &mut dst);
3578	dst = &mut dst[n..];
3579	}
3580	Ok(nwrite)
3581	}
3582
3583	/// Returns the number of bytes the serialized form of this transition
3584	/// table will use.
3585	fn write_to_len(&self) -> usize {
3586	size_of::<u32>() // state length
3587	+ size_of::<u32>() // stride2
3588	+ self.classes.write_to_len()
3589	+ (self.table().len() * StateID::SIZE)
3590	}
3591
3592	/// Validates that every state ID in this transition table is valid.
3593	///
3594	/// That is, every state ID can be used to correctly index a state in this
3595	/// table.
3596	fn validate(&self, dfa: &DFA<T>) -> Result<(), DeserializeError> {
3597	let sp = &dfa.special;
3598	for state in self.states() {
3599	// We check that the ID itself is well formed. That is, if it's
3600	// a special state then it must actually be a quit, dead, accel,
3601	// match or start state.
3602	if sp.is_special_state(state.id()) {
3603	let is_actually_special = sp.is_dead_state(state.id())
3604	\|\| sp.is_quit_state(state.id())
3605	\|\| sp.is_match_state(state.id())
3606	\|\| sp.is_start_state(state.id())
3607	\|\| sp.is_accel_state(state.id());
3608	if !is_actually_special {
3609	// This is kind of a cryptic error message...
3610	return Err(DeserializeError::generic(
3611	"found dense state tagged as special but \
3612	wasn't actually special",
3613	));
3614	}
3615	if sp.is_match_state(state.id())
3616	&& dfa.match_len(state.id()) == `0`
3617	{
3618	return Err(DeserializeError::generic(
3619	"found match state with zero pattern IDs",
3620	));
3621	}
3622	}
3623	for (_, to) in state.transitions() {
3624	if !self.is_valid(to) {
3625	return Err(DeserializeError::generic(
3626	"found invalid state ID in transition table",
3627	));
3628	}
3629	}
3630	}
3631	Ok(())
3632	}
3633
3634	/// Converts this transition table to a borrowed value.
3635	fn as_ref(&self) -> TransitionTable<&'_ [u32]> {
3636	TransitionTable {
3637	table: self.table.as_ref(),
3638	classes: self.classes.clone(),
3639	stride2: self.stride2,
3640	}
3641	}
3642
3643	/// Converts this transition table to an owned value.
3644	#[cfg(feature = "alloc")]
3645	fn to_owned(&self) -> TransitionTable<alloc::vec::Vec<u32>> {
3646	TransitionTable {
3647	table: self.table.as_ref().to_vec(),
3648	classes: self.classes.clone(),
3649	stride2: self.stride2,
3650	}
3651	}
3652
3653	/// Return the state for the given ID. If the given ID is not valid, then
3654	/// this panics.
3655	fn state(&self, id: StateID) -> State<'_> {
3656	assert!(self.is_valid(id));
3657
3658	let i = id.as_usize();
3659	State {
3660	id,
3661	stride2: self.stride2,
3662	transitions: &self.table()[i..i + self.alphabet_len()],
3663	}
3664	}
3665
3666	/// Returns an iterator over all states in this transition table.
3667	///
3668	/// This iterator yields a tuple for each state. The first element of the
3669	/// tuple corresponds to a state's identifier, and the second element
3670	/// corresponds to the state itself (comprised of its transitions).
3671	fn states(&self) -> StateIter<'_, T> {
3672	StateIter {
3673	tt: self,
3674	it: self.table().chunks(self.stride()).enumerate(),
3675	}
3676	}
3677
3678	/// Convert a state identifier to an index to a state (in the range
3679	/// 0..self.len()).
3680	///
3681	/// This is useful when using a `Vec<T>` as an efficient map keyed by state
3682	/// to some other information (such as a remapped state ID).
3683	///
3684	/// If the given ID is not valid, then this may panic or produce an
3685	/// incorrect index.
3686	fn to_index(&self, id: StateID) -> usize {
3687	id.as_usize() >> self.stride2
3688	}
3689
3690	/// Convert an index to a state (in the range 0..self.len()) to an actual
3691	/// state identifier.
3692	///
3693	/// This is useful when using a `Vec<T>` as an efficient map keyed by state
3694	/// to some other information (such as a remapped state ID).
3695	///
3696	/// If the given index is not in the specified range, then this may panic
3697	/// or produce an incorrect state ID.
3698	fn to_state_id(&self, index: usize) -> StateID {
3699	// CORRECTNESS: If the given index is not valid, then it is not
3700	// required for this to panic or return a valid state ID.
3701	StateID::new_unchecked(index << self.stride2)
3702	}
3703
3704	/// Returns the state ID for the state immediately following the one given.
3705	///
3706	/// This does not check whether the state ID returned is invalid. In fact,
3707	/// if the state ID given is the last state in this DFA, then the state ID
3708	/// returned is guaranteed to be invalid.
3709	#[cfg(feature = "dfa-build")]
3710	fn next_state_id(&self, id: StateID) -> StateID {
3711	self.to_state_id(self.to_index(id).checked_add(`1`).unwrap())
3712	}
3713
3714	/// Returns the state ID for the state immediately preceding the one given.
3715	///
3716	/// If the dead ID given (which is zero), then this panics.
3717	#[cfg(feature = "dfa-build")]
3718	fn prev_state_id(&self, id: StateID) -> StateID {
3719	self.to_state_id(self.to_index(id).checked_sub(`1`).unwrap())
3720	}
3721
3722	/// Returns the table as a slice of state IDs.
3723	fn table(&self) -> &[StateID] {
3724	wire::u32s_to_state_ids(self.table.as_ref())
3725	}
3726
3727	/// Returns the total number of states in this transition table.
3728	///
3729	/// Note that a DFA always has at least two states: the dead and quit
3730	/// states. In particular, the dead state always has ID 0 and is
3731	/// correspondingly always the first state. The dead state is never a match
3732	/// state.
3733	fn len(&self) -> usize {
3734	self.table().len() >> self.stride2
3735	}
3736
3737	/// Returns the total stride for every state in this DFA. This corresponds
3738	/// to the total number of transitions used by each state in this DFA's
3739	/// transition table.
3740	fn stride(&self) -> usize {
3741	`1` << self.stride2
3742	}
3743
3744	/// Returns the total number of elements in the alphabet for this
3745	/// transition table. This is always less than or equal to `self.stride()`.
3746	/// It is only equal when the alphabet length is a power of 2. Otherwise,
3747	/// it is always strictly less.
3748	fn alphabet_len(&self) -> usize {
3749	self.classes.alphabet_len()
3750	}
3751
3752	/// Returns true if and only if the given state ID is valid for this
3753	/// transition table. Validity in this context means that the given ID can
3754	/// be used as a valid offset with `self.stride()` to index this transition
3755	/// table.
3756	fn is_valid(&self, id: StateID) -> bool {
3757	let id = id.as_usize();
3758	id < self.table().len() && id % self.stride() == `0`
3759	}
3760
3761	/// Return the memory usage, in bytes, of this transition table.
3762	///
3763	/// This does not include the size of a `TransitionTable` value itself.
3764	fn memory_usage(&self) -> usize {
3765	self.table().len() * StateID::SIZE
3766	}
3767	}
3768
3769	#[cfg(feature = "dfa-build")]
3770	impl<T: AsMut<[u32]>> TransitionTable<T> {
3771	/// Returns the table as a slice of state IDs.
3772	fn table_mut(&mut self) -> &mut [StateID] {
3773	wire::u32s_to_state_ids_mut(self.table.as_mut())
3774	}
3775	}
3776
3777	/// The set of all possible starting states in a DFA.
3778	///
3779	/// The set of starting states corresponds to the possible choices one can make
3780	/// in terms of starting a DFA. That is, before following the first transition,
3781	/// you first need to select the state that you start in.
3782	///
3783	/// Normally, a DFA converted from an NFA that has a single starting state
3784	/// would itself just have one starting state. However, our support for look
3785	/// around generally requires more starting states. The correct starting state
3786	/// is chosen based on certain properties of the position at which we begin
3787	/// our search.
3788	///
3789	/// Before listing those properties, we first must define two terms:
3790	///
3791	/// `haystack` - The bytes to execute the search. The search always starts*
3792	/// at the beginning of `haystack` and ends before or at the end of
3793	/// `haystack`.
3794	/// `context` - The (possibly empty) bytes surrounding `haystack`. `haystack`*
3795	/// must be contained within `context` such that `context` is at least as big
3796	/// as `haystack`.
3797	///
3798	/// This split is crucial for dealing with look-around. For example, consider
3799	/// the context `foobarbaz`, the haystack `bar` and the regex `^bar$`. This
3800	/// regex should _not_ match the haystack since `bar` does not appear at the
3801	/// beginning of the input. Similarly, the regex `\Bbar\B` should match the
3802	/// haystack because `bar` is not surrounded by word boundaries. But a search
3803	/// that does not take context into account would not permit `\B` to match
3804	/// since the beginning of any string matches a word boundary. Similarly, a
3805	/// search that does not take context into account when searching `^bar$` in
3806	/// the haystack `bar` would produce a match when it shouldn't.
3807	///
3808	/// Thus, it follows that the starting state is chosen based on the following
3809	/// criteria, derived from the position at which the search starts in the
3810	/// `context` (corresponding to the start of `haystack`):
3811	///
3812	/// 1. If the search starts at the beginning of `context`, then the `Text`
3813	/// start state is used. (Since `^` corresponds to
3814	/// `hir::Anchor::Start`.)
3815	/// 2. If the search starts at a position immediately following a line
3816	/// terminator, then the `Line` start state is used. (Since `(?m:^)`
3817	/// corresponds to `hir::Anchor::StartLF`.)
3818	/// 3. If the search starts at a position immediately following a byte
3819	/// classified as a "word" character (`[_0-9a-zA-Z]`), then the `WordByte`
3820	/// start state is used. (Since `(?-u:\b)` corresponds to a word boundary.)
3821	/// 4. Otherwise, if the search starts at a position immediately following
3822	/// a byte that is not classified as a "word" character (`[^_0-9a-zA-Z]`),
3823	/// then the `NonWordByte` start state is used. (Since `(?-u:\B)`
3824	/// corresponds to a not-word-boundary.)
3825	///
3826	/// (N.B. Unicode word boundaries are not supported by the DFA because they
3827	/// require multi-byte look-around and this is difficult to support in a DFA.)
3828	///
3829	/// To further complicate things, we also support constructing individual
3830	/// anchored start states for each pattern in the DFA. (Which is required to
3831	/// implement overlapping regexes correctly, but is also generally useful.)
3832	/// Thus, when individual start states for each pattern are enabled, then the
3833	/// total number of start states represented is `4 + (4 #patterns)`, where*
3834	/// the 4 comes from each of the 4 possibilities above. The first 4 represents
3835	/// the starting states for the entire DFA, which support searching for
3836	/// multiple patterns simultaneously (possibly unanchored).
3837	///
3838	/// If individual start states are disabled, then this will only store 4
3839	/// start states. Typically, individual start states are only enabled when
3840	/// constructing the reverse DFA for regex matching. But they are also useful
3841	/// for building DFAs that can search for a specific pattern or even to support
3842	/// both anchored and unanchored searches with the same DFA.
3843	///
3844	/// Note though that while the start table always has either `4` or
3845	/// `4 + (4 #patterns)` starting state ids, the total number of states*
3846	/// might be considerably smaller. That is, many of the IDs may be duplicative.
3847	/// (For example, if a regex doesn't have a `\b` sub-pattern, then there's no
3848	/// reason to generate a unique starting state for handling word boundaries.
3849	/// Similarly for start/end anchors.)
3850	#[derive(Clone)]
3851	pub(crate) struct StartTable<T> {
3852	/// The initial start state IDs.
3853	///
3854	/// In practice, T is either `Vec<u32>` or `&[u32]`.
3855	///
3856	/// The first `2 stride` (currently always 8) entries always correspond*
3857	/// to the starts states for the entire DFA, with the first 4 entries being
3858	/// for unanchored searches and the second 4 entries being for anchored
3859	/// searches. To keep things simple, we always use 8 entries even if the
3860	/// `StartKind` is not both.
3861	///
3862	/// After that, there are `stride patterns` state IDs, where `patterns`*
3863	/// may be zero in the case of a DFA with no patterns or in the case where
3864	/// the DFA was built without enabling starting states for each pattern.
3865	table: T,
3866	/// The starting state configuration supported. When 'both', both
3867	/// unanchored and anchored searches work. When 'unanchored', anchored
3868	/// searches panic. When 'anchored', unanchored searches panic.
3869	kind: StartKind,
3870	/// The start state configuration for every possible byte.
3871	start_map: StartByteMap,
3872	/// The number of starting state IDs per pattern.
3873	stride: usize,
3874	/// The total number of patterns for which starting states are encoded.
3875	/// This is `None` for DFAs that were built without start states for each
3876	/// pattern. Thus, one cannot use this field to say how many patterns
3877	/// are in the DFA in all cases. It is specific to how many patterns are
3878	/// represented in this start table.
3879	pattern_len: Option<usize>,
3880	/// The universal starting state for unanchored searches. This is only
3881	/// present when the DFA supports unanchored searches and when all starting
3882	/// state IDs for an unanchored search are equivalent.
3883	universal_start_unanchored: Option<StateID>,
3884	/// The universal starting state for anchored searches. This is only
3885	/// present when the DFA supports anchored searches and when all starting
3886	/// state IDs for an anchored search are equivalent.
3887	universal_start_anchored: Option<StateID>,
3888	}
3889
3890	#[cfg(feature = "dfa-build")]
3891	impl StartTable<Vec<u32>> {
3892	/// Create a valid set of start states all pointing to the dead state.
3893	///
3894	/// When the corresponding DFA is constructed with start states for each
3895	/// pattern, then `patterns` should be the number of patterns. Otherwise,
3896	/// it should be zero.
3897	///
3898	/// If the total table size could exceed the allocatable limit, then this
3899	/// returns an error. In practice, this is unlikely to be able to occur,
3900	/// since it's likely that allocation would have failed long before it got
3901	/// to this point.
3902	fn dead(
3903	kind: StartKind,
3904	lookm: &LookMatcher,
3905	pattern_len: Option<usize>,
3906	) -> Result<StartTable<Vec<u32>>, BuildError> {
3907	if let Some(len) = pattern_len {
3908	assert!(len <= PatternID::LIMIT);
3909	}
3910	let stride = Start::len();
3911	// OK because 24 is never going to overflow anything.*
3912	let starts_len = stride.checked_mul(`2`).unwrap();
3913	let pattern_starts_len =
3914	match stride.checked_mul(pattern_len.unwrap_or(`0`)) {
3915	Some(x) => x,
3916	None => return Err(BuildError::too_many_start_states()),
3917	};
3918	let table_len = match starts_len.checked_add(pattern_starts_len) {
3919	Some(x) => x,
3920	None => return Err(BuildError::too_many_start_states()),
3921	};
3922	if let Err(_) = isize::try_from(table_len) {
3923	return Err(BuildError::too_many_start_states());
3924	}
3925	let table = vec![DEAD.as_u32(); table_len];
3926	let start_map = StartByteMap::new(lookm);
3927	Ok(StartTable {
3928	table,
3929	kind,
3930	start_map,
3931	stride,
3932	pattern_len,
3933	universal_start_unanchored: None,
3934	universal_start_anchored: None,
3935	})
3936	}
3937	}
3938
3939	impl<'a> StartTable<&'a [u32]> {
3940	/// Deserialize a table of start state IDs starting at the beginning of
3941	/// `slice`. Upon success, return the total number of bytes read along with
3942	/// the table of starting state IDs.
3943	///
3944	/// If there was a problem deserializing any part of the starting IDs,
3945	/// then this returns an error. Notably, if the given slice does not have
3946	/// the same alignment as `StateID`, then this will return an error (among
3947	/// other possible errors).
3948	///
3949	/// This is guaranteed to execute in constant time.
3950	///
3951	/// # Safety
3952	///
3953	/// This routine is not safe because it does not check the validity of the
3954	/// starting state IDs themselves. In particular, the number of starting
3955	/// IDs can be of variable length, so it's possible that checking their
3956	/// validity cannot be done in constant time. An invalid starting state
3957	/// ID is not safe because other code may rely on the starting IDs being
3958	/// correct (such as explicit bounds check elision). Therefore, an invalid
3959	/// start ID can lead to undefined behavior.
3960	///
3961	/// Callers that use this function must either pass on the safety invariant
3962	/// or guarantee that the bytes given contain valid starting state IDs.
3963	/// This guarantee is upheld by the bytes written by `write_to`.
3964	unsafe fn from_bytes_unchecked(
3965	mut slice: &'a [u8],
3966	) -> Result<(StartTable<&'a [u32]>, usize), DeserializeError> {
3967	let slice_start = slice.as_ptr().as_usize();
3968
3969	let (kind, nr) = StartKind::from_bytes(slice)?;
3970	slice = &slice[nr..];
3971
3972	let (start_map, nr) = StartByteMap::from_bytes(slice)?;
3973	slice = &slice[nr..];
3974
3975	let (stride, nr) =
3976	wire::try_read_u32_as_usize(slice, "start table stride")?;
3977	slice = &slice[nr..];
3978	if stride != Start::len() {
3979	return Err(DeserializeError::generic(
3980	"invalid starting table stride",
3981	));
3982	}
3983
3984	let (maybe_pattern_len, nr) =
3985	wire::try_read_u32_as_usize(slice, "start table patterns")?;
3986	slice = &slice[nr..];
3987	let pattern_len = if maybe_pattern_len.as_u32() == u32::MAX {
3988	None
3989	} else {
3990	Some(maybe_pattern_len)
3991	};
3992	if pattern_len.map_or(`false`, \|len\| len > PatternID::LIMIT) {
3993	return Err(DeserializeError::generic(
3994	"invalid number of patterns",
3995	));
3996	}
3997
3998	let (universal_unanchored, nr) =
3999	wire::try_read_u32(slice, "universal unanchored start")?;
4000	slice = &slice[nr..];
4001	let universal_start_unanchored = if universal_unanchored == u32::MAX {
4002	None
4003	} else {
4004	Some(StateID::try_from(universal_unanchored).map_err(\|e\| {
4005	DeserializeError::state_id_error(
4006	e,
4007	"universal unanchored start",
4008	)
4009	})?)
4010	};
4011
4012	let (universal_anchored, nr) =
4013	wire::try_read_u32(slice, "universal anchored start")?;
4014	slice = &slice[nr..];
4015	let universal_start_anchored = if universal_anchored == u32::MAX {
4016	None
4017	} else {
4018	Some(StateID::try_from(universal_anchored).map_err(\|e\| {
4019	DeserializeError::state_id_error(e, "universal anchored start")
4020	})?)
4021	};
4022
4023	let pattern_table_size = wire::mul(
4024	stride,
4025	pattern_len.unwrap_or(`0`),
4026	"invalid pattern length",
4027	)?;
4028	// Our start states always start with a two stride of start states for
4029	// the entire automaton. The first stride is for unanchored starting
4030	// states and the second stride is for anchored starting states. What
4031	// follows it are an optional set of start states for each pattern.
4032	let start_state_len = wire::add(
4033	wire::mul(`2`, stride, "start state stride too big")?,
4034	pattern_table_size,
4035	"invalid 'any' pattern starts size",
4036	)?;
4037	let table_bytes_len = wire::mul(
4038	start_state_len,
4039	StateID::SIZE,
4040	"pattern table bytes length",
4041	)?;
4042	wire::check_slice_len(slice, table_bytes_len, "start ID table")?;
4043	wire::check_alignment::<StateID>(slice)?;
4044	let table_bytes = &slice[..table_bytes_len];
4045	slice = &slice[table_bytes_len..];
4046	// SAFETY: Since StateID is always representable as a u32, all we need
4047	// to do is ensure that we have the proper length and alignment. We've
4048	// checked both above, so the cast below is safe.
4049	//
4050	// N.B. This is the only not-safe code in this function.
4051	let table = core::slice::from_raw_parts(
4052	table_bytes.as_ptr().cast::<u32>(),
4053	start_state_len,
4054	);
4055	let st = StartTable {
4056	table,
4057	kind,
4058	start_map,
4059	stride,
4060	pattern_len,
4061	universal_start_unanchored,
4062	universal_start_anchored,
4063	};
4064	Ok((st, slice.as_ptr().as_usize() - slice_start))
4065	}
4066	}
4067
4068	impl<T: AsRef<[u32]>> StartTable<T> {
4069	/// Writes a serialized form of this start table to the buffer given. If
4070	/// the buffer is too small, then an error is returned. To determine how
4071	/// big the buffer must be, use `write_to_len`.
4072	fn write_to<E: Endian>(
4073	&self,
4074	mut dst: &mut [u8],
4075	) -> Result<usize, SerializeError> {
4076	let nwrite = self.write_to_len();
4077	if dst.len() < nwrite {
4078	return Err(SerializeError::buffer_too_small(
4079	"starting table ids",
4080	));
4081	}
4082	dst = &mut dst[..nwrite];
4083
4084	// write start kind
4085	let nw = self.kind.write_to::<E>(dst)?;
4086	dst = &mut dst[nw..];
4087	// write start byte map
4088	let nw = self.start_map.write_to(dst)?;
4089	dst = &mut dst[nw..];
4090	// write stride
4091	// Unwrap is OK since the stride is always 4 (currently).
4092	E::write_u32(u32::try_from(self.stride).unwrap(), dst);
4093	dst = &mut dst[size_of::<u32>()..];
4094	// write pattern length
4095	// Unwrap is OK since number of patterns is guaranteed to fit in a u32.
4096	E::write_u32(
4097	u32::try_from(self.pattern_len.unwrap_or(`0xFFFF_FFFF`)).unwrap(),
4098	dst,
4099	);
4100	dst = &mut dst[size_of::<u32>()..];
4101	// write universal start unanchored state id, u32::MAX if absent
4102	E::write_u32(
4103	self.universal_start_unanchored
4104	.map_or(u32::MAX, \|sid\| sid.as_u32()),
4105	dst,
4106	);
4107	dst = &mut dst[size_of::<u32>()..];
4108	// write universal start anchored state id, u32::MAX if absent
4109	E::write_u32(
4110	self.universal_start_anchored.map_or(u32::MAX, \|sid\| sid.as_u32()),
4111	dst,
4112	);
4113	dst = &mut dst[size_of::<u32>()..];
4114	// write start IDs
4115	for &sid in self.table() {
4116	let n = wire::write_state_id::<E>(sid, &mut dst);
4117	dst = &mut dst[n..];
4118	}
4119	Ok(nwrite)
4120	}
4121
4122	/// Returns the number of bytes the serialized form of this start ID table
4123	/// will use.
4124	fn write_to_len(&self) -> usize {
4125	self.kind.write_to_len()
4126	+ self.start_map.write_to_len()
4127	+ size_of::<u32>() // stride
4128	+ size_of::<u32>() // # patterns
4129	+ size_of::<u32>() // universal unanchored start
4130	+ size_of::<u32>() // universal anchored start
4131	+ (self.table().len() * StateID::SIZE)
4132	}
4133
4134	/// Validates that every state ID in this start table is valid by checking
4135	/// it against the given transition table (which must be for the same DFA).
4136	///
4137	/// That is, every state ID can be used to correctly index a state.
4138	fn validate(&self, dfa: &DFA<T>) -> Result<(), DeserializeError> {
4139	let tt = &dfa.tt;
4140	if !self.universal_start_unanchored.map_or(`true`, \|s\| tt.is_valid(s)) {
4141	return Err(DeserializeError::generic(
4142	"found invalid universal unanchored starting state ID",
4143	));
4144	}
4145	if !self.universal_start_anchored.map_or(`true`, \|s\| tt.is_valid(s)) {
4146	return Err(DeserializeError::generic(
4147	"found invalid universal anchored starting state ID",
4148	));
4149	}
4150	for &id in self.table() {
4151	if !tt.is_valid(id) {
4152	return Err(DeserializeError::generic(
4153	"found invalid starting state ID",
4154	));
4155	}
4156	}
4157	Ok(())
4158	}
4159
4160	/// Converts this start list to a borrowed value.
4161	fn as_ref(&self) -> StartTable<&'_ [u32]> {
4162	StartTable {
4163	table: self.table.as_ref(),
4164	kind: self.kind,
4165	start_map: self.start_map.clone(),
4166	stride: self.stride,
4167	pattern_len: self.pattern_len,
4168	universal_start_unanchored: self.universal_start_unanchored,
4169	universal_start_anchored: self.universal_start_anchored,
4170	}
4171	}
4172
4173	/// Converts this start list to an owned value.
4174	#[cfg(feature = "alloc")]
4175	fn to_owned(&self) -> StartTable<alloc::vec::Vec<u32>> {
4176	StartTable {
4177	table: self.table.as_ref().to_vec(),
4178	kind: self.kind,
4179	start_map: self.start_map.clone(),
4180	stride: self.stride,
4181	pattern_len: self.pattern_len,
4182	universal_start_unanchored: self.universal_start_unanchored,
4183	universal_start_anchored: self.universal_start_anchored,
4184	}
4185	}
4186
4187	/// Return the start state for the given input and starting configuration.
4188	/// This returns an error if the input configuration is not supported by
4189	/// this DFA. For example, requesting an unanchored search when the DFA was
4190	/// not built with unanchored starting states. Or asking for an anchored
4191	/// pattern search with an invalid pattern ID or on a DFA that was not
4192	/// built with start states for each pattern.
4193	#[cfg_attr(feature = "perf-inline", inline(always))]
4194	fn start(
4195	&self,
4196	anchored: Anchored,
4197	start: Start,
4198	) -> Result<StateID, StartError> {
4199	let start_index = start.as_usize();
4200	let index = match anchored {
4201	Anchored::No => {
4202	if !self.kind.has_unanchored() {
4203	return Err(StartError::unsupported_anchored(anchored));
4204	}
4205	start_index
4206	}
4207	Anchored::Yes => {
4208	if !self.kind.has_anchored() {
4209	return Err(StartError::unsupported_anchored(anchored));
4210	}
4211	self.stride + start_index
4212	}
4213	Anchored::Pattern(pid) => {
4214	let len = match self.pattern_len {
4215	None => {
4216	return Err(StartError::unsupported_anchored(anchored))
4217	}
4218	Some(len) => len,
4219	};
4220	if pid.as_usize() >= len {
4221	return Ok(DEAD);
4222	}
4223	(`2` * self.stride)
4224	+ (self.stride * pid.as_usize())
4225	+ start_index
4226	}
4227	};
4228	Ok(self.table()[index])
4229	}
4230
4231	/// Returns an iterator over all start state IDs in this table.
4232	///
4233	/// Each item is a triple of: start state ID, the start state type and the
4234	/// pattern ID (if any).
4235	fn iter(&self) -> StartStateIter<'_> {
4236	StartStateIter { st: self.as_ref(), i: `0` }
4237	}
4238
4239	/// Returns the table as a slice of state IDs.
4240	fn table(&self) -> &[StateID] {
4241	wire::u32s_to_state_ids(self.table.as_ref())
4242	}
4243
4244	/// Return the memory usage, in bytes, of this start list.
4245	///
4246	/// This does not include the size of a `StartList` value itself.
4247	fn memory_usage(&self) -> usize {
4248	self.table().len() * StateID::SIZE
4249	}
4250	}
4251
4252	#[cfg(feature = "dfa-build")]
4253	impl<T: AsMut<[u32]>> StartTable<T> {
4254	/// Set the start state for the given index and pattern.
4255	///
4256	/// If the pattern ID or state ID are not valid, then this will panic.
4257	fn set_start(&mut self, anchored: Anchored, start: Start, id: StateID) {
4258	let start_index = start.as_usize();
4259	let index = match anchored {
4260	Anchored::No => start_index,
4261	Anchored::Yes => self.stride + start_index,
4262	Anchored::Pattern(pid) => {
4263	let pid = pid.as_usize();
4264	let len = self
4265	.pattern_len
4266	.expect("start states for each pattern enabled");
4267	assert!(pid < len, "invalid pattern ID {:?}", pid);
4268	self.stride
4269	.checked_mul(pid)
4270	.unwrap()
4271	.checked_add(self.stride.checked_mul(`2`).unwrap())
4272	.unwrap()
4273	.checked_add(start_index)
4274	.unwrap()
4275	}
4276	};
4277	self.table_mut()[index] = id;
4278	}
4279
4280	/// Returns the table as a mutable slice of state IDs.
4281	fn table_mut(&mut self) -> &mut [StateID] {
4282	wire::u32s_to_state_ids_mut(self.table.as_mut())
4283	}
4284	}
4285
4286	/// An iterator over start state IDs.
4287	///
4288	/// This iterator yields a triple of start state ID, the anchored mode and the
4289	/// start state type. If a pattern ID is relevant, then the anchored mode will
4290	/// contain it. Start states with an anchored mode containing a pattern ID will
4291	/// only occur when the DFA was compiled with start states for each pattern
4292	/// (which is disabled by default).
4293	pub(crate) struct StartStateIter<'a> {
4294	st: StartTable<&'a [u32]>,
4295	i: usize,
4296	}
4297
4298	impl<'a> Iterator for StartStateIter<'a> {
4299	type Item = (StateID, Anchored, Start);
4300
4301	fn next(&mut self) -> Option<(StateID, Anchored, Start)> {
4302	let i = self.i;
4303	let table = self.st.table();
4304	if i >= table.len() {
4305	return None;
4306	}
4307	self.i += `1`;
4308
4309	// This unwrap is okay since the stride of the starting state table
4310	// must always match the number of start state types.
4311	let start_type = Start::from_usize(i % self.st.stride).unwrap();
4312	let anchored = if i < self.st.stride {
4313	Anchored::No
4314	} else if i < (`2` * self.st.stride) {
4315	Anchored::Yes
4316	} else {
4317	let pid = (i - (`2` * self.st.stride)) / self.st.stride;
4318	Anchored::Pattern(PatternID::new(pid).unwrap())
4319	};
4320	Some((table[i], anchored, start_type))
4321	}
4322	}
4323
4324	/// This type represents that patterns that should be reported whenever a DFA
4325	/// enters a match state. This structure exists to support DFAs that search for
4326	/// matches for multiple regexes.
4327	///
4328	/// This structure relies on the fact that all match states in a DFA occur
4329	/// contiguously in the DFA's transition table. (See dfa/special.rs for a more
4330	/// detailed breakdown of the representation.) Namely, when a match occurs, we
4331	/// know its state ID. Since we know the start and end of the contiguous region
4332	/// of match states, we can use that to compute the position at which the match
4333	/// state occurs. That in turn is used as an offset into this structure.
4334	#[derive(Clone, Debug)]
4335	struct MatchStates<T> {
4336	/// Slices is a flattened sequence of pairs, where each pair points to a
4337	/// sub-slice of pattern_ids. The first element of the pair is an offset
4338	/// into pattern_ids and the second element of the pair is the number
4339	/// of 32-bit pattern IDs starting at that position. That is, each pair
4340	/// corresponds to a single DFA match state and its corresponding match
4341	/// IDs. The number of pairs always corresponds to the number of distinct
4342	/// DFA match states.
4343	///
4344	/// In practice, T is either Vec<u32> or &[u32].
4345	slices: T,
4346	/// A flattened sequence of pattern IDs for each DFA match state. The only
4347	/// way to correctly read this sequence is indirectly via `slices`.
4348	///
4349	/// In practice, T is either Vec<u32> or &[u32].
4350	pattern_ids: T,
4351	/// The total number of unique patterns represented by these match states.
4352	pattern_len: usize,
4353	}
4354
4355	impl<'a> MatchStates<&'a [u32]> {
4356	unsafe fn from_bytes_unchecked(
4357	mut slice: &'a [u8],
4358	) -> Result<(MatchStates<&'a [u32]>, usize), DeserializeError> {
4359	let slice_start = slice.as_ptr().as_usize();
4360
4361	// Read the total number of match states.
4362	let (state_len, nr) =
4363	wire::try_read_u32_as_usize(slice, "match state length")?;
4364	slice = &slice[nr..];
4365
4366	// Read the slice start/length pairs.
4367	let pair_len = wire::mul(`2`, state_len, "match state offset pairs")?;
4368	let slices_bytes_len = wire::mul(
4369	pair_len,
4370	PatternID::SIZE,
4371	"match state slice offset byte length",
4372	)?;
4373	wire::check_slice_len(slice, slices_bytes_len, "match state slices")?;
4374	wire::check_alignment::<PatternID>(slice)?;
4375	let slices_bytes = &slice[..slices_bytes_len];
4376	slice = &slice[slices_bytes_len..];
4377	// SAFETY: Since PatternID is always representable as a u32, all we
4378	// need to do is ensure that we have the proper length and alignment.
4379	// We've checked both above, so the cast below is safe.
4380	//
4381	// N.B. This is one of the few not-safe snippets in this function,
4382	// so we mark it explicitly to call it out.
4383	let slices = core::slice::from_raw_parts(
4384	slices_bytes.as_ptr().cast::<u32>(),
4385	pair_len,
4386	);
4387
4388	// Read the total number of unique pattern IDs (which is always 1 more
4389	// than the maximum pattern ID in this automaton, since pattern IDs are
4390	// handed out contiguously starting at 0).
4391	let (pattern_len, nr) =
4392	wire::try_read_u32_as_usize(slice, "pattern length")?;
4393	slice = &slice[nr..];
4394
4395	// Now read the pattern ID length. We don't need to store this
4396	// explicitly, but we need it to know how many pattern IDs to read.
4397	let (idlen, nr) =
4398	wire::try_read_u32_as_usize(slice, "pattern ID length")?;
4399	slice = &slice[nr..];
4400
4401	// Read the actual pattern IDs.
4402	let pattern_ids_len =
4403	wire::mul(idlen, PatternID::SIZE, "pattern ID byte length")?;
4404	wire::check_slice_len(slice, pattern_ids_len, "match pattern IDs")?;
4405	wire::check_alignment::<PatternID>(slice)?;
4406	let pattern_ids_bytes = &slice[..pattern_ids_len];
4407	slice = &slice[pattern_ids_len..];
4408	// SAFETY: Since PatternID is always representable as a u32, all we
4409	// need to do is ensure that we have the proper length and alignment.
4410	// We've checked both above, so the cast below is safe.
4411	//
4412	// N.B. This is one of the few not-safe snippets in this function,
4413	// so we mark it explicitly to call it out.
4414	let pattern_ids = core::slice::from_raw_parts(
4415	pattern_ids_bytes.as_ptr().cast::<u32>(),
4416	idlen,
4417	);
4418
4419	let ms = MatchStates { slices, pattern_ids, pattern_len };
4420	Ok((ms, slice.as_ptr().as_usize() - slice_start))
4421	}
4422	}
4423
4424	#[cfg(feature = "dfa-build")]
4425	impl MatchStates<Vec<u32>> {
4426	fn empty(pattern_len: usize) -> MatchStates<Vec<u32>> {
4427	assert!(pattern_len <= PatternID::LIMIT);
4428	MatchStates { slices: vec![], pattern_ids: vec![], pattern_len }
4429	}
4430
4431	fn new(
4432	matches: &BTreeMap<StateID, Vec<PatternID>>,
4433	pattern_len: usize,
4434	) -> Result<MatchStates<Vec<u32>>, BuildError> {
4435	let mut m = MatchStates::empty(pattern_len);
4436	for (_, pids) in matches.iter() {
4437	let start = PatternID::new(m.pattern_ids.len())
4438	.map_err(\|_\| BuildError::too_many_match_pattern_ids())?;
4439	m.slices.push(start.as_u32());
4440	// This is always correct since the number of patterns in a single
4441	// match state can never exceed maximum number of allowable
4442	// patterns. Why? Because a pattern can only appear once in a
4443	// particular match state, by construction. (And since our pattern
4444	// ID limit is one less than u32::MAX, we're guaranteed that the
4445	// length fits in a u32.)
4446	m.slices.push(u32::try_from(pids.len()).unwrap());
4447	for &pid in pids {
4448	m.pattern_ids.push(pid.as_u32());
4449	}
4450	}
4451	m.pattern_len = pattern_len;
4452	Ok(m)
4453	}
4454
4455	fn new_with_map(
4456	&self,
4457	matches: &BTreeMap<StateID, Vec<PatternID>>,
4458	) -> Result<MatchStates<Vec<u32>>, BuildError> {
4459	MatchStates::new(matches, self.pattern_len)
4460	}
4461	}
4462
4463	impl<T: AsRef<[u32]>> MatchStates<T> {
4464	/// Writes a serialized form of these match states to the buffer given. If
4465	/// the buffer is too small, then an error is returned. To determine how
4466	/// big the buffer must be, use `write_to_len`.
4467	fn write_to<E: Endian>(
4468	&self,
4469	mut dst: &mut [u8],
4470	) -> Result<usize, SerializeError> {
4471	let nwrite = self.write_to_len();
4472	if dst.len() < nwrite {
4473	return Err(SerializeError::buffer_too_small("match states"));
4474	}
4475	dst = &mut dst[..nwrite];
4476
4477	// write state ID length
4478	// Unwrap is OK since number of states is guaranteed to fit in a u32.
4479	E::write_u32(u32::try_from(self.len()).unwrap(), dst);
4480	dst = &mut dst[size_of::<u32>()..];
4481
4482	// write slice offset pairs
4483	for &pid in self.slices() {
4484	let n = wire::write_pattern_id::<E>(pid, &mut dst);
4485	dst = &mut dst[n..];
4486	}
4487
4488	// write unique pattern ID length
4489	// Unwrap is OK since number of patterns is guaranteed to fit in a u32.
4490	E::write_u32(u32::try_from(self.pattern_len).unwrap(), dst);
4491	dst = &mut dst[size_of::<u32>()..];
4492
4493	// write pattern ID length
4494	// Unwrap is OK since we check at construction (and deserialization)
4495	// that the number of patterns is representable as a u32.
4496	E::write_u32(u32::try_from(self.pattern_ids().len()).unwrap(), dst);
4497	dst = &mut dst[size_of::<u32>()..];
4498
4499	// write pattern IDs
4500	for &pid in self.pattern_ids() {
4501	let n = wire::write_pattern_id::<E>(pid, &mut dst);
4502	dst = &mut dst[n..];
4503	}
4504
4505	Ok(nwrite)
4506	}
4507
4508	/// Returns the number of bytes the serialized form of these match states
4509	/// will use.
4510	fn write_to_len(&self) -> usize {
4511	size_of::<u32>() // match state length
4512	+ (self.slices().len() * PatternID::SIZE)
4513	+ size_of::<u32>() // unique pattern ID length
4514	+ size_of::<u32>() // pattern ID length
4515	+ (self.pattern_ids().len() * PatternID::SIZE)
4516	}
4517
4518	/// Valides that the match state info is itself internally consistent and
4519	/// consistent with the recorded match state region in the given DFA.
4520	fn validate(&self, dfa: &DFA<T>) -> Result<(), DeserializeError> {
4521	if self.len() != dfa.special.match_len(dfa.stride()) {
4522	return Err(DeserializeError::generic(
4523	"match state length mismatch",
4524	));
4525	}
4526	for si in `0`..self.len() {
4527	let start = self.slices()[si * `2`].as_usize();
4528	let len = self.slices()[si * `2` + `1`].as_usize();
4529	if start >= self.pattern_ids().len() {
4530	return Err(DeserializeError::generic(
4531	"invalid pattern ID start offset",
4532	));
4533	}
4534	if start + len > self.pattern_ids().len() {
4535	return Err(DeserializeError::generic(
4536	"invalid pattern ID length",
4537	));
4538	}
4539	for mi in `0`..len {
4540	let pid = self.pattern_id(si, mi);
4541	if pid.as_usize() >= self.pattern_len {
4542	return Err(DeserializeError::generic(
4543	"invalid pattern ID",
4544	));
4545	}
4546	}
4547	}
4548	Ok(())
4549	}
4550
4551	/// Converts these match states back into their map form. This is useful
4552	/// when shuffling states, as the normal MatchStates representation is not
4553	/// amenable to easy state swapping. But with this map, to swap id1 and
4554	/// id2, all you need to do is:
4555	///
4556	/// if let Some(pids) = map.remove(&id1) {
4557	/// map.insert(id2, pids);
4558	/// }
4559	///
4560	/// Once shuffling is done, use MatchStates::new to convert back.
4561	#[cfg(feature = "dfa-build")]
4562	fn to_map(&self, dfa: &DFA<T>) -> BTreeMap<StateID, Vec<PatternID>> {
4563	let mut map = BTreeMap::new();
4564	for i in `0`..self.len() {
4565	let mut pids = vec![];
4566	for j in `0`..self.pattern_len(i) {
4567	pids.push(self.pattern_id(i, j));
4568	}
4569	map.insert(self.match_state_id(dfa, i), pids);
4570	}
4571	map
4572	}
4573
4574	/// Converts these match states to a borrowed value.
4575	fn as_ref(&self) -> MatchStates<&'_ [u32]> {
4576	MatchStates {
4577	slices: self.slices.as_ref(),
4578	pattern_ids: self.pattern_ids.as_ref(),
4579	pattern_len: self.pattern_len,
4580	}
4581	}
4582
4583	/// Converts these match states to an owned value.
4584	#[cfg(feature = "alloc")]
4585	fn to_owned(&self) -> MatchStates<alloc::vec::Vec<u32>> {
4586	MatchStates {
4587	slices: self.slices.as_ref().to_vec(),
4588	pattern_ids: self.pattern_ids.as_ref().to_vec(),
4589	pattern_len: self.pattern_len,
4590	}
4591	}
4592
4593	/// Returns the match state ID given the match state index. (Where the
4594	/// first match state corresponds to index 0.)
4595	///
4596	/// This panics if there is no match state at the given index.
4597	fn match_state_id(&self, dfa: &DFA<T>, index: usize) -> StateID {
4598	assert!(dfa.special.matches(), "no match states to index");
4599	// This is one of the places where we rely on the fact that match
4600	// states are contiguous in the transition table. Namely, that the
4601	// first match state ID always corresponds to dfa.special.min_start.
4602	// From there, since we know the stride, we can compute the ID of any
4603	// match state given its index.
4604	let stride2 = u32::try_from(dfa.stride2()).unwrap();
4605	let offset = index.checked_shl(stride2).unwrap();
4606	let id = dfa.special.min_match.as_usize().checked_add(offset).unwrap();
4607	let sid = StateID::new(id).unwrap();
4608	assert!(dfa.is_match_state(sid));
4609	sid
4610	}
4611
4612	/// Returns the pattern ID at the given match index for the given match
4613	/// state.
4614	///
4615	/// The match state index is the state index minus the state index of the
4616	/// first match state in the DFA.
4617	///
4618	/// The match index is the index of the pattern ID for the given state.
4619	/// The index must be less than `self.pattern_len(state_index)`.
4620	#[cfg_attr(feature = "perf-inline", inline(always))]
4621	fn pattern_id(&self, state_index: usize, match_index: usize) -> PatternID {
4622	self.pattern_id_slice(state_index)[match_index]
4623	}
4624
4625	/// Returns the number of patterns in the given match state.
4626	///
4627	/// The match state index is the state index minus the state index of the
4628	/// first match state in the DFA.
4629	#[cfg_attr(feature = "perf-inline", inline(always))]
4630	fn pattern_len(&self, state_index: usize) -> usize {
4631	self.slices()[state_index * `2` + `1`].as_usize()
4632	}
4633
4634	/// Returns all of the pattern IDs for the given match state index.
4635	///
4636	/// The match state index is the state index minus the state index of the
4637	/// first match state in the DFA.
4638	#[cfg_attr(feature = "perf-inline", inline(always))]
4639	fn pattern_id_slice(&self, state_index: usize) -> &[PatternID] {
4640	let start = self.slices()[state_index * `2`].as_usize();
4641	let len = self.pattern_len(state_index);
4642	&self.pattern_ids()[start..start + len]
4643	}
4644
4645	/// Returns the pattern ID offset slice of u32 as a slice of PatternID.
4646	#[cfg_attr(feature = "perf-inline", inline(always))]
4647	fn slices(&self) -> &[PatternID] {
4648	wire::u32s_to_pattern_ids(self.slices.as_ref())
4649	}
4650
4651	/// Returns the total number of match states.
4652	#[cfg_attr(feature = "perf-inline", inline(always))]
4653	fn len(&self) -> usize {
4654	assert_eq!(`0`, self.slices().len() % `2`);
4655	self.slices().len() / `2`
4656	}
4657
4658	/// Returns the pattern ID slice of u32 as a slice of PatternID.
4659	#[cfg_attr(feature = "perf-inline", inline(always))]
4660	fn pattern_ids(&self) -> &[PatternID] {
4661	wire::u32s_to_pattern_ids(self.pattern_ids.as_ref())
4662	}
4663
4664	/// Return the memory usage, in bytes, of these match pairs.
4665	fn memory_usage(&self) -> usize {
4666	(self.slices().len() + self.pattern_ids().len()) * PatternID::SIZE
4667	}
4668	}
4669
4670	/// A common set of flags for both dense and sparse DFAs. This primarily
4671	/// centralizes the serialization format of these flags at a bitset.
4672	#[derive(Clone, Copy, Debug)]
4673	pub(crate) struct Flags {
4674	/// Whether the DFA can match the empty string. When this is false, all
4675	/// matches returned by this DFA are guaranteed to have non-zero length.
4676	pub(crate) has_empty: bool,
4677	/// Whether the DFA should only produce matches with spans that correspond
4678	/// to valid UTF-8. This also includes omitting any zero-width matches that
4679	/// split the UTF-8 encoding of a codepoint.
4680	pub(crate) is_utf8: bool,
4681	/// Whether the DFA is always anchored or not, regardless of `Input`
4682	/// configuration. This is useful for avoiding a reverse scan even when
4683	/// executing unanchored searches.
4684	pub(crate) is_always_start_anchored: bool,
4685	}
4686
4687	impl Flags {
4688	/// Creates a set of flags for a DFA from an NFA.
4689	///
4690	/// N.B. This constructor was defined at the time of writing because all
4691	/// of the flags are derived directly from the NFA. If this changes in the
4692	/// future, we might be more thoughtful about how the `Flags` value is
4693	/// itself built.
4694	#[cfg(feature = "dfa-build")]
4695	fn from_nfa(nfa: &thompson::NFA) -> Flags {
4696	Flags {
4697	has_empty: nfa.has_empty(),
4698	is_utf8: nfa.is_utf8(),
4699	is_always_start_anchored: nfa.is_always_start_anchored(),
4700	}
4701	}
4702
4703	/// Deserializes the flags from the given slice. On success, this also
4704	/// returns the number of bytes read from the slice.
4705	pub(crate) fn from_bytes(
4706	slice: &[u8],
4707	) -> Result<(Flags, usize), DeserializeError> {
4708	let (bits, nread) = wire::try_read_u32(slice, "flag bitset")?;
4709	let flags = Flags {
4710	has_empty: bits & (`1` << `0`) != `0`,
4711	is_utf8: bits & (`1` << `1`) != `0`,
4712	is_always_start_anchored: bits & (`1` << `2`) != `0`,
4713	};
4714	Ok((flags, nread))
4715	}
4716
4717	/// Writes these flags to the given byte slice. If the buffer is too small,
4718	/// then an error is returned. To determine how big the buffer must be,
4719	/// use `write_to_len`.
4720	pub(crate) fn write_to<E: Endian>(
4721	&self,
4722	dst: &mut [u8],
4723	) -> Result<usize, SerializeError> {
4724	fn bool_to_int(b: bool) -> u32 {
4725	if b {
4726	`1`
4727	} else {
4728	`0`
4729	}
4730	}
4731
4732	let nwrite = self.write_to_len();
4733	if dst.len() < nwrite {
4734	return Err(SerializeError::buffer_too_small("flag bitset"));
4735	}
4736	let bits = (bool_to_int(self.has_empty) << `0`)
4737	\| (bool_to_int(self.is_utf8) << `1`)
4738	\| (bool_to_int(self.is_always_start_anchored) << `2`);
4739	E::write_u32(bits, dst);
4740	Ok(nwrite)
4741	}
4742
4743	/// Returns the number of bytes the serialized form of these flags
4744	/// will use.
4745	pub(crate) fn write_to_len(&self) -> usize {
4746	size_of::<u32>()
4747	}
4748	}
4749
4750	/// An iterator over all states in a DFA.
4751	///
4752	/// This iterator yields a tuple for each state. The first element of the
4753	/// tuple corresponds to a state's identifier, and the second element
4754	/// corresponds to the state itself (comprised of its transitions).
4755	///
4756	/// `'a` corresponding to the lifetime of original DFA, `T` corresponds to
4757	/// the type of the transition table itself.
4758	pub(crate) struct StateIter<'a, T> {
4759	tt: &'a TransitionTable<T>,
4760	it: iter::Enumerate<slice::Chunks<'a, StateID>>,
4761	}
4762
4763	impl<'a, T: AsRef<[u32]>> Iterator for StateIter<'a, T> {
4764	type Item = State<'a>;
4765
4766	fn next(&mut self) -> Option<State<'a>> {
4767	self.it.next().map(\|(index: usize, _)\| {
4768	let id: StateID = self.tt.to_state_id(index);
4769	self.tt.state(id)
4770	})
4771	}
4772	}
4773
4774	/// An immutable representation of a single DFA state.
4775	///
4776	/// `'a` correspondings to the lifetime of a DFA's transition table.
4777	pub(crate) struct State<'a> {
4778	id: StateID,
4779	stride2: usize,
4780	transitions: &'a [StateID],
4781	}
4782
4783	impl<'a> State<'a> {
4784	/// Return an iterator over all transitions in this state. This yields
4785	/// a number of transitions equivalent to the alphabet length of the
4786	/// corresponding DFA.
4787	///
4788	/// Each transition is represented by a tuple. The first element is
4789	/// the input byte for that transition and the second element is the
4790	/// transitions itself.
4791	pub(crate) fn transitions(&self) -> StateTransitionIter<'_> {
4792	StateTransitionIter {
4793	len: self.transitions.len(),
4794	it: self.transitions.iter().enumerate(),
4795	}
4796	}
4797
4798	/// Return an iterator over a sparse representation of the transitions in
4799	/// this state. Only non-dead transitions are returned.
4800	///
4801	/// The "sparse" representation in this case corresponds to a sequence of
4802	/// triples. The first two elements of the triple comprise an inclusive
4803	/// byte range while the last element corresponds to the transition taken
4804	/// for all bytes in the range.
4805	///
4806	/// This is somewhat more condensed than the classical sparse
4807	/// representation (where you have an element for every non-dead
4808	/// transition), but in practice, checking if a byte is in a range is very
4809	/// cheap and using ranges tends to conserve quite a bit more space.
4810	pub(crate) fn sparse_transitions(&self) -> StateSparseTransitionIter<'_> {
4811	StateSparseTransitionIter { dense: self.transitions(), cur: None }
4812	}
4813
4814	/// Returns the identifier for this state.
4815	pub(crate) fn id(&self) -> StateID {
4816	self.id
4817	}
4818
4819	/// Analyzes this state to determine whether it can be accelerated. If so,
4820	/// it returns an accelerator that contains at least one byte.
4821	#[cfg(feature = "dfa-build")]
4822	fn accelerate(&self, classes: &ByteClasses) -> Option<Accel> {
4823	// We just try to add bytes to our accelerator. Once adding fails
4824	// (because we've added too many bytes), then give up.
4825	let mut accel = Accel::new();
4826	for (class, id) in self.transitions() {
4827	if id == self.id() {
4828	continue;
4829	}
4830	for unit in classes.elements(class) {
4831	if let Some(byte) = unit.as_u8() {
4832	if !accel.add(byte) {
4833	return None;
4834	}
4835	}
4836	}
4837	}
4838	if accel.is_empty() {
4839	None
4840	} else {
4841	Some(accel)
4842	}
4843	}
4844	}
4845
4846	impl<'a> fmt::Debug for State<'a> {
4847	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4848	for (i: usize, (start: Unit, end: Unit, sid: StateID)) in self.sparse_transitions().enumerate() {
4849	let id: usize = if f.alternate() {
4850	sid.as_usize()
4851	} else {
4852	sid.as_usize() >> self.stride2
4853	};
4854	if i > `0` {
4855	write!(f, ", ")?;
4856	}
4857	if start == end {
4858	write!(f, "{:?} => {:?}", start, id)?;
4859	} else {
4860	write!(f, "{:?}-{:?} => {:?}", start, end, id)?;
4861	}
4862	}
4863	Ok(())
4864	}
4865	}
4866
4867	/// An iterator over all transitions in a single DFA state. This yields
4868	/// a number of transitions equivalent to the alphabet length of the
4869	/// corresponding DFA.
4870	///
4871	/// Each transition is represented by a tuple. The first element is the input
4872	/// byte for that transition and the second element is the transition itself.
4873	#[derive(Debug)]
4874	pub(crate) struct StateTransitionIter<'a> {
4875	len: usize,
4876	it: iter::Enumerate<slice::Iter<'a, StateID>>,
4877	}
4878
4879	impl<'a> Iterator for StateTransitionIter<'a> {
4880	type Item = (alphabet::Unit, StateID);
4881
4882	fn next(&mut self) -> Option<(alphabet::Unit, StateID)> {
4883	self.it.next().map(\|(i: usize, &id: StateID)\| {
4884	let unit: Unit = if i + `1` == self.len {
4885	alphabet::Unit::eoi(num_byte_equiv_classes:i)
4886	} else {
4887	let b: u8 = u8::try_from(i)
4888	.expect(msg:"raw byte alphabet is never exceeded");
4889	alphabet::Unit::u8(byte:b)
4890	};
4891	(unit, id)
4892	})
4893	}
4894	}
4895
4896	/// An iterator over all non-DEAD transitions in a single DFA state using a
4897	/// sparse representation.
4898	///
4899	/// Each transition is represented by a triple. The first two elements of the
4900	/// triple comprise an inclusive byte range while the last element corresponds
4901	/// to the transition taken for all bytes in the range.
4902	///
4903	/// As a convenience, this always returns `alphabet::Unit` values of the same
4904	/// type. That is, you'll never get a (byte, EOI) or a (EOI, byte). Only (byte,
4905	/// byte) and (EOI, EOI) values are yielded.
4906	#[derive(Debug)]
4907	pub(crate) struct StateSparseTransitionIter<'a> {
4908	dense: StateTransitionIter<'a>,
4909	cur: Option<(alphabet::Unit, alphabet::Unit, StateID)>,
4910	}
4911
4912	impl<'a> Iterator for StateSparseTransitionIter<'a> {
4913	type Item = (alphabet::Unit, alphabet::Unit, StateID);
4914
4915	fn next(&mut self) -> Option<(alphabet::Unit, alphabet::Unit, StateID)> {
4916	while let Some((unit, next)) = self.dense.next() {
4917	let (prev_start, prev_end, prev_next) = match self.cur {
4918	Some(t) => t,
4919	None => {
4920	self.cur = Some((unit, unit, next));
4921	continue;
4922	}
4923	};
4924	if prev_next == next && !unit.is_eoi() {
4925	self.cur = Some((prev_start, unit, prev_next));
4926	} else {
4927	self.cur = Some((unit, unit, next));
4928	if prev_next != DEAD {
4929	return Some((prev_start, prev_end, prev_next));
4930	}
4931	}
4932	}
4933	if let Some((start, end, next)) = self.cur.take() {
4934	if next != DEAD {
4935	return Some((start, end, next));
4936	}
4937	}
4938	None
4939	}
4940	}
4941
4942	/// An error that occurred during the construction of a DFA.
4943	///
4944	/// This error does not provide many introspection capabilities. There are
4945	/// generally only two things you can do with it:
4946	///
4947	/// Obtain a human readable message via its `std::fmt::Display` impl.*
4948	/// Access an underlying [`nfa::thompson::BuildError`](thompson::BuildError)*
4949	/// type from its `source` method via the `std::error::Error` trait. This error
4950	/// only occurs when using convenience routines for building a DFA directly
4951	/// from a pattern string.
4952	///
4953	/// When the `std` feature is enabled, this implements the `std::error::Error`
4954	/// trait.
4955	#[cfg(feature = "dfa-build")]
4956	#[derive(Clone, Debug)]
4957	pub struct BuildError {
4958	kind: BuildErrorKind,
4959	}
4960
4961	#[cfg(feature = "dfa-build")]
4962	impl BuildError {
4963	/// Returns true if and only if this error corresponds to an error with DFA
4964	/// construction that occurred because of exceeding a size limit.
4965	///
4966	/// While this can occur when size limits like [`Config::dfa_size_limit`]
4967	/// or [`Config::determinize_size_limit`] are exceeded, this can also occur
4968	/// when the number of states or patterns exceeds a hard-coded maximum.
4969	/// (Where these maximums are derived based on the values representable by
4970	/// [`StateID`] and [`PatternID`].)
4971	///
4972	/// This predicate is useful in contexts where you want to distinguish
4973	/// between errors related to something provided by an end user (for
4974	/// example, an invalid regex pattern) and errors related to configured
4975	/// heuristics. For example, building a DFA might be an optimization that
4976	/// you want to skip if construction fails because of an exceeded size
4977	/// limit, but where you want to bubble up an error if it fails for some
4978	/// other reason.
4979	///
4980	/// # Example
4981	///
4982	/// ```
4983	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
4984	/// # if !cfg!(target_pointer_width = "64") { return Ok(()); } // see #1039
4985	/// use regex_automata::{dfa::{dense, Automaton}, Input};
4986	///
4987	/// let err = dense::Builder::new()
4988	/// .configure(dense::Config::new()
4989	/// .determinize_size_limit(Some(100_000))
4990	/// )
4991	/// .build(r"\w{20}")
4992	/// .unwrap_err();
4993	/// // This error occurs because a size limit was exceeded.
4994	/// // But things are otherwise valid.
4995	/// assert!(err.is_size_limit_exceeded());
4996	///
4997	/// let err = dense::Builder::new()
4998	/// .build(r"\bxyz\b")
4999	/// .unwrap_err();
5000	/// // This error occurs because a Unicode word boundary
5001	/// // was used without enabling heuristic support for it.
5002	/// // So... not related to size limits.
5003	/// assert!(!err.is_size_limit_exceeded());
5004	///
5005	/// let err = dense::Builder::new()
5006	/// .build(r"(xyz")
5007	/// .unwrap_err();
5008	/// // This error occurs because the pattern is invalid.
5009	/// // So... not related to size limits.
5010	/// assert!(!err.is_size_limit_exceeded());
5011	///
5012	/// # Ok::<(), Box<dyn std::error::Error>>(())
5013	/// ```
5014	#[inline]
5015	pub fn is_size_limit_exceeded(&self) -> bool {
5016	use self::BuildErrorKind::*;
5017
5018	match self.kind {
5019	NFA(_) \| Unsupported(_) => `false`,
5020	TooManyStates
5021	\| TooManyStartStates
5022	\| TooManyMatchPatternIDs
5023	\| DFAExceededSizeLimit { .. }
5024	\| DeterminizeExceededSizeLimit { .. } => `true`,
5025	}
5026	}
5027	}
5028
5029	/// The kind of error that occurred during the construction of a DFA.
5030	///
5031	/// Note that this error is non-exhaustive. Adding new variants is not
5032	/// considered a breaking change.
5033	#[cfg(feature = "dfa-build")]
5034	#[derive(Clone, Debug)]
5035	enum BuildErrorKind {
5036	/// An error that occurred while constructing an NFA as a precursor step
5037	/// before a DFA is compiled.
5038	NFA(thompson::BuildError),
5039	/// An error that occurred because an unsupported regex feature was used.
5040	/// The message string describes which unsupported feature was used.
5041	///
5042	/// The primary regex feature that is unsupported by DFAs is the Unicode
5043	/// word boundary look-around assertion (`\b`). This can be worked around
5044	/// by either using an ASCII word boundary (`(?-u:\b)`) or by enabling
5045	/// Unicode word boundaries when building a DFA.
5046	Unsupported(&'static str),
5047	/// An error that occurs if too many states are produced while building a
5048	/// DFA.
5049	TooManyStates,
5050	/// An error that occurs if too many start states are needed while building
5051	/// a DFA.
5052	///
5053	/// This is a kind of oddball error that occurs when building a DFA with
5054	/// start states enabled for each pattern and enough patterns to cause
5055	/// the table of start states to overflow `usize`.
5056	TooManyStartStates,
5057	/// This is another oddball error that can occur if there are too many
5058	/// patterns spread out across too many match states.
5059	TooManyMatchPatternIDs,
5060	/// An error that occurs if the DFA got too big during determinization.
5061	DFAExceededSizeLimit { limit: usize },
5062	/// An error that occurs if auxiliary storage (not the DFA) used during
5063	/// determinization got too big.
5064	DeterminizeExceededSizeLimit { limit: usize },
5065	}
5066
5067	#[cfg(feature = "dfa-build")]
5068	impl BuildError {
5069	/// Return the kind of this error.
5070	fn kind(&self) -> &BuildErrorKind {
5071	&self.kind
5072	}
5073
5074	pub(crate) fn nfa(err: thompson::BuildError) -> BuildError {
5075	BuildError { kind: BuildErrorKind::NFA(err) }
5076	}
5077
5078	pub(crate) fn unsupported_dfa_word_boundary_unicode() -> BuildError {
5079	let msg = "cannot build DFAs for regexes with Unicode word \
5080	boundaries; switch to ASCII word boundaries, or \
5081	heuristically enable Unicode word boundaries or use a \
5082	different regex engine";
5083	BuildError { kind: BuildErrorKind::Unsupported(msg) }
5084	}
5085
5086	pub(crate) fn too_many_states() -> BuildError {
5087	BuildError { kind: BuildErrorKind::TooManyStates }
5088	}
5089
5090	pub(crate) fn too_many_start_states() -> BuildError {
5091	BuildError { kind: BuildErrorKind::TooManyStartStates }
5092	}
5093
5094	pub(crate) fn too_many_match_pattern_ids() -> BuildError {
5095	BuildError { kind: BuildErrorKind::TooManyMatchPatternIDs }
5096	}
5097
5098	pub(crate) fn dfa_exceeded_size_limit(limit: usize) -> BuildError {
5099	BuildError { kind: BuildErrorKind::DFAExceededSizeLimit { limit } }
5100	}
5101
5102	pub(crate) fn determinize_exceeded_size_limit(limit: usize) -> BuildError {
5103	BuildError {
5104	kind: BuildErrorKind::DeterminizeExceededSizeLimit { limit },
5105	}
5106	}
5107	}
5108
5109	#[cfg(all(feature = "std", feature = "dfa-build"))]
5110	impl std::error::Error for BuildError {
5111	fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
5112	match self.kind() {
5113	BuildErrorKind::NFA(ref err) => Some(err),
5114	_ => None,
5115	}
5116	}
5117	}
5118
5119	#[cfg(feature = "dfa-build")]
5120	impl core::fmt::Display for BuildError {
5121	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
5122	match self.kind() {
5123	BuildErrorKind::NFA(_) => write!(f, "error building NFA"),
5124	BuildErrorKind::Unsupported(ref msg) => {
5125	write!(f, "unsupported regex feature for DFAs: {}", msg)
5126	}
5127	BuildErrorKind::TooManyStates => write!(
5128	f,
5129	"number of DFA states exceeds limit of {}",
5130	StateID::LIMIT,
5131	),
5132	BuildErrorKind::TooManyStartStates => {
5133	let stride = Start::len();
5134	// The start table has `stride` entries for starting states for
5135	// the entire DFA, and then `stride` entries for each pattern
5136	// if start states for each pattern are enabled (which is the
5137	// only way this error can occur). Thus, the total number of
5138	// patterns that can fit in the table is `stride` less than
5139	// what we can allocate.
5140	let max = usize::try_from(core::isize::MAX).unwrap();
5141	let limit = (max - stride) / stride;
5142	write!(
5143	f,
5144	"compiling DFA with start states exceeds pattern \
5145	pattern limit of {}",
5146	limit,
5147	)
5148	}
5149	BuildErrorKind::TooManyMatchPatternIDs => write!(
5150	f,
5151	"compiling DFA with total patterns in all match states \
5152	exceeds limit of {}",
5153	PatternID::LIMIT,
5154	),
5155	BuildErrorKind::DFAExceededSizeLimit { limit } => write!(
5156	f,
5157	"DFA exceeded size limit of {:?} during determinization",
5158	limit,
5159	),
5160	BuildErrorKind::DeterminizeExceededSizeLimit { limit } => {
5161	write!(f, "determinization exceeded size limit of {:?}", limit)
5162	}
5163	}
5164	}
5165	}
5166
5167	#[cfg(all(test, feature = "syntax", feature = "dfa-build"))]
5168	mod tests {
5169	use crate::{Input, MatchError};
5170
5171	use super::*;
5172
5173	#[test]
5174	fn errors_with_unicode_word_boundary() {
5175	let pattern = r"\b";
5176	assert!(Builder::new().build(pattern).is_err());
5177	}
5178
5179	#[test]
5180	fn roundtrip_never_match() {
5181	let dfa = DFA::never_match().unwrap();
5182	let (buf, _) = dfa.to_bytes_native_endian();
5183	let dfa: DFA<&[u32]> = DFA::from_bytes(&buf).unwrap().0;
5184
5185	assert_eq!(None, dfa.try_search_fwd(&Input::new("foo12345")).unwrap());
5186	}
5187
5188	#[test]
5189	fn roundtrip_always_match() {
5190	use crate::HalfMatch;
5191
5192	let dfa = DFA::always_match().unwrap();
5193	let (buf, _) = dfa.to_bytes_native_endian();
5194	let dfa: DFA<&[u32]> = DFA::from_bytes(&buf).unwrap().0;
5195
5196	assert_eq!(
5197	Some(HalfMatch::must(`0`, `0`)),
5198	dfa.try_search_fwd(&Input::new("foo12345")).unwrap()
5199	);
5200	}
5201
5202	// See the analogous test in src/hybrid/dfa.rs.
5203	#[test]
5204	fn heuristic_unicode_reverse() {
5205	let dfa = DFA::builder()
5206	.configure(DFA::config().unicode_word_boundary(`true`))
5207	.thompson(thompson::Config::new().reverse(`true`))
5208	.build(r"\b[0-9]+\b")
5209	.unwrap();
5210
5211	let input = Input::new("β123").range(`2`..);
5212	let expected = MatchError::quit(`0xB2`, `1`);
5213	let got = dfa.try_search_rev(&input);
5214	assert_eq!(Err(expected), got);
5215
5216	let input = Input::new("123β").range(..`3`);
5217	let expected = MatchError::quit(`0xCE`, `3`);
5218	let got = dfa.try_search_rev(&input);
5219	assert_eq!(Err(expected), got);
5220	}
5221	}
5222