parse.bend

yaml-for-bend@0.1.1.0 · 779 lines · 100 definitions

1# The parser: tokens to events.
2#
3# It follows libyaml's parser: a state machine with a stack of the states to
4# return to. Each step looks at the next token and may take it and may emit
5# an event. Where libyaml looks at two tokens in one call, this parser takes
6# two steps, with a state in between, so a step never looks past one token.
7# Where YAML 1.2 and libyaml disagree, it reads YAML 1.2: ": value" with no
8# key has an empty key, a flow mapping's key may end on an earlier line
9# than its ":", a stream may start with "...", and a bare document may
10# follow "...".
11
12import Base
13
14import yaml-for-bend@0.1.1.0/token.bend as T
15
16import yaml-for-bend@0.1.1.0/scan.bend as S
17
18# A node's tag, resolved: none, or its full name ("!" when non-specific).
19type Tag is Data:
20  NoTag{}
21  Tag{name: String}
22
23# An event, as libyaml's are.
24type Ev is Data:
25  StreamStartEv{}
26  StreamEndEv{}
27  DocStartEv{explicit: Bool}
28  DocEndEv{explicit: Bool}
29  AliasEv{name: String}
30  ScalarEv{anchor: Maybe<&2, String>, tag: Tag, text: String, style: T.Style}
31  SeqStartEv{anchor: Maybe<&2, String>, tag: Tag, flow: Bool}
32  SeqEndEv{}
33  MapStartEv{anchor: Maybe<&2, String>, tag: Tag, flow: Bool}
34  MapEndEv{}
35
36# An event and where its node starts.
37type Evt is Data:
38  Evt{ev: Ev, at: T.Mark}
39
40# A tag as written: its handle and suffix.
41type Written is Data:
42  Written{handle: String, suffix: String}
43
44# A %TAG directive: a handle and the prefix it stands for.
45type Prefix is Data:
46  Prefix{handle: String, prefix: String}
47
48# The parser's states. A collection's state keeps where it started, for
49# errors; "After" states have just taken an indicator and keep where it
50# ended, where an empty node would be.
51type St is Data:
52  SStreamStart{}
53  SFirstDoc{}
54  SDocStart{ended: Bool}
55  SDocContent{}
56  SDocEnd{}
57  SNode{block: Bool, indentless: Bool, anchor: Maybe<&2, String>, tag: Maybe<&2, Written>, start: Maybe<&2, T.Mark>}
58  SBSeqFirst{}
59  SBSeqEntry{m: T.Mark}
60  SBSeqAfter{m: T.Mark, e: T.Mark}
61  SIndentless{m: T.Mark}
62  SIndentlessAfter{m: T.Mark, e: T.Mark}
63  SBMapFirst{}
64  SBMapKey{m: T.Mark}
65  SBMapAfterKey{m: T.Mark, e: T.Mark}
66  SBMapValue{m: T.Mark}
67  SBMapAfterValue{m: T.Mark, e: T.Mark}
68  SFSeqFirst{}
69  SFSeqEntry{m: T.Mark, first: Bool}
70  SFSeqMapKey{m: T.Mark}
71  SFSeqMapValue{m: T.Mark}
72  SFSeqMapAfterValue{m: T.Mark, e: T.Mark}
73  SFSeqMapEnd{m: T.Mark}
74  SFMapFirst{}
75  SFMapKey{m: T.Mark, first: Bool}
76  SFMapAfterKey{m: T.Mark, e: T.Mark}
77  SFMapValue{m: T.Mark}
78  SFMapAfterValue{m: T.Mark, e: T.Mark}
79  SFMapEmpty{m: T.Mark}
80  SEnd{}
81
82# The parser: the tokens left, the state, the states to return to, the
83# document's tag prefixes, and the events so far (newest first).
84type Ps is Data:
85  Ps{toks: List<&2, T.Token>, state: St, states: List<&2, St>, tags: List<&2, Prefix>, out: List<&2, Evt>}
86
87type PStep is Data:
88  PGo{ps: Ps}
89  PStop{ps: Ps, error: Maybe<&2, T.Error>}
90
91# The events, and the error that ended them early, if one did.
92type Parsed is Data:
93  Parsed{events: List<&2, Evt>, error: Maybe<&2, T.Error>}
94
95# Directives
96# ----------
97
98# The directives before a document: its %TAG prefixes (over the defaults),
99# checking that %YAML comes at most once and is 1.x and that no handle
100# repeats.
101type Dirs is Data:
102  Dirs{toks: List<&2, T.Token>, tags: List<&2, Prefix>}
103  DirsBad{error: T.Error}
104
105def when(-A: Type, hit: Bool, yes: Unit -> A, no: Unit -> A) -> A:
106  match hit:
107    case True{}:
108      yes(Unit{})
109    case False{}:
110      no(Unit{})
111
112# The parser's state
113# ------------------
114
115def ps.out(ps: Ps) -> List<&2, Evt>:
116  match ps:
117    case Ps{toks, state, states, tags, out}:
118      out
119
120def ps.tags(ps: Ps) -> List<&2, Prefix>:
121  match ps:
122    case Ps{toks, state, states, tags, out}:
123      tags
124
125def ps.state(ps: Ps) -> St:
126  match ps:
127    case Ps{toks, state, states, tags, out}:
128      state
129
130# Takes the next token.
131def take(ps: Ps) -> Ps:
132  match ps:
133    case Ps{toks, state, states, tags, out}:
134      Ps{List.drop(&2, T.Token, toks, 1n), state, states, tags, out}
135
136def emit(ps: Ps, ev: Ev, at: T.Mark) -> Ps:
137  match ps:
138    case Ps{toks, state, states, tags, out}:
139      Ps{toks, state, states, tags, Evt{ev, at} <> out}
140
141def goto(ps: Ps, s: St) -> Ps:
142  match ps:
143    case Ps{toks, state, states, tags, out}:
144      Ps{toks, s, states, tags, out}
145
146def push(ps: Ps, s: St) -> Ps:
147  match ps:
148    case Ps{toks, state, states, tags, out}:
149      Ps{toks, state, s <> states, tags, out}
150
151# Returns to the state on the stack.
152def pop(ps: Ps) -> Ps:
153  match ps:
154    case Ps{toks, state, states, tags, out}:
155      match states:
156        case Nil{}:
157          Ps{toks, SEnd{}, [], tags, out}
158        case Con{s, rest}:
159          Ps{toks, s, rest, tags, out}
160
161def with.tags(ps: Ps, ts: List<&2, Prefix>) -> Ps:
162  match ps:
163    case Ps{toks, state, states, tags, out}:
164      Ps{toks, state, states, ts, out}
165
166def fail(ps: Ps, why: String, at: T.Mark) -> PStep:
167  PStop{ps, Some{T.Error{why, at, T.Syntax{}}}}
168
169def empty(ps: Ps, at: T.Mark) -> Ps:
170  emit(ps, ScalarEv{None{}, NoTag{}, "", T.Plain{}}, at)
171
172# Tokens
173# ------
174
175def tok.kind(t: T.Token) -> T.Tok:
176  match t:
177    case T.Token{tok, start, end}:
178      tok
179
180def tok.start(t: T.Token) -> T.Mark:
181  match t:
182    case T.Token{tok, start, end}:
183      start
184
185def tok.end(t: T.Token) -> T.Mark:
186  match t:
187    case T.Token{tok, start, end}:
188      end
189
190# A token's kind as a number, to test it against a few.
191def kind.index(t: T.Tok) -> Nat:
192  match t:
193    case T.StreamStart{}:
194      0n
195    case T.StreamEnd{}:
196      1n
197    case T.VersionDir{a, b}:
198      2n
199    case T.TagDir{h, p}:
200      3n
201    case T.DocStart{}:
202      4n
203    case T.DocEnd{}:
204      5n
205    case T.BSeqStart{}:
206      6n
207    case T.BMapStart{}:
208      7n
209    case T.BEnd{}:
210      8n
211    case T.FSeqStart{}:
212      9n
213    case T.FSeqEnd{}:
214      10n
215    case T.FMapStart{}:
216      11n
217    case T.FMapEnd{}:
218      12n
219    case T.BEntry{}:
220      13n
221    case T.FEntry{}:
222      14n
223    case T.KeyTok{}:
224      15n
225    case T.ValueTok{}:
226      16n
227    case T.AliasTok{n}:
228      17n
229    case T.AnchorTok{n}:
230      18n
231    case T.TagTok{h, s}:
232      19n
233    case T.ScalarTok{t, s}:
234      20n
235    case T.Broken{e}:
236      21n
237
238def tok.is(+t: T.Token, k: Nat) -> Bool:
239  Nat.is_eq(kind.index(tok.kind(t)), k)
240
241def tok.any(+t: T.Token, ks: List<&2, Nat>) -> Bool:
242  List.contains(~Nat, ~Nat.is_eq, ks, kind.index(tok.kind(t)))
243
244def STREAM_END() -> Nat:
245  1n
246
247def VERSION() -> Nat:
248  2n
249
250def TAG_DIR() -> Nat:
251  3n
252
253def DOC_START() -> Nat:
254  4n
255
256def DOC_END() -> Nat:
257  5n
258
259def BEND() -> Nat:
260  8n
261
262def FSEQ_END() -> Nat:
263  10n
264
265def FMAP_END() -> Nat:
266  12n
267
268def BENTRY() -> Nat:
269  13n
270
271def FENTRY() -> Nat:
272  14n
273
274def KEY() -> Nat:
275  15n
276
277def VALUE() -> Nat:
278  16n
279
280# Tags
281# ----
282
283def defaults() -> List<&2, Prefix>:
284  [Prefix{"!", "!"}, Prefix{"!!", "tag:yaml.org,2002:"}]
285
286def prefix.find(ts: List<&2, Prefix>, +handle: String) -> Maybe<&2, String>:
287  match ts:
288    case Nil{}:
289      None{}
290    case Con{p, rest}:
291      match p:
292        case Prefix{h, +prefix}:
293          when(Maybe<&2, String>, String.eq(h, handle), u => Some{prefix}, u => prefix.find(rest, handle))
294
295def tag.found(m: Maybe<&2, String>, suffix: String, at: T.Mark) -> Result<&2, &2, T.Error, Tag>:
296  match m:
297    case None{}:
298      Fail{T.Error{"found undefined tag handle while parsing a node", at, T.Syntax{}}}
299    case Some{p}:
300      Done{Tag{p ++ suffix}}
301
302# A written tag's full name, through the document's %TAG prefixes.
303def tag.resolve(w: Maybe<&2, Written>, ts: List<&2, Prefix>, at: T.Mark) -> Result<&2, &2, T.Error, Tag>:
304  match w:
305    case None{}:
306      Done{NoTag{}}
307    case Some{x}:
308      match x:
309        case Written{+handle, +suffix}:
310          when(Result<&2, &2, T.Error, Tag>, String.is_empty(handle), u => Done{Tag{suffix}},
311            u => tag.found(prefix.find(ts, handle), suffix, at))
312
313def is_found(m: Maybe<&2, String>) -> Bool:
314  match m:
315    case None{}:
316      False{}
317    case Some{x}:
318      True{}
319
320def dirs.go(toks: List<&2, T.Token>, +user: List<&2, Prefix>, +seen: Bool) -> Dirs:
321  match toks:
322    case Nil{}:
323      Dirs{[], user}
324    case Con{t, +rest}:
325      match t:
326        case T.Token{tok, +start, +end}:
327          match tok:
328            case T.VersionDir{+major, minor}:
329              +bad = Bool.not(Nat.is_eq(major, 1n))
330              when(Dirs, seen, u => DirsBad{T.Error{"found duplicate %YAML directive", start, T.Syntax{}}},
331                u => when(Dirs, bad, u => DirsBad{T.Error{"found incompatible YAML document", start, T.Syntax{}}},
332                  u => dirs.go(rest, user, True{})))
333            case T.TagDir{+h, p}:
334              when(Dirs, is_found(prefix.find(user, h)), u => DirsBad{T.Error{"found duplicate %TAG directive", start, T.Syntax{}}},
335                u => dirs.go(rest, Prefix{h, p} <> user, seen))
336            case _:
337              Dirs{Con{T.Token{tok, start, end}, rest}, user}
338
339def toks.with(ps: Ps, ts: List<&2, T.Token>) -> Ps:
340  match ps:
341    case Ps{toks, state, states, tags, out}:
342      Ps{ts, state, states, tags, out}
343
344def ps.toks(ps: Ps) -> List<&2, T.Token>:
345  match ps:
346    case Ps{toks, state, states, tags, out}:
347      toks
348
349def head.is(ts: List<&2, T.Token>, k: Nat) -> Bool:
350  match ts:
351    case Nil{}:
352      False{}
353    case Con{+t, rest}:
354      tok.is(t, k)
355
356def head.start(ts: List<&2, T.Token>) -> T.Mark:
357  match ts:
358    case Nil{}:
359      T.Mark{0n, 0n, 0n}
360    case Con{t, rest}:
361      tok.start(t)
362
363# After the directives, "---" must start the document.
364def dirs.done(d: Dirs, +ps: Ps) -> PStep:
365  match d:
366    case DirsBad{e}:
367      PStop{ps, Some{e}}
368    case Dirs{+toks, user}:
369      when(PStep, head.is(toks, DOC_START()),
370        u => PGo{goto(push(emit(take(with.tags(toks.with(ps, toks), List.append(&2, Prefix, user, defaults()))), DocStartEv{True{}}, head.start(toks)), SDocEnd{}), SDocContent{})},
371        u => fail(ps, "did not find expected <document start>", head.start(toks)))
372
373def block.node() -> St:
374  SNode{True{}, False{}, None{}, None{}, None{}}
375
376# A document starts: bare, when nothing came before or the last one ended
377# with "..."; or with directives and "---"; or the stream ends.
378def h.doc.start(+ended: Bool, +t: T.Token, +ps: Ps) -> PStep:
379  +start = tok.start(t)
380  +bare = Bool.not(tok.any(t, [VERSION(), TAG_DIR(), DOC_START(), STREAM_END()]))
381  when(PStep, tok.is(t, DOC_END()), u => PGo{take(ps)},
382    u => when(PStep, tok.is(t, STREAM_END()), u => PGo{goto(emit(take(ps), StreamEndEv{}, start), SEnd{})},
383      u => when(PStep, Bool.and(bare, ended), u => PGo{goto(push(emit(with.tags(ps, defaults()), DocStartEv{False{}}, start), SDocEnd{}), block.node())},
384        u => when(PStep, Bool.or(bare, Bool.and(Bool.not(ended), Bool.not(tok.is(t, DOC_START())))), u => fail(ps, "did not find expected <document start>", start),
385          u => dirs.done(dirs.go(ps.toks(ps), [], False{}), ps)))))
386
387def h.doc.end(+t: T.Token, +ps: Ps) -> PStep:
388  +explicit = tok.is(t, DOC_END())
389  PGo{goto(emit(Bool.pick(Ps, explicit, take(ps), ps), DocEndEv{explicit}, tok.start(t)), SDocStart{explicit})}
390
391# Nodes
392# -----
393
394def mark.or(m: Maybe<&2, T.Mark>, d: T.Mark) -> T.Mark:
395  match m:
396    case None{}:
397      d
398    case Some{x}:
399      x
400
401def is_none.s(m: Maybe<&2, String>) -> Bool:
402  match m:
403    case None{}:
404      True{}
405    case Some{x}:
406      False{}
407
408def is_none.w(m: Maybe<&2, Written>) -> Bool:
409  match m:
410    case None{}:
411      True{}
412    case Some{x}:
413      False{}
414
415# No content: an empty scalar, when the node has an anchor or a tag.
416def content.none(+block: Bool, +props: Bool, anchor: Maybe<&2, String>, tag: Tag, +at: T.Mark, +ps: Ps) -> PStep:
417  when(PStep, props, u => PGo{emit(pop(ps), ScalarEv{anchor, tag, "", T.Plain{}}, at)},
418    u => fail(ps, Bool.pick(String, block, "did not find expected node content while parsing a block node",
419      "did not find expected node content while parsing a flow node"), at))
420
421# The node's content, after its anchor and tag.
422def content(k: T.Tok, +block: Bool, +indentless: Bool, +anchor: Maybe<&2, String>, +tag: Tag, +props: Bool, +at: T.Mark, +ps: Ps) -> PStep:
423  match k:
424    case T.BEntry{}:
425      when(PStep, indentless, u => PGo{emit(goto(ps, SIndentless{at}), SeqStartEv{anchor, tag, False{}}, at)},
426        u => content.none(block, props, anchor, tag, at, ps))
427    case T.ScalarTok{text, style}:
428      PGo{take(emit(pop(ps), ScalarEv{anchor, tag, text, style}, at))}
429    case T.FSeqStart{}:
430      PGo{emit(goto(ps, SFSeqFirst{}), SeqStartEv{anchor, tag, True{}}, at)}
431    case T.FMapStart{}:
432      PGo{emit(goto(ps, SFMapFirst{}), MapStartEv{anchor, tag, True{}}, at)}
433    case T.BSeqStart{}:
434      when(PStep, block, u => PGo{emit(goto(ps, SBSeqFirst{}), SeqStartEv{anchor, tag, False{}}, at)},
435        u => content.none(block, props, anchor, tag, at, ps))
436    case T.BMapStart{}:
437      when(PStep, block, u => PGo{emit(goto(ps, SBMapFirst{}), MapStartEv{anchor, tag, False{}}, at)},
438        u => content.none(block, props, anchor, tag, at, ps))
439    case _:
440      content.none(block, props, anchor, tag, at, ps)
441
442def content.tagged(r: Result<&2, &2, T.Error, Tag>, +k: T.Tok, +block: Bool, +indentless: Bool, +anchor: Maybe<&2, String>, +props: Bool, +at: T.Mark, +ps: Ps) -> PStep:
443  match r:
444    case Fail{e}:
445      PStop{ps, Some{e}}
446    case Done{tag}:
447      content(k, block, indentless, anchor, tag, props, at, ps)
448
449def node.rest(+block: Bool, +indentless: Bool, +anchor: Maybe<&2, String>, +tag: Maybe<&2, Written>, +bare: Bool, +at: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
450  content.tagged(tag.resolve(tag, ps.tags(ps), at), tok.kind(t), block, indentless, anchor, Bool.not(bare), at, ps)
451
452def h.node.kind(k: T.Tok, +block: Bool, +indentless: Bool, +anchor: Maybe<&2, String>, +tag: Maybe<&2, Written>, +bare: Bool, +at: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
453  match k:
454    case T.AliasTok{name}:
455      when(PStep, bare, u => PGo{take(emit(pop(ps), AliasEv{name}, at))}, u => node.rest(block, indentless, anchor, tag, bare, at, t, ps))
456    case T.AnchorTok{name}:
457      when(PStep, is_none.s(anchor), u => PGo{take(goto(ps, SNode{block, indentless, Some{name}, tag, Some{at}}))},
458        u => node.rest(block, indentless, anchor, tag, bare, at, t, ps))
459    case T.TagTok{h, s}:
460      when(PStep, is_none.w(tag), u => PGo{take(goto(ps, SNode{block, indentless, anchor, Some{Written{h, s}}, Some{at}}))},
461        u => node.rest(block, indentless, anchor, tag, bare, at, t, ps))
462    case _:
463      node.rest(block, indentless, anchor, tag, bare, at, t, ps)
464
465# A node: its anchor and tag (in either order), then an alias or content.
466def h.node(+block: Bool, +indentless: Bool, +anchor: Maybe<&2, String>, +tag: Maybe<&2, Written>, +start: Maybe<&2, T.Mark>, +t: T.Token, +ps: Ps) -> PStep:
467  +at = mark.or(start, tok.start(t))
468  +bare = Bool.and(is_none.s(anchor), is_none.w(tag))
469  h.node.kind(tok.kind(t), block, indentless, anchor, tag, bare, at, t, ps)
470
471def h.doc.content(+t: T.Token, +ps: Ps) -> PStep:
472  when(PStep, tok.any(t, [VERSION(), TAG_DIR(), DOC_START(), DOC_END(), STREAM_END()]), u => PGo{empty(pop(ps), tok.start(t))},
473    u => h.node(True{}, False{}, None{}, None{}, None{}, t, ps))
474
475# Block collections
476# -----------------
477
478def node.next(+block: Bool, +indentless: Bool, back: St, +t: T.Token, ps: Ps) -> PStep:
479  h.node(block, indentless, None{}, None{}, None{}, t, push(ps, back))
480
481def h.bseq.entry(+m: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
482  when(PStep, tok.is(t, BENTRY()), u => PGo{take(goto(ps, SBSeqAfter{m, tok.end(t)}))},
483    u => when(PStep, tok.is(t, BEND()), u => PGo{take(emit(pop(ps), SeqEndEv{}, tok.start(t)))},
484      u => fail(ps, "did not find expected '-' indicator while parsing a block collection", m)))
485
486def h.bseq.after(+m: T.Mark, e: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
487  when(PStep, tok.any(t, [BENTRY(), BEND()]), u => PGo{empty(goto(ps, SBSeqEntry{m}), e)},
488    u => node.next(True{}, False{}, SBSeqEntry{m}, t, ps))
489
490def h.indentless(+m: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
491  when(PStep, tok.is(t, BENTRY()), u => PGo{take(goto(ps, SIndentlessAfter{m, tok.end(t)}))},
492    u => PGo{emit(pop(ps), SeqEndEv{}, tok.start(t))})
493
494def h.indentless.after(+m: T.Mark, e: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
495  when(PStep, tok.any(t, [BENTRY(), KEY(), VALUE(), BEND()]), u => PGo{empty(goto(ps, SIndentless{m}), e)},
496    u => node.next(True{}, False{}, SIndentless{m}, t, ps))
497
498def h.bmap.key(+m: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
499  when(PStep, tok.is(t, KEY()), u => PGo{take(goto(ps, SBMapAfterKey{m, tok.end(t)}))},
500    u => when(PStep, tok.is(t, BEND()), u => PGo{take(emit(pop(ps), MapEndEv{}, tok.start(t)))},
501      u => when(PStep, tok.is(t, VALUE()), u => PGo{empty(goto(ps, SBMapValue{m}), tok.start(t))},
502        u => fail(ps, "did not find expected key while parsing a block mapping", m))))
503
504def h.bmap.after.key(+m: T.Mark, e: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
505  when(PStep, tok.any(t, [KEY(), VALUE(), BEND()]), u => PGo{empty(goto(ps, SBMapValue{m}), e)},
506    u => node.next(True{}, True{}, SBMapValue{m}, t, ps))
507
508def h.bmap.value(+m: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
509  when(PStep, tok.is(t, VALUE()), u => PGo{take(goto(ps, SBMapAfterValue{m, tok.end(t)}))},
510    u => PGo{empty(goto(ps, SBMapKey{m}), tok.start(t))})
511
512def h.bmap.after.value(+m: T.Mark, e: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
513  when(PStep, tok.any(t, [KEY(), VALUE(), BEND()]), u => PGo{empty(goto(ps, SBMapKey{m}), e)},
514    u => node.next(True{}, True{}, SBMapKey{m}, t, ps))
515
516# Flow collections
517# ----------------
518
519def h.fseq.entry(+m: T.Mark, +first: Bool, +t: T.Token, +ps: Ps) -> PStep:
520  when(PStep, tok.is(t, FSEQ_END()), u => PGo{take(emit(pop(ps), SeqEndEv{}, tok.start(t)))},
521    u => when(PStep, Bool.not(first),
522      u => when(PStep, tok.is(t, FENTRY()), u => PGo{take(goto(ps, SFSeqEntry{m, True{}}))},
523        u => fail(ps, "did not find expected ',' or ']' while parsing a flow sequence", m)),
524      u => when(PStep, tok.is(t, KEY()), u => PGo{take(emit(goto(ps, SFSeqMapKey{m}), MapStartEv{None{}, NoTag{}, True{}}, tok.start(t)))},
525        u => when(PStep, tok.is(t, VALUE()), u => PGo{emit(goto(ps, SFSeqMapKey{m}), MapStartEv{None{}, NoTag{}, True{}}, tok.start(t))},
526          u => node.next(False{}, False{}, SFSeqEntry{m, False{}}, t, ps)))))
527
528# An implicit pair's key in a flow sequence.
529def h.fseq.map.key(+m: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
530  when(PStep, tok.any(t, [VALUE(), FENTRY(), FSEQ_END()]),
531    u => PGo{empty(goto(ps, SFSeqMapValue{m}), tok.start(t))},
532    u => node.next(False{}, False{}, SFSeqMapValue{m}, t, ps))
533
534def h.fseq.map.value(+m: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
535  when(PStep, tok.is(t, VALUE()), u => PGo{take(goto(ps, SFSeqMapAfterValue{m, tok.end(t)}))},
536    u => PGo{empty(goto(ps, SFSeqMapEnd{m}), tok.start(t))})
537
538def h.fseq.map.after.value(+m: T.Mark, e: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
539  when(PStep, tok.any(t, [FENTRY(), FSEQ_END()]), u => PGo{empty(goto(ps, SFSeqMapEnd{m}), e)},
540    u => node.next(False{}, False{}, SFSeqMapEnd{m}, t, ps))
541
542def h.fseq.map.end(m: T.Mark, +t: T.Token, ps: Ps) -> PStep:
543  PGo{emit(goto(ps, SFSeqEntry{m, False{}}), MapEndEv{}, tok.start(t))}
544
545def h.fmap.key(+m: T.Mark, +first: Bool, +t: T.Token, +ps: Ps) -> PStep:
546  when(PStep, tok.is(t, FMAP_END()), u => PGo{take(emit(pop(ps), MapEndEv{}, tok.start(t)))},
547    u => when(PStep, Bool.not(first),
548      u => when(PStep, tok.is(t, FENTRY()), u => PGo{take(goto(ps, SFMapKey{m, True{}}))},
549        u => fail(ps, "did not find expected ',' or '}' while parsing a flow mapping", m)),
550      u => when(PStep, tok.is(t, KEY()), u => PGo{take(goto(ps, SFMapAfterKey{m, tok.end(t)}))},
551        u => when(PStep, tok.is(t, VALUE()), u => PGo{empty(goto(ps, SFMapValue{m}), tok.start(t))},
552          u => node.next(False{}, False{}, SFMapEmpty{m}, t, ps)))))
553
554def h.fmap.after.key(+m: T.Mark, e: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
555  when(PStep, tok.any(t, [VALUE(), FENTRY(), FMAP_END()]), u => PGo{empty(goto(ps, SFMapValue{m}), tok.start(t))},
556    u => node.next(False{}, False{}, SFMapValue{m}, t, ps))
557
558def h.fmap.value(+m: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
559  when(PStep, tok.is(t, VALUE()), u => PGo{take(goto(ps, SFMapAfterValue{m, tok.end(t)}))},
560    u => PGo{empty(goto(ps, SFMapKey{m, False{}}), tok.start(t))})
561
562def h.fmap.after.value(+m: T.Mark, e: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
563  when(PStep, tok.any(t, [FENTRY(), FMAP_END()]), u => PGo{empty(goto(ps, SFMapKey{m, False{}}), e)},
564    u => node.next(False{}, False{}, SFMapKey{m, False{}}, t, ps))
565
566# After a key with no KeyTok: a ":" on a later line is still its value (a
567# flow mapping's key may run over lines), else the value is empty.
568def h.fmap.empty(+m: T.Mark, +t: T.Token, +ps: Ps) -> PStep:
569  when(PStep, tok.is(t, VALUE()), u => PGo{take(goto(ps, SFMapAfterValue{m, tok.end(t)}))},
570    u => PGo{empty(goto(ps, SFMapKey{m, False{}}), tok.start(t))})
571
572# Steps
573# -----
574
575def h.state(s: St, +t: T.Token, +ps: Ps) -> PStep:
576  match s:
577    case SStreamStart{}:
578      PGo{take(goto(emit(ps, StreamStartEv{}, tok.start(t)), SFirstDoc{}))}
579    case SFirstDoc{}:
580      h.doc.start(True{}, t, ps)
581    case SDocStart{ended}:
582      h.doc.start(ended, t, ps)
583    case SDocContent{}:
584      h.doc.content(t, ps)
585    case SDocEnd{}:
586      h.doc.end(t, ps)
587    case SNode{block, indentless, anchor, tag, start}:
588      h.node(block, indentless, anchor, tag, start, t, ps)
589    case SBSeqFirst{}:
590      PGo{take(goto(ps, SBSeqEntry{tok.start(t)}))}
591    case SBSeqEntry{m}:
592      h.bseq.entry(m, t, ps)
593    case SBSeqAfter{m, e}:
594      h.bseq.after(m, e, t, ps)
595    case SIndentless{m}:
596      h.indentless(m, t, ps)
597    case SIndentlessAfter{m, e}:
598      h.indentless.after(m, e, t, ps)
599    case SBMapFirst{}:
600      PGo{take(goto(ps, SBMapKey{tok.start(t)}))}
601    case SBMapKey{m}:
602      h.bmap.key(m, t, ps)
603    case SBMapAfterKey{m, e}:
604      h.bmap.after.key(m, e, t, ps)
605    case SBMapValue{m}:
606      h.bmap.value(m, t, ps)
607    case SBMapAfterValue{m, e}:
608      h.bmap.after.value(m, e, t, ps)
609    case SFSeqFirst{}:
610      PGo{take(goto(ps, SFSeqEntry{tok.start(t), True{}}))}
611    case SFSeqEntry{m, first}:
612      h.fseq.entry(m, first, t, ps)
613    case SFSeqMapKey{m}:
614      h.fseq.map.key(m, t, ps)
615    case SFSeqMapValue{m}:
616      h.fseq.map.value(m, t, ps)
617    case SFSeqMapAfterValue{m, e}:
618      h.fseq.map.after.value(m, e, t, ps)
619    case SFSeqMapEnd{m}:
620      h.fseq.map.end(m, t, ps)
621    case SFMapFirst{}:
622      PGo{take(goto(ps, SFMapKey{tok.start(t), True{}}))}
623    case SFMapKey{m, first}:
624      h.fmap.key(m, first, t, ps)
625    case SFMapAfterKey{m, e}:
626      h.fmap.after.key(m, e, t, ps)
627    case SFMapValue{m}:
628      h.fmap.value(m, t, ps)
629    case SFMapAfterValue{m, e}:
630      h.fmap.after.value(m, e, t, ps)
631    case SFMapEmpty{m}:
632      h.fmap.empty(m, t, ps)
633    case SEnd{}:
634      PStop{ps, None{}}
635
636# A Broken token stops the parser with its error.
637def h.token(k: T.Tok, +t: T.Token, +ps: Ps) -> PStep:
638  match k:
639    case T.Broken{e}:
640      PStop{ps, Some{e}}
641    case _:
642      h.state(ps.state(ps), t, ps)
643
644def h.head(ts: List<&2, T.Token>, +ps: Ps) -> PStep:
645  match ts:
646    case Nil{}:
647      PStop{ps, None{}}
648    case Con{+t, rest}:
649      h.token(tok.kind(t), t, ps)
650
651def p.step(+ps: Ps) -> PStep:
652  h.head(ps.toks(ps), ps)
653
654def p.run(fuel: Nat, s: PStep) -> Parsed:
655  match fuel:
656    case 0n:
657      match s:
658        case PGo{ps}:
659          Parsed{List.reverse(&2, Evt, ps.out(ps)), Some{T.Error{"the parser ran out of steps", T.Mark{0n, 0n, 0n}, T.Syntax{}}}}
660        case PStop{ps, e}:
661          Parsed{List.reverse(&2, Evt, ps.out(ps)), e}
662    case 1n+k:
663      match s:
664        case PGo{ps}:
665          p.run(k, p.step(ps))
666        case PStop{ps, e}:
667          Parsed{List.reverse(&2, Evt, ps.out(ps)), e}
668
669# The events of a token stream.
670def parse(+toks: List<&2, T.Token>) -> Parsed:
671  p.run(Nat.add(Nat.mul(List.length(&2, T.Token, toks), 8n), 16n), PGo{Ps{toks, SStreamStart{}, [], defaults(), []}})
672
673# The events of a YAML text, with flow collections nesting at most +max+
674# deep.
675def events(text: String, max: Nat) -> Parsed:
676  parse(S.scan(text, max))
677
678def escaped.other(c: Char, rest: String) -> String:
679  match c:
680    case Chr{+x}:
681      Bool.pick(String, U32.is_eq(x, 8), "\\b", Bool.pick(String, U32.is_eq(x, 0), "\\0", SCon{Chr{x}, SNil{}})) ++ rest
682
683# Events as text
684# --------------
685
686# A scalar's text as the YAML test suite writes it: backslashes, breaks
687# and tabs escaped.
688def escaped(s: String) -> String:
689  match s:
690    case SNil{}:
691      ""
692    case SCon{c, t}:
693      match c:
694        case '\\':
695          "\\\\" ++ escaped(t)
696        case '\n':
697          "\\n" ++ escaped(t)
698        case '\t':
699          "\\t" ++ escaped(t)
700        case '\r':
701          "\\r" ++ escaped(t)
702        case _:
703          escaped.other(c, escaped(t))
704
705def style.mark(s: T.Style) -> String:
706  match s:
707    case T.Plain{}:
708      ":"
709    case T.Single{}:
710      "'"
711    case T.Double{}:
712      "\""
713    case T.Literal{}:
714      "|"
715    case T.Folded{}:
716      ">"
717
718def anchor.text(a: Maybe<&2, String>) -> String:
719  match a:
720    case None{}:
721      ""
722    case Some{n}:
723      " &" ++ n
724
725def tag.text(t: Tag) -> String:
726  match t:
727    case NoTag{}:
728      ""
729    case Tag{n}:
730      " <" ++ n ++ ">"
731
732def flow.text(+flow: Bool, brackets: String) -> String:
733  Bool.pick(String, flow, " " ++ brackets, "")
734
735# An event as the YAML test suite writes it: "+MAP {} &a <tag>", "=VAL :x".
736def ev.text(e: Ev) -> String:
737  match e:
738    case StreamStartEv{}:
739      "+STR"
740    case StreamEndEv{}:
741      "-STR"
742    case DocStartEv{explicit}:
743      Bool.pick(String, explicit, "+DOC ---", "+DOC")
744    case DocEndEv{explicit}:
745      Bool.pick(String, explicit, "-DOC ...", "-DOC")
746    case AliasEv{name}:
747      "=ALI *" ++ name
748    case ScalarEv{anchor, tag, text, style}:
749      "=VAL" ++ anchor.text(anchor) ++ tag.text(tag) ++ " " ++ style.mark(style) ++ escaped(text)
750    case SeqStartEv{anchor, tag, flow}:
751      "+SEQ" ++ flow.text(flow, "[]") ++ anchor.text(anchor) ++ tag.text(tag)
752    case SeqEndEv{}:
753      "-SEQ"
754    case MapStartEv{anchor, tag, flow}:
755      "+MAP" ++ flow.text(flow, "{}") ++ anchor.text(anchor) ++ tag.text(tag)
756    case MapEndEv{}:
757      "-MAP"
758
759def evts.text(es: List<&2, Evt>) -> String:
760  match es:
761    case Nil{}:
762      ""
763    case Con{e, rest}:
764      match e:
765        case Evt{ev, at}:
766          ev.text(ev) ++ "\n" ++ evts.text(rest)
767
768def error.text(m: Maybe<&2, T.Error>) -> String:
769  match m:
770    case None{}:
771      ""
772    case Some{e}:
773      "ERROR " ++ T.error.show(e) ++ "\n"
774
775# The events of a parse, one per line, and the error after them.
776def parsed.text(p: Parsed) -> String:
777  match p:
778    case Parsed{events, error}:
779      evts.text(events) ++ error.text(error)