Revision control
Copy as Markdown
Other Tools
/*!
Types and routines specific to dense DFAs.
This module is the home of [`dense::DFA`](DFA).
This module also contains a [`dense::Builder`](Builder) and a
[`dense::Config`](Config) for building and configuring a dense DFA.
*/
#[cfg(feature = "dfa-build")]
use core::cmp;
use core::{convert::TryFrom, fmt, iter, mem::size_of, slice};
#[cfg(feature = "dfa-build")]
use alloc::{
collections::{BTreeMap, BTreeSet},
vec,
vec::Vec,
};
#[cfg(feature = "dfa-build")]
use crate::{
dfa::{
accel::Accel, determinize, minimize::Minimizer, remapper::Remapper,
sparse,
},
nfa::thompson,
util::{look::LookMatcher, search::MatchKind},
};
use crate::{
dfa::{
accel::Accels,
automaton::{fmt_state_indicator, Automaton},
special::Special,
start::StartKind,
DEAD,
},
util::{
alphabet::{self, ByteClasses, ByteSet},
int::{Pointer, Usize},
prefilter::Prefilter,
primitives::{PatternID, StateID},
search::{Anchored, Input, MatchError},
start::{Start, StartByteMap},
wire::{self, DeserializeError, Endian, SerializeError},
},
};
/// The label that is pre-pended to a serialized DFA.
const LABEL: &str = "rust-regex-automata-dfa-dense";
/// The format version of dense regexes. This version gets incremented when a
/// change occurs. A change may not necessarily be a breaking change, but the
/// version does permit good error messages in the case where a breaking change
/// is made.
const VERSION: u32 = 2;
/// The configuration used for compiling a dense DFA.
///
/// As a convenience, [`DFA::config`] is an alias for [`Config::new`]. The
/// advantage of the former is that it often lets you avoid importing the
/// `Config` type directly.
///
/// A dense DFA configuration is a simple data object that is typically used
/// with [`dense::Builder::configure`](self::Builder::configure).
///
/// The default configuration guarantees that a search will never return
/// a "quit" error, although it is possible for a search to fail if
/// [`Config::starts_for_each_pattern`] wasn't enabled (which it is not by
/// default) and an [`Anchored::Pattern`] mode is requested via [`Input`].
#[cfg(feature = "dfa-build")]
#[derive(Clone, Debug, Default)]
pub struct Config {
// As with other configuration types in this crate, we put all our knobs
// in options so that we can distinguish between "default" and "not set."
// This makes it possible to easily combine multiple configurations
// without default values overwriting explicitly specified values. See the
// 'overwrite' method.
//
// For docs on the fields below, see the corresponding method setters.
accelerate: Option<bool>,
pre: Option<Option<Prefilter>>,
minimize: Option<bool>,
match_kind: Option<MatchKind>,
start_kind: Option<StartKind>,
starts_for_each_pattern: Option<bool>,
byte_classes: Option<bool>,
unicode_word_boundary: Option<bool>,
quitset: Option<ByteSet>,
specialize_start_states: Option<bool>,
dfa_size_limit: Option<Option<usize>>,
determinize_size_limit: Option<Option<usize>>,
}
#[cfg(feature = "dfa-build")]
impl Config {
/// Return a new default dense DFA compiler configuration.
pub fn new() -> Config {
Config::default()
}
/// Enable state acceleration.
///
/// When enabled, DFA construction will analyze each state to determine
/// whether it is eligible for simple acceleration. Acceleration typically
/// occurs when most of a state's transitions loop back to itself, leaving
/// only a select few bytes that will exit the state. When this occurs,
/// other routines like `memchr` can be used to look for those bytes which
/// may be much faster than traversing the DFA.
///
/// Callers may elect to disable this if consistent performance is more
/// desirable than variable performance. Namely, acceleration can sometimes
/// make searching slower than it otherwise would be if the transitions
/// that leave accelerated states are traversed frequently.
///
/// See [`Automaton::accelerator`](crate::dfa::Automaton::accelerator) for
/// an example.
///
/// This is enabled by default.
pub fn accelerate(mut self, yes: bool) -> Config {
self.accelerate = Some(yes);
self
}
/// Set a prefilter to be used whenever a start state is entered.
///
/// A [`Prefilter`] in this context is meant to accelerate searches by
/// looking for literal prefixes that every match for the corresponding
/// pattern (or patterns) must start with. Once a prefilter produces a
/// match, the underlying search routine continues on to try and confirm
/// the match.
///
/// Be warned that setting a prefilter does not guarantee that the search
/// will be faster. While it's usually a good bet, if the prefilter
/// produces a lot of false positive candidates (i.e., positions matched
/// by the prefilter but not by the regex), then the overall result can
/// be slower than if you had just executed the regex engine without any
/// prefilters.
///
/// Note that unless [`Config::specialize_start_states`] has been
/// explicitly set, then setting this will also enable (when `pre` is
/// `Some`) or disable (when `pre` is `None`) start state specialization.
/// This occurs because without start state specialization, a prefilter
/// is likely to be less effective. And without a prefilter, start state
/// specialization is usually pointless.
///
/// **WARNING:** Note that prefilters are not preserved as part of
/// serialization. Serializing a DFA will drop its prefilter.
///
/// By default no prefilter is set.
///
/// # Example
///
/// ```
/// use regex_automata::{
/// dfa::{dense::DFA, Automaton},
/// util::prefilter::Prefilter,
/// Input, HalfMatch, MatchKind,
/// };
///
/// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["foo", "bar"]);
/// let re = DFA::builder()
/// .configure(DFA::config().prefilter(pre))
/// .build(r"(foo|bar)[a-z]+")?;
/// let input = Input::new("foo1 barfox bar");
/// assert_eq!(
/// Some(HalfMatch::must(0, 11)),
/// re.try_search_fwd(&input)?,
/// );
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// Be warned though that an incorrect prefilter can lead to incorrect
/// results!
///
/// ```
/// use regex_automata::{
/// dfa::{dense::DFA, Automaton},
/// util::prefilter::Prefilter,
/// Input, HalfMatch, MatchKind,
/// };
///
/// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["foo", "car"]);
/// let re = DFA::builder()
/// .configure(DFA::config().prefilter(pre))
/// .build(r"(foo|bar)[a-z]+")?;
/// let input = Input::new("foo1 barfox bar");
/// assert_eq!(
/// // No match reported even though there clearly is one!
/// None,
/// re.try_search_fwd(&input)?,
/// );
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn prefilter(mut self, pre: Option<Prefilter>) -> Config {
self.pre = Some(pre);
if self.specialize_start_states.is_none() {
self.specialize_start_states =
Some(self.get_prefilter().is_some());
}
self
}
/// Minimize the DFA.
///
/// When enabled, the DFA built will be minimized such that it is as small
/// as possible.
///
/// Whether one enables minimization or not depends on the types of costs
/// you're willing to pay and how much you care about its benefits. In
/// particular, minimization has worst case `O(n*k*logn)` time and `O(k*n)`
/// space, where `n` is the number of DFA states and `k` is the alphabet
/// size. In practice, minimization can be quite costly in terms of both
/// space and time, so it should only be done if you're willing to wait
/// longer to produce a DFA. In general, you might want a minimal DFA in
/// the following circumstances:
///
/// 1. You would like to optimize for the size of the automaton. This can
/// manifest in one of two ways. Firstly, if you're converting the
/// DFA into Rust code (or a table embedded in the code), then a minimal
/// DFA will translate into a corresponding reduction in code size, and
/// thus, also the final compiled binary size. Secondly, if you are
/// building many DFAs and putting them on the heap, you'll be able to
/// fit more if they are smaller. Note though that building a minimal
/// DFA itself requires additional space; you only realize the space
/// savings once the minimal DFA is constructed (at which point, the
/// space used for minimization is freed).
/// 2. You've observed that a smaller DFA results in faster match
/// performance. Naively, this isn't guaranteed since there is no
/// inherent difference between matching with a bigger-than-minimal
/// DFA and a minimal DFA. However, a smaller DFA may make use of your
/// CPU's cache more efficiently.
/// 3. You are trying to establish an equivalence between regular
/// languages. The standard method for this is to build a minimal DFA
/// for each language and then compare them. If the DFAs are equivalent
/// (up to state renaming), then the languages are equivalent.
///
/// Typically, minimization only makes sense as an offline process. That
/// is, one might minimize a DFA before serializing it to persistent
/// storage. In practical terms, minimization can take around an order of
/// magnitude more time than compiling the initial DFA via determinization.
///
/// This option is disabled by default.
pub fn minimize(mut self, yes: bool) -> Config {
self.minimize = Some(yes);
self
}
/// Set the desired match semantics.
///
/// The default is [`MatchKind::LeftmostFirst`], which corresponds to the
/// match semantics of Perl-like regex engines. That is, when multiple
/// patterns would match at the same leftmost position, the pattern that
/// appears first in the concrete syntax is chosen.
///
/// Currently, the only other kind of match semantics supported is
/// [`MatchKind::All`]. This corresponds to classical DFA construction
/// where all possible matches are added to the DFA.
///
/// Typically, `All` is used when one wants to execute an overlapping
/// search and `LeftmostFirst` otherwise. In particular, it rarely makes
/// sense to use `All` with the various "leftmost" find routines, since the
/// leftmost routines depend on the `LeftmostFirst` automata construction
/// strategy. Specifically, `LeftmostFirst` adds dead states to the DFA
/// as a way to terminate the search and report a match. `LeftmostFirst`
/// also supports non-greedy matches using this strategy where as `All`
/// does not.
///
/// # Example: overlapping search
///
/// This example shows the typical use of `MatchKind::All`, which is to
/// report overlapping matches.
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// 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"\w+$", r"\S+$"])?;
/// let input = Input::new("@foo");
/// let mut state = OverlappingState::start();
///
/// let expected = Some(HalfMatch::must(1, 4));
/// dfa.try_search_overlapping_fwd(&input, &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, &mut state)?;
/// assert_eq!(expected, state.get_match());
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # Example: reverse automaton to find start of match
///
/// Another example for using `MatchKind::All` is for constructing a
/// reverse automaton to find the start of a match. `All` semantics are
/// used for this in order to find the longest possible match, which
/// corresponds to the leftmost starting position.
///
/// Note that if you need the starting position then
/// [`dfa::regex::Regex`](crate::dfa::regex::Regex) will handle this for
/// you, so it's usually not necessary to do this yourself.
///
/// ```
/// use regex_automata::{
/// dfa::{dense, Automaton, StartKind},
/// nfa::thompson::NFA,
/// Anchored, HalfMatch, Input, MatchKind,
/// };
///
/// let haystack = "123foobar456".as_bytes();
/// let pattern = r"[a-z]+r";
///
/// let dfa_fwd = dense::DFA::new(pattern)?;
/// let dfa_rev = dense::Builder::new()
/// .thompson(NFA::config().reverse(true))
/// .configure(dense::Config::new()
/// // This isn't strictly necessary since both anchored and
/// // unanchored searches are supported by default. But since
/// // finding the start-of-match only requires anchored searches,
/// // we can get rid of the unanchored configuration and possibly
/// // slim down our DFA considerably.
/// .start_kind(StartKind::Anchored)
/// .match_kind(MatchKind::All)
/// )
/// .build(pattern)?;
/// let expected_fwd = HalfMatch::must(0, 9);
/// let expected_rev = HalfMatch::must(0, 3);
/// let got_fwd = dfa_fwd.try_search_fwd(&Input::new(haystack))?.unwrap();
/// // Here we don't specify the pattern to search for since there's only
/// // one pattern and we're doing a leftmost search. But if this were an
/// // overlapping search, you'd need to specify the pattern that matched
/// // in the forward direction. (Otherwise, you might wind up finding the
/// // starting position of a match of some other pattern.) That in turn
/// // requires building the reverse automaton with starts_for_each_pattern
/// // enabled. Indeed, this is what Regex does internally.
/// let input = Input::new(haystack)
/// .range(..got_fwd.offset())
/// .anchored(Anchored::Yes);
/// let got_rev = dfa_rev.try_search_rev(&input)?.unwrap();
/// assert_eq!(expected_fwd, got_fwd);
/// assert_eq!(expected_rev, got_rev);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn match_kind(mut self, kind: MatchKind) -> Config {
self.match_kind = Some(kind);
self
}
/// The type of starting state configuration to use for a DFA.
///
/// By default, the starting state configuration is [`StartKind::Both`].
///
/// # Example
///
/// ```
/// use regex_automata::{
/// dfa::{dense::DFA, Automaton, StartKind},
/// Anchored, HalfMatch, Input,
/// };
///
/// let haystack = "quux foo123";
/// let expected = HalfMatch::must(0, 11);
///
/// // By default, DFAs support both anchored and unanchored searches.
/// let dfa = DFA::new(r"[0-9]+")?;
/// let input = Input::new(haystack);
/// assert_eq!(Some(expected), dfa.try_search_fwd(&input)?);
///
/// // But if we only need anchored searches, then we can build a DFA
/// // that only supports anchored searches. This leads to a smaller DFA
/// // (potentially significantly smaller in some cases), but a DFA that
/// // will panic if you try to use it with an unanchored search.
/// let dfa = DFA::builder()
/// .configure(DFA::config().start_kind(StartKind::Anchored))
/// .build(r"[0-9]+")?;
/// let input = Input::new(haystack)
/// .range(8..)
/// .anchored(Anchored::Yes);
/// assert_eq!(Some(expected), dfa.try_search_fwd(&input)?);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn start_kind(mut self, kind: StartKind) -> Config {
self.start_kind = Some(kind);
self
}
/// Whether to compile a separate start state for each pattern in the
/// automaton.
///
/// When enabled, a separate **anchored** start state is added for each
/// pattern in the DFA. When this start state is used, then the DFA will
/// only search for matches for the pattern specified, even if there are
/// other patterns in the DFA.
///
/// The main downside of this option is that it can potentially increase
/// the size of the DFA and/or increase the time it takes to build the DFA.
///
/// There are a few reasons one might want to enable this (it's disabled
/// by default):
///
/// 1. When looking for the start of an overlapping match (using a
/// reverse DFA), doing it correctly requires starting the reverse search
/// using the starting state of the pattern that matched in the forward
/// direction. Indeed, when building a [`Regex`](crate::dfa::regex::Regex),
/// it will automatically enable this option when building the reverse DFA
/// internally.
/// 2. When you want to use a DFA with multiple patterns to both search
/// for matches of any pattern or to search for anchored matches of one
/// particular pattern while using the same DFA. (Otherwise, you would need
/// to compile a new DFA for each pattern.)
/// 3. Since the start states added for each pattern are anchored, if you
/// compile an unanchored DFA with one pattern while also enabling this
/// option, then you can use the same DFA to perform anchored or unanchored
/// searches. The latter you get with the standard search APIs. The former
/// you get from the various `_at` search methods that allow you specify a
/// pattern ID to search for.
///
/// By default this is disabled.
///
/// # Example
///
/// This example shows how to use this option to permit the same DFA to
/// run both anchored and unanchored searches for a single pattern.
///
/// ```
/// use regex_automata::{
/// dfa::{dense, Automaton},
/// Anchored, HalfMatch, PatternID, Input,
/// };
///
/// let dfa = dense::Builder::new()
/// .configure(dense::Config::new().starts_for_each_pattern(true))
/// .build(r"foo[0-9]+")?;
/// let haystack = "quux foo123";
///
/// // Here's a normal unanchored search. Notice that we use 'None' for the
/// // pattern ID. Since the DFA was built as an unanchored machine, it
/// // use its default unanchored starting state.
/// let expected = HalfMatch::must(0, 11);
/// let input = Input::new(haystack);
/// assert_eq!(Some(expected), dfa.try_search_fwd(&input)?);
/// // But now if we explicitly specify the pattern to search ('0' being
/// // the only pattern in the DFA), then it will use the starting state
/// // for that specific pattern which is always anchored. Since the
/// // pattern doesn't have a match at the beginning of the haystack, we
/// // find nothing.
/// let input = Input::new(haystack)
/// .anchored(Anchored::Pattern(PatternID::must(0)));
/// assert_eq!(None, dfa.try_search_fwd(&input)?);
/// // And finally, an anchored search is not the same as putting a '^' at
/// // beginning of the pattern. An anchored search can only match at the
/// // beginning of the *search*, which we can change:
/// let input = Input::new(haystack)
/// .anchored(Anchored::Pattern(PatternID::must(0)))
/// .range(5..);
/// assert_eq!(Some(expected), dfa.try_search_fwd(&input)?);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn starts_for_each_pattern(mut self, yes: bool) -> Config {
self.starts_for_each_pattern = Some(yes);
self
}
/// Whether to attempt to shrink the size of the DFA's alphabet or not.
///
/// This option is enabled by default and should never be disabled unless
/// one is debugging a generated DFA.
///
/// When enabled, the DFA will use a map from all possible bytes to their
/// corresponding equivalence class. Each equivalence class represents a
/// set of bytes that does not discriminate between a match and a non-match
/// in the DFA. For example, the pattern `[ab]+` has at least two
/// equivalence classes: a set containing `a` and `b` and a set containing
/// every byte except for `a` and `b`. `a` and `b` are in the same
/// equivalence class because they never discriminate between a match and a
/// non-match.
///
/// The advantage of this map is that the size of the transition table
/// can be reduced drastically from `#states * 256 * sizeof(StateID)` to
/// `#states * k * sizeof(StateID)` where `k` is the number of equivalence
/// classes (rounded up to the nearest power of 2). As a result, total
/// space usage can decrease substantially. Moreover, since a smaller
/// alphabet is used, DFA compilation becomes faster as well.
///
/// **WARNING:** This is only useful for debugging DFAs. Disabling this
/// does not yield any speed advantages. Namely, even when this is
/// disabled, a byte class map is still used while searching. The only
/// difference is that every byte will be forced into its own distinct
/// equivalence class. This is useful for debugging the actual generated
/// transitions because it lets one see the transitions defined on actual
/// bytes instead of the equivalence classes.
pub fn byte_classes(mut self, yes: bool) -> Config {
self.byte_classes = Some(yes);
self
}
/// Heuristically enable Unicode word boundaries.
///
/// When set, this will attempt to implement Unicode word boundaries as if
/// they were ASCII word boundaries. This only works when the search input
/// is ASCII only. If a non-ASCII byte is observed while searching, then a
/// [`MatchError::quit`](crate::MatchError::quit) error is returned.
///
/// A possible alternative to enabling this option is to simply use an
/// ASCII word boundary, e.g., via `(?-u:\b)`. The main reason to use this
/// option is if you absolutely need Unicode support. This option lets one
/// use a fast search implementation (a DFA) for some potentially very
/// common cases, while providing the option to fall back to some other
/// regex engine to handle the general case when an error is returned.
///
/// If the pattern provided has no Unicode word boundary in it, then this
/// option has no effect. (That is, quitting on a non-ASCII byte only
/// occurs when this option is enabled _and_ a Unicode word boundary is
/// present in the pattern.)
///
/// This is almost equivalent to setting all non-ASCII bytes to be quit
/// bytes. The only difference is that this will cause non-ASCII bytes to
/// be quit bytes _only_ when a Unicode word boundary is present in the
/// pattern.
///
/// When enabling this option, callers _must_ be prepared to handle
/// a [`MatchError`](crate::MatchError) error during search.
/// When using a [`Regex`](crate::dfa::regex::Regex), this corresponds
/// to using the `try_` suite of methods. Alternatively, if
/// callers can guarantee that their input is ASCII only, then a
/// [`MatchError::quit`](crate::MatchError::quit) error will never be
/// returned while searching.
///
/// This is disabled by default.
///
/// # Example
///
/// This example shows how to heuristically enable Unicode word boundaries
/// in a pattern. It also shows what happens when a search comes across a
/// non-ASCII byte.
///
/// ```
/// use regex_automata::{
/// dfa::{Automaton, dense},
/// HalfMatch, Input, MatchError,
/// };
///
/// let dfa = dense::Builder::new()
/// .configure(dense::Config::new().unicode_word_boundary(true))
/// .build(r"\b[0-9]+\b")?;
///
/// // The match occurs before the search ever observes the snowman
/// // character, so no error occurs.
/// let haystack = "foo 123 ☃".as_bytes();
/// let expected = Some(HalfMatch::must(0, 7));
/// let got = dfa.try_search_fwd(&Input::new(haystack))?;
/// assert_eq!(expected, got);
///
/// // Notice that this search fails, even though the snowman character
/// // occurs after the ending match offset. This is because search
/// // routines read one byte past the end of the search to account for
/// // look-around, and indeed, this is required here to determine whether
/// // the trailing \b matches.
/// let haystack = "foo 123 ☃".as_bytes();
/// let expected = MatchError::quit(0xE2, 8);
/// let got = dfa.try_search_fwd(&Input::new(haystack));
/// assert_eq!(Err(expected), got);
///
/// // Another example is executing a search where the span of the haystack
/// // we specify is all ASCII, but there is non-ASCII just before it. This
/// // correctly also reports an error.
/// let input = Input::new("β123").range(2..);
/// let expected = MatchError::quit(0xB2, 1);
/// let got = dfa.try_search_fwd(&input);
/// assert_eq!(Err(expected), got);
///
/// // And similarly for the trailing word boundary.
/// let input = Input::new("123β").range(..3);
/// let expected = MatchError::quit(0xCE, 3);
/// let got = dfa.try_search_fwd(&input);
/// assert_eq!(Err(expected), got);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn unicode_word_boundary(mut self, yes: bool) -> Config {
// We have a separate option for this instead of just setting the
// appropriate quit bytes here because we don't want to set quit bytes
// for every regex. We only want to set them when the regex contains a
// Unicode word boundary.
self.unicode_word_boundary = Some(yes);
self
}
/// Add a "quit" byte to the DFA.
///
/// When a quit byte is seen during search time, then search will return
/// a [`MatchError::quit`](crate::MatchError::quit) error indicating the
/// offset at which the search stopped.
///
/// A quit byte will always overrule any other aspects of a regex. For
/// example, if the `x` byte is added as a quit byte and the regex `\w` is
/// used, then observing `x` will cause the search to quit immediately
/// despite the fact that `x` is in the `\w` class.
///
/// This mechanism is primarily useful for heuristically enabling certain
/// features like Unicode word boundaries in a DFA. Namely, if the input
/// to search is ASCII, then a Unicode word boundary can be implemented
/// via an ASCII word boundary with no change in semantics. Thus, a DFA
/// can attempt to match a Unicode word boundary but give up as soon as it
/// observes a non-ASCII byte. Indeed, if callers set all non-ASCII bytes
/// to be quit bytes, then Unicode word boundaries will be permitted when
/// building DFAs. Of course, callers should enable
/// [`Config::unicode_word_boundary`] if they want this behavior instead.
/// (The advantage being that non-ASCII quit bytes will only be added if a
/// Unicode word boundary is in the pattern.)
///
/// When enabling this option, callers _must_ be prepared to handle a
/// [`MatchError`](crate::MatchError) error during search. When using a
/// [`Regex`](crate::dfa::regex::Regex), this corresponds to using the
/// `try_` suite of methods.
///
/// By default, there are no quit bytes set.
///
/// # Panics
///
/// This panics if heuristic Unicode word boundaries are enabled and any
/// non-ASCII byte is removed from the set of quit bytes. Namely, enabling
/// Unicode word boundaries requires setting every non-ASCII byte to a quit
/// byte. So if the caller attempts to undo any of that, then this will
/// panic.
///
/// # Example
///
/// This example shows how to cause a search to terminate if it sees a
/// `\n` byte. This could be useful if, for example, you wanted to prevent
/// a user supplied pattern from matching across a line boundary.
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// use regex_automata::{dfa::{Automaton, dense}, Input, MatchError};
///
/// let dfa = dense::Builder::new()
/// .configure(dense::Config::new().quit(b'\n', true))
/// .build(r"foo\p{any}+bar")?;
///
/// let haystack = "foo\nbar".as_bytes();
/// // Normally this would produce a match, since \p{any} contains '\n'.
/// // But since we instructed the automaton to enter a quit state if a
/// // '\n' is observed, this produces a match error instead.
/// let expected = MatchError::quit(b'\n', 3);
/// let got = dfa.try_search_fwd(&Input::new(haystack)).unwrap_err();
/// assert_eq!(expected, got);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn quit(mut self, byte: u8, yes: bool) -> Config {
if self.get_unicode_word_boundary() && !byte.is_ascii() && !yes {
panic!(
"cannot set non-ASCII byte to be non-quit when \
Unicode word boundaries are enabled"
);
}
if self.quitset.is_none() {
self.quitset = Some(ByteSet::empty());
}
if yes {
self.quitset.as_mut().unwrap().add(byte);
} else {
self.quitset.as_mut().unwrap().remove(byte);
}
self
}
/// Enable specializing start states in the DFA.
///
/// When start states are specialized, an implementor of a search routine
/// using a lazy DFA can tell when the search has entered a starting state.
/// When start states aren't specialized, then it is impossible to know
/// whether the search has entered a start state.
///
/// Ideally, this option wouldn't need to exist and we could always
/// specialize start states. The problem is that start states can be quite
/// active. This in turn means that an efficient search routine is likely
/// to ping-pong between a heavily optimized hot loop that handles most
/// states and to a less optimized specialized handling of start states.
/// This causes branches to get heavily mispredicted and overall can
/// materially decrease throughput. Therefore, specializing start states
/// should only be enabled when it is needed.
///
/// Knowing whether a search is in a start state is typically useful when a
/// prefilter is active for the search. A prefilter is typically only run
/// when in a start state and a prefilter can greatly accelerate a search.
/// Therefore, the possible cost of specializing start states is worth it
/// in this case. Otherwise, if you have no prefilter, there is likely no
/// reason to specialize start states.
///
/// This is disabled by default, but note that it is automatically
/// enabled (or disabled) if [`Config::prefilter`] is set. Namely, unless
/// `specialize_start_states` has already been set, [`Config::prefilter`]
/// will automatically enable or disable it based on whether a prefilter
/// is present or not, respectively. This is done because a prefilter's
/// effectiveness is rooted in being executed whenever the DFA is in a
/// start state, and that's only possible to do when they are specialized.
///
/// Note that it is plausibly reasonable to _disable_ this option
/// explicitly while _enabling_ a prefilter. In that case, a prefilter
/// will still be run at the beginning of a search, but never again. This
/// in theory could strike a good balance if you're in a situation where a
/// prefilter is likely to produce many false positive candidates.
///
/// # Example
///
/// This example shows how to enable start state specialization and then
/// shows how to check whether a state is a start state or not.
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, Input};
///
/// let dfa = DFA::builder()
/// .configure(DFA::config().specialize_start_states(true))
/// .build(r"[a-z]+")?;
///
/// let haystack = "123 foobar 4567".as_bytes();
/// let sid = dfa.start_state_forward(&Input::new(haystack))?;
/// // The ID returned by 'start_state_forward' will always be tagged as
/// // a start state when start state specialization is enabled.
/// assert!(dfa.is_special_state(sid));
/// assert!(dfa.is_start_state(sid));
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// Compare the above with the default DFA configuration where start states
/// are _not_ specialized. In this case, the start state is not tagged at
/// all:
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, Input};
///
/// let dfa = DFA::new(r"[a-z]+")?;
///
/// let haystack = "123 foobar 4567";
/// let sid = dfa.start_state_forward(&Input::new(haystack))?;
/// // Start states are not special in the default configuration!
/// assert!(!dfa.is_special_state(sid));
/// assert!(!dfa.is_start_state(sid));
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn specialize_start_states(mut self, yes: bool) -> Config {
self.specialize_start_states = Some(yes);
self
}
/// Set a size limit on the total heap used by a DFA.
///
/// This size limit is expressed in bytes and is applied during
/// determinization of an NFA into a DFA. If the DFA's heap usage, and only
/// the DFA, exceeds this configured limit, then determinization is stopped
/// and an error is returned.
///
/// This limit does not apply to auxiliary storage used during
/// determinization that isn't part of the generated DFA.
///
/// This limit is only applied during determinization. Currently, there is
/// no way to post-pone this check to after minimization if minimization
/// was enabled.
///
/// The total limit on heap used during determinization is the sum of the
/// DFA and determinization size limits.
///
/// The default is no limit.
///
/// # Example
///
/// This example shows a DFA that fails to build because of a configured
/// size limit. This particular example also serves as a cautionary tale
/// demonstrating just how big DFAs with large Unicode character classes
/// can get.
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// use regex_automata::{dfa::{dense, Automaton}, Input};
///
/// // 6MB isn't enough!
/// dense::Builder::new()
/// .configure(dense::Config::new().dfa_size_limit(Some(6_000_000)))
/// .build(r"\w{20}")
/// .unwrap_err();
///
/// // ... but 7MB probably is!
/// // (Note that DFA sizes aren't necessarily stable between releases.)
/// let dfa = dense::Builder::new()
/// .configure(dense::Config::new().dfa_size_limit(Some(7_000_000)))
/// .build(r"\w{20}")?;
/// let haystack = "A".repeat(20).into_bytes();
/// assert!(dfa.try_search_fwd(&Input::new(&haystack))?.is_some());
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// While one needs a little more than 6MB to represent `\w{20}`, it
/// turns out that you only need a little more than 6KB to represent
/// `(?-u:\w{20})`. So only use Unicode if you need it!
///
/// As with [`Config::determinize_size_limit`], the size of a DFA is
/// influenced by other factors, such as what start state configurations
/// to support. For example, if you only need unanchored searches and not
/// anchored searches, then configuring the DFA to only support unanchored
/// searches can reduce its size. By default, DFAs support both unanchored
/// and anchored searches.
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// use regex_automata::{dfa::{dense, Automaton, StartKind}, Input};
///
/// // 3MB isn't enough!
/// dense::Builder::new()
/// .configure(dense::Config::new()
/// .dfa_size_limit(Some(3_000_000))
/// .start_kind(StartKind::Unanchored)
/// )
/// .build(r"\w{20}")
/// .unwrap_err();
///
/// // ... but 4MB probably is!
/// // (Note that DFA sizes aren't necessarily stable between releases.)
/// let dfa = dense::Builder::new()
/// .configure(dense::Config::new()
/// .dfa_size_limit(Some(4_000_000))
/// .start_kind(StartKind::Unanchored)
/// )
/// .build(r"\w{20}")?;
/// let haystack = "A".repeat(20).into_bytes();
/// assert!(dfa.try_search_fwd(&Input::new(&haystack))?.is_some());
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn dfa_size_limit(mut self, bytes: Option<usize>) -> Config {
self.dfa_size_limit = Some(bytes);
self
}
/// Set a size limit on the total heap used by determinization.
///
/// This size limit is expressed in bytes and is applied during
/// determinization of an NFA into a DFA. If the heap used for auxiliary
/// storage during determinization (memory that is not in the DFA but
/// necessary for building the DFA) exceeds this configured limit, then
/// determinization is stopped and an error is returned.
///
/// This limit does not apply to heap used by the DFA itself.
///
/// The total limit on heap used during determinization is the sum of the
/// DFA and determinization size limits.
///
/// The default is no limit.
///
/// # Example
///
/// This example shows a DFA that fails to build because of a
/// configured size limit on the amount of heap space used by
/// determinization. This particular example complements the example for
/// [`Config::dfa_size_limit`] by demonstrating that not only does Unicode
/// potentially make DFAs themselves big, but it also results in more
/// auxiliary storage during determinization. (Although, auxiliary storage
/// is still not as much as the DFA itself.)
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// # if !cfg!(target_pointer_width = "64") { return Ok(()); } // see #1039
/// use regex_automata::{dfa::{dense, Automaton}, Input};
///
/// // 600KB isn't enough!
/// dense::Builder::new()
/// .configure(dense::Config::new()
/// .determinize_size_limit(Some(600_000))
/// )
/// .build(r"\w{20}")
/// .unwrap_err();
///
/// // ... but 700KB probably is!
/// // (Note that auxiliary storage sizes aren't necessarily stable between
/// // releases.)
/// let dfa = dense::Builder::new()
/// .configure(dense::Config::new()
/// .determinize_size_limit(Some(700_000))
/// )
/// .build(r"\w{20}")?;
/// let haystack = "A".repeat(20).into_bytes();
/// assert!(dfa.try_search_fwd(&Input::new(&haystack))?.is_some());
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// Note that some parts of the configuration on a DFA can have a
/// big impact on how big the DFA is, and thus, how much memory is
/// used. For example, the default setting for [`Config::start_kind`] is
/// [`StartKind::Both`]. But if you only need an anchored search, for
/// example, then it can be much cheaper to build a DFA that only supports
/// anchored searches. (Running an unanchored search with it would panic.)
///
/// ```
/// # if cfg!(miri) { return Ok(()); } // miri takes too long
/// # if !cfg!(target_pointer_width = "64") { return Ok(()); } // see #1039
/// use regex_automata::{
/// dfa::{dense, Automaton, StartKind},
/// Anchored, Input,
/// };
///
/// // 200KB isn't enough!
/// dense::Builder::new()
/// .configure(dense::Config::new()
/// .determinize_size_limit(Some(200_000))
/// .start_kind(StartKind::Anchored)
/// )
/// .build(r"\w{20}")
/// .unwrap_err();
///
/// // ... but 300KB probably is!
/// // (Note that auxiliary storage sizes aren't necessarily stable between
/// // releases.)
/// let dfa = dense::Builder::new()
/// .configure(dense::Config::new()
/// .determinize_size_limit(Some(300_000))
/// .start_kind(StartKind::Anchored)
/// )
/// .build(r"\w{20}")?;
/// let haystack = "A".repeat(20).into_bytes();
/// let input = Input::new(&haystack).anchored(Anchored::Yes);
/// assert!(dfa.try_search_fwd(&input)?.is_some());
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn determinize_size_limit(mut self, bytes: Option<usize>) -> Config {
self.determinize_size_limit = Some(bytes);
self
}
/// Returns whether this configuration has enabled simple state
/// acceleration.
pub fn get_accelerate(&self) -> bool {
self.accelerate.unwrap_or(true)
}
/// Returns the prefilter attached to this configuration, if any.
pub fn get_prefilter(&self) -> Option<&Prefilter> {
self.pre.as_ref().unwrap_or(&None).as_ref()
}
/// Returns whether this configuration has enabled the expensive process
/// of minimizing a DFA.
pub fn get_minimize(&self) -> bool {
self.minimize.unwrap_or(false)
}
/// Returns the match semantics set in this configuration.
pub fn get_match_kind(&self) -> MatchKind {
self.match_kind.unwrap_or(MatchKind::LeftmostFirst)
}
/// Returns the starting state configuration for a DFA.
pub fn get_starts(&self) -> StartKind {
self.start_kind.unwrap_or(StartKind::Both)
}
/// Returns whether this configuration has enabled anchored starting states
/// for every pattern in the DFA.
pub fn get_starts_for_each_pattern(&self) -> bool {
self.starts_for_each_pattern.unwrap_or(false)
}
/// Returns whether this configuration has enabled byte classes or not.
/// This is typically a debugging oriented option, as disabling it confers
/// no speed benefit.
pub fn get_byte_classes(&self) -> bool {
self.byte_classes.unwrap_or(true)
}
/// Returns whether this configuration has enabled heuristic Unicode word
/// boundary support. When enabled, it is possible for a search to return
/// an error.
pub fn get_unicode_word_boundary(&self) -> bool {
self.unicode_word_boundary.unwrap_or(false)
}
/// Returns whether this configuration will instruct the DFA to enter a
/// quit state whenever the given byte is seen during a search. When at
/// least one byte has this enabled, it is possible for a search to return
/// an error.
pub fn get_quit(&self, byte: u8) -> bool {
self.quitset.map_or(false, |q| q.contains(byte))
}
/// Returns whether this configuration will instruct the DFA to
/// "specialize" start states. When enabled, the DFA will mark start states
/// as "special" so that search routines using the DFA can detect when
/// it's in a start state and do some kind of optimization (like run a
/// prefilter).
pub fn get_specialize_start_states(&self) -> bool {
self.specialize_start_states.unwrap_or(false)
}
/// Returns the DFA size limit of this configuration if one was set.
/// The size limit is total number of bytes on the heap that a DFA is
/// permitted to use. If the DFA exceeds this limit during construction,
/// then construction is stopped and an error is returned.
pub fn get_dfa_size_limit(&self) -> Option<usize> {
self.dfa_size_limit.unwrap_or(None)
}
/// Returns the determinization size limit of this configuration if one
/// was set. The size limit is total number of bytes on the heap that
/// determinization is permitted to use. If determinization exceeds this
/// limit during construction, then construction is stopped and an error is
/// returned.
///
/// This is different from the DFA size limit in that this only applies to
/// the auxiliary storage used during determinization. Once determinization
/// is complete, this memory is freed.
///
/// The limit on the total heap memory used is the sum of the DFA and
/// determinization size limits.
pub fn get_determinize_size_limit(&self) -> Option<usize> {
self.determinize_size_limit.unwrap_or(None)
}
/// Overwrite the default configuration such that the options in `o` are
/// always used. If an option in `o` is not set, then the corresponding
/// option in `self` is used. If it's not set in `self` either, then it
/// remains not set.
pub(crate) fn overwrite(&self, o: Config) -> Config {
Config {
accelerate: o.accelerate.or(self.accelerate),
pre: o.pre.or_else(|| self.pre.clone()),
minimize: o.minimize.or(self.minimize),
match_kind: o.match_kind.or(self.match_kind),
start_kind: o.start_kind.or(self.start_kind),
starts_for_each_pattern: o
.starts_for_each_pattern
.or(self.starts_for_each_pattern),
byte_classes: o.byte_classes.or(self.byte_classes),
unicode_word_boundary: o
.unicode_word_boundary
.or(self.unicode_word_boundary),
quitset: o.quitset.or(self.quitset),
specialize_start_states: o
.specialize_start_states
.or(self.specialize_start_states),
dfa_size_limit: o.dfa_size_limit.or(self.dfa_size_limit),
determinize_size_limit: o
.determinize_size_limit
.or(self.determinize_size_limit),
}
}
}
/// A builder for constructing a deterministic finite automaton from regular
/// expressions.
///
/// This builder provides two main things:
///
/// 1. It provides a few different `build` routines for actually constructing
/// a DFA from different kinds of inputs. The most convenient is
/// [`Builder::build`], which builds a DFA directly from a pattern string. The
/// most flexible is [`Builder::build_from_nfa`], which builds a DFA straight
/// from an NFA.
/// 2. The builder permits configuring a number of things.
/// [`Builder::configure`] is used with [`Config`] to configure aspects of
/// the DFA and the construction process itself. [`Builder::syntax`] and
/// [`Builder::thompson`] permit configuring the regex parser and Thompson NFA
/// construction, respectively. The syntax and thompson configurations only
/// apply when building from a pattern string.
///
/// This builder always constructs a *single* DFA. As such, this builder
/// can only be used to construct regexes that either detect the presence
/// of a match or find the end location of a match. A single DFA cannot
/// produce both the start and end of a match. For that information, use a
/// [`Regex`](crate::dfa::regex::Regex), which can be similarly configured
/// using [`regex::Builder`](crate::dfa::regex::Builder). The main reason to
/// use a DFA directly is if the end location of a match is enough for your use
/// case. Namely, a `Regex` will construct two DFAs instead of one, since a
/// second reverse DFA is needed to find the start of a match.
///
/// Note that if one wants to build a sparse DFA, you must first build a dense
/// DFA and convert that to a sparse DFA. There is no way to build a sparse
/// DFA without first building a dense DFA.
///
/// # Example
///
/// This example shows how to build a minimized DFA that completely disables
/// Unicode. That is:
///
/// * Things such as `\w`, `.` and `\b` are no longer Unicode-aware. `\w`
/// and `\b` are ASCII-only while `.` matches any byte except for `\n`
/// (instead of any UTF-8 encoding of a Unicode scalar value except for
/// `\n`). Things that are Unicode only, such as `\pL`, are not allowed.
/// * The pattern itself is permitted to match invalid UTF-8. For example,
/// things like `[^a]` that match any byte except for `a` are permitted.
///
/// ```
/// use regex_automata::{
/// dfa::{Automaton, dense},
/// util::syntax,
/// HalfMatch, Input,
/// };
///
/// let dfa = dense::Builder::new()
/// .configure(dense::Config::new().minimize(false))
/// .syntax(syntax::Config::new().unicode(false).utf8(false))
/// .build(r"foo[^b]ar.*")?;
///
/// let haystack = b"\xFEfoo\xFFar\xE2\x98\xFF\n";
/// let expected = Some(HalfMatch::must(0, 10));
/// let got = dfa.try_search_fwd(&Input::new(haystack))?;
/// assert_eq!(expected, got);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "dfa-build")]
#[derive(Clone, Debug)]
pub struct Builder {
config: Config,
#[cfg(feature = "syntax")]
thompson: thompson::Compiler,
}
#[cfg(feature = "dfa-build")]
impl Builder {
/// Create a new dense DFA builder with the default configuration.
pub fn new() -> Builder {
Builder {
config: Config::default(),
#[cfg(feature = "syntax")]
thompson: thompson::Compiler::new(),
}
}
/// Build a DFA from the given pattern.
///
/// If there was a problem parsing or compiling the pattern, then an error
/// is returned.
#[cfg(feature = "syntax")]
pub fn build(&self, pattern: &str) -> Result<OwnedDFA, BuildError> {
self.build_many(&[pattern])
}
/// Build a DFA from the given patterns.
///
/// When matches are returned, the pattern ID corresponds to the index of
/// the pattern in the slice given.
#[cfg(feature = "syntax")]
pub fn build_many<P: AsRef<str>>(
&self,
patterns: &[P],
) -> Result<OwnedDFA, BuildError> {
let nfa = self
.thompson
.clone()
// We can always forcefully disable captures because DFAs do not
// support them.
.configure(
thompson::Config::new()
.which_captures(thompson::WhichCaptures::None),
)
.build_many(patterns)
.map_err(BuildError::nfa)?;
self.build_from_nfa(&nfa)
}
/// Build a DFA from the given NFA.
///
/// # Example
///
/// This example shows how to build a DFA if you already have an NFA in
/// hand.
///
/// ```
/// use regex_automata::{
/// dfa::{Automaton, dense},
/// nfa::thompson::NFA,
/// HalfMatch, Input,
/// };
///
/// let haystack = "foo123bar".as_bytes();
///
/// // This shows how to set non-default options for building an NFA.
/// let nfa = NFA::compiler()
/// .configure(NFA::config().shrink(true))
/// .build(r"[0-9]+")?;
/// let dfa = dense::Builder::new().build_from_nfa(&nfa)?;
/// let expected = Some(HalfMatch::must(0, 6));
/// let got = dfa.try_search_fwd(&Input::new(haystack))?;
/// assert_eq!(expected, got);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn build_from_nfa(
&self,
nfa: &thompson::NFA,
) -> Result<OwnedDFA, BuildError> {
let mut quitset = self.config.quitset.unwrap_or(ByteSet::empty());
if self.config.get_unicode_word_boundary()
&& nfa.look_set_any().contains_word_unicode()
{
for b in 0x80..=0xFF {
quitset.add(b);
}
}
let classes = if !self.config.get_byte_classes() {
// DFAs will always use the equivalence class map, but enabling
// this option is useful for debugging. Namely, this will cause all
// transitions to be defined over their actual bytes instead of an
// opaque equivalence class identifier. The former is much easier
// to grok as a human.
ByteClasses::singletons()
} else {
let mut set = nfa.byte_class_set().clone();
// It is important to distinguish any "quit" bytes from all other
// bytes. Otherwise, a non-quit byte may end up in the same class
// as a quit byte, and thus cause the DFA stop when it shouldn't.
//
// Test case:
//
// regex-cli find hybrid regex -w @conn.json.1000x.log \
// '^#' '\b10\.55\.182\.100\b'
if !quitset.is_empty() {
set.add_set(&quitset);
}
set.byte_classes()
};
let mut dfa = DFA::initial(
classes,
nfa.pattern_len(),
self.config.get_starts(),
nfa.look_matcher(),
self.config.get_starts_for_each_pattern(),
self.config.get_prefilter().map(|p| p.clone()),
quitset,
Flags::from_nfa(&nfa),
)?;
determinize::Config::new()
.match_kind(self.config.get_match_kind())
.quit(quitset)
.dfa_size_limit(self.config.get_dfa_size_limit())
.determinize_size_limit(self.config.get_determinize_size_limit())
.run(nfa, &mut dfa)?;
if self.config.get_minimize() {
dfa.minimize();
}
if self.config.get_accelerate() {
dfa.accelerate();
}
// The state shuffling done before this point always assumes that start
// states should be marked as "special," even though it isn't the
// default configuration. State shuffling is complex enough as it is,
// so it's simpler to just "fix" our special state ID ranges to not
// include starting states after-the-fact.
if !self.config.get_specialize_start_states() {
dfa.special.set_no_special_start_states();
}
// Look for and set the universal starting states.
dfa.set_universal_starts();
Ok(dfa)
}
/// Apply the given dense DFA configuration options to this builder.
pub fn configure(&mut self, config: Config) -> &mut Builder {
self.config = self.config.overwrite(config);
self
}
/// Set the syntax configuration for this builder using
/// [`syntax::Config`](crate::util::syntax::Config).
///
/// This permits setting things like case insensitivity, Unicode and multi
/// line mode.
///
/// These settings only apply when constructing a DFA directly from a
/// pattern.
#[cfg(feature = "syntax")]
pub fn syntax(
&mut self,
config: crate::util::syntax::Config,
) -> &mut Builder {
self.thompson.syntax(config);
self
}
/// Set the Thompson NFA configuration for this builder using
/// [`nfa::thompson::Config`](crate::nfa::thompson::Config).
///
/// This permits setting things like whether the DFA should match the regex
/// in reverse or if additional time should be spent shrinking the size of
/// the NFA.
///
/// These settings only apply when constructing a DFA directly from a
/// pattern.
#[cfg(feature = "syntax")]
pub fn thompson(&mut self, config: thompson::Config) -> &mut Builder {
self.thompson.configure(config);
self
}
}
#[cfg(feature = "dfa-build")]
impl Default for Builder {
fn default() -> Builder {
Builder::new()
}
}
/// A convenience alias for an owned DFA. We use this particular instantiation
/// a lot in this crate, so it's worth giving it a name. This instantiation
/// is commonly used for mutable APIs on the DFA while building it. The main
/// reason for making DFAs generic is no_std support, and more generally,
/// making it possible to load a DFA from an arbitrary slice of bytes.
#[cfg(feature = "alloc")]
pub(crate) type OwnedDFA = DFA<alloc::vec::Vec<u32>>;
/// A dense table-based deterministic finite automaton (DFA).
///
/// All dense DFAs have one or more start states, zero or more match states
/// and a transition table that maps the current state and the current byte
/// of input to the next state. A DFA can use this information to implement
/// fast searching. In particular, the use of a dense DFA generally makes the
/// trade off that match speed is the most valuable characteristic, even if
/// building the DFA may take significant time *and* space. (More concretely,
/// building a DFA takes time and space that is exponential in the size of the
/// pattern in the worst case.) As such, the processing of every byte of input
/// is done with a small constant number of operations that does not vary with
/// the pattern, its size or the size of the alphabet. If your needs don't line
/// up with this trade off, then a dense DFA may not be an adequate solution to
/// your problem.
///
/// In contrast, a [`sparse::DFA`] makes the opposite
/// trade off: it uses less space but will execute a variable number of
/// instructions per byte at match time, which makes it slower for matching.
/// (Note that space usage is still exponential in the size of the pattern in
/// the worst case.)
///
/// A DFA can be built using the default configuration via the
/// [`DFA::new`] constructor. Otherwise, one can
/// configure various aspects via [`dense::Builder`](Builder).
///
/// A single DFA fundamentally supports the following operations:
///
/// 1. Detection of a match.
/// 2. Location of the end of a match.
/// 3. In the case of a 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* DFAs are required. This functionality is provided by a
/// [`Regex`](crate::dfa::regex::Regex).
///
/// # Type parameters
///
/// A `DFA` has one type parameter, `T`, which is used to represent state IDs,
/// pattern IDs and accelerators. `T` is typically a `Vec<u32>` or a `&[u32]`.
///
/// # The `Automaton` trait
///
/// This type implements the [`Automaton`] trait, which means it can be used
/// for searching. For example:
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// let dfa = DFA::new("foo[0-9]+")?;
/// let expected = HalfMatch::must(0, 8);
/// assert_eq!(Some(expected), dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(Clone)]
pub struct DFA<T> {
/// The transition table for this DFA. This includes the transitions
/// themselves, along with the stride, number of states and the equivalence
/// class mapping.
tt: TransitionTable<T>,
/// The set of starting state identifiers for this DFA. The starting state
/// IDs act as pointers into the transition table. The specific starting
/// state chosen for each search is dependent on the context at which the
/// search begins.
st: StartTable<T>,
/// The set of match states and the patterns that match for each
/// corresponding match state.
///
/// This structure is technically only needed because of support for
/// multi-regexes. Namely, multi-regexes require answering not just whether
/// a match exists, but _which_ patterns match. So we need to store the
/// matching pattern IDs for each match state. We do this even when there
/// is only one pattern for the sake of simplicity. In practice, this uses
/// up very little space for the case of one pattern.
ms: MatchStates<T>,
/// Information about which states are "special." Special states are states
/// that are dead, quit, matching, starting or accelerated. For more info,
/// see the docs for `Special`.
special: Special,
/// The accelerators for this DFA.
///
/// If a state is accelerated, then there exist only a small number of
/// bytes that can cause the DFA to leave the state. This permits searching
/// to use optimized routines to find those specific bytes instead of using
/// the transition table.
///
/// All accelerated states exist in a contiguous range in the DFA's
/// transition table. See dfa/special.rs for more details on how states are
/// arranged.
accels: Accels<T>,
/// Any prefilter attached to this DFA.
///
/// Note that currently prefilters are not serialized. When deserializing
/// a DFA from bytes, this is always set to `None`.
pre: Option<Prefilter>,
/// The set of "quit" bytes for this DFA.
///
/// This is only used when computing the start state for a particular
/// position in a haystack. Namely, in the case where there is a quit
/// byte immediately before the start of the search, this set needs to be
/// explicitly consulted. In all other cases, quit bytes are detected by
/// the DFA itself, by transitioning all quit bytes to a special "quit
/// state."
quitset: ByteSet,
/// Various flags describing the behavior of this DFA.
flags: Flags,
}
#[cfg(feature = "dfa-build")]
impl OwnedDFA {
/// Parse the given regular expression using a default configuration and
/// return the corresponding DFA.
///
/// If you want a non-default configuration, then use the
/// [`dense::Builder`](Builder) to set your own configuration.
///
/// # Example
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
///
/// let dfa = dense::DFA::new("foo[0-9]+bar")?;
/// let expected = Some(HalfMatch::must(0, 11));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345bar"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "syntax")]
pub fn new(pattern: &str) -> Result<OwnedDFA, BuildError> {
Builder::new().build(pattern)
}
/// Parse the given regular expressions using a default configuration and
/// return the corresponding multi-DFA.
///
/// If you want a non-default configuration, then use the
/// [`dense::Builder`](Builder) to set your own configuration.
///
/// # Example
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
///
/// let dfa = dense::DFA::new_many(&["[0-9]+", "[a-z]+"])?;
/// let expected = Some(HalfMatch::must(1, 3));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345bar"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "syntax")]
pub fn new_many<P: AsRef<str>>(
patterns: &[P],
) -> Result<OwnedDFA, BuildError> {
Builder::new().build_many(patterns)
}
}
#[cfg(feature = "dfa-build")]
impl OwnedDFA {
/// Create a new DFA that matches every input.
///
/// # Example
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
///
/// let dfa = dense::DFA::always_match()?;
///
/// let expected = Some(HalfMatch::must(0, 0));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new(""))?);
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn always_match() -> Result<OwnedDFA, BuildError> {
let nfa = thompson::NFA::always_match();
Builder::new().build_from_nfa(&nfa)
}
/// Create a new DFA that never matches any input.
///
/// # Example
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense}, Input};
///
/// let dfa = dense::DFA::never_match()?;
/// assert_eq!(None, dfa.try_search_fwd(&Input::new(""))?);
/// assert_eq!(None, dfa.try_search_fwd(&Input::new("foo"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn never_match() -> Result<OwnedDFA, BuildError> {
let nfa = thompson::NFA::never_match();
Builder::new().build_from_nfa(&nfa)
}
/// Create an initial DFA with the given equivalence classes, pattern
/// length and whether anchored starting states are enabled for each
/// pattern. An initial DFA can be further mutated via determinization.
fn initial(
classes: ByteClasses,
pattern_len: usize,
starts: StartKind,
lookm: &LookMatcher,
starts_for_each_pattern: bool,
pre: Option<Prefilter>,
quitset: ByteSet,
flags: Flags,
) -> Result<OwnedDFA, BuildError> {
let start_pattern_len =
if starts_for_each_pattern { Some(pattern_len) } else { None };
Ok(DFA {
tt: TransitionTable::minimal(classes),
st: StartTable::dead(starts, lookm, start_pattern_len)?,
ms: MatchStates::empty(pattern_len),
special: Special::new(),
accels: Accels::empty(),
pre,
quitset,
flags,
})
}
}
#[cfg(feature = "dfa-build")]
impl DFA<&[u32]> {
/// Return a new default dense DFA compiler configuration.
///
/// This is a convenience routine to avoid needing to import the [`Config`]
/// type when customizing the construction of a dense DFA.
pub fn config() -> Config {
Config::new()
}
/// Create a new dense DFA builder with the default configuration.
///
/// This is a convenience routine to avoid needing to import the
/// [`Builder`] type in common cases.
pub fn builder() -> Builder {
Builder::new()
}
}
impl<T: AsRef<[u32]>> DFA<T> {
/// Cheaply return a borrowed version of this dense DFA. Specifically,
/// the DFA returned always uses `&[u32]` for its transition table.
pub fn as_ref(&self) -> DFA<&'_ [u32]> {
DFA {
tt: self.tt.as_ref(),
st: self.st.as_ref(),
ms: self.ms.as_ref(),
special: self.special,
accels: self.accels(),
pre: self.pre.clone(),
quitset: self.quitset,
flags: self.flags,
}
}
/// Return an owned version of this sparse DFA. Specifically, the DFA
/// returned always uses `Vec<u32>` for its transition table.
///
/// Effectively, this returns a dense DFA whose transition table lives on
/// the heap.
#[cfg(feature = "alloc")]
pub fn to_owned(&self) -> OwnedDFA {
DFA {
tt: self.tt.to_owned(),
st: self.st.to_owned(),
ms: self.ms.to_owned(),
special: self.special,
accels: self.accels().to_owned(),
pre: self.pre.clone(),
quitset: self.quitset,
flags: self.flags,
}
}
/// Returns the starting state configuration for this DFA.
///
/// The default is [`StartKind::Both`], which means the DFA supports both
/// unanchored and anchored searches. However, this can generally lead to
/// bigger DFAs. Therefore, a DFA might be compiled with support for just
/// unanchored or anchored searches. In that case, running a search with
/// an unsupported configuration will panic.
pub fn start_kind(&self) -> StartKind {
self.st.kind
}
/// Returns the start byte map used for computing the `Start` configuration
/// at the beginning of a search.
pub(crate) fn start_map(&self) -> &StartByteMap {
&self.st.start_map
}
/// Returns true only if this DFA has starting states for each pattern.
///
/// When a DFA has starting states for each pattern, then a search with the
/// DFA can be configured to only look for anchored matches of a specific
/// pattern. Specifically, APIs like [`Automaton::try_search_fwd`] can
/// accept a non-None `pattern_id` if and only if this method returns true.
/// Otherwise, calling `try_search_fwd` will panic.
///
/// Note that if the DFA has no patterns, this always returns false.
pub fn starts_for_each_pattern(&self) -> bool {
self.st.pattern_len.is_some()
}
/// 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.
pub fn byte_classes(&self) -> &ByteClasses {
&self.tt.classes
}
/// Returns the total number of elements in the alphabet for this DFA.
///
/// That is, this returns the total number of transitions that each state
/// in this DFA must have. Typically, a normal byte oriented DFA would
/// always have an alphabet size of 256, corresponding to the number of
/// unique values in a single byte. However, this implementation has two
/// peculiarities that impact the alphabet length:
///
/// * Every state has a special "EOI" transition that is only followed
/// after the end of some haystack is reached. This EOI transition is
/// necessary to account for one byte of look-ahead when implementing
/// things like `\b` and `$`.
/// * Bytes are grouped into equivalence classes such that no two bytes in
/// the same class can distinguish a match from a non-match. For example,
/// in the regex `^[a-z]+$`, the ASCII bytes `a-z` could all be in the
/// same equivalence class. This leads to a massive space savings.
///
/// Note though that the alphabet length does _not_ necessarily equal the
/// total stride space taken up by a single DFA state in the transition
/// table. Namely, for performance reasons, the stride is always the
/// smallest power of two that is greater than or equal to the alphabet
/// length. For this reason, [`DFA::stride`] or [`DFA::stride2`] are
/// often more useful. The alphabet length is typically useful only for
/// informational purposes.
pub fn alphabet_len(&self) -> usize {
self.tt.alphabet_len()
}
/// Returns the total stride for every state in this DFA, expressed as the
/// exponent of a power of 2. The stride is the amount of space each state
/// takes up in the transition table, expressed as a number of transitions.
/// (Unused transitions map to dead states.)
///
/// The stride of a DFA is always equivalent to the smallest power of 2
/// that is greater than or equal to the DFA's alphabet length. This
/// definition uses extra space, but permits faster translation between
/// premultiplied state identifiers and contiguous indices (by using shifts
/// instead of relying on integer division).
///
/// For example, if the DFA's stride is 16 transitions, then its `stride2`
/// is `4` since `2^4 = 16`.
///
/// The minimum `stride2` value is `1` (corresponding to a stride of `2`)
/// while the maximum `stride2` value is `9` (corresponding to a stride of
/// `512`). The maximum is not `8` since the maximum alphabet size is `257`
/// when accounting for the special EOI transition. However, an alphabet
/// length of that size is exceptionally rare since the alphabet is shrunk
/// into equivalence classes.
pub fn stride2(&self) -> usize {
self.tt.stride2
}
/// Returns the total stride for every state in this DFA. This corresponds
/// to the total number of transitions used by each state in this DFA's
/// transition table.
///
/// Please see [`DFA::stride2`] for more information. In particular, this
/// returns the stride as the number of transitions, where as `stride2`
/// returns it as the exponent of a power of 2.
pub fn stride(&self) -> usize {
self.tt.stride()
}
/// Returns the memory usage, in bytes, of this DFA.
///
/// The memory usage is computed based on the number of bytes used to
/// represent this DFA.
///
/// This does **not** include the stack size used up by this DFA. To
/// compute that, use `std::mem::size_of::<dense::DFA>()`.
pub fn memory_usage(&self) -> usize {
self.tt.memory_usage()
+ self.st.memory_usage()
+ self.ms.memory_usage()
+ self.accels.memory_usage()
}
}
/// Routines for converting a dense DFA to other representations, such as
/// sparse DFAs or raw bytes suitable for persistent storage.
impl<T: AsRef<[u32]>> DFA<T> {
/// Convert this dense DFA to a sparse DFA.
///
/// If a `StateID` is too small to represent all states in the sparse
/// DFA, then this returns an error. In most cases, if a dense DFA is
/// constructable with `StateID` then a sparse DFA will be as well.
/// However, it is not guaranteed.
///
/// # Example
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense}, HalfMatch, Input};
///
/// let dense = dense::DFA::new("foo[0-9]+")?;
/// let sparse = dense.to_sparse()?;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, sparse.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "dfa-build")]
pub fn to_sparse(&self) -> Result<sparse::DFA<Vec<u8>>, BuildError> {
sparse::DFA::from_dense(self)
}
/// Serialize this DFA as raw bytes to a `Vec<u8>` in little endian
/// format. Upon success, the `Vec<u8>` and the initial padding length are
/// returned.
///
/// The written bytes are guaranteed to be deserialized correctly and
/// without errors in a semver compatible release of this crate by a
/// `DFA`'s deserialization APIs (assuming all other criteria for the
/// deserialization APIs has been satisfied):
///
/// * [`DFA::from_bytes`]
/// * [`DFA::from_bytes_unchecked`]
///
/// The padding returned is non-zero if the returned `Vec<u8>` starts at
/// an address that does not have the same alignment as `u32`. The padding
/// corresponds to the number of leading bytes written to the returned
/// `Vec<u8>`.
///
/// # Example
///
/// This example shows how to serialize and deserialize a DFA:
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// // Compile our original DFA.
/// let original_dfa = DFA::new("foo[0-9]+")?;
///
/// // N.B. We use native endianness here to make the example work, but
/// // using to_bytes_little_endian would work on a little endian target.
/// let (buf, _) = original_dfa.to_bytes_native_endian();
/// // Even if buf has initial padding, DFA::from_bytes will automatically
/// // ignore it.
/// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf)?.0;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "dfa-build")]
pub fn to_bytes_little_endian(&self) -> (Vec<u8>, usize) {
self.to_bytes::<wire::LE>()
}
/// Serialize this DFA as raw bytes to a `Vec<u8>` in big endian
/// format. Upon success, the `Vec<u8>` and the initial padding length are
/// returned.
///
/// The written bytes are guaranteed to be deserialized correctly and
/// without errors in a semver compatible release of this crate by a
/// `DFA`'s deserialization APIs (assuming all other criteria for the
/// deserialization APIs has been satisfied):
///
/// * [`DFA::from_bytes`]
/// * [`DFA::from_bytes_unchecked`]
///
/// The padding returned is non-zero if the returned `Vec<u8>` starts at
/// an address that does not have the same alignment as `u32`. The padding
/// corresponds to the number of leading bytes written to the returned
/// `Vec<u8>`.
///
/// # Example
///
/// This example shows how to serialize and deserialize a DFA:
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// // Compile our original DFA.
/// let original_dfa = DFA::new("foo[0-9]+")?;
///
/// // N.B. We use native endianness here to make the example work, but
/// // using to_bytes_big_endian would work on a big endian target.
/// let (buf, _) = original_dfa.to_bytes_native_endian();
/// // Even if buf has initial padding, DFA::from_bytes will automatically
/// // ignore it.
/// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf)?.0;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "dfa-build")]
pub fn to_bytes_big_endian(&self) -> (Vec<u8>, usize) {
self.to_bytes::<wire::BE>()
}
/// Serialize this DFA as raw bytes to a `Vec<u8>` in native endian
/// format. Upon success, the `Vec<u8>` and the initial padding length are
/// returned.
///
/// The written bytes are guaranteed to be deserialized correctly and
/// without errors in a semver compatible release of this crate by a
/// `DFA`'s deserialization APIs (assuming all other criteria for the
/// deserialization APIs has been satisfied):
///
/// * [`DFA::from_bytes`]
/// * [`DFA::from_bytes_unchecked`]
///
/// The padding returned is non-zero if the returned `Vec<u8>` starts at
/// an address that does not have the same alignment as `u32`. The padding
/// corresponds to the number of leading bytes written to the returned
/// `Vec<u8>`.
///
/// Generally speaking, native endian format should only be used when
/// you know that the target you're compiling the DFA for matches the
/// endianness of the target on which you're compiling DFA. For example,
/// if serialization and deserialization happen in the same process or on
/// the same machine. Otherwise, when serializing a DFA for use in a
/// portable environment, you'll almost certainly want to serialize _both_
/// a little endian and a big endian version and then load the correct one
/// based on the target's configuration.
///
/// # Example
///
/// This example shows how to serialize and deserialize a DFA:
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// // Compile our original DFA.
/// let original_dfa = DFA::new("foo[0-9]+")?;
///
/// let (buf, _) = original_dfa.to_bytes_native_endian();
/// // Even if buf has initial padding, DFA::from_bytes will automatically
/// // ignore it.
/// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf)?.0;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[cfg(feature = "dfa-build")]
pub fn to_bytes_native_endian(&self) -> (Vec<u8>, usize) {
self.to_bytes::<wire::NE>()
}
/// The implementation of the public `to_bytes` serialization methods,
/// which is generic over endianness.
#[cfg(feature = "dfa-build")]
fn to_bytes<E: Endian>(&self) -> (Vec<u8>, usize) {
let len = self.write_to_len();
let (mut buf, padding) = wire::alloc_aligned_buffer::<u32>(len);
// This should always succeed since the only possible serialization
// error is providing a buffer that's too small, but we've ensured that
// `buf` is big enough here.
self.as_ref().write_to::<E>(&mut buf[padding..]).unwrap();
(buf, padding)
}
/// Serialize this DFA as raw bytes to the given slice, in little endian
/// format. Upon success, the total number of bytes written to `dst` is
/// returned.
///
/// The written bytes are guaranteed to be deserialized correctly and
/// without errors in a semver compatible release of this crate by a
/// `DFA`'s deserialization APIs (assuming all other criteria for the
/// deserialization APIs has been satisfied):
///
/// * [`DFA::from_bytes`]
/// * [`DFA::from_bytes_unchecked`]
///
/// Note that unlike the various `to_byte_*` routines, this does not write
/// any padding. Callers are responsible for handling alignment correctly.
///
/// # Errors
///
/// This returns an error if the given destination slice is not big enough
/// to contain the full serialized DFA. If an error occurs, then nothing
/// is written to `dst`.
///
/// # Example
///
/// This example shows how to serialize and deserialize a DFA without
/// dynamic memory allocation.
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// // Compile our original DFA.
/// let original_dfa = DFA::new("foo[0-9]+")?;
///
/// // Create a 4KB buffer on the stack to store our serialized DFA. We
/// // need to use a special type to force the alignment of our [u8; N]
/// // array to be aligned to a 4 byte boundary. Otherwise, deserializing
/// // the DFA may fail because of an alignment mismatch.
/// #[repr(C)]
/// struct Aligned<B: ?Sized> {
/// _align: [u32; 0],
/// bytes: B,
/// }
/// let mut buf = Aligned { _align: [], bytes: [0u8; 4 * (1<<10)] };
/// // N.B. We use native endianness here to make the example work, but
/// // using write_to_little_endian would work on a little endian target.
/// let written = original_dfa.write_to_native_endian(&mut buf.bytes)?;
/// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf.bytes[..written])?.0;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn write_to_little_endian(
&self,
dst: &mut [u8],
) -> Result<usize, SerializeError> {
self.as_ref().write_to::<wire::LE>(dst)
}
/// Serialize this DFA as raw bytes to the given slice, in big endian
/// format. Upon success, the total number of bytes written to `dst` is
/// returned.
///
/// The written bytes are guaranteed to be deserialized correctly and
/// without errors in a semver compatible release of this crate by a
/// `DFA`'s deserialization APIs (assuming all other criteria for the
/// deserialization APIs has been satisfied):
///
/// * [`DFA::from_bytes`]
/// * [`DFA::from_bytes_unchecked`]
///
/// Note that unlike the various `to_byte_*` routines, this does not write
/// any padding. Callers are responsible for handling alignment correctly.
///
/// # Errors
///
/// This returns an error if the given destination slice is not big enough
/// to contain the full serialized DFA. If an error occurs, then nothing
/// is written to `dst`.
///
/// # Example
///
/// This example shows how to serialize and deserialize a DFA without
/// dynamic memory allocation.
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// // Compile our original DFA.
/// let original_dfa = DFA::new("foo[0-9]+")?;
///
/// // Create a 4KB buffer on the stack to store our serialized DFA. We
/// // need to use a special type to force the alignment of our [u8; N]
/// // array to be aligned to a 4 byte boundary. Otherwise, deserializing
/// // the DFA may fail because of an alignment mismatch.
/// #[repr(C)]
/// struct Aligned<B: ?Sized> {
/// _align: [u32; 0],
/// bytes: B,
/// }
/// let mut buf = Aligned { _align: [], bytes: [0u8; 4 * (1<<10)] };
/// // N.B. We use native endianness here to make the example work, but
/// // using write_to_big_endian would work on a big endian target.
/// let written = original_dfa.write_to_native_endian(&mut buf.bytes)?;
/// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf.bytes[..written])?.0;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn write_to_big_endian(
&self,
dst: &mut [u8],
) -> Result<usize, SerializeError> {
self.as_ref().write_to::<wire::BE>(dst)
}
/// Serialize this DFA as raw bytes to the given slice, in native endian
/// format. Upon success, the total number of bytes written to `dst` is
/// returned.
///
/// The written bytes are guaranteed to be deserialized correctly and
/// without errors in a semver compatible release of this crate by a
/// `DFA`'s deserialization APIs (assuming all other criteria for the
/// deserialization APIs has been satisfied):
///
/// * [`DFA::from_bytes`]
/// * [`DFA::from_bytes_unchecked`]
///
/// Generally speaking, native endian format should only be used when
/// you know that the target you're compiling the DFA for matches the
/// endianness of the target on which you're compiling DFA. For example,
/// if serialization and deserialization happen in the same process or on
/// the same machine. Otherwise, when serializing a DFA for use in a
/// portable environment, you'll almost certainly want to serialize _both_
/// a little endian and a big endian version and then load the correct one
/// based on the target's configuration.
///
/// Note that unlike the various `to_byte_*` routines, this does not write
/// any padding. Callers are responsible for handling alignment correctly.
///
/// # Errors
///
/// This returns an error if the given destination slice is not big enough
/// to contain the full serialized DFA. If an error occurs, then nothing
/// is written to `dst`.
///
/// # Example
///
/// This example shows how to serialize and deserialize a DFA without
/// dynamic memory allocation.
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// // Compile our original DFA.
/// let original_dfa = DFA::new("foo[0-9]+")?;
///
/// // Create a 4KB buffer on the stack to store our serialized DFA. We
/// // need to use a special type to force the alignment of our [u8; N]
/// // array to be aligned to a 4 byte boundary. Otherwise, deserializing
/// // the DFA may fail because of an alignment mismatch.
/// #[repr(C)]
/// struct Aligned<B: ?Sized> {
/// _align: [u32; 0],
/// bytes: B,
/// }
/// let mut buf = Aligned { _align: [], bytes: [0u8; 4 * (1<<10)] };
/// let written = original_dfa.write_to_native_endian(&mut buf.bytes)?;
/// let dfa: DFA<&[u32]> = DFA::from_bytes(&buf.bytes[..written])?.0;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn write_to_native_endian(
&self,
dst: &mut [u8],
) -> Result<usize, SerializeError> {
self.as_ref().write_to::<wire::NE>(dst)
}
/// Return the total number of bytes required to serialize this DFA.
///
/// This is useful for determining the size of the buffer required to pass
/// to one of the serialization routines:
///
/// * [`DFA::write_to_little_endian`]
/// * [`DFA::write_to_big_endian`]
/// * [`DFA::write_to_native_endian`]
///
/// Passing a buffer smaller than the size returned by this method will
/// result in a serialization error. Serialization routines are guaranteed
/// to succeed when the buffer is big enough.
///
/// # Example
///
/// This example shows how to dynamically allocate enough room to serialize
/// a DFA.
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// let original_dfa = DFA::new("foo[0-9]+")?;
///
/// let mut buf = vec![0; original_dfa.write_to_len()];
/// // This is guaranteed to succeed, because the only serialization error
/// // that can occur is when the provided buffer is too small. But
/// // write_to_len guarantees a correct size.
/// let written = original_dfa.write_to_native_endian(&mut buf).unwrap();
/// // But this is not guaranteed to succeed! In particular,
/// // deserialization requires proper alignment for &[u32], but our buffer
/// // was allocated as a &[u8] whose required alignment is smaller than
/// // &[u32]. However, it's likely to work in practice because of how most
/// // allocators work. So if you write code like this, make sure to either
/// // handle the error correctly and/or run it under Miri since Miri will
/// // likely provoke the error by returning Vec<u8> buffers with alignment
/// // less than &[u32].
/// let dfa: DFA<&[u32]> = match DFA::from_bytes(&buf[..written]) {
/// // As mentioned above, it is legal for an error to be returned
/// // here. It is quite difficult to get a Vec<u8> with a guaranteed
/// // alignment equivalent to Vec<u32>.
/// Err(_) => return Ok(()),
/// Ok((dfa, _)) => dfa,
/// };
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// Note that this example isn't actually guaranteed to work! In
/// particular, if `buf` is not aligned to a 4-byte boundary, then the
/// `DFA::from_bytes` call will fail. If you need this to work, then you
/// either need to deal with adding some initial padding yourself, or use
/// one of the `to_bytes` methods, which will do it for you.
pub fn write_to_len(&self) -> usize {
wire::write_label_len(LABEL)
+ wire::write_endianness_check_len()
+ wire::write_version_len()
+ size_of::<u32>() // unused, intended for future flexibility
+ self.flags.write_to_len()
+ self.tt.write_to_len()
+ self.st.write_to_len()
+ self.ms.write_to_len()
+ self.special.write_to_len()
+ self.accels.write_to_len()
+ self.quitset.write_to_len()
}
}
impl<'a> DFA<&'a [u32]> {
/// Safely deserialize a DFA with a specific state identifier
/// representation. Upon success, this returns both the deserialized DFA
/// and the number of bytes read from the given slice. Namely, the contents
/// of the slice beyond the DFA are not read.
///
/// Deserializing a DFA using this routine will never allocate heap memory.
/// For safety purposes, the DFA's transition table will be verified such
/// that every transition points to a valid state. If this verification is
/// too costly, then a [`DFA::from_bytes_unchecked`] API is provided, which
/// will always execute in constant time.
///
/// The bytes given must be generated by one of the serialization APIs
/// of a `DFA` using a semver compatible release of this crate. Those
/// include:
///
/// * [`DFA::to_bytes_little_endian`]
/// * [`DFA::to_bytes_big_endian`]
/// * [`DFA::to_bytes_native_endian`]
/// * [`DFA::write_to_little_endian`]
/// * [`DFA::write_to_big_endian`]
/// * [`DFA::write_to_native_endian`]
///
/// The `to_bytes` methods allocate and return a `Vec<u8>` for you, along
/// with handling alignment correctly. The `write_to` methods do not
/// allocate and write to an existing slice (which may be on the stack).
/// Since deserialization always uses the native endianness of the target
/// platform, the serialization API you use should match the endianness of
/// the target platform. (It's often a good idea to generate serialized
/// DFAs for both forms of endianness and then load the correct one based
/// on endianness.)
///
/// # Errors
///
/// Generally speaking, it's easier to state the conditions in which an
/// error is _not_ returned. All of the following must be true:
///
/// * The bytes given must be produced by one of the serialization APIs
/// on this DFA, as mentioned above.
/// * The endianness of the target platform matches the endianness used to
/// serialized the provided DFA.
/// * The slice given must have the same alignment as `u32`.
///
/// If any of the above are not true, then an error will be returned.
///
/// # Panics
///
/// This routine will never panic for any input.
///
/// # Example
///
/// This example shows how to serialize a DFA to raw bytes, deserialize it
/// and then use it for searching.
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// let initial = DFA::new("foo[0-9]+")?;
/// let (bytes, _) = initial.to_bytes_native_endian();
/// let dfa: DFA<&[u32]> = DFA::from_bytes(&bytes)?.0;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # Example: dealing with alignment and padding
///
/// In the above example, we used the `to_bytes_native_endian` method to
/// serialize a DFA, but we ignored part of its return value corresponding
/// to padding added to the beginning of the serialized DFA. This is OK
/// because deserialization will skip this initial padding. What matters
/// is that the address immediately following the padding has an alignment
/// that matches `u32`. That is, the following is an equivalent but
/// alternative way to write the above example:
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// let initial = DFA::new("foo[0-9]+")?;
/// // Serialization returns the number of leading padding bytes added to
/// // the returned Vec<u8>.
/// let (bytes, pad) = initial.to_bytes_native_endian();
/// let dfa: DFA<&[u32]> = DFA::from_bytes(&bytes[pad..])?.0;
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// This padding is necessary because Rust's standard library does
/// not expose any safe and robust way of creating a `Vec<u8>` with a
/// guaranteed alignment other than 1. Now, in practice, the underlying
/// allocator is likely to provide a `Vec<u8>` that meets our alignment
/// requirements, which means `pad` is zero in practice most of the time.
///
/// The purpose of exposing the padding like this is flexibility for the
/// caller. For example, if one wants to embed a serialized DFA into a
/// compiled program, then it's important to guarantee that it starts at a
/// `u32`-aligned address. The simplest way to do this is to discard the
/// padding bytes and set it up so that the serialized DFA itself begins at
/// a properly aligned address. We can show this in two parts. The first
/// part is serializing the DFA to a file:
///
/// ```no_run
/// use regex_automata::dfa::dense::DFA;
///
/// let dfa = DFA::new("foo[0-9]+")?;
///
/// let (bytes, pad) = dfa.to_bytes_big_endian();
/// // Write the contents of the DFA *without* the initial padding.
/// std::fs::write("foo.bigendian.dfa", &bytes[pad..])?;
///
/// // Do it again, but this time for little endian.
/// let (bytes, pad) = dfa.to_bytes_little_endian();
/// std::fs::write("foo.littleendian.dfa", &bytes[pad..])?;
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// And now the second part is embedding the DFA into the compiled program
/// and deserializing it at runtime on first use. We use conditional
/// compilation to choose the correct endianness.
///
/// ```no_run
/// use regex_automata::{
/// dfa::{Automaton, dense::DFA},
/// util::{lazy::Lazy, wire::AlignAs},
/// HalfMatch, Input,
/// };
///
/// // This crate provides its own "lazy" type, kind of like
/// // lazy_static! or once_cell::sync::Lazy. But it works in no-alloc
/// // no-std environments and let's us write this using completely
/// // safe code.
/// static RE: Lazy<DFA<&'static [u32]>> = Lazy::new(|| {
/// # const _: &str = stringify! {
/// // This assignment is made possible (implicitly) via the
/// // CoerceUnsized trait. This is what guarantees that our
/// // bytes are stored in memory on a 4 byte boundary. You
/// // *must* do this or something equivalent for correct
/// // deserialization.
/// static ALIGNED: &AlignAs<[u8], u32> = &AlignAs {
/// _align: [],
/// #[cfg(target_endian = "big")]
/// bytes: *include_bytes!("foo.bigendian.dfa"),
/// #[cfg(target_endian = "little")]
/// bytes: *include_bytes!("foo.littleendian.dfa"),
/// };
/// # };
/// # static ALIGNED: &AlignAs<[u8], u32> = &AlignAs {
/// # _align: [],
/// # bytes: [],
/// # };
///
/// let (dfa, _) = DFA::from_bytes(&ALIGNED.bytes)
/// .expect("serialized DFA should be valid");
/// dfa
/// });
///
/// let expected = Ok(Some(HalfMatch::must(0, 8)));
/// assert_eq!(expected, RE.try_search_fwd(&Input::new("foo12345")));
/// ```
///
/// An alternative to [`util::lazy::Lazy`](crate::util::lazy::Lazy)
/// stronger guarantees (like the initialization function only being
/// executed once). And `once_cell` in particular provides a more
/// expressive API. But a `Lazy` value from this crate is likely just fine
/// in most circumstances.
///
/// Note that regardless of which initialization method you use, you
/// will still need to use the [`AlignAs`](crate::util::wire::AlignAs)
/// trick above to force correct alignment, but this is safe to do and
/// `from_bytes` will return an error if you get it wrong.
pub fn from_bytes(
slice: &'a [u8],
) -> Result<(DFA<&'a [u32]>, usize), DeserializeError> {
// SAFETY: This is safe because we validate the transition table, start
// table, match states and accelerators below. If any validation fails,
// then we return an error.
let (dfa, nread) = unsafe { DFA::from_bytes_unchecked(slice)? };
dfa.tt.validate(&dfa.special)?;
dfa.st.validate(&dfa.tt)?;
dfa.ms.validate(&dfa)?;
dfa.accels.validate()?;
// N.B. dfa.special doesn't have a way to do unchecked deserialization,
// so it has already been validated.
Ok((dfa, nread))
}
/// Deserialize a DFA with a specific state identifier representation in
/// constant time by omitting the verification of the validity of the
/// transition table and other data inside the DFA.
///
/// This is just like [`DFA::from_bytes`], except it can potentially return
/// a DFA that exhibits undefined behavior if its transition table contains
/// invalid state identifiers.
///
/// This routine is useful if you need to deserialize a DFA cheaply
/// and cannot afford the transition table validation performed by
/// `from_bytes`.
///
/// # Example
///
/// ```
/// use regex_automata::{dfa::{Automaton, dense::DFA}, HalfMatch, Input};
///
/// let initial = DFA::new("foo[0-9]+")?;
/// let (bytes, _) = initial.to_bytes_native_endian();
/// // SAFETY: This is guaranteed to be safe since the bytes given come
/// // directly from a compatible serialization routine.
/// let dfa: DFA<&[u32]> = unsafe { DFA::from_bytes_unchecked(&bytes)?.0 };
///
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub unsafe fn from_bytes_unchecked(
slice: &'a [u8],
) -> Result<(DFA<&'a [u32]>, usize), DeserializeError> {
let mut nr = 0;
nr += wire::skip_initial_padding(slice);
wire::check_alignment::<StateID>(&slice[nr..])?;
nr += wire::read_label(&slice[nr..], LABEL)?;
nr += wire::read_endianness_check(&slice[nr..])?;
nr += wire::read_version(&slice[nr..], VERSION)?;
let _unused = wire::try_read_u32(&slice[nr..], "unused space")?;
nr += size_of::<u32>();
let (flags, nread) = Flags::from_bytes(&slice[nr..])?;
nr += nread;
let (tt, nread) = TransitionTable::from_bytes_unchecked(&slice[nr..])?;
nr += nread;
let (st, nread) = StartTable::from_bytes_unchecked(&slice[nr..])?;
nr += nread;
let (ms, nread) = MatchStates::from_bytes_unchecked(&slice[nr..])?;
nr += nread;
let (special, nread) = Special::from_bytes(&slice[nr..])?;
nr += nread;
special.validate_state_len(tt.len(), tt.stride2)?;
let (accels, nread) = Accels::from_bytes_unchecked(&slice[nr..])?;
nr += nread;
let (quitset, nread) = ByteSet::from_bytes(&slice[nr..])?;
nr += nread;
// Prefilters don't support serialization, so they're always absent.
let pre = None;
Ok((DFA { tt, st, ms, special, accels, pre, quitset, flags }, nr))
}
/// The implementation of the public `write_to` serialization methods,
/// which is generic over endianness.
///
/// This is defined only for &[u32] to reduce binary size/compilation time.
fn write_to<E: Endian>(
&self,
mut dst: &mut [u8],
) -> Result<usize, SerializeError> {
let nwrite = self.write_to_len();
if dst.len() < nwrite {
return Err(SerializeError::buffer_too_small("dense DFA"));
}
dst = &mut dst[..nwrite];
let mut nw = 0;
nw += wire::write_label(LABEL, &mut dst[nw..])?;
nw += wire::write_endianness_check::<E>(&mut dst[nw..])?;
nw += wire::write_version::<E>(VERSION, &mut dst[nw..])?;
nw += {
// Currently unused, intended for future flexibility
E::write_u32(0, &mut dst[nw..]);
size_of::<u32>()
};
nw += self.flags.write_to::<E>(&mut dst[nw..])?;
nw += self.tt.write_to::<E>(&mut dst[nw..])?;
nw += self.st.write_to::<E>(&mut dst[nw..])?;
nw += self.ms.write_to::<E>(&mut dst[nw..])?;
nw += self.special.write_to::<E>(&mut dst[nw..])?;
nw += self.accels.write_to::<E>(&mut dst[nw..])?;
nw += self.quitset.write_to::<E>(&mut dst[nw..])?;
Ok(nw)
}
}
// The following methods implement mutable routines on the internal
// representation of a DFA. As such, we must fix the first type parameter to a
// `Vec<u32>` since a generic `T: AsRef<[u32]>` does not permit mutation. We
// can get away with this because these methods are internal to the crate and
// are exclusively used during construction of the DFA.
#[cfg(feature = "dfa-build")]
impl OwnedDFA {
/// Add a start state of this DFA.
pub(crate) fn set_start_state(
&mut self,
anchored: Anchored,
start: Start,
id: StateID,
) {
assert!(self.tt.is_valid(id), "invalid start state");
self.st.set_start(anchored, start, id);
}
/// Set the given transition to this DFA. Both the `from` and `to` states
/// must already exist.
pub(crate) fn set_transition(
&mut self,
from: StateID,
byte: alphabet::Unit,
to: StateID,
) {
self.tt.set(from, byte, to);
}
/// An an empty state (a state where all transitions lead to a dead state)
/// and return its identifier. The identifier returned is guaranteed to
/// not point to any other existing state.
///
/// If adding a state would exceed `StateID::LIMIT`, then this returns an
/// error.
pub(crate) fn add_empty_state(&mut self) -> Result<StateID, BuildError> {
self.tt.add_empty_state()
}
/// Swap the two states given in the transition table.
///
/// This routine does not do anything to check the correctness of this
/// swap. Callers must ensure that other states pointing to id1 and id2 are
/// updated appropriately.
pub(crate) fn swap_states(&mut self, id1: StateID, id2: StateID) {
self.tt.swap(id1, id2);
}
/// Remap all of the state identifiers in this DFA according to the map
/// function given. This includes all transitions and all starting state
/// identifiers.
pub(crate) fn remap(&mut self, map: impl Fn(StateID) -> StateID) {
// We could loop over each state ID and call 'remap_state' here, but
// this is more direct: just map every transition directly. This
// technically might do a little extra work since the alphabet length
// is likely less than the stride, but if that is indeed an issue we
// should benchmark it and fix it.
for sid in self.tt.table_mut().iter_mut() {
*sid = map(*sid);
}
for sid in self.st.table_mut().iter_mut() {
*sid = map(*sid);
}
}
/// Remap the transitions for the state given according to the function
/// given. This applies the given map function to every transition in the
/// given state and changes the transition in place to the result of the
/// map function for that transition.
pub(crate) fn remap_state(
&mut self,
id: StateID,
map: impl Fn(StateID) -> StateID,
) {
self.tt.remap(id, map);
}
/// Truncate the states in this DFA to the given length.
///
/// This routine does not do anything to check the correctness of this
/// truncation. Callers must ensure that other states pointing to truncated
/// states are updated appropriately.
pub(crate) fn truncate_states(&mut self, len: usize) {
self.tt.truncate(len);
}
/// Minimize this DFA in place using Hopcroft's algorithm.
pub(crate) fn minimize(&mut self) {
Minimizer::new(self).run();
}
/// Updates the match state pattern ID map to use the one provided.
///
/// This is useful when it's convenient to manipulate matching states
/// (and their corresponding pattern IDs) as a map. In particular, the
/// representation used by a DFA for this map is not amenable to mutation,
/// so if things need to be changed (like when shuffling states), it's
/// often easier to work with the map form.
pub(crate) fn set_pattern_map(
&mut self,
map: &BTreeMap<StateID, Vec<PatternID>>,
) -> Result<(), BuildError> {
self.ms = self.ms.new_with_map(map)?;
Ok(())
}
/// Find states that have a small number of non-loop transitions and mark
/// them as candidates for acceleration during search.
pub(crate) fn accelerate(&mut self) {
// dead and quit states can never be accelerated.
if self.state_len() <= 2 {
return;
}
// Go through every state and record their accelerator, if possible.
let mut accels = BTreeMap::new();
// Count the number of accelerated match, start and non-match/start
// states.
let (mut cmatch, mut cstart, mut cnormal) = (0, 0, 0);
for state in self.states() {
if let Some(accel) = state.accelerate(self.byte_classes()) {
debug!(
"accelerating full DFA state {}: {:?}",
state.id().as_usize(),
accel,
);
accels.insert(state.id(), accel);
if self.is_match_state(state.id()) {
cmatch += 1;
} else if self.is_start_state(state.id()) {
cstart += 1;
} else {
assert!(!self.is_dead_state(state.id()));
assert!(!self.is_quit_state(state.id()));
cnormal += 1;
}
}
}
// If no states were able to be accelerated, then we're done.
if accels.is_empty() {
return;
}
let original_accels_len = accels.len();
// A remapper keeps track of state ID changes. Once we're done
// shuffling, the remapper is used to rewrite all transitions in the
// DFA based on the new positions of states.
let mut remapper = Remapper::new(self);
// As we swap states, if they are match states, we need to swap their
// pattern ID lists too (for multi-regexes). We do this by converting
// the lists to an easily swappable map, and then convert back to
// MatchStates once we're done.
let mut new_matches = self.ms.to_map(self);
// There is at least one state that gets accelerated, so these are
// guaranteed to get set to sensible values below.
self.special.min_accel = StateID::MAX;
self.special.max_accel = StateID::ZERO;
let update_special_accel =
|special: &mut Special, accel_id: StateID| {
special.min_accel = cmp::min(special.min_accel, accel_id);
special.max_accel = cmp::max(special.max_accel, accel_id);
};
// Start by shuffling match states. Any match states that are
// accelerated get moved to the end of the match state range.
if cmatch > 0 && self.special.matches() {
// N.B. special.{min,max}_match do not need updating, since the
// range/number of match states does not change. Only the ordering
// of match states may change.
let mut next_id = self.special.max_match;
let mut cur_id = next_id;
while cur_id >= self.special.min_match {
if let Some(accel) = accels.remove(&cur_id) {
accels.insert(next_id, accel);
update_special_accel(&mut self.special, next_id);
// No need to do any actual swapping for equivalent IDs.
if cur_id != next_id {
remapper.swap(self, cur_id, next_id);
// Swap pattern IDs for match states.
let cur_pids = new_matches.remove(&cur_id).unwrap();
let next_pids = new_matches.remove(&next_id).unwrap();
new_matches.insert(cur_id, next_pids);
new_matches.insert(next_id, cur_pids);
}
next_id = self.tt.prev_state_id(next_id);
}
cur_id = self.tt.prev_state_id(cur_id);
}
}
// This is where it gets tricky. Without acceleration, start states
// normally come right after match states. But we want accelerated
// states to be a single contiguous range (to make it very fast
// to determine whether a state *is* accelerated), while also keeping
// match and starting states as contiguous ranges for the same reason.
// So what we do here is shuffle states such that it looks like this:
//
// DQMMMMAAAAASSSSSSNNNNNNN
// | |
// |---------|
// accelerated states
//
// Where:
// D - dead state
// Q - quit state
// M - match state (may be accelerated)
// A - normal state that is accelerated
// S - start state (may be accelerated)
// N - normal state that is NOT accelerated
//
// We implement this by shuffling states, which is done by a sequence
// of pairwise swaps. We start by looking at all normal states to be
// accelerated. When we find one, we swap it with the earliest starting
// state, and then swap that with the earliest normal state. This
// preserves the contiguous property.
//
// Once we're done looking for accelerated normal states, now we look
// for accelerated starting states by moving them to the beginning
// of the starting state range (just like we moved accelerated match
// states to the end of the matching state range).
//
// For a more detailed/different perspective on this, see the docs
// in dfa/special.rs.
if cnormal > 0 {
// our next available starting and normal states for swapping.
let mut next_start_id = self.special.min_start;
let mut cur_id = self.to_state_id(self.state_len() - 1);
// This is guaranteed to exist since cnormal > 0.
let mut next_norm_id =
self.tt.next_state_id(self.special.max_start);
while cur_id >= next_norm_id {
if let Some(accel) = accels.remove(&cur_id) {
remapper.swap(self, next_start_id, cur_id);
remapper.swap(self, next_norm_id, cur_id);
// Keep our accelerator map updated with new IDs if the
// states we swapped were also accelerated.
if let Some(accel2) = accels.remove(&next_norm_id) {
accels.insert(cur_id, accel2);
}
if let Some(accel2) = accels.remove(&next_start_id) {
accels.insert(next_norm_id, accel2);
}
accels.insert(next_start_id, accel);
update_special_accel(&mut self.special, next_start_id);
// Our start range shifts one to the right now.
self.special.min_start =
self.tt.next_state_id(self.special.min_start);
self.special.max_start =
self.tt.next_state_id(self.special.max_start);
next_start_id = self.tt.next_state_id(next_start_id);
next_norm_id = self.tt.next_state_id(next_norm_id);
}
// This is pretty tricky, but if our 'next_norm_id' state also
// happened to be accelerated, then the result is that it is
// now in the position of cur_id, so we need to consider it
// again. This loop is still guaranteed to terminate though,
// because when accels contains cur_id, we're guaranteed to
// increment next_norm_id even if cur_id remains unchanged.
if !accels.contains_key(&cur_id) {
cur_id = self.tt.prev_state_id(cur_id);
}
}
}
// Just like we did for match states, but we want to move accelerated
// start states to the beginning of the range instead of the end.
if cstart > 0 {
// N.B. special.{min,max}_start do not need updating, since the
// range/number of start states does not change at this point. Only
// the ordering of start states may change.
let mut next_id = self.special.min_start;
let mut cur_id = next_id;
while cur_id <= self.special.max_start {
if let Some(accel) = accels.remove(&cur_id) {
remapper.swap(self, cur_id, next_id);
accels.insert(next_id, accel);
update_special_accel(&mut self.special, next_id);
next_id = self.tt.next_state_id(next_id);
}
cur_id = self.tt.next_state_id(cur_id);
}
}
// Remap all transitions in our DFA and assert some things.
remapper.remap(self);
// This unwrap is OK because acceleration never changes the number of
// match states or patterns in those match states. Since acceleration
// runs after the pattern map has been set at least once, we know that
// our match states cannot error.
self.set_pattern_map(&new_matches).unwrap();
self.special.set_max();
self.special.validate().expect("special state ranges should validate");
self.special
.validate_state_len(self.state_len(), self.stride2())
.expect(
"special state ranges should be consistent with state length",
);
assert_eq!(
self.special.accel_len(self.stride()),
// We record the number of accelerated states initially detected
// since the accels map is itself mutated in the process above.
// If mutated incorrectly, its size may change, and thus can't be
// trusted as a source of truth of how many accelerated states we
// expected there to be.
original_accels_len,
"mismatch with expected number of accelerated states",
);
// And finally record our accelerators. We kept our accels map updated
// as we shuffled states above, so the accelerators should now
// correspond to a contiguous range in the state ID space. (Which we
// assert.)
let mut prev: Option<StateID> = None;
for (id, accel) in accels {
assert!(prev.map_or(true, |p| self.tt.next_state_id(p) == id));
prev = Some(id);
self.accels.add(accel);
}
}
/// Shuffle the states in this DFA so that starting states, match
/// states and accelerated states are all contiguous.
///
/// See dfa/special.rs for more details.
pub(crate) fn shuffle(
&mut self,
mut matches: BTreeMap<StateID, Vec<PatternID>>,
) -> Result<(), BuildError> {
// The determinizer always adds a quit state and it is always second.
self.special.quit_id = self.to_state_id(1);
// If all we have are the dead and quit states, then we're done and
// the DFA will never produce a match.
if self.state_len() <= 2 {
self.special.set_max();
return Ok(());
}
// Collect all our non-DEAD start states into a convenient set and
// confirm there is no overlap with match states. In the classicl DFA
// construction, start states can be match states. But because of
// look-around, we delay all matches by a byte, which prevents start
// states from being match states.
let mut is_start: BTreeSet<StateID> = BTreeSet::new();
for (start_id, _, _) in self.starts() {
// If a starting configuration points to a DEAD state, then we
// don't want to shuffle it. The DEAD state is always the first
// state with ID=0. So we can just leave it be.
if start_id == DEAD {
continue;
}
assert!(
!matches.contains_key(&start_id),
"{:?} is both a start and a match state, which is not allowed",
start_id,
);
is_start.insert(start_id);
}
// We implement shuffling by a sequence of pairwise swaps of states.
// Since we have a number of things referencing states via their
// IDs and swapping them changes their IDs, we need to record every
// swap we make so that we can remap IDs. The remapper handles this
// book-keeping for us.
let mut remapper = Remapper::new(self);
// Shuffle matching states.
if matches.is_empty() {
self.special.min_match = DEAD;
self.special.max_match = DEAD;
} else {
// The determinizer guarantees that the first two states are the
// dead and quit states, respectively. We want our match states to
// come right after quit.
let mut next_id = self.to_state_id(2);
let mut new_matches = BTreeMap::new();
self.special.min_match = next_id;
for (id, pids) in matches {
remapper.swap(self, next_id, id);
new_matches.insert(next_id, pids);
// If we swapped a start state, then update our set.
if is_start.contains(&next_id) {
is_start.remove(&next_id);
is_start.insert(id);
}
next_id = self.tt.next_state_id(next_id);
}
matches = new_matches;
self.special.max_match = cmp::max(
self.special.min_match,
self.tt.prev_state_id(next_id),
);
}
// Shuffle starting states.
{
let mut next_id = self.to_state_id(2);
if self.special.matches() {
next_id = self.tt.next_state_id(self.special.max_match);
}
self.special.min_start = next_id;
for id in is_start {
remapper.swap(self, next_id, id);
next_id = self.tt.next_state_id(next_id);
}
self.special.max_start = cmp::max(
self.special.min_start,
self.tt.prev_state_id(next_id),
);
}
// Finally remap all transitions in our DFA.
remapper.remap(self);
self.set_pattern_map(&matches)?;
self.special.set_max();
self.special.validate().expect("special state ranges should validate");
self.special
.validate_state_len(self.state_len(), self.stride2())
.expect(
"special state ranges should be consistent with state length",
);
Ok(())
}
/// Checks whether there are universal start states (both anchored and
/// unanchored), and if so, sets the relevant fields to the start state
/// IDs.
///
/// Universal start states occur precisely when the all patterns in the
/// DFA have no look-around assertions in their prefix.
fn set_universal_starts(&mut self) {
assert_eq!(6, Start::len(), "expected 6 start configurations");
let start_id = |dfa: &mut OwnedDFA, inp: &Input<'_>, start: Start| {
// This OK because we only call 'start' under conditions
// in which we know it will succeed.
dfa.st.start(inp, start).expect("valid Input configuration")
};
if self.start_kind().has_unanchored() {
let inp = Input::new("").anchored(Anchored::No);
let sid = start_id(self, &inp, Start::NonWordByte);
if sid == start_id(self, &inp, Start::WordByte)
&& sid == start_id(self, &inp, Start::Text)
&& sid == start_id(self, &inp, Start::LineLF)
&& sid == start_id(self, &inp, Start::LineCR)
&& sid == start_id(self, &inp, Start::CustomLineTerminator)
{
self.st.universal_start_unanchored = Some(sid);
}
}
if self.start_kind().has_anchored() {
let inp = Input::new("").anchored(Anchored::Yes);
let sid = start_id(self, &inp, Start::NonWordByte);
if sid == start_id(self, &inp, Start::WordByte)
&& sid == start_id(self, &inp, Start::Text)
&& sid == start_id(self, &inp, Start::LineLF)
&& sid == start_id(self, &inp, Start::LineCR)
&& sid == start_id(self, &inp, Start::CustomLineTerminator)
{
self.st.universal_start_anchored = Some(sid);
}
}
}
}
// A variety of generic internal methods for accessing DFA internals.
impl<T: AsRef<[u32]>> DFA<T> {
/// Return the info about special states.
pub(crate) fn special(&self) -> &Special {
&self.special
}
/// Return the info about special states as a mutable borrow.
#[cfg(feature = "dfa-build")]
pub(crate) fn special_mut(&mut self) -> &mut Special {
&mut self.special
}
/// Returns the quit set (may be empty) used by this DFA.
pub(crate) fn quitset(&self) -> &ByteSet {
&self.quitset
}
/// Returns the flags for this DFA.
pub(crate) fn flags(&self) -> &Flags {
&self.flags
}
/// Returns an iterator over all states in this DFA.
///
/// This iterator yields a tuple for each state. The first element of the
/// tuple corresponds to a state's identifier, and the second element
/// corresponds to the state itself (comprised of its transitions).
pub(crate) fn states(&self) -> StateIter<'_, T> {
self.tt.states()
}
/// Return the total number of states in this DFA. Every DFA has at least
/// 1 state, even the empty DFA.
pub(crate) fn state_len(&self) -> usize {
self.tt.len()
}
/// Return an iterator over all pattern IDs for the given match state.
///
/// If the given state is not a match state, then this panics.
#[cfg(feature = "dfa-build")]
pub(crate) fn pattern_id_slice(&self, id: StateID) -> &[PatternID] {
assert!(self.is_match_state(id));
self.ms.pattern_id_slice(self.match_state_index(id))
}
/// Return the total number of pattern IDs for the given match state.
///
/// If the given state is not a match state, then this panics.
pub(crate) fn match_pattern_len(&self, id: StateID) -> usize {
assert!(self.is_match_state(id));
self.ms.pattern_len(self.match_state_index(id))
}
/// Returns the total number of patterns matched by this DFA.
pub(crate) fn pattern_len(&self) -> usize {
self.ms.pattern_len
}
/// Returns a map from match state ID to a list of pattern IDs that match
/// in that state.
#[cfg(feature = "dfa-build")]
pub(crate) fn pattern_map(&self) -> BTreeMap<StateID, Vec<PatternID>> {
self.ms.to_map(self)
}
/// Returns the ID of the quit state for this DFA.
#[cfg(feature = "dfa-build")]
pub(crate) fn quit_id(&self) -> StateID {
self.to_state_id(1)
}
/// Convert the given state identifier to the state's index. The state's
/// index corresponds to the position in which it appears in the transition
/// table. When a DFA is NOT premultiplied, then a state's identifier is
/// also its index. When a DFA is premultiplied, then a state's identifier
/// is equal to `index * alphabet_len`. This routine reverses that.
pub(crate) fn to_index(&self, id: StateID) -> usize {
self.tt.to_index(id)
}
/// Convert an index to a state (in the range 0..self.state_len()) to an
/// actual state identifier.
///
/// This is useful when using a `Vec<T>` as an efficient map keyed by state
/// to some other information (such as a remapped state ID).
#[cfg(feature = "dfa-build")]
pub(crate) fn to_state_id(&self, index: usize) -> StateID {
self.tt.to_state_id(index)
}
/// Return the table of state IDs for this DFA's start states.
pub(crate) fn starts(&self) -> StartStateIter<'_> {
self.st.iter()
}
/// Returns the index of the match state for the given ID. If the
/// given ID does not correspond to a match state, then this may
/// panic or produce an incorrect result.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn match_state_index(&self, id: StateID) -> usize {
debug_assert!(self.is_match_state(id));
// This is one of the places where we rely on the fact that match
// states are contiguous in the transition table. Namely, that the
// first match state ID always corresponds to dfa.special.min_match.
// From there, since we know the stride, we can compute the overall
// index of any match state given the match state's ID.
let min = self.special().min_match.as_usize();
// CORRECTNESS: We're allowed to produce an incorrect result or panic,
// so both the subtraction and the unchecked StateID construction is
// OK.
self.to_index(StateID::new_unchecked(id.as_usize() - min))
}
/// Returns the index of the accelerator state for the given ID. If the
/// given ID does not correspond to an accelerator state, then this may
/// panic or produce an incorrect result.
fn accelerator_index(&self, id: StateID) -> usize {
let min = self.special().min_accel.as_usize();
// CORRECTNESS: We're allowed to produce an incorrect result or panic,
// so both the subtraction and the unchecked StateID construction is
// OK.
self.to_index(StateID::new_unchecked(id.as_usize() - min))
}
/// Return the accelerators for this DFA.
fn accels(&self) -> Accels<&[u32]> {
self.accels.as_ref()
}
/// Return this DFA's transition table as a slice.
fn trans(&self) -> &[StateID] {
self.tt.table()
}
}
impl<T: AsRef<[u32]>> fmt::Debug for DFA<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
writeln!(f, "dense::DFA(")?;
for state in self.states() {
fmt_state_indicator(f, self, state.id())?;
let id = if f.alternate() {
state.id().as_usize()
} else {
self.to_index(state.id())
};
write!(f, "{:06?}: ", id)?;
state.fmt(f)?;
write!(f, "\n")?;
}
writeln!(f, "")?;
for (i, (start_id, anchored, sty)) in self.starts().enumerate() {
let id = if f.alternate() {
start_id.as_usize()
} else {
self.to_index(start_id)
};
if i % self.st.stride == 0 {
match anchored {
Anchored::No => writeln!(f, "START-GROUP(unanchored)")?,
Anchored::Yes => writeln!(f, "START-GROUP(anchored)")?,
Anchored::Pattern(pid) => {
writeln!(f, "START_GROUP(pattern: {:?})", pid)?
}
}
}
writeln!(f, " {:?} => {:06?}", sty, id)?;
}
if self.pattern_len() > 1 {
writeln!(f, "")?;
for i in 0..self.ms.len() {
let id = self.ms.match_state_id(self, i);
let id = if f.alternate() {
id.as_usize()
} else {
self.to_index(id)
};
write!(f, "MATCH({:06?}): ", id)?;
for (i, &pid) in self.ms.pattern_id_slice(i).iter().enumerate()
{
if i > 0 {
write!(f, ", ")?;
}
write!(f, "{:?}", pid)?;
}
writeln!(f, "")?;
}
}
writeln!(f, "state length: {:?}", self.state_len())?;
writeln!(f, "pattern length: {:?}", self.pattern_len())?;
writeln!(f, "flags: {:?}", self.flags)?;
writeln!(f, ")")?;
Ok(())
}
}
// SAFETY: We assert that our implementation of each method is correct.
unsafe impl<T: AsRef<[u32]>> Automaton for DFA<T> {
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_special_state(&self, id: StateID) -> bool {
self.special.is_special_state(id)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_dead_state(&self, id: StateID) -> bool {
self.special.is_dead_state(id)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_quit_state(&self, id: StateID) -> bool {
self.special.is_quit_state(id)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_match_state(&self, id: StateID) -> bool {
self.special.is_match_state(id)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_start_state(&self, id: StateID) -> bool {
self.special.is_start_state(id)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_accel_state(&self, id: StateID) -> bool {
self.special.is_accel_state(id)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn next_state(&self, current: StateID, input: u8) -> StateID {
let input = self.byte_classes().get(input);
let o = current.as_usize() + usize::from(input);
self.trans()[o]
}
#[cfg_attr(feature = "perf-inline", inline(always))]
unsafe fn next_state_unchecked(
&self,
current: StateID,
byte: u8,
) -> StateID {
// We don't (or shouldn't) need an unchecked variant for the byte
// class mapping, since bound checks should be omitted automatically
// by virtue of its representation. If this ends up not being true as
// confirmed by codegen, please file an issue. ---AG
let class = self.byte_classes().get(byte);
let o = current.as_usize() + usize::from(class);
let next = *self.trans().get_unchecked(o);
next
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn next_eoi_state(&self, current: StateID) -> StateID {
let eoi = self.byte_classes().eoi().as_usize();
let o = current.as_usize() + eoi;
self.trans()[o]
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn pattern_len(&self) -> usize {
self.ms.pattern_len
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn match_len(&self, id: StateID) -> usize {
self.match_pattern_len(id)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn match_pattern(&self, id: StateID, match_index: usize) -> PatternID {
// This is an optimization for the very common case of a DFA with a
// single pattern. This conditional avoids a somewhat more costly path
// that finds the pattern ID from the state machine, which requires
// a bit of slicing/pointer-chasing. This optimization tends to only
// matter when matches are frequent.
if self.ms.pattern_len == 1 {
return PatternID::ZERO;
}
let state_index = self.match_state_index(id);
self.ms.pattern_id(state_index, match_index)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn has_empty(&self) -> bool {
self.flags.has_empty
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_utf8(&self) -> bool {
self.flags.is_utf8
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_always_start_anchored(&self) -> bool {
self.flags.is_always_start_anchored
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn start_state_forward(
&self,
input: &Input<'_>,
) -> Result<StateID, MatchError> {
if !self.quitset.is_empty() && input.start() > 0 {
let offset = input.start() - 1;
let byte = input.haystack()[offset];
if self.quitset.contains(byte) {
return Err(MatchError::quit(byte, offset));
}
}
let start = self.st.start_map.fwd(&input);
self.st.start(input, start)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn start_state_reverse(
&self,
input: &Input<'_>,
) -> Result<StateID, MatchError> {
if !self.quitset.is_empty() && input.end() < input.haystack().len() {
let offset = input.end();
let byte = input.haystack()[offset];
if self.quitset.contains(byte) {
return Err(MatchError::quit(byte, offset));
}
}
let start = self.st.start_map.rev(&input);
self.st.start(input, start)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn universal_start_state(&self, mode: Anchored) -> Option<StateID> {
match mode {
Anchored::No => self.st.universal_start_unanchored,
Anchored::Yes => self.st.universal_start_anchored,
Anchored::Pattern(_) => None,
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn accelerator(&self, id: StateID) -> &[u8] {
if !self.is_accel_state(id) {
return &[];
}
self.accels.needles(self.accelerator_index(id))
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn get_prefilter(&self) -> Option<&Prefilter> {
self.pre.as_ref()
}
}
/// The transition table portion of a dense DFA.
///
/// The transition table is the core part of the DFA in that it describes how
/// to move from one state to another based on the input sequence observed.
#[derive(Clone)]
pub(crate) struct TransitionTable<T> {
/// A contiguous region of memory representing the transition table in
/// row-major order. The representation is dense. That is, every state
/// has precisely the same number of transitions. The maximum number of
/// transitions per state is 257 (256 for each possible byte value, plus 1
/// for the special EOI transition). If a DFA has been instructed to use
/// byte classes (the default), then the number of transitions is usually
/// substantially fewer.
///
/// In practice, T is either `Vec<u32>` or `&[u32]`.
table: T,
/// A set of equivalence classes, where a single equivalence class
/// represents a set of bytes that never discriminate between a match
/// and a non-match in the DFA. Each equivalence class corresponds to a
/// single character in this DFA's alphabet, where the maximum number of
/// characters is 257 (each possible value of a byte plus the special
/// EOI transition). Consequently, the number of equivalence classes
/// corresponds to the number of transitions for each DFA state. Note
/// though that the *space* used by each DFA state in the transition table
/// may be larger. The total space used by each DFA state is known as the
/// stride.
///
/// The only time the number of equivalence classes is fewer than 257 is if
/// the DFA's kind uses byte classes (which is the default). Equivalence
/// classes should generally only be disabled when debugging, so that
/// the transitions themselves aren't obscured. Disabling them has no
/// other benefit, since the equivalence class map is always used while
/// searching. In the vast majority of cases, the number of equivalence
/// classes is substantially smaller than 257, particularly when large
/// Unicode classes aren't used.
classes: ByteClasses,
/// The stride of each DFA state, expressed as a power-of-two exponent.
///
/// The stride of a DFA corresponds to the total amount of space used by
/// each DFA state in the transition table. This may be bigger than the
/// size of a DFA's alphabet, since the stride is always the smallest
/// power of two greater than or equal to the alphabet size.
///
/// While this wastes space, this avoids the need for integer division
/// to convert between premultiplied state IDs and their corresponding
/// indices. Instead, we can use simple bit-shifts.
///
/// See the docs for the `stride2` method for more details.
///
/// The minimum `stride2` value is `1` (corresponding to a stride of `2`)
/// while the maximum `stride2` value is `9` (corresponding to a stride of
/// `512`). The maximum is not `8` since the maximum alphabet size is `257`
/// when accounting for the special EOI transition. However, an alphabet
/// length of that size is exceptionally rare since the alphabet is shrunk
/// into equivalence classes.
stride2: usize,
}
impl<'a> TransitionTable<&'a [u32]> {
/// Deserialize a transition table starting at the beginning of `slice`.
/// Upon success, return the total number of bytes read along with the
/// transition table.
///
/// If there was a problem deserializing any part of the transition table,
/// then this returns an error. Notably, if the given slice does not have
/// the same alignment as `StateID`, then this will return an error (among
/// other possible errors).
///
/// This is guaranteed to execute in constant time.
///
/// # Safety
///
/// This routine is not safe because it does not check the validity of the
/// transition table itself. In particular, the transition table can be
/// quite large, so checking its validity can be somewhat expensive. An
/// invalid transition table is not safe because other code may rely on the
/// transition table being correct (such as explicit bounds check elision).
/// Therefore, an invalid transition table can lead to undefined behavior.
///
/// Callers that use this function must either pass on the safety invariant
/// or guarantee that the bytes given contain a valid transition table.
/// This guarantee is upheld by the bytes written by `write_to`.
unsafe fn from_bytes_unchecked(
mut slice: &'a [u8],
) -> Result<(TransitionTable<&'a [u32]>, usize), DeserializeError> {
let slice_start = slice.as_ptr().as_usize();
let (state_len, nr) =
wire::try_read_u32_as_usize(slice, "state length")?;
slice = &slice[nr..];
let (stride2, nr) = wire::try_read_u32_as_usize(slice, "stride2")?;
slice = &slice[nr..];
let (classes, nr) = ByteClasses::from_bytes(slice)?;
slice = &slice[nr..];
// The alphabet length (determined by the byte class map) cannot be
// bigger than the stride (total space used by each DFA state).
if stride2 > 9 {
return Err(DeserializeError::generic(
"dense DFA has invalid stride2 (too big)",
));
}
// It also cannot be zero, since even a DFA that never matches anything
// has a non-zero number of states with at least two equivalence
// classes: one for all 256 byte values and another for the EOI
// sentinel.
if stride2 < 1 {
return Err(DeserializeError::generic(
"dense DFA has invalid stride2 (too small)",
));
}
// This is OK since 1 <= stride2 <= 9.
let stride =
1usize.checked_shl(u32::try_from(stride2).unwrap()).unwrap();
if classes.alphabet_len() > stride {
return Err(DeserializeError::generic(
"alphabet size cannot be bigger than transition table stride",
));
}
let trans_len =
wire::shl(state_len, stride2, "dense table transition length")?;
let table_bytes_len = wire::mul(
trans_len,
StateID::SIZE,
"dense table state byte length",
)?;
wire::check_slice_len(slice, table_bytes_len, "transition table")?;
wire::check_alignment::<StateID>(slice)?;
let table_bytes = &slice[..table_bytes_len];
slice = &slice[table_bytes_len..];
// SAFETY: Since StateID is always representable as a u32, all we need
// to do is ensure that we have the proper length and alignment. We've
// checked both above, so the cast below is safe.
//
// N.B. This is the only not-safe code in this function.
let table = core::slice::from_raw_parts(
table_bytes.as_ptr().cast::<u32>(),
trans_len,
);
let tt = TransitionTable { table, classes, stride2 };
Ok((tt, slice.as_ptr().as_usize() - slice_start))
}
}
#[cfg(feature = "dfa-build")]
impl TransitionTable<Vec<u32>> {
/// Create a minimal transition table with just two states: a dead state
/// and a quit state. The alphabet length and stride of the transition
/// table is determined by the given set of equivalence classes.
fn minimal(classes: ByteClasses) -> TransitionTable<Vec<u32>> {
let mut tt = TransitionTable {
table: vec![],
classes,
stride2: classes.stride2(),
};
// Two states, regardless of alphabet size, can always fit into u32.
tt.add_empty_state().unwrap(); // dead state
tt.add_empty_state().unwrap(); // quit state
tt
}
/// Set a transition in this table. Both the `from` and `to` states must
/// already exist, otherwise this panics. `unit` should correspond to the
/// transition out of `from` to set to `to`.
fn set(&mut self, from: StateID, unit: alphabet::Unit, to: StateID) {
assert!(self.is_valid(from), "invalid 'from' state");
assert!(self.is_valid(to), "invalid 'to' state");
self.table[from.as_usize() + self.classes.get_by_unit(unit)] =
to.as_u32();
}
/// Add an empty state (a state where all transitions lead to a dead state)
/// and return its identifier. The identifier returned is guaranteed to
/// not point to any other existing state.
///
/// If adding a state would exhaust the state identifier space, then this
/// returns an error.
fn add_empty_state(&mut self) -> Result<StateID, BuildError> {
// Normally, to get a fresh state identifier, we would just
// take the index of the next state added to the transition
// table. However, we actually perform an optimization here
// that premultiplies state IDs by the stride, such that they
// point immediately at the beginning of their transitions in
// the transition table. This avoids an extra multiplication
// instruction for state lookup at search time.
//
// Premultiplied identifiers means that instead of your matching
// loop looking something like this:
//
// state = dfa.start
// for byte in haystack:
// next = dfa.transitions[state * stride + byte]
// if dfa.is_match(next):
// return true
// return false
//
// it can instead look like this:
//
// state = dfa.start
// for byte in haystack:
// next = dfa.transitions[state + byte]
// if dfa.is_match(next):
// return true
// return false
//
// In other words, we save a multiplication instruction in the
// critical path. This turns out to be a decent performance win.
// The cost of using premultiplied state ids is that they can
// require a bigger state id representation. (And they also make
// the code a bit more complex, especially during minimization and
// when reshuffling states, as one needs to convert back and forth
// between state IDs and state indices.)
//
// To do this, we simply take the index of the state into the
// entire transition table, rather than the index of the state
// itself. e.g., If the stride is 64, then the ID of the 3rd state
// is 192, not 2.
let next = self.table.len();
let id =
StateID::new(next).map_err(|_| BuildError::too_many_states())?;
self.table.extend(iter::repeat(0).take(self.stride()));
Ok(id)
}
/// Swap the two states given in this transition table.
///
/// This routine does not do anything to check the correctness of this
/// swap. Callers must ensure that other states pointing to id1 and id2 are
/// updated appropriately.
///
/// Both id1 and id2 must point to valid states, otherwise this panics.
fn swap(&mut self, id1: StateID, id2: StateID) {
assert!(self.is_valid(id1), "invalid 'id1' state: {:?}", id1);
assert!(self.is_valid(id2), "invalid 'id2' state: {:?}", id2);
// We only need to swap the parts of the state that are used. So if the
// stride is 64, but the alphabet length is only 33, then we save a lot
// of work.
for b in 0..self.classes.alphabet_len() {
self.table.swap(id1.as_usize() + b, id2.as_usize() + b);
}
}
/// Remap the transitions for the state given according to the function
/// given. This applies the given map function to every transition in the
/// given state and changes the transition in place to the result of the
/// map function for that transition.
fn remap(&mut self, id: StateID, map: impl Fn(StateID) -> StateID) {
for byte in 0..self.alphabet_len() {
let i = id.as_usize() + byte;
let next = self.table()[i];
self.table_mut()[id.as_usize() + byte] = map(next);
}
}
/// Truncate the states in this transition table to the given length.
///
/// This routine does not do anything to check the correctness of this
/// truncation. Callers must ensure that other states pointing to truncated
/// states are updated appropriately.
fn truncate(&mut self, len: usize) {
self.table.truncate(len << self.stride2);
}
}
impl<T: AsRef<[u32]>> TransitionTable<T> {
/// Writes a serialized form of this transition table to the buffer given.
/// If the buffer is too small, then an error is returned. To determine
/// how big the buffer must be, use `write_to_len`.
fn write_to<E: Endian>(
&self,
mut dst: &mut [u8],
) -> Result<usize, SerializeError> {
let nwrite = self.write_to_len();
if dst.len() < nwrite {
return Err(SerializeError::buffer_too_small("transition table"));
}
dst = &mut dst[..nwrite];
// write state length
// Unwrap is OK since number of states is guaranteed to fit in a u32.
E::write_u32(u32::try_from(self.len()).unwrap(), dst);
dst = &mut dst[size_of::<u32>()..];
// write state stride (as power of 2)
// Unwrap is OK since stride2 is guaranteed to be <= 9.
E::write_u32(u32::try_from(self.stride2).unwrap(), dst);
dst = &mut dst[size_of::<u32>()..];
// write byte class map
let n = self.classes.write_to(dst)?;
dst = &mut dst[n..];
// write actual transitions
for &sid in self.table() {
let n = wire::write_state_id::<E>(sid, &mut dst);
dst = &mut dst[n..];
}
Ok(nwrite)
}
/// Returns the number of bytes the serialized form of this transition
/// table will use.
fn write_to_len(&self) -> usize {
size_of::<u32>() // state length
+ size_of::<u32>() // stride2
+ self.classes.write_to_len()
+ (self.table().len() * StateID::SIZE)
}
/// Validates that every state ID in this transition table is valid.
///
/// That is, every state ID can be used to correctly index a state in this
/// table.
fn validate(&self, sp: &Special) -> Result<(), DeserializeError> {
for state in self.states() {
// We check that the ID itself is well formed. That is, if it's
// a special state then it must actually be a quit, dead, accel,
// match or start state.
if sp.is_special_state(state.id()) {
let is_actually_special = sp.is_dead_state(state.id())
|| sp.is_quit_state(state.id())
|| sp.is_match_state(state.id())
|| sp.is_start_state(state.id())
|| sp.is_accel_state(state.id());
if !is_actually_special {
// This is kind of a cryptic error message...
return Err(DeserializeError::generic(
"found dense state tagged as special but \
wasn't actually special",
));
}
}
for (_, to) in state.transitions() {
if !self.is_valid(to) {
return Err(DeserializeError::generic(
"found invalid state ID in transition table",
));
}
}
}
Ok(())
}
/// Converts this transition table to a borrowed value.
fn as_ref(&self) -> TransitionTable<&'_ [u32]> {
TransitionTable {
table: self.table.as_ref(),
classes: self.classes.clone(),
stride2: self.stride2,
}
}
/// Converts this transition table to an owned value.
#[cfg(feature = "alloc")]
fn to_owned(&self) -> TransitionTable<alloc::vec::Vec<u32>> {
TransitionTable {
table: self.table.as_ref().to_vec(),
classes: self.classes.clone(),
stride2: self.stride2,
}
}
/// Return the state for the given ID. If the given ID is not valid, then
/// this panics.
fn state(&self, id: StateID) -> State<'_> {
assert!(self.is_valid(id));
let i = id.as_usize();
State {
id,
stride2: self.stride2,
transitions: &self.table()[i..i + self.alphabet_len()],
}
}
/// Returns an iterator over all states in this transition table.
///
/// This iterator yields a tuple for each state. The first element of the
/// tuple corresponds to a state's identifier, and the second element
/// corresponds to the state itself (comprised of its transitions).
fn states(&self) -> StateIter<'_, T> {
StateIter {
tt: self,
it: self.table().chunks(self.stride()).enumerate(),
}
}
/// Convert a state identifier to an index to a state (in the range
/// 0..self.len()).
///
/// This is useful when using a `Vec<T>` as an efficient map keyed by state
/// to some other information (such as a remapped state ID).
///
/// If the given ID is not valid, then this may panic or produce an
/// incorrect index.
fn to_index(&self, id: StateID) -> usize {
id.as_usize() >> self.stride2
}
/// Convert an index to a state (in the range 0..self.len()) to an actual
/// state identifier.
///
/// This is useful when using a `Vec<T>` as an efficient map keyed by state
/// to some other information (such as a remapped state ID).
///
/// If the given index is not in the specified range, then this may panic
/// or produce an incorrect state ID.
fn to_state_id(&self, index: usize) -> StateID {
// CORRECTNESS: If the given index is not valid, then it is not
// required for this to panic or return a valid state ID.
StateID::new_unchecked(index << self.stride2)
}
/// Returns the state ID for the state immediately following the one given.
///
/// This does not check whether the state ID returned is invalid. In fact,
/// if the state ID given is the last state in this DFA, then the state ID
/// returned is guaranteed to be invalid.
#[cfg(feature = "dfa-build")]
fn next_state_id(&self, id: StateID) -> StateID {
self.to_state_id(self.to_index(id).checked_add(1).unwrap())
}
/// Returns the state ID for the state immediately preceding the one given.
///
/// If the dead ID given (which is zero), then this panics.
#[cfg(feature = "dfa-build")]
fn prev_state_id(&self, id: StateID) -> StateID {
self.to_state_id(self.to_index(id).checked_sub(1).unwrap())
}
/// Returns the table as a slice of state IDs.
fn table(&self) -> &[StateID] {
wire::u32s_to_state_ids(self.table.as_ref())
}
/// Returns the total number of states in this transition table.
///
/// Note that a DFA always has at least two states: the dead and quit
/// states. In particular, the dead state always has ID 0 and is
/// correspondingly always the first state. The dead state is never a match
/// state.
fn len(&self) -> usize {
self.table().len() >> self.stride2
}
/// Returns the total stride for every state in this DFA. This corresponds
/// to the total number of transitions used by each state in this DFA's
/// transition table.
fn stride(&self) -> usize {
1 << self.stride2
}
/// Returns the total number of elements in the alphabet for this
/// transition table. This is always less than or equal to `self.stride()`.
/// It is only equal when the alphabet length is a power of 2. Otherwise,
/// it is always strictly less.
fn alphabet_len(&self) -> usize {
self.classes.alphabet_len()
}
/// Returns true if and only if the given state ID is valid for this
/// transition table. Validity in this context means that the given ID can
/// be used as a valid offset with `self.stride()` to index this transition
/// table.
fn is_valid(&self, id: StateID) -> bool {
let id = id.as_usize();
id < self.table().len() && id % self.stride() == 0
}
/// Return the memory usage, in bytes, of this transition table.
///
/// This does not include the size of a `TransitionTable` value itself.
fn memory_usage(&self) -> usize {
self.table().len() * StateID::SIZE
}
}
#[cfg(feature = "dfa-build")]
impl<T: AsMut<[u32]>> TransitionTable<T> {
/// Returns the table as a slice of state IDs.
fn table_mut(&mut self) -> &mut [StateID] {
wire::u32s_to_state_ids_mut(self.table.as_mut())
}
}
/// The set of all possible starting states in a DFA.
///
/// The set of starting states corresponds to the possible choices one can make
/// in terms of starting a DFA. That is, before following the first transition,
/// you first need to select the state that you start in.
///
/// Normally, a DFA converted from an NFA that has a single starting state
/// would itself just have one starting state. However, our support for look
/// around generally requires more starting states. The correct starting state
/// is chosen based on certain properties of the position at which we begin
/// our search.
///
/// Before listing those properties, we first must define two terms:
///
/// * `haystack` - The bytes to execute the search. The search always starts
/// at the beginning of `haystack` and ends before or at the end of
/// `haystack`.
/// * `context` - The (possibly empty) bytes surrounding `haystack`. `haystack`
/// must be contained within `context` such that `context` is at least as big
/// as `haystack`.
///
/// This split is crucial for dealing with look-around. For example, consider
/// the context `foobarbaz`, the haystack `bar` and the regex `^bar$`. This
/// regex should _not_ match the haystack since `bar` does not appear at the
/// beginning of the input. Similarly, the regex `\Bbar\B` should match the
/// haystack because `bar` is not surrounded by word boundaries. But a search
/// that does not take context into account would not permit `\B` to match
/// since the beginning of any string matches a word boundary. Similarly, a
/// search that does not take context into account when searching `^bar$` in
/// the haystack `bar` would produce a match when it shouldn't.
///
/// Thus, it follows that the starting state is chosen based on the following
/// criteria, derived from the position at which the search starts in the
/// `context` (corresponding to the start of `haystack`):
///
/// 1. If the search starts at the beginning of `context`, then the `Text`
/// start state is used. (Since `^` corresponds to
/// `hir::Anchor::Start`.)
/// 2. If the search starts at a position immediately following a line
/// terminator, then the `Line` start state is used. (Since `(?m:^)`
/// corresponds to `hir::Anchor::StartLF`.)
/// 3. If the search starts at a position immediately following a byte
/// classified as a "word" character (`[_0-9a-zA-Z]`), then the `WordByte`
/// start state is used. (Since `(?-u:\b)` corresponds to a word boundary.)
/// 4. Otherwise, if the search starts at a position immediately following
/// a byte that is not classified as a "word" character (`[^_0-9a-zA-Z]`),
/// then the `NonWordByte` start state is used. (Since `(?-u:\B)`
/// corresponds to a not-word-boundary.)
///
/// (N.B. Unicode word boundaries are not supported by the DFA because they
/// require multi-byte look-around and this is difficult to support in a DFA.)
///
/// To further complicate things, we also support constructing individual
/// anchored start states for each pattern in the DFA. (Which is required to
/// implement overlapping regexes correctly, but is also generally useful.)
/// Thus, when individual start states for each pattern are enabled, then the
/// total number of start states represented is `4 + (4 * #patterns)`, where
/// the 4 comes from each of the 4 possibilities above. The first 4 represents
/// the starting states for the entire DFA, which support searching for
/// multiple patterns simultaneously (possibly unanchored).
///
/// If individual start states are disabled, then this will only store 4
/// start states. Typically, individual start states are only enabled when
/// constructing the reverse DFA for regex matching. But they are also useful
/// for building DFAs that can search for a specific pattern or even to support
/// both anchored and unanchored searches with the same DFA.
///
/// Note though that while the start table always has either `4` or
/// `4 + (4 * #patterns)` starting state *ids*, the total number of states
/// might be considerably smaller. That is, many of the IDs may be duplicative.
/// (For example, if a regex doesn't have a `\b` sub-pattern, then there's no
/// reason to generate a unique starting state for handling word boundaries.
/// Similarly for start/end anchors.)
#[derive(Clone)]
pub(crate) struct StartTable<T> {
/// The initial start state IDs.
///
/// In practice, T is either `Vec<u32>` or `&[u32]`.
///
/// The first `2 * stride` (currently always 8) entries always correspond
/// to the starts states for the entire DFA, with the first 4 entries being
/// for unanchored searches and the second 4 entries being for anchored
/// searches. To keep things simple, we always use 8 entries even if the
/// `StartKind` is not both.
///
/// After that, there are `stride * patterns` state IDs, where `patterns`
/// may be zero in the case of a DFA with no patterns or in the case where
/// the DFA was built without enabling starting states for each pattern.
table: T,
/// The starting state configuration supported. When 'both', both
/// unanchored and anchored searches work. When 'unanchored', anchored
/// searches panic. When 'anchored', unanchored searches panic.
kind: StartKind,
/// The start state configuration for every possible byte.
start_map: StartByteMap,
/// The number of starting state IDs per pattern.
stride: usize,
/// The total number of patterns for which starting states are encoded.
/// This is `None` for DFAs that were built without start states for each
/// pattern. Thus, one cannot use this field to say how many patterns
/// are in the DFA in all cases. It is specific to how many patterns are
/// represented in this start table.
pattern_len: Option<usize>,
/// The universal starting state for unanchored searches. This is only
/// present when the DFA supports unanchored searches and when all starting
/// state IDs for an unanchored search are equivalent.
universal_start_unanchored: Option<StateID>,
/// The universal starting state for anchored searches. This is only
/// present when the DFA supports anchored searches and when all starting
/// state IDs for an anchored search are equivalent.
universal_start_anchored: Option<StateID>,
}
#[cfg(feature = "dfa-build")]
impl StartTable<Vec<u32>> {
/// Create a valid set of start states all pointing to the dead state.
///
/// When the corresponding DFA is constructed with start states for each
/// pattern, then `patterns` should be the number of patterns. Otherwise,
/// it should be zero.
///
/// If the total table size could exceed the allocatable limit, then this
/// returns an error. In practice, this is unlikely to be able to occur,
/// since it's likely that allocation would have failed long before it got
/// to this point.
fn dead(
kind: StartKind,
lookm: &LookMatcher,
pattern_len: Option<usize>,
) -> Result<StartTable<Vec<u32>>, BuildError> {
if let Some(len) = pattern_len {
assert!(len <= PatternID::LIMIT);
}
let stride = Start::len();
// OK because 2*4 is never going to overflow anything.
let starts_len = stride.checked_mul(2).unwrap();
let pattern_starts_len =
match stride.checked_mul(pattern_len.unwrap_or(0)) {
Some(x) => x,
None => return Err(BuildError::too_many_start_states()),
};
let table_len = match starts_len.checked_add(pattern_starts_len) {
Some(x) => x,
None => return Err(BuildError::too_many_start_states()),
};
if let Err(_) = isize::try_from(table_len) {
return Err(BuildError::too_many_start_states());
}
let table = vec![DEAD.as_u32(); table_len];
let start_map = StartByteMap::new(lookm);
Ok(StartTable {
table,
kind,
start_map,
stride,
pattern_len,
universal_start_unanchored: None,
universal_start_anchored: None,
})
}
}
impl<'a> StartTable<&'a [u32]> {
/// Deserialize a table of start state IDs starting at the beginning of
/// `slice`. Upon success, return the total number of bytes read along with
/// the table of starting state IDs.
///
/// If there was a problem deserializing any part of the starting IDs,
/// then this returns an error. Notably, if the given slice does not have
/// the same alignment as `StateID`, then this will return an error (among
/// other possible errors).
///
/// This is guaranteed to execute in constant time.
///
/// # Safety
///
/// This routine is not safe because it does not check the validity of the
/// starting state IDs themselves. In particular, the number of starting
/// IDs can be of variable length, so it's possible that checking their
/// validity cannot be done in constant time. An invalid starting state
/// ID is not safe because other code may rely on the starting IDs being
/// correct (such as explicit bounds check elision). Therefore, an invalid
/// start ID can lead to undefined behavior.
///
/// Callers that use this function must either pass on the safety invariant
/// or guarantee that the bytes given contain valid starting state IDs.
/// This guarantee is upheld by the bytes written by `write_to`.
unsafe fn from_bytes_unchecked(
mut slice: &'a [u8],
) -> Result<(StartTable<&'a [u32]>, usize), DeserializeError> {
let slice_start = slice.as_ptr().as_usize();
let (kind, nr) = StartKind::from_bytes(slice)?;
slice = &slice[nr..];
let (start_map, nr) = StartByteMap::from_bytes(slice)?;
slice = &slice[nr..];
let (stride, nr) =
wire::try_read_u32_as_usize(slice, "start table stride")?;
slice = &slice[nr..];
if stride != Start::len() {
return Err(DeserializeError::generic(
"invalid starting table stride",
));
}
let (maybe_pattern_len, nr) =
wire::try_read_u32_as_usize(slice, "start table patterns")?;
slice = &slice[nr..];
let pattern_len = if maybe_pattern_len.as_u32() == u32::MAX {
None
} else {
Some(maybe_pattern_len)
};
if pattern_len.map_or(false, |len| len > PatternID::LIMIT) {
return Err(DeserializeError::generic(
"invalid number of patterns",
));
}
let (universal_unanchored, nr) =
wire::try_read_u32(slice, "universal unanchored start")?;
slice = &slice[nr..];
let universal_start_unanchored = if universal_unanchored == u32::MAX {
None
} else {
Some(StateID::try_from(universal_unanchored).map_err(|e| {
DeserializeError::state_id_error(
e,
"universal unanchored start",
)
})?)
};
let (universal_anchored, nr) =
wire::try_read_u32(slice, "universal anchored start")?;
slice = &slice[nr..];
let universal_start_anchored = if universal_anchored == u32::MAX {
None
} else {
Some(StateID::try_from(universal_anchored).map_err(|e| {
DeserializeError::state_id_error(e, "universal anchored start")
})?)
};
let pattern_table_size = wire::mul(
stride,
pattern_len.unwrap_or(0),
"invalid pattern length",
)?;
// Our start states always start with a two stride of start states for
// the entire automaton. The first stride is for unanchored starting
// states and the second stride is for anchored starting states. What
// follows it are an optional set of start states for each pattern.
let start_state_len = wire::add(
wire::mul(2, stride, "start state stride too big")?,
pattern_table_size,
"invalid 'any' pattern starts size",
)?;
let table_bytes_len = wire::mul(
start_state_len,
StateID::SIZE,
"pattern table bytes length",
)?;
wire::check_slice_len(slice, table_bytes_len, "start ID table")?;
wire::check_alignment::<StateID>(slice)?;
let table_bytes = &slice[..table_bytes_len];
slice = &slice[table_bytes_len..];
// SAFETY: Since StateID is always representable as a u32, all we need
// to do is ensure that we have the proper length and alignment. We've
// checked both above, so the cast below is safe.
//
// N.B. This is the only not-safe code in this function.
let table = core::slice::from_raw_parts(
table_bytes.as_ptr().cast::<u32>(),
start_state_len,
);
let st = StartTable {
table,
kind,
start_map,
stride,
pattern_len,
universal_start_unanchored,
universal_start_anchored,
};
Ok((st, slice.as_ptr().as_usize() - slice_start))
}
}
impl<T: AsRef<[u32]>> StartTable<T> {
/// Writes a serialized form of this start table to the buffer given. If
/// the buffer is too small, then an error is returned. To determine how
/// big the buffer must be, use `write_to_len`.
fn write_to<E: Endian>(
&self,
mut dst: &mut [u8],
) -> Result<usize, SerializeError> {
let nwrite = self.write_to_len();
if dst.len() < nwrite {
return Err(SerializeError::buffer_too_small(
"starting table ids",
));
}
dst = &mut dst[..nwrite];
// write start kind
let nw = self.kind.write_to::<E>(dst)?;
dst = &mut dst[nw..];
// write start byte map
let nw = self.start_map.write_to(dst)?;
dst = &mut dst[nw..];
// write stride
// Unwrap is OK since the stride is always 4 (currently).
E::write_u32(u32::try_from(self.stride).unwrap(), dst);
dst = &mut dst[size_of::<u32>()..];
// write pattern length
// Unwrap is OK since number of patterns is guaranteed to fit in a u32.
E::write_u32(
u32::try_from(self.pattern_len.unwrap_or(0xFFFF_FFFF)).unwrap(),
dst,
);
dst = &mut dst[size_of::<u32>()..];
// write universal start unanchored state id, u32::MAX if absent
E::write_u32(
self.universal_start_unanchored
.map_or(u32::MAX, |sid| sid.as_u32()),
dst,
);
dst = &mut dst[size_of::<u32>()..];
// write universal start anchored state id, u32::MAX if absent
E::write_u32(
self.universal_start_anchored.map_or(u32::MAX, |sid| sid.as_u32()),
dst,
);
dst = &mut dst[size_of::<u32>()..];
// write start IDs
for &sid in self.table() {
let n = wire::write_state_id::<E>(sid, &mut dst);
dst = &mut dst[n..];
}
Ok(nwrite)
}
/// Returns the number of bytes the serialized form of this start ID table
/// will use.
fn write_to_len(&self) -> usize {
self.kind.write_to_len()
+ self.start_map.write_to_len()
+ size_of::<u32>() // stride
+ size_of::<u32>() // # patterns
+ size_of::<u32>() // universal unanchored start
+ size_of::<u32>() // universal anchored start
+ (self.table().len() * StateID::SIZE)
}
/// Validates that every state ID in this start table is valid by checking
/// it against the given transition table (which must be for the same DFA).
///
/// That is, every state ID can be used to correctly index a state.
fn validate(
&self,
tt: &TransitionTable<T>,
) -> Result<(), DeserializeError> {
if !self.universal_start_unanchored.map_or(true, |s| tt.is_valid(s)) {
return Err(DeserializeError::generic(
"found invalid universal unanchored starting state ID",
));
}
if !self.universal_start_anchored.map_or(true, |s| tt.is_valid(s)) {
return Err(DeserializeError::generic(
"found invalid universal anchored starting state ID",
));
}
for &id in self.table() {
if !tt.is_valid(id) {
return Err(DeserializeError::generic(
"found invalid starting state ID",
));
}
}
Ok(())
}
/// Converts this start list to a borrowed value.
fn as_ref(&self) -> StartTable<&'_ [u32]> {
StartTable {
table: self.table.as_ref(),
kind: self.kind,
start_map: self.start_map.clone(),
stride: self.stride,
pattern_len: self.pattern_len,
universal_start_unanchored: self.universal_start_unanchored,
universal_start_anchored: self.universal_start_anchored,
}
}
/// Converts this start list to an owned value.
#[cfg(feature = "alloc")]
fn to_owned(&self) -> StartTable<alloc::vec::Vec<u32>> {
StartTable {
table: self.table.as_ref().to_vec(),
kind: self.kind,
start_map: self.start_map.clone(),
stride: self.stride,
pattern_len: self.pattern_len,
universal_start_unanchored: self.universal_start_unanchored,
universal_start_anchored: self.universal_start_anchored,
}
}
/// Return the start state for the given input and starting configuration.
/// This returns an error if the input configuration is not supported by
/// this DFA. For example, requesting an unanchored search when the DFA was
/// not built with unanchored starting states. Or asking for an anchored
/// pattern search with an invalid pattern ID or on a DFA that was not
/// built with start states for each pattern.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn start(
&self,
input: &Input<'_>,
start: Start,
) -> Result<StateID, MatchError> {
let start_index = start.as_usize();
let mode = input.get_anchored();
let index = match mode {
Anchored::No => {
if !self.kind.has_unanchored() {
return Err(MatchError::unsupported_anchored(mode));
}
start_index
}
Anchored::Yes => {
if !self.kind.has_anchored() {
return Err(MatchError::unsupported_anchored(mode));
}
self.stride + start_index
}
Anchored::Pattern(pid) => {
let len = match self.pattern_len {
None => {
return Err(MatchError::unsupported_anchored(mode))
}
Some(len) => len,
};
if pid.as_usize() >= len {
return Ok(DEAD);
}
(2 * self.stride)
+ (self.stride * pid.as_usize())
+ start_index
}
};
Ok(self.table()[index])
}
/// Returns an iterator over all start state IDs in this table.
///
/// Each item is a triple of: start state ID, the start state type and the
/// pattern ID (if any).
fn iter(&self) -> StartStateIter<'_> {
StartStateIter { st: self.as_ref(), i: 0 }
}
/// Returns the table as a slice of state IDs.
fn table(&self) -> &[StateID] {
wire::u32s_to_state_ids(self.table.as_ref())
}
/// Return the memory usage, in bytes, of this start list.
///
/// This does not include the size of a `StartList` value itself.
fn memory_usage(&self) -> usize {
self.table().len() * StateID::SIZE
}
}
#[cfg(feature = "dfa-build")]
impl<T: AsMut<[u32]>> StartTable<T> {
/// Set the start state for the given index and pattern.
///
/// If the pattern ID or state ID are not valid, then this will panic.
fn set_start(&mut self, anchored: Anchored, start: Start, id: StateID) {
let start_index = start.as_usize();
let index = match anchored {
Anchored::No => start_index,
Anchored::Yes => self.stride + start_index,
Anchored::Pattern(pid) => {
let pid = pid.as_usize();
let len = self
.pattern_len
.expect("start states for each pattern enabled");
assert!(pid < len, "invalid pattern ID {:?}", pid);
self.stride
.checked_mul(pid)
.unwrap()
.checked_add(self.stride.checked_mul(2).unwrap())
.unwrap()
.checked_add(start_index)
.unwrap()
}
};
self.table_mut()[index] = id;
}
/// Returns the table as a mutable slice of state IDs.
fn table_mut(&mut self) -> &mut [StateID] {
wire::u32s_to_state_ids_mut(self.table.as_mut())
}
}
/// An iterator over start state IDs.
///
/// This iterator yields a triple of start state ID, the anchored mode and the
/// start state type. If a pattern ID is relevant, then the anchored mode will
/// contain it. Start states with an anchored mode containing a pattern ID will
/// only occur when the DFA was compiled with start states for each pattern
/// (which is disabled by default).
pub(crate) struct StartStateIter<'a> {
st: StartTable<&'a [u32]>,
i: usize,
}
impl<'a> Iterator for StartStateIter<'a> {
type Item = (StateID, Anchored, Start);
fn next(&mut self) -> Option<(StateID, Anchored, Start)> {
let i = self.i;
let table = self.st.table();
if i >= table.len() {
return None;
}
self.i += 1;
// This unwrap is okay since the stride of the starting state table
// must always match the number of start state types.
let start_type = Start::from_usize(i % self.st.stride).unwrap();
let anchored = if i < self.st.stride {
Anchored::No
} else if i < (2 * self.st.stride) {
Anchored::Yes
} else {
let pid = (i - (2 * self.st.stride)) / self.st.stride;
Anchored::Pattern(PatternID::new(pid).unwrap())
};
Some((table[i], anchored, start_type))
}
}
/// This type represents that patterns that should be reported whenever a DFA
/// enters a match state. This structure exists to support DFAs that search for
/// matches for multiple regexes.
///
/// This structure relies on the fact that all match states in a DFA occur
/// contiguously in the DFA's transition table. (See dfa/special.rs for a more
/// detailed breakdown of the representation.) Namely, when a match occurs, we
/// know its state ID. Since we know the start and end of the contiguous region
/// of match states, we can use that to compute the position at which the match
/// state occurs. That in turn is used as an offset into this structure.
#[derive(Clone, Debug)]
struct MatchStates<T> {
/// Slices is a flattened sequence of pairs, where each pair points to a
/// sub-slice of pattern_ids. The first element of the pair is an offset
/// into pattern_ids and the second element of the pair is the number
/// of 32-bit pattern IDs starting at that position. That is, each pair
/// corresponds to a single DFA match state and its corresponding match
/// IDs. The number of pairs always corresponds to the number of distinct
/// DFA match states.
///
/// In practice, T is either Vec<u32> or &[u32].
slices: T,
/// A flattened sequence of pattern IDs for each DFA match state. The only
/// way to correctly read this sequence is indirectly via `slices`.
///
/// In practice, T is either Vec<u32> or &[u32].
pattern_ids: T,
/// The total number of unique patterns represented by these match states.
pattern_len: usize,
}
impl<'a> MatchStates<&'a [u32]> {
unsafe fn from_bytes_unchecked(
mut slice: &'a [u8],
) -> Result<(MatchStates<&'a [u32]>, usize), DeserializeError> {
let slice_start = slice.as_ptr().as_usize();
// Read the total number of match states.
let (state_len, nr) =
wire::try_read_u32_as_usize(slice, "match state length")?;
slice = &slice[nr..];
// Read the slice start/length pairs.
let pair_len = wire::mul(2, state_len, "match state offset pairs")?;
let slices_bytes_len = wire::mul(
pair_len,
PatternID::SIZE,
"match state slice offset byte length",
)?;
wire::check_slice_len(slice, slices_bytes_len, "match state slices")?;
wire::check_alignment::<PatternID>(slice)?;
let slices_bytes = &slice[..slices_bytes_len];
slice = &slice[slices_bytes_len..];
// SAFETY: Since PatternID is always representable as a u32, all we
// need to do is ensure that we have the proper length and alignment.
// We've checked both above, so the cast below is safe.
//
// N.B. This is one of the few not-safe snippets in this function,
// so we mark it explicitly to call it out.
let slices = core::slice::from_raw_parts(
slices_bytes.as_ptr().cast::<u32>(),
pair_len,
);
// Read the total number of unique pattern IDs (which is always 1 more
// than the maximum pattern ID in this automaton, since pattern IDs are
// handed out contiguously starting at 0).
let (pattern_len, nr) =
wire::try_read_u32_as_usize(slice, "pattern length")?;
slice = &slice[nr..];
// Now read the pattern ID length. We don't need to store this
// explicitly, but we need it to know how many pattern IDs to read.
let (idlen, nr) =
wire::try_read_u32_as_usize(slice, "pattern ID length")?;
slice = &slice[nr..];
// Read the actual pattern IDs.
let pattern_ids_len =
wire::mul(idlen, PatternID::SIZE, "pattern ID byte length")?;
wire::check_slice_len(slice, pattern_ids_len, "match pattern IDs")?;
wire::check_alignment::<PatternID>(slice)?;
let pattern_ids_bytes = &slice[..pattern_ids_len];
slice = &slice[pattern_ids_len..];
// SAFETY: Since PatternID is always representable as a u32, all we
// need to do is ensure that we have the proper length and alignment.
// We've checked both above, so the cast below is safe.
//
// N.B. This is one of the few not-safe snippets in this function,
// so we mark it explicitly to call it out.
let pattern_ids = core::slice::from_raw_parts(
pattern_ids_bytes.as_ptr().cast::<u32>(),
idlen,
);
let ms = MatchStates { slices, pattern_ids, pattern_len };
Ok((ms, slice.as_ptr().as_usize() - slice_start))
}
}
#[cfg(feature = "dfa-build")]
impl MatchStates<Vec<u32>> {
fn empty(pattern_len: usize) -> MatchStates<Vec<u32>> {
assert!(pattern_len <= PatternID::LIMIT);
MatchStates { slices: vec![], pattern_ids: vec![], pattern_len }
}
fn new(
matches: &BTreeMap<StateID, Vec<PatternID>>,
pattern_len: usize,
) -> Result<MatchStates<Vec<u32>>, BuildError> {
let mut m = MatchStates::empty(pattern_len);
for (_, pids) in matches.iter() {
let start = PatternID::new(m.pattern_ids.len())
.map_err(|_| BuildError::too_many_match_pattern_ids())?;
m.slices.push(start.as_u32());
// This is always correct since the number of patterns in a single
// match state can never exceed maximum number of allowable
// patterns. Why? Because a pattern can only appear once in a
// particular match state, by construction. (And since our pattern
// ID limit is one less than u32::MAX, we're guaranteed that the
// length fits in a u32.)
m.slices.push(u32::try_from(pids.len()).unwrap());
for &pid in pids {
m.pattern_ids.push(pid.as_u32());
}
}
m.pattern_len = pattern_len;
Ok(m)
}
fn new_with_map(
&self,
matches: &BTreeMap<StateID, Vec<PatternID>>,
) -> Result<MatchStates<Vec<u32>>, BuildError> {
MatchStates::new(matches, self.pattern_len)
}
}
impl<T: AsRef<[u32]>> MatchStates<T> {
/// Writes a serialized form of these match states to the buffer given. If
/// the buffer is too small, then an error is returned. To determine how
/// big the buffer must be, use `write_to_len`.
fn write_to<E: Endian>(
&self,
mut dst: &mut [u8],
) -> Result<usize, SerializeError> {
let nwrite = self.write_to_len();
if dst.len() < nwrite {
return Err(SerializeError::buffer_too_small("match states"));
}
dst = &mut dst[..nwrite];
// write state ID length
// Unwrap is OK since number of states is guaranteed to fit in a u32.
E::write_u32(u32::try_from(self.len()).unwrap(), dst);
dst = &mut dst[size_of::<u32>()..];
// write slice offset pairs
for &pid in self.slices() {
let n = wire::write_pattern_id::<E>(pid, &mut dst);
dst = &mut dst[n..];
}
// write unique pattern ID length
// Unwrap is OK since number of patterns is guaranteed to fit in a u32.
E::write_u32(u32::try_from(self.pattern_len).unwrap(), dst);
dst = &mut dst[size_of::<u32>()..];
// write pattern ID length
// Unwrap is OK since we check at construction (and deserialization)
// that the number of patterns is representable as a u32.
E::write_u32(u32::try_from(self.pattern_ids().len()).unwrap(), dst);
dst = &mut dst[size_of::<u32>()..];
// write pattern IDs
for &pid in self.pattern_ids() {
let n = wire::write_pattern_id::<E>(pid, &mut dst);
dst = &mut dst[n..];
}
Ok(nwrite)
}
/// Returns the number of bytes the serialized form of these match states
/// will use.
fn write_to_len(&self) -> usize {
size_of::<u32>() // match state length
+ (self.slices().len() * PatternID::SIZE)
+ size_of::<u32>() // unique pattern ID length
+ size_of::<u32>() // pattern ID length
+ (self.pattern_ids().len() * PatternID::SIZE)
}
/// Valides that the match state info is itself internally consistent and
/// consistent with the recorded match state region in the given DFA.
fn validate(&self, dfa: &DFA<T>) -> Result<(), DeserializeError> {
if self.len() != dfa.special.match_len(dfa.stride()) {
return Err(DeserializeError::generic(
"match state length mismatch",
));
}
for si in 0..self.len() {
let start = self.slices()[si * 2].as_usize();
let len = self.slices()[si * 2 + 1].as_usize();
if start >= self.pattern_ids().len() {
return Err(DeserializeError::generic(
"invalid pattern ID start offset",
));
}
if start + len > self.pattern_ids().len() {
return Err(DeserializeError::generic(
"invalid pattern ID length",
));
}
for mi in 0..len {
let pid = self.pattern_id(si, mi);
if pid.as_usize() >= self.pattern_len {
return Err(DeserializeError::generic(
"invalid pattern ID",
));
}
}
}
Ok(())
}
/// Converts these match states back into their map form. This is useful
/// when shuffling states, as the normal MatchStates representation is not
/// amenable to easy state swapping. But with this map, to swap id1 and
/// id2, all you need to do is:
///
/// if let Some(pids) = map.remove(&id1) {
/// map.insert(id2, pids);
/// }
///
/// Once shuffling is done, use MatchStates::new to convert back.
#[cfg(feature = "dfa-build")]
fn to_map(&self, dfa: &DFA<T>) -> BTreeMap<StateID, Vec<PatternID>> {
let mut map = BTreeMap::new();
for i in 0..self.len() {
let mut pids = vec![];
for j in 0..self.pattern_len(i) {
pids.push(self.pattern_id(i, j));
}
map.insert(self.match_state_id(dfa, i), pids);
}
map
}
/// Converts these match states to a borrowed value.
fn as_ref(&self) -> MatchStates<&'_ [u32]> {
MatchStates {
slices: self.slices.as_ref(),
pattern_ids: self.pattern_ids.as_ref(),
pattern_len: self.pattern_len,
}
}
/// Converts these match states to an owned value.
#[cfg(feature = "alloc")]
fn to_owned(&self) -> MatchStates<alloc::vec::Vec<u32>> {
MatchStates {
slices: self.slices.as_ref().to_vec(),
pattern_ids: self.pattern_ids.as_ref().to_vec(),
pattern_len: self.pattern_len,
}
}
/// Returns the match state ID given the match state index. (Where the
/// first match state corresponds to index 0.)
///
/// This panics if there is no match state at the given index.
fn match_state_id(&self, dfa: &DFA<T>, index: usize) -> StateID {
assert!(dfa.special.matches(), "no match states to index");
// This is one of the places where we rely on the fact that match
// states are contiguous in the transition table. Namely, that the
// first match state ID always corresponds to dfa.special.min_start.
// From there, since we know the stride, we can compute the ID of any
// match state given its index.
let stride2 = u32::try_from(dfa.stride2()).unwrap();
let offset = index.checked_shl(stride2).unwrap();
let id = dfa.special.min_match.as_usize().checked_add(offset).unwrap();
let sid = StateID::new(id).unwrap();
assert!(dfa.is_match_state(sid));
sid
}
/// Returns the pattern ID at the given match index for the given match
/// state.
///
/// The match state index is the state index minus the state index of the
/// first match state in the DFA.
///
/// The match index is the index of the pattern ID for the given state.
/// The index must be less than `self.pattern_len(state_index)`.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn pattern_id(&self, state_index: usize, match_index: usize) -> PatternID {
self.pattern_id_slice(state_index)[match_index]
}
/// Returns the number of patterns in the given match state.
///
/// The match state index is the state index minus the state index of the
/// first match state in the DFA.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn pattern_len(&self, state_index: usize) -> usize {
self.slices()[state_index * 2 + 1].as_usize()
}
/// Returns all of the pattern IDs for the given match state index.
///
/// The match state index is the state index minus the state index of the
/// first match state in the DFA.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn pattern_id_slice(&self, state_index: usize) -> &[PatternID] {
let start = self.slices()[state_index * 2].as_usize();
let len = self.pattern_len(state_index);
&self.pattern_ids()[start..start + len]
}
/// Returns the pattern ID offset slice of u32 as a slice of PatternID.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn slices(&self) -> &[PatternID] {
wire::u32s_to_pattern_ids(self.slices.as_ref())
}
/// Returns the total number of match states.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn len(&self) -> usize {
assert_eq!(0, self.slices().len() % 2);
self.slices().len() / 2
}
/// Returns the pattern ID slice of u32 as a slice of PatternID.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn pattern_ids(&self) -> &[PatternID] {
wire::u32s_to_pattern_ids(self.pattern_ids.as_ref())
}
/// Return the memory usage, in bytes, of these match pairs.
fn memory_usage(&self) -> usize {
(self.slices().len() + self.pattern_ids().len()) * PatternID::SIZE
}
}
/// A common set of flags for both dense and sparse DFAs. This primarily
/// centralizes the serialization format of these flags at a bitset.
#[derive(Clone, Copy, Debug)]
pub(crate) struct Flags {
/// Whether the DFA can match the empty string. When this is false, all
/// matches returned by this DFA are guaranteed to have non-zero length.
pub(crate) has_empty: bool,
/// Whether the DFA should only produce matches with spans that correspond
/// to valid UTF-8. This also includes omitting any zero-width matches that
/// split the UTF-8 encoding of a codepoint.
pub(crate) is_utf8: bool,
/// Whether the DFA is always anchored or not, regardless of `Input`
/// configuration. This is useful for avoiding a reverse scan even when
/// executing unanchored searches.
pub(crate) is_always_start_anchored: bool,
}
impl Flags {
/// Creates a set of flags for a DFA from an NFA.
///
/// N.B. This constructor was defined at the time of writing because all
/// of the flags are derived directly from the NFA. If this changes in the
/// future, we might be more thoughtful about how the `Flags` value is
/// itself built.
#[cfg(feature = "dfa-build")]
fn from_nfa(nfa: &thompson::NFA) -> Flags {
Flags {
has_empty: nfa.has_empty(),
is_utf8: nfa.is_utf8(),
is_always_start_anchored: nfa.is_always_start_anchored(),
}
}
/// Deserializes the flags from the given slice. On success, this also
/// returns the number of bytes read from the slice.
pub(crate) fn from_bytes(
slice: &[u8],
) -> Result<(Flags, usize), DeserializeError> {
let (bits, nread) = wire::try_read_u32(slice, "flag bitset")?;
let flags = Flags {
has_empty: bits & (1 << 0) != 0,
is_utf8: bits & (1 << 1) != 0,
is_always_start_anchored: bits & (1 << 2) != 0,
};
Ok((flags, nread))
}
/// Writes these flags to the given byte slice. If the buffer is too small,
/// then an error is returned. To determine how big the buffer must be,
/// use `write_to_len`.
pub(crate) fn write_to<E: Endian>(
&self,
dst: &mut [u8],
) -> Result<usize, SerializeError> {
fn bool_to_int(b: bool) -> u32 {
if b {
1
} else {
0
}
}
let nwrite = self.write_to_len();
if dst.len() < nwrite {
return Err(SerializeError::buffer_too_small("flag bitset"));
}
let bits = (bool_to_int(self.has_empty) << 0)
| (bool_to_int(self.is_utf8) << 1)
| (bool_to_int(self.is_always_start_anchored) << 2);
E::write_u32(bits, dst);
Ok(nwrite)
}
/// Returns the number of bytes the serialized form of these flags
/// will use.
pub(crate) fn write_to_len(&self) -> usize {
size_of::<u32>()
}
}
/// An iterator over all states in a DFA.
///
/// This iterator yields a tuple for each state. The first element of the
/// tuple corresponds to a state's identifier, and the second element
/// corresponds to the state itself (comprised of its transitions).
///
/// `'a` corresponding to the lifetime of original DFA, `T` corresponds to
/// the type of the transition table itself.
pub(crate) struct StateIter<'a, T> {
tt: &'a TransitionTable<T>,
it: iter::Enumerate<slice::Chunks<'a, StateID>>,
}
impl<'a, T: AsRef<[u32]>> Iterator for StateIter<'a, T> {
type Item = State<'a>;
fn next(&mut self) -> Option<State<'a>> {
self.it.next().map(|(index, _)| {
let id = self.tt.to_state_id(index);
self.tt.state(id)
})
}
}
/// An immutable representation of a single DFA state.
///
/// `'a` correspondings to the lifetime of a DFA's transition table.
pub(crate) struct State<'a> {
id: StateID,
stride2: usize,
transitions: &'a [StateID],
}
impl<'a> State<'a> {
/// Return an iterator over all transitions in this state. This yields
/// a number of transitions equivalent to the alphabet length of the
/// corresponding DFA.
///
/// Each transition is represented by a tuple. The first element is
/// the input byte for that transition and the second element is the
/// transitions itself.
pub(crate) fn transitions(&self) -> StateTransitionIter<'_> {
StateTransitionIter {
len: self.transitions.len(),
it: self.transitions.iter().enumerate(),
}
}
/// Return an iterator over a sparse representation of the transitions in
/// this state. Only non-dead transitions are returned.
///
/// The "sparse" representation in this case corresponds to a sequence of
/// triples. The first two elements of the triple comprise an inclusive
/// byte range while the last element corresponds to the transition taken
/// for all bytes in the range.
///
/// This is somewhat more condensed than the classical sparse
/// representation (where you have an element for every non-dead
/// transition), but in practice, checking if a byte is in a range is very
/// cheap and using ranges tends to conserve quite a bit more space.
pub(crate) fn sparse_transitions(&self) -> StateSparseTransitionIter<'_> {
StateSparseTransitionIter { dense: self.transitions(), cur: None }
}
/// Returns the identifier for this state.
pub(crate) fn id(&self) -> StateID {
self.id
}
/// Analyzes this state to determine whether it can be accelerated. If so,
/// it returns an accelerator that contains at least one byte.
#[cfg(feature = "dfa-build")]
fn accelerate(&self, classes: &ByteClasses) -> Option<Accel> {
// We just try to add bytes to our accelerator. Once adding fails
// (because we've added too many bytes), then give up.
let mut accel = Accel::new();
for (class, id) in self.transitions() {
if id == self.id() {
continue;
}
for unit in classes.elements(class) {
if let Some(byte) = unit.as_u8() {
if !accel.add(byte) {
return None;
}
}
}
}
if accel.is_empty() {
None
} else {
Some(accel)
}
}
}
impl<'a> fmt::Debug for State<'a> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
for (i, (start, end, sid)) in self.sparse_transitions().enumerate() {
let id = if f.alternate() {
sid.as_usize()
} else {
sid.as_usize() >> self.stride2
};
if i > 0 {
write!(f, ", ")?;
}
if start == end {
write!(f, "{:?} => {:?}", start, id)?;
} else {
write!(f, "{:?}-{:?} => {:?}", start, end, id)?;
}
}
Ok(())
}
}
/// An iterator over all transitions in a single DFA state. This yields
/// a number of transitions equivalent to the alphabet length of the
/// corresponding DFA.
///
/// Each transition is represented by a tuple. The first element is the input
/// byte for that transition and the second element is the transition itself.
#[derive(Debug)]
pub(crate) struct StateTransitionIter<'a> {
len: usize,
it: iter::Enumerate<slice::Iter<'a, StateID>>,
}
impl<'a> Iterator for StateTransitionIter<'a> {
type Item = (alphabet::Unit, StateID);
fn next(&mut self) -> Option<(alphabet::Unit, StateID)> {
self.it.next().map(|(i, &id)| {
let unit = if i + 1 == self.len {
alphabet::Unit::eoi(i)
} else {
let b = u8::try_from(i)
.expect("raw byte alphabet is never exceeded");
alphabet::Unit::u8(b)
};
(unit, id)
})
}
}
/// An iterator over all non-DEAD transitions in a single DFA state using a
/// sparse representation.
///
/// Each transition is represented by a triple. The first two elements of the
/// triple comprise an inclusive byte range while the last element corresponds
/// to the transition taken for all bytes in the range.
///
/// As a convenience, this always returns `alphabet::Unit` values of the same
/// type. That is, you'll never get a (byte, EOI) or a (EOI, byte). Only (byte,
/// byte) and (EOI, EOI) values are yielded.
#[derive(Debug)]
pub(crate) struct StateSparseTransitionIter<'a> {
dense: StateTransitionIter<'a>,
cur: Option<(alphabet::Unit, alphabet::Unit, StateID)>,
}
impl<'a> Iterator for StateSparseTransitionIter<'a> {
type Item = (alphabet::Unit, alphabet::Unit, StateID);
fn next(&mut self) -> Option<(alphabet::Unit, alphabet::Unit, StateID)> {
while let Some((unit, next)) = self.dense.next() {
let (prev_start, prev_end, prev_next) = match self.cur {
Some(t) => t,
None => {
self.cur = Some((unit, unit, next));
continue;
}
};
if prev_next == next && !unit.is_eoi() {
self.cur = Some((prev_start, unit, prev_next));
} else {
self.cur = Some((unit, unit, next));
if prev_next != DEAD {
return Some((prev_start, prev_end, prev_next));
}
}
}
if let Some((start, end, next)) = self.cur.take() {
if next != DEAD {
return Some((start, end, next));
}
}
None
}
}
/// An error that occurred during the construction of a DFA.
///
/// This error does not provide many introspection capabilities. There are
/// generally only two things you can do with it:
///
/// * Obtain a human readable message via its `std::fmt::Display` impl.
/// * Access an underlying [`nfa::thompson::BuildError`](thompson::BuildError)
/// type from its `source` method via the `std::error::Error` trait. This error
/// only occurs when using convenience routines for building a DFA directly
/// from a pattern string.
///
/// When the `std` feature is enabled, this implements the `std::error::Error`
/// trait.
#[cfg(feature = "dfa-build")]
#[derive(Clone, Debug)]
pub struct BuildError {
kind: BuildErrorKind,
}
/// The kind of error that occurred during the construction of a DFA.
///
/// Note that this error is non-exhaustive. Adding new variants is not
/// considered a breaking change.
#[cfg(feature = "dfa-build")]
#[derive(Clone, Debug)]
enum BuildErrorKind {
/// An error that occurred while constructing an NFA as a precursor step
/// before a DFA is compiled.
NFA(thompson::BuildError),
/// An error that occurred because an unsupported regex feature was used.
/// The message string describes which unsupported feature was used.
///
/// The primary regex feature that is unsupported by DFAs is the Unicode
/// word boundary look-around assertion (`\b`). This can be worked around
/// by either using an ASCII word boundary (`(?-u:\b)`) or by enabling
/// Unicode word boundaries when building a DFA.
Unsupported(&'static str),
/// An error that occurs if too many states are produced while building a
/// DFA.
TooManyStates,
/// An error that occurs if too many start states are needed while building
/// a DFA.
///
/// This is a kind of oddball error that occurs when building a DFA with
/// start states enabled for each pattern and enough patterns to cause
/// the table of start states to overflow `usize`.
TooManyStartStates,
/// This is another oddball error that can occur if there are too many
/// patterns spread out across too many match states.
TooManyMatchPatternIDs,
/// An error that occurs if the DFA got too big during determinization.
DFAExceededSizeLimit { limit: usize },
/// An error that occurs if auxiliary storage (not the DFA) used during
/// determinization got too big.
DeterminizeExceededSizeLimit { limit: usize },
}
#[cfg(feature = "dfa-build")]
impl BuildError {
/// Return the kind of this error.
fn kind(&self) -> &BuildErrorKind {
&self.kind
}
pub(crate) fn nfa(err: thompson::BuildError) -> BuildError {
BuildError { kind: BuildErrorKind::NFA(err) }
}
pub(crate) fn unsupported_dfa_word_boundary_unicode() -> BuildError {
let msg = "cannot build DFAs for regexes with Unicode word \
boundaries; switch to ASCII word boundaries, or \
heuristically enable Unicode word boundaries or use a \
different regex engine";
BuildError { kind: BuildErrorKind::Unsupported(msg) }
}
pub(crate) fn too_many_states() -> BuildError {
BuildError { kind: BuildErrorKind::TooManyStates }
}
pub(crate) fn too_many_start_states() -> BuildError {
BuildError { kind: BuildErrorKind::TooManyStartStates }
}
pub(crate) fn too_many_match_pattern_ids() -> BuildError {
BuildError { kind: BuildErrorKind::TooManyMatchPatternIDs }
}
pub(crate) fn dfa_exceeded_size_limit(limit: usize) -> BuildError {
BuildError { kind: BuildErrorKind::DFAExceededSizeLimit { limit } }
}
pub(crate) fn determinize_exceeded_size_limit(limit: usize) -> BuildError {
BuildError {
kind: BuildErrorKind::DeterminizeExceededSizeLimit { limit },
}
}
}
#[cfg(all(feature = "std", feature = "dfa-build"))]
impl std::error::Error for BuildError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self.kind() {
BuildErrorKind::NFA(ref err) => Some(err),
_ => None,
}
}
}
#[cfg(feature = "dfa-build")]
impl core::fmt::Display for BuildError {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self.kind() {
BuildErrorKind::NFA(_) => write!(f, "error building NFA"),
BuildErrorKind::Unsupported(ref msg) => {
write!(f, "unsupported regex feature for DFAs: {}", msg)
}
BuildErrorKind::TooManyStates => write!(
f,
"number of DFA states exceeds limit of {}",
StateID::LIMIT,
),
BuildErrorKind::TooManyStartStates => {
let stride = Start::len();
// The start table has `stride` entries for starting states for
// the entire DFA, and then `stride` entries for each pattern
// if start states for each pattern are enabled (which is the
// only way this error can occur). Thus, the total number of
// patterns that can fit in the table is `stride` less than
// what we can allocate.
let max = usize::try_from(core::isize::MAX).unwrap();
let limit = (max - stride) / stride;
write!(
f,
"compiling DFA with start states exceeds pattern \
pattern limit of {}",
limit,
)
}
BuildErrorKind::TooManyMatchPatternIDs => write!(
f,
"compiling DFA with total patterns in all match states \
exceeds limit of {}",
PatternID::LIMIT,
),
BuildErrorKind::DFAExceededSizeLimit { limit } => write!(
f,
"DFA exceeded size limit of {:?} during determinization",
limit,
),
BuildErrorKind::DeterminizeExceededSizeLimit { limit } => {
write!(f, "determinization exceeded size limit of {:?}", limit)
}
}
}
}
#[cfg(all(test, feature = "syntax", feature = "dfa-build"))]
mod tests {
use super::*;
#[test]
fn errors_with_unicode_word_boundary() {
let pattern = r"\b";
assert!(Builder::new().build(pattern).is_err());
}
#[test]
fn roundtrip_never_match() {
let dfa = DFA::never_match().unwrap();
let (buf, _) = dfa.to_bytes_native_endian();
let dfa: DFA<&[u32]> = DFA::from_bytes(&buf).unwrap().0;
assert_eq!(None, dfa.try_search_fwd(&Input::new("foo12345")).unwrap());
}
#[test]
fn roundtrip_always_match() {
use crate::HalfMatch;
let dfa = DFA::always_match().unwrap();
let (buf, _) = dfa.to_bytes_native_endian();
let dfa: DFA<&[u32]> = DFA::from_bytes(&buf).unwrap().0;
assert_eq!(
Some(HalfMatch::must(0, 0)),
dfa.try_search_fwd(&Input::new("foo12345")).unwrap()
);
}
// See the analogous test in src/hybrid/dfa.rs.
#[test]
fn heuristic_unicode_reverse() {
let dfa = DFA::builder()
.configure(DFA::config().unicode_word_boundary(true))
.thompson(thompson::Config::new().reverse(true))
.build(r"\b[0-9]+\b")
.unwrap();
let input = Input::new("β123").range(2..);
let expected = MatchError::quit(0xB2, 1);
let got = dfa.try_search_rev(&input);
assert_eq!(Err(expected), got);
let input = Input::new("123β").range(..3);
let expected = MatchError::quit(0xCE, 3);
let got = dfa.try_search_rev(&input);
assert_eq!(Err(expected), got);
}
}