Back in school during a beginner’s course for computer programming, when introducing the concept of loops the professor preempted students who might be planning to ask why we needed loops in our programs by declaring the axiom “Because we must have loops.” I guess he didn’t want to give too many examples or explanations to the students at that point, further immersing them in the fog that apparently hits newbies. Similarly, when I mentioned to my parents who knew nothing about computer programming about bugs I found in my own programs, they were flabbergasted as to how I, a so-called professional, could make such mistakes. Instead of trying to explain how complicated the relationships between different parts of the code are, how it is impossible to keep them all in your head at once, and how you can’t easily predict all the paths through your program – I should have just declared “Because you must have bugs.”
Coincidently, many bugs occur in loops. And since you must have loops and you must have bugs, developers are doomed to a life of searching for bugs inside loops. But does it really have to be that way?
Think of every program written by someone else that you inherited for maintenance or enhancements. It’s just a bunch of poorly written spaghetti code, right? (And if you’re honest, so is the code you wrote last year). Imagine next time you get on an airplane, that your life depends on somebody else’s code. (It does). Frightening, isn’t it? Or worse, imagine your life depends on your own code. Maybe every time you write a program, you should code it as if it was being installed in an airplane and you are the passenger (even if your boss wants it done quicker).
There is a story about architects in ancient Rome who were forced to stand under their own arches while the scaffolding was removed. They might be killed if the arch fell down the first time it had to stand on it’s own. If I was in their place, I would say “Can’t we just leave the scaffolding in permanently?” Well, that’s exactly what I do in my programs. I put scaffolding in to detect bugs, and I leave it in permanently. I have developed a simple set of techniques, and whenever I get lazy and don’t put them all in, every single time; I usually end up regretting it. There’s nothing worse than spending half a day solving a bug and then realize that the bug could have been prevented during compilation, or at least detected when the program was run, rather than by trying to figure out post-mortem why the program crashed or why the results are wrong. Or worse, thinking that the results are correct when they are not.
So what’s happening in loops that are causing bugs? Many times you are accessing elements of the arrays, and an array subscript goes out of range. It’s really that simple. I would guess that applies to 90% of the bugs dealing with loops. This would include many “buffer overrun” and “off by one” type of errors. An advanced programmer might tell you to not access arrays with subscripts, just use STL containers and built-in algorithms. I’m not going to tell you to change your coding style. If you use arrays and/or vectors, and use array subscripts, that’s fine with me.
Arrays can be fixed in size at compile time, or dynamic in length. The loop may access all the elements of an array, a fixed subset, or a varying subset of elements.
Declaring Fixed Sized Arrays
First, let’s start with how the size of fixed-size arrays are declared. Many programmers might declare the size of an array as:
const int NUM_MOONS_NEPTUNE = 13;
bool isMoonVisited[NUM_MOONS_NEPTUNE];
Another alternative is to define an enumerated list:
Enum
{
Naiad,
Thalassa,
…
Psamathe,
Neso,
NUM_MOONS_NEPTUNE
};
bool isMoonVisited[NUM_MOONS_NEPTUNE];
Then the programmer, thinking that this is good coding practice, loops through the array by writing:
for (int I = 0; I < NUM_MOONS_NEPTUNE; i++)
{
isMoonVisited[i] = false;
}
They even think they’ve prevented new bugs, because when the new moon of Neptune is discovered, all they have to do is change
const int NUM_MOONS_NEPTUNE = 13;
to
const int NUM_MOONS_NEPTUNE = 14;
or add S_2004_N1 to the enumerated list and they’re done.
Well, what happens if somebody changes
bool isMoonVisited[NUM_MOONS_NEPTUNE];
to
bool isMoonVisited[NUM_MOONS_SATURN];
But they don’t change
for (int i = 0; i < NUM_MOONS_NEPTUNE; i++)
{
isMoonVisited[i] = false;
}
They’ve just introduced a bug. The subscript to isMoonVisited will be outside the range of its declared size because there are more moons of Saturn than Neptune.
So here’s my first rule to prevent bugs. Other than declaring the size of a single array, at no other place anywhere in your program should you ever use the NUM_MOONS_NEPTUNE constant or enumerated value again. You might just as well code
bool isMoonVisited[13];
This appears to violate the magic number rule, but it doesn’t any more than
const int NUM_MOONS_NEPTUNE = 13;
violates the magic number rule. And not creating a variable NUM_MOONS_NEPTUNE is better, because it forces you to not have a variable that you can misuse.
Avoid loop bugs using fixed sized arrays
As you will see, my loop bug avoidance technique does not depend on whether or not you define NUM_MOONS_NEPTUNE; it will work either way. But you should never use the value other than for the declaration of the arrays.
Of course in the above example, it might be better to include the information that we are dealing with Neptune moons by naming the array isNeptuneMoonVisited instead of isMoonVisited, but that’s another issue entirely.
Assuming we don’t define NUM_MOONS_NEPTUNE, how do we know the size of the array in order to loop through it? We create a global macro (which I usually put in an include file called size.h) to get the size of an array:
#define SIZE(a) (sizeof(a) / sizeof(a[0]))
I’ve seen this defined as ARRAY_SIZE() which is less likely to be used incorrectly if you don’t mind the additional clutter in your code listing.
This macro handily returns the size of an array that was defined using an initialization list without a size indicator, for example:
bool isMoonVisited[] = {false, false, false, false, false, false, false, false, false, false, false, false, false};
Looping through all elements of an array.
We get the number of elements of isMoonVisited by invoking
SIZE(isMoonVisited)
This is evaluated at compile time, so there is no hit on your program’s efficiency. Now the loop is:
for (int i = 0; i < SIZE(isMoonVisited); i++)
{
isMoonVisited[i] = false;
}
We really don’t care what size it is, as the loop will work perfectly no matter what. Nothing will have to change if the size of the array changes.
So here’s where the scaffolding comes in. Suppose that there are a variety of arrays being accessed in the loop. For example:
for (int i = 0; i < SIZE(isMoonVisited); i++)
{
if (!isMoonVisited[i])
{
rocket->flyTo(moons[i]);
isMoonVisited[i] = true;
}
}
If the size of moons isn’t at least as big as the size of isMoonVisited, we have a buffer overrun. If the size of moons is bigger than the size of isMoonVisited, we probably have a bug, because we’re not calling flyToMoons for all of its elements. I would guess that even an automatic bug checker wouldn’t catch that one.
We can find both of these bugs at compile time by using a static assert call before we enter the loop. There are many implementations of static asserts, and you can find examples on the Internet. Some are simple macros (that return non-intuitive error messages), the Boost library has an implementation, and C++11 has a built-in version. I’m not going to provide a tutorial for static asserts, let it suffice that you have found one that you are happy with. Let’s call it static_assert().
static_assert (SIZE(moons) == SIZE(isMoonVisited));
Remembering the Roman architects, this is what I like to think of as scaffolding. Some programmers turn off asserts in delivered code (especially run-time asserts), but I always leave them in place, all the time, for all arrays that we are looping through, even if it seems obvious that we already made sure that we defined the arrays to be the same size. This assumption may not be true once the maintainer gets ahold of your code. (And that maintainer may be you, a year from now, after you’ve forgotten most of what you did.)
If you know for sure that you don’t care if flyTo is called for all elements of moons, use the lesser restrictive
static_assert (SIZE(moons) <= SIZE(isMoonVisited));
to at least prevent a buffer overrun.
Clearly isMoonVisited and moons are closely related. Let’s look at how we define the sizes of arrays that are related to each other.
Depending on how we defined our arrays we can do this several ways. One way is to use the same const int or enumerated value to define the size of each array to be the same.
const int NUM_MOONS_NEPTUNE = 13;
bool isMoonVisited[NUM_MOONS_NEPTUNE];
MoonClass moons[NUM_MOONS_NEPTUNE];
Each array may be defined in a different file, or far apart from each other in the same file, not one right under the other, and a maintainer could easily change the size of one without changing the other. If that happened, you’d have a bug, but if you left the scaffolding in (the assert at the beginning of each loop), at least you’d find the bug as soon as you compiled the program.
However, the above example violates my rule of reusing the size variable (NUM_MOONS_NEPTUNE) somewhere else in the program. Instead define related arrays in terms of the sizes of each other.
const int NUM_MOONS_NEPTUNE = 13;
bool isMoonVisited[NUM_MOONS_NEPTUNE];
MoonClass moons[SIZE(isMoonVisited)];
Or
bool isMoonVisited[13];
MoonClass moons[SIZE(isMoonVisited)];
Using this method, a maintainer would have to really go out of his way to change the size of one array without changing the size of the other (introducing a new bug), whereas if he repeats NUM_MOON_NEPTUNE to define the size of each array, he’d have to go out of his way to change the size of both arrays simultaneously (avoiding a new bug).
Which do you think is better? Coding your program so that a maintainer has to go out of his way to create new bugs, or so that new bugs appear whenever he is not careful. I think the former, no doubt.
Of course, if you could put both the arrays in a struct or class, you could have a single array of class objects, and you avoid the above potential problems. You don’t need the scaffolding either. However, this isn’t always possible.
struct MoonInfo
{
MoonClass moon;
Bool isMoonVisited;
};
const int NUM_MOONS_NEPTUNE = 13;
MoonInfo moonInfo[NUM_MOONS_NEPTUNE];
for (int i = 0; i < SIZE(moonInfo); i++)
{
if (!moonInfo[i].isMoonVisited)
{
rocket->flyTo(moonInfo[i].moons);
moonInfo[i].isMoonVisited = true;
}
}
In Part 2, I will discuss handling variable index ranges, variable sized arrays, and other issues.
Robert Felten’s SSD Manager software was demoed in the NVM Express booth during the Flash Memory Summit held at the Santa Clara Convention Center Aug 13-15, 2013. The GUI display was also shown in an article appearing in EETimes.
