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