1 | /*! |
2 | Provides [`Automaton`] trait for abstracting over Aho-Corasick automata. |
3 | |
4 | The `Automaton` trait provides a way to write generic code over any |
5 | Aho-Corasick automaton. It also provides access to lower level APIs that |
6 | permit walking the state transitions of an Aho-Corasick automaton manually. |
7 | */ |
8 | |
9 | use alloc::{string::String, vec::Vec}; |
10 | |
11 | use crate::util::{ |
12 | error::MatchError, |
13 | primitives::PatternID, |
14 | search::{Anchored, Input, Match, MatchKind, Span}, |
15 | }; |
16 | |
17 | pub use crate::util::{ |
18 | prefilter::{Candidate, Prefilter}, |
19 | primitives::{StateID, StateIDError}, |
20 | }; |
21 | |
22 | /// We seal the `Automaton` trait for now. It's a big trait, and it's |
23 | /// conceivable that I might want to add new required methods, and sealing the |
24 | /// trait permits doing that in a backwards compatible fashion. On other the |
25 | /// hand, if you have a solid use case for implementing the trait yourself, |
26 | /// please file an issue and we can discuss it. This was *mostly* done as a |
27 | /// conservative step. |
28 | pub(crate) mod private { |
29 | pub trait Sealed {} |
30 | } |
31 | impl private::Sealed for crate::nfa::noncontiguous::NFA {} |
32 | impl private::Sealed for crate::nfa::contiguous::NFA {} |
33 | impl private::Sealed for crate::dfa::DFA {} |
34 | |
35 | impl<'a, T: private::Sealed + ?Sized> private::Sealed for &'a T {} |
36 | |
37 | /// A trait that abstracts over Aho-Corasick automata. |
38 | /// |
39 | /// This trait primarily exists for niche use cases such as: |
40 | /// |
41 | /// * Using an NFA or DFA directly, bypassing the top-level |
42 | /// [`AhoCorasick`](crate::AhoCorasick) searcher. Currently, these include |
43 | /// [`noncontiguous::NFA`](crate::nfa::noncontiguous::NFA), |
44 | /// [`contiguous::NFA`](crate::nfa::contiguous::NFA) and |
45 | /// [`dfa::DFA`](crate::dfa::DFA). |
46 | /// * Implementing your own custom search routine by walking the automaton |
47 | /// yourself. This might be useful for implementing search on non-contiguous |
48 | /// strings or streams. |
49 | /// |
50 | /// For most use cases, it is not expected that users will need |
51 | /// to use or even know about this trait. Indeed, the top level |
52 | /// [`AhoCorasick`](crate::AhoCorasick) searcher does not expose any details |
53 | /// about this trait, nor does it implement it itself. |
54 | /// |
55 | /// Note that this trait defines a number of default methods, such as |
56 | /// [`Automaton::try_find`] and [`Automaton::try_find_iter`], which implement |
57 | /// higher level search routines in terms of the lower level automata API. |
58 | /// |
59 | /// # Sealed |
60 | /// |
61 | /// Currently, this trait is sealed. That means users of this crate can write |
62 | /// generic routines over this trait but cannot implement it themselves. This |
63 | /// restriction may be lifted in the future, but sealing the trait permits |
64 | /// adding new required methods in a backwards compatible fashion. |
65 | /// |
66 | /// # Special states |
67 | /// |
68 | /// This trait encodes a notion of "special" states in an automaton. Namely, |
69 | /// a state is treated as special if it is a dead, match or start state: |
70 | /// |
71 | /// * A dead state is a state that cannot be left once entered. All transitions |
72 | /// on a dead state lead back to itself. The dead state is meant to be treated |
73 | /// as a sentinel indicating that the search should stop and return a match if |
74 | /// one has been found, and nothing otherwise. |
75 | /// * A match state is a state that indicates one or more patterns have |
76 | /// matched. Depending on the [`MatchKind`] of the automaton, a search may |
77 | /// stop once a match is seen, or it may continue looking for matches until |
78 | /// it enters a dead state or sees the end of the haystack. |
79 | /// * A start state is a state that a search begins in. It is useful to know |
80 | /// when a search enters a start state because it may mean that a prefilter can |
81 | /// be used to skip ahead and quickly look for candidate matches. Unlike dead |
82 | /// and match states, it is never necessary to explicitly handle start states |
83 | /// for correctness. Indeed, in this crate, implementations of `Automaton` |
84 | /// will only treat start states as "special" when a prefilter is enabled and |
85 | /// active. Otherwise, treating it as special has no purpose and winds up |
86 | /// slowing down the overall search because it results in ping-ponging between |
87 | /// the main state transition and the "special" state logic. |
88 | /// |
89 | /// Since checking whether a state is special by doing three different |
90 | /// checks would be too expensive inside a fast search loop, the |
91 | /// [`Automaton::is_special`] method is provided for quickly checking whether |
92 | /// the state is special. The `Automaton::is_dead`, `Automaton::is_match` and |
93 | /// `Automaton::is_start` predicates can then be used to determine which kind |
94 | /// of special state it is. |
95 | /// |
96 | /// # Panics |
97 | /// |
98 | /// Most of the APIs on this trait should panic or give incorrect results |
99 | /// if invalid inputs are given to it. For example, `Automaton::next_state` |
100 | /// has unspecified behavior if the state ID given to it is not a valid |
101 | /// state ID for the underlying automaton. Valid state IDs can only be |
102 | /// retrieved in one of two ways: calling `Automaton::start_state` or calling |
103 | /// `Automaton::next_state` with a valid state ID. |
104 | /// |
105 | /// # Safety |
106 | /// |
107 | /// This trait is not safe to implement so that code may rely on the |
108 | /// correctness of implementations of this trait to avoid undefined behavior. |
109 | /// The primary correctness guarantees are: |
110 | /// |
111 | /// * `Automaton::start_state` always returns a valid state ID or an error or |
112 | /// panics. |
113 | /// * `Automaton::next_state`, when given a valid state ID, always returns |
114 | /// a valid state ID for all values of `anchored` and `byte`, or otherwise |
115 | /// panics. |
116 | /// |
117 | /// In general, the rest of the methods on `Automaton` need to uphold their |
118 | /// contracts as well. For example, `Automaton::is_dead` should only returns |
119 | /// true if the given state ID is actually a dead state. |
120 | /// |
121 | /// Note that currently this crate does not rely on the safety property defined |
122 | /// here to avoid undefined behavior. Instead, this was done to make it |
123 | /// _possible_ to do in the future. |
124 | /// |
125 | /// # Example |
126 | /// |
127 | /// This example shows how one might implement a basic but correct search |
128 | /// routine. We keep things simple by not using prefilters or worrying about |
129 | /// anchored searches, but do make sure our search is correct for all possible |
130 | /// [`MatchKind`] semantics. (The comments in the code below note the parts |
131 | /// that are needed to support certain `MatchKind` semantics.) |
132 | /// |
133 | /// ``` |
134 | /// use aho_corasick::{ |
135 | /// automaton::Automaton, |
136 | /// nfa::noncontiguous::NFA, |
137 | /// Anchored, Match, MatchError, MatchKind, |
138 | /// }; |
139 | /// |
140 | /// // Run an unanchored search for 'aut' in 'haystack'. Return the first match |
141 | /// // seen according to the automaton's match semantics. This returns an error |
142 | /// // if the given automaton does not support unanchored searches. |
143 | /// fn find<A: Automaton>( |
144 | /// aut: A, |
145 | /// haystack: &[u8], |
146 | /// ) -> Result<Option<Match>, MatchError> { |
147 | /// let mut sid = aut.start_state(Anchored::No)?; |
148 | /// let mut at = 0; |
149 | /// let mut mat = None; |
150 | /// let get_match = |sid, at| { |
151 | /// let pid = aut.match_pattern(sid, 0); |
152 | /// let len = aut.pattern_len(pid); |
153 | /// Match::new(pid, (at - len)..at) |
154 | /// }; |
155 | /// // Start states can be match states! |
156 | /// if aut.is_match(sid) { |
157 | /// mat = Some(get_match(sid, at)); |
158 | /// // Standard semantics require matches to be reported as soon as |
159 | /// // they're seen. Otherwise, we continue until we see a dead state |
160 | /// // or the end of the haystack. |
161 | /// if matches!(aut.match_kind(), MatchKind::Standard) { |
162 | /// return Ok(mat); |
163 | /// } |
164 | /// } |
165 | /// while at < haystack.len() { |
166 | /// sid = aut.next_state(Anchored::No, sid, haystack[at]); |
167 | /// if aut.is_special(sid) { |
168 | /// if aut.is_dead(sid) { |
169 | /// return Ok(mat); |
170 | /// } else if aut.is_match(sid) { |
171 | /// mat = Some(get_match(sid, at + 1)); |
172 | /// // As above, standard semantics require that we return |
173 | /// // immediately once a match is found. |
174 | /// if matches!(aut.match_kind(), MatchKind::Standard) { |
175 | /// return Ok(mat); |
176 | /// } |
177 | /// } |
178 | /// } |
179 | /// at += 1; |
180 | /// } |
181 | /// Ok(mat) |
182 | /// } |
183 | /// |
184 | /// // Show that it works for standard searches. |
185 | /// let nfa = NFA::new(&["samwise" , "sam" ]).unwrap(); |
186 | /// assert_eq!(Some(Match::must(1, 0..3)), find(&nfa, b"samwise" )?); |
187 | /// |
188 | /// // But also works when using leftmost-first. Notice how the match result |
189 | /// // has changed! |
190 | /// let nfa = NFA::builder() |
191 | /// .match_kind(MatchKind::LeftmostFirst) |
192 | /// .build(&["samwise" , "sam" ]) |
193 | /// .unwrap(); |
194 | /// assert_eq!(Some(Match::must(0, 0..7)), find(&nfa, b"samwise" )?); |
195 | /// |
196 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
197 | /// ``` |
198 | pub unsafe trait Automaton: private::Sealed { |
199 | /// Returns the starting state for the given anchor mode. |
200 | /// |
201 | /// Upon success, the state ID returned is guaranteed to be valid for |
202 | /// this automaton. |
203 | /// |
204 | /// # Errors |
205 | /// |
206 | /// This returns an error when the given search configuration is not |
207 | /// supported by the underlying automaton. For example, if the underlying |
208 | /// automaton only supports unanchored searches but the given configuration |
209 | /// was set to an anchored search, then this must return an error. |
210 | fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError>; |
211 | |
212 | /// Performs a state transition from `sid` for `byte` and returns the next |
213 | /// state. |
214 | /// |
215 | /// `anchored` should be [`Anchored::Yes`] when executing an anchored |
216 | /// search and [`Anchored::No`] otherwise. For some implementations of |
217 | /// `Automaton`, it is required to know whether the search is anchored |
218 | /// or not in order to avoid following failure transitions. Other |
219 | /// implementations may ignore `anchored` altogether and depend on |
220 | /// `Automaton::start_state` returning a state that walks a different path |
221 | /// through the automaton depending on whether the search is anchored or |
222 | /// not. |
223 | /// |
224 | /// # Panics |
225 | /// |
226 | /// This routine may panic or return incorrect results when the given state |
227 | /// ID is invalid. A state ID is valid if and only if: |
228 | /// |
229 | /// 1. It came from a call to `Automaton::start_state`, or |
230 | /// 2. It came from a previous call to `Automaton::next_state` with a |
231 | /// valid state ID. |
232 | /// |
233 | /// Implementations must treat all possible values of `byte` as valid. |
234 | /// |
235 | /// Implementations may panic on unsupported values of `anchored`, but are |
236 | /// not required to do so. |
237 | fn next_state( |
238 | &self, |
239 | anchored: Anchored, |
240 | sid: StateID, |
241 | byte: u8, |
242 | ) -> StateID; |
243 | |
244 | /// Returns true if the given ID represents a "special" state. A special |
245 | /// state is a dead, match or start state. |
246 | /// |
247 | /// Note that implementations may choose to return false when the given ID |
248 | /// corresponds to a start state. Namely, it always correct to treat start |
249 | /// states as non-special. Implementations must return true for states that |
250 | /// are dead or contain matches. |
251 | /// |
252 | /// This has unspecified behavior when given an invalid state ID. |
253 | fn is_special(&self, sid: StateID) -> bool; |
254 | |
255 | /// Returns true if the given ID represents a dead state. |
256 | /// |
257 | /// A dead state is a type of "sink" in a finite state machine. It |
258 | /// corresponds to a state whose transitions all loop back to itself. That |
259 | /// is, once entered, it can never be left. In practice, it serves as a |
260 | /// sentinel indicating that the search should terminate. |
261 | /// |
262 | /// This has unspecified behavior when given an invalid state ID. |
263 | fn is_dead(&self, sid: StateID) -> bool; |
264 | |
265 | /// Returns true if the given ID represents a match state. |
266 | /// |
267 | /// A match state is always associated with one or more pattern IDs that |
268 | /// matched at the position in the haystack when the match state was |
269 | /// entered. When a match state is entered, the match semantics dictate |
270 | /// whether it should be returned immediately (for `MatchKind::Standard`) |
271 | /// or if the search should continue (for `MatchKind::LeftmostFirst` and |
272 | /// `MatchKind::LeftmostLongest`) until a dead state is seen or the end of |
273 | /// the haystack has been reached. |
274 | /// |
275 | /// This has unspecified behavior when given an invalid state ID. |
276 | fn is_match(&self, sid: StateID) -> bool; |
277 | |
278 | /// Returns true if the given ID represents a start state. |
279 | /// |
280 | /// While it is never incorrect to ignore start states during a search |
281 | /// (except for the start of the search of course), knowing whether one has |
282 | /// entered a start state can be useful for certain classes of performance |
283 | /// optimizations. For example, if one is in a start state, it may be legal |
284 | /// to try to skip ahead and look for match candidates more quickly than |
285 | /// would otherwise be accomplished by walking the automaton. |
286 | /// |
287 | /// Implementations of `Automaton` in this crate "unspecialize" start |
288 | /// states when a prefilter is not active or enabled. In this case, it |
289 | /// is possible for `Automaton::is_special(sid)` to return false while |
290 | /// `Automaton::is_start(sid)` returns true. |
291 | /// |
292 | /// This has unspecified behavior when given an invalid state ID. |
293 | fn is_start(&self, sid: StateID) -> bool; |
294 | |
295 | /// Returns the match semantics that this automaton was built with. |
296 | fn match_kind(&self) -> MatchKind; |
297 | |
298 | /// Returns the total number of matches for the given state ID. |
299 | /// |
300 | /// This has unspecified behavior if the given ID does not refer to a match |
301 | /// state. |
302 | fn match_len(&self, sid: StateID) -> usize; |
303 | |
304 | /// Returns the pattern ID for the match state given by `sid` at the |
305 | /// `index` given. |
306 | /// |
307 | /// Typically, `index` is only ever greater than `0` when implementing an |
308 | /// overlapping search. Otherwise, it's likely that your search only cares |
309 | /// about reporting the first pattern ID in a match state. |
310 | /// |
311 | /// This has unspecified behavior if the given ID does not refer to a match |
312 | /// state, or if the index is greater than or equal to the total number of |
313 | /// matches in this match state. |
314 | fn match_pattern(&self, sid: StateID, index: usize) -> PatternID; |
315 | |
316 | /// Returns the total number of patterns compiled into this automaton. |
317 | fn patterns_len(&self) -> usize; |
318 | |
319 | /// Returns the length of the pattern for the given ID. |
320 | /// |
321 | /// This has unspecified behavior when given an invalid pattern |
322 | /// ID. A pattern ID is valid if and only if it is less than |
323 | /// `Automaton::patterns_len`. |
324 | fn pattern_len(&self, pid: PatternID) -> usize; |
325 | |
326 | /// Returns the length, in bytes, of the shortest pattern in this |
327 | /// automaton. |
328 | fn min_pattern_len(&self) -> usize; |
329 | |
330 | /// Returns the length, in bytes, of the longest pattern in this automaton. |
331 | fn max_pattern_len(&self) -> usize; |
332 | |
333 | /// Returns the heap memory usage, in bytes, used by this automaton. |
334 | fn memory_usage(&self) -> usize; |
335 | |
336 | /// Returns a prefilter, if available, that can be used to accelerate |
337 | /// searches for this automaton. |
338 | /// |
339 | /// The typical way this is used is when the start state is entered during |
340 | /// a search. When that happens, one can use a prefilter to skip ahead and |
341 | /// look for candidate matches without having to walk the automaton on the |
342 | /// bytes between candidates. |
343 | /// |
344 | /// Typically a prefilter is only available when there are a small (<100) |
345 | /// number of patterns built into the automaton. |
346 | fn prefilter(&self) -> Option<&Prefilter>; |
347 | |
348 | /// Executes a non-overlapping search with this automaton using the given |
349 | /// configuration. |
350 | /// |
351 | /// See |
352 | /// [`AhoCorasick::try_find`](crate::AhoCorasick::try_find) |
353 | /// for more documentation and examples. |
354 | fn try_find( |
355 | &self, |
356 | input: &Input<'_>, |
357 | ) -> Result<Option<Match>, MatchError> { |
358 | try_find_fwd(&self, input) |
359 | } |
360 | |
361 | /// Executes a overlapping search with this automaton using the given |
362 | /// configuration. |
363 | /// |
364 | /// See |
365 | /// [`AhoCorasick::try_find_overlapping`](crate::AhoCorasick::try_find_overlapping) |
366 | /// for more documentation and examples. |
367 | fn try_find_overlapping( |
368 | &self, |
369 | input: &Input<'_>, |
370 | state: &mut OverlappingState, |
371 | ) -> Result<(), MatchError> { |
372 | try_find_overlapping_fwd(&self, input, state) |
373 | } |
374 | |
375 | /// Returns an iterator of non-overlapping matches with this automaton |
376 | /// using the given configuration. |
377 | /// |
378 | /// See |
379 | /// [`AhoCorasick::try_find_iter`](crate::AhoCorasick::try_find_iter) |
380 | /// for more documentation and examples. |
381 | fn try_find_iter<'a, 'h>( |
382 | &'a self, |
383 | input: Input<'h>, |
384 | ) -> Result<FindIter<'a, 'h, Self>, MatchError> |
385 | where |
386 | Self: Sized, |
387 | { |
388 | FindIter::new(self, input) |
389 | } |
390 | |
391 | /// Returns an iterator of overlapping matches with this automaton |
392 | /// using the given configuration. |
393 | /// |
394 | /// See |
395 | /// [`AhoCorasick::try_find_overlapping_iter`](crate::AhoCorasick::try_find_overlapping_iter) |
396 | /// for more documentation and examples. |
397 | fn try_find_overlapping_iter<'a, 'h>( |
398 | &'a self, |
399 | input: Input<'h>, |
400 | ) -> Result<FindOverlappingIter<'a, 'h, Self>, MatchError> |
401 | where |
402 | Self: Sized, |
403 | { |
404 | if !self.match_kind().is_standard() { |
405 | return Err(MatchError::unsupported_overlapping( |
406 | self.match_kind(), |
407 | )); |
408 | } |
409 | // We might consider lifting this restriction. The reason why I added |
410 | // it was to ban the combination of "anchored search" and "overlapping |
411 | // iteration." The match semantics aren't totally clear in that case. |
412 | // Should we allow *any* matches that are adjacent to *any* previous |
413 | // match? Or only following the most recent one? Or only matches |
414 | // that start at the beginning of the search? We might also elect to |
415 | // just keep this restriction in place, as callers should be able to |
416 | // implement it themselves if they want to. |
417 | if input.get_anchored().is_anchored() { |
418 | return Err(MatchError::invalid_input_anchored()); |
419 | } |
420 | let _ = self.start_state(input.get_anchored())?; |
421 | let state = OverlappingState::start(); |
422 | Ok(FindOverlappingIter { aut: self, input, state }) |
423 | } |
424 | |
425 | /// Replaces all non-overlapping matches in `haystack` with |
426 | /// strings from `replace_with` depending on the pattern that |
427 | /// matched. The `replace_with` slice must have length equal to |
428 | /// `Automaton::patterns_len`. |
429 | /// |
430 | /// See |
431 | /// [`AhoCorasick::try_replace_all`](crate::AhoCorasick::try_replace_all) |
432 | /// for more documentation and examples. |
433 | fn try_replace_all<B>( |
434 | &self, |
435 | haystack: &str, |
436 | replace_with: &[B], |
437 | ) -> Result<String, MatchError> |
438 | where |
439 | Self: Sized, |
440 | B: AsRef<str>, |
441 | { |
442 | assert_eq!( |
443 | replace_with.len(), |
444 | self.patterns_len(), |
445 | "replace_all requires a replacement for every pattern \ |
446 | in the automaton" |
447 | ); |
448 | let mut dst = String::with_capacity(haystack.len()); |
449 | self.try_replace_all_with(haystack, &mut dst, |mat, _, dst| { |
450 | dst.push_str(replace_with[mat.pattern()].as_ref()); |
451 | true |
452 | })?; |
453 | Ok(dst) |
454 | } |
455 | |
456 | /// Replaces all non-overlapping matches in `haystack` with |
457 | /// strings from `replace_with` depending on the pattern that |
458 | /// matched. The `replace_with` slice must have length equal to |
459 | /// `Automaton::patterns_len`. |
460 | /// |
461 | /// See |
462 | /// [`AhoCorasick::try_replace_all_bytes`](crate::AhoCorasick::try_replace_all_bytes) |
463 | /// for more documentation and examples. |
464 | fn try_replace_all_bytes<B>( |
465 | &self, |
466 | haystack: &[u8], |
467 | replace_with: &[B], |
468 | ) -> Result<Vec<u8>, MatchError> |
469 | where |
470 | Self: Sized, |
471 | B: AsRef<[u8]>, |
472 | { |
473 | assert_eq!( |
474 | replace_with.len(), |
475 | self.patterns_len(), |
476 | "replace_all requires a replacement for every pattern \ |
477 | in the automaton" |
478 | ); |
479 | let mut dst = Vec::with_capacity(haystack.len()); |
480 | self.try_replace_all_with_bytes(haystack, &mut dst, |mat, _, dst| { |
481 | dst.extend(replace_with[mat.pattern()].as_ref()); |
482 | true |
483 | })?; |
484 | Ok(dst) |
485 | } |
486 | |
487 | /// Replaces all non-overlapping matches in `haystack` by calling the |
488 | /// `replace_with` closure given. |
489 | /// |
490 | /// See |
491 | /// [`AhoCorasick::try_replace_all_with`](crate::AhoCorasick::try_replace_all_with) |
492 | /// for more documentation and examples. |
493 | fn try_replace_all_with<F>( |
494 | &self, |
495 | haystack: &str, |
496 | dst: &mut String, |
497 | mut replace_with: F, |
498 | ) -> Result<(), MatchError> |
499 | where |
500 | Self: Sized, |
501 | F: FnMut(&Match, &str, &mut String) -> bool, |
502 | { |
503 | let mut last_match = 0; |
504 | for m in self.try_find_iter(Input::new(haystack))? { |
505 | // Since there are no restrictions on what kinds of patterns are |
506 | // in an Aho-Corasick automaton, we might get matches that split |
507 | // a codepoint, or even matches of a partial codepoint. When that |
508 | // happens, we just skip the match. |
509 | if !haystack.is_char_boundary(m.start()) |
510 | || !haystack.is_char_boundary(m.end()) |
511 | { |
512 | continue; |
513 | } |
514 | dst.push_str(&haystack[last_match..m.start()]); |
515 | last_match = m.end(); |
516 | if !replace_with(&m, &haystack[m.start()..m.end()], dst) { |
517 | break; |
518 | }; |
519 | } |
520 | dst.push_str(&haystack[last_match..]); |
521 | Ok(()) |
522 | } |
523 | |
524 | /// Replaces all non-overlapping matches in `haystack` by calling the |
525 | /// `replace_with` closure given. |
526 | /// |
527 | /// See |
528 | /// [`AhoCorasick::try_replace_all_with_bytes`](crate::AhoCorasick::try_replace_all_with_bytes) |
529 | /// for more documentation and examples. |
530 | fn try_replace_all_with_bytes<F>( |
531 | &self, |
532 | haystack: &[u8], |
533 | dst: &mut Vec<u8>, |
534 | mut replace_with: F, |
535 | ) -> Result<(), MatchError> |
536 | where |
537 | Self: Sized, |
538 | F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool, |
539 | { |
540 | let mut last_match = 0; |
541 | for m in self.try_find_iter(Input::new(haystack))? { |
542 | dst.extend(&haystack[last_match..m.start()]); |
543 | last_match = m.end(); |
544 | if !replace_with(&m, &haystack[m.start()..m.end()], dst) { |
545 | break; |
546 | }; |
547 | } |
548 | dst.extend(&haystack[last_match..]); |
549 | Ok(()) |
550 | } |
551 | |
552 | /// Returns an iterator of non-overlapping matches with this automaton |
553 | /// from the stream given. |
554 | /// |
555 | /// See |
556 | /// [`AhoCorasick::try_stream_find_iter`](crate::AhoCorasick::try_stream_find_iter) |
557 | /// for more documentation and examples. |
558 | #[cfg (feature = "std" )] |
559 | fn try_stream_find_iter<'a, R: std::io::Read>( |
560 | &'a self, |
561 | rdr: R, |
562 | ) -> Result<StreamFindIter<'a, Self, R>, MatchError> |
563 | where |
564 | Self: Sized, |
565 | { |
566 | Ok(StreamFindIter { it: StreamChunkIter::new(self, rdr)? }) |
567 | } |
568 | |
569 | /// Replaces all non-overlapping matches in `rdr` with strings from |
570 | /// `replace_with` depending on the pattern that matched, and writes the |
571 | /// result to `wtr`. The `replace_with` slice must have length equal to |
572 | /// `Automaton::patterns_len`. |
573 | /// |
574 | /// See |
575 | /// [`AhoCorasick::try_stream_replace_all`](crate::AhoCorasick::try_stream_replace_all) |
576 | /// for more documentation and examples. |
577 | #[cfg (feature = "std" )] |
578 | fn try_stream_replace_all<R, W, B>( |
579 | &self, |
580 | rdr: R, |
581 | wtr: W, |
582 | replace_with: &[B], |
583 | ) -> std::io::Result<()> |
584 | where |
585 | Self: Sized, |
586 | R: std::io::Read, |
587 | W: std::io::Write, |
588 | B: AsRef<[u8]>, |
589 | { |
590 | assert_eq!( |
591 | replace_with.len(), |
592 | self.patterns_len(), |
593 | "streaming replace_all requires a replacement for every pattern \ |
594 | in the automaton" , |
595 | ); |
596 | self.try_stream_replace_all_with(rdr, wtr, |mat, _, wtr| { |
597 | wtr.write_all(replace_with[mat.pattern()].as_ref()) |
598 | }) |
599 | } |
600 | |
601 | /// Replaces all non-overlapping matches in `rdr` by calling the |
602 | /// `replace_with` closure given and writing the result to `wtr`. |
603 | /// |
604 | /// See |
605 | /// [`AhoCorasick::try_stream_replace_all_with`](crate::AhoCorasick::try_stream_replace_all_with) |
606 | /// for more documentation and examples. |
607 | #[cfg (feature = "std" )] |
608 | fn try_stream_replace_all_with<R, W, F>( |
609 | &self, |
610 | rdr: R, |
611 | mut wtr: W, |
612 | mut replace_with: F, |
613 | ) -> std::io::Result<()> |
614 | where |
615 | Self: Sized, |
616 | R: std::io::Read, |
617 | W: std::io::Write, |
618 | F: FnMut(&Match, &[u8], &mut W) -> std::io::Result<()>, |
619 | { |
620 | let mut it = StreamChunkIter::new(self, rdr).map_err(|e| { |
621 | let kind = std::io::ErrorKind::Other; |
622 | std::io::Error::new(kind, e) |
623 | })?; |
624 | while let Some(result) = it.next() { |
625 | let chunk = result?; |
626 | match chunk { |
627 | StreamChunk::NonMatch { bytes, .. } => { |
628 | wtr.write_all(bytes)?; |
629 | } |
630 | StreamChunk::Match { bytes, mat } => { |
631 | replace_with(&mat, bytes, &mut wtr)?; |
632 | } |
633 | } |
634 | } |
635 | Ok(()) |
636 | } |
637 | } |
638 | |
639 | // SAFETY: This just defers to the underlying 'AcAutomaton' and thus inherits |
640 | // its safety properties. |
641 | unsafe impl<'a, A: Automaton + ?Sized> Automaton for &'a A { |
642 | #[inline (always)] |
643 | fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError> { |
644 | (**self).start_state(anchored) |
645 | } |
646 | |
647 | #[inline (always)] |
648 | fn next_state( |
649 | &self, |
650 | anchored: Anchored, |
651 | sid: StateID, |
652 | byte: u8, |
653 | ) -> StateID { |
654 | (**self).next_state(anchored, sid, byte) |
655 | } |
656 | |
657 | #[inline (always)] |
658 | fn is_special(&self, sid: StateID) -> bool { |
659 | (**self).is_special(sid) |
660 | } |
661 | |
662 | #[inline (always)] |
663 | fn is_dead(&self, sid: StateID) -> bool { |
664 | (**self).is_dead(sid) |
665 | } |
666 | |
667 | #[inline (always)] |
668 | fn is_match(&self, sid: StateID) -> bool { |
669 | (**self).is_match(sid) |
670 | } |
671 | |
672 | #[inline (always)] |
673 | fn is_start(&self, sid: StateID) -> bool { |
674 | (**self).is_start(sid) |
675 | } |
676 | |
677 | #[inline (always)] |
678 | fn match_kind(&self) -> MatchKind { |
679 | (**self).match_kind() |
680 | } |
681 | |
682 | #[inline (always)] |
683 | fn match_len(&self, sid: StateID) -> usize { |
684 | (**self).match_len(sid) |
685 | } |
686 | |
687 | #[inline (always)] |
688 | fn match_pattern(&self, sid: StateID, index: usize) -> PatternID { |
689 | (**self).match_pattern(sid, index) |
690 | } |
691 | |
692 | #[inline (always)] |
693 | fn patterns_len(&self) -> usize { |
694 | (**self).patterns_len() |
695 | } |
696 | |
697 | #[inline (always)] |
698 | fn pattern_len(&self, pid: PatternID) -> usize { |
699 | (**self).pattern_len(pid) |
700 | } |
701 | |
702 | #[inline (always)] |
703 | fn min_pattern_len(&self) -> usize { |
704 | (**self).min_pattern_len() |
705 | } |
706 | |
707 | #[inline (always)] |
708 | fn max_pattern_len(&self) -> usize { |
709 | (**self).max_pattern_len() |
710 | } |
711 | |
712 | #[inline (always)] |
713 | fn memory_usage(&self) -> usize { |
714 | (**self).memory_usage() |
715 | } |
716 | |
717 | #[inline (always)] |
718 | fn prefilter(&self) -> Option<&Prefilter> { |
719 | (**self).prefilter() |
720 | } |
721 | } |
722 | |
723 | /// Represents the current state of an overlapping search. |
724 | /// |
725 | /// This is used for overlapping searches since they need to know something |
726 | /// about the previous search. For example, when multiple patterns match at the |
727 | /// same position, this state tracks the last reported pattern so that the next |
728 | /// search knows whether to report another matching pattern or continue with |
729 | /// the search at the next position. Additionally, it also tracks which state |
730 | /// the last search call terminated in and the current offset of the search |
731 | /// in the haystack. |
732 | /// |
733 | /// This type provides limited introspection capabilities. The only thing a |
734 | /// caller can do is construct it and pass it around to permit search routines |
735 | /// to use it to track state, and to ask whether a match has been found. |
736 | /// |
737 | /// Callers should always provide a fresh state constructed via |
738 | /// [`OverlappingState::start`] when starting a new search. That same state |
739 | /// should be reused for subsequent searches on the same `Input`. The state |
740 | /// given will advance through the haystack itself. Callers can detect the end |
741 | /// of a search when neither an error nor a match is returned. |
742 | /// |
743 | /// # Example |
744 | /// |
745 | /// This example shows how to manually iterate over all overlapping matches. If |
746 | /// you need this, you might consider using |
747 | /// [`AhoCorasick::find_overlapping_iter`](crate::AhoCorasick::find_overlapping_iter) |
748 | /// instead, but this shows how to correctly use an `OverlappingState`. |
749 | /// |
750 | /// ``` |
751 | /// use aho_corasick::{ |
752 | /// automaton::OverlappingState, |
753 | /// AhoCorasick, Input, Match, |
754 | /// }; |
755 | /// |
756 | /// let patterns = &["append" , "appendage" , "app" ]; |
757 | /// let haystack = "append the app to the appendage" ; |
758 | /// |
759 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
760 | /// let mut state = OverlappingState::start(); |
761 | /// let mut matches = vec![]; |
762 | /// |
763 | /// loop { |
764 | /// ac.find_overlapping(haystack, &mut state); |
765 | /// let mat = match state.get_match() { |
766 | /// None => break, |
767 | /// Some(mat) => mat, |
768 | /// }; |
769 | /// matches.push(mat); |
770 | /// } |
771 | /// let expected = vec![ |
772 | /// Match::must(2, 0..3), |
773 | /// Match::must(0, 0..6), |
774 | /// Match::must(2, 11..14), |
775 | /// Match::must(2, 22..25), |
776 | /// Match::must(0, 22..28), |
777 | /// Match::must(1, 22..31), |
778 | /// ]; |
779 | /// assert_eq!(expected, matches); |
780 | /// ``` |
781 | #[derive (Clone, Debug)] |
782 | pub struct OverlappingState { |
783 | /// The match reported by the most recent overlapping search to use this |
784 | /// state. |
785 | /// |
786 | /// If a search does not find any matches, then it is expected to clear |
787 | /// this value. |
788 | mat: Option<Match>, |
789 | /// The state ID of the state at which the search was in when the call |
790 | /// terminated. When this is a match state, `last_match` must be set to a |
791 | /// non-None value. |
792 | /// |
793 | /// A `None` value indicates the start state of the corresponding |
794 | /// automaton. We cannot use the actual ID, since any one automaton may |
795 | /// have many start states, and which one is in use depends on search-time |
796 | /// factors (such as whether the search is anchored or not). |
797 | id: Option<StateID>, |
798 | /// The position of the search. |
799 | /// |
800 | /// When `id` is None (i.e., we are starting a search), this is set to |
801 | /// the beginning of the search as given by the caller regardless of its |
802 | /// current value. Subsequent calls to an overlapping search pick up at |
803 | /// this offset. |
804 | at: usize, |
805 | /// The index into the matching patterns of the next match to report if the |
806 | /// current state is a match state. Note that this may be 1 greater than |
807 | /// the total number of matches to report for the current match state. (In |
808 | /// which case, no more matches should be reported at the current position |
809 | /// and the search should advance to the next position.) |
810 | next_match_index: Option<usize>, |
811 | } |
812 | |
813 | impl OverlappingState { |
814 | /// Create a new overlapping state that begins at the start state. |
815 | pub fn start() -> OverlappingState { |
816 | OverlappingState { mat: None, id: None, at: 0, next_match_index: None } |
817 | } |
818 | |
819 | /// Return the match result of the most recent search to execute with this |
820 | /// state. |
821 | /// |
822 | /// Every search will clear this result automatically, such that if no |
823 | /// match is found, this will always correctly report `None`. |
824 | pub fn get_match(&self) -> Option<Match> { |
825 | self.mat |
826 | } |
827 | } |
828 | |
829 | /// An iterator of non-overlapping matches in a particular haystack. |
830 | /// |
831 | /// This iterator yields matches according to the [`MatchKind`] used by this |
832 | /// automaton. |
833 | /// |
834 | /// This iterator is constructed via the [`Automaton::try_find_iter`] method. |
835 | /// |
836 | /// The type variable `A` refers to the implementation of the [`Automaton`] |
837 | /// trait used to execute the search. |
838 | /// |
839 | /// The lifetime `'a` refers to the lifetime of the [`Automaton`] |
840 | /// implementation. |
841 | /// |
842 | /// The lifetime `'h` refers to the lifetime of the haystack being searched. |
843 | #[derive (Debug)] |
844 | pub struct FindIter<'a, 'h, A> { |
845 | /// The automaton used to drive the search. |
846 | aut: &'a A, |
847 | /// The input parameters to give to each search call. |
848 | /// |
849 | /// The start position of the search is mutated during iteration. |
850 | input: Input<'h>, |
851 | /// Records the end offset of the most recent match. This is necessary to |
852 | /// handle a corner case for preventing empty matches from overlapping with |
853 | /// the ending bounds of a prior match. |
854 | last_match_end: Option<usize>, |
855 | } |
856 | |
857 | impl<'a, 'h, A: Automaton> FindIter<'a, 'h, A> { |
858 | /// Creates a new non-overlapping iterator. If the given automaton would |
859 | /// return an error on a search with the given input configuration, then |
860 | /// that error is returned here. |
861 | fn new( |
862 | aut: &'a A, |
863 | input: Input<'h>, |
864 | ) -> Result<FindIter<'a, 'h, A>, MatchError> { |
865 | // The only way this search can fail is if we cannot retrieve the start |
866 | // state. e.g., Asking for an anchored search when only unanchored |
867 | // searches are supported. |
868 | let _ = aut.start_state(input.get_anchored())?; |
869 | Ok(FindIter { aut, input, last_match_end: None }) |
870 | } |
871 | |
872 | /// Executes a search and returns a match if one is found. |
873 | /// |
874 | /// This does not advance the input forward. It just executes a search |
875 | /// based on the current configuration/offsets. |
876 | fn search(&self) -> Option<Match> { |
877 | // The unwrap is OK here because we check at iterator construction time |
878 | // that no subsequent search call (using the same configuration) will |
879 | // ever return an error. |
880 | self.aut |
881 | .try_find(&self.input) |
882 | .expect("already checked that no match error can occur" ) |
883 | } |
884 | |
885 | /// Handles the special case of an empty match by ensuring that 1) the |
886 | /// iterator always advances and 2) empty matches never overlap with other |
887 | /// matches. |
888 | /// |
889 | /// (1) is necessary because we principally make progress by setting the |
890 | /// starting location of the next search to the ending location of the last |
891 | /// match. But if a match is empty, then this results in a search that does |
892 | /// not advance and thus does not terminate. |
893 | /// |
894 | /// (2) is not strictly necessary, but makes intuitive sense and matches |
895 | /// the presiding behavior of most general purpose regex engines. |
896 | /// (Obviously this crate isn't a regex engine, but we choose to match |
897 | /// their semantics.) The "intuitive sense" here is that we want to report |
898 | /// NON-overlapping matches. So for example, given the patterns 'a' and |
899 | /// '' (an empty string) against the haystack 'a', without the special |
900 | /// handling, you'd get the matches [0, 1) and [1, 1), where the latter |
901 | /// overlaps with the end bounds of the former. |
902 | /// |
903 | /// Note that we mark this cold and forcefully prevent inlining because |
904 | /// handling empty matches like this is extremely rare and does require |
905 | /// quite a bit of code, comparatively. Keeping this code out of the main |
906 | /// iterator function keeps it smaller and more amenable to inlining |
907 | /// itself. |
908 | #[cold ] |
909 | #[inline (never)] |
910 | fn handle_overlapping_empty_match( |
911 | &mut self, |
912 | mut m: Match, |
913 | ) -> Option<Match> { |
914 | assert!(m.is_empty()); |
915 | if Some(m.end()) == self.last_match_end { |
916 | self.input.set_start(self.input.start().checked_add(1).unwrap()); |
917 | m = self.search()?; |
918 | } |
919 | Some(m) |
920 | } |
921 | } |
922 | |
923 | impl<'a, 'h, A: Automaton> Iterator for FindIter<'a, 'h, A> { |
924 | type Item = Match; |
925 | |
926 | #[inline (always)] |
927 | fn next(&mut self) -> Option<Match> { |
928 | let mut m: Match = self.search()?; |
929 | if m.is_empty() { |
930 | m = self.handle_overlapping_empty_match(m)?; |
931 | } |
932 | self.input.set_start(m.end()); |
933 | self.last_match_end = Some(m.end()); |
934 | Some(m) |
935 | } |
936 | } |
937 | |
938 | /// An iterator of overlapping matches in a particular haystack. |
939 | /// |
940 | /// This iterator will report all possible matches in a particular haystack, |
941 | /// even when the matches overlap. |
942 | /// |
943 | /// This iterator is constructed via the |
944 | /// [`Automaton::try_find_overlapping_iter`] method. |
945 | /// |
946 | /// The type variable `A` refers to the implementation of the [`Automaton`] |
947 | /// trait used to execute the search. |
948 | /// |
949 | /// The lifetime `'a` refers to the lifetime of the [`Automaton`] |
950 | /// implementation. |
951 | /// |
952 | /// The lifetime `'h` refers to the lifetime of the haystack being searched. |
953 | #[derive (Debug)] |
954 | pub struct FindOverlappingIter<'a, 'h, A> { |
955 | aut: &'a A, |
956 | input: Input<'h>, |
957 | state: OverlappingState, |
958 | } |
959 | |
960 | impl<'a, 'h, A: Automaton> Iterator for FindOverlappingIter<'a, 'h, A> { |
961 | type Item = Match; |
962 | |
963 | #[inline (always)] |
964 | fn next(&mut self) -> Option<Match> { |
965 | self.aut |
966 | .try_find_overlapping(&self.input, &mut self.state) |
967 | .expect(msg:"already checked that no match error can occur here" ); |
968 | self.state.get_match() |
969 | } |
970 | } |
971 | |
972 | /// An iterator that reports matches in a stream. |
973 | /// |
974 | /// This iterator yields elements of type `io::Result<Match>`, where an error |
975 | /// is reported if there was a problem reading from the underlying stream. |
976 | /// The iterator terminates only when the underlying stream reaches `EOF`. |
977 | /// |
978 | /// This iterator is constructed via the [`Automaton::try_stream_find_iter`] |
979 | /// method. |
980 | /// |
981 | /// The type variable `A` refers to the implementation of the [`Automaton`] |
982 | /// trait used to execute the search. |
983 | /// |
984 | /// The type variable `R` refers to the `io::Read` stream that is being read |
985 | /// from. |
986 | /// |
987 | /// The lifetime `'a` refers to the lifetime of the [`Automaton`] |
988 | /// implementation. |
989 | #[cfg (feature = "std" )] |
990 | #[derive (Debug)] |
991 | pub struct StreamFindIter<'a, A, R> { |
992 | it: StreamChunkIter<'a, A, R>, |
993 | } |
994 | |
995 | #[cfg (feature = "std" )] |
996 | impl<'a, A: Automaton, R: std::io::Read> Iterator |
997 | for StreamFindIter<'a, A, R> |
998 | { |
999 | type Item = std::io::Result<Match>; |
1000 | |
1001 | fn next(&mut self) -> Option<std::io::Result<Match>> { |
1002 | loop { |
1003 | match self.it.next() { |
1004 | None => return None, |
1005 | Some(Err(err: Error)) => return Some(Err(err)), |
1006 | Some(Ok(StreamChunk::NonMatch { .. })) => {} |
1007 | Some(Ok(StreamChunk::Match { mat: Match, .. })) => { |
1008 | return Some(Ok(mat)); |
1009 | } |
1010 | } |
1011 | } |
1012 | } |
1013 | } |
1014 | |
1015 | /// An iterator that reports matches in a stream. |
1016 | /// |
1017 | /// (This doesn't actually implement the `Iterator` trait because it returns |
1018 | /// something with a lifetime attached to a buffer it owns, but that's OK. It |
1019 | /// still has a `next` method and is iterator-like enough to be fine.) |
1020 | /// |
1021 | /// This iterator yields elements of type `io::Result<StreamChunk>`, where |
1022 | /// an error is reported if there was a problem reading from the underlying |
1023 | /// stream. The iterator terminates only when the underlying stream reaches |
1024 | /// `EOF`. |
1025 | /// |
1026 | /// The idea here is that each chunk represents either a match or a non-match, |
1027 | /// and if you concatenated all of the chunks together, you'd reproduce the |
1028 | /// entire contents of the stream, byte-for-byte. |
1029 | /// |
1030 | /// This chunk machinery is a bit complicated and it isn't strictly required |
1031 | /// for a stream searcher that just reports matches. But we do need something |
1032 | /// like this to deal with the "replacement" API, which needs to know which |
1033 | /// chunks it can copy and which it needs to replace. |
1034 | #[cfg (feature = "std" )] |
1035 | #[derive (Debug)] |
1036 | struct StreamChunkIter<'a, A, R> { |
1037 | /// The underlying automaton to do the search. |
1038 | aut: &'a A, |
1039 | /// The source of bytes we read from. |
1040 | rdr: R, |
1041 | /// A roll buffer for managing bytes from `rdr`. Basically, this is used |
1042 | /// to handle the case of a match that is split by two different |
1043 | /// calls to `rdr.read()`. This isn't strictly needed if all we needed to |
1044 | /// do was report matches, but here we are reporting chunks of non-matches |
1045 | /// and matches and in order to do that, we really just cannot treat our |
1046 | /// stream as non-overlapping blocks of bytes. We need to permit some |
1047 | /// overlap while we retain bytes from a previous `read` call in memory. |
1048 | buf: crate::util::buffer::Buffer, |
1049 | /// The unanchored starting state of this automaton. |
1050 | start: StateID, |
1051 | /// The state of the automaton. |
1052 | sid: StateID, |
1053 | /// The absolute position over the entire stream. |
1054 | absolute_pos: usize, |
1055 | /// The position we're currently at within `buf`. |
1056 | buffer_pos: usize, |
1057 | /// The buffer position of the end of the bytes that we last returned |
1058 | /// to the caller. Basically, whenever we find a match, we look to see if |
1059 | /// there is a difference between where the match started and the position |
1060 | /// of the last byte we returned to the caller. If there's a difference, |
1061 | /// then we need to return a 'NonMatch' chunk. |
1062 | buffer_reported_pos: usize, |
1063 | } |
1064 | |
1065 | #[cfg (feature = "std" )] |
1066 | impl<'a, A: Automaton, R: std::io::Read> StreamChunkIter<'a, A, R> { |
1067 | fn new( |
1068 | aut: &'a A, |
1069 | rdr: R, |
1070 | ) -> Result<StreamChunkIter<'a, A, R>, MatchError> { |
1071 | // This restriction is a carry-over from older versions of this crate. |
1072 | // I didn't have the bandwidth to think through how to handle, say, |
1073 | // leftmost-first or leftmost-longest matching, but... it should be |
1074 | // possible? The main problem is that once you see a match state in |
1075 | // leftmost-first semantics, you can't just stop at that point and |
1076 | // report a match. You have to keep going until you either hit a dead |
1077 | // state or EOF. So how do you know when you'll hit a dead state? Well, |
1078 | // you don't. With Aho-Corasick, I believe you can put a bound on it |
1079 | // and say, "once a match has been seen, you'll need to scan forward at |
1080 | // most N bytes" where N=aut.max_pattern_len(). |
1081 | // |
1082 | // Which is fine, but it does mean that state about whether we're still |
1083 | // looking for a dead state or not needs to persist across buffer |
1084 | // refills. Which this code doesn't really handle. It does preserve |
1085 | // *some* state across buffer refills, basically ensuring that a match |
1086 | // span is always in memory. |
1087 | if !aut.match_kind().is_standard() { |
1088 | return Err(MatchError::unsupported_stream(aut.match_kind())); |
1089 | } |
1090 | // This is kind of a cop-out, but empty matches are SUPER annoying. |
1091 | // If we know they can't happen (which is what we enforce here), then |
1092 | // it makes a lot of logic much simpler. With that said, I'm open to |
1093 | // supporting this case, but we need to define proper semantics for it |
1094 | // first. It wasn't totally clear to me what it should do at the time |
1095 | // of writing, so I decided to just be conservative. |
1096 | // |
1097 | // It also seems like a very weird case to support anyway. Why search a |
1098 | // stream if you're just going to get a match at every position? |
1099 | // |
1100 | // ¯\_(ツ)_/¯ |
1101 | if aut.min_pattern_len() == 0 { |
1102 | return Err(MatchError::unsupported_empty()); |
1103 | } |
1104 | let start = aut.start_state(Anchored::No)?; |
1105 | Ok(StreamChunkIter { |
1106 | aut, |
1107 | rdr, |
1108 | buf: crate::util::buffer::Buffer::new(aut.max_pattern_len()), |
1109 | start, |
1110 | sid: start, |
1111 | absolute_pos: 0, |
1112 | buffer_pos: 0, |
1113 | buffer_reported_pos: 0, |
1114 | }) |
1115 | } |
1116 | |
1117 | fn next(&mut self) -> Option<std::io::Result<StreamChunk>> { |
1118 | // This code is pretty gnarly. It IS simpler than the equivalent code |
1119 | // in the previous aho-corasick release, in part because we inline |
1120 | // automaton traversal here and also in part because we have abdicated |
1121 | // support for automatons that contain an empty pattern. |
1122 | // |
1123 | // I suspect this code could be made a bit simpler by designing a |
1124 | // better buffer abstraction. |
1125 | // |
1126 | // But in general, this code is basically write-only. So you'll need |
1127 | // to go through it step-by-step to grok it. One of the key bits of |
1128 | // complexity is tracking a few different offsets. 'buffer_pos' is |
1129 | // where we are in the buffer for search. 'buffer_reported_pos' is the |
1130 | // position immediately following the last byte in the buffer that |
1131 | // we've returned to the caller. And 'absolute_pos' is the overall |
1132 | // current absolute position of the search in the entire stream, and |
1133 | // this is what match spans are reported in terms of. |
1134 | loop { |
1135 | if self.aut.is_match(self.sid) { |
1136 | let mat = self.get_match(); |
1137 | if let Some(r) = self.get_non_match_chunk(mat) { |
1138 | self.buffer_reported_pos += r.len(); |
1139 | let bytes = &self.buf.buffer()[r]; |
1140 | return Some(Ok(StreamChunk::NonMatch { bytes })); |
1141 | } |
1142 | self.sid = self.start; |
1143 | let r = self.get_match_chunk(mat); |
1144 | self.buffer_reported_pos += r.len(); |
1145 | let bytes = &self.buf.buffer()[r]; |
1146 | return Some(Ok(StreamChunk::Match { bytes, mat })); |
1147 | } |
1148 | if self.buffer_pos >= self.buf.buffer().len() { |
1149 | if let Some(r) = self.get_pre_roll_non_match_chunk() { |
1150 | self.buffer_reported_pos += r.len(); |
1151 | let bytes = &self.buf.buffer()[r]; |
1152 | return Some(Ok(StreamChunk::NonMatch { bytes })); |
1153 | } |
1154 | if self.buf.buffer().len() >= self.buf.min_buffer_len() { |
1155 | self.buffer_pos = self.buf.min_buffer_len(); |
1156 | self.buffer_reported_pos -= |
1157 | self.buf.buffer().len() - self.buf.min_buffer_len(); |
1158 | self.buf.roll(); |
1159 | } |
1160 | match self.buf.fill(&mut self.rdr) { |
1161 | Err(err) => return Some(Err(err)), |
1162 | Ok(true) => {} |
1163 | Ok(false) => { |
1164 | // We've hit EOF, but if there are still some |
1165 | // unreported bytes remaining, return them now. |
1166 | if let Some(r) = self.get_eof_non_match_chunk() { |
1167 | self.buffer_reported_pos += r.len(); |
1168 | let bytes = &self.buf.buffer()[r]; |
1169 | return Some(Ok(StreamChunk::NonMatch { bytes })); |
1170 | } |
1171 | // We've reported everything! |
1172 | return None; |
1173 | } |
1174 | } |
1175 | } |
1176 | let start = self.absolute_pos; |
1177 | for &byte in self.buf.buffer()[self.buffer_pos..].iter() { |
1178 | self.sid = self.aut.next_state(Anchored::No, self.sid, byte); |
1179 | self.absolute_pos += 1; |
1180 | if self.aut.is_match(self.sid) { |
1181 | break; |
1182 | } |
1183 | } |
1184 | self.buffer_pos += self.absolute_pos - start; |
1185 | } |
1186 | } |
1187 | |
1188 | /// Return a match chunk for the given match. It is assumed that the match |
1189 | /// ends at the current `buffer_pos`. |
1190 | fn get_match_chunk(&self, mat: Match) -> core::ops::Range<usize> { |
1191 | let start = self.buffer_pos - mat.len(); |
1192 | let end = self.buffer_pos; |
1193 | start..end |
1194 | } |
1195 | |
1196 | /// Return a non-match chunk, if necessary, just before reporting a match. |
1197 | /// This returns `None` if there is nothing to report. Otherwise, this |
1198 | /// assumes that the given match ends at the current `buffer_pos`. |
1199 | fn get_non_match_chunk( |
1200 | &self, |
1201 | mat: Match, |
1202 | ) -> Option<core::ops::Range<usize>> { |
1203 | let buffer_mat_start = self.buffer_pos - mat.len(); |
1204 | if buffer_mat_start > self.buffer_reported_pos { |
1205 | let start = self.buffer_reported_pos; |
1206 | let end = buffer_mat_start; |
1207 | return Some(start..end); |
1208 | } |
1209 | None |
1210 | } |
1211 | |
1212 | /// Look for any bytes that should be reported as a non-match just before |
1213 | /// rolling the buffer. |
1214 | /// |
1215 | /// Note that this only reports bytes up to `buffer.len() - |
1216 | /// min_buffer_len`, as it's not possible to know whether the bytes |
1217 | /// following that will participate in a match or not. |
1218 | fn get_pre_roll_non_match_chunk(&self) -> Option<core::ops::Range<usize>> { |
1219 | let end = |
1220 | self.buf.buffer().len().saturating_sub(self.buf.min_buffer_len()); |
1221 | if self.buffer_reported_pos < end { |
1222 | return Some(self.buffer_reported_pos..end); |
1223 | } |
1224 | None |
1225 | } |
1226 | |
1227 | /// Return any unreported bytes as a non-match up to the end of the buffer. |
1228 | /// |
1229 | /// This should only be called when the entire contents of the buffer have |
1230 | /// been searched and EOF has been hit when trying to fill the buffer. |
1231 | fn get_eof_non_match_chunk(&self) -> Option<core::ops::Range<usize>> { |
1232 | if self.buffer_reported_pos < self.buf.buffer().len() { |
1233 | return Some(self.buffer_reported_pos..self.buf.buffer().len()); |
1234 | } |
1235 | None |
1236 | } |
1237 | |
1238 | /// Return the match at the current position for the current state. |
1239 | /// |
1240 | /// This panics if `self.aut.is_match(self.sid)` isn't true. |
1241 | fn get_match(&self) -> Match { |
1242 | get_match(self.aut, self.sid, 0, self.absolute_pos) |
1243 | } |
1244 | } |
1245 | |
1246 | /// A single chunk yielded by the stream chunk iterator. |
1247 | /// |
1248 | /// The `'r` lifetime refers to the lifetime of the stream chunk iterator. |
1249 | #[cfg (feature = "std" )] |
1250 | #[derive (Debug)] |
1251 | enum StreamChunk<'r> { |
1252 | /// A chunk that does not contain any matches. |
1253 | NonMatch { bytes: &'r [u8] }, |
1254 | /// A chunk that precisely contains a match. |
1255 | Match { bytes: &'r [u8], mat: Match }, |
1256 | } |
1257 | |
1258 | #[inline (never)] |
1259 | pub(crate) fn try_find_fwd<A: Automaton + ?Sized>( |
1260 | aut: &A, |
1261 | input: &Input<'_>, |
1262 | ) -> Result<Option<Match>, MatchError> { |
1263 | if input.is_done() { |
1264 | return Ok(None); |
1265 | } |
1266 | let earliest: bool = aut.match_kind().is_standard() || input.get_earliest(); |
1267 | if input.get_anchored().is_anchored() { |
1268 | try_find_fwd_imp(aut, input, pre:None, Anchored::Yes, earliest) |
1269 | } else if let Some(pre: &Prefilter) = aut.prefilter() { |
1270 | if earliest { |
1271 | try_find_fwd_imp(aut, input, pre:Some(pre), Anchored::No, earliest:true) |
1272 | } else { |
1273 | try_find_fwd_imp(aut, input, pre:Some(pre), Anchored::No, earliest:false) |
1274 | } |
1275 | } else { |
1276 | if earliest { |
1277 | try_find_fwd_imp(aut, input, pre:None, Anchored::No, earliest:true) |
1278 | } else { |
1279 | try_find_fwd_imp(aut, input, pre:None, Anchored::No, earliest:false) |
1280 | } |
1281 | } |
1282 | } |
1283 | |
1284 | #[inline (always)] |
1285 | fn try_find_fwd_imp<A: Automaton + ?Sized>( |
1286 | aut: &A, |
1287 | input: &Input<'_>, |
1288 | pre: Option<&Prefilter>, |
1289 | anchored: Anchored, |
1290 | earliest: bool, |
1291 | ) -> Result<Option<Match>, MatchError> { |
1292 | let mut sid = aut.start_state(input.get_anchored())?; |
1293 | let mut at = input.start(); |
1294 | let mut mat = None; |
1295 | if aut.is_match(sid) { |
1296 | mat = Some(get_match(aut, sid, 0, at)); |
1297 | if earliest { |
1298 | return Ok(mat); |
1299 | } |
1300 | } |
1301 | if let Some(pre) = pre { |
1302 | match pre.find_in(input.haystack(), input.get_span()) { |
1303 | Candidate::None => return Ok(None), |
1304 | Candidate::Match(m) => return Ok(Some(m)), |
1305 | Candidate::PossibleStartOfMatch(i) => { |
1306 | at = i; |
1307 | } |
1308 | } |
1309 | } |
1310 | while at < input.end() { |
1311 | // I've tried unrolling this loop and eliding bounds checks, but no |
1312 | // matter what I did, I could not observe a consistent improvement on |
1313 | // any benchmark I could devise. (If someone wants to re-litigate this, |
1314 | // the way to do it is to add an 'next_state_unchecked' method to the |
1315 | // 'Automaton' trait with a default impl that uses 'next_state'. Then |
1316 | // use 'aut.next_state_unchecked' here and implement it on DFA using |
1317 | // unchecked slice index acces.) |
1318 | sid = aut.next_state(anchored, sid, input.haystack()[at]); |
1319 | if aut.is_special(sid) { |
1320 | if aut.is_dead(sid) { |
1321 | return Ok(mat); |
1322 | } else if aut.is_match(sid) { |
1323 | // We use 'at + 1' here because the match state is entered |
1324 | // at the last byte of the pattern. Since we use half-open |
1325 | // intervals, the end of the range of the match is one past the |
1326 | // last byte. |
1327 | let m = get_match(aut, sid, 0, at + 1); |
1328 | // For the automata in this crate, we make a size trade off |
1329 | // where we reuse the same automaton for both anchored and |
1330 | // unanchored searches. We achieve this, principally, by simply |
1331 | // not following failure transitions while computing the next |
1332 | // state. Instead, if we fail to find the next state, we return |
1333 | // a dead state, which instructs the search to stop. (This |
1334 | // is why 'next_state' needs to know whether the search is |
1335 | // anchored or not.) In addition, we have different start |
1336 | // states for anchored and unanchored searches. The latter has |
1337 | // a self-loop where as the former does not. |
1338 | // |
1339 | // In this way, we can use the same trie to execute both |
1340 | // anchored and unanchored searches. There is a catch though. |
1341 | // When building an Aho-Corasick automaton for unanchored |
1342 | // searches, we copy matches from match states to other states |
1343 | // (which would otherwise not be match states) if they are |
1344 | // reachable via a failure transition. In the case of an |
1345 | // anchored search, we *specifically* do not want to report |
1346 | // these matches because they represent matches that start past |
1347 | // the beginning of the search. |
1348 | // |
1349 | // Now we could tweak the automaton somehow to differentiate |
1350 | // anchored from unanchored match states, but this would make |
1351 | // 'aut.is_match' and potentially 'aut.is_special' slower. And |
1352 | // also make the automaton itself more complex. |
1353 | // |
1354 | // Instead, we insert a special hack: if the search is |
1355 | // anchored, we simply ignore matches that don't begin at |
1356 | // the start of the search. This is not quite ideal, but we |
1357 | // do specialize this function in such a way that unanchored |
1358 | // searches don't pay for this additional branch. While this |
1359 | // might cause a search to continue on for more than it |
1360 | // otherwise optimally would, it will be no more than the |
1361 | // longest pattern in the automaton. The reason for this is |
1362 | // that we ensure we don't follow failure transitions during |
1363 | // an anchored search. Combined with using a different anchored |
1364 | // starting state with no self-loop, we guarantee that we'll |
1365 | // at worst move through a number of transitions equal to the |
1366 | // longest pattern. |
1367 | // |
1368 | // Now for DFAs, the whole point of them is to eliminate |
1369 | // failure transitions entirely. So there is no way to say "if |
1370 | // it's an anchored search don't follow failure transitions." |
1371 | // Instead, we actually have to build two entirely separate |
1372 | // automatons into the transition table. One with failure |
1373 | // transitions built into it and another that is effectively |
1374 | // just an encoding of the base trie into a transition table. |
1375 | // DFAs still need this check though, because the match states |
1376 | // still carry matches only reachable via a failure transition. |
1377 | // Why? Because removing them seems difficult, although I |
1378 | // haven't given it a lot of thought. |
1379 | if !(anchored.is_anchored() && m.start() > input.start()) { |
1380 | mat = Some(m); |
1381 | if earliest { |
1382 | return Ok(mat); |
1383 | } |
1384 | } |
1385 | } else if let Some(pre) = pre { |
1386 | // If we're here, we know it's a special state that is not a |
1387 | // dead or a match state AND that a prefilter is active. Thus, |
1388 | // it must be a start state. |
1389 | debug_assert!(aut.is_start(sid)); |
1390 | // We don't care about 'Candidate::Match' here because if such |
1391 | // a match were possible, it would have been returned above |
1392 | // when we run the prefilter before walking the automaton. |
1393 | let span = Span::from(at..input.end()); |
1394 | match pre.find_in(input.haystack(), span).into_option() { |
1395 | None => return Ok(None), |
1396 | Some(i) => { |
1397 | if i > at { |
1398 | at = i; |
1399 | continue; |
1400 | } |
1401 | } |
1402 | } |
1403 | } else { |
1404 | // When pre.is_none(), then starting states should not be |
1405 | // treated as special. That is, without a prefilter, is_special |
1406 | // should only return true when the state is a dead or a match |
1407 | // state. |
1408 | // |
1409 | // It is possible to execute a search without a prefilter even |
1410 | // when the underlying searcher has one: an anchored search. |
1411 | // But in this case, the automaton makes it impossible to move |
1412 | // back to the start state by construction, and thus, we should |
1413 | // never reach this branch. |
1414 | debug_assert!(false, "unreachable" ); |
1415 | } |
1416 | } |
1417 | at += 1; |
1418 | } |
1419 | Ok(mat) |
1420 | } |
1421 | |
1422 | #[inline (never)] |
1423 | fn try_find_overlapping_fwd<A: Automaton + ?Sized>( |
1424 | aut: &A, |
1425 | input: &Input<'_>, |
1426 | state: &mut OverlappingState, |
1427 | ) -> Result<(), MatchError> { |
1428 | state.mat = None; |
1429 | if input.is_done() { |
1430 | return Ok(()); |
1431 | } |
1432 | // Searching with a pattern ID is always anchored, so we should only ever |
1433 | // use a prefilter when no pattern ID is given. |
1434 | if aut.prefilter().is_some() && !input.get_anchored().is_anchored() { |
1435 | let pre: &Prefilter = aut.prefilter().unwrap(); |
1436 | try_find_overlapping_fwd_imp(aut, input, pre:Some(pre), state) |
1437 | } else { |
1438 | try_find_overlapping_fwd_imp(aut, input, pre:None, state) |
1439 | } |
1440 | } |
1441 | |
1442 | #[inline (always)] |
1443 | fn try_find_overlapping_fwd_imp<A: Automaton + ?Sized>( |
1444 | aut: &A, |
1445 | input: &Input<'_>, |
1446 | pre: Option<&Prefilter>, |
1447 | state: &mut OverlappingState, |
1448 | ) -> Result<(), MatchError> { |
1449 | let mut sid = match state.id { |
1450 | None => { |
1451 | let sid = aut.start_state(input.get_anchored())?; |
1452 | // Handle the case where the start state is a match state. That is, |
1453 | // the empty string is in our automaton. We report every match we |
1454 | // can here before moving on and updating 'state.at' and 'state.id' |
1455 | // to find more matches in other parts of the haystack. |
1456 | if aut.is_match(sid) { |
1457 | let i = state.next_match_index.unwrap_or(0); |
1458 | let len = aut.match_len(sid); |
1459 | if i < len { |
1460 | state.next_match_index = Some(i + 1); |
1461 | state.mat = Some(get_match(aut, sid, i, input.start())); |
1462 | return Ok(()); |
1463 | } |
1464 | } |
1465 | state.at = input.start(); |
1466 | state.id = Some(sid); |
1467 | state.next_match_index = None; |
1468 | state.mat = None; |
1469 | sid |
1470 | } |
1471 | Some(sid) => { |
1472 | // If we still have matches left to report in this state then |
1473 | // report them until we've exhausted them. Only after that do we |
1474 | // advance to the next offset in the haystack. |
1475 | if let Some(i) = state.next_match_index { |
1476 | let len = aut.match_len(sid); |
1477 | if i < len { |
1478 | state.next_match_index = Some(i + 1); |
1479 | state.mat = Some(get_match(aut, sid, i, state.at + 1)); |
1480 | return Ok(()); |
1481 | } |
1482 | // Once we've reported all matches at a given position, we need |
1483 | // to advance the search to the next position. |
1484 | state.at += 1; |
1485 | state.next_match_index = None; |
1486 | state.mat = None; |
1487 | } |
1488 | sid |
1489 | } |
1490 | }; |
1491 | while state.at < input.end() { |
1492 | sid = aut.next_state( |
1493 | input.get_anchored(), |
1494 | sid, |
1495 | input.haystack()[state.at], |
1496 | ); |
1497 | if aut.is_special(sid) { |
1498 | state.id = Some(sid); |
1499 | if aut.is_dead(sid) { |
1500 | return Ok(()); |
1501 | } else if aut.is_match(sid) { |
1502 | state.next_match_index = Some(1); |
1503 | state.mat = Some(get_match(aut, sid, 0, state.at + 1)); |
1504 | return Ok(()); |
1505 | } else if let Some(pre) = pre { |
1506 | // If we're here, we know it's a special state that is not a |
1507 | // dead or a match state AND that a prefilter is active. Thus, |
1508 | // it must be a start state. |
1509 | debug_assert!(aut.is_start(sid)); |
1510 | let span = Span::from(state.at..input.end()); |
1511 | match pre.find_in(input.haystack(), span).into_option() { |
1512 | None => return Ok(()), |
1513 | Some(i) => { |
1514 | if i > state.at { |
1515 | state.at = i; |
1516 | continue; |
1517 | } |
1518 | } |
1519 | } |
1520 | } else { |
1521 | // When pre.is_none(), then starting states should not be |
1522 | // treated as special. That is, without a prefilter, is_special |
1523 | // should only return true when the state is a dead or a match |
1524 | // state. |
1525 | // |
1526 | // ... except for one special case: in stream searching, we |
1527 | // currently call overlapping search with a 'None' prefilter, |
1528 | // regardless of whether one exists or not, because stream |
1529 | // searching can't currently deal with prefilters correctly in |
1530 | // all cases. |
1531 | } |
1532 | } |
1533 | state.at += 1; |
1534 | } |
1535 | state.id = Some(sid); |
1536 | Ok(()) |
1537 | } |
1538 | |
1539 | #[inline (always)] |
1540 | fn get_match<A: Automaton + ?Sized>( |
1541 | aut: &A, |
1542 | sid: StateID, |
1543 | index: usize, |
1544 | at: usize, |
1545 | ) -> Match { |
1546 | let pid: PatternID = aut.match_pattern(sid, index); |
1547 | let len: usize = aut.pattern_len(pid); |
1548 | Match::new(pattern:pid, (at - len)..at) |
1549 | } |
1550 | |
1551 | /// Write a prefix "state" indicator for fmt::Debug impls. It always writes |
1552 | /// exactly two printable bytes to the given formatter. |
1553 | /// |
1554 | /// Specifically, this tries to succinctly distinguish the different types of |
1555 | /// states: dead states, start states and match states. It even accounts for |
1556 | /// the possible overlappings of different state types. (The only possible |
1557 | /// overlapping is that of match and start states.) |
1558 | pub(crate) fn fmt_state_indicator<A: Automaton>( |
1559 | f: &mut core::fmt::Formatter<'_>, |
1560 | aut: A, |
1561 | id: StateID, |
1562 | ) -> core::fmt::Result { |
1563 | if aut.is_dead(sid:id) { |
1564 | write!(f, "D " )?; |
1565 | } else if aut.is_match(sid:id) { |
1566 | if aut.is_start(sid:id) { |
1567 | write!(f, "*>" )?; |
1568 | } else { |
1569 | write!(f, "* " )?; |
1570 | } |
1571 | } else if aut.is_start(sid:id) { |
1572 | write!(f, " >" )?; |
1573 | } else { |
1574 | write!(f, " " )?; |
1575 | } |
1576 | Ok(()) |
1577 | } |
1578 | |
1579 | /// Return an iterator of transitions in a sparse format given an iterator |
1580 | /// of all explicitly defined transitions. The iterator yields ranges of |
1581 | /// transitions, such that any adjacent transitions mapped to the same |
1582 | /// state are combined into a single range. |
1583 | pub(crate) fn sparse_transitions<'a>( |
1584 | mut it: impl Iterator<Item = (u8, StateID)> + 'a, |
1585 | ) -> impl Iterator<Item = (u8, u8, StateID)> + 'a { |
1586 | let mut cur: Option<(u8, u8, StateID)> = None; |
1587 | core::iter::from_fn(move || { |
1588 | while let Some((class: u8, next: StateID)) = it.next() { |
1589 | let (prev_start: u8, prev_end: u8, prev_next: StateID) = match cur { |
1590 | Some(x: (u8, u8, StateID)) => x, |
1591 | None => { |
1592 | cur = Some((class, class, next)); |
1593 | continue; |
1594 | } |
1595 | }; |
1596 | if prev_next == next { |
1597 | cur = Some((prev_start, class, prev_next)); |
1598 | } else { |
1599 | cur = Some((class, class, next)); |
1600 | return Some((prev_start, prev_end, prev_next)); |
1601 | } |
1602 | } |
1603 | if let Some((start: u8, end: u8, next: StateID)) = cur.take() { |
1604 | return Some((start, end, next)); |
1605 | } |
1606 | None |
1607 | }) |
1608 | } |
1609 | |