Struct aho_corasick::dfa::DFA
source · pub struct DFA { /* private fields */ }
Expand description
A DFA implementation of Aho-Corasick.
When possible, prefer using 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
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))?,
);
It is also possible to implement your own version of try_find
. See the
Automaton
documentation for an example.
Implementations§
Trait Implementations§
source§impl Automaton for DFA
impl Automaton for DFA
source§fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError>
fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError>
source§fn is_special(&self, sid: StateID) -> bool
fn is_special(&self, sid: StateID) -> bool
source§fn is_dead(&self, sid: StateID) -> bool
fn is_dead(&self, sid: StateID) -> bool
source§fn is_match(&self, sid: StateID) -> bool
fn is_match(&self, sid: StateID) -> bool
source§fn is_start(&self, sid: StateID) -> bool
fn is_start(&self, sid: StateID) -> bool
source§fn match_kind(&self) -> MatchKind
fn match_kind(&self) -> MatchKind
source§fn patterns_len(&self) -> usize
fn patterns_len(&self) -> usize
source§fn pattern_len(&self, pid: PatternID) -> usize
fn pattern_len(&self, pid: PatternID) -> usize
source§fn min_pattern_len(&self) -> usize
fn min_pattern_len(&self) -> usize
source§fn max_pattern_len(&self) -> usize
fn max_pattern_len(&self) -> usize
source§fn match_len(&self, sid: StateID) -> usize
fn match_len(&self, sid: StateID) -> usize
source§fn memory_usage(&self) -> usize
fn memory_usage(&self) -> usize
source§fn prefilter(&self) -> Option<&Prefilter>
fn prefilter(&self) -> Option<&Prefilter>
source§fn try_find(&self, input: &Input<'_>) -> Result<Option<Match>, MatchError>
fn try_find(&self, input: &Input<'_>) -> Result<Option<Match>, MatchError>
source§fn try_find_overlapping(
&self,
input: &Input<'_>,
state: &mut OverlappingState,
) -> Result<(), MatchError>
fn try_find_overlapping( &self, input: &Input<'_>, state: &mut OverlappingState, ) -> Result<(), MatchError>
source§fn try_find_iter<'a, 'h>(
&'a self,
input: Input<'h>,
) -> Result<FindIter<'a, 'h, Self>, MatchError>where
Self: Sized,
fn try_find_iter<'a, 'h>(
&'a self,
input: Input<'h>,
) -> Result<FindIter<'a, 'h, Self>, MatchError>where
Self: Sized,
source§fn try_find_overlapping_iter<'a, 'h>(
&'a self,
input: Input<'h>,
) -> Result<FindOverlappingIter<'a, 'h, Self>, MatchError>where
Self: Sized,
fn try_find_overlapping_iter<'a, 'h>(
&'a self,
input: Input<'h>,
) -> Result<FindOverlappingIter<'a, 'h, Self>, MatchError>where
Self: Sized,
source§fn try_replace_all<B>(
&self,
haystack: &str,
replace_with: &[B],
) -> Result<String, MatchError>
fn try_replace_all<B>( &self, haystack: &str, replace_with: &[B], ) -> Result<String, MatchError>
haystack
with
strings from replace_with
depending on the pattern that
matched. The replace_with
slice must have length equal to
Automaton::patterns_len
. Read moresource§fn try_replace_all_bytes<B>(
&self,
haystack: &[u8],
replace_with: &[B],
) -> Result<Vec<u8>, MatchError>
fn try_replace_all_bytes<B>( &self, haystack: &[u8], replace_with: &[B], ) -> Result<Vec<u8>, MatchError>
haystack
with
strings from replace_with
depending on the pattern that
matched. The replace_with
slice must have length equal to
Automaton::patterns_len
. Read moresource§fn try_replace_all_with<F>(
&self,
haystack: &str,
dst: &mut String,
replace_with: F,
) -> Result<(), MatchError>
fn try_replace_all_with<F>( &self, haystack: &str, dst: &mut String, replace_with: F, ) -> Result<(), MatchError>
haystack
by calling the
replace_with
closure given. Read moresource§fn try_replace_all_with_bytes<F>(
&self,
haystack: &[u8],
dst: &mut Vec<u8>,
replace_with: F,
) -> Result<(), MatchError>
fn try_replace_all_with_bytes<F>( &self, haystack: &[u8], dst: &mut Vec<u8>, replace_with: F, ) -> Result<(), MatchError>
haystack
by calling the
replace_with
closure given. Read moresource§fn try_stream_find_iter<'a, R: Read>(
&'a self,
rdr: R,
) -> Result<StreamFindIter<'a, Self, R>, MatchError>where
Self: Sized,
fn try_stream_find_iter<'a, R: Read>(
&'a self,
rdr: R,
) -> Result<StreamFindIter<'a, Self, R>, MatchError>where
Self: Sized,
source§fn try_stream_replace_all<R, W, B>(
&self,
rdr: R,
wtr: W,
replace_with: &[B],
) -> Result<()>
fn try_stream_replace_all<R, W, B>( &self, rdr: R, wtr: W, replace_with: &[B], ) -> Result<()>
rdr
with strings from
replace_with
depending on the pattern that matched, and writes the
result to wtr
. The replace_with
slice must have length equal to
Automaton::patterns_len
. Read moreAuto Trait Implementations§
impl Freeze for DFA
impl RefUnwindSafe for DFA
impl Send for DFA
impl Sync for DFA
impl Unpin for DFA
impl UnwindSafe for DFA
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)