path: root/parse.go

// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later

package lowmemjson

import (
	"fmt"
	"io"
	iofs "io/fs"
	"strings"
)

type RuneType uint8

const (
	RuneTypeError = RuneType(iota)

	RuneTypeSpace // whitespace

	RuneTypeObjectBeg   // '{'
	RuneTypeObjectColon // ':'
	RuneTypeObjectComma // ','
	RuneTypeObjectEnd   // '}'

	RuneTypeArrayBeg   // '['
	RuneTypeArrayComma // ','
	RuneTypeArrayEnd   // ']'

	RuneTypeStringBeg   // opening '"'
	RuneTypeStringChar  // normal character
	RuneTypeStringEsc   // backslash
	RuneTypeStringEsc1  // single-char after a backslash
	RuneTypeStringEscU  // \uABCD : u
	RuneTypeStringEscUA // \uABCD : A
	RuneTypeStringEscUB // \uABCD : B
	RuneTypeStringEscUC // \uABCD : C
	RuneTypeStringEscUD // \uABCD : D
	RuneTypeStringEnd   // closing '"'

	RuneTypeNumberIntNeg
	RuneTypeNumberIntZero
	RuneTypeNumberIntDig
	RuneTypeNumberFracDot
	RuneTypeNumberFracDig
	RuneTypeNumberExpE
	RuneTypeNumberExpSign
	RuneTypeNumberExpDig

	RuneTypeTrueT
	RuneTypeTrueR
	RuneTypeTrueU
	RuneTypeTrueE

	RuneTypeFalseF
	RuneTypeFalseA
	RuneTypeFalseL
	RuneTypeFalseS
	RuneTypeFalseE

	RuneTypeNullN
	RuneTypeNullU
	RuneTypeNullL1
	RuneTypeNullL2
)

func (t RuneType) String() string {
	str, ok := map[RuneType]string{
		RuneTypeError: "x",

		RuneTypeSpace: " ",

		RuneTypeObjectBeg:   "{",
		RuneTypeObjectColon: ":",
		RuneTypeObjectComma: "o",
		RuneTypeObjectEnd:   "}",

		RuneTypeArrayBeg:   "[",
		RuneTypeArrayComma: "a",
		RuneTypeArrayEnd:   "]",

		RuneTypeStringBeg:   "“",
		RuneTypeStringChar:  "c",
		RuneTypeStringEsc:   "\\",
		RuneTypeStringEsc1:  "b",
		RuneTypeStringEscU:  "u",
		RuneTypeStringEscUA: "A",
		RuneTypeStringEscUB: "B",
		RuneTypeStringEscUC: "C",
		RuneTypeStringEscUD: "D",
		RuneTypeStringEnd:   "”",

		RuneTypeNumberIntNeg:  "-",
		RuneTypeNumberIntZero: "0",
		RuneTypeNumberIntDig:  "1",
		RuneTypeNumberFracDot: ".",
		RuneTypeNumberFracDig: "2",
		RuneTypeNumberExpE:    "e",
		RuneTypeNumberExpSign: "+",
		RuneTypeNumberExpDig:  "3",

		RuneTypeTrueT: "𝕥", // double-struck
		RuneTypeTrueR: "𝕣",
		RuneTypeTrueU: "𝕦",
		RuneTypeTrueE: "𝕖",

		RuneTypeFalseF: "𝔣", // fraktur
		RuneTypeFalseA: "𝔞",
		RuneTypeFalseL: "𝔩",
		RuneTypeFalseS: "𝔰",
		RuneTypeFalseE: "𝔢",

		RuneTypeNullN:  "ⓝ", // circled
		RuneTypeNullU:  "ⓤ",
		RuneTypeNullL1: "ⓛ",
		RuneTypeNullL2: "Ⓛ", // +uppercase
	}[t]
	if ok {
		return str
	}
	return fmt.Sprintf("<%d>", t)
}

func (t RuneType) IsNumber() bool {
	return RuneTypeNumberIntNeg <= t && t <= RuneTypeNumberExpDig
}

// { waiting for key to start or '}'
// ” reading key / waiting for colon
// : waiting for value to start
// , reading value / waiting for ',' or '}'
//
// {"x":"y","a":"b"}
//
// {       {
// ”“      {"
// ”“      {"x
// ”       {"x"
// :       {"x":
// o“      {"x":"
// o“      {"x":"y
// o       {"x":"y"
// {       {"x":"y",
// ”“      {"x":"y","
// ”“      {"x":"y","a
// ”       {"x":"y","a"
// :       {"x":"y","a":
// o“      {"x":"
// o“      {"x":"y
// o       {"x":"y"
//
// [ waiting for item to start or ']'
// a reading item / waiting for ',' or ']'

