compose.bend

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