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
248// This impl is handy for generic code over any type that exposes an internal `Index` -- with it,
249// a plain `Index` can be passed in as well.
250impl AsRef<Index> for Index {
251    fn as_ref(&self) -> &Index {
252        self
253    }
254}
255
256mapfn! {
257    [] fn UsizeToIndex[](raw: usize) -> Index {
258        Index(raw)
259    }
260}
261
262opaque_strategy_wrapper! {
263    /// Strategy to create `Index`es.
264    ///
265    /// Created via `any::<Index>()`.
266    #[derive(Clone, Debug)]
267    pub struct IndexStrategy[][](
268        statics::Map<num::usize::Any, UsizeToIndex>)
269        -> IndexValueTree;
270    /// `ValueTree` corresponding to `IndexStrategy`.
271    #[derive(Clone, Debug)]
272    pub struct IndexValueTree[][](
273        statics::Map<num::usize::BinarySearch,UsizeToIndex>)
274        -> Index;
275}
276
277impl IndexStrategy {
278    pub(crate) fn new() -> Self {
279        IndexStrategy(statics::Map::new(num::usize::ANY, UsizeToIndex))
280    }
281}
282
283/// A value for picking random values out of iterators.
284///
285/// This is, in a sense, a more flexible variant of
286/// [`Index`](struct.Index.html) in that it can operate on arbitrary
287/// `IntoIterator` values.
288///
289/// Initially, the selection is roughly uniform, with a very slight bias
290/// towards items earlier in the iterator.
291///
292/// Shrinking causes the selection to move toward items earlier in the
293/// iterator, ultimately settling on the very first, but this currently happens
294/// in a very haphazard way that may fail to find the earliest failing input.
295///
296/// ## Example
297///
298/// Generate a non-indexable collection and a value to pick out of it.
299///
300/// ```
301/// use proptest::prelude::*;
302///
303/// proptest! {
304///     # /*
305///     #[test]
306///     # */
307///     fn my_test(
308///         names in prop::collection::hash_set("[a-z]+", 10..20),
309///         selector in any::<prop::sample::Selector>()
310///     ) {
311///         println!("Selected name: {}", selector.select(&names));
312///         // Test stuff...
313///     }
314/// }
315/// #
316/// # fn main() { my_test(); }
317/// ```
318#[derive(Clone, Debug)]
319pub struct Selector {
320    rng: TestRng,
321    bias_increment: u64,
322}
323
324/// Strategy to create `Selector`s.
325///
326/// Created via `any::<Selector>()`.
327#[derive(Debug)]
328pub struct SelectorStrategy {
329    _nonexhaustive: (),
330}
331
332/// `ValueTree` corresponding to `SelectorStrategy`.
333#[derive(Debug)]
334pub struct SelectorValueTree {
335    rng: TestRng,
336    reverse_bias_increment: num::u64::BinarySearch,
337}
338
339impl SelectorStrategy {
340    pub(crate) fn new() -> Self {
341        SelectorStrategy { _nonexhaustive: () }
342    }
343}
344
345impl Strategy for SelectorStrategy {
346    type Tree = SelectorValueTree;
347    type Value = Selector;
348
349    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
350        Ok(SelectorValueTree {
351            rng: runner.new_rng(),
352            reverse_bias_increment: num::u64::BinarySearch::new(u64::MAX),
353        })
354    }
355}
356
357impl ValueTree for SelectorValueTree {
358    type Value = Selector;
359
360    fn current(&self) -> Selector {
361        Selector {
362            rng: self.rng.clone(),
363            bias_increment: u64::MAX - self.reverse_bias_increment.current(),
364        }
365    }
366
367    fn simplify(&mut self) -> bool {
368        self.reverse_bias_increment.simplify()
369    }
370
371    fn complicate(&mut self) -> bool {
372        self.reverse_bias_increment.complicate()
373    }
374}
375
376impl Selector {
377    /// Pick a random element from iterable `it`.
378    ///
379    /// The selection is unaffected by the elements themselves, and is
380    /// dependent only on the actual length of `it`.
381    ///
382    /// `it` is always iterated completely.
383    ///
384    /// ## Panics
385    ///
386    /// Panics if `it` has no elements.
387    pub fn select<T: IntoIterator>(&self, it: T) -> T::Item {
388        self.try_select(it).expect("select from empty iterator")
389    }
390
391    /// Pick a random element from iterable `it`.
392    ///
393    /// Returns `None` if `it` is empty.
394    ///
395    /// The selection is unaffected by the elements themselves, and is
396    /// dependent only on the actual length of `it`.
397    ///
398    /// `it` is always iterated completely.
399    pub fn try_select<T: IntoIterator>(&self, it: T) -> Option<T::Item> {
400        let mut bias = 0u64;
401        let mut min_score = 0;
402        let mut best = None;
403        let mut rng = self.rng.clone();
404
405        for item in it {
406            let score = bias.saturating_add(rng.gen());
407            if best.is_none() || score < min_score {
408                best = Some(item);
409                min_score = score;
410            }
411
412            bias = bias.saturating_add(self.bias_increment);
413        }
414
415        best
416    }
417}
418
419#[cfg(test)]
420mod test {
421    use crate::std_facade::BTreeSet;
422
423    use super::*;
424    use crate::arbitrary::any;
425
426    #[test]
427    fn sample_slice() {
428        static VALUES: &[usize] = &[0, 1, 2, 3, 4, 5, 6, 7];
429        let mut size_counts = [0; 8];
430        let mut value_counts = [0; 8];
431
432        let mut runner = TestRunner::deterministic();
433        let input = subsequence(VALUES, 3..7);
434
435        for _ in 0..2048 {
436            let value = input.new_tree(&mut runner).unwrap().current();
437            // Generated the correct number of items
438            assert!(value.len() >= 3 && value.len() < 7);
439            // Chose distinct items
440            assert_eq!(
441                value.len(),
442                value.iter().cloned().collect::<BTreeSet<_>>().len()
443            );
444            // Values are in correct order
445            let mut sorted = value.clone();
446            sorted.sort();
447            assert_eq!(sorted, value);
448
449            size_counts[value.len()] += 1;
450
451            for value in value {
452                value_counts[value] += 1;
453            }
454        }
455
456        for i in 3..7 {
457            assert!(
458                size_counts[i] >= 256 && size_counts[i] < 1024,
459                "size {} was chosen {} times",
460                i,
461                size_counts[i]
462            );
463        }
464
465        for (ix, &v) in value_counts.iter().enumerate() {
466            assert!(
467                v >= 1024 && v < 1500,
468                "Value {} was chosen {} times",
469                ix,
470                v
471            );
472        }
473    }
474
475    #[test]
476    fn sample_vec() {
477        // Just test that the types work out
478        let values = vec![0, 1, 2, 3, 4];
479
480        let mut runner = TestRunner::deterministic();
481        let input = subsequence(values, 1..3);
482
483        let _ = input.new_tree(&mut runner).unwrap().current();
484    }
485
486    #[test]
487    fn test_select() {
488        let values = vec![0, 1, 2, 3, 4, 5, 6, 7];
489        let mut counts = [0; 8];
490
491        let mut runner = TestRunner::deterministic();
492        let input = select(values);
493
494        for _ in 0..1024 {
495            counts[input.new_tree(&mut runner).unwrap().current()] += 1;
496        }
497
498        for (ix, &count) in counts.iter().enumerate() {
499            assert!(
500                count >= 64 && count < 256,
501                "Generated value {} {} times",
502                ix,
503                count
504            );
505        }
506    }
507
508    #[test]
509    fn test_sample_sanity() {
510        check_strategy_sanity(subsequence(vec![0, 1, 2, 3, 4], 1..3), None);
511    }
512
513    #[test]
514    fn test_select_sanity() {
515        check_strategy_sanity(select(vec![0, 1, 2, 3, 4]), None);
516    }
517
518    #[test]
519    fn subseq_empty_vec_works() {
520        let mut runner = TestRunner::deterministic();
521        let input = subsequence(Vec::<()>::new(), 0..1);
522        assert_eq!(
523            Vec::<()>::new(),
524            input.new_tree(&mut runner).unwrap().current()
525        );
526    }
527
528    #[test]
529    fn subseq_full_vec_works() {
530        let v = vec![1u32, 2u32, 3u32];
531        let mut runner = TestRunner::deterministic();
532        let input = subsequence(v.clone(), 3);
533        assert_eq!(v, input.new_tree(&mut runner).unwrap().current());
534    }
535
536    #[test]
537    fn index_works() {
538        let mut runner = TestRunner::deterministic();
539        let input = any::<Index>();
540        let col = vec!["foo", "bar", "baz"];
541        let mut seen = BTreeSet::new();
542
543        for _ in 0..16 {
544            let mut tree = input.new_tree(&mut runner).unwrap();
545            seen.insert(*tree.current().get(&col));
546
547            while tree.simplify() {}
548
549            assert_eq!("foo", *tree.current().get(&col));
550        }
551
552        assert_eq!(col.into_iter().collect::<BTreeSet<_>>(), seen);
553    }
554
555    #[test]
556    fn selector_works() {
557        let mut runner = TestRunner::deterministic();
558        let input = any::<Selector>();
559        let col: BTreeSet<&str> =
560            vec!["foo", "bar", "baz"].into_iter().collect();
561        let mut seen = BTreeSet::new();
562
563        for _ in 0..16 {
564            let mut tree = input.new_tree(&mut runner).unwrap();
565            seen.insert(*tree.current().select(&col));
566
567            while tree.simplify() {}
568
569            assert_eq!("bar", *tree.current().select(&col));
570        }
571
572        assert_eq!(col, seen);
573    }
574}
proptest/sample.rs

proptest/
sample.rs
