Adding upstream version 0.70.1+ds1.upstream/0.70.1+ds1upstream

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

6 files changed, 6855 insertions, 0 deletions

diff --git a/vendor/regex-automata/src/hybrid/dfa.rs b/vendor/regex-automata/src/hybrid/dfa.rs
new file mode 100644
index 0000000..bd9179b
--- /dev/null
+++ b/vendor/regex-automata/src/hybrid/dfa.rs
@@ -0,0 +1,4418 @@
+/*!
+Types and routines specific to lazy DFAs.
+
+This module is the home of [`hybrid::dfa::DFA`](DFA).
+
+This module also contains a [`hybrid::dfa::Builder`](Builder) and a
+[`hybrid::dfa::Config`](Config) for configuring and building a lazy DFA.
+*/
+
+use core::{iter, mem::size_of};
+
+use alloc::vec::Vec;
+
+use crate::{
+    hybrid::{
+        error::{BuildError, CacheError, StartError},
+        id::{LazyStateID, LazyStateIDError},
+        search,
+    },
+    nfa::thompson,
+    util::{
+        alphabet::{self, ByteClasses, ByteSet},
+        determinize::{self, State, StateBuilderEmpty, StateBuilderNFA},
+        empty,
+        prefilter::Prefilter,
+        primitives::{PatternID, StateID as NFAStateID},
+        search::{
+            Anchored, HalfMatch, Input, MatchError, MatchKind, PatternSet,
+        },
+        sparse_set::SparseSets,
+        start::{self, Start, StartByteMap},
+    },
+};
+
+/// The minimum number of states that a lazy DFA's cache size must support.
+///
+/// This is checked at time of construction to ensure that at least some small
+/// number of states can fit in the given capacity allotment. If we can't fit
+/// at least this number of states, then the thinking is that it's pretty
+/// senseless to use the lazy DFA. More to the point, parts of the code do
+/// assume that the cache can fit at least some small number of states.
+const MIN_STATES: usize = SENTINEL_STATES + 2;
+
+/// The number of "sentinel" states that get added to every lazy DFA.
+///
+/// These are special states indicating status conditions of a search: unknown,
+/// dead and quit. These states in particular also use zero NFA states, so
+/// their memory usage is quite small. This is relevant for computing the
+/// minimum memory needed for a lazy DFA cache.
+const SENTINEL_STATES: usize = 3;
+
+/// A hybrid NFA/DFA (also called a "lazy DFA") for regex searching.
+///
+/// A lazy DFA is a DFA that builds itself at search time. It otherwise has
+/// very similar characteristics as a [`dense::DFA`](crate::dfa::dense::DFA).
+/// Indeed, both support precisely the same regex features with precisely the
+/// same semantics.
+///
+/// Where as a `dense::DFA` must be completely built to handle any input before
+/// it may be used for search, a lazy DFA starts off effectively empty. During
+/// a search, a lazy DFA will build itself depending on whether it has already
+/// computed the next transition or not. If it has, then it looks a lot like
+/// a `dense::DFA` internally: it does a very fast table based access to find
+/// the next transition. Otherwise, if the state hasn't been computed, then it
+/// does determinization _for that specific transition_ to compute the next DFA
+/// state.
+///
+/// The main selling point of a lazy DFA is that, in practice, it has
+/// the performance profile of a `dense::DFA` without the weakness of it
+/// taking worst case exponential time to build. Indeed, for each byte of
+/// input, the lazy DFA will construct as most one new DFA state. Thus, a
+/// lazy DFA achieves worst case `O(mn)` time for regex search (where `m ~
+/// pattern.len()` and `n ~ haystack.len()`).
+///
+/// The main downsides of a lazy DFA are:
+///
+/// 1. It requires mutable "cache" space during search. This is where the
+/// transition table, among other things, is stored.
+/// 2. In pathological cases (e.g., if the cache is too small), it will run
+/// out of room and either require a bigger cache capacity or will repeatedly
+/// clear the cache and thus repeatedly regenerate DFA states. Overall, this
+/// will tend to be slower than a typical NFA simulation.
+///
+/// # Capabilities
+///
+/// Like a `dense::DFA`, a single lazy DFA fundamentally supports the following
+/// operations:
+///
+/// 1. Detection of a match.
+/// 2. Location of the end of a match.
+/// 3. In the case of a lazy DFA with multiple patterns, which pattern matched
+/// is reported as well.
+///
+/// A notable absence from the above list of capabilities is the location of
+/// the *start* of a match. In order to provide both the start and end of
+/// a match, *two* lazy DFAs are required. This functionality is provided by a
+/// [`Regex`](crate::hybrid::regex::Regex).
+///
+/// # Example
+///
+/// This shows how to build a lazy DFA with the default configuration and
+/// execute a search. Notice how, in contrast to a `dense::DFA`, we must create
+/// a cache and pass it to our search routine.
+///
+/// ```
+/// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+///
+/// let dfa = DFA::new("foo[0-9]+")?;
+/// let mut cache = dfa.create_cache();
+///
+/// let expected = Some(HalfMatch::must(0, 8));
+/// assert_eq!(expected, dfa.try_search_fwd(
+///     &mut cache, &Input::new("foo12345"))?,
+/// );
+/// # Ok::<(), Box<dyn std::error::Error>>(())
+/// ```
+#[derive(Clone, Debug)]
+pub struct DFA {
+    config: Config,
+    nfa: thompson::NFA,
+    stride2: usize,
+    start_map: StartByteMap,
+    classes: ByteClasses,
+    quitset: ByteSet,
+    cache_capacity: usize,
+}
+
+impl DFA {
+    /// Parse the given regular expression using a default configuration and
+    /// return the corresponding lazy DFA.
+    ///
+    /// If you want a non-default configuration, then use the [`Builder`] to
+    /// set your own configuration.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// let dfa = DFA::new("foo[0-9]+bar")?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let expected = HalfMatch::must(0, 11);
+    /// assert_eq!(
+    ///     Some(expected),
+    ///     dfa.try_search_fwd(&mut cache, &Input::new("foo12345bar"))?,
+    /// );
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[cfg(feature = "syntax")]
+    pub fn new(pattern: &str) -> Result<DFA, BuildError> {
+        DFA::builder().build(pattern)
+    }
+
+    /// Parse the given regular expressions using a default configuration and
+    /// return the corresponding lazy multi-DFA.
+    ///
+    /// If you want a non-default configuration, then use the [`Builder`] to
+    /// set your own configuration.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// let dfa = DFA::new_many(&["[0-9]+", "[a-z]+"])?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let expected = HalfMatch::must(1, 3);
+    /// assert_eq!(
+    ///     Some(expected),
+    ///     dfa.try_search_fwd(&mut cache, &Input::new("foo12345bar"))?,
+    /// );
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[cfg(feature = "syntax")]
+    pub fn new_many<P: AsRef<str>>(patterns: &[P]) -> Result<DFA, BuildError> {
+        DFA::builder().build_many(patterns)
+    }
+
+    /// Create a new lazy DFA that matches every input.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// let dfa = DFA::always_match()?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let expected = HalfMatch::must(0, 0);
+    /// assert_eq!(Some(expected), dfa.try_search_fwd(
+    ///     &mut cache, &Input::new(""))?,
+    /// );
+    /// assert_eq!(Some(expected), dfa.try_search_fwd(
+    ///     &mut cache, &Input::new("foo"))?,
+    /// );
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn always_match() -> Result<DFA, BuildError> {
+        let nfa = thompson::NFA::always_match();
+        Builder::new().build_from_nfa(nfa)
+    }
+
+    /// Create a new lazy DFA that never matches any input.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, Input};
+    ///
+    /// let dfa = DFA::never_match()?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// assert_eq!(None, dfa.try_search_fwd(&mut cache, &Input::new(""))?);
+    /// assert_eq!(None, dfa.try_search_fwd(&mut cache, &Input::new("foo"))?);
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn never_match() -> Result<DFA, BuildError> {
+        let nfa = thompson::NFA::never_match();
+        Builder::new().build_from_nfa(nfa)
+    }
+
+    /// Return a default configuration for a `DFA`.
+    ///
+    /// This is a convenience routine to avoid needing to import the [`Config`]
+    /// type when customizing the construction of a lazy DFA.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to build a lazy DFA that heuristically supports
+    /// Unicode word boundaries.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, MatchError, Input};
+    ///
+    /// let re = DFA::builder()
+    ///     .configure(DFA::config().unicode_word_boundary(true))
+    ///     .build(r"\b\w+\b")?;
+    /// let mut cache = re.create_cache();
+    ///
+    /// // Since our haystack is all ASCII, the DFA search sees then and knows
+    /// // it is legal to interpret Unicode word boundaries as ASCII word
+    /// // boundaries.
+    /// let input = Input::new("!!foo!!");
+    /// let expected = HalfMatch::must(0, 5);
+    /// assert_eq!(Some(expected), re.try_search_fwd(&mut cache, &input)?);
+    ///
+    /// // But if our haystack contains non-ASCII, then the search will fail
+    /// // with an error.
+    /// let input = Input::new("!!βββ!!");
+    /// let expected = MatchError::quit(b'\xCE', 2);
+    /// assert_eq!(Err(expected), re.try_search_fwd(&mut cache, &input));
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn config() -> Config {
+        Config::new()
+    }
+
+    /// Return a builder for configuring the construction of a `Regex`.
+    ///
+    /// This is a convenience routine to avoid needing to import the
+    /// [`Builder`] type in common cases.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to use the builder to disable UTF-8 mode
+    /// everywhere for lazy DFAs.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, util::syntax, HalfMatch, Input};
+    ///
+    /// let re = DFA::builder()
+    ///     .syntax(syntax::Config::new().utf8(false))
+    ///     .build(r"foo(?-u:[^b])ar.*")?;
+    /// let mut cache = re.create_cache();
+    ///
+    /// let input = Input::new(b"\xFEfoo\xFFarzz\xE2\x98\xFF\n");
+    /// let expected = Some(HalfMatch::must(0, 9));
+    /// let got = re.try_search_fwd(&mut cache, &input)?;
+    /// assert_eq!(expected, got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn builder() -> Builder {
+        Builder::new()
+    }
+
+    /// Create a new cache for this lazy DFA.
+    ///
+    /// The cache returned should only be used for searches for this
+    /// lazy DFA. If you want to reuse the cache for another DFA, then
+    /// you must call [`Cache::reset`] with that DFA (or, equivalently,
+    /// [`DFA::reset_cache`]).
+    pub fn create_cache(&self) -> Cache {
+        Cache::new(self)
+    }
+
+    /// Reset the given cache such that it can be used for searching with the
+    /// this lazy DFA (and only this DFA).
+    ///
+    /// A cache reset permits reusing memory already allocated in this cache
+    /// with a different lazy DFA.
+    ///
+    /// Resetting a cache sets its "clear count" to 0. This is relevant if the
+    /// lazy DFA has been configured to "give up" after it has cleared the
+    /// cache a certain number of times.
+    ///
+    /// Any lazy state ID generated by the cache prior to resetting it is
+    /// invalid after the reset.
+    ///
+    /// # Example
+    ///
+    /// This shows how to re-purpose a cache for use with a different DFA.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// let dfa1 = DFA::new(r"\w")?;
+    /// let dfa2 = DFA::new(r"\W")?;
+    ///
+    /// let mut cache = dfa1.create_cache();
+    /// assert_eq!(
+    ///     Some(HalfMatch::must(0, 2)),
+    ///     dfa1.try_search_fwd(&mut cache, &Input::new("Δ"))?,
+    /// );
+    ///
+    /// // Using 'cache' with dfa2 is not allowed. It may result in panics or
+    /// // incorrect results. In order to re-purpose the cache, we must reset
+    /// // it with the DFA we'd like to use it with.
+    /// //
+    /// // Similarly, after this reset, using the cache with 'dfa1' is also not
+    /// // allowed.
+    /// dfa2.reset_cache(&mut cache);
+    /// assert_eq!(
+    ///     Some(HalfMatch::must(0, 3)),
+    ///     dfa2.try_search_fwd(&mut cache, &Input::new("☃"))?,
+    /// );
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn reset_cache(&self, cache: &mut Cache) {
+        Lazy::new(self, cache).reset_cache()
+    }
+
+    /// Returns the total number of patterns compiled into this lazy DFA.
+    ///
+    /// In the case of a DFA that contains no patterns, this returns `0`.
+    ///
+    /// # Example
+    ///
+    /// This example shows the pattern length for a DFA that never matches:
+    ///
+    /// ```
+    /// use regex_automata::hybrid::dfa::DFA;
+    ///
+    /// let dfa = DFA::never_match()?;
+    /// assert_eq!(dfa.pattern_len(), 0);
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// And another example for a DFA that matches at every position:
+    ///
+    /// ```
+    /// use regex_automata::hybrid::dfa::DFA;
+    ///
+    /// let dfa = DFA::always_match()?;
+    /// assert_eq!(dfa.pattern_len(), 1);
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// And finally, a DFA that was constructed from multiple patterns:
+    ///
+    /// ```
+    /// use regex_automata::hybrid::dfa::DFA;
+    ///
+    /// let dfa = DFA::new_many(&["[0-9]+", "[a-z]+", "[A-Z]+"])?;
+    /// assert_eq!(dfa.pattern_len(), 3);
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn pattern_len(&self) -> usize {
+        self.nfa.pattern_len()
+    }
+
+    /// Returns the equivalence classes that make up the alphabet for this DFA.
+    ///
+    /// Unless [`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.classes
+    }
+
+    /// Returns this lazy DFA's configuration.
+    pub fn get_config(&self) -> &Config {
+        &self.config
+    }
+
+    /// Returns a reference to the underlying NFA.
+    pub fn get_nfa(&self) -> &thompson::NFA {
+        &self.nfa
+    }
+
+    /// Returns the stride, as a base-2 exponent, required for these
+    /// equivalence classes.
+    ///
+    /// The stride is always the smallest power of 2 that is greater than or
+    /// equal to the alphabet length. This is done so that converting between
+    /// state IDs and indices can be done with shifts alone, which is much
+    /// faster than integer division.
+    fn stride2(&self) -> usize {
+        self.stride2
+    }
+
+    /// Returns the total stride for every state in this lazy DFA. This
+    /// corresponds to the total number of transitions used by each state in
+    /// this DFA's transition table.
+    fn stride(&self) -> usize {
+        1 << self.stride2()
+    }
+
+    /// Returns the memory usage, in bytes, of this lazy DFA.
+    ///
+    /// This does **not** include the stack size used up by this lazy DFA. To
+    /// compute that, use `std::mem::size_of::<DFA>()`. This also does not
+    /// include the size of the `Cache` used.
+    ///
+    /// This also does not include any heap memory used by the NFA inside of
+    /// this hybrid NFA/DFA. This is because the NFA's ownership is shared, and
+    /// thus not owned by this hybrid NFA/DFA. More practically, several regex
+    /// engines in this crate embed an NFA, and reporting the NFA's memory
+    /// usage in all of them would likely result in reporting higher heap
+    /// memory than is actually used.
+    pub fn memory_usage(&self) -> usize {
+        // The only thing that uses heap memory in a DFA is the NFA. But the
+        // NFA has shared ownership, so reporting its memory as part of the
+        // hybrid DFA is likely to lead to double-counting the NFA memory
+        // somehow. In particular, this DFA does not really own an NFA, so
+        // including it in the DFA's memory usage doesn't seem semantically
+        // correct.
+        0
+    }
+}
+
+impl DFA {
+    /// Executes a forward search and returns the end position of the leftmost
+    /// match that is found. If no match exists, then `None` is returned.
+    ///
+    /// In particular, this method continues searching even after it enters
+    /// a match state. The search only terminates 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.
+    ///
+    /// # Errors
+    ///
+    /// This routine errors if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search returns an error, callers cannot know whether a match
+    /// exists or not.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to run a basic search.
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// let dfa = DFA::new("foo[0-9]+")?;
+    /// let mut cache = dfa.create_cache();
+    /// let expected = HalfMatch::must(0, 8);
+    /// assert_eq!(Some(expected), dfa.try_search_fwd(
+    ///     &mut cache, &Input::new("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 later parts.
+    /// let dfa = DFA::new("abc|a")?;
+    /// let mut cache = dfa.create_cache();
+    /// let expected = HalfMatch::must(0, 3);
+    /// assert_eq!(Some(expected), dfa.try_search_fwd(
+    ///     &mut cache, &Input::new("abc"))?,
+    /// );
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// # Example: specific pattern search
+    ///
+    /// This example shows how to build a lazy multi-DFA that permits searching
+    /// for specific patterns.
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     Anchored, HalfMatch, PatternID, Input,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().starts_for_each_pattern(true))
+    ///     .build_many(&["[a-z0-9]{6}", "[a-z][a-z0-9]{5}"])?;
+    /// let mut cache = dfa.create_cache();
+    /// let haystack = "foo123";
+    ///
+    /// // 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.try_search_fwd(&mut cache, &Input::new(haystack))?;
+    /// 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 input = Input::new(haystack)
+    ///     .anchored(Anchored::Pattern(PatternID::must(1)));
+    /// let got = dfa.try_search_fwd(&mut cache, &input)?;
+    /// 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::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// // 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 since our haystack is pure ASCII.
+    /// let dfa = DFA::new(r"(?-u)\b[0-9]{3}\b")?;
+    /// let mut cache = dfa.create_cache();
+    /// let haystack = "foo123bar";
+    ///
+    /// // 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.try_search_fwd(
+    ///     &mut cache,
+    ///     &Input::new(&haystack[3..6]),
+    /// )?;
+    /// 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.try_search_fwd(
+    ///     &mut cache,
+    ///     &Input::new(haystack).range(3..6),
+    /// )?;
+    /// assert_eq!(expected, got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn try_search_fwd(
+        &self,
+        cache: &mut Cache,
+        input: &Input<'_>,
+    ) -> Result<Option<HalfMatch>, MatchError> {
+        let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
+        let hm = match search::find_fwd(self, cache, input)? {
+            None => return Ok(None),
+            Some(hm) if !utf8empty => return Ok(Some(hm)),
+            Some(hm) => hm,
+        };
+        // We get to this point when we know our DFA can match the empty string
+        // AND when UTF-8 mode is enabled. In this case, we skip any matches
+        // whose offset splits a codepoint. Such a match is necessarily a
+        // zero-width match, because UTF-8 mode requires the underlying NFA
+        // to be built such that all non-empty matches span valid UTF-8.
+        // Therefore, any match that ends in the middle of a codepoint cannot
+        // be part of a span of valid UTF-8 and thus must be an empty match.
+        // In such cases, we skip it, so as not to report matches that split a
+        // codepoint.
+        //
+        // Note that this is not a checked assumption. Callers *can* provide an
+        // NFA with UTF-8 mode enabled but produces non-empty matches that span
+        // invalid UTF-8. But doing so is documented to result in unspecified
+        // behavior.
+        empty::skip_splits_fwd(input, hm, hm.offset(), |input| {
+            let got = search::find_fwd(self, cache, input)?;
+            Ok(got.map(|hm| (hm, hm.offset())))
+        })
+    }
+
+    /// 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 errors if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search returns an error, callers cannot know whether a match
+    /// exists or not.
+    ///
+    /// # Example
+    ///
+    /// 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
+    /// `try_search_fwd` and `try_search_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,
+    ///     hybrid::dfa::DFA,
+    ///     HalfMatch, Input,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .thompson(thompson::Config::new().reverse(true))
+    ///     .build("foo[0-9]+")?;
+    /// let mut cache = dfa.create_cache();
+    /// let expected = HalfMatch::must(0, 0);
+    /// assert_eq!(
+    ///     Some(expected),
+    ///     dfa.try_search_rev(&mut cache, &Input::new("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 = DFA::builder()
+    ///     .thompson(thompson::Config::new().reverse(true))
+    ///     .build("abc|c")?;
+    /// let mut cache = dfa.create_cache();
+    /// let expected = HalfMatch::must(0, 0);
+    /// assert_eq!(Some(expected), dfa.try_search_rev(
+    ///     &mut cache, &Input::new("abc"))?,
+    /// );
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// # Example: UTF-8 mode
+    ///
+    /// This examples demonstrates that UTF-8 mode applies to reverse
+    /// DFAs. When UTF-8 mode is enabled in the underlying NFA, then all
+    /// matches reported must correspond to valid UTF-8 spans. This includes
+    /// prohibiting zero-width matches that split a codepoint.
+    ///
+    /// UTF-8 mode is enabled by default. Notice below how the only zero-width
+    /// matches reported are those at UTF-8 boundaries:
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     nfa::thompson,
+    ///     HalfMatch, Input, MatchKind,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .thompson(thompson::Config::new().reverse(true))
+    ///     .build(r"")?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// // Run the reverse DFA to collect all matches.
+    /// let mut input = Input::new("☃");
+    /// let mut matches = vec![];
+    /// loop {
+    ///     match dfa.try_search_rev(&mut cache, &input)? {
+    ///         None => break,
+    ///         Some(hm) => {
+    ///             matches.push(hm);
+    ///             if hm.offset() == 0 || input.end() == 0 {
+    ///                 break;
+    ///             } else if hm.offset() < input.end() {
+    ///                 input.set_end(hm.offset());
+    ///             } else {
+    ///                 // This is only necessary to handle zero-width
+    ///                 // matches, which of course occur in this example.
+    ///                 // Without this, the search would never advance
+    ///                 // backwards beyond the initial match.
+    ///                 input.set_end(input.end() - 1);
+    ///             }
+    ///         }
+    ///     }
+    /// }
+    ///
+    /// // No matches split a codepoint.
+    /// let expected = vec![
+    ///     HalfMatch::must(0, 3),
+    ///     HalfMatch::must(0, 0),
+    /// ];
+    /// assert_eq!(expected, matches);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// Now let's look at the same example, but with UTF-8 mode on the
+    /// underlying NFA disabled:
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     nfa::thompson,
+    ///     HalfMatch, Input, MatchKind,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .thompson(thompson::Config::new().reverse(true).utf8(false))
+    ///     .build(r"")?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// // Run the reverse DFA to collect all matches.
+    /// let mut input = Input::new("☃");
+    /// let mut matches = vec![];
+    /// loop {
+    ///     match dfa.try_search_rev(&mut cache, &input)? {
+    ///         None => break,
+    ///         Some(hm) => {
+    ///             matches.push(hm);
+    ///             if hm.offset() == 0 || input.end() == 0 {
+    ///                 break;
+    ///             } else if hm.offset() < input.end() {
+    ///                 input.set_end(hm.offset());
+    ///             } else {
+    ///                 // This is only necessary to handle zero-width
+    ///                 // matches, which of course occur in this example.
+    ///                 // Without this, the search would never advance
+    ///                 // backwards beyond the initial match.
+    ///                 input.set_end(input.end() - 1);
+    ///             }
+    ///         }
+    ///     }
+    /// }
+    ///
+    /// // No matches split a codepoint.
+    /// let expected = vec![
+    ///     HalfMatch::must(0, 3),
+    ///     HalfMatch::must(0, 2),
+    ///     HalfMatch::must(0, 1),
+    ///     HalfMatch::must(0, 0),
+    /// ];
+    /// assert_eq!(expected, matches);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn try_search_rev(
+        &self,
+        cache: &mut Cache,
+        input: &Input<'_>,
+    ) -> Result<Option<HalfMatch>, MatchError> {
+        let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
+        let hm = match search::find_rev(self, cache, input)? {
+            None => return Ok(None),
+            Some(hm) if !utf8empty => return Ok(Some(hm)),
+            Some(hm) => hm,
+        };
+        empty::skip_splits_rev(input, hm, hm.offset(), |input| {
+            let got = search::find_rev(self, cache, input)?;
+            Ok(got.map(|hm| (hm, hm.offset())))
+        })
+    }
+
+    /// 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.
+    ///
+    /// When using this routine to implement an iterator of overlapping
+    /// matches, the `start` of the search should remain invariant throughout
+    /// iteration. The `OverlappingState` given to the search will keep track
+    /// of the current position of the search. (This is because multiple
+    /// matches may be reported at the same position, so only the search
+    /// implementation itself knows when to advance the position.)
+    ///
+    /// 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 errors if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search returns an error, callers cannot know whether a match
+    /// exists or not.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to run a basic overlapping search. 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).
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{
+    ///     hybrid::dfa::{DFA, OverlappingState},
+    ///     HalfMatch, Input, MatchKind,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().match_kind(MatchKind::All))
+    ///     .build_many(&[r"\w+$", r"\S+$"])?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let haystack = "@foo";
+    /// let mut state = OverlappingState::start();
+    ///
+    /// let expected = Some(HalfMatch::must(1, 4));
+    /// dfa.try_search_overlapping_fwd(
+    ///     &mut cache, &Input::new(haystack), &mut state,
+    /// )?;
+    /// assert_eq!(expected, state.get_match());
+    ///
+    /// // 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));
+    /// dfa.try_search_overlapping_fwd(
+    ///     &mut cache, &Input::new(haystack), &mut state,
+    /// )?;
+    /// assert_eq!(expected, state.get_match());
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn try_search_overlapping_fwd(
+        &self,
+        cache: &mut Cache,
+        input: &Input<'_>,
+        state: &mut OverlappingState,
+    ) -> Result<(), MatchError> {
+        let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
+        search::find_overlapping_fwd(self, cache, input, state)?;
+        match state.get_match() {
+            None => Ok(()),
+            Some(_) if !utf8empty => Ok(()),
+            Some(_) => skip_empty_utf8_splits_overlapping(
+                input,
+                state,
+                |input, state| {
+                    search::find_overlapping_fwd(self, cache, input, state)
+                },
+            ),
+        }
+    }
+
+    /// Executes a reverse overlapping search and returns the start of the
+    /// position of the leftmost match that is found. If no match exists, then
+    /// `None` is returned.
+    ///
+    /// When using this routine to implement an iterator of overlapping
+    /// matches, the `start` of the search should remain invariant throughout
+    /// iteration. The `OverlappingState` given to the search will keep track
+    /// of the current position of the search. (This is because multiple
+    /// matches may be reported at the same position, so only the search
+    /// implementation itself knows when to advance the position.)
+    ///
+    /// 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 errors if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search returns an error, callers cannot know whether a match
+    /// exists or not.
+    ///
+    /// # Example: UTF-8 mode
+    ///
+    /// This examples demonstrates that UTF-8 mode applies to reverse
+    /// DFAs. When UTF-8 mode is enabled in the underlying NFA, then all
+    /// matches reported must correspond to valid UTF-8 spans. This includes
+    /// prohibiting zero-width matches that split a codepoint.
+    ///
+    /// UTF-8 mode is enabled by default. Notice below how the only zero-width
+    /// matches reported are those at UTF-8 boundaries:
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::{DFA, OverlappingState},
+    ///     nfa::thompson,
+    ///     HalfMatch, Input, MatchKind,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().match_kind(MatchKind::All))
+    ///     .thompson(thompson::Config::new().reverse(true))
+    ///     .build_many(&[r"", r"☃"])?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// // Run the reverse DFA to collect all matches.
+    /// let input = Input::new("☃");
+    /// let mut state = OverlappingState::start();
+    /// let mut matches = vec![];
+    /// loop {
+    ///     dfa.try_search_overlapping_rev(&mut cache, &input, &mut state)?;
+    ///     match state.get_match() {
+    ///         None => break,
+    ///         Some(hm) => matches.push(hm),
+    ///     }
+    /// }
+    ///
+    /// // No matches split a codepoint.
+    /// let expected = vec![
+    ///     HalfMatch::must(0, 3),
+    ///     HalfMatch::must(1, 0),
+    ///     HalfMatch::must(0, 0),
+    /// ];
+    /// assert_eq!(expected, matches);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// Now let's look at the same example, but with UTF-8 mode on the
+    /// underlying NFA disabled:
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::{DFA, OverlappingState},
+    ///     nfa::thompson,
+    ///     HalfMatch, Input, MatchKind,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().match_kind(MatchKind::All))
+    ///     .thompson(thompson::Config::new().reverse(true).utf8(false))
+    ///     .build_many(&[r"", r"☃"])?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// // Run the reverse DFA to collect all matches.
+    /// let input = Input::new("☃");
+    /// let mut state = OverlappingState::start();
+    /// let mut matches = vec![];
+    /// loop {
+    ///     dfa.try_search_overlapping_rev(&mut cache, &input, &mut state)?;
+    ///     match state.get_match() {
+    ///         None => break,
+    ///         Some(hm) => matches.push(hm),
+    ///     }
+    /// }
+    ///
+    /// // Now *all* positions match, even within a codepoint,
+    /// // because we lifted the requirement that matches
+    /// // correspond to valid UTF-8 spans.
+    /// let expected = vec![
+    ///     HalfMatch::must(0, 3),
+    ///     HalfMatch::must(0, 2),
+    ///     HalfMatch::must(0, 1),
+    ///     HalfMatch::must(1, 0),
+    ///     HalfMatch::must(0, 0),
+    /// ];
+    /// assert_eq!(expected, matches);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn try_search_overlapping_rev(
+        &self,
+        cache: &mut Cache,
+        input: &Input<'_>,
+        state: &mut OverlappingState,
+    ) -> Result<(), MatchError> {
+        let utf8empty = self.get_nfa().has_empty() && self.get_nfa().is_utf8();
+        search::find_overlapping_rev(self, cache, input, state)?;
+        match state.get_match() {
+            None => Ok(()),
+            Some(_) if !utf8empty => Ok(()),
+            Some(_) => skip_empty_utf8_splits_overlapping(
+                input,
+                state,
+                |input, state| {
+                    search::find_overlapping_rev(self, cache, input, state)
+                },
+            ),
+        }
+    }
+
+    /// Writes the set of patterns that match anywhere in the given search
+    /// configuration to `patset`. If multiple patterns match at the same
+    /// position and the underlying DFA supports overlapping matches, then all
+    /// matching patterns are written to the given set.
+    ///
+    /// Unless all of the patterns in this DFA are anchored, then generally
+    /// speaking, this will visit every byte in the haystack.
+    ///
+    /// This search routine *does not* clear the pattern set. This gives some
+    /// flexibility to the caller (e.g., running multiple searches with the
+    /// same pattern set), but does make the API bug-prone if you're reusing
+    /// the same pattern set for multiple searches but intended them to be
+    /// independent.
+    ///
+    /// If a pattern ID matched but the given `PatternSet` does not have
+    /// sufficient capacity to store it, then it is not inserted and silently
+    /// dropped.
+    ///
+    /// # Errors
+    ///
+    /// This routine errors if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search returns an error, callers cannot know whether a match
+    /// exists or not.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to find all matching patterns in a haystack,
+    /// even when some patterns match at the same position as other patterns.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     Input, MatchKind, PatternSet,
+    /// };
+    ///
+    /// let patterns = &[
+    ///     r"\w+", r"\d+", r"\pL+", r"foo", r"bar", r"barfoo", r"foobar",
+    /// ];
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().match_kind(MatchKind::All))
+    ///     .build_many(patterns)?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let input = Input::new("foobar");
+    /// let mut patset = PatternSet::new(dfa.pattern_len());
+    /// dfa.try_which_overlapping_matches(&mut cache, &input, &mut patset)?;
+    /// let expected = vec![0, 2, 3, 4, 6];
+    /// let got: Vec<usize> = patset.iter().map(|p| p.as_usize()).collect();
+    /// assert_eq!(expected, got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn try_which_overlapping_matches(
+        &self,
+        cache: &mut Cache,
+        input: &Input<'_>,
+        patset: &mut PatternSet,
+    ) -> Result<(), MatchError> {
+        let mut state = OverlappingState::start();
+        while let Some(m) = {
+            self.try_search_overlapping_fwd(cache, input, &mut state)?;
+            state.get_match()
+        } {
+            let _ = patset.try_insert(m.pattern());
+            // There's nothing left to find, so we can stop. Or the caller
+            // asked us to.
+            if patset.is_full() || input.get_earliest() {
+                break;
+            }
+        }
+        Ok(())
+    }
+}
+
+impl DFA {
+    /// Transitions from the current state to the next state, given the next
+    /// byte of input.
+    ///
+    /// The given cache is used to either reuse pre-computed state
+    /// transitions, or to store this newly computed transition for future
+    /// reuse. Thus, this routine guarantees that it will never return a state
+    /// ID that has an "unknown" tag.
+    ///
+    /// # State identifier validity
+    ///
+    /// The only valid value for `current` is the lazy state ID returned
+    /// by the most recent call to `next_state`, `next_state_untagged`,
+    /// `next_state_untagged_unchecked`, `start_state_forward` or
+    /// `state_state_reverse` for the given `cache`. Any state ID returned from
+    /// prior calls to these routines (with the same `cache`) is considered
+    /// invalid (even if it gives an appearance of working). State IDs returned
+    /// from _any_ prior call for different `cache` values are also always
+    /// invalid.
+    ///
+    /// The returned ID is always a valid ID when `current` refers to a valid
+    /// ID. Moreover, this routine is defined for all possible values of
+    /// `input`.
+    ///
+    /// These validity rules are not checked, even in debug mode. Callers are
+    /// required to uphold these rules themselves.
+    ///
+    /// Violating these state ID validity rules will not sacrifice memory
+    /// safety, but _may_ produce an incorrect result or a panic.
+    ///
+    /// # 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 or
+    /// incorrect ID.
+    ///
+    /// # Example
+    ///
+    /// This shows a simplistic example for walking a lazy DFA for a given
+    /// haystack by using the `next_state` method.
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, Input};
+    ///
+    /// let dfa = DFA::new(r"[a-z]+r")?;
+    /// let mut cache = dfa.create_cache();
+    /// let haystack = "bar".as_bytes();
+    ///
+    /// // The start state is determined by inspecting the position and the
+    /// // initial bytes of the haystack.
+    /// let mut sid = dfa.start_state_forward(
+    ///     &mut cache, &Input::new(haystack),
+    /// )?;
+    /// // Walk all the bytes in the haystack.
+    /// for &b in haystack {
+    ///     sid = dfa.next_state(&mut cache, sid, b)?;
+    /// }
+    /// // Matches are always delayed by 1 byte, so we must explicitly walk the
+    /// // special "EOI" transition at the end of the search.
+    /// sid = dfa.next_eoi_state(&mut cache, sid)?;
+    /// assert!(sid.is_match());
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn next_state(
+        &self,
+        cache: &mut Cache,
+        current: LazyStateID,
+        input: u8,
+    ) -> Result<LazyStateID, CacheError> {
+        let class = usize::from(self.classes.get(input));
+        let offset = current.as_usize_untagged() + class;
+        let sid = cache.trans[offset];
+        if !sid.is_unknown() {
+            return Ok(sid);
+        }
+        let unit = alphabet::Unit::u8(input);
+        Lazy::new(self, cache).cache_next_state(current, unit)
+    }
+
+    /// Transitions from the current state to the next state, given the next
+    /// byte of input and a state ID that is not tagged.
+    ///
+    /// The only reason to use this routine is performance. In particular, the
+    /// `next_state` method needs to do some additional checks, among them is
+    /// to account for identifiers to states that are not yet computed. In
+    /// such a case, the transition is computed on the fly. However, if it is
+    /// known that the `current` state ID is untagged, then these checks can be
+    /// omitted.
+    ///
+    /// Since this routine does not compute states on the fly, it does not
+    /// modify the cache and thus cannot return an error. Consequently, `cache`
+    /// does not need to be mutable and it is possible for this routine to
+    /// return a state ID corresponding to the special "unknown" state. In
+    /// this case, it is the caller's responsibility to use the prior state
+    /// ID and `input` with `next_state` in order to force the computation of
+    /// the unknown transition. Otherwise, trying to use the "unknown" state
+    /// ID will just result in transitioning back to itself, and thus never
+    /// terminating. (This is technically a special exemption to the state ID
+    /// validity rules, but is permissible since this routine is guarateed to
+    /// never mutate the given `cache`, and thus the identifier is guaranteed
+    /// to remain valid.)
+    ///
+    /// See [`LazyStateID`] for more details on what it means for a state ID
+    /// to be tagged. Also, see
+    /// [`next_state_untagged_unchecked`](DFA::next_state_untagged_unchecked)
+    /// for this same idea, but with bounds checks forcefully elided.
+    ///
+    /// # State identifier validity
+    ///
+    /// The only valid value for `current` is an **untagged** lazy
+    /// state ID returned by the most recent call to `next_state`,
+    /// `next_state_untagged`, `next_state_untagged_unchecked`,
+    /// `start_state_forward` or `state_state_reverse` for the given `cache`.
+    /// Any state ID returned from prior calls to these routines (with the
+    /// same `cache`) is considered invalid (even if it gives an appearance
+    /// of working). State IDs returned from _any_ prior call for different
+    /// `cache` values are also always invalid.
+    ///
+    /// The returned ID is always a valid ID when `current` refers to a valid
+    /// ID, although it may be tagged. Moreover, this routine is defined for
+    /// all possible values of `input`.
+    ///
+    /// Not all validity rules are checked, even in debug mode. Callers are
+    /// required to uphold these rules themselves.
+    ///
+    /// Violating these state ID validity rules will not sacrifice memory
+    /// safety, but _may_ produce an incorrect result or a panic.
+    ///
+    /// # 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 or
+    /// incorrect ID.
+    ///
+    /// # Example
+    ///
+    /// This shows a simplistic example for walking a lazy DFA for a given
+    /// haystack by using the `next_state_untagged` method where possible.
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, Input};
+    ///
+    /// let dfa = DFA::new(r"[a-z]+r")?;
+    /// let mut cache = dfa.create_cache();
+    /// let haystack = "bar".as_bytes();
+    ///
+    /// // The start state is determined by inspecting the position and the
+    /// // initial bytes of the haystack.
+    /// let mut sid = dfa.start_state_forward(
+    ///     &mut cache, &Input::new(haystack),
+    /// )?;
+    /// // Walk all the bytes in the haystack.
+    /// let mut at = 0;
+    /// while at < haystack.len() {
+    ///     if sid.is_tagged() {
+    ///         sid = dfa.next_state(&mut cache, sid, haystack[at])?;
+    ///     } else {
+    ///         let mut prev_sid = sid;
+    ///         // We attempt to chew through as much as we can while moving
+    ///         // through untagged state IDs. Thus, the transition function
+    ///         // does less work on average per byte. (Unrolling this loop
+    ///         // may help even more.)
+    ///         while at < haystack.len() {
+    ///             prev_sid = sid;
+    ///             sid = dfa.next_state_untagged(
+    ///                 &mut cache, sid, haystack[at],
+    ///             );
+    ///             at += 1;
+    ///             if sid.is_tagged() {
+    ///                 break;
+    ///             }
+    ///         }
+    ///         // We must ensure that we never proceed to the next iteration
+    ///         // with an unknown state ID. If we don't account for this
+    ///         // case, then search isn't guaranteed to terminate since all
+    ///         // transitions on unknown states loop back to itself.
+    ///         if sid.is_unknown() {
+    ///             sid = dfa.next_state(
+    ///                 &mut cache, prev_sid, haystack[at - 1],
+    ///             )?;
+    ///         }
+    ///     }
+    /// }
+    /// // Matches are always delayed by 1 byte, so we must explicitly walk the
+    /// // special "EOI" transition at the end of the search.
+    /// sid = dfa.next_eoi_state(&mut cache, sid)?;
+    /// assert!(sid.is_match());
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn next_state_untagged(
+        &self,
+        cache: &Cache,
+        current: LazyStateID,
+        input: u8,
+    ) -> LazyStateID {
+        debug_assert!(!current.is_tagged());
+        let class = usize::from(self.classes.get(input));
+        let offset = current.as_usize_unchecked() + class;
+        cache.trans[offset]
+    }
+
+    /// Transitions from the current state to the next state, eliding bounds
+    /// checks, given the next byte of input and a state ID that is not tagged.
+    ///
+    /// The only reason to use this routine is performance. In particular, the
+    /// `next_state` method needs to do some additional checks, among them is
+    /// to account for identifiers to states that are not yet computed. In
+    /// such a case, the transition is computed on the fly. However, if it is
+    /// known that the `current` state ID is untagged, then these checks can be
+    /// omitted.
+    ///
+    /// Since this routine does not compute states on the fly, it does not
+    /// modify the cache and thus cannot return an error. Consequently, `cache`
+    /// does not need to be mutable and it is possible for this routine to
+    /// return a state ID corresponding to the special "unknown" state. In
+    /// this case, it is the caller's responsibility to use the prior state
+    /// ID and `input` with `next_state` in order to force the computation of
+    /// the unknown transition. Otherwise, trying to use the "unknown" state
+    /// ID will just result in transitioning back to itself, and thus never
+    /// terminating. (This is technically a special exemption to the state ID
+    /// validity rules, but is permissible since this routine is guarateed to
+    /// never mutate the given `cache`, and thus the identifier is guaranteed
+    /// to remain valid.)
+    ///
+    /// See [`LazyStateID`] for more details on what it means for a state ID
+    /// to be tagged. Also, see
+    /// [`next_state_untagged`](DFA::next_state_untagged)
+    /// for this same idea, but with memory safety guaranteed by retaining
+    /// bounds checks.
+    ///
+    /// # State identifier validity
+    ///
+    /// The only valid value for `current` is an **untagged** lazy
+    /// state ID returned by the most recent call to `next_state`,
+    /// `next_state_untagged`, `next_state_untagged_unchecked`,
+    /// `start_state_forward` or `state_state_reverse` for the given `cache`.
+    /// Any state ID returned from prior calls to these routines (with the
+    /// same `cache`) is considered invalid (even if it gives an appearance
+    /// of working). State IDs returned from _any_ prior call for different
+    /// `cache` values are also always invalid.
+    ///
+    /// The returned ID is always a valid ID when `current` refers to a valid
+    /// ID, although it may be tagged. Moreover, this routine is defined for
+    /// all possible values of `input`.
+    ///
+    /// Not all validity rules are checked, even in debug mode. Callers are
+    /// required to uphold these rules themselves.
+    ///
+    /// Violating these state ID validity rules will not sacrifice memory
+    /// safety, but _may_ produce an incorrect result or a panic.
+    ///
+    /// # Safety
+    ///
+    /// Callers of this method must guarantee that `current` refers to a valid
+    /// state ID according to the rules described above. 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 the ID returned is valid for all possible
+    /// values of `input`.
+    #[inline]
+    pub unsafe fn next_state_untagged_unchecked(
+        &self,
+        cache: &Cache,
+        current: LazyStateID,
+        input: u8,
+    ) -> LazyStateID {
+        debug_assert!(!current.is_tagged());
+        let class = usize::from(self.classes.get(input));
+        let offset = current.as_usize_unchecked() + class;
+        *cache.trans.get_unchecked(offset)
+    }
+
+    /// Transitions from the current state to the next state for the special
+    /// EOI symbol.
+    ///
+    /// The given cache is used to either reuse pre-computed state
+    /// transitions, or to store this newly computed transition for future
+    /// reuse. Thus, this routine guarantees that it will never return a state
+    /// ID that has an "unknown" tag.
+    ///
+    /// This routine must be called at the end of every search in a correct
+    /// implementation of search. Namely, lazy 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
+    /// lazy 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.)
+    ///
+    /// # State identifier validity
+    ///
+    /// The only valid value for `current` is the lazy state ID returned
+    /// by the most recent call to `next_state`, `next_state_untagged`,
+    /// `next_state_untagged_unchecked`, `start_state_forward` or
+    /// `state_state_reverse` for the given `cache`. Any state ID returned from
+    /// prior calls to these routines (with the same `cache`) is considered
+    /// invalid (even if it gives an appearance of working). State IDs returned
+    /// from _any_ prior call for different `cache` values are also always
+    /// invalid.
+    ///
+    /// The returned ID is always a valid ID when `current` refers to a valid
+    /// ID.
+    ///
+    /// These validity rules are not checked, even in debug mode. Callers are
+    /// required to uphold these rules themselves.
+    ///
+    /// Violating these state ID validity rules will not sacrifice memory
+    /// safety, but _may_ produce an incorrect result or a panic.
+    ///
+    /// # 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 or
+    /// incorrect ID.
+    ///
+    /// # 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::{hybrid::dfa::DFA, Input};
+    ///
+    /// let dfa = DFA::new(r"[a-z]+r")?;
+    /// let mut cache = dfa.create_cache();
+    /// let haystack = "bar".as_bytes();
+    ///
+    /// // The start state is determined by inspecting the position and the
+    /// // initial bytes of the haystack.
+    /// let mut sid = dfa.start_state_forward(
+    ///     &mut cache, &Input::new(haystack),
+    /// )?;
+    /// // Walk all the bytes in the haystack.
+    /// for &b in haystack {
+    ///     sid = dfa.next_state(&mut cache, sid, 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!
+    /// sid = dfa.next_eoi_state(&mut cache, sid)?;
+    /// assert!(sid.is_match());
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn next_eoi_state(
+        &self,
+        cache: &mut Cache,
+        current: LazyStateID,
+    ) -> Result<LazyStateID, CacheError> {
+        let eoi = self.classes.eoi().as_usize();
+        let offset = current.as_usize_untagged() + eoi;
+        let sid = cache.trans[offset];
+        if !sid.is_unknown() {
+            return Ok(sid);
+        }
+        let unit = self.classes.eoi();
+        Lazy::new(self, cache).cache_next_state(current, unit)
+    }
+
+    /// Return the ID of the start state for this lazy DFA for the given
+    /// starting configuration.
+    ///
+    /// Unlike typical DFA implementations, the start state for DFAs in this
+    /// crate is dependent on a few different factors:
+    ///
+    /// * The [`Anchored`] mode of the search. Unanchored, anchored and
+    /// anchored searches for a specific [`PatternID`] all use different start
+    /// states.
+    /// * Whether a "look-behind" byte exists. For example, the `^` anchor
+    /// matches if and only if there is no look-behind byte.
+    /// * The specific value of that look-behind byte. For example, a `(?m:^)`
+    /// assertion only matches when there is either no look-behind byte, or
+    /// when the look-behind byte is a line terminator.
+    ///
+    /// The [starting configuration](start::Config) provides the above
+    /// information.
+    ///
+    /// This routine can be used for either forward or reverse searches.
+    /// Although, as a convenience, if you have an [`Input`], then it
+    /// may be more succinct to use [`DFA::start_state_forward`] or
+    /// [`DFA::start_state_reverse`]. Note, for example, that the convenience
+    /// routines return a [`MatchError`] on failure where as this routine
+    /// returns a [`StartError`].
+    ///
+    /// # Errors
+    ///
+    /// This may return a [`StartError`] if the search needs to give up when
+    /// determining the start state (for example, if it sees a "quit" byte
+    /// or if the cache has become inefficient). This can also return an
+    /// error if the given configuration contains an unsupported [`Anchored`]
+    /// configuration.
+    #[cfg_attr(feature = "perf-inline", inline(always))]
+    pub fn start_state(
+        &self,
+        cache: &mut Cache,
+        config: &start::Config,
+    ) -> Result<LazyStateID, StartError> {
+        let lazy = LazyRef::new(self, cache);
+        let anchored = config.get_anchored();
+        let start = match config.get_look_behind() {
+            None => Start::Text,
+            Some(byte) => {
+                if !self.quitset.is_empty() && self.quitset.contains(byte) {
+                    return Err(StartError::quit(byte));
+                }
+                self.start_map.get(byte)
+            }
+        };
+        let start_id = lazy.get_cached_start_id(anchored, start)?;
+        if !start_id.is_unknown() {
+            return Ok(start_id);
+        }
+        Lazy::new(self, cache).cache_start_group(anchored, start)
+    }
+
+    /// Return the ID of the start state for this lazy DFA when executing a
+    /// forward search.
+    ///
+    /// This is a convenience routine for calling [`DFA::start_state`] that
+    /// converts the given [`Input`] to a [start configuration](start::Config).
+    /// Additionally, if an error occurs, it is converted from a [`StartError`]
+    /// to a [`MatchError`] using the offset information in the given
+    /// [`Input`].
+    ///
+    /// # Errors
+    ///
+    /// This may return a [`MatchError`] if the search needs to give up when
+    /// determining the start state (for example, if it sees a "quit" byte or
+    /// if the cache has become inefficient). This can also return an error if
+    /// the given `Input` contains an unsupported [`Anchored`] configuration.
+    #[cfg_attr(feature = "perf-inline", inline(always))]
+    pub fn start_state_forward(
+        &self,
+        cache: &mut Cache,
+        input: &Input<'_>,
+    ) -> Result<LazyStateID, MatchError> {
+        let config = start::Config::from_input_forward(input);
+        self.start_state(cache, &config).map_err(|err| match err {
+            StartError::Cache { .. } => MatchError::gave_up(input.start()),
+            StartError::Quit { byte } => {
+                let offset = input
+                    .start()
+                    .checked_sub(1)
+                    .expect("no quit in start without look-behind");
+                MatchError::quit(byte, offset)
+            }
+            StartError::UnsupportedAnchored { mode } => {
+                MatchError::unsupported_anchored(mode)
+            }
+        })
+    }
+
+    /// Return the ID of the start state for this lazy DFA when executing a
+    /// reverse search.
+    ///
+    /// This is a convenience routine for calling [`DFA::start_state`] that
+    /// converts the given [`Input`] to a [start configuration](start::Config).
+    /// Additionally, if an error occurs, it is converted from a [`StartError`]
+    /// to a [`MatchError`] using the offset information in the given
+    /// [`Input`].
+    ///
+    /// # Errors
+    ///
+    /// This may return a [`MatchError`] if the search needs to give up when
+    /// determining the start state (for example, if it sees a "quit" byte or
+    /// if the cache has become inefficient). This can also return an error if
+    /// the given `Input` contains an unsupported [`Anchored`] configuration.
+    #[cfg_attr(feature = "perf-inline", inline(always))]
+    pub fn start_state_reverse(
+        &self,
+        cache: &mut Cache,
+        input: &Input<'_>,
+    ) -> Result<LazyStateID, MatchError> {
+        let config = start::Config::from_input_reverse(input);
+        self.start_state(cache, &config).map_err(|err| match err {
+            StartError::Cache { .. } => MatchError::gave_up(input.end()),
+            StartError::Quit { byte } => {
+                let offset = input.end();
+                MatchError::quit(byte, offset)
+            }
+            StartError::UnsupportedAnchored { mode } => {
+                MatchError::unsupported_anchored(mode)
+            }
+        })
+    }
+
+    /// Returns the total number of patterns that match in this state.
+    ///
+    /// If the lazy DFA was compiled with one pattern, then this must
+    /// necessarily always return `1` for all match states.
+    ///
+    /// A lazy DFA guarantees that [`DFA::match_pattern`] can be called with
+    /// indices up to (but not including) the length returned by this routine
+    /// without panicking.
+    ///
+    /// # Panics
+    ///
+    /// If the given state is not a match state, then this may either panic
+    /// or return an incorrect result.
+    ///
+    /// # 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`] when building the DFA. If we
+    /// used [`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.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, Input, MatchKind};
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().match_kind(MatchKind::All))
+    ///     .build_many(&[
+    ///         r"\w+", r"[a-z]+", r"[A-Z]+", r"\S+",
+    ///     ])?;
+    /// let mut cache = dfa.create_cache();
+    /// let haystack = "@bar".as_bytes();
+    ///
+    /// // The start state is determined by inspecting the position and the
+    /// // initial bytes of the haystack.
+    /// let mut sid = dfa.start_state_forward(
+    ///     &mut cache, &Input::new(haystack),
+    /// )?;
+    /// // Walk all the bytes in the haystack.
+    /// for &b in haystack {
+    ///     sid = dfa.next_state(&mut cache, sid, b)?;
+    /// }
+    /// sid = dfa.next_eoi_state(&mut cache, sid)?;
+    ///
+    /// assert!(sid.is_match());
+    /// assert_eq!(dfa.match_len(&mut cache, sid), 3);
+    /// // The following calls are guaranteed to not panic since `match_len`
+    /// // returned `3` above.
+    /// assert_eq!(dfa.match_pattern(&mut cache, sid, 0).as_usize(), 3);
+    /// assert_eq!(dfa.match_pattern(&mut cache, sid, 1).as_usize(), 0);
+    /// assert_eq!(dfa.match_pattern(&mut cache, sid, 2).as_usize(), 1);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn match_len(&self, cache: &Cache, id: LazyStateID) -> usize {
+        assert!(id.is_match());
+        LazyRef::new(self, cache).get_cached_state(id).match_len()
+    }
+
+    /// Returns the pattern ID corresponding to the given match index in the
+    /// given state.
+    ///
+    /// See [`DFA::match_len`] for an example of how to use this method
+    /// correctly. Note that if you know your lazy DFA is configured 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 `DFA::match_len` 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 always produces a valid
+    /// `PatternID`.
+    #[inline]
+    pub fn match_pattern(
+        &self,
+        cache: &Cache,
+        id: LazyStateID,
+        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 corresponding `State`, which
+        // requires a bit of slicing/pointer-chasing. This optimization tends
+        // to only matter when matches are frequent.
+        if self.pattern_len() == 1 {
+            return PatternID::ZERO;
+        }
+        LazyRef::new(self, cache)
+            .get_cached_state(id)
+            .match_pattern(match_index)
+    }
+}
+
+/// A cache represents a partially computed DFA.
+///
+/// A cache is the key component that differentiates a classical DFA and a
+/// hybrid NFA/DFA (also called a "lazy DFA"). Where a classical DFA builds a
+/// complete transition table that can handle all possible inputs, a hybrid
+/// NFA/DFA starts with an empty transition table and builds only the parts
+/// required during search. The parts that are built are stored in a cache. For
+/// this reason, a cache is a required parameter for nearly every operation on
+/// a [`DFA`].
+///
+/// Caches can be created from their corresponding DFA via
+/// [`DFA::create_cache`]. A cache can only be used with either the DFA that
+/// created it, or the DFA that was most recently used to reset it with
+/// [`Cache::reset`]. Using a cache with any other DFA may result in panics
+/// or incorrect results.
+#[derive(Clone, Debug)]
+pub struct Cache {
+    // N.B. If you're looking to understand how determinization works, it
+    // is probably simpler to first grok src/dfa/determinize.rs, since that
+    // doesn't have the "laziness" component.
+    /// The transition table.
+    ///
+    /// Given a `current` LazyStateID and an `input` byte, the next state can
+    /// be computed via `trans[untagged(current) + equiv_class(input)]`. Notice
+    /// that no multiplication is used. That's because state identifiers are
+    /// "premultiplied."
+    ///
+    /// Note that the next state may be the "unknown" state. In this case, the
+    /// next state is not known and determinization for `current` on `input`
+    /// must be performed.
+    trans: Vec<LazyStateID>,
+    /// The starting states for this DFA.
+    ///
+    /// These are computed lazily. Initially, these are all set to "unknown"
+    /// lazy state IDs.
+    ///
+    /// When 'starts_for_each_pattern' is disabled (the default), then the size
+    /// of this is constrained to the possible starting configurations based
+    /// on the search parameters. (At time of writing, that's 4.) However,
+    /// when starting states for each pattern is enabled, then there are N
+    /// additional groups of starting states, where each group reflects the
+    /// different possible configurations and N is the number of patterns.
+    starts: Vec<LazyStateID>,
+    /// A sequence of NFA/DFA powerset states that have been computed for this
+    /// lazy DFA. This sequence is indexable by untagged LazyStateIDs. (Every
+    /// tagged LazyStateID can be used to index this sequence by converting it
+    /// to its untagged form.)
+    states: Vec<State>,
+    /// A map from states to their corresponding IDs. This map may be accessed
+    /// via the raw byte representation of a state, which means that a `State`
+    /// does not need to be allocated to determine whether it already exists
+    /// in this map. Indeed, the existence of such a state is what determines
+    /// whether we allocate a new `State` or not.
+    ///
+    /// The higher level idea here is that we do just enough determinization
+    /// for a state to check whether we've already computed it. If we have,
+    /// then we can save a little (albeit not much) work. The real savings is
+    /// in memory usage. If we never checked for trivially duplicate states,
+    /// then our memory usage would explode to unreasonable levels.
+    states_to_id: StateMap,
+    /// Sparse sets used to track which NFA states have been visited during
+    /// various traversals.
+    sparses: SparseSets,
+    /// Scratch space for traversing the NFA graph. (We use space on the heap
+    /// instead of the call stack.)
+    stack: Vec<NFAStateID>,
+    /// Scratch space for building a NFA/DFA powerset state. This is used to
+    /// help amortize allocation since not every powerset state generated is
+    /// added to the cache. In particular, if it already exists in the cache,
+    /// then there is no need to allocate a new `State` for it.
+    scratch_state_builder: StateBuilderEmpty,
+    /// A simple abstraction for handling the saving of at most a single state
+    /// across a cache clearing. This is required for correctness. Namely, if
+    /// adding a new state after clearing the cache fails, then the caller
+    /// must retain the ability to continue using the state ID given. The
+    /// state corresponding to the state ID is what we preserve across cache
+    /// clearings.
+    state_saver: StateSaver,
+    /// The memory usage, in bytes, used by 'states' and 'states_to_id'. We
+    /// track this as new states are added since states use a variable amount
+    /// of heap. Tracking this as we add states makes it possible to compute
+    /// the total amount of memory used by the determinizer in constant time.
+    memory_usage_state: usize,
+    /// The number of times the cache has been cleared. When a minimum cache
+    /// clear count is set, then the cache will return an error instead of
+    /// clearing the cache if the count has been exceeded.
+    clear_count: usize,
+    /// The total number of bytes searched since the last time this cache was
+    /// cleared, not including the current search.
+    ///
+    /// This can be added to the length of the current search to get the true
+    /// total number of bytes searched.
+    ///
+    /// This is generally only non-zero when the
+    /// `Cache::search_{start,update,finish}` APIs are used to track search
+    /// progress.
+    bytes_searched: usize,
+    /// The progress of the current search.
+    ///
+    /// This is only non-`None` when callers utlize the `Cache::search_start`,
+    /// `Cache::search_update` and `Cache::search_finish` APIs.
+    ///
+    /// The purpose of recording search progress is to be able to make a
+    /// determination about the efficiency of the cache. Namely, by keeping
+    /// track of the
+    progress: Option<SearchProgress>,
+}
+
+impl Cache {
+    /// Create a new cache for the given lazy DFA.
+    ///
+    /// The cache returned should only be used for searches for the given DFA.
+    /// If you want to reuse the cache for another DFA, then you must call
+    /// [`Cache::reset`] with that DFA.
+    pub fn new(dfa: &DFA) -> Cache {
+        let mut cache = Cache {
+            trans: alloc::vec![],
+            starts: alloc::vec![],
+            states: alloc::vec![],
+            states_to_id: StateMap::new(),
+            sparses: SparseSets::new(dfa.get_nfa().states().len()),
+            stack: alloc::vec![],
+            scratch_state_builder: StateBuilderEmpty::new(),
+            state_saver: StateSaver::none(),
+            memory_usage_state: 0,
+            clear_count: 0,
+            bytes_searched: 0,
+            progress: None,
+        };
+        debug!("pre-init lazy DFA cache size: {}", cache.memory_usage());
+        Lazy { dfa, cache: &mut cache }.init_cache();
+        debug!("post-init lazy DFA cache size: {}", cache.memory_usage());
+        cache
+    }
+
+    /// Reset this cache such that it can be used for searching with the given
+    /// lazy DFA (and only that DFA).
+    ///
+    /// A cache reset permits reusing memory already allocated in this cache
+    /// with a different lazy DFA.
+    ///
+    /// Resetting a cache sets its "clear count" to 0. This is relevant if the
+    /// lazy DFA has been configured to "give up" after it has cleared the
+    /// cache a certain number of times.
+    ///
+    /// Any lazy state ID generated by the cache prior to resetting it is
+    /// invalid after the reset.
+    ///
+    /// # Example
+    ///
+    /// This shows how to re-purpose a cache for use with a different DFA.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// let dfa1 = DFA::new(r"\w")?;
+    /// let dfa2 = DFA::new(r"\W")?;
+    ///
+    /// let mut cache = dfa1.create_cache();
+    /// assert_eq!(
+    ///     Some(HalfMatch::must(0, 2)),
+    ///     dfa1.try_search_fwd(&mut cache, &Input::new("Δ"))?,
+    /// );
+    ///
+    /// // Using 'cache' with dfa2 is not allowed. It may result in panics or
+    /// // incorrect results. In order to re-purpose the cache, we must reset
+    /// // it with the DFA we'd like to use it with.
+    /// //
+    /// // Similarly, after this reset, using the cache with 'dfa1' is also not
+    /// // allowed.
+    /// cache.reset(&dfa2);
+    /// assert_eq!(
+    ///     Some(HalfMatch::must(0, 3)),
+    ///     dfa2.try_search_fwd(&mut cache, &Input::new("☃"))?,
+    /// );
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn reset(&mut self, dfa: &DFA) {
+        Lazy::new(dfa, self).reset_cache()
+    }
+
+    /// Initializes a new search starting at the given position.
+    ///
+    /// If a previous search was unfinished, then it is finished automatically
+    /// and a new search is begun.
+    ///
+    /// Note that keeping track of search progress is _not necessary_
+    /// for correct implementations of search using a lazy DFA. Keeping
+    /// track of search progress is only necessary if you want the
+    /// [`Config::minimum_bytes_per_state`] configuration knob to work.
+    #[inline]
+    pub fn search_start(&mut self, at: usize) {
+        // If a previous search wasn't marked as finished, then finish it
+        // now automatically.
+        if let Some(p) = self.progress.take() {
+            self.bytes_searched += p.len();
+        }
+        self.progress = Some(SearchProgress { start: at, at });
+    }
+
+    /// Updates the current search to indicate that it has search to the
+    /// current position.
+    ///
+    /// No special care needs to be taken for reverse searches. Namely, the
+    /// position given may be _less than_ the starting position of the search.
+    ///
+    /// # Panics
+    ///
+    /// This panics if no search has been started by [`Cache::search_start`].
+    #[inline]
+    pub fn search_update(&mut self, at: usize) {
+        let p =
+            self.progress.as_mut().expect("no in-progress search to update");
+        p.at = at;
+    }
+
+    /// Indicates that a search has finished at the given position.
+    ///
+    /// # Panics
+    ///
+    /// This panics if no search has been started by [`Cache::search_start`].
+    #[inline]
+    pub fn search_finish(&mut self, at: usize) {
+        let mut p =
+            self.progress.take().expect("no in-progress search to finish");
+        p.at = at;
+        self.bytes_searched += p.len();
+    }
+
+    /// Returns the total number of bytes that have been searched since this
+    /// cache was last cleared.
+    ///
+    /// This is useful for determining the efficiency of the cache. For
+    /// example, the lazy DFA uses this value in conjunction with the
+    /// [`Config::minimum_bytes_per_state`] knob to help determine whether it
+    /// should quit searching.
+    ///
+    /// This always returns `0` if search progress isn't being tracked. Note
+    /// that the lazy DFA search routines in this crate always track search
+    /// progress.
+    pub fn search_total_len(&self) -> usize {
+        self.bytes_searched + self.progress.as_ref().map_or(0, |p| p.len())
+    }
+
+    /// Returns the total number of times this cache has been cleared since it
+    /// was either created or last reset.
+    ///
+    /// This is useful for informational purposes or if you want to change
+    /// search strategies based on the number of times the cache has been
+    /// cleared.
+    pub fn clear_count(&self) -> usize {
+        self.clear_count
+    }
+
+    /// Returns the heap memory usage, in bytes, of this cache.
+    ///
+    /// This does **not** include the stack size used up by this cache. To
+    /// compute that, use `std::mem::size_of::<Cache>()`.
+    pub fn memory_usage(&self) -> usize {
+        const ID_SIZE: usize = size_of::<LazyStateID>();
+        const STATE_SIZE: usize = size_of::<State>();
+
+        // NOTE: If you make changes to the below, then
+        // 'minimum_cache_capacity' should be updated correspondingly.
+
+        self.trans.len() * ID_SIZE
+        + self.starts.len() * ID_SIZE
+        + self.states.len() * STATE_SIZE
+        // Maps likely use more memory than this, but it's probably close.
+        + self.states_to_id.len() * (STATE_SIZE + ID_SIZE)
+        + self.sparses.memory_usage()
+        + self.stack.capacity() * ID_SIZE
+        + self.scratch_state_builder.capacity()
+        // Heap memory used by 'State' in both 'states' and 'states_to_id'.
+        + self.memory_usage_state
+    }
+}
+
+/// Keeps track of the progress of the current search.
+///
+/// This is updated via the `Cache::search_{start,update,finish}` APIs to
+/// record how many bytes have been searched. This permits computing a
+/// heuristic that represents the efficiency of a cache, and thus helps inform
+/// whether the lazy DFA should give up or not.
+#[derive(Clone, Debug)]
+struct SearchProgress {
+    start: usize,
+    at: usize,
+}
+
+impl SearchProgress {
+    /// Returns the length, in bytes, of this search so far.
+    ///
+    /// This automatically handles the case of a reverse search, where `at`
+    /// is likely to be less than `start`.
+    fn len(&self) -> usize {
+        if self.start <= self.at {
+            self.at - self.start
+        } else {
+            self.start - self.at
+        }
+    }
+}
+
+/// A map from states to state identifiers. When using std, we use a standard
+/// hashmap, since it's a bit faster for this use case. (Other maps, like
+/// one's based on FNV, have not yet been benchmarked.)
+///
+/// The main purpose of this map is to reuse states where possible. This won't
+/// fully minimize the DFA, but it works well in a lot of cases.
+#[cfg(feature = "std")]
+type StateMap = std::collections::HashMap<State, LazyStateID>;
+#[cfg(not(feature = "std"))]
+type StateMap = alloc::collections::BTreeMap<State, LazyStateID>;
+
+/// A type that groups methods that require the base NFA/DFA and writable
+/// access to the cache.
+#[derive(Debug)]
+struct Lazy<'i, 'c> {
+    dfa: &'i DFA,
+    cache: &'c mut Cache,
+}
+
+impl<'i, 'c> Lazy<'i, 'c> {
+    /// Creates a new 'Lazy' wrapper for a DFA and its corresponding cache.
+    fn new(dfa: &'i DFA, cache: &'c mut Cache) -> Lazy<'i, 'c> {
+        Lazy { dfa, cache }
+    }
+
+    /// Return an immutable view by downgrading a writable cache to a read-only
+    /// cache.
+    fn as_ref<'a>(&'a self) -> LazyRef<'i, 'a> {
+        LazyRef::new(self.dfa, self.cache)
+    }
+
+    /// This is marked as 'inline(never)' to avoid bloating methods on 'DFA'
+    /// like 'next_state' and 'next_eoi_state' that are called in critical
+    /// areas. The idea is to let the optimizer focus on the other areas of
+    /// those methods as the hot path.
+    ///
+    /// Here's an example that justifies 'inline(never)'
+    ///
+    /// ```ignore
+    /// regex-cli find match hybrid \
+    ///   --cache-capacity 100000000 \
+    ///   -p '\pL{100}'
+    ///   all-codepoints-utf8-100x
+    /// ```
+    ///
+    /// Where 'all-codepoints-utf8-100x' is the UTF-8 encoding of every
+    /// codepoint, in sequence, repeated 100 times.
+    ///
+    /// With 'inline(never)' hyperfine reports 1.1s per run. With
+    /// 'inline(always)', hyperfine reports 1.23s. So that's a 10% improvement.
+    #[cold]
+    #[inline(never)]
+    fn cache_next_state(
+        &mut self,
+        mut current: LazyStateID,
+        unit: alphabet::Unit,
+    ) -> Result<LazyStateID, CacheError> {
+        let stride2 = self.dfa.stride2();
+        let empty_builder = self.get_state_builder();
+        let builder = determinize::next(
+            self.dfa.get_nfa(),
+            self.dfa.get_config().get_match_kind(),
+            &mut self.cache.sparses,
+            &mut self.cache.stack,
+            &self.cache.states[current.as_usize_untagged() >> stride2],
+            unit,
+            empty_builder,
+        );
+        let save_state = !self.as_ref().state_builder_fits_in_cache(&builder);
+        if save_state {
+            self.save_state(current);
+        }
+        let next = self.add_builder_state(builder, |sid| sid)?;
+        if save_state {
+            current = self.saved_state_id();
+        }
+        // This is the payoff. The next time 'next_state' is called with this
+        // state and alphabet unit, it will find this transition and avoid
+        // having to re-determinize this transition.
+        self.set_transition(current, unit, next);
+        Ok(next)
+    }
+
+    /// Compute and cache the starting state for the given pattern ID (if
+    /// present) and the starting configuration.
+    ///
+    /// This panics if a pattern ID is given and the DFA isn't configured to
+    /// build anchored start states for each pattern.
+    ///
+    /// This will never return an unknown lazy state ID.
+    ///
+    /// If caching this state would otherwise result in a cache that has been
+    /// cleared too many times, then an error is returned.
+    #[cold]
+    #[inline(never)]
+    fn cache_start_group(
+        &mut self,
+        anchored: Anchored,
+        start: Start,
+    ) -> Result<LazyStateID, StartError> {
+        let nfa_start_id = match anchored {
+            Anchored::No => self.dfa.get_nfa().start_unanchored(),
+            Anchored::Yes => self.dfa.get_nfa().start_anchored(),
+            Anchored::Pattern(pid) => {
+                if !self.dfa.get_config().get_starts_for_each_pattern() {
+                    return Err(StartError::unsupported_anchored(anchored));
+                }
+                match self.dfa.get_nfa().start_pattern(pid) {
+                    None => return Ok(self.as_ref().dead_id()),
+                    Some(sid) => sid,
+                }
+            }
+        };
+
+        let id = self
+            .cache_start_one(nfa_start_id, start)
+            .map_err(StartError::cache)?;
+        self.set_start_state(anchored, start, id);
+        Ok(id)
+    }
+
+    /// Compute and cache the starting state for the given NFA state ID and the
+    /// starting configuration. The NFA state ID might be one of the following:
+    ///
+    /// 1) An unanchored start state to match any pattern.
+    /// 2) An anchored start state to match any pattern.
+    /// 3) An anchored start state for a particular pattern.
+    ///
+    /// This will never return an unknown lazy state ID.
+    ///
+    /// If caching this state would otherwise result in a cache that has been
+    /// cleared too many times, then an error is returned.
+    fn cache_start_one(
+        &mut self,
+        nfa_start_id: NFAStateID,
+        start: Start,
+    ) -> Result<LazyStateID, CacheError> {
+        let mut builder_matches = self.get_state_builder().into_matches();
+        determinize::set_lookbehind_from_start(
+            self.dfa.get_nfa(),
+            &start,
+            &mut builder_matches,
+        );
+        self.cache.sparses.set1.clear();
+        determinize::epsilon_closure(
+            self.dfa.get_nfa(),
+            nfa_start_id,
+            builder_matches.look_have(),
+            &mut self.cache.stack,
+            &mut self.cache.sparses.set1,
+        );
+        let mut builder = builder_matches.into_nfa();
+        determinize::add_nfa_states(
+            &self.dfa.get_nfa(),
+            &self.cache.sparses.set1,
+            &mut builder,
+        );
+        let tag_starts = self.dfa.get_config().get_specialize_start_states();
+        self.add_builder_state(builder, |id| {
+            if tag_starts {
+                id.to_start()
+            } else {
+                id
+            }
+        })
+    }
+
+    /// Either add the given builder state to this cache, or return an ID to an
+    /// equivalent state already in this cache.
+    ///
+    /// In the case where no equivalent state exists, the idmap function given
+    /// may be used to transform the identifier allocated. This is useful if
+    /// the caller needs to tag the ID with additional information.
+    ///
+    /// This will never return an unknown lazy state ID.
+    ///
+    /// If caching this state would otherwise result in a cache that has been
+    /// cleared too many times, then an error is returned.
+    fn add_builder_state(
+        &mut self,
+        builder: StateBuilderNFA,
+        idmap: impl Fn(LazyStateID) -> LazyStateID,
+    ) -> Result<LazyStateID, CacheError> {
+        if let Some(&cached_id) =
+            self.cache.states_to_id.get(builder.as_bytes())
+        {
+            // Since we have a cached state, put the constructed state's
+            // memory back into our scratch space, so that it can be reused.
+            self.put_state_builder(builder);
+            return Ok(cached_id);
+        }
+        let result = self.add_state(builder.to_state(), idmap);
+        self.put_state_builder(builder);
+        result
+    }
+
+    /// Allocate a new state ID and add the given state to this cache.
+    ///
+    /// The idmap function given may be used to transform the identifier
+    /// allocated. This is useful if the caller needs to tag the ID with
+    /// additional information.
+    ///
+    /// This will never return an unknown lazy state ID.
+    ///
+    /// If caching this state would otherwise result in a cache that has been
+    /// cleared too many times, then an error is returned.
+    fn add_state(
+        &mut self,
+        state: State,
+        idmap: impl Fn(LazyStateID) -> LazyStateID,
+    ) -> Result<LazyStateID, CacheError> {
+        if !self.as_ref().state_fits_in_cache(&state) {
+            self.try_clear_cache()?;
+        }
+        // It's important for this to come second, since the above may clear
+        // the cache. If we clear the cache after ID generation, then the ID
+        // is likely bunk since it would have been generated based on a larger
+        // transition table.
+        let mut id = idmap(self.next_state_id()?);
+        if state.is_match() {
+            id = id.to_match();
+        }
+        // Add room in the transition table. Since this is a fresh state, all
+        // of its transitions are unknown.
+        self.cache.trans.extend(
+            iter::repeat(self.as_ref().unknown_id()).take(self.dfa.stride()),
+        );
+        // When we add a sentinel state, we never want to set any quit
+        // transitions. Technically, this is harmless, since sentinel states
+        // have all of their transitions set to loop back to themselves. But
+        // when creating sentinel states before the quit sentinel state,
+        // this will try to call 'set_transition' on a state ID that doesn't
+        // actually exist yet, which isn't allowed. So we just skip doing so
+        // entirely.
+        if !self.dfa.quitset.is_empty() && !self.as_ref().is_sentinel(id) {
+            let quit_id = self.as_ref().quit_id();
+            for b in self.dfa.quitset.iter() {
+                self.set_transition(id, alphabet::Unit::u8(b), quit_id);
+            }
+        }
+        self.cache.memory_usage_state += state.memory_usage();
+        self.cache.states.push(state.clone());
+        self.cache.states_to_id.insert(state, id);
+        Ok(id)
+    }
+
+    /// Allocate a new state ID.
+    ///
+    /// This will never return an unknown lazy state ID.
+    ///
+    /// If caching this state would otherwise result in a cache that has been
+    /// cleared too many times, then an error is returned.
+    fn next_state_id(&mut self) -> Result<LazyStateID, CacheError> {
+        let sid = match LazyStateID::new(self.cache.trans.len()) {
+            Ok(sid) => sid,
+            Err(_) => {
+                self.try_clear_cache()?;
+                // This has to pass since we check that ID capacity at
+                // construction time can fit at least MIN_STATES states.
+                LazyStateID::new(self.cache.trans.len()).unwrap()
+            }
+        };
+        Ok(sid)
+    }
+
+    /// Attempt to clear the cache used by this lazy DFA.
+    ///
+    /// If clearing the cache exceeds the minimum number of required cache
+    /// clearings, then this will return a cache error. In this case,
+    /// callers should bubble this up as the cache can't be used until it is
+    /// reset. Implementations of search should convert this error into a
+    /// [`MatchError::gave_up`].
+    ///
+    /// If 'self.state_saver' is set to save a state, then this state is
+    /// persisted through cache clearing. Otherwise, the cache is returned to
+    /// its state after initialization with two exceptions: its clear count
+    /// is incremented and some of its memory likely has additional capacity.
+    /// That is, clearing a cache does _not_ release memory.
+    ///
+    /// Otherwise, any lazy state ID generated by the cache prior to resetting
+    /// it is invalid after the reset.
+    fn try_clear_cache(&mut self) -> Result<(), CacheError> {
+        let c = self.dfa.get_config();
+        if let Some(min_count) = c.get_minimum_cache_clear_count() {
+            if self.cache.clear_count >= min_count {
+                if let Some(min_bytes_per) = c.get_minimum_bytes_per_state() {
+                    let len = self.cache.search_total_len();
+                    let min_bytes =
+                        min_bytes_per.saturating_mul(self.cache.states.len());
+                    // If we've searched 0 bytes then probably something has
+                    // gone wrong and the lazy DFA search implementation isn't
+                    // correctly updating the search progress state.
+                    if len == 0 {
+                        trace!(
+                            "number of bytes searched is 0, but \
+                             a minimum bytes per state searched ({}) is \
+                             enabled, maybe Cache::search_update \
+                             is not being used?",
+                            min_bytes_per,
+                        );
+                    }
+                    if len < min_bytes {
+                        trace!(
+                            "lazy DFA cache has been cleared {} times, \
+                             which exceeds the limit of {}, \
+                             AND its bytes searched per state is less \
+                             than the configured minimum of {}, \
+                             therefore lazy DFA is giving up \
+                             (bytes searched since cache clear = {}, \
+                              number of states = {})",
+                            self.cache.clear_count,
+                            min_count,
+                            min_bytes_per,
+                            len,
+                            self.cache.states.len(),
+                        );
+                        return Err(CacheError::bad_efficiency());
+                    } else {
+                        trace!(
+                            "lazy DFA cache has been cleared {} times, \
+                             which exceeds the limit of {}, \
+                             AND its bytes searched per state is greater \
+                             than the configured minimum of {}, \
+                             therefore lazy DFA is continuing! \
+                             (bytes searched since cache clear = {}, \
+                              number of states = {})",
+                            self.cache.clear_count,
+                            min_count,
+                            min_bytes_per,
+                            len,
+                            self.cache.states.len(),
+                        );
+                    }
+                } else {
+                    trace!(
+                        "lazy DFA cache has been cleared {} times, \
+                         which exceeds the limit of {}, \
+                         since there is no configured bytes per state \
+                         minimum, lazy DFA is giving up",
+                        self.cache.clear_count,
+                        min_count,
+                    );
+                    return Err(CacheError::too_many_cache_clears());
+                }
+            }
+        }
+        self.clear_cache();
+        Ok(())
+    }
+
+    /// Clears _and_ resets the cache. Resetting the cache means that no
+    /// states are persisted and the clear count is reset to 0. No heap memory
+    /// is released.
+    ///
+    /// Note that the caller may reset a cache with a different DFA than what
+    /// it was created from. In which case, the cache can now be used with the
+    /// new DFA (and not the old DFA).
+    fn reset_cache(&mut self) {
+        self.cache.state_saver = StateSaver::none();
+        self.clear_cache();
+        // If a new DFA is used, it might have a different number of NFA
+        // states, so we need to make sure our sparse sets have the appropriate
+        // size.
+        self.cache.sparses.resize(self.dfa.get_nfa().states().len());
+        self.cache.clear_count = 0;
+        self.cache.progress = None;
+    }
+
+    /// Clear the cache used by this lazy DFA.
+    ///
+    /// If 'self.state_saver' is set to save a state, then this state is
+    /// persisted through cache clearing. Otherwise, the cache is returned to
+    /// its state after initialization with two exceptions: its clear count
+    /// is incremented and some of its memory likely has additional capacity.
+    /// That is, clearing a cache does _not_ release memory.
+    ///
+    /// Otherwise, any lazy state ID generated by the cache prior to resetting
+    /// it is invalid after the reset.
+    fn clear_cache(&mut self) {
+        self.cache.trans.clear();
+        self.cache.starts.clear();
+        self.cache.states.clear();
+        self.cache.states_to_id.clear();
+        self.cache.memory_usage_state = 0;
+        self.cache.clear_count += 1;
+        self.cache.bytes_searched = 0;
+        if let Some(ref mut progress) = self.cache.progress {
+            progress.start = progress.at;
+        }
+        trace!(
+            "lazy DFA cache has been cleared (count: {})",
+            self.cache.clear_count
+        );
+        self.init_cache();
+        // If the state we want to save is one of the sentinel
+        // (unknown/dead/quit) states, then 'init_cache' adds those back, and
+        // their identifier values remains invariant. So there's no need to add
+        // it again. (And indeed, doing so would be incorrect!)
+        if let Some((old_id, state)) = self.cache.state_saver.take_to_save() {
+            // If the state is one of the special sentinel states, then it is
+            // automatically added by cache initialization and its ID always
+            // remains the same. With that said, this should never occur since
+            // the sentinel states are all loop states back to themselves. So
+            // we should never be in a position where we're attempting to save
+            // a sentinel state since we never compute transitions out of a
+            // sentinel state.
+            assert!(
+                !self.as_ref().is_sentinel(old_id),
+                "cannot save sentinel state"
+            );
+            let new_id = self
+                .add_state(state, |id| {
+                    if old_id.is_start() {
+                        // We don't need to consult the
+                        // 'specialize_start_states' config knob here, because
+                        // if it's disabled, old_id.is_start() will never
+                        // return true.
+                        id.to_start()
+                    } else {
+                        id
+                    }
+                })
+                // The unwrap here is OK because lazy DFA creation ensures that
+                // we have room in the cache to add MIN_STATES states. Since
+                // 'init_cache' above adds 3, this adds a 4th.
+                .expect("adding one state after cache clear must work");
+            self.cache.state_saver = StateSaver::Saved(new_id);
+        }
+    }
+
+    /// Initialize this cache from emptiness to a place where it can be used
+    /// for search.
+    ///
+    /// This is called both at cache creation time and after the cache has been
+    /// cleared.
+    ///
+    /// Primarily, this adds the three sentinel states and allocates some
+    /// initial memory.
+    fn init_cache(&mut self) {
+        // Why multiply by 2 here? Because we make room for both the unanchored
+        // and anchored start states. Unanchored is first and then anchored.
+        let mut starts_len = Start::len().checked_mul(2).unwrap();
+        // ... but if we also want start states for every pattern, we make room
+        // for that too.
+        if self.dfa.get_config().get_starts_for_each_pattern() {
+            starts_len += Start::len() * self.dfa.pattern_len();
+        }
+        self.cache
+            .starts
+            .extend(iter::repeat(self.as_ref().unknown_id()).take(starts_len));
+        // This is the set of NFA states that corresponds to each of our three
+        // sentinel states: the empty set.
+        let dead = State::dead();
+        // This sets up some states that we use as sentinels that are present
+        // in every DFA. While it would be technically possible to implement
+        // this DFA without explicitly putting these states in the transition
+        // table, this is convenient to do to make `next_state` correct for all
+        // valid state IDs without needing explicit conditionals to special
+        // case these sentinel states.
+        //
+        // All three of these states are "dead" states. That is, all of
+        // them transition only to themselves. So once you enter one of
+        // these states, it's impossible to leave them. Thus, any correct
+        // search routine must explicitly check for these state types. (Sans
+        // `unknown`, since that is only used internally to represent missing
+        // states.)
+        let unk_id =
+            self.add_state(dead.clone(), |id| id.to_unknown()).unwrap();
+        let dead_id = self.add_state(dead.clone(), |id| id.to_dead()).unwrap();
+        let quit_id = self.add_state(dead.clone(), |id| id.to_quit()).unwrap();
+        assert_eq!(unk_id, self.as_ref().unknown_id());
+        assert_eq!(dead_id, self.as_ref().dead_id());
+        assert_eq!(quit_id, self.as_ref().quit_id());
+        // The idea here is that if you start in an unknown/dead/quit state and
+        // try to transition on them, then you should end up where you started.
+        self.set_all_transitions(unk_id, unk_id);
+        self.set_all_transitions(dead_id, dead_id);
+        self.set_all_transitions(quit_id, quit_id);
+        // All of these states are technically equivalent from the FSM
+        // perspective, so putting all three of them in the cache isn't
+        // possible. (They are distinct merely because we use their
+        // identifiers as sentinels to mean something, as indicated by the
+        // names.) Moreover, we wouldn't want to do that. Unknown and quit
+        // states are special in that they are artificial constructions
+        // this implementation. But dead states are a natural part of
+        // determinization. When you reach a point in the NFA where you cannot
+        // go anywhere else, a dead state will naturally arise and we MUST
+        // reuse the canonical dead state that we've created here. Why? Because
+        // it is the state ID that tells the search routine whether a state is
+        // dead or not, and thus, whether to stop the search. Having a bunch of
+        // distinct dead states would be quite wasteful!
+        self.cache.states_to_id.insert(dead, dead_id);
+    }
+
+    /// Save the state corresponding to the ID given such that the state
+    /// persists through a cache clearing.
+    ///
+    /// While the state may persist, the ID may not. In order to discover the
+    /// new state ID, one must call 'saved_state_id' after a cache clearing.
+    fn save_state(&mut self, id: LazyStateID) {
+        let state = self.as_ref().get_cached_state(id).clone();
+        self.cache.state_saver = StateSaver::ToSave { id, state };
+    }
+
+    /// Returns the updated lazy state ID for a state that was persisted
+    /// through a cache clearing.
+    ///
+    /// It is only correct to call this routine when both a state has been
+    /// saved and the cache has just been cleared. Otherwise, this panics.
+    fn saved_state_id(&mut self) -> LazyStateID {
+        self.cache
+            .state_saver
+            .take_saved()
+            .expect("state saver does not have saved state ID")
+    }
+
+    /// Set all transitions on the state 'from' to 'to'.
+    fn set_all_transitions(&mut self, from: LazyStateID, to: LazyStateID) {
+        for unit in self.dfa.classes.representatives(..) {
+            self.set_transition(from, unit, to);
+        }
+    }
+
+    /// Set the transition on 'from' for 'unit' to 'to'.
+    ///
+    /// This panics if either 'from' or 'to' is invalid.
+    ///
+    /// All unit values are OK.
+    fn set_transition(
+        &mut self,
+        from: LazyStateID,
+        unit: alphabet::Unit,
+        to: LazyStateID,
+    ) {
+        assert!(self.as_ref().is_valid(from), "invalid 'from' id: {:?}", from);
+        assert!(self.as_ref().is_valid(to), "invalid 'to' id: {:?}", to);
+        let offset =
+            from.as_usize_untagged() + self.dfa.classes.get_by_unit(unit);
+        self.cache.trans[offset] = to;
+    }
+
+    /// Set the start ID for the given pattern ID (if given) and starting
+    /// configuration to the ID given.
+    ///
+    /// This panics if 'id' is not valid or if a pattern ID is given and
+    /// 'starts_for_each_pattern' is not enabled.
+    fn set_start_state(
+        &mut self,
+        anchored: Anchored,
+        start: Start,
+        id: LazyStateID,
+    ) {
+        assert!(self.as_ref().is_valid(id));
+        let start_index = start.as_usize();
+        let index = match anchored {
+            Anchored::No => start_index,
+            Anchored::Yes => Start::len() + start_index,
+            Anchored::Pattern(pid) => {
+                assert!(
+                    self.dfa.get_config().get_starts_for_each_pattern(),
+                    "attempted to search for a specific pattern \
+                     without enabling starts_for_each_pattern",
+                );
+                let pid = pid.as_usize();
+                (2 * Start::len()) + (Start::len() * pid) + start_index
+            }
+        };
+        self.cache.starts[index] = id;
+    }
+
+    /// Returns a state builder from this DFA that might have existing
+    /// capacity. This helps avoid allocs in cases where a state is built that
+    /// turns out to already be cached.
+    ///
+    /// Callers must put the state builder back with 'put_state_builder',
+    /// otherwise the allocation reuse won't work.
+    fn get_state_builder(&mut self) -> StateBuilderEmpty {
+        core::mem::replace(
+            &mut self.cache.scratch_state_builder,
+            StateBuilderEmpty::new(),
+        )
+    }
+
+    /// Puts the given state builder back into this DFA for reuse.
+    ///
+    /// Note that building a 'State' from a builder always creates a new alloc,
+    /// so callers should always put the builder back.
+    fn put_state_builder(&mut self, builder: StateBuilderNFA) {
+        let _ = core::mem::replace(
+            &mut self.cache.scratch_state_builder,
+            builder.clear(),
+        );
+    }
+}
+
+/// A type that groups methods that require the base NFA/DFA and read-only
+/// access to the cache.
+#[derive(Debug)]
+struct LazyRef<'i, 'c> {
+    dfa: &'i DFA,
+    cache: &'c Cache,
+}
+
+impl<'i, 'c> LazyRef<'i, 'c> {
+    /// Creates a new 'Lazy' wrapper for a DFA and its corresponding cache.
+    fn new(dfa: &'i DFA, cache: &'c Cache) -> LazyRef<'i, 'c> {
+        LazyRef { dfa, cache }
+    }
+
+    /// Return the ID of the start state for the given configuration.
+    ///
+    /// If the start state has not yet been computed, then this returns an
+    /// unknown lazy state ID.
+    #[cfg_attr(feature = "perf-inline", inline(always))]
+    fn get_cached_start_id(
+        &self,
+        anchored: Anchored,
+        start: Start,
+    ) -> Result<LazyStateID, StartError> {
+        let start_index = start.as_usize();
+        let index = match anchored {
+            Anchored::No => start_index,
+            Anchored::Yes => Start::len() + start_index,
+            Anchored::Pattern(pid) => {
+                if !self.dfa.get_config().get_starts_for_each_pattern() {
+                    return Err(StartError::unsupported_anchored(anchored));
+                }
+                if pid.as_usize() >= self.dfa.pattern_len() {
+                    return Ok(self.dead_id());
+                }
+                (2 * Start::len())
+                    + (Start::len() * pid.as_usize())
+                    + start_index
+            }
+        };
+        Ok(self.cache.starts[index])
+    }
+
+    /// Return the cached NFA/DFA powerset state for the given ID.
+    ///
+    /// This panics if the given ID does not address a valid state.
+    fn get_cached_state(&self, sid: LazyStateID) -> &State {
+        let index = sid.as_usize_untagged() >> self.dfa.stride2();
+        &self.cache.states[index]
+    }
+
+    /// Returns true if and only if the given ID corresponds to a "sentinel"
+    /// state.
+    ///
+    /// A sentinel state is a state that signifies a special condition of
+    /// search, and where every transition maps back to itself. See LazyStateID
+    /// for more details. Note that start and match states are _not_ sentinels
+    /// since they may otherwise be real states with non-trivial transitions.
+    /// The purposes of sentinel states is purely to indicate something. Their
+    /// transitions are not meant to be followed.
+    fn is_sentinel(&self, id: LazyStateID) -> bool {
+        id == self.unknown_id() || id == self.dead_id() || id == self.quit_id()
+    }
+
+    /// Returns the ID of the unknown state for this lazy DFA.
+    fn unknown_id(&self) -> LazyStateID {
+        // This unwrap is OK since 0 is always a valid state ID.
+        LazyStateID::new(0).unwrap().to_unknown()
+    }
+
+    /// Returns the ID of the dead state for this lazy DFA.
+    fn dead_id(&self) -> LazyStateID {
+        // This unwrap is OK since the maximum value here is 1 * 512 = 512,
+        // which is <= 2047 (the maximum state ID on 16-bit systems). Where
+        // 512 is the worst case for our equivalence classes (every byte is a
+        // distinct class).
+        LazyStateID::new(1 << self.dfa.stride2()).unwrap().to_dead()
+    }
+
+    /// Returns the ID of the quit state for this lazy DFA.
+    fn quit_id(&self) -> LazyStateID {
+        // This unwrap is OK since the maximum value here is 2 * 512 = 1024,
+        // which is <= 2047 (the maximum state ID on 16-bit systems). Where
+        // 512 is the worst case for our equivalence classes (every byte is a
+        // distinct class).
+        LazyStateID::new(2 << self.dfa.stride2()).unwrap().to_quit()
+    }
+
+    /// Returns true if and only if the given ID is valid.
+    ///
+    /// An ID is valid if it is both a valid index into the transition table
+    /// and is a multiple of the DFA's stride.
+    fn is_valid(&self, id: LazyStateID) -> bool {
+        let id = id.as_usize_untagged();
+        id < self.cache.trans.len() && id % self.dfa.stride() == 0
+    }
+
+    /// Returns true if adding the state given would fit in this cache.
+    fn state_fits_in_cache(&self, state: &State) -> bool {
+        let needed = self.cache.memory_usage()
+            + self.memory_usage_for_one_more_state(state.memory_usage());
+        trace!(
+            "lazy DFA cache capacity check: {:?} ?<=? {:?}",
+            needed,
+            self.dfa.cache_capacity
+        );
+        needed <= self.dfa.cache_capacity
+    }
+
+    /// Returns true if adding the state to be built by the given builder would
+    /// fit in this cache.
+    fn state_builder_fits_in_cache(&self, state: &StateBuilderNFA) -> bool {
+        let needed = self.cache.memory_usage()
+            + self.memory_usage_for_one_more_state(state.as_bytes().len());
+        needed <= self.dfa.cache_capacity
+    }
+
+    /// Returns the additional memory usage, in bytes, required to add one more
+    /// state to this cache. The given size should be the heap size, in bytes,
+    /// that would be used by the new state being added.
+    fn memory_usage_for_one_more_state(
+        &self,
+        state_heap_size: usize,
+    ) -> usize {
+        const ID_SIZE: usize = size_of::<LazyStateID>();
+        const STATE_SIZE: usize = size_of::<State>();
+
+        self.dfa.stride() * ID_SIZE // additional space needed in trans table
+        + STATE_SIZE // space in cache.states
+        + (STATE_SIZE + ID_SIZE) // space in cache.states_to_id
+        + state_heap_size // heap memory used by state itself
+    }
+}
+
+/// A simple type that encapsulates the saving of a state ID through a cache
+/// clearing.
+///
+/// A state ID can be marked for saving with ToSave, while a state ID can be
+/// saved itself with Saved.
+#[derive(Clone, Debug)]
+enum StateSaver {
+    /// An empty state saver. In this case, no states (other than the special
+    /// sentinel states) are preserved after clearing the cache.
+    None,
+    /// An ID of a state (and the state itself) that should be preserved after
+    /// the lazy DFA's cache has been cleared. After clearing, the updated ID
+    /// is stored in 'Saved' since it may have changed.
+    ToSave { id: LazyStateID, state: State },
+    /// An ID that of a state that has been persisted through a lazy DFA
+    /// cache clearing. The ID recorded here corresponds to an ID that was
+    /// once marked as ToSave. The IDs are likely not equivalent even though
+    /// the states they point to are.
+    Saved(LazyStateID),
+}
+
+impl StateSaver {
+    /// Create an empty state saver.
+    fn none() -> StateSaver {
+        StateSaver::None
+    }
+
+    /// Replace this state saver with an empty saver, and if this saver is a
+    /// request to save a state, return that request.
+    fn take_to_save(&mut self) -> Option<(LazyStateID, State)> {
+        match core::mem::replace(self, StateSaver::None) {
+            StateSaver::None | StateSaver::Saved(_) => None,
+            StateSaver::ToSave { id, state } => Some((id, state)),
+        }
+    }
+
+    /// Replace this state saver with an empty saver, and if this saver is a
+    /// saved state (or a request to save a state), return that state's ID.
+    ///
+    /// The idea here is that a request to save a state isn't necessarily
+    /// honored because it might not be needed. e.g., Some higher level code
+    /// might request a state to be saved on the off chance that the cache gets
+    /// cleared when a new state is added at a lower level. But if that new
+    /// state is never added, then the cache is never cleared and the state and
+    /// its ID remain unchanged.
+    fn take_saved(&mut self) -> Option<LazyStateID> {
+        match core::mem::replace(self, StateSaver::None) {
+            StateSaver::None => None,
+            StateSaver::Saved(id) | StateSaver::ToSave { id, .. } => Some(id),
+        }
+    }
+}
+
+/// The configuration used for building a lazy DFA.
+///
+/// As a convenience, [`DFA::config`] is an alias for [`Config::new`]. The
+/// advantage of the former is that it often lets you avoid importing the
+/// `Config` type directly.
+///
+/// A lazy DFA configuration is a simple data object that is typically used
+/// with [`Builder::configure`].
+///
+/// The default configuration guarantees that a search will never return a
+/// "gave up" or "quit" error, although it is possible for a search to fail
+/// if [`Config::starts_for_each_pattern`] wasn't enabled (which it is not by
+/// default) and an [`Anchored::Pattern`] mode is requested via [`Input`].
+#[derive(Clone, Debug, Default)]
+pub struct Config {
+    // As with other configuration types in this crate, we put all our knobs
+    // in options so that we can distinguish between "default" and "not set."
+    // This makes it possible to easily combine multiple configurations
+    // without default values overwriting explicitly specified values. See the
+    // 'overwrite' method.
+    //
+    // For docs on the fields below, see the corresponding method setters.
+    match_kind: Option<MatchKind>,
+    pre: Option<Option<Prefilter>>,
+    starts_for_each_pattern: Option<bool>,
+    byte_classes: Option<bool>,
+    unicode_word_boundary: Option<bool>,
+    quitset: Option<ByteSet>,
+    specialize_start_states: Option<bool>,
+    cache_capacity: Option<usize>,
+    skip_cache_capacity_check: Option<bool>,
+    minimum_cache_clear_count: Option<Option<usize>>,
+    minimum_bytes_per_state: Option<Option<usize>>,
+}
+
+impl Config {
+    /// Return a new default lazy DFA builder configuration.
+    pub fn new() -> Config {
+        Config::default()
+    }
+
+    /// Set the desired match semantics.
+    ///
+    /// The default is [`MatchKind::LeftmostFirst`], which corresponds to the
+    /// match semantics of Perl-like regex engines. That is, when multiple
+    /// patterns would match at the same leftmost position, the pattern that
+    /// appears first in the concrete syntax is chosen.
+    ///
+    /// Currently, the only other kind of match semantics supported is
+    /// [`MatchKind::All`]. This corresponds to classical DFA construction
+    /// where all possible matches are added to the lazy DFA.
+    ///
+    /// Typically, `All` is used when one wants to execute an overlapping
+    /// search and `LeftmostFirst` otherwise. In particular, it rarely makes
+    /// sense to use `All` with the various "leftmost" find routines, since the
+    /// leftmost routines depend on the `LeftmostFirst` automata construction
+    /// strategy. Specifically, `LeftmostFirst` adds dead states to the
+    /// lazy DFA as a way to terminate the search and report a match.
+    /// `LeftmostFirst` also supports non-greedy matches using this strategy
+    /// where as `All` does not.
+    ///
+    /// # Example: overlapping search
+    ///
+    /// This example shows the typical use of `MatchKind::All`, which is to
+    /// report overlapping matches.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{
+    ///     hybrid::dfa::{DFA, OverlappingState},
+    ///     HalfMatch, Input, MatchKind,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().match_kind(MatchKind::All))
+    ///     .build_many(&[r"\w+$", r"\S+$"])?;
+    /// let mut cache = dfa.create_cache();
+    /// let haystack = "@foo";
+    /// let mut state = OverlappingState::start();
+    ///
+    /// let expected = Some(HalfMatch::must(1, 4));
+    /// dfa.try_search_overlapping_fwd(
+    ///     &mut cache, &Input::new(haystack), &mut state,
+    /// )?;
+    /// assert_eq!(expected, state.get_match());
+    ///
+    /// // 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));
+    /// dfa.try_search_overlapping_fwd(
+    ///     &mut cache, &Input::new(haystack), &mut state,
+    /// )?;
+    /// assert_eq!(expected, state.get_match());
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// # Example: reverse automaton to find start of match
+    ///
+    /// Another example for using `MatchKind::All` is for constructing a
+    /// reverse automaton to find the start of a match. `All` semantics are
+    /// used for this in order to find the longest possible match, which
+    /// corresponds to the leftmost starting position.
+    ///
+    /// Note that if you need the starting position then
+    /// [`hybrid::regex::Regex`](crate::hybrid::regex::Regex) will handle this
+    /// for you, so it's usually not necessary to do this yourself.
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     nfa::thompson::NFA,
+    ///     Anchored, HalfMatch, Input, MatchKind,
+    /// };
+    ///
+    /// let input = Input::new("123foobar456");
+    /// let pattern = r"[a-z]+r";
+    ///
+    /// let dfa_fwd = DFA::new(pattern)?;
+    /// let dfa_rev = DFA::builder()
+    ///     .thompson(NFA::config().reverse(true))
+    ///     .configure(DFA::config().match_kind(MatchKind::All))
+    ///     .build(pattern)?;
+    /// let mut cache_fwd = dfa_fwd.create_cache();
+    /// let mut cache_rev = dfa_rev.create_cache();
+    ///
+    /// let expected_fwd = HalfMatch::must(0, 9);
+    /// let expected_rev = HalfMatch::must(0, 3);
+    /// let got_fwd = dfa_fwd.try_search_fwd(&mut cache_fwd, &input)?.unwrap();
+    /// // Here we don't specify the pattern to search for since there's only
+    /// // one pattern and we're doing a leftmost search. But if this were an
+    /// // overlapping search, you'd need to specify the pattern that matched
+    /// // in the forward direction. (Otherwise, you might wind up finding the
+    /// // starting position of a match of some other pattern.) That in turn
+    /// // requires building the reverse automaton with starts_for_each_pattern
+    /// // enabled.
+    /// let input = input
+    ///     .clone()
+    ///     .range(..got_fwd.offset())
+    ///     .anchored(Anchored::Yes);
+    /// let got_rev = dfa_rev.try_search_rev(&mut cache_rev, &input)?.unwrap();
+    /// assert_eq!(expected_fwd, got_fwd);
+    /// assert_eq!(expected_rev, got_rev);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn match_kind(mut self, kind: MatchKind) -> Config {
+        self.match_kind = Some(kind);
+        self
+    }
+
+    /// Set a prefilter to be used whenever a start state is entered.
+    ///
+    /// A [`Prefilter`] in this context is meant to accelerate searches by
+    /// looking for literal prefixes that every match for the corresponding
+    /// pattern (or patterns) must start with. Once a prefilter produces a
+    /// match, the underlying search routine continues on to try and confirm
+    /// the match.
+    ///
+    /// Be warned that setting a prefilter does not guarantee that the search
+    /// will be faster. While it's usually a good bet, if the prefilter
+    /// produces a lot of false positive candidates (i.e., positions matched
+    /// by the prefilter but not by the regex), then the overall result can
+    /// be slower than if you had just executed the regex engine without any
+    /// prefilters.
+    ///
+    /// Note that unless [`Config::specialize_start_states`] has been
+    /// explicitly set, then setting this will also enable (when `pre` is
+    /// `Some`) or disable (when `pre` is `None`) start state specialization.
+    /// This occurs because without start state specialization, a prefilter
+    /// is likely to be less effective. And without a prefilter, start state
+    /// specialization is usually pointless.
+    ///
+    /// By default no prefilter is set.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     util::prefilter::Prefilter,
+    ///     Input, HalfMatch, MatchKind,
+    /// };
+    ///
+    /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["foo", "bar"]);
+    /// let re = DFA::builder()
+    ///     .configure(DFA::config().prefilter(pre))
+    ///     .build(r"(foo|bar)[a-z]+")?;
+    /// let mut cache = re.create_cache();
+    /// let input = Input::new("foo1 barfox bar");
+    /// assert_eq!(
+    ///     Some(HalfMatch::must(0, 11)),
+    ///     re.try_search_fwd(&mut cache, &input)?,
+    /// );
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// Be warned though that an incorrect prefilter can lead to incorrect
+    /// results!
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     util::prefilter::Prefilter,
+    ///     Input, HalfMatch, MatchKind,
+    /// };
+    ///
+    /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["foo", "car"]);
+    /// let re = DFA::builder()
+    ///     .configure(DFA::config().prefilter(pre))
+    ///     .build(r"(foo|bar)[a-z]+")?;
+    /// let mut cache = re.create_cache();
+    /// let input = Input::new("foo1 barfox bar");
+    /// assert_eq!(
+    ///     // No match reported even though there clearly is one!
+    ///     None,
+    ///     re.try_search_fwd(&mut cache, &input)?,
+    /// );
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn prefilter(mut self, pre: Option<Prefilter>) -> Config {
+        self.pre = Some(pre);
+        if self.specialize_start_states.is_none() {
+            self.specialize_start_states =
+                Some(self.get_prefilter().is_some());
+        }
+        self
+    }
+
+    /// Whether to compile a separate start state for each pattern in the
+    /// lazy DFA.
+    ///
+    /// When enabled, a separate **anchored** start state is added for each
+    /// pattern in the lazy DFA. When this start state is used, then the DFA
+    /// will only search for matches for the pattern specified, even if there
+    /// are other patterns in the DFA.
+    ///
+    /// The main downside of this option is that it can potentially increase
+    /// the size of the DFA and/or increase the time it takes to build the
+    /// DFA at search time. However, since this is configuration for a lazy
+    /// DFA, these states aren't actually built unless they're used. Enabling
+    /// this isn't necessarily free, however, as it may result in higher cache
+    /// usage.
+    ///
+    /// There are a few reasons one might want to enable this (it's disabled
+    /// by default):
+    ///
+    /// 1. When looking for the start of an overlapping match (using a reverse
+    /// DFA), doing it correctly requires starting the reverse search using the
+    /// starting state of the pattern that matched in the forward direction.
+    /// Indeed, when building a [`Regex`](crate::hybrid::regex::Regex), it
+    /// will automatically enable this option when building the reverse DFA
+    /// internally.
+    /// 2. When you want to use a DFA with multiple patterns to both search
+    /// for matches of any pattern or to search for anchored matches of one
+    /// particular pattern while using the same DFA. (Otherwise, you would need
+    /// to compile a new DFA for each pattern.)
+    ///
+    /// By default this is disabled.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to use this option to permit the same lazy DFA
+    /// to run both general searches for any pattern and anchored searches for
+    /// a specific pattern.
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     Anchored, HalfMatch, Input, PatternID,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().starts_for_each_pattern(true))
+    ///     .build_many(&[r"[a-z0-9]{6}", r"[a-z][a-z0-9]{5}"])?;
+    /// let mut cache = dfa.create_cache();
+    /// let haystack = "bar foo123";
+    ///
+    /// // Here's a normal unanchored search that looks for any pattern.
+    /// let expected = HalfMatch::must(0, 10);
+    /// let input = Input::new(haystack);
+    /// assert_eq!(Some(expected), dfa.try_search_fwd(&mut cache, &input)?);
+    /// // We can also do a normal anchored search for any pattern. Since it's
+    /// // an anchored search, we position the start of the search where we
+    /// // know the match will begin.
+    /// let expected = HalfMatch::must(0, 10);
+    /// let input = Input::new(haystack).range(4..);
+    /// assert_eq!(Some(expected), dfa.try_search_fwd(&mut cache, &input)?);
+    /// // Since we compiled anchored start states for each pattern, we can
+    /// // also look for matches of other patterns explicitly, even if a
+    /// // different pattern would have normally matched.
+    /// let expected = HalfMatch::must(1, 10);
+    /// let input = Input::new(haystack)
+    ///     .range(4..)
+    ///     .anchored(Anchored::Pattern(PatternID::must(1)));
+    /// assert_eq!(Some(expected), dfa.try_search_fwd(&mut cache, &input)?);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn starts_for_each_pattern(mut self, yes: bool) -> Config {
+        self.starts_for_each_pattern = Some(yes);
+        self
+    }
+
+    /// Whether to attempt to shrink the size of the lazy DFA's alphabet or
+    /// not.
+    ///
+    /// This option is enabled by default and should never be disabled unless
+    /// one is debugging the lazy DFA.
+    ///
+    /// When enabled, the lazy DFA will use a map from all possible bytes
+    /// to their corresponding equivalence class. Each equivalence class
+    /// represents a set of bytes that does not discriminate between a match
+    /// and a non-match in the DFA. For example, the pattern `[ab]+` has at
+    /// least two equivalence classes: a set containing `a` and `b` and a set
+    /// containing every byte except for `a` and `b`. `a` and `b` are in the
+    /// same equivalence classes because they never discriminate between a
+    /// match and a non-match.
+    ///
+    /// The advantage of this map is that the size of the transition table
+    /// can be reduced drastically from `#states * 256 * sizeof(LazyStateID)`
+    /// to `#states * k * sizeof(LazyStateID)` where `k` is the number of
+    /// equivalence classes (rounded up to the nearest power of 2). As a
+    /// result, total space usage can decrease substantially. Moreover, since a
+    /// smaller alphabet is used, DFA compilation during search becomes faster
+    /// as well since it will potentially be able to reuse a single transition
+    /// for multiple bytes.
+    ///
+    /// **WARNING:** This is only useful for debugging lazy DFAs. Disabling
+    /// this does not yield any speed advantages. Namely, even when this is
+    /// disabled, a byte class map is still used while searching. The only
+    /// difference is that every byte will be forced into its own distinct
+    /// equivalence class. This is useful for debugging the actual generated
+    /// transitions because it lets one see the transitions defined on actual
+    /// bytes instead of the equivalence classes.
+    pub fn byte_classes(mut self, yes: bool) -> Config {
+        self.byte_classes = Some(yes);
+        self
+    }
+
+    /// Heuristically enable Unicode word boundaries.
+    ///
+    /// When set, this will attempt to implement Unicode word boundaries as if
+    /// they were ASCII word boundaries. This only works when the search input
+    /// is ASCII only. If a non-ASCII byte is observed while searching, then a
+    /// [`MatchError::quit`] error is returned.
+    ///
+    /// A possible alternative to enabling this option is to simply use an
+    /// ASCII word boundary, e.g., via `(?-u:\b)`. The main reason to use this
+    /// option is if you absolutely need Unicode support. This option lets one
+    /// use a fast search implementation (a DFA) for some potentially very
+    /// common cases, while providing the option to fall back to some other
+    /// regex engine to handle the general case when an error is returned.
+    ///
+    /// If the pattern provided has no Unicode word boundary in it, then this
+    /// option has no effect. (That is, quitting on a non-ASCII byte only
+    /// occurs when this option is enabled _and_ a Unicode word boundary is
+    /// present in the pattern.)
+    ///
+    /// This is almost equivalent to setting all non-ASCII bytes to be quit
+    /// bytes. The only difference is that this will cause non-ASCII bytes to
+    /// be quit bytes _only_ when a Unicode word boundary is present in the
+    /// pattern.
+    ///
+    /// When enabling this option, callers _must_ be prepared to
+    /// handle a [`MatchError`] error during search. When using a
+    /// [`Regex`](crate::hybrid::regex::Regex), this corresponds to using the
+    /// `try_` suite of methods. Alternatively, if callers can guarantee that
+    /// their input is ASCII only, then a [`MatchError::quit`] error will never
+    /// be returned while searching.
+    ///
+    /// This is disabled by default.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to heuristically enable Unicode word boundaries
+    /// in a pattern. It also shows what happens when a search comes across a
+    /// non-ASCII byte.
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     HalfMatch, Input, MatchError,
+    /// };
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().unicode_word_boundary(true))
+    ///     .build(r"\b[0-9]+\b")?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// // The match occurs before the search ever observes the snowman
+    /// // character, so no error occurs.
+    /// let haystack = "foo 123  ☃";
+    /// let expected = Some(HalfMatch::must(0, 7));
+    /// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack))?;
+    /// assert_eq!(expected, got);
+    ///
+    /// // Notice that this search fails, even though the snowman character
+    /// // occurs after the ending match offset. This is because search
+    /// // routines read one byte past the end of the search to account for
+    /// // look-around, and indeed, this is required here to determine whether
+    /// // the trailing \b matches.
+    /// let haystack = "foo 123 ☃";
+    /// let expected = MatchError::quit(0xE2, 8);
+    /// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack));
+    /// assert_eq!(Err(expected), got);
+    ///
+    /// // Another example is executing a search where the span of the haystack
+    /// // we specify is all ASCII, but there is non-ASCII just before it. This
+    /// // correctly also reports an error.
+    /// let input = Input::new("β123").range(2..);
+    /// let expected = MatchError::quit(0xB2, 1);
+    /// let got = dfa.try_search_fwd(&mut cache, &input);
+    /// assert_eq!(Err(expected), got);
+    ///
+    /// // And similarly for the trailing word boundary.
+    /// let input = Input::new("123β").range(..3);
+    /// let expected = MatchError::quit(0xCE, 3);
+    /// let got = dfa.try_search_fwd(&mut cache, &input);
+    /// assert_eq!(Err(expected), got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn unicode_word_boundary(mut self, yes: bool) -> Config {
+        // We have a separate option for this instead of just setting the
+        // appropriate quit bytes here because we don't want to set quit bytes
+        // for every regex. We only want to set them when the regex contains a
+        // Unicode word boundary.
+        self.unicode_word_boundary = Some(yes);
+        self
+    }
+
+    /// Add a "quit" byte to the lazy DFA.
+    ///
+    /// When a quit byte is seen during search time, then search will return a
+    /// [`MatchError::quit`] error indicating the offset at which the search
+    /// stopped.
+    ///
+    /// A quit byte will always overrule any other aspects of a regex. For
+    /// example, if the `x` byte is added as a quit byte and the regex `\w` is
+    /// used, then observing `x` will cause the search to quit immediately
+    /// despite the fact that `x` is in the `\w` class.
+    ///
+    /// This mechanism is primarily useful for heuristically enabling certain
+    /// features like Unicode word boundaries in a DFA. Namely, if the input
+    /// to search is ASCII, then a Unicode word boundary can be implemented
+    /// via an ASCII word boundary with no change in semantics. Thus, a DFA
+    /// can attempt to match a Unicode word boundary but give up as soon as it
+    /// observes a non-ASCII byte. Indeed, if callers set all non-ASCII bytes
+    /// to be quit bytes, then Unicode word boundaries will be permitted when
+    /// building lazy DFAs. Of course, callers should enable
+    /// [`Config::unicode_word_boundary`] if they want this behavior instead.
+    /// (The advantage being that non-ASCII quit bytes will only be added if a
+    /// Unicode word boundary is in the pattern.)
+    ///
+    /// When enabling this option, callers _must_ be prepared to
+    /// handle a [`MatchError`] error during search. When using a
+    /// [`Regex`](crate::hybrid::regex::Regex), this corresponds to using the
+    /// `try_` suite of methods.
+    ///
+    /// By default, there are no quit bytes set.
+    ///
+    /// # Panics
+    ///
+    /// This panics if heuristic Unicode word boundaries are enabled and any
+    /// non-ASCII byte is removed from the set of quit bytes. Namely, enabling
+    /// Unicode word boundaries requires setting every non-ASCII byte to a quit
+    /// byte. So if the caller attempts to undo any of that, then this will
+    /// panic.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to cause a search to terminate if it sees a
+    /// `\n` byte. This could be useful if, for example, you wanted to prevent
+    /// a user supplied pattern from matching across a line boundary.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, MatchError, Input};
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().quit(b'\n', true))
+    ///     .build(r"foo\p{any}+bar")?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let haystack = "foo\nbar";
+    /// // Normally this would produce a match, since \p{any} contains '\n'.
+    /// // But since we instructed the automaton to enter a quit state if a
+    /// // '\n' is observed, this produces a match error instead.
+    /// let expected = MatchError::quit(b'\n', 3);
+    /// let got = dfa.try_search_fwd(
+    ///     &mut cache,
+    ///     &Input::new(haystack),
+    /// ).unwrap_err();
+    /// assert_eq!(expected, got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn quit(mut self, byte: u8, yes: bool) -> Config {
+        if self.get_unicode_word_boundary() && !byte.is_ascii() && !yes {
+            panic!(
+                "cannot set non-ASCII byte to be non-quit when \
+                 Unicode word boundaries are enabled"
+            );
+        }
+        if self.quitset.is_none() {
+            self.quitset = Some(ByteSet::empty());
+        }
+        if yes {
+            self.quitset.as_mut().unwrap().add(byte);
+        } else {
+            self.quitset.as_mut().unwrap().remove(byte);
+        }
+        self
+    }
+
+    /// Enable specializing start states in the lazy DFA.
+    ///
+    /// When start states are specialized, an implementor of a search routine
+    /// using a lazy DFA can tell when the search has entered a starting state.
+    /// When start states aren't specialized, then it is impossible to know
+    /// whether the search has entered a start state.
+    ///
+    /// Ideally, this option wouldn't need to exist and we could always
+    /// specialize start states. The problem is that start states can be quite
+    /// active. This in turn means that an efficient search routine is likely
+    /// to ping-pong between a heavily optimized hot loop that handles most
+    /// states and to a less optimized specialized handling of start states.
+    /// This causes branches to get heavily mispredicted and overall can
+    /// materially decrease throughput. Therefore, specializing start states
+    /// should only be enabled when it is needed.
+    ///
+    /// Knowing whether a search is in a start state is typically useful when a
+    /// prefilter is active for the search. A prefilter is typically only run
+    /// when in a start state and a prefilter can greatly accelerate a search.
+    /// Therefore, the possible cost of specializing start states is worth it
+    /// in this case. Otherwise, if you have no prefilter, there is likely no
+    /// reason to specialize start states.
+    ///
+    /// This is disabled by default, but note that it is automatically
+    /// enabled (or disabled) if [`Config::prefilter`] is set. Namely, unless
+    /// `specialize_start_states` has already been set, [`Config::prefilter`]
+    /// will automatically enable or disable it based on whether a prefilter
+    /// is present or not, respectively. This is done because a prefilter's
+    /// effectiveness is rooted in being executed whenever the DFA is in a
+    /// start state, and that's only possible to do when they are specialized.
+    ///
+    /// Note that it is plausibly reasonable to _disable_ this option
+    /// explicitly while _enabling_ a prefilter. In that case, a prefilter
+    /// will still be run at the beginning of a search, but never again. This
+    /// in theory could strike a good balance if you're in a situation where a
+    /// prefilter is likely to produce many false positive candidates.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to enable start state specialization and then
+    /// shows how to check whether a state is a start state or not.
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, MatchError, Input};
+    ///
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().specialize_start_states(true))
+    ///     .build(r"[a-z]+")?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let haystack = "123 foobar 4567".as_bytes();
+    /// let sid = dfa.start_state_forward(&mut cache, &Input::new(haystack))?;
+    /// // The ID returned by 'start_state_forward' will always be tagged as
+    /// // a start state when start state specialization is enabled.
+    /// assert!(sid.is_tagged());
+    /// assert!(sid.is_start());
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    ///
+    /// Compare the above with the default lazy DFA configuration where
+    /// start states are _not_ specialized. In this case, the start state
+    /// is not tagged and `sid.is_start()` returns false.
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::dfa::DFA, MatchError, Input};
+    ///
+    /// let dfa = DFA::new(r"[a-z]+")?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let haystack = "123 foobar 4567".as_bytes();
+    /// let sid = dfa.start_state_forward(&mut cache, &Input::new(haystack))?;
+    /// // Start states are not tagged in the default configuration!
+    /// assert!(!sid.is_tagged());
+    /// assert!(!sid.is_start());
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn specialize_start_states(mut self, yes: bool) -> Config {
+        self.specialize_start_states = Some(yes);
+        self
+    }
+
+    /// Sets the maximum amount of heap memory, in bytes, to allocate to the
+    /// cache for use during a lazy DFA search. If the lazy DFA would otherwise
+    /// use more heap memory, then, depending on other configuration knobs,
+    /// either stop the search and return an error or clear the cache and
+    /// continue the search.
+    ///
+    /// The default cache capacity is some "reasonable" number that will
+    /// accommodate most regular expressions. You may find that if you need
+    /// to build a large DFA then it may be necessary to increase the cache
+    /// capacity.
+    ///
+    /// Note that while building a lazy DFA will do a "minimum" check to ensure
+    /// the capacity is big enough, this is more or less about correctness.
+    /// If the cache is bigger than the minimum but still "too small," then the
+    /// lazy DFA could wind up spending a lot of time clearing the cache and
+    /// recomputing transitions, thus negating the performance benefits of a
+    /// lazy DFA. Thus, setting the cache capacity is mostly an experimental
+    /// endeavor. For most common patterns, however, the default should be
+    /// sufficient.
+    ///
+    /// For more details on how the lazy DFA's cache is used, see the
+    /// documentation for [`Cache`].
+    ///
+    /// # Example
+    ///
+    /// This example shows what happens if the configured cache capacity is
+    /// too small. In such cases, one can override the cache capacity to make
+    /// it bigger. Alternatively, one might want to use less memory by setting
+    /// a smaller cache capacity.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// let pattern = r"\p{L}{1000}";
+    ///
+    /// // The default cache capacity is likely too small to deal with regexes
+    /// // that are very large. Large repetitions of large Unicode character
+    /// // classes are a common way to make very large regexes.
+    /// let _ = DFA::new(pattern).unwrap_err();
+    /// // Bump up the capacity to something bigger.
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().cache_capacity(100 * (1<<20))) // 100 MB
+    ///     .build(pattern)?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let haystack = "ͰͲͶͿΆΈΉΊΌΎΏΑΒΓΔΕΖΗΘΙ".repeat(50);
+    /// let expected = Some(HalfMatch::must(0, 2000));
+    /// let got = dfa.try_search_fwd(&mut cache, &Input::new(&haystack))?;
+    /// assert_eq!(expected, got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn cache_capacity(mut self, bytes: usize) -> Config {
+        self.cache_capacity = Some(bytes);
+        self
+    }
+
+    /// Configures construction of a lazy DFA to use the minimum cache capacity
+    /// if the configured capacity is otherwise too small for the provided NFA.
+    ///
+    /// This is useful if you never want lazy DFA construction to fail because
+    /// of a capacity that is too small.
+    ///
+    /// In general, this option is typically not a good idea. In particular,
+    /// while a minimum cache capacity does permit the lazy DFA to function
+    /// where it otherwise couldn't, it's plausible that it may not function
+    /// well if it's constantly running out of room. In that case, the speed
+    /// advantages of the lazy DFA may be negated. On the other hand, the
+    /// "minimum" cache capacity computed may not be completely accurate and
+    /// could actually be bigger than what is really necessary. Therefore, it
+    /// is plausible that using the minimum cache capacity could still result
+    /// in very good performance.
+    ///
+    /// This is disabled by default.
+    ///
+    /// # Example
+    ///
+    /// This example shows what happens if the configured cache capacity is
+    /// too small. In such cases, one could override the capacity explicitly.
+    /// An alternative, demonstrated here, let's us force construction to use
+    /// the minimum cache capacity if the configured capacity is otherwise
+    /// too small.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};
+    ///
+    /// let pattern = r"\p{L}{1000}";
+    ///
+    /// // The default cache capacity is likely too small to deal with regexes
+    /// // that are very large. Large repetitions of large Unicode character
+    /// // classes are a common way to make very large regexes.
+    /// let _ = DFA::new(pattern).unwrap_err();
+    /// // Configure construction such it automatically selects the minimum
+    /// // cache capacity if it would otherwise be too small.
+    /// let dfa = DFA::builder()
+    ///     .configure(DFA::config().skip_cache_capacity_check(true))
+    ///     .build(pattern)?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// let haystack = "ͰͲͶͿΆΈΉΊΌΎΏΑΒΓΔΕΖΗΘΙ".repeat(50);
+    /// let expected = Some(HalfMatch::must(0, 2000));
+    /// let got = dfa.try_search_fwd(&mut cache, &Input::new(&haystack))?;
+    /// assert_eq!(expected, got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn skip_cache_capacity_check(mut self, yes: bool) -> Config {
+        self.skip_cache_capacity_check = Some(yes);
+        self
+    }
+
+    /// Configure a lazy DFA search to quit after a certain number of cache
+    /// clearings.
+    ///
+    /// When a minimum is set, then a lazy DFA search will *possibly* "give
+    /// up" after the minimum number of cache clearings has occurred. This is
+    /// typically useful in scenarios where callers want to detect whether the
+    /// lazy DFA search is "efficient" or not. If the cache is cleared too many
+    /// times, this is a good indicator that it is not efficient, and thus, the
+    /// caller may wish to use some other regex engine.
+    ///
+    /// Note that the number of times a cache is cleared is a property of
+    /// the cache itself. Thus, if a cache is used in a subsequent search
+    /// with a similarly configured lazy DFA, then it could cause the
+    /// search to "give up" if the cache needed to be cleared, depending
+    /// on its internal count and configured minimum. The cache clear
+    /// count can only be reset to `0` via [`DFA::reset_cache`] (or
+    /// [`Regex::reset_cache`](crate::hybrid::regex::Regex::reset_cache) if
+    /// you're using the `Regex` API).
+    ///
+    /// By default, no minimum is configured. Thus, a lazy DFA search will
+    /// never give up due to cache clearings. If you do set this option, you
+    /// might consider also setting [`Config::minimum_bytes_per_state`] in
+    /// order for the lazy DFA to take efficiency into account before giving
+    /// up.
+    ///
+    /// # Example
+    ///
+    /// This example uses a somewhat pathological configuration to demonstrate
+    /// the _possible_ behavior of cache clearing and how it might result
+    /// in a search that returns an error.
+    ///
+    /// It is important to note that the precise mechanics of how and when
+    /// a cache gets cleared is an implementation detail.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::dfa::DFA, Input, MatchError, MatchErrorKind};
+    ///
+    /// // This is a carefully chosen regex. The idea is to pick one
+    /// // that requires some decent number of states (hence the bounded
+    /// // repetition). But we specifically choose to create a class with an
+    /// // ASCII letter and a non-ASCII letter so that we can check that no new
+    /// // states are created once the cache is full. Namely, if we fill up the
+    /// // cache on a haystack of 'a's, then in order to match one 'β', a new
+    /// // state will need to be created since a 'β' is encoded with multiple
+    /// // bytes. Since there's no room for this state, the search should quit
+    /// // at the very first position.
+    /// let pattern = r"[aβ]{100}";
+    /// let dfa = DFA::builder()
+    ///     .configure(
+    ///         // Configure it so that we have the minimum cache capacity
+    ///         // possible. And that if any clearings occur, the search quits.
+    ///         DFA::config()
+    ///             .skip_cache_capacity_check(true)
+    ///             .cache_capacity(0)
+    ///             .minimum_cache_clear_count(Some(0)),
+    ///     )
+    ///     .build(pattern)?;
+    /// let mut cache = dfa.create_cache();
+    ///
+    /// // Our search will give up before reaching the end!
+    /// let haystack = "a".repeat(101).into_bytes();
+    /// let result = dfa.try_search_fwd(&mut cache, &Input::new(&haystack));
+    /// assert!(matches!(
+    ///     *result.unwrap_err().kind(),
+    ///     MatchErrorKind::GaveUp { .. },
+    /// ));
+    ///
+    /// // Now that we know the cache is full, if we search a haystack that we
+    /// // know will require creating at least one new state, it should not
+    /// // be able to make much progress.
+    /// let haystack = "β".repeat(101).into_bytes();
+    /// let result = dfa.try_search_fwd(&mut cache, &Input::new(&haystack));
+    /// assert!(matches!(
+    ///     *result.unwrap_err().kind(),
+    ///     MatchErrorKind::GaveUp { .. },
+    /// ));
+    ///
+    /// // If we reset the cache, then we should be able to create more states
+    /// // and make more progress with searching for betas.
+    /// cache.reset(&dfa);
+    /// let haystack = "β".repeat(101).into_bytes();
+    /// let result = dfa.try_search_fwd(&mut cache, &Input::new(&haystack));
+    /// assert!(matches!(
+    ///     *result.unwrap_err().kind(),
+    ///     MatchErrorKind::GaveUp { .. },
+    /// ));
+    ///
+    /// // ... switching back to ASCII still makes progress since it just needs
+    /// // to set transitions on existing states!
+    /// let haystack = "a".repeat(101).into_bytes();
+    /// let result = dfa.try_search_fwd(&mut cache, &Input::new(&haystack));
+    /// assert!(matches!(
+    ///     *result.unwrap_err().kind(),
+    ///     MatchErrorKind::GaveUp { .. },
+    /// ));
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn minimum_cache_clear_count(mut self, min: Option<usize>) -> Config {
+        self.minimum_cache_clear_count = Some(min);
+        self
+    }
+
+    /// Configure a lazy DFA search to quit only when its efficiency drops
+    /// below the given minimum.
+    ///
+    /// The efficiency of the cache is determined by the number of DFA states
+    /// compiled per byte of haystack searched. For example, if the efficiency
+    /// is 2, then it means the lazy DFA is creating a new DFA state after
+    /// searching approximately 2 bytes in a haystack. Generally speaking, 2
+    /// is quite bad and it's likely that even a slower regex engine like the
+    /// [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM) would be faster.
+    ///
+    /// This has no effect if [`Config::minimum_cache_clear_count`] is not set.
+    /// Namely, this option only kicks in when the cache has been cleared more
+    /// than the minimum number. If no minimum is set, then the cache is simply
+    /// cleared whenever it fills up and it is impossible for the lazy DFA to
+    /// quit due to ineffective use of the cache.
+    ///
+    /// In general, if one is setting [`Config::minimum_cache_clear_count`],
+    /// then one should probably also set this knob as well. The reason is
+    /// that the absolute number of times the cache is cleared is generally
+    /// not a great predictor of efficiency. For example, if a new DFA state
+    /// is created for every 1,000 bytes searched, then it wouldn't be hard
+    /// for the cache to get cleared more than `N` times and then cause the
+    /// lazy DFA to quit. But a new DFA state every 1,000 bytes is likely quite
+    /// good from a performance perspective, and it's likely that the lazy
+    /// DFA should continue searching, even if it requires clearing the cache
+    /// occasionally.
+    ///
+    /// Finally, note that if you're implementing your own lazy DFA search
+    /// routine and also want this efficiency check to work correctly, then
+    /// you'll need to use the following routines to record search progress:
+    ///
+    /// * Call [`Cache::search_start`] at the beginning of every search.
+    /// * Call [`Cache::search_update`] whenever [`DFA::next_state`] is
+    /// called.
+    /// * Call [`Cache::search_finish`] before completing a search. (It is
+    /// not strictly necessary to call this when an error is returned, as
+    /// `Cache::search_start` will automatically finish the previous search
+    /// for you. But calling it where possible before returning helps improve
+    /// the accuracy of how many bytes have actually been searched.)
+    pub fn minimum_bytes_per_state(mut self, min: Option<usize>) -> Config {
+        self.minimum_bytes_per_state = Some(min);
+        self
+    }
+
+    /// Returns the match semantics set in this configuration.
+    pub fn get_match_kind(&self) -> MatchKind {
+        self.match_kind.unwrap_or(MatchKind::LeftmostFirst)
+    }
+
+    /// Returns the prefilter set in this configuration, if one at all.
+    pub fn get_prefilter(&self) -> Option<&Prefilter> {
+        self.pre.as_ref().unwrap_or(&None).as_ref()
+    }
+
+    /// Returns whether this configuration has enabled anchored starting states
+    /// for every pattern in the DFA.
+    pub fn get_starts_for_each_pattern(&self) -> bool {
+        self.starts_for_each_pattern.unwrap_or(false)
+    }
+
+    /// Returns whether this configuration has enabled byte classes or not.
+    /// This is typically a debugging oriented option, as disabling it confers
+    /// no speed benefit.
+    pub fn get_byte_classes(&self) -> bool {
+        self.byte_classes.unwrap_or(true)
+    }
+
+    /// Returns whether this configuration has enabled heuristic Unicode word
+    /// boundary support. When enabled, it is possible for a search to return
+    /// an error.
+    pub fn get_unicode_word_boundary(&self) -> bool {
+        self.unicode_word_boundary.unwrap_or(false)
+    }
+
+    /// Returns whether this configuration will instruct the lazy DFA to enter
+    /// a quit state whenever the given byte is seen during a search. When at
+    /// least one byte has this enabled, it is possible for a search to return
+    /// an error.
+    pub fn get_quit(&self, byte: u8) -> bool {
+        self.quitset.map_or(false, |q| q.contains(byte))
+    }
+
+    /// Returns whether this configuration will instruct the lazy DFA to
+    /// "specialize" start states. When enabled, the lazy DFA will tag start
+    /// states so that search routines using the lazy DFA can detect when
+    /// it's in a start state and do some kind of optimization (like run a
+    /// prefilter).
+    pub fn get_specialize_start_states(&self) -> bool {
+        self.specialize_start_states.unwrap_or(false)
+    }
+
+    /// Returns the cache capacity set on this configuration.
+    pub fn get_cache_capacity(&self) -> usize {
+        self.cache_capacity.unwrap_or(2 * (1 << 20))
+    }
+
+    /// Returns whether the cache capacity check should be skipped.
+    pub fn get_skip_cache_capacity_check(&self) -> bool {
+        self.skip_cache_capacity_check.unwrap_or(false)
+    }
+
+    /// Returns, if set, the minimum number of times the cache must be cleared
+    /// before a lazy DFA search can give up. When no minimum is set, then a
+    /// search will never quit and will always clear the cache whenever it
+    /// fills up.
+    pub fn get_minimum_cache_clear_count(&self) -> Option<usize> {
+        self.minimum_cache_clear_count.unwrap_or(None)
+    }
+
+    /// Returns, if set, the minimum number of bytes per state that need to be
+    /// processed in order for the lazy DFA to keep going. If the minimum falls
+    /// below this number (and the cache has been cleared a minimum number of
+    /// times), then the lazy DFA will return a "gave up" error.
+    pub fn get_minimum_bytes_per_state(&self) -> Option<usize> {
+        self.minimum_bytes_per_state.unwrap_or(None)
+    }
+
+    /// Returns the minimum lazy DFA cache capacity required for the given NFA.
+    ///
+    /// The cache capacity required for a particular NFA may change without
+    /// notice. Callers should not rely on it being stable.
+    ///
+    /// This is useful for informational purposes, but can also be useful for
+    /// other reasons. For example, if one wants to check the minimum cache
+    /// capacity themselves or if one wants to set the capacity based on the
+    /// minimum.
+    ///
+    /// This may return an error if this configuration does not support all of
+    /// the instructions used in the given NFA. For example, if the NFA has a
+    /// Unicode word boundary but this configuration does not enable heuristic
+    /// support for Unicode word boundaries.
+    pub fn get_minimum_cache_capacity(
+        &self,
+        nfa: &thompson::NFA,
+    ) -> Result<usize, BuildError> {
+        let quitset = self.quit_set_from_nfa(nfa)?;
+        let classes = self.byte_classes_from_nfa(nfa, &quitset);
+        let starts = self.get_starts_for_each_pattern();
+        Ok(minimum_cache_capacity(nfa, &classes, starts))
+    }
+
+    /// Returns the byte class map used during search from the given NFA.
+    ///
+    /// If byte classes are disabled on this configuration, then a map is
+    /// returned that puts each byte in its own equivalent class.
+    fn byte_classes_from_nfa(
+        &self,
+        nfa: &thompson::NFA,
+        quit: &ByteSet,
+    ) -> ByteClasses {
+        if !self.get_byte_classes() {
+            // The lazy DFA will always use the equivalence class map, but
+            // enabling this option is useful for debugging. Namely, this will
+            // cause all transitions to be defined over their actual bytes
+            // instead of an opaque equivalence class identifier. The former is
+            // much easier to grok as a human.
+            ByteClasses::singletons()
+        } else {
+            let mut set = nfa.byte_class_set().clone();
+            // It is important to distinguish any "quit" bytes from all other
+            // bytes. Otherwise, a non-quit byte may end up in the same class
+            // as a quit byte, and thus cause the DFA stop when it shouldn't.
+            //
+            // Test case:
+            //
+            //   regex-cli find match hybrid --unicode-word-boundary \
+            //     -p '^#' -p '\b10\.55\.182\.100\b' -y @conn.json.1000x.log
+            if !quit.is_empty() {
+                set.add_set(&quit);
+            }
+            set.byte_classes()
+        }
+    }
+
+    /// Return the quit set for this configuration and the given NFA.
+    ///
+    /// This may return an error if the NFA is incompatible with this
+    /// configuration's quit set. For example, if the NFA has a Unicode word
+    /// boundary and the quit set doesn't include non-ASCII bytes.
+    fn quit_set_from_nfa(
+        &self,
+        nfa: &thompson::NFA,
+    ) -> Result<ByteSet, BuildError> {
+        let mut quit = self.quitset.unwrap_or(ByteSet::empty());
+        if nfa.look_set_any().contains_word_unicode() {
+            if self.get_unicode_word_boundary() {
+                for b in 0x80..=0xFF {
+                    quit.add(b);
+                }
+            } else {
+                // If heuristic support for Unicode word boundaries wasn't
+                // enabled, then we can still check if our quit set is correct.
+                // If the caller set their quit bytes in a way that causes the
+                // DFA to quit on at least all non-ASCII bytes, then that's all
+                // we need for heuristic support to work.
+                if !quit.contains_range(0x80, 0xFF) {
+                    return Err(
+                        BuildError::unsupported_dfa_word_boundary_unicode(),
+                    );
+                }
+            }
+        }
+        Ok(quit)
+    }
+
+    /// Overwrite the default configuration such that the options in `o` are
+    /// always used. If an option in `o` is not set, then the corresponding
+    /// option in `self` is used. If it's not set in `self` either, then it
+    /// remains not set.
+    fn overwrite(&self, o: Config) -> Config {
+        Config {
+            match_kind: o.match_kind.or(self.match_kind),
+            pre: o.pre.or_else(|| self.pre.clone()),
+            starts_for_each_pattern: o
+                .starts_for_each_pattern
+                .or(self.starts_for_each_pattern),
+            byte_classes: o.byte_classes.or(self.byte_classes),
+            unicode_word_boundary: o
+                .unicode_word_boundary
+                .or(self.unicode_word_boundary),
+            quitset: o.quitset.or(self.quitset),
+            specialize_start_states: o
+                .specialize_start_states
+                .or(self.specialize_start_states),
+            cache_capacity: o.cache_capacity.or(self.cache_capacity),
+            skip_cache_capacity_check: o
+                .skip_cache_capacity_check
+                .or(self.skip_cache_capacity_check),
+            minimum_cache_clear_count: o
+                .minimum_cache_clear_count
+                .or(self.minimum_cache_clear_count),
+            minimum_bytes_per_state: o
+                .minimum_bytes_per_state
+                .or(self.minimum_bytes_per_state),
+        }
+    }
+}
+
+/// A builder for constructing a lazy deterministic finite automaton from
+/// regular expressions.
+///
+/// As a convenience, [`DFA::builder`] is an alias for [`Builder::new`]. The
+/// advantage of the former is that it often lets you avoid importing the
+/// `Builder` type directly.
+///
+/// This builder provides two main things:
+///
+/// 1. It provides a few different `build` routines for actually constructing
+/// a DFA from different kinds of inputs. The most convenient is
+/// [`Builder::build`], which builds a DFA directly from a pattern string. The
+/// most flexible is [`Builder::build_from_nfa`], which builds a DFA straight
+/// from an NFA.
+/// 2. The builder permits configuring a number of things.
+/// [`Builder::configure`] is used with [`Config`] to configure aspects of
+/// the DFA and the construction process itself. [`Builder::syntax`] and
+/// [`Builder::thompson`] permit configuring the regex parser and Thompson NFA
+/// construction, respectively. The syntax and thompson configurations only
+/// apply when building from a pattern string.
+///
+/// This builder always constructs a *single* lazy DFA. As such, this builder
+/// can only be used to construct regexes that either detect the presence
+/// of a match or find the end location of a match. A single DFA cannot
+/// produce both the start and end of a match. For that information, use a
+/// [`Regex`](crate::hybrid::regex::Regex), which can be similarly configured
+/// using [`regex::Builder`](crate::hybrid::regex::Builder). The main reason
+/// to use a DFA directly is if the end location of a match is enough for your
+/// use case. Namely, a `Regex` will construct two lazy DFAs instead of one,
+/// since a second reverse DFA is needed to find the start of a match.
+///
+/// # Example
+///
+/// This example shows how to build a lazy DFA that uses a tiny cache capacity
+/// and completely disables Unicode. That is:
+///
+/// * Things such as `\w`, `.` and `\b` are no longer Unicode-aware. `\w`
+///   and `\b` are ASCII-only while `.` matches any byte except for `\n`
+///   (instead of any UTF-8 encoding of a Unicode scalar value except for
+///   `\n`). Things that are Unicode only, such as `\pL`, are not allowed.
+/// * The pattern itself is permitted to match invalid UTF-8. For example,
+///   things like `[^a]` that match any byte except for `a` are permitted.
+///
+/// ```
+/// use regex_automata::{
+///     hybrid::dfa::DFA,
+///     nfa::thompson,
+///     util::syntax,
+///     HalfMatch, Input,
+/// };
+///
+/// let dfa = DFA::builder()
+///     .configure(DFA::config().cache_capacity(5_000))
+///     .thompson(thompson::Config::new().utf8(false))
+///     .syntax(syntax::Config::new().unicode(false).utf8(false))
+///     .build(r"foo[^b]ar.*")?;
+/// let mut cache = dfa.create_cache();
+///
+/// let haystack = b"\xFEfoo\xFFar\xE2\x98\xFF\n";
+/// let expected = Some(HalfMatch::must(0, 10));
+/// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack))?;
+/// assert_eq!(expected, got);
+///
+/// # Ok::<(), Box<dyn std::error::Error>>(())
+/// ```
+#[derive(Clone, Debug)]
+pub struct Builder {
+    config: Config,
+    #[cfg(feature = "syntax")]
+    thompson: thompson::Compiler,
+}
+
+impl Builder {
+    /// Create a new lazy DFA builder with the default configuration.
+    pub fn new() -> Builder {
+        Builder {
+            config: Config::default(),
+            #[cfg(feature = "syntax")]
+            thompson: thompson::Compiler::new(),
+        }
+    }
+
+    /// Build a lazy DFA from the given pattern.
+    ///
+    /// If there was a problem parsing or compiling the pattern, then an error
+    /// is returned.
+    #[cfg(feature = "syntax")]
+    pub fn build(&self, pattern: &str) -> Result<DFA, BuildError> {
+        self.build_many(&[pattern])
+    }
+
+    /// Build a lazy DFA from the given patterns.
+    ///
+    /// When matches are returned, the pattern ID corresponds to the index of
+    /// the pattern in the slice given.
+    #[cfg(feature = "syntax")]
+    pub fn build_many<P: AsRef<str>>(
+        &self,
+        patterns: &[P],
+    ) -> Result<DFA, BuildError> {
+        let nfa = self
+            .thompson
+            .clone()
+            // We can always forcefully disable captures because DFAs do not
+            // support them.
+            .configure(
+                thompson::Config::new()
+                    .which_captures(thompson::WhichCaptures::None),
+            )
+            .build_many(patterns)
+            .map_err(BuildError::nfa)?;
+        self.build_from_nfa(nfa)
+    }
+
+    /// Build a DFA from the given NFA.
+    ///
+    /// Note that this requires owning a `thompson::NFA`. While this may force
+    /// you to clone the NFA, such a clone is not a deep clone. Namely, NFAs
+    /// are defined internally to support shared ownership such that cloning is
+    /// very cheap.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to build a lazy DFA if you already have an NFA
+    /// in hand.
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::dfa::DFA,
+    ///     nfa::thompson,
+    ///     HalfMatch, Input,
+    /// };
+    ///
+    /// let haystack = "foo123bar";
+    ///
+    /// // This shows how to set non-default options for building an NFA.
+    /// let nfa = thompson::Compiler::new()
+    ///     .configure(thompson::Config::new().shrink(true))
+    ///     .build(r"[0-9]+")?;
+    /// let dfa = DFA::builder().build_from_nfa(nfa)?;
+    /// let mut cache = dfa.create_cache();
+    /// let expected = Some(HalfMatch::must(0, 6));
+    /// let got = dfa.try_search_fwd(&mut cache, &Input::new(haystack))?;
+    /// assert_eq!(expected, got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn build_from_nfa(
+        &self,
+        nfa: thompson::NFA,
+    ) -> Result<DFA, BuildError> {
+        let quitset = self.config.quit_set_from_nfa(&nfa)?;
+        let classes = self.config.byte_classes_from_nfa(&nfa, &quitset);
+        // Check that we can fit at least a few states into our cache,
+        // otherwise it's pretty senseless to use the lazy DFA. This does have
+        // a possible failure mode though. This assumes the maximum size of a
+        // state in powerset space (so, the total number of NFA states), which
+        // may never actually materialize, and could be quite a bit larger
+        // than the actual biggest state. If this turns out to be a problem,
+        // we could expose a knob that disables this check. But if so, we have
+        // to be careful not to panic in other areas of the code (the cache
+        // clearing and init code) that tend to assume some minimum useful
+        // cache capacity.
+        let min_cache = minimum_cache_capacity(
+            &nfa,
+            &classes,
+            self.config.get_starts_for_each_pattern(),
+        );
+        let mut cache_capacity = self.config.get_cache_capacity();
+        if cache_capacity < min_cache {
+            // When the caller has asked us to skip the cache capacity check,
+            // then we simply force the cache capacity to its minimum amount
+            // and mush on.
+            if self.config.get_skip_cache_capacity_check() {
+                debug!(
+                    "given capacity ({}) is too small, \
+                     since skip_cache_capacity_check is enabled, \
+                     setting cache capacity to minimum ({})",
+                    cache_capacity, min_cache,
+                );
+                cache_capacity = min_cache;
+            } else {
+                return Err(BuildError::insufficient_cache_capacity(
+                    min_cache,
+                    cache_capacity,
+                ));
+            }
+        }
+        // We also need to check that we can fit at least some small number
+        // of states in our state ID space. This is unlikely to trigger in
+        // >=32-bit systems, but 16-bit systems have a pretty small state ID
+        // space since a number of bits are used up as sentinels.
+        if let Err(err) = minimum_lazy_state_id(&classes) {
+            return Err(BuildError::insufficient_state_id_capacity(err));
+        }
+        let stride2 = classes.stride2();
+        let start_map = StartByteMap::new(nfa.look_matcher());
+        Ok(DFA {
+            config: self.config.clone(),
+            nfa,
+            stride2,
+            start_map,
+            classes,
+            quitset,
+            cache_capacity,
+        })
+    }
+
+    /// Apply the given lazy DFA configuration options to this builder.
+    pub fn configure(&mut self, config: Config) -> &mut Builder {
+        self.config = self.config.overwrite(config);
+        self
+    }
+
+    /// Set the syntax configuration for this builder using
+    /// [`syntax::Config`](crate::util::syntax::Config).
+    ///
+    /// This permits setting things like case insensitivity, Unicode and multi
+    /// line mode.
+    ///
+    /// These settings only apply when constructing a lazy DFA directly from a
+    /// pattern.
+    #[cfg(feature = "syntax")]
+    pub fn syntax(
+        &mut self,
+        config: crate::util::syntax::Config,
+    ) -> &mut Builder {
+        self.thompson.syntax(config);
+        self
+    }
+
+    /// Set the Thompson NFA configuration for this builder using
+    /// [`nfa::thompson::Config`](crate::nfa::thompson::Config).
+    ///
+    /// This permits setting things like whether the DFA should match the regex
+    /// in reverse or if additional time should be spent shrinking the size of
+    /// the NFA.
+    ///
+    /// These settings only apply when constructing a DFA directly from a
+    /// pattern.
+    #[cfg(feature = "syntax")]
+    pub fn thompson(&mut self, config: thompson::Config) -> &mut Builder {
+        self.thompson.configure(config);
+        self
+    }
+}
+
+/// 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 little 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, and also ask whether a match has been found.
+///
+/// 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 match reported by the most recent overlapping search to use this
+    /// state.
+    ///
+    /// If a search does not find any matches, then it is expected to clear
+    /// this value.
+    pub(crate) mat: Option<HalfMatch>,
+    /// 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.
+    pub(crate) id: Option<LazyStateID>,
+    /// The position of the search.
+    ///
+    /// When `id` is None (i.e., we are starting a search), this is set to
+    /// the beginning of the search as given by the caller regardless of its
+    /// current value. Subsequent calls to an overlapping search pick up at
+    /// this offset.
+    pub(crate) at: usize,
+    /// The index into the matching patterns of the next match to report if the
+    /// current state is a match state. Note that this may be 1 greater than
+    /// the total number of matches to report for the current match state. (In
+    /// which case, no more matches should be reported at the current position
+    /// and the search should advance to the next position.)
+    pub(crate) next_match_index: Option<usize>,
+    /// This is set to true when a reverse overlapping search has entered its
+    /// EOI transitions.
+    ///
+    /// This isn't used in a forward search because it knows to stop once the
+    /// position exceeds the end of the search range. In a reverse search,
+    /// since we use unsigned offsets, we don't "know" once we've gone past
+    /// `0`. So the only way to detect it is with this extra flag. The reverse
+    /// overlapping search knows to terminate specifically after it has
+    /// reported all matches after following the EOI transition.
+    pub(crate) rev_eoi: bool,
+}
+
+impl OverlappingState {
+    /// Create a new overlapping state that begins at the start state of any
+    /// automaton.
+    pub fn start() -> OverlappingState {
+        OverlappingState {
+            mat: None,
+            id: None,
+            at: 0,
+            next_match_index: None,
+            rev_eoi: false,
+        }
+    }
+
+    /// Return the match result of the most recent search to execute with this
+    /// state.
+    ///
+    /// A searches will clear this result automatically, such that if no
+    /// match is found, this will correctly report `None`.
+    pub fn get_match(&self) -> Option<HalfMatch> {
+        self.mat
+    }
+}
+
+/// Runs the given overlapping `search` function (forwards or backwards) until
+/// a match is found whose offset does not split a codepoint.
+///
+/// This is *not* always correct to call. It should only be called when the
+/// underlying NFA has UTF-8 mode enabled *and* it can produce zero-width
+/// matches. Calling this when both of those things aren't true might result
+/// in legitimate matches getting skipped.
+#[cold]
+#[inline(never)]
+fn skip_empty_utf8_splits_overlapping<F>(
+    input: &Input<'_>,
+    state: &mut OverlappingState,
+    mut search: F,
+) -> Result<(), MatchError>
+where
+    F: FnMut(&Input<'_>, &mut OverlappingState) -> Result<(), MatchError>,
+{
+    // Note that this routine works for forwards and reverse searches
+    // even though there's no code here to handle those cases. That's
+    // because overlapping searches drive themselves to completion via
+    // `OverlappingState`. So all we have to do is push it until no matches are
+    // found.
+
+    let mut hm = match state.get_match() {
+        None => return Ok(()),
+        Some(hm) => hm,
+    };
+    if input.get_anchored().is_anchored() {
+        if !input.is_char_boundary(hm.offset()) {
+            state.mat = None;
+        }
+        return Ok(());
+    }
+    while !input.is_char_boundary(hm.offset()) {
+        search(input, state)?;
+        hm = match state.get_match() {
+            None => return Ok(()),
+            Some(hm) => hm,
+        };
+    }
+    Ok(())
+}
+
+/// Based on the minimum number of states required for a useful lazy DFA cache,
+/// this returns the minimum lazy state ID that must be representable.
+///
+/// It's not likely for this to have any impact 32-bit systems (or higher), but
+/// on 16-bit systems, the lazy state ID space is quite constrained and thus
+/// may be insufficient if our MIN_STATES value is (for some reason) too high.
+fn minimum_lazy_state_id(
+    classes: &ByteClasses,
+) -> Result<LazyStateID, LazyStateIDError> {
+    let stride = 1 << classes.stride2();
+    let min_state_index = MIN_STATES.checked_sub(1).unwrap();
+    LazyStateID::new(min_state_index * stride)
+}
+
+/// Based on the minimum number of states required for a useful lazy DFA cache,
+/// this returns a heuristic minimum number of bytes of heap space required.
+///
+/// This is a "heuristic" because the minimum it returns is likely bigger than
+/// the true minimum. Namely, it assumes that each powerset NFA/DFA state uses
+/// the maximum number of NFA states (all of them). This is likely bigger
+/// than what is required in practice. Computing the true minimum effectively
+/// requires determinization, which is probably too much work to do for a
+/// simple check like this.
+///
+/// One of the issues with this approach IMO is that it requires that this
+/// be in sync with the calculation above for computing how much heap memory
+/// the DFA cache uses. If we get it wrong, it's possible for example for the
+/// minimum to be smaller than the computed heap memory, and thus, it may be
+/// the case that we can't add the required minimum number of states. That in
+/// turn will make lazy DFA panic because we assume that we can add at least a
+/// minimum number of states.
+///
+/// Another approach would be to always allow the minimum number of states to
+/// be added to the lazy DFA cache, even if it exceeds the configured cache
+/// limit. This does mean that the limit isn't really a limit in all cases,
+/// which is unfortunate. But it does at least guarantee that the lazy DFA can
+/// always make progress, even if it is slow. (This approach is very similar to
+/// enabling the 'skip_cache_capacity_check' config knob, except it wouldn't
+/// rely on cache size calculation. Instead, it would just always permit a
+/// minimum number of states to be added.)
+fn minimum_cache_capacity(
+    nfa: &thompson::NFA,
+    classes: &ByteClasses,
+    starts_for_each_pattern: bool,
+) -> usize {
+    const ID_SIZE: usize = size_of::<LazyStateID>();
+    const STATE_SIZE: usize = size_of::<State>();
+
+    let stride = 1 << classes.stride2();
+    let states_len = nfa.states().len();
+    let sparses = 2 * states_len * NFAStateID::SIZE;
+    let trans = MIN_STATES * stride * ID_SIZE;
+
+    let mut starts = Start::len() * ID_SIZE;
+    if starts_for_each_pattern {
+        starts += (Start::len() * nfa.pattern_len()) * ID_SIZE;
+    }
+
+    // The min number of states HAS to be at least 4: we have 3 sentinel states
+    // and then we need space for one more when we save a state after clearing
+    // the cache. We also need space for one more, otherwise we get stuck in a
+    // loop where we try to add a 5th state, which gets rejected, which clears
+    // the cache, which adds back a saved state (4th total state) which then
+    // tries to add the 5th state again.
+    assert!(MIN_STATES >= 5, "minimum number of states has to be at least 5");
+    // The minimum number of non-sentinel states. We consider this separately
+    // because sentinel states are much smaller in that they contain no NFA
+    // states. Given our aggressive calculation here, it's worth being more
+    // precise with the number of states we need.
+    let non_sentinel = MIN_STATES.checked_sub(SENTINEL_STATES).unwrap();
+
+    // Every `State` has 5 bytes for flags, 4 bytes (max) for the number of
+    // patterns, followed by 32-bit encodings of patterns and then delta
+    // varint encodings of NFA state IDs. We use the worst case (which isn't
+    // technically possible) of 5 bytes for each NFA state ID.
+    //
+    // HOWEVER, three of the states needed by a lazy DFA are just the sentinel
+    // unknown, dead and quit states. Those states have a known size and it is
+    // small.
+    let dead_state_size = State::dead().memory_usage();
+    let max_state_size = 5 + 4 + (nfa.pattern_len() * 4) + (states_len * 5);
+    let states = (SENTINEL_STATES * (STATE_SIZE + dead_state_size))
+        + (non_sentinel * (STATE_SIZE + max_state_size));
+    // NOTE: We don't double count heap memory used by State for this map since
+    // we use reference counting to avoid doubling memory usage. (This tends to
+    // be where most memory is allocated in the cache.)
+    let states_to_sid = (MIN_STATES * STATE_SIZE) + (MIN_STATES * ID_SIZE);
+    let stack = states_len * NFAStateID::SIZE;
+    let scratch_state_builder = max_state_size;
+
+    trans
+        + starts
+        + states
+        + states_to_sid
+        + sparses
+        + stack
+        + scratch_state_builder
+}
+
+#[cfg(all(test, feature = "syntax"))]
+mod tests {
+    use super::*;
+
+    // Tests that we handle heuristic Unicode word boundary support in reverse
+    // DFAs in the specific case of contextual searches.
+    //
+    // I wrote this test when I discovered a bug in how heuristic word
+    // boundaries were handled. Namely, that the starting state selection
+    // didn't consider the DFA's quit byte set when looking at the byte
+    // immediately before the start of the search (or immediately after the
+    // end of the search in the case of a reverse search). As a result, it was
+    // possible for '\bfoo\b' to match 'β123' because the trailing \xB2 byte
+    // in the 'β' codepoint would be treated as a non-word character. But of
+    // course, this search should trigger the DFA to quit, since there is a
+    // non-ASCII byte in consideration.
+    //
+    // Thus, I fixed 'start_state_{forward,reverse}' to check the quit byte set
+    // if it wasn't empty. The forward case is tested in the doc test for the
+    // Config::unicode_word_boundary API. We test the reverse case here, which
+    // is sufficiently niche that it doesn't really belong in a doc test.
+    #[test]
+    fn heuristic_unicode_reverse() {
+        let dfa = DFA::builder()
+            .configure(DFA::config().unicode_word_boundary(true))
+            .thompson(thompson::Config::new().reverse(true))
+            .build(r"\b[0-9]+\b")
+            .unwrap();
+        let mut cache = dfa.create_cache();
+
+        let input = Input::new("β123").range(2..);
+        let expected = MatchError::quit(0xB2, 1);
+        let got = dfa.try_search_rev(&mut cache, &input);
+        assert_eq!(Err(expected), got);
+
+        let input = Input::new("123β").range(..3);
+        let expected = MatchError::quit(0xCE, 3);
+        let got = dfa.try_search_rev(&mut cache, &input);
+        assert_eq!(Err(expected), got);
+    }
+}
diff --git a/vendor/regex-automata/src/hybrid/error.rs b/vendor/regex-automata/src/hybrid/error.rs
new file mode 100644
index 0000000..d134e7e
--- /dev/null
+++ b/vendor/regex-automata/src/hybrid/error.rs
@@ -0,0 +1,242 @@
+use crate::{hybrid::id::LazyStateIDError, nfa, util::search::Anchored};
+
+/// An error that occurs when initial construction of a lazy DFA fails.
+///
+/// A build error can occur when insufficient cache capacity is configured or
+/// if something about the NFA is unsupported. (For example, if one attempts
+/// to build a lazy DFA without heuristic Unicode support but with an NFA that
+/// contains a Unicode word boundary.)
+///
+/// This error does not provide many introspection capabilities. There are
+/// generally only two things you can do with it:
+///
+/// * Obtain a human readable message via its `std::fmt::Display` impl.
+/// * Access an underlying
+/// [`nfa::thompson::BuildError`](crate::nfa::thompson::BuildError)
+/// type from its `source` method via the `std::error::Error` trait. This error
+/// only occurs when using convenience routines for building a lazy DFA
+/// directly from a pattern string.
+///
+/// When the `std` feature is enabled, this implements the `std::error::Error`
+/// trait.
+#[derive(Clone, Debug)]
+pub struct BuildError {
+    kind: BuildErrorKind,
+}
+
+#[derive(Clone, Debug)]
+enum BuildErrorKind {
+    NFA(nfa::thompson::BuildError),
+    InsufficientCacheCapacity { minimum: usize, given: usize },
+    InsufficientStateIDCapacity { err: LazyStateIDError },
+    Unsupported(&'static str),
+}
+
+impl BuildError {
+    pub(crate) fn nfa(err: nfa::thompson::BuildError) -> BuildError {
+        BuildError { kind: BuildErrorKind::NFA(err) }
+    }
+
+    pub(crate) fn insufficient_cache_capacity(
+        minimum: usize,
+        given: usize,
+    ) -> BuildError {
+        BuildError {
+            kind: BuildErrorKind::InsufficientCacheCapacity { minimum, given },
+        }
+    }
+
+    pub(crate) fn insufficient_state_id_capacity(
+        err: LazyStateIDError,
+    ) -> BuildError {
+        BuildError {
+            kind: BuildErrorKind::InsufficientStateIDCapacity { err },
+        }
+    }
+
+    pub(crate) fn unsupported_dfa_word_boundary_unicode() -> BuildError {
+        let msg = "cannot build lazy DFAs for regexes with Unicode word \
+                   boundaries; switch to ASCII word boundaries, or \
+                   heuristically enable Unicode word boundaries or use a \
+                   different regex engine";
+        BuildError { kind: BuildErrorKind::Unsupported(msg) }
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for BuildError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
+        match self.kind {
+            BuildErrorKind::NFA(ref err) => Some(err),
+            _ => None,
+        }
+    }
+}
+
+impl core::fmt::Display for BuildError {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        match self.kind {
+            BuildErrorKind::NFA(_) => write!(f, "error building NFA"),
+            BuildErrorKind::InsufficientCacheCapacity { minimum, given } => {
+                write!(
+                    f,
+                    "given cache capacity ({}) is smaller than \
+                     minimum required ({})",
+                    given, minimum,
+                )
+            }
+            BuildErrorKind::InsufficientStateIDCapacity { ref err } => {
+                err.fmt(f)
+            }
+            BuildErrorKind::Unsupported(ref msg) => {
+                write!(f, "unsupported regex feature for DFAs: {}", msg)
+            }
+        }
+    }
+}
+
+/// An error that can occur when computing the start state for a search.
+///
+/// Computing a start state can fail for a few reasons, either
+/// based on incorrect configuration or even based on whether
+/// the look-behind byte triggers a quit state. Typically
+/// one does not need to handle this error if you're using
+/// [`DFA::start_state_forward`](crate::hybrid::dfa::DFA::start_state_forward)
+/// (or its reverse counterpart), as that routine automatically converts
+/// `StartError` to a [`MatchError`](crate::MatchError) for you.
+///
+/// This error may be returned by the
+/// [`DFA::start_state`](crate::hybrid::dfa::DFA::start_state) routine.
+///
+/// This error implements the `std::error::Error` trait when the `std` feature
+/// is enabled.
+///
+/// This error is marked as non-exhaustive. New variants may be added in a
+/// semver compatible release.
+#[non_exhaustive]
+#[derive(Clone, Debug)]
+pub enum StartError {
+    /// An error that occurs when cache inefficiency has dropped below the
+    /// configured heuristic thresholds.
+    Cache {
+        /// The underlying cache error that occurred.
+        err: CacheError,
+    },
+    /// An error that occurs when a starting configuration's look-behind byte
+    /// is in this DFA's quit set.
+    Quit {
+        /// The quit byte that was found.
+        byte: u8,
+    },
+    /// An error that occurs when the caller requests an anchored mode that
+    /// isn't supported by the DFA.
+    UnsupportedAnchored {
+        /// The anchored mode given that is unsupported.
+        mode: Anchored,
+    },
+}
+
+impl StartError {
+    pub(crate) fn cache(err: CacheError) -> StartError {
+        StartError::Cache { err }
+    }
+
+    pub(crate) fn quit(byte: u8) -> StartError {
+        StartError::Quit { byte }
+    }
+
+    pub(crate) fn unsupported_anchored(mode: Anchored) -> StartError {
+        StartError::UnsupportedAnchored { mode }
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for StartError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
+        match *self {
+            StartError::Cache { ref err } => Some(err),
+            _ => None,
+        }
+    }
+}
+
+impl core::fmt::Display for StartError {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        match *self {
+            StartError::Cache { .. } => write!(
+                f,
+                "error computing start state because of cache inefficiency"
+            ),
+            StartError::Quit { byte } => write!(
+                f,
+                "error computing start state because the look-behind byte \
+                 {:?} triggered a quit state",
+                crate::util::escape::DebugByte(byte),
+            ),
+            StartError::UnsupportedAnchored { mode: Anchored::Yes } => {
+                write!(
+                    f,
+                    "error computing start state because \
+                     anchored searches are not supported or enabled"
+                )
+            }
+            StartError::UnsupportedAnchored { mode: Anchored::No } => {
+                write!(
+                    f,
+                    "error computing start state because \
+                     unanchored searches are not supported or enabled"
+                )
+            }
+            StartError::UnsupportedAnchored {
+                mode: Anchored::Pattern(pid),
+            } => {
+                write!(
+                    f,
+                    "error computing start state because \
+                     anchored searches for a specific pattern ({}) \
+                     are not supported or enabled",
+                    pid.as_usize(),
+                )
+            }
+        }
+    }
+}
+
+/// An error that occurs when cache usage has become inefficient.
+///
+/// One of the weaknesses of a lazy DFA is that it may need to clear its
+/// cache repeatedly if it's not big enough. If this happens too much, then it
+/// can slow searching down significantly. A mitigation to this is to use
+/// heuristics to detect whether the cache is being used efficiently or not.
+/// If not, then a lazy DFA can return a `CacheError`.
+///
+/// The default configuration of a lazy DFA in this crate is
+/// set such that a `CacheError` will never occur. Instead,
+/// callers must opt into this behavior with settings like
+/// [`dfa::Config::minimum_cache_clear_count`](crate::hybrid::dfa::Config::minimum_cache_clear_count)
+/// and
+/// [`dfa::Config::minimum_bytes_per_state`](crate::hybrid::dfa::Config::minimum_bytes_per_state).
+///
+/// When the `std` feature is enabled, this implements the `std::error::Error`
+/// trait.
+#[derive(Clone, Debug)]
+pub struct CacheError(());
+
+impl CacheError {
+    pub(crate) fn too_many_cache_clears() -> CacheError {
+        CacheError(())
+    }
+
+    pub(crate) fn bad_efficiency() -> CacheError {
+        CacheError(())
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for CacheError {}
+
+impl core::fmt::Display for CacheError {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        write!(f, "lazy DFA cache has been cleared too many times")
+    }
+}
diff --git a/vendor/regex-automata/src/hybrid/id.rs b/vendor/regex-automata/src/hybrid/id.rs
new file mode 100644
index 0000000..662e3c9
--- /dev/null
+++ b/vendor/regex-automata/src/hybrid/id.rs
@@ -0,0 +1,354 @@
+/// A state identifier specifically tailored for lazy DFAs.
+///
+/// A lazy state ID logically represents a pointer to a DFA state. In practice,
+/// by limiting the number of DFA states it can address, it reserves some
+/// bits of its representation to encode some additional information. That
+/// additional information is called a "tag." That tag is used to record
+/// whether the state it points to is an unknown, dead, quit, start or match
+/// state.
+///
+/// When implementing a low level search routine with a lazy DFA, it is
+/// necessary to query the type of the current state to know what to do:
+///
+/// * **Unknown** - The state has not yet been computed. The
+/// parameters used to get this state ID must be re-passed to
+/// [`DFA::next_state`](crate::hybrid::dfa::DFA::next_state), which will never
+/// return an unknown state ID.
+/// * **Dead** - A dead state only has transitions to itself. It indicates that
+/// the search cannot do anything else and should stop with whatever result it
+/// has.
+/// * **Quit** - A quit state indicates that the automaton could not answer
+/// whether a match exists or not. Correct search implementations must return a
+/// [`MatchError::quit`](crate::MatchError::quit) when a DFA enters a quit
+/// state.
+/// * **Start** - A start state is a state in which a search can begin.
+/// Lazy DFAs usually have more than one start state. Branching on
+/// this isn't required for correctness, but a common optimization is
+/// to run a prefilter when a search enters a start state. Note that
+/// start states are *not* tagged automatically, and one must enable the
+/// [`Config::specialize_start_states`](crate::hybrid::dfa::Config::specialize_start_states)
+/// setting for start states to be tagged. The reason for this is
+/// that a DFA search loop is usually written to execute a prefilter once it
+/// enters a start state. But if there is no prefilter, this handling can be
+/// quite diastrous as the DFA may ping-pong between the special handling code
+/// and a possible optimized hot path for handling untagged states. When start
+/// states aren't specialized, then they are untagged and remain in the hot
+/// path.
+/// * **Match** - A match state indicates that a match has been found.
+/// Depending on the semantics of your search implementation, it may either
+/// continue until the end of the haystack or a dead state, or it might quit
+/// and return the match immediately.
+///
+/// As an optimization, the [`is_tagged`](LazyStateID::is_tagged) predicate
+/// can be used to determine if a tag exists at all. This is useful to avoid
+/// branching on all of the above types for every byte searched.
+///
+/// # Example
+///
+/// This example shows how `LazyStateID` 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.
+///
+/// Notice also how a correct search implementation deals with
+/// [`CacheError`](crate::hybrid::CacheError)s returned by some of
+/// the lazy DFA routines. When a `CacheError` occurs, it returns
+/// [`MatchError::gave_up`](crate::MatchError::gave_up).
+///
+/// ```
+/// use regex_automata::{
+///     hybrid::dfa::{Cache, DFA},
+///     HalfMatch, MatchError, Input,
+/// };
+///
+/// fn find_leftmost_first(
+///     dfa: &DFA,
+///     cache: &mut Cache,
+///     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 sid = dfa.start_state_forward(
+///         cache,
+///         &Input::new(haystack),
+///     )?;
+///     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() {
+///         sid = dfa
+///             .next_state(cache, sid, b)
+///             .map_err(|_| MatchError::gave_up(i))?;
+///         if sid.is_tagged() {
+///             if sid.is_match() {
+///                 last_match = Some(HalfMatch::new(
+///                     dfa.match_pattern(cache, sid, 0),
+///                     i,
+///                 ));
+///             } else if sid.is_dead() {
+///                 return Ok(last_match);
+///             } else if sid.is_quit() {
+///                 // 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(b, i));
+///             }
+///             // Implementors may also want to check for start states and
+///             // handle them differently for performance reasons. But it is
+///             // not necessary for correctness. Note that in order to check
+///             // for start states, you'll need to enable the
+///             // 'specialize_start_states' config knob, otherwise start
+///             // states will not be tagged.
+///         }
+///     }
+///     // Matches are always delayed by 1 byte, so we must explicitly walk
+///     // the special "EOI" transition at the end of the search.
+///     sid = dfa
+///         .next_eoi_state(cache, sid)
+///         .map_err(|_| MatchError::gave_up(haystack.len()))?;
+///     if sid.is_match() {
+///         last_match = Some(HalfMatch::new(
+///             dfa.match_pattern(cache, sid, 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 = DFA::new(r"[a-z]+")?;
+/// let mut cache = dfa.create_cache();
+/// let haystack = "123 foobar 4567".as_bytes();
+/// let mat = find_leftmost_first(&dfa, &mut cache, 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 = DFA::new(r"[0-9]{4}")?;
+/// let mut cache = dfa.create_cache();
+/// let haystack = "123 foobar 4567".as_bytes();
+/// let mat = find_leftmost_first(&dfa, &mut cache, 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 = DFA::new_many(&[r"[a-z]+", r"[0-9]+"])?;
+/// let mut cache = dfa.create_cache();
+/// let haystack = "123 foobar 4567".as_bytes();
+/// let mat = find_leftmost_first(&dfa, &mut cache, haystack)?.unwrap();
+/// assert_eq!(mat.pattern().as_usize(), 1);
+/// assert_eq!(mat.offset(), 3);
+/// let mat = find_leftmost_first(&dfa, &mut cache, &haystack[3..])?.unwrap();
+/// assert_eq!(mat.pattern().as_usize(), 0);
+/// assert_eq!(mat.offset(), 7);
+/// let mat = find_leftmost_first(&dfa, &mut cache, &haystack[10..])?.unwrap();
+/// assert_eq!(mat.pattern().as_usize(), 1);
+/// assert_eq!(mat.offset(), 5);
+///
+/// # Ok::<(), Box<dyn std::error::Error>>(())
+/// ```
+#[derive(
+    Clone, Copy, Debug, Default, Eq, Hash, PartialEq, PartialOrd, Ord,
+)]
+pub struct LazyStateID(u32);
+
+impl LazyStateID {
+    #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
+    const MAX_BIT: usize = 31;
+
+    #[cfg(target_pointer_width = "16")]
+    const MAX_BIT: usize = 15;
+
+    const MASK_UNKNOWN: usize = 1 << (LazyStateID::MAX_BIT);
+    const MASK_DEAD: usize = 1 << (LazyStateID::MAX_BIT - 1);
+    const MASK_QUIT: usize = 1 << (LazyStateID::MAX_BIT - 2);
+    const MASK_START: usize = 1 << (LazyStateID::MAX_BIT - 3);
+    const MASK_MATCH: usize = 1 << (LazyStateID::MAX_BIT - 4);
+    const MAX: usize = LazyStateID::MASK_MATCH - 1;
+
+    /// Create a new lazy state ID.
+    ///
+    /// If the given identifier exceeds [`LazyStateID::MAX`], then this returns
+    /// an error.
+    #[inline]
+    pub(crate) fn new(id: usize) -> Result<LazyStateID, LazyStateIDError> {
+        if id > LazyStateID::MAX {
+            let attempted = u64::try_from(id).unwrap();
+            return Err(LazyStateIDError { attempted });
+        }
+        Ok(LazyStateID::new_unchecked(id))
+    }
+
+    /// Create a new lazy state ID without checking whether the given value
+    /// exceeds [`LazyStateID::MAX`].
+    ///
+    /// While this is unchecked, providing an incorrect value must never
+    /// sacrifice memory safety.
+    #[inline]
+    const fn new_unchecked(id: usize) -> LazyStateID {
+        // FIXME: Use as_u32() once const functions in traits are stable.
+        LazyStateID(id as u32)
+    }
+
+    /// Return this lazy state ID as an untagged `usize`.
+    ///
+    /// If this lazy state ID is tagged, then the usize returned is the state
+    /// ID without the tag. If the ID was not tagged, then the usize returned
+    /// is equivalent to the state ID.
+    #[inline]
+    pub(crate) fn as_usize_untagged(&self) -> usize {
+        self.as_usize_unchecked() & LazyStateID::MAX
+    }
+
+    /// Return this lazy state ID as its raw internal `usize` value, which may
+    /// be tagged (and thus greater than LazyStateID::MAX).
+    #[inline]
+    pub(crate) const fn as_usize_unchecked(&self) -> usize {
+        // FIXME: Use as_usize() once const functions in traits are stable.
+        self.0 as usize
+    }
+
+    #[inline]
+    pub(crate) const fn to_unknown(&self) -> LazyStateID {
+        LazyStateID::new_unchecked(
+            self.as_usize_unchecked() | LazyStateID::MASK_UNKNOWN,
+        )
+    }
+
+    #[inline]
+    pub(crate) const fn to_dead(&self) -> LazyStateID {
+        LazyStateID::new_unchecked(
+            self.as_usize_unchecked() | LazyStateID::MASK_DEAD,
+        )
+    }
+
+    #[inline]
+    pub(crate) const fn to_quit(&self) -> LazyStateID {
+        LazyStateID::new_unchecked(
+            self.as_usize_unchecked() | LazyStateID::MASK_QUIT,
+        )
+    }
+
+    /// Return this lazy state ID as a state ID that is tagged as a start
+    /// state.
+    #[inline]
+    pub(crate) const fn to_start(&self) -> LazyStateID {
+        LazyStateID::new_unchecked(
+            self.as_usize_unchecked() | LazyStateID::MASK_START,
+        )
+    }
+
+    /// Return this lazy state ID as a lazy state ID that is tagged as a match
+    /// state.
+    #[inline]
+    pub(crate) const fn to_match(&self) -> LazyStateID {
+        LazyStateID::new_unchecked(
+            self.as_usize_unchecked() | LazyStateID::MASK_MATCH,
+        )
+    }
+
+    /// Return true if and only if this lazy state ID is tagged.
+    ///
+    /// When a lazy state ID is tagged, then one can conclude that it is one
+    /// of a match, start, dead, quit or unknown state.
+    #[inline]
+    pub const fn is_tagged(&self) -> bool {
+        self.as_usize_unchecked() > LazyStateID::MAX
+    }
+
+    /// Return true if and only if this represents a lazy state ID that is
+    /// "unknown." That is, the state has not yet been created. When a caller
+    /// sees this state ID, it generally means that a state has to be computed
+    /// in order to proceed.
+    #[inline]
+    pub const fn is_unknown(&self) -> bool {
+        self.as_usize_unchecked() & LazyStateID::MASK_UNKNOWN > 0
+    }
+
+    /// Return true if and only if this represents a dead state. A dead state
+    /// is a state that can never transition to any other state except the
+    /// dead state. When a dead state is seen, it generally indicates that a
+    /// search should stop.
+    #[inline]
+    pub const fn is_dead(&self) -> bool {
+        self.as_usize_unchecked() & LazyStateID::MASK_DEAD > 0
+    }
+
+    /// Return true if and only if this represents a quit state. A quit state
+    /// is a state that is representationally equivalent to a dead state,
+    /// except it indicates the automaton has reached a point at which it can
+    /// no longer determine whether a match exists or not. In general, this
+    /// indicates an error during search and the caller must either pass this
+    /// error up or use a different search technique.
+    #[inline]
+    pub const fn is_quit(&self) -> bool {
+        self.as_usize_unchecked() & LazyStateID::MASK_QUIT > 0
+    }
+
+    /// Return true if and only if this lazy state ID has been tagged as a
+    /// start state.
+    ///
+    /// Note that if
+    /// [`Config::specialize_start_states`](crate::hybrid::dfa::Config) is
+    /// disabled (which is the default), then this will always return false
+    /// since start states won't be tagged.
+    #[inline]
+    pub const fn is_start(&self) -> bool {
+        self.as_usize_unchecked() & LazyStateID::MASK_START > 0
+    }
+
+    /// Return true if and only if this lazy state ID has been tagged as a
+    /// match state.
+    #[inline]
+    pub const fn is_match(&self) -> bool {
+        self.as_usize_unchecked() & LazyStateID::MASK_MATCH > 0
+    }
+}
+
+/// This error occurs when a lazy state ID could not be constructed.
+///
+/// This occurs when given an integer exceeding the maximum lazy state ID
+/// value.
+///
+/// When the `std` feature is enabled, this implements the `Error` trait.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub(crate) struct LazyStateIDError {
+    attempted: u64,
+}
+
+impl LazyStateIDError {
+    /// Returns the value that failed to constructed a lazy state ID.
+    pub(crate) fn attempted(&self) -> u64 {
+        self.attempted
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for LazyStateIDError {}
+
+impl core::fmt::Display for LazyStateIDError {
+    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
+        write!(
+            f,
+            "failed to create LazyStateID from {:?}, which exceeds {:?}",
+            self.attempted(),
+            LazyStateID::MAX,
+        )
+    }
+}
diff --git a/vendor/regex-automata/src/hybrid/mod.rs b/vendor/regex-automata/src/hybrid/mod.rs
new file mode 100644
index 0000000..2feb839
--- /dev/null
+++ b/vendor/regex-automata/src/hybrid/mod.rs
@@ -0,0 +1,144 @@
+/*!
+A module for building and searching with lazy deterministic finite automata
+(DFAs).
+
+Like other modules in this crate, lazy DFAs support a rich regex syntax with
+Unicode features. The key feature of a lazy DFA is that it builds itself
+incrementally during search, and never uses more than a configured capacity of
+memory. Thus, when searching with a lazy DFA, one must supply a mutable "cache"
+in which the actual DFA's transition table is stored.
+
+If you're looking for fully compiled DFAs, then please see the top-level
+[`dfa` module](crate::dfa).
+
+# Overview
+
+This section gives a brief overview of the primary types in this module:
+
+* A [`regex::Regex`] provides a way to search for matches of a regular
+expression using lazy DFAs. This includes iterating over matches with both the
+start and end positions of each match.
+* A [`dfa::DFA`] provides direct low level access to a lazy DFA.
+
+# Example: basic regex searching
+
+This example shows how to compile a regex using the default configuration
+and then use it to find matches in a byte string:
+
+```
+use regex_automata::{hybrid::regex::Regex, Match};
+
+let re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}")?;
+let mut cache = re.create_cache();
+
+let haystack = "2018-12-24 2016-10-08";
+let matches: Vec<Match> = re.find_iter(&mut cache, haystack).collect();
+assert_eq!(matches, vec![
+    Match::must(0, 0..10),
+    Match::must(0, 11..21),
+]);
+# Ok::<(), Box<dyn std::error::Error>>(())
+```
+
+# Example: searching with multiple regexes
+
+The lazy DFAs in this module all fully support searching with multiple regexes
+simultaneously. You can use this support with standard leftmost-first style
+searching to find non-overlapping matches:
+
+```
+# if cfg!(miri) { return Ok(()); } // miri takes too long
+use regex_automata::{hybrid::regex::Regex, Match};
+
+let re = Regex::new_many(&[r"\w+", r"\S+"])?;
+let mut cache = re.create_cache();
+
+let haystack = "@foo bar";
+let matches: Vec<Match> = re.find_iter(&mut cache, haystack).collect();
+assert_eq!(matches, vec![
+    Match::must(1, 0..4),
+    Match::must(0, 5..8),
+]);
+# Ok::<(), Box<dyn std::error::Error>>(())
+```
+
+# When should I use this?
+
+Generally speaking, if you can abide the use of mutable state during search,
+and you don't need things like capturing groups or Unicode word boundary
+support in non-ASCII text, then a lazy DFA is likely a robust choice with
+respect to both search speed and memory usage. Note however that its speed
+may be worse than a general purpose regex engine if you don't select a good
+[prefilter](crate::util::prefilter).
+
+If you know ahead of time that your pattern would result in a very large DFA
+if it was fully compiled, it may be better to use an NFA simulation instead
+of a lazy DFA. Either that, or increase the cache capacity of your lazy DFA
+to something that is big enough to hold the state machine (likely through
+experimentation). The issue here is that if the cache is too small, then it
+could wind up being reset too frequently and this might decrease searching
+speed significantly.
+
+# Differences with fully compiled DFAs
+
+A [`hybrid::regex::Regex`](crate::hybrid::regex::Regex) and a
+[`dfa::regex::Regex`](crate::dfa::regex::Regex) both have the same capabilities
+(and similarly for their underlying DFAs), but they achieve them through
+different means. The main difference is that a hybrid or "lazy" regex builds
+its DFA lazily during search, where as a fully compiled regex will build its
+DFA at construction time. While building a DFA at search time might sound like
+it's slow, it tends to work out where most bytes seen during a search will
+reuse pre-built parts of the DFA and thus can be almost as fast as a fully
+compiled DFA. The main downside is that searching requires mutable space to
+store the DFA, and, in the worst case, a search can result in a new state being
+created for each byte seen, which would make searching quite a bit slower.
+
+A fully compiled DFA never has to worry about searches being slower once
+it's built. (Aside from, say, the transition table being so large that it
+is subject to harsh CPU cache effects.) However, of course, building a full
+DFA can be quite time consuming and memory hungry. Particularly when large
+Unicode character classes are used, which tend to translate into very large
+DFAs.
+
+A lazy DFA strikes a nice balance _in practice_, particularly in the
+presence of Unicode mode, by only building what is needed. It avoids the
+worst case exponential time complexity of DFA compilation by guaranteeing that
+it will only build at most one state per byte searched. While the worst
+case here can lead to a very high constant, it will never be exponential.
+
+# Syntax
+
+This module supports the same syntax as the `regex` crate, since they share the
+same parser. You can find an exhaustive list of supported syntax in the
+[documentation for the `regex` crate](https://docs.rs/regex/1/regex/#syntax).
+
+There are two things that are not supported by the lazy DFAs in this module:
+
+* Capturing groups. The DFAs (and [`Regex`](regex::Regex)es built on top
+of them) can only find the offsets of an entire match, but cannot resolve
+the offsets of each capturing group. This is because DFAs do not have the
+expressive power necessary. Note that it is okay to build a lazy DFA from an
+NFA that contains capture groups. The capture groups will simply be ignored.
+* Unicode word boundaries. These present particularly difficult challenges for
+DFA construction and would result in an explosion in the number of states.
+One can enable [`dfa::Config::unicode_word_boundary`] though, which provides
+heuristic support for Unicode word boundaries that only works on ASCII text.
+Otherwise, one can use `(?-u:\b)` for an ASCII word boundary, which will work
+on any input.
+
+There are no plans to lift either of these limitations.
+
+Note that these restrictions are identical to the restrictions on fully
+compiled DFAs.
+*/
+
+pub use self::{
+    error::{BuildError, CacheError, StartError},
+    id::LazyStateID,
+};
+
+pub mod dfa;
+mod error;
+mod id;
+pub mod regex;
+mod search;
diff --git a/vendor/regex-automata/src/hybrid/regex.rs b/vendor/regex-automata/src/hybrid/regex.rs
new file mode 100644
index 0000000..b3b1fe3
--- /dev/null
+++ b/vendor/regex-automata/src/hybrid/regex.rs
@@ -0,0 +1,895 @@
+/*!
+A lazy DFA backed `Regex`.
+
+This module provides a [`Regex`] backed by a lazy DFA. A `Regex` implements
+convenience routines you might have come to expect, such as finding a match
+and iterating over all non-overlapping matches. This `Regex` type is limited
+in its capabilities to what a lazy DFA can provide. Therefore, APIs involving
+capturing groups, for example, are not provided.
+
+Internally, a `Regex` is composed of two DFAs. One is a "forward" DFA that
+finds the end offset of a match, where as the other is a "reverse" DFA that
+find the start offset of a match.
+
+See the [parent module](crate::hybrid) for examples.
+*/
+
+use crate::{
+    hybrid::{
+        dfa::{self, DFA},
+        error::BuildError,
+    },
+    nfa::thompson,
+    util::{
+        iter,
+        search::{Anchored, Input, Match, MatchError, MatchKind},
+    },
+};
+
+/// A regular expression that uses hybrid NFA/DFAs (also called "lazy DFAs")
+/// for searching.
+///
+/// A regular expression is comprised of two lazy DFAs, a "forward" DFA and a
+/// "reverse" DFA. The forward DFA is responsible for detecting the end of
+/// a match while the reverse DFA is responsible for detecting the start
+/// of a match. Thus, in order to find the bounds of any given match, a
+/// forward search must first be run followed by a reverse search. A match
+/// found by the forward DFA guarantees that the reverse DFA will also find
+/// a match.
+///
+/// # Fallibility
+///
+/// Most of the search routines defined on this type will _panic_ when the
+/// underlying search fails. This might be because the DFA gave up because it
+/// saw a quit byte, whether configured explicitly or via heuristic Unicode
+/// word boundary support, although neither are enabled by default. It might
+/// also fail if the underlying DFA determines it isn't making effective use of
+/// the cache (which also never happens by default). Or it might fail because
+/// an invalid `Input` configuration is given, for example, with an unsupported
+/// [`Anchored`] mode.
+///
+/// If you need to handle these error cases instead of allowing them to trigger
+/// a panic, then the lower level [`Regex::try_search`] provides a fallible API
+/// that never panics.
+///
+/// # Example
+///
+/// This example shows how to cause a search to terminate if it sees a
+/// `\n` byte, and handle the error returned. This could be useful if, for
+/// example, you wanted to prevent a user supplied pattern from matching
+/// across a line boundary.
+///
+/// ```
+/// # if cfg!(miri) { return Ok(()); } // miri takes too long
+/// use regex_automata::{hybrid::{dfa, regex::Regex}, Input, MatchError};
+///
+/// let re = Regex::builder()
+///     .dfa(dfa::Config::new().quit(b'\n', true))
+///     .build(r"foo\p{any}+bar")?;
+/// let mut cache = re.create_cache();
+///
+/// let input = Input::new("foo\nbar");
+/// // Normally this would produce a match, since \p{any} contains '\n'.
+/// // But since we instructed the automaton to enter a quit state if a
+/// // '\n' is observed, this produces a match error instead.
+/// let expected = MatchError::quit(b'\n', 3);
+/// let got = re.try_search(&mut cache, &input).unwrap_err();
+/// assert_eq!(expected, got);
+///
+/// # Ok::<(), Box<dyn std::error::Error>>(())
+/// ```
+#[derive(Debug)]
+pub struct Regex {
+    /// The forward lazy DFA. This can only find the end of a match.
+    forward: DFA,
+    /// The reverse lazy DFA. This can only find the start of a match.
+    ///
+    /// This is built with 'all' match semantics (instead of leftmost-first)
+    /// so that it always finds the longest possible match (which corresponds
+    /// to the leftmost starting position). It is also compiled as an anchored
+    /// matcher and has 'starts_for_each_pattern' enabled. Including starting
+    /// states for each pattern is necessary to ensure that we only look for
+    /// matches of a pattern that matched in the forward direction. Otherwise,
+    /// we might wind up finding the "leftmost" starting position of a totally
+    /// different pattern!
+    reverse: DFA,
+}
+
+/// Convenience routines for regex and cache construction.
+impl Regex {
+    /// Parse the given regular expression using the default configuration and
+    /// return the corresponding regex.
+    ///
+    /// If you want a non-default configuration, then use the [`Builder`] to
+    /// set your own configuration.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::regex::Regex, Match};
+    ///
+    /// let re = Regex::new("foo[0-9]+bar")?;
+    /// let mut cache = re.create_cache();
+    /// assert_eq!(
+    ///     Some(Match::must(0, 3..14)),
+    ///     re.find(&mut cache, "zzzfoo12345barzzz"),
+    /// );
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[cfg(feature = "syntax")]
+    pub fn new(pattern: &str) -> Result<Regex, BuildError> {
+        Regex::builder().build(pattern)
+    }
+
+    /// Like `new`, but parses multiple patterns into a single "multi regex."
+    /// This similarly uses the default regex configuration.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::regex::Regex, Match};
+    ///
+    /// let re = Regex::new_many(&["[a-z]+", "[0-9]+"])?;
+    /// let mut cache = re.create_cache();
+    ///
+    /// let mut it = re.find_iter(&mut cache, "abc 1 foo 4567 0 quux");
+    /// assert_eq!(Some(Match::must(0, 0..3)), it.next());
+    /// assert_eq!(Some(Match::must(1, 4..5)), it.next());
+    /// assert_eq!(Some(Match::must(0, 6..9)), it.next());
+    /// assert_eq!(Some(Match::must(1, 10..14)), it.next());
+    /// assert_eq!(Some(Match::must(1, 15..16)), it.next());
+    /// assert_eq!(Some(Match::must(0, 17..21)), it.next());
+    /// assert_eq!(None, it.next());
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[cfg(feature = "syntax")]
+    pub fn new_many<P: AsRef<str>>(
+        patterns: &[P],
+    ) -> Result<Regex, BuildError> {
+        Regex::builder().build_many(patterns)
+    }
+
+    /// Return a builder for configuring the construction of a `Regex`.
+    ///
+    /// This is a convenience routine to avoid needing to import the
+    /// [`Builder`] type in common cases.
+    ///
+    /// # Example
+    ///
+    /// This example shows how to use the builder to disable UTF-8 mode
+    /// everywhere.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{
+    ///     hybrid::regex::Regex, nfa::thompson, util::syntax, Match,
+    /// };
+    ///
+    /// let re = Regex::builder()
+    ///     .syntax(syntax::Config::new().utf8(false))
+    ///     .thompson(thompson::Config::new().utf8(false))
+    ///     .build(r"foo(?-u:[^b])ar.*")?;
+    /// let mut cache = re.create_cache();
+    ///
+    /// let haystack = b"\xFEfoo\xFFarzz\xE2\x98\xFF\n";
+    /// let expected = Some(Match::must(0, 1..9));
+    /// let got = re.find(&mut cache, haystack);
+    /// assert_eq!(expected, got);
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn builder() -> Builder {
+        Builder::new()
+    }
+
+    /// Create a new cache for this `Regex`.
+    ///
+    /// The cache returned should only be used for searches for this
+    /// `Regex`. If you want to reuse the cache for another `Regex`, then
+    /// you must call [`Cache::reset`] with that `Regex` (or, equivalently,
+    /// [`Regex::reset_cache`]).
+    pub fn create_cache(&self) -> Cache {
+        Cache::new(self)
+    }
+
+    /// Reset the given cache such that it can be used for searching with the
+    /// this `Regex` (and only this `Regex`).
+    ///
+    /// A cache reset permits reusing memory already allocated in this cache
+    /// with a different `Regex`.
+    ///
+    /// Resetting a cache sets its "clear count" to 0. This is relevant if the
+    /// `Regex` has been configured to "give up" after it has cleared the cache
+    /// a certain number of times.
+    ///
+    /// # Example
+    ///
+    /// This shows how to re-purpose a cache for use with a different `Regex`.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::regex::Regex, Match};
+    ///
+    /// let re1 = Regex::new(r"\w")?;
+    /// let re2 = Regex::new(r"\W")?;
+    ///
+    /// let mut cache = re1.create_cache();
+    /// assert_eq!(
+    ///     Some(Match::must(0, 0..2)),
+    ///     re1.find(&mut cache, "Δ"),
+    /// );
+    ///
+    /// // Using 'cache' with re2 is not allowed. It may result in panics or
+    /// // incorrect results. In order to re-purpose the cache, we must reset
+    /// // it with the Regex we'd like to use it with.
+    /// //
+    /// // Similarly, after this reset, using the cache with 're1' is also not
+    /// // allowed.
+    /// re2.reset_cache(&mut cache);
+    /// assert_eq!(
+    ///     Some(Match::must(0, 0..3)),
+    ///     re2.find(&mut cache, "☃"),
+    /// );
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn reset_cache(&self, cache: &mut Cache) {
+        self.forward().reset_cache(&mut cache.forward);
+        self.reverse().reset_cache(&mut cache.reverse);
+    }
+}
+
+/// Standard infallible search routines for finding and iterating over matches.
+impl Regex {
+    /// Returns true if and only if this regex matches the given haystack.
+    ///
+    /// This routine may short circuit if it knows that scanning future input
+    /// will never lead to a different result. In particular, if the underlying
+    /// DFA enters a match state or a dead state, then this routine will return
+    /// `true` or `false`, respectively, without inspecting any future input.
+    ///
+    /// # Panics
+    ///
+    /// This routine panics if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search panics, callers cannot know whether a match exists or
+    /// not.
+    ///
+    /// Use [`Regex::try_search`] if you want to handle these error conditions.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::hybrid::regex::Regex;
+    ///
+    /// let re = Regex::new("foo[0-9]+bar")?;
+    /// let mut cache = re.create_cache();
+    ///
+    /// assert!(re.is_match(&mut cache, "foo12345bar"));
+    /// assert!(!re.is_match(&mut cache, "foobar"));
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn is_match<'h, I: Into<Input<'h>>>(
+        &self,
+        cache: &mut Cache,
+        input: I,
+    ) -> bool {
+        // Not only can we do an "earliest" search, but we can avoid doing a
+        // reverse scan too.
+        self.forward()
+            .try_search_fwd(&mut cache.forward, &input.into().earliest(true))
+            .unwrap()
+            .is_some()
+    }
+
+    /// Returns the start and end offset of the leftmost match. If no match
+    /// exists, then `None` is returned.
+    ///
+    /// # Panics
+    ///
+    /// This routine panics if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search panics, callers cannot know whether a match exists or
+    /// not.
+    ///
+    /// Use [`Regex::try_search`] if you want to handle these error conditions.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{Match, hybrid::regex::Regex};
+    ///
+    /// let re = Regex::new("foo[0-9]+")?;
+    /// let mut cache = re.create_cache();
+    /// assert_eq!(
+    ///     Some(Match::must(0, 3..11)),
+    ///     re.find(&mut cache, "zzzfoo12345zzz"),
+    /// );
+    ///
+    /// // Even though a match is found after reading the first byte (`a`),
+    /// // the default leftmost-first match semantics demand that we find the
+    /// // earliest match that prefers earlier parts of the pattern over latter
+    /// // parts.
+    /// let re = Regex::new("abc|a")?;
+    /// let mut cache = re.create_cache();
+    /// assert_eq!(Some(Match::must(0, 0..3)), re.find(&mut cache, "abc"));
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn find<'h, I: Into<Input<'h>>>(
+        &self,
+        cache: &mut Cache,
+        input: I,
+    ) -> Option<Match> {
+        self.try_search(cache, &input.into()).unwrap()
+    }
+
+    /// Returns an iterator over all non-overlapping leftmost matches in the
+    /// given bytes. If no match exists, then the iterator yields no elements.
+    ///
+    /// # Panics
+    ///
+    /// This routine panics if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search panics, callers cannot know whether a match exists or
+    /// not.
+    ///
+    /// The above conditions also apply to the iterator returned as well. For
+    /// example, if the lazy DFA gives up or quits during a search using this
+    /// method, then a panic will occur during iteration.
+    ///
+    /// Use [`Regex::try_search`] with [`util::iter::Searcher`](iter::Searcher)
+    /// if you want to handle these error conditions.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use regex_automata::{hybrid::regex::Regex, Match};
+    ///
+    /// let re = Regex::new("foo[0-9]+")?;
+    /// let mut cache = re.create_cache();
+    ///
+    /// let text = "foo1 foo12 foo123";
+    /// let matches: Vec<Match> = re.find_iter(&mut cache, text).collect();
+    /// assert_eq!(matches, vec![
+    ///     Match::must(0, 0..4),
+    ///     Match::must(0, 5..10),
+    ///     Match::must(0, 11..17),
+    /// ]);
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    #[inline]
+    pub fn find_iter<'r, 'c, 'h, I: Into<Input<'h>>>(
+        &'r self,
+        cache: &'c mut Cache,
+        input: I,
+    ) -> FindMatches<'r, 'c, 'h> {
+        let it = iter::Searcher::new(input.into());
+        FindMatches { re: self, cache, it }
+    }
+}
+
+/// Lower level "search" primitives that accept a `&Input` for cheap reuse
+/// and return an error if one occurs instead of panicking.
+impl Regex {
+    /// Returns the start and end offset of the leftmost match. If no match
+    /// exists, then `None` is returned.
+    ///
+    /// This is like [`Regex::find`] but with two differences:
+    ///
+    /// 1. It is not generic over `Into<Input>` and instead accepts a
+    /// `&Input`. This permits reusing the same `Input` for multiple searches
+    /// without needing to create a new one. This _may_ help with latency.
+    /// 2. It returns an error if the search could not complete where as
+    /// [`Regex::find`] will panic.
+    ///
+    /// # Errors
+    ///
+    /// This routine errors if the search could not complete. This can occur
+    /// in a number of circumstances:
+    ///
+    /// * The configuration of the lazy DFA may permit it to "quit" the search.
+    /// For example, setting quit bytes or enabling heuristic support for
+    /// Unicode word boundaries. The default configuration does not enable any
+    /// option that could result in the lazy DFA quitting.
+    /// * The configuration of the lazy DFA may also permit it to "give up"
+    /// on a search if it makes ineffective use of its transition table
+    /// cache. The default configuration does not enable this by default,
+    /// although it is typically a good idea to.
+    /// * When the provided `Input` configuration is not supported. For
+    /// example, by providing an unsupported anchor mode.
+    ///
+    /// When a search returns an error, callers cannot know whether a match
+    /// exists or not.
+    #[inline]
+    pub fn try_search(
+        &self,
+        cache: &mut Cache,
+        input: &Input<'_>,
+    ) -> Result<Option<Match>, MatchError> {
+        let (fcache, rcache) = (&mut cache.forward, &mut cache.reverse);
+        let end = match self.forward().try_search_fwd(fcache, input)? {
+            None => return Ok(None),
+            Some(end) => end,
+        };
+        // This special cases an empty match at the beginning of the search. If
+        // our end matches our start, then since a reverse DFA can't match past
+        // the start, it must follow that our starting position is also our end
+        // position. So short circuit and skip the reverse search.
+        if input.start() == end.offset() {
+            return Ok(Some(Match::new(
+                end.pattern(),
+                end.offset()..end.offset(),
+            )));
+        }
+        // We can also skip the reverse search if we know our search was
+        // anchored. This occurs either when the input config is anchored or
+        // when we know the regex itself is anchored. In this case, we know the
+        // start of the match, if one is found, must be the start of the
+        // search.
+        if self.is_anchored(input) {
+            return Ok(Some(Match::new(
+                end.pattern(),
+                input.start()..end.offset(),
+            )));
+        }
+        // N.B. I have tentatively convinced myself that it isn't necessary
+        // to specify the specific pattern for the reverse search since the
+        // reverse search will always find the same pattern to match as the
+        // forward search. But I lack a rigorous proof. Why not just provide
+        // the pattern anyway? Well, if it is needed, then leaving it out
+        // gives us a chance to find a witness. (Also, if we don't need to
+        // specify the pattern, then we don't need to build the reverse DFA
+        // with 'starts_for_each_pattern' enabled. It doesn't matter too much
+        // for the lazy DFA, but does make the overall DFA bigger.)
+        //
+        // We also need to be careful to disable 'earliest' for the reverse
+        // search, since it could be enabled for the forward search. In the
+        // reverse case, to satisfy "leftmost" criteria, we need to match as
+        // much as we can. We also need to be careful to make the search
+        // anchored. We don't want the reverse search to report any matches
+        // other than the one beginning at the end of our forward search.
+        let revsearch = input
+            .clone()
+            .span(input.start()..end.offset())
+            .anchored(Anchored::Yes)
+            .earliest(false);
+        let start = self
+            .reverse()
+            .try_search_rev(rcache, &revsearch)?
+            .expect("reverse search must match if forward search does");
+        debug_assert_eq!(
+            start.pattern(),
+            end.pattern(),
+            "forward and reverse search must match same pattern",
+        );
+        debug_assert!(start.offset() <= end.offset());
+        Ok(Some(Match::new(end.pattern(), start.offset()..end.offset())))
+    }
+
+    /// Returns true if either the given input specifies an anchored search
+    /// or if the underlying NFA is always anchored.
+    fn is_anchored(&self, input: &Input<'_>) -> bool {
+        match input.get_anchored() {
+            Anchored::No => {
+                self.forward().get_nfa().is_always_start_anchored()
+            }
+            Anchored::Yes | Anchored::Pattern(_) => true,
+        }
+    }
+}
+
+/// Non-search APIs for querying information about the regex and setting a
+/// prefilter.
+impl Regex {
+    /// Return the underlying lazy DFA responsible for forward matching.
+    ///
+    /// This is useful for accessing the underlying lazy DFA and using it
+    /// directly if the situation calls for it.
+    pub fn forward(&self) -> &DFA {
+        &self.forward
+    }
+
+    /// Return the underlying lazy DFA responsible for reverse matching.
+    ///
+    /// This is useful for accessing the underlying lazy DFA and using it
+    /// directly if the situation calls for it.
+    pub fn reverse(&self) -> &DFA {
+        &self.reverse
+    }
+
+    /// Returns the total number of patterns matched by this regex.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::hybrid::regex::Regex;
+    ///
+    /// let re = Regex::new_many(&[r"[a-z]+", r"[0-9]+", r"\w+"])?;
+    /// assert_eq!(3, re.pattern_len());
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn pattern_len(&self) -> usize {
+        assert_eq!(self.forward().pattern_len(), self.reverse().pattern_len());
+        self.forward().pattern_len()
+    }
+}
+
+/// An iterator over all non-overlapping matches for an infallible search.
+///
+/// The iterator yields a [`Match`] value until no more matches could be found.
+/// If the underlying regex engine returns an error, then a panic occurs.
+///
+/// The lifetime parameters are as follows:
+///
+/// * `'r` represents the lifetime of the regex object.
+/// * `'h` represents the lifetime of the haystack being searched.
+/// * `'c` represents the lifetime of the regex cache.
+///
+/// This iterator can be created with the [`Regex::find_iter`] method.
+#[derive(Debug)]
+pub struct FindMatches<'r, 'c, 'h> {
+    re: &'r Regex,
+    cache: &'c mut Cache,
+    it: iter::Searcher<'h>,
+}
+
+impl<'r, 'c, 'h> Iterator for FindMatches<'r, 'c, 'h> {
+    type Item = Match;
+
+    #[inline]
+    fn next(&mut self) -> Option<Match> {
+        let FindMatches { re, ref mut cache, ref mut it } = *self;
+        it.advance(|input| re.try_search(cache, input))
+    }
+}
+
+/// A cache represents a partially computed forward and reverse DFA.
+///
+/// A cache is the key component that differentiates a classical DFA and a
+/// hybrid NFA/DFA (also called a "lazy DFA"). Where a classical DFA builds a
+/// complete transition table that can handle all possible inputs, a hybrid
+/// NFA/DFA starts with an empty transition table and builds only the parts
+/// required during search. The parts that are built are stored in a cache. For
+/// this reason, a cache is a required parameter for nearly every operation on
+/// a [`Regex`].
+///
+/// Caches can be created from their corresponding `Regex` via
+/// [`Regex::create_cache`]. A cache can only be used with either the `Regex`
+/// that created it, or the `Regex` that was most recently used to reset it
+/// with [`Cache::reset`]. Using a cache with any other `Regex` may result in
+/// panics or incorrect results.
+#[derive(Debug, Clone)]
+pub struct Cache {
+    forward: dfa::Cache,
+    reverse: dfa::Cache,
+}
+
+impl Cache {
+    /// Create a new cache for the given `Regex`.
+    ///
+    /// The cache returned should only be used for searches for the given
+    /// `Regex`. If you want to reuse the cache for another `Regex`, then you
+    /// must call [`Cache::reset`] with that `Regex`.
+    pub fn new(re: &Regex) -> Cache {
+        let forward = dfa::Cache::new(re.forward());
+        let reverse = dfa::Cache::new(re.reverse());
+        Cache { forward, reverse }
+    }
+
+    /// Reset this cache such that it can be used for searching with the given
+    /// `Regex` (and only that `Regex`).
+    ///
+    /// A cache reset permits reusing memory already allocated in this cache
+    /// with a different `Regex`.
+    ///
+    /// Resetting a cache sets its "clear count" to 0. This is relevant if the
+    /// `Regex` has been configured to "give up" after it has cleared the cache
+    /// a certain number of times.
+    ///
+    /// # Example
+    ///
+    /// This shows how to re-purpose a cache for use with a different `Regex`.
+    ///
+    /// ```
+    /// # if cfg!(miri) { return Ok(()); } // miri takes too long
+    /// use regex_automata::{hybrid::regex::Regex, Match};
+    ///
+    /// let re1 = Regex::new(r"\w")?;
+    /// let re2 = Regex::new(r"\W")?;
+    ///
+    /// let mut cache = re1.create_cache();
+    /// assert_eq!(
+    ///     Some(Match::must(0, 0..2)),
+    ///     re1.find(&mut cache, "Δ"),
+    /// );
+    ///
+    /// // Using 'cache' with re2 is not allowed. It may result in panics or
+    /// // incorrect results. In order to re-purpose the cache, we must reset
+    /// // it with the Regex we'd like to use it with.
+    /// //
+    /// // Similarly, after this reset, using the cache with 're1' is also not
+    /// // allowed.
+    /// cache.reset(&re2);
+    /// assert_eq!(
+    ///     Some(Match::must(0, 0..3)),
+    ///     re2.find(&mut cache, "☃"),
+    /// );
+    ///
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn reset(&mut self, re: &Regex) {
+        self.forward.reset(re.forward());
+        self.reverse.reset(re.reverse());
+    }
+
+    /// Return a reference to the forward cache.
+    pub fn forward(&mut self) -> &dfa::Cache {
+        &self.forward
+    }
+
+    /// Return a reference to the reverse cache.
+    pub fn reverse(&mut self) -> &dfa::Cache {
+        &self.reverse
+    }
+
+    /// Return a mutable reference to the forward cache.
+    ///
+    /// If you need mutable references to both the forward and reverse caches,
+    /// then use [`Cache::as_parts_mut`].
+    pub fn forward_mut(&mut self) -> &mut dfa::Cache {
+        &mut self.forward
+    }
+
+    /// Return a mutable reference to the reverse cache.
+    ///
+    /// If you need mutable references to both the forward and reverse caches,
+    /// then use [`Cache::as_parts_mut`].
+    pub fn reverse_mut(&mut self) -> &mut dfa::Cache {
+        &mut self.reverse
+    }
+
+    /// Return references to the forward and reverse caches, respectively.
+    pub fn as_parts(&self) -> (&dfa::Cache, &dfa::Cache) {
+        (&self.forward, &self.reverse)
+    }
+
+    /// Return mutable references to the forward and reverse caches,
+    /// respectively.
+    pub fn as_parts_mut(&mut self) -> (&mut dfa::Cache, &mut dfa::Cache) {
+        (&mut self.forward, &mut self.reverse)
+    }
+
+    /// Returns the heap memory usage, in bytes, as a sum of the forward and
+    /// reverse lazy DFA caches.
+    ///
+    /// This does **not** include the stack size used up by this cache. To
+    /// compute that, use `std::mem::size_of::<Cache>()`.
+    pub fn memory_usage(&self) -> usize {
+        self.forward.memory_usage() + self.reverse.memory_usage()
+    }
+}
+
+/// A builder for a regex based on a hybrid NFA/DFA.
+///
+/// This builder permits configuring options for the syntax of a pattern, the
+/// NFA construction, the lazy DFA construction and finally the regex searching
+/// itself. This builder is different from a general purpose regex builder
+/// in that it permits fine grain configuration of the construction process.
+/// The trade off for this is complexity, and the possibility of setting a
+/// configuration that might not make sense. For example, there are two
+/// different UTF-8 modes:
+///
+/// * [`syntax::Config::utf8`](crate::util::syntax::Config::utf8) controls
+/// whether the pattern itself can contain sub-expressions that match invalid
+/// UTF-8.
+/// * [`thompson::Config::utf8`] controls how the regex iterators themselves
+/// advance the starting position of the next search when a match with zero
+/// length is found.
+///
+/// Generally speaking, callers will want to either enable all of these or
+/// disable all of these.
+///
+/// Internally, building a regex requires building two hybrid NFA/DFAs,
+/// where one is responsible for finding the end of a match and the other is
+/// responsible for finding the start of a match. If you only need to detect
+/// whether something matched, or only the end of a match, then you should use
+/// a [`dfa::Builder`] to construct a single hybrid NFA/DFA, which is cheaper
+/// than building two of them.
+///
+/// # Example
+///
+/// This example shows how to disable UTF-8 mode in the syntax and the regex
+/// itself. This is generally what you want for matching on arbitrary bytes.
+///
+/// ```
+/// # if cfg!(miri) { return Ok(()); } // miri takes too long
+/// use regex_automata::{
+///     hybrid::regex::Regex, nfa::thompson, util::syntax, Match,
+/// };
+///
+/// let re = Regex::builder()
+///     .syntax(syntax::Config::new().utf8(false))
+///     .thompson(thompson::Config::new().utf8(false))
+///     .build(r"foo(?-u:[^b])ar.*")?;
+/// let mut cache = re.create_cache();
+///
+/// let haystack = b"\xFEfoo\xFFarzz\xE2\x98\xFF\n";
+/// let expected = Some(Match::must(0, 1..9));
+/// let got = re.find(&mut cache, haystack);
+/// assert_eq!(expected, got);
+/// // Notice that `(?-u:[^b])` matches invalid UTF-8,
+/// // but the subsequent `.*` does not! Disabling UTF-8
+/// // on the syntax permits this.
+/// assert_eq!(b"foo\xFFarzz", &haystack[got.unwrap().range()]);
+///
+/// # Ok::<(), Box<dyn std::error::Error>>(())
+/// ```
+#[derive(Clone, Debug)]
+pub struct Builder {
+    dfa: dfa::Builder,
+}
+
+impl Builder {
+    /// Create a new regex builder with the default configuration.
+    pub fn new() -> Builder {
+        Builder { dfa: DFA::builder() }
+    }
+
+    /// Build a regex from the given pattern.
+    ///
+    /// If there was a problem parsing or compiling the pattern, then an error
+    /// is returned.
+    #[cfg(feature = "syntax")]
+    pub fn build(&self, pattern: &str) -> Result<Regex, BuildError> {
+        self.build_many(&[pattern])
+    }
+
+    /// Build a regex from the given patterns.
+    #[cfg(feature = "syntax")]
+    pub fn build_many<P: AsRef<str>>(
+        &self,
+        patterns: &[P],
+    ) -> Result<Regex, BuildError> {
+        let forward = self.dfa.build_many(patterns)?;
+        let reverse = self
+            .dfa
+            .clone()
+            .configure(
+                DFA::config()
+                    .prefilter(None)
+                    .specialize_start_states(false)
+                    .match_kind(MatchKind::All),
+            )
+            .thompson(thompson::Config::new().reverse(true))
+            .build_many(patterns)?;
+        Ok(self.build_from_dfas(forward, reverse))
+    }
+
+    /// Build a regex from its component forward and reverse hybrid NFA/DFAs.
+    ///
+    /// This is useful when you've built a forward and reverse lazy DFA
+    /// separately, and want to combine them into a single regex. Once build,
+    /// the individual DFAs given can still be accessed via [`Regex::forward`]
+    /// and [`Regex::reverse`].
+    ///
+    /// It is important that the reverse lazy DFA be compiled under the
+    /// following conditions:
+    ///
+    /// * It should use [`MatchKind::All`] semantics.
+    /// * It should match in reverse.
+    /// * Otherwise, its configuration should match the forward DFA.
+    ///
+    /// If these conditions aren't satisfied, then the behavior of searches is
+    /// unspecified.
+    ///
+    /// Note that when using this constructor, no configuration is applied.
+    /// Since this routine provides the DFAs to the builder, there is no
+    /// opportunity to apply other configuration options.
+    ///
+    /// # Example
+    ///
+    /// This shows how to build individual lazy forward and reverse DFAs, and
+    /// then combine them into a single `Regex`.
+    ///
+    /// ```
+    /// use regex_automata::{
+    ///     hybrid::{dfa::DFA, regex::Regex},
+    ///     nfa::thompson,
+    ///     MatchKind,
+    /// };
+    ///
+    /// let fwd = DFA::new(r"foo[0-9]+")?;
+    /// let rev = DFA::builder()
+    ///     .configure(DFA::config().match_kind(MatchKind::All))
+    ///     .thompson(thompson::Config::new().reverse(true))
+    ///     .build(r"foo[0-9]+")?;
+    ///
+    /// let re = Regex::builder().build_from_dfas(fwd, rev);
+    /// let mut cache = re.create_cache();
+    /// assert_eq!(true, re.is_match(&mut cache, "foo123"));
+    /// # Ok::<(), Box<dyn std::error::Error>>(())
+    /// ```
+    pub fn build_from_dfas(&self, forward: DFA, reverse: DFA) -> Regex {
+        Regex { forward, reverse }
+    }
+
+    /// Set the syntax configuration for this builder using
+    /// [`syntax::Config`](crate::util::syntax::Config).
+    ///
+    /// This permits setting things like case insensitivity, Unicode and multi
+    /// line mode.
+    #[cfg(feature = "syntax")]
+    pub fn syntax(
+        &mut self,
+        config: crate::util::syntax::Config,
+    ) -> &mut Builder {
+        self.dfa.syntax(config);
+        self
+    }
+
+    /// Set the Thompson NFA configuration for this builder using
+    /// [`nfa::thompson::Config`](thompson::Config).
+    ///
+    /// This permits setting things like whether additional time should be
+    /// spent shrinking the size of the NFA.
+    #[cfg(feature = "syntax")]
+    pub fn thompson(&mut self, config: thompson::Config) -> &mut Builder {
+        self.dfa.thompson(config);
+        self
+    }
+
+    /// Set the lazy DFA compilation configuration for this builder using
+    /// [`dfa::Config`].
+    ///
+    /// This permits setting things like whether Unicode word boundaries should
+    /// be heuristically supported or settings how the behavior of the cache.
+    pub fn dfa(&mut self, config: dfa::Config) -> &mut Builder {
+        self.dfa.configure(config);
+        self
+    }
+}
+
+impl Default for Builder {
+    fn default() -> Builder {
+        Builder::new()
+    }
+}
diff --git a/vendor/regex-automata/src/hybrid/search.rs b/vendor/regex-automata/src/hybrid/search.rs
new file mode 100644
index 0000000..1f4a505
--- /dev/null
+++ b/vendor/regex-automata/src/hybrid/search.rs
@@ -0,0 +1,802 @@
+use crate::{
+    hybrid::{
+        dfa::{Cache, OverlappingState, DFA},
+        id::LazyStateID,
+    },
+    util::{
+        prefilter::Prefilter,
+        search::{HalfMatch, Input, MatchError, Span},
+    },
+};
+
+#[inline(never)]
+pub(crate) fn find_fwd(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+) -> Result<Option<HalfMatch>, MatchError> {
+    if input.is_done() {
+        return Ok(None);
+    }
+    let pre = if input.get_anchored().is_anchored() {
+        None
+    } else {
+        dfa.get_config().get_prefilter()
+    };
+    // So what we do here is specialize four different versions of 'find_fwd':
+    // one for each of the combinations for 'has prefilter' and 'is earliest
+    // search'. The reason for doing this is that both of these things require
+    // branches and special handling in some code that can be very hot,
+    // and shaving off as much as we can when we don't need it tends to be
+    // beneficial in ad hoc benchmarks. To see these differences, you often
+    // need a query with a high match count. In other words, specializing these
+    // four routines *tends* to help latency more than throughput.
+    if pre.is_some() {
+        if input.get_earliest() {
+            find_fwd_imp(dfa, cache, input, pre, true)
+        } else {
+            find_fwd_imp(dfa, cache, input, pre, false)
+        }
+    } else {
+        if input.get_earliest() {
+            find_fwd_imp(dfa, cache, input, None, true)
+        } else {
+            find_fwd_imp(dfa, cache, input, None, false)
+        }
+    }
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn find_fwd_imp(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+    pre: Option<&'_ Prefilter>,
+    earliest: bool,
+) -> Result<Option<HalfMatch>, MatchError> {
+    // See 'prefilter_restart' docs for explanation.
+    let universal_start = dfa.get_nfa().look_set_prefix_any().is_empty();
+    let mut mat = None;
+    let mut sid = init_fwd(dfa, cache, input)?;
+    let mut at = input.start();
+    // This could just be a closure, but then I think it would be unsound
+    // because it would need to be safe to invoke. This way, the lack of safety
+    // is clearer in the code below.
+    macro_rules! next_unchecked {
+        ($sid:expr, $at:expr) => {{
+            let byte = *input.haystack().get_unchecked($at);
+            dfa.next_state_untagged_unchecked(cache, $sid, byte)
+        }};
+    }
+
+    if let Some(ref pre) = pre {
+        let span = Span::from(at..input.end());
+        match pre.find(input.haystack(), span) {
+            None => return Ok(mat),
+            Some(ref span) => {
+                at = span.start;
+                if !universal_start {
+                    sid = prefilter_restart(dfa, cache, &input, at)?;
+                }
+            }
+        }
+    }
+    cache.search_start(at);
+    while at < input.end() {
+        if sid.is_tagged() {
+            cache.search_update(at);
+            sid = dfa
+                .next_state(cache, sid, input.haystack()[at])
+                .map_err(|_| gave_up(at))?;
+        } else {
+            // SAFETY: There are two safety invariants we need to uphold
+            // here in the loops below: that 'sid' and 'prev_sid' are valid
+            // state IDs for this DFA, and that 'at' is a valid index into
+            // 'haystack'. For the former, we rely on the invariant that
+            // next_state* and start_state_forward always returns a valid state
+            // ID (given a valid state ID in the former case), and that we are
+            // only at this place in the code if 'sid' is untagged. Moreover,
+            // every call to next_state_untagged_unchecked below is guarded by
+            // a check that sid is untagged. For the latter safety invariant,
+            // we always guard unchecked access with a check that 'at' is less
+            // than 'end', where 'end <= haystack.len()'. In the unrolled loop
+            // below, we ensure that 'at' is always in bounds.
+            //
+            // PERF: For justification of omitting bounds checks, it gives us a
+            // ~10% bump in search time. This was used for a benchmark:
+            //
+            //     regex-cli find half hybrid -p '(?m)^.+$' -UBb bigfile
+            //
+            // PERF: For justification for the loop unrolling, we use a few
+            // different tests:
+            //
+            //     regex-cli find half hybrid -p '\w{50}' -UBb bigfile
+            //     regex-cli find half hybrid -p '(?m)^.+$' -UBb bigfile
+            //     regex-cli find half hybrid -p 'ZQZQZQZQ' -UBb bigfile
+            //
+            // And there are three different configurations:
+            //
+            //     nounroll: this entire 'else' block vanishes and we just
+            //               always use 'dfa.next_state(..)'.
+            //      unroll1: just the outer loop below
+            //      unroll2: just the inner loop below
+            //      unroll3: both the outer and inner loops below
+            //
+            // This results in a matrix of timings for each of the above
+            // regexes with each of the above unrolling configurations:
+            //
+            //              '\w{50}'   '(?m)^.+$'   'ZQZQZQZQ'
+            //   nounroll   1.51s      2.34s        1.51s
+            //    unroll1   1.53s      2.32s        1.56s
+            //    unroll2   2.22s      1.50s        0.61s
+            //    unroll3   1.67s      1.45s        0.61s
+            //
+            // Ideally we'd be able to find a configuration that yields the
+            // best time for all regexes, but alas we settle for unroll3 that
+            // gives us *almost* the best for '\w{50}' and the best for the
+            // other two regexes.
+            //
+            // So what exactly is going on here? The first unrolling (grouping
+            // together runs of untagged transitions) specifically targets
+            // our choice of representation. The second unrolling (grouping
+            // together runs of self-transitions) specifically targets a common
+            // DFA topology. Let's dig in a little bit by looking at our
+            // regexes:
+            //
+            // '\w{50}': This regex spends a lot of time outside of the DFA's
+            // start state matching some part of the '\w' repetition. This
+            // means that it's a bit of a worst case for loop unrolling that
+            // targets self-transitions since the self-transitions in '\w{50}'
+            // are not particularly active for this haystack. However, the
+            // first unrolling (grouping together untagged transitions)
+            // does apply quite well here since very few transitions hit
+            // match/dead/quit/unknown states. It is however worth mentioning
+            // that if start states are configured to be tagged (which you
+            // typically want to do if you have a prefilter), then this regex
+            // actually slows way down because it is constantly ping-ponging
+            // out of the unrolled loop and into the handling of a tagged start
+            // state below. But when start states aren't tagged, the unrolled
+            // loop stays hot. (This is why it's imperative that start state
+            // tagging be disabled when there isn't a prefilter!)
+            //
+            // '(?m)^.+$': There are two important aspects of this regex: 1)
+            // on this haystack, its match count is very high, much higher
+            // than the other two regex and 2) it spends the vast majority
+            // of its time matching '.+'. Since Unicode mode is disabled,
+            // this corresponds to repeatedly following self transitions for
+            // the vast majority of the input. This does benefit from the
+            // untagged unrolling since most of the transitions will be to
+            // untagged states, but the untagged unrolling does more work than
+            // what is actually required. Namely, it has to keep track of the
+            // previous and next state IDs, which I guess requires a bit more
+            // shuffling. This is supported by the fact that nounroll+unroll1
+            // are both slower than unroll2+unroll3, where the latter has a
+            // loop unrolling that specifically targets self-transitions.
+            //
+            // 'ZQZQZQZQ': This one is very similar to '(?m)^.+$' because it
+            // spends the vast majority of its time in self-transitions for
+            // the (implicit) unanchored prefix. The main difference with
+            // '(?m)^.+$' is that it has a much lower match count. So there
+            // isn't much time spent in the overhead of reporting matches. This
+            // is the primary explainer in the perf difference here. We include
+            // this regex and the former to make sure we have comparison points
+            // with high and low match counts.
+            //
+            // NOTE: I used 'OpenSubtitles2018.raw.sample.en' for 'bigfile'.
+            //
+            // NOTE: In a follow-up, it turns out that the "inner" loop
+            // mentioned above was a pretty big pessimization in some other
+            // cases. Namely, it resulted in too much ping-ponging into and out
+            // of the loop, which resulted in nearly ~2x regressions in search
+            // time when compared to the originally lazy DFA in the regex crate.
+            // So I've removed the second loop unrolling that targets the
+            // self-transition case.
+            let mut prev_sid = sid;
+            while at < input.end() {
+                prev_sid = unsafe { next_unchecked!(sid, at) };
+                if prev_sid.is_tagged() || at + 3 >= input.end() {
+                    core::mem::swap(&mut prev_sid, &mut sid);
+                    break;
+                }
+                at += 1;
+
+                sid = unsafe { next_unchecked!(prev_sid, at) };
+                if sid.is_tagged() {
+                    break;
+                }
+                at += 1;
+
+                prev_sid = unsafe { next_unchecked!(sid, at) };
+                if prev_sid.is_tagged() {
+                    core::mem::swap(&mut prev_sid, &mut sid);
+                    break;
+                }
+                at += 1;
+
+                sid = unsafe { next_unchecked!(prev_sid, at) };
+                if sid.is_tagged() {
+                    break;
+                }
+                at += 1;
+            }
+            // If we quit out of the code above with an unknown state ID at
+            // any point, then we need to re-compute that transition using
+            // 'next_state', which will do NFA powerset construction for us.
+            if sid.is_unknown() {
+                cache.search_update(at);
+                sid = dfa
+                    .next_state(cache, prev_sid, input.haystack()[at])
+                    .map_err(|_| gave_up(at))?;
+            }
+        }
+        if sid.is_tagged() {
+            if sid.is_start() {
+                if let Some(ref pre) = pre {
+                    let span = Span::from(at..input.end());
+                    match pre.find(input.haystack(), span) {
+                        None => {
+                            cache.search_finish(span.end);
+                            return Ok(mat);
+                        }
+                        Some(ref span) => {
+                            // We want to skip any update to 'at' below
+                            // at the end of this iteration and just
+                            // jump immediately back to the next state
+                            // transition at the leading position of the
+                            // candidate match.
+                            //
+                            // ... but only if we actually made progress
+                            // with our prefilter, otherwise if the start
+                            // state has a self-loop, we can get stuck.
+                            if span.start > at {
+                                at = span.start;
+                                if !universal_start {
+                                    sid = prefilter_restart(
+                                        dfa, cache, &input, at,
+                                    )?;
+                                }
+                                continue;
+                            }
+                        }
+                    }
+                }
+            } else if sid.is_match() {
+                let pattern = dfa.match_pattern(cache, sid, 0);
+                // Since slice ranges are inclusive at the beginning and
+                // exclusive at the end, and since forward searches report
+                // the end, we can return 'at' as-is. This only works because
+                // matches are delayed by 1 byte. So by the time we observe a
+                // match, 'at' has already been set to 1 byte past the actual
+                // match location, which is precisely the exclusive ending
+                // bound of the match.
+                mat = Some(HalfMatch::new(pattern, at));
+                if earliest {
+                    cache.search_finish(at);
+                    return Ok(mat);
+                }
+            } else if sid.is_dead() {
+                cache.search_finish(at);
+                return Ok(mat);
+            } else if sid.is_quit() {
+                cache.search_finish(at);
+                return Err(MatchError::quit(input.haystack()[at], at));
+            } else {
+                debug_assert!(sid.is_unknown());
+                unreachable!("sid being unknown is a bug");
+            }
+        }
+        at += 1;
+    }
+    eoi_fwd(dfa, cache, input, &mut sid, &mut mat)?;
+    cache.search_finish(input.end());
+    Ok(mat)
+}
+
+#[inline(never)]
+pub(crate) fn find_rev(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+) -> Result<Option<HalfMatch>, MatchError> {
+    if input.is_done() {
+        return Ok(None);
+    }
+    if input.get_earliest() {
+        find_rev_imp(dfa, cache, input, true)
+    } else {
+        find_rev_imp(dfa, cache, input, false)
+    }
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn find_rev_imp(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+    earliest: bool,
+) -> Result<Option<HalfMatch>, MatchError> {
+    let mut mat = None;
+    let mut sid = init_rev(dfa, cache, input)?;
+    // In reverse search, the loop below can't handle the case of searching an
+    // empty slice. Ideally we could write something congruent to the forward
+    // search, i.e., 'while at >= start', but 'start' might be 0. Since we use
+    // an unsigned offset, 'at >= 0' is trivially always true. We could avoid
+    // this extra case handling by using a signed offset, but Rust makes it
+    // annoying to do. So... We just handle the empty case separately.
+    if input.start() == input.end() {
+        eoi_rev(dfa, cache, input, &mut sid, &mut mat)?;
+        return Ok(mat);
+    }
+
+    let mut at = input.end() - 1;
+    macro_rules! next_unchecked {
+        ($sid:expr, $at:expr) => {{
+            let byte = *input.haystack().get_unchecked($at);
+            dfa.next_state_untagged_unchecked(cache, $sid, byte)
+        }};
+    }
+    cache.search_start(at);
+    loop {
+        if sid.is_tagged() {
+            cache.search_update(at);
+            sid = dfa
+                .next_state(cache, sid, input.haystack()[at])
+                .map_err(|_| gave_up(at))?;
+        } else {
+            // SAFETY: See comments in 'find_fwd' for a safety argument.
+            //
+            // PERF: The comments in 'find_fwd' also provide a justification
+            // from a performance perspective as to 1) why we elide bounds
+            // checks and 2) why we do a specialized version of unrolling
+            // below. The reverse search does have a slightly different
+            // consideration in that most reverse searches tend to be
+            // anchored and on shorter haystacks. However, this still makes a
+            // difference. Take this command for example:
+            //
+            //     regex-cli find match hybrid -p '(?m)^.+$' -UBb bigfile
+            //
+            // (Notice that we use 'find hybrid regex', not 'find hybrid dfa'
+            // like in the justification for the forward direction. The 'regex'
+            // sub-command will find start-of-match and thus run the reverse
+            // direction.)
+            //
+            // Without unrolling below, the above command takes around 3.76s.
+            // But with the unrolling below, we get down to 2.55s. If we keep
+            // the unrolling but add in bounds checks, then we get 2.86s.
+            //
+            // NOTE: I used 'OpenSubtitles2018.raw.sample.en' for 'bigfile'.
+            let mut prev_sid = sid;
+            while at >= input.start() {
+                prev_sid = unsafe { next_unchecked!(sid, at) };
+                if prev_sid.is_tagged()
+                    || at <= input.start().saturating_add(3)
+                {
+                    core::mem::swap(&mut prev_sid, &mut sid);
+                    break;
+                }
+                at -= 1;
+
+                sid = unsafe { next_unchecked!(prev_sid, at) };
+                if sid.is_tagged() {
+                    break;
+                }
+                at -= 1;
+
+                prev_sid = unsafe { next_unchecked!(sid, at) };
+                if prev_sid.is_tagged() {
+                    core::mem::swap(&mut prev_sid, &mut sid);
+                    break;
+                }
+                at -= 1;
+
+                sid = unsafe { next_unchecked!(prev_sid, at) };
+                if sid.is_tagged() {
+                    break;
+                }
+                at -= 1;
+            }
+            // If we quit out of the code above with an unknown state ID at
+            // any point, then we need to re-compute that transition using
+            // 'next_state', which will do NFA powerset construction for us.
+            if sid.is_unknown() {
+                cache.search_update(at);
+                sid = dfa
+                    .next_state(cache, prev_sid, input.haystack()[at])
+                    .map_err(|_| gave_up(at))?;
+            }
+        }
+        if sid.is_tagged() {
+            if sid.is_start() {
+                // do nothing
+            } else if sid.is_match() {
+                let pattern = dfa.match_pattern(cache, sid, 0);
+                // Since reverse searches report the beginning of a match
+                // and the beginning is inclusive (not exclusive like the
+                // end of a match), we add 1 to make it inclusive.
+                mat = Some(HalfMatch::new(pattern, at + 1));
+                if earliest {
+                    cache.search_finish(at);
+                    return Ok(mat);
+                }
+            } else if sid.is_dead() {
+                cache.search_finish(at);
+                return Ok(mat);
+            } else if sid.is_quit() {
+                cache.search_finish(at);
+                return Err(MatchError::quit(input.haystack()[at], at));
+            } else {
+                debug_assert!(sid.is_unknown());
+                unreachable!("sid being unknown is a bug");
+            }
+        }
+        if at == input.start() {
+            break;
+        }
+        at -= 1;
+    }
+    cache.search_finish(input.start());
+    eoi_rev(dfa, cache, input, &mut sid, &mut mat)?;
+    Ok(mat)
+}
+
+#[inline(never)]
+pub(crate) fn find_overlapping_fwd(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+    state: &mut OverlappingState,
+) -> Result<(), MatchError> {
+    state.mat = None;
+    if input.is_done() {
+        return Ok(());
+    }
+    let pre = if input.get_anchored().is_anchored() {
+        None
+    } else {
+        dfa.get_config().get_prefilter()
+    };
+    if pre.is_some() {
+        find_overlapping_fwd_imp(dfa, cache, input, pre, state)
+    } else {
+        find_overlapping_fwd_imp(dfa, cache, input, None, state)
+    }
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn find_overlapping_fwd_imp(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+    pre: Option<&'_ Prefilter>,
+    state: &mut OverlappingState,
+) -> Result<(), MatchError> {
+    // See 'prefilter_restart' docs for explanation.
+    let universal_start = dfa.get_nfa().look_set_prefix_any().is_empty();
+    let mut sid = match state.id {
+        None => {
+            state.at = input.start();
+            init_fwd(dfa, cache, input)?
+        }
+        Some(sid) => {
+            if let Some(match_index) = state.next_match_index {
+                let match_len = dfa.match_len(cache, sid);
+                if match_index < match_len {
+                    state.next_match_index = Some(match_index + 1);
+                    let pattern = dfa.match_pattern(cache, sid, match_index);
+                    state.mat = Some(HalfMatch::new(pattern, state.at));
+                    return Ok(());
+                }
+            }
+            // Once we've reported all matches at a given position, we need to
+            // advance the search to the next position.
+            state.at += 1;
+            if state.at > input.end() {
+                return Ok(());
+            }
+            sid
+        }
+    };
+
+    // NOTE: We don't optimize the crap out of this routine primarily because
+    // it seems like most overlapping searches will have higher match counts,
+    // and thus, throughput is perhaps not as important. But if you have a use
+    // case for something faster, feel free to file an issue.
+    cache.search_start(state.at);
+    while state.at < input.end() {
+        sid = dfa
+            .next_state(cache, sid, input.haystack()[state.at])
+            .map_err(|_| gave_up(state.at))?;
+        if sid.is_tagged() {
+            state.id = Some(sid);
+            if sid.is_start() {
+                if let Some(ref pre) = pre {
+                    let span = Span::from(state.at..input.end());
+                    match pre.find(input.haystack(), span) {
+                        None => return Ok(()),
+                        Some(ref span) => {
+                            if span.start > state.at {
+                                state.at = span.start;
+                                if !universal_start {
+                                    sid = prefilter_restart(
+                                        dfa, cache, &input, state.at,
+                                    )?;
+                                }
+                                continue;
+                            }
+                        }
+                    }
+                }
+            } else if sid.is_match() {
+                state.next_match_index = Some(1);
+                let pattern = dfa.match_pattern(cache, sid, 0);
+                state.mat = Some(HalfMatch::new(pattern, state.at));
+                cache.search_finish(state.at);
+                return Ok(());
+            } else if sid.is_dead() {
+                cache.search_finish(state.at);
+                return Ok(());
+            } else if sid.is_quit() {
+                cache.search_finish(state.at);
+                return Err(MatchError::quit(
+                    input.haystack()[state.at],
+                    state.at,
+                ));
+            } else {
+                debug_assert!(sid.is_unknown());
+                unreachable!("sid being unknown is a bug");
+            }
+        }
+        state.at += 1;
+        cache.search_update(state.at);
+    }
+
+    let result = eoi_fwd(dfa, cache, input, &mut sid, &mut state.mat);
+    state.id = Some(sid);
+    if state.mat.is_some() {
+        // '1' is always correct here since if we get to this point, this
+        // always corresponds to the first (index '0') match discovered at
+        // this position. So the next match to report at this position (if
+        // it exists) is at index '1'.
+        state.next_match_index = Some(1);
+    }
+    cache.search_finish(input.end());
+    result
+}
+
+#[inline(never)]
+pub(crate) fn find_overlapping_rev(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+    state: &mut OverlappingState,
+) -> Result<(), MatchError> {
+    state.mat = None;
+    if input.is_done() {
+        return Ok(());
+    }
+    let mut sid = match state.id {
+        None => {
+            let sid = init_rev(dfa, cache, input)?;
+            state.id = Some(sid);
+            if input.start() == input.end() {
+                state.rev_eoi = true;
+            } else {
+                state.at = input.end() - 1;
+            }
+            sid
+        }
+        Some(sid) => {
+            if let Some(match_index) = state.next_match_index {
+                let match_len = dfa.match_len(cache, sid);
+                if match_index < match_len {
+                    state.next_match_index = Some(match_index + 1);
+                    let pattern = dfa.match_pattern(cache, sid, match_index);
+                    state.mat = Some(HalfMatch::new(pattern, state.at));
+                    return Ok(());
+                }
+            }
+            // Once we've reported all matches at a given position, we need
+            // to advance the search to the next position. However, if we've
+            // already followed the EOI transition, then we know we're done
+            // with the search and there cannot be any more matches to report.
+            if state.rev_eoi {
+                return Ok(());
+            } else if state.at == input.start() {
+                // At this point, we should follow the EOI transition. This
+                // will cause us the skip the main loop below and fall through
+                // to the final 'eoi_rev' transition.
+                state.rev_eoi = true;
+            } else {
+                // We haven't hit the end of the search yet, so move on.
+                state.at -= 1;
+            }
+            sid
+        }
+    };
+    cache.search_start(state.at);
+    while !state.rev_eoi {
+        sid = dfa
+            .next_state(cache, sid, input.haystack()[state.at])
+            .map_err(|_| gave_up(state.at))?;
+        if sid.is_tagged() {
+            state.id = Some(sid);
+            if sid.is_start() {
+                // do nothing
+            } else if sid.is_match() {
+                state.next_match_index = Some(1);
+                let pattern = dfa.match_pattern(cache, sid, 0);
+                state.mat = Some(HalfMatch::new(pattern, state.at + 1));
+                cache.search_finish(state.at);
+                return Ok(());
+            } else if sid.is_dead() {
+                cache.search_finish(state.at);
+                return Ok(());
+            } else if sid.is_quit() {
+                cache.search_finish(state.at);
+                return Err(MatchError::quit(
+                    input.haystack()[state.at],
+                    state.at,
+                ));
+            } else {
+                debug_assert!(sid.is_unknown());
+                unreachable!("sid being unknown is a bug");
+            }
+        }
+        if state.at == input.start() {
+            break;
+        }
+        state.at -= 1;
+        cache.search_update(state.at);
+    }
+
+    let result = eoi_rev(dfa, cache, input, &mut sid, &mut state.mat);
+    state.rev_eoi = true;
+    state.id = Some(sid);
+    if state.mat.is_some() {
+        // '1' is always correct here since if we get to this point, this
+        // always corresponds to the first (index '0') match discovered at
+        // this position. So the next match to report at this position (if
+        // it exists) is at index '1'.
+        state.next_match_index = Some(1);
+    }
+    cache.search_finish(input.start());
+    result
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn init_fwd(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+) -> Result<LazyStateID, MatchError> {
+    let sid = dfa.start_state_forward(cache, input)?;
+    // Start states can never be match states, since all matches are delayed
+    // by 1 byte.
+    debug_assert!(!sid.is_match());
+    Ok(sid)
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn init_rev(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+) -> Result<LazyStateID, MatchError> {
+    let sid = dfa.start_state_reverse(cache, input)?;
+    // Start states can never be match states, since all matches are delayed
+    // by 1 byte.
+    debug_assert!(!sid.is_match());
+    Ok(sid)
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn eoi_fwd(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+    sid: &mut LazyStateID,
+    mat: &mut Option<HalfMatch>,
+) -> Result<(), MatchError> {
+    let sp = input.get_span();
+    match input.haystack().get(sp.end) {
+        Some(&b) => {
+            *sid =
+                dfa.next_state(cache, *sid, b).map_err(|_| gave_up(sp.end))?;
+            if sid.is_match() {
+                let pattern = dfa.match_pattern(cache, *sid, 0);
+                *mat = Some(HalfMatch::new(pattern, sp.end));
+            } else if sid.is_quit() {
+                return Err(MatchError::quit(b, sp.end));
+            }
+        }
+        None => {
+            *sid = dfa
+                .next_eoi_state(cache, *sid)
+                .map_err(|_| gave_up(input.haystack().len()))?;
+            if sid.is_match() {
+                let pattern = dfa.match_pattern(cache, *sid, 0);
+                *mat = Some(HalfMatch::new(pattern, input.haystack().len()));
+            }
+            // N.B. We don't have to check 'is_quit' here because the EOI
+            // transition can never lead to a quit state.
+            debug_assert!(!sid.is_quit());
+        }
+    }
+    Ok(())
+}
+
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn eoi_rev(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+    sid: &mut LazyStateID,
+    mat: &mut Option<HalfMatch>,
+) -> Result<(), MatchError> {
+    let sp = input.get_span();
+    if sp.start > 0 {
+        let byte = input.haystack()[sp.start - 1];
+        *sid = dfa
+            .next_state(cache, *sid, byte)
+            .map_err(|_| gave_up(sp.start))?;
+        if sid.is_match() {
+            let pattern = dfa.match_pattern(cache, *sid, 0);
+            *mat = Some(HalfMatch::new(pattern, sp.start));
+        } else if sid.is_quit() {
+            return Err(MatchError::quit(byte, sp.start - 1));
+        }
+    } else {
+        *sid =
+            dfa.next_eoi_state(cache, *sid).map_err(|_| gave_up(sp.start))?;
+        if sid.is_match() {
+            let pattern = dfa.match_pattern(cache, *sid, 0);
+            *mat = Some(HalfMatch::new(pattern, 0));
+        }
+        // N.B. We don't have to check 'is_quit' here because the EOI
+        // transition can never lead to a quit state.
+        debug_assert!(!sid.is_quit());
+    }
+    Ok(())
+}
+
+/// Re-compute the starting state that a DFA should be in after finding a
+/// prefilter candidate match at the position `at`.
+///
+/// It is always correct to call this, but not always necessary. Namely,
+/// whenever the DFA has a universal start state, the DFA can remain in the
+/// start state that it was in when it ran the prefilter. Why? Because in that
+/// case, there is only one start state.
+///
+/// When does a DFA have a universal start state? In precisely cases where
+/// it has no look-around assertions in its prefix. So for example, `\bfoo`
+/// does not have a universal start state because the start state depends on
+/// whether the byte immediately before the start position is a word byte or
+/// not. However, `foo\b` does have a universal start state because the word
+/// boundary does not appear in the pattern's prefix.
+///
+/// So... most cases don't need this, but when a pattern doesn't have a
+/// universal start state, then after a prefilter candidate has been found, the
+/// current state *must* be re-litigated as if computing the start state at the
+/// beginning of the search because it might change. That is, not all start
+/// states are created equal.
+///
+/// Why avoid it? Because while it's not super expensive, it isn't a trivial
+/// operation to compute the start state. It is much better to avoid it and
+/// just state in the current state if you know it to be correct.
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn prefilter_restart(
+    dfa: &DFA,
+    cache: &mut Cache,
+    input: &Input<'_>,
+    at: usize,
+) -> Result<LazyStateID, MatchError> {
+    let mut input = input.clone();
+    input.set_start(at);
+    init_fwd(dfa, cache, &input)
+}
+
+/// A convenience routine for constructing a "gave up" match error.
+#[cfg_attr(feature = "perf-inline", inline(always))]
+fn gave_up(offset: usize) -> MatchError {
+    MatchError::gave_up(offset)
+}