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
JsonLimits
What a JsonTokenizer refuses to read, each with its own error code.
JsonTokenizer
The tokenizer.
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.

