regex_automata/util/prefilter/

mod.rs

/*!
Defines a prefilter for accelerating regex searches.

A prefilter can be created by building a [`Prefilter`] value.

A prefilter represents one of the most important optimizations available for
accelerating regex searches. The idea of a prefilter is to very quickly find
candidate locations in a haystack where a regex _could_ match. Once a candidate
is found, it is then intended for the regex engine to run at that position to
determine whether the candidate is a match or a false positive.

In the aforementioned description of the prefilter optimization also lay its
demise. Namely, if a prefilter has a high false positive rate and it produces
lots of candidates, then a prefilter can overall make a regex search slower.
It can run more slowly because more time is spent ping-ponging between the
prefilter search and the regex engine attempting to confirm each candidate as
a match. This ping-ponging has overhead that adds up, and is exacerbated by
a high false positive rate.

Nevertheless, the optimization is still generally worth performing in most
cases. Particularly given just how much throughput can be improved. (It is not
uncommon for prefilter optimizations to improve throughput by one or two orders
of magnitude.)

Typically a prefilter is used to find occurrences of literal prefixes from a
regex pattern, but this isn't required. A prefilter can be used to look for
suffixes or even inner literals.

Note that as of now, prefilters throw away information about which pattern
each literal comes from. In other words, when a prefilter finds a match,
there's no way to know which pattern (or patterns) it came from. Therefore,
in order to confirm a match, you'll have to check all of the patterns by
running the full regex engine.
*/

mod aho_corasick;
mod byteset;
mod memchr;
mod memmem;
mod teddy;

use core::{
    borrow::Borrow,
    fmt::Debug,
    panic::{RefUnwindSafe, UnwindSafe},
};

#[cfg(feature = "alloc")]
use alloc::sync::Arc;

#[cfg(feature = "syntax")]
use regex_syntax::hir::{literal, Hir};

use crate::util::search::{MatchKind, Span};

pub(crate) use crate::util::prefilter::{
    aho_corasick::AhoCorasick,
    byteset::ByteSet,
    memchr::{Memchr, Memchr2, Memchr3},
    memmem::Memmem,
    teddy::Teddy,
};

/// A prefilter for accelerating regex searches.
///
/// If you already have your literals that you want to search with,
/// then the vanilla [`Prefilter::new`] constructor is for you. But
/// if you have an [`Hir`] value from the `regex-syntax` crate, then
/// [`Prefilter::from_hir_prefix`] might be more convenient. Namely, it uses
/// the [`regex-syntax::hir::literal`](regex_syntax::hir::literal) module to
/// extract literal prefixes for you, optimize them and then select and build a
/// prefilter matcher.
///
/// A prefilter must have **zero false negatives**. However, by its very
/// nature, it may produce false positives. That is, a prefilter will never
/// skip over a position in the haystack that corresponds to a match of the
/// original regex pattern, but it *may* produce a match for a position
/// in the haystack that does *not* correspond to a match of the original
/// regex pattern. If you use either the [`Prefilter::from_hir_prefix`] or
/// [`Prefilter::from_hirs_prefix`] constructors, then this guarantee is
/// upheld for you automatically. This guarantee is not preserved if you use
/// [`Prefilter::new`] though, since it is up to the caller to provide correct
/// literal strings with respect to the original regex pattern.
///
/// # Cloning
///
/// It is an API guarantee that cloning a prefilter is cheap. That is, cloning
/// it will not duplicate whatever heap memory is used to represent the
/// underlying matcher.
///
/// # Example
///
/// This example shows how to attach a `Prefilter` to the
/// [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM) in order to accelerate
/// searches.
///
/// ```
/// use regex_automata::{
///     nfa::thompson::pikevm::PikeVM,
///     util::prefilter::Prefilter,
///     Match, MatchKind,
/// };
///
/// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["Bruce "])
///     .expect("a prefilter");
/// let re = PikeVM::builder()
///     .configure(PikeVM::config().prefilter(Some(pre)))
///     .build(r"Bruce \w+")?;
/// let mut cache = re.create_cache();
/// assert_eq!(
///     Some(Match::must(0, 6..23)),
///     re.find(&mut cache, "Hello Bruce Springsteen!"),
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// But note that if you get your prefilter incorrect, it could lead to an
/// incorrect result!
///
/// ```
/// use regex_automata::{
///     nfa::thompson::pikevm::PikeVM,
///     util::prefilter::Prefilter,
///     Match, MatchKind,
/// };
///
/// // This prefilter is wrong!
/// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["Patti "])
///     .expect("a prefilter");
/// let re = PikeVM::builder()
///     .configure(PikeVM::config().prefilter(Some(pre)))
///     .build(r"Bruce \w+")?;
/// let mut cache = re.create_cache();
/// // We find no match even though the regex does match.
/// assert_eq!(
///     None,
///     re.find(&mut cache, "Hello Bruce Springsteen!"),
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(Clone, Debug)]
pub struct Prefilter {
    #[cfg(not(feature = "alloc"))]
    _unused: (),
    #[cfg(feature = "alloc")]
    pre: Arc<dyn PrefilterI>,
    #[cfg(feature = "alloc")]
    is_fast: bool,
    #[cfg(feature = "alloc")]
    max_needle_len: usize,
}

