packages /

json 0.1.0

Converts JSON text (RFC 8259) to and from the core Value tree, and to and from your own types through the compiler-derived to_value/from_value.

files / src/lib.auk 18.5 kB · 558 lines

/// JSON text <-> the core `Value` tree (RFC 8259). Pure: no effects.

/// Why `parse` failed. Every variant carries the 1-based line and column (counted in chars).
pub enum JsonErr {
  Unexpected(found: char, line: int, col: int),  // a char that can't appear here
  Eof(line: int, col: int),                      // the text ended mid-value
  BadNumber(text: str, line: int, col: int),     // e.g. `01`, `1.`, `-`, `1e`
  BadEscape(text: str, line: int, col: int),     // e.g. `\x`, or a lone surrogate `\ud83d`
  ControlChar(line: int, col: int),              // a raw U+0000..U+001F inside a string
  TooDeep(line: int, col: int),                  // arrays/objects nested deeper than MAX_DEPTH
}

/// The deepest nesting `parse` accepts; deeper input is a `TooDeep` error, not a stack overflow.
imprint MAX_DEPTH = 512

/// A one-line description of a parse error, e.g. `2:11: unexpected '}'`.
pub fn message(e: JsonErr): str
fn message(Unexpected(c, l, k)): str = "{l}:{k}: unexpected '{c}'"
fn message(Eof(l, k)): str = "{l}:{k}: unexpected end of input"
fn message(BadNumber(t, l, k)): str = "{l}:{k}: bad number '{t}'"
fn message(BadEscape(t, l, k)): str = "{l}:{k}: bad escape '{t}'"
fn message(ControlChar(l, k)): str = "{l}:{k}: control character in string (escape it)"
fn message(TooDeep(l, k)): str = "{l}:{k}: nested deeper than {MAX_DEPTH}"

// ---- parser: a cursor over the chars; loops for anything long, recursion only per nesting level ----

struct P { cs: [char], i: int }

/// Parse JSON text (RFC 8259) into a `Value`. Integers become `Int` (or `Float` if they don't fit
/// in 64 bits); a number with a fraction or exponent becomes `Float`. A repeated object key keeps
/// its last value. Surrounding whitespace is allowed; anything else after the value is an error.
pub fn parse(s: str): Value!JsonErr {
  var p = P { cs: s.chars(), i: 0 }
  let v = value(&p, 0)?
  p.skip_ws()
  if p.i < p.cs.len() { fail(p.unexpected()) }
  v
}

fn peek(p: P): char? = p.cs.get(p.i)
fn at(p: P, c: char): bool = p.i < p.cs.len() && p.cs[p.i] == c
fn at_digit(p: P): bool = p.i < p.cs.len() && digit(p.cs[p.i])
fn digit(c: char): bool = "0123456789".contains(c)

fn skip_ws(p: var P) {
  while p.i < p.cs.len() && " \t\n\r".contains(p.cs[p.i]) { p.i += 1 }
}

// 1-based position of index i; only computed on the error path.
fn line(cs: [char], i: int): int = cs.take(i).filter(c => c == '\n').len() + 1
fn col(cs: [char], i: int): int = cs.take(i).reverse().take_while(c => c != '\n').len() + 1

fn text(cs: [char], from: int, to: int): str {
  let end = if to < cs.len() { to } else { cs.len() }  // bad_number may ask for one past the end
  core.str(cs[from..end])
}

fn too_deep(p: P): JsonErr = TooDeep(line(p.cs, p.i), col(p.cs, p.i))

fn unexpected(p: P): JsonErr {
  let (l, k) = (line(p.cs, p.i), col(p.cs, p.i))
  match p.peek() {
    some(c) => Unexpected(c, l, k)
    none => Eof(l, k)
  }
}

