Struct regex_automata::hybrid::dfa::DFA

pub struct DFA { /* private fields */ }

A hybrid NFA/DFA (also called a “lazy DFA”) for regex searching.

A lazy DFA is a DFA that builds itself at search time. It otherwise has very similar characteristics as a dense::DFA. Indeed, both support precisely the same regex features with precisely the same semantics.

Where as a dense::DFA must be completely built to handle any input before it may be used for search, a lazy DFA starts off effectively empty. During a search, a lazy DFA will build itself depending on whether it has already computed the next transition or not. If it has, then it looks a lot like a dense::DFA internally: it does a very fast table based access to find the next transition. Otherwise, if the state hasn’t been computed, then it does determinization for that specific transition to compute the next DFA state.

The main selling point of a lazy DFA is that, in practice, it has the performance profile of a dense::DFA without the weakness of it taking worst case exponential time to build. Indeed, for each byte of input, the lazy DFA will construct as most one new DFA state. Thus, a lazy DFA achieves worst case O(mn) time for regex search (where m ~ pattern.len() and n ~ haystack.len()).

The main downsides of a lazy DFA are:

1. It requires mutable “cache” space during search. This is where the transition table, among other things, is stored.
2. In pathological cases (e.g., if the cache is too small), it will run out of room and either require a bigger cache capacity or will repeatedly clear the cache and thus repeatedly regenerate DFA states. Overall, this will tend to be slower than a typical NFA simulation.

Capabilities

Like a dense::DFA, a single lazy DFA fundamentally supports the following operations:

1. Detection of a match.
2. Location of the end of a match.
3. In the case of a lazy DFA with multiple patterns, which pattern matched is reported as well.

A notable absence from the above list of capabilities is the location of the start of a match. In order to provide both the start and end of a match, two lazy DFAs are required. This functionality is provided by a Regex.

Example

This shows how to build a lazy DFA with the default configuration and execute a search. Notice how, in contrast to a dense::DFA, we must create a cache and pass it to our search routine.

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

let dfa = DFA::new("foo[0-9]+")?;
let mut cache = dfa.create_cache();

let expected = Some(HalfMatch::must(0, 8));
assert_eq!(expected, dfa.find_leftmost_fwd(&mut cache, b"foo12345")?);

Implementations

impl DFA

pub fn new(pattern: &str) -> Result<DFA, BuildError>

Parse the given regular expression using a default configuration and return the corresponding lazy DFA.

If you want a non-default configuration, then use the Builder to set your own configuration.

Example

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

let dfa = DFA::new("foo[0-9]+bar")?;
let mut cache = dfa.create_cache();

let expected = HalfMatch::must(0, 11);
assert_eq!(
    Some(expected),
    dfa.find_leftmost_fwd(&mut cache, b"foo12345bar")?,
);

pub fn new_many<P: AsRef<str>>(patterns: &[P]) -> Result<DFA, BuildError>

Parse the given regular expressions using a default configuration and return the corresponding lazy multi-DFA.

If you want a non-default configuration, then use the Builder to set your own configuration.

Example

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

let dfa = DFA::new_many(&["[0-9]+", "[a-z]+"])?;
let mut cache = dfa.create_cache();

let expected = HalfMatch::must(1, 3);
assert_eq!(
    Some(expected),
    dfa.find_leftmost_fwd(&mut cache, b"foo12345bar")?,
);

pub fn always_match() -> Result<DFA, BuildError>

Create a new lazy DFA that matches every input.

Example

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

let dfa = DFA::always_match()?;
let mut cache = dfa.create_cache();

let expected = HalfMatch::must(0, 0);
assert_eq!(Some(expected), dfa.find_leftmost_fwd(&mut cache, b"")?);
assert_eq!(Some(expected), dfa.find_leftmost_fwd(&mut cache, b"foo")?);

pub fn never_match() -> Result<DFA, BuildError>

Create a new lazy DFA that never matches any input.

Example

use regex_automata::hybrid::dfa::DFA;

let dfa = DFA::never_match()?;
let mut cache = dfa.create_cache();

assert_eq!(None, dfa.find_leftmost_fwd(&mut cache, b"")?);
assert_eq!(None, dfa.find_leftmost_fwd(&mut cache, b"foo")?);

pub fn config() -> Config

Return a default configuration for a DFA.

This is a convenience routine to avoid needing to import the Config type when customizing the construction of a lazy DFA.

Example

This example shows how to build a lazy DFA that only executes searches in anchored mode.

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

let re = DFA::builder()
    .configure(DFA::config().anchored(true))
    .build(r"[0-9]+")?;
let mut cache = re.create_cache();

let haystack = "abc123xyz".as_bytes();
assert_eq!(None, re.find_leftmost_fwd(&mut cache, haystack)?);
assert_eq!(
    Some(HalfMatch::must(0, 3)),
    re.find_leftmost_fwd(&mut cache, &haystack[3..6])?,
);

pub fn builder() -> Builder

Return a builder for configuring the construction of a Regex.

This is a convenience routine to avoid needing to import the Builder type in common cases.

Example

This example shows how to use the builder to disable UTF-8 mode everywhere for lazy DFAs. This includes disabling it for both the concrete syntax (e.g., . matches any byte and Unicode character classes like \p{Letter} are not allowed) and for the unanchored search prefix. The latter enables the regex to match anywhere in a sequence of arbitrary bytes. (Typically, the unanchored search prefix will only permit matching valid UTF-8.)

