regex_automata/util/

iter.rs

/*!
Generic helpers for iteration of matches from a regex engine in a haystack.

The principle type in this module is a [`Searcher`]. A `Searcher` provides
its own lower level iterator-like API in addition to methods for constructing
types that implement `Iterator`. The documentation for `Searcher` explains a
bit more about why these different APIs exist.

Currently, this module supports iteration over any regex engine that works
with the [`HalfMatch`], [`Match`] or [`Captures`] types.
*/

#[cfg(feature = "alloc")]
use crate::util::captures::Captures;
use crate::util::search::{HalfMatch, Input, Match, MatchError};

/// A searcher for creating iterators and performing lower level iteration.
///
/// This searcher encapsulates the logic required for finding all successive
/// non-overlapping matches in a haystack. In theory, iteration would look
/// something like this:
///
/// 1. Setting the start position to `0`.
/// 2. Execute a regex search. If no match, end iteration.
/// 3. Report the match and set the start position to the end of the match.
/// 4. Go back to (2).
///
/// And if this were indeed the case, it's likely that `Searcher` wouldn't
/// exist. Unfortunately, because a regex may match the empty string, the above
/// logic won't work for all possible regexes. Namely, if an empty match is
/// found, then step (3) would set the start position of the search to the
/// position it was at. Thus, iteration would never end.
///
/// Instead, a `Searcher` knows how to detect these cases and forcefully
/// advance iteration in the case of an empty match that overlaps with a
/// previous match.
///
/// If you know that your regex cannot match any empty string, then the simple
/// algorithm described above will work correctly.
///
/// When possible, prefer the iterators defined on the regex engine you're
/// using. This tries to abstract over the regex engine and is thus a bit more
/// unwieldy to use.
///
/// In particular, a `Searcher` is not itself an iterator. Instead, it provides
/// `advance` routines that permit moving the search along explicitly. It also
/// provides various routines, like [`Searcher::into_matches_iter`], that
/// accept a closure (representing how a regex engine executes a search) and
/// returns a conventional iterator.
///
/// The lifetime parameters come from the [`Input`] type passed to
/// [`Searcher::new`]:
///
/// * `'h` is the lifetime of the underlying haystack.
///
/// # Searcher vs Iterator
///
/// Why does a search type with "advance" APIs exist at all when we also have
/// iterators? Unfortunately, the reasoning behind this split is a complex
/// combination of the following things:
///
/// 1. While many of the regex engines expose their own iterators, it is also
/// nice to expose this lower level iteration helper because it permits callers
/// to provide their own `Input` configuration. Moreover, a `Searcher` can work
/// with _any_ regex engine instead of only the ones defined in this crate.
/// This way, everyone benefits from a shared iteration implementation.
/// 2. There are many different regex engines that, while they have the same
/// match semantics, they have slightly different APIs. Iteration is just
/// complex enough to want to share code, and so we need a way of abstracting
/// over those different regex engines. While we could define a new trait that
/// describes any regex engine search API, it would wind up looking very close
/// to a closure. While there may still be reasons for the more generic trait
/// to exist, for now and for the purposes of iteration, we use a closure.
/// Closures also provide a lot of easy flexibility at the call site, in that
/// they permit the caller to borrow any kind of state they want for use during
/// each search call.
/// 3. As a result of using closures, and because closures are anonymous types
/// that cannot be named, it is difficult to encapsulate them without both
/// costs to speed and added complexity to the public API. For example, in
/// defining an iterator type like
/// [`dfa::regex::FindMatches`](crate::dfa::regex::FindMatches),
/// if we use a closure internally, it's not possible to name this type in the
/// return type of the iterator constructor. Thus, the only way around it is
/// to erase the type by boxing it and turning it into a `Box<dyn FnMut ...>`.
/// This boxed closure is unlikely to be inlined _and_ it infects the public
/// API in subtle ways. Namely, unless you declare the closure as implementing
/// `Send` and `Sync`, then the resulting iterator type won't implement it
/// either. But there are practical issues with requiring the closure to
/// implement `Send` and `Sync` that result in other API complexities that
/// are beyond the scope of this already long exposition.
/// 4. Some regex engines expose more complex match information than just
/// "which pattern matched" and "at what offsets." For example, the PikeVM
/// exposes match spans for each capturing group that participated in the
/// match. In such cases, it can be quite beneficial to reuse the capturing
/// group allocation on subsequent searches. A proper iterator doesn't permit
/// this API due to its interface, so it's useful to have something a bit lower
/// level that permits callers to amortize allocations while also reusing a
/// shared implementation of iteration. (See the documentation for
/// [`Searcher::advance`] for an example of using the "advance" API with the
/// PikeVM.)
///
/// What this boils down to is that there are "advance" APIs which require
/// handing a closure to it for every call, and there are also APIs to create
/// iterators from a closure. The former are useful for _implementing_
/// iterators or when you need more flexibility, while the latter are useful
/// for conveniently writing custom iterators on-the-fly.
///
/// # Example: iterating with captures
///
/// Several regex engines in this crate over convenient iterator APIs over
/// [`Captures`] values. To do so, this requires allocating a new `Captures`
/// value for each iteration step. This can perhaps be more costly than you
/// might want. Instead of implementing your own iterator to avoid that
/// cost (which can be a little subtle if you want to handle empty matches
/// correctly), you can use this `Searcher` to do it for you:
///
/// ```
/// use regex_automata::{
///     nfa::thompson::pikevm::PikeVM,
///     util::iter::Searcher,
///     Input, Span,
/// };
///
/// let re = PikeVM::new("foo(?P<numbers>[0-9]+)")?;
/// let haystack = "foo1 foo12 foo123";
///
/// let mut caps = re.create_captures();
/// let mut cache = re.create_cache();
/// let mut matches = vec![];
/// let mut searcher = Searcher::new(Input::new(haystack));
/// while let Some(_) = searcher.advance(|input| {
///     re.search(&mut cache, input, &mut caps);
///     Ok(caps.get_match())
/// }) {
///     // The unwrap is OK since 'numbers' matches if the pattern matches.
///     matches.push(caps.get_group_by_name("numbers").unwrap());
/// }
/// assert_eq!(matches, vec![
///     Span::from(3..4),
///     Span::from(8..10),
///     Span::from(14..17),
/// ]);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(Clone, Debug)]
pub struct Searcher<'h> {
    /// The input parameters to give to each regex engine call.
    ///
    /// The start position of the search is mutated during iteration.
    input: Input<'h>,
    /// Records the end offset of the most recent match. This is necessary to
    /// handle a corner case for preventing empty matches from overlapping with
    /// the ending bounds of a prior match.
    last_match_end: Option<usize>,
}

