Quelle  sparse.rs   Sprache: unbekannt

/*!
Types and routines specific to sparse DFAs.

This module is the home of [`sparse::DFA`](DFA).

Unlike the [`dense`](super::dense) module, this module does not contain a
builder or configuration specific for sparse DFAs. Instead, the intended
way to build a sparse DFA is either by using a default configuration with
its constructor [`sparse::DFA::new`](DFA::new), or by first configuring the
construction of a dense DFA with [`dense::Builder`](super::dense::Builder)
and then calling [`dense::DFA::to_sparse`](super::dense::DFA::to_sparse). For
example, this configures a sparse DFA to do an overlapping search:

```
use regex_automata::{
    dfa::{Automaton, OverlappingState, dense},
    HalfMatch, Input, MatchKind,
};

let dense_re = dense::Builder::new()
    .configure(dense::Config::new().match_kind(MatchKind::All))
    .build(r"Samwise|Sam")?;
let sparse_re = dense_re.to_sparse()?;

// Setup our haystack and initial start state.
let input = Input::new("Samwise");
let mut state = OverlappingState::start();

// First, 'Sam' will match.
sparse_re.try_search_overlapping_fwd(&input, &mut state)?;
assert_eq!(Some(HalfMatch::must(0, 3)), state.get_match());

// And now 'Samwise' will match.
sparse_re.try_search_overlapping_fwd(&input, &mut state)?;
assert_eq!(Some(HalfMatch::must(0, 7)), state.get_match());
# Ok::<(), Box<dyn std::error::Error>>(())
```
*/

#[cfg(feature = "dfa-build")]
use core::iter;
use core::{
    convert::{TryFrom, TryInto},
    fmt,
    mem::size_of,
};

#[cfg(feature = "dfa-build")]
use alloc::{vec, vec::Vec};

#[cfg(feature = "dfa-build")]
use crate::dfa::dense::{self, BuildError};
use crate::{
    dfa::{
        automaton::{fmt_state_indicator, Automaton},
        dense::Flags,
        special::Special,
        StartKind, DEAD,
    },
    util::{
        alphabet::{ByteClasses, ByteSet},
        escape::DebugByte,
        int::{Pointer, Usize, U16, U32},
        prefilter::Prefilter,
        primitives::{PatternID, StateID},
        search::{Anchored, Input, MatchError},
        start::{Start, StartByteMap},
        wire::{self, DeserializeError, Endian, SerializeError},
    },
};

const LABEL: &str = "rust-regex-automata-dfa-sparse";
const VERSION: u32 = 2;

/// A sparse deterministic finite automaton (DFA) with variable sized states.
///
/// In contrast to a [dense::DFA](crate::dfa::dense::DFA), a sparse DFA uses
/// a more space efficient representation for its transitions. Consequently,
/// sparse DFAs may 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
/// [`DFA::new`] constructor. Otherwise, one can configure various aspects
/// of a dense DFA via [`dense::Builder`](crate::dfa::dense::Builder),
/// and then convert a dense DFA to a sparse DFA using
/// [`dense::DFA::to_sparse`](crate::dfa::dense::DFA::to_sparse).
///
/// In general, a sparse DFA supports all the same search 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!
///
/// # Type parameters
///
/// A `DFA` has one type parameter, `T`, which is used to represent the parts
/// of a sparse DFA. `T` is typically a `Vec<u8>` or a `&[u8]`.
///
/// # The `Automaton` trait
///
/// This type implements the [`Automaton`] trait, which means it can be used
/// for searching. For example:
///
/// ```
/// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
///
/// let dfa = DFA::new("foo[0-9]+")?;
/// let expected = Some(HalfMatch::must(0, 8));
/// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(Clone)]
pub struct DFA<T> {
    // When compared to a dense DFA, a sparse DFA *looks* a lot simpler
    // representation-wise. In reality, it is perhaps more complicated. Namely,
    // in a dense DFA, all information needs to be very cheaply accessible
    // using only state IDs. In a sparse DFA however, each state uses a
    // variable amount of space because each state encodes more information
    // than just its transitions. Each state also includes an accelerator if
    // one exists, along with the matching pattern IDs if the state is a match
    // state.
    //
    // That is, a lot of the complexity is pushed down into how each state
    // itself is represented.
    tt: Transitions<T>,
    st: StartTable<T>,
    special: Special,
    pre: Option<Prefilter>,
    quitset: ByteSet,
    flags: Flags,
}

#[cfg(feature = "dfa-build")]
impl DFA<Vec<u8>> {
    /// Parse the given regular expression using a default configuration and
    /// return the corresponding sparse DFA.
    ///
    /// If you want a non-default configuration, then use
    /// the [`dense::Builder`](crate::dfa::dense::Builder)
    /// to set your own configuration, and then call
    /// [`dense::DFA::to_sparse`](crate::dfa::dense::DFA::to_sparse) to create
    /// a sparse DFA.
    ///
    /// # Example
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse}, HalfMatch, Input};
    ///
    /// let dfa = sparse::DFA::new("foo[0-9]+bar")?;
    ///
    /// let expected = Some(HalfMatch::must(0, 11));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345bar"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "syntax")]
    pub fn new(pattern: &str) -> Result<DFA<Vec<u8>>, BuildError> {
        dense::Builder::new()
            .build(pattern)
            .and_then(|dense| dense.to_sparse())
    }

    /// Parse the given regular expressions using a default configuration and
    /// return the corresponding multi-DFA.
    ///
    /// If you want a non-default configuration, then use
    /// the [`dense::Builder`](crate::dfa::dense::Builder)
    /// to set your own configuration, and then call
    /// [`dense::DFA::to_sparse`](crate::dfa::dense::DFA::to_sparse) to create
    /// a sparse DFA.
    ///
    /// # Example
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse}, HalfMatch, Input};
    ///
    /// let dfa = sparse::DFA::new_many(&["[0-9]+", "[a-z]+"])?;
    /// let expected = Some(HalfMatch::must(1, 3));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345bar"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "syntax")]
    pub fn new_many<P: AsRef<str>>(
        patterns: &[P],
    ) -> Result<DFA<Vec<u8>>, BuildError> {
        dense::Builder::new()
            .build_many(patterns)
            .and_then(|dense| dense.to_sparse())
    }
}

