Struct regex_automata::hybrid::dfa::DFA
source · pub struct DFA { /* private fields */ }
Expand description
A hybrid NFA/DFA (also called a “lazy DFA”) for regex searching.
A lazy DFA is a DFA that builds itself at search time. It otherwise has
very similar characteristics as a dense::DFA
.
Indeed, both support precisely the same regex features with precisely the
same semantics.
Where as a dense::DFA
must be completely built to handle any input before
it may be used for search, a lazy DFA starts off effectively empty. During
a search, a lazy DFA will build itself depending on whether it has already
computed the next transition or not. If it has, then it looks a lot like
a dense::DFA
internally: it does a very fast table based access to find
the next transition. Otherwise, if the state hasn’t been computed, then it
does determinization for that specific transition to compute the next DFA
state.
The main selling point of a lazy DFA is that, in practice, it has
the performance profile of a dense::DFA
without the weakness of it
taking worst case exponential time to build. Indeed, for each byte of
input, the lazy DFA will construct as most one new DFA state. Thus, a
lazy DFA achieves worst case O(mn)
time for regex search (where m ~ pattern.len()
and n ~ haystack.len()
).
The main downsides of a lazy DFA are:
- It requires mutable “cache” space during search. This is where the transition table, among other things, is stored.
- In pathological cases (e.g., if the cache is too small), it will run out of room and either require a bigger cache capacity or will repeatedly clear the cache and thus repeatedly regenerate DFA states. Overall, this will tend to be slower than a typical NFA simulation.
§Capabilities
Like a dense::DFA
, a single lazy DFA fundamentally supports the following
operations:
- Detection of a match.
- Location of the end of a match.
- In the case of a lazy DFA with multiple patterns, which pattern matched is reported as well.
A notable absence from the above list of capabilities is the location of
the start of a match. In order to provide both the start and end of
a match, two lazy DFAs are required. This functionality is provided by a
Regex
.
§Example
This shows how to build a lazy DFA with the default configuration and
execute a search. Notice how, in contrast to a dense::DFA
, we must create
a cache and pass it to our search routine.
use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
let dfa = DFA::new("foo[0-9]+")?;
let mut cache = dfa.create_cache();
let expected = Some(HalfMatch::must(0, 8));
assert_eq!(expected, dfa.try_search_fwd(
&mut cache, &Input::new("foo12345"))?,
);
Implementations§
source§impl DFA
impl DFA
sourcepub fn new(pattern: &str) -> Result<DFA, BuildError>
pub fn new(pattern: &str) -> Result<DFA, BuildError>
Parse the given regular expression using a default configuration and return the corresponding lazy DFA.
If you want a non-default configuration, then use the Builder
to
set your own configuration.
§Example
use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
let dfa = DFA::new("foo[0-9]+bar")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 11);
assert_eq!(
Some(expected),
dfa.try_search_fwd(&mut cache, &Input::new("foo12345bar"))?,
);
sourcepub fn new_many<P: AsRef<str>>(patterns: &[P]) -> Result<DFA, BuildError>
pub fn new_many<P: AsRef<str>>(patterns: &[P]) -> Result<DFA, BuildError>
Parse the given regular expressions using a default configuration and return the corresponding lazy multi-DFA.
If you want a non-default configuration, then use the Builder
to
set your own configuration.
§Example
use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
let dfa = DFA::new_many(&["[0-9]+", "[a-z]+"])?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(1, 3);
assert_eq!(
Some(expected),
dfa.try_search_fwd(&mut cache, &Input::new("foo12345bar"))?,
);
sourcepub fn always_match() -> Result<DFA, BuildError>
pub fn always_match() -> Result<DFA, BuildError>
Create a new lazy DFA that matches every input.
§Example
use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
let dfa = DFA::always_match()?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 0);
assert_eq!(Some(expected), dfa.try_search_fwd(
&mut cache, &Input::new(""))?,
);
assert_eq!(Some(expected), dfa.try_search_fwd(
&mut cache, &Input::new("foo"))?,
);
sourcepub fn never_match() -> Result<DFA, BuildError>
pub fn never_match() -> Result<DFA, BuildError>
Create a new lazy DFA that never matches any input.
§Example
use regex_automata::{hybrid::dfa::DFA, Input};
let dfa = DFA::never_match()?;
let mut cache = dfa.create_cache();
assert_eq!(None, dfa.try_search_fwd(&mut cache, &Input::new(""))?);
assert_eq!(None, dfa.try_search_fwd(&mut cache, &Input::new("foo"))?);
sourcepub fn config() -> Config
pub fn config() -> Config
Return a default configuration for a DFA
.
This is a convenience routine to avoid needing to import the Config
type when customizing the construction of a lazy DFA.
§Example
This example shows how to build a lazy DFA that heuristically supports Unicode word boundaries.
use regex_automata::{hybrid::dfa::DFA, HalfMatch, MatchError, Input};
let re = DFA::builder()
.configure(DFA::config().unicode_word_boundary(true))
.build(r"\b\w+\b")?;
let mut cache = re.create_cache();
// Since our haystack is all ASCII, the DFA search sees then and knows
// it is legal to interpret Unicode word boundaries as ASCII word
// boundaries.
let input = Input::new("!!foo!!");
let expected = HalfMatch::must(0, 5);
assert_eq!(Some(expected), re.try_search_fwd(&mut cache, &input)?);
// But if our haystack contains non-ASCII, then the search will fail
// with an error.
let input = Input::new("!!βββ!!");
let expected = MatchError::quit(b'\xCE', 2);
assert_eq!(Err(expected), re.try_search_fwd(&mut cache, &input));
sourcepub fn builder() -> Builder
pub fn builder() -> Builder
Return a builder for configuring the construction of a Regex
.
This is a convenience routine to avoid needing to import the
Builder
type in common cases.
§Example
This example shows how to use the builder to disable UTF-8 mode everywhere for lazy DFAs.
use regex_automata::{hybrid::dfa::DFA, util::syntax, HalfMatch, Input};
let re = DFA::builder()
.syntax(syntax::Config::new().utf8(false))
.build(r"foo(?-u:[^b])ar.*")?;
let mut cache = re.create_cache();
let input = Input::new(b"\xFEfoo\xFFarzz\xE2\x98\xFF\n");
let expected = Some(HalfMatch::must(0, 9));
let got = re.try_search_fwd(&mut cache, &input)?;
assert_eq!(expected, got);
sourcepub fn create_cache(&self) -> Cache
pub fn create_cache(&self) -> Cache
Create a new cache for this lazy DFA.
The cache returned should only be used for searches for this
lazy DFA. If you want to reuse the cache for another DFA, then
you must call Cache::reset
with that DFA (or, equivalently,
DFA::reset_cache
).
sourcepub fn reset_cache(&self, cache: &mut Cache)
pub fn reset_cache(&self, cache: &mut Cache)
Reset the given cache such that it can be used for searching with the this lazy DFA (and only this DFA).
A cache reset permits reusing memory already allocated in this cache with a different lazy DFA.
Resetting a cache sets its “clear count” to 0. This is relevant if the lazy DFA has been configured to “give up” after it has cleared the cache a certain number of times.
Any lazy state ID generated by the cache prior to resetting it is invalid after the reset.
§Example
This shows how to re-purpose a cache for use with a different DFA.
use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
let dfa1 = DFA::new(r"\w")?;
let dfa2 = DFA::new(r"\W")?;
let mut cache = dfa1.create_cache();
assert_eq!(
Some(HalfMatch::must(0, 2)),
dfa1.try_search_fwd(&mut cache, &Input::new("Δ"))?,
);
// Using 'cache' with dfa2 is not allowed. It may result in panics or
// incorrect results. In order to re-purpose the cache, we must reset
// it with the DFA we'd like to use it with.
//
// Similarly, after this reset, using the cache with 'dfa1' is also not
// allowed.
dfa2.reset_cache(&mut cache);
assert_eq!(
Some(HalfMatch::must(0, 3)),
dfa2.try_search_fwd(&mut cache, &Input::new("☃"))?,
);
sourcepub fn pattern_len(&self) -> usize
pub fn pattern_len(&self) -> usize
Returns the total number of patterns compiled into this lazy DFA.
In the case of a DFA that contains no patterns, this returns 0
.
§Example
This example shows the pattern length for a DFA that never matches:
use regex_automata::hybrid::dfa::DFA;
let dfa = DFA::never_match()?;
assert_eq!(dfa.pattern_len(), 0);
And another example for a DFA that matches at every position:
use regex_automata::hybrid::dfa::DFA;
let dfa = DFA::always_match()?;
assert_eq!(dfa.pattern_len(), 1);
And finally, a DFA that was constructed from multiple patterns:
use regex_automata::hybrid::dfa::DFA;
let dfa = DFA::new_many(&["[0-9]+", "[a-z]+", "[A-Z]+"])?;
assert_eq!(dfa.pattern_len(), 3);
sourcepub fn byte_classes(&self) -> &ByteClasses
pub fn byte_classes(&self) -> &ByteClasses
Returns the equivalence classes that make up the alphabet for this DFA.
Unless Config::byte_classes
was disabled, it is possible that
multiple distinct bytes are grouped into the same equivalence class
if it is impossible for them to discriminate between a match and a
non-match. This has the effect of reducing the overall alphabet size
and in turn potentially substantially reducing the size of the DFA’s
transition table.
The downside of using equivalence classes like this is that every state transition will automatically use this map to convert an arbitrary byte to its corresponding equivalence class. In practice this has a negligible impact on performance.
sourcepub fn get_config(&self) -> &Config
pub fn get_config(&self) -> &Config
Returns this lazy DFA’s configuration.
sourcepub fn memory_usage(&self) -> usize
pub fn memory_usage(&self) -> usize
Returns the memory usage, in bytes, of this lazy DFA.
This does not include the stack size used up by this lazy DFA. To
compute that, use std::mem::size_of::<DFA>()
. This also does not
include the size of the Cache
used.
This also does not include any heap memory used by the NFA inside of this hybrid NFA/DFA. This is because the NFA’s ownership is shared, and thus not owned by this hybrid NFA/DFA. More practically, several regex engines in this crate embed an NFA, and reporting the NFA’s memory usage in all of them would likely result in reporting higher heap memory than is actually used.
source§impl DFA
impl DFA
sourcepub fn try_search_fwd(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, MatchError>
pub fn try_search_fwd( &self, cache: &mut Cache, 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 lazy 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 lazy DFA quitting.
- The configuration of the lazy DFA may also permit it to “give up” on a search if it makes ineffective use of its transition table cache. The default configuration does not enable this by default, although it is typically a good idea to.
- 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 search.
use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
let dfa = DFA::new("foo[0-9]+")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 8);
assert_eq!(Some(expected), dfa.try_search_fwd(
&mut cache, &Input::new("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 later parts.
let dfa = DFA::new("abc|a")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 3);
assert_eq!(Some(expected), dfa.try_search_fwd(
&mut cache, &Input::new("abc"))?,
);
§Example: specific pattern search
This example shows how to build a lazy multi-DFA that permits searching for specific patterns.
use regex_automata::{
hybrid::dfa::DFA,
Anchored, HalfMatch, PatternID, Input,
};
let dfa = DFA::builder()
.configure(DFA::config().starts_for_each_pattern(true))
.build_many(&["[a-z0-9]{6}", "[a-z][a-z0-9]{5}"])?;
let mut cache = dfa.create_cache();
let haystack = "foo123";
// 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(&mut cache, &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 expected = Some(HalfMatch::must(1, 6));
let input = Input::new(haystack)
.anchored(Anchored::Pattern(PatternID::must(1)));
let got = dfa.try_search_fwd(&mut cache, &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::{hybrid::dfa::DFA, 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 since our haystack is pure ASCII.
let dfa = DFA::new(r"(?-u)\b[0-9]{3}\b")?;
let mut cache = dfa.create_cache();
let haystack = "foo123bar";
// 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.try_search_fwd(
&mut cache,
&Input::new(&haystack[3..6]),
)?;
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.try_search_fwd(
&mut cache,
&Input::new(haystack).range(3..6),
)?;
assert_eq!(expected, got);
sourcepub fn try_search_rev(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, MatchError>
pub fn try_search_rev( &self, cache: &mut Cache, 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 lazy 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 lazy DFA quitting.
- The configuration of the lazy DFA may also permit it to “give up” on a search if it makes ineffective use of its transition table cache. The default configuration does not enable this by default, although it is typically a good idea to.
- 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 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,
hybrid::dfa::DFA,
HalfMatch, Input,
};
let dfa = DFA::builder()
.thompson(thompson::Config::new().reverse(true))
.build("foo[0-9]+")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 0);
assert_eq!(
Some(expected),
dfa.try_search_rev(&mut cache, &Input::new("foo12345"))?,
);
// Even though a match is found after reading the last byte (`c`),
// the leftmost first match semantics demand that we find the earliest
// match that prefers earlier parts of the pattern over latter parts.
let dfa = DFA::builder()
.thompson(thompson::Config::new().reverse(true))
.build("abc|c")?;
let mut cache = dfa.create_cache();
let expected = HalfMatch::must(0, 0);
assert_eq!(Some(expected), dfa.try_search_rev(
&mut cache, &Input::new("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::{
hybrid::dfa::DFA,
nfa::thompson,
HalfMatch, Input, MatchKind,
};
let dfa = DFA::builder()
.thompson(thompson::Config::new().reverse(true))
.build(r"")?;
let mut cache = dfa.create_cache();
// Run the reverse DFA to collect all matches.
let mut input = Input::new("☃");
let mut matches = vec![];
loop {
match dfa.try_search_rev(&mut cache, &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 underlying NFA disabled:
use regex_automata::{
hybrid::dfa::DFA,
nfa::thompson,
HalfMatch, Input, MatchKind,
};
let dfa = DFA::builder()
.thompson(thompson::Config::new().reverse(true).utf8(false))
.build(r"")?;
let mut cache = dfa.create_cache();
// Run the reverse DFA to collect all matches.
let mut input = Input::new("☃");
let mut matches = vec![];
loop {
match dfa.try_search_rev(&mut cache, &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);
sourcepub fn try_search_overlapping_fwd(
&self,
cache: &mut Cache,
input: &Input<'_>,
state: &mut OverlappingState,
) -> Result<(), MatchError>
pub fn try_search_overlapping_fwd( &self, cache: &mut Cache, input: &Input<'_>, state: &mut OverlappingState, ) -> Result<(), MatchError>
Executes an overlapping forward search and returns the end position of
matches as they are found. If no match exists, then None
is returned.
This routine is principally only useful when searching for multiple patterns on inputs where multiple patterns may match the same regions of text. In particular, callers must preserve the automaton’s search state from prior calls so that the implementation knows where the last match occurred.
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 lazy 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 lazy DFA quitting.
- The configuration of the lazy DFA may also permit it to “give up” on a search if it makes ineffective use of its transition table cache. The default configuration does not enable this by default, although it is typically a good idea to.
- 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. Notice
that we build the automaton with a MatchKind::All
configuration.
Overlapping searches are unlikely to work as one would expect when
using the default MatchKind::LeftmostFirst
match semantics, since
leftmost-first matching is fundamentally incompatible with overlapping
searches. Namely, overlapping searches need to report matches as they
are seen, where as leftmost-first searches will continue searching even
after a match has been observed in order to find the conventional end
position of the match. More concretely, leftmost-first searches use
dead states to terminate a search after a specific match can no longer
be extended. Overlapping searches instead do the opposite by continuing
the search to find totally new matches (potentially of other patterns).
use regex_automata::{
hybrid::dfa::{DFA, OverlappingState},
HalfMatch, Input, MatchKind,
};
let dfa = DFA::builder()
.configure(DFA::config().match_kind(MatchKind::All))
.build_many(&[r"\w+$", r"\S+$"])?;
let mut cache = dfa.create_cache();
let haystack = "@foo";
let mut state = OverlappingState::start();
let expected = Some(HalfMatch::must(1, 4));
dfa.try_search_overlapping_fwd(
&mut cache, &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(
&mut cache, &Input::new(haystack), &mut state,
)?;
assert_eq!(expected, state.get_match());
sourcepub fn try_search_overlapping_rev(
&self,
cache: &mut Cache,
input: &Input<'_>,
state: &mut OverlappingState,
) -> Result<(), MatchError>
pub fn try_search_overlapping_rev( &self, cache: &mut Cache, input: &Input<'_>, state: &mut OverlappingState, ) -> Result<(), MatchError>
Executes a reverse overlapping search and returns the start of the
position of the leftmost match that is found. If no match exists, then
None
is returned.
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 lazy 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 lazy DFA quitting.
- The configuration of the lazy DFA may also permit it to “give up” on a search if it makes ineffective use of its transition table cache. The default configuration does not enable this by default, although it is typically a good idea to.
- 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::{
hybrid::dfa::{DFA, 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"☃"])?;
let mut cache = dfa.create_cache();
// 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(&mut cache, &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 underlying NFA disabled:
use regex_automata::{
hybrid::dfa::{DFA, 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"☃"])?;
let mut cache = dfa.create_cache();
// 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(&mut cache, &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);
sourcepub fn try_which_overlapping_matches(
&self,
cache: &mut Cache,
input: &Input<'_>,
patset: &mut PatternSet,
) -> Result<(), MatchError>
pub fn try_which_overlapping_matches( &self, cache: &mut Cache, 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 lazy 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 lazy DFA quitting.
- The configuration of the lazy DFA may also permit it to “give up” on a search if it makes ineffective use of its transition table cache. The default configuration does not enable this by default, although it is typically a good idea to.
- 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::{
hybrid::dfa::DFA,
Input, MatchKind, PatternSet,
};
let patterns = &[
r"\w+", r"\d+", r"\pL+", r"foo", r"bar", r"barfoo", r"foobar",
];
let dfa = DFA::builder()
.configure(DFA::config().match_kind(MatchKind::All))
.build_many(patterns)?;
let mut cache = dfa.create_cache();
let input = Input::new("foobar");
let mut patset = PatternSet::new(dfa.pattern_len());
dfa.try_which_overlapping_matches(&mut cache, &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);
source§impl DFA
impl DFA
sourcepub fn next_state(
&self,
cache: &mut Cache,
current: LazyStateID,
input: u8,
) -> Result<LazyStateID, CacheError>
pub fn next_state( &self, cache: &mut Cache, current: LazyStateID, input: u8, ) -> Result<LazyStateID, CacheError>
Transitions from the current state to the next state, given the next byte of input.
The given cache is used to either reuse pre-computed state transitions, or to store this newly computed transition for future reuse. Thus, this routine guarantees that it will never return a state ID that has an “unknown” tag.
§State identifier validity
The only valid value for current
is the lazy state ID returned
by the most recent call to next_state
, next_state_untagged
,
next_state_untagged_unchecked
, start_state_forward
or
state_state_reverse
for the given cache
. Any state ID returned from
prior calls to these routines (with the same cache
) is considered
invalid (even if it gives an appearance of working). State IDs returned
from any prior call for different cache
values are also always
invalid.
The returned ID is always a valid ID when current
refers to a valid
ID. Moreover, this routine is defined for all possible values of
input
.
These validity rules are not checked, even in debug mode. Callers are required to uphold these rules themselves.
Violating these state ID validity rules will not sacrifice memory safety, but may produce an incorrect result or a panic.
§Panics
If the given ID does not refer to a valid state, then this routine may panic but it also may not panic and instead return an invalid or incorrect ID.
§Example
This shows a simplistic example for walking a lazy DFA for a given
haystack by using the next_state
method.
use regex_automata::{hybrid::dfa::DFA, Input};
let dfa = DFA::new(r"[a-z]+r")?;
let mut cache = dfa.create_cache();
let haystack = "bar".as_bytes();
// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut sid = dfa.start_state_forward(
&mut cache, &Input::new(haystack),
)?;
// Walk all the bytes in the haystack.
for &b in haystack {
sid = dfa.next_state(&mut cache, sid, b)?;
}
// Matches are always delayed by 1 byte, so we must explicitly walk the
// special "EOI" transition at the end of the search.
sid = dfa.next_eoi_state(&mut cache, sid)?;
assert!(sid.is_match());
sourcepub fn next_state_untagged(
&self,
cache: &Cache,
current: LazyStateID,
input: u8,
) -> LazyStateID
pub fn next_state_untagged( &self, cache: &Cache, current: LazyStateID, input: u8, ) -> LazyStateID
Transitions from the current state to the next state, given the next byte of input and a state ID that is not tagged.
The only reason to use this routine is performance. In particular, the
next_state
method needs to do some additional checks, among them is
to account for identifiers to states that are not yet computed. In
such a case, the transition is computed on the fly. However, if it is
known that the current
state ID is untagged, then these checks can be
omitted.
Since this routine does not compute states on the fly, it does not
modify the cache and thus cannot return an error. Consequently, cache
does not need to be mutable and it is possible for this routine to
return a state ID corresponding to the special “unknown” state. In
this case, it is the caller’s responsibility to use the prior state
ID and input
with next_state
in order to force the computation of
the unknown transition. Otherwise, trying to use the “unknown” state
ID will just result in transitioning back to itself, and thus never
terminating. (This is technically a special exemption to the state ID
validity rules, but is permissible since this routine is guarateed to
never mutate the given cache
, and thus the identifier is guaranteed
to remain valid.)
See LazyStateID
for more details on what it means for a state ID
to be tagged. Also, see
next_state_untagged_unchecked
for this same idea, but with bounds checks forcefully elided.
§State identifier validity
The only valid value for current
is an untagged lazy
state ID returned by the most recent call to next_state
,
next_state_untagged
, next_state_untagged_unchecked
,
start_state_forward
or state_state_reverse
for the given cache
.
Any state ID returned from prior calls to these routines (with the
same cache
) is considered invalid (even if it gives an appearance
of working). State IDs returned from any prior call for different
cache
values are also always invalid.
The returned ID is always a valid ID when current
refers to a valid
ID, although it may be tagged. Moreover, this routine is defined for
all possible values of input
.
Not all validity rules are checked, even in debug mode. Callers are required to uphold these rules themselves.
Violating these state ID validity rules will not sacrifice memory safety, but may produce an incorrect result or a panic.
§Panics
If the given ID does not refer to a valid state, then this routine may panic but it also may not panic and instead return an invalid or incorrect ID.
§Example
This shows a simplistic example for walking a lazy DFA for a given
haystack by using the next_state_untagged
method where possible.
use regex_automata::{hybrid::dfa::DFA, Input};
let dfa = DFA::new(r"[a-z]+r")?;
let mut cache = dfa.create_cache();
let haystack = "bar".as_bytes();
// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut sid = dfa.start_state_forward(
&mut cache, &Input::new(haystack),
)?;
// Walk all the bytes in the haystack.
let mut at = 0;
while at < haystack.len() {
if sid.is_tagged() {
sid = dfa.next_state(&mut cache, sid, haystack[at])?;
} else {
let mut prev_sid = sid;
// We attempt to chew through as much as we can while moving
// through untagged state IDs. Thus, the transition function
// does less work on average per byte. (Unrolling this loop
// may help even more.)
while at < haystack.len() {
prev_sid = sid;
sid = dfa.next_state_untagged(
&mut cache, sid, haystack[at],
);
at += 1;
if sid.is_tagged() {
break;
}
}
// We must ensure that we never proceed to the next iteration
// with an unknown state ID. If we don't account for this
// case, then search isn't guaranteed to terminate since all
// transitions on unknown states loop back to itself.
if sid.is_unknown() {
sid = dfa.next_state(
&mut cache, prev_sid, haystack[at - 1],
)?;
}
}
}
// Matches are always delayed by 1 byte, so we must explicitly walk the
// special "EOI" transition at the end of the search.
sid = dfa.next_eoi_state(&mut cache, sid)?;
assert!(sid.is_match());
sourcepub unsafe fn next_state_untagged_unchecked(
&self,
cache: &Cache,
current: LazyStateID,
input: u8,
) -> LazyStateID
pub unsafe fn next_state_untagged_unchecked( &self, cache: &Cache, current: LazyStateID, input: u8, ) -> LazyStateID
Transitions from the current state to the next state, eliding bounds checks, given the next byte of input and a state ID that is not tagged.
The only reason to use this routine is performance. In particular, the
next_state
method needs to do some additional checks, among them is
to account for identifiers to states that are not yet computed. In
such a case, the transition is computed on the fly. However, if it is
known that the current
state ID is untagged, then these checks can be
omitted.
Since this routine does not compute states on the fly, it does not
modify the cache and thus cannot return an error. Consequently, cache
does not need to be mutable and it is possible for this routine to
return a state ID corresponding to the special “unknown” state. In
this case, it is the caller’s responsibility to use the prior state
ID and input
with next_state
in order to force the computation of
the unknown transition. Otherwise, trying to use the “unknown” state
ID will just result in transitioning back to itself, and thus never
terminating. (This is technically a special exemption to the state ID
validity rules, but is permissible since this routine is guarateed to
never mutate the given cache
, and thus the identifier is guaranteed
to remain valid.)
See LazyStateID
for more details on what it means for a state ID
to be tagged. Also, see
next_state_untagged
for this same idea, but with memory safety guaranteed by retaining
bounds checks.
§State identifier validity
The only valid value for current
is an untagged lazy
state ID returned by the most recent call to next_state
,
next_state_untagged
, next_state_untagged_unchecked
,
start_state_forward
or state_state_reverse
for the given cache
.
Any state ID returned from prior calls to these routines (with the
same cache
) is considered invalid (even if it gives an appearance
of working). State IDs returned from any prior call for different
cache
values are also always invalid.
The returned ID is always a valid ID when current
refers to a valid
ID, although it may be tagged. Moreover, this routine is defined for
all possible values of input
.
Not all validity rules are checked, even in debug mode. Callers are required to uphold these rules themselves.
Violating these state ID validity rules will not sacrifice memory safety, but may produce an incorrect result or a panic.
§Safety
Callers of this method must guarantee that current
refers to a valid
state ID according to the rules described above. If current
is not a
valid state ID for this automaton, then calling this routine may result
in undefined behavior.
If current
is valid, then the ID returned is valid for all possible
values of input
.
sourcepub fn next_eoi_state(
&self,
cache: &mut Cache,
current: LazyStateID,
) -> Result<LazyStateID, CacheError>
pub fn next_eoi_state( &self, cache: &mut Cache, current: LazyStateID, ) -> Result<LazyStateID, CacheError>
Transitions from the current state to the next state for the special EOI symbol.
The given cache is used to either reuse pre-computed state transitions, or to store this newly computed transition for future reuse. Thus, this routine guarantees that it will never return a state ID that has an “unknown” tag.
This routine must be called at the end of every search in a correct implementation of search. Namely, lazy DFAs in this crate delay matches by one byte in order to support look-around operators. Thus, after reaching the end of a haystack, a search implementation must follow one last EOI transition.
It is best to think of EOI as an additional symbol in the alphabet of a
DFA that is distinct from every other symbol. That is, the alphabet of
lazy DFAs in this crate has a logical size of 257 instead of 256, where
256 corresponds to every possible inhabitant of u8
. (In practice, the
physical alphabet size may be smaller because of alphabet compression
via equivalence classes, but EOI is always represented somehow in the
alphabet.)
§State identifier validity
The only valid value for current
is the lazy state ID returned
by the most recent call to next_state
, next_state_untagged
,
next_state_untagged_unchecked
, start_state_forward
or
state_state_reverse
for the given cache
. Any state ID returned from
prior calls to these routines (with the same cache
) is considered
invalid (even if it gives an appearance of working). State IDs returned
from any prior call for different cache
values are also always
invalid.
The returned ID is always a valid ID when current
refers to a valid
ID.
These validity rules are not checked, even in debug mode. Callers are required to uphold these rules themselves.
Violating these state ID validity rules will not sacrifice memory safety, but may produce an incorrect result or a panic.
§Panics
If the given ID does not refer to a valid state, then this routine may panic but it also may not panic and instead return an invalid or incorrect ID.
§Example
This shows a simplistic example for walking a DFA for a given haystack, and then finishing the search with the final EOI transition.
use regex_automata::{hybrid::dfa::DFA, Input};
let dfa = DFA::new(r"[a-z]+r")?;
let mut cache = dfa.create_cache();
let haystack = "bar".as_bytes();
// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut sid = dfa.start_state_forward(
&mut cache, &Input::new(haystack),
)?;
// Walk all the bytes in the haystack.
for &b in haystack {
sid = dfa.next_state(&mut cache, sid, b)?;
}
// Matches are always delayed by 1 byte, so we must explicitly walk
// the special "EOI" transition at the end of the search. Without this
// final transition, the assert below will fail since the DFA will not
// have entered a match state yet!
sid = dfa.next_eoi_state(&mut cache, sid)?;
assert!(sid.is_match());
sourcepub fn start_state(
&self,
cache: &mut Cache,
config: &Config,
) -> Result<LazyStateID, StartError>
pub fn start_state( &self, cache: &mut Cache, config: &Config, ) -> Result<LazyStateID, StartError>
Return the ID of the start state for this lazy DFA for the given starting configuration.
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. - Whether a “look-behind” byte exists. For example, the
^
anchor matches if and only if there is no look-behind byte. - The specific value of that look-behind byte. For example, a
(?m:^)
assertion only matches when there is either no look-behind byte, or when the look-behind byte is a line terminator.
The starting configuration provides the above information.
This routine can be used for either forward or reverse searches.
Although, as a convenience, if you have an Input
, then it
may be more succinct to use DFA::start_state_forward
or
DFA::start_state_reverse
. Note, for example, that the convenience
routines return a MatchError
on failure where as this routine
returns a StartError
.
§Errors
This may return a StartError
if the search needs to give up when
determining the start state (for example, if it sees a “quit” byte
or if the cache has become inefficient). This can also return an
error if the given configuration contains an unsupported Anchored
configuration.
sourcepub fn start_state_forward(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<LazyStateID, MatchError>
pub fn start_state_forward( &self, cache: &mut Cache, input: &Input<'_>, ) -> Result<LazyStateID, MatchError>
Return the ID of the start state for this lazy DFA when executing a forward search.
This is a convenience routine for calling DFA::start_state
that
converts the given Input
to a start configuration.
Additionally, if an error occurs, it is converted from a StartError
to a MatchError
using the offset information in the given
Input
.
§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 or
if the cache has become inefficient). This can also return an error if
the given Input
contains an unsupported Anchored
configuration.
sourcepub fn start_state_reverse(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<LazyStateID, MatchError>
pub fn start_state_reverse( &self, cache: &mut Cache, input: &Input<'_>, ) -> Result<LazyStateID, MatchError>
Return the ID of the start state for this lazy DFA when executing a reverse search.
This is a convenience routine for calling DFA::start_state
that
converts the given Input
to a start configuration.
Additionally, if an error occurs, it is converted from a StartError
to a MatchError
using the offset information in the given
Input
.
§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 or
if the cache has become inefficient). This can also return an error if
the given Input
contains an unsupported Anchored
configuration.
sourcepub fn match_len(&self, cache: &Cache, id: LazyStateID) -> usize
pub fn match_len(&self, cache: &Cache, id: LazyStateID) -> usize
Returns the total number of patterns that match in this state.
If the lazy DFA was compiled with one pattern, then this must
necessarily always return 1
for all match states.
A lazy DFA guarantees that DFA::match_pattern
can be called with
indices up to (but not including) the length returned by this routine
without panicking.
§Panics
If the given state is not a match state, then this may either panic or return an incorrect result.
§Example
This example shows a simple instance of implementing overlapping matches. In particular, it shows not only how to determine how many patterns have matched in a particular state, but also how to access which specific patterns have matched.
Notice that we must use MatchKind::All
when building the DFA. If we
used MatchKind::LeftmostFirst
instead, then the DFA would not be
constructed in a way that supports overlapping matches. (It would only
report a single pattern that matches at any particular point in time.)
Another thing to take note of is the patterns used and the order in
which the pattern IDs are reported. In the example below, pattern 3
is yielded first. Why? Because it corresponds to the match that
appears first. Namely, the @
symbol is part of \S+
but not part
of any of the other patterns. Since the \S+
pattern has a match that
starts to the left of any other pattern, its ID is returned before any
other.
use regex_automata::{hybrid::dfa::DFA, Input, MatchKind};
let dfa = DFA::builder()
.configure(DFA::config().match_kind(MatchKind::All))
.build_many(&[
r"\w+", r"[a-z]+", r"[A-Z]+", r"\S+",
])?;
let mut cache = dfa.create_cache();
let haystack = "@bar".as_bytes();
// The start state is determined by inspecting the position and the
// initial bytes of the haystack.
let mut sid = dfa.start_state_forward(
&mut cache, &Input::new(haystack),
)?;
// Walk all the bytes in the haystack.
for &b in haystack {
sid = dfa.next_state(&mut cache, sid, b)?;
}
sid = dfa.next_eoi_state(&mut cache, sid)?;
assert!(sid.is_match());
assert_eq!(dfa.match_len(&mut cache, sid), 3);
// The following calls are guaranteed to not panic since `match_len`
// returned `3` above.
assert_eq!(dfa.match_pattern(&mut cache, sid, 0).as_usize(), 3);
assert_eq!(dfa.match_pattern(&mut cache, sid, 1).as_usize(), 0);
assert_eq!(dfa.match_pattern(&mut cache, sid, 2).as_usize(), 1);
sourcepub fn match_pattern(
&self,
cache: &Cache,
id: LazyStateID,
match_index: usize,
) -> PatternID
pub fn match_pattern( &self, cache: &Cache, id: LazyStateID, match_index: usize, ) -> PatternID
Returns the pattern ID corresponding to the given match index in the given state.
See DFA::match_len
for an example of how to use this method
correctly. Note that if you know your lazy DFA is configured with a
single pattern, then this routine is never necessary since it will
always return a pattern ID of 0
for an index of 0
when id
corresponds to a match state.
Typically, this routine is used when implementing an overlapping
search, as the example for DFA::match_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 always produces a valid
PatternID
.
Trait Implementations§
Auto Trait Implementations§
impl Freeze for DFA
impl RefUnwindSafe for DFA
impl Send for DFA
impl Sync for DFA
impl Unpin for DFA
impl UnwindSafe for DFA
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)