impl Prefilter {
    /// Create a new prefilter from a sequence of needles and a corresponding
    /// match semantics.
    ///
    /// This may return `None` for a variety of reasons, for example, if
    /// a suitable prefilter could not be constructed. That might occur
    /// if they are unavailable (e.g., the `perf-literal-substring` and
    /// `perf-literal-multisubstring` features aren't enabled), or it might
    /// occur because of heuristics or other artifacts of how the prefilter
    /// works.
    ///
    /// Note that if you have an [`Hir`] expression, it may be more convenient
    /// to use [`Prefilter::from_hir_prefix`]. It will automatically handle the
    /// task of extracting prefix literals for you.
    ///
    /// # Example
    ///
    /// This example shows how match semantics can impact the matching
    /// algorithm used by the prefilter. For this reason, it is important to
    /// ensure that the match semantics given here are consistent with the
    /// match semantics intended for the regular expression that the literals
    /// were extracted from.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hay = "Hello samwise";
    ///
    /// // With leftmost-first, we find 'samwise' here because it comes
    /// // before 'sam' in the sequence we give it..
    /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["samwise", "sam"])
    ///     .expect("a prefilter");
    /// assert_eq!(
    ///     Some(Span::from(6..13)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    /// // Still with leftmost-first but with the literals reverse, now 'sam'
    /// // will match instead!
    /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["sam", "samwise"])
    ///     .expect("a prefilter");
    /// assert_eq!(
    ///     Some(Span::from(6..9)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn new<B: AsRef<[u8]>>(
        kind: MatchKind,
        needles: &[B],
    ) -> Option<Prefilter> {
        Choice::new(kind, needles).and_then(|choice| {
            let max_needle_len =
                needles.iter().map(|b| b.as_ref().len()).max().unwrap_or(0);
            Prefilter::from_choice(choice, max_needle_len)
        })
    }

    /// This turns a prefilter selection into a `Prefilter`. That is, in turns
    /// the enum given into a trait object.
    fn from_choice(
        choice: Choice,
        max_needle_len: usize,
    ) -> Option<Prefilter> {
        #[cfg(not(feature = "alloc"))]
        {
            None
        }
        #[cfg(feature = "alloc")]
        {
            let pre: Arc<dyn PrefilterI> = match choice {
                Choice::Memchr(p) => Arc::new(p),
                Choice::Memchr2(p) => Arc::new(p),
                Choice::Memchr3(p) => Arc::new(p),
                Choice::Memmem(p) => Arc::new(p),
                Choice::Teddy(p) => Arc::new(p),
                Choice::ByteSet(p) => Arc::new(p),
                Choice::AhoCorasick(p) => Arc::new(p),
            };
            let is_fast = pre.is_fast();
            Some(Prefilter { pre, is_fast, max_needle_len })
        }
    }

    /// This attempts to extract prefixes from the given `Hir` expression for
    /// the given match semantics, and if possible, builds a prefilter for
    /// them.
    ///
    /// # Example
    ///
    /// This example shows how to build a prefilter directly from an [`Hir`]
    /// expression, and use to find an occurrence of a prefix from the regex
    /// pattern.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hir = syntax::parse(r"(Bruce|Patti) \w+")?;
    /// let pre = Prefilter::from_hir_prefix(MatchKind::LeftmostFirst, &hir)
    ///     .expect("a prefilter");
    /// let hay = "Hello Patti Scialfa!";
    /// assert_eq!(
    ///     Some(Span::from(6..12)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "syntax")]
    pub fn from_hir_prefix(kind: MatchKind, hir: &Hir) -> Option<Prefilter> {
        Prefilter::from_hirs_prefix(kind, &[hir])
    }

    /// This attempts to extract prefixes from the given `Hir` expressions for
    /// the given match semantics, and if possible, builds a prefilter for
    /// them.
    ///
    /// Note that as of now, prefilters throw away information about which
    /// pattern each literal comes from. In other words, when a prefilter finds
    /// a match, there's no way to know which pattern (or patterns) it came
    /// from. Therefore, in order to confirm a match, you'll have to check all
    /// of the patterns by running the full regex engine.
    ///
    /// # Example
    ///
    /// This example shows how to build a prefilter directly from multiple
    /// `Hir` expressions expression, and use it to find an occurrence of a
    /// prefix from the regex patterns.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hirs = syntax::parse_many(&[
    ///     r"(Bruce|Patti) \w+",
    ///     r"Mrs?\. Doubtfire",
    /// ])?;
    /// let pre = Prefilter::from_hirs_prefix(MatchKind::LeftmostFirst, &hirs)
    ///     .expect("a prefilter");
    /// let hay = "Hello Mrs. Doubtfire";
    /// assert_eq!(
    ///     Some(Span::from(6..20)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "syntax")]
    pub fn from_hirs_prefix<H: Borrow<Hir>>(
        kind: MatchKind,
        hirs: &[H],
    ) -> Option<Prefilter> {
        prefixes(kind, hirs)
            .literals()
            .and_then(|lits| Prefilter::new(kind, lits))
    }

    /// Run this prefilter on `haystack[span.start..end]` and return a matching
    /// span if one exists.
    ///
    /// The span returned is guaranteed to have a start position greater than
    /// or equal to the one given, and an end position less than or equal to
    /// the one given.
    ///
    /// # Example
    ///
    /// This example shows how to build a prefilter directly from an [`Hir`]
    /// expression, and use it to find an occurrence of a prefix from the regex
    /// pattern.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hir = syntax::parse(r"Bruce \w+")?;
    /// let pre = Prefilter::from_hir_prefix(MatchKind::LeftmostFirst, &hir)
    ///     .expect("a prefilter");
    /// let hay = "Hello Bruce Springsteen!";
    /// assert_eq!(
    ///     Some(Span::from(6..12)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    pub fn find(&self, haystack: &[u8], span: Span) -> Option<Span> {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.pre.find(haystack, span)
        }
    }

    /// Returns the span of a prefix of `haystack[span.start..span.end]` if
    /// the prefilter matches.
    ///
    /// The span returned is guaranteed to have a start position equivalent to
    /// the one given, and an end position less than or equal to the one given.
    ///
    /// # Example
    ///
    /// This example shows how to build a prefilter directly from an [`Hir`]
    /// expression, and use it to find an occurrence of a prefix from the regex
    /// pattern that begins at the start of a haystack only.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hir = syntax::parse(r"Bruce \w+")?;
    /// let pre = Prefilter::from_hir_prefix(MatchKind::LeftmostFirst, &hir)
    ///     .expect("a prefilter");
    /// let hay = "Hello Bruce Springsteen!";
    /// // Nothing is found here because 'Bruce' does
    /// // not occur at the beginning of our search.
    /// assert_eq!(
    ///     None,
    ///     pre.prefix(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    /// // But if we change where we start the search
    /// // to begin where 'Bruce ' begins, then a
    /// // match will be found.
    /// assert_eq!(
    ///     Some(Span::from(6..12)),
    ///     pre.prefix(hay.as_bytes(), Span::from(6..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    pub fn prefix(&self, haystack: &[u8], span: Span) -> Option<Span> {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.pre.prefix(haystack, span)
        }
    }

    /// Returns the heap memory, in bytes, used by the underlying prefilter.
    #[inline]
    pub fn memory_usage(&self) -> usize {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.pre.memory_usage()
        }
    }

    /// Return the length of the longest needle
    /// in this Prefilter
    #[inline]
    pub fn max_needle_len(&self) -> usize {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.max_needle_len
        }
    }

    /// Implementations might return true here if they believe themselves to
    /// be "fast." The concept of "fast" is deliberately left vague, but in
    /// practice this usually corresponds to whether it's believed that SIMD
    /// will be used.
    ///
    /// Why do we care about this? Well, some prefilter tricks tend to come
    /// with their own bits of overhead, and so might only make sense if we
    /// know that a scan will be *much* faster than the regex engine itself.
    /// Otherwise, the trick may not be worth doing. Whether something is
    /// "much" faster than the regex engine generally boils down to whether
    /// SIMD is used. (But not always. Even a SIMD matcher with a high false
    /// positive rate can become quite slow.)
    ///
    /// Even if this returns true, it is still possible for the prefilter to
    /// be "slow." Remember, prefilters are just heuristics. We can't really
    /// *know* a prefilter will be fast without actually trying the prefilter.
    /// (Which of course we cannot afford to do.)
    #[inline]
    pub fn is_fast(&self) -> bool {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.is_fast
        }
    }
}

