Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1256 insertions, 0 deletions

diff --git a/vendor/regex-automata/src/sparse.rs b/vendor/regex-automata/src/sparse.rs
new file mode 100644
index 000000000..d18024b34
--- /dev/null
+++ b/vendor/regex-automata/src/sparse.rs
@@ -0,0 +1,1256 @@
+#[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
+}