1	# JSON values, parsed and encoded as RFC 8259. Source: https://github.com/paymog/bend-kit/tree/main/json
2	import Base
3	import bend-kit-bytes@0.3.2.0/bytes.bend as Bytes
4	
5	# JSON (RFC 8259) as UTF-8 in Bytes. Strings, numbers and object keys are
6	# UTF-8 Bytes too. The shared parser keeps its own stack. parse.bytes preserves
7	# the RFC §8.2 replacement contract; parse.strict.bytes rejects lone surrogates
8	# and limits open arrays/objects before parsing their contents.
9	
10	# Num keeps the number's exact text, so no precision is lost. Obj keeps its
11	# fields in document order, repeated keys included.
12	type Val is Type:
13	  Null{}
14	  Flag{on: Bool}
15	  Num{s: Bytes.Bytes}
16	  Str{s: Bytes.Bytes}
17	  Arr{xs: List<&1, Val>}
18	  Obj{kvs: List<&1, Bytes.Bytes & Val>}
19	
20	# An open container: array items so far, object fields so far, or those fields
21	# and the key whose value comes next. Items and fields are reversed.
22	type Open is Type:
23	  OArr{xs: List<&1, Val>}
24	  OObj{kvs: List<&1, Bytes.Bytes & Val>}
25	  OKey{kvs: List<&1, Bytes.Bytes & Val>, key: Bytes.Bytes}
26	
27	# Writer
28	# ------
29	# Octets being written: the buffer, its size in words, the count so far, and
30	# the word being filled. Bytes enter at the top of w, as in Bytes.from_string.
31	type W is Type:
32	  W{buf: Array<U32>, cap: U32, n: U32, w: U32}
33	
34	# The buffer doubles when word k does not fit.
35	def w.room(grow: Bool, buf: Array<U32>, +k: U32) -> Array<U32>:
36	  match grow:
37	    case True{}:
38	      Bytes.grow((k * 4 : U32), buf, (k * 8 : U32))
39	    case False{}:
40	      buf
41	
42	def w.store(full: Bool, buf: Array<U32>, +cap: U32, +n: U32, +w: U32) -> W:
43	  match full:
44	    case True{}:
45	      +k = (n >> 2n : U32)
46	      +g = U32.is_eq(k, cap)
47	      W{Array.set(U32, w.room(g, buf, k), k, w), Bool.pick(U32, g, (cap * 2 : U32), cap), (n + 1 : U32), 0}
48	    case False{}:
49	      W{buf, cap, (n + 1 : U32), w}
50	
51	def w.put(o: W, +b: U32) -> W:
52	  W{buf, +cap, +n, +w} = o
53	  w.store(U32.is_eq((n .&. 3 : U32), 3), buf, cap, n, ((w >> 8n) .|. (b << 24n) : U32))
54	
55	def w.shrink(fit: Bool, +n: U32, buf: Array<U32>) -> Array<U32>:
56	  match fit:
57	    case True{}:
58	      buf
59	    case False{}:
60	      Bytes.dst(Bytes.copy(n, buf, Bytes.alloc(n), 0, 0))
61	
62	# Stores the last partial word, then copies into the fewest words, as Bytes requires.
63	def w.done(o: W) -> Bytes.Bytes:
64	  W{buf, +cap, +n, +w} = o
65	  +r = (n .&. 3 : U32)
66	  +k = (n >> 2n : U32)
67	  +g = U32.is_ne(r, 0) && U32.is_eq(k, cap)
68	  +cap2 = Bool.pick(U32, g, (cap * 2 : U32), cap)
69	  out = Bytes.flush(U32.is_ne(r, 0), w.room(g, buf, k), k, U32.shrn(w, U32.to_nat((((4 - r) .&. 3) * 8 : U32))))
70	  Bytes.Bytes{n, w.shrink(U32.is_eq(U32.shln(1, Bytes.depth(Bytes.words(n))), cap2), n, out)}
71	
72	def w.cont(+c: U32, +k: Nat) -> U32:
73	  (128 + (U32.shrn(c, k) .&. 63) : U32)
74	
75	def w.cp.of(+n: U32, +c: U32, o: W) -> W:
76	  match n:
77	    case 1:
78	      w.put(o, c)
79	    case 2:
80	      w.put(w.put(o, (192 + U32.shrn(c, 6n) : U32)), w.cont(c, 0n))
81	    case 3:
82	      w.put(w.put(w.put(o, (224 + U32.shrn(c, 12n) : U32)), w.cont(c, 6n)), w.cont(c, 0n))
83	    case _:
84	      w.put(w.put(w.put(w.put(o, (240 + U32.shrn(c, 18n) : U32)), w.cont(c, 12n)), w.cont(c, 6n)), w.cont(c, 0n))
85	
86	# One code point in UTF-8.
87	def w.cp(+c: U32, o: W) -> W:
88	  w.cp.of(Bool.pick(U32, U32.is_lt(c, 128), 1, Bool.pick(U32, U32.is_lt(c, 2048), 2, Bool.pick(U32, U32.is_lt(c, 65536), 3, 4))), c, o)
89	
90	def w.hex(+n: U32) -> U32:
91	  Bool.pick(U32, U32.is_lt(n, 10), (48 + n : U32), (87 + n : U32))
92	
93	def w.new() -> W:
94	  W{Bytes.alloc(0), 1, 0, 0}
95	
96	def w.of.at(+len: U32, +cap: U32, r: Array<U32> & U32) -> W:
97	  (buf, +v) = r
98	  +m = (len .&. 3 : U32)
99	  W{buf, cap, len, Bool.pick(U32, U32.is_eq(m, 0), 0, U32.shln(v, U32.to_nat(((4 - m) * 8 : U32))))}
100	
101	# A writer that appends to b.
102	def w.of(b: Bytes.Bytes) -> W:
103	  Bytes.Bytes{+len, buf} = b
104	  w.of.at(len, U32.shln(1, Bytes.depth(Bytes.words(len))), Array.get(U32, buf, (len >> 2n : U32)))
105	
106	def w.text(s: String, o: W) -> W:
107	  match s:
108	    case SNil{}:
109	      o
110	    case SCon{Chr{+c}, t}:
111	      w.text(t, w.cp(c, o))
112	
113	# Text, one Char per code point, as UTF-8.
114	def utf8(s: String) -> Bytes.Bytes:
115	  w.done(w.text(s, w.new()))
116	
117	# Numbers (§6)
118	# ------------
119	# States: 0 start, 1 after "-", 2 after a leading "0", 3 int digits, 4 after
120	# ".", 5 fraction digits, 6 after "e", 7 after the exponent sign, 8 exponent
121	# digits. 99 means the char does not continue the number.
122	
123	def digit(+c: U32) -> Bool:
124	  Bool.and(U32.is_le(48, c), U32.is_le(c, 57))
125	
126	def num.trans(+st: U32, +c: U32) -> U32:
127	  +d = digit(c)
128	  +z = U32.is_eq(c, 48)
129	  +dot = U32.is_eq(c, 46)
130	  +e = Bool.or(U32.is_eq(c, 101), U32.is_eq(c, 69))
131	  +sign = Bool.or(U32.is_eq(c, 43), U32.is_eq(c, 45))
132	  Bool.pick(U32, U32.is_eq(st, 0), Bool.pick(U32, U32.is_eq(c, 45), 1, Bool.pick(U32, z, 2, Bool.pick(U32, d, 3, 99))),
133	  Bool.pick(U32, U32.is_eq(st, 1), Bool.pick(U32, z, 2, Bool.pick(U32, d, 3, 99)),
134	  Bool.pick(U32, Bool.or(U32.is_eq(st, 2), U32.is_eq(st, 3)), Bool.pick(U32, Bool.and(d, U32.is_eq(st, 3)), 3, Bool.pick(U32, dot, 4, Bool.pick(U32, e, 6, 99))),
135	  Bool.pick(U32, Bool.or(U32.is_eq(st, 4), U32.is_eq(st, 5)), Bool.pick(U32, d, 5, Bool.pick(U32, Bool.and(e, U32.is_eq(st, 5)), 6, 99)),
136	  Bool.pick(U32, U32.is_eq(st, 6), Bool.pick(U32, sign, 7, Bool.pick(U32, d, 8, 99)),
137	  Bool.pick(U32, Bool.or(U32.is_eq(st, 7), U32.is_eq(st, 8)), Bool.pick(U32, d, 8, 99), 99))))))
138	
139	def num.accepts(+st: U32) -> Bool:
140	  Bool.or(Bool.or(U32.is_eq(st, 2), U32.is_eq(st, 3)), Bool.or(U32.is_eq(st, 5), U32.is_eq(st, 8)))
141	
142	# Strings (§7)
143	# ------------
144	
145	def hexd(+c: U32) -> U32:
146	  Bool.pick(U32, digit(c), (c - 48 : U32), Bool.pick(U32, Bool.and(U32.is_le(97, c), U32.is_le(c, 102)), (c - 87 : U32), Bool.pick(U32, Bool.and(U32.is_le(65, c), U32.is_le(c, 70)), (c - 55 : U32), 99)))
147	
148	def is_hi(+v: U32) -> Bool:
149	  Bool.and(U32.is_le(55296, v), U32.is_le(v, 56319))
150	
151	def is_lo(+v: U32) -> Bool:
152	  Bool.and(U32.is_le(56320, v), U32.is_le(v, 57343))
153	
154	def esc.simple(+e: U32) -> U32:
155	  Bool.pick(U32, U32.is_eq(e, 34), 34, Bool.pick(U32, U32.is_eq(e, 92), 92, Bool.pick(U32, U32.is_eq(e, 47), 47,
156	  Bool.pick(U32, U32.is_eq(e, 98), 8, Bool.pick(U32, U32.is_eq(e, 102), 12, Bool.pick(U32, U32.is_eq(e, 110), 10,
157	  Bool.pick(U32, U32.is_eq(e, 114), 13, Bool.pick(U32, U32.is_eq(e, 116), 9, 99))))))))
158	
159	# Parse
160	# -----
161	# A state holds the offset of its next byte; the buffer goes beside it. A
162	# string with no escape is copied out of the buffer when it closes; at its
163	# first escape it moves into a writer.
164	
165	type Sb is Type:
166	  BValue{i: U32, stack: List<&1, Open>}
167	  BFirst{i: U32, open: Open, stack: List<&1, Open>}
168	  BKey{i: U32, stack: List<&1, Open>}
169	  BColon{key: Bytes.Bytes, i: U32, stack: List<&1, Open>}
170	  BStr{i: U32, start: U32, key: Bool, stack: List<&1, Open>}
171	  BEsc{i: U32, acc: W, key: Bool, stack: List<&1, Open>}
172	  BNum{i: U32, start: U32, st: U32, stack: List<&1, Open>}
173	  BAfter{v: Val, i: U32, stack: List<&1, Open>}
174	  BSep{i: U32, open: Open, stack: List<&1, Open>}
175	  BEnd{v: Val, i: U32}
176	  BOk{v: Val}
177	  BFail{}
178	
179	type Cp is Data:
180	  Cp{c: U32, w: U32}
181	
182	def pk.if(ok: Bool, a: Array<U32>, +i: U32) -> Array<U32> & U32:
183	  match ok:
184	    case True{}:
185	      Bytes.peek(a, i)
186	    case False{}:
187	      (a, 256)
188	
189	# Byte i, or 256 at the end, which no rule accepts.
190	def pk(a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & U32:
191	  pk.if(U32.is_lt(i, len), a, i)
192	
193	def is_ws(+c: U32) -> Bool:
194	  U32.is_eq(c, 32) || U32.is_eq(c, 9) || U32.is_eq(c, 10) || U32.is_eq(c, 13)
195	
196	# A string byte that needs no check: ASCII, not a control, quote or backslash.
197	def plain(+c: U32) -> Bool:
198	  U32.is_le(32, c) && U32.is_lt(c, 128) && U32.is_ne(c, 34) && U32.is_ne(c, 92)
199	
200	def pos.of(+i: U32, r: Array<U32> & U32) -> Array<U32> & U32 & U32:
201	  (a, +c) = r
202	  (a, i, c)
203	
204	# The offset i and its byte.
205	def pos(a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & U32 & U32:
206	  pos.of(i, pk(a, len, i))
207	
208	def run.cls(~ok: @+c: U32 -> Bool, r: Array<U32> & U32) -> Array<U32> & U32 & Bool:
209	  (a, +c) = r
210	  (a, c, ok(c))
211	
212	# g bounds the loop; it is the parser's fuel, shared, so no count is built per run.
213	def run.go(~ok: @+c: U32 -> Bool, g: Nat, r: Array<U32> & U32 & Bool, +len: U32, +i: U32) -> Array<U32> & U32 & U32:
214	  match g:
215	    case 0n:
216	      (a, +c, more) = r
217	      (a, i, c)
218	    case 1n+h:
219	      (a, +c, more) = r
220	      match more:
221	        case True{}:
222	          run.go(~ok, h, run.cls(~ok, pk(a, len, (i + 1 : U32))), len, (i + 1 : U32))
223	        case False{}:
224	          (a, i, c)
225	
226	# The first offset from i whose byte is not ok, and that byte.
227	def run(~ok: @+c: U32 -> Bool, +g: Nat, a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & U32 & U32:
228	  run.go(~ok, g, run.cls(~ok, pk(a, len, i)), len, i)
229	
230	def word.go(w: String, ok: Bool, r: Array<U32> & U32, +len: U32, +j: U32) -> Array<U32> & Bool:
231	  match w:
232	    case SNil{}:
233	      (a, b) = r
234	      (a, ok)
235	    case SCon{Chr{+c}, t}:
236	      (a, +b) = r
237	      word.go(t, ok && U32.is_eq(b, c), pk(a, len, (j + 1 : U32)), len, (j + 1 : U32))
238	
239	# Do the bytes from j spell w?
240	def word(a: Array<U32>, +len: U32, w: String, +j: U32) -> Array<U32> & Bool:
241	  word.go(w, True{}, pk(a, len, j), len, j)
242	
243	def hex4.b.go(n: Nat, r: Array<U32> & U32, +len: U32, +j: U32, +acc: U32) -> Array<U32> & U32:
244	  match n:
245	    case 0n:
246	      (a, b) = r
247	      (a, acc)
248	    case 1n+k:
249	      (a, +b) = r
250	      +h = hexd(b)
251	      hex4.b.go(k, pk(a, len, (j + 1 : U32)), len, (j + 1 : U32), Bool.pick(U32, U32.is_eq(h, 99) || U32.is_eq(acc, 65536), 65536, (acc * 16 + h : U32)))
252	
253	# Four hex digits from byte j, or 65536 if one is not a hex digit.
254	def hex4.b(a: Array<U32>, +len: U32, +j: U32) -> Array<U32> & U32:
255	  hex4.b.go(4n, pk(a, len, j), len, j, 0)
256	
257	def cont(+b: U32) -> Bool:
258	  U32.is_eq((b .&. 192 : U32), 128)
259	
260	# RFC 3629 §4: overlong forms, surrogates, and code points past U+10FFFF are invalid, width 0.
261	def utf8.n(+b0: U32, +b1: U32, +b2: U32, +b3: U32) -> Cp:
262	  +x1 = (b1 .&. 63 : U32)
263	  +x2 = (b2 .&. 63 : U32)
264	  +x3 = (b3 .&. 63 : U32)
265	  +c2 = (((b0 .&. 31) << 6n) .|. x1 : U32)
266	  +c3 = ((((b0 .&. 15) << 12n) .|. (x1 << 6n)) .|. x2 : U32)
267	  +c4 = (((((b0 .&. 7) << 18n) .|. (x1 << 12n)) .|. (x2 << 6n)) .|. x3 : U32)
268	  +ok2 = U32.is_le(192, b0) && U32.is_lt(b0, 224) && cont(b1) && U32.is_le(128, c2)
269	  +ok3 = U32.is_le(224, b0) && U32.is_lt(b0, 240) && cont(b1) && cont(b2) && U32.is_le(2048, c3) && (U32.is_lt(c3, 55296) || U32.is_lt(57343, c3))
270	  +ok4 = U32.is_le(240, b0) && U32.is_lt(b0, 248) && cont(b1) && cont(b2) && cont(b3) && U32.is_le(65536, c4) && U32.is_le(c4, 1114111)
271	  Bool.pick(Cp, ok2, Cp{c2, 2}, Bool.pick(Cp, ok3, Cp{c3, 3}, Bool.pick(Cp, ok4, Cp{c4, 4}, Cp{0, 0})))
272	
273	def utf8.b3(+b0: U32, +b1: U32, +b2: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
274	  (a, +b3) = r
275	  (a, utf8.n(b0, b1, b2, b3))
276	
277	def utf8.b2(+len: U32, +i: U32, +b0: U32, +b1: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
278	  (a, +b2) = r
279	  utf8.b3(b0, b1, b2, pk(a, len, (i + 3 : U32)))
280	
281	def utf8.b1(+len: U32, +i: U32, +b0: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
282	  (a, +b1) = r
283	  utf8.b2(len, i, b0, b1, pk(a, len, (i + 2 : U32)))
284	
285	# The code point whose lead byte b0 is at i.
286	def utf8.at(a: Array<U32>, +len: U32, +i: U32, +b0: U32) -> Array<U32> & Cp:
287	  utf8.b1(len, i, b0, pk(a, len, (i + 1 : U32)))
288	
289	def slice.of(+n: U32, r: Array<U32> & Array<U32>) -> Array<U32> & Bytes.Bytes:
290	  (a, out) = r
291	  (a, Bytes.Bytes{n, out})
292	
293	# The n bytes from start, copied.
294	def slice(+n: U32, +start: U32, a: Array<U32>) -> Array<U32> & Bytes.Bytes:
295	  slice.of(n, Bytes.copy(n, a, Bytes.alloc(n), start, 0))
296	
297	def str.b.done(key: Bool, s: Bytes.Bytes, +i: U32, stack: List<&1, Open>) -> Sb:
298	  match key:
299	    case True{}:
300	      BColon{s, i, stack}
301	    case False{}:
302	      BAfter{Str{s}, i, stack}
303	
304	def esc.b.lone(strict: Bool, +i: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Sb:
305	  match strict:
306	    case True{}:
307	      BFail{}
308	    case False{}:
309	      BEsc{(i + 6 : U32), w.cp(65533, acc), key, stack}
310	
311	def esc.b.lo.if(ok: Bool, strict: Bool, +i: U32, +hi: U32, +lo: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Sb:
312	  match ok:
313	    case True{}:
314	      BEsc{(i + 12 : U32), w.cp((65536 + (hi - 55296 : U32) * 1024 + (lo - 56320 : U32) : U32), acc), key, stack}
315	    case False{}:
316	      esc.b.lone(strict, i, acc, key, stack)
317	
318	def esc.b.lo(strict: Bool, +i: U32, +hi: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & U32) -> Array<U32> & Sb:
319	  (a, +lo) = r
320	  (a, esc.b.lo.if(is_lo(lo), strict, i, hi, lo, acc, key, stack))
321	
322	# A high surrogate must pair in strict mode; RFC §8.2 mode replaces a lone one.
323	def esc.b.pair(+strict: Bool, +len: U32, +i: U32, +hi: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & Bool) -> Array<U32> & Sb:
324	  (a, ok) = r
325	  match ok:
326	    case True{}:
327	      esc.b.lo(strict, i, hi, acc, key, stack, hex4.b(a, len, (i + 8 : U32)))
328	    case False{}:
329	      (a, esc.b.lone(strict, i, acc, key, stack))
330	
331	# 0: not four hex digits; 1: high surrogate; 2: low surrogate; 3: other.
332	def u.class(+v: U32) -> U32:
333	  Bool.pick(U32, U32.is_eq(v, 65536), 0, Bool.pick(U32, is_hi(v), 1, Bool.pick(U32, is_lo(v), 2, 3)))
334	
335	def esc.b.u.of(+k: U32, strict: Bool, a: Array<U32>, +len: U32, +i: U32, +v: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Array<U32> & Sb:
336	  match k:
337	    case 0:
338	      (a, BFail{})
339	    case 1:
340	      esc.b.pair(strict, len, i, v, acc, key, stack, word(a, len, "\\u", (i + 6 : U32)))
341	    case 2:
342	      (a, esc.b.lone(strict, i, acc, key, stack))
343	    case _:
344	      (a, BEsc{(i + 6 : U32), w.cp(v, acc), key, stack})
345	
346	def esc.b.u(strict: Bool, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & U32) -> Array<U32> & Sb:
347	  (a, +v) = r
348	  esc.b.u.of(u.class(v), strict, a, len, i, v, acc, key, stack)
349	
350	# The escape whose backslash is at i.
351	def esc.b.one(strict: Bool, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & U32) -> Array<U32> & Sb:
352	  (a, +e) = r
353	  match e:
354	    case 117:
355	      esc.b.u(strict, len, i, acc, key, stack, hex4.b(a, len, (i + 2 : U32)))
356	    case _:
357	      +v = esc.simple(e)
358	      (a, Bool.pick(Sb, U32.is_eq(v, 99), BFail{}, BEsc{(i + 2 : U32), w.put(acc, v), key, stack}))
359	
360	def esc.b.cp(acc: W, key: Bool, stack: List<&1, Open>, +i: U32, r: Array<U32> & Cp) -> Array<U32> & Sb:
361	  (a, Cp{+c, +n}) = r
362	  (a, Bool.pick(Sb, U32.is_eq(n, 0), BFail{}, BEsc{(i + n : U32), w.cp(c, acc), key, stack}))
363	
364	# §7: unescaped chars below U+0020 are not allowed in a string.
365	def esc.b.other(ascii: Bool, +c: U32, a: Array<U32>, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Array<U32> & Sb:
366	  match ascii:
367	    case True{}:
368	      (a, Bool.pick(Sb, U32.is_lt(c, 32), BFail{}, BEsc{(i + 1 : U32), w.put(acc, c), key, stack}))
369	    case False{}:
370	      esc.b.cp(acc, key, stack, i, utf8.at(a, len, i, c))
371	
372	# A string after its first escape.
373	def esc.b(strict: Bool, r: Array<U32> & U32, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Array<U32> & Sb:
374	  (a, +c) = r
375	  match c:
376	    case 34:
377	      (a, str.b.done(key, w.done(acc), (i + 1 : U32), stack))
378	    case 92:
379	      esc.b.one(strict, len, i, acc, key, stack, pk(a, len, (i + 1 : U32)))
380	    case 256:
381	      (a, BFail{})
382	    case _:
383	      esc.b.other(U32.is_lt(c, 128), c, a, len, i, acc, key, stack)
384	
385	def str.b.close(key: Bool, +i: U32, stack: List<&1, Open>, r: Array<U32> & Bytes.Bytes) -> Array<U32> & Sb:
386	  (a, s) = r
387	  (a, str.b.done(key, s, (i + 1 : U32), stack))
388	
389	def str.b.esc(strict: Bool, +len: U32, +i: U32, key: Bool, stack: List<&1, Open>, r: Array<U32> & Bytes.Bytes) -> Array<U32> & Sb:
390	  (a, s) = r
391	  esc.b.one(strict, len, i, w.of(s), key, stack, pk(a, len, (i + 1 : U32)))
392	
393	def str.b.cp(+start: U32, key: Bool, stack: List<&1, Open>, +i: U32, r: Array<U32> & Cp) -> Array<U32> & Sb:
394	  (a, Cp{+c, +n}) = r
395	  (a, Bool.pick(Sb, U32.is_eq(n, 0), BFail{}, BStr{(i + n : U32), start, key, stack}))
396	
397	def str.b.other(ascii: Bool, +c: U32, a: Array<U32>, +len: U32, +i: U32, +start: U32, key: Bool, stack: List<&1, Open>) -> Array<U32> & Sb:
398	  match ascii:
399	    case True{}:
400	      (a, Bool.pick(Sb, U32.is_lt(c, 32), BFail{}, BStr{(i + 1 : U32), start, key, stack}))
401	    case False{}:
402	      str.b.cp(start, key, stack, i, utf8.at(a, len, i, c))
403	
404	# A string whose text so far starts at start and has no escape.
405	def str.b(strict: Bool, r: Array<U32> & U32, +len: U32, +i: U32, +start: U32, key: Bool, stack: List<&1, Open>) -> Array<U32> & Sb:
406	  (a, +c) = r
407	  match c:
408	    case 34:
409	      str.b.close(key, i, stack, slice((i - start : U32), start, a))
410	    case 92:
411	      str.b.esc(strict, len, i, key, stack, slice((i - start : U32), start, a))
412	    case 256:
413	      (a, BFail{})
414	    case _:
415	      str.b.other(U32.is_lt(c, 128), c, a, len, i, start, key, stack)
416	
417	def num.b.fin(+i: U32, stack: List<&1, Open>, r: Array<U32> & Bytes.Bytes) -> Array<U32> & Sb:
418	  (a, s) = r
419	  (a, BAfter{Num{s}, i, stack})
420	
421	def num.b.stop(ok: Bool, a: Array<U32>, +i: U32, +start: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
422	  match ok:
423	    case True{}:
424	      num.b.fin(i, stack, slice((i - start : U32), start, a))
425	    case False{}:
426	      (a, BFail{})
427	
428	def num.b.if(stop: Bool, a: Array<U32>, +i: U32, +start: U32, +st: U32, +n: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
429	  match stop:
430	    case True{}:
431	      num.b.stop(num.accepts(st), a, i, start, stack)
432	    case False{}:
433	      (a, BNum{(i + 1 : U32), start, n, stack})
434	
435	def num.b(r: Array<U32> & U32, +i: U32, +start: U32, +st: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
436	  (a, +c) = r
437	  +n = num.trans(st, c)
438	  num.b.if(U32.is_eq(n, 99), a, i, start, st, n, stack)
439	
440	def lit.b(+i: U32, +n: U32, v: Val, stack: List<&1, Open>, r: Array<U32> & Bool) -> Array<U32> & Sb:
441	  (a, ok) = r
442	  match ok:
443	    case True{}:
444	      (a, BAfter{v, (i + n : U32), stack})
445	    case False{}:
446	      (a, BFail{})
447	
448	def value.b(r: Array<U32> & U32, +len: U32, +i: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
449	  (a, +c) = r
450	  match c:
451	    case 32:
452	      (a, BValue{(i + 1 : U32), stack})
453	    case 9:
454	      (a, BValue{(i + 1 : U32), stack})
455	    case 10:
456	      (a, BValue{(i + 1 : U32), stack})
457	    case 13:
458	      (a, BValue{(i + 1 : U32), stack})
459	    case 91:
460	      (a, BFirst{(i + 1 : U32), OArr{Nil{}}, stack})
461	    case 123:
462	      (a, BFirst{(i + 1 : U32), OObj{Nil{}}, stack})
463	    case 34:
464	      (a, BStr{(i + 1 : U32), (i + 1 : U32), False{}, stack})
465	    case 116:
466	      lit.b(i, 4, Flag{True{}}, stack, word(a, len, "true", i))
467	    case 102:
468	      lit.b(i, 5, Flag{False{}}, stack, word(a, len, "false", i))
469	    case 110:
470	      lit.b(i, 4, Null{}, stack, word(a, len, "null", i))
471	    case _:
472	      (a, BNum{i, i, 0, stack})
473	
474	# After "[" or "{": the closing bracket, or the first item.
475	def first.b.end(open: Open, +c: U32, +i: U32, stack: List<&1, Open>) -> Sb:
476	  match open:
477	    case OArr{xs}:
478	      Bool.pick(Sb, U32.is_eq(c, 93), BAfter{Arr{xs}, (i + 1 : U32), stack}, BFail{})
479	    case OObj{kvs}:
480	      Bool.pick(Sb, U32.is_eq(c, 125), BAfter{Obj{kvs}, (i + 1 : U32), stack}, BFail{})
481	    case OKey{kvs, k}:
482	      BFail{}
483	
484	def first.b.open(open: Open, +i: U32, stack: List<&1, Open>) -> Sb:
485	  match open:
486	    case OArr{xs}:
487	      BValue{i, Con{OArr{xs}, stack}}
488	    case OObj{kvs}:
489	      BKey{i, Con{OObj{kvs}, stack}}
490	    case OKey{kvs, k}:
491	      BFail{}
492	
493	def first.b(r: Array<U32> & U32, +i: U32, open: Open, stack: List<&1, Open>) -> Array<U32> & Sb:
494	  (a, +c) = r
495	  match c:
496	    case 32:
497	      (a, BFirst{(i + 1 : U32), open, stack})
498	    case 9:
499	      (a, BFirst{(i + 1 : U32), open, stack})
500	    case 10:
501	      (a, BFirst{(i + 1 : U32), open, stack})
502	    case 13:
503	      (a, BFirst{(i + 1 : U32), open, stack})
504	    case 93:
505	      (a, first.b.end(open, c, i, stack))
506	    case 125:
507	      (a, first.b.end(open, c, i, stack))
508	    case _:
509	      (a, first.b.open(open, i, stack))
510	
511	def key.b(r: Array<U32> & U32, +i: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
512	  (a, +c) = r
513	  match c:
514	    case 32:
515	      (a, BKey{(i + 1 : U32), stack})
516	    case 9:
517	      (a, BKey{(i + 1 : U32), stack})
518	    case 10:
519	      (a, BKey{(i + 1 : U32), stack})
520	    case 13:
521	      (a, BKey{(i + 1 : U32), stack})
522	    case 34:
523	      (a, BStr{(i + 1 : U32), (i + 1 : U32), True{}, stack})
524	    case _:
525	      (a, BFail{})
526	
527	def colon.b.top(k: Bytes.Bytes, +i: U32, stack: List<&1, Open>) -> Sb:
528	  match stack:
529	    case Nil{}:
530	      BFail{}
531	    case Con{OArr{xs}, up}:
532	      BFail{}
533	    case Con{OObj{kvs}, up}:
534	      BValue{i, Con{OKey{kvs, k}, up}}
535	    case Con{OKey{kvs, old}, up}:
536	      BFail{}
537	
538	def colon.b(r: Array<U32> & U32, k: Bytes.Bytes, +i: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
539	  (a, +c) = r
540	  match c:
541	    case 32:
542	      (a, BColon{k, (i + 1 : U32), stack})
543	    case 9:
544	      (a, BColon{k, (i + 1 : U32), stack})
545	    case 10:
546	      (a, BColon{k, (i + 1 : U32), stack})
547	    case 13:
548	      (a, BColon{k, (i + 1 : U32), stack})
549	    case 58:
550	      (a, colon.b.top(k, (i + 1 : U32), stack))
551	    case _:
552	      (a, BFail{})
553	
554	# A finished value joins its container.
555	def after.b(v: Val, +i: U32, stack: List<&1, Open>) -> Sb:
556	  match stack:
557	    case Nil{}:
558	      BEnd{v, i}
559	    case Con{OArr{xs}, up}:
560	      BSep{i, OArr{Con{v, xs}}, up}
561	    case Con{OObj{kvs}, up}:
562	      BFail{}
563	    case Con{OKey{kvs, k}, up}:
564	      BSep{i, OObj{Con{(k, v), kvs}}, up}
565	
566	def sep.b.comma(open: Open, +i: U32, up: List<&1, Open>) -> Sb:
567	  match open:
568	    case OArr{xs}:
569	      BValue{i, Con{OArr{xs}, up}}
570	    case OObj{kvs}:
571	      BKey{i, Con{OObj{kvs}, up}}
572	    case OKey{kvs, k}:
573	      BFail{}
574	
575	def sep.b.close(open: Open, +c: U32, +i: U32, up: List<&1, Open>) -> Sb:
576	  match open:
577	    case OArr{xs}:
578	      Bool.pick(Sb, U32.is_eq(c, 93), BAfter{Arr{List.reverse(&1, Val, xs)}, i, up}, BFail{})
579	    case OObj{kvs}:
580	      Bool.pick(Sb, U32.is_eq(c, 125), BAfter{Obj{List.reverse(&1, Bytes.Bytes & Val, kvs)}, i, up}, BFail{})
581	    case OKey{kvs, k}:
582	      BFail{}
583	
584	# After an item: "," or the closing bracket.
585	def sep.b(r: Array<U32> & U32, +i: U32, open: Open, up: List<&1, Open>) -> Array<U32> & Sb:
586	  (a, +c) = r
587	  match c:
588	    case 32:
589	      (a, BSep{(i + 1 : U32), open, up})
590	    case 9:
591	      (a, BSep{(i + 1 : U32), open, up})
592	    case 10:
593	      (a, BSep{(i + 1 : U32), open, up})
594	    case 13:
595	      (a, BSep{(i + 1 : U32), open, up})
596	    case 44:
597	      (a, sep.b.comma(open, (i + 1 : U32), up))
598	    case _:
599	      (a, sep.b.close(open, c, (i + 1 : U32), up))
600	
601	def end.b(r: Array<U32> & U32, v: Val, +i: U32) -> Array<U32> & Sb:
602	  (a, +c) = r
603	  match c:
604	    case 32:
605	      (a, BEnd{v, (i + 1 : U32)})
606	    case 9:
607	      (a, BEnd{v, (i + 1 : U32)})
608	    case 10:
609	      (a, BEnd{v, (i + 1 : U32)})
610	    case 13:
611	      (a, BEnd{v, (i + 1 : U32)})
612	    case 256:
613	      (a, BOk{v})
614	    case _:
615	      (a, BFail{})
616	
617	# A run's end (a, i, c) to each step. The parts bind without + (bendlang/bend#1077).
618	def value.r(+len: U32, stack: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb:
619	  (a, i, c) = r
620	  value.b((a, c), len, i, stack)
621	
622	def level.r(depth: U32, r: Array<U32> & Sb) -> Array<U32> & Sb & U32:
623	  (a, sb) = r
624	  (a, sb, depth)
625	
626	def first.at(a: Array<U32>, +c: U32, i: U32, +depth: U32, open: Open, stack: List<&1, Open>) -> Array<U32> & Sb & U32:
627	  level.r(Bool.pick(U32, U32.is_eq(c, 93) || U32.is_eq(c, 125), depth, (depth + 1 : U32)), first.b((a, c), i, open, stack))
628	
629	def first.r(ok: Bool, +depth: U32, open: Open, stack: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb & U32:
630	  match ok:
631	    case False{}:
632	      (a, i, c) = r
633	      (a, BFail{}, depth)
634	    case True{}:
635	      (a, i, c) = r
636	      first.at(a, c, i, depth, open, stack)
637	
638	def first.limit(cap: U32, +depth: U32, open: Open, stack: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb & U32:
639	  first.r(U32.is_lt(depth, cap), depth, open, stack, r)
640	
641	def key.r(stack: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb:
642	  (a, i, c) = r
643	  key.b((a, c), i, stack)
644	
645	def colon.r(k: Bytes.Bytes, stack: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb:
646	  (a, i, c) = r
647	  colon.b((a, c), k, i, stack)
648	
649	def str.r(strict: Bool, +len: U32, +s: U32, key: Bool, stack: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb:
650	  (a, i, c) = r
651	  str.b(strict, (a, c), len, i, s, key, stack)
652	
653	def num.r(+s: U32, +st: U32, stack: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb:
654	  (a, i, c) = r
655	  num.b((a, c), i, s, st, stack)
656	
657	def sep.at(a: Array<U32>, +c: U32, i: U32, +depth: U32, open: Open, up: List<&1, Open>) -> Array<U32> & Sb & U32:
658	  level.r(Bool.pick(U32, U32.is_eq(c, 93) || U32.is_eq(c, 125), (depth - 1 : U32), depth), sep.b((a, c), i, open, up))
659	
660	def sep.r(+depth: U32, open: Open, up: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb & U32:
661	  (a, i, c) = r
662	  sep.at(a, c, i, depth, open, up)
663	
664	def end.r(v: Val, r: Array<U32> & U32 & U32) -> Array<U32> & Sb:
665	  (a, i, c) = r
666	  end.b((a, c), v, i)
667	
668	def w.span.go(n: Nat, r: Array<U32> & U32, +i: U32, o: W) -> Array<U32> & W:
669	  match n:
670	    case 0n:
671	      (a, v) = r
672	      (a, o)
673	    case 1n+k:
674	      (a, +c) = r
675	      w.span.go(k, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), w.put(o, c))
676	
677	def esc.r.go(strict: Bool, +len: U32, +j: U32, c: U32, key: Bool, stack: List<&1, Open>, r: Array<U32> & W) -> Array<U32> & Sb:
678	  (a, acc) = r
679	  esc.b(strict, (a, c), len, j, acc, key, stack)
680	
681	# The plain bytes from i to the run's end go onto acc in one loop.
682	def esc.r(strict: Bool, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & U32 & U32) -> Array<U32> & Sb:
683	  (a, +j, c) = r
684	  esc.r.go(strict, len, j, c, key, stack, w.span.go(U32.to_nat((j - i : U32)), Bytes.peek(a, i), i, acc))
685	
686	# States 3, 5 and 8 take digits until the number's part ends.
687	def num.run(loop: Bool, +g: Nat, a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & U32 & U32:
688	  match loop:
689	    case True{}:
690	      run(~digit, g, a, len, i)
691	    case False{}:
692	      pos(a, len, i)
693	
694	# fuel: a step eats a byte, or ends a number, a value, or an opening bracket, so 4 * len + 4 steps are enough.
695	def runb(+fuel: Nat, r: Array<U32> & Sb & U32, +len: U32, +strict: Bool, +cap: U32) -> Maybe<&1, Val>:
696	  match fuel:
697	    case 0n:
698	      None{}
699	    case 1n+f:
700	      (a, sb, depth) = r
701	      match sb:
702	        case BOk{v}:
703	          Some{v}
704	        case BFail{}:
705	          None{}
706	        case BValue{+i, stack}:
707	          runb(f, level.r(depth, value.r(len, stack, run(~is_ws, f, a, len, i))), len, strict, cap)
708	        case BFirst{+i, open, stack}:
709	          runb(f, first.limit(cap, depth, open, stack, run(~is_ws, f, a, len, i)), len, strict, cap)
710	        case BKey{+i, stack}:
711	          runb(f, level.r(depth, key.r(stack, run(~is_ws, f, a, len, i))), len, strict, cap)
712	        case BColon{k, +i, stack}:
713	          runb(f, level.r(depth, colon.r(k, stack, run(~is_ws, f, a, len, i))), len, strict, cap)
714	        case BStr{+i, +s, k, stack}:
715	          runb(f, level.r(depth, str.r(strict, len, s, k, stack, run(~plain, f, a, len, i))), len, strict, cap)
716	        case BEsc{+i, acc, k, stack}:
717	          runb(f, level.r(depth, esc.r(strict, len, i, acc, k, stack, run(~plain, f, a, len, i))), len, strict, cap)
718	        case BNum{+i, +s, +st, stack}:
719	          runb(f, level.r(depth, num.r(s, st, stack, num.run(U32.is_eq(st, 3) || U32.is_eq(st, 5) || U32.is_eq(st, 8), f, a, len, i))), len, strict, cap)
720	        case BAfter{v, +i, stack}:
721	          runb(f, (a, after.b(v, i, stack), depth), len, strict, cap)
722	        case BSep{+i, open, stack}:
723	          runb(f, sep.r(depth, open, stack, run(~is_ws, f, a, len, i)), len, strict, cap)
724	        case BEnd{v, +i}:
725	          runb(f, level.r(depth, end.r(v, run(~is_ws, f, a, len, i))), len, strict, cap)
726	
727	# One JSON text in UTF-8, with RFC §8.2 surrogate replacement and input-sized depth.
728	def parse.bytes(b: Bytes.Bytes) -> Maybe<&1, Val>:
729	  Bytes.Bytes{+len, buf} = b
730	  runb(Nat.add(Nat.mul(U32.to_nat(len), 4n), 4n), (buf, BValue{0, Nil{}}, 0), len, False{}, len)
731	
732	# Strict UTF-8 JSON: reject lone surrogate escapes and more than cap nested
733	# arrays/objects, including empty containers. Scalars have depth zero.
734	# The limit is checked at each opening, before any contents are parsed.
735	def parse.strict.bytes(b: Bytes.Bytes, cap: U32) -> Maybe<&1, Val>:
736	  Bytes.Bytes{+len, buf} = b
737	  runb(Nat.add(Nat.mul(U32.to_nat(len), 4n), 4n), (buf, BValue{0, Nil{}}, 0), len, True{}, cap)
738	
739	# Unique object keys
740	# ------------------
741	# Key equality uses the decoded UTF-8 bytes. Each object's keys become
742	# fingerprints that are sorted and compared with their neighbours, so an object
743	# of n keys costs O(n log n) comparisons. The value keeps its field order.
744	
745	# Reads from the last word down and prepends, so acc ends in index order.
746	def unique.print.go(n: Nat, r: Array<U32> & U32, +i: U32, acc: List<&2, U32>) -> Array<U32> & List<&2, U32>:
747	  match n:
748	    case 0n:
749	      (a, w) = r
750	      (a, acc)
751	    case 1n+p:
752	      (a, w) = r
753	      unique.print.go(p, Array.get(U32, a, (i - 1 : U32)), (i - 1 : U32), w <> acc)
754	
755	def unique.print.fin(+len: U32, r: Array<U32> & List<&2, U32>) -> Bytes.Bytes & List<&2, U32>:
756	  (a, ws) = r
757	  (Bytes.Bytes{len, a}, len <> ws)
758	
759	# The key back, and its fingerprint: the length, then its words. Bytes past the
760	# length are 0, so two keys are equal exactly when their fingerprints are.
761	def unique.print(k: Bytes.Bytes) -> Bytes.Bytes & List<&2, U32>:
762	  Bytes.Bytes{+len, buf} = k
763	  +n = Bytes.words(len)
764	  +i = (n - 1 : U32)
765	  unique.print.fin(len, unique.print.go(U32.to_nat(n), Array.get(U32, buf, i), i, Nil{}))
766	
767	# Lexicographic order on fingerprints.
768	def unique.le(a: List<&2, U32>, b: List<&2, U32>) -> Bool:
769	  match a b:
770	    case Nil{} Nil{}:
771	      True{}
772	    case Nil{} y <> yt:
773	      True{}
774	    case x <> xt Nil{}:
775	      False{}
776	    case +x <> xt +y <> yt:
777	      Bool.or(U32.is_lt(x, y), Bool.and(U32.is_eq(x, y), unique.le(xt, yt)))
778	
779	# xs is sorted and prev <= each of xs, so prev equals x when x <= prev.
780	def unique.distinct(xs: List<&2, List<&2, U32>>, +prev: List<&2, U32>) -> Bool:
781	  match xs:
782	    case Nil{}:
783	      True{}
784	    case +x <> t:
785	      Bool.and(Bool.not(unique.le(x, prev)), unique.distinct(t, x))
786	
787	def unique.sorted(xs: List<&2, List<&2, U32>>) -> Bool:
788	  match xs:
789	    case Nil{}:
790	      True{}
791	    case +x <> t:
792	      unique.distinct(t, x)
793	
794	# Whether one object's fingerprints are pairwise distinct.
795	def unique.check(keys: List<&2, List<&2, U32>>) -> Bool:
796	  unique.sorted(List.sort(~List<&2, U32>, ~unique.le, keys))
797	
798	def unique.array.tail(tail: Val, head: Val, ok: Bool) -> Val & Bool & List<&2, List<&2, U32>>:
799	  match tail:
800	    case Arr{xs}:
801	      (Arr{Con{head, xs}}, ok, Nil{})
802	    case other:
803	      (other, False{}, Nil{})
804	
805	def unique.array(head_result: Val & Bool & List<&2, List<&2, U32>>, tail_result: Val & Bool & List<&2, List<&2, U32>>) -> Val & Bool & List<&2, List<&2, U32>>:
806	  (head, head_ok, head_keys) = head_result
807	  (tail, tail_ok, tail_keys) = tail_result
808	  unique.array.tail(tail, head, Bool.and(head_ok, Bool.and(tail_ok, unique.check(head_keys))))
809	
810	def unique.object.done(print: Bytes.Bytes & List<&2, U32>, head: Val, kvs: List<&1, Bytes.Bytes & Val>, ok: Bool, keys: List<&2, List<&2, U32>>) -> Val & Bool & List<&2, List<&2, U32>>:
811	  (key, fp) = print
812	  (Obj{Con{(key, head), kvs}}, ok, fp <> keys)
813	
814	def unique.object.tail(tail: Val, key: Bytes.Bytes, head: Val, ok: Bool, keys: List<&2, List<&2, U32>>) -> Val & Bool & List<&2, List<&2, U32>>:
815	  match tail:
816	    case Obj{kvs}:
817	      unique.object.done(unique.print(key), head, kvs, ok, keys)
818	    case other:
819	      (other, False{}, Nil{})
820	
821	def unique.object(key: Bytes.Bytes, head_result: Val & Bool & List<&2, List<&2, U32>>, tail_result: Val & Bool & List<&2, List<&2, U32>>) -> Val & Bool & List<&2, List<&2, U32>>:
822	  (head, head_ok, head_keys) = head_result
823	  (tail, tail_ok, tail_keys) = tail_result
824	  unique.object.tail(tail, key, head, Bool.and(head_ok, Bool.and(tail_ok, unique.check(head_keys))), tail_keys)
825	
826	# The value back, whether every object nested inside it has unique keys, and
827	# the fingerprints of v's own keys when v is an object. The caller that holds
828	# the whole object checks those.
829	def unique.go(v: Val) -> Val & Bool & List<&2, List<&2, U32>>:
830	  match v:
831	    case Null{}:
832	      (Null{}, True{}, Nil{})
833	    case Flag{on}:
834	      (Flag{on}, True{}, Nil{})
835	    case Num{s}:
836	      (Num{s}, True{}, Nil{})
837	    case Str{s}:
838	      (Str{s}, True{}, Nil{})
839	    case Arr{Nil{}}:
840	      (Arr{Nil{}}, True{}, Nil{})
841	    case Arr{Con{head, tail}}:
842	      unique.array(unique.go(head), unique.go(Arr{tail}))
843	    case Obj{Nil{}}:
844	      (Obj{Nil{}}, True{}, Nil{})
845	    case Obj{(key, head) <> tail}:
846	      unique.object(key, unique.go(head), unique.go(Obj{tail}))
847	
848	def unique.keys.fin(r: Val & Bool & List<&2, List<&2, U32>>) -> Val & Bool:
849	  (v, ok, keys) = r
850	  (v, Bool.and(ok, unique.check(keys)))
851	
852	# Returns the value and whether every object's decoded keys are unique.
853	# This predicate checks keys. Syntax and depth limits belong to the parser.
854	def unique.keys(v: Val) -> Val & Bool:
855	  unique.keys.fin(unique.go(v))
856	
857	def unique.answer(r: Val & Bool) -> Maybe<&1, Val>:
858	  (v, ok) = r
859	  match ok:
860	    case True{}:
861	      Some{v}
862	    case False{}:
863	      None{}
864	
865	def unique.parsed(r: Maybe<&1, Val>) -> Maybe<&1, Val>:
866	  match r:
867	    case Some{v}:
868	      unique.answer(unique.keys(v))
869	    case None{}:
870	      None{}
871	
872	# Strict UTF-8 JSON with the caller's depth cap and unique decoded object keys.
873	def parse.strict.unique.bytes(b: Bytes.Bytes, cap: U32) -> Maybe<&1, Val>:
874	  unique.parsed(parse.strict.bytes(b, cap))
875	
876	# Access
877	# ------
878	
879	def get.pick(v: Val, found: Maybe<&1, Val>, r: Bytes.Bytes & Bytes.Bytes & Bool) -> Bytes.Bytes & Maybe<&1, Val>:
880	  (k, key, same) = r
881	  (key, Bool.pick(Maybe<&1, Val>, same, Some{v}, found))
882	
883	def get.step(k: Bytes.Bytes, v: Val, st: Bytes.Bytes & Maybe<&1, Val>) -> Bytes.Bytes & Maybe<&1, Val>:
884	  (key, found) = st
885	  get.pick(v, found, Bytes.eq(k, key))
886	
887	def get.go(kvs: List<&1, Bytes.Bytes & Val>, st: Bytes.Bytes & Maybe<&1, Val>) -> Maybe<&1, Val>:
888	  match kvs:
889	    case Nil{}:
890	      (key, found) = st
891	      found
892	    case (k, v) <> t:
893	      get.go(t, get.step(k, v, st))
894	
895	# §4: the value under key k of an object; the last one when k repeats, as most parsers do.
896	def get(v: Val, k: String) -> Maybe<&1, Val>:
897	  match v:
898	    case Obj{kvs}:
899	      get.go(kvs, (utf8(k), None{}))
900	    case Null{}:
901	      None{}
902	    case Flag{on}:
903	      None{}
904	    case Num{n}:
905	      None{}
906	    case Str{s}:
907	      None{}
908	    case Arr{xs}:
909	      None{}
910	
911	def at.go(xs: List<&1, Val>, n: Nat) -> Maybe<&1, Val>:
912	  match xs:
913	    case Nil{}:
914	      None{}
915	    case Con{v, t}:
916	      match n:
917	        case 0n:
918	          Some{v}
919	        case 1n+p:
920	          at.go(t, p)
921	
922	# Item n of an array.
923	def at(v: Val, n: Nat) -> Maybe<&1, Val>:
924	  match v:
925	    case Arr{xs}:
926	      at.go(xs, n)
927	    case Null{}:
928	      None{}
929	    case Flag{on}:
930	      None{}
931	    case Num{s}:
932	      None{}
933	    case Str{s}:
934	      None{}
935	    case Obj{kvs}:
936	      None{}
937	
938	def u32.over(+acc: U32, +c: U32) -> Bool:
939	  Bool.or(U32.is_lt(429496729, acc), Bool.and(U32.is_eq(acc, 429496729), U32.is_lt(53, c)))
940	
941	def u32.dig(s: String, +acc: U32, bad: Bool) -> Maybe<&2, U32>:
942	  match s:
943	    case SNil{}:
944	      match bad:
945	        case True{}:
946	          None{}
947	        case False{}:
948	          Some{acc}
949	    case SCon{Chr{+c}, t}:
950	      u32.dig(t, (acc * 10 + (c - 48 : U32) : U32), Bool.or(bad, Bool.or(Bool.not(digit(c)), u32.over(acc, c))))
951	
952	def u32.zero(t: String) -> Maybe<&2, U32>:
953	  match t:
954	    case SNil{}:
955	      Some{0}
956	    case SCon{d, u}:
957	      None{}
958	
959	def u32.lead(+c: U32, t: String, zero: Bool) -> Maybe<&2, U32>:
960	  match zero:
961	    case True{}:
962	      u32.zero(t)
963	    case False{}:
964	      u32.dig(t, (c - 48 : U32), Bool.or(Bool.not(digit(c)), u32.over(0, c)))
965	
966	def u32.num(s: String) -> Maybe<&2, U32>:
967	  match s:
968	    case SNil{}:
969	      None{}
970	    case SCon{Chr{+c}, t}:
971	      u32.lead(c, t, U32.is_eq(c, 48))
972	
973	# A number that is a whole U32, with no sign, fraction or exponent.
974	def u32(v: Val) -> Maybe<&2, U32>:
975	  match v:
976	    case Num{s}:
977	      u32.num(Bytes.to_string(s))
978	    case Null{}:
979	      None{}
980	    case Flag{on}:
981	      None{}
982	    case Str{s}:
983	      None{}
984	    case Arr{xs}:
985	      None{}
986	    case Obj{kvs}:
987	      None{}
988	
989	# Encode
990	# ------
991	
992	def w.ctl(ctl: Bool, +c: U32, o: W) -> W:
993	  match ctl:
994	    case True{}:
995	      w.put(w.put(w.put(w.put(w.put(w.put(o, 92), 117), 48), 48), w.hex(U32.shrn(c, 4n))), w.hex((c .&. 15 : U32)))
996	    case False{}:
997	      w.put(o, c)
998	
999	# §7: quote, backslash and control chars are escaped. Other bytes are already UTF-8.
1000	def w.esc.c(+c: U32, o: W) -> W:
1001	  match c:
1002	    case 34:
1003	      w.put(w.put(o, 92), 34)
1004	    case 92:
1005	      w.put(w.put(o, 92), 92)
1006	    case 10:
1007	      w.put(w.put(o, 92), 110)
1008	    case 13:
1009	      w.put(w.put(o, 92), 114)
1010	    case 9:
1011	      w.put(w.put(o, 92), 116)
1012	    case _:
1013	      w.ctl(U32.is_lt(c, 32), c, o)
1014	
1015	def w.bytes.go(n: Nat, r: Array<U32> & U32, +i: U32, o: W) -> W:
1016	  match n:
1017	    case 0n:
1018	      o
1019	    case 1n+k:
1020	      (a, +c) = r
1021	      w.bytes.go(k, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), w.put(o, c))
1022	
1023	def w.bytes(b: Bytes.Bytes, o: W) -> W:
1024	  Bytes.Bytes{+len, buf} = b
1025	  w.bytes.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, o)
1026	
1027	def w.str.go(n: Nat, r: Array<U32> & U32, +i: U32, o: W) -> W:
1028	  match n:
1029	    case 0n:
1030	      w.put(o, 34)
1031	    case 1n+k:
1032	      (a, +c) = r
1033	      w.str.go(k, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), w.esc.c(c, o))
1034	
1035	# A quoted, escaped string.
1036	def w.str(b: Bytes.Bytes, o: W) -> W:
1037	  Bytes.Bytes{+len, buf} = b
1038	  w.str.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, w.put(o, 34))
1039	
1040	# open: the container's first byte comes next; else a comma or its last byte.
1041	def w.lead(open: Bool, +c: U32, o: W) -> W:
1042	  match open:
1043	    case True{}:
1044	      w.put(o, c)
1045	    case False{}:
1046	      w.put(o, 44)
1047	
1048	def w.close(open: Bool, +a: U32, +z: U32, o: W) -> W:
1049	  match open:
1050	    case True{}:
1051	      w.put(w.put(o, a), z)
1052	    case False{}:
1053	      w.put(o, z)
1054	
1055	def encb.go(v: Val, open: Bool, o: W) -> W:
1056	  match v:
1057	    case Null{}:
1058	      w.text("null", o)
1059	    case Flag{on}:
1060	      match on:
1061	        case True{}:
1062	          w.text("true", o)
1063	        case False{}:
1064	          w.text("false", o)
1065	    case Num{n}:
1066	      w.bytes(n, o)
1067	    case Str{s}:
1068	      w.str(s, o)
1069	    case Arr{xs}:
1070	      match xs:
1071	        case Nil{}:
1072	          w.close(open, 91, 93, o)
1073	        case Con{x, t}:
1074	          encb.go(Arr{t}, False{}, encb.go(x, True{}, w.lead(open, 91, o)))
1075	    case Obj{kvs}:
1076	      match kvs:
1077	        case Nil{}:
1078	          w.close(open, 123, 125, o)
1079	        case (k, x) <> t:
1080	          encb.go(Obj{t}, False{}, encb.go(x, True{}, w.put(w.str(k, w.lead(open, 123, o)), 58)))
1081	
1082	# Compact JSON in UTF-8, with object fields in their order.
1083	def encode.bytes(v: Val) -> Bytes.Bytes:
1084	  w.done(encb.go(v, True{}, W{Bytes.alloc(64), 16, 0, 0}))