1	import Base
2	import ./json/lex.bend as Lex
3	import ./json/quote.bend as Quote
4	import ./json/scan.bend as Scan
5	
6	# JSON values, a parser and emitters that match Python's json module.
7	#
8	# Arrays and objects are chains inside Json itself (JNil, JCons, JField), not
9	# `List`s: Bend accepts structural recursion over one type only, and a value
10	# nested in a list would need two mutually recursive emitters. A chain keeps
11	# the emitter a single self-recursive def. Json is Data (reusable), which a
12	# `List<(String & Json)>` of pairs could not be. `arr`, `obj`, `to_pairs` and
13	# `of_pairs` convert at the edge.
14	#
15	# Numbers stay their source text, so `90.0` and `1e5` round-trip unchanged.
16	
17	type Json is Data:
18	  JNull{}
19	  JBool{b: Bool}
20	  JNum{text: String}
21	  JStr{s: String}
22	  JArr{items: Json}
23	  JObj{fields: Json}
24	  JNil{}
25	  JCons{head: Json, tail: Json}
26	  JField{key: String, val: Json, tail: Json}
27	
28	# ---- parser ------------------------------------------------------------------
29	
30	type Mode is Data:
31	  MVal{}
32	  MAFirst{}
33	  MANext{}
34	  MAAfter{}
35	  MOFirst{}
36	  MONext{}
37	  MOAfter{}
38	
39	def only(t: List<&2, Lex.Tok>, v: Json) -> Result<&2, &2, String, Json>:
40	  match t:
41	    case Nil{}:
42	      Done{v}
43	    case Con{h, r}:
44	      Fail{"trailing data after the value"}
45	
46	def wrap.arr(ok: Bool, r: Result<&2, &2, String, Json>) -> Result<&2, &2, String, Json>:
47	  match ok r:
48	    case True{} Done{items}:
49	      Done{JArr{items}}
50	    case True{} Fail{e}:
51	      Fail{e}
52	    case False{} _:
53	      Fail{"unclosed array"}
54	
55	def wrap.obj(ok: Bool, r: Result<&2, &2, String, Json>) -> Result<&2, &2, String, Json>:
56	  match ok r:
57	    case True{} Done{fields}:
58	      Done{JObj{fields}}
59	    case True{} Fail{e}:
60	      Fail{e}
61	    case False{} _:
62	      Fail{"unclosed object"}
63	
64	def item.cons(x: Result<&2, &2, String, Json>, rest: Result<&2, &2, String, Json>) -> Result<&2, &2, String, Json>:
65	  match x rest:
66	    case Done{a} Done{b}:
67	      Done{JCons{a, b}}
68	    case Fail{e} _:
69	      Fail{e}
70	    case _ Fail{e}:
71	      Fail{e}
72	
73	def field.cons(k: String, x: Result<&2, &2, String, Json>, rest: Result<&2, &2, String, Json>) -> Result<&2, &2, String, Json>:
74	  match x rest:
75	    case Done{a} Done{b}:
76	      Done{JField{k, a, b}}
77	    case Fail{e} _:
78	      Fail{e}
79	    case _ Fail{e}:
80	      Fail{e}
81	
82	# What one parser step decides, before it recurses: a finished result, a
83	# bracketed body, two parts to parse (array item and rest, object field and
84	# rest), or one more step in another mode. Splitting "decide" from "recurse"
85	# keeps `val` a single self-recursive def (Bend has no mutual recursion) with
86	# few arms.
87	type Plan is Data:
88	  PRes{r: Result<&2, &2, String, Json>}
89	  PArr{t: List<&2, Lex.Tok>}
90	  PObj{t: List<&2, Lex.Tok>}
91	  PItems{first: List<&2, Lex.Tok>, rest: List<&2, Lex.Tok>}
92	  PFields{k: String, vt: List<&2, Lex.Tok>, rest: List<&2, Lex.Tok>}
93	  PNext{mode: Mode, t: List<&2, Lex.Tok>}
94	
95	def plan.val(+toks: List<&2, Lex.Tok>) -> Plan:
96	  match toks:
97	    case Con{Lex.TNull{}, t}:
98	      PRes{only(t, JNull{})}
99	    case Con{Lex.TTrue{}, t}:
100	      PRes{only(t, JBool{True{}})}
101	    case Con{Lex.TFalse{}, t}:
102	      PRes{only(t, JBool{False{}})}
103	    case Con{Lex.TNum{x}, t}:
104	      PRes{only(t, JNum{x})}
105	    case Con{Lex.TStr{x}, t}:
106	      PRes{only(t, JStr{x})}
107	    case Con{Lex.TLBrack{}, +t}:
108	      PArr{t}
109	    case Con{Lex.TLBrace{}, +t}:
110	      PObj{t}
111	    case Nil{}:
112	      PRes{Fail{"unexpected end of input"}}
113	    case _:
114	      PRes{Fail{"unexpected token"}}
115	
116	def plan.items(+toks: List<&2, Lex.Tok>) -> Plan:
117	  match toks:
118	    case Nil{}:
119	      PRes{Fail{"unexpected end of input"}}
120	    case Con{+h, +t}:
121	      PItems{List.take(&2, Lex.Tok, Con{h, t}, Scan.scan(Con{h, t}, 0)), List.drop(&2, Lex.Tok, Con{h, t}, Scan.scan(Con{h, t}, 0))}
122	
123	def plan.arr_first(+toks: List<&2, Lex.Tok>) -> Plan:
124	  match toks:
125	    case Nil{}:
126	      PRes{Done{JNil{}}}
127	    case _:
128	      plan.items(toks)
129	
130	def plan.arr_next(+toks: List<&2, Lex.Tok>) -> Plan:
131	  match toks:
132	    case Nil{}:
133	      PRes{Fail{"trailing comma in array"}}
134	    case _:
135	      plan.items(toks)
136	
137	def plan.arr_after(+toks: List<&2, Lex.Tok>) -> Plan:
138	  match toks:
139	    case Nil{}:
140	      PRes{Done{JNil{}}}
141	    case Con{Lex.TComma{}, t}:
142	      PNext{MANext{}, t}
143	    case _:
144	      PRes{Fail{"expected , or ] in array"}}
145	
146	def plan.field(k: String, +t: List<&2, Lex.Tok>) -> Plan:
147	  PFields{k, List.take(&2, Lex.Tok, t, Scan.scan(t, 0)), List.drop(&2, Lex.Tok, t, Scan.scan(t, 0))}
148	
149	def plan.obj_first(+toks: List<&2, Lex.Tok>) -> Plan:
150	  match toks:
151	    case Nil{}:
152	      PRes{Done{JNil{}}}
153	    case Con{Lex.TStr{k}, Con{Lex.TColon{}, +t}}:
154	      plan.field(k, t)
155	    case _:
156	      PRes{Fail{"expected a string key and :"}}
157	
158	def plan.obj_next(+toks: List<&2, Lex.Tok>) -> Plan:
159	  match toks:
160	    case Nil{}:
161	      PRes{Fail{"trailing comma in object"}}
162	    case Con{Lex.TStr{k}, Con{Lex.TColon{}, +t}}:
163	      plan.field(k, t)
164	    case _:
165	      PRes{Fail{"expected a string key and :"}}
166	
167	def plan.obj_after(+toks: List<&2, Lex.Tok>) -> Plan:
168	  match toks:
169	    case Nil{}:
170	      PRes{Done{JNil{}}}
171	    case Con{Lex.TComma{}, t}:
172	      PNext{MONext{}, t}
173	    case _:
174	      PRes{Fail{"expected , or } in object"}}
175	
176	def plan(mode: Mode, +toks: List<&2, Lex.Tok>) -> Plan:
177	  match mode:
178	    case MVal{}:
179	      plan.val(toks)
180	    case MAFirst{}:
181	      plan.arr_first(toks)
182	    case MANext{}:
183	      plan.arr_next(toks)
184	    case MAAfter{}:
185	      plan.arr_after(toks)
186	    case MOFirst{}:
187	      plan.obj_first(toks)
188	    case MONext{}:
189	      plan.obj_next(toks)
190	    case MOAfter{}:
191	      plan.obj_after(toks)
192	
193	def body(+t: List<&2, Lex.Tok>) -> List<&2, Lex.Tok>:
194	  List.take(&2, Lex.Tok, t, Nat.sub(List.length(&2, Lex.Tok, t), 1n))
195	
196	# One def for values, array items and object fields: `plan` says which step
197	# this is. `fuel` bounds the work (3 * tokens + 5). An item's tokens are those
198	# up to the next comma or closer at depth 0.
199	def val(fuel: Nat, pl: Plan) -> Result<&2, &2, String, Json>:
200	  match fuel pl:
201	    case 0n _:
202	      Fail{"nesting too deep"}
203	    case 1n++p PRes{r}:
204	      r
205	    case 1n++p PArr{+t}:
206	      wrap.arr(Scan.closed_by(t, 22), val(p, plan(MAFirst{}, body(t))))
207	    case 1n++p PObj{+t}:
208	      wrap.obj(Scan.closed_by(t, 21), val(p, plan(MOFirst{}, body(t))))
209	    case 1n++p PItems{f, r}:
210	      item.cons(val(p, plan(MVal{}, f)), val(p, plan(MAAfter{}, r)))
211	    case 1n++p PFields{k, vt, r}:
212	      field.cons(k, val(p, plan(MVal{}, vt)), val(p, plan(MOAfter{}, r)))
213	    case 1n++p PNext{m, t}:
214	      val(p, plan(m, t))
215	
216	def parse.pick(msg: String, r: Result<&2, &2, String, Json>) -> Result<&2, &2, String, Json>:
217	  match msg r:
218	    case SNil{} _:
219	      r
220	    case _ _:
221	      Fail{msg}
222	
223	def parse.toks(+toks: List<&2, Lex.Tok>) -> Result<&2, &2, String, Json>:
224	  parse.pick(Scan.err.of(toks), val(Nat.add(Nat.mul(3n, List.length(&2, Lex.Tok, toks)), 5n), plan(MVal{}, toks)))
225	
226	# Parse JSON text; Fail carries a message.
227	def parse(+s: String) -> Result<&2, &2, String, Json>:
228	  parse.toks(Lex.lex(String.length(s), s))
229	
230	# ---- emitters ----------------------------------------------------------------
231	
232	def sep.of(next: Json, +style: U32, d: Nat) -> String:
233	  match next:
234	    case JNil{}:
235	      ""
236	    case _:
237	      Quote.sep(style, d)
238	
239	def bool.show(b: Bool) -> String:
240	  Lex.sel.s(b, "true", "false")
241	
242	# A bracketed body: `[]` or `{}` when empty, else the body on its own lines.
243	def emit.wrap(open: String, close: String, items: Json, inner: String, +style: U32, +d: Nat) -> String:
244	  match items:
245	    case JNil{}:
246	      open ++ close
247	    case _:
248	      open ++ Quote.nl(style, Nat.add(d, 1n)) ++ inner ++ Quote.nl(style, d) ++ close
249	
250	# The emitter. `j` shrinks on every call; `d` is the nesting depth.
251	def emit.go(j: Json, +style: U32, +ascii: Bool, +d: Nat) -> String:
252	  match j:
253	    case JNull{}:
254	      "null"
255	    case JBool{b}:
256	      bool.show(b)
257	    case JNum{t}:
258	      t
259	    case JStr{s}:
260	      Quote.quote(s, ascii)
261	    case JArr{+items}:
262	      emit.wrap("[", "]", items, emit.go(items, style, ascii, Nat.add(d, 1n)), style, d)
263	    case JObj{+fields}:
264	      emit.wrap("{", "}", fields, emit.go(fields, style, ascii, Nat.add(d, 1n)), style, d)
265	    case JNil{}:
266	      ""
267	    case JCons{h, +t}:
268	      emit.go(h, style, ascii, d) ++ sep.of(t, style, d) ++ emit.go(t, style, ascii, d)
269	    case JField{k, v, +t}:
270	      Quote.quote(k, ascii) ++ Quote.colon(style) ++ emit.go(v, style, ascii, d) ++ sep.of(t, style, d) ++ emit.go(t, style, ascii, d)
271	
272	# Compact, no spaces, UTF-8 left as is.
273	def emit(j: Json) -> String:
274	  emit.go(j, 0, False{}, 0n)
275	
276	# json.dumps(j): `, ` and `: ` separators, ensure_ascii.
277	def emit_py(j: Json) -> String:
278	  emit.go(j, 1, True{}, 0n)
279	
280	# json.dumps(j, indent=2), as the reference writes sequence.json and
281	# settings: ensure_ascii on (the reference never passes ensure_ascii=False
282	# for its own files), no trailing newline.
283	def emit_pretty(j: Json) -> String:
284	  emit.go(j, 2, True{}, 0n)
285	
286	# json.dumps(j, indent=2, ensure_ascii=False).
287	def emit_pretty_utf8(j: Json) -> String:
288	  emit.go(j, 2, False{}, 0n)
289	
290	def field.pick(hit: Bool, v: Json, rest: Maybe<&2, Json>) -> Maybe<&2, Json>:
291	  match hit:
292	    case True{}:
293	      Some{v}
294	    case False{}:
295	      rest
296	
297	# ---- accessors and builders ----------------------------------------------------
298	
299	def field.get(+key: String, fields: Json) -> Maybe<&2, Json>:
300	  match fields:
301	    case JField{k, v, t}:
302	      field.pick(String.eq(k, key), v, field.get(key, t))
303	    case _:
304	      None{}
305	
306	# The value under `key` of an object; None for a missing key or a non-object.
307	def get(key: String, j: Json) -> Maybe<&2, Json>:
308	  match j:
309	    case JObj{fields}:
310	      field.get(key, fields)
311	    case _:
312	      None{}
313	
314	def as_string(j: Json) -> Maybe<&2, String>:
315	  match j:
316	    case JStr{s}:
317	      Some{s}
318	    case _:
319	      None{}
320	
321	def as_bool(j: Json) -> Maybe<&2, Bool>:
322	  match j:
323	    case JBool{b}:
324	      Some{b}
325	    case _:
326	      None{}
327	
328	# A non-negative integer that fits U32; `5.0`, `-1` and `1e3` are None.
329	def as_u32(j: Json) -> Maybe<&2, U32>:
330	  match j:
331	    case JNum{t}:
332	      U32.read(t)
333	    case _:
334	      None{}
335	
336	# Array of the values, in order.
337	def arr.chain(xs: List<&2, Json>) -> Json:
338	  match xs:
339	    case Nil{}:
340	      JNil{}
341	    case Con{h, t}:
342	      JCons{h, arr.chain(t)}
343	
344	def arr(xs: List<&2, Json>) -> Json:
345	  JArr{arr.chain(xs)}
346	
347	# The elements of an array; empty for any other value.
348	def items.list(items: Json) -> List<&2, Json>:
349	  match items:
350	    case JCons{h, t}:
351	      h <> items.list(t)
352	    case _:
353	      []
354	
355	def to_list(j: Json) -> List<&2, Json>:
356	  match j:
357	    case JArr{items}:
358	      items.list(items)
359	    case _:
360	      []
361	
362	def field.of(kv: String & Json, rest: Json) -> Json:
363	  (k, v) = kv
364	  JField{k, v, rest}
365	
366	def obj.chain(kvs: List<(String & Json)>) -> Json:
367	  match kvs:
368	    case Nil{}:
369	      JNil{}
370	    case Con{kv, t}:
371	      field.of(kv, obj.chain(t))
372	
373	# Object from ordered (key, value) pairs.
374	def of_pairs(kvs: List<(String & Json)>) -> Json:
375	  JObj{obj.chain(kvs)}
376	
377	def pairs.list(fields: Json) -> List<(String & Json)>:
378	  match fields:
379	    case JField{k, v, t}:
380	      (k, v) <> pairs.list(t)
381	    case _:
382	      []
383	
384	# The (key, value) pairs of an object, in file order.
385	def to_pairs(j: Json) -> List<(String & Json)>:
386	  match j:
387	    case JObj{fields}:
388	      pairs.list(fields)
389	    case _:
390	      []
391	
392	def keys.list(fields: Json) -> List<&2, String>:
393	  match fields:
394	    case JField{k, v, t}:
395	      k <> keys.list(t)
396	    case _:
397	      []
398	
399	def keys(j: Json) -> List<&2, String>:
400	  match j:
401	    case JObj{fields}:
402	      keys.list(fields)
403	    case _:
404	      []
405	
406	def set.pick(hit: Bool, key: String, val: Json, v: Json, t: Json, rest: Json) -> Json:
407	  match hit:
408	    case True{}:
409	      JField{key, val, t}
410	    case False{}:
411	      JField{key, v, rest}
412	
413	def set.go(+key: String, +val: Json, fields: Json) -> Json:
414	  match fields:
415	    case JField{+k, v, +t}:
416	      set.pick(String.eq(k, key), k, val, v, t, set.go(key, val, t))
417	    case _:
418	      JField{key, val, JNil{}}
419	
420	# Replace the value under `key` in place, or append the field.
421	def set(+key: String, +val: Json, j: Json) -> Json:
422	  match j:
423	    case JObj{fields}:
424	      JObj{set.go(key, val, fields)}
425	    case _:
426	      j
427	
428	def del.pick(hit: Bool, k: String, v: Json, t: Json, rest: Json) -> Json:
429	  match hit:
430	    case True{}:
431	      t
432	    case False{}:
433	      JField{k, v, rest}
434	
435	def del.go(+key: String, fields: Json) -> Json:
436	  match fields:
437	    case JField{+k, v, +t}:
438	      del.pick(String.eq(k, key), k, v, t, del.go(key, t))
439	    case _:
440	      JNil{}
441	
442	# The object without `key`.
443	def del(+key: String, j: Json) -> Json:
444	  match j:
445	    case JObj{fields}:
446	      JObj{del.go(key, fields)}
447	    case _:
448	      j
449	
450	# The value of a parse that must have worked; JNull when it did not. For
451	# tests and constants, not for untrusted text.
452	def unwrap(+r: Result<&2, &2, String, Json>) -> Json:
453	  match r:
454	    case Done{v}:
455	      v
456	    case Fail{e}:
457	      JNull{}