| 1 |
/*! |
| 2 |
Provides a noncontiguous NFA implementation of Aho-Corasick. |
| 3 |
|
| 4 |
This is a low-level API that generally only needs to be used in niche |
| 5 |
circumstances. When possible, prefer using [`AhoCorasick`](crate::AhoCorasick) |
| 6 |
instead of a noncontiguous NFA directly. Using an `NFA` directly is typically |
| 7 |
only necessary when one needs access to the [`Automaton`] trait implementation. |
| 8 |
*/ |
| 9 |
|
| 10 |
use alloc::{ |
| 11 |
collections::{BTreeSet, VecDeque}, |
| 12 |
vec, |
| 13 |
vec::Vec, |
| 14 |
}; |
| 15 |
|
| 16 |
use crate::{ |
| 17 |
automaton::Automaton, |
| 18 |
util::{ |
| 19 |
alphabet::{ByteClassSet, ByteClasses}, |
| 20 |
error::{BuildError, MatchError}, |
| 21 |
prefilter::{self, opposite_ascii_case, Prefilter}, |
| 22 |
primitives::{IteratorIndexExt, PatternID, SmallIndex, StateID}, |
| 23 |
remapper::Remapper, |
| 24 |
search::{Anchored, MatchKind}, |
| 25 |
special::Special, |
| 26 |
}, |
| 27 |
}; |
| 28 |
|
| 29 |
/// A noncontiguous NFA implementation of Aho-Corasick. |
| 30 |
/// |
| 31 |
/// When possible, prefer using [`AhoCorasick`](crate::AhoCorasick) instead of |
| 32 |
/// this type directly. Using an `NFA` directly is typically only necessary |
| 33 |
/// when one needs access to the [`Automaton`] trait implementation. |
| 34 |
/// |
| 35 |
/// This NFA represents the "core" implementation of Aho-Corasick in this |
| 36 |
/// crate. Namely, constructing this NFA involving building a trie and then |
| 37 |
/// filling in the failure transitions between states, similar to what is |
| 38 |
/// described in any standard textbook description of Aho-Corasick. |
| 39 |
/// |
| 40 |
/// In order to minimize heap usage and to avoid additional construction costs, |
| 41 |
/// this implementation represents the transitions of all states as distinct |
| 42 |
/// sparse memory allocations. This is where it gets its name from. That is, |
| 43 |
/// this NFA has no contiguous memory allocation for its transition table. Each |
| 44 |
/// state gets its own allocation. |
| 45 |
/// |
| 46 |
/// While the sparse representation keeps memory usage to somewhat reasonable |
| 47 |
/// levels, it is still quite large and also results in somewhat mediocre |
| 48 |
/// search performance. For this reason, it is almost always a good idea to |
| 49 |
/// use a [`contiguous::NFA`](crate::nfa::contiguous::NFA) instead. It is |
| 50 |
/// marginally slower to build, but has higher throughput and can sometimes use |
| 51 |
/// an order of magnitude less memory. The main reason to use a noncontiguous |
| 52 |
/// NFA is when you need the fastest possible construction time, or when a |
| 53 |
/// contiguous NFA does not have the desired capacity. (The total number of NFA |
| 54 |
/// states it can have is fewer than a noncontiguous NFA.) |
| 55 |
/// |
| 56 |
/// # Example |
| 57 |
/// |
| 58 |
/// This example shows how to build an `NFA` directly and use it to execute |
| 59 |
/// [`Automaton::try_find`]: |
| 60 |
/// |
| 61 |
/// ``` |
| 62 |
/// use aho_corasick::{ |
| 63 |
/// automaton::Automaton, |
| 64 |
/// nfa::noncontiguous::NFA, |
| 65 |
/// Input, Match, |
| 66 |
/// }; |
| 67 |
/// |
| 68 |
/// let patterns = &["b", "abc", "abcd"]; |
| 69 |
/// let haystack = "abcd"; |
| 70 |
/// |
| 71 |
/// let nfa = NFA::new(patterns).unwrap(); |
| 72 |
/// assert_eq!( |
| 73 |
/// Some(Match::must(0, 1..2)), |
| 74 |
/// nfa.try_find(&Input::new(haystack))?, |
| 75 |
/// ); |
| 76 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 77 |
/// ``` |
| 78 |
/// |
| 79 |
/// It is also possible to implement your own version of `try_find`. See the |
| 80 |
/// [`Automaton`] documentation for an example. |
| 81 |
#[derive(Clone)] |
| 82 |
pub struct NFA { |
| 83 |
/// The match semantics built into this NFA. |
| 84 |
match_kind: MatchKind, |
| 85 |
/// A set of states. Each state defines its own transitions, a fail |
| 86 |
/// transition and a set of indices corresponding to matches. |
| 87 |
/// |
| 88 |
/// The first state is always the fail state, which is used only as a |
| 89 |
/// sentinel. Namely, in the final NFA, no transition into the fail state |
| 90 |
/// exists. (Well, they do, but they aren't followed. Instead, the state's |
| 91 |
/// failure transition is followed.) |
| 92 |
/// |
| 93 |
/// The second state (index 1) is always the dead state. Dead states are |
| 94 |
/// in every automaton, but only used when leftmost-{first,longest} match |
| 95 |
/// semantics are enabled. Specifically, they instruct search to stop |
| 96 |
/// at specific points in order to report the correct match location. In |
| 97 |
/// the standard Aho-Corasick construction, there are no transitions to |
| 98 |
/// the dead state. |
| 99 |
/// |
| 100 |
/// The third state (index 2) is generally intended to be the starting or |
| 101 |
/// "root" state. |
| 102 |
states: Vec<State>, |
| 103 |
/// Transitions stored in a sparse representation via a linked list. |
| 104 |
/// |
| 105 |
/// Each transition contains three pieces of information: the byte it |
| 106 |
/// is defined for, the state it transitions to and a link to the next |
| 107 |
/// transition in the same state (or `StateID::ZERO` if it is the last |
| 108 |
/// transition). |
| 109 |
/// |
| 110 |
/// The first transition for each state is determined by `State::sparse`. |
| 111 |
/// |
| 112 |
/// Note that this contains a complete set of all transitions in this NFA, |
| 113 |
/// including states that have a dense representation for transitions. |
| 114 |
/// (Adding dense transitions for a state doesn't remove its sparse |
| 115 |
/// transitions, since deleting transitions from this particular sparse |
| 116 |
/// representation would be fairly expensive.) |
| 117 |
sparse: Vec<Transition>, |
| 118 |
/// Transitions stored in a dense representation. |
| 119 |
/// |
| 120 |
/// A state has a row in this table if and only if `State::dense` is |
| 121 |
/// not equal to `StateID::ZERO`. When not zero, there are precisely |
| 122 |
/// `NFA::byte_classes::alphabet_len()` entries beginning at `State::dense` |
| 123 |
/// in this table. |
| 124 |
/// |
| 125 |
/// Generally a very small minority of states have a dense representation |
| 126 |
/// since it uses so much memory. |
| 127 |
dense: Vec<StateID>, |
| 128 |
/// Matches stored in linked list for each state. |
| 129 |
/// |
| 130 |
/// Like sparse transitions, each match has a link to the next match in the |
| 131 |
/// state. |
| 132 |
/// |
| 133 |
/// The first match for each state is determined by `State::matches`. |
| 134 |
matches: Vec<Match>, |
| 135 |
/// The length, in bytes, of each pattern in this NFA. This slice is |
| 136 |
/// indexed by `PatternID`. |
| 137 |
/// |
| 138 |
/// The number of entries in this vector corresponds to the total number of |
| 139 |
/// patterns in this automaton. |
| 140 |
pattern_lens: Vec<SmallIndex>, |
| 141 |
/// A prefilter for quickly skipping to candidate matches, if pertinent. |
| 142 |
prefilter: Option<Prefilter>, |
| 143 |
/// A set of equivalence classes in terms of bytes. We compute this while |
| 144 |
/// building the NFA, but don't use it in the NFA's states. Instead, we |
| 145 |
/// use this for building the DFA. We store it on the NFA since it's easy |
| 146 |
/// to compute while visiting the patterns. |
| 147 |
byte_classes: ByteClasses, |
| 148 |
/// The length, in bytes, of the shortest pattern in this automaton. This |
| 149 |
/// information is useful for detecting whether an automaton matches the |
| 150 |
/// empty string or not. |
| 151 |
min_pattern_len: usize, |
| 152 |
/// The length, in bytes, of the longest pattern in this automaton. This |
| 153 |
/// information is useful for keeping correct buffer sizes when searching |
| 154 |
/// on streams. |
| 155 |
max_pattern_len: usize, |
| 156 |
/// The information required to deduce which states are "special" in this |
| 157 |
/// NFA. |
| 158 |
/// |
| 159 |
/// Since the DEAD and FAIL states are always the first two states and |
| 160 |
/// there are only ever two start states (which follow all of the match |
| 161 |
/// states), it follows that we can determine whether a state is a fail, |
| 162 |
/// dead, match or start with just a few comparisons on the ID itself: |
| 163 |
/// |
| 164 |
/// is_dead(sid): sid == NFA::DEAD |
| 165 |
/// is_fail(sid): sid == NFA::FAIL |
| 166 |
/// is_match(sid): NFA::FAIL < sid && sid <= max_match_id |
| 167 |
/// is_start(sid): sid == start_unanchored_id || sid == start_anchored_id |
| 168 |
/// |
| 169 |
/// Note that this only applies to the NFA after it has been constructed. |
| 170 |
/// During construction, the start states are the first ones added and the |
| 171 |
/// match states are inter-leaved with non-match states. Once all of the |
| 172 |
/// states have been added, the states are shuffled such that the above |
| 173 |
/// predicates hold. |
| 174 |
special: Special, |
| 175 |
} |
| 176 |
|
| 177 |
impl NFA { |
| 178 |
/// Create a new Aho-Corasick noncontiguous NFA using the default |
| 179 |
/// configuration. |
| 180 |
/// |
| 181 |
/// Use a [`Builder`] if you want to change the configuration. |
| 182 |
pub fn new<I, P>(patterns: I) -> Result<NFA, BuildError> |
| 183 |
where |
| 184 |
I: IntoIterator<Item = P>, |
| 185 |
P: AsRef<[u8]>, |
| 186 |
{ |
| 187 |
NFA::builder().build(patterns) |
| 188 |
} |
| 189 |
|
| 190 |
/// A convenience method for returning a new Aho-Corasick noncontiguous NFA |
| 191 |
/// builder. |
| 192 |
/// |
| 193 |
/// This usually permits one to just import the `NFA` type. |
| 194 |
pub fn builder() -> Builder { |
| 195 |
Builder::new() |
| 196 |
} |
| 197 |
} |
| 198 |
|
| 199 |
impl NFA { |
| 200 |
/// The DEAD state is a sentinel state like the FAIL state. The DEAD state |
| 201 |
/// instructs any search to stop and return any currently recorded match, |
| 202 |
/// or no match otherwise. Generally speaking, it is impossible for an |
| 203 |
/// unanchored standard search to enter a DEAD state. But an anchored |
| 204 |
/// search can, and so to can a leftmost search. |
| 205 |
/// |
| 206 |
/// We put DEAD before FAIL so that DEAD is always 0. We repeat this |
| 207 |
/// decision across the other Aho-Corasicm automata, so that DEAD |
| 208 |
/// states there are always 0 too. It's not that we need all of the |
| 209 |
/// implementations to agree, but rather, the contiguous NFA and the DFA |
| 210 |
/// use a sort of "premultiplied" state identifier where the only state |
| 211 |
/// whose ID is always known and constant is the first state. Subsequent |
| 212 |
/// state IDs depend on how much space has already been used in the |
| 213 |
/// transition table. |
| 214 |
pub(crate) const DEAD: StateID = StateID::new_unchecked(0); |
| 215 |
/// The FAIL state mostly just corresponds to the ID of any transition on a |
| 216 |
/// state that isn't explicitly defined. When one transitions into the FAIL |
| 217 |
/// state, one must follow the previous state's failure transition before |
| 218 |
/// doing the next state lookup. In this way, FAIL is more of a sentinel |
| 219 |
/// than a state that one actually transitions into. In particular, it is |
| 220 |
/// never exposed in the `Automaton` interface. |
| 221 |
pub(crate) const FAIL: StateID = StateID::new_unchecked(1); |
| 222 |
|
| 223 |
/// Returns the equivalence classes of bytes found while constructing |
| 224 |
/// this NFA. |
| 225 |
/// |
| 226 |
/// Note that the NFA doesn't actually make use of these equivalence |
| 227 |
/// classes. Instead, these are useful for building the DFA when desired. |
| 228 |
pub(crate) fn byte_classes(&self) -> &ByteClasses { |
| 229 |
&self.byte_classes |
| 230 |
} |
| 231 |
|
| 232 |
/// Returns a slice containing the length of each pattern in this searcher. |
| 233 |
/// It is indexed by `PatternID` and has length `NFA::patterns_len`. |
| 234 |
/// |
| 235 |
/// This is exposed for convenience when building a contiguous NFA. But it |
| 236 |
/// can be reconstructed from the `Automaton` API if necessary. |
| 237 |
pub(crate) fn pattern_lens_raw(&self) -> &[SmallIndex] { |
| 238 |
&self.pattern_lens |
| 239 |
} |
| 240 |
|
| 241 |
/// Returns a slice of all states in this non-contiguous NFA. |
| 242 |
pub(crate) fn states(&self) -> &[State] { |
| 243 |
&self.states |
| 244 |
} |
| 245 |
|
| 246 |
/// Returns the underlying "special" state information for this NFA. |
| 247 |
pub(crate) fn special(&self) -> &Special { |
| 248 |
&self.special |
| 249 |
} |
| 250 |
|
| 251 |
/// Swaps the states at `id1` and `id2`. |
| 252 |
/// |
| 253 |
/// This does not update the transitions of any state to account for the |
| 254 |
/// state swap. |
| 255 |
pub(crate) fn swap_states(&mut self, id1: StateID, id2: StateID) { |
| 256 |
self.states.swap(id1.as_usize(), id2.as_usize()); |
| 257 |
} |
| 258 |
|
| 259 |
/// Re-maps all state IDs in this NFA according to the `map` function |
| 260 |
/// given. |
| 261 |
pub(crate) fn remap(&mut self, map: impl Fn(StateID) -> StateID) { |
| 262 |
let alphabet_len = self.byte_classes.alphabet_len(); |
| 263 |
for state in self.states.iter_mut() { |
| 264 |
state.fail = map(state.fail); |
| 265 |
let mut link = state.sparse; |
| 266 |
while link != StateID::ZERO { |
| 267 |
let t = &mut self.sparse[link]; |
| 268 |
t.next = map(t.next); |
| 269 |
link = t.link; |
| 270 |
} |
| 271 |
if state.dense != StateID::ZERO { |
| 272 |
let start = state.dense.as_usize(); |
| 273 |
for next in self.dense[start..][..alphabet_len].iter_mut() { |
| 274 |
*next = map(*next); |
| 275 |
} |
| 276 |
} |
| 277 |
} |
| 278 |
} |
| 279 |
|
| 280 |
/// Iterate over all of the transitions for the given state ID. |
| 281 |
pub(crate) fn iter_trans( |
| 282 |
&self, |
| 283 |
sid: StateID, |
| 284 |
) -> impl Iterator<Item = Transition> + '_ { |
| 285 |
let mut link = self.states[sid].sparse; |
| 286 |
core::iter::from_fn(move || { |
| 287 |
if link == StateID::ZERO { |
| 288 |
return None; |
| 289 |
} |
| 290 |
let t = self.sparse[link]; |
| 291 |
link = t.link; |
| 292 |
Some(t) |
| 293 |
}) |
| 294 |
} |
| 295 |
|
| 296 |
/// Iterate over all of the matches for the given state ID. |
| 297 |
pub(crate) fn iter_matches( |
| 298 |
&self, |
| 299 |
sid: StateID, |
| 300 |
) -> impl Iterator<Item = PatternID> + '_ { |
| 301 |
let mut link = self.states[sid].matches; |
| 302 |
core::iter::from_fn(move || { |
| 303 |
if link == StateID::ZERO { |
| 304 |
return None; |
| 305 |
} |
| 306 |
let m = self.matches[link]; |
| 307 |
link = m.link; |
| 308 |
Some(m.pid) |
| 309 |
}) |
| 310 |
} |
| 311 |
|
| 312 |
/// Return the link following the one given. If the one given is the last |
| 313 |
/// link for the given state, then return `None`. |
| 314 |
/// |
| 315 |
/// If no previous link is given, then this returns the first link in the |
| 316 |
/// state, if one exists. |
| 317 |
/// |
| 318 |
/// This is useful for manually iterating over the transitions in a single |
| 319 |
/// state without borrowing the NFA. This permits mutating other parts of |
| 320 |
/// the NFA during iteration. Namely, one can access the transition pointed |
| 321 |
/// to by the link via `self.sparse[link]`. |
| 322 |
fn next_link( |
| 323 |
&self, |
| 324 |
sid: StateID, |
| 325 |
prev: Option<StateID>, |
| 326 |
) -> Option<StateID> { |
| 327 |
let link = |
| 328 |
prev.map_or(self.states[sid].sparse, |p| self.sparse[p].link); |
| 329 |
if link == StateID::ZERO { |
| 330 |
None |
| 331 |
} else { |
| 332 |
Some(link) |
| 333 |
} |
| 334 |
} |
| 335 |
|
| 336 |
/// Follow the transition for the given byte in the given state. If no such |
| 337 |
/// transition exists, then the FAIL state ID is returned. |
| 338 |
#[inline(always)] |
| 339 |
fn follow_transition(&self, sid: StateID, byte: u8) -> StateID { |
| 340 |
let s = &self.states[sid]; |
| 341 |
// This is a special case that targets starting states and states |
| 342 |
// near a start state. Namely, after the initial trie is constructed, |
| 343 |
// we look for states close to the start state to convert to a dense |
| 344 |
// representation for their transitions. This winds up using a lot more |
| 345 |
// memory per state in exchange for faster transition lookups. But |
| 346 |
// since we only do this for a small number of states (by default), the |
| 347 |
// memory usage is usually minimal. |
| 348 |
// |
| 349 |
// This has *massive* benefit when executing searches because the |
| 350 |
// unanchored starting state is by far the hottest state and is |
| 351 |
// frequently visited. Moreover, the 'for' loop below that works |
| 352 |
// decently on an actually sparse state is disastrous on a state that |
| 353 |
// is nearly or completely dense. |
| 354 |
if s.dense == StateID::ZERO { |
| 355 |
self.follow_transition_sparse(sid, byte) |
| 356 |
} else { |
| 357 |
let class = usize::from(self.byte_classes.get(byte)); |
| 358 |
self.dense[s.dense.as_usize() + class] |
| 359 |
} |
| 360 |
} |
| 361 |
|
| 362 |
/// Like `follow_transition`, but always uses the sparse representation. |
| 363 |
#[inline(always)] |
| 364 |
fn follow_transition_sparse(&self, sid: StateID, byte: u8) -> StateID { |
| 365 |
for t in self.iter_trans(sid) { |
| 366 |
if byte <= t.byte { |
| 367 |
if byte == t.byte { |
| 368 |
return t.next; |
| 369 |
} |
| 370 |
break; |
| 371 |
} |
| 372 |
} |
| 373 |
NFA::FAIL |
| 374 |
} |
| 375 |
|
| 376 |
/// Set the transition for the given byte to the state ID given. |
| 377 |
/// |
| 378 |
/// Note that one should not set transitions to the FAIL state. It is not |
| 379 |
/// technically incorrect, but it wastes space. If a transition is not |
| 380 |
/// defined, then it is automatically assumed to lead to the FAIL state. |
| 381 |
fn add_transition( |
| 382 |
&mut self, |
| 383 |
prev: StateID, |
| 384 |
byte: u8, |
| 385 |
next: StateID, |
| 386 |
) -> Result<(), BuildError> { |
| 387 |
if self.states[prev].dense != StateID::ZERO { |
| 388 |
let dense = self.states[prev].dense; |
| 389 |
let class = usize::from(self.byte_classes.get(byte)); |
| 390 |
self.dense[dense.as_usize() + class] = next; |
| 391 |
} |
| 392 |
|
| 393 |
let head = self.states[prev].sparse; |
| 394 |
if head == StateID::ZERO || byte < self.sparse[head].byte { |
| 395 |
let new_link = self.alloc_transition()?; |
| 396 |
self.sparse[new_link] = Transition { byte, next, link: head }; |
| 397 |
self.states[prev].sparse = new_link; |
| 398 |
return Ok(()); |
| 399 |
} else if byte == self.sparse[head].byte { |
| 400 |
self.sparse[head].next = next; |
| 401 |
return Ok(()); |
| 402 |
} |
| 403 |
|
| 404 |
// We handled the only cases where the beginning of the transition |
| 405 |
// chain needs to change. At this point, we now know that there is |
| 406 |
// at least one entry in the transition chain and the byte for that |
| 407 |
// transition is less than the byte for the transition we're adding. |
| 408 |
let (mut link_prev, mut link_next) = (head, self.sparse[head].link); |
| 409 |
while link_next != StateID::ZERO && byte > self.sparse[link_next].byte |
| 410 |
{ |
| 411 |
link_prev = link_next; |
| 412 |
link_next = self.sparse[link_next].link; |
| 413 |
} |
| 414 |
if link_next == StateID::ZERO || byte < self.sparse[link_next].byte { |
| 415 |
let link = self.alloc_transition()?; |
| 416 |
self.sparse[link] = Transition { byte, next, link: link_next }; |
| 417 |
self.sparse[link_prev].link = link; |
| 418 |
} else { |
| 419 |
assert_eq!(byte, self.sparse[link_next].byte); |
| 420 |
self.sparse[link_next].next = next; |
| 421 |
} |
| 422 |
Ok(()) |
| 423 |
} |
| 424 |
|
| 425 |
/// This sets every possible transition (all 255 of them) for the given |
| 426 |
/// state to the name `next` value. |
| 427 |
/// |
| 428 |
/// This is useful for efficiently initializing start/dead states. |
| 429 |
/// |
| 430 |
/// # Panics |
| 431 |
/// |
| 432 |
/// This requires that the state has no transitions added to it already. |
| 433 |
/// If it has any transitions, then this panics. It will also panic if |
| 434 |
/// the state has been densified prior to calling this. |
| 435 |
fn init_full_state( |
| 436 |
&mut self, |
| 437 |
prev: StateID, |
| 438 |
next: StateID, |
| 439 |
) -> Result<(), BuildError> { |
| 440 |
assert_eq!( |
| 441 |
StateID::ZERO, |
| 442 |
self.states[prev].dense, |
| 443 |
"state must not be dense yet" |
| 444 |
); |
| 445 |
assert_eq!( |
| 446 |
StateID::ZERO, |
| 447 |
self.states[prev].sparse, |
| 448 |
"state must have zero transitions" |
| 449 |
); |
| 450 |
let mut prev_link = StateID::ZERO; |
| 451 |
for byte in 0..=255 { |
| 452 |
let new_link = self.alloc_transition()?; |
| 453 |
self.sparse[new_link] = |
| 454 |
Transition { byte, next, link: StateID::ZERO }; |
| 455 |
if prev_link == StateID::ZERO { |
| 456 |
self.states[prev].sparse = new_link; |
| 457 |
} else { |
| 458 |
self.sparse[prev_link].link = new_link; |
| 459 |
} |
| 460 |
prev_link = new_link; |
| 461 |
} |
| 462 |
Ok(()) |
| 463 |
} |
| 464 |
|
| 465 |
/// Add a match for the given pattern ID to the state for the given ID. |
| 466 |
fn add_match( |
| 467 |
&mut self, |
| 468 |
sid: StateID, |
| 469 |
pid: PatternID, |
| 470 |
) -> Result<(), BuildError> { |
| 471 |
let head = self.states[sid].matches; |
| 472 |
let mut link = head; |
| 473 |
while self.matches[link].link != StateID::ZERO { |
| 474 |
link = self.matches[link].link; |
| 475 |
} |
| 476 |
let new_match_link = self.alloc_match()?; |
| 477 |
self.matches[new_match_link].pid = pid; |
| 478 |
if link == StateID::ZERO { |
| 479 |
self.states[sid].matches = new_match_link; |
| 480 |
} else { |
| 481 |
self.matches[link].link = new_match_link; |
| 482 |
} |
| 483 |
Ok(()) |
| 484 |
} |
| 485 |
|
| 486 |
/// Copy matches from the `src` state to the `dst` state. This is useful |
| 487 |
/// when a match state can be reached via a failure transition. In which |
| 488 |
/// case, you'll want to copy the matches (if any) from the state reached |
| 489 |
/// by the failure transition to the original state you were at. |
| 490 |
fn copy_matches( |
| 491 |
&mut self, |
| 492 |
src: StateID, |
| 493 |
dst: StateID, |
| 494 |
) -> Result<(), BuildError> { |
| 495 |
let head_dst = self.states[dst].matches; |
| 496 |
let mut link_dst = head_dst; |
| 497 |
while self.matches[link_dst].link != StateID::ZERO { |
| 498 |
link_dst = self.matches[link_dst].link; |
| 499 |
} |
| 500 |
let mut link_src = self.states[src].matches; |
| 501 |
while link_src != StateID::ZERO { |
| 502 |
let new_match_link = |
| 503 |
StateID::new(self.matches.len()).map_err(|e| { |
| 504 |
BuildError::state_id_overflow( |
| 505 |
StateID::MAX.as_u64(), |
| 506 |
e.attempted(), |
| 507 |
) |
| 508 |
})?; |
| 509 |
self.matches.push(Match { |
| 510 |
pid: self.matches[link_src].pid, |
| 511 |
link: StateID::ZERO, |
| 512 |
}); |
| 513 |
if link_dst == StateID::ZERO { |
| 514 |
self.states[dst].matches = new_match_link; |
| 515 |
} else { |
| 516 |
self.matches[link_dst].link = new_match_link; |
| 517 |
} |
| 518 |
|
| 519 |
link_dst = new_match_link; |
| 520 |
link_src = self.matches[link_src].link; |
| 521 |
} |
| 522 |
Ok(()) |
| 523 |
} |
| 524 |
|
| 525 |
/// Create a new entry in `NFA::trans`, if there's room, and return that |
| 526 |
/// entry's ID. If there's no room, then an error is returned. |
| 527 |
fn alloc_transition(&mut self) -> Result<StateID, BuildError> { |
| 528 |
let id = StateID::new(self.sparse.len()).map_err(|e| { |
| 529 |
BuildError::state_id_overflow(StateID::MAX.as_u64(), e.attempted()) |
| 530 |
})?; |
| 531 |
self.sparse.push(Transition::default()); |
| 532 |
Ok(id) |
| 533 |
} |
| 534 |
|
| 535 |
/// Create a new entry in `NFA::matches`, if there's room, and return that |
| 536 |
/// entry's ID. If there's no room, then an error is returned. |
| 537 |
fn alloc_match(&mut self) -> Result<StateID, BuildError> { |
| 538 |
let id = StateID::new(self.matches.len()).map_err(|e| { |
| 539 |
BuildError::state_id_overflow(StateID::MAX.as_u64(), e.attempted()) |
| 540 |
})?; |
| 541 |
self.matches.push(Match::default()); |
| 542 |
Ok(id) |
| 543 |
} |
| 544 |
|
| 545 |
/// Create a new set of `N` transitions in this NFA's dense transition |
| 546 |
/// table. The ID return corresponds to the index at which the `N` |
| 547 |
/// transitions begin. So `id+0` is the first transition and `id+(N-1)` is |
| 548 |
/// the last. |
| 549 |
/// |
| 550 |
/// `N` is determined via `NFA::byte_classes::alphabet_len`. |
| 551 |
fn alloc_dense_state(&mut self) -> Result<StateID, BuildError> { |
| 552 |
let id = StateID::new(self.dense.len()).map_err(|e| { |
| 553 |
BuildError::state_id_overflow(StateID::MAX.as_u64(), e.attempted()) |
| 554 |
})?; |
| 555 |
// We use FAIL because it's the correct default. If a state doesn't |
| 556 |
// have a transition defined for every possible byte value, then the |
| 557 |
// transition function should return NFA::FAIL. |
| 558 |
self.dense.extend( |
| 559 |
core::iter::repeat(NFA::FAIL) |
| 560 |
.take(self.byte_classes.alphabet_len()), |
| 561 |
); |
| 562 |
Ok(id) |
| 563 |
} |
| 564 |
|
| 565 |
/// Allocate and add a fresh state to the underlying NFA and return its |
| 566 |
/// ID (guaranteed to be one more than the ID of the previously allocated |
| 567 |
/// state). If the ID would overflow `StateID`, then this returns an error. |
| 568 |
fn alloc_state(&mut self, depth: usize) -> Result<StateID, BuildError> { |
| 569 |
// This is OK because we error when building the trie if we see a |
| 570 |
// pattern whose length cannot fit into a 'SmallIndex', and the longest |
| 571 |
// possible depth corresponds to the length of the longest pattern. |
| 572 |
let depth = SmallIndex::new(depth) |
| 573 |
.expect("patterns longer than SmallIndex::MAX are not allowed"); |
| 574 |
let id = StateID::new(self.states.len()).map_err(|e| { |
| 575 |
BuildError::state_id_overflow(StateID::MAX.as_u64(), e.attempted()) |
| 576 |
})?; |
| 577 |
self.states.push(State { |
| 578 |
sparse: StateID::ZERO, |
| 579 |
dense: StateID::ZERO, |
| 580 |
matches: StateID::ZERO, |
| 581 |
fail: self.special.start_unanchored_id, |
| 582 |
depth, |
| 583 |
}); |
| 584 |
Ok(id) |
| 585 |
} |
| 586 |
} |
| 587 |
|
| 588 |
// SAFETY: 'start_state' always returns a valid state ID, 'next_state' always |
| 589 |
// returns a valid state ID given a valid state ID. We otherwise claim that |
| 590 |
// all other methods are correct as well. |
| 591 |
unsafe impl Automaton for NFA { |
| 592 |
#[inline(always)] |
| 593 |
fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError> { |
| 594 |
match anchored { |
| 595 |
Anchored::No => Ok(self.special.start_unanchored_id), |
| 596 |
Anchored::Yes => Ok(self.special.start_anchored_id), |
| 597 |
} |
| 598 |
} |
| 599 |
|
| 600 |
#[inline(always)] |
| 601 |
fn next_state( |
| 602 |
&self, |
| 603 |
anchored: Anchored, |
| 604 |
mut sid: StateID, |
| 605 |
byte: u8, |
| 606 |
) -> StateID { |
| 607 |
// This terminates since: |
| 608 |
// |
| 609 |
// 1. state.fail never points to the FAIL state. |
| 610 |
// 2. All state.fail values point to a state closer to the start state. |
| 611 |
// 3. The start state has no transitions to the FAIL state. |
| 612 |
loop { |
| 613 |
let next = self.follow_transition(sid, byte); |
| 614 |
if next != NFA::FAIL { |
| 615 |
return next; |
| 616 |
} |
| 617 |
// For an anchored search, we never follow failure transitions |
| 618 |
// because failure transitions lead us down a path to matching |
| 619 |
// a *proper* suffix of the path we were on. Thus, it can only |
| 620 |
// produce matches that appear after the beginning of the search. |
| 621 |
if anchored.is_anchored() { |
| 622 |
return NFA::DEAD; |
| 623 |
} |
| 624 |
sid = self.states[sid].fail(); |
| 625 |
} |
| 626 |
} |
| 627 |
|
| 628 |
#[inline(always)] |
| 629 |
fn is_special(&self, sid: StateID) -> bool { |
| 630 |
sid <= self.special.max_special_id |
| 631 |
} |
| 632 |
|
| 633 |
#[inline(always)] |
| 634 |
fn is_dead(&self, sid: StateID) -> bool { |
| 635 |
sid == NFA::DEAD |
| 636 |
} |
| 637 |
|
| 638 |
#[inline(always)] |
| 639 |
fn is_match(&self, sid: StateID) -> bool { |
| 640 |
// N.B. This returns true when sid==NFA::FAIL but that's okay because |
| 641 |
// NFA::FAIL is not actually a valid state ID from the perspective of |
| 642 |
// the Automaton trait. Namely, it is never returned by 'start_state' |
| 643 |
// or by 'next_state'. So we don't need to care about it here. |
| 644 |
!self.is_dead(sid) && sid <= self.special.max_match_id |
| 645 |
} |
| 646 |
|
| 647 |
#[inline(always)] |
| 648 |
fn is_start(&self, sid: StateID) -> bool { |
| 649 |
sid == self.special.start_unanchored_id |
| 650 |
|| sid == self.special.start_anchored_id |
| 651 |
} |
| 652 |
|
| 653 |
#[inline(always)] |
| 654 |
fn match_kind(&self) -> MatchKind { |
| 655 |
self.match_kind |
| 656 |
} |
| 657 |
|
| 658 |
#[inline(always)] |
| 659 |
fn patterns_len(&self) -> usize { |
| 660 |
self.pattern_lens.len() |
| 661 |
} |
| 662 |
|
| 663 |
#[inline(always)] |
| 664 |
fn pattern_len(&self, pid: PatternID) -> usize { |
| 665 |
self.pattern_lens[pid].as_usize() |
| 666 |
} |
| 667 |
|
| 668 |
#[inline(always)] |
| 669 |
fn min_pattern_len(&self) -> usize { |
| 670 |
self.min_pattern_len |
| 671 |
} |
| 672 |
|
| 673 |
#[inline(always)] |
| 674 |
fn max_pattern_len(&self) -> usize { |
| 675 |
self.max_pattern_len |
| 676 |
} |
| 677 |
|
| 678 |
#[inline(always)] |
| 679 |
fn match_len(&self, sid: StateID) -> usize { |
| 680 |
self.iter_matches(sid).count() |
| 681 |
} |
| 682 |
|
| 683 |
#[inline(always)] |
| 684 |
fn match_pattern(&self, sid: StateID, index: usize) -> PatternID { |
| 685 |
self.iter_matches(sid).nth(index).unwrap() |
| 686 |
} |
| 687 |
|
| 688 |
#[inline(always)] |
| 689 |
fn memory_usage(&self) -> usize { |
| 690 |
self.states.len() * core::mem::size_of::<State>() |
| 691 |
+ self.sparse.len() * core::mem::size_of::<Transition>() |
| 692 |
+ self.matches.len() * core::mem::size_of::<Match>() |
| 693 |
+ self.dense.len() * StateID::SIZE |
| 694 |
+ self.pattern_lens.len() * SmallIndex::SIZE |
| 695 |
+ self.prefilter.as_ref().map_or(0, |p| p.memory_usage()) |
| 696 |
} |
| 697 |
|
| 698 |
#[inline(always)] |
| 699 |
fn prefilter(&self) -> Option<&Prefilter> { |
| 700 |
self.prefilter.as_ref() |
| 701 |
} |
| 702 |
} |
| 703 |
|
| 704 |
/// A representation of a sparse NFA state for an Aho-Corasick automaton. |
| 705 |
/// |
| 706 |
/// It contains the transitions to the next state, a failure transition for |
| 707 |
/// cases where there exists no other transition for the current input byte |
| 708 |
/// and the matches implied by visiting this state (if any). |
| 709 |
#[derive(Clone, Debug)] |
| 710 |
pub(crate) struct State { |
| 711 |
/// A pointer to `NFA::trans` corresponding to the head of a linked list |
| 712 |
/// containing all of the transitions for this state. |
| 713 |
/// |
| 714 |
/// This is `StateID::ZERO` if and only if this state has zero transitions. |
| 715 |
sparse: StateID, |
| 716 |
/// A pointer to a row of `N` transitions in `NFA::dense`. These |
| 717 |
/// transitions correspond precisely to what is obtained by traversing |
| 718 |
/// `sparse`, but permits constant time lookup. |
| 719 |
/// |
| 720 |
/// When this is zero (which is true for most states in the default |
| 721 |
/// configuration), then this state has no dense representation. |
| 722 |
/// |
| 723 |
/// Note that `N` is equal to `NFA::byte_classes::alphabet_len()`. This is |
| 724 |
/// typically much less than 256 (the maximum value). |
| 725 |
dense: StateID, |
| 726 |
/// A pointer to `NFA::matches` corresponding to the head of a linked list |
| 727 |
/// containing all of the matches for this state. |
| 728 |
/// |
| 729 |
/// This is `StateID::ZERO` if and only if this state is not a match state. |
| 730 |
matches: StateID, |
| 731 |
/// The state that should be transitioned to if the current byte in the |
| 732 |
/// haystack does not have a corresponding transition defined in this |
| 733 |
/// state. |
| 734 |
fail: StateID, |
| 735 |
/// The depth of this state. Specifically, this is the distance from this |
| 736 |
/// state to the starting state. (For the special sentinel states DEAD and |
| 737 |
/// FAIL, their depth is always 0.) The depth of a starting state is 0. |
| 738 |
/// |
| 739 |
/// Note that depth is currently not used in this non-contiguous NFA. It |
| 740 |
/// may in the future, but it is used in the contiguous NFA. Namely, it |
| 741 |
/// permits an optimization where states near the starting state have their |
| 742 |
/// transitions stored in a dense fashion, but all other states have their |
| 743 |
/// transitions stored in a sparse fashion. (This non-contiguous NFA uses |
| 744 |
/// a sparse representation for all states unconditionally.) In any case, |
| 745 |
/// this is really the only convenient place to compute and store this |
| 746 |
/// information, which we need when building the contiguous NFA. |
| 747 |
depth: SmallIndex, |
| 748 |
} |
| 749 |
|
| 750 |
impl State { |
| 751 |
/// Return true if and only if this state is a match state. |
| 752 |
pub(crate) fn is_match(&self) -> bool { |
| 753 |
self.matches != StateID::ZERO |
| 754 |
} |
| 755 |
|
| 756 |
/// Returns the failure transition for this state. |
| 757 |
pub(crate) fn fail(&self) -> StateID { |
| 758 |
self.fail |
| 759 |
} |
| 760 |
|
| 761 |
/// Returns the depth of this state. That is, the number of transitions |
| 762 |
/// this state is from the start state of the NFA. |
| 763 |
pub(crate) fn depth(&self) -> SmallIndex { |
| 764 |
self.depth |
| 765 |
} |
| 766 |
} |
| 767 |
|
| 768 |
/// A single transition in a non-contiguous NFA. |
| 769 |
#[derive(Clone, Copy, Default)] |
| 770 |
#[repr(packed)] |
| 771 |
pub(crate) struct Transition { |
| 772 |
byte: u8, |
| 773 |
next: StateID, |
| 774 |
link: StateID, |
| 775 |
} |
| 776 |
|
| 777 |
impl Transition { |
| 778 |
/// Return the byte for which this transition is defined. |
| 779 |
pub(crate) fn byte(&self) -> u8 { |
| 780 |
self.byte |
| 781 |
} |
| 782 |
|
| 783 |
/// Return the ID of the state that this transition points to. |
| 784 |
pub(crate) fn next(&self) -> StateID { |
| 785 |
self.next |
| 786 |
} |
| 787 |
|
| 788 |
/// Return the ID of the next transition. |
| 789 |
fn link(&self) -> StateID { |
| 790 |
self.link |
| 791 |
} |
| 792 |
} |
| 793 |
|
| 794 |
impl core::fmt::Debug for Transition { |
| 795 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 796 |
write!( |
| 797 |
f, |
| 798 |
"Transition(byte: {:X?}, next: {:?}, link: {:?})", |
| 799 |
self.byte, |
| 800 |
self.next().as_usize(), |
| 801 |
self.link().as_usize() |
| 802 |
) |
| 803 |
} |
| 804 |
} |
| 805 |
|
| 806 |
/// A single match in a non-contiguous NFA. |
| 807 |
#[derive(Clone, Copy, Default)] |
| 808 |
struct Match { |
| 809 |
pid: PatternID, |
| 810 |
link: StateID, |
| 811 |
} |
| 812 |
|
| 813 |
impl Match { |
| 814 |
/// Return the pattern ID for this match. |
| 815 |
pub(crate) fn pattern(&self) -> PatternID { |
| 816 |
self.pid |
| 817 |
} |
| 818 |
|
| 819 |
/// Return the ID of the next match. |
| 820 |
fn link(&self) -> StateID { |
| 821 |
self.link |
| 822 |
} |
| 823 |
} |
| 824 |
|
| 825 |
impl core::fmt::Debug for Match { |
| 826 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 827 |
write!( |
| 828 |
f, |
| 829 |
"Match(pid: {:?}, link: {:?})", |
| 830 |
self.pattern().as_usize(), |
| 831 |
self.link().as_usize() |
| 832 |
) |
| 833 |
} |
| 834 |
} |
| 835 |
|
| 836 |
/// A builder for configuring an Aho-Corasick noncontiguous NFA. |
| 837 |
/// |
| 838 |
/// This builder has a subset of the options available to a |
| 839 |
/// [`AhoCorasickBuilder`](crate::AhoCorasickBuilder). Of the shared options, |
| 840 |
/// their behavior is identical. |
| 841 |
#[derive(Clone, Debug)] |
| 842 |
pub struct Builder { |
| 843 |
match_kind: MatchKind, |
| 844 |
prefilter: bool, |
| 845 |
ascii_case_insensitive: bool, |
| 846 |
dense_depth: usize, |
| 847 |
} |
| 848 |
|
| 849 |
impl Default for Builder { |
| 850 |
fn default() -> Builder { |
| 851 |
Builder { |
| 852 |
match_kind: MatchKind::default(), |
| 853 |
prefilter: true, |
| 854 |
ascii_case_insensitive: false, |
| 855 |
dense_depth: 3, |
| 856 |
} |
| 857 |
} |
| 858 |
} |
| 859 |
|
| 860 |
impl Builder { |
| 861 |
/// Create a new builder for configuring an Aho-Corasick noncontiguous NFA. |
| 862 |
pub fn new() -> Builder { |
| 863 |
Builder::default() |
| 864 |
} |
| 865 |
|
| 866 |
/// Build an Aho-Corasick noncontiguous NFA from the given iterator of |
| 867 |
/// patterns. |
| 868 |
/// |
| 869 |
/// A builder may be reused to create more NFAs. |
| 870 |
pub fn build<I, P>(&self, patterns: I) -> Result<NFA, BuildError> |
| 871 |
where |
| 872 |
I: IntoIterator<Item = P>, |
| 873 |
P: AsRef<[u8]>, |
| 874 |
{ |
| 875 |
debug!("building non-contiguous NFA"); |
| 876 |
let nfa = Compiler::new(self)?.compile(patterns)?; |
| 877 |
debug!( |
| 878 |
"non-contiguous NFA built, <states: {:?}, size: {:?}>", |
| 879 |
nfa.states.len(), |
| 880 |
nfa.memory_usage() |
| 881 |
); |
| 882 |
Ok(nfa) |
| 883 |
} |
| 884 |
|
| 885 |
/// Set the desired match semantics. |
| 886 |
/// |
| 887 |
/// See |
| 888 |
/// [`AhoCorasickBuilder::match_kind`](crate::AhoCorasickBuilder::match_kind) |
| 889 |
/// for more documentation and examples. |
| 890 |
pub fn match_kind(&mut self, kind: MatchKind) -> &mut Builder { |
| 891 |
self.match_kind = kind; |
| 892 |
self |
| 893 |
} |
| 894 |
|
| 895 |
/// Enable ASCII-aware case insensitive matching. |
| 896 |
/// |
| 897 |
/// See |
| 898 |
/// [`AhoCorasickBuilder::ascii_case_insensitive`](crate::AhoCorasickBuilder::ascii_case_insensitive) |
| 899 |
/// for more documentation and examples. |
| 900 |
pub fn ascii_case_insensitive(&mut self, yes: bool) -> &mut Builder { |
| 901 |
self.ascii_case_insensitive = yes; |
| 902 |
self |
| 903 |
} |
| 904 |
|
| 905 |
/// Set the limit on how many states use a dense representation for their |
| 906 |
/// transitions. Other states will generally use a sparse representation. |
| 907 |
/// |
| 908 |
/// See |
| 909 |
/// [`AhoCorasickBuilder::dense_depth`](crate::AhoCorasickBuilder::dense_depth) |
| 910 |
/// for more documentation and examples. |
| 911 |
pub fn dense_depth(&mut self, depth: usize) -> &mut Builder { |
| 912 |
self.dense_depth = depth; |
| 913 |
self |
| 914 |
} |
| 915 |
|
| 916 |
/// Enable heuristic prefilter optimizations. |
| 917 |
/// |
| 918 |
/// See |
| 919 |
/// [`AhoCorasickBuilder::prefilter`](crate::AhoCorasickBuilder::prefilter) |
| 920 |
/// for more documentation and examples. |
| 921 |
pub fn prefilter(&mut self, yes: bool) -> &mut Builder { |
| 922 |
self.prefilter = yes; |
| 923 |
self |
| 924 |
} |
| 925 |
} |
| 926 |
|
| 927 |
/// A compiler uses a builder configuration and builds up the NFA formulation |
| 928 |
/// of an Aho-Corasick automaton. This roughly corresponds to the standard |
| 929 |
/// formulation described in textbooks, with some tweaks to support leftmost |
| 930 |
/// searching. |
| 931 |
#[derive(Debug)] |
| 932 |
struct Compiler<'a> { |
| 933 |
builder: &'a Builder, |
| 934 |
prefilter: prefilter::Builder, |
| 935 |
nfa: NFA, |
| 936 |
byteset: ByteClassSet, |
| 937 |
} |
| 938 |
|
| 939 |
impl<'a> Compiler<'a> { |
| 940 |
fn new(builder: &'a Builder) -> Result<Compiler<'a>, BuildError> { |
| 941 |
let prefilter = prefilter::Builder::new(builder.match_kind) |
| 942 |
.ascii_case_insensitive(builder.ascii_case_insensitive); |
| 943 |
Ok(Compiler { |
| 944 |
builder, |
| 945 |
prefilter, |
| 946 |
nfa: NFA { |
| 947 |
match_kind: builder.match_kind, |
| 948 |
states: vec![], |
| 949 |
sparse: vec![], |
| 950 |
dense: vec![], |
| 951 |
matches: vec![], |
| 952 |
pattern_lens: vec![], |
| 953 |
prefilter: None, |
| 954 |
byte_classes: ByteClasses::singletons(), |
| 955 |
min_pattern_len: usize::MAX, |
| 956 |
max_pattern_len: 0, |
| 957 |
special: Special::zero(), |
| 958 |
}, |
| 959 |
byteset: ByteClassSet::empty(), |
| 960 |
}) |
| 961 |
} |
| 962 |
|
| 963 |
fn compile<I, P>(mut self, patterns: I) -> Result<NFA, BuildError> |
| 964 |
where |
| 965 |
I: IntoIterator<Item = P>, |
| 966 |
P: AsRef<[u8]>, |
| 967 |
{ |
| 968 |
// Add dummy transition/match links, so that no valid link will point |
| 969 |
// to another link at index 0. |
| 970 |
self.nfa.sparse.push(Transition::default()); |
| 971 |
self.nfa.matches.push(Match::default()); |
| 972 |
// Add a dummy dense transition so that no states can have dense==0 |
| 973 |
// represent a valid pointer to dense transitions. This permits |
| 974 |
// dense==0 to be a sentinel indicating "no dense transitions." |
| 975 |
self.nfa.dense.push(NFA::DEAD); |
| 976 |
// the dead state, only used for leftmost and fixed to id==0 |
| 977 |
self.nfa.alloc_state(0)?; |
| 978 |
// the fail state, which is never entered and fixed to id==1 |
| 979 |
self.nfa.alloc_state(0)?; |
| 980 |
// unanchored start state, initially fixed to id==2 but later shuffled |
| 981 |
// to appear after all non-start match states. |
| 982 |
self.nfa.special.start_unanchored_id = self.nfa.alloc_state(0)?; |
| 983 |
// anchored start state, initially fixed to id==3 but later shuffled |
| 984 |
// to appear after unanchored start state. |
| 985 |
self.nfa.special.start_anchored_id = self.nfa.alloc_state(0)?; |
| 986 |
// Initialize the unanchored starting state in order to make it dense, |
| 987 |
// and thus make transition lookups on this state faster. |
| 988 |
self.init_unanchored_start_state()?; |
| 989 |
// Set all transitions on the DEAD state to point to itself. This way, |
| 990 |
// the DEAD state can never be escaped. It MUST be used as a sentinel |
| 991 |
// in any correct search. |
| 992 |
self.add_dead_state_loop()?; |
| 993 |
// Build the base trie from the given patterns. |
| 994 |
self.build_trie(patterns)?; |
| 995 |
self.nfa.states.shrink_to_fit(); |
| 996 |
// Turn our set of bytes into equivalent classes. This NFA |
| 997 |
// implementation uses byte classes only for states that use a dense |
| 998 |
// representation of transitions. (And that's why this comes before |
| 999 |
// `self.densify()`, as the byte classes need to be set first.) |
| 1000 |
self.nfa.byte_classes = self.byteset.byte_classes(); |
| 1001 |
// Add transitions (and maybe matches) to the anchored starting state. |
| 1002 |
// The anchored starting state is used for anchored searches. The only |
| 1003 |
// mechanical difference between it and the unanchored start state is |
| 1004 |
// that missing transitions map to the DEAD state instead of the FAIL |
| 1005 |
// state. |
| 1006 |
self.set_anchored_start_state()?; |
| 1007 |
// Rewrite transitions to the FAIL state on the unanchored start state |
| 1008 |
// as self-transitions. This keeps the start state active at all times. |
| 1009 |
self.add_unanchored_start_state_loop(); |
| 1010 |
// Make some (possibly zero) states use a dense representation for |
| 1011 |
// transitions. It's important to do this right after the states |
| 1012 |
// and non-failure transitions are solidified. That way, subsequent |
| 1013 |
// accesses (particularly `fill_failure_transitions`) will benefit from |
| 1014 |
// the faster transition lookup in densified states. |
| 1015 |
self.densify()?; |
| 1016 |
// The meat of the Aho-Corasick algorithm: compute and write failure |
| 1017 |
// transitions. i.e., the state to move to when a transition isn't |
| 1018 |
// defined in the current state. These are epsilon transitions and thus |
| 1019 |
// make this formulation an NFA. |
| 1020 |
self.fill_failure_transitions()?; |
| 1021 |
// Handle a special case under leftmost semantics when at least one |
| 1022 |
// of the patterns is the empty string. |
| 1023 |
self.close_start_state_loop_for_leftmost(); |
| 1024 |
// Shuffle states so that we have DEAD, FAIL, MATCH, ..., START, START, |
| 1025 |
// NON-MATCH, ... This permits us to very quickly query the type of |
| 1026 |
// the state we're currently in during a search. |
| 1027 |
self.shuffle(); |
| 1028 |
self.nfa.prefilter = self.prefilter.build(); |
| 1029 |
// Store the maximum ID of all *relevant* special states. Start states |
| 1030 |
// are only relevant when we have a prefilter, otherwise, there is zero |
| 1031 |
// reason to care about whether a state is a start state or not during |
| 1032 |
// a search. Indeed, without a prefilter, we are careful to explicitly |
| 1033 |
// NOT care about start states, otherwise the search can ping pong |
| 1034 |
// between the unrolled loop and the handling of special-status states |
| 1035 |
// and destroy perf. |
| 1036 |
self.nfa.special.max_special_id = if self.nfa.prefilter.is_some() { |
| 1037 |
// Why the anchored starting state? Because we always put it |
| 1038 |
// after the unanchored starting state and it is therefore the |
| 1039 |
// maximum. Why put unanchored followed by anchored? No particular |
| 1040 |
// reason, but that's how the states are logically organized in the |
| 1041 |
// Thompson NFA implementation found in regex-automata. ¯\_(ツ)_/¯ |
| 1042 |
self.nfa.special.start_anchored_id |
| 1043 |
} else { |
| 1044 |
self.nfa.special.max_match_id |
| 1045 |
}; |
| 1046 |
self.nfa.sparse.shrink_to_fit(); |
| 1047 |
self.nfa.dense.shrink_to_fit(); |
| 1048 |
self.nfa.matches.shrink_to_fit(); |
| 1049 |
self.nfa.pattern_lens.shrink_to_fit(); |
| 1050 |
Ok(self.nfa) |
| 1051 |
} |
| 1052 |
|
| 1053 |
/// This sets up the initial prefix trie that makes up the Aho-Corasick |
| 1054 |
/// automaton. Effectively, it creates the basic structure of the |
| 1055 |
/// automaton, where every pattern given has a path from the start state to |
| 1056 |
/// the end of the pattern. |
| 1057 |
fn build_trie<I, P>(&mut self, patterns: I) -> Result<(), BuildError> |
| 1058 |
where |
| 1059 |
I: IntoIterator<Item = P>, |
| 1060 |
P: AsRef<[u8]>, |
| 1061 |
{ |
| 1062 |
'PATTERNS: for (i, pat) in patterns.into_iter().enumerate() { |
| 1063 |
let pid = PatternID::new(i).map_err(|e| { |
| 1064 |
BuildError::pattern_id_overflow( |
| 1065 |
PatternID::MAX.as_u64(), |
| 1066 |
e.attempted(), |
| 1067 |
) |
| 1068 |
})?; |
| 1069 |
let pat = pat.as_ref(); |
| 1070 |
let patlen = SmallIndex::new(pat.len()) |
| 1071 |
.map_err(|_| BuildError::pattern_too_long(pid, pat.len()))?; |
| 1072 |
self.nfa.min_pattern_len = |
| 1073 |
core::cmp::min(self.nfa.min_pattern_len, pat.len()); |
| 1074 |
self.nfa.max_pattern_len = |
| 1075 |
core::cmp::max(self.nfa.max_pattern_len, pat.len()); |
| 1076 |
assert_eq!( |
| 1077 |
i, |
| 1078 |
self.nfa.pattern_lens.len(), |
| 1079 |
"expected number of patterns to match pattern ID" |
| 1080 |
); |
| 1081 |
self.nfa.pattern_lens.push(patlen); |
| 1082 |
// We add the pattern to the prefilter here because the pattern |
| 1083 |
// ID in the prefilter is determined with respect to the patterns |
| 1084 |
// added to the prefilter. That is, it isn't the ID we have here, |
| 1085 |
// but the one determined by its own accounting of patterns. |
| 1086 |
// To ensure they line up, we add every pattern we see to the |
| 1087 |
// prefilter, even if some patterns ultimately are impossible to |
| 1088 |
// match (in leftmost-first semantics specifically). |
| 1089 |
// |
| 1090 |
// Another way of doing this would be to expose an API in the |
| 1091 |
// prefilter to permit setting your own pattern IDs. Or to just use |
| 1092 |
// our own map and go between them. But this case is sufficiently |
| 1093 |
// rare that we don't bother and just make sure they're in sync. |
| 1094 |
if self.builder.prefilter { |
| 1095 |
self.prefilter.add(pat); |
| 1096 |
} |
| 1097 |
|
| 1098 |
let mut prev = self.nfa.special.start_unanchored_id; |
| 1099 |
let mut saw_match = false; |
| 1100 |
for (depth, &b) in pat.iter().enumerate() { |
| 1101 |
// When leftmost-first match semantics are requested, we |
| 1102 |
// specifically stop adding patterns when a previously added |
| 1103 |
// pattern is a prefix of it. We avoid adding it because |
| 1104 |
// leftmost-first semantics imply that the pattern can never |
| 1105 |
// match. This is not just an optimization to save space! It |
| 1106 |
// is necessary for correctness. In fact, this is the only |
| 1107 |
// difference in the automaton between the implementations for |
| 1108 |
// leftmost-first and leftmost-longest. |
| 1109 |
saw_match = saw_match || self.nfa.states[prev].is_match(); |
| 1110 |
if self.builder.match_kind.is_leftmost_first() && saw_match { |
| 1111 |
// Skip to the next pattern immediately. This avoids |
| 1112 |
// incorrectly adding a match after this loop terminates. |
| 1113 |
continue 'PATTERNS; |
| 1114 |
} |
| 1115 |
|
| 1116 |
// Add this byte to our equivalence classes. These don't |
| 1117 |
// get used while building the trie, but other Aho-Corasick |
| 1118 |
// implementations may use them. |
| 1119 |
self.byteset.set_range(b, b); |
| 1120 |
if self.builder.ascii_case_insensitive { |
| 1121 |
let b = opposite_ascii_case(b); |
| 1122 |
self.byteset.set_range(b, b); |
| 1123 |
} |
| 1124 |
|
| 1125 |
// If the transition from prev using the current byte already |
| 1126 |
// exists, then just move through it. Otherwise, add a new |
| 1127 |
// state. We track the depth here so that we can determine |
| 1128 |
// how to represent transitions. States near the start state |
| 1129 |
// use a dense representation that uses more memory but is |
| 1130 |
// faster. Other states use a sparse representation that uses |
| 1131 |
// less memory but is slower. |
| 1132 |
let next = self.nfa.follow_transition(prev, b); |
| 1133 |
if next != NFA::FAIL { |
| 1134 |
prev = next; |
| 1135 |
} else { |
| 1136 |
let next = self.nfa.alloc_state(depth)?; |
| 1137 |
self.nfa.add_transition(prev, b, next)?; |
| 1138 |
if self.builder.ascii_case_insensitive { |
| 1139 |
let b = opposite_ascii_case(b); |
| 1140 |
self.nfa.add_transition(prev, b, next)?; |
| 1141 |
} |
| 1142 |
prev = next; |
| 1143 |
} |
| 1144 |
} |
| 1145 |
// Once the pattern has been added, log the match in the final |
| 1146 |
// state that it reached. |
| 1147 |
self.nfa.add_match(prev, pid)?; |
| 1148 |
} |
| 1149 |
Ok(()) |
| 1150 |
} |
| 1151 |
|
| 1152 |
/// This routine creates failure transitions according to the standard |
| 1153 |
/// textbook formulation of the Aho-Corasick algorithm, with a couple small |
| 1154 |
/// tweaks to support "leftmost" semantics. |
| 1155 |
/// |
| 1156 |
/// Building failure transitions is the most interesting part of building |
| 1157 |
/// the Aho-Corasick automaton, because they are what allow searches to |
| 1158 |
/// be performed in linear time. Specifically, a failure transition is |
| 1159 |
/// a single transition associated with each state that points back to |
| 1160 |
/// the longest proper suffix of the pattern being searched. The failure |
| 1161 |
/// transition is followed whenever there exists no transition on the |
| 1162 |
/// current state for the current input byte. If there is no other proper |
| 1163 |
/// suffix, then the failure transition points back to the starting state. |
| 1164 |
/// |
| 1165 |
/// For example, let's say we built an Aho-Corasick automaton with the |
| 1166 |
/// following patterns: 'abcd' and 'cef'. The trie looks like this: |
| 1167 |
/// |
| 1168 |
/// ```ignore |
| 1169 |
/// a - S1 - b - S2 - c - S3 - d - S4* |
| 1170 |
/// / |
| 1171 |
/// S0 - c - S5 - e - S6 - f - S7* |
| 1172 |
/// ``` |
| 1173 |
/// |
| 1174 |
/// At this point, it should be fairly straight-forward to see how this |
| 1175 |
/// trie can be used in a simplistic way. At any given position in the |
| 1176 |
/// text we're searching (called the "subject" string), all we need to do |
| 1177 |
/// is follow the transitions in the trie by consuming one transition for |
| 1178 |
/// each byte in the subject string. If we reach a match state, then we can |
| 1179 |
/// report that location as a match. |
| 1180 |
/// |
| 1181 |
/// The trick comes when searching a subject string like 'abcef'. We'll |
| 1182 |
/// initially follow the transition from S0 to S1 and wind up in S3 after |
| 1183 |
/// observng the 'c' byte. At this point, the next byte is 'e' but state |
| 1184 |
/// S3 has no transition for 'e', so the search fails. We then would need |
| 1185 |
/// to restart the search at the next position in 'abcef', which |
| 1186 |
/// corresponds to 'b'. The match would fail, but the next search starting |
| 1187 |
/// at 'c' would finally succeed. The problem with this approach is that |
| 1188 |
/// we wind up searching the subject string potentially many times. In |
| 1189 |
/// effect, this makes the algorithm have worst case `O(n * m)` complexity, |
| 1190 |
/// where `n ~ len(subject)` and `m ~ len(all patterns)`. We would instead |
| 1191 |
/// like to achieve a `O(n + m)` worst case complexity. |
| 1192 |
/// |
| 1193 |
/// This is where failure transitions come in. Instead of dying at S3 in |
| 1194 |
/// the first search, the automaton can instruct the search to move to |
| 1195 |
/// another part of the automaton that corresponds to a suffix of what |
| 1196 |
/// we've seen so far. Recall that we've seen 'abc' in the subject string, |
| 1197 |
/// and the automaton does indeed have a non-empty suffix, 'c', that could |
| 1198 |
/// potentially lead to another match. Thus, the actual Aho-Corasick |
| 1199 |
/// automaton for our patterns in this case looks like this: |
| 1200 |
/// |
| 1201 |
/// ```ignore |
| 1202 |
/// a - S1 - b - S2 - c - S3 - d - S4* |
| 1203 |
/// / / |
| 1204 |
/// / ---------------- |
| 1205 |
/// / / |
| 1206 |
/// S0 - c - S5 - e - S6 - f - S7* |
| 1207 |
/// ``` |
| 1208 |
/// |
| 1209 |
/// That is, we have a failure transition from S3 to S5, which is followed |
| 1210 |
/// exactly in cases when we are in state S3 but see any byte other than |
| 1211 |
/// 'd' (that is, we've "failed" to find a match in this portion of our |
| 1212 |
/// trie). We know we can transition back to S5 because we've already seen |
| 1213 |
/// a 'c' byte, so we don't need to re-scan it. We can then pick back up |
| 1214 |
/// with the search starting at S5 and complete our match. |
| 1215 |
/// |
| 1216 |
/// Adding failure transitions to a trie is fairly simple, but subtle. The |
| 1217 |
/// key issue is that you might have multiple failure transition that you |
| 1218 |
/// need to follow. For example, look at the trie for the patterns |
| 1219 |
/// 'abcd', 'b', 'bcd' and 'cd': |
| 1220 |
/// |
| 1221 |
/// ```ignore |
| 1222 |
/// - a - S1 - b - S2* - c - S3 - d - S4* |
| 1223 |
/// / / / |
| 1224 |
/// / ------- ------- |
| 1225 |
/// / / / |
| 1226 |
/// S0 --- b - S5* - c - S6 - d - S7* |
| 1227 |
/// \ / |
| 1228 |
/// \ -------- |
| 1229 |
/// \ / |
| 1230 |
/// - c - S8 - d - S9* |
| 1231 |
/// ``` |
| 1232 |
/// |
| 1233 |
/// The failure transitions for this trie are defined from S2 to S5, |
| 1234 |
/// S3 to S6 and S6 to S8. Moreover, state S2 needs to track that it |
| 1235 |
/// corresponds to a match, since its failure transition to S5 is itself |
| 1236 |
/// a match state. |
| 1237 |
/// |
| 1238 |
/// Perhaps simplest way to think about adding these failure transitions |
| 1239 |
/// is recursively. That is, if you know the failure transitions for every |
| 1240 |
/// possible previous state that could be visited (e.g., when computing the |
| 1241 |
/// failure transition for S3, you already know the failure transitions |
| 1242 |
/// for S0, S1 and S2), then you can simply follow the failure transition |
| 1243 |
/// of the previous state and check whether the incoming transition is |
| 1244 |
/// defined after following the failure transition. |
| 1245 |
/// |
| 1246 |
/// For example, when determining the failure state for S3, by our |
| 1247 |
/// assumptions, we already know that there is a failure transition from |
| 1248 |
/// S2 (the previous state) to S5. So we follow that transition and check |
| 1249 |
/// whether the transition connecting S2 to S3 is defined. Indeed, it is, |
| 1250 |
/// as there is a transition from S5 to S6 for the byte 'c'. If no such |
| 1251 |
/// transition existed, we could keep following the failure transitions |
| 1252 |
/// until we reach the start state, which is the failure transition for |
| 1253 |
/// every state that has no corresponding proper suffix. |
| 1254 |
/// |
| 1255 |
/// We don't actually use recursion to implement this, but instead, use a |
| 1256 |
/// breadth first search of the automaton. Our base case is the start |
| 1257 |
/// state, whose failure transition is just a transition to itself. |
| 1258 |
/// |
| 1259 |
/// When building a leftmost automaton, we proceed as above, but only |
| 1260 |
/// include a subset of failure transitions. Namely, we omit any failure |
| 1261 |
/// transitions that appear after a match state in the trie. This is |
| 1262 |
/// because failure transitions always point back to a proper suffix of |
| 1263 |
/// what has been seen so far. Thus, following a failure transition after |
| 1264 |
/// a match implies looking for a match that starts after the one that has |
| 1265 |
/// already been seen, which is of course therefore not the leftmost match. |
| 1266 |
/// |
| 1267 |
/// N.B. I came up with this algorithm on my own, and after scouring all of |
| 1268 |
/// the other AC implementations I know of (Perl, Snort, many on GitHub). |
| 1269 |
/// I couldn't find any that implement leftmost semantics like this. |
| 1270 |
/// Perl of course needs leftmost-first semantics, but they implement it |
| 1271 |
/// with a seeming hack at *search* time instead of encoding it into the |
| 1272 |
/// automaton. There are also a couple Java libraries that support leftmost |
| 1273 |
/// longest semantics, but they do it by building a queue of matches at |
| 1274 |
/// search time, which is even worse than what Perl is doing. ---AG |
| 1275 |
fn fill_failure_transitions(&mut self) -> Result<(), BuildError> { |
| 1276 |
let is_leftmost = self.builder.match_kind.is_leftmost(); |
| 1277 |
let start_uid = self.nfa.special.start_unanchored_id; |
| 1278 |
// Initialize the queue for breadth first search with all transitions |
| 1279 |
// out of the start state. We handle the start state specially because |
| 1280 |
// we only want to follow non-self transitions. If we followed self |
| 1281 |
// transitions, then this would never terminate. |
| 1282 |
let mut queue = VecDeque::new(); |
| 1283 |
let mut seen = self.queued_set(); |
| 1284 |
let mut prev_link = None; |
| 1285 |
while let Some(link) = self.nfa.next_link(start_uid, prev_link) { |
| 1286 |
prev_link = Some(link); |
| 1287 |
let t = self.nfa.sparse[link]; |
| 1288 |
|
| 1289 |
// Skip anything we've seen before and any self-transitions on the |
| 1290 |
// start state. |
| 1291 |
if start_uid == t.next() || seen.contains(t.next) { |
| 1292 |
continue; |
| 1293 |
} |
| 1294 |
queue.push_back(t.next); |
| 1295 |
seen.insert(t.next); |
| 1296 |
// Under leftmost semantics, if a state immediately following |
| 1297 |
// the start state is a match state, then we never want to |
| 1298 |
// follow its failure transition since the failure transition |
| 1299 |
// necessarily leads back to the start state, which we never |
| 1300 |
// want to do for leftmost matching after a match has been |
| 1301 |
// found. |
| 1302 |
// |
| 1303 |
// We apply the same logic to non-start states below as well. |
| 1304 |
if is_leftmost && self.nfa.states[t.next].is_match() { |
| 1305 |
self.nfa.states[t.next].fail = NFA::DEAD; |
| 1306 |
} |
| 1307 |
} |
| 1308 |
while let Some(id) = queue.pop_front() { |
| 1309 |
let mut prev_link = None; |
| 1310 |
while let Some(link) = self.nfa.next_link(id, prev_link) { |
| 1311 |
prev_link = Some(link); |
| 1312 |
let t = self.nfa.sparse[link]; |
| 1313 |
|
| 1314 |
if seen.contains(t.next) { |
| 1315 |
// The only way to visit a duplicate state in a transition |
| 1316 |
// list is when ASCII case insensitivity is enabled. In |
| 1317 |
// this case, we want to skip it since it's redundant work. |
| 1318 |
// But it would also end up duplicating matches, which |
| 1319 |
// results in reporting duplicate matches in some cases. |
| 1320 |
// See the 'acasei010' regression test. |
| 1321 |
continue; |
| 1322 |
} |
| 1323 |
queue.push_back(t.next); |
| 1324 |
seen.insert(t.next); |
| 1325 |
|
| 1326 |
// As above for start states, under leftmost semantics, once |
| 1327 |
// we see a match all subsequent states should have no failure |
| 1328 |
// transitions because failure transitions always imply looking |
| 1329 |
// for a match that is a suffix of what has been seen so far |
| 1330 |
// (where "seen so far" corresponds to the string formed by |
| 1331 |
// following the transitions from the start state to the |
| 1332 |
// current state). Under leftmost semantics, we specifically do |
| 1333 |
// not want to allow this to happen because we always want to |
| 1334 |
// report the match found at the leftmost position. |
| 1335 |
// |
| 1336 |
// The difference between leftmost-first and leftmost-longest |
| 1337 |
// occurs previously while we build the trie. For |
| 1338 |
// leftmost-first, we simply omit any entries that would |
| 1339 |
// otherwise require passing through a match state. |
| 1340 |
// |
| 1341 |
// Note that for correctness, the failure transition has to be |
| 1342 |
// set to the dead state for ALL states following a match, not |
| 1343 |
// just the match state itself. However, by setting the failure |
| 1344 |
// transition to the dead state on all match states, the dead |
| 1345 |
// state will automatically propagate to all subsequent states |
| 1346 |
// via the failure state computation below. |
| 1347 |
if is_leftmost && self.nfa.states[t.next].is_match() { |
| 1348 |
self.nfa.states[t.next].fail = NFA::DEAD; |
| 1349 |
continue; |
| 1350 |
} |
| 1351 |
let mut fail = self.nfa.states[id].fail; |
| 1352 |
while self.nfa.follow_transition(fail, t.byte) == NFA::FAIL { |
| 1353 |
fail = self.nfa.states[fail].fail; |
| 1354 |
} |
| 1355 |
fail = self.nfa.follow_transition(fail, t.byte); |
| 1356 |
self.nfa.states[t.next].fail = fail; |
| 1357 |
self.nfa.copy_matches(fail, t.next)?; |
| 1358 |
} |
| 1359 |
// If the start state is a match state, then this automaton can |
| 1360 |
// match the empty string. This implies all states are match states |
| 1361 |
// since every position matches the empty string, so copy the |
| 1362 |
// matches from the start state to every state. Strictly speaking, |
| 1363 |
// this is only necessary for overlapping matches since each |
| 1364 |
// non-empty non-start match state needs to report empty matches |
| 1365 |
// in addition to its own. For the non-overlapping case, such |
| 1366 |
// states only report the first match, which is never empty since |
| 1367 |
// it isn't a start state. |
| 1368 |
if !is_leftmost { |
| 1369 |
self.nfa |
| 1370 |
.copy_matches(self.nfa.special.start_unanchored_id, id)?; |
| 1371 |
} |
| 1372 |
} |
| 1373 |
Ok(()) |
| 1374 |
} |
| 1375 |
|
| 1376 |
/// Shuffle the states so that they appear in this sequence: |
| 1377 |
/// |
| 1378 |
/// DEAD, FAIL, MATCH..., START, START, NON-MATCH... |
| 1379 |
/// |
| 1380 |
/// The idea here is that if we know how special states are laid out in our |
| 1381 |
/// transition table, then we can determine what "kind" of state we're in |
| 1382 |
/// just by comparing our current state ID with a particular value. In this |
| 1383 |
/// way, we avoid doing extra memory lookups. |
| 1384 |
/// |
| 1385 |
/// Before shuffling begins, our states look something like this: |
| 1386 |
/// |
| 1387 |
/// DEAD, FAIL, START, START, (MATCH | NON-MATCH)... |
| 1388 |
/// |
| 1389 |
/// So all we need to do is move all of the MATCH states so that they |
| 1390 |
/// all appear before any NON-MATCH state, like so: |
| 1391 |
/// |
| 1392 |
/// DEAD, FAIL, START, START, MATCH... NON-MATCH... |
| 1393 |
/// |
| 1394 |
/// Then it's just a simple matter of swapping the two START states with |
| 1395 |
/// the last two MATCH states. |
| 1396 |
/// |
| 1397 |
/// (This is the same technique used for fully compiled DFAs in |
| 1398 |
/// regex-automata.) |
| 1399 |
fn shuffle(&mut self) { |
| 1400 |
let old_start_uid = self.nfa.special.start_unanchored_id; |
| 1401 |
let old_start_aid = self.nfa.special.start_anchored_id; |
| 1402 |
assert!(old_start_uid < old_start_aid); |
| 1403 |
assert_eq!( |
| 1404 |
3, |
| 1405 |
old_start_aid.as_usize(), |
| 1406 |
"anchored start state should be at index 3" |
| 1407 |
); |
| 1408 |
// We implement shuffling by a sequence of pairwise swaps of states. |
| 1409 |
// Since we have a number of things referencing states via their |
| 1410 |
// IDs and swapping them changes their IDs, we need to record every |
| 1411 |
// swap we make so that we can remap IDs. The remapper handles this |
| 1412 |
// book-keeping for us. |
| 1413 |
let mut remapper = Remapper::new(&self.nfa, 0); |
| 1414 |
// The way we proceed here is by moving all match states so that |
| 1415 |
// they directly follow the start states. So it will go: DEAD, FAIL, |
| 1416 |
// START-UNANCHORED, START-ANCHORED, MATCH, ..., NON-MATCH, ... |
| 1417 |
// |
| 1418 |
// To do that, we proceed forward through all states after |
| 1419 |
// START-ANCHORED and swap match states so that they appear before all |
| 1420 |
// non-match states. |
| 1421 |
let mut next_avail = StateID::from(4u8); |
| 1422 |
for i in next_avail.as_usize()..self.nfa.states.len() { |
| 1423 |
let sid = StateID::new(i).unwrap(); |
| 1424 |
if !self.nfa.states[sid].is_match() { |
| 1425 |
continue; |
| 1426 |
} |
| 1427 |
remapper.swap(&mut self.nfa, sid, next_avail); |
| 1428 |
// The key invariant here is that only non-match states exist |
| 1429 |
// between 'next_avail' and 'sid' (with them being potentially |
| 1430 |
// equivalent). Thus, incrementing 'next_avail' by 1 is guaranteed |
| 1431 |
// to land on the leftmost non-match state. (Unless 'next_avail' |
| 1432 |
// and 'sid' are equivalent, in which case, a swap will occur but |
| 1433 |
// it is a no-op.) |
| 1434 |
next_avail = StateID::new(next_avail.one_more()).unwrap(); |
| 1435 |
} |
| 1436 |
// Now we'd like to move the start states to immediately following the |
| 1437 |
// match states. (The start states may themselves be match states, but |
| 1438 |
// we'll handle that later.) We arrange the states this way so that we |
| 1439 |
// don't necessarily need to check whether a state is a start state or |
| 1440 |
// not before checking whether a state is a match state. For example, |
| 1441 |
// we'd like to be able to write this as our state machine loop: |
| 1442 |
// |
| 1443 |
// sid = start() |
| 1444 |
// for byte in haystack: |
| 1445 |
// sid = next(sid, byte) |
| 1446 |
// if sid <= nfa.max_start_id: |
| 1447 |
// if sid <= nfa.max_dead_id: |
| 1448 |
// # search complete |
| 1449 |
// elif sid <= nfa.max_match_id: |
| 1450 |
// # found match |
| 1451 |
// |
| 1452 |
// The important context here is that we might not want to look for |
| 1453 |
// start states at all. Namely, if a searcher doesn't have a prefilter, |
| 1454 |
// then there is no reason to care about whether we're in a start state |
| 1455 |
// or not. And indeed, if we did check for it, this very hot loop would |
| 1456 |
// ping pong between the special state handling and the main state |
| 1457 |
// transition logic. This in turn stalls the CPU by killing branch |
| 1458 |
// prediction. |
| 1459 |
// |
| 1460 |
// So essentially, we really want to be able to "forget" that start |
| 1461 |
// states even exist and this is why we put them at the end. |
| 1462 |
let new_start_aid = |
| 1463 |
StateID::new(next_avail.as_usize().checked_sub(1).unwrap()) |
| 1464 |
.unwrap(); |
| 1465 |
remapper.swap(&mut self.nfa, old_start_aid, new_start_aid); |
| 1466 |
let new_start_uid = |
| 1467 |
StateID::new(next_avail.as_usize().checked_sub(2).unwrap()) |
| 1468 |
.unwrap(); |
| 1469 |
remapper.swap(&mut self.nfa, old_start_uid, new_start_uid); |
| 1470 |
let new_max_match_id = |
| 1471 |
StateID::new(next_avail.as_usize().checked_sub(3).unwrap()) |
| 1472 |
.unwrap(); |
| 1473 |
self.nfa.special.max_match_id = new_max_match_id; |
| 1474 |
self.nfa.special.start_unanchored_id = new_start_uid; |
| 1475 |
self.nfa.special.start_anchored_id = new_start_aid; |
| 1476 |
// If one start state is a match state, then they both are. |
| 1477 |
if self.nfa.states[self.nfa.special.start_anchored_id].is_match() { |
| 1478 |
self.nfa.special.max_match_id = self.nfa.special.start_anchored_id; |
| 1479 |
} |
| 1480 |
remapper.remap(&mut self.nfa); |
| 1481 |
} |
| 1482 |
|
| 1483 |
/// Attempts to convert the transition representation of a subset of states |
| 1484 |
/// in this NFA from sparse to dense. This can greatly improve search |
| 1485 |
/// performance since states with a higher number of transitions tend to |
| 1486 |
/// correlate with very active states. |
| 1487 |
/// |
| 1488 |
/// We generally only densify states that are close to the start state. |
| 1489 |
/// These tend to be the most active states and thus benefit from a dense |
| 1490 |
/// representation more than other states. |
| 1491 |
/// |
| 1492 |
/// This tends to best balance between memory usage and performance. In |
| 1493 |
/// particular, the *vast majority* of all states in a typical Aho-Corasick |
| 1494 |
/// automaton have only 1 transition and are usually farther from the start |
| 1495 |
/// state and thus don't get densified. |
| 1496 |
/// |
| 1497 |
/// Note that this doesn't remove the sparse representation of transitions |
| 1498 |
/// for states that are densified. It could be done, but actually removing |
| 1499 |
/// entries from `NFA::sparse` is likely more expensive than it's worth. |
| 1500 |
fn densify(&mut self) -> Result<(), BuildError> { |
| 1501 |
for i in 0..self.nfa.states.len() { |
| 1502 |
let sid = StateID::new(i).unwrap(); |
| 1503 |
// Don't bother densifying states that are only used as sentinels. |
| 1504 |
if sid == NFA::DEAD || sid == NFA::FAIL { |
| 1505 |
continue; |
| 1506 |
} |
| 1507 |
// Only densify states that are "close enough" to the start state. |
| 1508 |
if self.nfa.states[sid].depth.as_usize() |
| 1509 |
>= self.builder.dense_depth |
| 1510 |
{ |
| 1511 |
continue; |
| 1512 |
} |
| 1513 |
let dense = self.nfa.alloc_dense_state()?; |
| 1514 |
let mut prev_link = None; |
| 1515 |
while let Some(link) = self.nfa.next_link(sid, prev_link) { |
| 1516 |
prev_link = Some(link); |
| 1517 |
let t = self.nfa.sparse[link]; |
| 1518 |
|
| 1519 |
let class = usize::from(self.nfa.byte_classes.get(t.byte)); |
| 1520 |
let index = dense.as_usize() + class; |
| 1521 |
self.nfa.dense[index] = t.next; |
| 1522 |
} |
| 1523 |
self.nfa.states[sid].dense = dense; |
| 1524 |
} |
| 1525 |
Ok(()) |
| 1526 |
} |
| 1527 |
|
| 1528 |
/// Returns a set that tracked queued states. |
| 1529 |
/// |
| 1530 |
/// This is only necessary when ASCII case insensitivity is enabled, since |
| 1531 |
/// it is the only way to visit the same state twice. Otherwise, this |
| 1532 |
/// returns an inert set that nevers adds anything and always reports |
| 1533 |
/// `false` for every member test. |
| 1534 |
fn queued_set(&self) -> QueuedSet { |
| 1535 |
if self.builder.ascii_case_insensitive { |
| 1536 |
QueuedSet::active() |
| 1537 |
} else { |
| 1538 |
QueuedSet::inert() |
| 1539 |
} |
| 1540 |
} |
| 1541 |
|
| 1542 |
/// Initializes the unanchored start state by making it dense. This is |
| 1543 |
/// achieved by explicitly setting every transition to the FAIL state. |
| 1544 |
/// This isn't necessary for correctness, since any missing transition is |
| 1545 |
/// automatically assumed to be mapped to the FAIL state. We do this to |
| 1546 |
/// make the unanchored starting state dense, and thus in turn make |
| 1547 |
/// transition lookups on it faster. (Which is worth doing because it's |
| 1548 |
/// the most active state.) |
| 1549 |
fn init_unanchored_start_state(&mut self) -> Result<(), BuildError> { |
| 1550 |
let start_uid = self.nfa.special.start_unanchored_id; |
| 1551 |
let start_aid = self.nfa.special.start_anchored_id; |
| 1552 |
self.nfa.init_full_state(start_uid, NFA::FAIL)?; |
| 1553 |
self.nfa.init_full_state(start_aid, NFA::FAIL)?; |
| 1554 |
Ok(()) |
| 1555 |
} |
| 1556 |
|
| 1557 |
/// Setup the anchored start state by copying all of the transitions and |
| 1558 |
/// matches from the unanchored starting state with one change: the failure |
| 1559 |
/// transition is changed to the DEAD state, so that for any undefined |
| 1560 |
/// transitions, the search will stop. |
| 1561 |
fn set_anchored_start_state(&mut self) -> Result<(), BuildError> { |
| 1562 |
let start_uid = self.nfa.special.start_unanchored_id; |
| 1563 |
let start_aid = self.nfa.special.start_anchored_id; |
| 1564 |
let (mut uprev_link, mut aprev_link) = (None, None); |
| 1565 |
loop { |
| 1566 |
let unext = self.nfa.next_link(start_uid, uprev_link); |
| 1567 |
let anext = self.nfa.next_link(start_aid, aprev_link); |
| 1568 |
let (ulink, alink) = match (unext, anext) { |
| 1569 |
(Some(ulink), Some(alink)) => (ulink, alink), |
| 1570 |
(None, None) => break, |
| 1571 |
_ => unreachable!(), |
| 1572 |
}; |
| 1573 |
uprev_link = Some(ulink); |
| 1574 |
aprev_link = Some(alink); |
| 1575 |
self.nfa.sparse[alink].next = self.nfa.sparse[ulink].next; |
| 1576 |
} |
| 1577 |
self.nfa.copy_matches(start_uid, start_aid)?; |
| 1578 |
// This is the main difference between the unanchored and anchored |
| 1579 |
// starting states. If a lookup on an anchored starting state fails, |
| 1580 |
// then the search should stop. |
| 1581 |
// |
| 1582 |
// N.B. This assumes that the loop on the unanchored starting state |
| 1583 |
// hasn't been created yet. |
| 1584 |
self.nfa.states[start_aid].fail = NFA::DEAD; |
| 1585 |
Ok(()) |
| 1586 |
} |
| 1587 |
|
| 1588 |
/// Set the failure transitions on the start state to loop back to the |
| 1589 |
/// start state. This effectively permits the Aho-Corasick automaton to |
| 1590 |
/// match at any position. This is also required for finding the next |
| 1591 |
/// state to terminate, namely, finding the next state should never return |
| 1592 |
/// a fail_id. |
| 1593 |
/// |
| 1594 |
/// This must be done after building the initial trie, since trie |
| 1595 |
/// construction depends on transitions to `fail_id` to determine whether a |
| 1596 |
/// state already exists or not. |
| 1597 |
fn add_unanchored_start_state_loop(&mut self) { |
| 1598 |
let start_uid = self.nfa.special.start_unanchored_id; |
| 1599 |
let mut prev_link = None; |
| 1600 |
while let Some(link) = self.nfa.next_link(start_uid, prev_link) { |
| 1601 |
prev_link = Some(link); |
| 1602 |
if self.nfa.sparse[link].next() == NFA::FAIL { |
| 1603 |
self.nfa.sparse[link].next = start_uid; |
| 1604 |
} |
| 1605 |
} |
| 1606 |
} |
| 1607 |
|
| 1608 |
/// Remove the start state loop by rewriting any transitions on the start |
| 1609 |
/// state back to the start state with transitions to the dead state. |
| 1610 |
/// |
| 1611 |
/// The loop is only closed when two conditions are met: the start state |
| 1612 |
/// is a match state and the match kind is leftmost-first or |
| 1613 |
/// leftmost-longest. |
| 1614 |
/// |
| 1615 |
/// The reason for this is that under leftmost semantics, a start state |
| 1616 |
/// that is also a match implies that we should never restart the search |
| 1617 |
/// process. We allow normal transitions out of the start state, but if |
| 1618 |
/// none exist, we transition to the dead state, which signals that |
| 1619 |
/// searching should stop. |
| 1620 |
fn close_start_state_loop_for_leftmost(&mut self) { |
| 1621 |
let start_uid = self.nfa.special.start_unanchored_id; |
| 1622 |
let start = &mut self.nfa.states[start_uid]; |
| 1623 |
let dense = start.dense; |
| 1624 |
if self.builder.match_kind.is_leftmost() && start.is_match() { |
| 1625 |
let mut prev_link = None; |
| 1626 |
while let Some(link) = self.nfa.next_link(start_uid, prev_link) { |
| 1627 |
prev_link = Some(link); |
| 1628 |
if self.nfa.sparse[link].next() == start_uid { |
| 1629 |
self.nfa.sparse[link].next = NFA::DEAD; |
| 1630 |
if dense != StateID::ZERO { |
| 1631 |
let b = self.nfa.sparse[link].byte; |
| 1632 |
let class = usize::from(self.nfa.byte_classes.get(b)); |
| 1633 |
self.nfa.dense[dense.as_usize() + class] = NFA::DEAD; |
| 1634 |
} |
| 1635 |
} |
| 1636 |
} |
| 1637 |
} |
| 1638 |
} |
| 1639 |
|
| 1640 |
/// Sets all transitions on the dead state to point back to the dead state. |
| 1641 |
/// Normally, missing transitions map back to the failure state, but the |
| 1642 |
/// point of the dead state is to act as a sink that can never be escaped. |
| 1643 |
fn add_dead_state_loop(&mut self) -> Result<(), BuildError> { |
| 1644 |
self.nfa.init_full_state(NFA::DEAD, NFA::DEAD)?; |
| 1645 |
Ok(()) |
| 1646 |
} |
| 1647 |
} |
| 1648 |
|
| 1649 |
/// A set of state identifiers used to avoid revisiting the same state multiple |
| 1650 |
/// times when filling in failure transitions. |
| 1651 |
/// |
| 1652 |
/// This set has an "inert" and an "active" mode. When inert, the set never |
| 1653 |
/// stores anything and always returns `false` for every member test. This is |
| 1654 |
/// useful to avoid the performance and memory overhead of maintaining this |
| 1655 |
/// set when it is not needed. |
| 1656 |
#[derive(Debug)] |
| 1657 |
struct QueuedSet { |
| 1658 |
set: Option<BTreeSet<StateID>>, |
| 1659 |
} |
| 1660 |
|
| 1661 |
impl QueuedSet { |
| 1662 |
/// Return an inert set that returns `false` for every state ID membership |
| 1663 |
/// test. |
| 1664 |
fn inert() -> QueuedSet { |
| 1665 |
QueuedSet { set: None } |
| 1666 |
} |
| 1667 |
|
| 1668 |
/// Return an active set that tracks state ID membership. |
| 1669 |
fn active() -> QueuedSet { |
| 1670 |
QueuedSet { set: Some(BTreeSet::new()) } |
| 1671 |
} |
| 1672 |
|
| 1673 |
/// Inserts the given state ID into this set. (If the set is inert, then |
| 1674 |
/// this is a no-op.) |
| 1675 |
fn insert(&mut self, state_id: StateID) { |
| 1676 |
if let Some(ref mut set) = self.set { |
| 1677 |
set.insert(state_id); |
| 1678 |
} |
| 1679 |
} |
| 1680 |
|
| 1681 |
/// Returns true if and only if the given state ID is in this set. If the |
| 1682 |
/// set is inert, this always returns false. |
| 1683 |
fn contains(&self, state_id: StateID) -> bool { |
| 1684 |
match self.set { |
| 1685 |
None => false, |
| 1686 |
Some(ref set) => set.contains(&state_id), |
| 1687 |
} |
| 1688 |
} |
| 1689 |
} |
| 1690 |
|
| 1691 |
impl core::fmt::Debug for NFA { |
| 1692 |
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { |
| 1693 |
use crate::{ |
| 1694 |
automaton::{fmt_state_indicator, sparse_transitions}, |
| 1695 |
util::debug::DebugByte, |
| 1696 |
}; |
| 1697 |
|
| 1698 |
writeln!(f, "noncontiguous::NFA(")?; |
| 1699 |
for (sid, state) in self.states.iter().with_state_ids() { |
| 1700 |
// The FAIL state doesn't actually have space for a state allocated |
| 1701 |
// for it, so we have to treat it as a special case. |
| 1702 |
if sid == NFA::FAIL { |
| 1703 |
writeln!(f, "F {:06}:", sid.as_usize())?; |
| 1704 |
continue; |
| 1705 |
} |
| 1706 |
fmt_state_indicator(f, self, sid)?; |
| 1707 |
write!( |
| 1708 |
f, |
| 1709 |
"{:06}({:06}): ", |
| 1710 |
sid.as_usize(), |
| 1711 |
state.fail.as_usize() |
| 1712 |
)?; |
| 1713 |
|
| 1714 |
let it = sparse_transitions( |
| 1715 |
self.iter_trans(sid).map(|t| (t.byte, t.next)), |
| 1716 |
) |
| 1717 |
.enumerate(); |
| 1718 |
for (i, (start, end, sid)) in it { |
| 1719 |
if i > 0 { |
| 1720 |
write!(f, ", ")?; |
| 1721 |
} |
| 1722 |
if start == end { |
| 1723 |
write!( |
| 1724 |
f, |
| 1725 |
"{:?} => {:?}", |
| 1726 |
DebugByte(start), |
| 1727 |
sid.as_usize() |
| 1728 |
)?; |
| 1729 |
} else { |
| 1730 |
write!( |
| 1731 |
f, |
| 1732 |
"{:?}-{:?} => {:?}", |
| 1733 |
DebugByte(start), |
| 1734 |
DebugByte(end), |
| 1735 |
sid.as_usize() |
| 1736 |
)?; |
| 1737 |
} |
| 1738 |
} |
| 1739 |
|
| 1740 |
write!(f, "\n")?; |
| 1741 |
if self.is_match(sid) { |
| 1742 |
write!(f, " matches: ")?; |
| 1743 |
for (i, pid) in self.iter_matches(sid).enumerate() { |
| 1744 |
if i > 0 { |
| 1745 |
write!(f, ", ")?; |
| 1746 |
} |
| 1747 |
write!(f, "{}", pid.as_usize())?; |
| 1748 |
} |
| 1749 |
write!(f, "\n")?; |
| 1750 |
} |
| 1751 |
} |
| 1752 |
writeln!(f, "match kind: {:?}", self.match_kind)?; |
| 1753 |
writeln!(f, "prefilter: {:?}", self.prefilter.is_some())?; |
| 1754 |
writeln!(f, "state length: {:?}", self.states.len())?; |
| 1755 |
writeln!(f, "pattern length: {:?}", self.patterns_len())?; |
| 1756 |
writeln!(f, "shortest pattern length: {:?}", self.min_pattern_len)?; |
| 1757 |
writeln!(f, "longest pattern length: {:?}", self.max_pattern_len)?; |
| 1758 |
writeln!(f, "memory usage: {:?}", self.memory_usage())?; |
| 1759 |
writeln!(f, ")")?; |
| 1760 |
Ok(()) |
| 1761 |
} |
| 1762 |
} |