Struct regex_automata::nfa::thompson::backtrack::Visited

struct Visited {
    bitset: Vec<usize>,
    stride: usize,
}

A bitset that keeps track of whether a particular (StateID, offset) has been considered during backtracking. If it has already been visited, then backtracking skips it. This is what gives backtracking its “bound.”

Fields

bitset: Vec<usize>

The actual underlying bitset. Each element in the bitset corresponds to a particular (StateID, offset) pair. States correspond to the rows and the offsets correspond to the columns.

If our underlying NFA has N states and the haystack we’re searching has M bytes, then we have N*(M+1) entries in our bitset table. The M+1 occurs because our matches are delayed by one byte (to support look-around), and so we need to handle the end position itself rather than stopping just before the end. (If there is no end position, then it’s treated as “end-of-input,” which is matched by things like ‘$’.)

Given BITS=N*(M+1), we wind up with div_ceil(BITS, sizeof(usize)) blocks.

We use ‘usize’ to represent our blocks because it makes some of the arithmetic in ‘insert’ a bit nicer. For example, if we used ‘u32’ for our block, we’d either need to cast u32s to usizes or usizes to u32s.

stride: usize

The stride represents one plus length of the haystack we’re searching (as described above). The stride must be initialized for each search.

Implementations

impl Visited

const BLOCK_SIZE: usize = 64usize

The size of each block, in bits.

fn new(re: &BoundedBacktracker) -> Visited

Create a new visited set for the given backtracker.

The set is ready to use, but must be setup at the beginning of each search by calling setup_search.

fn insert(&mut self, sid: StateID, at: usize) -> bool

Insert the given (StateID, offset) pair into this set. If it already exists, then this is a no-op and it returns false. Otherwise this returns true.

fn reset(&mut self, _: &BoundedBacktracker)

Reset this visited set to work with the given bounded backtracker.

fn setup_search( &mut self, re: &BoundedBacktracker, input: &Input<'_>, ) -> Result<(), MatchError>

Setup this visited set to work for a search using the given NFA and input configuration. The NFA must be the same NFA used by the BoundedBacktracker given to Visited::reset. Failing to call this might result in panics or silently incorrect search behavior.

fn memory_usage(&self) -> usize

Return the heap memory usage, in bytes, of this visited set.

Trait Implementations

impl Clone for Visited

fn clone(&self) -> Visited

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Visited

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

Formats the value using the given formatter.