JSON4 parser in Typescript

Question

Context

I may have accidentally gotten a little sidetracked during homeschooling, and wrote a JSON4 parser in Typescript during the down-time. This project started as an idea that I got while discussing something actually school-related and over the past few days grew into this.

I have no formal education on how compilers/parser/lexers work, except for the few hours I wasted on the internet reading up on the topic. This makes me especially curious if this implementation is somewhat correct - in the grand scheme of things.

I have dedicated myself to make it as spec-compliant as I deemed reasonable. I used this specification as a reference.

In the GIT repository I pulled in a "JSON test suite", which I used to run tests against the code. This helped me fix several bugs, but I think there are still lots of edge-cases that are not handled.

To help anyone kind enough to review my code, I've published this thing in my "pet project" github repo, with everything already set up, so you just have to clone that and install using yarn.

Questions

I am mainly interested in the technical implementation of the code. I tried to focus on readability, how did that work out?

• How readable/understandable is the code?
• How is the design/architecture of the code?
• Are there any best-practices or techniques I could implement?

I know this is a lot of code, but there is no need to review all of it!

This thing works as is, the only thing that is still a little wanky is the string escaping.

Code

src/Json.ts

import { JsonValue } from './lib/types';

import { parse } from './lib/parser';
import { tokenize } from "./lib/lexer";
import { convertNodeToJsValue } from './lib/generator';

export class Json {
  static parse(source: string): JsonValue {
    const tokens = tokenize(source);
    const ast = parse(tokens);
    const jsValue = convertNodeToJsValue(ast);

    return jsValue;
  }
}

src/lib/util/JsonError.ts

import { Token } from "../Token";

function serializeTokens(tokens: Token[]) {
    return tokens.map((token) => {
        if (token.isString) {
            return `"${token.value}"`;
        }

        return token.value;
    }).join("");
}

function formatMessage(message: string, tokens: Token[]): string {
    const source = serializeTokens(tokens);

    return `${message}\n\nSource at the point of the Error:\n${source}\n^`;
}

export class JsonError extends Error {
    constructor(message: string, tokens: Token[]) {
        super(formatMessage(message, tokens));
    }
}

src/lib/types.ts

export type JsonScalar = boolean | number | string | null;

export type JsonObject = { [key: string]: JsonValue };

export type JsonArray = JsonValue[];

export type JsonValue = JsonObject | JsonArray | JsonScalar;

src/lib/Token.ts

type TokenType = "punctuation" | "boolean" | "string" | "number" | "null";

export class Token {
  public readonly type: TokenType;
  public readonly value: string;

  public constructor(type: TokenType, value: string) {
    this.type = type;
    this.value = value;
  }

  public get isString(): boolean {
    return this.type === "string";
  }

  public get isNumber(): boolean {
    return this.type === "number";
  }

  public get isBoolean(): boolean {
    return this.type === "boolean";
  }

  public get isNull(): boolean {
    return this.type === "null";
  }

  public get isScalar(): boolean {
    return this.isNull || this.isString || this.isNumber || this.isBoolean;
  }

  public get isPunctuation(): boolean {
    return this.type === "punctuation";
  }

  public get isArrayOpen(): boolean {
    return isPredefinedPunctuation("arrayOpen", this);
  }

  public get isArrayClose(): boolean {
    return isPredefinedPunctuation("arrayClose", this);
  }

  public get isObjectOpen(): boolean {
    return isPredefinedPunctuation("objectOpen", this);
  }

  public get isObjectClose(): boolean {
    return isPredefinedPunctuation("objectClose", this);
  }

  public get isComma(): boolean {
    return isPredefinedPunctuation("comma", this);
  }

  public get isColon(): boolean {
    return isPredefinedPunctuation("colon", this);
  }
}

export const PUNCTUATION_TOKENS = {
  comma: new Token("punctuation", ","),
  colon: new Token("punctuation", ":"),
  arrayOpen: new Token("punctuation", "["),
  arrayClose: new Token("punctuation", "]"),
  objectOpen: new Token("punctuation", "{"),
  objectClose: new Token("punctuation", "}"),
};

function isPredefinedPunctuation(
  key: keyof typeof PUNCTUATION_TOKENS,
  token: Token,
): boolean {
  return token.isPunctuation && PUNCTUATION_TOKENS[key].value === token.value;
}

src/lib/lexer.ts

import { PUNCTUATION_TOKENS, Token } from "./Token";

type TokenizerResult =
  | { matched: false; cursor?: number }
  | { matched: true; token: Token; cursor: number };