// depth = how many arrays/objects enclose this value
fn value(p: var P, depth: int): Value!JsonErr {
  p.skip_ws()
  match p.peek() {
    some(c) when (c == '[' || c == '{') && depth >= MAX_DEPTH => fail(p.too_deep())
    some('{') => object(&p, depth + 1)
    some('[') => array(&p, depth + 1)
    some('"') => Str(string(&p)?)
    some('t') => word(&p, "true", Bool(true))
    some('f') => word(&p, "false", Bool(false))
    some('n') => word(&p, "null", Null)
    some(c) when c == '-' || digit(c) => number(&p)
    _ => fail(p.unexpected())
  }
}

fn word(p: var P, w: str, v: Value): Value!JsonErr {
  for c in w.chars() {
    if !p.at(c) { fail(p.unexpected()) }
    p.i += 1
  }
  v
}

fn array(p: var P, depth: int): Value!JsonErr {
  p.i += 1  // [
  var xs: [Value] = []
  p.skip_ws()
  if p.at(']') {
    p.i += 1
    return List(xs)
  }
  loop {
    xs.push(value(&p, depth)?)
    p.skip_ws()
    if p.at(',') {
      p.i += 1
    } else if p.at(']') {
      p.i += 1
      break List(xs)
    } else {
      fail(p.unexpected())
    }
  }
}

fn object(p: var P, depth: int): Value!JsonErr {
  p.i += 1  // {
  var m: {str: Value} = {}
  p.skip_ws()
  if p.at('}') {
    p.i += 1
    return Map(m)
  }
  loop {
    p.skip_ws()
    if !p.at('"') { fail(p.unexpected()) }
    let k = string(&p)?
    p.skip_ws()
    if !p.at(':') { fail(p.unexpected()) }
    p.i += 1
    m[k] = value(&p, depth)?
    p.skip_ws()
    if p.at(',') {
      p.i += 1
    } else if p.at('}') {
      p.i += 1
      break Map(m)
    } else {
      fail(p.unexpected())
    }
  }
}

// p is on the opening quote; leaves p just past the closing quote.
fn string(p: var P): str!JsonErr {
  p.i += 1
  var out: [str] = []
  loop {
    let c = p.peek() else fail(p.unexpected())
    match c {
      '"' => {
        p.i += 1
        break out.join("")
      }
      '\\' => out.push(escape(&p)?)
      _ when control(c) => fail(ControlChar(line(p.cs, p.i), col(p.cs, p.i)))
      _ => {
        out.push("{c}")
        p.i += 1
      }
    }
  }
}

// p is on the backslash.
fn escape(p: var P): str!JsonErr {
  let start = p.i
  p.i += 1
  let c = p.peek() else fail(p.unexpected())
  p.i += 1
  match c {
    '"' => "\""
    '\\' => "\\"
    '/' => "/"
    'b' => "\u{8}"
    'f' => "\u{c}"
    'n' => "\n"
    'r' => "\r"
    't' => "\t"
    'u' => unicode(&p, start)?
    _ => fail(BadEscape("\\{c}", line(p.cs, start), col(p.cs, start)))
  }
}

// p is just past `\u`; start is the backslash. Joins a UTF-16 surrogate pair into one code point.
fn unicode(p: var P, start: int): str!JsonErr {
  let hi = hex4(&p)?
  if hi < 0xD800 || hi > 0xDFFF { return "{char(hi)!}" }  // not a surrogate, so a valid char
  let lone = BadEscape(p.cs.text(start, p.i), line(p.cs, start), col(p.cs, start))
  if hi > 0xDBFF || !p.at('\\') { fail(lone) }  // a low surrogate first, or nothing after the high one
  p.i += 1
  if !p.at('u') { fail(lone) }
  p.i += 1
  let lo = hex4(&p)?
  if lo < 0xDC00 || lo > 0xDFFF {
    fail(BadEscape(p.cs.text(start, p.i), line(p.cs, start), col(p.cs, start)))
  }
  "{char(0x10000 + (hi - 0xD800) * 0x400 + (lo - 0xDC00))!}"  // always <= U+10FFFF
}

fn hex4(p: var P): int!JsonErr {
  var n = 0
  for _ in 0..4 {
    let c = p.peek() else fail(p.unexpected())
    let d = hex_val(c) else fail(p.unexpected())
    n = n * 16 + d
    p.i += 1
  }
  n
}

