A tiny JSON parser in thirteen languages

const DOC = String.raw`{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}`;

class ParseError extends Error {}

function parse(text) {
  let i = 0;
  const fail = msg => { throw new ParseError(msg); };
  const ws = () => { while (i < text.length && ' \t\n\r'.includes(text[i])) i++; };
  const expect = c => { ws(); if (text[i] !== c) fail(`expected '${c}' at ${i}`); i++; };

  function value() {
    ws();
    if (i >= text.length) fail('unexpected end of input');
    const c = text[i];
    if (c === '{') return object();
    if (c === '[') return array();
    if (c === '"') return string();
    if (c === '-' || (c >= '0' && c <= '9')) return number();
    for (const [word, v] of [['true', true], ['false', false], ['null', null]])
      if (text.startsWith(word, i)) { i += word.length; return v; }
    fail(`unexpected '${c}' at ${i}`);
  }
  function object() {
    const pairs = new Map();
    i++; ws();
    if (text[i] === '}') { i++; return pairs; }
    for (;;) {
      ws();
      if (text[i] !== '"') fail(`expected string at ${i}`);
      const key = string();
      expect(':');
      pairs.set(key, value());
      ws();
      if (text[i] === ',') { i++; continue; }
      if (text[i] === '}') { i++; return pairs; }
      fail(`expected ',' or '}' at ${i}`);
    }
  }
  function array() {
    const items = [];
    i++; ws();
    if (text[i] === ']') { i++; return items; }
    for (;;) {
      items.push(value());
      ws();
      if (text[i] === ',') { i++; continue; }
      if (text[i] === ']') { i++; return items; }
      fail(`expected ',' or ']' at ${i}`);
    }
  }
  function string() {
    let out = '';
    i++;
    for (;;) {
      if (i >= text.length) fail('unexpected end of input');
      const c = text[i++];
      if (c === '"') return out;
      if (c !== '\\') { out += c; continue; }
      const e = text[i++];
      if (e === 'u') { out += String.fromCharCode(parseInt(text.slice(i, i + 4), 16)); i += 4; }
      else out += { b: '\b', f: '\f', n: '\n', r: '\r', t: '\t' }[e] ?? e;
    }
  }
  function number() {
    const m = /^-?\d+(\.\d+)?([eE][+-]?\d+)?/.exec(text.slice(i));
    i += m[0].length;
    return Number(m[0]);
  }

  const v = value();
  ws();
  if (i < text.length) fail(`unexpected '${text[i]}' at ${i}`);
  return v;
}

