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    assert!(!cow.is_empty(), "Cannot select from empty collection");
162
163    Select(statics::Map::new(0..cow.len(), SelectMapFn(Arc::new(cow))))
164}
165
166/// A stand-in for an index into a slice or similar collection or conceptually
167/// similar things.
168///
169/// At the lowest level, `Index` is a mechanism for generating `usize` values
170/// in the range [0..N), for some N whose value is not known until it is
171/// needed. (Contrast with using `0..N` itself as a strategy, where you need to
172/// know N when you define the strategy.)
173///
174/// For any upper bound, the actual index produced by an `Index` is the same no
175/// matter how many times it is used. Different upper bounds will produce
176/// different but not independent values.
177///
178/// Shrinking will cause the index to binary search through the underlying
179/// collection(s) it is used to sample.
180///
181/// Note that `Index` _cannot_ currently be used as a slice index (e.g.,
182/// `slice[index]`) due to the trait coherence rules.
183///
184/// ## Example
185///
186/// If the collection itself being indexed is itself generated by a strategy,
187/// you can make separately define that strategy and a strategy generating one
188/// or more `Index`es and then join the two after input generation, avoiding a
189/// call to `prop_flat_map()`.
190///
191/// ```
192/// use proptest::prelude::*;
193///
194/// proptest! {
195///     # /*
196///     #[test]
197///     # */
198///     fn my_test(
199///         names in prop::collection::vec("[a-z]+", 10..20),
200///         indices in prop::collection::vec(any::<prop::sample::Index>(), 5..10)
201///     ) {
202///         // We now have Vec<String> of ten to twenty names, and a Vec<Index>
203///         // of five to ten indices and can combine them however we like.
204///         for index in &indices {
205///             println!("Accessing item by index: {}", names[index.index(names.len())]);
206///             println!("Accessing item by convenience method: {}", index.get(&names));
207///         }
208///         // Test stuff...
209///     }
210/// }
211/// #
212/// # fn main() { my_test(); }
213/// ```
214#[derive(Clone, Copy, Debug)]
215pub struct Index(usize);
216
217impl Index {
218    /// Return the real index that would be used to index a collection of size `size`.
219    ///
220    /// ## Panics
221    ///
222    /// Panics if `size == 0`.
223    pub fn index(&self, size: usize) -> usize {
224        assert!(size > 0, "Attempt to use `Index` with 0-size collection");
225
226        // No platforms currently have `usize` wider than 64 bits, so `u128` is
227        // sufficient to hold the result of a full multiply, letting us do a
228        // simple fixed-point multiply.
229        ((size as u128) * (self.0 as u128) >> (mem::size_of::<usize>() * 8))
230            as usize
231    }
232
233    /// Return a reference to the element in `slice` that this `Index` refers to.
234    ///
235    /// A shortcut for `&slice[index.index(slice.len())]`.
236    pub fn get<'a, T>(&self, slice: &'a [T]) -> &'a T {
237        &slice[self.index(slice.len())]
238    }
239
240    /// Return a mutable reference to the element in `slice` that this `Index`
241    /// refers to.
242    ///
243    /// A shortcut for `&mut slice[index.index(slice.len())]`.
244    pub fn get_mut<'a, T>(&self, slice: &'a mut [T]) -> &'a mut T {
245        let ix = self.index(slice.len());
246        &mut slice[ix]
247    }
248}
249
250// This impl is handy for generic code over any type that exposes an internal `Index` -- with it,
251// a plain `Index` can be passed in as well.
252impl AsRef<Index> for Index {
253    fn as_ref(&self) -> &Index {
254        self
255    }
256}
257
258mapfn! {
259    [] fn UsizeToIndex[](raw: usize) -> Index {
260        Index(raw)
261    }
262}
263
264opaque_strategy_wrapper! {
265    /// Strategy to create `Index`es.
266    ///
267    /// Created via `any::<Index>()`.
268    #[derive(Clone, Debug)]
269    pub struct IndexStrategy[][](
270        statics::Map<num::usize::Any, UsizeToIndex>)
271        -> IndexValueTree;
272    /// `ValueTree` corresponding to `IndexStrategy`.
273    #[derive(Clone, Debug)]
274    pub struct IndexValueTree[][](
275        statics::Map<num::usize::BinarySearch,UsizeToIndex>)
276        -> Index;
277}
278
279impl IndexStrategy {
280    pub(crate) fn new() -> Self {
281        IndexStrategy(statics::Map::new(num::usize::ANY, UsizeToIndex))
282    }
283}
284
285/// A value for picking random values out of iterators.
286///
287/// This is, in a sense, a more flexible variant of
288/// [`Index`](struct.Index.html) in that it can operate on arbitrary
289/// `IntoIterator` values.
290///
291/// Initially, the selection is roughly uniform, with a very slight bias
292/// towards items earlier in the iterator.
293///
294/// Shrinking causes the selection to move toward items earlier in the
295/// iterator, ultimately settling on the very first, but this currently happens
296/// in a very haphazard way that may fail to find the earliest failing input.
297///
298/// ## Example
299///
300/// Generate a non-indexable collection and a value to pick out of it.
301///
302/// ```
303/// use proptest::prelude::*;
304///
305/// proptest! {
306///     # /*
307///     #[test]
308///     # */
309///     fn my_test(
310///         names in prop::collection::hash_set("[a-z]+", 10..20),
311///         selector in any::<prop::sample::Selector>()
312///     ) {
313///         println!("Selected name: {}", selector.select(&names));
314///         // Test stuff...
315///     }
316/// }
317/// #
318/// # fn main() { my_test(); }
319/// ```
320#[derive(Clone, Debug)]
321pub struct Selector {
322    rng: TestRng,
323    bias_increment: u64,
324}
325
326/// Strategy to create `Selector`s.
327///
328/// Created via `any::<Selector>()`.
329#[derive(Debug)]
330pub struct SelectorStrategy {
331    _nonexhaustive: (),
332}
333
334/// `ValueTree` corresponding to `SelectorStrategy`.
335#[derive(Debug)]
336pub struct SelectorValueTree {
337    rng: TestRng,
338    reverse_bias_increment: num::u64::BinarySearch,
339}
340
341impl SelectorStrategy {
342    pub(crate) fn new() -> Self {
343        SelectorStrategy { _nonexhaustive: () }
344    }
345}
346
347impl Strategy for SelectorStrategy {
348    type Tree = SelectorValueTree;
349    type Value = Selector;
350
351    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
352        Ok(SelectorValueTree {
353            rng: runner.new_rng(),
354            reverse_bias_increment: num::u64::BinarySearch::new(u64::MAX),
355        })
356    }
357}
358
359impl ValueTree for SelectorValueTree {
360    type Value = Selector;
361
362    fn current(&self) -> Selector {
363        Selector {
364            rng: self.rng.clone(),
365            bias_increment: u64::MAX - self.reverse_bias_increment.current(),
366        }
367    }
368
369    fn simplify(&mut self) -> bool {
370        self.reverse_bias_increment.simplify()
371    }
372
373    fn complicate(&mut self) -> bool {
374        self.reverse_bias_increment.complicate()
375    }
376}
377
378impl Selector {
379    /// Pick a random element from iterable `it`.
380    ///
381    /// The selection is unaffected by the elements themselves, and is
382    /// dependent only on the actual length of `it`.
383    ///
384    /// `it` is always iterated completely.
385    ///
386    /// ## Panics
387    ///
388    /// Panics if `it` has no elements.
389    pub fn select<T: IntoIterator>(&self, it: T) -> T::Item {
390        self.try_select(it).expect("select from empty iterator")
391    }
392
393    /// Pick a random element from iterable `it`.
394    ///
395    /// Returns `None` if `it` is empty.
396    ///
397    /// The selection is unaffected by the elements themselves, and is
398    /// dependent only on the actual length of `it`.
399    ///
400    /// `it` is always iterated completely.
401    pub fn try_select<T: IntoIterator>(&self, it: T) -> Option<T::Item> {
402        let mut bias = 0u64;
403        let mut min_score = 0;
404        let mut best = None;
405        let mut rng = self.rng.clone();
406
407        for item in it {
408            let score = bias.saturating_add(rng.random());
409            if best.is_none() || score < min_score {
410                best = Some(item);
411                min_score = score;
412            }
413
414            bias = bias.saturating_add(self.bias_increment);
415        }
416
417        best
418    }
419}
420
421#[cfg(test)]
422mod test {
423    use crate::std_facade::BTreeSet;
424
425    use super::*;
426    use crate::arbitrary::any;
427
428    #[test]
429    fn sample_slice() {
430        static VALUES: &[usize] = &[0, 1, 2, 3, 4, 5, 6, 7];
431        let mut size_counts = [0; 8];
432        let mut value_counts = [0; 8];
433
434        let mut runner = TestRunner::deterministic();
435        let input = subsequence(VALUES, 3..7);
436
437        for _ in 0..2048 {
438            let value = input.new_tree(&mut runner).unwrap().current();
439            // Generated the correct number of items
440            assert!(value.len() >= 3 && value.len() < 7);
441            // Chose distinct items
442            assert_eq!(
443                value.len(),
444                value.iter().cloned().collect::<BTreeSet<_>>().len()
445            );
446            // Values are in correct order
447            let mut sorted = value.clone();
448            sorted.sort();
449            assert_eq!(sorted, value);
450
451            size_counts[value.len()] += 1;
452
453            for value in value {
454                value_counts[value] += 1;
455            }
456        }
457
458        for i in 3..7 {
459            assert!(
460                size_counts[i] >= 256 && size_counts[i] < 1024,
461                "size {} was chosen {} times",
462                i,
463                size_counts[i]
464            );
465        }
466
467        for (ix, &v) in value_counts.iter().enumerate() {
468            assert!(
469                v >= 1024 && v < 1500,
470                "Value {} was chosen {} times",
471                ix,
472                v
473            );
474        }
475    }
476
477    #[test]
478    fn sample_vec() {
479        // Just test that the types work out
480        let values = vec![0, 1, 2, 3, 4];
481
482        let mut runner = TestRunner::deterministic();
483        let input = subsequence(values, 1..3);
484
485        let _ = input.new_tree(&mut runner).unwrap().current();
486    }
487
488    #[test]
489    fn test_select() {
490        let values = vec![0, 1, 2, 3, 4, 5, 6, 7];
491        let mut counts = [0; 8];
492
493        let mut runner = TestRunner::deterministic();
494        let input = select(values);
495
496        for _ in 0..1024 {
497            counts[input.new_tree(&mut runner).unwrap().current()] += 1;
498        }
499
500        for (ix, &count) in counts.iter().enumerate() {
501            assert!(
502                count >= 64 && count < 256,
503                "Generated value {} {} times",
504                ix,
505                count
506            );
507        }
508    }
509
510    #[test]
511    fn test_sample_sanity() {
512        check_strategy_sanity(subsequence(vec![0, 1, 2, 3, 4], 1..3), None);
513    }
514
515    #[test]
516    fn test_select_sanity() {
517        check_strategy_sanity(select(vec![0, 1, 2, 3, 4]), None);
518    }
519
520    #[test]
521    fn subseq_empty_vec_works() {
522        let mut runner = TestRunner::deterministic();
523        let input = subsequence(Vec::<()>::new(), 0..1);
524        assert_eq!(
525            Vec::<()>::new(),
526            input.new_tree(&mut runner).unwrap().current()
527        );
528    }
529
530    #[test]
531    fn subseq_full_vec_works() {
532        let v = vec![1u32, 2u32, 3u32];
533        let mut runner = TestRunner::deterministic();
534        let input = subsequence(v.clone(), 3);
535        assert_eq!(v, input.new_tree(&mut runner).unwrap().current());
536    }
537
538    #[test]
539    fn index_works() {
540        let mut runner = TestRunner::deterministic();
541        let input = any::<Index>();
542        let col = vec!["foo", "bar", "baz"];
543        let mut seen = BTreeSet::new();
544
545        for _ in 0..16 {
546            let mut tree = input.new_tree(&mut runner).unwrap();
547            seen.insert(*tree.current().get(&col));
548
549            while tree.simplify() {}
550
551            assert_eq!("foo", *tree.current().get(&col));
552        }
553
554        assert_eq!(col.into_iter().collect::<BTreeSet<_>>(), seen);
555    }
556
557    #[test]
558    fn selector_works() {
559        let mut runner = TestRunner::deterministic();
560        let input = any::<Selector>();
561        let col: BTreeSet<&str> =
562            vec!["foo", "bar", "baz"].into_iter().collect();
563        let mut seen = BTreeSet::new();
564
565        for _ in 0..16 {
566            let mut tree = input.new_tree(&mut runner).unwrap();
567            seen.insert(*tree.current().select(&col));
568
569            while tree.simplify() {}
570
571            assert_eq!("bar", *tree.current().select(&col));
572        }
573
574        assert_eq!(col, seen);
575    }
576}
proptest/sample.rs

proptest/
sample.rs
