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};
pub struct Gen {
rng: rand::rngs::SmallRng,
size: usize,
}
impl Gen {
pub fn new(size: usize) -> Gen {
Gen { rng: rand::rngs::SmallRng::from_entropy(), size: size }
}
pub fn size(&self) -> usize {
self.size
}
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)
}
}
pub fn empty_shrinker<A: 'static>() -> Box<dyn Iterator<Item = A>> {
Box::new(empty())
}
pub fn single_shrinker<A: 'static>(value: A) -> Box<dyn Iterator<Item = A>> {
Box::new(once(value))
}
pub trait Arbitrary: Clone + 'static {
fn arbitrary(g: &mut Gen) -> Self;
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())
}
}
struct VecShrinker<A> {
seed: Vec<A>,
size: usize,
offset: usize,
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,
})
}
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>> {
if self.size == self.seed.len() {
self.size /= 2;
self.offset = self.size;
return Some(vec![]);
}
if self.size != 0 {
let xs1 = self.seed[..(self.offset - self.size)]
.iter()
.chain(&self.seed[self.offset..])
.cloned()
.collect();
self.offset += self.size;
if self.offset > self.seed.len() {
self.size /= 2;
self.offset = self.size;
}
Some(xs1)
} else {
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 {
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);
}
let normalized = self.iter().collect::<PathBuf>();
if normalized.as_os_str() != self.as_os_str() {
shrunk.push(normalized);
}
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>> {
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)
};
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>> {
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 => {
g.gen_range(0..0xB0) as u8 as char
}
50..=59 => {
loop {
if let Some(x) = char::from_u32(g.gen_range(0..0x10000)) {
return x;
}
}
}
60..=84 => {
g.choose(&[
' ', ' ', ' ', '\t', '\n', '~', '`', '!', '@', '#', '$',
'%', '^', '&', '*', '(', ')', '_', '-', '=', '+', '[',
']', '{', '}', ':', ';', '\'', '"', '\\', '|', ',', '<',
'>', '.', '/', '?', '0', '1', '2', '3', '4', '5', '6',
'7', '8', '9',
])
.unwrap()
.to_owned()
}
85..=89 => {
g.choose(&[
'\u{0149}', '\u{fff0}', '\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}', '\u{e0020}', '\u{e000}',
'\u{e001}',
'\u{ef8ff}', '\u{f0000}',
'\u{ffffd}',
'\u{ffffe}',
'\u{fffff}',
'\u{100000}',
'\u{10FFFD}',
'\u{10FFFE}',
'\u{10FFFF}',
'\u{3000}', '\u{1680}',
])
.unwrap()
.to_owned()
}
90..=94 => {
char::from_u32(g.gen_range(0x2000..0x2070)).unwrap()
}
95..=99 => {
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) => {{
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;
let double_chunks: $t = 9;
let chunks = double_chunks * 2; 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>());
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
);
}
let double_chunks: i8 = 9;
let chunks = double_chunks * 2; 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))
}
#[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() {
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() {
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![]);
}
fn eq<A: Arbitrary + Eq + Debug + Hash>(s: A, v: Vec<A>) {
let (left, right) = (shrunk(s), set(v)