Struct regex_automata::util::alphabet::ByteClassSet

pub(crate) struct ByteClassSet(ByteSet);

A partitioning of bytes into equivalence classes.

A byte class set keeps track of an approximation of equivalence classes of bytes during NFA construction. That is, every byte in an equivalence class cannot discriminate between a match and a non-match.

For example, in the regex [ab]+, the bytes a and b would be in the same equivalence class because it never matters whether an a or a b is seen, and no combination of as and bs in the text can discriminate a match.

Note though that this does not compute the minimal set of equivalence classes. For example, in the regex [ac]+, both a and c are in the same equivalence class for the same reason that a and b are in the same equivalence class in the aforementioned regex. However, in this implementation, a and c are put into distinct equivalence classes. The reason for this is implementation complexity. In the future, we should endeavor to compute the minimal equivalence classes since they can have a rather large impact on the size of the DFA. (Doing this will likely require rethinking how equivalence classes are computed, including changing the representation here, which is only able to group contiguous bytes into the same equivalence class.)

Tuple Fields

0: ByteSet

Implementations

impl ByteClassSet

pub(crate) fn empty() -> Self

Create a new set of byte classes where all bytes are part of the same equivalence class.

pub(crate) fn set_range(&mut self, start: u8, end: u8)

Indicate the range of byte given (inclusive) can discriminate a match between it and all other bytes outside of the range.

pub(crate) fn add_set(&mut self, set: &ByteSet)

Add the contiguous ranges in the set given to this byte class set.

pub(crate) fn byte_classes(&self) -> ByteClasses

Convert this boolean set to a map that maps all byte values to their corresponding equivalence class. The last mapping indicates the largest equivalence class identifier (which is never bigger than 255).

Trait Implementations

impl Clone for ByteClassSet

fn clone(&self) -> ByteClassSet

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for ByteClassSet

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

Formats the value using the given formatter.

impl Default for ByteClassSet

fn default() -> ByteClassSet

Returns the “default value” for a type.