Struct `Cache`

struct Cache { ... }

A cache represents a partially computed DFA.

A cache is the key component that differentiates a classical DFA and a hybrid NFA/DFA (also called a "lazy DFA"). Where a classical DFA builds a complete transition table that can handle all possible inputs, a hybrid NFA/DFA starts with an empty transition table and builds only the parts required during search. The parts that are built are stored in a cache. For this reason, a cache is a required parameter for nearly every operation on a DFA.

Caches can be created from their corresponding DFA via DFA::create_cache. A cache can only be used with either the DFA that created it, or the DFA that was most recently used to reset it with Cache::reset. Using a cache with any other DFA may result in panics or incorrect results.

Implementations

`impl Cache`

fn new(dfa: &DFA) -> Cache

Create a new cache for the given lazy DFA.

The cache returned should only be used for searches for the given DFA. If you want to reuse the cache for another DFA, then you must call Cache::reset with that DFA.

fn reset(self: &mut Self, dfa: &DFA)

Reset this cache such that it can be used for searching with the given lazy DFA (and only that DFA).

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

Resetting a cache sets its "clear count" to 0. This is relevant if the lazy DFA has been configured to "give up" after it has cleared the cache a certain number of times.

Any lazy state ID generated by the cache prior to resetting it is invalid after the reset.

Example

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

# if cfg!(miri) { return Ok(()); } // miri takes too long
use regex_automata::{hybrid::dfa::DFA, HalfMatch, Input};

let dfa1 = DFA::new(r"\w")?;
let dfa2 = DFA::new(r"\W")?;

let mut cache = dfa1.create_cache();
assert_eq!(
    Some(HalfMatch::must(0, 2)),
    dfa1.try_search_fwd(&mut cache, &Input::new("Δ"))?,
);

// Using 'cache' with dfa2 is not allowed. It may result in panics or
// incorrect results. In order to re-purpose the cache, we must reset
// it with the DFA we'd like to use it with.
//
// Similarly, after this reset, using the cache with 'dfa1' is also not
// allowed.
cache.reset(&dfa2);
assert_eq!(
    Some(HalfMatch::must(0, 3)),
    dfa2.try_search_fwd(&mut cache, &Input::new("☃"))?,
);

# Ok::<(), Box<dyn std::error::Error>>(())

fn search_start(self: &mut Self, at: usize)

Initializes a new search starting at the given position.

If a previous search was unfinished, then it is finished automatically and a new search is begun.

Note that keeping track of search progress is not necessary for correct implementations of search using a lazy DFA. Keeping track of search progress is only necessary if you want the Config::minimum_bytes_per_state configuration knob to work.

fn search_update(self: &mut Self, at: usize)

Updates the current search to indicate that it has search to the current position.

No special care needs to be taken for reverse searches. Namely, the position given may be less than the starting position of the search.

Panics

This panics if no search has been started by Cache::search_start.

fn search_finish(self: &mut Self, at: usize)

Indicates that a search has finished at the given position.

Panics

This panics if no search has been started by Cache::search_start.

fn search_total_len(self: &Self) -> usize

Returns the total number of bytes that have been searched since this cache was last cleared.

This is useful for determining the efficiency of the cache. For example, the lazy DFA uses this value in conjunction with the Config::minimum_bytes_per_state knob to help determine whether it should quit searching.

This always returns 0 if search progress isn't being tracked. Note that the lazy DFA search routines in this crate always track search progress.

fn clear_count(self: &Self) -> usize

Returns the total number of times this cache has been cleared since it was either created or last reset.

This is useful for informational purposes or if you want to change search strategies based on the number of times the cache has been cleared.

fn memory_usage(self: &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>().

`impl Clone for Cache`

fn clone(self: &Self) -> Cache

`impl Debug for Cache`

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

`impl Freeze for Cache`

`impl RefUnwindSafe for Cache`

`impl Send for Cache`

`impl Sync for Cache`

`impl Unpin for Cache`

`impl UnsafeUnpin for Cache`

`impl UnwindSafe for Cache`

`impl<T> Any for Cache`

fn type_id(self: &Self) -> TypeId

`impl<T> Borrow for Cache`

fn borrow(self: &Self) -> &T

`impl<T> BorrowMut for Cache`

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

`impl<T> CloneToUninit for Cache`

unsafe fn clone_to_uninit(self: &Self, dest: *mut u8)

`impl<T> From for Cache`

fn from(t: T) -> T: Returns the argument unchanged.

`impl<T> ToOwned for Cache`

fn to_owned(self: &Self) -> T
fn clone_into(self: &Self, target: &mut T)

`impl<T, U> Into for Cache`

fn into(self: Self) -> U

Calls U::from(self).

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

`impl<T, U> TryFrom for Cache`

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

`impl<T, U> TryInto for Cache`

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