type Tokenizer = (source: string, cursor: number) => TokenizerResult;

export function tokenize(source: string): Token[] {
  let cursor = 0;
  const tokens: Token[] = [];

  const tokenizers: Tokenizer[] = [
    tokenizeWhitespace,
    tokenizePunctuation,
    tokenizeNull,
    tokenizeNumber,
    tokenizeString,
    tokenizeBoolean,
  ];

  while (cursor < source.length) {
    let didMatch = false;

    for (const tokenizer of tokenizers) {
      const result = tokenizer(source, cursor);

      if (result.matched) {
        didMatch = true;
        cursor = result.cursor;
        tokens.push(result.token);

        break;
      }

      // Even if a tokenizer did not match, it is free to move the cursor
      // this is usefull for example when parsing white-space, which does not result in a token
      if (!result.matched && typeof result.cursor === "number") {
        didMatch = true;
        cursor = result.cursor;

        break;
      }
    }

    if (!didMatch) {
      throw new Error(`Could not lex token: "${source.substr(cursor)}"`);
    }
  }

  return tokens;
}

function tokenizeWhitespace(source: string, cursor: number): TokenizerResult {
  const result = matchRegex(source, cursor, /^(?!\f)\s/);

  if (result.matched) {
    return {
      matched: false,
      cursor: result.cursor,
    };
  }

  return {
    matched: false,
  };
}

function tokenizeNull(source: string, cursor: number): TokenizerResult {
  return matchStaticToken(source, cursor, new Token("null", "null"));
}

function tokenizeBoolean(source: string, cursor: number): TokenizerResult {
  const booleanTokens = [new Token("boolean", "true"), new Token("boolean", "false")];

  for (const token of booleanTokens) {
    const result = matchStaticToken(source, cursor, token);

    if (result.matched) {
      return result;
    }
  }

  return {
    matched: false,
  };
}

function tokenizeNumber(source: string, cursor: number): TokenizerResult {
  const result = matchRegex(
    source,
    cursor,
    /^(?:(?!0\d)(?!-0\d)-?(?:0(?:\.\d+)|\d+(?:\d+)?(?:\.\d+)?)(?:(?:e|E)(?:-?|\+?)\d+)?)/,
  );

  if (result.matched) {
    return {
      matched: true,
      cursor: result.cursor,
      token: new Token("number", result.value),
    };
  }

  return {
    matched: false,
  };
}

function tokenizeString(source: string, cursor: number): TokenizerResult {
  const result = matchRegex(source, cursor, /^"(?:[^\n"\\]|\\.)*"/);

  if (result.matched) {
    let value = result.value;

    if (
      // Check if we even have a value, dont run the following check if we dont
      value != null &&
      value.length > 0 &&
      // Check if the first or last character is a quotation mark, in which case we would need to remove them
      (value[0] === '"' || value[value.length - 1] === '"') &&
      // Ensure we do not remove quotation marks on a string with no content ("")
      !(value.length === 2 && value[0] === '"' && value[value.length - 1] === '"')
    ) {
      value = value.replace(/^"/, "").replace(/"$/, "");
    }

    return {
      matched: true,
      cursor: result.cursor,
      token: new Token("string", value),
    };
  }

  return {
    matched: false,
  };
}

function tokenizePunctuation(source: string, cursor: number): TokenizerResult {
  for (const token of Object.values(PUNCTUATION_TOKENS)) {
    const matchResult = matchLiteral(source, cursor, token.value);

    if (matchResult.matched) {
      return {
        matched: true,
        token,
        cursor: matchResult.cursor,
      };
    }
  }

  return {
    matched: false,
  };
}

/*
 * Helper Functions
 */

function matchRegex(
  source: string,
  cursor: number,
  regex: RegExp,
): { matched: false } | { matched: true; value: string; cursor: number } {
  const currentSource = source.substr(cursor);
  const match = currentSource.match(regex);

  if (!match || match.length === 0) {
    return {
      matched: false,
    };
  }

  if (match.length === 1) {
    const value = match[0];

    return {
      value,
      matched: true,
      cursor: cursor + value.toString().length,
    };
  }

  // We should not get here, regex passed in here should be designed
  // as such that there is only one Group match. (Use non-capture) groups.
  // Therefore it is most likely a programmer's error if we get here.
  throw new Error("Invalid regex matches");
}

function matchLiteral(
  source: string,
  cursor: number,
  token: string,
): { matched: false } | { matched: true; cursor: number } {
  if (source.substr(cursor, token.length) === token) {
    return {
      matched: true,
      cursor: cursor + token.length,
    };
  }

  return {
    matched: false,
  };
}

