std.json: parsing and writing JSON with nothing the caller did not hand it

Status: built. std/json.cho; tests tests/lex/json_*_test.cho (29, run by cancho test), conformance/json.rs; drivers under tests/programs/. Strict RFC 8259; no tree, no allocation of its own. §5 has the numbers, and §6 has the two compiler bugs it found.

1. Why

The question that started this was whether a FastAPI-shaped package is buildable here, and the first thing it needs is the thing every request carries. There was no JSON in the language at all: the VCS op log is JSON on the Rust side, --output json is JSON out of the CLI, and examples/serve writes {"ok":true} as a string literal.

2. The design: a tape, not a tree

A value tree is a heap, a free list and a drop order for every document, and a request handler wants none of them. std.json parses into a tape the caller provides: one flat [int], three ints a node, that points back into the source bytes instead of copying them.

let tape = alloc_slice[a](json.tape_len(body), 0);     // or a heap slice
let nodes = json.parse(body, tape);
let age = json.to_int(body, tape, json.get(body, tape, 0, "age"));

• A node is named by its index; -1 is “no node”, and every accessor answers its zero value for it, so get(get(get(..))) needs no check between steps.
• A string is not decoded until asked for: the node holds the byte range inside the quotes and a flag saying whether it has an escape. A string with none (string_plain) is its bytes in the source, borrowed with no copy (string_view). A number is not converted until asked for: an object is walked for the key and the one value, and the other forty are never turned into anything.
• An object’s children are its pairs in order; a key at node k has its value at k + 1 and the next key at skip(k + 1). at and get are linear in the position, which is what a flat list costs and what a request body of a few dozen fields makes irrelevant.

This is simdjson’s shape, and it is the shape here for a different reason: it is the one that needs no ownership. Everything lives in a slice the caller already knows how to size (tape_len is always enough: a node is at least a byte) and free.

Writing goes the other way, through a Writer that owns a std.buffer, puts the commas, colons and quotes in itself, and is moved through every call like a Buffer is, because growing it replaces the allocation under it.

3. What it decides

3.1 parse_with: no region per call

parse begins region a { let st = alloc_slice[a](2, 0); ... }: two ints of state in an arena made and freed on every call. A caller that parses one large document never notices. A caller that parses a million small ones (JSON lines, one request body after another) pays for the arena a million times, and on macOS that is nearly all of what a call costs. cancho-table’s reader design (docs/readers.md §6) measured it and asked for this.

let st = alloc_slice[a](2, 0);                 // or a heap slice; once
let tape = alloc_slice[a](12288, 0);           // once
let nodes = json.parse_with(line, tape, st);   // per document, no region

st is at least two ints. Their contents on entry do not matter (parse_with sets them), so one st serves any number of documents and nothing of one document is visible to the next. A shorter st is the caller’s bug and traps at the first store, as any index out of range does. parse is unchanged, byte for byte, so no identity that mentions it moved (§3.3). The name is parse_with (open to a better one; readers.md §6 used it for its spike, and it sorts beside parse).

Measured (benches/json_lines.py: 1,000,000 JSON lines of 72 bytes, {"id":..,"status":.., "bytes":..,"path":..,"note":..}, the task per line parse, get of status and bytes, two to_int, a count and a sum; cost per line = (best of 5 runs of 11 rounds − best of 5 runs of 1 round) / 10 rounds / lines, so reading the file drops out; every mode’s answer is compared with the rows’ before it is timed). parse is one tape reused for every line; region is a tape allocated in a region per line, which is what a first version writes.

Per line is wall time over all lines, so a perfectly parallel mode divides by the thread count. parse on the Mac does the opposite: 1.6 µs per line at 16 threads against 0.57 µs at 1, 2.6x slower with 16 threads than with one (2.9x in the re-measured run): a region is a malloc and a free, and this allocator does not scale with threads here (not diagnosed further); parse_with goes from 94 to 9.7 ns, 9.6x. On Linux the arena is cheap (about 30 ns), so the gain at one thread is small (1.02x in the re-measured run, 1.18x in the earlier one), which is what readers.md predicted (283 against 255). The number worth having is the Mac’s: it is where a user’s laptop is, and where “a library function that gets slower when you add threads” costs a day to find.

