proptest/
range_subset.rs

1//-
2// Copyright 2017, 2018 The proptest developers
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 index ranges.
11//!
12//! Note that the strategies in this module are not native combinators; that
13//! is, the input range is not itself a strategy, but is rather fixed when
14//! the strategy is created.
15
16use rand::Rng;
17
18use core::fmt;
19use core::hash::Hash;
20use core::ops::Range;
21
22use crate::bits::{BitSetLike, VarBitSet};
23use crate::num::sample_uniform_incl;
24use crate::sample::SizeRange;
25use crate::std_facade::HashMap;
26use crate::std_facade::Vec;
27use crate::strategy::*;
28use crate::test_runner::*;
29
30/// Sample subsets whose size are within `size` from the given `range`.
31///
32/// This is roughly analogous to `rand::sample`, except that it samples _without_ replacement.
33///
34/// ## Panics
35///
36/// Panics if the maximum size implied by `size` is larger than the size of
37/// `values`.
38///
39/// Panics if `size` is a zero-length range.
40pub fn range_subset<T>(
41    range: Range<T>,
42    size: impl Into<SizeRange>,
43) -> RangeSubset<T>
44where
45    T: Copy + Ord + fmt::Debug,
46    Range<T>: ExactSizeIterator<Item = T>,
47{
48    let len = range.len();
49    let size = size.into();
50
51    size.assert_nonempty();
52    assert!(
53        size.end_incl() <= len,
54        "Maximum size of subset {} exceeds length of input {}",
55        size.end_incl(),
56        len
57    );
58    RangeSubset { range, size }
59}
60
61/// Strategy to generate `Vec`s by sampling a subset from an index range.
62///
63/// This is created by the `range_subset` function in the same module.
64#[derive(Debug)]
65pub struct RangeSubset<T> {
66    range: Range<T>,
67    size: SizeRange,
68}
69
70impl<T> Strategy for RangeSubset<T>
71where
72    T: Copy + Eq + Hash + fmt::Debug,
73    Range<T>: ExactSizeIterator<Item = T>,
74{
75    type Tree = RangeSubsetValueTree<T>;
76    type Value = Vec<T>;
77
78    fn new_tree(&self, runner: &mut TestRunner) -> Result<Self::Tree, Reason> {
79        let (min_size, max_size) = (self.size.start(), self.size.end_incl());
80
81        let count = sample_uniform_incl(runner, min_size, max_size);
82
83        let range_len = self.range.len();
84
85        let mut swaps: HashMap<T, T> = HashMap::default();
86
87        let mut values: Vec<T> = Vec::default();
88
89        let rng = runner.rng();
90
91        // # Performance
92        //
93        // Thanks to specialization this `O(n)` access of `range.nth(…)` ends up being `O(1)`.
94
95        // # Safety
96        //
97        // The offsets `i`/`j` get sampled from `0..count`/`0..range.len()`,
98        // (where `0..count` is shorter, or equal in length to `0..range.len()`)
99        // so unwrapping `range.nth(i).unwrap()` is safe:
100
101        // Apply a Fisher-Yates shuffle:
102        for i in 0..count {
103            let j: usize = rng.random_range(i..range_len);
104
105            let iv = self.range.clone().nth(i).unwrap();
106            let vi = *swaps.get(&iv).unwrap_or(&iv);
107
108            let jv = self.range.clone().nth(j).unwrap();
109            let vj = *swaps.get(&jv).unwrap_or(&jv);
110
111            swaps.insert(iv, vj);
112            swaps.insert(jv, vi);
113            values.push(vj);
114        }
115
116        let included_values = VarBitSet::saturated(count);
117
118        Ok(RangeSubsetValueTree {
119            values,
120            included_values,
121            shrink: 0,
122            prev_shrink: None,
123            min_size,
124        })
125    }
126}
127
128/// `RangeSubsetValueTree` corresponding to `RangeSubset`.
129#[derive(Debug, Clone)]
130pub struct RangeSubsetValueTree<T> {
131    values: Vec<T>,
132    included_values: VarBitSet,
133    shrink: usize,
134    prev_shrink: Option<usize>,
135    min_size: usize,
136}
137
138impl<T> ValueTree for RangeSubsetValueTree<T>
139where
140    T: Copy + Eq + Hash + fmt::Debug,
141    Range<T>: ExactSizeIterator<Item = T>,
142{
143    type Value = Vec<T>;
144
145    fn current(&self) -> Self::Value {
146        self.values
147            .iter()
148            .enumerate()
149            .filter_map(|(index, value)| {
150                self.included_values.test(index).then_some(*value)
151            })
152            .collect()
153    }
154
155    fn simplify(&mut self) -> bool {
156        if self.included_values.len() <= self.min_size {
157            return false;
158        }
159
160        while self.shrink < self.values.len()
161            && !self.included_values.test(self.shrink)
162        {
163            self.shrink += 1;
164        }
165
166        if self.shrink >= self.values.len() {
167            self.prev_shrink = None;
168            false
169        } else {
170            self.prev_shrink = Some(self.shrink);
171            self.included_values.clear(self.shrink);
172            self.shrink += 1;
173            true
174        }
175    }
176
177    fn complicate(&mut self) -> bool {
178        if let Some(shrink) = self.prev_shrink.take() {
179            self.included_values.set(shrink);
180            true
181        } else {
182            false
183        }
184    }
185}
186
187#[cfg(test)]
188mod test {
189    use crate::std_facade::BTreeSet;
190
191    use super::*;
192
193    #[test]
194    fn sample_range() {
195        static INDICES: Range<usize> = 0..8;
196        let mut size_counts: [usize; 8] = [0; 8];
197        let mut value_counts: [usize; 8] = [0; 8];
198
199        let mut runner = TestRunner::deterministic();
200        let input = range_subset(INDICES.clone(), 3..7);
201
202        for _ in 0..2048 {
203            let value = input.new_tree(&mut runner).unwrap().current();
204            // Generated the correct number of items
205            assert!(value.len() >= 3 && value.len() < 7);
206            // Chose distinct items
207            assert_eq!(
208                value.len(),
209                value.iter().cloned().collect::<BTreeSet<_>>().len(),
210                "output contains non-distinct items ({value:?})"
211            );
212
213            size_counts[value.len()] += 1;
214
215            for value in value {
216                value_counts[value] += 1;
217            }
218        }
219
220        for i in 3..7 {
221            assert!(
222                size_counts[i] >= 256 && size_counts[i] < 1024,
223                "size {} was chosen {} times",
224                i,
225                size_counts[i]
226            );
227        }
228
229        for (ix, &v) in value_counts.iter().enumerate() {
230            assert!(
231                v >= 1024 && v < 1500,
232                "Value {} was chosen {} times",
233                ix,
234                v
235            );
236        }
237    }
238
239    #[test]
240    fn test_sample_sanity() {
241        check_strategy_sanity(range_subset(0..5, 1..3), None);
242    }
243
244    #[test]
245    fn subset_empty_range_works() {
246        let mut runner = TestRunner::deterministic();
247        let input = range_subset(0..0, 0..1);
248        assert_eq!(
249            Vec::<usize>::new(),
250            input.new_tree(&mut runner).unwrap().current()
251        );
252    }
253
254    #[test]
255    fn subset_full_range_works() {
256        let range = 1..4;
257        let mut runner = TestRunner::deterministic();
258        let input = range_subset(range.clone(), 3);
259        let mut values = input.new_tree(&mut runner).unwrap().current();
260        values.sort();
261        assert_eq!(Vec::<usize>::from_iter(range), values);
262    }
263}
proptest/range_subset.rs

proptest/
range_subset.rs
