json.bend
bend-kit-json@0.6.0.0 · 947 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.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.
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 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.
197def 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
200def 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.
205def pos(a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & U32 & U32:
206 pos.of(i, pk(a, len, i))
207
208def 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.
213def 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.
227def 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
230def 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?
240def 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
243def 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.
254def 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
257def 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.
261def 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
273def 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
277def 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
281def 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.
286def 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
289def 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.
294def 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
297def 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
304def 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
311def 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
318def 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.
323def 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.
332def 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
335def 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
346def 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.
351def 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
360def 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.
365def 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.
373def 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
385def 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
389def 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
393def 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
397def 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.
405def 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
417def 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
421def 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
428def 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
435def 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
440def 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
448def 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.
475def 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
484def 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
493def 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
511def 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
527def 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
538def 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.
555def 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
566def 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
575def 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.
585def 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
601def 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).
618def 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
622def level.r(depth: U32, r: Array<U32> & Sb) -> Array<U32> & Sb & U32:
623 (a, sb) = r
624 (a, sb, depth)
625
626def 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
629def 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
638def 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
641def 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
645def 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
649def 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
653def 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
657def 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
660def 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
664def 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
668def 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
677def 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.
682def 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.
687def 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.
695def 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.
728def 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.
735def 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# Access
740# ------
741
742def get.pick(v: Val, found: Maybe<&1, Val>, r: Bytes.Bytes & Bytes.Bytes & Bool) -> Bytes.Bytes & Maybe<&1, Val>:
743 (k, key, same) = r
744 (key, Bool.pick(Maybe<&1, Val>, same, Some{v}, found))
745
746def get.step(k: Bytes.Bytes, v: Val, st: Bytes.Bytes & Maybe<&1, Val>) -> Bytes.Bytes & Maybe<&1, Val>:
747 (key, found) = st
748 get.pick(v, found, Bytes.eq(k, key))
749
750def get.go(kvs: List<&1, Bytes.Bytes & Val>, st: Bytes.Bytes & Maybe<&1, Val>) -> Maybe<&1, Val>:
751 match kvs:
752 case Nil{}:
753 (key, found) = st
754 found
755 case (k, v) <> t:
756 get.go(t, get.step(k, v, st))
757
758# §4: the value under key k of an object; the last one when k repeats, as most parsers do.
759def get(v: Val, k: String) -> Maybe<&1, Val>:
760 match v:
761 case Obj{kvs}:
762 get.go(kvs, (utf8(k), None{}))
763 case Null{}:
764 None{}
765 case Flag{on}:
766 None{}
767 case Num{n}:
768 None{}
769 case Str{s}:
770 None{}
771 case Arr{xs}:
772 None{}
773
774def at.go(xs: List<&1, Val>, n: Nat) -> Maybe<&1, Val>:
775 match xs:
776 case Nil{}:
777 None{}
778 case Con{v, t}:
779 match n:
780 case 0n:
781 Some{v}
782 case 1n+p:
783 at.go(t, p)
784
785# Item n of an array.
786def at(v: Val, n: Nat) -> Maybe<&1, Val>:
787 match v:
788 case Arr{xs}:
789 at.go(xs, n)
790 case Null{}:
791 None{}
792 case Flag{on}:
793 None{}
794 case Num{s}:
795 None{}
796 case Str{s}:
797 None{}
798 case Obj{kvs}:
799 None{}
800
801def u32.over(+acc: U32, +c: U32) -> Bool:
802 Bool.or(U32.is_lt(429496729, acc), Bool.and(U32.is_eq(acc, 429496729), U32.is_lt(53, c)))
803
804def u32.dig(s: String, +acc: U32, bad: Bool) -> Maybe<&2, U32>:
805 match s:
806 case SNil{}:
807 match bad:
808 case True{}:
809 None{}
810 case False{}:
811 Some{acc}
812 case SCon{Chr{+c}, t}:
813 u32.dig(t, (acc * 10 + (c - 48 : U32) : U32), Bool.or(bad, Bool.or(Bool.not(digit(c)), u32.over(acc, c))))
814
815def u32.zero(t: String) -> Maybe<&2, U32>:
816 match t:
817 case SNil{}:
818 Some{0}
819 case SCon{d, u}:
820 None{}
821
822def u32.lead(+c: U32, t: String, zero: Bool) -> Maybe<&2, U32>:
823 match zero:
824 case True{}:
825 u32.zero(t)
826 case False{}:
827 u32.dig(t, (c - 48 : U32), Bool.or(Bool.not(digit(c)), u32.over(0, c)))
828
829def u32.num(s: String) -> Maybe<&2, U32>:
830 match s:
831 case SNil{}:
832 None{}
833 case SCon{Chr{+c}, t}:
834 u32.lead(c, t, U32.is_eq(c, 48))
835
836# A number that is a whole U32, with no sign, fraction or exponent.
837def u32(v: Val) -> Maybe<&2, U32>:
838 match v:
839 case Num{s}:
840 u32.num(Bytes.to_string(s))
841 case Null{}:
842 None{}
843 case Flag{on}:
844 None{}
845 case Str{s}:
846 None{}
847 case Arr{xs}:
848 None{}
849 case Obj{kvs}:
850 None{}
851
852# Encode
853# ------
854
855def w.ctl(ctl: Bool, +c: U32, o: W) -> W:
856 match ctl:
857 case True{}:
858 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)))
859 case False{}:
860 w.put(o, c)
861
862# §7: quote, backslash and control chars are escaped. Other bytes are already UTF-8.
863def w.esc.c(+c: U32, o: W) -> W:
864 match c:
865 case 34:
866 w.put(w.put(o, 92), 34)
867 case 92:
868 w.put(w.put(o, 92), 92)
869 case 10:
870 w.put(w.put(o, 92), 110)
871 case 13:
872 w.put(w.put(o, 92), 114)
873 case 9:
874 w.put(w.put(o, 92), 116)
875 case _:
876 w.ctl(U32.is_lt(c, 32), c, o)
877
878def w.bytes.go(n: Nat, r: Array<U32> & U32, +i: U32, o: W) -> W:
879 match n:
880 case 0n:
881 o
882 case 1n+k:
883 (a, +c) = r
884 w.bytes.go(k, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), w.put(o, c))
885
886def w.bytes(b: Bytes.Bytes, o: W) -> W:
887 Bytes.Bytes{+len, buf} = b
888 w.bytes.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, o)
889
890def w.str.go(n: Nat, r: Array<U32> & U32, +i: U32, o: W) -> W:
891 match n:
892 case 0n:
893 w.put(o, 34)
894 case 1n+k:
895 (a, +c) = r
896 w.str.go(k, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), w.esc.c(c, o))
897
898# A quoted, escaped string.
899def w.str(b: Bytes.Bytes, o: W) -> W:
900 Bytes.Bytes{+len, buf} = b
901 w.str.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, w.put(o, 34))
902
903# open: the container's first byte comes next; else a comma or its last byte.
904def w.lead(open: Bool, +c: U32, o: W) -> W:
905 match open:
906 case True{}:
907 w.put(o, c)
908 case False{}:
909 w.put(o, 44)
910
911def w.close(open: Bool, +a: U32, +z: U32, o: W) -> W:
912 match open:
913 case True{}:
914 w.put(w.put(o, a), z)
915 case False{}:
916 w.put(o, z)
917
918def encb.go(v: Val, open: Bool, o: W) -> W:
919 match v:
920 case Null{}:
921 w.text("null", o)
922 case Flag{on}:
923 match on:
924 case True{}:
925 w.text("true", o)
926 case False{}:
927 w.text("false", o)
928 case Num{n}:
929 w.bytes(n, o)
930 case Str{s}:
931 w.str(s, o)
932 case Arr{xs}:
933 match xs:
934 case Nil{}:
935 w.close(open, 91, 93, o)
936 case Con{x, t}:
937 encb.go(Arr{t}, False{}, encb.go(x, True{}, w.lead(open, 91, o)))
938 case Obj{kvs}:
939 match kvs:
940 case Nil{}:
941 w.close(open, 123, 125, o)
942 case (k, x) <> t:
943 encb.go(Obj{t}, False{}, encb.go(x, True{}, w.put(w.str(k, w.lead(open, 123, o)), 58)))
944
945# Compact JSON in UTF-8, with object fields in their order.
946def encode.bytes(v: Val) -> Bytes.Bytes:
947 w.done(encb.go(v, True{}, W{Bytes.alloc(64), 16, 0, 0}))