Trait regex_automata::dfa::Automaton

source · [−]
pub unsafe trait Automaton {

Show 25 methods    fn next_state(&self, current: StateID, input: u8) -> StateID;

    unsafe fn next_state_unchecked(
        &self, 
        current: StateID, 
        input: u8
    ) -> StateID;

    fn next_eoi_state(&self, current: StateID) -> StateID;

    fn start_state_forward(
        &self, 
        pattern_id: Option<PatternID>, 
        bytes: &[u8], 
        start: usize, 
        end: usize
    ) -> StateID;

    fn start_state_reverse(
        &self, 
        pattern_id: Option<PatternID>, 
        bytes: &[u8], 
        start: usize, 
        end: usize
    ) -> StateID;

    fn is_special_state(&self, id: StateID) -> bool;

    fn is_dead_state(&self, id: StateID) -> bool;

    fn is_quit_state(&self, id: StateID) -> bool;

    fn is_match_state(&self, id: StateID) -> bool;

    fn is_start_state(&self, id: StateID) -> bool;

    fn is_accel_state(&self, id: StateID) -> bool;

    fn pattern_count(&self) -> usize;

    fn match_count(&self, id: StateID) -> usize;

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

    fn accelerator(&self, _id: StateID) -> &[u8]ⓘNotable traits for &'_ [u8]impl<'_> Read for &'_ [u8]impl<'_> Write for &'_ mut [u8] { ... }

    fn find_earliest_fwd(
        &self, 
        bytes: &[u8]
    ) -> Result<Option<HalfMatch>, MatchError> { ... }

    fn find_earliest_rev(
        &self, 
        bytes: &[u8]
    ) -> Result<Option<HalfMatch>, MatchError> { ... }

    fn find_leftmost_fwd(
        &self, 
        bytes: &[u8]
    ) -> Result<Option<HalfMatch>, MatchError> { ... }

    fn find_leftmost_rev(
        &self, 
        bytes: &[u8]
    ) -> Result<Option<HalfMatch>, MatchError> { ... }

    fn find_overlapping_fwd(
        &self, 
        bytes: &[u8], 
        state: &mut OverlappingState
    ) -> Result<Option<HalfMatch>, MatchError> { ... }

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

    fn find_earliest_rev_at(
        &self, 
        pattern_id: Option<PatternID>, 
        bytes: &[u8], 
        start: usize, 
        end: usize
    ) -> Result<Option<HalfMatch>, MatchError> { ... }

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

    fn find_leftmost_rev_at(
        &self, 
        pattern_id: Option<PatternID>, 
        bytes: &[u8], 
        start: usize, 
        end: usize
    ) -> Result<Option<HalfMatch>, MatchError> { ... }

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

}
Expand description

A trait describing the interface of a deterministic finite automaton (DFA).

The complexity of this trait probably means that it’s unlikely for others to implement it. The primary purpose of the trait is to provide for a way of abstracting over different types of DFAs. In this crate, that means dense DFAs and sparse DFAs. (Dense DFAs are fast but memory hungry, where as sparse DFAs are slower but come with a smaller memory footprint. But they otherwise provide exactly equivalent expressive power.) For example, a dfa::regex::Regex is generic over this trait.

Normally, a DFA’s execution model is very simple. You might have a single start state, zero or more final or “match” states and a function that transitions from one state to the next given the next byte of input. Unfortunately, the interface described by this trait is significantly more complicated than this. The complexity has a number of different reasons, mostly motivated by performance, functionality or space savings:

  • A DFA can search for multiple patterns simultaneously. This means extra information is returned when a match occurs. Namely, a match is not just an offset, but an offset plus a pattern ID. Automaton::pattern_count returns the number of patterns compiled into the DFA, Automaton::match_count returns the total number of patterns that match in a particular state and Automaton::match_pattern permits iterating over the patterns that match in a particular state.
  • A DFA can have multiple start states, and the choice of which start state to use depends on the content of the string being searched and position of the search, as well as whether the search is an anchored search for a specific pattern in the DFA. Moreover, computing the start state also depends on whether you’re doing a forward or a reverse search. Automaton::start_state_forward and Automaton::start_state_reverse are used to compute the start state for forward and reverse searches, respectively.
  • All matches are delayed by one byte to support things like $ and \b at the end of a pattern. Therefore, every use of a DFA is required to use Automaton::next_eoi_state at the end of the search to compute the final transition.
  • For optimization reasons, some states are treated specially. Every state is either special or not, which can be determined via the Automaton::is_special_state method. If it’s special, then the state must be at least one of a few possible types of states. (Note that some types can overlap, for example, a match state can also be an accel state. But some types can’t. If a state is a dead state, then it can never be any other type of state.) Those types are:
    • A dead state. A dead state means the DFA will never enter a match state. This can be queried via the Automaton::is_dead_state method.
    • A quit state. A quit state occurs if the DFA had to stop the search prematurely for some reason. This can be queried via the Automaton::is_quit_state method.
    • A match state. A match state occurs when a match is found. When a DFA enters a match state, the search may stop immediately (when looking for the earliest match), or it may continue to find the leftmost-first match. This can be queried via the Automaton::is_match_state method.
    • A start state. A start state is where a search begins. For every search, there is exactly one start state that is used, however, a DFA may contain many start states. When the search is in a start state, it may use a prefilter to quickly skip to candidate matches without executing the DFA on every byte. This can be queried via the Automaton::is_start_state method.
    • An accel state. An accel state is a state that is accelerated. That is, it is a state where most of its transitions loop back to itself and only a small number of transitions lead to other states. This kind of state is said to be accelerated because a search routine can quickly look for the bytes leading out of the state instead of continuing to execute the DFA on each byte. This can be queried via the Automaton::is_accel_state method. And the bytes that lead out of the state can be queried via the Automaton::accelerator method.

There are a number of provided methods on this trait that implement efficient searching (for forwards and backwards) with a DFA using all of the above features of this trait. In particular, given the complexity of all these features, implementing a search routine in this trait is not straight forward. If you need to do this for specialized reasons, then it’s recommended to look at the source of this crate. It is intentionally well commented to help with this. With that said, it is possible to somewhat simplify the search routine. For example, handling accelerated states is strictly optional, since it is always correct to assume that Automaton::is_accel_state returns false. However, one complex part of writing a search routine using this trait is handling the 1-byte delay of a match. That is not optional.

Safety

This trait is unsafe to implement because DFA searching may rely on the correctness of the implementation for memory safety. For example, DFA searching may use explicit bounds check elision, which will in turn rely on the correctness of every function that returns a state ID.

When implementing this trait, one must uphold the documented correctness guarantees. Otherwise, undefined behavior may occur.

Required methods

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

Implementations must guarantee that the returned ID is always a valid ID when current refers to a valid ID. Moreover, the transition function must be defined for all possible values of input.

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 ID. However, if the caller provides an invalid ID then this must never sacrifice memory safety.

Example

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

use regex_automata::dfa::{Automaton, dense};

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

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

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

Unlike Automaton::next_state, implementations may implement this more efficiently by assuming that the current state ID is valid. Typically, this manifests by eliding bounds checks.

Safety

Callers of this method must guarantee that current refers to a valid state ID. 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 implementations must guarantee that the ID returned is valid for all possible values of input.

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

Implementations must guarantee that the returned ID is always a valid ID when current refers to a valid ID.

This routine must be called at the end of every search in a correct implementation of search. Namely, 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 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.)

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 ID. However, if the caller provides an invalid ID then this must never sacrifice memory safety.

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::dfa::{Automaton, dense};

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

// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut state = dfa.start_state_forward(
    None, haystack, 0, haystack.len(),
);
// Walk all the bytes in the haystack.
for &b in haystack {
    state = dfa.next_state(state, 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!
state = dfa.next_eoi_state(state);
assert!(dfa.is_match_state(state));

Return the ID of the start state for this 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 compiled with multiple patterns and the DFA has been configured to compile 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 doesn’t have start states compiled for each pattern, then implementations must panic. DFAs in this crate can be configured to compile start states for each pattern via dense::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

Implementations must panic if start..end is not a valid sub-slice of bytes. Implementations must also panic if pattern_id is non-None and does not refer to a valid pattern, or if the DFA was not compiled with anchored start states for each pattern.

Return the ID of the start state for this 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 compiled with multiple patterns and the DFA has been configured to compile 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 doesn’t have start states compiled for each pattern, then implementations must panic. DFAs in this crate can be configured to compile start states for each pattern via dense::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

Implementations must panic if start..end is not a valid sub-slice of bytes. Implementations must also panic if pattern_id is non-None and does not refer to a valid pattern, or if the DFA was not compiled with anchored start states for each pattern.

Returns true if and only if the given identifier corresponds to a “special” state. A special state is one or more of the following: a dead state, a quit state, a match state, a start state or an accelerated state.

A correct implementation may always return false for states that are either start states or accelerated states, since that information is only intended to be used for optimization purposes. Correct implementations must return true if the state is a dead, quit or match state. This is because search routines using this trait must be able to rely on is_special_state as an indicator that a state may need special treatment. (For example, when a search routine sees a dead state, it must terminate.)

This routine permits search implementations to use a single branch to check whether a state needs special attention before executing the next transition. The example below shows how to do this.

Example

This example shows how is_special_state can be used to implement a correct search routine with minimal branching. In particular, this search routine implements “leftmost” matching, which means that it doesn’t immediately stop once a match is found. Instead, it continues until it reaches a dead state.

use regex_automata::{
    dfa::{Automaton, dense},
    HalfMatch, MatchError, PatternID,
};

fn find_leftmost_first<A: Automaton>(
    dfa: &A,
    haystack: &[u8],
) -> Result<Option<HalfMatch>, MatchError> {
    // The start state is determined by inspecting the position and the
    // initial bytes of the haystack. Note that start states can never
    // be match states (since DFAs in this crate delay matches by 1
    // byte), so we don't need to check if the start state is a match.
    let mut state = dfa.start_state_forward(
        None, haystack, 0, haystack.len(),
    );
    let mut last_match = None;
    // Walk all the bytes in the haystack. We can quit early if we see
    // a dead or a quit state. The former means the automaton will
    // never transition to any other state. The latter means that the
    // automaton entered a condition in which its search failed.
    for (i, &b) in haystack.iter().enumerate() {
        state = dfa.next_state(state, b);
        if dfa.is_special_state(state) {
            if dfa.is_match_state(state) {
                last_match = Some(HalfMatch::new(
                    dfa.match_pattern(state, 0),
                    i,
                ));
            } else if dfa.is_dead_state(state) {
                return Ok(last_match);
            } else if dfa.is_quit_state(state) {
                // It is possible to enter into a quit state after
                // observing a match has occurred. In that case, we
                // should return the match instead of an error.
                if last_match.is_some() {
                    return Ok(last_match);
                }
                return Err(MatchError::Quit { byte: b, offset: i });
            }
            // Implementors may also want to check for start or accel
            // states and handle them differently for performance
            // reasons. But it is not necessary for correctness.
        }
    }
    // Matches are always delayed by 1 byte, so we must explicitly walk
    // the special "EOI" transition at the end of the search.
    state = dfa.next_eoi_state(state);
    if dfa.is_match_state(state) {
        last_match = Some(HalfMatch::new(
            dfa.match_pattern(state, 0),
            haystack.len(),
        ));
    }
    Ok(last_match)
}

// We use a greedy '+' operator to show how the search doesn't just
// stop once a match is detected. It continues extending the match.
// Using '[a-z]+?' would also work as expected and stop the search
// early. Greediness is built into the automaton.
let dfa = dense::DFA::new(r"[a-z]+")?;
let haystack = "123 foobar 4567".as_bytes();
let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
assert_eq!(mat.pattern().as_usize(), 0);
assert_eq!(mat.offset(), 10);

// Here's another example that tests our handling of the special EOI
// transition. This will fail to find a match if we don't call
// 'next_eoi_state' at the end of the search since the match isn't
// found until the final byte in the haystack.
let dfa = dense::DFA::new(r"[0-9]{4}")?;
let haystack = "123 foobar 4567".as_bytes();
let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
assert_eq!(mat.pattern().as_usize(), 0);
assert_eq!(mat.offset(), 15);

// And note that our search implementation above automatically works
// with multi-DFAs. Namely, `dfa.match_pattern(match_state, 0)` selects
// the appropriate pattern ID for us.
let dfa = dense::DFA::new_many(&[r"[a-z]+", r"[0-9]+"])?;
let haystack = "123 foobar 4567".as_bytes();
let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
assert_eq!(mat.pattern().as_usize(), 1);
assert_eq!(mat.offset(), 3);
let mat = find_leftmost_first(&dfa, &haystack[3..])?.unwrap();
assert_eq!(mat.pattern().as_usize(), 0);
assert_eq!(mat.offset(), 7);
let mat = find_leftmost_first(&dfa, &haystack[10..])?.unwrap();
assert_eq!(mat.pattern().as_usize(), 1);
assert_eq!(mat.offset(), 5);

Returns true if and only if the given identifier corresponds to a dead state. When a DFA enters a dead state, it is impossible to leave. That is, every transition on a dead state by definition leads back to the same dead state.

In practice, the dead state always corresponds to the identifier 0. Moreover, in practice, there is only one dead state.

The existence of a dead state is not strictly required in the classical model of finite state machines, where one generally only cares about the question of whether an input sequence matches or not. Dead states are not needed to answer that question, since one can immediately quit as soon as one enters a final or “match” state. However, we don’t just care about matches but also care about the location of matches, and more specifically, care about semantics like “greedy” matching.

For example, given the pattern a+ and the input aaaz, the dead state won’t be entered until the state machine reaches z in the input, at which point, the search routine can quit. But without the dead state, the search routine wouldn’t know when to quit. In a classical representation, the search routine would stop after seeing the first a (which is when the search would enter a match state). But this wouldn’t implement “greedy” matching where a+ matches as many a’s as possible.

Example

See the example for Automaton::is_special_state for how to use this method correctly.

Returns true if and only if the given identifier corresponds to a quit state. A quit state is like a dead state (it has no transitions other than to itself), except it indicates that the DFA failed to complete the search. When this occurs, callers can neither accept or reject that a match occurred.

In practice, the quit state always corresponds to the state immediately following the dead state. (Which is not usually represented by 1, since state identifiers are pre-multiplied by the state machine’s alphabet stride, and the alphabet stride varies between DFAs.)

By default, state machines created by this crate will never enter a quit state. Since entering a quit state is the only way for a DFA in this crate to fail at search time, it follows that the default configuration can never produce a match error. Nevertheless, handling quit states is necessary to correctly support all configurations in this crate.

The typical way in which a quit state can occur is when heuristic support for Unicode word boundaries is enabled via the dense::Config::unicode_word_boundary option. But other options, like the lower level dense::Config::quit configuration, can also result in a quit state being entered. The purpose of the quit state is to provide a way to execute a fast DFA in common cases while delegating to slower routines when the DFA quits.

The default search implementations provided by this crate will return a MatchError::Quit error when a quit state is entered.

Example

See the example for Automaton::is_special_state for how to use this method correctly.

Returns true if and only if the given identifier corresponds to a match state. A match state is also referred to as a “final” state and indicates that a match has been found.

If all you care about is whether a particular pattern matches in the input sequence, then a search routine can quit early as soon as the machine enters a match state. However, if you’re looking for the standard “leftmost-first” match location, then search must continue until either the end of the input or until the machine enters a dead state. (Since either condition implies that no other useful work can be done.) Namely, when looking for the location of a match, then search implementations should record the most recent location in which a match state was entered, but otherwise continue executing the search as normal. (The search may even leave the match state.) Once the termination condition is reached, the most recently recorded match location should be returned.

Finally, one additional power given to match states in this crate is that they are always associated with a specific pattern in order to support multi-DFAs. See Automaton::match_pattern for more details and an example for how to query the pattern associated with a particular match state.

Example

See the example for Automaton::is_special_state for how to use this method correctly.

Returns true if and only if the given identifier corresponds to a start state. A start state is a state in which a DFA begins a search. All searches begin in a start state. Moreover, since all matches are delayed by one byte, a start state can never be a match state.

The main role of a start state is, as mentioned, to be a starting point for a DFA. This starting point is determined via one of Automaton::start_state_forward or Automaton::start_state_reverse, depending on whether one is doing a forward or a reverse search, respectively.

A secondary use of start states is for prefix acceleration. Namely, while executing a search, if one detects that you’re in a start state, then it may be faster to look for the next match of a prefix of the pattern, if one exists. If a prefix exists and since all matches must begin with that prefix, then skipping ahead to occurrences of that prefix may be much faster than executing the DFA.

Example

This example shows how to implement your own search routine that does a prefix search whenever the search enters a start state.

Note that you do not need to implement your own search routine to make use of prefilters like this. The search routines provided by this crate already implement prefilter support via the Prefilter trait. The various find_*_at routines on this trait support the Prefilter trait through Scanners. This example is meant to show how you might deal with prefilters in a simplified case if you are implementing your own search routine.

use regex_automata::{
    MatchError, PatternID,
    dfa::{Automaton, dense},
    HalfMatch,
};

fn find_byte(slice: &[u8], at: usize, byte: u8) -> Option<usize> {
    // Would be faster to use the memchr crate, but this is still
    // faster than running through the DFA.
    slice[at..].iter().position(|&b| b == byte).map(|i| at + i)
}

fn find_leftmost_first<A: Automaton>(
    dfa: &A,
    haystack: &[u8],
    prefix_byte: Option<u8>,
) -> Result<Option<HalfMatch>, MatchError> {
    // See the Automaton::is_special_state example for similar code
    // with more comments.

    let mut state = dfa.start_state_forward(
        None, haystack, 0, haystack.len(),
    );
    let mut last_match = None;
    let mut pos = 0;
    while pos < haystack.len() {
        let b = haystack[pos];
        state = dfa.next_state(state, b);
        pos += 1;
        if dfa.is_special_state(state) {
            if dfa.is_match_state(state) {
                last_match = Some(HalfMatch::new(
                    dfa.match_pattern(state, 0),
                    pos - 1,
                ));
            } else if dfa.is_dead_state(state) {
                return Ok(last_match);
            } else if dfa.is_quit_state(state) {
                // It is possible to enter into a quit state after
                // observing a match has occurred. In that case, we
                // should return the match instead of an error.
                if last_match.is_some() {
                    return Ok(last_match);
                }
                return Err(MatchError::Quit {
                    byte: b, offset: pos - 1,
                });
            } else if dfa.is_start_state(state) {
                // If we're in a start state and know all matches begin
                // with a particular byte, then we can quickly skip to
                // candidate matches without running the DFA through
                // every byte inbetween.
                if let Some(prefix_byte) = prefix_byte {
                    pos = match find_byte(haystack, pos, prefix_byte) {
                        Some(pos) => pos,
                        None => break,
                    };
                }
            }
        }
    }
    // Matches are always delayed by 1 byte, so we must explicitly walk
    // the special "EOI" transition at the end of the search.
    state = dfa.next_eoi_state(state);
    if dfa.is_match_state(state) {
        last_match = Some(HalfMatch::new(
            dfa.match_pattern(state, 0),
            haystack.len(),
        ));
    }
    Ok(last_match)
}

// In this example, it's obvious that all occurrences of our pattern
// begin with 'Z', so we pass in 'Z'.
let dfa = dense::DFA::new(r"Z[a-z]+")?;
let haystack = "123 foobar Zbaz quux".as_bytes();
let mat = find_leftmost_first(&dfa, haystack, Some(b'Z'))?.unwrap();
assert_eq!(mat.pattern().as_usize(), 0);
assert_eq!(mat.offset(), 15);

// But note that we don't need to pass in a prefix byte. If we don't,
// then the search routine does no acceleration.
let mat = find_leftmost_first(&dfa, haystack, None)?.unwrap();
assert_eq!(mat.pattern().as_usize(), 0);
assert_eq!(mat.offset(), 15);

// However, if we pass an incorrect byte, then the prefix search will
// result in incorrect results.
assert_eq!(find_leftmost_first(&dfa, haystack, Some(b'X'))?, None);

Returns true if and only if the given identifier corresponds to an accelerated state.

An accelerated state is a special optimization trick implemented by this crate. Namely, if dense::Config::accelerate is enabled (and it is by default), then DFAs generated by this crate will tag states meeting certain characteristics as accelerated. States meet this criteria whenever most of their transitions are self-transitions. That is, transitions that loop back to the same state. When a small number of transitions aren’t self-transitions, then it follows that there are only a small number of bytes that can cause the DFA to leave that state. Thus, there is an opportunity to look for those bytes using more optimized routines rather than continuing to run through the DFA. This trick is similar to the prefilter idea described in the documentation of Automaton::is_start_state with two main differences:

  1. It is more limited since acceleration only applies to single bytes. This means states are rarely accelerated when Unicode mode is enabled (which is enabled by default).
  2. It can occur anywhere in the DFA, which increases optimization opportunities.

Like the prefilter idea, the main downside (and a possible reason to disable it) is that it can lead to worse performance in some cases. Namely, if a state is accelerated for very common bytes, then the overhead of checking for acceleration and using the more optimized routines to look for those bytes can cause overall performance to be worse than if acceleration wasn’t enabled at all.

A simple example of a regex that has an accelerated state is (?-u)[^a]+a. Namely, the [^a]+ sub-expression gets compiled down into a single state where all transitions except for a loop back to itself, and where a is the only transition (other than the special EOI transition) that goes to some other state. Thus, this state can be accelerated and implemented more efficiently by calling an optimized routine like memchr with a as the needle. Notice that the (?-u) to disable Unicode is necessary here, as without it, [^a] will match any UTF-8 encoding of any Unicode scalar value other than a. This more complicated expression compiles down to many DFA states and the simple acceleration optimization is no longer available.

Typically, this routine is used to guard calls to Automaton::accelerator, which returns the accelerated bytes for the specified state.

Returns the total number of patterns compiled into this DFA.

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

Example

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

use regex_automata::dfa::{Automaton, dense::DFA};

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

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

use regex_automata::dfa::{Automaton, dense::DFA};

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

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

use regex_automata::dfa::{Automaton, dense::DFA};

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

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

If the given state is not a match state, then implementations may panic.

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

Implementations must guarantee that Automaton::match_pattern can be called with indices up to (but not including) the count returned by this routine without panicking.

Panics

Implementations are permitted to panic if the provided state ID does not correspond to a match state.

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::{
    dfa::{Automaton, dense},
    MatchKind,
};

let dfa = dense::Builder::new()
    .configure(dense::Config::new().match_kind(MatchKind::All))
    .build_many(&[
        r"\w+", r"[a-z]+", r"[A-Z]+", r"\S+",
    ])?;
let haystack = "@bar".as_bytes();

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

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

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

See Automaton::match_count for an example of how to use this method correctly. Note that if you know your DFA is compiled 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 Automaton::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 must always produce a valid PatternID.

Provided methods

Return a slice of bytes to accelerate for the given state, if possible.

If the given state has no accelerator, then an empty slice must be returned. If Automaton::is_accel_state returns true for the given ID, then this routine must return a non-empty slice, but it is not required to do so.

If the given ID is not a valid state ID for this automaton, then implementations may panic or produce incorrect results.

See Automaton::is_accel_state for more details on state acceleration.

By default, this method will always return an empty slice.

Example

This example shows a contrived case in which we build a regex that we know is accelerated and extract the accelerator from a state.

use regex_automata::{
    nfa::thompson,
    dfa::{Automaton, dense},
    util::id::StateID,
    SyntaxConfig,
};

let dfa = dense::Builder::new()
    // We disable Unicode everywhere and permit the regex to match
    // invalid UTF-8. e.g., `[^abc]` matches `\xFF`, which is not valid
    // UTF-8.
    .syntax(SyntaxConfig::new().unicode(false).utf8(false))
    // This makes the implicit `(?s:.)*?` prefix added to the regex
    // match through arbitrary bytes instead of being UTF-8 aware. This
    // isn't necessary to get acceleration to work in this case, but
    // it does make the DFA substantially simpler.
    .thompson(thompson::Config::new().utf8(false))
    .build("[^abc]+a")?;

// Here we just pluck out the state that we know is accelerated.
// While the stride calculations are something that can be relied
// on by callers, the specific position of the accelerated state is
// implementation defined.
//
// N.B. We get '3' by inspecting the state machine using 'regex-cli'.
// e.g., try `regex-cli debug dfa dense '[^abc]+a' -BbUC`.
let id = StateID::new(3 * dfa.stride()).unwrap();
let accelerator = dfa.accelerator(id);
// The `[^abc]+` sub-expression permits [a, b, c] to be accelerated.
assert_eq!(accelerator, &[b'a', b'b', b'c']);

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 Automaton::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 DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Example

This example shows how to use this method with a dense::DFA. In particular, it demonstrates how the position returned might differ from what one might expect when executing a traditional leftmost search.

use regex_automata::{
    dfa::{Automaton, dense},
    HalfMatch,
};

let dfa = dense::DFA::new("foo[0-9]+")?;
// 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(b"foo12345")?);

let dfa = dense::DFA::new("abc|a")?;
// 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(b"abc")?);

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 DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Example

This example shows how to use this method with a dense::DFA. In particular, it demonstrates how the position returned might differ from what one might expect when executing a traditional leftmost reverse search.

use regex_automata::{
    nfa::thompson,
    dfa::{Automaton, dense},
    HalfMatch,
};

let dfa = dense::Builder::new()
    .thompson(thompson::Config::new().reverse(true))
    .build("[a-z]+[0-9]+")?;
// 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(b"foo12345")?);

let dfa = dense::Builder::new()
    .thompson(thompson::Config::new().reverse(true))
    .build("abc|c")?;
// 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(b"abc")?);

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

Errors

This routine only errors if the search could not complete. For DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Notes for implementors

Implementors of this trait are not required to implement any particular match semantics (such as leftmost-first), which are instead manifest in the DFA’s transitions.

In particular, this method must continue searching even after it enters a match state. The search should only terminate 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.

Since this trait provides an implementation for this method by default, it’s unlikely that one will need to implement this.

Example

This example shows how to use this method with a dense::DFA. By default, a dense DFA uses “leftmost first” match semantics.

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::{
    dfa::{Automaton, dense},
    HalfMatch,
};

let dfa = dense::DFA::new("foo[0-9]+")?;
let expected = HalfMatch::must(0, 8);
assert_eq!(Some(expected), dfa.find_leftmost_fwd(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 = dense::DFA::new("abc|a")?;
let expected = HalfMatch::must(0, 3);
assert_eq!(Some(expected), dfa.find_leftmost_fwd(b"abc")?);

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.

Errors

This routine only errors if the search could not complete. For DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Notes for implementors

Implementors of this trait are not required to implement any particular match semantics (such as leftmost-first), which are instead manifest in the DFA’s transitions.

In particular, this method must continue searching even after it enters a match state. The search should only terminate 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.

Since this trait provides an implementation for this method by default, it’s unlikely that one will need to implement this.

Example

This example shows how to use this method with a dense::DFA. In particular, this routine is principally useful when used in conjunction with the nfa::thompson::Config::reverse 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,
    dfa::{Automaton, dense},
    HalfMatch,
};

let dfa = dense::Builder::new()
    .thompson(thompson::Config::new().reverse(true))
    .build("foo[0-9]+")?;
let expected = HalfMatch::must(0, 0);
assert_eq!(Some(expected), dfa.find_leftmost_rev(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 = dense::Builder::new()
    .thompson(thompson::Config::new().reverse(true))
    .build("abc|c")?;
let expected = HalfMatch::must(0, 0);
assert_eq!(Some(expected), dfa.find_leftmost_rev(b"abc")?);

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 DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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 with a dense::DFA. 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::{
    dfa::{Automaton, OverlappingState, dense},
    HalfMatch,
    MatchKind,
};

let dfa = dense::Builder::new()
    .configure(dense::Config::new().match_kind(MatchKind::All))
    .build_many(&[r"\w+$", r"\S+$"])?;
let haystack = "@foo".as_bytes();
let mut state = OverlappingState::start();

let expected = Some(HalfMatch::must(1, 4));
let got = dfa.find_overlapping_fwd(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(haystack, &mut state)?;
assert_eq!(expected, got);

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 Automaton::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 DFAs built by this crate, dense::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 DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Panics

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

It must also panic 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::{
    dfa::{Automaton, dense},
    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 = dense::DFA::new("z[0-9]{3}")?;
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(
    Some(&mut scanner),
    None,
    haystack,
    0,
    haystack.len(),
)?;
assert_eq!(expected, got);

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

use regex_automata::{
    dfa::{Automaton, dense},
    HalfMatch,
    PatternID,
};

let dfa = dense::Builder::new()
    .configure(dense::Config::new().starts_for_each_pattern(true))
    .build_many(&["[a-z0-9]{6}", "[a-z][a-z0-9]{5}"])?;
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(
    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(
    None,
    Some(PatternID::must(1)),
    haystack,
    0,
    haystack.len(),
)?;
assert_eq!(expected, got);

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

use regex_automata::{
    dfa::{Automaton, dense},
    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.
let dfa = dense::DFA::new(r"(?-u)\b[0-9]{3}\b")?;
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(
    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(
    None,
    None,
    haystack,
    3,
    6,
)?;
assert_eq!(expected, got);

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 Automaton::find_earliest_rev, except it provides some additional control over how the search is executed. See the documentation of Automaton::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 DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Panics

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

It must also panic if the given haystack range is not valid.

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 Automaton::find_leftmost_fwd, except it provides some additional control over how the search is executed. See the documentation of Automaton::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 DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Panics

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

It must also panic if the given haystack range is not valid.

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 Automaton::find_leftmost_rev, except it provides some additional control over how the search is executed. See the documentation of Automaton::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 DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Panics

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

It must also panic if the given haystack range is not valid.

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 Automaton::find_overlapping_fwd, except it provides some additional control over how the search is executed. See the documentation of Automaton::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 DFAs generated by this crate, this only occurs in a non-default configuration where quit bytes are used or Unicode word boundaries are heuristically enabled.

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

Panics

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

It must also panic if the given haystack range is not valid.

Implementations on Foreign Types

Implementors