scan.bend

yaml-for-bend@0.1.1.0 · 1,532 lines · 207 definitions

1# The scanner: YAML text to tokens.
2#
3# It follows the design of libyaml's scanner. One step fetches the next
4# token. Block collections open and close by indentation, so the scanner
5# keeps a stack of indentations and adds BSeqStart, BMapStart and BEnd
6# tokens as they change. A "simple key" (a key without "?") is only known to
7# be a key when its ":" arrives, so the scanner remembers where each
8# possible key started and, at the ":", inserts a KeyTok (and BMapStart)
9# before the key's first token.
10#
11# It reads YAML 1.2 as the YAML test suite has it: tabs separate tokens
12# but never indent, a flow collection's lines and a quoted scalar's indent
13# past the block around them, a comment follows a blank, anchors take any
14# character but blanks and flow indicators, ":" is a value indicator right
15# after a JSON-like node in flow, and reserved directives are skipped.
16#
17# An error ends the tokens with a Broken token, so the parser still sees
18# the tokens before it.
19
20import Base
21
22import yaml-for-bend@0.1.1.0/token.bend as T
23
24# The text left to read, where it starts, and how many characters are left.
25type Cur is Data:
26  Cur{s: String, at: T.Mark, left: Nat}
27
28# A place a simple key may start: whether one still may, whether it must (a
29# block key at the indentation), the number its first token has, and where.
30# Each level also keeps where the oldest key still possible at or below it
31# started (+low+), so finding stale keys needn't look at every level.
32type SKey is Data:
33  SKey{possible: Bool, required: Bool, number: Nat, at: T.Mark, tab: Bool, low: Maybe<&2, T.Mark>}
34
35# The scanner: the cursor, the block indentation plus one (0 outside any
36# block collection) and the ones it returns to, how deep in flow collections
37# it is, whether a simple key may start here, one possible key per flow
38# level (the block level last), the tokens so far (newest first) and their
39# count, and how deep flow collections may nest.
40type Sc is Data:
41  Sc{cur: Cur, ind: Nat, inds: List<&2, Nat>, flow: Nat, allowed: Bool, tab: Bool, keys: List<&2, SKey>, out: List<&2, T.Token>, n: Nat, max: Nat}
42
43# A step goes on, or stops: at the stream's end or at an error, as the last
44# token says.
45type Step is Data:
46  Go{st: Sc}
47  Stop{st: Sc}
48
49type Lay is Data:
50  Lay{ind: Nat, inds: List<&2, Nat>, out: List<&2, T.Token>, n: Nat}
51
52# Between tokens
53# --------------
54
55type Skipped is Data:
56  Skipped{cur: Cur, allowed: Bool, tab: Bool, nl: Bool, sp: Nat, bad: Bool}
57
58# Plain scalars
59# -------------
60
61# Reading a plain scalar: the cursor, the text so far (reversed), where the
62# last word ended, the blanks after it (reversed), whether a line break came
63# since, how many more breaks did, and whether a word is being read.
64type Pl is Data:
65  Pl{cur: Cur, acc: String, end: T.Mark, ws: String, lead: Bool, brks: Nat, word: Bool, bad: Bool}
66  PlDone{cur: Cur, acc: String, end: T.Mark, lead: Bool}
67  PlBad{error: T.Error}
68
69# Quoted scalars
70# --------------
71
72# Reading a quoted scalar: the cursor, the text so far (reversed), the
73# blanks waiting (reversed), whether a line break came since the last text
74# and how many more did, whether that break was escaped, and whether text
75# (not blanks) is being read.
76type Qs is Data:
77  Qs{cur: Cur, acc: String, ws: String, lead: Bool, brks: Nat, esc: Bool, text: Bool, bad: Bool}
78  QsDone{cur: Cur, acc: String}
79  QsBad{error: T.Error}
80
81# Block scalars
82# -------------
83
84type Chomp is Data:
85  Clip{}
86  Strip{}
87  Keep{}
88
89# A block scalar's header: how to chomp, the indentation indicator (0 when
90# there's none), and the cursor after it; or an error.
91type Head is Data:
92  Head{chomp: Chomp, inc: Nat, cur: Cur}
93  HeadBad{why: String}
94
95type BPhase is Data:
96  Breaks{}
97  LineStart{}
98  Content{}
99
100# Reading a block scalar: the cursor, the text so far (reversed), the
101# content's indentation plus one (0 until known), the deepest blank line, whether a
102# line break waits, whether the last line started with a blank, how many
103# more breaks wait, and the phase: blank lines, a line's start, or content.
104type Bs is Data:
105  Bs{cur: Cur, acc: String, ind: Nat, max: Nat, lead: Bool, lblank: Bool, brks: Nat, phase: BPhase}
106  BsDone{acc: String, lead: Bool, brks: Nat, cur: Cur}
107  BsBad{error: T.Error}
108
109# Anchors, aliases and tags
110# -------------------------
111
112# What a scan took: the text it read and how many characters that was.
113type Taken is Data:
114  Taken{text: String, n: Nat}
115
116# The step after +v+, when it goes on.
117def then(v: Step, f: Sc -> Step) -> Step:
118  match v:
119    case Go{st}:
120      f(st)
121    case Stop{st}:
122      Stop{st}
123
124# +yes+ when +hit+, else +no+; only the one chosen runs.
125def when(-A: Type, hit: Bool, yes: Unit -> A, no: Unit -> A) -> A:
126  match hit:
127    case True{}:
128      yes(Unit{})
129    case False{}:
130      no(Unit{})
131
132# Characters
133# ----------
134
135def code(c: Char) -> U32:
136  match c:
137    case Chr{x}:
138      x
139
140# The character +n+ places on, or NUL past the end.
141def peek(s: String, n: Nat) -> Char:
142  match s:
143    case SNil{}:
144      Chr{0}
145    case SCon{c, t}:
146      match n:
147        case 0n:
148          c
149        case 1n+k:
150          peek(t, k)
151
152def is_blank(c: Char) -> Bool:
153  match c:
154    case ' ':
155      True{}
156    case '\t':
157      True{}
158    case _:
159      False{}
160
161def is_break(c: Char) -> Bool:
162  Char.is_eq(c, '\n')
163
164def is_end(c: Char) -> Bool:
165  U32.is_eq(code(c), 0)
166
167def is_blankz(+c: Char) -> Bool:
168  Bool.or(is_blank(c), Bool.or(is_break(c), is_end(c)))
169
170def is_breakz(+c: Char) -> Bool:
171  Bool.or(is_break(c), is_end(c))
172
173def is_flow.ind(c: Char) -> Bool:
174  match c:
175    case ',':
176      True{}
177    case '[':
178      True{}
179    case ']':
180      True{}
181    case '{':
182      True{}
183    case '}':
184      True{}
185    case _:
186      False{}
187
188def between(+x: U32, lo: U32, hi: U32) -> Bool:
189  Bool.and(U32.is_ge(x, lo), U32.is_le(x, hi))
190
191def is_digit(c: Char) -> Bool:
192  Char.is_digit(c)
193
194def is_hex(+c: Char) -> Bool:
195  Bool.or(Char.is_digit(c), Bool.or(between(code(c), 65, 70), between(code(c), 97, 102)))
196
197# A letter, digit or "-": what a tag handle's name is made of.
198def is_word(+c: Char) -> Bool:
199  Bool.or(Char.is_alpha(c), Bool.or(Char.is_digit(c), Char.is_eq(c, '-')))
200
201def is_in(c: Char, s: String) -> Bool:
202  String.contains(s, SCon{c, SNil{}})
203
204# A URI character other than "%" (which starts an escape).
205def is_uri(+c: Char) -> Bool:
206  Bool.or(is_word(c), is_in(c, "#;/?:@&=+$,_.!~*'()[]"))
207
208# A tag character: a URI character but "!" and the flow indicators.
209def is_tag(+c: Char) -> Bool:
210  Bool.or(is_word(c), is_in(c, "#;/?:@&=+$_.~*'()"))
211
212# What YAML allows in a document: tab, line feed, and printable characters.
213def is_printable(c: Char) -> Bool:
214  match c:
215    case Chr{+x}:
216      Bool.or(Bool.or(U32.is_eq(x, 9), U32.is_eq(x, 10)),
217        Bool.or(between(x, 32, 126), Bool.or(U32.is_eq(x, 133), Bool.or(between(x, 160, 55295),
218          Bool.or(between(x, 57344, 65533), between(x, 65536, 1114111))))))
219
220def hex.digit(c: Char) -> U32:
221  +x = code(c)
222  U32.sub(x, Bool.pick(U32, U32.is_ge(x, 97), 87, Bool.pick(U32, U32.is_ge(x, 65), 55, 48)))
223
224def hex.value(s: String, acc: U32) -> U32:
225  match s:
226    case SNil{}:
227      acc
228    case SCon{c, t}:
229      hex.value(t, U32.add(U32.mul(acc, 16), hex.digit(c)))
230
231def all.hex(s: String) -> Bool:
232  match s:
233    case SNil{}:
234      True{}
235    case SCon{+c, t}:
236      Bool.and(is_hex(c), all.hex(t))
237
238# "---" or "..." (+c+ thrice) and then a blank, a break or the end.
239def marker(+s: String, +c: Char) -> Bool:
240  Bool.and(Bool.and(Char.is_eq(peek(s, 0n), c), Char.is_eq(peek(s, 1n), c)), Bool.and(Char.is_eq(peek(s, 2n), c), is_blankz(peek(s, 3n))))
241
242def is_marker(+s: String) -> Bool:
243  Bool.or(marker(s, '-'), marker(s, '.'))
244
245# Line breaks as "\n": "\r\n" and a lone "\r" both become one, as YAML reads
246# them.
247def lf(s: String) -> String:
248  match s:
249    case SNil{}:
250      SNil{}
251    case SCon{c, t}:
252      match c:
253        case '\r':
254          match t:
255            case SCon{'\n', u}:
256              SCon{'\n', lf(u)}
257            case _:
258              SCon{'\n', lf(t)}
259        case _:
260          SCon{c, lf(t)}
261
262def strip.bom(s: String) -> String:
263  match s:
264    case SCon{c, +t}:
265      match c:
266        case Chr{+x}:
267          Bool.pick(String, U32.is_eq(x, 65279), t, SCon{Chr{x}, t})
268    case SNil{}:
269      SNil{}
270
271# The cursor
272# ----------
273
274def past(at: T.Mark, c: Char) -> T.Mark:
275  match at:
276    case T.Mark{line, col, idx}:
277      match c:
278        case '\n':
279          T.Mark{1n+line, 0n, 1n+idx}
280        case _:
281          T.Mark{line, 1n+col, 1n+idx}
282
283def adv(c: Cur) -> Cur:
284  match c:
285    case Cur{s, at, left}:
286      match s:
287        case SNil{}:
288          Cur{SNil{}, at, left}
289        case SCon{h, t}:
290          Cur{t, past(at, h), Nat.sub(left, 1n)}
291
292def adv.n(n: Nat, c: Cur) -> Cur:
293  match n:
294    case 0n:
295      c
296    case 1n+k:
297      adv.n(k, adv(c))
298
299def cur.s(c: Cur) -> String:
300  match c:
301    case Cur{s, at, left}:
302      s
303
304def cur.at(c: Cur) -> T.Mark:
305  match c:
306    case Cur{s, at, left}:
307      at
308
309def cur.left(c: Cur) -> Nat:
310  match c:
311    case Cur{s, at, left}:
312      left
313
314def cur.col(c: Cur) -> Nat:
315  T.mark.col(cur.at(c))
316
317# The scanner's state
318# -------------------
319
320def sc.cur(st: Sc) -> Cur:
321  match st:
322    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
323      cur
324
325def sc.s(st: Sc) -> String:
326  cur.s(sc.cur(st))
327
328def sc.at(st: Sc) -> T.Mark:
329  cur.at(sc.cur(st))
330
331def sc.col(st: Sc) -> Nat:
332  cur.col(sc.cur(st))
333
334def sc.ind(st: Sc) -> Nat:
335  match st:
336    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
337      ind
338
339def sc.flow(st: Sc) -> Nat:
340  match st:
341    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
342      flow
343
344def sc.in_flow(st: Sc) -> Bool:
345  Nat.is_gt(sc.flow(st), 0n)
346
347def sc.max(st: Sc) -> Nat:
348  match st:
349    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
350      max
351
352def sc.tab(st: Sc) -> Bool:
353  match st:
354    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
355      tab
356
357def sc.allowed(st: Sc) -> Bool:
358  match st:
359    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
360      allowed
361
362def sc.keys(st: Sc) -> List<&2, SKey>:
363  match st:
364    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
365      keys
366
367def sc.out(st: Sc) -> List<&2, T.Token>:
368  match st:
369    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
370      out
371
372def sc.with.cur(st: Sc, c: Cur) -> Sc:
373  match st:
374    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
375      Sc{c, ind, inds, flow, allowed, tab, keys, out, n, max}
376
377def sc.allow(st: Sc, b: Bool) -> Sc:
378  match st:
379    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
380      Sc{cur, ind, inds, flow, b, tab, keys, out, n, max}
381
382def sc.with.keys(st: Sc, ks: List<&2, SKey>) -> Sc:
383  match st:
384    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
385      Sc{cur, ind, inds, flow, allowed, tab, ks, out, n, max}
386
387def skip(+st: Sc, k: Nat) -> Sc:
388  sc.with.cur(st, adv.n(k, sc.cur(st)))
389
390# A token from +start+ to +end+.
391def emit.span(st: Sc, tok: T.Tok, start: T.Mark, end: T.Mark) -> Sc:
392  match st:
393    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
394      Sc{cur, ind, inds, flow, allowed, tab, keys, T.Token{tok, start, end} <> out, 1n+n, max}
395
396# A token from +start+ to here.
397def emit(+st: Sc, tok: T.Tok, start: T.Mark) -> Sc:
398  emit.span(st, tok, start, sc.at(st))
399
400# A one-character token here.
401def single(+st: Sc, tok: T.Tok) -> Sc:
402  emit(skip(st, 1n), tok, sc.at(st))
403
404def fail(+st: Sc, why: String, +at: T.Mark) -> Step:
405  Stop{emit(st, T.Broken{T.Error{why, at, T.Syntax{}}}, at)}
406
407# A limit reached: the error names it.
408def fail.limit(+st: Sc, why: String) -> Step:
409  Stop{emit(st, T.Broken{T.Error{why, sc.at(st), T.Limit{}}}, sc.at(st))}
410
411def fail.with(+st: Sc, e: T.Error) -> Step:
412  match e:
413    case T.Error{why, at, cause}:
414      fail(st, why, at)
415
416# "found character that cannot start any token"
417def cannot(+st: Sc) -> Step:
418  fail(st, "found character that cannot start any token while scanning for the next token", sc.at(st))
419
420# The token before this one: whether it was a JSON-like node (a quoted
421# scalar or a flow collection), after which ":" is a value indicator even
422# without a space.
423def json.tok(t: T.Tok) -> Bool:
424  match t:
425    case T.ScalarTok{text, style}:
426      match style:
427        case T.Single{}:
428          True{}
429        case T.Double{}:
430          True{}
431        case _:
432          False{}
433    case T.FSeqEnd{}:
434      True{}
435    case T.FMapEnd{}:
436      True{}
437    case _:
438      False{}
439
440def json.before(out: List<&2, T.Token>) -> Bool:
441  match out:
442    case Nil{}:
443      False{}
444    case Con{t, rest}:
445      match t:
446        case T.Token{tok, start, end}:
447          json.tok(tok)
448
449# Simple keys
450# -----------
451
452# The possible key on top, which a ":" would make a key.
453def key.top(keys: List<&2, SKey>) -> SKey:
454  match keys:
455    case Nil{}:
456      SKey{False{}, False{}, 0n, T.Mark{0n, 0n, 0n}, False{}, None{}}
457    case Con{k, rest}:
458      k
459
460def key.or(r: Result<&2, &2, T.Error, List<&2, SKey>>, +st: Sc) -> Step:
461  match r:
462    case Fail{e}:
463      fail.with(st, e)
464    case Done{ks}:
465      Go{sc.with.keys(st, ks)}
466
467def low.of(keys: List<&2, SKey>) -> Maybe<&2, T.Mark>:
468  match keys:
469    case Nil{}:
470      None{}
471    case Con{k, rest}:
472      match k:
473        case SKey{possible, required, number, at, tab, low}:
474          low
475
476def key.removed(keys: List<&2, SKey>) -> Result<&2, &2, T.Error, List<&2, SKey>>:
477  match keys:
478    case Nil{}:
479      Done{[]}
480    case Con{k, +rest}:
481      match k:
482        case SKey{+possible, +required, number, +at, tab, low}:
483          when(Result<&2, &2, T.Error, List<&2, SKey>>, Bool.and(possible, required),
484            u => Fail{T.Error{"could not find expected ':' while scanning a simple key", at, T.Syntax{}}},
485            u => Done{SKey{False{}, required, number, at, tab, low.of(rest)} <> rest})
486
487# The key on top can no longer be; an error if it had to be.
488def remove.key(+st: Sc) -> Step:
489  key.or(key.removed(sc.keys(st)), st)
490
491# A level's low: the one below it, or its own key when that is possible.
492def low.with(below: Maybe<&2, T.Mark>, possible: Bool, at: T.Mark) -> Maybe<&2, T.Mark>:
493  match below:
494    case Some{m}:
495      Some{m}
496    case None{}:
497      match possible:
498        case True{}:
499          Some{at}
500        case False{}:
501          None{}
502
503def key.put(st: Sc, required: Bool) -> Sc:
504  match st:
505    case Sc{+cur, ind, inds, flow, allowed, +tab, keys, out, +n, max}:
506      +rest = List.drop(&2, SKey, keys, 1n)
507      Sc{cur, ind, inds, flow, allowed, tab, SKey{True{}, required, n, cur.at(cur), tab, low.with(low.of(rest), True{}, cur.at(cur))} <> rest, out, n, max}
508
509def key.saved(r: Step, +required: Bool) -> Step:
510  match r:
511    case Go{st}:
512      Go{key.put(st, required)}
513    case Stop{st}:
514      Stop{st}
515
516# A simple key may start here. It must be one (no "?" can come later) when
517# it starts a block line at the indentation.
518def save.key(+st: Sc) -> Step:
519  +required = Bool.and(Nat.is_eq(sc.flow(st), 0n), Nat.is_eq(sc.ind(st), 1n+sc.col(st)))
520  when(Step, sc.allowed(st), u => key.saved(remove.key(st), required), u => Go{st})
521
522# A simple key stays on one line and within 1024 characters.
523def is_stale(+kat: T.Mark, +at: T.Mark) -> Bool:
524  Bool.or(Nat.is_lt(T.mark.line(kat), T.mark.line(at)), Nat.is_lt(Nat.add(T.mark.idx(kat), 1024n), T.mark.idx(at)))
525
526def low.stale(low: Maybe<&2, T.Mark>, +at: T.Mark) -> Bool:
527  match low:
528    case None{}:
529      False{}
530    case Some{m}:
531      is_stale(m, at)
532
533def stale.cons(+possible: Bool, required: Bool, number: Nat, +kat: T.Mark, tab: Bool, r: Result<&2, &2, T.Error, List<&2, SKey>>) -> Result<&2, &2, T.Error, List<&2, SKey>>:
534  match r:
535    case Fail{e}:
536      Fail{e}
537    case Done{+ks}:
538      Done{SKey{possible, required, number, kat, tab, low.with(low.of(ks), possible, kat)} <> ks}
539
540# Keys left behind are no longer possible. Keys go stale oldest first, so
541# a level whose oldest possible key is still fresh has nothing stale at or
542# below it, and the search stops there.
543def stale.go(keys: List<&2, SKey>, +at: T.Mark) -> Result<&2, &2, T.Error, List<&2, SKey>>:
544  match keys:
545    case Nil{}:
546      Done{[]}
547    case Con{k, +rest}:
548      match k:
549        case SKey{+possible, +required, +number, +kat, +tab, +low}:
550          +old = Bool.and(possible, is_stale(kat, at))
551          when(Result<&2, &2, T.Error, List<&2, SKey>>, Bool.not(low.stale(low, at)), u => Done{SKey{possible, required, number, kat, tab, low} <> rest},
552            u => when(Result<&2, &2, T.Error, List<&2, SKey>>, Bool.and(old, required),
553              u => Fail{T.Error{"could not find expected ':' while scanning a simple key", kat, T.Syntax{}}},
554              u => stale.cons(Bool.and(possible, Bool.not(old)), required, number, kat, tab, stale.go(rest, at))))
555
556def stale(+st: Sc) -> Step:
557  key.or(stale.go(sc.keys(st), sc.at(st)), st)
558
559def key.cleared(keys: List<&2, SKey>) -> List<&2, SKey>:
560  match keys:
561    case Nil{}:
562      []
563    case Con{k, +rest}:
564      match k:
565        case SKey{possible, required, number, at, tab, low}:
566          SKey{False{}, required, number, at, tab, low.of(rest)} <> rest
567
568def flow.push(st: Sc) -> Sc:
569  match st:
570    case Sc{cur, ind, inds, flow, allowed, tab, +keys, out, n, max}:
571      Sc{cur, ind, inds, 1n+flow, allowed, tab, SKey{False{}, False{}, 0n, T.Mark{0n, 0n, 0n}, False{}, low.of(keys)} <> keys, out, n, max}
572
573def flow.pop(st: Sc) -> Sc:
574  match st:
575    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
576      match flow:
577        case 0n:
578          Sc{cur, ind, inds, 0n, allowed, tab, keys, out, n, max}
579        case 1n+f:
580          Sc{cur, ind, inds, f, allowed, tab, List.drop(&2, SKey, keys, 1n), out, n, max}
581
582# Indentation
583# -----------
584
585def insert.at(d: Nat, out: List<&2, T.Token>, t: T.Token) -> List<&2, T.Token>:
586  match d:
587    case 0n:
588      t <> out
589    case 1n+k:
590      match out:
591        case Nil{}:
592          [t]
593        case Con{h, rest}:
594          h <> insert.at(k, rest, t)
595
596# A token at the end, or (+number+) before the token with that number.
597def insert(out: List<&2, T.Token>, n: Nat, number: Maybe<&2, Nat>, t: T.Token) -> List<&2, T.Token>:
598  match number:
599    case None{}:
600      t <> out
601    case Some{k}:
602      insert.at(Nat.sub(n, k), out, t)
603
604def roll.do(st: Sc, col: Nat, number: Maybe<&2, Nat>, tok: T.Tok, +at: T.Mark) -> Sc:
605  match st:
606    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, +n, max}:
607      Sc{cur, 1n+col, ind <> inds, flow, allowed, tab, keys, insert(out, n, number, T.Token{tok, at, at}), 1n+n, max}
608
609# A block collection starts at +col+ when that's deeper than the indentation.
610def roll(+st: Sc, +col: Nat, number: Maybe<&2, Nat>, tok: T.Tok, at: T.Mark) -> Sc:
611  when(Sc, Bool.and(Nat.is_eq(sc.flow(st), 0n), Nat.is_lt(sc.ind(st), 1n+col)), u => roll.do(st, col, number, tok, at), u => st)
612
613def unroll.go(inds: List<&2, Nat>, +ind: Nat, +lim: Nat, +at: T.Mark, +out: List<&2, T.Token>, +n: Nat) -> Lay:
614  match inds:
615    case Nil{}:
616      Lay{ind, [], out, n}
617    case Con{+h, +t}:
618      when(Lay, Nat.is_gt(ind, lim), u => unroll.go(t, h, lim, at, T.Token{T.BEnd{}, at, at} <> out, 1n+n), u => Lay{ind, h <> t, out, n})
619
620def unrolled(l: Lay, cur: Cur, flow: Nat, allowed: Bool, tab: Bool, keys: List<&2, SKey>, max: Nat) -> Sc:
621  match l:
622    case Lay{ind, inds, out, n}:
623      Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}
624
625def unroll.do(st: Sc, +lim: Nat) -> Sc:
626  match st:
627    case Sc{+cur, ind, inds, flow, allowed, tab, keys, out, n, max}:
628      unrolled(unroll.go(inds, ind, lim, cur.at(cur), out, n), cur, flow, allowed, tab, keys, max)
629
630# Block collections deeper than +lim+ (a column plus one) end.
631def unroll(+st: Sc, +lim: Nat) -> Sc:
632  when(Sc, sc.in_flow(st), u => st, u => unroll.do(st, lim))
633
634def skip.or(eat: Bool, more: Unit -> Skipped, stop: Skipped) -> Skipped:
635  match eat:
636    case True{}:
637      more(Unit{})
638    case False{}:
639      stop
640
641# Blanks, comments and line breaks before a token. A "#" starts a comment
642# after a blank or at a line's start (+gap+). A line break in block context
643# lets a simple key start. Along the way: whether a tab came on the token's
644# line (+tab+), whether a line break came (+nl+), the spaces that start the
645# token's line (+sp+, while +lead+), and whether a tab stood where block
646# indentation belongs (+bad+).
647def skip.go(s: String, +at: T.Mark, +left: Nat, +flow: Bool, +ind: Nat, +allowed: Bool, +comment: Bool, +gap: Bool,
648            +tab: Bool, +nl: Bool, +lead: Bool, +sp: Nat, +bad: Bool) -> Skipped:
649  match s:
650    case SNil{}:
651      Skipped{Cur{SNil{}, at, left}, allowed, tab, nl, sp, False{}}
652    case SCon{+c, +t}:
653      +brk = is_break(c)
654      +space = Char.is_eq(c, ' ')
655      +htab = Char.is_eq(c, '\t')
656      +eat = Bool.or(Bool.or(brk, comment), Bool.or(Bool.or(space, htab), Bool.and(Char.is_eq(c, '#'), gap)))
657      skip.or(eat,
658        u => skip.go(t, past(at, c), Nat.sub(left, 1n), flow, ind, Bool.or(allowed, Bool.and(brk, Bool.not(flow))),
659          Bool.and(Bool.not(brk), Bool.or(comment, Char.is_eq(c, '#'))), True{},
660          Bool.and(Bool.not(brk), Bool.or(tab, htab)), Bool.or(nl, brk), Bool.or(brk, Bool.and(lead, Bool.or(space, htab))),
661          Bool.pick(Nat, brk, 0n, Bool.pick(Nat, Bool.and(Bool.and(lead, space), Bool.not(tab)), 1n+sp, sp)),
662          Bool.and(Bool.not(brk), Bool.or(bad, Bool.and(Bool.and(htab, lead), Bool.and(Bool.not(flow), Nat.is_lt(1n+sp, ind)))))),
663        Skipped{Cur{SCon{c, t}, at, left}, allowed, tab, nl, sp, bad})
664
665def skipped(k: Skipped, st: Sc) -> Sc:
666  match k:
667    case Skipped{cur, allowed, tab, nl, sp, bad}:
668      match st:
669        case Sc{c, ind, inds, flow, a, b, keys, out, n, max}:
670          Sc{cur, ind, inds, flow, allowed, tab, keys, out, n, max}
671
672# Whether the last token was a plain or block scalar, which end past the
673# blanks after them, so a "#" here follows a blank.
674def last.plain(out: List<&2, T.Token>) -> Bool:
675  match out:
676    case Nil{}:
677      False{}
678    case Con{t, rest}:
679      match t:
680        case T.Token{tok, start, end}:
681          match tok:
682            case T.ScalarTok{text, style}:
683              match style:
684                case T.Plain{}:
685                  True{}
686                case T.Literal{}:
687                  True{}
688                case T.Folded{}:
689                  True{}
690                case _:
691                  False{}
692            case _:
693              False{}
694
695# What the skipped whitespace allows: no tab where block indentation
696# belongs, and in flow, lines indented past the block around them.
697def skip.check(k: Skipped, +st: Sc) -> Step:
698  match k:
699    case Skipped{+cur, +allowed, +tab, +nl, +sp, +bad}:
700      +content = Bool.not(is_end(peek(cur.s(cur), 0n)))
701      +at = cur.at(cur)
702      when(Step, Bool.and(bad, content), u => fail(st, "found a tab character where an indentation space is expected", at),
703        u => when(Step, Bool.and(Bool.and(sc.in_flow(st), nl), Bool.and(content, Nat.is_lt(sp, sc.ind(st)))),
704          u => fail(st, "did not find expected indentation in a flow collection", at),
705          u => Go{skipped(Skipped{cur, allowed, tab, nl, sp, bad}, st)}))
706
707def skip.ws.at(c: Cur, +st: Sc) -> Step:
708  match c:
709    case Cur{s, +at, left}:
710      +lead = Nat.is_eq(T.mark.col(at), 0n)
711      skip.check(skip.go(s, at, left, sc.in_flow(st), sc.ind(st), sc.allowed(st), False{}, Bool.or(lead, last.plain(sc.out(st))),
712        False{}, False{}, lead, 0n, False{}), st)
713
714def skip.ws(+st: Sc) -> Step:
715  skip.ws.at(sc.cur(st), st)
716
717# Folded line breaks: one break is a space, more are newlines (less one).
718def folded.breaks(+brks: Nat) -> String:
719  Bool.pick(String, Nat.is_eq(brks, 0n), " ", String.repeat("\n", brks))
720
721# The blanks or breaks before a word join the text.
722def flush(acc: String, ws: String, lead: Bool, +brks: Nat) -> String:
723  match lead:
724    case True{}:
725      folded.breaks(brks) ++ acc
726    case False{}:
727      ws ++ acc
728
729# In a word: a blank ends it; ": " or a flow indicator in flow ends the scalar.
730def pl.word(cur: Cur, +acc: String, +end: T.Mark, +ws: String, +lead: Bool, +brks: Nat, +flow: Bool) -> Pl:
731  match cur:
732    case Cur{+s, +at, +left}:
733      +c = peek(s, 0n)
734      +c1 = peek(s, 1n)
735      +stop = Bool.or(Bool.and(Char.is_eq(c, ':'), Bool.or(is_blankz(c1), Bool.and(flow, is_flow.ind(c1)))), Bool.and(flow, is_flow.ind(c)))
736      Bool.pick(Pl, is_blankz(c), Pl{Cur{s, at, left}, acc, end, ws, lead, brks, False{}, False{}},
737        Bool.pick(Pl, stop, PlDone{Cur{s, at, left}, acc, end, lead},
738          Pl{Cur{String.drop(s, 1n), past(at, c), Nat.sub(left, 1n)}, SCon{c, flush(acc, ws, lead, brks)}, past(at, c), "", False{}, 0n, True{}, False{}}))
739
740# Between words: blanks and breaks wait to join the text; then the next word
741# starts, unless the scalar ended (less indented, a document marker, a
742# comment, or the end). A tab may not stand where indentation belongs on a
743# line that goes on.
744def pl.blank(cur: Cur, +acc: String, +end: T.Mark, +ws: String, +lead: Bool, +brks: Nat, +bad: Bool, +ind: Nat, +flow: Bool, +start: T.Mark) -> Pl:
745  match cur:
746    case Cur{+s, +at, +left}:
747      +c = peek(s, 0n)
748      +next = {Cur{String.drop(s, 1n), past(at, c), Nat.sub(left, 1n)} : Cur}
749      +here = {Cur{s, at, left} : Cur}
750      +col = T.mark.col(at)
751      +done = Bool.or(Bool.or(is_end(c), Bool.and(Bool.not(flow), Nat.is_lt(col, ind))),
752        Bool.or(Bool.and(Nat.is_eq(col, 0n), is_marker(s)), Char.is_eq(c, '#')))
753      +tabbed = Bool.and(Bool.and(lead, Char.is_eq(c, '\t')), Nat.is_lt(col, ind))
754      Bool.pick(Pl, is_blank(c), Pl{next, acc, end, Bool.pick(String, lead, ws, SCon{c, ws}), lead, brks, False{}, Bool.or(bad, tabbed)},
755        Bool.pick(Pl, is_break(c), Pl{next, acc, end, Bool.pick(String, lead, ws, ""), True{}, Bool.pick(Nat, lead, 1n+brks, brks), False{}, False{}},
756          Bool.pick(Pl, done, PlDone{here, acc, end, lead},
757            Bool.pick(Pl, bad, PlBad{T.Error{"found a tab character that violates indentation while scanning a plain scalar", start, T.Syntax{}}},
758              Pl{here, acc, end, ws, lead, brks, True{}, False{}}))))
759
760def pl.step(p: Pl, +ind: Nat, +flow: Bool, +start: T.Mark) -> Pl:
761  match p:
762    case Pl{cur, acc, end, ws, lead, brks, word, bad}:
763      match word:
764        case True{}:
765          pl.word(cur, acc, end, ws, lead, brks, flow)
766        case False{}:
767          pl.blank(cur, acc, end, ws, lead, brks, bad, ind, flow, start)
768    case _:
769      p
770
771def pl.run(fuel: Nat, +ind: Nat, +flow: Bool, +start: T.Mark, p: Pl) -> Pl:
772  match fuel:
773    case 0n:
774      p
775    case 1n+k:
776      match p:
777        case Pl{cur, acc, end, ws, lead, brks, word, bad}:
778          pl.run(k, ind, flow, start, pl.step(Pl{cur, acc, end, ws, lead, brks, word, bad}, ind, flow, start))
779        case _:
780          p
781
782def plain.done(p: Pl, +st: Sc, start: T.Mark) -> Step:
783  match p:
784    case PlDone{cur, acc, end, lead}:
785      Go{sc.allow(emit.span(sc.with.cur(st, cur), T.ScalarTok{String.reverse(acc), T.Plain{}}, start, end), lead)}
786    case PlBad{e}:
787      fail.with(st, e)
788    case Pl{cur, acc, end, ws, lead, brks, word, bad}:
789      Go{sc.allow(emit.span(sc.with.cur(st, cur), T.ScalarTok{String.reverse(acc), T.Plain{}}, start, end), lead)}
790
791def plain.scan(+st: Sc) -> Step:
792  +cur = sc.cur(st)
793  +at = cur.at(cur)
794  plain.done(pl.run(Nat.add(Nat.mul(cur.left(cur), 2n), 4n), sc.ind(st), sc.in_flow(st), at, Pl{cur, "", at, "", False{}, 0n, True{}, False{}}), st, at)
795
796def plain(+st: Sc) -> Step:
797  then(save.key(st), st => plain.scan(sc.allow(st, False{})))
798
799def q.text(cur: Cur, acc: String) -> Qs:
800  Qs{cur, acc, "", False{}, 0n, False{}, True{}, False{}}
801
802def simple.escape(e: Char) -> Maybe<&2, Char>:
803  match e:
804    case '0':
805      Some{Chr{0}}
806    case 'a':
807      Some{Chr{7}}
808    case 'b':
809      Some{Chr{8}}
810    case 't':
811      Some{Chr{9}}
812    case '\t':
813      Some{Chr{9}}
814    case 'n':
815      Some{Chr{10}}
816    case 'v':
817      Some{Chr{11}}
818    case 'f':
819      Some{Chr{12}}
820    case 'r':
821      Some{Chr{13}}
822    case 'e':
823      Some{Chr{27}}
824    case ' ':
825      Some{' '}
826    case '"':
827      Some{'"'}
828    case '/':
829      Some{'/'}
830    case '\\':
831      Some{'\\'}
832    case 'N':
833      Some{Chr{133}}
834    case '_':
835      Some{Chr{160}}
836    case 'L':
837      Some{Chr{8232}}
838    case 'P':
839      Some{Chr{8233}}
840    case _:
841      None{}
842
843def q.simple(m: Maybe<&2, Char>, cur: Cur, acc: String, start: T.Mark) -> Qs:
844  match m:
845    case None{}:
846      QsBad{T.Error{"found unknown escape character while parsing a quoted scalar", start, T.Syntax{}}}
847    case Some{c}:
848      q.text(adv.n(2n, cur), SCon{c, acc})
849
850# A code point that is a character: not a surrogate, and at most 10FFFF.
851def is_scalar.value(+x: U32) -> Bool:
852  Bool.and(Bool.not(between(x, 55296, 57343)), U32.is_le(x, 1114111))
853
854# \x, \u or \U and +n+ hex digits.
855def q.hex(+n: Nat, +cur: Cur, acc: String, +start: T.Mark) -> Qs:
856  +digits = String.take(String.drop(cur.s(cur), 2n), n)
857  +x = hex.value(digits, 0)
858  Bool.pick(Qs, Bool.not(Bool.and(Nat.is_eq(String.length(digits), n), all.hex(digits))),
859    QsBad{T.Error{"did not find expected hexdecimal number while parsing a quoted scalar", start, T.Syntax{}}},
860    Bool.pick(Qs, Bool.not(is_scalar.value(x)),
861      QsBad{T.Error{"found invalid Unicode character escape code while parsing a quoted scalar", start, T.Syntax{}}},
862      q.text(adv.n(Nat.add(n, 2n), cur), SCon{Chr{x}, acc})))
863
864def q.escape(e: Char, cur: Cur, acc: String, start: T.Mark) -> Qs:
865  match e:
866    case '\n':
867      Qs{adv.n(2n, cur), acc, "", True{}, 0n, True{}, False{}, False{}}
868    case 'x':
869      q.hex(2n, cur, acc, start)
870    case 'u':
871      q.hex(4n, cur, acc, start)
872    case 'U':
873      q.hex(8n, cur, acc, start)
874    case _:
875      q.simple(simple.escape(e), cur, acc, start)
876
877def q.char(double: Bool, c: Char, +c1: Char, +cur: Cur, +acc: String, start: T.Mark) -> Qs:
878  match double:
879    case False{}:
880      match c:
881        case '\'':
882          Bool.pick(Qs, Char.is_eq(c1, '\''), q.text(adv.n(2n, cur), SCon{'\'', acc}), QsDone{adv(cur), acc})
883        case _:
884          q.text(adv(cur), SCon{c, acc})
885    case True{}:
886      match c:
887        case '"':
888          QsDone{adv(cur), acc}
889        case '\\':
890          q.escape(c1, cur, acc, start)
891        case _:
892          q.text(adv(cur), SCon{c, acc})
893
894def q.in.text(+double: Bool, +cur: Cur, +acc: String, +start: T.Mark) -> Qs:
895  +s = cur.s(cur)
896  +c = peek(s, 0n)
897  Bool.pick(Qs, Bool.and(Nat.is_eq(cur.col(cur), 0n), is_marker(s)),
898    QsBad{T.Error{"found unexpected document indicator while scanning a quoted scalar", start, T.Syntax{}}},
899    Bool.pick(Qs, is_end(c), QsBad{T.Error{"found unexpected end of stream while scanning a quoted scalar", start, T.Syntax{}}},
900      Bool.pick(Qs, Bool.or(is_blank(c), is_break(c)), Qs{cur, acc, "", False{}, 0n, False{}, False{}, False{}},
901        q.char(double, c, peek(s, 1n), cur, acc, start))))
902
903# The blanks and breaks between text: kept, or folded, once text resumes.
904def q.joined(+acc: String, ws: String, lead: Bool, +brks: Nat, esc: Bool) -> String:
905  match lead:
906    case False{}:
907      ws ++ acc
908    case True{}:
909      Bool.pick(String, esc, String.repeat("\n", brks), folded.breaks(brks)) ++ acc
910
911# Between text: blanks and breaks wait to join it. A line after a break
912# must be indented past the block around it (+ind+), with spaces.
913def q.in.blanks(+cur: Cur, +acc: String, +ws: String, +lead: Bool, +brks: Nat, +esc: Bool, +bad: Bool, +ind: Nat, +start: T.Mark) -> Qs:
914  +c = peek(cur.s(cur), 0n)
915  +shallow = Nat.is_lt(cur.col(cur), ind)
916  Bool.pick(Qs, is_blank(c), Qs{adv(cur), acc, Bool.pick(String, lead, ws, SCon{c, ws}), lead, brks, esc, False{}, Bool.or(bad, Bool.and(lead, Bool.and(shallow, Char.is_eq(c, '\t'))))},
917    Bool.pick(Qs, is_break(c), Qs{adv(cur), acc, "", True{}, Bool.pick(Nat, lead, 1n+brks, 0n), esc, False{}, False{}},
918      Bool.pick(Qs, Bool.and(lead, Bool.and(Bool.not(is_end(c)), Bool.or(bad, shallow))),
919        QsBad{T.Error{"found a line indented too little in a quoted scalar while scanning a quoted scalar", start, T.Syntax{}}},
920        q.text(cur, q.joined(acc, ws, lead, brks, esc)))))
921
922def q.step(q: Qs, +double: Bool, +ind: Nat, +start: T.Mark) -> Qs:
923  match q:
924    case Qs{cur, acc, ws, lead, brks, esc, text, bad}:
925      match text:
926        case True{}:
927          q.in.text(double, cur, acc, start)
928        case False{}:
929          q.in.blanks(cur, acc, ws, lead, brks, esc, bad, ind, start)
930    case _:
931      q
932
933def q.run(fuel: Nat, +double: Bool, +ind: Nat, +start: T.Mark, q: Qs) -> Qs:
934  match fuel:
935    case 0n:
936      q
937    case 1n+k:
938      match q:
939        case Qs{cur, acc, ws, lead, brks, esc, text, bad}:
940          q.run(k, double, ind, start, q.step(Qs{cur, acc, ws, lead, brks, esc, text, bad}, double, ind, start))
941        case _:
942          q
943
944def quoted.done(q: Qs, +st: Sc, +double: Bool, start: T.Mark) -> Step:
945  match q:
946    case QsDone{cur, acc}:
947      Go{emit(sc.with.cur(st, cur), T.ScalarTok{String.reverse(acc), Bool.pick(T.Style, double, T.Double{}, T.Single{})}, start)}
948    case QsBad{e}:
949      fail.with(st, e)
950    case _:
951      fail(st, "found unexpected end of stream while scanning a quoted scalar", start)
952
953def quoted.scan(+st: Sc, +double: Bool) -> Step:
954  +cur = sc.cur(st)
955  +at = cur.at(cur)
956  quoted.done(q.run(Nat.add(Nat.mul(cur.left(cur), 2n), 4n), double, sc.ind(st), at, q.text(adv(cur), "")), st, double, at)
957
958def quoted(+st: Sc, +double: Bool) -> Step:
959  then(save.key(st), st => quoted.scan(sc.allow(st, False{}), double))
960
961def digit.value(c: Char) -> Nat:
962  U32.to_nat(U32.sub(code(c), 48))
963
964def chomp.of(c: Char) -> Maybe<&2, Chomp>:
965  match c:
966    case '+':
967      Some{Keep{}}
968    case '-':
969      Some{Strip{}}
970    case _:
971      None{}
972
973def chomp.or(m: Maybe<&2, Chomp>, d: Chomp) -> Chomp:
974  match m:
975    case None{}:
976      d
977    case Some{c}:
978      c
979
980def is_some.chomp(m: Maybe<&2, Chomp>) -> Bool:
981  match m:
982    case None{}:
983      False{}
984    case Some{c}:
985      True{}
986
987# Past blanks and a comment (after a blank), to a line break or the end.
988def head.tail(s: String, +at: T.Mark, +left: Nat, +comment: Bool, +gap: Bool) -> Cur:
989  match s:
990    case SNil{}:
991      Cur{SNil{}, at, left}
992    case SCon{+c, +t}:
993      +hash = Bool.and(Char.is_eq(c, '#'), gap)
994      when(Cur, Bool.or(is_break(c), Bool.not(Bool.or(comment, Bool.or(is_blank(c), hash)))), u => Cur{SCon{c, t}, at, left},
995        u => head.tail(t, past(at, c), Nat.sub(left, 1n), Bool.or(comment, hash), is_blank(c)))
996
997def head.check(chomp: Chomp, +inc: Nat, +cur: Cur) -> Head:
998  Bool.pick(Head, is_breakz(peek(cur.s(cur), 0n)), Head{chomp, inc, adv(cur)}, HeadBad{"did not find expected comment or line break while scanning a block scalar"})
999
1000def head.end(chomp: Chomp, +inc: Nat, cur: Cur) -> Head:
1001  match cur:
1002    case Cur{s, at, left}:
1003      head.check(chomp, inc, head.tail(s, at, left, False{}, False{}))
1004
1005# The indicators after "|" or ">", in either order.
1006def header(+cur: Cur) -> Head:
1007  +s = cur.s(cur)
1008  +c0 = peek(s, 0n)
1009  +c1 = peek(s, 1n)
1010  +ch0 = chomp.of(c0)
1011  +ch1 = chomp.of(c1)
1012  +d0 = Bool.and(Char.is_digit(c0), Bool.not(Char.is_eq(c0, '0')))
1013  +d1 = Bool.and(Char.is_digit(c1), Bool.not(Char.is_eq(c1, '0')))
1014  when(Head, Bool.or(Char.is_eq(c0, '0'), Bool.and(is_some.chomp(ch0), Char.is_eq(c1, '0'))),
1015    u => HeadBad{"found an indentation indicator equal to 0 while scanning a block scalar"},
1016    u => when(Head, Bool.and(is_some.chomp(ch0), d1), u => head.end(chomp.or(ch0, Clip{}), digit.value(c1), adv.n(2n, cur)),
1017      u => when(Head, is_some.chomp(ch0), u => head.end(chomp.or(ch0, Clip{}), 0n, adv(cur)),
1018        u => when(Head, Bool.and(d0, is_some.chomp(ch1)), u => head.end(chomp.or(ch1, Clip{}), digit.value(c0), adv.n(2n, cur)),
1019          u => when(Head, d0, u => head.end(Clip{}, digit.value(c0), adv(cur)), u => head.end(Clip{}, 0n, cur))))))
1020
1021# Blank lines and the indentation before content. The first content line
1022# sets the indentation when the header didn't; no blank line before it may
1023# be deeper. A tab may start content but not indentation. A last line of
1024# spaces with no break after it still counts as a line.
1025def bs.breaks(+cur: Cur, +acc: String, +ind: Nat, +max: Nat, +lead: Bool, +lblank: Bool, +brks: Nat, +pind: Nat, +start: T.Mark) -> Bs:
1026  +c = peek(cur.s(cur), 0n)
1027  +col = cur.col(cur)
1028  +inside = Bool.or(Nat.is_eq(ind, 0n), Nat.is_lt(1n+col, ind))
1029  +first = Bool.and(Nat.is_eq(ind, 0n), Nat.is_ge(col, pind))
1030  +partial = Bool.and(Nat.is_gt(col, 0n), Nat.is_gt(T.mark.line(cur.at(cur)), T.mark.line(start)))
1031  Bool.pick(Bs, Bool.and(Char.is_eq(c, ' '), inside), Bs{adv(cur), acc, ind, max, lead, lblank, brks, Breaks{}},
1032    Bool.pick(Bs, is_break(c), Bs{adv(cur), acc, ind, Nat.max(col, max), lead, lblank, 1n+brks, Breaks{}},
1033      Bool.pick(Bs, is_end(c), Bs{cur, acc, ind, max, lead, lblank, Bool.pick(Nat, partial, 1n+brks, brks), LineStart{}},
1034        Bool.pick(Bs, Bool.and(Bool.and(Char.is_eq(c, '\t'), inside), Bool.not(first)),
1035          BsBad{T.Error{"found a tab character where an indentation space is expected while scanning a block scalar", start, T.Syntax{}}},
1036          Bool.pick(Bs, Bool.and(first, Nat.is_gt(max, col)),
1037            BsBad{T.Error{"found a leading blank line with more spaces than the first content line while scanning a block scalar", start, T.Syntax{}}},
1038            Bs{cur, acc, Bool.pick(Nat, Nat.is_eq(ind, 0n), 1n+Nat.max(col, pind), ind), max, lead, lblank, brks, LineStart{}})))))
1039
1040# A content line starts at the indentation: what waits joins the text.
1041def bs.line(+cur: Cur, +acc: String, +ind: Nat, +max: Nat, +lead: Bool, +lblank: Bool, +brks: Nat, +folded: Bool) -> Bs:
1042  +s = cur.s(cur)
1043  +c = peek(s, 0n)
1044  +fold = Bool.and(Bool.and(folded, lead), Bool.and(Bool.not(lblank), Bool.not(is_blank(c))))
1045  +joined = String.repeat("\n", brks) ++ Bool.pick(String, fold, Bool.pick(String, Nat.is_eq(brks, 0n), " ", ""), Bool.pick(String, lead, "\n", "")) ++ acc
1046  Bool.pick(Bs, Bool.or(Bool.not(Nat.is_eq(1n+cur.col(cur), ind)), Bool.or(is_end(c), Bool.and(Nat.is_eq(cur.col(cur), 0n), is_marker(s)))),
1047    BsDone{acc, lead, brks, cur},
1048    Bs{cur, joined, ind, max, False{}, is_blank(c), 0n, Content{}})
1049
1050def bs.content(+cur: Cur, +acc: String, +ind: Nat, +max: Nat, +lblank: Bool) -> Bs:
1051  +c = peek(cur.s(cur), 0n)
1052  Bool.pick(Bs, is_end(c), BsDone{acc, True{}, 0n, cur},
1053    Bool.pick(Bs, is_break(c), Bs{adv(cur), acc, ind, max, True{}, lblank, 0n, Breaks{}},
1054      Bs{adv(cur), SCon{c, acc}, ind, max, False{}, lblank, 0n, Content{}}))
1055
1056def bs.step(b: Bs, +folded: Bool, +pind: Nat, +start: T.Mark) -> Bs:
1057  match b:
1058    case Bs{cur, acc, ind, max, lead, lblank, brks, phase}:
1059      match phase:
1060        case Breaks{}:
1061          bs.breaks(cur, acc, ind, max, lead, lblank, brks, pind, start)
1062        case LineStart{}:
1063          bs.line(cur, acc, ind, max, lead, lblank, brks, folded)
1064        case Content{}:
1065          bs.content(cur, acc, ind, max, lblank)
1066    case _:
1067      b
1068
1069def bs.run(fuel: Nat, +folded: Bool, +pind: Nat, +start: T.Mark, b: Bs) -> Bs:
1070  match fuel:
1071    case 0n:
1072      b
1073    case 1n+k:
1074      match b:
1075        case Bs{cur, acc, ind, max, lead, lblank, brks, phase}:
1076          bs.run(k, folded, pind, start, bs.step(Bs{cur, acc, ind, max, lead, lblank, brks, phase}, folded, pind, start))
1077        case _:
1078          b
1079
1080# The final line break and the blank lines after the text.
1081def chomped(chomp: Chomp, +acc: String, +lead: Bool, +brks: Nat) -> String:
1082  match chomp:
1083    case Clip{}:
1084      Bool.pick(String, lead, SCon{'\n', acc}, acc)
1085    case Strip{}:
1086      acc
1087    case Keep{}:
1088      String.repeat("\n", brks) ++ Bool.pick(String, lead, SCon{'\n', acc}, acc)
1089
1090def block.done(b: Bs, chomp: Chomp, +st: Sc, +folded: Bool, start: T.Mark) -> Step:
1091  match b:
1092    case BsDone{acc, lead, brks, cur}:
1093      Go{emit(sc.with.cur(st, cur), T.ScalarTok{String.reverse(chomped(chomp, acc, lead, brks)), Bool.pick(T.Style, folded, T.Folded{}, T.Literal{})}, start)}
1094    case BsBad{e}:
1095      fail.with(st, e)
1096    case _:
1097      fail(st, "found unexpected end of stream while scanning a block scalar", start)
1098
1099def block.body(h: Head, +st: Sc, +folded: Bool, +start: T.Mark) -> Step:
1100  match h:
1101    case Head{chomp, +inc, +cur}:
1102      +pind = sc.ind(st)
1103      +given = Nat.add(pind, inc)
1104      block.done(bs.run(Nat.add(Nat.mul(cur.left(cur), 3n), 4n), folded, pind, start,
1105        Bs{cur, "", Bool.pick(Nat, Nat.is_eq(inc, 0n), 0n, given), 0n, False{}, False{}, 0n, Breaks{}}), chomp, st, folded, start)
1106    case HeadBad{why}:
1107      fail(st, why, start)
1108
1109def block.scan(+st: Sc, +folded: Bool) -> Step:
1110  +cur = sc.cur(st)
1111  block.body(header(adv(cur)), st, folded, cur.at(cur))
1112
1113def block.scalar(+st: Sc, +folded: Bool) -> Step:
1114  then(remove.key(st), st => block.scan(sc.allow(st, True{}), folded))
1115
1116def taken.cons(c: Char, +k: Nat, t: Taken) -> Taken:
1117  match t:
1118    case Taken{text, n}:
1119      Taken{SCon{c, text}, Nat.add(k, n)}
1120
1121def took.or(stop: Bool, more: Unit -> Taken) -> Taken:
1122  match stop:
1123    case True{}:
1124      Taken{"", 0n}
1125    case False{}:
1126      more(Unit{})
1127
1128# An anchor's name: anything up to a blank, a break or a flow indicator.
1129def anchor.name(s: String) -> Taken:
1130  match s:
1131    case SNil{}:
1132      Taken{"", 0n}
1133    case SCon{+c, t}:
1134      took.or(Bool.or(is_blankz(c), is_flow.ind(c)), u => taken.cons(c, 1n, anchor.name(t)))
1135
1136def anchor.took(t: Taken, +st: Sc, +is_anchor: Bool, +at: T.Mark) -> Step:
1137  match t:
1138    case Taken{+name, +n}:
1139      when(Step, String.is_empty(name),
1140        u => fail(st, Bool.pick(String, is_anchor, "did not find expected alphabetic or numeric character while scanning an anchor",
1141          "did not find expected alphabetic or numeric character while scanning an alias"), at),
1142        u => Go{emit(skip(st, 1n+n), Bool.pick(T.Tok, is_anchor, T.AnchorTok{name}, T.AliasTok{name}), at)})
1143
1144def anchor.scan(+st: Sc, +is_anchor: Bool) -> Step:
1145  +at = sc.at(st)
1146  anchor.took(anchor.name(String.drop(sc.s(st), 1n)), st, is_anchor, at)
1147
1148def anchor(+st: Sc, +is_anchor: Bool) -> Step:
1149  then(save.key(st), st => anchor.scan(sc.allow(st, False{}), is_anchor))
1150
1151# Tag characters, with %XX escapes decoded; +uri+ allows all URI characters
1152# (in a verbatim tag or a %TAG prefix).
1153def taken.skip(t: Taken) -> Taken:
1154  match t:
1155    case Taken{text, n}:
1156      Taken{text, 1n+n}
1157
1158def tag.chars(s: String, +uri: Bool, +pending: Nat) -> Taken:
1159  match s:
1160    case SNil{}:
1161      Taken{"", 0n}
1162    case SCon{+c, +t}:
1163      match pending:
1164        case 1n+k:
1165          taken.skip(tag.chars(t, uri, k))
1166        case 0n:
1167          +esc = Bool.and(Char.is_eq(c, '%'), Bool.and(is_hex(peek(t, 0n)), is_hex(peek(t, 1n))))
1168          +ok = Bool.pick(Bool, uri, is_uri(c), is_tag(c))
1169          took.or(Bool.not(Bool.or(esc, ok)),
1170            u => taken.cons(Bool.pick(Char, esc, Chr{hex.value(String.take(t, 2n), 0)}, c), 1n,
1171              tag.chars(t, uri, Bool.pick(Nat, esc, 2n, 0n))))
1172
1173# What may follow a tag: a blank, a break, the end, or in flow a flow
1174# indicator.
1175def tag.ends(+c: Char, +flow: Bool) -> Bool:
1176  Bool.or(is_blankz(c), Bool.and(flow, is_flow.ind(c)))
1177
1178def tag.emit(+st: Sc, handle: String, suffix: String, +n: Nat, +at: T.Mark) -> Step:
1179  +st2 = skip(st, n)
1180  +next = peek(sc.s(st2), 0n)
1181  when(Step, tag.ends(next, sc.in_flow(st2)),
1182    u => Go{emit(st2, T.TagTok{handle, suffix}, at)},
1183    u => fail(st2, Bool.pick(String, Char.is_eq(next, '%'), "did not find URI escaped octet while parsing a tag",
1184      "did not find expected whitespace or line break while scanning a tag"), at))
1185
1186# "!<uri>".
1187def tag.verbatim(t: Taken, +st: Sc, +at: T.Mark) -> Step:
1188  match t:
1189    case Taken{+uri, +n}:
1190      when(Step, Bool.or(String.is_empty(uri), Bool.not(Char.is_eq(peek(String.drop(sc.s(st), Nat.add(n, 2n)), 0n), '>'))),
1191        u => fail(st, "did not find the expected '>' while scanning a tag", at),
1192        u => tag.emit(st, "", uri, Nat.add(n, 3n), at))
1193
1194def tag.suffix(t: Taken, +named: Bool, +word: String, +k: Nat, +st: Sc, +at: T.Mark) -> Step:
1195  match t:
1196    case Taken{+suffix, +n}:
1197      +handle = Bool.pick(String, named, "!" ++ word ++ "!", "!")
1198      +used = Nat.add(1n, Bool.pick(Nat, named, Nat.add(1n+k, n), n))
1199      when(Step, Bool.and(named, String.is_empty(suffix)),
1200        u => fail(st, "did not find expected tag URI while parsing a tag", at),
1201        u => when(Step, String.is_empty(suffix), u => tag.emit(st, "", "!", used, at), u => tag.emit(st, handle, suffix, used, at)))
1202
1203# "!suffix", "!!suffix", "!name!suffix", or "!" alone.
1204def tag.short(w: Taken, +st: Sc, +at: T.Mark) -> Step:
1205  match w:
1206    case Taken{+word, +k}:
1207      +s = String.drop(sc.s(st), 1n)
1208      +named = Char.is_eq(peek(s, k), '!')
1209      tag.suffix(tag.chars(String.drop(s, Bool.pick(Nat, named, 1n+k, 0n)), False{}, 0n), named, word, k, st, at)
1210
1211def word.chars(s: String) -> Taken:
1212  match s:
1213    case SNil{}:
1214      Taken{"", 0n}
1215    case SCon{+c, t}:
1216      took.or(Bool.not(is_word(c)), u => taken.cons(c, 1n, word.chars(t)))
1217
1218def tag.scan(+st: Sc) -> Step:
1219  +s = sc.s(st)
1220  +at = sc.at(st)
1221  when(Step, Char.is_eq(peek(s, 1n), '<'),
1222    u => tag.verbatim(tag.chars(String.drop(s, 2n), True{}, 0n), st, at),
1223    u => tag.short(word.chars(String.drop(s, 1n)), st, at))
1224
1225def tag(+st: Sc) -> Step:
1226  then(save.key(st), st => tag.scan(sc.allow(st, False{})))
1227
1228# Directives
1229# ----------
1230
1231def count.or(go: Bool, more: Unit -> Nat) -> Nat:
1232  match go:
1233    case True{}:
1234      more(Unit{})
1235    case False{}:
1236      0n
1237
1238def blanks(s: String) -> Nat:
1239  match s:
1240    case SNil{}:
1241      0n
1242    case SCon{+c, t}:
1243      count.or(is_blank(c), u => 1n+blanks(t))
1244
1245def digits(s: String) -> Taken:
1246  match s:
1247    case SNil{}:
1248      Taken{"", 0n}
1249    case SCon{+c, t}:
1250      took.or(Bool.not(Char.is_digit(c)), u => taken.cons(c, 1n, digits(t)))
1251
1252def nat.of(s: String, acc: Nat) -> Nat:
1253  match s:
1254    case SNil{}:
1255      acc
1256    case SCon{c, t}:
1257      nat.of(t, Nat.add(Nat.mul(acc, 10n), digit.value(c)))
1258
1259def directive.put(+st: Sc, tok: Maybe<&2, T.Tok>, at: T.Mark) -> Sc:
1260  match tok:
1261    case None{}:
1262      st
1263    case Some{t}:
1264      emit(st, t, at)
1265
1266def directive.tail(+cur: Cur, +st: Sc, tok: Maybe<&2, T.Tok>, +at: T.Mark) -> Step:
1267  when(Step, is_breakz(peek(cur.s(cur), 0n)),
1268    u => Go{directive.put(sc.with.cur(st, cur), tok, at)},
1269    u => fail(st, "did not find expected comment or line break while scanning a directive", at))
1270
1271# After a directive: blanks, a comment, then a line break or the end.
1272def directive.end(+st: Sc, tok: Maybe<&2, T.Tok>, at: T.Mark) -> Step:
1273  directive.tail(head.tail(sc.s(st), sc.at(st), cur.left(sc.cur(st)), False{}, False{}), st, tok, at)
1274
1275def version.done(m: Taken, +st: Sc, major: String, +used: Nat, +at: T.Mark) -> Step:
1276  match m:
1277    case Taken{+minor, +k}:
1278      when(Step, Nat.is_eq(k, 0n), u => fail(st, "did not find expected digit or '.' character while scanning a %YAML directive", at),
1279        u => directive.end(skip(st, Nat.add(used, k)), Some{T.VersionDir{nat.of(major, 0n), nat.of(minor, 0n)}}, at))
1280
1281def version.minor(m: Taken, +st: Sc, +b: Nat, +at: T.Mark) -> Step:
1282  match m:
1283    case Taken{+major, +k}:
1284      +rest = String.drop(sc.s(st), Nat.add(b, k))
1285      +minor = digits(String.drop(rest, 1n))
1286      when(Step, Nat.is_eq(b, 0n), u => fail(st, "did not find expected whitespace while scanning a %YAML directive", at),
1287        u => when(Step, Bool.or(Nat.is_eq(k, 0n), Bool.not(Char.is_eq(peek(rest, 0n), '.'))),
1288          u => fail(st, "did not find expected digit or '.' character while scanning a %YAML directive", at),
1289          u => version.done(minor, st, major, Nat.add(b, Nat.add(k, 1n)), at)))
1290
1291# "%YAML 1.2".
1292def version.scan(+st: Sc, +at: T.Mark) -> Step:
1293  +s = sc.s(st)
1294  +b = blanks(s)
1295  +major = digits(String.drop(s, b))
1296  version.minor(major, st, b, at)
1297
1298def tagdir.prefix(p: Taken, +st: Sc, handle: String, +used: Nat, +at: T.Mark) -> Step:
1299  match p:
1300    case Taken{+prefix, +k}:
1301      when(Step, Nat.is_eq(k, 0n), u => fail(st, "did not find expected tag URI while scanning a %TAG directive", at),
1302        u => directive.end(skip(st, Nat.add(used, k)), Some{T.TagDir{handle, prefix}}, at))
1303
1304def tagdir.handle(w: Taken, +st: Sc, +b: Nat, +at: T.Mark) -> Step:
1305  match w:
1306    case Taken{+word, +k}:
1307      +rest = String.drop(sc.s(st), b)
1308      +closed = Char.is_eq(peek(rest, 1n+k), '!')
1309      +hlen = Nat.add(1n+k, Bool.pick(Nat, closed, 1n, 0n))
1310      +handle = String.take(rest, hlen)
1311      +b2 = blanks(String.drop(rest, hlen))
1312      +ok = Bool.and(Char.is_eq(peek(rest, 0n), '!'), Bool.or(closed, Nat.is_eq(k, 0n)))
1313      when(Step, Bool.or(Nat.is_eq(b, 0n), Bool.not(ok)), u => fail(st, "did not find expected '!' while scanning a %TAG directive", at),
1314        u => when(Step, Nat.is_eq(b2, 0n), u => fail(st, "did not find expected whitespace while scanning a %TAG directive", at),
1315          u => tagdir.prefix(tag.chars(String.drop(rest, Nat.add(hlen, b2)), True{}, 0n), st, handle, Nat.add(b, Nat.add(hlen, b2)), at)))
1316
1317# "%TAG !e! prefix".
1318def tagdir.scan(+st: Sc, +at: T.Mark) -> Step:
1319  +s = sc.s(st)
1320  +b = blanks(s)
1321  +rest = String.drop(s, b)
1322  tagdir.handle(word.chars(String.drop(rest, 1n)), st, b, at)
1323
1324# Past the rest of a line.
1325def line.rest(s: String) -> Nat:
1326  match s:
1327    case SNil{}:
1328      0n
1329    case SCon{+c, t}:
1330      count.or(Bool.not(is_break(c)), u => 1n+line.rest(t))
1331
1332# %YAML, %TAG, or a reserved directive, which is skipped.
1333def directive.named(+name: String, +st: Sc, +at: T.Mark) -> Step:
1334  when(Step, String.eq(name, "YAML"), u => version.scan(st, at),
1335    u => when(Step, String.eq(name, "TAG"), u => tagdir.scan(st, at),
1336      u => Go{skip(st, line.rest(sc.s(st)))}))
1337
1338def directive.name(w: Taken, +st: Sc, +at: T.Mark) -> Step:
1339  match w:
1340    case Taken{+name, +k}:
1341      when(Step, Nat.is_eq(k, 0n), u => fail(st, "could not find expected directive name while scanning a directive", at),
1342        u => directive.named(name, skip(st, 1n+k), at))
1343
1344def directive.scan(+st: Sc) -> Step:
1345  +at = sc.at(st)
1346  directive.name(word.chars(String.drop(sc.s(st), 1n)), st, at)
1347
1348def directive(+st: Sc) -> Step:
1349  then(remove.key(unroll(st, 0n)), st => directive.scan(sc.allow(st, False{})))
1350
1351# Tokens
1352# ------
1353
1354# "[" or "{", unless flow collections already nest as deep as allowed.
1355def flow.start(+st: Sc, t: T.Tok) -> Step:
1356  when(Step, Nat.is_ge(sc.flow(st), sc.max(st)), u => fail.limit(st, "found nesting deeper than the depth limit of " ++ Nat.show(sc.max(st))),
1357    u => then(save.key(st), st => Go{single(sc.allow(flow.push(st), True{}), t)}))
1358
1359def flow.end(+st: Sc, t: T.Tok) -> Step:
1360  then(remove.key(st), st => Go{single(sc.allow(flow.pop(st), False{}), t)})
1361
1362def flow.entry(+st: Sc) -> Step:
1363  then(remove.key(st), st => Go{single(sc.allow(st, True{}), T.FEntry{})})
1364
1365def block.entry.rest(+st: Sc) -> Step:
1366  then(remove.key(st), st => Go{single(sc.allow(st, True{}), T.BEntry{})})
1367
1368# "- ": a block sequence's entry, which may open the sequence.
1369def block.entry(+st: Sc) -> Step:
1370  when(Step, sc.in_flow(st), u => block.entry.rest(st),
1371    u => when(Step, sc.tab(st), u => fail(st, "found a tab character that violates indentation", sc.at(st)),
1372    u => when(Step, sc.allowed(st), u => block.entry.rest(roll(st, sc.col(st), None{}, T.BSeqStart{}, sc.at(st))),
1373      u => fail(st, "block sequence entries are not allowed in this context", sc.at(st)))))
1374
1375def key.tok(+st: Sc) -> Sc:
1376  single(sc.allow(st, Bool.not(sc.in_flow(st))), T.KeyTok{})
1377
1378def key.rest(+st: Sc) -> Step:
1379  then(remove.key(st), st => Go{key.tok(st)})
1380
1381# "? ": an explicit key.
1382def key(+st: Sc) -> Step:
1383  when(Step, sc.in_flow(st), u => key.rest(st),
1384    u => when(Step, sc.tab(st), u => fail(st, "found a tab character that violates indentation", sc.at(st)),
1385    u => when(Step, sc.allowed(st), u => key.rest(roll(st, sc.col(st), None{}, T.BMapStart{}, sc.at(st))),
1386      u => fail(st, "mapping keys are not allowed in this context", sc.at(st)))))
1387
1388def value.rest(+st: Sc) -> Sc:
1389  single(sc.allow(st, Bool.not(sc.in_flow(st))), T.ValueTok{})
1390
1391def value.alone(+st: Sc) -> Step:
1392  when(Step, sc.in_flow(st), u => Go{value.rest(st)},
1393    u => when(Step, sc.allowed(st), u => Go{value.rest(roll(st, sc.col(st), None{}, T.BMapStart{}, sc.at(st)))},
1394      u => fail(st, "mapping values are not allowed in this context", sc.at(st))))
1395
1396def insert.key(st: Sc, number: Nat, +at: T.Mark) -> Sc:
1397  match st:
1398    case Sc{cur, ind, inds, flow, allowed, tab, keys, out, +n, max}:
1399      Sc{cur, ind, inds, flow, allowed, tab, key.cleared(keys), insert(out, n, Some{number}, T.Token{T.KeyTok{}, at, at}), 1n+n, max}
1400
1401# ": ": a value. When a simple key waits, it becomes a key: a KeyTok goes
1402# before it, and a block mapping may start at its column.
1403def value.with(k: SKey, +st: Sc) -> Step:
1404  match k:
1405    case SKey{possible, required, +number, +at, tab, low}:
1406      +rolls = Bool.and(Nat.is_eq(sc.flow(st), 0n), Nat.is_lt(sc.ind(st), 1n+T.mark.col(at)))
1407      when(Step, possible,
1408        u => when(Step, Bool.and(tab, rolls), u => fail(st, "found a tab character that violates indentation", at),
1409          u => Go{single(sc.allow(roll(insert.key(st, number, at), T.mark.col(at), Some{number}, T.BMapStart{}, at), False{}), T.ValueTok{})}),
1410        u => value.alone(st))
1411
1412def value(+st: Sc) -> Step:
1413  value.with(key.top(sc.keys(st)), st)
1414
1415def marker.tok(+st: Sc, t: T.Tok) -> Sc:
1416  emit(skip(sc.allow(st, False{}), 3n), t, sc.at(st))
1417
1418# The stream ends on a line of its own.
1419def end.mark(m: T.Mark) -> T.Mark:
1420  match m:
1421    case T.Mark{+line, +col, +idx}:
1422      Bool.pick(T.Mark, Nat.is_eq(col, 0n), T.Mark{line, col, idx}, T.Mark{1n+line, 0n, idx})
1423
1424def end.tok(+st: Sc) -> Sc:
1425  +at = end.mark(sc.at(st))
1426  emit.span(sc.allow(st, False{}), T.StreamEnd{}, at, at)
1427
1428def doc.end.check(+st: Sc, t: T.Tok) -> Step:
1429  match t:
1430    case T.DocEnd{}:
1431      when(Step, is_breakz(peek(cur.s(head.tail(sc.s(st), sc.at(st), cur.left(sc.cur(st)), False{}, False{})), 0n)), u => Go{st},
1432        u => fail(st, "did not find expected comment or line break after a document end marker", sc.at(st)))
1433    case _:
1434      Go{st}
1435
1436def doc.indicator(+st: Sc, +t: T.Tok) -> Step:
1437  then(remove.key(unroll(st, 0n)), st => doc.end.check(marker.tok(st, t), t))
1438
1439def stream.end(+st: Sc) -> Step:
1440  then(remove.key(unroll(st, 0n)), st => Stop{end.tok(st)})
1441
1442def is_plain.start(+c: Char) -> Bool:
1443  Bool.and(is_printable(c), Bool.not(Bool.or(is_blankz(c), is_in(c, "-?:,[]{}#&*!|>'\"%@`"))))
1444
1445# The token a character starts.
1446def fetch.char(c: Char, +c1: Char, +flow: Bool, +st: Sc) -> Step:
1447  match c:
1448    case '[':
1449      flow.start(st, T.FSeqStart{})
1450    case '{':
1451      flow.start(st, T.FMapStart{})
1452    case ']':
1453      flow.end(st, T.FSeqEnd{})
1454    case '}':
1455      flow.end(st, T.FMapEnd{})
1456    case ',':
1457      flow.entry(st)
1458    case '-':
1459      when(Step, is_blankz(c1), u => block.entry(st), u => when(Step, Bool.and(flow, is_flow.ind(c1)), u => cannot(st), u => plain(st)))
1460    case '?':
1461      when(Step, Bool.or(is_blankz(c1), Bool.and(flow, is_flow.ind(c1))), u => key(st), u => plain(st))
1462    case ':':
1463      when(Step, Bool.or(is_blankz(c1), Bool.and(flow, Bool.or(is_flow.ind(c1), json.before(sc.out(st))))), u => value(st), u => plain(st))
1464    case '*':
1465      anchor(st, False{})
1466    case '&':
1467      anchor(st, True{})
1468    case '!':
1469      tag(st)
1470    case '|':
1471      when(Step, flow, u => cannot(st), u => block.scalar(st, False{}))
1472    case '>':
1473      when(Step, flow, u => cannot(st), u => block.scalar(st, True{}))
1474    case '\'':
1475      quoted(st, False{})
1476    case '"':
1477      quoted(st, True{})
1478    case _:
1479      when(Step, is_plain.start(c), u => plain(st), u => cannot(st))
1480
1481def fetch.next(+st: Sc) -> Step:
1482  +s = sc.s(st)
1483  +c = peek(s, 0n)
1484  +col0 = Nat.is_eq(sc.col(st), 0n)
1485  when(Step, String.is_empty(s), u => stream.end(st),
1486    u => when(Step, Bool.and(col0, Char.is_eq(c, '%')), u => directive(st),
1487      u => when(Step, Bool.and(col0, marker(s, '-')), u => doc.indicator(st, T.DocStart{}),
1488        u => when(Step, Bool.and(col0, marker(s, '.')), u => doc.indicator(st, T.DocEnd{}),
1489          u => fetch.char(c, peek(s, 1n), sc.in_flow(st), st)))))
1490
1491def fetch.after(+st: Sc) -> Step:
1492  fetch.next(unroll(st, 1n+sc.col(st)))
1493
1494# One token (and the block tokens before it).
1495def fetch(+st: Sc) -> Step:
1496  then(skip.ws(st), st => then(stale(st), st => fetch.after(st)))
1497
1498def scan.run(fuel: Nat, s: Step) -> List<&2, T.Token>:
1499  match fuel:
1500    case 0n:
1501      []
1502    case 1n+k:
1503      match s:
1504        case Go{st}:
1505          scan.run(k, fetch(st))
1506        case Stop{st}:
1507          List.reverse(&2, T.Token, sc.out(st))
1508
1509# Where the first character YAML doesn't allow is (a control character, a
1510# surrogate), if there is one.
1511def unprintable(s: String, +at: T.Mark) -> Maybe<&2, T.Mark>:
1512  match s:
1513    case SNil{}:
1514      None{}
1515    case SCon{+c, t}:
1516      when(Maybe<&2, T.Mark>, is_printable(c), u => unprintable(t, past(at, c)), u => Some{at})
1517
1518def stream.start() -> T.Token:
1519  T.Token{T.StreamStart{}, T.Mark{0n, 0n, 0n}, T.Mark{0n, 0n, 0n}}
1520
1521def scan.start(m: Maybe<&2, T.Mark>, +s: String, max: Nat) -> List<&2, T.Token>:
1522  match m:
1523    case Some{+at}:
1524      [stream.start(), T.Token{T.Broken{T.Error{"control characters are not allowed", at, T.Syntax{}}}, at, at}]
1525    case None{}:
1526      scan.run(Nat.add(String.length(s), 4n), Go{Sc{Cur{s, T.Mark{0n, 0n, 0n}, String.length(s)}, 0n, [], 0n, True{}, False{}, [SKey{False{}, False{}, 0n, T.Mark{0n, 0n, 0n}, False{}, None{}}], [stream.start()], 1n, max}})
1527
1528# The tokens of +text+, from StreamStart to StreamEnd, or to a Broken token
1529# at the first error. Flow collections may nest +max+ deep.
1530def scan(text: String, max: Nat) -> List<&2, T.Token>:
1531  +s = strip.bom(lf(text))
1532  scan.start(unprintable(s, T.Mark{0n, 0n, 0n}), s, max)