| use std::char; |
| use std::collections::{ |
| BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque, |
| }; |
| use std::env; |
| use std::ffi::{CString, OsString}; |
| use std::hash::{BuildHasher, Hash}; |
| use std::iter::{empty, once}; |
| use std::net::{ |
| IpAddr, Ipv4Addr, Ipv6Addr, SocketAddr, SocketAddrV4, SocketAddrV6, |
| }; |
| use std::num::Wrapping; |
| use std::num::{ |
| NonZeroU128, NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8, NonZeroUsize, |
| }; |
| use std::ops::{ |
| Bound, Range, RangeFrom, RangeFull, RangeInclusive, RangeTo, |
| RangeToInclusive, |
| }; |
| use std::path::PathBuf; |
| use std::sync::Arc; |
| use std::time::{Duration, SystemTime, UNIX_EPOCH}; |
| |
| use rand::seq::SliceRandom; |
| use rand::{self, Rng, SeedableRng}; |
| |
| /// Gen represents a PRNG. |
| /// |
| /// It is the source of randomness from which QuickCheck will generate |
| /// values. An instance of `Gen` is passed to every invocation of |
| /// `Arbitrary::arbitrary`, which permits callers to use lower level RNG |
| /// routines to generate values. |
| /// |
| /// It is unspecified whether this is a secure RNG or not. Therefore, callers |
| /// should assume it is insecure. |
| pub struct Gen { |
| rng: rand::rngs::SmallRng, |
| size: usize, |
| } |
| |
| impl Gen { |
| /// Returns a `Gen` with the given size configuration. |
| /// |
| /// The `size` parameter controls the size of random values generated. |
| /// For example, it specifies the maximum length of a randomly generated |
| /// vector, but is and should not be used to control the range of a |
| /// randomly generated number. (Unless that number is used to control the |
| /// size of a data structure.) |
| pub fn new(size: usize) -> Gen { |
| Gen { rng: rand::rngs::SmallRng::from_entropy(), size: size } |
| } |
| |
| /// Returns the size configured with this generator. |
| pub fn size(&self) -> usize { |
| self.size |
| } |
| |
| /// Choose among the possible alternatives in the slice given. If the slice |
| /// is empty, then `None` is returned. Otherwise, a non-`None` value is |
| /// guaranteed to be returned. |
| pub fn choose<'a, T>(&mut self, slice: &'a [T]) -> Option<&'a T> { |
| slice.choose(&mut self.rng) |
| } |
| |
| fn gen<T>(&mut self) -> T |
| where |
| rand::distributions::Standard: rand::distributions::Distribution<T>, |
| { |
| self.rng.gen() |
| } |
| |
| fn gen_range<T, R>(&mut self, range: R) -> T |
| where |
| T: rand::distributions::uniform::SampleUniform, |
| R: rand::distributions::uniform::SampleRange<T>, |
| { |
| self.rng.gen_range(range) |
| } |
| } |
| |
| /// Creates a shrinker with zero elements. |
| pub fn empty_shrinker<A: 'static>() -> Box<dyn Iterator<Item = A>> { |
| Box::new(empty()) |
| } |
| |
| /// Creates a shrinker with a single element. |
| pub fn single_shrinker<A: 'static>(value: A) -> Box<dyn Iterator<Item = A>> { |
| Box::new(once(value)) |
| } |
| |
| /// `Arbitrary` describes types whose values can be randomly generated and |
| /// shrunk. |
| /// |
| /// Aside from shrinking, `Arbitrary` is different from typical RNGs in that |
| /// it respects `Gen::size()` for controlling how much memory a particular |
| /// value uses, for practical purposes. For example, `Vec::arbitrary()` |
| /// respects `Gen::size()` to decide the maximum `len()` of the vector. |
| /// This behavior is necessary due to practical speed and size limitations. |
| /// Conversely, `i32::arbitrary()` ignores `size()` since all `i32` values |
| /// require `O(1)` memory and operations between `i32`s require `O(1)` time |
| /// (with the exception of exponentiation). |
| /// |
| /// Additionally, all types that implement `Arbitrary` must also implement |
| /// `Clone`. |
| pub trait Arbitrary: Clone + 'static { |
| /// Return an arbitrary value. |
| /// |
| /// Implementations should respect `Gen::size()` when decisions about how |
| /// big a particular value should be. Implementations should generally |
| /// defer to other `Arbitrary` implementations to generate other random |
| /// values when necessary. The `Gen` type also offers a few RNG helper |
| /// routines. |
| fn arbitrary(g: &mut Gen) -> Self; |
| |
| /// Return an iterator of values that are smaller than itself. |
| /// |
| /// The way in which a value is "smaller" is implementation defined. In |
| /// some cases, the interpretation is obvious: shrinking an integer should |
| /// produce integers smaller than itself. Others are more complex, for |
| /// example, shrinking a `Vec` should both shrink its size and shrink its |
| /// component values. |
| /// |
| /// The iterator returned should be bounded to some reasonable size. |
| /// |
| /// It is always correct to return an empty iterator, and indeed, this |
| /// is the default implementation. The downside of this approach is that |
| /// witnesses to failures in properties will be more inscrutable. |
| fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { |
| empty_shrinker() |
| } |
| } |
| |
| impl Arbitrary for () { |
| fn arbitrary(_: &mut Gen) -> () { |
| () |
| } |
| } |
| |
| impl Arbitrary for bool { |
| fn arbitrary(g: &mut Gen) -> bool { |
| g.gen() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = bool>> { |
| if *self { |
| single_shrinker(false) |
| } else { |
| empty_shrinker() |
| } |
| } |
| } |
| |
| impl<A: Arbitrary> Arbitrary for Option<A> { |
| fn arbitrary(g: &mut Gen) -> Option<A> { |
| if g.gen() { |
| None |
| } else { |
| Some(Arbitrary::arbitrary(g)) |
| } |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Option<A>>> { |
| match *self { |
| None => empty_shrinker(), |
| Some(ref x) => { |
| let chain = single_shrinker(None).chain(x.shrink().map(Some)); |
| Box::new(chain) |
| } |
| } |
| } |
| } |
| |
| impl<A: Arbitrary, B: Arbitrary> Arbitrary for Result<A, B> { |
| fn arbitrary(g: &mut Gen) -> Result<A, B> { |
| if g.gen() { |
| Ok(Arbitrary::arbitrary(g)) |
| } else { |
| Err(Arbitrary::arbitrary(g)) |
| } |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Result<A, B>>> { |
| match *self { |
| Ok(ref x) => { |
| let xs = x.shrink(); |
| let tagged = xs.map(Ok); |
| Box::new(tagged) |
| } |
| Err(ref x) => { |
| let xs = x.shrink(); |
| let tagged = xs.map(Err); |
| Box::new(tagged) |
| } |
| } |
| } |
| } |
| |
| macro_rules! impl_arb_for_single_tuple { |
| ($(($type_param:ident, $tuple_index:tt),)*) => { |
| impl<$($type_param),*> Arbitrary for ($($type_param,)*) |
| where $($type_param: Arbitrary,)* |
| { |
| fn arbitrary(g: &mut Gen) -> ($($type_param,)*) { |
| ( |
| $( |
| $type_param::arbitrary(g), |
| )* |
| ) |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item=($($type_param,)*)>> { |
| let iter = ::std::iter::empty(); |
| $( |
| let cloned = self.clone(); |
| let iter = iter.chain( |
| self.$tuple_index.shrink().map(move |shr_value| { |
| let mut result = cloned.clone(); |
| result.$tuple_index = shr_value; |
| result |
| }) |
| ); |
| )* |
| Box::new(iter) |
| } |
| } |
| }; |
| } |
| |
| macro_rules! impl_arb_for_tuples { |
| (@internal [$($acc:tt,)*]) => { }; |
| (@internal [$($acc:tt,)*] ($type_param:ident, $tuple_index:tt), $($rest:tt,)*) => { |
| impl_arb_for_single_tuple!($($acc,)* ($type_param, $tuple_index),); |
| impl_arb_for_tuples!(@internal [$($acc,)* ($type_param, $tuple_index),] $($rest,)*); |
| }; |
| ($(($type_param:ident, $tuple_index:tt),)*) => { |
| impl_arb_for_tuples!(@internal [] $(($type_param, $tuple_index),)*); |
| }; |
| } |
| |
| impl_arb_for_tuples! { |
| (A, 0), |
| (B, 1), |
| (C, 2), |
| (D, 3), |
| (E, 4), |
| (F, 5), |
| (G, 6), |
| (H, 7), |
| } |
| |
| impl<A: Arbitrary> Arbitrary for Vec<A> { |
| fn arbitrary(g: &mut Gen) -> Vec<A> { |
| let size = { |
| let s = g.size(); |
| g.gen_range(0..s) |
| }; |
| (0..size).map(|_| A::arbitrary(g)).collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Vec<A>>> { |
| VecShrinker::new(self.clone()) |
| } |
| } |
| |
| ///Iterator which returns successive attempts to shrink the vector `seed` |
| struct VecShrinker<A> { |
| seed: Vec<A>, |
| /// How much which is removed when trying with smaller vectors |
| size: usize, |
| /// The end of the removed elements |
| offset: usize, |
| /// The shrinker for the element at `offset` once shrinking of individual |
| /// elements are attempted |
| element_shrinker: Box<dyn Iterator<Item = A>>, |
| } |
| |
| impl<A: Arbitrary> VecShrinker<A> { |
| fn new(seed: Vec<A>) -> Box<dyn Iterator<Item = Vec<A>>> { |
| let es = match seed.get(0) { |
| Some(e) => e.shrink(), |
| None => return empty_shrinker(), |
| }; |
| let size = seed.len(); |
| Box::new(VecShrinker { |
| seed: seed, |
| size: size, |
| offset: size, |
| element_shrinker: es, |
| }) |
| } |
| |
| /// Returns the next shrunk element if any, `offset` points to the index |
| /// after the returned element after the function returns |
| fn next_element(&mut self) -> Option<A> { |
| loop { |
| match self.element_shrinker.next() { |
| Some(e) => return Some(e), |
| None => match self.seed.get(self.offset) { |
| Some(e) => { |
| self.element_shrinker = e.shrink(); |
| self.offset += 1; |
| } |
| None => return None, |
| }, |
| } |
| } |
| } |
| } |
| |
| impl<A> Iterator for VecShrinker<A> |
| where |
| A: Arbitrary, |
| { |
| type Item = Vec<A>; |
| fn next(&mut self) -> Option<Vec<A>> { |
| // Try with an empty vector first |
| if self.size == self.seed.len() { |
| self.size /= 2; |
| self.offset = self.size; |
| return Some(vec![]); |
| } |
| if self.size != 0 { |
| // Generate a smaller vector by removing the elements between |
| // (offset - size) and offset |
| let xs1 = self.seed[..(self.offset - self.size)] |
| .iter() |
| .chain(&self.seed[self.offset..]) |
| .cloned() |
| .collect(); |
| self.offset += self.size; |
| // Try to reduce the amount removed from the vector once all |
| // previous sizes tried |
| if self.offset > self.seed.len() { |
| self.size /= 2; |
| self.offset = self.size; |
| } |
| Some(xs1) |
| } else { |
| // A smaller vector did not work so try to shrink each element of |
| // the vector instead Reuse `offset` as the index determining which |
| // element to shrink |
| |
| // The first element shrinker is already created so skip the first |
| // offset (self.offset == 0 only on first entry to this part of the |
| // iterator) |
| if self.offset == 0 { |
| self.offset = 1 |
| } |
| |
| match self.next_element() { |
| Some(e) => Some( |
| self.seed[..self.offset - 1] |
| .iter() |
| .cloned() |
| .chain(Some(e).into_iter()) |
| .chain(self.seed[self.offset..].iter().cloned()) |
| .collect(), |
| ), |
| None => None, |
| } |
| } |
| } |
| } |
| |
| impl<K: Arbitrary + Ord, V: Arbitrary> Arbitrary for BTreeMap<K, V> { |
| fn arbitrary(g: &mut Gen) -> BTreeMap<K, V> { |
| let vec: Vec<(K, V)> = Arbitrary::arbitrary(g); |
| vec.into_iter().collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = BTreeMap<K, V>>> { |
| let vec: Vec<(K, V)> = self.clone().into_iter().collect(); |
| Box::new( |
| vec.shrink().map(|v| v.into_iter().collect::<BTreeMap<K, V>>()), |
| ) |
| } |
| } |
| |
| impl< |
| K: Arbitrary + Eq + Hash, |
| V: Arbitrary, |
| S: BuildHasher + Default + Clone + 'static, |
| > Arbitrary for HashMap<K, V, S> |
| { |
| fn arbitrary(g: &mut Gen) -> Self { |
| let vec: Vec<(K, V)> = Arbitrary::arbitrary(g); |
| vec.into_iter().collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { |
| let vec: Vec<(K, V)> = self.clone().into_iter().collect(); |
| Box::new(vec.shrink().map(|v| v.into_iter().collect::<Self>())) |
| } |
| } |
| |
| impl<T: Arbitrary + Ord> Arbitrary for BTreeSet<T> { |
| fn arbitrary(g: &mut Gen) -> BTreeSet<T> { |
| let vec: Vec<T> = Arbitrary::arbitrary(g); |
| vec.into_iter().collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = BTreeSet<T>>> { |
| let vec: Vec<T> = self.clone().into_iter().collect(); |
| Box::new(vec.shrink().map(|v| v.into_iter().collect::<BTreeSet<T>>())) |
| } |
| } |
| |
| impl<T: Arbitrary + Ord> Arbitrary for BinaryHeap<T> { |
| fn arbitrary(g: &mut Gen) -> BinaryHeap<T> { |
| let vec: Vec<T> = Arbitrary::arbitrary(g); |
| vec.into_iter().collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = BinaryHeap<T>>> { |
| let vec: Vec<T> = self.clone().into_iter().collect(); |
| Box::new( |
| vec.shrink().map(|v| v.into_iter().collect::<BinaryHeap<T>>()), |
| ) |
| } |
| } |
| |
| impl<T: Arbitrary + Eq + Hash, S: BuildHasher + Default + Clone + 'static> |
| Arbitrary for HashSet<T, S> |
| { |
| fn arbitrary(g: &mut Gen) -> Self { |
| let vec: Vec<T> = Arbitrary::arbitrary(g); |
| vec.into_iter().collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { |
| let vec: Vec<T> = self.clone().into_iter().collect(); |
| Box::new(vec.shrink().map(|v| v.into_iter().collect::<Self>())) |
| } |
| } |
| |
| impl<T: Arbitrary> Arbitrary for LinkedList<T> { |
| fn arbitrary(g: &mut Gen) -> LinkedList<T> { |
| let vec: Vec<T> = Arbitrary::arbitrary(g); |
| vec.into_iter().collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = LinkedList<T>>> { |
| let vec: Vec<T> = self.clone().into_iter().collect(); |
| Box::new( |
| vec.shrink().map(|v| v.into_iter().collect::<LinkedList<T>>()), |
| ) |
| } |
| } |
| |
| impl<T: Arbitrary> Arbitrary for VecDeque<T> { |
| fn arbitrary(g: &mut Gen) -> VecDeque<T> { |
| let vec: Vec<T> = Arbitrary::arbitrary(g); |
| vec.into_iter().collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = VecDeque<T>>> { |
| let vec: Vec<T> = self.clone().into_iter().collect(); |
| Box::new(vec.shrink().map(|v| v.into_iter().collect::<VecDeque<T>>())) |
| } |
| } |
| |
| impl Arbitrary for IpAddr { |
| fn arbitrary(g: &mut Gen) -> IpAddr { |
| let ipv4: bool = g.gen(); |
| if ipv4 { |
| IpAddr::V4(Arbitrary::arbitrary(g)) |
| } else { |
| IpAddr::V6(Arbitrary::arbitrary(g)) |
| } |
| } |
| } |
| |
| impl Arbitrary for Ipv4Addr { |
| fn arbitrary(g: &mut Gen) -> Ipv4Addr { |
| Ipv4Addr::new(g.gen(), g.gen(), g.gen(), g.gen()) |
| } |
| } |
| |
| impl Arbitrary for Ipv6Addr { |
| fn arbitrary(g: &mut Gen) -> Ipv6Addr { |
| Ipv6Addr::new( |
| g.gen(), |
| g.gen(), |
| g.gen(), |
| g.gen(), |
| g.gen(), |
| g.gen(), |
| g.gen(), |
| g.gen(), |
| ) |
| } |
| } |
| |
| impl Arbitrary for SocketAddr { |
| fn arbitrary(g: &mut Gen) -> SocketAddr { |
| SocketAddr::new(Arbitrary::arbitrary(g), g.gen()) |
| } |
| } |
| |
| impl Arbitrary for SocketAddrV4 { |
| fn arbitrary(g: &mut Gen) -> SocketAddrV4 { |
| SocketAddrV4::new(Arbitrary::arbitrary(g), g.gen()) |
| } |
| } |
| |
| impl Arbitrary for SocketAddrV6 { |
| fn arbitrary(g: &mut Gen) -> SocketAddrV6 { |
| SocketAddrV6::new(Arbitrary::arbitrary(g), g.gen(), g.gen(), g.gen()) |
| } |
| } |
| |
| impl Arbitrary for PathBuf { |
| fn arbitrary(g: &mut Gen) -> PathBuf { |
| // use some real directories as guesses, so we may end up with |
| // actual working directories in case that is relevant. |
| let here = |
| env::current_dir().unwrap_or(PathBuf::from("/test/directory")); |
| let temp = env::temp_dir(); |
| #[allow(deprecated)] |
| let home = env::home_dir().unwrap_or(PathBuf::from("/home/user")); |
| let mut p = g |
| .choose(&[ |
| here, |
| temp, |
| home, |
| PathBuf::from("."), |
| PathBuf::from(".."), |
| PathBuf::from("../../.."), |
| PathBuf::new(), |
| ]) |
| .unwrap() |
| .to_owned(); |
| p.extend(Vec::<OsString>::arbitrary(g).iter()); |
| p |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = PathBuf>> { |
| let mut shrunk = vec![]; |
| let mut popped = self.clone(); |
| if popped.pop() { |
| shrunk.push(popped); |
| } |
| |
| // Iterating over a Path performs a small amount of normalization. |
| let normalized = self.iter().collect::<PathBuf>(); |
| if normalized.as_os_str() != self.as_os_str() { |
| shrunk.push(normalized); |
| } |
| |
| // Add the canonicalized variant only if canonicalizing the path |
| // actually does something, making it (hopefully) smaller. Also, ignore |
| // canonicalization if canonicalization errors. |
| if let Ok(canonicalized) = self.canonicalize() { |
| if canonicalized.as_os_str() != self.as_os_str() { |
| shrunk.push(canonicalized); |
| } |
| } |
| |
| Box::new(shrunk.into_iter()) |
| } |
| } |
| |
| impl Arbitrary for OsString { |
| fn arbitrary(g: &mut Gen) -> OsString { |
| OsString::from(String::arbitrary(g)) |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = OsString>> { |
| let mystring: String = self.clone().into_string().unwrap(); |
| Box::new(mystring.shrink().map(|s| OsString::from(s))) |
| } |
| } |
| |
| impl Arbitrary for String { |
| fn arbitrary(g: &mut Gen) -> String { |
| let size = { |
| let s = g.size(); |
| g.gen_range(0..s) |
| }; |
| (0..size).map(|_| char::arbitrary(g)).collect() |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = String>> { |
| // Shrink a string by shrinking a vector of its characters. |
| let chars: Vec<char> = self.chars().collect(); |
| Box::new(chars.shrink().map(|x| x.into_iter().collect::<String>())) |
| } |
| } |
| |
| impl Arbitrary for CString { |
| fn arbitrary(g: &mut Gen) -> Self { |
| let size = { |
| let s = g.size(); |
| g.gen_range(0..s) |
| }; |
| // Use either random bytes or random UTF-8 encoded codepoints. |
| let utf8: bool = g.gen(); |
| if utf8 { |
| CString::new( |
| (0..) |
| .map(|_| char::arbitrary(g)) |
| .filter(|&c| c != '\0') |
| .take(size) |
| .collect::<String>(), |
| ) |
| } else { |
| CString::new( |
| (0..) |
| .map(|_| u8::arbitrary(g)) |
| .filter(|&c| c != b'\0') |
| .take(size) |
| .collect::<Vec<u8>>(), |
| ) |
| } |
| .expect("null characters should have been filtered out") |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = CString>> { |
| // Use the implementation for a vec here, but make sure null characters |
| // are filtered out. |
| Box::new(VecShrinker::new(self.as_bytes().to_vec()).map(|bytes| { |
| CString::new( |
| bytes.into_iter().filter(|&c| c != 0).collect::<Vec<u8>>(), |
| ) |
| .expect("null characters should have been filtered out") |
| })) |
| } |
| } |
| |
| impl Arbitrary for char { |
| fn arbitrary(g: &mut Gen) -> char { |
| let mode = g.gen_range(0..100); |
| match mode { |
| 0..=49 => { |
| // ASCII + some control characters |
| g.gen_range(0..0xB0) as u8 as char |
| } |
| 50..=59 => { |
| // Unicode BMP characters |
| loop { |
| if let Some(x) = char::from_u32(g.gen_range(0..0x10000)) { |
| return x; |
| } |
| // ignore surrogate pairs |
| } |
| } |
| 60..=84 => { |
| // Characters often used in programming languages |
| g.choose(&[ |
| ' ', ' ', ' ', '\t', '\n', '~', '`', '!', '@', '#', '$', |
| '%', '^', '&', '*', '(', ')', '_', '-', '=', '+', '[', |
| ']', '{', '}', ':', ';', '\'', '"', '\\', '|', ',', '<', |
| '>', '.', '/', '?', '0', '1', '2', '3', '4', '5', '6', |
| '7', '8', '9', |
| ]) |
| .unwrap() |
| .to_owned() |
| } |
| 85..=89 => { |
| // Tricky Unicode, part 1 |
| g.choose(&[ |
| '\u{0149}', // a deprecated character |
| '\u{fff0}', // some of "Other, format" category: |
| '\u{fff1}', |
| '\u{fff2}', |
| '\u{fff3}', |
| '\u{fff4}', |
| '\u{fff5}', |
| '\u{fff6}', |
| '\u{fff7}', |
| '\u{fff8}', |
| '\u{fff9}', |
| '\u{fffA}', |
| '\u{fffB}', |
| '\u{fffC}', |
| '\u{fffD}', |
| '\u{fffE}', |
| '\u{fffF}', |
| '\u{0600}', |
| '\u{0601}', |
| '\u{0602}', |
| '\u{0603}', |
| '\u{0604}', |
| '\u{0605}', |
| '\u{061C}', |
| '\u{06DD}', |
| '\u{070F}', |
| '\u{180E}', |
| '\u{110BD}', |
| '\u{1D173}', |
| '\u{e0001}', // tag |
| '\u{e0020}', // tag space |
| '\u{e000}', |
| '\u{e001}', |
| '\u{ef8ff}', // private use |
| '\u{f0000}', |
| '\u{ffffd}', |
| '\u{ffffe}', |
| '\u{fffff}', |
| '\u{100000}', |
| '\u{10FFFD}', |
| '\u{10FFFE}', |
| '\u{10FFFF}', |
| // "Other, surrogate" characters are so that very special |
| // that they are not even allowed in safe Rust, |
| //so omitted here |
| '\u{3000}', // ideographic space |
| '\u{1680}', |
| // other space characters are already covered by two next |
| // branches |
| ]) |
| .unwrap() |
| .to_owned() |
| } |
| 90..=94 => { |
| // Tricky unicode, part 2 |
| char::from_u32(g.gen_range(0x2000..0x2070)).unwrap() |
| } |
| 95..=99 => { |
| // Completely arbitrary characters |
| g.gen() |
| } |
| _ => unreachable!(), |
| } |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = char>> { |
| Box::new((*self as u32).shrink().filter_map(char::from_u32)) |
| } |
| } |
| |
| macro_rules! unsigned_shrinker { |
| ($ty:ty) => { |
| mod shrinker { |
| pub struct UnsignedShrinker { |
| x: $ty, |
| i: $ty, |
| } |
| |
| impl UnsignedShrinker { |
| pub fn new(x: $ty) -> Box<dyn Iterator<Item = $ty>> { |
| if x == 0 { |
| super::empty_shrinker() |
| } else { |
| Box::new( |
| vec![0] |
| .into_iter() |
| .chain(UnsignedShrinker { x: x, i: x / 2 }), |
| ) |
| } |
| } |
| } |
| |
| impl Iterator for UnsignedShrinker { |
| type Item = $ty; |
| fn next(&mut self) -> Option<$ty> { |
| if self.x - self.i < self.x { |
| let result = Some(self.x - self.i); |
| self.i = self.i / 2; |
| result |
| } else { |
| None |
| } |
| } |
| } |
| } |
| }; |
| } |
| |
| macro_rules! unsigned_problem_values { |
| ($t:ty) => { |
| &[<$t>::min_value(), 1, <$t>::max_value()] |
| }; |
| } |
| |
| macro_rules! unsigned_arbitrary { |
| ($($ty:tt),*) => { |
| $( |
| impl Arbitrary for $ty { |
| fn arbitrary(g: &mut Gen) -> $ty { |
| match g.gen_range(0..10) { |
| 0 => { |
| *g.choose(unsigned_problem_values!($ty)).unwrap() |
| }, |
| _ => g.gen() |
| } |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item=$ty>> { |
| unsigned_shrinker!($ty); |
| shrinker::UnsignedShrinker::new(*self) |
| } |
| } |
| )* |
| } |
| } |
| |
| unsigned_arbitrary! { |
| usize, u8, u16, u32, u64, u128 |
| } |
| |
| macro_rules! signed_shrinker { |
| ($ty:ty) => { |
| mod shrinker { |
| pub struct SignedShrinker { |
| x: $ty, |
| i: $ty, |
| } |
| |
| impl SignedShrinker { |
| pub fn new(x: $ty) -> Box<dyn Iterator<Item = $ty>> { |
| if x == 0 { |
| super::empty_shrinker() |
| } else { |
| let shrinker = SignedShrinker { x: x, i: x / 2 }; |
| let mut items = vec![0]; |
| if shrinker.i < 0 && shrinker.x != <$ty>::MIN { |
| items.push(shrinker.x.abs()); |
| } |
| Box::new(items.into_iter().chain(shrinker)) |
| } |
| } |
| } |
| |
| impl Iterator for SignedShrinker { |
| type Item = $ty; |
| fn next(&mut self) -> Option<$ty> { |
| if self.x == <$ty>::MIN |
| || (self.x - self.i).abs() < self.x.abs() |
| { |
| let result = Some(self.x - self.i); |
| self.i = self.i / 2; |
| result |
| } else { |
| None |
| } |
| } |
| } |
| } |
| }; |
| } |
| |
| macro_rules! signed_problem_values { |
| ($t:ty) => { |
| &[<$t>::min_value(), 0, <$t>::max_value()] |
| }; |
| } |
| |
| macro_rules! signed_arbitrary { |
| ($($ty:tt),*) => { |
| $( |
| impl Arbitrary for $ty { |
| fn arbitrary(g: &mut Gen) -> $ty { |
| match g.gen_range(0..10) { |
| 0 => { |
| *g.choose(signed_problem_values!($ty)).unwrap() |
| }, |
| _ => g.gen() |
| } |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item=$ty>> { |
| signed_shrinker!($ty); |
| shrinker::SignedShrinker::new(*self) |
| } |
| } |
| )* |
| } |
| } |
| |
| signed_arbitrary! { |
| isize, i8, i16, i32, i64, i128 |
| } |
| |
| macro_rules! float_problem_values { |
| ($path:path) => {{ |
| // hack. see: https://github.com/rust-lang/rust/issues/48067 |
| use $path as p; |
| &[p::NAN, p::NEG_INFINITY, p::MIN, -0., 0., p::MAX, p::INFINITY] |
| }}; |
| } |
| |
| macro_rules! float_arbitrary { |
| ($($t:ty, $path:path, $shrinkable:ty),+) => {$( |
| impl Arbitrary for $t { |
| fn arbitrary(g: &mut Gen) -> $t { |
| match g.gen_range(0..10) { |
| 0 => *g.choose(float_problem_values!($path)).unwrap(), |
| _ => { |
| use $path as p; |
| let exp = g.gen_range((0.)..p::MAX_EXP as i16 as $t); |
| let mantissa = g.gen_range((1.)..2.); |
| let sign = *g.choose(&[-1., 1.]).unwrap(); |
| sign * mantissa * exp.exp2() |
| } |
| } |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item = $t>> { |
| signed_shrinker!($shrinkable); |
| let it = shrinker::SignedShrinker::new(*self as $shrinkable); |
| Box::new(it.map(|x| x as $t)) |
| } |
| } |
| )*}; |
| } |
| |
| float_arbitrary!(f32, std::f32, i32, f64, std::f64, i64); |
| |
| macro_rules! unsigned_non_zero_shrinker { |
| ($ty:tt) => { |
| mod shrinker { |
| pub struct UnsignedNonZeroShrinker { |
| x: $ty, |
| i: $ty, |
| } |
| |
| impl UnsignedNonZeroShrinker { |
| pub fn new(x: $ty) -> Box<dyn Iterator<Item = $ty>> { |
| debug_assert!(x > 0); |
| |
| if x == 1 { |
| super::empty_shrinker() |
| } else { |
| Box::new( |
| std::iter::once(1).chain( |
| UnsignedNonZeroShrinker { x: x, i: x / 2 }, |
| ), |
| ) |
| } |
| } |
| } |
| |
| impl Iterator for UnsignedNonZeroShrinker { |
| type Item = $ty; |
| |
| fn next(&mut self) -> Option<$ty> { |
| if self.x - self.i < self.x { |
| let result = Some(self.x - self.i); |
| self.i = self.i / 2; |
| result |
| } else { |
| None |
| } |
| } |
| } |
| } |
| }; |
| } |
| |
| macro_rules! unsigned_non_zero_arbitrary { |
| ($($ty:tt => $inner:tt),*) => { |
| $( |
| impl Arbitrary for $ty { |
| fn arbitrary(g: &mut Gen) -> $ty { |
| let mut v: $inner = g.gen(); |
| if v == 0 { |
| v += 1; |
| } |
| $ty::new(v).expect("non-zero value contsturction failed") |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = $ty>> { |
| unsigned_non_zero_shrinker!($inner); |
| Box::new(shrinker::UnsignedNonZeroShrinker::new(self.get()) |
| .map($ty::new) |
| .map(Option::unwrap)) |
| } |
| } |
| )* |
| } |
| } |
| |
| unsigned_non_zero_arbitrary! { |
| NonZeroUsize => usize, |
| NonZeroU8 => u8, |
| NonZeroU16 => u16, |
| NonZeroU32 => u32, |
| NonZeroU64 => u64, |
| NonZeroU128 => u128 |
| } |
| |
| impl<T: Arbitrary> Arbitrary for Wrapping<T> { |
| fn arbitrary(g: &mut Gen) -> Wrapping<T> { |
| Wrapping(T::arbitrary(g)) |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item = Wrapping<T>>> { |
| Box::new(self.0.shrink().map(|inner| Wrapping(inner))) |
| } |
| } |
| |
| impl<T: Arbitrary> Arbitrary for Bound<T> { |
| fn arbitrary(g: &mut Gen) -> Bound<T> { |
| match g.gen_range(0..3) { |
| 0 => Bound::Included(T::arbitrary(g)), |
| 1 => Bound::Excluded(T::arbitrary(g)), |
| _ => Bound::Unbounded, |
| } |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item = Bound<T>>> { |
| match *self { |
| Bound::Included(ref x) => { |
| Box::new(x.shrink().map(Bound::Included)) |
| } |
| Bound::Excluded(ref x) => { |
| Box::new(x.shrink().map(Bound::Excluded)) |
| } |
| Bound::Unbounded => empty_shrinker(), |
| } |
| } |
| } |
| |
| impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for Range<T> { |
| fn arbitrary(g: &mut Gen) -> Range<T> { |
| Arbitrary::arbitrary(g)..Arbitrary::arbitrary(g) |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item = Range<T>>> { |
| Box::new( |
| (self.start.clone(), self.end.clone()).shrink().map(|(s, e)| s..e), |
| ) |
| } |
| } |
| |
| impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for RangeInclusive<T> { |
| fn arbitrary(g: &mut Gen) -> RangeInclusive<T> { |
| Arbitrary::arbitrary(g)..=Arbitrary::arbitrary(g) |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item = RangeInclusive<T>>> { |
| Box::new( |
| (self.start().clone(), self.end().clone()) |
| .shrink() |
| .map(|(s, e)| s..=e), |
| ) |
| } |
| } |
| |
| impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for RangeFrom<T> { |
| fn arbitrary(g: &mut Gen) -> RangeFrom<T> { |
| Arbitrary::arbitrary(g).. |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item = RangeFrom<T>>> { |
| Box::new(self.start.clone().shrink().map(|start| start..)) |
| } |
| } |
| |
| impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for RangeTo<T> { |
| fn arbitrary(g: &mut Gen) -> RangeTo<T> { |
| ..Arbitrary::arbitrary(g) |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item = RangeTo<T>>> { |
| Box::new(self.end.clone().shrink().map(|end| ..end)) |
| } |
| } |
| |
| impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for RangeToInclusive<T> { |
| fn arbitrary(g: &mut Gen) -> RangeToInclusive<T> { |
| ..=Arbitrary::arbitrary(g) |
| } |
| fn shrink(&self) -> Box<dyn Iterator<Item = RangeToInclusive<T>>> { |
| Box::new(self.end.clone().shrink().map(|end| ..=end)) |
| } |
| } |
| |
| impl Arbitrary for RangeFull { |
| fn arbitrary(_: &mut Gen) -> RangeFull { |
| .. |
| } |
| } |
| |
| impl Arbitrary for Duration { |
| fn arbitrary(gen: &mut Gen) -> Self { |
| let seconds = gen.gen_range(0..gen.size() as u64); |
| let nanoseconds = gen.gen_range(0..1_000_000); |
| Duration::new(seconds, nanoseconds) |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { |
| Box::new( |
| (self.as_secs(), self.subsec_nanos()) |
| .shrink() |
| .map(|(secs, nanos)| Duration::new(secs, nanos % 1_000_000)), |
| ) |
| } |
| } |
| |
| impl<A: Arbitrary> Arbitrary for Box<A> { |
| fn arbitrary(g: &mut Gen) -> Box<A> { |
| Box::new(A::arbitrary(g)) |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Box<A>>> { |
| Box::new((**self).shrink().map(Box::new)) |
| } |
| } |
| |
| impl<A: Arbitrary + Sync> Arbitrary for Arc<A> { |
| fn arbitrary(g: &mut Gen) -> Arc<A> { |
| Arc::new(A::arbitrary(g)) |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Arc<A>>> { |
| Box::new((**self).shrink().map(Arc::new)) |
| } |
| } |
| |
| impl Arbitrary for SystemTime { |
| fn arbitrary(gen: &mut Gen) -> Self { |
| let after_epoch = bool::arbitrary(gen); |
| let duration = Duration::arbitrary(gen); |
| if after_epoch { |
| UNIX_EPOCH + duration |
| } else { |
| UNIX_EPOCH - duration |
| } |
| } |
| |
| fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { |
| let duration = match self.duration_since(UNIX_EPOCH) { |
| Ok(duration) => duration, |
| Err(e) => e.duration(), |
| }; |
| Box::new( |
| duration |
| .shrink() |
| .flat_map(|d| vec![UNIX_EPOCH + d, UNIX_EPOCH - d]), |
| ) |
| } |
| } |
| |
| #[cfg(test)] |
| mod test { |
| use std::collections::{ |
| BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque, |
| }; |
| use std::fmt::Debug; |
| use std::hash::Hash; |
| use std::num::Wrapping; |
| use std::path::PathBuf; |
| |
| use super::{Arbitrary, Gen}; |
| |
| #[test] |
| fn arby_unit() { |
| assert_eq!(arby::<()>(), ()); |
| } |
| |
| macro_rules! arby_int { |
| ( $signed:expr, $($t:ty),+) => {$( |
| let mut arbys = (0..1_000_000).map(|_| arby::<$t>()); |
| let mut problems = if $signed { |
| signed_problem_values!($t).iter() |
| } else { |
| unsigned_problem_values!($t).iter() |
| }; |
| assert!(problems.all(|p| arbys.any(|arby| arby == *p)), |
| "Arbitrary does not generate all problematic values"); |
| let max = <$t>::max_value(); |
| let mid = (max + <$t>::min_value()) / 2; |
| // split full range of $t into chunks |
| // Arbitrary must return some value in each chunk |
| let double_chunks: $t = 9; |
| let chunks = double_chunks * 2; // chunks must be even |
| let lim: Box<dyn Iterator<Item=$t>> = if $signed { |
| Box::new((0..=chunks) |
| .map(|idx| idx - chunks / 2) |
| .map(|x| mid + max / (chunks / 2) * x)) |
| } else { |
| Box::new((0..=chunks).map(|idx| max / chunks * idx)) |
| }; |
| let mut lim = lim.peekable(); |
| while let (Some(low), Some(&high)) = (lim.next(), lim.peek()) { |
| assert!(arbys.any(|arby| low <= arby && arby <= high), |
| "Arbitrary doesn't generate numbers in {}..={}", low, high) |
| } |
| )*}; |
| } |
| |
| #[test] |
| fn arby_int() { |
| arby_int!(true, i8, i16, i32, i64, isize, i128); |
| } |
| |
| #[test] |
| fn arby_uint() { |
| arby_int!(false, u8, u16, u32, u64, usize, u128); |
| } |
| |
| macro_rules! arby_float { |
| ($($t:ty, $path:path),+) => {$({ |
| use $path as p; |
| let mut arbys = (0..1_000_000).map(|_| arby::<$t>()); |
| //NaN != NaN |
| assert!(arbys.any(|f| f.is_nan()), |
| "Arbitrary does not generate the problematic value NaN" |
| ); |
| for p in float_problem_values!($path).iter().filter(|f| !f.is_nan()) { |
| assert!(arbys.any(|arby| arby == *p), |
| "Arbitrary does not generate the problematic value {}", |
| p |
| ); |
| } |
| // split full range of $t into chunks |
| // Arbitrary must return some value in each chunk |
| let double_chunks: i8 = 9; |
| let chunks = double_chunks * 2; // chunks must be even |
| let lim = (-double_chunks..=double_chunks) |
| .map(|idx| <$t>::from(idx)) |
| .map(|idx| p::MAX/(<$t>::from(chunks/2)) * idx); |
| let mut lim = lim.peekable(); |
| while let (Some(low), Some(&high)) = (lim.next(), lim.peek()) { |
| assert!( |
| arbys.any(|arby| low <= arby && arby <= high), |
| "Arbitrary doesn't generate numbers in {:e}..={:e}", |
| low, |
| high, |
| ) |
| } |
| })*}; |
| } |
| |
| #[test] |
| fn arby_float() { |
| arby_float!(f32, std::f32, f64, std::f64); |
| } |
| |
| fn arby<A: Arbitrary>() -> A { |
| Arbitrary::arbitrary(&mut Gen::new(5)) |
| } |
| |
| // Shrink testing. |
| #[test] |
| fn unit() { |
| eq((), vec![]); |
| } |
| |
| #[test] |
| fn bools() { |
| eq(false, vec![]); |
| eq(true, vec![false]); |
| } |
| |
| #[test] |
| fn options() { |
| eq(None::<()>, vec![]); |
| eq(Some(false), vec![None]); |
| eq(Some(true), vec![None, Some(false)]); |
| } |
| |
| #[test] |
| fn results() { |
| // Result<A, B> doesn't implement the Hash trait, so these tests |
| // depends on the order of shrunk results. Ug. |
| // TODO: Fix this. |
| ordered_eq(Ok::<bool, ()>(true), vec![Ok(false)]); |
| ordered_eq(Err::<(), bool>(true), vec![Err(false)]); |
| } |
| |
| #[test] |
| fn tuples() { |
| eq((false, false), vec![]); |
| eq((true, false), vec![(false, false)]); |
| eq((true, true), vec![(false, true), (true, false)]); |
| } |
| |
| #[test] |
| fn triples() { |
| eq((false, false, false), vec![]); |
| eq((true, false, false), vec![(false, false, false)]); |
| eq( |
| (true, true, false), |
| vec![(false, true, false), (true, false, false)], |
| ); |
| } |
| |
| #[test] |
| fn quads() { |
| eq((false, false, false, false), vec![]); |
| eq((true, false, false, false), vec![(false, false, false, false)]); |
| eq( |
| (true, true, false, false), |
| vec![(false, true, false, false), (true, false, false, false)], |
| ); |
| } |
| |
| #[test] |
| fn ints() { |
| // TODO: Test overflow? |
| eq(5isize, vec![0, 3, 4]); |
| eq(-5isize, vec![5, 0, -3, -4]); |
| eq(0isize, vec![]); |
| } |
| |
| #[test] |
| fn ints8() { |
| eq(5i8, vec![0, 3, 4]); |
| eq(-5i8, vec![5, 0, -3, -4]); |
| eq(0i8, vec![]); |
| } |
| |
| #[test] |
| fn ints16() { |
| eq(5i16, vec![0, 3, 4]); |
| eq(-5i16, vec![5, 0, -3, -4]); |
| eq(0i16, vec![]); |
| } |
| |
| #[test] |
| fn ints32() { |
| eq(5i32, vec![0, 3, 4]); |
| eq(-5i32, vec![5, 0, -3, -4]); |
| eq(0i32, vec![]); |
| } |
| |
| #[test] |
| fn ints64() { |
| eq(5i64, vec![0, 3, 4]); |
| eq(-5i64, vec![5, 0, -3, -4]); |
| eq(0i64, vec![]); |
| } |
| |
| #[test] |
| fn ints128() { |
| eq(5i128, vec![0, 3, 4]); |
| eq(-5i128, vec![5, 0, -3, -4]); |
| eq(0i128, vec![]); |
| } |
| |
| #[test] |
| fn uints() { |
| eq(5usize, vec![0, 3, 4]); |
| eq(0usize, vec![]); |
| } |
| |
| #[test] |
| fn uints8() { |
| eq(5u8, vec![0, 3, 4]); |
| eq(0u8, vec![]); |
| } |
| |
| #[test] |
| fn uints16() { |
| eq(5u16, vec![0, 3, 4]); |
| eq(0u16, vec![]); |
| } |
| |
| #[test] |
| fn uints32() { |
| eq(5u32, vec![0, 3, 4]); |
| eq(0u32, vec![]); |
| } |
| |
| #[test] |
| fn uints64() { |
| eq(5u64, vec![0, 3, 4]); |
| eq(0u64, vec![]); |
| } |
| |
| #[test] |
| fn uints128() { |
| eq(5u128, vec![0, 3, 4]); |
| eq(0u128, vec![]); |
| } |
| |
| macro_rules! define_float_eq { |
| ($ty:ty) => { |
| fn eq(s: $ty, v: Vec<$ty>) { |
| let shrunk: Vec<$ty> = s.shrink().collect(); |
| for n in v { |
| let found = shrunk.iter().any(|&i| i == n); |
| if !found { |
| panic!(format!( |
| "Element {:?} was not found \ |
| in shrink results {:?}", |
| n, shrunk |
| )); |
| } |
| } |
| } |
| }; |
| } |
| |
| #[test] |
| fn floats32() { |
| define_float_eq!(f32); |
| |
| eq(0.0, vec![]); |
| eq(-0.0, vec![]); |
| eq(1.0, vec![0.0]); |
| eq(2.0, vec![0.0, 1.0]); |
| eq(-2.0, vec![0.0, 2.0, -1.0]); |
| eq(1.5, vec![0.0]); |
| } |
| |
| #[test] |
| fn floats64() { |
| define_float_eq!(f64); |
| |
| eq(0.0, vec![]); |
| eq(-0.0, vec![]); |
| eq(1.0, vec![0.0]); |
| eq(2.0, vec![0.0, 1.0]); |
| eq(-2.0, vec![0.0, 2.0, -1.0]); |
| eq(1.5, vec![0.0]); |
| } |
| |
| #[test] |
| fn wrapping_ints32() { |
| eq(Wrapping(5i32), vec![Wrapping(0), Wrapping(3), Wrapping(4)]); |
| eq( |
| Wrapping(-5i32), |
| vec![Wrapping(5), Wrapping(0), Wrapping(-3), Wrapping(-4)], |
| ); |
| eq(Wrapping(0i32), vec![]); |
| } |
| |
| #[test] |
| fn vecs() { |
| eq( |
| { |
| let it: Vec<isize> = vec![]; |
| it |
| }, |
| vec![], |
| ); |
| eq( |
| { |
| let it: Vec<Vec<isize>> = vec![vec![]]; |
| it |
| }, |
| vec![vec![]], |
| ); |
| eq(vec![1isize], vec![vec![], vec![0]]); |
| eq(vec![11isize], vec![vec![], vec![0], vec![6], vec![9], vec![10]]); |
| eq( |
| vec![3isize, 5], |
| vec![ |
| vec![], |
| vec![5], |
| vec![3], |
| vec![0, 5], |
| vec![2, 5], |
| vec![3, 0], |
| vec![3, 3], |
| vec![3, 4], |
| ], |
| ); |
| } |
| |
| macro_rules! map_tests { |
| ($name:ident, $ctor:expr) => { |
| #[test] |
| fn $name() { |
| ordered_eq($ctor, vec![]); |
| |
| { |
| let mut map = $ctor; |
| map.insert(1usize, 1isize); |
| |
| let shrinks = vec![ |
| $ctor, |
| { |
| let mut m = $ctor; |
| m.insert(0, 1); |
| m |
| }, |
| { |
| let mut m = $ctor; |
| m.insert(1, 0); |
| m |
| }, |
| ]; |
| |
| ordered_eq(map, shrinks); |
| } |
| } |
| }; |
| } |
| |
| map_tests!(btreemap, BTreeMap::<usize, isize>::new()); |
| map_tests!(hashmap, HashMap::<usize, isize>::new()); |
| |
| macro_rules! list_tests { |
| ($name:ident, $ctor:expr, $push:ident) => { |
| #[test] |
| fn $name() { |
| ordered_eq($ctor, vec![]); |
| |
| { |
| let mut list = $ctor; |
| list.$push(2usize); |
| |
| let shrinks = vec![ |
| $ctor, |
| { |
| let mut m = $ctor; |
| m.$push(0); |
| m |
| }, |
| { |
| let mut m = $ctor; |
| m.$push(1); |
| m |
| }, |
| ]; |
| |
| ordered_eq(list, shrinks); |
| } |
| } |
| }; |
| } |
| |
| list_tests!(btreesets, BTreeSet::<usize>::new(), insert); |
| list_tests!(hashsets, HashSet::<usize>::new(), insert); |
| list_tests!(linkedlists, LinkedList::<usize>::new(), push_back); |
| list_tests!(vecdeques, VecDeque::<usize>::new(), push_back); |
| |
| #[test] |
| fn binaryheaps() { |
| ordered_eq( |
| BinaryHeap::<usize>::new().into_iter().collect::<Vec<_>>(), |
| vec![], |
| ); |
| |
| { |
| let mut heap = BinaryHeap::<usize>::new(); |
| heap.push(2usize); |
| |
| let shrinks = vec![vec![], vec![0], vec![1]]; |
| |
| ordered_eq(heap.into_iter().collect::<Vec<_>>(), shrinks); |
| } |
| } |
| |
| #[test] |
| fn chars() { |
| eq('\x00', vec![]); |
| } |
| |
| // All this jazz is for testing set equality on the results of a shrinker. |
| fn eq<A: Arbitrary + Eq + Debug + Hash>(s: A, v: Vec<A>) { |
| let (left, right) = (shrunk(s), set(v)); |
| assert_eq!(left, right); |
| } |
| fn shrunk<A: Arbitrary + Eq + Hash>(s: A) -> HashSet<A> { |
| set(s.shrink()) |
| } |
| fn set<A: Hash + Eq, I: IntoIterator<Item = A>>(xs: I) -> HashSet<A> { |
| xs.into_iter().collect() |
| } |
| |
| fn ordered_eq<A: Arbitrary + Eq + Debug>(s: A, v: Vec<A>) { |
| let (left, right) = (s.shrink().collect::<Vec<A>>(), v); |
| assert_eq!(left, right); |
| } |
| |
| #[test] |
| fn bounds() { |
| use std::ops::Bound::*; |
| for i in -5..=5 { |
| ordered_eq(Included(i), i.shrink().map(Included).collect()); |
| ordered_eq(Excluded(i), i.shrink().map(Excluded).collect()); |
| } |
| eq(Unbounded::<i32>, vec![]); |
| } |
| |
| #[test] |
| fn ranges() { |
| ordered_eq(0..0, vec![]); |
| ordered_eq(1..1, vec![0..1, 1..0]); |
| ordered_eq(3..5, vec![0..5, 2..5, 3..0, 3..3, 3..4]); |
| ordered_eq(5..3, vec![0..3, 3..3, 4..3, 5..0, 5..2]); |
| ordered_eq(3.., vec![0.., 2..]); |
| ordered_eq(..3, vec![..0, ..2]); |
| ordered_eq(.., vec![]); |
| ordered_eq(3..=5, vec![0..=5, 2..=5, 3..=0, 3..=3, 3..=4]); |
| ordered_eq(..=3, vec![..=0, ..=2]); |
| } |
| |
| #[test] |
| fn pathbuf() { |
| ordered_eq( |
| PathBuf::from("/home/foo//.././bar"), |
| vec![ |
| PathBuf::from("/home/foo//.."), |
| PathBuf::from("/home/foo/../bar"), |
| ], |
| ); |
| } |
| } |