/// A trait for abstracting over prefilters. Basically, a prefilter is
/// something that do an unanchored *and* an anchored search in a haystack
/// within a given span.
///
/// This exists pretty much only so that we can use prefilters as a trait
/// object (which is what `Prefilter` is). If we ever move off of trait objects
/// and to an enum, then it's likely this trait could be removed.
pub(crate) trait PrefilterI:
    Debug + Send + Sync + RefUnwindSafe + UnwindSafe + 'static
{
    /// Return the name of this prefilter.
    fn name(&self) -> &'static str;

    /// Run this prefilter on `haystack[span.start..end]` and return a matching
    /// span if one exists.
    ///
    /// The span returned is guaranteed to have a start position greater than
    /// or equal to the one given, and an end position less than or equal to
    /// the one given.
    fn find(&self, haystack: &[u8], span: Span) -> Option<Span>;

    /// Returns the span of a prefix of `haystack[span.start..span.end]` if
    /// the prefilter matches.
    ///
    /// The span returned is guaranteed to have a start position equivalent to
    /// the one given, and an end position less than or equal to the one given.
    fn prefix(&self, haystack: &[u8], span: Span) -> Option<Span>;

    /// Returns the heap memory, in bytes, used by the underlying prefilter.
    fn memory_usage(&self) -> usize;

    /// Implementations might return true here if they believe themselves to
    /// be "fast." See [`Prefilter::is_fast`] for more details.
    fn is_fast(&self) -> bool;
}

