Debian Codegraph @

third_party/rust/regex-automata/src/hybrid/dfa.rs

raw
1 /*!
2 Types and routines specific to lazy DFAs.
3
4 This module is the home of [`hybrid::dfa::DFA`](DFA).
5
6 This module also contains a [`hybrid::dfa::Builder`](Builder) and a
7 [`hybrid::dfa::Config`](Config) for configuring and building a lazy DFA.
8 */
9
10 use core::{iter, mem::size_of};
11
12 use alloc::vec::Vec;
13
14 use crate::{
15 hybrid::{
16 error::{BuildError, CacheError},
17 id::{LazyStateID, LazyStateIDError},
18 search,
19 },
20 nfa::thompson,
21 util::{
22 alphabet::{self, ByteClasses, ByteSet},
23 determinize::{self, State, StateBuilderEmpty, StateBuilderNFA},
24 empty,
25 prefilter::Prefilter,
26 primitives::{PatternID, StateID as NFAStateID},
27 search::{
28 Anchored, HalfMatch, Input, MatchError, MatchKind, PatternSet,
29 },
30 sparse_set::SparseSets,
31 start::{Start, StartByteMap},
32 },
33 };
34
35 /// The minimum number of states that a lazy DFA's cache size must support.
36 ///
37 /// This is checked at time of construction to ensure that at least some small
38 /// number of states can fit in the given capacity allotment. If we can't fit
39 /// at least this number of states, then the thinking is that it's pretty
40 /// senseless to use the lazy DFA. More to the point, parts of the code do
41 /// assume that the cache can fit at least some small number of states.
42 const MIN_STATES: usize = SENTINEL_STATES + 2;
43
44 /// The number of "sentinel" states that get added to every lazy DFA.
45 ///
46 /// These are special states indicating status conditions of a search: unknown,
47 /// dead and quit. These states in particular also use zero NFA states, so
48 /// their memory usage is quite small. This is relevant for computing the
49 /// minimum memory needed for a lazy DFA cache.
50 const SENTINEL_STATES: usize = 3;
51
52 /// A hybrid NFA/DFA (also called a "lazy DFA") for regex searching.
53 ///
54 /// A lazy DFA is a DFA that builds itself at search time. It otherwise has
55 /// very similar characteristics as a [`dense::DFA`](crate::dfa::dense::DFA).
56 /// Indeed, both support precisely the same regex features with precisely the
57 /// same semantics.
58 ///
59 /// Where as a `dense::DFA` must be completely built to handle any input before
60 /// it may be used for search, a lazy DFA starts off effectively empty. During
61 /// a search, a lazy DFA will build itself depending on whether it has already
62 /// computed the next transition or not. If it has, then it looks a lot like
63 /// a `dense::DFA` internally: it does a very fast table based access to find
64 /// the next transition. Otherwise, if the state hasn't been computed, then it
65 /// does determinization _for that specific transition_ to compute the next DFA
66 /// state.
67 ///
68 /// The main selling point of a lazy DFA is that, in practice, it has
69 /// the performance profile of a `dense::DFA` without the weakness of it
70 /// taking worst case exponential time to build. Indeed, for each byte of
71 /// input, the lazy DFA will construct as most one new DFA state. Thus, a
72 /// lazy DFA achieves worst case `O(mn)` time for regex search (where `m ~
73 /// pattern.len()` and `n ~ haystack.len()`).
74 ///
75 /// The main downsides of a lazy DFA are:
76 ///
77 /// 1. It requires mutable "cache" space during search. This is where the
78 /// transition table, among other things, is stored.
79 /// 2. In pathological cases (e.g., if the cache is too small), it will run
80 /// out of room and either require a bigger cache capacity or will repeatedly
81 /// clear the cache and thus repeatedly regenerate DFA states. Overall, this
82 /// will tend to be slower than a typical NFA simulation.
83 ///
84 /// # Capabilities
85 ///
86 /// Like a `dense::DFA`, a single lazy DFA fundamentally supports the following
87 /// operations:
88 ///
89 /// 1. Detection of a match.
90 /// 2. Location of the end of a match.
91 /// 3. In the case of a lazy DFA with multiple patterns, which pattern matched
92 /// is reported as well.
93 ///
94 /// A notable absence from the above list of capabilities is the location of
95 /// the *start* of a match. In order to provide both the start and end of
96 /// a match, *two* lazy DFAs are required. This functionality is provided by a
97 /// [`Regex`](crate::hybrid::regex::Regex).
98 ///
99 /// # Example
100 ///
101 /// This shows how to build a lazy DFA with the default configuration and
102 /// execute a search. Notice how, in contrast to a `dense::DFA`, we must create
103 /// a cache and pass it to our search routine.
104 ///
105 /// ```
106 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
107 ///
108 /// let dfa = DFA::new("foo[0-9]+")?;
109 /// let mut cache = dfa.create_cache();
110 ///
111 /// let expected = Some(HalfMatch::must(0, 8));
112 /// assert_eq!(expected, dfa.try_search_fwd(
113 /// &mut cache, &Input::new("foo12345"))?,
114 /// );
115 /// # Ok::<(), Box<dyn std::error::Error>>(())
116 /// ```
117 #[derive(Clone, Debug)]
118 pub struct DFA {
119 config: Config,
120 nfa: thompson::NFA,
121 stride2: usize,
122 start_map: StartByteMap,
123 classes: ByteClasses,
124 quitset: ByteSet,
125 cache_capacity: usize,
126 }
127
128 impl DFA {
129 /// Parse the given regular expression using a default configuration and
130 /// return the corresponding lazy DFA.
131 ///
132 /// If you want a non-default configuration, then use the [`Builder`] to
133 /// set your own configuration.
134 ///
135 /// # Example
136 ///
137 /// ```
138 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
139 ///
140 /// let dfa = DFA::new("foo[0-9]+bar")?;
141 /// let mut cache = dfa.create_cache();
142 ///
143 /// let expected = HalfMatch::must(0, 11);
144 /// assert_eq!(
145 /// Some(expected),
146 /// dfa.try_search_fwd(&mut cache, &Input::new("foo12345bar"))?,
147 /// );
148 /// # Ok::<(), Box<dyn std::error::Error>>(())
149 /// ```
150 #[cfg(feature = "syntax")]
151 pub fn new(pattern: &str) -> Result<DFA, BuildError> {
152 DFA::builder().build(pattern)
153 }
154
155 /// Parse the given regular expressions using a default configuration and
156 /// return the corresponding lazy multi-DFA.
157 ///
158 /// If you want a non-default configuration, then use the [`Builder`] to
159 /// set your own configuration.
160 ///
161 /// # Example
162 ///
163 /// ```
164 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
165 ///
166 /// let dfa = DFA::new_many(&["[0-9]+", "[a-z]+"])?;
167 /// let mut cache = dfa.create_cache();
168 ///
169 /// let expected = HalfMatch::must(1, 3);
170 /// assert_eq!(
171 /// Some(expected),
172 /// dfa.try_search_fwd(&mut cache, &Input::new("foo12345bar"))?,
173 /// );
174 /// # Ok::<(), Box<dyn std::error::Error>>(())
175 /// ```
176 #[cfg(feature = "syntax")]
177 pub fn new_many<P: AsRef<str>>(patterns: &[P]) -> Result<DFA, BuildError> {
178 DFA::builder().build_many(patterns)
179 }
180
181 /// Create a new lazy DFA that matches every input.
182 ///
183 /// # Example
184 ///
185 /// ```
186 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
187 ///
188 /// let dfa = DFA::always_match()?;
189 /// let mut cache = dfa.create_cache();
190 ///
191 /// let expected = HalfMatch::must(0, 0);
192 /// assert_eq!(Some(expected), dfa.try_search_fwd(
193 /// &mut cache, &Input::new(""))?,
194 /// );
195 /// assert_eq!(Some(expected), dfa.try_search_fwd(
196 /// &mut cache, &Input::new("foo"))?,
197 /// );
198 /// # Ok::<(), Box<dyn std::error::Error>>(())
199 /// ```
200 pub fn always_match() -> Result<DFA, BuildError> {
201 let nfa = thompson::NFA::always_match();
202 Builder::new().build_from_nfa(nfa)
203 }
204
205 /// Create a new lazy DFA that never matches any input.
206 ///
207 /// # Example
208 ///
209 /// ```
210 /// use regex_automata::{hybrid::dfa::DFA, Input};
211 ///
212 /// let dfa = DFA::never_match()?;
213 /// let mut cache = dfa.create_cache();
214 ///
215 /// assert_eq!(None, dfa.try_search_fwd(&mut cache, &Input::new(""))?);
216 /// assert_eq!(None, dfa.try_search_fwd(&mut cache, &Input::new("foo"))?);
217 /// # Ok::<(), Box<dyn std::error::Error>>(())
218 /// ```
219 pub fn never_match() -> Result<DFA, BuildError> {
220 let nfa = thompson::NFA::never_match();
221 Builder::new().build_from_nfa(nfa)
222 }
223
224 /// Return a default configuration for a `DFA`.
225 ///
226 /// This is a convenience routine to avoid needing to import the [`Config`]
227 /// type when customizing the construction of a lazy DFA.
228 ///
229 /// # Example
230 ///
231 /// This example shows how to build a lazy DFA that heuristically supports
232 /// Unicode word boundaries.
233 ///
234 /// ```
235 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
236 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, MatchError, Input};
237 ///
238 /// let re = DFA::builder()
239 /// .configure(DFA::config().unicode_word_boundary(true))
240 /// .build(r"\b\w+\b")?;
241 /// let mut cache = re.create_cache();
242 ///
243 /// // Since our haystack is all ASCII, the DFA search sees then and knows
244 /// // it is legal to interpret Unicode word boundaries as ASCII word
245 /// // boundaries.
246 /// let input = Input::new("!!foo!!");
247 /// let expected = HalfMatch::must(0, 5);
248 /// assert_eq!(Some(expected), re.try_search_fwd(&mut cache, &input)?);
249 ///
250 /// // But if our haystack contains non-ASCII, then the search will fail
251 /// // with an error.
252 /// let input = Input::new("!!βββ!!");
253 /// let expected = MatchError::quit(b'\xCE', 2);
254 /// assert_eq!(Err(expected), re.try_search_fwd(&mut cache, &input));
255 ///
256 /// # Ok::<(), Box<dyn std::error::Error>>(())
257 /// ```
258 pub fn config() -> Config {
259 Config::new()
260 }
261
262 /// Return a builder for configuring the construction of a `Regex`.
263 ///
264 /// This is a convenience routine to avoid needing to import the
265 /// [`Builder`] type in common cases.
266 ///
267 /// # Example
268 ///
269 /// This example shows how to use the builder to disable UTF-8 mode
270 /// everywhere for lazy DFAs.
271 ///
272 /// ```
273 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
274 /// use regex_automata::{hybrid::dfa::DFA, util::syntax, HalfMatch, Input};
275 ///
276 /// let re = DFA::builder()
277 /// .syntax(syntax::Config::new().utf8(false))
278 /// .build(r"foo(?-u:[^b])ar.*")?;
279 /// let mut cache = re.create_cache();
280 ///
281 /// let input = Input::new(b"\xFEfoo\xFFarzz\xE2\x98\xFF\n");
282 /// let expected = Some(HalfMatch::must(0, 9));
283 /// let got = re.try_search_fwd(&mut cache, &input)?;
284 /// assert_eq!(expected, got);
285 ///
286 /// # Ok::<(), Box<dyn std::error::Error>>(())
287 /// ```
288 pub fn builder() -> Builder {
289 Builder::new()
290 }
291
292 /// Create a new cache for this lazy DFA.
293 ///
294 /// The cache returned should only be used for searches for this
295 /// lazy DFA. If you want to reuse the cache for another DFA, then
296 /// you must call [`Cache::reset`] with that DFA (or, equivalently,
297 /// [`DFA::reset_cache`]).
298 pub fn create_cache(&self) -> Cache {
299 Cache::new(self)
300 }
301
302 /// Reset the given cache such that it can be used for searching with the
303 /// this lazy DFA (and only this DFA).
304 ///
305 /// A cache reset permits reusing memory already allocated in this cache
306 /// with a different lazy DFA.
307 ///
308 /// Resetting a cache sets its "clear count" to 0. This is relevant if the
309 /// lazy DFA has been configured to "give up" after it has cleared the
310 /// cache a certain number of times.
311 ///
312 /// Any lazy state ID generated by the cache prior to resetting it is
313 /// invalid after the reset.
314 ///
315 /// # Example
316 ///
317 /// This shows how to re-purpose a cache for use with a different DFA.
318 ///
319 /// ```
320 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
321 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
322 ///
323 /// let dfa1 = DFA::new(r"\w")?;
324 /// let dfa2 = DFA::new(r"\W")?;
325 ///
326 /// let mut cache = dfa1.create_cache();
327 /// assert_eq!(
328 /// Some(HalfMatch::must(0, 2)),
329 /// dfa1.try_search_fwd(&mut cache, &Input::new("Δ"))?,
330 /// );
331 ///
332 /// // Using 'cache' with dfa2 is not allowed. It may result in panics or
333 /// // incorrect results. In order to re-purpose the cache, we must reset
334 /// // it with the DFA we'd like to use it with.
335 /// //
336 /// // Similarly, after this reset, using the cache with 'dfa1' is also not
337 /// // allowed.
338 /// dfa2.reset_cache(&mut cache);
339 /// assert_eq!(
340 /// Some(HalfMatch::must(0, 3)),
341 /// dfa2.try_search_fwd(&mut cache, &Input::new("☃"))?,
342 /// );
343 ///
344 /// # Ok::<(), Box<dyn std::error::Error>>(())
345 /// ```
346 pub fn reset_cache(&self, cache: &mut Cache) {
347 Lazy::new(self, cache).reset_cache()
348 }
349
350 /// Returns the total number of patterns compiled into this lazy DFA.
351 ///
352 /// In the case of a DFA that contains no patterns, this returns `0`.
353 ///
354 /// # Example
355 ///
356 /// This example shows the pattern length for a DFA that never matches:
357 ///
358 /// ```
359 /// use regex_automata::hybrid::dfa::DFA;
360 ///
361 /// let dfa = DFA::never_match()?;
362 /// assert_eq!(dfa.pattern_len(), 0);
363 /// # Ok::<(), Box<dyn std::error::Error>>(())
364 /// ```
365 ///
366 /// And another example for a DFA that matches at every position:
367 ///
368 /// ```
369 /// use regex_automata::hybrid::dfa::DFA;
370 ///
371 /// let dfa = DFA::always_match()?;
372 /// assert_eq!(dfa.pattern_len(), 1);
373 /// # Ok::<(), Box<dyn std::error::Error>>(())
374 /// ```
375 ///
376 /// And finally, a DFA that was constructed from multiple patterns:
377 ///
378 /// ```
379 /// use regex_automata::hybrid::dfa::DFA;
380 ///
381 /// let dfa = DFA::new_many(&["[0-9]+", "[a-z]+", "[A-Z]+"])?;
382 /// assert_eq!(dfa.pattern_len(), 3);
383 /// # Ok::<(), Box<dyn std::error::Error>>(())
384 /// ```
385 pub fn pattern_len(&self) -> usize {
386 self.nfa.pattern_len()
387 }
388
389 /// Returns the equivalence classes that make up the alphabet for this DFA.
390 ///
391 /// Unless [`Config::byte_classes`] was disabled, it is possible that
392 /// multiple distinct bytes are grouped into the same equivalence class
393 /// if it is impossible for them to discriminate between a match and a
394 /// non-match. This has the effect of reducing the overall alphabet size
395 /// and in turn potentially substantially reducing the size of the DFA's
396 /// transition table.
397 ///
398 /// The downside of using equivalence classes like this is that every state
399 /// transition will automatically use this map to convert an arbitrary
400 /// byte to its corresponding equivalence class. In practice this has a
401 /// negligible impact on performance.
402 pub fn byte_classes(&self) -> &ByteClasses {
403 &self.classes
404 }
405
406 /// Returns this lazy DFA's configuration.
407 pub fn get_config(&self) -> &Config {
408 &self.config
409 }
410
411 /// Returns a reference to the underlying NFA.
412 pub fn get_nfa(&self) -> &thompson::NFA {
413 &self.nfa
414 }
415
416 /// Returns the stride, as a base-2 exponent, required for these
417 /// equivalence classes.
418 ///
419 /// The stride is always the smallest power of 2 that is greater than or
420 /// equal to the alphabet length. This is done so that converting between
421 /// state IDs and indices can be done with shifts alone, which is much
422 /// faster than integer division.
423 fn stride2(&self) -> usize {
424 self.stride2
425 }
426
427 /// Returns the total stride for every state in this lazy DFA. This
428 /// corresponds to the total number of transitions used by each state in
429 /// this DFA's transition table.
430 fn stride(&self) -> usize {
431 1 << self.stride2()
432 }
433
434 /// Returns the memory usage, in bytes, of this lazy DFA.
435 ///
436 /// This does **not** include the stack size used up by this lazy DFA. To
437 /// compute that, use `std::mem::size_of::<DFA>()`. This also does not
438 /// include the size of the `Cache` used.
439 ///
440 /// This also does not include any heap memory used by the NFA inside of
441 /// this hybrid NFA/DFA. This is because the NFA's ownership is shared, and
442 /// thus not owned by this hybrid NFA/DFA. More practically, several regex
443 /// engines in this crate embed an NFA, and reporting the NFA's memory
444 /// usage in all of them would likely result in reporting higher heap
445 /// memory than is actually used.
446 pub fn memory_usage(&self) -> usize {
447 // The only thing that uses heap memory in a DFA is the NFA. But the
448 // NFA has shared ownership, so reporting its memory as part of the
449 // hybrid DFA is likely to lead to double-counting the NFA memory
450 // somehow. In particular, this DFA does not really own an NFA, so
451 // including it in the DFA's memory usage doesn't seem semantically
452 // correct.
453 0
454 }
455 }
456
457 impl DFA {
458 /// Executes a forward search and returns the end position of the leftmost
459 /// match that is found. If no match exists, then `None` is returned.
460 ///
461 /// In particular, this method continues searching even after it enters
462 /// a match state. The search only terminates once it has reached the
463 /// end of the input or when it has entered a dead or quit state. Upon
464 /// termination, the position of the last byte seen while still in a match
465 /// state is returned.
466 ///
467 /// # Errors
468 ///
469 /// This routine errors if the search could not complete. This can occur
470 /// in a number of circumstances:
471 ///
472 /// * The configuration of the lazy DFA may permit it to "quit" the search.
473 /// For example, setting quit bytes or enabling heuristic support for
474 /// Unicode word boundaries. The default configuration does not enable any
475 /// option that could result in the lazy DFA quitting.
476 /// * The configuration of the lazy DFA may also permit it to "give up"
477 /// on a search if it makes ineffective use of its transition table
478 /// cache. The default configuration does not enable this by default,
479 /// although it is typically a good idea to.
480 /// * When the provided `Input` configuration is not supported. For
481 /// example, by providing an unsupported anchor mode.
482 ///
483 /// When a search returns an error, callers cannot know whether a match
484 /// exists or not.
485 ///
486 /// # Example
487 ///
488 /// This example shows how to run a basic search.
489 ///
490 /// ```
491 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
492 ///
493 /// let dfa = DFA::new("foo[0-9]+")?;
494 /// let mut cache = dfa.create_cache();
495 /// let expected = HalfMatch::must(0, 8);
496 /// assert_eq!(Some(expected), dfa.try_search_fwd(
497 /// &mut cache, &Input::new("foo12345"))?,
498 /// );
499 ///
500 /// // Even though a match is found after reading the first byte (`a`),
501 /// // the leftmost first match semantics demand that we find the earliest
502 /// // match that prefers earlier parts of the pattern over later parts.
503 /// let dfa = DFA::new("abc|a")?;
504 /// let mut cache = dfa.create_cache();
505 /// let expected = HalfMatch::must(0, 3);
506 /// assert_eq!(Some(expected), dfa.try_search_fwd(
507 /// &mut cache, &Input::new("abc"))?,
508 /// );
509 ///
510 /// # Ok::<(), Box<dyn std::error::Error>>(())
511 /// ```
512 ///
513 /// # Example: specific pattern search
514 ///
515 /// This example shows how to build a lazy multi-DFA that permits searching
516 /// for specific patterns.
517 ///
518 /// ```
519 /// use regex_automata::{
520 /// hybrid::dfa::DFA,
521 /// Anchored, HalfMatch, PatternID, Input,
522 /// };
523 ///
524 /// let dfa = DFA::builder()
525 /// .configure(DFA::config().starts_for_each_pattern(true))
526 /// .build_many(&["[a-z0-9]{6}", "[a-z][a-z0-9]{5}"])?;
527 /// let mut cache = dfa.create_cache();
528 /// let haystack = "foo123";
529 ///
530 /// // Since we are using the default leftmost-first match and both
531 /// // patterns match at the same starting position, only the first pattern
532 /// // will be returned in this case when doing a search for any of the
533 /// // patterns.
534 /// let expected = Some(HalfMatch::must(0, 6));
535 /// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack))?;
536 /// assert_eq!(expected, got);
537 ///
538 /// // But if we want to check whether some other pattern matches, then we
539 /// // can provide its pattern ID.
540 /// let expected = Some(HalfMatch::must(1, 6));
541 /// let input = Input::new(haystack)
542 /// .anchored(Anchored::Pattern(PatternID::must(1)));
543 /// let got = dfa.try_search_fwd(&mut cache, &input)?;
544 /// assert_eq!(expected, got);
545 ///
546 /// # Ok::<(), Box<dyn std::error::Error>>(())
547 /// ```
548 ///
549 /// # Example: specifying the bounds of a search
550 ///
551 /// This example shows how providing the bounds of a search can produce
552 /// different results than simply sub-slicing the haystack.
553 ///
554 /// ```
555 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
556 ///
557 /// // N.B. We disable Unicode here so that we use a simple ASCII word
558 /// // boundary. Alternatively, we could enable heuristic support for
559 /// // Unicode word boundaries since our haystack is pure ASCII.
560 /// let dfa = DFA::new(r"(?-u)\b[0-9]{3}\b")?;
561 /// let mut cache = dfa.create_cache();
562 /// let haystack = "foo123bar";
563 ///
564 /// // Since we sub-slice the haystack, the search doesn't know about the
565 /// // larger context and assumes that `123` is surrounded by word
566 /// // boundaries. And of course, the match position is reported relative
567 /// // to the sub-slice as well, which means we get `3` instead of `6`.
568 /// let expected = Some(HalfMatch::must(0, 3));
569 /// let got = dfa.try_search_fwd(
570 /// &mut cache,
571 /// &Input::new(&haystack[3..6]),
572 /// )?;
573 /// assert_eq!(expected, got);
574 ///
575 /// // But if we provide the bounds of the search within the context of the
576 /// // entire haystack, then the search can take the surrounding context
577 /// // into account. (And if we did find a match, it would be reported
578 /// // as a valid offset into `haystack` instead of its sub-slice.)
579 /// let expected = None;
580 /// let got = dfa.try_search_fwd(
581 /// &mut cache,
582 /// &Input::new(haystack).range(3..6),
583 /// )?;
584 /// assert_eq!(expected, got);
585 ///
586 /// # Ok::<(), Box<dyn std::error::Error>>(())
587 /// ```
588 #[inline]
589 pub fn try_search_fwd(
590 &self,
591 cache: &mut Cache,
592 input: &Input<'_>,
593 ) -> Result<Option<HalfMatch>, MatchError> {
594 let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
595 let hm = match search::find_fwd(self, cache, input)? {
596 None => return Ok(None),
597 Some(hm) if !utf8empty => return Ok(Some(hm)),
598 Some(hm) => hm,
599 };
600 // We get to this point when we know our DFA can match the empty string
601 // AND when UTF-8 mode is enabled. In this case, we skip any matches
602 // whose offset splits a codepoint. Such a match is necessarily a
603 // zero-width match, because UTF-8 mode requires the underlying NFA
604 // to be built such that all non-empty matches span valid UTF-8.
605 // Therefore, any match that ends in the middle of a codepoint cannot
606 // be part of a span of valid UTF-8 and thus must be an empty match.
607 // In such cases, we skip it, so as not to report matches that split a
608 // codepoint.
609 //
610 // Note that this is not a checked assumption. Callers *can* provide an
611 // NFA with UTF-8 mode enabled but produces non-empty matches that span
612 // invalid UTF-8. But doing so is documented to result in unspecified
613 // behavior.
614 empty::skip_splits_fwd(input, hm, hm.offset(), |input| {
615 let got = search::find_fwd(self, cache, input)?;
616 Ok(got.map(|hm| (hm, hm.offset())))
617 })
618 }
619
620 /// Executes a reverse search and returns the start of the position of the
621 /// leftmost match that is found. If no match exists, then `None` is
622 /// returned.
623 ///
624 /// # Errors
625 ///
626 /// This routine errors if the search could not complete. This can occur
627 /// in a number of circumstances:
628 ///
629 /// * The configuration of the lazy DFA may permit it to "quit" the search.
630 /// For example, setting quit bytes or enabling heuristic support for
631 /// Unicode word boundaries. The default configuration does not enable any
632 /// option that could result in the lazy DFA quitting.
633 /// * The configuration of the lazy DFA may also permit it to "give up"
634 /// on a search if it makes ineffective use of its transition table
635 /// cache. The default configuration does not enable this by default,
636 /// although it is typically a good idea to.
637 /// * When the provided `Input` configuration is not supported. For
638 /// example, by providing an unsupported anchor mode.
639 ///
640 /// When a search returns an error, callers cannot know whether a match
641 /// exists or not.
642 ///
643 /// # Example
644 ///
645 /// This routine is principally useful when used in
646 /// conjunction with the
647 /// [`nfa::thompson::Config::reverse`](crate::nfa::thompson::Config::reverse)
648 /// configuration. In general, it's unlikely to be correct to use both
649 /// `try_search_fwd` and `try_search_rev` with the same DFA since any
650 /// particular DFA will only support searching in one direction with
651 /// respect to the pattern.
652 ///
653 /// ```
654 /// use regex_automata::{
655 /// nfa::thompson,
656 /// hybrid::dfa::DFA,
657 /// HalfMatch, Input,
658 /// };
659 ///
660 /// let dfa = DFA::builder()
661 /// .thompson(thompson::Config::new().reverse(true))
662 /// .build("foo[0-9]+")?;
663 /// let mut cache = dfa.create_cache();
664 /// let expected = HalfMatch::must(0, 0);
665 /// assert_eq!(
666 /// Some(expected),
667 /// dfa.try_search_rev(&mut cache, &Input::new("foo12345"))?,
668 /// );
669 ///
670 /// // Even though a match is found after reading the last byte (`c`),
671 /// // the leftmost first match semantics demand that we find the earliest
672 /// // match that prefers earlier parts of the pattern over latter parts.
673 /// let dfa = DFA::builder()
674 /// .thompson(thompson::Config::new().reverse(true))
675 /// .build("abc|c")?;
676 /// let mut cache = dfa.create_cache();
677 /// let expected = HalfMatch::must(0, 0);
678 /// assert_eq!(Some(expected), dfa.try_search_rev(
679 /// &mut cache, &Input::new("abc"))?,
680 /// );
681 ///
682 /// # Ok::<(), Box<dyn std::error::Error>>(())
683 /// ```
684 ///
685 /// # Example: UTF-8 mode
686 ///
687 /// This examples demonstrates that UTF-8 mode applies to reverse
688 /// DFAs. When UTF-8 mode is enabled in the underlying NFA, then all
689 /// matches reported must correspond to valid UTF-8 spans. This includes
690 /// prohibiting zero-width matches that split a codepoint.
691 ///
692 /// UTF-8 mode is enabled by default. Notice below how the only zero-width
693 /// matches reported are those at UTF-8 boundaries:
694 ///
695 /// ```
696 /// use regex_automata::{
697 /// hybrid::dfa::DFA,
698 /// nfa::thompson,
699 /// HalfMatch, Input, MatchKind,
700 /// };
701 ///
702 /// let dfa = DFA::builder()
703 /// .thompson(thompson::Config::new().reverse(true))
704 /// .build(r"")?;
705 /// let mut cache = dfa.create_cache();
706 ///
707 /// // Run the reverse DFA to collect all matches.
708 /// let mut input = Input::new("☃");
709 /// let mut matches = vec![];
710 /// loop {
711 /// match dfa.try_search_rev(&mut cache, &input)? {
712 /// None => break,
713 /// Some(hm) => {
714 /// matches.push(hm);
715 /// if hm.offset() == 0 || input.end() == 0 {
716 /// break;
717 /// } else if hm.offset() < input.end() {
718 /// input.set_end(hm.offset());
719 /// } else {
720 /// // This is only necessary to handle zero-width
721 /// // matches, which of course occur in this example.
722 /// // Without this, the search would never advance
723 /// // backwards beyond the initial match.
724 /// input.set_end(input.end() - 1);
725 /// }
726 /// }
727 /// }
728 /// }
729 ///
730 /// // No matches split a codepoint.
731 /// let expected = vec![
732 /// HalfMatch::must(0, 3),
733 /// HalfMatch::must(0, 0),
734 /// ];
735 /// assert_eq!(expected, matches);
736 ///
737 /// # Ok::<(), Box<dyn std::error::Error>>(())
738 /// ```
739 ///
740 /// Now let's look at the same example, but with UTF-8 mode on the
741 /// underlying NFA disabled:
742 ///
743 /// ```
744 /// use regex_automata::{
745 /// hybrid::dfa::DFA,
746 /// nfa::thompson,
747 /// HalfMatch, Input, MatchKind,
748 /// };
749 ///
750 /// let dfa = DFA::builder()
751 /// .thompson(thompson::Config::new().reverse(true).utf8(false))
752 /// .build(r"")?;
753 /// let mut cache = dfa.create_cache();
754 ///
755 /// // Run the reverse DFA to collect all matches.
756 /// let mut input = Input::new("☃");
757 /// let mut matches = vec![];
758 /// loop {
759 /// match dfa.try_search_rev(&mut cache, &input)? {
760 /// None => break,
761 /// Some(hm) => {
762 /// matches.push(hm);
763 /// if hm.offset() == 0 || input.end() == 0 {
764 /// break;
765 /// } else if hm.offset() < input.end() {
766 /// input.set_end(hm.offset());
767 /// } else {
768 /// // This is only necessary to handle zero-width
769 /// // matches, which of course occur in this example.
770 /// // Without this, the search would never advance
771 /// // backwards beyond the initial match.
772 /// input.set_end(input.end() - 1);
773 /// }
774 /// }
775 /// }
776 /// }
777 ///
778 /// // No matches split a codepoint.
779 /// let expected = vec![
780 /// HalfMatch::must(0, 3),
781 /// HalfMatch::must(0, 2),
782 /// HalfMatch::must(0, 1),
783 /// HalfMatch::must(0, 0),
784 /// ];
785 /// assert_eq!(expected, matches);
786 ///
787 /// # Ok::<(), Box<dyn std::error::Error>>(())
788 /// ```
789 #[inline]
790 pub fn try_search_rev(
791 &self,
792 cache: &mut Cache,
793 input: &Input<'_>,
794 ) -> Result<Option<HalfMatch>, MatchError> {
795 let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
796 let hm = match search::find_rev(self, cache, input)? {
797 None => return Ok(None),
798 Some(hm) if !utf8empty => return Ok(Some(hm)),
799 Some(hm) => hm,
800 };
801 empty::skip_splits_rev(input, hm, hm.offset(), |input| {
802 let got = search::find_rev(self, cache, input)?;
803 Ok(got.map(|hm| (hm, hm.offset())))
804 })
805 }
806
807 /// Executes an overlapping forward search and returns the end position of
808 /// matches as they are found. If no match exists, then `None` is returned.
809 ///
810 /// This routine is principally only useful when searching for multiple
811 /// patterns on inputs where multiple patterns may match the same regions
812 /// of text. In particular, callers must preserve the automaton's search
813 /// state from prior calls so that the implementation knows where the last
814 /// match occurred.
815 ///
816 /// When using this routine to implement an iterator of overlapping
817 /// matches, the `start` of the search should remain invariant throughout
818 /// iteration. The `OverlappingState` given to the search will keep track
819 /// of the current position of the search. (This is because multiple
820 /// matches may be reported at the same position, so only the search
821 /// implementation itself knows when to advance the position.)
822 ///
823 /// If for some reason you want the search to forget about its previous
824 /// state and restart the search at a particular position, then setting the
825 /// state to [`OverlappingState::start`] will accomplish that.
826 ///
827 /// # Errors
828 ///
829 /// This routine errors if the search could not complete. This can occur
830 /// in a number of circumstances:
831 ///
832 /// * The configuration of the lazy DFA may permit it to "quit" the search.
833 /// For example, setting quit bytes or enabling heuristic support for
834 /// Unicode word boundaries. The default configuration does not enable any
835 /// option that could result in the lazy DFA quitting.
836 /// * The configuration of the lazy DFA may also permit it to "give up"
837 /// on a search if it makes ineffective use of its transition table
838 /// cache. The default configuration does not enable this by default,
839 /// although it is typically a good idea to.
840 /// * When the provided `Input` configuration is not supported. For
841 /// example, by providing an unsupported anchor mode.
842 ///
843 /// When a search returns an error, callers cannot know whether a match
844 /// exists or not.
845 ///
846 /// # Example
847 ///
848 /// This example shows how to run a basic overlapping search. Notice
849 /// that we build the automaton with a `MatchKind::All` configuration.
850 /// Overlapping searches are unlikely to work as one would expect when
851 /// using the default `MatchKind::LeftmostFirst` match semantics, since
852 /// leftmost-first matching is fundamentally incompatible with overlapping
853 /// searches. Namely, overlapping searches need to report matches as they
854 /// are seen, where as leftmost-first searches will continue searching even
855 /// after a match has been observed in order to find the conventional end
856 /// position of the match. More concretely, leftmost-first searches use
857 /// dead states to terminate a search after a specific match can no longer
858 /// be extended. Overlapping searches instead do the opposite by continuing
859 /// the search to find totally new matches (potentially of other patterns).
860 ///
861 /// ```
862 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
863 /// use regex_automata::{
864 /// hybrid::dfa::{DFA, OverlappingState},
865 /// HalfMatch, Input, MatchKind,
866 /// };
867 ///
868 /// let dfa = DFA::builder()
869 /// .configure(DFA::config().match_kind(MatchKind::All))
870 /// .build_many(&[r"\w+$", r"\S+$"])?;
871 /// let mut cache = dfa.create_cache();
872 ///
873 /// let haystack = "@foo";
874 /// let mut state = OverlappingState::start();
875 ///
876 /// let expected = Some(HalfMatch::must(1, 4));
877 /// dfa.try_search_overlapping_fwd(
878 /// &mut cache, &Input::new(haystack), &mut state,
879 /// )?;
880 /// assert_eq!(expected, state.get_match());
881 ///
882 /// // The first pattern also matches at the same position, so re-running
883 /// // the search will yield another match. Notice also that the first
884 /// // pattern is returned after the second. This is because the second
885 /// // pattern begins its match before the first, is therefore an earlier
886 /// // match and is thus reported first.
887 /// let expected = Some(HalfMatch::must(0, 4));
888 /// dfa.try_search_overlapping_fwd(
889 /// &mut cache, &Input::new(haystack), &mut state,
890 /// )?;
891 /// assert_eq!(expected, state.get_match());
892 ///
893 /// # Ok::<(), Box<dyn std::error::Error>>(())
894 /// ```
895 #[inline]
896 pub fn try_search_overlapping_fwd(
897 &self,
898 cache: &mut Cache,
899 input: &Input<'_>,
900 state: &mut OverlappingState,
901 ) -> Result<(), MatchError> {
902 let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
903 search::find_overlapping_fwd(self, cache, input, state)?;
904 match state.get_match() {
905 None => Ok(()),
906 Some(_) if !utf8empty => Ok(()),
907 Some(_) => skip_empty_utf8_splits_overlapping(
908 input,
909 state,
910 |input, state| {
911 search::find_overlapping_fwd(self, cache, input, state)
912 },
913 ),
914 }
915 }
916
917 /// Executes a reverse overlapping search and returns the start of the
918 /// position of the leftmost match that is found. If no match exists, then
919 /// `None` is returned.
920 ///
921 /// When using this routine to implement an iterator of overlapping
922 /// matches, the `start` of the search should remain invariant throughout
923 /// iteration. The `OverlappingState` given to the search will keep track
924 /// of the current position of the search. (This is because multiple
925 /// matches may be reported at the same position, so only the search
926 /// implementation itself knows when to advance the position.)
927 ///
928 /// If for some reason you want the search to forget about its previous
929 /// state and restart the search at a particular position, then setting the
930 /// state to [`OverlappingState::start`] will accomplish that.
931 ///
932 /// # Errors
933 ///
934 /// This routine errors if the search could not complete. This can occur
935 /// in a number of circumstances:
936 ///
937 /// * The configuration of the lazy DFA may permit it to "quit" the search.
938 /// For example, setting quit bytes or enabling heuristic support for
939 /// Unicode word boundaries. The default configuration does not enable any
940 /// option that could result in the lazy DFA quitting.
941 /// * The configuration of the lazy DFA may also permit it to "give up"
942 /// on a search if it makes ineffective use of its transition table
943 /// cache. The default configuration does not enable this by default,
944 /// although it is typically a good idea to.
945 /// * When the provided `Input` configuration is not supported. For
946 /// example, by providing an unsupported anchor mode.
947 ///
948 /// When a search returns an error, callers cannot know whether a match
949 /// exists or not.
950 ///
951 /// # Example: UTF-8 mode
952 ///
953 /// This examples demonstrates that UTF-8 mode applies to reverse
954 /// DFAs. When UTF-8 mode is enabled in the underlying NFA, then all
955 /// matches reported must correspond to valid UTF-8 spans. This includes
956 /// prohibiting zero-width matches that split a codepoint.
957 ///
958 /// UTF-8 mode is enabled by default. Notice below how the only zero-width
959 /// matches reported are those at UTF-8 boundaries:
960 ///
961 /// ```
962 /// use regex_automata::{
963 /// hybrid::dfa::{DFA, OverlappingState},
964 /// nfa::thompson,
965 /// HalfMatch, Input, MatchKind,
966 /// };
967 ///
968 /// let dfa = DFA::builder()
969 /// .configure(DFA::config().match_kind(MatchKind::All))
970 /// .thompson(thompson::Config::new().reverse(true))
971 /// .build_many(&[r"", r"☃"])?;
972 /// let mut cache = dfa.create_cache();
973 ///
974 /// // Run the reverse DFA to collect all matches.
975 /// let input = Input::new("☃");
976 /// let mut state = OverlappingState::start();
977 /// let mut matches = vec![];
978 /// loop {
979 /// dfa.try_search_overlapping_rev(&mut cache, &input, &mut state)?;
980 /// match state.get_match() {
981 /// None => break,
982 /// Some(hm) => matches.push(hm),
983 /// }
984 /// }
985 ///
986 /// // No matches split a codepoint.
987 /// let expected = vec![
988 /// HalfMatch::must(0, 3),
989 /// HalfMatch::must(1, 0),
990 /// HalfMatch::must(0, 0),
991 /// ];
992 /// assert_eq!(expected, matches);
993 ///
994 /// # Ok::<(), Box<dyn std::error::Error>>(())
995 /// ```
996 ///
997 /// Now let's look at the same example, but with UTF-8 mode on the
998 /// underlying NFA disabled:
999 ///
1000 /// ```
1001 /// use regex_automata::{
1002 /// hybrid::dfa::{DFA, OverlappingState},
1003 /// nfa::thompson,
1004 /// HalfMatch, Input, MatchKind,
1005 /// };
1006 ///
1007 /// let dfa = DFA::builder()
1008 /// .configure(DFA::config().match_kind(MatchKind::All))
1009 /// .thompson(thompson::Config::new().reverse(true).utf8(false))
1010 /// .build_many(&[r"", r"☃"])?;
1011 /// let mut cache = dfa.create_cache();
1012 ///
1013 /// // Run the reverse DFA to collect all matches.
1014 /// let input = Input::new("☃");
1015 /// let mut state = OverlappingState::start();
1016 /// let mut matches = vec![];
1017 /// loop {
1018 /// dfa.try_search_overlapping_rev(&mut cache, &input, &mut state)?;
1019 /// match state.get_match() {
1020 /// None => break,
1021 /// Some(hm) => matches.push(hm),
1022 /// }
1023 /// }
1024 ///
1025 /// // Now *all* positions match, even within a codepoint,
1026 /// // because we lifted the requirement that matches
1027 /// // correspond to valid UTF-8 spans.
1028 /// let expected = vec![
1029 /// HalfMatch::must(0, 3),
1030 /// HalfMatch::must(0, 2),
1031 /// HalfMatch::must(0, 1),
1032 /// HalfMatch::must(1, 0),
1033 /// HalfMatch::must(0, 0),
1034 /// ];
1035 /// assert_eq!(expected, matches);
1036 ///
1037 /// # Ok::<(), Box<dyn std::error::Error>>(())
1038 /// ```
1039 #[inline]
1040 pub fn try_search_overlapping_rev(
1041 &self,
1042 cache: &mut Cache,
1043 input: &Input<'_>,
1044 state: &mut OverlappingState,
1045 ) -> Result<(), MatchError> {
1046 let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
1047 search::find_overlapping_rev(self, cache, input, state)?;
1048 match state.get_match() {
1049 None => Ok(()),
1050 Some(_) if !utf8empty => Ok(()),
1051 Some(_) => skip_empty_utf8_splits_overlapping(
1052 input,
1053 state,
1054 |input, state| {
1055 search::find_overlapping_rev(self, cache, input, state)
1056 },
1057 ),
1058 }
1059 }
1060
1061 /// Writes the set of patterns that match anywhere in the given search
1062 /// configuration to `patset`. If multiple patterns match at the same
1063 /// position and the underlying DFA supports overlapping matches, then all
1064 /// matching patterns are written to the given set.
1065 ///
1066 /// Unless all of the patterns in this DFA are anchored, then generally
1067 /// speaking, this will visit every byte in the haystack.
1068 ///
1069 /// This search routine *does not* clear the pattern set. This gives some
1070 /// flexibility to the caller (e.g., running multiple searches with the
1071 /// same pattern set), but does make the API bug-prone if you're reusing
1072 /// the same pattern set for multiple searches but intended them to be
1073 /// independent.
1074 ///
1075 /// If a pattern ID matched but the given `PatternSet` does not have
1076 /// sufficient capacity to store it, then it is not inserted and silently
1077 /// dropped.
1078 ///
1079 /// # Errors
1080 ///
1081 /// This routine errors if the search could not complete. This can occur
1082 /// in a number of circumstances:
1083 ///
1084 /// * The configuration of the lazy DFA may permit it to "quit" the search.
1085 /// For example, setting quit bytes or enabling heuristic support for
1086 /// Unicode word boundaries. The default configuration does not enable any
1087 /// option that could result in the lazy DFA quitting.
1088 /// * The configuration of the lazy DFA may also permit it to "give up"
1089 /// on a search if it makes ineffective use of its transition table
1090 /// cache. The default configuration does not enable this by default,
1091 /// although it is typically a good idea to.
1092 /// * When the provided `Input` configuration is not supported. For
1093 /// example, by providing an unsupported anchor mode.
1094 ///
1095 /// When a search returns an error, callers cannot know whether a match
1096 /// exists or not.
1097 ///
1098 /// # Example
1099 ///
1100 /// This example shows how to find all matching patterns in a haystack,
1101 /// even when some patterns match at the same position as other patterns.
1102 ///
1103 /// ```
1104 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
1105 /// use regex_automata::{
1106 /// hybrid::dfa::DFA,
1107 /// Input, MatchKind, PatternSet,
1108 /// };
1109 ///
1110 /// let patterns = &[
1111 /// r"\w+", r"\d+", r"\pL+", r"foo", r"bar", r"barfoo", r"foobar",
1112 /// ];
1113 /// let dfa = DFA::builder()
1114 /// .configure(DFA::config().match_kind(MatchKind::All))
1115 /// .build_many(patterns)?;
1116 /// let mut cache = dfa.create_cache();
1117 ///
1118 /// let input = Input::new("foobar");
1119 /// let mut patset = PatternSet::new(dfa.pattern_len());
1120 /// dfa.try_which_overlapping_matches(&mut cache, &input, &mut patset)?;
1121 /// let expected = vec![0, 2, 3, 4, 6];
1122 /// let got: Vec<usize> = patset.iter().map(|p| p.as_usize()).collect();
1123 /// assert_eq!(expected, got);
1124 ///
1125 /// # Ok::<(), Box<dyn std::error::Error>>(())
1126 /// ```
1127 #[inline]
1128 pub fn try_which_overlapping_matches(
1129 &self,
1130 cache: &mut Cache,
1131 input: &Input<'_>,
1132 patset: &mut PatternSet,
1133 ) -> Result<(), MatchError> {
1134 let mut state = OverlappingState::start();
1135 while let Some(m) = {
1136 self.try_search_overlapping_fwd(cache, input, &mut state)?;
1137 state.get_match()
1138 } {
1139 let _ = patset.try_insert(m.pattern());
1140 // There's nothing left to find, so we can stop. Or the caller
1141 // asked us to.
1142 if patset.is_full() || input.get_earliest() {
1143 break;
1144 }
1145 }
1146 Ok(())
1147 }
1148 }
1149
1150 impl DFA {
1151 /// Transitions from the current state to the next state, given the next
1152 /// byte of input.
1153 ///
1154 /// The given cache is used to either reuse pre-computed state
1155 /// transitions, or to store this newly computed transition for future
1156 /// reuse. Thus, this routine guarantees that it will never return a state
1157 /// ID that has an "unknown" tag.
1158 ///
1159 /// # State identifier validity
1160 ///
1161 /// The only valid value for `current` is the lazy state ID returned
1162 /// by the most recent call to `next_state`, `next_state_untagged`,
1163 /// `next_state_untagged_unchecked`, `start_state_forward` or
1164 /// `state_state_reverse` for the given `cache`. Any state ID returned from
1165 /// prior calls to these routines (with the same `cache`) is considered
1166 /// invalid (even if it gives an appearance of working). State IDs returned
1167 /// from _any_ prior call for different `cache` values are also always
1168 /// invalid.
1169 ///
1170 /// The returned ID is always a valid ID when `current` refers to a valid
1171 /// ID. Moreover, this routine is defined for all possible values of
1172 /// `input`.
1173 ///
1174 /// These validity rules are not checked, even in debug mode. Callers are
1175 /// required to uphold these rules themselves.
1176 ///
1177 /// Violating these state ID validity rules will not sacrifice memory
1178 /// safety, but _may_ produce an incorrect result or a panic.
1179 ///
1180 /// # Panics
1181 ///
1182 /// If the given ID does not refer to a valid state, then this routine
1183 /// may panic but it also may not panic and instead return an invalid or
1184 /// incorrect ID.
1185 ///
1186 /// # Example
1187 ///
1188 /// This shows a simplistic example for walking a lazy DFA for a given
1189 /// haystack by using the `next_state` method.
1190 ///
1191 /// ```
1192 /// use regex_automata::{hybrid::dfa::DFA, Input};
1193 ///
1194 /// let dfa = DFA::new(r"[a-z]+r")?;
1195 /// let mut cache = dfa.create_cache();
1196 /// let haystack = "bar".as_bytes();
1197 ///
1198 /// // The start state is determined by inspecting the position and the
1199 /// // initial bytes of the haystack.
1200 /// let mut sid = dfa.start_state_forward(
1201 /// &mut cache, &Input::new(haystack),
1202 /// )?;
1203 /// // Walk all the bytes in the haystack.
1204 /// for &b in haystack {
1205 /// sid = dfa.next_state(&mut cache, sid, b)?;
1206 /// }
1207 /// // Matches are always delayed by 1 byte, so we must explicitly walk the
1208 /// // special "EOI" transition at the end of the search.
1209 /// sid = dfa.next_eoi_state(&mut cache, sid)?;
1210 /// assert!(sid.is_match());
1211 ///
1212 /// # Ok::<(), Box<dyn std::error::Error>>(())
1213 /// ```
1214 #[inline]
1215 pub fn next_state(
1216 &self,
1217 cache: &mut Cache,
1218 current: LazyStateID,
1219 input: u8,
1220 ) -> Result<LazyStateID, CacheError> {
1221 let class = usize::from(self.classes.get(input));
1222 let offset = current.as_usize_untagged() + class;
1223 let sid = cache.trans[offset];
1224 if !sid.is_unknown() {
1225 return Ok(sid);
1226 }
1227 let unit = alphabet::Unit::u8(input);
1228 Lazy::new(self, cache).cache_next_state(current, unit)
1229 }
1230
1231 /// Transitions from the current state to the next state, given the next
1232 /// byte of input and a state ID that is not tagged.
1233 ///
1234 /// The only reason to use this routine is performance. In particular, the
1235 /// `next_state` method needs to do some additional checks, among them is
1236 /// to account for identifiers to states that are not yet computed. In
1237 /// such a case, the transition is computed on the fly. However, if it is
1238 /// known that the `current` state ID is untagged, then these checks can be
1239 /// omitted.
1240 ///
1241 /// Since this routine does not compute states on the fly, it does not
1242 /// modify the cache and thus cannot return an error. Consequently, `cache`
1243 /// does not need to be mutable and it is possible for this routine to
1244 /// return a state ID corresponding to the special "unknown" state. In
1245 /// this case, it is the caller's responsibility to use the prior state
1246 /// ID and `input` with `next_state` in order to force the computation of
1247 /// the unknown transition. Otherwise, trying to use the "unknown" state
1248 /// ID will just result in transitioning back to itself, and thus never
1249 /// terminating. (This is technically a special exemption to the state ID
1250 /// validity rules, but is permissible since this routine is guarateed to
1251 /// never mutate the given `cache`, and thus the identifier is guaranteed
1252 /// to remain valid.)
1253 ///
1254 /// See [`LazyStateID`] for more details on what it means for a state ID
1255 /// to be tagged. Also, see
1256 /// [`next_state_untagged_unchecked`](DFA::next_state_untagged_unchecked)
1257 /// for this same idea, but with bounds checks forcefully elided.
1258 ///
1259 /// # State identifier validity
1260 ///
1261 /// The only valid value for `current` is an **untagged** lazy
1262 /// state ID returned by the most recent call to `next_state`,
1263 /// `next_state_untagged`, `next_state_untagged_unchecked`,
1264 /// `start_state_forward` or `state_state_reverse` for the given `cache`.
1265 /// Any state ID returned from prior calls to these routines (with the
1266 /// same `cache`) is considered invalid (even if it gives an appearance
1267 /// of working). State IDs returned from _any_ prior call for different
1268 /// `cache` values are also always invalid.
1269 ///
1270 /// The returned ID is always a valid ID when `current` refers to a valid
1271 /// ID, although it may be tagged. Moreover, this routine is defined for
1272 /// all possible values of `input`.
1273 ///
1274 /// Not all validity rules are checked, even in debug mode. Callers are
1275 /// required to uphold these rules themselves.
1276 ///
1277 /// Violating these state ID validity rules will not sacrifice memory
1278 /// safety, but _may_ produce an incorrect result or a panic.
1279 ///
1280 /// # Panics
1281 ///
1282 /// If the given ID does not refer to a valid state, then this routine
1283 /// may panic but it also may not panic and instead return an invalid or
1284 /// incorrect ID.
1285 ///
1286 /// # Example
1287 ///
1288 /// This shows a simplistic example for walking a lazy DFA for a given
1289 /// haystack by using the `next_state_untagged` method where possible.
1290 ///
1291 /// ```
1292 /// use regex_automata::{hybrid::dfa::DFA, Input};
1293 ///
1294 /// let dfa = DFA::new(r"[a-z]+r")?;
1295 /// let mut cache = dfa.create_cache();
1296 /// let haystack = "bar".as_bytes();
1297 ///
1298 /// // The start state is determined by inspecting the position and the
1299 /// // initial bytes of the haystack.
1300 /// let mut sid = dfa.start_state_forward(
1301 /// &mut cache, &Input::new(haystack),
1302 /// )?;
1303 /// // Walk all the bytes in the haystack.
1304 /// let mut at = 0;
1305 /// while at < haystack.len() {
1306 /// if sid.is_tagged() {
1307 /// sid = dfa.next_state(&mut cache, sid, haystack[at])?;
1308 /// } else {
1309 /// let mut prev_sid = sid;
1310 /// // We attempt to chew through as much as we can while moving
1311 /// // through untagged state IDs. Thus, the transition function
1312 /// // does less work on average per byte. (Unrolling this loop
1313 /// // may help even more.)
1314 /// while at < haystack.len() {
1315 /// prev_sid = sid;
1316 /// sid = dfa.next_state_untagged(
1317 /// &mut cache, sid, haystack[at],
1318 /// );
1319 /// at += 1;
1320 /// if sid.is_tagged() {
1321 /// break;
1322 /// }
1323 /// }
1324 /// // We must ensure that we never proceed to the next iteration
1325 /// // with an unknown state ID. If we don't account for this
1326 /// // case, then search isn't guaranteed to terminate since all
1327 /// // transitions on unknown states loop back to itself.
1328 /// if sid.is_unknown() {
1329 /// sid = dfa.next_state(
1330 /// &mut cache, prev_sid, haystack[at - 1],
1331 /// )?;
1332 /// }
1333 /// }
1334 /// }
1335 /// // Matches are always delayed by 1 byte, so we must explicitly walk the
1336 /// // special "EOI" transition at the end of the search.
1337 /// sid = dfa.next_eoi_state(&mut cache, sid)?;
1338 /// assert!(sid.is_match());
1339 ///
1340 /// # Ok::<(), Box<dyn std::error::Error>>(())
1341 /// ```
1342 #[inline]
1343 pub fn next_state_untagged(
1344 &self,
1345 cache: &Cache,
1346 current: LazyStateID,
1347 input: u8,
1348 ) -> LazyStateID {
1349 debug_assert!(!current.is_tagged());
1350 let class = usize::from(self.classes.get(input));
1351 let offset = current.as_usize_unchecked() + class;
1352 cache.trans[offset]
1353 }
1354
1355 /// Transitions from the current state to the next state, eliding bounds
1356 /// checks, given the next byte of input and a state ID that is not tagged.
1357 ///
1358 /// The only reason to use this routine is performance. In particular, the
1359 /// `next_state` method needs to do some additional checks, among them is
1360 /// to account for identifiers to states that are not yet computed. In
1361 /// such a case, the transition is computed on the fly. However, if it is
1362 /// known that the `current` state ID is untagged, then these checks can be
1363 /// omitted.
1364 ///
1365 /// Since this routine does not compute states on the fly, it does not
1366 /// modify the cache and thus cannot return an error. Consequently, `cache`
1367 /// does not need to be mutable and it is possible for this routine to
1368 /// return a state ID corresponding to the special "unknown" state. In
1369 /// this case, it is the caller's responsibility to use the prior state
1370 /// ID and `input` with `next_state` in order to force the computation of
1371 /// the unknown transition. Otherwise, trying to use the "unknown" state
1372 /// ID will just result in transitioning back to itself, and thus never
1373 /// terminating. (This is technically a special exemption to the state ID
1374 /// validity rules, but is permissible since this routine is guarateed to
1375 /// never mutate the given `cache`, and thus the identifier is guaranteed
1376 /// to remain valid.)
1377 ///
1378 /// See [`LazyStateID`] for more details on what it means for a state ID
1379 /// to be tagged. Also, see
1380 /// [`next_state_untagged`](DFA::next_state_untagged)
1381 /// for this same idea, but with memory safety guaranteed by retaining
1382 /// bounds checks.
1383 ///
1384 /// # State identifier validity
1385 ///
1386 /// The only valid value for `current` is an **untagged** lazy
1387 /// state ID returned by the most recent call to `next_state`,
1388 /// `next_state_untagged`, `next_state_untagged_unchecked`,
1389 /// `start_state_forward` or `state_state_reverse` for the given `cache`.
1390 /// Any state ID returned from prior calls to these routines (with the
1391 /// same `cache`) is considered invalid (even if it gives an appearance
1392 /// of working). State IDs returned from _any_ prior call for different
1393 /// `cache` values are also always invalid.
1394 ///
1395 /// The returned ID is always a valid ID when `current` refers to a valid
1396 /// ID, although it may be tagged. Moreover, this routine is defined for
1397 /// all possible values of `input`.
1398 ///
1399 /// Not all validity rules are checked, even in debug mode. Callers are
1400 /// required to uphold these rules themselves.
1401 ///
1402 /// Violating these state ID validity rules will not sacrifice memory
1403 /// safety, but _may_ produce an incorrect result or a panic.
1404 ///
1405 /// # Safety
1406 ///
1407 /// Callers of this method must guarantee that `current` refers to a valid
1408 /// state ID according to the rules described above. If `current` is not a
1409 /// valid state ID for this automaton, then calling this routine may result
1410 /// in undefined behavior.
1411 ///
1412 /// If `current` is valid, then the ID returned is valid for all possible
1413 /// values of `input`.
1414 #[inline]
1415 pub unsafe fn next_state_untagged_unchecked(
1416 &self,
1417 cache: &Cache,
1418 current: LazyStateID,
1419 input: u8,
1420 ) -> LazyStateID {
1421 debug_assert!(!current.is_tagged());
1422 let class = usize::from(self.classes.get(input));
1423 let offset = current.as_usize_unchecked() + class;
1424 *cache.trans.get_unchecked(offset)
1425 }
1426
1427 /// Transitions from the current state to the next state for the special
1428 /// EOI symbol.
1429 ///
1430 /// The given cache is used to either reuse pre-computed state
1431 /// transitions, or to store this newly computed transition for future
1432 /// reuse. Thus, this routine guarantees that it will never return a state
1433 /// ID that has an "unknown" tag.
1434 ///
1435 /// This routine must be called at the end of every search in a correct
1436 /// implementation of search. Namely, lazy DFAs in this crate delay matches
1437 /// by one byte in order to support look-around operators. Thus, after
1438 /// reaching the end of a haystack, a search implementation must follow one
1439 /// last EOI transition.
1440 ///
1441 /// It is best to think of EOI as an additional symbol in the alphabet of a
1442 /// DFA that is distinct from every other symbol. That is, the alphabet of
1443 /// lazy DFAs in this crate has a logical size of 257 instead of 256, where
1444 /// 256 corresponds to every possible inhabitant of `u8`. (In practice, the
1445 /// physical alphabet size may be smaller because of alphabet compression
1446 /// via equivalence classes, but EOI is always represented somehow in the
1447 /// alphabet.)
1448 ///
1449 /// # State identifier validity
1450 ///
1451 /// The only valid value for `current` is the lazy state ID returned
1452 /// by the most recent call to `next_state`, `next_state_untagged`,
1453 /// `next_state_untagged_unchecked`, `start_state_forward` or
1454 /// `state_state_reverse` for the given `cache`. Any state ID returned from
1455 /// prior calls to these routines (with the same `cache`) is considered
1456 /// invalid (even if it gives an appearance of working). State IDs returned
1457 /// from _any_ prior call for different `cache` values are also always
1458 /// invalid.
1459 ///
1460 /// The returned ID is always a valid ID when `current` refers to a valid
1461 /// ID.
1462 ///
1463 /// These validity rules are not checked, even in debug mode. Callers are
1464 /// required to uphold these rules themselves.
1465 ///
1466 /// Violating these state ID validity rules will not sacrifice memory
1467 /// safety, but _may_ produce an incorrect result or a panic.
1468 ///
1469 /// # Panics
1470 ///
1471 /// If the given ID does not refer to a valid state, then this routine
1472 /// may panic but it also may not panic and instead return an invalid or
1473 /// incorrect ID.
1474 ///
1475 /// # Example
1476 ///
1477 /// This shows a simplistic example for walking a DFA for a given haystack,
1478 /// and then finishing the search with the final EOI transition.
1479 ///
1480 /// ```
1481 /// use regex_automata::{hybrid::dfa::DFA, Input};
1482 ///
1483 /// let dfa = DFA::new(r"[a-z]+r")?;
1484 /// let mut cache = dfa.create_cache();
1485 /// let haystack = "bar".as_bytes();
1486 ///
1487 /// // The start state is determined by inspecting the position and the
1488 /// // initial bytes of the haystack.
1489 /// let mut sid = dfa.start_state_forward(
1490 /// &mut cache, &Input::new(haystack),
1491 /// )?;
1492 /// // Walk all the bytes in the haystack.
1493 /// for &b in haystack {
1494 /// sid = dfa.next_state(&mut cache, sid, b)?;
1495 /// }
1496 /// // Matches are always delayed by 1 byte, so we must explicitly walk
1497 /// // the special "EOI" transition at the end of the search. Without this
1498 /// // final transition, the assert below will fail since the DFA will not
1499 /// // have entered a match state yet!
1500 /// sid = dfa.next_eoi_state(&mut cache, sid)?;
1501 /// assert!(sid.is_match());
1502 ///
1503 /// # Ok::<(), Box<dyn std::error::Error>>(())
1504 /// ```
1505 #[inline]
1506 pub fn next_eoi_state(
1507 &self,
1508 cache: &mut Cache,
1509 current: LazyStateID,
1510 ) -> Result<LazyStateID, CacheError> {
1511 let eoi = self.classes.eoi().as_usize();
1512 let offset = current.as_usize_untagged() + eoi;
1513 let sid = cache.trans[offset];
1514 if !sid.is_unknown() {
1515 return Ok(sid);
1516 }
1517 let unit = self.classes.eoi();
1518 Lazy::new(self, cache).cache_next_state(current, unit)
1519 }
1520
1521 /// Return the ID of the start state for this lazy DFA when executing a
1522 /// forward search.
1523 ///
1524 /// Unlike typical DFA implementations, the start state for DFAs in this
1525 /// crate is dependent on a few different factors:
1526 ///
1527 /// * The [`Anchored`] mode of the search. Unanchored, anchored and
1528 /// anchored searches for a specific [`PatternID`] all use different start
1529 /// states.
1530 /// * The position at which the search begins, via [`Input::start`]. This
1531 /// and the byte immediately preceding the start of the search (if one
1532 /// exists) influence which look-behind assertions are true at the start
1533 /// of the search. This in turn influences which start state is selected.
1534 /// * Whether the search is a forward or reverse search. This routine can
1535 /// only be used for forward searches.
1536 ///
1537 /// # Errors
1538 ///
1539 /// This may return a [`MatchError`] (not a [`CacheError`]!) if the search
1540 /// needs to give up when determining the start state (for example, if
1541 /// it sees a "quit" byte or if the cache has been cleared too many
1542 /// times). This can also return an error if the given `Input` contains an
1543 /// unsupported [`Anchored`] configuration.
1544 #[cfg_attr(feature = "perf-inline", inline(always))]
1545 pub fn start_state_forward(
1546 &self,
1547 cache: &mut Cache,
1548 input: &Input<'_>,
1549 ) -> Result<LazyStateID, MatchError> {
1550 if !self.quitset.is_empty() && input.start() > 0 {
1551 let offset = input.start() - 1;
1552 let byte = input.haystack()[offset];
1553 if self.quitset.contains(byte) {
1554 return Err(MatchError::quit(byte, offset));
1555 }
1556 }
1557 let start_type = self.start_map.fwd(input);
1558 let start = LazyRef::new(self, cache)
1559 .get_cached_start_id(input, start_type)?;
1560 if !start.is_unknown() {
1561 return Ok(start);
1562 }
1563 Lazy::new(self, cache).cache_start_group(input, start_type)
1564 }
1565
1566 /// Return the ID of the start state for this lazy DFA when executing a
1567 /// reverse search.
1568 ///
1569 /// Unlike typical DFA implementations, the start state for DFAs in this
1570 /// crate is dependent on a few different factors:
1571 ///
1572 /// * The [`Anchored`] mode of the search. Unanchored, anchored and
1573 /// anchored searches for a specific [`PatternID`] all use different start
1574 /// states.
1575 /// * The position at which the search begins, via [`Input::start`]. This
1576 /// and the byte immediately preceding the start of the search (if one
1577 /// exists) influence which look-behind assertions are true at the start
1578 /// of the search. This in turn influences which start state is selected.
1579 /// * Whether the search is a forward or reverse search. This routine can
1580 /// only be used for reverse searches.
1581 ///
1582 /// # Errors
1583 ///
1584 /// This may return a [`MatchError`] (not a [`CacheError`]!) if the search
1585 /// needs to give up when determining the start state (for example, if
1586 /// it sees a "quit" byte or if the cache has been cleared too many
1587 /// times). This can also return an error if the given `Input` contains an
1588 /// unsupported [`Anchored`] configuration.
1589 #[cfg_attr(feature = "perf-inline", inline(always))]
1590 pub fn start_state_reverse(
1591 &self,
1592 cache: &mut Cache,
1593 input: &Input<'_>,
1594 ) -> Result<LazyStateID, MatchError> {
1595 if !self.quitset.is_empty() && input.end() < input.haystack().len() {
1596 let offset = input.end();
1597 let byte = input.haystack()[offset];
1598 if self.quitset.contains(byte) {
1599 return Err(MatchError::quit(byte, offset));
1600 }
1601 }
1602 let start_type = self.start_map.rev(input);
1603 let start = LazyRef::new(self, cache)
1604 .get_cached_start_id(input, start_type)?;
1605 if !start.is_unknown() {
1606 return Ok(start);
1607 }
1608 Lazy::new(self, cache).cache_start_group(input, start_type)
1609 }
1610
1611 /// Returns the total number of patterns that match in this state.
1612 ///
1613 /// If the lazy DFA was compiled with one pattern, then this must
1614 /// necessarily always return `1` for all match states.
1615 ///
1616 /// A lazy DFA guarantees that [`DFA::match_pattern`] can be called with
1617 /// indices up to (but not including) the length returned by this routine
1618 /// without panicking.
1619 ///
1620 /// # Panics
1621 ///
1622 /// If the given state is not a match state, then this may either panic
1623 /// or return an incorrect result.
1624 ///
1625 /// # Example
1626 ///
1627 /// This example shows a simple instance of implementing overlapping
1628 /// matches. In particular, it shows not only how to determine how many
1629 /// patterns have matched in a particular state, but also how to access
1630 /// which specific patterns have matched.
1631 ///
1632 /// Notice that we must use [`MatchKind::All`] when building the DFA. If we
1633 /// used [`MatchKind::LeftmostFirst`] instead, then the DFA would not be
1634 /// constructed in a way that supports overlapping matches. (It would only
1635 /// report a single pattern that matches at any particular point in time.)
1636 ///
1637 /// Another thing to take note of is the patterns used and the order in
1638 /// which the pattern IDs are reported. In the example below, pattern `3`
1639 /// is yielded first. Why? Because it corresponds to the match that
1640 /// appears first. Namely, the `@` symbol is part of `\S+` but not part
1641 /// of any of the other patterns. Since the `\S+` pattern has a match that
1642 /// starts to the left of any other pattern, its ID is returned before any
1643 /// other.
1644 ///
1645 /// ```
1646 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
1647 /// use regex_automata::{hybrid::dfa::DFA, Input, MatchKind};
1648 ///
1649 /// let dfa = DFA::builder()
1650 /// .configure(DFA::config().match_kind(MatchKind::All))
1651 /// .build_many(&[
1652 /// r"\w+", r"[a-z]+", r"[A-Z]+", r"\S+",
1653 /// ])?;
1654 /// let mut cache = dfa.create_cache();
1655 /// let haystack = "@bar".as_bytes();
1656 ///
1657 /// // The start state is determined by inspecting the position and the
1658 /// // initial bytes of the haystack.
1659 /// let mut sid = dfa.start_state_forward(
1660 /// &mut cache, &Input::new(haystack),
1661 /// )?;
1662 /// // Walk all the bytes in the haystack.
1663 /// for &b in haystack {
1664 /// sid = dfa.next_state(&mut cache, sid, b)?;
1665 /// }
1666 /// sid = dfa.next_eoi_state(&mut cache, sid)?;
1667 ///
1668 /// assert!(sid.is_match());
1669 /// assert_eq!(dfa.match_len(&mut cache, sid), 3);
1670 /// // The following calls are guaranteed to not panic since `match_len`
1671 /// // returned `3` above.
1672 /// assert_eq!(dfa.match_pattern(&mut cache, sid, 0).as_usize(), 3);
1673 /// assert_eq!(dfa.match_pattern(&mut cache, sid, 1).as_usize(), 0);
1674 /// assert_eq!(dfa.match_pattern(&mut cache, sid, 2).as_usize(), 1);
1675 ///
1676 /// # Ok::<(), Box<dyn std::error::Error>>(())
1677 /// ```
1678 #[inline]
1679 pub fn match_len(&self, cache: &Cache, id: LazyStateID) -> usize {
1680 assert!(id.is_match());
1681 LazyRef::new(self, cache).get_cached_state(id).match_len()
1682 }
1683
1684 /// Returns the pattern ID corresponding to the given match index in the
1685 /// given state.
1686 ///
1687 /// See [`DFA::match_len`] for an example of how to use this method
1688 /// correctly. Note that if you know your lazy DFA is configured with a
1689 /// single pattern, then this routine is never necessary since it will
1690 /// always return a pattern ID of `0` for an index of `0` when `id`
1691 /// corresponds to a match state.
1692 ///
1693 /// Typically, this routine is used when implementing an overlapping
1694 /// search, as the example for `DFA::match_len` does.
1695 ///
1696 /// # Panics
1697 ///
1698 /// If the state ID is not a match state or if the match index is out
1699 /// of bounds for the given state, then this routine may either panic
1700 /// or produce an incorrect result. If the state ID is correct and the
1701 /// match index is correct, then this routine always produces a valid
1702 /// `PatternID`.
1703 #[inline]
1704 pub fn match_pattern(
1705 &self,
1706 cache: &Cache,
1707 id: LazyStateID,
1708 match_index: usize,
1709 ) -> PatternID {
1710 // This is an optimization for the very common case of a DFA with a
1711 // single pattern. This conditional avoids a somewhat more costly path
1712 // that finds the pattern ID from the corresponding `State`, which
1713 // requires a bit of slicing/pointer-chasing. This optimization tends
1714 // to only matter when matches are frequent.
1715 if self.pattern_len() == 1 {
1716 return PatternID::ZERO;
1717 }
1718 LazyRef::new(self, cache)
1719 .get_cached_state(id)
1720 .match_pattern(match_index)
1721 }
1722 }
1723
1724 /// A cache represents a partially computed DFA.
1725 ///
1726 /// A cache is the key component that differentiates a classical DFA and a
1727 /// hybrid NFA/DFA (also called a "lazy DFA"). Where a classical DFA builds a
1728 /// complete transition table that can handle all possible inputs, a hybrid
1729 /// NFA/DFA starts with an empty transition table and builds only the parts
1730 /// required during search. The parts that are built are stored in a cache. For
1731 /// this reason, a cache is a required parameter for nearly every operation on
1732 /// a [`DFA`].
1733 ///
1734 /// Caches can be created from their corresponding DFA via
1735 /// [`DFA::create_cache`]. A cache can only be used with either the DFA that
1736 /// created it, or the DFA that was most recently used to reset it with
1737 /// [`Cache::reset`]. Using a cache with any other DFA may result in panics
1738 /// or incorrect results.
1739 #[derive(Clone, Debug)]
1740 pub struct Cache {
1741 // N.B. If you're looking to understand how determinization works, it
1742 // is probably simpler to first grok src/dfa/determinize.rs, since that
1743 // doesn't have the "laziness" component.
1744 /// The transition table.
1745 ///
1746 /// Given a `current` LazyStateID and an `input` byte, the next state can
1747 /// be computed via `trans[untagged(current) + equiv_class(input)]`. Notice
1748 /// that no multiplication is used. That's because state identifiers are
1749 /// "premultiplied."
1750 ///
1751 /// Note that the next state may be the "unknown" state. In this case, the
1752 /// next state is not known and determinization for `current` on `input`
1753 /// must be performed.
1754 trans: Vec<LazyStateID>,
1755 /// The starting states for this DFA.
1756 ///
1757 /// These are computed lazily. Initially, these are all set to "unknown"
1758 /// lazy state IDs.
1759 ///
1760 /// When 'starts_for_each_pattern' is disabled (the default), then the size
1761 /// of this is constrained to the possible starting configurations based
1762 /// on the search parameters. (At time of writing, that's 4.) However,
1763 /// when starting states for each pattern is enabled, then there are N
1764 /// additional groups of starting states, where each group reflects the
1765 /// different possible configurations and N is the number of patterns.
1766 starts: Vec<LazyStateID>,
1767 /// A sequence of NFA/DFA powerset states that have been computed for this
1768 /// lazy DFA. This sequence is indexable by untagged LazyStateIDs. (Every
1769 /// tagged LazyStateID can be used to index this sequence by converting it
1770 /// to its untagged form.)
1771 states: Vec<State>,
1772 /// A map from states to their corresponding IDs. This map may be accessed
1773 /// via the raw byte representation of a state, which means that a `State`
1774 /// does not need to be allocated to determine whether it already exists
1775 /// in this map. Indeed, the existence of such a state is what determines
1776 /// whether we allocate a new `State` or not.
1777 ///
1778 /// The higher level idea here is that we do just enough determinization
1779 /// for a state to check whether we've already computed it. If we have,
1780 /// then we can save a little (albeit not much) work. The real savings is
1781 /// in memory usage. If we never checked for trivially duplicate states,
1782 /// then our memory usage would explode to unreasonable levels.
1783 states_to_id: StateMap,
1784 /// Sparse sets used to track which NFA states have been visited during
1785 /// various traversals.
1786 sparses: SparseSets,
1787 /// Scratch space for traversing the NFA graph. (We use space on the heap
1788 /// instead of the call stack.)
1789 stack: Vec<NFAStateID>,
1790 /// Scratch space for building a NFA/DFA powerset state. This is used to
1791 /// help amortize allocation since not every powerset state generated is
1792 /// added to the cache. In particular, if it already exists in the cache,
1793 /// then there is no need to allocate a new `State` for it.
1794 scratch_state_builder: StateBuilderEmpty,
1795 /// A simple abstraction for handling the saving of at most a single state
1796 /// across a cache clearing. This is required for correctness. Namely, if
1797 /// adding a new state after clearing the cache fails, then the caller
1798 /// must retain the ability to continue using the state ID given. The
1799 /// state corresponding to the state ID is what we preserve across cache
1800 /// clearings.
1801 state_saver: StateSaver,
1802 /// The memory usage, in bytes, used by 'states' and 'states_to_id'. We
1803 /// track this as new states are added since states use a variable amount
1804 /// of heap. Tracking this as we add states makes it possible to compute
1805 /// the total amount of memory used by the determinizer in constant time.
1806 memory_usage_state: usize,
1807 /// The number of times the cache has been cleared. When a minimum cache
1808 /// clear count is set, then the cache will return an error instead of
1809 /// clearing the cache if the count has been exceeded.
1810 clear_count: usize,
1811 /// The total number of bytes searched since the last time this cache was
1812 /// cleared, not including the current search.
1813 ///
1814 /// This can be added to the length of the current search to get the true
1815 /// total number of bytes searched.
1816 ///
1817 /// This is generally only non-zero when the
1818 /// `Cache::search_{start,update,finish}` APIs are used to track search
1819 /// progress.
1820 bytes_searched: usize,
1821 /// The progress of the current search.
1822 ///
1823 /// This is only non-`None` when callers utlize the `Cache::search_start`,
1824 /// `Cache::search_update` and `Cache::search_finish` APIs.
1825 ///
1826 /// The purpose of recording search progress is to be able to make a
1827 /// determination about the efficiency of the cache. Namely, by keeping
1828 /// track of the
1829 progress: Option<SearchProgress>,
1830 }
1831
1832 impl Cache {
1833 /// Create a new cache for the given lazy DFA.
1834 ///
1835 /// The cache returned should only be used for searches for the given DFA.
1836 /// If you want to reuse the cache for another DFA, then you must call
1837 /// [`Cache::reset`] with that DFA.
1838 pub fn new(dfa: &DFA) -> Cache {
1839 let mut cache = Cache {
1840 trans: alloc::vec![],
1841 starts: alloc::vec![],
1842 states: alloc::vec![],
1843 states_to_id: StateMap::new(),
1844 sparses: SparseSets::new(dfa.get_nfa().states().len()),
1845 stack: alloc::vec![],
1846 scratch_state_builder: StateBuilderEmpty::new(),
1847 state_saver: StateSaver::none(),
1848 memory_usage_state: 0,
1849 clear_count: 0,
1850 bytes_searched: 0,
1851 progress: None,
1852 };
1853 debug!("pre-init lazy DFA cache size: {}", cache.memory_usage());
1854 Lazy { dfa, cache: &mut cache }.init_cache();
1855 debug!("post-init lazy DFA cache size: {}", cache.memory_usage());
1856 cache
1857 }
1858
1859 /// Reset this cache such that it can be used for searching with the given
1860 /// lazy DFA (and only that DFA).
1861 ///
1862 /// A cache reset permits reusing memory already allocated in this cache
1863 /// with a different lazy DFA.
1864 ///
1865 /// Resetting a cache sets its "clear count" to 0. This is relevant if the
1866 /// lazy DFA has been configured to "give up" after it has cleared the
1867 /// cache a certain number of times.
1868 ///
1869 /// Any lazy state ID generated by the cache prior to resetting it is
1870 /// invalid after the reset.
1871 ///
1872 /// # Example
1873 ///
1874 /// This shows how to re-purpose a cache for use with a different DFA.
1875 ///
1876 /// ```
1877 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
1878 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
1879 ///
1880 /// let dfa1 = DFA::new(r"\w")?;
1881 /// let dfa2 = DFA::new(r"\W")?;
1882 ///
1883 /// let mut cache = dfa1.create_cache();
1884 /// assert_eq!(
1885 /// Some(HalfMatch::must(0, 2)),
1886 /// dfa1.try_search_fwd(&mut cache, &Input::new("Δ"))?,
1887 /// );
1888 ///
1889 /// // Using 'cache' with dfa2 is not allowed. It may result in panics or
1890 /// // incorrect results. In order to re-purpose the cache, we must reset
1891 /// // it with the DFA we'd like to use it with.
1892 /// //
1893 /// // Similarly, after this reset, using the cache with 'dfa1' is also not
1894 /// // allowed.
1895 /// cache.reset(&dfa2);
1896 /// assert_eq!(
1897 /// Some(HalfMatch::must(0, 3)),
1898 /// dfa2.try_search_fwd(&mut cache, &Input::new("☃"))?,
1899 /// );
1900 ///
1901 /// # Ok::<(), Box<dyn std::error::Error>>(())
1902 /// ```
1903 pub fn reset(&mut self, dfa: &DFA) {
1904 Lazy::new(dfa, self).reset_cache()
1905 }
1906
1907 /// Initializes a new search starting at the given position.
1908 ///
1909 /// If a previous search was unfinished, then it is finished automatically
1910 /// and a new search is begun.
1911 ///
1912 /// Note that keeping track of search progress is _not necessary_
1913 /// for correct implementations of search using a lazy DFA. Keeping
1914 /// track of search progress is only necessary if you want the
1915 /// [`Config::minimum_bytes_per_state`] configuration knob to work.
1916 #[inline]
1917 pub fn search_start(&mut self, at: usize) {
1918 // If a previous search wasn't marked as finished, then finish it
1919 // now automatically.
1920 if let Some(p) = self.progress.take() {
1921 self.bytes_searched += p.len();
1922 }
1923 self.progress = Some(SearchProgress { start: at, at });
1924 }
1925
1926 /// Updates the current search to indicate that it has search to the
1927 /// current position.
1928 ///
1929 /// No special care needs to be taken for reverse searches. Namely, the
1930 /// position given may be _less than_ the starting position of the search.
1931 ///
1932 /// # Panics
1933 ///
1934 /// This panics if no search has been started by [`Cache::search_start`].
1935 #[inline]
1936 pub fn search_update(&mut self, at: usize) {
1937 let p =
1938 self.progress.as_mut().expect("no in-progress search to update");
1939 p.at = at;
1940 }
1941
1942 /// Indicates that a search has finished at the given position.
1943 ///
1944 /// # Panics
1945 ///
1946 /// This panics if no search has been started by [`Cache::search_start`].
1947 #[inline]
1948 pub fn search_finish(&mut self, at: usize) {
1949 let mut p =
1950 self.progress.take().expect("no in-progress search to finish");
1951 p.at = at;
1952 self.bytes_searched += p.len();
1953 }
1954
1955 /// Returns the total number of bytes that have been searched since this
1956 /// cache was last cleared.
1957 ///
1958 /// This is useful for determining the efficiency of the cache. For
1959 /// example, the lazy DFA uses this value in conjunction with the
1960 /// [`Config::minimum_bytes_per_state`] knob to help determine whether it
1961 /// should quit searching.
1962 ///
1963 /// This always returns `0` if search progress isn't being tracked. Note
1964 /// that the lazy DFA search routines in this crate always track search
1965 /// progress.
1966 pub fn search_total_len(&self) -> usize {
1967 self.bytes_searched + self.progress.as_ref().map_or(0, |p| p.len())
1968 }
1969
1970 /// Returns the total number of times this cache has been cleared since it
1971 /// was either created or last reset.
1972 ///
1973 /// This is useful for informational purposes or if you want to change
1974 /// search strategies based on the number of times the cache has been
1975 /// cleared.
1976 pub fn clear_count(&self) -> usize {
1977 self.clear_count
1978 }
1979
1980 /// Returns the heap memory usage, in bytes, of this cache.
1981 ///
1982 /// This does **not** include the stack size used up by this cache. To
1983 /// compute that, use `std::mem::size_of::<Cache>()`.
1984 pub fn memory_usage(&self) -> usize {
1985 const ID_SIZE: usize = size_of::<LazyStateID>();
1986 const STATE_SIZE: usize = size_of::<State>();
1987
1988 // NOTE: If you make changes to the below, then
1989 // 'minimum_cache_capacity' should be updated correspondingly.
1990
1991 self.trans.len() * ID_SIZE
1992 + self.starts.len() * ID_SIZE
1993 + self.states.len() * STATE_SIZE
1994 // Maps likely use more memory than this, but it's probably close.
1995 + self.states_to_id.len() * (STATE_SIZE + ID_SIZE)
1996 + self.sparses.memory_usage()
1997 + self.stack.capacity() * ID_SIZE
1998 + self.scratch_state_builder.capacity()
1999 // Heap memory used by 'State' in both 'states' and 'states_to_id'.
2000 + self.memory_usage_state
2001 }
2002 }
2003
2004 /// Keeps track of the progress of the current search.
2005 ///
2006 /// This is updated via the `Cache::search_{start,update,finish}` APIs to
2007 /// record how many bytes have been searched. This permits computing a
2008 /// heuristic that represents the efficiency of a cache, and thus helps inform
2009 /// whether the lazy DFA should give up or not.
2010 #[derive(Clone, Debug)]
2011 struct SearchProgress {
2012 start: usize,
2013 at: usize,
2014 }
2015
2016 impl SearchProgress {
2017 /// Returns the length, in bytes, of this search so far.
2018 ///
2019 /// This automatically handles the case of a reverse search, where `at`
2020 /// is likely to be less than `start`.
2021 fn len(&self) -> usize {
2022 if self.start <= self.at {
2023 self.at - self.start
2024 } else {
2025 self.start - self.at
2026 }
2027 }
2028 }
2029
2030 /// A map from states to state identifiers. When using std, we use a standard
2031 /// hashmap, since it's a bit faster for this use case. (Other maps, like
2032 /// one's based on FNV, have not yet been benchmarked.)
2033 ///
2034 /// The main purpose of this map is to reuse states where possible. This won't
2035 /// fully minimize the DFA, but it works well in a lot of cases.
2036 #[cfg(feature = "std")]
2037 type StateMap = std::collections::HashMap<State, LazyStateID>;
2038 #[cfg(not(feature = "std"))]
2039 type StateMap = alloc::collections::BTreeMap<State, LazyStateID>;
2040
2041 /// A type that groups methods that require the base NFA/DFA and writable
2042 /// access to the cache.
2043 #[derive(Debug)]
2044 struct Lazy<'i, 'c> {
2045 dfa: &'i DFA,
2046 cache: &'c mut Cache,
2047 }
2048
2049 impl<'i, 'c> Lazy<'i, 'c> {
2050 /// Creates a new 'Lazy' wrapper for a DFA and its corresponding cache.
2051 fn new(dfa: &'i DFA, cache: &'c mut Cache) -> Lazy<'i, 'c> {
2052 Lazy { dfa, cache }
2053 }
2054
2055 /// Return an immutable view by downgrading a writable cache to a read-only
2056 /// cache.
2057 fn as_ref<'a>(&'a self) -> LazyRef<'i, 'a> {
2058 LazyRef::new(self.dfa, self.cache)
2059 }
2060
2061 /// This is marked as 'inline(never)' to avoid bloating methods on 'DFA'
2062 /// like 'next_state' and 'next_eoi_state' that are called in critical
2063 /// areas. The idea is to let the optimizer focus on the other areas of
2064 /// those methods as the hot path.
2065 ///
2066 /// Here's an example that justifies 'inline(never)'
2067 ///
2068 /// ```ignore
2069 /// regex-cli find hybrid dfa \
2070 /// @all-codepoints-utf8-100x '\pL{100}' --cache-capacity 10000000
2071 /// ```
2072 ///
2073 /// Where 'all-codepoints-utf8-100x' is the UTF-8 encoding of every
2074 /// codepoint, in sequence, repeated 100 times.
2075 ///
2076 /// With 'inline(never)' hyperfine reports 1.1s per run. With
2077 /// 'inline(always)', hyperfine reports 1.23s. So that's a 10% improvement.
2078 #[cold]
2079 #[inline(never)]
2080 fn cache_next_state(
2081 &mut self,
2082 mut current: LazyStateID,
2083 unit: alphabet::Unit,
2084 ) -> Result<LazyStateID, CacheError> {
2085 let stride2 = self.dfa.stride2();
2086 let empty_builder = self.get_state_builder();
2087 let builder = determinize::next(
2088 self.dfa.get_nfa(),
2089 self.dfa.get_config().get_match_kind(),
2090 &mut self.cache.sparses,
2091 &mut self.cache.stack,
2092 &self.cache.states[current.as_usize_untagged() >> stride2],
2093 unit,
2094 empty_builder,
2095 );
2096 let save_state = !self.as_ref().state_builder_fits_in_cache(&builder);
2097 if save_state {
2098 self.save_state(current);
2099 }
2100 let next = self.add_builder_state(builder, |sid| sid)?;
2101 if save_state {
2102 current = self.saved_state_id();
2103 }
2104 // This is the payoff. The next time 'next_state' is called with this
2105 // state and alphabet unit, it will find this transition and avoid
2106 // having to re-determinize this transition.
2107 self.set_transition(current, unit, next);
2108 Ok(next)
2109 }
2110
2111 /// Compute and cache the starting state for the given pattern ID (if
2112 /// present) and the starting configuration.
2113 ///
2114 /// This panics if a pattern ID is given and the DFA isn't configured to
2115 /// build anchored start states for each pattern.
2116 ///
2117 /// This will never return an unknown lazy state ID.
2118 ///
2119 /// If caching this state would otherwise result in a cache that has been
2120 /// cleared too many times, then an error is returned.
2121 #[cold]
2122 #[inline(never)]
2123 fn cache_start_group(
2124 &mut self,
2125 input: &Input<'_>,
2126 start: Start,
2127 ) -> Result<LazyStateID, MatchError> {
2128 let mode = input.get_anchored();
2129 let nfa_start_id = match mode {
2130 Anchored::No => self.dfa.get_nfa().start_unanchored(),
2131 Anchored::Yes => self.dfa.get_nfa().start_anchored(),
2132 Anchored::Pattern(pid) => {
2133 if !self.dfa.get_config().get_starts_for_each_pattern() {
2134 return Err(MatchError::unsupported_anchored(mode));
2135 }
2136 match self.dfa.get_nfa().start_pattern(pid) {
2137 None => return Ok(self.as_ref().dead_id()),
2138 Some(sid) => sid,
2139 }
2140 }
2141 };
2142
2143 let id = self
2144 .cache_start_one(nfa_start_id, start)
2145 .map_err(|_| MatchError::gave_up(input.start()))?;
2146 self.set_start_state(input, start, id);
2147 Ok(id)
2148 }
2149
2150 /// Compute and cache the starting state for the given NFA state ID and the
2151 /// starting configuration. The NFA state ID might be one of the following:
2152 ///
2153 /// 1) An unanchored start state to match any pattern.
2154 /// 2) An anchored start state to match any pattern.
2155 /// 3) An anchored start state for a particular pattern.
2156 ///
2157 /// This will never return an unknown lazy state ID.
2158 ///
2159 /// If caching this state would otherwise result in a cache that has been
2160 /// cleared too many times, then an error is returned.
2161 fn cache_start_one(
2162 &mut self,
2163 nfa_start_id: NFAStateID,
2164 start: Start,
2165 ) -> Result<LazyStateID, CacheError> {
2166 let mut builder_matches = self.get_state_builder().into_matches();
2167 determinize::set_lookbehind_from_start(
2168 self.dfa.get_nfa(),
2169 &start,
2170 &mut builder_matches,
2171 );
2172 self.cache.sparses.set1.clear();
2173 determinize::epsilon_closure(
2174 self.dfa.get_nfa(),
2175 nfa_start_id,
2176 builder_matches.look_have(),
2177 &mut self.cache.stack,
2178 &mut self.cache.sparses.set1,
2179 );
2180 let mut builder = builder_matches.into_nfa();
2181 determinize::add_nfa_states(
2182 &self.dfa.get_nfa(),
2183 &self.cache.sparses.set1,
2184 &mut builder,
2185 );
2186 let tag_starts = self.dfa.get_config().get_specialize_start_states();
2187 self.add_builder_state(builder, |id| {
2188 if tag_starts {
2189 id.to_start()
2190 } else {
2191 id
2192 }
2193 })
2194 }
2195
2196 /// Either add the given builder state to this cache, or return an ID to an
2197 /// equivalent state already in this cache.
2198 ///
2199 /// In the case where no equivalent state exists, the idmap function given
2200 /// may be used to transform the identifier allocated. This is useful if
2201 /// the caller needs to tag the ID with additional information.
2202 ///
2203 /// This will never return an unknown lazy state ID.
2204 ///
2205 /// If caching this state would otherwise result in a cache that has been
2206 /// cleared too many times, then an error is returned.
2207 fn add_builder_state(
2208 &mut self,
2209 builder: StateBuilderNFA,
2210 idmap: impl Fn(LazyStateID) -> LazyStateID,
2211 ) -> Result<LazyStateID, CacheError> {
2212 if let Some(&cached_id) =
2213 self.cache.states_to_id.get(builder.as_bytes())
2214 {
2215 // Since we have a cached state, put the constructed state's
2216 // memory back into our scratch space, so that it can be reused.
2217 self.put_state_builder(builder);
2218 return Ok(cached_id);
2219 }
2220 let result = self.add_state(builder.to_state(), idmap);
2221 self.put_state_builder(builder);
2222 result
2223 }
2224
2225 /// Allocate a new state ID and add the given state to this cache.
2226 ///
2227 /// The idmap function given may be used to transform the identifier
2228 /// allocated. This is useful if the caller needs to tag the ID with
2229 /// additional information.
2230 ///
2231 /// This will never return an unknown lazy state ID.
2232 ///
2233 /// If caching this state would otherwise result in a cache that has been
2234 /// cleared too many times, then an error is returned.
2235 fn add_state(
2236 &mut self,
2237 state: State,
2238 idmap: impl Fn(LazyStateID) -> LazyStateID,
2239 ) -> Result<LazyStateID, CacheError> {
2240 if !self.as_ref().state_fits_in_cache(&state) {
2241 self.try_clear_cache()?;
2242 }
2243 // It's important for this to come second, since the above may clear
2244 // the cache. If we clear the cache after ID generation, then the ID
2245 // is likely bunk since it would have been generated based on a larger
2246 // transition table.
2247 let mut id = idmap(self.next_state_id()?);
2248 if state.is_match() {
2249 id = id.to_match();
2250 }
2251 // Add room in the transition table. Since this is a fresh state, all
2252 // of its transitions are unknown.
2253 self.cache.trans.extend(
2254 iter::repeat(self.as_ref().unknown_id()).take(self.dfa.stride()),
2255 );
2256 // When we add a sentinel state, we never want to set any quit
2257 // transitions. Technically, this is harmless, since sentinel states
2258 // have all of their transitions set to loop back to themselves. But
2259 // when creating sentinel states before the quit sentinel state,
2260 // this will try to call 'set_transition' on a state ID that doesn't
2261 // actually exist yet, which isn't allowed. So we just skip doing so
2262 // entirely.
2263 if !self.dfa.quitset.is_empty() && !self.as_ref().is_sentinel(id) {
2264 let quit_id = self.as_ref().quit_id();
2265 for b in self.dfa.quitset.iter() {
2266 self.set_transition(id, alphabet::Unit::u8(b), quit_id);
2267 }
2268 }
2269 self.cache.memory_usage_state += state.memory_usage();
2270 self.cache.states.push(state.clone());
2271 self.cache.states_to_id.insert(state, id);
2272 Ok(id)
2273 }
2274
2275 /// Allocate a new state ID.
2276 ///
2277 /// This will never return an unknown lazy state ID.
2278 ///
2279 /// If caching this state would otherwise result in a cache that has been
2280 /// cleared too many times, then an error is returned.
2281 fn next_state_id(&mut self) -> Result<LazyStateID, CacheError> {
2282 let sid = match LazyStateID::new(self.cache.trans.len()) {
2283 Ok(sid) => sid,
2284 Err(_) => {
2285 self.try_clear_cache()?;
2286 // This has to pass since we check that ID capacity at
2287 // construction time can fit at least MIN_STATES states.
2288 LazyStateID::new(self.cache.trans.len()).unwrap()
2289 }
2290 };
2291 Ok(sid)
2292 }
2293
2294 /// Attempt to clear the cache used by this lazy DFA.
2295 ///
2296 /// If clearing the cache exceeds the minimum number of required cache
2297 /// clearings, then this will return a cache error. In this case,
2298 /// callers should bubble this up as the cache can't be used until it is
2299 /// reset. Implementations of search should convert this error into a
2300 /// [`MatchError::gave_up`].
2301 ///
2302 /// If 'self.state_saver' is set to save a state, then this state is
2303 /// persisted through cache clearing. Otherwise, the cache is returned to
2304 /// its state after initialization with two exceptions: its clear count
2305 /// is incremented and some of its memory likely has additional capacity.
2306 /// That is, clearing a cache does _not_ release memory.
2307 ///
2308 /// Otherwise, any lazy state ID generated by the cache prior to resetting
2309 /// it is invalid after the reset.
2310 fn try_clear_cache(&mut self) -> Result<(), CacheError> {
2311 let c = self.dfa.get_config();
2312 if let Some(min_count) = c.get_minimum_cache_clear_count() {
2313 if self.cache.clear_count >= min_count {
2314 if let Some(min_bytes_per) = c.get_minimum_bytes_per_state() {
2315 let len = self.cache.search_total_len();
2316 let min_bytes =
2317 min_bytes_per.saturating_mul(self.cache.states.len());
2318 // If we've searched 0 bytes then probably something has
2319 // gone wrong and the lazy DFA search implementation isn't
2320 // correctly updating the search progress state.
2321 if len == 0 {
2322 trace!(
2323 "number of bytes searched is 0, but \
2324 a minimum bytes per state searched ({}) is \
2325 enabled, maybe Cache::search_update \
2326 is not being used?",
2327 min_bytes_per,
2328 );
2329 }
2330 if len < min_bytes {
2331 trace!(
2332 "lazy DFA cache has been cleared {} times, \
2333 which exceeds the limit of {}, \
2334 AND its bytes searched per state is less \
2335 than the configured minimum of {}, \
2336 therefore lazy DFA is giving up \
2337 (bytes searched since cache clear = {}, \
2338 number of states = {})",
2339 self.cache.clear_count,
2340 min_count,
2341 min_bytes_per,
2342 len,
2343 self.cache.states.len(),
2344 );
2345 return Err(CacheError::bad_efficiency());
2346 } else {
2347 trace!(
2348 "lazy DFA cache has been cleared {} times, \
2349 which exceeds the limit of {}, \
2350 AND its bytes searched per state is greater \
2351 than the configured minimum of {}, \
2352 therefore lazy DFA is continuing! \
2353 (bytes searched since cache clear = {}, \
2354 number of states = {})",
2355 self.cache.clear_count,
2356 min_count,
2357 min_bytes_per,
2358 len,
2359 self.cache.states.len(),
2360 );
2361 }
2362 } else {
2363 trace!(
2364 "lazy DFA cache has been cleared {} times, \
2365 which exceeds the limit of {}, \
2366 since there is no configured bytes per state \
2367 minimum, lazy DFA is giving up",
2368 self.cache.clear_count,
2369 min_count,
2370 );
2371 return Err(CacheError::too_many_cache_clears());
2372 }
2373 }
2374 }
2375 self.clear_cache();
2376 Ok(())
2377 }
2378
2379 /// Clears _and_ resets the cache. Resetting the cache means that no
2380 /// states are persisted and the clear count is reset to 0. No heap memory
2381 /// is released.
2382 ///
2383 /// Note that the caller may reset a cache with a different DFA than what
2384 /// it was created from. In which case, the cache can now be used with the
2385 /// new DFA (and not the old DFA).
2386 fn reset_cache(&mut self) {
2387 self.cache.state_saver = StateSaver::none();
2388 self.clear_cache();
2389 // If a new DFA is used, it might have a different number of NFA
2390 // states, so we need to make sure our sparse sets have the appropriate
2391 // size.
2392 self.cache.sparses.resize(self.dfa.get_nfa().states().len());
2393 self.cache.clear_count = 0;
2394 self.cache.progress = None;
2395 }
2396
2397 /// Clear the cache used by this lazy DFA.
2398 ///
2399 /// If 'self.state_saver' is set to save a state, then this state is
2400 /// persisted through cache clearing. Otherwise, the cache is returned to
2401 /// its state after initialization with two exceptions: its clear count
2402 /// is incremented and some of its memory likely has additional capacity.
2403 /// That is, clearing a cache does _not_ release memory.
2404 ///
2405 /// Otherwise, any lazy state ID generated by the cache prior to resetting
2406 /// it is invalid after the reset.
2407 fn clear_cache(&mut self) {
2408 self.cache.trans.clear();
2409 self.cache.starts.clear();
2410 self.cache.states.clear();
2411 self.cache.states_to_id.clear();
2412 self.cache.memory_usage_state = 0;
2413 self.cache.clear_count += 1;
2414 self.cache.bytes_searched = 0;
2415 if let Some(ref mut progress) = self.cache.progress {
2416 progress.start = progress.at;
2417 }
2418 trace!(
2419 "lazy DFA cache has been cleared (count: {})",
2420 self.cache.clear_count
2421 );
2422 self.init_cache();
2423 // If the state we want to save is one of the sentinel
2424 // (unknown/dead/quit) states, then 'init_cache' adds those back, and
2425 // their identifier values remains invariant. So there's no need to add
2426 // it again. (And indeed, doing so would be incorrect!)
2427 if let Some((old_id, state)) = self.cache.state_saver.take_to_save() {
2428 // If the state is one of the special sentinel states, then it is
2429 // automatically added by cache initialization and its ID always
2430 // remains the same. With that said, this should never occur since
2431 // the sentinel states are all loop states back to themselves. So
2432 // we should never be in a position where we're attempting to save
2433 // a sentinel state since we never compute transitions out of a
2434 // sentinel state.
2435 assert!(
2436 !self.as_ref().is_sentinel(old_id),
2437 "cannot save sentinel state"
2438 );
2439 let new_id = self
2440 .add_state(state, |id| {
2441 if old_id.is_start() {
2442 // We don't need to consult the
2443 // 'specialize_start_states' config knob here, because
2444 // if it's disabled, old_id.is_start() will never
2445 // return true.
2446 id.to_start()
2447 } else {
2448 id
2449 }
2450 })
2451 // The unwrap here is OK because lazy DFA creation ensures that
2452 // we have room in the cache to add MIN_STATES states. Since
2453 // 'init_cache' above adds 3, this adds a 4th.
2454 .expect("adding one state after cache clear must work");
2455 self.cache.state_saver = StateSaver::Saved(new_id);
2456 }
2457 }
2458
2459 /// Initialize this cache from emptiness to a place where it can be used
2460 /// for search.
2461 ///
2462 /// This is called both at cache creation time and after the cache has been
2463 /// cleared.
2464 ///
2465 /// Primarily, this adds the three sentinel states and allocates some
2466 /// initial memory.
2467 fn init_cache(&mut self) {
2468 // Why multiply by 2 here? Because we make room for both the unanchored
2469 // and anchored start states. Unanchored is first and then anchored.
2470 let mut starts_len = Start::len().checked_mul(2).unwrap();
2471 // ... but if we also want start states for every pattern, we make room
2472 // for that too.
2473 if self.dfa.get_config().get_starts_for_each_pattern() {
2474 starts_len += Start::len() * self.dfa.pattern_len();
2475 }
2476 self.cache
2477 .starts
2478 .extend(iter::repeat(self.as_ref().unknown_id()).take(starts_len));
2479 // This is the set of NFA states that corresponds to each of our three
2480 // sentinel states: the empty set.
2481 let dead = State::dead();
2482 // This sets up some states that we use as sentinels that are present
2483 // in every DFA. While it would be technically possible to implement
2484 // this DFA without explicitly putting these states in the transition
2485 // table, this is convenient to do to make `next_state` correct for all
2486 // valid state IDs without needing explicit conditionals to special
2487 // case these sentinel states.
2488 //
2489 // All three of these states are "dead" states. That is, all of
2490 // them transition only to themselves. So once you enter one of
2491 // these states, it's impossible to leave them. Thus, any correct
2492 // search routine must explicitly check for these state types. (Sans
2493 // `unknown`, since that is only used internally to represent missing
2494 // states.)
2495 let unk_id =
2496 self.add_state(dead.clone(), |id| id.to_unknown()).unwrap();
2497 let dead_id = self.add_state(dead.clone(), |id| id.to_dead()).unwrap();
2498 let quit_id = self.add_state(dead.clone(), |id| id.to_quit()).unwrap();
2499 assert_eq!(unk_id, self.as_ref().unknown_id());
2500 assert_eq!(dead_id, self.as_ref().dead_id());
2501 assert_eq!(quit_id, self.as_ref().quit_id());
2502 // The idea here is that if you start in an unknown/dead/quit state and
2503 // try to transition on them, then you should end up where you started.
2504 self.set_all_transitions(unk_id, unk_id);
2505 self.set_all_transitions(dead_id, dead_id);
2506 self.set_all_transitions(quit_id, quit_id);
2507 // All of these states are technically equivalent from the FSM
2508 // perspective, so putting all three of them in the cache isn't
2509 // possible. (They are distinct merely because we use their
2510 // identifiers as sentinels to mean something, as indicated by the
2511 // names.) Moreover, we wouldn't want to do that. Unknown and quit
2512 // states are special in that they are artificial constructions
2513 // this implementation. But dead states are a natural part of
2514 // determinization. When you reach a point in the NFA where you cannot
2515 // go anywhere else, a dead state will naturally arise and we MUST
2516 // reuse the canonical dead state that we've created here. Why? Because
2517 // it is the state ID that tells the search routine whether a state is
2518 // dead or not, and thus, whether to stop the search. Having a bunch of
2519 // distinct dead states would be quite wasteful!
2520 self.cache.states_to_id.insert(dead, dead_id);
2521 }
2522
2523 /// Save the state corresponding to the ID given such that the state
2524 /// persists through a cache clearing.
2525 ///
2526 /// While the state may persist, the ID may not. In order to discover the
2527 /// new state ID, one must call 'saved_state_id' after a cache clearing.
2528 fn save_state(&mut self, id: LazyStateID) {
2529 let state = self.as_ref().get_cached_state(id).clone();
2530 self.cache.state_saver = StateSaver::ToSave { id, state };
2531 }
2532
2533 /// Returns the updated lazy state ID for a state that was persisted
2534 /// through a cache clearing.
2535 ///
2536 /// It is only correct to call this routine when both a state has been
2537 /// saved and the cache has just been cleared. Otherwise, this panics.
2538 fn saved_state_id(&mut self) -> LazyStateID {
2539 self.cache
2540 .state_saver
2541 .take_saved()
2542 .expect("state saver does not have saved state ID")
2543 }
2544
2545 /// Set all transitions on the state 'from' to 'to'.
2546 fn set_all_transitions(&mut self, from: LazyStateID, to: LazyStateID) {
2547 for unit in self.dfa.classes.representatives(..) {
2548 self.set_transition(from, unit, to);
2549 }
2550 }
2551
2552 /// Set the transition on 'from' for 'unit' to 'to'.
2553 ///
2554 /// This panics if either 'from' or 'to' is invalid.
2555 ///
2556 /// All unit values are OK.
2557 fn set_transition(
2558 &mut self,
2559 from: LazyStateID,
2560 unit: alphabet::Unit,
2561 to: LazyStateID,
2562 ) {
2563 assert!(self.as_ref().is_valid(from), "invalid 'from' id: {:?}", from);
2564 assert!(self.as_ref().is_valid(to), "invalid 'to' id: {:?}", to);
2565 let offset =
2566 from.as_usize_untagged() + self.dfa.classes.get_by_unit(unit);
2567 self.cache.trans[offset] = to;
2568 }
2569
2570 /// Set the start ID for the given pattern ID (if given) and starting
2571 /// configuration to the ID given.
2572 ///
2573 /// This panics if 'id' is not valid or if a pattern ID is given and
2574 /// 'starts_for_each_pattern' is not enabled.
2575 fn set_start_state(
2576 &mut self,
2577 input: &Input<'_>,
2578 start: Start,
2579 id: LazyStateID,
2580 ) {
2581 assert!(self.as_ref().is_valid(id));
2582 let start_index = start.as_usize();
2583 let index = match input.get_anchored() {
2584 Anchored::No => start_index,
2585 Anchored::Yes => Start::len() + start_index,
2586 Anchored::Pattern(pid) => {
2587 assert!(
2588 self.dfa.get_config().get_starts_for_each_pattern(),
2589 "attempted to search for a specific pattern \
2590 without enabling starts_for_each_pattern",
2591 );
2592 let pid = pid.as_usize();
2593 (2 * Start::len()) + (Start::len() * pid) + start_index
2594 }
2595 };
2596 self.cache.starts[index] = id;
2597 }
2598
2599 /// Returns a state builder from this DFA that might have existing
2600 /// capacity. This helps avoid allocs in cases where a state is built that
2601 /// turns out to already be cached.
2602 ///
2603 /// Callers must put the state builder back with 'put_state_builder',
2604 /// otherwise the allocation reuse won't work.
2605 fn get_state_builder(&mut self) -> StateBuilderEmpty {
2606 core::mem::replace(
2607 &mut self.cache.scratch_state_builder,
2608 StateBuilderEmpty::new(),
2609 )
2610 }
2611
2612 /// Puts the given state builder back into this DFA for reuse.
2613 ///
2614 /// Note that building a 'State' from a builder always creates a new alloc,
2615 /// so callers should always put the builder back.
2616 fn put_state_builder(&mut self, builder: StateBuilderNFA) {
2617 let _ = core::mem::replace(
2618 &mut self.cache.scratch_state_builder,
2619 builder.clear(),
2620 );
2621 }
2622 }
2623
2624 /// A type that groups methods that require the base NFA/DFA and read-only
2625 /// access to the cache.
2626 #[derive(Debug)]
2627 struct LazyRef<'i, 'c> {
2628 dfa: &'i DFA,
2629 cache: &'c Cache,
2630 }
2631
2632 impl<'i, 'c> LazyRef<'i, 'c> {
2633 /// Creates a new 'Lazy' wrapper for a DFA and its corresponding cache.
2634 fn new(dfa: &'i DFA, cache: &'c Cache) -> LazyRef<'i, 'c> {
2635 LazyRef { dfa, cache }
2636 }
2637
2638 /// Return the ID of the start state for the given configuration.
2639 ///
2640 /// If the start state has not yet been computed, then this returns an
2641 /// unknown lazy state ID.
2642 #[cfg_attr(feature = "perf-inline", inline(always))]
2643 fn get_cached_start_id(
2644 &self,
2645 input: &Input<'_>,
2646 start: Start,
2647 ) -> Result<LazyStateID, MatchError> {
2648 let start_index = start.as_usize();
2649 let mode = input.get_anchored();
2650 let index = match mode {
2651 Anchored::No => start_index,
2652 Anchored::Yes => Start::len() + start_index,
2653 Anchored::Pattern(pid) => {
2654 if !self.dfa.get_config().get_starts_for_each_pattern() {
2655 return Err(MatchError::unsupported_anchored(mode));
2656 }
2657 if pid.as_usize() >= self.dfa.pattern_len() {
2658 return Ok(self.dead_id());
2659 }
2660 (2 * Start::len())
2661 + (Start::len() * pid.as_usize())
2662 + start_index
2663 }
2664 };
2665 Ok(self.cache.starts[index])
2666 }
2667
2668 /// Return the cached NFA/DFA powerset state for the given ID.
2669 ///
2670 /// This panics if the given ID does not address a valid state.
2671 fn get_cached_state(&self, sid: LazyStateID) -> &State {
2672 let index = sid.as_usize_untagged() >> self.dfa.stride2();
2673 &self.cache.states[index]
2674 }
2675
2676 /// Returns true if and only if the given ID corresponds to a "sentinel"
2677 /// state.
2678 ///
2679 /// A sentinel state is a state that signifies a special condition of
2680 /// search, and where every transition maps back to itself. See LazyStateID
2681 /// for more details. Note that start and match states are _not_ sentinels
2682 /// since they may otherwise be real states with non-trivial transitions.
2683 /// The purposes of sentinel states is purely to indicate something. Their
2684 /// transitions are not meant to be followed.
2685 fn is_sentinel(&self, id: LazyStateID) -> bool {
2686 id == self.unknown_id() || id == self.dead_id() || id == self.quit_id()
2687 }
2688
2689 /// Returns the ID of the unknown state for this lazy DFA.
2690 fn unknown_id(&self) -> LazyStateID {
2691 // This unwrap is OK since 0 is always a valid state ID.
2692 LazyStateID::new(0).unwrap().to_unknown()
2693 }
2694
2695 /// Returns the ID of the dead state for this lazy DFA.
2696 fn dead_id(&self) -> LazyStateID {
2697 // This unwrap is OK since the maximum value here is 1 * 512 = 512,
2698 // which is <= 2047 (the maximum state ID on 16-bit systems). Where
2699 // 512 is the worst case for our equivalence classes (every byte is a
2700 // distinct class).
2701 LazyStateID::new(1 << self.dfa.stride2()).unwrap().to_dead()
2702 }
2703
2704 /// Returns the ID of the quit state for this lazy DFA.
2705 fn quit_id(&self) -> LazyStateID {
2706 // This unwrap is OK since the maximum value here is 2 * 512 = 1024,
2707 // which is <= 2047 (the maximum state ID on 16-bit systems). Where
2708 // 512 is the worst case for our equivalence classes (every byte is a
2709 // distinct class).
2710 LazyStateID::new(2 << self.dfa.stride2()).unwrap().to_quit()
2711 }
2712
2713 /// Returns true if and only if the given ID is valid.
2714 ///
2715 /// An ID is valid if it is both a valid index into the transition table
2716 /// and is a multiple of the DFA's stride.
2717 fn is_valid(&self, id: LazyStateID) -> bool {
2718 let id = id.as_usize_untagged();
2719 id < self.cache.trans.len() && id % self.dfa.stride() == 0
2720 }
2721
2722 /// Returns true if adding the state given would fit in this cache.
2723 fn state_fits_in_cache(&self, state: &State) -> bool {
2724 let needed = self.cache.memory_usage()
2725 + self.memory_usage_for_one_more_state(state.memory_usage());
2726 trace!(
2727 "lazy DFA cache capacity check: {:?} ?<=? {:?}",
2728 needed,
2729 self.dfa.cache_capacity
2730 );
2731 needed <= self.dfa.cache_capacity
2732 }
2733
2734 /// Returns true if adding the state to be built by the given builder would
2735 /// fit in this cache.
2736 fn state_builder_fits_in_cache(&self, state: &StateBuilderNFA) -> bool {
2737 let needed = self.cache.memory_usage()
2738 + self.memory_usage_for_one_more_state(state.as_bytes().len());
2739 needed <= self.dfa.cache_capacity
2740 }
2741
2742 /// Returns the additional memory usage, in bytes, required to add one more
2743 /// state to this cache. The given size should be the heap size, in bytes,
2744 /// that would be used by the new state being added.
2745 fn memory_usage_for_one_more_state(
2746 &self,
2747 state_heap_size: usize,
2748 ) -> usize {
2749 const ID_SIZE: usize = size_of::<LazyStateID>();
2750 const STATE_SIZE: usize = size_of::<State>();
2751
2752 self.dfa.stride() * ID_SIZE // additional space needed in trans table
2753 + STATE_SIZE // space in cache.states
2754 + (STATE_SIZE + ID_SIZE) // space in cache.states_to_id
2755 + state_heap_size // heap memory used by state itself
2756 }
2757 }
2758
2759 /// A simple type that encapsulates the saving of a state ID through a cache
2760 /// clearing.
2761 ///
2762 /// A state ID can be marked for saving with ToSave, while a state ID can be
2763 /// saved itself with Saved.
2764 #[derive(Clone, Debug)]
2765 enum StateSaver {
2766 /// An empty state saver. In this case, no states (other than the special
2767 /// sentinel states) are preserved after clearing the cache.
2768 None,
2769 /// An ID of a state (and the state itself) that should be preserved after
2770 /// the lazy DFA's cache has been cleared. After clearing, the updated ID
2771 /// is stored in 'Saved' since it may have changed.
2772 ToSave { id: LazyStateID, state: State },
2773 /// An ID that of a state that has been persisted through a lazy DFA
2774 /// cache clearing. The ID recorded here corresponds to an ID that was
2775 /// once marked as ToSave. The IDs are likely not equivalent even though
2776 /// the states they point to are.
2777 Saved(LazyStateID),
2778 }
2779
2780 impl StateSaver {
2781 /// Create an empty state saver.
2782 fn none() -> StateSaver {
2783 StateSaver::None
2784 }
2785
2786 /// Replace this state saver with an empty saver, and if this saver is a
2787 /// request to save a state, return that request.
2788 fn take_to_save(&mut self) -> Option<(LazyStateID, State)> {
2789 match core::mem::replace(self, StateSaver::None) {
2790 StateSaver::None | StateSaver::Saved(_) => None,
2791 StateSaver::ToSave { id, state } => Some((id, state)),
2792 }
2793 }
2794
2795 /// Replace this state saver with an empty saver, and if this saver is a
2796 /// saved state (or a request to save a state), return that state's ID.
2797 ///
2798 /// The idea here is that a request to save a state isn't necessarily
2799 /// honored because it might not be needed. e.g., Some higher level code
2800 /// might request a state to be saved on the off chance that the cache gets
2801 /// cleared when a new state is added at a lower level. But if that new
2802 /// state is never added, then the cache is never cleared and the state and
2803 /// its ID remain unchanged.
2804 fn take_saved(&mut self) -> Option<LazyStateID> {
2805 match core::mem::replace(self, StateSaver::None) {
2806 StateSaver::None => None,
2807 StateSaver::Saved(id) | StateSaver::ToSave { id, .. } => Some(id),
2808 }
2809 }
2810 }
2811
2812 /// The configuration used for building a lazy DFA.
2813 ///
2814 /// As a convenience, [`DFA::config`] is an alias for [`Config::new`]. The
2815 /// advantage of the former is that it often lets you avoid importing the
2816 /// `Config` type directly.
2817 ///
2818 /// A lazy DFA configuration is a simple data object that is typically used
2819 /// with [`Builder::configure`].
2820 ///
2821 /// The default configuration guarantees that a search will never return a
2822 /// "gave up" or "quit" error, although it is possible for a search to fail
2823 /// if [`Config::starts_for_each_pattern`] wasn't enabled (which it is not by
2824 /// default) and an [`Anchored::Pattern`] mode is requested via [`Input`].
2825 #[derive(Clone, Debug, Default)]
2826 pub struct Config {
2827 // As with other configuration types in this crate, we put all our knobs
2828 // in options so that we can distinguish between "default" and "not set."
2829 // This makes it possible to easily combine multiple configurations
2830 // without default values overwriting explicitly specified values. See the
2831 // 'overwrite' method.
2832 //
2833 // For docs on the fields below, see the corresponding method setters.
2834 match_kind: Option<MatchKind>,
2835 pre: Option<Option<Prefilter>>,
2836 starts_for_each_pattern: Option<bool>,
2837 byte_classes: Option<bool>,
2838 unicode_word_boundary: Option<bool>,
2839 quitset: Option<ByteSet>,
2840 specialize_start_states: Option<bool>,
2841 cache_capacity: Option<usize>,
2842 skip_cache_capacity_check: Option<bool>,
2843 minimum_cache_clear_count: Option<Option<usize>>,
2844 minimum_bytes_per_state: Option<Option<usize>>,
2845 }
2846
2847 impl Config {
2848 /// Return a new default lazy DFA builder configuration.
2849 pub fn new() -> Config {
2850 Config::default()
2851 }
2852
2853 /// Set the desired match semantics.
2854 ///
2855 /// The default is [`MatchKind::LeftmostFirst`], which corresponds to the
2856 /// match semantics of Perl-like regex engines. That is, when multiple
2857 /// patterns would match at the same leftmost position, the pattern that
2858 /// appears first in the concrete syntax is chosen.
2859 ///
2860 /// Currently, the only other kind of match semantics supported is
2861 /// [`MatchKind::All`]. This corresponds to classical DFA construction
2862 /// where all possible matches are added to the lazy DFA.
2863 ///
2864 /// Typically, `All` is used when one wants to execute an overlapping
2865 /// search and `LeftmostFirst` otherwise. In particular, it rarely makes
2866 /// sense to use `All` with the various "leftmost" find routines, since the
2867 /// leftmost routines depend on the `LeftmostFirst` automata construction
2868 /// strategy. Specifically, `LeftmostFirst` adds dead states to the
2869 /// lazy DFA as a way to terminate the search and report a match.
2870 /// `LeftmostFirst` also supports non-greedy matches using this strategy
2871 /// where as `All` does not.
2872 ///
2873 /// # Example: overlapping search
2874 ///
2875 /// This example shows the typical use of `MatchKind::All`, which is to
2876 /// report overlapping matches.
2877 ///
2878 /// ```
2879 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
2880 /// use regex_automata::{
2881 /// hybrid::dfa::{DFA, OverlappingState},
2882 /// HalfMatch, Input, MatchKind,
2883 /// };
2884 ///
2885 /// let dfa = DFA::builder()
2886 /// .configure(DFA::config().match_kind(MatchKind::All))
2887 /// .build_many(&[r"\w+$", r"\S+$"])?;
2888 /// let mut cache = dfa.create_cache();
2889 /// let haystack = "@foo";
2890 /// let mut state = OverlappingState::start();
2891 ///
2892 /// let expected = Some(HalfMatch::must(1, 4));
2893 /// dfa.try_search_overlapping_fwd(
2894 /// &mut cache, &Input::new(haystack), &mut state,
2895 /// )?;
2896 /// assert_eq!(expected, state.get_match());
2897 ///
2898 /// // The first pattern also matches at the same position, so re-running
2899 /// // the search will yield another match. Notice also that the first
2900 /// // pattern is returned after the second. This is because the second
2901 /// // pattern begins its match before the first, is therefore an earlier
2902 /// // match and is thus reported first.
2903 /// let expected = Some(HalfMatch::must(0, 4));
2904 /// dfa.try_search_overlapping_fwd(
2905 /// &mut cache, &Input::new(haystack), &mut state,
2906 /// )?;
2907 /// assert_eq!(expected, state.get_match());
2908 ///
2909 /// # Ok::<(), Box<dyn std::error::Error>>(())
2910 /// ```
2911 ///
2912 /// # Example: reverse automaton to find start of match
2913 ///
2914 /// Another example for using `MatchKind::All` is for constructing a
2915 /// reverse automaton to find the start of a match. `All` semantics are
2916 /// used for this in order to find the longest possible match, which
2917 /// corresponds to the leftmost starting position.
2918 ///
2919 /// Note that if you need the starting position then
2920 /// [`hybrid::regex::Regex`](crate::hybrid::regex::Regex) will handle this
2921 /// for you, so it's usually not necessary to do this yourself.
2922 ///
2923 /// ```
2924 /// use regex_automata::{
2925 /// hybrid::dfa::DFA,
2926 /// nfa::thompson::NFA,
2927 /// Anchored, HalfMatch, Input, MatchKind,
2928 /// };
2929 ///
2930 /// let input = Input::new("123foobar456");
2931 /// let pattern = r"[a-z]+r";
2932 ///
2933 /// let dfa_fwd = DFA::new(pattern)?;
2934 /// let dfa_rev = DFA::builder()
2935 /// .thompson(NFA::config().reverse(true))
2936 /// .configure(DFA::config().match_kind(MatchKind::All))
2937 /// .build(pattern)?;
2938 /// let mut cache_fwd = dfa_fwd.create_cache();
2939 /// let mut cache_rev = dfa_rev.create_cache();
2940 ///
2941 /// let expected_fwd = HalfMatch::must(0, 9);
2942 /// let expected_rev = HalfMatch::must(0, 3);
2943 /// let got_fwd = dfa_fwd.try_search_fwd(&mut cache_fwd, &input)?.unwrap();
2944 /// // Here we don't specify the pattern to search for since there's only
2945 /// // one pattern and we're doing a leftmost search. But if this were an
2946 /// // overlapping search, you'd need to specify the pattern that matched
2947 /// // in the forward direction. (Otherwise, you might wind up finding the
2948 /// // starting position of a match of some other pattern.) That in turn
2949 /// // requires building the reverse automaton with starts_for_each_pattern
2950 /// // enabled.
2951 /// let input = input
2952 /// .clone()
2953 /// .range(..got_fwd.offset())
2954 /// .anchored(Anchored::Yes);
2955 /// let got_rev = dfa_rev.try_search_rev(&mut cache_rev, &input)?.unwrap();
2956 /// assert_eq!(expected_fwd, got_fwd);
2957 /// assert_eq!(expected_rev, got_rev);
2958 ///
2959 /// # Ok::<(), Box<dyn std::error::Error>>(())
2960 /// ```
2961 pub fn match_kind(mut self, kind: MatchKind) -> Config {
2962 self.match_kind = Some(kind);
2963 self
2964 }
2965
2966 /// Set a prefilter to be used whenever a start state is entered.
2967 ///
2968 /// A [`Prefilter`] in this context is meant to accelerate searches by
2969 /// looking for literal prefixes that every match for the corresponding
2970 /// pattern (or patterns) must start with. Once a prefilter produces a
2971 /// match, the underlying search routine continues on to try and confirm
2972 /// the match.
2973 ///
2974 /// Be warned that setting a prefilter does not guarantee that the search
2975 /// will be faster. While it's usually a good bet, if the prefilter
2976 /// produces a lot of false positive candidates (i.e., positions matched
2977 /// by the prefilter but not by the regex), then the overall result can
2978 /// be slower than if you had just executed the regex engine without any
2979 /// prefilters.
2980 ///
2981 /// Note that unless [`Config::specialize_start_states`] has been
2982 /// explicitly set, then setting this will also enable (when `pre` is
2983 /// `Some`) or disable (when `pre` is `None`) start state specialization.
2984 /// This occurs because without start state specialization, a prefilter
2985 /// is likely to be less effective. And without a prefilter, start state
2986 /// specialization is usually pointless.
2987 ///
2988 /// By default no prefilter is set.
2989 ///
2990 /// # Example
2991 ///
2992 /// ```
2993 /// use regex_automata::{
2994 /// hybrid::dfa::DFA,
2995 /// util::prefilter::Prefilter,
2996 /// Input, HalfMatch, MatchKind,
2997 /// };
2998 ///
2999 /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["foo", "bar"]);
3000 /// let re = DFA::builder()
3001 /// .configure(DFA::config().prefilter(pre))
3002 /// .build(r"(foo|bar)[a-z]+")?;
3003 /// let mut cache = re.create_cache();
3004 /// let input = Input::new("foo1 barfox bar");
3005 /// assert_eq!(
3006 /// Some(HalfMatch::must(0, 11)),
3007 /// re.try_search_fwd(&mut cache, &input)?,
3008 /// );
3009 ///
3010 /// # Ok::<(), Box<dyn std::error::Error>>(())
3011 /// ```
3012 ///
3013 /// Be warned though that an incorrect prefilter can lead to incorrect
3014 /// results!
3015 ///
3016 /// ```
3017 /// use regex_automata::{
3018 /// hybrid::dfa::DFA,
3019 /// util::prefilter::Prefilter,
3020 /// Input, HalfMatch, MatchKind,
3021 /// };
3022 ///
3023 /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["foo", "car"]);
3024 /// let re = DFA::builder()
3025 /// .configure(DFA::config().prefilter(pre))
3026 /// .build(r"(foo|bar)[a-z]+")?;
3027 /// let mut cache = re.create_cache();
3028 /// let input = Input::new("foo1 barfox bar");
3029 /// assert_eq!(
3030 /// // No match reported even though there clearly is one!
3031 /// None,
3032 /// re.try_search_fwd(&mut cache, &input)?,
3033 /// );
3034 ///
3035 /// # Ok::<(), Box<dyn std::error::Error>>(())
3036 /// ```
3037 pub fn prefilter(mut self, pre: Option<Prefilter>) -> Config {
3038 self.pre = Some(pre);
3039 if self.specialize_start_states.is_none() {
3040 self.specialize_start_states =
3041 Some(self.get_prefilter().is_some());
3042 }
3043 self
3044 }
3045
3046 /// Whether to compile a separate start state for each pattern in the
3047 /// lazy DFA.
3048 ///
3049 /// When enabled, a separate **anchored** start state is added for each
3050 /// pattern in the lazy DFA. When this start state is used, then the DFA
3051 /// will only search for matches for the pattern specified, even if there
3052 /// are other patterns in the DFA.
3053 ///
3054 /// The main downside of this option is that it can potentially increase
3055 /// the size of the DFA and/or increase the time it takes to build the
3056 /// DFA at search time. However, since this is configuration for a lazy
3057 /// DFA, these states aren't actually built unless they're used. Enabling
3058 /// this isn't necessarily free, however, as it may result in higher cache
3059 /// usage.
3060 ///
3061 /// There are a few reasons one might want to enable this (it's disabled
3062 /// by default):
3063 ///
3064 /// 1. When looking for the start of an overlapping match (using a reverse
3065 /// DFA), doing it correctly requires starting the reverse search using the
3066 /// starting state of the pattern that matched in the forward direction.
3067 /// Indeed, when building a [`Regex`](crate::hybrid::regex::Regex), it
3068 /// will automatically enable this option when building the reverse DFA
3069 /// internally.
3070 /// 2. When you want to use a DFA with multiple patterns to both search
3071 /// for matches of any pattern or to search for anchored matches of one
3072 /// particular pattern while using the same DFA. (Otherwise, you would need
3073 /// to compile a new DFA for each pattern.)
3074 ///
3075 /// By default this is disabled.
3076 ///
3077 /// # Example
3078 ///
3079 /// This example shows how to use this option to permit the same lazy DFA
3080 /// to run both general searches for any pattern and anchored searches for
3081 /// a specific pattern.
3082 ///
3083 /// ```
3084 /// use regex_automata::{
3085 /// hybrid::dfa::DFA,
3086 /// Anchored, HalfMatch, Input, PatternID,
3087 /// };
3088 ///
3089 /// let dfa = DFA::builder()
3090 /// .configure(DFA::config().starts_for_each_pattern(true))
3091 /// .build_many(&[r"[a-z0-9]{6}", r"[a-z][a-z0-9]{5}"])?;
3092 /// let mut cache = dfa.create_cache();
3093 /// let haystack = "bar foo123";
3094 ///
3095 /// // Here's a normal unanchored search that looks for any pattern.
3096 /// let expected = HalfMatch::must(0, 10);
3097 /// let input = Input::new(haystack);
3098 /// assert_eq!(Some(expected), dfa.try_search_fwd(&mut cache, &input)?);
3099 /// // We can also do a normal anchored search for any pattern. Since it's
3100 /// // an anchored search, we position the start of the search where we
3101 /// // know the match will begin.
3102 /// let expected = HalfMatch::must(0, 10);
3103 /// let input = Input::new(haystack).range(4..);
3104 /// assert_eq!(Some(expected), dfa.try_search_fwd(&mut cache, &input)?);
3105 /// // Since we compiled anchored start states for each pattern, we can
3106 /// // also look for matches of other patterns explicitly, even if a
3107 /// // different pattern would have normally matched.
3108 /// let expected = HalfMatch::must(1, 10);
3109 /// let input = Input::new(haystack)
3110 /// .range(4..)
3111 /// .anchored(Anchored::Pattern(PatternID::must(1)));
3112 /// assert_eq!(Some(expected), dfa.try_search_fwd(&mut cache, &input)?);
3113 ///
3114 /// # Ok::<(), Box<dyn std::error::Error>>(())
3115 /// ```
3116 pub fn starts_for_each_pattern(mut self, yes: bool) -> Config {
3117 self.starts_for_each_pattern = Some(yes);
3118 self
3119 }
3120
3121 /// Whether to attempt to shrink the size of the lazy DFA's alphabet or
3122 /// not.
3123 ///
3124 /// This option is enabled by default and should never be disabled unless
3125 /// one is debugging the lazy DFA.
3126 ///
3127 /// When enabled, the lazy DFA will use a map from all possible bytes
3128 /// to their corresponding equivalence class. Each equivalence class
3129 /// represents a set of bytes that does not discriminate between a match
3130 /// and a non-match in the DFA. For example, the pattern `[ab]+` has at
3131 /// least two equivalence classes: a set containing `a` and `b` and a set
3132 /// containing every byte except for `a` and `b`. `a` and `b` are in the
3133 /// same equivalence classes because they never discriminate between a
3134 /// match and a non-match.
3135 ///
3136 /// The advantage of this map is that the size of the transition table
3137 /// can be reduced drastically from `#states * 256 * sizeof(LazyStateID)`
3138 /// to `#states * k * sizeof(LazyStateID)` where `k` is the number of
3139 /// equivalence classes (rounded up to the nearest power of 2). As a
3140 /// result, total space usage can decrease substantially. Moreover, since a
3141 /// smaller alphabet is used, DFA compilation during search becomes faster
3142 /// as well since it will potentially be able to reuse a single transition
3143 /// for multiple bytes.
3144 ///
3145 /// **WARNING:** This is only useful for debugging lazy DFAs. Disabling
3146 /// this does not yield any speed advantages. Namely, even when this is
3147 /// disabled, a byte class map is still used while searching. The only
3148 /// difference is that every byte will be forced into its own distinct
3149 /// equivalence class. This is useful for debugging the actual generated
3150 /// transitions because it lets one see the transitions defined on actual
3151 /// bytes instead of the equivalence classes.
3152 pub fn byte_classes(mut self, yes: bool) -> Config {
3153 self.byte_classes = Some(yes);
3154 self
3155 }
3156
3157 /// Heuristically enable Unicode word boundaries.
3158 ///
3159 /// When set, this will attempt to implement Unicode word boundaries as if
3160 /// they were ASCII word boundaries. This only works when the search input
3161 /// is ASCII only. If a non-ASCII byte is observed while searching, then a
3162 /// [`MatchError::quit`] error is returned.
3163 ///
3164 /// A possible alternative to enabling this option is to simply use an
3165 /// ASCII word boundary, e.g., via `(?-u:\b)`. The main reason to use this
3166 /// option is if you absolutely need Unicode support. This option lets one
3167 /// use a fast search implementation (a DFA) for some potentially very
3168 /// common cases, while providing the option to fall back to some other
3169 /// regex engine to handle the general case when an error is returned.
3170 ///
3171 /// If the pattern provided has no Unicode word boundary in it, then this
3172 /// option has no effect. (That is, quitting on a non-ASCII byte only
3173 /// occurs when this option is enabled _and_ a Unicode word boundary is
3174 /// present in the pattern.)
3175 ///
3176 /// This is almost equivalent to setting all non-ASCII bytes to be quit
3177 /// bytes. The only difference is that this will cause non-ASCII bytes to
3178 /// be quit bytes _only_ when a Unicode word boundary is present in the
3179 /// pattern.
3180 ///
3181 /// When enabling this option, callers _must_ be prepared to handle
3182 /// a [`MatchError`](crate::MatchError) error during search.
3183 /// When using a [`Regex`](crate::hybrid::regex::Regex), this
3184 /// corresponds to using the `try_` suite of methods. Alternatively,
3185 /// if callers can guarantee that their input is ASCII only, then a
3186 /// [`MatchError::quit`] error will never be returned while searching.
3187 ///
3188 /// This is disabled by default.
3189 ///
3190 /// # Example
3191 ///
3192 /// This example shows how to heuristically enable Unicode word boundaries
3193 /// in a pattern. It also shows what happens when a search comes across a
3194 /// non-ASCII byte.
3195 ///
3196 /// ```
3197 /// use regex_automata::{
3198 /// hybrid::dfa::DFA,
3199 /// HalfMatch, Input, MatchError,
3200 /// };
3201 ///
3202 /// let dfa = DFA::builder()
3203 /// .configure(DFA::config().unicode_word_boundary(true))
3204 /// .build(r"\b[0-9]+\b")?;
3205 /// let mut cache = dfa.create_cache();
3206 ///
3207 /// // The match occurs before the search ever observes the snowman
3208 /// // character, so no error occurs.
3209 /// let haystack = "foo 123 ☃";
3210 /// let expected = Some(HalfMatch::must(0, 7));
3211 /// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack))?;
3212 /// assert_eq!(expected, got);
3213 ///
3214 /// // Notice that this search fails, even though the snowman character
3215 /// // occurs after the ending match offset. This is because search
3216 /// // routines read one byte past the end of the search to account for
3217 /// // look-around, and indeed, this is required here to determine whether
3218 /// // the trailing \b matches.
3219 /// let haystack = "foo 123 ☃";
3220 /// let expected = MatchError::quit(0xE2, 8);
3221 /// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack));
3222 /// assert_eq!(Err(expected), got);
3223 ///
3224 /// // Another example is executing a search where the span of the haystack
3225 /// // we specify is all ASCII, but there is non-ASCII just before it. This
3226 /// // correctly also reports an error.
3227 /// let input = Input::new("β123").range(2..);
3228 /// let expected = MatchError::quit(0xB2, 1);
3229 /// let got = dfa.try_search_fwd(&mut cache, &input);
3230 /// assert_eq!(Err(expected), got);
3231 ///
3232 /// // And similarly for the trailing word boundary.
3233 /// let input = Input::new("123β").range(..3);
3234 /// let expected = MatchError::quit(0xCE, 3);
3235 /// let got = dfa.try_search_fwd(&mut cache, &input);
3236 /// assert_eq!(Err(expected), got);
3237 ///
3238 /// # Ok::<(), Box<dyn std::error::Error>>(())
3239 /// ```
3240 pub fn unicode_word_boundary(mut self, yes: bool) -> Config {
3241 // We have a separate option for this instead of just setting the
3242 // appropriate quit bytes here because we don't want to set quit bytes
3243 // for every regex. We only want to set them when the regex contains a
3244 // Unicode word boundary.
3245 self.unicode_word_boundary = Some(yes);
3246 self
3247 }
3248
3249 /// Add a "quit" byte to the lazy DFA.
3250 ///
3251 /// When a quit byte is seen during search time, then search will return a
3252 /// [`MatchError::quit`] error indicating the offset at which the search
3253 /// stopped.
3254 ///
3255 /// A quit byte will always overrule any other aspects of a regex. For
3256 /// example, if the `x` byte is added as a quit byte and the regex `\w` is
3257 /// used, then observing `x` will cause the search to quit immediately
3258 /// despite the fact that `x` is in the `\w` class.
3259 ///
3260 /// This mechanism is primarily useful for heuristically enabling certain
3261 /// features like Unicode word boundaries in a DFA. Namely, if the input
3262 /// to search is ASCII, then a Unicode word boundary can be implemented
3263 /// via an ASCII word boundary with no change in semantics. Thus, a DFA
3264 /// can attempt to match a Unicode word boundary but give up as soon as it
3265 /// observes a non-ASCII byte. Indeed, if callers set all non-ASCII bytes
3266 /// to be quit bytes, then Unicode word boundaries will be permitted when
3267 /// building lazy DFAs. Of course, callers should enable
3268 /// [`Config::unicode_word_boundary`] if they want this behavior instead.
3269 /// (The advantage being that non-ASCII quit bytes will only be added if a
3270 /// Unicode word boundary is in the pattern.)
3271 ///
3272 /// When enabling this option, callers _must_ be prepared to handle a
3273 /// [`MatchError`](crate::MatchError) error during search. When using a
3274 /// [`Regex`](crate::hybrid::regex::Regex), this corresponds to using the
3275 /// `try_` suite of methods.
3276 ///
3277 /// By default, there are no quit bytes set.
3278 ///
3279 /// # Panics
3280 ///
3281 /// This panics if heuristic Unicode word boundaries are enabled and any
3282 /// non-ASCII byte is removed from the set of quit bytes. Namely, enabling
3283 /// Unicode word boundaries requires setting every non-ASCII byte to a quit
3284 /// byte. So if the caller attempts to undo any of that, then this will
3285 /// panic.
3286 ///
3287 /// # Example
3288 ///
3289 /// This example shows how to cause a search to terminate if it sees a
3290 /// `\n` byte. This could be useful if, for example, you wanted to prevent
3291 /// a user supplied pattern from matching across a line boundary.
3292 ///
3293 /// ```
3294 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
3295 /// use regex_automata::{hybrid::dfa::DFA, MatchError, Input};
3296 ///
3297 /// let dfa = DFA::builder()
3298 /// .configure(DFA::config().quit(b'\n', true))
3299 /// .build(r"foo\p{any}+bar")?;
3300 /// let mut cache = dfa.create_cache();
3301 ///
3302 /// let haystack = "foo\nbar";
3303 /// // Normally this would produce a match, since \p{any} contains '\n'.
3304 /// // But since we instructed the automaton to enter a quit state if a
3305 /// // '\n' is observed, this produces a match error instead.
3306 /// let expected = MatchError::quit(b'\n', 3);
3307 /// let got = dfa.try_search_fwd(
3308 /// &mut cache,
3309 /// &Input::new(haystack),
3310 /// ).unwrap_err();
3311 /// assert_eq!(expected, got);
3312 ///
3313 /// # Ok::<(), Box<dyn std::error::Error>>(())
3314 /// ```
3315 pub fn quit(mut self, byte: u8, yes: bool) -> Config {
3316 if self.get_unicode_word_boundary() && !byte.is_ascii() && !yes {
3317 panic!(
3318 "cannot set non-ASCII byte to be non-quit when \
3319 Unicode word boundaries are enabled"
3320 );
3321 }
3322 if self.quitset.is_none() {
3323 self.quitset = Some(ByteSet::empty());
3324 }
3325 if yes {
3326 self.quitset.as_mut().unwrap().add(byte);
3327 } else {
3328 self.quitset.as_mut().unwrap().remove(byte);
3329 }
3330 self
3331 }
3332
3333 /// Enable specializing start states in the lazy DFA.
3334 ///
3335 /// When start states are specialized, an implementor of a search routine
3336 /// using a lazy DFA can tell when the search has entered a starting state.
3337 /// When start states aren't specialized, then it is impossible to know
3338 /// whether the search has entered a start state.
3339 ///
3340 /// Ideally, this option wouldn't need to exist and we could always
3341 /// specialize start states. The problem is that start states can be quite
3342 /// active. This in turn means that an efficient search routine is likely
3343 /// to ping-pong between a heavily optimized hot loop that handles most
3344 /// states and to a less optimized specialized handling of start states.
3345 /// This causes branches to get heavily mispredicted and overall can
3346 /// materially decrease throughput. Therefore, specializing start states
3347 /// should only be enabled when it is needed.
3348 ///
3349 /// Knowing whether a search is in a start state is typically useful when a
3350 /// prefilter is active for the search. A prefilter is typically only run
3351 /// when in a start state and a prefilter can greatly accelerate a search.
3352 /// Therefore, the possible cost of specializing start states is worth it
3353 /// in this case. Otherwise, if you have no prefilter, there is likely no
3354 /// reason to specialize start states.
3355 ///
3356 /// This is disabled by default, but note that it is automatically
3357 /// enabled (or disabled) if [`Config::prefilter`] is set. Namely, unless
3358 /// `specialize_start_states` has already been set, [`Config::prefilter`]
3359 /// will automatically enable or disable it based on whether a prefilter
3360 /// is present or not, respectively. This is done because a prefilter's
3361 /// effectiveness is rooted in being executed whenever the DFA is in a
3362 /// start state, and that's only possible to do when they are specialized.
3363 ///
3364 /// Note that it is plausibly reasonable to _disable_ this option
3365 /// explicitly while _enabling_ a prefilter. In that case, a prefilter
3366 /// will still be run at the beginning of a search, but never again. This
3367 /// in theory could strike a good balance if you're in a situation where a
3368 /// prefilter is likely to produce many false positive candidates.
3369 ///
3370 /// # Example
3371 ///
3372 /// This example shows how to enable start state specialization and then
3373 /// shows how to check whether a state is a start state or not.
3374 ///
3375 /// ```
3376 /// use regex_automata::{hybrid::dfa::DFA, MatchError, Input};
3377 ///
3378 /// let dfa = DFA::builder()
3379 /// .configure(DFA::config().specialize_start_states(true))
3380 /// .build(r"[a-z]+")?;
3381 /// let mut cache = dfa.create_cache();
3382 ///
3383 /// let haystack = "123 foobar 4567".as_bytes();
3384 /// let sid = dfa.start_state_forward(&mut cache, &Input::new(haystack))?;
3385 /// // The ID returned by 'start_state_forward' will always be tagged as
3386 /// // a start state when start state specialization is enabled.
3387 /// assert!(sid.is_tagged());
3388 /// assert!(sid.is_start());
3389 ///
3390 /// # Ok::<(), Box<dyn std::error::Error>>(())
3391 /// ```
3392 ///
3393 /// Compare the above with the default lazy DFA configuration where
3394 /// start states are _not_ specialized. In this case, the start state
3395 /// is not tagged and `sid.is_start()` returns false.
3396 ///
3397 /// ```
3398 /// use regex_automata::{hybrid::dfa::DFA, MatchError, Input};
3399 ///
3400 /// let dfa = DFA::new(r"[a-z]+")?;
3401 /// let mut cache = dfa.create_cache();
3402 ///
3403 /// let haystack = "123 foobar 4567".as_bytes();
3404 /// let sid = dfa.start_state_forward(&mut cache, &Input::new(haystack))?;
3405 /// // Start states are not tagged in the default configuration!
3406 /// assert!(!sid.is_tagged());
3407 /// assert!(!sid.is_start());
3408 ///
3409 /// # Ok::<(), Box<dyn std::error::Error>>(())
3410 /// ```
3411 pub fn specialize_start_states(mut self, yes: bool) -> Config {
3412 self.specialize_start_states = Some(yes);
3413 self
3414 }
3415
3416 /// Sets the maximum amount of heap memory, in bytes, to allocate to the
3417 /// cache for use during a lazy DFA search. If the lazy DFA would otherwise
3418 /// use more heap memory, then, depending on other configuration knobs,
3419 /// either stop the search and return an error or clear the cache and
3420 /// continue the search.
3421 ///
3422 /// The default cache capacity is some "reasonable" number that will
3423 /// accommodate most regular expressions. You may find that if you need
3424 /// to build a large DFA then it may be necessary to increase the cache
3425 /// capacity.
3426 ///
3427 /// Note that while building a lazy DFA will do a "minimum" check to ensure
3428 /// the capacity is big enough, this is more or less about correctness.
3429 /// If the cache is bigger than the minimum but still "too small," then the
3430 /// lazy DFA could wind up spending a lot of time clearing the cache and
3431 /// recomputing transitions, thus negating the performance benefits of a
3432 /// lazy DFA. Thus, setting the cache capacity is mostly an experimental
3433 /// endeavor. For most common patterns, however, the default should be
3434 /// sufficient.
3435 ///
3436 /// For more details on how the lazy DFA's cache is used, see the
3437 /// documentation for [`Cache`].
3438 ///
3439 /// # Example
3440 ///
3441 /// This example shows what happens if the configured cache capacity is
3442 /// too small. In such cases, one can override the cache capacity to make
3443 /// it bigger. Alternatively, one might want to use less memory by setting
3444 /// a smaller cache capacity.
3445 ///
3446 /// ```
3447 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
3448 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
3449 ///
3450 /// let pattern = r"\p{L}{1000}";
3451 ///
3452 /// // The default cache capacity is likely too small to deal with regexes
3453 /// // that are very large. Large repetitions of large Unicode character
3454 /// // classes are a common way to make very large regexes.
3455 /// let _ = DFA::new(pattern).unwrap_err();
3456 /// // Bump up the capacity to something bigger.
3457 /// let dfa = DFA::builder()
3458 /// .configure(DFA::config().cache_capacity(100 * (1<<20))) // 100 MB
3459 /// .build(pattern)?;
3460 /// let mut cache = dfa.create_cache();
3461 ///
3462 /// let haystack = "ͰͲͶͿΆΈΉΊΌΎΏΑΒΓΔΕΖΗΘΙ".repeat(50);
3463 /// let expected = Some(HalfMatch::must(0, 2000));
3464 /// let got = dfa.try_search_fwd(&mut cache, &Input::new(&haystack))?;
3465 /// assert_eq!(expected, got);
3466 ///
3467 /// # Ok::<(), Box<dyn std::error::Error>>(())
3468 /// ```
3469 pub fn cache_capacity(mut self, bytes: usize) -> Config {
3470 self.cache_capacity = Some(bytes);
3471 self
3472 }
3473
3474 /// Configures construction of a lazy DFA to use the minimum cache capacity
3475 /// if the configured capacity is otherwise too small for the provided NFA.
3476 ///
3477 /// This is useful if you never want lazy DFA construction to fail because
3478 /// of a capacity that is too small.
3479 ///
3480 /// In general, this option is typically not a good idea. In particular,
3481 /// while a minimum cache capacity does permit the lazy DFA to function
3482 /// where it otherwise couldn't, it's plausible that it may not function
3483 /// well if it's constantly running out of room. In that case, the speed
3484 /// advantages of the lazy DFA may be negated. On the other hand, the
3485 /// "minimum" cache capacity computed may not be completely accurate and
3486 /// could actually be bigger than what is really necessary. Therefore, it
3487 /// is plausible that using the minimum cache capacity could still result
3488 /// in very good performance.
3489 ///
3490 /// This is disabled by default.
3491 ///
3492 /// # Example
3493 ///
3494 /// This example shows what happens if the configured cache capacity is
3495 /// too small. In such cases, one could override the capacity explicitly.
3496 /// An alternative, demonstrated here, let's us force construction to use
3497 /// the minimum cache capacity if the configured capacity is otherwise
3498 /// too small.
3499 ///
3500 /// ```
3501 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
3502 /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
3503 ///
3504 /// let pattern = r"\p{L}{1000}";
3505 ///
3506 /// // The default cache capacity is likely too small to deal with regexes
3507 /// // that are very large. Large repetitions of large Unicode character
3508 /// // classes are a common way to make very large regexes.
3509 /// let _ = DFA::new(pattern).unwrap_err();
3510 /// // Configure construction such it automatically selects the minimum
3511 /// // cache capacity if it would otherwise be too small.
3512 /// let dfa = DFA::builder()
3513 /// .configure(DFA::config().skip_cache_capacity_check(true))
3514 /// .build(pattern)?;
3515 /// let mut cache = dfa.create_cache();
3516 ///
3517 /// let haystack = "ͰͲͶͿΆΈΉΊΌΎΏΑΒΓΔΕΖΗΘΙ".repeat(50);
3518 /// let expected = Some(HalfMatch::must(0, 2000));
3519 /// let got = dfa.try_search_fwd(&mut cache, &Input::new(&haystack))?;
3520 /// assert_eq!(expected, got);
3521 ///
3522 /// # Ok::<(), Box<dyn std::error::Error>>(())
3523 /// ```
3524 pub fn skip_cache_capacity_check(mut self, yes: bool) -> Config {
3525 self.skip_cache_capacity_check = Some(yes);
3526 self
3527 }
3528
3529 /// Configure a lazy DFA search to quit after a certain number of cache
3530 /// clearings.
3531 ///
3532 /// When a minimum is set, then a lazy DFA search will *possibly* "give
3533 /// up" after the minimum number of cache clearings has occurred. This is
3534 /// typically useful in scenarios where callers want to detect whether the
3535 /// lazy DFA search is "efficient" or not. If the cache is cleared too many
3536 /// times, this is a good indicator that it is not efficient, and thus, the
3537 /// caller may wish to use some other regex engine.
3538 ///
3539 /// Note that the number of times a cache is cleared is a property of
3540 /// the cache itself. Thus, if a cache is used in a subsequent search
3541 /// with a similarly configured lazy DFA, then it could cause the
3542 /// search to "give up" if the cache needed to be cleared, depending
3543 /// on its internal count and configured minimum. The cache clear
3544 /// count can only be reset to `0` via [`DFA::reset_cache`] (or
3545 /// [`Regex::reset_cache`](crate::hybrid::regex::Regex::reset_cache) if
3546 /// you're using the `Regex` API).
3547 ///
3548 /// By default, no minimum is configured. Thus, a lazy DFA search will
3549 /// never give up due to cache clearings. If you do set this option, you
3550 /// might consider also setting [`Config::minimum_bytes_per_state`] in
3551 /// order for the lazy DFA to take efficiency into account before giving
3552 /// up.
3553 ///
3554 /// # Example
3555 ///
3556 /// This example uses a somewhat pathological configuration to demonstrate
3557 /// the _possible_ behavior of cache clearing and how it might result
3558 /// in a search that returns an error.
3559 ///
3560 /// It is important to note that the precise mechanics of how and when
3561 /// a cache gets cleared is an implementation detail.
3562 ///
3563 /// ```
3564 /// # if cfg!(miri) { return Ok(()); } // miri takes too long
3565 /// use regex_automata::{hybrid::dfa::DFA, Input, MatchError, MatchErrorKind};
3566 ///
3567 /// // This is a carefully chosen regex. The idea is to pick one
3568 /// // that requires some decent number of states (hence the bounded
3569 /// // repetition). But we specifically choose to create a class with an
3570 /// // ASCII letter and a non-ASCII letter so that we can check that no new
3571 /// // states are created once the cache is full. Namely, if we fill up the
3572 /// // cache on a haystack of 'a's, then in order to match one 'β', a new
3573 /// // state will need to be created since a 'β' is encoded with multiple
3574 /// // bytes. Since there's no room for this state, the search should quit
3575 /// // at the very first position.
3576 /// let pattern = r"[aβ]{100}";
3577 /// let dfa = DFA::builder()
3578 /// .configure(
3579 /// // Configure it so that we have the minimum cache capacity
3580 /// // possible. And that if any clearings occur, the search quits.
3581 /// DFA::config()
3582 /// .skip_cache_capacity_check(true)
3583 /// .cache_capacity(0)
3584 /// .minimum_cache_clear_count(Some(0)),
3585 /// )
3586 /// .build(pattern)?;
3587 /// let mut cache = dfa.create_cache();
3588 ///
3589 /// // Our search will give up before reaching the end!
3590 /// let haystack = "a".repeat(101).into_bytes();
3591 /// let result = dfa.try_search_fwd(&mut cache, &Input::new(&haystack));
3592 /// assert!(matches!(
3593 /// *result.unwrap_err().kind(),
3594 /// MatchErrorKind::GaveUp { .. },
3595 /// ));
3596 ///
3597 /// // Now that we know the cache is full, if we search a haystack that we
3598 /// // know will require creating at least one new state, it should not
3599 /// // be able to make much progress.
3600 /// let haystack = "β".repeat(101).into_bytes();
3601 /// let result = dfa.try_search_fwd(&mut cache, &Input::new(&haystack));
3602 /// assert!(matches!(
3603 /// *result.unwrap_err().kind(),
3604 /// MatchErrorKind::GaveUp { .. },
3605 /// ));
3606 ///
3607 /// // If we reset the cache, then we should be able to create more states
3608 /// // and make more progress with searching for betas.
3609 /// cache.reset(&dfa);
3610 /// let haystack = "β".repeat(101).into_bytes();
3611 /// let result = dfa.try_search_fwd(&mut cache, &Input::new(&haystack));
3612 /// assert!(matches!(
3613 /// *result.unwrap_err().kind(),
3614 /// MatchErrorKind::GaveUp { .. },
3615 /// ));
3616 ///
3617 /// // ... switching back to ASCII still makes progress since it just needs
3618 /// // to set transitions on existing states!
3619 /// let haystack = "a".repeat(101).into_bytes();
3620 /// let result = dfa.try_search_fwd(&mut cache, &Input::new(&haystack));
3621 /// assert!(matches!(
3622 /// *result.unwrap_err().kind(),
3623 /// MatchErrorKind::GaveUp { .. },
3624 /// ));
3625 ///
3626 /// # Ok::<(), Box<dyn std::error::Error>>(())
3627 /// ```
3628 pub fn minimum_cache_clear_count(mut self, min: Option<usize>) -> Config {
3629 self.minimum_cache_clear_count = Some(min);
3630 self
3631 }
3632
3633 /// Configure a lazy DFA search to quit only when its efficiency drops
3634 /// below the given minimum.
3635 ///
3636 /// The efficiency of the cache is determined by the number of DFA states
3637 /// compiled per byte of haystack searched. For example, if the efficiency
3638 /// is 2, then it means the lazy DFA is creating a new DFA state after
3639 /// searching approximately 2 bytes in a haystack. Generally speaking, 2
3640 /// is quite bad and it's likely that even a slower regex engine like the
3641 /// [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM) would be faster.
3642 ///
3643 /// This has no effect if [`Config::minimum_cache_clear_count`] is not set.
3644 /// Namely, this option only kicks in when the cache has been cleared more
3645 /// than the minimum number. If no minimum is set, then the cache is simply
3646 /// cleared whenever it fills up and it is impossible for the lazy DFA to
3647 /// quit due to ineffective use of the cache.
3648 ///
3649 /// In general, if one is setting [`Config::minimum_cache_clear_count`],
3650 /// then one should probably also set this knob as well. The reason is
3651 /// that the absolute number of times the cache is cleared is generally
3652 /// not a great predictor of efficiency. For example, if a new DFA state
3653 /// is created for every 1,000 bytes searched, then it wouldn't be hard
3654 /// for the cache to get cleared more than `N` times and then cause the
3655 /// lazy DFA to quit. But a new DFA state every 1,000 bytes is likely quite
3656 /// good from a performance perspective, and it's likely that the lazy
3657 /// DFA should continue searching, even if it requires clearing the cache
3658 /// occasionally.
3659 ///
3660 /// Finally, note that if you're implementing your own lazy DFA search
3661 /// routine and also want this efficiency check to work correctly, then
3662 /// you'll need to use the following routines to record search progress:
3663 ///
3664 /// * Call [`Cache::search_start`] at the beginning of every search.
3665 /// * Call [`Cache::search_update`] whenever [`DFA::next_state`] is
3666 /// called.
3667 /// * Call [`Cache::search_finish`] before completing a search. (It is
3668 /// not strictly necessary to call this when an error is returned, as
3669 /// `Cache::search_start` will automatically finish the previous search
3670 /// for you. But calling it where possible before returning helps improve
3671 /// the accuracy of how many bytes have actually been searched.)
3672 pub fn minimum_bytes_per_state(mut self, min: Option<usize>) -> Config {
3673 self.minimum_bytes_per_state = Some(min);
3674 self
3675 }
3676
3677 /// Returns the match semantics set in this configuration.
3678 pub fn get_match_kind(&self) -> MatchKind {
3679 self.match_kind.unwrap_or(MatchKind::LeftmostFirst)
3680 }
3681
3682 /// Returns the prefilter set in this configuration, if one at all.
3683 pub fn get_prefilter(&self) -> Option<&Prefilter> {
3684 self.pre.as_ref().unwrap_or(&None).as_ref()
3685 }
3686
3687 /// Returns whether this configuration has enabled anchored starting states
3688 /// for every pattern in the DFA.
3689 pub fn get_starts_for_each_pattern(&self) -> bool {
3690 self.starts_for_each_pattern.unwrap_or(false)
3691 }
3692
3693 /// Returns whether this configuration has enabled byte classes or not.
3694 /// This is typically a debugging oriented option, as disabling it confers
3695 /// no speed benefit.
3696 pub fn get_byte_classes(&self) -> bool {
3697 self.byte_classes.unwrap_or(true)
3698 }
3699
3700 /// Returns whether this configuration has enabled heuristic Unicode word
3701 /// boundary support. When enabled, it is possible for a search to return
3702 /// an error.
3703 pub fn get_unicode_word_boundary(&self) -> bool {
3704 self.unicode_word_boundary.unwrap_or(false)
3705 }
3706
3707 /// Returns whether this configuration will instruct the lazy DFA to enter
3708 /// a quit state whenever the given byte is seen during a search. When at
3709 /// least one byte has this enabled, it is possible for a search to return
3710 /// an error.
3711 pub fn get_quit(&self, byte: u8) -> bool {
3712 self.quitset.map_or(false, |q| q.contains(byte))
3713 }
3714
3715 /// Returns whether this configuration will instruct the lazy DFA to
3716 /// "specialize" start states. When enabled, the lazy DFA will tag start
3717 /// states so that search routines using the lazy DFA can detect when
3718 /// it's in a start state and do some kind of optimization (like run a
3719 /// prefilter).
3720 pub fn get_specialize_start_states(&self) -> bool {
3721 self.specialize_start_states.unwrap_or(false)
3722 }
3723
3724 /// Returns the cache capacity set on this configuration.
3725 pub fn get_cache_capacity(&self) -> usize {
3726 self.cache_capacity.unwrap_or(2 * (1 << 20))
3727 }
3728
3729 /// Returns whether the cache capacity check should be skipped.
3730 pub fn get_skip_cache_capacity_check(&self) -> bool {
3731 self.skip_cache_capacity_check.unwrap_or(false)
3732 }
3733
3734 /// Returns, if set, the minimum number of times the cache must be cleared
3735 /// before a lazy DFA search can give up. When no minimum is set, then a
3736 /// search will never quit and will always clear the cache whenever it
3737 /// fills up.
3738 pub fn get_minimum_cache_clear_count(&self) -> Option<usize> {
3739 self.minimum_cache_clear_count.unwrap_or(None)
3740 }
3741
3742 /// Returns, if set, the minimum number of bytes per state that need to be
3743 /// processed in order for the lazy DFA to keep going. If the minimum falls
3744 /// below this number (and the cache has been cleared a minimum number of
3745 /// times), then the lazy DFA will return a "gave up" error.
3746 pub fn get_minimum_bytes_per_state(&self) -> Option<usize> {
3747 self.minimum_bytes_per_state.unwrap_or(None)
3748 }
3749
3750 /// Returns the minimum lazy DFA cache capacity required for the given NFA.
3751 ///
3752 /// The cache capacity required for a particular NFA may change without
3753 /// notice. Callers should not rely on it being stable.
3754 ///
3755 /// This is useful for informational purposes, but can also be useful for
3756 /// other reasons. For example, if one wants to check the minimum cache
3757 /// capacity themselves or if one wants to set the capacity based on the
3758 /// minimum.
3759 ///
3760 /// This may return an error if this configuration does not support all of
3761 /// the instructions used in the given NFA. For example, if the NFA has a
3762 /// Unicode word boundary but this configuration does not enable heuristic
3763 /// support for Unicode word boundaries.
3764 pub fn get_minimum_cache_capacity(
3765 &self,
3766 nfa: &thompson::NFA,
3767 ) -> Result<usize, BuildError> {
3768 let quitset = self.quit_set_from_nfa(nfa)?;
3769 let classes = self.byte_classes_from_nfa(nfa, &quitset);
3770 let starts = self.get_starts_for_each_pattern();
3771 Ok(minimum_cache_capacity(nfa, &classes, starts))
3772 }
3773
3774 /// Returns the byte class map used during search from the given NFA.
3775 ///
3776 /// If byte classes are disabled on this configuration, then a map is
3777 /// returned that puts each byte in its own equivalent class.
3778 fn byte_classes_from_nfa(
3779 &self,
3780 nfa: &thompson::NFA,
3781 quit: &ByteSet,
3782 ) -> ByteClasses {
3783 if !self.get_byte_classes() {
3784 // The lazy DFA will always use the equivalence class map, but
3785 // enabling this option is useful for debugging. Namely, this will
3786 // cause all transitions to be defined over their actual bytes
3787 // instead of an opaque equivalence class identifier. The former is
3788 // much easier to grok as a human.
3789 ByteClasses::singletons()
3790 } else {
3791 let mut set = nfa.byte_class_set().clone();
3792 // It is important to distinguish any "quit" bytes from all other
3793 // bytes. Otherwise, a non-quit byte may end up in the same class
3794 // as a quit byte, and thus cause the DFA stop when it shouldn't.
3795 //
3796 // Test case:
3797 //
3798 // regex-cli find hybrid regex -w @conn.json.1000x.log \
3799 // '^#' '\b10\.55\.182\.100\b'
3800 if !quit.is_empty() {
3801 set.add_set(&quit);
3802 }
3803 set.byte_classes()
3804 }
3805 }
3806
3807 /// Return the quit set for this configuration and the given NFA.
3808 ///
3809 /// This may return an error if the NFA is incompatible with this
3810 /// configuration's quit set. For example, if the NFA has a Unicode word
3811 /// boundary and the quit set doesn't include non-ASCII bytes.
3812 fn quit_set_from_nfa(
3813 &self,
3814 nfa: &thompson::NFA,
3815 ) -> Result<ByteSet, BuildError> {
3816 let mut quit = self.quitset.unwrap_or(ByteSet::empty());
3817 if nfa.look_set_any().contains_word_unicode() {
3818 if self.get_unicode_word_boundary() {
3819 for b in 0x80..=0xFF {
3820 quit.add(b);
3821 }
3822 } else {
3823 // If heuristic support for Unicode word boundaries wasn't
3824 // enabled, then we can still check if our quit set is correct.
3825 // If the caller set their quit bytes in a way that causes the
3826 // DFA to quit on at least all non-ASCII bytes, then that's all
3827 // we need for heuristic support to work.
3828 if !quit.contains_range(0x80, 0xFF) {
3829 return Err(
3830 BuildError::unsupported_dfa_word_boundary_unicode(),
3831 );
3832 }
3833 }
3834 }
3835 Ok(quit)
3836 }
3837
3838 /// Overwrite the default configuration such that the options in `o` are
3839 /// always used. If an option in `o` is not set, then the corresponding
3840 /// option in `self` is used. If it's not set in `self` either, then it
3841 /// remains not set.
3842 fn overwrite(&self, o: Config) -> Config {
3843 Config {
3844 match_kind: o.match_kind.or(self.match_kind),
3845 pre: o.pre.or_else(|| self.pre.clone()),
3846 starts_for_each_pattern: o
3847 .starts_for_each_pattern
3848 .or(self.starts_for_each_pattern),
3849 byte_classes: o.byte_classes.or(self.byte_classes),
3850 unicode_word_boundary: o
3851 .unicode_word_boundary
3852 .or(self.unicode_word_boundary),
3853 quitset: o.quitset.or(self.quitset),
3854 specialize_start_states: o
3855 .specialize_start_states
3856 .or(self.specialize_start_states),
3857 cache_capacity: o.cache_capacity.or(self.cache_capacity),
3858 skip_cache_capacity_check: o
3859 .skip_cache_capacity_check
3860 .or(self.skip_cache_capacity_check),
3861 minimum_cache_clear_count: o
3862 .minimum_cache_clear_count
3863 .or(self.minimum_cache_clear_count),
3864 minimum_bytes_per_state: o
3865 .minimum_bytes_per_state
3866 .or(self.minimum_bytes_per_state),
3867 }
3868 }
3869 }
3870
3871 /// A builder for constructing a lazy deterministic finite automaton from
3872 /// regular expressions.
3873 ///
3874 /// As a convenience, [`DFA::builder`] is an alias for [`Builder::new`]. The
3875 /// advantage of the former is that it often lets you avoid importing the
3876 /// `Builder` type directly.
3877 ///
3878 /// This builder provides two main things:
3879 ///
3880 /// 1. It provides a few different `build` routines for actually constructing
3881 /// a DFA from different kinds of inputs. The most convenient is
3882 /// [`Builder::build`], which builds a DFA directly from a pattern string. The
3883 /// most flexible is [`Builder::build_from_nfa`], which builds a DFA straight
3884 /// from an NFA.
3885 /// 2. The builder permits configuring a number of things.
3886 /// [`Builder::configure`] is used with [`Config`] to configure aspects of
3887 /// the DFA and the construction process itself. [`Builder::syntax`] and
3888 /// [`Builder::thompson`] permit configuring the regex parser and Thompson NFA
3889 /// construction, respectively. The syntax and thompson configurations only
3890 /// apply when building from a pattern string.
3891 ///
3892 /// This builder always constructs a *single* lazy DFA. As such, this builder
3893 /// can only be used to construct regexes that either detect the presence
3894 /// of a match or find the end location of a match. A single DFA cannot
3895 /// produce both the start and end of a match. For that information, use a
3896 /// [`Regex`](crate::hybrid::regex::Regex), which can be similarly configured
3897 /// using [`regex::Builder`](crate::hybrid::regex::Builder). The main reason
3898 /// to use a DFA directly is if the end location of a match is enough for your
3899 /// use case. Namely, a `Regex` will construct two lazy DFAs instead of one,
3900 /// since a second reverse DFA is needed to find the start of a match.
3901 ///
3902 /// # Example
3903 ///
3904 /// This example shows how to build a lazy DFA that uses a tiny cache capacity
3905 /// and completely disables Unicode. That is:
3906 ///
3907 /// * Things such as `\w`, `.` and `\b` are no longer Unicode-aware. `\w`
3908 /// and `\b` are ASCII-only while `.` matches any byte except for `\n`
3909 /// (instead of any UTF-8 encoding of a Unicode scalar value except for
3910 /// `\n`). Things that are Unicode only, such as `\pL`, are not allowed.
3911 /// * The pattern itself is permitted to match invalid UTF-8. For example,
3912 /// things like `[^a]` that match any byte except for `a` are permitted.
3913 ///
3914 /// ```
3915 /// use regex_automata::{
3916 /// hybrid::dfa::DFA,
3917 /// nfa::thompson,
3918 /// util::syntax,
3919 /// HalfMatch, Input,
3920 /// };
3921 ///
3922 /// let dfa = DFA::builder()
3923 /// .configure(DFA::config().cache_capacity(5_000))
3924 /// .thompson(thompson::Config::new().utf8(false))
3925 /// .syntax(syntax::Config::new().unicode(false).utf8(false))
3926 /// .build(r"foo[^b]ar.*")?;
3927 /// let mut cache = dfa.create_cache();
3928 ///
3929 /// let haystack = b"\xFEfoo\xFFar\xE2\x98\xFF\n";
3930 /// let expected = Some(HalfMatch::must(0, 10));
3931 /// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack))?;
3932 /// assert_eq!(expected, got);
3933 ///
3934 /// # Ok::<(), Box<dyn std::error::Error>>(())
3935 /// ```
3936 #[derive(Clone, Debug)]
3937 pub struct Builder {
3938 config: Config,
3939 #[cfg(feature = "syntax")]
3940 thompson: thompson::Compiler,
3941 }
3942
3943 impl Builder {
3944 /// Create a new lazy DFA builder with the default configuration.
3945 pub fn new() -> Builder {
3946 Builder {
3947 config: Config::default(),
3948 #[cfg(feature = "syntax")]
3949 thompson: thompson::Compiler::new(),
3950 }
3951 }
3952
3953 /// Build a lazy DFA from the given pattern.
3954 ///
3955 /// If there was a problem parsing or compiling the pattern, then an error
3956 /// is returned.
3957 #[cfg(feature = "syntax")]
3958 pub fn build(&self, pattern: &str) -> Result<DFA, BuildError> {
3959 self.build_many(&[pattern])
3960 }
3961
3962 /// Build a lazy DFA from the given patterns.
3963 ///
3964 /// When matches are returned, the pattern ID corresponds to the index of
3965 /// the pattern in the slice given.
3966 #[cfg(feature = "syntax")]
3967 pub fn build_many<P: AsRef<str>>(
3968 &self,
3969 patterns: &[P],
3970 ) -> Result<DFA, BuildError> {
3971 let nfa = self
3972 .thompson
3973 .clone()
3974 // We can always forcefully disable captures because DFAs do not
3975 // support them.
3976 .configure(
3977 thompson::Config::new()
3978 .which_captures(thompson::WhichCaptures::None),
3979 )
3980 .build_many(patterns)
3981 .map_err(BuildError::nfa)?;
3982 self.build_from_nfa(nfa)
3983 }
3984
3985 /// Build a DFA from the given NFA.
3986 ///
3987 /// Note that this requires owning a `thompson::NFA`. While this may force
3988 /// you to clone the NFA, such a clone is not a deep clone. Namely, NFAs
3989 /// are defined internally to support shared ownership such that cloning is
3990 /// very cheap.
3991 ///
3992 /// # Example
3993 ///
3994 /// This example shows how to build a lazy DFA if you already have an NFA
3995 /// in hand.
3996 ///
3997 /// ```
3998 /// use regex_automata::{
3999 /// hybrid::dfa::DFA,
4000 /// nfa::thompson,
4001 /// HalfMatch, Input,
4002 /// };
4003 ///
4004 /// let haystack = "foo123bar";
4005 ///
4006 /// // This shows how to set non-default options for building an NFA.
4007 /// let nfa = thompson::Compiler::new()
4008 /// .configure(thompson::Config::new().shrink(true))
4009 /// .build(r"[0-9]+")?;
4010 /// let dfa = DFA::builder().build_from_nfa(nfa)?;
4011 /// let mut cache = dfa.create_cache();
4012 /// let expected = Some(HalfMatch::must(0, 6));
4013 /// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack))?;
4014 /// assert_eq!(expected, got);
4015 ///
4016 /// # Ok::<(), Box<dyn std::error::Error>>(())
4017 /// ```
4018 pub fn build_from_nfa(
4019 &self,
4020 nfa: thompson::NFA,
4021 ) -> Result<DFA, BuildError> {
4022 let quitset = self.config.quit_set_from_nfa(&nfa)?;
4023 let classes = self.config.byte_classes_from_nfa(&nfa, &quitset);
4024 // Check that we can fit at least a few states into our cache,
4025 // otherwise it's pretty senseless to use the lazy DFA. This does have
4026 // a possible failure mode though. This assumes the maximum size of a
4027 // state in powerset space (so, the total number of NFA states), which
4028 // may never actually materialize, and could be quite a bit larger
4029 // than the actual biggest state. If this turns out to be a problem,
4030 // we could expose a knob that disables this check. But if so, we have
4031 // to be careful not to panic in other areas of the code (the cache
4032 // clearing and init code) that tend to assume some minimum useful
4033 // cache capacity.
4034 let min_cache = minimum_cache_capacity(
4035 &nfa,
4036 &classes,
4037 self.config.get_starts_for_each_pattern(),
4038 );
4039 let mut cache_capacity = self.config.get_cache_capacity();
4040 if cache_capacity < min_cache {
4041 // When the caller has asked us to skip the cache capacity check,
4042 // then we simply force the cache capacity to its minimum amount
4043 // and mush on.
4044 if self.config.get_skip_cache_capacity_check() {
4045 debug!(
4046 "given capacity ({}) is too small, \
4047 since skip_cache_capacity_check is enabled, \
4048 setting cache capacity to minimum ({})",
4049 cache_capacity, min_cache,
4050 );
4051 cache_capacity = min_cache;
4052 } else {
4053 return Err(BuildError::insufficient_cache_capacity(
4054 min_cache,
4055 cache_capacity,
4056 ));
4057 }
4058 }
4059 // We also need to check that we can fit at least some small number
4060 // of states in our state ID space. This is unlikely to trigger in
4061 // >=32-bit systems, but 16-bit systems have a pretty small state ID
4062 // space since a number of bits are used up as sentinels.
4063 if let Err(err) = minimum_lazy_state_id(&classes) {
4064 return Err(BuildError::insufficient_state_id_capacity(err));
4065 }
4066 let stride2 = classes.stride2();
4067 let start_map = StartByteMap::new(nfa.look_matcher());
4068 Ok(DFA {
4069 config: self.config.clone(),
4070 nfa,
4071 stride2,
4072 start_map,
4073 classes,
4074 quitset,
4075 cache_capacity,
4076 })
4077 }
4078
4079 /// Apply the given lazy DFA configuration options to this builder.
4080 pub fn configure(&mut self, config: Config) -> &mut Builder {
4081 self.config = self.config.overwrite(config);
4082 self
4083 }
4084
4085 /// Set the syntax configuration for this builder using
4086 /// [`syntax::Config`](crate::util::syntax::Config).
4087 ///
4088 /// This permits setting things like case insensitivity, Unicode and multi
4089 /// line mode.
4090 ///
4091 /// These settings only apply when constructing a lazy DFA directly from a
4092 /// pattern.
4093 #[cfg(feature = "syntax")]
4094 pub fn syntax(
4095 &mut self,
4096 config: crate::util::syntax::Config,
4097 ) -> &mut Builder {
4098 self.thompson.syntax(config);
4099 self
4100 }
4101
4102 /// Set the Thompson NFA configuration for this builder using
4103 /// [`nfa::thompson::Config`](crate::nfa::thompson::Config).
4104 ///
4105 /// This permits setting things like whether the DFA should match the regex
4106 /// in reverse or if additional time should be spent shrinking the size of
4107 /// the NFA.
4108 ///
4109 /// These settings only apply when constructing a DFA directly from a
4110 /// pattern.
4111 #[cfg(feature = "syntax")]
4112 pub fn thompson(&mut self, config: thompson::Config) -> &mut Builder {
4113 self.thompson.configure(config);
4114 self
4115 }
4116 }
4117
4118 /// Represents the current state of an overlapping search.
4119 ///
4120 /// This is used for overlapping searches since they need to know something
4121 /// about the previous search. For example, when multiple patterns match at the
4122 /// same position, this state tracks the last reported pattern so that the next
4123 /// search knows whether to report another matching pattern or continue with
4124 /// the search at the next position. Additionally, it also tracks which state
4125 /// the last search call terminated in.
4126 ///
4127 /// This type provides little introspection capabilities. The only thing a
4128 /// caller can do is construct it and pass it around to permit search routines
4129 /// to use it to track state, and also ask whether a match has been found.
4130 ///
4131 /// Callers should always provide a fresh state constructed via
4132 /// [`OverlappingState::start`] when starting a new search. Reusing state from
4133 /// a previous search may result in incorrect results.
4134 #[derive(Clone, Debug, Eq, PartialEq)]
4135 pub struct OverlappingState {
4136 /// The match reported by the most recent overlapping search to use this
4137 /// state.
4138 ///
4139 /// If a search does not find any matches, then it is expected to clear
4140 /// this value.
4141 pub(crate) mat: Option<HalfMatch>,
4142 /// The state ID of the state at which the search was in when the call
4143 /// terminated. When this is a match state, `last_match` must be set to a
4144 /// non-None value.
4145 ///
4146 /// A `None` value indicates the start state of the corresponding
4147 /// automaton. We cannot use the actual ID, since any one automaton may
4148 /// have many start states, and which one is in use depends on several
4149 /// search-time factors.
4150 pub(crate) id: Option<LazyStateID>,
4151 /// The position of the search.
4152 ///
4153 /// When `id` is None (i.e., we are starting a search), this is set to
4154 /// the beginning of the search as given by the caller regardless of its
4155 /// current value. Subsequent calls to an overlapping search pick up at
4156 /// this offset.
4157 pub(crate) at: usize,
4158 /// The index into the matching patterns of the next match to report if the
4159 /// current state is a match state. Note that this may be 1 greater than
4160 /// the total number of matches to report for the current match state. (In
4161 /// which case, no more matches should be reported at the current position
4162 /// and the search should advance to the next position.)
4163 pub(crate) next_match_index: Option<usize>,
4164 /// This is set to true when a reverse overlapping search has entered its
4165 /// EOI transitions.
4166 ///
4167 /// This isn't used in a forward search because it knows to stop once the
4168 /// position exceeds the end of the search range. In a reverse search,
4169 /// since we use unsigned offsets, we don't "know" once we've gone past
4170 /// `0`. So the only way to detect it is with this extra flag. The reverse
4171 /// overlapping search knows to terminate specifically after it has
4172 /// reported all matches after following the EOI transition.
4173 pub(crate) rev_eoi: bool,
4174 }
4175
4176 impl OverlappingState {
4177 /// Create a new overlapping state that begins at the start state of any
4178 /// automaton.
4179 pub fn start() -> OverlappingState {
4180 OverlappingState {
4181 mat: None,
4182 id: None,
4183 at: 0,
4184 next_match_index: None,
4185 rev_eoi: false,
4186 }
4187 }
4188
4189 /// Return the match result of the most recent search to execute with this
4190 /// state.
4191 ///
4192 /// A searches will clear this result automatically, such that if no
4193 /// match is found, this will correctly report `None`.
4194 pub fn get_match(&self) -> Option<HalfMatch> {
4195 self.mat
4196 }
4197 }
4198
4199 /// Runs the given overlapping `search` function (forwards or backwards) until
4200 /// a match is found whose offset does not split a codepoint.
4201 ///
4202 /// This is *not* always correct to call. It should only be called when the
4203 /// underlying NFA has UTF-8 mode enabled *and* it can produce zero-width
4204 /// matches. Calling this when both of those things aren't true might result
4205 /// in legitimate matches getting skipped.
4206 #[cold]
4207 #[inline(never)]
4208 fn skip_empty_utf8_splits_overlapping<F>(
4209 input: &Input<'_>,
4210 state: &mut OverlappingState,
4211 mut search: F,
4212 ) -> Result<(), MatchError>
4213 where
4214 F: FnMut(&Input<'_>, &mut OverlappingState) -> Result<(), MatchError>,
4215 {
4216 // Note that this routine works for forwards and reverse searches
4217 // even though there's no code here to handle those cases. That's
4218 // because overlapping searches drive themselves to completion via
4219 // `OverlappingState`. So all we have to do is push it until no matches are
4220 // found.
4221
4222 let mut hm = match state.get_match() {
4223 None => return Ok(()),
4224 Some(hm) => hm,
4225 };
4226 if input.get_anchored().is_anchored() {
4227 if !input.is_char_boundary(hm.offset()) {
4228 state.mat = None;
4229 }
4230 return Ok(());
4231 }
4232 while !input.is_char_boundary(hm.offset()) {
4233 search(input, state)?;
4234 hm = match state.get_match() {
4235 None => return Ok(()),
4236 Some(hm) => hm,
4237 };
4238 }
4239 Ok(())
4240 }
4241
4242 /// Based on the minimum number of states required for a useful lazy DFA cache,
4243 /// this returns the minimum lazy state ID that must be representable.
4244 ///
4245 /// It's not likely for this to have any impact 32-bit systems (or higher), but
4246 /// on 16-bit systems, the lazy state ID space is quite constrained and thus
4247 /// may be insufficient if our MIN_STATES value is (for some reason) too high.
4248 fn minimum_lazy_state_id(
4249 classes: &ByteClasses,
4250 ) -> Result<LazyStateID, LazyStateIDError> {
4251 let stride = 1 << classes.stride2();
4252 let min_state_index = MIN_STATES.checked_sub(1).unwrap();
4253 LazyStateID::new(min_state_index * stride)
4254 }
4255
4256 /// Based on the minimum number of states required for a useful lazy DFA cache,
4257 /// this returns a heuristic minimum number of bytes of heap space required.
4258 ///
4259 /// This is a "heuristic" because the minimum it returns is likely bigger than
4260 /// the true minimum. Namely, it assumes that each powerset NFA/DFA state uses
4261 /// the maximum number of NFA states (all of them). This is likely bigger
4262 /// than what is required in practice. Computing the true minimum effectively
4263 /// requires determinization, which is probably too much work to do for a
4264 /// simple check like this.
4265 ///
4266 /// One of the issues with this approach IMO is that it requires that this
4267 /// be in sync with the calculation above for computing how much heap memory
4268 /// the DFA cache uses. If we get it wrong, it's possible for example for the
4269 /// minimum to be smaller than the computed heap memory, and thus, it may be
4270 /// the case that we can't add the required minimum number of states. That in
4271 /// turn will make lazy DFA panic because we assume that we can add at least a
4272 /// minimum number of states.
4273 ///
4274 /// Another approach would be to always allow the minimum number of states to
4275 /// be added to the lazy DFA cache, even if it exceeds the configured cache
4276 /// limit. This does mean that the limit isn't really a limit in all cases,
4277 /// which is unfortunate. But it does at least guarantee that the lazy DFA can
4278 /// always make progress, even if it is slow. (This approach is very similar to
4279 /// enabling the 'skip_cache_capacity_check' config knob, except it wouldn't
4280 /// rely on cache size calculation. Instead, it would just always permit a
4281 /// minimum number of states to be added.)
4282 fn minimum_cache_capacity(
4283 nfa: &thompson::NFA,
4284 classes: &ByteClasses,
4285 starts_for_each_pattern: bool,
4286 ) -> usize {
4287 const ID_SIZE: usize = size_of::<LazyStateID>();
4288 const STATE_SIZE: usize = size_of::<State>();
4289
4290 let stride = 1 << classes.stride2();
4291 let states_len = nfa.states().len();
4292 let sparses = 2 * states_len * NFAStateID::SIZE;
4293 let trans = MIN_STATES * stride * ID_SIZE;
4294
4295 let mut starts = Start::len() * ID_SIZE;
4296 if starts_for_each_pattern {
4297 starts += (Start::len() * nfa.pattern_len()) * ID_SIZE;
4298 }
4299
4300 // The min number of states HAS to be at least 4: we have 3 sentinel states
4301 // and then we need space for one more when we save a state after clearing
4302 // the cache. We also need space for one more, otherwise we get stuck in a
4303 // loop where we try to add a 5th state, which gets rejected, which clears
4304 // the cache, which adds back a saved state (4th total state) which then
4305 // tries to add the 5th state again.
4306 assert!(MIN_STATES >= 5, "minimum number of states has to be at least 5");
4307 // The minimum number of non-sentinel states. We consider this separately
4308 // because sentinel states are much smaller in that they contain no NFA
4309 // states. Given our aggressive calculation here, it's worth being more
4310 // precise with the number of states we need.
4311 let non_sentinel = MIN_STATES.checked_sub(SENTINEL_STATES).unwrap();
4312
4313 // Every `State` has 5 bytes for flags, 4 bytes (max) for the number of
4314 // patterns, followed by 32-bit encodings of patterns and then delta
4315 // varint encodings of NFA state IDs. We use the worst case (which isn't
4316 // technically possible) of 5 bytes for each NFA state ID.
4317 //
4318 // HOWEVER, three of the states needed by a lazy DFA are just the sentinel
4319 // unknown, dead and quit states. Those states have a known size and it is
4320 // small.
4321 let dead_state_size = State::dead().memory_usage();
4322 let max_state_size = 5 + 4 + (nfa.pattern_len() * 4) + (states_len * 5);
4323 let states = (SENTINEL_STATES * (STATE_SIZE + dead_state_size))
4324 + (non_sentinel * (STATE_SIZE + max_state_size));
4325 // NOTE: We don't double count heap memory used by State for this map since
4326 // we use reference counting to avoid doubling memory usage. (This tends to
4327 // be where most memory is allocated in the cache.)
4328 let states_to_sid = (MIN_STATES * STATE_SIZE) + (MIN_STATES * ID_SIZE);
4329 let stack = states_len * NFAStateID::SIZE;
4330 let scratch_state_builder = max_state_size;
4331
4332 trans
4333 + starts
4334 + states
4335 + states_to_sid
4336 + sparses
4337 + stack
4338 + scratch_state_builder
4339 }
4340
4341 #[cfg(all(test, feature = "syntax"))]
4342 mod tests {
4343 use super::*;
4344
4345 // Tests that we handle heuristic Unicode word boundary support in reverse
4346 // DFAs in the specific case of contextual searches.
4347 //
4348 // I wrote this test when I discovered a bug in how heuristic word
4349 // boundaries were handled. Namely, that the starting state selection
4350 // didn't consider the DFA's quit byte set when looking at the byte
4351 // immediately before the start of the search (or immediately after the
4352 // end of the search in the case of a reverse search). As a result, it was
4353 // possible for '\bfoo\b' to match 'β123' because the trailing \xB2 byte
4354 // in the 'β' codepoint would be treated as a non-word character. But of
4355 // course, this search should trigger the DFA to quit, since there is a
4356 // non-ASCII byte in consideration.
4357 //
4358 // Thus, I fixed 'start_state_{forward,reverse}' to check the quit byte set
4359 // if it wasn't empty. The forward case is tested in the doc test for the
4360 // Config::unicode_word_boundary API. We test the reverse case here, which
4361 // is sufficiently niche that it doesn't really belong in a doc test.
4362 #[test]
4363 fn heuristic_unicode_reverse() {
4364 let dfa = DFA::builder()
4365 .configure(DFA::config().unicode_word_boundary(true))
4366 .thompson(thompson::Config::new().reverse(true))
4367 .build(r"\b[0-9]+\b")
4368 .unwrap();
4369 let mut cache = dfa.create_cache();
4370
4371 let input = Input::new("β123").range(2..);
4372 let expected = MatchError::quit(0xB2, 1);
4373 let got = dfa.try_search_rev(&mut cache, &input);
4374 assert_eq!(Err(expected), got);
4375
4376 let input = Input::new("123β").range(..3);
4377 let expected = MatchError::quit(0xCE, 3);
4378 let got = dfa.try_search_rev(&mut cache, &input);
4379 assert_eq!(Err(expected), got);
4380 }
4381 }