const quote = s => '"' + s.replace(/[\\"\n]/g, c => ({ '\\': '\\\\', '"': '\\"', '\n': '\\n' })[c]) + '"';

function show(v, indent = '') {
  const inner = indent + '  ';
  if (v instanceof Map) {
    if (!v.size) return '{}';
    return '{\n' + [...v].map(([k, x]) => inner + quote(k) + ': ' + show(x, inner)).join(',\n') + '\n' + indent + '}';
  }
  if (Array.isArray(v)) {
    if (!v.length) return '[]';
    return '[\n' + v.map(x => inner + show(x, inner)).join(',\n') + '\n' + indent + ']';
  }
  return typeof v === 'string' ? quote(v) : String(v);
}

function stats(v, s = { strings: 0, numbers: 0, sum: 0 }) {
  if (typeof v === 'string') s.strings++;
  else if (typeof v === 'number') { s.numbers++; s.sum += v; }
  else if (v instanceof Map || Array.isArray(v)) for (const x of v.values()) stats(x, s);
  return s;
}
const depth = v => (v instanceof Map || Array.isArray(v) ? 1 + Math.max(0, ...[...v.values()].map(depth)) : 0);

const doc = parse(DOC);
console.log(show(doc));
const s = stats(doc);
console.log(`strings: ${s.strings}, numbers: ${s.numbers}, sum: ${s.sum}, depth: ${depth(doc)}`);
for (const bad of ['[1, 2,]', '{"a" 1}', '"open']) {
  try { parse(bad); } catch (e) { if (!(e instanceof ParseError)) throw e; console.log(`error: ${e.message}`); }
}

import re

DOC = r'''{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}'''

NUMBER = re.compile(r"-?\d+(\.\d+)?([eE][+-]?\d+)?")
ESCAPES = {"b": "\b", "f": "\f", "n": "\n", "r": "\r", "t": "\t"}


class ParseError(Exception):
    pass


class Parser:
    def __init__(self, text):
        self.text, self.i = text, 0

    def peek(self):
        return self.text[self.i] if self.i < len(self.text) else ""

    def ws(self):
        while self.peek() in (" ", "\t", "\n", "\r"):
            self.i += 1

    def expect(self, c):
        self.ws()
        if self.peek() != c:
            raise ParseError(f"expected '{c}' at {self.i}")
        self.i += 1

    def parse(self):
        v = self.value()
        self.ws()
        if self.peek():
            raise ParseError(f"unexpected '{self.peek()}' at {self.i}")
        return v

    def value(self):
        self.ws()
        c = self.peek()
        if not c:
            raise ParseError("unexpected end of input")
        if c == "{":
            return self.object()
        if c == "[":
            return self.array()
        if c == '"':
            return self.string()
        if c == "-" or c.isdigit():
            return self.number()
        for word, v in (("true", True), ("false", False), ("null", None)):
            if self.text.startswith(word, self.i):
                self.i += len(word)
                return v
        raise ParseError(f"unexpected '{c}' at {self.i}")

    def object(self):
        pairs = {}
        self.i += 1
        self.ws()
        if self.peek() == "}":
            self.i += 1
            return pairs
        while True:
            self.ws()
            if self.peek() != '"':
                raise ParseError(f"expected string at {self.i}")
            key = self.string()
            self.expect(":")
            pairs[key] = self.value()
            self.ws()
            if self.peek() == ",":
                self.i += 1
            elif self.peek() == "}":
                self.i += 1
                return pairs
            else:
                raise ParseError(f"expected ',' or '}}' at {self.i}")

    def array(self):
        items = []
        self.i += 1
        self.ws()
        if self.peek() == "]":
            self.i += 1
            return items
        while True:
            items.append(self.value())
            self.ws()
            if self.peek() == ",":
                self.i += 1
            elif self.peek() == "]":
                self.i += 1
                return items
            else:
                raise ParseError(f"expected ',' or ']' at {self.i}")

    def string(self):
        out = []
        self.i += 1
        while True:
            c = self.peek()
            if not c:
                raise ParseError("unexpected end of input")
            self.i += 1
            if c == '"':
                return "".join(out)
            if c != "\\":
                out.append(c)
                continue
            e = self.peek()
            self.i += 1
            if e == "u":
                out.append(chr(int(self.text[self.i:self.i + 4], 16)))
                self.i += 4
            else:
                out.append(ESCAPES.get(e, e))

    def number(self):
        m = NUMBER.match(self.text, self.i)
        self.i = m.end()
        return float(m.group())


def quote(s):
    return '"' + s.replace("\\", "\\\\").replace('"', '\\"').replace("\n", "\\n") + '"'


def show(v, indent=""):
    inner = indent + "  "
    if isinstance(v, dict):
        if not v:
            return "{}"
        body = ",\n".join(f"{inner}{quote(k)}: {show(x, inner)}" for k, x in v.items())
        return "{\n" + body + "\n" + indent + "}"
    if isinstance(v, list):
        if not v:
            return "[]"
        return "[\n" + ",\n".join(inner + show(x, inner) for x in v) + "\n" + indent + "]"
    if isinstance(v, str):
        return quote(v)
    if v is None:
        return "null"
    if isinstance(v, bool):
        return "true" if v else "false"
    return str(int(v)) if v.is_integer() else repr(v)


def walk(v):
    yield v
    children = v.values() if isinstance(v, dict) else v if isinstance(v, list) else ()
    for x in children:
        yield from walk(x)


def depth(v):
    if isinstance(v, (dict, list)):
        return 1 + max((depth(x) for x in (v.values() if isinstance(v, dict) else v)), default=0)
    return 0


doc = Parser(DOC).parse()
print(show(doc))
values = list(walk(doc))
strings = [v for v in values if isinstance(v, str)]
numbers = [v for v in values if isinstance(v, float)]
print(f"strings: {len(strings)}, numbers: {len(numbers)}, sum: {show(sum(numbers))}, depth: {depth(doc)}")
for bad in ["[1, 2,]", '{"a" 1}', '"open']:
    try:
        Parser(bad).parse()
    except ParseError as e:
        print(f"error: {e}")

require "strscan"

DOC = <<~'JSON'
  {
    "name": "Ada",
    "langs": ["C", "OCaml", "Prolog"],
    "age": 36, "ratio": -0.25, "big": 1.5e3,
    "active": true, "boss": null,
    "note": "say \"hi\"\n\u00e9t\u00e9",
    "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
  }
JSON

class ParseError < StandardError; end

class Parser
  ESCAPES = { "b" => "\b", "f" => "\f", "n" => "\n", "r" => "\r", "t" => "\t" }.freeze

  def initialize(text) = @s = StringScanner.new(text)

  def parse
    v = value
    ws
    raise ParseError, "unexpected '#{@s.peek(1)}' at #{@s.pos}" unless @s.eos?
    v
  end

  private

  def ws = @s.skip(/[ \t\n\r]*/)

  def expect(c)
    ws
    raise ParseError, "expected '#{c}' at #{@s.pos}" unless @s.skip(c)
  end

  def value
    ws
    raise ParseError, "unexpected end of input" if @s.eos?
    case @s.peek(1)
    when "{" then object
    when "[" then array
    when '"' then string
    when "-", /\d/ then @s.scan(/-?\d+(\.\d+)?([eE][+-]?\d+)?/).to_f
    else
      return true if @s.skip("true")
      return false if @s.skip("false")
      return nil if @s.skip("null")
      raise ParseError, "unexpected '#{@s.peek(1)}' at #{@s.pos}"
    end
  end

  def object
    pairs = {}
    @s.getch
    ws
    return pairs if @s.skip("}")
    loop do
      ws
      raise ParseError, "expected string at #{@s.pos}" unless @s.peek(1) == '"'
      key = string
      expect(":")
      pairs[key] = value
      ws
      next if @s.skip(",")
      return pairs if @s.skip("}")
      raise ParseError, "expected ',' or '}' at #{@s.pos}"
    end
  end

  def array
    items = []
    @s.getch
    ws
    return items if @s.skip("]")
    loop do
      items << value
      ws
      next if @s.skip(",")
      return items if @s.skip("]")
      raise ParseError, "expected ',' or ']' at #{@s.pos}"
    end
  end

  def string
    out = +""
    @s.getch
    loop do
      c = @s.getch or raise ParseError, "unexpected end of input"
      return out if c == '"'
      if c != "\\"
        out << c
      elsif (e = @s.getch) == "u"
        out << @s.peek(4).to_i(16).chr(Encoding::UTF_8)
        @s.pos += 4
      else
        out << ESCAPES.fetch(e, e)
      end
    end
  end
end

def quote(s) = '"' + s.gsub(/[\\"\n]/, "\\" => "\\\\", '"' => '\\"', "\n" => "\\n") + '"'

def show(v, indent = "")
  inner = indent + "  "
  case v
  in Hash if v.empty? then "{}"
  in Hash then "{\n" + v.map { |k, x| "#{inner}#{quote(k)}: #{show(x, inner)}" }.join(",\n") + "\n#{indent}}"
  in Array if v.empty? then "[]"
  in Array then "[\n" + v.map { |x| inner + show(x, inner) }.join(",\n") + "\n#{indent}]"
  in String then quote(v)
  in nil then "null"
  in Float if v == v.floor then v.to_i.to_s
  else v.to_s
  end
end

def leaves(v) = case v
                when Hash then v.values.flat_map { leaves(_1) }
                when Array then v.flat_map { leaves(_1) }
                else [v]
                end

def depth(v) = case v
               when Hash, Array then 1 + ((v.is_a?(Hash) ? v.values : v).map { depth(_1) }.max || 0)
               else 0
               end

doc = Parser.new(DOC).parse
puts show(doc)
numbers = leaves(doc).grep(Float)
puts "strings: #{leaves(doc).grep(String).size}, numbers: #{numbers.size}, sum: #{show(numbers.sum)}, depth: #{depth(doc)}"
['[1, 2,]', '{"a" 1}', '"open'].each do |bad|
  Parser.new(bad).parse
rescue ParseError => e
  puts "error: #{e.message}"
end
nil

local DOC = [[{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}]]

-- Lua tables cannot hold nil, and do not remember key order, so JSON null is a
-- unique sentinel and objects keep their keys in a list.
local NULL = setmetatable({}, { __tostring = function() return "null" end })
local ESCAPES = { b = "\b", f = "\f", n = "\n", r = "\r", t = "\t" }

local function parse(text)
  local i = 1 -- Lua strings start at 1; errors report i - 1 to match the other languages
  local function fail(msg) error({ msg = msg }, 0) end
  local function peek() return text:sub(i, i) end
  local function ws() i = text:find("[^ \t\n\r]", i) or #text + 1 end
  local function expect(c)
    ws()
    if peek() ~= c then fail(("expected '%s' at %d"):format(c, i - 1)) end
    i = i + 1
  end

  local value

  local function string_()
    local out = {}
    i = i + 1
    while true do
      local c = peek()
      if c == "" then fail("unexpected end of input") end
      i = i + 1
      if c == '"' then return table.concat(out) end
      if c ~= "\\" then
        out[#out + 1] = c
      else
        local e = peek()
        i = i + 1
        if e == "u" then
          out[#out + 1] = utf8.char(tonumber(text:sub(i, i + 3), 16))
          i = i + 4
        else
          out[#out + 1] = ESCAPES[e] or e
        end
      end
    end
  end

  local function object()
    local obj = { kind = "object", keys = {}, vals = {} }
    i = i + 1
    ws()
    if peek() == "}" then i = i + 1; return obj end
    while true do
      ws()
      if peek() ~= '"' then fail(("expected string at %d"):format(i - 1)) end
      local key = string_()
      expect(":")
      obj.keys[#obj.keys + 1] = key
      obj.vals[#obj.vals + 1] = value()
      ws()
      local c = peek()
      i = i + 1
      if c == "}" then return obj end
      if c ~= "," then fail(("expected ',' or '}' at %d"):format(i - 2)) end
    end
  end

  local function array()
    local arr = { kind = "array", vals = {} }
    i = i + 1
    ws()
    if peek() == "]" then i = i + 1; return arr end
    while true do
      arr.vals[#arr.vals + 1] = value()
      ws()
      local c = peek()
      i = i + 1
      if c == "]" then return arr end
      if c ~= "," then fail(("expected ',' or ']' at %d"):format(i - 2)) end
    end
  end

  function value()
    ws()
    local c = peek()
    if c == "" then fail("unexpected end of input") end
    if c == "{" then return object() end
    if c == "[" then return array() end
    if c == '"' then return string_() end
    local num = text:match("^-?%d+%.?%d*[eE]?[-+]?%d*", i)
    if num then i = i + #num; return tonumber(num) + 0.0 end
    for word, v in pairs({ ["true"] = true, ["false"] = false, null = NULL }) do
      if text:sub(i, i + #word - 1) == word then i = i + #word; return v end
    end
    fail(("unexpected '%s' at %d"):format(c, i - 1))
  end

  local v = value()
  ws()
  if i <= #text then fail(("unexpected '%s' at %d"):format(peek(), i - 1)) end
  return v
end

local function quote(s)
  return '"' .. s:gsub('[\\"\n]', { ["\\"] = "\\\\", ['"'] = '\\"', ["\n"] = "\\n" }) .. '"'
end

local function number(n)
  return n == math.floor(n) and ("%d"):format(n) or ("%.17g"):format(n)
end

local function show(v, indent)
  indent = indent or ""
  local inner = indent .. "  "
  if type(v) == "table" and v.kind then
    if #v.vals == 0 then return v.kind == "object" and "{}" or "[]" end
    local parts = {}
    for k, x in ipairs(v.vals) do
      parts[k] = inner .. (v.keys and quote(v.keys[k]) .. ": " or "") .. show(x, inner)
    end
    local open, close = "[", "]"
    if v.kind == "object" then open, close = "{", "}" end
    return open .. "\n" .. table.concat(parts, ",\n") .. "\n" .. indent .. close
  elseif type(v) == "string" then return quote(v)
  elseif type(v) == "number" then return number(v)
  else return tostring(v)
  end
end

local function walk(v, s)
  if type(v) == "string" then s.strings = s.strings + 1
  elseif type(v) == "number" then s.numbers, s.sum = s.numbers + 1, s.sum + v
  elseif type(v) == "table" and v.kind then
    for _, x in ipairs(v.vals) do walk(x, s) end
  end
  return s
end

local function depth(v)
  if type(v) ~= "table" or not v.kind then return 0 end
  local d = 0
  for _, x in ipairs(v.vals) do d = math.max(d, depth(x)) end
  return 1 + d
end

local doc = parse(DOC)
print(show(doc))
local s = walk(doc, { strings = 0, numbers = 0, sum = 0.0 })
print(("strings: %d, numbers: %d, sum: %s, depth: %d"):format(s.strings, s.numbers, number(s.sum), depth(doc)))
for _, bad in ipairs({ "[1, 2,]", '{"a" 1}', '"open' }) do
  local ok, err = pcall(parse, bad)
  if not ok then print("error: " .. err.msg) end
end

<?php
const DOC = <<<'JSON'
{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}
JSON;

class JsonError extends Exception {}

final class Parser {
    private int $i = 0;
    private const ESCAPES = ['b' => "\x08", 'f' => "\f", 'n' => "\n", 'r' => "\r", 't' => "\t"];

    public function __construct(private string $text) {}

    public function parse(): mixed {
        $v = $this->value();
        $this->ws();
        if ($this->i < strlen($this->text)) $this->fail("unexpected '{$this->text[$this->i]}' at {$this->i}");
        return $v;
    }

    private function fail(string $msg): never { throw new JsonError($msg); }
    private function peek(): string { return $this->text[$this->i] ?? ''; }
    private function ws(): void { $this->i += strspn($this->text, " \t\n\r", $this->i); }

    private function expect(string $c): void {
        $this->ws();
        if ($this->peek() !== $c) $this->fail("expected '$c' at {$this->i}");
        $this->i++;
    }

    private function value(): mixed {
        $this->ws();
        $c = $this->peek();
        if ($c === '') $this->fail('unexpected end of input');
        if ($c === '{') return $this->object();
        if ($c === '[') return $this->array();
        if ($c === '"') return $this->string();
        if (preg_match('/-?\d+(\.\d+)?([eE][+-]?\d+)?/A', $this->text, $m, 0, $this->i)) {
            $this->i += strlen($m[0]);
            return (float) $m[0];
        }
        foreach (['true' => true, 'false' => false, 'null' => null] as $word => $v) {
            if (substr_compare($this->text, $word, $this->i, strlen($word)) === 0) {
                $this->i += strlen($word);
                return $v;
            }
        }
        $this->fail("unexpected '$c' at {$this->i}");
    }

    private function object(): stdClass {
        $obj = new stdClass();
        $this->i++;
        $this->ws();
        if ($this->peek() === '}') { $this->i++; return $obj; }
        while (true) {
            $this->ws();
            if ($this->peek() !== '"') $this->fail("expected string at {$this->i}");
            $key = $this->string();
            $this->expect(':');
            $obj->$key = $this->value();
            $this->ws();
            $c = $this->peek();
            if ($c === '}') { $this->i++; return $obj; }
            if ($c !== ',') $this->fail("expected ',' or '}' at {$this->i}");
            $this->i++;
        }
    }

    private function array(): array {
        $items = [];
        $this->i++;
        $this->ws();
        if ($this->peek() === ']') { $this->i++; return $items; }
        while (true) {
            $items[] = $this->value();
            $this->ws();
            $c = $this->peek();
            if ($c === ']') { $this->i++; return $items; }
            if ($c !== ',') $this->fail("expected ',' or ']' at {$this->i}");
            $this->i++;
        }
    }

    private function string(): string {
        $out = '';
        $this->i++;
        while (true) {
            $c = $this->peek();
            if ($c === '') $this->fail('unexpected end of input');
            $this->i++;
            if ($c === '"') return $out;
            if ($c !== '\\') { $out .= $c; continue; }
            $e = $this->peek();
            $this->i++;
            if ($e === 'u') {
                $out .= utf8(hexdec(substr($this->text, $this->i, 4)));
                $this->i += 4;
            } else {
                $out .= self::ESCAPES[$e] ?? $e;
            }
        }
    }
}

function utf8(int $cp): string {
    if ($cp < 0x80) return chr($cp);
    if ($cp < 0x800) return chr(0xC0 | $cp >> 6) . chr(0x80 | $cp & 0x3F);
    return chr(0xE0 | $cp >> 12) . chr(0x80 | $cp >> 6 & 0x3F) . chr(0x80 | $cp & 0x3F);
}

function quote(string $s): string {
    return '"' . strtr($s, ['\\' => '\\\\', '"' => '\\"', "\n" => '\\n']) . '"';
}

function show(mixed $v, string $indent = ''): string {
    $inner = "$indent  ";
    return match (true) {
        $v instanceof stdClass && !get_object_vars($v) => '{}',
        $v instanceof stdClass => "{\n" . implode(",\n", array_map(
            fn($k, $x) => $inner . quote((string) $k) . ': ' . show($x, $inner),
            array_keys(get_object_vars($v)), get_object_vars($v))) . "\n$indent}",
        $v === [] => '[]',
        is_array($v) => "[\n" . implode(",\n", array_map(fn($x) => $inner . show($x, $inner), $v)) . "\n$indent]",
        is_string($v) => quote($v),
        $v === null => 'null',
        is_bool($v) => $v ? 'true' : 'false',
        default => (string) $v,
    };
}

function leaves(mixed $v): array {
    if ($v instanceof stdClass) $v = get_object_vars($v);
    return is_array($v) ? array_merge([], ...array_map('leaves', array_values($v))) : [$v];
}

function depth(mixed $v): int {
    if ($v instanceof stdClass) $v = get_object_vars($v);
    return is_array($v) ? 1 + max([0, ...array_map('depth', $v)]) : 0;
}

$doc = (new Parser(DOC))->parse();
echo show($doc), "\n";
$numbers = array_filter(leaves($doc), 'is_float');
printf("strings: %d, numbers: %d, sum: %s, depth: %d\n",
    count(array_filter(leaves($doc), 'is_string')), count($numbers), show(array_sum($numbers)), depth($doc));
foreach (['[1, 2,]', '{"a" 1}', '"open'] as $bad) {
    try {
        (new Parser($bad))->parse();
    } catch (JsonError $e) {
        echo "error: {$e->getMessage()}\n";
    }
}

use strict;
use warnings;
binmode STDOUT, ':utf8';

my $DOC = <<'JSON';
{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}
JSON

# Values are tagged: [str => 'x'], [num => 1], [arr => [...]], [obj => [[key, value], ...]],
# [true], [false], [null] — a Perl scalar does not know whether it is a number or a string.
my %ESCAPES = (b => "\b", f => "\f", n => "\n", r => "\r", t => "\t");

sub parse {
    local $_ = shift;
    my $v = value();
    /\G\s*/gc;
    die sprintf("unexpected '%s' at %d\n", substr($_, pos), pos) if pos() < length;
    return $v;
}

sub value {
    /\G\s*/gc;
    die "unexpected end of input\n" if pos() >= length;
    return object() if /\G\{/gc;
    return array()  if /\G\[/gc;
    return [str => string()] if /\G"/gc;
    return [num => $1 + 0] if /\G(-?\d+(?:\.\d+)?(?:[eE][-+]?\d+)?)/gc;
    return [$1] if /\G(true|false|null)/gc;
    die sprintf("unexpected '%s' at %d\n", substr($_, pos, 1), pos);
}

sub object {
    my @pairs;
    return [obj => \@pairs] if /\G\s*\}/gc;
    while (1) {
        /\G\s*/gc;
        die sprintf("expected string at %d\n", pos) unless /\G"/gc;
        my $key = string();
        /\G\s*/gc;
        die sprintf("expected ':' at %d\n", pos) unless /\G:/gc;
        push @pairs, [$key, value()];
        /\G\s*/gc;
        next if /\G,/gc;
        return [obj => \@pairs] if /\G\}/gc;
        die sprintf("expected ',' or '}' at %d\n", pos);
    }
}

sub array {
    my @items;
    return [arr => \@items] if /\G\s*\]/gc;
    while (1) {
        push @items, value();
        /\G\s*/gc;
        next if /\G,/gc;
        return [arr => \@items] if /\G\]/gc;
        die sprintf("expected ',' or ']' at %d\n", pos);
    }
}

sub string {
    my $out = '';
    while (1) {
        if    (/\G([^"\\]+)/gc)          { $out .= $1 }
        elsif (/\G"/gc)                  { return $out }
        elsif (/\G\\u([0-9a-fA-F]{4})/gc) { $out .= chr hex $1 }
        elsif (/\G\\(.)/gcs)             { $out .= $ESCAPES{$1} // $1 }
        else                             { die "unexpected end of input\n" }
    }
}

sub quote {
    my $s = shift;
    $s =~ s/([\\"])/\\$1/g;
    $s =~ s/\n/\\n/g;
    return qq{"$s"};
}

sub show {
    my ($v, $indent) = (@_, '');
    my ($type, $x) = @$v;
    my $inner = "$indent  ";
    return quote($x) if $type eq 'str';
    return $x if $type eq 'num';
    if ($type eq 'arr') {
        return '[]' unless @$x;
        return "[\n" . join(",\n", map { $inner . show($_, $inner) } @$x) . "\n$indent]";
    }
    if ($type eq 'obj') {
        return '{}' unless @$x;
        return "{\n" . join(",\n", map { $inner . quote($_->[0]) . ': ' . show($_->[1], $inner) } @$x) . "\n$indent}";
    }
    return $type;
}

sub children {
    my ($type, $x) = @{ $_[0] };
    return $type eq 'arr' ? @$x : $type eq 'obj' ? map { $_->[1] } @$x : ();
}

sub leaves { my @c = children($_[0]); @c ? map { leaves($_) } @c : $_[0] }

sub depth {
    my $v = shift;
    return 0 unless $v->[0] eq 'arr' || $v->[0] eq 'obj';
    my $d = 0;
    for (children($v)) { my $c = depth($_); $d = $c if $c > $d }
    return 1 + $d;
}

my $doc = parse($DOC);
print show($doc), "\n";
my @leaves = leaves($doc);
my @numbers = map { $_->[1] } grep { $_->[0] eq 'num' } @leaves;
my $sum = 0;
$sum += $_ for @numbers;
printf "strings: %d, numbers: %d, sum: %s, depth: %d\n",
    scalar(grep { $_->[0] eq 'str' } @leaves), scalar @numbers, $sum, depth($doc);
for my $bad ('[1, 2,]', '{"a" 1}', '"open') {
    eval { parse($bad); 1 } or print "error: $@";
}

(def doc-text "{
  \"name\": \"Ada\",
  \"langs\": [\"C\", \"OCaml\", \"Prolog\"],
  \"age\": 36, \"ratio\": -0.25, \"big\": 1.5e3,
  \"active\": true, \"boss\": null,
  \"note\": \"say \\\"hi\\\"\\n\\u00e9t\\u00e9\",
  \"nested\": {\"a\": [1, 2, {\"b\": []}], \"c\": {}, \"path\": \"C:\\\\tmp\"}
}")

;; Each parse function takes the text and a position and returns [value next-position].
(defn fail [msg] (throw (ex-info msg {:json true})))
(defn skip-ws [s i] (if (and (< i (count s)) (#{\space \tab \newline \return} (nth s i))) (recur s (inc i)) i))
(defn at [s i] (when (< i (count s)) (nth s i)))

(declare parse-value)

(defn parse-string [s i]
  (loop [i (inc i) out []]
    (let [c (at s i)]
      (cond
        (nil? c) (fail "unexpected end of input")
        (= c \") [(apply str out) (inc i)]
        (not= c \\) (recur (inc i) (conj out c))
        (= (at s (inc i)) \u) (recur (+ i 6) (conj out (char (js/parseInt (subs s (+ i 2) (+ i 6)) 16))))
        :else (let [e (at s (inc i))]
                (recur (+ i 2) (conj out (get {\b "\b" \f "\f" \n "\n" \r "\r" \t "\t"} e e))))))))

(defn parse-seq
  "The shared shape of arrays and objects: items separated by commas until `close`."
  [s i close item]
  (let [i (skip-ws s (inc i))]
    (if (= (at s i) close)
      [[] (inc i)]
      (loop [i i items []]
        (let [[x i] (item s i)
              i (skip-ws s i)
              items (conj items x)]
          (condp = (at s i)
            \, (recur (inc i) items)
            close [items (inc i)]
            (fail (str "expected ',' or '" close "' at " i))))))))

(defn parse-pair [s i]
  (let [i (skip-ws s i)]
    (when-not (= (at s i) \") (fail (str "expected string at " i)))
    (let [[k i] (parse-string s i)
          i (skip-ws s i)]
      (when-not (= (at s i) \:) (fail (str "expected ':' at " i)))
      (let [[v i] (parse-value s (inc i))] [[k v] i]))))

(defn parse-value [s i]
  (let [i (skip-ws s i)
        c (at s i)
        rest-text (subs s (min i (count s)))]
    (cond
      (nil? c) (fail "unexpected end of input")
      (= c \{) (let [[pairs i] (parse-seq s i \} parse-pair)] [(apply array-map (apply concat pairs)) i])
      (= c \[) (parse-seq s i \] parse-value)
      (= c \") (parse-string s i)
      :else
      (if-let [n (re-find #"^-?\d+(?:\.\d+)?(?:[eE][+-]?\d+)?" rest-text)]
        [(parse-double n) (+ i (count n))]
        (if-let [[word v] (some (fn [[w v]] (when (clojure.string/starts-with? rest-text w) [w v]))
                                [["true" true] ["false" false] ["null" nil]])]
          [v (+ i (count word))]
          (fail (str "unexpected '" c "' at " i)))))))

(defn parse [s]
  (let [[v i] (parse-value s 0)
        i (skip-ws s i)]
    (when (< i (count s)) (fail (str "unexpected '" (at s i) "' at " i)))
    v))

(defn quote-str [s] (str "\"" (clojure.string/escape s {\\ "\\\\" \" "\\\"" \newline "\\n"}) "\""))

(defn show
  ([v] (show v ""))
  ([v indent]
   (let [inner (str indent "  ")
         block (fn [open close lines]
                 (if (empty? lines) (str open close)
                     (str open "\n" (clojure.string/join ",\n" lines) "\n" indent close)))]
     (cond
       (map? v) (block "{" "}" (for [[k x] v] (str inner (quote-str k) ": " (show x inner))))
       (vector? v) (block "[" "]" (for [x v] (str inner (show x inner))))
       (string? v) (quote-str v)
       (nil? v) "null"
       :else (str v)))))

(defn depth [v]
  (if (coll? v) (inc (reduce max 0 (map depth (if (map? v) (vals v) v)))) 0))

(let [doc (parse doc-text)
      leaves (remove coll? (tree-seq coll? #(if (map? %) (vals %) %) doc))
      numbers (filter number? leaves)]
  (println (show doc))
  (println (str "strings: " (count (filter string? leaves)) ", numbers: " (count numbers)
                ", sum: " (reduce + numbers) ", depth: " (depth doc)))
  (doseq [bad ["[1, 2,]" "{\"a\" 1}" "\"open"]]
    (try (parse bad)
         (catch :default e
           (if (:json (ex-data e)) (println (str "error: " (ex-message e))) (throw e))))))

#include <math.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static const char *DOC =
    "{\n"
    "  \"name\": \"Ada\",\n"
    "  \"langs\": [\"C\", \"OCaml\", \"Prolog\"],\n"
    "  \"age\": 36, \"ratio\": -0.25, \"big\": 1.5e3,\n"
    "  \"active\": true, \"boss\": null,\n"
    "  \"note\": \"say \\\"hi\\\"\\n\\u00e9t\\u00e9\",\n"
    "  \"nested\": {\"a\": [1, 2, {\"b\": []}], \"c\": {}, \"path\": \"C:\\\\tmp\"}\n"
    "}";

typedef enum { J_NULL, J_BOOL, J_NUM, J_STR, J_ARR, J_OBJ } Kind;

typedef struct Value {
    Kind kind;
    double num;            /* J_NUM; J_BOOL uses 0 or 1 */
    char *str;             /* J_STR */
    int n;                 /* J_ARR, J_OBJ: number of items */
    char **keys;           /* J_OBJ */
    struct Value **items;  /* J_ARR, J_OBJ */
} Value;

/* The parser's state. On an error, fail() records the first message and every function
   returns NULL (or 0) up the call chain. */
static const char *text;
static size_t pos;
static int failed;
static char message[80];

static void *fail(const char *fmt, ...) {
    if (!failed) {
        va_list ap;
        va_start(ap, fmt);
        vsnprintf(message, sizeof message, fmt, ap);
        va_end(ap);
        failed = 1;
    }
    return NULL;
}

static Value *new_value(Kind kind) {
    Value *v = calloc(1, sizeof *v);
    v->kind = kind;
    return v;
}

static void ws(void) {
    while (text[pos] == ' ' || text[pos] == '\t' || text[pos] == '\n' || text[pos] == '\r') pos++;
}

static int expect(char c) {
    ws();
    if (text[pos] != c) { fail("expected '%c' at %zu", c, pos); return 0; }
    pos++;
    return 1;
}

/* A growable string. */
typedef struct { char *s; size_t len, cap; } Buf;

static void put(Buf *b, char c) {
    if (b->len + 2 > b->cap) b->s = realloc(b->s, b->cap = b->cap * 2 + 16);
    b->s[b->len++] = c;
    b->s[b->len] = '\0';
}

static void put_utf8(Buf *b, unsigned cp) {
    if (cp < 0x80) {
        put(b, cp);
    } else if (cp < 0x800) {
        put(b, 0xC0 | cp >> 6);
        put(b, 0x80 | (cp & 0x3F));
    } else {
        put(b, 0xE0 | cp >> 12);
        put(b, 0x80 | (cp >> 6 & 0x3F));
        put(b, 0x80 | (cp & 0x3F));
    }
}

static Value *parse_value(void);

static char *parse_string(void) {
    Buf b = {0};
    put(&b, '\0');
    b.len = 0;
    pos++;
    for (;;) {
        char c = text[pos++];
        if (c == '\0') return fail("unexpected end of input");
        if (c == '"') return b.s;
        if (c != '\\') { put(&b, c); continue; }
        char e = text[pos++];
        switch (e) {
        case '\0': return fail("unexpected end of input");
        case 'b': put(&b, '\b'); break;
        case 'f': put(&b, '\f'); break;
        case 'n': put(&b, '\n'); break;
        case 'r': put(&b, '\r'); break;
        case 't': put(&b, '\t'); break;
        case 'u': {
            char hex[5] = {0};
            strncpy(hex, text + pos, 4);
            put_utf8(&b, strtoul(hex, NULL, 16));
            pos += strlen(hex);
            break;
        }
        default: put(&b, e);
        }
    }
}

static void add(Value *v, char *key, Value *item) {
    v->items = realloc(v->items, (v->n + 1) * sizeof *v->items);
    if (key) {
        v->keys = realloc(v->keys, (v->n + 1) * sizeof *v->keys);
        v->keys[v->n] = key;
    }
    v->items[v->n++] = item;
}

static Value *parse_object(void) {
    Value *v = new_value(J_OBJ);
    pos++;
    ws();
    if (text[pos] == '}') { pos++; return v; }
    for (;;) {
        ws();
        if (text[pos] != '"') return fail("expected string at %zu", pos);
        char *key = parse_string();
        if (!key || !expect(':')) return NULL;
        Value *item = parse_value();
        if (!item) return NULL;
        add(v, key, item);
        ws();
        if (text[pos] == ',') { pos++; continue; }
        if (text[pos] == '}') { pos++; return v; }
        return fail("expected ',' or '}' at %zu", pos);
    }
}

static Value *parse_array(void) {
    Value *v = new_value(J_ARR);
    pos++;
    ws();
    if (text[pos] == ']') { pos++; return v; }
    for (;;) {
        Value *item = parse_value();
        if (!item) return NULL;
        add(v, NULL, item);
        ws();
        if (text[pos] == ',') { pos++; continue; }
        if (text[pos] == ']') { pos++; return v; }
        return fail("expected ',' or ']' at %zu", pos);
    }
}

static Value *parse_value(void) {
    ws();
    char c = text[pos];
    if (c == '\0') return fail("unexpected end of input");
    if (c == '{') return parse_object();
    if (c == '[') return parse_array();
    if (c == '"') {
        char *s = parse_string();
        if (!s) return NULL;
        Value *v = new_value(J_STR);
        v->str = s;
        return v;
    }
    if (c == '-' || (c >= '0' && c <= '9')) {
        char *end;
        Value *v = new_value(J_NUM);
        v->num = strtod(text + pos, &end);
        pos = end - text;
        return v;
    }
    if (strncmp(text + pos, "true", 4) == 0) { pos += 4; Value *v = new_value(J_BOOL); v->num = 1; return v; }
    if (strncmp(text + pos, "false", 5) == 0) { pos += 5; return new_value(J_BOOL); }
    if (strncmp(text + pos, "null", 4) == 0) { pos += 4; return new_value(J_NULL); }
    return fail("unexpected '%c' at %zu", c, pos);
}

static Value *parse(const char *s) {
    text = s;
    pos = 0;
    failed = 0;
    Value *v = parse_value();
    if (!v) return NULL;
    ws();
    if (text[pos]) return fail("unexpected '%c' at %zu", text[pos], pos);
    return v;
}

static void print_number(double x) {
    if (x == floor(x) && fabs(x) < 1e15) printf("%.0f", x);
    else printf("%.17g", x);
}

static void print_string(const char *s) {
    putchar('"');
    for (; *s; s++) {
        if (*s == '"' || *s == '\\') printf("\\%c", *s);
        else if (*s == '\n') fputs("\\n", stdout);
        else putchar(*s);
    }
    putchar('"');
}

static void show(const Value *v, int indent) {
    switch (v->kind) {
    case J_NULL: fputs("null", stdout); break;
    case J_BOOL: fputs(v->num ? "true" : "false", stdout); break;
    case J_NUM: print_number(v->num); break;
    case J_STR: print_string(v->str); break;
    case J_ARR:
    case J_OBJ: {
        char open = v->kind == J_ARR ? '[' : '{', close = v->kind == J_ARR ? ']' : '}';
        if (v->n == 0) { printf("%c%c", open, close); break; }
        printf("%c\n", open);
        for (int k = 0; k < v->n; k++) {
            printf("%*s", indent + 2, "");
            if (v->kind == J_OBJ) { print_string(v->keys[k]); fputs(": ", stdout); }
            show(v->items[k], indent + 2);
            fputs(k + 1 < v->n ? ",\n" : "\n", stdout);
        }
        printf("%*s%c", indent, "", close);
    }
    }
}

static int strings, numbers;
static double sum;

static int walk(const Value *v) {  /* counts strings and numbers, returns the depth */
    if (v->kind == J_STR) strings++;
    if (v->kind == J_NUM) { numbers++; sum += v->num; }
    int deepest = 0;
    for (int k = 0; k < v->n; k++) {
        int d = walk(v->items[k]);
        if (d > deepest) deepest = d;
    }
    return v->kind == J_ARR || v->kind == J_OBJ ? 1 + deepest : 0;
}

static void try_parse(const char *s) {
    if (!parse(s)) printf("error: %s\n", message);
}

int main(void) {
    Value *doc = parse(DOC);
    if (!doc) { printf("error: %s\n", message); return 1; }
    show(doc, 0);
    putchar('\n');
    int depth = walk(doc);
    printf("strings: %d, numbers: %d, sum: ", strings, numbers);
    print_number(sum);
    printf(", depth: %d\n", depth);
    try_parse("[1, 2,]");
    try_parse("{\"a\" 1}");
    try_parse("\"open");
    return 0;
}

const DOC: &str = r#"{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}"#;

enum Json {
    Null,
    Bool(bool),
    Num(f64),
    Str(String),
    Arr(Vec<Json>),
    Obj(Vec<(String, Json)>),
}

struct Parser<'a> {
    text: &'a [u8],
    pos: usize,
}

type Result<T> = std::result::Result<T, String>;

impl Parser<'_> {
    fn peek(&self) -> Option<u8> {
        self.text.get(self.pos).copied()
    }

    fn ws(&mut self) {
        while matches!(self.peek(), Some(b' ' | b'\t' | b'\n' | b'\r')) {
            self.pos += 1;
        }
    }

    fn expect(&mut self, c: u8) -> Result<()> {
        self.ws();
        if self.peek() != Some(c) {
            return Err(format!("expected '{}' at {}", c as char, self.pos));
        }
        self.pos += 1;
        Ok(())
    }

    fn parse(mut self) -> Result<Json> {
        let v = self.value()?;
        self.ws();
        match self.peek() {
            Some(c) => Err(format!("unexpected '{}' at {}", c as char, self.pos)),
            None => Ok(v),
        }
    }

    fn value(&mut self) -> Result<Json> {
        self.ws();
        match self.peek() {
            None => Err("unexpected end of input".into()),
            Some(b'{') => self.object(),
            Some(b'[') => self.array(),
            Some(b'"') => Ok(Json::Str(self.string()?)),
            Some(b'-' | b'0'..=b'9') => Ok(self.number()),
            Some(c) => {
                for (word, v) in [("true", Json::Bool(true)), ("false", Json::Bool(false)), ("null", Json::Null)] {
                    if self.text[self.pos..].starts_with(word.as_bytes()) {
                        self.pos += word.len();
                        return Ok(v);
                    }
                }
                Err(format!("unexpected '{}' at {}", c as char, self.pos))
            }
        }
    }

    fn object(&mut self) -> Result<Json> {
        let mut pairs = Vec::new();
        self.pos += 1;
        self.ws();
        if self.peek() == Some(b'}') {
            self.pos += 1;
            return Ok(Json::Obj(pairs));
        }
        loop {
            self.ws();
            if self.peek() != Some(b'"') {
                return Err(format!("expected string at {}", self.pos));
            }
            let key = self.string()?;
            self.expect(b':')?;
            pairs.push((key, self.value()?));
            self.ws();
            match self.peek() {
                Some(b',') => self.pos += 1,
                Some(b'}') => {
                    self.pos += 1;
                    return Ok(Json::Obj(pairs));
                }
                _ => return Err(format!("expected ',' or '}}' at {}", self.pos)),
            }
        }
    }

    fn array(&mut self) -> Result<Json> {
        let mut items = Vec::new();
        self.pos += 1;
        self.ws();
        if self.peek() == Some(b']') {
            self.pos += 1;
            return Ok(Json::Arr(items));
        }
        loop {
            items.push(self.value()?);
            self.ws();
            match self.peek() {
                Some(b',') => self.pos += 1,
                Some(b']') => {
                    self.pos += 1;
                    return Ok(Json::Arr(items));
                }
                _ => return Err(format!("expected ',' or ']' at {}", self.pos)),
            }
        }
    }

    fn string(&mut self) -> Result<String> {
        let mut out = String::new();
        self.pos += 1;
        loop {
            let c = self.peek().ok_or("unexpected end of input")?;
            self.pos += 1;
            match c {
                b'"' => return Ok(out),
                b'\\' => {
                    let e = self.peek().ok_or("unexpected end of input")?;
                    self.pos += 1;
                    out.push(match e {
                        b'b' => '\u{8}',
                        b'f' => '\u{c}',
                        b'n' => '\n',
                        b'r' => '\r',
                        b't' => '\t',
                        b'u' => {
                            let hex = std::str::from_utf8(&self.text[self.pos..self.pos + 4]).unwrap();
                            self.pos += 4;
                            char::from_u32(u32::from_str_radix(hex, 16).unwrap()).unwrap_or('\u{fffd}')
                        }
                        other => other as char,
                    });
                }
                _ => {
                    // Copy a run of ordinary bytes at once: the text is UTF-8, so non-ASCII
                    // characters arrive as several bytes and must not be split.
                    let start = self.pos - 1;
                    while matches!(self.peek(), Some(b) if b != b'"' && b != b'\\') {
                        self.pos += 1;
                    }
                    out.push_str(std::str::from_utf8(&self.text[start..self.pos]).unwrap());
                }
            }
        }
    }

    fn number(&mut self) -> Json {
        let start = self.pos;
        while matches!(self.peek(), Some(b'-' | b'+' | b'.' | b'e' | b'E' | b'0'..=b'9')) {
            self.pos += 1;
        }
        let s = std::str::from_utf8(&self.text[start..self.pos]).unwrap();
        Json::Num(s.parse().unwrap())
    }
}

fn parse(text: &str) -> Result<Json> {
    Parser { text: text.as_bytes(), pos: 0 }.parse()
}

fn quote(s: &str) -> String {
    format!("\"{}\"", s.replace('\\', "\\\\").replace('"', "\\\"").replace('\n', "\\n"))
}

fn show(v: &Json, indent: &str) -> String {
    let inner = format!("{indent}  ");
    let block = |open: &str, close: &str, lines: Vec<String>| {
        if lines.is_empty() {
            format!("{open}{close}")
        } else {
            format!("{open}\n{}\n{indent}{close}", lines.join(",\n"))
        }
    };
    match v {
        Json::Null => "null".into(),
        Json::Bool(b) => b.to_string(),
        Json::Num(n) => n.to_string(),
        Json::Str(s) => quote(s),
        Json::Arr(items) => block("[", "]", items.iter().map(|x| format!("{inner}{}", show(x, &inner))).collect()),
        Json::Obj(pairs) => block("{", "}", pairs.iter().map(|(k, x)| format!("{inner}{}: {}", quote(k), show(x, &inner))).collect()),
    }
}

fn children(v: &Json) -> Box<dyn Iterator<Item = &Json> + '_> {
    match v {
        Json::Arr(items) => Box::new(items.iter()),
        Json::Obj(pairs) => Box::new(pairs.iter().map(|(_, x)| x)),
        _ => Box::new(std::iter::empty()),
    }
}

fn depth(v: &Json) -> usize {
    match v {
        Json::Arr(_) | Json::Obj(_) => 1 + children(v).map(depth).max().unwrap_or(0),
        _ => 0,
    }
}

fn leaves<'a>(v: &'a Json, out: &mut Vec<&'a Json>) {
    match v {
        Json::Arr(_) | Json::Obj(_) => children(v).for_each(|x| leaves(x, out)),
        _ => out.push(v),
    }
}

fn main() {
    let doc = parse(DOC).expect("the document parses");
    println!("{}", show(&doc, ""));
    let mut all = Vec::new();
    leaves(&doc, &mut all);
    let strings = all.iter().filter(|v| matches!(v, Json::Str(_))).count();
    let numbers: Vec<f64> = all.iter().filter_map(|v| if let Json::Num(n) = v { Some(*n) } else { None }).collect();
    let sum: f64 = numbers.iter().sum();
    println!("strings: {strings}, numbers: {}, sum: {sum}, depth: {}", numbers.len(), depth(&doc));
    for bad in ["[1, 2,]", r#"{"a" 1}"#, "\"open"] {
        if let Err(e) = parse(bad) {
            println!("error: {e}");
        }
    }
}

package main

import (
	"fmt"
	"strconv"
	"strings"
)

const doc = `{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}`

// A JSON value is nil, bool, float64, string, []any or *Object.
type Object struct {
	Keys   []string
	Values []any
}

type parser struct {
	text string
	pos  int
}

func (p *parser) peek() byte {
	if p.pos < len(p.text) {
		return p.text[p.pos]
	}
	return 0
}

func (p *parser) ws() {
	for p.pos < len(p.text) && strings.IndexByte(" \t\n\r", p.text[p.pos]) >= 0 {
		p.pos++
	}
}

func (p *parser) expect(c byte) error {
	p.ws()
	if p.peek() != c {
		return fmt.Errorf("expected '%c' at %d", c, p.pos)
	}
	p.pos++
	return nil
}

func (p *parser) value() (any, error) {
	p.ws()
	if p.pos >= len(p.text) {
		return nil, fmt.Errorf("unexpected end of input")
	}
	switch c := p.peek(); {
	case c == '{':
		return p.object()
	case c == '[':
		return p.array()
	case c == '"':
		return p.string()
	case c == '-' || c >= '0' && c <= '9':
		start := p.pos
		for p.pos < len(p.text) && strings.IndexByte("+-.eE0123456789", p.text[p.pos]) >= 0 {
			p.pos++
		}
		return strconv.ParseFloat(p.text[start:p.pos], 64)
	}
	for word, v := range map[string]any{"true": true, "false": false, "null": nil} {
		if strings.HasPrefix(p.text[p.pos:], word) {
			p.pos += len(word)
			return v, nil
		}
	}
	return nil, fmt.Errorf("unexpected '%c' at %d", p.peek(), p.pos)
}

func (p *parser) object() (any, error) {
	obj := &Object{}
	p.pos++
	p.ws()
	if p.peek() == '}' {
		p.pos++
		return obj, nil
	}
	for {
		p.ws()
		if p.peek() != '"' {
			return nil, fmt.Errorf("expected string at %d", p.pos)
		}
		key, err := p.string()
		if err != nil {
			return nil, err
		}
		if err := p.expect(':'); err != nil {
			return nil, err
		}
		v, err := p.value()
		if err != nil {
			return nil, err
		}
		obj.Keys = append(obj.Keys, key.(string))
		obj.Values = append(obj.Values, v)
		p.ws()
		switch p.peek() {
		case ',':
			p.pos++
		case '}':
			p.pos++
			return obj, nil
		default:
			return nil, fmt.Errorf("expected ',' or '}' at %d", p.pos)
		}
	}
}

func (p *parser) array() (any, error) {
	items := []any{}
	p.pos++
	p.ws()
	if p.peek() == ']' {
		p.pos++
		return items, nil
	}
	for {
		v, err := p.value()
		if err != nil {
			return nil, err
		}
		items = append(items, v)
		p.ws()
		switch p.peek() {
		case ',':
			p.pos++
		case ']':
			p.pos++
			return items, nil
		default:
			return nil, fmt.Errorf("expected ',' or ']' at %d", p.pos)
		}
	}
}

func (p *parser) string() (any, error) {
	var out strings.Builder
	p.pos++
	for {
		if p.pos >= len(p.text) {
			return nil, fmt.Errorf("unexpected end of input")
		}
		c := p.text[p.pos]
		p.pos++
		switch {
		case c == '"':
			return out.String(), nil
		case c != '\\':
			out.WriteByte(c)
		case p.peek() == 'u':
			n, _ := strconv.ParseUint(p.text[p.pos+1:p.pos+5], 16, 32)
			out.WriteRune(rune(n))
			p.pos += 5
		default:
			e := p.peek()
			p.pos++
			if r, ok := map[byte]byte{'b': '\b', 'f': '\f', 'n': '\n', 'r': '\r', 't': '\t'}[e]; ok {
				e = r
			}
			out.WriteByte(e)
		}
	}
}

func parse(text string) (any, error) {
	p := &parser{text: text}
	v, err := p.value()
	if err != nil {
		return nil, err
	}
	p.ws()
	if p.pos < len(p.text) {
		return nil, fmt.Errorf("unexpected '%c' at %d", p.peek(), p.pos)
	}
	return v, nil
}

var quoter = strings.NewReplacer(`\`, `\\`, `"`, `\"`, "\n", `\n`)

func show(v any, indent string) string {
	inner := indent + "  "
	block := func(open, close string, lines []string) string {
		if len(lines) == 0 {
			return open + close
		}
		return open + "\n" + strings.Join(lines, ",\n") + "\n" + indent + close
	}
	switch v := v.(type) {
	case nil:
		return "null"
	case bool:
		return strconv.FormatBool(v)
	case float64:
		return strconv.FormatFloat(v, 'f', -1, 64)
	case string:
		return `"` + quoter.Replace(v) + `"`
	case []any:
		lines := []string{}
		for _, x := range v {
			lines = append(lines, inner+show(x, inner))
		}
		return block("[", "]", lines)
	case *Object:
		lines := []string{}
		for k, key := range v.Keys {
			lines = append(lines, inner+show(key, inner)+": "+show(v.Values[k], inner))
		}
		return block("{", "}", lines)
	}
	panic("not a JSON value")
}

func children(v any) []any {
	switch v := v.(type) {
	case []any:
		return v
	case *Object:
		return v.Values
	}
	return nil
}

func depth(v any) int {
	switch v.(type) {
	case []any, *Object:
		d := 0
		for _, x := range children(v) {
			d = max(d, depth(x))
		}
		return 1 + d
	}
	return 0
}

func main() {
	v, err := parse(doc)
	if err != nil {
		panic(err)
	}
	fmt.Println(show(v, ""))
	strs, nums, sum := 0, 0, 0.0
	var walk func(any)
	walk = func(v any) {
		switch x := v.(type) {
		case string:
			strs++
		case float64:
			nums++
			sum += x
		}
		for _, c := range children(v) {
			walk(c)
		}
	}
	walk(v)
	fmt.Printf("strings: %d, numbers: %d, sum: %s, depth: %d\n", strs, nums, show(sum, ""), depth(v))
	for _, bad := range []string{"[1, 2,]", `{"a" 1}`, `"open`} {
		if _, err := parse(bad); err != nil {
			fmt.Println("error:", err)
		}
	}
}

const val DOC = """{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}"""

sealed interface Json {
    data object Null : Json
    data class Bool(val value: Boolean) : Json
    data class Num(val value: Double) : Json
    data class Str(val value: String) : Json
    data class Arr(val items: List<Json>) : Json
    data class Obj(val pairs: List<Pair<String, Json>>) : Json
}

class ParseError(message: String) : Exception(message)

class Parser(private val text: String) {
    private var i = 0

    private fun peek(): Char? = text.getOrNull(i)
    private fun fail(msg: String): Nothing = throw ParseError(msg)
    private fun ws() { while (peek()?.let { it in " \t\n\r" } == true) i++ }
    private fun expect(c: Char) { ws(); if (peek() != c) fail("expected '$c' at $i"); i++ }

    fun parse(): Json {
        val v = value()
        ws()
        if (i < text.length) fail("unexpected '${text[i]}' at $i")
        return v
    }

    private fun value(): Json {
        ws()
        val c = peek() ?: fail("unexpected end of input")
        return when {
            c == '{' -> obj()
            c == '[' -> arr()
            c == '"' -> Json.Str(string())
            c == '-' || c.isDigit() -> {
                val m = Regex("""-?\d+(\.\d+)?([eE][+-]?\d+)?""").matchAt(text, i)!!
                i = m.range.last + 1
                Json.Num(m.value.toDouble())
            }
            text.startsWith("true", i) -> { i += 4; Json.Bool(true) }
            text.startsWith("false", i) -> { i += 5; Json.Bool(false) }
            text.startsWith("null", i) -> { i += 4; Json.Null }
            else -> fail("unexpected '$c' at $i")
        }
    }

    private fun <T> items(close: Char, item: () -> T): List<T> {
        val out = mutableListOf<T>()
        i++
        ws()
        if (peek() == close) { i++; return out }
        while (true) {
            out += item()
            ws()
            when (peek()) {
                ',' -> i++
                close -> { i++; return out }
                else -> fail("expected ',' or '$close' at $i")
            }
        }
    }

    private fun obj() = Json.Obj(items('}') {
        ws()
        if (peek() != '"') fail("expected string at $i")
        val key = string()
        expect(':')
        key to value()
    })

    private fun arr() = Json.Arr(items(']') { value() })

    private fun string(): String = buildString {
        i++
        while (true) {
            val c = peek() ?: fail("unexpected end of input")
            i++
            when {
                c == '"' -> return@buildString
                c != '\\' -> append(c)
                peek() == 'u' -> { append(text.substring(i + 1, i + 5).toInt(16).toChar()); i += 5 }
                else -> {
                    val e = text[i++]
                    append(mapOf('b' to '\b', 'f' to '\u000c', 'n' to '\n', 'r' to '\r', 't' to '\t')[e] ?: e)
                }
            }
        }
    }
}

fun quote(s: String) = "\"" + s.replace("\\", "\\\\").replace("\"", "\\\"").replace("\n", "\\n") + "\""

fun num(d: Double) = if (d % 1.0 == 0.0 && Math.abs(d) < 1e15) d.toLong().toString() else d.toString()

fun show(v: Json, indent: String = ""): String {
    val inner = "$indent  "
    fun block(open: String, close: String, lines: List<String>) =
        if (lines.isEmpty()) open + close else "$open\n${lines.joinToString(",\n")}\n$indent$close"
    return when (v) {
        Json.Null -> "null"
        is Json.Bool -> v.value.toString()
        is Json.Num -> num(v.value)
        is Json.Str -> quote(v.value)
        is Json.Arr -> block("[", "]", v.items.map { inner + show(it, inner) })
        is Json.Obj -> block("{", "}", v.pairs.map { (k, x) -> "$inner${quote(k)}: ${show(x, inner)}" })
    }
}

fun children(v: Json): List<Json> = when (v) {
    is Json.Arr -> v.items
    is Json.Obj -> v.pairs.map { it.second }
    else -> emptyList()
}

fun leaves(v: Json): Sequence<Json> =
    if (v is Json.Arr || v is Json.Obj) children(v).asSequence().flatMap(::leaves) else sequenceOf(v)

fun depth(v: Json): Int = if (v is Json.Arr || v is Json.Obj) 1 + (children(v).maxOfOrNull(::depth) ?: 0) else 0

fun main() {
    val doc = Parser(DOC).parse()
    println(show(doc))
    val all = leaves(doc).toList()
    val numbers = all.filterIsInstance<Json.Num>().map { it.value }
    println("strings: ${all.count { it is Json.Str }}, numbers: ${numbers.size}, sum: ${num(numbers.sum())}, depth: ${depth(doc)}")
    for (bad in listOf("[1, 2,]", """{"a" 1}""", "\"open")) {
        try {
            Parser(bad).parse()
        } catch (e: ParseError) {
            println("error: ${e.message}")
        }
    }
}

let doc = {|{
  "name": "Ada",
  "langs": ["C", "OCaml", "Prolog"],
  "age": 36, "ratio": -0.25, "big": 1.5e3,
  "active": true, "boss": null,
  "note": "say \"hi\"\n\u00e9t\u00e9",
  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\tmp"}
}|}

type json =
  | Null
  | Bool of bool
  | Num of float
  | Str of string
  | Arr of json list
  | Obj of (string * json) list

exception Parse_error of string

let fail fmt = Printf.ksprintf (fun s -> raise (Parse_error s)) fmt

let parse text =
  let len = String.length text in
  let pos = ref 0 in
  let peek () = if !pos < len then Some text.[!pos] else None in
  let rec ws () = match peek () with Some (' ' | '\t' | '\n' | '\r') -> incr pos; ws () | _ -> () in
  let expect c =
    ws ();
    if peek () <> Some c then fail "expected '%c' at %d" c !pos;
    incr pos
  in
  let looking_at word = !pos + String.length word <= len && String.sub text !pos (String.length word) = word in
  let string () =
    let buf = Buffer.create 16 in
    incr pos;
    let rec loop () =
      match peek () with
      | None -> fail "unexpected end of input"
      | Some '"' -> incr pos; Buffer.contents buf
      | Some '\\' ->
        incr pos;
        (match peek () with
         | Some 'u' ->
           let code = int_of_string ("0x" ^ String.sub text (!pos + 1) 4) in
           Buffer.add_utf_8_uchar buf (Uchar.of_int code);
           pos := !pos + 5
         | Some e ->
           Buffer.add_char buf
             (match e with 'b' -> '\b' | 'f' -> '\012' | 'n' -> '\n' | 'r' -> '\r' | 't' -> '\t' | c -> c);
           incr pos
         | None -> fail "unexpected end of input");
        loop ()
      | Some c -> Buffer.add_char buf c; incr pos; loop ()
    in
    loop ()
  in
  (* Items separated by commas until [close]: the shared shape of arrays and objects. *)
  let items close item =
    incr pos;
    ws ();
    if peek () = Some close then (incr pos; [])
    else
      let rec loop acc =
        let acc = item () :: acc in
        ws ();
        match peek () with
        | Some ',' -> incr pos; loop acc
        | Some c when c = close -> incr pos; List.rev acc
        | _ -> fail "expected ',' or '%c' at %d" close !pos
      in
      loop []
  in
  let rec value () =
    ws ();
    match peek () with
    | None -> fail "unexpected end of input"
    | Some '{' ->
      Obj (items '}' (fun () ->
          ws ();
          if peek () <> Some '"' then fail "expected string at %d" !pos;
          let key = string () in
          expect ':';
          (key, value ())))
    | Some '[' -> Arr (items ']' value)
    | Some '"' -> Str (string ())
    | Some ('-' | '0' .. '9') ->
      let start = !pos in
      while (match peek () with Some ('-' | '+' | '.' | 'e' | 'E' | '0' .. '9') -> true | _ -> false) do
        incr pos
      done;
      Num (float_of_string (String.sub text start (!pos - start)))
    | Some _ when looking_at "true" -> pos := !pos + 4; Bool true
    | Some _ when looking_at "false" -> pos := !pos + 5; Bool false
    | Some _ when looking_at "null" -> pos := !pos + 4; Null
    | Some c -> fail "unexpected '%c' at %d" c !pos
  in
  let v = value () in
  ws ();
  (match peek () with Some c -> fail "unexpected '%c' at %d" c !pos | None -> ());
  v

let quote s =
  let buf = Buffer.create (String.length s + 2) in
  Buffer.add_char buf '"';
  String.iter (function
      | '"' -> Buffer.add_string buf "\\\""
      | '\\' -> Buffer.add_string buf "\\\\"
      | '\n' -> Buffer.add_string buf "\\n"
      | c -> Buffer.add_char buf c) s;
  Buffer.add_char buf '"';
  Buffer.contents buf

let number n =
  if Float.is_integer n && Float.abs n < 1e15 then Printf.sprintf "%.0f" n else Printf.sprintf "%.17g" n

let rec show ?(indent = "") v =
  let inner = indent ^ "  " in
  let block opn cls = function
    | [] -> opn ^ cls
    | lines -> opn ^ "\n" ^ String.concat ",\n" lines ^ "\n" ^ indent ^ cls
  in
  match v with
  | Null -> "null"
  | Bool b -> string_of_bool b
  | Num n -> number n
  | Str s -> quote s
  | Arr items -> block "[" "]" (List.map (fun x -> inner ^ show ~indent:inner x) items)
  | Obj pairs -> block "{" "}" (List.map (fun (k, x) -> inner ^ quote k ^ ": " ^ show ~indent:inner x) pairs)

let children = function Arr items -> items | Obj pairs -> List.map snd pairs | _ -> []

let is_container = function Arr _ | Obj _ -> true | _ -> false

let rec leaves v = if is_container v then List.concat_map leaves (children v) else [ v ]

let rec depth v = if is_container v then 1 + List.fold_left (fun d x -> max d (depth x)) 0 (children v) else 0

let () =
  let d = parse doc in
  print_endline (show d);
  let all = leaves d in
  let numbers = List.filter_map (function Num n -> Some n | _ -> None) all in
  let strings = List.length (List.filter (function Str _ -> true | _ -> false) all) in
  Printf.printf "strings: %d, numbers: %d, sum: %s, depth: %d\n" strings (List.length numbers)
    (number (List.fold_left ( +. ) 0. numbers)) (depth d);
  List.iter (fun bad -> try ignore (parse bad) with Parse_error msg -> Printf.printf "error: %s\n" msg)
    [ "[1, 2,]"; {|{"a" 1}|}; "\"open" ]

% Values: json(Pairs) for objects (Pairs = [Key-Value, ...]), lists for arrays, strings,
% numbers, and the atoms true, false and null. Parsing is a DCG over character codes.

doc(Doc) :- atomic_list_concat([
  '{',
  '  "name": "Ada",',
  '  "langs": ["C", "OCaml", "Prolog"],',
  '  "age": 36, "ratio": -0.25, "big": 1.5e3,',
  '  "active": true, "boss": null,',
  '  "note": "say \\"hi\\"\\n\\u00e9t\\u00e9",',
  '  "nested": {"a": [1, 2, {"b": []}], "c": {}, "path": "C:\\\\tmp"}',
  '}'], '\n', Doc).

parse(Text, Value) :-
    atom_codes(Text, Codes),
    length(Codes, Len),
    nb_setval(json_length, Len),
    phrase(json(Value), Codes).

json(V) --> value(V), ws, end_of_input.

end_of_input --> here(P), [C], !, { throw_at("unexpected '~c' at ~d", [C, P]) }.
end_of_input --> [].

% here(P): the position of the rest of the input, counted from the start.
here(P, S, S) :- nb_getval(json_length, Len), length(S, N), P is Len - N.

throw_at(Format, Args) :- format(string(M), Format, Args), throw(json_error(M)).

ws --> [C], { memberchk(C, ` \t\n\r`) }, !, ws.
ws --> [].

value(V) --> ws, ( peek(C) -> value(C, V) ; { throw(json_error("unexpected end of input")) } ).

peek(C, [C|T], [C|T]).

value(0'{, V) --> !, object(V).
value(0'[, V) --> !, array(V).
value(0'", S) --> !, string(S).
value(C, N) --> { C == 0'- ; code_type(C, digit) }, !, number(N).
value(_, true) --> "true", !.
value(_, false) --> "false", !.
value(_, null) --> "null", !.
value(C, _) --> here(P), { throw_at("unexpected '~c' at ~d", [C, P]) }.

object(json(Pairs)) --> "{", ws, ( "}" -> { Pairs = [] } ; members(Pairs) ).
members([K-V|Ps]) -->
    ws, key(K), ws, expect(0':), value(V), ws,
    (   "," -> members(Ps)
    ;   "}" -> { Ps = [] }
    ;   here(P), { throw_at("expected ',' or '}' at ~d", [P]) }
    ).

key(K) --> peek(0'"), !, string(K).
key(_) --> here(P), { throw_at("expected string at ~d", [P]) }.

expect(C) --> [C], !.
expect(C) --> here(P), { throw_at("expected '~c' at ~d", [C, P]) }.

array(Items) --> "[", ws, ( "]" -> { Items = [] } ; elements(Items) ).
elements([V|Vs]) -->
    value(V), ws,
    (   "," -> elements(Vs)
    ;   "]" -> { Vs = [] }
    ;   here(P), { throw_at("expected ',' or ']' at ~d", [P]) }
    ).

string(S) --> "\"", chars(Cs), { string_codes(S, Cs) }.
chars([]) --> "\"", !.
chars([C|Cs]) --> "\\", !, escape(C), chars(Cs).
chars([C|Cs]) --> [C], !, chars(Cs).
chars(_) --> { throw(json_error("unexpected end of input")) }.

escape(0'\b) --> "b", !.
escape(0'\f) --> "f", !.
escape(0'\n) --> "n", !.
escape(0'\r) --> "r", !.
escape(0'\t) --> "t", !.
escape(C) --> "u", !, [H1, H2, H3, H4], { number_codes(C, [0'0, 0'x, H1, H2, H3, H4]) }.
escape(C) --> [C].

number(N) --> num_codes(Cs), { number_codes(N0, Cs), N is float(N0) }.
num_codes([C|Cs]) --> [C], { memberchk(C, `+-.eE0123456789`) }, !, num_codes(Cs).
num_codes([]) --> [].

% Printing.
show(V) :- show(V, 0).
show(json([]), _) :- !, write('{}').
show(json(Pairs), I) :- !, block('{', '}', Pairs, I).
show([], _) :- !, write('[]').
show(Items, I) :- is_list(Items), !, block('[', ']', Items, I).
show(S, _) :- string(S), !, quote(S).
show(N, _) :- number(N), !, show_number(N).
show(Atom, _) :- write(Atom).

block(Open, Close, Items, I) :-
    I2 is I + 2,
    write(Open), nl,
    show_items(Items, I2),
    tab(I), write(Close).

show_items([X], I) :- !, tab(I), show_item(X, I), nl.
show_items([X|Xs], I) :- tab(I), show_item(X, I), write(','), nl, show_items(Xs, I).

show_item(K-V, I) :- string(K), !, quote(K), write(': '), show(V, I).
show_item(V, I) :- show(V, I).

show_number(N) :- N =:= truncate(N), abs(N) < 1.0e15, !, X is truncate(N), write(X).
show_number(N) :- write(N).

quote(S) :- string_codes(S, Cs), write('"'), forall(member(C, Cs), quote_code(C)), write('"').
quote_code(0'") :- !, write('\\"').
quote_code(0'\\) :- !, write('\\\\').
quote_code(0'\n) :- !, write('\\n').
quote_code(C) :- char_code(Ch, C), put_char(Ch).

% Counting.
leaves(json(Pairs), Ls) :- !, findall(V, member(_-V, Pairs), Vs), maplist(leaves, Vs, Lss), append(Lss, Ls).
leaves([], []) :- !.
leaves(Items, Ls) :- is_list(Items), !, maplist(leaves, Items, Lss), append(Lss, Ls).
leaves(V, [V]).

depth(json(Pairs), D) :- !, findall(X, (member(_-V, Pairs), depth(V, X)), Ds), max_list([0|Ds], M), D is M + 1.
depth(Items, D) :- is_list(Items), !, findall(X, (member(V, Items), depth(V, X)), Ds), max_list([0|Ds], M), D is M + 1.
depth(_, 0).

main :-
    doc(Text),
    parse(Text, Doc),
    show(Doc), nl,
    leaves(Doc, Leaves),
    include(string, Leaves, Strings), length(Strings, NS),
    include(number, Leaves, Numbers), length(Numbers, NN), sum_list(Numbers, Sum),
    depth(Doc, D),
    format("strings: ~d, numbers: ~d, sum: ", [NS, NN]), show_number(Sum), format(", depth: ~d~n", [D]),
    forall(member(Bad, ['[1, 2,]', '{"a" 1}', '"open']),
           catch(parse(Bad, _), json_error(M), format("error: ~s~n", [M]))).

?- main.