Source code
Revision control
Copy as Markdown
Other Tools
/*!
Provides [`Automaton`] trait for abstracting over Aho-Corasick automata.
The `Automaton` trait provides a way to write generic code over any
Aho-Corasick automaton. It also provides access to lower level APIs that
permit walking the state transitions of an Aho-Corasick automaton manually.
*/
use alloc::{string::String, vec::Vec};
use crate::util::{
error::MatchError,
primitives::PatternID,
search::{Anchored, Input, Match, MatchKind, Span},
};
pub use crate::util::{
prefilter::{Candidate, Prefilter},
primitives::{StateID, StateIDError},
};
/// We seal the `Automaton` trait for now. It's a big trait, and it's
/// conceivable that I might want to add new required methods, and sealing the
/// trait permits doing that in a backwards compatible fashion. On other the
/// hand, if you have a solid use case for implementing the trait yourself,
/// please file an issue and we can discuss it. This was *mostly* done as a
/// conservative step.
pub(crate) mod private {
pub trait Sealed {}
}
impl private::Sealed for crate::nfa::noncontiguous::NFA {}
impl private::Sealed for crate::nfa::contiguous::NFA {}
impl private::Sealed for crate::dfa::DFA {}
impl<'a, T: private::Sealed + ?Sized> private::Sealed for &'a T {}
/// A trait that abstracts over Aho-Corasick automata.
///
/// This trait primarily exists for niche use cases such as:
///
/// * Using an NFA or DFA directly, bypassing the top-level
/// [`AhoCorasick`](crate::AhoCorasick) searcher. Currently, these include
/// [`noncontiguous::NFA`](crate::nfa::noncontiguous::NFA),
/// [`contiguous::NFA`](crate::nfa::contiguous::NFA) and
/// [`dfa::DFA`](crate::dfa::DFA).
/// * Implementing your own custom search routine by walking the automaton
/// yourself. This might be useful for implementing search on non-contiguous
/// strings or streams.
///
/// For most use cases, it is not expected that users will need
/// to use or even know about this trait. Indeed, the top level
/// [`AhoCorasick`](crate::AhoCorasick) searcher does not expose any details
/// about this trait, nor does it implement it itself.
///
/// Note that this trait defines a number of default methods, such as
/// [`Automaton::try_find`] and [`Automaton::try_find_iter`], which implement
/// higher level search routines in terms of the lower level automata API.
///
/// # Sealed
///
/// Currently, this trait is sealed. That means users of this crate can write
/// generic routines over this trait but cannot implement it themselves. This
/// restriction may be lifted in the future, but sealing the trait permits
/// adding new required methods in a backwards compatible fashion.
///
/// # Special states
///
/// This trait encodes a notion of "special" states in an automaton. Namely,
/// a state is treated as special if it is a dead, match or start state:
///
/// * A dead state is a state that cannot be left once entered. All transitions
/// on a dead state lead back to itself. The dead state is meant to be treated
/// as a sentinel indicating that the search should stop and return a match if
/// one has been found, and nothing otherwise.
/// * A match state is a state that indicates one or more patterns have
/// matched. Depending on the [`MatchKind`] of the automaton, a search may
/// stop once a match is seen, or it may continue looking for matches until
/// it enters a dead state or sees the end of the haystack.
/// * A start state is a state that a search begins in. It is useful to know
/// when a search enters a start state because it may mean that a prefilter can
/// be used to skip ahead and quickly look for candidate matches. Unlike dead
/// and match states, it is never necessary to explicitly handle start states
/// for correctness. Indeed, in this crate, implementations of `Automaton`
/// will only treat start states as "special" when a prefilter is enabled and
/// active. Otherwise, treating it as special has no purpose and winds up
/// slowing down the overall search because it results in ping-ponging between
/// the main state transition and the "special" state logic.
///
/// Since checking whether a state is special by doing three different
/// checks would be too expensive inside a fast search loop, the
/// [`Automaton::is_special`] method is provided for quickly checking whether
/// the state is special. The `Automaton::is_dead`, `Automaton::is_match` and
/// `Automaton::is_start` predicates can then be used to determine which kind
/// of special state it is.
///
/// # Panics
///
/// Most of the APIs on this trait should panic or give incorrect results
/// if invalid inputs are given to it. For example, `Automaton::next_state`
/// has unspecified behavior if the state ID given to it is not a valid
/// state ID for the underlying automaton. Valid state IDs can only be
/// retrieved in one of two ways: calling `Automaton::start_state` or calling
/// `Automaton::next_state` with a valid state ID.
///
/// # Safety
///
/// This trait is not safe to implement so that code may rely on the
/// correctness of implementations of this trait to avoid undefined behavior.
/// The primary correctness guarantees are:
///
/// * `Automaton::start_state` always returns a valid state ID or an error or
/// panics.
/// * `Automaton::next_state`, when given a valid state ID, always returns
/// a valid state ID for all values of `anchored` and `byte`, or otherwise
/// panics.
///
/// In general, the rest of the methods on `Automaton` need to uphold their
/// contracts as well. For example, `Automaton::is_dead` should only returns
/// true if the given state ID is actually a dead state.
///
/// Note that currently this crate does not rely on the safety property defined
/// here to avoid undefined behavior. Instead, this was done to make it
/// _possible_ to do in the future.
///
/// # Example
///
/// This example shows how one might implement a basic but correct search
/// routine. We keep things simple by not using prefilters or worrying about
/// anchored searches, but do make sure our search is correct for all possible
/// [`MatchKind`] semantics. (The comments in the code below note the parts
/// that are needed to support certain `MatchKind` semantics.)
///
/// ```
/// use aho_corasick::{
/// automaton::Automaton,
/// nfa::noncontiguous::NFA,
/// Anchored, Match, MatchError, MatchKind,
/// };
///
/// // Run an unanchored search for 'aut' in 'haystack'. Return the first match
/// // seen according to the automaton's match semantics. This returns an error
/// // if the given automaton does not support unanchored searches.
/// fn find<A: Automaton>(
/// aut: A,
/// haystack: &[u8],
/// ) -> Result<Option<Match>, MatchError> {
/// let mut sid = aut.start_state(Anchored::No)?;
/// let mut at = 0;
/// let mut mat = None;
/// let get_match = |sid, at| {
/// let pid = aut.match_pattern(sid, 0);
/// let len = aut.pattern_len(pid);
/// Match::new(pid, (at - len)..at)
/// };
/// // Start states can be match states!
/// if aut.is_match(sid) {
/// mat = Some(get_match(sid, at));
/// // Standard semantics require matches to be reported as soon as
/// // they're seen. Otherwise, we continue until we see a dead state
/// // or the end of the haystack.
/// if matches!(aut.match_kind(), MatchKind::Standard) {
/// return Ok(mat);
/// }
/// }
/// while at < haystack.len() {
/// sid = aut.next_state(Anchored::No, sid, haystack[at]);
/// if aut.is_special(sid) {
/// if aut.is_dead(sid) {
/// return Ok(mat);
/// } else if aut.is_match(sid) {
/// mat = Some(get_match(sid, at + 1));
/// // As above, standard semantics require that we return
/// // immediately once a match is found.
/// if matches!(aut.match_kind(), MatchKind::Standard) {
/// return Ok(mat);
/// }
/// }
/// }
/// at += 1;
/// }
/// Ok(mat)
/// }
///
/// // Show that it works for standard searches.
/// let nfa = NFA::new(&["samwise", "sam"]).unwrap();
/// assert_eq!(Some(Match::must(1, 0..3)), find(&nfa, b"samwise")?);
///
/// // But also works when using leftmost-first. Notice how the match result
/// // has changed!
/// let nfa = NFA::builder()
/// .match_kind(MatchKind::LeftmostFirst)
/// .build(&["samwise", "sam"])
/// .unwrap();
/// assert_eq!(Some(Match::must(0, 0..7)), find(&nfa, b"samwise")?);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub unsafe trait Automaton: private::Sealed {
/// Returns the starting state for the given anchor mode.
///
/// Upon success, the state ID returned is guaranteed to be valid for
/// this automaton.
///
/// # Errors
///
/// This returns an error when the given search configuration is not
/// supported by the underlying automaton. For example, if the underlying
/// automaton only supports unanchored searches but the given configuration
/// was set to an anchored search, then this must return an error.
fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError>;
/// Performs a state transition from `sid` for `byte` and returns the next
/// state.
///
/// `anchored` should be [`Anchored::Yes`] when executing an anchored
/// search and [`Anchored::No`] otherwise. For some implementations of
/// `Automaton`, it is required to know whether the search is anchored
/// or not in order to avoid following failure transitions. Other
/// implementations may ignore `anchored` altogether and depend on
/// `Automaton::start_state` returning a state that walks a different path
/// through the automaton depending on whether the search is anchored or
/// not.
///
/// # Panics
///
/// This routine may panic or return incorrect results when the given state
/// ID is invalid. A state ID is valid if and only if:
///
/// 1. It came from a call to `Automaton::start_state`, or
/// 2. It came from a previous call to `Automaton::next_state` with a
/// valid state ID.
///
/// Implementations must treat all possible values of `byte` as valid.
///
/// Implementations may panic on unsupported values of `anchored`, but are
/// not required to do so.
fn next_state(
&self,
anchored: Anchored,
sid: StateID,
byte: u8,
) -> StateID;
/// Returns true if the given ID represents a "special" state. A special
/// state is a dead, match or start state.
///
/// Note that implementations may choose to return false when the given ID
/// corresponds to a start state. Namely, it always correct to treat start
/// states as non-special. Implementations must return true for states that
/// are dead or contain matches.
///
/// This has unspecified behavior when given an invalid state ID.
fn is_special(&self, sid: StateID) -> bool;
/// Returns true if the given ID represents a dead state.
///
/// A dead state is a type of "sink" in a finite state machine. It
/// corresponds to a state whose transitions all loop back to itself. That
/// is, once entered, it can never be left. In practice, it serves as a
/// sentinel indicating that the search should terminate.
///
/// This has unspecified behavior when given an invalid state ID.
fn is_dead(&self, sid: StateID) -> bool;
/// Returns true if the given ID represents a match state.
///
/// A match state is always associated with one or more pattern IDs that
/// matched at the position in the haystack when the match state was
/// entered. When a match state is entered, the match semantics dictate
/// whether it should be returned immediately (for `MatchKind::Standard`)
/// or if the search should continue (for `MatchKind::LeftmostFirst` and
/// `MatchKind::LeftmostLongest`) until a dead state is seen or the end of
/// the haystack has been reached.
///
/// This has unspecified behavior when given an invalid state ID.
fn is_match(&self, sid: StateID) -> bool;
/// Returns true if the given ID represents a start state.
///
/// While it is never incorrect to ignore start states during a search
/// (except for the start of the search of course), knowing whether one has
/// entered a start state can be useful for certain classes of performance
/// optimizations. For example, if one is in a start state, it may be legal
/// to try to skip ahead and look for match candidates more quickly than
/// would otherwise be accomplished by walking the automaton.
///
/// Implementations of `Automaton` in this crate "unspecialize" start
/// states when a prefilter is not active or enabled. In this case, it
/// is possible for `Automaton::is_special(sid)` to return false while
/// `Automaton::is_start(sid)` returns true.
///
/// This has unspecified behavior when given an invalid state ID.
fn is_start(&self, sid: StateID) -> bool;
/// Returns the match semantics that this automaton was built with.
fn match_kind(&self) -> MatchKind;
/// Returns the total number of matches for the given state ID.
///
/// This has unspecified behavior if the given ID does not refer to a match
/// state.
fn match_len(&self, sid: StateID) -> usize;
/// Returns the pattern ID for the match state given by `sid` at the
/// `index` given.
///
/// Typically, `index` is only ever greater than `0` when implementing an
/// overlapping search. Otherwise, it's likely that your search only cares
/// about reporting the first pattern ID in a match state.
///
/// This has unspecified behavior if the given ID does not refer to a match
/// state, or if the index is greater than or equal to the total number of
/// matches in this match state.
fn match_pattern(&self, sid: StateID, index: usize) -> PatternID;
/// Returns the total number of patterns compiled into this automaton.
fn patterns_len(&self) -> usize;
/// Returns the length of the pattern for the given ID.
///
/// This has unspecified behavior when given an invalid pattern
/// ID. A pattern ID is valid if and only if it is less than
/// `Automaton::patterns_len`.
fn pattern_len(&self, pid: PatternID) -> usize;
/// Returns the length, in bytes, of the shortest pattern in this
/// automaton.
fn min_pattern_len(&self) -> usize;
/// Returns the length, in bytes, of the longest pattern in this automaton.
fn max_pattern_len(&self) -> usize;
/// Returns the heap memory usage, in bytes, used by this automaton.
fn memory_usage(&self) -> usize;
/// Returns a prefilter, if available, that can be used to accelerate
/// searches for this automaton.
///
/// The typical way this is used is when the start state is entered during
/// a search. When that happens, one can use a prefilter to skip ahead and
/// look for candidate matches without having to walk the automaton on the
/// bytes between candidates.
///
/// Typically a prefilter is only available when there are a small (<100)
/// number of patterns built into the automaton.
fn prefilter(&self) -> Option<&Prefilter>;
/// Executes a non-overlapping search with this automaton using the given
/// configuration.
///
/// See
/// [`AhoCorasick::try_find`](crate::AhoCorasick::try_find)
/// for more documentation and examples.
fn try_find(
&self,
input: &Input<'_>,
) -> Result<Option<Match>, MatchError> {
try_find_fwd(&self, input)
}
/// Executes a overlapping search with this automaton using the given
/// configuration.
///
/// See
/// [`AhoCorasick::try_find_overlapping`](crate::AhoCorasick::try_find_overlapping)
/// for more documentation and examples.
fn try_find_overlapping(
&self,
input: &Input<'_>,
state: &mut OverlappingState,
) -> Result<(), MatchError> {
try_find_overlapping_fwd(&self, input, state)
}
/// Returns an iterator of non-overlapping matches with this automaton
/// using the given configuration.
///
/// See
/// [`AhoCorasick::try_find_iter`](crate::AhoCorasick::try_find_iter)
/// for more documentation and examples.
fn try_find_iter<'a, 'h>(
&'a self,
input: Input<'h>,
) -> Result<FindIter<'a, 'h, Self>, MatchError>
where
Self: Sized,
{
FindIter::new(self, input)
}
/// Returns an iterator of overlapping matches with this automaton
/// using the given configuration.
///
/// See
/// [`AhoCorasick::try_find_overlapping_iter`](crate::AhoCorasick::try_find_overlapping_iter)
/// for more documentation and examples.
fn try_find_overlapping_iter<'a, 'h>(
&'a self,
input: Input<'h>,
) -> Result<FindOverlappingIter<'a, 'h, Self>, MatchError>
where
Self: Sized,
{
if !self.match_kind().is_standard() {
return Err(MatchError::unsupported_overlapping(
self.match_kind(),
));
}
// We might consider lifting this restriction. The reason why I added
// it was to ban the combination of "anchored search" and "overlapping
// iteration." The match semantics aren't totally clear in that case.
// Should we allow *any* matches that are adjacent to *any* previous
// match? Or only following the most recent one? Or only matches
// that start at the beginning of the search? We might also elect to
// just keep this restriction in place, as callers should be able to
// implement it themselves if they want to.
if input.get_anchored().is_anchored() {
return Err(MatchError::invalid_input_anchored());
}
let _ = self.start_state(input.get_anchored())?;
let state = OverlappingState::start();
Ok(FindOverlappingIter { aut: self, input, state })
}
/// 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`.
///
/// See
/// [`AhoCorasick::try_replace_all`](crate::AhoCorasick::try_replace_all)
/// for more documentation and examples.
fn try_replace_all<B>(
&self,
haystack: &str,
replace_with: &[B],
) -> Result<String, MatchError>
where
Self: Sized,
B: AsRef<str>,
{
assert_eq!(
replace_with.len(),
self.patterns_len(),
"replace_all requires a replacement for every pattern \
in the automaton"
);
let mut dst = String::with_capacity(haystack.len());
self.try_replace_all_with(haystack, &mut dst, |mat, _, dst| {
dst.push_str(replace_with[mat.pattern()].as_ref());
true
})?;
Ok(dst)
}
/// 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`.
///
/// See
/// [`AhoCorasick::try_replace_all_bytes`](crate::AhoCorasick::try_replace_all_bytes)
/// for more documentation and examples.
fn try_replace_all_bytes<B>(
&self,
haystack: &[u8],
replace_with: &[B],
) -> Result<Vec<u8>, MatchError>
where
Self: Sized,
B: AsRef<[u8]>,
{
assert_eq!(
replace_with.len(),
self.patterns_len(),
"replace_all requires a replacement for every pattern \
in the automaton"
);
let mut dst = Vec::with_capacity(haystack.len());
self.try_replace_all_with_bytes(haystack, &mut dst, |mat, _, dst| {
dst.extend(replace_with[mat.pattern()].as_ref());
true
})?;
Ok(dst)
}
/// Replaces all non-overlapping matches in `haystack` by calling the
/// `replace_with` closure given.
///
/// See
/// [`AhoCorasick::try_replace_all_with`](crate::AhoCorasick::try_replace_all_with)
/// for more documentation and examples.
fn try_replace_all_with<F>(
&self,
haystack: &str,
dst: &mut String,
mut replace_with: F,
) -> Result<(), MatchError>
where
Self: Sized,
F: FnMut(&Match, &str, &mut String) -> bool,
{
let mut last_match = 0;
for m in self.try_find_iter(Input::new(haystack))? {
// Since there are no restrictions on what kinds of patterns are
// in an Aho-Corasick automaton, we might get matches that split
// a codepoint, or even matches of a partial codepoint. When that
// happens, we just skip the match.
if !haystack.is_char_boundary(m.start())
|| !haystack.is_char_boundary(m.end())
{
continue;
}
dst.push_str(&haystack[last_match..m.start()]);
last_match = m.end();
if !replace_with(&m, &haystack[m.start()..m.end()], dst) {
break;
};
}
dst.push_str(&haystack[last_match..]);
Ok(())
}
/// Replaces all non-overlapping matches in `haystack` by calling the
/// `replace_with` closure given.
///
/// See
/// [`AhoCorasick::try_replace_all_with_bytes`](crate::AhoCorasick::try_replace_all_with_bytes)
/// for more documentation and examples.
fn try_replace_all_with_bytes<F>(
&self,
haystack: &[u8],
dst: &mut Vec<u8>,
mut replace_with: F,
) -> Result<(), MatchError>
where
Self: Sized,
F: FnMut(&Match, &[u8], &mut Vec<u8>) -> bool,
{
let mut last_match = 0;
for m in self.try_find_iter(Input::new(haystack))? {
dst.extend(&haystack[last_match..m.start()]);
last_match = m.end();
if !replace_with(&m, &haystack[m.start()..m.end()], dst) {
break;
};
}
dst.extend(&haystack[last_match..]);
Ok(())
}
/// Returns an iterator of non-overlapping matches with this automaton
/// from the stream given.
///
/// See
/// [`AhoCorasick::try_stream_find_iter`](crate::AhoCorasick::try_stream_find_iter)
/// for more documentation and examples.
#[cfg(feature = "std")]
fn try_stream_find_iter<'a, R: std::io::Read>(
&'a self,
rdr: R,
) -> Result<StreamFindIter<'a, Self, R>, MatchError>
where
Self: Sized,
{
Ok(StreamFindIter { it: StreamChunkIter::new(self, rdr)? })
}
/// 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`.
///
/// See
/// [`AhoCorasick::try_stream_replace_all`](crate::AhoCorasick::try_stream_replace_all)
/// for more documentation and examples.
#[cfg(feature = "std")]
fn try_stream_replace_all<R, W, B>(
&self,
rdr: R,
wtr: W,
replace_with: &[B],
) -> std::io::Result<()>
where
Self: Sized,
R: std::io::Read,
W: std::io::Write,
B: AsRef<[u8]>,
{
assert_eq!(
replace_with.len(),
self.patterns_len(),
"streaming replace_all requires a replacement for every pattern \
in the automaton",
);
self.try_stream_replace_all_with(rdr, wtr, |mat, _, wtr| {
wtr.write_all(replace_with[mat.pattern()].as_ref())
})
}
/// Replaces all non-overlapping matches in `rdr` by calling the
/// `replace_with` closure given and writing the result to `wtr`.
///
/// See
/// [`AhoCorasick::try_stream_replace_all_with`](crate::AhoCorasick::try_stream_replace_all_with)
/// for more documentation and examples.
#[cfg(feature = "std")]
fn try_stream_replace_all_with<R, W, F>(
&self,
rdr: R,
mut wtr: W,
mut replace_with: F,
) -> std::io::Result<()>
where
Self: Sized,
R: std::io::Read,
W: std::io::Write,
F: FnMut(&Match, &[u8], &mut W) -> std::io::Result<()>,
{
let mut it = StreamChunkIter::new(self, rdr).map_err(|e| {
let kind = std::io::ErrorKind::Other;
std::io::Error::new(kind, e)
})?;
while let Some(result) = it.next() {
let chunk = result?;
match chunk {
StreamChunk::NonMatch { bytes, .. } => {
wtr.write_all(bytes)?;
}
StreamChunk::Match { bytes, mat } => {
replace_with(&mat, bytes, &mut wtr)?;
}
}
}
Ok(())
}
}
// SAFETY: This just defers to the underlying 'AcAutomaton' and thus inherits
// its safety properties.
unsafe impl<'a, A: Automaton + ?Sized> Automaton for &'a A {
#[inline(always)]
fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError> {
(**self).start_state(anchored)
}
#[inline(always)]
fn next_state(
&self,
anchored: Anchored,
sid: StateID,
byte: u8,
) -> StateID {
(**self).next_state(anchored, sid, byte)
}
#[inline(always)]
fn is_special(&self, sid: StateID) -> bool {
(**self).is_special(sid)
}
#[inline(always)]
fn is_dead(&self, sid: StateID) -> bool {
(**self).is_dead(sid)
}
#[inline(always)]
fn is_match(&self, sid: StateID) -> bool {
(**self).is_match(sid)
}
#[inline(always)]
fn is_start(&self, sid: StateID) -> bool {
(**self).is_start(sid)
}
#[inline(always)]
fn match_kind(&self) -> MatchKind {
(**self).match_kind()
}
#[inline(always)]
fn match_len(&self, sid: StateID) -> usize {
(**self).match_len(sid)
}
#[inline(always)]
fn match_pattern(&self, sid: StateID, index: usize) -> PatternID {
(**self).match_pattern(sid, index)
}
#[inline(always)]
fn patterns_len(&self) -> usize {
(**self).patterns_len()
}
#[inline(always)]
fn pattern_len(&self, pid: PatternID) -> usize {
(**self).pattern_len(pid)
}
#[inline(always)]
fn min_pattern_len(&self) -> usize {
(**self).min_pattern_len()
}
#[inline(always)]
fn max_pattern_len(&self) -> usize {
(**self).max_pattern_len()
}
#[inline(always)]
fn memory_usage(&self) -> usize {
(**self).memory_usage()
}
#[inline(always)]
fn prefilter(&self) -> Option<&Prefilter> {
(**self).prefilter()
}
}
/// Represents the current state of an overlapping search.
///
/// This is used for overlapping searches since they need to know something
/// about the previous search. For example, when multiple patterns match at the
/// same position, this state tracks the last reported pattern so that the next
/// search knows whether to report another matching pattern or continue with
/// the search at the next position. Additionally, it also tracks which state
/// the last search call terminated in and the current offset of the search
/// in the haystack.
///
/// This type provides limited introspection capabilities. The only thing a
/// caller can do is construct it and pass it around to permit search routines
/// to use it to track state, and to ask whether a match has been found.
///
/// Callers should always provide a fresh state constructed via
/// [`OverlappingState::start`] when starting a new search. That same state
/// should be reused for subsequent searches on the same `Input`. The state
/// given will advance through the haystack itself. Callers can detect the end
/// of a search when neither an error nor a match is returned.
///
/// # Example
///
/// This example shows how to manually iterate over all overlapping matches. If
/// you need this, you might consider using
/// [`AhoCorasick::find_overlapping_iter`](crate::AhoCorasick::find_overlapping_iter)
/// instead, but this shows how to correctly use an `OverlappingState`.
///
/// ```
/// use aho_corasick::{
/// automaton::OverlappingState,
/// AhoCorasick, Input, Match,
/// };
///
/// let patterns = &["append", "appendage", "app"];
/// let haystack = "append the app to the appendage";
///
/// let ac = AhoCorasick::new(patterns).unwrap();
/// let mut state = OverlappingState::start();
/// let mut matches = vec![];
///
/// loop {
/// ac.find_overlapping(haystack, &mut state);
/// let mat = match state.get_match() {
/// None => break,
/// Some(mat) => mat,
/// };
/// matches.push(mat);
/// }
/// let expected = vec![
/// Match::must(2, 0..3),
/// Match::must(0, 0..6),
/// Match::must(2, 11..14),
/// Match::must(2, 22..25),
/// Match::must(0, 22..28),
/// Match::must(1, 22..31),
/// ];
/// assert_eq!(expected, matches);
/// ```
#[derive(Clone, Debug)]
pub struct OverlappingState {
/// The match reported by the most recent overlapping search to use this
/// state.
///
/// If a search does not find any matches, then it is expected to clear
/// this value.
mat: Option<Match>,
/// The state ID of the state at which the search was in when the call
/// terminated. When this is a match state, `last_match` must be set to a
/// non-None value.
///
/// A `None` value indicates the start state of the corresponding
/// automaton. We cannot use the actual ID, since any one automaton may
/// have many start states, and which one is in use depends on search-time
/// factors (such as whether the search is anchored or not).
id: Option<StateID>,
/// The position of the search.
///
/// When `id` is None (i.e., we are starting a search), this is set to
/// the beginning of the search as given by the caller regardless of its
/// current value. Subsequent calls to an overlapping search pick up at
/// this offset.
at: usize,
/// The index into the matching patterns of the next match to report if the
/// current state is a match state. Note that this may be 1 greater than
/// the total number of matches to report for the current match state. (In
/// which case, no more matches should be reported at the current position
/// and the search should advance to the next position.)
next_match_index: Option<usize>,
}
impl OverlappingState {
/// Create a new overlapping state that begins at the start state.
pub fn start() -> OverlappingState {
OverlappingState { mat: None, id: None, at: 0, next_match_index: None }
}
/// Return the match result of the most recent search to execute with this
/// state.
///
/// Every search will clear this result automatically, such that if no
/// match is found, this will always correctly report `None`.
pub fn get_match(&self) -> Option<Match> {
self.mat
}
}
/// An iterator of non-overlapping matches in a particular haystack.
///
/// This iterator yields matches according to the [`MatchKind`] used by this
/// automaton.
///
/// This iterator is constructed via the [`Automaton::try_find_iter`] method.
///
/// The type variable `A` refers to the implementation of the [`Automaton`]
/// trait used to execute the search.
///
/// The lifetime `'a` refers to the lifetime of the [`Automaton`]
/// implementation.
///
/// The lifetime `'h` refers to the lifetime of the haystack being searched.
#[derive(Debug)]
pub struct FindIter<'a, 'h, A> {
/// The automaton used to drive the search.
aut: &'a A,
/// The input parameters to give to each search call.
///
/// The start position of the search is mutated during iteration.
input: Input<'h>,
/// Records the end offset of the most recent match. This is necessary to
/// handle a corner case for preventing empty matches from overlapping with
/// the ending bounds of a prior match.
last_match_end: Option<usize>,
}
impl<'a, 'h, A: Automaton> FindIter<'a, 'h, A> {
/// Creates a new non-overlapping iterator. If the given automaton would
/// return an error on a search with the given input configuration, then
/// that error is returned here.
fn new(
aut: &'a A,
input: Input<'h>,
) -> Result<FindIter<'a, 'h, A>, MatchError> {
// The only way this search can fail is if we cannot retrieve the start
// state. e.g., Asking for an anchored search when only unanchored
// searches are supported.
let _ = aut.start_state(input.get_anchored())?;
Ok(FindIter { aut, input, last_match_end: None })
}
/// Executes a search and returns a match if one is found.
///
/// This does not advance the input forward. It just executes a search
/// based on the current configuration/offsets.
fn search(&self) -> Option<Match> {
// The unwrap is OK here because we check at iterator construction time
// that no subsequent search call (using the same configuration) will
// ever return an error.
self.aut
.try_find(&self.input)
.expect("already checked that no match error can occur")
}
/// Handles the special case of an empty match by ensuring that 1) the
/// iterator always advances and 2) empty matches never overlap with other
/// matches.
///
/// (1) is necessary because we principally make progress by setting the
/// starting location of the next search to the ending location of the last
/// match. But if a match is empty, then this results in a search that does
/// not advance and thus does not terminate.
///
/// (2) is not strictly necessary, but makes intuitive sense and matches
/// the presiding behavior of most general purpose regex engines.
/// (Obviously this crate isn't a regex engine, but we choose to match
/// their semantics.) The "intuitive sense" here is that we want to report
/// NON-overlapping matches. So for example, given the patterns 'a' and
/// '' (an empty string) against the haystack 'a', without the special
/// handling, you'd get the matches [0, 1) and [1, 1), where the latter
/// overlaps with the end bounds of the former.
///
/// Note that we mark this cold and forcefully prevent inlining because
/// handling empty matches like this is extremely rare and does require
/// quite a bit of code, comparatively. Keeping this code out of the main
/// iterator function keeps it smaller and more amenable to inlining
/// itself.
#[cold]
#[inline(never)]
fn handle_overlapping_empty_match(
&mut self,
mut m: Match,
) -> Option<Match> {
assert!(m.is_empty());
if Some(m.end()) == self.last_match_end {
self.input.set_start(self.input.start().checked_add(1).unwrap());
m = self.search()?;
}
Some(m)
}
}
impl<'a, 'h, A: Automaton> Iterator for FindIter<'a, 'h, A> {
type Item = Match;
#[inline(always)]
fn next(&mut self) -> Option<Match> {
let mut m = self.search()?;
if m.is_empty() {
m = self.handle_overlapping_empty_match(m)?;
}
self.input.set_start(m.end());
self.last_match_end = Some(m.end());
Some(m)
}
}
/// An iterator of overlapping matches in a particular haystack.
///
/// This iterator will report all possible matches in a particular haystack,
/// even when the matches overlap.
///
/// This iterator is constructed via the
/// [`Automaton::try_find_overlapping_iter`] method.
///
/// The type variable `A` refers to the implementation of the [`Automaton`]
/// trait used to execute the search.
///
/// The lifetime `'a` refers to the lifetime of the [`Automaton`]
/// implementation.
///
/// The lifetime `'h` refers to the lifetime of the haystack being searched.
#[derive(Debug)]
pub struct FindOverlappingIter<'a, 'h, A> {
aut: &'a A,
input: Input<'h>,
state: OverlappingState,
}
impl<'a, 'h, A: Automaton> Iterator for FindOverlappingIter<'a, 'h, A> {
type Item = Match;
#[inline(always)]
fn next(&mut self) -> Option<Match> {
self.aut
.try_find_overlapping(&self.input, &mut self.state)
.expect("already checked that no match error can occur here");
self.state.get_match()
}
}
/// An iterator that reports matches in a stream.
///
/// This iterator yields elements of type `io::Result<Match>`, where an error
/// is reported if there was a problem reading from the underlying stream.
/// The iterator terminates only when the underlying stream reaches `EOF`.
///
/// This iterator is constructed via the [`Automaton::try_stream_find_iter`]
/// method.
///
/// The type variable `A` refers to the implementation of the [`Automaton`]
/// trait used to execute the search.
///
/// The type variable `R` refers to the `io::Read` stream that is being read
/// from.
///
/// The lifetime `'a` refers to the lifetime of the [`Automaton`]
/// implementation.
#[cfg(feature = "std")]
#[derive(Debug)]
pub struct StreamFindIter<'a, A, R> {
it: StreamChunkIter<'a, A, R>,
}
#[cfg(feature = "std")]
impl<'a, A: Automaton, R: std::io::Read> Iterator
for StreamFindIter<'a, A, R>
{
type Item = std::io::Result<Match>;
fn next(&mut self) -> Option<std::io::Result<Match>> {
loop {
match self.it.next() {
None => return None,
Some(Err(err)) => return Some(Err(err)),
Some(Ok(StreamChunk::NonMatch { .. })) => {}
Some(Ok(StreamChunk::Match { mat, .. })) => {
return Some(Ok(mat));
}
}
}
}
}
/// An iterator that reports matches in a stream.
///
/// (This doesn't actually implement the `Iterator` trait because it returns
/// something with a lifetime attached to a buffer it owns, but that's OK. It
/// still has a `next` method and is iterator-like enough to be fine.)
///
/// This iterator yields elements of type `io::Result<StreamChunk>`, where
/// an error is reported if there was a problem reading from the underlying
/// stream. The iterator terminates only when the underlying stream reaches
/// `EOF`.
///
/// The idea here is that each chunk represents either a match or a non-match,
/// and if you concatenated all of the chunks together, you'd reproduce the
/// entire contents of the stream, byte-for-byte.
///
/// This chunk machinery is a bit complicated and it isn't strictly required
/// for a stream searcher that just reports matches. But we do need something
/// like this to deal with the "replacement" API, which needs to know which
/// chunks it can copy and which it needs to replace.
#[cfg(feature = "std")]
#[derive(Debug)]
struct StreamChunkIter<'a, A, R> {
/// The underlying automaton to do the search.
aut: &'a A,
/// The source of bytes we read from.
rdr: R,
/// A roll buffer for managing bytes from `rdr`. Basically, this is used
/// to handle the case of a match that is split by two different
/// calls to `rdr.read()`. This isn't strictly needed if all we needed to
/// do was report matches, but here we are reporting chunks of non-matches
/// and matches and in order to do that, we really just cannot treat our
/// stream as non-overlapping blocks of bytes. We need to permit some
/// overlap while we retain bytes from a previous `read` call in memory.
buf: crate::util::buffer::Buffer,
/// The unanchored starting state of this automaton.
start: StateID,
/// The state of the automaton.
sid: StateID,
/// The absolute position over the entire stream.
absolute_pos: usize,
/// The position we're currently at within `buf`.
buffer_pos: usize,
/// The buffer position of the end of the bytes that we last returned
/// to the caller. Basically, whenever we find a match, we look to see if
/// there is a difference between where the match started and the position
/// of the last byte we returned to the caller. If there's a difference,
/// then we need to return a 'NonMatch' chunk.
buffer_reported_pos: usize,
}
#[cfg(feature = "std")]
impl<'a, A: Automaton, R: std::io::Read> StreamChunkIter<'a, A, R> {
fn new(
aut: &'a A,
rdr: R,
) -> Result<StreamChunkIter<'a, A, R>, MatchError> {
// This restriction is a carry-over from older versions of this crate.
// I didn't have the bandwidth to think through how to handle, say,
// leftmost-first or leftmost-longest matching, but... it should be
// possible? The main problem is that once you see a match state in
// leftmost-first semantics, you can't just stop at that point and
// report a match. You have to keep going until you either hit a dead
// state or EOF. So how do you know when you'll hit a dead state? Well,
// you don't. With Aho-Corasick, I believe you can put a bound on it
// and say, "once a match has been seen, you'll need to scan forward at
// most N bytes" where N=aut.max_pattern_len().
//
// Which is fine, but it does mean that state about whether we're still
// looking for a dead state or not needs to persist across buffer
// refills. Which this code doesn't really handle. It does preserve
// *some* state across buffer refills, basically ensuring that a match
// span is always in memory.
if !aut.match_kind().is_standard() {
return Err(MatchError::unsupported_stream(aut.match_kind()));
}
// This is kind of a cop-out, but empty matches are SUPER annoying.
// If we know they can't happen (which is what we enforce here), then
// it makes a lot of logic much simpler. With that said, I'm open to
// supporting this case, but we need to define proper semantics for it
// first. It wasn't totally clear to me what it should do at the time
// of writing, so I decided to just be conservative.
//
// It also seems like a very weird case to support anyway. Why search a
// stream if you're just going to get a match at every position?
//
// ¯\_(ツ)_/¯
if aut.min_pattern_len() == 0 {
return Err(MatchError::unsupported_empty());
}
let start = aut.start_state(Anchored::No)?;
Ok(StreamChunkIter {
aut,
rdr,
buf: crate::util::buffer::Buffer::new(aut.max_pattern_len()),
start,
sid: start,
absolute_pos: 0,
buffer_pos: 0,
buffer_reported_pos: 0,
})
}
fn next(&mut self) -> Option<std::io::Result<StreamChunk>> {
// This code is pretty gnarly. It IS simpler than the equivalent code
// in the previous aho-corasick release, in part because we inline
// automaton traversal here and also in part because we have abdicated
// support for automatons that contain an empty pattern.
//
// I suspect this code could be made a bit simpler by designing a
// better buffer abstraction.
//
// But in general, this code is basically write-only. So you'll need
// to go through it step-by-step to grok it. One of the key bits of
// complexity is tracking a few different offsets. 'buffer_pos' is
// where we are in the buffer for search. 'buffer_reported_pos' is the
// position immediately following the last byte in the buffer that
// we've returned to the caller. And 'absolute_pos' is the overall
// current absolute position of the search in the entire stream, and
// this is what match spans are reported in terms of.
loop {
if self.aut.is_match(self.sid) {
let mat = self.get_match();
if let Some(r) = self.get_non_match_chunk(mat) {
self.buffer_reported_pos += r.len();
let bytes = &self.buf.buffer()[r];
return Some(Ok(StreamChunk::NonMatch { bytes }));
}
self.sid = self.start;
let r = self.get_match_chunk(mat);
self.buffer_reported_pos += r.len();
let bytes = &self.buf.buffer()[r];
return Some(Ok(StreamChunk::Match { bytes, mat }));
}
if self.buffer_pos >= self.buf.buffer().len() {
if let Some(r) = self.get_pre_roll_non_match_chunk() {
self.buffer_reported_pos += r.len();
let bytes = &self.buf.buffer()[r];
return Some(Ok(StreamChunk::NonMatch { bytes }));
}
if self.buf.buffer().len() >= self.buf.min_buffer_len() {
self.buffer_pos = self.buf.min_buffer_len();
self.buffer_reported_pos -=
self.buf.buffer().len() - self.buf.min_buffer_len();
self.buf.roll();
}
match self.buf.fill(&mut self.rdr) {
Err(err) => return Some(Err(err)),
Ok(true) => {}
Ok(false) => {
// We've hit EOF, but if there are still some
// unreported bytes remaining, return them now.
if let Some(r) = self.get_eof_non_match_chunk() {
self.buffer_reported_pos += r.len();
let bytes = &self.buf.buffer()[r];
return Some(Ok(StreamChunk::NonMatch { bytes }));
}
// We've reported everything!
return None;
}
}
}
let start = self.absolute_pos;
for &byte in self.buf.buffer()[self.buffer_pos..].iter() {
self.sid = self.aut.next_state(Anchored::No, self.sid, byte);
self.absolute_pos += 1;
if self.aut.is_match(self.sid) {
break;
}
}
self.buffer_pos += self.absolute_pos - start;
}
}
/// Return a match chunk for the given match. It is assumed that the match
/// ends at the current `buffer_pos`.
fn get_match_chunk(&self, mat: Match) -> core::ops::Range<usize> {
let start = self.buffer_pos - mat.len();
let end = self.buffer_pos;
start..end
}
/// Return a non-match chunk, if necessary, just before reporting a match.
/// This returns `None` if there is nothing to report. Otherwise, this
/// assumes that the given match ends at the current `buffer_pos`.
fn get_non_match_chunk(
&self,
mat: Match,
) -> Option<core::ops::Range<usize>> {
let buffer_mat_start = self.buffer_pos - mat.len();
if buffer_mat_start > self.buffer_reported_pos {
let start = self.buffer_reported_pos;
let end = buffer_mat_start;
return Some(start..end);
}
None
}
/// Look for any bytes that should be reported as a non-match just before
/// rolling the buffer.
///
/// Note that this only reports bytes up to `buffer.len() -
/// min_buffer_len`, as it's not possible to know whether the bytes
/// following that will participate in a match or not.
fn get_pre_roll_non_match_chunk(&self) -> Option<core::ops::Range<usize>> {
let end =
self.buf.buffer().len().saturating_sub(self.buf.min_buffer_len());
if self.buffer_reported_pos < end {
return Some(self.buffer_reported_pos..end);
}
None
}
/// Return any unreported bytes as a non-match up to the end of the buffer.
///
/// This should only be called when the entire contents of the buffer have
/// been searched and EOF has been hit when trying to fill the buffer.
fn get_eof_non_match_chunk(&self) -> Option<core::ops::Range<usize>> {
if self.buffer_reported_pos < self.buf.buffer().len() {
return Some(self.buffer_reported_pos..self.buf.buffer().len());
}
None
}
/// Return the match at the current position for the current state.
///
/// This panics if `self.aut.is_match(self.sid)` isn't true.
fn get_match(&self) -> Match {
get_match(self.aut, self.sid, 0, self.absolute_pos)
}
}
/// A single chunk yielded by the stream chunk iterator.
///
/// The `'r` lifetime refers to the lifetime of the stream chunk iterator.
#[cfg(feature = "std")]
#[derive(Debug)]
enum StreamChunk<'r> {
/// A chunk that does not contain any matches.
NonMatch { bytes: &'r [u8] },
/// A chunk that precisely contains a match.
Match { bytes: &'r [u8], mat: Match },
}
#[inline(never)]
pub(crate) fn try_find_fwd<A: Automaton + ?Sized>(
aut: &A,
input: &Input<'_>,
) -> Result<Option<Match>, MatchError> {
if input.is_done() {
return Ok(None);
}
let earliest = aut.match_kind().is_standard() || input.get_earliest();
if input.get_anchored().is_anchored() {
try_find_fwd_imp(aut, input, None, Anchored::Yes, earliest)
} else if let Some(pre) = aut.prefilter() {
if earliest {
try_find_fwd_imp(aut, input, Some(pre), Anchored::No, true)
} else {
try_find_fwd_imp(aut, input, Some(pre), Anchored::No, false)
}
} else {
if earliest {
try_find_fwd_imp(aut, input, None, Anchored::No, true)
} else {
try_find_fwd_imp(aut, input, None, Anchored::No, false)
}
}
}
#[inline(always)]
fn try_find_fwd_imp<A: Automaton + ?Sized>(
aut: &A,
input: &Input<'_>,
pre: Option<&Prefilter>,
anchored: Anchored,
earliest: bool,
) -> Result<Option<Match>, MatchError> {
let mut sid = aut.start_state(input.get_anchored())?;
let mut at = input.start();
let mut mat = None;
if aut.is_match(sid) {
mat = Some(get_match(aut, sid, 0, at));
if earliest {
return Ok(mat);
}
}
if let Some(pre) = pre {
match pre.find_in(input.haystack(), input.get_span()) {
Candidate::None => return Ok(None),
Candidate::Match(m) => return Ok(Some(m)),
Candidate::PossibleStartOfMatch(i) => {
at = i;
}
}
}
while at < input.end() {
// I've tried unrolling this loop and eliding bounds checks, but no
// matter what I did, I could not observe a consistent improvement on
// any benchmark I could devise. (If someone wants to re-litigate this,
// the way to do it is to add an 'next_state_unchecked' method to the
// 'Automaton' trait with a default impl that uses 'next_state'. Then
// use 'aut.next_state_unchecked' here and implement it on DFA using
// unchecked slice index acces.)
sid = aut.next_state(anchored, sid, input.haystack()[at]);
if aut.is_special(sid) {
if aut.is_dead(sid) {
return Ok(mat);
} else if aut.is_match(sid) {
// We use 'at + 1' here because the match state is entered
// at the last byte of the pattern. Since we use half-open
// intervals, the end of the range of the match is one past the
// last byte.
let m = get_match(aut, sid, 0, at + 1);
// For the automata in this crate, we make a size trade off
// where we reuse the same automaton for both anchored and
// unanchored searches. We achieve this, principally, by simply
// not following failure transitions while computing the next
// state. Instead, if we fail to find the next state, we return
// a dead state, which instructs the search to stop. (This
// is why 'next_state' needs to know whether the search is
// anchored or not.) In addition, we have different start
// states for anchored and unanchored searches. The latter has
// a self-loop where as the former does not.
//
// In this way, we can use the same trie to execute both
// anchored and unanchored searches. There is a catch though.
// When building an Aho-Corasick automaton for unanchored
// searches, we copy matches from match states to other states
// (which would otherwise not be match states) if they are
// reachable via a failure transition. In the case of an
// anchored search, we *specifically* do not want to report
// these matches because they represent matches that start past
// the beginning of the search.
//
// Now we could tweak the automaton somehow to differentiate
// anchored from unanchored match states, but this would make
// 'aut.is_match' and potentially 'aut.is_special' slower. And
// also make the automaton itself more complex.
//
// Instead, we insert a special hack: if the search is
// anchored, we simply ignore matches that don't begin at
// the start of the search. This is not quite ideal, but we
// do specialize this function in such a way that unanchored
// searches don't pay for this additional branch. While this
// might cause a search to continue on for more than it
// otherwise optimally would, it will be no more than the
// longest pattern in the automaton. The reason for this is
// that we ensure we don't follow failure transitions during
// an anchored search. Combined with using a different anchored
// starting state with no self-loop, we guarantee that we'll
// at worst move through a number of transitions equal to the
// longest pattern.
//
// Now for DFAs, the whole point of them is to eliminate
// failure transitions entirely. So there is no way to say "if
// it's an anchored search don't follow failure transitions."
// Instead, we actually have to build two entirely separate
// automatons into the transition table. One with failure
// transitions built into it and another that is effectively
// just an encoding of the base trie into a transition table.
// DFAs still need this check though, because the match states
// still carry matches only reachable via a failure transition.
// Why? Because removing them seems difficult, although I
// haven't given it a lot of thought.
if !(anchored.is_anchored() && m.start() > input.start()) {
mat = Some(m);
if earliest {
return Ok(mat);
}
}
} else if let Some(pre) = pre {
// If we're here, we know it's a special state that is not a
// dead or a match state AND that a prefilter is active. Thus,
// it must be a start state.
debug_assert!(aut.is_start(sid));
// We don't care about 'Candidate::Match' here because if such
// a match were possible, it would have been returned above
// when we run the prefilter before walking the automaton.
let span = Span::from(at..input.end());
match pre.find_in(input.haystack(), span).into_option() {
None => return Ok(None),
Some(i) => {
if i > at {
at = i;
continue;
}
}
}
} else {
// When pre.is_none(), then starting states should not be
// treated as special. That is, without a prefilter, is_special
// should only return true when the state is a dead or a match
// state.
//
// It is possible to execute a search without a prefilter even
// when the underlying searcher has one: an anchored search.
// But in this case, the automaton makes it impossible to move
// back to the start state by construction, and thus, we should
// never reach this branch.
debug_assert!(false, "unreachable");
}
}
at += 1;
}
Ok(mat)
}
#[inline(never)]
fn try_find_overlapping_fwd<A: Automaton + ?Sized>(
aut: &A,
input: &Input<'_>,
state: &mut OverlappingState,
) -> Result<(), MatchError> {
state.mat = None;
if input.is_done() {
return Ok(());
}
// Searching with a pattern ID is always anchored, so we should only ever
// use a prefilter when no pattern ID is given.
if aut.prefilter().is_some() && !input.get_anchored().is_anchored() {
let pre = aut.prefilter().unwrap();
try_find_overlapping_fwd_imp(aut, input, Some(pre), state)
} else {
try_find_overlapping_fwd_imp(aut, input, None, state)
}
}
#[inline(always)]
fn try_find_overlapping_fwd_imp<A: Automaton + ?Sized>(
aut: &A,
input: &Input<'_>,
pre: Option<&Prefilter>,
state: &mut OverlappingState,
) -> Result<(), MatchError> {
let mut sid = match state.id {
None => {
let sid = aut.start_state(input.get_anchored())?;
// Handle the case where the start state is a match state. That is,
// the empty string is in our automaton. We report every match we
// can here before moving on and updating 'state.at' and 'state.id'
// to find more matches in other parts of the haystack.
if aut.is_match(sid) {
let i = state.next_match_index.unwrap_or(0);
let len = aut.match_len(sid);
if i < len {
state.next_match_index = Some(i + 1);
state.mat = Some(get_match(aut, sid, i, input.start()));
return Ok(());
}
}
state.at = input.start();
state.id = Some(sid);
state.next_match_index = None;
state.mat = None;
sid
}
Some(sid) => {
// If we still have matches left to report in this state then
// report them until we've exhausted them. Only after that do we
// advance to the next offset in the haystack.
if let Some(i) = state.next_match_index {
let len = aut.match_len(sid);
if i < len {
state.next_match_index = Some(i + 1);
state.mat = Some(get_match(aut, sid, i, state.at + 1));
return Ok(());
}
// Once we've reported all matches at a given position, we need
// to advance the search to the next position.
state.at += 1;
state.next_match_index = None;
state.mat = None;
}
sid
}
};
while state.at < input.end() {
sid = aut.next_state(
input.get_anchored(),
sid,
input.haystack()[state.at],
);
if aut.is_special(sid) {
state.id = Some(sid);
if aut.is_dead(sid) {
return Ok(());
} else if aut.is_match(sid) {
state.next_match_index = Some(1);
state.mat = Some(get_match(aut, sid, 0, state.at + 1));
return Ok(());
} else if let Some(pre) = pre {
// If we're here, we know it's a special state that is not a
// dead or a match state AND that a prefilter is active. Thus,
// it must be a start state.
debug_assert!(aut.is_start(sid));
let span = Span::from(state.at..input.end());
match pre.find_in(input.haystack(), span).into_option() {
None => return Ok(()),
Some(i) => {
if i > state.at {
state.at = i;
continue;
}
}
}
} else {
// When pre.is_none(), then starting states should not be
// treated as special. That is, without a prefilter, is_special
// should only return true when the state is a dead or a match
// state.
//
// ... except for one special case: in stream searching, we
// currently call overlapping search with a 'None' prefilter,
// regardless of whether one exists or not, because stream
// searching can't currently deal with prefilters correctly in
// all cases.
}
}
state.at += 1;
}
state.id = Some(sid);
Ok(())
}
#[inline(always)]
fn get_match<A: Automaton + ?Sized>(
aut: &A,
sid: StateID,
index: usize,
at: usize,
) -> Match {
let pid = aut.match_pattern(sid, index);
let len = aut.pattern_len(pid);
Match::new(pid, (at - len)..at)
}
/// Write a prefix "state" indicator for fmt::Debug impls. It always writes
/// exactly two printable bytes to the given formatter.
///
/// Specifically, this tries to succinctly distinguish the different types of
/// states: dead states, start states and match states. It even accounts for
/// the possible overlappings of different state types. (The only possible
/// overlapping is that of match and start states.)
pub(crate) fn fmt_state_indicator<A: Automaton>(
f: &mut core::fmt::Formatter<'_>,
aut: A,
id: StateID,
) -> core::fmt::Result {
if aut.is_dead(id) {
write!(f, "D ")?;
} else if aut.is_match(id) {
if aut.is_start(id) {
write!(f, "*>")?;
} else {
write!(f, "* ")?;
}
} else if aut.is_start(id) {
write!(f, " >")?;
} else {
write!(f, " ")?;
}
Ok(())
}
/// Return an iterator of transitions in a sparse format given an iterator
/// of all explicitly defined transitions. The iterator yields ranges of
/// transitions, such that any adjacent transitions mapped to the same
/// state are combined into a single range.
pub(crate) fn sparse_transitions<'a>(
mut it: impl Iterator<Item = (u8, StateID)> + 'a,
) -> impl Iterator<Item = (u8, u8, StateID)> + 'a {
let mut cur: Option<(u8, u8, StateID)> = None;
core::iter::from_fn(move || {
while let Some((class, next)) = it.next() {
let (prev_start, prev_end, prev_next) = match cur {
Some(x) => x,
None => {
cur = Some((class, class, next));
continue;
}
};
if prev_next == next {
cur = Some((prev_start, class, prev_next));
} else {
cur = Some((class, class, next));
return Some((prev_start, prev_end, prev_next));
}
}
if let Some((start, end, next)) = cur.take() {
return Some((start, end, next));
}
None
})
}