fn hex_val(c: char): int? {
  let i = "0123456789abcdefABCDEF".chars().find_index(d => d == c)?
  if i < 16 { i } else { i - 6 }
}

// U+0000..U+001F
fn control(c: char): bool = int(c) < 0x20

// p is on `-` or a digit. Grammar: -? (0 | [1-9][0-9]*) (. [0-9]+)? ([eE] [+-]? [0-9]+)?
fn number(p: var P): Value!JsonErr {
  let start = p.i
  if p.at('-') { p.i += 1 }
  if p.at('0') {
    p.i += 1
    if p.at_digit() { fail(p.bad_number(start)) }  // leading zero
  } else {
    p.digits(start)?
  }
  var frac = false
  if p.at('.') {
    p.i += 1
    p.digits(start)?
    frac = true
  }
  if p.at('e') || p.at('E') {
    p.i += 1
    if p.at('+') || p.at('-') { p.i += 1 }
    p.digits(start)?
    frac = true
  }
  let t = p.cs.text(start, p.i)
  let f = float.parse(t) else fail(p.bad_number(start))
  if frac { return Float(f) }
  Int(int.parse(t) else return Float(f))  // wider than 64 bits: keep it as a Float
}

// one or more digits
fn digits(p: var P, start: int): ()!JsonErr {
  let from = p.i
  while p.at_digit() { p.i += 1 }
  if p.i == from { fail(p.bad_number(start)) }
}

// the number so far plus the offending char, positioned at the number's start
fn bad_number(p: P, start: int): JsonErr =
  BadNumber(p.cs.text(start, p.i + 1), line(p.cs, start), col(p.cs, start))

// ---- writer ----

/// Compact JSON text: no whitespace, object keys in sorted order. A `Float` always keeps a `.` or
/// exponent so it reads back as a `Float`; NaN and infinities (which JSON can't express) become `null`.
pub fn str(v: Value): str = render(v, "")

/// Indented JSON text: 2 spaces per level, `"key": value`, object keys in sorted order.
/// Empty arrays and objects stay on one line (`[]`, `{}`).
pub fn pretty(v: Value): str = render(v, "  ")

fn render(v: Value, step: str): str {
  var out: [str] = []
  emit(v, &out, "", step)
  out.join("")
}

// ind = the current indent; step = "" for compact output, "  " for pretty
fn emit(Null, out: var [str], _: str, _: str) { out.push("null") }
fn emit(Bool(b), out: var [str], _: str, _: str) { out.push(if b { "true" } else { "false" }) }
fn emit(Int(n), out: var [str], _: str, _: str) { out.push("{n}") }
fn emit(Float(f), out: var [str], _: str, _: str) { out.push(num(f)) }
fn emit(Str(s), out: var [str], _: str, _: str) { out.push(quote(s)) }
fn emit(List(xs), out: var [str], ind: str, step: str) {
  out.push("[")
  for i, x in xs {
    if i > 0 { out.push(",") }
    out.newline(ind + step, step)
    emit(x, &out, ind + step, step)
  }
  if xs.len() > 0 { out.newline(ind, step) }
  out.push("]")
}
fn emit(Map(m), out: var [str], ind: str, step: str) {
  out.push(r"{")
  for i, k in m.keys().sort() {
    if i > 0 { out.push(",") }
    out.newline(ind + step, step)
    out.push(quote(k))
    out.push(if step == "" { ":" } else { ": " })
    emit(m[k], &out, ind + step, step)
  }
  if m.len() > 0 { out.newline(ind, step) }
  out.push(r"}")
}

fn newline(out: var [str], ind: str, step: str) {
  if step != "" { out.push("\n" + ind) }
}

fn num(f: float): str when f - f != 0.0 = "null"  // NaN or ±inf
fn num(f: float): str = "{f}"                     // shortest exact form, e.g. "1.0", "0.1"

fn quote(s: str): str = "\"" + s.chars().map(c => esc(c)).join("") + "\""

