Reading 13: Debugging

The mostCommonWord() data flow we just looked at is an example of slicing, which means finding the parts of a program that contributed to computing a particular value. When you have a failure — a bad value at a particular point in the program — the slice for that value consists of the lines of the program that helped compute that bad value. The bug that caused the bad value lies somewhere in that slice, so that’s your search space.

Automated tools for program slicing do exist, though they are not very practical yet. But programmers also do slicing naturally, in their heads, when looking at code to generate a hypothesis about where a bug might or might not be. It’s a useful skill for reasoning about programs, so let’s understand it better.

Here’s an example. Suppose x is a local number variable which is not supposed to exceed 100. At some point a debugging print statement reports that it has gone bad:

let x:number = 0; // must be <= 100
...
console.log("x=" + x); // prints a value much greater than 100

What is the slice for this bad value? What lines of code helped compute the large value that x has when it reaches that print statement? Let’s dig into the ... in the code above to find what code might be responsible.

Lines that directly change the value of x are part of the slice:

let x:number = 0; // must be <= 100
...
    x += bonus;
...
console.log("x=" + x); // prints a value much greater than 100

The value of bonus at that point also contributes to the value of x, so that means that its slice does too. So we have to look at the lines that helped compute bonus at that point:

let x:number = 0; // must be <= 100
const bonus:number = getBonus();
...
    x += bonus;
...
console.log("x=" + x); // prints a value much greater than 100

So the function getBonus() is now included in the slice, because it was responsible for computing bonus. (Technically we only need to include the slice of its return value, but we can simplify and just say that getBonus() itself is suspect.)

The slice also includes control statements that affected the execution of statements already in the slice:

let x:number = 0;
const bonus:number = getBonus();
...
  if (isWorthABonus(s)) {
    x += bonus;
  }
...
console.log("x=" + x); // prints a value much greater than 100

The if statement around x += bonus is part of the slice because it controls whether or not x was actually changed at that point. This also pulls in the function isWorthABonus(), and the value of s and its slice:

let x:number = 0;
const bonus:number = getBonus();
...
for (const s of salesList) {
  ...
  if (isWorthABonus(s)) {
    x += bonus;
  }
  ...
}
...
console.log("x=" + x); // prints a value much greater than 100

The enclosing for statement is included in the slice for two reasons: because it’s part of the slice of s, so it affects the if statement which is already in our slice, and because it affects the number of times that statements in our slice are executed (the if statement and x += bonus).

And now, because the for uses the variable salesList, we have to include its slice as well. It happens to be a function parameter:

function calculateTotalBonus(salesList:Array<Sale>):number {
  ...
  let x:number = 0;
  const bonus:number = getBonus();
  ...
  for (const s of salesList) {
    ...
    if (isWorthABonus(s)) {
      x += bonus;
    }
    ...
  }
  ...
  console.log("x=" + x); // prints a value much greater than 100
  ...
}

We could dig further and see where salesList came from in the rest of the program, but let’s stop there for now. We’ve found the lines of code in this method that might be responsible for the bad value of x we discovered. Studying these lines can generate some useful hypotheses:

• from the x+=bonus statement: maybe bonus is very large, so x+=bonus immediately goes out of range. This hypothesis would further imply that getBonus() returned a large value for bonus.
• from the if statement: maybe isWorthABonus() returns true for too many sales, so the sum accumulated in x grows beyond 100.
• from the for loop: maybe the entire loop is executing over too many sales, again making x too large from all the bonuses.
• from the method signature: maybe a bad value is being passed in for salesList, with far too many sales on it.

The upshot is that careful slicing – which you can do just by reading the code – can help you systematically identify places where the bug could be, and also where it could not be. We can rule out the ... code in this example, because it doesn’t contribute to the bad value of x.

It’s worth noting that our design choices can help or hinder the efficiency of reasoning by slicing. One such design choice is immutability. When we were slicing for the value of bonus, and saw that its declaration was const bonus:number = getBonus(), we immediately knew that we didn’t have to look any further – no other lines can be in the slice for bonus, because it’s an unreassignable reference to an immutable value. Immutability saved us a lot of time in reasoning and searching. When we saw const s of salesList though, we didn’t have quite the same confidence. Certainly s could never be reassigned within the body of the loop, but if the element type of salesList (Sale) is a mutable type, we would have to check the subsequent ... code to make sure no mutators were called on s or other aliases of the Sale object.