function matchStaticToken(source: string, cursor: number, token: Token): TokenizerResult {
  const lookahead = matchLiteral(source, cursor, token.value);

  if (lookahead.matched) {
    return {
      matched: true,
      cursor: lookahead.cursor,
      token,
    };
  }

  return {
    matched: false,
  };
}

src/lib/parser.ts

import { Token } from "./Token";
import { Node, ScalarNode, ObjectNode, ArrayNode } from "./nodes";
import { JsonError } from "./util/JsonError";

export function parse(tokens: Token[]): Node {
  const rootNode = parseSingle(tokens);

  if (tokens.length > 0) {
    throw new JsonError("Unexpected tokens at the end of source", tokens);
  }

  return rootNode;
}

export function parseSingle(tokens: Token[]): Node {
  if (tokens.length === 0) {
    throw new JsonError("Unexpected end of source!", tokens);
  }

  const initialToken = tokens[0];

  if (initialToken.isScalar) {
    return parseScalar(tokens);
  }

  if (initialToken.isObjectOpen) {
    return parseObject(tokens);
  }

  if (initialToken.isArrayOpen) {
    return parseArray(tokens);
  }

  throw new JsonError(
    `Could not parse token of type '${initialToken.type}' at this location`,
    tokens,
  );
}

function parseScalar(tokens: Token[]): ScalarNode {
  const { type, value } = tokens[0];

  if (type === "string") {
    validateString(value, tokens);
  }

  const scalar = new ScalarNode(type, value);

  tokens.shift();

  return scalar;
}

function parseArray(tokens: Token[]): ArrayNode {
  const arrayNode = new ArrayNode();

  // Removes the opening "[" token.
  tokens.shift();

  const firstToken = tokens[0];

  // Empty Array, exit early.
  if (firstToken && firstToken.isArrayClose) {
    tokens.shift();

    return arrayNode;
  }

  while (tokens.length > 0) {
    arrayNode.addChild(parseSingle(tokens));

    // The next token is either a comma or it is the closing bracket.
    // In both cases the token needs to be removed. We just need to keep it around
    // to check if it is a comma.
    const nextToken = tokens.shift();

    // If the next token "after" the value is not a comma, we do not expect
    // any more values. Technically we dont even need the comma, but we are stick
    // to the standard strictly.
    if (nextToken && nextToken.isComma) {
      continue;
    }

    if (nextToken && nextToken.isArrayClose) {
      return arrayNode;
    }

    throw new JsonError("Additional comma at end of array entries", tokens);
  }

  throw new JsonError(
    "Unexpected token at the end of an array entry, most likely a missing comma",
    tokens,
  );
}

function parseObject(tokens: Token[]) {
  const objectNode = new ObjectNode();

  tokens.shift();

  const firstToken = tokens[0];

  // Empty Object, exit early
  if (firstToken && firstToken.isObjectClose) {
    tokens.shift();

    return objectNode;
  }

  while (tokens.length > 0) {
    objectNode.addEntry(parseObjectEntry(tokens));

    const nextToken = tokens.shift();

    // If there is a comma, the json specifies that there *must*
    // be another entry on the object
    if (nextToken && nextToken.isComma) {
      continue;
    }

    // If the next token is not a comma, there are no more entries
    // which means that the next token *must* be a "}
    if (nextToken && nextToken.isObjectClose) {
      return objectNode;
    }

    throw new JsonError(
      "Unexpected token at the end of an object entry, most likely a missing comma",
      tokens,
    );
  }

  throw new JsonError("Unexpected end of source, while parsing object", tokens);
}

function parseObjectEntry(tokens: Token[]) {
  const [keyToken, seperatorToken] = tokens;

  if (!keyToken || !keyToken.isString) {
    throw new JsonError(
      `Unexpected token of type "${keyToken.type}" ("${keyToken.value}") on object key`,
      tokens,
    );
  }

  if (!seperatorToken || !seperatorToken.isColon) {
    throw new JsonError(
      `Unexpected token of type "${seperatorToken.type}" ("${seperatorToken.value}") as object key-value seperator`,
      tokens,
    );
  }

  tokens.splice(0, 2);

  return {
    key: keyToken.value,
    value: parseSingle(tokens),
  };
}