fn esc('"'): str = "\\\""
fn esc('\\'): str = "\\\\"
fn esc('\n'): str = "\\n"
fn esc('\r'): str = "\\r"
fn esc('\t'): str = "\\t"
fn esc(c: char): str when control(c) = "\\u00{hex_digit(int(c) / 16)}{hex_digit(int(c) % 16)}"
fn esc(c: char): str = "{c}"

fn hex_digit(n: int): char = "0123456789abcdef"[n]

// ---- typed decode / encode ----

/// Parse JSON text and convert it with the compiler-derived `from_value`. The target type comes
/// from the annotation at the call site: `let ts: [Todo] = json.decode(s)?`. Fails with the
/// parse error (a `JsonErr`, converted to `Err`) or the `from_value` error on a shape mismatch.
pub fn decode<T: Data>(s: str): T! = from_value(parse(s)?)

/// Convert any value with the derived `to_value` and write it as compact JSON (see `str`).
pub fn encode<T: Data>(x: T): str = str(to_value(x))

// ---- tests ----

test "literals and whitespace" {
  assert parse("null")? == Null
  assert parse("true")? == Bool(true)
  assert parse("false")? == Bool(false)
  assert parse(" \t\r\n 42 \n")? == Int(42)
  assert parse("\"\"")? == Str("")
  assert parse("nul") is err(Eof(1, 4))
  assert parse("nulL") is err(Unexpected('L', 1, 4))
  assert parse("True") is err(Unexpected('T', 1, 1))
}

test "numbers" {
  assert parse("0")? == Int(0)
  assert parse("-0")? == Int(0)
  assert parse("123")? == Int(123)
  assert parse("-7")? == Int(-7)
  assert parse("9223372036854775807")? == Int(9_223_372_036_854_775_807)
  assert parse("9223372036854775808")? is Float(_)  // too wide for int
  assert parse("1.5")? == Float(1.5)
  assert parse("-0.25")? == Float(-0.25)
  assert parse("1e3")? == Float(1000.0)
  assert parse("1E+2")? == Float(100.0)
  assert parse("2.5e-3")? == Float(0.0025)
  assert parse("10.0")? == Float(10.0)  // a fraction makes it a Float
  assert parse("[1,2.0]")? == List([Int(1), Float(2.0)])
}

test "bad numbers" {
  assert parse("01") is err(BadNumber("01", 1, 1))
  assert parse("-01") is err(BadNumber("-01", 1, 1))
  assert parse("1.") is err(BadNumber("1.", 1, 1))
  assert parse("1.x") is err(BadNumber("1.x", 1, 1))
  assert parse("-") is err(BadNumber("-", 1, 1))
  assert parse("-a") is err(BadNumber("-a", 1, 1))
  assert parse("1e") is err(BadNumber("1e", 1, 1))
  assert parse("1e+") is err(BadNumber("1e+", 1, 1))
  assert parse("[1, 2.e5]") is err(BadNumber("2.e", 1, 5))
  assert parse(".5") is err(Unexpected('.', 1, 1))
  assert parse("+1") is err(Unexpected('+', 1, 1))
  assert parse("0x1f") is err(Unexpected('x', 1, 2))
}

test "strings and escapes" {
  assert parse("\"hello, world\"")? == Str("hello, world")
  assert parse("\"\\\" \\\\ \\/ \\n \\r \\t\"")? == Str("\" \\ / \n \r \t")
  assert parse("\"\\b\\f\"")? == Str("\u{8}\u{c}")
  assert parse("\"\\u0041\\u00e9\\u20AC\"")? == Str("Aé€")
  assert parse("\"\\u0000\"")? == Str("\0")
  assert parse("\"\\ud83d\\ude00\"")? == Str("😀")    // surrogate pair
  assert parse("\"\\uD83D\\uDE00!\"")? == Str("😀!")  // upper-case hex
  assert parse("\"é😀 raw\"")? == Str("é😀 raw")       // non-ASCII passes through
  assert parse("\"a\\u0022b\"")? == Str("a\"b")
}

