A Case Where Using Auto Leads to Undefined Behaviour
C++11’s feature auto
has changed the looks of C++ code. In a lot of cases, auto
alleviates code from burdening information, and using it does make code simpler. So much so that using auto
becomes a second nature to make code more expressive.
Should we use auto
always? According to Herb Sutter guideline for C++11, yes, almost always (which has now been updated to Always in C++17).
Almost always.
Today we’ll see a case where you don’t want to use auto
, because it causes undefined behaviour, in a way that is not immediate to spot (and I haven’t found thus bug described elsewhere, please point me to an existing resource if I’m wrong).
I’m not arguing against auto
in the general case though, I think it does makes code flow better. But if you encounter the following case, it should save you some time to know that you shouldn’t use auto
there.
The case
We have a collection of bool
s, idiomatically stored in a std::deque<bool>
(the fact that this is idiomatic is not that glorious, but anyway) that you can think of as representing a binary number. The first elements are the most significant digits, and the last ones are the least significant digits.
We would like to do a ‘+1’ on this “binary number”, that is to say to produce the collection of bool
s that corresponds to that binary number + 1. To do this, we work our way up from the back of the collection, flip the current bit, and stop when it flips to 1.
For logging purposes, we print the value of the examined bit along with its position in the collection:
void flip(bool& bit) { bit = !bit; } void increment(std::deque<bool>& bits) { if (bits.empty()) return; if (bits.size() == 1) { flip(bits.back()); } for (auto bitIndex = bits.size() - 1; bitIndex >= 0; --bitIndex) { auto& bit = bits[bitIndex]; std::cout << "bitIndex=" << bitIndex << " value= " << bit << '\n'; flip(bit); if (bit == true) { break; } } }
If we test it by incrementing a binary number enough times so that it loops back to 0:
int main() { auto number = std::deque<bool>(3); increment(number); increment(number); increment(number); increment(number); increment(number); increment(number); increment(number); increment(number); }
Then the program…crashes.
Can you see why? Hint: it is because of one of the auto
s of the code, that isn’t doing what we’d naively expect. If you’d like to play around with the code, here is the code where the crash occurs.
The next section explains the cause of the problem, so if you’d like to think about it on your own first, maybe wait a minute before scrolling down the page.
…
…
One auto
too far?
Done searching? The culprit is the auto
in the initialization of the for loop:
void flip(bool& bit) { bit = !bit; } void increment(std::deque<bool>& bits) { if (bits.empty()) return; if (bits.size() == 1) { flip(bits.back()); } for (auto bitIndex = bits.size() - 1; bitIndex >= 0; --bitIndex) { auto& bit = bits[bitIndex]; std::cout << "bitIndex=" << bitIndex << " value= " << bit << '\n'; flip(bit); if (bit == true) { break; } } }
Indeed, this auto
defines bitIndex
to be of the type of bits.size() - 1
, which is itself the type of bits.size()
. Which in practice is often of type size_t
, which is unsigned.
So bitIndex
is unsigned. So if we pass in 1 1 1
to increment
, the for loop works its way from the back and all the way up to the beginning of the collection. bitIndex
is then 0
. The for loop performs an ultimate --bitIndex
, which looks like it sets bitIndex
to -1
and make the loop stop, but there is no such thing as -1
in the world of the unsigned.
Therefore, --bitIndex
sets --bitIndex
to a very, very high integral number (the highest possible unsigned number, like the mind-bogglingly high 18446744073709551615
on the implementation I tested), which is greater than 0, so the loops rolls on! It then tries to access an element of the collection that is way, way past its end (and even way past the end of your RAM, and the room that your computer is sitting in).
This causes undefined behaviour, which occurs in the form of a seg fault in this case. I’ve tried an analogous use case using std::vector
instead of std::deque
(therefore, not on booleans), and the program didn’t crash. Instead, it displayed the very big numbers. But this is still standard C++ since undefined behaviour can be anything, by definition.
To fix the issue, we can simply replace this auto
with int
, because this is really what we want here:
void increment(std::deque<bool>& bits) { if (bits.empty()) return; if (bits.size() == 1) { flip(bits.back()); } for (int bitIndex = bits.size() - 1; bitIndex >= 0; --bitIndex) { auto& bit = bits[bitIndex]; std::cout << "bitIndex=" << bitIndex << " value= " << bit << '\n'; flip(bit); if (bit == true) { break; } } }
Shouldn’t we avoid for loops in the first place?
The point here was to illustrate this risk with auto
. But going slightly off-topic, was this code well-designed in the first place? We know that we should try to avoid for loops and that using STL algorithms make code more robust and expressive, right?
There is one thing that makes using algorithms difficult here: we’re accessing the position of the current element in the collection here (bitIndex
). And STL algorithms don’t play well with positions. There are techniques to work around using a raw loop for that though, that we see in a dedicated article (see How to Access the Index of the Current Element in a For Loop), but it requires to write a bit of specific code for that.
If we didn’t have to access the position of the current element, there is a quick fix we could do to begin with: using reverse iterators instead of indexes:
void increment(std::deque<bool>& bits) { if (bits.empty()) return; if (bits.size() == 1) { flip(bits.front()); } for (auto bit = rbegin(bits); bit != rend(bits); ++bit) { flip(*bit); if (*bit == true) { break; } } }
And using auto
is fine now, because it resolves to an iterator type, no longer an unsigned number.
But a better solution would be to go all the way with STL algorithms! Which is off-topic for this post on auto
, but right on topic for a future post.
Stay tuned!
You may also like
Don't want to miss out ? Follow:Share this post!