#[cfg(feature = "dfa-build")]
impl DFA<Vec<u8>> {
    /// Create a new DFA that matches every input.
    ///
    /// # Example
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, sparse},
    ///     HalfMatch, Input,
    /// };
    ///
    /// let dfa = sparse::DFA::always_match()?;
    ///
    /// let expected = Some(HalfMatch::must(0, 0));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new(""))?);
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn always_match() -> Result<DFA<Vec<u8>>, BuildError> {
        dense::DFA::always_match()?.to_sparse()
    }

    /// Create a new sparse DFA that never matches any input.
    ///
    /// # Example
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse}, Input};
    ///
    /// let dfa = sparse::DFA::never_match()?;
    /// assert_eq!(None, dfa.try_search_fwd(&Input::new(""))?);
    /// assert_eq!(None, dfa.try_search_fwd(&Input::new("foo"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn never_match() -> Result<DFA<Vec<u8>>, BuildError> {
        dense::DFA::never_match()?.to_sparse()
    }

    /// The implementation for constructing a sparse DFA from a dense DFA.
    pub(crate) fn from_dense<T: AsRef<[u32]>>(
        dfa: &dense::DFA<T>,
    ) -> Result<DFA<Vec<u8>>, BuildError> {
        // 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 length, the input byte ranges and
        // zero-filled space for the transitions and accelerators, if present.
        // 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.

        // The capacity given here reflects a minimum. (Well, the true minimum
        // is likely even bigger, but hopefully this saves a few reallocs.)
        let mut sparse = Vec::with_capacity(StateID::SIZE * dfa.state_len());
        // This maps state indices from the dense DFA to StateIDs in the sparse
        // DFA. We build out this map on the first pass, and then use it in the
        // second pass to back-fill our transitions.
        let mut remap: Vec<StateID> = vec![DEAD; dfa.state_len()];
        for state in dfa.states() {
            let pos = sparse.len();

            remap[dfa.to_index(state.id())] = StateID::new(pos)
                .map_err(|_| BuildError::too_many_states())?;
            // zero-filled space for the transition length
            sparse.push(0);
            sparse.push(0);

            let mut transition_len = 0;
            for (unit1, unit2, _) in state.sparse_transitions() {
                match (unit1.as_u8(), unit2.as_u8()) {
                    (Some(b1), Some(b2)) => {
                        transition_len += 1;
                        sparse.push(b1);
                        sparse.push(b2);
                    }
                    (None, None) => {}
                    (Some(_), None) | (None, Some(_)) => {
                        // can never occur because sparse_transitions never
                        // groups EOI with any other transition.
                        unreachable!()
                    }
                }
            }
            // Add dummy EOI transition. This is never actually read while
            // searching, but having space equivalent to the total number
            // of transitions is convenient. Otherwise, we'd need to track
            // a different number of transitions for the byte ranges as for
            // the 'next' states.
            //
            // N.B. The loop above is not guaranteed to yield the EOI
            // transition, since it may point to a DEAD state. By putting
            // it here, we always write the EOI transition, and thus
            // guarantee that our transition length is >0. Why do we always
            // need the EOI transition? Because in order to implement
            // Automaton::next_eoi_state, this lets us just ask for the last
            // transition. There are probably other/better ways to do this.
            transition_len += 1;
            sparse.push(0);
            sparse.push(0);

            // Check some assumptions about transition length.
            assert_ne!(
                transition_len, 0,
                "transition length should be non-zero",
            );
            assert!(
                transition_len <= 257,
                "expected transition length {} to be <= 257",
                transition_len,
            );

            // Fill in the transition length.
            // Since transition length is always <= 257, we use the most
            // significant bit to indicate whether this is a match state or
            // not.
            let ntrans = if dfa.is_match_state(state.id()) {
                transition_len | (1 << 15)
            } else {
                transition_len
            };
            wire::NE::write_u16(ntrans, &mut sparse[pos..]);

            // zero-fill the actual transitions.
            // Unwraps are OK since transition_length <= 257 and our minimum
            // support usize size is 16-bits.
            let zeros = usize::try_from(transition_len)
                .unwrap()
                .checked_mul(StateID::SIZE)
                .unwrap();
            sparse.extend(iter::repeat(0).take(zeros));

            // If this is a match state, write the pattern IDs matched by this
            // state.
            if dfa.is_match_state(state.id()) {
                let plen = dfa.match_pattern_len(state.id());
                // Write the actual pattern IDs with a u32 length prefix.
                // First, zero-fill space.
                let mut pos = sparse.len();
                // Unwraps are OK since it's guaranteed that plen <=
                // PatternID::LIMIT, which is in turn guaranteed to fit into a
                // u32.
                let zeros = size_of::<u32>()
                    .checked_mul(plen)
                    .unwrap()
                    .checked_add(size_of::<u32>())
                    .unwrap();
                sparse.extend(iter::repeat(0).take(zeros));

                // Now write the length prefix.
                wire::NE::write_u32(
                    // Will never fail since u32::MAX is invalid pattern ID.
                    // Thus, the number of pattern IDs is representable by a
                    // u32.
                    plen.try_into().expect("pattern ID length fits in u32"),
                    &mut sparse[pos..],
                );
                pos += size_of::<u32>();

                // Now write the pattern IDs.
                for &pid in dfa.pattern_id_slice(state.id()) {
                    pos += wire::write_pattern_id::<wire::NE>(
                        pid,
                        &mut sparse[pos..],
                    );
                }
            }

            // And now add the accelerator, if one exists. An accelerator is
            // at most 4 bytes and at least 1 byte. The first byte is the
            // length, N. N bytes follow the length. The set of bytes that
            // follow correspond (exhaustively) to the bytes that must be seen
            // to leave this state.
            let accel = dfa.accelerator(state.id());
            sparse.push(accel.len().try_into().unwrap());
            sparse.extend_from_slice(accel);
        }

        let mut new = DFA {
            tt: Transitions {
                sparse,
                classes: dfa.byte_classes().clone(),
                state_len: dfa.state_len(),
                pattern_len: dfa.pattern_len(),
            },
            st: StartTable::from_dense_dfa(dfa, &remap)?,
            special: dfa.special().remap(|id| remap[dfa.to_index(id)]),
            pre: dfa.get_prefilter().map(|p| p.clone()),
            quitset: dfa.quitset().clone(),
            flags: dfa.flags().clone(),
        };
        // And here's our second pass. Iterate over all of the dense states
        // again, and update the transitions in each of the states in the
        // sparse DFA.
        for old_state in dfa.states() {
            let new_id = remap[dfa.to_index(old_state.id())];
            let mut new_state = new.tt.state_mut(new_id);
            let sparse = old_state.sparse_transitions();
            for (i, (_, _, next)) in sparse.enumerate() {
                let next = remap[dfa.to_index(next)];
                new_state.set_next_at(i, next);
            }
        }
        debug!(
            "created sparse DFA, memory usage: {} (dense memory usage: {})",
            new.memory_usage(),
            dfa.memory_usage(),
        );
        Ok(new)
    }
}

