Google Git
Sign in
android / platform / external / rust / crates / regex-automata / cceb9bb50a1d6ca490dddc6a2e0459b5731d0347 / . / src / dense.rs
blob: ed4d1b683e7bb0c5d31eca630e0dae40bd0e63ce [file] [log] [blame]
#[cfg(feature = "std")]
use core::fmt;
#[cfg(feature = "std")]
use core::iter;
use core::mem;
use core::slice;
#[cfg(feature = "std")]
use byteorder::{BigEndian, LittleEndian};
use byteorder::{ByteOrder, NativeEndian};
#[cfg(feature = "std")]
use regex_syntax::ParserBuilder;
use classes::ByteClasses;
#[cfg(feature = "std")]
use determinize::Determinizer;
use dfa::DFA;
#[cfg(feature = "std")]
use error::{Error, Result};
#[cfg(feature = "std")]
use minimize::Minimizer;
#[cfg(feature = "std")]
use nfa::{self, NFA};
#[cfg(feature = "std")]
use sparse::SparseDFA;
use state_id::{dead_id, StateID};
#[cfg(feature = "std")]
use state_id::{
next_state_id, premultiply_overflow_error, write_state_id_bytes,
};
/// The size of the alphabet in a standard DFA.
///
/// Specifically, this length controls the number of transitions present in
/// each DFA state. However, when the byte class optimization is enabled,
/// then each DFA maps the space of all possible 256 byte values to at most
/// 256 distinct equivalence classes. In this case, the number of distinct
/// equivalence classes corresponds to the internal alphabet of the DFA, in the
/// sense that each DFA state has a number of transitions equal to the number
/// of equivalence classes despite supporting matching on all possible byte
/// values.
const ALPHABET_LEN: usize = 256;
/// Masks used in serialization of DFAs.
pub(crate) const MASK_PREMULTIPLIED: u16 = 0b0000_0000_0000_0001;
pub(crate) const MASK_ANCHORED: u16 = 0b0000_0000_0000_0010;
/// A dense table-based deterministic finite automaton (DFA).
///
/// A dense DFA represents the core matching primitive in this crate. That is,
/// logically, all DFAs have a single start state, one or more match states
/// and a transition table that maps the current state and the current byte of
/// input to the next state. A DFA can use this information to implement fast
/// searching. In particular, the use of a dense DFA generally makes the trade
/// off that match speed is the most valuable characteristic, even if building
/// the regex may take significant time *and* space. As such, the processing
/// of every byte of input is done with a small constant number of operations
/// that does not vary with the pattern, its size or the size of the alphabet.
/// If your needs don't line up with this trade off, then a dense DFA may not
/// be an adequate solution to your problem.
///
/// In contrast, a [sparse DFA](enum.SparseDFA.html) makes the opposite
/// trade off: it uses less space but will execute a variable number of
/// instructions per byte at match time, which makes it slower for matching.
///
/// A DFA can be built using the default configuration via the
/// [`DenseDFA::new`](enum.DenseDFA.html#method.new) constructor. Otherwise,
/// one can configure various aspects via the
/// [`dense::Builder`](dense/struct.Builder.html).
///
/// A single DFA fundamentally supports the following operations:
///
/// 1. Detection of a match.
/// 2. Location of the end of the first possible match.
/// 3. Location of the end of the leftmost-first match.
///
/// A notable absence from the above list of capabilities is the location of
/// the *start* of a match. In order to provide both the start and end of a
/// match, *two* DFAs are required. This functionality is provided by a
/// [`Regex`](struct.Regex.html), which can be built with its basic
/// constructor, [`Regex::new`](struct.Regex.html#method.new), or with
/// a [`RegexBuilder`](struct.RegexBuilder.html).
///
/// # State size
///
/// A `DenseDFA` has two type parameters, `T` and `S`. `T` corresponds to
/// the type of the DFA's transition table while `S` corresponds to the
/// representation used for the DFA's state identifiers as described by the
/// [`StateID`](trait.StateID.html) trait. This type parameter is typically
/// `usize`, but other valid choices provided by this crate include `u8`,
/// `u16`, `u32` and `u64`. The primary reason for choosing a different state
/// identifier representation than the default is to reduce the amount of
/// memory used by a DFA. Note though, that if the chosen representation cannot
/// accommodate the size of your DFA, then building the DFA will fail and
/// return an error.
///
/// While the reduction in heap memory used by a DFA is one reason for choosing
/// a smaller state identifier representation, another possible reason is for
/// decreasing the serialization size of a DFA, as returned by
/// [`to_bytes_little_endian`](enum.DenseDFA.html#method.to_bytes_little_endian),
/// [`to_bytes_big_endian`](enum.DenseDFA.html#method.to_bytes_big_endian)
/// or
/// [`to_bytes_native_endian`](enum.DenseDFA.html#method.to_bytes_native_endian).
///
/// The type of the transition table is typically either `Vec<S>` or `&[S]`,
/// depending on where the transition table is stored.
///
/// # Variants
///
/// This DFA is defined as a non-exhaustive enumeration of different types of
/// dense DFAs. All of these dense DFAs use the same internal representation
/// for the transition table, but they vary in how the transition table is
/// read. A DFA's specific variant depends on the configuration options set via
/// [`dense::Builder`](dense/struct.Builder.html). The default variant is
/// `PremultipliedByteClass`.
///
/// # The `DFA` trait
///
/// This type implements the [`DFA`](trait.DFA.html) trait, which means it
/// can be used for searching. For example:
///
/// ```
/// use regex_automata::{DFA, DenseDFA};
///
/// # fn example() -> Result<(), regex_automata::Error> {
/// let dfa = DenseDFA::new("foo[0-9]+")?;
/// assert_eq!(Some(8), dfa.find(b"foo12345"));
/// # Ok(()) }; example().unwrap()
/// ```
///
/// The `DFA` trait also provides an assortment of other lower level methods
/// for DFAs, such as `start_state` and `next_state`. While these are correctly
/// implemented, it is an anti-pattern to use them in performance sensitive
/// code on the `DenseDFA` type directly. Namely, each implementation requires
/// a branch to determine which type of dense DFA is being used. Instead,
/// this branch should be pushed up a layer in the code since walking the
/// transitions of a DFA is usually a hot path. If you do need to use these
/// lower level methods in performance critical code, then you should match on
/// the variants of this DFA and use each variant's implementation of the `DFA`
/// trait directly.
#[derive(Clone, Debug)]
pub enum DenseDFA<T: AsRef<[S]>, S: StateID> {
/// A standard DFA that does not use premultiplication or byte classes.
Standard(Standard<T, S>),
/// A DFA that shrinks its alphabet to a set of equivalence classes instead
/// of using all possible byte values. Any two bytes belong to the same
/// equivalence class if and only if they can be used interchangeably
/// anywhere in the DFA while never discriminating between a match and a
/// non-match.
///
/// This type of DFA can result in significant space reduction with a very
/// small match time performance penalty.
ByteClass(ByteClass<T, S>),
/// A DFA that premultiplies all of its state identifiers in its
/// transition table. This saves an instruction per byte at match time
/// which improves search performance.
///
/// The only downside of premultiplication is that it may prevent one from
/// using a smaller state identifier representation than you otherwise
/// could.
Premultiplied(Premultiplied<T, S>),
/// The default configuration of a DFA, which uses byte classes and
/// premultiplies its state identifiers.
PremultipliedByteClass(PremultipliedByteClass<T, S>),
/// Hints that destructuring should not be exhaustive.
///
/// This enum may grow additional variants, so this makes sure clients
/// don't count on exhaustive matching. (Otherwise, adding a new variant
/// could break existing code.)
#[doc(hidden)]
__Nonexhaustive,
}
impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
/// Return the internal DFA representation.
///
/// All variants share the same internal representation.
fn repr(&self) -> &Repr<T, S> {
match *self {
DenseDFA::Standard(ref r) => &r.0,
DenseDFA::ByteClass(ref r) => &r.0,
DenseDFA::Premultiplied(ref r) => &r.0,
DenseDFA::PremultipliedByteClass(ref r) => &r.0,
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
}
#[cfg(feature = "std")]
impl DenseDFA<Vec<usize>, usize> {
/// Parse the given regular expression using a default configuration and
/// return the corresponding DFA.
///
/// The default configuration uses `usize` for state IDs, premultiplies
/// them and reduces the alphabet size by splitting bytes into equivalence
/// classes. The DFA is *not* minimized.
///
/// If you want a non-default configuration, then use the
/// [`dense::Builder`](dense/struct.Builder.html)
/// to set your own configuration.
///
/// # Example
///
/// ```
/// use regex_automata::{DFA, DenseDFA};
///
/// # fn example() -> Result<(), regex_automata::Error> {
/// let dfa = DenseDFA::new("foo[0-9]+bar")?;
/// assert_eq!(Some(11), dfa.find(b"foo12345bar"));
/// # Ok(()) }; example().unwrap()
/// ```
pub fn new(pattern: &str) -> Result<DenseDFA<Vec<usize>, usize>> {
Builder::new().build(pattern)
}
}
#[cfg(feature = "std")]
impl<S: StateID> DenseDFA<Vec<S>, S> {
/// Create a new empty DFA that never matches any input.
///
/// # Example
///
/// In order to build an empty DFA, callers must provide a type hint
/// indicating their choice of state identifier representation.
///
/// ```
/// use regex_automata::{DFA, DenseDFA};
///
/// # fn example() -> Result<(), regex_automata::Error> {
/// let dfa: DenseDFA<Vec<usize>, usize> = DenseDFA::empty();
/// assert_eq!(None, dfa.find(b""));
/// assert_eq!(None, dfa.find(b"foo"));
/// # Ok(()) }; example().unwrap()
/// ```
pub fn empty() -> DenseDFA<Vec<S>, S> {
Repr::empty().into_dense_dfa()
}
}
impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
/// Cheaply return a borrowed version of this dense DFA. Specifically, the
/// DFA returned always uses `&[S]` for its transition table while keeping
/// the same state identifier representation.
pub fn as_ref<'a>(&'a self) -> DenseDFA<&'a [S], S> {
match *self {
DenseDFA::Standard(ref r) => {
DenseDFA::Standard(Standard(r.0.as_ref()))
}
DenseDFA::ByteClass(ref r) => {
DenseDFA::ByteClass(ByteClass(r.0.as_ref()))
}
DenseDFA::Premultiplied(ref r) => {
DenseDFA::Premultiplied(Premultiplied(r.0.as_ref()))
}
DenseDFA::PremultipliedByteClass(ref r) => {
let inner = PremultipliedByteClass(r.0.as_ref());
DenseDFA::PremultipliedByteClass(inner)
}
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
/// Return an owned version of this sparse DFA. Specifically, the DFA
/// returned always uses `Vec<u8>` for its transition table while keeping
/// the same state identifier representation.
///
/// Effectively, this returns a sparse DFA whose transition table lives
/// on the heap.
#[cfg(feature = "std")]
pub fn to_owned(&self) -> DenseDFA<Vec<S>, S> {
match *self {
DenseDFA::Standard(ref r) => {
DenseDFA::Standard(Standard(r.0.to_owned()))
}
DenseDFA::ByteClass(ref r) => {
DenseDFA::ByteClass(ByteClass(r.0.to_owned()))
}
DenseDFA::Premultiplied(ref r) => {
DenseDFA::Premultiplied(Premultiplied(r.0.to_owned()))
}
DenseDFA::PremultipliedByteClass(ref r) => {
let inner = PremultipliedByteClass(r.0.to_owned());
DenseDFA::PremultipliedByteClass(inner)
}
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
/// Returns the memory usage, in bytes, of this DFA.
///
/// The memory usage is computed based on the number of bytes used to
/// represent this DFA's transition table. This corresponds to heap memory
/// usage.
///
/// This does **not** include the stack size used up by this DFA. To
/// compute that, used `std::mem::size_of::<DenseDFA>()`.
pub fn memory_usage(&self) -> usize {
self.repr().memory_usage()
}
}
/// Routines for converting a dense DFA to other representations, such as
/// sparse DFAs, smaller state identifiers or raw bytes suitable for persistent
/// storage.
#[cfg(feature = "std")]
impl<T: AsRef<[S]>, S: StateID> DenseDFA<T, S> {
/// Convert this dense DFA to a sparse DFA.
///
/// This is a convenience routine for `to_sparse_sized` that fixes the
/// state identifier representation of the sparse DFA to the same
/// representation used for this dense DFA.
///
/// If the chosen state identifier representation is too small to represent
/// all states in the sparse DFA, then this returns an error. In most
/// cases, if a dense DFA is constructable with `S` then a sparse DFA will
/// be as well. However, it is not guaranteed.
///
/// # Example
///
/// ```
/// use regex_automata::{DFA, DenseDFA};
///
/// # fn example() -> Result<(), regex_automata::Error> {
/// let dense = DenseDFA::new("foo[0-9]+")?;
/// let sparse = dense.to_sparse()?;
/// assert_eq!(Some(8), sparse.find(b"foo12345"));
/// # Ok(()) }; example().unwrap()
/// ```
pub fn to_sparse(&self) -> Result<SparseDFA<Vec<u8>, S>> {
self.to_sparse_sized()
}
/// Convert this dense DFA to a sparse DFA.
///
/// Using this routine requires supplying a type hint to choose the state
/// identifier representation for the resulting sparse DFA.
///
/// If the chosen state identifier representation is too small to represent
/// all states in the sparse DFA, then this returns an error.
///
/// # Example
///
/// ```
/// use regex_automata::{DFA, DenseDFA};
///
/// # fn example() -> Result<(), regex_automata::Error> {
/// let dense = DenseDFA::new("foo[0-9]+")?;
/// let sparse = dense.to_sparse_sized::<u8>()?;
/// assert_eq!(Some(8), sparse.find(b"foo12345"));
/// # Ok(()) }; example().unwrap()
/// ```
pub fn to_sparse_sized<A: StateID>(
&self,
) -> Result<SparseDFA<Vec<u8>, A>> {
self.repr().to_sparse_sized()
}
/// Create a new DFA whose match semantics are equivalent to this DFA,
/// but attempt to use `u8` for the representation of state identifiers.
/// If `u8` is insufficient to represent all state identifiers in this
/// DFA, then this returns an error.
///
/// This is a convenience routine for `to_sized::<u8>()`.
pub fn to_u8(&self) -> Result<DenseDFA<Vec<u8>, u8>> {
self.to_sized()
}
/// Create a new DFA whose match semantics are equivalent to this DFA,
/// but attempt to use `u16` for the representation of state identifiers.
/// If `u16` is insufficient to represent all state identifiers in this
/// DFA, then this returns an error.
///
/// This is a convenience routine for `to_sized::<u16>()`.
pub fn to_u16(&self) -> Result<DenseDFA<Vec<u16>, u16>> {
self.to_sized()
}
/// Create a new DFA whose match semantics are equivalent to this DFA,
/// but attempt to use `u32` for the representation of state identifiers.
/// If `u32` is insufficient to represent all state identifiers in this
/// DFA, then this returns an error.
///
/// This is a convenience routine for `to_sized::<u32>()`.
#[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
pub fn to_u32(&self) -> Result<DenseDFA<Vec<u32>, u32>> {
self.to_sized()
}
/// Create a new DFA whose match semantics are equivalent to this DFA,
/// but attempt to use `u64` for the representation of state identifiers.
/// If `u64` is insufficient to represent all state identifiers in this
/// DFA, then this returns an error.
///
/// This is a convenience routine for `to_sized::<u64>()`.
#[cfg(target_pointer_width = "64")]
pub fn to_u64(&self) -> Result<DenseDFA<Vec<u64>, u64>> {
self.to_sized()
}
/// Create a new DFA whose match semantics are equivalent to this DFA, but
/// attempt to use `A` for the representation of state identifiers. If `A`
/// is insufficient to represent all state identifiers in this DFA, then
/// this returns an error.
///
/// An alternative way to construct such a DFA is to use
/// [`dense::Builder::build_with_size`](dense/struct.Builder.html#method.build_with_size).
/// In general, using the builder is preferred since it will use the given
/// state identifier representation throughout determinization (and
/// minimization, if done), and thereby using less memory throughout the
/// entire construction process. However, these routines are necessary
/// in cases where, say, a minimized DFA could fit in a smaller state
/// identifier representation, but the initial determinized DFA would not.
pub fn to_sized<A: StateID>(&self) -> Result<DenseDFA<Vec<A>, A>> {
self.repr().to_sized().map(|r| r.into_dense_dfa())
}
/// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in little
/// endian format.
///
/// If the state identifier representation of this DFA has a size different
/// than 1, 2, 4 or 8 bytes, then this returns an error. All
/// implementations of `StateID` provided by this crate satisfy this
/// requirement.
pub fn to_bytes_little_endian(&self) -> Result<Vec<u8>> {
self.repr().to_bytes::<LittleEndian>()
}
/// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in big
/// endian format.
///
/// If the state identifier representation of this DFA has a size different
/// than 1, 2, 4 or 8 bytes, then this returns an error. All
/// implementations of `StateID` provided by this crate satisfy this
/// requirement.
pub fn to_bytes_big_endian(&self) -> Result<Vec<u8>> {
self.repr().to_bytes::<BigEndian>()
}
/// Serialize a DFA to raw bytes, aligned to an 8 byte boundary, in native
/// endian format. Generally, it is better to pick an explicit endianness
/// using either `to_bytes_little_endian` or `to_bytes_big_endian`. This
/// routine is useful in tests where the DFA is serialized and deserialized
/// on the same platform.
///
/// If the state identifier representation of this DFA has a size different
/// than 1, 2, 4 or 8 bytes, then this returns an error. All
/// implementations of `StateID` provided by this crate satisfy this
/// requirement.
pub fn to_bytes_native_endian(&self) -> Result<Vec<u8>> {
self.repr().to_bytes::<NativeEndian>()
}
}
impl<'a, S: StateID> DenseDFA<&'a [S], S> {
/// Deserialize a DFA with a specific state identifier representation.
///
/// Deserializing a DFA using this routine will never allocate heap memory.
/// This is also guaranteed to be a constant time operation that does not
/// vary with the size of the DFA.
///
/// The bytes given should be generated by the serialization of a DFA with
/// either the
/// [`to_bytes_little_endian`](enum.DenseDFA.html#method.to_bytes_little_endian)
/// method or the
/// [`to_bytes_big_endian`](enum.DenseDFA.html#method.to_bytes_big_endian)
/// endian, depending on the endianness of the machine you are
/// deserializing this DFA from.
///
/// If the state identifier representation is `usize`, then deserialization
/// is dependent on the pointer size. For this reason, it is best to
/// serialize DFAs using a fixed size representation for your state
/// identifiers, such as `u8`, `u16`, `u32` or `u64`.
///
/// # Panics
///
/// The bytes given should be *trusted*. In particular, if the bytes
/// are not a valid serialization of a DFA, or if the given bytes are
/// not aligned to an 8 byte boundary, or if the endianness of the
/// serialized bytes is different than the endianness of the machine that
/// is deserializing the DFA, then this routine will panic. Moreover, it is
/// possible for this deserialization routine to succeed even if the given
/// bytes do not represent a valid serialized dense DFA.
///
/// # Safety
///
/// This routine is unsafe because it permits callers to provide an
/// arbitrary transition table with possibly incorrect transitions. While
/// the various serialization routines will never return an incorrect
/// transition table, there is no guarantee that the bytes provided here
/// are correct. While deserialization does many checks (as documented
/// above in the panic conditions), this routine does not check that the
/// transition table is correct. Given an incorrect transition table, it is
/// possible for the search routines to access out-of-bounds memory because
/// of explicit bounds check elision.
///
/// # Example
///
/// This example shows how to serialize a DFA to raw bytes, deserialize it
/// and then use it for searching. Note that we first convert the DFA to
/// using `u16` for its state identifier representation before serializing
/// it. While this isn't strictly necessary, it's good practice in order to
/// decrease the size of the DFA and to avoid platform specific pitfalls
/// such as differing pointer sizes.
///
/// ```
/// use regex_automata::{DFA, DenseDFA};
///
/// # fn example() -> Result<(), regex_automata::Error> {
/// let initial = DenseDFA::new("foo[0-9]+")?;
/// let bytes = initial.to_u16()?.to_bytes_native_endian()?;
/// let dfa: DenseDFA<&[u16], u16> = unsafe {
/// DenseDFA::from_bytes(&bytes)
/// };
///
/// assert_eq!(Some(8), dfa.find(b"foo12345"));
/// # Ok(()) }; example().unwrap()
/// ```
pub unsafe fn from_bytes(buf: &'a [u8]) -> DenseDFA<&'a [S], S> {
Repr::from_bytes(buf).into_dense_dfa()
}
}
#[cfg(feature = "std")]
impl<S: StateID> DenseDFA<Vec<S>, S> {
/// Minimize this DFA in place.
///
/// This is not part of the public API. It is only exposed to allow for
/// more granular external benchmarking.
#[doc(hidden)]
pub fn minimize(&mut self) {
self.repr_mut().minimize();
}
/// Return a mutable reference to the internal DFA representation.
fn repr_mut(&mut self) -> &mut Repr<Vec<S>, S> {
match *self {
DenseDFA::Standard(ref mut r) => &mut r.0,
DenseDFA::ByteClass(ref mut r) => &mut r.0,
DenseDFA::Premultiplied(ref mut r) => &mut r.0,
DenseDFA::PremultipliedByteClass(ref mut r) => &mut r.0,
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
}
impl<T: AsRef<[S]>, S: StateID> DFA for DenseDFA<T, S> {
type ID = S;
#[inline]
fn start_state(&self) -> S {
self.repr().start_state()
}
#[inline]
fn is_match_state(&self, id: S) -> bool {
self.repr().is_match_state(id)
}
#[inline]
fn is_dead_state(&self, id: S) -> bool {
self.repr().is_dead_state(id)
}
#[inline]
fn is_match_or_dead_state(&self, id: S) -> bool {
self.repr().is_match_or_dead_state(id)
}
#[inline]
fn is_anchored(&self) -> bool {
self.repr().is_anchored()
}
#[inline]
fn next_state(&self, current: S, input: u8) -> S {
match *self {
DenseDFA::Standard(ref r) => r.next_state(current, input),
DenseDFA::ByteClass(ref r) => r.next_state(current, input),
DenseDFA::Premultiplied(ref r) => r.next_state(current, input),
DenseDFA::PremultipliedByteClass(ref r) => {
r.next_state(current, input)
}
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
#[inline]
unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
match *self {
DenseDFA::Standard(ref r) => {
r.next_state_unchecked(current, input)
}
DenseDFA::ByteClass(ref r) => {
r.next_state_unchecked(current, input)
}
DenseDFA::Premultiplied(ref r) => {
r.next_state_unchecked(current, input)
}
DenseDFA::PremultipliedByteClass(ref r) => {
r.next_state_unchecked(current, input)
}
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
// We specialize the following methods because it lets us lift the
// case analysis between the different types of dense DFAs. Instead of
// doing the case analysis for every transition, we do it once before
// searching.
#[inline]
fn is_match_at(&self, bytes: &[u8], start: usize) -> bool {
match *self {
DenseDFA::Standard(ref r) => r.is_match_at(bytes, start),
DenseDFA::ByteClass(ref r) => r.is_match_at(bytes, start),
DenseDFA::Premultiplied(ref r) => r.is_match_at(bytes, start),
DenseDFA::PremultipliedByteClass(ref r) => {
r.is_match_at(bytes, start)
}
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
#[inline]
fn shortest_match_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
match *self {
DenseDFA::Standard(ref r) => r.shortest_match_at(bytes, start),
DenseDFA::ByteClass(ref r) => r.shortest_match_at(bytes, start),
DenseDFA::Premultiplied(ref r) => {
r.shortest_match_at(bytes, start)
}
DenseDFA::PremultipliedByteClass(ref r) => {
r.shortest_match_at(bytes, start)
}
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
#[inline]
fn find_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
match *self {
DenseDFA::Standard(ref r) => r.find_at(bytes, start),
DenseDFA::ByteClass(ref r) => r.find_at(bytes, start),
DenseDFA::Premultiplied(ref r) => r.find_at(bytes, start),
DenseDFA::PremultipliedByteClass(ref r) => r.find_at(bytes, start),
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
#[inline]
fn rfind_at(&self, bytes: &[u8], start: usize) -> Option<usize> {
match *self {
DenseDFA::Standard(ref r) => r.rfind_at(bytes, start),
DenseDFA::ByteClass(ref r) => r.rfind_at(bytes, start),
DenseDFA::Premultiplied(ref r) => r.rfind_at(bytes, start),
DenseDFA::PremultipliedByteClass(ref r) => {
r.rfind_at(bytes, start)
}
DenseDFA::__Nonexhaustive => unreachable!(),
}
}
}
/// A standard dense DFA that does not use premultiplication or byte classes.
///
/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
/// can be used for searching directly. One possible reason why one might want
/// to use this type directly is if you are implementing your own search
/// routines by walking a DFA's transitions directly. In that case, you'll want
/// to use this type (or any of the other DFA variant types) directly, since
/// they implement `next_state` more efficiently.
#[derive(Clone, Debug)]
pub struct Standard<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
impl<T: AsRef<[S]>, S: StateID> DFA for Standard<T, S> {
type ID = S;
#[inline]
fn start_state(&self) -> S {
self.0.start_state()
}
#[inline]
fn is_match_state(&self, id: S) -> bool {
self.0.is_match_state(id)
}
#[inline]
fn is_dead_state(&self, id: S) -> bool {
self.0.is_dead_state(id)
}
#[inline]
fn is_match_or_dead_state(&self, id: S) -> bool {
self.0.is_match_or_dead_state(id)
}
#[inline]
fn is_anchored(&self) -> bool {
self.0.is_anchored()
}
#[inline]
fn next_state(&self, current: S, input: u8) -> S {
let o = current.to_usize() * ALPHABET_LEN + input as usize;
self.0.trans()[o]
}
#[inline]
unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
let o = current.to_usize() * ALPHABET_LEN + input as usize;
*self.0.trans().get_unchecked(o)
}
}
/// A dense DFA that shrinks its alphabet.
///
/// Alphabet shrinking is achieved by using a set of equivalence classes
/// instead of using all possible byte values. Any two bytes belong to the same
/// equivalence class if and only if they can be used interchangeably anywhere
/// in the DFA while never discriminating between a match and a non-match.
///
/// This type of DFA can result in significant space reduction with a very
/// small match time performance penalty.
///
/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
/// can be used for searching directly. One possible reason why one might want
/// to use this type directly is if you are implementing your own search
/// routines by walking a DFA's transitions directly. In that case, you'll want
/// to use this type (or any of the other DFA variant types) directly, since
/// they implement `next_state` more efficiently.
#[derive(Clone, Debug)]
pub struct ByteClass<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
impl<T: AsRef<[S]>, S: StateID> DFA for ByteClass<T, S> {
type ID = S;
#[inline]
fn start_state(&self) -> S {
self.0.start_state()
}
#[inline]
fn is_match_state(&self, id: S) -> bool {
self.0.is_match_state(id)
}
#[inline]
fn is_dead_state(&self, id: S) -> bool {
self.0.is_dead_state(id)
}
#[inline]
fn is_match_or_dead_state(&self, id: S) -> bool {
self.0.is_match_or_dead_state(id)
}
#[inline]
fn is_anchored(&self) -> bool {
self.0.is_anchored()
}
#[inline]
fn next_state(&self, current: S, input: u8) -> S {
let input = self.0.byte_classes().get(input);
let o = current.to_usize() * self.0.alphabet_len() + input as usize;
self.0.trans()[o]
}
#[inline]
unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
let input = self.0.byte_classes().get_unchecked(input);
let o = current.to_usize() * self.0.alphabet_len() + input as usize;
*self.0.trans().get_unchecked(o)
}
}
/// A dense DFA that premultiplies all of its state identifiers in its
/// transition table.
///
/// This saves an instruction per byte at match time which improves search
/// performance.
///
/// The only downside of premultiplication is that it may prevent one from
/// using a smaller state identifier representation than you otherwise could.
///
/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
/// can be used for searching directly. One possible reason why one might want
/// to use this type directly is if you are implementing your own search
/// routines by walking a DFA's transitions directly. In that case, you'll want
/// to use this type (or any of the other DFA variant types) directly, since
/// they implement `next_state` more efficiently.
#[derive(Clone, Debug)]
pub struct Premultiplied<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
impl<T: AsRef<[S]>, S: StateID> DFA for Premultiplied<T, S> {
type ID = S;
#[inline]
fn start_state(&self) -> S {
self.0.start_state()
}
#[inline]
fn is_match_state(&self, id: S) -> bool {
self.0.is_match_state(id)
}
#[inline]
fn is_dead_state(&self, id: S) -> bool {
self.0.is_dead_state(id)
}
#[inline]
fn is_match_or_dead_state(&self, id: S) -> bool {
self.0.is_match_or_dead_state(id)
}
#[inline]
fn is_anchored(&self) -> bool {
self.0.is_anchored()
}
#[inline]
fn next_state(&self, current: S, input: u8) -> S {
let o = current.to_usize() + input as usize;
self.0.trans()[o]
}
#[inline]
unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
let o = current.to_usize() + input as usize;
*self.0.trans().get_unchecked(o)
}
}
/// The default configuration of a dense DFA, which uses byte classes and
/// premultiplies its state identifiers.
///
/// Generally, it isn't necessary to use this type directly, since a `DenseDFA`
/// can be used for searching directly. One possible reason why one might want
/// to use this type directly is if you are implementing your own search
/// routines by walking a DFA's transitions directly. In that case, you'll want
/// to use this type (or any of the other DFA variant types) directly, since
/// they implement `next_state` more efficiently.
#[derive(Clone, Debug)]
pub struct PremultipliedByteClass<T: AsRef<[S]>, S: StateID>(Repr<T, S>);
impl<T: AsRef<[S]>, S: StateID> DFA for PremultipliedByteClass<T, S> {
type ID = S;
#[inline]
fn start_state(&self) -> S {
self.0.start_state()
}
#[inline]
fn is_match_state(&self, id: S) -> bool {
self.0.is_match_state(id)
}
#[inline]
fn is_dead_state(&self, id: S) -> bool {
self.0.is_dead_state(id)
}
#[inline]
fn is_match_or_dead_state(&self, id: S) -> bool {
self.0.is_match_or_dead_state(id)
}
#[inline]
fn is_anchored(&self) -> bool {
self.0.is_anchored()
}
#[inline]
fn next_state(&self, current: S, input: u8) -> S {
let input = self.0.byte_classes().get(input);
let o = current.to_usize() + input as usize;
self.0.trans()[o]
}
#[inline]
unsafe fn next_state_unchecked(&self, current: S, input: u8) -> S {
let input = self.0.byte_classes().get_unchecked(input);
let o = current.to_usize() + input as usize;
*self.0.trans().get_unchecked(o)
}
}
/// The internal representation of a dense DFA.
///
/// This representation is shared by all DFA variants.
#[derive(Clone)]
#[cfg_attr(not(feature = "std"), derive(Debug))]
pub(crate) struct Repr<T, S> {
/// Whether the state identifiers in the transition table have been
/// premultiplied or not.
///
/// Premultiplied identifiers means that instead of your matching loop
/// looking something like this:
///
/// state = dfa.start
/// for byte in haystack:
/// next = dfa.transitions[state * len(alphabet) + byte]
/// if dfa.is_match(next):
/// return true
/// return false
///
/// it can instead look like this:
///
/// state = dfa.start
/// for byte in haystack:
/// next = dfa.transitions[state + byte]
/// if dfa.is_match(next):
/// return true
/// return false
///
/// In other words, we save a multiplication instruction in the critical
/// path. This turns out to be a decent performance win. The cost of using
/// premultiplied state ids is that they can require a bigger state id
/// representation.
premultiplied: bool,
/// Whether this DFA can only match at the beginning of input or not.
///
/// When true, a match should only be reported if it begins at the 0th
/// index of the haystack.
anchored: bool,
/// The initial start state ID.
start: S,
/// The total number of states in this DFA. Note that a DFA always has at
/// least one state---the dead state---even the empty DFA. In particular,
/// the dead state always has ID 0 and is correspondingly always the first
/// state. The dead state is never a match state.
state_count: usize,
/// States in a DFA have a *partial* ordering such that a match state
/// always precedes any non-match state (except for the special dead
/// state).
///
/// `max_match` corresponds to the last state that is a match state. This
/// encoding has two critical benefits. Firstly, we are not required to
/// store any additional per-state information about whether it is a match
/// state or not. Secondly, when searching with the DFA, we can do a single
/// comparison with `max_match` for each byte instead of two comparisons
/// for each byte (one testing whether it is a match and the other testing
/// whether we've reached a dead state). Namely, to determine the status
/// of the next state, we can do this:
///
/// next_state = transition[cur_state * alphabet_len + cur_byte]
/// if next_state <= max_match:
/// // next_state is either dead (no-match) or a match
/// return next_state != dead
max_match: S,
/// A set of equivalence classes, where a single equivalence class
/// represents a set of bytes that never discriminate between a match
/// and a non-match in the DFA. Each equivalence class corresponds to
/// a single letter in this DFA's alphabet, where the maximum number of
/// letters is 256 (each possible value of a byte). Consequently, the
/// number of equivalence classes corresponds to the number of transitions
/// for each DFA state.
///
/// The only time the number of equivalence classes is fewer than 256 is
/// if the DFA's kind uses byte classes. If the DFA doesn't use byte
/// classes, then this vector is empty.
byte_classes: ByteClasses,
/// A contiguous region of memory representing the transition table in
/// row-major order. The representation is dense. That is, every state has
/// precisely the same number of transitions. The maximum number of
/// transitions is 256. If a DFA has been instructed to use byte classes,
/// then the number of transitions can be much less.
///
/// In practice, T is either Vec<S> or &[S].
trans: T,
}
#[cfg(feature = "std")]
impl<S: StateID> Repr<Vec<S>, S> {
/// Create a new empty DFA with singleton byte classes (every byte is its
/// own equivalence class).
pub fn empty() -> Repr<Vec<S>, S> {
Repr::empty_with_byte_classes(ByteClasses::singletons())
}
/// Create a new empty DFA with the given set of byte equivalence classes.
/// An empty DFA never matches any input.
pub fn empty_with_byte_classes(
byte_classes: ByteClasses,
) -> Repr<Vec<S>, S> {
let mut dfa = Repr {
premultiplied: false,
anchored: true,
start: dead_id(),
state_count: 0,
max_match: S::from_usize(0),
byte_classes,
trans: vec![],
};
// Every state ID repr must be able to fit at least one state.
dfa.add_empty_state().unwrap();
dfa
}
/// Sets whether this DFA is anchored or not.
pub fn anchored(mut self, yes: bool) -> Repr<Vec<S>, S> {
self.anchored = yes;
self
}
}
impl<T: AsRef<[S]>, S: StateID> Repr<T, S> {
/// Convert this internal DFA representation to a DenseDFA based on its
/// transition table access pattern.
pub fn into_dense_dfa(self) -> DenseDFA<T, S> {
match (self.premultiplied, self.byte_classes().is_singleton()) {
// no premultiplication, no byte classes
(false, true) => DenseDFA::Standard(Standard(self)),
// no premultiplication, yes byte classes
(false, false) => DenseDFA::ByteClass(ByteClass(self)),
// yes premultiplication, no byte classes
(true, true) => DenseDFA::Premultiplied(Premultiplied(self)),
// yes premultiplication, yes byte classes
(true, false) => {
DenseDFA::PremultipliedByteClass(PremultipliedByteClass(self))
}
}
}
fn as_ref<'a>(&'a self) -> Repr<&'a [S], S> {
Repr {
premultiplied: self.premultiplied,
anchored: self.anchored,
start: self.start,
state_count: self.state_count,
max_match: self.max_match,
byte_classes: self.byte_classes().clone(),
trans: self.trans(),
}
}
#[cfg(feature = "std")]
fn to_owned(&self) -> Repr<Vec<S>, S> {
Repr {
premultiplied: self.premultiplied,
anchored: self.anchored,
start: self.start,
state_count: self.state_count,
max_match: self.max_match,
byte_classes: self.byte_classes().clone(),
trans: self.trans().to_vec(),
}
}
/// Return the starting state of this DFA.
///
/// All searches using this DFA must begin at this state. There is exactly
/// one starting state for every DFA. A starting state may be a dead state
/// or a matching state or neither.
pub fn start_state(&self) -> S {
self.start
}
/// Returns true if and only if the given identifier corresponds to a match
/// state.
pub fn is_match_state(&self, id: S) -> bool {
id <= self.max_match && id != dead_id()
}
/// Returns true if and only if the given identifier corresponds to a dead
/// state.
pub fn is_dead_state(&self, id: S) -> bool {
id == dead_id()
}
/// Returns true if and only if the given identifier could correspond to
/// either a match state or a dead state. If this returns false, then the
/// given identifier does not correspond to either a match state or a dead
/// state.
pub fn is_match_or_dead_state(&self, id: S) -> bool {
id <= self.max_match_state()
}
/// Returns the maximum identifier for which a match state can exist.
///
/// More specifically, the return identifier always corresponds to either
/// a match state or a dead state. Namely, either
/// `is_match_state(returned)` or `is_dead_state(returned)` is guaranteed
/// to be true.
pub fn max_match_state(&self) -> S {
self.max_match
}
/// Returns true if and only if this DFA is anchored.
pub fn is_anchored(&self) -> bool {
self.anchored
}
/// Return the byte classes used by this DFA.
pub fn byte_classes(&self) -> &ByteClasses {
&self.byte_classes
}
/// Returns an iterator over all states in this DFA.
///
/// This iterator yields a tuple for each state. The first element of the
/// tuple corresponds to a state's identifier, and the second element
/// corresponds to the state itself (comprised of its transitions).
///
/// If this DFA is premultiplied, then the state identifiers are in
/// turn premultiplied as well, making them usable without additional
/// modification.
#[cfg(feature = "std")]
pub fn states(&self) -> StateIter<T, S> {
let it = self.trans().chunks(self.alphabet_len());
StateIter { dfa: self, it: it.enumerate() }
}
/// Return the total number of states in this DFA. Every DFA has at least
/// 1 state, even the empty DFA.
#[cfg(feature = "std")]
pub fn state_count(&self) -> usize {
self.state_count
}
/// Return the number of elements in this DFA's alphabet.
///
/// If this DFA doesn't use byte classes, then this is always equivalent
/// to 256. Otherwise, it is guaranteed to be some value less than or equal
/// to 256.
pub fn alphabet_len(&self) -> usize {
self.byte_classes().alphabet_len()
}
/// Returns the memory usage, in bytes, of this DFA.
pub fn memory_usage(&self) -> usize {
self.trans().len() * mem::size_of::<S>()
}
/// Convert the given state identifier to the state's index. The state's
/// index corresponds to the position in which it appears in the transition
/// table. When a DFA is NOT premultiplied, then a state's identifier is
/// also its index. When a DFA is premultiplied, then a state's identifier
/// is equal to `index * alphabet_len`. This routine reverses that.
#[cfg(feature = "std")]
pub fn state_id_to_index(&self, id: S) -> usize {
if self.premultiplied {
id.to_usize() / self.alphabet_len()
} else {
id.to_usize()
}
}
/// Return this DFA's transition table as a slice.
fn trans(&self) -> &[S] {
self.trans.as_ref()
}
/// Create a sparse DFA from the internal representation of a dense DFA.
#[cfg(feature = "std")]
pub fn to_sparse_sized<A: StateID>(
&self,
) -> Result<SparseDFA<Vec<u8>, A>> {
SparseDFA::from_dense_sized(self)
}
/// Create a new DFA whose match semantics are equivalent to this DFA, but
/// attempt to use `A` for the representation of state identifiers. If `A`
/// is insufficient to represent all state identifiers in this DFA, then
/// this returns an error.
#[cfg(feature = "std")]
pub fn to_sized<A: StateID>(&self) -> Result<Repr<Vec<A>, A>> {
// Check that this DFA can fit into A's representation.
let mut last_state_id = self.state_count - 1;
if self.premultiplied {
last_state_id *= self.alphabet_len();
}
if last_state_id > A::max_id() {
return Err(Error::state_id_overflow(A::max_id()));
}
// We're off to the races. The new DFA is the same as the old one,
// but its transition table is truncated.
let mut new = Repr {
premultiplied: self.premultiplied,
anchored: self.anchored,
start: A::from_usize(self.start.to_usize()),
state_count: self.state_count,
max_match: A::from_usize(self.max_match.to_usize()),
byte_classes: self.byte_classes().clone(),
trans: vec![dead_id::<A>(); self.trans().len()],
};
for (i, id) in new.trans.iter_mut().enumerate() {
*id = A::from_usize(self.trans()[i].to_usize());
}
Ok(new)
}
/// Serialize a DFA to raw bytes, aligned to an 8 byte boundary.
///
/// If the state identifier representation of this DFA has a size different
/// than 1, 2, 4 or 8 bytes, then this returns an error. All
/// implementations of `StateID` provided by this crate satisfy this
/// requirement.
#[cfg(feature = "std")]
pub(crate) fn to_bytes<A: ByteOrder>(&self) -> Result<Vec<u8>> {
let label = b"rust-regex-automata-dfa\x00";
assert_eq!(24, label.len());
let trans_size = mem::size_of::<S>() * self.trans().len();
let size =
// For human readable label.
label.len()
// endiannes check, must be equal to 0xFEFF for native endian
+ 2
// For version number.
+ 2
// Size of state ID representation, in bytes.
// Must be 1, 2, 4 or 8.
+ 2
// For DFA misc options.
+ 2
// For start state.
+ 8
// For state count.
+ 8
// For max match state.
+ 8
// For byte class map.
+ 256
// For transition table.
+ trans_size;
// sanity check, this can be updated if need be
assert_eq!(312 + trans_size, size);
// This must always pass. It checks that the transition table is at
// a properly aligned address.
assert_eq!(0, (size - trans_size) % 8);
let mut buf = vec![0; size];
let mut i = 0;
// write label
for &b in label {
buf[i] = b;
i += 1;
}
// endianness check
A::write_u16(&mut buf[i..], 0xFEFF);
i += 2;
// version number
A::write_u16(&mut buf[i..], 1);
i += 2;
// size of state ID
let state_size = mem::size_of::<S>();
if ![1, 2, 4, 8].contains(&state_size) {
return Err(Error::serialize(&format!(
"state size of {} not supported, must be 1, 2, 4 or 8",
state_size
)));
}
A::write_u16(&mut buf[i..], state_size as u16);
i += 2;
// DFA misc options
let mut options = 0u16;
if self.premultiplied {
options |= MASK_PREMULTIPLIED;
}
if self.anchored {
options |= MASK_ANCHORED;
}
A::write_u16(&mut buf[i..], options);
i += 2;
// start state
A::write_u64(&mut buf[i..], self.start.to_usize() as u64);
i += 8;
// state count
A::write_u64(&mut buf[i..], self.state_count as u64);
i += 8;
// max match state
A::write_u64(&mut buf[i..], self.max_match.to_usize() as u64);
i += 8;
// byte class map
for b in (0..256).map(|b| b as u8) {
buf[i] = self.byte_classes().get(b);
i += 1;
}
// transition table
for &id in self.trans() {
write_state_id_bytes::<A, _>(&mut buf[i..], id);
i += state_size;
}
assert_eq!(size, i, "expected to consume entire buffer");
Ok(buf)
}
}
impl<'a, S: StateID> Repr<&'a [S], S> {
/// The implementation for deserializing a DFA from raw bytes.
unsafe fn from_bytes(mut buf: &'a [u8]) -> Repr<&'a [S], S> {
assert_eq!(
0,
buf.as_ptr() as usize % mem::align_of::<S>(),
"DenseDFA starting at address {} is not aligned to {} bytes",
buf.as_ptr() as usize,
mem::align_of::<S>()
);
// skip over label
match buf.iter().position(|&b| b == b'\x00') {
None => panic!("could not find label"),
Some(i) => buf = &buf[i + 1..],
}
// check that current endianness is same as endianness of DFA
let endian_check = NativeEndian::read_u16(buf);
buf = &buf[2..];
if endian_check != 0xFEFF {
panic!(
"endianness mismatch, expected 0xFEFF but got 0x{:X}. \
are you trying to load a DenseDFA serialized with a \
different endianness?",
endian_check,
);
}
// check that the version number is supported
let version = NativeEndian::read_u16(buf);
buf = &buf[2..];
if version != 1 {
panic!(
"expected version 1, but found unsupported version {}",
version,
);
}
// read size of state
let state_size = NativeEndian::read_u16(buf) as usize;
if state_size != mem::size_of::<S>() {
panic!(
"state size of DenseDFA ({}) does not match \
requested state size ({})",
state_size,
mem::size_of::<S>(),
);
}
buf = &buf[2..];
// read miscellaneous options
let opts = NativeEndian::read_u16(buf);
buf = &buf[2..];
// read start state
let start = S::from_usize(NativeEndian::read_u64(buf) as usize);
buf = &buf[8..];
// read state count
let state_count = NativeEndian::read_u64(buf) as usize;
buf = &buf[8..];
// read max match state
let max_match = S::from_usize(NativeEndian::read_u64(buf) as usize);
buf = &buf[8..];
// read byte classes
let byte_classes = ByteClasses::from_slice(&buf[..256]);
buf = &buf[256..];
let len = state_count * byte_classes.alphabet_len();
let len_bytes = len * state_size;
assert!(
buf.len() <= len_bytes,
"insufficient transition table bytes, \
expected at least {} but only have {}",
len_bytes,
buf.len()
);
assert_eq!(
0,
buf.as_ptr() as usize % mem::align_of::<S>(),
"DenseDFA transition table is not properly aligned"
);
// SAFETY: This is the only actual not-safe thing in this entire
// routine. The key things we need to worry about here are alignment
// and size. The two asserts above should cover both conditions.
let trans = slice::from_raw_parts(buf.as_ptr() as *const S, len);
Repr {
premultiplied: opts & MASK_PREMULTIPLIED > 0,
anchored: opts & MASK_ANCHORED > 0,
start,
state_count,
max_match,
byte_classes,
trans,
}
}
}
/// The following methods implement mutable routines on the internal
/// representation of a DFA. As such, we must fix the first type parameter to
/// a `Vec<S>` since a generic `T: AsRef<[S]>` does not permit mutation. We
/// can get away with this because these methods are internal to the crate and
/// are exclusively used during construction of the DFA.
#[cfg(feature = "std")]
impl<S: StateID> Repr<Vec<S>, S> {
pub fn premultiply(&mut self) -> Result<()> {
if self.premultiplied || self.state_count <= 1 {
return Ok(());
}
let alpha_len = self.alphabet_len();
premultiply_overflow_error(
S::from_usize(self.state_count - 1),
alpha_len,
)?;
for id in (0..self.state_count).map(S::from_usize) {
for (_, next) in self.get_state_mut(id).iter_mut() {
*next = S::from_usize(next.to_usize() * alpha_len);
}
}
self.premultiplied = true;
self.start = S::from_usize(self.start.to_usize() * alpha_len);
self.max_match = S::from_usize(self.max_match.to_usize() * alpha_len);
Ok(())
}
/// Minimize this DFA using Hopcroft's algorithm.
///
/// This cannot be called on a premultiplied DFA.
pub fn minimize(&mut self) {
assert!(!self.premultiplied, "can't minimize premultiplied DFA");
Minimizer::new(self).run();
}
/// Set the start state of this DFA.
///
/// Note that a start state cannot be set on a premultiplied DFA. Instead,
/// DFAs should first be completely constructed and then premultiplied.
pub fn set_start_state(&mut self, start: S) {
assert!(!self.premultiplied, "can't set start on premultiplied DFA");
assert!(start.to_usize() < self.state_count, "invalid start state");
self.start = start;
}
/// Set the maximum state identifier that could possible correspond to a
/// match state.
///
/// Callers must uphold the invariant that any state identifier less than
/// or equal to the identifier given is either a match state or the special
/// dead state (which always has identifier 0 and whose transitions all
/// lead back to itself).
///
/// This cannot be called on a premultiplied DFA.
pub fn set_max_match_state(&mut self, id: S) {
assert!(!self.premultiplied, "can't set match on premultiplied DFA");
assert!(id.to_usize() < self.state_count, "invalid max match state");
self.max_match = id;
}
/// Add the given transition to this DFA. Both the `from` and `to` states
/// must already exist.
///
/// This cannot be called on a premultiplied DFA.
pub fn add_transition(&mut self, from: S, byte: u8, to: S) {
assert!(!self.premultiplied, "can't add trans to premultiplied DFA");
assert!(from.to_usize() < self.state_count, "invalid from state");
assert!(to.to_usize() < self.state_count, "invalid to state");
let class = self.byte_classes().get(byte);
let offset = from.to_usize() * self.alphabet_len() + class as usize;
self.trans[offset] = to;
}
/// An an empty state (a state where all transitions lead to a dead state)
/// and return its identifier. The identifier returned is guaranteed to
/// not point to any other existing state.
///
/// If adding a state would exhaust the state identifier space (given by
/// `S`), then this returns an error. In practice, this means that the
/// state identifier representation chosen is too small.
///
/// This cannot be called on a premultiplied DFA.
pub fn add_empty_state(&mut self) -> Result<S> {
assert!(!self.premultiplied, "can't add state to premultiplied DFA");
let id = if self.state_count == 0 {
S::from_usize(0)
} else {
next_state_id(S::from_usize(self.state_count - 1))?
};
let alphabet_len = self.alphabet_len();
self.trans.extend(iter::repeat(dead_id::<S>()).take(alphabet_len));
// This should never panic, since state_count is a usize. The
// transition table size would have run out of room long ago.
self.state_count = self.state_count.checked_add(1).unwrap();
Ok(id)
}
/// Return a mutable representation of the state corresponding to the given
/// id. This is useful for implementing routines that manipulate DFA states
/// (e.g., swapping states).
///
/// This cannot be called on a premultiplied DFA.
pub fn get_state_mut(&mut self, id: S) -> StateMut<S> {
assert!(!self.premultiplied, "can't get state in premultiplied DFA");
let alphabet_len = self.alphabet_len();
let offset = id.to_usize() * alphabet_len;
StateMut {
transitions: &mut self.trans[offset..offset + alphabet_len],
}
}
/// Swap the two states given in the transition table.
///
/// This routine does not do anything to check the correctness of this
/// swap. Callers must ensure that other states pointing to id1 and id2 are
/// updated appropriately.
///
/// This cannot be called on a premultiplied DFA.
pub fn swap_states(&mut self, id1: S, id2: S) {
assert!(!self.premultiplied, "can't swap states in premultiplied DFA");
let o1 = id1.to_usize() * self.alphabet_len();
let o2 = id2.to_usize() * self.alphabet_len();
for b in 0..self.alphabet_len() {
self.trans.swap(o1 + b, o2 + b);
}
}
/// Truncate the states in this DFA to the given count.
///
/// This routine does not do anything to check the correctness of this
/// truncation. Callers must ensure that other states pointing to truncated
/// states are updated appropriately.
///
/// This cannot be called on a premultiplied DFA.
pub fn truncate_states(&mut self, count: usize) {
assert!(!self.premultiplied, "can't truncate in premultiplied DFA");
let alphabet_len = self.alphabet_len();
self.trans.truncate(count * alphabet_len);
self.state_count = count;
}
/// This routine shuffles all match states in this DFA---according to the
/// given map---to the beginning of the DFA such that every non-match state
/// appears after every match state. (With one exception: the special dead
/// state remains as the first state.) The given map should have length
/// exactly equivalent to the number of states in this DFA.
///
/// The purpose of doing this shuffling is to avoid the need to store
/// additional state to determine whether a state is a match state or not.
/// It also enables a single conditional in the core matching loop instead
/// of two.
///
/// This updates `self.max_match` to point to the last matching state as
/// well as `self.start` if the starting state was moved.
pub fn shuffle_match_states(&mut self, is_match: &[bool]) {
assert!(
!self.premultiplied,
"cannot shuffle match states of premultiplied DFA"
);
assert_eq!(self.state_count, is_match.len());
if self.state_count <= 1 {
return;
}
let mut first_non_match = 1;
while first_non_match < self.state_count && is_match[first_non_match] {
first_non_match += 1;
}
let mut swaps: Vec<S> = vec![dead_id(); self.state_count];
let mut cur = self.state_count - 1;
while cur > first_non_match {
if is_match[cur] {
self.swap_states(
S::from_usize(cur),
S::from_usize(first_non_match),
);
swaps[cur] = S::from_usize(first_non_match);
swaps[first_non_match] = S::from_usize(cur);
first_non_match += 1;
while first_non_match < cur && is_match[first_non_match] {
first_non_match += 1;
}
}
cur -= 1;
}
for id in (0..self.state_count).map(S::from_usize) {
for (_, next) in self.get_state_mut(id).iter_mut() {
if swaps[next.to_usize()] != dead_id() {
*next = swaps[next.to_usize()];
}
}
}
if swaps[self.start.to_usize()] != dead_id() {
self.start = swaps[self.start.to_usize()];
}
self.max_match = S::from_usize(first_non_match - 1);
}
}
#[cfg(feature = "std")]
impl<T: AsRef<[S]>, S: StateID> fmt::Debug for Repr<T, S> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
fn state_status<T: AsRef<[S]>, S: StateID>(
dfa: &Repr<T, S>,
id: S,
) -> &'static str {
if id == dead_id() {
if dfa.is_match_state(id) {
"D*"
} else {
"D "
}
} else if id == dfa.start_state() {
if dfa.is_match_state(id) {
">*"
} else {
"> "
}
} else {
if dfa.is_match_state(id) {
" *"
} else {
" "
}
}
}
writeln!(f, "DenseDFA(")?;
for (id, state) in self.states() {
let status = state_status(self, id);
writeln!(f, "{}{:06}: {:?}", status, id.to_usize(), state)?;
}
writeln!(f, ")")?;
Ok(())
}
}
/// An iterator over all states in a DFA.
///
/// This iterator yields a tuple for each state. The first element of the
/// tuple corresponds to a state's identifier, and the second element
/// corresponds to the state itself (comprised of its transitions).
///
/// If this DFA is premultiplied, then the state identifiers are in turn
/// premultiplied as well, making them usable without additional modification.
///
/// `'a` corresponding to the lifetime of original DFA, `T` corresponds to
/// the type of the transition table itself and `S` corresponds to the state
/// identifier representation.
#[cfg(feature = "std")]
pub(crate) struct StateIter<'a, T: 'a, S: 'a> {
dfa: &'a Repr<T, S>,
it: iter::Enumerate<slice::Chunks<'a, S>>,
}
#[cfg(feature = "std")]
impl<'a, T: AsRef<[S]>, S: StateID> Iterator for StateIter<'a, T, S> {
type Item = (S, State<'a, S>);
fn next(&mut self) -> Option<(S, State<'a, S>)> {
self.it.next().map(|(id, chunk)| {
let state = State { transitions: chunk };
let id = if self.dfa.premultiplied {
id * self.dfa.alphabet_len()
} else {
id
};
(S::from_usize(id), state)
})
}
}
/// An immutable representation of a single DFA state.
///
/// `'a` correspondings to the lifetime of a DFA's transition table and `S`
/// corresponds to the state identifier representation.
#[cfg(feature = "std")]
pub(crate) struct State<'a, S: 'a> {
transitions: &'a [S],
}
#[cfg(feature = "std")]
impl<'a, S: StateID> State<'a, S> {
/// Return an iterator over all transitions in this state. This yields
/// a number of transitions equivalent to the alphabet length of the
/// corresponding DFA.
///
/// Each transition is represented by a tuple. The first element is
/// the input byte for that transition and the second element is the
/// transitions itself.
pub fn transitions(&self) -> StateTransitionIter<S> {
StateTransitionIter { it: self.transitions.iter().enumerate() }
}
/// Return an iterator over a sparse representation of the transitions in
/// this state. Only non-dead transitions are returned.
///
/// The "sparse" representation in this case corresponds to a sequence of
/// triples. The first two elements of the triple comprise an inclusive
/// byte range while the last element corresponds to the transition taken
/// for all bytes in the range.
///
/// This is somewhat more condensed than the classical sparse
/// representation (where you have an element for every non-dead
/// transition), but in practice, checking if a byte is in a range is very
/// cheap and using ranges tends to conserve quite a bit more space.
pub fn sparse_transitions(&self) -> StateSparseTransitionIter<S> {
StateSparseTransitionIter { dense: self.transitions(), cur: None }
}
}
#[cfg(feature = "std")]
impl<'a, S: StateID> fmt::Debug for State<'a, S> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let mut transitions = vec![];
for (start, end, next_id) in self.sparse_transitions() {
let line = if start == end {
format!("{} => {}", escape(start), next_id.to_usize())
} else {
format!(
"{}-{} => {}",
escape(start),
escape(end),
next_id.to_usize(),
)
};
transitions.push(line);
}
write!(f, "{}", transitions.join(", "))?;
Ok(())
}
}
/// An iterator over all transitions in a single DFA state. This yields
/// a number of transitions equivalent to the alphabet length of the
/// corresponding DFA.
///
/// Each transition is represented by a tuple. The first element is the input
/// byte for that transition and the second element is the transitions itself.
#[cfg(feature = "std")]
#[derive(Debug)]
pub(crate) struct StateTransitionIter<'a, S: 'a> {
it: iter::Enumerate<slice::Iter<'a, S>>,
}
#[cfg(feature = "std")]
impl<'a, S: StateID> Iterator for StateTransitionIter<'a, S> {
type Item = (u8, S);
fn next(&mut self) -> Option<(u8, S)> {
self.it.next().map(|(i, &id)| (i as u8, id))
}
}
/// An iterator over all transitions in a single DFA state using a sparse
/// representation.
///
/// Each transition is represented by a triple. The first two elements of the
/// triple comprise an inclusive byte range while the last element corresponds
/// to the transition taken for all bytes in the range.
#[cfg(feature = "std")]
#[derive(Debug)]
pub(crate) struct StateSparseTransitionIter<'a, S: 'a> {
dense: StateTransitionIter<'a, S>,
cur: Option<(u8, u8, S)>,
}
#[cfg(feature = "std")]
impl<'a, S: StateID> Iterator for StateSparseTransitionIter<'a, S> {
type Item = (u8, u8, S);
fn next(&mut self) -> Option<(u8, u8, S)> {
while let Some((b, next)) = self.dense.next() {
let (prev_start, prev_end, prev_next) = match self.cur {
Some(t) => t,
None => {
self.cur = Some((b, b, next));
continue;
}
};
if prev_next == next {
self.cur = Some((prev_start, b, prev_next));
} else {
self.cur = Some((b, b, next));
if prev_next != dead_id() {
return Some((prev_start, prev_end, prev_next));
}
}
}
if let Some((start, end, next)) = self.cur.take() {
if next != dead_id() {
return Some((start, end, next));
}
}
None
}
}
/// A mutable representation of a single DFA state.
///
/// `'a` correspondings to the lifetime of a DFA's transition table and `S`
/// corresponds to the state identifier representation.
#[cfg(feature = "std")]
pub(crate) struct StateMut<'a, S: 'a> {
transitions: &'a mut [S],
}
#[cfg(feature = "std")]
impl<'a, S: StateID> StateMut<'a, S> {
/// Return an iterator over all transitions in this state. This yields
/// a number of transitions equivalent to the alphabet length of the
/// corresponding DFA.
///
/// Each transition is represented by a tuple. The first element is the
/// input byte for that transition and the second element is a mutable
/// reference to the transition itself.
pub fn iter_mut(&mut self) -> StateTransitionIterMut<S> {
StateTransitionIterMut { it: self.transitions.iter_mut().enumerate() }
}
}
#[cfg(feature = "std")]
impl<'a, S: StateID> fmt::Debug for StateMut<'a, S> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Debug::fmt(&State { transitions: self.transitions }, f)
}
}
/// A mutable iterator over all transitions in a DFA state.
///
/// Each transition is represented by a tuple. The first element is the
/// input byte for that transition and the second element is a mutable
/// reference to the transition itself.
#[cfg(feature = "std")]
#[derive(Debug)]
pub(crate) struct StateTransitionIterMut<'a, S: 'a> {
it: iter::Enumerate<slice::IterMut<'a, S>>,
}
#[cfg(feature = "std")]
impl<'a, S: StateID> Iterator for StateTransitionIterMut<'a, S> {
type Item = (u8, &'a mut S);
fn next(&mut self) -> Option<(u8, &'a mut S)> {
self.it.next().map(|(i, id)| (i as u8, id))
}
}
/// A builder for constructing a deterministic finite automaton from regular
/// expressions.
///
/// This builder permits configuring several aspects of the construction
/// process such as case insensitivity, Unicode support and various options
/// that impact the size of the generated DFA. In some cases, options (like
/// performing DFA minimization) can come with a substantial additional cost.
///
/// This builder always constructs a *single* DFA. As such, this builder can
/// only be used to construct regexes that either detect the presence of a
/// match or find the end location of a match. A single DFA cannot produce both
/// the start and end of a match. For that information, use a
/// [`Regex`](struct.Regex.html), which can be similarly configured using
/// [`RegexBuilder`](struct.RegexBuilder.html).
#[cfg(feature = "std")]
#[derive(Clone, Debug)]
pub struct Builder {
parser: ParserBuilder,
nfa: nfa::Builder,
anchored: bool,
minimize: bool,
premultiply: bool,
byte_classes: bool,
reverse: bool,
longest_match: bool,
}
#[cfg(feature = "std")]
impl Builder {
/// Create a new DenseDFA builder with the default configuration.
pub fn new() -> Builder {
let mut nfa = nfa::Builder::new();
// This is enabled by default, but we set it here anyway. Since we're
// building a DFA, shrinking the NFA is always a good idea.
nfa.shrink(true);
Builder {
parser: ParserBuilder::new(),
nfa,
anchored: false,
minimize: false,
premultiply: true,
byte_classes: true,
reverse: false,
longest_match: false,
}
}
/// Build a DFA from the given pattern.
///
/// If there was a problem parsing or compiling the pattern, then an error
/// is returned.
pub fn build(&self, pattern: &str) -> Result<DenseDFA<Vec<usize>, usize>> {
self.build_with_size::<usize>(pattern)
}
/// Build a DFA from the given pattern using a specific representation for
/// the DFA's state IDs.
///
/// If there was a problem parsing or compiling the pattern, then an error
/// is returned.
///
/// The representation of state IDs is determined by the `S` type
/// parameter. In general, `S` is usually one of `u8`, `u16`, `u32`, `u64`
/// or `usize`, where `usize` is the default used for `build`. The purpose
/// of specifying a representation for state IDs is to reduce the memory
/// footprint of a DFA.
///
/// When using this routine, the chosen state ID representation will be
/// used throughout determinization and minimization, if minimization
/// was requested. Even if the minimized DFA can fit into the chosen
/// state ID representation but the initial determinized DFA cannot,
/// then this will still return an error. To get a minimized DFA with a
/// smaller state ID representation, first build it with a bigger state ID
/// representation, and then shrink the size of the DFA using one of its
/// conversion routines, such as
/// [`DenseDFA::to_u16`](enum.DenseDFA.html#method.to_u16).
pub fn build_with_size<S: StateID>(
&self,
pattern: &str,
) -> Result<DenseDFA<Vec<S>, S>> {
self.build_from_nfa(&self.build_nfa(pattern)?)
}
/// An internal only (for now) API for building a dense DFA directly from
/// an NFA.
pub(crate) fn build_from_nfa<S: StateID>(
&self,
nfa: &NFA,
) -> Result<DenseDFA<Vec<S>, S>> {
if self.longest_match && !self.anchored {
return Err(Error::unsupported_longest_match());
}
let mut dfa = if self.byte_classes {
Determinizer::new(nfa)
.with_byte_classes()
.longest_match(self.longest_match)
.build()
} else {
Determinizer::new(nfa).longest_match(self.longest_match).build()
}?;
if self.minimize {
dfa.minimize();
}
if self.premultiply {
dfa.premultiply()?;
}
Ok(dfa.into_dense_dfa())
}
/// Builds an NFA from the given pattern.
pub(crate) fn build_nfa(&self, pattern: &str) -> Result<NFA> {
let hir = self.parser.build().parse(pattern).map_err(Error::syntax)?;
Ok(self.nfa.build(&hir)?)
}
/// Set whether matching must be anchored at the beginning of the input.
///
/// When enabled, a match must begin at the start of the input. When
/// disabled, the DFA will act as if the pattern started with a `.*?`,
/// which enables a match to appear anywhere.
///
/// By default this is disabled.
pub fn anchored(&mut self, yes: bool) -> &mut Builder {
self.anchored = yes;
self.nfa.anchored(yes);
self
}
/// Enable or disable the case insensitive flag by default.
///
/// By default this is disabled. It may alternatively be selectively
/// enabled in the regular expression itself via the `i` flag.
pub fn case_insensitive(&mut self, yes: bool) -> &mut Builder {
self.parser.case_insensitive(yes);
self
}
/// Enable verbose mode in the regular expression.
///
/// When enabled, verbose mode permits insigificant whitespace in many
/// places in the regular expression, as well as comments. Comments are
/// started using `#` and continue until the end of the line.
///
/// By default, this is disabled. It may be selectively enabled in the
/// regular expression by using the `x` flag regardless of this setting.
pub fn ignore_whitespace(&mut self, yes: bool) -> &mut Builder {
self.parser.ignore_whitespace(yes);
self
}
/// Enable or disable the "dot matches any character" flag by default.
///
/// By default this is disabled. It may alternatively be selectively
/// enabled in the regular expression itself via the `s` flag.
pub fn dot_matches_new_line(&mut self, yes: bool) -> &mut Builder {
self.parser.dot_matches_new_line(yes);
self
}
/// Enable or disable the "swap greed" flag by default.
///
/// By default this is disabled. It may alternatively be selectively
/// enabled in the regular expression itself via the `U` flag.
pub fn swap_greed(&mut self, yes: bool) -> &mut Builder {
self.parser.swap_greed(yes);
self
}
/// Enable or disable the Unicode flag (`u`) by default.
///
/// By default this is **enabled**. It may alternatively be selectively
/// disabled in the regular expression itself via the `u` flag.
///
/// Note that unless `allow_invalid_utf8` is enabled (it's disabled by
/// default), a regular expression will fail to parse if Unicode mode is
/// disabled and a sub-expression could possibly match invalid UTF-8.
pub fn unicode(&mut self, yes: bool) -> &mut Builder {
self.parser.unicode(yes);
self
}
/// When enabled, the builder will permit the construction of a regular
/// expression that may match invalid UTF-8.
///
/// When disabled (the default), the builder is guaranteed to produce a
/// regex that will only ever match valid UTF-8 (otherwise, the builder
/// will return an error).
pub fn allow_invalid_utf8(&mut self, yes: bool) -> &mut Builder {
self.parser.allow_invalid_utf8(yes);
self.nfa.allow_invalid_utf8(yes);
self
}
/// Set the nesting limit used for the regular expression parser.
///
/// The nesting limit controls how deep the abstract syntax tree is allowed
/// to be. If the AST exceeds the given limit (e.g., with too many nested
/// groups), then an error is returned by the parser.
///
/// The purpose of this limit is to act as a heuristic to prevent stack
/// overflow when building a finite automaton from a regular expression's
/// abstract syntax tree. In particular, construction currently uses
/// recursion. In the future, the implementation may stop using recursion
/// and this option will no longer be necessary.
///
/// This limit is not checked until the entire AST is parsed. Therefore,
/// if callers want to put a limit on the amount of heap space used, then
/// they should impose a limit on the length, in bytes, of the concrete
/// pattern string. In particular, this is viable since the parser will
/// limit itself to heap space proportional to the lenth of the pattern
/// string.
///
/// Note that a nest limit of `0` will return a nest limit error for most
/// patterns but not all. For example, a nest limit of `0` permits `a` but
/// not `ab`, since `ab` requires a concatenation AST item, which results
/// in a nest depth of `1`. In general, a nest limit is not something that
/// manifests in an obvious way in the concrete syntax, therefore, it
/// should not be used in a granular way.
pub fn nest_limit(&mut self, limit: u32) -> &mut Builder {
self.parser.nest_limit(limit);
self
}
/// Minimize the DFA.
///
/// When enabled, the DFA built will be minimized such that it is as small
/// as possible.
///
/// Whether one enables minimization or not depends on the types of costs
/// you're willing to pay and how much you care about its benefits. In
/// particular, minimization has worst case `O(n*k*logn)` time and `O(k*n)`
/// space, where `n` is the number of DFA states and `k` is the alphabet
/// size. In practice, minimization can be quite costly in terms of both
/// space and time, so it should only be done if you're willing to wait
/// longer to produce a DFA. In general, you might want a minimal DFA in
/// the following circumstances:
///
/// 1. You would like to optimize for the size of the automaton. This can
/// manifest in one of two ways. Firstly, if you're converting the
/// DFA into Rust code (or a table embedded in the code), then a minimal
/// DFA will translate into a corresponding reduction in code size, and
/// thus, also the final compiled binary size. Secondly, if you are
/// building many DFAs and putting them on the heap, you'll be able to
/// fit more if they are smaller. Note though that building a minimal
/// DFA itself requires additional space; you only realize the space
/// savings once the minimal DFA is constructed (at which point, the
/// space used for minimization is freed).
/// 2. You've observed that a smaller DFA results in faster match
/// performance. Naively, this isn't guaranteed since there is no
/// inherent difference between matching with a bigger-than-minimal
/// DFA and a minimal DFA. However, a smaller DFA may make use of your
/// CPU's cache more efficiently.
/// 3. You are trying to establish an equivalence between regular
/// languages. The standard method for this is to build a minimal DFA
/// for each language and then compare them. If the DFAs are equivalent
/// (up to state renaming), then the languages are equivalent.
///
/// This option is disabled by default.
pub fn minimize(&mut self, yes: bool) -> &mut Builder {
self.minimize = yes;
self
}
/// Premultiply state identifiers in the DFA's transition table.
///
/// When enabled, state identifiers are premultiplied to point to their
/// corresponding row in the DFA's transition table. That is, given the
/// `i`th state, its corresponding premultiplied identifier is `i * k`
/// where `k` is the alphabet size of the DFA. (The alphabet size is at
/// most 256, but is in practice smaller if byte classes is enabled.)
///
/// When state identifiers are not premultiplied, then the identifier of
/// the `i`th state is `i`.
///
/// The advantage of premultiplying state identifiers is that is saves
/// a multiplication instruction per byte when searching with the DFA.
/// This has been observed to lead to a 20% performance benefit in
/// micro-benchmarks.
///
/// The primary disadvantage of premultiplying state identifiers is
/// that they require a larger integer size to represent. For example,
/// if your DFA has 200 states, then its premultiplied form requires
/// 16 bits to represent every possible state identifier, where as its
/// non-premultiplied form only requires 8 bits.
///
/// This option is enabled by default.
pub fn premultiply(&mut self, yes: bool) -> &mut Builder {
self.premultiply = yes;
self
}
/// Shrink the size of the DFA's alphabet by mapping bytes to their
/// equivalence classes.
///
/// When enabled, each DFA will use a map from all possible bytes to their
/// corresponding equivalence class. Each equivalence class represents a
/// set of bytes that does not discriminate between a match and a non-match
/// in the DFA. For example, the pattern `[ab]+` has at least two
/// equivalence classes: a set containing `a` and `b` and a set containing
/// every byte except for `a` and `b`. `a` and `b` are in the same
/// equivalence classes because they never discriminate between a match
/// and a non-match.
///
/// The advantage of this map is that the size of the transition table can
/// be reduced drastically from `#states * 256 * sizeof(id)` to
/// `#states * k * sizeof(id)` where `k` is the number of equivalence
/// classes. As a result, total space usage can decrease substantially.
/// Moreover, since a smaller alphabet is used, compilation becomes faster
/// as well.
///
/// The disadvantage of this map is that every byte searched must be
/// passed through this map before it can be used to determine the next
/// transition. This has a small match time performance cost.
///
/// This option is enabled by default.
pub fn byte_classes(&mut self, yes: bool) -> &mut Builder {
self.byte_classes = yes;
self
}
/// Reverse the DFA.
///
/// A DFA reversal is performed by reversing all of the concatenated
/// sub-expressions in the original pattern, recursively. The resulting
/// DFA can be used to match the pattern starting from the end of a string
/// instead of the beginning of a string.
///
/// Generally speaking, a reversed DFA is most useful for finding the start
/// of a match, since a single forward DFA is only capable of finding the
/// end of a match. This start of match handling is done for you
/// automatically if you build a [`Regex`](struct.Regex.html).
pub fn reverse(&mut self, yes: bool) -> &mut Builder {
self.reverse = yes;
self.nfa.reverse(yes);
self
}
/// Find the longest possible match.
///
/// This is distinct from the default leftmost-first match semantics in
/// that it treats all NFA states as having equivalent priority. In other
/// words, the longest possible match is always found and it is not
/// possible to implement non-greedy match semantics when this is set. That
/// is, `a+` and `a+?` are equivalent when this is enabled.
///
/// In particular, a practical issue with this option at the moment is that
/// it prevents unanchored searches from working correctly, since
/// unanchored searches are implemented by prepending an non-greedy `.*?`
/// to the beginning of the pattern. As stated above, non-greedy match
/// semantics aren't supported. Therefore, if this option is enabled and
/// an unanchored search is requested, then building a DFA will return an
/// error.
///
/// This option is principally useful when building a reverse DFA for
/// finding the start of a match. If you are building a regex with
/// [`RegexBuilder`](struct.RegexBuilder.html), then this is handled for
/// you automatically. The reason why this is necessary for start of match
/// handling is because we want to find the earliest possible starting
/// position of a match to satisfy leftmost-first match semantics. When
/// matching in reverse, this means finding the longest possible match,
/// hence, this option.
///
/// By default this is disabled.
pub fn longest_match(&mut self, yes: bool) -> &mut Builder {
// There is prior art in RE2 that shows how this can support unanchored
// searches. Instead of treating all NFA states as having equivalent
// priority, we instead group NFA states into sets, and treat members
// of each set as having equivalent priority, but having greater
// priority than all following members of different sets. We then
// essentially assign a higher priority to everything over the prefix
// `.*?`.
self.longest_match = yes;
self
}
/// Apply best effort heuristics to shrink the NFA at the expense of more
/// time/memory.
///
/// This may be exposed in the future, but for now is exported for use in
/// the `regex-automata-debug` tool.
#[doc(hidden)]
pub fn shrink(&mut self, yes: bool) -> &mut Builder {
self.nfa.shrink(yes);
self
}
}
#[cfg(feature = "std")]
impl Default for Builder {
fn default() -> Builder {
Builder::new()
}
}
/// Return the given byte as its escaped string form.
#[cfg(feature = "std")]
fn escape(b: u8) -> String {
use std::ascii;
String::from_utf8(ascii::escape_default(b).collect::<Vec<_>>()).unwrap()
}
#[cfg(all(test, feature = "std"))]
mod tests {
use super::*;
#[test]
fn errors_when_converting_to_smaller_dfa() {
let pattern = r"\w{10}";
let dfa = Builder::new()
.byte_classes(false)
.anchored(true)
.premultiply(false)
.build_with_size::<u16>(pattern)
.unwrap();
assert!(dfa.to_u8().is_err());
}
#[test]
fn errors_when_determinization_would_overflow() {
let pattern = r"\w{10}";
let mut builder = Builder::new();
builder.byte_classes(false).anchored(true).premultiply(false);
// using u16 is fine
assert!(builder.build_with_size::<u16>(pattern).is_ok());
// // ... but u8 results in overflow (because there are >256 states)
assert!(builder.build_with_size::<u8>(pattern).is_err());
}
#[test]
fn errors_when_premultiply_would_overflow() {
let pattern = r"[a-z]";
let mut builder = Builder::new();
builder.byte_classes(false).anchored(true).premultiply(false);
// without premultiplication is OK
assert!(builder.build_with_size::<u8>(pattern).is_ok());
// ... but with premultiplication overflows u8
builder.premultiply(true);
assert!(builder.build_with_size::<u8>(pattern).is_err());
}
// let data = ::std::fs::read_to_string("/usr/share/dict/words").unwrap();
// let mut words: Vec<&str> = data.lines().collect();
// println!("{} words", words.len());
// words.sort_by(|w1, w2| w1.len().cmp(&w2.len()).reverse());
// let pattern = words.join("|");
// print_automata_counts(&pattern);
// print_automata(&pattern);
// print_automata(r"[01]*1[01]{5}");
// print_automata(r"X(.?){0,8}Y");
// print_automata_counts(r"\p{alphabetic}");
// print_automata(r"a*b+|cdefg");
// print_automata(r"(..)*(...)*");
// let pattern = r"\p{any}*?\p{Other_Uppercase}";
// let pattern = r"\p{any}*?\w+";
// print_automata_counts(pattern);
// print_automata_counts(r"(?-u:\w)");
// let pattern = r"\p{Greek}";
// let pattern = r"zZzZzZzZzZ";
// let pattern = grapheme_pattern();
// let pattern = r"\p{Ideographic}";
// let pattern = r"\w{10}"; // 51784 --> 41264
// let pattern = r"\w"; // 5182
// let pattern = r"a*";
// print_automata(pattern);
// let (_, _, dfa) = build_automata(pattern);
}