src/sparse.rs

#[cfg(feature = "std")]
use core::fmt;
#[cfg(feature = "std")]
use core::iter;
use core::marker::PhantomData;
use core::mem::size_of;
#[cfg(feature = "std")]
use std::collections::HashMap;

#[cfg(feature = "std")]
use byteorder::{BigEndian, LittleEndian};
use byteorder::{ByteOrder, NativeEndian};

use classes::ByteClasses;
use dense;
use dfa::DFA;
#[cfg(feature = "std")]
use error::{Error, Result};
#[cfg(feature = "std")]
use state_id::{dead_id, usize_to_state_id, write_state_id_bytes, StateID};
#[cfg(not(feature = "std"))]
use state_id::{dead_id, StateID};

/// A sparse table-based deterministic finite automaton (DFA).
///
/// In contrast to a [dense DFA](enum.DenseDFA.html), a sparse DFA uses a
/// more space efficient representation for its transition table. Consequently,
/// sparse DFAs can use much less memory than dense DFAs, but this comes at a
/// price. In particular, reading the more space efficient transitions takes
/// more work, and consequently, searching using a sparse DFA is typically
/// slower than a dense DFA.
///
/// A sparse DFA can be built using the default configuration via the
/// [`SparseDFA::new`](enum.SparseDFA.html#method.new) constructor. Otherwise,
/// one can configure various aspects of a dense DFA via
/// [`dense::Builder`](dense/struct.Builder.html), and then convert a dense
/// DFA to a sparse DFA using
/// [`DenseDFA::to_sparse`](enum.DenseDFA.html#method.to_sparse).
///
/// In general, a sparse DFA supports all the same operations as a dense DFA.
///
/// Making the choice between a dense and sparse DFA depends on your specific
/// work load. If you can sacrifice a bit of search time performance, then a
/// sparse DFA might be the best choice. In particular, while sparse DFAs are
/// probably always slower than dense DFAs, you may find that they are easily
/// fast enough for your purposes!
///
/// # State size
///
/// A `SparseDFA` 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.SparseDFA.html#method.to_bytes_little_endian),
/// [`to_bytes_big_endian`](enum.SparseDFA.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<u8>` or `&[u8]`,
/// depending on where the transition table is stored. Note that this is
/// different than a dense DFA, whose transition table is typically
/// `Vec<S>` or `&[S]`. The reason for this is that a sparse DFA always reads
/// its transition table from raw bytes because the table is compactly packed.
///
/// # Variants
///
/// This DFA is defined as a non-exhaustive enumeration of different types of
/// dense DFAs. All of the variants 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
/// `ByteClass`.
///
/// # 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, SparseDFA};
///
/// # fn example() -> Result<(), regex_automata::Error> {
/// let dfa = SparseDFA::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 `SparseDFA` type directly. Namely, each implementation requires
/// a branch to determine which type of sparse 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 SparseDFA<T: AsRef<[u8]>, S: StateID = usize> {
    /// A standard DFA that does not use 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.
    ///
    /// Unlike dense DFAs, sparse DFAs do not tend to benefit nearly as much
    /// from using byte classes. In some cases, using byte classes can even
    /// marginally increase the size of a sparse DFA's transition table. The
    /// reason for this is that a sparse DFA already compacts each state's
    /// transitions separate from whether byte classes are used.
    ByteClass(ByteClass<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,
}

#[cfg(feature = "std")]
impl SparseDFA<Vec<u8>, usize> {
    /// Parse the given regular expression using a default configuration and
    /// return the corresponding sparse DFA.
    ///
    /// The default configuration uses `usize` for state IDs and reduces the
    /// alphabet size by splitting bytes into equivalence classes. The
    /// resulting 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, and then call
    /// [`DenseDFA::to_sparse`](enum.DenseDFA.html#method.to_sparse)
    /// to create a sparse DFA.
    ///
    /// # Example
    ///
    /// ```
    /// use regex_automata::{DFA, SparseDFA};
    ///
    /// # fn example() -> Result<(), regex_automata::Error> {
    /// let dfa = SparseDFA::new("foo[0-9]+bar")?;
    /// assert_eq!(Some(11), dfa.find(b"foo12345bar"));
    /// # Ok(()) }; example().unwrap()
    /// ```
    pub fn new(pattern: &str) -> Result<SparseDFA<Vec<u8>, usize>> {
        dense::Builder::new()
            .build(pattern)
            .and_then(|dense| dense.to_sparse())
    }
}

