use crate::std_facade::{Arc, Cow, Vec};
use core::fmt;
use core::mem;
use core::ops::Range;
use core::u64;
use rand::Rng;
use crate::bits::{self, BitSetValueTree, SampledBitSetStrategy, VarBitSet};
use crate::num;
use crate::strategy::*;
use crate::test_runner::*;
pub use crate::collection::{size_range, SizeRange};
pub fn subsequence<T: Clone + 'static>(
values: impl Into<Cow<'static, [T]>>,
size: impl Into<SizeRange>,
) -> Subsequence<T> {
let values = values.into();
let len = values.len();
let size = size.into();
size.assert_nonempty();
assert!(
size.end_incl() <= len,
"Maximum size of subsequence {} exceeds length of input {}",
size.end_incl(),
len
);
Subsequence {
values: Arc::new(values),
bit_strategy: bits::varsize::sampled(size, 0..len),
}
}
#[derive(Debug, Clone)]
#[must_use = "strategies do nothing unless used"]
pub struct Subsequence<T: Clone + 'static> {
values: Arc<Cow<'static, [T]>>,
bit_strategy: SampledBitSetStrategy<VarBitSet>,
}
impl<T: fmt::Debug + Clone + 'static> Strategy for Subsequence<T> {
type Tree = SubsequenceValueTree<T>;
type Value = Vec<T>;
fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
Ok(SubsequenceValueTree {
values: Arc::clone(&self.values),
inner: self.bit_strategy.new_tree(runner)?,
})
}
}
#[derive(Debug, Clone)]
pub struct SubsequenceValueTree<T: Clone + 'static> {
values: Arc<Cow<'static, [T]>>,
inner: BitSetValueTree<VarBitSet>,
}
impl<T: fmt::Debug + Clone + 'static> ValueTree for SubsequenceValueTree<T> {
type Value = Vec<T>;
fn current(&self) -> Self::Value {
let inner = self.inner.current();
let ret = inner.iter().map(|ix| self.values[ix].clone()).collect();
ret
}
fn simplify(&mut self) -> bool {
self.inner.simplify()
}
fn complicate(&mut self) -> bool {
self.inner.complicate()
}
}
#[derive(Debug, Clone)]
struct SelectMapFn<T: Clone + 'static>(Arc<Cow<'static, [T]>>);
impl<T: fmt::Debug + Clone + 'static> statics::MapFn<usize> for SelectMapFn<T> {
type Output = T;
fn apply(&self, ix: usize) -> T {
self.0[ix].clone()
}
}
opaque_strategy_wrapper! {
#[derive(Clone, Debug)]
pub struct Select[<T>][where T : Clone + fmt::Debug + 'static](
statics::Map<Range<usize>, SelectMapFn<T>>)
-> SelectValueTree<T>;
#[derive(Clone, Debug)]
pub struct SelectValueTree[<T>][where T : Clone + fmt::Debug + 'static](
statics::Map<num::usize::BinarySearch, SelectMapFn<T>>)
-> T;
}
pub fn select<T: Clone + fmt::Debug + 'static>(
values: impl Into<Cow<'static, [T]>>,
) -> Select<T> {
let cow = values.into();
Select(statics::Map::new(0..cow.len(), SelectMapFn(Arc::new(cow))))
}
#[derive(Clone, Copy, Debug)]
pub struct Index(usize);
impl Index {
pub fn index(&self, size: usize) -> usize {
assert!(size > 0, "Attempt to use `Index` with 0-size collection");
((size as u128) * (self.0 as u128) >> (mem::size_of::<usize>() * 8))
as usize
}
pub fn get<'a, T>(&self, slice: &'a [T]) -> &'a T {
&slice[self.index(slice.len())]
}
pub fn get_mut<'a, T>(&self, slice: &'a mut [T]) -> &'a mut T {
let ix = self.index(slice.len());
&mut slice[ix]
}
}
mapfn! {
[] fn UsizeToIndex[](raw: usize) -> Index {
Index(raw)
}
}
opaque_strategy_wrapper! {
#[derive(Clone, Debug)]
pub struct IndexStrategy[][](
statics::Map<num::usize::Any, UsizeToIndex>)
-> IndexValueTree;
#[derive(Clone, Debug)]
pub struct IndexValueTree[][](
statics::Map<num::usize::BinarySearch,UsizeToIndex>)
-> Index;
}
impl IndexStrategy {
pub(crate) fn new() -> Self {
IndexStrategy(statics::Map::new(num::usize::ANY, UsizeToIndex))
}
}
#[derive(Clone, Debug)]
pub struct Selector {
rng: TestRng,
bias_increment: u64,
}
#[derive(Debug)]
pub struct SelectorStrategy {
_nonexhaustive: (),
}
#[derive(Debug)]
pub struct SelectorValueTree {
rng: TestRng,
reverse_bias_increment: num::u64::BinarySearch,
}
impl SelectorStrategy {
pub(crate) fn new() -> Self {
SelectorStrategy { _nonexhaustive: () }
}
}
impl Strategy for SelectorStrategy {
type Tree = SelectorValueTree;
type Value = Selector;
fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
Ok(SelectorValueTree {
rng: runner.new_rng(),
reverse_bias_increment: num::u64::BinarySearch::new(u64::MAX),
})
}
}
impl ValueTree for SelectorValueTree {
type Value = Selector;
fn current(&self) -> Selector {
Selector {
rng: self.rng.clone(),
bias_increment: u64::MAX - self.reverse_bias_increment.current(),
}
}
fn simplify(&mut self) -> bool {
self.reverse_bias_increment.simplify()
}
fn complicate(&mut self) -> bool {
self.reverse_bias_increment.complicate()
}
}
impl Selector {
pub fn select<T: IntoIterator>(&self, it: T) -> T::Item {
self.try_select(it).expect("select from empty iterator")
}
pub fn try_select<T: IntoIterator>(&self, it: T) -> Option<T::Item> {
let mut bias = 0u64;
let mut min_score = 0;
let mut best = None;
let mut rng = self.rng.clone();
for item in it {
let score = bias.saturating_add(rng.gen());
if best.is_none() || score < min_score {
best = Some(item);
min_score = score;
}
bias = bias.saturating_add(self.bias_increment);
}
best
}
}
#[cfg(test)]
mod test {
use crate::std_facade::BTreeSet;
use super::*;
use crate::arbitrary::any;
#[test]
fn sample_slice() {
static VALUES: &[usize] = &[0, 1, 2, 3, 4, 5, 6, 7];
let mut size_counts = [0; 8];
let mut value_counts = [0; 8];
let mut runner = TestRunner::deterministic();
let input = subsequence(VALUES, 3..7);
for _ in 0..2048 {
let value = input.new_tree(&mut runner).unwrap().current();
assert!(value.len() >= 3 && value.len() < 7);
assert_eq!(
value.len(),
value.iter().cloned().collect::<BTreeSet<_>>().len()
);
let mut sorted = value.clone();
sorted.sort();
assert_eq!(sorted, value);
size_counts[value.len()] += 1;
for value in value {
value_counts[value] += 1;
}
}
for i in 3..7 {
assert!(
size_counts[i] >= 256 && size_counts[i] < 1024,
"size {} was chosen {} times",
i,
size_counts[i]
);
}
for (ix, &v) in value_counts.iter().enumerate() {
assert!(
v >= 1024 && v < 1500,
"Value {} was chosen {} times",
ix,
v
);
}
}
#[test]
fn sample_vec() {
let values = vec![0, 1, 2, 3, 4];
let mut runner = TestRunner::deterministic();
let input = subsequence(values, 1..3);
let _ = input.new_tree(&mut runner).unwrap().current();
}
#[test]
fn test_select() {
let values = vec![0, 1, 2, 3, 4, 5, 6, 7];
let mut counts = [0; 8];
let mut runner = TestRunner::deterministic();
let input = select(values);
for _ in 0..1024 {
counts[input.new_tree(&mut runner).unwrap().current()] += 1;
}
for (ix, &count) in counts.iter().enumerate() {
assert!(
count >= 64 && count < 256,
"Generated value {} {} times",
ix,
count
);
}
}
#[test]
fn test_sample_sanity() {
check_strategy_sanity(subsequence(vec![0, 1, 2, 3, 4], 1..3), None);
}
#[test]
fn test_select_sanity() {
check_strategy_sanity(select(vec![0, 1, 2, 3, 4]), None);
}
#[test]
fn subseq_empty_vec_works() {
let mut runner = TestRunner::deterministic();
let input = subsequence(Vec::<()>::new(), 0..1);
assert_eq!(
Vec::<()>::new(),
input.new_tree(&mut runner).unwrap().current()
);
}
#[test]
fn subseq_full_vec_works() {
let v = vec![1u32, 2u32, 3u32];
let mut runner = TestRunner::deterministic();
let input = subsequence(v.clone(), 3);
assert_eq!(v, input.new_tree(&mut runner).unwrap().current());
}
#[test]
fn index_works() {
let mut runner = TestRunner::deterministic();
let input = any::<Index>();
let col = vec!["foo", "bar", "baz"];
let mut seen = BTreeSet::new();
for _ in 0..16 {
let mut tree = input.new_tree(&mut runner).unwrap();
seen.insert(*tree.current().get(&col));
while tree.simplify() {}
assert_eq!("foo", *tree.current().get(&col));
}
assert_eq!(col.into_iter().collect::<BTreeSet<_>>(), seen);
}
#[test]
fn selector_works() {
let mut runner = TestRunner::deterministic();
let input = any::<Selector>();
let col: BTreeSet<&str> =
vec!["foo", "bar", "baz"].into_iter().collect();
let mut seen = BTreeSet::new();
for _ in 0..16 {
let mut tree = input.new_tree(&mut runner).unwrap();
seen.insert(*tree.current().select(&col));
while tree.simplify() {}
assert_eq!("bar", *tree.current().select(&col));
}
assert_eq!(col, seen);
}
}