json.bend
bend-kit-json@0.5.0.0 · 829 lines · 0 definitions
1# JSON values, parsed and encoded as RFC 8259. Source: https://github.com/paymog/bend-kit/tree/main/json
2import Base
3import bend-kit-bytes@0.3.0.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. Nesting has no depth limit other than input size: the parser
7# keeps its own stack, since a Bend def cannot call itself through another def.
8# import ./json/json.bend as Json
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.
12type 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.
22type 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.
31type 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.
35def 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
42def 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
51def 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
55def 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.
63def 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
72def w.cont(+c: U32, +k: Nat) -> U32:
73 (128 + (U32.shrn(c, k) .&. 63) : U32)
74
75def 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.
87def 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
90def w.hex(+n: U32) -> U32:
91 Bool.pick(U32, U32.is_lt(n, 10), (48 + n : U32), (87 + n : U32))
92
93def w.new() -> W:
94 W{Bytes.alloc(0), 1, 0, 0}
95
96def 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.
102def 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
106def 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.
114def 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
123def digit(+c: U32) -> Bool:
124 Bool.and(U32.is_le(48, c), U32.is_le(c, 57))
125
126def 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
139def 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
145def 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
148def is_hi(+v: U32) -> Bool:
149 Bool.and(U32.is_le(55296, v), U32.is_le(v, 56319))
150
151def is_lo(+v: U32) -> Bool:
152 Bool.and(U32.is_le(56320, v), U32.is_le(v, 57343))
153
154def 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
165type 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
179type Cp is Data:
180 Cp{c: U32, w: U32}
181
182def 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.
190def pk(a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & U32:
191 pk.if(U32.is_lt(i, len), a, i)
192
193def word.go(w: String, ok: Bool, r: Array<U32> & U32, +len: U32, +j: U32) -> Array<U32> & Bool:
194 match w:
195 case SNil{}:
196 (a, b) = r
197 (a, ok)
198 case SCon{Chr{+c}, t}:
199 (a, +b) = r
200 word.go(t, ok && U32.is_eq(b, c), pk(a, len, (j + 1 : U32)), len, (j + 1 : U32))
201
202# Do the bytes from j spell w?
203def word(a: Array<U32>, +len: U32, w: String, +j: U32) -> Array<U32> & Bool:
204 word.go(w, True{}, pk(a, len, j), len, j)
205
206def hex4.b.go(n: Nat, r: Array<U32> & U32, +len: U32, +j: U32, +acc: U32) -> Array<U32> & U32:
207 match n:
208 case 0n:
209 (a, b) = r
210 (a, acc)
211 case 1n+k:
212 (a, +b) = r
213 +h = hexd(b)
214 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)))
215
216# Four hex digits from byte j, or 65536 if one is not a hex digit.
217def hex4.b(a: Array<U32>, +len: U32, +j: U32) -> Array<U32> & U32:
218 hex4.b.go(4n, pk(a, len, j), len, j, 0)
219
220def cont(+b: U32) -> Bool:
221 U32.is_eq((b .&. 192 : U32), 128)
222
223# RFC 3629 §4: overlong forms, surrogates, and code points past U+10FFFF are invalid, width 0.
224def utf8.n(+b0: U32, +b1: U32, +b2: U32, +b3: U32) -> Cp:
225 +x1 = (b1 .&. 63 : U32)
226 +x2 = (b2 .&. 63 : U32)
227 +x3 = (b3 .&. 63 : U32)
228 +c2 = (((b0 .&. 31) << 6n) .|. x1 : U32)
229 +c3 = ((((b0 .&. 15) << 12n) .|. (x1 << 6n)) .|. x2 : U32)
230 +c4 = (((((b0 .&. 7) << 18n) .|. (x1 << 12n)) .|. (x2 << 6n)) .|. x3 : U32)
231 +ok2 = U32.is_le(192, b0) && U32.is_lt(b0, 224) && cont(b1) && U32.is_le(128, c2)
232 +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))
233 +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)
234 Bool.pick(Cp, ok2, Cp{c2, 2}, Bool.pick(Cp, ok3, Cp{c3, 3}, Bool.pick(Cp, ok4, Cp{c4, 4}, Cp{0, 0})))
235
236def utf8.b3(+b0: U32, +b1: U32, +b2: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
237 (a, +b3) = r
238 (a, utf8.n(b0, b1, b2, b3))
239
240def utf8.b2(+len: U32, +i: U32, +b0: U32, +b1: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
241 (a, +b2) = r
242 utf8.b3(b0, b1, b2, pk(a, len, (i + 3 : U32)))
243
244def utf8.b1(+len: U32, +i: U32, +b0: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
245 (a, +b1) = r
246 utf8.b2(len, i, b0, b1, pk(a, len, (i + 2 : U32)))
247
248# The code point whose lead byte b0 is at i.
249def utf8.at(a: Array<U32>, +len: U32, +i: U32, +b0: U32) -> Array<U32> & Cp:
250 utf8.b1(len, i, b0, pk(a, len, (i + 1 : U32)))
251
252def slice.of(+n: U32, r: Array<U32> & Array<U32>) -> Array<U32> & Bytes.Bytes:
253 (a, out) = r
254 (a, Bytes.Bytes{n, out})
255
256# The n bytes from start, copied.
257def slice(+n: U32, +start: U32, a: Array<U32>) -> Array<U32> & Bytes.Bytes:
258 slice.of(n, Bytes.copy(n, a, Bytes.alloc(n), start, 0))
259
260def str.b.done(key: Bool, s: Bytes.Bytes, +i: U32, stack: List<&1, Open>) -> Sb:
261 match key:
262 case True{}:
263 BColon{s, i, stack}
264 case False{}:
265 BAfter{Str{s}, i, stack}
266
267def esc.b.lo.if(ok: Bool, +i: U32, +hi: U32, +lo: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Sb:
268 match ok:
269 case True{}:
270 BEsc{(i + 12 : U32), w.cp((65536 + (hi - 55296 : U32) * 1024 + (lo - 56320 : U32) : U32), acc), key, stack}
271 case False{}:
272 BEsc{(i + 6 : U32), w.cp(65533, acc), key, stack}
273
274def esc.b.lo(+i: U32, +hi: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & U32) -> Array<U32> & Sb:
275 (a, +lo) = r
276 (a, esc.b.lo.if(is_lo(lo), i, hi, lo, acc, key, stack))
277
278# §8.2: a high surrogate pairs with a following \uDC00-\uDFFF; a lone one is U+FFFD.
279def esc.b.pair(+len: U32, +i: U32, +hi: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & Bool) -> Array<U32> & Sb:
280 (a, ok) = r
281 match ok:
282 case True{}:
283 esc.b.lo(i, hi, acc, key, stack, hex4.b(a, len, (i + 8 : U32)))
284 case False{}:
285 (a, BEsc{(i + 6 : U32), w.cp(65533, acc), key, stack})
286
287# 0: not four hex digits; 1: high surrogate; 2: low surrogate; 3: other.
288def u.class(+v: U32) -> U32:
289 Bool.pick(U32, U32.is_eq(v, 65536), 0, Bool.pick(U32, is_hi(v), 1, Bool.pick(U32, is_lo(v), 2, 3)))
290
291def esc.b.u.of(+k: U32, a: Array<U32>, +len: U32, +i: U32, +v: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Array<U32> & Sb:
292 match k:
293 case 0:
294 (a, BFail{})
295 case 1:
296 esc.b.pair(len, i, v, acc, key, stack, word(a, len, "\\u", (i + 6 : U32)))
297 case 2:
298 (a, BEsc{(i + 6 : U32), w.cp(65533, acc), key, stack})
299 case _:
300 (a, BEsc{(i + 6 : U32), w.cp(v, acc), key, stack})
301
302def esc.b.u(+len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & U32) -> Array<U32> & Sb:
303 (a, +v) = r
304 esc.b.u.of(u.class(v), a, len, i, v, acc, key, stack)
305
306# The escape whose backslash is at i.
307def esc.b.one(+len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array<U32> & U32) -> Array<U32> & Sb:
308 (a, +e) = r
309 match e:
310 case 117:
311 esc.b.u(len, i, acc, key, stack, hex4.b(a, len, (i + 2 : U32)))
312 case _:
313 +v = esc.simple(e)
314 (a, Bool.pick(Sb, U32.is_eq(v, 99), BFail{}, BEsc{(i + 2 : U32), w.put(acc, v), key, stack}))
315
316def esc.b.cp(acc: W, key: Bool, stack: List<&1, Open>, +i: U32, r: Array<U32> & Cp) -> Array<U32> & Sb:
317 (a, Cp{+c, +n}) = r
318 (a, Bool.pick(Sb, U32.is_eq(n, 0), BFail{}, BEsc{(i + n : U32), w.cp(c, acc), key, stack}))
319
320# §7: unescaped chars below U+0020 are not allowed in a string.
321def 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:
322 match ascii:
323 case True{}:
324 (a, Bool.pick(Sb, U32.is_lt(c, 32), BFail{}, BEsc{(i + 1 : U32), w.put(acc, c), key, stack}))
325 case False{}:
326 esc.b.cp(acc, key, stack, i, utf8.at(a, len, i, c))
327
328# A string after its first escape.
329def esc.b(r: Array<U32> & U32, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Array<U32> & Sb:
330 (a, +c) = r
331 match c:
332 case 34:
333 (a, str.b.done(key, w.done(acc), (i + 1 : U32), stack))
334 case 92:
335 esc.b.one(len, i, acc, key, stack, pk(a, len, (i + 1 : U32)))
336 case 256:
337 (a, BFail{})
338 case _:
339 esc.b.other(U32.is_lt(c, 128), c, a, len, i, acc, key, stack)
340
341def str.b.close(key: Bool, +i: U32, stack: List<&1, Open>, r: Array<U32> & Bytes.Bytes) -> Array<U32> & Sb:
342 (a, s) = r
343 (a, str.b.done(key, s, (i + 1 : U32), stack))
344
345def str.b.esc(+len: U32, +i: U32, key: Bool, stack: List<&1, Open>, r: Array<U32> & Bytes.Bytes) -> Array<U32> & Sb:
346 (a, s) = r
347 esc.b.one(len, i, w.of(s), key, stack, pk(a, len, (i + 1 : U32)))
348
349def str.b.cp(+start: U32, key: Bool, stack: List<&1, Open>, +i: U32, r: Array<U32> & Cp) -> Array<U32> & Sb:
350 (a, Cp{+c, +n}) = r
351 (a, Bool.pick(Sb, U32.is_eq(n, 0), BFail{}, BStr{(i + n : U32), start, key, stack}))
352
353def 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:
354 match ascii:
355 case True{}:
356 (a, Bool.pick(Sb, U32.is_lt(c, 32), BFail{}, BStr{(i + 1 : U32), start, key, stack}))
357 case False{}:
358 str.b.cp(start, key, stack, i, utf8.at(a, len, i, c))
359
360# A string whose text so far starts at start and has no escape.
361def str.b(r: Array<U32> & U32, +len: U32, +i: U32, +start: U32, key: Bool, stack: List<&1, Open>) -> Array<U32> & Sb:
362 (a, +c) = r
363 match c:
364 case 34:
365 str.b.close(key, i, stack, slice((i - start : U32), start, a))
366 case 92:
367 str.b.esc(len, i, key, stack, slice((i - start : U32), start, a))
368 case 256:
369 (a, BFail{})
370 case _:
371 str.b.other(U32.is_lt(c, 128), c, a, len, i, start, key, stack)
372
373def num.b.fin(+i: U32, stack: List<&1, Open>, r: Array<U32> & Bytes.Bytes) -> Array<U32> & Sb:
374 (a, s) = r
375 (a, BAfter{Num{s}, i, stack})
376
377def num.b.stop(ok: Bool, a: Array<U32>, +i: U32, +start: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
378 match ok:
379 case True{}:
380 num.b.fin(i, stack, slice((i - start : U32), start, a))
381 case False{}:
382 (a, BFail{})
383
384def num.b.if(stop: Bool, a: Array<U32>, +i: U32, +start: U32, +st: U32, +n: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
385 match stop:
386 case True{}:
387 num.b.stop(num.accepts(st), a, i, start, stack)
388 case False{}:
389 (a, BNum{(i + 1 : U32), start, n, stack})
390
391def num.b(r: Array<U32> & U32, +i: U32, +start: U32, +st: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
392 (a, +c) = r
393 +n = num.trans(st, c)
394 num.b.if(U32.is_eq(n, 99), a, i, start, st, n, stack)
395
396def lit.b(+i: U32, +n: U32, v: Val, stack: List<&1, Open>, r: Array<U32> & Bool) -> Array<U32> & Sb:
397 (a, ok) = r
398 match ok:
399 case True{}:
400 (a, BAfter{v, (i + n : U32), stack})
401 case False{}:
402 (a, BFail{})
403
404def value.b(r: Array<U32> & U32, +len: U32, +i: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
405 (a, +c) = r
406 match c:
407 case 32:
408 (a, BValue{(i + 1 : U32), stack})
409 case 9:
410 (a, BValue{(i + 1 : U32), stack})
411 case 10:
412 (a, BValue{(i + 1 : U32), stack})
413 case 13:
414 (a, BValue{(i + 1 : U32), stack})
415 case 91:
416 (a, BFirst{(i + 1 : U32), OArr{Nil{}}, stack})
417 case 123:
418 (a, BFirst{(i + 1 : U32), OObj{Nil{}}, stack})
419 case 34:
420 (a, BStr{(i + 1 : U32), (i + 1 : U32), False{}, stack})
421 case 116:
422 lit.b(i, 4, Flag{True{}}, stack, word(a, len, "true", i))
423 case 102:
424 lit.b(i, 5, Flag{False{}}, stack, word(a, len, "false", i))
425 case 110:
426 lit.b(i, 4, Null{}, stack, word(a, len, "null", i))
427 case _:
428 (a, BNum{i, i, 0, stack})
429
430# After "[" or "{": the closing bracket, or the first item.
431def first.b.end(open: Open, +c: U32, +i: U32, stack: List<&1, Open>) -> Sb:
432 match open:
433 case OArr{xs}:
434 Bool.pick(Sb, U32.is_eq(c, 93), BAfter{Arr{xs}, (i + 1 : U32), stack}, BFail{})
435 case OObj{kvs}:
436 Bool.pick(Sb, U32.is_eq(c, 125), BAfter{Obj{kvs}, (i + 1 : U32), stack}, BFail{})
437 case OKey{kvs, k}:
438 BFail{}
439
440def first.b.open(open: Open, +i: U32, stack: List<&1, Open>) -> Sb:
441 match open:
442 case OArr{xs}:
443 BValue{i, Con{OArr{xs}, stack}}
444 case OObj{kvs}:
445 BKey{i, Con{OObj{kvs}, stack}}
446 case OKey{kvs, k}:
447 BFail{}
448
449def first.b(r: Array<U32> & U32, +i: U32, open: Open, stack: List<&1, Open>) -> Array<U32> & Sb:
450 (a, +c) = r
451 match c:
452 case 32:
453 (a, BFirst{(i + 1 : U32), open, stack})
454 case 9:
455 (a, BFirst{(i + 1 : U32), open, stack})
456 case 10:
457 (a, BFirst{(i + 1 : U32), open, stack})
458 case 13:
459 (a, BFirst{(i + 1 : U32), open, stack})
460 case 93:
461 (a, first.b.end(open, c, i, stack))
462 case 125:
463 (a, first.b.end(open, c, i, stack))
464 case _:
465 (a, first.b.open(open, i, stack))
466
467def key.b(r: Array<U32> & U32, +i: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
468 (a, +c) = r
469 match c:
470 case 32:
471 (a, BKey{(i + 1 : U32), stack})
472 case 9:
473 (a, BKey{(i + 1 : U32), stack})
474 case 10:
475 (a, BKey{(i + 1 : U32), stack})
476 case 13:
477 (a, BKey{(i + 1 : U32), stack})
478 case 34:
479 (a, BStr{(i + 1 : U32), (i + 1 : U32), True{}, stack})
480 case _:
481 (a, BFail{})
482
483def colon.b.top(k: Bytes.Bytes, +i: U32, stack: List<&1, Open>) -> Sb:
484 match stack:
485 case Nil{}:
486 BFail{}
487 case Con{OArr{xs}, up}:
488 BFail{}
489 case Con{OObj{kvs}, up}:
490 BValue{i, Con{OKey{kvs, k}, up}}
491 case Con{OKey{kvs, old}, up}:
492 BFail{}
493
494def colon.b(r: Array<U32> & U32, k: Bytes.Bytes, +i: U32, stack: List<&1, Open>) -> Array<U32> & Sb:
495 (a, +c) = r
496 match c:
497 case 32:
498 (a, BColon{k, (i + 1 : U32), stack})
499 case 9:
500 (a, BColon{k, (i + 1 : U32), stack})
501 case 10:
502 (a, BColon{k, (i + 1 : U32), stack})
503 case 13:
504 (a, BColon{k, (i + 1 : U32), stack})
505 case 58:
506 (a, colon.b.top(k, (i + 1 : U32), stack))
507 case _:
508 (a, BFail{})
509
510# A finished value joins its container.
511def after.b(v: Val, +i: U32, stack: List<&1, Open>) -> Sb:
512 match stack:
513 case Nil{}:
514 BEnd{v, i}
515 case Con{OArr{xs}, up}:
516 BSep{i, OArr{Con{v, xs}}, up}
517 case Con{OObj{kvs}, up}:
518 BFail{}
519 case Con{OKey{kvs, k}, up}:
520 BSep{i, OObj{Con{(k, v), kvs}}, up}
521
522def sep.b.comma(open: Open, +i: U32, up: List<&1, Open>) -> Sb:
523 match open:
524 case OArr{xs}:
525 BValue{i, Con{OArr{xs}, up}}
526 case OObj{kvs}:
527 BKey{i, Con{OObj{kvs}, up}}
528 case OKey{kvs, k}:
529 BFail{}
530
531def sep.b.close(open: Open, +c: U32, +i: U32, up: List<&1, Open>) -> Sb:
532 match open:
533 case OArr{xs}:
534 Bool.pick(Sb, U32.is_eq(c, 93), BAfter{Arr{List.reverse(&1, Val, xs)}, i, up}, BFail{})
535 case OObj{kvs}:
536 Bool.pick(Sb, U32.is_eq(c, 125), BAfter{Obj{List.reverse(&1, Bytes.Bytes & Val, kvs)}, i, up}, BFail{})
537 case OKey{kvs, k}:
538 BFail{}
539
540# After an item: "," or the closing bracket.
541def sep.b(r: Array<U32> & U32, +i: U32, open: Open, up: List<&1, Open>) -> Array<U32> & Sb:
542 (a, +c) = r
543 match c:
544 case 32:
545 (a, BSep{(i + 1 : U32), open, up})
546 case 9:
547 (a, BSep{(i + 1 : U32), open, up})
548 case 10:
549 (a, BSep{(i + 1 : U32), open, up})
550 case 13:
551 (a, BSep{(i + 1 : U32), open, up})
552 case 44:
553 (a, sep.b.comma(open, (i + 1 : U32), up))
554 case _:
555 (a, sep.b.close(open, c, (i + 1 : U32), up))
556
557def end.b(r: Array<U32> & U32, v: Val, +i: U32) -> Array<U32> & Sb:
558 (a, +c) = r
559 match c:
560 case 32:
561 (a, BEnd{v, (i + 1 : U32)})
562 case 9:
563 (a, BEnd{v, (i + 1 : U32)})
564 case 10:
565 (a, BEnd{v, (i + 1 : U32)})
566 case 13:
567 (a, BEnd{v, (i + 1 : U32)})
568 case 256:
569 (a, BOk{v})
570 case _:
571 (a, BFail{})
572
573# fuel: a step eats a byte, or ends a number, a value, or an opening bracket, so 4 * len + 4 steps are enough.
574def runb(fuel: Nat, r: Array<U32> & Sb, +len: U32) -> Maybe<&1, Val>:
575 match fuel:
576 case 0n:
577 None{}
578 case 1n+f:
579 (a, sb) = r
580 match sb:
581 case BOk{v}:
582 Some{v}
583 case BFail{}:
584 None{}
585 case BValue{+i, stack}:
586 runb(f, value.b(pk(a, len, i), len, i, stack), len)
587 case BFirst{+i, open, stack}:
588 runb(f, first.b(pk(a, len, i), i, open, stack), len)
589 case BKey{+i, stack}:
590 runb(f, key.b(pk(a, len, i), i, stack), len)
591 case BColon{k, +i, stack}:
592 runb(f, colon.b(pk(a, len, i), k, i, stack), len)
593 case BStr{+i, +s, k, stack}:
594 runb(f, str.b(pk(a, len, i), len, i, s, k, stack), len)
595 case BEsc{+i, acc, k, stack}:
596 runb(f, esc.b(pk(a, len, i), len, i, acc, k, stack), len)
597 case BNum{+i, +s, +st, stack}:
598 runb(f, num.b(pk(a, len, i), i, s, st, stack), len)
599 case BAfter{v, +i, stack}:
600 runb(f, (a, after.b(v, i, stack)), len)
601 case BSep{+i, open, stack}:
602 runb(f, sep.b(pk(a, len, i), i, open, stack), len)
603 case BEnd{v, +i}:
604 runb(f, end.b(pk(a, len, i), v, i), len)
605
606# One JSON text in UTF-8. None for bad JSON or bad UTF-8 (RFC 8259 §8.1).
607def parse.bytes(b: Bytes.Bytes) -> Maybe<&1, Val>:
608 Bytes.Bytes{+len, buf} = b
609 runb(Nat.add(Nat.mul(U32.to_nat(len), 4n), 4n), (buf, BValue{0, Nil{}}), len)
610
611# Access
612# ------
613
614def get.pick(v: Val, found: Maybe<&1, Val>, r: Bytes.Bytes & Bytes.Bytes & Bool) -> Bytes.Bytes & Maybe<&1, Val>:
615 (k, key, same) = r
616 (key, Bool.pick(Maybe<&1, Val>, same, Some{v}, found))
617
618def get.step(k: Bytes.Bytes, v: Val, st: Bytes.Bytes & Maybe<&1, Val>) -> Bytes.Bytes & Maybe<&1, Val>:
619 (key, found) = st
620 get.pick(v, found, Bytes.eq(k, key))
621
622def get.go(kvs: List<&1, Bytes.Bytes & Val>, st: Bytes.Bytes & Maybe<&1, Val>) -> Maybe<&1, Val>:
623 match kvs:
624 case Nil{}:
625 (key, found) = st
626 found
627 case (k, v) <> t:
628 get.go(t, get.step(k, v, st))
629
630# §4: the value under key k of an object; the last one when k repeats, as most parsers do.
631def get(v: Val, k: String) -> Maybe<&1, Val>:
632 match v:
633 case Obj{kvs}:
634 get.go(kvs, (utf8(k), None{}))
635 case Null{}:
636 None{}
637 case Flag{on}:
638 None{}
639 case Num{n}:
640 None{}
641 case Str{s}:
642 None{}
643 case Arr{xs}:
644 None{}
645
646def at.go(xs: List<&1, Val>, n: Nat) -> Maybe<&1, Val>:
647 match xs:
648 case Nil{}:
649 None{}
650 case Con{v, t}:
651 match n:
652 case 0n:
653 Some{v}
654 case 1n+p:
655 at.go(t, p)
656
657# Item n of an array.
658def at(v: Val, n: Nat) -> Maybe<&1, Val>:
659 match v:
660 case Arr{xs}:
661 at.go(xs, n)
662 case Null{}:
663 None{}
664 case Flag{on}:
665 None{}
666 case Num{s}:
667 None{}
668 case Str{s}:
669 None{}
670 case Obj{kvs}:
671 None{}
672
673def u32.over(+acc: U32, +c: U32) -> Bool:
674 Bool.or(U32.is_lt(429496729, acc), Bool.and(U32.is_eq(acc, 429496729), U32.is_lt(53, c)))
675
676def u32.dig(s: String, +acc: U32, bad: Bool) -> Maybe<&2, U32>:
677 match s:
678 case SNil{}:
679 match bad:
680 case True{}:
681 None{}
682 case False{}:
683 Some{acc}
684 case SCon{Chr{+c}, t}:
685 u32.dig(t, (acc * 10 + (c - 48 : U32) : U32), Bool.or(bad, Bool.or(Bool.not(digit(c)), u32.over(acc, c))))
686
687def u32.zero(t: String) -> Maybe<&2, U32>:
688 match t:
689 case SNil{}:
690 Some{0}
691 case SCon{d, u}:
692 None{}
693
694def u32.lead(+c: U32, t: String, zero: Bool) -> Maybe<&2, U32>:
695 match zero:
696 case True{}:
697 u32.zero(t)
698 case False{}:
699 u32.dig(t, (c - 48 : U32), Bool.or(Bool.not(digit(c)), u32.over(0, c)))
700
701def u32.num(s: String) -> Maybe<&2, U32>:
702 match s:
703 case SNil{}:
704 None{}
705 case SCon{Chr{+c}, t}:
706 u32.lead(c, t, U32.is_eq(c, 48))
707
708# A number that is a whole U32, with no sign, fraction or exponent.
709def u32(v: Val) -> Maybe<&2, U32>:
710 match v:
711 case Num{s}:
712 u32.num(Bytes.to_string(s))
713 case Null{}:
714 None{}
715 case Flag{on}:
716 None{}
717 case Str{s}:
718 None{}
719 case Arr{xs}:
720 None{}
721 case Obj{kvs}:
722 None{}
723
724# Encode
725# ------
726
727def w.ctl(ctl: Bool, +c: U32, o: W) -> W:
728 match ctl:
729 case True{}:
730 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)))
731 case False{}:
732 w.put(o, c)
733
734# §7: quote, backslash and control chars are escaped. Other bytes are already UTF-8.
735def w.esc.c(+c: U32, o: W) -> W:
736 match c:
737 case 34:
738 w.put(w.put(o, 92), 34)
739 case 92:
740 w.put(w.put(o, 92), 92)
741 case 10:
742 w.put(w.put(o, 92), 110)
743 case 13:
744 w.put(w.put(o, 92), 114)
745 case 9:
746 w.put(w.put(o, 92), 116)
747 case _:
748 w.ctl(U32.is_lt(c, 32), c, o)
749
750def w.bytes.go(n: Nat, r: Array<U32> & U32, +i: U32, o: W) -> W:
751 match n:
752 case 0n:
753 o
754 case 1n+k:
755 (a, +c) = r
756 w.bytes.go(k, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), w.put(o, c))
757
758def w.bytes(b: Bytes.Bytes, o: W) -> W:
759 Bytes.Bytes{+len, buf} = b
760 w.bytes.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, o)
761
762def w.str.go(n: Nat, r: Array<U32> & U32, +i: U32, o: W) -> W:
763 match n:
764 case 0n:
765 w.put(o, 34)
766 case 1n+k:
767 (a, +c) = r
768 w.str.go(k, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), w.esc.c(c, o))
769
770# A quoted, escaped string.
771def w.str(b: Bytes.Bytes, o: W) -> W:
772 Bytes.Bytes{+len, buf} = b
773 w.str.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, w.put(o, 34))
774
775type Item is Type:
776 ILit{s: String}
777 IKey{k: Bytes.Bytes}
778 IVal{v: Val}
779
780def items.sep(first: Bool, tail: List<&1, Item>) -> List<&1, Item>:
781 match first:
782 case True{}:
783 tail
784 case False{}:
785 Con{ILit{","}, tail}
786
787def items.arr(xs: List<&1, Val>, first: Bool, rest: List<&1, Item>) -> List<&1, Item>:
788 match xs:
789 case Nil{}:
790 Con{ILit{"]"}, rest}
791 case Con{x, t}:
792 items.sep(first, Con{IVal{x}, items.arr(t, False{}, rest)})
793
794def items.obj(kvs: List<&1, Bytes.Bytes & Val>, first: Bool, rest: List<&1, Item>) -> List<&1, Item>:
795 match kvs:
796 case Nil{}:
797 Con{ILit{"}"}, rest}
798 case (k, v) <> t:
799 items.sep(first, Con{IKey{k}, Con{IVal{v}, items.obj(t, False{}, rest)}})
800
801# ponytail: @unsafe because it walks a work list, not the Val; each step
802# emits text or swaps a container for its strictly smaller parts.
803@unsafe
804def encb.go(items: List<&1, Item>, o: W) -> W:
805 match items:
806 case Nil{}:
807 o
808 case Con{ILit{s}, t}:
809 encb.go(t, w.text(s, o))
810 case Con{IKey{k}, t}:
811 encb.go(t, w.put(w.str(k, o), 58))
812 case Con{IVal{Null{}}, t}:
813 encb.go(t, w.text("null", o))
814 case Con{IVal{Flag{True{}}}, t}:
815 encb.go(t, w.text("true", o))
816 case Con{IVal{Flag{False{}}}, t}:
817 encb.go(t, w.text("false", o))
818 case Con{IVal{Num{n}}, t}:
819 encb.go(t, w.bytes(n, o))
820 case Con{IVal{Str{s}}, t}:
821 encb.go(t, w.str(s, o))
822 case Con{IVal{Arr{xs}}, t}:
823 encb.go(Con{ILit{"["}, items.arr(xs, True{}, t)}, o)
824 case Con{IVal{Obj{kvs}}, t}:
825 encb.go(Con{ILit{"{"}, items.obj(kvs, True{}, t)}, o)
826
827# Compact JSON in UTF-8, with object fields in their order.
828def encode.bytes(v: Val) -> Bytes.Bytes:
829 w.done(encb.go(Con{IVal{v}, Nil{}}, W{Bytes.alloc(64), 16, 0, 0}))