impl<T: AsRef<[u8]>> DFA<T> {
    /// Cheaply return a borrowed version of this sparse DFA. Specifically, the
    /// DFA returned always uses `&[u8]` for its transitions.
    pub fn as_ref<'a>(&'a self) -> DFA<&'a [u8]> {
        DFA {
            tt: self.tt.as_ref(),
            st: self.st.as_ref(),
            special: self.special,
            pre: self.pre.clone(),
            quitset: self.quitset,
            flags: self.flags,
        }
    }

    /// Return an owned version of this sparse DFA. Specifically, the DFA
    /// returned always uses `Vec<u8>` for its transitions.
    ///
    /// Effectively, this returns a sparse DFA whose transitions live on the
    /// heap.
    #[cfg(feature = "alloc")]
    pub fn to_owned(&self) -> DFA<alloc::vec::Vec<u8>> {
        DFA {
            tt: self.tt.to_owned(),
            st: self.st.to_owned(),
            special: self.special,
            pre: self.pre.clone(),
            quitset: self.quitset,
            flags: self.flags,
        }
    }

    /// Returns the starting state configuration for this DFA.
    ///
    /// The default is [`StartKind::Both`], which means the DFA supports both
    /// unanchored and anchored searches. However, this can generally lead to
    /// bigger DFAs. Therefore, a DFA might be compiled with support for just
    /// unanchored or anchored searches. In that case, running a search with
    /// an unsupported configuration will panic.
    pub fn start_kind(&self) -> StartKind {
        self.st.kind
    }

    /// Returns true only if this DFA has starting states for each pattern.
    ///
    /// When a DFA has starting states for each pattern, then a search with the
    /// DFA can be configured to only look for anchored matches of a specific
    /// pattern. Specifically, APIs like [`Automaton::try_search_fwd`] can
    /// accept a [`Anchored::Pattern`] if and only if this method returns true.
    /// Otherwise, an error will be returned.
    ///
    /// Note that if the DFA is empty, this always returns false.
    pub fn starts_for_each_pattern(&self) -> bool {
        self.st.pattern_len.is_some()
    }

    /// Returns the equivalence classes that make up the alphabet for this DFA.
    ///
    /// Unless [`dense::Config::byte_classes`] was disabled, it is possible
    /// that multiple distinct bytes are grouped into the same equivalence
    /// class if it is impossible for them to discriminate between a match and
    /// a non-match. This has the effect of reducing the overall alphabet size
    /// and in turn potentially substantially reducing the size of the DFA's
    /// transition table.
    ///
    /// The downside of using equivalence classes like this is that every state
    /// transition will automatically use this map to convert an arbitrary
    /// byte to its corresponding equivalence class. In practice this has a
    /// negligible impact on performance.
    pub fn byte_classes(&self) -> &ByteClasses {
        &self.tt.classes
    }

    /// Returns the memory usage, in bytes, of this DFA.
    ///
    /// The memory usage is computed based on the number of bytes used to
    /// represent this DFA.
    ///
    /// This does **not** include the stack size used up by this DFA. To
    /// compute that, use `std::mem::size_of::<sparse::DFA>()`.
    pub fn memory_usage(&self) -> usize {
        self.tt.memory_usage() + self.st.memory_usage()
    }
}

