proptest/strategy/traits.rs
1//-
2// Copyright 2017, 2018 The proptest developers
3//
4// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. This file may not be copied, modified, or distributed
8// except according to those terms.
9
10use crate::std_facade::{fmt, Arc, Box, Rc};
11use core::cmp;
12
13use crate::strategy::*;
14use crate::test_runner::*;
15
16//==============================================================================
17// Traits
18//==============================================================================
19
20/// A new [`ValueTree`] from a [`Strategy`] when [`Ok`] or otherwise [`Err`]
21/// when a new value-tree can not be produced for some reason such as
22/// in the case of filtering with a predicate which always returns false.
23/// You should pass in your strategy as the type parameter.
24///
25/// [`Strategy`]: trait.Strategy.html
26/// [`ValueTree`]: trait.ValueTree.html
27/// [`Ok`]: https://doc.rust-lang.org/nightly/std/result/enum.Result.html#variant.Ok
28/// [`Err`]: https://doc.rust-lang.org/nightly/std/result/enum.Result.html#variant.Err
29pub type NewTree<S> = Result<<S as Strategy>::Tree, Reason>;
30
31/// A strategy for producing arbitrary values of a given type.
32///
33/// `fmt::Debug` is a hard requirement for all strategies currently due to
34/// `prop_flat_map()`. This constraint will be removed when specialisation
35/// becomes stable.
36#[must_use = "strategies do nothing unless used"]
37pub trait Strategy: fmt::Debug {
38 /// The value tree generated by this `Strategy`.
39 type Tree: ValueTree<Value = Self::Value>;
40
41 /// The type of value used by functions under test generated by this Strategy.
42 ///
43 /// This corresponds to the same type as the associated type `Value`
44 /// in `Self::Tree`. It is provided here to simplify usage particularly
45 /// in conjunction with `-> impl Strategy<Value = MyType>`.
46 type Value: fmt::Debug;
47
48 /// Generate a new value tree from the given runner.
49 ///
50 /// This may fail if there are constraints on the generated value and the
51 /// generator is unable to produce anything that satisfies them. Any
52 /// failure is wrapped in `TestError::Abort`.
53 ///
54 /// This method is generally expected to be deterministic. That is, given a
55 /// `TestRunner` with its RNG in a particular state, this should produce an
56 /// identical `ValueTree` every time. Non-deterministic strategies do not
57 /// cause problems during normal operation, but they do break failure
58 /// persistence since it is implemented by simply saving the seed used to
59 /// generate the test case.
60 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self>;
61
62 /// Returns a strategy which produces values transformed by the function
63 /// `fun`.
64 ///
65 /// There is no need (or possibility, for that matter) to define how the
66 /// output is to be shrunken. Shrinking continues to take place in terms of
67 /// the source value.
68 ///
69 /// `fun` should be a deterministic function. That is, for a given input
70 /// value, it should produce an equivalent output value on every call.
71 /// Proptest assumes that it can call the function as many times as needed
72 /// to generate as many identical values as needed. For this reason, `F` is
73 /// `Fn` rather than `FnMut`.
74 fn prop_map<O: fmt::Debug, F: Fn(Self::Value) -> O>(
75 self,
76 fun: F,
77 ) -> Map<Self, F>
78 where
79 Self: Sized,
80 {
81 Map {
82 source: self,
83 fun: Arc::new(fun),
84 }
85 }
86
87 /// Returns a strategy which produces values of type `O` by transforming
88 /// `Self` with `Into<O>`.
89 ///
90 /// You should always prefer this operation instead of `prop_map` when
91 /// you can as it is both clearer and also currently more efficient.
92 ///
93 /// There is no need (or possibility, for that matter) to define how the
94 /// output is to be shrunken. Shrinking continues to take place in terms of
95 /// the source value.
96 fn prop_map_into<O: fmt::Debug>(self) -> MapInto<Self, O>
97 where
98 Self: Sized,
99 Self::Value: Into<O>,
100 {
101 MapInto::new(self)
102 }
103
104 /// Returns a strategy which produces values transformed by the function
105 /// `fun`, which is additionally given a random number generator.
106 ///
107 /// This is exactly like `prop_map()` except for the addition of the second
108 /// argument to the function. This allows introducing chaotic variations to
109 /// generated values that are not easily expressed otherwise while allowing
110 /// shrinking to proceed reasonably.
111 ///
112 /// During shrinking, `fun` is always called with an identical random
113 /// number generator, so if it is a pure function it will always perform
114 /// the same perturbation.
115 ///
116 /// ## Example
117 ///
118 /// ```
119 /// // The prelude also gets us the `Rng` trait.
120 /// use proptest::prelude::*;
121 ///
122 /// proptest! {
123 /// #[test]
124 /// fn test_something(a in (0i32..10).prop_perturb(
125 /// // Perturb the integer `a` (range 0..10) to a pair of that
126 /// // integer and another that's ± 10 of it.
127 /// // Note that this particular case would be better implemented as
128 /// // `(0i32..10, -10i32..10).prop_map(|(a, b)| (a, a + b))`
129 /// // but is shown here for simplicity.
130 /// |centre, rng| (centre, centre + rng.gen_range(-10, 10))))
131 /// {
132 /// // Test stuff
133 /// }
134 /// }
135 /// # fn main() { }
136 /// ```
137 fn prop_perturb<O: fmt::Debug, F: Fn(Self::Value, TestRng) -> O>(
138 self,
139 fun: F,
140 ) -> Perturb<Self, F>
141 where
142 Self: Sized,
143 {
144 Perturb {
145 source: self,
146 fun: Arc::new(fun),
147 }
148 }
149
150 /// Maps values produced by this strategy into new strategies and picks
151 /// values from those strategies.
152 ///
153 /// `fun` is used to transform the values produced by this strategy into
154 /// other strategies. Values are then chosen from the derived strategies.
155 /// Shrinking proceeds by shrinking individual values as well as shrinking
156 /// the input used to generate the internal strategies.
157 ///
158 /// ## Shrinking
159 ///
160 /// In the case of test failure, shrinking will not only shrink the output
161 /// from the combinator itself, but also the input, i.e., the strategy used
162 /// to generate the output itself. Doing this requires searching the new
163 /// derived strategy for a new failing input. The combinator will generate
164 /// up to `Config::cases` values for this search.
165 ///
166 /// As a result, nested `prop_flat_map`/`Flatten` combinators risk
167 /// exponential run time on this search for new failing values. To ensure
168 /// that test failures occur within a reasonable amount of time, all of
169 /// these combinators share a single "flat map regen" counter, and will
170 /// stop generating new values if it exceeds `Config::max_flat_map_regens`.
171 ///
172 /// ## Example
173 ///
174 /// Generate two integers, where the second is always less than the first,
175 /// without using filtering:
176 ///
177 /// ```
178 /// use proptest::prelude::*;
179 ///
180 /// proptest! {
181 /// # /*
182 /// #[test]
183 /// # */
184 /// fn test_two(
185 /// // Pick integers in the 1..65536 range, and derive a strategy
186 /// // which emits a tuple of that integer and another one which is
187 /// // some value less than it.
188 /// (a, b) in (1..65536).prop_flat_map(|a| (Just(a), 0..a))
189 /// ) {
190 /// prop_assert!(b < a);
191 /// }
192 /// }
193 /// #
194 /// # fn main() { test_two(); }
195 /// ```
196 ///
197 /// ## Choosing the right flat-map
198 ///
199 /// `Strategy` has three "flat-map" combinators. They look very similar at
200 /// first, and can be used to produce superficially identical test results.
201 /// For example, the following three expressions all produce inputs which
202 /// are 2-tuples `(a,b)` where the `b` component is less than `a`.
203 ///
204 /// ```no_run
205 /// # #![allow(unused_variables)]
206 /// use proptest::prelude::*;
207 ///
208 /// let flat_map = (1..10).prop_flat_map(|a| (Just(a), 0..a));
209 /// let ind_flat_map = (1..10).prop_ind_flat_map(|a| (Just(a), 0..a));
210 /// let ind_flat_map2 = (1..10).prop_ind_flat_map2(|a| 0..a);
211 /// ```
212 ///
213 /// The three do differ however in terms of how they shrink.
214 ///
215 /// For `flat_map`, both `a` and `b` will shrink, and the invariant that
216 /// `b < a` is maintained. This is a "dependent" or "higher-order" strategy
217 /// in that it remembers that the strategy for choosing `b` is dependent on
218 /// the value chosen for `a`.
219 ///
220 /// For `ind_flat_map`, the invariant `b < a` is maintained, but only
221 /// because `a` does not shrink. This is due to the fact that the
222 /// dependency between the strategies is not tracked; `a` is simply seen as
223 /// a constant.
224 ///
225 /// Finally, for `ind_flat_map2`, the invariant `b < a` is _not_
226 /// maintained, because `a` can shrink independently of `b`, again because
227 /// the dependency between the two variables is not tracked, but in this
228 /// case the derivation of `a` is still exposed to the shrinking system.
229 ///
230 /// The use-cases for the independent flat-map variants is pretty narrow.
231 /// For the majority of cases where invariants need to be maintained and
232 /// you want all components to shrink, `prop_flat_map` is the way to go.
233 /// `prop_ind_flat_map` makes the most sense when the input to the map
234 /// function is not exposed in the output and shrinking across strategies
235 /// is not expected to be useful. `prop_ind_flat_map2` is useful for using
236 /// related values as starting points while not constraining them to that
237 /// relation.
238 fn prop_flat_map<S: Strategy, F: Fn(Self::Value) -> S>(
239 self,
240 fun: F,
241 ) -> Flatten<Map<Self, F>>
242 where
243 Self: Sized,
244 {
245 Flatten::new(Map {
246 source: self,
247 fun: Arc::new(fun),
248 })
249 }
250
251 /// Maps values produced by this strategy into new strategies and picks
252 /// values from those strategies while considering the new strategies to be
253 /// independent.
254 ///
255 /// This is very similar to `prop_flat_map()`, but shrinking will *not*
256 /// attempt to shrink the input that produces the derived strategies. This
257 /// is appropriate for when the derived strategies already fully shrink in
258 /// the desired way.
259 ///
260 /// In most cases, you want `prop_flat_map()`.
261 ///
262 /// See `prop_flat_map()` for a more detailed explanation on how the
263 /// three flat-map combinators differ.
264 fn prop_ind_flat_map<S: Strategy, F: Fn(Self::Value) -> S>(
265 self,
266 fun: F,
267 ) -> IndFlatten<Map<Self, F>>
268 where
269 Self: Sized,
270 {
271 IndFlatten(Map {
272 source: self,
273 fun: Arc::new(fun),
274 })
275 }
276
277 /// Similar to `prop_ind_flat_map()`, but produces 2-tuples with the input
278 /// generated from `self` in slot 0 and the derived strategy in slot 1.
279 ///
280 /// See `prop_flat_map()` for a more detailed explanation on how the
281 /// three flat-map combinators differ.
282 fn prop_ind_flat_map2<S: Strategy, F: Fn(Self::Value) -> S>(
283 self,
284 fun: F,
285 ) -> IndFlattenMap<Self, F>
286 where
287 Self: Sized,
288 {
289 IndFlattenMap {
290 source: self,
291 fun: Arc::new(fun),
292 }
293 }
294
295 /// Returns a strategy which only produces values accepted by `fun`.
296 ///
297 /// This results in a very naïve form of rejection sampling and should only
298 /// be used if (a) relatively few values will actually be rejected; (b) it
299 /// isn't easy to express what you want by using another strategy and/or
300 /// `map()`.
301 ///
302 /// There are a lot of downsides to this form of filtering. It slows
303 /// testing down, since values must be generated but then discarded.
304 /// Proptest only allows a limited number of rejects this way (across the
305 /// entire `TestRunner`). Rejection can interfere with shrinking;
306 /// particularly, complex filters may largely or entirely prevent shrinking
307 /// from substantially altering the original value.
308 ///
309 /// Local rejection sampling is still preferable to rejecting the entire
310 /// input to a test (via `TestCaseError::Reject`), however, and the default
311 /// number of local rejections allowed is much higher than the number of
312 /// whole-input rejections.
313 ///
314 /// `whence` is used to record where and why the rejection occurred.
315 fn prop_filter<R: Into<Reason>, F: Fn(&Self::Value) -> bool>(
316 self,
317 whence: R,
318 fun: F,
319 ) -> Filter<Self, F>
320 where
321 Self: Sized,
322 {
323 Filter::new(self, whence.into(), fun)
324 }
325
326 /// Returns a strategy which only produces transformed values where `fun`
327 /// returns `Some(value)` and rejects those where `fun` returns `None`.
328 ///
329 /// Using this method is preferable to using `.prop_map(..).prop_filter(..)`.
330 ///
331 /// This results in a very naïve form of rejection sampling and should only
332 /// be used if (a) relatively few values will actually be rejected; (b) it
333 /// isn't easy to express what you want by using another strategy and/or
334 /// `map()`.
335 ///
336 /// There are a lot of downsides to this form of filtering. It slows
337 /// testing down, since values must be generated but then discarded.
338 /// Proptest only allows a limited number of rejects this way (across the
339 /// entire `TestRunner`). Rejection can interfere with shrinking;
340 /// particularly, complex filters may largely or entirely prevent shrinking
341 /// from substantially altering the original value.
342 ///
343 /// Local rejection sampling is still preferable to rejecting the entire
344 /// input to a test (via `TestCaseError::Reject`), however, and the default
345 /// number of local rejections allowed is much higher than the number of
346 /// whole-input rejections.
347 ///
348 /// `whence` is used to record where and why the rejection occurred.
349 fn prop_filter_map<F: Fn(Self::Value) -> Option<O>, O: fmt::Debug>(
350 self,
351 whence: impl Into<Reason>,
352 fun: F,
353 ) -> FilterMap<Self, F>
354 where
355 Self: Sized,
356 {
357 FilterMap::new(self, whence.into(), fun)
358 }
359
360 /// Returns a strategy which picks uniformly from `self` and `other`.
361 ///
362 /// When shrinking, if a value from `other` was originally chosen but that
363 /// value can be shrunken no further, it switches to a value from `self`
364 /// and starts shrinking that.
365 ///
366 /// Be aware that chaining `prop_union` calls will result in a very
367 /// right-skewed distribution. If this is not what you want, you can call
368 /// the `.or()` method on the `Union` to add more values to the same union,
369 /// or directly call `Union::new()`.
370 ///
371 /// Both `self` and `other` must be of the same type. To combine
372 /// heterogeneous strategies, call the `boxed()` method on both `self` and
373 /// `other` to erase the type differences before calling `prop_union()`.
374 fn prop_union(self, other: Self) -> Union<Self>
375 where
376 Self: Sized,
377 {
378 Union::new(vec![self, other])
379 }
380
381 /// Generate a recursive structure with `self` items as leaves.
382 ///
383 /// `recurse` is applied to various strategies that produce the same type
384 /// as `self` with nesting depth _n_ to create a strategy that produces the
385 /// same type with nesting depth _n+1_. Generated structures will have a
386 /// depth between 0 and `depth` and will usually have up to `desired_size`
387 /// total elements, though they may have more. `expected_branch_size` gives
388 /// the expected maximum size for any collection which may contain
389 /// recursive elements and is used to control branch probability to achieve
390 /// the desired size. Passing a too small value can result in trees vastly
391 /// larger than desired.
392 ///
393 /// Note that `depth` only counts branches; i.e., `depth = 0` is a single
394 /// leaf, and `depth = 1` is a leaf or a branch containing only leaves.
395 ///
396 /// In practise, generated values usually have a lower depth than `depth`
397 /// (but `depth` is a hard limit) and almost always under
398 /// `expected_branch_size` (though it is not a hard limit) since the
399 /// underlying code underestimates probabilities.
400 ///
401 /// Shrinking shrinks both the inner values and attempts switching from
402 /// recursive to non-recursive cases.
403 ///
404 /// ## Example
405 ///
406 /// ```rust,no_run
407 /// # #![allow(unused_variables)]
408 /// use std::collections::HashMap;
409 ///
410 /// use proptest::prelude::*;
411 ///
412 /// /// Define our own JSON AST type
413 /// #[derive(Debug, Clone)]
414 /// enum JsonNode {
415 /// Null,
416 /// Bool(bool),
417 /// Number(f64),
418 /// String(String),
419 /// Array(Vec<JsonNode>),
420 /// Map(HashMap<String, JsonNode>),
421 /// }
422 ///
423 /// # fn main() {
424 /// #
425 /// // Define a strategy for generating leaf nodes of the AST
426 /// let json_leaf = prop_oneof![
427 /// Just(JsonNode::Null),
428 /// prop::bool::ANY.prop_map(JsonNode::Bool),
429 /// prop::num::f64::ANY.prop_map(JsonNode::Number),
430 /// ".*".prop_map(JsonNode::String),
431 /// ];
432 ///
433 /// // Now define a strategy for a whole tree
434 /// let json_tree = json_leaf.prop_recursive(
435 /// 4, // No more than 4 branch levels deep
436 /// 64, // Target around 64 total elements
437 /// 16, // Each collection is up to 16 elements long
438 /// |element| prop_oneof![
439 /// // NB `element` is an `Arc` and we'll need to reference it twice,
440 /// // so we clone it the first time.
441 /// prop::collection::vec(element.clone(), 0..16)
442 /// .prop_map(JsonNode::Array),
443 /// prop::collection::hash_map(".*", element, 0..16)
444 /// .prop_map(JsonNode::Map)
445 /// ]);
446 /// # }
447 /// ```
448 fn prop_recursive<
449 R: Strategy<Value = Self::Value> + 'static,
450 F: Fn(BoxedStrategy<Self::Value>) -> R,
451 >(
452 self,
453 depth: u32,
454 desired_size: u32,
455 expected_branch_size: u32,
456 recurse: F,
457 ) -> Recursive<Self::Value, F>
458 where
459 Self: Sized + 'static,
460 {
461 Recursive::new(self, depth, desired_size, expected_branch_size, recurse)
462 }
463
464 /// Shuffle the contents of the values produced by this strategy.
465 ///
466 /// That is, this modifies a strategy producing a `Vec`, slice, etc, to
467 /// shuffle the contents of that `Vec`/slice/etc.
468 ///
469 /// Initially, the value is fully shuffled. During shrinking, the input
470 /// value will initially be unchanged while the result will gradually be
471 /// restored to its original order. Once de-shuffling either completes or
472 /// is cancelled by calls to `complicate()` pinning it to a particular
473 /// permutation, the inner value will be simplified.
474 ///
475 /// ## Example
476 ///
477 /// ```
478 /// use proptest::prelude::*;
479 ///
480 /// static VALUES: &'static [u32] = &[0, 1, 2, 3, 4];
481 ///
482 /// fn is_permutation(orig: &[u32], mut actual: Vec<u32>) -> bool {
483 /// actual.sort();
484 /// orig == &actual[..]
485 /// }
486 ///
487 /// proptest! {
488 /// # /*
489 /// #[test]
490 /// # */
491 /// fn test_is_permutation(
492 /// ref perm in Just(VALUES.to_owned()).prop_shuffle()
493 /// ) {
494 /// assert!(is_permutation(VALUES, perm.clone()));
495 /// }
496 /// }
497 /// #
498 /// # fn main() { test_is_permutation(); }
499 /// ```
500 fn prop_shuffle(self) -> Shuffle<Self>
501 where
502 Self: Sized,
503 Self::Value: Shuffleable,
504 {
505 Shuffle(self)
506 }
507
508 /// Erases the type of this `Strategy` so it can be passed around as a
509 /// simple trait object.
510 ///
511 /// See also `sboxed()` if this `Strategy` is `Send` and `Sync` and you
512 /// want to preserve that information.
513 ///
514 /// Strategies of this type afford cheap shallow cloning via reference
515 /// counting by using an `Arc` internally.
516 fn boxed(self) -> BoxedStrategy<Self::Value>
517 where
518 Self: Sized + 'static,
519 {
520 BoxedStrategy(Arc::new(BoxedStrategyWrapper(self)))
521 }
522
523 /// Erases the type of this `Strategy` so it can be passed around as a
524 /// simple trait object.
525 ///
526 /// Unlike `boxed()`, this conversion retains the `Send` and `Sync` traits
527 /// on the output.
528 ///
529 /// Strategies of this type afford cheap shallow cloning via reference
530 /// counting by using an `Arc` internally.
531 fn sboxed(self) -> SBoxedStrategy<Self::Value>
532 where
533 Self: Sized + Send + Sync + 'static,
534 {
535 SBoxedStrategy(Arc::new(BoxedStrategyWrapper(self)))
536 }
537
538 /// Wraps this strategy to prevent values from being subject to shrinking.
539 ///
540 /// Suppressing shrinking is useful when testing things like linear
541 /// approximation functions. Ordinarily, proptest will tend to shrink the
542 /// input to the function until the result is just barely outside the
543 /// acceptable range whereas the original input may have produced a result
544 /// far outside of it. Since this makes it harder to see what the actual
545 /// problem is, making the input `NoShrink` allows learning about inputs
546 /// that produce more incorrect results.
547 fn no_shrink(self) -> NoShrink<Self>
548 where
549 Self: Sized,
550 {
551 NoShrink(self)
552 }
553}
554
555/// A generated value and its associated shrinker.
556///
557/// Conceptually, a `ValueTree` represents a spectrum between a "minimally
558/// complex" value and a starting, randomly-chosen value. For values such as
559/// numbers, this can be thought of as a simple binary search, and this is how
560/// the `ValueTree` state machine is defined.
561///
562/// The `ValueTree` state machine notionally has three fields: low, current,
563/// and high. Initially, low is the "minimally complex" value for the type, and
564/// high and current are both the initially chosen value. It can be queried for
565/// its current state. When shrinking, the controlling code tries simplifying
566/// the value one step. If the test failure still happens with the simplified
567/// value, further simplification occurs. Otherwise, the code steps back up
568/// towards the prior complexity.
569///
570/// The main invariants here are that the "high" value always corresponds to a
571/// failing test case, and that repeated calls to `complicate()` will return
572/// `false` only once the "current" value has returned to what it was before
573/// the last call to `simplify()`.
574///
575/// While it would be possible for default do-nothing implementations of
576/// `simplify()` and `complicate()` to be provided, this was not done
577/// deliberately since the majority of strategies will want to define their own
578/// shrinking anyway, and the minority that do not must call it out explicitly
579/// by their own implementation.
580pub trait ValueTree {
581 /// The type of the value produced by this `ValueTree`.
582 type Value: fmt::Debug;
583
584 /// Returns the current value.
585 fn current(&self) -> Self::Value;
586 /// Attempts to simplify the current value. Notionally, this sets the
587 /// "high" value to the current value, and the current value to a "halfway
588 /// point" between high and low, rounding towards low.
589 ///
590 /// Returns whether any state changed as a result of this call. This does
591 /// not necessarily imply that the value of `current()` has changed, since
592 /// in the most general case, it is not possible for an implementation to
593 /// determine this.
594 ///
595 /// This call needs to correctly handle being called even immediately after
596 /// it had been called previously and returned `false`.
597 fn simplify(&mut self) -> bool;
598 /// Attempts to partially undo the last simplification. Notionally, this
599 /// sets the "low" value to one plus the current value, and the current
600 /// value to a "halfway point" between high and the new low, rounding
601 /// towards low.
602 ///
603 /// Returns whether any state changed as a result of this call. This does
604 /// not necessarily imply that the value of `current()` has changed, since
605 /// in the most general case, it is not possible for an implementation to
606 /// determine this.
607 ///
608 /// It is usually expected that, immediately after a call to `simplify()`
609 /// which returns true, this call will itself return true. However, this is
610 /// not always the case; in some strategies, particularly those that use
611 /// some form of rejection sampling, the act of trying to simplify may
612 /// change the state such that `simplify()` returns true, yet ultimately
613 /// left the resulting value unchanged, in which case there is nothing left
614 /// to complicate.
615 ///
616 /// This call does not need to gracefully handle being called before
617 /// `simplify()` was ever called, but does need to correctly handle being
618 /// called even immediately after it had been called previously and
619 /// returned `false`.
620 fn complicate(&mut self) -> bool;
621}
622
623//==============================================================================
624// NoShrink
625//==============================================================================
626
627/// Wraps a `Strategy` or `ValueTree` to suppress shrinking of generated
628/// values.
629///
630/// See `Strategy::no_shrink()` for more details.
631#[derive(Clone, Copy, Debug)]
632#[must_use = "strategies do nothing unless used"]
633pub struct NoShrink<T>(T);
634
635impl<T: Strategy> Strategy for NoShrink<T> {
636 type Tree = NoShrink<T::Tree>;
637 type Value = T::Value;
638
639 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
640 self.0.new_tree(runner).map(NoShrink)
641 }
642}
643
644impl<T: ValueTree> ValueTree for NoShrink<T> {
645 type Value = T::Value;
646
647 fn current(&self) -> T::Value {
648 self.0.current()
649 }
650
651 fn simplify(&mut self) -> bool {
652 false
653 }
654 fn complicate(&mut self) -> bool {
655 false
656 }
657}
658
659//==============================================================================
660// Trait objects
661//==============================================================================
662
663macro_rules! proxy_strategy {
664 ($typ:ty $(, $lt:tt)*) => {
665 impl<$($lt,)* S : Strategy + ?Sized> Strategy for $typ {
666 type Tree = S::Tree;
667 type Value = S::Value;
668
669 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
670 (**self).new_tree(runner)
671 }
672 }
673 };
674}
675proxy_strategy!(Box<S>);
676proxy_strategy!(&'a S, 'a);
677proxy_strategy!(&'a mut S, 'a);
678proxy_strategy!(Rc<S>);
679proxy_strategy!(Arc<S>);
680
681impl<T: ValueTree + ?Sized> ValueTree for Box<T> {
682 type Value = T::Value;
683 fn current(&self) -> Self::Value {
684 (**self).current()
685 }
686 fn simplify(&mut self) -> bool {
687 (**self).simplify()
688 }
689 fn complicate(&mut self) -> bool {
690 (**self).complicate()
691 }
692}
693
694/// A boxed `ValueTree`.
695type BoxedVT<T> = Box<dyn ValueTree<Value = T>>;
696
697/// A boxed `Strategy` trait object as produced by `Strategy::boxed()`.
698///
699/// Strategies of this type afford cheap shallow cloning via reference
700/// counting by using an `Arc` internally.
701#[derive(Debug)]
702#[must_use = "strategies do nothing unless used"]
703pub struct BoxedStrategy<T>(Arc<dyn Strategy<Value = T, Tree = BoxedVT<T>>>);
704
705/// A boxed `Strategy` trait object which is also `Sync` and
706/// `Send`, as produced by `Strategy::sboxed()`.
707///
708/// Strategies of this type afford cheap shallow cloning via reference
709/// counting by using an `Arc` internally.
710#[derive(Debug)]
711#[must_use = "strategies do nothing unless used"]
712pub struct SBoxedStrategy<T>(
713 Arc<dyn Strategy<Value = T, Tree = BoxedVT<T>> + Sync + Send>,
714);
715
716impl<T> Clone for BoxedStrategy<T> {
717 fn clone(&self) -> Self {
718 BoxedStrategy(Arc::clone(&self.0))
719 }
720}
721
722impl<T> Clone for SBoxedStrategy<T> {
723 fn clone(&self) -> Self {
724 SBoxedStrategy(Arc::clone(&self.0))
725 }
726}
727
728impl<T: fmt::Debug> Strategy for BoxedStrategy<T> {
729 type Tree = BoxedVT<T>;
730 type Value = T;
731
732 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
733 self.0.new_tree(runner)
734 }
735
736 // Optimization: Don't rebox the strategy.
737
738 fn boxed(self) -> BoxedStrategy<Self::Value>
739 where
740 Self: Sized + 'static,
741 {
742 self
743 }
744}
745
746impl<T: fmt::Debug> Strategy for SBoxedStrategy<T> {
747 type Tree = BoxedVT<T>;
748 type Value = T;
749
750 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
751 self.0.new_tree(runner)
752 }
753
754 // Optimization: Don't rebox the strategy.
755
756 fn sboxed(self) -> SBoxedStrategy<Self::Value>
757 where
758 Self: Sized + Send + Sync + 'static,
759 {
760 self
761 }
762
763 fn boxed(self) -> BoxedStrategy<Self::Value>
764 where
765 Self: Sized + 'static,
766 {
767 BoxedStrategy(self.0)
768 }
769}
770
771#[derive(Debug)]
772struct BoxedStrategyWrapper<T>(T);
773impl<T: Strategy> Strategy for BoxedStrategyWrapper<T>
774where
775 T::Tree: 'static,
776{
777 type Tree = Box<dyn ValueTree<Value = T::Value>>;
778 type Value = T::Value;
779
780 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
781 Ok(Box::new(self.0.new_tree(runner)?))
782 }
783}
784
785//==============================================================================
786// Sanity checking
787//==============================================================================
788
789/// Options passed to `check_strategy_sanity()`.
790#[derive(Clone, Copy, Debug)]
791pub struct CheckStrategySanityOptions {
792 /// If true (the default), require that `complicate()` return `true` at
793 /// least once after any call to `simplify()` which itself returns once.
794 ///
795 /// This property is not required by contract, but many strategies are
796 /// designed in a way that this is expected to hold.
797 pub strict_complicate_after_simplify: bool,
798
799 /// If true, cause local rejects to return an error instead of retrying.
800 /// Defaults to false. Useful for testing behaviors around error handling.
801 pub error_on_local_rejects: bool,
802
803 // Needs to be public for FRU syntax.
804 #[allow(missing_docs)]
805 #[doc(hidden)]
806 pub _non_exhaustive: (),
807}
808
809impl Default for CheckStrategySanityOptions {
810 fn default() -> Self {
811 CheckStrategySanityOptions {
812 strict_complicate_after_simplify: true,
813 error_on_local_rejects: false,
814 _non_exhaustive: (),
815 }
816 }
817}
818
819/// Run some tests on the given `Strategy` to ensure that it upholds the
820/// simplify/complicate contracts.
821///
822/// This is used to internally test proptest, but is made generally available
823/// for external implementations to use as well.
824///
825/// `options` can be passed to configure the test; if `None`, the defaults are
826/// used. Note that the defaults check for certain properties which are **not**
827/// actually required by the `Strategy` and `ValueTree` contracts; if you think
828/// your code is right but it fails the test, consider whether a non-default
829/// configuration is necessary.
830///
831/// This can work with fallible strategies, but limits how many times it will
832/// retry failures.
833pub fn check_strategy_sanity<S: Strategy>(
834 strategy: S,
835 options: Option<CheckStrategySanityOptions>,
836) where
837 S::Tree: Clone + fmt::Debug,
838 S::Value: cmp::PartialEq,
839{
840 // Like assert_eq!, but also pass if both values do not equal themselves.
841 // This allows the test to work correctly with things like NaN.
842 macro_rules! assert_same {
843 ($a:expr, $b:expr, $($stuff:tt)*) => { {
844 let a = $a;
845 let b = $b;
846 if a == a || b == b {
847 assert_eq!(a, b, $($stuff)*);
848 }
849 } }
850 }
851
852 let options = options.unwrap_or_else(CheckStrategySanityOptions::default);
853 let mut config = Config::default();
854 if options.error_on_local_rejects {
855 config.max_local_rejects = 0;
856 }
857 let mut runner = TestRunner::new(config);
858
859 for _ in 0..1024 {
860 let mut gen_tries = 0;
861 let mut state;
862 loop {
863 let err = match strategy.new_tree(&mut runner) {
864 Ok(s) => {
865 state = s;
866 break;
867 }
868 Err(e) => e,
869 };
870
871 gen_tries += 1;
872 if gen_tries > 100 {
873 panic!(
874 "Strategy passed to check_strategy_sanity failed \
875 to generate a value over 100 times in a row; \
876 last failure reason: {}",
877 err
878 );
879 }
880 }
881
882 {
883 let mut state = state.clone();
884 let mut count = 0;
885 while state.simplify() || state.complicate() {
886 count += 1;
887 if count > 65536 {
888 panic!(
889 "Failed to converge on any value. State:\n{:#?}",
890 state
891 );
892 }
893 }
894 }
895
896 let mut num_simplifies = 0;
897 let mut before_simplified;
898 loop {
899 before_simplified = state.clone();
900 if !state.simplify() {
901 break;
902 }
903
904 let mut complicated = state.clone();
905 let before_complicated = state.clone();
906 if options.strict_complicate_after_simplify {
907 assert!(
908 complicated.complicate(),
909 "complicate() returned false immediately after \
910 simplify() returned true. internal state after \
911 {} calls to simplify():\n\
912 {:#?}\n\
913 simplified to:\n\
914 {:#?}\n\
915 complicated to:\n\
916 {:#?}",
917 num_simplifies,
918 before_simplified,
919 state,
920 complicated
921 );
922 }
923
924 let mut prev_complicated = complicated.clone();
925 let mut num_complications = 0;
926 loop {
927 if !complicated.complicate() {
928 break;
929 }
930 prev_complicated = complicated.clone();
931 num_complications += 1;
932
933 if num_complications > 65_536 {
934 panic!(
935 "complicate() returned true over 65536 times in a \
936 row; aborting due to possible infinite loop. \
937 If this is not an infinite loop, it may be \
938 necessary to reconsider how shrinking is \
939 implemented or use a simpler test strategy. \
940 Internal state:\n{:#?}",
941 state
942 );
943 }
944 }
945
946 assert_same!(
947 before_simplified.current(),
948 complicated.current(),
949 "Calling simplify(), then complicate() until it \
950 returned false, did not return to the value before \
951 simplify. Expected:\n\
952 {:#?}\n\
953 Actual:\n\
954 {:#?}\n\
955 Internal state after {} calls to simplify():\n\
956 {:#?}\n\
957 Internal state after another call to simplify():\n\
958 {:#?}\n\
959 Internal state after {} subsequent calls to \
960 complicate():\n\
961 {:#?}",
962 before_simplified.current(),
963 complicated.current(),
964 num_simplifies,
965 before_simplified,
966 before_complicated,
967 num_complications + 1,
968 complicated
969 );
970
971 for iter in 1..16 {
972 assert_same!(
973 prev_complicated.current(),
974 complicated.current(),
975 "complicate() returned false but changed the output \
976 value anyway.\n\
977 Old value:\n\
978 {:#?}\n\
979 New value:\n\
980 {:#?}\n\
981 Old internal state:\n\
982 {:#?}\n\
983 New internal state after {} calls to complicate()\
984 including the :\n\
985 {:#?}",
986 prev_complicated.current(),
987 complicated.current(),
988 prev_complicated,
989 iter,
990 complicated
991 );
992
993 assert!(
994 !complicated.complicate(),
995 "complicate() returned true after having returned \
996 false;\n\
997 Internal state before:\n{:#?}\n\
998 Internal state after calling complicate() {} times:\n\
999 {:#?}",
1000 prev_complicated,
1001 iter + 1,
1002 complicated
1003 );
1004 }
1005
1006 num_simplifies += 1;
1007 if num_simplifies > 65_536 {
1008 panic!(
1009 "simplify() returned true over 65536 times in a row, \
1010 aborting due to possible infinite loop. If this is not \
1011 an infinite loop, it may be necessary to reconsider \
1012 how shrinking is implemented or use a simpler test \
1013 strategy. Internal state:\n{:#?}",
1014 state
1015 );
1016 }
1017 }
1018
1019 for iter in 0..16 {
1020 assert_same!(
1021 before_simplified.current(),
1022 state.current(),
1023 "simplify() returned false but changed the output \
1024 value anyway.\n\
1025 Old value:\n\
1026 {:#?}\n\
1027 New value:\n\
1028 {:#?}\n\
1029 Previous internal state:\n\
1030 {:#?}\n\
1031 New internal state after calling simplify() {} times:\n\
1032 {:#?}",
1033 before_simplified.current(),
1034 state.current(),
1035 before_simplified,
1036 iter,
1037 state
1038 );
1039
1040 if state.simplify() {
1041 panic!(
1042 "simplify() returned true after having returned false. \
1043 Previous internal state:\n\
1044 {:#?}\n\
1045 New internal state after calling simplify() {} times:\n\
1046 {:#?}",
1047 before_simplified,
1048 iter + 1,
1049 state
1050 );
1051 }
1052 }
1053 }
1054}