#[cfg(feature = "alloc")]
impl<P: PrefilterI + ?Sized> PrefilterI for Arc<P> {
    fn name(&self) -> &'static str {
        (**self).name()
    }

    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn find(&self, haystack: &[u8], span: Span) -> Option<Span> {
        (**self).find(haystack, span)
    }

    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn prefix(&self, haystack: &[u8], span: Span) -> Option<Span> {
        (**self).prefix(haystack, span)
    }

    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn memory_usage(&self) -> usize {
        (**self).memory_usage()
    }

    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn is_fast(&self) -> bool {
        (&**self).is_fast()
    }
}

/// A type that encapsulates the selection of a prefilter algorithm from a
/// sequence of needles.
///
/// The existence of this type is a little tricky, because we don't (currently)
/// use it for performing a search. Instead, we really only consume it by
/// converting the underlying prefilter into a trait object, whether that be
/// `dyn PrefilterI` or `dyn Strategy` (for the meta regex engine). In order
/// to avoid re-copying the prefilter selection logic, we isolate it here, and
/// then force anything downstream that wants to convert it to a trait object
/// to do trivial case analysis on it.
///
/// One wonders whether we *should* use an enum instead of a trait object.
/// At time of writing, I chose trait objects based on instinct because 1) I
/// knew I wasn't going to inline anything and 2) there would potentially be
/// many different choices. However, as of time of writing, I haven't actually
/// compared the trait object approach to the enum approach. That probably
/// should be litigated, but I ran out of steam.
///
/// Note that if the `alloc` feature is disabled, then values of this type
/// are (and should) never be constructed. Also, in practice, for any of the
/// prefilters to be selected, you'll need at least one of the `perf-literal-*`
/// features enabled.
#[derive(Clone, Debug)]
pub(crate) enum Choice {
    Memchr(Memchr),
    Memchr2(Memchr2),
    Memchr3(Memchr3),
    Memmem(Memmem),
    Teddy(Teddy),
    ByteSet(ByteSet),
    AhoCorasick(AhoCorasick),
}

