src/state_id.rs - platform/external/rust/crates/regex-automata - Git at Google

 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)
     }
 }
	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)
	}
	}