/// Routines for converting a sparse DFA to other representations, such as raw
/// bytes suitable for persistent storage.
impl<T: AsRef<[u8]>> DFA<T> {
    /// Serialize this DFA as raw bytes to a `Vec<u8>` in little endian
    /// format.
    ///
    /// The written bytes are guaranteed to be deserialized correctly and
    /// without errors in a semver compatible release of this crate by a
    /// `DFA`'s deserialization APIs (assuming all other criteria for the
    /// deserialization APIs has been satisfied):
    ///
    /// * [`DFA::from_bytes`]
    /// * [`DFA::from_bytes_unchecked`]
    ///
    /// Note that unlike a [`dense::DFA`](crate::dfa::dense::DFA)'s
    /// serialization methods, this does not add any initial padding to the
    /// returned bytes. Padding isn't required for sparse DFAs since they have
    /// no alignment requirements.
    ///
    /// # Example
    ///
    /// This example shows how to serialize and deserialize a DFA:
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// // Compile our original DFA.
    /// let original_dfa = DFA::new("foo[0-9]+")?;
    ///
    /// // N.B. We use native endianness here to make the example work, but
    /// // using to_bytes_little_endian would work on a little endian target.
    /// let buf = original_dfa.to_bytes_native_endian();
    /// // Even if buf has initial padding, DFA::from_bytes will automatically
    /// // ignore it.
    /// let dfa: DFA<&[u8]> = DFA::from_bytes(&buf)?.0;
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "dfa-build")]
    pub fn to_bytes_little_endian(&self) -> Vec<u8> {
        self.to_bytes::<wire::LE>()
    }

    /// Serialize this DFA as raw bytes to a `Vec<u8>` in big endian
    /// format.
    ///
    /// The written bytes are guaranteed to be deserialized correctly and
    /// without errors in a semver compatible release of this crate by a
    /// `DFA`'s deserialization APIs (assuming all other criteria for the
    /// deserialization APIs has been satisfied):
    ///
    /// * [`DFA::from_bytes`]
    /// * [`DFA::from_bytes_unchecked`]
    ///
    /// Note that unlike a [`dense::DFA`](crate::dfa::dense::DFA)'s
    /// serialization methods, this does not add any initial padding to the
    /// returned bytes. Padding isn't required for sparse DFAs since they have
    /// no alignment requirements.
    ///
    /// # Example
    ///
    /// This example shows how to serialize and deserialize a DFA:
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// // Compile our original DFA.
    /// let original_dfa = DFA::new("foo[0-9]+")?;
    ///
    /// // N.B. We use native endianness here to make the example work, but
    /// // using to_bytes_big_endian would work on a big endian target.
    /// let buf = original_dfa.to_bytes_native_endian();
    /// // Even if buf has initial padding, DFA::from_bytes will automatically
    /// // ignore it.
    /// let dfa: DFA<&[u8]> = DFA::from_bytes(&buf)?.0;
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "dfa-build")]
    pub fn to_bytes_big_endian(&self) -> Vec<u8> {
        self.to_bytes::<wire::BE>()
    }

    /// Serialize this DFA as raw bytes to a `Vec<u8>` in native endian
    /// format.
    ///
    /// The written bytes are guaranteed to be deserialized correctly and
    /// without errors in a semver compatible release of this crate by a
    /// `DFA`'s deserialization APIs (assuming all other criteria for the
    /// deserialization APIs has been satisfied):
    ///
    /// * [`DFA::from_bytes`]
    /// * [`DFA::from_bytes_unchecked`]
    ///
    /// Note that unlike a [`dense::DFA`](crate::dfa::dense::DFA)'s
    /// serialization methods, this does not add any initial padding to the
    /// returned bytes. Padding isn't required for sparse DFAs since they have
    /// no alignment requirements.
    ///
    /// Generally speaking, native endian format should only be used when
    /// you know that the target you're compiling the DFA for matches the
    /// endianness of the target on which you're compiling DFA. For example,
    /// if serialization and deserialization happen in the same process or on
    /// the same machine. Otherwise, when serializing a DFA for use in a
    /// portable environment, you'll almost certainly want to serialize _both_
    /// a little endian and a big endian version and then load the correct one
    /// based on the target's configuration.
    ///
    /// # Example
    ///
    /// This example shows how to serialize and deserialize a DFA:
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// // Compile our original DFA.
    /// let original_dfa = DFA::new("foo[0-9]+")?;
    ///
    /// let buf = original_dfa.to_bytes_native_endian();
    /// // Even if buf has initial padding, DFA::from_bytes will automatically
    /// // ignore it.
    /// let dfa: DFA<&[u8]> = DFA::from_bytes(&buf)?.0;
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "dfa-build")]
    pub fn to_bytes_native_endian(&self) -> Vec<u8> {
        self.to_bytes::<wire::NE>()
    }

    /// The implementation of the public `to_bytes` serialization methods,
    /// which is generic over endianness.
    #[cfg(feature = "dfa-build")]
    fn to_bytes<E: Endian>(&self) -> Vec<u8> {
        let mut buf = vec![0; self.write_to_len()];
        // This should always succeed since the only possible serialization
        // error is providing a buffer that's too small, but we've ensured that
        // `buf` is big enough here.
        self.write_to::<E>(&mut buf).unwrap();
        buf
    }

    /// Serialize this DFA as raw bytes to the given slice, in little endian
    /// format. Upon success, the total number of bytes written to `dst` is
    /// returned.
    ///
    /// The written bytes are guaranteed to be deserialized correctly and
    /// without errors in a semver compatible release of this crate by a
    /// `DFA`'s deserialization APIs (assuming all other criteria for the
    /// deserialization APIs has been satisfied):
    ///
    /// * [`DFA::from_bytes`]
    /// * [`DFA::from_bytes_unchecked`]
    ///
    /// # Errors
    ///
    /// This returns an error if the given destination slice is not big enough
    /// to contain the full serialized DFA. If an error occurs, then nothing
    /// is written to `dst`.
    ///
    /// # Example
    ///
    /// This example shows how to serialize and deserialize a DFA without
    /// dynamic memory allocation.
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// // Compile our original DFA.
    /// let original_dfa = DFA::new("foo[0-9]+")?;
    ///
    /// // Create a 4KB buffer on the stack to store our serialized DFA.
    /// let mut buf = [0u8; 4 * (1<<10)];
    /// // N.B. We use native endianness here to make the example work, but
    /// // using write_to_little_endian would work on a little endian target.
    /// let written = original_dfa.write_to_native_endian(&mut buf)?;
    /// let dfa: DFA<&[u8]> = DFA::from_bytes(&buf[..written])?.0;
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn write_to_little_endian(
        &self,
        dst: &mut [u8],
    ) -> Result<usize, SerializeError> {
        self.write_to::<wire::LE>(dst)
    }

    /// Serialize this DFA as raw bytes to the given slice, in big endian
    /// format. Upon success, the total number of bytes written to `dst` is
    /// returned.
    ///
    /// The written bytes are guaranteed to be deserialized correctly and
    /// without errors in a semver compatible release of this crate by a
    /// `DFA`'s deserialization APIs (assuming all other criteria for the
    /// deserialization APIs has been satisfied):
    ///
    /// * [`DFA::from_bytes`]
    /// * [`DFA::from_bytes_unchecked`]
    ///
    /// # Errors
    ///
    /// This returns an error if the given destination slice is not big enough
    /// to contain the full serialized DFA. If an error occurs, then nothing
    /// is written to `dst`.
    ///
    /// # Example
    ///
    /// This example shows how to serialize and deserialize a DFA without
    /// dynamic memory allocation.
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// // Compile our original DFA.
    /// let original_dfa = DFA::new("foo[0-9]+")?;
    ///
    /// // Create a 4KB buffer on the stack to store our serialized DFA.
    /// let mut buf = [0u8; 4 * (1<<10)];
    /// // N.B. We use native endianness here to make the example work, but
    /// // using write_to_big_endian would work on a big endian target.
    /// let written = original_dfa.write_to_native_endian(&mut buf)?;
    /// let dfa: DFA<&[u8]> = DFA::from_bytes(&buf[..written])?.0;
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn write_to_big_endian(
        &self,
        dst: &mut [u8],
    ) -> Result<usize, SerializeError> {
        self.write_to::<wire::BE>(dst)
    }

    /// Serialize this DFA as raw bytes to the given slice, in native endian
    /// format. Upon success, the total number of bytes written to `dst` is
    /// returned.
    ///
    /// The written bytes are guaranteed to be deserialized correctly and
    /// without errors in a semver compatible release of this crate by a
    /// `DFA`'s deserialization APIs (assuming all other criteria for the
    /// deserialization APIs has been satisfied):
    ///
    /// * [`DFA::from_bytes`]
    /// * [`DFA::from_bytes_unchecked`]
    ///
    /// Generally speaking, native endian format should only be used when
    /// you know that the target you're compiling the DFA for matches the
    /// endianness of the target on which you're compiling DFA. For example,
    /// if serialization and deserialization happen in the same process or on
    /// the same machine. Otherwise, when serializing a DFA for use in a
    /// portable environment, you'll almost certainly want to serialize _both_
    /// a little endian and a big endian version and then load the correct one
    /// based on the target's configuration.
    ///
    /// # Errors
    ///
    /// This returns an error if the given destination slice is not big enough
    /// to contain the full serialized DFA. If an error occurs, then nothing
    /// is written to `dst`.
    ///
    /// # Example
    ///
    /// This example shows how to serialize and deserialize a DFA without
    /// dynamic memory allocation.
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// // Compile our original DFA.
    /// let original_dfa = DFA::new("foo[0-9]+")?;
    ///
    /// // Create a 4KB buffer on the stack to store our serialized DFA.
    /// let mut buf = [0u8; 4 * (1<<10)];
    /// let written = original_dfa.write_to_native_endian(&mut buf)?;
    /// let dfa: DFA<&[u8]> = DFA::from_bytes(&buf[..written])?.0;
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn write_to_native_endian(
        &self,
        dst: &mut [u8],
    ) -> Result<usize, SerializeError> {
        self.write_to::<wire::NE>(dst)
    }

    /// The implementation of the public `write_to` serialization methods,
    /// which is generic over endianness.
    fn write_to<E: Endian>(
        &self,
        dst: &mut [u8],
    ) -> Result<usize, SerializeError> {
        let mut nw = 0;
        nw += wire::write_label(LABEL, &mut dst[nw..])?;
        nw += wire::write_endianness_check::<E>(&mut dst[nw..])?;
        nw += wire::write_version::<E>(VERSION, &mut dst[nw..])?;
        nw += {
            // Currently unused, intended for future flexibility
            E::write_u32(0, &mut dst[nw..]);
            size_of::<u32>()
        };
        nw += self.flags.write_to::<E>(&mut dst[nw..])?;
        nw += self.tt.write_to::<E>(&mut dst[nw..])?;
        nw += self.st.write_to::<E>(&mut dst[nw..])?;
        nw += self.special.write_to::<E>(&mut dst[nw..])?;
        nw += self.quitset.write_to::<E>(&mut dst[nw..])?;
        Ok(nw)
    }

    /// Return the total number of bytes required to serialize this DFA.
    ///
    /// This is useful for determining the size of the buffer required to pass
    /// to one of the serialization routines:
    ///
    /// * [`DFA::write_to_little_endian`]
    /// * [`DFA::write_to_big_endian`]
    /// * [`DFA::write_to_native_endian`]
    ///
    /// Passing a buffer smaller than the size returned by this method will
    /// result in a serialization error.
    ///
    /// # Example
    ///
    /// This example shows how to dynamically allocate enough room to serialize
    /// a sparse DFA.
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// // Compile our original DFA.
    /// let original_dfa = DFA::new("foo[0-9]+")?;
    ///
    /// let mut buf = vec![0; original_dfa.write_to_len()];
    /// let written = original_dfa.write_to_native_endian(&mut buf)?;
    /// let dfa: DFA<&[u8]> = DFA::from_bytes(&buf[..written])?.0;
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn write_to_len(&self) -> usize {
        wire::write_label_len(LABEL)
        + wire::write_endianness_check_len()
        + wire::write_version_len()
        + size_of::<u32>() // unused, intended for future flexibility
        + self.flags.write_to_len()
        + self.tt.write_to_len()
        + self.st.write_to_len()
        + self.special.write_to_len()
        + self.quitset.write_to_len()
    }
}

