Reading 13: Debugging

Start by finding a small, repeatable test case that produces the failure. If the bug was found by regression testing, then you’re in luck; you already have a failing test case in your test suite. If the bug was reported by a user, it may take some effort to reproduce the bug. For graphical user interfaces and multithreaded programs, a bug may be hard to reproduce consistently if it depends on timing of events or thread execution.

Nevertheless, any effort you put into making the test case small and repeatable will pay off, because you’ll have to run it over and over while you search for the bug and develop a fix for it. Furthermore, after you’ve successfully fixed the bug, you’ll want to add the test case to your regression test suite, so that the bug never crops up again. Once you have a test case for the bug, making this test work becomes your goal.

Here’s an example. Suppose you have written this function:

/**
 * Find the most common word in a string.
 * @param text string containing zero or more words, where a word
 *     is a string of alphanumeric characters bounded by nonalphanumerics.
 * @return a word that occurs maximally often in text, ignoring alphabetic case.
 */
public static String mostCommonWord(String text) {
    ...
}

A user passes the whole text of Shakespeare’s plays into your method, something like mostCommonWord(allShakespearesPlaysConcatenated), and discovers that instead of returning a predictably common English word like "the" or "a", the method returns something unexpected, perhaps "e".

Shakespeare’s plays have 100,000 lines containing over 800,000 words, so this input would be very painful to debug by normal methods, like print-debugging and breakpoint-debugging. Debugging will be easier if you first work on reducing the size of the buggy input to something manageable that still exhibits the same (or very similar) bug:

• does the first half of Shakespeare show the same bug? (Binary search! Always a good technique. More about this below.)
• does a single play have the same bug?
• does a single speech have the same bug?

Once you’ve found a small test case, find and fix the bug using that smaller test case, and then go back to the original buggy input and confirm that you fixed the same bug.

To localize the bug and its cause, you can use the scientific method:

1. Study the data. Look at the test input that causes the bug, and the incorrect results, failed assertions, and stack traces that result from it.

2. Hypothesize. Propose a hypothesis, consistent with all the data, about where the bug might be, or where it cannot be. It’s good to make this hypothesis general at first.

3. Experiment. Devise and run an experiment that tests your hypothesis. It’s good to make the experiment an observation at first – a probe that collects information but disturbs the system as little as possible.

4. Repeat. Add the data you collected from your experiment to what you knew before, and make a fresh hypothesis. Hopefully you have ruled out some possibilities and narrowed the set of possible locations and reasons for the bug.

This kind of deliberate process isn’t needed for every bug. With good fail-fast design, you’ll hopefully get an exception very close to the source of the bug, the stack trace will lead you right to it, and the mistake will be obvious from inspecting the code. So when do you need to apply the scientific method? A good rule of thumb is the 10-minute rule. If you’ve spent 10 minutes hunting for a bug using ad-hoc, unsystematic inspection, then it’s time to take a step back and start applying the scientific method instead.

As part of this transition, you should also move your debugging process out of your head – which has a very limited working memory of what you’ve tried and what you’ve learned from it – and start taking notes, either on paper or on your laptop. In each iteration of the process, you’ll be writing down:

• Hypothesis. Based on what you’ve learned so far, what’s your next hypothesis about the location or cause of the bug?
• Experiment. What are you about to try that will shed light (verify or falsify) on the hypothesis?
• Predictions. What do you expect, based on your hypothesis, to be the result of the experiment?
• Observations. What actually happened when you did the experiment?

These kinds of questions should be very familiar to you from your past experience in science classes. In the next few sections, we’ll see what kind of form they take when you’re debugging code. In debugging, some hypotheses and some experiments are better than others.

One important form of data is the stack trace from an exception. Practice reading the stack traces that you get, because they will give you enormous amounts of information about where and what the bug might be.

In a stack trace, the latest call is on top, and the oldest call is on the bottom. Sometimes the topmost call is your own code, but the exception may also have been thrown by library code that your code called, so the topmost call is not code that you wrote. Similarly, the bottommost call on the stack may be the main method that you wrote, but it may also be library code that you didn’t write, but which eventually called your code.

So your own code — where the bug is most likely to be — is often somewhere in the middle of the stack trace.

