Testing properties, boundaries, and state transitions

Prerequisites: Functions, loops, and input contracts.

Learning objectives

• Distinguish examples, properties, and model-based tests.
• Construct boundary cases from the specification.
• Interpret coverage without treating it as proof.

Start with a claim that could be false

A test executes a program on selected inputs and compares observations with an oracle. The oracle may be a known output, an invariant, a simpler reference implementation, or a relationship between executions. Testing becomes more informative when you can name the fault a case would expose. Calling a function without asserting its behavior checks very little.

For a sorting function, checking that output length matches input length misses lost duplicates replaced by other values. Checking nondecreasing order alone misses an implementation that always returns an empty list. A useful contract combines ordering with preservation of the multiset. A separate stability requirement concerns the relative order of elements with equal keys; it is not implied by the first two properties.

Exhaust a small input space

Small exhaustive tests can be powerful because they make edge cases ordinary. The following standard Python example checks a reference insertion sort over every list of length zero through four using values −1, 0, and 1. There are 121 cases. This does not prove correctness for every list, but it covers empty inputs, duplicates, reverse order, and several combinations systematically.

from itertools import product
from collections import Counter

def insertion_sort(values):
    result = list(values)
    for i in range(1, len(result)):
        value, j = result[i], i
        while j > 0 and result[j-1] > value:
            result[j] = result[j-1]
            j -= 1
        result[j] = value
    return result

cases = 0
for size in range(5):
    for values in product([-1, 0, 1], repeat=size):
        output = insertion_sort(values)
        assert Counter(output) == Counter(values)
        assert all(a <= b for a, b in zip(output, output[1:]))
        cases += 1
assert cases == 121

Test histories as well as individual calls

For a reservation service, failures can depend on call order. A state-machine test maintains a simple model, generates operations, and compares model outcomes with the implementation. Include invalid transitions and retries. Concurrent tests require controlled schedules or histories, since running two threads once may never produce the problematic interleaving.

Code coverage reports which code was exercised. It does not establish that assertions were meaningful, that all values were covered, or that concurrency assumptions held. Mutation testing offers another lens: deliberately introduce small faults and see whether tests detect them. A surviving mutation might expose a weak test or an equivalent program; inspect rather than treating the score as unquestionable.

Keep tests reproducible by recording seeds and reducing failing examples. A minimal counterexample is easier to explain and preserve as a regression case. Tests are engineering evidence with a scope, not a replacement for reasoning about invariants and termination.

Practice problem

For a binary-search function returning the first index at which a value could be inserted, state three postconditions and construct cases covering empty input, duplicates, a target below all values, and a target above all values.

Worked solution

For result i on sorted array a: 0≤i≤len(a); every element before i is less than the target; every element from i onward is at least the target. [] with target 4 returns 0; [2,2,5] with target 2 returns 0; [2,5] with target 1 returns 0; [2,5] with target 8 returns 2. Also test [2,2,5] with target 3, which returns 2. These contracts distinguish lower-bound search from a search that returns any matching duplicate.

Check your understanding

Which two properties together characterize a sorted permutation?

• Fixed length and positive values.
• No duplicates and nondecreasing order.
• Nondecreasing order and equal input/output multisets.
• A runtime below one second.

Explanation

Ordering and multiset preservation cover different obligations; sorting need not remove duplicates.

A test executes every line but asserts only that no exception occurred. What does coverage establish?

• The algorithm is correct.
• Those lines ran, with little evidence about their results.
• All branches and input values were tested.
• Concurrent schedules are safe.

Explanation

Execution coverage does not measure the strength of the oracle or the completeness of the input space.

Primary reading

• Software Engineering at Google: Google, open book
• How to Design Programs: Felleisen et al.

Open the study and save your work →