nish/json-tokenizer

A validating, streaming tokenizer for RFC 8259 JSON held in a window of a u8[].

import {
  JSON_DEFAULT_MAX_DEPTH,
  JSON_DEFAULT_MAX_NUMBER_BYTES,
  JSON_DEFAULT_MAX_STRING_BYTES,
  JSON_DEFAULT_MAX_TOTAL_BYTES,
  JSON_TOK_ARRAY_BEGIN,
  JSON_TOK_ARRAY_END,
  JSON_TOK_END,
  JSON_TOK_ERR_CONTROL,
  JSON_TOK_ERR_DEPTH,
  JSON_TOK_ERR_ESCAPE,
  JSON_TOK_ERR_NUMBER,
  JSON_TOK_ERR_NUMBER_LIMIT,
  JSON_TOK_ERR_STRING_LIMIT,
  JSON_TOK_ERR_SURROGATE,
  JSON_TOK_ERR_SYNTAX,
  JSON_TOK_ERR_TOTAL_LIMIT,
  JSON_TOK_ERR_TRAILING,
  JSON_TOK_ERR_TRUNCATED,
  JSON_TOK_ERR_UTF8,
  JSON_TOK_ERR_WINDOW,
  JSON_TOK_FALSE,
  JSON_TOK_KEY,
  JSON_TOK_NULL,
  JSON_TOK_NUMBER,
  JSON_TOK_OBJECT_BEGIN,
  JSON_TOK_OBJECT_END,
  JSON_TOK_STRING,
  JSON_TOK_TRUE,
  JsonLimits,
  JsonTokenizer,
} from "nish/json-tokenizer";
import { JsonLimits, JsonTokenizer, JSON_TOK_END, JSON_TOK_KEY } from "nish/json-tokenizer";

const t = new JsonTokenizer(body, 0, toI32(body.length), new JsonLimits());
let k: i32 = t.next();
while (k > 0) {
  if (k === JSON_TOK_KEY && t.keyEquals("message")) {
    // t.next() is the value; t.stringInto(out, 0) copies it out
  }
  k = t.next();
}
// k === JSON_TOK_END: the window held one whole, valid JSON text
// k < 0: a JSON_TOK_ERR_* code, also in t.failed, at byte t.errorAt

std/json's jsonField reads one field of one flat object and validates nothing. A server that takes JSON from a peer needs the opposite: every byte checked against the grammar, nothing allocated per request, and a hard limit on everything an attacker controls. That is this module.

One token per `next()`

It answers a JSON_TOK_* kind — an object or array opening or closing, a key, a string, a number, true, false or null — then JSON_TOK_END once the top-level value is complete and only blanks follow it, and JSON_TOK_END again on every later call. tokStart and tokEnd bound the token's bytes in the source (a string's include its quotes), and depth is the number of containers open after it. Structure is checked as the tokens go by: a comma or colon out of place, a closer that does not match its opener, a second top-level value, or anything but blanks after the first, is an error at the byte where it stands.

Errors are sticky

The first error sets failed to a negative JSON_TOK_ERR_* code and errorAt to the byte offset it was found at, and every later next() answers the same code without reading anything, as nish/net/hpack's decoder does. Nothing an input can hold panics, and no byte outside src[off, off + len) is ever read. reset starts over on a new window with the same limits and the same depth stack, so a server holds one tokenizer per connection and allocates nothing per request.

Strings are checked as UTF-8 and decoded on request

A string may hold any well-formed UTF-8 (RFC 3629: no overlong form, no surrogate code point, nothing past U+10FFFF, no sequence cut short), no raw byte below 0x20, and the escapes of RFC 8259 §7. A \u escape of a high surrogate must be followed at once by one of a low surrogate, and a low surrogate must follow a high one: a lone surrogate escape is an error.

