diff options
Diffstat (limited to 'vendor/proptest/src/strategy')
| -rw-r--r-- | vendor/proptest/src/strategy/filter.rs | 147 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/filter_map.rs | 209 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/flatten.rs | 359 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/fuse.rs | 228 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/just.rs | 145 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/lazy.rs | 175 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/map.rs | 301 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/mod.rs | 37 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/recursive.rs | 209 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/shuffle.rs | 287 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/statics.rs | 266 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/traits.rs | 1054 | ||||
| -rw-r--r-- | vendor/proptest/src/strategy/unions.rs | 697 |
13 files changed, 4114 insertions, 0 deletions
diff --git a/vendor/proptest/src/strategy/filter.rs b/vendor/proptest/src/strategy/filter.rs new file mode 100644 index 000000000..029dbcebc --- /dev/null +++ b/vendor/proptest/src/strategy/filter.rs @@ -0,0 +1,147 @@ +//- +// 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}; + +use crate::strategy::traits::*; +use crate::test_runner::*; + +/// `Strategy` and `ValueTree` filter adaptor. +/// +/// See `Strategy::prop_filter()`. +#[must_use = "strategies do nothing unless used"] +pub struct Filter<S, F> { + pub(super) source: S, + pub(super) whence: Reason, + pub(super) fun: Arc<F>, +} + +impl<S, F> Filter<S, F> { + pub(super) fn new(source: S, whence: Reason, fun: F) -> Self { + Self { + source, + whence, + fun: Arc::new(fun), + } + } +} + +impl<S: fmt::Debug, F> fmt::Debug for Filter<S, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("Filter") + .field("source", &self.source) + .field("whence", &self.whence) + .field("fun", &"<function>") + .finish() + } +} + +impl<S: Clone, F> Clone for Filter<S, F> { + fn clone(&self) -> Self { + Filter { + source: self.source.clone(), + whence: "unused".into(), + fun: Arc::clone(&self.fun), + } + } +} + +impl<S: Strategy, F: Fn(&S::Value) -> bool> Strategy for Filter<S, F> { + type Tree = Filter<S::Tree, F>; + type Value = S::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + loop { + let val = self.source.new_tree(runner)?; + if !(self.fun)(&val.current()) { + runner.reject_local(self.whence.clone())?; + } else { + return Ok(Filter { + source: val, + whence: self.whence.clone(), + fun: Arc::clone(&self.fun), + }); + } + } + } +} + +impl<S: ValueTree, F: Fn(&S::Value) -> bool> Filter<S, F> { + fn ensure_acceptable(&mut self) { + while !(self.fun)(&self.source.current()) { + if !self.source.complicate() { + panic!( + "Unable to complicate filtered strategy \ + back into acceptable value" + ); + } + } + } +} + +impl<S: ValueTree, F: Fn(&S::Value) -> bool> ValueTree for Filter<S, F> { + type Value = S::Value; + + fn current(&self) -> S::Value { + self.source.current() + } + + fn simplify(&mut self) -> bool { + if self.source.simplify() { + self.ensure_acceptable(); + true + } else { + false + } + } + + fn complicate(&mut self) -> bool { + if self.source.complicate() { + self.ensure_acceptable(); + true + } else { + false + } + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn test_filter() { + let input = (0..256).prop_filter("%3", |&v| 0 == v % 3); + + for _ in 0..256 { + let mut runner = TestRunner::default(); + let mut case = input.new_tree(&mut runner).unwrap(); + + assert!(0 == case.current() % 3); + + while case.simplify() { + assert!(0 == case.current() % 3); + } + assert!(0 == case.current() % 3); + } + } + + #[test] + fn test_filter_sanity() { + check_strategy_sanity( + (0..256).prop_filter("!%5", |&v| 0 != v % 5), + Some(CheckStrategySanityOptions { + // Due to internal rejection sampling, `simplify()` can + // converge back to what `complicate()` would do. + strict_complicate_after_simplify: false, + ..CheckStrategySanityOptions::default() + }), + ); + } +} diff --git a/vendor/proptest/src/strategy/filter_map.rs b/vendor/proptest/src/strategy/filter_map.rs new file mode 100644 index 000000000..52f901276 --- /dev/null +++ b/vendor/proptest/src/strategy/filter_map.rs @@ -0,0 +1,209 @@ +//- +// 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, Cell}; + +use crate::strategy::traits::*; +use crate::test_runner::*; + +/// `Strategy` and `ValueTree` filter_map adaptor. +/// +/// See `Strategy::prop_filter_map()`. +#[must_use = "strategies do nothing unless used"] +pub struct FilterMap<S, F> { + pub(super) source: S, + pub(super) whence: Reason, + pub(super) fun: Arc<F>, +} + +impl<S, F> FilterMap<S, F> { + pub(super) fn new(source: S, whence: Reason, fun: F) -> Self { + Self { + source, + whence, + fun: Arc::new(fun), + } + } +} + +impl<S: fmt::Debug, F> fmt::Debug for FilterMap<S, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("FilterMap") + .field("source", &self.source) + .field("whence", &self.whence) + .field("fun", &"<function>") + .finish() + } +} + +impl<S: Clone, F> Clone for FilterMap<S, F> { + fn clone(&self) -> Self { + Self { + source: self.source.clone(), + whence: self.whence.clone(), + fun: Arc::clone(&self.fun), + } + } +} + +impl<S: Strategy, F: Fn(S::Value) -> Option<O>, O: fmt::Debug> Strategy + for FilterMap<S, F> +{ + type Tree = FilterMapValueTree<S::Tree, F, O>; + type Value = O; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + loop { + let val = self.source.new_tree(runner)?; + if let Some(current) = (self.fun)(val.current()) { + return Ok(FilterMapValueTree::new(val, &self.fun, current)); + } else { + runner.reject_local(self.whence.clone())?; + } + } + } +} + +/// `ValueTree` corresponding to `FilterMap`. +pub struct FilterMapValueTree<V, F, O> { + source: V, + current: Cell<Option<O>>, + fun: Arc<F>, +} + +impl<V: Clone + ValueTree, F: Fn(V::Value) -> Option<O>, O> Clone + for FilterMapValueTree<V, F, O> +{ + fn clone(&self) -> Self { + Self::new(self.source.clone(), &self.fun, self.fresh_current()) + } +} + +impl<V: fmt::Debug, F, O> fmt::Debug for FilterMapValueTree<V, F, O> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("FilterMapValueTree") + .field("source", &self.source) + .field("current", &"<current>") + .field("fun", &"<function>") + .finish() + } +} + +impl<V: ValueTree, F: Fn(V::Value) -> Option<O>, O> + FilterMapValueTree<V, F, O> +{ + fn new(source: V, fun: &Arc<F>, current: O) -> Self { + Self { + source, + current: Cell::new(Some(current)), + fun: Arc::clone(fun), + } + } + + fn fresh_current(&self) -> O { + (self.fun)(self.source.current()) + .expect("internal logic error; this is a bug!") + } + + fn ensure_acceptable(&mut self) { + loop { + if let Some(current) = (self.fun)(self.source.current()) { + // Found an acceptable element! + self.current = Cell::new(Some(current)); + break; + } else if !self.source.complicate() { + panic!( + "Unable to complicate filtered strategy \ + back into acceptable value" + ); + } + } + } +} + +impl<V: ValueTree, F: Fn(V::Value) -> Option<O>, O: fmt::Debug> ValueTree + for FilterMapValueTree<V, F, O> +{ + type Value = O; + + fn current(&self) -> O { + // Optimization: we avoid the else branch in most success cases + // thereby avoiding to call the closure and the source tree. + if let Some(current) = self.current.replace(None) { + current + } else { + self.fresh_current() + } + } + + fn simplify(&mut self) -> bool { + if self.source.simplify() { + self.ensure_acceptable(); + true + } else { + false + } + } + + fn complicate(&mut self) -> bool { + if self.source.complicate() { + self.ensure_acceptable(); + true + } else { + false + } + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn test_filter_map() { + let input = (0..256).prop_filter_map("%3 + 1", |v| { + if 0 == v % 3 { + Some(v + 1) + } else { + None + } + }); + + for _ in 0..256 { + let mut runner = TestRunner::default(); + let mut case = input.new_tree(&mut runner).unwrap(); + + assert_eq!(0, (case.current() - 1) % 3); + + while case.simplify() { + assert_eq!(0, (case.current() - 1) % 3); + } + assert_eq!(0, (case.current() - 1) % 3); + } + } + + #[test] + fn test_filter_map_sanity() { + check_strategy_sanity( + (0..256).prop_filter_map("!%5 * 2", |v| { + if 0 != v % 5 { + Some(v * 2) + } else { + None + } + }), + Some(CheckStrategySanityOptions { + // Due to internal rejection sampling, `simplify()` can + // converge back to what `complicate()` would do. + strict_complicate_after_simplify: false, + ..CheckStrategySanityOptions::default() + }), + ); + } +} diff --git a/vendor/proptest/src/strategy/flatten.rs b/vendor/proptest/src/strategy/flatten.rs new file mode 100644 index 000000000..63ac41604 --- /dev/null +++ b/vendor/proptest/src/strategy/flatten.rs @@ -0,0 +1,359 @@ +//- +// 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}; +use core::mem; + +use crate::strategy::fuse::Fuse; +use crate::strategy::traits::*; +use crate::test_runner::*; + +/// Adaptor that flattens a `Strategy` which produces other `Strategy`s into a +/// `Strategy` that picks one of those strategies and then picks values from +/// it. +#[derive(Debug, Clone, Copy)] +#[must_use = "strategies do nothing unless used"] +pub struct Flatten<S> { + source: S, +} + +impl<S: Strategy> Flatten<S> { + /// Wrap `source` to flatten it. + pub fn new(source: S) -> Self { + Flatten { source } + } +} + +impl<S: Strategy> Strategy for Flatten<S> +where + S::Value: Strategy, +{ + type Tree = FlattenValueTree<S::Tree>; + type Value = <S::Value as Strategy>::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + let meta = self.source.new_tree(runner)?; + FlattenValueTree::new(runner, meta) + } +} + +/// The `ValueTree` produced by `Flatten`. +pub struct FlattenValueTree<S: ValueTree> +where + S::Value: Strategy, +{ + meta: Fuse<S>, + current: Fuse<<S::Value as Strategy>::Tree>, + // The final value to produce after successive calls to complicate() on the + // underlying objects return false. + final_complication: Option<Fuse<<S::Value as Strategy>::Tree>>, + // When `simplify()` or `complicate()` causes a new `Strategy` to be + // chosen, we need to find a new failing input for that case. To do this, + // we implement `complicate()` by regenerating values up to a number of + // times corresponding to the maximum number of test cases. A `simplify()` + // which does not cause a new strategy to be chosen always resets + // `complicate_regen_remaining` to 0. + // + // This does unfortunately depart from the direct interpretation of + // simplify/complicate as binary search, but is still easier to think about + // than other implementations of higher-order strategies. + runner: TestRunner, + complicate_regen_remaining: u32, +} + +impl<S: ValueTree> Clone for FlattenValueTree<S> +where + S::Value: Strategy + Clone, + S: Clone, + <S::Value as Strategy>::Tree: Clone, +{ + fn clone(&self) -> Self { + FlattenValueTree { + meta: self.meta.clone(), + current: self.current.clone(), + final_complication: self.final_complication.clone(), + runner: self.runner.clone(), + complicate_regen_remaining: self.complicate_regen_remaining, + } + } +} + +impl<S: ValueTree> fmt::Debug for FlattenValueTree<S> +where + S::Value: Strategy, + S: fmt::Debug, + <S::Value as Strategy>::Tree: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("FlattenValueTree") + .field("meta", &self.meta) + .field("current", &self.current) + .field("final_complication", &self.final_complication) + .field( + "complicate_regen_remaining", + &self.complicate_regen_remaining, + ) + .finish() + } +} + +impl<S: ValueTree> FlattenValueTree<S> +where + S::Value: Strategy, +{ + fn new(runner: &mut TestRunner, meta: S) -> Result<Self, Reason> { + let current = meta.current().new_tree(runner)?; + Ok(FlattenValueTree { + meta: Fuse::new(meta), + current: Fuse::new(current), + final_complication: None, + runner: runner.partial_clone(), + complicate_regen_remaining: 0, + }) + } +} + +impl<S: ValueTree> ValueTree for FlattenValueTree<S> +where + S::Value: Strategy, +{ + type Value = <S::Value as Strategy>::Value; + + fn current(&self) -> Self::Value { + self.current.current() + } + + fn simplify(&mut self) -> bool { + self.complicate_regen_remaining = 0; + + if self.current.simplify() { + // Now that we've simplified the derivative value, we can't + // re-complicate the meta value unless it gets simplified again. + // We also mustn't complicate back to whatever's in + // `final_complication` since the new state of `self.current` is + // the most complicated state. + self.meta.disallow_complicate(); + self.final_complication = None; + true + } else if !self.meta.simplify() { + false + } else if let Ok(v) = self.meta.current().new_tree(&mut self.runner) { + // Shift current into final_complication and `v` into + // `current`. We also need to prevent that value from + // complicating beyond the current point in the future + // since we're going to return `true` from `simplify()` + // ourselves. + self.current.disallow_complicate(); + self.final_complication = Some(Fuse::new(v)); + mem::swap( + self.final_complication.as_mut().unwrap(), + &mut self.current, + ); + // Initially complicate by regenerating the chosen value. + self.complicate_regen_remaining = self.runner.config().cases; + true + } else { + false + } + } + + fn complicate(&mut self) -> bool { + if self.complicate_regen_remaining > 0 { + if self.runner.flat_map_regen() { + self.complicate_regen_remaining -= 1; + + if let Ok(v) = self.meta.current().new_tree(&mut self.runner) { + self.current = Fuse::new(v); + return true; + } + } else { + self.complicate_regen_remaining = 0; + } + } + + if self.current.complicate() { + return true; + } else if self.meta.complicate() { + if let Ok(v) = self.meta.current().new_tree(&mut self.runner) { + self.complicate_regen_remaining = self.runner.config().cases; + self.current = Fuse::new(v); + return true; + } + } + + if let Some(v) = self.final_complication.take() { + self.current = v; + true + } else { + false + } + } +} + +/// Similar to `Flatten`, but does not shrink the input strategy. +/// +/// See `Strategy::prop_ind_flat_map()` fore more details. +#[derive(Clone, Copy, Debug)] +pub struct IndFlatten<S>(pub(super) S); + +impl<S: Strategy> Strategy for IndFlatten<S> +where + S::Value: Strategy, +{ + type Tree = <S::Value as Strategy>::Tree; + type Value = <S::Value as Strategy>::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + let inner = self.0.new_tree(runner)?; + inner.current().new_tree(runner) + } +} + +/// Similar to `Map` plus `Flatten`, but does not shrink the input strategy and +/// passes the original input through. +/// +/// See `Strategy::prop_ind_flat_map2()` for more details. +pub struct IndFlattenMap<S, F> { + pub(super) source: S, + pub(super) fun: Arc<F>, +} + +impl<S: fmt::Debug, F> fmt::Debug for IndFlattenMap<S, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("IndFlattenMap") + .field("source", &self.source) + .field("fun", &"<function>") + .finish() + } +} + +impl<S: Clone, F> Clone for IndFlattenMap<S, F> { + fn clone(&self) -> Self { + IndFlattenMap { + source: self.source.clone(), + fun: Arc::clone(&self.fun), + } + } +} + +impl<S: Strategy, R: Strategy, F: Fn(S::Value) -> R> Strategy + for IndFlattenMap<S, F> +{ + type Tree = crate::tuple::TupleValueTree<(S::Tree, R::Tree)>; + type Value = (S::Value, R::Value); + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + let left = self.source.new_tree(runner)?; + let right_source = (self.fun)(left.current()); + let right = right_source.new_tree(runner)?; + + Ok(crate::tuple::TupleValueTree::new((left, right))) + } +} + +#[cfg(test)] +mod test { + use super::*; + + use std::u32; + + use crate::strategy::just::Just; + use crate::test_runner::Config; + + #[test] + fn test_flat_map() { + // Pick random integer A, then random integer B which is ±5 of A and + // assert that B <= A if A > 10000. Shrinking should always converge to + // A=10001, B=10002. + let input = (0..65536).prop_flat_map(|a| (Just(a), (a - 5..a + 5))); + + let mut failures = 0; + let mut runner = TestRunner::new_with_rng( + Config { + max_shrink_iters: u32::MAX - 1, + ..Config::default() + }, + TestRng::deterministic_rng(RngAlgorithm::default()), + ); + for _ in 0..1000 { + let case = input.new_tree(&mut runner).unwrap(); + let result = runner.run_one(case, |(a, b)| { + if a <= 10000 || b <= a { + Ok(()) + } else { + Err(TestCaseError::fail("fail")) + } + }); + + match result { + Ok(_) => {} + Err(TestError::Fail(_, v)) => { + failures += 1; + assert_eq!((10001, 10002), v); + } + result => panic!("Unexpected result: {:?}", result), + } + } + + assert!(failures > 250); + } + + #[test] + fn test_flat_map_sanity() { + check_strategy_sanity( + (0..65536).prop_flat_map(|a| (Just(a), (a - 5..a + 5))), + None, + ); + } + + #[test] + fn flat_map_respects_regen_limit() { + use std::sync::atomic::{AtomicBool, Ordering}; + + let input = (0..65536) + .prop_flat_map(|_| 0..65536) + .prop_flat_map(|_| 0..65536) + .prop_flat_map(|_| 0..65536) + .prop_flat_map(|_| 0..65536) + .prop_flat_map(|_| 0..65536); + + // Arteficially make the first case fail and all others pass, so that + // the regeneration logic futilely searches for another failing + // example and eventually gives up. Unfortunately, the test is sort of + // semi-decidable; if the limit *doesn't* work, the test just runs + // almost forever. + let pass = AtomicBool::new(false); + let mut runner = TestRunner::new(Config { + max_flat_map_regens: 1000, + ..Config::default() + }); + let case = input.new_tree(&mut runner).unwrap(); + let _ = runner.run_one(case, |_| { + // Only the first run fails, all others succeed + prop_assert!(pass.fetch_or(true, Ordering::SeqCst)); + Ok(()) + }); + } + + #[test] + fn test_ind_flat_map_sanity() { + check_strategy_sanity( + (0..65536).prop_ind_flat_map(|a| (Just(a), (a - 5..a + 5))), + None, + ); + } + + #[test] + fn test_ind_flat_map2_sanity() { + check_strategy_sanity( + (0..65536).prop_ind_flat_map2(|a| a - 5..a + 5), + None, + ); + } +} diff --git a/vendor/proptest/src/strategy/fuse.rs b/vendor/proptest/src/strategy/fuse.rs new file mode 100644 index 000000000..5c0f9a374 --- /dev/null +++ b/vendor/proptest/src/strategy/fuse.rs @@ -0,0 +1,228 @@ +//- +// 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::strategy::*; +use crate::test_runner::*; + +/// Adaptor for `Strategy` and `ValueTree` which guards `simplify()` and +/// `complicate()` to avoid contract violations. +/// +/// This can be used as an intermediate when the caller would otherwise need +/// its own separate state tracking, or as a workaround for a broken +/// `ValueTree` implementation. +/// +/// This wrapper specifically has the following effects: +/// +/// - Calling `complicate()` before `simplify()` was ever called does nothing +/// and returns `false`. +/// +/// - Calling `simplify()` after it has returned `false` and no calls to +/// `complicate()` returned `true` does nothing and returns `false`. +/// +/// - Calling `complicate()` after it has returned `false` and no calls to +/// `simplify()` returned `true` does nothing and returns `false`. +/// +/// There is also limited functionality to alter the internal state to assist +/// in its usage as a state tracker. +/// +/// Wrapping a `Strategy` in `Fuse` simply causes its `ValueTree` to also be +/// wrapped in `Fuse`. +/// +/// While this is similar to `std::iter::Fuse`, it is not exposed as a method +/// on `Strategy` since the vast majority of proptest should never need this +/// functionality; it mainly concerns implementors of strategies. +#[derive(Debug, Clone, Copy)] +#[must_use = "strategies do nothing unless used"] +pub struct Fuse<T> { + inner: T, + may_simplify: bool, + may_complicate: bool, +} + +impl<T> Fuse<T> { + /// Wrap the given `T` in `Fuse`. + pub fn new(inner: T) -> Self { + Fuse { + inner, + may_simplify: true, + may_complicate: false, + } + } +} + +impl<T: Strategy> Strategy for Fuse<T> { + type Tree = Fuse<T::Tree>; + type Value = T::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + self.inner.new_tree(runner).map(Fuse::new) + } +} + +impl<T: ValueTree> Fuse<T> { + /// Return whether a call to `simplify()` may be productive. + /// + /// Formally, this is true if one of the following holds: + /// + /// - `simplify()` has never been called. + /// - The most recent call to `simplify()` returned `true`. + /// - `complicate()` has been called more recently than `simplify()` and + /// the last call returned `true`. + pub fn may_simplify(&self) -> bool { + self.may_simplify + } + + /// Disallow any further calls to `simplify()` until a call to + /// `complicate()` returns `true`. + pub fn disallow_simplify(&mut self) { + self.may_simplify = false; + } + + /// Return whether a call to `complicate()` may be productive. + /// + /// Formally, this is true if one of the following holds: + /// + /// - The most recent call to `complicate()` returned `true`. + /// - `simplify()` has been called more recently than `complicate()` and + /// the last call returned `true`. + pub fn may_complicate(&self) -> bool { + self.may_complicate + } + + /// Disallow any further calls to `complicate()` until a call to + /// `simplify()` returns `true`. + pub fn disallow_complicate(&mut self) { + self.may_complicate = false; + } + + /// Prevent any further shrinking operations from occurring. + pub fn freeze(&mut self) { + self.disallow_simplify(); + self.disallow_complicate(); + } +} + +impl<T: ValueTree> ValueTree for Fuse<T> { + type Value = T::Value; + + fn current(&self) -> T::Value { + self.inner.current() + } + + fn simplify(&mut self) -> bool { + if self.may_simplify { + if self.inner.simplify() { + self.may_complicate = true; + true + } else { + self.may_simplify = false; + false + } + } else { + false + } + } + + fn complicate(&mut self) -> bool { + if self.may_complicate { + if self.inner.complicate() { + self.may_simplify = true; + true + } else { + self.may_complicate = false; + false + } + } else { + false + } + } +} + +#[cfg(test)] +mod test { + use super::*; + + struct StrictValueTree { + min: u32, + curr: u32, + max: u32, + ready: bool, + } + + impl StrictValueTree { + fn new(start: u32) -> Self { + StrictValueTree { + min: 0, + curr: start, + max: start, + ready: false, + } + } + } + + impl ValueTree for StrictValueTree { + type Value = u32; + + fn current(&self) -> u32 { + self.curr + } + + fn simplify(&mut self) -> bool { + assert!(self.min <= self.curr); + if self.curr > self.min { + self.max = self.curr; + self.curr -= 1; + self.ready = true; + true + } else { + self.min += 1; + false + } + } + + fn complicate(&mut self) -> bool { + assert!(self.max >= self.curr); + assert!(self.ready); + if self.curr < self.max { + self.curr += 1; + true + } else { + self.max -= 1; + false + } + } + } + + #[test] + fn test_sanity() { + check_strategy_sanity(Fuse::new(0i32..100i32), None); + } + + #[test] + fn guards_bad_transitions() { + let mut vt = Fuse::new(StrictValueTree::new(5)); + assert!(!vt.complicate()); + assert_eq!(5, vt.current()); + + assert!(vt.simplify()); // 0, 4, 5 + assert!(vt.simplify()); // 0, 3, 4 + assert!(vt.simplify()); // 0, 2, 3 + assert!(vt.simplify()); // 0, 1, 2 + assert!(vt.simplify()); // 0, 0, 1 + assert_eq!(0, vt.current()); + assert!(!vt.simplify()); // 1, 0, 1 + assert!(!vt.simplify()); // 1, 0, 1 + assert_eq!(0, vt.current()); + assert!(vt.complicate()); // 1, 1, 1 + assert_eq!(1, vt.current()); + assert!(!vt.complicate()); // 1, 1, 0 + assert!(!vt.complicate()); // 1, 1, 0 + assert_eq!(1, vt.current()); + } +} diff --git a/vendor/proptest/src/strategy/just.rs b/vendor/proptest/src/strategy/just.rs new file mode 100644 index 000000000..a141f8a17 --- /dev/null +++ b/vendor/proptest/src/strategy/just.rs @@ -0,0 +1,145 @@ +//- +// Copyright 2017, 2018 The proptest developers +// +// 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; + +use crate::strategy::{NewTree, Strategy, ValueTree}; +use crate::test_runner::TestRunner; + +macro_rules! noshrink { + () => { + fn simplify(&mut self) -> bool { + false + } + fn complicate(&mut self) -> bool { + false + } + }; +} + +//============================================================================== +// Just +//============================================================================== + +/// A `Strategy` which always produces a single value value and never +/// simplifies. +#[derive(Clone, Copy, Debug)] +#[must_use = "strategies do nothing unless used"] +pub struct Just<T: Clone + fmt::Debug>( + /// The value produced by this strategy. + pub T, +); + +impl<T: Clone + fmt::Debug> Strategy for Just<T> { + type Tree = Self; + type Value = T; + + fn new_tree(&self, _: &mut TestRunner) -> NewTree<Self> { + Ok(self.clone()) + } +} + +impl<T: Clone + fmt::Debug> ValueTree for Just<T> { + type Value = T; + noshrink!(); + fn current(&self) -> T { + self.0.clone() + } +} + +//============================================================================== +// LazyJust +//============================================================================== + +/// A `Strategy` which always produces a single value value and never +/// simplifies. If `T` is `Clone`, you should use `Just` instead. +/// +/// This is a generalization of `Just` and works by calling +/// the provided `Fn () -> T` in `.current()` every time. This is not a +/// very interesting strategy, but is required in cases where `T` is +/// not `Clone`. It is also used in `proptest_derive` where we can't +/// assume that your type is `Clone`. +/// +/// **It is important that the function used be pure.** +#[must_use = "strategies do nothing unless used"] +pub struct LazyJust<T, F: Fn() -> T> { + /// The function executed in `.current()`. + function: F, +} + +/// Shorthand for `LazyJust<T, fn () -> T>`. +pub type LazyJustFn<V> = LazyJust<V, fn() -> V>; + +impl<T, F: Fn() -> T> LazyJust<T, F> { + /// Constructs a `LazyJust` strategy given the function/closure + /// that produces the value. + /// + /// **It is important that the function used be pure.** + pub fn new(function: F) -> Self { + Self { function } + } +} + +impl<T: fmt::Debug, F: Clone + Fn() -> T> Strategy for LazyJust<T, F> { + type Tree = Self; + type Value = T; + + fn new_tree(&self, _: &mut TestRunner) -> NewTree<Self> { + Ok(self.clone()) + } +} + +impl<T: fmt::Debug, F: Fn() -> T> ValueTree for LazyJust<T, F> { + type Value = T; + noshrink!(); + fn current(&self) -> Self::Value { + (self.function)() + } +} + +impl<T, F: Copy + Fn() -> T> Copy for LazyJust<T, F> {} + +impl<T, F: Clone + Fn() -> T> Clone for LazyJust<T, F> { + fn clone(&self) -> Self { + Self { + function: self.function.clone(), + } + } +} + +impl<T, F: Fn() -> T> fmt::Debug for LazyJust<T, F> { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fmt.debug_struct("LazyJust") + .field("function", &"<function>") + .finish() + } +} + +//============================================================================== +// Any `fn () -> T` is a Strategy +//============================================================================== + +// TODO: try 'F: Fn () -> T' instead when we've got specialization. + +impl<T: fmt::Debug> Strategy for fn() -> T { + type Tree = Self; + type Value = T; + + fn new_tree(&self, _: &mut TestRunner) -> NewTree<Self> { + Ok(*self) + } +} + +impl<T: fmt::Debug> ValueTree for fn() -> T { + type Value = T; + noshrink!(); + fn current(&self) -> Self::Value { + self() + } +} diff --git a/vendor/proptest/src/strategy/lazy.rs b/vendor/proptest/src/strategy/lazy.rs new file mode 100644 index 000000000..cb95a7492 --- /dev/null +++ b/vendor/proptest/src/strategy/lazy.rs @@ -0,0 +1,175 @@ +//- +// Copyright 2019 The proptest developers +// +// 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}; +use core::mem; + +use crate::strategy::traits::*; +use crate::test_runner::*; + +/// Represents a value tree that is initialized on the first call to any +/// methods. +/// +/// This is used to defer potentially expensive generation to shrinking time. It +/// is public only to allow APIs to expose it as an intermediate value. +pub struct LazyValueTree<S: Strategy> { + state: LazyValueTreeState<S>, +} + +enum LazyValueTreeState<S: Strategy> { + Initialized(S::Tree), + Uninitialized { + strategy: Arc<S>, + runner: TestRunner, + }, + Failed, +} + +impl<S: Strategy> LazyValueTree<S> { + /// Create a new value tree where initial generation is deferred until + /// `maybe_init` is called. + pub(crate) fn new(strategy: Arc<S>, runner: &mut TestRunner) -> Self { + let runner = runner.partial_clone(); + Self { + state: LazyValueTreeState::Uninitialized { strategy, runner }, + } + } + + /// Create a new value tree that has already been initialized. + pub(crate) fn new_initialized(value_tree: S::Tree) -> Self { + Self { + state: LazyValueTreeState::Initialized(value_tree), + } + } + + /// Returns a reference to the inner value tree if initialized. + pub(crate) fn as_inner(&self) -> Option<&S::Tree> { + match &self.state { + LazyValueTreeState::Initialized(v) => Some(v), + LazyValueTreeState::Uninitialized { .. } + | LazyValueTreeState::Failed => None, + } + } + + /// Returns a mutable reference to the inner value tree if uninitialized. + pub(crate) fn as_inner_mut(&mut self) -> Option<&mut S::Tree> { + match &mut self.state { + LazyValueTreeState::Initialized(v) => Some(v), + LazyValueTreeState::Uninitialized { .. } + | LazyValueTreeState::Failed => None, + } + } + + /// Try initializing the value tree. + pub(crate) fn maybe_init(&mut self) { + if !self.is_uninitialized() { + return; + } + + let state = mem::replace(&mut self.state, LazyValueTreeState::Failed); + match state { + LazyValueTreeState::Uninitialized { + strategy, + mut runner, + } => { + match strategy.new_tree(&mut runner) { + Ok(v) => { + let _ = mem::replace( + &mut self.state, + LazyValueTreeState::Initialized(v), + ); + } + Err(_) => { + // self.state is set to Failed above. Keep it that way. + } + } + } + LazyValueTreeState::Initialized(_) | LazyValueTreeState::Failed => { + unreachable!("can only reach here if uninitialized") + } + } + } + + /// Whether this value tree still needs to be initialized. + pub(crate) fn is_uninitialized(&self) -> bool { + match &self.state { + LazyValueTreeState::Uninitialized { .. } => true, + LazyValueTreeState::Initialized(_) | LazyValueTreeState::Failed => { + false + } + } + } + + /// Whether the value tree was successfully initialized. + pub(crate) fn is_initialized(&self) -> bool { + match &self.state { + LazyValueTreeState::Initialized(_) => true, + LazyValueTreeState::Uninitialized { .. } + | LazyValueTreeState::Failed => false, + } + } +} + +impl<S: Strategy> Clone for LazyValueTree<S> +where + S::Tree: Clone, +{ + fn clone(&self) -> Self { + Self { + state: self.state.clone(), + } + } +} + +impl<S: Strategy> fmt::Debug for LazyValueTree<S> +where + S::Tree: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("LazyValueTree") + .field("state", &self.state) + .finish() + } +} + +impl<S: Strategy> Clone for LazyValueTreeState<S> +where + S::Tree: Clone, +{ + fn clone(&self) -> Self { + use LazyValueTreeState::*; + + match self { + Initialized(v) => Initialized(v.clone()), + Uninitialized { strategy, runner } => Uninitialized { + strategy: Arc::clone(strategy), + runner: runner.clone(), + }, + Failed => Failed, + } + } +} + +impl<S: Strategy> fmt::Debug for LazyValueTreeState<S> +where + S::Tree: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + LazyValueTreeState::Initialized(value_tree) => { + f.debug_tuple("Initialized").field(value_tree).finish() + } + LazyValueTreeState::Uninitialized { strategy, .. } => f + .debug_struct("Uninitialized") + .field("strategy", strategy) + .finish(), + LazyValueTreeState::Failed => write!(f, "Failed"), + } + } +} diff --git a/vendor/proptest/src/strategy/map.rs b/vendor/proptest/src/strategy/map.rs new file mode 100644 index 000000000..464b99819 --- /dev/null +++ b/vendor/proptest/src/strategy/map.rs @@ -0,0 +1,301 @@ +//- +// 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::Arc; +use core::fmt; +use core::marker::PhantomData; + +use crate::strategy::traits::*; +use crate::test_runner::*; + +//============================================================================== +// Map +//============================================================================== + +/// `Strategy` and `ValueTree` map adaptor. +/// +/// See `Strategy::prop_map()`. +#[must_use = "strategies do nothing unless used"] +pub struct Map<S, F> { + pub(super) source: S, + pub(super) fun: Arc<F>, +} + +impl<S: fmt::Debug, F> fmt::Debug for Map<S, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("Map") + .field("source", &self.source) + .field("fun", &"<function>") + .finish() + } +} + +impl<S: Clone, F> Clone for Map<S, F> { + fn clone(&self) -> Self { + Map { + source: self.source.clone(), + fun: Arc::clone(&self.fun), + } + } +} + +impl<S: Strategy, O: fmt::Debug, F: Fn(S::Value) -> O> Strategy for Map<S, F> { + type Tree = Map<S::Tree, F>; + type Value = O; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + self.source.new_tree(runner).map(|v| Map { + source: v, + fun: Arc::clone(&self.fun), + }) + } +} + +impl<S: ValueTree, O: fmt::Debug, F: Fn(S::Value) -> O> ValueTree + for Map<S, F> +{ + type Value = O; + + fn current(&self) -> O { + (self.fun)(self.source.current()) + } + + fn simplify(&mut self) -> bool { + self.source.simplify() + } + + fn complicate(&mut self) -> bool { + self.source.complicate() + } +} + +//============================================================================== +// MapInto +//============================================================================== + +// NOTE: Since this is external stable API, +// we avoid relying on the Map in `statics`. + +/// `Strategy` and `ValueTree` map into adaptor. +/// +/// See `Strategy::prop_map_into()`. +#[must_use = "strategies do nothing unless used"] +pub struct MapInto<S, O> { + pub(super) source: S, + pub(super) output: PhantomData<O>, +} + +impl<S, O> MapInto<S, O> { + /// Construct a `MapInto` mapper from an `S` strategy into a strategy + /// producing `O`s. + pub(super) fn new(source: S) -> Self { + Self { + source, + output: PhantomData, + } + } +} + +impl<S: fmt::Debug, O> fmt::Debug for MapInto<S, O> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("MapInto") + .field("source", &self.source) + .finish() + } +} + +impl<S: Clone, O> Clone for MapInto<S, O> { + fn clone(&self) -> Self { + Self::new(self.source.clone()) + } +} + +impl<S: Strategy, O: fmt::Debug> Strategy for MapInto<S, O> +where + S::Value: Into<O>, +{ + type Tree = MapInto<S::Tree, O>; + type Value = O; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + self.source.new_tree(runner).map(MapInto::new) + } +} + +impl<S: ValueTree, O: fmt::Debug> ValueTree for MapInto<S, O> +where + S::Value: Into<O>, +{ + type Value = O; + + fn current(&self) -> O { + self.source.current().into() + } + + fn simplify(&mut self) -> bool { + self.source.simplify() + } + + fn complicate(&mut self) -> bool { + self.source.complicate() + } +} + +//============================================================================== +// Perturb +//============================================================================== + +/// `Strategy` perturbation adaptor. +/// +/// See `Strategy::prop_perturb()`. +#[must_use = "strategies do nothing unless used"] +pub struct Perturb<S, F> { + pub(super) source: S, + pub(super) fun: Arc<F>, +} + +impl<S: fmt::Debug, F> fmt::Debug for Perturb<S, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("Perturb") + .field("source", &self.source) + .field("fun", &"<function>") + .finish() + } +} + +impl<S: Clone, F> Clone for Perturb<S, F> { + fn clone(&self) -> Self { + Perturb { + source: self.source.clone(), + fun: Arc::clone(&self.fun), + } + } +} + +impl<S: Strategy, O: fmt::Debug, F: Fn(S::Value, TestRng) -> O> Strategy + for Perturb<S, F> +{ + type Tree = PerturbValueTree<S::Tree, F>; + type Value = O; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + let rng = runner.new_rng(); + + self.source.new_tree(runner).map(|source| PerturbValueTree { + source, + rng, + fun: Arc::clone(&self.fun), + }) + } +} + +/// `ValueTree` perturbation adaptor. +/// +/// See `Strategy::prop_perturb()`. +pub struct PerturbValueTree<S, F> { + source: S, + fun: Arc<F>, + rng: TestRng, +} + +impl<S: fmt::Debug, F> fmt::Debug for PerturbValueTree<S, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("PerturbValueTree") + .field("source", &self.source) + .field("fun", &"<function>") + .field("rng", &self.rng) + .finish() + } +} + +impl<S: Clone, F> Clone for PerturbValueTree<S, F> { + fn clone(&self) -> Self { + PerturbValueTree { + source: self.source.clone(), + fun: Arc::clone(&self.fun), + rng: self.rng.clone(), + } + } +} + +impl<S: ValueTree, O: fmt::Debug, F: Fn(S::Value, TestRng) -> O> ValueTree + for PerturbValueTree<S, F> +{ + type Value = O; + + fn current(&self) -> O { + (self.fun)(self.source.current(), self.rng.clone()) + } + + fn simplify(&mut self) -> bool { + self.source.simplify() + } + + fn complicate(&mut self) -> bool { + self.source.complicate() + } +} + +//============================================================================== +// Tests +//============================================================================== + +#[cfg(test)] +mod test { + use std::collections::HashSet; + + use rand::RngCore; + + use super::*; + use crate::strategy::just::Just; + + #[test] + fn test_map() { + TestRunner::default() + .run(&(0..10).prop_map(|v| v * 2), |v| { + assert!(0 == v % 2); + Ok(()) + }) + .unwrap(); + } + + #[test] + fn test_map_into() { + TestRunner::default() + .run(&(0..10u8).prop_map_into::<usize>(), |v| { + assert!(v < 10); + Ok(()) + }) + .unwrap(); + } + + #[test] + fn perturb_uses_same_rng_every_time() { + let mut runner = TestRunner::default(); + let input = Just(1).prop_perturb(|v, mut rng| v + rng.next_u32()); + + for _ in 0..16 { + let value = input.new_tree(&mut runner).unwrap(); + assert_eq!(value.current(), value.current()); + } + } + + #[test] + fn perturb_uses_varying_random_seeds() { + let mut runner = TestRunner::default(); + let input = Just(1).prop_perturb(|v, mut rng| v + rng.next_u32()); + + let mut seen = HashSet::new(); + for _ in 0..64 { + seen.insert(input.new_tree(&mut runner).unwrap().current()); + } + + assert_eq!(64, seen.len()); + } +} diff --git a/vendor/proptest/src/strategy/mod.rs b/vendor/proptest/src/strategy/mod.rs new file mode 100644 index 000000000..6427fc103 --- /dev/null +++ b/vendor/proptest/src/strategy/mod.rs @@ -0,0 +1,37 @@ +//- +// Copyright 2017, 2018 The proptest developers +// +// 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. + +//! Defines the core traits used by Proptest. + +mod filter; +mod filter_map; +mod flatten; +mod fuse; +mod just; +mod lazy; +mod map; +mod recursive; +mod shuffle; +mod traits; +mod unions; + +pub use self::filter::*; +pub use self::filter_map::*; +pub use self::flatten::*; +pub use self::fuse::*; +pub use self::just::*; +pub use self::lazy::*; +pub use self::lazy::*; +pub use self::map::*; +pub use self::recursive::*; +pub use self::shuffle::*; +pub use self::traits::*; +pub use self::unions::*; + +pub mod statics; diff --git a/vendor/proptest/src/strategy/recursive.rs b/vendor/proptest/src/strategy/recursive.rs new file mode 100644 index 000000000..6407be7c7 --- /dev/null +++ b/vendor/proptest/src/strategy/recursive.rs @@ -0,0 +1,209 @@ +//- +// 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, Box, Vec}; + +use crate::strategy::traits::*; +use crate::strategy::unions::float_to_weight; +use crate::test_runner::*; + +/// Return type from `Strategy::prop_recursive()`. +#[must_use = "strategies do nothing unless used"] +pub struct Recursive<T, F> { + base: BoxedStrategy<T>, + recurse: Arc<F>, + depth: u32, + desired_size: u32, + expected_branch_size: u32, +} + +impl<T: fmt::Debug, F> fmt::Debug for Recursive<T, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("Recursive") + .field("base", &self.base) + .field("recurse", &"<function>") + .field("depth", &self.depth) + .field("desired_size", &self.desired_size) + .field("expected_branch_size", &self.expected_branch_size) + .finish() + } +} + +impl<T, F> Clone for Recursive<T, F> { + fn clone(&self) -> Self { + Recursive { + base: self.base.clone(), + recurse: Arc::clone(&self.recurse), + depth: self.depth, + desired_size: self.desired_size, + expected_branch_size: self.expected_branch_size, + } + } +} + +impl< + T: fmt::Debug + 'static, + R: Strategy<Value = T> + 'static, + F: Fn(BoxedStrategy<T>) -> R, + > Recursive<T, F> +{ + pub(super) fn new( + base: impl Strategy<Value = T> + 'static, + depth: u32, + desired_size: u32, + expected_branch_size: u32, + recurse: F, + ) -> Self { + Self { + base: base.boxed(), + recurse: Arc::new(recurse), + depth, + desired_size, + expected_branch_size, + } + } +} + +impl< + T: fmt::Debug + 'static, + R: Strategy<Value = T> + 'static, + F: Fn(BoxedStrategy<T>) -> R, + > Strategy for Recursive<T, F> +{ + type Tree = Box<dyn ValueTree<Value = T>>; + type Value = T; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + // Since the generator is stateless, we can't implement any "absolutely + // X many items" rule. We _can_, however, with extremely high + // probability, obtain a value near what we want by using decaying + // probabilities of branching as we go down the tree. + // + // We are given a target size S and a branch size K (branch size = + // expected number of items immediately below each branch). We select + // some probability P for each level. + // + // A single level l is thus expected to hold PlK branches. Each of + // those will have P(l+1)K child branches of their own, so there are + // PlP(l+1)K² second-level branches. The total branches in the tree is + // thus (Σ PlK^l) for l from 0 to infinity. Each level is expected to + // hold K items, so the total number of items is simply K times the + // number of branches, or (K Σ PlK^l). So we want to find a P sequence + // such that (lim (K Σ PlK^l) = S), or more simply, + // (lim Σ PlK^l = S/K). + // + // Let Q be a second probability sequence such that Pl = Ql/K^l. This + // changes the formulation to (lim Σ Ql = S/K). The series Σ0.5^(l+1) + // converges on 1.0, so we can let Ql = S/K * 0.5^(l+1), and so + // Pl = S/K^(l+1) * 0.5^(l+1) = S / (2K) ^ (l+1) + // + // We don't actually have infinite levels here since we _can_ easily + // cap to a fixed max depth, so this will be a minor underestimate. We + // also clamp all probabilities to 0.9 to ensure that we can't end up + // with levels which are always pure branches, which further + // underestimates size. + + let mut branch_probabilities = Vec::new(); + let mut k2 = u64::from(self.expected_branch_size) * 2; + for _ in 0..self.depth { + branch_probabilities.push(f64::from(self.desired_size) / k2 as f64); + k2 = k2.saturating_mul(u64::from(self.expected_branch_size) * 2); + } + + let mut strat = self.base.clone(); + while let Some(branch_probability) = branch_probabilities.pop() { + let recursed = (self.recurse)(strat.clone()); + let recursive_choice = recursed.boxed(); + let non_recursive_choice = strat; + // Clamp the maximum branch probability to 0.9 to ensure we can + // generate non-recursive cases reasonably often. + let branch_probability = branch_probability.min(0.9); + let (weight_branch, weight_leaf) = + float_to_weight(branch_probability); + let branch = prop_oneof![ + weight_leaf => non_recursive_choice, + weight_branch => recursive_choice, + ]; + strat = branch.boxed(); + } + + strat.new_tree(runner) + } +} + +#[cfg(test)] +mod test { + use std::cmp::max; + + use super::*; + use crate::strategy::just::Just; + + #[derive(Clone, Debug, PartialEq)] + enum Tree { + Leaf, + Branch(Vec<Tree>), + } + + impl Tree { + fn stats(&self) -> (u32, u32) { + match *self { + Tree::Leaf => (0, 1), + Tree::Branch(ref children) => { + let mut depth = 0; + let mut count = 0; + for child in children { + let (d, c) = child.stats(); + depth = max(d, depth); + count += c; + } + + (depth + 1, count + 1) + } + } + } + } + + #[test] + fn test_recursive() { + let mut max_depth = 0; + let mut max_count = 0; + + let strat = Just(Tree::Leaf).prop_recursive(4, 64, 16, |element| { + crate::collection::vec(element, 8..16).prop_map(Tree::Branch) + }); + + let mut runner = TestRunner::deterministic(); + for _ in 0..65536 { + let tree = strat.new_tree(&mut runner).unwrap().current(); + let (depth, count) = tree.stats(); + assert!(depth <= 4, "Got depth {}", depth); + assert!(count <= 128, "Got count {}", count); + max_depth = max(depth, max_depth); + max_count = max(count, max_count); + } + + assert!(max_depth >= 3, "Only got max depth {}", max_depth); + assert!(max_count > 48, "Only got max count {}", max_count); + } + + #[test] + fn simplifies_to_non_recursive() { + let strat = Just(Tree::Leaf).prop_recursive(4, 64, 16, |element| { + crate::collection::vec(element, 8..16).prop_map(Tree::Branch) + }); + + let mut runner = TestRunner::deterministic(); + for _ in 0..256 { + let mut value = strat.new_tree(&mut runner).unwrap(); + while value.simplify() {} + + assert_eq!(Tree::Leaf, value.current()); + } + } +} diff --git a/vendor/proptest/src/strategy/shuffle.rs b/vendor/proptest/src/strategy/shuffle.rs new file mode 100644 index 000000000..b94a73c3b --- /dev/null +++ b/vendor/proptest/src/strategy/shuffle.rs @@ -0,0 +1,287 @@ +//- +// 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::{Cell, Vec, VecDeque}; + +use rand::Rng; + +use crate::num; +use crate::strategy::traits::*; +use crate::test_runner::*; + +/// `Strategy` shuffle adaptor. +/// +/// See `Strategy::prop_shuffle()`. +#[derive(Clone, Debug)] +#[must_use = "strategies do nothing unless used"] +pub struct Shuffle<S>(pub(super) S); + +/// A value which can be used with the `prop_shuffle` combinator. +/// +/// This is not a general-purpose trait. Its methods are prefixed with +/// `shuffle_` to avoid the compiler suggesting them or this trait as +/// corrections in errors. +pub trait Shuffleable { + /// Return the length of this collection. + fn shuffle_len(&self) -> usize; + /// Swap the elements at the given indices. + fn shuffle_swap(&mut self, a: usize, b: usize); +} + +macro_rules! shuffleable { + ($($t:tt)*) => { + impl<T> Shuffleable for $($t)* { + fn shuffle_len(&self) -> usize { + self.len() + } + + fn shuffle_swap(&mut self, a: usize, b: usize) { + self.swap(a, b); + } + } + } +} + +shuffleable!([T]); +shuffleable!(Vec<T>); +shuffleable!(VecDeque<T>); +// Zero- and 1-length arrays aren't usefully shuffleable, but are included to +// simplify external macros that may try to use them anyway. +shuffleable!([T; 0]); +shuffleable!([T; 1]); +shuffleable!([T; 2]); +shuffleable!([T; 3]); +shuffleable!([T; 4]); +shuffleable!([T; 5]); +shuffleable!([T; 6]); +shuffleable!([T; 7]); +shuffleable!([T; 8]); +shuffleable!([T; 9]); +shuffleable!([T; 10]); +shuffleable!([T; 11]); +shuffleable!([T; 12]); +shuffleable!([T; 13]); +shuffleable!([T; 14]); +shuffleable!([T; 15]); +shuffleable!([T; 16]); +shuffleable!([T; 17]); +shuffleable!([T; 18]); +shuffleable!([T; 19]); +shuffleable!([T; 20]); +shuffleable!([T; 21]); +shuffleable!([T; 22]); +shuffleable!([T; 23]); +shuffleable!([T; 24]); +shuffleable!([T; 25]); +shuffleable!([T; 26]); +shuffleable!([T; 27]); +shuffleable!([T; 28]); +shuffleable!([T; 29]); +shuffleable!([T; 30]); +shuffleable!([T; 31]); +shuffleable!([T; 32]); + +impl<S: Strategy> Strategy for Shuffle<S> +where + S::Value: Shuffleable, +{ + type Tree = ShuffleValueTree<S::Tree>; + type Value = S::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + let rng = runner.new_rng(); + + self.0.new_tree(runner).map(|inner| ShuffleValueTree { + inner, + rng, + dist: Cell::new(None), + simplifying_inner: false, + }) + } +} + +/// `ValueTree` shuffling adaptor. +/// +/// See `Strategy::prop_shuffle()`. +#[derive(Clone, Debug)] +pub struct ShuffleValueTree<V> { + inner: V, + rng: TestRng, + /// The maximum amount to move any one element during shuffling. + /// + /// This is `Cell` since we can't determine the bounds of the value until + /// the first call to `current()`. (We technically _could_ by generating a + /// value in `new_tree` and checking its length, but that would be a 100% + /// slowdown.) + dist: Cell<Option<num::usize::BinarySearch>>, + /// Whether we've started simplifying `inner`. After this point, we can no + /// longer simplify or complicate `dist`. + simplifying_inner: bool, +} + +impl<V: ValueTree> ShuffleValueTree<V> +where + V::Value: Shuffleable, +{ + fn init_dist(&self, dflt: usize) -> usize { + if self.dist.get().is_none() { + self.dist.set(Some(num::usize::BinarySearch::new(dflt))); + } + + self.dist.get().unwrap().current() + } + + fn force_init_dist(&self) { + if self.dist.get().is_none() { + self.init_dist(self.current().shuffle_len()); + } + } +} + +impl<V: ValueTree> ValueTree for ShuffleValueTree<V> +where + V::Value: Shuffleable, +{ + type Value = V::Value; + + fn current(&self) -> V::Value { + let mut value = self.inner.current(); + let len = value.shuffle_len(); + // The maximum distance to swap elements. This could be larger than + // `value` if `value` has reduced size during shrinking; that's OK, + // since we only use this to filter swaps. + let max_swap = self.init_dist(len); + + // If empty collection or all swaps will be filtered out, there's + // nothing to shuffle. + if 0 == len || 0 == max_swap { + return value; + } + + let mut rng = self.rng.clone(); + + for start_index in 0..len - 1 { + // Determine the other index to be swapped, then skip the swap if + // it is too far. This ordering is critical, as it ensures that we + // generate the same sequence of random numbers every time. + let end_index = rng.gen_range(start_index..len); + if end_index - start_index <= max_swap { + value.shuffle_swap(start_index, end_index); + } + } + + value + } + + fn simplify(&mut self) -> bool { + if self.simplifying_inner { + self.inner.simplify() + } else { + // Ensure that we've initialised `dist` to *something* to give + // consistent non-panicking behaviour even if called in an + // unexpected sequence. + self.force_init_dist(); + if self.dist.get_mut().as_mut().unwrap().simplify() { + true + } else { + self.simplifying_inner = true; + self.inner.simplify() + } + } + } + + fn complicate(&mut self) -> bool { + if self.simplifying_inner { + self.inner.complicate() + } else { + self.force_init_dist(); + self.dist.get_mut().as_mut().unwrap().complicate() + } + } +} + +#[cfg(test)] +mod test { + use std::borrow::ToOwned; + use std::collections::HashSet; + use std::i32; + + use super::*; + use crate::collection; + use crate::strategy::just::Just; + + static VALUES: &'static [i32] = &[ + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, + ]; + + #[test] + fn generates_different_permutations() { + let mut runner = TestRunner::default(); + let mut seen = HashSet::<Vec<i32>>::new(); + + let input = Just(VALUES.to_owned()).prop_shuffle(); + + for _ in 0..1024 { + let mut value = input.new_tree(&mut runner).unwrap().current(); + + assert!( + seen.insert(value.clone()), + "Value {:?} generated more than once", + value + ); + + value.sort(); + assert_eq!(VALUES, &value[..]); + } + } + + #[test] + fn simplify_reduces_shuffle_amount() { + let mut runner = TestRunner::default(); + + let input = Just(VALUES.to_owned()).prop_shuffle(); + for _ in 0..1024 { + let mut value = input.new_tree(&mut runner).unwrap(); + + let mut prev_dist = i32::MAX; + loop { + let v = value.current(); + // Compute the "shuffle distance" by summing the absolute + // distance of each element's displacement. + let mut dist = 0; + for (ix, &nominal) in v.iter().enumerate() { + dist += (nominal - ix as i32).abs(); + } + + assert!( + dist <= prev_dist, + "dist = {}, prev_dist = {}", + dist, + prev_dist + ); + + prev_dist = dist; + if !value.simplify() { + break; + } + } + + // When fully simplified, the result is in the original order. + assert_eq!(0, prev_dist); + } + } + + #[test] + fn simplify_complicate_contract_upheld() { + check_strategy_sanity( + collection::vec(0i32..1000, 5..10).prop_shuffle(), + None, + ); + } +} diff --git a/vendor/proptest/src/strategy/statics.rs b/vendor/proptest/src/strategy/statics.rs new file mode 100644 index 000000000..978dc13b9 --- /dev/null +++ b/vendor/proptest/src/strategy/statics.rs @@ -0,0 +1,266 @@ +//- +// 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. + +//! Modified versions of the normal strategy combinators which take specialised +//! traits instead of normal functions. +//! +//! This entire module is strictly a workaround until +//! <https://github.com/rust-lang/rfcs/pull/1522> and +//! <https://github.com/rust-lang/rfcs/pull/2071> are available in stable. It +//! allows naming types built on the combinators without resorting to dynamic +//! dispatch or causing `Arc` to allocate space for a function pointer. +//! +//! External code is discouraged from using this module directly. It is +//! deliberately not exposed in a convenient way (i.e., via the `Strategy` +//! trait itself), but is nonetheless exposed since external trait implementors +//! may face the same issues. +//! +//! **This module is subject to removal at some point after the language +//! features linked above become stable.** + +use crate::std_facade::fmt; + +use crate::strategy::traits::*; +use crate::test_runner::*; + +//============================================================================== +// Filter +//============================================================================== + +/// Essentially `Fn (&T) -> bool`. +pub trait FilterFn<T> { + /// Test whether `t` passes the filter. + fn apply(&self, t: &T) -> bool; +} + +/// Static version of `strategy::Filter`. +#[derive(Clone)] +#[must_use = "strategies do nothing unless used"] +pub struct Filter<S, F> { + source: S, + whence: Reason, + fun: F, +} + +impl<S, F> Filter<S, F> { + /// Adapt strategy `source` to reject values which do not pass `filter`, + /// using `whence` as the reported reason/location. + pub fn new(source: S, whence: Reason, filter: F) -> Self { + // NOTE: We don't use universal quantification R: Into<Reason> + // since the module is not conveniently exposed. + Filter { + source, + whence, + fun: filter, + } + } +} + +impl<S: fmt::Debug, F> fmt::Debug for Filter<S, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("Filter") + .field("source", &self.source) + .field("whence", &self.whence) + .field("fun", &"<function>") + .finish() + } +} + +impl<S: Strategy, F: FilterFn<S::Value> + Clone> Strategy for Filter<S, F> { + type Tree = Filter<S::Tree, F>; + type Value = S::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + loop { + let val = self.source.new_tree(runner)?; + if !self.fun.apply(&val.current()) { + runner.reject_local(self.whence.clone())?; + } else { + return Ok(Filter { + source: val, + whence: "unused".into(), + fun: self.fun.clone(), + }); + } + } + } +} + +impl<S: ValueTree, F: FilterFn<S::Value>> Filter<S, F> { + fn ensure_acceptable(&mut self) { + while !self.fun.apply(&self.source.current()) { + if !self.source.complicate() { + panic!( + "Unable to complicate filtered strategy \ + back into acceptable value" + ); + } + } + } +} + +impl<S: ValueTree, F: FilterFn<S::Value>> ValueTree for Filter<S, F> { + type Value = S::Value; + + fn current(&self) -> S::Value { + self.source.current() + } + + fn simplify(&mut self) -> bool { + if self.source.simplify() { + self.ensure_acceptable(); + true + } else { + false + } + } + + fn complicate(&mut self) -> bool { + if self.source.complicate() { + self.ensure_acceptable(); + true + } else { + false + } + } +} + +//============================================================================== +// Map +//============================================================================== + +/// Essentially `Fn (T) -> Output`. +pub trait MapFn<T> { + #[allow(missing_docs)] + type Output: fmt::Debug; + + /// Map `T` to `Output`. + fn apply(&self, t: T) -> Self::Output; +} + +/// Static version of `strategy::Map`. +#[derive(Clone)] +#[must_use = "strategies do nothing unless used"] +pub struct Map<S, F> { + source: S, + fun: F, +} + +impl<S, F> Map<S, F> { + /// Adapt strategy `source` by applying `fun` to values it produces. + pub fn new(source: S, fun: F) -> Self { + Map { source, fun } + } +} + +impl<S: fmt::Debug, F> fmt::Debug for Map<S, F> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("Map") + .field("source", &self.source) + .field("fun", &"<function>") + .finish() + } +} + +impl<S: Strategy, F: Clone + MapFn<S::Value>> Strategy for Map<S, F> { + type Tree = Map<S::Tree, F>; + type Value = F::Output; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + self.source.new_tree(runner).map(|v| Map { + source: v, + fun: self.fun.clone(), + }) + } +} + +impl<S: ValueTree, F: MapFn<S::Value>> ValueTree for Map<S, F> { + type Value = F::Output; + + fn current(&self) -> F::Output { + self.fun.apply(self.source.current()) + } + + fn simplify(&mut self) -> bool { + self.source.simplify() + } + + fn complicate(&mut self) -> bool { + self.source.complicate() + } +} + +impl<I, O: fmt::Debug> MapFn<I> for fn(I) -> O { + type Output = O; + fn apply(&self, x: I) -> Self::Output { + self(x) + } +} + +pub(crate) fn static_map<S: Strategy, O: fmt::Debug>( + strat: S, + fun: fn(S::Value) -> O, +) -> Map<S, fn(S::Value) -> O> { + Map::new(strat, fun) +} + +//============================================================================== +// Tests +//============================================================================== + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn test_static_filter() { + #[derive(Clone, Copy, Debug)] + struct MyFilter; + impl FilterFn<i32> for MyFilter { + fn apply(&self, &v: &i32) -> bool { + 0 == v % 3 + } + } + + let input = Filter::new(0..256, "%3".into(), MyFilter); + + for _ in 0..256 { + let mut runner = TestRunner::default(); + let mut case = input.new_tree(&mut runner).unwrap(); + + assert!(0 == case.current() % 3); + + while case.simplify() { + assert!(0 == case.current() % 3); + } + assert!(0 == case.current() % 3); + } + } + + #[test] + fn test_static_map() { + #[derive(Clone, Copy, Debug)] + struct MyMap; + impl MapFn<i32> for MyMap { + type Output = i32; + fn apply(&self, v: i32) -> i32 { + v * 2 + } + } + + let input = Map::new(0..10, MyMap); + + TestRunner::default() + .run(&input, |v| { + assert!(0 == v % 2); + Ok(()) + }) + .unwrap(); + } +} diff --git a/vendor/proptest/src/strategy/traits.rs b/vendor/proptest/src/strategy/traits.rs new file mode 100644 index 000000000..bcad20a1e --- /dev/null +++ b/vendor/proptest/src/strategy/traits.rs @@ -0,0 +1,1054 @@ +//- +// Copyright 2017, 2018 The proptest developers +// +// 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, Box, Rc}; +use core::cmp; + +use crate::strategy::*; +use crate::test_runner::*; + +//============================================================================== +// Traits +//============================================================================== + +/// A new [`ValueTree`] from a [`Strategy`] when [`Ok`] or otherwise [`Err`] +/// when a new value-tree can not be produced for some reason such as +/// in the case of filtering with a predicate which always returns false. +/// You should pass in your strategy as the type parameter. +/// +/// [`Strategy`]: trait.Strategy.html +/// [`ValueTree`]: trait.ValueTree.html +/// [`Ok`]: https://doc.rust-lang.org/nightly/std/result/enum.Result.html#variant.Ok +/// [`Err`]: https://doc.rust-lang.org/nightly/std/result/enum.Result.html#variant.Err +pub type NewTree<S> = Result<<S as Strategy>::Tree, Reason>; + +/// A strategy for producing arbitrary values of a given type. +/// +/// `fmt::Debug` is a hard requirement for all strategies currently due to +/// `prop_flat_map()`. This constraint will be removed when specialisation +/// becomes stable. +#[must_use = "strategies do nothing unless used"] +pub trait Strategy: fmt::Debug { + /// The value tree generated by this `Strategy`. + type Tree: ValueTree<Value = Self::Value>; + + /// The type of value used by functions under test generated by this Strategy. + /// + /// This corresponds to the same type as the associated type `Value` + /// in `Self::Tree`. It is provided here to simplify usage particularly + /// in conjunction with `-> impl Strategy<Value = MyType>`. + type Value: fmt::Debug; + + /// Generate a new value tree from the given runner. + /// + /// This may fail if there are constraints on the generated value and the + /// generator is unable to produce anything that satisfies them. Any + /// failure is wrapped in `TestError::Abort`. + /// + /// This method is generally expected to be deterministic. That is, given a + /// `TestRunner` with its RNG in a particular state, this should produce an + /// identical `ValueTree` every time. Non-deterministic strategies do not + /// cause problems during normal operation, but they do break failure + /// persistence since it is implemented by simply saving the seed used to + /// generate the test case. + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self>; + + /// Returns a strategy which produces values transformed by the function + /// `fun`. + /// + /// There is no need (or possibility, for that matter) to define how the + /// output is to be shrunken. Shrinking continues to take place in terms of + /// the source value. + /// + /// `fun` should be a deterministic function. That is, for a given input + /// value, it should produce an equivalent output value on every call. + /// Proptest assumes that it can call the function as many times as needed + /// to generate as many identical values as needed. For this reason, `F` is + /// `Fn` rather than `FnMut`. + fn prop_map<O: fmt::Debug, F: Fn(Self::Value) -> O>( + self, + fun: F, + ) -> Map<Self, F> + where + Self: Sized, + { + Map { + source: self, + fun: Arc::new(fun), + } + } + + /// Returns a strategy which produces values of type `O` by transforming + /// `Self` with `Into<O>`. + /// + /// You should always prefer this operation instead of `prop_map` when + /// you can as it is both clearer and also currently more efficient. + /// + /// There is no need (or possibility, for that matter) to define how the + /// output is to be shrunken. Shrinking continues to take place in terms of + /// the source value. + fn prop_map_into<O: fmt::Debug>(self) -> MapInto<Self, O> + where + Self: Sized, + Self::Value: Into<O>, + { + MapInto::new(self) + } + + /// Returns a strategy which produces values transformed by the function + /// `fun`, which is additionally given a random number generator. + /// + /// This is exactly like `prop_map()` except for the addition of the second + /// argument to the function. This allows introducing chaotic variations to + /// generated values that are not easily expressed otherwise while allowing + /// shrinking to proceed reasonably. + /// + /// During shrinking, `fun` is always called with an identical random + /// number generator, so if it is a pure function it will always perform + /// the same perturbation. + /// + /// ## Example + /// + /// ``` + /// // The prelude also gets us the `Rng` trait. + /// use proptest::prelude::*; + /// + /// proptest! { + /// #[test] + /// fn test_something(a in (0i32..10).prop_perturb( + /// // Perturb the integer `a` (range 0..10) to a pair of that + /// // integer and another that's ± 10 of it. + /// // Note that this particular case would be better implemented as + /// // `(0i32..10, -10i32..10).prop_map(|(a, b)| (a, a + b))` + /// // but is shown here for simplicity. + /// |centre, rng| (centre, centre + rng.gen_range(-10, 10)))) + /// { + /// // Test stuff + /// } + /// } + /// # fn main() { } + /// ``` + fn prop_perturb<O: fmt::Debug, F: Fn(Self::Value, TestRng) -> O>( + self, + fun: F, + ) -> Perturb<Self, F> + where + Self: Sized, + { + Perturb { + source: self, + fun: Arc::new(fun), + } + } + + /// Maps values produced by this strategy into new strategies and picks + /// values from those strategies. + /// + /// `fun` is used to transform the values produced by this strategy into + /// other strategies. Values are then chosen from the derived strategies. + /// Shrinking proceeds by shrinking individual values as well as shrinking + /// the input used to generate the internal strategies. + /// + /// ## Shrinking + /// + /// In the case of test failure, shrinking will not only shrink the output + /// from the combinator itself, but also the input, i.e., the strategy used + /// to generate the output itself. Doing this requires searching the new + /// derived strategy for a new failing input. The combinator will generate + /// up to `Config::cases` values for this search. + /// + /// As a result, nested `prop_flat_map`/`Flatten` combinators risk + /// exponential run time on this search for new failing values. To ensure + /// that test failures occur within a reasonable amount of time, all of + /// these combinators share a single "flat map regen" counter, and will + /// stop generating new values if it exceeds `Config::max_flat_map_regens`. + /// + /// ## Example + /// + /// Generate two integers, where the second is always less than the first, + /// without using filtering: + /// + /// ``` + /// use proptest::prelude::*; + /// + /// proptest! { + /// # /* + /// #[test] + /// # */ + /// fn test_two( + /// // Pick integers in the 1..65536 range, and derive a strategy + /// // which emits a tuple of that integer and another one which is + /// // some value less than it. + /// (a, b) in (1..65536).prop_flat_map(|a| (Just(a), 0..a)) + /// ) { + /// prop_assert!(b < a); + /// } + /// } + /// # + /// # fn main() { test_two(); } + /// ``` + /// + /// ## Choosing the right flat-map + /// + /// `Strategy` has three "flat-map" combinators. They look very similar at + /// first, and can be used to produce superficially identical test results. + /// For example, the following three expressions all produce inputs which + /// are 2-tuples `(a,b)` where the `b` component is less than `a`. + /// + /// ```no_run + /// # #![allow(unused_variables)] + /// use proptest::prelude::*; + /// + /// let flat_map = (1..10).prop_flat_map(|a| (Just(a), 0..a)); + /// let ind_flat_map = (1..10).prop_ind_flat_map(|a| (Just(a), 0..a)); + /// let ind_flat_map2 = (1..10).prop_ind_flat_map2(|a| 0..a); + /// ``` + /// + /// The three do differ however in terms of how they shrink. + /// + /// For `flat_map`, both `a` and `b` will shrink, and the invariant that + /// `b < a` is maintained. This is a "dependent" or "higher-order" strategy + /// in that it remembers that the strategy for choosing `b` is dependent on + /// the value chosen for `a`. + /// + /// For `ind_flat_map`, the invariant `b < a` is maintained, but only + /// because `a` does not shrink. This is due to the fact that the + /// dependency between the strategies is not tracked; `a` is simply seen as + /// a constant. + /// + /// Finally, for `ind_flat_map2`, the invariant `b < a` is _not_ + /// maintained, because `a` can shrink independently of `b`, again because + /// the dependency between the two variables is not tracked, but in this + /// case the derivation of `a` is still exposed to the shrinking system. + /// + /// The use-cases for the independent flat-map variants is pretty narrow. + /// For the majority of cases where invariants need to be maintained and + /// you want all components to shrink, `prop_flat_map` is the way to go. + /// `prop_ind_flat_map` makes the most sense when the input to the map + /// function is not exposed in the output and shrinking across strategies + /// is not expected to be useful. `prop_ind_flat_map2` is useful for using + /// related values as starting points while not constraining them to that + /// relation. + fn prop_flat_map<S: Strategy, F: Fn(Self::Value) -> S>( + self, + fun: F, + ) -> Flatten<Map<Self, F>> + where + Self: Sized, + { + Flatten::new(Map { + source: self, + fun: Arc::new(fun), + }) + } + + /// Maps values produced by this strategy into new strategies and picks + /// values from those strategies while considering the new strategies to be + /// independent. + /// + /// This is very similar to `prop_flat_map()`, but shrinking will *not* + /// attempt to shrink the input that produces the derived strategies. This + /// is appropriate for when the derived strategies already fully shrink in + /// the desired way. + /// + /// In most cases, you want `prop_flat_map()`. + /// + /// See `prop_flat_map()` for a more detailed explanation on how the + /// three flat-map combinators differ. + fn prop_ind_flat_map<S: Strategy, F: Fn(Self::Value) -> S>( + self, + fun: F, + ) -> IndFlatten<Map<Self, F>> + where + Self: Sized, + { + IndFlatten(Map { + source: self, + fun: Arc::new(fun), + }) + } + + /// Similar to `prop_ind_flat_map()`, but produces 2-tuples with the input + /// generated from `self` in slot 0 and the derived strategy in slot 1. + /// + /// See `prop_flat_map()` for a more detailed explanation on how the + /// three flat-map combinators differ. + fn prop_ind_flat_map2<S: Strategy, F: Fn(Self::Value) -> S>( + self, + fun: F, + ) -> IndFlattenMap<Self, F> + where + Self: Sized, + { + IndFlattenMap { + source: self, + fun: Arc::new(fun), + } + } + + /// Returns a strategy which only produces values accepted by `fun`. + /// + /// This results in a very naïve form of rejection sampling and should only + /// be used if (a) relatively few values will actually be rejected; (b) it + /// isn't easy to express what you want by using another strategy and/or + /// `map()`. + /// + /// There are a lot of downsides to this form of filtering. It slows + /// testing down, since values must be generated but then discarded. + /// Proptest only allows a limited number of rejects this way (across the + /// entire `TestRunner`). Rejection can interfere with shrinking; + /// particularly, complex filters may largely or entirely prevent shrinking + /// from substantially altering the original value. + /// + /// Local rejection sampling is still preferable to rejecting the entire + /// input to a test (via `TestCaseError::Reject`), however, and the default + /// number of local rejections allowed is much higher than the number of + /// whole-input rejections. + /// + /// `whence` is used to record where and why the rejection occurred. + fn prop_filter<R: Into<Reason>, F: Fn(&Self::Value) -> bool>( + self, + whence: R, + fun: F, + ) -> Filter<Self, F> + where + Self: Sized, + { + Filter::new(self, whence.into(), fun) + } + + /// Returns a strategy which only produces transformed values where `fun` + /// returns `Some(value)` and rejects those where `fun` returns `None`. + /// + /// Using this method is preferable to using `.prop_map(..).prop_filter(..)`. + /// + /// This results in a very naïve form of rejection sampling and should only + /// be used if (a) relatively few values will actually be rejected; (b) it + /// isn't easy to express what you want by using another strategy and/or + /// `map()`. + /// + /// There are a lot of downsides to this form of filtering. It slows + /// testing down, since values must be generated but then discarded. + /// Proptest only allows a limited number of rejects this way (across the + /// entire `TestRunner`). Rejection can interfere with shrinking; + /// particularly, complex filters may largely or entirely prevent shrinking + /// from substantially altering the original value. + /// + /// Local rejection sampling is still preferable to rejecting the entire + /// input to a test (via `TestCaseError::Reject`), however, and the default + /// number of local rejections allowed is much higher than the number of + /// whole-input rejections. + /// + /// `whence` is used to record where and why the rejection occurred. + fn prop_filter_map<F: Fn(Self::Value) -> Option<O>, O: fmt::Debug>( + self, + whence: impl Into<Reason>, + fun: F, + ) -> FilterMap<Self, F> + where + Self: Sized, + { + FilterMap::new(self, whence.into(), fun) + } + + /// Returns a strategy which picks uniformly from `self` and `other`. + /// + /// When shrinking, if a value from `other` was originally chosen but that + /// value can be shrunken no further, it switches to a value from `self` + /// and starts shrinking that. + /// + /// Be aware that chaining `prop_union` calls will result in a very + /// right-skewed distribution. If this is not what you want, you can call + /// the `.or()` method on the `Union` to add more values to the same union, + /// or directly call `Union::new()`. + /// + /// Both `self` and `other` must be of the same type. To combine + /// heterogeneous strategies, call the `boxed()` method on both `self` and + /// `other` to erase the type differences before calling `prop_union()`. + fn prop_union(self, other: Self) -> Union<Self> + where + Self: Sized, + { + Union::new(vec![self, other]) + } + + /// Generate a recursive structure with `self` items as leaves. + /// + /// `recurse` is applied to various strategies that produce the same type + /// as `self` with nesting depth _n_ to create a strategy that produces the + /// same type with nesting depth _n+1_. Generated structures will have a + /// depth between 0 and `depth` and will usually have up to `desired_size` + /// total elements, though they may have more. `expected_branch_size` gives + /// the expected maximum size for any collection which may contain + /// recursive elements and is used to control branch probability to achieve + /// the desired size. Passing a too small value can result in trees vastly + /// larger than desired. + /// + /// Note that `depth` only counts branches; i.e., `depth = 0` is a single + /// leaf, and `depth = 1` is a leaf or a branch containing only leaves. + /// + /// In practise, generated values usually have a lower depth than `depth` + /// (but `depth` is a hard limit) and almost always under + /// `expected_branch_size` (though it is not a hard limit) since the + /// underlying code underestimates probabilities. + /// + /// Shrinking shrinks both the inner values and attempts switching from + /// recursive to non-recursive cases. + /// + /// ## Example + /// + /// ```rust,no_run + /// # #![allow(unused_variables)] + /// use std::collections::HashMap; + /// + /// use proptest::prelude::*; + /// + /// /// Define our own JSON AST type + /// #[derive(Debug, Clone)] + /// enum JsonNode { + /// Null, + /// Bool(bool), + /// Number(f64), + /// String(String), + /// Array(Vec<JsonNode>), + /// Map(HashMap<String, JsonNode>), + /// } + /// + /// # fn main() { + /// # + /// // Define a strategy for generating leaf nodes of the AST + /// let json_leaf = prop_oneof![ + /// Just(JsonNode::Null), + /// prop::bool::ANY.prop_map(JsonNode::Bool), + /// prop::num::f64::ANY.prop_map(JsonNode::Number), + /// ".*".prop_map(JsonNode::String), + /// ]; + /// + /// // Now define a strategy for a whole tree + /// let json_tree = json_leaf.prop_recursive( + /// 4, // No more than 4 branch levels deep + /// 64, // Target around 64 total elements + /// 16, // Each collection is up to 16 elements long + /// |element| prop_oneof![ + /// // NB `element` is an `Arc` and we'll need to reference it twice, + /// // so we clone it the first time. + /// prop::collection::vec(element.clone(), 0..16) + /// .prop_map(JsonNode::Array), + /// prop::collection::hash_map(".*", element, 0..16) + /// .prop_map(JsonNode::Map) + /// ]); + /// # } + /// ``` + fn prop_recursive< + R: Strategy<Value = Self::Value> + 'static, + F: Fn(BoxedStrategy<Self::Value>) -> R, + >( + self, + depth: u32, + desired_size: u32, + expected_branch_size: u32, + recurse: F, + ) -> Recursive<Self::Value, F> + where + Self: Sized + 'static, + { + Recursive::new(self, depth, desired_size, expected_branch_size, recurse) + } + + /// Shuffle the contents of the values produced by this strategy. + /// + /// That is, this modifies a strategy producing a `Vec`, slice, etc, to + /// shuffle the contents of that `Vec`/slice/etc. + /// + /// Initially, the value is fully shuffled. During shrinking, the input + /// value will initially be unchanged while the result will gradually be + /// restored to its original order. Once de-shuffling either completes or + /// is cancelled by calls to `complicate()` pinning it to a particular + /// permutation, the inner value will be simplified. + /// + /// ## Example + /// + /// ``` + /// use proptest::prelude::*; + /// + /// static VALUES: &'static [u32] = &[0, 1, 2, 3, 4]; + /// + /// fn is_permutation(orig: &[u32], mut actual: Vec<u32>) -> bool { + /// actual.sort(); + /// orig == &actual[..] + /// } + /// + /// proptest! { + /// # /* + /// #[test] + /// # */ + /// fn test_is_permutation( + /// ref perm in Just(VALUES.to_owned()).prop_shuffle() + /// ) { + /// assert!(is_permutation(VALUES, perm.clone())); + /// } + /// } + /// # + /// # fn main() { test_is_permutation(); } + /// ``` + fn prop_shuffle(self) -> Shuffle<Self> + where + Self: Sized, + Self::Value: Shuffleable, + { + Shuffle(self) + } + + /// Erases the type of this `Strategy` so it can be passed around as a + /// simple trait object. + /// + /// See also `sboxed()` if this `Strategy` is `Send` and `Sync` and you + /// want to preserve that information. + /// + /// Strategies of this type afford cheap shallow cloning via reference + /// counting by using an `Arc` internally. + fn boxed(self) -> BoxedStrategy<Self::Value> + where + Self: Sized + 'static, + { + BoxedStrategy(Arc::new(BoxedStrategyWrapper(self))) + } + + /// Erases the type of this `Strategy` so it can be passed around as a + /// simple trait object. + /// + /// Unlike `boxed()`, this conversion retains the `Send` and `Sync` traits + /// on the output. + /// + /// Strategies of this type afford cheap shallow cloning via reference + /// counting by using an `Arc` internally. + fn sboxed(self) -> SBoxedStrategy<Self::Value> + where + Self: Sized + Send + Sync + 'static, + { + SBoxedStrategy(Arc::new(BoxedStrategyWrapper(self))) + } + + /// Wraps this strategy to prevent values from being subject to shrinking. + /// + /// Suppressing shrinking is useful when testing things like linear + /// approximation functions. Ordinarily, proptest will tend to shrink the + /// input to the function until the result is just barely outside the + /// acceptable range whereas the original input may have produced a result + /// far outside of it. Since this makes it harder to see what the actual + /// problem is, making the input `NoShrink` allows learning about inputs + /// that produce more incorrect results. + fn no_shrink(self) -> NoShrink<Self> + where + Self: Sized, + { + NoShrink(self) + } +} + +/// A generated value and its associated shrinker. +/// +/// Conceptually, a `ValueTree` represents a spectrum between a "minimally +/// complex" value and a starting, randomly-chosen value. For values such as +/// numbers, this can be thought of as a simple binary search, and this is how +/// the `ValueTree` state machine is defined. +/// +/// The `ValueTree` state machine notionally has three fields: low, current, +/// and high. Initially, low is the "minimally complex" value for the type, and +/// high and current are both the initially chosen value. It can be queried for +/// its current state. When shrinking, the controlling code tries simplifying +/// the value one step. If the test failure still happens with the simplified +/// value, further simplification occurs. Otherwise, the code steps back up +/// towards the prior complexity. +/// +/// The main invariants here are that the "high" value always corresponds to a +/// failing test case, and that repeated calls to `complicate()` will return +/// `false` only once the "current" value has returned to what it was before +/// the last call to `simplify()`. +/// +/// While it would be possible for default do-nothing implementations of +/// `simplify()` and `complicate()` to be provided, this was not done +/// deliberately since the majority of strategies will want to define their own +/// shrinking anyway, and the minority that do not must call it out explicitly +/// by their own implementation. +pub trait ValueTree { + /// The type of the value produced by this `ValueTree`. + type Value: fmt::Debug; + + /// Returns the current value. + fn current(&self) -> Self::Value; + /// Attempts to simplify the current value. Notionally, this sets the + /// "high" value to the current value, and the current value to a "halfway + /// point" between high and low, rounding towards low. + /// + /// Returns whether any state changed as a result of this call. This does + /// not necessarily imply that the value of `current()` has changed, since + /// in the most general case, it is not possible for an implementation to + /// determine this. + /// + /// This call needs to correctly handle being called even immediately after + /// it had been called previously and returned `false`. + fn simplify(&mut self) -> bool; + /// Attempts to partially undo the last simplification. Notionally, this + /// sets the "low" value to one plus the current value, and the current + /// value to a "halfway point" between high and the new low, rounding + /// towards low. + /// + /// Returns whether any state changed as a result of this call. This does + /// not necessarily imply that the value of `current()` has changed, since + /// in the most general case, it is not possible for an implementation to + /// determine this. + /// + /// It is usually expected that, immediately after a call to `simplify()` + /// which returns true, this call will itself return true. However, this is + /// not always the case; in some strategies, particularly those that use + /// some form of rejection sampling, the act of trying to simplify may + /// change the state such that `simplify()` returns true, yet ultimately + /// left the resulting value unchanged, in which case there is nothing left + /// to complicate. + /// + /// This call does not need to gracefully handle being called before + /// `simplify()` was ever called, but does need to correctly handle being + /// called even immediately after it had been called previously and + /// returned `false`. + fn complicate(&mut self) -> bool; +} + +//============================================================================== +// NoShrink +//============================================================================== + +/// Wraps a `Strategy` or `ValueTree` to suppress shrinking of generated +/// values. +/// +/// See `Strategy::no_shrink()` for more details. +#[derive(Clone, Copy, Debug)] +#[must_use = "strategies do nothing unless used"] +pub struct NoShrink<T>(T); + +impl<T: Strategy> Strategy for NoShrink<T> { + type Tree = NoShrink<T::Tree>; + type Value = T::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + self.0.new_tree(runner).map(NoShrink) + } +} + +impl<T: ValueTree> ValueTree for NoShrink<T> { + type Value = T::Value; + + fn current(&self) -> T::Value { + self.0.current() + } + + fn simplify(&mut self) -> bool { + false + } + fn complicate(&mut self) -> bool { + false + } +} + +//============================================================================== +// Trait objects +//============================================================================== + +macro_rules! proxy_strategy { + ($typ:ty $(, $lt:tt)*) => { + impl<$($lt,)* S : Strategy + ?Sized> Strategy for $typ { + type Tree = S::Tree; + type Value = S::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + (**self).new_tree(runner) + } + } + }; +} +proxy_strategy!(Box<S>); +proxy_strategy!(&'a S, 'a); +proxy_strategy!(&'a mut S, 'a); +proxy_strategy!(Rc<S>); +proxy_strategy!(Arc<S>); + +impl<T: ValueTree + ?Sized> ValueTree for Box<T> { + type Value = T::Value; + fn current(&self) -> Self::Value { + (**self).current() + } + fn simplify(&mut self) -> bool { + (**self).simplify() + } + fn complicate(&mut self) -> bool { + (**self).complicate() + } +} + +/// A boxed `ValueTree`. +type BoxedVT<T> = Box<dyn ValueTree<Value = T>>; + +/// A boxed `Strategy` trait object as produced by `Strategy::boxed()`. +/// +/// Strategies of this type afford cheap shallow cloning via reference +/// counting by using an `Arc` internally. +#[derive(Debug)] +#[must_use = "strategies do nothing unless used"] +pub struct BoxedStrategy<T>(Arc<dyn Strategy<Value = T, Tree = BoxedVT<T>>>); + +/// A boxed `Strategy` trait object which is also `Sync` and +/// `Send`, as produced by `Strategy::sboxed()`. +/// +/// Strategies of this type afford cheap shallow cloning via reference +/// counting by using an `Arc` internally. +#[derive(Debug)] +#[must_use = "strategies do nothing unless used"] +pub struct SBoxedStrategy<T>( + Arc<dyn Strategy<Value = T, Tree = BoxedVT<T>> + Sync + Send>, +); + +impl<T> Clone for BoxedStrategy<T> { + fn clone(&self) -> Self { + BoxedStrategy(Arc::clone(&self.0)) + } +} + +impl<T> Clone for SBoxedStrategy<T> { + fn clone(&self) -> Self { + SBoxedStrategy(Arc::clone(&self.0)) + } +} + +impl<T: fmt::Debug> Strategy for BoxedStrategy<T> { + type Tree = BoxedVT<T>; + type Value = T; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + self.0.new_tree(runner) + } + + // Optimization: Don't rebox the strategy. + + fn boxed(self) -> BoxedStrategy<Self::Value> + where + Self: Sized + 'static, + { + self + } +} + +impl<T: fmt::Debug> Strategy for SBoxedStrategy<T> { + type Tree = BoxedVT<T>; + type Value = T; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + self.0.new_tree(runner) + } + + // Optimization: Don't rebox the strategy. + + fn sboxed(self) -> SBoxedStrategy<Self::Value> + where + Self: Sized + Send + Sync + 'static, + { + self + } + + fn boxed(self) -> BoxedStrategy<Self::Value> + where + Self: Sized + 'static, + { + BoxedStrategy(self.0) + } +} + +#[derive(Debug)] +struct BoxedStrategyWrapper<T>(T); +impl<T: Strategy> Strategy for BoxedStrategyWrapper<T> +where + T::Tree: 'static, +{ + type Tree = Box<dyn ValueTree<Value = T::Value>>; + type Value = T::Value; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + Ok(Box::new(self.0.new_tree(runner)?)) + } +} + +//============================================================================== +// Sanity checking +//============================================================================== + +/// Options passed to `check_strategy_sanity()`. +#[derive(Clone, Copy, Debug)] +pub struct CheckStrategySanityOptions { + /// If true (the default), require that `complicate()` return `true` at + /// least once after any call to `simplify()` which itself returns once. + /// + /// This property is not required by contract, but many strategies are + /// designed in a way that this is expected to hold. + pub strict_complicate_after_simplify: bool, + + /// If true, cause local rejects to return an error instead of retrying. + /// Defaults to false. Useful for testing behaviors around error handling. + pub error_on_local_rejects: bool, + + // Needs to be public for FRU syntax. + #[allow(missing_docs)] + #[doc(hidden)] + pub _non_exhaustive: (), +} + +impl Default for CheckStrategySanityOptions { + fn default() -> Self { + CheckStrategySanityOptions { + strict_complicate_after_simplify: true, + error_on_local_rejects: false, + _non_exhaustive: (), + } + } +} + +/// Run some tests on the given `Strategy` to ensure that it upholds the +/// simplify/complicate contracts. +/// +/// This is used to internally test proptest, but is made generally available +/// for external implementations to use as well. +/// +/// `options` can be passed to configure the test; if `None`, the defaults are +/// used. Note that the defaults check for certain properties which are **not** +/// actually required by the `Strategy` and `ValueTree` contracts; if you think +/// your code is right but it fails the test, consider whether a non-default +/// configuration is necessary. +/// +/// This can work with fallible strategies, but limits how many times it will +/// retry failures. +pub fn check_strategy_sanity<S: Strategy>( + strategy: S, + options: Option<CheckStrategySanityOptions>, +) where + S::Tree: Clone + fmt::Debug, + S::Value: cmp::PartialEq, +{ + // Like assert_eq!, but also pass if both values do not equal themselves. + // This allows the test to work correctly with things like NaN. + macro_rules! assert_same { + ($a:expr, $b:expr, $($stuff:tt)*) => { { + let a = $a; + let b = $b; + if a == a || b == b { + assert_eq!(a, b, $($stuff)*); + } + } } + } + + let options = options.unwrap_or_else(CheckStrategySanityOptions::default); + let mut config = Config::default(); + if options.error_on_local_rejects { + config.max_local_rejects = 0; + } + let mut runner = TestRunner::new(config); + + for _ in 0..1024 { + let mut gen_tries = 0; + let mut state; + loop { + let err = match strategy.new_tree(&mut runner) { + Ok(s) => { + state = s; + break; + } + Err(e) => e, + }; + + gen_tries += 1; + if gen_tries > 100 { + panic!( + "Strategy passed to check_strategy_sanity failed \ + to generate a value over 100 times in a row; \ + last failure reason: {}", + err + ); + } + } + + { + let mut state = state.clone(); + let mut count = 0; + while state.simplify() || state.complicate() { + count += 1; + if count > 65536 { + panic!( + "Failed to converge on any value. State:\n{:#?}", + state + ); + } + } + } + + let mut num_simplifies = 0; + let mut before_simplified; + loop { + before_simplified = state.clone(); + if !state.simplify() { + break; + } + + let mut complicated = state.clone(); + let before_complicated = state.clone(); + if options.strict_complicate_after_simplify { + assert!( + complicated.complicate(), + "complicate() returned false immediately after \ + simplify() returned true. internal state after \ + {} calls to simplify():\n\ + {:#?}\n\ + simplified to:\n\ + {:#?}\n\ + complicated to:\n\ + {:#?}", + num_simplifies, + before_simplified, + state, + complicated + ); + } + + let mut prev_complicated = complicated.clone(); + let mut num_complications = 0; + loop { + if !complicated.complicate() { + break; + } + prev_complicated = complicated.clone(); + num_complications += 1; + + if num_complications > 65_536 { + panic!( + "complicate() returned true over 65536 times in a \ + row; aborting due to possible infinite loop. \ + If this is not an infinite loop, it may be \ + necessary to reconsider how shrinking is \ + implemented or use a simpler test strategy. \ + Internal state:\n{:#?}", + state + ); + } + } + + assert_same!( + before_simplified.current(), + complicated.current(), + "Calling simplify(), then complicate() until it \ + returned false, did not return to the value before \ + simplify. Expected:\n\ + {:#?}\n\ + Actual:\n\ + {:#?}\n\ + Internal state after {} calls to simplify():\n\ + {:#?}\n\ + Internal state after another call to simplify():\n\ + {:#?}\n\ + Internal state after {} subsequent calls to \ + complicate():\n\ + {:#?}", + before_simplified.current(), + complicated.current(), + num_simplifies, + before_simplified, + before_complicated, + num_complications + 1, + complicated + ); + + for iter in 1..16 { + assert_same!( + prev_complicated.current(), + complicated.current(), + "complicate() returned false but changed the output \ + value anyway.\n\ + Old value:\n\ + {:#?}\n\ + New value:\n\ + {:#?}\n\ + Old internal state:\n\ + {:#?}\n\ + New internal state after {} calls to complicate()\ + including the :\n\ + {:#?}", + prev_complicated.current(), + complicated.current(), + prev_complicated, + iter, + complicated + ); + + assert!( + !complicated.complicate(), + "complicate() returned true after having returned \ + false;\n\ + Internal state before:\n{:#?}\n\ + Internal state after calling complicate() {} times:\n\ + {:#?}", + prev_complicated, + iter + 1, + complicated + ); + } + + num_simplifies += 1; + if num_simplifies > 65_536 { + panic!( + "simplify() returned true over 65536 times in a row, \ + aborting due to possible infinite loop. If this is not \ + an infinite loop, it may be necessary to reconsider \ + how shrinking is implemented or use a simpler test \ + strategy. Internal state:\n{:#?}", + state + ); + } + } + + for iter in 0..16 { + assert_same!( + before_simplified.current(), + state.current(), + "simplify() returned false but changed the output \ + value anyway.\n\ + Old value:\n\ + {:#?}\n\ + New value:\n\ + {:#?}\n\ + Previous internal state:\n\ + {:#?}\n\ + New internal state after calling simplify() {} times:\n\ + {:#?}", + before_simplified.current(), + state.current(), + before_simplified, + iter, + state + ); + + if state.simplify() { + panic!( + "simplify() returned true after having returned false. \ + Previous internal state:\n\ + {:#?}\n\ + New internal state after calling simplify() {} times:\n\ + {:#?}", + before_simplified, + iter + 1, + state + ); + } + } + } +} 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() + } + } +} |