Property testing is the automated testing of programs by its specific properties. To write a property test a programmer will provide a specification for the program, function of software which its should accept as inputs, and then a test to validate the outputs.

With property testing, we specify the domain of a function and then create generators which will randomly generate inputs and validate our assumptions. Property testing started with a library called Quick Check in Haskell and has moved into most other programming languages — as it’s pretty useful.

Rust has a useful proptery testing library that I hope to demonstrate through an example. I chose this example because it has a pretty rigid domain, which made writing the tests pretty fun. I’ll get pretty pedantic with these tests in this example, however, in a real-world scenario you may decide to write a simplified property test.

The Advent of Code

Let’s take a look at the Advent of Code 2015 Day 11 and our team’s implementation. The AOC describes the need for a password according to the following specification:

  • Passwords must include one increasing straight of at least three letters, like abc, bcd, cde, and so on, up to xyz. They cannot skip letters; abd doesn’t count.
  • Passwords may not contain the letters i, o, or l, as these letters can be mistaken for other characters and are therefore confusing.
  • Passwords must contain at least two different, non-overlapping pairs of letters, like aa, bb, or zz.

As you’re aware someone on our team has already solved this problem, as evident by the bright and shiny Christmas tree:

AOC Tree

However, we can we use property testing to validate that our code is correct, beyond the few tests that we have already written! Looking into our source code you can see that one of our teammates created a function with the following signature, and the associated unit tests.

    // This function has been implemented. 
    pub fn is_valid_password(password: &[u8]) -> bool

    // These tests have been created to validate the code works. 
    assert_eq!(false, is_valid_password(b"hijklmmn"));
    assert_eq!(false, is_valid_password(b"abbceffg"));
    assert_eq!(false, is_valid_password(b"abbcegjk"));

These unit tests are great, however, they only validate 3 scenarios b"hijklmmn", b"abbceffg", b"abbcegjk" I’ll use property tests to improve the strength and coverage of these tests. Starting simple we’ll implement our simplest property, the second rule: “Passwords may not contain the letters i, o, or l”. We’ll start by creating a property test and give it a generator that will create an 8 character string without i, o, or l; this genrator will be the following: s in "[a-hjkmnp-z]{8}". This property will generate different strings according to the regex provided.

use proptest::prelude::Strategy;
use proptest::{prop_compose, proptest, proptest_helper};

proptest! {
    #[test]
    fn property_test_valid_password(s in "[a-hjkmnp-z]{8}"){
        println!("{}", s);
        let byte_string = s.as_bytes();
        assert_eq!(true, is_valid_password(byte_string));
    }

   //   left: `true`,
   //   right: `false`; minimal failing input: s = "pmjjmjjp"
   //   successes: 0
   //   local rejects: 0
   //   global rejects: 0
   //   tests/year2015/day_11.rs:68:1
}

As expected, when running this test, it fails. We haven’t satisfied the other two conditions abc or bb, which our generator is not currently generating.

Next we’ll implement the first condidtion for passwords “Passwords must include one increasing straight of at least three letters, like abc”. For clarity I’ll use prop_compose and create our a generator specifically for this constraint — and then reference it in our test.

We can’t include i, l, or o, so we are limited in what sequences are possible "[a-fp-x]", which is the domain of our new generator sequence_of_three. Now we’d like to use the domain but want u8 so let’s use prop_map to make that converstion immedialty. Once we have the value represented as a u8 we can increment the value to create a sequnce. In the above code, a letter is randmoly generated, say a, it’s then converted to u8 and then returned in a tuple (s, s + 1, s + 2) or abc in u8, so that there is a sequence of letters.

use proptest::prelude::Strategy;
use proptest::{prop_compose, proptest, proptest_helper};

// a sequence of three excluding forbiden letters and out of bound ranges
prop_compose! {
    fn sequence_of_three() (s in "[a-fp-x]".prop_map(|v| v.as_bytes()[0])) -> (u8, u8, u8) {
        (s, s + 1, s + 2)
    }
}

