Implement a simple json.parse method from 0

JSON is a subset of Javascript, and although you can use eval to convert JSON strings into Javascript objects, this presents security issues

If we want to implement a Json.stringify, we first need to understand the structure of JSON. Through a simple lookup, we can see that a JSON can look like the following

• Literal, includingtrue.false.null
• digital
• string
• Object whose key is a string and whose value can be a JSON value
• The contents of an array can contain any JSON value

Therefore, in Typescript, JSON can be defined as follows

type LiteralValue = boolean | null;
type PrimitiveValue = number | LiteralValue | string;
type JSONArray = (PrimitiveValue | JSONArray | JSONObject)[];
type JSONObject = { [key: string]: PrimitiveValue | JSONArray | JSONObject };
type JSONValue = PrimitiveValue | JSONArray | JSONObject;
Copy the code

JSONValue represents all the possible types that we can present through Json.parse

So, quite naturally, for the three basic types, we need to provide these three methods

Then, for arrays and objects that form nesting structures, we need two other methods, parseObject and parseArray.

Obviously, they indirectly recursively call themselves and methods that convert numbers, strings, and literals. We define a parseJSONValue method that guesses the type of the next value to call the appropriate Parse XXX method.

Also, we need a skipWhitespace method to skip null characters. They have no effect on the result of the JSON transformation

This gives us a general framework for our code

class JSONParser {
  private input: string;
  constructor(input: string) {
    this.input = input;
  }
  
  privateskipWhitespace(cur? :number) :number {}
  privateguessNextValueType(cur? :number): MaybeJSONValue
  privateparseLiteral(cur? :number): ParseResult<LiteralValue>
  privateparseNumber(cur? :number): ParseResult<number>
  privateparseString(cur? :number): ParseResult<string>
  privateparseObject(cur? :number): ParseResult<JSONObject>
  privateparseArray(cur? :number): ParseResult<JSONArray>
  
  privateparseJSON(cur? :number): ParseResult<JSONValue>
  
  // This is a method for external calls
  parse(): string;
}
Copy the code

You also need some type and enumeration definitions

type ParseResult<T extends JSONValue> = {
  success: boolean;

  // If the conversion succeeds, its value represents the position of the last bit of the value in the entire JSON string
  // If it fails, it represents the location of the failure
  position: number; value? : T; };enum MaybeJSONValue {
  LITERAL,
  NUMBER,
  STRING,
  ARRAY,
  OBJECT,
  UNKNOWN,
}
Copy the code

implementation

We have agreed that the cur parameter in all parse methods represents where the input string begins for subsequent conversion operations. The position field in the return value of these functions represents the position at which the current resolution succeeded or failed. As we progress through the conversion, the value of cur increases until the conversion is complete or the conversion fails.

parseLiteral

Literals have fixed values. The literal can be converted simply by identifying the literal string with an equal sign.

  private parseLiteral(cur = 0): ParseResult<LiteralValue> {
    if (this.input[cur] === "t") {
      if (this.input.substring(cur, cur + 4) = = ="true") {
        return {
          success: true.position: cur + 3.value: true}; }}else if (this.input[cur] === "f") {
      if (this.input.substring(cur, cur + 5) = = ="false") {
        return {
          success: true.position: cur + 4.value: false}; }}else if (this.input[cur] === "n") {
      if (this.input.substring(cur, cur + 4) = = ="null") {
        return {
          success: true.position: cur + 3.value: null}; }}return {
      success: false.position: cur,
    };
  }
Copy the code

parseString

There is one detail to note about string length, ‘\n’. Length === 1, the result of executing json.stringify (‘\n’) is ‘\\n’. Obviously, we need a dictionary to convert multiple characters beginning with ‘\\’ before conversion into a single character such as \n.

const ESCAPE_CHAR_MAP = {
  "\ \ \ \": "\ \".'\ \ "': '"'."\\b": "\b"."\\f": "\f"."\\n": "\n"."\\r": "\r"};private parseString(cur = 0): ParseResult<string> {
    if (this.input[cur] ! = ='"') {
      return {
        success: false.position: cur,
      };
    }

    let value = "";
    cur++;
    while (this.input[cur] ! = ='"') {
      if (this.input[cur] === "\ \") {
        const maybeEscapeChar = this.input.slice(cur, cur + 2);
        const ch = ESCAPE_CHAR_MAP[maybeEscapeChar];
        if (ch) {
          value += ch;
          cur += 2;
          continue;
        } else {
          return {
            success: false.position: cur,
          };
        }
      }

      value += this.input[cur];
      cur++;
    }

    return {
      success: true.position: cur,
      value,
    };
  }

