Your own property based testing framework - Part 4: Runners with shrink
Tags: algorithms, softwaredevelopment, education, javascript
Published: 2020-07-18 10:11:58

---
title: Your own property based testing framework - Part 4: Runners with shrink
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. In [Part 3](https://dev.to/dubzzz/your-own-property-based-testing-framework-part-3-shrinkers-5a9j), 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…_

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](https://dev.to/dubzzz/your-own-property-based-testing-framework-part-3-shrinkers-5a9j)
4. **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:

![Shrinking process](https://dev-to-uploads.s3.amazonaws.com/i/x9n1oxutfzleti9cidbs.png)

In terms of code, we can adapt our `miniFc.assert` as follow:

```js
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.

{% 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
    );
}

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();
    }
}
%}
function isSubstring(pattern, text) {
    return text.indexOf(pattern) > 0;
}

miniFc.assert(
    miniFc.property(
        miniFc.tuple(miniFc.string(), miniFc.string(), miniFc.string()),
        function([a, b, c]) {
            return isSubstring(b, a + b + c);
        }
    )
)
{% endrunkit %}

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](https://github.com/dubzzz/fast-check/) looked like during my first experiments, but no version has been released with this design.