diff options
Diffstat (limited to 'vendor/proptest/src/strategy/traits.rs')
-rw-r--r-- | vendor/proptest/src/strategy/traits.rs | 1054 |
1 files changed, 1054 insertions, 0 deletions
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 + ); + } + } + } +} |