use regex_automata::{
    hybrid::dfa::DFA,
    nfa::thompson,
    HalfMatch, SyntaxConfig,
};

let re = DFA::builder()
    .syntax(SyntaxConfig::new().utf8(false))
    .thompson(thompson::Config::new().utf8(false))
    .build(r"foo(?-u:[^b])ar.*")?;
let mut cache = re.create_cache();

let haystack = b"\xFEfoo\xFFarzz\xE2\x98\xFF\n";
let expected = Some(HalfMatch::must(0, 9));
let got = re.find_leftmost_fwd(&mut cache, haystack)?;
assert_eq!(expected, got);

pub fn create_cache(&self) -> Cache

Create a new cache for this lazy DFA.

The cache returned should only be used for searches for this lazy DFA. If you want to reuse the cache for another DFA, then you must call Cache::reset with that DFA (or, equivalently, DFA::reset_cache).

pub fn reset_cache(&self, cache: &mut Cache)

Reset the given cache such that it can be used for searching with the this lazy DFA (and only this DFA).

A cache reset permits reusing memory already allocated in this cache with a different lazy DFA.

Resetting a cache sets its “clear count” to 0. This is relevant if the lazy DFA has been configured to “give up” after it has cleared the cache a certain number of times.

Any lazy state ID generated by the cache prior to resetting it is invalid after the reset.

Example

This shows how to re-purpose a cache for use with a different DFA.

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

let dfa1 = DFA::new(r"\w")?;
let dfa2 = DFA::new(r"\W")?;

let mut cache = dfa1.create_cache();
assert_eq!(
    Some(HalfMatch::must(0, 2)),
    dfa1.find_leftmost_fwd(&mut cache, "Δ".as_bytes())?,
);

// Using 'cache' with dfa2 is not allowed. It may result in panics or
// incorrect results. In order to re-purpose the cache, we must reset
// it with the DFA we'd like to use it with.
//
// Similarly, after this reset, using the cache with 'dfa1' is also not
// allowed.
dfa2.reset_cache(&mut cache);
assert_eq!(
    Some(HalfMatch::must(0, 3)),
    dfa2.find_leftmost_fwd(&mut cache, "☃".as_bytes())?,
);

pub fn pattern_count(&self) -> usize

Returns the total number of patterns compiled into this lazy DFA.

In the case of a DFA that contains no patterns, this returns 0.

Example

This example shows the pattern count for a DFA that never matches:

use regex_automata::hybrid::dfa::DFA;

let dfa = DFA::never_match()?;
assert_eq!(dfa.pattern_count(), 0);

And another example for a DFA that matches at every position:

use regex_automata::hybrid::dfa::DFA;

let dfa = DFA::always_match()?;
assert_eq!(dfa.pattern_count(), 1);

And finally, a DFA that was constructed from multiple patterns:

use regex_automata::hybrid::dfa::DFA;

let dfa = DFA::new_many(&["[0-9]+", "[a-z]+", "[A-Z]+"])?;
assert_eq!(dfa.pattern_count(), 3);

pub fn nfa(&self) -> &Arc<NFA>

Returns a reference to the underlying NFA.

pub fn memory_usage(&self) -> usize

Returns the memory usage, in bytes, of this lazy DFA.

This does not include the stack size used up by this lazy DFA. To compute that, use std::mem::size_of::<DFA>(). This also does not include the size of the Cache used.

impl DFA

pub fn find_earliest_fwd(
    &self,
    cache: &mut Cache,
    bytes: &[u8]
) -> Result<Option<HalfMatch>, MatchError>

Executes a forward search and returns the end position of the first match that is found as early as possible. If no match exists, then None is returned.

This routine stops scanning input as soon as the search observes a match state. This is useful for implementing boolean is_match-like routines, where as little work is done as possible.

See DFA::find_earliest_fwd_at for additional functionality, such as providing a prefilter, a specific pattern to match and the bounds of the search within the haystack. This routine is meant as a convenience for common cases where the additional functionality is not needed.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Example

This example demonstrates how the position returned might differ from what one might expect when executing a traditional leftmost search.

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

let dfa = DFA::new("foo[0-9]+")?;
let mut cache = dfa.create_cache();
// Normally, the end of the leftmost first match here would be 8,
// corresponding to the end of the input. But the "earliest" semantics
// this routine cause it to stop as soon as a match is known, which
// occurs once 'foo[0-9]' has matched.
let expected = HalfMatch::must(0, 4);
assert_eq!(
    Some(expected),
    dfa.find_earliest_fwd(&mut cache, b"foo12345")?,
);

let dfa = DFA::new("abc|a")?;
let mut cache = dfa.create_cache();
// Normally, the end of the leftmost first match here would be 3,
// but the shortest match semantics detect a match earlier.
let expected = HalfMatch::must(0, 1);
assert_eq!(Some(expected), dfa.find_earliest_fwd(&mut cache, b"abc")?);

pub fn find_earliest_rev(
    &self,
    cache: &mut Cache,
    bytes: &[u8]
) -> Result<Option<HalfMatch>, MatchError>

Executes a reverse search and returns the start position of the first match that is found as early as possible. If no match exists, then None is returned.

