diff options
Diffstat (limited to 'vendor/proptest/src/strategy/unions.rs')
| -rw-r--r-- | vendor/proptest/src/strategy/unions.rs | 697 |
1 files changed, 697 insertions, 0 deletions
diff --git a/vendor/proptest/src/strategy/unions.rs b/vendor/proptest/src/strategy/unions.rs new file mode 100644 index 000000000..fb5806297 --- /dev/null +++ b/vendor/proptest/src/strategy/unions.rs @@ -0,0 +1,697 @@ +//- +// Copyright 2017 Jason Lingle +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::std_facade::{fmt, Arc, Vec}; +use core::cmp::{max, min}; +use core::u32; + +#[cfg(not(feature = "std"))] +use num_traits::float::FloatCore; + +use crate::num::sample_uniform; +use crate::strategy::{lazy::LazyValueTree, traits::*}; +use crate::test_runner::*; + +/// A **relative** `weight` of a particular `Strategy` corresponding to `T` +/// coupled with `T` itself. The weight is currently given in `u32`. +pub type W<T> = (u32, T); + +/// A **relative** `weight` of a particular `Strategy` corresponding to `T` +/// coupled with `Arc<T>`. The weight is currently given in `u32`. +pub type WA<T> = (u32, Arc<T>); + +/// A `Strategy` which picks from one of several delegate `Stragegy`s. +/// +/// See `Strategy::prop_union()`. +#[derive(Clone, Debug)] +#[must_use = "strategies do nothing unless used"] +pub struct Union<T: Strategy> { + // In principle T could be any `Strategy + Clone`, but that isn't possible + // for BC reasons with the 0.9 series. + options: Vec<WA<T>>, +} + +impl<T: Strategy> Union<T> { + /// Create a strategy which selects uniformly from the given delegate + /// strategies. + /// + /// When shrinking, after maximal simplification of the chosen element, the + /// strategy will move to earlier options and continue simplification with + /// those. + /// + /// ## Panics + /// + /// Panics if `options` is empty. + pub fn new(options: impl IntoIterator<Item = T>) -> Self { + let options: Vec<WA<T>> = + options.into_iter().map(|v| (1, Arc::new(v))).collect(); + assert!(!options.is_empty()); + Self { options } + } + + pub(crate) fn try_new<E>( + it: impl Iterator<Item = Result<T, E>>, + ) -> Result<Self, E> { + let options: Vec<WA<T>> = it + .map(|r| r.map(|v| (1, Arc::new(v)))) + .collect::<Result<_, _>>()?; + + assert!(!options.is_empty()); + Ok(Self { options }) + } + + /// Create a strategy which selects from the given delegate strategies. + /// + /// Each strategy is assigned a non-zero weight which determines how + /// frequently that strategy is chosen. For example, a strategy with a + /// weight of 2 will be chosen twice as frequently as one with a weight of + /// 1\. + /// + /// ## Panics + /// + /// Panics if `options` is empty or any element has a weight of 0. + /// + /// Panics if the sum of the weights overflows a `u32`. + pub fn new_weighted(options: Vec<W<T>>) -> Self { + assert!(!options.is_empty()); + assert!( + !options.iter().any(|&(w, _)| 0 == w), + "Union option has a weight of 0" + ); + assert!( + options.iter().map(|&(w, _)| u64::from(w)).sum::<u64>() + <= u64::from(u32::MAX), + "Union weights overflow u32" + ); + let options = + options.into_iter().map(|(w, v)| (w, Arc::new(v))).collect(); + Self { options } + } + + /// Add `other` as an additional alternate strategy with weight 1. + pub fn or(mut self, other: T) -> Self { + self.options.push((1, Arc::new(other))); + self + } +} + +fn pick_weighted<I: Iterator<Item = u32>>( + runner: &mut TestRunner, + weights1: I, + weights2: I, +) -> usize { + let sum = weights1.map(u64::from).sum(); + let weighted_pick = sample_uniform(runner, 0, sum); + weights2 + .scan(0u64, |state, w| { + *state += u64::from(w); + Some(*state) + }) + .filter(|&v| v <= weighted_pick) + .count() +} + +impl<T: Strategy> Strategy for Union<T> { + type Tree = UnionValueTree<T>; + type Value = T::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + fn extract_weight<V>(&(w, _): &WA<V>) -> u32 { + w + } + + let pick = pick_weighted( + runner, + self.options.iter().map(extract_weight::<T>), + self.options.iter().map(extract_weight::<T>), + ); + + let mut options = Vec::with_capacity(pick); + + // Delay initialization for all options less than pick. + for option in &self.options[0..pick] { + options.push(LazyValueTree::new(Arc::clone(&option.1), runner)); + } + + // Initialize the tree at pick so at least one value is available. Note + // that if generation for the value at pick fails, the entire strategy + // will fail. This seems like the right call. + options.push(LazyValueTree::new_initialized( + self.options[pick].1.new_tree(runner)?, + )); + + Ok(UnionValueTree { + options, + pick, + min_pick: 0, + prev_pick: None, + }) + } +} + +macro_rules! access_vec { + ([$($muta:tt)*] $dst:ident = $this:expr, $ix:expr, $body:block) => {{ + let $dst = &$($muta)* $this.options[$ix]; + $body + }} +} + +/// `ValueTree` corresponding to `Union`. +pub struct UnionValueTree<T: Strategy> { + options: Vec<LazyValueTree<T>>, + // This struct maintains the invariant that between function calls, + // `pick` and `prev_pick` (if Some) always point to initialized + // trees. + pick: usize, + min_pick: usize, + prev_pick: Option<usize>, +} + +macro_rules! lazy_union_value_tree_body { + ($typ:ty, $access:ident) => { + type Value = $typ; + + fn current(&self) -> Self::Value { + $access!([] opt = self, self.pick, { + opt.as_inner().unwrap_or_else(|| + panic!( + "value tree at self.pick = {} must be initialized", + self.pick, + ) + ).current() + }) + } + + fn simplify(&mut self) -> bool { + let orig_pick = self.pick; + if $access!([mut] opt = self, orig_pick, { + opt.as_inner_mut().unwrap_or_else(|| + panic!( + "value tree at self.pick = {} must be initialized", + orig_pick, + ) + ).simplify() + }) { + self.prev_pick = None; + return true; + } + + assert!( + self.pick >= self.min_pick, + "self.pick = {} should never go below self.min_pick = {}", + self.pick, + self.min_pick, + ); + if self.pick == self.min_pick { + // No more simplification to be done. + return false; + } + + // self.prev_pick is always a valid pick. + self.prev_pick = Some(self.pick); + + let mut next_pick = self.pick; + while next_pick > self.min_pick { + next_pick -= 1; + let initialized = $access!([mut] opt = self, next_pick, { + opt.maybe_init(); + opt.is_initialized() + }); + if initialized { + // next_pick was correctly initialized above. + self.pick = next_pick; + return true; + } + } + + false + } + + fn complicate(&mut self) -> bool { + if let Some(pick) = self.prev_pick { + // simplify() ensures that the previous pick was initialized. + self.pick = pick; + self.min_pick = pick; + self.prev_pick = None; + true + } else { + let pick = self.pick; + $access!([mut] opt = self, pick, { + opt.as_inner_mut().unwrap_or_else(|| + panic!( + "value tree at self.pick = {} must be initialized", + pick, + ) + ).complicate() + }) + } + } + } +} + +impl<T: Strategy> ValueTree for UnionValueTree<T> { + lazy_union_value_tree_body!(T::Value, access_vec); +} + +impl<T: Strategy> Clone for UnionValueTree<T> +where + T::Tree: Clone, +{ + fn clone(&self) -> Self { + Self { + options: self.options.clone(), + pick: self.pick, + min_pick: self.min_pick, + prev_pick: self.prev_pick, + } + } +} + +impl<T: Strategy> fmt::Debug for UnionValueTree<T> +where + T::Tree: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("UnionValueTree") + .field("options", &self.options) + .field("pick", &self.pick) + .field("min_pick", &self.min_pick) + .field("prev_pick", &self.prev_pick) + .finish() + } +} + +macro_rules! def_access_tuple { + ($b:tt $name:ident, $($n:tt)*) => { + macro_rules! $name { + ([$b($b muta:tt)*] $b dst:ident = $b this:expr, + $b ix:expr, $b body:block) => { + match $b ix { + 0 => { + let $b dst = &$b($b muta)* $b this.options.0; + $b body + }, + $( + $n => { + if let Some(ref $b($b muta)* $b dst) = + $b this.options.$n + { + $b body + } else { + panic!("TupleUnion tried to access \ + uninitialised slot {}", $n) + } + }, + )* + _ => panic!("TupleUnion tried to access out-of-range \ + slot {}", $b ix), + } + } + } + } +} + +def_access_tuple!($ access_tuple2, 1); +def_access_tuple!($ access_tuple3, 1 2); +def_access_tuple!($ access_tuple4, 1 2 3); +def_access_tuple!($ access_tuple5, 1 2 3 4); +def_access_tuple!($ access_tuple6, 1 2 3 4 5); +def_access_tuple!($ access_tuple7, 1 2 3 4 5 6); +def_access_tuple!($ access_tuple8, 1 2 3 4 5 6 7); +def_access_tuple!($ access_tuple9, 1 2 3 4 5 6 7 8); +def_access_tuple!($ access_tupleA, 1 2 3 4 5 6 7 8 9); + +/// Similar to `Union`, but internally uses a tuple to hold the strategies. +/// +/// This allows better performance than vanilla `Union` since one does not need +/// to resort to boxing and dynamic dispatch to handle heterogeneous +/// strategies. +/// +/// The difference between this and `TupleUnion` is that with this, value trees +/// for variants that aren't picked at first are generated lazily. +#[must_use = "strategies do nothing unless used"] +#[derive(Clone, Copy, Debug)] +pub struct TupleUnion<T>(T); + +impl<T> TupleUnion<T> { + /// Wrap `tuple` in a `TupleUnion`. + /// + /// The struct definition allows any `T` for `tuple`, but to be useful, it + /// must be a 2- to 10-tuple of `(u32, Arc<impl Strategy>)` pairs where all + /// strategies ultimately produce the same value. Each `u32` indicates the + /// relative weight of its corresponding strategy. + /// You may use `WA<S>` as an alias for `(u32, Arc<S>)`. + /// + /// Using this constructor directly is discouraged; prefer to use + /// `prop_oneof!` since it is generally clearer. + pub fn new(tuple: T) -> Self { + TupleUnion(tuple) + } +} + +macro_rules! tuple_union { + ($($gen:ident $ix:tt)*) => { + impl<A : Strategy, $($gen: Strategy<Value = A::Value>),*> + Strategy for TupleUnion<(WA<A>, $(WA<$gen>),*)> { + type Tree = TupleUnionValueTree< + (LazyValueTree<A>, $(Option<LazyValueTree<$gen>>),*)>; + type Value = A::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + let weights = [((self.0).0).0, $(((self.0).$ix).0),*]; + let pick = pick_weighted(runner, weights.iter().cloned(), + weights.iter().cloned()); + + Ok(TupleUnionValueTree { + options: ( + if 0 == pick { + LazyValueTree::new_initialized( + ((self.0).0).1.new_tree(runner)?) + } else { + LazyValueTree::new( + Arc::clone(&((self.0).0).1), runner) + }, + $( + if $ix == pick { + Some(LazyValueTree::new_initialized( + ((self.0).$ix).1.new_tree(runner)?)) + } else if $ix < pick { + Some(LazyValueTree::new( + Arc::clone(&((self.0).$ix).1), runner)) + } else { + None + }),*), + pick: pick, + min_pick: 0, + prev_pick: None, + }) + } + } + } +} + +tuple_union!(B 1); +tuple_union!(B 1 C 2); +tuple_union!(B 1 C 2 D 3); +tuple_union!(B 1 C 2 D 3 E 4); +tuple_union!(B 1 C 2 D 3 E 4 F 5); +tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6); +tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7); +tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8); +tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9); + +/// `ValueTree` type produced by `TupleUnion`. +#[derive(Clone, Copy, Debug)] +pub struct TupleUnionValueTree<T> { + options: T, + pick: usize, + min_pick: usize, + prev_pick: Option<usize>, +} + +macro_rules! value_tree_tuple { + ($access:ident, $($gen:ident)*) => { + impl<A : Strategy, $($gen: Strategy<Value = A::Value>),*> ValueTree + for TupleUnionValueTree< + (LazyValueTree<A>, $(Option<LazyValueTree<$gen>>),*) + > { + lazy_union_value_tree_body!(A::Value, $access); + } + } +} + +value_tree_tuple!(access_tuple2, B); +value_tree_tuple!(access_tuple3, B C); +value_tree_tuple!(access_tuple4, B C D); +value_tree_tuple!(access_tuple5, B C D E); +value_tree_tuple!(access_tuple6, B C D E F); +value_tree_tuple!(access_tuple7, B C D E F G); +value_tree_tuple!(access_tuple8, B C D E F G H); +value_tree_tuple!(access_tuple9, B C D E F G H I); +value_tree_tuple!(access_tupleA, B C D E F G H I J); + +const WEIGHT_BASE: u32 = 0x8000_0000; + +/// Convert a floating-point weight in the range (0.0,1.0) to a pair of weights +/// that can be used with `Union` and similar. +/// +/// The first return value is the weight corresponding to `f`; the second +/// return value is the weight corresponding to `1.0 - f`. +/// +/// This call does not make any guarantees as to what range of weights it may +/// produce, except that adding the two return values will never overflow a +/// `u32`. As such, it is generally not meaningful to combine any other weights +/// with the two returned. +/// +/// ## Panics +/// +/// Panics if `f` is not a real number between 0.0 and 1.0, both exclusive. +pub fn float_to_weight(f: f64) -> (u32, u32) { + assert!(f > 0.0 && f < 1.0, "Invalid probability: {}", f); + + // Clamp to 1..WEIGHT_BASE-1 so that we never produce a weight of 0. + let pos = max( + 1, + min(WEIGHT_BASE - 1, (f * f64::from(WEIGHT_BASE)).round() as u32), + ); + let neg = WEIGHT_BASE - pos; + + (pos, neg) +} + +#[cfg(test)] +mod test { + use super::*; + use crate::strategy::just::Just; + + // FIXME(2018-06-01): figure out a way to run this test on no_std. + // The problem is that the default seed is fixed and does not produce + // enough passed tests. We need some universal source of non-determinism + // for the seed, which is unlikely. + #[cfg(feature = "std")] + #[test] + fn test_union() { + let input = (10u32..20u32).prop_union(30u32..40u32); + // Expect that 25% of cases pass (left input happens to be < 15, and + // left is chosen as initial value). Of the 75% that fail, 50% should + // converge to 15 and 50% to 30 (the latter because the left is beneath + // the passing threshold). + let mut passed = 0; + let mut converged_low = 0; + let mut converged_high = 0; + let mut runner = TestRunner::deterministic(); + for _ in 0..256 { + let case = input.new_tree(&mut runner).unwrap(); + let result = runner.run_one(case, |v| { + prop_assert!(v < 15); + Ok(()) + }); + + match result { + Ok(true) => passed += 1, + Err(TestError::Fail(_, 15)) => converged_low += 1, + Err(TestError::Fail(_, 30)) => converged_high += 1, + e => panic!("Unexpected result: {:?}", e), + } + } + + assert!(passed >= 32 && passed <= 96, "Bad passed count: {}", passed); + assert!( + converged_low >= 32 && converged_low <= 160, + "Bad converged_low count: {}", + converged_low + ); + assert!( + converged_high >= 32 && converged_high <= 160, + "Bad converged_high count: {}", + converged_high + ); + } + + #[test] + fn test_union_weighted() { + let input = Union::new_weighted(vec![ + (1, Just(0usize)), + (2, Just(1usize)), + (1, Just(2usize)), + ]); + + let mut counts = [0, 0, 0]; + let mut runner = TestRunner::deterministic(); + for _ in 0..65536 { + counts[input.new_tree(&mut runner).unwrap().current()] += 1; + } + + println!("{:?}", counts); + assert!(counts[0] > 0); + assert!(counts[2] > 0); + assert!(counts[1] > counts[0] * 3 / 2); + assert!(counts[1] > counts[2] * 3 / 2); + } + + #[test] + fn test_union_sanity() { + check_strategy_sanity( + Union::new_weighted(vec![ + (1, 0i32..100), + (2, 200i32..300), + (1, 400i32..500), + ]), + None, + ); + } + + // FIXME(2018-06-01): See note on `test_union`. + #[cfg(feature = "std")] + #[test] + fn test_tuple_union() { + let input = TupleUnion::new(( + (1, Arc::new(10u32..20u32)), + (1, Arc::new(30u32..40u32)), + )); + // Expect that 25% of cases pass (left input happens to be < 15, and + // left is chosen as initial value). Of the 75% that fail, 50% should + // converge to 15 and 50% to 30 (the latter because the left is beneath + // the passing threshold). + let mut passed = 0; + let mut converged_low = 0; + let mut converged_high = 0; + let mut runner = TestRunner::deterministic(); + for _ in 0..256 { + let case = input.new_tree(&mut runner).unwrap(); + let result = runner.run_one(case, |v| { + prop_assert!(v < 15); + Ok(()) + }); + + match result { + Ok(true) => passed += 1, + Err(TestError::Fail(_, 15)) => converged_low += 1, + Err(TestError::Fail(_, 30)) => converged_high += 1, + e => panic!("Unexpected result: {:?}", e), + } + } + + assert!(passed >= 32 && passed <= 96, "Bad passed count: {}", passed); + assert!( + converged_low >= 32 && converged_low <= 160, + "Bad converged_low count: {}", + converged_low + ); + assert!( + converged_high >= 32 && converged_high <= 160, + "Bad converged_high count: {}", + converged_high + ); + } + + #[test] + fn test_tuple_union_weighting() { + let input = TupleUnion::new(( + (1, Arc::new(Just(0usize))), + (2, Arc::new(Just(1usize))), + (1, Arc::new(Just(2usize))), + )); + + let mut counts = [0, 0, 0]; + let mut runner = TestRunner::deterministic(); + for _ in 0..65536 { + counts[input.new_tree(&mut runner).unwrap().current()] += 1; + } + + println!("{:?}", counts); + assert!(counts[0] > 0); + assert!(counts[2] > 0); + assert!(counts[1] > counts[0] * 3 / 2); + assert!(counts[1] > counts[2] * 3 / 2); + } + + #[test] + fn test_tuple_union_all_sizes() { + let mut runner = TestRunner::deterministic(); + let r = Arc::new(1i32..10); + + macro_rules! test { + ($($part:expr),*) => {{ + let input = TupleUnion::new(( + $((1, $part.clone())),*, + (1, Arc::new(Just(0i32))) + )); + + let mut pass = false; + for _ in 0..1024 { + if 0 == input.new_tree(&mut runner).unwrap().current() { + pass = true; + break; + } + } + + assert!(pass); + }} + } + + test!(r); // 2 + test!(r, r); // 3 + test!(r, r, r); // 4 + test!(r, r, r, r); // 5 + test!(r, r, r, r, r); // 6 + test!(r, r, r, r, r, r); // 7 + test!(r, r, r, r, r, r, r); // 8 + test!(r, r, r, r, r, r, r, r); // 9 + test!(r, r, r, r, r, r, r, r, r); // 10 + } + + #[test] + fn test_tuple_union_sanity() { + check_strategy_sanity( + TupleUnion::new(( + (1, Arc::new(0i32..100i32)), + (1, Arc::new(200i32..1000i32)), + (1, Arc::new(2000i32..3000i32)), + )), + None, + ); + } + + /// Test that unions work even if local filtering causes errors. + #[test] + fn test_filter_union_sanity() { + let filter_strategy = (0u32..256).prop_filter("!%5", |&v| 0 != v % 5); + check_strategy_sanity( + Union::new(vec![filter_strategy; 8]), + Some(filter_sanity_options()), + ); + } + + /// Test that tuple unions work even if local filtering causes errors. + #[test] + fn test_filter_tuple_union_sanity() { + let filter_strategy = (0u32..256).prop_filter("!%5", |&v| 0 != v % 5); + check_strategy_sanity( + TupleUnion::new(( + (1, Arc::new(filter_strategy.clone())), + (1, Arc::new(filter_strategy.clone())), + (1, Arc::new(filter_strategy.clone())), + (1, Arc::new(filter_strategy.clone())), + )), + Some(filter_sanity_options()), + ); + } + + fn filter_sanity_options() -> CheckStrategySanityOptions { + CheckStrategySanityOptions { + // Due to internal rejection sampling, `simplify()` can + // converge back to what `complicate()` would do. + strict_complicate_after_simplify: false, + // Make failed filters return errors to test edge cases. + error_on_local_rejects: true, + ..CheckStrategySanityOptions::default() + } + } +} |