impl Choice {
    /// Select what is believed to be the best prefilter algorithm for the
    /// match semantics and sequence of needles given.
    ///
    /// This selection algorithm uses the needles as given without any
    /// modification. For example, if `[bar]` is given, then this doesn't
    /// try to select `memchr` for `b`. Instead, it would select `memmem`
    /// for `bar`. If callers would want `memchr` selected for `[bar]`, then
    /// callers should massages the literals themselves. That is, callers are
    /// responsible for heuristics surrounding which sequence of literals is
    /// best.
    ///
    /// What this selection algorithm does is attempt to use the fastest
    /// prefilter that works for the literals given. So if `[a, b]`, is given,
    /// then `memchr2` is selected.
    ///
    /// Of course, which prefilter is selected is also subject to what
    /// is available. For example, if `alloc` isn't enabled, then
    /// that limits which prefilters can be selected. Similarly, if
    /// `perf-literal-substring` isn't enabled, then nothing from the `memchr`
    /// crate can be returned.
    pub(crate) fn new<B: AsRef<[u8]>>(
        kind: MatchKind,
        needles: &[B],
    ) -> Option<Choice> {
        // An empty set means the regex matches nothing, so no sense in
        // building a prefilter.
        if needles.len() == 0 {
            debug!("prefilter building failed: found empty set of literals");
            return None;
        }
        // If the regex can match the empty string, then the prefilter
        // will by definition match at every position. This is obviously
        // completely ineffective.
        if needles.iter().any(|n| n.as_ref().is_empty()) {
            debug!("prefilter building failed: literals match empty string");
            return None;
        }
        // BREADCRUMBS: Perhaps the literal optimizer should special case
        // sequences of length two or three if the leading bytes of each are
        // "rare"? Or perhaps, if there are two or three total possible leading
        // bytes, regardless of the number of literals, and all are rare...
        // Then well, perhaps we should use memchr2 or memchr3 in those cases?
        if let Some(pre) = Memchr::new(kind, needles) {
            debug!("prefilter built: memchr");
            return Some(Choice::Memchr(pre));
        }
        if let Some(pre) = Memchr2::new(kind, needles) {
            debug!("prefilter built: memchr2");
            return Some(Choice::Memchr2(pre));
        }
        if let Some(pre) = Memchr3::new(kind, needles) {
            debug!("prefilter built: memchr3");
            return Some(Choice::Memchr3(pre));
        }
        if let Some(pre) = Memmem::new(kind, needles) {
            debug!("prefilter built: memmem");
            return Some(Choice::Memmem(pre));
        }
        if let Some(pre) = Teddy::new(kind, needles) {
            debug!("prefilter built: teddy");
            return Some(Choice::Teddy(pre));
        }
        if let Some(pre) = ByteSet::new(kind, needles) {
            debug!("prefilter built: byteset");
            return Some(Choice::ByteSet(pre));
        }
        if let Some(pre) = AhoCorasick::new(kind, needles) {
            debug!("prefilter built: aho-corasick");
            return Some(Choice::AhoCorasick(pre));
        }
        debug!("prefilter building failed: no strategy could be found");
        None
    }
}

