Struct aho_corasick::nfa::noncontiguous::NFA

pub struct NFA { /* private fields */ }

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

It is also possible to implement your own version of try_find. See the Automaton documentation for an example.

Implementations

impl NFA

pub 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.

pub 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.

Trait Implementations

impl Automaton for NFA

fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError>

Returns the starting state for the given anchor mode.

fn next_state(&self, anchored: Anchored, sid: StateID, byte: u8) -> StateID

Performs a state transition from sid for byte and returns the next state.

fn is_special(&self, sid: StateID) -> bool

Returns true if the given ID represents a “special” state. A special state is a dead, match or start state.

fn is_dead(&self, sid: StateID) -> bool

Returns true if the given ID represents a dead state.

fn is_match(&self, sid: StateID) -> bool

Returns true if the given ID represents a match state.

fn is_start(&self, sid: StateID) -> bool

Returns true if the given ID represents a start state.

fn match_kind(&self) -> MatchKind

Returns the match semantics that this automaton was built with.

fn patterns_len(&self) -> usize

Returns the total number of patterns compiled into this automaton.

fn pattern_len(&self, pid: PatternID) -> usize

Returns the length of the pattern for the given ID.

fn min_pattern_len(&self) -> usize

Returns the length, in bytes, of the shortest pattern in this automaton.

fn max_pattern_len(&self) -> usize

Returns the length, in bytes, of the longest pattern in this automaton.

fn match_len(&self, sid: StateID) -> usize

Returns the total number of matches for the given state ID.

fn match_pattern(&self, sid: StateID, index: usize) -> PatternID

Returns the pattern ID for the match state given by sid at the index given.

fn memory_usage(&self) -> usize

Returns the heap memory usage, in bytes, used by this automaton.

fn prefilter(&self) -> Option<&Prefilter>

Returns a prefilter, if available, that can be used to accelerate searches for this automaton.

fn try_find(&self, input: &Input<'_>) -> Result<Option<Match>, MatchError>

Executes a non-overlapping search with this automaton using the given configuration.

fn try_find_overlapping(
    &self,
    input: &Input<'_>,
    state: &mut OverlappingState
) -> Result<(), MatchError>

Executes a overlapping search with this automaton using the given configuration.

fn try_find_iter<'a, 'h>(
    &'a self,
    input: Input<'h>
) -> Result<FindIter<'a, 'h, Self>, MatchError>where
    Self: Sized,

Returns an iterator of non-overlapping matches with this automaton using the given configuration.

fn try_find_overlapping_iter<'a, 'h>(
    &'a self,
    input: Input<'h>
) -> Result<FindOverlappingIter<'a, 'h, Self>, MatchError>where
    Self: Sized,

Returns an iterator of overlapping matches with this automaton using the given configuration.

fn try_replace_all<B>(
    &self,
    haystack: &str,
    replace_with: &[B]
) -> Result<String, MatchError>where
    Self: Sized,
    B: AsRef<str>,

Replaces all non-overlapping matches in haystack with strings from replace_with depending on the pattern that matched. The replace_with slice must have length equal to Automaton::patterns_len.

fn try_replace_all_bytes<B>(
    &self,
    haystack: &[u8],
    replace_with: &[B]
) -> Result<Vec<u8>, MatchError>where
    Self: Sized,
    B: AsRef<[u8]>,

Replaces all non-overlapping matches in haystack with strings from replace_with depending on the pattern that matched. The replace_with slice must have length equal to Automaton::patterns_len.

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,

Replaces all non-overlapping matches in haystack by calling the replace_with closure given.

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,

Replaces all non-overlapping matches in haystack by calling the replace_with closure given.

fn try_stream_find_iter<'a, R: Read>(
    &'a self,
    rdr: R
) -> Result<StreamFindIter<'a, Self, R>, MatchError>where
    Self: Sized,

Returns an iterator of non-overlapping matches with this automaton from the stream given.

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]>,

Replaces all non-overlapping matches in 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.

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<()>,

Replaces all non-overlapping matches in rdr by calling the replace_with closure given and writing the result to wtr.

impl Clone for NFA

fn clone(&self) -> NFA

Returns a copy of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for NFA

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

Formats the value using the given formatter.