This post might be a bit too much of Hypothesis inside baseball, but it’s something I did this morning that I found pretty interesting so I thought I’d share it. Hypothesis has a pretty sophisticated system for example simplification. A simplification pass looks roughly like

def simplify_such_that(search_strategy, random, value, condition):
    changed = True
    while changed:
        changed = False
        for simplify in search_strategy.simplifiers(random, t):
            while True:
                for s in simplify(random, value):
                    if condition(s):
                        changed = True
                        value = s
                        break
                else:
                    break
    return value

Instead of having a single simplify function we split our simplification up into multiple passes. Each pass is repeatedly applied until it stops working. Then we move onto the next one. If any pass succeeded at simplifying the value we start again from the beginning, else we’re done and return the current best value. This works well for a number of reasons, but the principle goal of it is to avoid spending time on steps that we’re pretty sure are going to be useless: If one pass deletes elements of a list and another simplifies them, we don’t want to try deleting again every time we successfully shrink a value because usually we’ve already found the smallest list possible (the reason we start again from the beginning if any pass worked is because sometimes later passes can unblock earlier ones, but generally speaking this doesn’t happen much). This generally works pretty well, but there’s an edge case where it has pathologically bad performance, which is when we have a pass which is useless but has a lot of possible values. This happens e.g. when you have large lists of complicated values. One of my example quality tests involves finding lists of strings with high unicode codepoints and long strictly increasing subsequences. This normally works pretty well, but I was finding it hit this pathological case sometimes and the test would fail because it used up all its time trying simplification passes that wouldn’t work because they were blocked by the previous step. This morning I figured out a trick which seems to improve this behaviour a lot. The idea is to spend a few passes (5 is my highly scientifically derived number here) where we cut each simplifier off early: We give it a few attempts to improve matters and if it doesn’t we bail immediately rather than running to the end. The new code looks roughly like this:

from itertools import islice
 
max_warmups = 5
 
def simplify_such_that(search_strategy, random, value, condition):
    changed = true
    warmup = 0
    while changed or warmup < max_warmups:
        warmup += 1
        changed = false
        for simplify in search_strategy.simplifiers(random, t):
            while true:
                simpler = simplify(random, value)
                if warmup < max_warmups:
                    simpler = islice(simpler, warmup)
                for s in simpler:
                    if condition(s):
                        changed = true
                        value = s
                        break
                else:
                    break
    return value

This seems to avoid the pathological case because rather than getting stuck on a useless simplifier we simply skip over it fairly quickly and give other simplifiers that are more likely to work a chance to shine. Then once the warmup phase is over we get to do the full simplification algorithm as before, but because we’ve already chewed it down to something much less complicated than we started with there isn’t as much of a problem – we tend not to have individually long simplifier passes because most of the really complex structure has already been thrown away. Empirically, for the test cases this was designed to improve this is more than an order of magnitude speed improvement (even when they’re not hitting the pathological case where they fail altogether), going from giving up after hitting the timeout at 30 seconds to completing the full pass in 3, and for everything else it merely seems about the same or a little better. So, yeah, I’m pretty pleased with this. This is definitely in the category of “Hypothesis’s example simplification is an overly sophisticated solution to problems that are mostly self-inflicted”, but who doesn’t like nice examples?

I’ve just released a version of Hypothesis with an implementation of a form of state machine based testing.

This is pretty exciting for me as it’s something that I’ve wanted to do for about a year and a half now. Back in the beginning of 2014 I wrote testmachine, which at the time I thought was revolutionary. I’ve since realised that it’s just a variation on the theme of state machine based testing that’s been popular in the Erlang world for a while. I’ve been wanting to merge the ideas for it with those in Hypothesis for some time.

In theory this should have been easy. To be honest, it should have been easy in practice too. The two-fold problems were that each project had somewhat incompatible assumptions about how the world works, and I wanted to put it all into a single uniform framework rather than half-arsing it.

Well, in the end I’ve half-arsed it, but that was because I came at it from another angle: there are a bunch of things I wanted to test that were fundamentally impossible in either Hypothesis or testmachine. Thinking hard about what sort of API I would actually need in order to test these made me realise a very simple generic state machine testing API which made building a testmachine like API so incredibly easy that it seemed a shame not to do it.

