Bugs and debugging

Comments and questions to John Rowe.

In this course, and in the exercises, we have emphasised the importance of writing a little code at a time and checking it thoroughly before moving on to the next piece.

Just because we hope our code is bug-free doesn't mean that it really is!

In practice, however, it's very easy to degenerate to doing the minimum amount necessary for us to be able to tell our self that it's working properly, rather than doing everything we can to find any bugs. This is usually due to a combination of lack of time, laziness or wishful thinking.

The programs that take a lot of time to get working are the ones where we have let a bug slip through and have to find it later, not the ones where we have spent time checking for bugs as we go.

Shake the scorpions from your shoes (or worse!)

Image: wikipedia

In countries where scorpions and poisonous spiders are common, we are advised to carefully shake out shoes and other clothes in the morning before putting them on, particularly when camping or living out in the country.

Warm up discussion

1. If you were living in fairly rough accommodation in an area with large numbers of poisonous spiders and scorpions, how careful would you be shaking out your shoes, underwear etc. before putting them on them on in the morning? Why?

2. If somebody brought you such an item to put on but were rather vague about whether they had checked for scorpions ("Yeah, well, I think so..."), how would you feel about putting that item on?

Remember

It may be unpleasant to shake out a piece of clothing we were about to put on next to our skin and to see a scorpion fall out, but it's nothing compared to what would have happened had we not bothered!

Find the bugs before they bite you where it hurts

In the case of physical poisonous bugs, the psychology described above is fairly clear. But for logical bugs in our code the psychology tends to be reversed: we can tend not to carefully check for bugs in the hope that if we don't look for them somehow they won't be there.

Nobody would make that mistake when checking for a poisonous spider in their underwear so don't make it when checking for bugs in your code!

Debug thoroughly as you go

It's not the scorpion we shake out of our underwear that we need to worry about, but the one we don't shake out of our underwear. It's not the bug we find as we go along that takes the time,but the one we don'tfind as we go along.

Check every class of possibility

It's seldom possible to check every possible combination of input.

Let's imagine we are programming a generalised, NxN naughts and crosses program, for example a 5x5 game rather than the usual 3x3. This has around 25 factorial possible games and we can't check them all.

Even worse, the quadratic equation a*x*x + b*x + c = 0 has an infinite number of possible coefficients.

It's important to consider every possible class of cases and to test at least one of every class.

For a quadratic we have the following possibilities:

• Two real roots.
• Two complex roots.
• One repeated root.
• Any or all of a, b and c equal to zero. (a equals zero is particularly important of course.)

We should make sure we test them all.

Check that tests fail as well as pass

If we are checking, say, that a number is divisible by four we must first check that the conditions triggers when the condition is divisible by four and second that it does not trigger when the number is not divisible by four.

Put in checks

If we are dealing with a triangle, check that the angles add up to two pi, to within a margin of error. (But see below.)

Mistakes to avoid

Sadly, these are all things I have seen (and probably done!).

1. Printing out the result without checking it's correct

If we write a factorial function and print out 11 factorial as a test, we will need some evidence that it's correct - nobody can work out the value of 11 factorial in their head.

2. Always using the same test data

It's easy to get into the habit of typing a certain set of numbers into the terminal until that particular input data gets handled properly and then moving on. It is even easier when the test data is in a file.

3. Checking only special cases

For example, when reading in a floating-point number to just type in integers. Or when solving the quadratic equation a*x*x + b*x + c = 0 to make b or c equal to zero. There are a number of errors that won't get caught in this case, for example forgetting the initial minus sign in "-b + sqrt(b*b - 4.0*a*c)".

4. Failing to check special cases

We should make sure that our program can handle a equals zero for example.

Conclusion

Using a piece of code which we've only vaguely debugged is like putting on underwear in the Australian outback which we've only vaguely checked for poisonous spiders or scorpions: it's going to come back and bite us somewhere very painful indeed!

Finding bugs

Despite our best intentions, bugs do occur. When they do there are two main priorities, which often operate in parallel:

1. Narrow down where the bug is

Successively partition the problem

If we were playing a game where we choose a (whole) number between one and a hundred and the other person has to guess it, a small child might ask "Is it one? Is it two?...". A more numerate person would start "Is it less than fifty?", thus going from an "order N" problem to an "order log(N)" problem.

Similarly, if an incorrect value or algorithm has two or three components, try to work out which of these is wrong, rather than starting at the first sub-component of the first component, then the second sub-component and so so.

Also be aware that it can be the code that puts the components together that's in error, or even the debugging code itself. And the worst bugs can be where we make one assumption when writing a function and another when using it - get rid of those ambiguities and where that's not possible say which one you've chosen in the comment at the top of the function.

2. Get more information.

The 80/20 rule is more properly known as the Pareto principle.