impl<'h> Searcher<'h> {
    /// Create a new fallible non-overlapping matches iterator.
    ///
    /// The given `input` provides the parameters (including the haystack),
    /// while the `finder` represents a closure that calls the underlying regex
    /// engine. The closure may borrow any additional state that is needed,
    /// such as a prefilter scanner.
    pub fn new(input: Input<'h>) -> Searcher<'h> {
        Searcher { input, last_match_end: None }
    }

    /// Returns the current `Input` used by this searcher.
    ///
    /// The `Input` returned is generally equivalent to the one given to
    /// [`Searcher::new`], but its start position may be different to reflect
    /// the start of the next search to be executed.
    pub fn input<'s>(&'s self) -> &'s Input<'h> {
        &self.input
    }

    /// Return the next half match for an infallible search if one exists, and
    /// advance to the next position.
    ///
    /// This is like `try_advance_half`, except errors are converted into
    /// panics.
    ///
    /// # Panics
    ///
    /// If the given closure returns an error, then this panics. This is useful
    /// when you know your underlying regex engine has been configured to not
    /// return an error.
    ///
    /// # Example
    ///
    /// This example shows how to use a `Searcher` to iterate over all matches
    /// when using a DFA, which only provides "half" matches.
    ///
    /// ```
    /// use regex_automata::{
    ///     hybrid::dfa::DFA,
    ///     util::iter::Searcher,
    ///     HalfMatch, Input,
    /// };
    ///
    /// let re = DFA::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}")?;
    /// let mut cache = re.create_cache();
    ///
    /// let input = Input::new("2010-03-14 2016-10-08 2020-10-22");
    /// let mut it = Searcher::new(input);
    ///
    /// let expected = Some(HalfMatch::must(0, 10));
    /// let got = it.advance_half(|input| re.try_search_fwd(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = Some(HalfMatch::must(0, 21));
    /// let got = it.advance_half(|input| re.try_search_fwd(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = Some(HalfMatch::must(0, 32));
    /// let got = it.advance_half(|input| re.try_search_fwd(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = None;
    /// let got = it.advance_half(|input| re.try_search_fwd(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    ///
    /// This correctly moves iteration forward even when an empty match occurs:
    ///
    /// ```
    /// use regex_automata::{
    ///     hybrid::dfa::DFA,
    ///     util::iter::Searcher,
    ///     HalfMatch, Input,
    /// };
    ///
    /// let re = DFA::new(r"a|")?;
    /// let mut cache = re.create_cache();
    ///
    /// let input = Input::new("abba");
    /// let mut it = Searcher::new(input);
    ///
    /// let expected = Some(HalfMatch::must(0, 1));
    /// let got = it.advance_half(|input| re.try_search_fwd(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = Some(HalfMatch::must(0, 2));
    /// let got = it.advance_half(|input| re.try_search_fwd(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = Some(HalfMatch::must(0, 4));
    /// let got = it.advance_half(|input| re.try_search_fwd(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = None;
    /// let got = it.advance_half(|input| re.try_search_fwd(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    pub fn advance_half<F>(&mut self, finder: F) -> Option<HalfMatch>
    where
        F: FnMut(&Input<'_>) -> Result<Option<HalfMatch>, MatchError>,
    {
        match self.try_advance_half(finder) {
            Ok(m) => m,
            Err(err) => panic!(
                "unexpected regex half find error: {err}\n\
                 to handle find errors, use 'try' or 'search' methods",
            ),
        }
    }

    /// Return the next match for an infallible search if one exists, and
    /// advance to the next position.
    ///
    /// The search is advanced even in the presence of empty matches by
    /// forbidding empty matches from overlapping with any other match.
    ///
    /// This is like `try_advance`, except errors are converted into panics.
    ///
    /// # Panics
    ///
    /// If the given closure returns an error, then this panics. This is useful
    /// when you know your underlying regex engine has been configured to not
    /// return an error.
    ///
    /// # Example
    ///
    /// This example shows how to use a `Searcher` to iterate over all matches
    /// when using a regex based on lazy DFAs:
    ///
    /// ```
    /// use regex_automata::{
    ///     hybrid::regex::Regex,
    ///     util::iter::Searcher,
    ///     Match, Input,
    /// };
    ///
    /// let re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}")?;
    /// let mut cache = re.create_cache();
    ///
    /// let input = Input::new("2010-03-14 2016-10-08 2020-10-22");
    /// let mut it = Searcher::new(input);
    ///
    /// let expected = Some(Match::must(0, 0..10));
    /// let got = it.advance(|input| re.try_search(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = Some(Match::must(0, 11..21));
    /// let got = it.advance(|input| re.try_search(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = Some(Match::must(0, 22..32));
    /// let got = it.advance(|input| re.try_search(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// let expected = None;
    /// let got = it.advance(|input| re.try_search(&mut cache, input));
    /// assert_eq!(expected, got);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    ///
    /// This example shows the same as above, but with the PikeVM. This example
    /// is useful because it shows how to use this API even when the regex
    /// engine doesn't directly return a `Match`.
    ///
    /// ```
    /// use regex_automata::{
    ///     nfa::thompson::pikevm::PikeVM,
    ///     util::iter::Searcher,
    ///     Match, Input,
    /// };
    ///
    /// let re = PikeVM::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}")?;
    /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures());
    ///
    /// let input = Input::new("2010-03-14 2016-10-08 2020-10-22");
    /// let mut it = Searcher::new(input);
    ///
    /// let expected = Some(Match::must(0, 0..10));
    /// let got = it.advance(|input| {
    ///     re.search(&mut cache, input, &mut caps);
    ///     Ok(caps.get_match())
    /// });
    /// // Note that if we wanted to extract capturing group spans, we could
    /// // do that here with 'caps'.
    /// assert_eq!(expected, got);
    ///
    /// let expected = Some(Match::must(0, 11..21));
    /// let got = it.advance(|input| {
    ///     re.search(&mut cache, input, &mut caps);
    ///     Ok(caps.get_match())
    /// });
    /// assert_eq!(expected, got);
    ///
    /// let expected = Some(Match::must(0, 22..32));
    /// let got = it.advance(|input| {
    ///     re.search(&mut cache, input, &mut caps);
    ///     Ok(caps.get_match())
    /// });
    /// assert_eq!(expected, got);
    ///
    /// let expected = None;
    /// let got = it.advance(|input| {
    ///     re.search(&mut cache, input, &mut caps);
    ///     Ok(caps.get_match())
    /// });
    /// assert_eq!(expected, got);
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    pub fn advance<F>(&mut self, finder: F) -> Option<Match>
    where
        F: FnMut(&Input<'_>) -> Result<Option<Match>, MatchError>,
    {
        match self.try_advance(finder) {
            Ok(m) => m,
            Err(err) => panic!(
                "unexpected regex find error: {err}\n\
                 to handle find errors, use 'try' or 'search' methods",
            ),
        }
    }

    /// Return the next half match for a fallible search if one exists, and
    /// advance to the next position.
    ///
    /// This is like `advance_half`, except it permits callers to handle errors
    /// during iteration.
    #[inline]
    pub fn try_advance_half<F>(
        &mut self,
        mut finder: F,
    ) -> Result<Option<HalfMatch>, MatchError>
    where
        F: FnMut(&Input<'_>) -> Result<Option<HalfMatch>, MatchError>,
    {
        let mut m = match finder(&self.input)? {
            None => return Ok(None),
            Some(m) => m,
        };
        if Some(m.offset()) == self.last_match_end {
            m = match self.handle_overlapping_empty_half_match(m, finder)? {
                None => return Ok(None),
                Some(m) => m,
            };
        }
        self.input.set_start(m.offset());
        self.last_match_end = Some(m.offset());
        Ok(Some(m))
    }

    /// Return the next match for a fallible search if one exists, and advance
    /// to the next position.
    ///
    /// This is like `advance`, except it permits callers to handle errors
    /// during iteration.
    #[inline]
    pub fn try_advance<F>(
        &mut self,
        mut finder: F,
    ) -> Result<Option<Match>, MatchError>
    where
        F: FnMut(&Input<'_>) -> Result<Option<Match>, MatchError>,
    {
        let mut m = match finder(&self.input)? {
            None => return Ok(None),
            Some(m) => m,
        };
        if m.is_empty() && Some(m.end()) == self.last_match_end {
            m = match self.handle_overlapping_empty_match(m, finder)? {
                None => return Ok(None),
                Some(m) => m,
            };
        }
        self.input.set_start(m.end());
        self.last_match_end = Some(m.end());
        Ok(Some(m))
    }

    /// Given a closure that executes a single search, return an iterator over
    /// all successive non-overlapping half matches.
    ///
    /// The iterator returned yields result values. If the underlying regex
    /// engine is configured to never return an error, consider calling
    /// [`TryHalfMatchesIter::infallible`] to convert errors into panics.
    ///
    /// # Example
    ///
    /// This example shows how to use a `Searcher` to create a proper
    /// iterator over half matches.
    ///
    /// ```
    /// use regex_automata::{
    ///     hybrid::dfa::DFA,
    ///     util::iter::Searcher,
    ///     HalfMatch, Input,
    /// };
    ///
    /// let re = DFA::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}")?;
    /// let mut cache = re.create_cache();
    ///
    /// let input = Input::new("2010-03-14 2016-10-08 2020-10-22");
    /// let mut it = Searcher::new(input).into_half_matches_iter(|input| {
    ///     re.try_search_fwd(&mut cache, input)
    /// });
    ///
    /// let expected = Some(Ok(HalfMatch::must(0, 10)));
    /// assert_eq!(expected, it.next());
    ///
    /// let expected = Some(Ok(HalfMatch::must(0, 21)));
    /// assert_eq!(expected, it.next());
    ///
    /// let expected = Some(Ok(HalfMatch::must(0, 32)));
    /// assert_eq!(expected, it.next());
    ///
    /// let expected = None;
    /// assert_eq!(expected, it.next());
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    pub fn into_half_matches_iter<F>(
        self,
        finder: F,
    ) -> TryHalfMatchesIter<'h, F>
    where
        F: FnMut(&Input<'_>) -> Result<Option<HalfMatch>, MatchError>,
    {
        TryHalfMatchesIter { it: self, finder }
    }

    /// Given a closure that executes a single search, return an iterator over
    /// all successive non-overlapping matches.
    ///
    /// The iterator returned yields result values. If the underlying regex
    /// engine is configured to never return an error, consider calling
    /// [`TryMatchesIter::infallible`] to convert errors into panics.
    ///
    /// # Example
    ///
    /// This example shows how to use a `Searcher` to create a proper
    /// iterator over matches.
    ///
    /// ```
    /// use regex_automata::{
    ///     hybrid::regex::Regex,
    ///     util::iter::Searcher,
    ///     Match, Input,
    /// };
    ///
    /// let re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}")?;
    /// let mut cache = re.create_cache();
    ///
    /// let input = Input::new("2010-03-14 2016-10-08 2020-10-22");
    /// let mut it = Searcher::new(input).into_matches_iter(|input| {
    ///     re.try_search(&mut cache, input)
    /// });
    ///
    /// let expected = Some(Ok(Match::must(0, 0..10)));
    /// assert_eq!(expected, it.next());
    ///
    /// let expected = Some(Ok(Match::must(0, 11..21)));
    /// assert_eq!(expected, it.next());
    ///
    /// let expected = Some(Ok(Match::must(0, 22..32)));
    /// assert_eq!(expected, it.next());
    ///
    /// let expected = None;
    /// assert_eq!(expected, it.next());
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    pub fn into_matches_iter<F>(self, finder: F) -> TryMatchesIter<'h, F>
    where
        F: FnMut(&Input<'_>) -> Result<Option<Match>, MatchError>,
    {
        TryMatchesIter { it: self, finder }
    }

    /// Given a closure that executes a single search, return an iterator over
    /// all successive non-overlapping `Captures` values.
    ///
    /// The iterator returned yields result values. If the underlying regex
    /// engine is configured to never return an error, consider calling
    /// [`TryCapturesIter::infallible`] to convert errors into panics.
    ///
    /// Unlike the other iterator constructors, this accepts an initial
    /// `Captures` value. This `Captures` value is reused for each search, and
    /// the iterator implementation clones it before returning it. The caller
    /// must provide this value because the iterator is purposely ignorant
    /// of the underlying regex engine and thus doesn't know how to create
    /// one itself. More to the point, a `Captures` value itself has a few
    /// different constructors, which change which kind of information is
    /// available to query in exchange for search performance.
    ///
    /// # Example
    ///
    /// This example shows how to use a `Searcher` to create a proper iterator
    /// over `Captures` values, which provides access to all capturing group
    /// spans for each match.
    ///
    /// ```
    /// use regex_automata::{
    ///     nfa::thompson::pikevm::PikeVM,
    ///     util::iter::Searcher,
    ///     Input,
    /// };
    ///
    /// let re = PikeVM::new(
    ///     r"(?P<y>[0-9]{4})-(?P<m>[0-9]{2})-(?P<d>[0-9]{2})",
    /// )?;
    /// let (mut cache, caps) = (re.create_cache(), re.create_captures());
    ///
    /// let haystack = "2010-03-14 2016-10-08 2020-10-22";
    /// let input = Input::new(haystack);
    /// let mut it = Searcher::new(input)
    ///     .into_captures_iter(caps, |input, caps| {
    ///         re.search(&mut cache, input, caps);
    ///         Ok(())
    ///     });
    ///
    /// let got = it.next().expect("first date")?;
    /// let year = got.get_group_by_name("y").expect("must match");
    /// assert_eq!("2010", &haystack[year]);
    ///
    /// let got = it.next().expect("second date")?;
    /// let month = got.get_group_by_name("m").expect("must match");
    /// assert_eq!("10", &haystack[month]);
    ///
    /// let got = it.next().expect("third date")?;
    /// let day = got.get_group_by_name("d").expect("must match");
    /// assert_eq!("22", &haystack[day]);
    ///
    /// assert!(it.next().is_none());
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "alloc")]
    #[inline]
    pub fn into_captures_iter<F>(
        self,
        caps: Captures,
        finder: F,
    ) -> TryCapturesIter<'h, F>
    where
        F: FnMut(&Input<'_>, &mut Captures) -> Result<(), MatchError>,
    {
        TryCapturesIter { it: self, caps, finder }
    }

    /// Handles the special case of a match that begins where the previous
    /// match ended. Without this special handling, it'd be possible to get
    /// stuck where an empty match never results in forward progress. This
    /// also makes it more consistent with how presiding general purpose regex
    /// engines work.
    #[cold]
    #[inline(never)]
    fn handle_overlapping_empty_half_match<F>(
        &mut self,
        _: HalfMatch,
        mut finder: F,
    ) -> Result<Option<HalfMatch>, MatchError>
    where
        F: FnMut(&Input<'_>) -> Result<Option<HalfMatch>, MatchError>,
    {
        // Since we are only here when 'm.offset()' matches the offset of the
        // last match, it follows that this must have been an empty match.
        // Since we both need to make progress *and* prevent overlapping
        // matches, we discard this match and advance the search by 1.
        //
        // Note that this may start a search in the middle of a codepoint. The
        // regex engines themselves are expected to deal with that and not
        // report any matches within a codepoint if they are configured in
        // UTF-8 mode.
        self.input.set_start(self.input.start().checked_add(1).unwrap());
        finder(&self.input)
    }

    /// Handles the special case of an empty match by ensuring that 1) the
    /// iterator always advances and 2) empty matches never overlap with other
    /// matches.
    ///
    /// (1) is necessary because we principally make progress by setting the
    /// starting location of the next search to the ending location of the last
    /// match. But if a match is empty, then this results in a search that does
    /// not advance and thus does not terminate.
    ///
    /// (2) is not strictly necessary, but makes intuitive sense and matches
    /// the presiding behavior of most general purpose regex engines. The
    /// "intuitive sense" here is that we want to report NON-overlapping
    /// matches. So for example, given the regex 'a|(?:)' against the haystack
    /// 'a', without the special handling, you'd get the matches [0, 1) and [1,
    /// 1), where the latter overlaps with the end bounds of the former.
    ///
    /// Note that we mark this cold and forcefully prevent inlining because
    /// handling empty matches like this is extremely rare and does require
    /// quite a bit of code, comparatively. Keeping this code out of the main
    /// iterator function keeps it smaller and more amenable to inlining
    /// itself.
    #[cold]
    #[inline(never)]
    fn handle_overlapping_empty_match<F>(
        &mut self,
        m: Match,
        mut finder: F,
    ) -> Result<Option<Match>, MatchError>
    where
        F: FnMut(&Input<'_>) -> Result<Option<Match>, MatchError>,
    {
        assert!(m.is_empty());
        self.input.set_start(self.input.start().checked_add(1).unwrap());
        finder(&self.input)
    }
}

/// An iterator over all non-overlapping half matches for a fallible search.
///
/// The iterator yields a `Result<HalfMatch, MatchError>` value until no more
/// matches could be found.
///
/// The type parameters are as follows:
///
/// * `F` represents the type of a closure that executes the search.
///
/// The lifetime parameters come from the [`Input`] type:
///
/// * `'h` is the lifetime of the underlying haystack.
///
/// When possible, prefer the iterators defined on the regex engine you're
/// using. This tries to abstract over the regex engine and is thus a bit more
/// unwieldy to use.
///
/// This iterator is created by [`Searcher::into_half_matches_iter`].
pub struct TryHalfMatchesIter<'h, F> {
    it: Searcher<'h>,
    finder: F,
}

impl<'h, F> TryHalfMatchesIter<'h, F> {
    /// Return an infallible version of this iterator.
    ///
    /// Any item yielded that corresponds to an error results in a panic. This
    /// is useful if your underlying regex engine is configured in a way that
    /// it is guaranteed to never return an error.
    pub fn infallible(self) -> HalfMatchesIter<'h, F> {
        HalfMatchesIter(self)
    }

    /// Returns the current `Input` used by this iterator.
    ///
    /// The `Input` returned is generally equivalent to the one used to
    /// construct this iterator, but its start position may be different to
    /// reflect the start of the next search to be executed.
    pub fn input<'i>(&'i self) -> &'i Input<'h> {
        self.it.input()
    }
}

impl<'h, F> Iterator for TryHalfMatchesIter<'h, F>
where
    F: FnMut(&Input<'_>) -> Result<Option<HalfMatch>, MatchError>,
{
    type Item = Result<HalfMatch, MatchError>;

    #[inline]
    fn next(&mut self) -> Option<Result<HalfMatch, MatchError>> {
        self.it.try_advance_half(&mut self.finder).transpose()
    }
}

impl<'h, F> core::fmt::Debug for TryHalfMatchesIter<'h, F> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("TryHalfMatchesIter")
            .field("it", &self.it)
            .field("finder", &"<closure>")
            .finish()
    }
}

/// An iterator over all non-overlapping half matches for an infallible search.
///
/// The iterator yields a [`HalfMatch`] value until no more matches could be
/// found.
///
/// The type parameters are as follows:
///
/// * `F` represents the type of a closure that executes the search.
///
/// The lifetime parameters come from the [`Input`] type:
///
/// * `'h` is the lifetime of the underlying haystack.
///
/// When possible, prefer the iterators defined on the regex engine you're
/// using. This tries to abstract over the regex engine and is thus a bit more
/// unwieldy to use.
///
/// This iterator is created by [`Searcher::into_half_matches_iter`] and
/// then calling [`TryHalfMatchesIter::infallible`].
#[derive(Debug)]
pub struct HalfMatchesIter<'h, F>(TryHalfMatchesIter<'h, F>);

impl<'h, F> HalfMatchesIter<'h, F> {
    /// Returns the current `Input` used by this iterator.
    ///
    /// The `Input` returned is generally equivalent to the one used to
    /// construct this iterator, but its start position may be different to
    /// reflect the start of the next search to be executed.
    pub fn input<'i>(&'i self) -> &'i Input<'h> {
        self.0.it.input()
    }
}

