Beautiful Code [135]
In other words, I have logic of the form p implies q (or, p q, using logic notation), which means I am only testing half of what I should be testing. I should also have tests of the form q p:[§§]
[§§] Of course, either p, q, or both, could be negated (e.g., ~p ~q, or p ~q). I am arbitrarily using p and q as stand-ins for any predicate about the return value and the array parameter, respectively. What's important here is to recognize that when you are programming, you typically think in terms of p q (if p is true, then q must happen—the so-called happy path: the normal, most common usage of the code). When you are testing, however, you must force yourself to think both backward (q ?, or if q is true what must be true about p?), and in negative terms (if p is not true [i.e., ~p], what must be true about q?).
If something is true about the testArray and the target, then something else must be true about the return value.
This is a bit tricky, but important, so let me clarify with some specifics. The tests for Theory 1 verify that when the return value is -1, the target element is not in the array. But they don't verify that when the target element is not in the array, the return value is -1. In other words: if I only had this one theory with which to test, an implementation that returned -1 sometimes, but not every time it should, would still pass all my tests. A similar problem exists with Theory 2.
I can demonstrate this with mutation testing, a technique for testing the tests invented by Jeff Offut. The basic idea is to mutate the code under tests with some known bugs. If the tests you have still pass despite the bug in the code, then the tests are probably not as thorough as they need to be.
Let me mutate binarySearch in some drastic and arbitrary way. I'll try do this: if target is greater than 424242 and target is not contained in the array, instead of returning -1, I am going to return -42. How's that for software vandalism? See the tail end of the following code:
public static int binarySearch(int[] a, int target) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
int midVal = a[mid];
if (midVal < target)
low = mid + 1;
else if (midVal > target)
high = mid - 1;
else
return mid;
}
if (target <= 424242)
return -1;
else
return -42;
}
Hopefully, you'll agree that this is a pretty big mutation: the code returns an unexpected and unspecified value if the target is a number greater than 424242 and is not contained in the array. And yet, all the tests we have written so far pass with flying colors.
We definitely need to add at least a couple more theories to make the tests tighter and catch this category of mutations:
Theory 3: If testArray does not contain target, then it must return -1.
Theory 4: If testArray contains target at position n, then binarySearch (testArray, target) must return n.
These theories are tested as follows:
public void assertTheory3(int[] testArray, int target, int returnValue) {
if (!arrayContainsTarget(testArray, target))
assertEquals(-1, returnValue);
}
public void assertTheory4(int[] testArray, int target, int returnValue) {
assertEquals(getTargetPosition(testArray, target), returnValue);
}
public int getTargetPosition(int[] testArray, int target) {
for (int i = 0; i < testArray.length; i++)
if (testArray[i] == target)
return i;
return -1;
}
Notice that I had to create another helper method, getTargetPosition, which has exactly the same behavior as binarySearch (but I am confident that it works properly, with the huge downside that it requires up to n instead of log2n comparisons). Because getTargetPosition is very similar to arrayContainsTarget, and code duplication is bad, I rewrite the latter as follows:
public boolean arrayContainsTarget(int[] testArray, int target) {
return getTargetPosition(testArray, target) >= 0;
}
I run these tests again with my random-array generator, and now the return-42 mutation is caught immediately.