Design: a streaming JSON parser built around controlling memory

[SeanTAllen]

The problem

The json package parses a whole document at once. You hand JsonParser a complete string and it hands back a JsonValue. That's the right tool most of the time. It's the wrong tool when the document arrives in pieces over a socket, or when it's too big to hold in memory. There is no incremental path.

#5558, an open pull request, adds an incremental parser. It hands back each top-level value as it completes, so a stream of separate values, object after object off a socket, works. What it doesn't do is stream within a value. It builds the whole JsonValue and hands it back only when that value's root container closes, so a single large document, the case that most needs streaming, is built whole in memory before you see any of it. That's exactly the cost streaming is supposed to avoid.

So the goal that drives this design is narrow and specific: the user controls how much memory the parse uses. Not the parser. The user.

What "controls memory" means

A whole-tree parser is O(document). You pay for every byte of structure, with no way to opt out. That fails the goal on its own.

The parser's own memory should never scale with the document. Its floor is three things: the container-depth stack, the one string or number it's partway through, and the fed bytes it hasn't consumed yet. The streaming design carries depth and size caps (from #5558's JsonStreamLimits) that bound the first two, and the unconsumed bytes are bounded by how much you feed before you drain. Nothing there is document-sized.

Everything above that floor is a choice the caller makes. Process each piece and drop it, and memory stays flat. Keep a value, and you pay for that value. Want the whole document as one JsonValue, and you pay for the whole document, but that's your choice, not one baked into the parser.

The design

An incremental token stream

Feed bytes in, get tokens pushed out: object start, a key, a value, object end, and the matching array-start and array-end. The parser walks the full structure to any depth and builds no tree. Its working memory is the depth stack plus whatever single value it's mid-parse on.

We already have most of this. JsonTokenParser walks a document and pushes exactly these tokens to a notify callback. The one thing it can't do is stop in the middle. It needs the whole document up front: run out of bytes partway through a token and it raises the same error a malformed byte would, and it keeps no state to pick up from. The streaming parser is that same token walk made resumable, and it replaces JsonTokenParser. Feeding a whole document at once is just the case where every byte is already in hand. When a chunk ends 12 bytes into a 14-byte token, the parser holds the unfinished part and stitches the next feed onto it. You never manage the leftover bytes.

The parser is push. You feed it bytes, tokens land in your notifier, and abort stops it when you've seen enough.

Tokens carry their values

Today a token is a bare primitive and the value rides a field. After a JsonTokenKey you read parser.last_string; after a JsonTokenNumber you read parser.last_number. That field is live only until the next token overwrites it, and Key and String share last_string, so in {"id":"foo"} the key "id" is already gone by the time the string value fires. You have to grab the value the instant its token arrives, and you can't hold a token to look at later.

Make the tokens carry their own values instead:

type JsonToken is
  ( JsonTokenObjectStart | JsonTokenObjectEnd
  | JsonTokenArrayStart  | JsonTokenArrayEnd
  | JsonTokenTrue | JsonTokenFalse | JsonTokenNull   // primitives; the type is the value
  | JsonTokenKey | JsonTokenString | JsonTokenNumber ) // classes; carry a value

class val JsonTokenNumber
  let value: (I64 | F64)
  new val create(value': (I64 | F64)) => value = value'
// JsonTokenKey and JsonTokenString have the same shape with a String value

Now you match and read the value off the token:

match token
| let k: JsonTokenKey    => // k.value
| let n: JsonTokenNumber => // n.value
| JsonTokenObjectStart   => // ...
end

Nothing shared, nothing to overwrite, and a token is a value you can hold. That last part is what the rest of the design leans on: a token that carries its own value is what lets that value be a zero-copy view instead of a clobbered field, and what lets you hold a run of tokens to hand to the reassembler. The structural and literal tokens carry nothing, so they stay primitives.

Zero-copy strings, most of the time

Reassembling a streamed string doesn't have to allocate. The reader for this parser, modeled on the msgpack streaming decoder's ZeroCopyReader, holds each fed chunk as it arrived and hands back a trim view into it when a string sits inside a single chunk and has no escapes. String.from_iso_array turns that view into a String with no copy either.

Two cases fall back to a copy. Escapes: "a\nb" decodes to different bytes than the source, so the decoded form has to be built. A boundary split: a string that starts in one fed chunk and finishes in the next isn't contiguous, so the pieces have to be joined. The scan that finds the closing quote also turns up any escapes, so the copy-or-not choice is settled during that scan, before anything is built.

The decoder drives this by peeking a whole value before it consumes any bytes: if the value isn't fully present yet, nothing is consumed, and the next feed continues it. That's what handles a value split across a feed boundary without you stitching bytes by hand. The one place JSON is harder than MessagePack is that MessagePack length-prefixes its strings, so the decoder reads a length; JSON has no length, so it scans to the closing quote.

Skipping is just not using a token

Most streaming work reads a few fields out of a big document and ignores the rest. There's no skip operation for that, and it doesn't need one. You ignore the tokens you don't want, the same way for an object member or an array element. Zero-copy is what makes ignoring cheap: a string you don't use was never copied, so dropping its token costs nothing but the view.

Ignoring a large subtree still walks its bytes and builds a token per element inside. That's small, and no string copies, but not free. A dedicated skip that fast-forwards past a subtree and builds nothing could cut even that. It's left out for now, and because it's additive it can land later, once there's a real use case or two to design it against.

Reassembly, when you want it

Tokens are the floor. When you want a JsonValue instead, there's a standalone reassembler: hand it any run of tokens, and if that run forms complete JSON values you get those values back; if the run ends mid-value you get IncompleteValue. What it builds is an ordinary JsonValue, the same representation JsonParser returns from a whole document, so whichever path you take, whole-document or incremental, the value you end up holding is the same. It's the same work the private _TreeBuilder already does for JsonParser, moved from the forced default to something you reach for when you want it.

Nothing is automatic. You choose which tokens to hand it, so you choose how much it builds, and that choice is where the memory cost lands. Hand it the whole run and you've buffered the whole document. Hand it one record's worth of tokens, take the value, drop it, and move on, and memory stays flat. It's the caller's call either way.

What this changes

The value-carrying tokens are a breaking change to the public JsonTokenParser. The token primitives become classes, last_string/last_number go away, and any JsonTokenNotify that reads those fields moves to reading the value off the token. It's a mechanical migration.

The batch JsonParser is built on JsonTokenParser through the private _TreeBuilder, which reads those fields. _TreeBuilder gets rewritten to read the new tokens, but JsonParser.parse's signature and behavior don't change, so batch callers are untouched. JsonValue, JsonObject, JsonArray, JsonPrinter, JsonNav, JsonLens, and JsonPath don't change at all, so everything you already do with a parsed value keeps working on a streamed one.

The break is worth taking. There's one token vocabulary across the batch parser's internals and the streaming parser, so the code that handles tokens is identical between them. A notifier you wrote against one plugs straight into the other; moving between them changes how you feed bytes, not how you handle what comes out. The break also fixes the field design everywhere instead of leaving it in the old parser, and it leaves one token type to learn instead of two that look almost alike.