type parseState func(rune) (RuneType, error)

type Parser struct {
	err    error
	closed bool

	bailAfterCurrent bool // bad hack

	stack []RuneType
}

// public API //////////////////////////////////////////////////////////////////////////////////////

func (par *Parser) HandleRune(c rune) (typ RuneType, err error) {
	if par.closed {
		return RuneTypeError, iofs.ErrClosed
	}
	if par.err != nil {
		return RuneTypeError, par.err
	}
	return par.handleRune(c)
}

func (par *Parser) HandleEOF() error {
	if par.closed {
		return iofs.ErrClosed
	}
	if par.err == nil {
		switch len(par.stack) {
		case 0:
			par.err = nil
		case 1:
			if par.stack[0].IsNumber() {
				_, par.err = par.handleRune('\n')
				break
			}
			fallthrough
		default:
			par.err = io.ErrUnexpectedEOF
		}
	}
	par.closed = true
	return par.err
}

// internal ////////////////////////////////////////////////////////////////////////////////////////

func (par *Parser) pushState(state RuneType) RuneType {
	par.stack = append(par.stack, state)
	return state
}
func (par *Parser) replaceState(state RuneType) RuneType {
	par.stack[len(par.stack)-1] = state
	return state
}
func (par *Parser) popState() {
	par.stack = par.stack[:len(par.stack)-1]
}

func (par *Parser) stackString() string {
	var buf strings.Builder
	for _, s := range par.stack {
		buf.WriteString(s.String())
	}
	return buf.String()
}