test "bad strings" {
  assert parse("\"abc") is err(Eof(1, 5))
  assert parse("\"abc\\") is err(Eof(1, 6))
  assert parse("\"\\x\"") is err(BadEscape("\\x", 1, 2))
  assert parse("\"\\u12g4\"") is err(Unexpected('g', 1, 6))
  assert parse("\"\\u12\"") is err(Unexpected('"', 1, 6))
  assert parse("\"\\ud83d\"") is err(BadEscape("\\ud83d", 1, 2))                // lone high
  assert parse("\"\\ude00\"") is err(BadEscape("\\ude00", 1, 2))                // lone low
  assert parse("\"\\ud83d\\n\"") is err(BadEscape("\\ud83d", 1, 2))             // high + other escape
  assert parse("\"\\ud83d\\u0041\"") is err(BadEscape("\\ud83d\\u0041", 1, 2))  // high + non-low
  assert parse("\"a\nb\"") is err(ControlChar(1, 3))                            // raw newline
  assert parse("\"a\tb\"") is err(ControlChar(1, 3))                            // raw tab
}

test "arrays and objects" {
  assert parse("[]")? == List([])
  assert parse("[ ]")? == List([])
  assert parse(r"{}")? == Map({})
  assert parse(r" { } ")? == Map({})
  assert parse("[1, \"a\", true, null, [], [[2]]]")? ==
    List([Int(1), Str("a"), Bool(true), Null, List([]), List([List([Int(2)])])])
  assert parse(r"""{"a": 1, "b": {"c": [null]}, "": "empty key"}""")? ==
    Map({"a": Int(1), "b": Map({"c": List([Null])}), "": Str("empty key")})
  assert parse(r"""{"k": 1, "k": 2}""")? == Map({"k": Int(2)})  // last duplicate wins
  assert parse(r"""
    {
      "list" : [ 1 ,2 ] ,
      "obj":{"x":true}
    }
  """)? == Map({"list": List([Int(1), Int(2)]), "obj": Map({"x": Bool(true)})})
}

test "structural errors" {
  assert parse("") is err(Eof(1, 1))
  assert parse("   ") is err(Eof(1, 4))
  assert parse("[1,") is err(Eof(1, 4))
  assert parse("[1,]") is err(Unexpected(']', 1, 4))   // trailing comma
  assert parse("[1 2]") is err(Unexpected('2', 1, 4))  // missing comma
  assert parse("]") is err(Unexpected(']', 1, 1))
  assert parse("1 2") is err(Unexpected('2', 1, 3))             // trailing data
  assert parse(r"""{"a" 1}""") is err(Unexpected('1', 1, 6))    // missing colon
  assert parse(r"""{"a": 1,}""") is err(Unexpected('}', 1, 9))  // trailing comma
  assert parse(r"""{a: 1}""") is err(Unexpected('a', 1, 2))     // unquoted key
  assert parse(r"""{1: 1}""") is err(Unexpected('1', 1, 2))     // non-string key
  assert parse(r"""{"a": 1""") is err(Eof(1, 8))
  assert parse("[1, 2,\n  x]") is err(Unexpected('x', 2, 3))
  assert parse(r"""{
  "a": tru
}""") is err(Unexpected('\n', 2, 11))
  assert parse("[1]\r\n\r\n  }}") is err(Unexpected('}', 3, 3))  // CRLF counts as one line
}

test "nesting limit" {
  var fine = ""
  for _ in 0..MAX_DEPTH { fine += "[" }
  for _ in 0..MAX_DEPTH { fine += "]" }
  assert parse(fine)? is List(_)
  var deep = ""
  for _ in 0..10_000 { deep += "[" }
  let err(TooDeep(l, k)) = parse(deep) else fail("expected TooDeep")
  assert (l, k) == (1, MAX_DEPTH + 1)
}

test "long input does not overflow" {
  var parts: [str] = []
  for i in 0..100_000 { parts.push("{i}") }
  let List(xs) = parse("[" + parts.join(", ") + "]")? else fail("expected a list")
  assert xs.len() == 100_000
  assert xs[99_999] == Int(99_999)
  let long = parts.join("")
  assert parse("\"" + long + "\"")? == Str(long)
}

