use crate::{
    dfa::search,
    util::{
        id::{PatternID, StateID},
        matchtypes::{HalfMatch, MatchError},
        prefilter,
    },
};

/// A trait describing the interface of a deterministic finite automaton (DFA).
///
/// The complexity of this trait probably means that it's unlikely for others
/// to implement it. The primary purpose of the trait is to provide for a way
/// of abstracting over different types of DFAs. In this crate, that means
/// dense DFAs and sparse DFAs. (Dense DFAs are fast but memory hungry, where
/// as sparse DFAs are slower but come with a smaller memory footprint. But
/// they otherwise provide exactly equivalent expressive power.) For example, a
/// [`dfa::regex::Regex`](crate::dfa::regex::Regex) is generic over this trait.
///
/// Normally, a DFA's execution model is very simple. You might have a single
/// start state, zero or more final or "match" states and a function that
/// transitions from one state to the next given the next byte of input.
/// Unfortunately, the interface described by this trait is significantly
/// more complicated than this. The complexity has a number of different
/// reasons, mostly motivated by performance, functionality or space savings:
///
/// * A DFA can search for multiple patterns simultaneously. This
/// means extra information is returned when a match occurs. Namely,
/// a match is not just an offset, but an offset plus a pattern ID.
/// [`Automaton::pattern_count`] returns the number of patterns compiled into
/// the DFA, [`Automaton::match_count`] returns the total number of patterns
/// that match in a particular state and [`Automaton::match_pattern`] permits
/// iterating over the patterns that match in a particular state.
/// * A DFA can have multiple start states, and the choice of which start
/// state to use depends on the content of the string being searched and
/// position of the search, as well as whether the search is an anchored
/// search for a specific pattern in the DFA. Moreover, computing the start
/// state also depends on whether you're doing a forward or a reverse search.
/// [`Automaton::start_state_forward`] and [`Automaton::start_state_reverse`]
/// are used to compute the start state for forward and reverse searches,
/// respectively.
/// * All matches are delayed by one byte to support things like `$` and `\b`
/// at the end of a pattern. Therefore, every use of a DFA is required to use
/// [`Automaton::next_eoi_state`]
/// at the end of the search to compute the final transition.
/// * For optimization reasons, some states are treated specially. Every
/// state is either special or not, which can be determined via the
/// [`Automaton::is_special_state`] method. If it's special, then the state
/// must be at least one of a few possible types of states. (Note that some
/// types can overlap, for example, a match state can also be an accel state.
/// But some types can't. If a state is a dead state, then it can never be any
/// other type of state.) Those types are:
///     * A dead state. A dead state means the DFA will never enter a match
///     state. This can be queried via the [`Automaton::is_dead_state`] method.
///     * A quit state. A quit state occurs if the DFA had to stop the search
///     prematurely for some reason. This can be queried via the
///     [`Automaton::is_quit_state`] method.
///     * A match state. A match state occurs when a match is found. When a DFA
///     enters a match state, the search may stop immediately (when looking
///     for the earliest match), or it may continue to find the leftmost-first
///     match. This can be queried via the [`Automaton::is_match_state`]
///     method.
///     * A start state. A start state is where a search begins. For every
///     search, there is exactly one start state that is used, however, a
///     DFA may contain many start states. When the search is in a start
///     state, it may use a prefilter to quickly skip to candidate matches
///     without executing the DFA on every byte. This can be queried via the
///     [`Automaton::is_start_state`] method.
///     * An accel state. An accel state is a state that is accelerated.
///     That is, it is a state where _most_ of its transitions loop back to
///     itself and only a small number of transitions lead to other states.
///     This kind of state is said to be accelerated because a search routine
///     can quickly look for the bytes leading out of the state instead of
///     continuing to execute the DFA on each byte. This can be queried via the
///     [`Automaton::is_accel_state`] method. And the bytes that lead out of
///     the state can be queried via the [`Automaton::accelerator`] method.
///
/// There are a number of provided methods on this trait that implement
/// efficient searching (for forwards and backwards) with a DFA using all of
/// the above features of this trait. In particular, given the complexity of
/// all these features, implementing a search routine in this trait is not
/// straight forward. If you need to do this for specialized reasons, then
/// it's recommended to look at the source of this crate. It is intentionally
/// well commented to help with this. With that said, it is possible to
/// somewhat simplify the search routine. For example, handling accelerated
/// states is strictly optional, since it is always correct to assume that
/// `Automaton::is_accel_state` returns false. However, one complex part of
/// writing a search routine using this trait is handling the 1-byte delay of a
/// match. That is not optional.
///
/// # Safety
///
/// This trait is unsafe to implement because DFA searching may rely on the
/// correctness of the implementation for memory safety. For example, DFA
/// searching may use explicit bounds check elision, which will in turn rely
/// on the correctness of every function that returns a state ID.
///
/// When implementing this trait, one must uphold the documented correctness
/// guarantees. Otherwise, undefined behavior may occur.
pub unsafe trait Automaton {
    /// Transitions from the current state to the next state, given the next
    /// byte of input.
    ///
    /// Implementations must guarantee that the returned ID is always a valid
    /// ID when `current` refers to a valid ID. Moreover, the transition
    /// function must be defined for all possible values of `input`.
    ///
    /// # Panics
    ///
    /// If the given ID does not refer to a valid state, then this routine
    /// may panic but it also may not panic and instead return an invalid ID.
    /// However, if the caller provides an invalid ID then this must never
    /// sacrifice memory safety.
    ///
    /// # Example
    ///
    /// This shows a simplistic example for walking a DFA for a given haystack
    /// by using the `next_state` method.
    ///
    /// ```
    /// use regex_automata::dfa::{Automaton, dense};
    ///
    /// let dfa = dense::DFA::new(r"[a-z]+r")?;
    /// let haystack = "bar".as_bytes();
    ///
    /// // The start state is determined by inspecting the position and the
    /// // initial bytes of the haystack.
    /// let mut state = dfa.start_state_forward(
    ///     None, haystack, 0, haystack.len(),
    /// );
    /// // Walk all the bytes in the haystack.
    /// for &b in haystack {
    ///     state = dfa.next_state(state, b);
    /// }
    /// // Matches are always delayed by 1 byte, so we must explicitly walk the
    /// // special "EOI" transition at the end of the search.
    /// state = dfa.next_eoi_state(state);
    /// assert!(dfa.is_match_state(state));
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn next_state(&self, current: StateID, input: u8) -> StateID;

    /// Transitions from the current state to the next state, given the next
    /// byte of input.
    ///
    /// Unlike [`Automaton::next_state`], implementations may implement this
    /// more efficiently by assuming that the `current` state ID is valid.
    /// Typically, this manifests by eliding bounds checks.
    ///
    /// # Safety
    ///
    /// Callers of this method must guarantee that `current` refers to a valid
    /// state ID. If `current` is not a valid state ID for this automaton, then
    /// calling this routine may result in undefined behavior.
    ///
    /// If `current` is valid, then implementations must guarantee that the ID
    /// returned is valid for all possible values of `input`.
    unsafe fn next_state_unchecked(
        &self,
        current: StateID,
        input: u8,
    ) -> StateID;

    /// Transitions from the current state to the next state for the special
    /// EOI symbol.
    ///
    /// Implementations must guarantee that the returned ID is always a valid
    /// ID when `current` refers to a valid ID.
    ///
    /// This routine must be called at the end of every search in a correct
    /// implementation of search. Namely, DFAs in this crate delay matches
    /// by one byte in order to support look-around operators. Thus, after
    /// reaching the end of a haystack, a search implementation must follow one
    /// last EOI transition.
    ///
    /// It is best to think of EOI as an additional symbol in the alphabet of
    /// a DFA that is distinct from every other symbol. That is, the alphabet
    /// of DFAs in this crate has a logical size of 257 instead of 256, where
    /// 256 corresponds to every possible inhabitant of `u8`. (In practice, the
    /// physical alphabet size may be smaller because of alphabet compression
    /// via equivalence classes, but EOI is always represented somehow in the
    /// alphabet.)
    ///
    /// # Panics
    ///
    /// If the given ID does not refer to a valid state, then this routine
    /// may panic but it also may not panic and instead return an invalid ID.
    /// However, if the caller provides an invalid ID then this must never
    /// sacrifice memory safety.
    ///
    /// # Example
    ///
    /// This shows a simplistic example for walking a DFA for a given haystack,
    /// and then finishing the search with the final EOI transition.
    ///
    /// ```
    /// use regex_automata::dfa::{Automaton, dense};
    ///
    /// let dfa = dense::DFA::new(r"[a-z]+r")?;
    /// let haystack = "bar".as_bytes();
    ///
    /// // The start state is determined by inspecting the position and the
    /// // initial bytes of the haystack.
    /// let mut state = dfa.start_state_forward(
    ///     None, haystack, 0, haystack.len(),
    /// );
    /// // Walk all the bytes in the haystack.
    /// for &b in haystack {
    ///     state = dfa.next_state(state, b);
    /// }
    /// // Matches are always delayed by 1 byte, so we must explicitly walk
    /// // the special "EOI" transition at the end of the search. Without this
    /// // final transition, the assert below will fail since the DFA will not
    /// // have entered a match state yet!
    /// state = dfa.next_eoi_state(state);
    /// assert!(dfa.is_match_state(state));
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn next_eoi_state(&self, current: StateID) -> StateID;