This routine stops scanning input as soon as the search observes a match state.

Note that while it is not technically necessary to build a reverse automaton to use a reverse search, it is likely that you’ll want to do so. Namely, the typical use of a reverse search is to find the starting location of a match once its end is discovered from a forward search. A reverse DFA automaton can be built by configuring the intermediate NFA to be reversed via nfa::thompson::Config::reverse.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Example

This example demonstrates how the position returned might differ from what one might expect when executing a traditional leftmost reverse search.

use regex_automata::{hybrid::dfa::DFA, nfa::thompson, HalfMatch};

let dfa = DFA::builder()
    .thompson(thompson::Config::new().reverse(true))
    .build("[a-z]+[0-9]+")?;
let mut cache = dfa.create_cache();
// Normally, the end of the leftmost first match here would be 0,
// corresponding to the beginning of the input. But the "earliest"
// semantics of this routine cause it to stop as soon as a match is
// known, which occurs once '[a-z][0-9]+' has matched.
let expected = HalfMatch::must(0, 2);
assert_eq!(
    Some(expected),
    dfa.find_earliest_rev(&mut cache, b"foo12345")?,
);

let dfa = DFA::builder()
    .thompson(thompson::Config::new().reverse(true))
    .build("abc|c")?;
let mut cache = dfa.create_cache();
// Normally, the end of the leftmost first match here would be 0,
// but the shortest match semantics detect a match earlier.
let expected = HalfMatch::must(0, 2);
assert_eq!(Some(expected), dfa.find_earliest_rev(&mut cache, b"abc")?);

pub fn find_leftmost_fwd(
    &self,
    cache: &mut Cache,
    bytes: &[u8]
) -> Result<Option<HalfMatch>, MatchError>

Executes a forward search and returns the end position of the leftmost match that is found. If no match exists, then None is returned.

In particular, this method continues searching even after it enters a match state. The search only terminates once it has reached the end of the input or when it has entered a dead or quit state. Upon termination, the position of the last byte seen while still in a match state is returned.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Example

Leftmost first match semantics corresponds to the match with the smallest starting offset, but where the end offset is determined by preferring earlier branches in the original regular expression. For example, Sam|Samwise will match Sam in Samwise, but Samwise|Sam will match Samwise in Samwise.

Generally speaking, the “leftmost first” match is how most backtracking regular expressions tend to work. This is in contrast to POSIX-style regular expressions that yield “leftmost longest” matches. Namely, both Sam|Samwise and Samwise|Sam match Samwise when using leftmost longest semantics. (This crate does not currently support leftmost longest semantics.)

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

let dfa = DFA::new("foo[0-9]+")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 8);
assert_eq!(
    Some(expected),
    dfa.find_leftmost_fwd(&mut cache, b"foo12345")?,
);

// Even though a match is found after reading the first byte (`a`),
// the leftmost first match semantics demand that we find the earliest
// match that prefers earlier parts of the pattern over latter parts.
let dfa = DFA::new("abc|a")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 3);
assert_eq!(Some(expected), dfa.find_leftmost_fwd(&mut cache, b"abc")?);

pub fn find_leftmost_rev(
    &self,
    cache: &mut Cache,
    bytes: &[u8]
) -> Result<Option<HalfMatch>, MatchError>

Executes a reverse search and returns the start of the position of the leftmost match that is found. If no match exists, then None is returned.

In particular, this method continues searching even after it enters a match state. The search only terminates once it has reached the end of the input or when it has entered a dead or quit state. Upon termination, the position of the last byte seen while still in a match state is returned.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Example

In particular, this routine is principally useful when used in conjunction with the [nfa::thompson::Config::reverse](crate::nfa::thompson::Config::revers e) configuration. In general, it’s unlikely to be correct to use both find_leftmost_fwd and find_leftmost_rev with the same DFA since any particular DFA will only support searching in one direction with respect to the pattern.

use regex_automata::{nfa::thompson, hybrid::dfa::DFA, HalfMatch};

let dfa = DFA::builder()
    .thompson(thompson::Config::new().reverse(true))
    .build("foo[0-9]+")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 0);
assert_eq!(
    Some(expected),
    dfa.find_leftmost_rev(&mut cache, b"foo12345")?,
);

// Even though a match is found after reading the last byte (`c`),
// the leftmost first match semantics demand that we find the earliest
// match that prefers earlier parts of the pattern over latter parts.
let dfa = DFA::builder()
    .thompson(thompson::Config::new().reverse(true))
    .build("abc|c")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 0);
assert_eq!(Some(expected), dfa.find_leftmost_rev(&mut cache, b"abc")?);

pub fn find_overlapping_fwd(
    &self,
    cache: &mut Cache,
    bytes: &[u8],
    state: &mut OverlappingState
) -> Result<Option<HalfMatch>, MatchError>

Executes an overlapping forward search and returns the end position of matches as they are found. If no match exists, then None is returned.

This routine is principally only useful when searching for multiple patterns on inputs where multiple patterns may match the same regions of text. In particular, callers must preserve the automaton’s search state from prior calls so that the implementation knows where the last match occurred.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Example

