regex_automata/

dense.rs

#[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);
}