3 use automaton
::Automaton
;
9 use prefilter
::PrefilterState
;
10 use state_id
::StateID
;
13 /// An automaton for searching multiple strings in linear time.
15 /// The `AhoCorasick` type supports a few basic ways of constructing an
16 /// automaton, including
17 /// [`AhoCorasick::new`](struct.AhoCorasick.html#method.new)
19 /// [`AhoCorasick::new_auto_configured`](struct.AhoCorasick.html#method.new_auto_configured).
20 /// However, there are a fair number of configurable options that can be set
22 /// [`AhoCorasickBuilder`](struct.AhoCorasickBuilder.html)
23 /// instead. Such options include, but are not limited to, how matches are
24 /// determined, simple case insensitivity, whether to use a DFA or not and
25 /// various knobs for controlling the space-vs-time trade offs taken when
26 /// building the automaton.
28 /// If you aren't sure where to start, try beginning with
29 /// [`AhoCorasick::new_auto_configured`](struct.AhoCorasick.html#method.new_auto_configured).
33 /// Aho-Corasick automatons are always constructed in `O(p)` time, where `p`
34 /// is the combined length of all patterns being searched. With that said,
35 /// building an automaton can be fairly costly because of high constant
36 /// factors, particularly when enabling the
37 /// [DFA](struct.AhoCorasickBuilder.html#method.dfa)
38 /// option (which is disabled by default). For this reason, it's generally a
39 /// good idea to build an automaton once and reuse it as much as possible.
41 /// Aho-Corasick automatons can also use a fair bit of memory. To get a
42 /// concrete idea of how much memory is being used, try using the
43 /// [`AhoCorasick::heap_bytes`](struct.AhoCorasick.html#method.heap_bytes)
48 /// This example shows how to search for occurrences of multiple patterns
49 /// simultaneously in a case insensitive fashion. Each match includes the
50 /// pattern that matched along with the byte offsets of the match.
53 /// use aho_corasick::AhoCorasickBuilder;
55 /// let patterns = &["apple", "maple", "snapple"];
56 /// let haystack = "Nobody likes maple in their apple flavored Snapple.";
58 /// let ac = AhoCorasickBuilder::new()
59 /// .ascii_case_insensitive(true)
61 /// let mut matches = vec![];
62 /// for mat in ac.find_iter(haystack) {
63 /// matches.push((mat.pattern(), mat.start(), mat.end()));
65 /// assert_eq!(matches, vec![
72 /// This example shows how to replace matches with some other string:
75 /// use aho_corasick::AhoCorasick;
77 /// let patterns = &["fox", "brown", "quick"];
78 /// let haystack = "The quick brown fox.";
79 /// let replace_with = &["sloth", "grey", "slow"];
81 /// let ac = AhoCorasick::new(patterns);
82 /// let result = ac.replace_all(haystack, replace_with);
83 /// assert_eq!(result, "The slow grey sloth.");
85 #[derive(Clone, Debug)]
86 pub struct AhoCorasick
<S
: StateID
= usize> {
88 match_kind
: MatchKind
,
92 /// Create a new Aho-Corasick automaton using the default configuration.
94 /// The default configuration optimizes for less space usage, but at the
95 /// expense of longer search times. To change the configuration, use
96 /// [`AhoCorasickBuilder`](struct.AhoCorasickBuilder.html)
97 /// for fine-grained control, or
98 /// [`AhoCorasick::new_auto_configured`](struct.AhoCorasick.html#method.new_auto_configured)
99 /// for automatic configuration if you aren't sure which settings to pick.
101 /// This uses the default
102 /// [`MatchKind::Standard`](enum.MatchKind.html#variant.Standard)
103 /// match semantics, which reports a match as soon as it is found. This
104 /// corresponds to the standard match semantics supported by textbook
105 /// descriptions of the Aho-Corasick algorithm.
112 /// use aho_corasick::AhoCorasick;
114 /// let ac = AhoCorasick::new(&[
115 /// "foo", "bar", "baz",
117 /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
119 pub fn new
<I
, P
>(patterns
: I
) -> AhoCorasick
121 I
: IntoIterator
<Item
= P
>,
124 AhoCorasickBuilder
::new().build(patterns
)
127 /// Build an Aho-Corasick automaton with an automatically determined
130 /// Specifically, this requires a slice of patterns instead of an iterator
131 /// since the configuration is determined by looking at the patterns before
132 /// constructing the automaton. The idea here is to balance space and time
133 /// automatically. That is, when searching a small number of patterns, this
134 /// will attempt to use the fastest possible configuration since the total
135 /// space required will be small anyway. As the number of patterns grows,
136 /// this will fall back to slower configurations that use less space.
138 /// If you want auto configuration but with match semantics different from
139 /// the default `MatchKind::Standard`, then use
140 /// [`AhoCorasickBuilder::auto_configure`](struct.AhoCorasickBuilder.html#method.auto_configure).
144 /// Basic usage is just like `new`, except you must provide a slice:
147 /// use aho_corasick::AhoCorasick;
149 /// let ac = AhoCorasick::new_auto_configured(&[
150 /// "foo", "bar", "baz",
152 /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
154 pub fn new_auto_configured
<B
>(patterns
: &[B
]) -> AhoCorasick
158 AhoCorasickBuilder
::new().auto_configure(patterns
).build(patterns
)
162 impl<S
: StateID
> AhoCorasick
<S
> {
163 /// Returns true if and only if this automaton matches the haystack at any
166 /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
167 /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
175 /// use aho_corasick::AhoCorasick;
177 /// let ac = AhoCorasick::new(&[
178 /// "foo", "bar", "quux", "baz",
180 /// assert!(ac.is_match("xxx bar xxx"));
181 /// assert!(!ac.is_match("xxx qux xxx"));
183 pub fn is_match
<B
: AsRef
<[u8]>>(&self, haystack
: B
) -> bool
{
184 self.earliest_find(haystack
).is_some()
187 /// Returns the location of the first detected match in `haystack`.
189 /// This method has the same behavior regardless of the
190 /// [`MatchKind`](enum.MatchKind.html)
191 /// of this automaton.
193 /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
194 /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
202 /// use aho_corasick::AhoCorasick;
204 /// let ac = AhoCorasick::new(&[
207 /// let mat = ac.earliest_find("abcd").expect("should have match");
208 /// assert_eq!(1, mat.pattern());
209 /// assert_eq!((1, 2), (mat.start(), mat.end()));
211 pub fn earliest_find
<B
: AsRef
<[u8]>>(&self, haystack
: B
) -> Option
<Match
> {
212 let mut prestate
= PrefilterState
::new(self.max_pattern_len());
213 let mut start
= self.imp
.start_state();
214 self.imp
.earliest_find_at(
222 /// Returns the location of the first match according to the match
223 /// semantics that this automaton was constructed with.
225 /// When using `MatchKind::Standard`, this corresponds precisely to the
227 /// [`earliest_find`](struct.AhoCorasick.html#method.earliest_find).
228 /// Otherwise, match semantics correspond to either
229 /// [leftmost-first](enum.MatchKind.html#variant.LeftmostFirst)
231 /// [leftmost-longest](enum.MatchKind.html#variant.LeftmostLongest).
233 /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
234 /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
239 /// Basic usage, with standard semantics:
242 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
244 /// let patterns = &["b", "abc", "abcd"];
245 /// let haystack = "abcd";
247 /// let ac = AhoCorasickBuilder::new()
248 /// .match_kind(MatchKind::Standard) // default, not necessary
249 /// .build(patterns);
250 /// let mat = ac.find(haystack).expect("should have a match");
251 /// assert_eq!("b", &haystack[mat.start()..mat.end()]);
254 /// Now with leftmost-first semantics:
257 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
259 /// let patterns = &["b", "abc", "abcd"];
260 /// let haystack = "abcd";
262 /// let ac = AhoCorasickBuilder::new()
263 /// .match_kind(MatchKind::LeftmostFirst)
264 /// .build(patterns);
265 /// let mat = ac.find(haystack).expect("should have a match");
266 /// assert_eq!("abc", &haystack[mat.start()..mat.end()]);
269 /// And finally, leftmost-longest semantics:
272 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
274 /// let patterns = &["b", "abc", "abcd"];
275 /// let haystack = "abcd";
277 /// let ac = AhoCorasickBuilder::new()
278 /// .match_kind(MatchKind::LeftmostLongest)
279 /// .build(patterns);
280 /// let mat = ac.find(haystack).expect("should have a match");
281 /// assert_eq!("abcd", &haystack[mat.start()..mat.end()]);
283 pub fn find
<B
: AsRef
<[u8]>>(&self, haystack
: B
) -> Option
<Match
> {
284 let mut prestate
= PrefilterState
::new(self.max_pattern_len());
285 self.imp
.find_at_no_state(&mut prestate
, haystack
.as_ref(), 0)
288 /// Returns an iterator of non-overlapping matches, using the match
289 /// semantics that this automaton was constructed with.
291 /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
292 /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
297 /// Basic usage, with standard semantics:
300 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
302 /// let patterns = &["append", "appendage", "app"];
303 /// let haystack = "append the app to the appendage";
305 /// let ac = AhoCorasickBuilder::new()
306 /// .match_kind(MatchKind::Standard) // default, not necessary
307 /// .build(patterns);
308 /// let matches: Vec<usize> = ac
309 /// .find_iter(haystack)
310 /// .map(|mat| mat.pattern())
312 /// assert_eq!(vec![2, 2, 2], matches);
315 /// Now with leftmost-first semantics:
318 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
320 /// let patterns = &["append", "appendage", "app"];
321 /// let haystack = "append the app to the appendage";
323 /// let ac = AhoCorasickBuilder::new()
324 /// .match_kind(MatchKind::LeftmostFirst)
325 /// .build(patterns);
326 /// let matches: Vec<usize> = ac
327 /// .find_iter(haystack)
328 /// .map(|mat| mat.pattern())
330 /// assert_eq!(vec![0, 2, 0], matches);
333 /// And finally, leftmost-longest semantics:
336 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
338 /// let patterns = &["append", "appendage", "app"];
339 /// let haystack = "append the app to the appendage";
341 /// let ac = AhoCorasickBuilder::new()
342 /// .match_kind(MatchKind::LeftmostLongest)
343 /// .build(patterns);
344 /// let matches: Vec<usize> = ac
345 /// .find_iter(haystack)
346 /// .map(|mat| mat.pattern())
348 /// assert_eq!(vec![0, 2, 1], matches);
350 pub fn find_iter
<'a
, 'b
, B
: ?Sized
+ AsRef
<[u8]>>(
353 ) -> FindIter
<'a
, 'b
, S
> {
354 FindIter
::new(self, haystack
.as_ref())
357 /// Returns an iterator of overlapping matches in the given `haystack`.
359 /// Overlapping matches can _only_ be detected using
360 /// `MatchKind::Standard` semantics. If this automaton was constructed with
361 /// leftmost semantics, then this method will panic. To determine whether
362 /// this will panic at runtime, use the
363 /// [`AhoCorasick::supports_overlapping`](struct.AhoCorasick.html#method.supports_overlapping)
366 /// `haystack` may be any type that is cheaply convertible to a `&[u8]`.
367 /// This includes, but is not limited to, `String`, `&str`, `Vec<u8>`, and
372 /// This panics when `AhoCorasick::supports_overlapping` returns `false`.
373 /// That is, this panics when this automaton's match semantics are not
374 /// `MatchKind::Standard`.
378 /// Basic usage, with standard semantics:
381 /// use aho_corasick::AhoCorasick;
383 /// let patterns = &["append", "appendage", "app"];
384 /// let haystack = "append the app to the appendage";
386 /// let ac = AhoCorasick::new(patterns);
387 /// let matches: Vec<usize> = ac
388 /// .find_overlapping_iter(haystack)
389 /// .map(|mat| mat.pattern())
391 /// assert_eq!(vec![2, 0, 2, 2, 0, 1], matches);
393 pub fn find_overlapping_iter
<'a
, 'b
, B
: ?Sized
+ AsRef
<[u8]>>(
396 ) -> FindOverlappingIter
<'a
, 'b
, S
> {
397 FindOverlappingIter
::new(self, haystack
.as_ref())
400 /// Replace all matches with a corresponding value in the `replace_with`
401 /// slice given. Matches correspond to the same matches as reported by
402 /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
404 /// Replacements are determined by the index of the matching pattern.
405 /// For example, if the pattern with index `2` is found, then it is
406 /// replaced by `replace_with[2]`.
410 /// This panics when `replace_with.len()` does not equal the total number
411 /// of patterns that are matched by this automaton.
418 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
420 /// let patterns = &["append", "appendage", "app"];
421 /// let haystack = "append the app to the appendage";
423 /// let ac = AhoCorasickBuilder::new()
424 /// .match_kind(MatchKind::LeftmostFirst)
425 /// .build(patterns);
426 /// let result = ac.replace_all(haystack, &["x", "y", "z"]);
427 /// assert_eq!("x the z to the xage", result);
429 pub fn replace_all
<B
>(&self, haystack
: &str, replace_with
: &[B
]) -> String
435 self.pattern_count(),
436 "replace_all requires a replacement for every pattern \
439 let mut dst
= String
::with_capacity(haystack
.len());
440 self.replace_all_with(haystack
, &mut dst
, |mat
, _
, dst
| {
441 dst
.push_str(replace_with
[mat
.pattern()].as_ref());
447 /// Replace all matches using raw bytes with a corresponding value in the
448 /// `replace_with` slice given. Matches correspond to the same matches as
449 /// reported by [`find_iter`](struct.AhoCorasick.html#method.find_iter).
451 /// Replacements are determined by the index of the matching pattern.
452 /// For example, if the pattern with index `2` is found, then it is
453 /// replaced by `replace_with[2]`.
457 /// This panics when `replace_with.len()` does not equal the total number
458 /// of patterns that are matched by this automaton.
465 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
467 /// let patterns = &["append", "appendage", "app"];
468 /// let haystack = b"append the app to the appendage";
470 /// let ac = AhoCorasickBuilder::new()
471 /// .match_kind(MatchKind::LeftmostFirst)
472 /// .build(patterns);
473 /// let result = ac.replace_all_bytes(haystack, &["x", "y", "z"]);
474 /// assert_eq!(b"x the z to the xage".to_vec(), result);
476 pub fn replace_all_bytes
<B
>(
486 self.pattern_count(),
487 "replace_all_bytes requires a replacement for every pattern \
490 let mut dst
= Vec
::with_capacity(haystack
.len());
491 self.replace_all_with_bytes(haystack
, &mut dst
, |mat
, _
, dst
| {
492 dst
.extend(replace_with
[mat
.pattern()].as_ref());
498 /// Replace all matches using a closure called on each match.
499 /// Matches correspond to the same matches as reported by
500 /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
502 /// The closure accepts three parameters: the match found, the text of
503 /// the match and a string buffer with which to write the replaced text
504 /// (if any). If the closure returns `true`, then it continues to the next
505 /// match. If the closure returns false, then searching is stopped.
512 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
514 /// let patterns = &["append", "appendage", "app"];
515 /// let haystack = "append the app to the appendage";
517 /// let ac = AhoCorasickBuilder::new()
518 /// .match_kind(MatchKind::LeftmostFirst)
519 /// .build(patterns);
520 /// let mut result = String::new();
521 /// ac.replace_all_with(haystack, &mut result, |mat, _, dst| {
522 /// dst.push_str(&mat.pattern().to_string());
525 /// assert_eq!("0 the 2 to the 0age", result);
527 pub fn replace_all_with
<F
>(
533 F
: FnMut(&Match
, &str, &mut String
) -> bool
,
535 let mut last_match
= 0;
536 for mat
in self.find_iter(haystack
) {
537 dst
.push_str(&haystack
[last_match
..mat
.start()]);
538 last_match
= mat
.end();
539 replace_with(&mat
, &haystack
[mat
.start()..mat
.end()], dst
);
541 dst
.push_str(&haystack
[last_match
..]);
544 /// Replace all matches using raw bytes with a closure called on each
545 /// match. Matches correspond to the same matches as reported by
546 /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
548 /// The closure accepts three parameters: the match found, the text of
549 /// the match and a byte buffer with which to write the replaced text
550 /// (if any). If the closure returns `true`, then it continues to the next
551 /// match. If the closure returns false, then searching is stopped.
558 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
560 /// let patterns = &["append", "appendage", "app"];
561 /// let haystack = b"append the app to the appendage";
563 /// let ac = AhoCorasickBuilder::new()
564 /// .match_kind(MatchKind::LeftmostFirst)
565 /// .build(patterns);
566 /// let mut result = vec![];
567 /// ac.replace_all_with_bytes(haystack, &mut result, |mat, _, dst| {
568 /// dst.extend(mat.pattern().to_string().bytes());
571 /// assert_eq!(b"0 the 2 to the 0age".to_vec(), result);
573 pub fn replace_all_with_bytes
<F
>(
579 F
: FnMut(&Match
, &[u8], &mut Vec
<u8>) -> bool
,
581 let mut last_match
= 0;
582 for mat
in self.find_iter(haystack
) {
583 dst
.extend(&haystack
[last_match
..mat
.start()]);
584 last_match
= mat
.end();
585 replace_with(&mat
, &haystack
[mat
.start()..mat
.end()], dst
);
587 dst
.extend(&haystack
[last_match
..]);
590 /// Returns an iterator of non-overlapping matches in the given
591 /// stream. Matches correspond to the same matches as reported by
592 /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
594 /// The matches yielded by this iterator use absolute position offsets in
595 /// the stream given, where the first byte has index `0`. Matches are
596 /// yieled until the stream is exhausted.
598 /// Each item yielded by the iterator is an `io::Result<Match>`, where an
599 /// error is yielded if there was a problem reading from the reader given.
601 /// When searching a stream, an internal buffer is used. Therefore, callers
602 /// should avoiding providing a buffered reader, if possible.
604 /// Searching a stream requires that the automaton was built with
605 /// `MatchKind::Standard` semantics. If this automaton was constructed
606 /// with leftmost semantics, then this method will panic. To determine
607 /// whether this will panic at runtime, use the
608 /// [`AhoCorasick::supports_stream`](struct.AhoCorasick.html#method.supports_stream)
613 /// In general, searching streams will use a constant amount of memory for
614 /// its internal buffer. The one requirement is that the internal buffer
615 /// must be at least the size of the longest possible match. In most use
616 /// cases, the default buffer size will be much larger than any individual
621 /// This panics when `AhoCorasick::supports_stream` returns `false`.
622 /// That is, this panics when this automaton's match semantics are not
623 /// `MatchKind::Standard`. This restriction may be lifted in the future.
630 /// use aho_corasick::AhoCorasick;
632 /// # fn example() -> Result<(), ::std::io::Error> {
633 /// let patterns = &["append", "appendage", "app"];
634 /// let haystack = "append the app to the appendage";
636 /// let ac = AhoCorasick::new(patterns);
637 /// let mut matches = vec![];
638 /// for result in ac.stream_find_iter(haystack.as_bytes()) {
639 /// let mat = result?;
640 /// matches.push(mat.pattern());
642 /// assert_eq!(vec![2, 2, 2], matches);
643 /// # Ok(()) }; example().unwrap()
645 pub fn stream_find_iter
<'a
, R
: io
::Read
>(
648 ) -> StreamFindIter
<'a
, R
, S
> {
649 StreamFindIter
::new(self, rdr
)
652 /// Search for and replace all matches of this automaton in
653 /// the given reader, and write the replacements to the given
654 /// writer. Matches correspond to the same matches as reported by
655 /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
657 /// Replacements are determined by the index of the matching pattern.
658 /// For example, if the pattern with index `2` is found, then it is
659 /// replaced by `replace_with[2]`.
661 /// After all matches are replaced, the writer is _not_ flushed.
663 /// If there was a problem reading from the given reader or writing to the
664 /// given writer, then the corresponding `io::Error` is returned and all
665 /// replacement is stopped.
667 /// When searching a stream, an internal buffer is used. Therefore, callers
668 /// should avoiding providing a buffered reader, if possible. However,
669 /// callers may want to provide a buffered writer.
671 /// Searching a stream requires that the automaton was built with
672 /// `MatchKind::Standard` semantics. If this automaton was constructed
673 /// with leftmost semantics, then this method will panic. To determine
674 /// whether this will panic at runtime, use the
675 /// [`AhoCorasick::supports_stream`](struct.AhoCorasick.html#method.supports_stream)
680 /// In general, searching streams will use a constant amount of memory for
681 /// its internal buffer. The one requirement is that the internal buffer
682 /// must be at least the size of the longest possible match. In most use
683 /// cases, the default buffer size will be much larger than any individual
688 /// This panics when `AhoCorasick::supports_stream` returns `false`.
689 /// That is, this panics when this automaton's match semantics are not
690 /// `MatchKind::Standard`. This restriction may be lifted in the future.
697 /// use aho_corasick::AhoCorasick;
699 /// # fn example() -> Result<(), ::std::io::Error> {
700 /// let patterns = &["fox", "brown", "quick"];
701 /// let haystack = "The quick brown fox.";
702 /// let replace_with = &["sloth", "grey", "slow"];
704 /// let ac = AhoCorasick::new(patterns);
705 /// let mut result = vec![];
706 /// ac.stream_replace_all(haystack.as_bytes(), &mut result, replace_with)?;
707 /// assert_eq!(b"The slow grey sloth.".to_vec(), result);
708 /// # Ok(()) }; example().unwrap()
710 pub fn stream_replace_all
<R
, W
, B
>(
723 self.pattern_count(),
724 "stream_replace_all requires a replacement for every pattern \
727 self.stream_replace_all_with(rdr
, wtr
, |mat
, _
, wtr
| {
728 wtr
.write_all(replace_with
[mat
.pattern()].as_ref())
732 /// Search the given reader and replace all matches of this automaton
733 /// using the given closure. The result is written to the given
734 /// writer. Matches correspond to the same matches as reported by
735 /// [`find_iter`](struct.AhoCorasick.html#method.find_iter).
737 /// The closure accepts three parameters: the match found, the text of
738 /// the match and the writer with which to write the replaced text
739 /// (if any). If the closure returns `true`, then it continues to the next
740 /// match. If the closure returns false, then searching is stopped.
742 /// After all matches are replaced, the writer is _not_ flushed.
744 /// If there was a problem reading from the given reader or writing to the
745 /// given writer, then the corresponding `io::Error` is returned and all
746 /// replacement is stopped.
748 /// When searching a stream, an internal buffer is used. Therefore, callers
749 /// should avoiding providing a buffered reader, if possible. However,
750 /// callers may want to provide a buffered writer.
752 /// Searching a stream requires that the automaton was built with
753 /// `MatchKind::Standard` semantics. If this automaton was constructed
754 /// with leftmost semantics, then this method will panic. To determine
755 /// whether this will panic at runtime, use the
756 /// [`AhoCorasick::supports_stream`](struct.AhoCorasick.html#method.supports_stream)
761 /// In general, searching streams will use a constant amount of memory for
762 /// its internal buffer. The one requirement is that the internal buffer
763 /// must be at least the size of the longest possible match. In most use
764 /// cases, the default buffer size will be much larger than any individual
769 /// This panics when `AhoCorasick::supports_stream` returns `false`.
770 /// That is, this panics when this automaton's match semantics are not
771 /// `MatchKind::Standard`. This restriction may be lifted in the future.
778 /// use std::io::Write;
779 /// use aho_corasick::AhoCorasick;
781 /// # fn example() -> Result<(), ::std::io::Error> {
782 /// let patterns = &["fox", "brown", "quick"];
783 /// let haystack = "The quick brown fox.";
785 /// let ac = AhoCorasick::new(patterns);
786 /// let mut result = vec![];
787 /// ac.stream_replace_all_with(
788 /// haystack.as_bytes(),
791 /// wtr.write_all(mat.pattern().to_string().as_bytes())
794 /// assert_eq!(b"The 2 1 0.".to_vec(), result);
795 /// # Ok(()) }; example().unwrap()
797 pub fn stream_replace_all_with
<R
, W
, F
>(
806 F
: FnMut(&Match
, &[u8], &mut W
) -> io
::Result
<()>,
808 let mut it
= StreamChunkIter
::new(self, rdr
);
809 while let Some(result
) = it
.next() {
812 StreamChunk
::NonMatch { bytes, .. }
=> {
813 wtr
.write_all(bytes
)?
;
815 StreamChunk
::Match { bytes, mat }
=> {
816 replace_with(&mat
, bytes
, &mut wtr
)?
;
823 /// Returns the match kind used by this automaton.
830 /// use aho_corasick::{AhoCorasick, MatchKind};
832 /// let ac = AhoCorasick::new(&[
833 /// "foo", "bar", "quux", "baz",
835 /// assert_eq!(&MatchKind::Standard, ac.match_kind());
837 pub fn match_kind(&self) -> &MatchKind
{
838 self.imp
.match_kind()
841 /// Returns the length of the longest pattern matched by this automaton.
848 /// use aho_corasick::AhoCorasick;
850 /// let ac = AhoCorasick::new(&[
851 /// "foo", "bar", "quux", "baz",
853 /// assert_eq!(4, ac.max_pattern_len());
855 pub fn max_pattern_len(&self) -> usize {
856 self.imp
.max_pattern_len()
859 /// Return the total number of patterns matched by this automaton.
861 /// This includes patterns that may never participate in a match. For
863 /// [`MatchKind::LeftmostFirst`](enum.MatchKind.html#variant.LeftmostFirst)
864 /// match semantics are used, and the patterns `Sam` and `Samwise` were
865 /// used to build the automaton, then `Samwise` can never participate in a
866 /// match because `Sam` will always take priority.
873 /// use aho_corasick::AhoCorasick;
875 /// let ac = AhoCorasick::new(&[
876 /// "foo", "bar", "baz",
878 /// assert_eq!(3, ac.pattern_count());
880 pub fn pattern_count(&self) -> usize {
881 self.imp
.pattern_count()
884 /// Returns true if and only if this automaton supports reporting
885 /// overlapping matches.
887 /// If this returns false and overlapping matches are requested, then it
888 /// will result in a panic.
890 /// Since leftmost matching is inherently incompatible with overlapping
892 /// [`MatchKind::Standard`](enum.MatchKind.html#variant.Standard)
893 /// supports overlapping matches. This is unlikely to change in the future.
900 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
902 /// let ac = AhoCorasickBuilder::new()
903 /// .match_kind(MatchKind::Standard)
904 /// .build(&["foo", "bar", "baz"]);
905 /// assert!(ac.supports_overlapping());
907 /// let ac = AhoCorasickBuilder::new()
908 /// .match_kind(MatchKind::LeftmostFirst)
909 /// .build(&["foo", "bar", "baz"]);
910 /// assert!(!ac.supports_overlapping());
912 pub fn supports_overlapping(&self) -> bool
{
913 self.match_kind
.supports_overlapping()
916 /// Returns true if and only if this automaton supports stream searching.
918 /// If this returns false and stream searching (or replacing) is attempted,
919 /// then it will result in a panic.
922 /// [`MatchKind::Standard`](enum.MatchKind.html#variant.Standard)
923 /// supports streaming. This may be expanded in the future.
930 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
932 /// let ac = AhoCorasickBuilder::new()
933 /// .match_kind(MatchKind::Standard)
934 /// .build(&["foo", "bar", "baz"]);
935 /// assert!(ac.supports_stream());
937 /// let ac = AhoCorasickBuilder::new()
938 /// .match_kind(MatchKind::LeftmostFirst)
939 /// .build(&["foo", "bar", "baz"]);
940 /// assert!(!ac.supports_stream());
942 pub fn supports_stream(&self) -> bool
{
943 self.match_kind
.supports_stream()
946 /// Returns the approximate total amount of heap used by this automaton, in
951 /// This example shows the difference in heap usage between a few
955 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
957 /// let ac = AhoCorasickBuilder::new()
958 /// .dfa(false) // default
959 /// .build(&["foo", "bar", "baz"]);
960 /// assert_eq!(10_336, ac.heap_bytes());
962 /// let ac = AhoCorasickBuilder::new()
963 /// .dfa(false) // default
964 /// .ascii_case_insensitive(true)
965 /// .build(&["foo", "bar", "baz"]);
966 /// assert_eq!(10_384, ac.heap_bytes());
968 /// let ac = AhoCorasickBuilder::new()
970 /// .byte_classes(false)
971 /// .build(&["foo", "bar", "baz"]);
972 /// assert_eq!(20_768, ac.heap_bytes());
974 /// let ac = AhoCorasickBuilder::new()
976 /// .byte_classes(true) // default
977 /// .build(&["foo", "bar", "baz"]);
978 /// assert_eq!(1_248, ac.heap_bytes());
980 /// let ac = AhoCorasickBuilder::new()
982 /// .ascii_case_insensitive(true)
983 /// .build(&["foo", "bar", "baz"]);
984 /// assert_eq!(1_248, ac.heap_bytes());
986 pub fn heap_bytes(&self) -> usize {
988 Imp
::NFA(ref nfa
) => nfa
.heap_bytes(),
989 Imp
::DFA(ref dfa
) => dfa
.heap_bytes(),
994 /// The internal implementation of Aho-Corasick, which is either an NFA or
995 /// a DFA. The NFA is slower but uses less memory. The DFA is faster but uses
997 #[derive(Clone, Debug)]
998 enum Imp
<S
: StateID
> {
1003 impl<S
: StateID
> Imp
<S
> {
1004 /// Returns the type of match semantics implemented by this automaton.
1005 fn match_kind(&self) -> &MatchKind
{
1007 Imp
::NFA(ref nfa
) => nfa
.match_kind(),
1008 Imp
::DFA(ref dfa
) => dfa
.match_kind(),
1012 /// Returns the identifier of the start state.
1013 fn start_state(&self) -> S
{
1015 Imp
::NFA(ref nfa
) => nfa
.start_state(),
1016 Imp
::DFA(ref dfa
) => dfa
.start_state(),
1020 /// The length, in bytes, of the longest pattern in this automaton. This
1021 /// information is useful for maintaining correct buffer sizes when
1022 /// searching on streams.
1023 fn max_pattern_len(&self) -> usize {
1025 Imp
::NFA(ref nfa
) => nfa
.max_pattern_len(),
1026 Imp
::DFA(ref dfa
) => dfa
.max_pattern_len(),
1030 /// The total number of patterns added to this automaton. This includes
1031 /// patterns that may never match. The maximum matching pattern that can be
1032 /// reported is exactly one less than this number.
1033 fn pattern_count(&self) -> usize {
1035 Imp
::NFA(ref nfa
) => nfa
.pattern_count(),
1036 Imp
::DFA(ref dfa
) => dfa
.pattern_count(),
1041 fn overlapping_find_at(
1043 prestate
: &mut PrefilterState
,
1047 match_index
: &mut usize,
1048 ) -> Option
<Match
> {
1050 Imp
::NFA(ref nfa
) => nfa
.overlapping_find_at(
1057 Imp
::DFA(ref dfa
) => dfa
.overlapping_find_at(
1068 fn earliest_find_at(
1070 prestate
: &mut PrefilterState
,
1074 ) -> Option
<Match
> {
1076 Imp
::NFA(ref nfa
) => {
1077 nfa
.earliest_find_at(prestate
, haystack
, at
, state_id
)
1079 Imp
::DFA(ref dfa
) => {
1080 dfa
.earliest_find_at(prestate
, haystack
, at
, state_id
)
1086 fn find_at_no_state(
1088 prestate
: &mut PrefilterState
,
1091 ) -> Option
<Match
> {
1093 Imp
::NFA(ref nfa
) => nfa
.find_at_no_state(prestate
, haystack
, at
),
1094 Imp
::DFA(ref dfa
) => dfa
.find_at_no_state(prestate
, haystack
, at
),
1099 /// An iterator of non-overlapping matches in a particular haystack.
1101 /// This iterator yields matches according to the
1102 /// [`MatchKind`](enum.MatchKind.html)
1103 /// used by this automaton.
1105 /// This iterator is constructed via the
1106 /// [`AhoCorasick::find_iter`](struct.AhoCorasick.html#method.find_iter)
1109 /// The type variable `S` refers to the representation used for state
1110 /// identifiers. (By default, this is `usize`.)
1112 /// The lifetime `'a` refers to the lifetime of the `AhoCorasick` automaton.
1114 /// The lifetime `'b` refers to the lifetime of the haystack being searched.
1116 pub struct FindIter
<'a
, 'b
, S
: 'a
+ StateID
> {
1118 prestate
: PrefilterState
,
1123 impl<'a
, 'b
, S
: StateID
> FindIter
<'a
, 'b
, S
> {
1124 fn new(ac
: &'a AhoCorasick
<S
>, haystack
: &'b
[u8]) -> FindIter
<'a
, 'b
, S
> {
1125 let prestate
= PrefilterState
::new(ac
.max_pattern_len());
1126 FindIter { fsm: &ac.imp, prestate, haystack, pos: 0 }
1130 impl<'a
, 'b
, S
: StateID
> Iterator
for FindIter
<'a
, 'b
, S
> {
1133 fn next(&mut self) -> Option
<Match
> {
1134 if self.pos
> self.haystack
.len() {
1137 let result
= self.fsm
.find_at_no_state(
1142 let mat
= match result
{
1143 None
=> return None
,
1146 if mat
.end() == self.pos
{
1147 // If the automaton can match the empty string and if we found an
1148 // empty match, then we need to forcefully move the position.
1151 self.pos
= mat
.end();
1157 /// An iterator of overlapping matches in a particular haystack.
1159 /// This iterator will report all possible matches in a particular haystack,
1160 /// even when the matches overlap.
1162 /// This iterator is constructed via the
1163 /// [`AhoCorasick::find_overlapping_iter`](struct.AhoCorasick.html#method.find_overlapping_iter)
1166 /// The type variable `S` refers to the representation used for state
1167 /// identifiers. (By default, this is `usize`.)
1169 /// The lifetime `'a` refers to the lifetime of the `AhoCorasick` automaton.
1171 /// The lifetime `'b` refers to the lifetime of the haystack being searched.
1173 pub struct FindOverlappingIter
<'a
, 'b
, S
: 'a
+ StateID
> {
1175 prestate
: PrefilterState
,
1178 last_match_end
: usize,
1183 impl<'a
, 'b
, S
: StateID
> FindOverlappingIter
<'a
, 'b
, S
> {
1185 ac
: &'a AhoCorasick
<S
>,
1187 ) -> FindOverlappingIter
<'a
, 'b
, S
> {
1189 ac
.supports_overlapping(),
1190 "automaton does not support overlapping searches"
1192 let prestate
= PrefilterState
::new(ac
.max_pattern_len());
1193 FindOverlappingIter
{
1199 state_id
: ac
.imp
.start_state(),
1205 impl<'a
, 'b
, S
: StateID
> Iterator
for FindOverlappingIter
<'a
, 'b
, S
> {
1208 fn next(&mut self) -> Option
<Match
> {
1209 let result
= self.fsm
.overlapping_find_at(
1214 &mut self.match_index
,
1217 None
=> return None
,
1226 /// An iterator that reports Aho-Corasick matches in a stream.
1228 /// This iterator yields elements of type `io::Result<Match>`, where an error
1229 /// is reported if there was a problem reading from the underlying stream.
1230 /// The iterator terminates only when the underlying stream reaches `EOF`.
1232 /// This iterator is constructed via the
1233 /// [`AhoCorasick::stream_find_iter`](struct.AhoCorasick.html#method.stream_find_iter)
1236 /// The type variable `R` refers to the `io::Read` stream that is being read
1239 /// The type variable `S` refers to the representation used for state
1240 /// identifiers. (By default, this is `usize`.)
1242 /// The lifetime `'a` refers to the lifetime of the `AhoCorasick` automaton.
1244 pub struct StreamFindIter
<'a
, R
, S
: 'a
+ StateID
> {
1245 it
: StreamChunkIter
<'a
, R
, S
>,
1248 impl<'a
, R
: io
::Read
, S
: StateID
> StreamFindIter
<'a
, R
, S
> {
1249 fn new(ac
: &'a AhoCorasick
<S
>, rdr
: R
) -> StreamFindIter
<'a
, R
, S
> {
1250 StreamFindIter { it: StreamChunkIter::new(ac, rdr) }
1254 impl<'a
, R
: io
::Read
, S
: StateID
> Iterator
for StreamFindIter
<'a
, R
, S
> {
1255 type Item
= io
::Result
<Match
>;
1257 fn next(&mut self) -> Option
<io
::Result
<Match
>> {
1259 match self.it
.next() {
1260 None
=> return None
,
1261 Some(Err(err
)) => return Some(Err(err
)),
1262 Some(Ok(StreamChunk
::NonMatch { .. }
)) => {}
1263 Some(Ok(StreamChunk
::Match { mat, .. }
)) => {
1264 return Some(Ok(mat
));
1271 /// An iterator over chunks in an underlying reader. Each chunk either
1272 /// corresponds to non-matching bytes or matching bytes, but all bytes from
1273 /// the underlying reader are reported in sequence. There may be an arbitrary
1274 /// number of non-matching chunks before seeing a matching chunk.
1276 /// N.B. This does not actually implement Iterator because we need to borrow
1277 /// from the underlying reader. But conceptually, it's still an iterator.
1279 struct StreamChunkIter
<'a
, R
, S
: 'a
+ StateID
> {
1280 /// The AC automaton.
1282 /// State associated with this automaton's prefilter. It is a heuristic
1283 /// for stopping the prefilter if it's deemed ineffective.
1284 prestate
: PrefilterState
,
1285 /// The source of bytes we read from.
1287 /// A fixed size buffer. This is what we actually search. There are some
1288 /// invariants around the buffer's size, namely, it must be big enough to
1289 /// contain the longest possible match.
1291 /// The ID of the FSM state we're currently in.
1293 /// The current position at which to start the next search in `buf`.
1295 /// The absolute position of `search_pos`, where `0` corresponds to the
1296 /// position of the first byte read from `rdr`.
1297 absolute_pos
: usize,
1298 /// The ending position of the last StreamChunk that was returned to the
1299 /// caller. This position is used to determine whether we need to emit
1300 /// non-matching bytes before emitting a match.
1302 /// A match that should be reported on the next call.
1303 pending_match
: Option
<Match
>,
1304 /// Enabled only when the automaton can match the empty string. When
1305 /// enabled, we need to execute one final search after consuming the
1306 /// reader to find the trailing empty match.
1307 has_empty_match_at_end
: bool
,
1310 /// A single chunk yielded by the stream chunk iterator.
1312 /// The `'r` lifetime refers to the lifetime of the stream chunk iterator.
1314 enum StreamChunk
<'r
> {
1315 /// A chunk that does not contain any matches.
1316 NonMatch { bytes: &'r [u8], start: usize }
,
1317 /// A chunk that precisely contains a match.
1318 Match { bytes: &'r [u8], mat: Match }
,
1321 impl<'a
, R
: io
::Read
, S
: StateID
> StreamChunkIter
<'a
, R
, S
> {
1322 fn new(ac
: &'a AhoCorasick
<S
>, rdr
: R
) -> StreamChunkIter
<'a
, R
, S
> {
1324 ac
.supports_stream(),
1325 "stream searching is only supported for Standard match semantics"
1328 let prestate
= PrefilterState
::new(ac
.max_pattern_len());
1329 let buf
= Buffer
::new(ac
.imp
.max_pattern_len());
1330 let state_id
= ac
.imp
.start_state();
1340 pending_match
: None
,
1341 has_empty_match_at_end
: ac
.is_match(""),
1345 fn next
<'r
>(&'r
mut self) -> Option
<io
::Result
<StreamChunk
<'r
>>> {
1347 if let Some(mut mat
) = self.pending_match
.take() {
1348 let bytes
= &self.buf
.buffer()[mat
.start()..mat
.end()];
1349 self.report_pos
= mat
.end();
1350 mat
= mat
.increment(self.absolute_pos
);
1351 return Some(Ok(StreamChunk
::Match { bytes, mat }
));
1353 if self.search_pos
>= self.buf
.len() {
1354 if let Some(end
) = self.unreported() {
1355 let bytes
= &self.buf
.buffer()[self.report_pos
..end
];
1356 let start
= self.absolute_pos
+ self.report_pos
;
1357 self.report_pos
= end
;
1358 return Some(Ok(StreamChunk
::NonMatch { bytes, start }
));
1360 if self.buf
.len() >= self.buf
.min_buffer_len() {
1361 // This is the point at which we roll our buffer, which we
1362 // only do if our buffer has at least the minimum amount of
1363 // bytes in it. Before rolling, we update our various
1364 // positions to be consistent with the buffer after it has
1368 self.buf
.len() - self.buf
.min_buffer_len();
1369 self.absolute_pos
+=
1370 self.search_pos
- self.buf
.min_buffer_len();
1371 self.search_pos
= self.buf
.min_buffer_len();
1374 match self.buf
.fill(&mut self.rdr
) {
1375 Err(err
) => return Some(Err(err
)),
1377 // We've hit EOF, but if there are still some
1378 // unreported bytes remaining, return them now.
1379 if self.report_pos
< self.buf
.len() {
1380 let bytes
= &self.buf
.buffer()[self.report_pos
..];
1381 let start
= self.absolute_pos
+ self.report_pos
;
1382 self.report_pos
= self.buf
.len();
1384 let chunk
= StreamChunk
::NonMatch { bytes, start }
;
1385 return Some(Ok(chunk
));
1387 // We've reported everything, but there might still
1388 // be a match at the very last position.
1389 if !self.has_empty_match_at_end
{
1392 // fallthrough for another search to get trailing
1394 self.has_empty_match_at_end
= false;
1400 let result
= self.fsm
.earliest_find_at(
1408 self.search_pos
= self.buf
.len();
1411 self.state_id
= self.fsm
.start_state();
1412 if mat
.end() == self.search_pos
{
1413 // If the automaton can match the empty string and if
1414 // we found an empty match, then we need to forcefully
1415 // move the position.
1416 self.search_pos
+= 1;
1418 self.search_pos
= mat
.end();
1420 self.pending_match
= Some(mat
.clone());
1421 if self.report_pos
< mat
.start() {
1423 &self.buf
.buffer()[self.report_pos
..mat
.start()];
1424 let start
= self.absolute_pos
+ self.report_pos
;
1425 self.report_pos
= mat
.start();
1427 let chunk
= StreamChunk
::NonMatch { bytes, start }
;
1428 return Some(Ok(chunk
));
1435 fn unreported(&self) -> Option
<usize> {
1436 let end
= self.search_pos
.saturating_sub(self.buf
.min_buffer_len());
1437 if self.report_pos
< end
{
1445 /// A builder for configuring an Aho-Corasick automaton.
1446 #[derive(Clone, Debug)]
1447 pub struct AhoCorasickBuilder
{
1448 nfa_builder
: nfa
::Builder
,
1449 dfa_builder
: dfa
::Builder
,
1453 impl Default
for AhoCorasickBuilder
{
1454 fn default() -> AhoCorasickBuilder
{
1455 AhoCorasickBuilder
::new()
1459 impl AhoCorasickBuilder
{
1460 /// Create a new builder for configuring an Aho-Corasick automaton.
1462 /// If you don't need fine grained configuration or aren't sure which knobs
1463 /// to set, try using
1464 /// [`AhoCorasick::new_auto_configured`](struct.AhoCorasick.html#method.new_auto_configured)
1466 pub fn new() -> AhoCorasickBuilder
{
1467 AhoCorasickBuilder
{
1468 nfa_builder
: nfa
::Builder
::new(),
1469 dfa_builder
: dfa
::Builder
::new(),
1474 /// Build an Aho-Corasick automaton using the configuration set on this
1477 /// A builder may be reused to create more automatons.
1479 /// This method will use the default for representing internal state
1480 /// identifiers, which is `usize`. This guarantees that building the
1481 /// automaton will succeed and is generally a good default, but can make
1482 /// the size of the automaton 2-8 times bigger than it needs to be,
1483 /// depending on your target platform.
1490 /// use aho_corasick::AhoCorasickBuilder;
1492 /// let patterns = &["foo", "bar", "baz"];
1493 /// let ac = AhoCorasickBuilder::new()
1494 /// .build(patterns);
1495 /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
1497 pub fn build
<I
, P
>(&self, patterns
: I
) -> AhoCorasick
1499 I
: IntoIterator
<Item
= P
>,
1502 // The builder only returns an error if the chosen state ID
1503 // representation is too small to fit all of the given patterns. In
1504 // this case, since we fix the representation to usize, it will always
1505 // work because it's impossible to overflow usize since the underlying
1506 // storage would OOM long before that happens.
1507 self.build_with_size
::<usize, I
, P
>(patterns
)
1508 .expect("usize state ID type should always work")
1511 /// Build an Aho-Corasick automaton using the configuration set on this
1512 /// builder with a specific state identifier representation. This only has
1513 /// an effect when the `dfa` option is enabled.
1515 /// Generally, the choices for a state identifier representation are
1516 /// `u8`, `u16`, `u32`, `u64` or `usize`, with `usize` being the default.
1517 /// The advantage of choosing a smaller state identifier representation
1518 /// is that the automaton produced will be smaller. This might be
1519 /// beneficial for just generally using less space, or might even allow it
1520 /// to fit more of the automaton in your CPU's cache, leading to overall
1521 /// better search performance.
1523 /// Unlike the standard `build` method, this can report an error if the
1524 /// state identifier representation cannot support the size of the
1527 /// Note that the state identifier representation is determined by the
1528 /// `S` type variable. This requires a type hint of some sort, either
1529 /// by specifying the return type or using the turbofish, e.g.,
1530 /// `build_with_size::<u16, _, _>(...)`.
1537 /// use aho_corasick::{AhoCorasick, AhoCorasickBuilder};
1539 /// # fn example() -> Result<(), ::aho_corasick::Error> {
1540 /// let patterns = &["foo", "bar", "baz"];
1541 /// let ac: AhoCorasick<u8> = AhoCorasickBuilder::new()
1542 /// .build_with_size(patterns)?;
1543 /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
1544 /// # Ok(()) }; example().unwrap()
1547 /// Or alternatively, with turbofish:
1550 /// use aho_corasick::AhoCorasickBuilder;
1552 /// # fn example() -> Result<(), ::aho_corasick::Error> {
1553 /// let patterns = &["foo", "bar", "baz"];
1554 /// let ac = AhoCorasickBuilder::new()
1555 /// .build_with_size::<u8, _, _>(patterns)?;
1556 /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
1557 /// # Ok(()) }; example().unwrap()
1559 pub fn build_with_size
<S
, I
, P
>(
1562 ) -> Result
<AhoCorasick
<S
>>
1565 I
: IntoIterator
<Item
= P
>,
1568 let nfa
= self.nfa_builder
.build(patterns
)?
;
1569 let match_kind
= nfa
.match_kind().clone();
1570 let imp
= if self.dfa
{
1571 let dfa
= self.dfa_builder
.build(&nfa
)?
;
1576 Ok(AhoCorasick { imp, match_kind }
)
1579 /// Automatically configure the settings on this builder according to the
1580 /// patterns that will be used to construct the automaton.
1582 /// The idea here is to balance space and time automatically. That is, when
1583 /// searching a small number of patterns, this will attempt to use the
1584 /// fastest possible configuration since the total space required will be
1585 /// small anyway. As the number of patterns grows, this will fall back to
1586 /// slower configurations that use less space.
1588 /// This is guaranteed to never set `match_kind`, but any other option may
1596 /// use aho_corasick::AhoCorasickBuilder;
1598 /// let patterns = &["foo", "bar", "baz"];
1599 /// let ac = AhoCorasickBuilder::new()
1600 /// .auto_configure(patterns)
1601 /// .build(patterns);
1602 /// assert_eq!(Some(1), ac.find("xxx bar xxx").map(|m| m.pattern()));
1604 pub fn auto_configure
<B
: AsRef
<[u8]>>(
1607 ) -> &mut AhoCorasickBuilder
{
1608 // N.B. Currently we only use the length of `patterns` to make a
1609 // decision here, and could therefore ask for an `ExactSizeIterator`
1610 // instead. But it's conceivable that we might adapt this to look at
1611 // the total number of bytes, which would requires a second pass.
1613 // The logic here is fairly rudimentary at the moment, but probably
1614 // OK. The idea here is to use the fastest thing possible for a small
1615 // number of patterns. That is, a DFA with no byte classes, since byte
1616 // classes require an extra indirection for every byte searched. With a
1617 // moderate number of patterns, we still want a DFA, but save on both
1618 // space and compilation time by enabling byte classes. Finally, fall
1619 // back to the slower but smaller NFA.
1620 if patterns
.len() <= 100 {
1621 // N.B. Using byte classes can actually be faster by improving
1622 // locality, but this only really applies for multi-megabyte
1623 // automata (i.e., automata that don't fit in your CPU's cache).
1624 self.dfa(true).byte_classes(false);
1625 } else if patterns
.len() <= 5000 {
1631 /// Set the desired match semantics.
1633 /// The default is `MatchKind::Standard`, which corresponds to the match
1634 /// semantics supported by the standard textbook description of the
1635 /// Aho-Corasick algorithm. Namely, matches are reported as soon as they
1636 /// are found. Moreover, this is the only way to get overlapping matches
1637 /// or do stream searching.
1639 /// The other kinds of match semantics that are supported are
1640 /// `MatchKind::LeftmostFirst` and `MatchKind::LeftmostLongest`. The former
1641 /// corresponds to the match you would get if you were to try to match
1642 /// each pattern at each position in the haystack in the same order that
1643 /// you give to the automaton. That is, it returns the leftmost match
1644 /// corresponding the earliest pattern given to the automaton. The latter
1645 /// corresponds to finding the longest possible match among all leftmost
1648 /// For more details on match semantics, see the
1649 /// [documentation for `MatchKind`](enum.MatchKind.html).
1653 /// In these examples, we demonstrate the differences between match
1654 /// semantics for a particular set of patterns in a specific order:
1655 /// `b`, `abc`, `abcd`.
1657 /// Standard semantics:
1660 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
1662 /// let patterns = &["b", "abc", "abcd"];
1663 /// let haystack = "abcd";
1665 /// let ac = AhoCorasickBuilder::new()
1666 /// .match_kind(MatchKind::Standard) // default, not necessary
1667 /// .build(patterns);
1668 /// let mat = ac.find(haystack).expect("should have a match");
1669 /// assert_eq!("b", &haystack[mat.start()..mat.end()]);
1672 /// Leftmost-first semantics:
1675 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
1677 /// let patterns = &["b", "abc", "abcd"];
1678 /// let haystack = "abcd";
1680 /// let ac = AhoCorasickBuilder::new()
1681 /// .match_kind(MatchKind::LeftmostFirst)
1682 /// .build(patterns);
1683 /// let mat = ac.find(haystack).expect("should have a match");
1684 /// assert_eq!("abc", &haystack[mat.start()..mat.end()]);
1687 /// Leftmost-longest semantics:
1690 /// use aho_corasick::{AhoCorasickBuilder, MatchKind};
1692 /// let patterns = &["b", "abc", "abcd"];
1693 /// let haystack = "abcd";
1695 /// let ac = AhoCorasickBuilder::new()
1696 /// .match_kind(MatchKind::LeftmostLongest)
1697 /// .build(patterns);
1698 /// let mat = ac.find(haystack).expect("should have a match");
1699 /// assert_eq!("abcd", &haystack[mat.start()..mat.end()]);
1701 pub fn match_kind(&mut self, kind
: MatchKind
) -> &mut AhoCorasickBuilder
{
1702 self.nfa_builder
.match_kind(kind
);
1706 /// Enable anchored mode, which requires all matches to start at the
1707 /// first position in a haystack.
1709 /// This option is disabled by default.
1716 /// use aho_corasick::AhoCorasickBuilder;
1718 /// let patterns = &["foo", "bar"];
1719 /// let haystack = "foobar";
1721 /// let ac = AhoCorasickBuilder::new()
1723 /// .build(patterns);
1724 /// assert_eq!(1, ac.find_iter(haystack).count());
1727 /// When searching for overlapping matches, all matches that start at
1728 /// the beginning of a haystack will be reported:
1731 /// use aho_corasick::AhoCorasickBuilder;
1733 /// let patterns = &["foo", "foofoo"];
1734 /// let haystack = "foofoo";
1736 /// let ac = AhoCorasickBuilder::new()
1738 /// .build(patterns);
1739 /// assert_eq!(2, ac.find_overlapping_iter(haystack).count());
1740 /// // A non-anchored search would return 3 matches.
1742 pub fn anchored(&mut self, yes
: bool
) -> &mut AhoCorasickBuilder
{
1743 self.nfa_builder
.anchored(yes
);
1747 /// Enable ASCII-aware case insensitive matching.
1749 /// When this option is enabled, searching will be performed without
1750 /// respect to case for ASCII letters (`a-z` and `A-Z`) only.
1752 /// Enabling this option does not change the search algorithm, but it may
1753 /// increase the size of the automaton.
1755 /// **NOTE:** In the future, support for full Unicode case insensitivity
1756 /// may be added, but ASCII case insensitivity is comparatively much
1764 /// use aho_corasick::AhoCorasickBuilder;
1766 /// let patterns = &["FOO", "bAr", "BaZ"];
1767 /// let haystack = "foo bar baz";
1769 /// let ac = AhoCorasickBuilder::new()
1770 /// .ascii_case_insensitive(true)
1771 /// .build(patterns);
1772 /// assert_eq!(3, ac.find_iter(haystack).count());
1774 pub fn ascii_case_insensitive(
1777 ) -> &mut AhoCorasickBuilder
{
1778 self.nfa_builder
.ascii_case_insensitive(yes
);
1782 /// Set the limit on how many NFA states use a dense representation for
1783 /// their transitions.
1785 /// A dense representation uses more space, but supports faster access to
1786 /// transitions at search time. Thus, this setting permits the control of a
1787 /// space vs time trade off when using the NFA variant of Aho-Corasick.
1789 /// This limit is expressed in terms of the depth of a state, i.e., the
1790 /// number of transitions from the starting state of the NFA. The idea is
1791 /// that most of the time searching will be spent near the starting state
1792 /// of the automaton, so states near the start state should use a dense
1793 /// representation. States further away from the start state would then use
1794 /// a sparse representation, which uses less space but is slower to access
1795 /// transitions at search time.
1797 /// By default, this is set to a low but non-zero number.
1799 /// This setting has no effect if the `dfa` option is enabled.
1800 pub fn dense_depth(&mut self, depth
: usize) -> &mut AhoCorasickBuilder
{
1801 self.nfa_builder
.dense_depth(depth
);
1805 /// Compile the standard Aho-Corasick automaton into a deterministic finite
1806 /// automaton (DFA).
1808 /// When this is disabled (which is the default), then a non-deterministic
1809 /// finite automaton (NFA) is used instead.
1811 /// The main benefit to a DFA is that it can execute searches more quickly
1812 /// than a DFA (perhaps 2-4 times as fast). The main drawback is that the
1813 /// DFA uses more space and can take much longer to build.
1815 /// Enabling this option does not change the time complexity for
1816 /// constructing the Aho-Corasick automaton (which is `O(p)` where
1817 /// `p` is the total number of patterns being compiled). Enabling this
1818 /// option does however reduce the time complexity of non-overlapping
1819 /// searches from `O(n + p)` to `O(n)`, where `n` is the length of the
1822 /// In general, it's a good idea to enable this if you're searching a
1823 /// small number of fairly short patterns (~1000), or if you want the
1824 /// fastest possible search without regard to compilation time or space
1826 pub fn dfa(&mut self, yes
: bool
) -> &mut AhoCorasickBuilder
{
1831 /// Enable heuristic prefilter optimizations.
1833 /// When enabled, searching will attempt to quickly skip to match
1834 /// candidates using specialized literal search routines. A prefilter
1835 /// cannot always be used, and is generally treated as a heuristic. It
1836 /// can be useful to disable this if the prefilter is observed to be
1837 /// sub-optimal for a particular workload.
1839 /// This is enabled by default.
1840 pub fn prefilter(&mut self, yes
: bool
) -> &mut AhoCorasickBuilder
{
1841 self.nfa_builder
.prefilter(yes
);
1845 /// Shrink the size of the transition alphabet by mapping bytes to their
1846 /// equivalence classes. This only has an effect when the `dfa` option is
1849 /// When enabled, each a DFA will use a map from all possible bytes
1850 /// to their corresponding equivalence class. Each equivalence class
1851 /// represents a set of bytes that does not discriminate between a match
1852 /// and a non-match in the DFA. For example, the patterns `bar` and `baz`
1853 /// have at least five equivalence classes: singleton sets of `b`, `a`, `r`
1854 /// and `z`, and a final set that contains every other byte.
1856 /// The advantage of this map is that the size of the transition table can
1857 /// be reduced drastically from `#states * 256 * sizeof(id)` to
1858 /// `#states * k * sizeof(id)` where `k` is the number of equivalence
1859 /// classes. As a result, total space usage can decrease substantially.
1860 /// Moreover, since a smaller alphabet is used, compilation becomes faster
1863 /// The disadvantage of this map is that every byte searched must be
1864 /// passed through this map before it can be used to determine the next
1865 /// transition. This has a small match time performance cost. However, if
1866 /// the DFA is otherwise very large without byte classes, then using byte
1867 /// classes can greatly improve memory locality and thus lead to better
1868 /// overall performance.
1870 /// This option is enabled by default.
1871 pub fn byte_classes(&mut self, yes
: bool
) -> &mut AhoCorasickBuilder
{
1872 self.dfa_builder
.byte_classes(yes
);
1876 /// Premultiply state identifiers in the transition table. This only has
1877 /// an effect when the `dfa` option is enabled.
1879 /// When enabled, state identifiers are premultiplied to point to their
1880 /// corresponding row in the transition table. That is, given the `i`th
1881 /// state, its corresponding premultiplied identifier is `i * k` where `k`
1882 /// is the alphabet size of the automaton. (The alphabet size is at most
1883 /// 256, but is in practice smaller if byte classes is enabled.)
1885 /// When state identifiers are not premultiplied, then the identifier of
1886 /// the `i`th state is `i`.
1888 /// The advantage of premultiplying state identifiers is that is saves a
1889 /// multiplication instruction per byte when searching with a DFA. This has
1890 /// been observed to lead to a 20% performance benefit in micro-benchmarks.
1892 /// The primary disadvantage of premultiplying state identifiers is
1893 /// that they require a larger integer size to represent. For example,
1894 /// if the DFA has 200 states, then its premultiplied form requires 16
1895 /// bits to represent every possible state identifier, where as its
1896 /// non-premultiplied form only requires 8 bits.
1898 /// This option is enabled by default.
1899 pub fn premultiply(&mut self, yes
: bool
) -> &mut AhoCorasickBuilder
{
1900 self.dfa_builder
.premultiply(yes
);
1905 /// A knob for controlling the match semantics of an Aho-Corasick automaton.
1907 /// There are two generally different ways that Aho-Corasick automatons can
1908 /// report matches. The first way is the "standard" approach that results from
1909 /// implementing most textbook explanations of Aho-Corasick. The second way is
1910 /// to report only the leftmost non-overlapping matches. The leftmost approach
1911 /// is in turn split into two different ways of resolving ambiguous matches:
1912 /// leftmost-first and leftmost-longest.
1914 /// The `Standard` match kind is the default and is the only one that supports
1915 /// overlapping matches and stream searching. (Trying to find overlapping
1916 /// or streaming matches using leftmost match semantics will result in a
1917 /// panic.) The `Standard` match kind will report matches as they are seen.
1918 /// When searching for overlapping matches, then all possible matches are
1919 /// reported. When searching for non-overlapping matches, the first match seen
1920 /// is reported. For example, for non-overlapping matches, given the patterns
1921 /// `abcd` and `b` and the subject string `abcdef`, only a match for `b` is
1922 /// reported since it is detected first. The `abcd` match is never reported
1923 /// since it overlaps with the `b` match.
1925 /// In contrast, the leftmost match kind always prefers the leftmost match
1926 /// among all possible matches. Given the same example as above with `abcd` and
1927 /// `b` as patterns and `abcdef` as the subject string, the leftmost match is
1928 /// `abcd` since it begins before the `b` match, even though the `b` match is
1929 /// detected before the `abcd` match. In this case, the `b` match is not
1930 /// reported at all since it overlaps with the `abcd` match.
1932 /// The difference between leftmost-first and leftmost-longest is in how they
1933 /// resolve ambiguous matches when there are multiple leftmost matches to
1934 /// choose from. Leftmost-first always chooses the pattern that was provided
1935 /// earliest, where as leftmost-longest always chooses the longest matching
1936 /// pattern. For example, given the patterns `a` and `ab` and the subject
1937 /// string `ab`, the leftmost-first match is `a` but the leftmost-longest match
1938 /// is `ab`. Conversely, if the patterns were given in reverse order, i.e.,
1939 /// `ab` and `a`, then both the leftmost-first and leftmost-longest matches
1940 /// would be `ab`. Stated differently, the leftmost-first match depends on the
1941 /// order in which the patterns were given to the Aho-Corasick automaton.
1942 /// Because of that, when leftmost-first matching is used, if a pattern `A`
1943 /// that appears before a pattern `B` is a prefix of `B`, then it is impossible
1944 /// to ever observe a match of `B`.
1946 /// If you're not sure which match kind to pick, then stick with the standard
1947 /// kind, which is the default. In particular, if you need overlapping or
1948 /// streaming matches, then you _must_ use the standard kind. The leftmost
1949 /// kinds are useful in specific circumstances. For example, leftmost-first can
1950 /// be very useful as a way to implement match priority based on the order of
1951 /// patterns given and leftmost-longest can be useful for dictionary searching
1952 /// such that only the longest matching words are reported.
1954 /// # Relationship with regular expression alternations
1956 /// Understanding match semantics can be a little tricky, and one easy way
1957 /// to conceptualize non-overlapping matches from an Aho-Corasick automaton
1958 /// is to think about them as a simple alternation of literals in a regular
1959 /// expression. For example, let's say we wanted to match the strings
1960 /// `Sam` and `Samwise`, which would turn into the regex `Sam|Samwise`. It
1961 /// turns out that regular expression engines have two different ways of
1962 /// matching this alternation. The first way, leftmost-longest, is commonly
1963 /// found in POSIX compatible implementations of regular expressions (such as
1964 /// `grep`). The second way, leftmost-first, is commonly found in backtracking
1965 /// implementations such as Perl. (Some regex engines, such as RE2 and Rust's
1966 /// regex engine do not use backtracking, but still implement leftmost-first
1967 /// semantics in an effort to match the behavior of dominant backtracking
1968 /// regex engines such as those found in Perl, Ruby, Python, Javascript and
1971 /// That is, when matching `Sam|Samwise` against `Samwise`, a POSIX regex
1972 /// will match `Samwise` because it is the longest possible match, but a
1973 /// Perl-like regex will match `Sam` since it appears earlier in the
1974 /// alternation. Indeed, the regex `Sam|Samwise` in a Perl-like regex engine
1975 /// will never match `Samwise` since `Sam` will always have higher priority.
1976 /// Conversely, matching the regex `Samwise|Sam` against `Samwise` will lead to
1977 /// a match of `Samwise` in both POSIX and Perl-like regexes since `Samwise` is
1978 /// still longest match, but it also appears earlier than `Sam`.
1980 /// The "standard" match semantics of Aho-Corasick generally don't correspond
1981 /// to the match semantics of any large group of regex implementations, so
1982 /// there's no direct analogy that can be made here. Standard match semantics
1983 /// are generally useful for overlapping matches, or if you just want to see
1984 /// matches as they are detected.
1986 /// The main conclusion to draw from this section is that the match semantics
1987 /// can be tweaked to precisely match either Perl-like regex alternations or
1988 /// POSIX regex alternations.
1989 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
1990 pub enum MatchKind
{
1991 /// Use standard match semantics, which support overlapping matches. When
1992 /// used with non-overlapping matches, matches are reported as they are
1995 /// Use leftmost-first match semantics, which reports leftmost matches.
1996 /// When there are multiple possible leftmost matches, the match
1997 /// corresponding to the pattern that appeared earlier when constructing
1998 /// the automaton is reported.
2000 /// This does **not** support overlapping matches or stream searching. If
2001 /// this match kind is used, attempting to find overlapping matches or
2002 /// stream matches will panic.
2004 /// Use leftmost-longest match semantics, which reports leftmost matches.
2005 /// When there are multiple possible leftmost matches, the longest match
2008 /// This does **not** support overlapping matches or stream searching. If
2009 /// this match kind is used, attempting to find overlapping matches or
2010 /// stream matches will panic.
2012 /// Hints that destructuring should not be exhaustive.
2014 /// This enum may grow additional variants, so this makes sure clients
2015 /// don't count on exhaustive matching. (Otherwise, adding a new variant
2016 /// could break existing code.)
2021 /// The default match kind is `MatchKind::Standard`.
2022 impl Default
for MatchKind
{
2023 fn default() -> MatchKind
{
2029 fn supports_overlapping(&self) -> bool
{
2033 fn supports_stream(&self) -> bool
{
2034 // TODO: It may be possible to support this. It's hard.
2036 // See: https://github.com/rust-lang/regex/issues/425#issuecomment-471367838
2040 pub(crate) fn is_standard(&self) -> bool
{
2041 *self == MatchKind
::Standard
2044 pub(crate) fn is_leftmost(&self) -> bool
{
2045 *self == MatchKind
::LeftmostFirst
2046 || *self == MatchKind
::LeftmostLongest
2049 pub(crate) fn is_leftmost_first(&self) -> bool
{
2050 *self == MatchKind
::LeftmostFirst
2053 /// Convert this match kind into a packed match kind. If this match kind
2054 /// corresponds to standard semantics, then this returns None, since
2055 /// packed searching does not support standard semantics.
2056 pub(crate) fn as_packed(&self) -> Option
<packed
::MatchKind
> {
2058 MatchKind
::Standard
=> None
,
2059 MatchKind
::LeftmostFirst
=> Some(packed
::MatchKind
::LeftmostFirst
),
2060 MatchKind
::LeftmostLongest
=> {
2061 Some(packed
::MatchKind
::LeftmostLongest
)
2063 MatchKind
::__Nonexhaustive
=> unreachable
!(),
2074 use std
::panic
::{RefUnwindSafe, UnwindSafe}
;
2076 fn assert_send
<T
: Send
>() {}
2077 fn assert_sync
<T
: Sync
>() {}
2078 fn assert_unwind_safe
<T
: RefUnwindSafe
+ UnwindSafe
>() {}
2080 assert_send
::<AhoCorasick
>();
2081 assert_sync
::<AhoCorasick
>();
2082 assert_unwind_safe
::<AhoCorasick
>();
2083 assert_send
::<AhoCorasickBuilder
>();
2084 assert_sync
::<AhoCorasickBuilder
>();
2085 assert_unwind_safe
::<AhoCorasickBuilder
>();