diff options
Diffstat (limited to 'vendor/arbitrary/src/unstructured.rs')
| -rw-r--r-- | vendor/arbitrary/src/unstructured.rs | 1016 |
1 files changed, 1016 insertions, 0 deletions
diff --git a/vendor/arbitrary/src/unstructured.rs b/vendor/arbitrary/src/unstructured.rs new file mode 100644 index 000000000..6467659eb --- /dev/null +++ b/vendor/arbitrary/src/unstructured.rs @@ -0,0 +1,1016 @@ +// Copyright © 2019 The Rust Fuzz Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Wrappers around raw, unstructured bytes. + +use crate::{Arbitrary, Error, Result}; +use std::marker::PhantomData; +use std::ops::ControlFlow; +use std::{mem, ops}; + +/// A source of unstructured data. +/// +/// An `Unstructured` helps `Arbitrary` implementations interpret raw data +/// (typically provided by a fuzzer) as a "DNA string" that describes how to +/// construct the `Arbitrary` type. The goal is that a small change to the "DNA +/// string" (the raw data wrapped by an `Unstructured`) results in a small +/// change to the generated `Arbitrary` instance. This helps a fuzzer +/// efficiently explore the `Arbitrary`'s input space. +/// +/// `Unstructured` is deterministic: given the same raw data, the same series of +/// API calls will return the same results (modulo system resource constraints, +/// like running out of memory). However, `Unstructured` does not guarantee +/// anything beyond that: it makes not guarantee that it will yield bytes from +/// the underlying data in any particular order. +/// +/// You shouldn't generally need to use an `Unstructured` unless you are writing +/// a custom `Arbitrary` implementation by hand, instead of deriving it. Mostly, +/// you should just be passing it through to nested `Arbitrary::arbitrary` +/// calls. +/// +/// # Example +/// +/// Imagine you were writing a color conversion crate. You might want to write +/// fuzz tests that take a random RGB color and assert various properties, run +/// functions and make sure nothing panics, etc. +/// +/// Below is what translating the fuzzer's raw input into an `Unstructured` and +/// using that to generate an arbitrary RGB color might look like: +/// +/// ``` +/// # #[cfg(feature = "derive")] fn foo() { +/// use arbitrary::{Arbitrary, Unstructured}; +/// +/// /// An RGB color. +/// #[derive(Arbitrary)] +/// pub struct Rgb { +/// r: u8, +/// g: u8, +/// b: u8, +/// } +/// +/// // Get the raw bytes from the fuzzer. +/// # let get_input_from_fuzzer = || &[]; +/// let raw_data: &[u8] = get_input_from_fuzzer(); +/// +/// // Wrap it in an `Unstructured`. +/// let mut unstructured = Unstructured::new(raw_data); +/// +/// // Generate an `Rgb` color and run our checks. +/// if let Ok(rgb) = Rgb::arbitrary(&mut unstructured) { +/// # let run_my_color_conversion_checks = |_| {}; +/// run_my_color_conversion_checks(rgb); +/// } +/// # } +/// ``` +pub struct Unstructured<'a> { + data: &'a [u8], +} + +impl<'a> Unstructured<'a> { + /// Create a new `Unstructured` from the given raw data. + /// + /// # Example + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let u = Unstructured::new(&[1, 2, 3, 4]); + /// ``` + pub fn new(data: &'a [u8]) -> Self { + Unstructured { data } + } + + /// Get the number of remaining bytes of underlying data that are still + /// available. + /// + /// # Example + /// + /// ``` + /// use arbitrary::{Arbitrary, Unstructured}; + /// + /// let mut u = Unstructured::new(&[1, 2, 3]); + /// + /// // Initially have three bytes of data. + /// assert_eq!(u.len(), 3); + /// + /// // Generating a `bool` consumes one byte from the underlying data, so + /// // we are left with two bytes afterwards. + /// let _ = bool::arbitrary(&mut u); + /// assert_eq!(u.len(), 2); + /// ``` + #[inline] + pub fn len(&self) -> usize { + self.data.len() + } + + /// Is the underlying unstructured data exhausted? + /// + /// `unstructured.is_empty()` is the same as `unstructured.len() == 0`. + /// + /// # Example + /// + /// ``` + /// use arbitrary::{Arbitrary, Unstructured}; + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4]); + /// + /// // Initially, we are not empty. + /// assert!(!u.is_empty()); + /// + /// // Generating a `u32` consumes all four bytes of the underlying data, so + /// // we become empty afterwards. + /// let _ = u32::arbitrary(&mut u); + /// assert!(u.is_empty()); + /// ``` + #[inline] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Generate an arbitrary instance of `A`. + /// + /// This is simply a helper method that is equivalent to `<A as + /// Arbitrary>::arbitrary(self)`. This helper is a little bit more concise, + /// and can be used in situations where Rust's type inference will figure + /// out what `A` should be. + /// + /// # Example + /// + /// ``` + /// # #[cfg(feature="derive")] fn foo() -> arbitrary::Result<()> { + /// use arbitrary::{Arbitrary, Unstructured}; + /// + /// #[derive(Arbitrary)] + /// struct MyType { + /// // ... + /// } + /// + /// fn do_stuff(value: MyType) { + /// # let _ = value; + /// // ... + /// } + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4]); + /// + /// // Rust's type inference can figure out that `value` should be of type + /// // `MyType` here: + /// let value = u.arbitrary()?; + /// do_stuff(value); + /// # Ok(()) } + /// ``` + pub fn arbitrary<A>(&mut self) -> Result<A> + where + A: Arbitrary<'a>, + { + <A as Arbitrary<'a>>::arbitrary(self) + } + + /// Get the number of elements to insert when building up a collection of + /// arbitrary `ElementType`s. + /// + /// This uses the [`<ElementType as + /// Arbitrary>::size_hint`][crate::Arbitrary::size_hint] method to smartly + /// choose a length such that we most likely have enough underlying bytes to + /// construct that many arbitrary `ElementType`s. + /// + /// This should only be called within an `Arbitrary` implementation. + /// + /// # Example + /// + /// ``` + /// use arbitrary::{Arbitrary, Result, Unstructured}; + /// # pub struct MyCollection<T> { _t: std::marker::PhantomData<T> } + /// # impl<T> MyCollection<T> { + /// # pub fn with_capacity(capacity: usize) -> Self { MyCollection { _t: std::marker::PhantomData } } + /// # pub fn insert(&mut self, element: T) {} + /// # } + /// + /// impl<'a, T> Arbitrary<'a> for MyCollection<T> + /// where + /// T: Arbitrary<'a>, + /// { + /// fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> { + /// // Get the number of `T`s we should insert into our collection. + /// let len = u.arbitrary_len::<T>()?; + /// + /// // And then create a collection of that length! + /// let mut my_collection = MyCollection::with_capacity(len); + /// for _ in 0..len { + /// let element = T::arbitrary(u)?; + /// my_collection.insert(element); + /// } + /// + /// Ok(my_collection) + /// } + /// } + /// ``` + pub fn arbitrary_len<ElementType>(&mut self) -> Result<usize> + where + ElementType: Arbitrary<'a>, + { + let byte_size = self.arbitrary_byte_size()?; + let (lower, upper) = <ElementType as Arbitrary>::size_hint(0); + let elem_size = upper.unwrap_or(lower * 2); + let elem_size = std::cmp::max(1, elem_size); + Ok(byte_size / elem_size) + } + + fn arbitrary_byte_size(&mut self) -> Result<usize> { + if self.data.is_empty() { + Ok(0) + } else if self.data.len() == 1 { + self.data = &[]; + Ok(0) + } else { + // Take lengths from the end of the data, since the `libFuzzer` folks + // found that this lets fuzzers more efficiently explore the input + // space. + // + // https://github.com/rust-fuzz/libfuzzer-sys/blob/0c450753/libfuzzer/utils/FuzzedDataProvider.h#L92-L97 + + // We only consume as many bytes as necessary to cover the entire + // range of the byte string. + // Note: We cast to u64 so we don't overflow when checking std::u32::MAX + 4 on 32-bit archs + let len = if self.data.len() as u64 <= std::u8::MAX as u64 + 1 { + let bytes = 1; + let max_size = self.data.len() - bytes; + let (rest, for_size) = self.data.split_at(max_size); + self.data = rest; + Self::int_in_range_impl(0..=max_size as u8, for_size.iter().copied())?.0 as usize + } else if self.data.len() as u64 <= std::u16::MAX as u64 + 2 { + let bytes = 2; + let max_size = self.data.len() - bytes; + let (rest, for_size) = self.data.split_at(max_size); + self.data = rest; + Self::int_in_range_impl(0..=max_size as u16, for_size.iter().copied())?.0 as usize + } else if self.data.len() as u64 <= std::u32::MAX as u64 + 4 { + let bytes = 4; + let max_size = self.data.len() - bytes; + let (rest, for_size) = self.data.split_at(max_size); + self.data = rest; + Self::int_in_range_impl(0..=max_size as u32, for_size.iter().copied())?.0 as usize + } else { + let bytes = 8; + let max_size = self.data.len() - bytes; + let (rest, for_size) = self.data.split_at(max_size); + self.data = rest; + Self::int_in_range_impl(0..=max_size as u64, for_size.iter().copied())?.0 as usize + }; + + Ok(len) + } + } + + /// Generate an integer within the given range. + /// + /// Do not use this to generate the size of a collection. Use + /// `arbitrary_len` instead. + /// + /// # Panics + /// + /// Panics if `range.start > range.end`. That is, the given range must be + /// non-empty. + /// + /// # Example + /// + /// ``` + /// use arbitrary::{Arbitrary, Unstructured}; + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4]); + /// + /// let x: i32 = u.int_in_range(-5_000..=-1_000) + /// .expect("constructed `u` with enough bytes to generate an `i32`"); + /// + /// assert!(-5_000 <= x); + /// assert!(x <= -1_000); + /// ``` + pub fn int_in_range<T>(&mut self, range: ops::RangeInclusive<T>) -> Result<T> + where + T: Int, + { + let (result, bytes_consumed) = Self::int_in_range_impl(range, self.data.iter().cloned())?; + self.data = &self.data[bytes_consumed..]; + Ok(result) + } + + fn int_in_range_impl<T>( + range: ops::RangeInclusive<T>, + mut bytes: impl Iterator<Item = u8>, + ) -> Result<(T, usize)> + where + T: Int, + { + let start = *range.start(); + let end = *range.end(); + assert!( + start <= end, + "`arbitrary::Unstructured::int_in_range` requires a non-empty range" + ); + + // When there is only one possible choice, don't waste any entropy from + // the underlying data. + if start == end { + return Ok((start, 0)); + } + + // From here on out we work with the unsigned representation. All of the + // operations performed below work out just as well whether or not `T` + // is a signed or unsigned integer. + let start = start.to_unsigned(); + let end = end.to_unsigned(); + + let delta = end.wrapping_sub(start); + debug_assert_ne!(delta, T::Unsigned::ZERO); + + // Compute an arbitrary integer offset from the start of the range. We + // do this by consuming `size_of(T)` bytes from the input to create an + // arbitrary integer and then clamping that int into our range bounds + // with a modulo operation. + let mut arbitrary_int = T::Unsigned::ZERO; + let mut bytes_consumed: usize = 0; + + while (bytes_consumed < mem::size_of::<T>()) + && (delta >> T::Unsigned::from_usize(bytes_consumed * 8)) > T::Unsigned::ZERO + { + let byte = match bytes.next() { + None => break, + Some(b) => b, + }; + bytes_consumed += 1; + + // Combine this byte into our arbitrary integer, but avoid + // overflowing the shift for `u8` and `i8`. + arbitrary_int = if mem::size_of::<T>() == 1 { + T::Unsigned::from_u8(byte) + } else { + (arbitrary_int << 8) | T::Unsigned::from_u8(byte) + }; + } + + let offset = if delta == T::Unsigned::MAX { + arbitrary_int + } else { + arbitrary_int % (delta.checked_add(T::Unsigned::ONE).unwrap()) + }; + + // Finally, we add `start` to our offset from `start` to get the result + // actual value within the range. + let result = start.wrapping_add(offset); + + // And convert back to our maybe-signed representation. + let result = T::from_unsigned(result); + debug_assert!(*range.start() <= result); + debug_assert!(result <= *range.end()); + + Ok((result, bytes_consumed)) + } + + /// Choose one of the given choices. + /// + /// This should only be used inside of `Arbitrary` implementations. + /// + /// Returns an error if there is not enough underlying data to make a + /// choice or if no choices are provided. + /// + /// # Examples + /// + /// Selecting from an array of choices: + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]); + /// let choices = ['a', 'b', 'c', 'd', 'e', 'f', 'g']; + /// + /// let choice = u.choose(&choices).unwrap(); + /// + /// println!("chose {}", choice); + /// ``` + /// + /// An error is returned if no choices are provided: + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]); + /// let choices: [char; 0] = []; + /// + /// let result = u.choose(&choices); + /// + /// assert!(result.is_err()); + /// ``` + pub fn choose<'b, T>(&mut self, choices: &'b [T]) -> Result<&'b T> { + let idx = self.choose_index(choices.len())?; + Ok(&choices[idx]) + } + + /// Choose a value in `0..len`. + /// + /// Returns an error if the `len` is zero. + /// + /// # Examples + /// + /// Using Fisher–Yates shuffle shuffle to gerate an arbitrary permutation. + /// + /// [Fisher–Yates shuffle]: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]); + /// let mut permutation = ['a', 'b', 'c', 'd', 'e', 'f', 'g']; + /// let mut to_permute = &mut permutation[..]; + /// while to_permute.len() > 1 { + /// let idx = u.choose_index(to_permute.len()).unwrap(); + /// to_permute.swap(0, idx); + /// to_permute = &mut to_permute[1..]; + /// } + /// + /// println!("permutation: {:?}", permutation); + /// ``` + /// + /// An error is returned if the length is zero: + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]); + /// let array: [i32; 0] = []; + /// + /// let result = u.choose_index(array.len()); + /// + /// assert!(result.is_err()); + /// ``` + pub fn choose_index(&mut self, len: usize) -> Result<usize> { + if len == 0 { + return Err(Error::EmptyChoose); + } + let idx = self.int_in_range(0..=len - 1)?; + Ok(idx) + } + + /// Generate a boolean according to the given ratio. + /// + /// # Panics + /// + /// Panics when the numerator and denominator do not meet these constraints: + /// + /// * `0 < numerator <= denominator` + /// + /// # Example + /// + /// Generate a boolean that is `true` five sevenths of the time: + /// + /// ``` + /// # fn foo() -> arbitrary::Result<()> { + /// use arbitrary::Unstructured; + /// + /// # let my_data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]; + /// let mut u = Unstructured::new(&my_data); + /// + /// if u.ratio(5, 7)? { + /// // Take this branch 5/7 of the time. + /// } + /// # Ok(()) + /// # } + /// ``` + pub fn ratio<T>(&mut self, numerator: T, denominator: T) -> Result<bool> + where + T: Int, + { + assert!(T::ZERO < numerator); + assert!(numerator <= denominator); + let x = self.int_in_range(T::ONE..=denominator)?; + Ok(x <= numerator) + } + + /// Fill a `buffer` with bytes from the underlying raw data. + /// + /// This should only be called within an `Arbitrary` implementation. This is + /// a very low-level operation. You should generally prefer calling nested + /// `Arbitrary` implementations like `<Vec<u8>>::arbitrary` and + /// `String::arbitrary` over using this method directly. + /// + /// If this `Unstructured` does not have enough underlying data to fill the + /// whole `buffer`, it pads the buffer out with zeros. + /// + /// # Example + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4]); + /// + /// let mut buf = [0; 2]; + /// + /// assert!(u.fill_buffer(&mut buf).is_ok()); + /// assert_eq!(buf, [1, 2]); + /// + /// assert!(u.fill_buffer(&mut buf).is_ok()); + /// assert_eq!(buf, [3, 4]); + /// + /// assert!(u.fill_buffer(&mut buf).is_ok()); + /// assert_eq!(buf, [0, 0]); + /// ``` + pub fn fill_buffer(&mut self, buffer: &mut [u8]) -> Result<()> { + let n = std::cmp::min(buffer.len(), self.data.len()); + buffer[..n].copy_from_slice(&self.data[..n]); + for byte in buffer[n..].iter_mut() { + *byte = 0; + } + self.data = &self.data[n..]; + Ok(()) + } + + /// Provide `size` bytes from the underlying raw data. + /// + /// This should only be called within an `Arbitrary` implementation. This is + /// a very low-level operation. You should generally prefer calling nested + /// `Arbitrary` implementations like `<Vec<u8>>::arbitrary` and + /// `String::arbitrary` over using this method directly. + /// + /// # Example + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let mut u = Unstructured::new(&[1, 2, 3, 4]); + /// + /// assert!(u.bytes(2).unwrap() == &[1, 2]); + /// assert!(u.bytes(2).unwrap() == &[3, 4]); + /// ``` + pub fn bytes(&mut self, size: usize) -> Result<&'a [u8]> { + if self.data.len() < size { + return Err(Error::NotEnoughData); + } + + let (for_buf, rest) = self.data.split_at(size); + self.data = rest; + Ok(for_buf) + } + + /// Peek at `size` number of bytes of the underlying raw input. + /// + /// Does not consume the bytes, only peeks at them. + /// + /// Returns `None` if there are not `size` bytes left in the underlying raw + /// input. + /// + /// # Example + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let u = Unstructured::new(&[1, 2, 3]); + /// + /// assert_eq!(u.peek_bytes(0).unwrap(), []); + /// assert_eq!(u.peek_bytes(1).unwrap(), [1]); + /// assert_eq!(u.peek_bytes(2).unwrap(), [1, 2]); + /// assert_eq!(u.peek_bytes(3).unwrap(), [1, 2, 3]); + /// + /// assert!(u.peek_bytes(4).is_none()); + /// ``` + pub fn peek_bytes(&self, size: usize) -> Option<&'a [u8]> { + self.data.get(..size) + } + + /// Consume all of the rest of the remaining underlying bytes. + /// + /// Returns a slice of all the remaining, unconsumed bytes. + /// + /// # Example + /// + /// ``` + /// use arbitrary::Unstructured; + /// + /// let mut u = Unstructured::new(&[1, 2, 3]); + /// + /// let mut remaining = u.take_rest(); + /// + /// assert_eq!(remaining, [1, 2, 3]); + /// ``` + pub fn take_rest(mut self) -> &'a [u8] { + mem::take(&mut self.data) + } + + /// Provide an iterator over elements for constructing a collection + /// + /// This is useful for implementing [`Arbitrary::arbitrary`] on collections + /// since the implementation is simply `u.arbitrary_iter()?.collect()` + pub fn arbitrary_iter<'b, ElementType: Arbitrary<'a>>( + &'b mut self, + ) -> Result<ArbitraryIter<'a, 'b, ElementType>> { + Ok(ArbitraryIter { + u: &mut *self, + _marker: PhantomData, + }) + } + + /// Provide an iterator over elements for constructing a collection from + /// all the remaining bytes. + /// + /// This is useful for implementing [`Arbitrary::arbitrary_take_rest`] on collections + /// since the implementation is simply `u.arbitrary_take_rest_iter()?.collect()` + pub fn arbitrary_take_rest_iter<ElementType: Arbitrary<'a>>( + self, + ) -> Result<ArbitraryTakeRestIter<'a, ElementType>> { + Ok(ArbitraryTakeRestIter { + u: self, + _marker: PhantomData, + }) + } + + /// Call the given function an arbitrary number of times. + /// + /// The function is given this `Unstructured` so that it can continue to + /// generate arbitrary data and structures. + /// + /// You may optionaly specify minimum and maximum bounds on the number of + /// times the function is called. + /// + /// You may break out of the loop early by returning + /// `Ok(std::ops::ControlFlow::Break)`. To continue the loop, return + /// `Ok(std::ops::ControlFlow::Continue)`. + /// + /// # Panics + /// + /// Panics if `min > max`. + /// + /// # Example + /// + /// Call a closure that generates an arbitrary type inside a context an + /// arbitrary number of times: + /// + /// ``` + /// use arbitrary::{Result, Unstructured}; + /// use std::ops::ControlFlow; + /// + /// enum Type { + /// /// A boolean type. + /// Bool, + /// + /// /// An integer type. + /// Int, + /// + /// /// A list of the `i`th type in this type's context. + /// List(usize), + /// } + /// + /// fn arbitrary_types_context(u: &mut Unstructured) -> Result<Vec<Type>> { + /// let mut context = vec![]; + /// + /// u.arbitrary_loop(Some(10), Some(20), |u| { + /// let num_choices = if context.is_empty() { + /// 2 + /// } else { + /// 3 + /// }; + /// let ty = match u.int_in_range::<u8>(1..=num_choices)? { + /// 1 => Type::Bool, + /// 2 => Type::Int, + /// 3 => Type::List(u.int_in_range(0..=context.len() - 1)?), + /// _ => unreachable!(), + /// }; + /// context.push(ty); + /// Ok(ControlFlow::Continue(())) + /// })?; + /// + /// // The number of loop iterations are constrained by the min/max + /// // bounds that we provided. + /// assert!(context.len() >= 10); + /// assert!(context.len() <= 20); + /// + /// Ok(context) + /// } + /// ``` + pub fn arbitrary_loop( + &mut self, + min: Option<u32>, + max: Option<u32>, + mut f: impl FnMut(&mut Self) -> Result<ControlFlow<(), ()>>, + ) -> Result<()> { + let min = min.unwrap_or(0); + let max = max.unwrap_or(u32::MAX); + + for _ in 0..self.int_in_range(min..=max)? { + match f(self)? { + ControlFlow::Continue(_) => continue, + ControlFlow::Break(_) => break, + } + } + + Ok(()) + } +} + +/// Utility iterator produced by [`Unstructured::arbitrary_iter`] +pub struct ArbitraryIter<'a, 'b, ElementType> { + u: &'b mut Unstructured<'a>, + _marker: PhantomData<ElementType>, +} + +impl<'a, 'b, ElementType: Arbitrary<'a>> Iterator for ArbitraryIter<'a, 'b, ElementType> { + type Item = Result<ElementType>; + fn next(&mut self) -> Option<Result<ElementType>> { + let keep_going = self.u.arbitrary().unwrap_or(false); + if keep_going { + Some(Arbitrary::arbitrary(self.u)) + } else { + None + } + } +} + +/// Utility iterator produced by [`Unstructured::arbitrary_take_rest_iter`] +pub struct ArbitraryTakeRestIter<'a, ElementType> { + u: Unstructured<'a>, + _marker: PhantomData<ElementType>, +} + +impl<'a, ElementType: Arbitrary<'a>> Iterator for ArbitraryTakeRestIter<'a, ElementType> { + type Item = Result<ElementType>; + fn next(&mut self) -> Option<Result<ElementType>> { + let keep_going = self.u.arbitrary().unwrap_or(false); + if keep_going { + Some(Arbitrary::arbitrary(&mut self.u)) + } else { + None + } + } +} + +/// A trait that is implemented for all of the primitive integers: +/// +/// * `u8` +/// * `u16` +/// * `u32` +/// * `u64` +/// * `u128` +/// * `usize` +/// * `i8` +/// * `i16` +/// * `i32` +/// * `i64` +/// * `i128` +/// * `isize` +/// +/// Don't implement this trait yourself. +pub trait Int: + Copy + + std::fmt::Debug + + PartialOrd + + Ord + + ops::Sub<Self, Output = Self> + + ops::Rem<Self, Output = Self> + + ops::Shr<Self, Output = Self> + + ops::Shl<usize, Output = Self> + + ops::BitOr<Self, Output = Self> +{ + #[doc(hidden)] + type Unsigned: Int; + + #[doc(hidden)] + const ZERO: Self; + + #[doc(hidden)] + const ONE: Self; + + #[doc(hidden)] + const MAX: Self; + + #[doc(hidden)] + fn from_u8(b: u8) -> Self; + + #[doc(hidden)] + fn from_usize(u: usize) -> Self; + + #[doc(hidden)] + fn checked_add(self, rhs: Self) -> Option<Self>; + + #[doc(hidden)] + fn wrapping_add(self, rhs: Self) -> Self; + + #[doc(hidden)] + fn wrapping_sub(self, rhs: Self) -> Self; + + #[doc(hidden)] + fn to_unsigned(self) -> Self::Unsigned; + + #[doc(hidden)] + fn from_unsigned(unsigned: Self::Unsigned) -> Self; +} + +macro_rules! impl_int { + ( $( $ty:ty : $unsigned_ty: ty ; )* ) => { + $( + impl Int for $ty { + type Unsigned = $unsigned_ty; + + const ZERO: Self = 0; + + const ONE: Self = 1; + + const MAX: Self = Self::MAX; + + fn from_u8(b: u8) -> Self { + b as Self + } + + fn from_usize(u: usize) -> Self { + u as Self + } + + fn checked_add(self, rhs: Self) -> Option<Self> { + <$ty>::checked_add(self, rhs) + } + + fn wrapping_add(self, rhs: Self) -> Self { + <$ty>::wrapping_add(self, rhs) + } + + fn wrapping_sub(self, rhs: Self) -> Self { + <$ty>::wrapping_sub(self, rhs) + } + + fn to_unsigned(self) -> Self::Unsigned { + self as $unsigned_ty + } + + fn from_unsigned(unsigned: $unsigned_ty) -> Self { + unsigned as Self + } + } + )* + } +} + +impl_int! { + u8: u8; + u16: u16; + u32: u32; + u64: u64; + u128: u128; + usize: usize; + i8: u8; + i16: u16; + i32: u32; + i64: u64; + i128: u128; + isize: usize; +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_byte_size() { + let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 6]); + // Should take one byte off the end + assert_eq!(u.arbitrary_byte_size().unwrap(), 6); + assert_eq!(u.len(), 9); + let mut v = vec![]; + v.resize(260, 0); + v.push(1); + v.push(4); + let mut u = Unstructured::new(&v); + // Should read two bytes off the end + assert_eq!(u.arbitrary_byte_size().unwrap(), 0x104); + assert_eq!(u.len(), 260); + } + + #[test] + fn int_in_range_of_one() { + let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 6]); + let x = u.int_in_range(0..=0).unwrap(); + assert_eq!(x, 0); + let choice = *u.choose(&[42]).unwrap(); + assert_eq!(choice, 42) + } + + #[test] + fn int_in_range_uses_minimal_amount_of_bytes() { + let mut u = Unstructured::new(&[1, 2]); + assert_eq!(1, u.int_in_range::<u8>(0..=u8::MAX).unwrap()); + assert_eq!(u.len(), 1); + + let mut u = Unstructured::new(&[1, 2]); + assert_eq!(1, u.int_in_range::<u32>(0..=u8::MAX as u32).unwrap()); + assert_eq!(u.len(), 1); + + let mut u = Unstructured::new(&[1]); + assert_eq!(1, u.int_in_range::<u32>(0..=u8::MAX as u32 + 1).unwrap()); + assert!(u.is_empty()); + } + + #[test] + fn int_in_range_in_bounds() { + for input in u8::MIN..=u8::MAX { + let input = [input]; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(1..=u8::MAX).unwrap(); + assert_ne!(x, 0); + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(0..=u8::MAX - 1).unwrap(); + assert_ne!(x, u8::MAX); + } + } + + #[test] + fn int_in_range_covers_unsigned_range() { + // Test that we generate all values within the range given to + // `int_in_range`. + + let mut full = [false; u8::MAX as usize + 1]; + let mut no_zero = [false; u8::MAX as usize]; + let mut no_max = [false; u8::MAX as usize]; + let mut narrow = [false; 10]; + + for input in u8::MIN..=u8::MAX { + let input = [input]; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(0..=u8::MAX).unwrap(); + full[x as usize] = true; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(1..=u8::MAX).unwrap(); + no_zero[x as usize - 1] = true; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(0..=u8::MAX - 1).unwrap(); + no_max[x as usize] = true; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(100..=109).unwrap(); + narrow[x as usize - 100] = true; + } + + for (i, covered) in full.iter().enumerate() { + assert!(covered, "full[{}] should have been generated", i); + } + for (i, covered) in no_zero.iter().enumerate() { + assert!(covered, "no_zero[{}] should have been generated", i); + } + for (i, covered) in no_max.iter().enumerate() { + assert!(covered, "no_max[{}] should have been generated", i); + } + for (i, covered) in narrow.iter().enumerate() { + assert!(covered, "narrow[{}] should have been generated", i); + } + } + + #[test] + fn int_in_range_covers_signed_range() { + // Test that we generate all values within the range given to + // `int_in_range`. + + let mut full = [false; u8::MAX as usize + 1]; + let mut no_min = [false; u8::MAX as usize]; + let mut no_max = [false; u8::MAX as usize]; + let mut narrow = [false; 21]; + + let abs_i8_min: isize = 128; + + for input in 0..=u8::MAX { + let input = [input]; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(i8::MIN..=i8::MAX).unwrap(); + full[(x as isize + abs_i8_min) as usize] = true; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(i8::MIN + 1..=i8::MAX).unwrap(); + no_min[(x as isize + abs_i8_min - 1) as usize] = true; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(i8::MIN..=i8::MAX - 1).unwrap(); + no_max[(x as isize + abs_i8_min) as usize] = true; + + let mut u = Unstructured::new(&input); + let x = u.int_in_range(-10..=10).unwrap(); + narrow[(x as isize + 10) as usize] = true; + } + + for (i, covered) in full.iter().enumerate() { + assert!(covered, "full[{}] should have been generated", i); + } + for (i, covered) in no_min.iter().enumerate() { + assert!(covered, "no_min[{}] should have been generated", i); + } + for (i, covered) in no_max.iter().enumerate() { + assert!(covered, "no_max[{}] should have been generated", i); + } + for (i, covered) in narrow.iter().enumerate() { + assert!(covered, "narrow[{}] should have been generated", i); + } + } +} |