proptest/strategy/recursive.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 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());
}
}
}