Debian Codegraph @

.cargo/vendor/aho-corasick/README.md

raw
1 aho-corasick
2 ============
3 A library for finding occurrences of many patterns at once with SIMD
4 acceleration in some cases. This library provides multiple pattern
5 search principally through an implementation of the
6 [Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm),
7 which builds a finite state machine for executing searches in linear time.
8 Features include case insensitive matching, overlapping matches, fast searching
9 via SIMD and optional full DFA construction and search & replace in streams.
10
11 [![Build status](https://github.com/BurntSushi/aho-corasick/workflows/ci/badge.svg)](https://github.com/BurntSushi/aho-corasick/actions)
12 [![crates.io](https://img.shields.io/crates/v/aho-corasick.svg)](https://crates.io/crates/aho-corasick)
13
14 Dual-licensed under MIT or the [UNLICENSE](https://unlicense.org/).
15
16
17 ### Documentation
18
19 https://docs.rs/aho-corasick
20
21
22 ### Usage
23
24 Run `cargo add aho-corasick` to automatically add this crate as a dependency
25 in your `Cargo.toml` file.
26
27
28 ### Example: basic searching
29
30 This example shows how to search for occurrences of multiple patterns
31 simultaneously. Each match includes the pattern that matched along with the
32 byte offsets of the match.
33
34 ```rust
35 use aho_corasick::{AhoCorasick, PatternID};
36
37 let patterns = &["apple", "maple", "Snapple"];
38 let haystack = "Nobody likes maple in their apple flavored Snapple.";
39
40 let ac = AhoCorasick::new(patterns).unwrap();
41 let mut matches = vec![];
42 for mat in ac.find_iter(haystack) {
43 matches.push((mat.pattern(), mat.start(), mat.end()));
44 }
45 assert_eq!(matches, vec![
46 (PatternID::must(1), 13, 18),
47 (PatternID::must(0), 28, 33),
48 (PatternID::must(2), 43, 50),
49 ]);
50 ```
51
52
53 ### Example: ASCII case insensitivity
54
55 This is like the previous example, but matches `Snapple` case insensitively
56 using `AhoCorasickBuilder`:
57
58 ```rust
59 use aho_corasick::{AhoCorasick, PatternID};
60
61 let patterns = &["apple", "maple", "snapple"];
62 let haystack = "Nobody likes maple in their apple flavored Snapple.";
63
64 let ac = AhoCorasick::builder()
65 .ascii_case_insensitive(true)
66 .build(patterns)
67 .unwrap();
68 let mut matches = vec![];
69 for mat in ac.find_iter(haystack) {
70 matches.push((mat.pattern(), mat.start(), mat.end()));
71 }
72 assert_eq!(matches, vec![
73 (PatternID::must(1), 13, 18),
74 (PatternID::must(0), 28, 33),
75 (PatternID::must(2), 43, 50),
76 ]);
77 ```
78
79
80 ### Example: replacing matches in a stream
81
82 This example shows how to execute a search and replace on a stream without
83 loading the entire stream into memory first.
84
85 ```rust,ignore
86 use aho_corasick::AhoCorasick;
87
88 let patterns = &["fox", "brown", "quick"];
89 let replace_with = &["sloth", "grey", "slow"];
90
91 // In a real example, these might be `std::fs::File`s instead. All you need to
92 // do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
93 let rdr = "The quick brown fox.";
94 let mut wtr = vec![];
95
96 let ac = AhoCorasick::new(patterns).unwrap();
97 ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)
98 .expect("stream_replace_all failed");
99 assert_eq!(b"The slow grey sloth.".to_vec(), wtr);
100 ```
101
102
103 ### Example: finding the leftmost first match
104
105 In the textbook description of Aho-Corasick, its formulation is typically
106 structured such that it reports all possible matches, even when they overlap
107 with another. In many cases, overlapping matches may not be desired, such as
108 the case of finding all successive non-overlapping matches like you might with
109 a standard regular expression.
110
111 Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do
112 this doesn't always work in the expected way, since it will report matches as
113 soon as they are seen. For example, consider matching the regex `Samwise|Sam`
114 against the text `Samwise`. Most regex engines (that are Perl-like, or
115 non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick
116 algorithm modified for reporting non-overlapping matches will report `Sam`.
117
118 A novel contribution of this library is the ability to change the match
119 semantics of Aho-Corasick (without additional search time overhead) such that
120 `Samwise` is reported instead. For example, here's the standard approach:
121
122 ```rust
123 use aho_corasick::AhoCorasick;
124
125 let patterns = &["Samwise", "Sam"];
126 let haystack = "Samwise";
127
128 let ac = AhoCorasick::new(patterns).unwrap();
129 let mat = ac.find(haystack).expect("should have a match");
130 assert_eq!("Sam", &haystack[mat.start()..mat.end()]);
131 ```
132
133 And now here's the leftmost-first version, which matches how a Perl-like
134 regex will work:
135
136 ```rust
137 use aho_corasick::{AhoCorasick, MatchKind};
138
139 let patterns = &["Samwise", "Sam"];
140 let haystack = "Samwise";
141
142 let ac = AhoCorasick::builder()
143 .match_kind(MatchKind::LeftmostFirst)
144 .build(patterns)
145 .unwrap();
146 let mat = ac.find(haystack).expect("should have a match");
147 assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);
148 ```
149
150 In addition to leftmost-first semantics, this library also supports
151 leftmost-longest semantics, which match the POSIX behavior of a regular
152 expression alternation. See `MatchKind` in the docs for more details.
153
154
155 ### Minimum Rust version policy
156
157 This crate's minimum supported `rustc` version is `1.60.0`.
158
159 The current policy is that the minimum Rust version required to use this crate
160 can be increased in minor version updates. For example, if `crate 1.0` requires
161 Rust 1.20.0, then `crate 1.0.z` for all values of `z` will also require Rust
162 1.20.0 or newer. However, `crate 1.y` for `y > 0` may require a newer minimum
163 version of Rust.
164
165 In general, this crate will be conservative with respect to the minimum
166 supported version of Rust.
167
168
169 ### FFI bindings
170
171 * [G-Research/ahocorasick_rs](https://github.com/G-Research/ahocorasick_rs/)
172 is a Python wrapper for this library.
173 * [tmikus/ahocorasick_rs](https://github.com/tmikus/ahocorasick_rs) is a Go
174 wrapper for this library.