Copy the code

parseNumber

Digital transformation is actually more complicated than imagination, the number of the JSON, integer, ordinary floating point number, you can also use like 2 e – 6 scientific notation to represent a floating point number But the official document will have a variety of circumstances are represented using images, although its code to achieve slightly longer, I drew a flow chart to help you understand.

Graph of TD is called [parseNumber] -- > B} {if there is A minus B - > | | C () reads in minus B - > whether | | D {whether to begin with 0} C -- -- -- -- > > D D is | | E read in [0] D - > whether | | F [read non-zero Numbers] F - > G {} if there is a decimal point E > G G -- - > | | H is [read in decimal point] H -- -- > I [read in decimal point Numbers] I -- -- -- -- > > J G whether | | J {if there is a character E or E} J - > K/read E K - > {have a plus or minus sign} L L - > is | | M] [read index of plus or minus K - > whether | | O M - > O [read in scientific notation index] J - > whether | | P O - > P [call parseInt or parseFloat strings that will be read into digital]

  private parseNumber(cur = 0): ParseResult<number> {
    const parseDigit = (cur: number, allowLeadingZero: boolean) = > {
      let dights = "";
      if(! allowLeadingZero &&this.input[cur] === "0") {
        return ["", cur] as const;
      }


      let allowZero = allowLeadingZero;
      while (
        (allowZero ? "0" : "1") < =this.input[cur] &&
        this.input[cur] <= "9"
      ) {
        dights += this.input[cur];
        cur++;
        allowZero = true;
      }
      return [dights, cur - 1] as const;
    };

    let value = "";
    let isFloat = false;

    / / minus
    if (this.input[cur] === "-") {
      value += "-";
      cur++;
    }

    // The number before the decimal point
    if (this.input[cur] === "0") {
      value += "0";
    } else {
      const [dights, endCur] = parseDigit(cur, false);

      // Invalid case 1, which begins with a non-digit or multiple zeros
      if (dights.length === 0) {
        return {
          success: false.position: cur,
        };
      }

      value += dights;
      cur = endCur;
    }

    / / the decimal point
    if (this.input[cur + 1= = =".") {
      isFloat = true;
      value += ".";
      cur++;
      // Input [cur] is the decimal

      // Move to the position after the decimal point
      const [dights, endCur] = parseDigit(cur + 1.true);
      // Invalid case 2, there are no numbers after the decimal point
      if (dights.length === 0) {
        return {
          success: false.position: cur,
        };
      }
      value += dights;
      cur = endCur;
    }

    // The index of scientific notation
    if (this.input[cur + 1= = ="e" || this.input[cur + 1= = ="E") {
      isFloat = true;
      value += "e";
      cur++;
      // This. Input [cur] is e or e
      if (this.input[cur + 1= = ="+" || this.input[cur + 1= = ="-") {
        cur++;
        value += this.input[cur];
        // This. Input [cur] is the symbol
      }

      const [dights, endCur] = parseDigit(cur + 1.false);
      // Illegal case 3, E has no exponent
      if (dights.length === 0) {
        return {
          success: false.position: cur,
        };
      }
      value += dights;
      cur = endCur;
    }

    return {
      success: true.value: isFloat ? parseFloat(value) : parseInt(value, 10),
      position: cur,
    };
  }
Copy the code

parseJSONandguessNextValueType

We need to use guessNextValueType to make a guess at the exact type of the JSONValue that follows. The logic of this guess is very simple: if it starts with a ‘[‘ it is an array, and if it starts with a ‘” it is a string. When we fail to guess, the incoming JSON string is invalid.

  private guessNextValueType(cur = 0): MaybeJSONValue {
    const leadingChar = this.input[cur];
    if (/ [0-9] /.test(leadingChar)) {
      return MaybeJSONValue.NUMBER;
    }

    switch (leadingChar) {
      case "[":
        return MaybeJSONValue.ARRAY;
      case "{":
        return MaybeJSONValue.OBJECT;
      case '"':
        return MaybeJSONValue.STRING;
      case "n":
        return MaybeJSONValue.LITERAL;
      case "t":
        return MaybeJSONValue.LITERAL;
      case "f":
        return MaybeJSONValue.LITERAL;
      default:
        returnMaybeJSONValue.UNKNOWN; }}private parseJSON(cur = 0): ParseResult<JSONValue> {
    const valueType = this.guessNextValueType(cur);
    switch (valueType) {
      case MaybeJSONValue.NUMBER:
        return this.parseNumber(cur);
      case MaybeJSONValue.ARRAY:
        return this.parseArray(cur);
      case MaybeJSONValue.OBJECT:
        return this.parseObject(cur);
      case MaybeJSONValue.STRING:
        return this.parseString(cur);
      case MaybeJSONValue.LITERAL:
        return this.parseLiteral(cur);
      case MaybeJSONValue.UNKNOWN:
        return {
          success: false.position: cur, }; }}Copy the code

parseArray

Once we have parseJSON above, the implementation of parseArray becomes simpler. All we need to do is read the left square bracket and keep calling parseJSON and handling the comma separating elements, putting the converted elements into an array.

  private parseArray(cur = 0): ParseResult<JSONArray> {
    if (this.input[cur] ! = ="[") {
      return {
        success: false.position: cur,
      };
    }
    const result: JSONArray = [];
    cur++;

    let isFirstItem = true;
    while (this.input[cur] ! = ="]") {
      cur = this.skipWhitespace(cur);

      if(! isFirstItem) {if (this.input[cur] ! = =",") {
          return {
            success: false.position: cur,
          };
        }
        cur++;
      }
      const itemResult = this.parseJSON(cur);
      if(! itemResult.success) {return itemResult as ParseResult<JSONArray>;
      }
      cur = itemResult.position + 1; result.push(itemResult.value!) ; isFirstItem =false;
    }

    return {
      success: true.position: cur,
      value: result,
    };
  }
Copy the code

parseObject

Again, we need to do much the same thing as parseArray, except that object has a key, and we need to call parseString to get the key of the object, then call parseJSON to get the value, and finally set the key and its value to the result.

  private parseObject(cur = 0): ParseResult<JSONObject> {
    if (this.input[cur] ! = ="{") {
      return {
        success: false.position: cur,
      };
    }

    const result: JSONObject = {};
    let isFirstItem = true;
    cur++;
    cur = this.skipWhitespace(cur);

    while (this.input[cur] ! = ="}") {
      cur = this.skipWhitespace(cur);
      if(! isFirstItem) {if (this.input[cur] ! = =",") {
          return {
            success: false.position: cur,
          };
        }
        cur++;
      }

      const keyResult = this.parseString(cur);
      if(! keyResult.success) {return keyResult as unknown as ParseResult<JSONObject>;
      }

      cur = keyResult.position;
      cur = this.skipWhitespace(cur);
      cur++;
      if (this.input[cur] ! = =":") {
        return {
          success: false.position: cur,
        };
      }

      const valueResult = this.parseJSON(cur + 1); result[keyResult.value!]  = valueResult.value; isFirstItem =false;
      cur = valueResult.position + 1;
    }

    return {
      success: true.value: result,
      position: cur,
    };
  }
Copy the code

parseMethods and test methodstestmethods

  public parse() {
    const result = this.parseJSON();
    if (result.success) {
      returnresult.value! ; }else {
      throw new Error(`parse error at ${result.position}`); }}Copy the code

function test(input: JSONValue) {
  const parser = new JSONParser(JSON.stringify(input));
  const result = parser.parse();
  if (JSON.stringify(result) ! = =JSON.stringify(input)) {
    throw new Error(`The ${JSON.stringify(result)}! = =The ${JSON.stringify(input)}`); }}Copy the code

Finally, let’s do a simple test

/ / digital
test(0.1);
test(1.1);
test(0);
test(-1);
test(+2);
test(+1e2);
test(+1e-2);
test(123456);
test(1.23456 e2);

/ / string
test("");
test("Hello, world");
test("\n");
test("\b");
test("\f");
test("\r");
test("\ \ \ \ \ \");
test('"');
test('\ \ \ \ "');

/ / literal
test(null);
test(true);
test(false);

/ / array
test([]);
test([0.null.undefined.true.false."", [], [[], [], {}, {value: {}}]);/ / object
test({
  number: 1.string: "".array: [].object: {},
  null: null.boolean: true.nested: {
    number: 1.string: "".array: [123].object: {},
    null: null.boolean: true,}});Copy the code

I used Visual Studio CodeQuokkaExtension that responds to code changes in real time and marks correctly running code to the left. Our tests were cleanThe complete code

type LiteralValue = boolean | null;
type PrimitiveValue = number | LiteralValue | string;
type JSONArray = (PrimitiveValue | JSONArray | JSONObject)[];
type JSONObject = { [key: string]: PrimitiveValue | JSONArray | JSONObject };
type JSONValue = PrimitiveValue | JSONArray | JSONObject;

type ParseResult<T extends JSONValue> = {
  success: boolean;

  // If the conversion succeeds, its value represents the position of the last bit of the value in the entire JSON string
  // If it fails, it represents the location of the failure
  position: number; value? : T; };enum MaybeJSONValue {
  LITERAL,
  NUMBER,
  STRING,
  ARRAY,
  OBJECT,
  UNKNOWN,
}

const ESCAPE_CHAR_MAP = {
  "\ \ \ \": "\ \".'\ \ "': '"'."\\b": "\b"."\\f": "\f"."\\n": "\n"."\\r": "\r"};class JSONParser {
  private input: string;
  constructor(input: string) {
    this.input = input;
  }

  private parseLiteral(cur = 0): ParseResult<LiteralValue> {
    if (this.input[cur] === "t") {
      if (this.input.substring(cur, cur + 4) = = ="true") {
        return {
          success: true.position: cur + 3.value: true}; }}else if (this.input[cur] === "f") {
      if (this.input.substring(cur, cur + 5) = = ="false") {
        return {
          success: true.position: cur + 4.value: false}; }}else if (this.input[cur] === "n") {
      if (this.input.substring(cur, cur + 4) = = ="null") {
        return {
          success: true.position: cur + 3.value: null}; }}return {
      success: false.position: cur,
    };
  }

  private parseNumber(cur = 0): ParseResult<number> {
    const parseDigit = (cur: number, allowLeadingZero: boolean) = > {
      let dights = "";
      if(! allowLeadingZero &&this.input[cur] === "0") {
        return ["", cur] as const;
      }

      let allowZero = allowLeadingZero;
      while (
        (allowZero ? "0" : "1") < =this.input[cur] &&
        this.input[cur] <= "9"
      ) {
        dights += this.input[cur];
        cur++;
        allowZero = true;
      }
      return [dights, cur - 1] as const;
    };

    let value = "";
    let isFloat = false;

    / / minus
    if (this.input[cur] === "-") {
      value += "-";
      cur++;
    }

    // The number before the decimal point
    if (this.input[cur] === "0") {
      value += "0";
    } else {
      const [dights, endCur] = parseDigit(cur, false);

      // Invalid case 1, which begins with a non-digit or multiple zeros
      if (dights.length === 0) {
        return {
          success: false.position: cur,
        };
      }

      value += dights;
      cur = endCur;
    }

    / / the decimal point
    if (this.input[cur + 1= = =".") {
      isFloat = true;
      value += ".";
      cur++;
      // Input [cur] is the decimal

      // Move to the position after the decimal point
      const [dights, endCur] = parseDigit(cur + 1.true);
      // Invalid case 2, there are no numbers after the decimal point
      if (dights.length === 0) {
        return {
          success: false.position: cur,
        };
      }
      value += dights;
      cur = endCur;
    }

    // The index of scientific notation
    if (this.input[cur + 1= = ="e" || this.input[cur + 1= = ="E") {
      isFloat = true;
      value += "e";
      cur++;
      // This. Input [cur] is e or e
      if (this.input[cur + 1= = ="+" || this.input[cur + 1= = ="-") {
        cur++;
        value += this.input[cur];
        // This. Input [cur] is the symbol
      }

      const [dights, endCur] = parseDigit(cur + 1.false);
      // Illegal case 3, E has no exponent
      if (dights.length === 0) {
        return {
          success: false.position: cur,
        };
      }
      value += dights;
      cur = endCur;
    }

    return {
      success: true.value: isFloat ? parseFloat(value) : parseInt(value, 10),
      position: cur,
    };
  }

  private parseString(cur = 0): ParseResult<string> {
    if (this.input[cur] ! = ='"') {
      return {
        success: false.position: cur,
      };
    }

    let value = "";
    cur++;
    while (this.input[cur] ! = ='"') {
      if (this.input[cur] === "\ \") {
        const maybeEscapeChar = this.input.slice(cur, cur + 2);
        const ch = ESCAPE_CHAR_MAP[maybeEscapeChar];
        if (ch) {
          value += ch;
          cur += 2;
          continue;
        } else {
          return {
            success: false.position: cur,
          };
        }
      }

      value += this.input[cur];
      cur++;
    }

    return {
      success: true.position: cur,
      value,
    };
  }

  private skipWhitespace(cur = 0) :number {
    const isWhitespace = (cur: string) = > {
      return (
        cur === "\u0009" ||
        cur === "\u000A" ||
        cur === "\u000D" ||
        cur === "\u0020"
      );
    };

    while (isWhitespace(this.input[cur])) {
      cur++;
    }

    return cur;
  }

  private parseArray(cur = 0): ParseResult<JSONArray> {
    if (this.input[cur] ! = ="[") {
      return {
        success: false.position: cur,
      };
    }
    const result: JSONArray = [];
    cur++;

    let isFirstItem = true;
    while (this.input[cur] ! = ="]") {
      cur = this.skipWhitespace(cur);

      if(! isFirstItem) {if (this.input[cur] ! = =",") {
          return {
            success: false.position: cur,
          };
        }
        cur++;
      }
      const itemResult = this.parseJSON(cur);
      if(! itemResult.success) {return itemResult as ParseResult<JSONArray>;
      }
      cur = itemResult.position + 1; result.push(itemResult.value!) ; isFirstItem =false;
    }

    return {
      success: true.position: cur,
      value: result,
    };
  }

  private parseObject(cur = 0): ParseResult<JSONObject> {
    if (this.input[cur] ! = ="{") {
      return {
        success: false.position: cur,
      };
    }

    const result: JSONObject = {};
    let isFirstItem = true;
    cur++;
    cur = this.skipWhitespace(cur);

    while (this.input[cur] ! = ="}") {
      cur = this.skipWhitespace(cur);
      if(! isFirstItem) {if (this.input[cur] ! = =",") {
          return {
            success: false.position: cur,
          };
        }
        cur++;
      }

      const keyResult = this.parseString(cur);
      if(! keyResult.success) {return keyResult as unknown as ParseResult<JSONObject>;
      }

      cur = keyResult.position;
      cur = this.skipWhitespace(cur);
      cur++;
      if (this.input[cur] ! = =":") {
        return {
          success: false.position: cur,
        };
      }

      const valueResult = this.parseJSON(cur + 1); result[keyResult.value!]  = valueResult.value; isFirstItem =false;
      cur = valueResult.position + 1;
    }

    return {
      success: true.value: result,
      position: cur,
    };
  }

  private guessNextValueType(cur = 0): MaybeJSONValue {
    const leadingChar = this.input[cur];
    if (/ [0-9] /.test(leadingChar)) {
      return MaybeJSONValue.NUMBER;
    }

    switch (leadingChar) {
      case "[":
        return MaybeJSONValue.ARRAY;
      case "{":
        return MaybeJSONValue.OBJECT;
      case '"':
        return MaybeJSONValue.STRING;
      case "n":
        return MaybeJSONValue.LITERAL;
      case "t":
        return MaybeJSONValue.LITERAL;
      case "f":
        return MaybeJSONValue.LITERAL;
      default:
        returnMaybeJSONValue.UNKNOWN; }}private parseJSON(cur = 0): ParseResult<JSONValue> {
    const valueType = this.guessNextValueType(cur);
    switch (valueType) {
      case MaybeJSONValue.NUMBER:
        return this.parseNumber(cur);
      case MaybeJSONValue.ARRAY:
        return this.parseArray(cur);
      case MaybeJSONValue.OBJECT:
        return this.parseObject(cur);
      case MaybeJSONValue.STRING:
        return this.parseString(cur);
      case MaybeJSONValue.LITERAL:
        return this.parseLiteral(cur);
      case MaybeJSONValue.UNKNOWN:
        return {
          success: false.position: cur, }; }}public parse() {
    const result = this.parseJSON();
    if (result.success) {
      returnresult.value! ; }else {
      throw new Error(`parse error at ${result.position}`); }}}function test(input: JSONValue) {
  const parser = new JSONParser(JSON.stringify(input));
  const result = parser.parse();
  if (JSON.stringify(result) ! = =JSON.stringify(input)) {
    throw new Error(`The ${JSON.stringify(result)}! = =The ${JSON.stringify(input)}`); }}/ / digital
test(0.1);
test(1.1);
test(0);
test(-1);
test(+2);
test(+1e2);
test(+1e-2);
test(123456);
test(1.23456 e2);

/ / string
test("");
test("Hello, world");
test("\n");
test("\b");
test("\f");
test("\r");
test("\ \ \ \ \ \");
test('"');
test('\ \ \ \ "');

/ / literal
test(null);
test(true);
test(false);

/ / array
test([]);
test([0.null.undefined.true.false."", [], [[], [], {}, {value: {}}]);/ / object
test({
  number: 1.string: "".array: [].object: {},
  null: null.boolean: true.nested: {
    number: 1.string: "".array: [123].object: {},
    null: null.boolean: true,}});Copy the code