Bearing in mind the 80/20 rule, there are two debugging tools that will form the majority of what you do. The first is for programs that run but produce the wrong answer. It's very simple:

Print stuff out

Example: looking for rows in an NxN naughts and crosses

The following example shows how we might use a printf() statement to debug a problem looking for rows in the NxN naughts and crosses program mentioned above.

  int count = 0;
  for (x = 0; x < N; ++x)
    if (grid[x][0] != ' ') {
       for (y = 0; y < N; ++y) {
         if ( grid[x][y] == grid[x][0] )
           ++count;
         printf("DIAG: x=%d y=%d count=%d\n", x, y, count);
       }
       if (count == N) {
         printf("Player %c has won\n", grid[x][0]);
         return grid[x][0];
       }
    } 

The key is to work out which variables tell us what is going on and print out their names and values (not just anonymous numbers). In our case that's x, y and count.

The above information should be enough to tell us that we have forgotten to reset count when we are starting a new row.

There are various more subtle ways we could have approached this problem: we could have passed the most recent move as an argument and checked only that row, and we could have broken out of our for() loop at the first non-matching square and checked that y was equal to N.

Dealing with infinity and Nan

A macro is a more advanced use of #define which is allowed to have arguments.

One useful tip, which we also use below, is that the #include file math.h also defines the macro isfinite() that returns zero if its parameter is infinity or Not a Number or one otherwise.

For example, suppose we have an array and for some reason we think that some of its values are Nan or infinity. We might write the following loop:

  for(i = 0; i < N; ++i)
    if (isfinite(x[i]) == 0)
      printf("x[%d] is %f\n", i, x[i]);

This will print out i followed by inf, Nan, etc. for any bad array elements. If we were to use the debugger, below, we would have a choice of a few other things to do.

3. Check your assumptions

The executive summary of this section is that we should not assume that we know what the problem is. After all, if we knew where the problem was it wouldn't exist!

Some things we "know" to be true aren't

It may not always be the last thing we changed

Most of the time the bug will be in the bit of code we are working on. But if we can't find it there we need to look at the code we had previously assumed was bug-free. This is an unpleasant occurance (there's lots of code to look through!), but there again we've been saying this for the whole lecture so it should not be a susrprise by now.

Check the diagnostics

We mentioned this above, but sometimes the code is actually correct, it's our diagnostic that's wrong.

Using the debugger

When programs crash

The printf() technique is not very helpful when a program crashes with a segmentation fault or other memory error. All we get is a message saying it has crashed, with no idea where or why.

I have seen bugs so bad that the debugging information itself has been destroyed but these cases are rare.

Fortunately the debugger can tell us where the program was when it crashed and what values the variables had at the time.

For the debugger to be useful we must have enabled the appropriate options when we compiled the program. These are enabled by default on the Macs.

What the debugger does for us

The purpose of the debugger is to provide us with a window like the one above. The above example is for a program that has crashed due to trying to modify a read-only string. It has four main windows:

Top left: function list

This shows us which function we are in (uppercase(), the function that called it, and so on up to main(). In our case there are just two functions.

The function names are click-able: if we click on the word main the two windows described below will show us the state of main() not uppercase(). The ability to go up and down the function list, examining the variables in each function can be extremely useful.

Top right: variables and their values

The main items of interest to us are the arguments, local variables and global variables.

When viewing the values of arrays passed as arguments it can be better to go up to the function where they were first declared.

Bottom full-width: source code

This shows the statement where the program crashed. If we were to click on main in the top-left window it would show us where inside main() we had called uppercase().

Very top: "video" controls

These are less relevant in this case as the program has crashed so the only option open to us is to restart the program from the beginning. If we had paused the program (see below) we would also have the option to continue the program.

At any one time the debugger can be in one of two main states: when finished or paused, the program is not running and the three main debugger windows are active. When the program is running (after having pressed the Restart or Continue buttons) the three debugger windows are inactive. This includes when the program is waiting for input from scanf().

Invoking the debugger

Starting the program under the debugger

If we have compiled with the debugging options, many systems will also give us the option of saving the entire memory of a program so we can debug it later.

1. Open the "Build" menu and choose "Build and Debug". The "Duild" icon changes to one with a yellow can of insecticide.
2. Make a small change to the program to force it to rebuild it.
3. Press the Build and debug icon: a smaller yellow can of insecticide should appear on below and to the left of the main one. Click on it to open the window shown above.

If XCode gets confused when running the debugger, just quit XCode and restart.

Advanced usage

Using the debugger to look at a program's variables, and where it was, when it crashes will be by far the most use to you. The following should be regarded as optional material.

  for(i = 0; i < N; ++i)
    assert(isfinite(x[i]));

/* Turn off assert */
#define NDEBUG
#include <assert.h