Learn Rust Series (#53) - Property-Based Testing with proptest

scipio(71)

Published in

StemSocial

Words

2975

Reading

14 min

Listen

Play

12h

Learn Rust Series (#53) - Property-Based Testing with proptest

What will I learn

You will learn the difference between example-based tests and property-based tests;
how a property describes what must hold for every input, not just the ones you thought of;
how the proptest crate generates hundreds of random inputs and checks a property against each;
what shrinking is, and why it turns a giant random failure into a tiny reproducible one;
how to write the same ideas by hand in plain std, so you understand what the crate automates.

Requirements

A working modern computer running macOS, Windows or Ubuntu, with Cargo;
An installed Rust toolchain (via rustup, from rustup.rs);
The previous fifty-two episodes, especially unit testing and closures;
The ambition to learn systems programming from the ground up.

Difficulty

Intermediate

Curriculum (of the `Learn Rust Series`):

Learn Rust Series (#53) - Property-Based Testing with proptest

At the end of last episode I left a question hanging in the air: we had proven our code correct, but only against inputs we dreamt up, one at a time. And that is the quiet weakness of every example-based test ever written. A test checks the cases you were clever enough (or paranoid enough) to think of -- and says absolutely nothing about the case you missed. The bug always lives in the case you missed. Always.

Property-based testing flips the whole thing on its head. In stead of writing "for this input I expect that output", you state a property -- a rule that must hold for every input -- and you hand a machine the job of trying to break it. "Reversing a list twice gives the original list." "Parsing the text form of a number gives the number back." "A sorted list is never longer or shorter than the list you started with." You assert the rule, and the framework throws hundreds of randomly generated inputs at it, hunting for a single counterexample. When it finds one, it does something genuinely clever: it shrinks that ugly random failure down to the smallest, simplest input that still breaks the property, and hands you that.

The standard tool in Rust is the proptest crate. It is external (not part of std), so I will show you what it looks like -- but then, as is our habit in this series, we will build the idea by hand in pure std, because the machinery is simple enough that nothing should feel like magic ;-)

Solutions to Episode 52 Exercises

Episode 52 was testing: unit tests, integration tests, and doctests. Here are all three exercises worked out in full.

Exercise 1 asked for is_palindrome(&str) -> bool and a #[cfg(test)] module asserting a real palindrome, a non-palindrome, and the empty string:

pub fn is_palindrome(s: &str) -> bool {
    let chars: Vec<char> = s.chars().collect();
    chars.iter().eq(chars.iter().rev())
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn cases() {
        assert!(is_palindrome("racecar"));
        assert!(!is_palindrome("rust"));
        assert!(is_palindrome("")); // the empty string reads the same both ways
    }
}

The neat trick here is chars.iter().eq(chars.iter().rev()): the Iterator::eq method compares two iterators element by element, and rev() walks the second one backwards. No index juggling, no off-by-one, and it reads almost like the definition of a palindrome out loud.

Exercise 2 wanted a function that panics on a negative argument, a #[should_panic(expected = "...")] test proving it panics for the right reason, and a second ordinary test proving it returns the correct value for a valid argument:

pub fn checked_sqrt(n: i64) -> i64 {
    if n < 0 {
        panic!("cannot take the square root of a negative number");
    }
    (n as f64).sqrt() as i64
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[should_panic(expected = "negative")]
    fn rejects_negative() {
        checked_sqrt(-1);
    }

    #[test]
    fn computes_a_valid_root() {
        assert_eq!(checked_sqrt(144), 12);
    }
}

Notice that expected = "negative" only has to be a substring of the real panic message, so it matches "cannot take the square root of a negative number" comfortably. The second test matters just as much as the first: proving a function panics when it should is only half the contract -- you also have to prove it does the right thing when it should not panic.

Exercise 3 asked for a test returning Result<(), std::num::ParseIntError> that uses ? on a parse step, plus an #[ignore]d test with a documented reason:

pub fn parse_sum(s: &str) -> Result<i64, std::num::ParseIntError> {
    let mut total = 0;
    for part in s.split(',') {
        total += part.trim().parse::<i64>()?;
    }
    Ok(total)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sums_a_csv_line() -> Result<(), std::num::ParseIntError> {
        let total = parse_sum("10, 20, 12")?; // ? turns a parse error into a failed test
        assert_eq!(total, 42);
        Ok(())
    }

    #[test]
    #[ignore = "slow; run with: cargo test -- --ignored"]
    fn sums_a_long_line() -> Result<(), std::num::ParseIntError> {
        let line = (1..=1000).map(|n| n.to_string()).collect::<Vec<_>>().join(",");
        assert_eq!(parse_sum(&line)?, 500_500);
        Ok(())
    }
}

The ? inside the test is the whole point of the Result-returning shape: a parse failure bubbles up and is reported as a failed test, no tower of unwraps required. And that = "reason" on #[ignore] is simple courtesy to your future self -- it says why the test is skipped, so nobody wonders whether it was disabled because it is slow or because it is broken. Right, homework cleared. On to properties.

Example-based tests only cover what you imagine

Let me show you the exact weakness property testing was invented to fix. Here is a function and a test that passes -- green, clean, looks finished. And yet the function has a lurking bug for one specific input we never thought to type:

fn abs_diff(a: i32, b: i32) -> i32 {
    (a - b).abs()
}

fn main() {
    assert_eq!(abs_diff(5, 3), 2);
    assert_eq!(abs_diff(3, 5), 2);
    // both hand-picked cases pass. but abs_diff(i32::MIN, 0) computes
    // (i32::MIN - 0).abs(), and i32::MIN has no positive counterpart in i32,
    // so that .abs() overflows -- we simply never tried it.
    println!("two hand-picked cases passed; are we sure that is enough?");
}

Two confident green checkmarks, and a landmine sitting one input away. The problem is not that we were lazy -- we tested both argument orders, which feels thorough. The problem is structural: a human picks representative inputs, and i32::MIN never feels representative until it blows up in production. The fix is to stop hand-picking entirely and let a generator wander the input space for us, into the corners we would never visit on purpose.

What a property actually is

Before reaching for a crate, get the mindset right, because it is the hard part. A property is a statement that is true for all valid inputs, not a specific input-output pair. The shift in thinking is from "the answer for 5 and 3 is 2" to "for any two numbers, the absolute difference is never negative, and swapping the arguments does not change it". You are describing the shape of correct behaviour rather than enumerating examples of it.

That is harder than it sounds, because the obvious property is often just a reimplementation of the function -- "the sum of this list equals a + b + c + ...", which is useless, since to check it you would write the same summation you are trying to test and any bug would appear in both. The art is finding a property that is true, cheap to state, and independent of the implementation. Having said that, there are a handful of reliable patterns that work again and again, and we will meet the two best of them shortly.

A property with proptest

Here is what the real tool looks like. With proptest you declare a strategy for generating inputs, then assert your property inside the proptest! macro. The framework runs the body many times (256 by default) with different random values:

// requires the `proptest` crate: shown for illustration, not compiled locally
use proptest::prelude::*;

proptest! {
    #[test]
    fn reversing_twice_is_identity(v in prop::collection::vec(any::<i32>(), 0..100)) {
        let mut twice = v.clone();
        twice.reverse();
        twice.reverse();
        prop_assert_eq!(twice, v); // must hold for EVERY generated vector
    }
}

Read the parameter out loud: v in prop::collection::vec(any::<i32>(), 0..100) says "let v be a vector of up to 100 elements, each a randomly chosen i32". That prop::collection::vec(...) is the strategy -- a recipe for producing values. proptest ships strategies for every primitive, for collections, for tuples, for structs you compose yourself, and you can map and filter them to carve out exactly the input domain you care about. prop_assert_eq! is just like assert_eq! except it plays nicely with the shrinking machinery. Add proptest under [dev-dependencies] in your Cargo.toml, and cargo test runs these right alongside your ordinary unit tests.

The same idea by hand

Now let us prove there is no magic. A property test, stripped to its bones, is nothing more than a loop: generate an input, run the property, assert. The only ingredient std does not hand us is a random number generator, so we will write a tiny deterministic one -- a linear congruential generator, the same three-line classic that shipped in C standard libraries for decades:

struct Lcg(u64); // a minimal linear congruential generator

impl Lcg {
    fn next_u64(&mut self) -> u64 {
        // these exact constants are the ones used by PCG / musl -- battle-tested
        self.0 = self.0.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        self.0
    }
}

fn reversing_twice_is_identity(v: &[i32]) -> bool {
    let mut t = v.to_vec();
    t.reverse();
    t.reverse();
    t == v
}

fn main() {
    let mut rng = Lcg(0x1234_5678); // a fixed seed -> the run is reproducible
    for _ in 0..1000 {
        let len = (rng.next_u64() % 20) as usize;
        let v: Vec<i32> = (0..len).map(|_| rng.next_u64() as i32).collect();
        assert!(reversing_twice_is_identity(&v)); // the property under test
    }
    println!("1000 random cases passed");
}

That loop is property testing in miniature: generate a random-length vector of random integers, check the property, repeat a thousand times. Note the two wrapping_ operations -- we want the arithmetic to wrap around on overflow here, because that is how an LCG scrambles its state; using ordinary * and + would panic in a debug build the instant the multiplication overflowed. (This is a lovely echo of episode 43 and the std::mem / wrapping-arithmetic discipline: Rust makes you say out loud that you meant the overflow.) A fixed seed means the run is perfectly reproducible -- run it today, run it next year, same thousand vectors. What proptest adds on top is better-distributed generators, automatic reproducible seeds saved to disk, strategies for complex types, and the shrinking we are about to build.

Two properties worth reaching for

The two patterns that pay off most often are the round-trip and the oracle. A round-trip says: if you transform a value and then reverse the transform, you get the original back. Encode-then-decode, serialise-then-parse, compress-then-decompress. It is a fantastic property because it is almost always true by intent and brutally exposes any asymmetry between the two halves:

fn main() {
    // property: for any i32, parsing its own string form gives the number back
    for n in [i32::MIN + 1, -1, 0, 1, 42, i32::MAX] {
        let round = n.to_string().parse::<i32>().unwrap();
        assert_eq!(round, n); // to_string and parse must be perfect inverses
    }
    println!("round-trip held for the sampled values");
}

The oracle (sometimes called a "model") pattern says: you have a fast, clever, hard-to-trust implementation, and a slow, obvious, obviously-correct reference. The property is simply that the two always agree. This is how you gain confidence in an optimised routine -- you check it against the dumb version that nobody could get wrong:

fn sum_fast(v: &[u64]) -> u64 {
    v.iter().copied().sum() // the concise, idiomatic version
}

fn sum_reference(v: &[u64]) -> u64 {
    let mut total = 0; // the plodding, obviously-correct version
    for &x in v {
        total += x;
    }
    total
}

fn main() {
    for len in 0..50u64 {
        let v: Vec<u64> = (0..len).collect();
        assert_eq!(sum_fast(&v), sum_reference(&v)); // they must agree on every input
    }
    println!("fast implementation matches the reference");
}

A third pattern worth knowing is the invariant: a fact about the output alone, without reference to the input, like "the length of a sorted vector equals the length of the original" or "every element of a filtered list satisfied the predicate". Round-trip, oracle, invariant -- keep those three in your head and you will rarely be stuck for a property to write.

Shrinking: from a monster to a minimal case

Here is the feature that turns property testing from a neat idea into something you actually want. When a random test fails, the failing input is usually enormous and full of irrelevant noise -- a vector of forty random numbers, only one of which actually matters. Staring at that and trying to work out which element triggers the bug is miserable. Shrinking does it for you: once it has a failing input, the framework repeatedly simplifies it -- dropping elements, shrinking numbers toward zero -- and rechecks, keeping any simpler input that still fails, until it cannot simplify any further. What lands on your desk is the minimal reproducing case.

Let me build a shrinker by hand for a deliberately-buggy property -- "no element exceeds 100" -- so you can see the loop is genuinely simple:

fn property_holds(v: &[i32]) -> bool {
    v.iter().all(|&x| x <= 100) // the (buggy, for demo) property we are testing
}

fn shrink_failing(mut v: Vec<i32>) -> Vec<i32> {
    let mut i = 0;
    while i < v.len() {
        let mut candidate = v.clone();
        candidate.remove(i);
        if !property_holds(&candidate) {
            v = candidate; // dropping element i STILL fails, so it was noise -- keep it dropped
        } else {
            i += 1;        // dropping it made the test pass, so element i mattered -- keep it
        }
    }
    v
}

fn main() {
    let failing = vec![1, 2, 500, 3, 4]; // a "found" failure, full of noise
    let minimal = shrink_failing(failing);
    println!("smallest failing input: {minimal:?}"); // [500]
}

The logic is worth pausing on. We try removing each element in turn. If the property still fails without it, that element was irrelevant to the failure, so we throw it away and carry on. If removing it makes the property pass, that element was load-bearing, so we put it back and move to the next. What survives is the irreducible core of the bug -- here, just [500]. proptest does exactly this, only far more cleverly (it shrinks the values too, not only the length, so a failing 99999 becomes 101, the smallest value that still exceeds 100), and it saves the seed of any failure into a proptest-regressions file so the exact case is replayed on every future run until you have genuinely fixed it. That is the difference between a random test that nags you with a new giant input every time and a property test that pins the bug down and keeps it pinned.

How Python and Go do it

A glance sideways sharpens the picture, as always, since quite some of you came through the Learn Python Series. In Python the reigning tool is hypothesis, and it reads beautifully -- you decorate a test with @given and a strategy, and it does the generating and shrinking for you:

# pip install hypothesis
from hypothesis import given
from hypothesis import strategies as st

@given(st.lists(st.integers()))
def test_reversing_twice_is_identity(xs):
    assert list(reversed(list(reversed(xs)))) == xs  # holds for every generated list

The shape is strikingly close to proptest: a strategy (st.lists(st.integers())) feeds generated values into a body that asserts a property, and hypothesis shrinks any failure to a minimal example. The big difference is cultural -- hypothesis is a third-party install you reach for deliberately, whereas in Rust proptest slots straight into the one blessed cargo test harness we met last episode.

Go took a different and interesting road: as of Go 1.18 the standard testing package grew built-in fuzzing, where you write a Fuzz function, seed it with a few examples, and the toolchain mutates them to explore new code paths:

// fuzz_test.go -- run with: go test -fuzz=FuzzReverse
package main

import "testing"

func FuzzReverseTwice(f *testing.F) {
    f.Add([]byte("hello"))
    f.Fuzz(func(t *testing.T, data []byte) {
        once := reverse(data)
        twice := reverse(once)
        if string(twice) != string(data) {
            t.Errorf("round-trip failed for %q", data)
        }
    })
}

That is not quite the same thing as property testing -- fuzzing is coverage-guided, mutating inputs to reach unexplored branches rather than sampling a declared strategy -- but the spirit is identical: stop hand-picking inputs, let the machine hunt. And it is a rather perfect segue, because that coverage-guided style of hunting is exactly where we are headed next ;-)

Wrapping up

So here is the whole picture. Example-based tests only ever check the inputs your imagination produced, and the bug is forever in the input you did not imagine. Property-based testing fixes that by letting you assert a rule that must hold for all inputs -- a round-trip, an oracle, an invariant -- while a generator explores the space far more ruthlessly than any human would. The proptest crate is the standard tool, but the engine underneath is just a loop (generate, run, assert) bolted to a random generator and a shrinker, and we built a working version of each in plain std to prove it.

The single feature that makes the whole approach practical rather than merely clever is shrinking: a failure report that hands you [500] instead of a screenful of random noise is a failure report you can act on in seconds. Write the property once, and it keeps finding the edge cases your example tests never reach -- and thanks to the saved regression seed, once it catches a bug it never lets that bug sneak back in.

We have now handed the wheel to a generator that samples a strategy we declared. The logical next step is to take our hands even further off the wheel: instead of sampling from a distribution we described, we let a tool watch which branches of our code actually execute and mutate its inputs specifically to reach the ones we have never hit -- hunting the darkest, least-travelled corners of a function automatically. After that, with correctness well in hand, we finally stop asking "is it right?" and start asking "how fast is it?", and learn to measure that honestly rather than guess. Finding the bugs imagination misses is only the first half of the story ;-)

Exercises

Write a hand-rolled property loop (reuse the Lcg generator above) that asserts sorting a vector and then sorting the result again yields the same vector -- an idempotence property. Generate a few hundred random vectors and check it holds for all of them.
Write a round-trip property over a set of sample digit-strings: for each, call parse::<u32>() and then to_string(), and assert you get the original string back. Think about which inputs would break the round-trip (leading zeros, a leading +) and leave those out of your generator.
Extend the shrink_failing shrinker so that, after it has finished removing elements, it also tries reducing each remaining element toward zero (keep halving it while the property still fails), so a failing 500 shrinks down to the smallest value that still trips the bug.