This example shows how to run a basic overlapping search. Notice that we build the automaton with a MatchKind::All configuration. Overlapping searches are unlikely to work as one would expect when using the default MatchKind::LeftmostFirst match semantics, since leftmost-first matching is fundamentally incompatible with overlapping searches. Namely, overlapping searches need to report matches as they are seen, where as leftmost-first searches will continue searching even after a match has been observed in order to find the conventional end position of the match. More concretely, leftmost-first searches use dead states to terminate a search after a specific match can no longer be extended. Overlapping searches instead do the opposite by continuing the search to find totally new matches (potentially of other patterns).

use regex_automata::{
    hybrid::{dfa::DFA, OverlappingState},
    HalfMatch,
    MatchKind,
};

let dfa = DFA::builder()
    .configure(DFA::config().match_kind(MatchKind::All))
    .build_many(&[r"\w+$", r"\S+$"])?;
let mut cache = dfa.create_cache();

let haystack = "@foo".as_bytes();
let mut state = OverlappingState::start();

let expected = Some(HalfMatch::must(1, 4));
let got = dfa.find_overlapping_fwd(&mut cache, haystack, &mut state)?;
assert_eq!(expected, got);

// The first pattern also matches at the same position, so re-running
// the search will yield another match. Notice also that the first
// pattern is returned after the second. This is because the second
// pattern begins its match before the first, is therefore an earlier
// match and is thus reported first.
let expected = Some(HalfMatch::must(0, 4));
let got = dfa.find_overlapping_fwd(&mut cache, haystack, &mut state)?;
assert_eq!(expected, got);

pub fn find_earliest_fwd_at(
    &self,
    cache: &mut Cache,
    pre: Option<&mut Scanner<'_>>,
    pattern_id: Option<PatternID>,
    bytes: &[u8],
    start: usize,
    end: usize
) -> Result<Option<HalfMatch>, MatchError>

Executes a forward search and returns the end position of the first match that is found as early as possible. If no match exists, then None is returned.

This routine stops scanning input as soon as the search observes a match state. This is useful for implementing boolean is_match-like routines, where as little work is done as possible.

This is like DFA::find_earliest_fwd, except it provides some additional control over how the search is executed:

• pre is a prefilter scanner that, when given, is used whenever the DFA enters its starting state. This is meant to speed up searches where one or a small number of literal prefixes are known.
• pattern_id specifies a specific pattern in the DFA to run an anchored search for. If not given, then a search for any pattern is performed. For lazy DFAs, Config::starts_for_each_pattern must be enabled to use this functionality.
• start and end permit searching a specific region of the haystack bytes. This is useful when implementing an iterator over matches within the same haystack, which cannot be done correctly by simply providing a subslice of bytes. (Because the existence of look-around operations such as \b, ^ and $ need to take the surrounding context into account. This cannot be done if the haystack doesn’t contain it.)

The examples below demonstrate each of these additional parameters.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Panics

This routine panics if a pattern_id is given and this lazy DFA does not support specific pattern searches.

It also panics if the given haystack range is not valid.

Example: prefilter

This example shows how to provide a prefilter for a pattern where all matches start with a z byte.

use regex_automata::{
    hybrid::dfa::DFA,
    util::prefilter::{Candidate, Prefilter, Scanner, State},
    HalfMatch,
};

#[derive(Debug)]
pub struct ZPrefilter;

impl Prefilter for ZPrefilter {
    fn next_candidate(
        &self,
        _: &mut State,
        haystack: &[u8],
        at: usize,
    ) -> Candidate {
        // Try changing b'z' to b'q' and observe this test fail since
        // the prefilter will skip right over the match.
        match haystack.iter().position(|&b| b == b'z') {
            None => Candidate::None,
            Some(i) => Candidate::PossibleStartOfMatch(at + i),
        }
    }

    fn heap_bytes(&self) -> usize {
        0
    }
}

let dfa = DFA::new("z[0-9]{3}")?;
let mut cache = dfa.create_cache();

let haystack = "foobar z123 q123".as_bytes();
// A scanner executes a prefilter while tracking some state that helps
// determine whether a prefilter is still "effective" or not.
let mut scanner = Scanner::new(&ZPrefilter);

let expected = Some(HalfMatch::must(0, 11));
let got = dfa.find_earliest_fwd_at(
    &mut cache,
    Some(&mut scanner),
    None,
    haystack,
    0,
    haystack.len(),
)?;
assert_eq!(expected, got);

Example: specific pattern search

This example shows how to build a lazy multi-DFA that permits searching for specific patterns.

use regex_automata::{
    hybrid::dfa::DFA,
    HalfMatch,
    PatternID,
};

let dfa = DFA::builder()
    .configure(DFA::config().starts_for_each_pattern(true))
    .build_many(&["[a-z0-9]{6}", "[a-z][a-z0-9]{5}"])?;
let mut cache = dfa.create_cache();
let haystack = "foo123".as_bytes();

// Since we are using the default leftmost-first match and both
// patterns match at the same starting position, only the first pattern
// will be returned in this case when doing a search for any of the
// patterns.
let expected = Some(HalfMatch::must(0, 6));
let got = dfa.find_earliest_fwd_at(
    &mut cache,
    None,
    None,
    haystack,
    0,
    haystack.len(),
)?;
assert_eq!(expected, got);