#[cfg(feature = "std")]
impl<S: StateID> SparseDFA<Vec<u8>, S> {
    /// Create a new empty sparse 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, SparseDFA};
    ///
    /// # fn example() -> Result<(), regex_automata::Error> {
    /// let dfa: SparseDFA<Vec<u8>, usize> = SparseDFA::empty();
    /// assert_eq!(None, dfa.find(b""));
    /// assert_eq!(None, dfa.find(b"foo"));
    /// # Ok(()) }; example().unwrap()
    /// ```
    pub fn empty() -> SparseDFA<Vec<u8>, S> {
        dense::DenseDFA::empty().to_sparse().unwrap()
    }

    pub(crate) fn from_dense_sized<T: AsRef<[S]>, A: StateID>(
        dfa: &dense::Repr<T, S>,
    ) -> Result<SparseDFA<Vec<u8>, A>> {
        Repr::from_dense_sized(dfa).map(|r| r.into_sparse_dfa())
    }
}

impl<T: AsRef<[u8]>, S: StateID> SparseDFA<T, S> {
    /// Cheaply return a borrowed version of this sparse DFA. Specifically, the
    /// DFA returned always uses `&[u8]` for its transition table while keeping
    /// the same state identifier representation.
    pub fn as_ref<'a>(&'a self) -> SparseDFA<&'a [u8], S> {
        match *self {
            SparseDFA::Standard(Standard(ref r)) => {
                SparseDFA::Standard(Standard(r.as_ref()))
            }
            SparseDFA::ByteClass(ByteClass(ref r)) => {
                SparseDFA::ByteClass(ByteClass(r.as_ref()))
            }
            SparseDFA::__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) -> SparseDFA<Vec<u8>, S> {
        match *self {
            SparseDFA::Standard(Standard(ref r)) => {
                SparseDFA::Standard(Standard(r.to_owned()))
            }
            SparseDFA::ByteClass(ByteClass(ref r)) => {
                SparseDFA::ByteClass(ByteClass(r.to_owned()))
            }
            SparseDFA::__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 typically 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::<SparseDFA>()`.
    pub fn memory_usage(&self) -> usize {
        self.repr().memory_usage()
    }

    fn repr(&self) -> &Repr<T, S> {
        match *self {
            SparseDFA::Standard(ref r) => &r.0,
            SparseDFA::ByteClass(ref r) => &r.0,
            SparseDFA::__Nonexhaustive => unreachable!(),
        }
    }
}

/// Routines for converting a sparse DFA to other representations, such as
/// smaller state identifiers or raw bytes suitable for persistent storage.
#[cfg(feature = "std")]
impl<T: AsRef<[u8]>, S: StateID> SparseDFA<T, S> {
    /// Create a new sparse 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<SparseDFA<Vec<u8>, u8>> {
        self.to_sized()
    }

    /// Create a new sparse 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<SparseDFA<Vec<u8>, u16>> {
        self.to_sized()
    }

    /// Create a new sparse 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<SparseDFA<Vec<u8>, u32>> {
        self.to_sized()
    }

    /// Create a new sparse 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<SparseDFA<Vec<u8>, u64>> {
        self.to_sized()
    }

    /// Create a new sparse 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
    /// [`DenseDFA::to_sparse_sized`](enum.DenseDFA.html#method.to_sparse_sized).
    /// In general, picking the appropriate size upon initial construction of
    /// a sparse DFA is preferred, since it will do the conversion in one
    /// step instead of two.
    pub fn to_sized<A: StateID>(&self) -> Result<SparseDFA<Vec<u8>, A>> {
        self.repr().to_sized().map(|r| r.into_sparse_dfa())
    }

    /// Serialize a sparse DFA to raw bytes 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 sparse DFA to raw bytes 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 sparse DFA to raw bytes 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> SparseDFA<&'a [u8], S> {
    /// Deserialize a sparse 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 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 sparse 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, SparseDFA};
    ///
    /// # fn example() -> Result<(), regex_automata::Error> {
    /// let sparse = SparseDFA::new("foo[0-9]+")?;
    /// let bytes = sparse.to_u16()?.to_bytes_native_endian()?;
    ///
    /// let dfa: SparseDFA<&[u8], u16> = unsafe {
    ///     SparseDFA::from_bytes(&bytes)
    /// };
    ///
    /// assert_eq!(Some(8), dfa.find(b"foo12345"));
    /// # Ok(()) }; example().unwrap()
    /// ```
    pub unsafe fn from_bytes(buf: &'a [u8]) -> SparseDFA<&'a [u8], S> {
        Repr::from_bytes(buf).into_sparse_dfa()
    }
}

impl<T: AsRef<[u8]>, S: StateID> DFA for SparseDFA<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 {
            SparseDFA::Standard(ref r) => r.next_state(current, input),
            SparseDFA::ByteClass(ref r) => r.next_state(current, input),
            SparseDFA::__Nonexhaustive => unreachable!(),
        }
    }

    #[inline]
    unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
        self.next_state(current, input)
    }

    // We specialize the following methods because it lets us lift the
    // case analysis between the different types of sparse DFAs. Instead of
    // doing the case analysis for every transition, we do it once before
    // searching. For sparse DFAs, this doesn't seem to benefit performance as
    // much as it does for the dense DFAs, but it's easy to do so we might as
    // well do it.

    #[inline]
    fn is_match_at(&self, bytes: &[u8], start: usize) -> bool {
        match *self {
            SparseDFA::Standard(ref r) => r.is_match_at(bytes, start),
            SparseDFA::ByteClass(ref r) => r.is_match_at(bytes, start),
            SparseDFA::__Nonexhaustive => unreachable!(),
        }
    }

    #[inline]
    fn shortest_match_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
        match *self {
            SparseDFA::Standard(ref r) => r.shortest_match_at(bytes, start),
            SparseDFA::ByteClass(ref r) => r.shortest_match_at(bytes, start),
            SparseDFA::__Nonexhaustive => unreachable!(),
        }
    }

    #[inline]
    fn find_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
        match *self {
            SparseDFA::Standard(ref r) => r.find_at(bytes, start),
            SparseDFA::ByteClass(ref r) => r.find_at(bytes, start),
            SparseDFA::__Nonexhaustive => unreachable!(),
        }
    }

    #[inline]
    fn rfind_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
        match *self {
            SparseDFA::Standard(ref r) => r.rfind_at(bytes, start),
            SparseDFA::ByteClass(ref r) => r.rfind_at(bytes, start),
            SparseDFA::__Nonexhaustive => unreachable!(),
        }
    }
}