impl<'h, F> Iterator for HalfMatchesIter<'h, F>
where
    F: FnMut(&Input<'_>) -> Result<Option<HalfMatch>, MatchError>,
{
    type Item = HalfMatch;

    #[inline]
    fn next(&mut self) -> Option<HalfMatch> {
        match self.0.next()? {
            Ok(m) => Some(m),
            Err(err) => panic!(
                "unexpected regex half find error: {err}\n\
                 to handle find errors, use 'try' or 'search' methods",
            ),
        }
    }
}

/// An iterator over all non-overlapping matches for a fallible search.
///
/// The iterator yields a `Result<Match, MatchError>` value until no more
/// matches could be found.
///
/// The type parameters are as follows:
///
/// * `F` represents the type of a closure that executes the search.
///
/// The lifetime parameters come from the [`Input`] type:
///
/// * `'h` is the lifetime of the underlying haystack.
///
/// When possible, prefer the iterators defined on the regex engine you're
/// using. This tries to abstract over the regex engine and is thus a bit more
/// unwieldy to use.
///
/// This iterator is created by [`Searcher::into_matches_iter`].
pub struct TryMatchesIter<'h, F> {
    it: Searcher<'h>,
    finder: F,
}

impl<'h, F> TryMatchesIter<'h, F> {
    /// Return an infallible version of this iterator.
    ///
    /// Any item yielded that corresponds to an error results in a panic. This
    /// is useful if your underlying regex engine is configured in a way that
    /// it is guaranteed to never return an error.
    pub fn infallible(self) -> MatchesIter<'h, F> {
        MatchesIter(self)
    }

    /// Returns the current `Input` used by this iterator.
    ///
    /// The `Input` returned is generally equivalent to the one used to
    /// construct this iterator, but its start position may be different to
    /// reflect the start of the next search to be executed.
    pub fn input<'i>(&'i self) -> &'i Input<'h> {
        self.it.input()
    }
}

