Covering the Edge Cases

We have tested an empty list, a single add and get, and an out-of-range index. Bugs are more likely at the edges of the behavior than in the common case. An add that looks correct may still mishandle the first element added to an empty list. A get may be right everywhere except the very last index. A remove may work until it has to remove the only element.

The same small set of edge cases comes up for almost every collection. For a list, a thorough suite includes:

• The empty list. Size is 0; get at any index throws; contains is false; remove returns false. The starting state needs its own tests because a lot of code has a special case for an empty collection.
• A single element. Adding one element should grow the size to 1, make contains return true, and make the element retrievable at index 0. The change from an empty list to a list with one element is where many off-by-one bugs occur.
• Several elements. Elements come back in the order they were added; get returns the correct element at every valid index.
• Duplicates. Add the same value twice and check exactly what the contract promises: indexOf returns the first occurrence, remove deletes the first occurrence, contains is still true afterward.
• The boundaries of the index. Index 0 and index size - 1 are valid and must return the right element; index -1 and index size are invalid and must throw. The boundary between valid and invalid indices is a common source of bugs.
• Removal positions. Removing the first element, a middle element, the last element, the only element, and an element that is not present (which returns false and changes nothing) are different code paths.
• Edge arguments. If the contract says something about unusual arguments, such as a null element, write a test for what it says.

Let’s write a few of these as tests:

@Test
public void indexOfReturnsFirstOccurrence() {
  list.add(7);
  list.add(7);
  assertEquals(0, list.indexOf(7));
}

@Test
public void removeOnlyElementReturnsTrue() {
  list.add(99);
  assertTrue(list.remove(99));
}

@Test
public void removeOnlyElementLeavesEmpty() {
  list.add(99);
  list.remove(99);
  assertEquals(0, list.size());
}

@Test
public void removeMissingElementReturnsFalse() {
  list.add(1);
  assertFalse(list.remove(2));
}

@Test
public void removeMissingElementLeavesSizeUnchanged() {
  list.add(1);
  list.remove(2);
  assertEquals(1, list.size());
}

Notice that JUnit has assertTrue and assertFalse in addition to assertEquals. The library provides a few other assertions, such as assertNull and assertNotNull, which are useful for testing the occasional method that returns a reference that may be null. We also used fail inside the try/catch idiom to assert that a method throws an exception when it is supposed to.

These edge-case tests are in ListTest, so they run against ArrayList and LinkedList. The edge cases are where two implementations differ most. A linked list’s node traversal can be off by one at the last index. An array-backed list can be wrong when the array is full and has to grow.

Sometimes you go to write an edge-case test and discover the contract never said what should happen. What does add(null) do? Does it store the null, or reject it? When a test makes you ask that question, you have found a missing case in the specification. I think a good test suite is also a good specification. If the contract does not say what should happen, the test says it, and seeing the test helps the implementer understand what is expected.