Struct `DFA`

struct DFA { ... }

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))?,
);
# 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.

Implementations

`impl DFA`

fn new<I, P>(patterns: I) -> Result<DFA, BuildError> where I: IntoIterator<Item = P>, P: AsRef<[u8]>

Create a new Aho-Corasick DFA using the default configuration.

Use a Builder if you want to change the configuration.

fn builder() -> Builder

A convenience method for returning a new Aho-Corasick DFA builder.

This usually permits one to just import the DFA type.

`impl Automaton for DFA`

fn start_state(self: &Self, anchored: Anchored) -> Result<StateID, MatchError>
fn next_state(self: &Self, _anchored: Anchored, sid: StateID, byte: u8) -> StateID
fn is_special(self: &Self, sid: StateID) -> bool
fn is_dead(self: &Self, sid: StateID) -> bool
fn is_match(self: &Self, sid: StateID) -> bool
fn is_start(self: &Self, sid: StateID) -> bool
fn match_kind(self: &Self) -> MatchKind
fn patterns_len(self: &Self) -> usize
fn pattern_len(self: &Self, pid: PatternID) -> usize
fn min_pattern_len(self: &Self) -> usize
fn max_pattern_len(self: &Self) -> usize
fn match_len(self: &Self, sid: StateID) -> usize
fn match_pattern(self: &Self, sid: StateID, index: usize) -> PatternID
fn memory_usage(self: &Self) -> usize
fn prefilter(self: &Self) -> Option<&Prefilter>

`impl Clone for DFA`

fn clone(self: &Self) -> DFA

`impl Debug for DFA`

fn fmt(self: &Self, f: &mut Formatter<'_>) -> Result

`impl Freeze for DFA`

`impl RefUnwindSafe for DFA`

`impl Send for DFA`

`impl Sync for DFA`

`impl Unpin for DFA`

`impl UnsafeUnpin for DFA`

`impl UnwindSafe for DFA`

`impl<T> Any for DFA`

fn type_id(self: &Self) -> TypeId

`impl<T> Borrow for DFA`

fn borrow(self: &Self) -> &T

`impl<T> BorrowMut for DFA`

fn borrow_mut(self: &mut Self) -> &mut T

`impl<T> CloneToUninit for DFA`

unsafe fn clone_to_uninit(self: &Self, dest: *mut u8)

`impl<T> From for DFA`

fn from(t: T) -> T: Returns the argument unchanged.

`impl<T> ToOwned for DFA`

fn to_owned(self: &Self) -> T
fn clone_into(self: &Self, target: &mut T)

`impl<T, U> Into for DFA`

fn into(self: Self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of [From]<T> for U chooses to do.

`impl<T, U> TryFrom for DFA`

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

`impl<T, U> TryInto for DFA`

fn try_into(self: Self) -> Result<U, <U as TryFrom<T>>::Error>