Rust coding challenge - JSON parser

Table of Contents

• Prologue
• TL;DR:
• Challenge
• Specifications
• High level design
• High level diagram of parser
• Reading from file
• Tokenization
• Handling buffered read
• Buffer boundaries
• Tokenizer as an Iterator
• Token state
• String
  • String case: Unicode escape
  • Unicode edge case: Surrogate pairs - 🚀😀😭
• Number
• Number case: Integers
• Number case: Exponent
• Number case: Fraction
• Keywords
• Handling EOF
• Parser - Endgame
• Nesting limit
• Unit testing and coverage
• References

Prologue

---

As a part of coding challenges that I am working on the side, the second challenge was to build a JSON parser, this was my very first attempt to build a parser, let alone in Rust. But once I have built it, I can say that parsers are nothing but stateful pattern matching, that’s it. While parsers themselves are nothing new, they have been written since as early as 50s and 60s, over time it has become an almost invisible component of our daily tools.

We take them for granted, and they are either buried deep behind visual design layers, user interfaces. Any time a machine needs to understand structured text, data or code, a parser is at work behind the scenes.

1. Web browsers - HTML, CSS and JavaScript parsers turn plain code into dynamic pages.
2. Programming languages - Compilers and interpreters parse source code into a tree structures before running it.
3. Network traffic - Routers and firewalls parse packet headers to direct internet traffic securely.
4. Command lines - Shells parse text commands and flags, do file resolution based on paths and execute system commands.
5. Database systems - Parse database queries to optimize and retrieve data.

and many more…

While each parser will be different in its implementation, the core ideas stay the same across all implementations.

TL;DR:

---

All the links to the code who think talk is cheap, show me the code

• Coding Challenge #2: Build your JSON parser
• Code here

Challenge

---

The challenge is to build your own JSON parser.

Idea is to take in a user input string either from a file or stream, and parse it and make it available in the target language as data. Here I have decided to choose Rust as my target language.

Input:

{
  "name": "Flying Zebra",
  "job": "Writer"
}

We can expect output to be of the form:

Output:

JsonValue::Object(HashMap::from([("name".to_string(), "Flying Zebra".to_string()),("job".to_string(), "Writer".to_string())]))

An enum type enclosing a hashmap with key and values matching the input, along with handling valid input types, it should be able to handle invalid user inputs gracefully and throw meaningful errors, that highlight line and col which point where the error might be to the user.

Specifications

---

JSON(which stands for JavaScript Object Notation) is a lightweight data-interchange format, which is widely used for transmitting data over the internet.

• IETF JSON specification std90
• Helpful graphical visualization of JSON specification

High level design

---

Parsing is often broken up into two stages:

1. Lexical analysis (aka Tokenization),
2. Syntactic analysis (aka Grammar check)

Lexical analysis or tokenization is the very first and crucial step of handling user input, you are dealing with a string and picking out components that might form a valid data structure, these components are called tokens. During tokenization you are concerned if its possible to form valid tokens out of given user input.

Syntactic analysis or grammar check is the next level of parsing, where you are concerned if the tokens generated as part of tokenization process make sense syntactically, do they follow valid grammar of JSON.

