3 use core
::mem
::size_of
;
5 use byteorder
::{ByteOrder, NativeEndian}
;
7 #[cfg(feature = "std")]
10 #[cfg(feature = "std")]
12 use byteorder
::ByteOrder
;
13 use core
::mem
::size_of
;
14 use error
::{Error, Result}
;
18 /// Check that the premultiplication of the given state identifier can
19 /// fit into the representation indicated by `S`. If it cannot, or if it
20 /// overflows `usize` itself, then an error is returned.
21 pub fn premultiply_overflow_error
<S
: StateID
>(
25 let requested
= match last_state
.to_usize().checked_mul(alphabet_len
) {
26 Some(requested
) => requested
,
27 None
=> return Err(Error
::premultiply_overflow(0, 0)),
29 if requested
> S
::max_id() {
30 return Err(Error
::premultiply_overflow(S
::max_id(), requested
));
35 /// Allocate the next sequential identifier for a fresh state given
36 /// the previously constructed state identified by `current`. If the
37 /// next sequential identifier would overflow `usize` or the chosen
38 /// representation indicated by `S`, then an error is returned.
39 pub fn next_state_id
<S
: StateID
>(current
: S
) -> Result
<S
> {
40 let next
= match current
.to_usize().checked_add(1) {
42 None
=> return Err(Error
::state_id_overflow(::std
::usize::MAX
)),
44 if next
> S
::max_id() {
45 return Err(Error
::state_id_overflow(S
::max_id()));
47 Ok(S
::from_usize(next
))
50 /// Convert the given `usize` to the chosen state identifier
51 /// representation. If the given value cannot fit in the chosen
52 /// representation, then an error is returned.
53 pub fn usize_to_state_id
<S
: StateID
>(value
: usize) -> Result
<S
> {
54 if value
> S
::max_id() {
55 Err(Error
::state_id_overflow(S
::max_id()))
57 Ok(S
::from_usize(value
))
61 /// Write the given identifier to the given slice of bytes using the
62 /// specified endianness. The given slice must have length at least
65 /// The given state identifier representation must have size 1, 2, 4 or 8.
66 pub fn write_state_id_bytes
<E
: ByteOrder
, S
: StateID
>(
72 || 2 == size_of
::<S
>()
73 || 4 == size_of
::<S
>()
74 || 8 == size_of
::<S
>()
77 match size_of
::<S
>() {
78 1 => slice
[0] = id
.to_usize() as u8,
79 2 => E
::write_u16(slice
, id
.to_usize() as u16),
80 4 => E
::write_u32(slice
, id
.to_usize() as u32),
81 8 => E
::write_u64(slice
, id
.to_usize() as u64),
87 /// Return the unique identifier for a DFA's dead state in the chosen
88 /// representation indicated by `S`.
89 pub fn dead_id
<S
: StateID
>() -> S
{
93 /// A trait describing the representation of a DFA's state identifier.
95 /// The purpose of this trait is to safely express both the possible state
96 /// identifier representations that can be used in a DFA and to convert between
97 /// state identifier representations and types that can be used to efficiently
98 /// index memory (such as `usize`).
100 /// In general, one should not need to implement this trait explicitly. In
101 /// particular, this crate provides implementations for `u8`, `u16`, `u32`,
102 /// `u64` and `usize`. (`u32` and `u64` are only provided for targets that can
103 /// represent all corresponding values in a `usize`.)
107 /// This trait is unsafe because the correctness of its implementations may be
108 /// relied upon by other unsafe code. For example, one possible way to
109 /// implement this trait incorrectly would be to return a maximum identifier
110 /// in `max_id` that is greater than the real maximum identifier. This will
111 /// likely result in wrap-on-overflow semantics in release mode, which can in
112 /// turn produce incorrect state identifiers. Those state identifiers may then
113 /// in turn access out-of-bounds memory in a DFA's search routine, where bounds
114 /// checks are explicitly elided for performance reasons.
115 pub unsafe trait StateID
:
116 Clone
+ Copy
+ Debug
+ Eq
+ Hash
+ PartialEq
+ PartialOrd
+ Ord
118 /// Convert from a `usize` to this implementation's representation.
120 /// Implementors may assume that `n <= Self::max_id`. That is, implementors
121 /// do not need to check whether `n` can fit inside this implementation's
123 fn from_usize(n
: usize) -> Self;
125 /// Convert this implementation's representation to a `usize`.
127 /// Implementors must not return a `usize` value greater than
128 /// `Self::max_id` and must not permit overflow when converting between the
129 /// implementor's representation and `usize`. In general, the preferred
130 /// way for implementors to achieve this is to simply not provide
131 /// implementations of `StateID` that cannot fit into the target platform's
133 fn to_usize(self) -> usize;
135 /// Return the maximum state identifier supported by this representation.
137 /// Implementors must return a correct bound. Doing otherwise may result
138 /// in memory unsafety.
139 fn max_id() -> usize;
141 /// Read a single state identifier from the given slice of bytes in native
144 /// Implementors may assume that the given slice has length at least
145 /// `size_of::<Self>()`.
146 fn read_bytes(slice
: &[u8]) -> Self;
148 /// Write this state identifier to the given slice of bytes in native
151 /// Implementors may assume that the given slice has length at least
152 /// `size_of::<Self>()`.
153 fn write_bytes(self, slice
: &mut [u8]);
156 unsafe impl StateID
for usize {
158 fn from_usize(n
: usize) -> usize {
163 fn to_usize(self) -> usize {
168 fn max_id() -> usize {
173 fn read_bytes(slice
: &[u8]) -> Self {
174 NativeEndian
::read_uint(slice
, size_of
::<usize>()) as usize
178 fn write_bytes(self, slice
: &mut [u8]) {
179 NativeEndian
::write_uint(slice
, self as u64, size_of
::<usize>())
183 unsafe impl StateID
for u8 {
185 fn from_usize(n
: usize) -> u8 {
190 fn to_usize(self) -> usize {
195 fn max_id() -> usize {
196 ::core
::u8::MAX
as usize
200 fn read_bytes(slice
: &[u8]) -> Self {
205 fn write_bytes(self, slice
: &mut [u8]) {
210 unsafe impl StateID
for u16 {
212 fn from_usize(n
: usize) -> u16 {
217 fn to_usize(self) -> usize {
222 fn max_id() -> usize {
223 ::core
::u16::MAX
as usize
227 fn read_bytes(slice
: &[u8]) -> Self {
228 NativeEndian
::read_u16(slice
)
232 fn write_bytes(self, slice
: &mut [u8]) {
233 NativeEndian
::write_u16(slice
, self)
237 #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
238 unsafe impl StateID
for u32 {
240 fn from_usize(n
: usize) -> u32 {
245 fn to_usize(self) -> usize {
250 fn max_id() -> usize {
251 ::core
::u32::MAX
as usize
255 fn read_bytes(slice
: &[u8]) -> Self {
256 NativeEndian
::read_u32(slice
)
260 fn write_bytes(self, slice
: &mut [u8]) {
261 NativeEndian
::write_u32(slice
, self)
265 #[cfg(target_pointer_width = "64")]
266 unsafe impl StateID
for u64 {
268 fn from_usize(n
: usize) -> u64 {
273 fn to_usize(self) -> usize {
278 fn max_id() -> usize {
279 ::core
::u64::MAX
as usize
283 fn read_bytes(slice
: &[u8]) -> Self {
284 NativeEndian
::read_u64(slice
)
288 fn write_bytes(self, slice
: &mut [u8]) {
289 NativeEndian
::write_u64(slice
, self)