compose.bend
yaml-for-bend@0.1.0.0 · 458 lines · 0 definitions
1# The composer: events to values, through a schema.
2#
3# It reads the events in order with a stack of the collections still open.
4# A scalar is resolved as it arrives; a collection is finished at its end
5# event, where a mapping's keys are checked and merged. An anchored node is
6# kept by name, and an alias is a copy of it. Every alias adds the size of
7# its node to a count, and past a limit the document is refused, so a
8# small text can't expand into a huge tree ("billion laughs").
9#
10# A key may appear once in a mapping; a repeat is an error. Under YAML 1.1,
11# "<<" merges a mapping, or a list of them, into the mapping it's in: the
12# mapping's own keys win, and among merged mappings the earlier wins.
13
14import Base
15
16import yaml-for-bend@0.1.0.0/token.bend as T
17
18import yaml-for-bend@0.1.0.0/parse.bend as P
19
20import yaml-for-bend@0.1.0.0/value.bend as V
21
22import yaml-for-bend@0.1.0.0/core.bend as C
23
24import yaml-for-bend@0.1.0.0/yaml11.bend as Y11
25
26# How scalars resolve: the YAML 1.2 Core schema, or the YAML 1.1 types.
27type Schema is Data:
28 Core{}
29 Yaml11{}
30
31# A finished node, and whether it is the merge key "<<".
32type Item is Data:
33 Item{val: V.Yaml, merge: Bool}
34
35# A collection still open: its anchor and tag, its items so far (newest
36# first; a mapping's alternate keys and values), how many nodes came before
37# it, and where it starts.
38type Open is Data:
39 OSeq{anchor: Maybe<&2, String>, tag: P.Tag, items: List<&2, V.Yaml>, start: Nat, at: T.Mark}
40 OMap{anchor: Maybe<&2, String>, tag: P.Tag, items: List<&2, Item>, start: Nat, at: T.Mark}
41
42# An anchored node and how many nodes it holds.
43type Anchored is Data:
44 Anchored{val: V.Yaml, size: Nat}
45
46# A document and where it starts.
47type Doc is Data:
48 Doc{val: V.Yaml, at: T.Mark}
49
50# The composer: the open collections, the anchors, how many nodes the
51# document has (aliases counted in full), the document's value once it has
52# one, the documents so far (newest first), and where the document started.
53type Co is Data:
54 Co{stack: List<&2, Open>, anchors: Map<&2, Anchored>, count: Nat, root: Maybe<&2, V.Yaml>, docs: List<&2, Doc>, opened: T.Mark}
55
56# Keys in order, and each key's entry, looked up by its canon text.
57type Ord is Data:
58 Ord{index: Map<&2, V.Entry>, order: List<&2, String>}
59
60def when(-A: Type, hit: Bool, yes: Unit -> A, no: Unit -> A) -> A:
61 match hit:
62 case True{}:
63 yes(Unit{})
64 case False{}:
65 no(Unit{})
66
67def content(why: String, at: T.Mark) -> T.Error:
68 T.Error{why, at, T.Content{}}
69
70# Ordered mappings
71# ----------------
72
73def ord.new() -> Ord:
74 Ord{Map.new(&2, V.Entry), []}
75
76def ord.has(o: Ord, +key: V.Yaml) -> Bool:
77 match o:
78 case Ord{index, order}:
79 Pair.snd(Map<&2, V.Entry>, Bool, Map.has(&2, V.Entry, index, V.canon(key)))
80
81def ord.put.at(hm: Map<&2, V.Entry> & Bool, +order: List<&2, String>, +c: String, key: V.Yaml, val: V.Yaml) -> Ord:
82 (m, has) = hm
83 Ord{Map.set(&2, V.Entry, m, c, V.Entry{key, val}), Bool.pick(List<&2, String>, has, order, c <> order)}
84
85# Puts +key+'s value: in its place when it's there, else at the end.
86def ord.put(o: Ord, +key: V.Yaml, val: V.Yaml) -> Ord:
87 match o:
88 case Ord{index, order}:
89 +c = V.canon(key)
90 ord.put.at(Map.has(&2, V.Entry, index, c), order, c, key, val)
91
92# Each entry put in turn.
93def ord.merge(es: List<&2, V.Entry>, o: Ord) -> Ord:
94 match es:
95 case Nil{}:
96 o
97 case Con{e, rest}:
98 match e:
99 case V.Entry{k, v}:
100 ord.merge(rest, ord.put(o, k, v))
101
102# The entries whose keys aren't there yet.
103def ord.fill(es: List<&2, V.Entry>, +o: Ord) -> Ord:
104 match es:
105 case Nil{}:
106 o
107 case Con{e, rest}:
108 match e:
109 case V.Entry{+k, v}:
110 ord.fill(rest, Bool.pick(Ord, ord.has(o, k), o, ord.put(o, k, v)))
111
112def ord.list(order: List<&2, String>, +m: Map<&2, V.Entry>) -> List<&2, V.Entry>:
113 match order:
114 case Nil{}:
115 []
116 case Con{c, rest}:
117 Pair.snd(Map<&2, V.Entry>, V.Entry, Map.get(V.Entry, V.Entry{V.Null{}, V.Null{}}, m, c)) <> ord.list(rest, m)
118
119def ord.entries(o: Ord) -> List<&2, V.Entry>:
120 match o:
121 case Ord{index, order}:
122 ord.list(List.reverse(&2, String, order), index)
123
124# Mappings
125# --------
126
127def key.text(v: V.Yaml) -> String:
128 match v:
129 case V.Str{t}:
130 t
131 case _:
132 V.canon(v)
133
134def item.val(i: Item) -> V.Yaml:
135 match i:
136 case Item{v, m}:
137 v
138
139def item.merge(i: Item) -> Bool:
140 match i:
141 case Item{v, m}:
142 m
143
144# A list of mappings merged, the earlier winning.
145def merge.list(xs: List<&2, V.Yaml>, +o: Ord) -> Result<&2, &2, String, Ord>:
146 match xs:
147 case Nil{}:
148 Done{o}
149 case Con{x, rest}:
150 match x:
151 case V.Mapping{es}:
152 merge.list(rest, ord.fill(es, o))
153 case _:
154 Fail{"found a merge value that isn't a mapping or a list of mappings"}
155
156# What a "<<" brings in: a mapping's entries, or each of a list's.
157def merge.value(v: V.Yaml, +o: Ord) -> Result<&2, &2, String, Ord>:
158 match v:
159 case V.Mapping{es}:
160 Done{ord.fill(es, o)}
161 case V.Seq{xs}:
162 merge.list(xs, o)
163 case _:
164 Fail{"found a merge value that isn't a mapping or a list of mappings"}
165
166def merge.step(r: Result<&2, &2, String, Ord>, +k: Item, v: Item, +seen: Bool) -> Result<&2, &2, String, Ord>:
167 match r:
168 case Fail{e}:
169 Fail{e}
170 case Done{+o}:
171 when(Result<&2, &2, String, Ord>, Bool.and(item.merge(k), seen), u => Fail{"found a duplicate key: <<"},
172 u => when(Result<&2, &2, String, Ord>, item.merge(k), u => merge.value(item.val(v), o), u => Done{o}))
173
174# The merged entries, from the mapping's "<<" (it may have one).
175def merges(items: List<&2, Item>, r: Result<&2, &2, String, Ord>, +seen: Bool) -> Result<&2, &2, String, Ord>:
176 match items:
177 case Nil{}:
178 r
179 case Con{+k, more}:
180 match more:
181 case Nil{}:
182 r
183 case Con{v, rest}:
184 merges(rest, merge.step(r, k, v, seen), Bool.or(seen, item.merge(k)))
185
186def own.step(r: Result<&2, &2, String, Ord>, +k: Item, v: Item) -> Result<&2, &2, String, Ord>:
187 match r:
188 case Fail{e}:
189 Fail{e}
190 case Done{+o}:
191 +key = item.val(k)
192 when(Result<&2, &2, String, Ord>, item.merge(k), u => Done{o},
193 u => when(Result<&2, &2, String, Ord>, ord.has(o, key), u => Fail{"found a duplicate key: " ++ key.text(key)},
194 u => Done{ord.put(o, key, item.val(v))}))
195
196# The mapping's own entries, each key once.
197def owns(items: List<&2, Item>, r: Result<&2, &2, String, Ord>) -> Result<&2, &2, String, Ord>:
198 match items:
199 case Nil{}:
200 r
201 case Con{k, more}:
202 match more:
203 case Nil{}:
204 r
205 case Con{v, rest}:
206 owns(rest, own.step(r, k, v))
207
208def joined(merged: Result<&2, &2, String, Ord>, own: Result<&2, &2, String, Ord>) -> Result<&2, &2, String, V.Yaml>:
209 match merged:
210 case Fail{e}:
211 Fail{e}
212 case Done{m}:
213 match own:
214 case Fail{e}:
215 Fail{e}
216 case Done{o}:
217 Done{V.Mapping{ord.entries(ord.merge(ord.entries(o), m))}}
218
219# A mapping from its keys and values, oldest first: merged entries first,
220# then its own, which replace any merged ones with the same key.
221def map.value(+items: List<&2, Item>) -> Result<&2, &2, String, V.Yaml>:
222 joined(merges(items, Done{ord.new()}, False{}), owns(items, Done{ord.new()}))
223
224# Scalars and collections
225# -----------------------
226
227def is_plain(s: T.Style) -> Bool:
228 match s:
229 case T.Plain{}:
230 True{}
231 case _:
232 False{}
233
234def scalar.value(s: Schema, t: P.Tag, +text: String, +plain: Bool) -> Result<&2, &2, String, V.Yaml>:
235 match s:
236 case Core{}:
237 match t:
238 case P.NoTag{}:
239 Done{when(V.Yaml, plain, u => C.plain(text), u => V.Str{text})}
240 case P.Tag{n}:
241 C.tagged(n, text)
242 case Yaml11{}:
243 match t:
244 case P.NoTag{}:
245 Done{when(V.Yaml, plain, u => Y11.plain(text), u => V.Str{text})}
246 case P.Tag{n}:
247 Y11.tagged(n, text)
248
249# Whether a scalar is YAML 1.1's merge key: "<<" plain, or tagged !!merge.
250def is_merge(s: Schema, t: P.Tag, +text: String, +plain: Bool) -> Bool:
251 match s:
252 case Core{}:
253 False{}
254 case Yaml11{}:
255 match t:
256 case P.NoTag{}:
257 Bool.and(plain, String.eq(text, "<<"))
258 case P.Tag{n}:
259 String.eq(n, C.yaml.tag("merge"))
260
261def collection(t: P.Tag, v: V.Yaml) -> V.Yaml:
262 match t:
263 case P.NoTag{}:
264 v
265 case P.Tag{n}:
266 C.collection(n, v)
267
268# The composer's steps
269# --------------------
270
271def co.count(co: Co) -> Nat:
272 match co:
273 case Co{stack, anchors, count, root, docs, opened}:
274 count
275
276def co.docs(co: Co) -> List<&2, Doc>:
277 match co:
278 case Co{stack, anchors, count, root, docs, opened}:
279 docs
280
281# A finished node goes to the collection it's in, or is the document.
282def attach(co: Co, item: Item) -> Co:
283 match co:
284 case Co{stack, anchors, count, root, docs, opened}:
285 match stack:
286 case Nil{}:
287 Co{[], anchors, count, Some{item.val(item)}, docs, opened}
288 case Con{top, rest}:
289 match top:
290 case OSeq{anchor, tag, items, start, at}:
291 Co{OSeq{anchor, tag, item.val(item) <> items, start, at} <> rest, anchors, count, root, docs, opened}
292 case OMap{anchor, tag, items, start, at}:
293 Co{OMap{anchor, tag, item <> items, start, at} <> rest, anchors, count, root, docs, opened}
294
295def name.anchor(m: Map<&2, Anchored>, anchor: Maybe<&2, String>, v: V.Yaml, size: Nat) -> Map<&2, Anchored>:
296 match anchor:
297 case None{}:
298 m
299 case Some{n}:
300 Map.set(&2, Anchored, m, n, Anchored{v, size})
301
302# A node of +size+ nodes is finished: its anchor names it, and the count
303# grows by +more+ (the nodes not counted yet: a collection's items were).
304def finish(co: Co, anchor: Maybe<&2, String>, +item: Item, +size: Nat, more: Nat) -> Co:
305 match co:
306 case Co{stack, anchors, count, root, docs, opened}:
307 attach(Co{stack, name.anchor(anchors, anchor, item.val(item), size), Nat.add(count, more), root, docs, opened}, item)
308
309def co.push(co: Co, o: Open) -> Co:
310 match co:
311 case Co{stack, anchors, count, root, docs, opened}:
312 Co{o <> stack, anchors, count, root, docs, opened}
313
314def node.done(r: Result<&2, &2, String, V.Yaml>, co: Co, anchor: Maybe<&2, String>, +merge: Bool, +size: Nat, more: Nat, at: T.Mark) -> Result<&2, &2, T.Error, Co>:
315 match r:
316 case Fail{why}:
317 Fail{content(why, at)}
318 case Done{v}:
319 Done{finish(co, anchor, Item{v, merge}, size, more)}
320
321def is_name(m: Maybe<&2, String>, +name: String) -> Bool:
322 match m:
323 case None{}:
324 False{}
325 case Some{n}:
326 String.eq(n, name)
327
328# Whether a collection still open has the anchor +name+.
329def opens(stack: List<&2, Open>, +name: String) -> Bool:
330 match stack:
331 case Nil{}:
332 False{}
333 case Con{o, rest}:
334 match o:
335 case OSeq{anchor, tag, items, start, at}:
336 Bool.or(is_name(anchor, name), opens(rest, name))
337 case OMap{anchor, tag, items, start, at}:
338 Bool.or(is_name(anchor, name), opens(rest, name))
339
340def found(hm: Map<&2, Anchored> & Bool) -> Bool:
341 Pair.snd(Map<&2, Anchored>, Bool, hm)
342
343def alias.got(ma: Map<&2, Anchored> & Anchored, +co: Co, +limit: Nat, at: T.Mark) -> Result<&2, &2, T.Error, Co>:
344 (m, a) = ma
345 match a:
346 case Anchored{v, +size}:
347 when(Result<&2, &2, T.Error, Co>, Nat.is_gt(Nat.add(co.count(co), size), limit),
348 u => Fail{content("found more than " ++ Nat.show(limit) ++ " nodes through aliases", at)},
349 u => Done{finish(co, None{}, Item{v, False{}}, size, size)})
350
351# An alias: a copy of its node, counted at the node's full size. An alias
352# inside the node it names would make a cycle, which a tree can't hold.
353def co.alias(co: Co, +name: String, +limit: Nat, +at: T.Mark) -> Result<&2, &2, T.Error, Co>:
354 match co:
355 case Co{+stack, +anchors, count, root, docs, opened}:
356 when(Result<&2, &2, T.Error, Co>, opens(stack, name),
357 u => Fail{content("found an alias to a node that holds it: " ++ name ++ " is recursive, and a tree can't hold a cycle", at)},
358 u => when(Result<&2, &2, T.Error, Co>, Bool.not(found(Map.has(&2, Anchored, anchors, name))),
359 u => Fail{content("found an alias to an unknown anchor: " ++ name, at)},
360 u => alias.got(Map.get(Anchored, Anchored{V.Null{}, 0n}, anchors, name), Co{stack, anchors, count, root, docs, opened}, limit, at)))
361
362def co.doc.start(co: Co, at: T.Mark) -> Co:
363 match co:
364 case Co{stack, anchors, count, root, docs, opened}:
365 Co{[], Map.new(&2, Anchored), 0n, None{}, docs, at}
366
367def co.doc.end(co: Co) -> Co:
368 match co:
369 case Co{stack, anchors, count, root, docs, +opened}:
370 Co{stack, anchors, count, None{}, Doc{Maybe.default(&2, V.Yaml, root, V.Null{}), opened} <> docs, opened}
371
372def map.tagged(r: Result<&2, &2, String, V.Yaml>, t: P.Tag) -> Result<&2, &2, String, V.Yaml>:
373 match r:
374 case Fail{e}:
375 Fail{e}
376 case Done{v}:
377 Done{collection(t, v)}
378
379# The collection on top ends.
380def co.close(co: Co) -> Result<&2, &2, T.Error, Co>:
381 match co:
382 case Co{stack, anchors, +count, root, docs, opened}:
383 match stack:
384 case Nil{}:
385 Fail{content("found the end of a collection that never started", T.Mark{0n, 0n, 0n})}
386 case Con{top, rest}:
387 match top:
388 case OSeq{anchor, tag, items, start, +at}:
389 node.done(Done{collection(tag, V.Seq{List.reverse(&2, V.Yaml, items)})}, Co{rest, anchors, count, root, docs, opened}, anchor, False{}, 1n+Nat.sub(count, start), 1n, at)
390 case OMap{anchor, tag, items, start, +at}:
391 node.done(map.tagged(map.value(List.reverse(&2, Item, items)), tag), Co{rest, anchors, count, root, docs, opened}, anchor, False{}, 1n+Nat.sub(count, start), 1n, at)
392
393def co.step(e: P.Evt, +co: Co, +s: Schema, +limit: Nat) -> Result<&2, &2, T.Error, Co>:
394 match e:
395 case P.Evt{ev, +at}:
396 match ev:
397 case P.StreamStartEv{}:
398 Done{co}
399 case P.StreamEndEv{}:
400 Done{co}
401 case P.DocStartEv{explicit}:
402 Done{co.doc.start(co, at)}
403 case P.DocEndEv{explicit}:
404 Done{co.doc.end(co)}
405 case P.AliasEv{name}:
406 co.alias(co, name, limit, at)
407 case P.ScalarEv{anchor, +tag, +text, style}:
408 +plain = is_plain(style)
409 node.done(scalar.value(s, tag, text, plain), co, anchor, is_merge(s, tag, text, plain), 1n, 1n, at)
410 case P.SeqStartEv{anchor, tag, flow}:
411 Done{co.push(co, OSeq{anchor, tag, [], co.count(co), at})}
412 case P.SeqEndEv{}:
413 co.close(co)
414 case P.MapStartEv{anchor, tag, flow}:
415 Done{co.push(co, OMap{anchor, tag, [], co.count(co), at})}
416 case P.MapEndEv{}:
417 co.close(co)
418
419def co.run(evs: List<&2, P.Evt>, +s: Schema, +limit: Nat, r: Result<&2, &2, T.Error, Co>) -> Result<&2, &2, T.Error, Co>:
420 match evs:
421 case Nil{}:
422 r
423 case Con{e, rest}:
424 match r:
425 case Fail{err}:
426 Fail{err}
427 case Done{+co}:
428 co.run(rest, s, limit, co.step(e, co, s, limit))
429
430# How many nodes aliases may make a document: past this, it's refused.
431def alias.limit() -> Nat:
432 100000n
433
434def co.new() -> Co:
435 Co{[], Map.new(&2, Anchored), 0n, None{}, [], T.Mark{0n, 0n, 0n}}
436
437def composed.ok(r: Result<&2, &2, T.Error, Co>) -> Result<&2, &2, T.Error, List<&2, Doc>>:
438 match r:
439 case Fail{e}:
440 Fail{e}
441 case Done{co}:
442 Done{List.reverse(&2, Doc, co.docs(co))}
443
444# A text that isn't YAML is a syntax error, before anything its values do
445# wrong.
446def composed(r: Result<&2, &2, T.Error, Co>, error: Maybe<&2, T.Error>) -> Result<&2, &2, T.Error, List<&2, Doc>>:
447 match error:
448 case None{}:
449 composed.ok(r)
450 case Some{e}:
451 Fail{e}
452
453# The documents the events hold, through schema +s+, with aliases making at
454# most +limit+ nodes in a document.
455def compose.limited(p: P.Parsed, +s: Schema, +limit: Nat) -> Result<&2, &2, T.Error, List<&2, Doc>>:
456 match p:
457 case P.Parsed{events, error}:
458 composed(co.run(events, s, limit, Done{co.new()}), error)