My C++ Debugging Challenge
A while ago I posted a C++ debugging challenge to LinkedIn. About 60 lines of code with a subtle bug. In this article I will analyze and fix the bug.
The challenge
When built with ‘-g -O1’, the code outputs a never-ending stream of lines that follow this pattern:
0 32508
1 32508
2 32508
...This is a bug.
It should have printed a sequence from 0 to 9 in both columns. You don’t need a complete understanding to start debugging, but maybe you want to have a look at the code below to see whether you can figure out how it should have worked.
Top marks if you spot the bug just reviewing the code. If you’re like me, you will not find it with a review, so let’s dig in!
The analysis
As with every debugging problem, you want to get as much guidance from tooling you can, so let’s enable warnings, and while we’re at it treat them as errors. That’s nearly always a good idea.
And indeed we get a warning:
In member function 'range::iterator range::begin() const',
inlined from 'enumerate<T>::iterator enumerate<T>::begin() const [with T = range]' at <source>:53:41,
inlined from 'int main()' at <source>:60:37:
<source>:29:58: error: '<anonymous>.range::mStep' is used uninitialized [-Werror=uninitialized]
29 | iterator begin() const { return iterator(mBegin, mStep); }Let’s try to make some sense of this new information. Beside all the text that indicates the context of the error, it basically says that range::mStep has not been initialized in a call to range::begin().
Reading the code, we see on line 20 that mStep has a default initial value, so this is not a matter of forgotten initialization. Every constructor will initialize this field. We must conclude that the range object itself is sound.
If the range object is sound, it must mean that it is uninitialized during the call to the range::begin() method. There’s no messing around with pointers and casts, which may be a cause of uninitialized use, at least at run-time, so where is this dirty piece of code that causes this method to be called on an uninitialized object?
The life-time of an object follows these stages: allocation, construction, use, destruction. The object may be uninitialized before construction or after destruction. Let’s see where these stages are for the range object.
The range object is allocated and constructed on line 60, in the ranged-for construct. For its use it is not assigned to a variable, but it is passed as a temporary value to another function, the enumerate constructor. On line 51, the enumerate object takes it as a reference and maintains the reference in the field mContainer. The enumerate object holds a reference to a temporary object.
Where is the destruction? Apparently it is not at the end of the main function.
Let’s hypothesize:
The temporary range object is destructed right after a reference was passed to the enumerate object, invalidating the reference.
We can test this hypothesis by adding a destructor to range, and printing some message:
~range() {
printf("Range destructed\n");
}Debugging by printf(), you’ve got to love it. But sure enough, the message is printed before the endless list of wrong numbers.
Now we know where the code goes wrong. But what exactly is the problem?
- We pass a reference to a temporary object.
- We store a reference to an object.
In isolation, these points don’t seem to be a big problem. Only the combination. We can fix the bug by addressing either point. Let’s see what the effect is.
The fix (1)
If we consider point (1) to be the problem, we could modify the code to pass a reference to a non-temporary range object. We store the range in a local variable and pass that to the enumerate constructor. This was the solution proposed by Sachin Chadha in his comment.
Change line 60 to this:
const auto& r = range(10);
for (auto p: enumerate(r)) {It works.
But... I don’t really want to write the loop that way. It lacks elegance. Moreover, I’m still left with this ticking time-bomb that could go off if anyone accidentally did pass a temporary object to enumerate.
The fix (2)
Another fix addressing point (1) would be to have enumerate make a copy of the container in its constructor. That would work, but if we were to enumerate a vector it would create a duplicate. I know what’s been said about premature optimization, but this is a performance problem waiting to happen.
The fix (3)
If we consider point (2) to be the problem, then we should modify the code to not store a reference to the container in the enumerate object.
The container is used in only 2 ways. It is called with begin() and it is called with end(), and both return an iterator object, not a reference. So rather than store the container, we can store the begin and end iterator objects. You can see the effect here.
Note that this changes the behavior! If slightly. The iterators may change between the construction of enumerate and the calls to enumerate::begin(). But I think this is an acceptable change given the increased safety and elegance.
The conclusion
We had a buggy piece of code, discovered it was a problem with the lifetime of a temporary, and, through careful analysis, found a number of solutions. The fix we chose was performant and, more importantly, robust, not only fixing this bug but preventing future problems with these classes.
I’m happy with the fix, but I’m annoyed it’s necessary. Bugs like these should be hard to make or easy to spot. Although they make for a nice challenge. I feel it really shouldn’t have been. The language should have protected me from making this — well — beginner’s mistake.
