Skip to the content ForoHackers
Log inJoin

Test a data structure against a boring model (property-based testing)

PythonQuality assuranceTesting
#1019 · race_condition_rita · · Report

Before writing example-based tests for a container, I write one property: "it behaves like the obvious slow implementation." Here the container is a fixed-capacity ring buffer, the model is a deque plus a length check.

from collections import deque
from hypothesis import given, strategies as st

class RingBuffer:
    def __init__(self, cap):
        self.buf = [None] * cap
        self.head = 0
        self.size = 0

    def push(self, x):
        if self.size == len(self.buf):
            return False
        self.buf[(self.head + self.size) % len(self.buf)] = x
        self.size += 1
        return True

    def pop(self):
        if self.size == 0:
            return None
        x = self.buf[self.head]
        self.head = (self.head + 1) % len(self.buf)
        self.size -= 1
        return x

ops = st.lists(st.one_of(
    st.tuples(st.just("push"), st.integers()),
    st.tuples(st.just("pop"), st.none())))

@given(ops, st.integers(min_value=1, max_value=8))
def test_matches_model(operations, cap):
    rb, model = RingBuffer(cap), deque()
    for op, x in operations:
        if op == "push":
            ok = rb.push(x)
            assert ok == (len(model) < cap)
            if ok:
                model.append(x)
        else:
            assert rb.pop() == (model.popleft() if model else None)

The framework generates hundreds of operation sequences, and when one fails it shrinks it to a minimal one. Bugs in wraparound (an off-by-one in % len) show up in seconds. My failure model for the test: single thread, no crash. Concurrency is another post.

#1455 · lambda_llama · · Report

This idea started in Haskell with QuickCheck, where the property is the whole point of the type signature. Glad it escaped into other languages. Consider adding a second property with the model as a tiny state machine; Hypothesis has stateful testing for exactly that.

#1456 · off_by_two · · Report

Nice. I would make the capacity range include 1. Wraparound bugs love the case where head and the end coincide on every operation.

#1457 · race_condition_rita · · Report

It does include 1, min_value=1. Capacity 0 would be a separate decision: should RingBuffer(0) even exist? That is a design question the generator cannot answer for you.

#1458 · tabs_over_spaces_42 · · Report

Reviewer note: this is the kind of test I will approve without a single nit. One property, a clear model, and it fails with a readable counterexample.

Log in or join to reply.