regex_automata/meta/

reverse_inner.rs

/*!
A module dedicated to plucking inner literals out of a regex pattern, and
then constructing a prefilter for them. We also include a regex pattern
"prefix" that corresponds to the bits of the regex that need to match before
the literals do. The reverse inner optimization then proceeds by looking for
matches of the inner literal(s), and then doing a reverse search of the prefix
from the start of the literal match to find the overall start position of the
match.

The essential invariant we want to uphold here is that the literals we return
reflect a set where *at least* one of them must match in order for the overall
regex to match. We also need to maintain the invariant that the regex prefix
returned corresponds to the entirety of the regex up until the literals we
return.

This somewhat limits what we can do. That is, if we a regex like
`\w+(@!|%%)\w+`, then we can pluck the `{@!, %%}` out and build a prefilter
from it. Then we just need to compile `\w+` in reverse. No fuss no muss. But if
we have a regex like \d+@!|\w+%%`, then we get kind of stymied. Technically,
we could still extract `{@!, %%}`, and it is true that at least of them must
match. But then, what is our regex prefix? Again, in theory, that could be
`\d+|\w+`, but that's not quite right, because the `\d+` only matches when `@!`
matches, and `\w+` only matches when `%%` matches.

All of that is technically possible to do, but it seemingly requires a lot of
sophistication and machinery. Probably the way to tackle that is with some kind
of formalism and approach this problem more generally.

For now, the code below basically just looks for a top-level concatenation.
And if it can find one, it looks for literals in each of the direct child
sub-expressions of that concatenation. If some good ones are found, we return
those and a concatenation of the Hir expressions seen up to that point.
*/

use alloc::vec::Vec;

use regex_syntax::hir::{
    self,
    literal::{self, Literal},
    Hir, HirKind,
};

use crate::{meta::prefix, util::prefilter::Prefilter, MatchKind};

/// Returns true when it's impossible for an earlier match to be detected after
/// a literal candidate (corresponding to anything in `literals`) has
/// been found.
///
/// Specifically, that there is no earlier match than what a reverse scan of
/// `concat_prefix` after a match of `literals` reports.
///
/// Since this requires a single `Hir`, this implies the reverse inner optimization
/// only works with a single regex.
pub(super) fn has_no_earlier_match(
    concat_prefix: &Hir,
    literals: &[Literal],
) -> bool {
    // let literals = prefix::LiteralSet::many(literals);
    if literals.is_empty() || literals.iter().any(|lit| lit.is_empty()) {
        debug!(
            "reverse inner is not early return safe because \
                 no non-empty inner literals were found"
        );
        return false;
    }
    // With one literal, an occurrence crossing the prefix boundary must
    // overlap another occurrence of that same literal. Such an overlap
    // requires the prefix to consume every distinct byte in the literal.
    // This reasoning does not apply when one extracted literal can cross
    // the boundary into a different extracted literal.
    if literals.len() == 1 {
        let prefix_may_contain = prefix::hir_can_contain_literal(
            concat_prefix,
            literals[0].as_bytes(),
        );
        debug!(
            "reverse inner prefix can contain inner literals? \
             {prefix_may_contain}"
        );
        if !prefix_may_contain {
            return true;
        }
    }

    let fixed_length = prefix::hir_has_fixed_length(concat_prefix);
    debug!("reverse inner has fixed length prefix? {fixed_length}");
    if fixed_length {
        return true;
    }

    let class_separator =
        prefix::has_disjoint_class_separator(concat_prefix, &literals);
    debug!("reverse inner has disjoint class separator? {class_separator}");
    if class_separator {
        return true;
    }

    // We couldn't prove that the reverse inner optimization
    // was safe, so bail out.
    false
}

/// This attempts to extract an "inner" prefilter from the given HIR
/// expressions. If one was found, then a concatenation of the HIR expressions
/// that precede it is returned.
///
/// The idea here is that the prefilter returned can be used to find
/// candidate matches. And then the HIR returned can be used to build a
/// reverse regex matcher, which will find the start of the candidate
/// match. Finally, the match still has to be confirmed with a normal
/// anchored forward scan to find the end position of the match.
///
/// Note that this assumes leftmost-first match semantics, so callers must
/// not call this otherwise.
#[derive(Debug)]
pub(crate) struct InnerPrefilter {
    pub(crate) prefix: Hir,
    /// The prefilter generated from `literals`.
    pub(crate) pre: Prefilter,
    /// The actual literals extracted and used to build `pre`.
    ///
    /// These are used by the meta strategy to prove that the inner prefilter
    /// can return after the first confirmed candidate. If that proof fails, we
    /// could try extracting a different set of literals. But we don't
    /// currently do that.
    pub(crate) literals: Vec<Literal>,
}