/// Extracts all of the prefix literals from the given HIR expressions into a
/// single `Seq`. The literals in the sequence are ordered with respect to the
/// order of the given HIR expressions and consistent with the match semantics
/// given.
///
/// The sequence returned is "optimized." That is, they may be shrunk or even
/// truncated according to heuristics with the intent of making them more
/// useful as a prefilter. (Which translates to both using faster algorithms
/// and minimizing the false positive rate.)
///
/// Note that this erases any connection between the literals and which pattern
/// (or patterns) they came from.
///
/// The match kind given must correspond to the match semantics of the regex
/// that is represented by the HIRs given. The match semantics may change the
/// literal sequence returned.
#[cfg(feature = "syntax")]
pub(crate) fn prefixes<H>(kind: MatchKind, hirs: &[H]) -> literal::Seq
where
    H: core::borrow::Borrow<Hir>,
{
    let mut extractor = literal::Extractor::new();
    extractor.kind(literal::ExtractKind::Prefix);

    let mut prefixes = literal::Seq::empty();
    for hir in hirs {
        prefixes.union(&mut extractor.extract(hir.borrow()));
    }
    debug!(
        "prefixes (len={:?}, exact={:?}) extracted before optimization: {:?}",
        prefixes.len(),
        prefixes.is_exact(),
        prefixes
    );
    match kind {
        MatchKind::All => {
            prefixes.sort();
            prefixes.dedup();
        }
        MatchKind::LeftmostFirst => {
            prefixes.optimize_for_prefix_by_preference();
        }
    }
    debug!(
        "prefixes (len={:?}, exact={:?}) extracted after optimization: {:?}",
        prefixes.len(),
        prefixes.is_exact(),
        prefixes
    );
    prefixes
}

/// Like `prefixes`, but for all suffixes of all matches for the given HIRs.
#[cfg(feature = "syntax")]
pub(crate) fn suffixes<H>(kind: MatchKind, hirs: &[H]) -> literal::Seq
where
    H: core::borrow::Borrow<Hir>,
{
    let mut extractor = literal::Extractor::new();
    extractor.kind(literal::ExtractKind::Suffix);

    let mut suffixes = literal::Seq::empty();
    for hir in hirs {
        suffixes.union(&mut extractor.extract(hir.borrow()));
    }
    debug!(
        "suffixes (len={:?}, exact={:?}) extracted before optimization: {:?}",
        suffixes.len(),
        suffixes.is_exact(),
        suffixes
    );
    match kind {
        MatchKind::All => {
            suffixes.sort();
            suffixes.dedup();
        }
        MatchKind::LeftmostFirst => {
            suffixes.optimize_for_suffix_by_preference();
        }
    }
    debug!(
        "suffixes (len={:?}, exact={:?}) extracted after optimization: {:?}",
        suffixes.len(),
        suffixes.is_exact(),
        suffixes
    );
    suffixes
}