Source code
Revision control
Copy as Markdown
Other Tools
/// A state identifier specifically tailored for lazy DFAs.
///
/// A lazy state ID logically represents a pointer to a DFA state. In practice,
/// by limiting the number of DFA states it can address, it reserves some
/// bits of its representation to encode some additional information. That
/// additional information is called a "tag." That tag is used to record
/// whether the state it points to is an unknown, dead, quit, start or match
/// state.
///
/// When implementing a low level search routine with a lazy DFA, it is
/// necessary to query the type of the current state to know what to do:
///
/// * **Unknown** - The state has not yet been computed. The
/// parameters used to get this state ID must be re-passed to
/// [`DFA::next_state`](crate::hybrid::dfa::DFA::next_state), which will never
/// return an unknown state ID.
/// * **Dead** - A dead state only has transitions to itself. It indicates that
/// the search cannot do anything else and should stop with whatever result it
/// has.
/// * **Quit** - A quit state indicates that the automaton could not answer
/// whether a match exists or not. Correct search implementations must return a
/// [`MatchError::quit`](crate::MatchError::quit) when a DFA enters a quit
/// state.
/// * **Start** - A start state is a state in which a search can begin.
/// Lazy DFAs usually have more than one start state. Branching on
/// this isn't required for correctness, but a common optimization is
/// to run a prefilter when a search enters a start state. Note that
/// start states are *not* tagged automatically, and one must enable the
/// [`Config::specialize_start_states`](crate::hybrid::dfa::Config::specialize_start_states)
/// setting for start states to be tagged. The reason for this is
/// that a DFA search loop is usually written to execute a prefilter once it
/// enters a start state. But if there is no prefilter, this handling can be
/// quite diastrous as the DFA may ping-pong between the special handling code
/// and a possible optimized hot path for handling untagged states. When start
/// states aren't specialized, then they are untagged and remain in the hot
/// path.
/// * **Match** - A match state indicates that a match has been found.
/// Depending on the semantics of your search implementation, it may either
/// continue until the end of the haystack or a dead state, or it might quit
/// and return the match immediately.
///
/// As an optimization, the [`is_tagged`](LazyStateID::is_tagged) predicate
/// can be used to determine if a tag exists at all. This is useful to avoid
/// branching on all of the above types for every byte searched.
///
/// # Example
///
/// This example shows how `LazyStateID` can be used to implement a correct
/// search routine with minimal branching. In particular, this search routine
/// implements "leftmost" matching, which means that it doesn't immediately
/// stop once a match is found. Instead, it continues until it reaches a dead
/// state.
///
/// Notice also how a correct search implementation deals with
/// [`CacheError`](crate::hybrid::CacheError)s returned by some of
/// the lazy DFA routines. When a `CacheError` occurs, it returns
/// [`MatchError::gave_up`](crate::MatchError::gave_up).
///
/// ```
/// use regex_automata::{
/// hybrid::dfa::{Cache, DFA},
/// HalfMatch, MatchError, Input,
/// };
///
/// fn find_leftmost_first(
/// dfa: &DFA,
/// cache: &mut Cache,
/// haystack: &[u8],
/// ) -> Result<Option<HalfMatch>, MatchError> {
/// // The start state is determined by inspecting the position and the
/// // initial bytes of the haystack. Note that start states can never
/// // be match states (since DFAs in this crate delay matches by 1
/// // byte), so we don't need to check if the start state is a match.
/// let mut sid = dfa.start_state_forward(
/// cache,
/// &Input::new(haystack),
/// )?;
/// let mut last_match = None;
/// // Walk all the bytes in the haystack. We can quit early if we see
/// // a dead or a quit state. The former means the automaton will
/// // never transition to any other state. The latter means that the
/// // automaton entered a condition in which its search failed.
/// for (i, &b) in haystack.iter().enumerate() {
/// sid = dfa
/// .next_state(cache, sid, b)
/// .map_err(|_| MatchError::gave_up(i))?;
/// if sid.is_tagged() {
/// if sid.is_match() {
/// last_match = Some(HalfMatch::new(
/// dfa.match_pattern(cache, sid, 0),
/// i,
/// ));
/// } else if sid.is_dead() {
/// return Ok(last_match);
/// } else if sid.is_quit() {
/// // It is possible to enter into a quit state after
/// // observing a match has occurred. In that case, we
/// // should return the match instead of an error.
/// if last_match.is_some() {
/// return Ok(last_match);
/// }
/// return Err(MatchError::quit(b, i));
/// }
/// // Implementors may also want to check for start states and
/// // handle them differently for performance reasons. But it is
/// // not necessary for correctness. Note that in order to check
/// // for start states, you'll need to enable the
/// // 'specialize_start_states' config knob, otherwise start
/// // states will not be tagged.
/// }
/// }
/// // Matches are always delayed by 1 byte, so we must explicitly walk
/// // the special "EOI" transition at the end of the search.
/// sid = dfa
/// .next_eoi_state(cache, sid)
/// .map_err(|_| MatchError::gave_up(haystack.len()))?;
/// if sid.is_match() {
/// last_match = Some(HalfMatch::new(
/// dfa.match_pattern(cache, sid, 0),
/// haystack.len(),
/// ));
/// }
/// Ok(last_match)
/// }
///
/// // We use a greedy '+' operator to show how the search doesn't just stop
/// // once a match is detected. It continues extending the match. Using
/// // '[a-z]+?' would also work as expected and stop the search early.
/// // Greediness is built into the automaton.
/// let dfa = DFA::new(r"[a-z]+")?;
/// let mut cache = dfa.create_cache();
/// let haystack = "123 foobar 4567".as_bytes();
/// let mat = find_leftmost_first(&dfa, &mut cache, haystack)?.unwrap();
/// assert_eq!(mat.pattern().as_usize(), 0);
/// assert_eq!(mat.offset(), 10);
///
/// // Here's another example that tests our handling of the special
/// // EOI transition. This will fail to find a match if we don't call
/// // 'next_eoi_state' at the end of the search since the match isn't found
/// // until the final byte in the haystack.
/// let dfa = DFA::new(r"[0-9]{4}")?;
/// let mut cache = dfa.create_cache();
/// let haystack = "123 foobar 4567".as_bytes();
/// let mat = find_leftmost_first(&dfa, &mut cache, haystack)?.unwrap();
/// assert_eq!(mat.pattern().as_usize(), 0);
/// assert_eq!(mat.offset(), 15);
///
/// // And note that our search implementation above automatically works
/// // with multi-DFAs. Namely, `dfa.match_pattern(match_state, 0)` selects
/// // the appropriate pattern ID for us.
/// let dfa = DFA::new_many(&[r"[a-z]+", r"[0-9]+"])?;
/// let mut cache = dfa.create_cache();
/// let haystack = "123 foobar 4567".as_bytes();
/// let mat = find_leftmost_first(&dfa, &mut cache, haystack)?.unwrap();
/// assert_eq!(mat.pattern().as_usize(), 1);
/// assert_eq!(mat.offset(), 3);
/// let mat = find_leftmost_first(&dfa, &mut cache, &haystack[3..])?.unwrap();
/// assert_eq!(mat.pattern().as_usize(), 0);
/// assert_eq!(mat.offset(), 7);
/// let mat = find_leftmost_first(&dfa, &mut cache, &haystack[10..])?.unwrap();
/// assert_eq!(mat.pattern().as_usize(), 1);
/// assert_eq!(mat.offset(), 5);
///
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(
Clone, Copy, Debug, Default, Eq, Hash, PartialEq, PartialOrd, Ord,
)]
pub struct LazyStateID(u32);
impl LazyStateID {
#[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
const MAX_BIT: usize = 31;
#[cfg(target_pointer_width = "16")]
const MAX_BIT: usize = 15;
const MASK_UNKNOWN: usize = 1 << (LazyStateID::MAX_BIT);
const MASK_DEAD: usize = 1 << (LazyStateID::MAX_BIT - 1);
const MASK_QUIT: usize = 1 << (LazyStateID::MAX_BIT - 2);
const MASK_START: usize = 1 << (LazyStateID::MAX_BIT - 3);
const MASK_MATCH: usize = 1 << (LazyStateID::MAX_BIT - 4);
const MAX: usize = LazyStateID::MASK_MATCH - 1;
/// Create a new lazy state ID.
///
/// If the given identifier exceeds [`LazyStateID::MAX`], then this returns
/// an error.
#[inline]
pub(crate) fn new(id: usize) -> Result<LazyStateID, LazyStateIDError> {
if id > LazyStateID::MAX {
let attempted = u64::try_from(id).unwrap();
return Err(LazyStateIDError { attempted });
}
Ok(LazyStateID::new_unchecked(id))
}
/// Create a new lazy state ID without checking whether the given value
/// exceeds [`LazyStateID::MAX`].
///
/// While this is unchecked, providing an incorrect value must never
/// sacrifice memory safety.
#[inline]
const fn new_unchecked(id: usize) -> LazyStateID {
// FIXME: Use as_u32() once const functions in traits are stable.
LazyStateID(id as u32)
}
/// Return this lazy state ID as an untagged `usize`.
///
/// If this lazy state ID is tagged, then the usize returned is the state
/// ID without the tag. If the ID was not tagged, then the usize returned
/// is equivalent to the state ID.
#[inline]
pub(crate) fn as_usize_untagged(&self) -> usize {
self.as_usize_unchecked() & LazyStateID::MAX
}
/// Return this lazy state ID as its raw internal `usize` value, which may
/// be tagged (and thus greater than LazyStateID::MAX).
#[inline]
pub(crate) const fn as_usize_unchecked(&self) -> usize {
// FIXME: Use as_usize() once const functions in traits are stable.
self.0 as usize
}
#[inline]
pub(crate) const fn to_unknown(&self) -> LazyStateID {
LazyStateID::new_unchecked(
self.as_usize_unchecked() | LazyStateID::MASK_UNKNOWN,
)
}
#[inline]
pub(crate) const fn to_dead(&self) -> LazyStateID {
LazyStateID::new_unchecked(
self.as_usize_unchecked() | LazyStateID::MASK_DEAD,
)
}
#[inline]
pub(crate) const fn to_quit(&self) -> LazyStateID {
LazyStateID::new_unchecked(
self.as_usize_unchecked() | LazyStateID::MASK_QUIT,
)
}
/// Return this lazy state ID as a state ID that is tagged as a start
/// state.
#[inline]
pub(crate) const fn to_start(&self) -> LazyStateID {
LazyStateID::new_unchecked(
self.as_usize_unchecked() | LazyStateID::MASK_START,
)
}
/// Return this lazy state ID as a lazy state ID that is tagged as a match
/// state.
#[inline]
pub(crate) const fn to_match(&self) -> LazyStateID {
LazyStateID::new_unchecked(
self.as_usize_unchecked() | LazyStateID::MASK_MATCH,
)
}
/// Return true if and only if this lazy state ID is tagged.
///
/// When a lazy state ID is tagged, then one can conclude that it is one
/// of a match, start, dead, quit or unknown state.
#[inline]
pub const fn is_tagged(&self) -> bool {
self.as_usize_unchecked() > LazyStateID::MAX
}
/// Return true if and only if this represents a lazy state ID that is
/// "unknown." That is, the state has not yet been created. When a caller
/// sees this state ID, it generally means that a state has to be computed
/// in order to proceed.
#[inline]
pub const fn is_unknown(&self) -> bool {
self.as_usize_unchecked() & LazyStateID::MASK_UNKNOWN > 0
}
/// Return true if and only if this represents a dead state. A dead state
/// is a state that can never transition to any other state except the
/// dead state. When a dead state is seen, it generally indicates that a
/// search should stop.
#[inline]
pub const fn is_dead(&self) -> bool {
self.as_usize_unchecked() & LazyStateID::MASK_DEAD > 0
}
/// Return true if and only if this represents a quit state. A quit state
/// is a state that is representationally equivalent to a dead state,
/// except it indicates the automaton has reached a point at which it can
/// no longer determine whether a match exists or not. In general, this
/// indicates an error during search and the caller must either pass this
/// error up or use a different search technique.
#[inline]
pub const fn is_quit(&self) -> bool {
self.as_usize_unchecked() & LazyStateID::MASK_QUIT > 0
}
/// Return true if and only if this lazy state ID has been tagged as a
/// start state.
///
/// Note that if
/// [`Config::specialize_start_states`](crate::hybrid::dfa::Config) is
/// disabled (which is the default), then this will always return false
/// since start states won't be tagged.
#[inline]
pub const fn is_start(&self) -> bool {
self.as_usize_unchecked() & LazyStateID::MASK_START > 0
}
/// Return true if and only if this lazy state ID has been tagged as a
/// match state.
#[inline]
pub const fn is_match(&self) -> bool {
self.as_usize_unchecked() & LazyStateID::MASK_MATCH > 0
}
}
/// This error occurs when a lazy state ID could not be constructed.
///
/// This occurs when given an integer exceeding the maximum lazy state ID
/// value.
///
/// When the `std` feature is enabled, this implements the `Error` trait.
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct LazyStateIDError {
attempted: u64,
}
impl LazyStateIDError {
/// Returns the value that failed to constructed a lazy state ID.
pub(crate) fn attempted(&self) -> u64 {
self.attempted
}
}
#[cfg(feature = "std")]
impl std::error::Error for LazyStateIDError {}
impl core::fmt::Display for LazyStateIDError {
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
write!(
f,
"failed to create LazyStateID from {:?}, which exceeds {:?}",
self.attempted(),
LazyStateID::MAX,
)
}
}