Beautiful Code [133]
This is a known problem with programmers testing their own code. If they can't think of some scenarios when implementing the code, it's likely that they will not be able to think of them when they switch context and try to break the code. Truly beautiful testing requires a developer to make an extra effort, think outside the box, explore weird scenarios, look for weaknesses, and try to break things.
So, what haven't I thought of? My smoke test and boundary tests do not feel sufficient. Is my test set representative enough that I can, through some form of induction,[**] claim the code will work in all instances? The words of Joshua Bloch echo in my mind: "…It is hard to write even the smallest piece of code correctly."
[**] By induction, I mean deriving general principles from particular facts or instances.
What kind of tests would make me feel confident enough that my implementation will do the right thing with all sorts of inputs—not just the ones I handcrafted?
7.3.3. Random Acts of Testing
So far I've written traditional, tried-and-true types of tests. I used a few concrete examples to test the search code against my expectations of what the correct behavior should be in those cases. Those tests all pass, so I have some level of confidence in my code. But I also realize that my tests are very specific and cover only a very small subset of all the possible inputs. What I would like, and what would help me sleep at night knowing my code has been thoroughly covered, is a way of testing over a much broader set of inputs. For this to happen I need two things:
A way to generate a large and diverse set of inputs
A set of generalized assertions that will work on any input
Let's tackle the first requirement.
What I need here is a way to generate arrays of integers of all shapes and sizes. The only requirement I am going to make is that the resulting arrays are sorted, because that's a precondition. Other than that, anything goes. Here's my initial implementation of the generator:[]
[] I say initial implementation because I quickly realized that I needed to populate the array with negative as well as positive numbers, and changed the generator accordingly.
public int[] generateRandomSortedArray(int maxArraySize, int maxValue) {
int arraySize = 1 + rand.nextInt(maxArraySize);
int[] randomArray = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
randomArray[i] = rand.nextInt(maxValue);
}
Arrays.sort(randomArray);
return randomArray;
}
For my generator, I take advantage of java.util's random-number generator and Arrays utilities. The latter once contained the very same binary-search bug Joshua Bloch mentioned in his blog, but it's fixed in the version of Java I am using. Because I already covered the handling of empty arrays to my satisfaction in my other tests, I use a minimum array size here of 1. The generator is parameterized because I might want to create different sets of tests as I go along: some with small arrays containing big numbers, some with big arrays and small numbers, and so on.
Now I have to come up with some general statements about the desired behavior of the binary search that can be expressed as assertions. By "general," I mean statements that must hold true for any input array and target value. My colleagues Marat Boshernitsan and David Saff call these theories. The idea is that we have a theory of how the code should behave, and the more we test the theory, the more confident we can be that what we theorize is actually true. In the following example, I am going to apply a much