Property-based testing #3: Shrinking Take One
Tags: testing, programming, python
Published: 2022-06-12 21:13:42

---
title: Property-based testing #3: Shrinking Take One
published: true
date: 2022-05-26 08:47:23 UTC
tags: testing,programming,python
canonical_url: https://getcode.substack.com/p/property-based-testing-3-shrinking
series: PBT
---

_This is the third post in a series about property-based testing. This post completes the design and implementation of the original property-based testing library, QuickCheck. The first and introductory post is [What is it anyway?](https://getcode.substack.com/p/property-based-testing-1-what-is?r=1dboko&s=w&utm_campaign=post&utm_medium=web), followed by [The Essentials of Vintage QuickCheck](https://getcode.substack.com/p/-property-based-testing-2-the-essentials?r=1dboko&s=w&utm_campaign=post&utm_medium=web)._

_The complete code for this post can be found on [GitHub](https://github.com/kurtschelfthout/substack-pbt) - in particular [example.py](https://github.com/kurtschelfthout/substack-pbt/blob/master/example.py) and [vintage\_shrink.py](https://github.com/kurtschelfthout/substack-pbt/blob/master/vintage_shrink.py)._

In the first two posts we created a reference implementation that allows users to generate random values, specify properties using `for_all`, and run tests. An excellent start, but modern PBT libraries have one more very nifty (and helpful) feature called _shrinking_. Shrinking starts after we have generated an input for which a property fails, and aims to make the failing test input easier to understand by removing parts that have no effect on whether the property fails.

[![](https://images.unsplash.com/photo-1632399593344-7f96512c0c86?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=MnwzMDAzMzh8MHwxfHNlYXJjaHwyfHxzaHJpbmtpbmd8ZW58MHx8fHwxNjUyNTIxNzg5&ixlib=rb-1.2.1&q=80&w=1080)](https://images.unsplash.com/photo-1632399593344-7f96512c0c86?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=MnwzMDAzMzh8MHwxfHNlYXJjaHwyfHxzaHJpbmtpbmd8ZW58MHx8fHwxNjUyNTIxNzg5&ixlib=rb-1.2.1&q=80&w=1080)
_Legend has it that if you keep walking down this gallery, you eventually shrink to the quantum realm. Photo by Elizabeth Villalta on Unsplash_

Let's take a sneak peek ahead at what we'll implement in this post.

As a reminder, we were testing a function `sort_by_age` which takes as input a list of `Person` objects and is simply supposed to sort them by their `age` field. Now let's see what happens when we inject a bug in the implementation:

```python
def wrong_sort_by_age(people: list[Person]) -> list[Person]:
    # whoops, forgot the sort key
    return sorted(people)

prop_wrong_sort_by_age = for_all(
    lists_of_person,
    lambda persons_in: is_valid(persons_in, wrong_sort_by_age(persons_in))
)
```

This bug means the result is sorted by name first, then by age. Our implementation dutifully finds a list for which this property fails:

```python
> test(prop_wrong_sort_by_age)
Fail: at test 0 with arguments ([Person(name='bwnbaz', age=21), Person(name='jdmzns', age=98), Person(name='nhyvan', age=90), Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)],).
```

That's a good start, but it doesn't really give us any idea of where the problem is. We could try and see what `wrong_sort_by_age`'s output is on the randomly generated input:

```python
> wrong_sort_by_age([Person(name='bwnbaz', age=21), Person(name='jdmzns', age=98), Person(name='nhyvan', age=90), Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)])

[Person(name='bwnbaz', age=21),
 Person(name='gmtwqx', age=68),
 Person(name='jdmzns', age=98),
 Person(name='nhyvan', age=90),
 Person(name='odapqz', age=49)]
```

Still it's not clear what the problem is - besides that the result is not sorted by age. We could debug with this input value, but it's quite unwieldy, even for this toy example. Imagine `Person` is a more realistic class with more than a handful of fields, some of which may be other classes with their own fields as well.

This is where shrinking comes in. Shrinking starts when we find a failing random test input. To make the test input smaller, we repeatedly re-run the test with "smaller" input values, and check if the test still fails. Here's what that process looks like after we're through with this post:

```python
> test(prop_wrong_sort_by_age)
Fail: at test 0 with arguments ([Person(name='bwnbaz', age=21), Person(name='jdmzns', age=98), Person(name='nhyvan', age=90), Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)],).
Shrinking: found smaller arguments ([Person(name='nhyvan', age=90), Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='gmtwqx', age=68), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='gmtwqx', age=51), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='gmtwqx', age=50), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='', age=50), Person(name='odapqz', age=49)],)
Shrinking: found smaller arguments ([Person(name='', age=50), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=25), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=13), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=7), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=4), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=2), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=1), Person(name='odapqz', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=1), Person(name='oda', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=1), Person(name='o', age=0)],)
Shrinking: found smaller arguments ([Person(name='', age=1), Person(name='a', age=0)],)
Shrinking: gave up - smallest arguments found ([Person(name='', age=1), Person(name='a', age=0)],)
```

Usually, real PBT libraries will present the original randomly generated argument, and the final smallest value, but I've printed all the intermediate "shrinks" here for reference. The approach for shrinking we'll implement in this post is methodical: first the number of elements in the list is reduced to two, then the remaining `Person` values are individually shrunk by making their fields smaller.

The end result is a perfect shrink - there's no way to make the value smaller while still failing the test! Indeed, the number of elements must be at least two, the names must be minimally different, and the ages must be minimally different as well. Shrinking won't always work this well, but nonetheless is surprisingly effective in practice.

There are quite a few different approaches to shrinking in various PBT libraries, each with their own trade-offs. Here we'll look at the original proposal first implemented in QuickCheck, and we'll cover others in following posts.

## Not the kind of shrink you pour your heart out to

QuickCheck's approach is relatively easy to explain, but can be tricky to understand.

The strategy is, in a nutshell, iterative improvement. Since we have randomly found an input for which the test fails, we can re-run the test with candidate input values that are in some way smaller than the failing input value. If the test still fails with the smaller value, we have succeeded in shrinking the input, and can try to shrink that smaller input further. Lather, rinse, repeat until we can't come up with candidate smaller values.

We'll assume we'll have an oracle available that for any given value comes up with candidate smaller values. For lists of `Person`s that function looks like this:

```python
def shrink_list_of_person(value: list[Person]) -> Iterable[list[Person]]:
    ...
```

The argument `value` is the value we're trying to shrink - so all returned candidates must be smaller than `value`. We'll assume we have such a function available for everything that we can generate randomly - in other words this function needs to be user-provided, like generators. We'll look at the effect this decision has on the API later.

What "smaller" means in this context is in the eye of the beholder - for lists "smaller" normally means lists shorter than the original list. For letters it might mean lexicographically earlier. For integers it might mean closer to 0. We'll look at some examples soon.

In more detail, shrinking works as follows.

1. We start out with a randomly generated failing input.

2. Get shrink candidates for the failing input by running `shrink`.

3. Run the test on the candidate.

4. If there are no more candidates, give up and report the smallest failing input.

We can visualise this as a search process on a candidate tree - an n-ary tree defined as follows:

```python
@dataclass(frozen=True)
class CandidateTree(Generic[T]):
    value: T
    candidates: Iterable[CandidateTree[T]]
```

The root of the tree has as `value` the randomly generated failing input, and the result of an appropriate `shrink` call on that value as children in `candidates`.

For example, let's assume our value is a simple `int` and we have a shrink function for it:

```python
def shrink_int(value: int) -> Iterable[int]:
    if value != 0:
        yield 0
    current = abs(value) // 2
    while current != 0:
        yield abs(value) - current
        current = current // 2

> list(shrink_int(15))
[0, 8, 12, 14]
```

The idea is to try to shrink to 0 first, as that is the smallest possible integer, and then try one half, three quarters etc of the input value. Here's the candidate tree for `shrink_int` with an initial failing value of 6:

[![](https://substackcdn.com/image/fetch/w_1456,c_limit,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fbucketeer-e05bbc84-baa3-437e-9518-adb32be77984.s3.amazonaws.com%2Fpublic%2Fimages%2Ff6937a29-e168-4446-ac09-ba9fb73c78ed_854x480.png)](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fbucketeer-e05bbc84-baa3-437e-9518-adb32be77984.s3.amazonaws.com%2Fpublic%2Fimages%2Ff6937a29-e168-4446-ac09-ba9fb73c78ed_854x480.png)

At the top we see the initial value, 6. On the next level down are all the candidates generated by `shrink_int(6)`, and this continues recursively - each node's children are the candidate smaller values for that node's value.

Here's how the search process detailed above would work for a test which fails if value > 3:

[![](https://substackcdn.com/image/fetch/w_1456,c_limit,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fbucketeer-e05bbc84-baa3-437e-9518-adb32be77984.s3.amazonaws.com%2Fpublic%2Fimages%2F51d56581-7e28-4ae6-915c-5d245a26f336_854x480.gif)](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fbucketeer-e05bbc84-baa3-437e-9518-adb32be77984.s3.amazonaws.com%2Fpublic%2Fimages%2F51d56581-7e28-4ae6-915c-5d245a26f336_854x480.gif)
_What happens when a powerful tool like Manin Community is put in the hands of a graphically challenged person_

I'll call a shrink candidate "successful" if it still makes the test fail. As the animation indicates, as long as shrinking a candidate is not successful (indicated by a red cross) we simply move on to the next candidate. If shrinking a candidate is successful, we move one level deeper in the tree. If at some point all the candidates are unsuccessful, the process ends.

In this case we find the smallest value 4 that still fails the test. It's possible to come up with a test that doesn't shrink that perfectly - depending on the implementation of the `shrink` candidate generating function. Before we discuss that, let's complete the picture above by writing a function that turns a function like `shrink_int` into a `CandidateTree`.

First let's make the general shape of functions like `shrink_int` explicit:

```python
class Shrink(Protocol[T]):
    def __call__ (self, value: T) -> Iterable[T]:
        ...
```

In case you're not familiar with Mypy's [protocols](https://mypy.readthedocs.io/en/stable/protocols.html) the details are not that important - `Shrink[T]` means: a function that takes a `value` of type `T` and generates an `Iterable` of smaller candidate values `T`. The `shrink_int` function satisfies this protocol and is a `Shrink[int]`. The `Shrink` class is just here for Mypy's benefit, and as documentation for readers - it has no effect at runtime. If that didn't make sense, feel free to ignore it, like all the other types. I find them useful for understanding and documentation so I will keep adding them.

Creating a `CandidateTree` from a `shrink` function is relatively straightforward:

```python
def tree_from_shrink(value: T, shrink: Shrink[T]) -> CandidateTree[T]:
    return CandidateTree(
        value = value,
        candidates = (
            tree_from_shrink(v, shrink)
            for v in shrink(value)
        )
    )
```

We create the `CandidateTree` recursively by calling `tree_from_shrink` lazily in a generator expression - we only create children of a node as we iterate through `candidates`. Creating the entire tree when we're only exploring a small part of it would be a waste, especially since for more complex shrink functions the tree can become big.

That's the basics of shrinking under your belt! Now relax for a bit with a calming camomile tea with honey.

[![](https://images.unsplash.com/photo-1632639521806-cead484cc369?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=MnwzMDAzMzh8MHwxfHNlYXJjaHw4fHxjYW1vbWlsZSUyMHRlYXxlbnwwfHx8fDE2NTM1MTczNjk&ixlib=rb-1.2.1&q=80&w=1080)](https://images.unsplash.com/photo-1632639521806-cead484cc369?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=MnwzMDAzMzh8MHwxfHNlYXJjaHw4fHxjYW1vbWlsZSUyMHRlYXxlbnwwfHx8fDE2NTM1MTczNjk&ixlib=rb-1.2.1&q=80&w=1080)
_Photo by Catia Climovich on Unsplash_

## Putting it all together

We'll come back to writing more interesting shrink functions for lists of `Person` objects, but first let's try to put everything we have so far together.

Remember how last time we started out with a generator `Random[T]` and turned that into a simple property, by mapping it to a `Random[bool]` which generates `True` if the test passes. Then we mapped `bool` to `TestResult`:

```python
@dataclass(frozen=True)
class TestResult:
    is_success: bool
    arguments: Tuple[Any,...]
```

So that we could capture the generated arguments as well. We ended up with `Property = Random[TestResult]` and running tests was simply calling `generate` 100 times and checking `is_success` on the resulting `TestResult` objects. This way we were able to piggy-back on the `Random` class - which is quite useful because we could keep using our `map`, `mapN` and `bind` functions for implementing the test runner itself.

We'll play this trick again by re-defining a property as a random generator of candidate trees of test results:

```python
Property = Random[CandidateTree[TestResult]]
```

This looks like a nicely layered type, but what does it mean in practice? Let's see by implementing a new `for_all`. `for_all` will have to change because it needs to produce this new `Property` type. To do so, it now needs an appropriate shrink function as an additional user-provided argument:

```python
def for_all(
    gen: Random[T], 
    shrink: Shrink[T], 
    property: Callable[[T], bool]
) -> Property:
    ...
```

I've simplified `property` again to just return a bool, which means we won't be able to nest `for_all`. We'll lift that restriction in a later post.

Our task is now to take a `Random[T]` and somehow turn it into a `Random[CandidateTree[TestResult]]`. We should be able to do something by using `map` - if we can implement a function that takes a `T` to a `CandidateTree[TestResult]`, we'll have what we need:

```python
def for_all(
    gen: Random[T],
    shrink: Shrink[T],
    property: Callable[[T], bool]
) -> Property:

    def property_wrapper(value: T) -> CandidateTree[TestResult]:
        ...

    return map(property_wrapper, gen)
```

It turns out we already have most of what we need to implement `property_wrapper`:

```python
def for_all(
    gen: Random[T],
    shrink: Shrink[T],
    property: Callable[[T], bool]
) -> Property:

    def property_wrapper(value: T) -> CandidateTree[TestResult]:
        tree_value = tree_from_shrink(value, shrink)
        tree_test_result = tree_map(
            lambda v: TestResult(is_success=property(v), arguments=(v,)),
            tree_value
        )
        return tree_test_result

    return map(property_wrapper, gen)
```

We use `tree_from_shrink` on the value to create a `CandidateTree[T]`. We're almost there now because we know from before how to turn a `T` in a `TestResult`, by invoking `property` on `value` and capturing the arguments. We just need to do that on every element of `CandidateTree` - which means we also need a map-like function on `CandidateTree`, just like we created one for `Random` in the previous post:

```python
def tree_map(f: Callable[[T], U], tree: CandidateTree[T]) -> CandidateTree[U]:
    value_u = f(tree.value)
    branches_u = (
        tree_map(f, branch)
        for branch in tree.candidates
    )
    return CandidateTree(
        value = value_u,
        candidates = branches_u
    )
```

Applying a function `f` to each value in a tree is easily expressed recursively - apply `f` to the value in the current node, and then recurse to all of the node's children.

With all that, we can finally write a new `test` function:

```python
def test(property: Property):
    def do_shrink(tree: CandidateTree[TestResult]) -> None:
        for smaller in tree.candidates:
            if not smaller.value.is_success:
                # cool, found a smaller value that still fails - keep shrinking
                print(f"Shrinking: found smaller arguments {smaller.value.arguments}")
                do_shrink(smaller)
                return
        print(f"Shrinking: gave up - smallest arguments found {tree.value.arguments}")
        

    for test_number in range(100):
        result = property.generate()
        if not result.value.is_success:
            print(f"Fail: at test {test_number} with arguments {result.value.arguments}.")
            do_shrink(result)
            return
    print("Success: 100 tests passed.")
```

The new part is the inner function `do_shrink` which is called if a randomly generated test case fails. `do_shrink` executes the search discussed above - it keeps trying candidates until it finds a smaller input. If so, it recursively continues shrinking the smaller value.

We can now run a simple example that corresponds to the shrinking animation above:

```python
wrong_shrink_1 = for_all(
    int_between(0, 20), 
    shrink_int,
    lambda l: l <= 3
)

> test(wrong_shrink_1)
Fail: at test 0 with arguments (10,).
Shrinking: found smaller arguments (5,)
Shrinking: found smaller arguments (4,)
Shrinking: gave up - smallest arguments found (4,)
```

Quick recap of where we are.

Our test library so far is nicely described by the type `Random[CandidateTree[TestResult]]`. We can read this type outside-in as a pipeline of sorts. The pipeline starts with a random value generator `Random[T]` which produces a `T` value every time we call `generate()`. Next in the pipeline we take that `T` value and turn it into a tree of `T` values, with the original `T` at the root. We now have a `Random[CandidateTree[T]]`. In the last step in the pipeline each `T` in the tree is turned into a `TestResult`.

That seems like a lot of objects to create, but since nodes in the tree are created only as we search it, in practice this works out OK. Undeniably shrinking does add some overhead though.

## Some more shrink functions

Let's now look at a few shrinking functions, to get a feel of how to write them.

The first one is `shrink_letter`. It just generates up to three candidates a,b or c, if the input value is not already one of those:

```python
def shrink_letter(value: str) -> Iterable[str]:
    for candidate in ('a', 'b', 'c'):
        if candidate < value:
            yield candidate
```

This illustrates that even for simple values, we have to take care that the generated candidates are strictly smaller than the root value - if not the shrinking process will get stuck in an infinite loop.

When shrinking containers like lists and dictionaries it's good to not only shrink the container itself by removing elements, but also call a shrink function for the individual elements. For example, a shrink function for lists:

```python
def shrink_list(value: list[T], shrink_element: Shrink[T]) -> Iterable[list[T]]:
    length = len(value)
    if length > 0:
        yield []
        half_length = length // 2
        while half_length != 0:
            yield value[:half_length]
            yield value[half_length:]
            half_length = half_length // 2
        for i,elem in enumerate(value):
            for smaller_elem in shrink_element(elem):
                smaller_list = list(value)
                smaller_list[i] = smaller_elem
                yield smaller_list
```

Somewhat similar to shrinking integers, we first try the empty list. Then we do a bisect of sorts - trying each half of the list. If none of those yield a successful shrink, we shrink each element of the list successively using `shrink_element`. So, in a way, we can compose shrink functions with others to generate more candidates for the search to try. If we wouldn't shrink the elements, we'd only be able to reduce the length of the list.

Now we have all the ingredients to write shrink functions for lists of `Person` objects:

```python
def shrink_name(name: str) -> Iterable[str]:
    name_as_list = list(name)
    for smaller_list in shrink_list(name_as_list, shrink_letter):
        yield "".join(smaller_list)

def shrink_person(value: Person) -> Iterable[Person]:
    for smaller_age in shrink_int(value.age):
        yield Person(value.name, smaller_age)
    for smaller_name in shrink_name(value.name):
        yield Person(smaller_name, value.age)

def shrink_list_of_person(value: list[Person]) -> Iterable[list[Person]]:
    return shrink_list(value, shrink_person)
```

We shrink names by converting them to a list of letters, and using `shrink_list`; we shrink `Person` objects by first shrinking the `age` field, and then the `name` field.

Our property for `sort_by_age` now becomes:

```python
prop_wrong_sort_by_age = for_all(
    lists_of_person, 
    shrink_list_of_person,
    lambda persons_in: is_valid(persons_in, wrong_sort_by_age(persons_in))
)
```

The only difference from before is that `for_all` now also needs the shrink function.

## Conclusion and Onwards

Shrinking is a useful part of property-based testing libraries, expanding their practicality significantly. Without shrinking we'd still find bugs but reproducing and understanding the randomly generated examples would be unnecessarily hard.

When you first see shrinking in action it can feel magical, and indeed it works very well in practice. This is a great example of a feature that turns a weakness into a core strength.

However, you may have noticed that shrinking requires a lot of additional work on the part of the user - all those `shrink` functions must be implemented. If for some reason you need to write a custom `Random` generator, now that also needs a `shrink` function. Worse, these are two separate bits of code that need to be kept in sync - for example, if the random generator for `age` only generates positive values, then the shrink function for `age` should not try to shrink to negative values either.

Actual property-based testing libraries wrap up the `Random` generators and the `Shrink` functions into a single type typically called `Arbitrary`. This helps somewhat to define a set of convenient randomly generated and shrink-able types, but it doesn't help all that much with writing your own, because both need to be separately written.

Also, while the `Random` API is very nice to use thanks to `map`, `mapN` and `bind`, shrink functions are not so easily composed. In fact, try to write a function like `def map(f: Callable[[T], U], shrink: Shrink[T]) -> Shrink[U]` - you won't be able to do it! Implementing `mapN` and `bind` on `Shrink` is out of the question as well. These issues impact the ease of use of the API, and in practice people often don't bother with writing shrink functions until they really, really need them.

A final problem with this approach is mutable values. I've already mentioned in the previous post that mutability is problematic when capturing the arguments in `TestResult`, but shrinking also captures the generated value in the root of the tree - so if it's mutated in place all kinds of shenanigans ensue, and shrinking gives very unexpected and confusing results.

We won't solve the mutability problem just yet, but next post we'll look into how we can regain a nice, compositional, integrated generation _and_ shrinking API. As it turns out, this post already contains most of the answer!

As usual, comment below or discuss on Twitter [@kurt2001](https://twitter.com/kurt2001).

Until next time!