    /// Return the ID of the start state for this DFA when executing a forward
    /// search.
    ///
    /// Unlike typical DFA implementations, the start state for DFAs in this
    /// crate is dependent on a few different factors:
    ///
    /// * The pattern ID, if present. When the underlying DFA has been compiled
    /// with multiple patterns _and_ the DFA has been configured to compile
    /// an anchored start state for each pattern, then a pattern ID may be
    /// specified to execute an anchored search for that specific pattern.
    /// If `pattern_id` is invalid or if the DFA doesn't have start states
    /// compiled for each pattern, then implementations must panic. DFAs in
    /// this crate can be configured to compile start states for each pattern
    /// via
    /// [`dense::Config::starts_for_each_pattern`](crate::dfa::dense::Config::starts_for_each_pattern).
    /// * When `start > 0`, the byte at index `start - 1` may influence the
    /// start state if the regex uses `^` or `\b`.
    /// * Similarly, when `start == 0`, it may influence the start state when
    /// the regex uses `^` or `\A`.
    /// * Currently, `end` is unused.
    /// * Whether the search is a forward or reverse search. This routine can
    /// only be used for forward searches.
    ///
    /// # Panics
    ///
    /// Implementations must panic if `start..end` is not a valid sub-slice of
    /// `bytes`. Implementations must also panic if `pattern_id` is non-None
    /// and does not refer to a valid pattern, or if the DFA was not compiled
    /// with anchored start states for each pattern.
    fn start_state_forward(
        &self,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> StateID;

    /// Return the ID of the start state for this DFA when executing a reverse
    /// search.
    ///
    /// Unlike typical DFA implementations, the start state for DFAs in this
    /// crate is dependent on a few different factors:
    ///
    /// * The pattern ID, if present. When the underlying DFA has been compiled
    /// with multiple patterns _and_ the DFA has been configured to compile an
    /// anchored start state for each pattern, then a pattern ID may be
    /// specified to execute an anchored search for that specific pattern. If
    /// `pattern_id` is invalid or if the DFA doesn't have start states compiled
    /// for each pattern, then implementations must panic. DFAs in this crate
    /// can be configured to compile start states for each pattern via
    /// [`dense::Config::starts_for_each_pattern`](crate::dfa::dense::Config::starts_for_each_pattern).
    /// * When `end < bytes.len()`, the byte at index `end` may influence the
    /// start state if the regex uses `$` or `\b`.
    /// * Similarly, when `end == bytes.len()`, it may influence the start
    /// state when the regex uses `$` or `\z`.
    /// * Currently, `start` is unused.
    /// * Whether the search is a forward or reverse search. This routine can
    /// only be used for reverse searches.
    ///
    /// # Panics
    ///
    /// Implementations must panic if `start..end` is not a valid sub-slice of
    /// `bytes`. Implementations must also panic if `pattern_id` is non-None
    /// and does not refer to a valid pattern, or if the DFA was not compiled
    /// with anchored start states for each pattern.
    fn start_state_reverse(
        &self,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> StateID;

    /// Returns true if and only if the given identifier corresponds to a
    /// "special" state. A special state is one or more of the following:
    /// a dead state, a quit state, a match state, a start state or an
    /// accelerated state.
    ///
    /// A correct implementation _may_ always return false for states that
    /// are either start states or accelerated states, since that information
    /// is only intended to be used for optimization purposes. Correct
    /// implementations must return true if the state is a dead, quit or match
    /// state. This is because search routines using this trait must be able
    /// to rely on `is_special_state` as an indicator that a state may need
    /// special treatment. (For example, when a search routine sees a dead
    /// state, it must terminate.)
    ///
    /// This routine permits search implementations to use a single branch to
    /// check whether a state needs special attention before executing the next
    /// transition. The example below shows how to do this.
    ///
    /// # Example
    ///
    /// This example shows how `is_special_state` can be used to implement a
    /// correct search routine with minimal branching. In particular, this
    /// search routine implements "leftmost" matching, which means that it
    /// doesn't immediately stop once a match is found. Instead, it continues
    /// until it reaches a dead state.
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, dense},
    ///     HalfMatch, MatchError, PatternID,
    /// };
    ///
    /// fn find_leftmost_first<A: Automaton>(
    ///     dfa: &A,
    ///     haystack: &[u8],
    /// ) -> Result<Option<HalfMatch>, MatchError> {
    ///     // The start state is determined by inspecting the position and the
    ///     // initial bytes of the haystack. Note that start states can never
    ///     // be match states (since DFAs in this crate delay matches by 1
    ///     // byte), so we don't need to check if the start state is a match.
    ///     let mut state = dfa.start_state_forward(
    ///         None, haystack, 0, haystack.len(),
    ///     );
    ///     let mut last_match = None;
    ///     // Walk all the bytes in the haystack. We can quit early if we see
    ///     // a dead or a quit state. The former means the automaton will
    ///     // never transition to any other state. The latter means that the
    ///     // automaton entered a condition in which its search failed.
    ///     for (i, &b) in haystack.iter().enumerate() {
    ///         state = dfa.next_state(state, b);
    ///         if dfa.is_special_state(state) {
    ///             if dfa.is_match_state(state) {
    ///                 last_match = Some(HalfMatch::new(
    ///                     dfa.match_pattern(state, 0),
    ///                     i,
    ///                 ));
    ///             } else if dfa.is_dead_state(state) {
    ///                 return Ok(last_match);
    ///             } else if dfa.is_quit_state(state) {
    ///                 // It is possible to enter into a quit state after
    ///                 // observing a match has occurred. In that case, we
    ///                 // should return the match instead of an error.
    ///                 if last_match.is_some() {
    ///                     return Ok(last_match);
    ///                 }
    ///                 return Err(MatchError::Quit { byte: b, offset: i });
    ///             }
    ///             // Implementors may also want to check for start or accel
    ///             // states and handle them differently for performance
    ///             // reasons. But it is not necessary for correctness.
    ///         }
    ///     }
    ///     // Matches are always delayed by 1 byte, so we must explicitly walk
    ///     // the special "EOI" transition at the end of the search.
    ///     state = dfa.next_eoi_state(state);
    ///     if dfa.is_match_state(state) {
    ///         last_match = Some(HalfMatch::new(
    ///             dfa.match_pattern(state, 0),
    ///             haystack.len(),
    ///         ));
    ///     }
    ///     Ok(last_match)
    /// }
    ///
    /// // We use a greedy '+' operator to show how the search doesn't just
    /// // stop once a match is detected. It continues extending the match.
    /// // Using '[a-z]+?' would also work as expected and stop the search
    /// // early. Greediness is built into the automaton.
    /// let dfa = dense::DFA::new(r"[a-z]+")?;
    /// let haystack = "123 foobar 4567".as_bytes();
    /// let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
    /// assert_eq!(mat.pattern().as_usize(), 0);
    /// assert_eq!(mat.offset(), 10);
    ///
    /// // Here's another example that tests our handling of the special EOI
    /// // transition. This will fail to find a match if we don't call
    /// // 'next_eoi_state' at the end of the search since the match isn't
    /// // found until the final byte in the haystack.
    /// let dfa = dense::DFA::new(r"[0-9]{4}")?;
    /// let haystack = "123 foobar 4567".as_bytes();
    /// let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
    /// assert_eq!(mat.pattern().as_usize(), 0);
    /// assert_eq!(mat.offset(), 15);
    ///
    /// // And note that our search implementation above automatically works
    /// // with multi-DFAs. Namely, `dfa.match_pattern(match_state, 0)` selects
    /// // the appropriate pattern ID for us.
    /// let dfa = dense::DFA::new_many(&[r"[a-z]+", r"[0-9]+"])?;
    /// let haystack = "123 foobar 4567".as_bytes();
    /// let mat = find_leftmost_first(&dfa, haystack)?.unwrap();
    /// assert_eq!(mat.pattern().as_usize(), 1);
    /// assert_eq!(mat.offset(), 3);
    /// let mat = find_leftmost_first(&dfa, &haystack[3..])?.unwrap();
    /// assert_eq!(mat.pattern().as_usize(), 0);
    /// assert_eq!(mat.offset(), 7);
    /// let mat = find_leftmost_first(&dfa, &haystack[10..])?.unwrap();
    /// assert_eq!(mat.pattern().as_usize(), 1);
    /// assert_eq!(mat.offset(), 5);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn is_special_state(&self, id: StateID) -> bool;

    /// Returns true if and only if the given identifier corresponds to a dead
    /// state. When a DFA enters a dead state, it is impossible to leave. That
    /// is, every transition on a dead state by definition leads back to the
    /// same dead state.
    ///
    /// In practice, the dead state always corresponds to the identifier `0`.
    /// Moreover, in practice, there is only one dead state.
    ///
    /// The existence of a dead state is not strictly required in the classical
    /// model of finite state machines, where one generally only cares about
    /// the question of whether an input sequence matches or not. Dead states
    /// are not needed to answer that question, since one can immediately quit
    /// as soon as one enters a final or "match" state. However, we don't just
    /// care about matches but also care about the location of matches, and
    /// more specifically, care about semantics like "greedy" matching.
    ///
    /// For example, given the pattern `a+` and the input `aaaz`, the dead
    /// state won't be entered until the state machine reaches `z` in the
    /// input, at which point, the search routine can quit. But without the
    /// dead state, the search routine wouldn't know when to quit. In a
    /// classical representation, the search routine would stop after seeing
    /// the first `a` (which is when the search would enter a match state). But
    /// this wouldn't implement "greedy" matching where `a+` matches as many
    /// `a`'s as possible.
    ///
    /// # Example
    ///
    /// See the example for [`Automaton::is_special_state`] for how to use this
    /// method correctly.
    fn is_dead_state(&self, id: StateID) -> bool;

    /// Returns true if and only if the given identifier corresponds to a quit
    /// state. A quit state is like a dead state (it has no transitions other
    /// than to itself), except it indicates that the DFA failed to complete
    /// the search. When this occurs, callers can neither accept or reject that
    /// a match occurred.
    ///
    /// In practice, the quit state always corresponds to the state immediately
    /// following the dead state. (Which is not usually represented by `1`,
    /// since state identifiers are pre-multiplied by the state machine's
    /// alphabet stride, and the alphabet stride varies between DFAs.)
    ///
    /// By default, state machines created by this crate will never enter a
    /// quit state. Since entering a quit state is the only way for a DFA
    /// in this crate to fail at search time, it follows that the default
    /// configuration can never produce a match error. Nevertheless, handling
    /// quit states is necessary to correctly support all configurations in
    /// this crate.
    ///
    /// The typical way in which a quit state can occur is when heuristic
    /// support for Unicode word boundaries is enabled via the
    /// [`dense::Config::unicode_word_boundary`](crate::dfa::dense::Config::unicode_word_boundary)
    /// option. But other options, like the lower level
    /// [`dense::Config::quit`](crate::dfa::dense::Config::quit)
    /// configuration, can also result in a quit state being entered. The
    /// purpose of the quit state is to provide a way to execute a fast DFA
    /// in common cases while delegating to slower routines when the DFA quits.
    ///
    /// The default search implementations provided by this crate will return
    /// a [`MatchError::Quit`](crate::MatchError::Quit) error when a quit state
    /// is entered.
    ///
    /// # Example
    ///
    /// See the example for [`Automaton::is_special_state`] for how to use this
    /// method correctly.
    fn is_quit_state(&self, id: StateID) -> bool;

    /// Returns true if and only if the given identifier corresponds to a
    /// match state. A match state is also referred to as a "final" state and
    /// indicates that a match has been found.
    ///
    /// If all you care about is whether a particular pattern matches in the
    /// input sequence, then a search routine can quit early as soon as the
    /// machine enters a match state. However, if you're looking for the
    /// standard "leftmost-first" match location, then search _must_ continue
    /// until either the end of the input or until the machine enters a dead
    /// state. (Since either condition implies that no other useful work can
    /// be done.) Namely, when looking for the location of a match, then
    /// search implementations should record the most recent location in
    /// which a match state was entered, but otherwise continue executing the
    /// search as normal. (The search may even leave the match state.) Once
    /// the termination condition is reached, the most recently recorded match
    /// location should be returned.
    ///
    /// Finally, one additional power given to match states in this crate
    /// is that they are always associated with a specific pattern in order
    /// to support multi-DFAs. See [`Automaton::match_pattern`] for more
    /// details and an example for how to query the pattern associated with a
    /// particular match state.
    ///
    /// # Example
    ///
    /// See the example for [`Automaton::is_special_state`] for how to use this
    /// method correctly.
    fn is_match_state(&self, id: StateID) -> bool;

    /// Returns true if and only if the given identifier corresponds to a
    /// start state. A start state is a state in which a DFA begins a search.
    /// All searches begin in a start state. Moreover, since all matches are
    /// delayed by one byte, a start state can never be a match state.
    ///
    /// The main role of a start state is, as mentioned, to be a starting
    /// point for a DFA. This starting point is determined via one of
    /// [`Automaton::start_state_forward`] or
    /// [`Automaton::start_state_reverse`], depending on whether one is doing
    /// a forward or a reverse search, respectively.
    ///
    /// A secondary use of start states is for prefix acceleration. Namely,
    /// while executing a search, if one detects that you're in a start state,
    /// then it may be faster to look for the next match of a prefix of the
    /// pattern, if one exists. If a prefix exists and since all matches must
    /// begin with that prefix, then skipping ahead to occurrences of that
    /// prefix may be much faster than executing the DFA.
    ///
    /// # Example
    ///
    /// This example shows how to implement your own search routine that does
    /// a prefix search whenever the search enters a start state.
    ///
    /// Note that you do not need to implement your own search routine to
    /// make use of prefilters like this. The search routines provided
    /// by this crate already implement prefilter support via the
    /// [`Prefilter`](crate::util::prefilter::Prefilter) trait. The various
    /// `find_*_at` routines on this trait support the `Prefilter` trait
    /// through [`Scanner`](crate::util::prefilter::Scanner)s. This example is
    /// meant to show how you might deal with prefilters in a simplified case
    /// if you are implementing your own search routine.
    ///
    /// ```
    /// use regex_automata::{
    ///     MatchError, PatternID,
    ///     dfa::{Automaton, dense},
    ///     HalfMatch,
    /// };
    ///
    /// fn find_byte(slice: &[u8], at: usize, byte: u8) -> Option<usize> {
    ///     // Would be faster to use the memchr crate, but this is still
    ///     // faster than running through the DFA.
    ///     slice[at..].iter().position(|&b| b == byte).map(|i| at + i)
    /// }
    ///
    /// fn find_leftmost_first<A: Automaton>(
    ///     dfa: &A,
    ///     haystack: &[u8],
    ///     prefix_byte: Option<u8>,
    /// ) -> Result<Option<HalfMatch>, MatchError> {
    ///     // See the Automaton::is_special_state example for similar code
    ///     // with more comments.
    ///
    ///     let mut state = dfa.start_state_forward(
    ///         None, haystack, 0, haystack.len(),
    ///     );
    ///     let mut last_match = None;
    ///     let mut pos = 0;
    ///     while pos < haystack.len() {
    ///         let b = haystack[pos];
    ///         state = dfa.next_state(state, b);
    ///         pos += 1;
    ///         if dfa.is_special_state(state) {
    ///             if dfa.is_match_state(state) {
    ///                 last_match = Some(HalfMatch::new(
    ///                     dfa.match_pattern(state, 0),
    ///                     pos - 1,
    ///                 ));
    ///             } else if dfa.is_dead_state(state) {
    ///                 return Ok(last_match);
    ///             } else if dfa.is_quit_state(state) {
    ///                 // It is possible to enter into a quit state after
    ///                 // observing a match has occurred. In that case, we
    ///                 // should return the match instead of an error.
    ///                 if last_match.is_some() {
    ///                     return Ok(last_match);
    ///                 }
    ///                 return Err(MatchError::Quit {
    ///                     byte: b, offset: pos - 1,
    ///                 });
    ///             } else if dfa.is_start_state(state) {
    ///                 // If we're in a start state and know all matches begin
    ///                 // with a particular byte, then we can quickly skip to
    ///                 // candidate matches without running the DFA through
    ///                 // every byte inbetween.
    ///                 if let Some(prefix_byte) = prefix_byte {
    ///                     pos = match find_byte(haystack, pos, prefix_byte) {
    ///                         Some(pos) => pos,
    ///                         None => break,
    ///                     };
    ///                 }
    ///             }
    ///         }
    ///     }
    ///     // Matches are always delayed by 1 byte, so we must explicitly walk
    ///     // the special "EOI" transition at the end of the search.
    ///     state = dfa.next_eoi_state(state);
    ///     if dfa.is_match_state(state) {
    ///         last_match = Some(HalfMatch::new(
    ///             dfa.match_pattern(state, 0),
    ///             haystack.len(),
    ///         ));
    ///     }
    ///     Ok(last_match)
    /// }
    ///
    /// // In this example, it's obvious that all occurrences of our pattern
    /// // begin with 'Z', so we pass in 'Z'.
    /// let dfa = dense::DFA::new(r"Z[a-z]+")?;
    /// let haystack = "123 foobar Zbaz quux".as_bytes();
    /// let mat = find_leftmost_first(&dfa, haystack, Some(b'Z'))?.unwrap();
    /// assert_eq!(mat.pattern().as_usize(), 0);
    /// assert_eq!(mat.offset(), 15);
    ///
    /// // But note that we don't need to pass in a prefix byte. If we don't,
    /// // then the search routine does no acceleration.
    /// let mat = find_leftmost_first(&dfa, haystack, None)?.unwrap();
    /// assert_eq!(mat.pattern().as_usize(), 0);
    /// assert_eq!(mat.offset(), 15);
    ///
    /// // However, if we pass an incorrect byte, then the prefix search will
    /// // result in incorrect results.
    /// assert_eq!(find_leftmost_first(&dfa, haystack, Some(b'X'))?, None);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn is_start_state(&self, id: StateID) -> bool;

    /// Returns true if and only if the given identifier corresponds to an
    /// accelerated state.
    ///
    /// An accelerated state is a special optimization
    /// trick implemented by this crate. Namely, if
    /// [`dense::Config::accelerate`](crate::dfa::dense::Config::accelerate) is
    /// enabled (and it is by default), then DFAs generated by this crate will
    /// tag states meeting certain characteristics as accelerated. States meet
    /// this criteria whenever most of their transitions are self-transitions.
    /// That is, transitions that loop back to the same state. When a small
    /// number of transitions aren't self-transitions, then it follows that
    /// there are only a small number of bytes that can cause the DFA to leave
    /// that state. Thus, there is an opportunity to look for those bytes
    /// using more optimized routines rather than continuing to run through
    /// the DFA. This trick is similar to the prefilter idea described in
    /// the documentation of [`Automaton::is_start_state`] with two main
    /// differences:
    ///
    /// 1. It is more limited since acceleration only applies to single bytes.
    /// This means states are rarely accelerated when Unicode mode is enabled
    /// (which is enabled by default).
    /// 2. It can occur anywhere in the DFA, which increases optimization
    /// opportunities.
    ///
    /// Like the prefilter idea, the main downside (and a possible reason to
    /// disable it) is that it can lead to worse performance in some cases.
    /// Namely, if a state is accelerated for very common bytes, then the
    /// overhead of checking for acceleration and using the more optimized
    /// routines to look for those bytes can cause overall performance to be
    /// worse than if acceleration wasn't enabled at all.
    ///
    /// A simple example of a regex that has an accelerated state is
    /// `(?-u)[^a]+a`. Namely, the `[^a]+` sub-expression gets compiled down
    /// into a single state where all transitions except for `a` loop back to
    /// itself, and where `a` is the only transition (other than the special
    /// EOI transition) that goes to some other state. Thus, this state can
    /// be accelerated and implemented more efficiently by calling an
    /// optimized routine like `memchr` with `a` as the needle. Notice that
    /// the `(?-u)` to disable Unicode is necessary here, as without it,
    /// `[^a]` will match any UTF-8 encoding of any Unicode scalar value other
    /// than `a`. This more complicated expression compiles down to many DFA
    /// states and the simple acceleration optimization is no longer available.
    ///
    /// Typically, this routine is used to guard calls to
    /// [`Automaton::accelerator`], which returns the accelerated bytes for
    /// the specified state.
    fn is_accel_state(&self, id: StateID) -> bool;

    /// Returns the total number of patterns compiled into this DFA.
    ///
    /// In the case of a DFA that contains no patterns, this must return `0`.
    ///
    /// # Example
    ///
    /// This example shows the pattern count for a DFA that never matches:
    ///
    /// ```
    /// use regex_automata::dfa::{Automaton, dense::DFA};
    ///
    /// let dfa: DFA<Vec<u32>> = DFA::never_match()?;
    /// assert_eq!(dfa.pattern_count(), 0);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    ///
    /// And another example for a DFA that matches at every position:
    ///
    /// ```
    /// use regex_automata::dfa::{Automaton, dense::DFA};
    ///
    /// let dfa: DFA<Vec<u32>> = DFA::always_match()?;
    /// assert_eq!(dfa.pattern_count(), 1);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    ///
    /// And finally, a DFA that was constructed from multiple patterns:
    ///
    /// ```
    /// use regex_automata::dfa::{Automaton, dense::DFA};
    ///
    /// let dfa = DFA::new_many(&["[0-9]+", "[a-z]+", "[A-Z]+"])?;
    /// assert_eq!(dfa.pattern_count(), 3);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn pattern_count(&self) -> usize;

    /// Returns the total number of patterns that match in this state.
    ///
    /// If the given state is not a match state, then implementations may
    /// panic.
    ///
    /// If the DFA was compiled with one pattern, then this must necessarily
    /// always return `1` for all match states.
    ///
    /// Implementations must guarantee that [`Automaton::match_pattern`] can
    /// be called with indices up to (but not including) the count returned by
    /// this routine without panicking.
    ///
    /// # Panics
    ///
    /// Implementations are permitted to panic if the provided state ID does
    /// not correspond to a match state.
    ///
    /// # Example
    ///
    /// This example shows a simple instance of implementing overlapping
    /// matches. In particular, it shows not only how to determine how many
    /// patterns have matched in a particular state, but also how to access
    /// which specific patterns have matched.
    ///
    /// Notice that we must use [`MatchKind::All`](crate::MatchKind::All)
    /// when building the DFA. If we used
    /// [`MatchKind::LeftmostFirst`](crate::MatchKind::LeftmostFirst)
    /// instead, then the DFA would not be constructed in a way that supports
    /// overlapping matches. (It would only report a single pattern that
    /// matches at any particular point in time.)
    ///
    /// Another thing to take note of is the patterns used and the order in
    /// which the pattern IDs are reported. In the example below, pattern `3`
    /// is yielded first. Why? Because it corresponds to the match that
    /// appears first. Namely, the `@` symbol is part of `\S+` but not part
    /// of any of the other patterns. Since the `\S+` pattern has a match that
    /// starts to the left of any other pattern, its ID is returned before any
    /// other.
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, dense},
    ///     MatchKind,
    /// };
    ///
    /// let dfa = dense::Builder::new()
    ///     .configure(dense::Config::new().match_kind(MatchKind::All))
    ///     .build_many(&[
    ///         r"\w+", r"[a-z]+", r"[A-Z]+", r"\S+",
    ///     ])?;
    /// let haystack = "@bar".as_bytes();
    ///
    /// // The start state is determined by inspecting the position and the
    /// // initial bytes of the haystack.
    /// let mut state = dfa.start_state_forward(
    ///     None, haystack, 0, haystack.len(),
    /// );
    /// // Walk all the bytes in the haystack.
    /// for &b in haystack {
    ///     state = dfa.next_state(state, b);
    /// }
    /// state = dfa.next_eoi_state(state);
    ///
    /// assert!(dfa.is_match_state(state));
    /// assert_eq!(dfa.match_count(state), 3);
    /// // The following calls are guaranteed to not panic since `match_count`
    /// // returned `3` above.
    /// assert_eq!(dfa.match_pattern(state, 0).as_usize(), 3);
    /// assert_eq!(dfa.match_pattern(state, 1).as_usize(), 0);
    /// assert_eq!(dfa.match_pattern(state, 2).as_usize(), 1);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn match_count(&self, id: StateID) -> usize;

