Source code
Revision control
Copy as Markdown
Other Tools
use core::{
fmt::Debug,
panic::{RefUnwindSafe, UnwindSafe},
};
use alloc::sync::Arc;
use regex_syntax::hir::{literal, Hir};
use crate::{
meta::{
error::{BuildError, RetryError, RetryFailError, RetryQuadraticError},
regex::{Cache, RegexInfo},
reverse_inner, wrappers,
},
nfa::thompson::{self, WhichCaptures, NFA},
util::{
captures::{Captures, GroupInfo},
look::LookMatcher,
prefilter::{self, Prefilter, PrefilterI},
primitives::{NonMaxUsize, PatternID},
search::{Anchored, HalfMatch, Input, Match, MatchKind, PatternSet},
},
};
/// A trait that represents a single meta strategy. Its main utility is in
/// providing a way to do dynamic dispatch over a few choices.
///
/// Why dynamic dispatch? I actually don't have a super compelling reason, and
/// importantly, I have not benchmarked it with the main alternative: an enum.
/// I went with dynamic dispatch initially because the regex engine search code
/// really can't be inlined into caller code in most cases because it's just
/// too big. In other words, it is already expected that every regex search
/// will entail at least the cost of a function call.
///
/// I do wonder whether using enums would result in better codegen overall
/// though. It's a worthwhile experiment to try. Probably the most interesting
/// benchmark to run in such a case would be one with a high match count. That
/// is, a benchmark to test the overall latency of a search call.
pub(super) trait Strategy:
Debug + Send + Sync + RefUnwindSafe + UnwindSafe + 'static
{
fn group_info(&self) -> &GroupInfo;
fn create_cache(&self) -> Cache;
fn reset_cache(&self, cache: &mut Cache);
fn is_accelerated(&self) -> bool;
fn memory_usage(&self) -> usize;
fn search(&self, cache: &mut Cache, input: &Input<'_>) -> Option<Match>;
fn search_half(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<HalfMatch>;
fn is_match(&self, cache: &mut Cache, input: &Input<'_>) -> bool;
fn search_slots(
&self,
cache: &mut Cache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID>;
fn which_overlapping_matches(
&self,
cache: &mut Cache,
input: &Input<'_>,
patset: &mut PatternSet,
);
}
pub(super) fn new(
info: &RegexInfo,
hirs: &[&Hir],
) -> Result<Arc<dyn Strategy>, BuildError> {
// At this point, we're committed to a regex engine of some kind. So pull
// out a prefilter if we can, which will feed to each of the constituent
// regex engines.
let pre = if info.is_always_anchored_start() {
// PERF: I'm not sure we necessarily want to do this... We may want to
// run a prefilter for quickly rejecting in some cases. The problem
// is that anchored searches overlap quite a bit with the use case
// of "run a regex on every line to extract data." In that case, the
// regex always matches, so running a prefilter doesn't really help us
// there. The main place where a prefilter helps in an anchored search
// is if the anchored search is not expected to match frequently. That
// is, the prefilter gives us a way to possibly reject a haystack very
// quickly.
//
// Maybe we should do use a prefilter, but only for longer haystacks?
// Or maybe we should only use a prefilter when we think it's "fast"?
//
// Interestingly, I think we currently lack the infrastructure for
// disabling a prefilter based on haystack length. That would probably
// need to be a new 'Input' option. (Interestingly, an 'Input' used to
// carry a 'Prefilter' with it, but I moved away from that.)
debug!("skipping literal extraction since regex is anchored");
None
} else if let Some(pre) = info.config().get_prefilter() {
debug!(
"skipping literal extraction since the caller provided a prefilter"
);
Some(pre.clone())
} else if info.config().get_auto_prefilter() {
let kind = info.config().get_match_kind();
let prefixes = crate::util::prefilter::prefixes(kind, hirs);
// If we can build a full `Strategy` from just the extracted prefixes,
// then we can short-circuit and avoid building a regex engine at all.
if let Some(pre) = Pre::from_prefixes(info, &prefixes) {
debug!(
"found that the regex can be broken down to a literal \
search, avoiding the regex engine entirely",
);
return Ok(pre);
}
// This now attempts another short-circuit of the regex engine: if we
// have a huge alternation of just plain literals, then we can just use
// Aho-Corasick for that and avoid the regex engine entirely.
//
// You might think this case would just be handled by
// `Pre::from_prefixes`, but that technique relies on heuristic literal
// extraction from the corresponding `Hir`. That works, but part of
// heuristics limit the size and number of literals returned. This case
// will specifically handle patterns with very large alternations.
//
// One wonders if we should just roll this our heuristic literal
// extraction, and then I think this case could disappear entirely.
if let Some(pre) = Pre::from_alternation_literals(info, hirs) {
debug!(
"found plain alternation of literals, \
avoiding regex engine entirely and using Aho-Corasick"
);
return Ok(pre);
}
prefixes.literals().and_then(|strings| {
debug!(
"creating prefilter from {} literals: {:?}",
strings.len(),
strings,
);
Prefilter::new(kind, strings)
})
} else {
debug!("skipping literal extraction since prefilters were disabled");
None
};
let mut core = Core::new(info.clone(), pre.clone(), hirs)?;
// Now that we have our core regex engines built, there are a few cases
// where we can do a little bit better than just a normal "search forward
// and maybe use a prefilter when in a start state." However, these cases
// may not always work or otherwise build on top of the Core searcher.
// For example, the reverse anchored optimization seems like it might
// always work, but only the DFAs support reverse searching and the DFAs
// might give up or quit for reasons. If we had, e.g., a PikeVM that
// supported reverse searching, then we could avoid building a full Core
// engine for this case.
core = match ReverseAnchored::new(core) {
Err(core) => core,
Ok(ra) => {
debug!("using reverse anchored strategy");
return Ok(Arc::new(ra));
}
};
core = match ReverseSuffix::new(core, hirs) {
Err(core) => core,
Ok(rs) => {
debug!("using reverse suffix strategy");
return Ok(Arc::new(rs));
}
};
core = match ReverseInner::new(core, hirs) {
Err(core) => core,
Ok(ri) => {
debug!("using reverse inner strategy");
return Ok(Arc::new(ri));
}
};
debug!("using core strategy");
Ok(Arc::new(core))
}
#[derive(Clone, Debug)]
struct Pre<P> {
pre: P,
group_info: GroupInfo,
}
impl<P: PrefilterI> Pre<P> {
fn new(pre: P) -> Arc<dyn Strategy> {
// The only thing we support when we use prefilters directly as a
// strategy is the start and end of the overall match for a single
// pattern. In other words, exactly one implicit capturing group. Which
// is exactly what we use here for a GroupInfo.
let group_info = GroupInfo::new([[None::<&str>]]).unwrap();
Arc::new(Pre { pre, group_info })
}
}
// This is a little weird, but we don't actually care about the type parameter
// here because we're selecting which underlying prefilter to use. So we just
// define it on an arbitrary type.
impl Pre<()> {
/// Given a sequence of prefixes, attempt to return a full `Strategy` using
/// just the prefixes.
///
/// Basically, this occurs when the prefixes given not just prefixes,
/// but an enumeration of the entire language matched by the regular
/// expression.
///
/// A number of other conditions need to be true too. For example, there
/// can be only one pattern, the number of explicit capture groups is 0, no
/// look-around assertions and so on.
///
/// Note that this ignores `Config::get_auto_prefilter` because if this
/// returns something, then it isn't a prefilter but a matcher itself.
/// Therefore, it shouldn't suffer from the problems typical to prefilters
/// (such as a high false positive rate).
fn from_prefixes(
info: &RegexInfo,
prefixes: &literal::Seq,
) -> Option<Arc<dyn Strategy>> {
let kind = info.config().get_match_kind();
// Check to see if our prefixes are exact, which means we might be
// able to bypass the regex engine entirely and just rely on literal
// searches.
if !prefixes.is_exact() {
return None;
}
// We also require that we have a single regex pattern. Namely,
// we reuse the prefilter infrastructure to implement search and
// prefilters only report spans. Prefilters don't know about pattern
// IDs. The multi-regex case isn't a lost cause, we might still use
// Aho-Corasick and we might still just use a regular prefilter, but
// that's done below.
if info.pattern_len() != 1 {
return None;
}
// We can't have any capture groups either. The literal engines don't
// know how to deal with things like '(foo)(bar)'. In that case, a
// prefilter will just be used and then the regex engine will resolve
// the capture groups.
if info.props()[0].explicit_captures_len() != 0 {
return None;
}
// We also require that it has zero look-around assertions. Namely,
// literal extraction treats look-around assertions as if they match
// *every* empty string. But of course, that isn't true. So for
// example, 'foo\bquux' never matches anything, but 'fooquux' is
// extracted from that as an exact literal. Such cases should just run
// the regex engine. 'fooquux' will be used as a normal prefilter, and
// then the regex engine will try to look for an actual match.
if !info.props()[0].look_set().is_empty() {
return None;
}
// Finally, currently, our prefilters are all oriented around
// leftmost-first match semantics, so don't try to use them if the
// caller asked for anything else.
if kind != MatchKind::LeftmostFirst {
return None;
}
// The above seems like a lot of requirements to meet, but it applies
// to a lot of cases. 'foo', '[abc][123]' and 'foo|bar|quux' all meet
// the above criteria, for example.
//
// Note that this is effectively a latency optimization. If we didn't
// do this, then the extracted literals would still get bundled into
// a prefilter, and every regex engine capable of running unanchored
// searches supports prefilters. So this optimization merely sidesteps
// having to run the regex engine at all to confirm the match. Thus, it
// decreases the latency of a match.
// OK because we know the set is exact and thus finite.
let prefixes = prefixes.literals().unwrap();
debug!(
"trying to bypass regex engine by creating \
prefilter from {} literals: {:?}",
prefixes.len(),
prefixes,
);
let choice = match prefilter::Choice::new(kind, prefixes) {
Some(choice) => choice,
None => {
debug!(
"regex bypass failed because no prefilter could be built"
);
return None;
}
};
let strat: Arc<dyn Strategy> = match choice {
prefilter::Choice::Memchr(pre) => Pre::new(pre),
prefilter::Choice::Memchr2(pre) => Pre::new(pre),
prefilter::Choice::Memchr3(pre) => Pre::new(pre),
prefilter::Choice::Memmem(pre) => Pre::new(pre),
prefilter::Choice::Teddy(pre) => Pre::new(pre),
prefilter::Choice::ByteSet(pre) => Pre::new(pre),
prefilter::Choice::AhoCorasick(pre) => Pre::new(pre),
};
Some(strat)
}
/// Attempts to extract an alternation of literals, and if it's deemed
/// worth doing, returns an Aho-Corasick prefilter as a strategy.
///
/// And currently, this only returns something when 'hirs.len() == 1'. This
/// could in theory do something if there are multiple HIRs where all of
/// them are alternation of literals, but I haven't had the time to go down
/// that path yet.
fn from_alternation_literals(
info: &RegexInfo,
hirs: &[&Hir],
) -> Option<Arc<dyn Strategy>> {
use crate::util::prefilter::AhoCorasick;
let lits = crate::meta::literal::alternation_literals(info, hirs)?;
let ac = AhoCorasick::new(MatchKind::LeftmostFirst, &lits)?;
Some(Pre::new(ac))
}
}
// This implements Strategy for anything that implements PrefilterI.
//
// Note that this must only be used for regexes of length 1. Multi-regexes
// don't work here. The prefilter interface only provides the span of a match
// and not the pattern ID. (I did consider making it more expressive, but I
// couldn't figure out how to tie everything together elegantly.) Thus, so long
// as the regex only contains one pattern, we can simply assume that a match
// corresponds to PatternID::ZERO. And indeed, that's what we do here.
//
// In practice, since this impl is used to report matches directly and thus
// completely bypasses the regex engine, we only wind up using this under the
// following restrictions:
//
// * There must be only one pattern. As explained above.
// * The literal sequence must be finite and only contain exact literals.
// * There must not be any look-around assertions. If there are, the literals
// extracted might be exact, but a match doesn't necessarily imply an overall
// match. As a trivial example, 'foo\bbar' does not match 'foobar'.
// * The pattern must not have any explicit capturing groups. If it does, the
// caller might expect them to be resolved. e.g., 'foo(bar)'.
//
// So when all of those things are true, we use a prefilter directly as a
// strategy.
//
// In the case where the number of patterns is more than 1, we don't use this
// but do use a special Aho-Corasick strategy if all of the regexes are just
// simple literals or alternations of literals. (We also use the Aho-Corasick
// strategy when len(patterns)==1 if the number of literals is large. In that
// case, literal extraction gives up and will return an infinite set.)
impl<P: PrefilterI> Strategy for Pre<P> {
fn group_info(&self) -> &GroupInfo {
&self.group_info
}
fn create_cache(&self) -> Cache {
Cache {
capmatches: Captures::all(self.group_info().clone()),
pikevm: wrappers::PikeVMCache::none(),
backtrack: wrappers::BoundedBacktrackerCache::none(),
onepass: wrappers::OnePassCache::none(),
hybrid: wrappers::HybridCache::none(),
revhybrid: wrappers::ReverseHybridCache::none(),
}
}
fn reset_cache(&self, _cache: &mut Cache) {}
fn is_accelerated(&self) -> bool {
self.pre.is_fast()
}
fn memory_usage(&self) -> usize {
self.pre.memory_usage()
}
fn search(&self, _cache: &mut Cache, input: &Input<'_>) -> Option<Match> {
if input.is_done() {
return None;
}
if input.get_anchored().is_anchored() {
return self
.pre
.prefix(input.haystack(), input.get_span())
.map(|sp| Match::new(PatternID::ZERO, sp));
}
self.pre
.find(input.haystack(), input.get_span())
.map(|sp| Match::new(PatternID::ZERO, sp))
}
fn search_half(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<HalfMatch> {
self.search(cache, input).map(|m| HalfMatch::new(m.pattern(), m.end()))
}
fn is_match(&self, cache: &mut Cache, input: &Input<'_>) -> bool {
self.search(cache, input).is_some()
}
fn search_slots(
&self,
cache: &mut Cache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
let m = self.search(cache, input)?;
if let Some(slot) = slots.get_mut(0) {
*slot = NonMaxUsize::new(m.start());
}
if let Some(slot) = slots.get_mut(1) {
*slot = NonMaxUsize::new(m.end());
}
Some(m.pattern())
}
fn which_overlapping_matches(
&self,
cache: &mut Cache,
input: &Input<'_>,
patset: &mut PatternSet,
) {
if self.search(cache, input).is_some() {
patset.insert(PatternID::ZERO);
}
}
}
#[derive(Debug)]
struct Core {
info: RegexInfo,
pre: Option<Prefilter>,
nfa: NFA,
nfarev: Option<NFA>,
pikevm: wrappers::PikeVM,
backtrack: wrappers::BoundedBacktracker,
onepass: wrappers::OnePass,
hybrid: wrappers::Hybrid,
dfa: wrappers::DFA,
}
impl Core {
fn new(
info: RegexInfo,
pre: Option<Prefilter>,
hirs: &[&Hir],
) -> Result<Core, BuildError> {
let mut lookm = LookMatcher::new();
lookm.set_line_terminator(info.config().get_line_terminator());
let thompson_config = thompson::Config::new()
.utf8(info.config().get_utf8_empty())
.nfa_size_limit(info.config().get_nfa_size_limit())
.shrink(false)
.which_captures(info.config().get_which_captures())
.look_matcher(lookm);
let nfa = thompson::Compiler::new()
.configure(thompson_config.clone())
.build_many_from_hir(hirs)
.map_err(BuildError::nfa)?;
// It's possible for the PikeVM or the BB to fail to build, even though
// at this point, we already have a full NFA in hand. They can fail
// when a Unicode word boundary is used but where Unicode word boundary
// support is disabled at compile time, thus making it impossible to
// match. (Construction can also fail if the NFA was compiled without
// captures, but we always enable that above.)
let pikevm = wrappers::PikeVM::new(&info, pre.clone(), &nfa)?;
let backtrack =
wrappers::BoundedBacktracker::new(&info, pre.clone(), &nfa)?;
// The onepass engine can of course fail to build, but we expect it to
// fail in many cases because it is an optimization that doesn't apply
// to all regexes. The 'OnePass' wrapper encapsulates this failure (and
// logs a message if it occurs).
let onepass = wrappers::OnePass::new(&info, &nfa);
// We try to encapsulate whether a particular regex engine should be
// used within each respective wrapper, but the DFAs need a reverse NFA
// to build itself, and we really do not want to build a reverse NFA if
// we know we aren't going to use the lazy DFA. So we do a config check
// up front, which is in practice the only way we won't try to use the
// DFA.
let (nfarev, hybrid, dfa) =
if !info.config().get_hybrid() && !info.config().get_dfa() {
(None, wrappers::Hybrid::none(), wrappers::DFA::none())
} else {
// FIXME: Technically, we don't quite yet KNOW that we need
// a reverse NFA. It's possible for the DFAs below to both
// fail to build just based on the forward NFA. In which case,
// building the reverse NFA was totally wasted work. But...
// fixing this requires breaking DFA construction apart into
// two pieces: one for the forward part and another for the
// reverse part. Quite annoying. Making it worse, when building
// both DFAs fails, it's quite likely that the NFA is large and
// that it will take quite some time to build the reverse NFA
// too. So... it's really probably worth it to do this!
let nfarev = thompson::Compiler::new()
// Currently, reverse NFAs don't support capturing groups,
// so we MUST disable them. But even if we didn't have to,
// we would, because nothing in this crate does anything
// useful with capturing groups in reverse. And of course,
// the lazy DFA ignores capturing groups in all cases.
.configure(
thompson_config
.clone()
.which_captures(WhichCaptures::None)
.reverse(true),
)
.build_many_from_hir(hirs)
.map_err(BuildError::nfa)?;
let dfa = if !info.config().get_dfa() {
wrappers::DFA::none()
} else {
wrappers::DFA::new(&info, pre.clone(), &nfa, &nfarev)
};
let hybrid = if !info.config().get_hybrid() {
wrappers::Hybrid::none()
} else if dfa.is_some() {
debug!("skipping lazy DFA because we have a full DFA");
wrappers::Hybrid::none()
} else {
wrappers::Hybrid::new(&info, pre.clone(), &nfa, &nfarev)
};
(Some(nfarev), hybrid, dfa)
};
Ok(Core {
info,
pre,
nfa,
nfarev,
pikevm,
backtrack,
onepass,
hybrid,
dfa,
})
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn try_search_mayfail(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<Result<Option<Match>, RetryFailError>> {
if let Some(e) = self.dfa.get(input) {
trace!("using full DFA for search at {:?}", input.get_span());
Some(e.try_search(input))
} else if let Some(e) = self.hybrid.get(input) {
trace!("using lazy DFA for search at {:?}", input.get_span());
Some(e.try_search(&mut cache.hybrid, input))
} else {
None
}
}
fn search_nofail(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<Match> {
let caps = &mut cache.capmatches;
caps.set_pattern(None);
// We manually inline 'try_search_slots_nofail' here because we need to
// borrow from 'cache.capmatches' in this method, but if we do, then
// we can't pass 'cache' wholesale to to 'try_slots_no_hybrid'. It's a
// classic example of how the borrow checker inhibits decomposition.
// There are of course work-arounds (more types and/or interior
// mutability), but that's more annoying than this IMO.
let pid = if let Some(ref e) = self.onepass.get(input) {
trace!("using OnePass for search at {:?}", input.get_span());
e.search_slots(&mut cache.onepass, input, caps.slots_mut())
} else if let Some(ref e) = self.backtrack.get(input) {
trace!(
"using BoundedBacktracker for search at {:?}",
input.get_span()
);
e.search_slots(&mut cache.backtrack, input, caps.slots_mut())
} else {
trace!("using PikeVM for search at {:?}", input.get_span());
let e = self.pikevm.get();
e.search_slots(&mut cache.pikevm, input, caps.slots_mut())
};
caps.set_pattern(pid);
caps.get_match()
}
fn search_half_nofail(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<HalfMatch> {
// Only the lazy/full DFA returns half-matches, since the DFA requires
// a reverse scan to find the start position. These fallback regex
// engines can find the start and end in a single pass, so we just do
// that and throw away the start offset to conform to the API.
let m = self.search_nofail(cache, input)?;
Some(HalfMatch::new(m.pattern(), m.end()))
}
fn search_slots_nofail(
&self,
cache: &mut Cache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
if let Some(ref e) = self.onepass.get(input) {
trace!(
"using OnePass for capture search at {:?}",
input.get_span()
);
e.search_slots(&mut cache.onepass, input, slots)
} else if let Some(ref e) = self.backtrack.get(input) {
trace!(
"using BoundedBacktracker for capture search at {:?}",
input.get_span()
);
e.search_slots(&mut cache.backtrack, input, slots)
} else {
trace!(
"using PikeVM for capture search at {:?}",
input.get_span()
);
let e = self.pikevm.get();
e.search_slots(&mut cache.pikevm, input, slots)
}
}
fn is_match_nofail(&self, cache: &mut Cache, input: &Input<'_>) -> bool {
if let Some(ref e) = self.onepass.get(input) {
trace!(
"using OnePass for is-match search at {:?}",
input.get_span()
);
e.search_slots(&mut cache.onepass, input, &mut []).is_some()
} else if let Some(ref e) = self.backtrack.get(input) {
trace!(
"using BoundedBacktracker for is-match search at {:?}",
input.get_span()
);
e.is_match(&mut cache.backtrack, input)
} else {
trace!(
"using PikeVM for is-match search at {:?}",
input.get_span()
);
let e = self.pikevm.get();
e.is_match(&mut cache.pikevm, input)
}
}
fn is_capture_search_needed(&self, slots_len: usize) -> bool {
slots_len > self.nfa.group_info().implicit_slot_len()
}
}
impl Strategy for Core {
#[cfg_attr(feature = "perf-inline", inline(always))]
fn group_info(&self) -> &GroupInfo {
self.nfa.group_info()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn create_cache(&self) -> Cache {
Cache {
capmatches: Captures::all(self.group_info().clone()),
pikevm: self.pikevm.create_cache(),
backtrack: self.backtrack.create_cache(),
onepass: self.onepass.create_cache(),
hybrid: self.hybrid.create_cache(),
revhybrid: wrappers::ReverseHybridCache::none(),
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn reset_cache(&self, cache: &mut Cache) {
cache.pikevm.reset(&self.pikevm);
cache.backtrack.reset(&self.backtrack);
cache.onepass.reset(&self.onepass);
cache.hybrid.reset(&self.hybrid);
}
fn is_accelerated(&self) -> bool {
self.pre.as_ref().map_or(false, |pre| pre.is_fast())
}
fn memory_usage(&self) -> usize {
self.info.memory_usage()
+ self.pre.as_ref().map_or(0, |pre| pre.memory_usage())
+ self.nfa.memory_usage()
+ self.nfarev.as_ref().map_or(0, |nfa| nfa.memory_usage())
+ self.onepass.memory_usage()
+ self.dfa.memory_usage()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search(&self, cache: &mut Cache, input: &Input<'_>) -> Option<Match> {
// We manually inline try_search_mayfail here because letting the
// compiler do it seems to produce pretty crappy codegen.
return if let Some(e) = self.dfa.get(input) {
trace!("using full DFA for full search at {:?}", input.get_span());
match e.try_search(input) {
Ok(x) => x,
Err(_err) => {
trace!("full DFA search failed: {}", _err);
self.search_nofail(cache, input)
}
}
} else if let Some(e) = self.hybrid.get(input) {
trace!("using lazy DFA for full search at {:?}", input.get_span());
match e.try_search(&mut cache.hybrid, input) {
Ok(x) => x,
Err(_err) => {
trace!("lazy DFA search failed: {}", _err);
self.search_nofail(cache, input)
}
}
} else {
self.search_nofail(cache, input)
};
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search_half(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<HalfMatch> {
// The main difference with 'search' is that if we're using a DFA, we
// can use a single forward scan without needing to run the reverse
// DFA.
if let Some(e) = self.dfa.get(input) {
trace!("using full DFA for half search at {:?}", input.get_span());
match e.try_search_half_fwd(input) {
Ok(x) => x,
Err(_err) => {
trace!("full DFA half search failed: {}", _err);
self.search_half_nofail(cache, input)
}
}
} else if let Some(e) = self.hybrid.get(input) {
trace!("using lazy DFA for half search at {:?}", input.get_span());
match e.try_search_half_fwd(&mut cache.hybrid, input) {
Ok(x) => x,
Err(_err) => {
trace!("lazy DFA half search failed: {}", _err);
self.search_half_nofail(cache, input)
}
}
} else {
self.search_half_nofail(cache, input)
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_match(&self, cache: &mut Cache, input: &Input<'_>) -> bool {
if let Some(e) = self.dfa.get(input) {
trace!(
"using full DFA for is-match search at {:?}",
input.get_span()
);
match e.try_search_half_fwd(input) {
Ok(x) => x.is_some(),
Err(_err) => {
trace!("full DFA half search failed: {}", _err);
self.is_match_nofail(cache, input)
}
}
} else if let Some(e) = self.hybrid.get(input) {
trace!(
"using lazy DFA for is-match search at {:?}",
input.get_span()
);
match e.try_search_half_fwd(&mut cache.hybrid, input) {
Ok(x) => x.is_some(),
Err(_err) => {
trace!("lazy DFA half search failed: {}", _err);
self.is_match_nofail(cache, input)
}
}
} else {
self.is_match_nofail(cache, input)
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search_slots(
&self,
cache: &mut Cache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
// Even if the regex has explicit capture groups, if the caller didn't
// provide any explicit slots, then it doesn't make sense to try and do
// extra work to get offsets for those slots. Ideally the caller should
// realize this and not call this routine in the first place, but alas,
// we try to save the caller from themselves if they do.
if !self.is_capture_search_needed(slots.len()) {
trace!("asked for slots unnecessarily, trying fast path");
let m = self.search(cache, input)?;
copy_match_to_slots(m, slots);
return Some(m.pattern());
}
// If the onepass DFA is available for this search (which only happens
// when it's anchored), then skip running a fallible DFA. The onepass
// DFA isn't as fast as a full or lazy DFA, but it is typically quite
// a bit faster than the backtracker or the PikeVM. So it isn't as
// advantageous to try and do a full/lazy DFA scan first.
//
// We still theorize that it's better to do a full/lazy DFA scan, even
// when it's anchored, because it's usually much faster and permits us
// to say "no match" much more quickly. This does hurt the case of,
// say, parsing each line in a log file into capture groups, because
// in that case, the line always matches. So the lazy DFA scan is
// usually just wasted work. But, the lazy DFA is usually quite fast
// and doesn't cost too much here.
if self.onepass.get(&input).is_some() {
return self.search_slots_nofail(cache, &input, slots);
}
let m = match self.try_search_mayfail(cache, input) {
Some(Ok(Some(m))) => m,
Some(Ok(None)) => return None,
Some(Err(_err)) => {
trace!("fast capture search failed: {}", _err);
return self.search_slots_nofail(cache, input, slots);
}
None => {
return self.search_slots_nofail(cache, input, slots);
}
};
// At this point, now that we've found the bounds of the
// match, we need to re-run something that can resolve
// capturing groups. But we only need to run on it on the
// match bounds and not the entire haystack.
trace!(
"match found at {}..{} in capture search, \
using another engine to find captures",
m.start(),
m.end(),
);
let input = input
.clone()
.span(m.start()..m.end())
.anchored(Anchored::Pattern(m.pattern()));
Some(
self.search_slots_nofail(cache, &input, slots)
.expect("should find a match"),
)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn which_overlapping_matches(
&self,
cache: &mut Cache,
input: &Input<'_>,
patset: &mut PatternSet,
) {
if let Some(e) = self.dfa.get(input) {
trace!(
"using full DFA for overlapping search at {:?}",
input.get_span()
);
let _err = match e.try_which_overlapping_matches(input, patset) {
Ok(()) => return,
Err(err) => err,
};
trace!("fast overlapping search failed: {}", _err);
} else if let Some(e) = self.hybrid.get(input) {
trace!(
"using lazy DFA for overlapping search at {:?}",
input.get_span()
);
let _err = match e.try_which_overlapping_matches(
&mut cache.hybrid,
input,
patset,
) {
Ok(()) => {
return;
}
Err(err) => err,
};
trace!("fast overlapping search failed: {}", _err);
}
trace!(
"using PikeVM for overlapping search at {:?}",
input.get_span()
);
let e = self.pikevm.get();
e.which_overlapping_matches(&mut cache.pikevm, input, patset)
}
}
#[derive(Debug)]
struct ReverseAnchored {
core: Core,
}
impl ReverseAnchored {
fn new(core: Core) -> Result<ReverseAnchored, Core> {
if !core.info.is_always_anchored_end() {
debug!(
"skipping reverse anchored optimization because \
the regex is not always anchored at the end"
);
return Err(core);
}
// Note that the caller can still request an anchored search even when
// the regex isn't anchored at the start. We detect that case in the
// search routines below and just fallback to the core engine. This
// is fine because both searches are anchored. It's just a matter of
// picking one. Falling back to the core engine is a little simpler,
// since if we used the reverse anchored approach, we'd have to add an
// extra check to ensure the match reported starts at the place where
// the caller requested the search to start.
if core.info.is_always_anchored_start() {
debug!(
"skipping reverse anchored optimization because \
the regex is also anchored at the start"
);
return Err(core);
}
// Only DFAs can do reverse searches (currently), so we need one of
// them in order to do this optimization. It's possible (although
// pretty unlikely) that we have neither and need to give up.
if !core.hybrid.is_some() && !core.dfa.is_some() {
debug!(
"skipping reverse anchored optimization because \
we don't have a lazy DFA or a full DFA"
);
return Err(core);
}
Ok(ReverseAnchored { core })
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn try_search_half_anchored_rev(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, RetryFailError> {
// We of course always want an anchored search. In theory, the
// underlying regex engines should automatically enable anchored
// searches since the regex is itself anchored, but this more clearly
// expresses intent and is always correct.
let input = input.clone().anchored(Anchored::Yes);
if let Some(e) = self.core.dfa.get(&input) {
trace!(
"using full DFA for reverse anchored search at {:?}",
input.get_span()
);
e.try_search_half_rev(&input)
} else if let Some(e) = self.core.hybrid.get(&input) {
trace!(
"using lazy DFA for reverse anchored search at {:?}",
input.get_span()
);
e.try_search_half_rev(&mut cache.hybrid, &input)
} else {
unreachable!("ReverseAnchored always has a DFA")
}
}
}
// Note that in this impl, we don't check that 'input.end() ==
// input.haystack().len()'. In particular, when that condition is false, a
// match is always impossible because we know that the regex is always anchored
// at the end (or else 'ReverseAnchored' won't be built). We don't check that
// here because the 'Regex' wrapper actually does that for us in all cases.
// Thus, in this impl, we can actually assume that the end position in 'input'
// is equivalent to the length of the haystack.
impl Strategy for ReverseAnchored {
#[cfg_attr(feature = "perf-inline", inline(always))]
fn group_info(&self) -> &GroupInfo {
self.core.group_info()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn create_cache(&self) -> Cache {
self.core.create_cache()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn reset_cache(&self, cache: &mut Cache) {
self.core.reset_cache(cache);
}
fn is_accelerated(&self) -> bool {
// Since this is anchored at the end, a reverse anchored search is
// almost certainly guaranteed to result in a much faster search than
// a standard forward search.
true
}
fn memory_usage(&self) -> usize {
self.core.memory_usage()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search(&self, cache: &mut Cache, input: &Input<'_>) -> Option<Match> {
if input.get_anchored().is_anchored() {
return self.core.search(cache, input);
}
match self.try_search_half_anchored_rev(cache, input) {
Err(_err) => {
trace!("fast reverse anchored search failed: {}", _err);
self.core.search_nofail(cache, input)
}
Ok(None) => None,
Ok(Some(hm)) => {
Some(Match::new(hm.pattern(), hm.offset()..input.end()))
}
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search_half(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<HalfMatch> {
if input.get_anchored().is_anchored() {
return self.core.search_half(cache, input);
}
match self.try_search_half_anchored_rev(cache, input) {
Err(_err) => {
trace!("fast reverse anchored search failed: {}", _err);
self.core.search_half_nofail(cache, input)
}
Ok(None) => None,
Ok(Some(hm)) => {
// Careful here! 'try_search_half' is a *forward* search that
// only cares about the *end* position of a match. But
// 'hm.offset()' is actually the start of the match. So we
// actually just throw that away here and, since we know we
// have a match, return the only possible position at which a
// match can occur: input.end().
Some(HalfMatch::new(hm.pattern(), input.end()))
}
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_match(&self, cache: &mut Cache, input: &Input<'_>) -> bool {
if input.get_anchored().is_anchored() {
return self.core.is_match(cache, input);
}
match self.try_search_half_anchored_rev(cache, input) {
Err(_err) => {
trace!("fast reverse anchored search failed: {}", _err);
self.core.is_match_nofail(cache, input)
}
Ok(None) => false,
Ok(Some(_)) => true,
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search_slots(
&self,
cache: &mut Cache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
if input.get_anchored().is_anchored() {
return self.core.search_slots(cache, input, slots);
}
match self.try_search_half_anchored_rev(cache, input) {
Err(_err) => {
trace!("fast reverse anchored search failed: {}", _err);
self.core.search_slots_nofail(cache, input, slots)
}
Ok(None) => None,
Ok(Some(hm)) => {
if !self.core.is_capture_search_needed(slots.len()) {
trace!("asked for slots unnecessarily, skipping captures");
let m = Match::new(hm.pattern(), hm.offset()..input.end());
copy_match_to_slots(m, slots);
return Some(m.pattern());
}
let start = hm.offset();
let input = input
.clone()
.span(start..input.end())
.anchored(Anchored::Pattern(hm.pattern()));
self.core.search_slots_nofail(cache, &input, slots)
}
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn which_overlapping_matches(
&self,
cache: &mut Cache,
input: &Input<'_>,
patset: &mut PatternSet,
) {
// It seems like this could probably benefit from a reverse anchored
// optimization, perhaps by doing an overlapping reverse search (which
// the DFAs do support). I haven't given it much thought though, and
// I'm currently focus more on the single pattern case.
self.core.which_overlapping_matches(cache, input, patset)
}
}
#[derive(Debug)]
struct ReverseSuffix {
core: Core,
pre: Prefilter,
}
impl ReverseSuffix {
fn new(core: Core, hirs: &[&Hir]) -> Result<ReverseSuffix, Core> {
if !core.info.config().get_auto_prefilter() {
debug!(
"skipping reverse suffix optimization because \
automatic prefilters are disabled"
);
return Err(core);
}
// Like the reverse inner optimization, we don't do this for regexes
// that are always anchored. It could lead to scanning too much, but
// could say "no match" much more quickly than running the regex
// engine if the initial literal scan doesn't match. With that said,
// the reverse suffix optimization has lower overhead, since it only
// requires a reverse scan after a literal match to confirm or reject
// the match. (Although, in the case of confirmation, it then needs to
// do another forward scan to find the end position.)
//
// Note that the caller can still request an anchored search even
// when the regex isn't anchored. We detect that case in the search
// routines below and just fallback to the core engine. Currently this
// optimization assumes all searches are unanchored, so if we do want
// to enable this optimization for anchored searches, it will need a
// little work to support it.
if core.info.is_always_anchored_start() {
debug!(
"skipping reverse suffix optimization because \
the regex is always anchored at the start",
);
return Err(core);
}
// Only DFAs can do reverse searches (currently), so we need one of
// them in order to do this optimization. It's possible (although
// pretty unlikely) that we have neither and need to give up.
if !core.hybrid.is_some() && !core.dfa.is_some() {
debug!(
"skipping reverse suffix optimization because \
we don't have a lazy DFA or a full DFA"
);
return Err(core);
}
if core.pre.as_ref().map_or(false, |p| p.is_fast()) {
debug!(
"skipping reverse suffix optimization because \
we already have a prefilter that we think is fast"
);
return Err(core);
}
let kind = core.info.config().get_match_kind();
let suffixes = crate::util::prefilter::suffixes(kind, hirs);
let lcs = match suffixes.longest_common_suffix() {
None => {
debug!(
"skipping reverse suffix optimization because \
a longest common suffix could not be found",
);
return Err(core);
}
Some(lcs) if lcs.is_empty() => {
debug!(
"skipping reverse suffix optimization because \
the longest common suffix is the empty string",
);
return Err(core);
}
Some(lcs) => lcs,
};
let pre = match Prefilter::new(kind, &[lcs]) {
Some(pre) => pre,
None => {
debug!(
"skipping reverse suffix optimization because \
a prefilter could not be constructed from the \
longest common suffix",
);
return Err(core);
}
};
if !pre.is_fast() {
debug!(
"skipping reverse suffix optimization because \
while we have a suffix prefilter, it is not \
believed to be 'fast'"
);
return Err(core);
}
Ok(ReverseSuffix { core, pre })
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn try_search_half_start(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, RetryError> {
let mut span = input.get_span();
let mut min_start = 0;
loop {
let litmatch = match self.pre.find(input.haystack(), span) {
None => return Ok(None),
Some(span) => span,
};
trace!("reverse suffix scan found suffix match at {:?}", litmatch);
let revinput = input
.clone()
.anchored(Anchored::Yes)
.span(input.start()..litmatch.end);
match self
.try_search_half_rev_limited(cache, &revinput, min_start)?
{
None => {
if span.start >= span.end {
break;
}
span.start = litmatch.start.checked_add(1).unwrap();
}
Some(hm) => return Ok(Some(hm)),
}
min_start = litmatch.end;
}
Ok(None)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn try_search_half_fwd(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, RetryFailError> {
if let Some(e) = self.core.dfa.get(&input) {
trace!(
"using full DFA for forward reverse suffix search at {:?}",
input.get_span()
);
e.try_search_half_fwd(&input)
} else if let Some(e) = self.core.hybrid.get(&input) {
trace!(
"using lazy DFA for forward reverse suffix search at {:?}",
input.get_span()
);
e.try_search_half_fwd(&mut cache.hybrid, &input)
} else {
unreachable!("ReverseSuffix always has a DFA")
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn try_search_half_rev_limited(
&self,
cache: &mut Cache,
input: &Input<'_>,
min_start: usize,
) -> Result<Option<HalfMatch>, RetryError> {
if let Some(e) = self.core.dfa.get(&input) {
trace!(
"using full DFA for reverse suffix search at {:?}, \
but will be stopped at {} to avoid quadratic behavior",
input.get_span(),
min_start,
);
e.try_search_half_rev_limited(&input, min_start)
} else if let Some(e) = self.core.hybrid.get(&input) {
trace!(
"using lazy DFA for reverse inner search at {:?}, \
but will be stopped at {} to avoid quadratic behavior",
input.get_span(),
min_start,
);
e.try_search_half_rev_limited(&mut cache.hybrid, &input, min_start)
} else {
unreachable!("ReverseSuffix always has a DFA")
}
}
}
impl Strategy for ReverseSuffix {
#[cfg_attr(feature = "perf-inline", inline(always))]
fn group_info(&self) -> &GroupInfo {
self.core.group_info()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn create_cache(&self) -> Cache {
self.core.create_cache()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn reset_cache(&self, cache: &mut Cache) {
self.core.reset_cache(cache);
}
fn is_accelerated(&self) -> bool {
self.pre.is_fast()
}
fn memory_usage(&self) -> usize {
self.core.memory_usage() + self.pre.memory_usage()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search(&self, cache: &mut Cache, input: &Input<'_>) -> Option<Match> {
if input.get_anchored().is_anchored() {
return self.core.search(cache, input);
}
match self.try_search_half_start(cache, input) {
Err(RetryError::Quadratic(_err)) => {
trace!("reverse suffix optimization failed: {}", _err);
self.core.search(cache, input)
}
Err(RetryError::Fail(_err)) => {
trace!("reverse suffix reverse fast search failed: {}", _err);
self.core.search_nofail(cache, input)
}
Ok(None) => None,
Ok(Some(hm_start)) => {
let fwdinput = input
.clone()
.anchored(Anchored::Pattern(hm_start.pattern()))
.span(hm_start.offset()..input.end());
match self.try_search_half_fwd(cache, &fwdinput) {
Err(_err) => {
trace!(
"reverse suffix forward fast search failed: {}",
_err
);
self.core.search_nofail(cache, input)
}
Ok(None) => {
unreachable!(
"suffix match plus reverse match implies \
there must be a match",
)
}
Ok(Some(hm_end)) => Some(Match::new(
hm_start.pattern(),
hm_start.offset()..hm_end.offset(),
)),
}
}
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search_half(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<HalfMatch> {
if input.get_anchored().is_anchored() {
return self.core.search_half(cache, input);
}
match self.try_search_half_start(cache, input) {
Err(RetryError::Quadratic(_err)) => {
trace!("reverse suffix half optimization failed: {}", _err);
self.core.search_half(cache, input)
}
Err(RetryError::Fail(_err)) => {
trace!(
"reverse suffix reverse fast half search failed: {}",
_err
);
self.core.search_half_nofail(cache, input)
}
Ok(None) => None,
Ok(Some(hm_start)) => {
// This is a bit subtle. It is tempting to just stop searching
// at this point and return a half-match with an offset
// corresponding to where the suffix was found. But the suffix
// match does not necessarily correspond to the end of the
// proper leftmost-first match. Consider /[a-z]+ing/ against
// 'tingling'. The first suffix match is the first 'ing', and
// the /[a-z]+/ matches the 't'. So if we stopped here, then
// we'd report 'ting' as the match. But 'tingling' is the
// correct match because of greediness.
let fwdinput = input
.clone()
.anchored(Anchored::Pattern(hm_start.pattern()))
.span(hm_start.offset()..input.end());
match self.try_search_half_fwd(cache, &fwdinput) {
Err(_err) => {
trace!(
"reverse suffix forward fast search failed: {}",
_err
);
self.core.search_half_nofail(cache, input)
}
Ok(None) => {
unreachable!(
"suffix match plus reverse match implies \
there must be a match",
)
}
Ok(Some(hm_end)) => Some(hm_end),
}
}
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_match(&self, cache: &mut Cache, input: &Input<'_>) -> bool {
if input.get_anchored().is_anchored() {
return self.core.is_match(cache, input);
}
match self.try_search_half_start(cache, input) {
Err(RetryError::Quadratic(_err)) => {
trace!("reverse suffix half optimization failed: {}", _err);
self.core.is_match_nofail(cache, input)
}
Err(RetryError::Fail(_err)) => {
trace!(
"reverse suffix reverse fast half search failed: {}",
_err
);
self.core.is_match_nofail(cache, input)
}
Ok(None) => false,
Ok(Some(_)) => true,
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search_slots(
&self,
cache: &mut Cache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
if input.get_anchored().is_anchored() {
return self.core.search_slots(cache, input, slots);
}
if !self.core.is_capture_search_needed(slots.len()) {
trace!("asked for slots unnecessarily, trying fast path");
let m = self.search(cache, input)?;
copy_match_to_slots(m, slots);
return Some(m.pattern());
}
let hm_start = match self.try_search_half_start(cache, input) {
Err(RetryError::Quadratic(_err)) => {
trace!(
"reverse suffix captures optimization failed: {}",
_err
);
return self.core.search_slots(cache, input, slots);
}
Err(RetryError::Fail(_err)) => {
trace!(
"reverse suffix reverse fast captures search failed: {}",
_err
);
return self.core.search_slots_nofail(cache, input, slots);
}
Ok(None) => return None,
Ok(Some(hm_start)) => hm_start,
};
trace!(
"match found at {}..{} in capture search, \
using another engine to find captures",
hm_start.offset(),
input.end(),
);
let start = hm_start.offset();
let input = input
.clone()
.span(start..input.end())
.anchored(Anchored::Pattern(hm_start.pattern()));
self.core.search_slots_nofail(cache, &input, slots)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn which_overlapping_matches(
&self,
cache: &mut Cache,
input: &Input<'_>,
patset: &mut PatternSet,
) {
self.core.which_overlapping_matches(cache, input, patset)
}
}
#[derive(Debug)]
struct ReverseInner {
core: Core,
preinner: Prefilter,
nfarev: NFA,
hybrid: wrappers::ReverseHybrid,
dfa: wrappers::ReverseDFA,
}
impl ReverseInner {
fn new(core: Core, hirs: &[&Hir]) -> Result<ReverseInner, Core> {
if !core.info.config().get_auto_prefilter() {
debug!(
"skipping reverse inner optimization because \
automatic prefilters are disabled"
);
return Err(core);
}
// Currently we hard-code the assumption of leftmost-first match
// semantics. This isn't a huge deal because 'all' semantics tend to
// only be used for forward overlapping searches with multiple regexes,
// and this optimization only supports a single pattern at the moment.
if core.info.config().get_match_kind() != MatchKind::LeftmostFirst {
debug!(
"skipping reverse inner optimization because \
match kind is {:?} but this only supports leftmost-first",
core.info.config().get_match_kind(),
);
return Err(core);
}
// It's likely that a reverse inner scan has too much overhead for it
// to be worth it when the regex is anchored at the start. It is
// possible for it to be quite a bit faster if the initial literal
// scan fails to detect a match, in which case, we can say "no match"
// very quickly. But this could be undesirable, e.g., scanning too far
// or when the literal scan matches. If it matches, then confirming the
// match requires a reverse scan followed by a forward scan to confirm
// or reject, which is a fair bit of work.
//
// Note that the caller can still request an anchored search even
// when the regex isn't anchored. We detect that case in the search
// routines below and just fallback to the core engine. Currently this
// optimization assumes all searches are unanchored, so if we do want
// to enable this optimization for anchored searches, it will need a
// little work to support it.
if core.info.is_always_anchored_start() {
debug!(
"skipping reverse inner optimization because \
the regex is always anchored at the start",
);
return Err(core);
}
// Only DFAs can do reverse searches (currently), so we need one of
// them in order to do this optimization. It's possible (although
// pretty unlikely) that we have neither and need to give up.
if !core.hybrid.is_some() && !core.dfa.is_some() {
debug!(
"skipping reverse inner optimization because \
we don't have a lazy DFA or a full DFA"
);
return Err(core);
}
if core.pre.as_ref().map_or(false, |p| p.is_fast()) {
debug!(
"skipping reverse inner optimization because \
we already have a prefilter that we think is fast"
);
return Err(core);
} else if core.pre.is_some() {
debug!(
"core engine has a prefix prefilter, but it is \
probably not fast, so continuing with attempt to \
use reverse inner prefilter"
);
}
let (concat_prefix, preinner) = match reverse_inner::extract(hirs) {
Some(x) => x,
// N.B. the 'extract' function emits debug messages explaining
// why we bailed out here.
None => return Err(core),
};
debug!("building reverse NFA for prefix before inner literal");
let mut lookm = LookMatcher::new();
lookm.set_line_terminator(core.info.config().get_line_terminator());
let thompson_config = thompson::Config::new()
.reverse(true)
.utf8(core.info.config().get_utf8_empty())
.nfa_size_limit(core.info.config().get_nfa_size_limit())
.shrink(false)
.which_captures(WhichCaptures::None)
.look_matcher(lookm);
let result = thompson::Compiler::new()
.configure(thompson_config)
.build_from_hir(&concat_prefix);
let nfarev = match result {
Ok(nfarev) => nfarev,
Err(_err) => {
debug!(
"skipping reverse inner optimization because the \
reverse NFA failed to build: {}",
_err,
);
return Err(core);
}
};
debug!("building reverse DFA for prefix before inner literal");
let dfa = if !core.info.config().get_dfa() {
wrappers::ReverseDFA::none()
} else {
wrappers::ReverseDFA::new(&core.info, &nfarev)
};
let hybrid = if !core.info.config().get_hybrid() {
wrappers::ReverseHybrid::none()
} else if dfa.is_some() {
debug!(
"skipping lazy DFA for reverse inner optimization \
because we have a full DFA"
);
wrappers::ReverseHybrid::none()
} else {
wrappers::ReverseHybrid::new(&core.info, &nfarev)
};
Ok(ReverseInner { core, preinner, nfarev, hybrid, dfa })
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn try_search_full(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Option<Match>, RetryError> {
let mut span = input.get_span();
let mut min_match_start = 0;
let mut min_pre_start = 0;
loop {
let litmatch = match self.preinner.find(input.haystack(), span) {
None => return Ok(None),
Some(span) => span,
};
if litmatch.start < min_pre_start {
trace!(
"found inner prefilter match at {:?}, which starts \
before the end of the last forward scan at {}, \
quitting to avoid quadratic behavior",
litmatch,
min_pre_start,
);
return Err(RetryError::Quadratic(RetryQuadraticError::new()));
}
trace!("reverse inner scan found inner match at {:?}", litmatch);
let revinput = input
.clone()
.anchored(Anchored::Yes)
.span(input.start()..litmatch.start);
// Note that in addition to the literal search above scanning past
// our minimum start point, this routine can also return an error
// as a result of detecting possible quadratic behavior if the
// reverse scan goes past the minimum start point. That is, the
// literal search might not, but the reverse regex search for the
// prefix might!
match self.try_search_half_rev_limited(
cache,
&revinput,
min_match_start,
)? {
None => {
if span.start >= span.end {
break;
}
span.start = litmatch.start.checked_add(1).unwrap();
}
Some(hm_start) => {
let fwdinput = input
.clone()
.anchored(Anchored::Pattern(hm_start.pattern()))
.span(hm_start.offset()..input.end());
match self.try_search_half_fwd_stopat(cache, &fwdinput)? {
Err(stopat) => {
min_pre_start = stopat;
span.start =
litmatch.start.checked_add(1).unwrap();
}
Ok(hm_end) => {
return Ok(Some(Match::new(
hm_start.pattern(),
hm_start.offset()..hm_end.offset(),
)))
}
}
}
}
min_match_start = litmatch.end;
}
Ok(None)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn try_search_half_fwd_stopat(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Result<Result<HalfMatch, usize>, RetryFailError> {
if let Some(e) = self.core.dfa.get(&input) {
trace!(
"using full DFA for forward reverse inner search at {:?}",
input.get_span()
);
e.try_search_half_fwd_stopat(&input)
} else if let Some(e) = self.core.hybrid.get(&input) {
trace!(
"using lazy DFA for forward reverse inner search at {:?}",
input.get_span()
);
e.try_search_half_fwd_stopat(&mut cache.hybrid, &input)
} else {
unreachable!("ReverseInner always has a DFA")
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn try_search_half_rev_limited(
&self,
cache: &mut Cache,
input: &Input<'_>,
min_start: usize,
) -> Result<Option<HalfMatch>, RetryError> {
if let Some(e) = self.dfa.get(&input) {
trace!(
"using full DFA for reverse inner search at {:?}, \
but will be stopped at {} to avoid quadratic behavior",
input.get_span(),
min_start,
);
e.try_search_half_rev_limited(&input, min_start)
} else if let Some(e) = self.hybrid.get(&input) {
trace!(
"using lazy DFA for reverse inner search at {:?}, \
but will be stopped at {} to avoid quadratic behavior",
input.get_span(),
min_start,
);
e.try_search_half_rev_limited(
&mut cache.revhybrid,
&input,
min_start,
)
} else {
unreachable!("ReverseInner always has a DFA")
}
}
}
impl Strategy for ReverseInner {
#[cfg_attr(feature = "perf-inline", inline(always))]
fn group_info(&self) -> &GroupInfo {
self.core.group_info()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn create_cache(&self) -> Cache {
let mut cache = self.core.create_cache();
cache.revhybrid = self.hybrid.create_cache();
cache
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn reset_cache(&self, cache: &mut Cache) {
self.core.reset_cache(cache);
cache.revhybrid.reset(&self.hybrid);
}
fn is_accelerated(&self) -> bool {
self.preinner.is_fast()
}
fn memory_usage(&self) -> usize {
self.core.memory_usage()
+ self.preinner.memory_usage()
+ self.nfarev.memory_usage()
+ self.dfa.memory_usage()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search(&self, cache: &mut Cache, input: &Input<'_>) -> Option<Match> {
if input.get_anchored().is_anchored() {
return self.core.search(cache, input);
}
match self.try_search_full(cache, input) {
Err(RetryError::Quadratic(_err)) => {
trace!("reverse inner optimization failed: {}", _err);
self.core.search(cache, input)
}
Err(RetryError::Fail(_err)) => {
trace!("reverse inner fast search failed: {}", _err);
self.core.search_nofail(cache, input)
}
Ok(matornot) => matornot,
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search_half(
&self,
cache: &mut Cache,
input: &Input<'_>,
) -> Option<HalfMatch> {
if input.get_anchored().is_anchored() {
return self.core.search_half(cache, input);
}
match self.try_search_full(cache, input) {
Err(RetryError::Quadratic(_err)) => {
trace!("reverse inner half optimization failed: {}", _err);
self.core.search_half(cache, input)
}
Err(RetryError::Fail(_err)) => {
trace!("reverse inner fast half search failed: {}", _err);
self.core.search_half_nofail(cache, input)
}
Ok(None) => None,
Ok(Some(m)) => Some(HalfMatch::new(m.pattern(), m.end())),
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn is_match(&self, cache: &mut Cache, input: &Input<'_>) -> bool {
if input.get_anchored().is_anchored() {
return self.core.is_match(cache, input);
}
match self.try_search_full(cache, input) {
Err(RetryError::Quadratic(_err)) => {
trace!("reverse inner half optimization failed: {}", _err);
self.core.is_match_nofail(cache, input)
}
Err(RetryError::Fail(_err)) => {
trace!("reverse inner fast half search failed: {}", _err);
self.core.is_match_nofail(cache, input)
}
Ok(None) => false,
Ok(Some(_)) => true,
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn search_slots(
&self,
cache: &mut Cache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
if input.get_anchored().is_anchored() {
return self.core.search_slots(cache, input, slots);
}
if !self.core.is_capture_search_needed(slots.len()) {
trace!("asked for slots unnecessarily, trying fast path");
let m = self.search(cache, input)?;
copy_match_to_slots(m, slots);
return Some(m.pattern());
}
let m = match self.try_search_full(cache, input) {
Err(RetryError::Quadratic(_err)) => {
trace!("reverse inner captures optimization failed: {}", _err);
return self.core.search_slots(cache, input, slots);
}
Err(RetryError::Fail(_err)) => {
trace!("reverse inner fast captures search failed: {}", _err);
return self.core.search_slots_nofail(cache, input, slots);
}
Ok(None) => return None,
Ok(Some(m)) => m,
};
trace!(
"match found at {}..{} in capture search, \
using another engine to find captures",
m.start(),
m.end(),
);
let input = input
.clone()
.span(m.start()..m.end())
.anchored(Anchored::Pattern(m.pattern()));
self.core.search_slots_nofail(cache, &input, slots)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn which_overlapping_matches(
&self,
cache: &mut Cache,
input: &Input<'_>,
patset: &mut PatternSet,
) {
self.core.which_overlapping_matches(cache, input, patset)
}
}
/// Copies the offsets in the given match to the corresponding positions in
/// `slots`.
///
/// In effect, this sets the slots corresponding to the implicit group for the
/// pattern in the given match. If the indices for the corresponding slots do
/// not exist, then no slots are set.
///
/// This is useful when the caller provides slots (or captures), but you use a
/// regex engine that doesn't operate on slots (like a lazy DFA). This function
/// lets you map the match you get back to the slots provided by the caller.
#[cfg_attr(feature = "perf-inline", inline(always))]
fn copy_match_to_slots(m: Match, slots: &mut [Option<NonMaxUsize>]) {
let slot_start = m.pattern().as_usize() * 2;
let slot_end = slot_start + 1;
if let Some(slot) = slots.get_mut(slot_start) {
*slot = NonMaxUsize::new(m.start());
}
if let Some(slot) = slots.get_mut(slot_end) {
*slot = NonMaxUsize::new(m.end());
}
}