In the intro post I spoke about my experiments with checks we can give AI to get better validation of our changes.
Property-based testing is an interesting idea. Its quite popular in functional programming circles but I haven’t seen it where I’ve worked before. I think one reason is that it’s a different way to think about testing your code. Instead of thinking of specific cases that you want your code to cover, try to codify what should always be true for it. e.g. a sort function’s output should be sorted.
Let’s use a naive example. We want to allocate a number based on weights.
# allocation.py
def allocate_naive(total: int, weights: list[float]) -> list[int]:
"""Split ``total`` units across accounts in proportion to ``weights``.
>>> allocate_naive(10, [1.0, 1.0, 1.0])
[3, 3, 3]
Ten units in, nine units out.
"""
_validate(total, weights)
denominator = sum(weights)
return [round(total * w / denominator) for w in weights]
On the surface it looks reasonable. You can even create a few tests and see them pass.
# test_allocation_examples.py
from collections.abc import Callable
from typing import cast
import pytest
from allocation import AllocationError, allocate, allocate_naive
Allocator = Callable[[int, list[float]], list[int]]
IMPLEMENTATIONS = [allocate, allocate_naive]
@pytest.fixture(params=IMPLEMENTATIONS, ids=lambda f: f.__name__)
def alloc(request: pytest.FixtureRequest) -> Allocator:
return cast("Allocator", request.param)
def test_splits_evenly_between_two_accounts(alloc: Allocator) -> None:
assert alloc(100, [1.0, 1.0]) == [50, 50]
def test_respects_uneven_weights(alloc: Allocator) -> None:
assert alloc(100, [3.0, 1.0]) == [75, 25]
def test_weights_need_not_be_normalised(alloc: Allocator) -> None:
assert alloc(100, [30.0, 10.0]) == [75, 25]
def test_zero_total_allocates_nothing(alloc: Allocator) -> None:
assert alloc(0, [1.0, 2.0, 3.0]) == [0, 0, 0]
def test_single_account_takes_everything(alloc: Allocator) -> None:
assert alloc(500, [1.0]) == [500]
def test_account_with_zero_weight_gets_nothing(alloc: Allocator) -> None:
assert alloc(100, [1.0, 0.0]) == [100, 0]
def test_negative_total_is_rejected(alloc: Allocator) -> None:
with pytest.raises(AllocationError):
alloc(-1, [1.0])
def test_empty_weights_is_rejected(alloc: Allocator) -> None:
with pytest.raises(AllocationError):
alloc(100, [])
def test_zero_weights_is_rejected(alloc: Allocator) -> None:
with pytest.raises(AllocationError):
alloc(100, [0.0, 0.0])
Ship it? AI can create pages of these tests. LGTM?
What the property file looks like
# test_allocation_properties.py
from allocation import allocate
from hypothesis import given, settings
from hypothesis import strategies as st
totals = st.integers(min_value=0, max_value=10_000_000)
weights = st.lists(
st.floats(min_value=0.0, max_value=1_000.0, allow_nan=False, allow_infinity=False),
min_size=1,
max_size=24,
).filter(lambda ws: sum(ws) > 0)
There’s a lot here. Not that easy to write straight away. We are constraining what counts as a realistic input for our method. You have to think about what is possible, and revisit it when that changes.
Each test below is a property that we can logically say should stay true for any input. AI is very good at generating these too!
@given(total=totals, ws=weights)
def test_conservation(total: int, ws: list[float]) -> None:
"""Nothing is created and nothing is lost."""
assert sum(allocate(total, ws)) == total
@given(total=totals, ws=weights)
def test_parts_are_non_negative(total: int, ws: list[float]) -> None:
assert all(part >= 0 for part in allocate(total, ws))
@given(total=totals, ws=weights)
def test_no_account_exceeds_the_total(total: int, ws: list[float]) -> None:
assert all(part <= total for part in allocate(total, ws))
@given(total=totals, ws=weights)
def test_zero_weight_gets_zero(total: int, ws: list[float]) -> None:
"""An account with no target allocation must not receive units."""
parts = allocate(total, ws)
for weight, part in zip(ws, parts, strict=True):
if weight == 0.0:
assert part == 0
@given(total=totals, ws=weights)
def test_each_part_is_within_one_unit_of_its_exact_share(
total: int, ws: list[float]
) -> None:
"""Allocation stays faithful to the requested proportions.
Conservation alone is satisfiable by a function that dumps everything
into the first account, so it has to be pinned alongside fairness.
"""
denominator = sum(ws)
parts = allocate(total, ws)
for weight, part in zip(ws, parts, strict=True):
exact = total * weight / denominator
assert abs(part - exact) < 1.0
@given(total=totals, ws=weights)
@settings(max_examples=200)
def test_permuting_weights_permutes_the_allocation(
total: int, ws: list[float]
) -> None:
"""Order of accounts must not change who gets what."""
forward = allocate(total, ws)
reversed_result = allocate(total, list(reversed(ws)))
assert sorted(forward) == sorted(reversed_result)
After running them we find this failure. Oh no!
What’s really nice is that it gives you the input that caused the failure. Then you can just write another normal test for that specific case.
$ python 01-property-based/demo_failure.py
Property: sum(allocate(total, weights)) == total
FAILS allocate_naive
allocate_naive(1, [1.0, 1.0]) -> [0, 0] which sums to 0, not 1
Failing test case: prop(
total=1,
ws=[1.0, 1.0],
)
HOLDS allocate
no counterexample found in 500 examples
It doesn’t just give you the first massive input that breaks your code. It keeps on shrinking the input to smaller, simpler numbers until it finds the simplest one that still breaks it.
| total |
weights |
naive |
fixed |
| 10 |
[1, 1, 1] |
[3, 3, 3] → 9 |
[4, 3, 3] → 10 |
| 1 |
[1, 1] |
[0, 0] → 0 |
[1, 0] → 1 |
| 7 |
[1, 1, 1] |
[2, 2, 2] → 6 |
[3, 2, 2] → 7 |
Now you can fix the code and be more confident it works as expected.
def allocate(total: int, weights: list[float]) -> list[int]:
"""Largest-remainder allocation. Conserves the total exactly."""
_validate(total, weights)
denominator = sum(weights)
exact = [total * w / denominator for w in weights]
parts = [math.floor(x) for x in exact]
leftover = total - sum(parts)
if leftover:
# Largest fractional remainder first; index ascending as the tie-break.
order = sorted(range(len(weights)), key=lambda i: (-(exact[i] - parts[i]), i))
for i in order[:leftover]:
parts[i] += 1
return parts