java.lang.NullPointerException
  at java.util.Objects.requireNonNull(Objects.java:203)
  at java.util.AbstractSet.removeAll(AbstractSet.java:169)
  at turtle.TurtleSoup.drawPersonalArt(TurtleSoup.java:29)
  at turtle.TurtleSoupTest.testPersonalArt(TurtleSoupTest.java:39)
  at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
  at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
  at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
  at java.lang.reflect.Method.invoke(Method.java:498)
  at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
  at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
  at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
  at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
  at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
  at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
  at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
  at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
  at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
  at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
  at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
  at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
  at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
  at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:86)
  at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
  at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:459)
  at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:678)
  at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:382)
  at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:192)

The point where the program actually failed, by throwing an exception or producing a wrong answer, isn’t necessarily where the bug is. The buggy code may have propagated some bad values through good parts of the program before it eventually failed. So your hypotheses should be about where the bug actually is (or is not), and what might have caused it.

It can help to think about your program as a flow of data, or steps in an algorithm, and try to rule out whole sections of the program at once. Let’s think about this in the context of the mostCommonWord() example, fleshed out a little more with three helper methods:

/**
 * Find the most common word in a string.
 * ...
 */
public static String mostCommonWord(String text) {
    List<String> words = splitIntoWords(text);
    Map<String,Integer> frequencies = countOccurrences(words);
    String winner = findMostFrequent(frequencies);
    return winner;
}

The flow of data in mostCommonWord() is shown at right.

Suppose that we’re getting an unexpected exception in countOccurrences(). That’s the failure that we’re investigating. Then we can rule out everything downstream of that point as a possible location for the bug. There’s no point in looking for the bug in findMostFrequent(), for example, because it hasn’t even been executed yet when the failure occurs.

So here are some hypotheses consistent with the information we have so far. They’re listed in reverse order of time from the failure:

• the bug is in countOccurrences: its input is valid but then it throws an exception
• the bug is in the connection between splitIntoWords and countOccurrences: both methods meet their contracts, but the postcondition guaranteed by the former doesn’t satisfy the precondition expected by the latter
• the bug is in splitIntoWords: its input is valid but it produces bad output
• the bug is in the original input to mostCommonWord: text doesn’t satisfy the precondition of the whole method

Which hypothesis to try first? Debugging is a search process, and you can use binary search to speed up the process. To do a binary search, you could divide this dataflow in half, perhaps guessing that the bug is in the connection between the first helper method and the second, and use one of the experiments below (like print statements, breakpoints, or assertions) to check the value there. From the answer to that experiment, you would know whether to pursue the bug in the earlier half of the dataflow or the later half.

Slicing

int x = 0; // must be >= 0
...
System.out.println("x=" + x);  // prints a negative number

int x = 0; // must be >= 0
...
    x += bonus;
...
System.out.println("x=" + x);  // prints a negative number

int x = 0; // must be >= 0
final int bonus = getBonus();
...
    x += bonus;
...
System.out.println("x=" + x);  // prints a negative number

int x = 0;
final int bonus = getBonus();
...
  if (isWorthABonus(s)) {
    x += bonus;
  }
...
System.out.println("x=" + x);  // prints a negative number

int x = 0;
final int bonus = getBonus();
...
for (final Sale s : salesList) {
  ...
  if (isWorthABonus(s)) {
    x += bonus;
  }
  ...
}
...
System.out.println("x=" + x);  // prints a negative number

int calculateTotalBonus(final List<Sale> salesList) {
  ...
  int x = 0;
  final int bonus = getBonus();
  ...
  for (final Sale s : salesList) {
    ...
    if (isWorthABonus(s)) {
      x += bonus;
    }
    ...
  }
  ...
  System.out.println("x=" + x);  // prints a negative number
  ...
}

double total = 0.0;
double tax = 0.0;
double taxRate = 0.06;
for (final Item item : items) {
  total += item.getPrice();
  if (isOutOfStateCustomer) {
    taxRate /= 2;
  }
  if (item.isTaxable()) {
    tax += item.getPrice() * taxRate;
  }
}
total += tax;
return total;

int[] incrementAll(int[] a) {
  int[] b = a;
  for (int i = 0; i < a.length; ++i) {
    ++b[i];
  }
  return b;
}

Delta debugging

Prioritize Hypotheses

/**
 * Solves quadratic equation ax^2 + bx + c = 0.
 * 
 * @param a quadratic coefficient, requires a != 0
 * @param b linear coefficient
 * @param c constant term
 * @return a list of the real roots of the equation
 */
public static List<Double> quadraticRoots(int a, int b, int c) { ... }

Your hypothesis should lead to a prediction, such as “I think variable x has a bad value at this point” or even “I think this code is never executed.” Your experiment should be chosen to test the prediction. The best experiment is a probe, a gentle observation of the system that disturbs it as little as possible.