impl<'h, F> Iterator for TryMatchesIter<'h, F>
where
    F: FnMut(&Input<'_>) -> Result<Option<Match>, MatchError>,
{
    type Item = Result<Match, MatchError>;

    #[inline]
    fn next(&mut self) -> Option<Result<Match, MatchError>> {
        self.it.try_advance(&mut self.finder).transpose()
    }
}

impl<'h, F> core::fmt::Debug for TryMatchesIter<'h, F> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("TryMatchesIter")
            .field("it", &self.it)
            .field("finder", &"<closure>")
            .finish()
    }
}

/// An iterator over all non-overlapping matches for an infallible search.
///
/// The iterator yields a [`Match`] value until no more matches could be found.
///
/// The type parameters are as follows:
///
/// * `F` represents the type of a closure that executes the search.
///
/// The lifetime parameters come from the [`Input`] type:
///
/// * `'h` is the lifetime of the underlying haystack.
///
/// When possible, prefer the iterators defined on the regex engine you're
/// using. This tries to abstract over the regex engine and is thus a bit more
/// unwieldy to use.
///
/// This iterator is created by [`Searcher::into_matches_iter`] and
/// then calling [`TryMatchesIter::infallible`].
#[derive(Debug)]
pub struct MatchesIter<'h, F>(TryMatchesIter<'h, F>);