RFC 8259 allows one, but it names no Unicode character, decodes to no valid UTF-8, and is what a peer smuggles past a check done on the decoded bytes, so this module takes the stricter reading (docs/security/json.md, "Lone surrogates"). Nothing is decoded until the caller asks: stringInto writes the decoded bytes of the current key or string into the caller's array, and keyEquals compares them with a string without writing them anywhere.

Numbers are read in the pass that checks them against the grammar

The scan adds the digits into a u64 as it steps over them, eight at a time where eight digits fit before the window's end, and keeps that mantissa, the decimal exponent and the digit count for numberF64, which is correctly rounded, ties to even, in one of three ways. When the mantissa of at most 19 digits is at most 2^53 and the decimal exponent is within ±22, the answer is one exact multiply or divide of two exact doubles (Clinger's fast path).

Any other number of at most 19 digits is the Eisel–Lemire algorithm as fast_float computes it: one or two 64×64-bit products with a truncated power of five, which Mushtak and Lemire prove always decide the rounding for so few digits, so it never needs a fallback. A number of more digits, or with an exponent past JSON_TOK_EXPONENT_CAP, goes to the runtime's parseFloat, which is strtod, from a function whose own arena scope releases the copy it reads, so it leaves the arena where it was.

isInteger and numberI64 read a number written without a fraction or an exponent that fits in an i64, and isU64 and numberU64 one written without a sign either that fits in a u64. Those go by spelling; isIntegral asks whether the value is whole, however it is written (1.0, 1e2), from the text and at any size.

Runs are read in bulk

A string's plain bytes, the blanks between tokens and a number's digits are each stepped over by a loop that reads src directly, bounded by the window's end (or a string's or number's limit, which is never past it) and by the array's length, so a run stops exactly where a read through jsonTokByteAt would have answered -1. The readers of a number already scanned, and stringInto's copy of a string with no escape, read src the same way; every other byte goes through jsonTokByteAt.

Duplicate keys are tokens

{"a":1,"a":2} is two keys; which one wins, or whether a duplicate is an error, is the decision of whatever reads the tokens (docs/security/json.md, JSON-3).

The limits are JsonLimits: nesting depth, bytes in one string, bytes in one number and bytes in the whole window. Each has its own error code and a default sized for a request body, and each is checked before the work it bounds, so a depth bomb costs one byte of stack per level allowed and an over-long string is refused at the first byte past the limit.

Every name here is json-prefixed, because a std/ module is compiled into the program that imports it and the symbol namespace is flat (std/README.md). Every offset is a byte offset, and every constant is an i32, so the module is the same under --number-mode f64 (docs/wp26-stdlib.md §4). Written from RFC 8259 and RFC 3629, except numberF64's Eisel–Lemire path, its table of powers of five and the scan's eight-digit reads, which are adapted from fast_float under the notice above jsonTokW64.

Classes

JsonLimits

What a JsonTokenizer refuses to read, each with its own error code. The tokenizer copies the four numbers when it is made, so changing an object afterwards changes nothing for a tokenizer already made from it. A negative limit is read as zero: with a depth of zero only a scalar top-level value is accepted, with a string limit of zero only "".

class JsonLimits
Member
new JsonLimits() The defaults, JSON_DEFAULT_*.
maxDepth: i32 Containers open at once; the tokenizer allocates one byte of stack per level, once.
maxNumberBytes: i32 Bytes in one number, sign and exponent included.
maxStringBytes: i32 Raw bytes between a string's quotes, escapes counted as written.
maxTotalBytes: i32 Bytes in the window handed to the constructor or to reset.

JsonTokenizer

The tokenizer. One per connection or per document; reset reuses it, and nothing it does after the constructor allocates, except numberF64's parseFloat path, which releases what it allocated before it returns.

The fields a caller reads are depth, kind, tokStart, tokEnd, failed and errorAt. The rest are the cursor and what the scan of the current token found, and are read through the methods.

