Nicolas DUBIEN

Posted on Jul 5, 2020 • Edited on Jul 12

Your own property based testing framework - Part 2: Runners

#algorithms #softwaredevelopment #education #javascript

In Part 1, we covered the concept of generators. Without them property based testing would not be possible. Alone they do not offer a lot.

In this part, we will cover an other main piece of property based testing frameworks: runners.

In fast-check there is one main runner called fc.assert. Let's see how to add such feature into our minimal framework.

Part 2 over 4…

First of all, we will have to define the concept of property. For simplicity, a property can be seen as a super generator:

type Property<T> = {
    generate(mrng: Random): T;
    run(valueUnderTest: T): boolean;
}

In our case, properties will be created using the following helper:

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

Now, let's consider a simple example to understand how we want to use our minimal version of fast-check. The code under test will be an implementation of isSubstring with obviously a bug into it in order to check that our framework can find it. As a user we would like to be able to write:

const isSubstring = (pattern, text) => {
    return text.indexOf(pattern) > 0;
}

miniFc.assert(
    miniFc.property(
        miniFc.tuple(miniFc.string(), miniFc.string(), miniFc.string()),
        ([a, b, c]) => isSubstring(b, a + b + c)
    )
)

In terms of typings we have the following signature to fulfill on ssert:

declare function assert<T>(property: Property<T>): void;

By default, in most of the frameworks, runners run the property a hundred times and stop if everything is working fine after those hundred runs.

A basic implementation for the runner can be written as follow:

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

Additionally in property based testing, seed is supposed not to be fixed except if specified on call-site. Implementation above can be updated as follow:

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));
        if (!property.run(valueUnderTest)) {
            throw new Error(`Property failed after ${runId + 1} runs with value ${JSON.stringify(valueUnderTest)} (seed: ${seed})`);
        }
        rng = rng.jump();
    }
}

In previous section, we did not cover the reason why we opted for pure random generators. In property based we want properties to be reproducible no matter the seed, no matter the hardware and no matter the unix time… But we also want to have independent runs for each iteration in the loop.

For instance, in the implementation defined above, we call generate with the following instances of Random:

runId = 0 - Call with new Random(prand.xoroshiro128plus(seed))
runId = 1 - Call with new Random(prand.xoroshiro128plus(seed)).jump()
runId = 2 - Call with new Random(prand.xoroshiro128plus(seed)).jump().jump()
...

jump offsets a random number generator, in the context of xoroshiro128plus calling jump is equivalent to 2⁶⁴ calls to next. In the case of pure-rand neither jump nor next alter the original instance, they both create a new instance of the generator while keeping the original one unchanged.

No matter how many times our property will call the passed mutable random generator, we will always ignore it to build the generator required for the next iteration. While it might appear strange at first glance, this feature is important as we don't really know what will happen to this instance of our random generator. Among the possible scenario:

relying on the offset applied by the property to the passed instance of Random is problematic as it makes replays difficult to implement except if we re-generate all the values one-by-one whenever replaying stuff
instance of Random might be kept and re-used later by the property and its Generator (we will see that it might be the case in some implementations of shrink), thus calls to generate in subsequent iterations might alter it.

We can now use our small framework on the property we discussed earlier in this section.


    
require("core-js");
const prand = require('pure-rand');

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];
    }
}

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

const miniFc = {};

miniFc.integer = function(min, max) {
    return {
        generate(mrng) {
            return mrng.next(min, max);
        }
    };
}

miniFc.boolean = function() {
    return map(
        miniFc.integer(0, 1),
        Boolean
    );
}

miniFc.character = function() {
    return map(
        miniFc.integer(0, 25),
        function(n) { return String.fromCharCode(97 + n); }
    );
}

miniFc.tuple = function(...itemGenerators) {
    return {
        generate(mrng) {
            return itemGenerators.map(function(g) { return g.generate(mrng); });
        }
    };
}

miniFc.array = function(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;
        }
    };
}

miniFc.string = function() {
    return map(
        miniFc.array(miniFc.character()),
        function(characters) { return characters.join(''); }
    );
}

miniFc.dictionary = function(valueGenerator) {
    return map(
            miniFc.array(
            miniFc.tuple(
                miniFc.string(),
                valueGenerator
            )
        ),
        Object.fromEntries
    );
}

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

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

As we were expecting, it finds an issue and reports it. When running it locally you should have an output similar to:

Property failed after 11 runs with value ["","w","vmethwd"] (seed: 42)

Given all the work above, you should be able to write and test properties as if you were using fast-check.

Full snippet at https://runkit.com/dubzzz/part-2-runners

Next part: https://dev.to/dubzzz/your-own-property-based-testing-framework-part-3-shrinkers-5a9j

DEV Community

Your own property based testing framework - Part 2: Runners

Top comments (0)

Read next

The JavaScript History API

How to Make a Retro 2D JavaScript Game Part 2

Mastering HTML: From Basics to Intermediate Level

Asymptotic Analysis Exercises — Java