proptest/
sample.rs

1//-
2// Copyright 2017, 2018 Jason Lingle
3//
4// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. This file may not be copied, modified, or distributed
8// except according to those terms.
9
10//! Strategies for generating values by taking samples of collections.
11//!
12//! Note that the strategies in this module are not native combinators; that
13//! is, the input collection is not itself a strategy, but is rather fixed when
14//! the strategy is created.
15
16use crate::std_facade::{Arc, Cow, Vec};
17use core::fmt;
18use core::mem;
19use core::ops::Range;
20use core::u64;
21
22use rand::Rng;
23
24use crate::bits::{self, BitSetValueTree, SampledBitSetStrategy, VarBitSet};
25use crate::num;
26use crate::strategy::*;
27use crate::test_runner::*;
28
29/// Re-exported to make usage more ergonomic.
30pub use crate::collection::{size_range, SizeRange};
31
32/// Sample subsequences whose size are within `size` from the given collection
33/// `values`.
34///
35/// A subsequence is a subset of the elements in a collection in the order they
36/// occur in that collection. The elements are not chosen to be contiguous.
37///
38/// This is roughly analogous to `rand::sample`, except that it guarantees that
39/// the order is preserved.
40///
41/// `values` may be a static slice or a `Vec`.
42///
43/// ## Panics
44///
45/// Panics if the maximum size implied by `size` is larger than the size of
46/// `values`.
47///
48/// Panics if `size` is a zero-length range.
49pub fn subsequence<T: Clone + 'static>(
50    values: impl Into<Cow<'static, [T]>>,
51    size: impl Into<SizeRange>,
52) -> Subsequence<T> {
53    let values = values.into();
54    let len = values.len();
55    let size = size.into();
56
57    size.assert_nonempty();
58    assert!(
59        size.end_incl() <= len,
60        "Maximum size of subsequence {} exceeds length of input {}",
61        size.end_incl(),
62        len
63    );
64    Subsequence {
65        values: Arc::new(values),
66        bit_strategy: bits::varsize::sampled(size, 0..len),
67    }
68}
69
70/// Strategy to generate `Vec`s by sampling a subsequence from another
71/// collection.
72///
73/// This is created by the `subsequence` function in the same module.
74#[derive(Debug, Clone)]
75#[must_use = "strategies do nothing unless used"]
76pub struct Subsequence<T: Clone + 'static> {
77    values: Arc<Cow<'static, [T]>>,
78    bit_strategy: SampledBitSetStrategy<VarBitSet>,
79}
80
81impl<T: fmt::Debug + Clone + 'static> Strategy for Subsequence<T> {
82    type Tree = SubsequenceValueTree<T>;
83    type Value = Vec<T>;
84
85    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
86        Ok(SubsequenceValueTree {
87            values: Arc::clone(&self.values),
88            inner: self.bit_strategy.new_tree(runner)?,
89        })
90    }
91}
92
93/// `ValueTree` type for `Subsequence`.
94#[derive(Debug, Clone)]
95pub struct SubsequenceValueTree<T: Clone + 'static> {
96    values: Arc<Cow<'static, [T]>>,
97    inner: BitSetValueTree<VarBitSet>,
98}
99
100impl<T: fmt::Debug + Clone + 'static> ValueTree for SubsequenceValueTree<T> {
101    type Value = Vec<T>;
102
103    fn current(&self) -> Self::Value {
104        let inner = self.inner.current();
105        let ret = inner.iter().map(|ix| self.values[ix].clone()).collect();
106        ret
107    }
108
109    fn simplify(&mut self) -> bool {
110        self.inner.simplify()
111    }
112
113    fn complicate(&mut self) -> bool {
114        self.inner.complicate()
115    }
116}
117
118#[derive(Debug, Clone)]
119struct SelectMapFn<T: Clone + 'static>(Arc<Cow<'static, [T]>>);
120
121impl<T: fmt::Debug + Clone + 'static> statics::MapFn<usize> for SelectMapFn<T> {
122    type Output = T;
123
124    fn apply(&self, ix: usize) -> T {
125        self.0[ix].clone()
126    }
127}
128
129opaque_strategy_wrapper! {
130    /// Strategy to produce one value from a fixed collection of options.
131    ///
132    /// Created by the `select()` in the same module.
133    #[derive(Clone, Debug)]
134    pub struct Select[<T>][where T : Clone + fmt::Debug + 'static](
135        statics::Map<Range<usize>, SelectMapFn<T>>)
136        -> SelectValueTree<T>;
137    /// `ValueTree` corresponding to `Select`.
138    #[derive(Clone, Debug)]
139    pub struct SelectValueTree[<T>][where T : Clone + fmt::Debug + 'static](
140        statics::Map<num::usize::BinarySearch, SelectMapFn<T>>)
141        -> T;
142}
143
144/// Create a strategy which uniformly selects one value from `values`.
145///
146/// `values` should be a `&'static [T]` or a `Vec<T>`, or potentially another
147/// type that can be coerced to `Cow<'static,[T]>`.
148///
149/// This is largely equivalent to making a `Union` of a bunch of `Just`
150/// strategies, but is substantially more efficient and shrinks by binary
151/// search.
152///
153/// If `values` is also to be generated by a strategy, see
154/// [`Index`](struct.Index.html) for a more efficient way to select values than
155/// using `prop_flat_map()`.
156pub fn select<T: Clone + fmt::Debug + 'static>(
157    values: impl Into<Cow<'static, [T]>>,
158) -> Select<T> {
159    let cow = values.into();
160
161    Select(statics::Map::new(0..cow.len(), SelectMapFn(Arc::new(cow))))
162}
163
164/// A stand-in for an index into a slice or similar collection or conceptually
165/// similar things.
166///
167/// At the lowest level, `Index` is a mechanism for generating `usize` values
168/// in the range [0..N), for some N whose value is not known until it is
169/// needed. (Contrast with using `0..N` itself as a strategy, where you need to
170/// know N when you define the strategy.)
171///
172/// For any upper bound, the actual index produced by an `Index` is the same no
173/// matter how many times it is used. Different upper bounds will produce
174/// different but not independent values.
175///
176/// Shrinking will cause the index to binary search through the underlying
177/// collection(s) it is used to sample.
178///
179/// Note that `Index` _cannot_ currently be used as a slice index (e.g.,
180/// `slice[index]`) due to the trait coherence rules.
181///
182/// ## Example
183///
184/// If the collection itself being indexed is itself generated by a strategy,
185/// you can make separately define that strategy and a strategy generating one
186/// or more `Index`es and then join the two after input generation, avoiding a
187/// call to `prop_flat_map()`.
188///
189/// ```
190/// use proptest::prelude::*;
191///
192/// proptest! {
193///     # /*
194///     #[test]
195///     # */
196///     fn my_test(
197///         names in prop::collection::vec("[a-z]+", 10..20),
198///         indices in prop::collection::vec(any::<prop::sample::Index>(), 5..10)
199///     ) {
200///         // We now have Vec<String> of ten to twenty names, and a Vec<Index>
201///         // of five to ten indices and can combine them however we like.
202///         for index in &indices {
203///             println!("Accessing item by index: {}", names[index.index(names.len())]);
204///             println!("Accessing item by convenience method: {}", index.get(&names));
205///         }
206///         // Test stuff...
207///     }
208/// }
209/// #
210/// # fn main() { my_test(); }
211/// ```
212#[derive(Clone, Copy, Debug)]
213pub struct Index(usize);
214
215impl Index {
216    /// Return the real index that would be used to index a collection of size `size`.
217    ///
218    /// ## Panics
219    ///
220    /// Panics if `size == 0`.
221    pub fn index(&self, size: usize) -> usize {
222        assert!(size > 0, "Attempt to use `Index` with 0-size collection");
223
224        // No platforms currently have `usize` wider than 64 bits, so `u128` is
225        // sufficient to hold the result of a full multiply, letting us do a
226        // simple fixed-point multiply.
227        ((size as u128) * (self.0 as u128) >> (mem::size_of::<usize>() * 8))
228            as usize
229    }
230
231    /// Return a reference to the element in `slice` that this `Index` refers to.
232    ///
233    /// A shortcut for `&slice[index.index(slice.len())]`.
234    pub fn get<'a, T>(&self, slice: &'a [T]) -> &'a T {
235        &slice[self.index(slice.len())]
236    }
237
238    /// Return a mutable reference to the element in `slice` that this `Index`
239    /// refers to.
240    ///
241    /// A shortcut for `&mut slice[index.index(slice.len())]`.
242    pub fn get_mut<'a, T>(&self, slice: &'a mut [T]) -> &'a mut T {
243        let ix = self.index(slice.len());
244        &mut slice[ix]
245    }
246}
247
248mapfn! {
249    [] fn UsizeToIndex[](raw: usize) -> Index {
250        Index(raw)
251    }
252}
253
254opaque_strategy_wrapper! {
255    /// Strategy to create `Index`es.
256    ///
257    /// Created via `any::<Index>()`.
258    #[derive(Clone, Debug)]
259    pub struct IndexStrategy[][](
260        statics::Map<num::usize::Any, UsizeToIndex>)
261        -> IndexValueTree;
262    /// `ValueTree` corresponding to `IndexStrategy`.
263    #[derive(Clone, Debug)]
264    pub struct IndexValueTree[][](
265        statics::Map<num::usize::BinarySearch,UsizeToIndex>)
266        -> Index;
267}
268
269impl IndexStrategy {
270    pub(crate) fn new() -> Self {
271        IndexStrategy(statics::Map::new(num::usize::ANY, UsizeToIndex))
272    }
273}
274
275/// A value for picking random values out of iterators.
276///
277/// This is, in a sense, a more flexible variant of
278/// [`Index`](struct.Index.html) in that it can operate on arbitrary
279/// `IntoIterator` values.
280///
281/// Initially, the selection is roughly uniform, with a very slight bias
282/// towards items earlier in the iterator.
283///
284/// Shrinking causes the selection to move toward items earlier in the
285/// iterator, ultimately settling on the very first, but this currently happens
286/// in a very haphazard way that may fail to find the earliest failing input.
287///
288/// ## Example
289///
290/// Generate a non-indexable collection and a value to pick out of it.
291///
292/// ```
293/// use proptest::prelude::*;
294///
295/// proptest! {
296///     # /*
297///     #[test]
298///     # */
299///     fn my_test(
300///         names in prop::collection::hash_set("[a-z]+", 10..20),
301///         selector in any::<prop::sample::Selector>()
302///     ) {
303///         println!("Selected name: {}", selector.select(&names));
304///         // Test stuff...
305///     }
306/// }
307/// #
308/// # fn main() { my_test(); }
309/// ```
310#[derive(Clone, Debug)]
311pub struct Selector {
312    rng: TestRng,
313    bias_increment: u64,
314}
315
316/// Strategy to create `Selector`s.
317///
318/// Created via `any::<Selector>()`.
319#[derive(Debug)]
320pub struct SelectorStrategy {
321    _nonexhaustive: (),
322}
323
324/// `ValueTree` corresponding to `SelectorStrategy`.
325#[derive(Debug)]
326pub struct SelectorValueTree {
327    rng: TestRng,
328    reverse_bias_increment: num::u64::BinarySearch,
329}
330
331impl SelectorStrategy {
332    pub(crate) fn new() -> Self {
333        SelectorStrategy { _nonexhaustive: () }
334    }
335}
336
337impl Strategy for SelectorStrategy {
338    type Tree = SelectorValueTree;
339    type Value = Selector;
340
341    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
342        Ok(SelectorValueTree {
343            rng: runner.new_rng(),
344            reverse_bias_increment: num::u64::BinarySearch::new(u64::MAX),
345        })
346    }
347}
348
349impl ValueTree for SelectorValueTree {
350    type Value = Selector;
351
352    fn current(&self) -> Selector {
353        Selector {
354            rng: self.rng.clone(),
355            bias_increment: u64::MAX - self.reverse_bias_increment.current(),
356        }
357    }
358
359    fn simplify(&mut self) -> bool {
360        self.reverse_bias_increment.simplify()
361    }
362
363    fn complicate(&mut self) -> bool {
364        self.reverse_bias_increment.complicate()
365    }
366}
367
368impl Selector {
369    /// Pick a random element from iterable `it`.
370    ///
371    /// The selection is unaffected by the elements themselves, and is
372    /// dependent only on the actual length of `it`.
373    ///
374    /// `it` is always iterated completely.
375    ///
376    /// ## Panics
377    ///
378    /// Panics if `it` has no elements.
379    pub fn select<T: IntoIterator>(&self, it: T) -> T::Item {
380        self.try_select(it).expect("select from empty iterator")
381    }
382
383    /// Pick a random element from iterable `it`.
384    ///
385    /// Returns `None` if `it` is empty.
386    ///
387    /// The selection is unaffected by the elements themselves, and is
388    /// dependent only on the actual length of `it`.
389    ///
390    /// `it` is always iterated completely.
391    pub fn try_select<T: IntoIterator>(&self, it: T) -> Option<T::Item> {
392        let mut bias = 0u64;
393        let mut min_score = 0;
394        let mut best = None;
395        let mut rng = self.rng.clone();
396
397        for item in it {
398            let score = bias.saturating_add(rng.gen());
399            if best.is_none() || score < min_score {
400                best = Some(item);
401                min_score = score;
402            }
403
404            bias = bias.saturating_add(self.bias_increment);
405        }
406
407        best
408    }
409}
410
411#[cfg(test)]
412mod test {
413    use crate::std_facade::BTreeSet;
414
415    use super::*;
416    use crate::arbitrary::any;
417
418    #[test]
419    fn sample_slice() {
420        static VALUES: &[usize] = &[0, 1, 2, 3, 4, 5, 6, 7];
421        let mut size_counts = [0; 8];
422        let mut value_counts = [0; 8];
423
424        let mut runner = TestRunner::deterministic();
425        let input = subsequence(VALUES, 3..7);
426
427        for _ in 0..2048 {
428            let value = input.new_tree(&mut runner).unwrap().current();
429            // Generated the correct number of items
430            assert!(value.len() >= 3 && value.len() < 7);
431            // Chose distinct items
432            assert_eq!(
433                value.len(),
434                value.iter().cloned().collect::<BTreeSet<_>>().len()
435            );
436            // Values are in correct order
437            let mut sorted = value.clone();
438            sorted.sort();
439            assert_eq!(sorted, value);
440
441            size_counts[value.len()] += 1;
442
443            for value in value {
444                value_counts[value] += 1;
445            }
446        }
447
448        for i in 3..7 {
449            assert!(
450                size_counts[i] >= 256 && size_counts[i] < 1024,
451                "size {} was chosen {} times",
452                i,
453                size_counts[i]
454            );
455        }
456
457        for (ix, &v) in value_counts.iter().enumerate() {
458            assert!(
459                v >= 1024 && v < 1500,
460                "Value {} was chosen {} times",
461                ix,
462                v
463            );
464        }
465    }
466
467    #[test]
468    fn sample_vec() {
469        // Just test that the types work out
470        let values = vec![0, 1, 2, 3, 4];
471
472        let mut runner = TestRunner::deterministic();
473        let input = subsequence(values, 1..3);
474
475        let _ = input.new_tree(&mut runner).unwrap().current();
476    }
477
478    #[test]
479    fn test_select() {
480        let values = vec![0, 1, 2, 3, 4, 5, 6, 7];
481        let mut counts = [0; 8];
482
483        let mut runner = TestRunner::deterministic();
484        let input = select(values);
485
486        for _ in 0..1024 {
487            counts[input.new_tree(&mut runner).unwrap().current()] += 1;
488        }
489
490        for (ix, &count) in counts.iter().enumerate() {
491            assert!(
492                count >= 64 && count < 256,
493                "Generated value {} {} times",
494                ix,
495                count
496            );
497        }
498    }
499
500    #[test]
501    fn test_sample_sanity() {
502        check_strategy_sanity(subsequence(vec![0, 1, 2, 3, 4], 1..3), None);
503    }
504
505    #[test]
506    fn test_select_sanity() {
507        check_strategy_sanity(select(vec![0, 1, 2, 3, 4]), None);
508    }
509
510    #[test]
511    fn subseq_empty_vec_works() {
512        let mut runner = TestRunner::deterministic();
513        let input = subsequence(Vec::<()>::new(), 0..1);
514        assert_eq!(
515            Vec::<()>::new(),
516            input.new_tree(&mut runner).unwrap().current()
517        );
518    }
519
520    #[test]
521    fn subseq_full_vec_works() {
522        let v = vec![1u32, 2u32, 3u32];
523        let mut runner = TestRunner::deterministic();
524        let input = subsequence(v.clone(), 3);
525        assert_eq!(v, input.new_tree(&mut runner).unwrap().current());
526    }
527
528    #[test]
529    fn index_works() {
530        let mut runner = TestRunner::deterministic();
531        let input = any::<Index>();
532        let col = vec!["foo", "bar", "baz"];
533        let mut seen = BTreeSet::new();
534
535        for _ in 0..16 {
536            let mut tree = input.new_tree(&mut runner).unwrap();
537            seen.insert(*tree.current().get(&col));
538
539            while tree.simplify() {}
540
541            assert_eq!("foo", *tree.current().get(&col));
542        }
543
544        assert_eq!(col.into_iter().collect::<BTreeSet<_>>(), seen);
545    }
546
547    #[test]
548    fn selector_works() {
549        let mut runner = TestRunner::deterministic();
550        let input = any::<Selector>();
551        let col: BTreeSet<&str> =
552            vec!["foo", "bar", "baz"].into_iter().collect();
553        let mut seen = BTreeSet::new();
554
555        for _ in 0..16 {
556            let mut tree = input.new_tree(&mut runner).unwrap();
557            seen.insert(*tree.current().select(&col));
558
559            while tree.simplify() {}
560
561            assert_eq!("bar", *tree.current().select(&col));
562        }
563
564        assert_eq!(col, seen);
565    }
566}
proptest/sample.rs

proptest/
sample.rs
