Higher-Order Strategies

A higher-order strategy is a strategy which is generated by another strategy. That sounds kind of scary, so let’s consider an example first.

Say you have a function you want to test that takes a slice and an index into that slice. If we use a fixed size for the slice, it’s easy, but maybe we need to test with different slice sizes. We could try something with a filter:

fn some_function(stuff: &[String], index: usize) { /* do stuff */ }

proptest! {
    #[test]
    fn test_some_function(
        stuff in prop::collection::vec(".*", 1..100),
        index in 0..100usize
    ) {
        prop_assume!(index < stuff.len());
        some_function(stuff, index);
    }
}

This doesn’t work very well. First off, you get a lot of global rejections since index will be outside of stuff 50% of the time. But secondly, it will be rare to actually get a small stuff vector, since it would have to randomly choose a small index at the same time.

The solution is the prop_flat_map combinator. This is sort of like prop_map, except that the transform returns a strategy instead of a value. This is more easily understood by implementing our example:

use proptest::prelude::*;

fn some_function(stuff: Vec<String>, index: usize) {
    let _ = &stuff[index];
    // Do stuff
}

fn vec_and_index() -> impl Strategy<Value = (Vec<String>, usize)> {
    prop::collection::vec(".*", 1..100)
        .prop_flat_map(|vec| {
            let len = vec.len();
            (Just(vec), 0..len)
        })
}

proptest! {
    #[test]
    fn test_some_function((vec, index) in vec_and_index()) {
        some_function(vec, index);
    }
}
fn main() { test_some_function(); }

In vec_and_index(), we make a strategy to produce an arbitrary vector. But then we derive a new strategy based on values produced by the first one. The new strategy produces the generated vector unchanged, but also adds a valid index into that vector, which we can do by picking the strategy for that index based on the size of the vector.

Even though the new strategy specifies the singleton Just(vec) strategy for the vector, proptest still understands the connection to the original strategy and will shrink vec as well. All the while, index continues to be a valid index into vec.

prop_compose! actually allows making second-order strategies like this by simply providing three argument lists instead of two. The below desugars to something much like what we wrote by hand above, except that the index and vector’s positions are internally reversed due to borrowing limitations.

use proptest::prelude::*;
prop_compose! {
    fn vec_and_index()(vec in prop::collection::vec(".*", 1..100))
                    (index in 0..vec.len(), vec in Just(vec))
                    -> (Vec<String>, usize) {
       (vec, index)
   }
}
fn main() { }