impl<'h, F> MatchesIter<'h, F> {
    /// Returns the current `Input` used by this iterator.
    ///
    /// The `Input` returned is generally equivalent to the one used to
    /// construct this iterator, but its start position may be different to
    /// reflect the start of the next search to be executed.
    pub fn input<'i>(&'i self) -> &'i Input<'h> {
        self.0.it.input()
    }
}

impl<'h, F> Iterator for MatchesIter<'h, F>
where
    F: FnMut(&Input<'_>) -> Result<Option<Match>, MatchError>,
{
    type Item = Match;

    #[inline]
    fn next(&mut self) -> Option<Match> {
        match self.0.next()? {
            Ok(m) => Some(m),
            Err(err) => panic!(
                "unexpected regex find error: {err}\n\
                 to handle find errors, use 'try' or 'search' methods",
            ),
        }
    }
}

/// An iterator over all non-overlapping captures for a fallible search.
///
/// The iterator yields a `Result<Captures, MatchError>` value until no more
/// matches could be found.
///
/// The type parameters are as follows:
///
/// * `F` represents the type of a closure that executes the search.
///
/// The lifetime parameters come from the [`Input`] type:
///
/// * `'h` is the lifetime of the underlying haystack.
///
/// When possible, prefer the iterators defined on the regex engine you're
/// using. This tries to abstract over the regex engine and is thus a bit more
/// unwieldy to use.
///
/// This iterator is created by [`Searcher::into_captures_iter`].
#[cfg(feature = "alloc")]
pub struct TryCapturesIter<'h, F> {
    it: Searcher<'h>,
    caps: Captures,
    finder: F,
}

