vendor/proptest/src/strategy/recursive.rs

//-
// 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 crate::strategy::just::Just;
    use super::*;

    #[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());
        }
    }
}