function validateString(value: string, tokens: Token[]) {
  const chars = value.split("");

  for (let index = 0; index < chars.length; index++) {
    const element = chars[index];

    if (
      element === "\t" ||
      element === "\n" ||
      element === "\b" ||
      element === "\f" ||
      element === "\r"
    ) {
      throw new JsonError(
        "Invalid characters in string. Control characters must be escaped!",
        tokens,
      );
    }

    if (element !== "\\") {
      continue;
    }

    if (chars.length <= index + 1) {
      throw new JsonError("Unexpected end of escape-sequence", tokens);
    }

    const escapeCharacter = chars[index + 1];

    if (escapeCharacter === "\\" || escapeCharacter === "/") {
      index++;

      continue;
    }

    if (["b", "f", "n", "r", "t", '"'].includes(escapeCharacter)) {
      continue;
    }

    if (escapeCharacter === "u") {
      if (chars.length >= index + 6) {
        const unicodeEscapeSequence = chars.slice(index + 2, index + 6).join("");

        if (/^[0-9A-Fa-f]{4}$/.test(unicodeEscapeSequence)) {
          index += 5;

          continue;
        } else {
          throw new JsonError("Invalid unicode escape sequence", tokens);
        }
      } else {
        throw new JsonError("Unexpected end of escape-sequence", tokens);
      }
    }

    throw new JsonError("Unrecognized escape sequence", tokens);
  }
}

src/lib/generator.ts

import { JsonArray, JsonObject, JsonValue } from "./types";
import { Node, ObjectNode, ArrayNode, ScalarNode } from "./nodes";

export function convertNodeToJsValue(root: Node): JsonValue {
  if (root instanceof ScalarNode) {
    return scalarToJsValue(root);
  }

  if (root instanceof ObjectNode) {
    const result: JsonObject = {};

    for (const [key, value] of root.entries) {
      result[key] = convertNodeToJsValue(value);
    }

    return result;
  }

  if (root instanceof ArrayNode) {
    const result: JsonArray = [];

    for (const value of root.children) {
      result.push(convertNodeToJsValue(value));
    }

    return result;
  }

  throw new Error(
    `Unknown node type "${root.constructor.name}" found while deserializing tree`,
  );
}

function scalarToJsValue(node: ScalarNode) {
  const { type, value } = node;

  switch (type) {
    case "boolean":
      if (value === "true") {
        return true;
      }

      if (value === "false") {
        return false;
      }

      throw new Error(`Invalid boolean value "${value}" found.`);
    case "null":
      return null;
    case "number":
      return Number(value as string);
    case "string":
      return value;
    default:
      throw new Error(`Unknown node of type "${type}" cannot be converted to a js value`);
  }
}

src/lib/nodes/index.ts

export * from './Node';
export * from './ArrayNode';
export * from './ScalarNode';
export * from './ObjectNode';

src/lib/nodes/Node.ts

/**
 * Simple node base class.
 *
 * This class mainly exists to make typing a little easier.
 */
export class Node {}

src/lib/nodes/ScalarNode.ts

import { Node } from './Node';

export class ScalarNode extends Node {
  public readonly type: string;
  public readonly value: string;

  public constructor(type: string, value: string) {
    super();

    this.type = type;
    this.value = value;
  }
}

src/lib/nodes/ObjectNode.ts

import { Node } from './Node';

export class ObjectNode extends Node {
  public readonly entries: Map<string, Node>;

  public constructor() {
    super();

    this.entries = new Map();
  }

  public addEntry(entry: { key: string, value: Node }): void {
    this.entries.set(entry.key, entry.value);
  }
}

src/lib/nodes/ArrayNode.ts

import { Node } from './Node';

export class ArrayNode extends Node {
  public readonly children: Node[];

  public constructor() {
    super();

    this.children = [];
  }

  public addChild(value: Node): void {
    this.children.push(value);
  }
}

Answer 1

All in all, this is some well-written, well-structured and well-typed code. I like it! I do have a few nitpicks, though:

The type of ScalarNode.type might be a bit too broad. If it were me, I'd probably restrict it to 'string' | 'number' | 'boolean' | 'null'.

The type of ScalarNode.value feels wrong - a ScalarNode with type = 'number' feels like it should have a value which is a number, rather than a string. parseScalar already knows the type, it should be able to ensure the value conforms to that as well.

On a related note, you validate the various escape sequences of strings there, but wouldn't that be a good place to actually parse them? Instead of validateString(value); scalar = new ScalarNode(type, value), why not parsedValue = parseString(value); scalar = new ScalarNode(type, parsedValue)? If we take the value of a string ScalarNode to be the already-parsed value, it means we can, by definition, never have an invalid string ScalarNode.

