src/fold.bend

bend-toon-codec@0.1.0.0 · 242 lines · 35 definitions

1import Base
2import bend-toon-codec@0.1.0.0/src/json.bend as J
3import bend-toon-codec@0.1.0.0/src/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.
18type 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.
24type Plan is Data:
25  Plan{key: String, vt: J.Json, fs2: J.Json, sibs2: List<&2, String>, nb: U32, np: String}
26
27def alnum(+c: Char) -> Bool:
28  Char.is_alpha(c) || Char.is_digit(c) || Char.is_eq(c, '_')
29
30def 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.
38def 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
45def 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
52def 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
59def 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
66def 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.
74def 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.
82def 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
95def 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.
103def 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
110def path(+prefix: String, +key: String) -> String:
111  match prefix:
112    case SNil{}:
113      key
114    case _:
115      prefix ++ "." ++ key
116
117def ci.n(+c: Ci) -> U32:
118  match c:
119    case Ci{n, key, tail, ok}:
120      n
121
122def ci.key(+c: Ci) -> String:
123  match c:
124    case Ci{n, key, tail, ok}:
125      key
126
127def ci.tail(+c: Ci) -> J.Json:
128  match c:
129    case Ci{n, key, tail, ok}:
130      tail
131
132def ci.ok(+c: Ci) -> Bool:
133  match c:
134    case Ci{n, key, tail, ok}:
135      ok
136
137# Does this field fold?
138def 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
141def pick.s(+b: Bool, +x: String, +y: String) -> String:
142  match b:
143    case True{}:
144      x
145    case False{}:
146      y
147
148def 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
155def 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.
163def 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.
171def 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
178def 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
183def 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
187def plan.fs(+pl: Plan) -> J.Json:
188  match pl:
189    case Plan{key, vt, fs2, sibs2, nb, np}:
190      fs2
191
192def plan.sibs(+pl: Plan) -> List<&2, String>:
193  match pl:
194    case Plan{key, vt, fs2, sibs2, nb, np}:
195      sibs2
196
197def plan.nb(+pl: Plan) -> U32:
198  match pl:
199    case Plan{key, vt, fs2, sibs2, nb, np}:
200      nb
201
202def 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.
208def 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.
215def 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
225def 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
228def 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.
241def fold(+j: J.Json, +depth: U32) -> J.Json:
242  fold.if(U32.is_lt(depth, 2), j, depth)