I’ve just merged a branch with a redesign of the hypothesis core into master. All the tests are passing, and I’m much happier with the new design than I was with the old one. It takes the idea of the search strategy I mentioned in my previous post and makes it the fundamental building block of the library. This seems to work quite well.

But in doing this rewrite I’ve gone and taken something which was always at the core of hypothesis and made it explicit, and it’s pretty… well actually I don’t want to say it’s bad per se. Using it has actually been very pleasant, and it’s made some very nice things possible that would otherwise have been quite awkward to do.

So while it’s not exactly bad, it’s sure as hell unpythonic.

What is it?

Well, it’s essentially a highly dynamic multiple dispatch object model with prototype based inheritance.

Err, yeah.

Why, David? Why do you do this?

Well, I arrived at it through a sequence of individually logical steps.

Here’s what drove me down this path:

The first requirement:

We need to be able to go from a type to a strategy. e.g. we want to say “give me a strategy for ints”. Or “give me a strategy for strings”. Or “give me a strategy for tuples of (int, str)”.

However, we absolutely don’t want to put the logic for this on the types themselves. We’re not going to monkey patch things to add in a strategy method or anything uncouth like that.

There are two reasons we’re not going to do that:

1. We want to be able to configure specific strategies per run, e.g. biasing for short lists or only producing alphanumeric strings
2. It would be gross

Note also that we need to be able to pass instances, not just types here. For example we can ask for a strategy for the tuple (int, str) which will give us a strategy returning pairs where the first is an int and the second a string.

So that’s where the multiple dispatch came from. It’s not implemented in any very clever way, and it currently is closer to just type based overriding than true multiple dispatch because it doesn’t support subtyping (if you define a handler for instances of Foo then it will not trigger for instances of subclasses of Foo. I may fix this at some point but I currently have no need to do so).

Where does the prototype based inheritance come in?

Well, it started at just level one: There was a single default object which all other lookups would delegate to if needed. The reason for this was that it allowed you to both define new strategy handlers wherever you wanted because you could define them on the default object, but you could then override them on a fresh local copy.

Then I realised that having full prototype based inheritance was no more work and was actually quite useful. So I provided that.

Why? Let me show you an example of its usage in practice. Here’s how we define the strategy for strings:

class StringStrategy(MappedSearchStrategy):
    def __init__( self,
                    strategies,
                    descriptor,
                    **kwargs):
        SearchStrategy.__init__(self, strategies, descriptor,**kwargs)
        self.length_strategy = strategies.strategy(int)
        char_strategy = kwargs.get("char_strategy",
                                   OneCharStringStrategy)
 
        cs = strategies.new_child_mapper()
        cs.define_specification_for(str, char_strategy)
        self.mapped_strategy = cs.strategy([str])
 
    def pack(self, ls):
        return ''.join(ls)
 
    def unpack(self, s):
        return list(s)

What are we doing here?

Well, MappedSearchStrategy lets you define a search strategy in terms of another one. You then just need to define methods for converting to and from instances of that other type. In this case we are defining the strategy for strings in terms of the strategy for lists of strings.

Which makes it sound like it’s recursive, but it’s not. Let me draw your attention to the following bit:

        char_strategy = kwargs.get("char_strategy",
                                   OneCharStringStrategy)        
        cs = strategies.new_child_mapper()
        cs.define_specification_for(str, char_strategy)
        self.mapped_strategy = cs.strategy([str])

What do we have here?

We have another strategy for strings which only generates one character strings (python doesn’t have a Character data type). This is not normally installed anywhere.

We now create a new child mapper. This is a fresh SearchStrategies object whose prototype is the SearchStrategies object we started with. We can now define a strategy for strings on it, which overrides strings for that mapper but leaves the original untouched. When we ask it for a strategy for lists of strings, it uses the list strategy it’s inherited and the string strategy that’s just been defined for it to give a strategy for lists of strings that uses the new one character string strategy.