/// A standard sparse DFA that does not use premultiplication or byte classes.
///
/// Generally, it isn't necessary to use this type directly, since a
/// `SparseDFA` 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<[u8]>, S: StateID = usize>(Repr<T, S>);

impl<T: AsRef<[u8]>, 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 {
        self.0.state(current).next(input)
    }

    #[inline]
    unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
        self.next_state(current, input)
    }
}

/// A sparse 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.
///
/// Unlike dense DFAs, sparse DFAs do not tend to benefit nearly as much from
/// using byte classes. In some cases, using byte classes can even marginally
/// increase the size of a sparse DFA's transition table. The reason for this
/// is that a sparse DFA already compacts each state's transitions separate
/// from whether byte classes are used.
///
/// Generally, it isn't necessary to use this type directly, since a
/// `SparseDFA` 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<[u8]>, S: StateID = usize>(Repr<T, S>);

impl<T: AsRef<[u8]>, 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);
        self.0.state(current).next(input)
    }

    #[inline]
    unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
        self.next_state(current, input)
    }
}

/// The underlying representation of a sparse DFA. This is shared by all of
/// the different variants of a sparse DFA.
#[derive(Clone)]
#[cfg_attr(not(feature = "std"), derive(Debug))]
struct Repr<T: AsRef<[u8]>, S: StateID = usize> {
    anchored: bool,
    start: S,
    state_count: usize,
    max_match: S,
    byte_classes: ByteClasses,
    trans: T,
}

