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.

One of the decisions I’m quite happy I made is that the SearchStrategy API in Hypothesis is not public for 1.0. This gives me some freedom to break it when I figure out ways to make it better.

Which is good, because I’ve already figured out a way to break it to make it better.

In my fuzzer for yapf, I realised an interesting thing: The minimization happens in two phases, first line based, then character based. Once character based simplification has started we stop bothering with line based simplification altogether: Although in principle character based simplification could get us back into a state where line based simplification would be useful again, in practice this happens so rarely that trying line based simplification is basically never worth going back to.

Meanwhile, back in Hypothesis land, I was staring at the following quality test this morning:

def dedupe(xs):
    result = []
    for x in xs:
        if x not in result:
            result.append(x)
    return result
 
@given(strategy([bytes]).map(dedupe))
def is_sorted(xs):
    assume(len(xs) >= 10)
    assert sorted(xs) == xs

This is an example that is designed to fail and mostly exists to test the quality of the minimization: What’s the simplest list of byte strings it can find such that:

• The list only has distinct elements
• The list has at least 10 elements
• The list is not sorted

It’s not hard to find such an example – generally speaking Hypothesis will find an example within the first couple of throws of the dice – but producing a good example is harder, which is what this test looks for (In the actual test we make a bunch of assertions about the quality of the result we got at the end).

The problem is that sometimes this can get into a bad state where it takes an extraordinarily long time to minimize.

The problem is basically this: Every time it successfully minimizes an example, the simplification process starts again from scratch on the new example. This means that it tries all the usual simplifications for deleting elements from the list. These are a complete waste of time because they always shrink the list, violating the size assumption. But every time we shrink an element (and there are 10 elements to shrink) we do it all again.

I was originally thinking of trying to fix this in terms of making simplify skip simplifications which fail to produce examples too often, but that’s not really very satisfactory and requires a lot of delicate state tracking. It might be worth it in some cases, but I think it probably wouldn’t be.

Then I realised that this problem fits entirely into the approach I mentioned using for yapf, and we can use it to fix this problem.

Right now Hypothesis essentially follows the classic quickcheck API where there is a function shrink which takes values and provides a generator over simpler versions of the value. Simplified, the hypothesis example finding algorithm looks like:

def find_minimal(x, f):
    for s in shrink(x):
       if f(s):
          return find_minimal(s, f)
    return x

(that’s not actual Hypothesis code. The real implementation is more complex in several ways and doesn’t use recursion because Python, but it’s the idea of it).

The idea is to instead change this so that there are multiple shrinkers, each behaving like our shrink function above, and then we apply each shrinker in turn, never returning to an earlier one. This would be something akin to:

def minimize_with_shrinker(x, f, shrinker):
    for s in shrinker(x):
       if f(s):
          return minimize_with_shrinker(s, f, shrinker)
    return x
 
def find_minimal(x, f):
   for shrinker in shrinkers:
      x = minimize_with_shrinker(x, f, shrinker)
   return x

This lets us fix the list example by splitting up shrinking into two phases: First it tries to shrink by removing elements from the list. Then it tries to shrink by shrinking individual elements. Once it starts shrinking elements, the size of the list is fixed – it’s already found the smallest list it’s going to.

This does impact the quality of the examples a little bit. If necessary that could be fixed by iterating to a fixed point: We run the above algorithm then we run it again until it no longer changes the result. A simpler version would just be to run it twice. I don’t plan to do this unless I find the results from a single pass of this are much worse than I expect them to be. The goal here isn’t always to find the single simplest example, only to find a simple enough example in a short amount of time. I think this will be entirely acceptable quality and it should be very aceptable in time in comparison to the existing implementation.