| 1 |
/*! |
| 2 |
A module dedicated to plucking inner literals out of a regex pattern, and |
| 3 |
then constructing a prefilter for them. We also include a regex pattern |
| 4 |
"prefix" that corresponds to the bits of the regex that need to match before |
| 5 |
the literals do. The reverse inner optimization then proceeds by looking for |
| 6 |
matches of the inner literal(s), and then doing a reverse search of the prefix |
| 7 |
from the start of the literal match to find the overall start position of the |
| 8 |
match. |
| 9 |
|
| 10 |
The essential invariant we want to uphold here is that the literals we return |
| 11 |
reflect a set where *at least* one of them must match in order for the overall |
| 12 |
regex to match. We also need to maintain the invariant that the regex prefix |
| 13 |
returned corresponds to the entirety of the regex up until the literals we |
| 14 |
return. |
| 15 |
|
| 16 |
This somewhat limits what we can do. That is, if we a regex like |
| 17 |
`\w+(@!|%%)\w+`, then we can pluck the `{@!, %%}` out and build a prefilter |
| 18 |
from it. Then we just need to compile `\w+` in reverse. No fuss no muss. But if |
| 19 |
we have a regex like \d+@!|\w+%%`, then we get kind of stymied. Technically, |
| 20 |
we could still extract `{@!, %%}`, and it is true that at least of them must |
| 21 |
match. But then, what is our regex prefix? Again, in theory, that could be |
| 22 |
`\d+|\w+`, but that's not quite right, because the `\d+` only matches when `@!` |
| 23 |
matches, and `\w+` only matches when `%%` matches. |
| 24 |
|
| 25 |
All of that is technically possible to do, but it seemingly requires a lot of |
| 26 |
sophistication and machinery. Probably the way to tackle that is with some kind |
| 27 |
of formalism and approach this problem more generally. |
| 28 |
|
| 29 |
For now, the code below basically just looks for a top-level concatenation. |
| 30 |
And if it can find one, it looks for literals in each of the direct child |
| 31 |
sub-expressions of that concatenation. If some good ones are found, we return |
| 32 |
those and a concatenation of the Hir expressions seen up to that point. |
| 33 |
*/ |
| 34 |
|
| 35 |
use alloc::vec::Vec; |
| 36 |
|
| 37 |
use regex_syntax::hir::{self, literal, Hir, HirKind}; |
| 38 |
|
| 39 |
use crate::{util::prefilter::Prefilter, MatchKind}; |
| 40 |
|
| 41 |
/// Attempts to extract an "inner" prefilter from the given HIR expressions. If |
| 42 |
/// one was found, then a concatenation of the HIR expressions that precede it |
| 43 |
/// is returned. |
| 44 |
/// |
| 45 |
/// The idea here is that the prefilter returned can be used to find candidate |
| 46 |
/// matches. And then the HIR returned can be used to build a reverse regex |
| 47 |
/// matcher, which will find the start of the candidate match. Finally, the |
| 48 |
/// match still has to be confirmed with a normal anchored forward scan to find |
| 49 |
/// the end position of the match. |
| 50 |
/// |
| 51 |
/// Note that this assumes leftmost-first match semantics, so callers must |
| 52 |
/// not call this otherwise. |
| 53 |
pub(crate) fn extract(hirs: &[&Hir]) -> Option<(Hir, Prefilter)> { |
| 54 |
if hirs.len() != 1 { |
| 55 |
debug!( |
| 56 |
"skipping reverse inner optimization since it only \ |
| 57 |
supports 1 pattern, {} were given", |
| 58 |
hirs.len(), |
| 59 |
); |
| 60 |
return None; |
| 61 |
} |
| 62 |
let mut concat = match top_concat(hirs[0]) { |
| 63 |
Some(concat) => concat, |
| 64 |
None => { |
| 65 |
debug!( |
| 66 |
"skipping reverse inner optimization because a top-level \ |
| 67 |
concatenation could not found", |
| 68 |
); |
| 69 |
return None; |
| 70 |
} |
| 71 |
}; |
| 72 |
// We skip the first HIR because if it did have a prefix prefilter in it, |
| 73 |
// we probably wouldn't be here looking for an inner prefilter. |
| 74 |
for i in 1..concat.len() { |
| 75 |
let hir = &concat[i]; |
| 76 |
let pre = match prefilter(hir) { |
| 77 |
None => continue, |
| 78 |
Some(pre) => pre, |
| 79 |
}; |
| 80 |
// Even if we got a prefilter, if it isn't consider "fast," then we |
| 81 |
// probably don't want to bother with it. Namely, since the reverse |
| 82 |
// inner optimization requires some overhead, it likely only makes |
| 83 |
// sense if the prefilter scan itself is (believed) to be much faster |
| 84 |
// than the regex engine. |
| 85 |
if !pre.is_fast() { |
| 86 |
debug!( |
| 87 |
"skipping extracted inner prefilter because \ |
| 88 |
it probably isn't fast" |
| 89 |
); |
| 90 |
continue; |
| 91 |
} |
| 92 |
let concat_suffix = Hir::concat(concat.split_off(i)); |
| 93 |
let concat_prefix = Hir::concat(concat); |
| 94 |
// Look for a prefilter again. Why? Because above we only looked for |
| 95 |
// a prefilter on the individual 'hir', but we might be able to find |
| 96 |
// something better and more discriminatory by looking at the entire |
| 97 |
// suffix. We don't do this above to avoid making this loop worst case |
| 98 |
// quadratic in the length of 'concat'. |
| 99 |
let pre2 = match prefilter(&concat_suffix) { |
| 100 |
None => pre, |
| 101 |
Some(pre2) => { |
| 102 |
if pre2.is_fast() { |
| 103 |
pre2 |
| 104 |
} else { |
| 105 |
pre |
| 106 |
} |
| 107 |
} |
| 108 |
}; |
| 109 |
return Some((concat_prefix, pre2)); |
| 110 |
} |
| 111 |
debug!( |
| 112 |
"skipping reverse inner optimization because a top-level \ |
| 113 |
sub-expression with a fast prefilter could not be found" |
| 114 |
); |
| 115 |
None |
| 116 |
} |
| 117 |
|
| 118 |
/// Attempt to extract a prefilter from an HIR expression. |
| 119 |
/// |
| 120 |
/// We do a little massaging here to do our best that the prefilter we get out |
| 121 |
/// of this is *probably* fast. Basically, the false positive rate has a much |
| 122 |
/// higher impact for things like the reverse inner optimization because more |
| 123 |
/// work needs to potentially be done for each candidate match. |
| 124 |
/// |
| 125 |
/// Note that this assumes leftmost-first match semantics, so callers must |
| 126 |
/// not call this otherwise. |
| 127 |
fn prefilter(hir: &Hir) -> Option<Prefilter> { |
| 128 |
let mut extractor = literal::Extractor::new(); |
| 129 |
extractor.kind(literal::ExtractKind::Prefix); |
| 130 |
let mut prefixes = extractor.extract(hir); |
| 131 |
debug!( |
| 132 |
"inner prefixes (len={:?}) extracted before optimization: {:?}", |
| 133 |
prefixes.len(), |
| 134 |
prefixes |
| 135 |
); |
| 136 |
// Since these are inner literals, we know they cannot be exact. But the |
| 137 |
// extractor doesn't know this. We mark them as inexact because this might |
| 138 |
// impact literal optimization. Namely, optimization weights "all literals |
| 139 |
// are exact" as very high, because it presumes that any match results in |
| 140 |
// an overall match. But of course, that is not the case here. |
| 141 |
// |
| 142 |
// In practice, this avoids plucking out a ASCII-only \s as an alternation |
| 143 |
// of single-byte whitespace characters. |
| 144 |
prefixes.make_inexact(); |
| 145 |
prefixes.optimize_for_prefix_by_preference(); |
| 146 |
debug!( |
| 147 |
"inner prefixes (len={:?}) extracted after optimization: {:?}", |
| 148 |
prefixes.len(), |
| 149 |
prefixes |
| 150 |
); |
| 151 |
prefixes |
| 152 |
.literals() |
| 153 |
.and_then(|lits| Prefilter::new(MatchKind::LeftmostFirst, lits)) |
| 154 |
} |
| 155 |
|
| 156 |
/// Looks for a "top level" HirKind::Concat item in the given HIR. This will |
| 157 |
/// try to return one even if it's embedded in a capturing group, but is |
| 158 |
/// otherwise pretty conservative in what is returned. |
| 159 |
/// |
| 160 |
/// The HIR returned is a complete copy of the concat with all capturing |
| 161 |
/// groups removed. In effect, the concat returned is "flattened" with respect |
| 162 |
/// to capturing groups. This makes the detection logic above for prefixes |
| 163 |
/// a bit simpler, and it works because 1) capturing groups never influence |
| 164 |
/// whether a match occurs or not and 2) capturing groups are not used when |
| 165 |
/// doing the reverse inner search to find the start of the match. |
| 166 |
fn top_concat(mut hir: &Hir) -> Option<Vec<Hir>> { |
| 167 |
loop { |
| 168 |
hir = match hir.kind() { |
| 169 |
HirKind::Empty |
| 170 |
| HirKind::Literal(_) |
| 171 |
| HirKind::Class(_) |
| 172 |
| HirKind::Look(_) |
| 173 |
| HirKind::Repetition(_) |
| 174 |
| HirKind::Alternation(_) => return None, |
| 175 |
HirKind::Capture(hir::Capture { ref sub, .. }) => sub, |
| 176 |
HirKind::Concat(ref subs) => { |
| 177 |
// We are careful to only do the flattening/copy when we know |
| 178 |
// we have a "top level" concat we can inspect. This avoids |
| 179 |
// doing extra work in cases where we definitely won't use it. |
| 180 |
// (This might still be wasted work if we can't go on to find |
| 181 |
// some literals to extract.) |
| 182 |
let concat = |
| 183 |
Hir::concat(subs.iter().map(|h| flatten(h)).collect()); |
| 184 |
return match concat.into_kind() { |
| 185 |
HirKind::Concat(xs) => Some(xs), |
| 186 |
// It is actually possible for this case to occur, because |
| 187 |
// 'Hir::concat' might simplify the expression to the point |
| 188 |
// that concatenations are actually removed. One wonders |
| 189 |
// whether this leads to other cases where we should be |
| 190 |
// extracting literals, but in theory, I believe if we do |
| 191 |
// get here, then it means that a "real" prefilter failed |
| 192 |
// to be extracted and we should probably leave well enough |
| 193 |
// alone. (A "real" prefilter is unbothered by "top-level |
| 194 |
// concats" and "capturing groups.") |
| 195 |
_ => return None, |
| 196 |
}; |
| 197 |
} |
| 198 |
}; |
| 199 |
} |
| 200 |
} |
| 201 |
|
| 202 |
/// Returns a copy of the given HIR but with all capturing groups removed. |
| 203 |
fn flatten(hir: &Hir) -> Hir { |
| 204 |
match hir.kind() { |
| 205 |
HirKind::Empty => Hir::empty(), |
| 206 |
HirKind::Literal(hir::Literal(ref x)) => Hir::literal(x.clone()), |
| 207 |
HirKind::Class(ref x) => Hir::class(x.clone()), |
| 208 |
HirKind::Look(ref x) => Hir::look(x.clone()), |
| 209 |
HirKind::Repetition(ref x) => Hir::repetition(x.with(flatten(&x.sub))), |
| 210 |
// This is the interesting case. We just drop the group information |
| 211 |
// entirely and use the child HIR itself. |
| 212 |
HirKind::Capture(hir::Capture { ref sub, .. }) => flatten(sub), |
| 213 |
HirKind::Alternation(ref xs) => { |
| 214 |
Hir::alternation(xs.iter().map(|x| flatten(x)).collect()) |
| 215 |
} |
| 216 |
HirKind::Concat(ref xs) => { |
| 217 |
Hir::concat(xs.iter().map(|x| flatten(x)).collect()) |
| 218 |
} |
| 219 |
} |
| 220 |
} |