impl<'a> DFA<&'a [u8]> {
    /// Safely deserialize a sparse DFA with a specific state identifier
    /// representation. Upon success, this returns both the deserialized DFA
    /// and the number of bytes read from the given slice. Namely, the contents
    /// of the slice beyond the DFA are not read.
    ///
    /// Deserializing a DFA using this routine will never allocate heap memory.
    /// For safety purposes, the DFA's transitions will be verified such that
    /// every transition points to a valid state. If this verification is too
    /// costly, then a [`DFA::from_bytes_unchecked`] API is provided, which
    /// will always execute in constant time.
    ///
    /// The bytes given must be generated by one of the serialization APIs
    /// of a `DFA` using a semver compatible release of this crate. Those
    /// include:
    ///
    /// * [`DFA::to_bytes_little_endian`]
    /// * [`DFA::to_bytes_big_endian`]
    /// * [`DFA::to_bytes_native_endian`]
    /// * [`DFA::write_to_little_endian`]
    /// * [`DFA::write_to_big_endian`]
    /// * [`DFA::write_to_native_endian`]
    ///
    /// The `to_bytes` methods allocate and return a `Vec<u8>` for you. The
    /// `write_to` methods do not allocate and write to an existing slice
    /// (which may be on the stack). Since deserialization always uses the
    /// native endianness of the target platform, the serialization API you use
    /// should match the endianness of the target platform. (It's often a good
    /// idea to generate serialized DFAs for both forms of endianness and then
    /// load the correct one based on endianness.)
    ///
    /// # Errors
    ///
    /// Generally speaking, it's easier to state the conditions in which an
    /// error is _not_ returned. All of the following must be true:
    ///
    /// * The bytes given must be produced by one of the serialization APIs
    ///   on this DFA, as mentioned above.
    /// * The endianness of the target platform matches the endianness used to
    ///   serialized the provided DFA.
    ///
    /// If any of the above are not true, then an error will be returned.
    ///
    /// Note that unlike deserializing a
    /// [`dense::DFA`](crate::dfa::dense::DFA), deserializing a sparse DFA has
    /// no alignment requirements. That is, an alignment of `1` is valid.
    ///
    /// # Panics
    ///
    /// This routine will never panic for any input.
    ///
    /// # Example
    ///
    /// This example shows how to serialize a DFA to raw bytes, deserialize it
    /// and then use it for searching.
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// let initial = DFA::new("foo[0-9]+")?;
    /// let bytes = initial.to_bytes_native_endian();
    /// let dfa: DFA<&[u8]> = DFA::from_bytes(&bytes)?.0;
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    ///
    /// # Example: loading a DFA from static memory
    ///
    /// One use case this library supports is the ability to serialize a
    /// DFA to disk and then use `include_bytes!` to store it in a compiled
    /// Rust program. Those bytes can then be cheaply deserialized into a
    /// `DFA` structure at runtime and used for searching without having to
    /// re-compile the DFA (which can be quite costly).
    ///
    /// We can show this in two parts. The first part is serializing the DFA to
    /// a file:
    ///
    /// ```no_run
    /// use regex_automata::dfa::sparse::DFA;
    ///
    /// let dfa = DFA::new("foo[0-9]+")?;
    ///
    /// // Write a big endian serialized version of this DFA to a file.
    /// let bytes = dfa.to_bytes_big_endian();
    /// std::fs::write("foo.bigendian.dfa", &bytes)?;
    ///
    /// // Do it again, but this time for little endian.
    /// let bytes = dfa.to_bytes_little_endian();
    /// std::fs::write("foo.littleendian.dfa", &bytes)?;
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    ///
    /// And now the second part is embedding the DFA into the compiled program
    /// and deserializing it at runtime on first use. We use conditional
    /// compilation to choose the correct endianness. We do not need to employ
    /// any special tricks to ensure a proper alignment, since a sparse DFA has
    /// no alignment requirements.
    ///
    /// ```no_run
    /// use regex_automata::{
    ///     dfa::{Automaton, sparse::DFA},
    ///     util::lazy::Lazy,
    ///     HalfMatch, Input,
    /// };
    ///
    /// // This crate provides its own "lazy" type, kind of like
    /// // lazy_static! or once_cell::sync::Lazy. But it works in no-alloc
    /// // no-std environments and let's us write this using completely
    /// // safe code.
    /// static RE: Lazy<DFA<&'static [u8]>> = Lazy::new(|| {
    ///     # const _: &str = stringify! {
    ///     #[cfg(target_endian = "big")]
    ///     static BYTES: &[u8] = include_bytes!("foo.bigendian.dfa");
    ///     #[cfg(target_endian = "little")]
    ///     static BYTES: &[u8] = include_bytes!("foo.littleendian.dfa");
    ///     # };
    ///     # static BYTES: &[u8] = b"";
    ///
    ///     let (dfa, _) = DFA::from_bytes(BYTES)
    ///         .expect("serialized DFA should be valid");
    ///     dfa
    /// });
    ///
    /// let expected = Ok(Some(HalfMatch::must(0, 8)));
    /// assert_eq!(expected, RE.try_search_fwd(&Input::new("foo12345")));
    /// ```
    ///
    /// Alternatively, consider using
    /// [`lazy_static`](https://crates.io/crates/lazy_static)
    /// or
    /// [`once_cell`](https://crates.io/crates/once_cell),
    /// which will guarantee safety for you.
    pub fn from_bytes(
        slice: &'a [u8],
    ) -> Result<(DFA<&'a [u8]>, usize), DeserializeError> {
        // SAFETY: This is safe because we validate both the sparse transitions
        // (by trying to decode every state) and start state ID list below. If
        // either validation fails, then we return an error.
        let (dfa, nread) = unsafe { DFA::from_bytes_unchecked(slice)? };
        dfa.tt.validate(&dfa.special)?;
        dfa.st.validate(&dfa.special, &dfa.tt)?;
        // N.B. dfa.special doesn't have a way to do unchecked deserialization,
        // so it has already been validated.
        Ok((dfa, nread))
    }