proptest! {
    #[test]
    fn property_test_valid_password(s in "[a-hjkmnp-z]{5}", (x, y, z) in sequence_of_three()){
        // create a vector to build the string
        let mut v: Vec<u8> = Vec::new();
        // push each u8 into the vector
        s.as_bytes().iter().for_each(|b| v.push(*b));

        // add the sequence
        v.push(x); 
        v.push(y); 
        v.push(z);

        println!("{:?}", v);
        
        assert_eq!(true, is_valid_password(v.as_slice()));

        // now we have two sets of genrated data but still are failing
        //   left: `true`,
        //  right: `false`; minimal failing input: s = "pmjjm", (x, y, z) = (112, 113, 114)
        //         successes: 0
        //         local rejects: 0
        //         global rejects: 0
    }
}

As expected our tests are still failing. We still have to implement the last contraint, “Passwords must contain at least two different, non-overlapping pairs of letters, like aa, bb, or zz”. Let’s create another generator. This generator unique_pairs creates pairs with the following code.

// this gives me random valid letters
prop_compose! {
    fn doubles() (s in "[a-hjkmnp-z]".prop_map(|v| v.as_bytes()[0]),
                  z in "[a-hjkmnp-z]".prop_map(|v| v.as_bytes()[0])) -> (u8, u8){
        (s, z)
    }
}

// this gives me two pairs
prop_compose! {
    fn unique_pairs() ((a, b) in doubles()) -> (u8, u8, u8, u8) {
        (a, a, b, b)
    }
}

This code still fails. Why? because we need two unique pairs aa and aa don’t satisfy the requirment for two pairs. We can solve this problem by introducing prop_filter, which will filter out any generated values that don’t satisfy the condition.

// this gives me two unique pairs
prop_compose! {
    fn unique_pairs() ((a, b) in doubles().prop_filter("", |(x, y)| x != y)) -> (u8, u8, u8, u8) {
        (a, a, b, b)
    }
}

Putting it all together we get the following

use proptest::prelude::Strategy;
use proptest::{prop_compose, proptest, proptest_helper};

// this gives me random valid letters
prop_compose! {
    fn doubles() (s in "[a-hjkmnp-z]".prop_map(|v| v.as_bytes()[0]),
                  z in "[a-hjkmnp-z]".prop_map(|v| v.as_bytes()[0])) -> (u8, u8){
        (s, z)
    }
}

// this gives me two unique pairs
prop_compose! {
    fn unique_pairs() ((a, b) in doubles().prop_filter("", |(x, y)| x != y)) -> (u8, u8, u8, u8) {
        (a, a, b, b)
    }
}

// a sequence of three excluding forbiden letters and out of bound ranges
prop_compose! {
    fn sequence_of_three() (s in "[a-fp-x]".prop_map(|v| v.as_bytes()[0])) -> (u8, u8, u8) {
        (s, s + 1, s + 2)
    }
}

proptest! {
    #[test]
    fn property_test_valid_password(s in "[a-hjkmnp-z]".prop_map(|b| b.as_bytes()[0]),
                                    (x, y, z) in sequence_of_three(),
                                    (a, b, c, d) in unique_pairs()){
        let v: Vec<u8> = vec![x, y, z, s, a, b, c, d];
        println!("{:?}", v);

        assert_eq!(true, is_valid_password(v.as_slice()));
    }
}

// STDOUT of the generated values
// running 1 test
// [120, 121, 122, 102, 114, 114, 107, 107]
// [114, 115, 116, 104, 118, 118, 110, 110]
// [114, 115, 116, 122, 102, 102, 112, 112]
// [97, 98, 99, 113, 98, 98, 99, 99]
// [120, 121, 122, 115, 114, 114, 113, 113]
// [117, 118, 119, 102, 107, 107, 99, 99]
// [100, 101, 102, 107, 106, 106, 118, 118]
// [117, 118, 119, 106, 112, 112, 99, 99]
// .
// .
// .1000+ generated values tested
// .
// .
// [116, 117, 118, 120, 106, 106, 114, 114]
// [99, 100, 101, 104, 110, 110, 101, 101]
// [99, 100, 101, 109, 98, 98, 115, 115]
// [100, 101, 102, 121, 110, 110, 109, 109]
// [115, 116, 117, 98, 109, 109, 106, 106]
// test year2015::day_11::property_test_valid_password ... ok

The output of these tests are 1000s of individual tests that generate random values — according to the domain that we specified. These tests increase the value our CI/CD brings us as each run represents a different combvination of values.