#[cfg(feature = "alloc")]
impl<'h, F> TryCapturesIter<'h, F> {
    /// Return an infallible version of this iterator.
    ///
    /// Any item yielded that corresponds to an error results in a panic. This
    /// is useful if your underlying regex engine is configured in a way that
    /// it is guaranteed to never return an error.
    pub fn infallible(self) -> CapturesIter<'h, F> {
        CapturesIter(self)
    }
}

#[cfg(feature = "alloc")]
impl<'h, F> Iterator for TryCapturesIter<'h, F>
where
    F: FnMut(&Input<'_>, &mut Captures) -> Result<(), MatchError>,
{
    type Item = Result<Captures, MatchError>;

    #[inline]
    fn next(&mut self) -> Option<Result<Captures, MatchError>> {
        let TryCapturesIter { ref mut it, ref mut caps, ref mut finder } =
            *self;
        let result = it
            .try_advance(|input| {
                (finder)(input, caps)?;
                Ok(caps.get_match())
            })
            .transpose()?;
        match result {
            Ok(_) => Some(Ok(caps.clone())),
            Err(err) => Some(Err(err)),
        }
    }
}

#[cfg(feature = "alloc")]
impl<'h, F> core::fmt::Debug for TryCapturesIter<'h, F> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("TryCapturesIter")
            .field("it", &self.it)
            .field("caps", &self.caps)
            .field("finder", &"<closure>")
            .finish()
    }
}

