1use crate::{
2 dfa::search,
3 util::{
4 id::{PatternID, StateID},
5 matchtypes::{HalfMatch, MatchError},
6 prefilter,
7 },
8};
9
10/// A trait describing the interface of a deterministic finite automaton (DFA).
11///
12/// The complexity of this trait probably means that it's unlikely for others
13/// to implement it. The primary purpose of the trait is to provide for a way
14/// of abstracting over different types of DFAs. In this crate, that means
15/// dense DFAs and sparse DFAs. (Dense DFAs are fast but memory hungry, where
16/// as sparse DFAs are slower but come with a smaller memory footprint. But
17/// they otherwise provide exactly equivalent expressive power.) For example, a
18/// [`dfa::regex::Regex`](crate::dfa::regex::Regex) is generic over this trait.
19///
20/// Normally, a DFA's execution model is very simple. You might have a single
21/// start state, zero or more final or "match" states and a function that
22/// transitions from one state to the next given the next byte of input.
23/// Unfortunately, the interface described by this trait is significantly
24/// more complicated than this. The complexity has a number of different
25/// reasons, mostly motivated by performance, functionality or space savings:
26///
27/// * A DFA can search for multiple patterns simultaneously. This
28/// means extra information is returned when a match occurs. Namely,
29/// a match is not just an offset, but an offset plus a pattern ID.
30/// [`Automaton::pattern_count`] returns the number of patterns compiled into
31/// the DFA, [`Automaton::match_count`] returns the total number of patterns
32/// that match in a particular state and [`Automaton::match_pattern`] permits
33/// iterating over the patterns that match in a particular state.
34/// * A DFA can have multiple start states, and the choice of which start
35/// state to use depends on the content of the string being searched and
36/// position of the search, as well as whether the search is an anchored
37/// search for a specific pattern in the DFA. Moreover, computing the start
38/// state also depends on whether you're doing a forward or a reverse search.
39/// [`Automaton::start_state_forward`] and [`Automaton::start_state_reverse`]
40/// are used to compute the start state for forward and reverse searches,
41/// respectively.
42/// * All matches are delayed by one byte to support things like `$` and `\b`
43/// at the end of a pattern. Therefore, every use of a DFA is required to use
44/// [`Automaton::next_eoi_state`]
45/// at the end of the search to compute the final transition.
46/// * For optimization reasons, some states are treated specially. Every
47/// state is either special or not, which can be determined via the
48/// [`Automaton::is_special_state`] method. If it's special, then the state
49/// must be at least one of a few possible types of states. (Note that some
50/// types can overlap, for example, a match state can also be an accel state.
51/// But some types can't. If a state is a dead state, then it can never be any
52/// other type of state.) Those types are:
53/// * A dead state. A dead state means the DFA will never enter a match
54/// state. This can be queried via the [`Automaton::is_dead_state`] method.
55/// * A quit state. A quit state occurs if the DFA had to stop the search
56/// prematurely for some reason. This can be queried via the
57/// [`Automaton::is_quit_state`] method.
58/// * A match state. A match state occurs when a match is found. When a DFA
59/// enters a match state, the search may stop immediately (when looking
60/// for the earliest match), or it may continue to find the leftmost-first
61/// match. This can be queried via the [`Automaton::is_match_state`]
62/// method.
63/// * A start state. A start state is where a search begins. For every
64/// search, there is exactly one start state that is used, however, a
65/// DFA may contain many start states. When the search is in a start
66/// state, it may use a prefilter to quickly skip to candidate matches
67/// without executing the DFA on every byte. This can be queried via the
68/// [`Automaton::is_start_state`] method.
69/// * An accel state. An accel state is a state that is accelerated.
70/// That is, it is a state where _most_ of its transitions loop back to
71/// itself and only a small number of transitions lead to other states.
72/// This kind of state is said to be accelerated because a search routine
73/// can quickly look for the bytes leading out of the state instead of
74/// continuing to execute the DFA on each byte. This can be queried via the
75/// [`Automaton::is_accel_state`] method. And the bytes that lead out of
76/// the state can be queried via the [`Automaton::accelerator`] method.
77///
78/// There are a number of provided methods on this trait that implement
79/// efficient searching (for forwards and backwards) with a DFA using all of
80/// the above features of this trait. In particular, given the complexity of
81/// all these features, implementing a search routine in this trait is not
82/// straight forward. If you need to do this for specialized reasons, then
83/// it's recommended to look at the source of this crate. It is intentionally
84/// well commented to help with this. With that said, it is possible to
85/// somewhat simplify the search routine. For example, handling accelerated
86/// states is strictly optional, since it is always correct to assume that
87/// `Automaton::is_accel_state` returns false. However, one complex part of
88/// writing a search routine using this trait is handling the 1-byte delay of a
89/// match. That is not optional.
90///
91/// # Safety
92///
93/// This trait is unsafe to implement because DFA searching may rely on the
94/// correctness of the implementation for memory safety. For example, DFA
95/// searching may use explicit bounds check elision, which will in turn rely
96/// on the correctness of every function that returns a state ID.
97///
98/// When implementing this trait, one must uphold the documented correctness
99/// guarantees. Otherwise, undefined behavior may occur.
100pub unsafe trait Automaton {
101 /// Transitions from the current state to the next state, given the next
102 /// byte of input.
103 ///
104 /// Implementations must guarantee that the returned ID is always a valid
105 /// ID when `current` refers to a valid ID. Moreover, the transition
106 /// function must be defined for all possible values of `input`.
107 ///
108 /// # Panics
109 ///
110 /// If the given ID does not refer to a valid state, then this routine
111 /// may panic but it also may not panic and instead return an invalid ID.
112 /// However, if the caller provides an invalid ID then this must never
113 /// sacrifice memory safety.
114 ///
115 /// # Example
116 ///
117 /// This shows a simplistic example for walking a DFA for a given haystack
118 /// by using the `next_state` method.
119 ///
120 /// ```
121 /// use regex_automata::dfa::{Automaton, dense};
122 ///
123 /// let dfa = dense::DFA::new(r"[a-z]+r")?;
124 /// let haystack = "bar".as_bytes();
125 ///
126 /// // The start state is determined by inspecting the position and the
127 /// // initial bytes of the haystack.
128 /// let mut state = dfa.start_state_forward(
129 /// None, haystack, 0, haystack.len(),
130 /// );
131 /// // Walk all the bytes in the haystack.
132 /// for &b in haystack {
133 /// state = dfa.next_state(state, b);
134 /// }
135 /// // Matches are always delayed by 1 byte, so we must explicitly walk the
136 /// // special "EOI" transition at the end of the search.
137 /// state = dfa.next_eoi_state(state);
138 /// assert!(dfa.is_match_state(state));
139 ///
140 /// # Ok::<(), Box<dyn std::error::Error>>(())
141 /// ```
142 fn next_state(&self, current: StateID, input: u8) -> StateID;
143
144 /// Transitions from the current state to the next state, given the next
145 /// byte of input.
146 ///
147 /// Unlike [`Automaton::next_state`], implementations may implement this
148 /// more efficiently by assuming that the `current` state ID is valid.
149 /// Typically, this manifests by eliding bounds checks.
150 ///
151 /// # Safety
152 ///
153 /// Callers of this method must guarantee that `current` refers to a valid
154 /// state ID. If `current` is not a valid state ID for this automaton, then
155 /// calling this routine may result in undefined behavior.
156 ///
157 /// If `current` is valid, then implementations must guarantee that the ID
158 /// returned is valid for all possible values of `input`.
159 unsafe fn next_state_unchecked(
160 &self,
161 current: StateID,
162 input: u8,
163 ) -> StateID;
164
165 /// Transitions from the current state to the next state for the special
166 /// EOI symbol.
167 ///
168 /// Implementations must guarantee that the returned ID is always a valid
169 /// ID when `current` refers to a valid ID.
170 ///
171 /// This routine must be called at the end of every search in a correct
172 /// implementation of search. Namely, DFAs in this crate delay matches
173 /// by one byte in order to support look-around operators. Thus, after
174 /// reaching the end of a haystack, a search implementation must follow one
175 /// last EOI transition.
176 ///
177 /// It is best to think of EOI as an additional symbol in the alphabet of
178 /// a DFA that is distinct from every other symbol. That is, the alphabet
179 /// of DFAs in this crate has a logical size of 257 instead of 256, where
180 /// 256 corresponds to every possible inhabitant of `u8`. (In practice, the
181 /// physical alphabet size may be smaller because of alphabet compression
182 /// via equivalence classes, but EOI is always represented somehow in the
183 /// alphabet.)
184 ///
185 /// # Panics
186 ///
187 /// If the given ID does not refer to a valid state, then this routine
188 /// may panic but it also may not panic and instead return an invalid ID.
189 /// However, if the caller provides an invalid ID then this must never
190 /// sacrifice memory safety.
191 ///
192 /// # Example
193 ///
194 /// This shows a simplistic example for walking a DFA for a given haystack,
195 /// and then finishing the search with the final EOI transition.
196 ///
197 /// ```
198 /// use regex_automata::dfa::{Automaton, dense};
199 ///
200 /// let dfa = dense::DFA::new(r"[a-z]+r")?;
201 /// let haystack = "bar".as_bytes();
202 ///
203 /// // The start state is determined by inspecting the position and the
204 /// // initial bytes of the haystack.
205 /// let mut state = dfa.start_state_forward(
206 /// None, haystack, 0, haystack.len(),
207 /// );
208 /// // Walk all the bytes in the haystack.
209 /// for &b in haystack {
210 /// state = dfa.next_state(state, b);
211 /// }
212 /// // Matches are always delayed by 1 byte, so we must explicitly walk
213 /// // the special "EOI" transition at the end of the search. Without this
214 /// // final transition, the assert below will fail since the DFA will not
215 /// // have entered a match state yet!
216 /// state = dfa.next_eoi_state(state);
217 /// assert!(dfa.is_match_state(state));
218 ///
219 /// # Ok::<(), Box<dyn std::error::Error>>(())
220 /// ```
221 fn next_eoi_state(&self, current: StateID) -> StateID;
222
223 /// Return the ID of the start state for this DFA when executing a forward
224 /// search.
225 ///
226 /// Unlike typical DFA implementations, the start state for DFAs in this
227 /// crate is dependent on a few different factors:
228 ///
229 /// * The pattern ID, if present. When the underlying DFA has been compiled
230 /// with multiple patterns _and_ the DFA has been configured to compile
231 /// an anchored start state for each pattern, then a pattern ID may be
232 /// specified to execute an anchored search for that specific pattern.
233 /// If `pattern_id` is invalid or if the DFA doesn't have start states
234 /// compiled for each pattern, then implementations must panic. DFAs in
235 /// this crate can be configured to compile start states for each pattern
236 /// via
237 /// [`dense::Config::starts_for_each_pattern`](crate::dfa::dense::Config::starts_for_each_pattern).
238 /// * When `start > 0`, the byte at index `start - 1` may influence the
239 /// start state if the regex uses `^` or `\b`.
240 /// * Similarly, when `start == 0`, it may influence the start state when
241 /// the regex uses `^` or `\A`.
242 /// * Currently, `end` is unused.
243 /// * Whether the search is a forward or reverse search. This routine can
244 /// only be used for forward searches.
245 ///
246 /// # Panics
247 ///
248 /// Implementations must panic if `start..end` is not a valid sub-slice of
249 /// `bytes`. Implementations must also panic if `pattern_id` is non-None
250 /// and does not refer to a valid pattern, or if the DFA was not compiled
251 /// with anchored start states for each pattern.
252 fn start_state_forward(
253 &self,
254 pattern_id: Option<PatternID>,
255 bytes: &[u8],
256 start: usize,
257 end: usize,
258 ) -> StateID;
259
260 /// Return the ID of the start state for this DFA when executing a reverse
261 /// search.
262 ///
263 /// Unlike typical DFA implementations, the start state for DFAs in this
264 /// crate is dependent on a few different factors:
265 ///
266 /// * The pattern ID, if present. When the underlying DFA has been compiled
267 /// with multiple patterns _and_ the DFA has been configured to compile an
268 /// anchored start state for each pattern, then a pattern ID may be
269 /// specified to execute an anchored search for that specific pattern. If
270 /// `pattern_id` is invalid or if the DFA doesn't have start states compiled
271 /// for each pattern, then implementations must panic. DFAs in this crate
272 /// can be configured to compile start states for each pattern via
273 /// [`dense::Config::starts_for_each_pattern`](crate::dfa::dense::Config::starts_for_each_pattern).
274 /// * When `end < bytes.len()`, the byte at index `end` may influence the
275 /// start state if the regex uses `$` or `\b`.
276 /// * Similarly, when `end == bytes.len()`, it may influence the start
277 /// state when the regex uses `$` or `\z`.
278 /// * Currently, `start` is unused.
279 /// * Whether the search is a forward or reverse search. This routine can
280 /// only be used for reverse searches.
281 ///
282 /// # Panics
283 ///
284 /// Implementations must panic if `start..end` is not a valid sub-slice of
285 /// `bytes`. Implementations must also panic if `pattern_id` is non-None
286 /// and does not refer to a valid pattern, or if the DFA was not compiled
287 /// with anchored start states for each pattern.
288 fn start_state_reverse(
289 &self,
290 pattern_id: Option<PatternID>,
291 bytes: &[u8],
292 start: usize,
293 end: usize,
294 ) -> StateID;
295
296 /// Returns true if and only if the given identifier corresponds to a
297 /// "special" state. A special state is one or more of the following:
298 /// a dead state, a quit state, a match state, a start state or an
299 /// accelerated state.
300 ///
301 /// A correct implementation _may_ always return false for states that
302 /// are either start states or accelerated states, since that information
303 /// is only intended to be used for optimization purposes. Correct
304 /// implementations must return true if the state is a dead, quit or match
305 /// state. This is because search routines using this trait must be able
306 /// to rely on `is_special_state` as an indicator that a state may need
307 /// special treatment. (For example, when a search routine sees a dead
308 /// state, it must terminate.)
309 ///
310 /// This routine permits search implementations to use a single branch to
311 /// check whether a state needs special attention before executing the next
312 /// transition. The example below shows how to do this.
313 ///
314 /// # Example
315 ///
316 /// This example shows how `is_special_state` can be used to implement a
317 /// correct search routine with minimal branching. In particular, this
318 /// search routine implements "leftmost" matching, which means that it
319 /// doesn't immediately stop once a match is found. Instead, it continues
320 /// until it reaches a dead state.
321 ///
322 /// ```
323 /// use regex_automata::{
324 /// dfa::{Automaton, dense},
325 /// HalfMatch, MatchError, PatternID,
326 /// };
327 ///
328 /// fn find_leftmost_first<A: Automaton>(
329 /// dfa: &A,
330 /// haystack: &[u8],
331 /// ) -> Result<Option<HalfMatch>, MatchError> {
332 /// // The start state is determined by inspecting the position and the
333 /// // initial bytes of the haystack. Note that start states can never
334 /// // be match states (since DFAs in this crate delay matches by 1
335 /// // byte), so we don't need to check if the start state is a match.
336 /// let mut state = dfa.start_state_forward(
337 /// None, haystack, 0, haystack.len(),
338 /// );
339 /// let mut last_match = None;
340 /// // Walk all the bytes in the haystack. We can quit early if we see
341 /// // a dead or a quit state. The former means the automaton will
342 /// // never transition to any other state. The latter means that the
343 /// // automaton entered a condition in which its search failed.
344 /// for (i, &b) in haystack.iter().enumerate() {
345 /// state = dfa.next_state(state, b);
346 /// if dfa.is_special_state(state) {
347 /// if dfa.is_match_state(state) {
348 /// last_match = Some(HalfMatch::new(
349 /// dfa.match_pattern(state, 0),
350 /// i,
351 /// ));
352 /// } else if dfa.is_dead_state(state) {
353 /// return Ok(last_match);
354 /// } else if dfa.is_quit_state(state) {
355 /// // It is possible to enter into a quit state after
356 /// // observing a match has occurred. In that case, we
357 /// // should return the match instead of an error.
358 /// if last_match.is_some() {
359 /// return Ok(last_match);
360 /// }
361 /// return Err(MatchError::Quit { byte: b, offset: i });
362 /// }
363 /// // Implementors may also want to check for start or accel
364 /// // states and handle them differently for performance
365 /// // reasons. But it is not necessary for correctness.
366 /// }
367 /// }
368 /// // Matches are always delayed by 1 byte, so we must explicitly walk
369 /// // the special "EOI" transition at the end of the search.
370 /// state = dfa.next_eoi_state(state);
371 /// if dfa.is_match_state(state) {
372 /// last_match = Some(HalfMatch::new(
373 /// dfa.match_pattern(state, 0),
374 /// haystack.len(),
375 /// ));
376 /// }
377 /// Ok(last_match)
378 /// }
379 ///
380 /// // We use a greedy '+' operator to show how the search doesn't just
381 /// // stop once a match is detected. It continues extending the match.
382 /// // Using '[a-z]+?' would also work as expected and stop the search
383 /// // early. Greediness is built into the automaton.
384 /// let dfa = dense::DFA::new(r"[a-z]+")?;
385 /// let haystack = "123 foobar 4567".as_bytes();
386 /// let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
387 /// assert_eq!(mat.pattern().as_usize(), 0);
388 /// assert_eq!(mat.offset(), 10);
389 ///
390 /// // Here's another example that tests our handling of the special EOI
391 /// // transition. This will fail to find a match if we don't call
392 /// // 'next_eoi_state' at the end of the search since the match isn't
393 /// // found until the final byte in the haystack.
394 /// let dfa = dense::DFA::new(r"[0-9]{4}")?;
395 /// let haystack = "123 foobar 4567".as_bytes();
396 /// let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
397 /// assert_eq!(mat.pattern().as_usize(), 0);
398 /// assert_eq!(mat.offset(), 15);
399 ///
400 /// // And note that our search implementation above automatically works
401 /// // with multi-DFAs. Namely, `dfa.match_pattern(match_state, 0)` selects
402 /// // the appropriate pattern ID for us.
403 /// let dfa = dense::DFA::new_many(&[r"[a-z]+", r"[0-9]+"])?;
404 /// let haystack = "123 foobar 4567".as_bytes();
405 /// let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
406 /// assert_eq!(mat.pattern().as_usize(), 1);
407 /// assert_eq!(mat.offset(), 3);
408 /// let mat = find_leftmost_first(&dfa, &haystack[3..])?.unwrap();
409 /// assert_eq!(mat.pattern().as_usize(), 0);
410 /// assert_eq!(mat.offset(), 7);
411 /// let mat = find_leftmost_first(&dfa, &haystack[10..])?.unwrap();
412 /// assert_eq!(mat.pattern().as_usize(), 1);
413 /// assert_eq!(mat.offset(), 5);
414 ///
415 /// # Ok::<(), Box<dyn std::error::Error>>(())
416 /// ```
417 fn is_special_state(&self, id: StateID) -> bool;
418
419 /// Returns true if and only if the given identifier corresponds to a dead
420 /// state. When a DFA enters a dead state, it is impossible to leave. That
421 /// is, every transition on a dead state by definition leads back to the
422 /// same dead state.
423 ///
424 /// In practice, the dead state always corresponds to the identifier `0`.
425 /// Moreover, in practice, there is only one dead state.
426 ///
427 /// The existence of a dead state is not strictly required in the classical
428 /// model of finite state machines, where one generally only cares about
429 /// the question of whether an input sequence matches or not. Dead states
430 /// are not needed to answer that question, since one can immediately quit
431 /// as soon as one enters a final or "match" state. However, we don't just
432 /// care about matches but also care about the location of matches, and
433 /// more specifically, care about semantics like "greedy" matching.
434 ///
435 /// For example, given the pattern `a+` and the input `aaaz`, the dead
436 /// state won't be entered until the state machine reaches `z` in the
437 /// input, at which point, the search routine can quit. But without the
438 /// dead state, the search routine wouldn't know when to quit. In a
439 /// classical representation, the search routine would stop after seeing
440 /// the first `a` (which is when the search would enter a match state). But
441 /// this wouldn't implement "greedy" matching where `a+` matches as many
442 /// `a`'s as possible.
443 ///
444 /// # Example
445 ///
446 /// See the example for [`Automaton::is_special_state`] for how to use this
447 /// method correctly.
448 fn is_dead_state(&self, id: StateID) -> bool;
449
450 /// Returns true if and only if the given identifier corresponds to a quit
451 /// state. A quit state is like a dead state (it has no transitions other
452 /// than to itself), except it indicates that the DFA failed to complete
453 /// the search. When this occurs, callers can neither accept or reject that
454 /// a match occurred.
455 ///
456 /// In practice, the quit state always corresponds to the state immediately
457 /// following the dead state. (Which is not usually represented by `1`,
458 /// since state identifiers are pre-multiplied by the state machine's
459 /// alphabet stride, and the alphabet stride varies between DFAs.)
460 ///
461 /// By default, state machines created by this crate will never enter a
462 /// quit state. Since entering a quit state is the only way for a DFA
463 /// in this crate to fail at search time, it follows that the default
464 /// configuration can never produce a match error. Nevertheless, handling
465 /// quit states is necessary to correctly support all configurations in
466 /// this crate.
467 ///
468 /// The typical way in which a quit state can occur is when heuristic
469 /// support for Unicode word boundaries is enabled via the
470 /// [`dense::Config::unicode_word_boundary`](crate::dfa::dense::Config::unicode_word_boundary)
471 /// option. But other options, like the lower level
472 /// [`dense::Config::quit`](crate::dfa::dense::Config::quit)
473 /// configuration, can also result in a quit state being entered. The
474 /// purpose of the quit state is to provide a way to execute a fast DFA
475 /// in common cases while delegating to slower routines when the DFA quits.
476 ///
477 /// The default search implementations provided by this crate will return
478 /// a [`MatchError::Quit`](crate::MatchError::Quit) error when a quit state
479 /// is entered.
480 ///
481 /// # Example
482 ///
483 /// See the example for [`Automaton::is_special_state`] for how to use this
484 /// method correctly.
485 fn is_quit_state(&self, id: StateID) -> bool;
486
487 /// Returns true if and only if the given identifier corresponds to a
488 /// match state. A match state is also referred to as a "final" state and
489 /// indicates that a match has been found.
490 ///
491 /// If all you care about is whether a particular pattern matches in the
492 /// input sequence, then a search routine can quit early as soon as the
493 /// machine enters a match state. However, if you're looking for the
494 /// standard "leftmost-first" match location, then search _must_ continue
495 /// until either the end of the input or until the machine enters a dead
496 /// state. (Since either condition implies that no other useful work can
497 /// be done.) Namely, when looking for the location of a match, then
498 /// search implementations should record the most recent location in
499 /// which a match state was entered, but otherwise continue executing the
500 /// search as normal. (The search may even leave the match state.) Once
501 /// the termination condition is reached, the most recently recorded match
502 /// location should be returned.
503 ///
504 /// Finally, one additional power given to match states in this crate
505 /// is that they are always associated with a specific pattern in order
506 /// to support multi-DFAs. See [`Automaton::match_pattern`] for more
507 /// details and an example for how to query the pattern associated with a
508 /// particular match state.
509 ///
510 /// # Example
511 ///
512 /// See the example for [`Automaton::is_special_state`] for how to use this
513 /// method correctly.
514 fn is_match_state(&self, id: StateID) -> bool;
515
516 /// Returns true if and only if the given identifier corresponds to a
517 /// start state. A start state is a state in which a DFA begins a search.
518 /// All searches begin in a start state. Moreover, since all matches are
519 /// delayed by one byte, a start state can never be a match state.
520 ///
521 /// The main role of a start state is, as mentioned, to be a starting
522 /// point for a DFA. This starting point is determined via one of
523 /// [`Automaton::start_state_forward`] or
524 /// [`Automaton::start_state_reverse`], depending on whether one is doing
525 /// a forward or a reverse search, respectively.
526 ///
527 /// A secondary use of start states is for prefix acceleration. Namely,
528 /// while executing a search, if one detects that you're in a start state,
529 /// then it may be faster to look for the next match of a prefix of the
530 /// pattern, if one exists. If a prefix exists and since all matches must
531 /// begin with that prefix, then skipping ahead to occurrences of that
532 /// prefix may be much faster than executing the DFA.
533 ///
534 /// # Example
535 ///
536 /// This example shows how to implement your own search routine that does
537 /// a prefix search whenever the search enters a start state.
538 ///
539 /// Note that you do not need to implement your own search routine to
540 /// make use of prefilters like this. The search routines provided
541 /// by this crate already implement prefilter support via the
542 /// [`Prefilter`](crate::util::prefilter::Prefilter) trait. The various
543 /// `find_*_at` routines on this trait support the `Prefilter` trait
544 /// through [`Scanner`](crate::util::prefilter::Scanner)s. This example is
545 /// meant to show how you might deal with prefilters in a simplified case
546 /// if you are implementing your own search routine.
547 ///
548 /// ```
549 /// use regex_automata::{
550 /// MatchError, PatternID,
551 /// dfa::{Automaton, dense},
552 /// HalfMatch,
553 /// };
554 ///
555 /// fn find_byte(slice: &[u8], at: usize, byte: u8) -> Option<usize> {
556 /// // Would be faster to use the memchr crate, but this is still
557 /// // faster than running through the DFA.
558 /// slice[at..].iter().position(|&b| b == byte).map(|i| at + i)
559 /// }
560 ///
561 /// fn find_leftmost_first<A: Automaton>(
562 /// dfa: &A,
563 /// haystack: &[u8],
564 /// prefix_byte: Option<u8>,
565 /// ) -> Result<Option<HalfMatch>, MatchError> {
566 /// // See the Automaton::is_special_state example for similar code
567 /// // with more comments.
568 ///
569 /// let mut state = dfa.start_state_forward(
570 /// None, haystack, 0, haystack.len(),
571 /// );
572 /// let mut last_match = None;
573 /// let mut pos = 0;
574 /// while pos < haystack.len() {
575 /// let b = haystack[pos];
576 /// state = dfa.next_state(state, b);
577 /// pos += 1;
578 /// if dfa.is_special_state(state) {
579 /// if dfa.is_match_state(state) {
580 /// last_match = Some(HalfMatch::new(
581 /// dfa.match_pattern(state, 0),
582 /// pos - 1,
583 /// ));
584 /// } else if dfa.is_dead_state(state) {
585 /// return Ok(last_match);
586 /// } else if dfa.is_quit_state(state) {
587 /// // It is possible to enter into a quit state after
588 /// // observing a match has occurred. In that case, we
589 /// // should return the match instead of an error.
590 /// if last_match.is_some() {
591 /// return Ok(last_match);
592 /// }
593 /// return Err(MatchError::Quit {
594 /// byte: b, offset: pos - 1,
595 /// });
596 /// } else if dfa.is_start_state(state) {
597 /// // If we're in a start state and know all matches begin
598 /// // with a particular byte, then we can quickly skip to
599 /// // candidate matches without running the DFA through
600 /// // every byte inbetween.
601 /// if let Some(prefix_byte) = prefix_byte {
602 /// pos = match find_byte(haystack, pos, prefix_byte) {
603 /// Some(pos) => pos,
604 /// None => break,
605 /// };
606 /// }
607 /// }
608 /// }
609 /// }
610 /// // Matches are always delayed by 1 byte, so we must explicitly walk
611 /// // the special "EOI" transition at the end of the search.
612 /// state = dfa.next_eoi_state(state);
613 /// if dfa.is_match_state(state) {
614 /// last_match = Some(HalfMatch::new(
615 /// dfa.match_pattern(state, 0),
616 /// haystack.len(),
617 /// ));
618 /// }
619 /// Ok(last_match)
620 /// }
621 ///
622 /// // In this example, it's obvious that all occurrences of our pattern
623 /// // begin with 'Z', so we pass in 'Z'.
624 /// let dfa = dense::DFA::new(r"Z[a-z]+")?;
625 /// let haystack = "123 foobar Zbaz quux".as_bytes();
626 /// let mat = find_leftmost_first(&dfa, haystack, Some(b'Z'))?.unwrap();
627 /// assert_eq!(mat.pattern().as_usize(), 0);
628 /// assert_eq!(mat.offset(), 15);
629 ///
630 /// // But note that we don't need to pass in a prefix byte. If we don't,
631 /// // then the search routine does no acceleration.
632 /// let mat = find_leftmost_first(&dfa, haystack, None)?.unwrap();
633 /// assert_eq!(mat.pattern().as_usize(), 0);
634 /// assert_eq!(mat.offset(), 15);
635 ///
636 /// // However, if we pass an incorrect byte, then the prefix search will
637 /// // result in incorrect results.
638 /// assert_eq!(find_leftmost_first(&dfa, haystack, Some(b'X'))?, None);
639 ///
640 /// # Ok::<(), Box<dyn std::error::Error>>(())
641 /// ```
642 fn is_start_state(&self, id: StateID) -> bool;
643
644 /// Returns true if and only if the given identifier corresponds to an
645 /// accelerated state.
646 ///
647 /// An accelerated state is a special optimization
648 /// trick implemented by this crate. Namely, if
649 /// [`dense::Config::accelerate`](crate::dfa::dense::Config::accelerate) is
650 /// enabled (and it is by default), then DFAs generated by this crate will
651 /// tag states meeting certain characteristics as accelerated. States meet
652 /// this criteria whenever most of their transitions are self-transitions.
653 /// That is, transitions that loop back to the same state. When a small
654 /// number of transitions aren't self-transitions, then it follows that
655 /// there are only a small number of bytes that can cause the DFA to leave
656 /// that state. Thus, there is an opportunity to look for those bytes
657 /// using more optimized routines rather than continuing to run through
658 /// the DFA. This trick is similar to the prefilter idea described in
659 /// the documentation of [`Automaton::is_start_state`] with two main
660 /// differences:
661 ///
662 /// 1. It is more limited since acceleration only applies to single bytes.
663 /// This means states are rarely accelerated when Unicode mode is enabled
664 /// (which is enabled by default).
665 /// 2. It can occur anywhere in the DFA, which increases optimization
666 /// opportunities.
667 ///
668 /// Like the prefilter idea, the main downside (and a possible reason to
669 /// disable it) is that it can lead to worse performance in some cases.
670 /// Namely, if a state is accelerated for very common bytes, then the
671 /// overhead of checking for acceleration and using the more optimized
672 /// routines to look for those bytes can cause overall performance to be
673 /// worse than if acceleration wasn't enabled at all.
674 ///
675 /// A simple example of a regex that has an accelerated state is
676 /// `(?-u)[^a]+a`. Namely, the `[^a]+` sub-expression gets compiled down
677 /// into a single state where all transitions except for `a` loop back to
678 /// itself, and where `a` is the only transition (other than the special
679 /// EOI transition) that goes to some other state. Thus, this state can
680 /// be accelerated and implemented more efficiently by calling an
681 /// optimized routine like `memchr` with `a` as the needle. Notice that
682 /// the `(?-u)` to disable Unicode is necessary here, as without it,
683 /// `[^a]` will match any UTF-8 encoding of any Unicode scalar value other
684 /// than `a`. This more complicated expression compiles down to many DFA
685 /// states and the simple acceleration optimization is no longer available.
686 ///
687 /// Typically, this routine is used to guard calls to
688 /// [`Automaton::accelerator`], which returns the accelerated bytes for
689 /// the specified state.
690 fn is_accel_state(&self, id: StateID) -> bool;
691
692 /// Returns the total number of patterns compiled into this DFA.
693 ///
694 /// In the case of a DFA that contains no patterns, this must return `0`.
695 ///
696 /// # Example
697 ///
698 /// This example shows the pattern count for a DFA that never matches:
699 ///
700 /// ```
701 /// use regex_automata::dfa::{Automaton, dense::DFA};
702 ///
703 /// let dfa: DFA<Vec<u32>> = DFA::never_match()?;
704 /// assert_eq!(dfa.pattern_count(), 0);
705 /// # Ok::<(), Box<dyn std::error::Error>>(())
706 /// ```
707 ///
708 /// And another example for a DFA that matches at every position:
709 ///
710 /// ```
711 /// use regex_automata::dfa::{Automaton, dense::DFA};
712 ///
713 /// let dfa: DFA<Vec<u32>> = DFA::always_match()?;
714 /// assert_eq!(dfa.pattern_count(), 1);
715 /// # Ok::<(), Box<dyn std::error::Error>>(())
716 /// ```
717 ///
718 /// And finally, a DFA that was constructed from multiple patterns:
719 ///
720 /// ```
721 /// use regex_automata::dfa::{Automaton, dense::DFA};
722 ///
723 /// let dfa = DFA::new_many(&["[0-9]+", "[a-z]+", "[A-Z]+"])?;
724 /// assert_eq!(dfa.pattern_count(), 3);
725 /// # Ok::<(), Box<dyn std::error::Error>>(())
726 /// ```
727 fn pattern_count(&self) -> usize;
728
729 /// Returns the total number of patterns that match in this state.
730 ///
731 /// If the given state is not a match state, then implementations may
732 /// panic.
733 ///
734 /// If the DFA was compiled with one pattern, then this must necessarily
735 /// always return `1` for all match states.
736 ///
737 /// Implementations must guarantee that [`Automaton::match_pattern`] can
738 /// be called with indices up to (but not including) the count returned by
739 /// this routine without panicking.
740 ///
741 /// # Panics
742 ///
743 /// Implementations are permitted to panic if the provided state ID does
744 /// not correspond to a match state.
745 ///
746 /// # Example
747 ///
748 /// This example shows a simple instance of implementing overlapping
749 /// matches. In particular, it shows not only how to determine how many
750 /// patterns have matched in a particular state, but also how to access
751 /// which specific patterns have matched.
752 ///
753 /// Notice that we must use [`MatchKind::All`](crate::MatchKind::All)
754 /// when building the DFA. If we used
755 /// [`MatchKind::LeftmostFirst`](crate::MatchKind::LeftmostFirst)
756 /// instead, then the DFA would not be constructed in a way that supports
757 /// overlapping matches. (It would only report a single pattern that
758 /// matches at any particular point in time.)
759 ///
760 /// Another thing to take note of is the patterns used and the order in
761 /// which the pattern IDs are reported. In the example below, pattern `3`
762 /// is yielded first. Why? Because it corresponds to the match that
763 /// appears first. Namely, the `@` symbol is part of `\S+` but not part
764 /// of any of the other patterns. Since the `\S+` pattern has a match that
765 /// starts to the left of any other pattern, its ID is returned before any
766 /// other.
767 ///
768 /// ```
769 /// use regex_automata::{
770 /// dfa::{Automaton, dense},
771 /// MatchKind,
772 /// };
773 ///
774 /// let dfa = dense::Builder::new()
775 /// .configure(dense::Config::new().match_kind(MatchKind::All))
776 /// .build_many(&[
777 /// r"\w+", r"[a-z]+", r"[A-Z]+", r"\S+",
778 /// ])?;
779 /// let haystack = "@bar".as_bytes();
780 ///
781 /// // The start state is determined by inspecting the position and the
782 /// // initial bytes of the haystack.
783 /// let mut state = dfa.start_state_forward(
784 /// None, haystack, 0, haystack.len(),
785 /// );
786 /// // Walk all the bytes in the haystack.
787 /// for &b in haystack {
788 /// state = dfa.next_state(state, b);
789 /// }
790 /// state = dfa.next_eoi_state(state);
791 ///
792 /// assert!(dfa.is_match_state(state));
793 /// assert_eq!(dfa.match_count(state), 3);
794 /// // The following calls are guaranteed to not panic since `match_count`
795 /// // returned `3` above.
796 /// assert_eq!(dfa.match_pattern(state, 0).as_usize(), 3);
797 /// assert_eq!(dfa.match_pattern(state, 1).as_usize(), 0);
798 /// assert_eq!(dfa.match_pattern(state, 2).as_usize(), 1);
799 ///
800 /// # Ok::<(), Box<dyn std::error::Error>>(())
801 /// ```
802 fn match_count(&self, id: StateID) -> usize;
803
804 /// Returns the pattern ID corresponding to the given match index in the
805 /// given state.
806 ///
807 /// See [`Automaton::match_count`] for an example of how to use this
808 /// method correctly. Note that if you know your DFA is compiled with a
809 /// single pattern, then this routine is never necessary since it will
810 /// always return a pattern ID of `0` for an index of `0` when `id`
811 /// corresponds to a match state.
812 ///
813 /// Typically, this routine is used when implementing an overlapping
814 /// search, as the example for `Automaton::match_count` does.
815 ///
816 /// # Panics
817 ///
818 /// If the state ID is not a match state or if the match index is out
819 /// of bounds for the given state, then this routine may either panic
820 /// or produce an incorrect result. If the state ID is correct and the
821 /// match index is correct, then this routine must always produce a valid
822 /// `PatternID`.
823 fn match_pattern(&self, id: StateID, index: usize) -> PatternID;
824
825 /// Return a slice of bytes to accelerate for the given state, if possible.
826 ///
827 /// If the given state has no accelerator, then an empty slice must be
828 /// returned. If `Automaton::is_accel_state` returns true for the given
829 /// ID, then this routine _must_ return a non-empty slice, but it is not
830 /// required to do so.
831 ///
832 /// If the given ID is not a valid state ID for this automaton, then
833 /// implementations may panic or produce incorrect results.
834 ///
835 /// See [`Automaton::is_accel_state`] for more details on state
836 /// acceleration.
837 ///
838 /// By default, this method will always return an empty slice.
839 ///
840 /// # Example
841 ///
842 /// This example shows a contrived case in which we build a regex that we
843 /// know is accelerated and extract the accelerator from a state.
844 ///
845 /// ```
846 /// use regex_automata::{
847 /// nfa::thompson,
848 /// dfa::{Automaton, dense},
849 /// util::id::StateID,
850 /// SyntaxConfig,
851 /// };
852 ///
853 /// let dfa = dense::Builder::new()
854 /// // We disable Unicode everywhere and permit the regex to match
855 /// // invalid UTF-8. e.g., `[^abc]` matches `\xFF`, which is not valid
856 /// // UTF-8.
857 /// .syntax(SyntaxConfig::new().unicode(false).utf8(false))
858 /// // This makes the implicit `(?s:.)*?` prefix added to the regex
859 /// // match through arbitrary bytes instead of being UTF-8 aware. This
860 /// // isn't necessary to get acceleration to work in this case, but
861 /// // it does make the DFA substantially simpler.
862 /// .thompson(thompson::Config::new().utf8(false))
863 /// .build("[^abc]+a")?;
864 ///
865 /// // Here we just pluck out the state that we know is accelerated.
866 /// // While the stride calculations are something that can be relied
867 /// // on by callers, the specific position of the accelerated state is
868 /// // implementation defined.
869 /// //
870 /// // N.B. We get '3' by inspecting the state machine using 'regex-cli'.
871 /// // e.g., try `regex-cli debug dfa dense '[^abc]+a' -BbUC`.
872 /// let id = StateID::new(3 * dfa.stride()).unwrap();
873 /// let accelerator = dfa.accelerator(id);
874 /// // The `[^abc]+` sub-expression permits [a, b, c] to be accelerated.
875 /// assert_eq!(accelerator, &[b'a', b'b', b'c']);
876 /// # Ok::<(), Box<dyn std::error::Error>>(())
877 /// ```
878 fn accelerator(&self, _id: StateID) -> &[u8] {
879 &[]
880 }
881
882 /// Executes a forward search and returns the end position of the first
883 /// match that is found as early as possible. If no match exists, then
884 /// `None` is returned.
885 ///
886 /// This routine stops scanning input as soon as the search observes a
887 /// match state. This is useful for implementing boolean `is_match`-like
888 /// routines, where as little work is done as possible.
889 ///
890 /// See [`Automaton::find_earliest_fwd_at`] for additional functionality,
891 /// such as providing a prefilter, a specific pattern to match and the
892 /// bounds of the search within the haystack. This routine is meant as
893 /// a convenience for common cases where the additional functionality is
894 /// not needed.
895 ///
896 /// # Errors
897 ///
898 /// This routine only errors if the search could not complete. For
899 /// DFAs generated by this crate, this only occurs in a non-default
900 /// configuration where quit bytes are used or Unicode word boundaries are
901 /// heuristically enabled.
902 ///
903 /// When a search cannot complete, callers cannot know whether a match
904 /// exists or not.
905 ///
906 /// # Example
907 ///
908 /// This example shows how to use this method with a
909 /// [`dense::DFA`](crate::dfa::dense::DFA). In particular, it demonstrates
910 /// how the position returned might differ from what one might expect when
911 /// executing a traditional leftmost search.
912 ///
913 /// ```
914 /// use regex_automata::{
915 /// dfa::{Automaton, dense},
916 /// HalfMatch,
917 /// };
918 ///
919 /// let dfa = dense::DFA::new("foo[0-9]+")?;
920 /// // Normally, the end of the leftmost first match here would be 8,
921 /// // corresponding to the end of the input. But the "earliest" semantics
922 /// // this routine cause it to stop as soon as a match is known, which
923 /// // occurs once 'foo[0-9]' has matched.
924 /// let expected = HalfMatch::must(0, 4);
925 /// assert_eq!(Some(expected), dfa.find_earliest_fwd(b"foo12345")?);
926 ///
927 /// let dfa = dense::DFA::new("abc|a")?;
928 /// // Normally, the end of the leftmost first match here would be 3,
929 /// // but the shortest match semantics detect a match earlier.
930 /// let expected = HalfMatch::must(0, 1);
931 /// assert_eq!(Some(expected), dfa.find_earliest_fwd(b"abc")?);
932 /// # Ok::<(), Box<dyn std::error::Error>>(())
933 /// ```
934 #[inline]
935 fn find_earliest_fwd(
936 &self,
937 bytes: &[u8],
938 ) -> Result<Option<HalfMatch>, MatchError> {
939 self.find_earliest_fwd_at(None, None, bytes, 0, bytes.len())
940 }
941
942 /// Executes a reverse search and returns the start position of the first
943 /// match that is found as early as possible. If no match exists, then
944 /// `None` is returned.
945 ///
946 /// This routine stops scanning input as soon as the search observes a
947 /// match state.
948 ///
949 /// Note that while it is not technically necessary to build a reverse
950 /// automaton to use a reverse search, it is likely that you'll want to do
951 /// so. Namely, the typical use of a reverse search is to find the starting
952 /// location of a match once its end is discovered from a forward search. A
953 /// reverse DFA automaton can be built by configuring the intermediate NFA
954 /// to be reversed via
955 /// [`nfa::thompson::Config::reverse`](crate::nfa::thompson::Config::reverse).
956 ///
957 /// # Errors
958 ///
959 /// This routine only errors if the search could not complete. For
960 /// DFAs generated by this crate, this only occurs in a non-default
961 /// configuration where quit bytes are used or Unicode word boundaries are
962 /// heuristically enabled.
963 ///
964 /// When a search cannot complete, callers cannot know whether a match
965 /// exists or not.
966 ///
967 /// # Example
968 ///
969 /// This example shows how to use this method with a
970 /// [`dense::DFA`](crate::dfa::dense::DFA). In particular, it demonstrates
971 /// how the position returned might differ from what one might expect when
972 /// executing a traditional leftmost reverse search.
973 ///
974 /// ```
975 /// use regex_automata::{
976 /// nfa::thompson,
977 /// dfa::{Automaton, dense},
978 /// HalfMatch,
979 /// };
980 ///
981 /// let dfa = dense::Builder::new()
982 /// .thompson(thompson::Config::new().reverse(true))
983 /// .build("[a-z]+[0-9]+")?;
984 /// // Normally, the end of the leftmost first match here would be 0,
985 /// // corresponding to the beginning of the input. But the "earliest"
986 /// // semantics of this routine cause it to stop as soon as a match is
987 /// // known, which occurs once '[a-z][0-9]+' has matched.
988 /// let expected = HalfMatch::must(0, 2);
989 /// assert_eq!(Some(expected), dfa.find_earliest_rev(b"foo12345")?);
990 ///
991 /// let dfa = dense::Builder::new()
992 /// .thompson(thompson::Config::new().reverse(true))
993 /// .build("abc|c")?;
994 /// // Normally, the end of the leftmost first match here would be 0,
995 /// // but the shortest match semantics detect a match earlier.
996 /// let expected = HalfMatch::must(0, 2);
997 /// assert_eq!(Some(expected), dfa.find_earliest_rev(b"abc")?);
998 /// # Ok::<(), Box<dyn std::error::Error>>(())
999 /// ```
1000 #[inline]
1001 fn find_earliest_rev(
1002 &self,
1003 bytes: &[u8],
1004 ) -> Result<Option<HalfMatch>, MatchError> {
1005 self.find_earliest_rev_at(None, bytes, 0, bytes.len())
1006 }
1007
1008 /// Executes a forward search and returns the end position of the leftmost
1009 /// match that is found. If no match exists, then `None` is returned.
1010 ///
1011 /// # Errors
1012 ///
1013 /// This routine only errors if the search could not complete. For
1014 /// DFAs generated by this crate, this only occurs in a non-default
1015 /// configuration where quit bytes are used or Unicode word boundaries are
1016 /// heuristically enabled.
1017 ///
1018 /// When a search cannot complete, callers cannot know whether a match
1019 /// exists or not.
1020 ///
1021 /// # Notes for implementors
1022 ///
1023 /// Implementors of this trait are not required to implement any particular
1024 /// match semantics (such as leftmost-first), which are instead manifest in
1025 /// the DFA's transitions.
1026 ///
1027 /// In particular, this method must continue searching even after it enters
1028 /// a match state. The search should only terminate once it has reached
1029 /// the end of the input or when it has entered a dead or quit state. Upon
1030 /// termination, the position of the last byte seen while still in a match
1031 /// state is returned.
1032 ///
1033 /// Since this trait provides an implementation for this method by default,
1034 /// it's unlikely that one will need to implement this.
1035 ///
1036 /// # Example
1037 ///
1038 /// This example shows how to use this method with a
1039 /// [`dense::DFA`](crate::dfa::dense::DFA). By default, a dense DFA uses
1040 /// "leftmost first" match semantics.
1041 ///
1042 /// Leftmost first match semantics corresponds to the match with the
1043 /// smallest starting offset, but where the end offset is determined by
1044 /// preferring earlier branches in the original regular expression. For
1045 /// example, `Sam|Samwise` will match `Sam` in `Samwise`, but `Samwise|Sam`
1046 /// will match `Samwise` in `Samwise`.
1047 ///
1048 /// Generally speaking, the "leftmost first" match is how most backtracking
1049 /// regular expressions tend to work. This is in contrast to POSIX-style
1050 /// regular expressions that yield "leftmost longest" matches. Namely,
1051 /// both `Sam|Samwise` and `Samwise|Sam` match `Samwise` when using
1052 /// leftmost longest semantics. (This crate does not currently support
1053 /// leftmost longest semantics.)
1054 ///
1055 /// ```
1056 /// use regex_automata::{
1057 /// dfa::{Automaton, dense},
1058 /// HalfMatch,
1059 /// };
1060 ///
1061 /// let dfa = dense::DFA::new("foo[0-9]+")?;
1062 /// let expected = HalfMatch::must(0, 8);
1063 /// assert_eq!(Some(expected), dfa.find_leftmost_fwd(b"foo12345")?);
1064 ///
1065 /// // Even though a match is found after reading the first byte (`a`),
1066 /// // the leftmost first match semantics demand that we find the earliest
1067 /// // match that prefers earlier parts of the pattern over latter parts.
1068 /// let dfa = dense::DFA::new("abc|a")?;
1069 /// let expected = HalfMatch::must(0, 3);
1070 /// assert_eq!(Some(expected), dfa.find_leftmost_fwd(b"abc")?);
1071 ///
1072 /// # Ok::<(), Box<dyn std::error::Error>>(())
1073 /// ```
1074 #[inline]
1075 fn find_leftmost_fwd(
1076 &self,
1077 bytes: &[u8],
1078 ) -> Result<Option<HalfMatch>, MatchError> {
1079 self.find_leftmost_fwd_at(None, None, bytes, 0, bytes.len())
1080 }
1081
1082 /// Executes a reverse search and returns the start of the position of the
1083 /// leftmost match that is found. If no match exists, then `None` is
1084 /// returned.
1085 ///
1086 /// # Errors
1087 ///
1088 /// This routine only errors if the search could not complete. For
1089 /// DFAs generated by this crate, this only occurs in a non-default
1090 /// configuration where quit bytes are used or Unicode word boundaries are
1091 /// heuristically enabled.
1092 ///
1093 /// When a search cannot complete, callers cannot know whether a match
1094 /// exists or not.
1095 ///
1096 /// # Notes for implementors
1097 ///
1098 /// Implementors of this trait are not required to implement any particular
1099 /// match semantics (such as leftmost-first), which are instead manifest in
1100 /// the DFA's transitions.
1101 ///
1102 /// In particular, this method must continue searching even after it enters
1103 /// a match state. The search should only terminate once it has reached
1104 /// the end of the input or when it has entered a dead or quit state. Upon
1105 /// termination, the position of the last byte seen while still in a match
1106 /// state is returned.
1107 ///
1108 /// Since this trait provides an implementation for this method by default,
1109 /// it's unlikely that one will need to implement this.
1110 ///
1111 /// # Example
1112 ///
1113 /// This example shows how to use this method with a
1114 /// [`dense::DFA`](crate::dfa::dense::DFA). In particular, this routine
1115 /// is principally useful when used in conjunction with the
1116 /// [`nfa::thompson::Config::reverse`](crate::nfa::thompson::Config::reverse)
1117 /// configuration. In general, it's unlikely to be correct to use both
1118 /// `find_leftmost_fwd` and `find_leftmost_rev` with the same DFA since any
1119 /// particular DFA will only support searching in one direction with
1120 /// respect to the pattern.
1121 ///
1122 /// ```
1123 /// use regex_automata::{
1124 /// nfa::thompson,
1125 /// dfa::{Automaton, dense},
1126 /// HalfMatch,
1127 /// };
1128 ///
1129 /// let dfa = dense::Builder::new()
1130 /// .thompson(thompson::Config::new().reverse(true))
1131 /// .build("foo[0-9]+")?;
1132 /// let expected = HalfMatch::must(0, 0);
1133 /// assert_eq!(Some(expected), dfa.find_leftmost_rev(b"foo12345")?);
1134 ///
1135 /// // Even though a match is found after reading the last byte (`c`),
1136 /// // the leftmost first match semantics demand that we find the earliest
1137 /// // match that prefers earlier parts of the pattern over latter parts.
1138 /// let dfa = dense::Builder::new()
1139 /// .thompson(thompson::Config::new().reverse(true))
1140 /// .build("abc|c")?;
1141 /// let expected = HalfMatch::must(0, 0);
1142 /// assert_eq!(Some(expected), dfa.find_leftmost_rev(b"abc")?);
1143 ///
1144 /// # Ok::<(), Box<dyn std::error::Error>>(())
1145 /// ```
1146 #[inline]
1147 fn find_leftmost_rev(
1148 &self,
1149 bytes: &[u8],
1150 ) -> Result<Option<HalfMatch>, MatchError> {
1151 self.find_leftmost_rev_at(None, bytes, 0, bytes.len())
1152 }
1153
1154 /// Executes an overlapping forward search and returns the end position of
1155 /// matches as they are found. If no match exists, then `None` is returned.
1156 ///
1157 /// This routine is principally only useful when searching for multiple
1158 /// patterns on inputs where multiple patterns may match the same regions
1159 /// of text. In particular, callers must preserve the automaton's search
1160 /// state from prior calls so that the implementation knows where the last
1161 /// match occurred.
1162 ///
1163 /// # Errors
1164 ///
1165 /// This routine only errors if the search could not complete. For
1166 /// DFAs generated by this crate, this only occurs in a non-default
1167 /// configuration where quit bytes are used or Unicode word boundaries are
1168 /// heuristically enabled.
1169 ///
1170 /// When a search cannot complete, callers cannot know whether a match
1171 /// exists or not.
1172 ///
1173 /// # Example
1174 ///
1175 /// This example shows how to run a basic overlapping search with a
1176 /// [`dense::DFA`](crate::dfa::dense::DFA). Notice that we build the
1177 /// automaton with a `MatchKind::All` configuration. Overlapping searches
1178 /// are unlikely to work as one would expect when using the default
1179 /// `MatchKind::LeftmostFirst` match semantics, since leftmost-first
1180 /// matching is fundamentally incompatible with overlapping searches.
1181 /// Namely, overlapping searches need to report matches as they are seen,
1182 /// where as leftmost-first searches will continue searching even after a
1183 /// match has been observed in order to find the conventional end position
1184 /// of the match. More concretely, leftmost-first searches use dead states
1185 /// to terminate a search after a specific match can no longer be extended.
1186 /// Overlapping searches instead do the opposite by continuing the search
1187 /// to find totally new matches (potentially of other patterns).
1188 ///
1189 /// ```
1190 /// use regex_automata::{
1191 /// dfa::{Automaton, OverlappingState, dense},
1192 /// HalfMatch,
1193 /// MatchKind,
1194 /// };
1195 ///
1196 /// let dfa = dense::Builder::new()
1197 /// .configure(dense::Config::new().match_kind(MatchKind::All))
1198 /// .build_many(&[r"\w+$", r"\S+$"])?;
1199 /// let haystack = "@foo".as_bytes();
1200 /// let mut state = OverlappingState::start();
1201 ///
1202 /// let expected = Some(HalfMatch::must(1, 4));
1203 /// let got = dfa.find_overlapping_fwd(haystack, &mut state)?;
1204 /// assert_eq!(expected, got);
1205 ///
1206 /// // The first pattern also matches at the same position, so re-running
1207 /// // the search will yield another match. Notice also that the first
1208 /// // pattern is returned after the second. This is because the second
1209 /// // pattern begins its match before the first, is therefore an earlier
1210 /// // match and is thus reported first.
1211 /// let expected = Some(HalfMatch::must(0, 4));
1212 /// let got = dfa.find_overlapping_fwd(haystack, &mut state)?;
1213 /// assert_eq!(expected, got);
1214 ///
1215 /// # Ok::<(), Box<dyn std::error::Error>>(())
1216 /// ```
1217 #[inline]
1218 fn find_overlapping_fwd(
1219 &self,
1220 bytes: &[u8],
1221 state: &mut OverlappingState,
1222 ) -> Result<Option<HalfMatch>, MatchError> {
1223 self.find_overlapping_fwd_at(None, None, bytes, 0, bytes.len(), state)
1224 }
1225
1226 /// Executes a forward search and returns the end position of the first
1227 /// match that is found as early as possible. If no match exists, then
1228 /// `None` is returned.
1229 ///
1230 /// This routine stops scanning input as soon as the search observes a
1231 /// match state. This is useful for implementing boolean `is_match`-like
1232 /// routines, where as little work is done as possible.
1233 ///
1234 /// This is like [`Automaton::find_earliest_fwd`], except it provides some
1235 /// additional control over how the search is executed:
1236 ///
1237 /// * `pre` is a prefilter scanner that, when given, is used whenever the
1238 /// DFA enters its starting state. This is meant to speed up searches where
1239 /// one or a small number of literal prefixes are known.
1240 /// * `pattern_id` specifies a specific pattern in the DFA to run an
1241 /// anchored search for. If not given, then a search for any pattern is
1242 /// performed. For DFAs built by this crate,
1243 /// [`dense::Config::starts_for_each_pattern`](crate::dfa::dense::Config::starts_for_each_pattern)
1244 /// must be enabled to use this functionality.
1245 /// * `start` and `end` permit searching a specific region of the haystack
1246 /// `bytes`. This is useful when implementing an iterator over matches
1247 /// within the same haystack, which cannot be done correctly by simply
1248 /// providing a subslice of `bytes`. (Because the existence of look-around
1249 /// operations such as `\b`, `^` and `$` need to take the surrounding
1250 /// context into account. This cannot be done if the haystack doesn't
1251 /// contain it.)
1252 ///
1253 /// The examples below demonstrate each of these additional parameters.
1254 ///
1255 /// # Errors
1256 ///
1257 /// This routine only errors if the search could not complete. For
1258 /// DFAs generated by this crate, this only occurs in a non-default
1259 /// configuration where quit bytes are used or Unicode word boundaries are
1260 /// heuristically enabled.
1261 ///
1262 /// When a search cannot complete, callers cannot know whether a match
1263 /// exists or not.
1264 ///
1265 /// # Panics
1266 ///
1267 /// This routine must panic if a `pattern_id` is given and the underlying
1268 /// DFA does not support specific pattern searches.
1269 ///
1270 /// It must also panic if the given haystack range is not valid.
1271 ///
1272 /// # Example: prefilter
1273 ///
1274 /// This example shows how to provide a prefilter for a pattern where all
1275 /// matches start with a `z` byte.
1276 ///
1277 /// ```
1278 /// use regex_automata::{
1279 /// dfa::{Automaton, dense},
1280 /// util::prefilter::{Candidate, Prefilter, Scanner, State},
1281 /// HalfMatch,
1282 /// };
1283 ///
1284 /// #[derive(Debug)]
1285 /// pub struct ZPrefilter;
1286 ///
1287 /// impl Prefilter for ZPrefilter {
1288 /// fn next_candidate(
1289 /// &self,
1290 /// _: &mut State,
1291 /// haystack: &[u8],
1292 /// at: usize,
1293 /// ) -> Candidate {
1294 /// // Try changing b'z' to b'q' and observe this test fail since
1295 /// // the prefilter will skip right over the match.
1296 /// match haystack.iter().position(|&b| b == b'z') {
1297 /// None => Candidate::None,
1298 /// Some(i) => Candidate::PossibleStartOfMatch(at + i),
1299 /// }
1300 /// }
1301 ///
1302 /// fn heap_bytes(&self) -> usize {
1303 /// 0
1304 /// }
1305 /// }
1306 ///
1307 /// let dfa = dense::DFA::new("z[0-9]{3}")?;
1308 /// let haystack = "foobar z123 q123".as_bytes();
1309 /// // A scanner executes a prefilter while tracking some state that helps
1310 /// // determine whether a prefilter is still "effective" or not.
1311 /// let mut scanner = Scanner::new(&ZPrefilter);
1312 ///
1313 /// let expected = Some(HalfMatch::must(0, 11));
1314 /// let got = dfa.find_earliest_fwd_at(
1315 /// Some(&mut scanner),
1316 /// None,
1317 /// haystack,
1318 /// 0,
1319 /// haystack.len(),
1320 /// )?;
1321 /// assert_eq!(expected, got);
1322 ///
1323 /// # Ok::<(), Box<dyn std::error::Error>>(())
1324 /// ```
1325 ///
1326 /// # Example: specific pattern search
1327 ///
1328 /// This example shows how to build a multi-DFA that permits searching for
1329 /// specific patterns.
1330 ///
1331 /// ```
1332 /// use regex_automata::{
1333 /// dfa::{Automaton, dense},
1334 /// HalfMatch,
1335 /// PatternID,
1336 /// };
1337 ///
1338 /// let dfa = dense::Builder::new()
1339 /// .configure(dense::Config::new().starts_for_each_pattern(true))
1340 /// .build_many(&["[a-z0-9]{6}", "[a-z][a-z0-9]{5}"])?;
1341 /// let haystack = "foo123".as_bytes();
1342 ///
1343 /// // Since we are using the default leftmost-first match and both
1344 /// // patterns match at the same starting position, only the first pattern
1345 /// // will be returned in this case when doing a search for any of the
1346 /// // patterns.
1347 /// let expected = Some(HalfMatch::must(0, 6));
1348 /// let got = dfa.find_earliest_fwd_at(
1349 /// None,
1350 /// None,
1351 /// haystack,
1352 /// 0,
1353 /// haystack.len(),
1354 /// )?;
1355 /// assert_eq!(expected, got);
1356 ///
1357 /// // But if we want to check whether some other pattern matches, then we
1358 /// // can provide its pattern ID.
1359 /// let expected = Some(HalfMatch::must(1, 6));
1360 /// let got = dfa.find_earliest_fwd_at(
1361 /// None,
1362 /// Some(PatternID::must(1)),
1363 /// haystack,
1364 /// 0,
1365 /// haystack.len(),
1366 /// )?;
1367 /// assert_eq!(expected, got);
1368 ///
1369 /// # Ok::<(), Box<dyn std::error::Error>>(())
1370 /// ```
1371 ///
1372 /// # Example: specifying the bounds of a search
1373 ///
1374 /// This example shows how providing the bounds of a search can produce
1375 /// different results than simply sub-slicing the haystack.
1376 ///
1377 /// ```
1378 /// use regex_automata::{
1379 /// dfa::{Automaton, dense},
1380 /// HalfMatch,
1381 /// };
1382 ///
1383 /// // N.B. We disable Unicode here so that we use a simple ASCII word
1384 /// // boundary. Alternatively, we could enable heuristic support for
1385 /// // Unicode word boundaries.
1386 /// let dfa = dense::DFA::new(r"(?-u)\b[0-9]{3}\b")?;
1387 /// let haystack = "foo123bar".as_bytes();
1388 ///
1389 /// // Since we sub-slice the haystack, the search doesn't know about the
1390 /// // larger context and assumes that `123` is surrounded by word
1391 /// // boundaries. And of course, the match position is reported relative
1392 /// // to the sub-slice as well, which means we get `3` instead of `6`.
1393 /// let expected = Some(HalfMatch::must(0, 3));
1394 /// let got = dfa.find_earliest_fwd_at(
1395 /// None,
1396 /// None,
1397 /// &haystack[3..6],
1398 /// 0,
1399 /// haystack[3..6].len(),
1400 /// )?;
1401 /// assert_eq!(expected, got);
1402 ///
1403 /// // But if we provide the bounds of the search within the context of the
1404 /// // entire haystack, then the search can take the surrounding context
1405 /// // into account. (And if we did find a match, it would be reported
1406 /// // as a valid offset into `haystack` instead of its sub-slice.)
1407 /// let expected = None;
1408 /// let got = dfa.find_earliest_fwd_at(
1409 /// None,
1410 /// None,
1411 /// haystack,
1412 /// 3,
1413 /// 6,
1414 /// )?;
1415 /// assert_eq!(expected, got);
1416 ///
1417 /// # Ok::<(), Box<dyn std::error::Error>>(())
1418 /// ```
1419 #[inline]
1420 fn find_earliest_fwd_at(
1421 &self,
1422 pre: Option<&mut prefilter::Scanner>,
1423 pattern_id: Option<PatternID>,
1424 bytes: &[u8],
1425 start: usize,
1426 end: usize,
1427 ) -> Result<Option<HalfMatch>, MatchError> {
1428 search::find_earliest_fwd(pre, self, pattern_id, bytes, start, end)
1429 }
1430
1431 /// Executes a reverse search and returns the start position of the first
1432 /// match that is found as early as possible. If no match exists, then
1433 /// `None` is returned.
1434 ///
1435 /// This routine stops scanning input as soon as the search observes a
1436 /// match state.
1437 ///
1438 /// This is like [`Automaton::find_earliest_rev`], except it provides some
1439 /// additional control over how the search is executed. See the
1440 /// documentation of [`Automaton::find_earliest_fwd_at`] for more details
1441 /// on the additional parameters along with examples of their usage.
1442 ///
1443 /// # Errors
1444 ///
1445 /// This routine only errors if the search could not complete. For
1446 /// DFAs generated by this crate, this only occurs in a non-default
1447 /// configuration where quit bytes are used or Unicode word boundaries are
1448 /// heuristically enabled.
1449 ///
1450 /// When a search cannot complete, callers cannot know whether a match
1451 /// exists or not.
1452 ///
1453 /// # Panics
1454 ///
1455 /// This routine must panic if a `pattern_id` is given and the underlying
1456 /// DFA does not support specific pattern searches.
1457 ///
1458 /// It must also panic if the given haystack range is not valid.
1459 #[inline]
1460 fn find_earliest_rev_at(
1461 &self,
1462 pattern_id: Option<PatternID>,
1463 bytes: &[u8],
1464 start: usize,
1465 end: usize,
1466 ) -> Result<Option<HalfMatch>, MatchError> {
1467 search::find_earliest_rev(self, pattern_id, bytes, start, end)
1468 }
1469
1470 /// Executes a forward search and returns the end position of the leftmost
1471 /// match that is found. If no match exists, then `None` is returned.
1472 ///
1473 /// This is like [`Automaton::find_leftmost_fwd`], except it provides some
1474 /// additional control over how the search is executed. See the
1475 /// documentation of [`Automaton::find_earliest_fwd_at`] for more details
1476 /// on the additional parameters along with examples of their usage.
1477 ///
1478 /// # Errors
1479 ///
1480 /// This routine only errors if the search could not complete. For
1481 /// DFAs generated by this crate, this only occurs in a non-default
1482 /// configuration where quit bytes are used or Unicode word boundaries are
1483 /// heuristically enabled.
1484 ///
1485 /// When a search cannot complete, callers cannot know whether a match
1486 /// exists or not.
1487 ///
1488 /// # Panics
1489 ///
1490 /// This routine must panic if a `pattern_id` is given and the underlying
1491 /// DFA does not support specific pattern searches.
1492 ///
1493 /// It must also panic if the given haystack range is not valid.
1494 #[inline]
1495 fn find_leftmost_fwd_at(
1496 &self,
1497 pre: Option<&mut prefilter::Scanner>,
1498 pattern_id: Option<PatternID>,
1499 bytes: &[u8],
1500 start: usize,
1501 end: usize,
1502 ) -> Result<Option<HalfMatch>, MatchError> {
1503 search::find_leftmost_fwd(pre, self, pattern_id, bytes, start, end)
1504 }
1505
1506 /// Executes a reverse search and returns the start of the position of the
1507 /// leftmost match that is found. If no match exists, then `None` is
1508 /// returned.
1509 ///
1510 /// This is like [`Automaton::find_leftmost_rev`], except it provides some
1511 /// additional control over how the search is executed. See the
1512 /// documentation of [`Automaton::find_earliest_fwd_at`] for more details
1513 /// on the additional parameters along with examples of their usage.
1514 ///
1515 /// # Errors
1516 ///
1517 /// This routine only errors if the search could not complete. For
1518 /// DFAs generated by this crate, this only occurs in a non-default
1519 /// configuration where quit bytes are used or Unicode word boundaries are
1520 /// heuristically enabled.
1521 ///
1522 /// When a search cannot complete, callers cannot know whether a match
1523 /// exists or not.
1524 ///
1525 /// # Panics
1526 ///
1527 /// This routine must panic if a `pattern_id` is given and the underlying
1528 /// DFA does not support specific pattern searches.
1529 ///
1530 /// It must also panic if the given haystack range is not valid.
1531 #[inline]
1532 fn find_leftmost_rev_at(
1533 &self,
1534 pattern_id: Option<PatternID>,
1535 bytes: &[u8],
1536 start: usize,
1537 end: usize,
1538 ) -> Result<Option<HalfMatch>, MatchError> {
1539 search::find_leftmost_rev(self, pattern_id, bytes, start, end)
1540 }
1541
1542 /// Executes an overlapping forward search and returns the end position of
1543 /// matches as they are found. If no match exists, then `None` is returned.
1544 ///
1545 /// This routine is principally only useful when searching for multiple
1546 /// patterns on inputs where multiple patterns may match the same regions
1547 /// of text. In particular, callers must preserve the automaton's search
1548 /// state from prior calls so that the implementation knows where the last
1549 /// match occurred.
1550 ///
1551 /// This is like [`Automaton::find_overlapping_fwd`], except it provides
1552 /// some additional control over how the search is executed. See the
1553 /// documentation of [`Automaton::find_earliest_fwd_at`] for more details
1554 /// on the additional parameters along with examples of their usage.
1555 ///
1556 /// When using this routine to implement an iterator of overlapping
1557 /// matches, the `start` of the search should always be set to the end
1558 /// of the last match. If more patterns match at the previous location,
1559 /// then they will be immediately returned. (This is tracked by the given
1560 /// overlapping state.) Otherwise, the search continues at the starting
1561 /// position given.
1562 ///
1563 /// If for some reason you want the search to forget about its previous
1564 /// state and restart the search at a particular position, then setting the
1565 /// state to [`OverlappingState::start`] will accomplish that.
1566 ///
1567 /// # Errors
1568 ///
1569 /// This routine only errors if the search could not complete. For
1570 /// DFAs generated by this crate, this only occurs in a non-default
1571 /// configuration where quit bytes are used or Unicode word boundaries are
1572 /// heuristically enabled.
1573 ///
1574 /// When a search cannot complete, callers cannot know whether a match
1575 /// exists or not.
1576 ///
1577 /// # Panics
1578 ///
1579 /// This routine must panic if a `pattern_id` is given and the underlying
1580 /// DFA does not support specific pattern searches.
1581 ///
1582 /// It must also panic if the given haystack range is not valid.
1583 #[inline]
1584 fn find_overlapping_fwd_at(
1585 &self,
1586 pre: Option<&mut prefilter::Scanner>,
1587 pattern_id: Option<PatternID>,
1588 bytes: &[u8],
1589 start: usize,
1590 end: usize,
1591 state: &mut OverlappingState,
1592 ) -> Result<Option<HalfMatch>, MatchError> {
1593 search::find_overlapping_fwd(
1594 pre, self, pattern_id, bytes, start, end, state,
1595 )
1596 }
1597}
1598
1599unsafe impl<'a, T: Automaton> Automaton for &'a T {
1600 #[inline]
1601 fn next_state(&self, current: StateID, input: u8) -> StateID {
1602 (**self).next_state(current, input)
1603 }
1604
1605 #[inline]
1606 unsafe fn next_state_unchecked(
1607 &self,
1608 current: StateID,
1609 input: u8,
1610 ) -> StateID {
1611 (**self).next_state_unchecked(current, input)
1612 }
1613
1614 #[inline]
1615 fn next_eoi_state(&self, current: StateID) -> StateID {
1616 (**self).next_eoi_state(current)
1617 }
1618
1619 #[inline]
1620 fn start_state_forward(
1621 &self,
1622 pattern_id: Option<PatternID>,
1623 bytes: &[u8],
1624 start: usize,
1625 end: usize,
1626 ) -> StateID {
1627 (**self).start_state_forward(pattern_id, bytes, start, end)
1628 }
1629
1630 #[inline]
1631 fn start_state_reverse(
1632 &self,
1633 pattern_id: Option<PatternID>,
1634 bytes: &[u8],
1635 start: usize,
1636 end: usize,
1637 ) -> StateID {
1638 (**self).start_state_reverse(pattern_id, bytes, start, end)
1639 }
1640
1641 #[inline]
1642 fn is_special_state(&self, id: StateID) -> bool {
1643 (**self).is_special_state(id)
1644 }
1645
1646 #[inline]
1647 fn is_dead_state(&self, id: StateID) -> bool {
1648 (**self).is_dead_state(id)
1649 }
1650
1651 #[inline]
1652 fn is_quit_state(&self, id: StateID) -> bool {
1653 (**self).is_quit_state(id)
1654 }
1655
1656 #[inline]
1657 fn is_match_state(&self, id: StateID) -> bool {
1658 (**self).is_match_state(id)
1659 }
1660
1661 #[inline]
1662 fn is_start_state(&self, id: StateID) -> bool {
1663 (**self).is_start_state(id)
1664 }
1665
1666 #[inline]
1667 fn is_accel_state(&self, id: StateID) -> bool {
1668 (**self).is_accel_state(id)
1669 }
1670
1671 #[inline]
1672 fn pattern_count(&self) -> usize {
1673 (**self).pattern_count()
1674 }
1675
1676 #[inline]
1677 fn match_count(&self, id: StateID) -> usize {
1678 (**self).match_count(id)
1679 }
1680
1681 #[inline]
1682 fn match_pattern(&self, id: StateID, index: usize) -> PatternID {
1683 (**self).match_pattern(id, index)
1684 }
1685
1686 #[inline]
1687 fn accelerator(&self, id: StateID) -> &[u8] {
1688 (**self).accelerator(id)
1689 }
1690
1691 #[inline]
1692 fn find_earliest_fwd(
1693 &self,
1694 bytes: &[u8],
1695 ) -> Result<Option<HalfMatch>, MatchError> {
1696 (**self).find_earliest_fwd(bytes)
1697 }
1698
1699 #[inline]
1700 fn find_earliest_rev(
1701 &self,
1702 bytes: &[u8],
1703 ) -> Result<Option<HalfMatch>, MatchError> {
1704 (**self).find_earliest_rev(bytes)
1705 }
1706
1707 #[inline]
1708 fn find_leftmost_fwd(
1709 &self,
1710 bytes: &[u8],
1711 ) -> Result<Option<HalfMatch>, MatchError> {
1712 (**self).find_leftmost_fwd(bytes)
1713 }
1714
1715 #[inline]
1716 fn find_leftmost_rev(
1717 &self,
1718 bytes: &[u8],
1719 ) -> Result<Option<HalfMatch>, MatchError> {
1720 (**self).find_leftmost_rev(bytes)
1721 }
1722
1723 #[inline]
1724 fn find_overlapping_fwd(
1725 &self,
1726 bytes: &[u8],
1727 state: &mut OverlappingState,
1728 ) -> Result<Option<HalfMatch>, MatchError> {
1729 (**self).find_overlapping_fwd(bytes, state)
1730 }
1731
1732 #[inline]
1733 fn find_earliest_fwd_at(
1734 &self,
1735 pre: Option<&mut prefilter::Scanner>,
1736 pattern_id: Option<PatternID>,
1737 bytes: &[u8],
1738 start: usize,
1739 end: usize,
1740 ) -> Result<Option<HalfMatch>, MatchError> {
1741 (**self).find_earliest_fwd_at(pre, pattern_id, bytes, start, end)
1742 }
1743
1744 #[inline]
1745 fn find_earliest_rev_at(
1746 &self,
1747 pattern_id: Option<PatternID>,
1748 bytes: &[u8],
1749 start: usize,
1750 end: usize,
1751 ) -> Result<Option<HalfMatch>, MatchError> {
1752 (**self).find_earliest_rev_at(pattern_id, bytes, start, end)
1753 }
1754
1755 #[inline]
1756 fn find_leftmost_fwd_at(
1757 &self,
1758 pre: Option<&mut prefilter::Scanner>,
1759 pattern_id: Option<PatternID>,
1760 bytes: &[u8],
1761 start: usize,
1762 end: usize,
1763 ) -> Result<Option<HalfMatch>, MatchError> {
1764 (**self).find_leftmost_fwd_at(pre, pattern_id, bytes, start, end)
1765 }
1766
1767 #[inline]
1768 fn find_leftmost_rev_at(
1769 &self,
1770 pattern_id: Option<PatternID>,
1771 bytes: &[u8],
1772 start: usize,
1773 end: usize,
1774 ) -> Result<Option<HalfMatch>, MatchError> {
1775 (**self).find_leftmost_rev_at(pattern_id, bytes, start, end)
1776 }
1777
1778 #[inline]
1779 fn find_overlapping_fwd_at(
1780 &self,
1781 pre: Option<&mut prefilter::Scanner>,
1782 pattern_id: Option<PatternID>,
1783 bytes: &[u8],
1784 start: usize,
1785 end: usize,
1786 state: &mut OverlappingState,
1787 ) -> Result<Option<HalfMatch>, MatchError> {
1788 (**self)
1789 .find_overlapping_fwd_at(pre, pattern_id, bytes, start, end, state)
1790 }
1791}
1792
1793/// Represents the current state of an overlapping search.
1794///
1795/// This is used for overlapping searches since they need to know something
1796/// about the previous search. For example, when multiple patterns match at the
1797/// same position, this state tracks the last reported pattern so that the next
1798/// search knows whether to report another matching pattern or continue with
1799/// the search at the next position. Additionally, it also tracks which state
1800/// the last search call terminated in.
1801///
1802/// This type provides no introspection capabilities. The only thing a caller
1803/// can do is construct it and pass it around to permit search routines to use
1804/// it to track state.
1805///
1806/// Callers should always provide a fresh state constructed via
1807/// [`OverlappingState::start`] when starting a new search. Reusing state from
1808/// a previous search may result in incorrect results.
1809#[derive(Clone, Debug, Eq, PartialEq)]
1810pub struct OverlappingState {
1811 /// The state ID of the state at which the search was in when the call
1812 /// terminated. When this is a match state, `last_match` must be set to a
1813 /// non-None value.
1814 ///
1815 /// A `None` value indicates the start state of the corresponding
1816 /// automaton. We cannot use the actual ID, since any one automaton may
1817 /// have many start states, and which one is in use depends on several
1818 /// search-time factors.
1819 id: Option<StateID>,
1820 /// Information associated with a match when `id` corresponds to a match
1821 /// state.
1822 last_match: Option<StateMatch>,
1823}
1824
1825/// Internal state about the last match that occurred. This records both the
1826/// offset of the match and the match index.
1827#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1828pub(crate) struct StateMatch {
1829 /// The index into the matching patterns for the current match state.
1830 pub(crate) match_index: usize,
1831 /// The offset in the haystack at which the match occurred. This is used
1832 /// when reporting multiple matches at the same offset. That is, when
1833 /// an overlapping search runs, the first thing it checks is whether it's
1834 /// already in a match state, and if so, whether there are more patterns
1835 /// to report as matches in that state. If so, it increments `match_index`
1836 /// and returns the pattern and this offset. Once `match_index` exceeds the
1837 /// number of matching patterns in the current state, the search continues.
1838 pub(crate) offset: usize,
1839}
1840
1841impl OverlappingState {
1842 /// Create a new overlapping state that begins at the start state of any
1843 /// automaton.
1844 pub fn start() -> OverlappingState {
1845 OverlappingState { id: None, last_match: None }
1846 }
1847
1848 pub(crate) fn id(&self) -> Option<StateID> {
1849 self.id
1850 }
1851
1852 pub(crate) fn set_id(&mut self, id: StateID) {
1853 self.id = Some(id);
1854 }
1855
1856 pub(crate) fn last_match(&mut self) -> Option<&mut StateMatch> {
1857 self.last_match.as_mut()
1858 }
1859
1860 pub(crate) fn set_last_match(&mut self, last_match: StateMatch) {
1861 self.last_match = Some(last_match);
1862 }
1863}
1864
1865/// Write a prefix "state" indicator for fmt::Debug impls.
1866///
1867/// Specifically, this tries to succinctly distinguish the different types of
1868/// states: dead states, quit states, accelerated states, start states and
1869/// match states. It even accounts for the possible overlappings of different
1870/// state types.
1871pub(crate) fn fmt_state_indicator<A: Automaton>(
1872 f: &mut core::fmt::Formatter<'_>,
1873 dfa: A,
1874 id: StateID,
1875) -> core::fmt::Result {
1876 if dfa.is_dead_state(id) {
1877 write!(f, "D")?;
1878 if dfa.is_start_state(id) {
1879 write!(f, ">")?;
1880 } else {
1881 write!(f, " ")?;
1882 }
1883 } else if dfa.is_quit_state(id) {
1884 write!(f, "Q ")?;
1885 } else if dfa.is_start_state(id) {
1886 if dfa.is_accel_state(id) {
1887 write!(f, "A>")?;
1888 } else {
1889 write!(f, " >")?;
1890 }
1891 } else if dfa.is_match_state(id) {
1892 if dfa.is_accel_state(id) {
1893 write!(f, "A*")?;
1894 } else {
1895 write!(f, " *")?;
1896 }
1897 } else if dfa.is_accel_state(id) {
1898 write!(f, "A ")?;
1899 } else {
1900 write!(f, " ")?;
1901 }
1902 Ok(())
1903}
1904