rustproperty-based-testingproptest

Proptest: Strategy to generate vectors of vectors


I want to generate DAGs with proptest. The algorithm that I pick would be this. I've written the plain algorithm below -- but I need help transforming this to a proptest strategy.

What would a strategy need to look like that did the same as the below code but without using a random number generator? (It goes without saying that random number generators are bad for property-based testing.)

Standard code without proptest strategy: (https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2de4a757a96d123bf83b5157e0633d33)

use rand::Rng;

fn main() {
    println!("{:?}", random_vec_of_vec());
}

fn random_vec_of_vec() -> Vec<Vec<u16>> {
    const N: u16 = 30;
    const K: usize = 3;
    let mut rng = rand::thread_rng();

    let length: u16 = rng.gen_range(0, N);
    let mut outer = vec![];
    for index in 1..length {
        let mut inner = vec![0u16; rng.gen_range(0, K)];
        for e in &mut inner {
            *e = rng.gen_range(0, index);
        }
        // De-duplicate elements. Particularly a problem with `index < K`.
        inner.sort();
        inner.dedup();
        outer.push(inner);
    }
    outer
}

Previous work

I tried using the vec function, but I would need to nest two vec functions. And, the inner vec function could only generate values up to the index in the outer vector.

use proptest::collection::vec;
// INDEX should be the value of the position of the inner vector
// in the outer vector. How could the be found?
let strategy = vec(vec(1..INDEX, 0..K), 0..N);

The index method is not helpful because the right size would still not be known.


Solution

  • One way to go about this, is to replace each rng.gen_range() call with a strategy. Nested strategies must then be connected with prop_flat_map.

    In the below code, I replaced my pattern let length = rng.gen_range(0, N); for i in 1..length { .. }, with a new function vec_from_length(length: usize), which returns a Strategy.

    #[cfg(test)]
    mod tests {
        use super::*;
        use proptest::collection::hash_set;
        use proptest::prelude::*;
        use std::collections::HashSet;
    
        proptest! {
            #[test]
            fn meaningless_test(v in vec_of_vec()) {
                let s = sum(&v);  // sum of the sum of all vectors.
                prop_assert!(s < 15);
            }
        }
    
        fn vec_of_vec() -> impl Strategy<Value = Vec<Vec<u16>>> {
            const N: u16 = 10;
    
            let length = 0..N;
            length.prop_flat_map(vec_from_length).prop_map(convert)
        }
    
        fn vec_from_length(length: u16) -> impl Strategy<Value = Vec<HashSet<u16>>> {
            const K: usize = 5;
            let mut result = vec![];
            for index in 1..length {
                // Using a hash_set instead of vec because the elements should be unique.
                let inner = hash_set(0..index, 0..K);
    
                result.push(inner);
            }
            result
        }
    
        /// Convert Vec<HashSet<T>> to Vec<Vec<T>>
        fn convert(input: Vec<HashSet<u16>>) -> Vec<Vec<u16>> {
            let mut output = vec![];
            for inner in input {
                output.push(inner.into_iter().collect())
            }
            output
        }
    }
    

    One more thing: An impl Strategy<Value=Vec<T>> can be generated from either the vec function (a strategy of vector) or from a vector of strategies! In the above code, I do this through having result be pushed with hash_set(..) which is a Strategy. The type is thus something like Vec<Strategy<T>> not Strategy<Vec<T>> (pedantic: Strategy is not a type, maybe).