vendor/aho-corasick/README.md

   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 [![](http://meritbadge.herokuapp.com/aho-corasick)](https://crates.io/crates/aho-corasick)
  13
  14 Dual-licensed under MIT or the [UNLICENSE](http://unlicense.org).
  15
  16
  17 ### Documentation
  18
  19 https://docs.rs/aho-corasick
  20
  21
  22 ### Usage
  23
  24 Add this to your `Cargo.toml`:
  25
  26 ```toml
  27 [dependencies]
  28 aho-corasick = "0.7"
  29 ```
  30
  31 and this to your crate root (if you're using Rust 2015):
  32
  33 ```rust
  34 extern crate aho_corasick;
  35 ```
  36
  37
  38 ### Example: basic searching
  39
  40 This example shows how to search for occurrences of multiple patterns
  41 simultaneously. Each match includes the pattern that matched along with the
  42 byte offsets of the match.
  43
  44 ```rust
  45 use aho_corasick::AhoCorasick;
  46
  47 let patterns = &["apple", "maple", "Snapple"];
  48 let haystack = "Nobody likes maple in their apple flavored Snapple.";
  49
  50 let ac = AhoCorasick::new(patterns);
  51 let mut matches = vec![];
  52 for mat in ac.find_iter(haystack) {
  53     matches.push((mat.pattern(), mat.start(), mat.end()));
  54 }
  55 assert_eq!(matches, vec![
  56     (1, 13, 18),
  57     (0, 28, 33),
  58     (2, 43, 50),
  59 ]);
  60 ```
  61
  62
  63 ### Example: case insensitivity
  64
  65 This is like the previous example, but matches `Snapple` case insensitively
  66 using `AhoCorasickBuilder`:
  67
  68 ```rust
  69 use aho_corasick::AhoCorasickBuilder;
  70
  71 let patterns = &["apple", "maple", "snapple"];
  72 let haystack = "Nobody likes maple in their apple flavored Snapple.";
  73
  74 let ac = AhoCorasickBuilder::new()
  75     .ascii_case_insensitive(true)
  76     .build(patterns);
  77 let mut matches = vec![];
  78 for mat in ac.find_iter(haystack) {
  79     matches.push((mat.pattern(), mat.start(), mat.end()));
  80 }
  81 assert_eq!(matches, vec![
  82     (1, 13, 18),
  83     (0, 28, 33),
  84     (2, 43, 50),
  85 ]);
  86 ```
  87
  88
  89 ### Example: replacing matches in a stream
  90
  91 This example shows how to execute a search and replace on a stream without
  92 loading the entire stream into memory first.
  93
  94 ```rust
  95 use aho_corasick::AhoCorasick;
  96
  97 let patterns = &["fox", "brown", "quick"];
  98 let replace_with = &["sloth", "grey", "slow"];
  99
 100 // In a real example, these might be `std::fs::File`s instead. All you need to
 101 // do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
 102 let rdr = "The quick brown fox.";
 103 let mut wtr = vec![];
 104
 105 let ac = AhoCorasick::new(patterns);
 106 ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)
 107     .expect("stream_replace_all failed");
 108 assert_eq!(b"The slow grey sloth.".to_vec(), wtr);
 109 ```
 110
 111
 112 ### Example: finding the leftmost first match
 113
 114 In the textbook description of Aho-Corasick, its formulation is typically
 115 structured such that it reports all possible matches, even when they overlap
 116 with another. In many cases, overlapping matches may not be desired, such as
 117 the case of finding all successive non-overlapping matches like you might with
 118 a standard regular expression.
 119
 120 Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do
 121 this doesn't always work in the expected way, since it will report matches as
 122 soon as they are seen. For example, consider matching the regex `Samwise|Sam`
 123 against the text `Samwise`. Most regex engines (that are Perl-like, or
 124 non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick
 125 algorithm modified for reporting non-overlapping matches will report `Sam`.
 126
 127 A novel contribution of this library is the ability to change the match
 128 semantics of Aho-Corasick (without additional search time overhead) such that
 129 `Samwise` is reported instead. For example, here's the standard approach:
 130
 131 ```rust
 132 use aho_corasick::AhoCorasick;
 133
 134 let patterns = &["Samwise", "Sam"];
 135 let haystack = "Samwise";
 136
 137 let ac = AhoCorasick::new(patterns);
 138 let mat = ac.find(haystack).expect("should have a match");
 139 assert_eq!("Sam", &haystack[mat.start()..mat.end()]);
 140 ```
 141
 142 And now here's the leftmost-first version, which matches how a Perl-like
 143 regex will work:
 144
 145 ```rust
 146 use aho_corasick::{AhoCorasickBuilder, MatchKind};
 147
 148 let patterns = &["Samwise", "Sam"];
 149 let haystack = "Samwise";
 150
 151 let ac = AhoCorasickBuilder::new()
 152     .match_kind(MatchKind::LeftmostFirst)
 153     .build(patterns);
 154 let mat = ac.find(haystack).expect("should have a match");
 155 assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);
 156 ```
 157
 158 In addition to leftmost-first semantics, this library also supports
 159 leftmost-longest semantics, which match the POSIX behavior of a regular
 160 expression alternation. See `MatchKind` in the docs for more details.
 161
 162
 163 ### Minimum Rust version policy
 164
 165 This crate's minimum supported `rustc` version is `1.28.0`.
 166
 167 The current policy is that the minimum Rust version required to use this crate
 168 can be increased in minor version updates. For example, if `crate 1.0` requires
 169 Rust 1.20.0, then `crate 1.0.z` for all values of `z` will also require Rust
 170 1.20.0 or newer. However, `crate 1.y` for `y > 0` may require a newer minimum
 171 version of Rust.
 172
 173 In general, this crate will be conservative with respect to the minimum
 174 supported version of Rust.
 175
 176
 177 ### Future work
 178
 179 Here are some plans for the future:
 180
 181 * Assuming the current API is sufficient, I'd like to commit to it and release
 182   a `1.0` version of this crate some time in the next 6-12 months.
 183 * Support stream searching with leftmost match semantics. Currently, only
 184   standard match semantics are supported. Getting this right seems possible,
 185   but is tricky since the match state needs to be propagated through multiple
 186   searches. (With standard semantics, as soon as a match is seen the search
 187   ends.)