Capstone 1: testing the parser
The parser has four rules and six kinds, and the cases that break it are the ones nobody wrote a program for. A table of documents and expected results covers them in a page and runs in a millisecond.
The harness is the one from lesson 085 with the parser plugged in. The last section is the part that matters on a build server: a test runner that prints failures and returns success is worse than no tests at all.
The three tables also show the shape of the whole suite: good input, bad input and a failing expectation. A project that keeps the three in one file runs them in one command, which is what the build server needs.
The three programs also run in one command, and the command's status is the one the build server reads. The table is data, so a new case is a line and not a function.
A table of good documents
Each row is a document and the kind of value it should produce. The loop parses the document, compares the kind and prints a line only when the two disagree, which keeps a passing run quiet.
The program checks four documents and prints 4 passed. The string and the number rows are the ones that catch the quoted flag of the tokenizer, because a number in quotes must come out as a string.
The table is the documentation of what the parser accepts. A bug report becomes a new row, and the row stays after the fix, which is the property a regression test is for.
#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct token
{
std::string text;
bool quoted;
};
std::vector<token> split(const std::string& text)
{
std::vector<token> tokens;
for (std::size_t i = 0; i < text.size();) {
unsigned char current = static_cast<unsigned char>(text[i]);
if (std::isspace(current)) {
++i;
} else if (std::strchr("{}[]:,", text[i]) != nullptr) {
tokens.push_back({std::string(1, text[i]), false});
++i;
} else if (text[i] == '"') {
std::size_t start = ++i;
while (i < text.size() && text[i] != '"') {
++i;
}
tokens.push_back({text.substr(start, i - start), true});
++i;
} else {
std::size_t start = i;
while (i < text.size() && !std::isspace(static_cast<unsigned char>(text[i]))
&& std::strchr("{}[]:,", text[i]) == nullptr) {
++i;
}
tokens.push_back({text.substr(start, i - start), false});
}
}
return tokens;
}
struct node
{
std::string kind;
std::string text;
std::vector<std::string> keys;
std::vector<node> children;
};
class parser
{
public:
explicit parser(std::vector<token> tokens) : tokens_(std::move(tokens)) {}
node parse()
{
node value = parse_value();
if (!at_end()) {
throw std::runtime_error("trailing text at token " + std::to_string(position_));
}
return value;
}
private:
bool at_end() const
{
return position_ == tokens_.size();
}
const token& peek() const
{
return tokens_[position_];
}
std::runtime_error error(const std::string& message) const
{
return std::runtime_error(message + " at token " + std::to_string(position_));
}
node parse_value()
{
if (at_end()) {
throw std::runtime_error("unexpected end of document");
}
const token current = peek();
if (!current.quoted && current.text == "{") {
return parse_object();
}
if (!current.quoted && current.text == "[") {
return parse_array();
}
++position_;
node result;
result.text = current.text;
if (current.quoted) {
result.kind = "string";
} else if (current.text == "true" || current.text == "false"
|| current.text == "null") {
result.kind = "literal";
} else {
result.kind = "number";
}
return result;
}
node parse_object()
{
++position_;
node result;
result.kind = "object";
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
while (true) {
if (at_end() || !peek().quoted) {
throw error("expected a key");
}
result.keys.push_back(peek().text);
++position_;
if (at_end() || peek().text != ":") {
throw error("expected a colon");
}
++position_;
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
throw error("expected a comma or a closing brace");
}
}
node parse_array()
{
++position_;
node result;
result.kind = "array";
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
while (true) {
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
throw error("expected a comma or a closing bracket");
}
}
std::vector<token> tokens_;
std::size_t position_ = 0;
};
int main()
{
std::vector<std::pair<std::string, std::string>> cases{
{R"({"a": 1})", "object"},
{R"([true, null])", "array"},
{R"("text")", "string"},
{R"(42.5)", "number"},
};
int passed = 0;
for (const auto& [document, expected] : cases) {
parser read{split(document)};
std::string actual = read.parse().kind;
if (actual == expected) {
++passed;
} else {
std::cout << "FAIL " << document << ": " << actual << '\n';
}
}
std::cout << passed << " passed\n";
}
g++ -std=c++23 -Wall -Wextra good.cpp -o good_tests
./good_tests
4 passed
A table of error messages
A bad document is tested by its message, not only by the fact that it threw. The row keeps a fragment of the expected text, and the check is a substring match, so the token number can change without breaking the test.
The program feeds three broken documents to the parser and checks the message of each exception. The print is 3 passed, and a document that throws the wrong message would be reported with both texts.
The fragment is the part of the message that names the rule, such as expected a colon. The position is left out on purpose: it is the detail most likely to change when the tokenizer gains an improvement.
#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct token
{
std::string text;
bool quoted;
};
std::vector<token> split(const std::string& text)
{
std::vector<token> tokens;
for (std::size_t i = 0; i < text.size();) {
unsigned char current = static_cast<unsigned char>(text[i]);
if (std::isspace(current)) {
++i;
} else if (std::strchr("{}[]:,", text[i]) != nullptr) {
tokens.push_back({std::string(1, text[i]), false});
++i;
} else if (text[i] == '"') {
std::size_t start = ++i;
while (i < text.size() && text[i] != '"') {
++i;
}
tokens.push_back({text.substr(start, i - start), true});
++i;
} else {
std::size_t start = i;
while (i < text.size() && !std::isspace(static_cast<unsigned char>(text[i]))
&& std::strchr("{}[]:,", text[i]) == nullptr) {
++i;
}
tokens.push_back({text.substr(start, i - start), false});
}
}
return tokens;
}
struct node
{
std::string kind;
std::string text;
std::vector<std::string> keys;
std::vector<node> children;
};
class parser
{
public:
explicit parser(std::vector<token> tokens) : tokens_(std::move(tokens)) {}
node parse()
{
node value = parse_value();
if (!at_end()) {
throw std::runtime_error("trailing text at token " + std::to_string(position_));
}
return value;
}
private:
bool at_end() const
{
return position_ == tokens_.size();
}
const token& peek() const
{
return tokens_[position_];
}
std::runtime_error error(const std::string& message) const
{
return std::runtime_error(message + " at token " + std::to_string(position_));
}
node parse_value()
{
if (at_end()) {
throw std::runtime_error("unexpected end of document");
}
const token current = peek();
if (!current.quoted && current.text == "{") {
return parse_object();
}
if (!current.quoted && current.text == "[") {
return parse_array();
}
++position_;
node result;
result.text = current.text;
if (current.quoted) {
result.kind = "string";
} else if (current.text == "true" || current.text == "false"
|| current.text == "null") {
result.kind = "literal";
} else {
result.kind = "number";
}
return result;
}
node parse_object()
{
++position_;
node result;
result.kind = "object";
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
while (true) {
if (at_end() || !peek().quoted) {
throw error("expected a key");
}
result.keys.push_back(peek().text);
++position_;
if (at_end() || peek().text != ":") {
throw error("expected a colon");
}
++position_;
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
throw error("expected a comma or a closing brace");
}
}
node parse_array()
{
++position_;
node result;
result.kind = "array";
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
while (true) {
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
throw error("expected a comma or a closing bracket");
}
}
std::vector<token> tokens_;
std::size_t position_ = 0;
};
bool contains(const std::string& text, const std::string& part)
{
return text.find(part) != std::string::npos;
}
int main()
{
std::vector<std::pair<std::string, std::string>> cases{
{R"({"a" 1})", "expected a colon"},
{R"({"a": 1)", "expected a comma or a closing brace"},
{R"([1, 2)", "expected a comma or a closing bracket"},
};
int passed = 0;
for (const auto& [document, expected] : cases) {
parser read{split(document)};
try {
read.parse();
std::cout << "FAIL " << document << ": no error\n";
} catch (const std::runtime_error& error) {
if (contains(error.what(), expected)) {
++passed;
} else {
std::cout << "FAIL " << document << ": " << error.what() << '\n';
}
}
}
std::cout << passed << " passed\n";
}
g++ -std=c++23 -Wall -Wextra bad.cpp -o bad_tests
./bad_tests
3 passed
The test that fails
A test is only useful if it can fail. The row below expects a trailing comma to be accepted, and the parser rejects it, so the run reports one failure and the reason.
The program prints the failing document and the message from the parser, and the summary counts one case and one failure. That output is exactly what a developer needs: which input, and what the code said.
The expectation is wrong on purpose: JSON does not allow a trailing comma, and the parser is right. The lesson is that a failing test is sometimes a wrong test, and reading the message tells you which one to fix.
#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct token
{
std::string text;
bool quoted;
};
std::vector<token> split(const std::string& text)
{
std::vector<token> tokens;
for (std::size_t i = 0; i < text.size();) {
unsigned char current = static_cast<unsigned char>(text[i]);
if (std::isspace(current)) {
++i;
} else if (std::strchr("{}[]:,", text[i]) != nullptr) {
tokens.push_back({std::string(1, text[i]), false});
++i;
} else if (text[i] == '"') {
std::size_t start = ++i;
while (i < text.size() && text[i] != '"') {
++i;
}
tokens.push_back({text.substr(start, i - start), true});
++i;
} else {
std::size_t start = i;
while (i < text.size() && !std::isspace(static_cast<unsigned char>(text[i]))
&& std::strchr("{}[]:,", text[i]) == nullptr) {
++i;
}
tokens.push_back({text.substr(start, i - start), false});
}
}
return tokens;
}
struct node
{
std::string kind;
std::string text;
std::vector<std::string> keys;
std::vector<node> children;
};
class parser
{
public:
explicit parser(std::vector<token> tokens) : tokens_(std::move(tokens)) {}
node parse()
{
node value = parse_value();
if (!at_end()) {
throw std::runtime_error("trailing text at token " + std::to_string(position_));
}
return value;
}
private:
bool at_end() const
{
return position_ == tokens_.size();
}
const token& peek() const
{
return tokens_[position_];
}
std::runtime_error error(const std::string& message) const
{
return std::runtime_error(message + " at token " + std::to_string(position_));
}
node parse_value()
{
if (at_end()) {
throw std::runtime_error("unexpected end of document");
}
const token current = peek();
if (!current.quoted && current.text == "{") {
return parse_object();
}
if (!current.quoted && current.text == "[") {
return parse_array();
}
++position_;
node result;
result.text = current.text;
if (current.quoted) {
result.kind = "string";
} else if (current.text == "true" || current.text == "false"
|| current.text == "null") {
result.kind = "literal";
} else {
result.kind = "number";
}
return result;
}
node parse_object()
{
++position_;
node result;
result.kind = "object";
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
while (true) {
if (at_end() || !peek().quoted) {
throw error("expected a key");
}
result.keys.push_back(peek().text);
++position_;
if (at_end() || peek().text != ":") {
throw error("expected a colon");
}
++position_;
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
throw error("expected a comma or a closing brace");
}
}
node parse_array()
{
++position_;
node result;
result.kind = "array";
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
while (true) {
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
throw error("expected a comma or a closing bracket");
}
}
std::vector<token> tokens_;
std::size_t position_ = 0;
};
int main()
{
std::vector<std::string> documents{
R"({"a": 1,})",
R"({"a": 1})",
};
int failed = 0;
for (const std::string& document : documents) {
parser read{split(document)};
try {
read.parse();
} catch (const std::runtime_error& error) {
++failed;
std::cout << "FAIL " << document << ": " << error.what() << '\n';
}
}
std::cout << failed << " failed\n";
}
g++ -std=c++23 -Wall -Wextra fail.cpp -o failing_tests
./failing_tests
FAIL {"a": 1,}: expected a key at token 5
1 failed
The exit code the server reads
A test runner reports through its exit status: zero for success and anything else for a failure. The program below prints a failure and returns 0 anyway, so a build server that reads the status sees a green run.
The command runs the program and then prints the status. The output shows one failed case and exit=0, which is the bug: the summary is right and the status is wrong.
The fix is one line, return failed == 0 ? 0 : 1;. Lesson 101 showed that CTest reads exactly this status, so a runner without it is invisible to the build.
#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct token
{
std::string text;
bool quoted;
};
std::vector<token> split(const std::string& text)
{
std::vector<token> tokens;
for (std::size_t i = 0; i < text.size();) {
unsigned char current = static_cast<unsigned char>(text[i]);
if (std::isspace(current)) {
++i;
} else if (std::strchr("{}[]:,", text[i]) != nullptr) {
tokens.push_back({std::string(1, text[i]), false});
++i;
} else if (text[i] == '"') {
std::size_t start = ++i;
while (i < text.size() && text[i] != '"') {
++i;
}
tokens.push_back({text.substr(start, i - start), true});
++i;
} else {
std::size_t start = i;
while (i < text.size() && !std::isspace(static_cast<unsigned char>(text[i]))
&& std::strchr("{}[]:,", text[i]) == nullptr) {
++i;
}
tokens.push_back({text.substr(start, i - start), false});
}
}
return tokens;
}
struct node
{
std::string kind;
std::string text;
std::vector<std::string> keys;
std::vector<node> children;
};
class parser
{
public:
explicit parser(std::vector<token> tokens) : tokens_(std::move(tokens)) {}
node parse()
{
node value = parse_value();
if (!at_end()) {
throw std::runtime_error("trailing text at token " + std::to_string(position_));
}
return value;
}
private:
bool at_end() const
{
return position_ == tokens_.size();
}
const token& peek() const
{
return tokens_[position_];
}
std::runtime_error error(const std::string& message) const
{
return std::runtime_error(message + " at token " + std::to_string(position_));
}
node parse_value()
{
if (at_end()) {
throw std::runtime_error("unexpected end of document");
}
const token current = peek();
if (!current.quoted && current.text == "{") {
return parse_object();
}
if (!current.quoted && current.text == "[") {
return parse_array();
}
++position_;
node result;
result.text = current.text;
if (current.quoted) {
result.kind = "string";
} else if (current.text == "true" || current.text == "false"
|| current.text == "null") {
result.kind = "literal";
} else {
result.kind = "number";
}
return result;
}
node parse_object()
{
++position_;
node result;
result.kind = "object";
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
while (true) {
if (at_end() || !peek().quoted) {
throw error("expected a key");
}
result.keys.push_back(peek().text);
++position_;
if (at_end() || peek().text != ":") {
throw error("expected a colon");
}
++position_;
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "}") {
++position_;
return result;
}
throw error("expected a comma or a closing brace");
}
}
node parse_array()
{
++position_;
node result;
result.kind = "array";
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
while (true) {
result.children.push_back(parse_value());
if (!at_end() && peek().text == ",") {
++position_;
continue;
}
if (!at_end() && peek().text == "]") {
++position_;
return result;
}
throw error("expected a comma or a closing bracket");
}
}
std::vector<token> tokens_;
std::size_t position_ = 0;
};
int main()
{
parser read{split("[1, 2")};
int failed = 0;
try {
read.parse();
} catch (const std::runtime_error& error) {
++failed;
std::cout << "FAIL: " << error.what() << '\n';
}
std::cout << failed << " failed\n";
}
g++ -std=c++23 -Wall -Wextra exit.cpp -o exit_runner
./exit_runner; echo "exit=$?"
FAIL: expected a comma or a closing bracket at token 4
1 failed
exit=0
Exercises
- Add a good row for an empty object and an empty array, and check that both parse.
- Add a bad row for a string with an unterminated escape and choose the fragment to expect.
- Fix the exit code and run the program through ctest of lesson 101.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why is a table of documents better than a hand-written test per bug?
Answer
A new case is one row, and every case runs the same way
The rows are data, so the cost of a new regression test is one line.
-
How does the bad-document test compare the error?
Answer
It looks for a fragment of the message
The fragment survives a change of token numbers and still names the rule that failed.
-
What exit status should a failing test runner return?
Answer
A non-zero value
The build server stops on a non-zero status, and 0 means success to every runner.
-
What does the good table print?
Answer
4 passed
All four documents parse to the expected kinds, so only the summary is printed.
-
What does the bad table print?
Answer
3 passed
Each exception message contains the fragment, so all three cases pass.
-
What does the failing run print?
Answer
FAIL for the trailing comma and 1 failed
The trailing comma is rejected, and the loop counts the one exception.
-
Why is the trailing-comma test's expectation wrong?
Answer
JSON does not allow a trailing comma
The grammar has no trailing comma, so the rejection is correct and the test expectation is not.
-
What does this program print?
#include <iostream> int failures = 0; void check(bool condition, const char* what) { if (!condition) { std::cout << "FAIL: " << what << '\n'; ++failures; } } int main() { check(2 + 2 == 5, "add(2, 2) == 5"); std::cout << failures << " failed"; }Answer
FAIL: add(2, 2) == 5 / 1 failed
The check fails, the message names it, and the summary counts one failure.
-
What makes a test runner invisible to a build server?
Answer
Returning 0 when a test failed
The server reads the status first and the output only after a failure.
-
What is the right expectation for a document that throws?
Answer
The rule fragment in the message
The rule is the stable part; the position changes when the tokenizer changes.
The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev