1 # JSON values, parsed and encoded as RFC 8259. Source: https://github.com/paymog/bend-kit/tree/main/json 2 import Base 3 import 0x49814d83de8f70993a43e1002be29ecd/bytes.bend as Bytes 4 5 # JSON (RFC 8259) 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. 12 type 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. 22 type 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. 31 type W is Type: 32 W{buf: Array, cap: U32, n: U32, w: U32} 33 34 # The buffer doubles when word k does not fit. 35 def w.room(grow: Bool, buf: Array, +k: U32) -> Array: 36 match grow: 37 case True{}: 38 Bytes.grow((k * 4 : U32), buf, (k * 8 : U32)) 39 case False{}: 40 buf 41 42 def w.store(full: Bool, buf: Array, +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 51 def 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 55 def w.shrink(fit: Bool, +n: U32, buf: Array) -> Array: 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. 63 def 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 72 def w.cont(+c: U32, +k: Nat) -> U32: 73 (128 + (U32.shrn(c, k) .&. 63) : U32) 74 75 def 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. 87 def 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 90 def w.hex(+n: U32) -> U32: 91 Bool.pick(U32, U32.is_lt(n, 10), (48 + n : U32), (87 + n : U32)) 92 93 def w.new() -> W: 94 W{Bytes.alloc(0), 1, 0, 0} 95 96 def w.of.at(+len: U32, +cap: U32, r: Array & 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. 102 def 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 106 def 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. 114 def 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 123 def digit(+c: U32) -> Bool: 124 Bool.and(U32.is_le(48, c), U32.is_le(c, 57)) 125 126 def 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 139 def 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 145 def 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 148 def is_hi(+v: U32) -> Bool: 149 Bool.and(U32.is_le(55296, v), U32.is_le(v, 56319)) 150 151 def is_lo(+v: U32) -> Bool: 152 Bool.and(U32.is_le(56320, v), U32.is_le(v, 57343)) 153 154 def 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 165 type 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 179 type Cp is Data: 180 Cp{c: U32, w: U32} 181 182 def pk.if(ok: Bool, a: Array, +i: U32) -> Array & 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. 190 def pk(a: Array, +len: U32, +i: U32) -> Array & U32: 191 pk.if(U32.is_lt(i, len), a, i) 192 193 def 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. 197 def 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 200 def pos.of(+i: U32, r: Array & U32) -> Array & U32 & U32: 201 (a, +c) = r 202 (a, i, c) 203 204 # The offset i and its byte. 205 def pos(a: Array, +len: U32, +i: U32) -> Array & U32 & U32: 206 pos.of(i, pk(a, len, i)) 207 208 def run.cls(~ok: @+c: U32 -> Bool, r: Array & U32) -> Array & 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. 213 def run.go(~ok: @+c: U32 -> Bool, g: Nat, r: Array & U32 & Bool, +len: U32, +i: U32) -> Array & 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. 227 def run(~ok: @+c: U32 -> Bool, +g: Nat, a: Array, +len: U32, +i: U32) -> Array & U32 & U32: 228 run.go(~ok, g, run.cls(~ok, pk(a, len, i)), len, i) 229 230 def word.go(w: String, ok: Bool, r: Array & U32, +len: U32, +j: U32) -> Array & 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? 240 def word(a: Array, +len: U32, w: String, +j: U32) -> Array & Bool: 241 word.go(w, True{}, pk(a, len, j), len, j) 242 243 def hex4.b.go(n: Nat, r: Array & U32, +len: U32, +j: U32, +acc: U32) -> Array & 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. 254 def hex4.b(a: Array, +len: U32, +j: U32) -> Array & U32: 255 hex4.b.go(4n, pk(a, len, j), len, j, 0) 256 257 def 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. 261 def 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 273 def utf8.b3(+b0: U32, +b1: U32, +b2: U32, r: Array & U32) -> Array & Cp: 274 (a, +b3) = r 275 (a, utf8.n(b0, b1, b2, b3)) 276 277 def utf8.b2(+len: U32, +i: U32, +b0: U32, +b1: U32, r: Array & U32) -> Array & Cp: 278 (a, +b2) = r 279 utf8.b3(b0, b1, b2, pk(a, len, (i + 3 : U32))) 280 281 def utf8.b1(+len: U32, +i: U32, +b0: U32, r: Array & U32) -> Array & 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. 286 def utf8.at(a: Array, +len: U32, +i: U32, +b0: U32) -> Array & Cp: 287 utf8.b1(len, i, b0, pk(a, len, (i + 1 : U32))) 288 289 def slice.of(+n: U32, r: Array & Array) -> Array & Bytes.Bytes: 290 (a, out) = r 291 (a, Bytes.Bytes{n, out}) 292 293 # The n bytes from start, copied. 294 def slice(+n: U32, +start: U32, a: Array) -> Array & Bytes.Bytes: 295 slice.of(n, Bytes.copy(n, a, Bytes.alloc(n), start, 0)) 296 297 def 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 304 def 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 311 def 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 318 def esc.b.lo(strict: Bool, +i: U32, +hi: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array & U32) -> Array & 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. 323 def esc.b.pair(+strict: Bool, +len: U32, +i: U32, +hi: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array & Bool) -> Array & 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. 332 def 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 335 def esc.b.u.of(+k: U32, strict: Bool, a: Array, +len: U32, +i: U32, +v: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Array & 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 346 def esc.b.u(strict: Bool, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array & U32) -> Array & 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. 351 def esc.b.one(strict: Bool, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array & U32) -> Array & 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 360 def esc.b.cp(acc: W, key: Bool, stack: List<&1, Open>, +i: U32, r: Array & Cp) -> Array & 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. 365 def esc.b.other(ascii: Bool, +c: U32, a: Array, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Array & 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. 373 def esc.b(strict: Bool, r: Array & U32, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>) -> Array & 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 385 def str.b.close(key: Bool, +i: U32, stack: List<&1, Open>, r: Array & Bytes.Bytes) -> Array & Sb: 386 (a, s) = r 387 (a, str.b.done(key, s, (i + 1 : U32), stack)) 388 389 def str.b.esc(strict: Bool, +len: U32, +i: U32, key: Bool, stack: List<&1, Open>, r: Array & Bytes.Bytes) -> Array & Sb: 390 (a, s) = r 391 esc.b.one(strict, len, i, w.of(s), key, stack, pk(a, len, (i + 1 : U32))) 392 393 def str.b.cp(+start: U32, key: Bool, stack: List<&1, Open>, +i: U32, r: Array & Cp) -> Array & 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 397 def str.b.other(ascii: Bool, +c: U32, a: Array, +len: U32, +i: U32, +start: U32, key: Bool, stack: List<&1, Open>) -> Array & 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. 405 def str.b(strict: Bool, r: Array & U32, +len: U32, +i: U32, +start: U32, key: Bool, stack: List<&1, Open>) -> Array & 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 417 def num.b.fin(+i: U32, stack: List<&1, Open>, r: Array & Bytes.Bytes) -> Array & Sb: 418 (a, s) = r 419 (a, BAfter{Num{s}, i, stack}) 420 421 def num.b.stop(ok: Bool, a: Array, +i: U32, +start: U32, stack: List<&1, Open>) -> Array & 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 428 def num.b.if(stop: Bool, a: Array, +i: U32, +start: U32, +st: U32, +n: U32, stack: List<&1, Open>) -> Array & 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 435 def num.b(r: Array & U32, +i: U32, +start: U32, +st: U32, stack: List<&1, Open>) -> Array & 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 440 def lit.b(+i: U32, +n: U32, v: Val, stack: List<&1, Open>, r: Array & Bool) -> Array & 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 448 def value.b(r: Array & U32, +len: U32, +i: U32, stack: List<&1, Open>) -> Array & 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. 475 def 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 484 def 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 493 def first.b(r: Array & U32, +i: U32, open: Open, stack: List<&1, Open>) -> Array & 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 511 def key.b(r: Array & U32, +i: U32, stack: List<&1, Open>) -> Array & 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 527 def 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 538 def colon.b(r: Array & U32, k: Bytes.Bytes, +i: U32, stack: List<&1, Open>) -> Array & 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. 555 def 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 566 def 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 575 def 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. 585 def sep.b(r: Array & U32, +i: U32, open: Open, up: List<&1, Open>) -> Array & 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 601 def end.b(r: Array & U32, v: Val, +i: U32) -> Array & 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). 618 def value.r(+len: U32, stack: List<&1, Open>, r: Array & U32 & U32) -> Array & Sb: 619 (a, i, c) = r 620 value.b((a, c), len, i, stack) 621 622 def level.r(depth: U32, r: Array & Sb) -> Array & Sb & U32: 623 (a, sb) = r 624 (a, sb, depth) 625 626 def first.at(a: Array, +c: U32, i: U32, +depth: U32, open: Open, stack: List<&1, Open>) -> Array & 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 629 def first.r(ok: Bool, +depth: U32, open: Open, stack: List<&1, Open>, r: Array & U32 & U32) -> Array & 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 638 def first.limit(cap: U32, +depth: U32, open: Open, stack: List<&1, Open>, r: Array & U32 & U32) -> Array & Sb & U32: 639 first.r(U32.is_lt(depth, cap), depth, open, stack, r) 640 641 def key.r(stack: List<&1, Open>, r: Array & U32 & U32) -> Array & Sb: 642 (a, i, c) = r 643 key.b((a, c), i, stack) 644 645 def colon.r(k: Bytes.Bytes, stack: List<&1, Open>, r: Array & U32 & U32) -> Array & Sb: 646 (a, i, c) = r 647 colon.b((a, c), k, i, stack) 648 649 def str.r(strict: Bool, +len: U32, +s: U32, key: Bool, stack: List<&1, Open>, r: Array & U32 & U32) -> Array & Sb: 650 (a, i, c) = r 651 str.b(strict, (a, c), len, i, s, key, stack) 652 653 def num.r(+s: U32, +st: U32, stack: List<&1, Open>, r: Array & U32 & U32) -> Array & Sb: 654 (a, i, c) = r 655 num.b((a, c), i, s, st, stack) 656 657 def sep.at(a: Array, +c: U32, i: U32, +depth: U32, open: Open, up: List<&1, Open>) -> Array & 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 660 def sep.r(+depth: U32, open: Open, up: List<&1, Open>, r: Array & U32 & U32) -> Array & Sb & U32: 661 (a, i, c) = r 662 sep.at(a, c, i, depth, open, up) 663 664 def end.r(v: Val, r: Array & U32 & U32) -> Array & Sb: 665 (a, i, c) = r 666 end.b((a, c), v, i) 667 668 def w.span.go(n: Nat, r: Array & U32, +i: U32, o: W) -> Array & 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 677 def esc.r.go(strict: Bool, +len: U32, +j: U32, c: U32, key: Bool, stack: List<&1, Open>, r: Array & W) -> Array & 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. 682 def esc.r(strict: Bool, +len: U32, +i: U32, acc: W, key: Bool, stack: List<&1, Open>, r: Array & U32 & U32) -> Array & 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. 687 def num.run(loop: Bool, +g: Nat, a: Array, +len: U32, +i: U32) -> Array & 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. 695 def runb(+fuel: Nat, r: Array & 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. 728 def 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. 735 def 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 742 def 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 746 def 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 750 def 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. 759 def 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 774 def 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. 786 def 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 801 def 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 804 def 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 815 def u32.zero(t: String) -> Maybe<&2, U32>: 816 match t: 817 case SNil{}: 818 Some{0} 819 case SCon{d, u}: 820 None{} 821 822 def 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 829 def 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. 837 def 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 855 def 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. 863 def 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 878 def w.bytes.go(n: Nat, r: Array & 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 886 def 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 890 def w.str.go(n: Nat, r: Array & 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. 899 def 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. 904 def 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 911 def 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 918 def 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. 946 def encode.bytes(v: Val) -> Bytes.Bytes: 947 w.done(encb.go(v, True{}, W{Bytes.alloc(64), 16, 0, 0}))