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
sourceimpl Automaton for DFA
impl Automaton for DFA
sourcefn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError>
fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError>
sourcefn is_special(&self, sid: StateID) -> bool
fn is_special(&self, sid: StateID) -> bool
sourcefn is_dead(&self, sid: StateID) -> bool
fn is_dead(&self, sid: StateID) -> bool
sourcefn is_match(&self, sid: StateID) -> bool
fn is_match(&self, sid: StateID) -> bool
sourcefn is_start(&self, sid: StateID) -> bool
fn is_start(&self, sid: StateID) -> bool
sourcefn match_kind(&self) -> MatchKind
fn match_kind(&self) -> MatchKind
sourcefn patterns_len(&self) -> usize
fn patterns_len(&self) -> usize
sourcefn pattern_len(&self, pid: PatternID) -> usize
fn pattern_len(&self, pid: PatternID) -> usize
sourcefn min_pattern_len(&self) -> usize
fn min_pattern_len(&self) -> usize
sourcefn max_pattern_len(&self) -> usize
fn max_pattern_len(&self) -> usize
sourcefn match_len(&self, sid: StateID) -> usize
fn match_len(&self, sid: StateID) -> usize
sourcefn match_pattern(&self, sid: StateID, index: usize) -> PatternID
fn match_pattern(&self, sid: StateID, index: usize) -> PatternID
sourcefn memory_usage(&self) -> usize
fn memory_usage(&self) -> usize
sourcefn prefilter(&self) -> Option<&Prefilter>
fn prefilter(&self) -> Option<&Prefilter>
sourcefn try_find(&self, input: &Input<'_>) -> Result<Option<Match>, MatchError>
fn try_find(&self, input: &Input<'_>) -> Result<Option<Match>, MatchError>
sourcefn try_find_overlapping(
&self,
input: &Input<'_>,
state: &mut OverlappingState
) -> Result<(), MatchError>
fn try_find_overlapping(
&self,
input: &Input<'_>,
state: &mut OverlappingState
) -> Result<(), MatchError>
sourcefn 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,
sourcefn 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,
sourcefn try_replace_all<B>(
&self,
haystack: &str,
replace_with: &[B]
) -> Result<String, MatchError>where
Self: Sized,
B: AsRef<str>,
fn try_replace_all<B>(
&self,
haystack: &str,
replace_with: &[B]
) -> Result<String, MatchError>where
Self: Sized,
B: AsRef<str>,
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 moresourcefn try_replace_all_bytes<B>(
&self,
haystack: &[u8],
replace_with: &[B]
) -> Result<Vec<u8>, MatchError>where
Self: Sized,
B: AsRef<[u8]>,
fn try_replace_all_bytes<B>(
&self,
haystack: &[u8],
replace_with: &[B]
) -> Result<Vec<u8>, MatchError>where
Self: Sized,
B: AsRef<[u8]>,
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 moresourcefn try_replace_all_with<F>(
&self,
haystack: &str,
dst: &mut String,
replace_with: F
) -> Result<(), MatchError>where
Self: Sized,
F: FnMut(&Match, &str, &mut String) -> bool,
fn try_replace_all_with<F>(
&self,
haystack: &str,
dst: &mut String,
replace_with: F
) -> Result<(), MatchError>where
Self: Sized,
F: FnMut(&Match, &str, &mut String) -> bool,
haystack
by calling the
replace_with
closure given. Read moresourcefn try_replace_all_with_bytes<F>(
&self,
haystack: &[u8],
dst: &mut Vec<u8>,
replace_with: F
) -> Result<(), MatchError>where
Self: Sized,
F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool,
fn try_replace_all_with_bytes<F>(
&self,
haystack: &[u8],
dst: &mut Vec<u8>,
replace_with: F
) -> Result<(), MatchError>where
Self: Sized,
F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool,
haystack
by calling the
replace_with
closure given. Read moresourcefn 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,
sourcefn try_stream_replace_all<R, W, B>(
&self,
rdr: R,
wtr: W,
replace_with: &[B]
) -> Result<()>where
Self: Sized,
R: Read,
W: Write,
B: AsRef<[u8]>,
fn try_stream_replace_all<R, W, B>(
&self,
rdr: R,
wtr: W,
replace_with: &[B]
) -> Result<()>where
Self: Sized,
R: Read,
W: Write,
B: AsRef<[u8]>,
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 moresourcefn try_stream_replace_all_with<R, W, F>(
&self,
rdr: R,
wtr: W,
replace_with: F
) -> Result<()>where
Self: Sized,
R: Read,
W: Write,
F: FnMut(&Match, &[u8], &mut W) -> Result<()>,
fn try_stream_replace_all_with<R, W, F>(
&self,
rdr: R,
wtr: W,
replace_with: F
) -> Result<()>where
Self: Sized,
R: Read,
W: Write,
F: FnMut(&Match, &[u8], &mut W) -> Result<()>,
rdr
by calling the
replace_with
closure given and writing the result to wtr
. Read more