1 # CBOR (RFC 8949) values encoded and decoded over Bytes. Source: https://github.com/paymog/bend-kit/tree/main/cbor 2 import Base 3 import 0x49814d83de8f70993a43e1002be29ecd/bytes.bend as Bytes 4 5 # Raw words preserve CBOR integer and floating-point bit patterns. 6 type W64 is Data: 7 W64{hi: U32, lo: U32} 8 9 type Float is Data: 10 Half{bits: U32} 11 Single{bits: U32} 12 Double{bits: W64} 13 14 type Simple is Data: 15 SFalse{} 16 STrue{} 17 SNull{} 18 SUndefined{} 19 Other{value: U32} 20 21 type 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 32 type W is Type: 33 W{buf: Array, cap: U32, n: U32, word: U32} 34 def grow.if(grow: Bool, buf: Array, +k: U32) -> Array: 35 match grow: 36 case True{}: 37 Bytes.grow((k * 4 : U32), buf, (k * 8 : U32)) 38 case False{}: 39 buf 40 41 42 def put(full: Bool, buf: Array, +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} 51 def finish.buf(full: Bool, cap: U32, buf: Array, +k: U32, +r: U32, +word: U32) -> Array: 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 60 def 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 65 def 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)} 71 def empty() -> W: 72 W{Bytes.alloc(0), 1, 0, 0} 73 74 def head.small(+major: U32, +v: U32, o: W) -> W: 75 byte(o, ((major << 5n) .|. v : U32)) 76 77 def 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 84 def 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 91 def 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) 97 def head.u32(+major: U32, +v: U32, o: W) -> W: 98 head.u32.small(U32.is_lt(v, 24), major, v, o) 99 100 def raw.u32(o: W, +v: U32) -> W: 101 byte(byte(byte(byte(o, (v >> 24n : U32)), (v >> 16n : U32)), (v >> 8n : U32)), v) 102 103 def 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 110 def 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 114 def raw.bytes.go(n: Nat, r: Array & 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 122 def 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. 127 type Cp is Data: 128 Cp{c: U32, w: U32} 129 130 def pk.if(ok: Bool, a: Array, +i: U32) -> Array & 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. 138 def pk(a: Array, +end: U32, +i: U32) -> Array & U32: 139 pk.if(U32.is_lt(i, end), a, i) 140 141 def cont(+b: U32) -> Bool: 142 U32.is_eq((b .&. 192 : U32), 128) 143 144 def 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 156 def utf8.b3(+b0: U32, +b1: U32, +b2: U32, r: Array & U32) -> Array & Cp: 157 (a, +b3) = r 158 (a, utf8.n(b0, b1, b2, b3)) 159 160 def utf8.b2(+end: U32, +i: U32, +b0: U32, +b1: U32, r: Array & U32) -> Array & Cp: 161 (a, +b2) = r 162 utf8.b3(b0, b1, b2, pk(a, end, (i + 3 : U32))) 163 164 def utf8.b1(+end: U32, +i: U32, +b0: U32, r: Array & U32) -> Array & Cp: 165 (a, +b1) = r 166 utf8.b2(end, i, b0, b1, pk(a, end, (i + 2 : U32))) 167 168 def utf8.cp(+i: U32, r: Array & Cp) -> Array & U32 & Bool: 169 (a, cp) = r 170 Cp{c, +w} = cp 171 (a, (i + w : U32), U32.is_ne(w, 0)) 172 173 def utf8.byte(ascii: Bool, a: Array, +end: U32, +i: U32, +b: U32) -> Array & 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 180 def utf8.lead(+end: U32, +i: U32, r: Array & U32) -> Array & U32 & Bool: 181 (a, +b) = r 182 utf8.byte(U32.is_lt(b, 128), a, end, i, b) 183 184 def utf8.more(go: Bool, a: Array, +end: U32, +i: U32) -> Array & 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 191 def utf8.step(ok: Bool, a: Array, +end: U32, +i: U32) -> Array & 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. 199 def utf8.go(n: Nat, r: Array & U32 & Bool, +end: U32) -> Array & 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? 209 def utf8.check(a: Array, +i: U32, +end: U32) -> Array & Bool: 210 utf8.go(U32.to_nat((end - i : U32)), (a, i, True{}), end) 211 212 def text.fin(+len: U32, r: Array & Bool) -> Bytes.Bytes & Bool: 213 (a, ok) = r 214 (Bytes.Bytes{len, a}, ok) 215 216 def 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). 221 def 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. 225 type 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} 233 def 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 237 def 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 241 def 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 248 def 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 256 def 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 327 def 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. 336 def encode(v: Val) -> Maybe<&1, Bytes.Bytes>: 337 encode.done(encode.go(Con{IVal{v}, Nil{}}, empty())) 338 339 def 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 346 def 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 359 def 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 375 def 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. 383 type Hd is Data: 384 Hd{major: U32, ai: U32, arg: W64, next: U32} 385 386 # n argument bytes from j, most significant first. 387 def hd.words(n: Nat, r: Array & U32, +j: U32, +hi: U32, +lo: U32, +major: U32, +ai: U32) -> Array & 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 396 def hd.wide(ok: Bool, n: Nat, a: Array, +i: U32, +major: U32, +ai: U32) -> Array & 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. 404 def hd.arg(+ai: U32, a: Array, +len: U32, +i: U32, +major: U32) -> Array & 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 423 def hd.of(+len: U32, +i: U32, r: Array & U32) -> Array & Maybe<&2, Hd>: 424 (a, +b) = r 425 hd.arg((b .&. 31 : U32), a, len, i, (b >> 5n : U32)) 426 427 def hd.read(ok: Bool, a: Array, +len: U32, +i: U32) -> Array & 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 434 def bstr.some(+n: U32, r: Array & Array) -> Array & Maybe<&1, Bytes.Bytes>: 435 (a, out) = r 436 (a, Some{Bytes.Bytes{n, out}}) 437 438 def bstr.copy(+n: U32, +i: U32, r: Array & Bool) -> Array & 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 446 def bstr.valid(text: Bool, a: Array, +i: U32, +end: U32) -> Array & Bool: 447 match text: 448 case True{}: 449 utf8.check(a, i, end) 450 case False{}: 451 (a, True{}) 452 453 def bstr.fit(ok: Bool, +text: Bool, a: Array, +n: U32, +i: U32) -> Array & 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. 461 def bstr.read(+text: Bool, +arg: W64, a: Array, +len: U32, +i: U32) -> Array & 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 465 def 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. 473 type 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. 483 type 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 490 def item.str(+text: Bool, +i: U32, stack: List<&1, Frame>, r: Array & Maybe<&1, Bytes.Bytes>) -> Array & 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 499 def 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 506 def 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 513 def 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 520 def 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. 528 def 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 532 def 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 539 def item.def(+major: U32, +ai: U32, +arg: W64, +i: U32, a: Array, +len: U32, stack: List<&1, Frame>) -> Array & 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. 559 def 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 576 def 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. 584 def 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 599 def item.hd(indef: Bool, +major: U32, +ai: U32, +arg: W64, +i: U32, a: Array, +len: U32, stack: List<&1, Frame>) -> Array & 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 606 def step.head(stack: List<&1, Frame>, +len: U32, r: Array & Maybe<&2, Hd>) -> Array & 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 614 def chunk.str(+text: Bool, chunks: List<&1, Bytes.Bytes>, +i: U32, stack: List<&1, Frame>, r: Array & Maybe<&1, Bytes.Bytes>) -> Array & 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 623 def chunk.more(ok: Bool, +text: Bool, chunks: List<&1, Bytes.Bytes>, +arg: W64, +i: U32, a: Array, +len: U32, stack: List<&1, Frame>) -> Array & 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). 631 def chunk.end(stop: Bool, ok: Bool, +text: Bool, chunks: List<&1, Bytes.Bytes>, +arg: W64, +i: U32, a: Array, +len: U32, stack: List<&1, Frame>) -> Array & 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 638 def step.chunk(+text: Bool, chunks: List<&1, Bytes.Bytes>, stack: List<&1, Frame>, +len: U32, r: Array & Maybe<&2, Hd>) -> Array & 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 646 def 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 653 def 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 660 def 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 677 def 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. 685 def 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 692 def run(fuel: Nat, r: Array & 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. 714 def 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)