class JsonTokenizer
Member
new JsonTokenizer(src: u8[], off: i32, len: i32, limits: JsonLimits) A tokenizer over src[off, off + len) held to limits. A negative limit counts as 0, and the depth stack is allocated here, once, maxDepth bytes long, and reset reuses it.
depth: i32 Containers open after the current token.
errorAt: i32 The byte offset in src the error was found at, and -1 until one. Read it only once failed is set: a JSON_TOK_ERR_WINDOW records the off the caller passed, which may itself be negative or past the end of src.
failed: i32 The sticky error, a negative JSON_TOK_ERR_* code; 0 until one.
integral: boolean Whether the current number is written with neither a fraction nor an exponent: the spelling, so 1.0 is not. isIntegral() reads the value.
kind: i32 The current token's kind, the last next() answered; JSON_TOK_END before the first.
src: u8[] The bytes being read. The tokenizer never writes them.
tokEnd: i32 One past the current token's last byte; see tokStart.
tokStart: i32 The current token's bytes, src[tokStart, tokEnd); a string's and a key's include their quotes.
isInteger(): boolean Whether the current token is a number written without a fraction or an exponent whose value fits in an i64: -0 and 9223372036854775807 are, 1.0, 1e2 and 9223372036854775808 are not. That is the spelling rule; isIntegral() asks whether the value is whole.
isIntegral(): boolean Whether the current token is a number whose value is a whole number, however it is written: JSON Schema 2020-12's "integer". -0.0, 1.0, 1e2, 100e-2 and 1e400 are; 1.5, 10e-2 and 1e-400 are not. It says nothing about fitting an i64, and it is not the integral field or isInteger(), which go by spelling and refuse 1.0 and 1e2.

It reads the text, never an f64, so 12345678901234567890.0 and 1e400 answer exactly. With F fraction digits, z trailing zeros across all the digits and the exponent E, the value is whole when every digit is zero or E - F + z >= 0. F and z count bytes of the token, so F - z fits an i32 whatever the limits, and jsonTokDigitsExceed compares E with it without adding up more of E than it needs, so 1e99999999999 answers too.
isText(): boolean Whether the current token is a key or a string.
isU64(): boolean Whether the current token is a number written in digits alone, with no sign, fraction or exponent, whose value fits in a u64: 0 and 18446744073709551615 are; -0, -1, 1.0, 1e2 and 18446744073709551616 are not.
keyEquals(name: string): boolean Whether the current key or string, decoded, is exactly name's bytes; false when the token is neither. Nothing is allocated or written. name.length and charCodeAt are bytes natively. Under Node they are UTF-16 code units, compared one by one against the decoded UTF-8 bytes: an ASCII name answers the same both ways, a genuine non-ASCII name does not match there, and a name whose code units 0x80 to 0xFF spell those bytes does ("é" matches a key "é"). That is the bytes against code units divergence docs/wp33-round-trip.md §3.2 records.
next(): i32 The next token's kind, JSON_TOK_END, or a negative error, which is sticky.
numberF64(): f64 The current number as the nearest f64, ties to even, as JSON.parse reads it: -0 is negative zero, a magnitude past the largest double is an infinity and one below the smallest is zero. 0 when the current token is not a number.
numberI64(): i64 The current number as an i64 when isInteger() holds, and 0 otherwise. Read it after checking isInteger(): a 0 alone does not say which.
numberU64(): u64 The current number as a u64 when isU64() holds, and 0 otherwise. Read it after checking isU64(): a 0 alone does not say which.
reset(src: u8[], off: i32, len: i32): void Starts over on src[off, off + len), keeping the limits and the depth stack, and clearing any error. A window outside src or longer than the total limit is refused here, and the first next() answers it.
skipValue(): i32 Steps over the value the current token starts, so that the next next() answers what follows it. After a key, that is the key's value; after an opener, everything up to and including its closer; after a scalar or a closer, nothing. Answers the kind of the last token it read (the closer, or the scalar), or a negative error.
stringInto(out: u8[], at: i32): i32 Writes the current key's or string's decoded bytes to out from at, and answers how many; -1, writing nothing, when the current token is neither or out has fewer than stringLength() bytes from at.
stringLength(): i32 The current key's or string's length once decoded, or -1 when the token is neither.

