src/json.bend

bend-kube-runtime@0.2.0.0 · 654 lines · 79 definitions

1import Base
2
3# JSON
4# ====
5#
6# A JSON value is one datatype whose children are direct subterms, so every
7# fold over it is structural: an array is a chain of JCons ending in JNil, and
8# an object is a chain of JMem ending in JNil. Numbers keep their source text,
9# as serde_json's arbitrary_precision does, so int64 and float values
10# round-trip exactly.
11
12type Json is Data:
13  JNull{}
14  JBool{value: Bool}
15  JNum{text: String}
16  JStr{text: String}
17  JArr{items: Json}
18  JObj{members: Json}
19  JNil{}
20  JCons{head: Json, tail: Json}
21  JMem{key: String, val: Json, tail: Json}
22
23# Parsing
24# -------
25#
26# A pushdown automaton fed one char at a time: the recursion is on the input
27# string, so it terminates by structure, and a watch stream can feed it as
28# bytes arrive. Containers under construction sit on the stack, newest first,
29# with their members reversed.
30
31# A key and its value, as an object member outside the chain.
32type KV is Data:
33  KV{key: String, val: Json}
34
35type Frame is Data:
36  FArr{items: List<&2, Json>}
37  FObj{members: List<&2, KV>, key: String}
38
39# What the automaton expects next.
40#   LVal: a value; open says a ']' may close an empty array here
41#   LAfter: ',' or a closer, after a value
42#   LKey: a member key; open says a '}' may close an empty object
43#   LColon: the ':' after a key
44#   LStr: inside a string, reversed; esc is 0, 1 after '\', 2..5 in \uXXXX
45#   LNum, LLit: inside a number or a literal, reversed
46type Lex is Data:
47  LVal{open: Bool}
48  LAfter{}
49  LKey{open: Bool}
50  LColon{}
51  LStr{buf: String, key: Bool, esc: U32, code: U32}
52  LNum{buf: String}
53  LLit{buf: String}
54  LDone{value: Json}
55  LErr{msg: String}
56
57type JState is Data:
58  JS{lex: Lex, stack: List<&2, Frame>}
59
60def Json.cons_all(xs: List<&2, Json>) -> Json:
61  match xs:
62    case Nil{}:
63      JNil{}
64    case Con{h, t}:
65      JCons{h, Json.cons_all(t)}
66
67# Construction
68# ------------
69
70def Json.arr(xs: List<&2, Json>) -> Json:
71  JArr{Json.cons_all(xs)}
72
73def Json.mem_all(fs: List<&2, KV>) -> Json:
74  match fs:
75    case Nil{}:
76      JNil{}
77    case Con{KV{k, v}, t}:
78      JMem{k, v, Json.mem_all(t)}
79
80def Json.obj(fs: List<&2, KV>) -> Json:
81  JObj{Json.mem_all(fs)}
82
83def Json.str(s: String) -> Json:
84  JStr{s}
85
86def Json.u32(n: U32) -> Json:
87  JNum{U32.show(n)}
88
89# Access
90# ------
91
92# Whether a member chain starts with key.
93def Json.head_is(ms: Json, +key: String) -> Bool:
94  match ms:
95    case JMem{k, v, t}:
96      String.eq(k, key)
97    case _:
98      False{}
99
100# The value under key in an object's member chain; JNull when absent. hit
101# says whether the chain's head is key.
102def Json.lookup.go(ms: Json, +key: String, hit: Bool) -> Json:
103  match ms hit:
104    case JMem{k, v, t} True{}:
105      v
106    case JMem{k, v, +t} False{}:
107      Json.lookup.go(t, key, Json.head_is(t, key))
108    case _ _:
109      JNull{}
110
111def Json.lookup(+ms: Json, +key: String) -> Json:
112  Json.lookup.go(ms, key, Json.head_is(ms, key))
113
114# Sets key in a member chain, replacing the first match or appending.
115def Json.put_mem.go(ms: Json, +key: String, v: Json, hit: Bool) -> Json:
116  match ms hit:
117    case JMem{k, x, t} True{}:
118      JMem{k, v, t}
119    case JMem{k, x, +t} False{}:
120      JMem{k, x, Json.put_mem.go(t, key, v, Json.head_is(t, key))}
121    case _ _:
122      JMem{key, v, JNil{}}
123
124def Json.put_mem(+ms: Json, +key: String, v: Json) -> Json:
125  Json.put_mem.go(ms, key, v, Json.head_is(ms, key))
126
127# The value under key in an object's member chain; JNull when absent.
128def Json.get(j: Json, +key: String) -> Json:
129  match j:
130    case JObj{ms}:
131      Json.lookup(ms, key)
132    case _:
133      JNull{}
134
135# Follows a path of keys; JNull as soon as one is missing.
136def Json.at.go(path: List<&2, String>, j: Json) -> Json:
137  match path:
138    case Nil{}:
139      j
140    case Con{k, t}:
141      Json.at.go(t, Json.get(j, k))
142
143def Json.at(j: Json, path: List<&2, String>) -> Json:
144  Json.at.go(path, j)
145
146def Json.as_str(j: Json) -> Maybe<&2, String>:
147  match j:
148    case JStr{s}:
149      Some{s}
150    case _:
151      None{}
152
153def Json.as_u32(j: Json) -> Maybe<&2, U32>:
154  match j:
155    case JNum{s}:
156      U32.read(s)
157    case _:
158      None{}
159
160def Json.str_or(j: Json, d: String) -> String:
161  match j:
162    case JStr{s}:
163      s
164    case _:
165      d
166
167def Json.is_null(j: Json) -> Bool:
168  match j:
169    case JNull{}:
170      True{}
171    case _:
172      False{}
173
174def Json.chain(xs: Json) -> List<&2, Json>:
175  match xs:
176    case JCons{h, t}:
177      h <> Json.chain(t)
178    case _:
179      Nil{}
180
181# The elements of an array, in order; Nil for anything else.
182def Json.items(j: Json) -> List<&2, Json>:
183  match j:
184    case JArr{xs}:
185      Json.chain(xs)
186    case _:
187      Nil{}
188
189# Sets key in an object's member chain, replacing the first match or
190# appending at the end.
191def Json.set(j: Json, +key: String, v: Json) -> Json:
192  match j:
193    case JObj{ms}:
194      JObj{Json.put_mem(ms, key, v)}
195    case _:
196      JObj{JMem{key, v, JNil{}}}
197
198def Json.del_mem.if(k: String, x: Json, t: Json, hit: Bool) -> Json:
199  match hit:
200    case True{}:
201      t
202    case False{}:
203      JMem{k, x, t}
204
205# Removes every member named key.
206def Json.del_mem(ms: Json, +key: String) -> Json:
207  match ms:
208    case JMem{+k, x, t}:
209      Json.del_mem.if(k, x, Json.del_mem(t, key), String.eq(k, key))
210    case _:
211      JNil{}
212
213def Json.del(j: Json, +key: String) -> Json:
214  match j:
215    case JObj{ms}:
216      JObj{Json.del_mem(ms, key)}
217    case x:
218      x
219
220def Json.hex.if(+n: U32, lt: Bool) -> Char:
221  match lt:
222    case True{}:
223      Chr{(n + 48 : U32)}
224    case False{}:
225      Chr{(n + 87 : U32)}
226
227# Printing
228# --------
229
230def Json.hex(+n: U32) -> Char:
231  Json.hex.if(n, U32.is_lt(n, 10))
232
233def Json.esc_ctl(+x: U32, rest: String, ctl: Bool) -> String:
234  match ctl:
235    case True{}:
236      "\\u00" ++ SCon{Json.hex((x >> 4n : U32)), SCon{Json.hex((x .&. 15 : U32)), rest}}
237    case False{}:
238      SCon{Chr{x}, rest}
239
240# Escapes one char onto the front of the already-escaped rest.
241def Json.esc_chr(c: Char, rest: String) -> String:
242  match c:
243    case '"':
244      SCon{'\\', SCon{'"', rest}}
245    case '\\':
246      SCon{'\\', SCon{'\\', rest}}
247    case '\n':
248      SCon{'\\', SCon{'n', rest}}
249    case '\r':
250      SCon{'\\', SCon{'r', rest}}
251    case '\t':
252      SCon{'\\', SCon{'t', rest}}
253    case Chr{+x}:
254      Json.esc_ctl(x, rest, U32.is_lt(x, 32))
255
256def Json.esc(s: String) -> String:
257  match s:
258    case SNil{}:
259      SNil{}
260    case SCon{c, t}:
261      Json.esc_chr(c, Json.esc(t))
262
263def Json.quote(s: String) -> String:
264  "\"" ++ Json.esc(s) ++ "\""
265
266# The compact text of a value. Inside a chain, the first element prints
267# bare and the rest follow a comma.
268def Json.show(j: Json) -> String:
269  match j:
270    case JNull{}:
271      "null"
272    case JBool{True{}}:
273      "true"
274    case JBool{False{}}:
275      "false"
276    case JNum{s}:
277      s
278    case JStr{s}:
279      Json.quote(s)
280    case JArr{xs}:
281      "[" ++ Json.show(xs) ++ "]"
282    case JObj{ms}:
283      "{" ++ Json.show(ms) ++ "}"
284    case JNil{}:
285      ""
286    case JCons{h, JNil{}}:
287      Json.show(h)
288    case JCons{h, t}:
289      Json.show(h) ++ "," ++ Json.show(t)
290    case JMem{k, v, JNil{}}:
291      Json.quote(k) ++ ":" ++ Json.show(v)
292    case JMem{k, v, t}:
293      Json.quote(k) ++ ":" ++ Json.show(v) ++ "," ++ Json.show(t)
294
295def Json.parse.init() -> JState:
296  JS{LVal{False{}}, Nil{}}
297
298def Json.rev_pairs(xs: List<&2, KV>, acc: Json) -> Json:
299  match xs:
300    case Nil{}:
301      acc
302    case Con{KV{k, v}, t}:
303      Json.rev_pairs(t, JMem{k, v, acc})
304
305def Json.rev_items(xs: List<&2, Json>, acc: Json) -> Json:
306  match xs:
307    case Nil{}:
308      acc
309    case Con{h, t}:
310      Json.rev_items(t, JCons{h, acc})
311
312# Hands a finished value to the innermost open container, or ends the
313# document when there is none.
314def Json.parse.give(v: Json, stack: List<&2, Frame>) -> JState:
315  match stack:
316    case Nil{}:
317      JS{LDone{v}, Nil{}}
318    case Con{FArr{xs}, t}:
319      JS{LAfter{}, FArr{v <> xs} <> t}
320    case Con{FObj{ms, k}, t}:
321      JS{LAfter{}, FObj{KV{k, v} <> ms, ""} <> t}
322
323def Json.parse.err(msg: String) -> JState:
324  JS{LErr{msg}, Nil{}}
325
326# The value a literal's reversed chars spell.
327def Json.parse.lit(buf: String, stack: List<&2, Frame>) -> JState:
328  match buf:
329    case "eurt":
330      Json.parse.give(JBool{True{}}, stack)
331    case "eslaf":
332      Json.parse.give(JBool{False{}}, stack)
333    case "llun":
334      Json.parse.give(JNull{}, stack)
335    case _:
336      Json.parse.err("bad literal")
337
338def Json.is_num_chr(c: Char) -> Bool:
339  match c:
340    case '-':
341      True{}
342    case '+':
343      True{}
344    case '.':
345      True{}
346    case 'e':
347      True{}
348    case 'E':
349      True{}
350    case Chr{+x}:
351      Bool.and(U32.is_ge(x, 48), U32.is_le(x, 57))
352
353def Json.is_alpha_chr(c: Char) -> Bool:
354  match c:
355    case Chr{+x}:
356      Bool.and(U32.is_ge(x, 97), U32.is_le(x, 122))
357
358def Json.is_ws(c: Char) -> Bool:
359  match c:
360    case ' ':
361      True{}
362    case '\n':
363      True{}
364    case '\r':
365      True{}
366    case '\t':
367      True{}
368    case _:
369      False{}
370
371# Closes the innermost container on ']' or '}'.
372def Json.parse.close(c: Char, stack: List<&2, Frame>) -> JState:
373  match c stack:
374    case ']' Con{FArr{xs}, t}:
375      Json.parse.give(JArr{Json.rev_items(xs, JNil{})}, t)
376    case '}' Con{FObj{ms, k}, t}:
377      Json.parse.give(JObj{Json.rev_pairs(ms, JNil{})}, t)
378    case _ _:
379      Json.parse.err("mismatched closer")
380
381def Json.parse.after.ws(ws: Bool, stack: List<&2, Frame>) -> JState:
382  match ws:
383    case True{}:
384      JS{LAfter{}, stack}
385    case False{}:
386      Json.parse.err("expected , or a closer")
387
388def Json.parse.comma(stack: List<&2, Frame>) -> JState:
389  match stack:
390    case Con{FArr{xs}, t}:
391      JS{LVal{False{}}, FArr{xs} <> t}
392    case Con{FObj{ms, k}, t}:
393      JS{LKey{False{}}, FObj{ms, k} <> t}
394    case Nil{}:
395      Json.parse.err("comma at top level")
396
397# After a value: a comma reopens the container, a closer ends it.
398def Json.parse.after(c: Char, stack: List<&2, Frame>) -> JState:
399  match c:
400    case ',':
401      Json.parse.comma(stack)
402    case ']':
403      Json.parse.close(']', stack)
404    case '}':
405      Json.parse.close('}', stack)
406    case x:
407      Json.parse.after.ws(Json.is_ws(x), stack)
408
409def Json.parse.value.close(open: Bool, stack: List<&2, Frame>) -> JState:
410  match open:
411    case True{}:
412      Json.parse.close(']', stack)
413    case False{}:
414      Json.parse.err("unexpected ]")
415
416def Json.parse.value.other(x: Char, ws: Bool, num: Bool, alpha: Bool, open: Bool,
417  stack: List<&2, Frame>) -> JState:
418  match ws num alpha:
419    case True{} _ _:
420      JS{LVal{open}, stack}
421    case False{} True{} _:
422      JS{LNum{SCon{x, SNil{}}}, stack}
423    case False{} False{} True{}:
424      JS{LLit{SCon{x, SNil{}}}, stack}
425    case _ _ _:
426      Json.parse.err("unexpected char")
427
428# Starts a value with its first char.
429def Json.parse.value(c: Char, open: Bool, stack: List<&2, Frame>) -> JState:
430  match c:
431    case '{':
432      JS{LKey{True{}}, FObj{Nil{}, ""} <> stack}
433    case '[':
434      JS{LVal{True{}}, FArr{Nil{}} <> stack}
435    case '"':
436      JS{LStr{"", False{}, 0, 0}, stack}
437    case ']':
438      Json.parse.value.close(open, stack)
439    case +x:
440      Json.parse.value.other(x, Json.is_ws(x), Json.is_num_chr(x), Json.is_alpha_chr(x), open, stack)
441
442def Json.parse.key.close(open: Bool, stack: List<&2, Frame>) -> JState:
443  match open:
444    case True{}:
445      Json.parse.close('}', stack)
446    case False{}:
447      Json.parse.err("unexpected }")
448
449def Json.parse.key.ws(ws: Bool, open: Bool, stack: List<&2, Frame>) -> JState:
450  match ws:
451    case True{}:
452      JS{LKey{open}, stack}
453    case False{}:
454      Json.parse.err("expected a key")
455
456def Json.parse.key(c: Char, open: Bool, stack: List<&2, Frame>) -> JState:
457  match c:
458    case '"':
459      JS{LStr{"", True{}, 0, 0}, stack}
460    case '}':
461      Json.parse.key.close(open, stack)
462    case x:
463      Json.parse.key.ws(Json.is_ws(x), open, stack)
464
465def Json.parse.colon.ws(ws: Bool, stack: List<&2, Frame>) -> JState:
466  match ws:
467    case True{}:
468      JS{LColon{}, stack}
469    case False{}:
470      Json.parse.err("expected :")
471
472def Json.parse.colon(c: Char, stack: List<&2, Frame>) -> JState:
473  match c:
474    case ':':
475      JS{LVal{False{}}, stack}
476    case x:
477      Json.parse.colon.ws(Json.is_ws(x), stack)
478
479# A finished string: a key waits for its ':', a value is given.
480def Json.parse.str_end(s: String, key: Bool, stack: List<&2, Frame>) -> JState:
481  match key stack:
482    case True{} Con{FObj{ms, k}, t}:
483      JS{LColon{}, FObj{ms, s} <> t}
484    case True{} _:
485      Json.parse.err("key outside an object")
486    case False{} st:
487      Json.parse.give(JStr{s}, st)
488
489def Json.hex_val.go(+x: U32, digit: Bool, lower: Bool, upper: Bool) -> Maybe<&2, U32>:
490  match digit lower upper:
491    case True{} _ _:
492      Some{(x - 48 : U32)}
493    case False{} True{} _:
494      Some{(x - 87 : U32)}
495    case False{} False{} True{}:
496      Some{(x - 55 : U32)}
497    case _ _ _:
498      None{}
499
500def Json.hex_val(c: Char) -> Maybe<&2, U32>:
501  match c:
502    case Chr{+x}:
503      Json.hex_val.go(x, U32.is_le(x, 57), U32.is_ge(x, 97), U32.is_ge(x, 65))
504
505def Json.parse.in_str.plain(c: Char, buf: String, key: Bool, stack: List<&2, Frame>) -> JState:
506  match c:
507    case '"':
508      Json.parse.str_end(String.reverse(buf), key, stack)
509    case '\\':
510      JS{LStr{buf, key, 1, 0}, stack}
511    case x:
512      JS{LStr{SCon{x, buf}, key, 0, 0}, stack}
513
514def Json.parse.in_str.esc(c: Char, buf: String, key: Bool, stack: List<&2, Frame>) -> JState:
515  match c:
516    case 'n':
517      JS{LStr{SCon{'\n', buf}, key, 0, 0}, stack}
518    case 't':
519      JS{LStr{SCon{'\t', buf}, key, 0, 0}, stack}
520    case 'r':
521      JS{LStr{SCon{'\r', buf}, key, 0, 0}, stack}
522    case 'b':
523      JS{LStr{SCon{Chr{8}, buf}, key, 0, 0}, stack}
524    case 'f':
525      JS{LStr{SCon{Chr{12}, buf}, key, 0, 0}, stack}
526    case 'u':
527      JS{LStr{buf, key, 2, 0}, stack}
528    case x:
529      JS{LStr{SCon{x, buf}, key, 0, 0}, stack}
530
531def Json.parse.in_str.hex.fin(+code: U32, buf: String, key: Bool, +esc: U32,
532  stack: List<&2, Frame>, last: Bool) -> JState:
533  match last:
534    case True{}:
535      JS{LStr{SCon{Chr{code}, buf}, key, 0, 0}, stack}
536    case False{}:
537      JS{LStr{buf, key, (esc + 1 : U32), code}, stack}
538
539def Json.parse.in_str.hex.put(+code: U32, buf: String, key: Bool, +esc: U32,
540  stack: List<&2, Frame>) -> JState:
541  Json.parse.in_str.hex.fin(code, buf, key, esc, stack, U32.is_eq(esc, 5))
542
543# \uXXXX: esc counts 2..5 over the four digits. A UTF-16 surrogate pair
544# arrives as two escapes; each half is kept as its own code, which the
545# Kubernetes API never emits for text it validates.
546def Json.parse.in_str.hex(d: Maybe<&2, U32>, buf: String, key: Bool, +esc: U32, code: U32,
547  stack: List<&2, Frame>) -> JState:
548  match d:
549    case None{}:
550      Json.parse.err("bad \\u escape")
551    case Some{v}:
552      Json.parse.in_str.hex.put(((code << 4n) + v : U32), buf, key, esc, stack)
553
554def Json.parse.in_str.go(c: Char, buf: String, key: Bool, +esc: U32, code: U32,
555  stack: List<&2, Frame>, e0: Bool, e1: Bool) -> JState:
556  match e0 e1:
557    case True{} _:
558      Json.parse.in_str.plain(c, buf, key, stack)
559    case False{} True{}:
560      Json.parse.in_str.esc(c, buf, key, stack)
561    case False{} False{}:
562      Json.parse.in_str.hex(Json.hex_val(c), buf, key, esc, code, stack)
563
564# One char inside a string.
565def Json.parse.in_str(c: Char, buf: String, key: Bool, +esc: U32, code: U32,
566  stack: List<&2, Frame>) -> JState:
567  Json.parse.in_str.go(c, buf, key, esc, code, stack, U32.is_eq(esc, 0), U32.is_eq(esc, 1))
568
569def Json.parse.done.if(v: Json, ws: Bool) -> JState:
570  match ws:
571    case True{}:
572      JS{LDone{v}, Nil{}}
573    case False{}:
574      Json.parse.err("trailing data")
575
576def Json.parse.done(c: Char, v: Json) -> JState:
577  Json.parse.done.if(v, Json.is_ws(c))
578
579def Json.parse.resume(c: Char, st: JState) -> JState:
580  match st:
581    case JS{LAfter{}, stack}:
582      Json.parse.after(c, stack)
583    case JS{LDone{v}, stack}:
584      Json.parse.done(c, v)
585    case other:
586      other
587
588def Json.parse.in_num.if(+c: Char, buf: String, stack: List<&2, Frame>, more: Bool) -> JState:
589  match more:
590    case True{}:
591      JS{LNum{SCon{c, buf}}, stack}
592    case False{}:
593      Json.parse.resume(c, Json.parse.give(JNum{String.reverse(buf)}, stack))
594
595# A number or literal ends at the first char that cannot extend it; that
596# char is then read as if after a value.
597def Json.parse.in_num(+c: Char, buf: String, stack: List<&2, Frame>) -> JState:
598  Json.parse.in_num.if(c, buf, stack, Json.is_num_chr(c))
599
600def Json.parse.in_lit.if(+c: Char, buf: String, stack: List<&2, Frame>, more: Bool) -> JState:
601  match more:
602    case True{}:
603      JS{LLit{SCon{c, buf}}, stack}
604    case False{}:
605      Json.parse.resume(c, Json.parse.lit(buf, stack))
606
607def Json.parse.in_lit(+c: Char, buf: String, stack: List<&2, Frame>) -> JState:
608  Json.parse.in_lit.if(c, buf, stack, Json.is_alpha_chr(c))
609
610# One step of the automaton.
611def Json.parse.step(st: JState, c: Char) -> JState:
612  match st:
613    case JS{LVal{open}, stack}:
614      Json.parse.value(c, open, stack)
615    case JS{LAfter{}, stack}:
616      Json.parse.after(c, stack)
617    case JS{LKey{open}, stack}:
618      Json.parse.key(c, open, stack)
619    case JS{LColon{}, stack}:
620      Json.parse.colon(c, stack)
621    case JS{LStr{buf, key, esc, code}, stack}:
622      Json.parse.in_str(c, buf, key, esc, code, stack)
623    case JS{LNum{buf}, stack}:
624      Json.parse.in_num(c, buf, stack)
625    case JS{LLit{buf}, stack}:
626      Json.parse.in_lit(c, buf, stack)
627    case JS{LDone{v}, stack}:
628      Json.parse.done(c, v)
629    case JS{LErr{m}, stack}:
630      JS{LErr{m}, Nil{}}
631
632def Json.parse.feed(s: String, st: JState) -> JState:
633  match s:
634    case SNil{}:
635      st
636    case SCon{c, t}:
637      Json.parse.feed(t, Json.parse.step(st, c))
638
639def Json.parse.result(st: JState) -> Result<&2, &2, String, Json>:
640  match st:
641    case JS{LDone{v}, stack}:
642      Done{v}
643    case JS{LErr{m}, stack}:
644      Fail{m}
645    case _:
646      Fail{"unexpected end of input"}
647
648# Ends the input: a pending number or literal completes, then the document
649# must be whole.
650def Json.parse.finish(st: JState) -> Result<&2, &2, String, Json>:
651  Json.parse.result(Json.parse.step(st, ' '))
652
653def Json.parse(s: String) -> Result<&2, &2, String, Json>:
654  Json.parse.finish(Json.parse.feed(s, Json.parse.init()))