Struct aho_corasick::AhoCorasick

source · [−]

pub struct AhoCorasick { /* private fields */ }

Expand description

An automaton for searching multiple strings in linear time.

The AhoCorasick type supports a few basic ways of constructing an automaton, with the default being AhoCorasick::new. However, there are a fair number of configurable options that can be set by using AhoCorasickBuilder instead. Such options include, but are not limited to, how matches are determined, simple case insensitivity, whether to use a DFA or not and various knobs for controlling the space-vs-time trade offs taken when building the automaton.

Resource usage

Aho-Corasick automatons are always constructed in O(p) time, where p is the combined length of all patterns being searched. With that said, building an automaton can be fairly costly because of high constant factors, particularly when enabling the DFA option with AhoCorasickBuilder::kind. For this reason, it’s generally a good idea to build an automaton once and reuse it as much as possible.

Aho-Corasick automatons can also use a fair bit of memory. To get a concrete idea of how much memory is being used, try using the AhoCorasick::memory_usage method.

To give a quick idea of the differences between Aho-Corasick implementations and their resource usage, here’s a sample of construction times and heap memory used after building an automaton from 100,000 randomly selected titles from Wikipedia:

99MB for a noncontiguous::NFA in 240ms.
21MB for a contiguous::NFA in 275ms.
1.6GB for a dfa::DFA in 1.88s.

(Note that the memory usage above reflects the size of each automaton and not peak memory usage. For example, building a contiguous NFA requires first building a noncontiguous NFA. Once the contiguous NFA is built, the noncontiguous NFA is freed.)

This experiment very strongly argues that a contiguous NFA is often the best balance in terms of resource usage. It takes a little longer to build, but its memory usage is quite small. Its search speed (not listed) is also often faster than a noncontiguous NFA, but a little slower than a DFA. Indeed, when no specific AhoCorasickKind is used (which is the default), a contiguous NFA is used in most cases.

The only “catch” to using a contiguous NFA is that, because of its variety of compression tricks, it may not be able to support automatons as large as what the noncontiguous NFA supports. In which case, building a contiguous NFA will fail and (by default) AhoCorasick will automatically fall back to a noncontiguous NFA. (This typically only happens when building automatons from millions of patterns.) Otherwise, the small additional time for building a contiguous NFA is almost certainly worth it.

Cloning

The AhoCorasick type uses thread safe reference counting internally. It is guaranteed that it is cheap to clone.

Search configuration

Most of the search routines accept anything that can be cheaply converted to an Input. This includes &[u8], &str and Input itself.

Construction failure

It is generally possible for building an Aho-Corasick automaton to fail. Construction can fail in generally one way: when the inputs provided are too big. Whether that’s a pattern that is too long, too many patterns or some combination of both. A first approximation for the scale at which construction can fail is somewhere around “millions of patterns.”

For that reason, if you’re building an Aho-Corasick automaton from untrusted input (or input that doesn’t have any reasonable bounds on its size), then it is strongly recommended to handle the possibility of an error.

If you’re constructing an Aho-Corasick automaton from static or trusted data, then it is likely acceptable to panic (by calling unwrap() or expect()) if construction fails.

Fallibility

The AhoCorasick type provides a number of methods for searching, as one might expect. Depending on how the Aho-Corasick automaton was built and depending on the search configuration, it is possible for a search to return an error. Since an error is never dependent on the actual contents of the haystack, this type provides both infallible and fallible methods for searching. The infallible methods panic if an error occurs, and can be used for convenience and when you know the search will never return an error.

For example, the AhoCorasick::find_iter method is the infallible version of the AhoCorasick::try_find_iter method.

Examples of errors that can occur:

Running a search that requires MatchKind::Standard semantics (such as a stream or overlapping search) with an automaton that was built with MatchKind::LeftmostFirst or MatchKind::LeftmostLongest semantics.
Running an anchored search with an automaton that only supports unanchored searches. (By default, AhoCorasick only supports unanchored searches. But this can be toggled with AhoCorasickBuilder::start_kind.)
Running an unanchored search with an automaton that only supports anchored searches.

The common thread between the different types of errors is that they are all rooted in the automaton construction and search configurations. If those configurations are a static property of your program, then it is reasonable to call infallible routines since you know an error will never occur. And if one does occur, then it’s a bug in your program.

To re-iterate, if the patterns, build or search configuration come from user or untrusted data, then you should handle errors at build or search time. If only the haystack comes from user or untrusted data, then there should be no need to handle errors anywhere and it is generally encouraged to unwrap() (or expect()) both build and search time calls.

Examples

This example shows how to search for occurrences of multiple patterns simultaneously in a case insensitive fashion. Each match includes the pattern that matched along with the byte offsets of the match.

use aho_corasick::{AhoCorasick, PatternID};

let patterns = &["apple", "maple", "snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";

let ac = AhoCorasick::builder()
    .ascii_case_insensitive(true)
    .build(patterns)
    .unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
    matches.push((mat.pattern(), mat.start(), mat.end()));
}
assert_eq!(matches, vec![
    (PatternID::must(1), 13, 18),
    (PatternID::must(0), 28, 33),
    (PatternID::must(2), 43, 50),
]);