impl InnerPrefilter {
    pub(crate) fn new(hirs: &[&Hir]) -> Option<InnerPrefilter> {
        if hirs.len() != 1 {
            debug!(
                "skipping reverse inner optimization since it only \
                 supports 1 pattern, {} were given",
                hirs.len(),
            );
            return None;
        }
        let mut concat = match top_concat(hirs[0]) {
            Some(concat) => concat,
            None => {
                debug!(
                    "skipping reverse inner optimization because a top-level \
                     concatenation could not found",
                );
                return None;
            }
        };
        // We skip the first HIR because if it did have a prefix prefilter in
        // it, we probably wouldn't be here looking for an inner prefilter.
        for i in 1..concat.len() {
            let hir = &concat[i];
            let (pre, lits) = match prefilter_with_literals(hir) {
                None => continue,
                Some(pre) => pre,
            };
            // Even if we got a prefilter, if it isn't consider "fast," then
            // we probably don't want to bother with it. Namely, since the
            // reverse inner optimization requires some overhead, it likely
            // only makes sense if the prefilter scan itself is (believed) to
            // be much faster than the regex engine.
            if !pre.is_fast() {
                debug!(
                    "skipping extracted inner prefilter because \
                     it probably isn't fast"
                );
                continue;
            }
            let concat_suffix = Hir::concat(concat.split_off(i));
            let concat_prefix = Hir::concat(concat);
            // Look for a prefilter again. Why? Because above we only looked
            // for a prefilter on the individual 'hir', but we might be able
            // to find something better and more discriminatory by looking at
            // the entire suffix. We don't do this above to avoid making this
            // loop worst case quadratic in the length of 'concat'.
            let (preinner, inner_literals) =
                match prefilter_with_literals(&concat_suffix) {
                    None => (pre, lits),
                    Some((pre2, lits2)) => {
                        if pre2.is_fast() {
                            (pre2, lits2)
                        } else {
                            (pre, lits)
                        }
                    }
                };
            return Some(InnerPrefilter {
                prefix: concat_prefix,
                pre: preinner,
                literals: inner_literals,
            });
        }
        debug!(
            "skipping reverse inner optimization because a top-level \
             sub-expression with a fast prefilter could not be found"
        );
        None
    }
}

/// Attempt to extract a prefilter from an HIR expression.
///
/// We do a little massaging here to do our best that the prefilter we get out
/// of this is *probably* fast. Basically, the false positive rate has a much
/// higher impact for things like the reverse inner optimization because more
/// work needs to potentially be done for each candidate match.
///
/// Note that this assumes leftmost-first match semantics, so callers must
/// not call this otherwise.
fn prefilter_with_literals(hir: &Hir) -> Option<(Prefilter, Vec<Literal>)> {
    let mut extractor = literal::Extractor::new();
    extractor.kind(literal::ExtractKind::Prefix);
    let mut prefixes = extractor.extract(hir);
    debug!(
        "inner prefixes (len={:?}) extracted before optimization: {:?}",
        prefixes.len(),
        prefixes
    );
    // Since these are inner literals, we know they cannot be exact. But the
    // extractor doesn't know this. We mark them as inexact because this might
    // impact literal optimization. Namely, optimization weights "all literals
    // are exact" as very high, because it presumes that any match results in
    // an overall match. But of course, that is not the case here.
    //
    // In practice, this avoids plucking out a ASCII-only \s as an alternation
    // of single-byte whitespace characters.
    prefixes.make_inexact();
    prefixes.optimize_for_prefix_by_preference();
    debug!(
        "inner prefixes (len={:?}) extracted after optimization: {:?}",
        prefixes.len(),
        prefixes
    );
    let lits = prefixes.literals()?;
    let pre = Prefilter::new(MatchKind::LeftmostFirst, lits)?;
    Some((pre, lits.to_vec()))
}

/// Looks for a "top level" HirKind::Concat item in the given HIR. This will
/// try to return one even if it's embedded in a capturing group, but is
/// otherwise pretty conservative in what is returned.
///
/// The HIR returned is a complete copy of the concat with all capturing
/// groups removed. In effect, the concat returned is "flattened" with respect
/// to capturing groups. This makes the detection logic above for prefixes
/// a bit simpler, and it works because 1) capturing groups never influence
/// whether a match occurs or not and 2) capturing groups are not used when
/// doing the reverse inner search to find the start of the match.
fn top_concat(mut hir: &Hir) -> Option<Vec<Hir>> {
    loop {
        hir = match hir.kind() {
            HirKind::Empty
            | HirKind::Literal(_)
            | HirKind::Class(_)
            | HirKind::Look(_)
            | HirKind::Repetition(_)
            | HirKind::Alternation(_) => return None,
            HirKind::Capture(hir::Capture { ref sub, .. }) => sub,
            HirKind::Concat(ref subs) => {
                // We are careful to only do the flattening/copy when we know
                // we have a "top level" concat we can inspect. This avoids
                // doing extra work in cases where we definitely won't use it.
                // (This might still be wasted work if we can't go on to find
                // some literals to extract.)
                let concat =
                    Hir::concat(subs.iter().map(|h| flatten(h)).collect());
                return match concat.into_kind() {
                    HirKind::Concat(xs) => Some(xs),
                    // It is actually possible for this case to occur, because
                    // 'Hir::concat' might simplify the expression to the point
                    // that concatenations are actually removed. One wonders
                    // whether this leads to other cases where we should be
                    // extracting literals, but in theory, I believe if we do
                    // get here, then it means that a "real" prefilter failed
                    // to be extracted and we should probably leave well enough
                    // alone. (A "real" prefilter is unbothered by "top-level
                    // concats" and "capturing groups.")
                    _ => return None,
                };
            }
        };
    }
}

/// Returns a copy of the given HIR but with all capturing groups removed.
fn flatten(hir: &Hir) -> Hir {
    match hir.kind() {
        HirKind::Empty => Hir::empty(),
        HirKind::Literal(hir::Literal(ref x)) => Hir::literal(x.clone()),
        HirKind::Class(ref x) => Hir::class(x.clone()),
        HirKind::Look(ref x) => Hir::look(x.clone()),
        HirKind::Repetition(ref x) => Hir::repetition(x.with(flatten(&x.sub))),
        // This is the interesting case. We just drop the group information
        // entirely and use the child HIR itself.
        HirKind::Capture(hir::Capture { ref sub, .. }) => flatten(sub),
        HirKind::Alternation(ref xs) => {
            Hir::alternation(xs.iter().map(|x| flatten(x)).collect())
        }
        HirKind::Concat(ref xs) => {
            Hir::concat(xs.iter().map(|x| flatten(x)).collect())
        }
    }
}