Choose Inputs for Walkthroughs

If you tried the preceding steps and still don't know what the bug is, you probably need to walk through the code by hand. In a sense, walking through the code is less than ideal. In a perfect world, you would prove to yourself that every section accomplishes its goal, that every variable sticks to its meaning, and that the proper value is returned or displayed, leaving no doubt that the function is correct for all inputs. Walking through the code introduces an element of uncertainty because no matter how many inputs you try, the bug might not be exposed by any of them.

Still, in many cases, the only way to unearth a bug is to walk through the code. To do this, you need to select inputs to the code. Except for short standalone programs that are hard-coded to calculate a given value (or set of values), all sections of code-be they a program, a function, or just a piece within a larger section of code-behave differently based on what input they receive.

In cases where you try to track down a bug that has been reported by someone else, that person might have provided specific inputs that cause the problem to occur. This is then your first candidate for a walkthrough. But, you need to choose your own series of inputs to figure out a hard-to-reproduce or insufficiently documented bug, to check new code before releasing it, or in cases where the reported inputs are too complicated to use. Walking through code is time consuming; you cannot walk through code with all possible inputs. Hopefully, you can walk through with a small sample that is nonetheless representative enough of all possible inputs to expose all possible bugs.

When you design inputs for code, remember that you are not limited to choosing only inputs to the outer function or the entire standalone program. In fact, it is often easier to break the code into smaller groups and walk through them first. After you are confident that these smaller groups handle various inputs correctly, you can move back and walk through larger sections of code without having to revisit the details of the sections you already checked.

The easiest way to break up code is when your functions are layered, one on top of another. Start with the lowest-level function, the one that does not make any calls to code that you are checking. Then, move up the chain, checking each outer function in turn.

You can do the same within a single function that you have split into logical sections. Pick a section that you want to check and then figure out the inputs for it. In this case, the "inputs" consist of values for all variables that are used within the section of code you are walking through. You should know which variables are relevant if you have determined the meaning of each variable.

If the program has any state data that it keeps from one execution of the code to the next, think of possible values for that as well. For example, in object-oriented languages, the function that you look at might be a method on a class; in this case, the current state of the class member variables (the ones that are used in the function) is logically part of the inputs to that function.

Finally, it should go without saying that when you select a test input, you need to know what your test output is supposed to be. Otherwise, it makes it difficult to decipher whether the program works correctly.

Code Coverage

When designing inputs with the code in front of you, you have an advantage over others who are doing "black box" testing on the code-who can execute only the code and cannot see the source. The advantage is that you can tailor your inputs to ensure that they exercise all the code. For example, if at some point in the code you have an if() condition that can be either true or false, you can make sure you provide at least one input that makes the condition true and one that makes it false.

It might be tempting to think that any reasonably large or diverse group of inputs will naturally cover all the code-in particular, that everyday usage for some period of time will do so. This is unlikely to be true. In fact, code that is executed on every input is more likely to be correct than code that runs rarely. This is because errors in the common code are more likely to have been found during initial development and debugging.

Consider Donald Knuth's cautionary tale about assuming code coverage, taken from his essay "The Errors of T_eX" (for more about this essay, see Appendix A, "Classification of Bugs"):

In one of my early experiments, I wrote a small compiler for Burroughs Corporation, using an interpretive language specially devised for the occasion. I rigged the interpreter so that it would count how often each instruction was interpreted; then I tested the new system by compiling a large user application. To my surprise, this big test case didn't really test much; it left more than half of the frequency counts sitting at zero! Most of my code could have been completely messed up, yet this application would have worked fine. So I wrote a nasty, artificially contrived program. . . and of course I detected numerous new bugs while doing so. Still, I discovered that 10% of the code had not been exercised by the new test. I looked at the remaining zeros and said, Shucks, my source code [of his test input, not the compiler itself] wasn't nasty enough, it overlooked some special cases I had forgotten about. It was easy to add a few more statements, until eventually I had constructed a test routine that invoked all but one of the instructions in the compiler. (And I proved that the remaining instruction would never be executed in any circumstances, so I took it out.)

You cannot assume that all the code has been covered by your tests; instead, choose inputs that ensure it will be.

One aspect of code that you must keep in mind is the "implied else," that is, everything that is done if an if() is true, is not done if the if() is false. The most obvious case of an "implied else" is where no else body exists at all, such as in the following:

if (x = 5) {

    y = 7;

}

In this case, the "implied else" is that if x is not equal to 5, y retains its current value. However, even if there is an explicit else clause, something is often implied:

if (total > 20) {

    total = 0;

    carry = 1;

} else {

    total = total + 1;

}

The implied else here is that carry remains unchanged.

Of course, loops can be reversed (the logical meaning of the if() inverted and the if and else bodies swapped), as in the following rewrite of the previous fragment:

if (total <= 20) {

    total = total + 1;

} else {

    total = 0;

    carry = 1;

}

This means that else clauses also have an "implied if".

In terms of choosing inputs, you have to cover the "implied else" also. If you have code such as the following

if (tax > 0) {

    price += price * tax;

}

you might think that having just one input where tax is greater than 0 covers all the code because each line will be executed. But, you also need to think about covering the "implied else" by having an input where tax is equal to 0 and the if() is therefore false.

Empty Input

Empty input is a situation where there is no data to work on. For example, a program to sort an array is passed an array with zero elements; or a program to operate on strings is given an empty string. Typically, a program will handle this in one of two ways: either by explicitly checking for it at the beginning