    /// Deserialize a DFA with a specific state identifier representation in
    /// constant time by omitting the verification of the validity of the
    /// sparse transitions.
    ///
    /// This is just like [`DFA::from_bytes`], except it can potentially return
    /// a DFA that exhibits undefined behavior if its transitions contains
    /// invalid state identifiers.
    ///
    /// This routine is useful if you need to deserialize a DFA cheaply and
    /// cannot afford the transition validation performed by `from_bytes`.
    ///
    /// # Safety
    ///
    /// This routine is not safe because it permits callers to provide
    /// arbitrary transitions with possibly incorrect state identifiers. While
    /// the various serialization routines will never return an incorrect
    /// DFA, there is no guarantee that the bytes provided here are correct.
    /// While `from_bytes_unchecked` will still do several forms of basic
    /// validation, this routine does not check that the transitions themselves
    /// are 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
    ///
    /// ```
    /// use regex_automata::{dfa::{Automaton, sparse::DFA}, HalfMatch, Input};
    ///
    /// let initial = DFA::new("foo[0-9]+")?;
    /// let bytes = initial.to_bytes_native_endian();
    /// // SAFETY: This is guaranteed to be safe since the bytes given come
    /// // directly from a compatible serialization routine.
    /// let dfa: DFA<&[u8]> = unsafe { DFA::from_bytes_unchecked(&bytes)?.0 };
    ///
    /// let expected = Some(HalfMatch::must(0, 8));
    /// assert_eq!(expected, dfa.try_search_fwd(&Input::new("foo12345"))?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub unsafe fn from_bytes_unchecked(
        slice: &'a [u8],
    ) -> Result<(DFA<&'a [u8]>, usize), DeserializeError> {
        let mut nr = 0;

        nr += wire::read_label(&slice[nr..], LABEL)?;
        nr += wire::read_endianness_check(&slice[nr..])?;
        nr += wire::read_version(&slice[nr..], VERSION)?;

        let _unused = wire::try_read_u32(&slice[nr..], "unused space")?;
        nr += size_of::<u32>();

        let (flags, nread) = Flags::from_bytes(&slice[nr..])?;
        nr += nread;

        let (tt, nread) = Transitions::from_bytes_unchecked(&slice[nr..])?;
        nr += nread;

        let (st, nread) = StartTable::from_bytes_unchecked(&slice[nr..])?;
        nr += nread;

        let (special, nread) = Special::from_bytes(&slice[nr..])?;
        nr += nread;
        if special.max.as_usize() >= tt.sparse().len() {
            return Err(DeserializeError::generic(
                "max should not be greater than or equal to sparse bytes",
            ));
        }

        let (quitset, nread) = ByteSet::from_bytes(&slice[nr..])?;
        nr += nread;

        // Prefilters don't support serialization, so they're always absent.
        let pre = None;
        Ok((DFA { tt, st, special, pre, quitset, flags }, nr))
    }
}

impl<T: AsRef<[u8]>> fmt::Debug for DFA<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "sparse::DFA(")?;
        for state in self.tt.states() {
            fmt_state_indicator(f, self, state.id())?;
            writeln!(f, "{:06?}: {:?}", state.id().as_usize(), state)?;
        }
        writeln!(f, "")?;
        for (i, (start_id, anchored, sty)) in self.st.iter().enumerate() {
            if i % self.st.stride == 0 {
                match anchored {
                    Anchored::No => writeln!(f, "START-GROUP(unanchored)")?,
                    Anchored::Yes => writeln!(f, "START-GROUP(anchored)")?,
                    Anchored::Pattern(pid) => writeln!(
                        f,
                        "START_GROUP(pattern: {:?})",
                        pid.as_usize()
                    )?,
                }
            }
            writeln!(f, "  {:?} => {:06?}", sty, start_id.as_usize())?;
        }
        writeln!(f, "state length: {:?}", self.tt.state_len)?;
        writeln!(f, "pattern length: {:?}", self.pattern_len())?;
        writeln!(f, "flags: {:?}", self.flags)?;
        writeln!(f, ")")?;
        Ok(())
    }
}

// SAFETY: We assert that our implementation of each method is correct.
unsafe impl<T: AsRef<[u8]>> Automaton for DFA<T> {
    #[inline]
    fn is_special_state(&self, id: StateID) -> bool {
        self.special.is_special_state(id)
    }

    #[inline]
    fn is_dead_state(&self, id: StateID) -> bool {
        self.special.is_dead_state(id)
    }

    #[inline]
    fn is_quit_state(&self, id: StateID) -> bool {
        self.special.is_quit_state(id)
    }

    #[inline]
    fn is_match_state(&self, id: StateID) -> bool {
        self.special.is_match_state(id)
    }

    #[inline]
    fn is_start_state(&self, id: StateID) -> bool {
        self.special.is_start_state(id)
    }

    #[inline]
    fn is_accel_state(&self, id: StateID) -> bool {
        self.special.is_accel_state(id)
    }

    // This is marked as inline to help dramatically boost sparse searching,
    // which decodes each state it enters to follow the next transition.
    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn next_state(&self, current: StateID, input: u8) -> StateID {
        let input = self.tt.classes.get(input);
        self.tt.state(current).next(input)
    }

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

    #[inline]
    fn next_eoi_state(&self, current: StateID) -> StateID {
        self.tt.state(current).next_eoi()
    }

    #[inline]
    fn pattern_len(&self) -> usize {
        self.tt.pattern_len
    }

    #[inline]
    fn match_len(&self, id: StateID) -> usize {
        self.tt.state(id).pattern_len()
    }

    #[inline]
    fn match_pattern(&self, id: StateID, match_index: usize) -> PatternID {
        // This is an optimization for the very common case of a DFA with a
        // single pattern. This conditional avoids a somewhat more costly path
        // that finds the pattern ID from the state machine, which requires
        // a bit of slicing/pointer-chasing. This optimization tends to only
        // matter when matches are frequent.
        if self.tt.pattern_len == 1 {
            return PatternID::ZERO;
        }
        self.tt.state(id).pattern_id(match_index)
    }

    #[inline]
    fn has_empty(&self) -> bool {
        self.flags.has_empty
    }

    #[inline]
    fn is_utf8(&self) -> bool {
        self.flags.is_utf8
    }

    #[inline]
    fn is_always_start_anchored(&self) -> bool {
        self.flags.is_always_start_anchored
    }

    #[inline]
    fn start_state_forward(
        &self,
        input: &Input<'_>,
    ) -> Result<StateID, MatchError> {
        if !self.quitset.is_empty() && input.start() > 0 {
            let offset = input.start() - 1;
            let byte = input.haystack()[offset];
            if self.quitset.contains(byte) {
                return Err(MatchError::quit(byte, offset));
            }
        }
        let start = self.st.start_map.fwd(&input);
        self.st.start(input, start)
    }

    #[inline]
    fn start_state_reverse(
        &self,
        input: &Input<'_>,
    ) -> Result<StateID, MatchError> {
        if !self.quitset.is_empty() && input.end() < input.haystack().len() {
            let offset = input.end();
            let byte = input.haystack()[offset];
            if self.quitset.contains(byte) {
                return Err(MatchError::quit(byte, offset));
            }
        }
        let start = self.st.start_map.rev(&input);
        self.st.start(input, start)
    }