This example shows how to replace matches with some other string:

use aho_corasick::AhoCorasick;

let patterns = &["fox", "brown", "quick"];
let haystack = "The quick brown fox.";
let replace_with = &["sloth", "grey", "slow"];

let ac = AhoCorasick::new(patterns).unwrap();
let result = ac.replace_all(haystack, replace_with);
assert_eq!(result, "The slow grey sloth.");

Struct aho_corasick::AhoCorasick

Implementations

impl AhoCorasick

pub fn new<I, P>(patterns: I) -> Result<AhoCorasick, BuildError>where I: IntoIterator<Item = P>, P: AsRef<[u8]>,

pub fn builder() -> AhoCorasickBuilder

impl AhoCorasick

pub fn is_match<'h, I: Into<Input<'h>>>(&self, input: I) -> bool

pub fn find<'h, I: Into<Input<'h>>>(&self, input: I) -> Option<Match>

pub fn find_overlapping<'h, I: Into<Input<'h>>>( &self, input: I, state: &mut OverlappingState)

pub fn find_iter<'a, 'h, I: Into<Input<'h>>>( &'a self, input: I) -> FindIter<'a, 'h>ⓘNotable traits for FindIter<'a, 'h>impl<'a, 'h> Iterator for FindIter<'a, 'h> type Item = Match;

pub fn find_overlapping_iter<'a, 'h, I: Into<Input<'h>>>( &'a self, input: I) -> FindOverlappingIter<'a, 'h>ⓘNotable traits for FindOverlappingIter<'a, 'h>impl<'a, 'h> Iterator for FindOverlappingIter<'a, 'h> type Item = Match;

pub fn replace_all<B>(&self, haystack: &str, replace_with: &[B]) -> Stringwhere B: AsRef<str>,

pub fn replace_all_bytes<B>(&self, haystack: &[u8], replace_with: &[B]) -> Vec<u8>where B: AsRef<[u8]>,

pub fn replace_all_with<F>( &self, haystack: &str, dst: &mut String, replace_with: F)where F: FnMut(&Match, &str, &mut String) -> bool,

pub fn replace_all_with_bytes<F>( &self, haystack: &[u8], dst: &mut Vec<u8>, replace_with: F)where F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool,

pub fn stream_find_iter<'a, R: Read>(&'a self, rdr: R) -> StreamFindIter<'a, R>ⓘNotable traits for StreamFindIter<'a, R>impl<'a, R: Read> Iterator for StreamFindIter<'a, R> type Item = Result<Match, Error>;

impl AhoCorasick

pub fn try_find<'h, I: Into<Input<'h>>>( &self, input: I) -> Result<Option<Match>, MatchError>

pub fn try_find_overlapping<'h, I: Into<Input<'h>>>( &self, input: I, state: &mut OverlappingState) -> Result<(), MatchError>

pub fn try_find_iter<'a, 'h, I: Into<Input<'h>>>( &'a self, input: I) -> Result<FindIter<'a, 'h>, MatchError>

pub fn try_find_overlapping_iter<'a, 'h, I: Into<Input<'h>>>( &'a self, input: I) -> Result<FindOverlappingIter<'a, 'h>, MatchError>

pub fn try_replace_all<B>( &self, haystack: &str, replace_with: &[B]) -> Result<String, MatchError>where B: AsRef<str>,

pub fn try_replace_all_bytes<B>( &self, haystack: &[u8], replace_with: &[B]) -> Result<Vec<u8>, MatchError>where B: AsRef<[u8]>,

pub fn try_replace_all_with<F>( &self, haystack: &str, dst: &mut String, replace_with: F) -> Result<(), MatchError>where F: FnMut(&Match, &str, &mut String) -> bool,

pub fn try_replace_all_with_bytes<F>( &self, haystack: &[u8], dst: &mut Vec<u8>, replace_with: F) -> Result<(), MatchError>where F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool,

pub fn try_stream_find_iter<'a, R: Read>( &'a self, rdr: R) -> Result<StreamFindIter<'a, R>, MatchError>

pub fn try_stream_replace_all<R, W, B>( &self, rdr: R, wtr: W, replace_with: &[B]) -> Result<(), Error>where R: Read, W: Write, B: AsRef<[u8]>,

pub fn try_stream_replace_all_with<R, W, F>( &self, rdr: R, wtr: W, replace_with: F) -> Result<(), Error>where R: Read, W: Write, F: FnMut(&Match, &[u8], &mut W) -> Result<(), Error>,

impl AhoCorasick

pub fn kind(&self) -> AhoCorasickKind

pub fn start_kind(&self) -> StartKind

pub fn match_kind(&self) -> MatchKind

pub fn min_pattern_len(&self) -> usize

pub fn max_pattern_len(&self) -> usize

pub fn patterns_len(&self) -> usize

pub fn memory_usage(&self) -> usize

Trait Implementations

impl Clone for AhoCorasick

fn clone(&self) -> AhoCorasick

const fn clone_from(&mut self, source: &Self)

