Rodney Bates has been programming for a lot of years, doing mostly compiler work in various languages. He also is interested in language-based environments. When not programming he fixes aging (mechanical) machines and sings renaissance music. He can be contacted at 7757 S. Pattie; Wichita, KS 67233-1245, (316) 554-0403; e-mail [email protected].
Assertions are truth-valued expressions that you put in your program at carefully-selected spots. They verify at runtime conditions you believe must always be true at that spot. The code that follows relies on the truth of these conditions for its correct functioning. If one of the assertions ever turns out to be false, the program prints a message and halts. Probably the greatest practical advantage to runtime assertions is that they catch bugs early, before the evidence is destroyed.
Most C dialects have a macro named assert in a header file named assert.h. Frequently, bugs cause assertions to fail, providing the advantage of early detection. So, the assert macro, when properly used, can be a powerful debugging tool, particularly for large, complex programs. In contrast, execution of a program written without assertions can obliterate the evidence of a bug or perhaps even obscure the fact that a bug exists at all.
I used the assert macro as a debugging tool for the first time six years ago on a compiler code-generator project. During this project, I kept a careful log of each run, what changes it included, and the results of these changes, including a short description of each bug.
The project consisted of a 7000-line program. It took over two months to code, a week to get a clean compile, and two weeks to debug. After debugging, I made the program available to a handful of fellow employees.
During the two-week debugging period, I detected and repaired 59 bugs. My log doesn't specifically show this, but I estimate from the descriptions that about half of these bugs were detected by assertions. During the subsequent life of this version of the program (about one year), 12 additional bugs were discovered, about half by me and the rest by other users. Since then, I have used assertions extensively on every programming project, with similarly good results.
A Bit of History
Correctness-Proof Theory
The original idea of assertions in programs emerged in the early 70's as part of the theory of program-correctness proofs. There was a lot of frustration then about the fact that the debugging and maintenance of programs were becoming unmanageable as the problems people were attempting to solve grew more complex.
At that time, the only techniques anybody could describe for debugging were tracing and testing. (These still seem to predominate today.) Both suffer from the fact that they only answer questions about what a program will do when presented with one particular set of inputs, i.e. a single computation. But to be of any use at all, a program must correctly carry out any of a huge number of different computations.
So the goal of the time was to discover ways of doing what I call algorithmic thinking. Algorithmic thinking is anything you can say about the behavior of a program that is true for every computation it can carry out. Computational thinking is, in contrast, anything that applies to only one case. Algorithmic thinking is to computational thinking as algebra is to arithmetic. When you start manipulating expressions and equations with Xs and Ys, you must find claims you can make that are true regardless of the values of X and Y.
Testing and tracing are hopelessly computational, and the fact that many different cases are tested and/or traced does not alter this. The correctness-proof researchers were looking for algorithmic techniques for studying programs.
Correctness-proof theory has not turned out to be what some have claimed it would be. The whole process is just too time-consuming to go through for programs much larger than toy examples. On the other hand, tracing for a single set of input values is also intractible for real programs. Yet it is the basis of the way a whole generation of programmers was taught to think. I think assertions have the potential to be the basis of a way of thinking too — a better, algorithmic way.
A Different Kind of Assertion
In 1977, a report was published defining a programming language named Euclid (Lampson, et al, 1977). Among the features of Euclid were several kinds of assert statements. Unlike the classical assertions, which were comments, these had a defined syntax consisting of a reserved word such as assert followed by a boolean expression.
The designers of Euclid had two ideas about how these might be used. First, an automatic theorem prover could be integrated with a compiler to derive some assertions from others. Second, the theorem prover would delete any assertions that it could prove before code generation. Those left-overs would actually be compiled into runtime checks that tested the truth of the expressions.
Actually, there was a third idea. The compiler front-end could generate assertions that were not in the source code at all, instead of the traditional runtime checks. By doing this the theorem prover might succeed in removing some of them, producing code that was faster, but just as safe as if the runtime checks were enabled.
As far as I know, none of this ever got implemented. However, it did introduce the subject of this article, that is, the notion of compiling assertions into runtime checks.
Proofing Technique
An assertion using the proofing technique that resulted from the correctness-proof theory normally involves the values of program variables being manipulated by nearby code. It might, for example, look as simple as I >= 0, where I is a variable in the program. The assertion is supposed to be true at this point, for every possible situation that this program can get into.
The proof technique has two steps. First, figure out assertions that can be inserted (as comments) at various points in a program. This involves a lot of invention and intuition, which develops only with practice. The very last assertion is hopefully a formalized statement of what the program should do in every case. Second, formally derive each assertion from one or more nearby other assertions, using standard rules that apply to each of the kinds of statements in the programming language.
How assert Works
The assert macro takes a single argument in parentheses. This argument is a truth-valued expression that you believe will always be true at this place in your code. It expands into code that checks the expression and, if it turns out FALSE, prints a message on standard output and terminates the program. The message usually looks something like
Assertion failure I <= 0 file: mergetxt.c line: 1073This means that the assertion I <= 0 on line 1073 of source file mergetxt.c has failed. Some versions call exit, while others call abort.
The Two Sides to an Assertion
An assertion has two sides. The code leading to the assertion must ensure that it is always true. I call such code the ensurer code. The code leading from the assertion can rely on the truth of the assertion to make its job easier. I call this relyer code.
There can be several alternative paths, any one of which is an ensurer and several of which are relyers. In fact, this scenario gives assertions their greatest value, since you can easily get most of the ensurer paths right but overlook one or two ensurer paths when coding.
An invariant, a somewhat special type of assertion, uses some portion of code as both a relyer and an ensurer. The simplest example is the body of a loop. It performs some computation that relies on the truth of the assertion at the beginning of the loop body and that ensures it is true again by the end. The loop initialization is a separate path that must also contain ensurer code.
Data structures can also have invariants. Each section of code that manipulates the structure relies on the invariant at its beginning, but ensures by its end that it is true again.
A Simple Example
A simple, complete program does not make a good example, because any assertions are likely to be so obvious that they have little value in debugging. However, many assertions are related to a simple part of a complex program.
In this example, assume there is a complex algorithm that needs a stack. Perhaps it is traversing some complicated, linked data structure and needs to be nonrecursive. A simple array implementation of the stack will suffice.
The relevant code fragments are shown in Listing 1. The type of the elements of the stack is given by the typedef name StackElemTyp, declared elsewhere. The maximum stack depth is also given elsewhere by the #define name StackMax. The four functions might well be inlined or made into macros, but I have shown them as functions to get them together. They will be called at appropriate places by the main traversal code.
Init initializes the stack. Push and Pop do the obvious. These are both probably called many times, from several different places in the code. However, Pop starts out with an assertion that the stack is not already empty. There is a very large variety of potential bugs in the traversal algorithm that could cause the number of pops to exceed the number of pushes. If any of these occurs, eventually it will be detected by an assertion failure when Pop is executed with the stack already empty.
Similarly, the number of pops could be less than the number of pushes. If a call on CheckEmpty is made once at the end of the traversal, this class of bug will be detected by a failure of the assertion in CheckEmpty.
These two assertions together ensure that the numbers of pushes and pops executed are equal. No matter how complicated the traversal gets, these two assertions will always detect any imbalance by the time the traversal ends.
Push also has a comment marking the place where stack overflow should be detected. I did not put an assertion here, because it is not clear, without knowing a lot more about the traversal algorithm, what should be the result of stack overflow.
Possibly there is some line of reasoning the programmer can make such that the traversal can never overflow. Perhaps the data structure to be traversed has some finite maximum size and StackMax has been chosen large enough for this maximum. If this is the case, then the stack overflow check should be an assertion. If it ever fails, it means there is a bug somewhere.
On the other hand, stack overflow could simply mean that the program has been given a problem that exceeds its designed capacity. In this case, the overflow is a user error, not a bug. It should be reported as such, not as an assertion failure. It is important to keep this distinction in mind and easy to forget it, once you get accustomed to putting in lots of consistency checks.
Another Example
Listing 2 gives another example, also distilled from a much more complicated program. In the complete program is a collection that contains numbered items visited in ascending item-number order. The program also includes a separate array Dels, whose elements are of type DelTyp. Each element gives a range of item numbers that the program logically deletes from the collection without physically removing them. The program traverses the collection, but skips over deleted items.
It is invariant of this data structure that the structures in Dels are non-overlapping and in ascending order. You move through the deletions in a single pass, in parallel with the items in the collection. It is invariant of the traversal that DelPtr always points to the next deletion possibly relevant to the next item to be processed.
CheckDeleted is called once for each item found in the collection. It returns a BOOL telling whether the item is deleted. As a side effect, it also increments DelPtr when needed, keeping it in sync with the items in the collection.
If there are no more deletions or the next deletion begins with a later item number, CheckDeleted returns FALSE. Otherwise, it concludes that the current deletion covers ItemNo. This is relyer code. The validity of the conclusion relies on the invariant, and the assertion checks this.
Now, if the deletion range ends exactly with ItemNo, CheckDeleted consumes the deletion by incrementing DelPtr. This is ensurer code. The initialization of DelPtr in the declarations is also ensurer code on a different path.
After all visiting of all node elements has been done, there should also be an assertion that checks that DelPtr == DelMaxPtr. This means that all the deletions have been associated with an item and consumed.
Where to locate Assertions
Deciding were to locate assertions (and what to assert) requires some careful judgement, which you can only master with some experience. Here are some guidelines that may help:
- Always be asking yourself what the code you are writing needs in order to work. Especially look out for things that could cause serious damage if not detected. Array bounds errors and NIL or bad pointer values are good examples.
- Check for the things which are not easily verified by a close look at a localized section of code. Checking array bounds when the subscript or element pointer is completely controlled by a small surrounding for loop is hardly worth the bother. However, when the subscript or pointer value could be affected by statements anywhere in a large and widely scattered region of code, a bounds check is definitely indicated.
- Put assertions at the site of relyer code, not after ensurer code. At the beginning of relyer code you will be thinking about what you need to rely on. Furthermore, there may be several ensurer paths. This way, if you forget one, the assertion will still catch the bug.
- Look for opportunities for simple consistency checking, even in cases where your code doesn't directly rely on the assertion. This kind of assertion cuts down on the work and increases the value of testing, since it catches some kinds of incorrect answers without depending on manual examination. This is especially valuable if your program builds internal data structures or files for later use by itself or a related program.
- Generally, a good place for assertions is the start of a function body. You should be able to assert the basic assumptions regarding input parameter values that your function relies on. It is relatively easy to think through the logic of a single function, from assertions at the beginning.
- Don't confuse assertions with ordinary error checks. Assertion failures indicate bugs in your program and result in a deliberate program crash. Error check failures indicate that the user of your program did something wrong, or at least something your program isn't intended to handle. They should result in tactful and informative messages and usually leave the program running, so the user can try something else.
- If a function of yours is called by code written by someone else, you probably want to think of the calling code as your user. This means that parameter validity checks you write should be error checks rather than assertions.
- Files with application-specific format are a particular vulnerability. Your program or a companion program that produces these files is the ensurer of invariants about their internal structure. However, even if your ensurer code is bug-free, a user can always edit the file, copy in a file that your application didn't produce, etc. Be especially vigilant in checking these files for consistency when reading them.
- If consistency checks on special files fail, there is uncertainty whether this indicates a bug or a user error. You should probably treat this as a user error, just to ensure graceful behavior in case it really is.
The Debugging Process
Testing is inherently computational. You have to make up specific test cases to try. This is hard to do well, and the number of test cases anybody can afford to actually run falls so many orders of magnitude short of being exhaustive that it is amazing testing does any good at all. Assertions improve the testing process greatly, because when you run a single test case, not only do you check for the right output but the assertions do all sorts of internal consistency checking as well. A lot more bugs get flushed out with less testing.
Probably the greatest practical advantage to runtime assertions is that they catch bugs early, before the evidence is destroyed. Suppose you had a bug in a doubly linked list insertion routine that left the list in an inconsistent state. Very often, the program might go through many more insertions and deletions of the same list before actually crashing. By the time you get to look at the data, say with a debugger, things have gotten so mixed up that it is virtually impossible to reconstruct what happened or where things originally went wrong. This kind of bug can be extremely difficult to track down. Even when you finally do find the bug, the chances are you still can't reconstruct the final state of affairs.
A few well-placed assertions will probably stop the program quite early in this process, when the evidence of what went wrong has seen little or no damage. They turn a difficult bug into a relatively straightforward one.
A buggy program without assertions might not crash at all but muddle through to normal termination, producing garbled output. What is much worse is that the output could be erroneous in so subtle a way that nobody notices it, during testing. Assertions often mean that more bugs are noticed early.
Diagnosing the Problem
Problems detected by assertion failures are usually relatively easy to diagnose. The problem has been caught early. Try to determine what path was followed to the failing assertion. Ask what statements on that path set the values involved in the failing condition. This often greatly narrows the portion of code you must examine, so you can review it quickly for errors.
It also frequently happens that this is a path you forgot to put ensurer code into at all. Control flow has slipped around all your carefully-coded ensurer statements. Uninitialized variables are a classic special case of this.
The only other possibility is that you ensured the asserted condition, then did something to negate it later. This is the hardest case to find, because the location of the problem code is not narrowed down as much. The code that did the negating either shouldn't or else it needs some more statements to reensure the condition.
Diagnosing assertion failures can be difficult when the failing expression involves dereferenced pointers. The objects pointed to are often not named variables. Furthermore, different parts of the code that manipulate them usually use different pointer variables, with different names, to locate the same object. Thus it is hard to identify related ensurer and relyer code sections.
The best approach is to use the type of the object as a locator. Find other places that also use objects of this type and and ask whether they can be the same objects as in the failing assertion.
Choosing a Repair
Once you have diagnosed an assertion failure, you want to switch to an algorithmic thinking style. Try to understand not just how this case failed but all the cases where this particular bug could occur.
After you think you understand the problem algorithmically, you must decide how to fix it. This is not necessarily easy. You must think about the ensurer code, the relyer code, the assertion, and their relationship. Obviously, the ensurer code did not match up with the assertion, or it would never have failed. But this does not necessarily mean the the ensurer code needs to be fixed.
You might realize that the assertion you wrote is much harder than you thought to ensure. Now is a good time to also review relyer code to see if it can more easily be fixed to work without relying on the assertion. Perhaps it can best be changed to rely on a weaker assertion which is already ensured or that you can ensure with simple changes. In these cases, don't forget to delete or change the original assertion too.
It occasionally happens that what you thought was relyer code actually works fine without needing the asserted condition at all. This is an overzealous assertion. Just delete or weaken the assertion. This is a case where using assertions has introduced a bug that wasn't there without them, since it made the program crash unnecessarily. These are far less frequent than the cases where assertions help, so the cost is well worth it. In the project I mentioned earlier, there was just one instance of an overzealous assertion.
Storage Leaks
Storage leaks occur when you fail to release all the dynamically allocated storage after you finish with it. They can be particularly obnoxious bugs to find. Not only do they occur in widely-scattered places, but they are especially bad about not showing symptoms until much later. Assertions can help greatly, although they may not get you as close to the original problem as they can for many other kinds of bugs.
First, instrument all allocation and deallocation statements to keep track of the total amount of storage allocated but not deallocated. Usually, you can identify certain points where everything should have been deallocated. A simple assertion can check this, by ensuring that the net allocation count you have been keeping has gone back to zero.
You may also be able to discover pairs of points such that everything allocated after the first point must be deallocated by the time control reaches the second. You can check this by saving the allocation count at the first point and verifying that it is equal to the saved value at the second point.
You may have to experiment with your assertions for storage leak detection. Often there is some allocation and deallocation going on that you didn't think about. I have also occasionally found bugs this way that were not really allocation problems but that showed up indirecly in allocation imbalances.
When You Are Done Debugging
The assert macro can be disabled by defining macro name NDEBUG. Then when you recompile, all the assertions will expand into a void expression that does nothing. If you believe the last bug is gone, you can do this to generate a release version of your program.
If your confidence that the last bug is gone is just slightly shaky, you have a dilemma. Leaving assertions enabled could cause a graceless crash. On the other hand, there is no telling what turning them off will do. If there is an overzealous assertion, disabling assertions would eliminate a crash. If there is a real bug, it will just change the symptoms in some unpredictable way. Is this possibility better than an assertion failure? It is very hard to decide.
My personal practice is to leave assertions active in released programs. However, I sometimes rework assert so that the behavior of an assertion failure is a little more graceful. For example, in an interactive application, I would display a message informing the user that an internal error was detected. Then, rather than just aborting the application, I would attempt to recover so the user can try a different command. This is not easy, because the failing command may have left things in an inconsistent state. Often you can do it, at least for the majority of cases.
Try using assertions in your next programming project. You have to start during coding. I think you will find the extra time pays off very well by both speeding up initial debugging and creating a less buggy program in the end.
References
Lampson, Horning, London, Mitchell, Popek. February 1977. Report on the Programming Language Euclid. ACM SIGPLAN Notices.
