onepass.rs - Codebrowser

1	/!*
2	A DFA that can return spans for matching capturing groups.
3
4	This module is the home of a [one-pass DFA](DFA).
5
6	This module also contains a [`Builder`] and a [`Config`] for building and
7	configuring a one-pass DFA.
8	*/
9
10	// A note on naming and credit:
11	//
12	// As far as I know, Russ Cox came up with the practical vision and
13	// implementation of a "one-pass regex engine." He mentions and describes it
14	// briefly in the third article of his regexp article series:
15	// https://swtch.com/~rsc/regexp/regexp3.html
16	//
17	// Cox's implementation is in RE2, and the implementation below is most
18	// heavily inspired by RE2's. The key thing they have in common is that
19	// their transitions are defined over an alphabet of bytes. In contrast,
20	// Go's regex engine also has a one-pass engine, but its transitions are
21	// more firmly rooted on Unicode codepoints. The ideas are the same, but the
22	// implementations are different.
23	//
24	// RE2 tends to call this a "one-pass NFA." Here, we call it a "one-pass DFA."
25	// They're both true in their own ways:
26	//
27	// The "one-pass" criterion is generally a property of the NFA itself. In*
28	// particular, it is said that an NFA is one-pass if, after each byte of input
29	// during a search, there is at most one "VM thread" remaining to take for the
30	// next byte of input. That is, there is never any ambiguity as to the path to
31	// take through the NFA during a search.
32	//
33	// On the other hand, once a one-pass NFA has its representation converted*
34	// to something where a constant number of instructions is used for each byte
35	// of input, the implementation looks a lot more like a DFA. It's technically
36	// more powerful than a DFA since it has side effects (storing offsets inside
37	// of slots activated by a transition), but it is far closer to a DFA than an
38	// NFA simulation.
39	//
40	// Thus, in this crate, we call it a one-pass DFA.
41
42	use alloc::{vec, vec::Vec};
43
44	use crate::{
45	dfa::{remapper::Remapper, DEAD},
46	nfa::thompson::{self, NFA},
47	util::{
48	alphabet::ByteClasses,
49	captures::Captures,
50	escape::DebugByte,
51	int::{Usize, U32, U64, U8},
52	look::{Look, LookSet, UnicodeWordBoundaryError},
53	primitives::{NonMaxUsize, PatternID, StateID},
54	search::{Anchored, Input, Match, MatchError, MatchKind, Span},
55	sparse_set::SparseSet,
56	},
57	};
58
59	/// The configuration used for building a [one-pass DFA](DFA).
60	///
61	/// A one-pass DFA configuration is a simple data object that is typically used
62	/// with [`Builder::configure`]. It can be cheaply cloned.
63	///
64	/// A default configuration can be created either with `Config::new`, or
65	/// perhaps more conveniently, with [`DFA::config`].
66	#[derive(Clone, Debug, Default)]
67	pub struct Config {
68	match_kind: Option<MatchKind>,
69	starts_for_each_pattern: Option<bool>,
70	byte_classes: Option<bool>,
71	size_limit: Option<Option<usize>>,
72	}
73
74	impl Config {
75	/// Return a new default one-pass DFA configuration.
76	pub fn new() -> Config {
77	Config::default()
78	}
79
80	/// Set the desired match semantics.
81	///
82	/// The default is [`MatchKind::LeftmostFirst`], which corresponds to the
83	/// match semantics of Perl-like regex engines. That is, when multiple
84	/// patterns would match at the same leftmost position, the pattern that
85	/// appears first in the concrete syntax is chosen.
86	///
87	/// Currently, the only other kind of match semantics supported is
88	/// [`MatchKind::All`]. This corresponds to "classical DFA" construction
89	/// where all possible matches are visited.
90	///
91	/// When it comes to the one-pass DFA, it is rarer for preference order and
92	/// "longest match" to actually disagree. Since if they did disagree, then
93	/// the regex typically isn't one-pass. For example, searching `Samwise`
94	/// for `Sam\|Samwise` will report `Sam` for leftmost-first matching and
95	/// `Samwise` for "longest match" or "all" matching. However, this regex is
96	/// not one-pass if taken literally. The equivalent regex, `Sam(?:\|wise)`
97	/// is one-pass and `Sam\|Samwise` may be optimized to it.
98	///
99	/// The other main difference is that "all" match semantics don't support
100	/// non-greedy matches. "All" match semantics always try to match as much
101	/// as possible.
102	pub fn match_kind(mut self, kind: MatchKind) -> Config {
103	self.match_kind = Some(kind);
104	self
105	}
106
107	/// Whether to compile a separate start state for each pattern in the
108	/// one-pass DFA.
109	///
110	/// When enabled, a separate anchored* start state is added for each*
111	/// pattern in the DFA. When this start state is used, then the DFA will
112	/// only search for matches for the pattern specified, even if there are
113	/// other patterns in the DFA.
114	///
115	/// The main downside of this option is that it can potentially increase
116	/// the size of the DFA and/or increase the time it takes to build the DFA.
117	///
118	/// You might want to enable this option when you want to both search for
119	/// anchored matches of any pattern or to search for anchored matches of
120	/// one particular pattern while using the same DFA. (Otherwise, you would
121	/// need to compile a new DFA for each pattern.)
122	///
123	/// By default this is disabled.
124	///
125	/// # Example
126	///
127	/// This example shows how to build a multi-regex and then search for
128	/// matches for a any of the patterns or matches for a specific pattern.
129	///
130	/// ```
131	/// use regex_automata::{
132	/// dfa::onepass::DFA, Anchored, Input, Match, PatternID,
133	/// };
134	///
135	/// let re = DFA::builder()
136	/// .configure(DFA::config().starts_for_each_pattern(`true`))
137	/// .build_many(&["[a-z]+", "[0-9]+"])?;
138	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
139	/// let haystack = "123abc";
140	/// let input = Input::new(haystack).anchored(Anchored::Yes);
141	///
142	/// // A normal multi-pattern search will show pattern 1 matches.
143	/// re.try_search(&mut cache, &input, &mut caps)?;
144	/// assert_eq!(Some(Match::must(`1`, `0`..`3`)), caps.get_match());
145	///
146	/// // If we only want to report pattern 0 matches, then we'll get no
147	/// // match here.
148	/// let input = input.anchored(Anchored::Pattern(PatternID::must(`0`)));
149	/// re.try_search(&mut cache, &input, &mut caps)?;
150	/// assert_eq!(None, caps.get_match());
151	///
152	/// # Ok::<(), Box<dyn std::error::Error>>(())
153	/// ```
154	pub fn starts_for_each_pattern(mut self, yes: bool) -> Config {
155	self.starts_for_each_pattern = Some(yes);
156	self
157	}
158
159	/// Whether to attempt to shrink the size of the DFA's alphabet or not.
160	///
161	/// This option is enabled by default and should never be disabled unless
162	/// one is debugging a one-pass DFA.
163	///
164	/// When enabled, the DFA will use a map from all possible bytes to their
165	/// corresponding equivalence class. Each equivalence class represents a
166	/// set of bytes that does not discriminate between a match and a non-match
167	/// in the DFA. For example, the pattern `[ab]+` has at least two
168	/// equivalence classes: a set containing `a` and `b` and a set containing
169	/// every byte except for `a` and `b`. `a` and `b` are in the same
170	/// equivalence class because they never discriminate between a match and a
171	/// non-match.
172	///
173	/// The advantage of this map is that the size of the transition table
174	/// can be reduced drastically from (approximately) `#states * 256 *
175	/// sizeof(StateID)` to `#states k * sizeof(StateID)` where `k` is the*
176	/// number of equivalence classes (rounded up to the nearest power of 2).
177	/// As a result, total space usage can decrease substantially. Moreover,
178	/// since a smaller alphabet is used, DFA compilation becomes faster as
179	/// well.
180	///
181	/// WARNING:* This is only useful for debugging DFAs. Disabling this*
182	/// does not yield any speed advantages. Namely, even when this is
183	/// disabled, a byte class map is still used while searching. The only
184	/// difference is that every byte will be forced into its own distinct
185	/// equivalence class. This is useful for debugging the actual generated
186	/// transitions because it lets one see the transitions defined on actual
187	/// bytes instead of the equivalence classes.
188	pub fn byte_classes(mut self, yes: bool) -> Config {
189	self.byte_classes = Some(yes);
190	self
191	}
192
193	/// Set a size limit on the total heap used by a one-pass DFA.
194	///
195	/// This size limit is expressed in bytes and is applied during
196	/// construction of a one-pass DFA. If the DFA's heap usage exceeds
197	/// this configured limit, then construction is stopped and an error is
198	/// returned.
199	///
200	/// The default is no limit.
201	///
202	/// # Example
203	///
204	/// This example shows a one-pass DFA that fails to build because of
205	/// a configured size limit. This particular example also serves as a
206	/// cautionary tale demonstrating just how big DFAs with large Unicode
207	/// character classes can get.
208	///
209	/// ```
210	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
211	/// use regex_automata::{dfa::onepass::DFA, Match};
212	///
213	/// // 6MB isn't enough!
214	/// DFA::builder()
215	/// .configure(DFA::config().size_limit(Some(`6_000_000`)))
216	/// .build(r"\w{20}")
217	/// .unwrap_err();
218	///
219	/// // ... but 7MB probably is!
220	/// // (Note that DFA sizes aren't necessarily stable between releases.)
221	/// let re = DFA::builder()
222	/// .configure(DFA::config().size_limit(Some(`7_000_000`)))
223	/// .build(r"\w{20}")?;
224	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
225	/// let haystack = "A".repeat(`20`);
226	/// re.captures(&mut cache, &haystack, &mut caps);
227	/// assert_eq!(Some(Match::must(`0`, `0`..`20`)), caps.get_match());
228	///
229	/// # Ok::<(), Box<dyn std::error::Error>>(())
230	/// ```
231	///
232	/// While one needs a little more than 3MB to represent `\w{20}`, it
233	/// turns out that you only need a little more than 4KB to represent
234	/// `(?-u:\w{20})`. So only use Unicode if you need it!
235	pub fn size_limit(mut self, limit: Option<usize>) -> Config {
236	self.size_limit = Some(limit);
237	self
238	}
239
240	/// Returns the match semantics set in this configuration.
241	pub fn get_match_kind(&self) -> MatchKind {
242	self.match_kind.unwrap_or(MatchKind::LeftmostFirst)
243	}
244
245	/// Returns whether this configuration has enabled anchored starting states
246	/// for every pattern in the DFA.
247	pub fn get_starts_for_each_pattern(&self) -> bool {
248	self.starts_for_each_pattern.unwrap_or(`false`)
249	}
250
251	/// Returns whether this configuration has enabled byte classes or not.
252	/// This is typically a debugging oriented option, as disabling it confers
253	/// no speed benefit.
254	pub fn get_byte_classes(&self) -> bool {
255	self.byte_classes.unwrap_or(`true`)
256	}
257
258	/// Returns the DFA size limit of this configuration if one was set.
259	/// The size limit is total number of bytes on the heap that a DFA is
260	/// permitted to use. If the DFA exceeds this limit during construction,
261	/// then construction is stopped and an error is returned.
262	pub fn get_size_limit(&self) -> Option<usize> {
263	self.size_limit.unwrap_or(None)
264	}
265
266	/// Overwrite the default configuration such that the options in `o` are
267	/// always used. If an option in `o` is not set, then the corresponding
268	/// option in `self` is used. If it's not set in `self` either, then it
269	/// remains not set.
270	pub(crate) fn overwrite(&self, o: Config) -> Config {
271	Config {
272	match_kind: o.match_kind.or(self.match_kind),
273	starts_for_each_pattern: o
274	.starts_for_each_pattern
275	.or(self.starts_for_each_pattern),
276	byte_classes: o.byte_classes.or(self.byte_classes),
277	size_limit: o.size_limit.or(self.size_limit),
278	}
279	}
280	}
281
282	/// A builder for a [one-pass DFA](DFA).
283	///
284	/// This builder permits configuring options for the syntax of a pattern, the
285	/// NFA construction and the DFA construction. This builder is different from a
286	/// general purpose regex builder in that it permits fine grain configuration
287	/// of the construction process. The trade off for this is complexity, and
288	/// the possibility of setting a configuration that might not make sense. For
289	/// example, there are two different UTF-8 modes:
290	///
291	/// * [`syntax::Config::utf8`](crate::util::syntax::Config::utf8) controls
292	/// whether the pattern itself can contain sub-expressions that match invalid
293	/// UTF-8.
294	/// * [`thompson::Config::utf8`] controls whether empty matches that split a
295	/// Unicode codepoint are reported or not.
296	///
297	/// Generally speaking, callers will want to either enable all of these or
298	/// disable all of these.
299	///
300	/// # Example
301	///
302	/// This example shows how to disable UTF-8 mode in the syntax and the NFA.
303	/// This is generally what you want for matching on arbitrary bytes.
304	///
305	/// ```
306	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
307	/// use regex_automata::{
308	/// dfa::onepass::DFA,
309	/// nfa::thompson,
310	/// util::syntax,
311	/// Match,
312	/// };
313	///
314	/// let re = DFA::builder()
315	/// .syntax(syntax::Config::new().utf8(`false`))
316	/// .thompson(thompson::Config::new().utf8(`false`))
317	/// .build(r"foo(?-u:[^b])ar.*")?;
318	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
319	///
320	/// let haystack = b"foo`\xFF`arzz`\xE2\x98\xFF\n`";
321	/// re.captures(&mut cache, haystack, &mut caps);
322	/// // Notice that `(?-u:[^b])` matches invalid UTF-8,
323	/// // but the subsequent `.` does not! Disabling UTF-8*
324	/// // on the syntax permits this.
325	/// //
326	/// // N.B. This example does not show the impact of
327	/// // disabling UTF-8 mode on a one-pass DFA Config,
328	/// // since that only impacts regexes that can
329	/// // produce matches of length 0.
330	/// assert_eq!(Some(Match::must(`0`, `0`..`8`)), caps.get_match());
331	///
332	/// # Ok::<(), Box<dyn std::error::Error>>(())
333	/// ```
334	#[derive(Clone, Debug)]
335	pub struct Builder {
336	config: Config,
337	#[cfg(feature = "syntax")]
338	thompson: thompson::Compiler,
339	}
340
341	impl Builder {
342	/// Create a new one-pass DFA builder with the default configuration.
343	pub fn new() -> Builder {
344	Builder {
345	config: Config::default(),
346	#[cfg(feature = "syntax")]
347	thompson: thompson::Compiler::new(),
348	}
349	}
350
351	/// Build a one-pass DFA from the given pattern.
352	///
353	/// If there was a problem parsing or compiling the pattern, then an error
354	/// is returned.
355	#[cfg(feature = "syntax")]
356	pub fn build(&self, pattern: &str) -> Result<DFA, BuildError> {
357	self.build_many(&[pattern])
358	}
359
360	/// Build a one-pass DFA from the given patterns.
361	///
362	/// When matches are returned, the pattern ID corresponds to the index of
363	/// the pattern in the slice given.
364	#[cfg(feature = "syntax")]
365	pub fn build_many<P: AsRef<str>>(
366	&self,
367	patterns: &[P],
368	) -> Result<DFA, BuildError> {
369	let nfa =
370	self.thompson.build_many(patterns).map_err(BuildError::nfa)?;
371	self.build_from_nfa(nfa)
372	}
373
374	/// Build a DFA from the given NFA.
375	///
376	/// # Example
377	///
378	/// This example shows how to build a DFA if you already have an NFA in
379	/// hand.
380	///
381	/// ```
382	/// use regex_automata::{dfa::onepass::DFA, nfa::thompson::NFA, Match};
383	///
384	/// // This shows how to set non-default options for building an NFA.
385	/// let nfa = NFA::compiler()
386	/// .configure(NFA::config().shrink(`true`))
387	/// .build(r"[a-z0-9]+")?;
388	/// let re = DFA::builder().build_from_nfa(nfa)?;
389	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
390	/// re.captures(&mut cache, "foo123bar", &mut caps);
391	/// assert_eq!(Some(Match::must(`0`, `0`..`9`)), caps.get_match());
392	///
393	/// # Ok::<(), Box<dyn std::error::Error>>(())
394	/// ```
395	pub fn build_from_nfa(&self, nfa: NFA) -> Result<DFA, BuildError> {
396	// Why take ownership if we're just going to pass a reference to the
397	// NFA to our internal builder? Well, the first thing to note is that
398	// an NFA uses reference counting internally, so either choice is going
399	// to be cheap. So there isn't much cost either way.
400	//
401	// The real reason is that a one-pass DFA, semantically, shares
402	// ownership of an NFA. This is unlike other DFAs that don't share
403	// ownership of an NFA at all, primarily because they want to be
404	// self-contained in order to support cheap (de)serialization.
405	//
406	// But then why pass a '&nfa' below if we want to share ownership?
407	// Well, it turns out that using a '&NFA' in our internal builder
408	// separates its lifetime from the DFA we're building, and this turns
409	// out to make code a bit more composable. e.g., We can iterate over
410	// things inside the NFA while borrowing the builder as mutable because
411	// we know the NFA cannot be mutated. So TL;DR --- this weirdness is
412	// "because borrow checker."
413	InternalBuilder::new(self.config.clone(), &nfa).build()
414	}
415
416	/// Apply the given one-pass DFA configuration options to this builder.
417	pub fn configure(&mut self, config: Config) -> &mut Builder {
418	self.config = self.config.overwrite(config);
419	self
420	}
421
422	/// Set the syntax configuration for this builder using
423	/// [`syntax::Config`](crate::util::syntax::Config).
424	///
425	/// This permits setting things like case insensitivity, Unicode and multi
426	/// line mode.
427	///
428	/// These settings only apply when constructing a one-pass DFA directly
429	/// from a pattern.
430	#[cfg(feature = "syntax")]
431	pub fn syntax(
432	&mut self,
433	config: crate::util::syntax::Config,
434	) -> &mut Builder {
435	self.thompson.syntax(config);
436	self
437	}
438
439	/// Set the Thompson NFA configuration for this builder using
440	/// [`nfa::thompson::Config`](crate::nfa::thompson::Config).
441	///
442	/// This permits setting things like whether additional time should be
443	/// spent shrinking the size of the NFA.
444	///
445	/// These settings only apply when constructing a DFA directly from a
446	/// pattern.
447	#[cfg(feature = "syntax")]
448	pub fn thompson(&mut self, config: thompson::Config) -> &mut Builder {
449	self.thompson.configure(config);
450	self
451	}
452	}
453
454	/// An internal builder for encapsulating the state necessary to build a
455	/// one-pass DFA. Typical use is just `InternalBuilder::new(..).build()`.
456	///
457	/// There is no separate pass for determining whether the NFA is one-pass or
458	/// not. We just try to build the DFA. If during construction we discover that
459	/// it is not one-pass, we bail out. This is likely to lead to some undesirable
460	/// expense in some cases, so it might make sense to try an identify common
461	/// patterns in the NFA that make it definitively not one-pass. That way, we
462	/// can avoid ever trying to build a one-pass DFA in the first place. For
463	/// example, '\w\s' is not one-pass, and since '\w' is Unicode-aware by*
464	/// default, it's probably not a trivial cost to try and build a one-pass DFA
465	/// for it and then fail.
466	///
467	/// Note that some (immutable) fields are duplicated here. For example, the
468	/// 'nfa' and 'classes' fields are both in the 'DFA'. They are the same thing,
469	/// but we duplicate them because it makes composition easier below. Otherwise,
470	/// since the borrow checker can't see through method calls, the mutable borrow
471	/// we use to mutate the DFA winds up preventing borrowing from any other part
472	/// of the DFA, even though we aren't mutating those parts. We only do this
473	/// because the duplication is cheap.
474	#[derive(Debug)]
475	struct InternalBuilder<'a> {
476	/// The DFA we're building.
477	dfa: DFA,
478	/// An unordered collection of NFA state IDs that we haven't yet tried to
479	/// build into a DFA state yet.
480	///
481	/// This collection does not ultimately wind up including every NFA state
482	/// ID. Instead, each ID represents a "start" state for a sub-graph of the
483	/// NFA. The set of NFA states we then use to build a DFA state consists
484	/// of that "start" state and all states reachable from it via epsilon
485	/// transitions.
486	uncompiled_nfa_ids: Vec<StateID>,
487	/// A map from NFA state ID to DFA state ID. This is useful for easily
488	/// determining whether an NFA state has been used as a "starting" point
489	/// to build a DFA state yet. If it hasn't, then it is mapped to DEAD,
490	/// and since DEAD is specially added and never corresponds to any NFA
491	/// state, it follows that a mapping to DEAD implies the NFA state has
492	/// no corresponding DFA state yet.
493	nfa_to_dfa_id: Vec<StateID>,
494	/// A stack used to traverse the NFA states that make up a single DFA
495	/// state. Traversal occurs until the stack is empty, and we only push to
496	/// the stack when the state ID isn't in 'seen'. Actually, even more than
497	/// that, if we try to push something on to this stack that is already in
498	/// 'seen', then we bail out on construction completely, since it implies
499	/// that the NFA is not one-pass.
500	stack: Vec<(StateID, Epsilons)>,
501	/// The set of NFA states that we've visited via 'stack'.
502	seen: SparseSet,
503	/// Whether a match NFA state has been observed while constructing a
504	/// one-pass DFA state. Once a match state is seen, assuming we are using
505	/// leftmost-first match semantics, then we don't add any more transitions
506	/// to the DFA state we're building.
507	matched: bool,
508	/// The config passed to the builder.
509	///
510	/// This is duplicated in dfa.config.
511	config: Config,
512	/// The NFA we're building a one-pass DFA from.
513	///
514	/// This is duplicated in dfa.nfa.
515	nfa: &'a NFA,
516	/// The equivalence classes that make up the alphabet for this DFA>
517	///
518	/// This is duplicated in dfa.classes.
519	classes: ByteClasses,
520	}
521
522	impl<'a> InternalBuilder<'a> {
523	/// Create a new builder with an initial empty DFA.
524	fn new(config: Config, nfa: &'a NFA) -> InternalBuilder {
525	let classes = if !config.get_byte_classes() {
526	// A one-pass DFA will always use the equivalence class map, but
527	// enabling this option is useful for debugging. Namely, this will
528	// cause all transitions to be defined over their actual bytes
529	// instead of an opaque equivalence class identifier. The former is
530	// much easier to grok as a human.
531	ByteClasses::singletons()
532	} else {
533	nfa.byte_classes().clone()
534	};
535	// Normally a DFA alphabet includes the EOI symbol, but we don't need
536	// that in the one-pass DFA since we handle look-around explicitly
537	// without encoding it into the DFA. Thus, we don't need to delay
538	// matches by 1 byte. However, we reuse the space that would* be used*
539	// by the EOI transition by putting match information there (like which
540	// pattern matches and which look-around assertions need to hold). So
541	// this means our real alphabet length is 1 fewer than what the byte
542	// classes report, since we don't use EOI.
543	let alphabet_len = classes.alphabet_len().checked_sub(`1`).unwrap();
544	let stride2 = classes.stride2();
545	let dfa = DFA {
546	config: config.clone(),
547	nfa: nfa.clone(),
548	table: vec![],
549	starts: vec![],
550	// Since one-pass DFAs have a smaller state ID max than
551	// StateID::MAX, it follows that StateID::MAX is a valid initial
552	// value for min_match_id since no state ID can ever be greater
553	// than it. In the case of a one-pass DFA with no match states, the
554	// min_match_id will keep this sentinel value.
555	min_match_id: StateID::MAX,
556	classes: classes.clone(),
557	alphabet_len,
558	stride2,
559	pateps_offset: alphabet_len,
560	// OK because PatternID::MAX2 is guaranteed not to overflow.*
561	explicit_slot_start: nfa.pattern_len().checked_mul(`2`).unwrap(),
562	};
563	InternalBuilder {
564	dfa,
565	uncompiled_nfa_ids: vec![],
566	nfa_to_dfa_id: vec![DEAD; nfa.states().len()],
567	stack: vec![],
568	seen: SparseSet::new(nfa.states().len()),
569	matched: `false`,
570	config,
571	nfa,
572	classes,
573	}
574	}
575
576	/// Build the DFA from the NFA given to this builder. If the NFA is not
577	/// one-pass, then return an error. An error may also be returned if a
578	/// particular limit is exceeded. (Some limits, like the total heap memory
579	/// used, are configurable. Others, like the total patterns or slots, are
580	/// hard-coded based on representational limitations.)
581	fn build(mut self) -> Result<DFA, BuildError> {
582	self.nfa.look_set_any().available().map_err(BuildError::word)?;
583	for look in self.nfa.look_set_any().iter() {
584	// This is a future incompatibility check where if we add any
585	// more look-around assertions, then the one-pass DFA either
586	// needs to reject them (what we do here) or it needs to have its
587	// Transition representation modified to be capable of storing the
588	// new assertions.
589	if look.as_repr() > Look::WordUnicodeNegate.as_repr() {
590	return Err(BuildError::unsupported_look(look));
591	}
592	}
593	if self.nfa.pattern_len().as_u64() > PatternEpsilons::PATTERN_ID_LIMIT
594	{
595	return Err(BuildError::too_many_patterns(
596	PatternEpsilons::PATTERN_ID_LIMIT,
597	));
598	}
599	if self.nfa.group_info().explicit_slot_len() > Slots::LIMIT {
600	return Err(BuildError::not_one_pass(
601	"too many explicit capturing groups (max is 16)",
602	));
603	}
604	assert_eq!(DEAD, self.add_empty_state()?);
605
606	// This is where the explicit slots start. We care about this because
607	// we only need to track explicit slots. The implicit slots---two for
608	// each pattern---are tracked as part of the search routine itself.
609	let explicit_slot_start = self.nfa.pattern_len() * `2`;
610	self.add_start_state(None, self.nfa.start_anchored())?;
611	if self.config.get_starts_for_each_pattern() {
612	for pid in self.nfa.patterns() {
613	self.add_start_state(
614	Some(pid),
615	self.nfa.start_pattern(pid).unwrap(),
616	)?;
617	}
618	}
619	// NOTE: One wonders what the effects of treating 'uncompiled_nfa_ids'
620	// as a stack are. It is really an unordered set* of NFA state IDs.*
621	// If it, for example, in practice led to discovering whether a regex
622	// was or wasn't one-pass later than if we processed NFA state IDs in
623	// ascending order, then that would make this routine more costly in
624	// the somewhat common case of a regex that isn't one-pass.
625	while let Some(nfa_id) = self.uncompiled_nfa_ids.pop() {
626	let dfa_id = self.nfa_to_dfa_id[nfa_id];
627	// Once we see a match, we keep going, but don't add any new
628	// transitions. Normally we'd just stop, but we have to keep
629	// going in order to verify that our regex is actually one-pass.
630	self.matched = `false`;
631	// The NFA states we've already explored for this DFA state.
632	self.seen.clear();
633	// The NFA states to explore via epsilon transitions. If we ever
634	// try to push an NFA state that we've already seen, then the NFA
635	// is not one-pass because it implies there are multiple epsilon
636	// transition paths that lead to the same NFA state. In other
637	// words, there is ambiguity.
638	self.stack_push(nfa_id, Epsilons::empty())?;
639	while let Some((id, epsilons)) = self.stack.pop() {
640	match *self.nfa.state(id) {
641	thompson::State::ByteRange { ref trans } => {
642	self.compile_transition(dfa_id, trans, epsilons)?;
643	}
644	thompson::State::Sparse(ref sparse) => {
645	for trans in sparse.transitions.iter() {
646	self.compile_transition(dfa_id, trans, epsilons)?;
647	}
648	}
649	thompson::State::Dense(ref dense) => {
650	for trans in dense.iter() {
651	self.compile_transition(dfa_id, &trans, epsilons)?;
652	}
653	}
654	thompson::State::Look { look, next } => {
655	let looks = epsilons.looks().insert(look);
656	self.stack_push(next, epsilons.set_looks(looks))?;
657	}
658	thompson::State::Union { ref alternates } => {
659	for &sid in alternates.iter().rev() {
660	self.stack_push(sid, epsilons)?;
661	}
662	}
663	thompson::State::BinaryUnion { alt1, alt2 } => {
664	self.stack_push(alt2, epsilons)?;
665	self.stack_push(alt1, epsilons)?;
666	}
667	thompson::State::Capture { next, slot, .. } => {
668	let slot = slot.as_usize();
669	let epsilons = if slot < explicit_slot_start {
670	// If this is an implicit slot, we don't care
671	// about it, since we handle implicit slots in
672	// the search routine. We can get away with that
673	// because there are 2 implicit slots for every
674	// pattern.
675	epsilons
676	} else {
677	// Offset our explicit slots so that they start
678	// at index 0.
679	let offset = slot - explicit_slot_start;
680	epsilons.set_slots(epsilons.slots().insert(offset))
681	};
682	self.stack_push(next, epsilons)?;
683	}
684	thompson::State::Fail => {
685	continue;
686	}
687	thompson::State::Match { pattern_id } => {
688	// If we found two different paths to a match state
689	// for the same DFA state, then we have ambiguity.
690	// Thus, it's not one-pass.
691	if self.matched {
692	return Err(BuildError::not_one_pass(
693	"multiple epsilon transitions to match state",
694	));
695	}
696	self.matched = `true`;
697	// Shove the matching pattern ID and the 'epsilons'
698	// into the current DFA state's pattern epsilons. The
699	// 'epsilons' includes the slots we need to capture
700	// before reporting the match and also the conditional
701	// epsilon transitions we need to check before we can
702	// report a match.
703	self.dfa.set_pattern_epsilons(
704	dfa_id,
705	PatternEpsilons::empty()
706	.set_pattern_id(pattern_id)
707	.set_epsilons(epsilons),
708	);
709	// N.B. It is tempting to just bail out here when
710	// compiling a leftmost-first DFA, since we will never
711	// compile any more transitions in that case. But we
712	// actually need to keep going in order to verify that
713	// we actually have a one-pass regex. e.g., We might
714	// see more Match states (e.g., for other patterns)
715	// that imply that we don't have a one-pass regex.
716	// So instead, we mark that we've found a match and
717	// continue on. When we go to compile a new DFA state,
718	// we just skip that part. But otherwise check that the
719	// one-pass property is upheld.
720	}
721	}
722	}
723	}
724	self.shuffle_states();
725	Ok(self.dfa)
726	}
727
728	/// Shuffle all match states to the end of the transition table and set
729	/// 'min_match_id' to the ID of the first such match state.
730	///
731	/// The point of this is to make it extremely cheap to determine whether
732	/// a state is a match state or not. We need to check on this on every
733	/// transition during a search, so it being cheap is important. This
734	/// permits us to check it by simply comparing two state identifiers, as
735	/// opposed to looking for the pattern ID in the state's `PatternEpsilons`.
736	/// (Which requires a memory load and some light arithmetic.)
737	fn shuffle_states(&mut self) {
738	let mut remapper = Remapper::new(&self.dfa);
739	let mut next_dest = self.dfa.last_state_id();
740	for i in (`0`..self.dfa.state_len()).rev() {
741	let id = StateID::must(i);
742	let is_match =
743	self.dfa.pattern_epsilons(id).pattern_id().is_some();
744	if !is_match {
745	continue;
746	}
747	remapper.swap(&mut self.dfa, next_dest, id);
748	self.dfa.min_match_id = next_dest;
749	next_dest = self.dfa.prev_state_id(next_dest).expect(
750	"match states should be a proper subset of all states",
751	);
752	}
753	remapper.remap(&mut self.dfa);
754	}
755
756	/// Compile the given NFA transition into the DFA state given.
757	///
758	/// 'Epsilons' corresponds to any conditional epsilon transitions that need
759	/// to be satisfied to follow this transition, and any slots that need to
760	/// be saved if the transition is followed.
761	///
762	/// If this transition indicates that the NFA is not one-pass, then
763	/// this returns an error. (This occurs, for example, if the DFA state
764	/// already has a transition defined for the same input symbols as the
765	/// given transition, and* the result of the old and new transitions is*
766	/// different.)
767	fn compile_transition(
768	&mut self,
769	dfa_id: StateID,
770	trans: &thompson::Transition,
771	epsilons: Epsilons,
772	) -> Result<(), BuildError> {
773	let next_dfa_id = self.add_dfa_state_for_nfa_state(trans.next)?;
774	for byte in self
775	.classes
776	.representatives(trans.start..=trans.end)
777	.filter_map(\|r\| r.as_u8())
778	{
779	let oldtrans = self.dfa.transition(dfa_id, byte);
780	let newtrans =
781	Transition::new(self.matched, next_dfa_id, epsilons);
782	// If the old transition points to the DEAD state, then we know
783	// 'byte' has not been mapped to any transition for this DFA state
784	// yet. So set it unconditionally. Otherwise, we require that the
785	// old and new transitions are equivalent. Otherwise, there is
786	// ambiguity and thus the regex is not one-pass.
787	if oldtrans.state_id() == DEAD {
788	self.dfa.set_transition(dfa_id, byte, newtrans);
789	} else if oldtrans != newtrans {
790	return Err(BuildError::not_one_pass(
791	"conflicting transition",
792	));
793	}
794	}
795	Ok(())
796	}
797
798	/// Add a start state to the DFA corresponding to the given NFA starting
799	/// state ID.
800	///
801	/// If adding a state would blow any limits (configured or hard-coded),
802	/// then an error is returned.
803	///
804	/// If the starting state is an anchored state for a particular pattern,
805	/// then callers must provide the pattern ID for that starting state.
806	/// Callers must also ensure that the first starting state added is the
807	/// start state for all patterns, and then each anchored starting state for
808	/// each pattern (if necessary) added in order. Otherwise, this panics.
809	fn add_start_state(
810	&mut self,
811	pid: Option<PatternID>,
812	nfa_id: StateID,
813	) -> Result<StateID, BuildError> {
814	match pid {
815	// With no pid, this should be the start state for all patterns
816	// and thus be the first one.
817	None => assert!(self.dfa.starts.is_empty()),
818	// With a pid, we want it to be at self.dfa.starts[pid+1].
819	Some(pid) => assert!(self.dfa.starts.len() == pid.one_more()),
820	}
821	let dfa_id = self.add_dfa_state_for_nfa_state(nfa_id)?;
822	self.dfa.starts.push(dfa_id);
823	Ok(dfa_id)
824	}
825
826	/// Add a new DFA state corresponding to the given NFA state. If adding a
827	/// state would blow any limits (configured or hard-coded), then an error
828	/// is returned. If a DFA state already exists for the given NFA state,
829	/// then that DFA state's ID is returned and no new states are added.
830	///
831	/// It is not expected that this routine is called for every NFA state.
832	/// Instead, an NFA state ID will usually correspond to the "start" state
833	/// for a sub-graph of the NFA, where all states in the sub-graph are
834	/// reachable via epsilon transitions (conditional or unconditional). That
835	/// sub-graph of NFA states is ultimately what produces a single DFA state.
836	fn add_dfa_state_for_nfa_state(
837	&mut self,
838	nfa_id: StateID,
839	) -> Result<StateID, BuildError> {
840	// If we've already built a DFA state for the given NFA state, then
841	// just return that. We definitely do not want to have more than one
842	// DFA state in existence for the same NFA state, since all but one of
843	// them will likely become unreachable. And at least some of them are
844	// likely to wind up being incomplete.
845	let existing_dfa_id = self.nfa_to_dfa_id[nfa_id];
846	if existing_dfa_id != DEAD {
847	return Ok(existing_dfa_id);
848	}
849	// If we don't have any DFA state yet, add it and then add the given
850	// NFA state to the list of states to explore.
851	let dfa_id = self.add_empty_state()?;
852	self.nfa_to_dfa_id[nfa_id] = dfa_id;
853	self.uncompiled_nfa_ids.push(nfa_id);
854	Ok(dfa_id)
855	}
856
857	/// Unconditionally add a new empty DFA state. If adding it would exceed
858	/// any limits (configured or hard-coded), then an error is returned. The
859	/// ID of the new state is returned on success.
860	///
861	/// The added state is not* a match state.*
862	fn add_empty_state(&mut self) -> Result<StateID, BuildError> {
863	let state_limit = Transition::STATE_ID_LIMIT;
864	// Note that unlike dense and lazy DFAs, we specifically do NOT
865	// premultiply our state IDs here. The reason is that we want to pack
866	// our state IDs into 64-bit transitions with other info, so the fewer
867	// the bits we use for state IDs the better. If we premultiply, then
868	// our state ID space shrinks. We justify this by the assumption that
869	// a one-pass DFA is just already doing a fair bit more work than a
870	// normal DFA anyway, so an extra multiplication to compute a state
871	// transition doesn't seem like a huge deal.
872	let next_id = self.dfa.table.len() >> self.dfa.stride2();
873	let id = StateID::new(next_id)
874	.map_err(\|_\| BuildError::too_many_states(state_limit))?;
875	if id.as_u64() > Transition::STATE_ID_LIMIT {
876	return Err(BuildError::too_many_states(state_limit));
877	}
878	self.dfa
879	.table
880	.extend(core::iter::repeat(Transition(`0`)).take(self.dfa.stride()));
881	// The default empty value for 'PatternEpsilons' is sadly not all
882	// zeroes. Instead, a special sentinel is used to indicate that there
883	// is no pattern. So we need to explicitly set the pattern epsilons to
884	// the correct "empty" PatternEpsilons.
885	self.dfa.set_pattern_epsilons(id, PatternEpsilons::empty());
886	if let Some(size_limit) = self.config.get_size_limit() {
887	if self.dfa.memory_usage() > size_limit {
888	return Err(BuildError::exceeded_size_limit(size_limit));
889	}
890	}
891	Ok(id)
892	}
893
894	/// Push the given NFA state ID and its corresponding epsilons (slots and
895	/// conditional epsilon transitions) on to a stack for use in a depth first
896	/// traversal of a sub-graph of the NFA.
897	///
898	/// If the given NFA state ID has already been pushed on to the stack, then
899	/// it indicates the regex is not one-pass and this correspondingly returns
900	/// an error.
901	fn stack_push(
902	&mut self,
903	nfa_id: StateID,
904	epsilons: Epsilons,
905	) -> Result<(), BuildError> {
906	// If we already have seen a match and we are compiling a leftmost
907	// first DFA, then we shouldn't add any more states to look at. This is
908	// effectively how preference order and non-greediness is implemented.
909	// if !self.config.get_match_kind().continue_past_first_match()
910	// && self.matched
911	// {
912	// return Ok(());
913	// }
914	if !self.seen.insert(nfa_id) {
915	return Err(BuildError::not_one_pass(
916	"multiple epsilon transitions to same state",
917	));
918	}
919	self.stack.push((nfa_id, epsilons));
920	Ok(())
921	}
922	}
923
924	/// A one-pass DFA for executing a subset of anchored regex searches while
925	/// resolving capturing groups.
926	///
927	/// A one-pass DFA can be built from an NFA that is one-pass. An NFA is
928	/// one-pass when there is never any ambiguity about how to continue a search.
929	/// For example, `aa` is not one-pass becuase during a search, it's not*
930	/// possible to know whether to continue matching the `a` or to move on to*
931	/// the single `a`. However, `ab` is one-pass, because for every byte in the*
932	/// input, it's always clear when to move on from `a` to `b`.*
933	///
934	/// # Only anchored searches are supported
935	///
936	/// In this crate, especially for DFAs, unanchored searches are implemented by
937	/// treating the pattern as if it had a `(?s-u:.)?` prefix. While the prefix*
938	/// is one-pass on its own, adding anything after it, e.g., `(?s-u:.)?a` will*
939	/// make the overall pattern not one-pass. Why? Because the `(?s-u:.)` matches
940	/// any byte, and there is therefore ambiguity as to when the prefix should
941	/// stop matching and something else should start matching.
942	///
943	/// Therefore, one-pass DFAs do not support unanchored searches. In addition
944	/// to many regexes simply not being one-pass, it implies that one-pass DFAs
945	/// have limited utility. With that said, when a one-pass DFA can be used, it
946	/// can potentially provide a dramatic speed up over alternatives like the
947	/// [`BoundedBacktracker`](crate::nfa::thompson::backtrack::BoundedBacktracker)
948	/// and the [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM). In particular,
949	/// a one-pass DFA is the only DFA capable of reporting the spans of matching
950	/// capturing groups.
951	///
952	/// To clarify, when we say that unanchored searches are not supported, what
953	/// that actually means is:
954	///
955	/// The high level routines, [`DFA::is_match`] and [`DFA::captures`], always*
956	/// do anchored searches.
957	/// Since iterators are most useful in the context of unanchored searches,*
958	/// there is no `DFA::captures_iter` method.
959	/// For lower level routines like [`DFA::try_search`], an error will be*
960	/// returned if the given [`Input`] is configured to do an unanchored search or
961	/// search for an invalid pattern ID. (Note that an [`Input`] is configured to
962	/// do an unanchored search by default, so just giving a `Input::new` is
963	/// guaranteed to return an error.)
964	///
965	/// # Other limitations
966	///
967	/// In addition to the [configurable heap limit](Config::size_limit) and
968	/// the requirement that a regex pattern be one-pass, there are some other
969	/// limitations:
970	///
971	/// There is an internal limit on the total number of explicit capturing*
972	/// groups that appear across all patterns. It is somewhat small and there is
973	/// no way to configure it. If your pattern(s) exceed this limit, then building
974	/// a one-pass DFA will fail.
975	/// If the number of patterns exceeds an internal unconfigurable limit, then*
976	/// building a one-pass DFA will fail. This limit is quite large and you're
977	/// unlikely to hit it.
978	/// If the total number of states exceeds an internal unconfigurable limit,*
979	/// then building a one-pass DFA will fail. This limit is quite large and
980	/// you're unlikely to hit it.
981	///
982	/// # Other examples of regexes that aren't one-pass
983	///
984	/// One particularly unfortunate example is that enabling Unicode can cause
985	/// regexes that were one-pass to no longer be one-pass. Consider the regex
986	/// `(?-u)\w\s` for example. It is one-pass because there is exactly no*
987	/// overlap between the ASCII definitions of `\w` and `\s`. But `\w\s`*
988	/// (i.e., with Unicode enabled) is not* one-pass because `\w` and `\s` get*
989	/// translated to UTF-8 automatons. And while the codepoints* in `\w` and `\s`*
990	/// do not overlap, the underlying UTF-8 encodings do. Indeed, because of the
991	/// overlap between UTF-8 automata, the use of Unicode character classes will
992	/// tend to vastly increase the likelihood of a regex not being one-pass.
993	///
994	/// # How does one know if a regex is one-pass or not?
995	///
996	/// At the time of writing, the only way to know is to try and build a one-pass
997	/// DFA. The one-pass property is checked while constructing the DFA.
998	///
999	/// This does mean that you might potentially waste some CPU cycles and memory
1000	/// by optimistically trying to build a one-pass DFA. But this is currently the
1001	/// only way. In the future, building a one-pass DFA might be able to use some
1002	/// heuristics to detect common violations of the one-pass property and bail
1003	/// more quickly.
1004	///
1005	/// # Resource usage
1006	///
1007	/// Unlike a general DFA, a one-pass DFA has stricter bounds on its resource
1008	/// usage. Namely, construction of a one-pass DFA has a time and space
1009	/// complexity of `O(n)`, where `n ~ nfa.states().len()`. (A general DFA's time
1010	/// and space complexity is `O(2^n)`.) This smaller time bound is achieved
1011	/// because there is at most one DFA state created for each NFA state. If
1012	/// additional DFA states would be required, then the pattern is not one-pass
1013	/// and construction will fail.
1014	///
1015	/// Note though that currently, this DFA uses a fully dense representation.
1016	/// This means that while its space complexity is no worse than an NFA, it may
1017	/// in practice use more memory because of higher constant factors. The reason
1018	/// for this trade off is two-fold. Firstly, a dense representation makes the
1019	/// search faster. Secondly, the bigger an NFA, the more unlikely it is to be
1020	/// one-pass. Therefore, most one-pass DFAs are usually pretty small.
1021	///
1022	/// # Example
1023	///
1024	/// This example shows that the one-pass DFA implements Unicode word boundaries
1025	/// correctly while simultaneously reporting spans for capturing groups that
1026	/// participate in a match. (This is the only DFA that implements full support
1027	/// for Unicode word boundaries.)
1028	///
1029	/// ```
1030	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
1031	/// use regex_automata::{dfa::onepass::DFA, Match, Span};
1032	///
1033	/// let re = DFA::new(r"\b(?P<first>\w+)[[:space:]]+(?P<last>\w+)\b")?;
1034	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
1035	///
1036	/// re.captures(&mut cache, "Шерлок Холмс", &mut caps);
1037	/// assert_eq!(Some(Match::must(`0`, `0`..`23`)), caps.get_match());
1038	/// assert_eq!(Some(Span::from(`0`..`12`)), caps.get_group_by_name("first"));
1039	/// assert_eq!(Some(Span::from(`13`..`23`)), caps.get_group_by_name("last"));
1040	/// # Ok::<(), Box<dyn std::error::Error>>(())
1041	/// ```
1042	///
1043	/// # Example: iteration
1044	///
1045	/// Unlike other regex engines in this crate, this one does not provide
1046	/// iterator search functions. This is because a one-pass DFA only supports
1047	/// anchored searches, and so iterator functions are generally not applicable.
1048	///
1049	/// However, if you know that all of your matches are
1050	/// directly adjacent, then an iterator can be used. The
1051	/// [`util::iter::Searcher`](crate::util::iter::Searcher) type can be used for
1052	/// this purpose:
1053	///
1054	/// ```
1055	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
1056	/// use regex_automata::{
1057	/// dfa::onepass::DFA,
1058	/// util::iter::Searcher,
1059	/// Anchored, Input, Span,
1060	/// };
1061	///
1062	/// let re = DFA::new(r"\w(\d)\w")?;
1063	/// let (mut cache, caps) = (re.create_cache(), re.create_captures());
1064	/// let input = Input::new("a1zb2yc3x").anchored(Anchored::Yes);
1065	///
1066	/// let mut it = Searcher::new(input).into_captures_iter(caps, \|input, caps\| {
1067	/// Ok(re.try_search(&mut cache, input, caps)?)
1068	/// }).infallible();
1069	/// let caps0 = it.next().unwrap();
1070	/// assert_eq!(Some(Span::from(`1`..`2`)), caps0.get_group(`1`));
1071	///
1072	/// # Ok::<(), Box<dyn std::error::Error>>(())
1073	/// ```
1074	#[derive(Clone)]
1075	pub struct DFA {
1076	/// The configuration provided by the caller.
1077	config: Config,
1078	/// The NFA used to build this DFA.
1079	///
1080	/// NOTE: We probably don't need to store the NFA here, but we use enough
1081	/// bits from it that it's convenient to do so. And there really isn't much
1082	/// cost to doing so either, since an NFA is reference counted internally.
1083	nfa: NFA,
1084	/// The transition table. Given a state ID 's' and a byte of haystack 'b',
1085	/// the next state is `table[sid + classes[byte]]`.
1086	///
1087	/// The stride of this table (i.e., the number of columns) is always
1088	/// a power of 2, even if the alphabet length is smaller. This makes
1089	/// converting between state IDs and state indices very cheap.
1090	///
1091	/// Note that the stride always includes room for one extra "transition"
1092	/// that isn't actually a transition. It is a 'PatternEpsilons' that is
1093	/// used for match states only. Because of this, the maximum number of
1094	/// active columns in the transition table is 257, which means the maximum
1095	/// stride is 512 (the next power of 2 greater than or equal to 257).
1096	table: Vec<Transition>,
1097	/// The DFA state IDs of the starting states.
1098	///
1099	/// `starts[0]` is always present and corresponds to the starting state
1100	/// when searching for matches of any pattern in the DFA.
1101	///
1102	/// `starts[i]` where i>0 corresponds to the starting state for the pattern
1103	/// ID 'i-1'. These starting states are optional.
1104	starts: Vec<StateID>,
1105	/// Every state ID >= this value corresponds to a match state.
1106	///
1107	/// This is what a search uses to detect whether a state is a match state
1108	/// or not. It requires only a simple comparison instead of bit-unpacking
1109	/// the PatternEpsilons from every state.
1110	min_match_id: StateID,
1111	/// The alphabet of this DFA, split into equivalence classes. Bytes in the
1112	/// same equivalence class can never discriminate between a match and a
1113	/// non-match.
1114	classes: ByteClasses,
1115	/// The number of elements in each state in the transition table. This may
1116	/// be less than the stride, since the stride is always a power of 2 and
1117	/// the alphabet length can be anything up to and including 256.
1118	alphabet_len: usize,
1119	/// The number of columns in the transition table, expressed as a power of
1120	/// 2.
1121	stride2: usize,
1122	/// The offset at which the PatternEpsilons for a match state is stored in
1123	/// the transition table.
1124	///
1125	/// PERF: One wonders whether it would be better to put this in a separate
1126	/// allocation, since only match states have a non-empty PatternEpsilons
1127	/// and the number of match states tends be dwarfed by the number of
1128	/// non-match states. So this would save '8len(non_match_states)' for each*
1129	/// DFA. The question is whether moving this to a different allocation will
1130	/// lead to a perf hit during searches. You might think dealing with match
1131	/// states is rare, but some regexes spend a lot of time in match states
1132	/// gobbling up input. But... match state handling is already somewhat
1133	/// expensive, so maybe this wouldn't do much? Either way, it's worth
1134	/// experimenting.
1135	pateps_offset: usize,
1136	/// The first explicit slot index. This refers to the first slot appearing
1137	/// immediately after the last implicit slot. It is always 'patterns.len()
1138	/// 2'.*
1139	///
1140	/// We record this because we only store the explicit slots in our DFA
1141	/// transition table that need to be saved. Implicit slots are handled
1142	/// automatically as part of the search.
1143	explicit_slot_start: usize,
1144	}
1145
1146	impl DFA {
1147	/// Parse the given regular expression using the default configuration and
1148	/// return the corresponding one-pass DFA.
1149	///
1150	/// If you want a non-default configuration, then use the [`Builder`] to
1151	/// set your own configuration.
1152	///
1153	/// # Example
1154	///
1155	/// ```
1156	/// use regex_automata::{dfa::onepass::DFA, Match};
1157	///
1158	/// let re = DFA::new("foo[0-9]+bar")?;
1159	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
1160	///
1161	/// re.captures(&mut cache, "foo12345barzzz", &mut caps);
1162	/// assert_eq!(Some(Match::must(`0`, `0`..`11`)), caps.get_match());
1163	/// # Ok::<(), Box<dyn std::error::Error>>(())
1164	/// ```
1165	#[cfg(feature = "syntax")]
1166	#[inline]
1167	pub fn new(pattern: &str) -> Result<DFA, BuildError> {
1168	DFA::builder().build(pattern)
1169	}
1170
1171	/// Like `new`, but parses multiple patterns into a single "multi regex."
1172	/// This similarly uses the default regex configuration.
1173	///
1174	/// # Example
1175	///
1176	/// ```
1177	/// use regex_automata::{dfa::onepass::DFA, Match};
1178	///
1179	/// let re = DFA::new_many(&["[a-z]+", "[0-9]+"])?;
1180	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
1181	///
1182	/// re.captures(&mut cache, "abc123", &mut caps);
1183	/// assert_eq!(Some(Match::must(`0`, `0`..`3`)), caps.get_match());
1184	///
1185	/// re.captures(&mut cache, "123abc", &mut caps);
1186	/// assert_eq!(Some(Match::must(`1`, `0`..`3`)), caps.get_match());
1187	///
1188	/// # Ok::<(), Box<dyn std::error::Error>>(())
1189	/// ```
1190	#[cfg(feature = "syntax")]
1191	#[inline]
1192	pub fn new_many<P: AsRef<str>>(patterns: &[P]) -> Result<DFA, BuildError> {
1193	DFA::builder().build_many(patterns)
1194	}
1195
1196	/// Like `new`, but builds a one-pass DFA directly from an NFA. This is
1197	/// useful if you already have an NFA, or even if you hand-assembled the
1198	/// NFA.
1199	///
1200	/// # Example
1201	///
1202	/// This shows how to hand assemble a regular expression via its HIR,
1203	/// compile an NFA from it and build a one-pass DFA from the NFA.
1204	///
1205	/// ```
1206	/// use regex_automata::{
1207	/// dfa::onepass::DFA,
1208	/// nfa::thompson::NFA,
1209	/// Match,
1210	/// };
1211	/// use regex_syntax::hir::{Hir, Class, ClassBytes, ClassBytesRange};
1212	///
1213	/// let hir = Hir::class(Class::Bytes(ClassBytes::new(vec![
1214	/// ClassBytesRange::new(b'0', b'9'),
1215	/// ClassBytesRange::new(b'A', b'Z'),
1216	/// ClassBytesRange::new(b'_', b'_'),
1217	/// ClassBytesRange::new(b'a', b'z'),
1218	/// ])));
1219	///
1220	/// let config = NFA::config().nfa_size_limit(Some(`1_000`));
1221	/// let nfa = NFA::compiler().configure(config).build_from_hir(&hir)?;
1222	///
1223	/// let re = DFA::new_from_nfa(nfa)?;
1224	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
1225	/// let expected = Some(Match::must(`0`, `0`..`1`));
1226	/// re.captures(&mut cache, "A", &mut caps);
1227	/// assert_eq!(expected, caps.get_match());
1228	///
1229	/// # Ok::<(), Box<dyn std::error::Error>>(())
1230	/// ```
1231	pub fn new_from_nfa(nfa: NFA) -> Result<DFA, BuildError> {
1232	DFA::builder().build_from_nfa(nfa)
1233	}
1234
1235	/// Create a new one-pass DFA that matches every input.
1236	///
1237	/// # Example
1238	///
1239	/// ```
1240	/// use regex_automata::{dfa::onepass::DFA, Match};
1241	///
1242	/// let dfa = DFA::always_match()?;
1243	/// let mut cache = dfa.create_cache();
1244	/// let mut caps = dfa.create_captures();
1245	///
1246	/// let expected = Match::must(`0`, `0`..`0`);
1247	/// dfa.captures(&mut cache, "", &mut caps);
1248	/// assert_eq!(Some(expected), caps.get_match());
1249	/// dfa.captures(&mut cache, "foo", &mut caps);
1250	/// assert_eq!(Some(expected), caps.get_match());
1251	/// # Ok::<(), Box<dyn std::error::Error>>(())
1252	/// ```
1253	pub fn always_match() -> Result<DFA, BuildError> {
1254	let nfa = thompson::NFA::always_match();
1255	Builder::new().build_from_nfa(nfa)
1256	}
1257
1258	/// Create a new one-pass DFA that never matches any input.
1259	///
1260	/// # Example
1261	///
1262	/// ```
1263	/// use regex_automata::dfa::onepass::DFA;
1264	///
1265	/// let dfa = DFA::never_match()?;
1266	/// let mut cache = dfa.create_cache();
1267	/// let mut caps = dfa.create_captures();
1268	///
1269	/// dfa.captures(&mut cache, "", &mut caps);
1270	/// assert_eq!(None, caps.get_match());
1271	/// dfa.captures(&mut cache, "foo", &mut caps);
1272	/// assert_eq!(None, caps.get_match());
1273	/// # Ok::<(), Box<dyn std::error::Error>>(())
1274	/// ```
1275	pub fn never_match() -> Result<DFA, BuildError> {
1276	let nfa = thompson::NFA::never_match();
1277	Builder::new().build_from_nfa(nfa)
1278	}
1279
1280	/// Return a default configuration for a DFA.
1281	///
1282	/// This is a convenience routine to avoid needing to import the `Config`
1283	/// type when customizing the construction of a DFA.
1284	///
1285	/// # Example
1286	///
1287	/// This example shows how to change the match semantics of this DFA from
1288	/// its default "leftmost first" to "all." When using "all," non-greediness
1289	/// doesn't apply and neither does preference order matching. Instead, the
1290	/// longest match possible is always returned. (Although, by construction,
1291	/// it's impossible for a one-pass DFA to have a different answer for
1292	/// "preference order" vs "longest match.")
1293	///
1294	/// ```
1295	/// use regex_automata::{dfa::onepass::DFA, Match, MatchKind};
1296	///
1297	/// let re = DFA::builder()
1298	/// .configure(DFA::config().match_kind(MatchKind::All))
1299	/// .build(r"(abc)+?")?;
1300	/// let mut cache = re.create_cache();
1301	/// let mut caps = re.create_captures();
1302	///
1303	/// re.captures(&mut cache, "abcabc", &mut caps);
1304	/// // Normally, the non-greedy repetition would give us a 0..3 match.
1305	/// assert_eq!(Some(Match::must(`0`, `0`..`6`)), caps.get_match());
1306	/// # Ok::<(), Box<dyn std::error::Error>>(())
1307	/// ```
1308	#[inline]
1309	pub fn config() -> Config {
1310	Config::new()
1311	}
1312
1313	/// Return a builder for configuring the construction of a DFA.
1314	///
1315	/// This is a convenience routine to avoid needing to import the
1316	/// [`Builder`] type in common cases.
1317	///
1318	/// # Example
1319	///
1320	/// This example shows how to use the builder to disable UTF-8 mode.
1321	///
1322	/// ```
1323	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
1324	/// use regex_automata::{
1325	/// dfa::onepass::DFA,
1326	/// nfa::thompson,
1327	/// util::syntax,
1328	/// Match,
1329	/// };
1330	///
1331	/// let re = DFA::builder()
1332	/// .syntax(syntax::Config::new().utf8(`false`))
1333	/// .thompson(thompson::Config::new().utf8(`false`))
1334	/// .build(r"foo(?-u:[^b])ar.*")?;
1335	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
1336	///
1337	/// let haystack = b"foo`\xFF`arzz`\xE2\x98\xFF\n`";
1338	/// let expected = Some(Match::must(`0`, `0`..`8`));
1339	/// re.captures(&mut cache, haystack, &mut caps);
1340	/// assert_eq!(expected, caps.get_match());
1341	///
1342	/// # Ok::<(), Box<dyn std::error::Error>>(())
1343	/// ```
1344	#[inline]
1345	pub fn builder() -> Builder {
1346	Builder::new()
1347	}
1348
1349	/// Create a new empty set of capturing groups that is guaranteed to be
1350	/// valid for the search APIs on this DFA.
1351	///
1352	/// A `Captures` value created for a specific DFA cannot be used with any
1353	/// other DFA.
1354	///
1355	/// This is a convenience function for [`Captures::all`]. See the
1356	/// [`Captures`] documentation for an explanation of its alternative
1357	/// constructors that permit the DFA to do less work during a search, and
1358	/// thus might make it faster.
1359	#[inline]
1360	pub fn create_captures(&self) -> Captures {
1361	Captures::all(self.nfa.group_info().clone())
1362	}
1363
1364	/// Create a new cache for this DFA.
1365	///
1366	/// The cache returned should only be used for searches for this
1367	/// DFA. If you want to reuse the cache for another DFA, then you
1368	/// must call [`Cache::reset`] with that DFA (or, equivalently,
1369	/// [`DFA::reset_cache`]).
1370	#[inline]
1371	pub fn create_cache(&self) -> Cache {
1372	Cache::new(self)
1373	}
1374
1375	/// Reset the given cache such that it can be used for searching with the
1376	/// this DFA (and only this DFA).
1377	///
1378	/// A cache reset permits reusing memory already allocated in this cache
1379	/// with a different DFA.
1380	///
1381	/// # Example
1382	///
1383	/// This shows how to re-purpose a cache for use with a different DFA.
1384	///
1385	/// ```
1386	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
1387	/// use regex_automata::{dfa::onepass::DFA, Match};
1388	///
1389	/// let re1 = DFA::new(r"\w")?;
1390	/// let re2 = DFA::new(r"\W")?;
1391	/// let mut caps1 = re1.create_captures();
1392	/// let mut caps2 = re2.create_captures();
1393	///
1394	/// let mut cache = re1.create_cache();
1395	/// assert_eq!(
1396	/// Some(Match::must(`0`, `0`..`2`)),
1397	/// { re1.captures(&mut cache, "Δ", &mut caps1); caps1.get_match() },
1398	/// );
1399	///
1400	/// // Using 'cache' with re2 is not allowed. It may result in panics or
1401	/// // incorrect results. In order to re-purpose the cache, we must reset
1402	/// // it with the one-pass DFA we'd like to use it with.
1403	/// //
1404	/// // Similarly, after this reset, using the cache with 're1' is also not
1405	/// // allowed.
1406	/// re2.reset_cache(&mut cache);
1407	/// assert_eq!(
1408	/// Some(Match::must(`0`, `0`..`3`)),
1409	/// { re2.captures(&mut cache, "☃", &mut caps2); caps2.get_match() },
1410	/// );
1411	///
1412	/// # Ok::<(), Box<dyn std::error::Error>>(())
1413	/// ```
1414	#[inline]
1415	pub fn reset_cache(&self, cache: &mut Cache) {
1416	cache.reset(self);
1417	}
1418
1419	/// Return the config for this one-pass DFA.
1420	#[inline]
1421	pub fn get_config(&self) -> &Config {
1422	&self.config
1423	}
1424
1425	/// Returns a reference to the underlying NFA.
1426	#[inline]
1427	pub fn get_nfa(&self) -> &NFA {
1428	&self.nfa
1429	}
1430
1431	/// Returns the total number of patterns compiled into this DFA.
1432	///
1433	/// In the case of a DFA that contains no patterns, this returns `0`.
1434	#[inline]
1435	pub fn pattern_len(&self) -> usize {
1436	self.get_nfa().pattern_len()
1437	}
1438
1439	/// Returns the total number of states in this one-pass DFA.
1440	///
1441	/// Note that unlike dense or sparse DFAs, a one-pass DFA does not expose
1442	/// a low level DFA API. Therefore, this routine has little use other than
1443	/// being informational.
1444	#[inline]
1445	pub fn state_len(&self) -> usize {
1446	self.table.len() >> self.stride2()
1447	}
1448
1449	/// Returns the total number of elements in the alphabet for this DFA.
1450	///
1451	/// That is, this returns the total number of transitions that each
1452	/// state in this DFA must have. The maximum alphabet size is 256, which
1453	/// corresponds to each possible byte value.
1454	///
1455	/// The alphabet size may be less than 256 though, and unless
1456	/// [`Config::byte_classes`] is disabled, it is typically must less than
1457	/// 256. Namely, bytes are grouped into equivalence classes such that no
1458	/// two bytes in the same class can distinguish a match from a non-match.
1459	/// For example, in the regex `^[a-z]+$`, the ASCII bytes `a-z` could
1460	/// all be in the same equivalence class. This leads to a massive space
1461	/// savings.
1462	///
1463	/// Note though that the alphabet length does _not_ necessarily equal the
1464	/// total stride space taken up by a single DFA state in the transition
1465	/// table. Namely, for performance reasons, the stride is always the
1466	/// smallest power of two that is greater than or equal to the alphabet
1467	/// length. For this reason, [`DFA::stride`] or [`DFA::stride2`] are
1468	/// often more useful. The alphabet length is typically useful only for
1469	/// informational purposes.
1470	///
1471	/// Note also that unlike dense or sparse DFAs, a one-pass DFA does
1472	/// not have a special end-of-input (EOI) transition. This is because
1473	/// a one-pass DFA handles look-around assertions explicitly (like the
1474	/// [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM)) and does not build
1475	/// them into the transitions of the DFA.
1476	#[inline]
1477	pub fn alphabet_len(&self) -> usize {
1478	self.alphabet_len
1479	}
1480
1481	/// Returns the total stride for every state in this DFA, expressed as the
1482	/// exponent of a power of 2. The stride is the amount of space each state
1483	/// takes up in the transition table, expressed as a number of transitions.
1484	/// (Unused transitions map to dead states.)
1485	///
1486	/// The stride of a DFA is always equivalent to the smallest power of
1487	/// 2 that is greater than or equal to the DFA's alphabet length. This
1488	/// definition uses extra space, but possibly permits faster translation
1489	/// between state identifiers and their corresponding offsets in this DFA's
1490	/// transition table.
1491	///
1492	/// For example, if the DFA's stride is 16 transitions, then its `stride2`
1493	/// is `4` since `2^4 = 16`.
1494	///
1495	/// The minimum `stride2` value is `1` (corresponding to a stride of `2`)
1496	/// while the maximum `stride2` value is `9` (corresponding to a stride
1497	/// of `512`). The maximum in theory should be `8`, but because of some
1498	/// implementation quirks that may be relaxed in the future, it is one more
1499	/// than `8`. (Do note that a maximal stride is incredibly rare, as it
1500	/// would imply that there is almost no redundant in the regex pattern.)
1501	///
1502	/// Note that unlike dense or sparse DFAs, a one-pass DFA does not expose
1503	/// a low level DFA API. Therefore, this routine has little use other than
1504	/// being informational.
1505	#[inline]
1506	pub fn stride2(&self) -> usize {
1507	self.stride2
1508	}
1509
1510	/// Returns the total stride for every state in this DFA. This corresponds
1511	/// to the total number of transitions used by each state in this DFA's
1512	/// transition table.
1513	///
1514	/// Please see [`DFA::stride2`] for more information. In particular, this
1515	/// returns the stride as the number of transitions, where as `stride2`
1516	/// returns it as the exponent of a power of 2.
1517	///
1518	/// Note that unlike dense or sparse DFAs, a one-pass DFA does not expose
1519	/// a low level DFA API. Therefore, this routine has little use other than
1520	/// being informational.
1521	#[inline]
1522	pub fn stride(&self) -> usize {
1523	`1` << self.stride2()
1524	}
1525
1526	/// Returns the memory usage, in bytes, of this DFA.
1527	///
1528	/// The memory usage is computed based on the number of bytes used to
1529	/// represent this DFA.
1530	///
1531	/// This does not* include the stack size used up by this DFA. To*
1532	/// compute that, use `std::mem::size_of::<onepass::DFA>()`.
1533	#[inline]
1534	pub fn memory_usage(&self) -> usize {
1535	use core::mem::size_of;
1536
1537	self.table.len() * size_of::<Transition>()
1538	+ self.starts.len() * size_of::<StateID>()
1539	}
1540	}
1541
1542	impl DFA {
1543	/// Executes an anchored leftmost forward search, and returns true if and
1544	/// only if this one-pass DFA matches the given haystack.
1545	///
1546	/// This routine may short circuit if it knows that scanning future
1547	/// input will never lead to a different result. In particular, if the
1548	/// underlying DFA enters a match state, then this routine will return
1549	/// `true` immediately without inspecting any future input. (Consider how
1550	/// this might make a difference given the regex `a+` on the haystack
1551	/// `aaaaaaaaaaaaaaa`. This routine can stop after it sees the first `a`,
1552	/// but routines like `find` need to continue searching because `+` is
1553	/// greedy by default.)
1554	///
1555	/// The given `Input` is forcefully set to use [`Anchored::Yes`] if the
1556	/// given configuration was [`Anchored::No`] (which is the default).
1557	///
1558	/// # Panics
1559	///
1560	/// This routine panics if the search could not complete. This can occur
1561	/// in the following circumstances:
1562	///
1563	/// When the provided `Input` configuration is not supported. For*
1564	/// example, by providing an unsupported anchor mode. Concretely,
1565	/// this occurs when using [`Anchored::Pattern`] without enabling
1566	/// [`Config::starts_for_each_pattern`].
1567	///
1568	/// When a search panics, callers cannot know whether a match exists or
1569	/// not.
1570	///
1571	/// Use [`DFA::try_search`] if you want to handle these panics as error
1572	/// values instead.
1573	///
1574	/// # Example
1575	///
1576	/// This shows basic usage:
1577	///
1578	/// ```
1579	/// use regex_automata::dfa::onepass::DFA;
1580	///
1581	/// let re = DFA::new("foo[0-9]+bar")?;
1582	/// let mut cache = re.create_cache();
1583	///
1584	/// assert!(re.is_match(&mut cache, "foo12345bar"));
1585	/// assert!(!re.is_match(&mut cache, "foobar"));
1586	/// # Ok::<(), Box<dyn std::error::Error>>(())
1587	/// ```
1588	///
1589	/// # Example: consistency with search APIs
1590	///
1591	/// `is_match` is guaranteed to return `true` whenever `captures` returns
1592	/// a match. This includes searches that are executed entirely within a
1593	/// codepoint:
1594	///
1595	/// ```
1596	/// use regex_automata::{dfa::onepass::DFA, Input};
1597	///
1598	/// let re = DFA::new("a*")?;
1599	/// let mut cache = re.create_cache();
1600	///
1601	/// assert!(!re.is_match(&mut cache, Input::new("☃").span(`1`..`2`)));
1602	/// # Ok::<(), Box<dyn std::error::Error>>(())
1603	/// ```
1604	///
1605	/// Notice that when UTF-8 mode is disabled, then the above reports a
1606	/// match because the restriction against zero-width matches that split a
1607	/// codepoint has been lifted:
1608	///
1609	/// ```
1610	/// use regex_automata::{dfa::onepass::DFA, nfa::thompson::NFA, Input};
1611	///
1612	/// let re = DFA::builder()
1613	/// .thompson(NFA::config().utf8(`false`))
1614	/// .build("a*")?;
1615	/// let mut cache = re.create_cache();
1616	///
1617	/// assert!(re.is_match(&mut cache, Input::new("☃").span(`1`..`2`)));
1618	/// # Ok::<(), Box<dyn std::error::Error>>(())
1619	/// ```
1620	#[inline]
1621	pub fn is_match<'h, I: Into<Input<'h>>>(
1622	&self,
1623	cache: &mut Cache,
1624	input: I,
1625	) -> bool {
1626	let mut input = input.into().earliest(`true`);
1627	if matches!(input.get_anchored(), Anchored::No) {
1628	input.set_anchored(Anchored::Yes);
1629	}
1630	self.try_search_slots(cache, &input, &mut []).unwrap().is_some()
1631	}
1632
1633	/// Executes an anchored leftmost forward search, and returns a `Match` if
1634	/// and only if this one-pass DFA matches the given haystack.
1635	///
1636	/// This routine only includes the overall match span. To get access to the
1637	/// individual spans of each capturing group, use [`DFA::captures`].
1638	///
1639	/// The given `Input` is forcefully set to use [`Anchored::Yes`] if the
1640	/// given configuration was [`Anchored::No`] (which is the default).
1641	///
1642	/// # Panics
1643	///
1644	/// This routine panics if the search could not complete. This can occur
1645	/// in the following circumstances:
1646	///
1647	/// When the provided `Input` configuration is not supported. For*
1648	/// example, by providing an unsupported anchor mode. Concretely,
1649	/// this occurs when using [`Anchored::Pattern`] without enabling
1650	/// [`Config::starts_for_each_pattern`].
1651	///
1652	/// When a search panics, callers cannot know whether a match exists or
1653	/// not.
1654	///
1655	/// Use [`DFA::try_search`] if you want to handle these panics as error
1656	/// values instead.
1657	///
1658	/// # Example
1659	///
1660	/// Leftmost first match semantics corresponds to the match with the
1661	/// smallest starting offset, but where the end offset is determined by
1662	/// preferring earlier branches in the original regular expression. For
1663	/// example, `Sam\|Samwise` will match `Sam` in `Samwise`, but `Samwise\|Sam`
1664	/// will match `Samwise` in `Samwise`.
1665	///
1666	/// Generally speaking, the "leftmost first" match is how most backtracking
1667	/// regular expressions tend to work. This is in contrast to POSIX-style
1668	/// regular expressions that yield "leftmost longest" matches. Namely,
1669	/// both `Sam\|Samwise` and `Samwise\|Sam` match `Samwise` when using
1670	/// leftmost longest semantics. (This crate does not currently support
1671	/// leftmost longest semantics.)
1672	///
1673	/// ```
1674	/// use regex_automata::{dfa::onepass::DFA, Match};
1675	///
1676	/// let re = DFA::new("foo[0-9]+")?;
1677	/// let mut cache = re.create_cache();
1678	/// let expected = Match::must(`0`, `0`..`8`);
1679	/// assert_eq!(Some(expected), re.find(&mut cache, "foo12345"));
1680	///
1681	/// // Even though a match is found after reading the first byte (`a`),
1682	/// // the leftmost first match semantics demand that we find the earliest
1683	/// // match that prefers earlier parts of the pattern over later parts.
1684	/// let re = DFA::new("abc\|a")?;
1685	/// let mut cache = re.create_cache();
1686	/// let expected = Match::must(`0`, `0`..`3`);
1687	/// assert_eq!(Some(expected), re.find(&mut cache, "abc"));
1688	///
1689	/// # Ok::<(), Box<dyn std::error::Error>>(())
1690	/// ```
1691	#[inline]
1692	pub fn find<'h, I: Into<Input<'h>>>(
1693	&self,
1694	cache: &mut Cache,
1695	input: I,
1696	) -> Option<Match> {
1697	let mut input = input.into();
1698	if matches!(input.get_anchored(), Anchored::No) {
1699	input.set_anchored(Anchored::Yes);
1700	}
1701	if self.get_nfa().pattern_len() == `1` {
1702	let mut slots = [None, None];
1703	let pid =
1704	self.try_search_slots(cache, &input, &mut slots).unwrap()?;
1705	let start = slots[`0`].unwrap().get();
1706	let end = slots[`1`].unwrap().get();
1707	return Some(Match::new(pid, Span { start, end }));
1708	}
1709	let ginfo = self.get_nfa().group_info();
1710	let slots_len = ginfo.implicit_slot_len();
1711	let mut slots = vec![None; slots_len];
1712	let pid = self.try_search_slots(cache, &input, &mut slots).unwrap()?;
1713	let start = slots[pid.as_usize() * `2`].unwrap().get();
1714	let end = slots[pid.as_usize() * `2` + `1`].unwrap().get();
1715	Some(Match::new(pid, Span { start, end }))
1716	}
1717
1718	/// Executes an anchored leftmost forward search and writes the spans
1719	/// of capturing groups that participated in a match into the provided
1720	/// [`Captures`] value. If no match was found, then [`Captures::is_match`]
1721	/// is guaranteed to return `false`.
1722	///
1723	/// The given `Input` is forcefully set to use [`Anchored::Yes`] if the
1724	/// given configuration was [`Anchored::No`] (which is the default).
1725	///
1726	/// # Panics
1727	///
1728	/// This routine panics if the search could not complete. This can occur
1729	/// in the following circumstances:
1730	///
1731	/// When the provided `Input` configuration is not supported. For*
1732	/// example, by providing an unsupported anchor mode. Concretely,
1733	/// this occurs when using [`Anchored::Pattern`] without enabling
1734	/// [`Config::starts_for_each_pattern`].
1735	///
1736	/// When a search panics, callers cannot know whether a match exists or
1737	/// not.
1738	///
1739	/// Use [`DFA::try_search`] if you want to handle these panics as error
1740	/// values instead.
1741	///
1742	/// # Example
1743	///
1744	/// This shows a simple example of a one-pass regex that extracts
1745	/// capturing group spans.
1746	///
1747	/// ```
1748	/// use regex_automata::{dfa::onepass::DFA, Match, Span};
1749	///
1750	/// let re = DFA::new(
1751	/// // Notice that we use ASCII here. The corresponding Unicode regex
1752	/// // is sadly not one-pass.
1753	/// "(?P<first>[[:alpha:]]+)[[:space:]]+(?P<last>[[:alpha:]]+)",
1754	/// )?;
1755	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
1756	///
1757	/// re.captures(&mut cache, "Bruce Springsteen", &mut caps);
1758	/// assert_eq!(Some(Match::must(`0`, `0`..`17`)), caps.get_match());
1759	/// assert_eq!(Some(Span::from(`0`..`5`)), caps.get_group(`1`));
1760	/// assert_eq!(Some(Span::from(`6`..`17`)), caps.get_group_by_name("last"));
1761	///
1762	/// # Ok::<(), Box<dyn std::error::Error>>(())
1763	/// ```
1764	#[inline]
1765	pub fn captures<'h, I: Into<Input<'h>>>(
1766	&self,
1767	cache: &mut Cache,
1768	input: I,
1769	caps: &mut Captures,
1770	) {
1771	let mut input = input.into();
1772	if matches!(input.get_anchored(), Anchored::No) {
1773	input.set_anchored(Anchored::Yes);
1774	}
1775	self.try_search(cache, &input, caps).unwrap();
1776	}
1777
1778	/// Executes an anchored leftmost forward search and writes the spans
1779	/// of capturing groups that participated in a match into the provided
1780	/// [`Captures`] value. If no match was found, then [`Captures::is_match`]
1781	/// is guaranteed to return `false`.
1782	///
1783	/// The differences with [`DFA::captures`] are:
1784	///
1785	/// 1. This returns an error instead of panicking if the search fails.
1786	/// 2. Accepts an `&Input` instead of a `Into<Input>`. This permits reusing
1787	/// the same input for multiple searches, which _may_ be important for
1788	/// latency.
1789	/// 3. This does not automatically change the [`Anchored`] mode from `No`
1790	/// to `Yes`. Instead, if [`Input::anchored`] is `Anchored::No`, then an
1791	/// error is returned.
1792	///
1793	/// # Errors
1794	///
1795	/// This routine errors if the search could not complete. This can occur
1796	/// in the following circumstances:
1797	///
1798	/// When the provided `Input` configuration is not supported. For*
1799	/// example, by providing an unsupported anchor mode. Concretely,
1800	/// this occurs when using [`Anchored::Pattern`] without enabling
1801	/// [`Config::starts_for_each_pattern`].
1802	///
1803	/// When a search returns an error, callers cannot know whether a match
1804	/// exists or not.
1805	///
1806	/// # Example: specific pattern search
1807	///
1808	/// This example shows how to build a multi-regex that permits searching
1809	/// for specific patterns. Note that this is somewhat less useful than
1810	/// in other regex engines, since a one-pass DFA by definition has no
1811	/// ambiguity about which pattern can match at a position. That is, if it
1812	/// were possible for two different patterns to match at the same starting
1813	/// position, then the multi-regex would not be one-pass and construction
1814	/// would have failed.
1815	///
1816	/// Nevertheless, this can still be useful if you only care about matches
1817	/// for a specific pattern, and want the DFA to report "no match" even if
1818	/// some other pattern would have matched.
1819	///
1820	/// Note that in order to make use of this functionality,
1821	/// [`Config::starts_for_each_pattern`] must be enabled. It is disabled
1822	/// by default since it may result in higher memory usage.
1823	///
1824	/// ```
1825	/// use regex_automata::{
1826	/// dfa::onepass::DFA, Anchored, Input, Match, PatternID,
1827	/// };
1828	///
1829	/// let re = DFA::builder()
1830	/// .configure(DFA::config().starts_for_each_pattern(`true`))
1831	/// .build_many(&["[a-z]+", "[0-9]+"])?;
1832	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
1833	/// let haystack = "123abc";
1834	/// let input = Input::new(haystack).anchored(Anchored::Yes);
1835	///
1836	/// // A normal multi-pattern search will show pattern 1 matches.
1837	/// re.try_search(&mut cache, &input, &mut caps)?;
1838	/// assert_eq!(Some(Match::must(`1`, `0`..`3`)), caps.get_match());
1839	///
1840	/// // If we only want to report pattern 0 matches, then we'll get no
1841	/// // match here.
1842	/// let input = input.anchored(Anchored::Pattern(PatternID::must(`0`)));
1843	/// re.try_search(&mut cache, &input, &mut caps)?;
1844	/// assert_eq!(None, caps.get_match());
1845	///
1846	/// # Ok::<(), Box<dyn std::error::Error>>(())
1847	/// ```
1848	///
1849	/// # Example: specifying the bounds of a search
1850	///
1851	/// This example shows how providing the bounds of a search can produce
1852	/// different results than simply sub-slicing the haystack.
1853	///
1854	/// ```
1855	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
1856	/// use regex_automata::{dfa::onepass::DFA, Anchored, Input, Match};
1857	///
1858	/// // one-pass DFAs fully support Unicode word boundaries!
1859	/// // A sad joke is that a Unicode aware regex like \w+\s is not one-pass.
1860	/// // :-(
1861	/// let re = DFA::new(r"\b[0-9]{3}\b")?;
1862	/// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
1863	/// let haystack = "foo123bar";
1864	///
1865	/// // Since we sub-slice the haystack, the search doesn't know about
1866	/// // the larger context and assumes that `123` is surrounded by word
1867	/// // boundaries. And of course, the match position is reported relative
1868	/// // to the sub-slice as well, which means we get `0..3` instead of
1869	/// // `3..6`.
1870	/// let expected = Some(Match::must(`0`, `0`..`3`));
1871	/// let input = Input::new(&haystack[`3`..`6`]).anchored(Anchored::Yes);
1872	/// re.try_search(&mut cache, &input, &mut caps)?;
1873	/// assert_eq!(expected, caps.get_match());
1874	///
1875	/// // But if we provide the bounds of the search within the context of the
1876	/// // entire haystack, then the search can take the surrounding context
1877	/// // into account. (And if we did find a match, it would be reported
1878	/// // as a valid offset into `haystack` instead of its sub-slice.)
1879	/// let expected = None;
1880	/// let input = Input::new(haystack).range(`3`..`6`).anchored(Anchored::Yes);
1881	/// re.try_search(&mut cache, &input, &mut caps)?;
1882	/// assert_eq!(expected, caps.get_match());
1883	///
1884	/// # Ok::<(), Box<dyn std::error::Error>>(())
1885	/// ```
1886	#[inline]
1887	pub fn try_search(
1888	&self,
1889	cache: &mut Cache,
1890	input: &Input<'_>,
1891	caps: &mut Captures,
1892	) -> Result<(), MatchError> {
1893	let pid = self.try_search_slots(cache, input, caps.slots_mut())?;
1894	caps.set_pattern(pid);
1895	Ok(())
1896	}
1897
1898	/// Executes an anchored leftmost forward search and writes the spans
1899	/// of capturing groups that participated in a match into the provided
1900	/// `slots`, and returns the matching pattern ID. The contents of the
1901	/// slots for patterns other than the matching pattern are unspecified. If
1902	/// no match was found, then `None` is returned and the contents of all
1903	/// `slots` is unspecified.
1904	///
1905	/// This is like [`DFA::try_search`], but it accepts a raw slots slice
1906	/// instead of a `Captures` value. This is useful in contexts where you
1907	/// don't want or need to allocate a `Captures`.
1908	///
1909	/// It is legal to pass _any_ number of slots to this routine. If the regex
1910	/// engine would otherwise write a slot offset that doesn't fit in the
1911	/// provided slice, then it is simply skipped. In general though, there are
1912	/// usually three slice lengths you might want to use:
1913	///
1914	/// An empty slice, if you only care about which pattern matched.*
1915	/// A slice with*
1916	/// [`pattern_len() 2`](crate::dfa::onepass::DFA::pattern_len)*
1917	/// slots, if you only care about the overall match spans for each matching
1918	/// pattern.
1919	/// A slice with*
1920	/// [`slot_len()`](crate::util::captures::GroupInfo::slot_len) slots, which
1921	/// permits recording match offsets for every capturing group in every
1922	/// pattern.
1923	///
1924	/// # Errors
1925	///
1926	/// This routine errors if the search could not complete. This can occur
1927	/// in the following circumstances:
1928	///
1929	/// When the provided `Input` configuration is not supported. For*
1930	/// example, by providing an unsupported anchor mode. Concretely,
1931	/// this occurs when using [`Anchored::Pattern`] without enabling
1932	/// [`Config::starts_for_each_pattern`].
1933	///
1934	/// When a search returns an error, callers cannot know whether a match
1935	/// exists or not.
1936	///
1937	/// # Example
1938	///
1939	/// This example shows how to find the overall match offsets in a
1940	/// multi-pattern search without allocating a `Captures` value. Indeed, we
1941	/// can put our slots right on the stack.
1942	///
1943	/// ```
1944	/// use regex_automata::{dfa::onepass::DFA, Anchored, Input, PatternID};
1945	///
1946	/// let re = DFA::new_many(&[
1947	/// r"[a-zA-Z]+",
1948	/// r"[0-9]+",
1949	/// ])?;
1950	/// let mut cache = re.create_cache();
1951	/// let input = Input::new("123").anchored(Anchored::Yes);
1952	///
1953	/// // We only care about the overall match offsets here, so we just
1954	/// // allocate two slots for each pattern. Each slot records the start
1955	/// // and end of the match.
1956	/// let mut slots = [None; `4`];
1957	/// let pid = re.try_search_slots(&mut cache, &input, &mut slots)?;
1958	/// assert_eq!(Some(PatternID::must(`1`)), pid);
1959	///
1960	/// // The overall match offsets are always at 'pid 2' and 'pid * 2 + 1'.*
1961	/// // See 'GroupInfo' for more details on the mapping between groups and
1962	/// // slot indices.
1963	/// let slot_start = pid.unwrap().as_usize() * `2`;
1964	/// let slot_end = slot_start + `1`;
1965	/// assert_eq!(Some(`0`), slots[slot_start].map(\|s\| s.get()));
1966	/// assert_eq!(Some(`3`), slots[slot_end].map(\|s\| s.get()));
1967	///
1968	/// # Ok::<(), Box<dyn std::error::Error>>(())
1969	/// ```
1970	#[inline]
1971	pub fn try_search_slots(
1972	&self,
1973	cache: &mut Cache,
1974	input: &Input<'_>,
1975	slots: &mut [Option<NonMaxUsize>],
1976	) -> Result<Option<PatternID>, MatchError> {
1977	let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
1978	if !utf8empty {
1979	return self.try_search_slots_imp(cache, input, slots);
1980	}
1981	// See PikeVM::try_search_slots for why we do this.
1982	let min = self.get_nfa().group_info().implicit_slot_len();
1983	if slots.len() >= min {
1984	return self.try_search_slots_imp(cache, input, slots);
1985	}
1986	if self.get_nfa().pattern_len() == `1` {
1987	let mut enough = [None, None];
1988	let got = self.try_search_slots_imp(cache, input, &mut enough)?;
1989	// This is OK because we know `enough_slots` is strictly bigger
1990	// than `slots`, otherwise this special case isn't reached.
1991	slots.copy_from_slice(&enough[..slots.len()]);
1992	return Ok(got);
1993	}
1994	let mut enough = vec![None; min];
1995	let got = self.try_search_slots_imp(cache, input, &mut enough)?;
1996	// This is OK because we know `enough_slots` is strictly bigger than
1997	// `slots`, otherwise this special case isn't reached.
1998	slots.copy_from_slice(&enough[..slots.len()]);
1999	Ok(got)
2000	}
2001
2002	#[inline(never)]
2003	fn try_search_slots_imp(
2004	&self,
2005	cache: &mut Cache,
2006	input: &Input<'_>,
2007	slots: &mut [Option<NonMaxUsize>],
2008	) -> Result<Option<PatternID>, MatchError> {
2009	let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
2010	match self.search_imp(cache, input, slots)? {
2011	None => return Ok(None),
2012	Some(pid) if !utf8empty => return Ok(Some(pid)),
2013	Some(pid) => {
2014	// These slot indices are always correct because we know our
2015	// 'pid' is valid and thus we know that the slot indices for it
2016	// are valid.
2017	let slot_start = pid.as_usize().wrapping_mul(`2`);
2018	let slot_end = slot_start.wrapping_add(`1`);
2019	// OK because we know we have a match and we know our caller
2020	// provided slots are big enough (which we make true above if
2021	// the caller didn't). Namely, we're only here when 'utf8empty'
2022	// is true, and when that's true, we require slots for every
2023	// pattern.
2024	let start = slots[slot_start].unwrap().get();
2025	let end = slots[slot_end].unwrap().get();
2026	// If our match splits a codepoint, then we cannot report is
2027	// as a match. And since one-pass DFAs only support anchored
2028	// searches, we don't try to skip ahead to find the next match.
2029	// We can just quit with nothing.
2030	if start == end && !input.is_char_boundary(start) {
2031	return Ok(None);
2032	}
2033	Ok(Some(pid))
2034	}
2035	}
2036	}
2037	}
2038
2039	impl DFA {
2040	fn search_imp(
2041	&self,
2042	cache: &mut Cache,
2043	input: &Input<'_>,
2044	slots: &mut [Option<NonMaxUsize>],
2045	) -> Result<Option<PatternID>, MatchError> {
2046	// PERF: Some ideas. I ran out of steam after my initial impl to try
2047	// many of these.
2048	//
2049	// 1) Try doing more state shuffling. Right now, all we do is push
2050	// match states to the end of the transition table so that we can do
2051	// 'if sid >= self.min_match_id' to know whether we're in a match
2052	// state or not. But what about doing something like dense DFAs and
2053	// pushing dead, match and states with captures/looks all toward the
2054	// beginning of the transition table. Then we could do 'if sid <=
2055	// self.max_special_id', in which case, we need to do some special
2056	// handling of some sort. Otherwise, we get the happy path, just
2057	// like in a DFA search. The main argument against this is that the
2058	// one-pass DFA is likely to be used most often with capturing groups
2059	// and if capturing groups are common, then this might wind up being a
2060	// pessimization.
2061	//
2062	// 2) Consider moving 'PatternEpsilons' out of the transition table.
2063	// It is only needed for match states and usually a small minority of
2064	// states are match states. Therefore, we're using an extra 'u64' for
2065	// most states.
2066	//
2067	// 3) I played around with the match state handling and it seems like
2068	// there is probably a lot left on the table for improvement. The
2069	// key tension is that the 'find_match' routine is a giant mess, but
2070	// splitting it out into a non-inlineable function is a non-starter
2071	// because the match state might consume input, so 'find_match' COULD
2072	// be called quite a lot, and a function call at that point would trash
2073	// perf. In theory, we could detect whether a match state consumes
2074	// input and then specialize our search routine based on that. In that
2075	// case, maybe an extra function call is OK, but even then, it might be
2076	// too much of a latency hit. Another idea is to just try and figure
2077	// out how to reduce the code size of 'find_match'. RE2 has a trick
2078	// here where the match handling isn't done if we know the next byte of
2079	// input yields a match too. Maybe we adopt that?
2080	//
2081	// This just might be a tricky DFA to optimize.
2082
2083	if input.is_done() {
2084	return Ok(None);
2085	}
2086	// We unfortunately have a bit of book-keeping to do to set things
2087	// up. We do have to setup our cache and clear all of our slots. In
2088	// particular, clearing the slots is necessary for the case where we
2089	// report a match, but one of the capturing groups didn't participate
2090	// in the match but had a span set from a previous search. That would
2091	// be bad. In theory, we could avoid all this slot clearing if we knew
2092	// that every slot was always activated for every match. Then we would
2093	// know they would always be overwritten when a match is found.
2094	let explicit_slots_len = core::cmp::min(
2095	Slots::LIMIT,
2096	slots.len().saturating_sub(self.explicit_slot_start),
2097	);
2098	cache.setup_search(explicit_slots_len);
2099	for slot in cache.explicit_slots() {
2100	*slot = None;
2101	}
2102	for slot in slots.iter_mut() {
2103	*slot = None;
2104	}
2105	// We set the starting slots for every pattern up front. This does
2106	// increase our latency somewhat, but it avoids having to do it every
2107	// time we see a match state (which could be many times in a single
2108	// search if the match state consumes input).
2109	for pid in self.nfa.patterns() {
2110	let i = pid.as_usize() * `2`;
2111	if i >= slots.len() {
2112	break;
2113	}
2114	slots[i] = NonMaxUsize::new(input.start());
2115	}
2116	let mut pid = None;
2117	let mut next_sid = match input.get_anchored() {
2118	Anchored::Yes => self.start(),
2119	Anchored::Pattern(pid) => self.start_pattern(pid)?,
2120	Anchored::No => {
2121	// If the regex is itself always anchored, then we're fine,
2122	// even if the search is configured to be unanchored.
2123	if !self.nfa.is_always_start_anchored() {
2124	return Err(MatchError::unsupported_anchored(
2125	Anchored::No,
2126	));
2127	}
2128	self.start()
2129	}
2130	};
2131	let leftmost_first =
2132	matches!(self.config.get_match_kind(), MatchKind::LeftmostFirst);
2133	for at in input.start()..input.end() {
2134	let sid = next_sid;
2135	let trans = self.transition(sid, input.haystack()[at]);
2136	next_sid = trans.state_id();
2137	let epsilons = trans.epsilons();
2138	if sid >= self.min_match_id {
2139	if self.find_match(cache, input, at, sid, slots, &mut pid) {
2140	if input.get_earliest()
2141	\|\| (leftmost_first && trans.match_wins())
2142	{
2143	return Ok(pid);
2144	}
2145	}
2146	}
2147	if sid == DEAD
2148	\|\| (!epsilons.looks().is_empty()
2149	&& !self.nfa.look_matcher().matches_set_inline(
2150	epsilons.looks(),
2151	input.haystack(),
2152	at,
2153	))
2154	{
2155	return Ok(pid);
2156	}
2157	epsilons.slots().apply(at, cache.explicit_slots());
2158	}
2159	if next_sid >= self.min_match_id {
2160	self.find_match(
2161	cache,
2162	input,
2163	input.end(),
2164	next_sid,
2165	slots,
2166	&mut pid,
2167	);
2168	}
2169	Ok(pid)
2170	}
2171
2172	/// Assumes 'sid' is a match state and looks for whether a match can
2173	/// be reported. If so, appropriate offsets are written to 'slots' and
2174	/// 'matched_pid' is set to the matching pattern ID.
2175	///
2176	/// Even when 'sid' is a match state, it's possible that a match won't
2177	/// be reported. For example, when the conditional epsilon transitions
2178	/// leading to the match state aren't satisfied at the given position in
2179	/// the haystack.
2180	#[cfg_attr(feature = "perf-inline", inline(always))]
2181	fn find_match(
2182	&self,
2183	cache: &mut Cache,
2184	input: &Input<'_>,
2185	at: usize,
2186	sid: StateID,
2187	slots: &mut [Option<NonMaxUsize>],
2188	matched_pid: &mut Option<PatternID>,
2189	) -> bool {
2190	debug_assert!(sid >= self.min_match_id);
2191	let pateps = self.pattern_epsilons(sid);
2192	let epsilons = pateps.epsilons();
2193	if !epsilons.looks().is_empty()
2194	&& !self.nfa.look_matcher().matches_set_inline(
2195	epsilons.looks(),
2196	input.haystack(),
2197	at,
2198	)
2199	{
2200	return `false`;
2201	}
2202	let pid = pateps.pattern_id_unchecked();
2203	// This calculation is always correct because we know our 'pid' is
2204	// valid and thus we know that the slot indices for it are valid.
2205	let slot_end = pid.as_usize().wrapping_mul(`2`).wrapping_add(`1`);
2206	// Set the implicit 'end' slot for the matching pattern. (The 'start'
2207	// slot was set at the beginning of the search.)
2208	if slot_end < slots.len() {
2209	slots[slot_end] = NonMaxUsize::new(at);
2210	}
2211	// If the caller provided enough room, copy the previously recorded
2212	// explicit slots from our scratch space to the caller provided slots.
2213	// We also* need to set any explicit slots that are active as part of*
2214	// the path to the match state.
2215	if self.explicit_slot_start < slots.len() {
2216	// NOTE: The 'cache.explicit_slots()' slice is setup at the
2217	// beginning of every search such that it is guaranteed to return a
2218	// slice of length equivalent to 'slots[explicit_slot_start..]'.
2219	slots[self.explicit_slot_start..]
2220	.copy_from_slice(cache.explicit_slots());
2221	epsilons.slots().apply(at, &mut slots[self.explicit_slot_start..]);
2222	}
2223	*matched_pid = Some(pid);
2224	`true`
2225	}
2226	}
2227
2228	impl DFA {
2229	/// Returns the anchored start state for matching any pattern in this DFA.
2230	fn start(&self) -> StateID {
2231	self.starts[`0`]
2232	}
2233
2234	/// Returns the anchored start state for matching the given pattern. If
2235	/// 'starts_for_each_pattern'
2236	/// was not enabled, then this returns an error. If the given pattern is
2237	/// not in this DFA, then `Ok(None)` is returned.
2238	fn start_pattern(&self, pid: PatternID) -> Result<StateID, MatchError> {
2239	if !self.config.get_starts_for_each_pattern() {
2240	return Err(MatchError::unsupported_anchored(Anchored::Pattern(
2241	pid,
2242	)));
2243	}
2244	// 'starts' always has non-zero length. The first entry is always the
2245	// anchored starting state for all patterns, and the following entries
2246	// are optional and correspond to the anchored starting states for
2247	// patterns at pid+1. Thus, starts.len()-1 corresponds to the total
2248	// number of patterns that one can explicitly search for. (And it may
2249	// be zero.)
2250	Ok(self.starts.get(pid.one_more()).copied().unwrap_or(DEAD))
2251	}
2252
2253	/// Returns the transition from the given state ID and byte of input. The
2254	/// transition includes the next state ID, the slots that should be saved
2255	/// and any conditional epsilon transitions that must be satisfied in order
2256	/// to take this transition.
2257	fn transition(&self, sid: StateID, byte: u8) -> Transition {
2258	let offset = sid.as_usize() << self.stride2();
2259	let class = self.classes.get(byte).as_usize();
2260	self.table[offset + class]
2261	}
2262
2263	/// Set the transition from the given state ID and byte of input to the
2264	/// transition given.
2265	fn set_transition(&mut self, sid: StateID, byte: u8, to: Transition) {
2266	let offset = sid.as_usize() << self.stride2();
2267	let class = self.classes.get(byte).as_usize();
2268	self.table[offset + class] = to;
2269	}
2270
2271	/// Return an iterator of "sparse" transitions for the given state ID.
2272	/// "sparse" in this context means that consecutive transitions that are
2273	/// equivalent are returned as one group, and transitions to the DEAD state
2274	/// are ignored.
2275	///
2276	/// This winds up being useful for debug printing, since it's much terser
2277	/// to display runs of equivalent transitions than the transition for every
2278	/// possible byte value. Indeed, in practice, it's very common for runs
2279	/// of equivalent transitions to appear.
2280	fn sparse_transitions(&self, sid: StateID) -> SparseTransitionIter<'_> {
2281	let start = sid.as_usize() << self.stride2();
2282	let end = start + self.alphabet_len();
2283	SparseTransitionIter {
2284	it: self.table[start..end].iter().enumerate(),
2285	cur: None,
2286	}
2287	}
2288
2289	/// Return the pattern epsilons for the given state ID.
2290	///
2291	/// If the given state ID does not correspond to a match state ID, then the
2292	/// pattern epsilons returned is empty.
2293	fn pattern_epsilons(&self, sid: StateID) -> PatternEpsilons {
2294	let offset = sid.as_usize() << self.stride2();
2295	PatternEpsilons(self.table[offset + self.pateps_offset].0)
2296	}
2297
2298	/// Set the pattern epsilons for the given state ID.
2299	fn set_pattern_epsilons(&mut self, sid: StateID, pateps: PatternEpsilons) {
2300	let offset = sid.as_usize() << self.stride2();
2301	self.table[offset + self.pateps_offset] = Transition(pateps.0);
2302	}
2303
2304	/// Returns the state ID prior to the one given. This returns None if the
2305	/// given ID is the first DFA state.
2306	fn prev_state_id(&self, id: StateID) -> Option<StateID> {
2307	if id == DEAD {
2308	None
2309	} else {
2310	// CORRECTNESS: Since 'id' is not the first state, subtracting 1
2311	// is always valid.
2312	Some(StateID::new_unchecked(id.as_usize().checked_sub(`1`).unwrap()))
2313	}
2314	}
2315
2316	/// Returns the state ID of the last state in this DFA's transition table.
2317	/// "last" in this context means the last state to appear in memory, i.e.,
2318	/// the one with the greatest ID.
2319	fn last_state_id(&self) -> StateID {
2320	// CORRECTNESS: A DFA table is always non-empty since it always at
2321	// least contains a DEAD state. Since every state has the same stride,
2322	// we can just compute what the "next" state ID would have been and
2323	// then subtract 1 from it.
2324	StateID::new_unchecked(
2325	(self.table.len() >> self.stride2()).checked_sub(`1`).unwrap(),
2326	)
2327	}
2328
2329	/// Move the transitions from 'id1' to 'id2' and vice versa.
2330	///
2331	/// WARNING: This does not update the rest of the transition table to have
2332	/// transitions to 'id1' changed to 'id2' and vice versa. This merely moves
2333	/// the states in memory.
2334	pub(super) fn swap_states(&mut self, id1: StateID, id2: StateID) {
2335	let o1 = id1.as_usize() << self.stride2();
2336	let o2 = id2.as_usize() << self.stride2();
2337	for b in `0`..self.stride() {
2338	self.table.swap(o1 + b, o2 + b);
2339	}
2340	}
2341
2342	/// Map all state IDs in this DFA (transition table + start states)
2343	/// according to the closure given.
2344	pub(super) fn remap(&mut self, map: impl Fn(StateID) -> StateID) {
2345	for i in `0`..self.state_len() {
2346	let offset = i << self.stride2();
2347	for b in `0`..self.alphabet_len() {
2348	let next = self.table[offset + b].state_id();
2349	self.table[offset + b].set_state_id(map(next));
2350	}
2351	}
2352	for i in `0`..self.starts.len() {
2353	self.starts[i] = map(self.starts[i]);
2354	}
2355	}
2356	}
2357
2358	impl core::fmt::Debug for DFA {
2359	fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
2360	fn debug_state_transitions(
2361	f: &mut core::fmt::Formatter,
2362	dfa: &DFA,
2363	sid: StateID,
2364	) -> core::fmt::Result {
2365	for (i, (start, end, trans)) in
2366	dfa.sparse_transitions(sid).enumerate()
2367	{
2368	let next = trans.state_id();
2369	if i > `0` {
2370	write!(f, ", ")?;
2371	}
2372	if start == end {
2373	write!(
2374	f,
2375	"{:?} => {:?}",
2376	DebugByte(start),
2377	next.as_usize(),
2378	)?;
2379	} else {
2380	write!(
2381	f,
2382	"{:?}-{:?} => {:?}",
2383	DebugByte(start),
2384	DebugByte(end),
2385	next.as_usize(),
2386	)?;
2387	}
2388	if trans.match_wins() {
2389	write!(f, " (MW)")?;
2390	}
2391	if !trans.epsilons().is_empty() {
2392	write!(f, " ({:?})", trans.epsilons())?;
2393	}
2394	}
2395	Ok(())
2396	}
2397
2398	writeln!(f, "onepass::DFA(")?;
2399	for index in `0`..self.state_len() {
2400	let sid = StateID::must(index);
2401	let pateps = self.pattern_epsilons(sid);
2402	if sid == DEAD {
2403	write!(f, "D ")?;
2404	} else if pateps.pattern_id().is_some() {
2405	write!(f, "* ")?;
2406	} else {
2407	write!(f, " ")?;
2408	}
2409	write!(f, "{:06?}", sid.as_usize())?;
2410	if !pateps.is_empty() {
2411	write!(f, " ({:?})", pateps)?;
2412	}
2413	write!(f, ": ")?;
2414	debug_state_transitions(f, self, sid)?;
2415	write!(f, "`\n`")?;
2416	}
2417	writeln!(f, "")?;
2418	for (i, &sid) in self.starts.iter().enumerate() {
2419	if i == `0` {
2420	writeln!(f, "START(ALL): {:?}", sid.as_usize())?;
2421	} else {
2422	writeln!(
2423	f,
2424	"START(pattern: {:?}): {:?}",
2425	i - `1`,
2426	sid.as_usize(),
2427	)?;
2428	}
2429	}
2430	writeln!(f, "state length: {:?}", self.state_len())?;
2431	writeln!(f, "pattern length: {:?}", self.pattern_len())?;
2432	writeln!(f, ")")?;
2433	Ok(())
2434	}
2435	}
2436
2437	/// An iterator over groups of consecutive equivalent transitions in a single
2438	/// state.
2439	#[derive(Debug)]
2440	struct SparseTransitionIter<'a> {
2441	it: core::iter::Enumerate<core::slice::Iter<'a, Transition>>,
2442	cur: Option<(u8, u8, Transition)>,
2443	}
2444
2445	impl<'a> Iterator for SparseTransitionIter<'a> {
2446	type Item = (u8, u8, Transition);
2447
2448	fn next(&mut self) -> Option<(u8, u8, Transition)> {
2449	while let Some((b, &trans)) = self.it.next() {
2450	// Fine because we'll never have more than u8::MAX transitions in
2451	// one state.
2452	let b = b.as_u8();
2453	let (prev_start, prev_end, prev_trans) = match self.cur {
2454	Some(t) => t,
2455	None => {
2456	self.cur = Some((b, b, trans));
2457	continue;
2458	}
2459	};
2460	if prev_trans == trans {
2461	self.cur = Some((prev_start, b, prev_trans));
2462	} else {
2463	self.cur = Some((b, b, trans));
2464	if prev_trans.state_id() != DEAD {
2465	return Some((prev_start, prev_end, prev_trans));
2466	}
2467	}
2468	}
2469	if let Some((start, end, trans)) = self.cur.take() {
2470	if trans.state_id() != DEAD {
2471	return Some((start, end, trans));
2472	}
2473	}
2474	None
2475	}
2476	}
2477
2478	/// A cache represents mutable state that a one-pass [`DFA`] requires during a
2479	/// search.
2480	///
2481	/// For a given one-pass DFA, its corresponding cache may be created either via
2482	/// [`DFA::create_cache`], or via [`Cache::new`]. They are equivalent in every
2483	/// way, except the former does not require explicitly importing `Cache`.
2484	///
2485	/// A particular `Cache` is coupled with the one-pass DFA from which it was
2486	/// created. It may only be used with that one-pass DFA. A cache and its
2487	/// allocations may be re-purposed via [`Cache::reset`], in which case, it can
2488	/// only be used with the new one-pass DFA (and not the old one).
2489	#[derive(Clone, Debug)]
2490	pub struct Cache {
2491	/// Scratch space used to store slots during a search. Basically, we use
2492	/// the caller provided slots to store slots known when a match occurs.
2493	/// But after a match occurs, we might continue a search but ultimately
2494	/// fail to extend the match. When continuing the search, we need some
2495	/// place to store candidate capture offsets without overwriting the slot
2496	/// offsets recorded for the most recently seen match.
2497	explicit_slots: Vec<Option<NonMaxUsize>>,
2498	/// The number of slots in the caller-provided 'Captures' value for the
2499	/// current search. This is always at most 'explicit_slots.len()', but
2500	/// might be less than it, if the caller provided fewer slots to fill.
2501	explicit_slot_len: usize,
2502	}
2503
2504	impl Cache {
2505	/// Create a new [`onepass::DFA`](DFA) cache.
2506	///
2507	/// A potentially more convenient routine to create a cache is
2508	/// [`DFA::create_cache`], as it does not require also importing the
2509	/// `Cache` type.
2510	///
2511	/// If you want to reuse the returned `Cache` with some other one-pass DFA,
2512	/// then you must call [`Cache::reset`] with the desired one-pass DFA.
2513	pub fn new(re: &DFA) -> Cache {
2514	let mut cache = Cache { explicit_slots: vec![], explicit_slot_len: `0` };
2515	cache.reset(re);
2516	cache
2517	}
2518
2519	/// Reset this cache such that it can be used for searching with a
2520	/// different [`onepass::DFA`](DFA).
2521	///
2522	/// A cache reset permits reusing memory already allocated in this cache
2523	/// with a different one-pass DFA.
2524	///
2525	/// # Example
2526	///
2527	/// This shows how to re-purpose a cache for use with a different one-pass
2528	/// DFA.
2529	///
2530	/// ```
2531	/// # if cfg!(miri) { return Ok(()); } // miri takes too long
2532	/// use regex_automata::{dfa::onepass::DFA, Match};
2533	///
2534	/// let re1 = DFA::new(r"\w")?;
2535	/// let re2 = DFA::new(r"\W")?;
2536	/// let mut caps1 = re1.create_captures();
2537	/// let mut caps2 = re2.create_captures();
2538	///
2539	/// let mut cache = re1.create_cache();
2540	/// assert_eq!(
2541	/// Some(Match::must(`0`, `0`..`2`)),
2542	/// { re1.captures(&mut cache, "Δ", &mut caps1); caps1.get_match() },
2543	/// );
2544	///
2545	/// // Using 'cache' with re2 is not allowed. It may result in panics or
2546	/// // incorrect results. In order to re-purpose the cache, we must reset
2547	/// // it with the one-pass DFA we'd like to use it with.
2548	/// //
2549	/// // Similarly, after this reset, using the cache with 're1' is also not
2550	/// // allowed.
2551	/// re2.reset_cache(&mut cache);
2552	/// assert_eq!(
2553	/// Some(Match::must(`0`, `0`..`3`)),
2554	/// { re2.captures(&mut cache, "☃", &mut caps2); caps2.get_match() },
2555	/// );
2556	///
2557	/// # Ok::<(), Box<dyn std::error::Error>>(())
2558	/// ```
2559	pub fn reset(&mut self, re: &DFA) {
2560	let explicit_slot_len = re.get_nfa().group_info().explicit_slot_len();
2561	self.explicit_slots.resize(explicit_slot_len, None);
2562	self.explicit_slot_len = explicit_slot_len;
2563	}
2564
2565	/// Returns the heap memory usage, in bytes, of this cache.
2566	///
2567	/// This does not* include the stack size used up by this cache. To*
2568	/// compute that, use `std::mem::size_of::<Cache>()`.
2569	pub fn memory_usage(&self) -> usize {
2570	self.explicit_slots.len() * core::mem::size_of::<Option<NonMaxUsize>>()
2571	}
2572
2573	fn explicit_slots(&mut self) -> &mut [Option<NonMaxUsize>] {
2574	&mut self.explicit_slots[..self.explicit_slot_len]
2575	}
2576
2577	fn setup_search(&mut self, explicit_slot_len: usize) {
2578	self.explicit_slot_len = explicit_slot_len;
2579	}
2580	}
2581
2582	/// Represents a single transition in a one-pass DFA.
2583	///
2584	/// The high 21 bits corresponds to the state ID. The bit following corresponds
2585	/// to the special "match wins" flag. The remaining low 42 bits corresponds to
2586	/// the transition epsilons, which contains the slots that should be saved when
2587	/// this transition is followed and the conditional epsilon transitions that
2588	/// must be satisfied in order to follow this transition.
2589	#[derive(Clone, Copy, Eq, PartialEq)]
2590	struct Transition(u64);
2591
2592	impl Transition {
2593	const STATE_ID_BITS: u64 = `21`;
2594	const STATE_ID_SHIFT: u64 = `64` - Transition::STATE_ID_BITS;
2595	const STATE_ID_LIMIT: u64 = `1` << Transition::STATE_ID_BITS;
2596	const MATCH_WINS_SHIFT: u64 = `64` - (Transition::STATE_ID_BITS + `1`);
2597	const INFO_MASK: u64 = `0x000003FF_FFFFFFFF`;
2598
2599	/// Return a new transition to the given state ID with the given epsilons.
2600	fn new(match_wins: bool, sid: StateID, epsilons: Epsilons) -> Transition {
2601	let match_wins =
2602	if match_wins { `1` << Transition::MATCH_WINS_SHIFT } else { `0` };
2603	let sid = sid.as_u64() << Transition::STATE_ID_SHIFT;
2604	Transition(sid \| match_wins \| epsilons.0)
2605	}
2606
2607	/// Returns true if and only if this transition points to the DEAD state.
2608	fn is_dead(self) -> bool {
2609	self.state_id() == DEAD
2610	}
2611
2612	/// Return whether this transition has a "match wins" property.
2613	///
2614	/// When a transition has this property, it means that if a match has been
2615	/// found and the search uses leftmost-first semantics, then that match
2616	/// should be returned immediately instead of continuing on.
2617	///
2618	/// The "match wins" name comes from RE2, which uses a pretty much
2619	/// identical mechanism for implementing leftmost-first semantics.
2620	fn match_wins(&self) -> bool {
2621	(self.0 >> Transition::MATCH_WINS_SHIFT & `1`) == `1`
2622	}
2623
2624	/// Return the "next" state ID that this transition points to.
2625	fn state_id(&self) -> StateID {
2626	// OK because a Transition has a valid StateID in its upper bits by
2627	// construction. The cast to usize is also correct, even on 16-bit
2628	// targets because, again, we know the upper bits is a valid StateID,
2629	// which can never overflow usize on any supported target.
2630	StateID::new_unchecked(
2631	(self.0 >> Transition::STATE_ID_SHIFT).as_usize(),
2632	)
2633	}
2634
2635	/// Set the "next" state ID in this transition.
2636	fn set_state_id(&mut self, sid: StateID) {
2637	*self = Transition::new(self.match_wins(), sid, self.epsilons());
2638	}
2639
2640	/// Return the epsilons embedded in this transition.
2641	fn epsilons(&self) -> Epsilons {
2642	Epsilons(self.0 & Transition::INFO_MASK)
2643	}
2644	}
2645
2646	impl core::fmt::Debug for Transition {
2647	fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
2648	if self.is_dead() {
2649	return write!(f, "0");
2650	}
2651	write!(f, "{}", self.state_id().as_usize())?;
2652	if self.match_wins() {
2653	write!(f, "-MW")?;
2654	}
2655	if !self.epsilons().is_empty() {
2656	write!(f, "-{:?}", self.epsilons())?;
2657	}
2658	Ok(())
2659	}
2660	}
2661
2662	/// A representation of a match state's pattern ID along with the epsilons for
2663	/// when a match occurs.
2664	///
2665	/// A match state in a one-pass DFA, unlike in a more general DFA, has exactly
2666	/// one pattern ID. If it had more, then the original NFA would not have been
2667	/// one-pass.
2668	///
2669	/// The "epsilons" part of this corresponds to what was found in the epsilon
2670	/// transitions between the transition taken in the last byte of input and the
2671	/// ultimate match state. This might include saving slots and/or conditional
2672	/// epsilon transitions that must be satisfied before one can report the match.
2673	///
2674	/// Technically, every state has room for a 'PatternEpsilons', but it is only
2675	/// ever non-empty for match states.
2676	#[derive(Clone, Copy)]
2677	struct PatternEpsilons(u64);
2678
2679	impl PatternEpsilons {
2680	const PATTERN_ID_BITS: u64 = `22`;
2681	const PATTERN_ID_SHIFT: u64 = `64` - PatternEpsilons::PATTERN_ID_BITS;
2682	// A sentinel value indicating that this is not a match state. We don't
2683	// use 0 since 0 is a valid pattern ID.
2684	const PATTERN_ID_NONE: u64 = `0x00000000_003FFFFF`;
2685	const PATTERN_ID_LIMIT: u64 = PatternEpsilons::PATTERN_ID_NONE;
2686	const PATTERN_ID_MASK: u64 = `0xFFFFFC00_00000000`;
2687	const EPSILONS_MASK: u64 = `0x000003FF_FFFFFFFF`;
2688
2689	/// Return a new empty pattern epsilons that has no pattern ID and has no
2690	/// epsilons. This is suitable for non-match states.
2691	fn empty() -> PatternEpsilons {
2692	PatternEpsilons(
2693	PatternEpsilons::PATTERN_ID_NONE
2694	<< PatternEpsilons::PATTERN_ID_SHIFT,
2695	)
2696	}
2697
2698	/// Whether this pattern epsilons is empty or not. It's empty when it has
2699	/// no pattern ID and an empty epsilons.
2700	fn is_empty(self) -> bool {
2701	self.pattern_id().is_none() && self.epsilons().is_empty()
2702	}
2703
2704	/// Return the pattern ID in this pattern epsilons if one exists.
2705	fn pattern_id(self) -> Option<PatternID> {
2706	let pid = self.0 >> PatternEpsilons::PATTERN_ID_SHIFT;
2707	if pid == PatternEpsilons::PATTERN_ID_LIMIT {
2708	None
2709	} else {
2710	Some(PatternID::new_unchecked(pid.as_usize()))
2711	}
2712	}
2713
2714	/// Returns the pattern ID without checking whether it's valid. If this is
2715	/// called and there is no pattern ID in this `PatternEpsilons`, then this
2716	/// will likely produce an incorrect result or possibly even a panic or
2717	/// an overflow. But safety will not be violated.
2718	///
2719	/// This is useful when you know a particular state is a match state. If
2720	/// it's a match state, then it must have a pattern ID.
2721	fn pattern_id_unchecked(self) -> PatternID {
2722	let pid = self.0 >> PatternEpsilons::PATTERN_ID_SHIFT;
2723	PatternID::new_unchecked(pid.as_usize())
2724	}
2725
2726	/// Return a new pattern epsilons with the given pattern ID, but the same
2727	/// epsilons.
2728	fn set_pattern_id(self, pid: PatternID) -> PatternEpsilons {
2729	PatternEpsilons(
2730	(pid.as_u64() << PatternEpsilons::PATTERN_ID_SHIFT)
2731	\| (self.0 & PatternEpsilons::EPSILONS_MASK),
2732	)
2733	}
2734
2735	/// Return the epsilons part of this pattern epsilons.
2736	fn epsilons(self) -> Epsilons {
2737	Epsilons(self.0 & PatternEpsilons::EPSILONS_MASK)
2738	}
2739
2740	/// Return a new pattern epsilons with the given epsilons, but the same
2741	/// pattern ID.
2742	fn set_epsilons(self, epsilons: Epsilons) -> PatternEpsilons {
2743	PatternEpsilons(
2744	(self.0 & PatternEpsilons::PATTERN_ID_MASK)
2745	\| (u64::from(epsilons.0) & PatternEpsilons::EPSILONS_MASK),
2746	)
2747	}
2748	}
2749
2750	impl core::fmt::Debug for PatternEpsilons {
2751	fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
2752	if self.is_empty() {
2753	return write!(f, "N/A");
2754	}
2755	if let Some(pid) = self.pattern_id() {
2756	write!(f, "{}", pid.as_usize())?;
2757	}
2758	if !self.epsilons().is_empty() {
2759	if self.pattern_id().is_some() {
2760	write!(f, "/")?;
2761	}
2762	write!(f, "{:?}", self.epsilons())?;
2763	}
2764	Ok(())
2765	}
2766	}
2767
2768	/// Epsilons represents all of the NFA epsilons transitions that went into a
2769	/// single transition in a single DFA state. In this case, it only represents
2770	/// the epsilon transitions that have some kind of non-consuming side effect:
2771	/// either the transition requires storing the current position of the search
2772	/// into a slot, or the transition is conditional and requires the current
2773	/// position in the input to satisfy an assertion before the transition may be
2774	/// taken.
2775	///
2776	/// This folds the cumulative effect of a group of NFA states (all connected
2777	/// by epsilon transitions) down into a single set of bits. While these bits
2778	/// can represent all possible conditional epsilon transitions, it only permits
2779	/// storing up to a somewhat small number of slots.
2780	///
2781	/// Epsilons is represented as a 42-bit integer. For example, it is packed into
2782	/// the lower 42 bits of a `Transition`. (Where the high 22 bits contains a
2783	/// `StateID` and a special "match wins" property.)
2784	#[derive(Clone, Copy)]
2785	struct Epsilons(u64);
2786
2787	impl Epsilons {
2788	const SLOT_MASK: u64 = `0x000003FF_FFFFFC00`;
2789	const SLOT_SHIFT: u64 = `10`;
2790	const LOOK_MASK: u64 = `0x00000000_000003FF`;
2791
2792	/// Create a new empty epsilons. It has no slots and no assertions that
2793	/// need to be satisfied.
2794	fn empty() -> Epsilons {
2795	Epsilons(`0`)
2796	}
2797
2798	/// Returns true if this epsilons contains no slots and no assertions.
2799	fn is_empty(self) -> bool {
2800	self.0 == `0`
2801	}
2802
2803	/// Returns the slot epsilon transitions.
2804	fn slots(self) -> Slots {
2805	Slots((self.0 >> Epsilons::SLOT_SHIFT).low_u32())
2806	}
2807
2808	/// Set the slot epsilon transitions.
2809	fn set_slots(self, slots: Slots) -> Epsilons {
2810	Epsilons(
2811	(u64::from(slots.0) << Epsilons::SLOT_SHIFT)
2812	\| (self.0 & Epsilons::LOOK_MASK),
2813	)
2814	}
2815
2816	/// Return the set of look-around assertions in these epsilon transitions.
2817	fn looks(self) -> LookSet {
2818	LookSet { bits: (self.0 & Epsilons::LOOK_MASK).low_u32() }
2819	}
2820
2821	/// Set the look-around assertions on these epsilon transitions.
2822	fn set_looks(self, look_set: LookSet) -> Epsilons {
2823	Epsilons(
2824	(self.0 & Epsilons::SLOT_MASK)
2825	\| (u64::from(look_set.bits) & Epsilons::LOOK_MASK),
2826	)
2827	}
2828	}
2829
2830	impl core::fmt::Debug for Epsilons {
2831	fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
2832	let mut wrote = `false`;
2833	if !self.slots().is_empty() {
2834	write!(f, "{:?}", self.slots())?;
2835	wrote = `true`;
2836	}
2837	if !self.looks().is_empty() {
2838	if wrote {
2839	write!(f, "/")?;
2840	}
2841	write!(f, "{:?}", self.looks())?;
2842	wrote = `true`;
2843	}
2844	if !wrote {
2845	write!(f, "N/A")?;
2846	}
2847	Ok(())
2848	}
2849	}
2850
2851	/// The set of epsilon transitions indicating that the current position in a
2852	/// search should be saved to a slot.
2853	///
2854	/// This only* represents explicit slots. So for example, the pattern*
2855	/// `[a-z]+([0-9]+)([a-z]+)` has:
2856	///
2857	/// 3 capturing groups, thus 6 slots.*
2858	/// 1 implicit capturing group, thus 2 implicit slots.*
2859	/// 2 explicit capturing groups, thus 4 explicit slots.*
2860	///
2861	/// While implicit slots are represented by epsilon transitions in an NFA, we
2862	/// do not explicitly represent them here. Instead, implicit slots are assumed
2863	/// to be present and handled automatically in the search code. Therefore,
2864	/// that means we only need to represent explicit slots in our epsilon
2865	/// transitions.
2866	///
2867	/// Its representation is a bit set. The bit 'i' is set if and only if there
2868	/// exists an explicit slot at index 'c', where 'c = (#patterns 2) + i'. That*
2869	/// is, the bit 'i' corresponds to the first explicit slot and the first
2870	/// explicit slot appears immediately following the last implicit slot. (If
2871	/// this is confusing, see `GroupInfo` for more details on how slots works.)
2872	///
2873	/// A single `Slots` represents all the active slots in a sub-graph of an NFA,
2874	/// where all the states are connected by epsilon transitions. In effect, when
2875	/// traversing the one-pass DFA during a search, all slots set in a particular
2876	/// transition must be captured by recording the current search position.
2877	///
2878	/// The API of `Slots` requires the caller to handle the explicit slot offset.
2879	/// That is, a `Slots` doesn't know where the explicit slots start for a
2880	/// particular NFA. Thus, if the callers see's the bit 'i' is set, then they
2881	/// need to do the arithmetic above to find 'c', which is the real actual slot
2882	/// index in the corresponding NFA.
2883	#[derive(Clone, Copy)]
2884	struct Slots(u32);
2885
2886	impl Slots {
2887	const LIMIT: usize = `32`;
2888
2889	/// Insert the slot at the given bit index.
2890	fn insert(self, slot: usize) -> Slots {
2891	debug_assert!(slot < Slots::LIMIT);
2892	Slots(self.0 \| (`1` << slot.as_u32()))
2893	}
2894
2895	/// Remove the slot at the given bit index.
2896	fn remove(self, slot: usize) -> Slots {
2897	debug_assert!(slot < Slots::LIMIT);
2898	Slots(self.0 & !(`1` << slot.as_u32()))
2899	}
2900
2901	/// Returns true if and only if this set contains no slots.
2902	fn is_empty(self) -> bool {
2903	self.0 == `0`
2904	}
2905
2906	/// Returns an iterator over all of the set bits in this set.
2907	fn iter(self) -> SlotsIter {
2908	SlotsIter { slots: self }
2909	}
2910
2911	/// For the position `at` in the current haystack, copy it to
2912	/// `caller_explicit_slots` for all slots that are in this set.
2913	///
2914	/// Callers may pass a slice of any length. Slots in this set bigger than
2915	/// the length of the given explicit slots are simply skipped.
2916	///
2917	/// The slice must* correspond only to the explicit slots and the first*
2918	/// element of the slice must always correspond to the first explicit slot
2919	/// in the corresponding NFA.
2920	fn apply(
2921	self,
2922	at: usize,
2923	caller_explicit_slots: &mut [Option<NonMaxUsize>],
2924	) {
2925	if self.is_empty() {
2926	return;
2927	}
2928	let at = NonMaxUsize::new(at);
2929	for slot in self.iter() {
2930	if slot >= caller_explicit_slots.len() {
2931	break;
2932	}
2933	caller_explicit_slots[slot] = at;
2934	}
2935	}
2936	}
2937
2938	impl core::fmt::Debug for Slots {
2939	fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
2940	write!(f, "S")?;
2941	for slot in self.iter() {
2942	write!(f, "-{:?}", slot)?;
2943	}
2944	Ok(())
2945	}
2946	}
2947
2948	/// An iterator over all of the bits set in a slot set.
2949	///
2950	/// This returns the bit index that is set, so callers may need to offset it
2951	/// to get the actual NFA slot index.
2952	#[derive(Debug)]
2953	struct SlotsIter {
2954	slots: Slots,
2955	}
2956
2957	impl Iterator for SlotsIter {
2958	type Item = usize;
2959
2960	fn next(&mut self) -> Option<usize> {
2961	// Number of zeroes here is always <= u8::MAX, and so fits in a usize.
2962	let slot = self.slots.0.trailing_zeros().as_usize();
2963	if slot >= Slots::LIMIT {
2964	return None;
2965	}
2966	self.slots = self.slots.remove(slot);
2967	Some(slot)
2968	}
2969	}
2970
2971	/// An error that occurred during the construction of a one-pass DFA.
2972	///
2973	/// This error does not provide many introspection capabilities. There are
2974	/// generally only two things you can do with it:
2975	///
2976	/// Obtain a human readable message via its `std::fmt::Display` impl.*
2977	/// Access an underlying* [`thompson::BuildError`] type from its `source`
2978	/// method via the `std::error::Error` trait. This error only occurs when using
2979	/// convenience routines for building a one-pass DFA directly from a pattern
2980	/// string.
2981	///
2982	/// When the `std` feature is enabled, this implements the `std::error::Error`
2983	/// trait.
2984	#[derive(Clone, Debug)]
2985	pub struct BuildError {
2986	kind: BuildErrorKind,
2987	}
2988
2989	/// The kind of error that occurred during the construction of a one-pass DFA.
2990	#[derive(Clone, Debug)]
2991	enum BuildErrorKind {
2992	NFA(crate::nfa::thompson::BuildError),
2993	Word(UnicodeWordBoundaryError),
2994	TooManyStates { limit: u64 },
2995	TooManyPatterns { limit: u64 },
2996	UnsupportedLook { look: Look },
2997	ExceededSizeLimit { limit: usize },
2998	NotOnePass { msg: &'static str },
2999	}
3000
3001	impl BuildError {
3002	fn nfa(err: crate::nfa::thompson::BuildError) -> BuildError {
3003	BuildError { kind: BuildErrorKind::NFA(err) }
3004	}
3005
3006	fn word(err: UnicodeWordBoundaryError) -> BuildError {
3007	BuildError { kind: BuildErrorKind::Word(err) }
3008	}
3009
3010	fn too_many_states(limit: u64) -> BuildError {
3011	BuildError { kind: BuildErrorKind::TooManyStates { limit } }
3012	}
3013
3014	fn too_many_patterns(limit: u64) -> BuildError {
3015	BuildError { kind: BuildErrorKind::TooManyPatterns { limit } }
3016	}
3017
3018	fn unsupported_look(look: Look) -> BuildError {
3019	BuildError { kind: BuildErrorKind::UnsupportedLook { look } }
3020	}
3021
3022	fn exceeded_size_limit(limit: usize) -> BuildError {
3023	BuildError { kind: BuildErrorKind::ExceededSizeLimit { limit } }
3024	}
3025
3026	fn not_one_pass(msg: &'static str) -> BuildError {
3027	BuildError { kind: BuildErrorKind::NotOnePass { msg } }
3028	}
3029	}
3030
3031	#[cfg(feature = "std")]
3032	impl std::error::Error for BuildError {
3033	fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
3034	use self::BuildErrorKind::*;
3035
3036	match self.kind {
3037	NFA(ref err) => Some(err),
3038	Word(ref err) => Some(err),
3039	_ => None,
3040	}
3041	}
3042	}
3043
3044	impl core::fmt::Display for BuildError {
3045	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
3046	use self::BuildErrorKind::*;
3047
3048	match self.kind {
3049	NFA(_) => write!(f, "error building NFA"),
3050	Word(_) => write!(f, "NFA contains Unicode word boundary"),
3051	TooManyStates { limit } => write!(
3052	f,
3053	"one-pass DFA exceeded a limit of {:?} for number of states",
3054	limit,
3055	),
3056	TooManyPatterns { limit } => write!(
3057	f,
3058	"one-pass DFA exceeded a limit of {:?} for number of patterns",
3059	limit,
3060	),
3061	UnsupportedLook { look } => write!(
3062	f,
3063	"one-pass DFA does not support the {:?} assertion",
3064	look,
3065	),
3066	ExceededSizeLimit { limit } => write!(
3067	f,
3068	"one-pass DFA exceeded size limit of {:?} during building",
3069	limit,
3070	),
3071	NotOnePass { msg } => write!(
3072	f,
3073	"one-pass DFA could not be built because \
3074	pattern is not one-pass: {}",
3075	msg,
3076	),
3077	}
3078	}
3079	}
3080
3081	#[cfg(all(test, feature = "syntax"))]
3082	mod tests {
3083	use alloc::string::ToString;
3084
3085	use super::*;
3086
3087	#[test]
3088	fn fail_conflicting_transition() {
3089	let predicate = \|err: &str\| err.contains("conflicting transition");
3090
3091	let err = DFA::new(r"a*[ab]").unwrap_err().to_string();
3092	assert!(predicate(&err), "{}", err);
3093	}
3094
3095	#[test]
3096	fn fail_multiple_epsilon() {
3097	let predicate = \|err: &str\| {
3098	err.contains("multiple epsilon transitions to same state")
3099	};
3100
3101	let err = DFA::new(r"(^\|$)a").unwrap_err().to_string();
3102	assert!(predicate(&err), "{}", err);
3103	}
3104
3105	#[test]
3106	fn fail_multiple_match() {
3107	let predicate = \|err: &str\| {
3108	err.contains("multiple epsilon transitions to match state")
3109	};
3110
3111	let err = DFA::new_many(&[r"^", r"$"]).unwrap_err().to_string();
3112	assert!(predicate(&err), "{}", err);
3113	}
3114
3115	// This test is meant to build a one-pass regex with the maximum number of
3116	// possible slots.
3117	//
3118	// NOTE: Remember that the slot limit only applies to explicit capturing
3119	// groups. Any number of implicit capturing groups is supported (up to the
3120	// maximum number of supported patterns), since implicit groups are handled
3121	// by the search loop itself.
3122	#[test]
3123	fn max_slots() {
3124	// One too many...
3125	let pat = r"(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)";
3126	assert!(DFA::new(pat).is_err());
3127	// Just right.
3128	let pat = r"(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)";
3129	assert!(DFA::new(pat).is_ok());
3130	}
3131
3132	// This test ensures that the one-pass DFA works with all look-around
3133	// assertions that we expect it to work with.
3134	//
3135	// The utility of this test is that each one-pass transition has a small
3136	// amount of space to store look-around assertions. Currently, there is
3137	// logic in the one-pass constructor to ensure there aren't more than ten
3138	// possible assertions. And indeed, there are only ten possible assertions
3139	// (at time of writing), so this is okay. But conceivably, more assertions
3140	// could be added. So we check that things at least work with what we
3141	// expect them to work with.
3142	#[test]
3143	fn assertions() {
3144	// haystack anchors
3145	assert!(DFA::new(r"^").is_ok());
3146	assert!(DFA::new(r"$").is_ok());
3147
3148	// line anchors
3149	assert!(DFA::new(r"(?m)^").is_ok());
3150	assert!(DFA::new(r"(?m)$").is_ok());
3151	assert!(DFA::new(r"(?Rm)^").is_ok());
3152	assert!(DFA::new(r"(?Rm)$").is_ok());
3153
3154	// word boundaries
3155	if cfg!(feature = "unicode-word-boundary") {
3156	assert!(DFA::new(r"\b").is_ok());
3157	assert!(DFA::new(r"\B").is_ok());
3158	}
3159	assert!(DFA::new(r"(?-u)\b").is_ok());
3160	assert!(DFA::new(r"(?-u)\B").is_ok());
3161	}
3162
3163	#[cfg(not(miri))] // takes too long on miri
3164	#[test]
3165	fn is_one_pass() {
3166	use crate::util::syntax;
3167
3168	assert!(DFA::new(r"a*b").is_ok());
3169	if cfg!(feature = "unicode-perl") {
3170	assert!(DFA::new(r"\w").is_ok());
3171	}
3172	assert!(DFA::new(r"(?-u)\w*\s").is_ok());
3173	assert!(DFA::new(r"(?s:.)*?").is_ok());
3174	assert!(DFA::builder()
3175	.syntax(syntax::Config::new().utf8(`false`))
3176	.build(r"(?s-u:.)*?")
3177	.is_ok());
3178	}
3179
3180	#[test]
3181	fn is_not_one_pass() {
3182	assert!(DFA::new(r"a*a").is_err());
3183	assert!(DFA::new(r"(?s-u:.)*?").is_err());
3184	assert!(DFA::new(r"(?s:.)*?a").is_err());
3185	}
3186
3187	#[cfg(not(miri))]
3188	#[test]
3189	fn is_not_one_pass_bigger() {
3190	assert!(DFA::new(r"\w*\s").is_err());
3191	}
3192	}
3193