I’d like to talk about the design and the implementation of that underlying API in this piece. First though I’d like to note some motivating examples:

1. Testing a game where the decisions available to you at any point depend heavily on the game state
2. Testing a website using selenium webdriver
3. Testing your data access API against a database (e.g. in Django)

The crucial thing about all of these is that you simply can’t provide a valid spec for the steps to execute in advance of executing them – at each stage the set of actions available to you is so dependent on the state you’ve executed so far that there’s really no way to make a decision in advance about what it is you’re doing. The only way to know what you can do for step N + 1 is to run the first N steps.

So I tried to think what the API I would need to make something like this work would be and what I came up with was this:

class GenericStateMachine(object):
    def steps(self):
        raise NotImplementedError('%r.steps()' % (self,))
    def execute_step(self, step):
        raise NotImplementedError('%r.execute_steps()' % (self,))
    def teardown(self):
        pass

The idea is that steps returns a SearchStrategy over the set of possible actions, which can depend on the current state in essentially arbitrary ways. execute_step runs a value drawn from the search strategy, and then teardown shuts your machine down at the end. So you’re running something that looks more or less like:

machine = MyMachine()
try:
    for i in range(n_steps):
        machine.execute_step(machine.steps.example())
finally:
    machine.teardown()

(what is actually run is notably more complicated for a variety of reasons, but that’s the essence of it)

The system then basically just generates programs of this form until one of them errors.

This will obviously work: At each point you choose a random action available to you, then you execute it. If anything like this is going to work for testing your stateful system this will.

There’s a problem though: How can you possibly simplify such a thing? Your steps() function can depend in arbitrary ways on the state of the system. If you’re unlucky it might even depend on an external source of randomness! (Normal Hypothesis’s answer to this is “Well don’t do that then”. Stateful testing has to be a little more robust, although it will still complain that your test is flaky if the same program doesn’t fail twice).

The first part is easy: We save the random seeds we use for examples. This means that we can always delete intermediate steps without affecting the draw for later steps. So we can start by considering the stateful test execution as just a list of random number seeds and attempt to find a minimal such list by deleting elements from it.

It is important to note that just because we’ve saved the seed at each step doesn’t mean that the sequence of step values is going to be the same! e.g. if earlier steps populate some list and a later one draws from it, even though the seed is the same the choice from the now smaller list might not be.

In theory this can work arbitrarily badly: e.g. If each step was generated by taking a cryptographic hash of the state, turning that into a random number generator, and return the strategy just(random.random()), essentially any change you make to your execution by deleting previous steps might break the failure. In practice however it seems to work rather well – most natural choices of strategies and execution approaches are relatively robust to deleting intermediate steps and not changing the meaning of later ones.

However we still want to be able to minimize the values in the steps. If we started with having generated the value “aweraweraiouuovawenlmnlkewar” and actually all we cared about was that it was a non-empty string of latin alphabet characters we’d sure like to be able to shrink it down to the value “a”.

But there’s a problem. Shrinking in Hypothesis happens on strategy templates (the intermediate representation that gets turned into values) and is defined by the strategy, not based on the type of the value. This is not a technical limitation, it’s genuinely an important feature: Otherwise you might shrink things to things not permitted by the strategy. e.g. if our strategy was actually sampled_from([“aweraweraiouuovawenlmnlkewar”, 2]) it’s pretty important we don’t try to shrink the string to “a”.

Additionally, what do we do if the strategy changes under us? If on a previous run we got to this point and demanded a string to progress, but now it wants an int?

So, uh, this is where it gets a little weird.

