Property-based testing in Rust using Hegel

Hegel is a relatively new cross-language library for doing Property-based testing (also referred to as Property testing or PBT) based on the work from Hypothesis, which is a Python library for PBT. It has not seen massive adoption yet (it’s still in beta after all), so I’m writing this to encourage others to try it out, because it’s awesome!

What’s Property-based testing?

Property-based testing is a technique for testing your code where you test specific properties rather than focusing on specific test cases. Commonly, you’ll use a library such as QuickCheck (which introduced this idea) or some other library inspired by it, and the library will take care of finding the right inputs under which your property doesn’t hold.

Here are some properties we’d test for if we were to test, for example, a reverse function:

• length(input) == reverse(input)
• reverse(reverse(input)) == input
• the last element of input is the first element of reverse(input)

Each of these can be tested independently and often times, if your function is nontrivial, it will find edge cases you’d never think of if you were writing the test cases by hand.

An Example: A Sorting Function

Let’s say we want to test our shiny new Bubble sort implementation.

fn sort(nums: &[i8]) -> Vec<i8> {
    let mut sorted: Vec<i8> = nums.into();

    for i in 0..nums.len() - 1 {
        for j in 0..nums.len() - 1 - i {
            if sorted[j] > sorted[j + 1] {
                sorted.swap(j, j + 1);
            }
        }
    }

    sorted
}

How would we do this normally? Well we’d probably think of all the interesting that cases we’d like to ensure behave correctly. Let’s think…

• A list with just one element
• A list with a few elements of different values
• A list with a few elements of the same value

Let’s test for these.

#[test]
fn test_singleton() {
    assert_eq!(sort(&[1]), [1]);
}

#[test]
fn test_diff_values() {
    assert_eq!(sort(&[8, 1, 9, 3, 81, 13, 41]), [1, 3, 8, 9, 41, 81]);
}

#[test]
fn test_repeated_values() {
    assert_eq!(sort(&[3, 3, 3, 3, 3, 3]), [3, 3, 3, 3,  3]);
}

Let’s see if they pass.

running 4 tests
test tests::test_diff_values ... FAILED
test tests::test_repeated_values ... FAILED
test tests::test_singleton ... ok

failures:

---- tests::test_diff_values stdout ----

thread 'tests::test_diff_values' (6321) panicked at src/lib.rs:25:9:
assertion `left == right` failed
  left: [1, 3, 8, 9, 13, 41, 81]
 right: [1, 3, 8, 9, 41, 81]
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- tests::test_repeated_values stdout ----

thread 'tests::test_repeated_values' (6323) panicked at src/lib.rs:30:9:
assertion `left == right` failed
  left: [3, 3, 3, 3, 3, 3]
 right: [3, 3, 3, 3, 3]

Oh, sorry. Here are our fixed tests.

#[test]
fn test_diff_values() {
    assert_eq!(sort(&[8, 1, 9, 3, 81, 13, 41]), [1, 3, 8, 9, 13, 41, 81]);
}

#[test]
fn test_repeated_values() {
    assert_eq!(sort(&[3, 3, 3, 3, 3, 3]), [3, 3, 3, 3, 3, 3]);
}

Let’s test again!

running 3 tests
test tests::test_diff_values ... ok
test tests::test_repeated_values ... ok
test tests::test_singleton ... ok

Great!

Okay, now let’s see how we’d test this with hegel. First let’s look at our tests and extract the properties we’re testing for.

test_diff_values and test_repeated_values could just be generalized into a single property which checks that, when given more than one value, the output is sorted.

This is how we encode this property using hegel

use hegel::TestCase;
use hegel::generators as gs;

#[hegel::test]
fn test_sorted(tc: TestCase) {
    let nums = tc.draw(gs::vecs(gs::integers::<i8>()));

    let sorted = sort(&nums);

    assert!(sorted.is_sorted());
}

The most important thing here is the TestCase parameter our test takes. We don’t have to provide a value for this, hegel does so automatically.

TestCase allows us to “draw” (i.e. generate) some data from a Generator, which we can create using the functions exposed in hegel::generators (which we’ve aliased to gs for convenience).

The hegel::generators module has lots of different generators you can use, like:

• hashmaps
• optional
• urls
• emails
• ip_addresses

just to name a few.

Since generators are values, we can compose them in various ways. For example, this is how we’d generate a HashMap<String, Vec<Vec<u8>> if we wanted to get crazy:

let cool_map = tc.draw(gs::hashmaps(
    gs::text(),
    gs::vecs(gs::vecs(gs::integers::<u8>())),
));

We can also encode constraints on the generated data. Let’s make the values 10x10.

let cool_map = tc.draw(gs::hashmaps(
    gs::text(),
    gs::vecs(
        gs::vecs(gs::integers::<u8>()).filter(|v| v.len() == 10)
    ).filter(|v| v.len() == 10),
));

This is starting to get ugly. We can always

An Example: Testing a JSON Parser

Let’s say we want to parse JSON (or, well a small subset of it). I’ve written a parser using winnow, which is a library for parser combinators. This is my first time writing a JSON parser, so I’m not sure if there are any edge cases I didn’t account for, so we’ll use hegel to uncover them.

(I will not be showing the implementation here because it’s irrelevant right now, but you can see the code here if you’re curious.)

This is the syntax tree we’re parsing into:

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct JsonString(pub String);

pub struct JsonNumber(pub i32);

pub struct JsonObject(pub BTreeMap<JsonString, JsonValue>);

pub enum JsonValue {
    String(JsonString),
    Number(JsonNumber),
    Object(JsonObject),
}

We have these parsers:

fn parse_string(input: &mut &str) -> ModalResult<JsonString>;
fn parse_number(input: &mut &str) -> ModalResult<JsonNumber>;
fn parse_key_value(input: &mut &str) -> ModalResult<(JsonString, JsonValue)>;
fn parse_object(input: &mut &str) -> ModalResult<JsonObject>;
fn parse_value(input: &mut &str) -> ModalResult<JsonValue>;

pub fn parse_json(input: &str) -> anyhow::Result<JsonValue>;

The first four functions here are parsers for atomic units of our syntax, and parse_value combines them. This is usually how a parser combinators-based parser library looks like. Here parse_json is a higher level function which just wraps parse_value. It’s much friendlier for outsiders because it doesn’t consume the slice it’s given, and returns a result that is better to work with than winnow’s ModalResult.

How would we test this normally? We would probably write some unit tests for each function, so we can ensure that each function is correct in isolation, then we would write some test for parse_json.