// But if we want to check whether some other pattern matches, then we
// can provide its pattern ID.
let expected = Some(HalfMatch::must(1, 6));
let got = dfa.find_earliest_fwd_at(
    &mut cache,
    None,
    Some(PatternID::must(1)),
    haystack,
    0,
    haystack.len(),
)?;
assert_eq!(expected, got);

Example: specifying the bounds of a search

This example shows how providing the bounds of a search can produce different results than simply sub-slicing the haystack.

use regex_automata::{hybrid::dfa::DFA, HalfMatch};

// N.B. We disable Unicode here so that we use a simple ASCII word
// boundary. Alternatively, we could enable heuristic support for
// Unicode word boundaries since our haystack is pure ASCII.
let dfa = DFA::new(r"(?-u)\b[0-9]{3}\b")?;
let mut cache = dfa.create_cache();
let haystack = "foo123bar".as_bytes();

// Since we sub-slice the haystack, the search doesn't know about the
// larger context and assumes that `123` is surrounded by word
// boundaries. And of course, the match position is reported relative
// to the sub-slice as well, which means we get `3` instead of `6`.
let expected = Some(HalfMatch::must(0, 3));
let got = dfa.find_earliest_fwd_at(
    &mut cache,
    None,
    None,
    &haystack[3..6],
    0,
    haystack[3..6].len(),
)?;
assert_eq!(expected, got);

// But if we provide the bounds of the search within the context of the
// entire haystack, then the search can take the surrounding context
// into account. (And if we did find a match, it would be reported
// as a valid offset into `haystack` instead of its sub-slice.)
let expected = None;
let got = dfa.find_earliest_fwd_at(
    &mut cache,
    None,
    None,
    haystack,
    3,
    6,
)?;
assert_eq!(expected, got);

pub fn find_earliest_rev_at(
    &self,
    cache: &mut Cache,
    pattern_id: Option<PatternID>,
    bytes: &[u8],
    start: usize,
    end: usize
) -> Result<Option<HalfMatch>, MatchError>

Executes a reverse search and returns the start position of the first match that is found as early as possible. If no match exists, then None is returned.

This routine stops scanning input as soon as the search observes a match state.

This is like DFA::find_earliest_rev, except it provides some additional control over how the search is executed. See the documentation of DFA::find_earliest_fwd_at for more details on the additional parameters along with examples of their usage.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Panics

This routine panics if a pattern_id is given and the underlying DFA does not support specific pattern searches.

It also panics if the given haystack range is not valid.

pub fn find_leftmost_fwd_at(
    &self,
    cache: &mut Cache,
    pre: Option<&mut Scanner<'_>>,
    pattern_id: Option<PatternID>,
    bytes: &[u8],
    start: usize,
    end: usize
) -> Result<Option<HalfMatch>, MatchError>

Executes a forward search and returns the end position of the leftmost match that is found. If no match exists, then None is returned.

This is like DFA::find_leftmost_fwd, except it provides some additional control over how the search is executed. See the documentation of DFA::find_earliest_fwd_at for more details on the additional parameters along with examples of their usage.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Panics

This routine panics if a pattern_id is given and the underlying DFA does not support specific pattern searches.

It also panics if the given haystack range is not valid.

pub fn find_leftmost_rev_at(
    &self,
    cache: &mut Cache,
    pattern_id: Option<PatternID>,
    bytes: &[u8],
    start: usize,
    end: usize
) -> Result<Option<HalfMatch>, MatchError>

Executes a reverse search and returns the start of the position of the leftmost match that is found. If no match exists, then None is returned.

This is like DFA::find_leftmost_rev, except it provides some additional control over how the search is executed. See the documentation of DFA::find_earliest_fwd_at for more details on the additional parameters along with examples of their usage.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Panics

This routine panics if a pattern_id is given and the underlying DFA does not support specific pattern searches.

It also panics if the given haystack range is not valid.

pub fn find_overlapping_fwd_at(
    &self,
    cache: &mut Cache,
    pre: Option<&mut Scanner<'_>>,
    pattern_id: Option<PatternID>,
    bytes: &[u8],
    start: usize,
    end: usize,
    state: &mut OverlappingState
) -> Result<Option<HalfMatch>, MatchError>

Executes an overlapping forward search and returns the end position of matches as they are found. If no match exists, then None is returned.

This routine is principally only useful when searching for multiple patterns on inputs where multiple patterns may match the same regions of text. In particular, callers must preserve the automaton’s search state from prior calls so that the implementation knows where the last match occurred.

This is like DFA::find_overlapping_fwd, except it provides some additional control over how the search is executed. See the documentation of DFA::find_earliest_fwd_at for more details on the additional parameters along with examples of their usage.

When using this routine to implement an iterator of overlapping matches, the start of the search should always be set to the end of the last match. If more patterns match at the previous location, then they will be immediately returned. (This is tracked by the given overlapping state.) Otherwise, the search continues at the starting position given.

If for some reason you want the search to forget about its previous state and restart the search at a particular position, then setting the state to OverlappingState::start will accomplish that.

Errors

This routine only errors if the search could not complete. For lazy DFAs generated by this crate, this only occurs in non-default configurations where quit bytes are used, Unicode word boundaries are heuristically enabled or limits are set on the number of times the lazy DFA’s cache may be cleared.

When a search cannot complete, callers cannot know whether a match exists or not.

Panics

This routine panics if a pattern_id is given and the underlying DFA does not support specific pattern searches.

