| 1 |
/*! |
| 2 |
Provides direct access to a DFA 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 DFA directly. Using an `DFA` directly is typically only necessary |
| 7 |
when one needs access to the [`Automaton`] trait implementation. |
| 8 |
*/ |
| 9 |
|
| 10 |
use alloc::{vec, vec::Vec}; |
| 11 |
|
| 12 |
use crate::{ |
| 13 |
automaton::Automaton, |
| 14 |
nfa::noncontiguous, |
| 15 |
util::{ |
| 16 |
alphabet::ByteClasses, |
| 17 |
error::{BuildError, MatchError}, |
| 18 |
int::{Usize, U32}, |
| 19 |
prefilter::Prefilter, |
| 20 |
primitives::{IteratorIndexExt, PatternID, SmallIndex, StateID}, |
| 21 |
search::{Anchored, MatchKind, StartKind}, |
| 22 |
special::Special, |
| 23 |
}, |
| 24 |
}; |
| 25 |
|
| 26 |
/// A DFA implementation of Aho-Corasick. |
| 27 |
/// |
| 28 |
/// When possible, prefer using [`AhoCorasick`](crate::AhoCorasick) instead of |
| 29 |
/// this type directly. Using a `DFA` directly is typically only necessary when |
| 30 |
/// one needs access to the [`Automaton`] trait implementation. |
| 31 |
/// |
| 32 |
/// This DFA can only be built by first constructing a [`noncontiguous::NFA`]. |
| 33 |
/// Both [`DFA::new`] and [`Builder::build`] do this for you automatically, but |
| 34 |
/// [`Builder::build_from_noncontiguous`] permits doing it explicitly. |
| 35 |
/// |
| 36 |
/// A DFA provides the best possible search performance (in this crate) via two |
| 37 |
/// mechanisms: |
| 38 |
/// |
| 39 |
/// * All states use a dense representation for their transitions. |
| 40 |
/// * All failure transitions are pre-computed such that they are never |
| 41 |
/// explicitly handled at search time. |
| 42 |
/// |
| 43 |
/// These two facts combined mean that every state transition is performed |
| 44 |
/// using a constant number of instructions. However, this comes at |
| 45 |
/// great cost. The memory usage of a DFA can be quite exorbitant. |
| 46 |
/// It is potentially multiple orders of magnitude greater than a |
| 47 |
/// [`contiguous::NFA`](crate::nfa::contiguous::NFA) for example. In exchange, |
| 48 |
/// a DFA will typically have better search speed than a `contiguous::NFA`, but |
| 49 |
/// not by orders of magnitude. |
| 50 |
/// |
| 51 |
/// Unless you have a small number of patterns or memory usage is not a concern |
| 52 |
/// and search performance is critical, a DFA is usually not the best choice. |
| 53 |
/// |
| 54 |
/// Moreover, unlike the NFAs in this crate, it is costly for a DFA to |
| 55 |
/// support for anchored and unanchored search configurations. Namely, |
| 56 |
/// since failure transitions are pre-computed, supporting both anchored |
| 57 |
/// and unanchored searches requires a duplication of the transition table, |
| 58 |
/// making the memory usage of such a DFA ever bigger. (The NFAs in this crate |
| 59 |
/// unconditionally support both anchored and unanchored searches because there |
| 60 |
/// is essentially no added cost for doing so.) It is for this reason that |
| 61 |
/// a DFA's support for anchored and unanchored searches can be configured |
| 62 |
/// via [`Builder::start_kind`]. By default, a DFA only supports unanchored |
| 63 |
/// searches. |
| 64 |
/// |
| 65 |
/// # Example |
| 66 |
/// |
| 67 |
/// This example shows how to build an `DFA` directly and use it to execute |
| 68 |
/// [`Automaton::try_find`]: |
| 69 |
/// |
| 70 |
/// ``` |
| 71 |
/// use aho_corasick::{ |
| 72 |
/// automaton::Automaton, |
| 73 |
/// dfa::DFA, |
| 74 |
/// Input, Match, |
| 75 |
/// }; |
| 76 |
/// |
| 77 |
/// let patterns = &["b", "abc", "abcd"]; |
| 78 |
/// let haystack = "abcd"; |
| 79 |
/// |
| 80 |
/// let nfa = DFA::new(patterns).unwrap(); |
| 81 |
/// assert_eq!( |
| 82 |
/// Some(Match::must(0, 1..2)), |
| 83 |
/// nfa.try_find(&Input::new(haystack))?, |
| 84 |
/// ); |
| 85 |
/// # Ok::<(), Box<dyn std::error::Error>>(()) |
| 86 |
/// ``` |
| 87 |
/// |
| 88 |
/// It is also possible to implement your own version of `try_find`. See the |
| 89 |
/// [`Automaton`] documentation for an example. |
| 90 |
#[derive(Clone)] |
| 91 |
pub struct DFA { |
| 92 |
/// The DFA transition table. IDs in this table are pre-multiplied. So |
| 93 |
/// instead of the IDs being 0, 1, 2, 3, ..., they are 0*stride, 1*stride, |
| 94 |
/// 2*stride, 3*stride, ... |
| 95 |
trans: Vec<StateID>, |
| 96 |
/// The matches for every match state in this DFA. This is first indexed by |
| 97 |
/// state index (so that's `sid >> stride2`) and then by order in which the |
| 98 |
/// matches are meant to occur. |
| 99 |
matches: Vec<Vec<PatternID>>, |
| 100 |
/// The amount of heap memory used, in bytes, by the inner Vecs of |
| 101 |
/// 'matches'. |
| 102 |
matches_memory_usage: usize, |
| 103 |
/// The length of each pattern. This is used to compute the start offset |
| 104 |
/// of a match. |
| 105 |
pattern_lens: Vec<SmallIndex>, |
| 106 |
/// A prefilter for accelerating searches, if one exists. |
| 107 |
prefilter: Option<Prefilter>, |
| 108 |
/// The match semantics built into this DFA. |
| 109 |
match_kind: MatchKind, |
| 110 |
/// The total number of states in this DFA. |
| 111 |
state_len: usize, |
| 112 |
/// The alphabet size, or total number of equivalence classes, for this |
| 113 |
/// DFA. Note that the actual number of transitions in each state is |
| 114 |
/// stride=2^stride2, where stride is the smallest power of 2 greater than |
| 115 |
/// or equal to alphabet_len. We do things this way so that we can use |
| 116 |
/// bitshifting to go from a state ID to an index into 'matches'. |
| 117 |
alphabet_len: usize, |
| 118 |
/// The exponent with a base 2, such that stride=2^stride2. Given a state |
| 119 |
/// index 'i', its state identifier is 'i << stride2'. Given a state |
| 120 |
/// identifier 'sid', its state index is 'sid >> stride2'. |
| 121 |
stride2: usize, |
| 122 |
/// The equivalence classes for this DFA. All transitions are defined on |
| 123 |
/// equivalence classes and not on the 256 distinct byte values. |
| 124 |
byte_classes: ByteClasses, |
| 125 |
/// The length of the shortest pattern in this automaton. |
| 126 |
min_pattern_len: usize, |
| 127 |
/// The length of the longest pattern in this automaton. |
| 128 |
max_pattern_len: usize, |
| 129 |
/// The information required to deduce which states are "special" in this |
| 130 |
/// DFA. |
| 131 |
special: Special, |
| 132 |
} |
| 133 |
|
| 134 |
impl DFA { |
| 135 |
/// Create a new Aho-Corasick DFA using the default configuration. |
| 136 |
/// |
| 137 |
/// Use a [`Builder`] if you want to change the configuration. |
| 138 |
pub fn new<I, P>(patterns: I) -> Result<DFA, BuildError> |
| 139 |
where |
| 140 |
I: IntoIterator<Item = P>, |
| 141 |
P: AsRef<[u8]>, |
| 142 |
{ |
| 143 |
DFA::builder().build(patterns) |
| 144 |
} |
| 145 |
|
| 146 |
/// A convenience method for returning a new Aho-Corasick DFA builder. |
| 147 |
/// |
| 148 |
/// This usually permits one to just import the `DFA` type. |
| 149 |
pub fn builder() -> Builder { |
| 150 |
Builder::new() |
| 151 |
} |
| 152 |
} |
| 153 |
|
| 154 |
impl DFA { |
| 155 |
/// A sentinel state ID indicating that a search should stop once it has |
| 156 |
/// entered this state. When a search stops, it returns a match if one has |
| 157 |
/// been found, otherwise no match. A DFA always has an actual dead state |
| 158 |
/// at this ID. |
| 159 |
/// |
| 160 |
/// N.B. DFAs, unlike NFAs, do not have any notion of a FAIL state. |
| 161 |
/// Namely, the whole point of a DFA is that the FAIL state is completely |
| 162 |
/// compiled away. That is, DFA construction involves pre-computing the |
| 163 |
/// failure transitions everywhere, such that failure transitions are no |
| 164 |
/// longer used at search time. This, combined with its uniformly dense |
| 165 |
/// representation, are the two most important factors in why it's faster |
| 166 |
/// than the NFAs in this crate. |
| 167 |
const DEAD: StateID = StateID::new_unchecked(0); |
| 168 |
|
| 169 |
/// Adds the given pattern IDs as matches to the given state and also |
| 170 |
/// records the added memory usage. |
| 171 |
fn set_matches( |
| 172 |
&mut self, |
| 173 |
sid: StateID, |
| 174 |
pids: impl Iterator<Item = PatternID>, |
| 175 |
) { |
| 176 |
let index = (sid.as_usize() >> self.stride2).checked_sub(2).unwrap(); |
| 177 |
let mut at_least_one = false; |
| 178 |
for pid in pids { |
| 179 |
self.matches[index].push(pid); |
| 180 |
self.matches_memory_usage += PatternID::SIZE; |
| 181 |
at_least_one = true; |
| 182 |
} |
| 183 |
assert!(at_least_one, "match state must have non-empty pids"); |
| 184 |
} |
| 185 |
} |
| 186 |
|
| 187 |
// SAFETY: 'start_state' always returns a valid state ID, 'next_state' always |
| 188 |
// returns a valid state ID given a valid state ID. We otherwise claim that |
| 189 |
// all other methods are correct as well. |
| 190 |
unsafe impl Automaton for DFA { |
| 191 |
#[inline(always)] |
| 192 |
fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError> { |
| 193 |
// Either of the start state IDs can be DEAD, in which case, support |
| 194 |
// for that type of search is not provided by this DFA. Which start |
| 195 |
// state IDs are inactive depends on the 'StartKind' configuration at |
| 196 |
// DFA construction time. |
| 197 |
match anchored { |
| 198 |
Anchored::No => { |
| 199 |
let start = self.special.start_unanchored_id; |
| 200 |
if start == DFA::DEAD { |
| 201 |
Err(MatchError::invalid_input_unanchored()) |
| 202 |
} else { |
| 203 |
Ok(start) |
| 204 |
} |
| 205 |
} |
| 206 |
Anchored::Yes => { |
| 207 |
let start = self.special.start_anchored_id; |
| 208 |
if start == DFA::DEAD { |
| 209 |
Err(MatchError::invalid_input_anchored()) |
| 210 |
} else { |
| 211 |
Ok(start) |
| 212 |
} |
| 213 |
} |
| 214 |
} |
| 215 |
} |
| 216 |
|
| 217 |
#[inline(always)] |
| 218 |
fn next_state( |
| 219 |
&self, |
| 220 |
_anchored: Anchored, |
| 221 |
sid: StateID, |
| 222 |
byte: u8, |
| 223 |
) -> StateID { |
| 224 |
let class = self.byte_classes.get(byte); |
| 225 |
self.trans[(sid.as_u32() + u32::from(class)).as_usize()] |
| 226 |
} |
| 227 |
|
| 228 |
#[inline(always)] |
| 229 |
fn is_special(&self, sid: StateID) -> bool { |
| 230 |
sid <= self.special.max_special_id |
| 231 |
} |
| 232 |
|
| 233 |
#[inline(always)] |
| 234 |
fn is_dead(&self, sid: StateID) -> bool { |
| 235 |
sid == DFA::DEAD |
| 236 |
} |
| 237 |
|
| 238 |
#[inline(always)] |
| 239 |
fn is_match(&self, sid: StateID) -> bool { |
| 240 |
!self.is_dead(sid) && sid <= self.special.max_match_id |
| 241 |
} |
| 242 |
|
| 243 |
#[inline(always)] |
| 244 |
fn is_start(&self, sid: StateID) -> bool { |
| 245 |
sid == self.special.start_unanchored_id |
| 246 |
|| sid == self.special.start_anchored_id |
| 247 |
} |
| 248 |
|
| 249 |
#[inline(always)] |
| 250 |
fn match_kind(&self) -> MatchKind { |
| 251 |
self.match_kind |
| 252 |
} |
| 253 |
|
| 254 |
#[inline(always)] |
| 255 |
fn patterns_len(&self) -> usize { |
| 256 |
self.pattern_lens.len() |
| 257 |
} |
| 258 |
|
| 259 |
#[inline(always)] |
| 260 |
fn pattern_len(&self, pid: PatternID) -> usize { |
| 261 |
self.pattern_lens[pid].as_usize() |
| 262 |
} |
| 263 |
|
| 264 |
#[inline(always)] |
| 265 |
fn min_pattern_len(&self) -> usize { |
| 266 |
self.min_pattern_len |
| 267 |
} |
| 268 |
|
| 269 |
#[inline(always)] |
| 270 |
fn max_pattern_len(&self) -> usize { |
| 271 |
self.max_pattern_len |
| 272 |
} |
| 273 |
|
| 274 |
#[inline(always)] |
| 275 |
fn match_len(&self, sid: StateID) -> usize { |
| 276 |
debug_assert!(self.is_match(sid)); |
| 277 |
let offset = (sid.as_usize() >> self.stride2) - 2; |
| 278 |
self.matches[offset].len() |
| 279 |
} |
| 280 |
|
| 281 |
#[inline(always)] |
| 282 |
fn match_pattern(&self, sid: StateID, index: usize) -> PatternID { |
| 283 |
debug_assert!(self.is_match(sid)); |
| 284 |
let offset = (sid.as_usize() >> self.stride2) - 2; |
| 285 |
self.matches[offset][index] |
| 286 |
} |
| 287 |
|
| 288 |
#[inline(always)] |
| 289 |
fn memory_usage(&self) -> usize { |
| 290 |
use core::mem::size_of; |
| 291 |
|
| 292 |
(self.trans.len() * size_of::<u32>()) |
| 293 |
+ (self.matches.len() * size_of::<Vec<PatternID>>()) |
| 294 |
+ self.matches_memory_usage |
| 295 |
+ (self.pattern_lens.len() * size_of::<SmallIndex>()) |
| 296 |
+ self.prefilter.as_ref().map_or(0, |p| p.memory_usage()) |
| 297 |
} |
| 298 |
|
| 299 |
#[inline(always)] |
| 300 |
fn prefilter(&self) -> Option<&Prefilter> { |
| 301 |
self.prefilter.as_ref() |
| 302 |
} |
| 303 |
} |
| 304 |
|
| 305 |
impl core::fmt::Debug for DFA { |
| 306 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 307 |
use crate::{ |
| 308 |
automaton::{fmt_state_indicator, sparse_transitions}, |
| 309 |
util::debug::DebugByte, |
| 310 |
}; |
| 311 |
|
| 312 |
writeln!(f, "dfa::DFA(")?; |
| 313 |
for index in 0..self.state_len { |
| 314 |
let sid = StateID::new_unchecked(index << self.stride2); |
| 315 |
// While we do currently include the FAIL state in the transition |
| 316 |
// table (to simplify construction), it is never actually used. It |
| 317 |
// poses problems with the code below because it gets treated as |
| 318 |
// a match state incidentally when it is, of course, not. So we |
| 319 |
// special case it. The fail state is always the first state after |
| 320 |
// the dead state. |
| 321 |
// |
| 322 |
// If the construction is changed to remove the fail state (it |
| 323 |
// probably should be), then this special case should be updated. |
| 324 |
if index == 1 { |
| 325 |
writeln!(f, "F {:06}:", sid.as_usize())?; |
| 326 |
continue; |
| 327 |
} |
| 328 |
fmt_state_indicator(f, self, sid)?; |
| 329 |
write!(f, "{:06}: ", sid.as_usize())?; |
| 330 |
|
| 331 |
let it = (0..self.byte_classes.alphabet_len()).map(|class| { |
| 332 |
(class.as_u8(), self.trans[sid.as_usize() + class]) |
| 333 |
}); |
| 334 |
for (i, (start, end, next)) in sparse_transitions(it).enumerate() { |
| 335 |
if i > 0 { |
| 336 |
write!(f, ", ")?; |
| 337 |
} |
| 338 |
if start == end { |
| 339 |
write!( |
| 340 |
f, |
| 341 |
"{:?} => {:?}", |
| 342 |
DebugByte(start), |
| 343 |
next.as_usize() |
| 344 |
)?; |
| 345 |
} else { |
| 346 |
write!( |
| 347 |
f, |
| 348 |
"{:?}-{:?} => {:?}", |
| 349 |
DebugByte(start), |
| 350 |
DebugByte(end), |
| 351 |
next.as_usize() |
| 352 |
)?; |
| 353 |
} |
| 354 |
} |
| 355 |
write!(f, "\n")?; |
| 356 |
if self.is_match(sid) { |
| 357 |
write!(f, " matches: ")?; |
| 358 |
for i in 0..self.match_len(sid) { |
| 359 |
if i > 0 { |
| 360 |
write!(f, ", ")?; |
| 361 |
} |
| 362 |
let pid = self.match_pattern(sid, i); |
| 363 |
write!(f, "{}", pid.as_usize())?; |
| 364 |
} |
| 365 |
write!(f, "\n")?; |
| 366 |
} |
| 367 |
} |
| 368 |
writeln!(f, "match kind: {:?}", self.match_kind)?; |
| 369 |
writeln!(f, "prefilter: {:?}", self.prefilter.is_some())?; |
| 370 |
writeln!(f, "state length: {:?}", self.state_len)?; |
| 371 |
writeln!(f, "pattern length: {:?}", self.patterns_len())?; |
| 372 |
writeln!(f, "shortest pattern length: {:?}", self.min_pattern_len)?; |
| 373 |
writeln!(f, "longest pattern length: {:?}", self.max_pattern_len)?; |
| 374 |
writeln!(f, "alphabet length: {:?}", self.alphabet_len)?; |
| 375 |
writeln!(f, "stride: {:?}", 1 << self.stride2)?; |
| 376 |
writeln!(f, "byte classes: {:?}", self.byte_classes)?; |
| 377 |
writeln!(f, "memory usage: {:?}", self.memory_usage())?; |
| 378 |
writeln!(f, ")")?; |
| 379 |
Ok(()) |
| 380 |
} |
| 381 |
} |
| 382 |
|
| 383 |
/// A builder for configuring an Aho-Corasick DFA. |
| 384 |
/// |
| 385 |
/// This builder has a subset of the options available to a |
| 386 |
/// [`AhoCorasickBuilder`](crate::AhoCorasickBuilder). Of the shared options, |
| 387 |
/// their behavior is identical. |
| 388 |
#[derive(Clone, Debug)] |
| 389 |
pub struct Builder { |
| 390 |
noncontiguous: noncontiguous::Builder, |
| 391 |
start_kind: StartKind, |
| 392 |
byte_classes: bool, |
| 393 |
} |
| 394 |
|
| 395 |
impl Default for Builder { |
| 396 |
fn default() -> Builder { |
| 397 |
Builder { |
| 398 |
noncontiguous: noncontiguous::Builder::new(), |
| 399 |
start_kind: StartKind::Unanchored, |
| 400 |
byte_classes: true, |
| 401 |
} |
| 402 |
} |
| 403 |
} |
| 404 |
|
| 405 |
impl Builder { |
| 406 |
/// Create a new builder for configuring an Aho-Corasick DFA. |
| 407 |
pub fn new() -> Builder { |
| 408 |
Builder::default() |
| 409 |
} |
| 410 |
|
| 411 |
/// Build an Aho-Corasick DFA from the given iterator of patterns. |
| 412 |
/// |
| 413 |
/// A builder may be reused to create more DFAs. |
| 414 |
pub fn build<I, P>(&self, patterns: I) -> Result<DFA, BuildError> |
| 415 |
where |
| 416 |
I: IntoIterator<Item = P>, |
| 417 |
P: AsRef<[u8]>, |
| 418 |
{ |
| 419 |
let nnfa = self.noncontiguous.build(patterns)?; |
| 420 |
self.build_from_noncontiguous(&nnfa) |
| 421 |
} |
| 422 |
|
| 423 |
/// Build an Aho-Corasick DFA from the given noncontiguous NFA. |
| 424 |
/// |
| 425 |
/// Note that when this method is used, only the `start_kind` and |
| 426 |
/// `byte_classes` settings on this builder are respected. The other |
| 427 |
/// settings only apply to the initial construction of the Aho-Corasick |
| 428 |
/// automaton. Since using this method requires that initial construction |
| 429 |
/// has already completed, all settings impacting only initial construction |
| 430 |
/// are no longer relevant. |
| 431 |
pub fn build_from_noncontiguous( |
| 432 |
&self, |
| 433 |
nnfa: &noncontiguous::NFA, |
| 434 |
) -> Result<DFA, BuildError> { |
| 435 |
debug!("building DFA"); |
| 436 |
let byte_classes = if self.byte_classes { |
| 437 |
nnfa.byte_classes().clone() |
| 438 |
} else { |
| 439 |
ByteClasses::singletons() |
| 440 |
}; |
| 441 |
let state_len = match self.start_kind { |
| 442 |
StartKind::Unanchored | StartKind::Anchored => nnfa.states().len(), |
| 443 |
StartKind::Both => { |
| 444 |
// These unwraps are OK because we know that the number of |
| 445 |
// NFA states is < StateID::LIMIT which is in turn less than |
| 446 |
// i32::MAX. Thus, there is always room to multiply by 2. |
| 447 |
// Finally, the number of states is always at least 4 in the |
| 448 |
// NFA (DEAD, FAIL, START-UNANCHORED, START-ANCHORED), so the |
| 449 |
// subtraction of 4 is okay. |
| 450 |
// |
| 451 |
// Note that we subtract 4 because the "anchored" part of |
| 452 |
// the DFA duplicates the unanchored part (without failure |
| 453 |
// transitions), but reuses the DEAD, FAIL and START states. |
| 454 |
nnfa.states() |
| 455 |
.len() |
| 456 |
.checked_mul(2) |
| 457 |
.unwrap() |
| 458 |
.checked_sub(4) |
| 459 |
.unwrap() |
| 460 |
} |
| 461 |
}; |
| 462 |
let trans_len = |
| 463 |
match state_len.checked_shl(byte_classes.stride2().as_u32()) { |
| 464 |
Some(trans_len) => trans_len, |
| 465 |
None => { |
| 466 |
return Err(BuildError::state_id_overflow( |
| 467 |
StateID::MAX.as_u64(), |
| 468 |
usize::MAX.as_u64(), |
| 469 |
)) |
| 470 |
} |
| 471 |
}; |
| 472 |
StateID::new(trans_len.checked_sub(byte_classes.stride()).unwrap()) |
| 473 |
.map_err(|e| { |
| 474 |
BuildError::state_id_overflow( |
| 475 |
StateID::MAX.as_u64(), |
| 476 |
e.attempted(), |
| 477 |
) |
| 478 |
})?; |
| 479 |
let num_match_states = match self.start_kind { |
| 480 |
StartKind::Unanchored | StartKind::Anchored => { |
| 481 |
nnfa.special().max_match_id.as_usize().checked_sub(1).unwrap() |
| 482 |
} |
| 483 |
StartKind::Both => nnfa |
| 484 |
.special() |
| 485 |
.max_match_id |
| 486 |
.as_usize() |
| 487 |
.checked_sub(1) |
| 488 |
.unwrap() |
| 489 |
.checked_mul(2) |
| 490 |
.unwrap(), |
| 491 |
}; |
| 492 |
let mut dfa = DFA { |
| 493 |
trans: vec![DFA::DEAD; trans_len], |
| 494 |
matches: vec![vec![]; num_match_states], |
| 495 |
matches_memory_usage: 0, |
| 496 |
pattern_lens: nnfa.pattern_lens_raw().to_vec(), |
| 497 |
prefilter: nnfa.prefilter().map(|p| p.clone()), |
| 498 |
match_kind: nnfa.match_kind(), |
| 499 |
state_len, |
| 500 |
alphabet_len: byte_classes.alphabet_len(), |
| 501 |
stride2: byte_classes.stride2(), |
| 502 |
byte_classes, |
| 503 |
min_pattern_len: nnfa.min_pattern_len(), |
| 504 |
max_pattern_len: nnfa.max_pattern_len(), |
| 505 |
// The special state IDs are set later. |
| 506 |
special: Special::zero(), |
| 507 |
}; |
| 508 |
match self.start_kind { |
| 509 |
StartKind::Both => { |
| 510 |
self.finish_build_both_starts(nnfa, &mut dfa); |
| 511 |
} |
| 512 |
StartKind::Unanchored => { |
| 513 |
self.finish_build_one_start(Anchored::No, nnfa, &mut dfa); |
| 514 |
} |
| 515 |
StartKind::Anchored => { |
| 516 |
self.finish_build_one_start(Anchored::Yes, nnfa, &mut dfa) |
| 517 |
} |
| 518 |
} |
| 519 |
debug!( |
| 520 |
"DFA built, <states: {:?}, size: {:?}, \ |
| 521 |
alphabet len: {:?}, stride: {:?}>", |
| 522 |
dfa.state_len, |
| 523 |
dfa.memory_usage(), |
| 524 |
dfa.byte_classes.alphabet_len(), |
| 525 |
dfa.byte_classes.stride(), |
| 526 |
); |
| 527 |
// The vectors can grow ~twice as big during construction because a |
| 528 |
// Vec amortizes growth. But here, let's shrink things back down to |
| 529 |
// what we actually need since we're never going to add more to it. |
| 530 |
dfa.trans.shrink_to_fit(); |
| 531 |
dfa.pattern_lens.shrink_to_fit(); |
| 532 |
dfa.matches.shrink_to_fit(); |
| 533 |
// TODO: We might also want to shrink each Vec inside of `dfa.matches`, |
| 534 |
// or even better, convert it to one contiguous allocation. But I think |
| 535 |
// I went with nested allocs for good reason (can't remember), so this |
| 536 |
// may be tricky to do. I decided not to shrink them here because it |
| 537 |
// might require a fair bit of work to do. It's unclear whether it's |
| 538 |
// worth it. |
| 539 |
Ok(dfa) |
| 540 |
} |
| 541 |
|
| 542 |
/// Finishes building a DFA for either unanchored or anchored searches, |
| 543 |
/// but NOT both. |
| 544 |
fn finish_build_one_start( |
| 545 |
&self, |
| 546 |
anchored: Anchored, |
| 547 |
nnfa: &noncontiguous::NFA, |
| 548 |
dfa: &mut DFA, |
| 549 |
) { |
| 550 |
// This function always succeeds because we check above that all of the |
| 551 |
// states in the NFA can be mapped to DFA state IDs. |
| 552 |
let stride2 = dfa.stride2; |
| 553 |
let old2new = |oldsid: StateID| { |
| 554 |
StateID::new_unchecked(oldsid.as_usize() << stride2) |
| 555 |
}; |
| 556 |
for (oldsid, state) in nnfa.states().iter().with_state_ids() { |
| 557 |
let newsid = old2new(oldsid); |
| 558 |
if state.is_match() { |
| 559 |
dfa.set_matches(newsid, nnfa.iter_matches(oldsid)); |
| 560 |
} |
| 561 |
sparse_iter( |
| 562 |
nnfa, |
| 563 |
oldsid, |
| 564 |
&dfa.byte_classes, |
| 565 |
|byte, class, mut oldnextsid| { |
| 566 |
if oldnextsid == noncontiguous::NFA::FAIL { |
| 567 |
if anchored.is_anchored() { |
| 568 |
oldnextsid = noncontiguous::NFA::DEAD; |
| 569 |
} else if state.fail() == noncontiguous::NFA::DEAD { |
| 570 |
// This is a special case that avoids following |
| 571 |
// DEAD transitions in a non-contiguous NFA. |
| 572 |
// Following these transitions is pretty slow |
| 573 |
// because the non-contiguous NFA will always use |
| 574 |
// a sparse representation for it (because the |
| 575 |
// DEAD state is usually treated as a sentinel). |
| 576 |
// The *vast* majority of failure states are DEAD |
| 577 |
// states, so this winds up being pretty slow if |
| 578 |
// we go through the non-contiguous NFA state |
| 579 |
// transition logic. Instead, just do it ourselves. |
| 580 |
oldnextsid = noncontiguous::NFA::DEAD; |
| 581 |
} else { |
| 582 |
oldnextsid = nnfa.next_state( |
| 583 |
Anchored::No, |
| 584 |
state.fail(), |
| 585 |
byte, |
| 586 |
); |
| 587 |
} |
| 588 |
} |
| 589 |
dfa.trans[newsid.as_usize() + usize::from(class)] = |
| 590 |
old2new(oldnextsid); |
| 591 |
}, |
| 592 |
); |
| 593 |
} |
| 594 |
// Now that we've remapped all the IDs in our states, all that's left |
| 595 |
// is remapping the special state IDs. |
| 596 |
let old = nnfa.special(); |
| 597 |
let new = &mut dfa.special; |
| 598 |
new.max_special_id = old2new(old.max_special_id); |
| 599 |
new.max_match_id = old2new(old.max_match_id); |
| 600 |
if anchored.is_anchored() { |
| 601 |
new.start_unanchored_id = DFA::DEAD; |
| 602 |
new.start_anchored_id = old2new(old.start_anchored_id); |
| 603 |
} else { |
| 604 |
new.start_unanchored_id = old2new(old.start_unanchored_id); |
| 605 |
new.start_anchored_id = DFA::DEAD; |
| 606 |
} |
| 607 |
} |
| 608 |
|
| 609 |
/// Finishes building a DFA that supports BOTH unanchored and anchored |
| 610 |
/// searches. It works by inter-leaving unanchored states with anchored |
| 611 |
/// states in the same transition table. This way, we avoid needing to |
| 612 |
/// re-shuffle states afterward to ensure that our states still look like |
| 613 |
/// DEAD, MATCH, ..., START-UNANCHORED, START-ANCHORED, NON-MATCH, ... |
| 614 |
/// |
| 615 |
/// Honestly this is pretty inscrutable... Simplifications are most |
| 616 |
/// welcome. |
| 617 |
fn finish_build_both_starts( |
| 618 |
&self, |
| 619 |
nnfa: &noncontiguous::NFA, |
| 620 |
dfa: &mut DFA, |
| 621 |
) { |
| 622 |
let stride2 = dfa.stride2; |
| 623 |
let stride = 1 << stride2; |
| 624 |
let mut remap_unanchored = vec![DFA::DEAD; nnfa.states().len()]; |
| 625 |
let mut remap_anchored = vec![DFA::DEAD; nnfa.states().len()]; |
| 626 |
let mut is_anchored = vec![false; dfa.state_len]; |
| 627 |
let mut newsid = DFA::DEAD; |
| 628 |
let next_dfa_id = |
| 629 |
|sid: StateID| StateID::new_unchecked(sid.as_usize() + stride); |
| 630 |
for (oldsid, state) in nnfa.states().iter().with_state_ids() { |
| 631 |
if oldsid == noncontiguous::NFA::DEAD |
| 632 |
|| oldsid == noncontiguous::NFA::FAIL |
| 633 |
{ |
| 634 |
remap_unanchored[oldsid] = newsid; |
| 635 |
remap_anchored[oldsid] = newsid; |
| 636 |
newsid = next_dfa_id(newsid); |
| 637 |
} else if oldsid == nnfa.special().start_unanchored_id |
| 638 |
|| oldsid == nnfa.special().start_anchored_id |
| 639 |
{ |
| 640 |
if oldsid == nnfa.special().start_unanchored_id { |
| 641 |
remap_unanchored[oldsid] = newsid; |
| 642 |
remap_anchored[oldsid] = DFA::DEAD; |
| 643 |
} else { |
| 644 |
remap_unanchored[oldsid] = DFA::DEAD; |
| 645 |
remap_anchored[oldsid] = newsid; |
| 646 |
is_anchored[newsid.as_usize() >> stride2] = true; |
| 647 |
} |
| 648 |
if state.is_match() { |
| 649 |
dfa.set_matches(newsid, nnfa.iter_matches(oldsid)); |
| 650 |
} |
| 651 |
sparse_iter( |
| 652 |
nnfa, |
| 653 |
oldsid, |
| 654 |
&dfa.byte_classes, |
| 655 |
|_, class, oldnextsid| { |
| 656 |
let class = usize::from(class); |
| 657 |
if oldnextsid == noncontiguous::NFA::FAIL { |
| 658 |
dfa.trans[newsid.as_usize() + class] = DFA::DEAD; |
| 659 |
} else { |
| 660 |
dfa.trans[newsid.as_usize() + class] = oldnextsid; |
| 661 |
} |
| 662 |
}, |
| 663 |
); |
| 664 |
newsid = next_dfa_id(newsid); |
| 665 |
} else { |
| 666 |
let unewsid = newsid; |
| 667 |
newsid = next_dfa_id(newsid); |
| 668 |
let anewsid = newsid; |
| 669 |
newsid = next_dfa_id(newsid); |
| 670 |
|
| 671 |
remap_unanchored[oldsid] = unewsid; |
| 672 |
remap_anchored[oldsid] = anewsid; |
| 673 |
is_anchored[anewsid.as_usize() >> stride2] = true; |
| 674 |
if state.is_match() { |
| 675 |
dfa.set_matches(unewsid, nnfa.iter_matches(oldsid)); |
| 676 |
dfa.set_matches(anewsid, nnfa.iter_matches(oldsid)); |
| 677 |
} |
| 678 |
sparse_iter( |
| 679 |
nnfa, |
| 680 |
oldsid, |
| 681 |
&dfa.byte_classes, |
| 682 |
|byte, class, oldnextsid| { |
| 683 |
let class = usize::from(class); |
| 684 |
if oldnextsid == noncontiguous::NFA::FAIL { |
| 685 |
let oldnextsid = |
| 686 |
if state.fail() == noncontiguous::NFA::DEAD { |
| 687 |
noncontiguous::NFA::DEAD |
| 688 |
} else { |
| 689 |
nnfa.next_state( |
| 690 |
Anchored::No, |
| 691 |
state.fail(), |
| 692 |
byte, |
| 693 |
) |
| 694 |
}; |
| 695 |
dfa.trans[unewsid.as_usize() + class] = oldnextsid; |
| 696 |
} else { |
| 697 |
dfa.trans[unewsid.as_usize() + class] = oldnextsid; |
| 698 |
dfa.trans[anewsid.as_usize() + class] = oldnextsid; |
| 699 |
} |
| 700 |
}, |
| 701 |
); |
| 702 |
} |
| 703 |
} |
| 704 |
for i in 0..dfa.state_len { |
| 705 |
let sid = i << stride2; |
| 706 |
if is_anchored[i] { |
| 707 |
for next in dfa.trans[sid..][..stride].iter_mut() { |
| 708 |
*next = remap_anchored[*next]; |
| 709 |
} |
| 710 |
} else { |
| 711 |
for next in dfa.trans[sid..][..stride].iter_mut() { |
| 712 |
*next = remap_unanchored[*next]; |
| 713 |
} |
| 714 |
} |
| 715 |
} |
| 716 |
// Now that we've remapped all the IDs in our states, all that's left |
| 717 |
// is remapping the special state IDs. |
| 718 |
let old = nnfa.special(); |
| 719 |
let new = &mut dfa.special; |
| 720 |
new.max_special_id = remap_anchored[old.max_special_id]; |
| 721 |
new.max_match_id = remap_anchored[old.max_match_id]; |
| 722 |
new.start_unanchored_id = remap_unanchored[old.start_unanchored_id]; |
| 723 |
new.start_anchored_id = remap_anchored[old.start_anchored_id]; |
| 724 |
} |
| 725 |
|
| 726 |
/// Set the desired match semantics. |
| 727 |
/// |
| 728 |
/// This only applies when using [`Builder::build`] and not |
| 729 |
/// [`Builder::build_from_noncontiguous`]. |
| 730 |
/// |
| 731 |
/// See |
| 732 |
/// [`AhoCorasickBuilder::match_kind`](crate::AhoCorasickBuilder::match_kind) |
| 733 |
/// for more documentation and examples. |
| 734 |
pub fn match_kind(&mut self, kind: MatchKind) -> &mut Builder { |
| 735 |
self.noncontiguous.match_kind(kind); |
| 736 |
self |
| 737 |
} |
| 738 |
|
| 739 |
/// Enable ASCII-aware case insensitive matching. |
| 740 |
/// |
| 741 |
/// This only applies when using [`Builder::build`] and not |
| 742 |
/// [`Builder::build_from_noncontiguous`]. |
| 743 |
/// |
| 744 |
/// See |
| 745 |
/// [`AhoCorasickBuilder::ascii_case_insensitive`](crate::AhoCorasickBuilder::ascii_case_insensitive) |
| 746 |
/// for more documentation and examples. |
| 747 |
pub fn ascii_case_insensitive(&mut self, yes: bool) -> &mut Builder { |
| 748 |
self.noncontiguous.ascii_case_insensitive(yes); |
| 749 |
self |
| 750 |
} |
| 751 |
|
| 752 |
/// Enable heuristic prefilter optimizations. |
| 753 |
/// |
| 754 |
/// This only applies when using [`Builder::build`] and not |
| 755 |
/// [`Builder::build_from_noncontiguous`]. |
| 756 |
/// |
| 757 |
/// See |
| 758 |
/// [`AhoCorasickBuilder::prefilter`](crate::AhoCorasickBuilder::prefilter) |
| 759 |
/// for more documentation and examples. |
| 760 |
pub fn prefilter(&mut self, yes: bool) -> &mut Builder { |
| 761 |
self.noncontiguous.prefilter(yes); |
| 762 |
self |
| 763 |
} |
| 764 |
|
| 765 |
/// Sets the starting state configuration for the automaton. |
| 766 |
/// |
| 767 |
/// See |
| 768 |
/// [`AhoCorasickBuilder::start_kind`](crate::AhoCorasickBuilder::start_kind) |
| 769 |
/// for more documentation and examples. |
| 770 |
pub fn start_kind(&mut self, kind: StartKind) -> &mut Builder { |
| 771 |
self.start_kind = kind; |
| 772 |
self |
| 773 |
} |
| 774 |
|
| 775 |
/// A debug setting for whether to attempt to shrink the size of the |
| 776 |
/// automaton's alphabet or not. |
| 777 |
/// |
| 778 |
/// This should never be enabled unless you're debugging an automaton. |
| 779 |
/// Namely, disabling byte classes makes transitions easier to reason |
| 780 |
/// about, since they use the actual bytes instead of equivalence classes. |
| 781 |
/// Disabling this confers no performance benefit at search time. |
| 782 |
/// |
| 783 |
/// See |
| 784 |
/// [`AhoCorasickBuilder::byte_classes`](crate::AhoCorasickBuilder::byte_classes) |
| 785 |
/// for more documentation and examples. |
| 786 |
pub fn byte_classes(&mut self, yes: bool) -> &mut Builder { |
| 787 |
self.byte_classes = yes; |
| 788 |
self |
| 789 |
} |
| 790 |
} |
| 791 |
|
| 792 |
/// Iterate over all possible equivalence class transitions in this state. |
| 793 |
/// The closure is called for all transitions with a distinct equivalence |
| 794 |
/// class, even those not explicitly represented in this sparse state. For |
| 795 |
/// any implicitly defined transitions, the given closure is called with |
| 796 |
/// the fail state ID. |
| 797 |
/// |
| 798 |
/// The closure is guaranteed to be called precisely |
| 799 |
/// `byte_classes.alphabet_len()` times, once for every possible class in |
| 800 |
/// ascending order. |
| 801 |
fn sparse_iter<F: FnMut(u8, u8, StateID)>( |
| 802 |
nnfa: &noncontiguous::NFA, |
| 803 |
oldsid: StateID, |
| 804 |
classes: &ByteClasses, |
| 805 |
mut f: F, |
| 806 |
) { |
| 807 |
let mut prev_class = None; |
| 808 |
let mut byte = 0usize; |
| 809 |
for t in nnfa.iter_trans(oldsid) { |
| 810 |
while byte < usize::from(t.byte()) { |
| 811 |
let rep = byte.as_u8(); |
| 812 |
let class = classes.get(rep); |
| 813 |
byte += 1; |
| 814 |
if prev_class != Some(class) { |
| 815 |
f(rep, class, noncontiguous::NFA::FAIL); |
| 816 |
prev_class = Some(class); |
| 817 |
} |
| 818 |
} |
| 819 |
let rep = t.byte(); |
| 820 |
let class = classes.get(rep); |
| 821 |
byte += 1; |
| 822 |
if prev_class != Some(class) { |
| 823 |
f(rep, class, t.next()); |
| 824 |
prev_class = Some(class); |
| 825 |
} |
| 826 |
} |
| 827 |
for b in byte..=255 { |
| 828 |
let rep = b.as_u8(); |
| 829 |
let class = classes.get(rep); |
| 830 |
if prev_class != Some(class) { |
| 831 |
f(rep, class, noncontiguous::NFA::FAIL); |
| 832 |
prev_class = Some(class); |
| 833 |
} |
| 834 |
} |
| 835 |
} |