Struct regex_automata::nfa::thompson::DenseTransitions

pub struct DenseTransitions {
    pub transitions: Box<[StateID]>,
}

A sequence of transitions used to represent a dense state.

This is the primary representation of a Dense state. It provides constant time matching. That is, given a byte in a haystack and a DenseTransitions, one can determine if the state matches in constant time.

This is in contrast to SparseTransitions, whose time complexity is necessarily bigger than constant time. Also in contrast, DenseTransitions usually requires (much) more heap memory.

Fields

transitions: Box<[StateID]>

A dense representation of this state’s transitions on the heap. This always has length 256.

Implementations

impl DenseTransitions

pub fn matches(&self, haystack: &[u8], at: usize) -> Option<StateID>

This follows the matching transition for a particular byte.

The matching transition is found by looking for a transition that doesn’t correspond to StateID::ZERO for the byte at the given position in haystack.

If at >= haystack.len(), then this returns None.

pub(crate) fn matches_unit(&self, unit: Unit) -> Option<StateID>

This follows the matching transition for any member of the alphabet.

The matching transition is found by looking for a transition that doesn’t correspond to StateID::ZERO for the byte at the given position in haystack.

If at >= haystack.len() or if the given alphabet unit is EOI, then this returns None.

pub fn matches_byte(&self, byte: u8) -> Option<StateID>

This follows the matching transition for a particular byte.

The matching transition is found by looking for a transition that doesn’t correspond to StateID::ZERO for the given byte.

If at >= haystack.len(), then this returns None.

pub(crate) fn iter(&self) -> impl Iterator<Item = Transition> + '_

Returns an iterator over all transitions that don’t point to StateID::ZERO.

Trait Implementations

impl Clone for DenseTransitions

fn clone(&self) -> DenseTransitions

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for DenseTransitions

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

Formats the value using the given formatter.

impl PartialEq for DenseTransitions

fn eq(&self, other: &DenseTransitions) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for DenseTransitions

impl StructuralPartialEq for DenseTransitions