It also panics if the given haystack range is not valid.

impl DFA

pub fn next_state(
    &self,
    cache: &mut Cache,
    current: LazyStateID,
    input: u8
) -> Result<LazyStateID, CacheError>

Transitions from the current state to the next state, given the next byte of input.

The given cache is used to either reuse pre-computed state transitions, or to store this newly computed transition for future reuse. Thus, this routine guarantees that it will never return a state ID that has an “unknown” tag.

State identifier validity

The only valid value for current is the lazy state ID returned by the most recent call to next_state, next_state_untagged, next_state_untagged_unchecked, start_state_forward or state_state_reverse for the given cache. Any state ID returned from prior calls to these routines (with the same cache) is considered invalid (even if it gives an appearance of working). State IDs returned from any prior call for different cache values are also always invalid.

The returned ID is always a valid ID when current refers to a valid ID. Moreover, this routine is defined for all possible values of input.

These validity rules are not checked, even in debug mode. Callers are required to uphold these rules themselves.

Violating these state ID validity rules will not sacrifice memory safety, but may produce an incorrect result or a panic.

Panics

If the given ID does not refer to a valid state, then this routine may panic but it also may not panic and instead return an invalid or incorrect ID.

Example

This shows a simplistic example for walking a lazy DFA for a given haystack by using the next_state method.

use regex_automata::hybrid::dfa::DFA;

let dfa = DFA::new(r"[a-z]+r")?;
let mut cache = dfa.create_cache();
let haystack = "bar".as_bytes();

// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut sid = dfa.start_state_forward(
    &mut cache, None, haystack, 0, haystack.len(),
)?;
// Walk all the bytes in the haystack.
for &b in haystack {
    sid = dfa.next_state(&mut cache, sid, b)?;
}
// Matches are always delayed by 1 byte, so we must explicitly walk the
// special "EOI" transition at the end of the search.
sid = dfa.next_eoi_state(&mut cache, sid)?;
assert!(sid.is_match());

pub fn next_state_untagged(
    &self,
    cache: &Cache,
    current: LazyStateID,
    input: u8
) -> LazyStateID

Transitions from the current state to the next state, given the next byte of input and a state ID that is not tagged.

The only reason to use this routine is performance. In particular, the next_state method needs to do some additional checks, among them is to account for identifiers to states that are not yet computed. In such a case, the transition is computed on the fly. However, if it is known that the current state ID is untagged, then these checks can be omitted.

Since this routine does not compute states on the fly, it does not modify the cache and thus cannot return an error. Consequently, cache does not need to be mutable and it is possible for this routine to return a state ID corresponding to the special “unknown” state. In this case, it is the caller’s responsibility to use the prior state ID and input with next_state in order to force the computation of the unknown transition. Otherwise, trying to use the “unknown” state ID will just result in transitioning back to itself, and thus never terminating. (This is technically a special exemption to the state ID validity rules, but is permissible since this routine is guarateed to never mutate the given cache, and thus the identifier is guaranteed to remain valid.)

See LazyStateID for more details on what it means for a state ID to be tagged. Also, see next_state_untagged_unchecked for this same idea, but with bounds checks forcefully elided.

State identifier validity

The only valid value for current is an untagged lazy state ID returned by the most recent call to next_state, next_state_untagged, next_state_untagged_unchecked, start_state_forward or state_state_reverse for the given cache. Any state ID returned from prior calls to these routines (with the same cache) is considered invalid (even if it gives an appearance of working). State IDs returned from any prior call for different cache values are also always invalid.

The returned ID is always a valid ID when current refers to a valid ID, although it may be tagged. Moreover, this routine is defined for all possible values of input.

Not all validity rules are checked, even in debug mode. Callers are required to uphold these rules themselves.

Violating these state ID validity rules will not sacrifice memory safety, but may produce an incorrect result or a panic.

Panics

If the given ID does not refer to a valid state, then this routine may panic but it also may not panic and instead return an invalid or incorrect ID.

Example

This shows a simplistic example for walking a lazy DFA for a given haystack by using the next_state_untagged method where possible.

use regex_automata::hybrid::dfa::DFA;

let dfa = DFA::new(r"[a-z]+r")?;
let mut cache = dfa.create_cache();
let haystack = "bar".as_bytes();

// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut sid = dfa.start_state_forward(
    &mut cache, None, haystack, 0, haystack.len(),
)?;
// Walk all the bytes in the haystack.
let mut at = 0;
while at < haystack.len() {
    if sid.is_tagged() {
        sid = dfa.next_state(&mut cache, sid, haystack[at])?;
    } else {
        let mut prev_sid = sid;
        // We attempt to chew through as much as we can while moving
        // through untagged state IDs. Thus, the transition function
        // does less work on average per byte. (Unrolling this loop
        // may help even more.)
        while at < haystack.len() {
            prev_sid = sid;
            sid = dfa.next_state_untagged(
                &mut cache, sid, haystack[at],
            );
            at += 1;
            if sid.is_tagged() {
                break;
            }
        }
        // We must ensure that we never proceed to the next iteration
        // with an unknown state ID. If we don't account for this
        // case, then search isn't guaranteed to terminate since all
        // transitions on unknown states loop back to itself.
        if sid.is_unknown() {
            sid = dfa.next_state(
                &mut cache, prev_sid, haystack[at - 1],
            )?;
        }
    }
}
// Matches are always delayed by 1 byte, so we must explicitly walk the
// special "EOI" transition at the end of the search.
sid = dfa.next_eoi_state(&mut cache, sid)?;
assert!(sid.is_match());

