proptest/
collection.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 `std::collections` of values.
11
12use core::cmp::Ord;
13use core::hash::Hash;
14use core::ops::{Add, Range, RangeInclusive, RangeTo, RangeToInclusive};
15use core::usize;
16
17use crate::std_facade::{
18    fmt, BTreeMap, BTreeSet, BinaryHeap, LinkedList, Vec, VecDeque,
19};
20
21#[cfg(feature = "std")]
22use crate::std_facade::{HashMap, HashSet};
23
24use crate::bits::{BitSetLike, VarBitSet};
25use crate::num::sample_uniform_incl;
26use crate::strategy::*;
27use crate::test_runner::*;
28use crate::tuple::TupleValueTree;
29
30//==============================================================================
31// SizeRange
32//==============================================================================
33
34/// The minimum and maximum range/bounds on the size of a collection.
35/// The interval must form a subset of `[0, std::usize::MAX)`.
36///
37/// A value like `0..=std::usize::MAX` will still be accepted but will silently
38/// truncate the maximum to `std::usize::MAX - 1`.
39///
40/// The `Default` is `0..PROPTEST_MAX_DEFAULT_SIZE_RANGE`. The max can be set with
41/// the `PROPTEST_MAX_DEFAULT_SIZE_RANGE` env var, which defaults to `100`.
42#[derive(Clone, PartialEq, Eq, Hash, Debug)]
43pub struct SizeRange(Range<usize>);
44
45/// Creates a `SizeRange` from some value that is convertible into it.
46pub fn size_range(from: impl Into<SizeRange>) -> SizeRange {
47    from.into()
48}
49
50impl Default for SizeRange {
51    /// Constructs a `SizeRange` equivalent to `size_range(0..PROPTEST_MAX_DEFAULT_SIZE_RANGE)`.
52    /// The max can be set with the `PROPTEST_MAX_DEFAULT_SIZE_RANGE` env var, which defaults to `100`.
53    fn default() -> Self {
54        size_range(0..Config::default().max_default_size_range)
55    }
56}
57
58impl SizeRange {
59    /// Creates a `SizeBounds` from a `RangeInclusive<usize>`.
60    pub fn new(range: RangeInclusive<usize>) -> Self {
61        range.into()
62    }
63
64    // Don't rely on these existing internally:
65
66    /// Merges self together with some other argument producing a product
67    /// type expected by some implementations of `A: Arbitrary` in
68    /// `A::Parameters`. This can be more ergonomic to work with and may
69    /// help type inference.
70    pub fn with<X>(self, and: X) -> product_type![Self, X] {
71        product_pack![self, and]
72    }
73
74    /// Merges self together with some other argument generated with a
75    /// default value producing a product type expected by some
76    /// implementations of `A: Arbitrary` in `A::Parameters`.
77    /// This can be more ergonomic to work with and may help type inference.
78    pub fn lift<X: Default>(self) -> product_type![Self, X] {
79        self.with(Default::default())
80    }
81
82    /// The lower bound of the range (inclusive).
83    pub fn start(&self) -> usize {
84        self.0.start
85    }
86
87    /// Extract the ends `[low, high]` of a `SizeRange`.
88    pub fn start_end_incl(&self) -> (usize, usize) {
89        (self.start(), self.end_incl())
90    }
91
92    /// The upper bound of the range (inclusive).
93    pub fn end_incl(&self) -> usize {
94        self.0.end - 1
95    }
96
97    /// The upper bound of the range (exclusive).
98    pub fn end_excl(&self) -> usize {
99        self.0.end
100    }
101
102    pub(crate) fn iter(&self) -> impl Iterator<Item = usize> {
103        self.0.clone().into_iter()
104    }
105
106    pub(crate) fn is_empty(&self) -> bool {
107        self.start() == self.end_excl()
108    }
109
110    pub(crate) fn assert_nonempty(&self) {
111        if self.is_empty() {
112            panic!(
113                "Invalid use of empty size range. (hint: did you \
114                 accidentally write {}..{} where you meant {}..={} \
115                 somewhere?)",
116                self.start(),
117                self.end_excl(),
118                self.start(),
119                self.end_excl()
120            );
121        }
122    }
123}
124
125/// Given `(low: usize, high: usize)`,
126/// then a size range of `[low..high)` is the result.
127impl From<(usize, usize)> for SizeRange {
128    fn from((low, high): (usize, usize)) -> Self {
129        size_range(low..high)
130    }
131}
132
133/// Given `exact`, then a size range of `[exact, exact]` is the result.
134impl From<usize> for SizeRange {
135    fn from(exact: usize) -> Self {
136        size_range(exact..=exact)
137    }
138}
139
140/// Given `..high`, then a size range `[0, high)` is the result.
141impl From<RangeTo<usize>> for SizeRange {
142    fn from(high: RangeTo<usize>) -> Self {
143        size_range(0..high.end)
144    }
145}
146
147/// Given `low .. high`, then a size range `[low, high)` is the result.
148impl From<Range<usize>> for SizeRange {
149    fn from(r: Range<usize>) -> Self {
150        SizeRange(r)
151    }
152}
153
154/// Given `low ..= high`, then a size range `[low, high]` is the result.
155impl From<RangeInclusive<usize>> for SizeRange {
156    fn from(r: RangeInclusive<usize>) -> Self {
157        size_range(*r.start()..r.end().saturating_add(1))
158    }
159}
160
161/// Given `..=high`, then a size range `[0, high]` is the result.
162impl From<RangeToInclusive<usize>> for SizeRange {
163    fn from(high: RangeToInclusive<usize>) -> Self {
164        size_range(0..=high.end)
165    }
166}
167
168#[cfg(feature = "frunk")]
169impl Generic for SizeRange {
170    type Repr = RangeInclusive<usize>;
171
172    /// Converts the `SizeRange` into `Range<usize>`.
173    fn into(self) -> Self::Repr {
174        self.0
175    }
176
177    /// Converts `RangeInclusive<usize>` into `SizeRange`.
178    fn from(r: Self::Repr) -> Self {
179        r.into()
180    }
181}
182
183/// Adds `usize` to both start and end of the bounds.
184///
185/// Panics if adding to either end overflows `usize`.
186impl Add<usize> for SizeRange {
187    type Output = SizeRange;
188
189    fn add(self, rhs: usize) -> Self::Output {
190        let (start, end) = self.start_end_incl();
191        size_range((start + rhs)..=(end + rhs))
192    }
193}
194
195//==============================================================================
196// Strategies
197//==============================================================================
198
199/// Strategy to create `Vec`s with a length in a certain range.
200///
201/// Created by the `vec()` function in the same module.
202#[must_use = "strategies do nothing unless used"]
203#[derive(Clone, Debug)]
204pub struct VecStrategy<T: Strategy> {
205    element: T,
206    size: SizeRange,
207}
208
209/// Create a strategy to generate `Vec`s containing elements drawn from
210/// `element` and with a size range given by `size`.
211///
212/// To make a `Vec` with a fixed number of elements, each with its own
213/// strategy, you can instead make a `Vec` of strategies (boxed if necessary).
214pub fn vec<T: Strategy>(
215    element: T,
216    size: impl Into<SizeRange>,
217) -> VecStrategy<T> {
218    let size = size.into();
219    size.assert_nonempty();
220    VecStrategy { element, size }
221}
222
223mapfn! {
224    [] fn VecToDeque[<T : fmt::Debug>](vec: Vec<T>) -> VecDeque<T> {
225        vec.into()
226    }
227}
228
229opaque_strategy_wrapper! {
230    /// Strategy to create `VecDeque`s with a length in a certain range.
231    ///
232    /// Created by the `vec_deque()` function in the same module.
233    #[derive(Clone, Debug)]
234    pub struct VecDequeStrategy[<T>][where T : Strategy](
235        statics::Map<VecStrategy<T>, VecToDeque>)
236        -> VecDequeValueTree<T::Tree>;
237    /// `ValueTree` corresponding to `VecDequeStrategy`.
238    #[derive(Clone, Debug)]
239    pub struct VecDequeValueTree[<T>][where T : ValueTree](
240        statics::Map<VecValueTree<T>, VecToDeque>)
241        -> VecDeque<T::Value>;
242}
243
244/// Create a strategy to generate `VecDeque`s containing elements drawn from
245/// `element` and with a size range given by `size`.
246pub fn vec_deque<T: Strategy>(
247    element: T,
248    size: impl Into<SizeRange>,
249) -> VecDequeStrategy<T> {
250    VecDequeStrategy(statics::Map::new(vec(element, size), VecToDeque))
251}
252
253mapfn! {
254    [] fn VecToLl[<T : fmt::Debug>](vec: Vec<T>) -> LinkedList<T> {
255        vec.into_iter().collect()
256    }
257}
258
259opaque_strategy_wrapper! {
260    /// Strategy to create `LinkedList`s with a length in a certain range.
261    ///
262    /// Created by the `linkedlist()` function in the same module.
263    #[derive(Clone, Debug)]
264    pub struct LinkedListStrategy[<T>][where T : Strategy](
265        statics::Map<VecStrategy<T>, VecToLl>)
266        -> LinkedListValueTree<T::Tree>;
267    /// `ValueTree` corresponding to `LinkedListStrategy`.
268    #[derive(Clone, Debug)]
269    pub struct LinkedListValueTree[<T>][where T : ValueTree](
270        statics::Map<VecValueTree<T>, VecToLl>)
271        -> LinkedList<T::Value>;
272}
273
274/// Create a strategy to generate `LinkedList`s containing elements drawn from
275/// `element` and with a size range given by `size`.
276pub fn linked_list<T: Strategy>(
277    element: T,
278    size: impl Into<SizeRange>,
279) -> LinkedListStrategy<T> {
280    LinkedListStrategy(statics::Map::new(vec(element, size), VecToLl))
281}
282
283mapfn! {
284    [] fn VecToBinHeap[<T : fmt::Debug + Ord>](vec: Vec<T>) -> BinaryHeap<T> {
285        vec.into()
286    }
287}
288
289opaque_strategy_wrapper! {
290    /// Strategy to create `BinaryHeap`s with a length in a certain range.
291    ///
292    /// Created by the `binary_heap()` function in the same module.
293    #[derive(Clone, Debug)]
294    pub struct BinaryHeapStrategy[<T>][where T : Strategy, T::Value : Ord](
295        statics::Map<VecStrategy<T>, VecToBinHeap>)
296        -> BinaryHeapValueTree<T::Tree>;
297    /// `ValueTree` corresponding to `BinaryHeapStrategy`.
298    #[derive(Clone, Debug)]
299    pub struct BinaryHeapValueTree[<T>][where T : ValueTree, T::Value : Ord](
300        statics::Map<VecValueTree<T>, VecToBinHeap>)
301        -> BinaryHeap<T::Value>;
302}
303
304/// Create a strategy to generate `BinaryHeap`s containing elements drawn from
305/// `element` and with a size range given by `size`.
306pub fn binary_heap<T: Strategy>(
307    element: T,
308    size: impl Into<SizeRange>,
309) -> BinaryHeapStrategy<T>
310where
311    T::Value: Ord,
312{
313    BinaryHeapStrategy(statics::Map::new(vec(element, size), VecToBinHeap))
314}
315
316mapfn! {
317    {#[cfg(feature = "std")]}
318    [] fn VecToHashSet[<T : fmt::Debug + Hash + Eq>](vec: Vec<T>)
319                                                     -> HashSet<T> {
320        vec.into_iter().collect()
321    }
322}
323
324#[derive(Debug, Clone, Copy)]
325struct MinSize(usize);
326
327#[cfg(feature = "std")]
328impl<T: Eq + Hash> statics::FilterFn<HashSet<T>> for MinSize {
329    fn apply(&self, set: &HashSet<T>) -> bool {
330        set.len() >= self.0
331    }
332}
333
334opaque_strategy_wrapper! {
335    {#[cfg(feature = "std")]}
336    {#[cfg_attr(docsrs, doc(cfg(feature = "std")))]}
337    /// Strategy to create `HashSet`s with a length in a certain range.
338    ///
339    /// Created by the `hash_set()` function in the same module.
340    #[derive(Clone, Debug)]
341    pub struct HashSetStrategy[<T>][where T : Strategy, T::Value : Hash + Eq](
342        statics::Filter<statics::Map<VecStrategy<T>, VecToHashSet>, MinSize>)
343        -> HashSetValueTree<T::Tree>;
344    /// `ValueTree` corresponding to `HashSetStrategy`.
345    #[derive(Clone, Debug)]
346    pub struct HashSetValueTree[<T>][where T : ValueTree, T::Value : Hash + Eq](
347        statics::Filter<statics::Map<VecValueTree<T>, VecToHashSet>, MinSize>)
348        -> HashSet<T::Value>;
349}
350
351/// Create a strategy to generate `HashSet`s containing elements drawn from
352/// `element` and with a size range given by `size`.
353///
354/// This strategy will implicitly do local rejects to ensure that the `HashSet`
355/// has at least the minimum number of elements, in case `element` should
356/// produce duplicate values.
357#[cfg(feature = "std")]
358#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
359pub fn hash_set<T: Strategy>(
360    element: T,
361    size: impl Into<SizeRange>,
362) -> HashSetStrategy<T>
363where
364    T::Value: Hash + Eq,
365{
366    let size = size.into();
367    HashSetStrategy(statics::Filter::new(
368        statics::Map::new(vec(element, size.clone()), VecToHashSet),
369        "HashSet minimum size".into(),
370        MinSize(size.start()),
371    ))
372}
373
374mapfn! {
375    [] fn VecToBTreeSet[<T : fmt::Debug + Ord>](vec: Vec<T>)
376                                                -> BTreeSet<T> {
377        vec.into_iter().collect()
378    }
379}
380
381impl<T: Ord> statics::FilterFn<BTreeSet<T>> for MinSize {
382    fn apply(&self, set: &BTreeSet<T>) -> bool {
383        set.len() >= self.0
384    }
385}
386
387opaque_strategy_wrapper! {
388    /// Strategy to create `BTreeSet`s with a length in a certain range.
389    ///
390    /// Created by the `btree_set()` function in the same module.
391    #[derive(Clone, Debug)]
392    pub struct BTreeSetStrategy[<T>][where T : Strategy, T::Value : Ord](
393        statics::Filter<statics::Map<VecStrategy<T>, VecToBTreeSet>, MinSize>)
394        -> BTreeSetValueTree<T::Tree>;
395    /// `ValueTree` corresponding to `BTreeSetStrategy`.
396    #[derive(Clone, Debug)]
397    pub struct BTreeSetValueTree[<T>][where T : ValueTree, T::Value : Ord](
398        statics::Filter<statics::Map<VecValueTree<T>, VecToBTreeSet>, MinSize>)
399        -> BTreeSet<T::Value>;
400}
401
402/// Create a strategy to generate `BTreeSet`s containing elements drawn from
403/// `element` and with a size range given by `size`.
404///
405/// This strategy will implicitly do local rejects to ensure that the
406/// `BTreeSet` has at least the minimum number of elements, in case `element`
407/// should produce duplicate values.
408pub fn btree_set<T: Strategy>(
409    element: T,
410    size: impl Into<SizeRange>,
411) -> BTreeSetStrategy<T>
412where
413    T::Value: Ord,
414{
415    let size = size.into();
416    BTreeSetStrategy(statics::Filter::new(
417        statics::Map::new(vec(element, size.clone()), VecToBTreeSet),
418        "BTreeSet minimum size".into(),
419        MinSize(size.start()),
420    ))
421}
422
423mapfn! {
424    {#[cfg(feature = "std")]}
425    [] fn VecToHashMap[<K : fmt::Debug + Hash + Eq, V : fmt::Debug>]
426        (vec: Vec<(K, V)>) -> HashMap<K, V>
427    {
428        vec.into_iter().collect()
429    }
430}
431
432#[cfg(feature = "std")]
433impl<K: Hash + Eq, V> statics::FilterFn<HashMap<K, V>> for MinSize {
434    fn apply(&self, map: &HashMap<K, V>) -> bool {
435        map.len() >= self.0
436    }
437}
438
439opaque_strategy_wrapper! {
440    {#[cfg(feature = "std")]}
441    {#[cfg_attr(docsrs, doc(cfg(feature = "std")))]}
442    /// Strategy to create `HashMap`s with a length in a certain range.
443    ///
444    /// Created by the `hash_map()` function in the same module.
445    #[derive(Clone, Debug)]
446    pub struct HashMapStrategy[<K, V>]
447        [where K : Strategy, V : Strategy, K::Value : Hash + Eq](
448            statics::Filter<statics::Map<VecStrategy<(K,V)>,
449            VecToHashMap>, MinSize>)
450        -> HashMapValueTree<K::Tree, V::Tree>;
451    /// `ValueTree` corresponding to `HashMapStrategy`.
452    #[derive(Clone, Debug)]
453    pub struct HashMapValueTree[<K, V>]
454        [where K : ValueTree, V : ValueTree, K::Value : Hash + Eq](
455            statics::Filter<statics::Map<VecValueTree<TupleValueTree<(K, V)>>,
456            VecToHashMap>, MinSize>)
457        -> HashMap<K::Value, V::Value>;
458}
459
460/// Create a strategy to generate `HashMap`s containing keys and values drawn
461/// from `key` and `value` respectively, and with a size within the given
462/// range.
463///
464/// This strategy will implicitly do local rejects to ensure that the `HashMap`
465/// has at least the minimum number of elements, in case `key` should produce
466/// duplicate values.
467#[cfg(feature = "std")]
468#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
469pub fn hash_map<K: Strategy, V: Strategy>(
470    key: K,
471    value: V,
472    size: impl Into<SizeRange>,
473) -> HashMapStrategy<K, V>
474where
475    K::Value: Hash + Eq,
476{
477    let size = size.into();
478    HashMapStrategy(statics::Filter::new(
479        statics::Map::new(vec((key, value), size.clone()), VecToHashMap),
480        "HashMap minimum size".into(),
481        MinSize(size.start()),
482    ))
483}
484
485mapfn! {
486    [] fn VecToBTreeMap[<K : fmt::Debug + Ord, V : fmt::Debug>]
487        (vec: Vec<(K, V)>) -> BTreeMap<K, V>
488    {
489        vec.into_iter().collect()
490    }
491}
492
493impl<K: Ord, V> statics::FilterFn<BTreeMap<K, V>> for MinSize {
494    fn apply(&self, map: &BTreeMap<K, V>) -> bool {
495        map.len() >= self.0
496    }
497}
498
499opaque_strategy_wrapper! {
500    /// Strategy to create `BTreeMap`s with a length in a certain range.
501    ///
502    /// Created by the `btree_map()` function in the same module.
503    #[derive(Clone, Debug)]
504    pub struct BTreeMapStrategy[<K, V>]
505        [where K : Strategy, V : Strategy, K::Value : Ord](
506            statics::Filter<statics::Map<VecStrategy<(K,V)>,
507            VecToBTreeMap>, MinSize>)
508        -> BTreeMapValueTree<K::Tree, V::Tree>;
509    /// `ValueTree` corresponding to `BTreeMapStrategy`.
510    #[derive(Clone, Debug)]
511    pub struct BTreeMapValueTree[<K, V>]
512        [where K : ValueTree, V : ValueTree, K::Value : Ord](
513            statics::Filter<statics::Map<VecValueTree<TupleValueTree<(K, V)>>,
514            VecToBTreeMap>, MinSize>)
515        -> BTreeMap<K::Value, V::Value>;
516}
517
518/// Create a strategy to generate `BTreeMap`s containing keys and values drawn
519/// from `key` and `value` respectively, and with a size within the given
520/// range.
521///
522/// This strategy will implicitly do local rejects to ensure that the
523/// `BTreeMap` has at least the minimum number of elements, in case `key`
524/// should produce duplicate values.
525pub fn btree_map<K: Strategy, V: Strategy>(
526    key: K,
527    value: V,
528    size: impl Into<SizeRange>,
529) -> BTreeMapStrategy<K, V>
530where
531    K::Value: Ord,
532{
533    let size = size.into();
534    BTreeMapStrategy(statics::Filter::new(
535        statics::Map::new(vec((key, value), size.clone()), VecToBTreeMap),
536        "BTreeMap minimum size".into(),
537        MinSize(size.start()),
538    ))
539}
540
541#[derive(Clone, Copy, Debug)]
542enum Shrink {
543    DeleteElement(usize),
544    ShrinkElement(usize),
545}
546
547/// `ValueTree` corresponding to `VecStrategy`.
548#[derive(Clone, Debug)]
549pub struct VecValueTree<T: ValueTree> {
550    elements: Vec<T>,
551    included_elements: VarBitSet,
552    min_size: usize,
553    shrink: Shrink,
554    prev_shrink: Option<Shrink>,
555}
556
557impl<T: Strategy> Strategy for VecStrategy<T> {
558    type Tree = VecValueTree<T::Tree>;
559    type Value = Vec<T::Value>;
560
561    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
562        let (start, end) = self.size.start_end_incl();
563        let max_size = sample_uniform_incl(runner, start, end);
564        let mut elements = Vec::with_capacity(max_size);
565        while elements.len() < max_size {
566            elements.push(self.element.new_tree(runner)?);
567        }
568
569        Ok(VecValueTree {
570            elements,
571            included_elements: VarBitSet::saturated(max_size),
572            min_size: start,
573            shrink: Shrink::DeleteElement(0),
574            prev_shrink: None,
575        })
576    }
577}
578
579impl<T: Strategy> Strategy for Vec<T> {
580    type Tree = VecValueTree<T::Tree>;
581    type Value = Vec<T::Value>;
582
583    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
584        let len = self.len();
585        let elements = self
586            .iter()
587            .map(|t| t.new_tree(runner))
588            .collect::<Result<Vec<_>, Reason>>()?;
589
590        Ok(VecValueTree {
591            elements,
592            included_elements: VarBitSet::saturated(len),
593            min_size: len,
594            shrink: Shrink::ShrinkElement(0),
595            prev_shrink: None,
596        })
597    }
598}
599
600impl<T: ValueTree> ValueTree for VecValueTree<T> {
601    type Value = Vec<T::Value>;
602
603    fn current(&self) -> Vec<T::Value> {
604        self.elements
605            .iter()
606            .enumerate()
607            .filter(|&(ix, _)| self.included_elements.test(ix))
608            .map(|(_, element)| element.current())
609            .collect()
610    }
611
612    fn simplify(&mut self) -> bool {
613        // The overall strategy here is to iteratively delete elements from the
614        // list until we can do so no further, then to shrink each remaining
615        // element in sequence.
616        //
617        // For `complicate()`, we simply undo the last shrink operation, if
618        // there was any.
619        if let Shrink::DeleteElement(ix) = self.shrink {
620            // Can't delete an element if beyond the end of the vec or if it
621            // would put us under the minimum length.
622            if ix >= self.elements.len()
623                || self.included_elements.count() == self.min_size
624            {
625                self.shrink = Shrink::ShrinkElement(0);
626            } else {
627                self.included_elements.clear(ix);
628                self.prev_shrink = Some(self.shrink);
629                self.shrink = Shrink::DeleteElement(ix + 1);
630                return true;
631            }
632        }
633
634        while let Shrink::ShrinkElement(ix) = self.shrink {
635            if ix >= self.elements.len() {
636                // Nothing more we can do
637                return false;
638            }
639
640            if !self.included_elements.test(ix) {
641                // No use shrinking something we're not including.
642                self.shrink = Shrink::ShrinkElement(ix + 1);
643                continue;
644            }
645
646            if !self.elements[ix].simplify() {
647                // Move on to the next element
648                self.shrink = Shrink::ShrinkElement(ix + 1);
649            } else {
650                self.prev_shrink = Some(self.shrink);
651                return true;
652            }
653        }
654
655        panic!("Unexpected shrink state");
656    }
657
658    fn complicate(&mut self) -> bool {
659        match self.prev_shrink {
660            None => false,
661            Some(Shrink::DeleteElement(ix)) => {
662                // Undo the last item we deleted. Can't complicate any further,
663                // so unset prev_shrink.
664                self.included_elements.set(ix);
665                self.prev_shrink = None;
666                true
667            }
668            Some(Shrink::ShrinkElement(ix)) => {
669                if self.elements[ix].complicate() {
670                    // Don't unset prev_shrink; we may be able to complicate
671                    // again.
672                    true
673                } else {
674                    // Can't complicate the last element any further.
675                    self.prev_shrink = None;
676                    false
677                }
678            }
679        }
680    }
681}
682
683//==============================================================================
684// Tests
685//==============================================================================
686
687#[cfg(test)]
688mod test {
689    use super::*;
690
691    use crate::bits;
692
693    #[test]
694    fn test_vec() {
695        let input = vec(1usize..20usize, 5..20);
696        let mut num_successes = 0;
697
698        let mut runner = TestRunner::deterministic();
699        for _ in 0..256 {
700            let case = input.new_tree(&mut runner).unwrap();
701            let start = case.current();
702            // Has correct length
703            assert!(start.len() >= 5 && start.len() < 20);
704            // Has at least 2 distinct values
705            assert!(start.iter().map(|&v| v).collect::<VarBitSet>().len() >= 2);
706
707            let result = runner.run_one(case, |v| {
708                prop_assert!(
709                    v.iter().map(|&v| v).sum::<usize>() < 9,
710                    "greater than 8"
711                );
712                Ok(())
713            });
714
715            match result {
716                Ok(true) => num_successes += 1,
717                Err(TestError::Fail(_, value)) => {
718                    // The minimal case always has between 5 (due to min
719                    // length) and 9 (min element value = 1) elements, and
720                    // always sums to exactly 9.
721                    assert!(
722                        value.len() >= 5
723                            && value.len() <= 9
724                            && value.iter().map(|&v| v).sum::<usize>() == 9,
725                        "Unexpected minimal value: {:?}",
726                        value
727                    );
728                }
729                e => panic!("Unexpected result: {:?}", e),
730            }
731        }
732
733        assert!(num_successes < 256);
734    }
735
736    #[test]
737    fn test_vec_sanity() {
738        check_strategy_sanity(vec(0i32..1000, 5..10), None);
739    }
740
741    #[test]
742    fn test_parallel_vec() {
743        let input =
744            vec![(1u32..10).boxed(), bits::u32::masked(0xF0u32).boxed()];
745
746        for _ in 0..256 {
747            let mut runner = TestRunner::default();
748            let mut case = input.new_tree(&mut runner).unwrap();
749
750            loop {
751                let current = case.current();
752                assert_eq!(2, current.len());
753                assert!(current[0] >= 1 && current[0] <= 10);
754                assert_eq!(0, (current[1] & !0xF0));
755
756                if !case.simplify() {
757                    break;
758                }
759            }
760        }
761    }
762
763    #[cfg(feature = "std")]
764    #[test]
765    fn test_map() {
766        // Only 8 possible keys
767        let input = hash_map("[ab]{3}", "a", 2..3);
768        let mut runner = TestRunner::deterministic();
769
770        for _ in 0..256 {
771            let v = input.new_tree(&mut runner).unwrap().current();
772            assert_eq!(2, v.len());
773        }
774    }
775
776    #[cfg(feature = "std")]
777    #[test]
778    fn test_set() {
779        // Only 8 possible values
780        let input = hash_set("[ab]{3}", 2..3);
781        let mut runner = TestRunner::deterministic();
782
783        for _ in 0..256 {
784            let v = input.new_tree(&mut runner).unwrap().current();
785            assert_eq!(2, v.len());
786        }
787    }
788}
proptest/collection.rs

proptest/
collection.rs
