DEV Community

Cover image for Your own property based testing framework - Part 3: Shrinkers
Nicolas DUBIEN
Nicolas DUBIEN

Posted on • Updated on

Your own property based testing framework - Part 3: Shrinkers

In Part 1, we covered the concept of generators. In Part 2, we added a runner on top of them.
We are now closer from a real property based testing framework but we still miss one important feature: shrinking capabilities.

In fast-check all generated values can be shrunk. Shrinking proves pretty useful whenever a property fails as it will reduce the failure to something easier to analyze and debug with.


Part 3 over 4…

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

In property based testing, whenever a failure occurs the framework will try to reduce it to something smaller so that the end-user only has to cope with a very simple and small input. It is designed to help developers focusing on the real cause without having to manually investigate several potential sources of bugs.

For instance: If our isSubstring reported an error like: ["", "null$¤¤", "\\undefined.NaN"]. We may have investigate potentially useless source of bugs.

Before designing complex shrinkers let's see how they integrate themselves in our current design.
First we need to adapt the Generator type.

type Generator<T> = {
    generate(mrng: Random): T;
    shrink(value: T): IterableIterator<T>;
}
Enter fullscreen mode Exit fullscreen mode

As you can see in the snippet above, we added a method called shrink onto our Generator type. This method takes a value - that have been generated by this Generator and builds a stream of potential shrinks for this value.

In other words, if I take back our generator of integers, I'd expect the following:

const arb = miniFc.integer(0, 100);
abr.shrink(64) // potential output: 32, 16, 8, 4, 2, 1, 0
Enter fullscreen mode Exit fullscreen mode

For integers, the implementation will use a classical technique used in programming: dichotomy. Given the technique we want to use we can adapt the code for integers as follow:

miniFc.integer = (min, max) => {
    return {
        generate(mrng) {
            return mrng.next(min, max);
        },
        *shrink(value) {
            while (value !== min) {
                value = min + Math.floor((value - min) / 2);
                yield value;
            }
        }
    }
}
// You can check the output by calling:
// > [...miniFc.integer(0, 100).shrink(64)]
// > [...miniFc.integer(0, 100).shrink(48)]
Enter fullscreen mode Exit fullscreen mode

Let's now consider our next root generators: the one for tuples and the one for arrays.

As tuples is simpler let's consider it first. As described in the diagram below a possible way to implement shrink on tuples is to shrink on the first item only, then on the second one only and so on and so forth.

Shrinking a tuple with an example

While it does not cover all the possible smaller combinations it should be good enough while keeping a great convergence speed. It can be implemented as follow:

miniFc.tuple = (...itemGenerators) => {
    return {
        generate(mrng) {
            return itemGenerators.map(g => 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)];
                }
            }
        }
    }
}
// You can check the output by calling:
// > [...miniFc.tuple(miniFc.integer(0, 100), miniFc.integer(0, 100), miniFc.integer(0, 100)).shrink([4, 3, 4])]
Enter fullscreen mode Exit fullscreen mode

Concerning arrays, the algorithm needs to shrink on two dimensions:

  • the size of the array
  • the content of the array

When impacting the size, it should not only cover the cases in which we keep the N first items. It should also consider cases in which last item is required to reproduce the failure while the first ones can be partially removed.

For instance, if we consider an algorithm that fails whenever an array contains twice the same item. If it first failed on [4, 1, 2, 1, 3] shrinker will have to be able to remove one item at the beginning, one at the middle and one at the end in order to converge towards the minimal case [1, 1].

Shrinking strategy on arrays is divided into three different steps.

  1. As most of the time, smaller arrays are simpler to understand, the first step will focus on reducing the size of the array and preserving only the N last items
  2. As for tuples, arrays are made of values and shrinking them might also simplify investigations. The second step shrink the first element and concatenate it to the remaining ones (not impacted).
  3. We keep the first item as is and apply recursively 1. and 2. on the tail of the array.

Let's apply this logic onto our example [4, 1, 2, 1, 3]:

  • [2, 1, 3] (due to 1.)
  • [1, 2, 1, 3] (due to 1.)
  • [2, 1, 2, 1, 3] (due to 2.)
  • [1, 1, 2, 1, 3] (due to 2.)
  • [0, 1, 2, 1, 3] (due to 2.)
  • [4, 1, 3] = [4] :: [1, 3] (due to 3.1.)
  • [4, 2, 1, 3] = [4] :: [2, 1, 3] (due to 3.1.)
  • [4, 0, 2, 1, 3] = [4] :: [0, 2, 1, 3] (due to 3.2.)
  • ...

