Property Testing

The Problem

Let’s say you’re writing a function.

When you’re writing it, there are a lot of little signals in your iteration loop that will tell you it will or won’t work. In my toolbox they come in this order:

1. IDE underlines the code I wrote in red
2. it doesn’t compile
3. unit test case doesn’t pass for one case
4. test doesn’t pass local integration tests
5. test doesn’t pass CI tests
6. code fails in staging
7. code fails in production

The step in there that I rely the most on is the compiler. The compiler is a good friend of mine. It tells me where my mistakes are and how to fix them, even before I know that it’s an issue. When I’m writing in my IDE and it gives me a red line, even before I’m done typing my token, I smile a little knowing that my tools have my back.

Now, let’s talk about testing. One way to write tests is to come up with a few test cases, then assert their equality. Finally, you write a few cases for testing the negative cases. This works, and for really simple types, this works well…

fn main() {
    println!("Hello, world!");
    println!("{}", add(3, 3));
}

fn add(a: i32, b: i32) -> i32 {
    a + b
}

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

    #[test]
    fn test_add() {
        // positive cases
        assert_eq!(2, add(1, 1));
        assert_eq!(6, add(3, 3));

        // negative cases
        assert_ne!(6, add(7, 3));
    }
}

However, the more complicated your types get, the less fun it is to generate test cases. Let’s say you’re trying to test the following structures. I’ll put the proto definition for brevity.

// Transform represents an objects location in 3D space. The origin is
// a vector that represents the objects translation from the origin.
message Transform {
    // origin is the translated offset from the origin of the scene
    Vector3 origin = 1;

    // basis represents the the orientation in 3D space
    Basis basis = 2;
}

message Vector3 {
  float x = 1;
  float y = 2;
  float z = 3;
}

// Basis represents the objects orientation in a 3D space
message Basis {
    Vector3 x = 1;
    Vector3 y = 2;
    Vector3 z = 3;
}

If you need to test any function that takes a Transform as a parameter, you have to build out each part of the struct. This is tedious and error-prone. Some languages handle this ugly structure building with dependency injection (another paradigm I take issue with), but the same problems are still there. Coming up with the positive test cases and negative test cases are even more tedious. As engineers get closer to finishing their projects, the last thing they want to do is spend time writing more test cases.

The Idea

Let’s look back at the problem we’re addressing in more abstract terms. We have some pure function (no side effects, network calls, disk IO, static variables, state changes) and need to test that Fn(A) -> B (where A represents the domain of the function and B represents the co-domain), does what it’s expected to. When engineers typically write tests, then use f(a) -> b for a specific a in A and a specific b in B. This only asserts that f(a) -> b, it doesn’t say much about Fn(A) -> B.

A different way to think about tests is to consider what it means to be a member of A and B. Let’s say we’re trying to test the proto above as an example.

In code, it means that A is some struct (or implements some interface) and B likewise. From the information in the proto definition, what do we know about what it means to be in either of these sets? Well, each a in A has a Basis and a Vector. It’s really easy to catch errors here because a compiler will tell you whether or not the type is valid.

What is much more interesting is describing the qualities that b should have after being mapped to the co-domain. In other words, what qualities would b have given a?

If I have a Transform and want to get a vector of the next possible positions, I know that the next possible positions have to within 10m (as an example). So instead of testing exact solutions, I’m checking that there are a few properties about the b. If the initial transform has a given position, then the next transform should be a reasonable distance away. I should also check that the next transform isn’t the same as the initial one. Notice that I’m describing rules about what I expect the outcome to be, and not testing individual inputs for validity.

The Solution

In this case, I’m checking that if I add any two numbers, the result is definitely going to be bigger.

    #[test]
    fn test_add_two() {
        fn test_logic(a: i32, b: i32) -> TestResult {
            TestResult::from_bool(a < add(a, b)) // a + b is definitely bigger than a right? 3 + 3 > 3 ???
        }
        QuickCheck::new()
            .tests(10)
            .max_tests(100)
            .quickcheck(test_logic as fn(i32, i32) -> TestResult);
    }

I’m trying to use Property Testing to write some rules about the inputs and outputs. In this case, I believe that a + b > a. The property testing library will then generate a bunch of test cases for a in A and b in B (which are just ints) and check that the properties that I believe in hold true. I don’t specify any input or output.

Indeed, the library generates some test cases and finds a case where this property does not hold.

running 1 test
thread 'tests::test_add_two' panicked at '[quickcheck] TEST FAILED. Arguments: (0, 0)', /home/drew/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/macros.rs:13:23

In a more complicated example, the library is generate a more complicated input. The transform from above has a few nested types. In another file, I’ve implemented a trait on Transform so that the Quickcheck library can create random transforms. Then, I test that every transform returned by possible_direction is between 0 and 15 units away from the initial transform.

#[quickcheck]
fn possible_directions(initial: Transform) -> bool {
    let pd = possible_direction(&initial);

    pd.iter().fold(true, |acc, (t, _)| {
        let distance_traveled = magnitude(&(t.get_origin() - initial.get_origin()));
        0f32 < distance_traveled && distance_traveled < 15f32 && acc
    })
}

This is a much more abstract way of writing tests, and can take a little bit to get used to, but this has helped a ton with my productivity. The original Quickcheck is a Haskell project, but I’ve been using a Rust port for my new videogame.