impl<T: AsRef<[u8]>, S: StateID> Repr<T, S> {
    fn into_sparse_dfa(self) -> SparseDFA<T, S> {
        if self.byte_classes.is_singleton() {
            SparseDFA::Standard(Standard(self))
        } else {
            SparseDFA::ByteClass(ByteClass(self))
        }
    }

    fn as_ref<'a>(&'a self) -> Repr<&'a [u8], S> {
        Repr {
            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<u8>, S> {
        Repr {
            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 a convenient representation of the given state.
    ///
    /// This is marked as inline because it doesn't seem to get inlined
    /// otherwise, which leads to a fairly significant performance loss (~25%).
    #[inline]
    fn state<'a>(&'a self, id: S) -> State<'a, S> {
        let mut pos = id.to_usize();
        let ntrans = NativeEndian::read_u16(&self.trans()[pos..]) as usize;
        pos += 2;
        let input_ranges = &self.trans()[pos..pos + (ntrans * 2)];
        pos += 2 * ntrans;
        let next = &self.trans()[pos..pos + (ntrans * size_of::<S>())];
        State { _state_id_repr: PhantomData, ntrans, input_ranges, next }
    }

    /// Return an iterator over all of the states in this DFA.
    ///
    /// The iterator returned yields tuples, where the first element is the
    /// state ID and the second element is the state itself.
    #[cfg(feature = "std")]
    fn states<'a>(&'a self) -> StateIter<'a, T, S> {
        StateIter { dfa: self, id: dead_id() }
    }

    fn memory_usage(&self) -> usize {
        self.trans().len()
    }

    fn start_state(&self) -> S {
        self.start
    }

    fn is_match_state(&self, id: S) -> bool {
        self.is_match_or_dead_state(id) && !self.is_dead_state(id)
    }

    fn is_dead_state(&self, id: S) -> bool {
        id == dead_id()
    }

    fn is_match_or_dead_state(&self, id: S) -> bool {
        id <= self.max_match
    }

    fn is_anchored(&self) -> bool {
        self.anchored
    }

    fn trans(&self) -> &[u8] {
        self.trans.as_ref()
    }

    /// Create a new sparse 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")]
    fn to_sized<A: StateID>(&self) -> Result<Repr<Vec<u8>, A>> {
        // To build the new DFA, we proceed much like the initial construction
        // of the sparse DFA. Namely, since the state ID size is changing,
        // we don't actually know all of our state IDs until we've allocated
        // all necessary space. So we do one pass that allocates all of the
        // storage we need, and then another pass to fill in the transitions.

        let mut trans = Vec::with_capacity(size_of::<A>() * self.state_count);
        let mut map: HashMap<S, A> = HashMap::with_capacity(self.state_count);
        for (old_id, state) in self.states() {
            let pos = trans.len();
            map.insert(old_id, usize_to_state_id(pos)?);

            let n = state.ntrans;
            let zeros = 2 + (n * 2) + (n * size_of::<A>());
            trans.extend(iter::repeat(0).take(zeros));

            NativeEndian::write_u16(&mut trans[pos..], n as u16);
            let (s, e) = (pos + 2, pos + 2 + (n * 2));
            trans[s..e].copy_from_slice(state.input_ranges);
        }

        let mut new = Repr {
            anchored: self.anchored,
            start: map[&self.start],
            state_count: self.state_count,
            max_match: map[&self.max_match],
            byte_classes: self.byte_classes.clone(),
            trans,
        };
        for (&old_id, &new_id) in map.iter() {
            let old_state = self.state(old_id);
            let mut new_state = new.state_mut(new_id);
            for i in 0..new_state.ntrans {
                let next = map[&old_state.next_at(i)];
                new_state.set_next_at(i, usize_to_state_id(next.to_usize())?);
            }
        }
        new.start = map[&self.start];
        new.max_match = map[&self.max_match];
        Ok(new)
    }

    /// Serialize a sparse DFA to raw bytes using the provided endianness.
    ///
    /// 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.
    ///
    /// Unlike dense DFAs, the result is not necessarily aligned since a
    /// sparse DFA's transition table is always read as a sequence of bytes.
    #[cfg(feature = "std")]
    fn to_bytes<A: ByteOrder>(&self) -> Result<Vec<u8>> {
        let label = b"rust-regex-automata-sparse-dfa\x00";
        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. (Currently unused.)
            + 2
            // For start state.
            + 8
            // For state count.
            + 8
            // For max match state.
            + 8
            // For byte class map.
            + 256
            // For transition table.
            + self.trans().len();

        let mut i = 0;
        let mut buf = vec![0; size];

        // 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 = 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.anchored {
            options |= dense::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 (_, state) in self.states() {
            A::write_u16(&mut buf[i..], state.ntrans as u16);
            i += 2;
            buf[i..i + (state.ntrans * 2)].copy_from_slice(state.input_ranges);
            i += state.ntrans * 2;
            for j in 0..state.ntrans {
                write_state_id_bytes::<A, _>(&mut buf[i..], state.next_at(j));
                i += size_of::<S>();
            }
        }

        assert_eq!(size, i, "expected to consume entire buffer");

        Ok(buf)
    }
}

