Edge cases, and testing with random inputs

What you will be able to do

After this lesson you can

• list the edge cases of a function before you test it,
• find a bug that appears only for repeats, for one item, or for nothing,
• test with random inputs against a trusted answer, and
• check properties that must always hold.

Where bugs live

Think about a function that gives the second largest number of a list. You try [5, 9, 2] and get 5. Right. You try [1, 2, 3, 4] and get 3. Right. It works! But does it?

Predict first. Which of the seven cases will fail? Then run it.

The function sorts the list from the biggest, and takes the item at position 1. For the usual cases, it is right. But look at what you did not think of.

• Repeats of the biggest: [9, 9, 3]. The sorted list is [9, 9, 3], and position 1 is 9. But the second largest different number is 3. A bug, if we want the second largest value.
• All equal: [5, 5, 5]. There is no second largest. What should the function say? The test says None.
• One item and empty: [8] and [] have no second item. The code raises an IndexError.

Four of the seven cases fail. The fixed version works with set (which drops the repeats) and checks the length before taking position 1. All seven cases pass.

The edge-case checklist

For almost any function, before you test, go through this list and ask: what does my function do for...

This list finds more bugs than any amount of testing with ordinary values.

Testing with random inputs

You cannot think of every case. A computer can try thousands. The method: make many random inputs, and compare the function with a trusted answer: a different way to compute the same thing that you know is right, such as Python's own sorted.

Comparing with a trusted answer. my_sort is an insertion sort with a hidden bug: it drops the last item of a list that has more than 4 items. first_failure makes 200 random lists (sizes 0 to 8, values 0 to 20), and compares my_sort(data) with sorted(data). It returns the first input where they differ. You see the exact input that breaks the function. For the correct function, sorted, it returns None: no failure.

Note random.seed(7). A seed makes the "random" inputs the same every time, so that a failure can be reproduced. A bug that appears sometimes and cannot be repeated is very hard to fix. The seed is the cure.

Properties. Sometimes there is no trusted answer, but there are things that must always be true. For a sort:

1. The result has the same length as the input.
2. The result is in order.
3. The result has the same items (a sorted copy of the result equals a sorted copy of the input).

check_properties tests all three on 100 random lists with assert. For the buggy sort, the first property fails: "the length changed". Properties are a powerful way to test: you state what must be true, and the computer looks for a counter-example.

Random tests are a net, not a proof. The edge cases on the checklist are still the first tests to write.

Assert inside the code

assert is also good inside a function, to check your own thinking, as the next program shows.

Common mistakes

• Testing only the middle of the range.
• Not deciding what the answer should be for the empty or the equal case. Decide, write it down, and test it.
• Random tests without a seed. A failure cannot be repeated.
• A "trusted answer" that is not trusted, such as another function that you wrote yourself and did not test.
• Checking only that the code does not crash. Check the answer.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the problem List the edges and the problem Second largest, again.
2. Build. Open the lab Find a failing input. You write the random tester, and the checker runs it on good and buggy sorts.
3. Stretch. Open the problem Properties of reverse and write three properties of a list reversal.

Remember these

• Bugs live at the edges: nothing, one, two, repeats, all equal, the ends, strange values.
• List the edge cases before you test.
• Random tests with a fixed seed, compared with a trusted answer, find bugs that nobody thought of, and can be repeated.
• A property is something that must always be true. Test it on many random inputs.
• assert inside a function checks the thinking of the code.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Why do we set a seed in a random test?

2. Name three properties of a correct sorting function.

3. What does second_largest([9, 9, 3]) give in the buggy version, and what should it give?