3.2 The differential

parse_with is the same grammar as parse and a second copy of its body (a call from parse would have been shorter and would have moved parse’s identity, §3.3), so the claim that they agree is tested rather than argued. tests/programs/json_with_diff.cho runs both on every document, into a tape of the right size and into one too short (where the full code and the partial tape come from), with the state slice still holding the previous document’s garbage, and compares the answers and every int of both tapes. conformance/json.rs feeds it 58,733 documents (11,444 accepted, 47,289 refused): the seeds, every prefix of every seed, every short seed with each of 39 pool bytes in each position, 40,000 randomly damaged seeds and the edge documents of the JSON test suites written out (depth 127, 128, 129, 1000 and 100,000, lone surrogates, overlong and truncated UTF-8, a BOM, 01, 1., NaN, comments, trailing bytes). Zero differences. A second test classifies the edge documents with serde_json so that “they agree” cannot mean “both wrong the same way”. scripts/json_with_suite.py runs nst/JSONTestSuite (318 files; not vendored): 95 y_ all accepted, 188 n_ all refused, 10 i_ accepted and 25 refused, parse and parse_with agreeing on all 318, answers and tapes. Breaking parse_with three ways (not resetting the node count, not checking trailing bytes, an off-by-one error position) fails the differential each time (differ 3, differ 37, differ 0 is the document index that caught it).

3.3 Identity

Adding parse_with adds a body and a sig to std.json and changes none: cancho ids --std over a program that imports every std module lists 1,805 identities on origin/main (6a8bc1ed; 1,677 when this was first measured, before more std modules arrived) and the same 1,805 plus those two on this branch (comm finds nothing only on origin/main). Over the programs in tests/ and examples/ that cancho ids can read, 95 list identical identities with and without this change; with --std all 211 differ by exactly those two lines and nothing else. (The earlier run reported 165.)

4. Why it can be trusted

• Numbers: 13,000 of them, bit for bit. conformance/json.rs reads a corpus with Rust’s str::parse::<f64> (correctly rounded) as the reference: random doubles over every exponent in their shortest form, 17-digit decimals, the exact decimal midpoint between two adjacent floats and one digit either side of it (the case a floating-point shortcut gets wrong, built from m * 5^s / 10^s in 128-bit integers), integers on both sides of 2^53 and of int’s ends, subnormals, the overflow edge, and exponents of a million digits. Zero mismatches.

  Corrected: that corpus built its halfway cells only among the normal floats (m of 54 bits, shifts under 26), so “and subnormals” meant random subnormals in their shortest form – which no tie can be – and the claim above said more than it tested. A downstream table reader found that to_float read the exact halfway point between two of the larger subnormals (between about 1e-308 and 2^-1022: the 768 significant digits of (2k+1) * 2^-1075) to the wrong neighbour about half the time: the digit cap was 767, so the final 5 was dropped as a “sticky” digit, the tie became a value above the middle, and it went up whatever the parity. Measured: 33,541 of the 1,000,000 cells of float_text.rs (3.4%; 440 of 1,700 in the first reproduction, and 113 of 400 exact midpoints of 52-bit subnormals) read wrong, none in any other shape. The cap is 768 now. conformance/float_text.rs reads 1,000,000 cells against Rust’s parse – the halfway point, a hair above and a hair below it for every subnormal below 64 units, for the largest subnormals and smallest normals, for 30,000 anywhere, and up to DBL_MAX plus half an ulp (a tie that rounds to infinity) – and scripts/float_differential.py runs the same driver against Python’s float() and against exact rational arithmetic (fractions), 1,000,000 cells, 0 differences. The same run checks to_int against an i128 parse clamped to i64.

