Struct regex_automata::nfa::thompson::backtrack::Cache

source ·
pub struct Cache {
    stack: Vec<Frame>,
    visited: Visited,
}
Expand description

A cache represents mutable state that a BoundedBacktracker requires during a search.

For a given BoundedBacktracker, its corresponding cache may be created either via BoundedBacktracker::create_cache, or via Cache::new. They are equivalent in every way, except the former does not require explicitly importing Cache.

A particular Cache is coupled with the BoundedBacktracker from which it was created. It may only be used with that BoundedBacktracker. A cache and its allocations may be re-purposed via Cache::reset, in which case, it can only be used with the new BoundedBacktracker (and not the old one).

Fields§

§stack: Vec<Frame>

Stack used on the heap for doing backtracking instead of the traditional recursive approach. We don’t want recursion because then we’re likely to hit a stack overflow for bigger regexes.

§visited: Visited

The set of (StateID, HaystackOffset) pairs that have been visited by the backtracker within a single search. If such a pair has been visited, then we avoid doing the work for that pair again. This is what “bounds” the backtracking and prevents it from having worst case exponential time.

Implementations§

source§

impl Cache

source

pub fn new(re: &BoundedBacktracker) -> Cache

Create a new BoundedBacktracker cache.

A potentially more convenient routine to create a cache is BoundedBacktracker::create_cache, as it does not require also importing the Cache type.

If you want to reuse the returned Cache with some other BoundedBacktracker, then you must call Cache::reset with the desired BoundedBacktracker.

source

pub fn reset(&mut self, re: &BoundedBacktracker)

Reset this cache such that it can be used for searching with different BoundedBacktracker.

A cache reset permits reusing memory already allocated in this cache with a different BoundedBacktracker.

§Example

This shows how to re-purpose a cache for use with a different BoundedBacktracker.

use regex_automata::{
    nfa::thompson::backtrack::BoundedBacktracker,
    Match,
};

let re1 = BoundedBacktracker::new(r"\w")?;
let re2 = BoundedBacktracker::new(r"\W")?;

let mut cache = re1.create_cache();
assert_eq!(
    Some(Ok(Match::must(0, 0..2))),
    re1.try_find_iter(&mut cache, "Δ").next(),
);

// Using 'cache' with re2 is not allowed. It may result in panics or
// incorrect results. In order to re-purpose the cache, we must reset
// it with the BoundedBacktracker we'd like to use it with.
//
// Similarly, after this reset, using the cache with 're1' is also not
// allowed.
cache.reset(&re2);
assert_eq!(
    Some(Ok(Match::must(0, 0..3))),
    re2.try_find_iter(&mut cache, "☃").next(),
);
source

pub fn memory_usage(&self) -> usize

Returns the heap memory usage, in bytes, of this cache.

This does not include the stack size used up by this cache. To compute that, use std::mem::size_of::<Cache>().

Clears this cache. This should be called at the start of every search to ensure we start with a clean slate.

This also sets the length of the capturing groups used in the current search. This permits an optimization where by ‘SlotTable::for_state’ only returns the number of slots equivalent to the number of slots given in the ‘Captures’ value. This may be less than the total number of possible slots, e.g., when one only wants to track overall match offsets. This in turn permits less copying of capturing group spans in the BoundedBacktracker.

Trait Implementations§

source§

impl Clone for Cache

source§

fn clone(&self) -> Cache

Returns a copy of the value. Read more
1.0.0 · source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
source§

impl Debug for Cache

source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl Freeze for Cache

§

impl RefUnwindSafe for Cache

§

impl Send for Cache

§

impl Sync for Cache

§

impl Unpin for Cache

§

impl UnwindSafe for Cache

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

source§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

source§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.