Segfault on std::vector
June 3, 2016 by Chris Johnson. Filed under
Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378
Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379
Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380
Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381
Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382
Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383
Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378
Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379
Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380
Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381
Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382
Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383
code, public.
I was writing a syntax highlighter for the Madeup desktop application the other day. I already had a lexer written months ago that generated a token stream. Each token in the stream knows its indices in the source code, so I sat down to write a pretty innocent algorithm:
tokens = lex src
for each token in tokens
case token.type
when COMMENT
color src[token.start..token.end] in mute gray
when NUMBER
color src[token.start..token.end] token orange
when IDENTIFIER
color src[token.start..token.end] token dark blue
etc
end
end
It worked pretty well, except the GUI framework complained about the indices of the last couple of tokens. Oh, yeah. The last couple of tokens are artificial ones that aren’t really in the original source. The last one is END_OF_FILE, which I emit so the parser knows when to stop processing. The second to last one is NEWLINE, which I insert just in the case the programmer didn’t include one. If the parser can assume that all statements end with a NEWLINE, the rules are simpler. (This practice is common. See how POSIX defines line.) Trying to colorize these artificial tokens triggered the warning.
So, I changed my loop a bit:
for i = 0; i < tokens.size - 2; ++i
...
end
This generated a segfault—sometimes. My routine worked fine on blank source. It worked on longer programs too. But sometimes it crashed. That’s weird, I thought. I’m doing strictly less work than before. How can I be getting a segfault? I wish I could say I found the answer right away. But I didn’t. Here’s a minimum working example that demonstrates the same problem:
#include <iostream>
#include <vector>
int main(int argc, char **argv) {
std::vector<int> numbers;
for (int i = 0; i < numbers.size() - 2; ++i) {
std::cout << "numbers[" << i << "]: " << numbers[i] << std::endl;
}
return 0;
}
On my machine, this generates a segfault pretty reliably. It might not on your machine, but it definitely shouldn’t print anything, since the vector is empty.
The issue is numbers.size() - 2. The size method probably returns a size_t value, an unsigned type. If the size is ever 0, the subtraction will wrap around and the upper bound will be really big:
#include <iostream>
int main(int argc, char **argv) {
size_t size = 0;
// prints 18446744073709551614
std::cout << "size - 2: " << size - 2 << std::endl;
return 0;
}
So, how was the number of tokens ever 0, given my two artificial tokens? When the lexer encounters a unknown token early in the processing, I raise an exception and no tokens are emitted. I still want the highlighter to colorize as much as it can on such an exception, so I must still process whatever tokens I do have.
The fix was simple: just favor addition over subtraction:
#include <iostream>
#include <vector>
int main(int argc, char **argv) {
std::vector<int> numbers;
for (int i = 0; i + 2 < numbers.size(); ++i) {
std::cout << "numbers[" << i << "]: " << numbers[i] << std::endl;
}
return 0;
}