pub unsafe fn next_state_untagged_unchecked(
    &self,
    cache: &Cache,
    current: LazyStateID,
    input: u8
) -> LazyStateID

Transitions from the current state to the next state, eliding bounds checks, given the next byte of input and a state ID that is not tagged.

The only reason to use this routine is performance. In particular, the next_state method needs to do some additional checks, among them is to account for identifiers to states that are not yet computed. In such a case, the transition is computed on the fly. However, if it is known that the current state ID is untagged, then these checks can be omitted.

Since this routine does not compute states on the fly, it does not modify the cache and thus cannot return an error. Consequently, cache does not need to be mutable and it is possible for this routine to return a state ID corresponding to the special “unknown” state. In this case, it is the caller’s responsibility to use the prior state ID and input with next_state in order to force the computation of the unknown transition. Otherwise, trying to use the “unknown” state ID will just result in transitioning back to itself, and thus never terminating. (This is technically a special exemption to the state ID validity rules, but is permissible since this routine is guarateed to never mutate the given cache, and thus the identifier is guaranteed to remain valid.)

See LazyStateID for more details on what it means for a state ID to be tagged. Also, see next_state_untagged for this same idea, but with memory safety guaranteed by retaining bounds checks.

State identifier validity

The only valid value for current is an untagged lazy state ID returned by the most recent call to next_state, next_state_untagged, next_state_untagged_unchecked, start_state_forward or state_state_reverse for the given cache. Any state ID returned from prior calls to these routines (with the same cache) is considered invalid (even if it gives an appearance of working). State IDs returned from any prior call for different cache values are also always invalid.

The returned ID is always a valid ID when current refers to a valid ID, although it may be tagged. Moreover, this routine is defined for all possible values of input.

Not all validity rules are checked, even in debug mode. Callers are required to uphold these rules themselves.

Violating these state ID validity rules will not sacrifice memory safety, but may produce an incorrect result or a panic.

Safety

Callers of this method must guarantee that current refers to a valid state ID according to the rules described above. If current is not a valid state ID for this automaton, then calling this routine may result in undefined behavior.

If current is valid, then the ID returned is valid for all possible values of input.

pub fn next_eoi_state(
    &self,
    cache: &mut Cache,
    current: LazyStateID
) -> Result<LazyStateID, CacheError>

Transitions from the current state to the next state for the special EOI symbol.

The given cache is used to either reuse pre-computed state transitions, or to store this newly computed transition for future reuse. Thus, this routine guarantees that it will never return a state ID that has an “unknown” tag.

This routine must be called at the end of every search in a correct implementation of search. Namely, lazy DFAs in this crate delay matches by one byte in order to support look-around operators. Thus, after reaching the end of a haystack, a search implementation must follow one last EOI transition.

It is best to think of EOI as an additional symbol in the alphabet of a DFA that is distinct from every other symbol. That is, the alphabet of lazy DFAs in this crate has a logical size of 257 instead of 256, where 256 corresponds to every possible inhabitant of u8. (In practice, the physical alphabet size may be smaller because of alphabet compression via equivalence classes, but EOI is always represented somehow in the alphabet.)

State identifier validity

The only valid value for current is the lazy state ID returned by the most recent call to next_state, next_state_untagged, next_state_untagged_unchecked, start_state_forward or state_state_reverse for the given cache. Any state ID returned from prior calls to these routines (with the same cache) is considered invalid (even if it gives an appearance of working). State IDs returned from any prior call for different cache values are also always invalid.

The returned ID is always a valid ID when current refers to a valid ID.

These validity rules are not checked, even in debug mode. Callers are required to uphold these rules themselves.

Violating these state ID validity rules will not sacrifice memory safety, but may produce an incorrect result or a panic.

Panics

If the given ID does not refer to a valid state, then this routine may panic but it also may not panic and instead return an invalid or incorrect ID.

Example

This shows a simplistic example for walking a DFA for a given haystack, and then finishing the search with the final EOI transition.

use regex_automata::hybrid::dfa::DFA;

let dfa = DFA::new(r"[a-z]+r")?;
let mut cache = dfa.create_cache();
let haystack = "bar".as_bytes();

// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut sid = dfa.start_state_forward(
    &mut cache, None, haystack, 0, haystack.len(),
)?;
// Walk all the bytes in the haystack.
for &b in haystack {
    sid = dfa.next_state(&mut cache, sid, b)?;
}
// Matches are always delayed by 1 byte, so we must explicitly walk
// the special "EOI" transition at the end of the search. Without this
// final transition, the assert below will fail since the DFA will not
// have entered a match state yet!
sid = dfa.next_eoi_state(&mut cache, sid)?;
assert!(sid.is_match());

pub fn start_state_forward(
    &self,
    cache: &mut Cache,
    pattern_id: Option<PatternID>,
    bytes: &[u8],
    start: usize,
    end: usize
) -> Result<LazyStateID, CacheError>

Return the ID of the start state for this lazy DFA when executing a forward search.

