cbor.bend
bend-kit-cbor@0.1.0.0 · 716 lines · 0 definitions
1# CBOR (RFC 8949) values encoded and decoded over Bytes. Source: https://github.com/paymog/bend-kit/tree/main/cbor
2import Base
3import bend-kit-bytes@0.3.0.0/bytes.bend as Bytes
4
5# Raw words preserve CBOR integer and floating-point bit patterns.
6type W64 is Data:
7 W64{hi: U32, lo: U32}
8
9type Float is Data:
10 Half{bits: U32}
11 Single{bits: U32}
12 Double{bits: W64}
13
14type Simple is Data:
15 SFalse{}
16 STrue{}
17 SNull{}
18 SUndefined{}
19 Other{value: U32}
20
21type Val is Type:
22 UInt{value: W64}
23 NInt{value: W64}
24 BStr{value: Bytes.Bytes}
25 TStr{value: Bytes.Bytes}
26 Arr{items: List<&1, Val>}
27 Obj{items: List<&1, Val & Val>}
28 Tag{number: W64, value: Val}
29 Sim{value: Simple}
30 Flt{value: Float}
31
32type W is Type:
33 W{buf: Array<U32>, cap: U32, n: U32, word: U32}
34def grow.if(grow: Bool, buf: Array<U32>, +k: U32) -> Array<U32>:
35 match grow:
36 case True{}:
37 Bytes.grow((k * 4 : U32), buf, (k * 8 : U32))
38 case False{}:
39 buf
40
41
42def put(full: Bool, buf: Array<U32>, +cap: U32, +n: U32, +word: U32) -> W:
43 match full:
44 case True{}:
45 +k = (n >> 2n : U32)
46 +grow = U32.is_eq(k, cap)
47 +cap2 = Bool.pick(U32, grow, (cap * 2 : U32), cap)
48 W{Array.set(U32, grow.if(grow, buf, k), k, word), cap2, (n + 1 : U32), 0}
49 case False{}:
50 W{buf, cap, (n + 1 : U32), word}
51def finish.buf(full: Bool, cap: U32, buf: Array<U32>, +k: U32, +r: U32, +word: U32) -> Array<U32>:
52 match full:
53 case True{}:
54 +grow = U32.is_eq(k, cap)
55 Bytes.flush(True{}, grow.if(grow, buf, k), k, U32.shrn(word, U32.to_nat(((4 - r) * 8 : U32))))
56 case False{}:
57 buf
58
59
60def byte(o: W, +b: U32) -> W:
61 W{buf, +cap, +n, +word} = o
62 +w = ((word >> 8n) .|. (b << 24n) : U32)
63 put(U32.is_eq((n .&. 3 : U32), 3), buf, cap, n, w)
64
65def finish(o: W) -> Bytes.Bytes:
66 W{buf, cap, +n, +word} = o
67 +r = (n .&. 3 : U32)
68 +k = (n >> 2n : U32)
69 +full = U32.is_ne(r, 0)
70 Bytes.Bytes{n, finish.buf(full, cap, buf, k, r, word)}
71def empty() -> W:
72 W{Bytes.alloc(0), 1, 0, 0}
73
74def head.small(+major: U32, +v: U32, o: W) -> W:
75 byte(o, ((major << 5n) .|. v : U32))
76
77def head.u32.sixteen(fits: Bool, +major: U32, +v: U32, o: W) -> W:
78 match fits:
79 case True{}:
80 byte(byte(byte(o, ((major << 5n) .|. 25 : U32)), (v >> 8n : U32)), v)
81 case False{}:
82 byte(byte(byte(byte(byte(o, ((major << 5n) .|. 26 : U32)), (v >> 24n : U32)), (v >> 16n : U32)), (v >> 8n : U32)), v)
83
84def head.u32.eight(fits: Bool, +major: U32, +v: U32, o: W) -> W:
85 match fits:
86 case True{}:
87 byte(byte(o, ((major << 5n) .|. 24 : U32)), v)
88 case False{}:
89 head.u32.sixteen(U32.is_le(v, 65535), major, v, o)
90
91def head.u32.small(small: Bool, +major: U32, +v: U32, o: W) -> W:
92 match small:
93 case True{}:
94 head.small(major, v, o)
95 case False{}:
96 head.u32.eight(U32.is_le(v, 255), major, v, o)
97def head.u32(+major: U32, +v: U32, o: W) -> W:
98 head.u32.small(U32.is_lt(v, 24), major, v, o)
99
100def raw.u32(o: W, +v: U32) -> W:
101 byte(byte(byte(byte(o, (v >> 24n : U32)), (v >> 16n : U32)), (v >> 8n : U32)), v)
102
103def uint.bytes.small(small: Bool, +major: U32, +hi: U32, +lo: U32, o: W) -> W:
104 match small:
105 case True{}:
106 head.u32(major, lo, o)
107 case False{}:
108 raw.u32(raw.u32(byte(o, ((major << 5n) .|. 27 : U32)), hi), lo)
109
110def uint.bytes(+major: U32, v: W64, o: W) -> W:
111 W64{+hi, +lo} = v
112 uint.bytes.small(U32.is_eq(hi, 0), major, hi, lo, o)
113
114def raw.bytes.go(n: Nat, r: Array<U32> & U32, +i: U32, o: W) -> W:
115 match n:
116 case 0n:
117 o
118 case 1n+p:
119 (a, +b) = r
120 raw.bytes.go(p, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), byte(o, b))
121
122def raw.bytes(b: Bytes.Bytes, o: W) -> W:
123 Bytes.Bytes{+len, buf} = b
124 raw.bytes.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, o)
125
126# RFC 3629 §4 validity, as in json: overlong forms, surrogates, and code points past U+10FFFF have width 0.
127type Cp is Data:
128 Cp{c: U32, w: U32}
129
130def pk.if(ok: Bool, a: Array<U32>, +i: U32) -> Array<U32> & U32:
131 match ok:
132 case True{}:
133 Bytes.peek(a, i)
134 case False{}:
135 (a, 256)
136
137# Byte i, or 256 at end, which no rule accepts.
138def pk(a: Array<U32>, +end: U32, +i: U32) -> Array<U32> & U32:
139 pk.if(U32.is_lt(i, end), a, i)
140
141def cont(+b: U32) -> Bool:
142 U32.is_eq((b .&. 192 : U32), 128)
143
144def utf8.n(+b0: U32, +b1: U32, +b2: U32, +b3: U32) -> Cp:
145 +x1 = (b1 .&. 63 : U32)
146 +x2 = (b2 .&. 63 : U32)
147 +x3 = (b3 .&. 63 : U32)
148 +c2 = (((b0 .&. 31) << 6n) .|. x1 : U32)
149 +c3 = ((((b0 .&. 15) << 12n) .|. (x1 << 6n)) .|. x2 : U32)
150 +c4 = (((((b0 .&. 7) << 18n) .|. (x1 << 12n)) .|. (x2 << 6n)) .|. x3 : U32)
151 +ok2 = U32.is_le(192, b0) && U32.is_lt(b0, 224) && cont(b1) && U32.is_le(128, c2)
152 +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))
153 +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)
154 Bool.pick(Cp, ok2, Cp{c2, 2}, Bool.pick(Cp, ok3, Cp{c3, 3}, Bool.pick(Cp, ok4, Cp{c4, 4}, Cp{0, 0})))
155
156def utf8.b3(+b0: U32, +b1: U32, +b2: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
157 (a, +b3) = r
158 (a, utf8.n(b0, b1, b2, b3))
159
160def utf8.b2(+end: U32, +i: U32, +b0: U32, +b1: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
161 (a, +b2) = r
162 utf8.b3(b0, b1, b2, pk(a, end, (i + 3 : U32)))
163
164def utf8.b1(+end: U32, +i: U32, +b0: U32, r: Array<U32> & U32) -> Array<U32> & Cp:
165 (a, +b1) = r
166 utf8.b2(end, i, b0, b1, pk(a, end, (i + 2 : U32)))
167
168def utf8.cp(+i: U32, r: Array<U32> & Cp) -> Array<U32> & U32 & Bool:
169 (a, cp) = r
170 Cp{c, +w} = cp
171 (a, (i + w : U32), U32.is_ne(w, 0))
172
173def utf8.byte(ascii: Bool, a: Array<U32>, +end: U32, +i: U32, +b: U32) -> Array<U32> & U32 & Bool:
174 match ascii:
175 case True{}:
176 (a, (i + 1 : U32), True{})
177 case False{}:
178 utf8.cp(i, utf8.b1(end, i, b, pk(a, end, (i + 1 : U32))))
179
180def utf8.lead(+end: U32, +i: U32, r: Array<U32> & U32) -> Array<U32> & U32 & Bool:
181 (a, +b) = r
182 utf8.byte(U32.is_lt(b, 128), a, end, i, b)
183
184def utf8.more(go: Bool, a: Array<U32>, +end: U32, +i: U32) -> Array<U32> & U32 & Bool:
185 match go:
186 case True{}:
187 utf8.lead(end, i, Bytes.peek(a, i))
188 case False{}:
189 (a, i, True{})
190
191def utf8.step(ok: Bool, a: Array<U32>, +end: U32, +i: U32) -> Array<U32> & U32 & Bool:
192 match ok:
193 case True{}:
194 utf8.more(U32.is_lt(i, end), a, end, i)
195 case False{}:
196 (a, i, False{})
197
198# Each step eats a whole code point, so end - i steps reach end.
199def utf8.go(n: Nat, r: Array<U32> & U32 & Bool, +end: U32) -> Array<U32> & Bool:
200 match n:
201 case 0n:
202 (a, i, ok) = r
203 (a, ok)
204 case 1n+p:
205 (a, +i, ok) = r
206 utf8.go(p, utf8.step(ok, a, end, i), end)
207
208# Are bytes i until end well-formed UTF-8?
209def utf8.check(a: Array<U32>, +i: U32, +end: U32) -> Array<U32> & Bool:
210 utf8.go(U32.to_nat((end - i : U32)), (a, i, True{}), end)
211
212def text.fin(+len: U32, r: Array<U32> & Bool) -> Bytes.Bytes & Bool:
213 (a, ok) = r
214 (Bytes.Bytes{len, a}, ok)
215
216def text.check(b: Bytes.Bytes) -> Bytes.Bytes & Bool:
217 Bytes.Bytes{+len, buf} = b
218 text.fin(len, utf8.check(buf, 0, len))
219
220# Simple values 20..23 have their own constructors, 24..31 are reserved (RFC 8949 §3.3).
221def simple.ok(+v: U32) -> Bool:
222 U32.is_lt(v, 20) || (U32.is_le(32, v) && U32.is_le(v, 255))
223
224# IGuard aborts the encoding when a value has no CBOR form; IText carries a text string and its UTF-8 check.
225type Item is Type:
226 IVal{value: Val}
227 IArr{items: List<&1, Val>}
228 IMap{items: List<&1, Val & Val>}
229 IArrLen{value: List<&1, Val> & Nat}
230 IMapLen{value: List<&1, Val & Val> & Nat}
231 IGuard{ok: Bool}
232 IText{value: Bytes.Bytes & Bool}
233def vals.length.put(h: Val, r: List<&1, Val> & Nat) -> List<&1, Val> & Nat:
234 (rest, n) = r
235 (Con{h, rest}, (1n + n : Nat))
236
237def pairs.length.put(h: Val & Val, r: List<&1, Val & Val> & Nat) -> List<&1, Val & Val> & Nat:
238 (rest, n) = r
239 (Con{h, rest}, (1n + n : Nat))
240
241def vals.length(xs: List<&1, Val>) -> List<&1, Val> & Nat:
242 match xs:
243 case Nil{}:
244 (Nil{}, 0n)
245 case Con{h, t}:
246 vals.length.put(h, vals.length(t))
247
248def pairs.length(xs: List<&1, Val & Val>) -> List<&1, Val & Val> & Nat:
249 match xs:
250 case Nil{}:
251 (Nil{}, 0n)
252 case Con{h, t}:
253 pairs.length.put(h, pairs.length(t))
254
255@unsafe
256def encode.go(items: List<&1, Item>, o: W) -> Maybe<&1, W>:
257 match items:
258 case Nil{}:
259 Some{o}
260 case Con{IGuard{ok}, rest}:
261 match ok:
262 case True{}:
263 encode.go(rest, o)
264 case False{}:
265 None{}
266 case Con{IText{value}, rest}:
267 (b, ok) = value
268 Bytes.Bytes{+len, buf} = b
269 encode.go(Con{IGuard{ok}, rest}, raw.bytes(Bytes.Bytes{len, buf}, head.u32(3, len, o)))
270 case Con{IArrLen{value}, rest}:
271 (xs, n) = value
272 encode.go(Con{IArr{xs}, rest}, head.u32(4, U32.from_nat(n), o))
273 case Con{IMapLen{value}, rest}:
274 (kvs, n) = value
275 encode.go(Con{IMap{kvs}, rest}, head.u32(5, U32.from_nat(n), o))
276 case Con{IArr{xs}, rest}:
277 match xs:
278 case Nil{}:
279 encode.go(rest, o)
280 case Con{h, t}:
281 encode.go(Con{IVal{h}, Con{IArr{t}, rest}}, o)
282 case Con{IMap{kvs}, rest}:
283 match kvs:
284 case Nil{}:
285 encode.go(rest, o)
286 case Con{(k, v), t}:
287 encode.go(Con{IVal{k}, Con{IVal{v}, Con{IMap{t}, rest}}}, o)
288 case Con{IVal{value}, rest}:
289 match value:
290 case UInt{value}:
291 encode.go(rest, uint.bytes(0, value, o))
292 case NInt{value}:
293 encode.go(rest, uint.bytes(1, value, o))
294 case BStr{value}:
295 Bytes.Bytes{+len, buf} = value
296 encode.go(rest, raw.bytes.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, head.u32(2, len, o)))
297 case TStr{value}:
298 encode.go(Con{IText{text.check(value)}, rest}, o)
299 case Arr{items}:
300 encode.go(Con{IArrLen{vals.length(items)}, rest}, o)
301 case Obj{items}:
302 encode.go(Con{IMapLen{pairs.length(items)}, rest}, o)
303 case Tag{number, value}:
304 encode.go(Con{IVal{value}, rest}, uint.bytes(6, number, o))
305 case Sim{value}:
306 match value:
307 case SFalse{}:
308 encode.go(rest, byte(o, 244))
309 case STrue{}:
310 encode.go(rest, byte(o, 245))
311 case SNull{}:
312 encode.go(rest, byte(o, 246))
313 case SUndefined{}:
314 encode.go(rest, byte(o, 247))
315 case Other{+value}:
316 encode.go(Con{IGuard{simple.ok(value)}, rest}, head.u32(7, value, o))
317 case Flt{value}:
318 match value:
319 case Half{+bits}:
320 encode.go(Con{IGuard{U32.is_lt(bits, 65536)}, rest}, byte(byte(byte(o, 249), (bits >> 8n : U32)), bits))
321 case Single{+bits}:
322 encode.go(rest, raw.u32(byte(o, 250), bits))
323 case Double{+bits}:
324 W64{+hi, +lo} = bits
325 encode.go(rest, raw.u32(raw.u32(byte(o, 251), hi), lo))
326
327def encode.done(r: Maybe<&1, W>) -> Maybe<&1, Bytes.Bytes>:
328 match r:
329 case Some{o}:
330 Some{finish(o)}
331 case None{}:
332 None{}
333
334# Definite lengths and the shortest head for every length, integer, and tag; floats keep their width.
335# None when a TStr is not UTF-8, a Half has more than 16 bits, or Other is not a simple value 0..19 or 32..255.
336def encode(v: Val) -> Maybe<&1, Bytes.Bytes>:
337 encode.done(encode.go(Con{IVal{v}, Nil{}}, empty()))
338
339def decode.other(ok: Bool, +value: U32) -> Maybe<&1, Val>:
340 match ok:
341 case True{}:
342 Some{Sim{Other{value}}}
343 case False{}:
344 None{}
345
346def decode.simple(+ai: U32) -> Maybe<&1, Val>:
347 match ai:
348 case 20:
349 Some{Sim{SFalse{}}}
350 case 21:
351 Some{Sim{STrue{}}}
352 case 22:
353 Some{Sim{SNull{}}}
354 case 23:
355 Some{Sim{SUndefined{}}}
356 case _:
357 decode.other(U32.is_lt(ai, 20), ai)
358
359def decode.major7.arg(+ai: U32, +arg: W64) -> Maybe<&1, Val>:
360 match ai:
361 case 24:
362 W64{+hi, +lo} = arg
363 decode.other(U32.is_le(32, lo) && U32.is_le(lo, 255), lo)
364 case 25:
365 W64{hi, lo} = arg
366 Some{Flt{Half{lo}}}
367 case 26:
368 W64{hi, lo} = arg
369 Some{Flt{Single{lo}}}
370 case 27:
371 Some{Flt{Double{arg}}}
372 case _:
373 None{}
374
375def decode.major7(small: Bool, +ai: U32, +arg: W64) -> Maybe<&1, Val>:
376 match small:
377 case True{}:
378 decode.simple(ai)
379 case False{}:
380 decode.major7.arg(ai, arg)
381
382# A head: major type, additional info, argument, and the index after it.
383type Hd is Data:
384 Hd{major: U32, ai: U32, arg: W64, next: U32}
385
386# n argument bytes from j, most significant first.
387def hd.words(n: Nat, r: Array<U32> & U32, +j: U32, +hi: U32, +lo: U32, +major: U32, +ai: U32) -> Array<U32> & Maybe<&2, Hd>:
388 match n:
389 case 0n:
390 (a, b) = r
391 (a, Some{Hd{major, ai, W64{hi, lo}, j}})
392 case 1n+p:
393 (a, +b) = r
394 hd.words(p, Bytes.peek(a, (j + 1 : U32)), (j + 1 : U32), ((hi << 8n) .|. (lo >> 24n) : U32), ((lo << 8n) .|. b : U32), major, ai)
395
396def hd.wide(ok: Bool, n: Nat, a: Array<U32>, +i: U32, +major: U32, +ai: U32) -> Array<U32> & Maybe<&2, Hd>:
397 match ok:
398 case True{}:
399 hd.words(n, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), 0, 0, major, ai)
400 case False{}:
401 (a, None{})
402
403# ai 24..27 take 1, 2, 4 or 8 more bytes; 28..30 are reserved; 31 is indefinite or break.
404def hd.arg(+ai: U32, a: Array<U32>, +len: U32, +i: U32, +major: U32) -> Array<U32> & Maybe<&2, Hd>:
405 match ai:
406 case 24:
407 hd.wide(Bytes.fits(len, (i + 1 : U32), 1), 1n, a, i, major, 24)
408 case 25:
409 hd.wide(Bytes.fits(len, (i + 1 : U32), 2), 2n, a, i, major, 25)
410 case 26:
411 hd.wide(Bytes.fits(len, (i + 1 : U32), 4), 4n, a, i, major, 26)
412 case 27:
413 hd.wide(Bytes.fits(len, (i + 1 : U32), 8), 8n, a, i, major, 27)
414 case 28:
415 (a, None{})
416 case 29:
417 (a, None{})
418 case 30:
419 (a, None{})
420 case _:
421 (a, Some{Hd{major, ai, W64{0, ai}, (i + 1 : U32)}})
422
423def hd.of(+len: U32, +i: U32, r: Array<U32> & U32) -> Array<U32> & Maybe<&2, Hd>:
424 (a, +b) = r
425 hd.arg((b .&. 31 : U32), a, len, i, (b >> 5n : U32))
426
427def hd.read(ok: Bool, a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & Maybe<&2, Hd>:
428 match ok:
429 case True{}:
430 hd.of(len, i, Bytes.peek(a, i))
431 case False{}:
432 (a, None{})
433
434def bstr.some(+n: U32, r: Array<U32> & Array<U32>) -> Array<U32> & Maybe<&1, Bytes.Bytes>:
435 (a, out) = r
436 (a, Some{Bytes.Bytes{n, out}})
437
438def bstr.copy(+n: U32, +i: U32, r: Array<U32> & Bool) -> Array<U32> & Maybe<&1, Bytes.Bytes>:
439 (a, ok) = r
440 match ok:
441 case True{}:
442 bstr.some(n, Bytes.copy(n, a, Bytes.alloc(n), i, 0))
443 case False{}:
444 (a, None{})
445
446def bstr.valid(text: Bool, a: Array<U32>, +i: U32, +end: U32) -> Array<U32> & Bool:
447 match text:
448 case True{}:
449 utf8.check(a, i, end)
450 case False{}:
451 (a, True{})
452
453def bstr.fit(ok: Bool, +text: Bool, a: Array<U32>, +n: U32, +i: U32) -> Array<U32> & Maybe<&1, Bytes.Bytes>:
454 match ok:
455 case True{}:
456 bstr.copy(n, i, bstr.valid(text, a, i, (i + n : U32)))
457 case False{}:
458 (a, None{})
459
460# A definite string of arg bytes from i. None when it runs past len, or when text is not UTF-8.
461def bstr.read(+text: Bool, +arg: W64, a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & Maybe<&1, Bytes.Bytes>:
462 W64{+hi, +lo} = arg
463 bstr.fit(U32.is_eq(hi, 0) && Bytes.fits(len, i, lo), text, a, lo, i)
464
465def wrap(text: Bool, b: Bytes.Bytes) -> Val:
466 match text:
467 case True{}:
468 TStr{b}
469 case False{}:
470 BStr{b}
471
472# An open container. Items are reversed; left counts the definite items (or pairs) still due, this one included.
473type Frame is Type:
474 FArr{left: U32, xs: List<&1, Val>}
475 FArrI{xs: List<&1, Val>}
476 FMap{left: U32, kvs: List<&1, Val & Val>}
477 FKey{left: U32, kvs: List<&1, Val & Val>, key: Val}
478 FMapI{kvs: List<&1, Val & Val>}
479 FKeyI{kvs: List<&1, Val & Val>, key: Val}
480 FTag{number: W64}
481
482# SHead reads an item at i; SChunk reads the next chunk of an indefinite string; SDone hands v to the open frame.
483type St is Type:
484 SHead{i: U32, stack: List<&1, Frame>}
485 SChunk{i: U32, text: Bool, chunks: List<&1, Bytes.Bytes>, stack: List<&1, Frame>}
486 SDone{v: Val, i: U32, stack: List<&1, Frame>}
487 SOk{v: Val}
488 SFail{}
489
490def item.str(+text: Bool, +i: U32, stack: List<&1, Frame>, r: Array<U32> & Maybe<&1, Bytes.Bytes>) -> Array<U32> & St:
491 (a, m) = r
492 match m:
493 case Some{b}:
494 Bytes.Bytes{+n, buf} = b
495 (a, SDone{wrap(text, Bytes.Bytes{n, buf}), (i + n : U32), stack})
496 case None{}:
497 (a, SFail{})
498
499def item.empty(map: Bool, +i: U32, stack: List<&1, Frame>) -> St:
500 match map:
501 case True{}:
502 SDone{Obj{Nil{}}, i, stack}
503 case False{}:
504 SDone{Arr{Nil{}}, i, stack}
505
506def item.push(map: Bool, +n: U32, +i: U32, stack: List<&1, Frame>) -> St:
507 match map:
508 case True{}:
509 SHead{i, Con{FMap{n, Nil{}}, stack}}
510 case False{}:
511 SHead{i, Con{FArr{n, Nil{}}, stack}}
512
513def item.open(empty: Bool, +map: Bool, +n: U32, +i: U32, stack: List<&1, Frame>) -> St:
514 match empty:
515 case True{}:
516 item.empty(map, i, stack)
517 case False{}:
518 item.push(map, n, i, stack)
519
520def item.count(ok: Bool, +map: Bool, +n: U32, +i: U32, stack: List<&1, Frame>) -> St:
521 match ok:
522 case True{}:
523 item.open(U32.is_eq(n, 0), map, n, i, stack)
524 case False{}:
525 SFail{}
526
527# Every item takes a byte, so a count past the bytes left is malformed; this also keeps it in a U32.
528def item.len(+map: Bool, +arg: W64, +len: U32, +i: U32, stack: List<&1, Frame>) -> St:
529 W64{+hi, +lo} = arg
530 item.count(U32.is_eq(hi, 0) && U32.is_le(lo, (len - i : U32)), map, lo, i, stack)
531
532def item.simple(m: Maybe<&1, Val>, +i: U32, stack: List<&1, Frame>) -> St:
533 match m:
534 case Some{v}:
535 SDone{v, i, stack}
536 case None{}:
537 SFail{}
538
539def item.def(+major: U32, +ai: U32, +arg: W64, +i: U32, a: Array<U32>, +len: U32, stack: List<&1, Frame>) -> Array<U32> & St:
540 match major:
541 case 0:
542 (a, SDone{UInt{arg}, i, stack})
543 case 1:
544 (a, SDone{NInt{arg}, i, stack})
545 case 2:
546 item.str(False{}, i, stack, bstr.read(False{}, arg, a, len, i))
547 case 3:
548 item.str(True{}, i, stack, bstr.read(True{}, arg, a, len, i))
549 case 4:
550 (a, item.len(False{}, arg, len, i, stack))
551 case 5:
552 (a, item.len(True{}, arg, len, i, stack))
553 case 6:
554 (a, SHead{i, Con{FTag{arg}, stack}})
555 case _:
556 (a, item.simple(decode.major7(U32.is_lt(ai, 24), ai, arg), i, stack))
557
558# A break closes the innermost indefinite array, or map with no key pending; anywhere else it is malformed.
559def brk.fr(fr: Frame, +i: U32, rest: List<&1, Frame>) -> St:
560 match fr:
561 case FArrI{xs}:
562 SDone{Arr{List.reverse(&1, Val, xs)}, i, rest}
563 case FMapI{kvs}:
564 SDone{Obj{List.reverse(&1, Val & Val, kvs)}, i, rest}
565 case FArr{left, xs}:
566 SFail{}
567 case FMap{left, kvs}:
568 SFail{}
569 case FKey{left, kvs, k}:
570 SFail{}
571 case FKeyI{kvs, k}:
572 SFail{}
573 case FTag{number}:
574 SFail{}
575
576def brk(stack: List<&1, Frame>, +i: U32) -> St:
577 match stack:
578 case Nil{}:
579 SFail{}
580 case Con{fr, rest}:
581 brk.fr(fr, i, rest)
582
583# ai 31: indefinite string, array, or map, or (major 7) a break. Majors 0, 1 and 6 have no indefinite form.
584def item.indef(+major: U32, +i: U32, stack: List<&1, Frame>) -> St:
585 match major:
586 case 2:
587 SChunk{i, False{}, Nil{}, stack}
588 case 3:
589 SChunk{i, True{}, Nil{}, stack}
590 case 4:
591 SHead{i, Con{FArrI{Nil{}}, stack}}
592 case 5:
593 SHead{i, Con{FMapI{Nil{}}, stack}}
594 case 7:
595 brk(stack, i)
596 case _:
597 SFail{}
598
599def item.hd(indef: Bool, +major: U32, +ai: U32, +arg: W64, +i: U32, a: Array<U32>, +len: U32, stack: List<&1, Frame>) -> Array<U32> & St:
600 match indef:
601 case True{}:
602 (a, item.indef(major, i, stack))
603 case False{}:
604 item.def(major, ai, arg, i, a, len, stack)
605
606def step.head(stack: List<&1, Frame>, +len: U32, r: Array<U32> & Maybe<&2, Hd>) -> Array<U32> & St:
607 (a, h) = r
608 match h:
609 case Some{Hd{+major, +ai, +arg, +i}}:
610 item.hd(U32.is_eq(ai, 31), major, ai, arg, i, a, len, stack)
611 case None{}:
612 (a, SFail{})
613
614def chunk.str(+text: Bool, chunks: List<&1, Bytes.Bytes>, +i: U32, stack: List<&1, Frame>, r: Array<U32> & Maybe<&1, Bytes.Bytes>) -> Array<U32> & St:
615 (a, m) = r
616 match m:
617 case Some{b}:
618 Bytes.Bytes{+n, buf} = b
619 (a, SChunk{(i + n : U32), text, Con{Bytes.Bytes{n, buf}, chunks}, stack})
620 case None{}:
621 (a, SFail{})
622
623def chunk.more(ok: Bool, +text: Bool, chunks: List<&1, Bytes.Bytes>, +arg: W64, +i: U32, a: Array<U32>, +len: U32, stack: List<&1, Frame>) -> Array<U32> & St:
624 match ok:
625 case True{}:
626 chunk.str(text, chunks, i, stack, bstr.read(text, arg, a, len, i))
627 case False{}:
628 (a, SFail{})
629
630# Each chunk is a definite string of the same major type, UTF-8 by itself for text (RFC 8949 §3.2.3).
631def chunk.end(stop: Bool, ok: Bool, +text: Bool, chunks: List<&1, Bytes.Bytes>, +arg: W64, +i: U32, a: Array<U32>, +len: U32, stack: List<&1, Frame>) -> Array<U32> & St:
632 match stop:
633 case True{}:
634 (a, SDone{wrap(text, Bytes.concat(List.reverse(&1, Bytes.Bytes, chunks))), i, stack})
635 case False{}:
636 chunk.more(ok, text, chunks, arg, i, a, len, stack)
637
638def step.chunk(+text: Bool, chunks: List<&1, Bytes.Bytes>, stack: List<&1, Frame>, +len: U32, r: Array<U32> & Maybe<&2, Hd>) -> Array<U32> & St:
639 (a, h) = r
640 match h:
641 case Some{Hd{+major, +ai, +arg, +i}}:
642 chunk.end(U32.is_eq(major, 7) && U32.is_eq(ai, 31), U32.is_eq(major, Bool.pick(U32, text, 3, 2)) && U32.is_ne(ai, 31), text, chunks, arg, i, a, len, stack)
643 case None{}:
644 (a, SFail{})
645
646def done.arr(last: Bool, +left: U32, xs: List<&1, Val>, +i: U32, rest: List<&1, Frame>) -> St:
647 match last:
648 case True{}:
649 SDone{Arr{List.reverse(&1, Val, xs)}, i, rest}
650 case False{}:
651 SHead{i, Con{FArr{(left - 1 : U32), xs}, rest}}
652
653def done.map(last: Bool, +left: U32, kvs: List<&1, Val & Val>, +i: U32, rest: List<&1, Frame>) -> St:
654 match last:
655 case True{}:
656 SDone{Obj{List.reverse(&1, Val & Val, kvs)}, i, rest}
657 case False{}:
658 SHead{i, Con{FMap{(left - 1 : U32), kvs}, rest}}
659
660def done.fr(fr: Frame, v: Val, +i: U32, rest: List<&1, Frame>) -> St:
661 match fr:
662 case FArr{+left, xs}:
663 done.arr(U32.is_eq(left, 1), left, Con{v, xs}, i, rest)
664 case FArrI{xs}:
665 SHead{i, Con{FArrI{Con{v, xs}}, rest}}
666 case FMap{+left, kvs}:
667 SHead{i, Con{FKey{left, kvs, v}, rest}}
668 case FKey{+left, kvs, k}:
669 done.map(U32.is_eq(left, 1), left, Con{(k, v), kvs}, i, rest)
670 case FMapI{kvs}:
671 SHead{i, Con{FKeyI{kvs, v}, rest}}
672 case FKeyI{kvs, k}:
673 SHead{i, Con{FMapI{Con{(k, v), kvs}}, rest}}
674 case FTag{number}:
675 SDone{Tag{number, v}, i, rest}
676
677def done.top(end: Bool, v: Val) -> St:
678 match end:
679 case True{}:
680 SOk{v}
681 case False{}:
682 SFail{}
683
684# A finished top-level item must end the input.
685def done(stack: List<&1, Frame>, v: Val, +i: U32, +len: U32) -> St:
686 match stack:
687 case Nil{}:
688 done.top(U32.is_eq(i, len), v)
689 case Con{fr, rest}:
690 done.fr(fr, v, i, rest)
691
692def run(fuel: Nat, r: Array<U32> & St, +len: U32) -> Maybe<&1, Val>:
693 match fuel:
694 case 0n:
695 None{}
696 case 1n+f:
697 (a, st) = r
698 match st:
699 case SOk{v}:
700 Some{v}
701 case SFail{}:
702 None{}
703 case SHead{+i, stack}:
704 run(f, step.head(stack, len, hd.read(U32.is_lt(i, len), a, len, i)), len)
705 case SChunk{+i, +text, chunks, stack}:
706 run(f, step.chunk(text, chunks, stack, len, hd.read(U32.is_lt(i, len), a, len, i)), len)
707 case SDone{v, +i, stack}:
708 run(f, (a, done(stack, v, i, len)), len)
709
710# One well-formed data item (RFC 8949 §3, Appendix C) filling b. Indefinite strings, arrays and maps come back
711# definite, with chunks joined. None for truncation, reserved ai 28..30, a misplaced break or indefinite form,
712# a simple value 0..31 in two bytes, text that is not UTF-8, or trailing bytes.
713# fuel: a head or chunk eats a byte, and each SDone step follows one, so 2 * len + 2 steps are enough.
714def decode(b: Bytes.Bytes) -> Maybe<&1, Val>:
715 Bytes.Bytes{+len, buf} = b
716 run(Nat.add(Nat.mul(U32.to_nat(len), 2n), 2n), (buf, SHead{0, Nil{}}), len)