diem_proptest_helpers/
lib.rs

1// Copyright (c) The Diem Core Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4// Copyright 2021 Conflux Foundation. All rights reserved.
5// Conflux is free software and distributed under GNU General Public License.
6// See http://www.gnu.org/licenses/
7
8#![forbid(unsafe_code)]
9
10#[cfg(test)]
11mod unit_tests;
12
13mod growing_subset;
14mod repeat_vec;
15mod value_generator;
16
17pub use crate::{
18    growing_subset::GrowingSubset, repeat_vec::RepeatVec,
19    value_generator::ValueGenerator,
20};
21
22use crossbeam::thread;
23use proptest::sample::Index as PropIndex;
24use proptest_derive::Arbitrary;
25use std::{
26    any::Any,
27    collections::BTreeSet,
28    ops::{Deref, Index as OpsIndex},
29};
30
31/// Creates a new thread with a larger stack size.
32///
33/// Generating some proptest values can overflow the stack. This allows test
34/// authors to work around this limitation.
35///
36/// This is expected to be used with closure-style proptest invocations:
37///
38/// ```
39/// use proptest::prelude::*;
40/// use diem_proptest_helpers::with_stack_size;
41///
42/// with_stack_size(4 * 1024 * 1024, || proptest!(|(x in 0usize..128)| {
43///     // assertions go here
44///     prop_assert!(x >= 0 && x < 128);
45/// }));
46/// ```
47pub fn with_stack_size<'a, F, T>(
48    size: usize, f: F,
49) -> Result<T, Box<dyn Any + 'static + Send>>
50where
51    F: FnOnce() -> T + Send + 'a,
52    T: Send + 'a,
53{
54    thread::scope(|s| {
55        let handle =
56            s.builder().stack_size(size).spawn(|_| f()).map_err(|err| {
57                let any: Box<dyn Any + 'static + Send> = Box::new(err);
58                any
59            })?;
60        handle.join()
61    })?
62}
63
64/// Given a maximum value `max` and a list of [`Index`](proptest::sample::Index)
65/// instances, picks integers in the range `[0, max)` uniformly randomly and
66/// without duplication.
67///
68/// If `indexes_len` is greater than `max`, all indexes will be returned.
69///
70/// This function implements [Robert Floyd's F2
71/// algorithm](https://blog.acolyer.org/2018/01/30/a-sample-of-brilliance/) for sampling without
72/// replacement.
73pub fn pick_idxs<T, P>(
74    max: usize, indexes: &T, indexes_len: usize,
75) -> Vec<usize>
76where
77    T: OpsIndex<usize, Output = P> + ?Sized,
78    P: AsRef<PropIndex>,
79{
80    // See https://blog.acolyer.org/2018/01/30/a-sample-of-brilliance/ (the F2 algorithm)
81    // for a longer explanation. This is a variant that works with
82    // zero-indexing.
83    let mut selected = BTreeSet::new();
84    let to_select = indexes_len.min(max);
85    for (iter_idx, choice) in ((max - to_select)..max).enumerate() {
86        // "RandInt(1, J)" in the original algorithm means a number between 1
87        // and choice, both inclusive. `PropIndex::index` picks a number between
88        // 0 and whatever's passed in, with the latter exclusive. Pass
89        // in "+1" to ensure the same range of values is picked from.
90        // (This also ensures that if choice is 0 then `index`
91        // doesn't panic.
92        let idx = indexes[iter_idx].as_ref().index(choice + 1);
93        if !selected.insert(idx) {
94            selected.insert(choice);
95        }
96    }
97    selected.into_iter().collect()
98}
99
100/// Given a maximum value `max` and a slice of
101/// [`Index`](proptest::sample::Index) instances, picks integers in the range
102/// `[0, max)` uniformly randomly and without duplication.
103///
104/// If the number of `Index` instances is greater than `max`, all indexes will
105/// be returned.
106///
107/// This function implements [Robert Floyd's F2
108/// algorithm](https://blog.acolyer.org/2018/01/30/a-sample-of-brilliance/) for sampling without
109/// replacement.
110#[inline]
111pub fn pick_slice_idxs(
112    max: usize, indexes: &[impl AsRef<PropIndex>],
113) -> Vec<usize> {
114    pick_idxs(max, indexes, indexes.len())
115}
116
117/// Wrapper for `proptest`'s [`Index`][proptest::sample::Index] that allows
118/// `AsRef` to work.
119///
120/// There is no blanket `impl<T> AsRef<T> for T`, so `&[PropIndex]` doesn't work
121/// with `&[impl AsRef<PropIndex>]` (unless an impl gets added upstream).
122/// `Index` does.
123#[derive(Arbitrary, Clone, Copy, Debug)]
124pub struct Index(PropIndex);
125
126impl AsRef<PropIndex> for Index {
127    fn as_ref(&self) -> &PropIndex { &self.0 }
128}
129
130impl Deref for Index {
131    type Target = PropIndex;
132
133    fn deref(&self) -> &PropIndex { &self.0 }
134}
diem_proptest_helpers/lib.rs

diem_proptest_helpers/
lib.rs
