      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296

    /*!
    A library for finding occurrences of many patterns at once. This library
    provides multiple pattern search principally through an implementation of the
    [Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm),
    which builds a fast finite state machine for executing searches in linear time.

    Additionally, this library provides a number of configuration options for
    building the automaton that permit controlling the space versus time trade
    off. Other features include simple ASCII case insensitive matching, finding
    overlapping matches, replacements, searching streams and even searching and
    replacing text in streams.

    Finally, unlike all other (known) Aho-Corasick implementations, this one
    supports enabling
    [leftmost-first](enum.MatchKind.html#variant.LeftmostFirst)
    or
    [leftmost-longest](enum.MatchKind.html#variant.LeftmostFirst)
    match semantics, using a (seemingly) novel alternative construction algorithm.
    For more details on what match semantics means, see the
    [`MatchKind`](enum.MatchKind.html)
    type.

    # Overview

    This section gives a brief overview of the primary types in this crate:

    * [`AhoCorasick`](struct.AhoCorasick.html) is the primary type and represents
      an Aho-Corasick automaton. This is the type you use to execute searches.
    * [`AhoCorasickBuilder`](struct.AhoCorasickBuilder.html) can be used to build
      an Aho-Corasick automaton, and supports configuring a number of options.
    * [`Match`](struct.Match.html) represents a single match reported by an
      Aho-Corasick automaton. Each match has two pieces of information: the pattern
      that matched and the start and end byte offsets corresponding to the position
      in the haystack at which it matched.

    # Example: basic searching

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

    ```
    use aho_corasick::AhoCorasick;

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

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

    # Example: case insensitivity

    This is like the previous example, but matches `Snapple` case insensitively
    using `AhoCorasickBuilder`:

    ```
    use aho_corasick::AhoCorasickBuilder;

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

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

    # Example: replacing matches in a stream

    This example shows how to execute a search and replace on a stream without
    loading the entire stream into memory first.

    ```
    use aho_corasick::AhoCorasick;

    # fn example() -> Result<(), ::std::io::Error> {
    let patterns = &["fox", "brown", "quick"];
    let replace_with = &["sloth", "grey", "slow"];

    // In a real example, these might be `std::fs::File`s instead. All you need to
    // do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
    let rdr = "The quick brown fox.";
    let mut wtr = vec![];

    let ac = AhoCorasick::new(patterns);
    ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)?;
    assert_eq!(b"The slow grey sloth.".to_vec(), wtr);
    # Ok(()) }; example().unwrap()
    ```

    # Example: finding the leftmost first match

    In the textbook description of Aho-Corasick, its formulation is typically
    structured such that it reports all possible matches, even when they overlap
    with another. In many cases, overlapping matches may not be desired, such as
    the case of finding all successive non-overlapping matches like you might with
    a standard regular expression.

    Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do
    this doesn't always work in the expected way, since it will report matches as
    soon as they are seen. For example, consider matching the regex `Samwise|Sam`
    against the text `Samwise`. Most regex engines (that are Perl-like, or
    non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick
    algorithm modified for reporting non-overlapping matches will report `Sam`.

    A novel contribution of this library is the ability to change the match
    semantics of Aho-Corasick (without additional search time overhead) such that
    `Samwise` is reported instead. For example, here's the standard approach:

    ```
    use aho_corasick::AhoCorasick;

    let patterns = &["Samwise", "Sam"];
    let haystack = "Samwise";

    let ac = AhoCorasick::new(patterns);
    let mat = ac.find(haystack).expect("should have a match");
    assert_eq!("Sam", &haystack[mat.start()..mat.end()]);
    ```

    And now here's the leftmost-first version, which matches how a Perl-like
    regex will work:

    ```
    use aho_corasick::{AhoCorasickBuilder, MatchKind};

    let patterns = &["Samwise", "Sam"];
    let haystack = "Samwise";

    let ac = AhoCorasickBuilder::new()
        .match_kind(MatchKind::LeftmostFirst)
        .build(patterns);
    let mat = ac.find(haystack).expect("should have a match");
    assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);
    ```

    In addition to leftmost-first semantics, this library also supports
    leftmost-longest semantics, which match the POSIX behavior of a regular
    expression alternation. See
    [`MatchKind`](enum.MatchKind.html)
    for more details.

    # Prefilters

    While an Aho-Corasick automaton can perform admirably when compared to more
    naive solutions, it is generally slower than more specialized algorithms that
    are accelerated using vector instructions such as SIMD.

    For that reason, this library will internally use a "prefilter" to attempt
    to accelerate searches when possible. Currently, this library has fairly
    limited implementation that only applies when there are 3 or fewer unique
    starting bytes among all patterns in an automaton.

    In the future, it is intended for this prefilter to grow more sophisticated
    by pushing applicable optimizations from the
    [`regex`](http://docs.rs/regex)
    crate (and other places) down into this library.

    While a prefilter is generally good to have on by default since it works well
    in the common case, it can lead to less predictable or even sub-optimal
    performance in some cases. For that reason, prefilters can be disabled via
    [`AhoCorasickBuilder::prefilter`](struct.AhoCorasickBuilder.html#method.prefilter).
    */

    #![deny(missing_docs)]
    #![allow(bare_trait_objects)]

    // We can never be truly no_std, but we could be alloc-only some day, so
    // require the std feature for now.
    #[cfg(not(feature = "std"))]
    compile_error!("`std` feature is currently required to build this crate");

    extern crate memchr;
    #[cfg(test)]
    #[macro_use]
    extern crate doc_comment;

    #[cfg(test)]
    doctest!("../README.md");

    pub use ahocorasick::{
        AhoCorasick, AhoCorasickBuilder, MatchKind,
        FindIter, FindOverlappingIter, StreamFindIter,
    };
    pub use error::{Error, ErrorKind};
    pub use state_id::StateID;

    mod ahocorasick;
    mod automaton;
    mod buffer;
    mod dfa;
    mod error;
    mod classes;
    mod prefilter;
    mod nfa;
    mod state_id;
    #[cfg(test)]
    mod tests;

    /// A representation of a match reported by an Aho-Corasick automaton.
    ///
    /// A match has two essential pieces of information: the identifier of the
    /// pattern that matched, along with the start and end offsets of the match
    /// in the haystack.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// use aho_corasick::AhoCorasick;
    ///
    /// let ac = AhoCorasick::new(&[
    ///     "foo", "bar", "baz",
    /// ]);
    /// let mat = ac.find("xxx bar xxx").expect("should have a match");
    /// assert_eq!(1, mat.pattern());
    /// assert_eq!(4, mat.start());
    /// assert_eq!(7, mat.end());
    /// ```
    #[derive(Clone, Debug, Eq, Hash, PartialEq)]
    pub struct Match {
        /// The pattern id.
        pattern: usize,
        /// The length of this match, such that the starting position of the match
        /// is `end - len`.
        ///
        /// We use length here because, other than the pattern id, the only
        /// information about each pattern that the automaton stores is its length.
        /// So using the length here is just a bit more natural. But it isn't
        /// technically required.
        len: usize,
        /// The end offset of the match, exclusive.
        end: usize,
    }

    impl Match {
        /// Returns the identifier of the pattern that matched.
        ///
        /// The identifier of a pattern is derived from the position in which it
        /// was originally inserted into the corresponding automaton. The first
        /// pattern has identifier `0`, and each subsequent pattern is `1`, `2`
        /// and so on.
        #[inline]
        pub fn pattern(&self) -> usize {
            self.pattern
        }

        /// The starting position of the match.
        #[inline]
        pub fn start(&self) -> usize {
            self.end - self.len
        }

        /// The ending position of the match.
        #[inline]
        pub fn end(&self) -> usize {
            self.end
        }

        /// Returns true if and only if this match is empty. That is, when
        /// `start() == end()`.
        ///
        /// An empty match can only be returned when the empty string was among
        /// the patterns used to build the Aho-Corasick automaton.
        #[inline]
        pub fn is_empty(&self) -> bool {
            self.len == 0
        }

        #[inline]
        fn increment(&self, by: usize) -> Match {
            Match {
                pattern: self.pattern,
                len: self.len,
                end: self.end + by,
            }
        }
    }

# Help

## Keyboard Shortcuts

`?`
  Show this help dialog
`S`
  Focus the search field
`↑`
  Move up in search results
`↓`
  Move down in search results
`↹`
  Switch tab
`⏎`
  Go to active search result
`+`
  Expand all sections
`-`
  Collapse all sections

## Search Tricks

Prefix searches with a type followed by a colon (e.g., `fn:`) to restrict the search to a given type.

Accepted types are: `fn`, `mod`, `struct`, `enum`, `trait`, `type`, `macro`, and `const`.

Search functions by type signature (e.g., `vec -> usize` or `* -> vec`)

Search multiple things at once by splitting your query with comma (e.g., `str,u8` or `String,struct:Vec,test`)