Personally, I might even be tempted to do that kind of thing while tokenizing. It doesn't make sense to me to have {type: 'number', value: 'just kidding!'} be considered a valid Token - as far as I'm concerned, that's wrong by definition, and "wrong by definition" is exactly the kind of wrong the typechecker should be detecting for me.

It feels a bit odd to allow a Tokenizer that fails to match to still move the cursor. Yes, it's useful for getting past whitespace, but I would argue that tokenizeWhitespace does match the input there, even though it doesn't produce a token. It feels natural to me to have whitespace be a token, the parser can just skip it. Or if not that, it does feel a bit more natural to me to instead of letting a TokenizerResult with matched = false move the cursor, allowing one with matched = true to not contain a token.

Your JSON objects appear to allow the same key to appear multiple times (or at least parseObjectEntry, parseObject and convertNodeToJsValue don't seem to check for that as far as I can tell). When that happens, it seems like you keep the last value. I don't know whether that's the correct behaviour, or even if an object with repeated keys is valid JSON, so I figured I'd point it out.

The instanceof checks in convertNodeToJsValue are a bit awkward. It might be nicer to define the Node interface such that it includes a toJsonValue : () => JsonValue and let each node type deal with its own conversion?

Answer 2

I don't often look at code for compilers/parsers. I did take a course on compilers as a university student and in order to complete the course had to implement a compiler though since then have not really done anything like that.

How readable/understandable is the code?

The code is simple to read and understand. Whitespace follows common conventions accepted by many popular style guides. Indentation is consistent and names are appropriate - for variables, functions, etc.

It might help others with understanding the code if docblocks were added. Some argue that good code is self-documenting though others point out that "You shouldn't document what the code is doing, but you should document why it's doing it.".

Are there any best-practices or techniques I could implement?

There are a couple of techniques that could be used to simplify the code in a couple spots.

return early more often, avoid else

Much of the code returns/throws early, but there is a block towards the end of validateString() in src/lib/parser.ts:

if (escapeCharacter === "u") {
  if (chars.length >= index + 6) {
    const unicodeEscapeSequence = chars.slice(index + 2, index + 6).join("");

    if (/^[0-9A-Fa-f]{4}$/.test(unicodeEscapeSequence)) {
      index += 5;

      continue;
    } else {
      throw new JsonError("Invalid unicode escape sequence", tokens);
    }
  } else {
    throw new JsonError("Unexpected end of escape-sequence", tokens);
  }
}

throw new JsonError("Unrecognized escape sequence", tokens);

By placing the throw statements earlier (which required flipping the logic on the conditions), the indentation levels of subsequent lines can be decreased, and there is no need for the continue statement:

if (escapeCharacter !== "u") {
  throw new JsonError("Unrecognized escape sequence", tokens);
}
if (chars.length < index + 6) {
  throw new JsonError("Unexpected end of escape-sequence", tokens);
}
const unicodeEscapeSequence = chars.slice(index + 2, index + 6).join("");

if (!/^[0-9A-Fa-f]{4}$/.test(unicodeEscapeSequence)) {
  throw new JsonError("Invalid unicode escape sequence", tokens);
}
index += 5;

With such changes the decision tree of the logic could go from looking something like this:

_{screenshot captured from source: Your code sucks, let's fix it - By Rafael Dohms at 15:17}

To this:

_{screenshot captured from source: Your code sucks, let's fix it - By Rafael Dohms at 15:28}

use map method instead of push in loop

In convertNodeToJsValue() of src/lib/generator.ts:

if (root instanceof ArrayNode) {
  const result: JsonArray = [];

  for (const value of root.children) {
    result.push(convertNodeToJsValue(value));
  }

  return result;

Whenever a loop iterates over one array and pushes into another array, the array method map can be used, so the block above can be simplified to the following:

if (root instanceof ArrayNode) {
  return root.children.map(convertNodeToJsValue);
}

Not only does this require fewer lines of code but also the loop iteration function remains pure.

For the next suggestion: performance might likely be impacted so if that is a priority then skip this advice.

The block before that is similar, except keys are set on an object instead of pushing into an array:

if (root instanceof ObjectNode) {
    const result: JsonObject = {};

    for (const [key, value] of root.entries) {
      result[key] = convertNodeToJsValue(value);
  }

   return result;
 }

this can be simplified by converting the entries (iterator values) to an array and using the array method reduce:

if (root instanceof ObjectNode) {
  return Array.from(root.entries).reduce((result: JsonObject, [key, value]) => {
    result[key] = convertNodeToJsValue(value);
    return result;
  }, {});
}

To learn more about methods like map, reduce, etc. check out these functional programming exercises.