    #[inline]
    fn universal_start_state(&self, mode: Anchored) -> Option<StateID> {
        match mode {
            Anchored::No => self.st.universal_start_unanchored,
            Anchored::Yes => self.st.universal_start_anchored,
            Anchored::Pattern(_) => None,
        }
    }

    #[inline]
    fn accelerator(&self, id: StateID) -> &[u8] {
        self.tt.state(id).accelerator()
    }

    #[inline]
    fn get_prefilter(&self) -> Option<&Prefilter> {
        self.pre.as_ref()
    }
}

/// The transition table portion of a sparse DFA.
///
/// The transition table is the core part of the DFA in that it describes how
/// to move from one state to another based on the input sequence observed.
///
/// Unlike a typical dense table based DFA, states in a sparse transition
/// table have variable size. That is, states with more transitions use more
/// space than states with fewer transitions. This means that finding the next
/// transition takes more work than with a dense DFA, but also typically uses
/// much less space.
#[derive(Clone)]
struct Transitions<T> {
    /// The raw encoding of each state in this DFA.
    ///
    /// Each state has the following information:
    ///
    /// * A set of transitions to subsequent states. Transitions to the dead
    ///   state are omitted.
    /// * If the state can be accelerated, then any additional accelerator
    ///   information.
    /// * If the state is a match state, then the state contains all pattern
    ///   IDs that match when in that state.
    ///
    /// To decode a state, use Transitions::state.
    ///
    /// In practice, T is either Vec<u8> or &[u8].
    sparse: T,
    /// A set of equivalence classes, where a single equivalence class
    /// represents a set of bytes that never discriminate between a match
    /// and a non-match in the DFA. Each equivalence class corresponds to a
    /// single character in this DFA's alphabet, where the maximum number of
    /// characters is 257 (each possible value of a byte plus the special
    /// EOI transition). Consequently, the number of equivalence classes
    /// corresponds to the number of transitions for each DFA state. Note
    /// though that the *space* used by each DFA state in the transition table
    /// may be larger. The total space used by each DFA state is known as the
    /// stride and is documented above.
    ///
    /// The only time the number of equivalence classes is fewer than 257 is
    /// if the DFA's kind uses byte classes which is the default. Equivalence
    /// classes should generally only be disabled when debugging, so that
    /// the transitions themselves aren't obscured. Disabling them has no
    /// other benefit, since the equivalence class map is always used while
    /// searching. In the vast majority of cases, the number of equivalence
    /// classes is substantially smaller than 257, particularly when large
    /// Unicode classes aren't used.
    ///
    /// N.B. Equivalence classes aren't particularly useful in a sparse DFA
    /// in the current implementation, since equivalence classes generally tend
    /// to correspond to continuous ranges of bytes that map to the same
    /// transition. So in a sparse DFA, equivalence classes don't really lead
    /// to a space savings. In the future, it would be good to try and remove
    /// them from sparse DFAs entirely, but requires a bit of work since sparse
    /// DFAs are built from dense DFAs, which are in turn built on top of
    /// equivalence classes.
    classes: ByteClasses,
    /// The total number of states in this DFA. Note that a DFA always has at
    /// least one state---the dead state---even the empty DFA. In particular,
    /// the dead state always has ID 0 and is correspondingly always the first
    /// state. The dead state is never a match state.
    state_len: usize,
    /// The total number of unique patterns represented by these match states.
    pattern_len: usize,
}

impl<'a> Transitions<&'a [u8]> {
    unsafe fn from_bytes_unchecked(
        mut slice: &'a [u8],
    ) -> Result<(Transitions<&'a [u8]>, usize), DeserializeError> {
        let slice_start = slice.as_ptr().as_usize();

        let (state_len, nr) =
            wire::try_read_u32_as_usize(&slice, "state length")?;
        slice = &slice[nr..];

        let (pattern_len, nr) =
            wire::try_read_u32_as_usize(&slice, "pattern length")?;
        slice = &slice[nr..];

        let (classes, nr) = ByteClasses::from_bytes(&slice)?;
        slice = &slice[nr..];

        let (len, nr) =
            wire::try_read_u32_as_usize(&slice, "sparse transitions length")?;
        slice = &slice[nr..];

        wire::check_slice_len(slice, len, "sparse states byte length")?;
        let sparse = &slice[..len];
        slice = &slice[len..];

        let trans = Transitions { sparse, classes, state_len, pattern_len };
        Ok((trans, slice.as_ptr().as_usize() - slice_start))
    }
}

impl<T: AsRef<[u8]>> Transitions<T> {
    /// Writes a serialized form of this transition table to the buffer given.
    /// If the buffer is too small, then an error is returned. To determine
    /// how big the buffer must be, use `write_to_len`.
    fn write_to<E: Endian>(
        &self,
        mut dst: &mut [u8],
    ) -> Result<usize, SerializeError> {
        let nwrite = self.write_to_len();
        if dst.len() < nwrite {
            return Err(SerializeError::buffer_too_small(
                "sparse transition table",
            ));
        }
        dst = &mut dst[..nwrite];

        // write state length
        E::write_u32(u32::try_from(self.state_len).unwrap(), dst);
        dst = &mut dst[size_of::<u32>()..];

        // write pattern length
        E::write_u32(u32::try_from(self.pattern_len).unwrap(), dst);
        dst = &mut dst[size_of::<u32>()..];

        // write byte class map
        let n = self.classes.write_to(dst)?;
        dst = &mut dst[n..];

        // write number of bytes in sparse transitions
        E::write_u32(u32::try_from(self.sparse().len()).unwrap(), dst);
        dst = &mut dst[size_of::<u32>()..];

        // write actual transitions
        let mut id = DEAD;
        while id.as_usize() < self.sparse().len() {
            let state = self.state(id);
            let n = state.write_to::<E>(&mut dst)?;
            dst = &mut dst[n..];
            // The next ID is the offset immediately following `state`.
            id = StateID::new(id.as_usize() + state.write_to_len()).unwrap();
        }
        Ok(nwrite)
    }

    /// Returns the number of bytes the serialized form of this transition
    /// table will use.
    fn write_to_len(&self) -> usize {
        size_of::<u32>()   // state length
        + size_of::<u32>() // pattern length
        + self.classes.write_to_len()
        + size_of::<u32>() // sparse transitions length
        + self.sparse().len()
    }