func (par *Parser) handleRune(c rune) (RuneType, error) {
	if len(par.stack) == 0 {
		par.pushState(RuneTypeError)
	}
	switch par.stack[len(par.stack)-1] {
	// any /////////////////////////////////////////////////////////////////////////////////////
	case RuneTypeError:
		switch c {
		case 0x0020, 0x000A, 0x000D, 0x0009:
			return RuneTypeSpace, nil
		case '{':
			return par.replaceState(RuneTypeObjectBeg), nil
		case '[':
			return par.replaceState(RuneTypeArrayBeg), nil
		case '"':
			return par.replaceState(RuneTypeStringBeg), nil
		case '-':
			return par.replaceState(RuneTypeNumberIntNeg), nil
		case '0':
			return par.replaceState(RuneTypeNumberIntZero), nil
		case '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return par.replaceState(RuneTypeNumberIntDig), nil
		case 't':
			return par.replaceState(RuneTypeTrueT), nil
		case 'f':
			return par.replaceState(RuneTypeFalseF), nil
		case 'n':
			return par.replaceState(RuneTypeNullN), nil
		default:
			return RuneTypeError, fmt.Errorf("any: unexpected character: %q", c)
		}
	// object //////////////////////////////////////////////////////////////////////////////////
	case RuneTypeObjectBeg: // waiting for key to start or '}'
		switch c {
		case 0x0020, 0x000A, 0x000D, 0x0009:
			return RuneTypeSpace, nil
		case '"':
			par.replaceState(RuneTypeStringEnd)
			return par.pushState(RuneTypeStringBeg), nil
		case '}':
			par.popState()
			return RuneTypeObjectEnd, nil
		default:
			return RuneTypeError, fmt.Errorf("object: unexpected character: %q", c)
		}
	case RuneTypeStringEnd: // waiting for ':'
		switch c {
		case 0x0020, 0x000A, 0x000D, 0x0009:
			return RuneTypeSpace, nil
		case ':':
			par.replaceState(RuneTypeObjectComma)
			par.pushState(RuneTypeError)
			return RuneTypeObjectColon, nil
		default:
			return RuneTypeError, fmt.Errorf("object member: unexpected character: %q", c)
		}
	case RuneTypeObjectComma: // waiting for ',' or '}'
		switch c {
		case 0x0020, 0x000A, 0x000D, 0x0009:
			return RuneTypeSpace, nil
		case ',':
			par.replaceState(RuneTypeObjectBeg)
			return RuneTypeObjectComma, nil
		case '}':
			par.popState()
			return RuneTypeObjectEnd, nil
		default:
			return RuneTypeError, fmt.Errorf("object member: unexpected character: %q", c)
		}
	// array ///////////////////////////////////////////////////////////////////////////////////
	case RuneTypeArrayBeg: // waiting for item to start or ']'
		switch c {
		case 0x0020, 0x000A, 0x000D, 0x0009:
			return RuneTypeSpace, nil
		case ']':
			par.popState()
			return RuneTypeArrayEnd, nil
		default:
			par.replaceState(RuneTypeArrayComma)
			par.pushState(RuneTypeError)
			return par.handleRune(c)
		}
	case RuneTypeArrayComma: // waiting for ',' or ']'
		switch c {
		case 0x0020, 0x000A, 0x000D, 0x0009:
			return RuneTypeSpace, nil
		case ',':
			par.replaceState(RuneTypeArrayBeg)
			return RuneTypeArrayComma, nil
		case ']':
			par.popState()
			return RuneTypeArrayEnd, nil
		default:
			return RuneTypeError, fmt.Errorf("array: unexpected character: %q", c)
		}
	// string //////////////////////////////////////////////////////////////////////////////////
	case RuneTypeStringBeg: // waiting for char or '"'
		switch {
		case c == '\\':
			return par.replaceState(RuneTypeStringEsc), nil
		case c == '"':
			par.popState()
			return RuneTypeStringEnd, nil
		case 0x0020 <= c && c <= 0x10FFFF:
			return RuneTypeStringChar, nil
		default:
			return RuneTypeError, fmt.Errorf("string: unexpected character: %q", c)
		}
	case RuneTypeStringEsc: // waiting for escape char
		switch c {
		case '"', '\\', '/', 'b', 'f', 'n', 'r', 't':
			par.replaceState(RuneTypeStringBeg)
			return RuneTypeStringEsc1, nil
		case 'u':
			return par.replaceState(RuneTypeStringEscU), nil
		default:
			return RuneTypeError, fmt.Errorf("string backslash sequence: unexpected character: %q", c)
		}
	case RuneTypeStringEscU:
		if _, ok := hex2int(c); ok {
			return par.replaceState(RuneTypeStringEscUA), nil
		} else {
			return RuneTypeError, fmt.Errorf("string unicode sequence: unexpected character: %q", c)
		}
	case RuneTypeStringEscUA:
		if _, ok := hex2int(c); ok {
			return par.replaceState(RuneTypeStringEscUB), nil
		} else {
			return RuneTypeError, fmt.Errorf("string unicode sequence: unexpected character: %q", c)
		}
	case RuneTypeStringEscUB:
		if _, ok := hex2int(c); ok {
			return par.replaceState(RuneTypeStringEscUC), nil
		} else {
			return RuneTypeError, fmt.Errorf("string unicode sequence: unexpected character: %q", c)
		}
	case RuneTypeStringEscUC:
		if _, ok := hex2int(c); ok {
			par.replaceState(RuneTypeStringBeg)
			return RuneTypeStringEscUD, nil
		} else {
			return RuneTypeError, fmt.Errorf("string unicode sequence: unexpected character: %q", c)
		}
	// number //////////////////////////////////////////////////////////////////////////////////
	//
	// Here's a flattened drawing of the syntax diagram from www.json.org :
	//
	//      [------------ integer ----------][-- fraction ---][-------- exponent -------]
	//     >─╮─────╭─╮─"0"───────╭─────────╭──╮─────────────╭──╮───────────────────────╭─>
	//       │     │ │           │         │  │             │  │                       │
	//       ╰─"-"─╯ ╰─digit 1-9─╯─╭digit╮─╯  ╰─"."─╭digit╮─╯  ╰─"e"─╭─╮─────╭─╭digit╮─╯
	//                             ╰──<──╯          ╰──<──╯    │     │ │     │ ╰──<──╯
	//                                                         ╰─"E"─╯ ╰─"-"─╯
	//                                                                 │     │
	//                                                                 ╰─"+"─╯
	//
	// Now here it is slightly redrawn, and with each distinct state our
	// parser can be in marked with a single-capital-letter:
	//
	//        [-------------- integer ------------][--------- fraction --------][--------- exponent ---------]
	//     >─A─╮───────╭──╮─"0"─────────C─╭─────────╮──────────────────╭─────────╮──────────────────────────╭─>
	//         │       │  │               │         │                  │         │                          │
	//         ╰─"-"─B─╯  ╰─digit 1-9─╭─D─╯─digit╮  ╰─"."─E─digit──╭─F─╯─digit╮  ╰─"e"─╭─G─╮─────╭─╭digit─I─╯
	//                                ╰────<─────╯                 ╰────<─────╯  │     │   │     H ╰────<───╯
	//                                                                           ╰─"E"─╯   ╰─"-"─╯
	//                                                                                     │     │
	//                                                                                     ╰─"+"─╯
	//
	// You may notice that each of these states may be uniquely identified
	// by the last-read RuneType:
	//
	//     A = (nothing yet)
	//     B = IntNeg
	//     C = IntZero
	//     D = IntDig
	//     E = FracDot
	//     F = FracDig
	//     G = ExpE
	//     H = ExpSign
	//     I = ExpDig
	//
	// The 'A' state is part of the RuneTypeError "any" case
	// above, and the remainder follow:
	case RuneTypeNumberIntNeg: // B
		switch c {
		case '0':
			return par.replaceState(RuneTypeNumberIntZero), nil
		case '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return par.replaceState(RuneTypeNumberIntDig), nil
		default:
			return RuneTypeError, fmt.Errorf("number: unexpected character: %q", c)
		}
	case RuneTypeNumberIntZero: // C
		switch c {
		case '.':
			return par.replaceState(RuneTypeNumberFracDot), nil
		case 'e', 'E':
			return par.replaceState(RuneTypeNumberExpE), nil
		default:
			par.popState()
			return par.handleRune(c)
		}
	case RuneTypeNumberIntDig: // D
		switch c {
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return par.replaceState(RuneTypeNumberIntDig), nil
		case '.':
			return par.replaceState(RuneTypeNumberFracDot), nil
		case 'e', 'E':
			return par.replaceState(RuneTypeNumberExpE), nil
		default:
			par.popState()
			return par.handleRune(c)
		}
	case RuneTypeNumberFracDot: // E
		switch c {
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return par.replaceState(RuneTypeNumberFracDig), nil
		default:
			return RuneTypeError, fmt.Errorf("number: unexpected character: %q", c)
		}
	case RuneTypeNumberFracDig: // F
		switch c {
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return par.replaceState(RuneTypeNumberFracDig), nil
		case 'e', 'E':
			return par.replaceState(RuneTypeNumberExpE), nil
		default:
			par.popState()
			return par.handleRune(c)
		}
	case RuneTypeNumberExpE: // G
		switch c {
		case '-', '+':
			return par.replaceState(RuneTypeNumberExpSign), nil
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return par.replaceState(RuneTypeNumberExpDig), nil
		default:
			return RuneTypeError, fmt.Errorf("number: unexpected character: %c", c)
		}
	case RuneTypeNumberExpSign: // H
		switch c {
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return par.replaceState(RuneTypeNumberExpDig), nil
		default:
			return RuneTypeError, fmt.Errorf("number: unexpected character: %c", c)
		}
	case RuneTypeNumberExpDig: // I
		switch c {
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return par.replaceState(RuneTypeNumberExpDig), nil
		default:
			par.popState()
			return par.handleRune(c)
		}
	// literals ////////////////////////////////////////////////////////////////////////////////
	// true
	case RuneTypeTrueT:
		return par.expectRune(c, 'r', RuneTypeTrueR, "true", false)
	case RuneTypeTrueR:
		return par.expectRune(c, 'u', RuneTypeTrueU, "true", false)
	case RuneTypeTrueU:
		return par.expectRune(c, 'e', RuneTypeTrueE, "true", true)
	// false
	case RuneTypeFalseF:
		return par.expectRune(c, 'a', RuneTypeFalseA, "false", false)
	case RuneTypeFalseA:
		return par.expectRune(c, 'l', RuneTypeFalseL, "false", false)
	case RuneTypeFalseL:
		return par.expectRune(c, 's', RuneTypeFalseS, "false", false)
	case RuneTypeFalseS:
		return par.expectRune(c, 'e', RuneTypeFalseE, "false", true)
	// null
	case RuneTypeNullN:
		return par.expectRune(c, 'u', RuneTypeNullU, "null", false)
	case RuneTypeNullU:
		return par.expectRune(c, 'l', RuneTypeNullL1, "null", false)
	case RuneTypeNullL1:
		return par.expectRune(c, 'l', RuneTypeNullL2, "null", true)
	default:
		panic(fmt.Errorf(`invalid stack: "%s"`, par.stackString()))
	}
}

func (par *Parser) expectRune(c, exp rune, typ RuneType, context string, pop bool) (RuneType, error) {
	if c != exp {
		return RuneTypeError, fmt.Errorf("%s: unexpected character: %q", context, c)
	}
	if pop {
		par.popState()
		return typ, nil
	} else {
		return par.replaceState(typ), nil
	}
}