Source code
Revision control
Copy as Markdown
Other Tools
/*!
This module contains a boat load of wrappers around each of our internal regex
engines. They encapsulate a few things:
1. The wrappers manage the conditional existence of the regex engine. Namely,
the PikeVM is the only required regex engine. The rest are optional. These
wrappers present a uniform API regardless of which engines are available. And
availability might be determined by compile time features or by dynamic
configuration via `meta::Config`. Encapsulating the conditional compilation
features is in particular a huge simplification for the higher level code that
composes these engines.
2. The wrappers manage construction of each engine, including skipping it if
the engine is unavailable or configured to not be used.
3. The wrappers manage whether an engine *can* be used for a particular
search configuration. For example, `BoundedBacktracker::get` only returns a
backtracking engine when the haystack is bigger than the maximum supported
length. The wrappers also sometimes take a position on when an engine *ought*
to be used, but only in cases where the logic is extremely local to the engine
itself. Otherwise, things like "choose between the backtracker and the one-pass
DFA" are managed by the higher level meta strategy code.
There are also corresponding wrappers for the various `Cache` types for each
regex engine that needs them. If an engine is unavailable or not used, then a
cache for it will *not* actually be allocated.
*/
use alloc::vec::Vec;
use crate::{
meta::{
error::{BuildError, RetryError, RetryFailError},
regex::RegexInfo,
},
nfa::thompson::{pikevm, NFA},
util::{prefilter::Prefilter, primitives::NonMaxUsize},
HalfMatch, Input, Match, MatchKind, PatternID, PatternSet,
};
#[cfg(feature = "dfa-build")]
use crate::dfa;
#[cfg(feature = "dfa-onepass")]
use crate::dfa::onepass;
#[cfg(feature = "hybrid")]
use crate::hybrid;
#[cfg(feature = "nfa-backtrack")]
use crate::nfa::thompson::backtrack;
#[derive(Debug)]
pub(crate) struct PikeVM(PikeVMEngine);
impl PikeVM {
pub(crate) fn new(
info: &RegexInfo,
pre: Option<Prefilter>,
nfa: &NFA,
) -> Result<PikeVM, BuildError> {
PikeVMEngine::new(info, pre, nfa).map(PikeVM)
}
pub(crate) fn create_cache(&self) -> PikeVMCache {
PikeVMCache::new(self)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn get(&self) -> &PikeVMEngine {
&self.0
}
}
#[derive(Debug)]
pub(crate) struct PikeVMEngine(pikevm::PikeVM);
impl PikeVMEngine {
pub(crate) fn new(
info: &RegexInfo,
pre: Option<Prefilter>,
nfa: &NFA,
) -> Result<PikeVMEngine, BuildError> {
let pikevm_config = pikevm::Config::new()
.match_kind(info.config().get_match_kind())
.prefilter(pre);
let engine = pikevm::Builder::new()
.configure(pikevm_config)
.build_from_nfa(nfa.clone())
.map_err(BuildError::nfa)?;
debug!("PikeVM built");
Ok(PikeVMEngine(engine))
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn is_match(
&self,
cache: &mut PikeVMCache,
input: &Input<'_>,
) -> bool {
self.0.is_match(cache.0.as_mut().unwrap(), input.clone())
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn search_slots(
&self,
cache: &mut PikeVMCache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
self.0.search_slots(cache.0.as_mut().unwrap(), input, slots)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn which_overlapping_matches(
&self,
cache: &mut PikeVMCache,
input: &Input<'_>,
patset: &mut PatternSet,
) {
self.0.which_overlapping_matches(
cache.0.as_mut().unwrap(),
input,
patset,
)
}
}
#[derive(Clone, Debug)]
pub(crate) struct PikeVMCache(Option<pikevm::Cache>);
impl PikeVMCache {
pub(crate) fn none() -> PikeVMCache {
PikeVMCache(None)
}
pub(crate) fn new(builder: &PikeVM) -> PikeVMCache {
PikeVMCache(Some(builder.get().0.create_cache()))
}
pub(crate) fn reset(&mut self, builder: &PikeVM) {
self.0.as_mut().unwrap().reset(&builder.get().0);
}
pub(crate) fn memory_usage(&self) -> usize {
self.0.as_ref().map_or(0, |c| c.memory_usage())
}
}
#[derive(Debug)]
pub(crate) struct BoundedBacktracker(Option<BoundedBacktrackerEngine>);
impl BoundedBacktracker {
pub(crate) fn new(
info: &RegexInfo,
pre: Option<Prefilter>,
nfa: &NFA,
) -> Result<BoundedBacktracker, BuildError> {
BoundedBacktrackerEngine::new(info, pre, nfa).map(BoundedBacktracker)
}
pub(crate) fn create_cache(&self) -> BoundedBacktrackerCache {
BoundedBacktrackerCache::new(self)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn get(
&self,
input: &Input<'_>,
) -> Option<&BoundedBacktrackerEngine> {
let engine = self.0.as_ref()?;
// It is difficult to make the backtracker give up early if it is
// guaranteed to eventually wind up in a match state. This is because
// of the greedy nature of a backtracker: it just blindly mushes
// forward. Every other regex engine is able to give up more quickly,
// so even if the backtracker might be able to zip through faster than
// (say) the PikeVM, we prefer the theoretical benefit that some other
// engine might be able to scan much less of the haystack than the
// backtracker.
//
// Now, if the haystack is really short already, then we allow the
// backtracker to run. (This hasn't been litigated quantitatively with
// benchmarks. Just a hunch.)
if input.get_earliest() && input.haystack().len() > 128 {
return None;
}
// If the backtracker is just going to return an error because the
// haystack is too long, then obviously do not use it.
if input.get_span().len() > engine.max_haystack_len() {
return None;
}
Some(engine)
}
}
#[derive(Debug)]
pub(crate) struct BoundedBacktrackerEngine(
#[cfg(feature = "nfa-backtrack")] backtrack::BoundedBacktracker,
#[cfg(not(feature = "nfa-backtrack"))] (),
);
impl BoundedBacktrackerEngine {
pub(crate) fn new(
info: &RegexInfo,
pre: Option<Prefilter>,
nfa: &NFA,
) -> Result<Option<BoundedBacktrackerEngine>, BuildError> {
#[cfg(feature = "nfa-backtrack")]
{
if !info.config().get_backtrack()
|| info.config().get_match_kind() != MatchKind::LeftmostFirst
{
return Ok(None);
}
let backtrack_config = backtrack::Config::new().prefilter(pre);
let engine = backtrack::Builder::new()
.configure(backtrack_config)
.build_from_nfa(nfa.clone())
.map_err(BuildError::nfa)?;
debug!("BoundedBacktracker built");
Ok(Some(BoundedBacktrackerEngine(engine)))
}
#[cfg(not(feature = "nfa-backtrack"))]
{
Ok(None)
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn is_match(
&self,
cache: &mut BoundedBacktrackerCache,
input: &Input<'_>,
) -> bool {
#[cfg(feature = "nfa-backtrack")]
{
// OK because we only permit access to this engine when we know
// the haystack is short enough for the backtracker to run without
// reporting an error.
self.0
.try_is_match(cache.0.as_mut().unwrap(), input.clone())
.unwrap()
}
#[cfg(not(feature = "nfa-backtrack"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn search_slots(
&self,
cache: &mut BoundedBacktrackerCache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
#[cfg(feature = "nfa-backtrack")]
{
// OK because we only permit access to this engine when we know
// the haystack is short enough for the backtracker to run without
// reporting an error.
self.0
.try_search_slots(cache.0.as_mut().unwrap(), input, slots)
.unwrap()
}
#[cfg(not(feature = "nfa-backtrack"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn max_haystack_len(&self) -> usize {
#[cfg(feature = "nfa-backtrack")]
{
self.0.max_haystack_len()
}
#[cfg(not(feature = "nfa-backtrack"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
}
#[derive(Clone, Debug)]
pub(crate) struct BoundedBacktrackerCache(
#[cfg(feature = "nfa-backtrack")] Option<backtrack::Cache>,
#[cfg(not(feature = "nfa-backtrack"))] (),
);
impl BoundedBacktrackerCache {
pub(crate) fn none() -> BoundedBacktrackerCache {
#[cfg(feature = "nfa-backtrack")]
{
BoundedBacktrackerCache(None)
}
#[cfg(not(feature = "nfa-backtrack"))]
{
BoundedBacktrackerCache(())
}
}
pub(crate) fn new(
builder: &BoundedBacktracker,
) -> BoundedBacktrackerCache {
#[cfg(feature = "nfa-backtrack")]
{
BoundedBacktrackerCache(
builder.0.as_ref().map(|e| e.0.create_cache()),
)
}
#[cfg(not(feature = "nfa-backtrack"))]
{
BoundedBacktrackerCache(())
}
}
pub(crate) fn reset(&mut self, builder: &BoundedBacktracker) {
#[cfg(feature = "nfa-backtrack")]
if let Some(ref e) = builder.0 {
self.0.as_mut().unwrap().reset(&e.0);
}
}
pub(crate) fn memory_usage(&self) -> usize {
#[cfg(feature = "nfa-backtrack")]
{
self.0.as_ref().map_or(0, |c| c.memory_usage())
}
#[cfg(not(feature = "nfa-backtrack"))]
{
0
}
}
}
#[derive(Debug)]
pub(crate) struct OnePass(Option<OnePassEngine>);
impl OnePass {
pub(crate) fn new(info: &RegexInfo, nfa: &NFA) -> OnePass {
OnePass(OnePassEngine::new(info, nfa))
}
pub(crate) fn create_cache(&self) -> OnePassCache {
OnePassCache::new(self)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn get(&self, input: &Input<'_>) -> Option<&OnePassEngine> {
let engine = self.0.as_ref()?;
if !input.get_anchored().is_anchored()
&& !engine.get_nfa().is_always_start_anchored()
{
return None;
}
Some(engine)
}
pub(crate) fn memory_usage(&self) -> usize {
self.0.as_ref().map_or(0, |e| e.memory_usage())
}
}
#[derive(Debug)]
pub(crate) struct OnePassEngine(
#[cfg(feature = "dfa-onepass")] onepass::DFA,
#[cfg(not(feature = "dfa-onepass"))] (),
);
impl OnePassEngine {
pub(crate) fn new(info: &RegexInfo, nfa: &NFA) -> Option<OnePassEngine> {
#[cfg(feature = "dfa-onepass")]
{
if !info.config().get_onepass() {
return None;
}
// In order to even attempt building a one-pass DFA, we require
// that we either have at least one explicit capturing group or
// there's a Unicode word boundary somewhere. If we don't have
// either of these things, then the lazy DFA will almost certainly
// be useable and be much faster. The only case where it might
// not is if the lazy DFA isn't utilizing its cache effectively,
// but in those cases, the underlying regex is almost certainly
// not one-pass or is too big to fit within the current one-pass
// implementation limits.
if info.props_union().explicit_captures_len() == 0
&& !info.props_union().look_set().contains_word_unicode()
{
debug!("not building OnePass because it isn't worth it");
return None;
}
let onepass_config = onepass::Config::new()
.match_kind(info.config().get_match_kind())
// Like for the lazy DFA, we unconditionally enable this
// because it doesn't cost much and makes the API more
// flexible.
.starts_for_each_pattern(true)
.byte_classes(info.config().get_byte_classes())
.size_limit(info.config().get_onepass_size_limit());
let result = onepass::Builder::new()
.configure(onepass_config)
.build_from_nfa(nfa.clone());
let engine = match result {
Ok(engine) => engine,
Err(_err) => {
debug!("OnePass failed to build: {}", _err);
return None;
}
};
debug!("OnePass built, {} bytes", engine.memory_usage());
Some(OnePassEngine(engine))
}
#[cfg(not(feature = "dfa-onepass"))]
{
None
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn search_slots(
&self,
cache: &mut OnePassCache,
input: &Input<'_>,
slots: &mut [Option<NonMaxUsize>],
) -> Option<PatternID> {
#[cfg(feature = "dfa-onepass")]
{
// OK because we only permit getting a OnePassEngine when we know
// the search is anchored and thus an error cannot occur.
self.0
.try_search_slots(cache.0.as_mut().unwrap(), input, slots)
.unwrap()
}
#[cfg(not(feature = "dfa-onepass"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
pub(crate) fn memory_usage(&self) -> usize {
#[cfg(feature = "dfa-onepass")]
{
self.0.memory_usage()
}
#[cfg(not(feature = "dfa-onepass"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn get_nfa(&self) -> &NFA {
#[cfg(feature = "dfa-onepass")]
{
self.0.get_nfa()
}
#[cfg(not(feature = "dfa-onepass"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
}
#[derive(Clone, Debug)]
pub(crate) struct OnePassCache(
#[cfg(feature = "dfa-onepass")] Option<onepass::Cache>,
#[cfg(not(feature = "dfa-onepass"))] (),
);
impl OnePassCache {
pub(crate) fn none() -> OnePassCache {
#[cfg(feature = "dfa-onepass")]
{
OnePassCache(None)
}
#[cfg(not(feature = "dfa-onepass"))]
{
OnePassCache(())
}
}
pub(crate) fn new(builder: &OnePass) -> OnePassCache {
#[cfg(feature = "dfa-onepass")]
{
OnePassCache(builder.0.as_ref().map(|e| e.0.create_cache()))
}
#[cfg(not(feature = "dfa-onepass"))]
{
OnePassCache(())
}
}
pub(crate) fn reset(&mut self, builder: &OnePass) {
#[cfg(feature = "dfa-onepass")]
if let Some(ref e) = builder.0 {
self.0.as_mut().unwrap().reset(&e.0);
}
}
pub(crate) fn memory_usage(&self) -> usize {
#[cfg(feature = "dfa-onepass")]
{
self.0.as_ref().map_or(0, |c| c.memory_usage())
}
#[cfg(not(feature = "dfa-onepass"))]
{
0
}
}
}
#[derive(Debug)]
pub(crate) struct Hybrid(Option<HybridEngine>);
impl Hybrid {
pub(crate) fn none() -> Hybrid {
Hybrid(None)
}
pub(crate) fn new(
info: &RegexInfo,
pre: Option<Prefilter>,
nfa: &NFA,
nfarev: &NFA,
) -> Hybrid {
Hybrid(HybridEngine::new(info, pre, nfa, nfarev))
}
pub(crate) fn create_cache(&self) -> HybridCache {
HybridCache::new(self)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn get(&self, _input: &Input<'_>) -> Option<&HybridEngine> {
let engine = self.0.as_ref()?;
Some(engine)
}
pub(crate) fn is_some(&self) -> bool {
self.0.is_some()
}
}
#[derive(Debug)]
pub(crate) struct HybridEngine(
#[cfg(feature = "hybrid")] hybrid::regex::Regex,
#[cfg(not(feature = "hybrid"))] (),
);
impl HybridEngine {
pub(crate) fn new(
info: &RegexInfo,
pre: Option<Prefilter>,
nfa: &NFA,
nfarev: &NFA,
) -> Option<HybridEngine> {
#[cfg(feature = "hybrid")]
{
if !info.config().get_hybrid() {
return None;
}
let dfa_config = hybrid::dfa::Config::new()
.match_kind(info.config().get_match_kind())
.prefilter(pre.clone())
// Enabling this is necessary for ensuring we can service any
// kind of 'Input' search without error. For the lazy DFA,
// this is not particularly costly, since the start states are
// generated lazily.
.starts_for_each_pattern(true)
.byte_classes(info.config().get_byte_classes())
.unicode_word_boundary(true)
.specialize_start_states(pre.is_some())
.cache_capacity(info.config().get_hybrid_cache_capacity())
// This makes it possible for building a lazy DFA to
// fail even though the NFA has already been built. Namely,
// if the cache capacity is too small to fit some minimum
// number of states (which is small, like 4 or 5), then the
// DFA will refuse to build.
//
// We shouldn't enable this to make building always work, since
// this could cause the allocation of a cache bigger than the
// provided capacity amount.
//
// This is effectively the only reason why building a lazy DFA
// could fail. If it does, then we simply suppress the error
// and return None.
.skip_cache_capacity_check(false)
// This and enabling heuristic Unicode word boundary support
// above make it so the lazy DFA can quit at match time.
.minimum_cache_clear_count(Some(3))
.minimum_bytes_per_state(Some(10));
let result = hybrid::dfa::Builder::new()
.configure(dfa_config.clone())
.build_from_nfa(nfa.clone());
let fwd = match result {
Ok(fwd) => fwd,
Err(_err) => {
debug!("forward lazy DFA failed to build: {}", _err);
return None;
}
};
let result = hybrid::dfa::Builder::new()
.configure(
dfa_config
.clone()
.match_kind(MatchKind::All)
.prefilter(None)
.specialize_start_states(false),
)
.build_from_nfa(nfarev.clone());
let rev = match result {
Ok(rev) => rev,
Err(_err) => {
debug!("reverse lazy DFA failed to build: {}", _err);
return None;
}
};
let engine =
hybrid::regex::Builder::new().build_from_dfas(fwd, rev);
debug!("lazy DFA built");
Some(HybridEngine(engine))
}
#[cfg(not(feature = "hybrid"))]
{
None
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search(
&self,
cache: &mut HybridCache,
input: &Input<'_>,
) -> Result<Option<Match>, RetryFailError> {
#[cfg(feature = "hybrid")]
{
let cache = cache.0.as_mut().unwrap();
self.0.try_search(cache, input).map_err(|e| e.into())
}
#[cfg(not(feature = "hybrid"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_fwd(
&self,
cache: &mut HybridCache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, RetryFailError> {
#[cfg(feature = "hybrid")]
{
let fwd = self.0.forward();
let mut fwdcache = cache.0.as_mut().unwrap().as_parts_mut().0;
fwd.try_search_fwd(&mut fwdcache, input).map_err(|e| e.into())
}
#[cfg(not(feature = "hybrid"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_fwd_stopat(
&self,
cache: &mut HybridCache,
input: &Input<'_>,
) -> Result<Result<HalfMatch, usize>, RetryFailError> {
#[cfg(feature = "hybrid")]
{
let dfa = self.0.forward();
let mut cache = cache.0.as_mut().unwrap().as_parts_mut().0;
crate::meta::stopat::hybrid_try_search_half_fwd(
dfa, &mut cache, input,
)
}
#[cfg(not(feature = "hybrid"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_rev(
&self,
cache: &mut HybridCache,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, RetryFailError> {
#[cfg(feature = "hybrid")]
{
let rev = self.0.reverse();
let mut revcache = cache.0.as_mut().unwrap().as_parts_mut().1;
rev.try_search_rev(&mut revcache, input).map_err(|e| e.into())
}
#[cfg(not(feature = "hybrid"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_rev_limited(
&self,
cache: &mut HybridCache,
input: &Input<'_>,
min_start: usize,
) -> Result<Option<HalfMatch>, RetryError> {
#[cfg(feature = "hybrid")]
{
let dfa = self.0.reverse();
let mut cache = cache.0.as_mut().unwrap().as_parts_mut().1;
crate::meta::limited::hybrid_try_search_half_rev(
dfa, &mut cache, input, min_start,
)
}
#[cfg(not(feature = "hybrid"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[inline]
pub(crate) fn try_which_overlapping_matches(
&self,
cache: &mut HybridCache,
input: &Input<'_>,
patset: &mut PatternSet,
) -> Result<(), RetryFailError> {
#[cfg(feature = "hybrid")]
{
let fwd = self.0.forward();
let mut fwdcache = cache.0.as_mut().unwrap().as_parts_mut().0;
fwd.try_which_overlapping_matches(&mut fwdcache, input, patset)
.map_err(|e| e.into())
}
#[cfg(not(feature = "hybrid"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
}
#[derive(Clone, Debug)]
pub(crate) struct HybridCache(
#[cfg(feature = "hybrid")] Option<hybrid::regex::Cache>,
#[cfg(not(feature = "hybrid"))] (),
);
impl HybridCache {
pub(crate) fn none() -> HybridCache {
#[cfg(feature = "hybrid")]
{
HybridCache(None)
}
#[cfg(not(feature = "hybrid"))]
{
HybridCache(())
}
}
pub(crate) fn new(builder: &Hybrid) -> HybridCache {
#[cfg(feature = "hybrid")]
{
HybridCache(builder.0.as_ref().map(|e| e.0.create_cache()))
}
#[cfg(not(feature = "hybrid"))]
{
HybridCache(())
}
}
pub(crate) fn reset(&mut self, builder: &Hybrid) {
#[cfg(feature = "hybrid")]
if let Some(ref e) = builder.0 {
self.0.as_mut().unwrap().reset(&e.0);
}
}
pub(crate) fn memory_usage(&self) -> usize {
#[cfg(feature = "hybrid")]
{
self.0.as_ref().map_or(0, |c| c.memory_usage())
}
#[cfg(not(feature = "hybrid"))]
{
0
}
}
}
#[derive(Debug)]
pub(crate) struct DFA(Option<DFAEngine>);
impl DFA {
pub(crate) fn none() -> DFA {
DFA(None)
}
pub(crate) fn new(
info: &RegexInfo,
pre: Option<Prefilter>,
nfa: &NFA,
nfarev: &NFA,
) -> DFA {
DFA(DFAEngine::new(info, pre, nfa, nfarev))
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn get(&self, _input: &Input<'_>) -> Option<&DFAEngine> {
let engine = self.0.as_ref()?;
Some(engine)
}
pub(crate) fn is_some(&self) -> bool {
self.0.is_some()
}
pub(crate) fn memory_usage(&self) -> usize {
self.0.as_ref().map_or(0, |e| e.memory_usage())
}
}
#[derive(Debug)]
pub(crate) struct DFAEngine(
#[cfg(feature = "dfa-build")] dfa::regex::Regex,
#[cfg(not(feature = "dfa-build"))] (),
);
impl DFAEngine {
pub(crate) fn new(
info: &RegexInfo,
pre: Option<Prefilter>,
nfa: &NFA,
nfarev: &NFA,
) -> Option<DFAEngine> {
#[cfg(feature = "dfa-build")]
{
if !info.config().get_dfa() {
return None;
}
// If our NFA is anything but small, don't even bother with a DFA.
if let Some(state_limit) = info.config().get_dfa_state_limit() {
if nfa.states().len() > state_limit {
debug!(
"skipping full DFA because NFA has {} states, \
which exceeds the heuristic limit of {}",
nfa.states().len(),
state_limit,
);
return None;
}
}
// We cut the size limit in four because the total heap used by
// DFA construction is determinization aux memory and the DFA
// itself, and those things are configured independently in the
// lower level DFA builder API. And then split that in two because
// of forward and reverse DFAs.
let size_limit = info.config().get_dfa_size_limit().map(|n| n / 4);
let dfa_config = dfa::dense::Config::new()
.match_kind(info.config().get_match_kind())
.prefilter(pre.clone())
// Enabling this is necessary for ensuring we can service any
// kind of 'Input' search without error. For the full DFA, this
// can be quite costly. But since we have such a small bound
// on the size of the DFA, in practice, any multl-regexes are
// probably going to blow the limit anyway.
.starts_for_each_pattern(true)
.byte_classes(info.config().get_byte_classes())
.unicode_word_boundary(true)
.specialize_start_states(pre.is_some())
.determinize_size_limit(size_limit)
.dfa_size_limit(size_limit);
let result = dfa::dense::Builder::new()
.configure(dfa_config.clone())
.build_from_nfa(&nfa);
let fwd = match result {
Ok(fwd) => fwd,
Err(_err) => {
debug!("forward full DFA failed to build: {}", _err);
return None;
}
};
let result = dfa::dense::Builder::new()
.configure(
dfa_config
.clone()
// We never need unanchored reverse searches, so
// there's no point in building it into the DFA, which
// WILL take more space. (This isn't done for the lazy
// DFA because the DFA is, well, lazy. It doesn't pay
// the cost for supporting unanchored searches unless
// you actually do an unanchored search, which we
// don't.)
.start_kind(dfa::StartKind::Anchored)
.match_kind(MatchKind::All)
.prefilter(None)
.specialize_start_states(false),
)
.build_from_nfa(&nfarev);
let rev = match result {
Ok(rev) => rev,
Err(_err) => {
debug!("reverse full DFA failed to build: {}", _err);
return None;
}
};
let engine = dfa::regex::Builder::new().build_from_dfas(fwd, rev);
debug!(
"fully compiled forward and reverse DFAs built, {} bytes",
engine.forward().memory_usage()
+ engine.reverse().memory_usage(),
);
Some(DFAEngine(engine))
}
#[cfg(not(feature = "dfa-build"))]
{
None
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search(
&self,
input: &Input<'_>,
) -> Result<Option<Match>, RetryFailError> {
#[cfg(feature = "dfa-build")]
{
self.0.try_search(input).map_err(|e| e.into())
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_fwd(
&self,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, RetryFailError> {
#[cfg(feature = "dfa-build")]
{
use crate::dfa::Automaton;
self.0.forward().try_search_fwd(input).map_err(|e| e.into())
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_fwd_stopat(
&self,
input: &Input<'_>,
) -> Result<Result<HalfMatch, usize>, RetryFailError> {
#[cfg(feature = "dfa-build")]
{
let dfa = self.0.forward();
crate::meta::stopat::dfa_try_search_half_fwd(dfa, input)
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_rev(
&self,
input: &Input<'_>,
) -> Result<Option<HalfMatch>, RetryFailError> {
#[cfg(feature = "dfa-build")]
{
use crate::dfa::Automaton;
self.0.reverse().try_search_rev(&input).map_err(|e| e.into())
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_rev_limited(
&self,
input: &Input<'_>,
min_start: usize,
) -> Result<Option<HalfMatch>, RetryError> {
#[cfg(feature = "dfa-build")]
{
let dfa = self.0.reverse();
crate::meta::limited::dfa_try_search_half_rev(
dfa, input, min_start,
)
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
#[inline]
pub(crate) fn try_which_overlapping_matches(
&self,
input: &Input<'_>,
patset: &mut PatternSet,
) -> Result<(), RetryFailError> {
#[cfg(feature = "dfa-build")]
{
use crate::dfa::Automaton;
self.0
.forward()
.try_which_overlapping_matches(input, patset)
.map_err(|e| e.into())
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
pub(crate) fn memory_usage(&self) -> usize {
#[cfg(feature = "dfa-build")]
{
self.0.forward().memory_usage() + self.0.reverse().memory_usage()
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
}
#[derive(Debug)]
pub(crate) struct ReverseHybrid(Option<ReverseHybridEngine>);
impl ReverseHybrid {
pub(crate) fn none() -> ReverseHybrid {
ReverseHybrid(None)
}
pub(crate) fn new(info: &RegexInfo, nfarev: &NFA) -> ReverseHybrid {
ReverseHybrid(ReverseHybridEngine::new(info, nfarev))
}
pub(crate) fn create_cache(&self) -> ReverseHybridCache {
ReverseHybridCache::new(self)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn get(
&self,
_input: &Input<'_>,
) -> Option<&ReverseHybridEngine> {
let engine = self.0.as_ref()?;
Some(engine)
}
}
#[derive(Debug)]
pub(crate) struct ReverseHybridEngine(
#[cfg(feature = "hybrid")] hybrid::dfa::DFA,
#[cfg(not(feature = "hybrid"))] (),
);
impl ReverseHybridEngine {
pub(crate) fn new(
info: &RegexInfo,
nfarev: &NFA,
) -> Option<ReverseHybridEngine> {
#[cfg(feature = "hybrid")]
{
if !info.config().get_hybrid() {
return None;
}
// Since we only use this for reverse searches, we can hard-code
// a number of things like match semantics, prefilters, starts
// for each pattern and so on.
let dfa_config = hybrid::dfa::Config::new()
.match_kind(MatchKind::All)
.prefilter(None)
.starts_for_each_pattern(false)
.byte_classes(info.config().get_byte_classes())
.unicode_word_boundary(true)
.specialize_start_states(false)
.cache_capacity(info.config().get_hybrid_cache_capacity())
.skip_cache_capacity_check(false)
.minimum_cache_clear_count(Some(3))
.minimum_bytes_per_state(Some(10));
let result = hybrid::dfa::Builder::new()
.configure(dfa_config)
.build_from_nfa(nfarev.clone());
let rev = match result {
Ok(rev) => rev,
Err(_err) => {
debug!("lazy reverse DFA failed to build: {}", _err);
return None;
}
};
debug!("lazy reverse DFA built");
Some(ReverseHybridEngine(rev))
}
#[cfg(not(feature = "hybrid"))]
{
None
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_rev_limited(
&self,
cache: &mut ReverseHybridCache,
input: &Input<'_>,
min_start: usize,
) -> Result<Option<HalfMatch>, RetryError> {
#[cfg(feature = "hybrid")]
{
let dfa = &self.0;
let mut cache = cache.0.as_mut().unwrap();
crate::meta::limited::hybrid_try_search_half_rev(
dfa, &mut cache, input, min_start,
)
}
#[cfg(not(feature = "hybrid"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
}
#[derive(Clone, Debug)]
pub(crate) struct ReverseHybridCache(
#[cfg(feature = "hybrid")] Option<hybrid::dfa::Cache>,
#[cfg(not(feature = "hybrid"))] (),
);
impl ReverseHybridCache {
pub(crate) fn none() -> ReverseHybridCache {
#[cfg(feature = "hybrid")]
{
ReverseHybridCache(None)
}
#[cfg(not(feature = "hybrid"))]
{
ReverseHybridCache(())
}
}
pub(crate) fn new(builder: &ReverseHybrid) -> ReverseHybridCache {
#[cfg(feature = "hybrid")]
{
ReverseHybridCache(builder.0.as_ref().map(|e| e.0.create_cache()))
}
#[cfg(not(feature = "hybrid"))]
{
ReverseHybridCache(())
}
}
pub(crate) fn reset(&mut self, builder: &ReverseHybrid) {
#[cfg(feature = "hybrid")]
if let Some(ref e) = builder.0 {
self.0.as_mut().unwrap().reset(&e.0);
}
}
pub(crate) fn memory_usage(&self) -> usize {
#[cfg(feature = "hybrid")]
{
self.0.as_ref().map_or(0, |c| c.memory_usage())
}
#[cfg(not(feature = "hybrid"))]
{
0
}
}
}
#[derive(Debug)]
pub(crate) struct ReverseDFA(Option<ReverseDFAEngine>);
impl ReverseDFA {
pub(crate) fn none() -> ReverseDFA {
ReverseDFA(None)
}
pub(crate) fn new(info: &RegexInfo, nfarev: &NFA) -> ReverseDFA {
ReverseDFA(ReverseDFAEngine::new(info, nfarev))
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn get(&self, _input: &Input<'_>) -> Option<&ReverseDFAEngine> {
let engine = self.0.as_ref()?;
Some(engine)
}
pub(crate) fn is_some(&self) -> bool {
self.0.is_some()
}
pub(crate) fn memory_usage(&self) -> usize {
self.0.as_ref().map_or(0, |e| e.memory_usage())
}
}
#[derive(Debug)]
pub(crate) struct ReverseDFAEngine(
#[cfg(feature = "dfa-build")] dfa::dense::DFA<Vec<u32>>,
#[cfg(not(feature = "dfa-build"))] (),
);
impl ReverseDFAEngine {
pub(crate) fn new(
info: &RegexInfo,
nfarev: &NFA,
) -> Option<ReverseDFAEngine> {
#[cfg(feature = "dfa-build")]
{
if !info.config().get_dfa() {
return None;
}
// If our NFA is anything but small, don't even bother with a DFA.
if let Some(state_limit) = info.config().get_dfa_state_limit() {
if nfarev.states().len() > state_limit {
debug!(
"skipping full reverse DFA because NFA has {} states, \
which exceeds the heuristic limit of {}",
nfarev.states().len(),
state_limit,
);
return None;
}
}
// We cut the size limit in two because the total heap used by DFA
// construction is determinization aux memory and the DFA itself,
// and those things are configured independently in the lower level
// DFA builder API.
let size_limit = info.config().get_dfa_size_limit().map(|n| n / 2);
// Since we only use this for reverse searches, we can hard-code
// a number of things like match semantics, prefilters, starts
// for each pattern and so on. We also disable acceleration since
// it's incompatible with limited searches (which is the only
// operation we support for this kind of engine at the moment).
let dfa_config = dfa::dense::Config::new()
.match_kind(MatchKind::All)
.prefilter(None)
.accelerate(false)
.start_kind(dfa::StartKind::Anchored)
.starts_for_each_pattern(false)
.byte_classes(info.config().get_byte_classes())
.unicode_word_boundary(true)
.specialize_start_states(false)
.determinize_size_limit(size_limit)
.dfa_size_limit(size_limit);
let result = dfa::dense::Builder::new()
.configure(dfa_config)
.build_from_nfa(&nfarev);
let rev = match result {
Ok(rev) => rev,
Err(_err) => {
debug!("full reverse DFA failed to build: {}", _err);
return None;
}
};
debug!(
"fully compiled reverse DFA built, {} bytes",
rev.memory_usage()
);
Some(ReverseDFAEngine(rev))
}
#[cfg(not(feature = "dfa-build"))]
{
None
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub(crate) fn try_search_half_rev_limited(
&self,
input: &Input<'_>,
min_start: usize,
) -> Result<Option<HalfMatch>, RetryError> {
#[cfg(feature = "dfa-build")]
{
let dfa = &self.0;
crate::meta::limited::dfa_try_search_half_rev(
dfa, input, min_start,
)
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
pub(crate) fn memory_usage(&self) -> usize {
#[cfg(feature = "dfa-build")]
{
self.0.memory_usage()
}
#[cfg(not(feature = "dfa-build"))]
{
// Impossible to reach because this engine is never constructed
// if the requisite features aren't enabled.
unreachable!()
}
}
}