1 | use core::{ |
2 | fmt::Debug, |
3 | panic::{RefUnwindSafe, UnwindSafe}, |
4 | }; |
5 | |
6 | use alloc::{string::String, sync::Arc, vec::Vec}; |
7 | |
8 | use crate::{ |
9 | automaton::{self, Automaton, OverlappingState}, |
10 | dfa, |
11 | nfa::{contiguous, noncontiguous}, |
12 | util::{ |
13 | error::{BuildError, MatchError}, |
14 | prefilter::Prefilter, |
15 | primitives::{PatternID, StateID}, |
16 | search::{Anchored, Input, Match, MatchKind, StartKind}, |
17 | }, |
18 | }; |
19 | |
20 | /// An automaton for searching multiple strings in linear time. |
21 | /// |
22 | /// The `AhoCorasick` type supports a few basic ways of constructing an |
23 | /// automaton, with the default being [`AhoCorasick::new`]. However, there |
24 | /// are a fair number of configurable options that can be set by using |
25 | /// [`AhoCorasickBuilder`] instead. Such options include, but are not limited |
26 | /// to, how matches are determined, simple case insensitivity, whether to use a |
27 | /// DFA or not and various knobs for controlling the space-vs-time trade offs |
28 | /// taken when building the automaton. |
29 | /// |
30 | /// # Resource usage |
31 | /// |
32 | /// Aho-Corasick automatons are always constructed in `O(p)` time, where |
33 | /// `p` is the combined length of all patterns being searched. With that |
34 | /// said, building an automaton can be fairly costly because of high constant |
35 | /// factors, particularly when enabling the [DFA](AhoCorasickKind::DFA) option |
36 | /// with [`AhoCorasickBuilder::kind`]. For this reason, it's generally a good |
37 | /// idea to build an automaton once and reuse it as much as possible. |
38 | /// |
39 | /// Aho-Corasick automatons can also use a fair bit of memory. To get |
40 | /// a concrete idea of how much memory is being used, try using the |
41 | /// [`AhoCorasick::memory_usage`] method. |
42 | /// |
43 | /// To give a quick idea of the differences between Aho-Corasick |
44 | /// implementations and their resource usage, here's a sample of construction |
45 | /// times and heap memory used after building an automaton from 100,000 |
46 | /// randomly selected titles from Wikipedia: |
47 | /// |
48 | /// * 99MB for a [`noncontiguous::NFA`] in 240ms. |
49 | /// * 21MB for a [`contiguous::NFA`] in 275ms. |
50 | /// * 1.6GB for a [`dfa::DFA`] in 1.88s. |
51 | /// |
52 | /// (Note that the memory usage above reflects the size of each automaton and |
53 | /// not peak memory usage. For example, building a contiguous NFA requires |
54 | /// first building a noncontiguous NFA. Once the contiguous NFA is built, the |
55 | /// noncontiguous NFA is freed.) |
56 | /// |
57 | /// This experiment very strongly argues that a contiguous NFA is often the |
58 | /// best balance in terms of resource usage. It takes a little longer to build, |
59 | /// but its memory usage is quite small. Its search speed (not listed) is |
60 | /// also often faster than a noncontiguous NFA, but a little slower than a |
61 | /// DFA. Indeed, when no specific [`AhoCorasickKind`] is used (which is the |
62 | /// default), a contiguous NFA is used in most cases. |
63 | /// |
64 | /// The only "catch" to using a contiguous NFA is that, because of its variety |
65 | /// of compression tricks, it may not be able to support automatons as large as |
66 | /// what the noncontiguous NFA supports. In which case, building a contiguous |
67 | /// NFA will fail and (by default) `AhoCorasick` will automatically fall |
68 | /// back to a noncontiguous NFA. (This typically only happens when building |
69 | /// automatons from millions of patterns.) Otherwise, the small additional time |
70 | /// for building a contiguous NFA is almost certainly worth it. |
71 | /// |
72 | /// # Cloning |
73 | /// |
74 | /// The `AhoCorasick` type uses thread safe reference counting internally. It |
75 | /// is guaranteed that it is cheap to clone. |
76 | /// |
77 | /// # Search configuration |
78 | /// |
79 | /// Most of the search routines accept anything that can be cheaply converted |
80 | /// to an [`Input`]. This includes `&[u8]`, `&str` and `Input` itself. |
81 | /// |
82 | /// # Construction failure |
83 | /// |
84 | /// It is generally possible for building an Aho-Corasick automaton to fail. |
85 | /// Construction can fail in generally one way: when the inputs provided are |
86 | /// too big. Whether that's a pattern that is too long, too many patterns |
87 | /// or some combination of both. A first approximation for the scale at which |
88 | /// construction can fail is somewhere around "millions of patterns." |
89 | /// |
90 | /// For that reason, if you're building an Aho-Corasick automaton from |
91 | /// untrusted input (or input that doesn't have any reasonable bounds on its |
92 | /// size), then it is strongly recommended to handle the possibility of an |
93 | /// error. |
94 | /// |
95 | /// If you're constructing an Aho-Corasick automaton from static or trusted |
96 | /// data, then it is likely acceptable to panic (by calling `unwrap()` or |
97 | /// `expect()`) if construction fails. |
98 | /// |
99 | /// # Fallibility |
100 | /// |
101 | /// The `AhoCorasick` type provides a number of methods for searching, as one |
102 | /// might expect. Depending on how the Aho-Corasick automaton was built and |
103 | /// depending on the search configuration, it is possible for a search to |
104 | /// return an error. Since an error is _never_ dependent on the actual contents |
105 | /// of the haystack, this type provides both infallible and fallible methods |
106 | /// for searching. The infallible methods panic if an error occurs, and can be |
107 | /// used for convenience and when you know the search will never return an |
108 | /// error. |
109 | /// |
110 | /// For example, the [`AhoCorasick::find_iter`] method is the infallible |
111 | /// version of the [`AhoCorasick::try_find_iter`] method. |
112 | /// |
113 | /// Examples of errors that can occur: |
114 | /// |
115 | /// * Running a search that requires [`MatchKind::Standard`] semantics (such |
116 | /// as a stream or overlapping search) with an automaton that was built with |
117 | /// [`MatchKind::LeftmostFirst`] or [`MatchKind::LeftmostLongest`] semantics. |
118 | /// * Running an anchored search with an automaton that only supports |
119 | /// unanchored searches. (By default, `AhoCorasick` only supports unanchored |
120 | /// searches. But this can be toggled with [`AhoCorasickBuilder::start_kind`].) |
121 | /// * Running an unanchored search with an automaton that only supports |
122 | /// anchored searches. |
123 | /// |
124 | /// The common thread between the different types of errors is that they are |
125 | /// all rooted in the automaton construction and search configurations. If |
126 | /// those configurations are a static property of your program, then it is |
127 | /// reasonable to call infallible routines since you know an error will never |
128 | /// occur. And if one _does_ occur, then it's a bug in your program. |
129 | /// |
130 | /// To re-iterate, if the patterns, build or search configuration come from |
131 | /// user or untrusted data, then you should handle errors at build or search |
132 | /// time. If only the haystack comes from user or untrusted data, then there |
133 | /// should be no need to handle errors anywhere and it is generally encouraged |
134 | /// to `unwrap()` (or `expect()`) both build and search time calls. |
135 | /// |
136 | /// # Examples |
137 | /// |
138 | /// This example shows how to search for occurrences of multiple patterns |
139 | /// simultaneously in a case insensitive fashion. Each match includes the |
140 | /// pattern that matched along with the byte offsets of the match. |
141 | /// |
142 | /// ``` |
143 | /// use aho_corasick::{AhoCorasick, PatternID}; |
144 | /// |
145 | /// let patterns = &["apple" , "maple" , "snapple" ]; |
146 | /// let haystack = "Nobody likes maple in their apple flavored Snapple." ; |
147 | /// |
148 | /// let ac = AhoCorasick::builder() |
149 | /// .ascii_case_insensitive(true) |
150 | /// .build(patterns) |
151 | /// .unwrap(); |
152 | /// let mut matches = vec![]; |
153 | /// for mat in ac.find_iter(haystack) { |
154 | /// matches.push((mat.pattern(), mat.start(), mat.end())); |
155 | /// } |
156 | /// assert_eq!(matches, vec![ |
157 | /// (PatternID::must(1), 13, 18), |
158 | /// (PatternID::must(0), 28, 33), |
159 | /// (PatternID::must(2), 43, 50), |
160 | /// ]); |
161 | /// ``` |
162 | /// |
163 | /// This example shows how to replace matches with some other string: |
164 | /// |
165 | /// ``` |
166 | /// use aho_corasick::AhoCorasick; |
167 | /// |
168 | /// let patterns = &["fox" , "brown" , "quick" ]; |
169 | /// let haystack = "The quick brown fox." ; |
170 | /// let replace_with = &["sloth" , "grey" , "slow" ]; |
171 | /// |
172 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
173 | /// let result = ac.replace_all(haystack, replace_with); |
174 | /// assert_eq!(result, "The slow grey sloth." ); |
175 | /// ``` |
176 | #[derive (Clone)] |
177 | pub struct AhoCorasick { |
178 | /// The underlying Aho-Corasick automaton. It's one of |
179 | /// nfa::noncontiguous::NFA, nfa::contiguous::NFA or dfa::DFA. |
180 | aut: Arc<dyn AcAutomaton>, |
181 | /// The specific Aho-Corasick kind chosen. This makes it possible to |
182 | /// inspect any `AhoCorasick` and know what kind of search strategy it |
183 | /// uses. |
184 | kind: AhoCorasickKind, |
185 | /// The start kind of this automaton as configured by the caller. |
186 | /// |
187 | /// We don't really *need* to put this here, since the underlying automaton |
188 | /// will correctly return errors if the caller requests an unsupported |
189 | /// search type. But we do keep this here for API behavior consistency. |
190 | /// Namely, the NFAs in this crate support both unanchored and anchored |
191 | /// searches unconditionally. There's no way to disable one or the other. |
192 | /// They always both work. But the DFA in this crate specifically only |
193 | /// supports both unanchored and anchored searches if it's configured to |
194 | /// do so. Why? Because for the DFA, supporting both essentially requires |
195 | /// two copies of the transition table: one generated by following failure |
196 | /// transitions from the original NFA and one generated by not following |
197 | /// those failure transitions. |
198 | /// |
199 | /// So why record the start kind here? Well, consider what happens |
200 | /// when no specific 'AhoCorasickKind' is selected by the caller and |
201 | /// 'StartKind::Unanchored' is used (both are the default). It *might* |
202 | /// result in using a DFA or it might pick an NFA. If it picks an NFA, the |
203 | /// caller would then be able to run anchored searches, even though the |
204 | /// caller only asked for support for unanchored searches. Maybe that's |
205 | /// fine, but what if the DFA was chosen instead? Oops, the caller would |
206 | /// get an error. |
207 | /// |
208 | /// Basically, it seems bad to return an error or not based on some |
209 | /// internal implementation choice. So we smooth things out and ensure |
210 | /// anchored searches *always* report an error when only unanchored support |
211 | /// was asked for (and vice versa), even if the underlying automaton |
212 | /// supports it. |
213 | start_kind: StartKind, |
214 | } |
215 | |
216 | /// Convenience constructors for an Aho-Corasick searcher. To configure the |
217 | /// searcher, use an [`AhoCorasickBuilder`] instead. |
218 | impl AhoCorasick { |
219 | /// Create a new Aho-Corasick automaton using the default configuration. |
220 | /// |
221 | /// The default configuration optimizes for less space usage, but at the |
222 | /// expense of longer search times. To change the configuration, use |
223 | /// [`AhoCorasickBuilder`]. |
224 | /// |
225 | /// This uses the default [`MatchKind::Standard`] match semantics, which |
226 | /// reports a match as soon as it is found. This corresponds to the |
227 | /// standard match semantics supported by textbook descriptions of the |
228 | /// Aho-Corasick algorithm. |
229 | /// |
230 | /// # Examples |
231 | /// |
232 | /// Basic usage: |
233 | /// |
234 | /// ``` |
235 | /// use aho_corasick::{AhoCorasick, PatternID}; |
236 | /// |
237 | /// let ac = AhoCorasick::new(&["foo" , "bar" , "baz" ]).unwrap(); |
238 | /// assert_eq!( |
239 | /// Some(PatternID::must(1)), |
240 | /// ac.find("xxx bar xxx" ).map(|m| m.pattern()), |
241 | /// ); |
242 | /// ``` |
243 | pub fn new<I, P>(patterns: I) -> Result<AhoCorasick, BuildError> |
244 | where |
245 | I: IntoIterator<Item = P>, |
246 | P: AsRef<[u8]>, |
247 | { |
248 | AhoCorasickBuilder::new().build(patterns) |
249 | } |
250 | |
251 | /// A convenience method for returning a new Aho-Corasick builder. |
252 | /// |
253 | /// This usually permits one to just import the `AhoCorasick` type. |
254 | /// |
255 | /// # Examples |
256 | /// |
257 | /// Basic usage: |
258 | /// |
259 | /// ``` |
260 | /// use aho_corasick::{AhoCorasick, Match, MatchKind}; |
261 | /// |
262 | /// let ac = AhoCorasick::builder() |
263 | /// .match_kind(MatchKind::LeftmostFirst) |
264 | /// .build(&["samwise" , "sam" ]) |
265 | /// .unwrap(); |
266 | /// assert_eq!(Some(Match::must(0, 0..7)), ac.find("samwise" )); |
267 | /// ``` |
268 | pub fn builder() -> AhoCorasickBuilder { |
269 | AhoCorasickBuilder::new() |
270 | } |
271 | } |
272 | |
273 | /// Infallible search routines. These APIs panic when the underlying search |
274 | /// would otherwise fail. Infallible routines are useful because the errors are |
275 | /// a result of both search-time configuration and what configuration is used |
276 | /// to build the Aho-Corasick searcher. Both of these things are not usually |
277 | /// the result of user input, and thus, an error is typically indicative of a |
278 | /// programmer error. In cases where callers want errors instead of panics, use |
279 | /// the corresponding `try` method in the section below. |
280 | impl AhoCorasick { |
281 | /// Returns true if and only if this automaton matches the haystack at any |
282 | /// position. |
283 | /// |
284 | /// `input` may be any type that is cheaply convertible to an `Input`. This |
285 | /// includes, but is not limited to, `&str` and `&[u8]`. |
286 | /// |
287 | /// Aside from convenience, when `AhoCorasick` was built with |
288 | /// leftmost-first or leftmost-longest semantics, this might result in a |
289 | /// search that visits less of the haystack than [`AhoCorasick::find`] |
290 | /// would otherwise. (For standard semantics, matches are always |
291 | /// immediately returned once they are seen, so there is no way for this to |
292 | /// do less work in that case.) |
293 | /// |
294 | /// Note that there is no corresponding fallible routine for this method. |
295 | /// If you need a fallible version of this, then [`AhoCorasick::try_find`] |
296 | /// can be used with [`Input::earliest`] enabled. |
297 | /// |
298 | /// # Examples |
299 | /// |
300 | /// Basic usage: |
301 | /// |
302 | /// ``` |
303 | /// use aho_corasick::AhoCorasick; |
304 | /// |
305 | /// let ac = AhoCorasick::new(&[ |
306 | /// "foo" , "bar" , "quux" , "baz" , |
307 | /// ]).unwrap(); |
308 | /// assert!(ac.is_match("xxx bar xxx" )); |
309 | /// assert!(!ac.is_match("xxx qux xxx" )); |
310 | /// ``` |
311 | pub fn is_match<'h, I: Into<Input<'h>>>(&self, input: I) -> bool { |
312 | self.aut |
313 | .try_find(&input.into().earliest(true)) |
314 | .expect("AhoCorasick::try_find is not expected to fail" ) |
315 | .is_some() |
316 | } |
317 | |
318 | /// Returns the location of the first match according to the match |
319 | /// semantics that this automaton was constructed with. |
320 | /// |
321 | /// `input` may be any type that is cheaply convertible to an `Input`. This |
322 | /// includes, but is not limited to, `&str` and `&[u8]`. |
323 | /// |
324 | /// This is the infallible version of [`AhoCorasick::try_find`]. |
325 | /// |
326 | /// # Panics |
327 | /// |
328 | /// This panics when [`AhoCorasick::try_find`] would return an error. |
329 | /// |
330 | /// # Examples |
331 | /// |
332 | /// Basic usage, with standard semantics: |
333 | /// |
334 | /// ``` |
335 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
336 | /// |
337 | /// let patterns = &["b" , "abc" , "abcd" ]; |
338 | /// let haystack = "abcd" ; |
339 | /// |
340 | /// let ac = AhoCorasick::builder() |
341 | /// .match_kind(MatchKind::Standard) // default, not necessary |
342 | /// .build(patterns) |
343 | /// .unwrap(); |
344 | /// let mat = ac.find(haystack).expect("should have a match" ); |
345 | /// assert_eq!("b" , &haystack[mat.start()..mat.end()]); |
346 | /// ``` |
347 | /// |
348 | /// Now with leftmost-first semantics: |
349 | /// |
350 | /// ``` |
351 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
352 | /// |
353 | /// let patterns = &["b" , "abc" , "abcd" ]; |
354 | /// let haystack = "abcd" ; |
355 | /// |
356 | /// let ac = AhoCorasick::builder() |
357 | /// .match_kind(MatchKind::LeftmostFirst) |
358 | /// .build(patterns) |
359 | /// .unwrap(); |
360 | /// let mat = ac.find(haystack).expect("should have a match" ); |
361 | /// assert_eq!("abc" , &haystack[mat.start()..mat.end()]); |
362 | /// ``` |
363 | /// |
364 | /// And finally, leftmost-longest semantics: |
365 | /// |
366 | /// ``` |
367 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
368 | /// |
369 | /// let patterns = &["b" , "abc" , "abcd" ]; |
370 | /// let haystack = "abcd" ; |
371 | /// |
372 | /// let ac = AhoCorasick::builder() |
373 | /// .match_kind(MatchKind::LeftmostLongest) |
374 | /// .build(patterns) |
375 | /// .unwrap(); |
376 | /// let mat = ac.find(haystack).expect("should have a match" ); |
377 | /// ``` |
378 | /// |
379 | /// # Example: configuring a search |
380 | /// |
381 | /// Because this method accepts anything that can be turned into an |
382 | /// [`Input`], it's possible to provide an `Input` directly in order to |
383 | /// configure the search. In this example, we show how to use the |
384 | /// `earliest` option to force the search to return as soon as it knows |
385 | /// a match has occurred. |
386 | /// |
387 | /// ``` |
388 | /// use aho_corasick::{AhoCorasick, Input, MatchKind}; |
389 | /// |
390 | /// let patterns = &["b" , "abc" , "abcd" ]; |
391 | /// let haystack = "abcd" ; |
392 | /// |
393 | /// let ac = AhoCorasick::builder() |
394 | /// .match_kind(MatchKind::LeftmostLongest) |
395 | /// .build(patterns) |
396 | /// .unwrap(); |
397 | /// let mat = ac.find(Input::new(haystack).earliest(true)) |
398 | /// .expect("should have a match" ); |
399 | /// // The correct leftmost-longest match here is 'abcd', but since we |
400 | /// // told the search to quit as soon as it knows a match has occurred, |
401 | /// // we get a different match back. |
402 | /// assert_eq!("b" , &haystack[mat.start()..mat.end()]); |
403 | /// ``` |
404 | pub fn find<'h, I: Into<Input<'h>>>(&self, input: I) -> Option<Match> { |
405 | self.try_find(input) |
406 | .expect("AhoCorasick::try_find is not expected to fail" ) |
407 | } |
408 | |
409 | /// Returns the location of the first overlapping match in the given |
410 | /// input with respect to the current state of the underlying searcher. |
411 | /// |
412 | /// `input` may be any type that is cheaply convertible to an `Input`. This |
413 | /// includes, but is not limited to, `&str` and `&[u8]`. |
414 | /// |
415 | /// Overlapping searches do not report matches in their return value. |
416 | /// Instead, matches can be accessed via [`OverlappingState::get_match`] |
417 | /// after a search call. |
418 | /// |
419 | /// This is the infallible version of |
420 | /// [`AhoCorasick::try_find_overlapping`]. |
421 | /// |
422 | /// # Panics |
423 | /// |
424 | /// This panics when [`AhoCorasick::try_find_overlapping`] would |
425 | /// return an error. For example, when the Aho-Corasick searcher |
426 | /// doesn't support overlapping searches. (Only searchers built with |
427 | /// [`MatchKind::Standard`] semantics support overlapping searches.) |
428 | /// |
429 | /// # Example |
430 | /// |
431 | /// This shows how we can repeatedly call an overlapping search without |
432 | /// ever needing to explicitly re-slice the haystack. Overlapping search |
433 | /// works this way because searches depend on state saved during the |
434 | /// previous search. |
435 | /// |
436 | /// ``` |
437 | /// use aho_corasick::{ |
438 | /// automaton::OverlappingState, |
439 | /// AhoCorasick, Input, Match, |
440 | /// }; |
441 | /// |
442 | /// let patterns = &["append" , "appendage" , "app" ]; |
443 | /// let haystack = "append the app to the appendage" ; |
444 | /// |
445 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
446 | /// let mut state = OverlappingState::start(); |
447 | /// |
448 | /// ac.find_overlapping(haystack, &mut state); |
449 | /// assert_eq!(Some(Match::must(2, 0..3)), state.get_match()); |
450 | /// |
451 | /// ac.find_overlapping(haystack, &mut state); |
452 | /// assert_eq!(Some(Match::must(0, 0..6)), state.get_match()); |
453 | /// |
454 | /// ac.find_overlapping(haystack, &mut state); |
455 | /// assert_eq!(Some(Match::must(2, 11..14)), state.get_match()); |
456 | /// |
457 | /// ac.find_overlapping(haystack, &mut state); |
458 | /// assert_eq!(Some(Match::must(2, 22..25)), state.get_match()); |
459 | /// |
460 | /// ac.find_overlapping(haystack, &mut state); |
461 | /// assert_eq!(Some(Match::must(0, 22..28)), state.get_match()); |
462 | /// |
463 | /// ac.find_overlapping(haystack, &mut state); |
464 | /// assert_eq!(Some(Match::must(1, 22..31)), state.get_match()); |
465 | /// |
466 | /// // No more match matches to be found. |
467 | /// ac.find_overlapping(haystack, &mut state); |
468 | /// assert_eq!(None, state.get_match()); |
469 | /// ``` |
470 | pub fn find_overlapping<'h, I: Into<Input<'h>>>( |
471 | &self, |
472 | input: I, |
473 | state: &mut OverlappingState, |
474 | ) { |
475 | self.try_find_overlapping(input, state).expect( |
476 | "AhoCorasick::try_find_overlapping is not expected to fail" , |
477 | ) |
478 | } |
479 | |
480 | /// Returns an iterator of non-overlapping matches, using the match |
481 | /// semantics that this automaton was constructed with. |
482 | /// |
483 | /// `input` may be any type that is cheaply convertible to an `Input`. This |
484 | /// includes, but is not limited to, `&str` and `&[u8]`. |
485 | /// |
486 | /// This is the infallible version of [`AhoCorasick::try_find_iter`]. |
487 | /// |
488 | /// # Panics |
489 | /// |
490 | /// This panics when [`AhoCorasick::try_find_iter`] would return an error. |
491 | /// |
492 | /// # Examples |
493 | /// |
494 | /// Basic usage, with standard semantics: |
495 | /// |
496 | /// ``` |
497 | /// use aho_corasick::{AhoCorasick, MatchKind, PatternID}; |
498 | /// |
499 | /// let patterns = &["append" , "appendage" , "app" ]; |
500 | /// let haystack = "append the app to the appendage" ; |
501 | /// |
502 | /// let ac = AhoCorasick::builder() |
503 | /// .match_kind(MatchKind::Standard) // default, not necessary |
504 | /// .build(patterns) |
505 | /// .unwrap(); |
506 | /// let matches: Vec<PatternID> = ac |
507 | /// .find_iter(haystack) |
508 | /// .map(|mat| mat.pattern()) |
509 | /// .collect(); |
510 | /// assert_eq!(vec![ |
511 | /// PatternID::must(2), |
512 | /// PatternID::must(2), |
513 | /// PatternID::must(2), |
514 | /// ], matches); |
515 | /// ``` |
516 | /// |
517 | /// Now with leftmost-first semantics: |
518 | /// |
519 | /// ``` |
520 | /// use aho_corasick::{AhoCorasick, MatchKind, PatternID}; |
521 | /// |
522 | /// let patterns = &["append" , "appendage" , "app" ]; |
523 | /// let haystack = "append the app to the appendage" ; |
524 | /// |
525 | /// let ac = AhoCorasick::builder() |
526 | /// .match_kind(MatchKind::LeftmostFirst) |
527 | /// .build(patterns) |
528 | /// .unwrap(); |
529 | /// let matches: Vec<PatternID> = ac |
530 | /// .find_iter(haystack) |
531 | /// .map(|mat| mat.pattern()) |
532 | /// .collect(); |
533 | /// assert_eq!(vec![ |
534 | /// PatternID::must(0), |
535 | /// PatternID::must(2), |
536 | /// PatternID::must(0), |
537 | /// ], matches); |
538 | /// ``` |
539 | /// |
540 | /// And finally, leftmost-longest semantics: |
541 | /// |
542 | /// ``` |
543 | /// use aho_corasick::{AhoCorasick, MatchKind, PatternID}; |
544 | /// |
545 | /// let patterns = &["append" , "appendage" , "app" ]; |
546 | /// let haystack = "append the app to the appendage" ; |
547 | /// |
548 | /// let ac = AhoCorasick::builder() |
549 | /// .match_kind(MatchKind::LeftmostLongest) |
550 | /// .build(patterns) |
551 | /// .unwrap(); |
552 | /// let matches: Vec<PatternID> = ac |
553 | /// .find_iter(haystack) |
554 | /// .map(|mat| mat.pattern()) |
555 | /// .collect(); |
556 | /// assert_eq!(vec![ |
557 | /// PatternID::must(0), |
558 | /// PatternID::must(2), |
559 | /// PatternID::must(1), |
560 | /// ], matches); |
561 | /// ``` |
562 | pub fn find_iter<'a, 'h, I: Into<Input<'h>>>( |
563 | &'a self, |
564 | input: I, |
565 | ) -> FindIter<'a, 'h> { |
566 | self.try_find_iter(input) |
567 | .expect("AhoCorasick::try_find_iter is not expected to fail" ) |
568 | } |
569 | |
570 | /// Returns an iterator of overlapping matches. Stated differently, this |
571 | /// returns an iterator of all possible matches at every position. |
572 | /// |
573 | /// `input` may be any type that is cheaply convertible to an `Input`. This |
574 | /// includes, but is not limited to, `&str` and `&[u8]`. |
575 | /// |
576 | /// This is the infallible version of |
577 | /// [`AhoCorasick::try_find_overlapping_iter`]. |
578 | /// |
579 | /// # Panics |
580 | /// |
581 | /// This panics when `AhoCorasick::try_find_overlapping_iter` would return |
582 | /// an error. For example, when the Aho-Corasick searcher is built with |
583 | /// either leftmost-first or leftmost-longest match semantics. Stated |
584 | /// differently, overlapping searches require one to build the searcher |
585 | /// with [`MatchKind::Standard`] (it is the default). |
586 | /// |
587 | /// # Example: basic usage |
588 | /// |
589 | /// ``` |
590 | /// use aho_corasick::{AhoCorasick, PatternID}; |
591 | /// |
592 | /// let patterns = &["append" , "appendage" , "app" ]; |
593 | /// let haystack = "append the app to the appendage" ; |
594 | /// |
595 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
596 | /// let matches: Vec<PatternID> = ac |
597 | /// .find_overlapping_iter(haystack) |
598 | /// .map(|mat| mat.pattern()) |
599 | /// .collect(); |
600 | /// assert_eq!(vec![ |
601 | /// PatternID::must(2), |
602 | /// PatternID::must(0), |
603 | /// PatternID::must(2), |
604 | /// PatternID::must(2), |
605 | /// PatternID::must(0), |
606 | /// PatternID::must(1), |
607 | /// ], matches); |
608 | /// ``` |
609 | pub fn find_overlapping_iter<'a, 'h, I: Into<Input<'h>>>( |
610 | &'a self, |
611 | input: I, |
612 | ) -> FindOverlappingIter<'a, 'h> { |
613 | self.try_find_overlapping_iter(input).expect( |
614 | "AhoCorasick::try_find_overlapping_iter is not expected to fail" , |
615 | ) |
616 | } |
617 | |
618 | /// Replace all matches with a corresponding value in the `replace_with` |
619 | /// slice given. Matches correspond to the same matches as reported by |
620 | /// [`AhoCorasick::find_iter`]. |
621 | /// |
622 | /// Replacements are determined by the index of the matching pattern. |
623 | /// For example, if the pattern with index `2` is found, then it is |
624 | /// replaced by `replace_with[2]`. |
625 | /// |
626 | /// This is the infallible version of [`AhoCorasick::try_replace_all`]. |
627 | /// |
628 | /// # Panics |
629 | /// |
630 | /// This panics when [`AhoCorasick::try_replace_all`] would return an |
631 | /// error. |
632 | /// |
633 | /// This also panics when `replace_with.len()` does not equal |
634 | /// [`AhoCorasick::patterns_len`]. |
635 | /// |
636 | /// # Example: basic usage |
637 | /// |
638 | /// ``` |
639 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
640 | /// |
641 | /// let patterns = &["append" , "appendage" , "app" ]; |
642 | /// let haystack = "append the app to the appendage" ; |
643 | /// |
644 | /// let ac = AhoCorasick::builder() |
645 | /// .match_kind(MatchKind::LeftmostFirst) |
646 | /// .build(patterns) |
647 | /// .unwrap(); |
648 | /// let result = ac.replace_all(haystack, &["x" , "y" , "z" ]); |
649 | /// assert_eq!("x the z to the xage" , result); |
650 | /// ``` |
651 | pub fn replace_all<B>(&self, haystack: &str, replace_with: &[B]) -> String |
652 | where |
653 | B: AsRef<str>, |
654 | { |
655 | self.try_replace_all(haystack, replace_with) |
656 | .expect("AhoCorasick::try_replace_all is not expected to fail" ) |
657 | } |
658 | |
659 | /// Replace all matches using raw bytes with a corresponding value in the |
660 | /// `replace_with` slice given. Matches correspond to the same matches as |
661 | /// reported by [`AhoCorasick::find_iter`]. |
662 | /// |
663 | /// Replacements are determined by the index of the matching pattern. |
664 | /// For example, if the pattern with index `2` is found, then it is |
665 | /// replaced by `replace_with[2]`. |
666 | /// |
667 | /// This is the infallible version of |
668 | /// [`AhoCorasick::try_replace_all_bytes`]. |
669 | /// |
670 | /// # Panics |
671 | /// |
672 | /// This panics when [`AhoCorasick::try_replace_all_bytes`] would return an |
673 | /// error. |
674 | /// |
675 | /// This also panics when `replace_with.len()` does not equal |
676 | /// [`AhoCorasick::patterns_len`]. |
677 | /// |
678 | /// # Example: basic usage |
679 | /// |
680 | /// ``` |
681 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
682 | /// |
683 | /// let patterns = &["append" , "appendage" , "app" ]; |
684 | /// let haystack = b"append the app to the appendage" ; |
685 | /// |
686 | /// let ac = AhoCorasick::builder() |
687 | /// .match_kind(MatchKind::LeftmostFirst) |
688 | /// .build(patterns) |
689 | /// .unwrap(); |
690 | /// let result = ac.replace_all_bytes(haystack, &["x" , "y" , "z" ]); |
691 | /// assert_eq!(b"x the z to the xage" .to_vec(), result); |
692 | /// ``` |
693 | pub fn replace_all_bytes<B>( |
694 | &self, |
695 | haystack: &[u8], |
696 | replace_with: &[B], |
697 | ) -> Vec<u8> |
698 | where |
699 | B: AsRef<[u8]>, |
700 | { |
701 | self.try_replace_all_bytes(haystack, replace_with) |
702 | .expect("AhoCorasick::try_replace_all_bytes should not fail" ) |
703 | } |
704 | |
705 | /// Replace all matches using a closure called on each match. |
706 | /// Matches correspond to the same matches as reported by |
707 | /// [`AhoCorasick::find_iter`]. |
708 | /// |
709 | /// The closure accepts three parameters: the match found, the text of |
710 | /// the match and a string buffer with which to write the replaced text |
711 | /// (if any). If the closure returns `true`, then it continues to the next |
712 | /// match. If the closure returns `false`, then searching is stopped. |
713 | /// |
714 | /// Note that any matches with boundaries that don't fall on a valid UTF-8 |
715 | /// boundary are silently skipped. |
716 | /// |
717 | /// This is the infallible version of |
718 | /// [`AhoCorasick::try_replace_all_with`]. |
719 | /// |
720 | /// # Panics |
721 | /// |
722 | /// This panics when [`AhoCorasick::try_replace_all_with`] would return an |
723 | /// error. |
724 | /// |
725 | /// # Examples |
726 | /// |
727 | /// Basic usage: |
728 | /// |
729 | /// ``` |
730 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
731 | /// |
732 | /// let patterns = &["append" , "appendage" , "app" ]; |
733 | /// let haystack = "append the app to the appendage" ; |
734 | /// |
735 | /// let ac = AhoCorasick::builder() |
736 | /// .match_kind(MatchKind::LeftmostFirst) |
737 | /// .build(patterns) |
738 | /// .unwrap(); |
739 | /// let mut result = String::new(); |
740 | /// ac.replace_all_with(haystack, &mut result, |mat, _, dst| { |
741 | /// dst.push_str(&mat.pattern().as_usize().to_string()); |
742 | /// true |
743 | /// }); |
744 | /// assert_eq!("0 the 2 to the 0age" , result); |
745 | /// ``` |
746 | /// |
747 | /// Stopping the replacement by returning `false` (continued from the |
748 | /// example above): |
749 | /// |
750 | /// ``` |
751 | /// # use aho_corasick::{AhoCorasick, MatchKind, PatternID}; |
752 | /// # let patterns = &["append" , "appendage" , "app" ]; |
753 | /// # let haystack = "append the app to the appendage" ; |
754 | /// # let ac = AhoCorasick::builder() |
755 | /// # .match_kind(MatchKind::LeftmostFirst) |
756 | /// # .build(patterns) |
757 | /// # .unwrap(); |
758 | /// let mut result = String::new(); |
759 | /// ac.replace_all_with(haystack, &mut result, |mat, _, dst| { |
760 | /// dst.push_str(&mat.pattern().as_usize().to_string()); |
761 | /// mat.pattern() != PatternID::must(2) |
762 | /// }); |
763 | /// assert_eq!("0 the 2 to the appendage" , result); |
764 | /// ``` |
765 | pub fn replace_all_with<F>( |
766 | &self, |
767 | haystack: &str, |
768 | dst: &mut String, |
769 | replace_with: F, |
770 | ) where |
771 | F: FnMut(&Match, &str, &mut String) -> bool, |
772 | { |
773 | self.try_replace_all_with(haystack, dst, replace_with) |
774 | .expect("AhoCorasick::try_replace_all_with should not fail" ) |
775 | } |
776 | |
777 | /// Replace all matches using raw bytes with a closure called on each |
778 | /// match. Matches correspond to the same matches as reported by |
779 | /// [`AhoCorasick::find_iter`]. |
780 | /// |
781 | /// The closure accepts three parameters: the match found, the text of |
782 | /// the match and a byte buffer with which to write the replaced text |
783 | /// (if any). If the closure returns `true`, then it continues to the next |
784 | /// match. If the closure returns `false`, then searching is stopped. |
785 | /// |
786 | /// This is the infallible version of |
787 | /// [`AhoCorasick::try_replace_all_with_bytes`]. |
788 | /// |
789 | /// # Panics |
790 | /// |
791 | /// This panics when [`AhoCorasick::try_replace_all_with_bytes`] would |
792 | /// return an error. |
793 | /// |
794 | /// # Examples |
795 | /// |
796 | /// Basic usage: |
797 | /// |
798 | /// ``` |
799 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
800 | /// |
801 | /// let patterns = &["append" , "appendage" , "app" ]; |
802 | /// let haystack = b"append the app to the appendage" ; |
803 | /// |
804 | /// let ac = AhoCorasick::builder() |
805 | /// .match_kind(MatchKind::LeftmostFirst) |
806 | /// .build(patterns) |
807 | /// .unwrap(); |
808 | /// let mut result = vec![]; |
809 | /// ac.replace_all_with_bytes(haystack, &mut result, |mat, _, dst| { |
810 | /// dst.extend(mat.pattern().as_usize().to_string().bytes()); |
811 | /// true |
812 | /// }); |
813 | /// assert_eq!(b"0 the 2 to the 0age" .to_vec(), result); |
814 | /// ``` |
815 | /// |
816 | /// Stopping the replacement by returning `false` (continued from the |
817 | /// example above): |
818 | /// |
819 | /// ``` |
820 | /// # use aho_corasick::{AhoCorasick, MatchKind, PatternID}; |
821 | /// # let patterns = &["append" , "appendage" , "app" ]; |
822 | /// # let haystack = b"append the app to the appendage" ; |
823 | /// # let ac = AhoCorasick::builder() |
824 | /// # .match_kind(MatchKind::LeftmostFirst) |
825 | /// # .build(patterns) |
826 | /// # .unwrap(); |
827 | /// let mut result = vec![]; |
828 | /// ac.replace_all_with_bytes(haystack, &mut result, |mat, _, dst| { |
829 | /// dst.extend(mat.pattern().as_usize().to_string().bytes()); |
830 | /// mat.pattern() != PatternID::must(2) |
831 | /// }); |
832 | /// assert_eq!(b"0 the 2 to the appendage" .to_vec(), result); |
833 | /// ``` |
834 | pub fn replace_all_with_bytes<F>( |
835 | &self, |
836 | haystack: &[u8], |
837 | dst: &mut Vec<u8>, |
838 | replace_with: F, |
839 | ) where |
840 | F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool, |
841 | { |
842 | self.try_replace_all_with_bytes(haystack, dst, replace_with) |
843 | .expect("AhoCorasick::try_replace_all_with_bytes should not fail" ) |
844 | } |
845 | |
846 | /// Returns an iterator of non-overlapping matches in the given |
847 | /// stream. Matches correspond to the same matches as reported by |
848 | /// [`AhoCorasick::find_iter`]. |
849 | /// |
850 | /// The matches yielded by this iterator use absolute position offsets in |
851 | /// the stream given, where the first byte has index `0`. Matches are |
852 | /// yieled until the stream is exhausted. |
853 | /// |
854 | /// Each item yielded by the iterator is an `Result<Match, |
855 | /// std::io::Error>`, where an error is yielded if there was a problem |
856 | /// reading from the reader given. |
857 | /// |
858 | /// When searching a stream, an internal buffer is used. Therefore, callers |
859 | /// should avoiding providing a buffered reader, if possible. |
860 | /// |
861 | /// This is the infallible version of |
862 | /// [`AhoCorasick::try_stream_find_iter`]. Note that both methods return |
863 | /// iterators that produce `Result` values. The difference is that this |
864 | /// routine panics if _construction_ of the iterator failed. The `Result` |
865 | /// values yield by the iterator come from whether the given reader returns |
866 | /// an error or not during the search. |
867 | /// |
868 | /// # Memory usage |
869 | /// |
870 | /// In general, searching streams will use a constant amount of memory for |
871 | /// its internal buffer. The one requirement is that the internal buffer |
872 | /// must be at least the size of the longest possible match. In most use |
873 | /// cases, the default buffer size will be much larger than any individual |
874 | /// match. |
875 | /// |
876 | /// # Panics |
877 | /// |
878 | /// This panics when [`AhoCorasick::try_stream_find_iter`] would return |
879 | /// an error. For example, when the Aho-Corasick searcher doesn't support |
880 | /// stream searches. (Only searchers built with [`MatchKind::Standard`] |
881 | /// semantics support stream searches.) |
882 | /// |
883 | /// # Example: basic usage |
884 | /// |
885 | /// ``` |
886 | /// use aho_corasick::{AhoCorasick, PatternID}; |
887 | /// |
888 | /// let patterns = &["append" , "appendage" , "app" ]; |
889 | /// let haystack = "append the app to the appendage" ; |
890 | /// |
891 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
892 | /// let mut matches = vec![]; |
893 | /// for result in ac.stream_find_iter(haystack.as_bytes()) { |
894 | /// let mat = result?; |
895 | /// matches.push(mat.pattern()); |
896 | /// } |
897 | /// assert_eq!(vec![ |
898 | /// PatternID::must(2), |
899 | /// PatternID::must(2), |
900 | /// PatternID::must(2), |
901 | /// ], matches); |
902 | /// |
903 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
904 | /// ``` |
905 | #[cfg (feature = "std" )] |
906 | pub fn stream_find_iter<'a, R: std::io::Read>( |
907 | &'a self, |
908 | rdr: R, |
909 | ) -> StreamFindIter<'a, R> { |
910 | self.try_stream_find_iter(rdr) |
911 | .expect("AhoCorasick::try_stream_find_iter should not fail" ) |
912 | } |
913 | } |
914 | |
915 | /// Fallible search routines. These APIs return an error in cases where the |
916 | /// infallible routines would panic. |
917 | impl AhoCorasick { |
918 | /// Returns the location of the first match according to the match |
919 | /// semantics that this automaton was constructed with, and according |
920 | /// to the given `Input` configuration. |
921 | /// |
922 | /// This is the fallible version of [`AhoCorasick::find`]. |
923 | /// |
924 | /// # Errors |
925 | /// |
926 | /// This returns an error when this Aho-Corasick searcher does not support |
927 | /// the given `Input` configuration. |
928 | /// |
929 | /// For example, if the Aho-Corasick searcher only supports anchored |
930 | /// searches or only supports unanchored searches, then providing an |
931 | /// `Input` that requests an anchored (or unanchored) search when it isn't |
932 | /// supported would result in an error. |
933 | /// |
934 | /// # Example: leftmost-first searching |
935 | /// |
936 | /// Basic usage with leftmost-first semantics: |
937 | /// |
938 | /// ``` |
939 | /// use aho_corasick::{AhoCorasick, MatchKind, Input}; |
940 | /// |
941 | /// let patterns = &["b" , "abc" , "abcd" ]; |
942 | /// let haystack = "foo abcd" ; |
943 | /// |
944 | /// let ac = AhoCorasick::builder() |
945 | /// .match_kind(MatchKind::LeftmostFirst) |
946 | /// .build(patterns) |
947 | /// .unwrap(); |
948 | /// let mat = ac.try_find(haystack)?.expect("should have a match" ); |
949 | /// assert_eq!("abc" , &haystack[mat.span()]); |
950 | /// |
951 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
952 | /// ``` |
953 | /// |
954 | /// # Example: anchored leftmost-first searching |
955 | /// |
956 | /// This shows how to anchor the search, so that even if the haystack |
957 | /// contains a match somewhere, a match won't be reported unless one can |
958 | /// be found that starts at the beginning of the search: |
959 | /// |
960 | /// ``` |
961 | /// use aho_corasick::{AhoCorasick, Anchored, Input, MatchKind, StartKind}; |
962 | /// |
963 | /// let patterns = &["b" , "abc" , "abcd" ]; |
964 | /// let haystack = "foo abcd" ; |
965 | /// |
966 | /// let ac = AhoCorasick::builder() |
967 | /// .match_kind(MatchKind::LeftmostFirst) |
968 | /// .start_kind(StartKind::Anchored) |
969 | /// .build(patterns) |
970 | /// .unwrap(); |
971 | /// let input = Input::new(haystack).anchored(Anchored::Yes); |
972 | /// assert_eq!(None, ac.try_find(input)?); |
973 | /// |
974 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
975 | /// ``` |
976 | /// |
977 | /// If the beginning of the search is changed to where a match begins, then |
978 | /// it will be found: |
979 | /// |
980 | /// ``` |
981 | /// use aho_corasick::{AhoCorasick, Anchored, Input, MatchKind, StartKind}; |
982 | /// |
983 | /// let patterns = &["b" , "abc" , "abcd" ]; |
984 | /// let haystack = "foo abcd" ; |
985 | /// |
986 | /// let ac = AhoCorasick::builder() |
987 | /// .match_kind(MatchKind::LeftmostFirst) |
988 | /// .start_kind(StartKind::Anchored) |
989 | /// .build(patterns) |
990 | /// .unwrap(); |
991 | /// let input = Input::new(haystack).range(4..).anchored(Anchored::Yes); |
992 | /// let mat = ac.try_find(input)?.expect("should have a match" ); |
993 | /// assert_eq!("abc" , &haystack[mat.span()]); |
994 | /// |
995 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
996 | /// ``` |
997 | /// |
998 | /// # Example: earliest leftmost-first searching |
999 | /// |
1000 | /// This shows how to run an "earliest" search even when the Aho-Corasick |
1001 | /// searcher was compiled with leftmost-first match semantics. In this |
1002 | /// case, the search is stopped as soon as it is known that a match has |
1003 | /// occurred, even if it doesn't correspond to the leftmost-first match. |
1004 | /// |
1005 | /// ``` |
1006 | /// use aho_corasick::{AhoCorasick, Input, MatchKind}; |
1007 | /// |
1008 | /// let patterns = &["b" , "abc" , "abcd" ]; |
1009 | /// let haystack = "foo abcd" ; |
1010 | /// |
1011 | /// let ac = AhoCorasick::builder() |
1012 | /// .match_kind(MatchKind::LeftmostFirst) |
1013 | /// .build(patterns) |
1014 | /// .unwrap(); |
1015 | /// let input = Input::new(haystack).earliest(true); |
1016 | /// let mat = ac.try_find(input)?.expect("should have a match" ); |
1017 | /// assert_eq!("b" , &haystack[mat.span()]); |
1018 | /// |
1019 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1020 | /// ``` |
1021 | pub fn try_find<'h, I: Into<Input<'h>>>( |
1022 | &self, |
1023 | input: I, |
1024 | ) -> Result<Option<Match>, MatchError> { |
1025 | let input = input.into(); |
1026 | enforce_anchored_consistency(self.start_kind, input.get_anchored())?; |
1027 | self.aut.try_find(&input) |
1028 | } |
1029 | |
1030 | /// Returns the location of the first overlapping match in the given |
1031 | /// input with respect to the current state of the underlying searcher. |
1032 | /// |
1033 | /// Overlapping searches do not report matches in their return value. |
1034 | /// Instead, matches can be accessed via [`OverlappingState::get_match`] |
1035 | /// after a search call. |
1036 | /// |
1037 | /// This is the fallible version of [`AhoCorasick::find_overlapping`]. |
1038 | /// |
1039 | /// # Errors |
1040 | /// |
1041 | /// This returns an error when this Aho-Corasick searcher does not support |
1042 | /// the given `Input` configuration or if overlapping search is not |
1043 | /// supported. |
1044 | /// |
1045 | /// One example is that only Aho-Corasicker searchers built with |
1046 | /// [`MatchKind::Standard`] semantics support overlapping searches. Using |
1047 | /// any other match semantics will result in this returning an error. |
1048 | /// |
1049 | /// # Example: basic usage |
1050 | /// |
1051 | /// This shows how we can repeatedly call an overlapping search without |
1052 | /// ever needing to explicitly re-slice the haystack. Overlapping search |
1053 | /// works this way because searches depend on state saved during the |
1054 | /// previous search. |
1055 | /// |
1056 | /// ``` |
1057 | /// use aho_corasick::{ |
1058 | /// automaton::OverlappingState, |
1059 | /// AhoCorasick, Input, Match, |
1060 | /// }; |
1061 | /// |
1062 | /// let patterns = &["append" , "appendage" , "app" ]; |
1063 | /// let haystack = "append the app to the appendage" ; |
1064 | /// |
1065 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
1066 | /// let mut state = OverlappingState::start(); |
1067 | /// |
1068 | /// ac.try_find_overlapping(haystack, &mut state)?; |
1069 | /// assert_eq!(Some(Match::must(2, 0..3)), state.get_match()); |
1070 | /// |
1071 | /// ac.try_find_overlapping(haystack, &mut state)?; |
1072 | /// assert_eq!(Some(Match::must(0, 0..6)), state.get_match()); |
1073 | /// |
1074 | /// ac.try_find_overlapping(haystack, &mut state)?; |
1075 | /// assert_eq!(Some(Match::must(2, 11..14)), state.get_match()); |
1076 | /// |
1077 | /// ac.try_find_overlapping(haystack, &mut state)?; |
1078 | /// assert_eq!(Some(Match::must(2, 22..25)), state.get_match()); |
1079 | /// |
1080 | /// ac.try_find_overlapping(haystack, &mut state)?; |
1081 | /// assert_eq!(Some(Match::must(0, 22..28)), state.get_match()); |
1082 | /// |
1083 | /// ac.try_find_overlapping(haystack, &mut state)?; |
1084 | /// assert_eq!(Some(Match::must(1, 22..31)), state.get_match()); |
1085 | /// |
1086 | /// // No more match matches to be found. |
1087 | /// ac.try_find_overlapping(haystack, &mut state)?; |
1088 | /// assert_eq!(None, state.get_match()); |
1089 | /// |
1090 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1091 | /// ``` |
1092 | /// |
1093 | /// # Example: implementing your own overlapping iteration |
1094 | /// |
1095 | /// The previous example can be easily adapted to implement your own |
1096 | /// iteration by repeatedly calling `try_find_overlapping` until either |
1097 | /// an error occurs or no more matches are reported. |
1098 | /// |
1099 | /// This is effectively equivalent to the iterator returned by |
1100 | /// [`AhoCorasick::try_find_overlapping_iter`], with the only difference |
1101 | /// being that the iterator checks for errors before construction and |
1102 | /// absolves the caller of needing to check for errors on every search |
1103 | /// call. (Indeed, if the first `try_find_overlapping` call succeeds and |
1104 | /// the same `Input` is given to subsequent calls, then all subsequent |
1105 | /// calls are guaranteed to succeed.) |
1106 | /// |
1107 | /// ``` |
1108 | /// use aho_corasick::{ |
1109 | /// automaton::OverlappingState, |
1110 | /// AhoCorasick, Input, Match, |
1111 | /// }; |
1112 | /// |
1113 | /// let patterns = &["append" , "appendage" , "app" ]; |
1114 | /// let haystack = "append the app to the appendage" ; |
1115 | /// |
1116 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
1117 | /// let mut state = OverlappingState::start(); |
1118 | /// let mut matches = vec![]; |
1119 | /// |
1120 | /// loop { |
1121 | /// ac.try_find_overlapping(haystack, &mut state)?; |
1122 | /// let mat = match state.get_match() { |
1123 | /// None => break, |
1124 | /// Some(mat) => mat, |
1125 | /// }; |
1126 | /// matches.push(mat); |
1127 | /// } |
1128 | /// let expected = vec![ |
1129 | /// Match::must(2, 0..3), |
1130 | /// Match::must(0, 0..6), |
1131 | /// Match::must(2, 11..14), |
1132 | /// Match::must(2, 22..25), |
1133 | /// Match::must(0, 22..28), |
1134 | /// Match::must(1, 22..31), |
1135 | /// ]; |
1136 | /// assert_eq!(expected, matches); |
1137 | /// |
1138 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1139 | /// ``` |
1140 | /// |
1141 | /// # Example: anchored iteration |
1142 | /// |
1143 | /// The previous example can also be adapted to implement |
1144 | /// iteration over all anchored matches. In particular, |
1145 | /// [`AhoCorasick::try_find_overlapping_iter`] does not support this |
1146 | /// because it isn't totally clear what the match semantics ought to be. |
1147 | /// |
1148 | /// In this example, we will find all overlapping matches that start at |
1149 | /// the beginning of our search. |
1150 | /// |
1151 | /// ``` |
1152 | /// use aho_corasick::{ |
1153 | /// automaton::OverlappingState, |
1154 | /// AhoCorasick, Anchored, Input, Match, StartKind, |
1155 | /// }; |
1156 | /// |
1157 | /// let patterns = &["append" , "appendage" , "app" ]; |
1158 | /// let haystack = "append the app to the appendage" ; |
1159 | /// |
1160 | /// let ac = AhoCorasick::builder() |
1161 | /// .start_kind(StartKind::Anchored) |
1162 | /// .build(patterns) |
1163 | /// .unwrap(); |
1164 | /// let input = Input::new(haystack).anchored(Anchored::Yes); |
1165 | /// let mut state = OverlappingState::start(); |
1166 | /// let mut matches = vec![]; |
1167 | /// |
1168 | /// loop { |
1169 | /// ac.try_find_overlapping(input.clone(), &mut state)?; |
1170 | /// let mat = match state.get_match() { |
1171 | /// None => break, |
1172 | /// Some(mat) => mat, |
1173 | /// }; |
1174 | /// matches.push(mat); |
1175 | /// } |
1176 | /// let expected = vec![ |
1177 | /// Match::must(2, 0..3), |
1178 | /// Match::must(0, 0..6), |
1179 | /// ]; |
1180 | /// assert_eq!(expected, matches); |
1181 | /// |
1182 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1183 | /// ``` |
1184 | pub fn try_find_overlapping<'h, I: Into<Input<'h>>>( |
1185 | &self, |
1186 | input: I, |
1187 | state: &mut OverlappingState, |
1188 | ) -> Result<(), MatchError> { |
1189 | let input = input.into(); |
1190 | enforce_anchored_consistency(self.start_kind, input.get_anchored())?; |
1191 | self.aut.try_find_overlapping(&input, state) |
1192 | } |
1193 | |
1194 | /// Returns an iterator of non-overlapping matches, using the match |
1195 | /// semantics that this automaton was constructed with. |
1196 | /// |
1197 | /// This is the fallible version of [`AhoCorasick::find_iter`]. |
1198 | /// |
1199 | /// Note that the error returned by this method occurs during construction |
1200 | /// of the iterator. The iterator itself yields `Match` values. That is, |
1201 | /// once the iterator is constructed, the iteration itself will never |
1202 | /// report an error. |
1203 | /// |
1204 | /// # Errors |
1205 | /// |
1206 | /// This returns an error when this Aho-Corasick searcher does not support |
1207 | /// the given `Input` configuration. |
1208 | /// |
1209 | /// For example, if the Aho-Corasick searcher only supports anchored |
1210 | /// searches or only supports unanchored searches, then providing an |
1211 | /// `Input` that requests an anchored (or unanchored) search when it isn't |
1212 | /// supported would result in an error. |
1213 | /// |
1214 | /// # Example: leftmost-first searching |
1215 | /// |
1216 | /// Basic usage with leftmost-first semantics: |
1217 | /// |
1218 | /// ``` |
1219 | /// use aho_corasick::{AhoCorasick, Input, MatchKind, PatternID}; |
1220 | /// |
1221 | /// let patterns = &["append" , "appendage" , "app" ]; |
1222 | /// let haystack = "append the app to the appendage" ; |
1223 | /// |
1224 | /// let ac = AhoCorasick::builder() |
1225 | /// .match_kind(MatchKind::LeftmostFirst) |
1226 | /// .build(patterns) |
1227 | /// .unwrap(); |
1228 | /// let matches: Vec<PatternID> = ac |
1229 | /// .try_find_iter(Input::new(haystack))? |
1230 | /// .map(|mat| mat.pattern()) |
1231 | /// .collect(); |
1232 | /// assert_eq!(vec![ |
1233 | /// PatternID::must(0), |
1234 | /// PatternID::must(2), |
1235 | /// PatternID::must(0), |
1236 | /// ], matches); |
1237 | /// |
1238 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1239 | /// ``` |
1240 | /// |
1241 | /// # Example: anchored leftmost-first searching |
1242 | /// |
1243 | /// This shows how to anchor the search, such that all matches must begin |
1244 | /// at the starting location of the search. For an iterator, an anchored |
1245 | /// search implies that all matches are adjacent. |
1246 | /// |
1247 | /// ``` |
1248 | /// use aho_corasick::{ |
1249 | /// AhoCorasick, Anchored, Input, MatchKind, PatternID, StartKind, |
1250 | /// }; |
1251 | /// |
1252 | /// let patterns = &["foo" , "bar" , "quux" ]; |
1253 | /// let haystack = "fooquuxbar foo" ; |
1254 | /// |
1255 | /// let ac = AhoCorasick::builder() |
1256 | /// .match_kind(MatchKind::LeftmostFirst) |
1257 | /// .start_kind(StartKind::Anchored) |
1258 | /// .build(patterns) |
1259 | /// .unwrap(); |
1260 | /// let matches: Vec<PatternID> = ac |
1261 | /// .try_find_iter(Input::new(haystack).anchored(Anchored::Yes))? |
1262 | /// .map(|mat| mat.pattern()) |
1263 | /// .collect(); |
1264 | /// assert_eq!(vec![ |
1265 | /// PatternID::must(0), |
1266 | /// PatternID::must(2), |
1267 | /// PatternID::must(1), |
1268 | /// // The final 'foo' is not found because it is not adjacent to the |
1269 | /// // 'bar' match. It needs to be adjacent because our search is |
1270 | /// // anchored. |
1271 | /// ], matches); |
1272 | /// |
1273 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1274 | /// ``` |
1275 | pub fn try_find_iter<'a, 'h, I: Into<Input<'h>>>( |
1276 | &'a self, |
1277 | input: I, |
1278 | ) -> Result<FindIter<'a, 'h>, MatchError> { |
1279 | let input = input.into(); |
1280 | enforce_anchored_consistency(self.start_kind, input.get_anchored())?; |
1281 | Ok(FindIter(self.aut.try_find_iter(input)?)) |
1282 | } |
1283 | |
1284 | /// Returns an iterator of overlapping matches. |
1285 | /// |
1286 | /// This is the fallible version of [`AhoCorasick::find_overlapping_iter`]. |
1287 | /// |
1288 | /// Note that the error returned by this method occurs during construction |
1289 | /// of the iterator. The iterator itself yields `Match` values. That is, |
1290 | /// once the iterator is constructed, the iteration itself will never |
1291 | /// report an error. |
1292 | /// |
1293 | /// # Errors |
1294 | /// |
1295 | /// This returns an error when this Aho-Corasick searcher does not support |
1296 | /// the given `Input` configuration or does not support overlapping |
1297 | /// searches. |
1298 | /// |
1299 | /// One example is that only Aho-Corasicker searchers built with |
1300 | /// [`MatchKind::Standard`] semantics support overlapping searches. Using |
1301 | /// any other match semantics will result in this returning an error. |
1302 | /// |
1303 | /// # Example: basic usage |
1304 | /// |
1305 | /// ``` |
1306 | /// use aho_corasick::{AhoCorasick, Input, PatternID}; |
1307 | /// |
1308 | /// let patterns = &["append" , "appendage" , "app" ]; |
1309 | /// let haystack = "append the app to the appendage" ; |
1310 | /// |
1311 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
1312 | /// let matches: Vec<PatternID> = ac |
1313 | /// .try_find_overlapping_iter(Input::new(haystack))? |
1314 | /// .map(|mat| mat.pattern()) |
1315 | /// .collect(); |
1316 | /// assert_eq!(vec![ |
1317 | /// PatternID::must(2), |
1318 | /// PatternID::must(0), |
1319 | /// PatternID::must(2), |
1320 | /// PatternID::must(2), |
1321 | /// PatternID::must(0), |
1322 | /// PatternID::must(1), |
1323 | /// ], matches); |
1324 | /// |
1325 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1326 | /// ``` |
1327 | /// |
1328 | /// # Example: anchored overlapping search returns an error |
1329 | /// |
1330 | /// It isn't clear what the match semantics for anchored overlapping |
1331 | /// iterators *ought* to be, so currently an error is returned. Callers |
1332 | /// may use [`AhoCorasick::try_find_overlapping`] to implement their own |
1333 | /// semantics if desired. |
1334 | /// |
1335 | /// ``` |
1336 | /// use aho_corasick::{AhoCorasick, Anchored, Input, StartKind}; |
1337 | /// |
1338 | /// let patterns = &["append" , "appendage" , "app" ]; |
1339 | /// let haystack = "appendappendage app" ; |
1340 | /// |
1341 | /// let ac = AhoCorasick::builder() |
1342 | /// .start_kind(StartKind::Anchored) |
1343 | /// .build(patterns) |
1344 | /// .unwrap(); |
1345 | /// let input = Input::new(haystack).anchored(Anchored::Yes); |
1346 | /// assert!(ac.try_find_overlapping_iter(input).is_err()); |
1347 | /// |
1348 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1349 | /// ``` |
1350 | pub fn try_find_overlapping_iter<'a, 'h, I: Into<Input<'h>>>( |
1351 | &'a self, |
1352 | input: I, |
1353 | ) -> Result<FindOverlappingIter<'a, 'h>, MatchError> { |
1354 | let input = input.into(); |
1355 | enforce_anchored_consistency(self.start_kind, input.get_anchored())?; |
1356 | Ok(FindOverlappingIter(self.aut.try_find_overlapping_iter(input)?)) |
1357 | } |
1358 | |
1359 | /// Replace all matches with a corresponding value in the `replace_with` |
1360 | /// slice given. Matches correspond to the same matches as reported by |
1361 | /// [`AhoCorasick::try_find_iter`]. |
1362 | /// |
1363 | /// Replacements are determined by the index of the matching pattern. |
1364 | /// For example, if the pattern with index `2` is found, then it is |
1365 | /// replaced by `replace_with[2]`. |
1366 | /// |
1367 | /// # Panics |
1368 | /// |
1369 | /// This panics when `replace_with.len()` does not equal |
1370 | /// [`AhoCorasick::patterns_len`]. |
1371 | /// |
1372 | /// # Errors |
1373 | /// |
1374 | /// This returns an error when this Aho-Corasick searcher does not support |
1375 | /// the default `Input` configuration. More specifically, this occurs only |
1376 | /// when the Aho-Corasick searcher does not support unanchored searches |
1377 | /// since this replacement routine always does an unanchored search. |
1378 | /// |
1379 | /// # Example: basic usage |
1380 | /// |
1381 | /// ``` |
1382 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
1383 | /// |
1384 | /// let patterns = &["append" , "appendage" , "app" ]; |
1385 | /// let haystack = "append the app to the appendage" ; |
1386 | /// |
1387 | /// let ac = AhoCorasick::builder() |
1388 | /// .match_kind(MatchKind::LeftmostFirst) |
1389 | /// .build(patterns) |
1390 | /// .unwrap(); |
1391 | /// let result = ac.try_replace_all(haystack, &["x" , "y" , "z" ])?; |
1392 | /// assert_eq!("x the z to the xage" , result); |
1393 | /// |
1394 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1395 | /// ``` |
1396 | pub fn try_replace_all<B>( |
1397 | &self, |
1398 | haystack: &str, |
1399 | replace_with: &[B], |
1400 | ) -> Result<String, MatchError> |
1401 | where |
1402 | B: AsRef<str>, |
1403 | { |
1404 | enforce_anchored_consistency(self.start_kind, Anchored::No)?; |
1405 | self.aut.try_replace_all(haystack, replace_with) |
1406 | } |
1407 | |
1408 | /// Replace all matches using raw bytes with a corresponding value in the |
1409 | /// `replace_with` slice given. Matches correspond to the same matches as |
1410 | /// reported by [`AhoCorasick::try_find_iter`]. |
1411 | /// |
1412 | /// Replacements are determined by the index of the matching pattern. |
1413 | /// For example, if the pattern with index `2` is found, then it is |
1414 | /// replaced by `replace_with[2]`. |
1415 | /// |
1416 | /// This is the fallible version of [`AhoCorasick::replace_all_bytes`]. |
1417 | /// |
1418 | /// # Panics |
1419 | /// |
1420 | /// This panics when `replace_with.len()` does not equal |
1421 | /// [`AhoCorasick::patterns_len`]. |
1422 | /// |
1423 | /// # Errors |
1424 | /// |
1425 | /// This returns an error when this Aho-Corasick searcher does not support |
1426 | /// the default `Input` configuration. More specifically, this occurs only |
1427 | /// when the Aho-Corasick searcher does not support unanchored searches |
1428 | /// since this replacement routine always does an unanchored search. |
1429 | /// |
1430 | /// # Example: basic usage |
1431 | /// |
1432 | /// ``` |
1433 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
1434 | /// |
1435 | /// let patterns = &["append" , "appendage" , "app" ]; |
1436 | /// let haystack = b"append the app to the appendage" ; |
1437 | /// |
1438 | /// let ac = AhoCorasick::builder() |
1439 | /// .match_kind(MatchKind::LeftmostFirst) |
1440 | /// .build(patterns) |
1441 | /// .unwrap(); |
1442 | /// let result = ac.try_replace_all_bytes(haystack, &["x" , "y" , "z" ])?; |
1443 | /// assert_eq!(b"x the z to the xage" .to_vec(), result); |
1444 | /// |
1445 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1446 | /// ``` |
1447 | pub fn try_replace_all_bytes<B>( |
1448 | &self, |
1449 | haystack: &[u8], |
1450 | replace_with: &[B], |
1451 | ) -> Result<Vec<u8>, MatchError> |
1452 | where |
1453 | B: AsRef<[u8]>, |
1454 | { |
1455 | enforce_anchored_consistency(self.start_kind, Anchored::No)?; |
1456 | self.aut.try_replace_all_bytes(haystack, replace_with) |
1457 | } |
1458 | |
1459 | /// Replace all matches using a closure called on each match. |
1460 | /// Matches correspond to the same matches as reported by |
1461 | /// [`AhoCorasick::try_find_iter`]. |
1462 | /// |
1463 | /// The closure accepts three parameters: the match found, the text of |
1464 | /// the match and a string buffer with which to write the replaced text |
1465 | /// (if any). If the closure returns `true`, then it continues to the next |
1466 | /// match. If the closure returns `false`, then searching is stopped. |
1467 | /// |
1468 | /// Note that any matches with boundaries that don't fall on a valid UTF-8 |
1469 | /// boundary are silently skipped. |
1470 | /// |
1471 | /// This is the fallible version of [`AhoCorasick::replace_all_with`]. |
1472 | /// |
1473 | /// # Errors |
1474 | /// |
1475 | /// This returns an error when this Aho-Corasick searcher does not support |
1476 | /// the default `Input` configuration. More specifically, this occurs only |
1477 | /// when the Aho-Corasick searcher does not support unanchored searches |
1478 | /// since this replacement routine always does an unanchored search. |
1479 | /// |
1480 | /// # Examples |
1481 | /// |
1482 | /// Basic usage: |
1483 | /// |
1484 | /// ``` |
1485 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
1486 | /// |
1487 | /// let patterns = &["append" , "appendage" , "app" ]; |
1488 | /// let haystack = "append the app to the appendage" ; |
1489 | /// |
1490 | /// let ac = AhoCorasick::builder() |
1491 | /// .match_kind(MatchKind::LeftmostFirst) |
1492 | /// .build(patterns) |
1493 | /// .unwrap(); |
1494 | /// let mut result = String::new(); |
1495 | /// ac.try_replace_all_with(haystack, &mut result, |mat, _, dst| { |
1496 | /// dst.push_str(&mat.pattern().as_usize().to_string()); |
1497 | /// true |
1498 | /// })?; |
1499 | /// assert_eq!("0 the 2 to the 0age" , result); |
1500 | /// |
1501 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1502 | /// ``` |
1503 | /// |
1504 | /// Stopping the replacement by returning `false` (continued from the |
1505 | /// example above): |
1506 | /// |
1507 | /// ``` |
1508 | /// # use aho_corasick::{AhoCorasick, MatchKind, PatternID}; |
1509 | /// # let patterns = &["append" , "appendage" , "app" ]; |
1510 | /// # let haystack = "append the app to the appendage" ; |
1511 | /// # let ac = AhoCorasick::builder() |
1512 | /// # .match_kind(MatchKind::LeftmostFirst) |
1513 | /// # .build(patterns) |
1514 | /// # .unwrap(); |
1515 | /// let mut result = String::new(); |
1516 | /// ac.try_replace_all_with(haystack, &mut result, |mat, _, dst| { |
1517 | /// dst.push_str(&mat.pattern().as_usize().to_string()); |
1518 | /// mat.pattern() != PatternID::must(2) |
1519 | /// })?; |
1520 | /// assert_eq!("0 the 2 to the appendage" , result); |
1521 | /// |
1522 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1523 | /// ``` |
1524 | pub fn try_replace_all_with<F>( |
1525 | &self, |
1526 | haystack: &str, |
1527 | dst: &mut String, |
1528 | replace_with: F, |
1529 | ) -> Result<(), MatchError> |
1530 | where |
1531 | F: FnMut(&Match, &str, &mut String) -> bool, |
1532 | { |
1533 | enforce_anchored_consistency(self.start_kind, Anchored::No)?; |
1534 | self.aut.try_replace_all_with(haystack, dst, replace_with) |
1535 | } |
1536 | |
1537 | /// Replace all matches using raw bytes with a closure called on each |
1538 | /// match. Matches correspond to the same matches as reported by |
1539 | /// [`AhoCorasick::try_find_iter`]. |
1540 | /// |
1541 | /// The closure accepts three parameters: the match found, the text of |
1542 | /// the match and a byte buffer with which to write the replaced text |
1543 | /// (if any). If the closure returns `true`, then it continues to the next |
1544 | /// match. If the closure returns `false`, then searching is stopped. |
1545 | /// |
1546 | /// This is the fallible version of |
1547 | /// [`AhoCorasick::replace_all_with_bytes`]. |
1548 | /// |
1549 | /// # Errors |
1550 | /// |
1551 | /// This returns an error when this Aho-Corasick searcher does not support |
1552 | /// the default `Input` configuration. More specifically, this occurs only |
1553 | /// when the Aho-Corasick searcher does not support unanchored searches |
1554 | /// since this replacement routine always does an unanchored search. |
1555 | /// |
1556 | /// # Examples |
1557 | /// |
1558 | /// Basic usage: |
1559 | /// |
1560 | /// ``` |
1561 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
1562 | /// |
1563 | /// let patterns = &["append" , "appendage" , "app" ]; |
1564 | /// let haystack = b"append the app to the appendage" ; |
1565 | /// |
1566 | /// let ac = AhoCorasick::builder() |
1567 | /// .match_kind(MatchKind::LeftmostFirst) |
1568 | /// .build(patterns) |
1569 | /// .unwrap(); |
1570 | /// let mut result = vec![]; |
1571 | /// ac.try_replace_all_with_bytes(haystack, &mut result, |mat, _, dst| { |
1572 | /// dst.extend(mat.pattern().as_usize().to_string().bytes()); |
1573 | /// true |
1574 | /// })?; |
1575 | /// assert_eq!(b"0 the 2 to the 0age" .to_vec(), result); |
1576 | /// |
1577 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1578 | /// ``` |
1579 | /// |
1580 | /// Stopping the replacement by returning `false` (continued from the |
1581 | /// example above): |
1582 | /// |
1583 | /// ``` |
1584 | /// # use aho_corasick::{AhoCorasick, MatchKind, PatternID}; |
1585 | /// # let patterns = &["append" , "appendage" , "app" ]; |
1586 | /// # let haystack = b"append the app to the appendage" ; |
1587 | /// # let ac = AhoCorasick::builder() |
1588 | /// # .match_kind(MatchKind::LeftmostFirst) |
1589 | /// # .build(patterns) |
1590 | /// # .unwrap(); |
1591 | /// let mut result = vec![]; |
1592 | /// ac.try_replace_all_with_bytes(haystack, &mut result, |mat, _, dst| { |
1593 | /// dst.extend(mat.pattern().as_usize().to_string().bytes()); |
1594 | /// mat.pattern() != PatternID::must(2) |
1595 | /// })?; |
1596 | /// assert_eq!(b"0 the 2 to the appendage" .to_vec(), result); |
1597 | /// |
1598 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1599 | /// ``` |
1600 | pub fn try_replace_all_with_bytes<F>( |
1601 | &self, |
1602 | haystack: &[u8], |
1603 | dst: &mut Vec<u8>, |
1604 | replace_with: F, |
1605 | ) -> Result<(), MatchError> |
1606 | where |
1607 | F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool, |
1608 | { |
1609 | enforce_anchored_consistency(self.start_kind, Anchored::No)?; |
1610 | self.aut.try_replace_all_with_bytes(haystack, dst, replace_with) |
1611 | } |
1612 | |
1613 | /// Returns an iterator of non-overlapping matches in the given |
1614 | /// stream. Matches correspond to the same matches as reported by |
1615 | /// [`AhoCorasick::try_find_iter`]. |
1616 | /// |
1617 | /// The matches yielded by this iterator use absolute position offsets in |
1618 | /// the stream given, where the first byte has index `0`. Matches are |
1619 | /// yieled until the stream is exhausted. |
1620 | /// |
1621 | /// Each item yielded by the iterator is an `Result<Match, |
1622 | /// std::io::Error>`, where an error is yielded if there was a problem |
1623 | /// reading from the reader given. |
1624 | /// |
1625 | /// When searching a stream, an internal buffer is used. Therefore, callers |
1626 | /// should avoiding providing a buffered reader, if possible. |
1627 | /// |
1628 | /// This is the fallible version of [`AhoCorasick::stream_find_iter`]. |
1629 | /// Note that both methods return iterators that produce `Result` values. |
1630 | /// The difference is that this routine returns an error if _construction_ |
1631 | /// of the iterator failed. The `Result` values yield by the iterator |
1632 | /// come from whether the given reader returns an error or not during the |
1633 | /// search. |
1634 | /// |
1635 | /// # Memory usage |
1636 | /// |
1637 | /// In general, searching streams will use a constant amount of memory for |
1638 | /// its internal buffer. The one requirement is that the internal buffer |
1639 | /// must be at least the size of the longest possible match. In most use |
1640 | /// cases, the default buffer size will be much larger than any individual |
1641 | /// match. |
1642 | /// |
1643 | /// # Errors |
1644 | /// |
1645 | /// This returns an error when this Aho-Corasick searcher does not support |
1646 | /// the default `Input` configuration. More specifically, this occurs only |
1647 | /// when the Aho-Corasick searcher does not support unanchored searches |
1648 | /// since this stream searching routine always does an unanchored search. |
1649 | /// |
1650 | /// This also returns an error if the searcher does not support stream |
1651 | /// searches. Only searchers built with [`MatchKind::Standard`] semantics |
1652 | /// support stream searches. |
1653 | /// |
1654 | /// # Example: basic usage |
1655 | /// |
1656 | /// ``` |
1657 | /// use aho_corasick::{AhoCorasick, PatternID}; |
1658 | /// |
1659 | /// let patterns = &["append" , "appendage" , "app" ]; |
1660 | /// let haystack = "append the app to the appendage" ; |
1661 | /// |
1662 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
1663 | /// let mut matches = vec![]; |
1664 | /// for result in ac.try_stream_find_iter(haystack.as_bytes())? { |
1665 | /// let mat = result?; |
1666 | /// matches.push(mat.pattern()); |
1667 | /// } |
1668 | /// assert_eq!(vec![ |
1669 | /// PatternID::must(2), |
1670 | /// PatternID::must(2), |
1671 | /// PatternID::must(2), |
1672 | /// ], matches); |
1673 | /// |
1674 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1675 | /// ``` |
1676 | #[cfg (feature = "std" )] |
1677 | pub fn try_stream_find_iter<'a, R: std::io::Read>( |
1678 | &'a self, |
1679 | rdr: R, |
1680 | ) -> Result<StreamFindIter<'a, R>, MatchError> { |
1681 | enforce_anchored_consistency(self.start_kind, Anchored::No)?; |
1682 | self.aut.try_stream_find_iter(rdr).map(StreamFindIter) |
1683 | } |
1684 | |
1685 | /// Search for and replace all matches of this automaton in |
1686 | /// the given reader, and write the replacements to the given |
1687 | /// writer. Matches correspond to the same matches as reported by |
1688 | /// [`AhoCorasick::try_find_iter`]. |
1689 | /// |
1690 | /// Replacements are determined by the index of the matching pattern. For |
1691 | /// example, if the pattern with index `2` is found, then it is replaced by |
1692 | /// `replace_with[2]`. |
1693 | /// |
1694 | /// After all matches are replaced, the writer is _not_ flushed. |
1695 | /// |
1696 | /// If there was a problem reading from the given reader or writing to the |
1697 | /// given writer, then the corresponding `io::Error` is returned and all |
1698 | /// replacement is stopped. |
1699 | /// |
1700 | /// When searching a stream, an internal buffer is used. Therefore, callers |
1701 | /// should avoiding providing a buffered reader, if possible. However, |
1702 | /// callers may want to provide a buffered writer. |
1703 | /// |
1704 | /// Note that there is currently no infallible version of this routine. |
1705 | /// |
1706 | /// # Memory usage |
1707 | /// |
1708 | /// In general, searching streams will use a constant amount of memory for |
1709 | /// its internal buffer. The one requirement is that the internal buffer |
1710 | /// must be at least the size of the longest possible match. In most use |
1711 | /// cases, the default buffer size will be much larger than any individual |
1712 | /// match. |
1713 | /// |
1714 | /// # Panics |
1715 | /// |
1716 | /// This panics when `replace_with.len()` does not equal |
1717 | /// [`AhoCorasick::patterns_len`]. |
1718 | /// |
1719 | /// # Errors |
1720 | /// |
1721 | /// This returns an error when this Aho-Corasick searcher does not support |
1722 | /// the default `Input` configuration. More specifically, this occurs only |
1723 | /// when the Aho-Corasick searcher does not support unanchored searches |
1724 | /// since this stream searching routine always does an unanchored search. |
1725 | /// |
1726 | /// This also returns an error if the searcher does not support stream |
1727 | /// searches. Only searchers built with [`MatchKind::Standard`] semantics |
1728 | /// support stream searches. |
1729 | /// |
1730 | /// # Example: basic usage |
1731 | /// |
1732 | /// ``` |
1733 | /// use aho_corasick::AhoCorasick; |
1734 | /// |
1735 | /// let patterns = &["fox" , "brown" , "quick" ]; |
1736 | /// let haystack = "The quick brown fox." ; |
1737 | /// let replace_with = &["sloth" , "grey" , "slow" ]; |
1738 | /// |
1739 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
1740 | /// let mut result = vec![]; |
1741 | /// ac.try_stream_replace_all( |
1742 | /// haystack.as_bytes(), |
1743 | /// &mut result, |
1744 | /// replace_with, |
1745 | /// )?; |
1746 | /// assert_eq!(b"The slow grey sloth." .to_vec(), result); |
1747 | /// |
1748 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1749 | /// ``` |
1750 | #[cfg (feature = "std" )] |
1751 | pub fn try_stream_replace_all<R, W, B>( |
1752 | &self, |
1753 | rdr: R, |
1754 | wtr: W, |
1755 | replace_with: &[B], |
1756 | ) -> Result<(), std::io::Error> |
1757 | where |
1758 | R: std::io::Read, |
1759 | W: std::io::Write, |
1760 | B: AsRef<[u8]>, |
1761 | { |
1762 | enforce_anchored_consistency(self.start_kind, Anchored::No) |
1763 | .map_err(|e| std::io::Error::new(std::io::ErrorKind::Other, e))?; |
1764 | self.aut.try_stream_replace_all(rdr, wtr, replace_with) |
1765 | } |
1766 | |
1767 | /// Search the given reader and replace all matches of this automaton |
1768 | /// using the given closure. The result is written to the given |
1769 | /// writer. Matches correspond to the same matches as reported by |
1770 | /// [`AhoCorasick::try_find_iter`]. |
1771 | /// |
1772 | /// The closure accepts three parameters: the match found, the text of |
1773 | /// the match and the writer with which to write the replaced text (if any). |
1774 | /// |
1775 | /// After all matches are replaced, the writer is _not_ flushed. |
1776 | /// |
1777 | /// If there was a problem reading from the given reader or writing to the |
1778 | /// given writer, then the corresponding `io::Error` is returned and all |
1779 | /// replacement is stopped. |
1780 | /// |
1781 | /// When searching a stream, an internal buffer is used. Therefore, callers |
1782 | /// should avoiding providing a buffered reader, if possible. However, |
1783 | /// callers may want to provide a buffered writer. |
1784 | /// |
1785 | /// Note that there is currently no infallible version of this routine. |
1786 | /// |
1787 | /// # Memory usage |
1788 | /// |
1789 | /// In general, searching streams will use a constant amount of memory for |
1790 | /// its internal buffer. The one requirement is that the internal buffer |
1791 | /// must be at least the size of the longest possible match. In most use |
1792 | /// cases, the default buffer size will be much larger than any individual |
1793 | /// match. |
1794 | /// |
1795 | /// # Errors |
1796 | /// |
1797 | /// This returns an error when this Aho-Corasick searcher does not support |
1798 | /// the default `Input` configuration. More specifically, this occurs only |
1799 | /// when the Aho-Corasick searcher does not support unanchored searches |
1800 | /// since this stream searching routine always does an unanchored search. |
1801 | /// |
1802 | /// This also returns an error if the searcher does not support stream |
1803 | /// searches. Only searchers built with [`MatchKind::Standard`] semantics |
1804 | /// support stream searches. |
1805 | /// |
1806 | /// # Example: basic usage |
1807 | /// |
1808 | /// ``` |
1809 | /// use std::io::Write; |
1810 | /// use aho_corasick::AhoCorasick; |
1811 | /// |
1812 | /// let patterns = &["fox" , "brown" , "quick" ]; |
1813 | /// let haystack = "The quick brown fox." ; |
1814 | /// |
1815 | /// let ac = AhoCorasick::new(patterns).unwrap(); |
1816 | /// let mut result = vec![]; |
1817 | /// ac.try_stream_replace_all_with( |
1818 | /// haystack.as_bytes(), |
1819 | /// &mut result, |
1820 | /// |mat, _, wtr| { |
1821 | /// wtr.write_all(mat.pattern().as_usize().to_string().as_bytes()) |
1822 | /// }, |
1823 | /// )?; |
1824 | /// assert_eq!(b"The 2 1 0." .to_vec(), result); |
1825 | /// |
1826 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
1827 | /// ``` |
1828 | #[cfg (feature = "std" )] |
1829 | pub fn try_stream_replace_all_with<R, W, F>( |
1830 | &self, |
1831 | rdr: R, |
1832 | wtr: W, |
1833 | replace_with: F, |
1834 | ) -> Result<(), std::io::Error> |
1835 | where |
1836 | R: std::io::Read, |
1837 | W: std::io::Write, |
1838 | F: FnMut(&Match, &[u8], &mut W) -> Result<(), std::io::Error>, |
1839 | { |
1840 | enforce_anchored_consistency(self.start_kind, Anchored::No) |
1841 | .map_err(|e| std::io::Error::new(std::io::ErrorKind::Other, e))?; |
1842 | self.aut.try_stream_replace_all_with(rdr, wtr, replace_with) |
1843 | } |
1844 | } |
1845 | |
1846 | /// Routines for querying information about the Aho-Corasick automaton. |
1847 | impl AhoCorasick { |
1848 | /// Returns the kind of the Aho-Corasick automaton used by this searcher. |
1849 | /// |
1850 | /// Knowing the Aho-Corasick kind is principally useful for diagnostic |
1851 | /// purposes. In particular, if no specific kind was given to |
1852 | /// [`AhoCorasickBuilder::kind`], then one is automatically chosen and |
1853 | /// this routine will report which one. |
1854 | /// |
1855 | /// Note that the heuristics used for choosing which `AhoCorasickKind` |
1856 | /// may be changed in a semver compatible release. |
1857 | /// |
1858 | /// # Examples |
1859 | /// |
1860 | /// ``` |
1861 | /// use aho_corasick::{AhoCorasick, AhoCorasickKind}; |
1862 | /// |
1863 | /// let ac = AhoCorasick::new(&["foo" , "bar" , "quux" , "baz" ]).unwrap(); |
1864 | /// // The specific Aho-Corasick kind chosen is not guaranteed! |
1865 | /// assert_eq!(AhoCorasickKind::DFA, ac.kind()); |
1866 | /// ``` |
1867 | pub fn kind(&self) -> AhoCorasickKind { |
1868 | self.kind |
1869 | } |
1870 | |
1871 | /// Returns the type of starting search configuration supported by this |
1872 | /// Aho-Corasick automaton. |
1873 | /// |
1874 | /// # Examples |
1875 | /// |
1876 | /// ``` |
1877 | /// use aho_corasick::{AhoCorasick, StartKind}; |
1878 | /// |
1879 | /// let ac = AhoCorasick::new(&["foo" , "bar" , "quux" , "baz" ]).unwrap(); |
1880 | /// assert_eq!(StartKind::Unanchored, ac.start_kind()); |
1881 | /// ``` |
1882 | pub fn start_kind(&self) -> StartKind { |
1883 | self.start_kind |
1884 | } |
1885 | |
1886 | /// Returns the match kind used by this automaton. |
1887 | /// |
1888 | /// The match kind is important because it determines what kinds of |
1889 | /// matches are returned. Also, some operations (such as overlapping |
1890 | /// search and stream searching) are only supported when using the |
1891 | /// [`MatchKind::Standard`] match kind. |
1892 | /// |
1893 | /// # Examples |
1894 | /// |
1895 | /// ``` |
1896 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
1897 | /// |
1898 | /// let ac = AhoCorasick::new(&["foo" , "bar" , "quux" , "baz" ]).unwrap(); |
1899 | /// assert_eq!(MatchKind::Standard, ac.match_kind()); |
1900 | /// ``` |
1901 | pub fn match_kind(&self) -> MatchKind { |
1902 | self.aut.match_kind() |
1903 | } |
1904 | |
1905 | /// Returns the length of the shortest pattern matched by this automaton. |
1906 | /// |
1907 | /// # Examples |
1908 | /// |
1909 | /// Basic usage: |
1910 | /// |
1911 | /// ``` |
1912 | /// use aho_corasick::AhoCorasick; |
1913 | /// |
1914 | /// let ac = AhoCorasick::new(&["foo" , "bar" , "quux" , "baz" ]).unwrap(); |
1915 | /// assert_eq!(3, ac.min_pattern_len()); |
1916 | /// ``` |
1917 | /// |
1918 | /// Note that an `AhoCorasick` automaton has a minimum length of `0` if |
1919 | /// and only if it can match the empty string: |
1920 | /// |
1921 | /// ``` |
1922 | /// use aho_corasick::AhoCorasick; |
1923 | /// |
1924 | /// let ac = AhoCorasick::new(&["foo" , "" , "quux" , "baz" ]).unwrap(); |
1925 | /// assert_eq!(0, ac.min_pattern_len()); |
1926 | /// ``` |
1927 | pub fn min_pattern_len(&self) -> usize { |
1928 | self.aut.min_pattern_len() |
1929 | } |
1930 | |
1931 | /// Returns the length of the longest pattern matched by this automaton. |
1932 | /// |
1933 | /// # Examples |
1934 | /// |
1935 | /// Basic usage: |
1936 | /// |
1937 | /// ``` |
1938 | /// use aho_corasick::AhoCorasick; |
1939 | /// |
1940 | /// let ac = AhoCorasick::new(&["foo" , "bar" , "quux" , "baz" ]).unwrap(); |
1941 | /// assert_eq!(4, ac.max_pattern_len()); |
1942 | /// ``` |
1943 | pub fn max_pattern_len(&self) -> usize { |
1944 | self.aut.max_pattern_len() |
1945 | } |
1946 | |
1947 | /// Return the total number of patterns matched by this automaton. |
1948 | /// |
1949 | /// This includes patterns that may never participate in a match. For |
1950 | /// example, if [`MatchKind::LeftmostFirst`] match semantics are used, and |
1951 | /// the patterns `Sam` and `Samwise` were used to build the automaton (in |
1952 | /// that order), then `Samwise` can never participate in a match because |
1953 | /// `Sam` will always take priority. |
1954 | /// |
1955 | /// # Examples |
1956 | /// |
1957 | /// Basic usage: |
1958 | /// |
1959 | /// ``` |
1960 | /// use aho_corasick::AhoCorasick; |
1961 | /// |
1962 | /// let ac = AhoCorasick::new(&["foo" , "bar" , "baz" ]).unwrap(); |
1963 | /// assert_eq!(3, ac.patterns_len()); |
1964 | /// ``` |
1965 | pub fn patterns_len(&self) -> usize { |
1966 | self.aut.patterns_len() |
1967 | } |
1968 | |
1969 | /// Returns the approximate total amount of heap used by this automaton, in |
1970 | /// units of bytes. |
1971 | /// |
1972 | /// # Examples |
1973 | /// |
1974 | /// This example shows the difference in heap usage between a few |
1975 | /// configurations: |
1976 | /// |
1977 | /// ``` |
1978 | /// # if !cfg!(target_pointer_width = "64" ) { return; } |
1979 | /// use aho_corasick::{AhoCorasick, AhoCorasickKind, MatchKind}; |
1980 | /// |
1981 | /// let ac = AhoCorasick::builder() |
1982 | /// .kind(None) // default |
1983 | /// .build(&["foobar" , "bruce" , "triskaidekaphobia" , "springsteen" ]) |
1984 | /// .unwrap(); |
1985 | /// assert_eq!(5_632, ac.memory_usage()); |
1986 | /// |
1987 | /// let ac = AhoCorasick::builder() |
1988 | /// .kind(None) // default |
1989 | /// .ascii_case_insensitive(true) |
1990 | /// .build(&["foobar" , "bruce" , "triskaidekaphobia" , "springsteen" ]) |
1991 | /// .unwrap(); |
1992 | /// assert_eq!(11_136, ac.memory_usage()); |
1993 | /// |
1994 | /// let ac = AhoCorasick::builder() |
1995 | /// .kind(Some(AhoCorasickKind::NoncontiguousNFA)) |
1996 | /// .ascii_case_insensitive(true) |
1997 | /// .build(&["foobar" , "bruce" , "triskaidekaphobia" , "springsteen" ]) |
1998 | /// .unwrap(); |
1999 | /// assert_eq!(9_128, ac.memory_usage()); |
2000 | /// |
2001 | /// let ac = AhoCorasick::builder() |
2002 | /// .kind(Some(AhoCorasickKind::ContiguousNFA)) |
2003 | /// .ascii_case_insensitive(true) |
2004 | /// .build(&["foobar" , "bruce" , "triskaidekaphobia" , "springsteen" ]) |
2005 | /// .unwrap(); |
2006 | /// assert_eq!(2_584, ac.memory_usage()); |
2007 | /// |
2008 | /// let ac = AhoCorasick::builder() |
2009 | /// .kind(Some(AhoCorasickKind::DFA)) |
2010 | /// .ascii_case_insensitive(true) |
2011 | /// .build(&["foobar" , "bruce" , "triskaidekaphobia" , "springsteen" ]) |
2012 | /// .unwrap(); |
2013 | /// // While this shows the DFA being the biggest here by a small margin, |
2014 | /// // don't let the difference fool you. With such a small number of |
2015 | /// // patterns, the difference is small, but a bigger number of patterns |
2016 | /// // will reveal that the rate of growth of the DFA is far bigger than |
2017 | /// // the NFAs above. For a large number of patterns, it is easy for the |
2018 | /// // DFA to take an order of magnitude more heap space (or more!). |
2019 | /// assert_eq!(11_136, ac.memory_usage()); |
2020 | /// ``` |
2021 | pub fn memory_usage(&self) -> usize { |
2022 | self.aut.memory_usage() |
2023 | } |
2024 | } |
2025 | |
2026 | // We provide a manual debug impl so that we don't include the 'start_kind', |
2027 | // principally because it's kind of weird to do so and because it screws with |
2028 | // the carefully curated debug output for the underlying automaton. |
2029 | impl core::fmt::Debug for AhoCorasick { |
2030 | fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
2031 | f.debug_tuple(name:"AhoCorasick" ).field(&self.aut).finish() |
2032 | } |
2033 | } |
2034 | |
2035 | /// An iterator of non-overlapping matches in a particular haystack. |
2036 | /// |
2037 | /// This iterator yields matches according to the [`MatchKind`] used by this |
2038 | /// automaton. |
2039 | /// |
2040 | /// This iterator is constructed via the [`AhoCorasick::find_iter`] and |
2041 | /// [`AhoCorasick::try_find_iter`] methods. |
2042 | /// |
2043 | /// The lifetime `'a` refers to the lifetime of the `AhoCorasick` automaton. |
2044 | /// |
2045 | /// The lifetime `'h` refers to the lifetime of the haystack being searched. |
2046 | #[derive (Debug)] |
2047 | pub struct FindIter<'a, 'h>(automaton::FindIter<'a, 'h, Arc<dyn AcAutomaton>>); |
2048 | |
2049 | impl<'a, 'h> Iterator for FindIter<'a, 'h> { |
2050 | type Item = Match; |
2051 | |
2052 | #[inline ] |
2053 | fn next(&mut self) -> Option<Match> { |
2054 | self.0.next() |
2055 | } |
2056 | } |
2057 | |
2058 | /// An iterator of overlapping matches in a particular haystack. |
2059 | /// |
2060 | /// This iterator will report all possible matches in a particular haystack, |
2061 | /// even when the matches overlap. |
2062 | /// |
2063 | /// This iterator is constructed via the [`AhoCorasick::find_overlapping_iter`] |
2064 | /// and [`AhoCorasick::try_find_overlapping_iter`] methods. |
2065 | /// |
2066 | /// The lifetime `'a` refers to the lifetime of the `AhoCorasick` automaton. |
2067 | /// |
2068 | /// The lifetime `'h` refers to the lifetime of the haystack being searched. |
2069 | #[derive (Debug)] |
2070 | pub struct FindOverlappingIter<'a, 'h>( |
2071 | automaton::FindOverlappingIter<'a, 'h, Arc<dyn AcAutomaton>>, |
2072 | ); |
2073 | |
2074 | impl<'a, 'h> Iterator for FindOverlappingIter<'a, 'h> { |
2075 | type Item = Match; |
2076 | |
2077 | #[inline ] |
2078 | fn next(&mut self) -> Option<Match> { |
2079 | self.0.next() |
2080 | } |
2081 | } |
2082 | |
2083 | /// An iterator that reports Aho-Corasick matches in a stream. |
2084 | /// |
2085 | /// This iterator yields elements of type `Result<Match, std::io::Error>`, |
2086 | /// where an error is reported if there was a problem reading from the |
2087 | /// underlying stream. The iterator terminates only when the underlying stream |
2088 | /// reaches `EOF`. |
2089 | /// |
2090 | /// This iterator is constructed via the [`AhoCorasick::stream_find_iter`] and |
2091 | /// [`AhoCorasick::try_stream_find_iter`] methods. |
2092 | /// |
2093 | /// The type variable `R` refers to the `io::Read` stream that is being read |
2094 | /// from. |
2095 | /// |
2096 | /// The lifetime `'a` refers to the lifetime of the corresponding |
2097 | /// [`AhoCorasick`] searcher. |
2098 | #[cfg (feature = "std" )] |
2099 | #[derive (Debug)] |
2100 | pub struct StreamFindIter<'a, R>( |
2101 | automaton::StreamFindIter<'a, Arc<dyn AcAutomaton>, R>, |
2102 | ); |
2103 | |
2104 | #[cfg (feature = "std" )] |
2105 | impl<'a, R: std::io::Read> Iterator for StreamFindIter<'a, R> { |
2106 | type Item = Result<Match, std::io::Error>; |
2107 | |
2108 | fn next(&mut self) -> Option<Result<Match, std::io::Error>> { |
2109 | self.0.next() |
2110 | } |
2111 | } |
2112 | |
2113 | /// A builder for configuring an Aho-Corasick automaton. |
2114 | /// |
2115 | /// # Quick advice |
2116 | /// |
2117 | /// * Use [`AhoCorasickBuilder::match_kind`] to configure your searcher |
2118 | /// with [`MatchKind::LeftmostFirst`] if you want to match how backtracking |
2119 | /// regex engines execute searches for `pat1|pat2|..|patN`. Use |
2120 | /// [`MatchKind::LeftmostLongest`] if you want to match how POSIX regex engines |
2121 | /// do it. |
2122 | /// * If you need an anchored search, use [`AhoCorasickBuilder::start_kind`] to |
2123 | /// set the [`StartKind::Anchored`] mode since [`StartKind::Unanchored`] is the |
2124 | /// default. Or just use [`StartKind::Both`] to support both types of searches. |
2125 | /// * You might want to use [`AhoCorasickBuilder::kind`] to set your searcher |
2126 | /// to always use a [`AhoCorasickKind::DFA`] if search speed is critical and |
2127 | /// memory usage isn't a concern. Otherwise, not setting a kind will probably |
2128 | /// make the right choice for you. Beware that if you use [`StartKind::Both`] |
2129 | /// to build a searcher that supports both unanchored and anchored searches |
2130 | /// _and_ you set [`AhoCorasickKind::DFA`], then the DFA will essentially be |
2131 | /// duplicated to support both simultaneously. This results in very high memory |
2132 | /// usage. |
2133 | /// * For all other options, their defaults are almost certainly what you want. |
2134 | #[derive (Clone, Debug, Default)] |
2135 | pub struct AhoCorasickBuilder { |
2136 | nfa_noncontiguous: noncontiguous::Builder, |
2137 | nfa_contiguous: contiguous::Builder, |
2138 | dfa: dfa::Builder, |
2139 | kind: Option<AhoCorasickKind>, |
2140 | start_kind: StartKind, |
2141 | } |
2142 | |
2143 | impl AhoCorasickBuilder { |
2144 | /// Create a new builder for configuring an Aho-Corasick automaton. |
2145 | /// |
2146 | /// The builder provides a way to configure a number of things, including |
2147 | /// ASCII case insensitivity and what kind of match semantics are used. |
2148 | pub fn new() -> AhoCorasickBuilder { |
2149 | AhoCorasickBuilder::default() |
2150 | } |
2151 | |
2152 | /// Build an Aho-Corasick automaton using the configuration set on this |
2153 | /// builder. |
2154 | /// |
2155 | /// A builder may be reused to create more automatons. |
2156 | /// |
2157 | /// # Examples |
2158 | /// |
2159 | /// Basic usage: |
2160 | /// |
2161 | /// ``` |
2162 | /// use aho_corasick::{AhoCorasickBuilder, PatternID}; |
2163 | /// |
2164 | /// let patterns = &["foo" , "bar" , "baz" ]; |
2165 | /// let ac = AhoCorasickBuilder::new().build(patterns).unwrap(); |
2166 | /// assert_eq!( |
2167 | /// Some(PatternID::must(1)), |
2168 | /// ac.find("xxx bar xxx" ).map(|m| m.pattern()), |
2169 | /// ); |
2170 | /// ``` |
2171 | pub fn build<I, P>(&self, patterns: I) -> Result<AhoCorasick, BuildError> |
2172 | where |
2173 | I: IntoIterator<Item = P>, |
2174 | P: AsRef<[u8]>, |
2175 | { |
2176 | let nfa = self.nfa_noncontiguous.build(patterns)?; |
2177 | let (aut, kind): (Arc<dyn AcAutomaton>, AhoCorasickKind) = |
2178 | match self.kind { |
2179 | None => { |
2180 | debug!( |
2181 | "asked for automatic Aho-Corasick implementation, \ |
2182 | criteria: <patterns: {:?}, max pattern len: {:?}, \ |
2183 | start kind: {:?}>" , |
2184 | nfa.patterns_len(), |
2185 | nfa.max_pattern_len(), |
2186 | self.start_kind, |
2187 | ); |
2188 | self.build_auto(nfa) |
2189 | } |
2190 | Some(AhoCorasickKind::NoncontiguousNFA) => { |
2191 | debug!("forcefully chose noncontiguous NFA" ); |
2192 | (Arc::new(nfa), AhoCorasickKind::NoncontiguousNFA) |
2193 | } |
2194 | Some(AhoCorasickKind::ContiguousNFA) => { |
2195 | debug!("forcefully chose contiguous NFA" ); |
2196 | let cnfa = |
2197 | self.nfa_contiguous.build_from_noncontiguous(&nfa)?; |
2198 | (Arc::new(cnfa), AhoCorasickKind::ContiguousNFA) |
2199 | } |
2200 | Some(AhoCorasickKind::DFA) => { |
2201 | debug!("forcefully chose DFA" ); |
2202 | let dfa = self.dfa.build_from_noncontiguous(&nfa)?; |
2203 | (Arc::new(dfa), AhoCorasickKind::DFA) |
2204 | } |
2205 | }; |
2206 | Ok(AhoCorasick { aut, kind, start_kind: self.start_kind }) |
2207 | } |
2208 | |
2209 | /// Implements the automatic selection logic for the Aho-Corasick |
2210 | /// implementation to use. Since all Aho-Corasick automatons are built |
2211 | /// from a non-contiguous NFA, the caller is responsible for building |
2212 | /// that first. |
2213 | fn build_auto( |
2214 | &self, |
2215 | nfa: noncontiguous::NFA, |
2216 | ) -> (Arc<dyn AcAutomaton>, AhoCorasickKind) { |
2217 | // We try to build a DFA if we have a very small number of patterns, |
2218 | // otherwise the memory usage just gets too crazy. We also only do it |
2219 | // when the start kind is unanchored or anchored, but not both, because |
2220 | // both implies two full copies of the transition table. |
2221 | let try_dfa = !matches!(self.start_kind, StartKind::Both) |
2222 | && nfa.patterns_len() <= 100; |
2223 | if try_dfa { |
2224 | match self.dfa.build_from_noncontiguous(&nfa) { |
2225 | Ok(dfa) => { |
2226 | debug!("chose a DFA" ); |
2227 | return (Arc::new(dfa), AhoCorasickKind::DFA); |
2228 | } |
2229 | Err(_err) => { |
2230 | debug!( |
2231 | "failed to build DFA, trying something else: {}" , |
2232 | _err |
2233 | ); |
2234 | } |
2235 | } |
2236 | } |
2237 | // We basically always want a contiguous NFA if the limited |
2238 | // circumstances in which we use a DFA are not true. It is quite fast |
2239 | // and has excellent memory usage. The only way we don't use it is if |
2240 | // there are so many states that it can't fit in a contiguous NFA. |
2241 | // And the only way to know that is to try to build it. Building a |
2242 | // contiguous NFA is mostly just reshuffling data from a noncontiguous |
2243 | // NFA, so it isn't too expensive, especially relative to building a |
2244 | // noncontiguous NFA in the first place. |
2245 | match self.nfa_contiguous.build_from_noncontiguous(&nfa) { |
2246 | Ok(nfa) => { |
2247 | debug!("chose contiguous NFA" ); |
2248 | return (Arc::new(nfa), AhoCorasickKind::ContiguousNFA); |
2249 | } |
2250 | #[allow (unused_variables)] // unused when 'logging' is disabled |
2251 | Err(_err) => { |
2252 | debug!( |
2253 | "failed to build contiguous NFA, \ |
2254 | trying something else: {}" , |
2255 | _err |
2256 | ); |
2257 | } |
2258 | } |
2259 | debug!("chose non-contiguous NFA" ); |
2260 | (Arc::new(nfa), AhoCorasickKind::NoncontiguousNFA) |
2261 | } |
2262 | |
2263 | /// Set the desired match semantics. |
2264 | /// |
2265 | /// The default is [`MatchKind::Standard`], which corresponds to the match |
2266 | /// semantics supported by the standard textbook description of the |
2267 | /// Aho-Corasick algorithm. Namely, matches are reported as soon as they |
2268 | /// are found. Moreover, this is the only way to get overlapping matches |
2269 | /// or do stream searching. |
2270 | /// |
2271 | /// The other kinds of match semantics that are supported are |
2272 | /// [`MatchKind::LeftmostFirst`] and [`MatchKind::LeftmostLongest`]. The |
2273 | /// former corresponds to the match you would get if you were to try to |
2274 | /// match each pattern at each position in the haystack in the same order |
2275 | /// that you give to the automaton. That is, it returns the leftmost match |
2276 | /// corresponding to the earliest pattern given to the automaton. The |
2277 | /// latter corresponds to finding the longest possible match among all |
2278 | /// leftmost matches. |
2279 | /// |
2280 | /// For more details on match semantics, see the [documentation for |
2281 | /// `MatchKind`](MatchKind). |
2282 | /// |
2283 | /// Note that setting this to [`MatchKind::LeftmostFirst`] or |
2284 | /// [`MatchKind::LeftmostLongest`] will cause some search routines on |
2285 | /// [`AhoCorasick`] to return an error (or panic if you're using the |
2286 | /// infallible API). Notably, this includes stream and overlapping |
2287 | /// searches. |
2288 | /// |
2289 | /// # Examples |
2290 | /// |
2291 | /// In these examples, we demonstrate the differences between match |
2292 | /// semantics for a particular set of patterns in a specific order: |
2293 | /// `b`, `abc`, `abcd`. |
2294 | /// |
2295 | /// Standard semantics: |
2296 | /// |
2297 | /// ``` |
2298 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
2299 | /// |
2300 | /// let patterns = &["b" , "abc" , "abcd" ]; |
2301 | /// let haystack = "abcd" ; |
2302 | /// |
2303 | /// let ac = AhoCorasick::builder() |
2304 | /// .match_kind(MatchKind::Standard) // default, not necessary |
2305 | /// .build(patterns) |
2306 | /// .unwrap(); |
2307 | /// let mat = ac.find(haystack).expect("should have a match" ); |
2308 | /// assert_eq!("b" , &haystack[mat.start()..mat.end()]); |
2309 | /// ``` |
2310 | /// |
2311 | /// Leftmost-first semantics: |
2312 | /// |
2313 | /// ``` |
2314 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
2315 | /// |
2316 | /// let patterns = &["b" , "abc" , "abcd" ]; |
2317 | /// let haystack = "abcd" ; |
2318 | /// |
2319 | /// let ac = AhoCorasick::builder() |
2320 | /// .match_kind(MatchKind::LeftmostFirst) |
2321 | /// .build(patterns) |
2322 | /// .unwrap(); |
2323 | /// let mat = ac.find(haystack).expect("should have a match" ); |
2324 | /// assert_eq!("abc" , &haystack[mat.start()..mat.end()]); |
2325 | /// ``` |
2326 | /// |
2327 | /// Leftmost-longest semantics: |
2328 | /// |
2329 | /// ``` |
2330 | /// use aho_corasick::{AhoCorasick, MatchKind}; |
2331 | /// |
2332 | /// let patterns = &["b" , "abc" , "abcd" ]; |
2333 | /// let haystack = "abcd" ; |
2334 | /// |
2335 | /// let ac = AhoCorasick::builder() |
2336 | /// .match_kind(MatchKind::LeftmostLongest) |
2337 | /// .build(patterns) |
2338 | /// .unwrap(); |
2339 | /// let mat = ac.find(haystack).expect("should have a match" ); |
2340 | /// assert_eq!("abcd" , &haystack[mat.start()..mat.end()]); |
2341 | /// ``` |
2342 | pub fn match_kind(&mut self, kind: MatchKind) -> &mut AhoCorasickBuilder { |
2343 | self.nfa_noncontiguous.match_kind(kind); |
2344 | self.nfa_contiguous.match_kind(kind); |
2345 | self.dfa.match_kind(kind); |
2346 | self |
2347 | } |
2348 | |
2349 | /// Sets the starting state configuration for the automaton. |
2350 | /// |
2351 | /// Every Aho-Corasick automaton is capable of having two start states: one |
2352 | /// that is used for unanchored searches and one that is used for anchored |
2353 | /// searches. Some automatons, like the NFAs, support this with almost zero |
2354 | /// additional cost. Other automatons, like the DFA, require two copies of |
2355 | /// the underlying transition table to support both simultaneously. |
2356 | /// |
2357 | /// Because there may be an added non-trivial cost to supporting both, it |
2358 | /// is possible to configure which starting state configuration is needed. |
2359 | /// |
2360 | /// Indeed, since anchored searches tend to be somewhat more rare, |
2361 | /// _only_ unanchored searches are supported by default. Thus, |
2362 | /// [`StartKind::Unanchored`] is the default. |
2363 | /// |
2364 | /// Note that when this is set to [`StartKind::Unanchored`], then |
2365 | /// running an anchored search will result in an error (or a panic |
2366 | /// if using the infallible APIs). Similarly, when this is set to |
2367 | /// [`StartKind::Anchored`], then running an unanchored search will |
2368 | /// result in an error (or a panic if using the infallible APIs). When |
2369 | /// [`StartKind::Both`] is used, then both unanchored and anchored searches |
2370 | /// are always supported. |
2371 | /// |
2372 | /// Also note that even if an `AhoCorasick` searcher is using an NFA |
2373 | /// internally (which always supports both unanchored and anchored |
2374 | /// searches), an error will still be reported for a search that isn't |
2375 | /// supported by the configuration set via this method. This means, |
2376 | /// for example, that an error is never dependent on which internal |
2377 | /// implementation of Aho-Corasick is used. |
2378 | /// |
2379 | /// # Example: anchored search |
2380 | /// |
2381 | /// This shows how to build a searcher that only supports anchored |
2382 | /// searches: |
2383 | /// |
2384 | /// ``` |
2385 | /// use aho_corasick::{ |
2386 | /// AhoCorasick, Anchored, Input, Match, MatchKind, StartKind, |
2387 | /// }; |
2388 | /// |
2389 | /// let ac = AhoCorasick::builder() |
2390 | /// .match_kind(MatchKind::LeftmostFirst) |
2391 | /// .start_kind(StartKind::Anchored) |
2392 | /// .build(&["b" , "abc" , "abcd" ]) |
2393 | /// .unwrap(); |
2394 | /// |
2395 | /// // An unanchored search is not supported! An error here is guaranteed |
2396 | /// // given the configuration above regardless of which kind of |
2397 | /// // Aho-Corasick implementation ends up being used internally. |
2398 | /// let input = Input::new("foo abcd" ).anchored(Anchored::No); |
2399 | /// assert!(ac.try_find(input).is_err()); |
2400 | /// |
2401 | /// let input = Input::new("foo abcd" ).anchored(Anchored::Yes); |
2402 | /// assert_eq!(None, ac.try_find(input)?); |
2403 | /// |
2404 | /// let input = Input::new("abcd" ).anchored(Anchored::Yes); |
2405 | /// assert_eq!(Some(Match::must(1, 0..3)), ac.try_find(input)?); |
2406 | /// |
2407 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
2408 | /// ``` |
2409 | /// |
2410 | /// # Example: unanchored and anchored searches |
2411 | /// |
2412 | /// This shows how to build a searcher that supports both unanchored and |
2413 | /// anchored searches: |
2414 | /// |
2415 | /// ``` |
2416 | /// use aho_corasick::{ |
2417 | /// AhoCorasick, Anchored, Input, Match, MatchKind, StartKind, |
2418 | /// }; |
2419 | /// |
2420 | /// let ac = AhoCorasick::builder() |
2421 | /// .match_kind(MatchKind::LeftmostFirst) |
2422 | /// .start_kind(StartKind::Both) |
2423 | /// .build(&["b" , "abc" , "abcd" ]) |
2424 | /// .unwrap(); |
2425 | /// |
2426 | /// let input = Input::new("foo abcd" ).anchored(Anchored::No); |
2427 | /// assert_eq!(Some(Match::must(1, 4..7)), ac.try_find(input)?); |
2428 | /// |
2429 | /// let input = Input::new("foo abcd" ).anchored(Anchored::Yes); |
2430 | /// assert_eq!(None, ac.try_find(input)?); |
2431 | /// |
2432 | /// let input = Input::new("abcd" ).anchored(Anchored::Yes); |
2433 | /// assert_eq!(Some(Match::must(1, 0..3)), ac.try_find(input)?); |
2434 | /// |
2435 | /// # Ok::<(), Box<dyn std::error::Error>>(()) |
2436 | /// ``` |
2437 | pub fn start_kind(&mut self, kind: StartKind) -> &mut AhoCorasickBuilder { |
2438 | self.dfa.start_kind(kind); |
2439 | self.start_kind = kind; |
2440 | self |
2441 | } |
2442 | |
2443 | /// Enable ASCII-aware case insensitive matching. |
2444 | /// |
2445 | /// When this option is enabled, searching will be performed without |
2446 | /// respect to case for ASCII letters (`a-z` and `A-Z`) only. |
2447 | /// |
2448 | /// Enabling this option does not change the search algorithm, but it may |
2449 | /// increase the size of the automaton. |
2450 | /// |
2451 | /// **NOTE:** It is unlikely that support for Unicode case folding will |
2452 | /// be added in the future. The ASCII case works via a simple hack to the |
2453 | /// underlying automaton, but full Unicode handling requires a fair bit of |
2454 | /// sophistication. If you do need Unicode handling, you might consider |
2455 | /// using the [`regex` crate](https://docs.rs/regex) or the lower level |
2456 | /// [`regex-automata` crate](https://docs.rs/regex-automata). |
2457 | /// |
2458 | /// # Examples |
2459 | /// |
2460 | /// Basic usage: |
2461 | /// |
2462 | /// ``` |
2463 | /// use aho_corasick::AhoCorasick; |
2464 | /// |
2465 | /// let patterns = &["FOO" , "bAr" , "BaZ" ]; |
2466 | /// let haystack = "foo bar baz" ; |
2467 | /// |
2468 | /// let ac = AhoCorasick::builder() |
2469 | /// .ascii_case_insensitive(true) |
2470 | /// .build(patterns) |
2471 | /// .unwrap(); |
2472 | /// assert_eq!(3, ac.find_iter(haystack).count()); |
2473 | /// ``` |
2474 | pub fn ascii_case_insensitive( |
2475 | &mut self, |
2476 | yes: bool, |
2477 | ) -> &mut AhoCorasickBuilder { |
2478 | self.nfa_noncontiguous.ascii_case_insensitive(yes); |
2479 | self.nfa_contiguous.ascii_case_insensitive(yes); |
2480 | self.dfa.ascii_case_insensitive(yes); |
2481 | self |
2482 | } |
2483 | |
2484 | /// Choose the type of underlying automaton to use. |
2485 | /// |
2486 | /// Currently, there are four choices: |
2487 | /// |
2488 | /// * [`AhoCorasickKind::NoncontiguousNFA`] instructs the searcher to |
2489 | /// use a [`noncontiguous::NFA`]. A noncontiguous NFA is the fastest to |
2490 | /// be built, has moderate memory usage and is typically the slowest to |
2491 | /// execute a search. |
2492 | /// * [`AhoCorasickKind::ContiguousNFA`] instructs the searcher to use a |
2493 | /// [`contiguous::NFA`]. A contiguous NFA is a little slower to build than |
2494 | /// a noncontiguous NFA, has excellent memory usage and is typically a |
2495 | /// little slower than a DFA for a search. |
2496 | /// * [`AhoCorasickKind::DFA`] instructs the searcher to use a |
2497 | /// [`dfa::DFA`]. A DFA is very slow to build, uses exorbitant amounts of |
2498 | /// memory, but will typically execute searches the fastest. |
2499 | /// * `None` (the default) instructs the searcher to choose the "best" |
2500 | /// Aho-Corasick implementation. This choice is typically based primarily |
2501 | /// on the number of patterns. |
2502 | /// |
2503 | /// Setting this configuration does not change the time complexity for |
2504 | /// constructing the Aho-Corasick automaton (which is `O(p)` where `p` |
2505 | /// is the total number of patterns being compiled). Setting this to |
2506 | /// [`AhoCorasickKind::DFA`] does however reduce the time complexity of |
2507 | /// non-overlapping searches from `O(n + p)` to `O(n)`, where `n` is the |
2508 | /// length of the haystack. |
2509 | /// |
2510 | /// In general, you should probably stick to the default unless you have |
2511 | /// some kind of reason to use a specific Aho-Corasick implementation. For |
2512 | /// example, you might choose `AhoCorasickKind::DFA` if you don't care |
2513 | /// about memory usage and want the fastest possible search times. |
2514 | /// |
2515 | /// Setting this guarantees that the searcher returned uses the chosen |
2516 | /// implementation. If that implementation could not be constructed, then |
2517 | /// an error will be returned. In contrast, when `None` is used, it is |
2518 | /// possible for it to attempt to construct, for example, a contiguous |
2519 | /// NFA and have it fail. In which case, it will fall back to using a |
2520 | /// noncontiguous NFA. |
2521 | /// |
2522 | /// If `None` is given, then one may use [`AhoCorasick::kind`] to determine |
2523 | /// which Aho-Corasick implementation was chosen. |
2524 | /// |
2525 | /// Note that the heuristics used for choosing which `AhoCorasickKind` |
2526 | /// may be changed in a semver compatible release. |
2527 | pub fn kind( |
2528 | &mut self, |
2529 | kind: Option<AhoCorasickKind>, |
2530 | ) -> &mut AhoCorasickBuilder { |
2531 | self.kind = kind; |
2532 | self |
2533 | } |
2534 | |
2535 | /// Enable heuristic prefilter optimizations. |
2536 | /// |
2537 | /// When enabled, searching will attempt to quickly skip to match |
2538 | /// candidates using specialized literal search routines. A prefilter |
2539 | /// cannot always be used, and is generally treated as a heuristic. It |
2540 | /// can be useful to disable this if the prefilter is observed to be |
2541 | /// sub-optimal for a particular workload. |
2542 | /// |
2543 | /// Currently, prefilters are typically only active when building searchers |
2544 | /// with a small (less than 100) number of patterns. |
2545 | /// |
2546 | /// This is enabled by default. |
2547 | pub fn prefilter(&mut self, yes: bool) -> &mut AhoCorasickBuilder { |
2548 | self.nfa_noncontiguous.prefilter(yes); |
2549 | self.nfa_contiguous.prefilter(yes); |
2550 | self.dfa.prefilter(yes); |
2551 | self |
2552 | } |
2553 | |
2554 | /// Set the limit on how many states use a dense representation for their |
2555 | /// transitions. Other states will generally use a sparse representation. |
2556 | /// |
2557 | /// A dense representation uses more memory but is generally faster, since |
2558 | /// the next transition in a dense representation can be computed in a |
2559 | /// constant number of instructions. A sparse representation uses less |
2560 | /// memory but is generally slower, since the next transition in a sparse |
2561 | /// representation requires executing a variable number of instructions. |
2562 | /// |
2563 | /// This setting is only used when an Aho-Corasick implementation is used |
2564 | /// that supports the dense versus sparse representation trade off. Not all |
2565 | /// do. |
2566 | /// |
2567 | /// This limit is expressed in terms of the depth of a state, i.e., the |
2568 | /// number of transitions from the starting state of the automaton. The |
2569 | /// idea is that most of the time searching will be spent near the starting |
2570 | /// state of the automaton, so states near the start state should use a |
2571 | /// dense representation. States further away from the start state would |
2572 | /// then use a sparse representation. |
2573 | /// |
2574 | /// By default, this is set to a low but non-zero number. Setting this to |
2575 | /// `0` is almost never what you want, since it is likely to make searches |
2576 | /// very slow due to the start state itself being forced to use a sparse |
2577 | /// representation. However, it is unlikely that increasing this number |
2578 | /// will help things much, since the most active states have a small depth. |
2579 | /// More to the point, the memory usage increases superlinearly as this |
2580 | /// number increases. |
2581 | pub fn dense_depth(&mut self, depth: usize) -> &mut AhoCorasickBuilder { |
2582 | self.nfa_contiguous.dense_depth(depth); |
2583 | self |
2584 | } |
2585 | |
2586 | /// A debug settting for whether to attempt to shrink the size of the |
2587 | /// automaton's alphabet or not. |
2588 | /// |
2589 | /// This option is enabled by default and should never be disabled unless |
2590 | /// one is debugging the underlying automaton. |
2591 | /// |
2592 | /// When enabled, some (but not all) Aho-Corasick automatons will use a map |
2593 | /// from all possible bytes to their corresponding equivalence class. Each |
2594 | /// equivalence class represents a set of bytes that does not discriminate |
2595 | /// between a match and a non-match in the automaton. |
2596 | /// |
2597 | /// The advantage of this map is that the size of the transition table can |
2598 | /// be reduced drastically from `#states * 256 * sizeof(u32)` to |
2599 | /// `#states * k * sizeof(u32)` where `k` is the number of equivalence |
2600 | /// classes (rounded up to the nearest power of 2). As a result, total |
2601 | /// space usage can decrease substantially. Moreover, since a smaller |
2602 | /// alphabet is used, automaton compilation becomes faster as well. |
2603 | /// |
2604 | /// **WARNING:** This is only useful for debugging automatons. Disabling |
2605 | /// this does not yield any speed advantages. Namely, even when this is |
2606 | /// disabled, a byte class map is still used while searching. The only |
2607 | /// difference is that every byte will be forced into its own distinct |
2608 | /// equivalence class. This is useful for debugging the actual generated |
2609 | /// transitions because it lets one see the transitions defined on actual |
2610 | /// bytes instead of the equivalence classes. |
2611 | pub fn byte_classes(&mut self, yes: bool) -> &mut AhoCorasickBuilder { |
2612 | self.nfa_contiguous.byte_classes(yes); |
2613 | self.dfa.byte_classes(yes); |
2614 | self |
2615 | } |
2616 | } |
2617 | |
2618 | /// The type of Aho-Corasick implementation to use in an [`AhoCorasick`] |
2619 | /// searcher. |
2620 | /// |
2621 | /// This is principally used as an input to the |
2622 | /// [`AhoCorasickBuilder::start_kind`] method. Its documentation goes into more |
2623 | /// detail about each choice. |
2624 | #[non_exhaustive ] |
2625 | #[derive (Clone, Copy, Debug, Eq, PartialEq)] |
2626 | pub enum AhoCorasickKind { |
2627 | /// Use a noncontiguous NFA. |
2628 | NoncontiguousNFA, |
2629 | /// Use a contiguous NFA. |
2630 | ContiguousNFA, |
2631 | /// Use a DFA. Warning: DFAs typically use a large amount of memory. |
2632 | DFA, |
2633 | } |
2634 | |
2635 | /// A trait that effectively gives us practical dynamic dispatch over anything |
2636 | /// that impls `Automaton`, but without needing to add a bunch of bounds to |
2637 | /// the core `Automaton` trait. Basically, we provide all of the marker traits |
2638 | /// that our automatons have, in addition to `Debug` impls and requiring that |
2639 | /// there is no borrowed data. Without these, the main `AhoCorasick` type would |
2640 | /// not be able to meaningfully impl `Debug` or the marker traits without also |
2641 | /// requiring that all impls of `Automaton` do so, which would be not great. |
2642 | trait AcAutomaton: |
2643 | Automaton + Debug + Send + Sync + UnwindSafe + RefUnwindSafe + 'static |
2644 | { |
2645 | } |
2646 | |
2647 | impl<A> AcAutomaton for A where |
2648 | A: Automaton + Debug + Send + Sync + UnwindSafe + RefUnwindSafe + 'static |
2649 | { |
2650 | } |
2651 | |
2652 | impl crate::automaton::private::Sealed for Arc<dyn AcAutomaton> {} |
2653 | |
2654 | // I'm not sure why this trait impl shows up in the docs, as the AcAutomaton |
2655 | // trait is not exported. So we forcefully hide it. |
2656 | // |
2657 | // SAFETY: This just defers to the underlying 'AcAutomaton' and thus inherits |
2658 | // its safety properties. |
2659 | #[doc (hidden)] |
2660 | unsafe impl Automaton for Arc<dyn AcAutomaton> { |
2661 | #[inline (always)] |
2662 | fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError> { |
2663 | (**self).start_state(anchored) |
2664 | } |
2665 | |
2666 | #[inline (always)] |
2667 | fn next_state( |
2668 | &self, |
2669 | anchored: Anchored, |
2670 | sid: StateID, |
2671 | byte: u8, |
2672 | ) -> StateID { |
2673 | (**self).next_state(anchored, sid, byte) |
2674 | } |
2675 | |
2676 | #[inline (always)] |
2677 | fn is_special(&self, sid: StateID) -> bool { |
2678 | (**self).is_special(sid) |
2679 | } |
2680 | |
2681 | #[inline (always)] |
2682 | fn is_dead(&self, sid: StateID) -> bool { |
2683 | (**self).is_dead(sid) |
2684 | } |
2685 | |
2686 | #[inline (always)] |
2687 | fn is_match(&self, sid: StateID) -> bool { |
2688 | (**self).is_match(sid) |
2689 | } |
2690 | |
2691 | #[inline (always)] |
2692 | fn is_start(&self, sid: StateID) -> bool { |
2693 | (**self).is_start(sid) |
2694 | } |
2695 | |
2696 | #[inline (always)] |
2697 | fn match_kind(&self) -> MatchKind { |
2698 | (**self).match_kind() |
2699 | } |
2700 | |
2701 | #[inline (always)] |
2702 | fn match_len(&self, sid: StateID) -> usize { |
2703 | (**self).match_len(sid) |
2704 | } |
2705 | |
2706 | #[inline (always)] |
2707 | fn match_pattern(&self, sid: StateID, index: usize) -> PatternID { |
2708 | (**self).match_pattern(sid, index) |
2709 | } |
2710 | |
2711 | #[inline (always)] |
2712 | fn patterns_len(&self) -> usize { |
2713 | (**self).patterns_len() |
2714 | } |
2715 | |
2716 | #[inline (always)] |
2717 | fn pattern_len(&self, pid: PatternID) -> usize { |
2718 | (**self).pattern_len(pid) |
2719 | } |
2720 | |
2721 | #[inline (always)] |
2722 | fn min_pattern_len(&self) -> usize { |
2723 | (**self).min_pattern_len() |
2724 | } |
2725 | |
2726 | #[inline (always)] |
2727 | fn max_pattern_len(&self) -> usize { |
2728 | (**self).max_pattern_len() |
2729 | } |
2730 | |
2731 | #[inline (always)] |
2732 | fn memory_usage(&self) -> usize { |
2733 | (**self).memory_usage() |
2734 | } |
2735 | |
2736 | #[inline (always)] |
2737 | fn prefilter(&self) -> Option<&Prefilter> { |
2738 | (**self).prefilter() |
2739 | } |
2740 | |
2741 | // Even though 'try_find' and 'try_find_overlapping' each have their |
2742 | // own default impls, we explicitly define them here to fix a perf bug. |
2743 | // Without these explicit definitions, the default impl will wind up using |
2744 | // dynamic dispatch for all 'Automaton' method calls, including things like |
2745 | // 'next_state' that absolutely must get inlined or else perf is trashed. |
2746 | // Defining them explicitly here like this still requires dynamic dispatch |
2747 | // to call 'try_find' itself, but all uses of 'Automaton' within 'try_find' |
2748 | // are monomorphized. |
2749 | // |
2750 | // We don't need to explicitly impl any other methods, I think, because |
2751 | // they are all implemented themselves in terms of 'try_find' and |
2752 | // 'try_find_overlapping'. We still might wind up with an extra virtual |
2753 | // call here or there, but that's okay since it's outside of any perf |
2754 | // critical areas. |
2755 | |
2756 | #[inline (always)] |
2757 | fn try_find( |
2758 | &self, |
2759 | input: &Input<'_>, |
2760 | ) -> Result<Option<Match>, MatchError> { |
2761 | (**self).try_find(input) |
2762 | } |
2763 | |
2764 | #[inline (always)] |
2765 | fn try_find_overlapping( |
2766 | &self, |
2767 | input: &Input<'_>, |
2768 | state: &mut OverlappingState, |
2769 | ) -> Result<(), MatchError> { |
2770 | (**self).try_find_overlapping(input, state) |
2771 | } |
2772 | } |
2773 | |
2774 | /// Returns an error if the start state configuration does not support the |
2775 | /// desired search configuration. See the internal 'AhoCorasick::start_kind' |
2776 | /// field docs for more details. |
2777 | fn enforce_anchored_consistency( |
2778 | have: StartKind, |
2779 | want: Anchored, |
2780 | ) -> Result<(), MatchError> { |
2781 | match have { |
2782 | StartKind::Both => Ok(()), |
2783 | StartKind::Unanchored if !want.is_anchored() => Ok(()), |
2784 | StartKind::Unanchored => Err(MatchError::invalid_input_anchored()), |
2785 | StartKind::Anchored if want.is_anchored() => Ok(()), |
2786 | StartKind::Anchored => Err(MatchError::invalid_input_unanchored()), |
2787 | } |
2788 | } |
2789 | |