    /// Validates that every state ID in this transition table is valid.
    ///
    /// That is, every state ID can be used to correctly index a state in this
    /// table.
    fn validate(&self, sp: &Special) -> Result<(), DeserializeError> {
        // In order to validate everything, we not only need to make sure we
        // can decode every state, but that every transition in every state
        // points to a valid state. There are many duplicative transitions, so
        // we record state IDs that we've verified so that we don't redo the
        // decoding work.
        //
        // Except, when in no_std mode, we don't have dynamic memory allocation
        // available to us, so we skip this optimization. It's not clear
        // whether doing something more clever is worth it just yet. If you're
        // profiling this code and need it to run faster, please file an issue.
        //
        // OK, so we also use this to record the set of valid state IDs. Since
        // it is possible for a transition to point to an invalid state ID that
        // still (somehow) deserializes to a valid state. So we need to make
        // sure our transitions are limited to actually correct state IDs.
        // The problem is, I'm not sure how to do this verification step in
        // no-std no-alloc mode. I think we'd *have* to store the set of valid
        // state IDs in the DFA itself. For now, we don't do this verification
        // in no-std no-alloc mode. The worst thing that can happen is an
        // incorrect result. But no panics or memory safety problems should
        // result. Because we still do validate that the state itself is
        // "valid" in the sense that everything it points to actually exists.
        //
        // ---AG
        struct Seen {
            #[cfg(feature = "alloc")]
            set: alloc::collections::BTreeSet<StateID>,
            #[cfg(not(feature = "alloc"))]
            set: core::marker::PhantomData<StateID>,
        }

        #[cfg(feature = "alloc")]
        impl Seen {
            fn new() -> Seen {
                Seen { set: alloc::collections::BTreeSet::new() }
            }
            fn insert(&mut self, id: StateID) {
                self.set.insert(id);
            }
            fn contains(&self, id: &StateID) -> bool {
                self.set.contains(id)
            }
        }

        #[cfg(not(feature = "alloc"))]
        impl Seen {
            fn new() -> Seen {
                Seen { set: core::marker::PhantomData }
            }
            fn insert(&mut self, _id: StateID) {}
            fn contains(&self, _id: &StateID) -> bool {
                false
            }
        }

        let mut verified: Seen = Seen::new();
        // We need to make sure that we decode the correct number of states.
        // Otherwise, an empty set of transitions would validate even if the
        // recorded state length is non-empty.
        let mut len = 0;
        // We can't use the self.states() iterator because it assumes the state
        // encodings are valid. It could panic if they aren't.
        let mut id = DEAD;
        while id.as_usize() < self.sparse().len() {
            // Before we even decode the state, we check that the ID itself
            // is well formed. That is, if it's a special state then it must
            // actually be a quit, dead, accel, match or start state.
            if sp.is_special_state(id) {
                let is_actually_special = sp.is_dead_state(id)
                    || sp.is_quit_state(id)
                    || sp.is_match_state(id)
                    || sp.is_start_state(id)
                    || sp.is_accel_state(id);
                if !is_actually_special {
                    // This is kind of a cryptic error message...
                    return Err(DeserializeError::generic(
                        "found sparse state tagged as special but \
                         wasn't actually special",
                    ));
                }
            }
            let state = self.try_state(sp, id)?;
            verified.insert(id);
            // The next ID should be the offset immediately following `state`.
            id = StateID::new(wire::add(
                id.as_usize(),
                state.write_to_len(),
                "next state ID offset",
            )?)
            .map_err(|err| {
                DeserializeError::state_id_error(err, "next state ID offset")
            })?;
            len += 1;
        }
        // Now that we've checked that all top-level states are correct and
        // importantly, collected a set of valid state IDs, we have all the
        // information we need to check that all transitions are correct too.
        //
        // Note that we can't use `valid_ids` to iterate because it will
        // be empty in no-std no-alloc contexts. (And yes, that means our
        // verification isn't quite as good.) We can use `self.states()`
        // though at least, since we know that all states can at least be
        // decoded and traversed correctly.
        for state in self.states() {
            // Check that all transitions in this state are correct.
            for i in 0..state.ntrans {
                let to = state.next_at(i);
                // For no-alloc, we just check that the state can decode. It is
                // technically possible that the state ID could still point to
                // a non-existent state even if it decodes (fuzzing proved this
                // to be true), but it shouldn't result in any memory unsafety
                // or panics in non-debug mode.
                #[cfg(not(feature = "alloc"))]
                {
                    let _ = self.try_state(sp, to)?;
                }
                #[cfg(feature = "alloc")]
                {
                    if !verified.contains(&to) {
                        return Err(DeserializeError::generic(
                            "found transition that points to a \
                             non-existent state",
                        ));
                    }
                }
            }
        }
        if len != self.state_len {
            return Err(DeserializeError::generic(
                "mismatching sparse state length",
            ));
        }
        Ok(())
    }

    /// Converts these transitions to a borrowed value.
    fn as_ref(&self) -> Transitions<&'_ [u8]> {
        Transitions {
            sparse: self.sparse(),
            classes: self.classes.clone(),
            state_len: self.state_len,
            pattern_len: self.pattern_len,
        }
    }

    /// Converts these transitions to an owned value.
    #[cfg(feature = "alloc")]
    fn to_owned(&self) -> Transitions<alloc::vec::Vec<u8>> {
        Transitions {
            sparse: self.sparse().to_vec(),
            classes: self.classes.clone(),
            state_len: self.state_len,
            pattern_len: self.pattern_len,
        }
    }

    /// Return a convenient representation of the given state.
    ///
    /// This panics if the state is invalid.
    ///
    /// This is marked as inline to help dramatically boost sparse searching,
    /// which decodes each state it enters to follow the next transition. Other
    /// functions involved are also inlined, which should hopefully eliminate
    /// a lot of the extraneous decoding that is never needed just to follow
    /// the next transition.
    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn state(&self, id: StateID) -> State<'_> {
        let mut state = &self.sparse()[id.as_usize()..];
        let mut ntrans = wire::read_u16(&state).as_usize();
        let is_match = (1 << 15) & ntrans != 0;
        ntrans &= !(1 << 15);
        state = &state[2..];

        let (input_ranges, state) = state.split_at(ntrans * 2);
        let (next, state) = state.split_at(ntrans * StateID::SIZE);
        let (pattern_ids, state) = if is_match {
            let npats = wire::read_u32(&state).as_usize();
            state[4..].split_at(npats * 4)
        } else {
            (&[][..], state)
        };

        let accel_len = usize::from(state[0]);
        let accel = &state[1..accel_len + 1];
        State { id, is_match, ntrans, input_ranges, next, pattern_ids, accel }
    }

    /// Like `state`, but will return an error if the state encoding is
    /// invalid. This is useful for verifying states after deserialization,
    /// which is required for a safe deserialization API.
    ///
    /// Note that this only verifies that this state is decodable and that
    /// all of its data is consistent. It does not verify that its state ID
    /// transitions point to valid states themselves, nor does it verify that
    /// every pattern ID is valid.
    fn try_state(
        &self,
        sp: &Special,
        id: StateID,
    ) -> Result<State<'_>, DeserializeError> {
        if id.as_usize() > self.sparse().len() {
            return Err(DeserializeError::generic(
                "invalid caller provided sparse state ID",
            ));
        }
        let mut state = &self.sparse()[id.as_usize()..];
        // Encoding format starts with a u16 that stores the total number of
        // transitions in this state.
        let (mut ntrans, _) =
            wire::try_read_u16_as_usize(state, "state transition length")?;
        let is_match = ((1 << 15) & ntrans) != 0;
        ntrans &= !(1 << 15);
        state = &state[2..];
        if ntrans > 257 || ntrans == 0 {
            return Err(DeserializeError::generic(
                "invalid transition length",
            ));
        }
--> --------------------

--> maximum size reached

--> --------------------