Struct `NFA`

struct NFA { ... }

A noncontiguous NFA implementation of Aho-Corasick.

When possible, prefer using AhoCorasick instead of this type directly. Using an NFA directly is typically only necessary when one needs access to the Automaton trait implementation.

This NFA represents the "core" implementation of Aho-Corasick in this crate. Namely, constructing this NFA involving building a trie and then filling in the failure transitions between states, similar to what is described in any standard textbook description of Aho-Corasick.

In order to minimize heap usage and to avoid additional construction costs, this implementation represents the transitions of all states as distinct sparse memory allocations. This is where it gets its name from. That is, this NFA has no contiguous memory allocation for its transition table. Each state gets its own allocation.

While the sparse representation keeps memory usage to somewhat reasonable levels, it is still quite large and also results in somewhat mediocre search performance. For this reason, it is almost always a good idea to use a contiguous::NFA instead. It is marginally slower to build, but has higher throughput and can sometimes use an order of magnitude less memory. The main reason to use a noncontiguous NFA is when you need the fastest possible construction time, or when a contiguous NFA does not have the desired capacity. (The total number of NFA states it can have is fewer than a noncontiguous NFA.)

Example

This example shows how to build an NFA directly and use it to execute [Automaton::try_find]:

use aho_corasick::{
    automaton::Automaton,
    nfa::noncontiguous::NFA,
    Input, Match,
};

let patterns = &["b", "abc", "abcd"];
let haystack = "abcd";

let nfa = NFA::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 NFA`

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

Create a new Aho-Corasick noncontiguous NFA 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 noncontiguous NFA builder.

This usually permits one to just import the NFA type.

`impl Automaton for NFA`

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 NFA`

fn clone(self: &Self) -> NFA

`impl Debug for NFA`

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

`impl Freeze for NFA`

`impl RefUnwindSafe for NFA`

`impl Send for NFA`

`impl Sync for NFA`

`impl Unpin for NFA`

`impl UnsafeUnpin for NFA`

`impl UnwindSafe for NFA`

`impl<T> Any for NFA`

fn type_id(self: &Self) -> TypeId

`impl<T> Borrow for NFA`

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

`impl<T> BorrowMut for NFA`

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

`impl<T> CloneToUninit for NFA`

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

`impl<T> From for NFA`

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

`impl<T> ToOwned for NFA`

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

`impl<T, U> Into for NFA`

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 NFA`

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

`impl<T, U> TryInto for NFA`

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