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

#algorithms #softwaredevelopment #education #javascript

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…

Generators
Runners
Shrinkers
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.


    
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, unmapper) {
    return {
        generate(mrng) {
            const value = g.generate(mrng);
            return mapper(value);
        },
        *shrink(value) {
            for (const shrunkValue of g.shrink(unmapper(value))) {
                yield mapper(shrunkValue);
            }
        }
    };
}

const miniFc = {};

miniFc.integer = function(min, max) {
    return {
        generate(mrng) {
            return mrng.next(min, max);
        },
        *shrink(value) {
            while (value !== min) {
                value = min + Math.floor((value - min) / 2);
                yield value;
            }
        }
    };
}

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

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

miniFc.tuple = function(...itemGenerators) {
    return {
        generate(mrng) {
            return itemGenerators.map(function(g) { return g.generate(mrng); });
        },
        *shrink(value) {
            for (let index = 0 ; index !== itemGenerators.length ; ++index) {
                const currentGenerator = itemGenerators[index];
                const currentValue = value[index];
                for (const shrunkValue of currentGenerator.shrink(currentValue)) {
                    yield [...value.slice(0, index), shrunkValue, ...value.slice(index + 1)];
                }
            }
        }
    };
}

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;
        },
        *shrink(value) {
            // No shrink on empty arrays
            if (value.length === 0) {
                return;
            }
            // Step 1. Shrink on size first by keeping last items
            for (let removedSize = Math.floor(value.length / 2) ; Math.sign(removedSize) === 1 ; removedSize = Math.floor(removedSize / 2)){
                yield value.slice(removedSize);
            }
            // Step 2. Shrink the first item alone
            for (const shrunkItemValue of itemGenerator.shrink(value[0])) {
                yield [shrunkItemValue, ...value.slice(1)];
            }
            // Step 3. Keep first item untouched
            for (const shrunkValue of this.shrink(value.slice(1))) {
                yield [value[0], ...shrunkValue];
            }
        }
    };
}

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

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

miniFc.property = function(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)) {
        // console.log('Failure with: ' + JSON.stringify(valueUnderTest));
        for (const shrunkValue of property.shrink(valueUnderTest)) {
            const shrunkResults = executeAndShrink(shrunkValue, property);
            if (shrunkResults.failed) {
                shrunkResults.depth += 1;
                return shrunkResults;
            }
        }
        return { failed: true, value: valueUnderTest, depth: 0 };
    }
    return { failed: false };
}

miniFc.assert = function(property, conf) {
    let seed = conf !== undefined ? (conf.seed !== undefined ? conf.seed : Date.now()) : 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 + ', depth: ' + testResults.depth + ')');
        }
        rng = rng.jump();
    }
}

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.

DEV Community

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

Top comments (0)

Read next

Svelte Counter I made to understand runes

Is React-query out of date? This new favorite makes cross-component requests a breeze!

Using Guard Clauses Instead of Try-Catch in Async/Await: A Clean Coding Technique for Readable and Maintainable Code 🦄🚀

From useEffect to React Query: Modernizing your data management in react