proptest/strategy/
shuffle.rs

1//-
2// Copyright 2017 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
10use crate::std_facade::{Cell, Vec, VecDeque};
11
12use rand::Rng;
13
14use crate::num;
15use crate::strategy::traits::*;
16use crate::test_runner::*;
17
18/// `Strategy` shuffle adaptor.
19///
20/// See `Strategy::prop_shuffle()`.
21#[derive(Clone, Debug)]
22#[must_use = "strategies do nothing unless used"]
23pub struct Shuffle<S>(pub(super) S);
24
25/// A value which can be used with the `prop_shuffle` combinator.
26///
27/// This is not a general-purpose trait. Its methods are prefixed with
28/// `shuffle_` to avoid the compiler suggesting them or this trait as
29/// corrections in errors.
30pub trait Shuffleable {
31    /// Return the length of this collection.
32    fn shuffle_len(&self) -> usize;
33    /// Swap the elements at the given indices.
34    fn shuffle_swap(&mut self, a: usize, b: usize);
35}
36
37macro_rules! shuffleable {
38    ($($t:tt)*) => {
39        impl<T> Shuffleable for $($t)* {
40            fn shuffle_len(&self) -> usize {
41                self.len()
42            }
43
44            fn shuffle_swap(&mut self, a: usize, b: usize) {
45                self.swap(a, b);
46            }
47        }
48    }
49}
50
51shuffleable!([T]);
52shuffleable!(Vec<T>);
53shuffleable!(VecDeque<T>);
54// Zero- and 1-length arrays aren't usefully shuffleable, but are included to
55// simplify external macros that may try to use them anyway.
56shuffleable!([T; 0]);
57shuffleable!([T; 1]);
58shuffleable!([T; 2]);
59shuffleable!([T; 3]);
60shuffleable!([T; 4]);
61shuffleable!([T; 5]);
62shuffleable!([T; 6]);
63shuffleable!([T; 7]);
64shuffleable!([T; 8]);
65shuffleable!([T; 9]);
66shuffleable!([T; 10]);
67shuffleable!([T; 11]);
68shuffleable!([T; 12]);
69shuffleable!([T; 13]);
70shuffleable!([T; 14]);
71shuffleable!([T; 15]);
72shuffleable!([T; 16]);
73shuffleable!([T; 17]);
74shuffleable!([T; 18]);
75shuffleable!([T; 19]);
76shuffleable!([T; 20]);
77shuffleable!([T; 21]);
78shuffleable!([T; 22]);
79shuffleable!([T; 23]);
80shuffleable!([T; 24]);
81shuffleable!([T; 25]);
82shuffleable!([T; 26]);
83shuffleable!([T; 27]);
84shuffleable!([T; 28]);
85shuffleable!([T; 29]);
86shuffleable!([T; 30]);
87shuffleable!([T; 31]);
88shuffleable!([T; 32]);
89
90impl<S: Strategy> Strategy for Shuffle<S>
91where
92    S::Value: Shuffleable,
93{
94    type Tree = ShuffleValueTree<S::Tree>;
95    type Value = S::Value;
96
97    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
98        let rng = runner.new_rng();
99
100        self.0.new_tree(runner).map(|inner| ShuffleValueTree {
101            inner,
102            rng,
103            dist: Cell::new(None),
104            simplifying_inner: false,
105        })
106    }
107}
108
109/// `ValueTree` shuffling adaptor.
110///
111/// See `Strategy::prop_shuffle()`.
112#[derive(Clone, Debug)]
113pub struct ShuffleValueTree<V> {
114    inner: V,
115    rng: TestRng,
116    /// The maximum amount to move any one element during shuffling.
117    ///
118    /// This is `Cell` since we can't determine the bounds of the value until
119    /// the first call to `current()`. (We technically _could_ by generating a
120    /// value in `new_tree` and checking its length, but that would be a 100%
121    /// slowdown.)
122    dist: Cell<Option<num::usize::BinarySearch>>,
123    /// Whether we've started simplifying `inner`. After this point, we can no
124    /// longer simplify or complicate `dist`.
125    simplifying_inner: bool,
126}
127
128impl<V: ValueTree> ShuffleValueTree<V>
129where
130    V::Value: Shuffleable,
131{
132    fn init_dist(&self, dflt: usize) -> usize {
133        if self.dist.get().is_none() {
134            self.dist.set(Some(num::usize::BinarySearch::new(dflt)));
135        }
136
137        self.dist.get().unwrap().current()
138    }
139
140    fn force_init_dist(&self) {
141        if self.dist.get().is_none() {
142            self.init_dist(self.current().shuffle_len());
143        }
144    }
145}
146
147impl<V: ValueTree> ValueTree for ShuffleValueTree<V>
148where
149    V::Value: Shuffleable,
150{
151    type Value = V::Value;
152
153    fn current(&self) -> V::Value {
154        let mut value = self.inner.current();
155        let len = value.shuffle_len();
156        // The maximum distance to swap elements. This could be larger than
157        // `value` if `value` has reduced size during shrinking; that's OK,
158        // since we only use this to filter swaps.
159        let max_swap = self.init_dist(len);
160
161        // If empty collection or all swaps will be filtered out, there's
162        // nothing to shuffle.
163        if 0 == len || 0 == max_swap {
164            return value;
165        }
166
167        let mut rng = self.rng.clone();
168
169        for start_index in 0..len - 1 {
170            // Determine the other index to be swapped, then skip the swap if
171            // it is too far. This ordering is critical, as it ensures that we
172            // generate the same sequence of random numbers every time.
173            let end_index = rng.gen_range(start_index..len);
174            if end_index - start_index <= max_swap {
175                value.shuffle_swap(start_index, end_index);
176            }
177        }
178
179        value
180    }
181
182    fn simplify(&mut self) -> bool {
183        if self.simplifying_inner {
184            self.inner.simplify()
185        } else {
186            // Ensure that we've initialised `dist` to *something* to give
187            // consistent non-panicking behaviour even if called in an
188            // unexpected sequence.
189            self.force_init_dist();
190            if self.dist.get_mut().as_mut().unwrap().simplify() {
191                true
192            } else {
193                self.simplifying_inner = true;
194                self.inner.simplify()
195            }
196        }
197    }
198
199    fn complicate(&mut self) -> bool {
200        if self.simplifying_inner {
201            self.inner.complicate()
202        } else {
203            self.force_init_dist();
204            self.dist.get_mut().as_mut().unwrap().complicate()
205        }
206    }
207}
208
209#[cfg(test)]
210mod test {
211    use std::borrow::ToOwned;
212    use std::collections::HashSet;
213    use std::i32;
214
215    use super::*;
216    use crate::collection;
217    use crate::strategy::just::Just;
218
219    static VALUES: &'static [i32] = &[
220        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
221    ];
222
223    #[test]
224    fn generates_different_permutations() {
225        let mut runner = TestRunner::default();
226        let mut seen = HashSet::<Vec<i32>>::new();
227
228        let input = Just(VALUES.to_owned()).prop_shuffle();
229
230        for _ in 0..1024 {
231            let mut value = input.new_tree(&mut runner).unwrap().current();
232
233            assert!(
234                seen.insert(value.clone()),
235                "Value {:?} generated more than once",
236                value
237            );
238
239            value.sort();
240            assert_eq!(VALUES, &value[..]);
241        }
242    }
243
244    #[test]
245    fn simplify_reduces_shuffle_amount() {
246        let mut runner = TestRunner::default();
247
248        let input = Just(VALUES.to_owned()).prop_shuffle();
249        for _ in 0..1024 {
250            let mut value = input.new_tree(&mut runner).unwrap();
251
252            let mut prev_dist = i32::MAX;
253            loop {
254                let v = value.current();
255                // Compute the "shuffle distance" by summing the absolute
256                // distance of each element's displacement.
257                let mut dist = 0;
258                for (ix, &nominal) in v.iter().enumerate() {
259                    dist += (nominal - ix as i32).abs();
260                }
261
262                assert!(
263                    dist <= prev_dist,
264                    "dist = {}, prev_dist = {}",
265                    dist,
266                    prev_dist
267                );
268
269                prev_dist = dist;
270                if !value.simplify() {
271                    break;
272                }
273            }
274
275            // When fully simplified, the result is in the original order.
276            assert_eq!(0, prev_dist);
277        }
278    }
279
280    #[test]
281    fn simplify_complicate_contract_upheld() {
282        check_strategy_sanity(
283            collection::vec(0i32..1000, 5..10).prop_shuffle(),
284            None,
285        );
286    }
287}
proptest/strategy/shuffle.rs

proptest/strategy/
shuffle.rs