impl<'a, S: StateID> Repr<&'a [u8], S> {
    /// The implementation for deserializing a sparse DFA from raw bytes.
    unsafe fn from_bytes(mut buf: &'a [u8]) -> Repr<&'a [u8], 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 SparseDFA 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 != size_of::<S>() {
            panic!(
                "state size of SparseDFA ({}) does not match \
                 requested state size ({})",
                state_size,
                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..];

        Repr {
            anchored: opts & dense::MASK_ANCHORED > 0,
            start,
            state_count,
            max_match,
            byte_classes,
            trans: buf,
        }
    }
}

#[cfg(feature = "std")]
impl<S: StateID> Repr<Vec<u8>, S> {
    /// The implementation for constructing a sparse DFA from a dense DFA.
    fn from_dense_sized<T: AsRef<[S]>, A: StateID>(
        dfa: &dense::Repr<T, S>,
    ) -> Result<Repr<Vec<u8>, A>> {
        // In order to build the transition table, we need to be able to write
        // state identifiers for each of the "next" transitions in each state.
        // Our state identifiers correspond to the byte offset in the
        // transition table at which the state is encoded. Therefore, we do not
        // actually know what the state identifiers are until we've allocated
        // exactly as much space as we need for each state. Thus, construction
        // of the transition table happens in two passes.
        //
        // In the first pass, we fill out the shell of each state, which
        // includes the transition count, the input byte ranges and zero-filled
        // space for the transitions. In this first pass, we also build up a
        // map from the state identifier index of the dense DFA to the state
        // identifier in this sparse DFA.
        //
        // In the second pass, we fill in the transitions based on the map
        // built in the first pass.

        let mut trans = Vec::with_capacity(size_of::<A>() * dfa.state_count());
        let mut remap: Vec<A> = vec![dead_id(); dfa.state_count()];
        for (old_id, state) in dfa.states() {
            let pos = trans.len();

            remap[dfa.state_id_to_index(old_id)] = usize_to_state_id(pos)?;
            // zero-filled space for the transition count
            trans.push(0);
            trans.push(0);

            let mut trans_count = 0;
            for (b1, b2, _) in state.sparse_transitions() {
                trans_count += 1;
                trans.push(b1);
                trans.push(b2);
            }
            // fill in the transition count
            NativeEndian::write_u16(&mut trans[pos..], trans_count);

            // zero-fill the actual transitions
            let zeros = trans_count as usize * size_of::<A>();
            trans.extend(iter::repeat(0).take(zeros));
        }

        let mut new = Repr {
            anchored: dfa.is_anchored(),
            start: remap[dfa.state_id_to_index(dfa.start_state())],
            state_count: dfa.state_count(),
            max_match: remap[dfa.state_id_to_index(dfa.max_match_state())],
            byte_classes: dfa.byte_classes().clone(),
            trans,
        };
        for (old_id, old_state) in dfa.states() {
            let new_id = remap[dfa.state_id_to_index(old_id)];
            let mut new_state = new.state_mut(new_id);
            let sparse = old_state.sparse_transitions();
            for (i, (_, _, next)) in sparse.enumerate() {
                let next = remap[dfa.state_id_to_index(next)];
                new_state.set_next_at(i, next);
            }
        }
        Ok(new)
    }