test "compact output" {
  assert str(Null) == "null"
  assert str(Bool(false)) == "false"
  assert str(Int(-12)) == "-12"
  assert str(List([])) == "[]"
  assert str(Map({})) == r"{}"
  assert str(List([Int(1), Str("a"), Bool(true), Null])) == "[1,\"a\",true,null]"
  assert str(Map({"b": Int(2), "a": List([Map({})])})) == r"""{"a":[{}],"b":2}"""
  assert str(Str("a\"b\\c/\n\r\t")) == "\"a\\\"b\\\\c/\\n\\r\\t\""
  assert str(Str("\u{1}\u{8}\u{1f}")) == "\"\\u0001\\u0008\\u001f\""
  assert str(Str("é😀")) == "\"é😀\""
}

test "float output" {
  assert str(Float(1.0)) == "1.0"
  assert str(Float(2.5)) == "2.5"
  assert str(Float(-0.5)) == "-0.5"
  assert str(Float(0.0 / 0.0)) == "null"
  assert str(Float(1.0 / 0.0)) == "null"
  assert str(Float(-1.0 / 0.0)) == "null"
  for f in [0.1, 1.0, 1e300, -2.5e-8, 123456789.0] {
    assert parse(str(Float(f)))? == Float(f)
  }
}

test "pretty output" {
  assert pretty(Int(1)) == "1"
  assert pretty(List([])) == "[]"
  let v = Map({
    "name": Str("auk"),
    "tags": List([Str("a"), Int(1)]),
    "empty": Map({}),
    "none": List([]),
    "nested": Map({"x": Null}),
  })
  assert pretty(v) == r"""{
  "empty": {},
  "name": "auk",
  "nested": {
    "x": null
  },
  "none": [],
  "tags": [
    "a",
    1
  ]
}"""
}

test "round trips" {
  let values = [
    Null,
    List([Int(1), Int(-2), Float(3.5), Str("x"), Bool(false)]),
    Map({"a": Map({"b": List([Map({"c": Str("é")})])}), "z": List([])}),
    Map({"esc": Str("\"\\\n/\u{1}😀"), "n": Float(-1.5e-7), "": Null}),
  ]
  for v in values {
    assert parse(str(v))? == v
    assert parse(pretty(v))? == v
  }
  assert str(parse(r"""{"b":1,"a":[true,null]}""")?) == r"""{"a":[true,null],"b":1}"""
}

test "messages" {
  assert message(Unexpected('}', 2, 11)) == r"2:11: unexpected '}'"
  assert message(Eof(1, 4)) == "1:4: unexpected end of input"
  assert message(BadNumber("01", 1, 1)) == "1:1: bad number '01'"
  assert message(TooDeep(1, 513)) == "1:513: nested deeper than 512"
}

// used by the decode/encode tests
struct Todo { id: int, title: str, done: bool }
enum Status { Open, Closed(reason: str) }

test "decode and encode" {
  let t: Todo = decode(r"""{"id": 1, "title": "milk", "done": false}""")?
  assert t == Todo { id: 1, title: "milk", done: false }
  assert encode(t) == r"""{"done":false,"id":1,"title":"milk"}"""
  let ts: [Todo] = decode(encode([t, Todo { id: 2, done: true, ..t }]))?
  assert ts.len() == 2 && ts[1].done && ts[1].title == "milk"
  let s: Status = decode("\"Open\"")?
  assert s == Open
  assert encode(Closed("dup")) == r"""{"reason":"dup","tag":"Closed"}"""
  let c: Status = decode(encode(Closed("dup")))?
  assert c == Closed("dup")
  let n: int = decode(" 7 ")?
  assert n == 7
}

test "decode errors" {
  let syntax: Todo! = decode(r"""{"id": 1,""")
  assert syntax is err(_)
  let wrong_type: Todo! = decode(r"""{"id": "one", "title": "x", "done": false}""")
  assert wrong_type is err(_)
  let missing: Todo! = decode(r"""{"id": 1}""")
  assert missing is err(_)
  let not_obj: Todo! = decode("[]")
  assert not_obj is err(_)
}