We can adapt our implementation of array to to support shrinking as follow:

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;
        },
        *shrink(value) {
            // No shrink on empty arrays
            if (value.length === 0) {
                return;
            }
            // Step 1. Shrink on size first by keeping last items
            let removedSize = Math.floor(value.length / 2);
            while (removedSize > 0) {
                yield value.slice(removedSize);
                removedSize = Math.floor(removedSize / 2);
            }
            // 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];
            }
        }
    }
}
// You can check the output by calling:
// > [...miniFc.array(miniFc.integer(0, 100)).shrink([4, 1, 2, 1, 3])]
Enter fullscreen mode Exit fullscreen mode

Now that all our root generators have been covered let's adapt the generators based on them. When defined those derived generators we introduced a map function to help us in our task.

Generator for characters has been defined as follow:

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

As it generates string (of a single character), shrinker will consume string and produce smaller string. But how can map know how to convert the string received as input of the shrinker to passe it the shrinker of mapped generator (or miniFc.integer(0, 25) in our case)?

Actually if we wanted to define the shrinker function for miniFc.character we would have written something like:

const shrinker = (character) => {
    const derivedGenerator = miniFc.integer(0, 25);
    const initialValue = character.codePointAt(0) - 97;
    for (const shrunkValue of derivedGenerator.shrink(initialValue)) {
        yield String.fromCharCode(97 + shrunkValue);
    }
}
Enter fullscreen mode Exit fullscreen mode

In other words, it means that mapping a generator to derive it requires the user to declare two helper functions:

  • one to map - eg.: from integer to character in our example
  • another one to unmap - eg.: from character to integer in our example

With that in mind, map can be changed into:

const map = (g, mapper, unmapper) => {
    return {
        generate(mrng) {
            return mapper(g.generate(mrng));
        },
        *shrink(value) {
            for (const shrunkValue of g.shrink(unmapper(value))) {
                yield mapper(shrunkValue);
            }
        }
    };
};
Enter fullscreen mode Exit fullscreen mode

And all our derived generators can be adapted to add support for shrink:

miniFc.boolean = () => map(
    miniFc.integer(0, 1),
    Boolean,
    b => b ? 1 : 0,
)
miniFc.character = () => map(
    miniFc.integer(0, 25),
    n => String.fromCharCode(97 + n),
    c => c.codePointAt(0) - 97,
)
miniFc.string = () => map(
    miniFc.array(miniFc.character()),
    characters => characters.join(''),
    s => s.split('')
)
miniFc.dictionary = (valueGenerator) => map(
    miniFc.array(miniFc.tuple(miniFc.string(), valueGenerator)),
    Object.fromEntries,
    Object.entries,
)

// > [...miniFc.boolean().shrink(true)]
// > [...miniFc.character().shrink("h")]
// > [...miniFc.string().shrink("hello")]
// > [...miniFc.dictionary(miniFc.string()).shrink({"hello": "world"})]
Enter fullscreen mode Exit fullscreen mode

Given all the work above, you should be able to shrink values including complex ones such as dictionaries.

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 ); } console.log('integer(64)', [...miniFc.integer(0, 100).shrink(64)]); console.log('tuple([4, 3, 4])', [ ...miniFc.tuple( miniFc.integer(0, 100), miniFc.integer(0, 100), miniFc.integer(0, 100) ).shrink([4, 3, 4]) ]); console.log('array([4, 1, 2, 1, 3])', [ ...miniFc.array( miniFc.integer(0, 100) ).shrink([4, 1, 2, 1, 3]) ]); console.log('character("h")', [...miniFc.character().shrink("h")]); console.log('string("hello")', [...miniFc.string().shrink("hello")]); console.log('dictionary({hello: "world"})', [ ...miniFc.dictionary( miniFc.string() ).shrink({ hello: "world" }) ]);

Full snippet at https://runkit.com/dubzzz/part-3-shrinkers


Next part: https://dev.to/dubzzz/your-own-property-based-testing-framework-part-4-runners-with-shrink-53f7

Top comments (0)