void sort_array(int arr[], int count) {

    if (count == 0) {

        return;

    }

    // code to sort the array

}

or by handling the empty case as part of the main algorithm:

void sort_array(int arr[], int count) {

    for (int i = 0; i < count; i++) {

        // code to sort the array

    }

}

If count is 0, the test i < count fails immediately, so the main loop never iterates and the code correctly does nothing.

Whichever way the code handles the empty case, you need to determine what an appropriate empty input would be, and walk through the code with that input.

Trivial Input

Trivial input is the next step up from empty input: A possible list of items turns out to have only one item, so the work to be done is trivial or nonexistent. Examples of trivial inputs are a program that prints the first n prime numbers being asked to print the first one, or a program that removes duplicates from an array being given an array with only one element.

As with empty input, trivial input might be handled by performing a special check at the beginning, often combined with a check for the empty case

void remove_dups(int arr[], int count) {

    if (count < 2) {

        return;

    }

    // rest of remove_dups

}

or else trivial input can be taken care of as part of the main algorithm.

Again, neither way is "right" or "wrong." The goal is just to make sure the code works correctly when you walk through it with a trivial input. Especially in cases where the trivial case is handled by the main algorithm, walking through the code-even if it manages to handle the trivial case correctly-can make you aware of a situation in which it would handle a nontrivial case incorrectly.

Already Solved Input

Already solved input is for functions that are supposed to modify data in place. It refers to a situation in which nothing needs to be modified. An example of already solved input is when a function that uppercases a string discovers that the string is already uppercase.

The already solved input exercises the code that determines if something needs to be done, without (hopefully) executing the code that actually does something:

void upper_case(char * s, int len) {

    for (int j = 0; j < len; j++) {

        if ((s[j] >= 'a') && (s[j] <= 'z')) {

            // code to upper-case s[j] goes here

        }

    }

}

Unlike the empty and trivial inputs, it is usually impossible (or not worth the trouble) for the code to determine with an initial check whether the input is already solved. In the previous code, an input string s that was all uppercase would still cause the iteration of the entire for() loop. However, the if() on the next line would always be false, so any bugs in the code marked with the comment code to upper-case s[j] goes here would not be found.

When designing input for the already solved case, one question is how long the input needs to be. For example, with the previous code, how many characters would the string need to be to give the code an adequate workout? The answer to this question is highly relative. In general, using an input of between three and five "items" (where an item is one element in an array, one character in a string, and so on) is a good tradeoff between being short enough to feasibly walk through the code as it processes the entire input, and long enough to encounter any bugs that are dependent on the fact that a certain number of items are present in the input.

Pay attention to cases where the code seems to be doing too much in processing the already solved case. Moving data items around unnecessarily, even if they all wind up back in their original places, is certainly a performance issue, and might indicate a bug that will appear in some not already solved cases.

Error Input

Error input is input that is just plain wrong. Examples of this are a function that expects a numeric string is given a character string, or a function that expects a pointer is passed a NULL pointer.

With error input, in addition to making sure that the function handles it without crashing, a walkthrough should verify that it behaves in the correct way. In many cases, an actual error input should be handled differently from, say, an empty input, by returning a specific error value or throwing an exception.

In other situations, where a function is nested within other code that is part of the same module, an error input might be considered an error on the part of the calling function, and by design should not be handled. Of course, some functions do not have any input that could be considered a real error. But in most cases, it should be possible to come up with an error input and walk through it.

Loops

Just as you can't walk through your code with all possible inputs, you usually can't walk through every iteration of a loop. In some cases, you can control the number of iterations of the loop by limiting the input size. With code such as the following

int sum_array(int arr[], int count) {

    int j;

    for (j = 0; j < count; j++) {

        // code to sum the array

    }

    // return the sum

}

the input to the function directly controls how many times the loop iterates. The guidelines given earlier for the number of items in the input also apply here. First, try the code with count equal to 0 (the empty case), then with count equal to 1 (the trivial case), and then with count somewhere between 3 and 5.

Random Numbers

Some functions use a randomly generated number in their computations. These functions typically use a random-number package written by someone else, either part of the language, the operating system, or a separate library.

The main thing to worry about with random numbers is to check the exact range that the random number returns. Some numbers return a value that is between 0 and a specified number; others, between 0 and 1. In some cases, the top range of the random number is just less than the specified number, so they will never be equal. For example, Python has a standard import called random:

import random

index = int (len(my_array) * random.random())

The random.random() call returns a number between 0 and 1, but not equal to 1, so this call is a proper way to randomly pick an element out of an array. Because random.random() will never return exactly 1, the index calculated will never equal len(my_array) (which would be too high an index).

The value returned by the random-number generator is another input to the code, even if it appears suddenly in the middle. As such, you have to pick values for the random-number generator to return during your walkthrough.

It's best to first pick those that are at the lower and upper limits; in the case just shown, those would be 0 and a number just below 1. Picking other inputs usually depends on what is done next with the random number. If, as an example, the code does one of three things based on the result of the random number, pick three values to correspond to the three choices (it's likely that the values 0 and "just below 1" already covered two of the choices):

// Determine if the pitch was a ball, strike, or foul

rnd = random.random()

if rnd < 0.3:

    ball()

elif rnd < 0.75:

    strike()

else:

    foul()

In this case, you would want to pick one value that was less than 0.3, one that was between 0.3 and 0.75, and one that was above 0.75.

For random numbers that are used in a calculation as opposed to an explicit choice, picking a third choice that is halfway between the lower and upper limits is usually adequate.