1	import Base
2	import ./json.bend as J
3	import ./head.bend as Hd
4	
5	# Key folding (spec section 13.4, encoder, mode "safe"): a chain of objects
6	# with one key each collapses into a dotted key, `{a: {b: {c: 1}}}` into
7	# `a.b.c: 1`.
8	#
9	# It is a rewrite of the value before encoding. Along objects only (arrays are
10	# leaves of a chain, and objects inside arrays are not folded), a key K1 whose
11	# value is an object with the single key K2, and so on, folds to `K1.K2...Kd`
12	# when every segment matches `^[A-Za-z_][A-Za-z0-9_]*$`, d = min(L, flatten
13	# depth) is at least 2, and the folded key collides with neither a sibling key
14	# nor (at root) a literal dotted root key.
15	
16	# A chain: how many segments, the folded key, the value after the last
17	# segment, and whether every segment is an identifier.
18	type Ci is Data:
19	  Ci{n: U32, key: String, tail: J.Json, ok: Bool}
20	
21	# What to do with one field: the key to write, the value after any folding,
22	# that value's fields, their sibling keys, the budget and the path to carry
23	# into them.
24	type Plan is Data:
25	  Plan{key: String, vt: J.Json, fs2: J.Json, sibs2: List<&2, String>, nb: U32, np: String}
26	
27	def alnum(+c: Char) -> Bool:
28	  Char.is_alpha(c) || Char.is_digit(c) || Char.is_eq(c, '_')
29	
30	def ident_tail(+s: String) -> Bool:
31	  match s:
32	    case SNil{}:
33	      True{}
34	    case SCon{c, t}:
35	      alnum(c) && ident_tail(t)
36	
37	# An IdentifierSegment.
38	def ident(+s: String) -> Bool:
39	  match s:
40	    case SNil{}:
41	      False{}
42	    case SCon{c, t}:
43	      (Char.is_alpha(c) || Char.is_eq(c, '_')) && ident_tail(t)
44	
45	def member(+k: String, +ks: List<&2, String>) -> Bool:
46	  match ks:
47	    case Nil{}:
48	      False{}
49	    case Con{h, t}:
50	      String.eq(k, h) || member(k, t)
51	
52	def keys(+fs: J.Json) -> List<&2, String>:
53	  match fs:
54	    case J.JField{k, v, t}:
55	      Con{k, keys(t)}
56	    case _:
57	      Nil{}
58	
59	def has_dot(+s: String) -> Bool:
60	  match s:
61	    case SNil{}:
62	      False{}
63	    case SCon{c, t}:
64	      Char.is_eq(c, '.') || has_dot(t)
65	
66	def dotted.pick(+hit: Bool, +k: String, +rest: List<&2, String>) -> List<&2, String>:
67	  match hit:
68	    case True{}:
69	      Con{k, rest}
70	    case False{}:
71	      rest
72	
73	# Keys that hold a dot.
74	def dotted(+ks: List<&2, String>) -> List<&2, String>:
75	  match ks:
76	    case Nil{}:
77	      Nil{}
78	    case Con{k, t}:
79	      dotted.pick(has_dot(k), k, dotted(t))
80	
81	# Nodes in a value: the fuel for the fold.
82	def size(+j: J.Json) -> Nat:
83	  match j:
84	    case J.JArr{x}:
85	      1n+size(x)
86	    case J.JObj{x}:
87	      1n+size(x)
88	    case J.JCons{h, t}:
89	      1n+Nat.add(size(h), size(t))
90	    case J.JField{k, v, t}:
91	      1n+Nat.add(size(v), size(t))
92	    case _:
93	      1n
94	
95	def chain.step(+go: Bool, +v: J.Json, +n: U32, +key: String, +ok: Bool, +r: Ci) -> Ci:
96	  match go:
97	    case True{}:
98	      r
99	    case False{}:
100	      Ci{n, key, v, ok}
101	
102	# Walk single-key objects from `v`, at most `budget` segments in all.
103	def chain(+v: J.Json, +n: U32, +budget: U32, +key: String, +ok: Bool) -> Ci:
104	  match v:
105	    case J.JObj{J.JField{k2, v2, J.JNil{}}}:
106	      chain.step(U32.is_lt(n, budget), v, n, key, ok, chain(v2, (n + 1 : U32), budget, key ++ "." ++ k2, ok && ident(k2)))
107	    case _:
108	      Ci{n, key, v, ok}
109	
110	def path(+prefix: String, +key: String) -> String:
111	  match prefix:
112	    case SNil{}:
113	      key
114	    case _:
115	      prefix ++ "." ++ key
116	
117	def ci.n(+c: Ci) -> U32:
118	  match c:
119	    case Ci{n, key, tail, ok}:
120	      n
121	
122	def ci.key(+c: Ci) -> String:
123	  match c:
124	    case Ci{n, key, tail, ok}:
125	      key
126	
127	def ci.tail(+c: Ci) -> J.Json:
128	  match c:
129	    case Ci{n, key, tail, ok}:
130	      tail
131	
132	def ci.ok(+c: Ci) -> Bool:
133	  match c:
134	    case Ci{n, key, tail, ok}:
135	      ok
136	
137	# Does this field fold?
138	def foldable(+c: Ci, +sibs: List<&2, String>, +prefix: String, +rl: List<&2, String>) -> Bool:
139	  U32.is_ge(ci.n(c), 2) && ci.ok(c) && Bool.not(member(ci.key(c), sibs)) && Bool.not(member(path(prefix, ci.key(c)), rl))
140	
141	def pick.s(+b: Bool, +x: String, +y: String) -> String:
142	  match b:
143	    case True{}:
144	      x
145	    case False{}:
146	      y
147	
148	def pick.j(+b: Bool, +x: J.Json, +y: J.Json) -> J.Json:
149	  match b:
150	    case True{}:
151	      x
152	    case False{}:
153	      y
154	
155	def pick.u(+b: Bool, +x: U32, +y: U32) -> U32:
156	  match b:
157	    case True{}:
158	      x
159	    case False{}:
160	      y
161	
162	# The fields of an object value, or none.
163	def fields.of(+v: J.Json) -> J.Json:
164	  match v:
165	    case J.JObj{fs}:
166	      fs
167	    case _:
168	      J.JNil{}
169	
170	# An object value with its folded fields, other values unchanged.
171	def rebuild(+v: J.Json, +inner: J.Json) -> J.Json:
172	  match v:
173	    case J.JObj{fs}:
174	      J.JObj{inner}
175	    case _:
176	      v
177	
178	def plan.go(+c: Ci, +f: Bool, +k: String, +v: J.Json, +budget: U32, +prefix: String) -> Plan:
179	  +nk : String = pick.s(f, ci.key(c), k)
180	  +vt : J.Json = pick.j(f, ci.tail(c), v)
181	  Plan{nk, vt, fields.of(vt), keys(fields.of(vt)), pick.u(f, (budget - ci.n(c) : U32), budget), path(prefix, nk)}
182	
183	def plan(+k: String, +v: J.Json, +sibs: List<&2, String>, +budget: U32, +prefix: String, +rl: List<&2, String>) -> Plan:
184	  +c : Ci = chain(v, 1, budget, k, ident(k))
185	  plan.go(c, foldable(c, sibs, prefix, rl), k, v, budget, prefix)
186	
187	def plan.fs(+pl: Plan) -> J.Json:
188	  match pl:
189	    case Plan{key, vt, fs2, sibs2, nb, np}:
190	      fs2
191	
192	def plan.sibs(+pl: Plan) -> List<&2, String>:
193	  match pl:
194	    case Plan{key, vt, fs2, sibs2, nb, np}:
195	      sibs2
196	
197	def plan.nb(+pl: Plan) -> U32:
198	  match pl:
199	    case Plan{key, vt, fs2, sibs2, nb, np}:
200	      nb
201	
202	def plan.np(+pl: Plan) -> String:
203	  match pl:
204	    case Plan{key, vt, fs2, sibs2, nb, np}:
205	      np
206	
207	# The field with its folded inside, followed by the folded rest.
208	def field.mk(+pl: Plan, +inner: J.Json, +rest: J.Json) -> J.Json:
209	  match pl:
210	    case Plan{key, vt, fs2, sibs2, nb, np}:
211	      J.JField{key, rebuild(vt, inner), rest}
212	
213	# `fs` is a field chain. `budget` is the segments still allowed, `prefix` the
214	# dotted path of the object so far, `rl` the literal dotted keys at root.
215	def foldf(+fuel: Nat, +fs: J.Json, +sibs: List<&2, String>, +budget: U32, +prefix: String, +rl: List<&2, String>) -> J.Json:
216	  match fuel fs:
217	    case 0n _:
218	      fs
219	    case 1n+p J.JField{k, v, t}:
220	      +pl : Plan = plan(k, v, sibs, budget, prefix, rl)
221	      field.mk(pl, foldf(p, plan.fs(pl), plan.sibs(pl), plan.nb(pl), plan.np(pl), rl), foldf(p, t, sibs, budget, prefix, rl))
222	    case 1n+p _:
223	      fs
224	
225	def fold.obj(+j: J.Json, +fs: J.Json, +budget: U32) -> J.Json:
226	  J.JObj{foldf(size(j), fs, keys(fs), budget, SNil{}, dotted(keys(fs)))}
227	
228	def fold.if(+off: Bool, +j: J.Json, +depth: U32) -> J.Json:
229	  match off:
230	    case True{}:
231	      j
232	    case False{}:
233	      match j:
234	        case J.JObj{fs}:
235	          fold.obj(j, fs, depth)
236	        case _:
237	          j
238	
239	# Fold keys of a value with at most `depth` segments per dotted key; a depth
240	# below 2 folds nothing.
241	def fold(+j: J.Json, +depth: U32) -> J.Json:
242	  fold.if(U32.is_lt(depth, 2), j, depth)