Proptests

Property testing is a fascinating subject, and our crate lends itself really well to proptests. We use the proptest crate for them.

What is property testing?

In informal terms, property testing is a more abstract way of testing, where instead of explicitly defining an input and the expected output, and then asserting actual == expected, we define rules for how input should look like and what properties the output for that input should satisfy. The testing framework then takes care of generating a wide coverage of the possible inputs.

More formally, we test an algorithm $f: I \rightarrow O$ by defining a set of possible inputs, $X \subseteq I$, and a property that we expect the output of our algorithm to have on inputs from $X$, $p: 2^O$. The framework then generates $k$ inputs, $x_1, \ldots, x_k \in X$, and for each asserts that $p(f(x_i))$ holds. Sort of a fuzzy model checking.

This is an extremely potent testing technique, that can fish out bugs that would be difficult to test for otherwise. To test against a given case classically the developer has to think of that case and create the input.

Example

First, read the proptest book up to a point where you get bored.

A good case study is the small_test proptest suite we have. SmallSet256 is a heavily optimised set that holds u8 values in two 128-bit wide bitmasks.

Let's consider this test:

#[test]
fn contains(btree_set in collection::btree_set(any_elem(), 0..=MAX_SET_SIZE)) {
    let vec: Vec<u8> = btree_set.iter().copied().collect();
    let slice: &[u8] = &vec;
    let small_set: SmallSet256 = slice.into();

    for elem in 0..=MAX_ELEM {
        assert_eq!(btree_set.contains(&elem), small_set.contains(elem));
    }
}

The any_elem function is a generation strategy that returns any u8 value. So in this case the set $X$ is all BTreeSet<u8> instances. The function we test here is the From<&[u8]> impl for SmallSet256. The property is that after calling into each value of u8 it is in the result set if and only if it was in the source.