/// An iterator over all non-overlapping captures for an infallible search.
///
/// The iterator yields a [`Captures`] value until no more matches could be
/// found.
///
/// The type parameters are as follows:
///
/// * `F` represents the type of a closure that executes the search.
///
/// The lifetime parameters come from the [`Input`] type:
///
/// * `'h` is the lifetime of the underlying haystack.
///
/// When possible, prefer the iterators defined on the regex engine you're
/// using. This tries to abstract over the regex engine and is thus a bit more
/// unwieldy to use.
///
/// This iterator is created by [`Searcher::into_captures_iter`] and then
/// calling [`TryCapturesIter::infallible`].
#[cfg(feature = "alloc")]
#[derive(Debug)]
pub struct CapturesIter<'h, F>(TryCapturesIter<'h, F>);

#[cfg(feature = "alloc")]
impl<'h, F> Iterator for CapturesIter<'h, F>
where
    F: FnMut(&Input<'_>, &mut Captures) -> Result<(), MatchError>,
{
    type Item = Captures;

    #[inline]
    fn next(&mut self) -> Option<Captures> {
        match self.0.next()? {
            Ok(m) => Some(m),
            Err(err) => panic!(
                "unexpected regex captures error: {err}\n\
                 to handle find errors, use 'try' or 'search' methods",
            ),
        }
    }
}