Initial import of regex-automata-0.1.9.
Bug: 155309706
Change-Id: I20031167cbe49d12754936285a0781eb7a3b8bfd
diff --git a/src/state_id.rs b/src/state_id.rs
new file mode 100644
index 0000000..c9bac19
--- /dev/null
+++ b/src/state_id.rs
@@ -0,0 +1,291 @@
+use core::fmt::Debug;
+use core::hash::Hash;
+use core::mem::size_of;
+
+use byteorder::{ByteOrder, NativeEndian};
+
+#[cfg(feature = "std")]
+pub use self::std::*;
+
+#[cfg(feature = "std")]
+mod std {
+ use byteorder::ByteOrder;
+ use core::mem::size_of;
+ use error::{Error, Result};
+
+ use super::StateID;
+
+ /// Check that the premultiplication of the given state identifier can
+ /// fit into the representation indicated by `S`. If it cannot, or if it
+ /// overflows `usize` itself, then an error is returned.
+ pub fn premultiply_overflow_error<S: StateID>(
+ last_state: S,
+ alphabet_len: usize,
+ ) -> Result<()> {
+ let requested = match last_state.to_usize().checked_mul(alphabet_len) {
+ Some(requested) => requested,
+ None => return Err(Error::premultiply_overflow(0, 0)),
+ };
+ if requested > S::max_id() {
+ return Err(Error::premultiply_overflow(S::max_id(), requested));
+ }
+ Ok(())
+ }
+
+ /// Allocate the next sequential identifier for a fresh state given
+ /// the previously constructed state identified by `current`. If the
+ /// next sequential identifier would overflow `usize` or the chosen
+ /// representation indicated by `S`, then an error is returned.
+ pub fn next_state_id<S: StateID>(current: S) -> Result<S> {
+ let next = match current.to_usize().checked_add(1) {
+ Some(next) => next,
+ None => return Err(Error::state_id_overflow(::std::usize::MAX)),
+ };
+ if next > S::max_id() {
+ return Err(Error::state_id_overflow(S::max_id()));
+ }
+ Ok(S::from_usize(next))
+ }
+
+ /// Convert the given `usize` to the chosen state identifier
+ /// representation. If the given value cannot fit in the chosen
+ /// representation, then an error is returned.
+ pub fn usize_to_state_id<S: StateID>(value: usize) -> Result<S> {
+ if value > S::max_id() {
+ Err(Error::state_id_overflow(S::max_id()))
+ } else {
+ Ok(S::from_usize(value))
+ }
+ }
+
+ /// Write the given identifier to the given slice of bytes using the
+ /// specified endianness. The given slice must have length at least
+ /// `size_of::<S>()`.
+ ///
+ /// The given state identifier representation must have size 1, 2, 4 or 8.
+ pub fn write_state_id_bytes<E: ByteOrder, S: StateID>(
+ slice: &mut [u8],
+ id: S,
+ ) {
+ assert!(
+ 1 == size_of::<S>()
+ || 2 == size_of::<S>()
+ || 4 == size_of::<S>()
+ || 8 == size_of::<S>()
+ );
+
+ match size_of::<S>() {
+ 1 => slice[0] = id.to_usize() as u8,
+ 2 => E::write_u16(slice, id.to_usize() as u16),
+ 4 => E::write_u32(slice, id.to_usize() as u32),
+ 8 => E::write_u64(slice, id.to_usize() as u64),
+ _ => unreachable!(),
+ }
+ }
+}
+
+/// Return the unique identifier for a DFA's dead state in the chosen
+/// representation indicated by `S`.
+pub fn dead_id<S: StateID>() -> S {
+ S::from_usize(0)
+}
+
+/// A trait describing the representation of a DFA's state identifier.
+///
+/// The purpose of this trait is to safely express both the possible state
+/// identifier representations that can be used in a DFA and to convert between
+/// state identifier representations and types that can be used to efficiently
+/// index memory (such as `usize`).
+///
+/// In general, one should not need to implement this trait explicitly. In
+/// particular, this crate provides implementations for `u8`, `u16`, `u32`,
+/// `u64` and `usize`. (`u32` and `u64` are only provided for targets that can
+/// represent all corresponding values in a `usize`.)
+///
+/// # Safety
+///
+/// This trait is unsafe because the correctness of its implementations may be
+/// relied upon by other unsafe code. For example, one possible way to
+/// implement this trait incorrectly would be to return a maximum identifier
+/// in `max_id` that is greater than the real maximum identifier. This will
+/// likely result in wrap-on-overflow semantics in release mode, which can in
+/// turn produce incorrect state identifiers. Those state identifiers may then
+/// in turn access out-of-bounds memory in a DFA's search routine, where bounds
+/// checks are explicitly elided for performance reasons.
+pub unsafe trait StateID:
+ Clone + Copy + Debug + Eq + Hash + PartialEq + PartialOrd + Ord
+{
+ /// Convert from a `usize` to this implementation's representation.
+ ///
+ /// Implementors may assume that `n <= Self::max_id`. That is, implementors
+ /// do not need to check whether `n` can fit inside this implementation's
+ /// representation.
+ fn from_usize(n: usize) -> Self;
+
+ /// Convert this implementation's representation to a `usize`.
+ ///
+ /// Implementors must not return a `usize` value greater than
+ /// `Self::max_id` and must not permit overflow when converting between the
+ /// implementor's representation and `usize`. In general, the preferred
+ /// way for implementors to achieve this is to simply not provide
+ /// implementations of `StateID` that cannot fit into the target platform's
+ /// `usize`.
+ fn to_usize(self) -> usize;
+
+ /// Return the maximum state identifier supported by this representation.
+ ///
+ /// Implementors must return a correct bound. Doing otherwise may result
+ /// in memory unsafety.
+ fn max_id() -> usize;
+
+ /// Read a single state identifier from the given slice of bytes in native
+ /// endian format.
+ ///
+ /// Implementors may assume that the given slice has length at least
+ /// `size_of::<Self>()`.
+ fn read_bytes(slice: &[u8]) -> Self;
+
+ /// Write this state identifier to the given slice of bytes in native
+ /// endian format.
+ ///
+ /// Implementors may assume that the given slice has length at least
+ /// `size_of::<Self>()`.
+ fn write_bytes(self, slice: &mut [u8]);
+}
+
+unsafe impl StateID for usize {
+ #[inline]
+ fn from_usize(n: usize) -> usize {
+ n
+ }
+
+ #[inline]
+ fn to_usize(self) -> usize {
+ self
+ }
+
+ #[inline]
+ fn max_id() -> usize {
+ ::core::usize::MAX
+ }
+
+ #[inline]
+ fn read_bytes(slice: &[u8]) -> Self {
+ NativeEndian::read_uint(slice, size_of::<usize>()) as usize
+ }
+
+ #[inline]
+ fn write_bytes(self, slice: &mut [u8]) {
+ NativeEndian::write_uint(slice, self as u64, size_of::<usize>())
+ }
+}
+
+unsafe impl StateID for u8 {
+ #[inline]
+ fn from_usize(n: usize) -> u8 {
+ n as u8
+ }
+
+ #[inline]
+ fn to_usize(self) -> usize {
+ self as usize
+ }
+
+ #[inline]
+ fn max_id() -> usize {
+ ::core::u8::MAX as usize
+ }
+
+ #[inline]
+ fn read_bytes(slice: &[u8]) -> Self {
+ slice[0]
+ }
+
+ #[inline]
+ fn write_bytes(self, slice: &mut [u8]) {
+ slice[0] = self;
+ }
+}
+
+unsafe impl StateID for u16 {
+ #[inline]
+ fn from_usize(n: usize) -> u16 {
+ n as u16
+ }
+
+ #[inline]
+ fn to_usize(self) -> usize {
+ self as usize
+ }
+
+ #[inline]
+ fn max_id() -> usize {
+ ::core::u16::MAX as usize
+ }
+
+ #[inline]
+ fn read_bytes(slice: &[u8]) -> Self {
+ NativeEndian::read_u16(slice)
+ }
+
+ #[inline]
+ fn write_bytes(self, slice: &mut [u8]) {
+ NativeEndian::write_u16(slice, self)
+ }
+}
+
+#[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
+unsafe impl StateID for u32 {
+ #[inline]
+ fn from_usize(n: usize) -> u32 {
+ n as u32
+ }
+
+ #[inline]
+ fn to_usize(self) -> usize {
+ self as usize
+ }
+
+ #[inline]
+ fn max_id() -> usize {
+ ::core::u32::MAX as usize
+ }
+
+ #[inline]
+ fn read_bytes(slice: &[u8]) -> Self {
+ NativeEndian::read_u32(slice)
+ }
+
+ #[inline]
+ fn write_bytes(self, slice: &mut [u8]) {
+ NativeEndian::write_u32(slice, self)
+ }
+}
+
+#[cfg(target_pointer_width = "64")]
+unsafe impl StateID for u64 {
+ #[inline]
+ fn from_usize(n: usize) -> u64 {
+ n as u64
+ }
+
+ #[inline]
+ fn to_usize(self) -> usize {
+ self as usize
+ }
+
+ #[inline]
+ fn max_id() -> usize {
+ ::core::u64::MAX as usize
+ }
+
+ #[inline]
+ fn read_bytes(slice: &[u8]) -> Self {
+ NativeEndian::read_u64(slice)
+ }
+
+ #[inline]
+ fn write_bytes(self, slice: &mut [u8]) {
+ NativeEndian::write_u64(slice, self)
+ }
+}