pbt 0.4.4

Property-based testing with `derive` macros, aware of mutual induction & instantiability.
Documentation 
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

use {
    crate::{
        construct::{Construct, Decomposition},
        reflection::{AlgebraicTypeFormer, Erased, PrecomputedTypeFormer, info},
    },
    core::mem,
};

// TODO: Take a reference instead of a moved value.
/// Iterate over values that are "smaller" than this one in some sense.
/// This iterator is designed to cut about half the remaining "size" of the type
/// on the first go, then to cut only about a quarter, then only an eighth, etc.,
/// until they almost reach (but do not equal) the original term.
#[inline]
pub fn shrink<T: Construct>(t: T) -> Box<dyn Iterator<Item = T>> {
    let info = info::<T>();
    let AlgebraicTypeFormer {
        all_constructors: ref ctors,
        eliminator,
        ..
    } = *match info.type_former {
        PrecomputedTypeFormer::Algebraic(ref alg) => alg,
        PrecomputedTypeFormer::Literal { shrink, .. } => {
            // SAFETY: Undoing an earlier `transmute`.
            let shrink = unsafe {
                mem::transmute::<
                    fn(Erased) -> Box<dyn Iterator<Item = Erased>>,
                    fn(T) -> Box<dyn Iterator<Item = T>>,
                >(shrink)
            };
            return shrink(t);
        }
    };
    let ctors = ctors.clone();

    // SAFETY: Undoing an earlier `erase`.
    let eliminator = unsafe { eliminator.unerase::<T>() };
    let Decomposition { ctor_idx, fields } = eliminator(t.clone());
    #[expect(
        clippy::indexing_slicing,
        reason = "internal invariants; violation should panic"
    )]
    let (orig_ctor_fn, orig_ctor_deps) = ctors[ctor_idx.get() - 1].clone();
    // SAFETY: Undoing an earlier `erase`.
    let orig_ctor_fn = unsafe { orig_ctor_fn.unerase::<T>() };
    // Visit all terms of type `Self` (deeply) and try them all as toplevel solutions:
    let nested_selves = t
        .visit_deep::<T>()
        .skip(1) // skip `t` itself
        .collect::<Vec<_>>(); // need to collect b/c `t` is local :(

    let shrink_fields = fields
        .clone()
        .shrink()
        .map(move |mut fields| orig_ctor_fn(&mut fields));

    // Try all other constructors whose field multisets are subsets of `t`'s fields:
    // (It's fine that constructors are unsorted, since success will effectively restart,
    // and that's probably just as efficient as eagerly sorting and/or
    // storing the constructors in sorted order but then multiplexing indices.)
    // TODO: Benchmark the above -- but still, not a big deal.
    let try_smaller_ctors = ctors
        .into_iter()
        .filter(move |&(_, ref deps)| {
            let ctor_info = &deps.constructor;
            // We can reuse fields iff the other constructor's fields are a
            // sub(multi)set of this constructor's fields;
            // otherwise, we'd have to generate new fields,
            // and the whole resulting value might be larger than this one:
            ctor_info
                .immediate
                .is_subset_of(&orig_ctor_deps.constructor.immediate)
                .is_some_and(|strict| {
                    strict || {
                        // If the two constructors' fields were *precisely* equal
                        // (still technically a subset, just not a strict one),
                        // then we need to tiebreak a potential loop:
                        ctor_info.index < orig_ctor_deps.constructor.index
                    }
                })
            // TODO: should we do this for *all* (deep) terms
            // or just immediate toplevel fields?
        })
        .map(move |(f, _)| {
            // SAFETY: Undoing an earlier `erase`.
            let f = unsafe { f.unerase::<T>() };
            // TODO: iterate over sections if there would be fields left over;
            // right now, we're effectively only taking the first N and dropping the rest
            f(&mut fields.clone())
        });

    Box::new(
        nested_selves
            .into_iter()
            .chain(try_smaller_ctors)
            .chain(shrink_fields),
    )
}