On a C++ programming forum, somebody asked a relatively simple question: How do you write a function that counts the number of lines in a text file? Most of the answers were friendly and helpful, but flawed.
As programmers, we often think of a problem as so trivial that we don’t take the time to think through the answers or to appreciate the subtlety of corner cases. In one of my favorite books, Programming Pearls, Jon Bentley talks about how hard it is for programmers to get fairly simple and routine problems correct on the first try. He writes:
I’ve assigned this [binary search] problem in courses at Bell Labs and IBM. Professional programmers had a couple hours to [implement a binary search] in the language of their choice; a high-level pseudocode was fine. At the end of the specified time, almost all the programmers reported that they had the correct code for the task. We would then take thirty minutes to examine their code, which the programmers did with test cases. In several classes and with over a hundred programmers, the results were varied little; ninety percent of the programmers found bugs in their programs (and I wasn’t always convinced of the correctness of the code in which no bugs were found). [p. 36]
Remember, these are professional programmers, in the language of their choice, with hours of time, messing up a binary search.
Notice the oh-so-common pattern here:
- Write code.
- Declare that it works.
- Test it and discover it’s broken.
It’s enough to make you wonder if there’s a better way. Many people in the extreme programming and agile crowds would say that we’re doing it all out of order. Not only should “declare it works” come after testing, but probably so should writing code. So let’s take this seemingly trivial line-counting problem and apply a little test-driven development in C++.
First, let’s agree on an interface. I propose:
template <typename InputIt>
size_t CountLines(InputIt begin, InputIt end);
That is, we’ll give the function a pair of iterators pointing to the beginning and end of the text we want examined, and the function will return the number of lines. (If you want to count the lines in a file, read the file into a std::string and call the function.) I’ve used size_t for the return type, as that’s typically unsigned (after all, the count will be 0 or more—it can’t be negative), and it’s generally as large an integer type as your platform will comfortably handle, so we shouldn’t have to worry about text consisting of too many lines. If you’re not a fan of the template parameters for the iterator types, feel free to re-write it with const char pointers.
Now that we know the interface, we will write the test function—even before we discuss how we’ll count lines. This function will iterate through a set of test cases, feed the input to CountLines, and check the return.
bool Test_CountLines() {
struct TestCase {
std::string input;
size_t output;
};
const TestCase tests[] = {
{"Hello\nWorld\n", 2}
};
const size_t cTests = sizeof(tests) / sizeof(tests[0]);
size_t cPassed = 0;
size_t cFailed = 0;
for (size_t i = 0; i < cTests; ++i) {
const TestCase &test = tests[i];
size_t cLines = CountLines(test.input.begin(), test.input.end());
if (cLines == test.output) {
++cPassed;
} else {
std::cerr << "FAILURE" << std::endl
<< "Input \"" << test.input << '"' << std::endl
<< "Output " << cLines << " instead of " << test.output << std::endl;
++cFailed;
}
}
return cPassed == cTests && cFailed == 0;
}
I’ve started us with one test case, and we can add more as we develop the function. Just to make sure our testing framework is solid, let’s stub out CountLines and a little main function to make sure it all compiles and runs.
template <typename InputIt>
size_t CountLines(InputIt /* begin */, InputIt /* end */) {
size_t cLines = 0;
return cLines;
}
I commented out the parameter names to avoid the “unused parameter” warnings. These will come into play shortly.
int main() {
assert(Test_CountLines());
return 0;
}
If you put all this together and run it, you’ll see that the test fails as expected. This is good, as we want to make sure we exercise the failure case of our test function to know that it works.
Some of you are probably saying that you could have already written a correct CountLines function by now. Maybe. Remember all those “helpful” answers on the programming forum? Remember all those professional developers attempting a binary search? Besides, it really didn’t take long to build this test infrastructure. If a bug ever does crop up in the function, we can easily debug it. When we fix a bug, we can immediately verify that we didn’t create a regression by re-checking every test case we’ve ever come up with. And you can add that new test case so that it never breaks again. If you change something fundamental, like the compiler or OS you’re using one, you can know with certainty whether or not it affects the behavior of your function.
Next we need test cases. Off the top of my head, here are some interesting cases we’ll have to design for:
- An empty string should have zero lines.
- The count of a string with blank lines or empty lines (e.g., “Hello\n\nWorld!\n”) should include those blank lines.
Doesn’t seem too hard yet, so let’s add those test cases.
const TestCase tests[] = {
{"", 0},
{"Hello\nWorld\n", 2},
{"Hello\n\nWorld\n", 3}
};
It seems pretty “obvious” that the way to count the lines is to count the number of newline (‘\n’) characters in the string:
template <typename InputIt>
size_t CountLines(InputIt begin, InputIt end) {
return std::count(begin, end, '\n');
}
Ta da! Test-driven development has led us directly to one of the common—but incorrect—answers given on the programming forum.
Consider the string “Hello”. That has zero newline characters, but most people would consider it to be one line long. Too bad we didn’t think of that while coming up with our test cases. Now that we have thought of it, the first thing to do is to add it to our test code.
const TestCase tests[] = {
…
{"Hello", 1},
…
};
We might be tempted to treat this new string as a special case.
// Ugly -- don't do this!
template <typename InputIt>
size_t CountLines(InputIt begin, InputIt end) {
size_t cLines = std::count(begin, end, '\n');
if (cLines == 0 && begin != end) {
cLines = 1;
}
return cLines;
}
While this hack will pass our tests, it’s ugly and still wrong. We’ve failed to realize that the “Hello” string is just a special case of not having a newline character on the last line in the string. (This is an extremely common bug in the wild. Many parsers choke if the last line of the input doesn’t end with a newline.) So we add another test case:
const TestCase tests[] = {
…
{"Hello\nWorld", 2},
…
};
When adding a test case, it’s good to think of counter-examples. For instance, if the last line of the string does end with a newline, that shouldn’t trigger an extra line. Fortunately, we’ve already got a test case for that.
Now our original approach is starting to look bad. Simply counting the newline characters, even with some hacky fix-ups for “corner cases”, isn’t going to work.
All is not lost. Yes, we have to completely re-think how we’re going to implement CountLines, but none of that invalidates the test framework we’ve built. When we come up with our new solution, we can immediately check to see if it solves the new test cases as well as the others we’ve already made. Suddenly it looks like the time we’ve put into the test framework is going to pay off.
There are a few ways to solve the line counting problem, but they all boil down to a state machine. Here’s my solution:
template <typename InputIt>
size_t CountLines(InputIt begin, InputIt end) {
size_t cLines = 0;
bool bStartOfLine = true;
for ( ; begin != end; ++begin) {
if (bStartOfLine) {
++cLines;
}
bStartOfLine = *begin == '\n';
}
return cLines;
}
In this case, there’s not much state—just a boolean. If we’re at the beginning of a line, and there’s anything on it (even a ‘\n’), then we need to count the line. After that, we simply need to figure out if the next character will be at the start of a line or not. This solution passes all five of our test cases.
Some say that you shouldn’t “waste time” on the corner cases, since, well, they’re corner cases. In my experience, though, if you get the corner cases right, then the mainstream cases generally just work. After all, the corner cases should just be degenerate versions of the mainstream case—or vice versa.
Uh oh, another bug. We’ve been considering ‘\n’ to be the newline character. Text files on Multics-derived operating systems use a single ASCII line feed character (LF) to indicate a line break, but that’s far from universal. CP/M, DOS, Windows and a lot of Internet protocols require a carriage return (CR) followed by LF to mark a line break. C and C++ file i/o routines will translate whichever convention your platform uses to and from ‘\n’. Most compilers give ‘\n’ the value 0×0A, which happens to be the same as an ASCII LF. On Unix systems, the compiler’s i/o routines have to do no translation. On others, when you write ‘\n’, the output routine actually writes CR-LF, and when the input routine reads CR-LF, it returns ‘\n’. (Read all about newlines on Wikipedia.)
But if we were to read in the data in binary mode (which could be faster), then we’ll see the actual bytes used in the file. So we have to add test cases. First, we’ll add the CR+LF cases. Then we’ll conditionally add ones with explicit LFs in case our compiler doesn’t use LF for ‘\n’.
const TestCase tests[] = {
…
{"Hello\x0D\x0AWorld", 2},
{"Hello\x0D\x0AWorld\x0D\x0A", 2},
{"Hello\x0D\x0A\x0D\x0AWorld\x0D\x0A", 3},
#if '\n' != '\x0A'
{"Hello\x0AWorld", 2},
{"Hello\x0AWorld\x0A", 2},
{"Hello\x0A\x0AWorld\x0A", 3}
#endif
};
Happily, our latest version of CountLines works with these new examples. Essentially, the CR characters aren’t important to the algorithm, and our compiler does assign LF for ‘\n’.
If you did read the Wikipedia article, you know that there are several more newline conventions that we might want to support. Old Mac and Amiga files use just a CR, old IBM mainframes used NEL from the EBCDIC character set, Unicode introduced LINE SEPARATOR and PARAGRAPH SEPARATOR code points, etc. I’m sure you could imagine refining CountLines to handle these additional cases. Essentially, the state machine grows in complexity.
Conclusion
OK, this has been a long blog post, mostly because I’ve shown the iterative process necessary to solve the problem. What we’ve seen is that even the simplest problems might be more complex than we anticipate. The more thought we put into coming up with test cases, the more robust an implementation we were able to write. And when we had to start the implementation over from scratch, having a unit test framework helped us quickly ensure that the new implementation was at least as correct as the previous one.