For example,

}{

Tokenization will produce two valid tokens, although we know its not valid object in JSON, that would be job of the next stage of parser (aka grammar check stage) to find out.

This separation is crucial and necessary for almost any parser you are going to build, and this is because you can’t know if the grammar is valid or not unless you have enough context surrounding the current token you are looking at, parsing of such structures do require retention of state, and look ahead, to know if the overall structure makes sense.

High level diagram of parser

---

  [Parser.parse()]
        |
        |
        |
        V
  [Tokenizer.next()] -> We turn tokenizer into an iterator
        |
        |
        |
        V
  [Reads raw bytes from the BufReader, builds valid tokens] -> Tokenizer needs to manage split tokens across buffers,
        |                                                      token state
        |
        |
        V
  [Returns `Some(Ok(JsonToken))`] -> Iterator returns one token at a time
        |
        |
        |
        V
  [Parser receives a token] -> updates its syntax state, loops back to step 1 until we reach end of the content or error.

Reading from file

---

    let file_name = args_os()
        .skip(1)
        .take(1)
        .next()
        .expect("Please provide a file path with json");

    let file =
        File::open(&file_name).expect("Failed to open the file, please enter a valid file path");
    let reader = BufReader::new(file);

Just good old code to take in a path from the cli,

> ./json-parser tests/valid.json

BufReader takes in a value that implements Read trait, that could include file, network stream, or stdio, even slices ! This is extremely useful for programs like mine since I can avoid reading large amount of data in memory, by default, BufReader will take in a certain chunk size of data (8 KB) and keep it in local memory and when the program reads from buf reader, it will read from the local memory instead of source and reduce system calls.

This will make perfect sense as we want to read enough memory from the reader to create a single token at a time, and avoid reading from data all at once. This makes our parser extremely memory efficient.

Tokenization

---

Tokenization is process of taking in user input in this case a string input, and turning that into units that form a unit within the constraints of the grammar of the language for which you are writing a parser for.

What is that unit in JSON ? We need to look at spec to understand this,

Typically a value in JSON is represented as either of these,

1. Object
2. Array
3. number
4. true
5. false
6. null
7. string

and the structures like object and array can be nested

Further, each value is codified with following constraints,

1. Object

{ [whitespace] [key should be a string] [whitespace] :
  [whitespace] [value] [whitespace] (comma , as separator)
}

2. Array

[ [whitespace] [value] [whitespace] (comma , as a separator) ]

3. Strings

[Quote][any codepoint except " or  or control characters]
[ when using  it should be followed by ", ,/,b,f,n,r,t, u<4 hex digits>]
[Quote]

4. Number - Is like a number except that hexadecimal or octal formats are not used. This one is a bit loose on purpose, but we will see its complexity down the line.
5. Whitespace - Can be inserted between any tokens (whitespace includes space, linefeed, carriage return, horizontal tab)

So based on above information, now I want to decide tokens,

For primitives, and keywords,

if my input is

1. a string -> token::string()
2. a number -> token::number()
3. true || false || null -> token::bool() or token::null

Now for objects and arrays I cannot have a token type as token::object or token::array -> this is because a token should constitute a valid unit, which is not possible to tell without looking at the rest of string first.

So we work around it and look at the shape of an object and decide what constitutes an object

{ "name": "Flying Zebra", "hobby": "Writing" }

Above is an example of a valid object, looking at it we know an object is bound by a left and a right brace, and string keys, colon (:) as a separator between these key and value pair, and comma (,) as a separator between these key value pairs.

So we tokenize the bounds and separators that will be valid in an object, and same is true for arrays as well, only difference is we have left and right square brackets and separator is comma.

#[derive(Debug, PartialEq)]
enum PairStart {
    LeftBrace,
    LeftBracket,
}

#[derive(Debug, PartialEq)]
enum PairEnd {
    RightBrace,
    RightBracket,
}

#[derive(Debug, PartialEq)]
enum Delimiter {
    Colon,
    Comma,
}

#[derive(Debug, PartialEq)]
enum Literal {
    String(String),
    Number(f64),
    Bool(bool),
    Null,
}

#[derive(Debug, PartialEq)]
enum JsonToken {
    PairStart(PairStart),
    PairClose(PairEnd),
    Delimiter(Delimiter),
    Literal(Literal),
}

So I create this nice separation between different types of tokens, interesting part of tokenization is we are technically creating a linear list of tokens and don’t need to care about nesting yet, we maintain the user input integrity with list of tokens, but difference is that we strip away unnecessary stuff from user input (whitespace), convert raw string data to JSON representation of data units.

Apart from dubious naming convention for PairStart and PairEnd, there is one more point that is worth noting that is capping number to a f64 precision, since JSON itself does not limit precision to a particular limit, its left up to the parsers (implementations) to implement that or handle that as they see fit, which is such a curve ball, given that computers are really bad at handling precisions beyond a limit say 2^53.

What this means for a number with or without decimal point is that a number in f64 can be represented accurately with around 15 to 17 digits and then starts losing precision (numbers is rounded off for further digits).

If beyond that precision is required to be maintained, maybe this JSON parser will not work for you. But then again I would suggest people to use strings to retain that precision and not rely on parsers at all, seems like an edge case but worth mentioning nonetheless.

What f64 means in Rust ?

1 bit -> sign (+ / -)
11 bit -> exponent (digits of exponent, for example. 2^(exponent)
52 bit -> mantissa

This limitation is not unique to my tokenizer or parser, even JSON.parse() in JavaScript faces this issue.

This was a real problem in JS btw, solution is simple enough to send such long numbers as strings, and not be dependent on target parsers to retain precisions. Snowflake id 53 bit problem

Handling buffered read

---

I rely on fill_buf() and consume() to read efficiently from a file, these apis help me read a fairly large file efficiently by avoiding repeated system calls to Read.

I could maintain a Vec<JsonToken> but that will grow proportionally in relation to user input, and we lose any advantage that we gain by buffered read, instead I decided to implement an iterator for a tokenizer, which is something known as lazy evaluation in programming paradigms.

Why lazy evaluation or implement an iterator ?

Idea is simple fill_buf() fills roughly 8 KB of data and stores in local memory - so that is read optimization, a parser will need tokens to check if the structure of the input JSON is valid, this can be either done by giving a list of all tokens all at once or one token at a time, advantage of second approach is we are incrementally reading, generating tokens and also parsing those tokens, so we will have an fairly low memory footprint throughout the execution of the program.

Parser pulls in a token from tokenizer and tokenizer yields a single token at a time.

What we get is a streaming parser, so by the time we are done reading the input, we will have a valid JSON representation of input JSON in Rust. That’s the beauty of this implementation. I would not compare this to any production grade json parsers for obvious reasons that this has been developed by someone learning Rust and writing a parser first time, so I don’t know what I don’t know what it takes to build a production grade parser, I have not optimized anything. My focus was implementation of spec and passing the tests I set forth and the ones mentioned in the coding challenges.

Buffer boundaries

---

Buffer is like a vector of u8 along with some state to track where you are in a file or a stream, Each read is a system call which is expensive, to avoid multiple system calls while reading from a file, we take a chunk out of it, let’s say 8KB and we keep it in local memory and read from it which eliminates the system calls.

But doing so comes with its own challenges, it might be possible a long enough string or value might be split between two different buffers.

In that case you need to hold a state / accumulate what you have already read in a local state to avoid loss of data.

struct Tokenizer<R: BufRead> {
    col: usize, // current col at which we are reading the byte
    line: usize, // current line at which we are reading the byte
    reader: R, // the buffer reader
    scratch: Vec<u8>, // intermediate state to hold values between iterations or buffer boundaries
    state: TokenState, // current reading state
}

Tokenizer as an Iterator

---

Implementing an iterator for tokenizer can be done as per the following code:

impl<R: BufRead> Iterator for Tokenizer<R> {
    type Item = std::io::Result<JsonToken>

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let buffer = self.reader.fill_buf().ok()?;

            let mut consume_amt=0;
            let buff_len = buffer.len();

            if buffer.is_empty() {
                /*handle pending values in scratch, throw error for invalid state on EOF*/
            }

            while consume_amt < buff_len {
                let b = buffer[consume_amt];

                match self.state {
                    /*Token state matching against the current byte we are reading*/
                    TokenState::Idle => match b {
                        /*match conditions for start of tokens or token themselves*/
                        b'{' => {
                            self.col += 1;
                            consume_amt += 1;
                            self.reader.consume(consume_amt);
                            return Some(Ok(JsonToken::PairStart(PairStart::LeftBrace)));
                        }
                    }
                }
            }
            self.reader.consume(consume_amt);
        }
    }
}

Iterator makes sense given that we only want to ever produce a token when its needed by parser, this makes a perfect use case for an iterator, parser requests for a token and tokenizer reads enough from buffer to produce a token and yield it to the parser.

Parser can own the tokenizer and do this simply

for token_result in tokenizer.by_ref() {
    let token = token_result?;

    /*process token*/ 
}

Token state

---

#[derive(Copy, Clone)]
enum TokenState {
    Idle,
    InKeyword { state: ExpectKeywordState }, // true, false, null
    InNumber { state: NumberState },             // 1.0e-002, 1.0e000000000022222, -0.0, +0.0,1.
    InString { escaped: bool },
    InUnicodeEscape { collected: [u8; 4], count: usize },
    ExpectLowSurrogate { state: SurrogatePairState },
}

Token state will switch between above states, TokenState::Idle is essentially a state you see during start or you would want to transition into once you are done generating a token.

Idle state is used to find out out next token type in case of brackets, or delimiters, returning a token from idle state is common.

let b = buffer[consume_amt];
TokenState::Idle => match b {
    b'{' => {
        self.col += 1;
        consume_amt += 1;
        self.reader.consume(consume_amt);
        return Some(Ok(JsonToken::PairStart(PairStart::LeftBrace)));
    }
    b'}' => {
        self.col += 1;
        consume_amt += 1;
        self.reader.consume(consume_amt);
        return Some(Ok(JsonToken::PairClose(PairEnd::RightBrace)));
    }
    b'[' => {
        self.col += 1;
        consume_amt += 1;
        self.reader.consume(consume_amt);
        return Some(Ok(JsonToken::PairStart(PairStart::LeftBracket)));
    }
    b']' => {
        self.col += 1;
        consume_amt += 1;
        self.reader.consume(consume_amt);
        return Some(Ok(JsonToken::PairClose(PairEnd::RightBracket)));
    }
    b':' => {
        self.col += 1;
        consume_amt += 1;
        self.reader.consume(consume_amt);
        return Some(Ok(JsonToken::Delimiter(Delimiter::Colon)));
    }
    b',' => {
        self.col += 1;
        consume_amt += 1;
        self.reader.consume(consume_amt);
        return Some(Ok(JsonToken::Delimiter(Delimiter::Comma)));
    }
    b' ' | b'\t' | b'\r' => {
        // for radical simplicity, and to keep my head intact
        // I am not getting into text parsing for damn json parser, sorry
        // that's a scope creep
        self.col += 1;
        consume_amt += 1;
    }
    b'\n' => {
        self.line += 1;
        // reset col to make sure it increments to 1 on next line
        self.col = 0;
        consume_amt += 1;
    }
    b't' => {
        self.col += 1;
        consume_amt += 1;
        self.scratch.push(b);
        self.state = TokenState::InKeyword {
            state: ExpectKeywordState::True,
        };
    }
    b'f' => {
        self.col += 1;
        consume_amt += 1;
        self.scratch.push(b);
        self.state = TokenState::InKeyword {
            state: ExpectKeywordState::False,
        };
    }
    b'n' => {
        self.col += 1;
        consume_amt += 1;
        self.scratch.push(b);
        self.state = TokenState::InKeyword {
            state: ExpectKeywordState::Null,
        };
    }
    b'-' => {
        self.col += 1;
        consume_amt += 1;
        self.scratch.push(b);
        self.state = TokenState::InNumber {
            state: NumberState::LeadingMinus,
        };
    }
    b'0'..=b'9' => {
        self.col += 1;
        consume_amt += 1;
        self.scratch.push(b);
        self.state = TokenState::InNumber {
            state: if b == b'0' {
                NumberState::LeadingZero
            } else {
                NumberState::Integer
            },
        }
    }
    b'"' => {
        self.col += 1;
        consume_amt += 1;
        self.state = TokenState::InString { escaped: false };
    }
    _ => {
        self.col += 1;
        consume_amt += 1;
        self.reader.consume(consume_amt);
        let error_message =
            format!("Invalid symbol at line:{},col:{}", self.line, self.col);
        return Some(Err(Error::new(ErrorKind::InvalidData, error_message)));
    }
}

Certain edge cases like +1 gets handled here as an error, since we can’t have + as sign before a number, well before we get into parsing, along with any edge cases that can have any weird symbols or notations at the start of token.

There are certain token types that we simply cannot rely a single byte to form a token, these include

• String
• Number
• Keywords

String and Number types more or less rule the JSON tokenizer, almost 90% of the code in the tokenizer will be handling string specific sub states or number specific states. I break them down below in great detail.

String

---

#[derive(Copy, Clone)]
enum TokenState {
    Idle,
    InKeyword { state: ExpectKeywordState, last: u8 }, // true, false, null
    InNumber { state: NumberState },             // 1.0e-002, 1.0e000000000022222, -0.0, 0, 0.1
    InString { escaped: bool },
    InUnicodeEscape { collected: [u8; 4], count: usize },
    ExpectLowSurrogate { state: SurrogatePairState },
}

match self.state {
TokenState::Idle => match b {
        b'"' => {
            self.col += 1;
            consume_amt += 1;
            self.state = TokenState::InString { escaped: false };
        }
    }
}

Quotes mark boundaries of the string in JSON (For ex. "Flying Zebra"), so we match for a byte that corresponds to a quotation mark and transition to a InString state.

We are using enums here, and since enums can hold data, its making my life easier to manage sub states of string. A string itself can have multiple sub states,

1. Good old regular characters in string - escaped = false
2. we see a backslash in string (\) - escaped = true
   1. Either a escape character (\b, \n, \t, \r) or
   2. a unicode (\u83D8)

Since the enum can hold that data of whether we seen the escape character or not and mark the transition into sub states, we don’t need any more variables to manage that, which is just 🤌

TokenState::InString { escaped } => {
    if escaped {
        match b {
            b'"' => {
                self.col += 1;
                consume_amt += 1;
                self.scratch.push(b);
                self.state = TokenState::InString { escaped: false }
            }
            b'\\' => {}
            b'/' => {}
            b'b' => {}
            b'f' => {}
            b'u' => {
                self.col += 1;
                consume_amt += 1;
                self.state = TokenState::InUnicodeEscape {
                    collected: [0u8; 4],
                    count: 0,
                };
                break;
                
            }
            b'n' => {}
            b't' => {}
            b'r' => {}
            _ => {}
        }
    } else {
        match b {
            b'\\' => {
                self.col += 1;
                consume_amt += 1;
                self.state = TokenState::InString { escaped: true }
                
            }
            0x00..=0x1F => {
                self.col += 1;
                consume_amt += 1;
                self.reader.consume(consume_amt);
                return Some(Err(Error::new(
                    ErrorKind::InvalidData,
                    format!(
                        "Illegal character {} at line:{} at col:{}",
                        b.to_ascii_lowercase(),
                        self.line,
                        self.col
                    ),
                )));
            }
            b'"' => {
            self.col += 1;
            consume_amt += 1;
            self.reader.consume(consume_amt);
            match String::from_utf8(std::mem::take(&mut self.scratch)) {
                Ok(v) => {
                    self.state = TokenState::Idle;
                    return Some(Ok(JsonToken::Literal(Literal::String(
                        v,
                    ))));
                }
                Err(_err) => {
                    return Some(Err(Error::new(
                        ErrorKind::InvalidData,
                        format!(
                            "Failed to parse the string at line:{}, col:{}",
                            self.line, self.col
                        ),
                    )));
                }
            
            }
            _ => {
                self.col += 1;
                consume_amt += 1;
                self.scratch.push(b);
            }
        }
    }
}

An actual control code is invalid in the string, for example,

`
Hello
Flying
Zebra
`;

Here we can see that each word is on a new line and there is an invalid string, we cannot have any newlines in a JSON string, and along with that a range of control codes,

0x00..=0x1F define the range of control codes in JSON spec,

All Unicode characters may be placed within the quotation marks, except for the characters that MUST be escaped: quotation mark, reverse solidus, and the control characters (U+0000 through U+001F).

Overall structure for the string token type, I have skipped adding and repeating code here essentially we will be pushing values to scratch buffer or transitioning to sub states like escaped:true or TokenState::InUnicode sub state.

I decided to keep escaped state boolean in same variant of TokenState and decided to extract out unicode variant as a separate to manage the code since it was getting quite complex to manage nested states within InString.

String case: Unicode escape

---

Okay this one is subtler and slightly a mind bender, also spec does no favor of making this understand any clearer to a novice like me, but as per spec example,

"a\\b" should be equal to "a\u005Cb"

Reason that both strings should be equal is that the parsers will parse the strings and interpret the escape sequences,

so a\\b is just a\b and a\u005Cb is also a\b since \u005C corresponds to \ in unicode, so its advised, to encode these escape sequences.

Now to be able to do that, we need to collect values in an array of fixed length of 4, [u8;4] to be precise, but there is one more catch, where languages such as JavaScript use UTF-16 (internally) to encode emojis, so when it stringify the payload with JSON.stringify() to be compliant with UTF-8 requirement we will get a surrogate pair for such characters!

JSON.stringify(obj); // Could be '{"emoji":"💩"}' OR '{"emoji":"💩"}'

We want to store the four digits in a state and also convert to valid u16 values, to do this we first look at the bytes after \u,

They should in the hexadecimal digit range

let hexadecimal_digit_range = b'0'..=b'9' | b'a'..=b'f' | b'A'..=b'F'

If they fall within it we collect these four digits, technically these are raw bytes (u8), but we want to convert them to u16 representation since we need that to check if the sequences within the range of surrogate pair, (high / low surrogate),

I wrote a helper for this,

fn hex_to_u16(collected: [u8; 4]) -> u16 {
    fn hex_value(b: u8) -> u16 {
        match b {
            b'0'..=b'9' => (b - b'0') as u16,
            b'a'..=b'f' => (b - b'a' + 10) as u16,
            b'A'..=b'F' => (b - b'A' + 10) as u16,
            _ => unreachable!("Internal error: Cannot call hex_to_u16"),
        }
    }
    hex_value(collected[0]) << 12
        | hex_value(collected[1]) << 8
        | hex_value(collected[2]) << 4
        | hex_value(collected[3])
}

Above helper seems complex but its operation is pretty simple,

Step 1. Take in a single u8 and convert it to the corresponding number,

[b’0’,b’0’,b’4’,b’1’] => [48,48,52,49]

What we need is [0,0,4,1] as u16, this can be achieved by subtracting the base value, or rather the start value of range either b'0', or b'a' or b'A',

in case of range A through F we need to add 10 back since b’a’ - b’a’ will be 0 but the actual hexadecimal value of a in \uaaaa,is 10, we have the hexadecimal digits but not the number itself yet, so since we have 4 digits,

┌─────┬─────┬─────┬─────┐ 
│ '0' │ '0' │ '4' │ '1' │
└─────┴─────┴─────┴─────┘

In bytes we get this, b'0' = 48 and so on
┌────┬────┬────┬────┐ 
│ 48 │ 48 │ 52 │ 49 │
└────┴────┴────┴────┘


Now normalize back to their original values, by substracting either b'0' or b'a' or b'A' (and adding back 10) 

┌────┬────┬────┬────┐ 
│ 0  │ 0  │ 4  │  1 │
└─┬──┴─┬──┴─┬──┴──┬─┘
  │    │    │     │
  │    │    │     │
  │    │    │     │
  └───────────────────────────────────🠞 0000 0000 0000 0000 << 12 ──🠞  0000 0000 0000 0000 │
       │    │     │
       └──────────────────────────────🠞 0000 0000 0000 0000 << 8  ──🠞  0000 0000 0000 0000 │
            │     │
            └─────────────────────────🠞 0000 0000 0000 0100 << 4  ──🠞  0000 0000 0100 0000 │
                  │
                  └───────────────────🠞 0000 0000 0000 0001 ────────🠞  0000 0000 0000 0001 │
                                                                       ────────────────────
                                                                       0000 0000 0100 0001

1 hex digit can represent 16 states (0 - 15), that means a digit in a binary sense is made up of 4 bits,
Shifting by 12, 8, 4 means we are shifting the digits in right place and then creating the number as a hexadecimal.

Why am I jumping through all the hoops to convert \u0041 to a u16 ?

• Most unicode characters we use in day to day life fall under BMP (Basic Multilingual Plane) that can be represented by number 0 to (2^16 - 1) or (0 to 65,535). For example,

  “\u0041”

  is A \u0041 is 65 in decimal and 0x0041.
• There are some characters that go beyond this range that include emojis, rare kanji characters and some historical scripts. So instead of using u32 for every character which doubles the file size for everything, Windows, Java and JavaScript decided to use 2 u16 to decode these characters.
• Because surrogate pairs use special mathematical ranges, we need to look at the bytes as u16.
• So to make sure I account for this, I need to convert [u8;4] to an u16.

const high_surrogate_range = 0xD800..=0xDBFF;
const low_surrogate_range = 0xDC00..=0xDFFF;

Following code takes in the bytes after \u, collects it in an array of u8 convert that to u16 and check if we have high or low surrogate pair, in case we encounter a high surrogate pair we transition into states related to handling surrogate pairs, if we encounter a low surrogate here that means the string is invalid and we throw error, and the last blocks just collects the bytes and tries to parse the collected bytes to a character with char::from_u32.

TokenState::InUnicodeEscape {
    mut collected,
    mut count,
} => match b {
    b'0'..=b'9' | b'a'..=b'f' | b'A'..=b'F' => {
        collected[count] = b;
        count += 1;
        self.col += 1;
        consume_amt += 1;
        self.state = TokenState::InUnicodeEscape { collected, count };
        if count == 4 {
            let code_unit = hex_to_u16(collected);
            match code_unit {
                // high surrogate range
                0xD800..=0xDBFF => {
                    self.state = TokenState::ExpectLowSurrogate {
                        state: SurrogatePairState::ExpectSlash {
                            high: code_unit,
                        },
                    }
                }
                // low surrogate range
                0xDC00..=0xDFFF => {
                    return Some(Err(Error::new(
                        ErrorKind::InvalidData,
                        format!(
                            "Cannot have a lone low surrogate in string at line:{}, col:{}",
                            self.line, self.col
                        ),
                    )));
                }
                _ => {
                    let c = char::from_u32(code_unit as u32).unwrap();
                    let mut buf = [0u8; 4];
                    let encoded = c.encode_utf8(&mut buf);
                    self.scratch.extend_from_slice(encoded.as_bytes());
                    self.state = TokenState::InString { escaped: false }
                }
            }
        }
    }
    _ => {
        self.col += 1;
        consume_amt += 1;
        self.reader.consume(consume_amt);
        return Some(Err(Error::new(
            ErrorKind::InvalidData,
            format!(
                "Invalid unicode escape at line:{} col:{}",
                self.line, self.col
            ),
        )));
    }
}

Unicode edge case: Surrogate pairs - 🚀😀😭

---

For surrogate pairs, we keep the following state,

Once we encounter a valid high surrogate we transition into SurrogatePairState::ExpectSlash, we keep the high surrogate as part of the state high: u16, and shift it to every state transition

#[derive(Copy, Clone)]
enum SurrogatePairState {
    ExpectSlash {
        high: u16,
    },
    ExpectU {
        high: u16,
    },
    ExpectCode {
        high: u16,
        collected: [u8; 4],
        count: usize,
    },
}

State transition for surrogate pair after encountering a valid high surrogate

--> Transition in TokenState::ExpectLowSurrogate
    --> SurroagatePairState::ExpectSlash
    --> SurrogatePairState::ExpectU
    --> SurrogatePairState::ExpectCode
--> Transition back to InString {escaped: false}

TokenState::ExpectLowSurrogate { state } => {
    match state {
        SurrogatePairState::ExpectSlash { high } => {
            if b'\\' == b {
                consume_amt += 1;
                self.col += 1;
                self.state = TokenState::ExpectLowSurrogate {
                    state: SurrogatePairState::ExpectU { high },
                }
            } else {
            /*throw error*/
            }
        }
        SurrogatePairState::ExpectU { high } => {
            if b'u' == b {
                consume_amt += 1;
                self.col += 1;
                self.state = TokenState::ExpectLowSurrogate {
                    state: SurrogatePairState::ExpectCode {
                        high,
                        collected: [0; 4],
                        count: 0,
                    },
                }
            } else {
            /*throw error*/
            }
        }
        SurrogatePairState::ExpectCode {
            high,
            mut collected,
            mut count,
        } => match b {
            b'0'..=b'9' | b'a'..=b'f' | b'A'..=b'F' => {
                collected[count] = b;
                count += 1;
                consume_amt += 1;
                self.col += 1;
                self.state = TokenState::ExpectLowSurrogate {
                    state: SurrogatePairState::ExpectCode {
                        high,
                        collected,
                        count,
                    },
                };
                if count == 4 {
                    let low = hex_to_u16(collected);
                    if !(0xDC00..=0xDFFF).contains(&low) {
                    /*throw error*/
                    }

                    let code_units = vec![high, low];
                    if let Some(Ok(c)) = char::decode_utf16(code_units).next() {
                        let mut buf = [0u8; 4];
                        self.scratch.extend_from_slice(
                            c.encode_utf8(&mut buf).as_bytes(),
                        );
                    } else {
                    /*throw error*/
                    }
                    self.state = TokenState::InString { escaped: false }
                }
            }
            _ => {/*throw error*/}
        },
    }
}

Under SurrogatePair::ExpectCode, we use char::decode_utf16 to convert the surrogate pair to the valid character, and encode it back as bytes and push it to scratch. Final Step is to transition back to TokenState::InString.

For sake of the article, I have removed error handling parts, but error typically looks something like under each block where I say throw error.

return Some(Err(Error::new(
    ErrorKind::InvalidData,
    format!(
        "Invalid UTF-8, at line:{}, col:{}",
        self.line, self.col
    ),
)));

Number

---

Once we encounter a valid number starting value (either a - sign, or a digit 0-9) we transition into a TokenState::InNumber, further there is a separate state required to transition within number to handle all valid variants,

1. Integer
2. Fractions
3. Exponents

I have skipped mentioning positive and negative numbers but JSON supports both, the catch is that JSON does not impose any limits on the number of digits a number can have, technically you can send an infinitely long number but you would not violate any JSON rules.

JSON number rules,

1. Integers
   • Should have digit 0-9
   • Leading zeros are not allowed
   • 0 on its own is not a leading zero
   • Only negative sign is allowed i.e. (’-’ sign)
2. Fraction
   • Should have .
   • At least one digit (0-9) before .
3. Exponents
   • ‘e’ or ‘E’ transitions to exponent
   • exponent must be followed by digits
   • ’+’ or ’-’ are allowed with exponent part of digits

Entry point to number transition

b'-' => {
    self.col += 1;
    consume_amt += 1;
    self.scratch.push(b);
    self.state = TokenState::InNumber {
        state: NumberState::LeadingMinus,
    };
}
b'0'..=b'9' => {
    self.col += 1;
    consume_amt += 1;
    self.scratch.push(b);
    self.state = TokenState::InNumber {
        state: if b == b'0' {
            NumberState::LeadingZero
        } else {
            NumberState::Integer
        },
    }
}

Based on above rules, I decided to keep these as number transition states

#[derive(Copy, Clone)]
enum NumberState {
    DotSeen,
    Exponent, // emit
    ExponentSign,
    ExponentMarker,
    LeadingMinus,
    LeadingZero, // emit
    Integer,     // emit
    Fraction,    // emit
}

DotSeen -> Is for fractions, typically is a deciding point whether a number is valid or not based on what comes after the dot, ExponentMarker -> Stands for ‘e’ or ‘E’, same point as above, based on what comes next we can decide whether a exponent is valid or not. ExponentSign -> ’+’ or ’-’ LeadingMinus -> ’-’ seen in front of a number LeadingZero -> 0 at the start, we can’t know for certain if there are any more digits are not next so its a case of its own Integer -> means an integer, typical state a number would be in and branch out to other states, Fraction -> If number is valid after DotSeen case, we transition to this one.

So the state transitions are based on look-back rather than look-ahead, we know with self.state what the last state the number was in and check what the current byte is, with this we avoid unnecessarily looking ahead.

Choosing a state transition is based on the fact that each state indicates a clear and a sure-shot branch point, where its clear that the number will no longer be just an integer, along with the fact that it can be valid or invalid based on values coming after that symbol.

For example,

0. represents a TokenState::InNumber {state::NumberState::DotSeen} state transition, and further transition depends on the fact that what comes next,

1. a number then transition into a NumberState::Fraction
2. EOF - throw error since we cannot have a 0. as a number
3. anything else but a digit - throw error

Number case: Integers

---

NumberState::Integer => {
    match b {
        b'.' => {
            self.col += 1;
            consume_amt += 1;
            self.scratch.push(b);
            self.state = TokenState::InNumber {
                state: NumberState::DotSeen,
            }
        }
        b'0'..=b'9' => {
            self.col += 1;
            consume_amt += 1;
            self.scratch.push(b);
            self.state = TokenState::InNumber {
                state: NumberState::Integer,
            }
        }
        b'e' | b'E' => {
            self.col += 1;
            consume_amt += 1;
            self.scratch.push(b);
            self.state = TokenState::InNumber {
                state: NumberState::ExponentMarker,
            }
        }
        b' ' | b'\t' | b'\n' | b'\r' | b',' | b'}' | b']' => {
            self.reader.consume(consume_amt);
            self.state = TokenState::Idle;
            return Some(
        parse_number(std::mem::take(&mut self.scratch)).map(|v| JsonToken::Literal(Literal::Number(v))).map_err(|_| Error::new(ErrorKind::InvalidData,format!("Invalid number found at line:{}, col:{}",self.line,self.col)))
    );
        }
        _ => {/*throw error*/}
    }
}

Integer state under number state is straight forward,

1. If you encounter a . transition to a DotSeen state.
2. If a digit is seen, push the byte to scratch and keep it in Integer state.
3. If a exponent marker is seen, transition to a ExponentMarker state.
4. If you encounter whitespace or newline, that means we have reached end of the number, and its time to emit the token

I have written a small helper which will repeat across different number states that emit valid number token, its used to convert a Vec<u8> -> f64,

fn parse_number(seq: Vec<u8>) -> Result<f64, Error> {
    let format_str = String::from_utf8(seq).map_err(|e| Error::new(ErrorKind::InvalidData, e))?;
    let number: f64 = format_str
        .parse()
        .map_err(|e| Error::new(ErrorKind::InvalidData, e))?;
    Ok(number)
}

// used like this
parse_number(std::mem::take(&mut self.scratch)).map(|v| JsonToken::Literal(Literal::Number(v))).map_err(|_| Error::new(ErrorKind::InvalidData,format!("Invalid number found at line:{}, col:{}",self.line,self.col)))

1. Parse number - Takes in a Vec<u8> converts to String and then parses back to a f64 - This is sub optimal, and probably would not fly in a production grade parsers, but its not that bad for learning purposes and makes sense for me since its just less code and does things safely enough. Other options include, converting Vec<u8> to f64 directly with just UTF-8 validation, and not converting to string first, which improves speed greatly or write a custom parser for just number. Other option includes directly parsing from bytes, but I probably need to write that custom parser, and it will be fastest option, since we would skip UTF-8 validation + parsing string into a f64.
2. std::mem::take(&mut self.scratch) - This is worth mentioning since I want the self.scratch to be re-initialized to an empty vector, std::mem::take moves ownership from the tokenizer self.scratch to the function and reinitializes, self.scratch with an empty vector.
3. .map and .map_err - Used to handle Result Type, it takes in a callback and calls it with either the wrapped value or error in case of map_err, which makes it easier to cast in appropriate Token or throw error, basically I am choosing to write methods chained than do one more match statement here.

Number case: Exponent

---

State transition for exponents looks something like this

You can land under Exponent marker from following states,

1. Integer
2. Fraction
3. Leading Zero (0e212 or 0e3 both are valid)

--> TokenState::InNumber
    --> NumberState::Integer | NumberState::Fraction | NumberState::LeadingZero
        ---> ExponentMarker
        ---> ExponentSign (optional)
        ---> Exponent
---> emits a JSONToken::Number
---> TokenState::Idle

Similar to string we collect the bytes in the scratch before and convert the final value to the expected f64 equivalent.

Exponent Marker state transitions:

NumberState::ExponentMarker => match b {
    b'-' | b'+' => {
        self.col += 1;
        consume_amt += 1;
        if b == b'-' {
            // we can skip + sign in buffer since its optional and apparent if there
            // is no sign its positive
            self.scratch.push(b);
        }
        self.state = TokenState::InNumber {
            state: NumberState::ExponentSign,
        }
    }
    b'0'..=b'9' => {
        // only see the byte to transition, don't consume it
        self.state = TokenState::InNumber {
            state: NumberState::Exponent,
        }
    }
    _ => {
    /*throw error*/
    }
}

Exponent Sign state transitions:

NumberState::ExponentSign => match b {
    b'0'..=b'9' => {
        self.col += 1;
        consume_amt += 1;
        self.scratch.push(b);
        self.state = TokenState::InNumber {
            state: NumberState::Exponent,
        }
    }
    _ => {
    /*throw error*/
    }
}

Exponent state transitions:

NumberState::Exponent => {
    match b {
        b'0'..=b'9' => {
            self.col += 1;
            consume_amt += 1;
            self.scratch.push(b);
        }
        b' ' | b'\t' | b'\n' | b'\r' | b',' | b'}' | b']' => {
            self.reader.consume(consume_amt);
            self.state = TokenState::Idle;
            return Some(
        parse_number(std::mem::take(&mut self.scratch)).map(|v| JsonToken::Literal(Literal::Number(v))).map_err(|_| Error::new(ErrorKind::InvalidData,format!("Invalid number found at line:{}, col:{}",self.line,self.col)))
    );
        }
        _ => {/*throw error*/}
    }
}

Number case: Fraction

---

Fractions have following state transitions:

---> TokenState::InNumber
     -->  NumberState::Integer
          --> NumberState::DotSeen
              ---> NumberState::Fraction
                   ---> return JsonToken::Number
---> TokenState::Idle

NumberState::Fraction => {
    match b {
        b'.' => {
        /*throw error*/
        }
        b'0'..=b'9' => {
            self.col += 1;
            consume_amt += 1;
            self.scratch.push(b);
        }
        b'e' | b'E' => {
            self.col += 1;
            consume_amt += 1;
            self.scratch.push(b);
            self.state = TokenState::InNumber {
                state: NumberState::ExponentMarker,
            }
        }
        b' ' | b'\t' | b'\n' | b'\r' | b',' | b'}' | b']' => {
            self.reader.consume(consume_amt);
            self.state = TokenState::Idle;
            return Some(
        parse_number(std::mem::take(&mut self.scratch))
        .map(|v| JsonToken::Literal(Literal::Number(v)))
        .map_err(|_| Error::new(ErrorKind::InvalidData,format!("Invalid number found at line:{}, col:{}",self.line,self.col)))
    );
        }
        _ => {
        /*throw error*/
        }
    }
}

We can’t have duplicate ’.’ in a number which is an error case or any character other than digits (0-9) should throw error. The rest of the logic for handling parsing the valid number is same as number The rest of the logic for handling parsing the valid number is same as number.

There are other two states of number: LeadingZero and LeadingMinus but they don’t emit anything rather serve as a way to handle edge cases of leading zero or leading minus sign and they will either throw an error or transition to integer state.

    NumberState::LeadingMinus => match b {
        b'0' => {
            self.col += 1;
            consume_amt += 1;
            self.scratch.push(b);
            self.state = TokenState::InNumber {
                state: NumberState::LeadingZero,
            };
        }
        b'1'..=b'9' => {
            self.col += 1;
            consume_amt += 1;
            self.scratch.push(b);
            self.state = TokenState::InNumber {
                state: NumberState::Integer,
            };
        }
        _ => {
        /*throw error*/
        }
    },
    // emit here
    NumberState::LeadingZero => {
        match b {
            b'0'..=b'9' => {//throw error}
            // handling cases where the number ends naturally
            // we skip processing here the byte to avoid duplicate logic
            b' ' | b'\t' | b'\n' | b'\r' | b',' | b'}' | b']' => {
                self.reader.consume(consume_amt);
                self.state = TokenState::Idle;
                return Some(
            parse_number(std::mem::take(&mut self.scratch)).map(|v| JsonToken::Literal(Literal::Number(v))).map_err(|_| Error::new(ErrorKind::InvalidData,format!("Invalid number found at line:{}, col:{}",self.line,self.col)))
        );
            }
            _ => {
                //throw error
                )));
            }
        }
    }

Keywords

---

Keywords include null, true and false in JSON, the mechanism for handling is more or less the same,

The entry point is decided based on the fact that whether we encounter a byte equal to (b'n', b't', b'f'), and we transition into one of the ExpectKeywordState,

#[derive(Copy, Clone)]
enum ExpectKeywordState {
    True,
    False,
    Null,
}

Transitioning from idle to keyword state is as follows:

b't' => {
    self.col += 1;
    consume_amt += 1;
    self.scratch.push(b);
    self.state = TokenState::InKeyword {
        state: ExpectKeywordState::True,
    };
}
b'f' => {
    self.col += 1;
    consume_amt += 1;
    self.scratch.push(b);
    self.state = TokenState::InKeyword {
        state: ExpectKeywordState::False,
    };
}
b'n' => {
    self.col += 1;
    consume_amt += 1;
    self.scratch.push(b);
    self.state = TokenState::InKeyword {
        state: ExpectKeywordState::Null,
    };
}

I can implement similar strategy of look back, just look at the last character in the scratch and match against current if the pair makes sense then the overall sequence must be valid.

I am putting a block for true keyword since the rest of keyword use same logic to build.

TokenState::InKeyword { state, last } => match state {
ExpectKeywordState::True => {
    let last =
        self.scratch.last().copied().expect(
            "ExpectKeywordState state always has ≥1 byte in scratch",
        );
    let valid_next =
        matches!((last, b), (b't', b'r') | (b'r', b'u') | (b'u', b'e'));

    if valid_next && self.scratch.len() < 4 {
        self.col += 1;
        consume_amt += 1;
        self.scratch.push(b);
        self.state = TokenState::InKeyword {
            state: ExpectKeywordState::True,
        };
        break;
    };
    match b {
        b' ' | b'\t' | b'\r' | b'\n' | b'{' | b'}' | b'[' | b']' | b',' => {
            // no need to change self.line, self.col since we are not consuming the byte here
            // for newline or any other characters
            self.reader.consume(consume_amt);
            if self.scratch == b"true" {
                self.scratch = vec![];
                self.state = TokenState::Idle;
                return Some(Ok(JsonToken::Literal(Literal::Bool(true))));
            } else {
            /*error handling*/
            }
        }
        _ => {
        /*error handling*/
        }
    };
}
}

I am using tuple pattern matching to check as I push the current byte to the scratch if it will form a valid sequence, if not I can throw an early error for such cases, finally once I reach a desired length say 4 in case of true keyword, I check what is the next byte corresponding to it should either be a whitespace, or array end or an object end or comma, that marks end of the keyword there is also EOF but that’s a separate section at the start of iteration.

I check again within the final match b {} block if the scratch holds what I intended to hold, if yes then I return the keyword token else throw an error, while that error should not happen in ideal conditions, there is some chance of bug or indirect manipulation of scratch, that could break this btw, so that check if present under each keyword.

Handling EOF

---

While we have all the logic up there that describes how to handle the intricacies of the various values, handling EOF is crucial to make this work properly.

EOF indicates you have reached the end of file quite literally there is nothing more left to read and its time to be done.

This makes sense in most cases since all JSON values are top level, except the ones nested in top level ones, so its crucial to know first hand how to handle this,

For numbers in this code, its possible to hit EOF at any point, but if the number is in some states as listed below

1. Fraction
2. Exponent
3. Integer
4. LeadingZero

Its possible that the number might be valid so we group these states and try to parse the number from scratch vector.

Some states that mark the transition,

1. DotSeen
2. ExponentMarker
3. ExponentSign
4. LeadingMinus

will never result in a valid number at EOF, for example (0.2E-, 0., 0e, -), we throw error for such states.

If TokenState is Idle, it just means there is nothing more to process and we return None which marks end of iterator.

For keywords, true,false and null we check if the values in scratch correspond to valid keyword, if they do, return the token else throw an error.

A string should never be in any of its states if we reach EOF, basically that would signal us that we never hit the boundary of quotes and that we were in the middle of the string when we hit EOF, I just throw error in that case.

if buffer.is_empty() {
match self.state {
    TokenState::InNumber { state } => {
        match state {
            NumberState::Fraction
            | NumberState::Exponent
            | NumberState::Integer
            | NumberState::LeadingZero => {
                self.state = TokenState::Idle;
                return Some(
                    parse_number(std::mem::take(&mut self.scratch))
                        .map(|v| JsonToken::Literal(Literal::Number(v)))
                        .map_err(|_| {
                            Error::new(
                                ErrorKind::InvalidData,
                                format!(
                                    "Invalid number found at line:{}, col:{}",
                                    self.line, self.col
                                ),
                            )
                        }),
                );
            }
            NumberState::DotSeen
            | NumberState::ExponentSign
            | NumberState::ExponentMarker
            | NumberState::LeadingMinus => {
                self.state = TokenState::Idle;
                // throw error - incomplete number passed into the parser
                return Some(Err(Error::new(
                    ErrorKind::InvalidData,
                    format!(
                        "Incomplete number at line:{}, col:{}",
                        self.line, self.col
                    ),
                )));
            }
        }
    }
    TokenState::Idle => return None,
    TokenState::InKeyword { state, .. } => match state {
        ExpectKeywordState::True => {
            if self.scratch == b"true" {
                self.scratch = vec![];
                self.state = TokenState::Idle;
                return Some(Ok(JsonToken::Literal(Literal::Bool(true))));
            } else {
                self.scratch = vec![];
                return Some(Err(Error::new(
                    ErrorKind::InvalidData,
                    format!(
                        "Invalid true keyword at line:{}, col:{}",
                        self.line, self.col
                    ),
                )));
            }
        }
        ExpectKeywordState::False => {
            if self.scratch == b"false" {
                self.scratch = vec![];
                self.state = TokenState::Idle;
                return Some(Ok(JsonToken::Literal(Literal::Bool(false))));
            } else {
                self.scratch = vec![];
                return Some(Err(Error::new(
                    ErrorKind::InvalidData,
                    format!(
                        "Invalid false keyword at line:{}, col:{}",
                        self.line, self.col
                    ),
                )));
            }
        }
        ExpectKeywordState::Null => {
            if self.scratch == b"null" {
                self.scratch = vec![];
                self.state = TokenState::Idle;
                return Some(Ok(JsonToken::Literal(Literal::Null)));
            } else {
                self.scratch = vec![];
                return Some(Err(Error::new(
                    ErrorKind::InvalidData,
                    format!(
                        "Invalid null keyword at line:{}, col:{}",
                        self.line, self.col
                    ),
                )));
            }
        }
    },
    TokenState::InString { escaped: _ } => {
        return Some(Err(Error::new(
            ErrorKind::InvalidData,
            format!("Incomplete string at line:{}, col:{}", self.line, self.col),
        )));
    }
    TokenState::InUnicodeEscape {
        collected: _,
        count: _,
    } => {
        return Some(Err(Error::new(
            ErrorKind::InvalidData,
            format!("Incomplete string at line:{}, col:{}", self.line, self.col),
        )));
    }
    TokenState::ExpectLowSurrogate { .. } => {
        return Some(Err(Error::new(
            ErrorKind::InvalidData,
            format!("Invalid unicode at line:{}, col:{}", self.line, self.col),
        )));
    }
}
};

Parser - Endgame

---

Once we have tokens down, it comes down to re-constructing same structure in Rust equivalent data structure, now choosing a valid data structure is crucial, we can’t go structs or arrays to represent json object or arrays,

Again we go for enums, one of the reasons this makes sense is because JSON arrays can hold values of multiple types, for example [0, 'hello',true] is a valid array in JSON, but the equivalent is not possible in many strictly typed languages in this case enum come in handy where each value can be wrapped in a variant of an enum, same value can be represented as

let output = JsonValue::Array(
    vec![
        JsonValue::Number(0_f64),
        JsonValue::String("hello".to_string()),
        JsonValue::Bool(true)
    ]
);

So we represent various value types as variants of JsonValue:

#[derive(Debug, PartialEq)]
enum JsonValue {
    String(String),
    Number(f64),
    Bool(bool),
    Null,
    Array(Vec<JsonValue>),
    Object(HashMap<String, JsonValue>),
}

Now a major reason we need a parser at all, is arrays and objects, and we can infinitely nest objects and arrays, within themselves, and to handle that we need to handle those context somehow, for this, I am still going to embrace the look back approach rather than look ahead, or any kind of recursive approach to generate the expected data structure.

So to track nested objects or arrays, I need to hold such values on a stack, I am just putting a field called stack:Vec<Container> on parser, Container represents either an array or object.

For object container, I need to hold a state that indicates whether currently I am either looking at a start bracket, closing bracket, a key, value or a colon or a comma.

map:HashMap<String,JsonValue> - Simply means a key value pair like JSON, I am also holding a current key, reason being we could have an object as a value and we might enter some deeply nested context, so we need to know what key for which level points to what value.

The top level object is always going to belong to a level below if it exists, either as a value for a key in an object, a value in an array.

Handling Array as a context is much simpler, we only need a vec to hold collection of JsonValue and a state variable.

enum Container {
    Object {
        state: ObjectState,
        map: HashMap<String, JsonValue>,
        current_key: Option<String>,
    },
    Array {
        state: ArrayState,
        vec: Vec<JsonValue>,
    },
}

struct Parser<R: BufRead> {
    stack: Vec<Container>,
    tokenizer: Tokenizer<R>,
}

impl<R: BufRead> Parser<R> {
    fn new(tokenizer: Tokenizer<R>) -> Self {
        Self {
            stack: vec![],
            tokenizer,
        }
    }

    fn parse(&mut self) -> Result<JsonValue, Error> {}

For states,

1. Object
   • ObjectState::Start -> Transition when you see JsonToken::PairStart(PairStart::LeftBrace) -> Push the container on stack
   • ObjectState::Key -> Transition after start or a comma, when you see a string
   • ObjectState::Colon -> Transition after you see a colon after a key
   • ObjectState::Comma -> Transition after you see a comma after a value
   • ObjectValue::Value -> Transition after you see a value after a colon
2. Array
   • ArrayState::Start -> When you see a [
   • ArrayState::Value -> When you see a value either after a start or a separator like comma
   • ArrayState::Comma -> When you see it after a value

These states define what individual states a token can represent in reference to previous state. I am skipping the end states here since they kind of don’t make sense to hold, since you will most likely pop or assign the value to the last stack item in case of nested objects or arrays.

enum ObjectState {
    Start, // at the start when { is encountered
    Key,   // has to be of type JsonToken::String
    Colon, // separator
    Comma, // separator
    Value, // can be of type JsonToken::String, JsonToken::Number, JsonToken::Bool, JsonToken::Null or object or Array
}

enum ArrayState {
    Start, // at the start when [is seen
    Value, // value within array is seen
    Comma, // comma is seen
}

Parser by itself is very simple, stack to manage nested values like arrays or objects and tokenizer which is owned by parser, where we use tokenizer in parse() method to pull in JsonToken.

struct Parser<R: BufRead> {
    stack: Vec<Container>,
    tokenizer: Tokenizer<R>,
}

One of the reasons I am using look back rather than look ahead is simply because it comes down to complexity and performance, accessing the last stack frame is just O(1), self.stack.last() while a look ahead might sound fancy or cool, I decide against using that simply because I decided to work with previous state that is accumulated already in a stack and generate a token just once, and then no more, this keeps the flow simple, simple enough for debugging and understanding transitions, there are some cases where I had to pull out my paper and pen and draw the stack, but nonetheless a lot easier to deal with than look ahead.

I am putting down a snippet for a single token type handling below, since putting the complete parser code in here, will bloat this article beyond control.

impl<R: BufRead> Parser<R> {
    fn new(tokenizer: Tokenizer<R>) -> Self {
        Self {
            stack: vec![],
            tokenizer,
        }
    }

    fn parse(&mut self) -> Result<JsonValue, Error> {
        let tokenizer = &mut self.tokenizer;
        let mut error_msg: Option<String> = None;
        let mut output: Option<JsonValue> = None;

        for token_result in tokenizer.by_ref() {
            let token = token_result?;
            if output.is_some() {
                match token {
                    /*handling top level value edge cases*/
                }
            };

        match token {
            JsonToken::PairStart(PairStart::LeftBrace) => match self.stack.last_mut() {
                Some(Container::Object { state, .. }) => match state {
                    ObjectState::Start => {
                        error_msg = Some("Cannot have duplicate { in object".to_string());
                        break;
                    }
                    ObjectState::Key => {
                        error_msg = Some("Cannot have { in object after key".to_string());
                        break;
                    }
                    ObjectState::Colon => {
                        let next_stack_frame = Container::Object {
                            state: ObjectState::Start,
                            map: HashMap::new(),
                            current_key: None,
                        };
                        *state = ObjectState::Value;
                        if allow_push_to_stack(self.stack.len()) {
                            self.stack.push(next_stack_frame);
                        } else {
                            error_msg = Some("Exceeded nesting limit of 512".to_string());
                            break;
                        }
                    }
                    ObjectState::Value => {
                        error_msg = Some("Cannot have { in object after a value".to_string());
                        break;
                    }
                    ObjectState::Comma => {
                        error_msg = Some("Cannot have { in object after a comma".to_string());
                        break;
                    }
                },
                Some(Container::Array { state, .. }) => match state {
                    ArrayState::Start => {
                        let next_stack_frame = Container::Object {
                            state: ObjectState::Start,
                            map: HashMap::new(),
                            current_key: None,
                        };
                        *state = ArrayState::Value;
                        if allow_push_to_stack(self.stack.len()) {
                            self.stack.push(next_stack_frame);
                        } else {
                            error_msg = Some("Exceeded nesting limit of 512".to_string());
                            break;
                        }
                    }
                    ArrayState::Value => {
                        error_msg = Some("Cannot have { in an array after a value".to_string());
                        break;
                    }
                    ArrayState::Comma => {
                        let next_stack_frame = Container::Object {
                            state: ObjectState::Start,
                            map: HashMap::new(),
                            current_key: None,
                        };
                        *state = ArrayState::Value;
                        if allow_push_to_stack(self.stack.len()) {
                            self.stack.push(next_stack_frame);
                        } else {
                            error_msg = Some("Exceeded nesting limit of 512".to_string());
                            break;
                        }
                    }
                },
                None => {
                    let next_stack_frame = Container::Object {
                        state: ObjectState::Start,
                        map: HashMap::new(),
                        current_key: None,
                    };
                    if allow_push_to_stack(self.stack.len()) {
                        self.stack.push(next_stack_frame);
                    } else {
                        error_msg = Some("Exceeded nesting limit of 512".to_string());
                        break;
                    }
                }
            },
            // much more code in here than I wish to share in this blog
        }
        }

        // handling the out put at the end of loop

        match (output, error_msg) {
            (Some(_), Some(mut err)) => {
                let line_msg = format!(
                    ", at line:{}, col:{}",
                    self.tokenizer.line, self.tokenizer.col
                );
                err.push_str(&line_msg);
                Err(Error::new(ErrorKind::InvalidData, err))
            }
            (None, None) => Err(Error::new(
                ErrorKind::InvalidData,
                "No valid input was provided",
            )),
            (None, Some(mut err)) => {
                let line_msg = format!(
                    ", at line:{}, col:{}",
                    self.tokenizer.line, self.tokenizer.col
                );
                err.push_str(&line_msg);
                Err(Error::new(ErrorKind::InvalidData, err))
            }
            (Some(v), None) => {
                if self.stack.is_empty() {
                    Ok(v)
                } else {
                    Err(Error::new(ErrorKind::InvalidData, "Invalid input"))
                }
            }
        }
    }
}

Nesting limit

---

I added a hardcoded limit of 512, which is generous for general use and for the purpose of side project as well. Although nesting should be absolutely kept to a minimum to have better parsing performance and overall speed, if its unavoidable this limit should be more than enough for 99% of cases.

I am using iterative approach for handling nesting 512 is pretty cheap compared to recursive calls for modern CPUs.

const NEST_LIMIT: i32 = 512;
fn allow_push_to_stack(stack_size: usize) -> bool {
    (stack_size as i32 + 1) < NEST_LIMIT
}

A defensive check to check if pushing to stack will by pass limit set, is used before pushing anything onto stack

if allow_push_to_stack(self.stack.len()) {
    self.stack.push(next_stack_frame);
} else {
    error_msg = Some("Exceeded nesting limit of 512".to_string());
    break;
}

Unit testing and coverage

---

Unit tests are kept in the same file to avoid complexity of dealing with imports and what not, and makes it easier to manage and debug without constantly switching context, I found a great way to group related tests together as below

#[cfg(test)]
mod test {
use super::*;

fn get_tokenizer(mock_string: &str) -> Tokenizer<BufReader<&[u8]>> {
    let reader = BufReader::new(mock_string.as_bytes());
    Tokenizer::new(reader)
}

fn expect_message(mock_string: &str) -> String {
    format!("Expected {}, got None", mock_string)
}

mod tokenizer_tests {
use super::*;
    #[test]
    fn test_tokenizer_left_brace() {
        let mock_string = r"{";
        let mut tokenizer = get_tokenizer(mock_string);
        let message = expect_message(mock_string);
        let result = tokenizer.next().expect(&message);
        assert_eq!(result.unwrap(), JsonToken::PairStart(PairStart::LeftBrace));
        assert_eq!(tokenizer.line, 1);
        assert_eq!(tokenizer.col, 1);
    }


}

mod parser_tests {
use super::*;

    mod primitive_tests {
        use super::*;
        #[test]
        fn parse_primitive_number() {
            let mock_input = r"9";
            let tokenizer = get_tokenizer(mock_input);
            let mut parser = Parser::new(tokenizer);
            let message = expect_message(mock_input);
            let out = parser.parse().expect(&message);
            assert_eq!(out, JsonValue::Number(9_f64));
        }
     }

}
}

Then from command line you can do this

> cargo test // runs all tests
> cargo test parser_tests // runs all parser tests
> cargo test parser_tests::primitive_tests // runs only primitive tests under parser tests

Coverage is especially an important guidance tool for discovery of missing unit tests, I decided to go with llvm-cov for getting coverage, after installing llvm-cov you can view the coverage in your browser with nice red-green color, coding and a coverage report, just run

> cargo llvm-cov --html --open

A healthy amount of unit tests and coverage for the first parser I have written…

Filename	Function	Coverage	Line
home/flyingzebra/repo/coding-challenges-rust/json-parser/src/main.rs	96.32% (183/190)	97.26% (2837/2917)	97.80% (4943/5054)
Totals	96.32% (183/190)	97.26% (2837/2917)	97.80% (4943/5054)

running 167 tests

// A wall of tests with ok at its end

test result: ok. 167 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.01s

References

---

• JSON specification RFC 8259
• JSON diagrammatic reference
• Parsing commandline args with no dependencies
• Simple but powerful pratt parsing