• Accept and refuse what serde_json does, over damaged input. Ten valid documents and 1,500 mutations of them (one to two bytes replaced, deleted, inserted, swapped or truncated from a pool of structural and non-ASCII bytes): 291 accepted by both, 1,218 refused by both, no disagreement. Every accepted one is written back out by std.json’s own writer and read by serde_json to the same value. One policy difference, found by it and declared in §3: 1.5e22100 is a number serde_json refuses as out of range and this accepts as an infinity.

• 29 library tests, in the language, on both backends (tests/lex/): every error code with its position, UTF-8 corner cases built byte by byte in a buffer, escape decoding including a surrogate pair, saturation at both ends of int, writer output exact to the byte, and 1,500 floats written and read back to the same bits.

• Misuse traps are checked by building eight misusing programs and confirming each dies by signal.

4.1 The part that was hard: reading a float

A decimal with 15 or fewer digits and a power of ten within 10^±22 is two exact floats and one correctly rounded operation (Clinger’s fast path). Everything else – and a random double printed in 17 digits is the common case – needs exact arithmetic, because m * 10^e in floating point is off by an ulp often enough to break a round trip. slow_decimal does it with std.bignum: the digits (up to 768, the most a halfway point can have, plus a sticky digit for the rest) and the power of ten become bignums, scaled so the quotient has 56–57 bits, divided bit by bit, and rounded on those bits with the remainder as the sticky bit. Limbs are sized to the number (a 17-digit one needs a dozen where a worst-case one needs hundreds), which is what took it from 18 µs to under 1 µs.

5. Measured

tests/programs/json_bench.cho and json_write_bench.cho; timing from outside as the difference between one round and twenty-one, so the byte-at-a-time stdin read is left out. A 4-core sandbox; Python 3.11’s C json, which builds every Python object where the tape builds none – the comparison is real for a handler that touches a few fields and unfair to the tape for one that needs every value, so both columns are given.

Reading

Writing 200,000 small objects (id, name, a score of the form n/8, a bool, a two-element array), 15.7 MB, byte-for-byte the same bytes as json.dumps(separators=(",", ":")):

The honest reading. Scanning is fast and conversion is not uniformly: 17-digit floats are the weak case (about 0.9 µs each, 3.3× slower than Python’s float()), and writing a 17-digit float is slower still (§7). A handler reading a few fields and writing a short reply is at the top of both tables; one that converts 300,000 random doubles is not.

6. Found along the way

Writing a module that is the third to declare a pub fn drop found two compiler bugs, both with their own regression test (conformance/modules.rs, both backends), and modules.md §3.1.1 records them:

• Functions: every function was emitted as lexs_<name>. The type checker accepted two modules each declaring drop; the assembler refused with invalid redefinition of function 'lexs_drop'. Symbols are module.name now.
• Statics (silent, and worse): a static was looked up among every module’s and the first taken, so two modules each with static table read one table. a.first() * 10 + b.first() answered 55 where the tables held 5 and 7. Looked up in its own module now.

And one change outside this module’s files that it needed: std.fmt’s float_into prints a number with a short decimal form (3.5, 19.99, 0.000125) without the exact algorithm (a candidate m / 10^k is checked by one exact division; 10^-k wider than a float’s spacing makes the candidate unique, so it is the shortest and the nearest). That took float writing from 6 µs to under 0.5 µs where it applies, and the existing oracle test (against Rust’s {:e}) now includes 2,000 short decimals and their one-ulp neighbours, which must fall back correctly.

6.1 Splicing a document in: put_fragment

The writer had no way to take an already-written value – a schema another library generated, a stored row, a cached answer – so a service assembling an OpenAPI document or a list response from stored JSON built it by hand with a Buffer and commas, correct only by construction. put_fragment(heap, w, fragment) writes the fragment as the next value, with the writer’s own commas and colons. The fragment is checked: parsed with this module’s strict parser, it must be exactly one value (whitespace around it is fine); a second value, a trailing comma, or nothing traps, for the reason finish traps on an open container – splicing a non-value makes the whole document invalid from a distance. The cost is one pass over the fragment and a tape freed before it returns. (put_raw is the writer’s private helper for null, true and the rest, and is not that: it trusts its text.)

7. What it does not do

8. Open