conjectureprototype.py

import os
import struct


class Rejected(Exception):
    pass


class TestContext(object):
    def __init__(self, data, should_report):
        self.data = data
        self.should_report = should_report
        self.index = 0

    def getbytes(self, n):
        if self.index + n > len(self.data):
            raise Rejected()
        result = self.data[self.index:self.index+n]
        self.index += n
        return result

    def report(self, text):
        if self.should_report:
            print(text)

    def declare(self, name, value):
        self.report("%s = %r" % (name, value))
        return value


MAX_SIZE = 1024 * 1024


def shrink(data):
    if not data:
        return
    for i in range(len(data)):
        for j in range(len(data), i, -1):
            yield data[:i] + data[j:]
    for i in range(len(data)):
        for j in range(len(data), i, -1):
            result = data[:i] + (b'\0' * (j - i)) + data[j:]
            if result == data:
                break
            yield result
    for i in range(len(data)):
        unpacked = list(data)
        for c in range(data[i]):
            unpacked[i] = c
            yield bytes(unpacked)
    for i in range(len(data) - 1):
        if data[i] > data[i+1]:
            unpacked = list(data)
            unpacked[i], unpacked[i+1] = unpacked[i+1], unpacked[i]
            yield bytes(unpacked)


def simpler(x, y):
    return (len(x), x) < (len(y), y)


def runtest(test):
    def accept():
        n = 8
        good_examples = 0
        rejected_examples = 0
        failure = None
        while good_examples < 200:
            good_examples += 1
            data = os.urandom(n)
            try:
                test(TestContext(data, False))
            except Rejected:
                good_examples -= 1
                rejected_examples += 1
                n = min(n * 2, MAX_SIZE)
            except Exception:
                failure = data
                break
        shrinks = 0
        if failure is not None:
            while True:
                for shrunk in shrink(failure):
                    assert simpler(shrunk, failure)
                    try:
                        good_examples += 1
                        test(TestContext(shrunk, False))
                    except Rejected:
                        good_examples -= 1
                        rejected_examples += 1
                        continue
                    except Exception:
                        print("Shrunk %r to %r" % (failure, shrunk))
                        shrinks += 1
                        failure = shrunk
                        break
                else:
                    break

            print((
                "Considered %d valid examples, %d rejected,"
                " with %d successful shrinks") % (
                good_examples, rejected_examples, shrinks
            ))
            print("Final data: %r" % (failure,))
            test(TestContext(failure, True))
        else:
            print("No failures in %d good examples and %d rejected" % (
                good_examples, rejected_examples
            ))
    accept.__name__ = test.__name__
    return accept


def draw_struct(context, code):
    data = context.getbytes(struct.calcsize(code))
    return struct.unpack(code, data)[0]


def draw_list(context, draw_element, min_size=0):
    threshold = draw_struct(context, 'c')
    result = []
    while True:
        if len(result) < min_size:
            result.append(draw_element(context))
        else:
            probe = draw_struct(context, 'c')
            if probe >= threshold:
                break
            else:
                result.append(draw_element(context))
    return result


def draw_integer(context, min_value, max_value):
    n = max_value - min_value
    mask = saturate(n)
    while True:
        x = draw_struct(context, '>L') & mask
        if x <= n:
            return min_value + x


def saturate(x):
    # FIXME: This is horribly inefficient
    for _ in range(64):
        x |= (x >> 1)
    return x

test_stuff.py

import conjectureprototype as p


@p.runtest
def test_dislike_zero(context):
    data = context.declare('data', context.getbytes(9))
    assert hash(data) & 1


@p.runtest
def test_lists_are_vaguely_sorted(context):
    ls = context.declare(
        'ls', p.draw_list(context, lambda c: p.draw_struct(c, '>L')))
    assert ls <= list(reversed(ls))


@p.runtest
def test_lists_of_lists_are_vaguely_sorted(context):
    ls = context.declare('ls', p.draw_list(
        context, lambda c: p.draw_list(c, lambda c2: p.draw_struct(c2, '>L'))))
    assert ls <= list(reversed(ls))


@p.runtest
def test_small_sums(context):
    x = context.declare('x', p.draw_integer(context, 1, 10))
    y = context.declare('y', p.draw_integer(context, 5, 11))
    assert x + y < 10


@p.runtest
def test_associative_floats(context):
    x = context.declare('x', p.draw_struct(context, 'd'))
    y = context.declare('y', p.draw_struct(context, 'd'))
    z = context.declare('z', p.draw_struct(context, 'd'))
    assert (x + y) + z == x + (y + z)