This isn’t the only place it’s used. We also use it in stateful testing in a broadly similar way for generating the individual test steps without interfering with the larger strategies namespace.

Is this all a terrible idea? I dunno. It works pretty well, and it’s allowed to write some quite interestingly powerful code, but I do have the feeling that it’s probably a bit too clever and that there might be a better solution.

I’ve just merged a branch with a redesign of the hypothesis core into master. All the tests are passing, and I’m much happier with the new design than I was...

The idea of stateful testing is that it is “quickcheck for mutable data structures”.

The way it works is that rather than trying to produce arguments which falsify an example, we instead try and produce a sequence of operations which break a data structure.

Let me show you. We’re going to start with the following broken implementation of a set:

class BadSet:
    def __init__(self):
        self.data = []
 
    def add(self, arg):
        self.data.append(arg)
 
    def remove(self, arg):
        for i in xrange(0, len(self.data)):
            if self.data[i] == arg:
                del self.data[i]
                break
 
    def contains(self, arg):
        return arg in self.data

Because it uses an array internally to store its items and doesn’t check if an item is already contained when adding it, if you add an item twice and then remove it then the item will still be there.

(Obviously this is a really stupid example, but it should demonstrate how it works for more complicated examples)

Now lets write some tests that break this!

The operations we want to test are adding and removing elements. So we do the following:

from hypothesis.statefultesting import StatefulTest, step, requires
 
class BadSetTester(StatefulTest):
    def __init__(self):
        self.target = BadSet()
 
    @step
    @requires(int)
    def add(self,i):
        self.target.add(i)
        assert self.target.contains(i)
 
    @step
    @requires(int)
    def remove(self,i):
        self.target.remove(i)
        assert not self.target.contains(i)

We can now ask this to produce us a breaking example:

>>> print BadSetTester.breaking_example()
[('add', 0), ('add', 0), ('remove', 0)]

Note the nicely minimized example sequence.

At the moment this code is very much a work in progress – what I have works, but should probably be considered a sketch of how it might work rather than a finished product. As such, feedback would very definitely be appreciated.

The idea of stateful testing is that it is “quickcheck for mutable data structures”. The way it works is that rather than trying to produce arguments which falsify an example,...

So I’ve been tinkering a bit more with hypothesis. I would now cautiously label it “probably not too broken and I’m unlikely to completely change the API”. The version number is currently 0.0.4 though, so you should certainly regard it with some degree of suspicion. However I’m now reasonably confident that it’s good enough for simple usage in the sense that I expect bug reports from most people who use it in anger but probably not all people and probably not many bug reports from most. :-)

Since the initial version I’ve mostly been thinking about the API and fixing anything that was really obviously stupid. I’ve also cleaned up a bunch of internals. The implementation is still pretty far from perfect, but it’s no longer awful.

Most importantly, I’ve added a feature to it that makes it actually useful. Test integration! You can now use it for some fairly pretty quickcheck style testing:

@given(int,int)
def test_int_addition_is_commutative(x,y):
    assert x + y == y + x
 
@given(str,str)
def test_str_addition_is_commutative(x,y):
    assert x + y == y + x

The first test will pass, because int addition really is commutative, but of course string addition is not so what you’ll get is an error from the test suite:

    x = '0', y = '1'
 
    @given(str,str)
    def test_str_addition_is_commutative(x,y):
>       assert x + y == y + x
E       assert '01' == '10'
E         - 01
E         + 10

This doesn’t currently support passing keyword arguments through to the tests – all arguments have to be positional. I think I know how to fix this, I just haven’t sorted out the details yet.

But yeah, quickcheck style testing with test case minimization (look at how nice the counter-example it produced was!). If that turns out to be exactly what you’ve always wanted, go wild.

So I’ve been tinkering a bit more with hypothesis. I would now cautiously label it “probably not too broken and I’m unlikely to completely change the API”. The version number...