Trait regex_automata::DFA
source · pub trait DFA {
type ID: StateID;
Show 15 methods
// Required methods
fn start_state(&self) -> Self::ID;
fn is_match_state(&self, id: Self::ID) -> bool;
fn is_dead_state(&self, id: Self::ID) -> bool;
fn is_match_or_dead_state(&self, id: Self::ID) -> bool;
fn is_anchored(&self) -> bool;
fn next_state(&self, current: Self::ID, input: u8) -> Self::ID;
unsafe fn next_state_unchecked(
&self,
current: Self::ID,
input: u8
) -> Self::ID;
// Provided methods
fn is_match(&self, bytes: &[u8]) -> bool { ... }
fn shortest_match(&self, bytes: &[u8]) -> Option<usize> { ... }
fn find(&self, bytes: &[u8]) -> Option<usize> { ... }
fn rfind(&self, bytes: &[u8]) -> Option<usize> { ... }
fn is_match_at(&self, bytes: &[u8], start: usize) -> bool { ... }
fn shortest_match_at(&self, bytes: &[u8], start: usize) -> Option<usize> { ... }
fn find_at(&self, bytes: &[u8], start: usize) -> Option<usize> { ... }
fn rfind_at(&self, bytes: &[u8], start: usize) -> Option<usize> { ... }
}Expand description
A trait describing the interface of a deterministic finite automaton (DFA).
Every DFA has exactly one start state and at least one dead state (which
may be the same, as in the case of an empty DFA). In all cases, a state
identifier of 0 must be a dead state such that DFA::is_dead_state(0)
always returns true.
Every DFA also has zero or more match states, such that
DFA::is_match_state(id) returns true if and only if id corresponds to
a match state.
In general, users of this trait likely will only need to use the search
routines such as is_match, shortest_match, find or rfind. The other
methods are lower level and are used for walking the transitions of a DFA
manually. In particular, the aforementioned search routines are implemented
generically in terms of the lower level transition walking routines.
Required Associated Types§
Required Methods§
sourcefn start_state(&self) -> Self::ID
fn start_state(&self) -> Self::ID
Return the identifier of this DFA’s start state.
sourcefn is_match_state(&self, id: Self::ID) -> bool
fn is_match_state(&self, id: Self::ID) -> bool
Returns true if and only if the given identifier corresponds to a match state.
sourcefn is_dead_state(&self, id: Self::ID) -> bool
fn is_dead_state(&self, id: Self::ID) -> 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 and thus can never lead to a match.
sourcefn is_match_or_dead_state(&self, id: Self::ID) -> bool
fn is_match_or_dead_state(&self, id: Self::ID) -> bool
Returns true if and only if the given identifier corresponds to either
a dead state or a match state, such that one of is_match_state(id)
or is_dead_state(id) must return true.
Depending on the implementation of the DFA, this routine can be used
to save a branch in the core matching loop. Nevertheless,
is_match_state(id) || is_dead_state(id) is always a valid
implementation.
sourcefn is_anchored(&self) -> bool
fn is_anchored(&self) -> bool
Returns true if and only if this DFA is anchored.
When a DFA is anchored, it is only allowed to report matches that
start at index 0.
sourcefn next_state(&self, current: Self::ID, input: u8) -> Self::ID
fn next_state(&self, current: Self::ID, input: u8) -> Self::ID
Given the current state that this DFA is in and the next input byte, this method returns the identifier of the next state. The identifier returned is always valid, but it may correspond to a dead state.
sourceunsafe fn next_state_unchecked(&self, current: Self::ID, input: u8) -> Self::ID
unsafe fn next_state_unchecked(&self, current: Self::ID, input: u8) -> Self::ID
Like next_state, but its implementation may look up the next state
without memory safety checks such as bounds checks. As such, callers
must ensure that the given identifier corresponds to a valid DFA
state. Implementors must, in turn, ensure that this routine is safe
for all valid state identifiers and for all possible u8 values.
Provided Methods§
sourcefn is_match(&self, bytes: &[u8]) -> bool
fn is_match(&self, bytes: &[u8]) -> bool
Returns true if and only if the given bytes match this DFA.
This routine may short circuit if it knows that scanning future input
will never lead to a different result. In particular, if a DFA enters
a match state or a dead state, then this routine will return true or
false, respectively, without inspecting any future input.
Example
This example shows how to use this method with a
DenseDFA.
use regex_automata::{DFA, DenseDFA};
let dfa = DenseDFA::new("foo[0-9]+bar")?;
assert_eq!(true, dfa.is_match(b"foo12345bar"));
assert_eq!(false, dfa.is_match(b"foobar"));sourcefn shortest_match(&self, bytes: &[u8]) -> Option<usize>
fn shortest_match(&self, bytes: &[u8]) -> Option<usize>
Returns the first position at which a match is found.
This routine stops scanning input in precisely the same circumstances
as is_match. The key difference is that this routine returns the
position at which it stopped scanning input if and only if a match
was found. If no match is found, then None is returned.
Example
This example shows how to use this method with a
DenseDFA.
use regex_automata::{DFA, DenseDFA};
let dfa = DenseDFA::new("foo[0-9]+")?;
assert_eq!(Some(4), dfa.shortest_match(b"foo12345"));
// Normally, the end of the leftmost first match here would be 3,
// but the shortest match semantics detect a match earlier.
let dfa = DenseDFA::new("abc|a")?;
assert_eq!(Some(1), dfa.shortest_match(b"abc"));sourcefn find(&self, bytes: &[u8]) -> Option<usize>
fn find(&self, bytes: &[u8]) -> Option<usize>
Returns the end offset of the longest match. If no match exists,
then None is returned.
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 topology itself.
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 state. Upon termination, the position of the last byte seen while still in a match state is returned.
Example
This example shows how to use this method with a
DenseDFA. 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.
use regex_automata::{DFA, DenseDFA};
let dfa = DenseDFA::new("foo[0-9]+")?;
assert_eq!(Some(8), dfa.find(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 = DenseDFA::new("abc|a")?;
assert_eq!(Some(3), dfa.find(b"abc"));sourcefn rfind(&self, bytes: &[u8]) -> Option<usize>
fn rfind(&self, bytes: &[u8]) -> Option<usize>
Returns the start offset of the longest match in reverse, by searching
from the end of the input towards the start of the input. If no match
exists, then None is returned. In other words, this has the same
match semantics as find, but in reverse.
Example
This example shows how to use this method with a
DenseDFA. In particular, this routine
is principally useful when used in conjunction with the
dense::Builder::reverse
configuration knob. In general, it’s unlikely to be correct to use both
find and rfind with the same DFA since any particular DFA will only
support searching in one direction.
use regex_automata::{dense, DFA};
let dfa = dense::Builder::new().reverse(true).build("foo[0-9]+")?;
assert_eq!(Some(0), dfa.rfind(b"foo12345"));sourcefn is_match_at(&self, bytes: &[u8], start: usize) -> bool
fn is_match_at(&self, bytes: &[u8], start: usize) -> bool
Returns the same as is_match, but starts the search at the given
offset.
The significance of the starting point is that it takes the surrounding
context into consideration. For example, if the DFA is anchored, then
a match can only occur when start == 0.
sourcefn shortest_match_at(&self, bytes: &[u8], start: usize) -> Option<usize>
fn shortest_match_at(&self, bytes: &[u8], start: usize) -> Option<usize>
Returns the same as shortest_match, but starts the search at the
given offset.
The significance of the starting point is that it takes the surrounding
context into consideration. For example, if the DFA is anchored, then
a match can only occur when start == 0.
sourcefn find_at(&self, bytes: &[u8], start: usize) -> Option<usize>
fn find_at(&self, bytes: &[u8], start: usize) -> Option<usize>
Returns the same as find, but starts the search at the given
offset.
The significance of the starting point is that it takes the surrounding
context into consideration. For example, if the DFA is anchored, then
a match can only occur when start == 0.
sourcefn rfind_at(&self, bytes: &[u8], start: usize) -> Option<usize>
fn rfind_at(&self, bytes: &[u8], start: usize) -> Option<usize>
Returns the same as rfind, but starts the search at the given
offset.
The significance of the starting point is that it takes the surrounding
context into consideration. For example, if the DFA is anchored, then
a match can only occur when start == bytes.len().