Constants

128

JSON_DEFAULT_MAX_DEPTH: i32

The default limits, sized for a request body. A depth of 128 is serde_json's recursion limit and deeper than any document a person writes; a string may be a mebibyte; 256 bytes hold every double in its shortest form many times over; and a body of 16 MiB is past what an HTTP server should buffer anyway.

256

JSON_DEFAULT_MAX_NUMBER_BYTES: i32

The default longest number text, in bytes: room for any double in its shortest form.

1,048,576

JSON_DEFAULT_MAX_STRING_BYTES: i32

The default longest string or key: a mebibyte of raw bytes between its quotes, escapes counted as written.

16,777,216

JSON_DEFAULT_MAX_TOTAL_BYTES: i32

The default largest window, in bytes: a 16 MiB body.

3

JSON_TOK_ARRAY_BEGIN: i32

[.

4

JSON_TOK_ARRAY_END: i32

].

0

JSON_TOK_END: i32

The top-level value is complete and only blanks follow it. Answered again on every later call.

-7

JSON_TOK_ERR_CONTROL: i32

A raw byte below 0x20 inside a string, which RFC 8259 §7 requires to be escaped.

-9

JSON_TOK_ERR_DEPTH: i32

An opening bracket or brace past JsonLimits.maxDepth open containers.

-5

JSON_TOK_ERR_ESCAPE: i32

A backslash not followed by one of "/bfnrt, or a \u not followed by four hex digits.

-8

JSON_TOK_ERR_NUMBER: i32

A number outside the RFC 8259 §6 grammar: -a, 1.a, 1ex, -Infinity. A number the window cuts short (1., -) is JSON_TOK_ERR_TRUNCATED.

-11

JSON_TOK_ERR_NUMBER_LIMIT: i32

A number longer than JsonLimits.maxNumberBytes bytes.

-10

JSON_TOK_ERR_STRING_LIMIT: i32

A string, or a key, longer than JsonLimits.maxStringBytes bytes between its quotes.

-6

JSON_TOK_ERR_SURROGATE: i32

A \u escape of a surrogate that is not one half of a high-then-low pair.

-1

JSON_TOK_ERR_SYNTAX: i32

A byte that cannot stand where it stands: [1,], {"a" 1}, [1}, [01], +1, .5, nulx, a byte outside a string that is not ASCII.

-12

JSON_TOK_ERR_TOTAL_LIMIT: i32

A window longer than JsonLimits.maxTotalBytes bytes. Answered by the first next(), before anything is read.

-3

JSON_TOK_ERR_TRAILING: i32

Something other than blanks after the top-level value: [] [], 1 2, a trailing NUL.

-2

JSON_TOK_ERR_TRUNCATED: i32

The window ended inside a value: an empty window, [1,, {"a":, an unclosed string.

-4

JSON_TOK_ERR_UTF8: i32

A string holds a byte sequence that is not UTF-8: an overlong form, a surrogate, a code point past U+10FFFF, a sequence cut short by a byte that does not continue it, a stray continuation byte.

-13

JSON_TOK_ERR_WINDOW: i32

off and len do not describe a window inside src. Answered by the first next().

9

JSON_TOK_FALSE: i32

false.

5

JSON_TOK_KEY: i32

A member's name: a string followed by its colon. The value is the next token.

10

JSON_TOK_NULL: i32

null.

7

JSON_TOK_NUMBER: i32

A number value.

1

JSON_TOK_OBJECT_BEGIN: i32

{.

2

JSON_TOK_OBJECT_END: i32

}.

6

JSON_TOK_STRING: i32

A string value.

8

JSON_TOK_TRUE: i32

true.