      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
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    338
    339
    340
    341
    342
    343
    344
    345
    346
    347
    348
    349
    350
    351
    352
    353
    354
    355
    356
    357
    358
    359
    360
    361
    362
    363
    364
    365
    366
    367
    368
    369
    370
    371
    372
    373
    374
    375
    376
    377
    378
    379
    380
    381
    382
    383
    384
    385
    386
    387
    388
    389
    390
    391
    392
    393
    394
    395
    396
    397
    398
    399
    400
    401

    use ahocorasick::MatchKind;
    use prefilter::{Prefilter, PrefilterState};
    use state_id::{StateID, dead_id, fail_id};
    use Match;

    // NOTE: This trait was essentially copied from regex-automata, with some
    // wording changed since we use this trait for NFAs in addition to DFAs in this
    // crate. Additionally, we do not export this trait. It's only used internally
    // to reduce code duplication. The regex-automata crate needs to expose it
    // because its Regex type is generic over implementations of this trait. In
    // this crate, we can encapsulate everything behind the AhoCorasick type.

    /// A trait describing the interface of an Aho-Corasick finite state machine.
    ///
    /// Every automaton has exactly one fail state, one dead state and exactly one
    /// start state. Generally, these correspond to the first, second and third
    /// states, respectively. The failure state is always treated as a sentinel.
    /// That is, no correct Aho-Corasick automaton will ever transition into the
    /// fail state. The dead state, however, can be transitioned into, but only
    /// when leftmost-first or leftmost-longest match semantics are enabled and
    /// only when at least one match has been observed.
    ///
    /// Every automaton also has one or more match states, such that
    /// `Automaton::is_match_state_unchecked(id)` returns `true` if and only if
    /// `id` corresponds to a match state.
    pub trait Automaton {
        /// The representation used for state identifiers in this automaton.
        ///
        /// Typically, this is one of `u8`, `u16`, `u32`, `u64` or `usize`.
        type ID: StateID;

        /// The type of matching that should be done.
        fn match_kind(&self) -> &MatchKind;

        /// An optional prefilter for quickly skipping to the next candidate match.
        /// A prefilter must report at least every match, although it may report
        /// positions that do not correspond to a match. That is, it must not allow
        /// false negatives, but can allow false positives.
        ///
        /// Currently, a prefilter only runs when the automaton is in the start
        /// state. That is, the position reported by a prefilter should always
        /// correspond to the start of a potential match.
        fn prefilter(&self) -> Option<&Prefilter>;

        /// Return the identifier of this automaton's start state.
        fn start_state(&self) -> Self::ID;

        /// Returns true if and only if the given state identifier refers to a
        /// valid state.
        fn is_valid(&self, id: Self::ID) -> bool;

        /// Returns true if and only if the given identifier corresponds to a match
        /// state.
        ///
        /// The state ID given must be valid, or else implementors may panic.
        fn is_match_state(&self, id: Self::ID) -> bool;

        /// Returns true if and only if the given identifier corresponds to a state
        /// that is either the dead state or a match state.
        ///
        /// Depending on the implementation of the automaton, this routine can
        /// be used to save a branch in the core matching loop. Nevertheless,
        /// `is_match_state(id) || id == dead_id()` is always a valid
        /// implementation. Indeed, this is the default implementation.
        ///
        /// The state ID given must be valid, or else implementors may panic.
        fn is_match_or_dead_state(&self, id: Self::ID) -> bool {
            id == dead_id() || self.is_match_state(id)
        }

        /// If the given state is a match state, return the match corresponding
        /// to the given match index. `end` must be the ending position of the
        /// detected match. If no match exists or if `match_index` exceeds the
        /// number of matches in this state, then `None` is returned.
        ///
        /// The state ID given must be valid, or else implementors may panic.
        ///
        /// If the given state ID is correct and if the `match_index` is less than
        /// the number of matches for that state, then this is guaranteed to return
        /// a match.
        fn get_match(
            &self,
            id: Self::ID,
            match_index: usize,
            end: usize,
        ) -> Option<Match>;

        /// Returns the number of matches for the given state. If the given state
        /// is not a match state, then this returns 0.
        ///
        /// The state ID given must be valid, or else implementors must panic.
        fn match_count(&self, id: Self::ID) -> usize;

        /// Given the current state that this automaton is in and the next input
        /// byte, this method returns the identifier of the next state. The
        /// identifier returned must always be valid and may never correspond to
        /// the fail state. The returned identifier may, however, point to the
        /// dead state.
        ///
        /// This is not safe so that implementors may look up the next state
        /// without memory safety checks such as bounds checks. As such, callers
        /// must ensure that the given identifier corresponds to a valid automaton
        /// state. Implementors must, in turn, ensure that this routine is safe for
        /// all valid state identifiers and for all possible `u8` values.
        unsafe fn next_state_unchecked(
            &self,
            current: Self::ID,
            input: u8,
        ) -> Self::ID;

        /// Like next_state_unchecked, but debug_asserts that the underlying
        /// implementation never returns a `fail_id()` for the next state.
        unsafe fn next_state_unchecked_no_fail(
            &self,
            current: Self::ID,
            input: u8,
        ) -> Self::ID {
            let next = self.next_state_unchecked(current, input);
            // We should never see a transition to the failure state.
            debug_assert!(
                next != fail_id(),
                "automaton should never return fail_id for next state"
            );
            next
        }

        /// Execute a search using standard match semantics.
        ///
        /// This can be used even when the automaton was constructed with leftmost
        /// match semantics when you want to find the earliest possible match. This
        /// can also be used as part of an overlapping search implementation.
        ///
        /// N.B. This does not report a match if `state_id` is given as a matching
        /// state. As such, this should not be used directly.
        #[inline(always)]
        fn standard_find_at(
            &self,
            prestate: &mut PrefilterState,
            haystack: &[u8],
            at: usize,
            state_id: &mut Self::ID,
        ) -> Option<Match> {
            if let Some(pre) = self.prefilter() {
                self.standard_find_at_imp(
                    prestate, Some(pre), haystack, at, state_id,
                )
            } else {
                self.standard_find_at_imp(
                    prestate, None, haystack, at, state_id,
                )
            }
        }

        // It's important for this to always be inlined. Namely, it's only caller
        // is standard_find_at, and the inlining should remove the case analysis
        // for prefilter scanning when there is no prefilter available.
        #[inline(always)]
        fn standard_find_at_imp(
            &self,
            prestate: &mut PrefilterState,
            prefilter: Option<&Prefilter>,
            haystack: &[u8],
            at: usize,
            state_id: &mut Self::ID,
        ) -> Option<Match> {
            // This is necessary for guaranteeing a safe API, since we use the
            // state ID below in a function that exhibits UB if called with an
            // invalid state ID.
            assert!(
                self.is_valid(*state_id),
                "{} is not a valid state ID",
                state_id.to_usize()
            );
            unsafe {
                let start = haystack.as_ptr();
                let end = haystack[haystack.len()..].as_ptr();
                let mut ptr = haystack[at..].as_ptr();
                while ptr < end {
                    if let Some(pre) = prefilter {
                        if prestate.is_effective()
                            && *state_id == self.start_state()
                        {
                            let at = ptr as usize - start as usize;
                            match pre.next_candidate(haystack, at) {
                                None => return None,
                                Some(i) => {
                                    prestate.update(i - at);
                                    ptr = start.offset(i as isize);
                                }
                            }
                        }
                    }
                    // SAFETY: next_state is safe for all possible u8 values,
                    // so the only thing we're concerned about is the validity
                    // of `state_id`. `state_id` either comes from the caller
                    // (in which case, we assert above that it is valid), or it
                    // comes from the return value of next_state, which is also
                    // guaranteed to be valid.
                    *state_id = self.next_state_unchecked_no_fail(*state_id, *ptr);
                    ptr = ptr.offset(1);
                    // This routine always quits immediately after seeing a
                    // match, and since dead states can only come after seeing
                    // a match, seeing a dead state here is impossible.
                    debug_assert!(
                        *state_id != dead_id(),
                        "standard find should never see a dead state"
                    );

                    let end = ptr as usize - start as usize;
                    if let Some(m) = self.get_match(*state_id, 0, end) {
                        return Some(m);
                    }
                }
                None
            }
        }

        /// Execute a search using leftmost (either first or longest) match
        /// semantics.
        ///
        /// The principle difference between searching with standard semantics and
        /// searching with leftmost semantics is that leftmost searching will
        /// continue searching even after a match has been found. Once a match
        /// is found, the search does not stop until either the haystack has been
        /// exhausted or a dead state is observed in the automaton. (Dead states
        /// only exist in automatons constructed with leftmost semantics.) That is,
        /// we rely on the construction of the automaton to tell us when to quit.
        #[inline(never)]
        fn leftmost_find_at(
            &self,
            prestate: &mut PrefilterState,
            haystack: &[u8],
            at: usize,
            state_id: &mut Self::ID,
        ) -> Option<Match> {
            if let Some(pre) = self.prefilter() {
                self.leftmost_find_at_imp(
                    prestate, Some(pre), haystack, at, state_id,
                )
            } else {
                self.leftmost_find_at_imp(
                    prestate, None, haystack, at, state_id,
                )
            }
        }

        // It's important for this to always be inlined. Namely, it's only caller
        // is leftmost_find_at, and the inlining should remove the case analysis
        // for prefilter scanning when there is no prefilter available.
        #[inline(always)]
        fn leftmost_find_at_imp(
            &self,
            prestate: &mut PrefilterState,
            prefilter: Option<&Prefilter>,
            haystack: &[u8],
            at: usize,
            state_id: &mut Self::ID,
        ) -> Option<Match> {
            debug_assert!(self.match_kind().is_leftmost());
            // This is necessary for guaranteeing a safe API, since we use the
            // state ID below in a function that exhibits UB if called with an
            // invalid state ID.
            assert!(
                self.is_valid(*state_id),
                "{} is not a valid state ID",
                state_id.to_usize()
            );
            unsafe {
                let start = haystack.as_ptr();
                let end = haystack[haystack.len()..].as_ptr();
                let mut ptr = haystack[at..].as_ptr();

                let mut last_match = self.get_match(*state_id, 0, at);
                while ptr < end {
                    if let Some(pre) = prefilter {
                        if prestate.is_effective()
                            && *state_id == self.start_state()
                        {
                            let at = ptr as usize - start as usize;
                            match pre.next_candidate(haystack, at) {
                                None => return None,
                                Some(i) => {
                                    prestate.update(i - at);
                                    ptr = start.offset(i as isize);
                                }
                            }
                        }
                    }
                    // SAFETY: next_state is safe for all possible u8 values,
                    // so the only thing we're concerned about is the validity
                    // of `state_id`. `state_id` either comes from the caller
                    // (in which case, we assert above that it is valid), or it
                    // comes from the return value of next_state, which is also
                    // guaranteed to be valid.
                    *state_id = self.next_state_unchecked_no_fail(*state_id, *ptr);
                    ptr = ptr.offset(1);
                    if self.is_match_or_dead_state(*state_id) {
                        if *state_id == dead_id() {
                            // The only way to enter into a dead state is if a
                            // match has been found, so we assert as much. This
                            // is different from normal automata, where you might
                            // enter a dead state if you know a subsequent match
                            // will never be found (regardless of whether a match
                            // has already been found). For Aho-Corasick, it is
                            // built so that we can match at any position, so the
                            // possibility of a match always exists.
                            debug_assert!(
                                last_match.is_some(),
                                "failure state should only be seen after match"
                            );
                            return last_match;
                        }
                        let end = ptr as usize - start as usize;
                        last_match = self.get_match(*state_id, 0, end);
                    }
                }
                last_match
            }
        }

        /// Execute an overlapping search.
        ///
        /// When executing an overlapping match, the previous state ID in addition
        /// to the previous match index should be given. If there are more matches
        /// at the given state, then the match is reported and the given index is
        /// incremented.
        #[inline(always)]
        fn overlapping_find_at(
            &self,
            prestate: &mut PrefilterState,
            haystack: &[u8],
            at: usize,
            state_id: &mut Self::ID,
            match_index: &mut usize,
        ) -> Option<Match> {
            let match_count = self.match_count(*state_id);
            if *match_index < match_count {
                // This is guaranteed to return a match since
                // match_index < match_count.
                let result = self.get_match(
                    *state_id,
                    *match_index,
                    at,
                );
                debug_assert!(result.is_some(), "must be a match");
                *match_index += 1;
                return result;
            }

            *match_index = 0;
            match self.standard_find_at(prestate, haystack, at, state_id) {
                None => None,
                Some(m) => {
                    *match_index = 1;
                    Some(m)
                }
            }
        }

        /// Return the earliest match found. This returns as soon as we know that
        /// we have a match. As such, this does not necessarily correspond to the
        /// leftmost starting match, but rather, the leftmost position at which a
        /// match ends.
        #[inline(always)]
        fn earliest_find_at(
            &self,
            prestate: &mut PrefilterState,
            haystack: &[u8],
            at: usize,
            state_id: &mut Self::ID,
        ) -> Option<Match> {
            if *state_id == self.start_state() {
                if let Some(m) = self.get_match(*state_id, 0, at) {
                    return Some(m);
                }
            }
            self.standard_find_at(prestate, haystack, at, state_id)
        }

        /// A convenience function for finding the next match according to the
        /// match semantics of this automaton. For standard match semantics, this
        /// finds the earliest match. Otherwise, the leftmost match is found.
        #[inline(always)]
        fn find_at(
            &self,
            prestate: &mut PrefilterState,
            haystack: &[u8],
            at: usize,
            state_id: &mut Self::ID,
        ) -> Option<Match> {
            match *self.match_kind() {
                MatchKind::Standard => {
                    self.earliest_find_at(prestate, haystack, at, state_id)
                }
                MatchKind::LeftmostFirst | MatchKind::LeftmostLongest => {
                    self.leftmost_find_at(prestate, haystack, at, state_id)
                }
                MatchKind::__Nonexhaustive => unreachable!(),
            }
        }
    }

# 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`)