aho_corasick/lib.rs
1/*!
2A library for finding occurrences of many patterns at once. This library
3provides multiple pattern search principally through an implementation of the
4[Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm),
5which builds a fast finite state machine for executing searches in linear time.
6
7Additionally, this library provides a number of configuration options for
8building the automaton that permit controlling the space versus time trade
9off. Other features include simple ASCII case insensitive matching, finding
10overlapping matches, replacements, searching streams and even searching and
11replacing text in streams.
12
13Finally, unlike all other (known) Aho-Corasick implementations, this one
14supports enabling
15[leftmost-first](enum.MatchKind.html#variant.LeftmostFirst)
16or
17[leftmost-longest](enum.MatchKind.html#variant.LeftmostFirst)
18match semantics, using a (seemingly) novel alternative construction algorithm.
19For more details on what match semantics means, see the
20[`MatchKind`](enum.MatchKind.html)
21type.
22
23# Overview
24
25This section gives a brief overview of the primary types in this crate:
26
27* [`AhoCorasick`](struct.AhoCorasick.html) is the primary type and represents
28 an Aho-Corasick automaton. This is the type you use to execute searches.
29* [`AhoCorasickBuilder`](struct.AhoCorasickBuilder.html) can be used to build
30 an Aho-Corasick automaton, and supports configuring a number of options.
31* [`Match`](struct.Match.html) represents a single match reported by an
32 Aho-Corasick automaton. Each match has two pieces of information: the pattern
33 that matched and the start and end byte offsets corresponding to the position
34 in the haystack at which it matched.
35
36Additionally, the [`packed`](packed/index.html) sub-module contains a lower
37level API for using fast vectorized routines for finding a small number of
38patterns in a haystack.
39
40# Example: basic searching
41
42This example shows how to search for occurrences of multiple patterns
43simultaneously. Each match includes the pattern that matched along with the
44byte offsets of the match.
45
46```
47use aho_corasick::AhoCorasick;
48
49let patterns = &["apple", "maple", "Snapple"];
50let haystack = "Nobody likes maple in their apple flavored Snapple.";
51
52let ac = AhoCorasick::new(patterns);
53let mut matches = vec![];
54for mat in ac.find_iter(haystack) {
55 matches.push((mat.pattern(), mat.start(), mat.end()));
56}
57assert_eq!(matches, vec![
58 (1, 13, 18),
59 (0, 28, 33),
60 (2, 43, 50),
61]);
62```
63
64# Example: case insensitivity
65
66This is like the previous example, but matches `Snapple` case insensitively
67using `AhoCorasickBuilder`:
68
69```
70use aho_corasick::AhoCorasickBuilder;
71
72let patterns = &["apple", "maple", "snapple"];
73let haystack = "Nobody likes maple in their apple flavored Snapple.";
74
75let ac = AhoCorasickBuilder::new()
76 .ascii_case_insensitive(true)
77 .build(patterns);
78let mut matches = vec![];
79for mat in ac.find_iter(haystack) {
80 matches.push((mat.pattern(), mat.start(), mat.end()));
81}
82assert_eq!(matches, vec![
83 (1, 13, 18),
84 (0, 28, 33),
85 (2, 43, 50),
86]);
87```
88
89# Example: replacing matches in a stream
90
91This example shows how to execute a search and replace on a stream without
92loading the entire stream into memory first.
93
94```
95use aho_corasick::AhoCorasick;
96
97# fn example() -> Result<(), ::std::io::Error> {
98let patterns = &["fox", "brown", "quick"];
99let replace_with = &["sloth", "grey", "slow"];
100
101// In a real example, these might be `std::fs::File`s instead. All you need to
102// do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
103let rdr = "The quick brown fox.";
104let mut wtr = vec![];
105
106let ac = AhoCorasick::new(patterns);
107ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)?;
108assert_eq!(b"The slow grey sloth.".to_vec(), wtr);
109# Ok(()) }; example().unwrap()
110```
111
112# Example: finding the leftmost first match
113
114In the textbook description of Aho-Corasick, its formulation is typically
115structured such that it reports all possible matches, even when they overlap
116with another. In many cases, overlapping matches may not be desired, such as
117the case of finding all successive non-overlapping matches like you might with
118a standard regular expression.
119
120Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do
121this doesn't always work in the expected way, since it will report matches as
122soon as they are seen. For example, consider matching the regex `Samwise|Sam`
123against the text `Samwise`. Most regex engines (that are Perl-like, or
124non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick
125algorithm modified for reporting non-overlapping matches will report `Sam`.
126
127A novel contribution of this library is the ability to change the match
128semantics of Aho-Corasick (without additional search time overhead) such that
129`Samwise` is reported instead. For example, here's the standard approach:
130
131```
132use aho_corasick::AhoCorasick;
133
134let patterns = &["Samwise", "Sam"];
135let haystack = "Samwise";
136
137let ac = AhoCorasick::new(patterns);
138let mat = ac.find(haystack).expect("should have a match");
139assert_eq!("Sam", &haystack[mat.start()..mat.end()]);
140```
141
142And now here's the leftmost-first version, which matches how a Perl-like
143regex will work:
144
145```
146use aho_corasick::{AhoCorasickBuilder, MatchKind};
147
148let patterns = &["Samwise", "Sam"];
149let haystack = "Samwise";
150
151let ac = AhoCorasickBuilder::new()
152 .match_kind(MatchKind::LeftmostFirst)
153 .build(patterns);
154let mat = ac.find(haystack).expect("should have a match");
155assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);
156```
157
158In addition to leftmost-first semantics, this library also supports
159leftmost-longest semantics, which match the POSIX behavior of a regular
160expression alternation. See
161[`MatchKind`](enum.MatchKind.html)
162for more details.
163
164# Prefilters
165
166While an Aho-Corasick automaton can perform admirably when compared to more
167naive solutions, it is generally slower than more specialized algorithms that
168are accelerated using vector instructions such as SIMD.
169
170For that reason, this library will internally use a "prefilter" to attempt
171to accelerate searches when possible. Currently, this library has several
172different algorithms it might use depending on the patterns provided. Once the
173number of patterns gets too big, prefilters are no longer used.
174
175While a prefilter is generally good to have on by default since it works
176well in the common case, it can lead to less predictable or even sub-optimal
177performance in some cases. For that reason, prefilters can be explicitly
178disabled via
179[`AhoCorasickBuilder::prefilter`](struct.AhoCorasickBuilder.html#method.prefilter).
180*/
181
182#![allow(warnings)]
183#![deny(missing_docs)]
184
185// We can never be truly no_std, but we could be alloc-only some day, so
186// require the std feature for now.
187#[cfg(not(feature = "std"))]
188compile_error!("`std` feature is currently required to build this crate");
189
190// #[cfg(doctest)]
191// #[macro_use]
192// extern crate doc_comment;
193
194// #[cfg(doctest)]
195// doctest!("../README.md");
196
197pub use crate::ahocorasick::{
198 AhoCorasick, AhoCorasickBuilder, FindIter, FindOverlappingIter, MatchKind,
199 StreamFindIter,
200};
201pub use crate::error::{Error, ErrorKind};
202pub use crate::state_id::StateID;
203
204mod ahocorasick;
205mod automaton;
206mod buffer;
207mod byte_frequencies;
208mod classes;
209mod dfa;
210mod error;
211mod nfa;
212pub mod packed;
213mod prefilter;
214mod state_id;
215#[cfg(test)]
216mod tests;
217
218/// A representation of a match reported by an Aho-Corasick automaton.
219///
220/// A match has two essential pieces of information: the identifier of the
221/// pattern that matched, along with the start and end offsets of the match
222/// in the haystack.
223///
224/// # Examples
225///
226/// Basic usage:
227///
228/// ```
229/// use aho_corasick::AhoCorasick;
230///
231/// let ac = AhoCorasick::new(&[
232/// "foo", "bar", "baz",
233/// ]);
234/// let mat = ac.find("xxx bar xxx").expect("should have a match");
235/// assert_eq!(1, mat.pattern());
236/// assert_eq!(4, mat.start());
237/// assert_eq!(7, mat.end());
238/// ```
239#[derive(Clone, Debug, Eq, Hash, PartialEq)]
240pub struct Match {
241 /// The pattern id.
242 pattern: usize,
243 /// The length of this match, such that the starting position of the match
244 /// is `end - len`.
245 ///
246 /// We use length here because, other than the pattern id, the only
247 /// information about each pattern that the automaton stores is its length.
248 /// So using the length here is just a bit more natural. But it isn't
249 /// technically required.
250 len: usize,
251 /// The end offset of the match, exclusive.
252 end: usize,
253}
254
255impl Match {
256 /// Returns the identifier of the pattern that matched.
257 ///
258 /// The identifier of a pattern is derived from the position in which it
259 /// was originally inserted into the corresponding automaton. The first
260 /// pattern has identifier `0`, and each subsequent pattern is `1`, `2`
261 /// and so on.
262 #[inline]
263 pub fn pattern(&self) -> usize {
264 self.pattern
265 }
266
267 /// The starting position of the match.
268 #[inline]
269 pub fn start(&self) -> usize {
270 self.end - self.len
271 }
272
273 /// The ending position of the match.
274 #[inline]
275 pub fn end(&self) -> usize {
276 self.end
277 }
278
279 /// Returns true if and only if this match is empty. That is, when
280 /// `start() == end()`.
281 ///
282 /// An empty match can only be returned when the empty string was among
283 /// the patterns used to build the Aho-Corasick automaton.
284 #[inline]
285 pub fn is_empty(&self) -> bool {
286 self.len == 0
287 }
288
289 #[inline]
290 fn increment(&self, by: usize) -> Match {
291 Match { pattern: self.pattern, len: self.len, end: self.end + by }
292 }
293
294 #[inline]
295 fn from_span(id: usize, start: usize, end: usize) -> Match {
296 Match { pattern: id, len: end - start, end }
297 }
298}