impl Debug for AhoCorasick

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Auto Trait Implementations

impl RefUnwindSafe for AhoCorasick

impl Send for AhoCorasick

impl Sync for AhoCorasick

impl Unpin for AhoCorasick

impl UnwindSafe for AhoCorasick

Blanket Implementations

impl<T> Any for Twhere T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for Twhere T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for Twhere T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> From<T> for T

fn from(t: T) -> T

impl<T, U> Into<U> for Twhere U: From<T>,

fn into(self) -> U

impl<T> ToOwned for Twhere T: Clone,

type Owned = T

fn to_owned(&self) -> T

fn clone_into(&self, target: &mut T)

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

type Error = Infallible

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

pub fn new<I, P>(patterns: I) -> Result<AhoCorasick, BuildError>where
I: IntoIterator<Item = P>,
P: AsRef<[u8]>,

pub fn find_overlapping<'h, I: Into<Input<'h>>>(
&self,
input: I,
state: &mut OverlappingState
)

pub fn find_iter<'a, 'h, I: Into<Input<'h>>>(
&'a self,
input: I
) -> FindIter<'a, 'h>ⓘNotable traits for FindIter<'a, 'h>`impl<'a, 'h> Iterator for FindIter<'a, 'h> type Item = Match;`

pub fn find_overlapping_iter<'a, 'h, I: Into<Input<'h>>>(
&'a self,
input: I
) -> FindOverlappingIter<'a, 'h>ⓘNotable traits for FindOverlappingIter<'a, 'h>`impl<'a, 'h> Iterator for FindOverlappingIter<'a, 'h> type Item = Match;`

pub fn replace_all<B>(&self, haystack: &str, replace_with: &[B]) -> Stringwhere
B: AsRef<str>,

pub fn replace_all_bytes<B>(&self, haystack: &[u8], replace_with: &[B]) -> Vec<u8>where
B: AsRef<[u8]>,

pub fn replace_all_with<F>(
&self,
haystack: &str,
dst: &mut String,
replace_with: F
)where
F: FnMut(&Match, &str, &mut String) -> bool,

pub fn replace_all_with_bytes<F>(
&self,
haystack: &[u8],
dst: &mut Vec<u8>,
replace_with: F
)where
F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool,

pub fn stream_find_iter<'a, R: Read>(&'a self, rdr: R) -> StreamFindIter<'a, R>ⓘNotable traits for StreamFindIter<'a, R>`impl<'a, R: Read> Iterator for StreamFindIter<'a, R> type Item = Result<Match, Error>;`

pub fn try_find<'h, I: Into<Input<'h>>>(
&self,
input: I
) -> Result<Option<Match>, MatchError>

pub fn try_find_overlapping<'h, I: Into<Input<'h>>>(
&self,
input: I,
state: &mut OverlappingState
) -> Result<(), MatchError>

pub fn try_find_iter<'a, 'h, I: Into<Input<'h>>>(
&'a self,
input: I
) -> Result<FindIter<'a, 'h>, MatchError>

pub fn try_find_overlapping_iter<'a, 'h, I: Into<Input<'h>>>(
&'a self,
input: I
) -> Result<FindOverlappingIter<'a, 'h>, MatchError>

pub fn try_replace_all<B>(
&self,
haystack: &str,
replace_with: &[B]
) -> Result<String, MatchError>where
B: AsRef<str>,

pub fn try_replace_all_bytes<B>(
&self,
haystack: &[u8],
replace_with: &[B]
) -> Result<Vec<u8>, MatchError>where
B: AsRef<[u8]>,

pub fn try_replace_all_with<F>(
&self,
haystack: &str,
dst: &mut String,
replace_with: F
) -> Result<(), MatchError>where
F: FnMut(&Match, &str, &mut String) -> bool,

pub fn try_replace_all_with_bytes<F>(
&self,
haystack: &[u8],
dst: &mut Vec<u8>,
replace_with: F
) -> Result<(), MatchError>where
F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool,

pub fn try_stream_find_iter<'a, R: Read>(
&'a self,
rdr: R
) -> Result<StreamFindIter<'a, R>, MatchError>

pub fn try_stream_replace_all<R, W, B>(
&self,
rdr: R,
wtr: W,
replace_with: &[B]
) -> Result<(), Error>where
R: Read,
W: Write,
B: AsRef<[u8]>,

pub fn try_stream_replace_all_with<R, W, F>(
&self,
rdr: R,
wtr: W,
replace_with: F
) -> Result<(), Error>where
R: Read,
W: Write,
F: FnMut(&Match, &[u8], &mut W) -> Result<(), Error>,

impl<T> Any for Twhere
T: 'static + ?Sized,

impl<T> Borrow<T> for Twhere
T: ?Sized,

impl<T> BorrowMut<T> for Twhere
T: ?Sized,

impl<T, U> Into<U> for Twhere
U: From<T>,

impl<T> ToOwned for Twhere
T: Clone,

impl<T, U> TryFrom<U> for Twhere
U: Into<T>,

impl<T, U> TryInto<U> for Twhere
U: TryFrom<T>,