Unlike typical DFA implementations, the start state for DFAs in this crate is dependent on a few different factors:

• The pattern ID, if present. When the underlying DFA has been configured with multiple patterns and the DFA has been configured to build an anchored start state for each pattern, then a pattern ID may be specified to execute an anchored search for that specific pattern. If pattern_id is invalid or if the DFA isn’t configured to build start states for each pattern, then implementations must panic. DFAs in this crate can be configured to build start states for each pattern via Config::starts_for_each_pattern.
• When start > 0, the byte at index start - 1 may influence the start state if the regex uses ^ or \b.
• Similarly, when start == 0, it may influence the start state when the regex uses ^ or \A.
• Currently, end is unused.
• Whether the search is a forward or reverse search. This routine can only be used for forward searches.

Panics

This panics if start..end is not a valid sub-slice of bytes. This also panics if pattern_id is non-None and does not refer to a valid pattern, or if the DFA was not configured to build anchored start states for each pattern.

pub fn start_state_reverse(
    &self,
    cache: &mut Cache,
    pattern_id: Option<PatternID>,
    bytes: &[u8],
    start: usize,
    end: usize
) -> Result<LazyStateID, CacheError>

Return the ID of the start state for this lazy DFA when executing a reverse search.

Unlike typical DFA implementations, the start state for DFAs in this crate is dependent on a few different factors:

• The pattern ID, if present. When the underlying DFA has been configured with multiple patterns and the DFA has been configured to build an anchored start state for each pattern, then a pattern ID may be specified to execute an anchored search for that specific pattern. If pattern_id is invalid or if the DFA isn’t configured to build start states for each pattern, then implementations must panic. DFAs in this crate can be configured to build start states for each pattern via Config::starts_for_each_pattern.
• When end < bytes.len(), the byte at index end may influence the start state if the regex uses $ or \b.
• Similarly, when end == bytes.len(), it may influence the start state when the regex uses $ or \z.
• Currently, start is unused.
• Whether the search is a forward or reverse search. This routine can only be used for reverse searches.

Panics

This panics if start..end is not a valid sub-slice of bytes. This also panics if pattern_id is non-None and does not refer to a valid pattern, or if the DFA was not configured to build anchored start states for each pattern.

pub fn match_count(&self, cache: &Cache, id: LazyStateID) -> usize

Returns the total number of patterns that match in this state.

If the lazy DFA was compiled with one pattern, then this must necessarily always return 1 for all match states.

A lazy DFA guarantees that DFA::match_pattern can be called with indices up to (but not including) the count returned by this routine without panicking.

If the given state is not a match state, then this may either panic or return an incorrect result.

Example

This example shows a simple instance of implementing overlapping matches. In particular, it shows not only how to determine how many patterns have matched in a particular state, but also how to access which specific patterns have matched.

Notice that we must use MatchKind::All when building the DFA. If we used MatchKind::LeftmostFirst instead, then the DFA would not be constructed in a way that supports overlapping matches. (It would only report a single pattern that matches at any particular point in time.)

Another thing to take note of is the patterns used and the order in which the pattern IDs are reported. In the example below, pattern 3 is yielded first. Why? Because it corresponds to the match that appears first. Namely, the @ symbol is part of \S+ but not part of any of the other patterns. Since the \S+ pattern has a match that starts to the left of any other pattern, its ID is returned before any other.

use regex_automata::{hybrid::dfa::DFA, MatchKind};

let dfa = DFA::builder()
    .configure(DFA::config().match_kind(MatchKind::All))
    .build_many(&[
        r"\w+", r"[a-z]+", r"[A-Z]+", r"\S+",
    ])?;
let mut cache = dfa.create_cache();
let haystack = "@bar".as_bytes();

// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut sid = dfa.start_state_forward(
    &mut cache, None, haystack, 0, haystack.len(),
)?;
// Walk all the bytes in the haystack.
for &b in haystack {
    sid = dfa.next_state(&mut cache, sid, b)?;
}
sid = dfa.next_eoi_state(&mut cache, sid)?;

assert!(sid.is_match());
assert_eq!(dfa.match_count(&mut cache, sid), 3);
// The following calls are guaranteed to not panic since `match_count`
// returned `3` above.
assert_eq!(dfa.match_pattern(&mut cache, sid, 0).as_usize(), 3);
assert_eq!(dfa.match_pattern(&mut cache, sid, 1).as_usize(), 0);
assert_eq!(dfa.match_pattern(&mut cache, sid, 2).as_usize(), 1);

pub fn match_pattern(
    &self,
    cache: &Cache,
    id: LazyStateID,
    match_index: usize
) -> PatternID

Returns the pattern ID corresponding to the given match index in the given state.

See DFA::match_count for an example of how to use this method correctly. Note that if you know your lazy DFA is configured with a single pattern, then this routine is never necessary since it will always return a pattern ID of 0 for an index of 0 when id corresponds to a match state.

Typically, this routine is used when implementing an overlapping search, as the example for DFA::match_count does.

Panics

If the state ID is not a match state or if the match index is out of bounds for the given state, then this routine may either panic or produce an incorrect result. If the state ID is correct and the match index is correct, then this routine always produces a valid PatternID.

Trait Implementations

impl Clone for DFA

fn clone(&self) -> DFA

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for DFA

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

Formats the value using the given formatter.