Capstone 1: writing JSON
Writing JSON is reading it backwards, with one extra rule: some characters cannot appear inside a string in their raw form. A quote would end the string, a backslash would start an escape, and a newline would break the line the format is built on. The writer turns each of them into two characters, and the parser turns them back.
This lesson adds the escape table, a writer that indents two spaces per level, a round trip that proves the two directions agree, and the version of the writer that forgets one escape and produces a document no parser accepts.
The escape table
One function writes a text value and one writes a whole value, and the second calls the first for every key and every string. The escape match has an arm for the four characters JSON names and a guard for every other control character, which is written as \u and four hex digits.
The program parses a document whose string contains a newline escape, a tab, a quote, a backslash and the control character one, then writes it back in compact form. The debug print of the value shows what the parser stored.
#[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('}');
}
}
}
fn main() {
let value = parse(r#""line\nnext\ttab \"quote\" \\ end\u0001""#).unwrap();
let mut out = String::new();
write_compact(&value, &mut out);
println!("{out}");
println!("{:?}", value);
}
rustc --edition 2024 escape.rs
./escape
"line\nnext\ttab \"quote\" \\ end\u0001"
Text("line\nnext\ttab \"quote\" \\ end\u{1}")
The two lines carry the same text: the first is JSON and the second is the Rust debug format, and both write one backslash for each of the two in the source. The control character is the reason the guard exists; a JSON document may contain it only as \u0001, while the writer of a C program would put the raw byte in the file and most readers would refuse the document.
One detail of the table is easy to miss: the escape is applied to the value, not to the source. A text that already contains the two characters backslash and n stays that way on the way out, because the writer sees one backslash and writes two. The escape table is the one place where the writer can be wrong, and it is small enough to test exhaustively. The lesson on characters covers the code point behind the u32 comparison, and formatting covers the {:04x} that pads the hex number to four digits.
Indentation and the recursive writer
A serializer also has to decide what it does with a value it cannot represent. JSON has no bare NaN and no infinity, so a program that writes a float has to map both to null or to a string, and the writer is the place where that decision is made once. The pretty form is the same writer with two changes: a level counter, and a newline with indentation before every element. An empty array and an empty object stay on one line, because [] and {} read better than two lines with nothing between them.
The program writes a small configuration with a nested object and both kinds of empty container. The output is the text a person reads and a program could still parse.
#[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('}');
}
}
}
fn push_indent(level: usize, out: &mut String) {
for _ in 0..level {
out.push_str(" ");
}
}
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 main() {
let document = r#"{"name": "rust", "tags": ["fast", "safe"], "nested": {"empty": {}, "list": []}}"#;
let value = parse(document).unwrap();
let mut out = String::new();
write_pretty(&value, 0, &mut out);
println!("{out}");
}
rustc --edition 2024 pretty.rs
./pretty
{
"name": "rust",
"tags": [
"fast",
"safe"
],
"nested": {
"empty": {},
"list": []
}
}
The empty containers appear on one line and the nested ones open onto their own lines, which is the rule the whole function encodes. The level is passed by value, so the recursion does not need a mutable counter and the writer has no state between calls.
A pretty writer is a debugging and documentation tool; a program that sends a document over a socket uses the compact form, because the indentation is bytes that the reader throws away. The lesson on text files covers writing either form to disk.
A round trip through the writer
The test of a serializer is that the parser reads what it wrote. The program writes the same value twice, in both forms, parses each result and compares it with the original tree. It also prints the two lengths, which shows how much the indentation costs.
#[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('}');
}
}
}
fn push_indent(level: usize, out: &mut String) {
for _ in 0..level {
out.push_str(" ");
}
}
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 main() {
let document = r#"{"name": "rust", "tags": ["fast", "safe"], "note": "a \"b\"\\nc", "empty": {}}"#;
let value = parse(document).unwrap();
let mut compact = String::new();
write_compact(&value, &mut compact);
let mut pretty = String::new();
write_pretty(&value, 0, &mut pretty);
println!("{}", parse(&compact).unwrap() == value);
println!("{}", parse(&pretty).unwrap() == value);
println!("{} {}", compact.len(), pretty.len());
}
rustc --edition 2024 roundtrip.rs
./roundtrip
true
true
70 100
Both forms parse back to an equal tree, which is the property the writer has to keep: the indentation is cosmetic and the compact form is not, because both are the same document to a parser. The thirty bytes of difference are the newlines and the spaces, and a large configuration pays them once per save.
A round trip does not prove that the text is valid JSON in every detail, only that this parser accepts it. The next lesson adds a table of documents taken from other writers, which is how a format implementation catches the cases its own writer never produces.
The escape that was forgotten
Removing the arm for the quote is the smallest change that breaks the format. The writer puts the text between quotes, a quote inside the text ends the string early, and the rest of the document is read as something else.
The program below is the same file with that one arm deleted. It parses a text with a quote in it, writes it back and asks the parser whether the result reads.
#[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("\\\\"),
\'\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('}');
}
}
}
fn main() {
let value = parse(r#""a\"b""#).unwrap();
let mut out = String::new();
write_compact(&value, &mut out);
println!("{out}");
println!("{}", parse(&out).is_ok());
}
rustc --edition 2024 broken.rs
./broken
"a"b"
false
A reader that accepts the text would have built a document that means something else, which is worse than a refused document: the output has three quotes where JSON allows two, and the parser refuses the text, which is the good outcome: a reader that accepted it would build a document that means something else. The comparison with the first section shows the whole value of the table: one arm covers a character that appears in almost every real document.
The exercise of the next lesson, a table of documents, is how a writer is checked: a text with a quote, a text with a backslash, an empty object, an empty array, a deep nesting and a number in exponent form. The next lesson builds that table and a runner for it.
Exercises
- Add the \/ escape on the way out and check that the parser accepts both forms on the way in.
- Make the indentation width a parameter of write_pretty and print the same document with four spaces per level.
- Write a text with every byte from zero to thirty-one and round-trip it.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why must a quote inside a text be escaped?
Answer
Because a raw quote would end the string early
The string starts and ends with a quote, so a quote inside it has to be marked.
-
How is a control character written in JSON?
Answer
As
\uand four hex digitsThe format allows the raw byte only for the printable range; the rest uses the unicode escape.
-
Why are empty containers written on one line?
Answer
[]and{}are shorter and clearer than two lines with nothing between themIt is a style decision of the pretty writer, and both forms parse the same.
-
What does the round trip prove?
Answer
That this parser reads what this writer wrote
It compares the tree with itself, so it checks the pair and not the whole format.
-
Why does the writer take a level counter instead of building the indentation string once?
Answer
The counter is passed by value, so the recursion keeps no state and copies nothing
The level is a number, and the indentation is pushed only when a line starts.
-
What does this program print?
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"), other => out.push(other), } } out.push('"'); } fn main() { let mut out = String::new(); write_text("a\"b\\nc", &mut out); println!("{out}"); }Answer
"a\"b\\nc"
The quote and the backslash each gain one backslash, and the letters n and c stay.
-
What does this program print?
fn push_indent(level: usize, out: &mut String) { for _ in 0..level { out.push_str(" "); } } fn main() { let mut out = String::new(); for level in 0..3 { push_indent(level, &mut out); out.push('x'); out.push('\n'); } print!("{out}"); }Answer
x / x / x
Each level adds two spaces, and the loop runs for zero, one and two.
-
What does this program print?
fn main() { let mut out = String::new(); let fields = [("a", 1), ("b", 2)]; out.push('{'); for (index, (key, value)) in fields.iter().enumerate() { if index > 0 { out.push(','); } out.push_str(&format!("\"{key}\":{value}")); } out.push('}'); println!("{out}"); }Answer
{"a":1,"b":2}
The commas go between the pairs, and the braces wrap the whole object.
-
What does this program print?
fn main() { let document = r#"{"a": [], "b": {}}"#; let mut depth = 0; let mut max_depth = 0; for c in document.chars() { match c { '[' | '{' => { depth += 1; if depth > max_depth { max_depth = depth; } } ']' | '}' => depth -= 1, _ => {} } } println!("{max_depth} {depth}"); }Answer
2 0
The object opens, its two empty containers open one at a time, and everything closes.
-
What does this program print?
fn main() { let text = "a\tb"; let mut out = String::new(); for c in text.chars() { match c { '\t' => out.push_str("\\t"), other => out.push(other), } } println!("{} {}", out.len(), out.contains('\t')); }Answer
4 false
The tab becomes two characters, so the text is four bytes and holds no raw tab.
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