Your own property based testing framework - Part 1: Generators

While understanding the internals of each tool is not required to use them properly, sometimes I personally feel the need to dig a bit into the tools I am using regularly.

If you never heard about property based testing, you might be interested by reading this quick introduction first.

Part 1 over 4…

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

Concerning property based testing everything started at the end of 2017…

At that time I was trying to apply property based testing on User Interfaces as explained by this article from the author of RapidCheck or my article. So I took the leading JavaScript property based testing library and tried to add model based testing support to it… but failed.

So after weeks of trials and errors, I finally changed my mind. I wanted to understand how things worked under the hood to get why it did not work. The result of this analysis is fast-check - a property based testing framework written in TypeScript for both JavaScript and TypeScript users that tries to solve the issue I faced at that time to make model based testing real.

Throughout this serie of articles we will see how to build our own property based testing library from scratch. Our wonderful library will be called miniFc, it will expose all the features required for property based testing from generation of random values to shrinking capabilities.

But let's start from the beginning…

In property based testing everything starts with generators. Generators take a random number generator and build anything out of it.

You can see generators as follow:

type Generator<T> = {
    generate(mrng: Random): T;
}

In the signature above mrng is a mutable random generator. In our case, it is a simple wrapper around pure-rand that provides a usable random instance. The class Random can be implemented as follow:

class Random {
    constructor(rng) {
        this.rng = rng;
    }
    next(min, max) {
        const g = prand.uniformIntDistribution(min, max, this.rng);
        this.rng = g[1];
        return g[0];
    }
}

// Can be used as follow:
// > const prand = require('pure-rand');
// > const seed = 0;
// > const mrng = new Random(prand.xoroshiro128plus(seed));
// > mrng.next(0, 50); // generate a random value between 0 (incl.) and 50 (incl.)
// >                   // using a uniform distribution, all values have the same probability

Let's build our first generator: the one responsible to build random integers.

// const miniFc = {}

miniFc.integer = (min, max) => {
    return {
        generate(mrng) {
            return mrng.next(min, max);
        }
    };
}
// It can be used as follow:
// > miniFc.integer(0, 50).generate(mrng)

Our random integer Generator is simply returning the value forged by the passed random number generator.

But we want to go further as generators should be able to generate not only integers, they are supposed to generate barely any kind of values. In fast-check, you can generate numbers, strings, arrays but also objects, functions, recursive structures and also infinite streams of any kind of stuff. In order to produce so many different kind of values without copying the same code again and again, they rely on taking root structures and deriving them into more complex ones as described below:

Let's first consider boolean and character.
In the diagram above they are constructed out of integer generator.
In order to do so, we need to introduce an extra function: map.
It will take an existing generator and a mapping function and create another generator out of it:

declare function map<T, U>(g: Generator<T>, mapper: (v: T) => U): Generator<U>;

It can be implemented as follow:

function map(g, mapper) {
    return {
        generate(mrng) {
            const value = g.generate(mrng);
            return mapper(value);
        }
    };
}

Now that we have map we can implement some of our missing generators:

miniFc.boolean = () => map(
    miniFc.integer(0, 1),
    Boolean
)

miniFc.character = () => map(
    miniFc.integer(0, 25),
    n => String.fromCharCode(97 + n)
)

In order to build others, we first need to implement a generator for tuples and a generator for arrays:

miniFc.tuple = (...itemGenerators) => {
    return {
        generate(mrng) {
            return itemGenerators.map(g => g.generate(mrng));
        }
    };
}
// It can be used as follow:
// > miniFc.tuple(miniFc.integer(0, 50), miniFc.boolean()).generate(mrng)

miniFc.array = (itemGenerator) => {
    return {
        generate(mrng) {
            const size = mrng.next(0, 10);
            const content = [];
            for (let index = 0 ; index !== size ; ++index) {
                content.push(itemGenerator.generate(mrng));
            }
            return content;
        }
    };
}
// It can be used as follow:
// > miniFc.array(miniFc.character()).generate(mrng)

Now we can build our last generators:

miniFc.string = () => map(
    miniFc.array(miniFc.character()),
    characters => characters.join('')
)

miniFc.dictionary = (valueGenerator) => map(
    miniFc.array(
        miniFc.tuple(
            miniFc.string(),
            valueGenerator
        )
    ),
    Object.fromEntries
)

Given all the work above, you should be able to generate values ranging from simple booleans to complex dictionaries. But our framework is far from done.

Full snippet at https://runkit.com/dubzzz/part-1-generators

Next part: https://dev.to/dubzzz/your-own-property-based-testing-framework-part-2-runners-12fl