Struct `NFA`

struct NFA { ... }

A contiguous 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 can only be built by first constructing a noncontiguous::NFA. Both NFA::new and Builder::build do this for you automatically, but Builder::build_from_noncontiguous permits doing it explicitly.

The main difference between a noncontiguous NFA and a contiguous NFA is that the latter represents all of its states and transitions in a single allocation, where as the former uses a separate allocation for each state. Doing this at construction time while keeping a low memory footprint isn't feasible, which is primarily why there are two different NFA types: one that does the least amount of work possible to build itself, and another that does a little extra work to compact itself and make state transitions faster by making some states use a dense representation.

Because a contiguous NFA uses a single allocation, there is a lot more opportunity for compression tricks to reduce the heap memory used. Indeed, it is not uncommon for a contiguous NFA to use an order of magnitude less heap memory than a noncontiguous NFA. Since building a contiguous NFA usually only takes a fraction of the time it takes to build a noncontiguous NFA, the overall build time is not much slower. Thus, in most cases, a contiguous NFA is the best choice.

Since a contiguous NFA uses various tricks for compression and to achieve faster state transitions, currently, its limit on the number of states is somewhat smaller than what a noncontiguous NFA can achieve. Generally speaking, you shouldn't expect to run into this limit if the number of patterns is under 1 million. It is plausible that this limit will be increased in the future. If the limit is reached, building a contiguous NFA will return an error. Often, since building a contiguous NFA is relatively cheap, it can make sense to always try it even if you aren't sure if it will fail or not. If it does, you can always fall back to a noncontiguous NFA. (Indeed, the main AhoCorasick type employs a strategy similar to this at construction time.)

Example

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

use aho_corasick::{
    automaton::Automaton,
    nfa::contiguous::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 contiguous 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 contiguous 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>