Your own property based testing framework - Part 4: Runners with shrink

In Part 1, we covered the concept of generators. In Part 2, we added a runner on top of them. In Part 3, we brought shrinking capabilities to all our generators.

But at this point, our runner is not using shrinker capabilities we introduced in previous part.

Part 4 over 4…

1. Generators
2. Runners
3. Shrinkers
4. Runners with shrink

Shrinkers have been introduced in an attempt to find the smallest failing case. They achieve one main purpose: given one value they compute strictly smaller ones.

From a runner perspective, in order to get the smallest possible failing case we want to shrink as soon as we find an issue. So we generate values and run the predicate on it and as soon as we find an issue we take this value and shrink it. Moreover while iterating over those shrunk values we may find another failing one. So, we shrink it and iterate over it until we reach the smallest failing case (a failing value for which none of its shrunk values can cause a failure).

The process is summarized into the diagram below:

In terms of code, we can adapt our miniFc.assert as follow:

miniFc.property = (generator, predicate) => {
    return {
        generate(mrng) {
            return generator.generate(mrng);
        },
        shrink(value) {
            return generator.shrink(value);
        },
        run(valueUnderTest) {
            return predicate(valueUnderTest);
        }
    }
}

function executeAndShrink(valueUnderTest, property) {
    if (!property.run(valueUnderTest)) {
        for (const shrunkValue of property.shrink(valueUnderTest)) {
            const shrunkResults = executeAndShrink(shrunkValue, property);
            if (shrunkResults.failed) {
                return shrunkResults;
            }
        }
        return { failed: true, value: valueUnderTest };
    }
    return { failed: false };
}

miniFc.assert = (property, { seed = Date.now() } = {}) => {
    let rng = prand.xoroshiro128plus(seed);
    for (let runId = 0 ; runId !== 100 ; ++runId) {
        const valueUnderTest = property.generate(new Random(rng));
        const testResults = executeAndShrink(valueUnderTest, property);
        if (testResults.failed) {
            throw new Error(`Property failed after ${runId + 1} runs with value ${JSON.stringify(testResults.value)} (seed: ${seed})`);
        }
        rng = rng.jump();
    }
}

Here we are, our home-made property based framework is now able to generate values, run tests and find failures, and in case of failure to shrink it towards something smaller to help our users.

Full snippet at https://runkit.com/dubzzz/part-4-runners-with-shrink

But unfortunately this design is not solid enough…

Several things will not be enough in this framework, some of those limitations are detailed into the official documentation of fast-check at https://github.com/dubzzz/fast-check/blob/master/documentation/1-Guides/HowItWorks.md

In a nutshell:

• Our way to map from a generator to another requires both a map and an un-map function. Unfortunately, reversing an entity is not always feasible and may require an extra work just to get shrinking capabilities
• Our way to map from a generator makes it difficult to provide a oneof generator with shrinking capabilities
• Current generators are too dummy, they miss lots of corner cases. While uniform random is good, it may takes an infinite time to find bugs…

I hope this serie of articles helpt you to get a better understanding of how property based testing may work under-the-hood. The minimal framework we finally got was how fast-check looked like during my first experiments, but no version has been released with this design.