Another design choice that helps slicing is scope minimization. All the variables in this example were local variables, with minimal scope, so we only had to look close by for lines of code that might affect them. With instance variables, the slicing search might have to expand to include the entire class. For a global variable (gasp), the search expands to include the entire program.

let total:number = 0.0;
let tax:number = 0.0;
let taxRate:number = 0.06;
for (const item of items) {
  let price:number = item.getPrice();
  total += price;
  if (isOutOfStateCustomer) {
    taxRate /= 2;
  }
  if (item.isTaxable()) {
    tax += price * taxRate;
  }
}
total += tax;
return total;

function incrementAll(a:Array<number>):number {
  let b:Array<number> = a;
  for (let i = 0; i < a.length; ++i) {
    ++b[i];
  }
  return b.length;
}

The process of isolating a small test case may also give you data that helps form a hypothesis, if it uncovers two closely-related test cases that bracket the bug, in the sense that one succeeds and one fails. For example, maybe mostCommonWords("c c, b") is broken, but mostCommonWords("c c b") is fine. Now you can examine the difference between the execution of these two test cases to help form your hypothesis. Which code is executed for the passing test case, but skipped for the failing test case, and vice versa? One hypothesis is that the bug lies in those lines of code, the delta between the passing run and the failing run.

This is a specific example of a general idea in bug finding called delta debugging, in which you compare successful runs with failing runs to try to localize the bug. Another kind of delta debugging is useful when a regression test starts failing. Using your version control system, you retrieve the most recent version that still passed the test, and then systematically explore the code-changes between the older working version and the newer failing version, until you find the change that introduced the bug. Delta debugging tools can automate this kind of search process, though like slicing tools they are not widely used yet.

When making your hypothesis, you may want to keep in mind that different parts of the system have different likelihoods of failure. For example, old, well-tested code is probably more trustworthy than recently-added code. TypeScript library code is probably more trustworthy than yours. The TypeScript compiler and runtime, operating system platform, and hardware are increasingly more trustworthy, because they are more tried and tested. You should trust these lower levels until you’ve found good reason not to.

/**
 * Solves quadratic equation ax^2 + bx + c = 0.
 * 
 * @param a quadratic coefficient, requires a != 0
 * @param b linear coefficient
 * @param c constant term
 * @returns a list of the real roots of the equation
 */
function quadraticRoots(a:number, b:number, c:number):Array<number> { ... }

If you hypothesize that the bug is in a module, and you happen to have a different implementation of it that satisfies the same interface, then one experiment you can do is to try swapping in the alternative. For example:

• If you suspect your binarySearch() implementation, then substitute a simpler linearSearch() instead.
• If you suspect the JavaScript runtime, run with a different web browser or a different version of Node.
• If you suspect the operating system, run your program on a different OS.
• If you suspect the hardware, run on a different machine.

You can waste a lot of time swapping unfailing components, however, so don’t do this unless you have good reason to suspect a component. As we discussed under prioritizing hypotheses, the programming language, operating system, or hardware should be very low on your list of suspects.

It’s not unusual, while you’re trying to debug one problem, to discover other problems. Maybe you notice that some other module is returning wrong answers. Maybe while you’re reading your own code (effectively a self code review), you notice obvious mistakes that need to be fixed.

Keep a bug list. This helps you deal with fresh problems that arise during debugging. Write them down on your bug list so that you can come back to them later. A bug list can be as simple as a paper notebook or text file. For software development in a group, an online bug tracker like GitHub’s Issues tab is the best approach.

Don’t get distracted from the bug you’re working on. Reflect on whether the new problem is informative data for the bug you’re working on — does it lead to new hypotheses? But don’t immediately start a recursive debugging process for the new bug, because you may have a hard time popping your mental stack to return to the original bug. And don’t edit your code arbitrarily while you are debugging, because you don’t know whether those changes might affect your debugging experiments. Keep your code changes focused on careful, controlled probes of one bug at a time.

If the new problem is interfering with your ability to debug — for example, by crashing the program intermittently, so that you can’t reliably run your experiments — then you may need to reprioritize your bug fixing. Put the current bug down (unwinding or commenting out your experimental probes, and making sure the bug is on your bug list to fix later) and tackle the new bug instead.