    /// Return a convenient mutable representation of the given state.
    fn state_mut<'a>(&'a mut self, id: S) -> StateMut<'a, S> {
        let mut pos = id.to_usize();
        let ntrans = NativeEndian::read_u16(&self.trans[pos..]) as usize;
        pos += 2;

        let size = (ntrans * 2) + (ntrans * size_of::<S>());
        let ranges_and_next = &mut self.trans[pos..pos + size];
        let (input_ranges, next) = ranges_and_next.split_at_mut(ntrans * 2);
        StateMut { _state_id_repr: PhantomData, ntrans, input_ranges, next }
    }
}

#[cfg(feature = "std")]
impl<T: AsRef<[u8]>, S: StateID> fmt::Debug for Repr<T, S> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fn state_status<T: AsRef<[u8]>, 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, "SparseDFA(")?;
        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 sparse DFA.
///
/// This iterator yields tuples, where the first element is the state ID and
/// the second element is the state itself.
#[cfg(feature = "std")]
#[derive(Debug)]
struct StateIter<'a, T: AsRef<[u8]> + 'a, S: StateID + 'a = usize> {
    dfa: &'a Repr<T, S>,
    id: S,
}

#[cfg(feature = "std")]
impl<'a, T: AsRef<[u8]>, S: StateID> Iterator for StateIter<'a, T, S> {
    type Item = (S, State<'a, S>);

    fn next(&mut self) -> Option<(S, State<'a, S>)> {
        if self.id.to_usize() >= self.dfa.trans().len() {
            return None;
        }
        let id = self.id;
        let state = self.dfa.state(id);
        self.id = S::from_usize(self.id.to_usize() + state.bytes());
        Some((id, state))
    }
}

/// A representation of a sparse DFA state that can be cheaply materialized
/// from a state identifier.
#[derive(Clone)]
struct State<'a, S: StateID = usize> {
    /// The state identifier representation used by the DFA from which this
    /// state was extracted. Since our transition table is compacted in a
    /// &[u8], we don't actually use the state ID type parameter explicitly
    /// anywhere, so we fake it. This prevents callers from using an incorrect
    /// state ID representation to read from this state.
    _state_id_repr: PhantomData<S>,
    /// The number of transitions in this state.
    ntrans: usize,
    /// Pairs of input ranges, where there is one pair for each transition.
    /// Each pair specifies an inclusive start and end byte range for the
    /// corresponding transition.
    input_ranges: &'a [u8],
    /// Transitions to the next state. This slice contains native endian
    /// encoded state identifiers, with `S` as the representation. Thus, there
    /// are `ntrans * size_of::<S>()` bytes in this slice.
    next: &'a [u8],
}

impl<'a, S: StateID> State<'a, S> {
    /// Searches for the next transition given an input byte. If no such
    /// transition could be found, then a dead state is returned.
    fn next(&self, input: u8) -> S {
        // This straight linear search was observed to be much better than
        // binary search on ASCII haystacks, likely because a binary search
        // visits the ASCII case last but a linear search sees it first. A
        // binary search does do a little better on non-ASCII haystacks, but
        // not by much. There might be a better trade off lurking here.
        for i in 0..self.ntrans {
            let (start, end) = self.range(i);
            if start <= input && input <= end {
                return self.next_at(i);
            }
            // We could bail early with an extra branch: if input < b1, then
            // we know we'll never find a matching transition. Interestingly,
            // this extra branch seems to not help performance, or will even
            // hurt it. It's likely very dependent on the DFA itself and what
            // is being searched.
        }
        dead_id()
    }

    /// Returns the inclusive input byte range for the ith transition in this
    /// state.
    fn range(&self, i: usize) -> (u8, u8) {
        (self.input_ranges[i * 2], self.input_ranges[i * 2 + 1])
    }

