How Do We Know It’s Correct?

In the last chapter we built two implementations of the List ADT, ArrayList and LinkedList, and we wrote down a contract: the promises every list makes, documented on the List interface. We claimed that both classes keep that contract. But we have not shown that they do. How do we actually know our ArrayList is correct?

So far, our evidence has been informal. We wrote the code carefully, and perhaps we ran it once to see if it produced the output we expected. A check like that usually looks something like this:

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);

System.out.println(list.size());  // prints 3   — looks right
System.out.println(list.get(0));  // prints 10  — looks right
list.remove(20);
System.out.println(list.size());  // prints 2   — looks right

Everything prints what we expected, so we move on.

That check tested a handful of cases we happened to type. It did not call get(-1), even though the contract promises an IndexOutOfBoundsException for that. It also did not try to remove a value that is not in the list, it did not run on an empty list, and it did not remove the last element. If there is a bug in any of those cases, we would not know about it.

There are two more problems here.

First, we are the ones deciding pass or fail. The program prints numbers. A human has to read them and judge whether each one is correct. It is easy to glance at a wrong number and not notice, especially across dozens of lines of output.

Second, it is not repeatable. We change the code all the time. We fix a bug, or we add a feature, or we rewrite something to make it faster. Every time we do, we would have to run the check again and re-read all the output by eye to make sure we did not break anything. In practice, nobody does this reliably. After a while we stop running the check, and then it tells us nothing about the code.

What we want instead is something we write down once. We state the cases we expect, including the awkward edge cases. The machine runs all of them for us, and it reports pass or fail every time we change the code, without a human reading the output. This is called an automated test. In this chapter we will learn to write them.

An implementation is correct when every operation behaves as the contract specifies, for all valid inputs, including the edge cases, not just for the few we tried by hand. Notice that this definition is stated in terms of the contract, not the code. Both ArrayList and LinkedList keep the same List contract, so the right thing to test is the contract itself. We will come back to that idea once we have the basic tools.

The first tool we need is a library for writing and running tests.