Your own property based testing framework - Part 3: Shrinkers
Tags: algorithms, softwaredevelopment, education, javascript
Published: 2020-07-07 06:58:43

---
title: Your own property based testing framework - Part 3: Shrinkers
published: true
description: Build your own property based testing framework
tags: algorithms, softwaredevelopment, education, javascript
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/0y7bn71d664kw0yqydjg.jpg

---

In [Part 1](https://dev.to/dubzzz/your-own-property-based-testing-framework-part-1-generators-3afi), we covered the concept of generators. In [Part 2](https://dev.to/dubzzz/your-own-property-based-testing-framework-part-2-runners-12fl), 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](https://github.com/dubzzz/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](https://dev.to/dubzzz/your-own-property-based-testing-framework-part-1-generators-3afi)
2. [Runners](https://dev.to/dubzzz/your-own-property-based-testing-framework-part-2-runners-12fl)
3. **Shrinkers**
4. [Runners with shrinker](https://dev.to/dubzzz/your-own-property-based-testing-framework-part-4-runners-with-shrink-53f7)

---

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.

```ts
type Generator<T> = {
    generate(mrng: Random): T;
    shrink(value: T): IterableIterator<T>;
}
```

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:
```js
const arb = miniFc.integer(0, 100);
abr.shrink(64) // potential output: 32, 16, 8, 4, 2, 1, 0
```

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:

```js
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)]
```

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](https://dev-to-uploads.s3.amazonaws.com/i/5qyk5ztoa45juqu94zfn.png)

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:

```js
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])]
```

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:

```js
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])]
```

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:
```js
miniFc.character = () => map(
    miniFc.integer(0, 25),
    n => String.fromCharCode(97 + n)
)
```

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:
```js
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);
    }
}
```

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:

```js
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);
            }
        }
    };
};
```

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

```js
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"})]
```

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

{% runkit
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"
    })
]);
{% endrunkit %}

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