I realised an important trick a little while ago: Hypothesis templates don’t have to be immutable. They have to do a pretty good job of faking it in a lot of roles, but it’s actually perfectly OK for a bit of mutation to be happening behind the scenes and to make use of this. This is used in the support for generating infinite stream, where we keep track of how much of the stream has been evaluated so we know how far to bother simplifying up to (no point in simplifying element #10 if we’ve only looked at the first 9 values).

And we can also use this here, combined with another Hypothesis feature.

Hypothesis has the ability to serialize and deserialize all templates. Moreover it makes very strong guarantees: You can feed it literally any data in and you will get either a valid template for the strategy with all invariants satisfied or a BadData exception. This is an important feature for compatibility with older databases – Hypothesis can’t necessarily use a serialized example from a previous version, but it will never break because of it.

And this means that we can convert two templates between arbitrary strategies if we know both strategy: We serialize the template on the one end and then deserialize it on the other. No problem. Either we got a valid template and everything is fine, or we didn’t and we know about it.

So the first step is that our templates for executing a state machine actually have two parts: The seed and a serialized blob of data. When deciding on a step to take, we first attempt to deserialize the blob. If that works, we use that as the template for the step. If it doesn’t, we draw a template from the random seed we have.

And this, combined with the mutability, allows us to simplify individual elements.

As we execute the state machine, we store the strategies and the serialized form of their template on the template for our execution. If we started with a serialized blob this will often leave it unchanged, but it may refresh the strategy.

This means that at the time we come to simplify the template, we have a strategy and a representation of a template for each value. So we use that strategy to simplify the value and serialize the results back. This means that the next time we try the example we have a candidate for something simpler to run with.

This works fairly well, albeit partly due to the choice of fairly stable strategies and compatible serialization formats – e.g. I’ve used this with sampled_from() based strategies a lot, and these just serialize as integer indices so if you’ve picked something early in the list it will remain valid if you simplify it, even if you remove an element of two from the list elsewhere in the simplify.

This is still a work in progress, and there are a bunch more things I’d like to do to improve it – for example one problem that would be relatively easily solved is if there were several incompatible strategies you could get at a given stage. Currently this will not be correctly simplified, but by storing a couple of different serialized representations you could try multiple until one works.

All told I’m not really sure where I feel about this on a scale of great to guilty. I’m really happy with the end result, and I’m somewhat amazed that this was even possible, but I’m looking forward to great improvements in both the implementation and the API.

When asked what’s genuinely novel in Hypothesis as opposed to mere optimisation, I usually cite three things:

1. Strategies carry simplification and serialization with them but still compose monadically.
2. The data generation can hit corners of the search space that standard Quickcheck can not, and adapt dynamically to requirements.
3. The simplification is much more sophisticated than the standard Quickcheck interface and can adapt to the structure of the problem much better.

It took me a surprisingly long time to notice that all three of these rely on essentially the same tweak to the standard API.

The tweak is this: Introduce an intermediate representation.

1. By introducing an intermediate template type which is then reified to the final result, you can simplify a mapped object by simplifying the argument.
2. Instead of generating a random value, you first generate a random parameter and then draw a conditional value given that parameter. As well as producing more interesting results this way (because of how you compose parameters for e.g. lists) this also lets you reuse parameters which are more likely to give you a useful result.
3. Instead of having a single simplify function, you have a list of simplifiers which you apply in turn.

Each of these have taken what was a single step and broken it up into two steps which you can naturally compose to give the original. We then don’t compose these in the obvious way, but instead change things around just enough to give something strictly more powerful while still mostly retaining the original characteristics.

I’m not sure what the broader significance of this is yet, but it seems likely that this approach has other areas to which you could apply it.

Simplification in Hypothesis is something of a vanity feature for me. I spend significantly more development effort on it than it strictly warrants, because I like nice examples. In reality it doesn’t really matter if the simplest value of a list of integers with at least three duplicates is [0, 0, 0] or [-37, -37, -37] but it matters to me because the latter makes me look bad. (To me. Nobody else cares I suspect)

So I was really pleased that I got simultaneous simplification in as a feature for Hypothesis 1.0. If a list contains a bunch of duplicate values (and because templating this is easy to check for – all templates are hashable and comparable for equality) before trying to simplify them individually, Hypothesis tries to simplify them in a batch all at once.

As well as solving the above ugly example, this turns out to be really good for performance when it fires. Even if your test case has nothing to do with duplication, a lot of the time there will be elements in the list whose value fundamentally doesn’t matter. e.g. imagine that all that is needed to trigger a failure is a list of more than 100 elements. The individual elements don’t matter at all. If we happen to have produced an example where we have a list of 100 elements of the same value, we can simplify this 100x as fast as if we had to simplify every individual element.

I’m doing a bunch of work on simplification at the moment, and as a result I have lots of tests for example quality of the form “In this circumstance, Hypothesis should produce an example that looks like this”. Some of them had a tendency to get into really pathological performance problems because they’re in exactly this scenario: They have to do a lot of individual simplifications of values in order to find an optimal solution, and this takes a long time. For example, I have a test that says that the list must contain at least 70 elements of size at least ten. This example was deliberately constructed to make some of the existing most powerful simplification passes in Hypothesis cry, but it ended up wreaking havoc on basically all the passes. The goal is that you should get a list of 70 copies of 10 out at the end, and the simplification run should not take more than 5 seconds.

This obviously is going to work well with simultaneous simplification: If you have a set of duplicate indices greater than 10, simultaneous simplification will move them all to 10 at once.

Unfortunately the chances of getting an interesting amount of duplication for integers larger than 10 is pretty low, so this rarely fires and we usually have to fall back to individual simplification which ends up taking ages (I don’t actually know how long – I’ve got a hard 5 second timeout on the test that it usually hits, but eyeballing it it looked like it got about halfway in that time).

So the question is this: Can we design another simplification pass that is designed to deliberately put the list into a state where simultaneous simplification can fire?

On the face of it the answer is obviously yes: You can just change a bunch of elements in the list into duplicates. Then if any of those are also falsifying examples we end up in a state where we can apply simultaneous simplification and race to the finish line.

Naturally there’s a wrinkle. The problem is that simplification in Hypothesis should be designed to make progress towards a goal. Loops aren’t a problem, but things which cause unbounded paths in the simplify graph will cause it to spend a vast amount of time not doing anything very useful until it gets bored of this simplification, declares enough is enough, and gives you whatever it’s got at the time (a lesson I should probably learn from my own creation).

Or, to put it more directly: How can we tell if a list of cloned elements is actually simpler. If we have [1, 2, 3, 4, 5, 6, 7, 8, 9999999999999999] we’d really much rather clone 1 all over the place than 9999999999999999.

The solution is to extend SearchStrategy with yet another bloody method (it has a default, fortunately), which allows it to test whether one of two templates should be consider strictly simpler than the other. This is a strict partial order, so x is not strictly simpler than x and it needn’t be the case that for any x and y one of the two is simpler. In general this is intended as a heuristic, so fast is better than high accuracy.

For the particular case of integers the rule is that every positive number is simpler than every negative number, and otherwise a number is simpler if it’s closer to zero.

We can now use this to implement a cloning strategy which always makes progress towards a simpler list (or produces nothing):

1. Pick a random element of the list. Call this the original.
2. Find the indices of every element in the list for which the original is strictly simpler.
3. If that set is empty, nothing to do here.
4. Otherwise pick a random subset of those indices (the current choice is that we pick an integer uniformly at random between 1 and the size of the list and then pick that many elements. This is not a terribly scientifically chosen approach but seems to work well).
5. Replace the element in each index we selected with a clone of the original

Empirically this seems to do a very good job of solving the particular example it was designed to solve and does not harm the remaining cases too much (I also have an example which deliberately throws away duplicates. Believe it or not this sped that example up).

It’s unclear how useful this is in real practical tests, but it at the very least shouldn’t hurt and appears it would often help. The list generation code is fairly fundamental in that most other collection generation code (and later on, stateful testing) is built on it, so it’s worth putting in this sort of effort.

The following is the release announcement I sent to the testing in python mailing list and the main python mailing list:

Hypothesis is a Python library for turning unit tests into generative tests,
covering a far wider range of cases than you can manually. Rather than just
testing for the things you already know about, Hypothesis goes out and
actively hunts for bugs in your code. It usually finds them, and when it
does it gives you simple and easy to read examples to demonstrate.

Hypothesis is based on Quickcheck (
https://wiki.haskell.org/Introduction_to_QuickCheck2) but is designed to
have a naturally Pythonic API and integrate well with Python testing
libraries.

It’s easy to use, extremely solid, and probably more devious than you
are at finding
edge cases.

The 1.0 release of Hypothesis has a stable and well documented public API.
It’s more than ready for you to use and it’s easy to get started.

Full documentation is available at
http://hypothesis.readthedocs.org/en/latest/, or if you prefer you can skip
straight to the quick start guide:
http://hypothesis.readthedocs.org/en/latest/quickstart.html

It seems to be a hit – less on the mailing list, but the link to it is doing the rounds of the internet and has the dubious honour of being the first time in ages I’ve been on the front page of Hacker News.