Capstone 1: testing the parser
The capstone has five lessons of code behind it and this one is the first that runs it as a whole. A test at this level is not a proof that the parser is correct; it is a guard that keeps the four earlier lessons correct after the next change, and the table is small enough to read in one screen.
A parser is easy to test because it is a function from text to a tree, and a table of documents covers it better than a handful of named tests. Each row gives a document and what the result must be: the shape of the tree for a good document, a fragment of the message for a bad one. The runner walks the table, prints a line per row and counts the failures.
The four sections use the same capstone program and a different table: good documents with a round trip, bad documents with their messages, a wrong expectation that the runner reports, and a main that returns a status a pipeline can read.
A table of good documents
The shape of a tree is the smallest property worth checking for a good document: it proves that the parser read the text and picked the right variant without freezing the whole value in the test. The round trip is the second property, and it checks the writer at the same time.
The table below has one document per kind of container and scalar. The runner prints a line per row and a count at the end.
#[derive(Debug, Clone, PartialEq)]
enum Token {
OpenBrace,
CloseBrace,
OpenBracket,
CloseBracket,
Colon,
Comma,
Text(String),
Number(f64),
Word(String),
End,
}
fn text_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
*position += 1;
let mut value = String::new();
while *position < bytes.len() && bytes[*position] != b'"\' {
let byte = bytes[*position];
if byte == b\'\\\' {
*position += 1;
match bytes.get(*position) {
Some(b\'"') => value.push('"\'),
Some(b\'\\\') => value.push(\'\\\'),
Some(b\'n\') => value.push(\'\n\'),
Some(b\'t\') => value.push(\'\t\'),
Some(b\'u\') => {
let digits = bytes.get(*position + 1..*position + 5)
.ok_or_else(|| format!("short unicode escape at {}", *position))?;
let hex = std::str::from_utf8(digits)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
let code = u32::from_str_radix(hex, 16)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
value.push(char::from_u32(code)
.ok_or_else(|| format!("bad code point at {}", *position))?);
*position += 4;
}
_ => return Err(format!("bad escape at {}", *position)),
}
} else {
value.push(byte as char);
}
*position += 1;
}
if *position == bytes.len() {
return Err(format!("unterminated text at {start}"));
}
*position += 1;
Ok(Token::Text(value))
}
fn number_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
while *position < bytes.len()
&& matches!(bytes[*position], b\'0\'..=b\'9\' | b\'-\' | b\'+\' | b\'.\' | b\'e\' | b\'E\')
{
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
match slice.parse() {
Ok(value) => Ok(Token::Number(value)),
Err(_) => Err(format!("bad number at {start}")),
}
}
fn word_token(bytes: &[u8], position: &mut usize) -> Token {
let start = *position;
while *position < bytes.len() && bytes[*position].is_ascii_alphabetic() {
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
Token::Word(slice.to_string())
}
fn tokenize(text: &str) -> Result<Vec<Token>, String> {
let bytes = text.as_bytes();
let mut position = 0;
let mut tokens = Vec::new();
loop {
while position < bytes.len() && bytes[position].is_ascii_whitespace() {
position += 1;
}
if position == bytes.len() {
tokens.push(Token::End);
return Ok(tokens);
}
let start = position;
let token = match bytes[position] {
b\'{\' => { position += 1; Token::OpenBrace }
b\'}\' => { position += 1; Token::CloseBrace }
b\'[\' => { position += 1; Token::OpenBracket }
b\']\' => { position += 1; Token::CloseBracket }
b\':\' => { position += 1; Token::Colon }
b\',\' => { position += 1; Token::Comma }
b\'"' => text_token(bytes, &mut position)?,
b'-' | b'0'..=b'9' => number_token(bytes, &mut position)?,
b'a'..=b'z' => word_token(bytes, &mut position),
other => return Err(format!("unexpected character \'{}\' at {start}", other as char)),
};
tokens.push(token);
}
}
#[derive(Debug, Clone, PartialEq)]
enum Value {
Null,
Bool(bool),
Number(f64),
Text(String),
Array(Vec<Value>),
Object(Vec<(String, Value)>),
}
struct Parser {
tokens: Vec<Token>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Parser {
Parser { tokens, position: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.position]
}
fn next(&mut self) -> Token {
let token = self.tokens[self.position].clone();
self.position += 1;
token
}
fn value(&mut self) -> Result<Value, String> {
match self.peek().clone() {
Token::OpenBrace => self.object(),
Token::OpenBracket => self.array(),
Token::Text(text) => {
self.next();
Ok(Value::Text(text))
}
Token::Number(number) => {
self.next();
Ok(Value::Number(number))
}
Token::Word(word) => {
self.next();
match word.as_str() {
"true" => Ok(Value::Bool(true)),
"false" => Ok(Value::Bool(false)),
"null" => Ok(Value::Null),
other => Err(format!("unknown word {other}")),
}
}
other => Err(format!("expected a value, found {other:?}")),
}
}
fn array(&mut self) -> Result<Value, String> {
self.next();
let mut items = Vec::new();
if matches!(self.peek(), Token::CloseBracket) {
self.next();
return Ok(Value::Array(items));
}
loop {
let value = self.value()?;
items.push(value);
match self.next() {
Token::Comma => continue,
Token::CloseBracket => return Ok(Value::Array(items)),
Token::End => return Err("document ended inside an array".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
fn object(&mut self) -> Result<Value, String> {
self.next();
let mut fields = Vec::new();
if matches!(self.peek(), Token::CloseBrace) {
self.next();
return Ok(Value::Object(fields));
}
loop {
let key = match self.next() {
Token::Text(text) => text,
other => return Err(format!("expected a key, found {other:?}")),
};
match self.next() {
Token::Colon => {}
other => return Err(format!("expected a colon, found {other:?}")),
}
let value = self.value()?;
fields.push((key, value));
match self.next() {
Token::Comma => continue,
Token::CloseBrace => return Ok(Value::Object(fields)),
Token::End => return Err("document ended inside an object".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
}
fn parse(text: &str) -> Result<Value, String> {
let tokens = tokenize(text)?;
let mut parser = Parser::new(tokens);
let value = parser.value()?;
match parser.peek() {
Token::End => Ok(value),
other => Err(format!("trailing token {other:?}")),
}
}
#[allow(dead_code)]
impl Value {
fn as_number(&self) -> Option<f64> {
match self {
Value::Number(number) => Some(*number),
_ => None,
}
}
fn as_text(&self) -> Option<&str> {
match self {
Value::Text(text) => Some(text),
_ => None,
}
}
fn as_bool(&self) -> Option<bool> {
match self {
Value::Bool(value) => Some(*value),
_ => None,
}
}
fn get(&self, key: &str) -> Option<&Value> {
match self {
Value::Object(fields) => fields.iter().find(|(name, _)| name == key).map(|(_, value)| value),
_ => None,
}
}
fn index(&self, index: usize) -> Option<&Value> {
match self {
Value::Array(items) => items.get(index),
_ => None,
}
}
fn len(&self) -> usize {
match self {
Value::Array(items) => items.len(),
Value::Object(fields) => fields.len(),
_ => 0,
}
}
}
fn write_text(text: &str, out: &mut String) {
out.push('"\');
for c in text.chars() {
match c {
\'"' => out.push_str("\\\""),
\'\\\' => out.push_str("\\\\"),
\'\n\' => out.push_str("\\n"),
\'\r\' => out.push_str("\\r"),
\'\t\' => out.push_str("\\t"),
c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
other => out.push(other),
}
}
out.push(\'"');
}
fn write_compact(value: &Value, out: &mut String) {
match value {
Value::Null => out.push_str("null"),
Value::Bool(value) => out.push_str(if *value { "true" } else { "false" }),
Value::Number(number) => out.push_str(&format!("{number}")),
Value::Text(text) => write_text(text, out),
Value::Array(items) => {
out.push('[');
for (index, item) in items.iter().enumerate() {
if index > 0 {
out.push(',');
}
write_compact(item, out);
}
out.push(']');
}
Value::Object(fields) => {
out.push('{');
for (index, (key, item)) in fields.iter().enumerate() {
if index > 0 {
out.push(',');
}
write_text(key, out);
out.push(':');
write_compact(item, out);
}
out.push('}');
}
}
}
#[allow(dead_code)]
fn push_indent(level: usize, out: &mut String) {
for _ in 0..level {
out.push_str(" ");
}
}
#[allow(dead_code)]
fn write_pretty(value: &Value, level: usize, out: &mut String) {
match value {
Value::Array(items) if items.is_empty() => out.push_str("[]"),
Value::Array(items) => {
out.push_str("[\n");
for (index, item) in items.iter().enumerate() {
if index > 0 {
out.push_str(",\n");
}
push_indent(level + 1, out);
write_pretty(item, level + 1, out);
}
out.push('\n');
push_indent(level, out);
out.push(']');
}
Value::Object(fields) if fields.is_empty() => out.push_str("{}"),
Value::Object(fields) => {
out.push_str("{\n");
for (index, (key, item)) in fields.iter().enumerate() {
if index > 0 {
out.push_str(",\n");
}
push_indent(level + 1, out);
write_text(key, out);
out.push_str(": ");
write_pretty(item, level + 1, out);
}
out.push('\n');
push_indent(level, out);
out.push('}');
}
other => write_compact(other, out),
}
}
fn check(name: &str, ok: bool) -> bool {
if ok {
println!("ok {name}");
} else {
println!("FAILED {name}");
}
ok
}
#[allow(dead_code)]
fn shape(value: &Value) -> &'static str {
match value {
Value::Null => "Null",
Value::Bool(_) => "Bool",
Value::Number(_) => "Number",
Value::Text(_) => "Text",
Value::Array(_) => "Array",
Value::Object(_) => "Object",
}
}
fn main() {
let good = [
(r#"null"#, "Null"),
(r#"[1, 2, 3]"#, "Array"),
(r#"{"a": {"b": [true, false]}}"#, "Object"),
(r#""text""#, "Text"),
];
let mut failures = 0;
for (document, expected) in good {
match parse(document) {
Ok(value) => {
let mut out = String::new();
write_compact(&value, &mut out);
let round = parse(&out).map(|again| again == value).unwrap_or(false);
if !check(document, shape(&value) == expected && round) {
failures += 1;
}
}
Err(error) => {
println!("FAILED {document}: {error}");
failures += 1;
}
}
}
println!("{failures} failures");
}
rustc --edition 2024 good.rs
./good
ok null
ok [1, 2, 3]
ok {"a": {"b": [true, false]}}
ok "text"
0 failures
A table is data, so a row is added by writing a line rather than by writing a function, and the runner does not change when the table grows. The price is that every row runs in the same process and the first panic ends all of them, which is why the parser returns a Result instead of panicking and why this runner never needs to catch anything.
The document is the name of the test, which is why a failing row prints the text that broke it rather than a number. The shape function is four lines of match, and the six variants are the reason the compiler accepts it without a wildcard: a seventh variant would fail to build until the test knew about it.
The lesson on unit tests shows the same idea with #[test] and cargo test. The table here is a function so that the runner can be one program with no framework, which is what the C++ version of this capstone does with a CHECK macro.
A table of error messages
The runner is deliberately plain: a loop, a function that prints and returns the boolean, and a counter. A framework adds filtering, parallelism and a report format, and none of that changes the table, so the table is the part worth designing first.
An error message is part of the interface of a parser, so the table holds a fragment of the expected text rather than the whole message. The check is contains, which leaves the position free to change without breaking every row.
The four bad documents cover a missing colon, a truncated array, an unknown word and an unterminated string. Every row is expected to fail, and the runner reports a row that parses as a failure of its own.
#[derive(Debug, Clone, PartialEq)]
enum Token {
OpenBrace,
CloseBrace,
OpenBracket,
CloseBracket,
Colon,
Comma,
Text(String),
Number(f64),
Word(String),
End,
}
fn text_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
*position += 1;
let mut value = String::new();
while *position < bytes.len() && bytes[*position] != b'"\' {
let byte = bytes[*position];
if byte == b\'\\\' {
*position += 1;
match bytes.get(*position) {
Some(b\'"') => value.push('"\'),
Some(b\'\\\') => value.push(\'\\\'),
Some(b\'n\') => value.push(\'\n\'),
Some(b\'t\') => value.push(\'\t\'),
Some(b\'u\') => {
let digits = bytes.get(*position + 1..*position + 5)
.ok_or_else(|| format!("short unicode escape at {}", *position))?;
let hex = std::str::from_utf8(digits)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
let code = u32::from_str_radix(hex, 16)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
value.push(char::from_u32(code)
.ok_or_else(|| format!("bad code point at {}", *position))?);
*position += 4;
}
_ => return Err(format!("bad escape at {}", *position)),
}
} else {
value.push(byte as char);
}
*position += 1;
}
if *position == bytes.len() {
return Err(format!("unterminated text at {start}"));
}
*position += 1;
Ok(Token::Text(value))
}
fn number_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
while *position < bytes.len()
&& matches!(bytes[*position], b\'0\'..=b\'9\' | b\'-\' | b\'+\' | b\'.\' | b\'e\' | b\'E\')
{
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
match slice.parse() {
Ok(value) => Ok(Token::Number(value)),
Err(_) => Err(format!("bad number at {start}")),
}
}
fn word_token(bytes: &[u8], position: &mut usize) -> Token {
let start = *position;
while *position < bytes.len() && bytes[*position].is_ascii_alphabetic() {
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
Token::Word(slice.to_string())
}
fn tokenize(text: &str) -> Result<Vec<Token>, String> {
let bytes = text.as_bytes();
let mut position = 0;
let mut tokens = Vec::new();
loop {
while position < bytes.len() && bytes[position].is_ascii_whitespace() {
position += 1;
}
if position == bytes.len() {
tokens.push(Token::End);
return Ok(tokens);
}
let start = position;
let token = match bytes[position] {
b\'{\' => { position += 1; Token::OpenBrace }
b\'}\' => { position += 1; Token::CloseBrace }
b\'[\' => { position += 1; Token::OpenBracket }
b\']\' => { position += 1; Token::CloseBracket }
b\':\' => { position += 1; Token::Colon }
b\',\' => { position += 1; Token::Comma }
b\'"' => text_token(bytes, &mut position)?,
b'-' | b'0'..=b'9' => number_token(bytes, &mut position)?,
b'a'..=b'z' => word_token(bytes, &mut position),
other => return Err(format!("unexpected character \'{}\' at {start}", other as char)),
};
tokens.push(token);
}
}
#[derive(Debug, Clone, PartialEq)]
enum Value {
Null,
Bool(bool),
Number(f64),
Text(String),
Array(Vec<Value>),
Object(Vec<(String, Value)>),
}
struct Parser {
tokens: Vec<Token>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Parser {
Parser { tokens, position: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.position]
}
fn next(&mut self) -> Token {
let token = self.tokens[self.position].clone();
self.position += 1;
token
}
fn value(&mut self) -> Result<Value, String> {
match self.peek().clone() {
Token::OpenBrace => self.object(),
Token::OpenBracket => self.array(),
Token::Text(text) => {
self.next();
Ok(Value::Text(text))
}
Token::Number(number) => {
self.next();
Ok(Value::Number(number))
}
Token::Word(word) => {
self.next();
match word.as_str() {
"true" => Ok(Value::Bool(true)),
"false" => Ok(Value::Bool(false)),
"null" => Ok(Value::Null),
other => Err(format!("unknown word {other}")),
}
}
other => Err(format!("expected a value, found {other:?}")),
}
}
fn array(&mut self) -> Result<Value, String> {
self.next();
let mut items = Vec::new();
if matches!(self.peek(), Token::CloseBracket) {
self.next();
return Ok(Value::Array(items));
}
loop {
let value = self.value()?;
items.push(value);
match self.next() {
Token::Comma => continue,
Token::CloseBracket => return Ok(Value::Array(items)),
Token::End => return Err("document ended inside an array".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
fn object(&mut self) -> Result<Value, String> {
self.next();
let mut fields = Vec::new();
if matches!(self.peek(), Token::CloseBrace) {
self.next();
return Ok(Value::Object(fields));
}
loop {
let key = match self.next() {
Token::Text(text) => text,
other => return Err(format!("expected a key, found {other:?}")),
};
match self.next() {
Token::Colon => {}
other => return Err(format!("expected a colon, found {other:?}")),
}
let value = self.value()?;
fields.push((key, value));
match self.next() {
Token::Comma => continue,
Token::CloseBrace => return Ok(Value::Object(fields)),
Token::End => return Err("document ended inside an object".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
}
fn parse(text: &str) -> Result<Value, String> {
let tokens = tokenize(text)?;
let mut parser = Parser::new(tokens);
let value = parser.value()?;
match parser.peek() {
Token::End => Ok(value),
other => Err(format!("trailing token {other:?}")),
}
}
#[allow(dead_code)]
impl Value {
fn as_number(&self) -> Option<f64> {
match self {
Value::Number(number) => Some(*number),
_ => None,
}
}
fn as_text(&self) -> Option<&str> {
match self {
Value::Text(text) => Some(text),
_ => None,
}
}
fn as_bool(&self) -> Option<bool> {
match self {
Value::Bool(value) => Some(*value),
_ => None,
}
}
fn get(&self, key: &str) -> Option<&Value> {
match self {
Value::Object(fields) => fields.iter().find(|(name, _)| name == key).map(|(_, value)| value),
_ => None,
}
}
fn index(&self, index: usize) -> Option<&Value> {
match self {
Value::Array(items) => items.get(index),
_ => None,
}
}
fn len(&self) -> usize {
match self {
Value::Array(items) => items.len(),
Value::Object(fields) => fields.len(),
_ => 0,
}
}
}
#[allow(dead_code)]
fn write_text(text: &str, out: &mut String) {
out.push('"\');
for c in text.chars() {
match c {
\'"' => out.push_str("\\\""),
\'\\\' => out.push_str("\\\\"),
\'\n\' => out.push_str("\\n"),
\'\r\' => out.push_str("\\r"),
\'\t\' => out.push_str("\\t"),
c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
other => out.push(other),
}
}
out.push(\'"');
}
#[allow(dead_code)]
fn write_compact(value: &Value, out: &mut String) {
match value {
Value::Null => out.push_str("null"),
Value::Bool(value) => out.push_str(if *value { "true" } else { "false" }),
Value::Number(number) => out.push_str(&format!("{number}")),
Value::Text(text) => write_text(text, out),
Value::Array(items) => {
out.push('[');
for (index, item) in items.iter().enumerate() {
if index > 0 {
out.push(',');
}
write_compact(item, out);
}
out.push(']');
}
Value::Object(fields) => {
out.push('{');
for (index, (key, item)) in fields.iter().enumerate() {
if index > 0 {
out.push(',');
}
write_text(key, out);
out.push(':');
write_compact(item, out);
}
out.push('}');
}
}
}
#[allow(dead_code)]
fn push_indent(level: usize, out: &mut String) {
for _ in 0..level {
out.push_str(" ");
}
}
#[allow(dead_code)]
fn write_pretty(value: &Value, level: usize, out: &mut String) {
match value {
Value::Array(items) if items.is_empty() => out.push_str("[]"),
Value::Array(items) => {
out.push_str("[\n");
for (index, item) in items.iter().enumerate() {
if index > 0 {
out.push_str(",\n");
}
push_indent(level + 1, out);
write_pretty(item, level + 1, out);
}
out.push('\n');
push_indent(level, out);
out.push(']');
}
Value::Object(fields) if fields.is_empty() => out.push_str("{}"),
Value::Object(fields) => {
out.push_str("{\n");
for (index, (key, item)) in fields.iter().enumerate() {
if index > 0 {
out.push_str(",\n");
}
push_indent(level + 1, out);
write_text(key, out);
out.push_str(": ");
write_pretty(item, level + 1, out);
}
out.push('\n');
push_indent(level, out);
out.push('}');
}
other => write_compact(other, out),
}
}
fn check(name: &str, ok: bool) -> bool {
if ok {
println!("ok {name}");
} else {
println!("FAILED {name}");
}
ok
}
#[allow(dead_code)]
fn shape(value: &Value) -> &'static str {
match value {
Value::Null => "Null",
Value::Bool(_) => "Bool",
Value::Number(_) => "Number",
Value::Text(_) => "Text",
Value::Array(_) => "Array",
Value::Object(_) => "Object",
}
}
fn main() {
let bad = [
(r#"{"a" 1}"#, "expected a colon"),
(r#"[1, 2"#, "document ended inside an array"),
(r#"{"a": tru}"#, "unknown word tru"),
(r#""open"#, "unterminated text"),
];
let mut failures = 0;
for (document, expected) in bad {
match parse(document) {
Ok(_) => {
println!("FAILED {document}: parsed without an error");
failures += 1;
}
Err(error) => {
if !check(document, error.contains(expected)) {
println!(" got: {error}");
failures += 1;
}
}
}
}
println!("{failures} failures");
}
rustc --edition 2024 bad.rs
./bad
ok {"a" 1}
ok [1, 2
ok {"a": tru}
ok "open
0 failures
A row whose document parses is a failure even though no comparison ran, which is the second half of the table's value: the runner has an opinion about every row, and a parser that suddenly accepts "open is caught by the same code that checks the messages. Four rows pass, which means four documents are refused with the message the table expects. A table of bad documents is the part of a test suite that people skip, and it is the part that catches the parser which accepts everything: a runner that only checks good documents passes on a parser that returns Null for every input.
The lesson on assertions covers the macros a smaller test uses, and the lesson on error types shows how a message becomes a value with a kind and a position.
The test that fails
A test suite is only trusted after it has been seen to fail. The program below expects the wrong message on purpose: the document is missing a colon and the table asks for a comma. The runner prints the row, the message it got and the count.
#[derive(Debug, Clone, PartialEq)]
enum Token {
OpenBrace,
CloseBrace,
OpenBracket,
CloseBracket,
Colon,
Comma,
Text(String),
Number(f64),
Word(String),
End,
}
fn text_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
*position += 1;
let mut value = String::new();
while *position < bytes.len() && bytes[*position] != b'"\' {
let byte = bytes[*position];
if byte == b\'\\\' {
*position += 1;
match bytes.get(*position) {
Some(b\'"') => value.push('"\'),
Some(b\'\\\') => value.push(\'\\\'),
Some(b\'n\') => value.push(\'\n\'),
Some(b\'t\') => value.push(\'\t\'),
Some(b\'u\') => {
let digits = bytes.get(*position + 1..*position + 5)
.ok_or_else(|| format!("short unicode escape at {}", *position))?;
let hex = std::str::from_utf8(digits)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
let code = u32::from_str_radix(hex, 16)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
value.push(char::from_u32(code)
.ok_or_else(|| format!("bad code point at {}", *position))?);
*position += 4;
}
_ => return Err(format!("bad escape at {}", *position)),
}
} else {
value.push(byte as char);
}
*position += 1;
}
if *position == bytes.len() {
return Err(format!("unterminated text at {start}"));
}
*position += 1;
Ok(Token::Text(value))
}
fn number_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
while *position < bytes.len()
&& matches!(bytes[*position], b\'0\'..=b\'9\' | b\'-\' | b\'+\' | b\'.\' | b\'e\' | b\'E\')
{
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
match slice.parse() {
Ok(value) => Ok(Token::Number(value)),
Err(_) => Err(format!("bad number at {start}")),
}
}
fn word_token(bytes: &[u8], position: &mut usize) -> Token {
let start = *position;
while *position < bytes.len() && bytes[*position].is_ascii_alphabetic() {
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
Token::Word(slice.to_string())
}
fn tokenize(text: &str) -> Result<Vec<Token>, String> {
let bytes = text.as_bytes();
let mut position = 0;
let mut tokens = Vec::new();
loop {
while position < bytes.len() && bytes[position].is_ascii_whitespace() {
position += 1;
}
if position == bytes.len() {
tokens.push(Token::End);
return Ok(tokens);
}
let start = position;
let token = match bytes[position] {
b\'{\' => { position += 1; Token::OpenBrace }
b\'}\' => { position += 1; Token::CloseBrace }
b\'[\' => { position += 1; Token::OpenBracket }
b\']\' => { position += 1; Token::CloseBracket }
b\':\' => { position += 1; Token::Colon }
b\',\' => { position += 1; Token::Comma }
b\'"' => text_token(bytes, &mut position)?,
b'-' | b'0'..=b'9' => number_token(bytes, &mut position)?,
b'a'..=b'z' => word_token(bytes, &mut position),
other => return Err(format!("unexpected character \'{}\' at {start}", other as char)),
};
tokens.push(token);
}
}
#[derive(Debug, Clone, PartialEq)]
enum Value {
Null,
Bool(bool),
Number(f64),
Text(String),
Array(Vec<Value>),
Object(Vec<(String, Value)>),
}
struct Parser {
tokens: Vec<Token>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Parser {
Parser { tokens, position: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.position]
}
fn next(&mut self) -> Token {
let token = self.tokens[self.position].clone();
self.position += 1;
token
}
fn value(&mut self) -> Result<Value, String> {
match self.peek().clone() {
Token::OpenBrace => self.object(),
Token::OpenBracket => self.array(),
Token::Text(text) => {
self.next();
Ok(Value::Text(text))
}
Token::Number(number) => {
self.next();
Ok(Value::Number(number))
}
Token::Word(word) => {
self.next();
match word.as_str() {
"true" => Ok(Value::Bool(true)),
"false" => Ok(Value::Bool(false)),
"null" => Ok(Value::Null),
other => Err(format!("unknown word {other}")),
}
}
other => Err(format!("expected a value, found {other:?}")),
}
}
fn array(&mut self) -> Result<Value, String> {
self.next();
let mut items = Vec::new();
if matches!(self.peek(), Token::CloseBracket) {
self.next();
return Ok(Value::Array(items));
}
loop {
let value = self.value()?;
items.push(value);
match self.next() {
Token::Comma => continue,
Token::CloseBracket => return Ok(Value::Array(items)),
Token::End => return Err("document ended inside an array".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
fn object(&mut self) -> Result<Value, String> {
self.next();
let mut fields = Vec::new();
if matches!(self.peek(), Token::CloseBrace) {
self.next();
return Ok(Value::Object(fields));
}
loop {
let key = match self.next() {
Token::Text(text) => text,
other => return Err(format!("expected a key, found {other:?}")),
};
match self.next() {
Token::Colon => {}
other => return Err(format!("expected a colon, found {other:?}")),
}
let value = self.value()?;
fields.push((key, value));
match self.next() {
Token::Comma => continue,
Token::CloseBrace => return Ok(Value::Object(fields)),
Token::End => return Err("document ended inside an object".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
}
fn parse(text: &str) -> Result<Value, String> {
let tokens = tokenize(text)?;
let mut parser = Parser::new(tokens);
let value = parser.value()?;
match parser.peek() {
Token::End => Ok(value),
other => Err(format!("trailing token {other:?}")),
}
}
#[allow(dead_code)]
impl Value {
fn as_number(&self) -> Option<f64> {
match self {
Value::Number(number) => Some(*number),
_ => None,
}
}
fn as_text(&self) -> Option<&str> {
match self {
Value::Text(text) => Some(text),
_ => None,
}
}
fn as_bool(&self) -> Option<bool> {
match self {
Value::Bool(value) => Some(*value),
_ => None,
}
}
fn get(&self, key: &str) -> Option<&Value> {
match self {
Value::Object(fields) => fields.iter().find(|(name, _)| name == key).map(|(_, value)| value),
_ => None,
}
}
fn index(&self, index: usize) -> Option<&Value> {
match self {
Value::Array(items) => items.get(index),
_ => None,
}
}
fn len(&self) -> usize {
match self {
Value::Array(items) => items.len(),
Value::Object(fields) => fields.len(),
_ => 0,
}
}
}
#[allow(dead_code)]
fn write_text(text: &str, out: &mut String) {
out.push('"\');
for c in text.chars() {
match c {
\'"' => out.push_str("\\\""),
\'\\\' => out.push_str("\\\\"),
\'\n\' => out.push_str("\\n"),
\'\r\' => out.push_str("\\r"),
\'\t\' => out.push_str("\\t"),
c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
other => out.push(other),
}
}
out.push(\'"');
}
#[allow(dead_code)]
fn write_compact(value: &Value, out: &mut String) {
match value {
Value::Null => out.push_str("null"),
Value::Bool(value) => out.push_str(if *value { "true" } else { "false" }),
Value::Number(number) => out.push_str(&format!("{number}")),
Value::Text(text) => write_text(text, out),
Value::Array(items) => {
out.push('[');
for (index, item) in items.iter().enumerate() {
if index > 0 {
out.push(',');
}
write_compact(item, out);
}
out.push(']');
}
Value::Object(fields) => {
out.push('{');
for (index, (key, item)) in fields.iter().enumerate() {
if index > 0 {
out.push(',');
}
write_text(key, out);
out.push(':');
write_compact(item, out);
}
out.push('}');
}
}
}
#[allow(dead_code)]
fn push_indent(level: usize, out: &mut String) {
for _ in 0..level {
out.push_str(" ");
}
}
#[allow(dead_code)]
fn write_pretty(value: &Value, level: usize, out: &mut String) {
match value {
Value::Array(items) if items.is_empty() => out.push_str("[]"),
Value::Array(items) => {
out.push_str("[\n");
for (index, item) in items.iter().enumerate() {
if index > 0 {
out.push_str(",\n");
}
push_indent(level + 1, out);
write_pretty(item, level + 1, out);
}
out.push('\n');
push_indent(level, out);
out.push(']');
}
Value::Object(fields) if fields.is_empty() => out.push_str("{}"),
Value::Object(fields) => {
out.push_str("{\n");
for (index, (key, item)) in fields.iter().enumerate() {
if index > 0 {
out.push_str(",\n");
}
push_indent(level + 1, out);
write_text(key, out);
out.push_str(": ");
write_pretty(item, level + 1, out);
}
out.push('\n');
push_indent(level, out);
out.push('}');
}
other => write_compact(other, out),
}
}
fn check(name: &str, ok: bool) -> bool {
if ok {
println!("ok {name}");
} else {
println!("FAILED {name}");
}
ok
}
#[allow(dead_code)]
fn shape(value: &Value) -> &'static str {
match value {
Value::Null => "Null",
Value::Bool(_) => "Bool",
Value::Number(_) => "Number",
Value::Text(_) => "Text",
Value::Array(_) => "Array",
Value::Object(_) => "Object",
}
}
fn main() {
let bad = [(r#"{"a" 1}"#, "expected a comma")];
let mut failures = 0;
for (document, expected) in bad {
match parse(document) {
Ok(_) => {
println!("FAILED {document}: parsed without an error");
failures += 1;
}
Err(error) => {
if !check(document, error.contains(expected)) {
println!(" got: {error}");
failures += 1;
}
}
}
}
println!("{failures} failures");
}
rustc --edition 2024 fail.rs
./fail; echo "status $?"
FAILED {"a" 1}
got: expected a colon, found Number(1.0)
1 failures
status 0
The runner works: it names the row, prints what the parser said and counts one failure. The status is zero, which is the bug that the next section fixes: a pipeline that runs this program sees a success and lets a broken parser through.
Printing the message it got is the part that makes a failure cheap to diagnose. A runner that printed only the name of the row would leave the reader to run the parser by hand, which is exactly the work the table was meant to save.
The exit code the pipeline reads
main may return ExitCode, and the process status is what a shell, a makefile and a continuous integration job read. The runner returns ExitCode::FAILURE when a row fails, so the same program is a test and a check.
use std::process::ExitCode;
#[derive(Debug, Clone, PartialEq)]
enum Token {
OpenBrace,
CloseBrace,
OpenBracket,
CloseBracket,
Colon,
Comma,
Text(String),
Number(f64),
Word(String),
End,
}
fn text_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
*position += 1;
let mut value = String::new();
while *position < bytes.len() && bytes[*position] != b'"\' {
let byte = bytes[*position];
if byte == b\'\\\' {
*position += 1;
match bytes.get(*position) {
Some(b\'"') => value.push('"\'),
Some(b\'\\\') => value.push(\'\\\'),
Some(b\'n\') => value.push(\'\n\'),
Some(b\'t\') => value.push(\'\t\'),
Some(b\'u\') => {
let digits = bytes.get(*position + 1..*position + 5)
.ok_or_else(|| format!("short unicode escape at {}", *position))?;
let hex = std::str::from_utf8(digits)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
let code = u32::from_str_radix(hex, 16)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
value.push(char::from_u32(code)
.ok_or_else(|| format!("bad code point at {}", *position))?);
*position += 4;
}
_ => return Err(format!("bad escape at {}", *position)),
}
} else {
value.push(byte as char);
}
*position += 1;
}
if *position == bytes.len() {
return Err(format!("unterminated text at {start}"));
}
*position += 1;
Ok(Token::Text(value))
}
fn number_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
while *position < bytes.len()
&& matches!(bytes[*position], b\'0\'..=b\'9\' | b\'-\' | b\'+\' | b\'.\' | b\'e\' | b\'E\')
{
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
match slice.parse() {
Ok(value) => Ok(Token::Number(value)),
Err(_) => Err(format!("bad number at {start}")),
}
}
fn word_token(bytes: &[u8], position: &mut usize) -> Token {
let start = *position;
while *position < bytes.len() && bytes[*position].is_ascii_alphabetic() {
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
Token::Word(slice.to_string())
}
fn tokenize(text: &str) -> Result<Vec<Token>, String> {
let bytes = text.as_bytes();
let mut position = 0;
let mut tokens = Vec::new();
loop {
while position < bytes.len() && bytes[position].is_ascii_whitespace() {
position += 1;
}
if position == bytes.len() {
tokens.push(Token::End);
return Ok(tokens);
}
let start = position;
let token = match bytes[position] {
b\'{\' => { position += 1; Token::OpenBrace }
b\'}\' => { position += 1; Token::CloseBrace }
b\'[\' => { position += 1; Token::OpenBracket }
b\']\' => { position += 1; Token::CloseBracket }
b\':\' => { position += 1; Token::Colon }
b\',\' => { position += 1; Token::Comma }
b\'"' => text_token(bytes, &mut position)?,
b'-' | b'0'..=b'9' => number_token(bytes, &mut position)?,
b'a'..=b'z' => word_token(bytes, &mut position),
other => return Err(format!("unexpected character \'{}\' at {start}", other as char)),
};
tokens.push(token);
}
}
#[derive(Debug, Clone, PartialEq)]
enum Value {
Null,
Bool(bool),
Number(f64),
Text(String),
Array(Vec<Value>),
Object(Vec<(String, Value)>),
}
struct Parser {
tokens: Vec<Token>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Parser {
Parser { tokens, position: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.position]
}
fn next(&mut self) -> Token {
let token = self.tokens[self.position].clone();
self.position += 1;
token
}
fn value(&mut self) -> Result<Value, String> {
match self.peek().clone() {
Token::OpenBrace => self.object(),
Token::OpenBracket => self.array(),
Token::Text(text) => {
self.next();
Ok(Value::Text(text))
}
Token::Number(number) => {
self.next();
Ok(Value::Number(number))
}
Token::Word(word) => {
self.next();
match word.as_str() {
"true" => Ok(Value::Bool(true)),
"false" => Ok(Value::Bool(false)),
"null" => Ok(Value::Null),
other => Err(format!("unknown word {other}")),
}
}
other => Err(format!("expected a value, found {other:?}")),
}
}
fn array(&mut self) -> Result<Value, String> {
self.next();
let mut items = Vec::new();
if matches!(self.peek(), Token::CloseBracket) {
self.next();
return Ok(Value::Array(items));
}
loop {
let value = self.value()?;
items.push(value);
match self.next() {
Token::Comma => continue,
Token::CloseBracket => return Ok(Value::Array(items)),
Token::End => return Err("document ended inside an array".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
fn object(&mut self) -> Result<Value, String> {
self.next();
let mut fields = Vec::new();
if matches!(self.peek(), Token::CloseBrace) {
self.next();
return Ok(Value::Object(fields));
}
loop {
let key = match self.next() {
Token::Text(text) => text,
other => return Err(format!("expected a key, found {other:?}")),
};
match self.next() {
Token::Colon => {}
other => return Err(format!("expected a colon, found {other:?}")),
}
let value = self.value()?;
fields.push((key, value));
match self.next() {
Token::Comma => continue,
Token::CloseBrace => return Ok(Value::Object(fields)),
Token::End => return Err("document ended inside an object".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
}
fn parse(text: &str) -> Result<Value, String> {
let tokens = tokenize(text)?;
let mut parser = Parser::new(tokens);
let value = parser.value()?;
match parser.peek() {
Token::End => Ok(value),
other => Err(format!("trailing token {other:?}")),
}
}
#[allow(dead_code)]
impl Value {
fn as_number(&self) -> Option<f64> {
match self {
Value::Number(number) => Some(*number),
_ => None,
}
}
fn as_text(&self) -> Option<&str> {
match self {
Value::Text(text) => Some(text),
_ => None,
}
}
fn as_bool(&self) -> Option<bool> {
match self {
Value::Bool(value) => Some(*value),
_ => None,
}
}
fn get(&self, key: &str) -> Option<&Value> {
match self {
Value::Object(fields) => fields.iter().find(|(name, _)| name == key).map(|(_, value)| value),
_ => None,
}
}
fn index(&self, index: usize) -> Option<&Value> {
match self {
Value::Array(items) => items.get(index),
_ => None,
}
}
fn len(&self) -> usize {
match self {
Value::Array(items) => items.len(),
Value::Object(fields) => fields.len(),
_ => 0,
}
}
}
#[allow(dead_code)]
fn write_text(text: &str, out: &mut String) {
out.push('"\');
for c in text.chars() {
match c {
\'"' => out.push_str("\\\""),
\'\\\' => out.push_str("\\\\"),
\'\n\' => out.push_str("\\n"),
\'\r\' => out.push_str("\\r"),
\'\t\' => out.push_str("\\t"),
c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
other => out.push(other),
}
}
out.push(\'"');
}
#[allow(dead_code)]
fn write_compact(value: &Value, out: &mut String) {
match value {
Value::Null => out.push_str("null"),
Value::Bool(value) => out.push_str(if *value { "true" } else { "false" }),
Value::Number(number) => out.push_str(&format!("{number}")),
Value::Text(text) => write_text(text, out),
Value::Array(items) => {
out.push('[');
for (index, item) in items.iter().enumerate() {
if index > 0 {
out.push(',');
}
write_compact(item, out);
}
out.push(']');
}
Value::Object(fields) => {
out.push('{');
for (index, (key, item)) in fields.iter().enumerate() {
if index > 0 {
out.push(',');
}
write_text(key, out);
out.push(':');
write_compact(item, out);
}
out.push('}');
}
}
}
#[allow(dead_code)]
fn push_indent(level: usize, out: &mut String) {
for _ in 0..level {
out.push_str(" ");
}
}
#[allow(dead_code)]
fn write_pretty(value: &Value, level: usize, out: &mut String) {
match value {
Value::Array(items) if items.is_empty() => out.push_str("[]"),
Value::Array(items) => {
out.push_str("[\n");
for (index, item) in items.iter().enumerate() {
if index > 0 {
out.push_str(",\n");
}
push_indent(level + 1, out);
write_pretty(item, level + 1, out);
}
out.push('\n');
push_indent(level, out);
out.push(']');
}
Value::Object(fields) if fields.is_empty() => out.push_str("{}"),
Value::Object(fields) => {
out.push_str("{\n");
for (index, (key, item)) in fields.iter().enumerate() {
if index > 0 {
out.push_str(",\n");
}
push_indent(level + 1, out);
write_text(key, out);
out.push_str(": ");
write_pretty(item, level + 1, out);
}
out.push('\n');
push_indent(level, out);
out.push('}');
}
other => write_compact(other, out),
}
}
fn check(name: &str, ok: bool) -> bool {
if ok {
println!("ok {name}");
} else {
println!("FAILED {name}");
}
ok
}
#[allow(dead_code)]
fn shape(value: &Value) -> &'static str {
match value {
Value::Null => "Null",
Value::Bool(_) => "Bool",
Value::Number(_) => "Number",
Value::Text(_) => "Text",
Value::Array(_) => "Array",
Value::Object(_) => "Object",
}
}
fn main() -> ExitCode {
let bad = [(r#"{"a" 1}"#, "expected a comma")];
let mut failures = 0;
for (document, expected) in bad {
match parse(document) {
Ok(_) => {
println!("FAILED {document}: parsed without an error");
failures += 1;
}
Err(error) => {
if !check(document, error.contains(expected)) {
println!(" got: {error}");
failures += 1;
}
}
}
}
println!("{failures} failures");
if failures == 0 {
ExitCode::SUCCESS
} else {
ExitCode::FAILURE
}
}
rustc --edition 2024 exit.rs
./exit; echo "status $?"
FAILED {"a" 1}
got: expected a colon, found Number(1.0)
1 failures
status 1
A continuous integration job runs the program and reads nothing but the status, so the count line is for the person who opens the log and the status is for the machine. The program prints the same lines and now exits with one, which is the whole difference between a report and a check. The lesson on exit codes covers the type in a command-line program, and the next lesson starts the second capstone with a data model that its own tests can use.
Exercises
- Add a row with a number in exponent form and one with a deeply nested array.
- Make the runner stop at the first failure and print the remaining count.
- Add a table of documents that the writer produces and that the parser must read back unchanged.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why does the good table check the shape of the tree rather than the whole value?
Answer
The shape is enough to prove the variant and does not freeze every number in the test
A shape check is stable when a number or a key changes; the round trip covers the rest.
-
Why does the bad table hold a fragment of the message?
Answer
The position and the found token may change without breaking the row
contains checks the part the interface promises and leaves the details free.
-
Why is a table of bad documents necessary?
Answer
A parser that accepts everything passes a table of good documents
Only a refused document proves that the parser has rules at all.
-
What does the exit code add to a test runner?
Answer
A pipeline can see the failure without reading the output
ExitCode::FAILURE becomes status 1, which make and CI treat as a failure.
-
Why does the failing table print the message it got?
Answer
To make the failure diagnosable without a second run
The actual message is the fact the reader needs to fix the row or the parser.
-
What does this program print?
fn check(name: &str, ok: bool) -> bool { println!("{} {}", if ok { "ok" } else { "FAILED" }, name); ok } fn main() { let mut failures = 0; for (name, value) in [("a", 2), ("b", 3), ("c", 4)] { if !check(name, value % 2 == 0) { failures += 1; } } println!("{failures} failures"); }Answer
ok a / FAILED b / ok c / 1 failures
Two and four are even and three is not, so one row fails.
-
What does this program print?
fn main() { let table = [("null", true), ("[]", true), ("{", false), ("[1, 2", false)]; let mut failures = 0; for (document, should_parse) in table { let parsed = document.starts_with('[') && document.ends_with(']'); if parsed != should_parse { failures += 1; println!("FAILED {document}"); } } println!("{failures} failures"); }Answer
FAILED null / 1 failures
The stub parser accepts only bracketed text, so null and the open brace disagree with the table.
-
What does this program print?
use std::process::ExitCode; fn main() -> ExitCode { let rows = [("a", true), ("b", false)]; let failures = rows.iter().filter(|(_, ok)| !ok).count(); if failures == 0 { ExitCode::SUCCESS } else { println!("{failures} failures"); ExitCode::FAILURE } }Answer
1 failures
One row fails and the count is printed; the returned ExitCode then becomes status 1.
-
What does this program print?
fn shape(text: &str) -> &'static str { match text { "" => "empty", t if t.starts_with('[') => "array", t if t.starts_with('{') => "object", _ => "scalar", } } fn main() { let documents = ["[]", "{}", "1", ""]; let names: Vec<&str> = documents.iter().map(|d| shape(d)).collect(); println!("{}", names.join(",")); }Answer
array,object,scalar,empty
The match tests the empty string first, then the two brackets, and the number is a scalar.
-
What does this program print?
fn main() { let document = "{\"a\": [1, 2}"; let mut stack: Vec<char> = Vec::new(); let mut ok = true; for c in document.chars() { match c { '{' => stack.push('}'), '[' => stack.push(']'), '}' | ']' => { if stack.pop() != Some(c) { ok = false; break; } } _ => {} } } println!("{} {}", ok, stack.len()); }Answer
false 1
The brace arrives while an array bracket is open, so the check fails and one expectation stays.
The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev