Trait regex_automata::dfa::Automaton
source · pub unsafe trait Automaton {
Show 25 methods
// Required 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,
input: &Input<'_>
) -> Result<StateID, MatchError>;
fn start_state_reverse(
&self,
input: &Input<'_>
) -> Result<StateID, MatchError>;
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_len(&self) -> usize;
fn match_len(&self, id: StateID) -> usize;
fn match_pattern(&self, id: StateID, index: usize) -> PatternID;
fn has_empty(&self) -> bool;
fn is_utf8(&self) -> bool;
fn is_always_start_anchored(&self) -> bool;
// Provided methods
fn universal_start_state(&self, _mode: Anchored) -> Option<StateID> { ... }
fn accelerator(&self, _id: StateID) -> &[u8] ⓘ { ... }
fn get_prefilter(&self) -> Option<&Prefilter> { ... }
fn try_search_fwd(
&self,
input: &Input<'_>
) -> Result<Option<HalfMatch>, MatchError> { ... }
fn try_search_rev(
&self,
input: &Input<'_>
) -> Result<Option<HalfMatch>, MatchError> { ... }
fn try_search_overlapping_fwd(
&self,
input: &Input<'_>,
state: &mut OverlappingState
) -> Result<(), MatchError> { ... }
fn try_search_overlapping_rev(
&self,
input: &Input<'_>,
state: &mut OverlappingState
) -> Result<(), MatchError> { ... }
fn try_which_overlapping_matches(
&self,
input: &Input<'_>,
patset: &mut PatternSet
) -> Result<(), 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_len
returns the number of patterns compiled into the DFA,Automaton::match_len
returns the total number of patterns that match in a particular state andAutomaton::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
andAutomaton::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 useAutomaton::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 theAutomaton::accelerator
method.
- A dead state. A dead state means the DFA will never enter a match
state. This can be queried via the
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 can be a little subtle. 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 not safe to implement so that code may rely on the correctness of implementations of this trait to avoid undefined behavior. The primary correctness guarantees are:
Automaton::start_state
always returns a valid state ID or an error or panics.Automaton::next_state
, when given a valid state ID, always returns a valid state ID for all values ofanchored
andbyte
, or otherwise panics.
In general, the rest of the methods on Automaton
need to uphold their
contracts as well. For example, Automaton::is_dead
should only returns
true if the given state ID is actually a dead state.
Required Methods§
sourcefn next_state(&self, current: StateID, input: u8) -> StateID
fn next_state(&self, current: StateID, input: u8) -> StateID
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}, Input};
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(&Input::new(haystack))?;
// 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));
sourceunsafe fn next_state_unchecked(&self, current: StateID, input: u8) -> StateID
unsafe fn next_state_unchecked(&self, current: StateID, input: u8) -> StateID
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
.
sourcefn next_eoi_state(&self, current: StateID) -> StateID
fn next_eoi_state(&self, current: StateID) -> StateID
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}, Input};
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.
//
// The unwrap is OK because we aren't requesting a start state for a
// specific pattern.
let mut state = dfa.start_state_forward(&Input::new(haystack))?;
// 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));
sourcefn start_state_forward(&self, input: &Input<'_>) -> Result<StateID, MatchError>
fn start_state_forward(&self, input: &Input<'_>) -> Result<StateID, MatchError>
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
Anchored
mode of the search. Unanchored, anchored and anchored searches for a specificPatternID
all use different start states. - The position at which the search begins, via
Input::start
. This and the byte immediately preceding the start of the search (if one exists) influence which look-behind assertions are true at the start of the search. This in turn influences which start state is selected. - Whether the search is a forward or reverse search. This routine can only be used for forward searches.
Errors
This may return a MatchError
if the search needs to give up
when determining the start state (for example, if it sees a “quit”
byte). This can also return an error if the given Input
contains an
unsupported Anchored
configuration.
sourcefn start_state_reverse(&self, input: &Input<'_>) -> Result<StateID, MatchError>
fn start_state_reverse(&self, input: &Input<'_>) -> Result<StateID, MatchError>
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
Anchored
mode of the search. Unanchored, anchored and anchored searches for a specificPatternID
all use different start states. - The position at which the search begins, via
Input::start
. This and the byte immediately preceding the start of the search (if one exists) influence which look-behind assertions are true at the start of the search. This in turn influences which start state is selected. - Whether the search is a forward or reverse search. This routine can only be used for reverse searches.
Errors
This may return a MatchError
if the search needs to give up
when determining the start state (for example, if it sees a “quit”
byte). This can also return an error if the given Input
contains an
unsupported Anchored
configuration.
sourcefn is_special_state(&self, id: StateID) -> bool
fn is_special_state(&self, id: StateID) -> bool
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, Input,
};
fn find<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(&Input::new(haystack))?;
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(b, 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(&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(&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(&dfa, haystack)?.unwrap();
assert_eq!(mat.pattern().as_usize(), 1);
assert_eq!(mat.offset(), 3);
let mat = find(&dfa, &haystack[3..])?.unwrap();
assert_eq!(mat.pattern().as_usize(), 0);
assert_eq!(mat.offset(), 7);
let mat = find(&dfa, &haystack[10..])?.unwrap();
assert_eq!(mat.pattern().as_usize(), 1);
assert_eq!(mat.offset(), 5);
sourcefn is_dead_state(&self, id: StateID) -> bool
fn is_dead_state(&self, id: StateID) -> bool
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.
sourcefn is_quit_state(&self, id: StateID) -> bool
fn is_quit_state(&self, id: StateID) -> bool
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.)
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.
sourcefn is_match_state(&self, id: StateID) -> bool
fn is_match_state(&self, id: StateID) -> bool
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.
sourcefn is_start_state(&self, id: StateID) -> bool
fn is_start_state(&self, id: StateID) -> bool
Returns true 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.
As mentioned in the documentation for
is_special_state
implementations
may always return false, even if the given identifier is a start
state. This is because knowing whether a state is a start state or not
is not necessary for correctness and is only treated as a potential
performance optimization. (For example, the implementations of this
trait in this crate will only return true when the given identifier
corresponds to a start state and when specialization of start
states was enabled
during DFA construction. If start state specialization is disabled
(which is the default), then this method will always return false.)
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.
A prefilter can be added to your search configuration with
dense::Config::prefilter
for
dense and sparse DFAs in this crate.
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::{
dfa::{Automaton, dense},
HalfMatch, MatchError, Input,
};
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<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(&Input::new(haystack))?;
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(b, 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'. Note also that we need to
// enable start state specialization, or else it won't be possible to
// detect start states during a search. ('is_start_state' would always
// return false.)
let dfa = dense::DFA::builder()
.configure(dense::DFA::config().specialize_start_states(true))
.build(r"Z[a-z]+")?;
let haystack = "123 foobar Zbaz quux".as_bytes();
let mat = find(&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(&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(&dfa, haystack, Some(b'X'))?, None);
sourcefn is_accel_state(&self, id: StateID) -> bool
fn is_accel_state(&self, id: StateID) -> bool
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:
- 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).
- 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.
sourcefn pattern_len(&self) -> usize
fn pattern_len(&self) -> usize
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 length 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_len(), 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_len(), 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_len(), 3);
sourcefn match_len(&self, id: StateID) -> usize
fn match_len(&self, id: StateID) -> usize
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 length 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}, Input, MatchKind};
let dfa = dense::Builder::new()
.configure(dense::Config::new().match_kind(MatchKind::All))
.build_many(&[
r"[[:word:]]+", r"[a-z]+", r"[A-Z]+", r"[[:^space:]]+",
])?;
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(&Input::new(haystack))?;
// 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_len(state), 3);
// The following calls are guaranteed to not panic since `match_len`
// 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);
sourcefn match_pattern(&self, id: StateID, index: usize) -> PatternID
fn match_pattern(&self, id: StateID, index: usize) -> PatternID
Returns the pattern ID corresponding to the given match index in the given state.
See Automaton::match_len
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_len
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
.
sourcefn has_empty(&self) -> bool
fn has_empty(&self) -> bool
Returns true if and only if this automaton can match the empty string. When it returns false, all possible matches are guaranteed to have a non-zero length.
This is useful as cheap way to know whether code needs to handle the case of a zero length match. This is particularly important when UTF-8 modes are enabled, as when UTF-8 mode is enabled, empty matches that split a codepoint must never be reported. This extra handling can sometimes be costly, and since regexes matching an empty string are somewhat rare, it can be beneficial to treat such regexes specially.
Example
This example shows a few different DFAs and whether they match the
empty string or not. Notice the empty string isn’t merely a matter
of a string of length literally 0
, but rather, whether a match can
occur between specific pairs of bytes.
use regex_automata::{dfa::{dense::DFA, Automaton}, util::syntax};
// The empty regex matches the empty string.
let dfa = DFA::new("")?;
assert!(dfa.has_empty(), "empty matches empty");
// The '+' repetition operator requires at least one match, and so
// does not match the empty string.
let dfa = DFA::new("a+")?;
assert!(!dfa.has_empty(), "+ does not match empty");
// But the '*' repetition operator does.
let dfa = DFA::new("a*")?;
assert!(dfa.has_empty(), "* does match empty");
// And wrapping '+' in an operator that can match an empty string also
// causes it to match the empty string too.
let dfa = DFA::new("(a+)*")?;
assert!(dfa.has_empty(), "+ inside of * matches empty");
// If a regex is just made of a look-around assertion, even if the
// assertion requires some kind of non-empty string around it (such as
// \b), then it is still treated as if it matches the empty string.
// Namely, if a match occurs of just a look-around assertion, then the
// match returned is empty.
let dfa = DFA::builder()
.configure(DFA::config().unicode_word_boundary(true))
.syntax(syntax::Config::new().utf8(false))
.build(r"^$\A\z\b\B(?-u:\b\B)")?;
assert!(dfa.has_empty(), "assertions match empty");
// Even when an assertion is wrapped in a '+', it still matches the
// empty string.
let dfa = DFA::new(r"^+")?;
assert!(dfa.has_empty(), "+ of an assertion matches empty");
// An alternation with even one branch that can match the empty string
// is also said to match the empty string overall.
let dfa = DFA::new("foo|(bar)?|quux")?;
assert!(dfa.has_empty(), "alternations can match empty");
// An NFA that matches nothing does not match the empty string.
let dfa = DFA::new("[a&&b]")?;
assert!(!dfa.has_empty(), "never matching means not matching empty");
// But if it's wrapped in something that doesn't require a match at
// all, then it can match the empty string!
let dfa = DFA::new("[a&&b]*")?;
assert!(dfa.has_empty(), "* on never-match still matches empty");
// Since a '+' requires a match, using it on something that can never
// match will itself produce a regex that can never match anything,
// and thus does not match the empty string.
let dfa = DFA::new("[a&&b]+")?;
assert!(!dfa.has_empty(), "+ on never-match still matches nothing");
sourcefn is_utf8(&self) -> bool
fn is_utf8(&self) -> bool
Whether UTF-8 mode is enabled for this DFA or not.
When UTF-8 mode is enabled, all matches reported by a DFA are guaranteed to correspond to spans of valid UTF-8. This includes zero-width matches. For example, the DFA must guarantee that the empty regex will not match at the positions between code units in the UTF-8 encoding of a single codepoint.
See thompson::Config::utf8
for
more information.
Example
This example shows how UTF-8 mode can impact the match spans that may be reported in certain cases.
use regex_automata::{
dfa::{dense::DFA, Automaton},
nfa::thompson,
HalfMatch, Input,
};
// UTF-8 mode is enabled by default.
let re = DFA::new("")?;
assert!(re.is_utf8());
let mut input = Input::new("☃");
let got = re.try_search_fwd(&input)?;
assert_eq!(Some(HalfMatch::must(0, 0)), got);
// Even though an empty regex matches at 1..1, our next match is
// 3..3 because 1..1 and 2..2 split the snowman codepoint (which is
// three bytes long).
input.set_start(1);
let got = re.try_search_fwd(&input)?;
assert_eq!(Some(HalfMatch::must(0, 3)), got);
// But if we disable UTF-8, then we'll get matches at 1..1 and 2..2:
let re = DFA::builder()
.thompson(thompson::Config::new().utf8(false))
.build("")?;
assert!(!re.is_utf8());
let got = re.try_search_fwd(&input)?;
assert_eq!(Some(HalfMatch::must(0, 1)), got);
input.set_start(2);
let got = re.try_search_fwd(&input)?;
assert_eq!(Some(HalfMatch::must(0, 2)), got);
input.set_start(3);
let got = re.try_search_fwd(&input)?;
assert_eq!(Some(HalfMatch::must(0, 3)), got);
input.set_start(4);
let got = re.try_search_fwd(&input)?;
assert_eq!(None, got);
sourcefn is_always_start_anchored(&self) -> bool
fn is_always_start_anchored(&self) -> bool
Returns true if and only if this DFA is limited to returning matches
whose start position is 0
.
Note that if you’re using DFAs provided by
this crate, then this is orthogonal to
Config::start_kind
.
This is useful in some cases because if a DFA is limited to producing
matches that start at offset 0
, then a reverse search is never
required for finding the start of a match.
Example
use regex_automata::dfa::{dense::DFA, Automaton};
// The empty regex matches anywhere
let dfa = DFA::new("")?;
assert!(!dfa.is_always_start_anchored(), "empty matches anywhere");
// 'a' matches anywhere.
let dfa = DFA::new("a")?;
assert!(!dfa.is_always_start_anchored(), "'a' matches anywhere");
// '^' only matches at offset 0!
let dfa = DFA::new("^a")?;
assert!(dfa.is_always_start_anchored(), "'^a' matches only at 0");
// But '(?m:^)' matches at 0 but at other offsets too.
let dfa = DFA::new("(?m:^)a")?;
assert!(!dfa.is_always_start_anchored(), "'(?m:^)a' matches anywhere");
Provided Methods§
sourcefn universal_start_state(&self, _mode: Anchored) -> Option<StateID>
fn universal_start_state(&self, _mode: Anchored) -> Option<StateID>
If this DFA has a universal starting state for the given anchor mode and the DFA supports universal starting states, then this returns that state’s identifier.
A DFA is said to have a universal starting state when the starting state is invariant with respect to the haystack. Usually, the starting state is chosen depending on the bytes immediately surrounding the starting position of a search. However, the starting state only differs when one or more of the patterns in the DFA have look-around assertions in its prefix.
Stated differently, if none of the patterns in a DFA have look-around assertions in their prefix, then the DFA has a universal starting state and may be returned by this method.
It is always correct for implementations to return None
, and indeed,
this is what the default implementation does. When this returns None
,
callers must use either start_state_forward
or start_state_reverse
to get the starting state.
Use case
There are a few reasons why one might want to use this:
- If you know your regex patterns have no look-around assertions in their prefix, then calling this routine is likely cheaper and perhaps more semantically meaningful.
- When implementing prefilter support in a DFA regex implementation, it is necessary to re-compute the start state after a candidate is returned from the prefilter. However, this is only needed when there isn’t a universal start state. When one exists, one can avoid re-computing the start state.
Example
use regex_automata::{
dfa::{Automaton, dense::DFA},
Anchored,
};
// There are no look-around assertions in the prefixes of any of the
// patterns, so we get a universal start state.
let dfa = DFA::new_many(&["[0-9]+", "[a-z]+$", "[A-Z]+"])?;
assert!(dfa.universal_start_state(Anchored::No).is_some());
assert!(dfa.universal_start_state(Anchored::Yes).is_some());
// One of the patterns has a look-around assertion in its prefix,
// so this means there is no longer a universal start state.
let dfa = DFA::new_many(&["[0-9]+", "^[a-z]+$", "[A-Z]+"])?;
assert!(!dfa.universal_start_state(Anchored::No).is_some());
assert!(!dfa.universal_start_state(Anchored::Yes).is_some());
sourcefn accelerator(&self, _id: StateID) -> &[u8] ⓘ
fn accelerator(&self, _id: StateID) -> &[u8] ⓘ
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 note that it is
not required for an implementation of this trait to ever return true
for is_accel_state
, even if the state could be accelerated. That
is, acceleration is an optional optimization. But the return values of
is_accel_state
and accelerator
must be in sync.
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::{
dfa::{Automaton, dense},
util::{primitives::StateID, syntax},
};
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. If we left Unicode enabled, [^abc] would match any UTF-8
// encoding of any Unicode scalar value except for 'a', 'b' or 'c'.
// That translates to a much more complicated DFA, and also
// inhibits the 'accelerator' optimization that we are trying to
// demonstrate in this example.
.syntax(syntax::Config::new().unicode(false).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']);
sourcefn get_prefilter(&self) -> Option<&Prefilter>
fn get_prefilter(&self) -> Option<&Prefilter>
Returns the prefilter associated with a DFA, if one exists.
The default implementation of this trait always returns None
. And
indeed, it is always correct to return None
.
For DFAs in this crate, a prefilter can be attached to a DFA via
dense::Config::prefilter
.
Do note that prefilters are not serialized by DFAs in this crate. So if you deserialize a DFA that had a prefilter attached to it at serialization time, then it will not have a prefilter after deserialization.
sourcefn try_search_fwd(
&self,
input: &Input<'_>
) -> Result<Option<HalfMatch>, MatchError>
fn try_search_fwd( &self, input: &Input<'_> ) -> 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 errors if the search could not complete. This can occur in a number of circumstances:
- The configuration of the DFA may permit it to “quit” the search. For example, setting quit bytes or enabling heuristic support for Unicode word boundaries. The default configuration does not enable any option that could result in the DFA quitting.
- When the provided
Input
configuration is not supported. For example, by providing an unsupported anchor mode.
When a search returns an error, 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. But this search routine should behave as a general “leftmost” search.
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
.
use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
let dfa = dense::DFA::new("foo[0-9]+")?;
let expected = Some(HalfMatch::must(0, 8));
assert_eq!(expected, dfa.try_search_fwd(&Input::new(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 = Some(HalfMatch::must(0, 3));
assert_eq!(expected, dfa.try_search_fwd(&Input::new(b"abc"))?);
Example: specific pattern search
This example shows how to build a multi-DFA that permits searching for specific patterns.
use regex_automata::{
dfa::{Automaton, dense},
Anchored, HalfMatch, PatternID, Input,
};
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.try_search_fwd(&Input::new(haystack))?;
assert_eq!(expected, got);
// But if we want to check whether some other pattern matches, then we
// can provide its pattern ID.
let input = Input::new(haystack)
.anchored(Anchored::Pattern(PatternID::must(1)));
let expected = Some(HalfMatch::must(1, 6));
let got = dfa.try_search_fwd(&input)?;
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::{dfa::{Automaton, dense}, HalfMatch, Input};
// 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 input = Input::new(&haystack[3..6]);
let expected = Some(HalfMatch::must(0, 3));
let got = dfa.try_search_fwd(&input)?;
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 input = Input::new(haystack).range(3..6);
let expected = None;
let got = dfa.try_search_fwd(&input)?;
assert_eq!(expected, got);
sourcefn try_search_rev(
&self,
input: &Input<'_>
) -> Result<Option<HalfMatch>, MatchError>
fn try_search_rev( &self, input: &Input<'_> ) -> 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.
Errors
This routine errors if the search could not complete. This can occur in a number of circumstances:
- The configuration of the DFA may permit it to “quit” the search. For example, setting quit bytes or enabling heuristic support for Unicode word boundaries. The default configuration does not enable any option that could result in the DFA quitting.
- When the provided
Input
configuration is not supported. For example, by providing an unsupported anchor mode.
When a search returns an error, callers cannot know whether a match exists or not.
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 try_search_fwd
and try_search_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, Input,
};
let dfa = dense::Builder::new()
.thompson(thompson::Config::new().reverse(true))
.build("foo[0-9]+")?;
let expected = Some(HalfMatch::must(0, 0));
assert_eq!(expected, dfa.try_search_rev(&Input::new(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 = Some(HalfMatch::must(0, 0));
assert_eq!(expected, dfa.try_search_rev(&Input::new(b"abc"))?);
Example: UTF-8 mode
This examples demonstrates that UTF-8 mode applies to reverse DFAs. When UTF-8 mode is enabled in the underlying NFA, then all matches reported must correspond to valid UTF-8 spans. This includes prohibiting zero-width matches that split a codepoint.
UTF-8 mode is enabled by default. Notice below how the only zero-width matches reported are those at UTF-8 boundaries:
use regex_automata::{
dfa::{dense::DFA, Automaton},
nfa::thompson,
HalfMatch, Input, MatchKind,
};
let dfa = DFA::builder()
.thompson(thompson::Config::new().reverse(true))
.build(r"")?;
// Run the reverse DFA to collect all matches.
let mut input = Input::new("☃");
let mut matches = vec![];
loop {
match dfa.try_search_rev(&input)? {
None => break,
Some(hm) => {
matches.push(hm);
if hm.offset() == 0 || input.end() == 0 {
break;
} else if hm.offset() < input.end() {
input.set_end(hm.offset());
} else {
// This is only necessary to handle zero-width
// matches, which of course occur in this example.
// Without this, the search would never advance
// backwards beyond the initial match.
input.set_end(input.end() - 1);
}
}
}
}
// No matches split a codepoint.
let expected = vec![
HalfMatch::must(0, 3),
HalfMatch::must(0, 0),
];
assert_eq!(expected, matches);
Now let’s look at the same example, but with UTF-8 mode on the original NFA disabled (which results in disabling UTF-8 mode on the DFA):
use regex_automata::{
dfa::{dense::DFA, Automaton},
nfa::thompson,
HalfMatch, Input, MatchKind,
};
let dfa = DFA::builder()
.thompson(thompson::Config::new().reverse(true).utf8(false))
.build(r"")?;
// Run the reverse DFA to collect all matches.
let mut input = Input::new("☃");
let mut matches = vec![];
loop {
match dfa.try_search_rev(&input)? {
None => break,
Some(hm) => {
matches.push(hm);
if hm.offset() == 0 || input.end() == 0 {
break;
} else if hm.offset() < input.end() {
input.set_end(hm.offset());
} else {
// This is only necessary to handle zero-width
// matches, which of course occur in this example.
// Without this, the search would never advance
// backwards beyond the initial match.
input.set_end(input.end() - 1);
}
}
}
}
// No matches split a codepoint.
let expected = vec![
HalfMatch::must(0, 3),
HalfMatch::must(0, 2),
HalfMatch::must(0, 1),
HalfMatch::must(0, 0),
];
assert_eq!(expected, matches);
sourcefn try_search_overlapping_fwd(
&self,
input: &Input<'_>,
state: &mut OverlappingState
) -> Result<(), MatchError>
fn try_search_overlapping_fwd( &self, input: &Input<'_>, state: &mut OverlappingState ) -> Result<(), MatchError>
Executes an overlapping forward search. Matches, if one exists, can be
obtained via the OverlappingState::get_match
method.
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.
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 errors if the search could not complete. This can occur in a number of circumstances:
- The configuration of the DFA may permit it to “quit” the search. For example, setting quit bytes or enabling heuristic support for Unicode word boundaries. The default configuration does not enable any option that could result in the DFA quitting.
- When the provided
Input
configuration is not supported. For example, by providing an unsupported anchor mode.
When a search returns an error, 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, Input, MatchKind,
};
let dfa = dense::Builder::new()
.configure(dense::Config::new().match_kind(MatchKind::All))
.build_many(&[r"[[:word:]]+$", r"[[:^space:]]+$"])?;
let haystack = "@foo";
let mut state = OverlappingState::start();
let expected = Some(HalfMatch::must(1, 4));
dfa.try_search_overlapping_fwd(&Input::new(haystack), &mut state)?;
assert_eq!(expected, state.get_match());
// 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));
dfa.try_search_overlapping_fwd(&Input::new(haystack), &mut state)?;
assert_eq!(expected, state.get_match());
sourcefn try_search_overlapping_rev(
&self,
input: &Input<'_>,
state: &mut OverlappingState
) -> Result<(), MatchError>
fn try_search_overlapping_rev( &self, input: &Input<'_>, state: &mut OverlappingState ) -> Result<(), MatchError>
Executes a reverse overlapping forward search. Matches, if one exists,
can be obtained via the OverlappingState::get_match
method.
When using this routine to implement an iterator of overlapping
matches, the start
of the search should remain invariant throughout
iteration. The OverlappingState
given to the search will keep track
of the current position of the search. (This is because multiple
matches may be reported at the same position, so only the search
implementation itself knows when to advance the position.)
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 errors if the search could not complete. This can occur in a number of circumstances:
- The configuration of the DFA may permit it to “quit” the search. For example, setting quit bytes or enabling heuristic support for Unicode word boundaries. The default configuration does not enable any option that could result in the DFA quitting.
- When the provided
Input
configuration is not supported. For example, by providing an unsupported anchor mode.
When a search returns an error, callers cannot know whether a match exists or not.
Example: UTF-8 mode
This examples demonstrates that UTF-8 mode applies to reverse DFAs. When UTF-8 mode is enabled in the underlying NFA, then all matches reported must correspond to valid UTF-8 spans. This includes prohibiting zero-width matches that split a codepoint.
UTF-8 mode is enabled by default. Notice below how the only zero-width matches reported are those at UTF-8 boundaries:
use regex_automata::{
dfa::{dense::DFA, Automaton, OverlappingState},
nfa::thompson,
HalfMatch, Input, MatchKind,
};
let dfa = DFA::builder()
.configure(DFA::config().match_kind(MatchKind::All))
.thompson(thompson::Config::new().reverse(true))
.build_many(&[r"", r"☃"])?;
// Run the reverse DFA to collect all matches.
let input = Input::new("☃");
let mut state = OverlappingState::start();
let mut matches = vec![];
loop {
dfa.try_search_overlapping_rev(&input, &mut state)?;
match state.get_match() {
None => break,
Some(hm) => matches.push(hm),
}
}
// No matches split a codepoint.
let expected = vec![
HalfMatch::must(0, 3),
HalfMatch::must(1, 0),
HalfMatch::must(0, 0),
];
assert_eq!(expected, matches);
Now let’s look at the same example, but with UTF-8 mode on the original NFA disabled (which results in disabling UTF-8 mode on the DFA):
use regex_automata::{
dfa::{dense::DFA, Automaton, OverlappingState},
nfa::thompson,
HalfMatch, Input, MatchKind,
};
let dfa = DFA::builder()
.configure(DFA::config().match_kind(MatchKind::All))
.thompson(thompson::Config::new().reverse(true).utf8(false))
.build_many(&[r"", r"☃"])?;
// Run the reverse DFA to collect all matches.
let input = Input::new("☃");
let mut state = OverlappingState::start();
let mut matches = vec![];
loop {
dfa.try_search_overlapping_rev(&input, &mut state)?;
match state.get_match() {
None => break,
Some(hm) => matches.push(hm),
}
}
// Now *all* positions match, even within a codepoint,
// because we lifted the requirement that matches
// correspond to valid UTF-8 spans.
let expected = vec![
HalfMatch::must(0, 3),
HalfMatch::must(0, 2),
HalfMatch::must(0, 1),
HalfMatch::must(1, 0),
HalfMatch::must(0, 0),
];
assert_eq!(expected, matches);
sourcefn try_which_overlapping_matches(
&self,
input: &Input<'_>,
patset: &mut PatternSet
) -> Result<(), MatchError>
fn try_which_overlapping_matches( &self, input: &Input<'_>, patset: &mut PatternSet ) -> Result<(), MatchError>
Writes the set of patterns that match anywhere in the given search
configuration to patset
. If multiple patterns match at the same
position and the underlying DFA supports overlapping matches, then all
matching patterns are written to the given set.
Unless all of the patterns in this DFA are anchored, then generally speaking, this will visit every byte in the haystack.
This search routine does not clear the pattern set. This gives some flexibility to the caller (e.g., running multiple searches with the same pattern set), but does make the API bug-prone if you’re reusing the same pattern set for multiple searches but intended them to be independent.
If a pattern ID matched but the given PatternSet
does not have
sufficient capacity to store it, then it is not inserted and silently
dropped.
Errors
This routine errors if the search could not complete. This can occur in a number of circumstances:
- The configuration of the DFA may permit it to “quit” the search. For example, setting quit bytes or enabling heuristic support for Unicode word boundaries. The default configuration does not enable any option that could result in the DFA quitting.
- When the provided
Input
configuration is not supported. For example, by providing an unsupported anchor mode.
When a search returns an error, callers cannot know whether a match exists or not.
Example
This example shows how to find all matching patterns in a haystack, even when some patterns match at the same position as other patterns.
use regex_automata::{
dfa::{Automaton, dense::DFA},
Input, MatchKind, PatternSet,
};
let patterns = &[
r"[[:word:]]+",
r"[0-9]+",
r"[[:alpha:]]+",
r"foo",
r"bar",
r"barfoo",
r"foobar",
];
let dfa = DFA::builder()
.configure(DFA::config().match_kind(MatchKind::All))
.build_many(patterns)?;
let input = Input::new("foobar");
let mut patset = PatternSet::new(dfa.pattern_len());
dfa.try_which_overlapping_matches(&input, &mut patset)?;
let expected = vec![0, 2, 3, 4, 6];
let got: Vec<usize> = patset.iter().map(|p| p.as_usize()).collect();
assert_eq!(expected, got);