| /*! |
| Provides direct access to a DFA implementation of Aho-Corasick. |
| |
| This is a low-level API that generally only needs to be used in niche |
| circumstances. When possible, prefer using [`AhoCorasick`](crate::AhoCorasick) |
| instead of a DFA directly. Using an `DFA` directly is typically only necessary |
| when one needs access to the [`Automaton`] trait implementation. |
| */ |
| |
| use alloc::{vec, vec::Vec}; |
| |
| use crate::{ |
| automaton::Automaton, |
| nfa::noncontiguous, |
| util::{ |
| alphabet::ByteClasses, |
| error::{BuildError, MatchError}, |
| int::{Usize, U32}, |
| prefilter::Prefilter, |
| primitives::{IteratorIndexExt, PatternID, SmallIndex, StateID}, |
| search::{Anchored, MatchKind, StartKind}, |
| special::Special, |
| }, |
| }; |
| |
| /// A DFA implementation of Aho-Corasick. |
| /// |
| /// When possible, prefer using [`AhoCorasick`](crate::AhoCorasick) instead of |
| /// this type directly. Using a `DFA` directly is typically only necessary when |
| /// one needs access to the [`Automaton`] trait implementation. |
| /// |
| /// This DFA can only be built by first constructing a [`noncontiguous::NFA`]. |
| /// Both [`DFA::new`] and [`Builder::build`] do this for you automatically, but |
| /// [`Builder::build_from_noncontiguous`] permits doing it explicitly. |
| /// |
| /// A DFA provides the best possible search performance (in this crate) via two |
| /// mechanisms: |
| /// |
| /// * All states use a dense representation for their transitions. |
| /// * All failure transitions are pre-computed such that they are never |
| /// explicitly handled at search time. |
| /// |
| /// These two facts combined mean that every state transition is performed |
| /// using a constant number of instructions. However, this comes at |
| /// great cost. The memory usage of a DFA can be quite exorbitant. |
| /// It is potentially multiple orders of magnitude greater than a |
| /// [`contiguous::NFA`](crate::nfa::contiguous::NFA) for example. In exchange, |
| /// a DFA will typically have better search speed than a `contiguous::NFA`, but |
| /// not by orders of magnitude. |
| /// |
| /// Unless you have a small number of patterns or memory usage is not a concern |
| /// and search performance is critical, a DFA is usually not the best choice. |
| /// |
| /// Moreover, unlike the NFAs in this crate, it is costly for a DFA to |
| /// support for anchored and unanchored search configurations. Namely, |
| /// since failure transitions are pre-computed, supporting both anchored |
| /// and unanchored searches requires a duplication of the transition table, |
| /// making the memory usage of such a DFA ever bigger. (The NFAs in this crate |
| /// unconditionally support both anchored and unanchored searches because there |
| /// is essentially no added cost for doing so.) It is for this reason that |
| /// a DFA's support for anchored and unanchored searches can be configured |
| /// via [`Builder::start_kind`]. By default, a DFA only supports unanchored |
| /// searches. |
| /// |
| /// # Example |
| /// |
| /// This example shows how to build an `DFA` directly and use it to execute |
| /// [`Automaton::try_find`]: |
| /// |
| /// ``` |
| /// use aho_corasick::{ |
| /// automaton::Automaton, |
| /// dfa::DFA, |
| /// Input, Match, |
| /// }; |
| /// |
| /// let patterns = &["b", "abc", "abcd"]; |
| /// let haystack = "abcd"; |
| /// |
| /// let nfa = DFA::new(patterns).unwrap(); |
| /// assert_eq!( |
| /// Some(Match::must(0, 1..2)), |
| /// nfa.try_find(&Input::new(haystack))?, |
| /// ); |
| /// # Ok::<(), Box<dyn std::error::Error>>(()) |
| /// ``` |
| /// |
| /// It is also possible to implement your own version of `try_find`. See the |
| /// [`Automaton`] documentation for an example. |
| #[derive(Clone)] |
| pub struct DFA { |
| /// The DFA transition table. IDs in this table are pre-multiplied. So |
| /// instead of the IDs being 0, 1, 2, 3, ..., they are 0*stride, 1*stride, |
| /// 2*stride, 3*stride, ... |
| trans: Vec<StateID>, |
| /// The matches for every match state in this DFA. This is first indexed by |
| /// state index (so that's `sid >> stride2`) and then by order in which the |
| /// matches are meant to occur. |
| matches: Vec<Vec<PatternID>>, |
| /// The amount of heap memory used, in bytes, by the inner Vecs of |
| /// 'matches'. |
| matches_memory_usage: usize, |
| /// The length of each pattern. This is used to compute the start offset |
| /// of a match. |
| pattern_lens: Vec<SmallIndex>, |
| /// A prefilter for accelerating searches, if one exists. |
| prefilter: Option<Prefilter>, |
| /// The match semantics built into this DFA. |
| match_kind: MatchKind, |
| /// The total number of states in this DFA. |
| state_len: usize, |
| /// The alphabet size, or total number of equivalence classes, for this |
| /// DFA. Note that the actual number of transitions in each state is |
| /// stride=2^stride2, where stride is the smallest power of 2 greater than |
| /// or equal to alphabet_len. We do things this way so that we can use |
| /// bitshifting to go from a state ID to an index into 'matches'. |
| alphabet_len: usize, |
| /// The exponent with a base 2, such that stride=2^stride2. Given a state |
| /// index 'i', its state identifier is 'i << stride2'. Given a state |
| /// identifier 'sid', its state index is 'sid >> stride2'. |
| stride2: usize, |
| /// The equivalence classes for this DFA. All transitions are defined on |
| /// equivalence classes and not on the 256 distinct byte values. |
| byte_classes: ByteClasses, |
| /// The length of the shortest pattern in this automaton. |
| min_pattern_len: usize, |
| /// The length of the longest pattern in this automaton. |
| max_pattern_len: usize, |
| /// The information required to deduce which states are "special" in this |
| /// DFA. |
| special: Special, |
| } |
| |
| impl DFA { |
| /// Create a new Aho-Corasick DFA using the default configuration. |
| /// |
| /// Use a [`Builder`] if you want to change the configuration. |
| pub fn new<I, P>(patterns: I) -> Result<DFA, BuildError> |
| where |
| I: IntoIterator<Item = P>, |
| P: AsRef<[u8]>, |
| { |
| DFA::builder().build(patterns) |
| } |
| |
| /// A convenience method for returning a new Aho-Corasick DFA builder. |
| /// |
| /// This usually permits one to just import the `DFA` type. |
| pub fn builder() -> Builder { |
| Builder::new() |
| } |
| } |
| |
| impl DFA { |
| /// A sentinel state ID indicating that a search should stop once it has |
| /// entered this state. When a search stops, it returns a match if one has |
| /// been found, otherwise no match. A DFA always has an actual dead state |
| /// at this ID. |
| /// |
| /// N.B. DFAs, unlike NFAs, do not have any notion of a FAIL state. |
| /// Namely, the whole point of a DFA is that the FAIL state is completely |
| /// compiled away. That is, DFA construction involves pre-computing the |
| /// failure transitions everywhere, such that failure transitions are no |
| /// longer used at search time. This, combined with its uniformly dense |
| /// representation, are the two most important factors in why it's faster |
| /// than the NFAs in this crate. |
| const DEAD: StateID = StateID::new_unchecked(0); |
| |
| /// Adds the given pattern IDs as matches to the given state and also |
| /// records the added memory usage. |
| fn set_matches( |
| &mut self, |
| sid: StateID, |
| pids: impl Iterator<Item = PatternID>, |
| ) { |
| let index = (sid.as_usize() >> self.stride2).checked_sub(2).unwrap(); |
| let mut at_least_one = false; |
| for pid in pids { |
| self.matches[index].push(pid); |
| self.matches_memory_usage += PatternID::SIZE; |
| at_least_one = true; |
| } |
| assert!(at_least_one, "match state must have non-empty pids"); |
| } |
| } |
| |
| // SAFETY: 'start_state' always returns a valid state ID, 'next_state' always |
| // returns a valid state ID given a valid state ID. We otherwise claim that |
| // all other methods are correct as well. |
| unsafe impl Automaton for DFA { |
| #[inline(always)] |
| fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError> { |
| // Either of the start state IDs can be DEAD, in which case, support |
| // for that type of search is not provided by this DFA. Which start |
| // state IDs are inactive depends on the 'StartKind' configuration at |
| // DFA construction time. |
| match anchored { |
| Anchored::No => { |
| let start = self.special.start_unanchored_id; |
| if start == DFA::DEAD { |
| Err(MatchError::invalid_input_unanchored()) |
| } else { |
| Ok(start) |
| } |
| } |
| Anchored::Yes => { |
| let start = self.special.start_anchored_id; |
| if start == DFA::DEAD { |
| Err(MatchError::invalid_input_anchored()) |
| } else { |
| Ok(start) |
| } |
| } |
| } |
| } |
| |
| #[inline(always)] |
| fn next_state( |
| &self, |
| _anchored: Anchored, |
| sid: StateID, |
| byte: u8, |
| ) -> StateID { |
| let class = self.byte_classes.get(byte); |
| self.trans[(sid.as_u32() + u32::from(class)).as_usize()] |
| } |
| |
| #[inline(always)] |
| fn is_special(&self, sid: StateID) -> bool { |
| sid <= self.special.max_special_id |
| } |
| |
| #[inline(always)] |
| fn is_dead(&self, sid: StateID) -> bool { |
| sid == DFA::DEAD |
| } |
| |
| #[inline(always)] |
| fn is_match(&self, sid: StateID) -> bool { |
| !self.is_dead(sid) && sid <= self.special.max_match_id |
| } |
| |
| #[inline(always)] |
| fn is_start(&self, sid: StateID) -> bool { |
| sid == self.special.start_unanchored_id |
| || sid == self.special.start_anchored_id |
| } |
| |
| #[inline(always)] |
| fn match_kind(&self) -> MatchKind { |
| self.match_kind |
| } |
| |
| #[inline(always)] |
| fn patterns_len(&self) -> usize { |
| self.pattern_lens.len() |
| } |
| |
| #[inline(always)] |
| fn pattern_len(&self, pid: PatternID) -> usize { |
| self.pattern_lens[pid].as_usize() |
| } |
| |
| #[inline(always)] |
| fn min_pattern_len(&self) -> usize { |
| self.min_pattern_len |
| } |
| |
| #[inline(always)] |
| fn max_pattern_len(&self) -> usize { |
| self.max_pattern_len |
| } |
| |
| #[inline(always)] |
| fn match_len(&self, sid: StateID) -> usize { |
| debug_assert!(self.is_match(sid)); |
| let offset = (sid.as_usize() >> self.stride2) - 2; |
| self.matches[offset].len() |
| } |
| |
| #[inline(always)] |
| fn match_pattern(&self, sid: StateID, index: usize) -> PatternID { |
| debug_assert!(self.is_match(sid)); |
| let offset = (sid.as_usize() >> self.stride2) - 2; |
| self.matches[offset][index] |
| } |
| |
| #[inline(always)] |
| fn memory_usage(&self) -> usize { |
| use core::mem::size_of; |
| |
| (self.trans.len() * size_of::<u32>()) |
| + (self.matches.len() * size_of::<Vec<PatternID>>()) |
| + self.matches_memory_usage |
| + (self.pattern_lens.len() * size_of::<SmallIndex>()) |
| + self.prefilter.as_ref().map_or(0, |p| p.memory_usage()) |
| } |
| |
| #[inline(always)] |
| fn prefilter(&self) -> Option<&Prefilter> { |
| self.prefilter.as_ref() |
| } |
| } |
| |
| impl core::fmt::Debug for DFA { |
| fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| use crate::{ |
| automaton::{fmt_state_indicator, sparse_transitions}, |
| util::debug::DebugByte, |
| }; |
| |
| writeln!(f, "dfa::DFA(")?; |
| for index in 0..self.state_len { |
| let sid = StateID::new_unchecked(index << self.stride2); |
| // While we do currently include the FAIL state in the transition |
| // table (to simplify construction), it is never actually used. It |
| // poses problems with the code below because it gets treated as |
| // a match state incidentally when it is, of course, not. So we |
| // special case it. The fail state is always the first state after |
| // the dead state. |
| // |
| // If the construction is changed to remove the fail state (it |
| // probably should be), then this special case should be updated. |
| if index == 1 { |
| writeln!(f, "F {:06}:", sid.as_usize())?; |
| continue; |
| } |
| fmt_state_indicator(f, self, sid)?; |
| write!(f, "{:06}: ", sid.as_usize())?; |
| |
| let it = (0..self.byte_classes.alphabet_len()).map(|class| { |
| (class.as_u8(), self.trans[sid.as_usize() + class]) |
| }); |
| for (i, (start, end, next)) in sparse_transitions(it).enumerate() { |
| if i > 0 { |
| write!(f, ", ")?; |
| } |
| if start == end { |
| write!( |
| f, |
| "{:?} => {:?}", |
| DebugByte(start), |
| next.as_usize() |
| )?; |
| } else { |
| write!( |
| f, |
| "{:?}-{:?} => {:?}", |
| DebugByte(start), |
| DebugByte(end), |
| next.as_usize() |
| )?; |
| } |
| } |
| write!(f, "\n")?; |
| if self.is_match(sid) { |
| write!(f, " matches: ")?; |
| for i in 0..self.match_len(sid) { |
| if i > 0 { |
| write!(f, ", ")?; |
| } |
| let pid = self.match_pattern(sid, i); |
| write!(f, "{}", pid.as_usize())?; |
| } |
| write!(f, "\n")?; |
| } |
| } |
| writeln!(f, "match kind: {:?}", self.match_kind)?; |
| writeln!(f, "prefilter: {:?}", self.prefilter.is_some())?; |
| writeln!(f, "state length: {:?}", self.state_len)?; |
| writeln!(f, "pattern length: {:?}", self.patterns_len())?; |
| writeln!(f, "shortest pattern length: {:?}", self.min_pattern_len)?; |
| writeln!(f, "longest pattern length: {:?}", self.max_pattern_len)?; |
| writeln!(f, "alphabet length: {:?}", self.alphabet_len)?; |
| writeln!(f, "stride: {:?}", 1 << self.stride2)?; |
| writeln!(f, "byte classes: {:?}", self.byte_classes)?; |
| writeln!(f, "memory usage: {:?}", self.memory_usage())?; |
| writeln!(f, ")")?; |
| Ok(()) |
| } |
| } |
| |
| /// A builder for configuring an Aho-Corasick DFA. |
| /// |
| /// This builder has a subset of the options available to a |
| /// [`AhoCorasickBuilder`](crate::AhoCorasickBuilder). Of the shared options, |
| /// their behavior is identical. |
| #[derive(Clone, Debug)] |
| pub struct Builder { |
| noncontiguous: noncontiguous::Builder, |
| start_kind: StartKind, |
| byte_classes: bool, |
| } |
| |
| impl Default for Builder { |
| fn default() -> Builder { |
| Builder { |
| noncontiguous: noncontiguous::Builder::new(), |
| start_kind: StartKind::Unanchored, |
| byte_classes: true, |
| } |
| } |
| } |
| |
| impl Builder { |
| /// Create a new builder for configuring an Aho-Corasick DFA. |
| pub fn new() -> Builder { |
| Builder::default() |
| } |
| |
| /// Build an Aho-Corasick DFA from the given iterator of patterns. |
| /// |
| /// A builder may be reused to create more DFAs. |
| pub fn build<I, P>(&self, patterns: I) -> Result<DFA, BuildError> |
| where |
| I: IntoIterator<Item = P>, |
| P: AsRef<[u8]>, |
| { |
| let nnfa = self.noncontiguous.build(patterns)?; |
| self.build_from_noncontiguous(&nnfa) |
| } |
| |
| /// Build an Aho-Corasick DFA from the given noncontiguous NFA. |
| /// |
| /// Note that when this method is used, only the `start_kind` and |
| /// `byte_classes` settings on this builder are respected. The other |
| /// settings only apply to the initial construction of the Aho-Corasick |
| /// automaton. Since using this method requires that initial construction |
| /// has already completed, all settings impacting only initial construction |
| /// are no longer relevant. |
| pub fn build_from_noncontiguous( |
| &self, |
| nnfa: &noncontiguous::NFA, |
| ) -> Result<DFA, BuildError> { |
| debug!("building DFA"); |
| let byte_classes = if self.byte_classes { |
| nnfa.byte_classes().clone() |
| } else { |
| ByteClasses::singletons() |
| }; |
| let state_len = match self.start_kind { |
| StartKind::Unanchored | StartKind::Anchored => nnfa.states().len(), |
| StartKind::Both => { |
| // These unwraps are OK because we know that the number of |
| // NFA states is < StateID::LIMIT which is in turn less than |
| // i32::MAX. Thus, there is always room to multiply by 2. |
| // Finally, the number of states is always at least 4 in the |
| // NFA (DEAD, FAIL, START-UNANCHORED, START-ANCHORED), so the |
| // subtraction of 4 is okay. |
| // |
| // Note that we subtract 4 because the "anchored" part of |
| // the DFA duplicates the unanchored part (without failure |
| // transitions), but reuses the DEAD, FAIL and START states. |
| nnfa.states() |
| .len() |
| .checked_mul(2) |
| .unwrap() |
| .checked_sub(4) |
| .unwrap() |
| } |
| }; |
| let trans_len = |
| match state_len.checked_shl(byte_classes.stride2().as_u32()) { |
| Some(trans_len) => trans_len, |
| None => { |
| return Err(BuildError::state_id_overflow( |
| StateID::MAX.as_u64(), |
| usize::MAX.as_u64(), |
| )) |
| } |
| }; |
| StateID::new(trans_len.checked_sub(byte_classes.stride()).unwrap()) |
| .map_err(|e| { |
| BuildError::state_id_overflow( |
| StateID::MAX.as_u64(), |
| e.attempted(), |
| ) |
| })?; |
| let num_match_states = match self.start_kind { |
| StartKind::Unanchored | StartKind::Anchored => { |
| nnfa.special().max_match_id.as_usize().checked_sub(1).unwrap() |
| } |
| StartKind::Both => nnfa |
| .special() |
| .max_match_id |
| .as_usize() |
| .checked_sub(1) |
| .unwrap() |
| .checked_mul(2) |
| .unwrap(), |
| }; |
| let mut dfa = DFA { |
| trans: vec![DFA::DEAD; trans_len], |
| matches: vec![vec![]; num_match_states], |
| matches_memory_usage: 0, |
| pattern_lens: nnfa.pattern_lens_raw().to_vec(), |
| prefilter: nnfa.prefilter().map(|p| p.clone()), |
| match_kind: nnfa.match_kind(), |
| state_len, |
| alphabet_len: byte_classes.alphabet_len(), |
| stride2: byte_classes.stride2(), |
| byte_classes, |
| min_pattern_len: nnfa.min_pattern_len(), |
| max_pattern_len: nnfa.max_pattern_len(), |
| // The special state IDs are set later. |
| special: Special::zero(), |
| }; |
| match self.start_kind { |
| StartKind::Both => { |
| self.finish_build_both_starts(nnfa, &mut dfa); |
| } |
| StartKind::Unanchored => { |
| self.finish_build_one_start(Anchored::No, nnfa, &mut dfa); |
| } |
| StartKind::Anchored => { |
| self.finish_build_one_start(Anchored::Yes, nnfa, &mut dfa) |
| } |
| } |
| debug!( |
| "DFA built, <states: {:?}, size: {:?}, \ |
| alphabet len: {:?}, stride: {:?}>", |
| dfa.state_len, |
| dfa.memory_usage(), |
| dfa.byte_classes.alphabet_len(), |
| dfa.byte_classes.stride(), |
| ); |
| // The vectors can grow ~twice as big during construction because a |
| // Vec amortizes growth. But here, let's shrink things back down to |
| // what we actually need since we're never going to add more to it. |
| dfa.trans.shrink_to_fit(); |
| dfa.pattern_lens.shrink_to_fit(); |
| dfa.matches.shrink_to_fit(); |
| // TODO: We might also want to shrink each Vec inside of `dfa.matches`, |
| // or even better, convert it to one contiguous allocation. But I think |
| // I went with nested allocs for good reason (can't remember), so this |
| // may be tricky to do. I decided not to shrink them here because it |
| // might require a fair bit of work to do. It's unclear whether it's |
| // worth it. |
| Ok(dfa) |
| } |
| |
| /// Finishes building a DFA for either unanchored or anchored searches, |
| /// but NOT both. |
| fn finish_build_one_start( |
| &self, |
| anchored: Anchored, |
| nnfa: &noncontiguous::NFA, |
| dfa: &mut DFA, |
| ) { |
| // This function always succeeds because we check above that all of the |
| // states in the NFA can be mapped to DFA state IDs. |
| let stride2 = dfa.stride2; |
| let old2new = |oldsid: StateID| { |
| StateID::new_unchecked(oldsid.as_usize() << stride2) |
| }; |
| for (oldsid, state) in nnfa.states().iter().with_state_ids() { |
| let newsid = old2new(oldsid); |
| if state.is_match() { |
| dfa.set_matches(newsid, nnfa.iter_matches(oldsid)); |
| } |
| sparse_iter( |
| nnfa, |
| oldsid, |
| &dfa.byte_classes, |
| |byte, class, mut oldnextsid| { |
| if oldnextsid == noncontiguous::NFA::FAIL { |
| if anchored.is_anchored() { |
| oldnextsid = noncontiguous::NFA::DEAD; |
| } else { |
| oldnextsid = nnfa.next_state( |
| Anchored::No, |
| state.fail(), |
| byte, |
| ); |
| } |
| } |
| dfa.trans[newsid.as_usize() + usize::from(class)] = |
| old2new(oldnextsid); |
| }, |
| ); |
| } |
| // Now that we've remapped all the IDs in our states, all that's left |
| // is remapping the special state IDs. |
| let old = nnfa.special(); |
| let new = &mut dfa.special; |
| new.max_special_id = old2new(old.max_special_id); |
| new.max_match_id = old2new(old.max_match_id); |
| if anchored.is_anchored() { |
| new.start_unanchored_id = DFA::DEAD; |
| new.start_anchored_id = old2new(old.start_anchored_id); |
| } else { |
| new.start_unanchored_id = old2new(old.start_unanchored_id); |
| new.start_anchored_id = DFA::DEAD; |
| } |
| } |
| |
| /// Finishes building a DFA that supports BOTH unanchored and anchored |
| /// searches. It works by inter-leaving unanchored states with anchored |
| /// states in the same transition table. This way, we avoid needing to |
| /// re-shuffle states afterward to ensure that our states still look like |
| /// DEAD, MATCH, ..., START-UNANCHORED, START-ANCHORED, NON-MATCH, ... |
| /// |
| /// Honestly this is pretty inscrutable... Simplifications are most |
| /// welcome. |
| fn finish_build_both_starts( |
| &self, |
| nnfa: &noncontiguous::NFA, |
| dfa: &mut DFA, |
| ) { |
| let stride2 = dfa.stride2; |
| let stride = 1 << stride2; |
| let mut remap_unanchored = vec![DFA::DEAD; nnfa.states().len()]; |
| let mut remap_anchored = vec![DFA::DEAD; nnfa.states().len()]; |
| let mut is_anchored = vec![false; dfa.state_len]; |
| let mut newsid = DFA::DEAD; |
| let next_dfa_id = |
| |sid: StateID| StateID::new_unchecked(sid.as_usize() + stride); |
| for (oldsid, state) in nnfa.states().iter().with_state_ids() { |
| if oldsid == noncontiguous::NFA::DEAD |
| || oldsid == noncontiguous::NFA::FAIL |
| { |
| remap_unanchored[oldsid] = newsid; |
| remap_anchored[oldsid] = newsid; |
| newsid = next_dfa_id(newsid); |
| } else if oldsid == nnfa.special().start_unanchored_id |
| || oldsid == nnfa.special().start_anchored_id |
| { |
| if oldsid == nnfa.special().start_unanchored_id { |
| remap_unanchored[oldsid] = newsid; |
| remap_anchored[oldsid] = DFA::DEAD; |
| } else { |
| remap_unanchored[oldsid] = DFA::DEAD; |
| remap_anchored[oldsid] = newsid; |
| is_anchored[newsid.as_usize() >> stride2] = true; |
| } |
| if state.is_match() { |
| dfa.set_matches(newsid, nnfa.iter_matches(oldsid)); |
| } |
| sparse_iter( |
| nnfa, |
| oldsid, |
| &dfa.byte_classes, |
| |_, class, oldnextsid| { |
| let class = usize::from(class); |
| if oldnextsid == noncontiguous::NFA::FAIL { |
| dfa.trans[newsid.as_usize() + class] = DFA::DEAD; |
| } else { |
| dfa.trans[newsid.as_usize() + class] = oldnextsid; |
| } |
| }, |
| ); |
| newsid = next_dfa_id(newsid); |
| } else { |
| let unewsid = newsid; |
| newsid = next_dfa_id(newsid); |
| let anewsid = newsid; |
| newsid = next_dfa_id(newsid); |
| |
| remap_unanchored[oldsid] = unewsid; |
| remap_anchored[oldsid] = anewsid; |
| is_anchored[anewsid.as_usize() >> stride2] = true; |
| if state.is_match() { |
| dfa.set_matches(unewsid, nnfa.iter_matches(oldsid)); |
| dfa.set_matches(anewsid, nnfa.iter_matches(oldsid)); |
| } |
| sparse_iter( |
| nnfa, |
| oldsid, |
| &dfa.byte_classes, |
| |byte, class, oldnextsid| { |
| let class = usize::from(class); |
| if oldnextsid == noncontiguous::NFA::FAIL { |
| dfa.trans[unewsid.as_usize() + class] = nnfa |
| .next_state(Anchored::No, state.fail(), byte); |
| } else { |
| dfa.trans[unewsid.as_usize() + class] = oldnextsid; |
| dfa.trans[anewsid.as_usize() + class] = oldnextsid; |
| } |
| }, |
| ); |
| } |
| } |
| for i in 0..dfa.state_len { |
| let sid = i << stride2; |
| if is_anchored[i] { |
| for next in dfa.trans[sid..][..stride].iter_mut() { |
| *next = remap_anchored[*next]; |
| } |
| } else { |
| for next in dfa.trans[sid..][..stride].iter_mut() { |
| *next = remap_unanchored[*next]; |
| } |
| } |
| } |
| // Now that we've remapped all the IDs in our states, all that's left |
| // is remapping the special state IDs. |
| let old = nnfa.special(); |
| let new = &mut dfa.special; |
| new.max_special_id = remap_anchored[old.max_special_id]; |
| new.max_match_id = remap_anchored[old.max_match_id]; |
| new.start_unanchored_id = remap_unanchored[old.start_unanchored_id]; |
| new.start_anchored_id = remap_anchored[old.start_anchored_id]; |
| } |
| |
| /// Set the desired match semantics. |
| /// |
| /// This only applies when using [`Builder::build`] and not |
| /// [`Builder::build_from_noncontiguous`]. |
| /// |
| /// See |
| /// [`AhoCorasickBuilder::match_kind`](crate::AhoCorasickBuilder::match_kind) |
| /// for more documentation and examples. |
| pub fn match_kind(&mut self, kind: MatchKind) -> &mut Builder { |
| self.noncontiguous.match_kind(kind); |
| self |
| } |
| |
| /// Enable ASCII-aware case insensitive matching. |
| /// |
| /// This only applies when using [`Builder::build`] and not |
| /// [`Builder::build_from_noncontiguous`]. |
| /// |
| /// See |
| /// [`AhoCorasickBuilder::ascii_case_insensitive`](crate::AhoCorasickBuilder::ascii_case_insensitive) |
| /// for more documentation and examples. |
| pub fn ascii_case_insensitive(&mut self, yes: bool) -> &mut Builder { |
| self.noncontiguous.ascii_case_insensitive(yes); |
| self |
| } |
| |
| /// Enable heuristic prefilter optimizations. |
| /// |
| /// This only applies when using [`Builder::build`] and not |
| /// [`Builder::build_from_noncontiguous`]. |
| /// |
| /// See |
| /// [`AhoCorasickBuilder::prefilter`](crate::AhoCorasickBuilder::prefilter) |
| /// for more documentation and examples. |
| pub fn prefilter(&mut self, yes: bool) -> &mut Builder { |
| self.noncontiguous.prefilter(yes); |
| self |
| } |
| |
| /// Sets the starting state configuration for the automaton. |
| /// |
| /// See |
| /// [`AhoCorasickBuilder::start_kind`](crate::AhoCorasickBuilder::start_kind) |
| /// for more documentation and examples. |
| pub fn start_kind(&mut self, kind: StartKind) -> &mut Builder { |
| self.start_kind = kind; |
| self |
| } |
| |
| /// A debug setting for whether to attempt to shrink the size of the |
| /// automaton's alphabet or not. |
| /// |
| /// This should never be enabled unless you're debugging an automaton. |
| /// Namely, disabling byte classes makes transitions easier to reason |
| /// about, since they use the actual bytes instead of equivalence classes. |
| /// Disabling this confers no performance benefit at search time. |
| /// |
| /// See |
| /// [`AhoCorasickBuilder::byte_classes`](crate::AhoCorasickBuilder::byte_classes) |
| /// for more documentation and examples. |
| pub fn byte_classes(&mut self, yes: bool) -> &mut Builder { |
| self.byte_classes = yes; |
| self |
| } |
| } |
| |
| /// Iterate over all possible equivalence class transitions in this state. |
| /// The closure is called for all transitions with a distinct equivalence |
| /// class, even those not explicitly represented in this sparse state. For |
| /// any implicitly defined transitions, the given closure is called with |
| /// the fail state ID. |
| /// |
| /// The closure is guaranteed to be called precisely |
| /// `byte_classes.alphabet_len()` times, once for every possible class in |
| /// ascending order. |
| fn sparse_iter<F: FnMut(u8, u8, StateID)>( |
| nnfa: &noncontiguous::NFA, |
| oldsid: StateID, |
| classes: &ByteClasses, |
| mut f: F, |
| ) { |
| let mut prev_class = None; |
| let mut byte = 0usize; |
| for t in nnfa.iter_trans(oldsid) { |
| while byte < usize::from(t.byte()) { |
| let rep = byte.as_u8(); |
| let class = classes.get(rep); |
| byte += 1; |
| if prev_class != Some(class) { |
| f(rep, class, noncontiguous::NFA::FAIL); |
| prev_class = Some(class); |
| } |
| } |
| let rep = t.byte(); |
| let class = classes.get(rep); |
| byte += 1; |
| if prev_class != Some(class) { |
| f(rep, class, t.next()); |
| prev_class = Some(class); |
| } |
| } |
| for b in byte..=255 { |
| let rep = b.as_u8(); |
| let class = classes.get(rep); |
| if prev_class != Some(class) { |
| f(rep, class, noncontiguous::NFA::FAIL); |
| prev_class = Some(class); |
| } |
| } |
| } |