    /// Returns the pattern ID corresponding to the given match index in the
    /// given state.
    ///
    /// See [`Automaton::match_count`] for an example of how to use this
    /// method correctly. Note that if you know your DFA is compiled with a
    /// single pattern, then this routine is never necessary since it will
    /// always return a pattern ID of `0` for an index of `0` when `id`
    /// corresponds to a match state.
    ///
    /// Typically, this routine is used when implementing an overlapping
    /// search, as the example for `Automaton::match_count` does.
    ///
    /// # Panics
    ///
    /// If the state ID is not a match state or if the match index is out
    /// of bounds for the given state, then this routine may either panic
    /// or produce an incorrect result. If the state ID is correct and the
    /// match index is correct, then this routine must always produce a valid
    /// `PatternID`.
    fn match_pattern(&self, id: StateID, index: usize) -> PatternID;

    /// Return a slice of bytes to accelerate for the given state, if possible.
    ///
    /// If the given state has no accelerator, then an empty slice must be
    /// returned. If `Automaton::is_accel_state` returns true for the given
    /// ID, then this routine _must_ return a non-empty slice, but it is not
    /// required to do so.
    ///
    /// If the given ID is not a valid state ID for this automaton, then
    /// implementations may panic or produce incorrect results.
    ///
    /// See [`Automaton::is_accel_state`] for more details on state
    /// acceleration.
    ///
    /// By default, this method will always return an empty slice.
    ///
    /// # Example
    ///
    /// This example shows a contrived case in which we build a regex that we
    /// know is accelerated and extract the accelerator from a state.
    ///
    /// ```
    /// use regex_automata::{
    ///     nfa::thompson,
    ///     dfa::{Automaton, dense},
    ///     util::id::StateID,
    ///     SyntaxConfig,
    /// };
    ///
    /// let dfa = dense::Builder::new()
    ///     // We disable Unicode everywhere and permit the regex to match
    ///     // invalid UTF-8. e.g., `[^abc]` matches `\xFF`, which is not valid
    ///     // UTF-8.
    ///     .syntax(SyntaxConfig::new().unicode(false).utf8(false))
    ///     // This makes the implicit `(?s:.)*?` prefix added to the regex
    ///     // match through arbitrary bytes instead of being UTF-8 aware. This
    ///     // isn't necessary to get acceleration to work in this case, but
    ///     // it does make the DFA substantially simpler.
    ///     .thompson(thompson::Config::new().utf8(false))
    ///     .build("[^abc]+a")?;
    ///
    /// // Here we just pluck out the state that we know is accelerated.
    /// // While the stride calculations are something that can be relied
    /// // on by callers, the specific position of the accelerated state is
    /// // implementation defined.
    /// //
    /// // N.B. We get '3' by inspecting the state machine using 'regex-cli'.
    /// // e.g., try `regex-cli debug dfa dense '[^abc]+a' -BbUC`.
    /// let id = StateID::new(3 * dfa.stride()).unwrap();
    /// let accelerator = dfa.accelerator(id);
    /// // The `[^abc]+` sub-expression permits [a, b, c] to be accelerated.
    /// assert_eq!(accelerator, &[b'a', b'b', b'c']);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn accelerator(&self, _id: StateID) -> &[u8] {
        &[]
    }

    /// Executes a forward search and returns the end position of the first
    /// match that is found as early as possible. If no match exists, then
    /// `None` is returned.
    ///
    /// This routine stops scanning input as soon as the search observes a
    /// match state. This is useful for implementing boolean `is_match`-like
    /// routines, where as little work is done as possible.
    ///
    /// See [`Automaton::find_earliest_fwd_at`] for additional functionality,
    /// such as providing a prefilter, a specific pattern to match and the
    /// bounds of the search within the haystack. This routine is meant as
    /// a convenience for common cases where the additional functionality is
    /// not needed.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Example
    ///
    /// This example shows how to use this method with a
    /// [`dense::DFA`](crate::dfa::dense::DFA). In particular, it demonstrates
    /// how the position returned might differ from what one might expect when
    /// executing a traditional leftmost search.
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, dense},
    ///     HalfMatch,
    /// };
    ///
    /// let dfa = dense::DFA::new("foo[0-9]+")?;
    /// // Normally, the end of the leftmost first match here would be 8,
    /// // corresponding to the end of the input. But the "earliest" semantics
    /// // this routine cause it to stop as soon as a match is known, which
    /// // occurs once 'foo[0-9]' has matched.
    /// let expected = HalfMatch::must(0, 4);
    /// assert_eq!(Some(expected), dfa.find_earliest_fwd(b"foo12345")?);
    ///
    /// let dfa = dense::DFA::new("abc|a")?;
    /// // Normally, the end of the leftmost first match here would be 3,
    /// // but the shortest match semantics detect a match earlier.
    /// let expected = HalfMatch::must(0, 1);
    /// assert_eq!(Some(expected), dfa.find_earliest_fwd(b"abc")?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    fn find_earliest_fwd(
        &self,
        bytes: &[u8],
    ) -> Result<Option<HalfMatch>, MatchError> {
        self.find_earliest_fwd_at(None, None, bytes, 0, bytes.len())
    }

    /// Executes a reverse search and returns the start position of the first
    /// match that is found as early as possible. If no match exists, then
    /// `None` is returned.
    ///
    /// This routine stops scanning input as soon as the search observes a
    /// match state.
    ///
    /// Note that while it is not technically necessary to build a reverse
    /// automaton to use a reverse search, it is likely that you'll want to do
    /// so. Namely, the typical use of a reverse search is to find the starting
    /// location of a match once its end is discovered from a forward search. A
    /// reverse DFA automaton can be built by configuring the intermediate NFA
    /// to be reversed via
    /// [`nfa::thompson::Config::reverse`](crate::nfa::thompson::Config::reverse).
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Example
    ///
    /// This example shows how to use this method with a
    /// [`dense::DFA`](crate::dfa::dense::DFA). In particular, it demonstrates
    /// how the position returned might differ from what one might expect when
    /// executing a traditional leftmost reverse search.
    ///
    /// ```
    /// use regex_automata::{
    ///     nfa::thompson,
    ///     dfa::{Automaton, dense},
    ///     HalfMatch,
    /// };
    ///
    /// let dfa = dense::Builder::new()
    ///     .thompson(thompson::Config::new().reverse(true))
    ///     .build("[a-z]+[0-9]+")?;
    /// // Normally, the end of the leftmost first match here would be 0,
    /// // corresponding to the beginning of the input. But the "earliest"
    /// // semantics of this routine cause it to stop as soon as a match is
    /// // known, which occurs once '[a-z][0-9]+' has matched.
    /// let expected = HalfMatch::must(0, 2);
    /// assert_eq!(Some(expected), dfa.find_earliest_rev(b"foo12345")?);
    ///
    /// let dfa = dense::Builder::new()
    ///     .thompson(thompson::Config::new().reverse(true))
    ///     .build("abc|c")?;
    /// // Normally, the end of the leftmost first match here would be 0,
    /// // but the shortest match semantics detect a match earlier.
    /// let expected = HalfMatch::must(0, 2);
    /// assert_eq!(Some(expected), dfa.find_earliest_rev(b"abc")?);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    fn find_earliest_rev(
        &self,
        bytes: &[u8],
    ) -> Result<Option<HalfMatch>, MatchError> {
        self.find_earliest_rev_at(None, bytes, 0, bytes.len())
    }

    /// Executes a forward search and returns the end position of the leftmost
    /// match that is found. If no match exists, then `None` is returned.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Notes for implementors
    ///
    /// Implementors of this trait are not required to implement any particular
    /// match semantics (such as leftmost-first), which are instead manifest in
    /// the DFA's transitions.
    ///
    /// In particular, this method must continue searching even after it enters
    /// a match state. The search should only terminate once it has reached
    /// the end of the input or when it has entered a dead or quit state. Upon
    /// termination, the position of the last byte seen while still in a match
    /// state is returned.
    ///
    /// Since this trait provides an implementation for this method by default,
    /// it's unlikely that one will need to implement this.
    ///
    /// # Example
    ///
    /// This example shows how to use this method with a
    /// [`dense::DFA`](crate::dfa::dense::DFA). By default, a dense DFA uses
    /// "leftmost first" match semantics.
    ///
    /// Leftmost first match semantics corresponds to the match with the
    /// smallest starting offset, but where the end offset is determined by
    /// preferring earlier branches in the original regular expression. For
    /// example, `Sam|Samwise` will match `Sam` in `Samwise`, but `Samwise|Sam`
    /// will match `Samwise` in `Samwise`.
    ///
    /// Generally speaking, the "leftmost first" match is how most backtracking
    /// regular expressions tend to work. This is in contrast to POSIX-style
    /// regular expressions that yield "leftmost longest" matches. Namely,
    /// both `Sam|Samwise` and `Samwise|Sam` match `Samwise` when using
    /// leftmost longest semantics. (This crate does not currently support
    /// leftmost longest semantics.)
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, dense},
    ///     HalfMatch,
    /// };
    ///
    /// let dfa = dense::DFA::new("foo[0-9]+")?;
    /// let expected = HalfMatch::must(0, 8);
    /// assert_eq!(Some(expected), dfa.find_leftmost_fwd(b"foo12345")?);
    ///
    /// // Even though a match is found after reading the first byte (`a`),
    /// // the leftmost first match semantics demand that we find the earliest
    /// // match that prefers earlier parts of the pattern over latter parts.
    /// let dfa = dense::DFA::new("abc|a")?;
    /// let expected = HalfMatch::must(0, 3);
    /// assert_eq!(Some(expected), dfa.find_leftmost_fwd(b"abc")?);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    fn find_leftmost_fwd(
        &self,
        bytes: &[u8],
    ) -> Result<Option<HalfMatch>, MatchError> {
        self.find_leftmost_fwd_at(None, None, bytes, 0, bytes.len())
    }

    /// Executes a reverse search and returns the start of the position of the
    /// leftmost match that is found. If no match exists, then `None` is
    /// returned.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Notes for implementors
    ///
    /// Implementors of this trait are not required to implement any particular
    /// match semantics (such as leftmost-first), which are instead manifest in
    /// the DFA's transitions.
    ///
    /// In particular, this method must continue searching even after it enters
    /// a match state. The search should only terminate once it has reached
    /// the end of the input or when it has entered a dead or quit state. Upon
    /// termination, the position of the last byte seen while still in a match
    /// state is returned.
    ///
    /// Since this trait provides an implementation for this method by default,
    /// it's unlikely that one will need to implement this.
    ///
    /// # Example
    ///
    /// This example shows how to use this method with a
    /// [`dense::DFA`](crate::dfa::dense::DFA). In particular, this routine
    /// is principally useful when used in conjunction with the
    /// [`nfa::thompson::Config::reverse`](crate::nfa::thompson::Config::reverse)
    /// configuration. In general, it's unlikely to be correct to use both
    /// `find_leftmost_fwd` and `find_leftmost_rev` with the same DFA since any
    /// particular DFA will only support searching in one direction with
    /// respect to the pattern.
    ///
    /// ```
    /// use regex_automata::{
    ///     nfa::thompson,
    ///     dfa::{Automaton, dense},
    ///     HalfMatch,
    /// };
    ///
    /// let dfa = dense::Builder::new()
    ///     .thompson(thompson::Config::new().reverse(true))
    ///     .build("foo[0-9]+")?;
    /// let expected = HalfMatch::must(0, 0);
    /// assert_eq!(Some(expected), dfa.find_leftmost_rev(b"foo12345")?);
    ///
    /// // Even though a match is found after reading the last byte (`c`),
    /// // the leftmost first match semantics demand that we find the earliest
    /// // match that prefers earlier parts of the pattern over latter parts.
    /// let dfa = dense::Builder::new()
    ///     .thompson(thompson::Config::new().reverse(true))
    ///     .build("abc|c")?;
    /// let expected = HalfMatch::must(0, 0);
    /// assert_eq!(Some(expected), dfa.find_leftmost_rev(b"abc")?);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    fn find_leftmost_rev(
        &self,
        bytes: &[u8],
    ) -> Result<Option<HalfMatch>, MatchError> {
        self.find_leftmost_rev_at(None, bytes, 0, bytes.len())
    }

    /// Executes an overlapping forward search and returns the end position of
    /// matches as they are found. If no match exists, then `None` is returned.
    ///
    /// This routine is principally only useful when searching for multiple
    /// patterns on inputs where multiple patterns may match the same regions
    /// of text. In particular, callers must preserve the automaton's search
    /// state from prior calls so that the implementation knows where the last
    /// match occurred.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Example
    ///
    /// This example shows how to run a basic overlapping search with a
    /// [`dense::DFA`](crate::dfa::dense::DFA). Notice that we build the
    /// automaton with a `MatchKind::All` configuration. Overlapping searches
    /// are unlikely to work as one would expect when using the default
    /// `MatchKind::LeftmostFirst` match semantics, since leftmost-first
    /// matching is fundamentally incompatible with overlapping searches.
    /// Namely, overlapping searches need to report matches as they are seen,
    /// where as leftmost-first searches will continue searching even after a
    /// match has been observed in order to find the conventional end position
    /// of the match. More concretely, leftmost-first searches use dead states
    /// to terminate a search after a specific match can no longer be extended.
    /// Overlapping searches instead do the opposite by continuing the search
    /// to find totally new matches (potentially of other patterns).
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, OverlappingState, dense},
    ///     HalfMatch,
    ///     MatchKind,
    /// };
    ///
    /// let dfa = dense::Builder::new()
    ///     .configure(dense::Config::new().match_kind(MatchKind::All))
    ///     .build_many(&[r"\w+$", r"\S+$"])?;
    /// let haystack = "@foo".as_bytes();
    /// let mut state = OverlappingState::start();
    ///
    /// let expected = Some(HalfMatch::must(1, 4));
    /// let got = dfa.find_overlapping_fwd(haystack, &mut state)?;
    /// assert_eq!(expected, got);
    ///
    /// // The first pattern also matches at the same position, so re-running
    /// // the search will yield another match. Notice also that the first
    /// // pattern is returned after the second. This is because the second
    /// // pattern begins its match before the first, is therefore an earlier
    /// // match and is thus reported first.
    /// let expected = Some(HalfMatch::must(0, 4));
    /// let got = dfa.find_overlapping_fwd(haystack, &mut state)?;
    /// assert_eq!(expected, got);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    fn find_overlapping_fwd(
        &self,
        bytes: &[u8],
        state: &mut OverlappingState,
    ) -> Result<Option<HalfMatch>, MatchError> {
        self.find_overlapping_fwd_at(None, None, bytes, 0, bytes.len(), state)
    }

    /// Executes a forward search and returns the end position of the first
    /// match that is found as early as possible. If no match exists, then
    /// `None` is returned.
    ///
    /// This routine stops scanning input as soon as the search observes a
    /// match state. This is useful for implementing boolean `is_match`-like
    /// routines, where as little work is done as possible.
    ///
    /// This is like [`Automaton::find_earliest_fwd`], except it provides some
    /// additional control over how the search is executed:
    ///
    /// * `pre` is a prefilter scanner that, when given, is used whenever the
    /// DFA enters its starting state. This is meant to speed up searches where
    /// one or a small number of literal prefixes are known.
    /// * `pattern_id` specifies a specific pattern in the DFA to run an
    /// anchored search for. If not given, then a search for any pattern is
    /// performed. For DFAs built by this crate,
    /// [`dense::Config::starts_for_each_pattern`](crate::dfa::dense::Config::starts_for_each_pattern)
    /// must be enabled to use this functionality.
    /// * `start` and `end` permit searching a specific region of the haystack
    /// `bytes`. This is useful when implementing an iterator over matches
    /// within the same haystack, which cannot be done correctly by simply
    /// providing a subslice of `bytes`. (Because the existence of look-around
    /// operations such as `\b`, `^` and `$` need to take the surrounding
    /// context into account. This cannot be done if the haystack doesn't
    /// contain it.)
    ///
    /// The examples below demonstrate each of these additional parameters.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Panics
    ///
    /// This routine must panic if a `pattern_id` is given and the underlying
    /// DFA does not support specific pattern searches.
    ///
    /// It must also panic if the given haystack range is not valid.
    ///
    /// # Example: prefilter
    ///
    /// This example shows how to provide a prefilter for a pattern where all
    /// matches start with a `z` byte.
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, dense},
    ///     util::prefilter::{Candidate, Prefilter, Scanner, State},
    ///     HalfMatch,
    /// };
    ///
    /// #[derive(Debug)]
    /// pub struct ZPrefilter;
    ///
    /// impl Prefilter for ZPrefilter {
    ///     fn next_candidate(
    ///         &self,
    ///         _: &mut State,
    ///         haystack: &[u8],
    ///         at: usize,
    ///     ) -> Candidate {
    ///         // Try changing b'z' to b'q' and observe this test fail since
    ///         // the prefilter will skip right over the match.
    ///         match haystack.iter().position(|&b| b == b'z') {
    ///             None => Candidate::None,
    ///             Some(i) => Candidate::PossibleStartOfMatch(at + i),
    ///         }
    ///     }
    ///
    ///     fn heap_bytes(&self) -> usize {
    ///         0
    ///     }
    /// }
    ///
    /// let dfa = dense::DFA::new("z[0-9]{3}")?;
    /// let haystack = "foobar z123 q123".as_bytes();
    /// // A scanner executes a prefilter while tracking some state that helps
    /// // determine whether a prefilter is still "effective" or not.
    /// let mut scanner = Scanner::new(&ZPrefilter);
    ///
    /// let expected = Some(HalfMatch::must(0, 11));
    /// let got = dfa.find_earliest_fwd_at(
    ///     Some(&mut scanner),
    ///     None,
    ///     haystack,
    ///     0,
    ///     haystack.len(),
    /// )?;
    /// assert_eq!(expected, got);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    ///
    /// # Example: specific pattern search
    ///
    /// This example shows how to build a multi-DFA that permits searching for
    /// specific patterns.
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, dense},
    ///     HalfMatch,
    ///     PatternID,
    /// };
    ///
    /// let dfa = dense::Builder::new()
    ///     .configure(dense::Config::new().starts_for_each_pattern(true))
    ///     .build_many(&["[a-z0-9]{6}", "[a-z][a-z0-9]{5}"])?;
    /// let haystack = "foo123".as_bytes();
    ///
    /// // Since we are using the default leftmost-first match and both
    /// // patterns match at the same starting position, only the first pattern
    /// // will be returned in this case when doing a search for any of the
    /// // patterns.
    /// let expected = Some(HalfMatch::must(0, 6));
    /// let got = dfa.find_earliest_fwd_at(
    ///     None,
    ///     None,
    ///     haystack,
    ///     0,
    ///     haystack.len(),
    /// )?;
    /// assert_eq!(expected, got);
    ///
    /// // But if we want to check whether some other pattern matches, then we
    /// // can provide its pattern ID.
    /// let expected = Some(HalfMatch::must(1, 6));
    /// let got = dfa.find_earliest_fwd_at(
    ///     None,
    ///     Some(PatternID::must(1)),
    ///     haystack,
    ///     0,
    ///     haystack.len(),
    /// )?;
    /// assert_eq!(expected, got);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    ///
    /// # Example: specifying the bounds of a search
    ///
    /// This example shows how providing the bounds of a search can produce
    /// different results than simply sub-slicing the haystack.
    ///
    /// ```
    /// use regex_automata::{
    ///     dfa::{Automaton, dense},
    ///     HalfMatch,
    /// };
    ///
    /// // N.B. We disable Unicode here so that we use a simple ASCII word
    /// // boundary. Alternatively, we could enable heuristic support for
    /// // Unicode word boundaries.
    /// let dfa = dense::DFA::new(r"(?-u)\b[0-9]{3}\b")?;
    /// let haystack = "foo123bar".as_bytes();
    ///
    /// // Since we sub-slice the haystack, the search doesn't know about the
    /// // larger context and assumes that `123` is surrounded by word
    /// // boundaries. And of course, the match position is reported relative
    /// // to the sub-slice as well, which means we get `3` instead of `6`.
    /// let expected = Some(HalfMatch::must(0, 3));
    /// let got = dfa.find_earliest_fwd_at(
    ///     None,
    ///     None,
    ///     &haystack[3..6],
    ///     0,
    ///     haystack[3..6].len(),
    /// )?;
    /// assert_eq!(expected, got);
    ///
    /// // But if we provide the bounds of the search within the context of the
    /// // entire haystack, then the search can take the surrounding context
    /// // into account. (And if we did find a match, it would be reported
    /// // as a valid offset into `haystack` instead of its sub-slice.)
    /// let expected = None;
    /// let got = dfa.find_earliest_fwd_at(
    ///     None,
    ///     None,
    ///     haystack,
    ///     3,
    ///     6,
    /// )?;
    /// assert_eq!(expected, got);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    fn find_earliest_fwd_at(
        &self,
        pre: Option<&mut prefilter::Scanner>,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> Result<Option<HalfMatch>, MatchError> {
        search::find_earliest_fwd(pre, self, pattern_id, bytes, start, end)
    }

    /// Executes a reverse search and returns the start position of the first
    /// match that is found as early as possible. If no match exists, then
    /// `None` is returned.
    ///
    /// This routine stops scanning input as soon as the search observes a
    /// match state.
    ///
    /// This is like [`Automaton::find_earliest_rev`], except it provides some
    /// additional control over how the search is executed. See the
    /// documentation of [`Automaton::find_earliest_fwd_at`] for more details
    /// on the additional parameters along with examples of their usage.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Panics
    ///
    /// This routine must panic if a `pattern_id` is given and the underlying
    /// DFA does not support specific pattern searches.
    ///
    /// It must also panic if the given haystack range is not valid.
    #[inline]
    fn find_earliest_rev_at(
        &self,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> Result<Option<HalfMatch>, MatchError> {
        search::find_earliest_rev(self, pattern_id, bytes, start, end)
    }

    /// Executes a forward search and returns the end position of the leftmost
    /// match that is found. If no match exists, then `None` is returned.
    ///
    /// This is like [`Automaton::find_leftmost_fwd`], except it provides some
    /// additional control over how the search is executed. See the
    /// documentation of [`Automaton::find_earliest_fwd_at`] for more details
    /// on the additional parameters along with examples of their usage.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Panics
    ///
    /// This routine must panic if a `pattern_id` is given and the underlying
    /// DFA does not support specific pattern searches.
    ///
    /// It must also panic if the given haystack range is not valid.
    #[inline]
    fn find_leftmost_fwd_at(
        &self,
        pre: Option<&mut prefilter::Scanner>,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> Result<Option<HalfMatch>, MatchError> {
        search::find_leftmost_fwd(pre, self, pattern_id, bytes, start, end)
    }

    /// Executes a reverse search and returns the start of the position of the
    /// leftmost match that is found. If no match exists, then `None` is
    /// returned.
    ///
    /// This is like [`Automaton::find_leftmost_rev`], except it provides some
    /// additional control over how the search is executed. See the
    /// documentation of [`Automaton::find_earliest_fwd_at`] for more details
    /// on the additional parameters along with examples of their usage.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Panics
    ///
    /// This routine must panic if a `pattern_id` is given and the underlying
    /// DFA does not support specific pattern searches.
    ///
    /// It must also panic if the given haystack range is not valid.
    #[inline]
    fn find_leftmost_rev_at(
        &self,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> Result<Option<HalfMatch>, MatchError> {
        search::find_leftmost_rev(self, pattern_id, bytes, start, end)
    }

    /// Executes an overlapping forward search and returns the end position of
    /// matches as they are found. If no match exists, then `None` is returned.
    ///
    /// This routine is principally only useful when searching for multiple
    /// patterns on inputs where multiple patterns may match the same regions
    /// of text. In particular, callers must preserve the automaton's search
    /// state from prior calls so that the implementation knows where the last
    /// match occurred.
    ///
    /// This is like [`Automaton::find_overlapping_fwd`], except it provides
    /// some additional control over how the search is executed. See the
    /// documentation of [`Automaton::find_earliest_fwd_at`] for more details
    /// on the additional parameters along with examples of their usage.
    ///
    /// When using this routine to implement an iterator of overlapping
    /// matches, the `start` of the search should always be set to the end
    /// of the last match. If more patterns match at the previous location,
    /// then they will be immediately returned. (This is tracked by the given
    /// overlapping state.) Otherwise, the search continues at the starting
    /// position given.
    ///
    /// If for some reason you want the search to forget about its previous
    /// state and restart the search at a particular position, then setting the
    /// state to [`OverlappingState::start`] will accomplish that.
    ///
    /// # Errors
    ///
    /// This routine only errors if the search could not complete. For
    /// DFAs generated by this crate, this only occurs in a non-default
    /// configuration where quit bytes are used or Unicode word boundaries are
    /// heuristically enabled.
    ///
    /// When a search cannot complete, callers cannot know whether a match
    /// exists or not.
    ///
    /// # Panics
    ///
    /// This routine must panic if a `pattern_id` is given and the underlying
    /// DFA does not support specific pattern searches.
    ///
    /// It must also panic if the given haystack range is not valid.
    #[inline]
    fn find_overlapping_fwd_at(
        &self,
        pre: Option<&mut prefilter::Scanner>,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
        state: &mut OverlappingState,
    ) -> Result<Option<HalfMatch>, MatchError> {
        search::find_overlapping_fwd(
            pre, self, pattern_id, bytes, start, end, state,
        )
    }
}

unsafe impl<'a, T: Automaton> Automaton for &'a T {
    #[inline]
    fn next_state(&self, current: StateID, input: u8) -> StateID {
        (**self).next_state(current, input)
    }

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

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

    #[inline]
    fn start_state_forward(
        &self,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> StateID {
        (**self).start_state_forward(pattern_id, bytes, start, end)
    }

    #[inline]
    fn start_state_reverse(
        &self,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> StateID {
        (**self).start_state_reverse(pattern_id, bytes, start, end)
    }

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

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

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

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

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

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

    #[inline]
    fn pattern_count(&self) -> usize {
        (**self).pattern_count()
    }

    #[inline]
    fn match_count(&self, id: StateID) -> usize {
        (**self).match_count(id)
    }

    #[inline]
    fn match_pattern(&self, id: StateID, index: usize) -> PatternID {
        (**self).match_pattern(id, index)
    }

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

    #[inline]
    fn find_earliest_fwd(
        &self,
        bytes: &[u8],
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_earliest_fwd(bytes)
    }

    #[inline]
    fn find_earliest_rev(
        &self,
        bytes: &[u8],
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_earliest_rev(bytes)
    }

    #[inline]
    fn find_leftmost_fwd(
        &self,
        bytes: &[u8],
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_leftmost_fwd(bytes)
    }

    #[inline]
    fn find_leftmost_rev(
        &self,
        bytes: &[u8],
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_leftmost_rev(bytes)
    }

    #[inline]
    fn find_overlapping_fwd(
        &self,
        bytes: &[u8],
        state: &mut OverlappingState,
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_overlapping_fwd(bytes, state)
    }

    #[inline]
    fn find_earliest_fwd_at(
        &self,
        pre: Option<&mut prefilter::Scanner>,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_earliest_fwd_at(pre, pattern_id, bytes, start, end)
    }

    #[inline]
    fn find_earliest_rev_at(
        &self,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_earliest_rev_at(pattern_id, bytes, start, end)
    }

    #[inline]
    fn find_leftmost_fwd_at(
        &self,
        pre: Option<&mut prefilter::Scanner>,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_leftmost_fwd_at(pre, pattern_id, bytes, start, end)
    }

    #[inline]
    fn find_leftmost_rev_at(
        &self,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self).find_leftmost_rev_at(pattern_id, bytes, start, end)
    }

    #[inline]
    fn find_overlapping_fwd_at(
        &self,
        pre: Option<&mut prefilter::Scanner>,
        pattern_id: Option<PatternID>,
        bytes: &[u8],
        start: usize,
        end: usize,
        state: &mut OverlappingState,
    ) -> Result<Option<HalfMatch>, MatchError> {
        (**self)
            .find_overlapping_fwd_at(pre, pattern_id, bytes, start, end, state)
    }
}

/// Represents the current state of an overlapping search.
///
/// This is used for overlapping searches since they need to know something
/// about the previous search. For example, when multiple patterns match at the
/// same position, this state tracks the last reported pattern so that the next
/// search knows whether to report another matching pattern or continue with
/// the search at the next position. Additionally, it also tracks which state
/// the last search call terminated in.
///
/// This type provides no introspection capabilities. The only thing a caller
/// can do is construct it and pass it around to permit search routines to use
/// it to track state.
///
/// Callers should always provide a fresh state constructed via
/// [`OverlappingState::start`] when starting a new search. Reusing state from
/// a previous search may result in incorrect results.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct OverlappingState {
    /// The state ID of the state at which the search was in when the call
    /// terminated. When this is a match state, `last_match` must be set to a
    /// non-None value.
    ///
    /// A `None` value indicates the start state of the corresponding
    /// automaton. We cannot use the actual ID, since any one automaton may
    /// have many start states, and which one is in use depends on several
    /// search-time factors.
    id: Option<StateID>,
    /// Information associated with a match when `id` corresponds to a match
    /// state.
    last_match: Option<StateMatch>,
}

/// Internal state about the last match that occurred. This records both the
/// offset of the match and the match index.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct StateMatch {
    /// The index into the matching patterns for the current match state.
    pub(crate) match_index: usize,
    /// The offset in the haystack at which the match occurred. This is used
    /// when reporting multiple matches at the same offset. That is, when
    /// an overlapping search runs, the first thing it checks is whether it's
    /// already in a match state, and if so, whether there are more patterns
    /// to report as matches in that state. If so, it increments `match_index`
    /// and returns the pattern and this offset. Once `match_index` exceeds the
    /// number of matching patterns in the current state, the search continues.
    pub(crate) offset: usize,
}

impl OverlappingState {
    /// Create a new overlapping state that begins at the start state of any
    /// automaton.
    pub fn start() -> OverlappingState {
        OverlappingState { id: None, last_match: None }
    }

    pub(crate) fn id(&self) -> Option<StateID> {
        self.id
    }

    pub(crate) fn set_id(&mut self, id: StateID) {
        self.id = Some(id);
    }

    pub(crate) fn last_match(&mut self) -> Option<&mut StateMatch> {
        self.last_match.as_mut()
    }

    pub(crate) fn set_last_match(&mut self, last_match: StateMatch) {
        self.last_match = Some(last_match);
    }
}

/// Write a prefix "state" indicator for fmt::Debug impls.
///
/// Specifically, this tries to succinctly distinguish the different types of
/// states: dead states, quit states, accelerated states, start states and
/// match states. It even accounts for the possible overlappings of different
/// state types.
pub(crate) fn fmt_state_indicator<A: Automaton>(
    f: &mut core::fmt::Formatter<'_>,
    dfa: A,
    id: StateID,
) -> core::fmt::Result {
    if dfa.is_dead_state(id) {
        write!(f, "D")?;
        if dfa.is_start_state(id) {
            write!(f, ">")?;
        } else {
            write!(f, " ")?;
        }
    } else if dfa.is_quit_state(id) {
        write!(f, "Q ")?;
    } else if dfa.is_start_state(id) {
        if dfa.is_accel_state(id) {
            write!(f, "A>")?;
        } else {
            write!(f, " >")?;
        }
    } else if dfa.is_match_state(id) {
        if dfa.is_accel_state(id) {
            write!(f, "A*")?;
        } else {
            write!(f, " *")?;
        }
    } else if dfa.is_accel_state(id) {
        write!(f, "A ")?;
    } else {
        write!(f, "  ")?;
    }
    Ok(())
}