    /// Returns the next state for the ith transition in this state.
    fn next_at(&self, i: usize) -> S {
        S::read_bytes(&self.next[i * size_of::<S>()..])
    }

    /// Return the total number of bytes that this state consumes in its
    /// encoded form.
    #[cfg(feature = "std")]
    fn bytes(&self) -> usize {
        2 + (self.ntrans * 2) + (self.ntrans * size_of::<S>())
    }
}

#[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 i in 0..self.ntrans {
            let next = self.next_at(i);
            if next == dead_id() {
                continue;
            }

            let (start, end) = self.range(i);
            if start == end {
                transitions.push(format!(
                    "{} => {}",
                    escape(start),
                    next.to_usize()
                ));
            } else {
                transitions.push(format!(
                    "{}-{} => {}",
                    escape(start),
                    escape(end),
                    next.to_usize(),
                ));
            }
        }
        write!(f, "{}", transitions.join(", "))
    }
}

/// A representation of a mutable sparse DFA state that can be cheaply
/// materialized from a state identifier.
#[cfg(feature = "std")]
struct StateMut<'a, S: StateID = usize> {
    /// The state identifier representation used by the DFA from which this
    /// state was extracted. Since our transition table is compacted in a
    /// &[u8], we don't actually use the state ID type parameter explicitly
    /// anywhere, so we fake it. This prevents callers from using an incorrect
    /// state ID representation to read from this state.
    _state_id_repr: PhantomData<S>,
    /// The number of transitions in this state.
    ntrans: usize,
    /// Pairs of input ranges, where there is one pair for each transition.
    /// Each pair specifies an inclusive start and end byte range for the
    /// corresponding transition.
    input_ranges: &'a mut [u8],
    /// Transitions to the next state. This slice contains native endian
    /// encoded state identifiers, with `S` as the representation. Thus, there
    /// are `ntrans * size_of::<S>()` bytes in this slice.
    next: &'a mut [u8],
}

#[cfg(feature = "std")]
impl<'a, S: StateID> StateMut<'a, S> {
    /// Sets the ith transition to the given state.
    fn set_next_at(&mut self, i: usize, next: S) {
        next.write_bytes(&mut self.next[i * size_of::<S>()..]);
    }
}

#[cfg(feature = "std")]
impl<'a, S: StateID> fmt::Debug for StateMut<'a, S> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let state = State {
            _state_id_repr: self._state_id_repr,
            ntrans: self.ntrans,
            input_ranges: self.input_ranges,
            next: self.next,
        };
        fmt::Debug::fmt(&state, f)
    }
}

/// 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()
}

/// A binary search routine specialized specifically to a sparse DFA state's
/// transitions. Specifically, the transitions are defined as a set of pairs
/// of input bytes that delineate an inclusive range of bytes. If the input
/// byte is in the range, then the corresponding transition is a match.
///
/// This binary search accepts a slice of these pairs and returns the position
/// of the matching pair (the ith transition), or None if no matching pair
/// could be found.
///
/// Note that this routine is not currently used since it was observed to
/// either decrease performance when searching ASCII, or did not provide enough
/// of a boost on non-ASCII haystacks to be worth it. However, we leave it here
/// for posterity in case we can find a way to use it.
///
/// In theory, we could use the standard library's search routine if we could
/// cast a `&[u8]` to a `&[(u8, u8)]`, but I don't believe this is currently
/// guaranteed to be safe and is thus UB (since I don't think the in-memory
/// representation of `(u8, u8)` has been nailed down).
#[inline(always)]
#[allow(dead_code)]
fn binary_search_ranges(ranges: &[u8], needle: u8) -> Option<usize> {
    debug_assert!(ranges.len() % 2 == 0, "ranges must have even length");
    debug_assert!(ranges.len() <= 512, "ranges should be short");

    let (mut left, mut right) = (0, ranges.len() / 2);
    while left < right {
        let mid = (left + right) / 2;
        let (b1, b2) = (ranges[mid * 2], ranges[mid * 2 + 1]);
        if needle < b1 {
            right = mid;
        } else if needle > b2 {
            left = mid + 1;
        } else {
            return Some(mid);
        }
    }
    None
}