Initial import of regex-automata-0.1.9.
Bug: 155309706
Change-Id: I20031167cbe49d12754936285a0781eb7a3b8bfd
diff --git a/src/dense.rs b/src/dense.rs
new file mode 100644
index 0000000..ed4d1b6
--- /dev/null
+++ b/src/dense.rs
@@ -0,0 +1,2332 @@
+#[cfg(feature = "std")]
+use core::fmt;
+#[cfg(feature = "std")]
+use core::iter;
+use core::mem;
+use core::slice;
+
+#[cfg(feature = "std")]
+use byteorder::{BigEndian, LittleEndian};
+use byteorder::{ByteOrder, NativeEndian};
+#[cfg(feature = "std")]
+use regex_syntax::ParserBuilder;
+
+use classes::ByteClasses;
+#[cfg(feature = "std")]
+use determinize::Determinizer;
+use dfa::DFA;
+#[cfg(feature = "std")]
+use error::{Error, Result};
+#[cfg(feature = "std")]
+use minimize::Minimizer;
+#[cfg(feature = "std")]
+use nfa::{self, NFA};
+#[cfg(feature = "std")]
+use sparse::SparseDFA;
+use state_id::{dead_id, StateID};
+#[cfg(feature = "std")]
+use state_id::{
+ next_state_id, premultiply_overflow_error, write_state_id_bytes,
+};
+
+/// The size of the alphabet in a standard DFA.
+///
+/// Specifically, this length controls the number of transitions present in
+/// each DFA state. However, when the byte class optimization is enabled,
+/// then each DFA maps the space of all possible 256 byte values to at most
+/// 256 distinct equivalence classes. In this case, the number of distinct
+/// equivalence classes corresponds to the internal alphabet of the DFA, in the
+/// sense that each DFA state has a number of transitions equal to the number
+/// of equivalence classes despite supporting matching on all possible byte
+/// values.
+const ALPHABET_LEN: usize = 256;
+
+/// Masks used in serialization of DFAs.
+pub(crate) const MASK_PREMULTIPLIED: u16 = 0b0000_0000_0000_0001;
+pub(crate) const MASK_ANCHORED: u16 = 0b0000_0000_0000_0010;
+
+/// A dense table-based deterministic finite automaton (DFA).
+///
+/// A dense DFA represents the core matching primitive in this crate. That is,
+/// logically, all DFAs have a single start state, one 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 regex may take significant time *and* space. 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](enum.SparseDFA.html) 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.
+///
+/// A DFA can be built using the default configuration via the
+/// [`DenseDFA::new`](enum.DenseDFA.html#method.new) constructor. Otherwise,
+/// one can configure various aspects via the
+/// [`dense::Builder`](dense/struct.Builder.html).
+///
+/// A single DFA fundamentally supports the following operations:
+///
+/// 1. Detection of a match.
+/// 2. Location of the end of the first possible match.
+/// 3. Location of the end of the leftmost-first match.
+///
+/// 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`](struct.Regex.html), which can be built with its basic
+/// constructor, [`Regex::new`](struct.Regex.html#method.new), or with
+/// a [`RegexBuilder`](struct.RegexBuilder.html).
+///
+/// # State size
+///
+/// A `DenseDFA` has two type parameters, `T` and `S`. `T` corresponds to
+/// the type of the DFA's transition table while `S` corresponds to the
+/// representation used for the DFA's state identifiers as described by the
+/// [`StateID`](trait.StateID.html) trait. This type parameter is typically
+/// `usize`, but other valid choices provided by this crate include `u8`,
+/// `u16`, `u32` and `u64`. The primary reason for choosing a different state
+/// identifier representation than the default is to reduce the amount of
+/// memory used by a DFA. Note though, that if the chosen representation cannot
+/// accommodate the size of your DFA, then building the DFA will fail and
+/// return an error.
+///
+/// While the reduction in heap memory used by a DFA is one reason for choosing
+/// a smaller state identifier representation, another possible reason is for
+/// decreasing the serialization size of a DFA, as returned by
+/// [`to_bytes_little_endian`](enum.DenseDFA.html#method.to_bytes_little_endian),
+/// [`to_bytes_big_endian`](enum.DenseDFA.html#method.to_bytes_big_endian)
+/// or
+/// [`to_bytes_native_endian`](enum.DenseDFA.html#method.to_bytes_native_endian).
+///
+/// The type of the transition table is typically either `Vec<S>` or `&[S]`,
+/// depending on where the transition table is stored.
+///
+/// # Variants
+///
+/// This DFA is defined as a non-exhaustive enumeration of different types of
+/// dense DFAs. All of these dense DFAs use the same internal representation
+/// for the transition table, but they vary in how the transition table is
+/// read. A DFA's specific variant depends on the configuration options set via
+/// [`dense::Builder`](dense/struct.Builder.html). The default variant is
+/// `PremultipliedByteClass`.
+///
+/// # The `DFA` trait
+///
+/// This type implements the [`DFA`](trait.DFA.html) trait, which means it
+/// can be used for searching. For example:
+///
+/// ```
+/// use regex_automata::{DFA, DenseDFA};
+///
+/// # fn example() -> Result<(), regex_automata::Error> {
+/// let dfa = DenseDFA::new("foo[0-9]+")?;
+/// assert_eq!(Some(8), dfa.find(b"foo12345"));
+/// # Ok(()) }; example().unwrap()
+/// ```
+///
+/// The `DFA` trait also provides an assortment of other lower level methods
+/// for DFAs, such as `start_state` and `next_state`. While these are correctly
+/// implemented, it is an anti-pattern to use them in performance sensitive
+/// code on the `DenseDFA` type directly. Namely, each implementation requires
+/// a branch to determine which type of dense DFA is being used. Instead,
+/// this branch should be pushed up a layer in the code since walking the
+/// transitions of a DFA is usually a hot path. If you do need to use these
+/// lower level methods in performance critical code, then you should match on
+/// the variants of this DFA and use each variant's implementation of the `DFA`
+/// trait directly.
+#[derive(Clone, Debug)]
+pub enum DenseDFA<T: AsRef<[S]>, S: StateID> {
+ /// A standard DFA that does not use premultiplication or byte classes.
+ Standard(Standard<T, S>),
+ /// A DFA that shrinks its alphabet to a set of equivalence classes instead
+ /// of using all possible byte values. Any two bytes belong to the same
+ /// equivalence class if and only if they can be used interchangeably
+ /// anywhere in the DFA while never discriminating between a match and a
+ /// non-match.
+ ///
+ /// This type of DFA can result in significant space reduction with a very
+ /// small match time performance penalty.
+ ByteClass(ByteClass<T, S>),
+ /// A DFA that premultiplies all of its state identifiers in its
+ /// transition table. This saves an instruction per byte at match time
+ /// which improves search performance.
+ ///
+ /// The only downside of premultiplication is that it may prevent one from
+ /// using a smaller state identifier representation than you otherwise
+ /// could.
+ Premultiplied(Premultiplied<T, S>),
+ /// The default configuration of a DFA, which uses byte classes and
+ /// premultiplies its state identifiers.
+ PremultipliedByteClass(PremultipliedByteClass<T, S>),
+ /// Hints that destructuring should not be exhaustive.
+ ///
+ /// This enum may grow additional variants, so this makes sure clients
+ /// don't count on exhaustive matching. (Otherwise, adding a new variant
+ /// could break existing code.)
+ #[doc(hidden)]
+ __Nonexhaustive,
+}
+
+impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
+ /// Return the internal DFA representation.
+ ///
+ /// All variants share the same internal representation.
+ fn repr(&self) -> &Repr<T, S> {
+ match *self {
+ DenseDFA::Standard(ref r) => &r.0,
+ DenseDFA::ByteClass(ref r) => &r.0,
+ DenseDFA::Premultiplied(ref r) => &r.0,
+ DenseDFA::PremultipliedByteClass(ref r) => &r.0,
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+}
+
+#[cfg(feature = "std")]
+impl DenseDFA<Vec<usize>, usize> {
+ /// Parse the given regular expression using a default configuration and
+ /// return the corresponding DFA.
+ ///
+ /// The default configuration uses `usize` for state IDs, premultiplies
+ /// them and reduces the alphabet size by splitting bytes into equivalence
+ /// classes. The DFA is *not* minimized.
+ ///
+ /// If you want a non-default configuration, then use the
+ /// [`dense::Builder`](dense/struct.Builder.html)
+ /// to set your own configuration.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use regex_automata::{DFA, DenseDFA};
+ ///
+ /// # fn example() -> Result<(), regex_automata::Error> {
+ /// let dfa = DenseDFA::new("foo[0-9]+bar")?;
+ /// assert_eq!(Some(11), dfa.find(b"foo12345bar"));
+ /// # Ok(()) }; example().unwrap()
+ /// ```
+ pub fn new(pattern: &str) -> Result<DenseDFA<Vec<usize>, usize>> {
+ Builder::new().build(pattern)
+ }
+}
+
+#[cfg(feature = "std")]
+impl<S: StateID> DenseDFA<Vec<S>, S> {
+ /// Create a new empty DFA that never matches any input.
+ ///
+ /// # Example
+ ///
+ /// In order to build an empty DFA, callers must provide a type hint
+ /// indicating their choice of state identifier representation.
+ ///
+ /// ```
+ /// use regex_automata::{DFA, DenseDFA};
+ ///
+ /// # fn example() -> Result<(), regex_automata::Error> {
+ /// let dfa: DenseDFA<Vec<usize>, usize> = DenseDFA::empty();
+ /// assert_eq!(None, dfa.find(b""));
+ /// assert_eq!(None, dfa.find(b"foo"));
+ /// # Ok(()) }; example().unwrap()
+ /// ```
+ pub fn empty() -> DenseDFA<Vec<S>, S> {
+ Repr::empty().into_dense_dfa()
+ }
+}
+
+impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
+ /// Cheaply return a borrowed version of this dense DFA. Specifically, the
+ /// DFA returned always uses `&[S]` for its transition table while keeping
+ /// the same state identifier representation.
+ pub fn as_ref<'a>(&'a self) -> DenseDFA<&'a [S], S> {
+ match *self {
+ DenseDFA::Standard(ref r) => {
+ DenseDFA::Standard(Standard(r.0.as_ref()))
+ }
+ DenseDFA::ByteClass(ref r) => {
+ DenseDFA::ByteClass(ByteClass(r.0.as_ref()))
+ }
+ DenseDFA::Premultiplied(ref r) => {
+ DenseDFA::Premultiplied(Premultiplied(r.0.as_ref()))
+ }
+ DenseDFA::PremultipliedByteClass(ref r) => {
+ let inner = PremultipliedByteClass(r.0.as_ref());
+ DenseDFA::PremultipliedByteClass(inner)
+ }
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+
+ /// Return an owned version of this sparse DFA. Specifically, the DFA
+ /// returned always uses `Vec<u8>` for its transition table while keeping
+ /// the same state identifier representation.
+ ///
+ /// Effectively, this returns a sparse DFA whose transition table lives
+ /// on the heap.
+ #[cfg(feature = "std")]
+ pub fn to_owned(&self) -> DenseDFA<Vec<S>, S> {
+ match *self {
+ DenseDFA::Standard(ref r) => {
+ DenseDFA::Standard(Standard(r.0.to_owned()))
+ }
+ DenseDFA::ByteClass(ref r) => {
+ DenseDFA::ByteClass(ByteClass(r.0.to_owned()))
+ }
+ DenseDFA::Premultiplied(ref r) => {
+ DenseDFA::Premultiplied(Premultiplied(r.0.to_owned()))
+ }
+ DenseDFA::PremultipliedByteClass(ref r) => {
+ let inner = PremultipliedByteClass(r.0.to_owned());
+ DenseDFA::PremultipliedByteClass(inner)
+ }
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+
+ /// 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's transition table. This corresponds to heap memory
+ /// usage.
+ ///
+ /// This does **not** include the stack size used up by this DFA. To
+ /// compute that, used `std::mem::size_of::<DenseDFA>()`.
+ pub fn memory_usage(&self) -> usize {
+ self.repr().memory_usage()
+ }
+}
+
+/// Routines for converting a dense DFA to other representations, such as
+/// sparse DFAs, smaller state identifiers or raw bytes suitable for persistent
+/// storage.
+#[cfg(feature = "std")]
+impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
+ /// Convert this dense DFA to a sparse DFA.
+ ///
+ /// This is a convenience routine for `to_sparse_sized` that fixes the
+ /// state identifier representation of the sparse DFA to the same
+ /// representation used for this dense DFA.
+ ///
+ /// If the chosen state identifier representation 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 `S` then a sparse DFA will
+ /// be as well. However, it is not guaranteed.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use regex_automata::{DFA, DenseDFA};
+ ///
+ /// # fn example() -> Result<(), regex_automata::Error> {
+ /// let dense = DenseDFA::new("foo[0-9]+")?;
+ /// let sparse = dense.to_sparse()?;
+ /// assert_eq!(Some(8), sparse.find(b"foo12345"));
+ /// # Ok(()) }; example().unwrap()
+ /// ```
+ pub fn to_sparse(&self) -> Result<SparseDFA<Vec<u8>, S>> {
+ self.to_sparse_sized()
+ }
+
+ /// Convert this dense DFA to a sparse DFA.
+ ///
+ /// Using this routine requires supplying a type hint to choose the state
+ /// identifier representation for the resulting sparse DFA.
+ ///
+ /// If the chosen state identifier representation is too small to represent
+ /// all states in the sparse DFA, then this returns an error.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use regex_automata::{DFA, DenseDFA};
+ ///
+ /// # fn example() -> Result<(), regex_automata::Error> {
+ /// let dense = DenseDFA::new("foo[0-9]+")?;
+ /// let sparse = dense.to_sparse_sized::<u8>()?;
+ /// assert_eq!(Some(8), sparse.find(b"foo12345"));
+ /// # Ok(()) }; example().unwrap()
+ /// ```
+ pub fn to_sparse_sized<A: StateID>(
+ &self,
+ ) -> Result<SparseDFA<Vec<u8>, A>> {
+ self.repr().to_sparse_sized()
+ }
+
+ /// Create a new DFA whose match semantics are equivalent to this DFA,
+ /// but attempt to use `u8` for the representation of state identifiers.
+ /// If `u8` is insufficient to represent all state identifiers in this
+ /// DFA, then this returns an error.
+ ///
+ /// This is a convenience routine for `to_sized::<u8>()`.
+ pub fn to_u8(&self) -> Result<DenseDFA<Vec<u8>, u8>> {
+ self.to_sized()
+ }
+
+ /// Create a new DFA whose match semantics are equivalent to this DFA,
+ /// but attempt to use `u16` for the representation of state identifiers.
+ /// If `u16` is insufficient to represent all state identifiers in this
+ /// DFA, then this returns an error.
+ ///
+ /// This is a convenience routine for `to_sized::<u16>()`.
+ pub fn to_u16(&self) -> Result<DenseDFA<Vec<u16>, u16>> {
+ self.to_sized()
+ }
+
+ /// Create a new DFA whose match semantics are equivalent to this DFA,
+ /// but attempt to use `u32` for the representation of state identifiers.
+ /// If `u32` is insufficient to represent all state identifiers in this
+ /// DFA, then this returns an error.
+ ///
+ /// This is a convenience routine for `to_sized::<u32>()`.
+ #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
+ pub fn to_u32(&self) -> Result<DenseDFA<Vec<u32>, u32>> {
+ self.to_sized()
+ }
+
+ /// Create a new DFA whose match semantics are equivalent to this DFA,
+ /// but attempt to use `u64` for the representation of state identifiers.
+ /// If `u64` is insufficient to represent all state identifiers in this
+ /// DFA, then this returns an error.
+ ///
+ /// This is a convenience routine for `to_sized::<u64>()`.
+ #[cfg(target_pointer_width = "64")]
+ pub fn to_u64(&self) -> Result<DenseDFA<Vec<u64>, u64>> {
+ self.to_sized()
+ }
+
+ /// Create a new DFA whose match semantics are equivalent to this DFA, but
+ /// attempt to use `A` for the representation of state identifiers. If `A`
+ /// is insufficient to represent all state identifiers in this DFA, then
+ /// this returns an error.
+ ///
+ /// An alternative way to construct such a DFA is to use
+ /// [`dense::Builder::build_with_size`](dense/struct.Builder.html#method.build_with_size).
+ /// In general, using the builder is preferred since it will use the given
+ /// state identifier representation throughout determinization (and
+ /// minimization, if done), and thereby using less memory throughout the
+ /// entire construction process. However, these routines are necessary
+ /// in cases where, say, a minimized DFA could fit in a smaller state
+ /// identifier representation, but the initial determinized DFA would not.
+ pub fn to_sized<A: StateID>(&self) -> Result<DenseDFA<Vec<A>, A>> {
+ self.repr().to_sized().map(|r| r.into_dense_dfa())
+ }
+
+ /// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in little
+ /// endian format.
+ ///
+ /// If the state identifier representation of this DFA has a size different
+ /// than 1, 2, 4 or 8 bytes, then this returns an error. All
+ /// implementations of `StateID` provided by this crate satisfy this
+ /// requirement.
+ pub fn to_bytes_little_endian(&self) -> Result<Vec<u8>> {
+ self.repr().to_bytes::<LittleEndian>()
+ }
+
+ /// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in big
+ /// endian format.
+ ///
+ /// If the state identifier representation of this DFA has a size different
+ /// than 1, 2, 4 or 8 bytes, then this returns an error. All
+ /// implementations of `StateID` provided by this crate satisfy this
+ /// requirement.
+ pub fn to_bytes_big_endian(&self) -> Result<Vec<u8>> {
+ self.repr().to_bytes::<BigEndian>()
+ }
+
+ /// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in native
+ /// endian format. Generally, it is better to pick an explicit endianness
+ /// using either `to_bytes_little_endian` or `to_bytes_big_endian`. This
+ /// routine is useful in tests where the DFA is serialized and deserialized
+ /// on the same platform.
+ ///
+ /// If the state identifier representation of this DFA has a size different
+ /// than 1, 2, 4 or 8 bytes, then this returns an error. All
+ /// implementations of `StateID` provided by this crate satisfy this
+ /// requirement.
+ pub fn to_bytes_native_endian(&self) -> Result<Vec<u8>> {
+ self.repr().to_bytes::<NativeEndian>()
+ }
+}
+
+impl<'a, S: StateID> DenseDFA<&'a [S], S> {
+ /// Deserialize a DFA with a specific state identifier representation.
+ ///
+ /// Deserializing a DFA using this routine will never allocate heap memory.
+ /// This is also guaranteed to be a constant time operation that does not
+ /// vary with the size of the DFA.
+ ///
+ /// The bytes given should be generated by the serialization of a DFA with
+ /// either the
+ /// [`to_bytes_little_endian`](enum.DenseDFA.html#method.to_bytes_little_endian)
+ /// method or the
+ /// [`to_bytes_big_endian`](enum.DenseDFA.html#method.to_bytes_big_endian)
+ /// endian, depending on the endianness of the machine you are
+ /// deserializing this DFA from.
+ ///
+ /// If the state identifier representation is `usize`, then deserialization
+ /// is dependent on the pointer size. For this reason, it is best to
+ /// serialize DFAs using a fixed size representation for your state
+ /// identifiers, such as `u8`, `u16`, `u32` or `u64`.
+ ///
+ /// # Panics
+ ///
+ /// The bytes given should be *trusted*. In particular, if the bytes
+ /// are not a valid serialization of a DFA, or if the given bytes are
+ /// not aligned to an 8 byte boundary, or if the endianness of the
+ /// serialized bytes is different than the endianness of the machine that
+ /// is deserializing the DFA, then this routine will panic. Moreover, it is
+ /// possible for this deserialization routine to succeed even if the given
+ /// bytes do not represent a valid serialized dense DFA.
+ ///
+ /// # Safety
+ ///
+ /// This routine is unsafe because it permits callers to provide an
+ /// arbitrary transition table with possibly incorrect transitions. While
+ /// the various serialization routines will never return an incorrect
+ /// transition table, there is no guarantee that the bytes provided here
+ /// are correct. While deserialization does many checks (as documented
+ /// above in the panic conditions), this routine does not check that the
+ /// transition table is correct. Given an incorrect transition table, it is
+ /// possible for the search routines to access out-of-bounds memory because
+ /// of explicit bounds check elision.
+ ///
+ /// # Example
+ ///
+ /// This example shows how to serialize a DFA to raw bytes, deserialize it
+ /// and then use it for searching. Note that we first convert the DFA to
+ /// using `u16` for its state identifier representation before serializing
+ /// it. While this isn't strictly necessary, it's good practice in order to
+ /// decrease the size of the DFA and to avoid platform specific pitfalls
+ /// such as differing pointer sizes.
+ ///
+ /// ```
+ /// use regex_automata::{DFA, DenseDFA};
+ ///
+ /// # fn example() -> Result<(), regex_automata::Error> {
+ /// let initial = DenseDFA::new("foo[0-9]+")?;
+ /// let bytes = initial.to_u16()?.to_bytes_native_endian()?;
+ /// let dfa: DenseDFA<&[u16], u16> = unsafe {
+ /// DenseDFA::from_bytes(&bytes)
+ /// };
+ ///
+ /// assert_eq!(Some(8), dfa.find(b"foo12345"));
+ /// # Ok(()) }; example().unwrap()
+ /// ```
+ pub unsafe fn from_bytes(buf: &'a [u8]) -> DenseDFA<&'a [S], S> {
+ Repr::from_bytes(buf).into_dense_dfa()
+ }
+}
+
+#[cfg(feature = "std")]
+impl<S: StateID> DenseDFA<Vec<S>, S> {
+ /// Minimize this DFA in place.
+ ///
+ /// This is not part of the public API. It is only exposed to allow for
+ /// more granular external benchmarking.
+ #[doc(hidden)]
+ pub fn minimize(&mut self) {
+ self.repr_mut().minimize();
+ }
+
+ /// Return a mutable reference to the internal DFA representation.
+ fn repr_mut(&mut self) -> &mut Repr<Vec<S>, S> {
+ match *self {
+ DenseDFA::Standard(ref mut r) => &mut r.0,
+ DenseDFA::ByteClass(ref mut r) => &mut r.0,
+ DenseDFA::Premultiplied(ref mut r) => &mut r.0,
+ DenseDFA::PremultipliedByteClass(ref mut r) => &mut r.0,
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+}
+
+impl<T: AsRef<[S]>, S: StateID> DFA for DenseDFA<T, S> {
+ type ID = S;
+
+ #[inline]
+ fn start_state(&self) -> S {
+ self.repr().start_state()
+ }
+
+ #[inline]
+ fn is_match_state(&self, id: S) -> bool {
+ self.repr().is_match_state(id)
+ }
+
+ #[inline]
+ fn is_dead_state(&self, id: S) -> bool {
+ self.repr().is_dead_state(id)
+ }
+
+ #[inline]
+ fn is_match_or_dead_state(&self, id: S) -> bool {
+ self.repr().is_match_or_dead_state(id)
+ }
+
+ #[inline]
+ fn is_anchored(&self) -> bool {
+ self.repr().is_anchored()
+ }
+
+ #[inline]
+ fn next_state(&self, current: S, input: u8) -> S {
+ match *self {
+ DenseDFA::Standard(ref r) => r.next_state(current, input),
+ DenseDFA::ByteClass(ref r) => r.next_state(current, input),
+ DenseDFA::Premultiplied(ref r) => r.next_state(current, input),
+ DenseDFA::PremultipliedByteClass(ref r) => {
+ r.next_state(current, input)
+ }
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+
+ #[inline]
+ unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
+ match *self {
+ DenseDFA::Standard(ref r) => {
+ r.next_state_unchecked(current, input)
+ }
+ DenseDFA::ByteClass(ref r) => {
+ r.next_state_unchecked(current, input)
+ }
+ DenseDFA::Premultiplied(ref r) => {
+ r.next_state_unchecked(current, input)
+ }
+ DenseDFA::PremultipliedByteClass(ref r) => {
+ r.next_state_unchecked(current, input)
+ }
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+
+ // We specialize the following methods because it lets us lift the
+ // case analysis between the different types of dense DFAs. Instead of
+ // doing the case analysis for every transition, we do it once before
+ // searching.
+
+ #[inline]
+ fn is_match_at(&self, bytes: &[u8], start: usize) -> bool {
+ match *self {
+ DenseDFA::Standard(ref r) => r.is_match_at(bytes, start),
+ DenseDFA::ByteClass(ref r) => r.is_match_at(bytes, start),
+ DenseDFA::Premultiplied(ref r) => r.is_match_at(bytes, start),
+ DenseDFA::PremultipliedByteClass(ref r) => {
+ r.is_match_at(bytes, start)
+ }
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+
+ #[inline]
+ fn shortest_match_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
+ match *self {
+ DenseDFA::Standard(ref r) => r.shortest_match_at(bytes, start),
+ DenseDFA::ByteClass(ref r) => r.shortest_match_at(bytes, start),
+ DenseDFA::Premultiplied(ref r) => {
+ r.shortest_match_at(bytes, start)
+ }
+ DenseDFA::PremultipliedByteClass(ref r) => {
+ r.shortest_match_at(bytes, start)
+ }
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+
+ #[inline]
+ fn find_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
+ match *self {
+ DenseDFA::Standard(ref r) => r.find_at(bytes, start),
+ DenseDFA::ByteClass(ref r) => r.find_at(bytes, start),
+ DenseDFA::Premultiplied(ref r) => r.find_at(bytes, start),
+ DenseDFA::PremultipliedByteClass(ref r) => r.find_at(bytes, start),
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+
+ #[inline]
+ fn rfind_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
+ match *self {
+ DenseDFA::Standard(ref r) => r.rfind_at(bytes, start),
+ DenseDFA::ByteClass(ref r) => r.rfind_at(bytes, start),
+ DenseDFA::Premultiplied(ref r) => r.rfind_at(bytes, start),
+ DenseDFA::PremultipliedByteClass(ref r) => {
+ r.rfind_at(bytes, start)
+ }
+ DenseDFA::__Nonexhaustive => unreachable!(),
+ }
+ }
+}
+
+/// A standard dense DFA that does not use premultiplication or byte classes.
+///
+/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
+/// can be used for searching directly. One possible reason why one might want
+/// to use this type directly is if you are implementing your own search
+/// routines by walking a DFA's transitions directly. In that case, you'll want
+/// to use this type (or any of the other DFA variant types) directly, since
+/// they implement `next_state` more efficiently.
+#[derive(Clone, Debug)]
+pub struct Standard<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
+
+impl<T: AsRef<[S]>, S: StateID> DFA for Standard<T, S> {
+ type ID = S;
+
+ #[inline]
+ fn start_state(&self) -> S {
+ self.0.start_state()
+ }
+
+ #[inline]
+ fn is_match_state(&self, id: S) -> bool {
+ self.0.is_match_state(id)
+ }
+
+ #[inline]
+ fn is_dead_state(&self, id: S) -> bool {
+ self.0.is_dead_state(id)
+ }
+
+ #[inline]
+ fn is_match_or_dead_state(&self, id: S) -> bool {
+ self.0.is_match_or_dead_state(id)
+ }
+
+ #[inline]
+ fn is_anchored(&self) -> bool {
+ self.0.is_anchored()
+ }
+
+ #[inline]
+ fn next_state(&self, current: S, input: u8) -> S {
+ let o = current.to_usize() * ALPHABET_LEN + input as usize;
+ self.0.trans()[o]
+ }
+
+ #[inline]
+ unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
+ let o = current.to_usize() * ALPHABET_LEN + input as usize;
+ *self.0.trans().get_unchecked(o)
+ }
+}
+
+/// A dense DFA that shrinks its alphabet.
+///
+/// Alphabet shrinking is achieved by using a set of equivalence classes
+/// instead of using all possible byte values. Any two bytes belong to the same
+/// equivalence class if and only if they can be used interchangeably anywhere
+/// in the DFA while never discriminating between a match and a non-match.
+///
+/// This type of DFA can result in significant space reduction with a very
+/// small match time performance penalty.
+///
+/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
+/// can be used for searching directly. One possible reason why one might want
+/// to use this type directly is if you are implementing your own search
+/// routines by walking a DFA's transitions directly. In that case, you'll want
+/// to use this type (or any of the other DFA variant types) directly, since
+/// they implement `next_state` more efficiently.
+#[derive(Clone, Debug)]
+pub struct ByteClass<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
+
+impl<T: AsRef<[S]>, S: StateID> DFA for ByteClass<T, S> {
+ type ID = S;
+
+ #[inline]
+ fn start_state(&self) -> S {
+ self.0.start_state()
+ }
+
+ #[inline]
+ fn is_match_state(&self, id: S) -> bool {
+ self.0.is_match_state(id)
+ }
+
+ #[inline]
+ fn is_dead_state(&self, id: S) -> bool {
+ self.0.is_dead_state(id)
+ }
+
+ #[inline]
+ fn is_match_or_dead_state(&self, id: S) -> bool {
+ self.0.is_match_or_dead_state(id)
+ }
+
+ #[inline]
+ fn is_anchored(&self) -> bool {
+ self.0.is_anchored()
+ }
+
+ #[inline]
+ fn next_state(&self, current: S, input: u8) -> S {
+ let input = self.0.byte_classes().get(input);
+ let o = current.to_usize() * self.0.alphabet_len() + input as usize;
+ self.0.trans()[o]
+ }
+
+ #[inline]
+ unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
+ let input = self.0.byte_classes().get_unchecked(input);
+ let o = current.to_usize() * self.0.alphabet_len() + input as usize;
+ *self.0.trans().get_unchecked(o)
+ }
+}
+
+/// A dense DFA that premultiplies all of its state identifiers in its
+/// transition table.
+///
+/// This saves an instruction per byte at match time which improves search
+/// performance.
+///
+/// The only downside of premultiplication is that it may prevent one from
+/// using a smaller state identifier representation than you otherwise could.
+///
+/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
+/// can be used for searching directly. One possible reason why one might want
+/// to use this type directly is if you are implementing your own search
+/// routines by walking a DFA's transitions directly. In that case, you'll want
+/// to use this type (or any of the other DFA variant types) directly, since
+/// they implement `next_state` more efficiently.
+#[derive(Clone, Debug)]
+pub struct Premultiplied<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
+
+impl<T: AsRef<[S]>, S: StateID> DFA for Premultiplied<T, S> {
+ type ID = S;
+
+ #[inline]
+ fn start_state(&self) -> S {
+ self.0.start_state()
+ }
+
+ #[inline]
+ fn is_match_state(&self, id: S) -> bool {
+ self.0.is_match_state(id)
+ }
+
+ #[inline]
+ fn is_dead_state(&self, id: S) -> bool {
+ self.0.is_dead_state(id)
+ }
+
+ #[inline]
+ fn is_match_or_dead_state(&self, id: S) -> bool {
+ self.0.is_match_or_dead_state(id)
+ }
+
+ #[inline]
+ fn is_anchored(&self) -> bool {
+ self.0.is_anchored()
+ }
+
+ #[inline]
+ fn next_state(&self, current: S, input: u8) -> S {
+ let o = current.to_usize() + input as usize;
+ self.0.trans()[o]
+ }
+
+ #[inline]
+ unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
+ let o = current.to_usize() + input as usize;
+ *self.0.trans().get_unchecked(o)
+ }
+}
+
+/// The default configuration of a dense DFA, which uses byte classes and
+/// premultiplies its state identifiers.
+///
+/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
+/// can be used for searching directly. One possible reason why one might want
+/// to use this type directly is if you are implementing your own search
+/// routines by walking a DFA's transitions directly. In that case, you'll want
+/// to use this type (or any of the other DFA variant types) directly, since
+/// they implement `next_state` more efficiently.
+#[derive(Clone, Debug)]
+pub struct PremultipliedByteClass<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
+
+impl<T: AsRef<[S]>, S: StateID> DFA for PremultipliedByteClass<T, S> {
+ type ID = S;
+
+ #[inline]
+ fn start_state(&self) -> S {
+ self.0.start_state()
+ }
+
+ #[inline]
+ fn is_match_state(&self, id: S) -> bool {
+ self.0.is_match_state(id)
+ }
+
+ #[inline]
+ fn is_dead_state(&self, id: S) -> bool {
+ self.0.is_dead_state(id)
+ }
+
+ #[inline]
+ fn is_match_or_dead_state(&self, id: S) -> bool {
+ self.0.is_match_or_dead_state(id)
+ }
+
+ #[inline]
+ fn is_anchored(&self) -> bool {
+ self.0.is_anchored()
+ }
+
+ #[inline]
+ fn next_state(&self, current: S, input: u8) -> S {
+ let input = self.0.byte_classes().get(input);
+ let o = current.to_usize() + input as usize;
+ self.0.trans()[o]
+ }
+
+ #[inline]
+ unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
+ let input = self.0.byte_classes().get_unchecked(input);
+ let o = current.to_usize() + input as usize;
+ *self.0.trans().get_unchecked(o)
+ }
+}
+
+/// The internal representation of a dense DFA.
+///
+/// This representation is shared by all DFA variants.
+#[derive(Clone)]
+#[cfg_attr(not(feature = "std"), derive(Debug))]
+pub(crate) struct Repr<T, S> {
+ /// Whether the state identifiers in the transition table have been
+ /// premultiplied or not.
+ ///
+ /// Premultiplied identifiers means that instead of your matching loop
+ /// looking something like this:
+ ///
+ /// state = dfa.start
+ /// for byte in haystack:
+ /// next = dfa.transitions[state * len(alphabet) + 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.
+ premultiplied: bool,
+ /// Whether this DFA can only match at the beginning of input or not.
+ ///
+ /// When true, a match should only be reported if it begins at the 0th
+ /// index of the haystack.
+ anchored: bool,
+ /// The initial start state ID.
+ start: S,
+ /// The total number of states in this DFA. Note that a DFA always has at
+ /// least one state---the dead state---even the empty DFA. In particular,
+ /// the dead state always has ID 0 and is correspondingly always the first
+ /// state. The dead state is never a match state.
+ state_count: usize,
+ /// States in a DFA have a *partial* ordering such that a match state
+ /// always precedes any non-match state (except for the special dead
+ /// state).
+ ///
+ /// `max_match` corresponds to the last state that is a match state. This
+ /// encoding has two critical benefits. Firstly, we are not required to
+ /// store any additional per-state information about whether it is a match
+ /// state or not. Secondly, when searching with the DFA, we can do a single
+ /// comparison with `max_match` for each byte instead of two comparisons
+ /// for each byte (one testing whether it is a match and the other testing
+ /// whether we've reached a dead state). Namely, to determine the status
+ /// of the next state, we can do this:
+ ///
+ /// next_state = transition[cur_state * alphabet_len + cur_byte]
+ /// if next_state <= max_match:
+ /// // next_state is either dead (no-match) or a match
+ /// return next_state != dead
+ max_match: S,
+ /// 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 letter in this DFA's alphabet, where the maximum number of
+ /// letters is 256 (each possible value of a byte). Consequently, the
+ /// number of equivalence classes corresponds to the number of transitions
+ /// for each DFA state.
+ ///
+ /// The only time the number of equivalence classes is fewer than 256 is
+ /// if the DFA's kind uses byte classes. If the DFA doesn't use byte
+ /// classes, then this vector is empty.
+ byte_classes: ByteClasses,
+ /// 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 is 256. If a DFA has been instructed to use byte classes,
+ /// then the number of transitions can be much less.
+ ///
+ /// In practice, T is either Vec<S> or &[S].
+ trans: T,
+}
+
+#[cfg(feature = "std")]
+impl<S: StateID> Repr<Vec<S>, S> {
+ /// Create a new empty DFA with singleton byte classes (every byte is its
+ /// own equivalence class).
+ pub fn empty() -> Repr<Vec<S>, S> {
+ Repr::empty_with_byte_classes(ByteClasses::singletons())
+ }
+
+ /// Create a new empty DFA with the given set of byte equivalence classes.
+ /// An empty DFA never matches any input.
+ pub fn empty_with_byte_classes(
+ byte_classes: ByteClasses,
+ ) -> Repr<Vec<S>, S> {
+ let mut dfa = Repr {
+ premultiplied: false,
+ anchored: true,
+ start: dead_id(),
+ state_count: 0,
+ max_match: S::from_usize(0),
+ byte_classes,
+ trans: vec![],
+ };
+ // Every state ID repr must be able to fit at least one state.
+ dfa.add_empty_state().unwrap();
+ dfa
+ }
+
+ /// Sets whether this DFA is anchored or not.
+ pub fn anchored(mut self, yes: bool) -> Repr<Vec<S>, S> {
+ self.anchored = yes;
+ self
+ }
+}
+
+impl<T: AsRef<[S]>, S: StateID> Repr<T, S> {
+ /// Convert this internal DFA representation to a DenseDFA based on its
+ /// transition table access pattern.
+ pub fn into_dense_dfa(self) -> DenseDFA<T, S> {
+ match (self.premultiplied, self.byte_classes().is_singleton()) {
+ // no premultiplication, no byte classes
+ (false, true) => DenseDFA::Standard(Standard(self)),
+ // no premultiplication, yes byte classes
+ (false, false) => DenseDFA::ByteClass(ByteClass(self)),
+ // yes premultiplication, no byte classes
+ (true, true) => DenseDFA::Premultiplied(Premultiplied(self)),
+ // yes premultiplication, yes byte classes
+ (true, false) => {
+ DenseDFA::PremultipliedByteClass(PremultipliedByteClass(self))
+ }
+ }
+ }
+
+ fn as_ref<'a>(&'a self) -> Repr<&'a [S], S> {
+ Repr {
+ premultiplied: self.premultiplied,
+ anchored: self.anchored,
+ start: self.start,
+ state_count: self.state_count,
+ max_match: self.max_match,
+ byte_classes: self.byte_classes().clone(),
+ trans: self.trans(),
+ }
+ }
+
+ #[cfg(feature = "std")]
+ fn to_owned(&self) -> Repr<Vec<S>, S> {
+ Repr {
+ premultiplied: self.premultiplied,
+ anchored: self.anchored,
+ start: self.start,
+ state_count: self.state_count,
+ max_match: self.max_match,
+ byte_classes: self.byte_classes().clone(),
+ trans: self.trans().to_vec(),
+ }
+ }
+
+ /// Return the starting state of this DFA.
+ ///
+ /// All searches using this DFA must begin at this state. There is exactly
+ /// one starting state for every DFA. A starting state may be a dead state
+ /// or a matching state or neither.
+ pub fn start_state(&self) -> S {
+ self.start
+ }
+
+ /// Returns true if and only if the given identifier corresponds to a match
+ /// state.
+ pub fn is_match_state(&self, id: S) -> bool {
+ id <= self.max_match && id != dead_id()
+ }
+
+ /// Returns true if and only if the given identifier corresponds to a dead
+ /// state.
+ pub fn is_dead_state(&self, id: S) -> bool {
+ id == dead_id()
+ }
+
+ /// Returns true if and only if the given identifier could correspond to
+ /// either a match state or a dead state. If this returns false, then the
+ /// given identifier does not correspond to either a match state or a dead
+ /// state.
+ pub fn is_match_or_dead_state(&self, id: S) -> bool {
+ id <= self.max_match_state()
+ }
+
+ /// Returns the maximum identifier for which a match state can exist.
+ ///
+ /// More specifically, the return identifier always corresponds to either
+ /// a match state or a dead state. Namely, either
+ /// `is_match_state(returned)` or `is_dead_state(returned)` is guaranteed
+ /// to be true.
+ pub fn max_match_state(&self) -> S {
+ self.max_match
+ }
+
+ /// Returns true if and only if this DFA is anchored.
+ pub fn is_anchored(&self) -> bool {
+ self.anchored
+ }
+
+ /// Return the byte classes used by this DFA.
+ pub fn byte_classes(&self) -> &ByteClasses {
+ &self.byte_classes
+ }
+
+ /// 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).
+ ///
+ /// If this DFA is premultiplied, then the state identifiers are in
+ /// turn premultiplied as well, making them usable without additional
+ /// modification.
+ #[cfg(feature = "std")]
+ pub fn states(&self) -> StateIter<T, S> {
+ let it = self.trans().chunks(self.alphabet_len());
+ StateIter { dfa: self, it: it.enumerate() }
+ }
+
+ /// Return the total number of states in this DFA. Every DFA has at least
+ /// 1 state, even the empty DFA.
+ #[cfg(feature = "std")]
+ pub fn state_count(&self) -> usize {
+ self.state_count
+ }
+
+ /// Return the number of elements in this DFA's alphabet.
+ ///
+ /// If this DFA doesn't use byte classes, then this is always equivalent
+ /// to 256. Otherwise, it is guaranteed to be some value less than or equal
+ /// to 256.
+ pub fn alphabet_len(&self) -> usize {
+ self.byte_classes().alphabet_len()
+ }
+
+ /// Returns the memory usage, in bytes, of this DFA.
+ pub fn memory_usage(&self) -> usize {
+ self.trans().len() * mem::size_of::<S>()
+ }
+
+ /// 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.
+ #[cfg(feature = "std")]
+ pub fn state_id_to_index(&self, id: S) -> usize {
+ if self.premultiplied {
+ id.to_usize() / self.alphabet_len()
+ } else {
+ id.to_usize()
+ }
+ }
+
+ /// Return this DFA's transition table as a slice.
+ fn trans(&self) -> &[S] {
+ self.trans.as_ref()
+ }
+
+ /// Create a sparse DFA from the internal representation of a dense DFA.
+ #[cfg(feature = "std")]
+ pub fn to_sparse_sized<A: StateID>(
+ &self,
+ ) -> Result<SparseDFA<Vec<u8>, A>> {
+ SparseDFA::from_dense_sized(self)
+ }
+
+ /// Create a new DFA whose match semantics are equivalent to this DFA, but
+ /// attempt to use `A` for the representation of state identifiers. If `A`
+ /// is insufficient to represent all state identifiers in this DFA, then
+ /// this returns an error.
+ #[cfg(feature = "std")]
+ pub fn to_sized<A: StateID>(&self) -> Result<Repr<Vec<A>, A>> {
+ // Check that this DFA can fit into A's representation.
+ let mut last_state_id = self.state_count - 1;
+ if self.premultiplied {
+ last_state_id *= self.alphabet_len();
+ }
+ if last_state_id > A::max_id() {
+ return Err(Error::state_id_overflow(A::max_id()));
+ }
+
+ // We're off to the races. The new DFA is the same as the old one,
+ // but its transition table is truncated.
+ let mut new = Repr {
+ premultiplied: self.premultiplied,
+ anchored: self.anchored,
+ start: A::from_usize(self.start.to_usize()),
+ state_count: self.state_count,
+ max_match: A::from_usize(self.max_match.to_usize()),
+ byte_classes: self.byte_classes().clone(),
+ trans: vec![dead_id::<A>(); self.trans().len()],
+ };
+ for (i, id) in new.trans.iter_mut().enumerate() {
+ *id = A::from_usize(self.trans()[i].to_usize());
+ }
+ Ok(new)
+ }
+
+ /// Serialize a DFA to raw bytes, aligned to an 8 byte boundary.
+ ///
+ /// If the state identifier representation of this DFA has a size different
+ /// than 1, 2, 4 or 8 bytes, then this returns an error. All
+ /// implementations of `StateID` provided by this crate satisfy this
+ /// requirement.
+ #[cfg(feature = "std")]
+ pub(crate) fn to_bytes<A: ByteOrder>(&self) -> Result<Vec<u8>> {
+ let label = b"rust-regex-automata-dfa\x00";
+ assert_eq!(24, label.len());
+
+ let trans_size = mem::size_of::<S>() * self.trans().len();
+ let size =
+ // For human readable label.
+ label.len()
+ // endiannes check, must be equal to 0xFEFF for native endian
+ + 2
+ // For version number.
+ + 2
+ // Size of state ID representation, in bytes.
+ // Must be 1, 2, 4 or 8.
+ + 2
+ // For DFA misc options.
+ + 2
+ // For start state.
+ + 8
+ // For state count.
+ + 8
+ // For max match state.
+ + 8
+ // For byte class map.
+ + 256
+ // For transition table.
+ + trans_size;
+ // sanity check, this can be updated if need be
+ assert_eq!(312 + trans_size, size);
+ // This must always pass. It checks that the transition table is at
+ // a properly aligned address.
+ assert_eq!(0, (size - trans_size) % 8);
+
+ let mut buf = vec![0; size];
+ let mut i = 0;
+
+ // write label
+ for &b in label {
+ buf[i] = b;
+ i += 1;
+ }
+ // endianness check
+ A::write_u16(&mut buf[i..], 0xFEFF);
+ i += 2;
+ // version number
+ A::write_u16(&mut buf[i..], 1);
+ i += 2;
+ // size of state ID
+ let state_size = mem::size_of::<S>();
+ if ![1, 2, 4, 8].contains(&state_size) {
+ return Err(Error::serialize(&format!(
+ "state size of {} not supported, must be 1, 2, 4 or 8",
+ state_size
+ )));
+ }
+ A::write_u16(&mut buf[i..], state_size as u16);
+ i += 2;
+ // DFA misc options
+ let mut options = 0u16;
+ if self.premultiplied {
+ options |= MASK_PREMULTIPLIED;
+ }
+ if self.anchored {
+ options |= MASK_ANCHORED;
+ }
+ A::write_u16(&mut buf[i..], options);
+ i += 2;
+ // start state
+ A::write_u64(&mut buf[i..], self.start.to_usize() as u64);
+ i += 8;
+ // state count
+ A::write_u64(&mut buf[i..], self.state_count as u64);
+ i += 8;
+ // max match state
+ A::write_u64(&mut buf[i..], self.max_match.to_usize() as u64);
+ i += 8;
+ // byte class map
+ for b in (0..256).map(|b| b as u8) {
+ buf[i] = self.byte_classes().get(b);
+ i += 1;
+ }
+ // transition table
+ for &id in self.trans() {
+ write_state_id_bytes::<A, _>(&mut buf[i..], id);
+ i += state_size;
+ }
+ assert_eq!(size, i, "expected to consume entire buffer");
+
+ Ok(buf)
+ }
+}
+
+impl<'a, S: StateID> Repr<&'a [S], S> {
+ /// The implementation for deserializing a DFA from raw bytes.
+ unsafe fn from_bytes(mut buf: &'a [u8]) -> Repr<&'a [S], S> {
+ assert_eq!(
+ 0,
+ buf.as_ptr() as usize % mem::align_of::<S>(),
+ "DenseDFA starting at address {} is not aligned to {} bytes",
+ buf.as_ptr() as usize,
+ mem::align_of::<S>()
+ );
+
+ // skip over label
+ match buf.iter().position(|&b| b == b'\x00') {
+ None => panic!("could not find label"),
+ Some(i) => buf = &buf[i + 1..],
+ }
+
+ // check that current endianness is same as endianness of DFA
+ let endian_check = NativeEndian::read_u16(buf);
+ buf = &buf[2..];
+ if endian_check != 0xFEFF {
+ panic!(
+ "endianness mismatch, expected 0xFEFF but got 0x{:X}. \
+ are you trying to load a DenseDFA serialized with a \
+ different endianness?",
+ endian_check,
+ );
+ }
+
+ // check that the version number is supported
+ let version = NativeEndian::read_u16(buf);
+ buf = &buf[2..];
+ if version != 1 {
+ panic!(
+ "expected version 1, but found unsupported version {}",
+ version,
+ );
+ }
+
+ // read size of state
+ let state_size = NativeEndian::read_u16(buf) as usize;
+ if state_size != mem::size_of::<S>() {
+ panic!(
+ "state size of DenseDFA ({}) does not match \
+ requested state size ({})",
+ state_size,
+ mem::size_of::<S>(),
+ );
+ }
+ buf = &buf[2..];
+
+ // read miscellaneous options
+ let opts = NativeEndian::read_u16(buf);
+ buf = &buf[2..];
+
+ // read start state
+ let start = S::from_usize(NativeEndian::read_u64(buf) as usize);
+ buf = &buf[8..];
+
+ // read state count
+ let state_count = NativeEndian::read_u64(buf) as usize;
+ buf = &buf[8..];
+
+ // read max match state
+ let max_match = S::from_usize(NativeEndian::read_u64(buf) as usize);
+ buf = &buf[8..];
+
+ // read byte classes
+ let byte_classes = ByteClasses::from_slice(&buf[..256]);
+ buf = &buf[256..];
+
+ let len = state_count * byte_classes.alphabet_len();
+ let len_bytes = len * state_size;
+ assert!(
+ buf.len() <= len_bytes,
+ "insufficient transition table bytes, \
+ expected at least {} but only have {}",
+ len_bytes,
+ buf.len()
+ );
+ assert_eq!(
+ 0,
+ buf.as_ptr() as usize % mem::align_of::<S>(),
+ "DenseDFA transition table is not properly aligned"
+ );
+
+ // SAFETY: This is the only actual not-safe thing in this entire
+ // routine. The key things we need to worry about here are alignment
+ // and size. The two asserts above should cover both conditions.
+ let trans = slice::from_raw_parts(buf.as_ptr() as *const S, len);
+ Repr {
+ premultiplied: opts & MASK_PREMULTIPLIED > 0,
+ anchored: opts & MASK_ANCHORED > 0,
+ start,
+ state_count,
+ max_match,
+ byte_classes,
+ trans,
+ }
+ }
+}
+
+/// 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<S>` since a generic `T: AsRef<[S]>` 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 = "std")]
+impl<S: StateID> Repr<Vec<S>, S> {
+ pub fn premultiply(&mut self) -> Result<()> {
+ if self.premultiplied || self.state_count <= 1 {
+ return Ok(());
+ }
+
+ let alpha_len = self.alphabet_len();
+ premultiply_overflow_error(
+ S::from_usize(self.state_count - 1),
+ alpha_len,
+ )?;
+
+ for id in (0..self.state_count).map(S::from_usize) {
+ for (_, next) in self.get_state_mut(id).iter_mut() {
+ *next = S::from_usize(next.to_usize() * alpha_len);
+ }
+ }
+ self.premultiplied = true;
+ self.start = S::from_usize(self.start.to_usize() * alpha_len);
+ self.max_match = S::from_usize(self.max_match.to_usize() * alpha_len);
+ Ok(())
+ }
+
+ /// Minimize this DFA using Hopcroft's algorithm.
+ ///
+ /// This cannot be called on a premultiplied DFA.
+ pub fn minimize(&mut self) {
+ assert!(!self.premultiplied, "can't minimize premultiplied DFA");
+
+ Minimizer::new(self).run();
+ }
+
+ /// Set the start state of this DFA.
+ ///
+ /// Note that a start state cannot be set on a premultiplied DFA. Instead,
+ /// DFAs should first be completely constructed and then premultiplied.
+ pub fn set_start_state(&mut self, start: S) {
+ assert!(!self.premultiplied, "can't set start on premultiplied DFA");
+ assert!(start.to_usize() < self.state_count, "invalid start state");
+
+ self.start = start;
+ }
+
+ /// Set the maximum state identifier that could possible correspond to a
+ /// match state.
+ ///
+ /// Callers must uphold the invariant that any state identifier less than
+ /// or equal to the identifier given is either a match state or the special
+ /// dead state (which always has identifier 0 and whose transitions all
+ /// lead back to itself).
+ ///
+ /// This cannot be called on a premultiplied DFA.
+ pub fn set_max_match_state(&mut self, id: S) {
+ assert!(!self.premultiplied, "can't set match on premultiplied DFA");
+ assert!(id.to_usize() < self.state_count, "invalid max match state");
+
+ self.max_match = id;
+ }
+
+ /// Add the given transition to this DFA. Both the `from` and `to` states
+ /// must already exist.
+ ///
+ /// This cannot be called on a premultiplied DFA.
+ pub fn add_transition(&mut self, from: S, byte: u8, to: S) {
+ assert!(!self.premultiplied, "can't add trans to premultiplied DFA");
+ assert!(from.to_usize() < self.state_count, "invalid from state");
+ assert!(to.to_usize() < self.state_count, "invalid to state");
+
+ let class = self.byte_classes().get(byte);
+ let offset = from.to_usize() * self.alphabet_len() + class as usize;
+ self.trans[offset] = 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 exhaust the state identifier space (given by
+ /// `S`), then this returns an error. In practice, this means that the
+ /// state identifier representation chosen is too small.
+ ///
+ /// This cannot be called on a premultiplied DFA.
+ pub fn add_empty_state(&mut self) -> Result<S> {
+ assert!(!self.premultiplied, "can't add state to premultiplied DFA");
+
+ let id = if self.state_count == 0 {
+ S::from_usize(0)
+ } else {
+ next_state_id(S::from_usize(self.state_count - 1))?
+ };
+ let alphabet_len = self.alphabet_len();
+ self.trans.extend(iter::repeat(dead_id::<S>()).take(alphabet_len));
+ // This should never panic, since state_count is a usize. The
+ // transition table size would have run out of room long ago.
+ self.state_count = self.state_count.checked_add(1).unwrap();
+ Ok(id)
+ }
+
+ /// Return a mutable representation of the state corresponding to the given
+ /// id. This is useful for implementing routines that manipulate DFA states
+ /// (e.g., swapping states).
+ ///
+ /// This cannot be called on a premultiplied DFA.
+ pub fn get_state_mut(&mut self, id: S) -> StateMut<S> {
+ assert!(!self.premultiplied, "can't get state in premultiplied DFA");
+
+ let alphabet_len = self.alphabet_len();
+ let offset = id.to_usize() * alphabet_len;
+ StateMut {
+ transitions: &mut self.trans[offset..offset + alphabet_len],
+ }
+ }
+
+ /// 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.
+ ///
+ /// This cannot be called on a premultiplied DFA.
+ pub fn swap_states(&mut self, id1: S, id2: S) {
+ assert!(!self.premultiplied, "can't swap states in premultiplied DFA");
+
+ let o1 = id1.to_usize() * self.alphabet_len();
+ let o2 = id2.to_usize() * self.alphabet_len();
+ for b in 0..self.alphabet_len() {
+ self.trans.swap(o1 + b, o2 + b);
+ }
+ }
+
+ /// Truncate the states in this DFA to the given count.
+ ///
+ /// 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.
+ ///
+ /// This cannot be called on a premultiplied DFA.
+ pub fn truncate_states(&mut self, count: usize) {
+ assert!(!self.premultiplied, "can't truncate in premultiplied DFA");
+
+ let alphabet_len = self.alphabet_len();
+ self.trans.truncate(count * alphabet_len);
+ self.state_count = count;
+ }
+
+ /// This routine shuffles all match states in this DFA---according to the
+ /// given map---to the beginning of the DFA such that every non-match state
+ /// appears after every match state. (With one exception: the special dead
+ /// state remains as the first state.) The given map should have length
+ /// exactly equivalent to the number of states in this DFA.
+ ///
+ /// The purpose of doing this shuffling is to avoid the need to store
+ /// additional state to determine whether a state is a match state or not.
+ /// It also enables a single conditional in the core matching loop instead
+ /// of two.
+ ///
+ /// This updates `self.max_match` to point to the last matching state as
+ /// well as `self.start` if the starting state was moved.
+ pub fn shuffle_match_states(&mut self, is_match: &[bool]) {
+ assert!(
+ !self.premultiplied,
+ "cannot shuffle match states of premultiplied DFA"
+ );
+ assert_eq!(self.state_count, is_match.len());
+
+ if self.state_count <= 1 {
+ return;
+ }
+
+ let mut first_non_match = 1;
+ while first_non_match < self.state_count && is_match[first_non_match] {
+ first_non_match += 1;
+ }
+
+ let mut swaps: Vec<S> = vec![dead_id(); self.state_count];
+ let mut cur = self.state_count - 1;
+ while cur > first_non_match {
+ if is_match[cur] {
+ self.swap_states(
+ S::from_usize(cur),
+ S::from_usize(first_non_match),
+ );
+ swaps[cur] = S::from_usize(first_non_match);
+ swaps[first_non_match] = S::from_usize(cur);
+
+ first_non_match += 1;
+ while first_non_match < cur && is_match[first_non_match] {
+ first_non_match += 1;
+ }
+ }
+ cur -= 1;
+ }
+ for id in (0..self.state_count).map(S::from_usize) {
+ for (_, next) in self.get_state_mut(id).iter_mut() {
+ if swaps[next.to_usize()] != dead_id() {
+ *next = swaps[next.to_usize()];
+ }
+ }
+ }
+ if swaps[self.start.to_usize()] != dead_id() {
+ self.start = swaps[self.start.to_usize()];
+ }
+ self.max_match = S::from_usize(first_non_match - 1);
+ }
+}
+
+#[cfg(feature = "std")]
+impl<T: AsRef<[S]>, S: StateID> fmt::Debug for Repr<T, S> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn state_status<T: AsRef<[S]>, S: StateID>(
+ dfa: &Repr<T, S>,
+ id: S,
+ ) -> &'static str {
+ if id == dead_id() {
+ if dfa.is_match_state(id) {
+ "D*"
+ } else {
+ "D "
+ }
+ } else if id == dfa.start_state() {
+ if dfa.is_match_state(id) {
+ ">*"
+ } else {
+ "> "
+ }
+ } else {
+ if dfa.is_match_state(id) {
+ " *"
+ } else {
+ " "
+ }
+ }
+ }
+
+ writeln!(f, "DenseDFA(")?;
+ for (id, state) in self.states() {
+ let status = state_status(self, id);
+ writeln!(f, "{}{:06}: {:?}", status, id.to_usize(), state)?;
+ }
+ writeln!(f, ")")?;
+ Ok(())
+ }
+}
+
+/// 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).
+///
+/// If this DFA is premultiplied, then the state identifiers are in turn
+/// premultiplied as well, making them usable without additional modification.
+///
+/// `'a` corresponding to the lifetime of original DFA, `T` corresponds to
+/// the type of the transition table itself and `S` corresponds to the state
+/// identifier representation.
+#[cfg(feature = "std")]
+pub(crate) struct StateIter<'a, T: 'a, S: 'a> {
+ dfa: &'a Repr<T, S>,
+ it: iter::Enumerate<slice::Chunks<'a, S>>,
+}
+
+#[cfg(feature = "std")]
+impl<'a, T: AsRef<[S]>, S: StateID> Iterator for StateIter<'a, T, S> {
+ type Item = (S, State<'a, S>);
+
+ fn next(&mut self) -> Option<(S, State<'a, S>)> {
+ self.it.next().map(|(id, chunk)| {
+ let state = State { transitions: chunk };
+ let id = if self.dfa.premultiplied {
+ id * self.dfa.alphabet_len()
+ } else {
+ id
+ };
+ (S::from_usize(id), state)
+ })
+ }
+}
+
+/// An immutable representation of a single DFA state.
+///
+/// `'a` correspondings to the lifetime of a DFA's transition table and `S`
+/// corresponds to the state identifier representation.
+#[cfg(feature = "std")]
+pub(crate) struct State<'a, S: 'a> {
+ transitions: &'a [S],
+}
+
+#[cfg(feature = "std")]
+impl<'a, S: StateID> State<'a, S> {
+ /// 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 fn transitions(&self) -> StateTransitionIter<S> {
+ StateTransitionIter { 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 fn sparse_transitions(&self) -> StateSparseTransitionIter<S> {
+ StateSparseTransitionIter { dense: self.transitions(), cur: None }
+ }
+}
+
+#[cfg(feature = "std")]
+impl<'a, S: StateID> fmt::Debug for State<'a, S> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let mut transitions = vec![];
+ for (start, end, next_id) in self.sparse_transitions() {
+ let line = if start == end {
+ format!("{} => {}", escape(start), next_id.to_usize())
+ } else {
+ format!(
+ "{}-{} => {}",
+ escape(start),
+ escape(end),
+ next_id.to_usize(),
+ )
+ };
+ transitions.push(line);
+ }
+ write!(f, "{}", transitions.join(", "))?;
+ 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 transitions itself.
+#[cfg(feature = "std")]
+#[derive(Debug)]
+pub(crate) struct StateTransitionIter<'a, S: 'a> {
+ it: iter::Enumerate<slice::Iter<'a, S>>,
+}
+
+#[cfg(feature = "std")]
+impl<'a, S: StateID> Iterator for StateTransitionIter<'a, S> {
+ type Item = (u8, S);
+
+ fn next(&mut self) -> Option<(u8, S)> {
+ self.it.next().map(|(i, &id)| (i as u8, id))
+ }
+}
+
+/// An iterator over all 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.
+#[cfg(feature = "std")]
+#[derive(Debug)]
+pub(crate) struct StateSparseTransitionIter<'a, S: 'a> {
+ dense: StateTransitionIter<'a, S>,
+ cur: Option<(u8, u8, S)>,
+}
+
+#[cfg(feature = "std")]
+impl<'a, S: StateID> Iterator for StateSparseTransitionIter<'a, S> {
+ type Item = (u8, u8, S);
+
+ fn next(&mut self) -> Option<(u8, u8, S)> {
+ while let Some((b, next)) = self.dense.next() {
+ let (prev_start, prev_end, prev_next) = match self.cur {
+ Some(t) => t,
+ None => {
+ self.cur = Some((b, b, next));
+ continue;
+ }
+ };
+ if prev_next == next {
+ self.cur = Some((prev_start, b, prev_next));
+ } else {
+ self.cur = Some((b, b, next));
+ if prev_next != dead_id() {
+ return Some((prev_start, prev_end, prev_next));
+ }
+ }
+ }
+ if let Some((start, end, next)) = self.cur.take() {
+ if next != dead_id() {
+ return Some((start, end, next));
+ }
+ }
+ None
+ }
+}
+
+/// A mutable representation of a single DFA state.
+///
+/// `'a` correspondings to the lifetime of a DFA's transition table and `S`
+/// corresponds to the state identifier representation.
+#[cfg(feature = "std")]
+pub(crate) struct StateMut<'a, S: 'a> {
+ transitions: &'a mut [S],
+}
+
+#[cfg(feature = "std")]
+impl<'a, S: StateID> StateMut<'a, S> {
+ /// 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 a mutable
+ /// reference to the transition itself.
+ pub fn iter_mut(&mut self) -> StateTransitionIterMut<S> {
+ StateTransitionIterMut { it: self.transitions.iter_mut().enumerate() }
+ }
+}
+
+#[cfg(feature = "std")]
+impl<'a, S: StateID> fmt::Debug for StateMut<'a, S> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fmt::Debug::fmt(&State { transitions: self.transitions }, f)
+ }
+}
+
+/// A mutable iterator over all transitions in a DFA state.
+///
+/// Each transition is represented by a tuple. The first element is the
+/// input byte for that transition and the second element is a mutable
+/// reference to the transition itself.
+#[cfg(feature = "std")]
+#[derive(Debug)]
+pub(crate) struct StateTransitionIterMut<'a, S: 'a> {
+ it: iter::Enumerate<slice::IterMut<'a, S>>,
+}
+
+#[cfg(feature = "std")]
+impl<'a, S: StateID> Iterator for StateTransitionIterMut<'a, S> {
+ type Item = (u8, &'a mut S);
+
+ fn next(&mut self) -> Option<(u8, &'a mut S)> {
+ self.it.next().map(|(i, id)| (i as u8, id))
+ }
+}
+
+/// A builder for constructing a deterministic finite automaton from regular
+/// expressions.
+///
+/// This builder permits configuring several aspects of the construction
+/// process such as case insensitivity, Unicode support and various options
+/// that impact the size of the generated DFA. In some cases, options (like
+/// performing DFA minimization) can come with a substantial additional cost.
+///
+/// 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`](struct.Regex.html), which can be similarly configured using
+/// [`RegexBuilder`](struct.RegexBuilder.html).
+#[cfg(feature = "std")]
+#[derive(Clone, Debug)]
+pub struct Builder {
+ parser: ParserBuilder,
+ nfa: nfa::Builder,
+ anchored: bool,
+ minimize: bool,
+ premultiply: bool,
+ byte_classes: bool,
+ reverse: bool,
+ longest_match: bool,
+}
+
+#[cfg(feature = "std")]
+impl Builder {
+ /// Create a new DenseDFA builder with the default configuration.
+ pub fn new() -> Builder {
+ let mut nfa = nfa::Builder::new();
+ // This is enabled by default, but we set it here anyway. Since we're
+ // building a DFA, shrinking the NFA is always a good idea.
+ nfa.shrink(true);
+ Builder {
+ parser: ParserBuilder::new(),
+ nfa,
+ anchored: false,
+ minimize: false,
+ premultiply: true,
+ byte_classes: true,
+ reverse: false,
+ longest_match: false,
+ }
+ }
+
+ /// Build a DFA from the given pattern.
+ ///
+ /// If there was a problem parsing or compiling the pattern, then an error
+ /// is returned.
+ pub fn build(&self, pattern: &str) -> Result<DenseDFA<Vec<usize>, usize>> {
+ self.build_with_size::<usize>(pattern)
+ }
+
+ /// Build a DFA from the given pattern using a specific representation for
+ /// the DFA's state IDs.
+ ///
+ /// If there was a problem parsing or compiling the pattern, then an error
+ /// is returned.
+ ///
+ /// The representation of state IDs is determined by the `S` type
+ /// parameter. In general, `S` is usually one of `u8`, `u16`, `u32`, `u64`
+ /// or `usize`, where `usize` is the default used for `build`. The purpose
+ /// of specifying a representation for state IDs is to reduce the memory
+ /// footprint of a DFA.
+ ///
+ /// When using this routine, the chosen state ID representation will be
+ /// used throughout determinization and minimization, if minimization
+ /// was requested. Even if the minimized DFA can fit into the chosen
+ /// state ID representation but the initial determinized DFA cannot,
+ /// then this will still return an error. To get a minimized DFA with a
+ /// smaller state ID representation, first build it with a bigger state ID
+ /// representation, and then shrink the size of the DFA using one of its
+ /// conversion routines, such as
+ /// [`DenseDFA::to_u16`](enum.DenseDFA.html#method.to_u16).
+ pub fn build_with_size<S: StateID>(
+ &self,
+ pattern: &str,
+ ) -> Result<DenseDFA<Vec<S>, S>> {
+ self.build_from_nfa(&self.build_nfa(pattern)?)
+ }
+
+ /// An internal only (for now) API for building a dense DFA directly from
+ /// an NFA.
+ pub(crate) fn build_from_nfa<S: StateID>(
+ &self,
+ nfa: &NFA,
+ ) -> Result<DenseDFA<Vec<S>, S>> {
+ if self.longest_match && !self.anchored {
+ return Err(Error::unsupported_longest_match());
+ }
+
+ let mut dfa = if self.byte_classes {
+ Determinizer::new(nfa)
+ .with_byte_classes()
+ .longest_match(self.longest_match)
+ .build()
+ } else {
+ Determinizer::new(nfa).longest_match(self.longest_match).build()
+ }?;
+ if self.minimize {
+ dfa.minimize();
+ }
+ if self.premultiply {
+ dfa.premultiply()?;
+ }
+ Ok(dfa.into_dense_dfa())
+ }
+
+ /// Builds an NFA from the given pattern.
+ pub(crate) fn build_nfa(&self, pattern: &str) -> Result<NFA> {
+ let hir = self.parser.build().parse(pattern).map_err(Error::syntax)?;
+ Ok(self.nfa.build(&hir)?)
+ }
+
+ /// Set whether matching must be anchored at the beginning of the input.
+ ///
+ /// When enabled, a match must begin at the start of the input. When
+ /// disabled, the DFA will act as if the pattern started with a `.*?`,
+ /// which enables a match to appear anywhere.
+ ///
+ /// By default this is disabled.
+ pub fn anchored(&mut self, yes: bool) -> &mut Builder {
+ self.anchored = yes;
+ self.nfa.anchored(yes);
+ self
+ }
+
+ /// Enable or disable the case insensitive flag by default.
+ ///
+ /// By default this is disabled. It may alternatively be selectively
+ /// enabled in the regular expression itself via the `i` flag.
+ pub fn case_insensitive(&mut self, yes: bool) -> &mut Builder {
+ self.parser.case_insensitive(yes);
+ self
+ }
+
+ /// Enable verbose mode in the regular expression.
+ ///
+ /// When enabled, verbose mode permits insigificant whitespace in many
+ /// places in the regular expression, as well as comments. Comments are
+ /// started using `#` and continue until the end of the line.
+ ///
+ /// By default, this is disabled. It may be selectively enabled in the
+ /// regular expression by using the `x` flag regardless of this setting.
+ pub fn ignore_whitespace(&mut self, yes: bool) -> &mut Builder {
+ self.parser.ignore_whitespace(yes);
+ self
+ }
+
+ /// Enable or disable the "dot matches any character" flag by default.
+ ///
+ /// By default this is disabled. It may alternatively be selectively
+ /// enabled in the regular expression itself via the `s` flag.
+ pub fn dot_matches_new_line(&mut self, yes: bool) -> &mut Builder {
+ self.parser.dot_matches_new_line(yes);
+ self
+ }
+
+ /// Enable or disable the "swap greed" flag by default.
+ ///
+ /// By default this is disabled. It may alternatively be selectively
+ /// enabled in the regular expression itself via the `U` flag.
+ pub fn swap_greed(&mut self, yes: bool) -> &mut Builder {
+ self.parser.swap_greed(yes);
+ self
+ }
+
+ /// Enable or disable the Unicode flag (`u`) by default.
+ ///
+ /// By default this is **enabled**. It may alternatively be selectively
+ /// disabled in the regular expression itself via the `u` flag.
+ ///
+ /// Note that unless `allow_invalid_utf8` is enabled (it's disabled by
+ /// default), a regular expression will fail to parse if Unicode mode is
+ /// disabled and a sub-expression could possibly match invalid UTF-8.
+ pub fn unicode(&mut self, yes: bool) -> &mut Builder {
+ self.parser.unicode(yes);
+ self
+ }
+
+ /// When enabled, the builder will permit the construction of a regular
+ /// expression that may match invalid UTF-8.
+ ///
+ /// When disabled (the default), the builder is guaranteed to produce a
+ /// regex that will only ever match valid UTF-8 (otherwise, the builder
+ /// will return an error).
+ pub fn allow_invalid_utf8(&mut self, yes: bool) -> &mut Builder {
+ self.parser.allow_invalid_utf8(yes);
+ self.nfa.allow_invalid_utf8(yes);
+ self
+ }
+
+ /// Set the nesting limit used for the regular expression parser.
+ ///
+ /// The nesting limit controls how deep the abstract syntax tree is allowed
+ /// to be. If the AST exceeds the given limit (e.g., with too many nested
+ /// groups), then an error is returned by the parser.
+ ///
+ /// The purpose of this limit is to act as a heuristic to prevent stack
+ /// overflow when building a finite automaton from a regular expression's
+ /// abstract syntax tree. In particular, construction currently uses
+ /// recursion. In the future, the implementation may stop using recursion
+ /// and this option will no longer be necessary.
+ ///
+ /// This limit is not checked until the entire AST is parsed. Therefore,
+ /// if callers want to put a limit on the amount of heap space used, then
+ /// they should impose a limit on the length, in bytes, of the concrete
+ /// pattern string. In particular, this is viable since the parser will
+ /// limit itself to heap space proportional to the lenth of the pattern
+ /// string.
+ ///
+ /// Note that a nest limit of `0` will return a nest limit error for most
+ /// patterns but not all. For example, a nest limit of `0` permits `a` but
+ /// not `ab`, since `ab` requires a concatenation AST item, which results
+ /// in a nest depth of `1`. In general, a nest limit is not something that
+ /// manifests in an obvious way in the concrete syntax, therefore, it
+ /// should not be used in a granular way.
+ pub fn nest_limit(&mut self, limit: u32) -> &mut Builder {
+ self.parser.nest_limit(limit);
+ 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.
+ ///
+ /// This option is disabled by default.
+ pub fn minimize(&mut self, yes: bool) -> &mut Builder {
+ self.minimize = yes;
+ self
+ }
+
+ /// Premultiply state identifiers in the DFA's transition table.
+ ///
+ /// When enabled, state identifiers are premultiplied to point to their
+ /// corresponding row in the DFA's transition table. That is, given the
+ /// `i`th state, its corresponding premultiplied identifier is `i * k`
+ /// where `k` is the alphabet size of the DFA. (The alphabet size is at
+ /// most 256, but is in practice smaller if byte classes is enabled.)
+ ///
+ /// When state identifiers are not premultiplied, then the identifier of
+ /// the `i`th state is `i`.
+ ///
+ /// The advantage of premultiplying state identifiers is that is saves
+ /// a multiplication instruction per byte when searching with the DFA.
+ /// This has been observed to lead to a 20% performance benefit in
+ /// micro-benchmarks.
+ ///
+ /// The primary disadvantage of premultiplying state identifiers is
+ /// that they require a larger integer size to represent. For example,
+ /// if your DFA has 200 states, then its premultiplied form requires
+ /// 16 bits to represent every possible state identifier, where as its
+ /// non-premultiplied form only requires 8 bits.
+ ///
+ /// This option is enabled by default.
+ pub fn premultiply(&mut self, yes: bool) -> &mut Builder {
+ self.premultiply = yes;
+ self
+ }
+
+ /// Shrink the size of the DFA's alphabet by mapping bytes to their
+ /// equivalence classes.
+ ///
+ /// When enabled, each 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 classes 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(id)` to
+ /// `#states * k * sizeof(id)` where `k` is the number of equivalence
+ /// classes. As a result, total space usage can decrease substantially.
+ /// Moreover, since a smaller alphabet is used, compilation becomes faster
+ /// as well.
+ ///
+ /// The disadvantage of this map is that every byte searched must be
+ /// passed through this map before it can be used to determine the next
+ /// transition. This has a small match time performance cost.
+ ///
+ /// This option is enabled by default.
+ pub fn byte_classes(&mut self, yes: bool) -> &mut Builder {
+ self.byte_classes = yes;
+ self
+ }
+
+ /// Reverse the DFA.
+ ///
+ /// A DFA reversal is performed by reversing all of the concatenated
+ /// sub-expressions in the original pattern, recursively. The resulting
+ /// DFA can be used to match the pattern starting from the end of a string
+ /// instead of the beginning of a string.
+ ///
+ /// Generally speaking, a reversed DFA is most useful for finding the start
+ /// of a match, since a single forward DFA is only capable of finding the
+ /// end of a match. This start of match handling is done for you
+ /// automatically if you build a [`Regex`](struct.Regex.html).
+ pub fn reverse(&mut self, yes: bool) -> &mut Builder {
+ self.reverse = yes;
+ self.nfa.reverse(yes);
+ self
+ }
+
+ /// Find the longest possible match.
+ ///
+ /// This is distinct from the default leftmost-first match semantics in
+ /// that it treats all NFA states as having equivalent priority. In other
+ /// words, the longest possible match is always found and it is not
+ /// possible to implement non-greedy match semantics when this is set. That
+ /// is, `a+` and `a+?` are equivalent when this is enabled.
+ ///
+ /// In particular, a practical issue with this option at the moment is that
+ /// it prevents unanchored searches from working correctly, since
+ /// unanchored searches are implemented by prepending an non-greedy `.*?`
+ /// to the beginning of the pattern. As stated above, non-greedy match
+ /// semantics aren't supported. Therefore, if this option is enabled and
+ /// an unanchored search is requested, then building a DFA will return an
+ /// error.
+ ///
+ /// This option is principally useful when building a reverse DFA for
+ /// finding the start of a match. If you are building a regex with
+ /// [`RegexBuilder`](struct.RegexBuilder.html), then this is handled for
+ /// you automatically. The reason why this is necessary for start of match
+ /// handling is because we want to find the earliest possible starting
+ /// position of a match to satisfy leftmost-first match semantics. When
+ /// matching in reverse, this means finding the longest possible match,
+ /// hence, this option.
+ ///
+ /// By default this is disabled.
+ pub fn longest_match(&mut self, yes: bool) -> &mut Builder {
+ // There is prior art in RE2 that shows how this can support unanchored
+ // searches. Instead of treating all NFA states as having equivalent
+ // priority, we instead group NFA states into sets, and treat members
+ // of each set as having equivalent priority, but having greater
+ // priority than all following members of different sets. We then
+ // essentially assign a higher priority to everything over the prefix
+ // `.*?`.
+ self.longest_match = yes;
+ self
+ }
+
+ /// Apply best effort heuristics to shrink the NFA at the expense of more
+ /// time/memory.
+ ///
+ /// This may be exposed in the future, but for now is exported for use in
+ /// the `regex-automata-debug` tool.
+ #[doc(hidden)]
+ pub fn shrink(&mut self, yes: bool) -> &mut Builder {
+ self.nfa.shrink(yes);
+ self
+ }
+}
+
+#[cfg(feature = "std")]
+impl Default for Builder {
+ fn default() -> Builder {
+ Builder::new()
+ }
+}
+
+/// Return the given byte as its escaped string form.
+#[cfg(feature = "std")]
+fn escape(b: u8) -> String {
+ use std::ascii;
+
+ String::from_utf8(ascii::escape_default(b).collect::<Vec<_>>()).unwrap()
+}
+
+#[cfg(all(test, feature = "std"))]
+mod tests {
+ use super::*;
+
+ #[test]
+ fn errors_when_converting_to_smaller_dfa() {
+ let pattern = r"\w{10}";
+ let dfa = Builder::new()
+ .byte_classes(false)
+ .anchored(true)
+ .premultiply(false)
+ .build_with_size::<u16>(pattern)
+ .unwrap();
+ assert!(dfa.to_u8().is_err());
+ }
+
+ #[test]
+ fn errors_when_determinization_would_overflow() {
+ let pattern = r"\w{10}";
+
+ let mut builder = Builder::new();
+ builder.byte_classes(false).anchored(true).premultiply(false);
+ // using u16 is fine
+ assert!(builder.build_with_size::<u16>(pattern).is_ok());
+ // // ... but u8 results in overflow (because there are >256 states)
+ assert!(builder.build_with_size::<u8>(pattern).is_err());
+ }
+
+ #[test]
+ fn errors_when_premultiply_would_overflow() {
+ let pattern = r"[a-z]";
+
+ let mut builder = Builder::new();
+ builder.byte_classes(false).anchored(true).premultiply(false);
+ // without premultiplication is OK
+ assert!(builder.build_with_size::<u8>(pattern).is_ok());
+ // ... but with premultiplication overflows u8
+ builder.premultiply(true);
+ assert!(builder.build_with_size::<u8>(pattern).is_err());
+ }
+
+ // let data = ::std::fs::read_to_string("/usr/share/dict/words").unwrap();
+ // let mut words: Vec<&str> = data.lines().collect();
+ // println!("{} words", words.len());
+ // words.sort_by(|w1, w2| w1.len().cmp(&w2.len()).reverse());
+ // let pattern = words.join("|");
+ // print_automata_counts(&pattern);
+ // print_automata(&pattern);
+
+ // print_automata(r"[01]*1[01]{5}");
+ // print_automata(r"X(.?){0,8}Y");
+ // print_automata_counts(r"\p{alphabetic}");
+ // print_automata(r"a*b+|cdefg");
+ // print_automata(r"(..)*(...)*");
+
+ // let pattern = r"\p{any}*?\p{Other_Uppercase}";
+ // let pattern = r"\p{any}*?\w+";
+ // print_automata_counts(pattern);
+ // print_automata_counts(r"(?-u:\w)");
+
+ // let pattern = r"\p{Greek}";
+ // let pattern = r"zZzZzZzZzZ";
+ // let pattern = grapheme_pattern();
+ // let pattern = r"\p{Ideographic}";
+ // let pattern = r"\w{10}"; // 51784 --> 41264
+ // let pattern = r"\w"; // 5182
+ // let pattern = r"a*";
+ // print_automata(pattern);
+ // let (_, _, dfa) = build_automata(pattern);
+}