One familiar probe is a print statement. Print debugging has the advantage that it works for virtually every programming language. It has the disadvantage that it makes a change to the program, which you have to remember to revert. It’s too easy to end up with a program littered with print statements after a long debugging session. It’s also wise to be a little thoughtful when you write a debugging print statement. Rather than printing the same hi! in fifteen different places to trace how the program is executing, and losing track of which is which, print something clear and descriptive like start of calculateTotalBonus.

Another kind of probe is an assertion that tests variable values or other internal state. In the example above where x is never allowed to be negative, we could insert assert(x >= 0); as a probe at any point. Assertions have the advantage that they don’t require you to inspect output by hand, and can even be left in the code after debugging if the test is universally true (some debugging assertions are only true for the specific test case you’re debugging, and those would need to be removed). Assertions have the disadvantage that they’re not turned on by default, so you can be fooled by an assertion that seems to be passing but is actually not even running. We talked about this problem in a previous reading.

A third kind of probe is setting a breakpoint with a debugger, which stops the running program at that point, and allows you to single-step through the program and inspect values of variables. A debugger is a powerful tool that rewards the effort put into learning how to use it.

/**
 * Convert from one currency to another.
 * @param fromCurrency currency that customer has (e.g. DOLLAR)
 * @param fromValue value of fromCurrency that customer has (e.g. $145.23)
 * @param toCurrency currency that customer wants (e.g. EURO).  
 *                   Must be different from fromCurrency.
 * @return value of toCurrency that customer will get,
 *         after applying the conversion rate and bank fee
 */
public static double convertCurrency(Currency fromCurrency, double fromValue, Currency toCurrency) {
  assert(fromCurrency != null && toCurrency != null);
  assert(! fromCurrency.equals(toCurrency));

  double rate = getConversionRate(fromCurrency, toCurrency);
  System.out.println("conversion rate is " + rate);

  double fee = getFee();
  assert(fee == 0.01); // right now the bank charges 1%

  return fromValue * rate * (1-fee);
}

import java.util.ArrayList;
import java.util.List;

public class Hailstone {
    public static List<Integer> hailstoneSequence(int n) {
        List<Integer> list = new ArrayList<Integer>();
        while (n != 1) {
            list.add(n);
            if (n % 2 == 0) {
                n = n / 2;
            } else {
                n = 3 * n + 1;
            }
        }
        list.add(n);
        return list;
    }

    public static void main(String[] args) {
        System.out.println("hailstoneSequence(5)=" + hailstoneSequence(5));
    }

}

Swap Components

Don’t Fix Yet

/**
 * @return true if and only if word1 is an anagram of word2
 *         (i.e. a permutation of its characters)
 */
boolean isAnagram(String word1, String word2) {
  try {
    if (word1.equals("")) return word2.equals("");

    for (int i = 0; i < word1.length; ++i) {
      if (! word2.contains(word1.charAt(i))) return false;
    }

    if (! isAnagram(word2, word1)) return false;
    else if (word2.length() == word1.length()) return true;
    else return false;

  } catch (StackOverflowError e) { return true; }
}

After the experiment, reflect on the results and modify your hypothesis. If what you observed disagreed with what the hypothesis predicted, then reject that hypothesis and make a new one. If the observation agreed with the prediction, then refine the hypothesis to narrow down the location and cause of the bug. Then repeat the process with this fresh hypothesis.

Make sure your source code and object code are up to date. If none of your observations seem to make sense, one possible hypothesis is that the code you’re running (the object code) doesn’t match the code you’re reading (the source). To test this, pull the latest version from the repository, and delete all your binary files and recompile everything (in Eclipse, this is done by Project → Clean).

Once you’ve found the bug and understand its cause, the third step is to devise a fix for it. Avoid the temptation to slap a patch on it and move on. Ask yourself whether the bug was a coding error, like a misspelled variable or interchanged method parameters, or a design error, like an underspecified or insufficient interface. Design errors may suggest that you step back and revisit your design, or at the very least consider all the other clients of the failing interface to see if they suffer from the bug too.

Think also whether the bug has any relatives. If I just found a divide-by-zero error here, did I do that anywhere else in the code? Try to make the code safe from future bugs like this. Also consider what effects your fix will have. Will it break any other code?

Finally, after you have applied your fix, add the bug’s test case to your regression test suite, and run all the tests to assure yourself that (a) the bug is fixed, and (b) no new bugs have been introduced.

Other tips

Summary