It’s tempting to try to do an experiment that seems to fix the hypothesized bug, instead of a mere probe. This is almost always the wrong thing to do. First, it leads to a kind of ad hoc guess-and-test programming, which produces awful, complex, hard-to-understand code. Second, your fix may just mask the true bug without actually removing it — treating the symptom rather than the disease.

For example, if you’re getting a RangeError, don’t just add code that catches the exception and ignores it. Make sure you’ve understood why that exception was being thrown, and fix the real problem that was causing it.

/**
 * @returns true if and only if word1 is an anagram of word2
 *         (i.e. a permutation of its characters)
 */
function isAnagram(word1:string, word2:string):boolean {
  if (word1 === "" || word2 === "") {
    return word1 === "" && word2 === "";
  }

  try {
    word1 = sortCharacters(word1);
    word2 = sortCharacters(word2);
    return word1 === word2;
  } catch (e) { return false; }
}

This is one of Agans’ nine rules of debugging: Keep an Audit Trail.

If a bug takes more than a few minutes to find, or more than a couple iterations of the study-hypothesis-experiment loop, then you need to start writing things down, because the short-term memory in your brain will very quickly lose track of what’s working and what isn’t.

Keep a log in a text file of what you did, in what order, and what happened as a result. Include:

• the hypothesis you are exploring now
• the experiment you are trying now to test that hypothesis
• what you observe as a result of the experiment:
  • whether the test passed or failed this time
  • the program output, especially your own debugging messages
  • any stack traces

Systematic debugging techniques can rapidly exceed the ability of your brain to keep track of them, so start writing things down sooner rather than later. Minimizing a test case and delta debugging often require several iterations to zero in on an answer. If you don’t write down which test case you’re trying, and whether it passes or fails, then it will be hard to keep track of what you’re doing.

If you have been iterating on a bug and nothing makes sense, consider another of Agans’ rules: Check the Plug. What this means is you should question your assumptions. For example, if you turn on the power switch of a machine, and the machine doesn’t start, maybe you shouldn’t be debugging the switch or the machine – but asking whether the machine is even plugged in? Or whether the electrical outlet itself has power?

An example of “checking the plug” in programming is to 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, delete all the JavaScript output files (the files ending .js), and recompile all your TypeScript code.

This is another one of Agans’ nine rules. In a complex system, sometimes a bug will suddenly disappear. Maybe it was something you did, but maybe not. If the system seems to be working now, and you don’t know how the bug got fixed… then most likely it isn’t fixed. The bug is just hiding again, masked by some change in environment, but ready to rear its ugly head again someday. We will see some examples of nasty bugs like this when we talk about concurrency, later in the course.

Systematic debugging helps build confidence that a bug is really fixed, and not just temporarily hidden. This is why you first reproduce the bug, so that you have seen the system in a failing state. Then you understand the cause of the bug without fixing it yet. Then finally apply a change to fix the bug using your knowledge of the cause. To gain confidence that you have really fixed it, you want to see that your change caused the system to transition from failing to working, and understand why.

Get a fresh view. This is another of Agans’ nine rules of debugging. It often helps to explain your problem to someone else, even if the person you’re talking to has no idea what you’re talking about. This is sometimes called rubber-duck debugging or teddy-bear debugging. One computer lab had a big teddy bear sitting next to their help desk, with the rule that you had to “tell it to the bear” before you tried the human. The bear dealt with a surprising number of problems all by itself. Talking aloud about why you expect your code to work, and what it’s doing instead, can be good at helping you realize the problem yourself.

When the teddy bear doesn’t help, 6.031 staff and fellow students usually know what you’re talking about, so they’re even better to get help from. Outside this class, you may seek a fresh view from other team members, coworkers, or StackOverflow. The effort you put into minimizing your bug will help you make a minimal, reproducible example that you can use to ask a question online.

Sleep on it. If you’re too tired, you won’t be an effective debugger. Trade latency for efficiency.

In this reading, we looked at how to debug systematically:

• reproduce the bug as a test case, and put it in your regression suite
• find the bug using the scientific method:
  • generate hypotheses using slicing, binary search, and delta debugging
  • use minimially-invasive probes, like print statements, assertions, or a debugger, to observe program behavior and test the prediction of your hypotheses
• fix the bug thoughtfully

Thinking about our three main measures of code quality, systematic debugging is essentially about safety from bugs: we’re trying to get rid of a bug, while using regression testing to keep it from coming back.