1	# layout/format: a file that differs from its formatted text, where it first differs. One formatter
2	# owns indentation, spacing, declaration gaps and wrapping.
3	# Fix: writes the formatted text.
4	# Options: tabWidth (2); wrapAtWidth (100, or "never": no optional wrapping); endOfLine ("lf",
5	# "crlf", or "preserve": the file's first, or LF if it has none).
6	# Heuristics: it reads tokens, not Bend's syntax, and changes only blanks, line breaks and the space
7	# after a comment's #, so a fix keeps the program. A form its token rules do not know can come out
8	# laid out oddly.
9	#
10	# A String is a JS string at run time: ++ is native, and a match on SCon reads one character and slices off the rest.
11	# So the lexer reads the text once, tokens carry what the layout asks of them, and docs carry widths.
12	#
13	# Each loop is go(input, state): a step that does not recurse makes the next state, so every loop recurses on a smaller
14	# part of its input. The lexer and the printer recurse on fuel instead: more steps than they can need.
15	import Base
16	import bend-lint-api@0.2.1.0/linter/lint.bend as Lint
17	import bend-lint-api@0.2.1.0/shared/strings.bend as Strings
18	
19	# Types
20	# =====
21	type Lex is Data:
22	  Code{}
23	  Literal{}
24	  Comment{}
25	  Newline{}
26	
27	# The spellings the layout tells apart; Word{} is any other, Inc{} ends in n+.
28	type Sym is Data:
29	  Word{}
30	  Comma{}
31	  Semi{}
32	  Colon{}
33	  Ques{}
34	  Bang{}
35	  Dot{}
36	  Tilde{}
37	  At{}
38	  Bslash{}
39	  Plus{}
40	  Minus{}
41	  Star{}
42	  Slash{}
43	  Pct{}
44	  Caret{}
45	  Amp{}
46	  Bar{}
47	  Lpar{}
48	  Rpar{}
49	  Lbrk{}
50	  Rbrk{}
51	  Lbrc{}
52	  Rbrc{}
53	  Lt{}
54	  Gt{}
55	  Assign{}
56	  Arrow{}
57	  Concat{}
58	  AndAnd{}
59	  OrOr{}
60	  Meet{}
61	  BitAnd{}
62	  BitOr{}
63	  BitXor{}
64	  Shl{}
65	  Shr{}
66	  Cons{}
67	  Le{}
68	  Ge{}
69	  EqEq{}
70	  Ne{}
71	  Inc{}
72	  KwReturn{}
73	  KwCase{}
74	  KwMatch{}
75	  KwFor{}
76	  KwExs{}
77	  KwIs{}
78	  KwDo{}
79	  KwDef{}
80	  KwType{}
81	  KwLaw{}
82	  KwImport{}
83	
84	# Offsets and columns count code points. name: whether the text matches
85	# /^[\w.]+$/. tail: for a literal across lines, how many characters follow
86	# its last newline. from: the text from the token on.
87	type Token is Data:
88	  Token{
89	    text: String,
90	    beg: U32,
91	    end: U32,
92	    col: U32,
93	    lex: Lex,
94	    sym: Sym,
95	    name: Bool,
96	    tail: Maybe<&2, U32>,
97	    from: String
98	  }
99	
100	# What the lexer read: the end of the text, one whitespace character, or a
101	# token; with the text after it and its last character.
102	type Scan is Data:
103	  Eof{}
104	  Blank{rest: String, last: Char, len: U32}
105	  Tok{
106	    text: String,
107	    len: U32,
108	    rest: String,
109	    last: Char,
110	    lex: Lex,
111	    sym: Sym,
112	    name: Bool,
113	    tail: Maybe<&2, U32>
114	  }
115	
116	# Characters read by run: their text and count, the text after them, and
117	# the last one.
118	type Run is Data:
119	  Run{text: String, len: U32, rest: String, last: Char}
120	
121	# What the next character of a literal is: inside it, escaped, or past it.
122	type Quote is Data:
123	  Inside{}
124	  Escaped{}
125	  Shut{}
126	
127	type Class is Data:
128	  IsBlank{}
129	  IsHead{}
130	  IsDigit{}
131	  IsOther{}
132	
133	type Tree is Data:
134	  Leaf{token: Token}
135	  Group{open: Token, close: Token, children: List<&2, Tree>, block: Bool}
136	
137	# A group the tree has opened: the sym that closes it, children last first,
138	# and whether a child is a token that makes it a block.
139	type Open is Data:
140	  Open{token: Token, close: Sym, children: List<&2, Tree>, block: Bool}
141	
142	type Built is Data:
143	  Built{stack: List<&2, Open>, root: List<&2, Tree>}
144	
145	# A doc printed flat: its width up to the first break it cannot lose (a
146	# hard line, or a newline in text), and whether it has one.
147	type Flat is Data:
148	  Flat{width: U32, brk: Bool}
149	
150	# Str: text without its trailing whitespace, that whitespace, the width, and
151	# how many characters follow the last newline, if any. Line: the text and
152	# width when flat. Grp, Nest and Cat keep their Flat; Cat its docs last
153	# first.
154	type Doc is Data:
155	  Str{body: String, blank: String, width: U32, tail: Maybe<&2, U32>}
156	  Line{flat: String, width: U32, hard: Bool, offset: U32}
157	  Grp{doc: Doc, flat: Flat}
158	  Nest{doc: Doc, amount: U32, flat: Flat}
159	  Cat{docs: List<&2, Doc>, flat: Flat}
160	
161	type Measure is Data:
162	  Measure{width: U32, tail: Maybe<&2, U32>, keep: U32}
163	
164	# How build reads a list of trees: a record, a group's children as a raw
165	# block, as comma-separated parts, or a group with no children. A block is
166	# an embedded statement body: its line and column boundaries mean
167	# something, so it keeps them, while ordinary calls inside it still wrap.
168	type Mode is Data:
169	  Plain{}
170	  Block{open: Token, close: Token}
171	  Parts{open: Token, close: Token}
172	  Bare{open: Token, close: Token}
173	
174	# A sequence being built: its docs last first, the docs of an operator
175	# chain, the previous tree, the indentation levels deepest first, and
176	# whether the rest of a run of newlines is skipped.
177	type Seq is Data:
178	  Seq{
179	    out: List<&2, Doc>,
180	    chain: Maybe<&2, List<&2, Doc>>,
181	    prev: Maybe<&2, Tree>,
182	    levels: List<&2, U32>,
183	    skip: Bool
184	  }
185	
186	# A comma-separated part: whether it holds only newlines, and whether its
187	# last other tree ends in a comment.
188	type Part is Data:
189	  Part{doc: Doc, newlines: Bool, comment: Bool}
190	
191	# A group's parts so far, last first; the current part's flags; whether the
192	# next tree ends the current part; whether a child starts with a comment.
193	type Split is Data:
194	  Split{parts: List<&2, Part>, newlines: Bool, comment: Bool, attach: Bool, comments: Bool}
195	
196	type State is Data:
197	  State{seq: Seq, split: Split}
198	
199	# What a child of a group does to its parts.
200	type Act is Data:
201	  Add{}
202	  AddAttach{}
203	  AddEnd{}
204	  End{}
205	
206	type Job is Data:
207	  Job{doc: Doc, indent: U32, flat: Bool}
208	
209	# The printer: jobs left, the text so far as chunks last first, the
210	# whitespace not written yet (dropped at a break or at the end), and the
211	# column.
212	type Print is Data:
213	  Print{jobs: List<&2, Job>, out: List<&2, String>, pending: String, col: U32}
214	
215	type Fit is Data:
216	  Go{jobs: List<&2, Job>, left: U32}
217	  Stop{fits: Bool}
218	
219	# Records so far, last first, and the current record, last first.
220	type Recs is Data:
221	  Recs{done: List<&2, List<&2, Tree>>, current: List<&2, Tree>}
222	
223	# A declaration record cut after its first colon, if it has one.
224	type Cut is Data:
225	  Cut{before: List<&2, Tree>, after: List<&2, Tree>, found: Bool}
226	
227	type Hash is Data:
228	  Hash{before: String, comment: Maybe<&2, String>}
229	
230	# The rows so far, last first, and what the next record needs from them.
231	type Rows is Data:
232	  Rows{levels: List<&2, U32>, blank: Bool, unsafe: Bool, comment: Bool, rows: List<&2, String>}
233	
234	# width: None{} for "never".
235	type Settings is Data:
236	  Settings{tab: U32, width: Maybe<&2, U32>, newline: String}
237	
238	# Constants
239	# =========
240	
241	# Fuel per code point of a record: more printer steps than any doc needs.
242	def fuel_per_point() -> U32:
243	  64
244	
245	# Functions
246	# =========
247	
248	# Text
249	# ----
250	
251	# Whitespace, as Bend's parser reads it.
252	def is_blank(+c: Char) -> Bool:
253	  match c:
254	    case ' ':
255	      True{}
256	    case '\t':
257	      True{}
258	    case '\n':
259	      True{}
260	    case '\r':
261	      True{}
262	    case _:
263	      False{}
264	
265	def is_head(+c: Char) -> Bool:
266	  Char.is_alpha(c) || Char.is_eq(c, '_')
267	
268	def is_word(+c: Char) -> Bool:
269	  is_head(c) || Char.is_digit(c)
270	
271	def head_passes(~test: @+c: Char -> Bool, s: String) -> Bool:
272	  match s:
273	    case SNil{}:
274	      False{}
275	    case SCon{c, rest}:
276	      test(c)
277	
278	def char(c: Char) -> String:
279	  SCon{c, SNil{}}
280	
281	def drop_blank.go(s: String, blank: Bool) -> String:
282	  match s blank:
283	    case SNil{} _:
284	      SNil{}
285	    case SCon{c, rest} False{}:
286	      SCon{c, rest}
287	    case SCon{c, +rest} True{}:
288	      drop_blank.go(rest, head_passes(~is_blank, rest))
289	
290	def drop_blank(+s: String) -> String:
291	  drop_blank.go(s, head_passes(~is_blank, s))
292	
293	def trim_end(s: String) -> String:
294	  String.reverse(drop_blank(String.reverse(s)))
295	
296	def pad(n: Nat, out: String) -> String:
297	  match n:
298	    case 0n:
299	      out
300	    case 1n+k:
301	      pad(k, SCon{' ', out})
302	
303	# Base's String.eq is not tail-recursive, so long text would overflow the stack; is_same is.
304	# ok: whether the characters so far were the same.
305	def is_same.go(a: String, b: String, ok: Bool) -> Bool:
306	  match a b ok:
307	    case SCon{x, xs} SCon{y, ys} True{}:
308	      is_same.go(xs, ys, Char.is_eq(x, y))
309	    case SNil{} SNil{} done:
310	      done
311	    case _ _ _:
312	      False{}
313	
314	def is_same(a: String, b: String) -> Bool:
315	  is_same.go(a, b, True{})
316	
317	# Lexer
318	# -----
319	#
320	# A branch that uses a string or a character its match took apart gets it
321	# rebuilt: a string as character + rest, a rope that the next read copies
322	# whole, and a character bit by bit. So a def that needs the whole value in
323	# a branch takes it twice, as keep, and matches the other copy.
324	def is_not_line_end(s: String) -> Bool:
325	  match s:
326	    case SNil{}:
327	      False{}
328	    case SCon{'\n', rest}:
329	      False{}
330	    case SCon{'\r', rest}:
331	      False{}
332	    case _:
333	      True{}
334	
335	def is_digit_at(s: String) -> Bool:
336	  match s:
337	    case SNil{}:
338	      False{}
339	    case SCon{c, rest}:
340	      Char.is_digit(c)
341	
342	def is_ident_at.of(dot: Bool, c: Char, rest: String) -> Bool:
343	  match dot:
344	    case True{}:
345	      head_passes(~is_head, rest)
346	    case False{}:
347	      is_word(c)
348	
349	# A word character, or a dot before the start of a word.
350	def is_ident_at(s: String) -> Bool:
351	  match s:
352	    case SNil{}:
353	      False{}
354	    case SCon{+c, rest}:
355	      is_ident_at.of(Char.is_eq(c, '.'), c, rest)
356	
357	# `scan`, with the text so far last character first: on the C lane, ++ copies its left side.
358	def scan.go(
359	  ~test: String -> Bool,
360	  s: String,
361	  keep: String,
362	  ok: Bool,
363	  text: String,
364	  n: U32,
365	  last: Char
366	) -> Run:
367	  match s ok:
368	    case SCon{+c, +rest} True{}:
369	      scan.go(~test, rest, rest, test(rest), SCon{c, text}, (n + 1: U32), c)
370	    case _ _:
371	      Run{String.reverse(text), n, keep, last}
372	
373	# Reads characters while test holds, after text; test sees the text from
374	# each character on, so it can look ahead.
375	def scan(
376	  ~test: String -> Bool,
377	  s: String,
378	  keep: String,
379	  ok: Bool,
380	  text: String,
381	  n: U32,
382	  last: Char
383	) -> Run:
384	  scan.go(~test, s, keep, ok, String.reverse(text), n, last)
385	
386	def tok(r: Run, sym: Sym, name: Bool) -> Scan:
387	  match r:
388	    case Run{text, len, rest, last}:
389	      Tok{text, len, rest, last, Code{}, sym, name, None{}}
390	
391	def fixed(text: String, len: U32, rest: String, last: Char, sym: Sym) -> Scan:
392	  Tok{text, len, rest, last, Code{}, sym, False{}, None{}}
393	
394	def keyword.is(text: String, word: String, sym: Sym) -> Sym:
395	  Bool.pick(Sym, is_same(text, word), sym, Word{})
396	
397	def keyword(text: String, +keep: String) -> Sym:
398	  match text:
399	    case SCon{'r', rest}:
400	      keyword.is(keep, "return", KwReturn{})
401	    case SCon{'c', rest}:
402	      keyword.is(keep, "case", KwCase{})
403	    case SCon{'m', rest}:
404	      keyword.is(keep, "match", KwMatch{})
405	    case SCon{'f', rest}:
406	      keyword.is(keep, "for", KwFor{})
407	    case SCon{'e', rest}:
408	      keyword.is(keep, "exs", KwExs{})
409	    case SCon{'i', rest}:
410	      Bool.pick(Sym, is_same(keep, "is"), KwIs{}, keyword.is(keep, "import", KwImport{}))
411	    case SCon{'d', rest}:
412	      Bool.pick(Sym, is_same(keep, "do"), KwDo{}, keyword.is(keep, "def", KwDef{}))
413	    case SCon{'t', rest}:
414	      keyword.is(keep, "type", KwType{})
415	    case SCon{'l', rest}:
416	      keyword.is(keep, "law", KwLaw{})
417	    case _:
418	      Word{}
419	
420	def ident(r: Run) -> Scan:
421	  match r:
422	    case Run{+text, len, rest, last}:
423	      Tok{text, len, rest, last, Code{}, keyword(text, text), True{}, None{}}
424	
425	def number.tok(r: Run, inc: Bool, name: Bool) -> Scan:
426	  tok(r, Bool.pick(Sym, inc, Inc{}, Word{}), name)
427	
428	def exponent.digits(
429	  go: Bool,
430	  +rest: String,
431	  mark: String,
432	  k: U32,
433	  keep: String,
434	  text: String,
435	  n: U32,
436	  last: Char,
437	  signed: Bool
438	) -> Scan:
439	  match go:
440	    case True{}:
441	      number.tok(
442	        scan(~is_digit_at, rest, rest, True{}, text ++ mark, (n + k: U32), last),
443	        False{},
444	        Bool.not(signed)
445	      )
446	    case False{}:
447	      number.tok(Run{text, n, keep, last}, False{}, True{})
448	
449	def exponent.sign(
450	  rest: String,
451	  +again: String,
452	  mark: String,
453	  keep: String,
454	  text: String,
455	  n: U32,
456	  last: Char
457	) -> Scan:
458	  match rest:
459	    case SCon{'+', +r}:
460	      exponent.digits(is_digit_at(r), r, mark ++ "+", 2, keep, text, n, last, True{})
461	    case SCon{'-', +r}:
462	      exponent.digits(is_digit_at(r), r, mark ++ "-", 2, keep, text, n, last, True{})
463	    case _:
464	      exponent.digits(is_digit_at(again), again, mark, 1, keep, text, n, last, False{})
465	
466	def exponent.of(s: String, keep: String, text: String, n: U32, last: Char) -> Scan:
467	  match s:
468	    case SCon{'e', +rest}:
469	      exponent.sign(rest, rest, "e", keep, text, n, last)
470	    case SCon{'E', +rest}:
471	      exponent.sign(rest, rest, "E", keep, text, n, last)
472	    case _:
473	      number.tok(Run{text, n, keep, last}, False{}, True{})
474	
475	# After a fraction: [eE][+-]?\d+, if it is there.
476	def exponent(r: Run) -> Scan:
477	  match r:
478	    case Run{text, n, +s, last}:
479	      exponent.of(s, s, text, n, last)
480	
481	def fraction(go: Bool, +rest: String, keep: String, text: String, n: U32, last: Char) -> Scan:
482	  match go:
483	    case True{}:
484	      exponent(scan(~is_digit_at, rest, rest, True{}, text ++ ".", (n + 1: U32), '.'))
485	    case False{}:
486	      number.tok(Run{text, n, keep, last}, False{}, True{})
487	
488	# After "n": n+, or n alone.
489	def number.inc(s: String, keep: String, text: String, n: U32) -> Scan:
490	  match s:
491	    case SCon{'+', rest}:
492	      number.tok(Run{text ++ "n+", (n + 2: U32), rest, '+'}, True{}, False{})
493	    case _:
494	      number.tok(Run{text ++ "n", (n + 1: U32), keep, 'n'}, False{}, True{})
495	
496	def number.of(s: String, keep: String, text: String, n: U32, last: Char) -> Scan:
497	  match s:
498	    case SCon{'n', +rest}:
499	      number.inc(rest, rest, text, n)
500	    case SCon{'.', +rest}:
501	      fraction(is_digit_at(rest), rest, keep, text, n, last)
502	    case _:
503	      number.tok(Run{text, n, keep, last}, False{}, True{})
504	
505	# After a number's digits: n, n+, or a fraction and its exponent.
506	def number(r: Run) -> Scan:
507	  match r:
508	    case Run{text, n, +s, last}:
509	      number.of(s, s, text, n, last)
510	
511	def tail_after(c: Char, tail: Maybe<&2, U32>) -> Maybe<&2, U32>:
512	  match c tail:
513	    case '\n' _:
514	      Some{0}
515	    case _ Some{t}:
516	      Some{(t + 1: U32)}
517	    case _ None{}:
518	      None{}
519	
520	def quote_after(+c: Char, quote: Char) -> Quote:
521	  Bool.pick(
522	    Quote,
523	    Char.is_eq(c, '\\'),
524	    Escaped{},
525	    Bool.pick(Quote, Char.is_eq(c, quote), Shut{}, Inside{})
526	  )
527	
528	# `literal`, with the text so far last character first: on the C lane, ++ copies its left side.
529	def literal.go(
530	  s: String,
531	  keep: String,
532	  +quote: Char,
533	  at: Quote,
534	  text: String,
535	  n: U32,
536	  last: Char,
537	  tail: Maybe<&2, U32>
538	) -> Scan:
539	  match s at:
540	    case SCon{+c, +rest} Inside{}:
541	      literal.go(
542	        rest,
543	        rest,
544	        quote,
545	        quote_after(c, quote),
546	        SCon{c, text},
547	        (n + 1: U32),
548	        c,
549	        tail_after(c, tail)
550	      )
551	    case SCon{+c, +rest} Escaped{}:
552	      literal.go(rest, rest, quote, Inside{}, SCon{c, text}, (n + 1: U32), c, tail_after(c, tail))
553	    case _ _:
554	      Tok{String.reverse(text), n, keep, last, Literal{}, Word{}, False{}, tail}
555	
556	def literal(
557	  s: String,
558	  keep: String,
559	  quote: Char,
560	  at: Quote,
561	  text: String,
562	  n: U32,
563	  last: Char,
564	  tail: Maybe<&2, U32>
565	) -> Scan:
566	  literal.go(s, keep, quote, at, String.reverse(text), n, last, tail)
567	
568	def class_of(+c: Char) -> Class:
569	  Bool.pick(
570	    Class,
571	    is_blank(c),
572	    IsBlank{},
573	    Bool.pick(Class, is_head(c), IsHead{}, Bool.pick(Class, Char.is_digit(c), IsDigit{}, IsOther{}))
574	  )
575	
576	def single(c: Char) -> Sym:
577	  match c:
578	    case ',':
579	      Comma{}
580	    case ';':
581	      Semi{}
582	    case ':':
583	      Colon{}
584	    case '?':
585	      Ques{}
586	    case '~':
587	      Tilde{}
588	    case '@':
589	      At{}
590	    case '\\':
591	      Bslash{}
592	    case '*':
593	      Star{}
594	    case '/':
595	      Slash{}
596	    case '%':
597	      Pct{}
598	    case '^':
599	      Caret{}
600	    case '(':
601	      Lpar{}
602	    case ')':
603	      Rpar{}
604	    case '[':
605	      Lbrk{}
606	    case ']':
607	      Rbrk{}
608	    case '{':
609	      Lbrc{}
610	    case '}':
611	      Rbrc{}
612	    case _:
613	      Word{}
614	
615	def lex.other(class: Class, +c: Char, +rest: String) -> Scan:
616	  match class:
617	    case IsBlank{}:
618	      Blank{rest, c, 1}
619	    case IsHead{}:
620	      ident(scan(~is_ident_at, rest, rest, is_ident_at(rest), char(c), 1, c))
621	    case IsDigit{}:
622	      number(scan(~is_digit_at, rest, rest, is_digit_at(rest), char(c), 1, c))
623	    case IsOther{}:
624	      fixed(char(c), 1, rest, c, single(c))
625	
626	def lex.char(s: String) -> Scan:
627	  match s:
628	    case SNil{}:
629	      Eof{}
630	    case SCon{+c, rest}:
631	      lex.other(class_of(c), c, rest)
632	
633	def lex.dash(word: Bool, keep: String, r: String) -> Scan:
634	  match word:
635	    case True{}:
636	      fixed("<", 1, keep, '<', Lt{})
637	    case False{}:
638	      fixed("<-", 2, r, '-', Word{})
639	
640	def lex.lt(rest: String, keep: String, +prev: Char) -> Scan:
641	  match rest:
642	    case SCon{'&', SCon{'>', r}}:
643	      fixed("<&>", 3, r, '>', Meet{})
644	    case SCon{'-', r}:
645	      lex.dash(is_word(prev) || Char.is_eq(prev, '.'), keep, r)
646	    case SCon{'=', r}:
647	      fixed("<=", 2, r, '=', Le{})
648	    case SCon{'<', r}:
649	      fixed("<<", 2, r, '<', Shl{})
650	    case SCon{'>', r}:
651	      fixed("<>", 2, r, '>', Cons{})
652	    case _:
653	      fixed("<", 1, keep, '<', Lt{})
654	
655	def lex.shr(blank: Bool, keep: String, r: String) -> Scan:
656	  match blank:
657	    case True{}:
658	      fixed(">>", 2, r, '>', Shr{})
659	    case False{}:
660	      fixed(">", 1, keep, '>', Gt{})
661	
662	def lex.gt(rest: String, keep: String, prev: Char) -> Scan:
663	  match rest:
664	    case SCon{'>', r}:
665	      lex.shr(is_blank(prev), keep, r)
666	    case SCon{'=', r}:
667	      fixed(">=", 2, r, '=', Ge{})
668	    case _:
669	      fixed(">", 1, keep, '>', Gt{})
670	
671	def lex.dot(rest: String, keep: String) -> Scan:
672	  match rest:
673	    case SCon{'&', SCon{'.', r}}:
674	      fixed(".&.", 3, r, '.', BitAnd{})
675	    case SCon{'|', SCon{'.', r}}:
676	      fixed(".|.", 3, r, '.', BitOr{})
677	    case SCon{'^', SCon{'.', r}}:
678	      fixed(".^.", 3, r, '.', BitXor{})
679	    case _:
680	      Tok{".", 1, keep, '.', Code{}, Dot{}, True{}, None{}}
681	
682	def lex.minus(rest: String, keep: String) -> Scan:
683	  match rest:
684	    case SCon{'>', r}:
685	      fixed("->", 2, r, '>', Arrow{})
686	    case _:
687	      fixed("-", 1, keep, '-', Minus{})
688	
689	def lex.eq(rest: String, keep: String) -> Scan:
690	  match rest:
691	    case SCon{'=', r}:
692	      fixed("==", 2, r, '=', EqEq{})
693	    case SCon{'>', r}:
694	      fixed("=>", 2, r, '>', Word{})
695	    case _:
696	      fixed("=", 1, keep, '=', Assign{})
697	
698	def lex.bang(rest: String, keep: String) -> Scan:
699	  match rest:
700	    case SCon{'=', r}:
701	      fixed("!=", 2, r, '=', Ne{})
702	    case _:
703	      fixed("!", 1, keep, '!', Bang{})
704	
705	def lex.amp(rest: String, keep: String) -> Scan:
706	  match rest:
707	    case SCon{'&', r}:
708	      fixed("&&", 2, r, '&', AndAnd{})
709	    case SCon{'0', r}:
710	      fixed("&0", 2, r, '0', Word{})
711	    case SCon{'1', r}:
712	      fixed("&1", 2, r, '1', Word{})
713	    case SCon{'2', r}:
714	      fixed("&2", 2, r, '2', Word{})
715	    case _:
716	      fixed("&", 1, keep, '&', Amp{})
717	
718	def lex.bar(rest: String, keep: String) -> Scan:
719	  match rest:
720	    case SCon{'|', r}:
721	      fixed("||", 2, r, '|', OrOr{})
722	    case _:
723	      fixed("|", 1, keep, '|', Bar{})
724	
725	def lex.plus(rest: String, keep: String) -> Scan:
726	  match rest:
727	    case SCon{'+', r}:
728	      fixed("++", 2, r, '+', Concat{})
729	    case _:
730	      fixed("+", 1, keep, '+', Plus{})
731	
732	def comment(r: Run) -> Scan:
733	  match r:
734	    case Run{text, len, rest, last}:
735	      Tok{text, len, rest, last, Comment{}, Word{}, False{}, None{}}
736	
737	# A run of whitespace on one line.
738	def blanks(s: String, keep: String, n: U32, last: Char) -> Scan:
739	  match s:
740	    case SCon{' ', +rest}:
741	      blanks(rest, rest, (n + 1: U32), ' ')
742	    case SCon{'\t', +rest}:
743	      blanks(rest, rest, (n + 1: U32), '\t')
744	    case SCon{'\r', +rest}:
745	      blanks(rest, rest, (n + 1: U32), '\r')
746	    case _:
747	      Blank{keep, last, n}
748	
749	# The token at the start of s; prev is the character before it. Literals
750	# and comment text are kept verbatim: a quote or # inside a string is not
751	# syntax. Successor notation (1n+) and quantities (&2) are single tokens.
752	def lex.token(s: String, keep: String, prev: Char) -> Scan:
753	  match s:
754	    case SNil{}:
755	      Eof{}
756	    case SCon{' ', +rest}:
757	      blanks(rest, rest, 1, ' ')
758	    case SCon{'\n', rest}:
759	      Tok{"\n", 1, rest, '\n', Newline{}, Word{}, False{}, None{}}
760	    case SCon{'#', +rest}:
761	      comment(scan(~is_not_line_end, rest, rest, is_not_line_end(rest), "#", 1, '#'))
762	    case SCon{'"', +rest}:
763	      literal(rest, rest, '"', Inside{}, "\"", 1, '"', None{})
764	    case SCon{'\'', +rest}:
765	      literal(rest, rest, '\'', Inside{}, "'", 1, '\'', None{})
766	    case SCon{'<', +rest}:
767	      lex.lt(rest, rest, prev)
768	    case SCon{'>', +rest}:
769	      lex.gt(rest, rest, prev)
770	    case SCon{'.', +rest}:
771	      lex.dot(rest, rest)
772	    case SCon{'-', +rest}:
773	      lex.minus(rest, rest)
774	    case SCon{'=', +rest}:
775	      lex.eq(rest, rest)
776	    case SCon{'!', +rest}:
777	      lex.bang(rest, rest)
778	    case SCon{'&', +rest}:
779	      lex.amp(rest, rest)
780	    case SCon{'|', +rest}:
781	      lex.bar(rest, rest)
782	    case SCon{'+', +rest}:
783	      lex.plus(rest, rest)
784	    case _:
785	      lex.char(keep)
786	
787	def next_col(lex: Lex, tail: Maybe<&2, U32>, col: U32, len: U32) -> U32:
788	  match lex tail:
789	    case Newline{} _:
790	      0
791	    case _ Some{t}:
792	      t
793	    case _ None{}:
794	      (col + len: U32)
795	
796	# Each step reads at least one character, so the text's length is fuel.
797	def lex.go(
798	  fuel: Nat,
799	  sc: Scan,
800	  from: String,
801	  +at: U32,
802	  +col: U32,
803	  acc: List<&2, Token>
804	) -> List<&2, Token>:
805	  match fuel sc:
806	    case 1n+k Tok{text, +len, +rest, last, +lex, sym, name, +tail}:
807	      lex.go(
808	        k,
809	        lex.token(rest, rest, last),
810	        rest,
811	        (at + len: U32),
812	        next_col(lex, tail, col, len),
813	        Con{Token{text, at, (at + len: U32), col, lex, sym, name, tail, from}, acc}
814	      )
815	    case 1n+k Blank{+rest, last, +len}:
816	      lex.go(k, lex.token(rest, rest, last), rest, (at + len: U32), (col + len: U32), acc)
817	    case _ _:
818	      List.reverse(&2, Token, acc)
819	
820	def tokens(+s: String) -> List<&2, Token>:
821	  lex.go(1n+String.length(s), lex.token(s, s, '\0'), s, 0, 0, [])
822	
823	# Tokens
824	# ------
825	def Token.text(t: Token) -> String:
826	  match t:
827	    case Token{text, beg, end, col, lex, sym, name, tail, from}:
828	      text
829	
830	def Token.beg(t: Token) -> U32:
831	  match t:
832	    case Token{text, beg, end, col, lex, sym, name, tail, from}:
833	      beg
834	
835	def Token.end(t: Token) -> U32:
836	  match t:
837	    case Token{text, beg, end, col, lex, sym, name, tail, from}:
838	      end
839	
840	def Token.col(t: Token) -> U32:
841	  match t:
842	    case Token{text, beg, end, col, lex, sym, name, tail, from}:
843	      col
844	
845	def Token.sym(t: Token) -> Sym:
846	  match t:
847	    case Token{text, beg, end, col, lex, sym, name, tail, from}:
848	      sym
849	
850	def Token.is_name(t: Token) -> Bool:
851	  match t:
852	    case Token{text, beg, end, col, lex, sym, name, tail, from}:
853	      name
854	
855	def Token.from(t: Token) -> String:
856	  match t:
857	    case Token{text, beg, end, col, lex, sym, name, tail, from}:
858	      from
859	
860	def is_comment(t: Token) -> Bool:
861	  match t:
862	    case Token{text, beg, end, col, Comment{}, sym, name, tail, from}:
863	      True{}
864	    case _:
865	      False{}
866	
867	def is_operator(s: Sym) -> Bool:
868	  match s:
869	    case Plus{}:
870	      True{}
871	    case Minus{}:
872	      True{}
873	    case Star{}:
874	      True{}
875	    case Slash{}:
876	      True{}
877	    case Pct{}:
878	      True{}
879	    case Caret{}:
880	      True{}
881	    case Concat{}:
882	      True{}
883	    case AndAnd{}:
884	      True{}
885	    case OrOr{}:
886	      True{}
887	    case Meet{}:
888	      True{}
889	    case BitAnd{}:
890	      True{}
891	    case BitOr{}:
892	      True{}
893	    case BitXor{}:
894	      True{}
895	    case Shl{}:
896	      True{}
897	    case Shr{}:
898	      True{}
899	    case Cons{}:
900	      True{}
901	    case Lt{}:
902	      True{}
903	    case Gt{}:
904	      True{}
905	    case Le{}:
906	      True{}
907	    case Ge{}:
908	      True{}
909	    case EqEq{}:
910	      True{}
911	    case Ne{}:
912	      True{}
913	    case Amp{}:
914	      True{}
915	    case Bar{}:
916	      True{}
917	    case _:
918	      False{}
919	
920	# A sign or quantity glued to what follows it.
921	def is_prefix(s: Sym) -> Bool:
922	  match s:
923	    case Plus{}:
924	      True{}
925	    case Minus{}:
926	      True{}
927	    case Pct{}:
928	      True{}
929	    case Amp{}:
930	      True{}
931	    case _:
932	      False{}
933	
934	def is_tight(s: Sym) -> Bool:
935	  match s:
936	    case Comma{}:
937	      True{}
938	    case Semi{}:
939	      True{}
940	    case Colon{}:
941	      True{}
942	    case Ques{}:
943	      True{}
944	    case Bang{}:
945	      True{}
946	    case Dot{}:
947	      True{}
948	    case _:
949	      False{}
950	
951	def is_punct(s: Sym) -> Bool:
952	  match s:
953	    case Comma{}:
954	      True{}
955	    case Semi{}:
956	      True{}
957	    case Colon{}:
958	      True{}
959	    case _:
960	      False{}
961	
962	def is_sigil(s: Sym) -> Bool:
963	  match s:
964	    case Tilde{}:
965	      True{}
966	    case At{}:
967	      True{}
968	    case Ques{}:
969	      True{}
970	    case Bang{}:
971	      True{}
972	    case Bslash{}:
973	      True{}
974	    case _:
975	      False{}
976	
977	def is_opener(s: Sym) -> Bool:
978	  match s:
979	    case Lpar{}:
980	      True{}
981	    case Lbrk{}:
982	      True{}
983	    case Lbrc{}:
984	      True{}
985	    case Lt{}:
986	      True{}
987	    case _:
988	      False{}
989	
990	def is_closer(s: Sym) -> Bool:
991	  match s:
992	    case Rpar{}:
993	      True{}
994	    case Rbrk{}:
995	      True{}
996	    case Rbrc{}:
997	      True{}
998	    case _:
999	      False{}
1000	
1001	def is_keyword(s: Sym) -> Bool:
1002	  match s:
1003	    case KwReturn{}:
1004	      True{}
1005	    case KwCase{}:
1006	      True{}
1007	    case KwMatch{}:
1008	      True{}
1009	    case KwFor{}:
1010	      True{}
1011	    case KwExs{}:
1012	      True{}
1013	    case KwIs{}:
1014	      True{}
1015	    case _:
1016	      False{}
1017	
1018	def is_block_word(s: Sym) -> Bool:
1019	  match s:
1020	    case KwMatch{}:
1021	      True{}
1022	    case KwCase{}:
1023	      True{}
1024	    case KwDo{}:
1025	      True{}
1026	    case Assign{}:
1027	      True{}
1028	    case Semi{}:
1029	      True{}
1030	    case Pct{}:
1031	      True{}
1032	    case Bslash{}:
1033	      True{}
1034	    case _:
1035	      False{}
1036	
1037	# A record that ends in one of these goes on at the next line.
1038	def is_continued(s: Sym) -> Bool:
1039	  match s:
1040	    case Arrow{}:
1041	      True{}
1042	    case Assign{}:
1043	      True{}
1044	    case Concat{}:
1045	      True{}
1046	    case AndAnd{}:
1047	      True{}
1048	    case OrOr{}:
1049	      True{}
1050	    case _:
1051	      False{}
1052	
1053	def is_declaration(s: Sym) -> Bool:
1054	  match s:
1055	    case KwDef{}:
1056	      True{}
1057	    case KwType{}:
1058	      True{}
1059	    case KwLaw{}:
1060	      True{}
1061	    case At{}:
1062	      True{}
1063	    case _:
1064	      False{}
1065	
1066	def is_import(s: Sym) -> Bool:
1067	  match s:
1068	    case KwImport{}:
1069	      True{}
1070	    case _:
1071	      False{}
1072	
1073	def is_sym(s: Sym, t: Sym) -> Bool:
1074	  match s t:
1075	    case Comma{} Comma{}:
1076	      True{}
1077	    case Colon{} Colon{}:
1078	      True{}
1079	    case Lbrc{} Lbrc{}:
1080	      True{}
1081	    case Gt{} Gt{}:
1082	      True{}
1083	    case Rpar{} Rpar{}:
1084	      True{}
1085	    case Rbrk{} Rbrk{}:
1086	      True{}
1087	    case Rbrc{} Rbrc{}:
1088	      True{}
1089	    case Bang{} Bang{}:
1090	      True{}
1091	    case At{} At{}:
1092	      True{}
1093	    case _ _:
1094	      False{}
1095	
1096	# Trees
1097	# -----
1098	def first(n: Tree) -> Token:
1099	  match n:
1100	    case Leaf{t}:
1101	      t
1102	    case Group{open, close, children, block}:
1103	      open
1104	
1105	def last(n: Tree) -> Token:
1106	  match n:
1107	    case Leaf{t}:
1108	      t
1109	    case Group{open, close, children, block}:
1110	      close
1111	
1112	def is_newline(n: Tree) -> Bool:
1113	  match n:
1114	    case Leaf{Token{text, beg, end, col, Newline{}, sym, name, tail, from}}:
1115	      True{}
1116	    case _:
1117	      False{}
1118	
1119	def is_leaf(n: Tree) -> Bool:
1120	  match n:
1121	    case Leaf{t}:
1122	      True{}
1123	    case _:
1124	      False{}
1125	
1126	def is_leaf_of(n: Tree, s: Sym) -> Bool:
1127	  match n:
1128	    case Leaf{t}:
1129	      is_sym(Token.sym(t), s)
1130	    case _:
1131	      False{}
1132	
1133	def head(xs: List<&2, Tree>) -> Maybe<&2, Tree>:
1134	  match xs:
1135	    case Nil{}:
1136	      None{}
1137	    case Con{x, rest}:
1138	      Some{x}
1139	
1140	def last_of(xs: List<&2, Tree>, at: Maybe<&2, Tree>) -> Maybe<&2, Tree>:
1141	  match xs:
1142	    case Nil{}:
1143	      at
1144	    case Con{x, rest}:
1145	      last_of(rest, Some{x})
1146	
1147	# The first tree after a run of newlines.
1148	def upcoming(xs: List<&2, Tree>) -> Maybe<&2, Tree>:
1149	  match xs:
1150	    case Nil{}:
1151	      None{}
1152	    case Con{Leaf{Token{text, beg, end, col, Newline{}, sym, name, tail, from}}, rest}:
1153	      upcoming(rest)
1154	    case Con{x, rest}:
1155	      Some{x}
1156	
1157	# What closes the group s opens, or Word{}.
1158	def closer(s: Sym) -> Sym:
1159	  match s:
1160	    case Lpar{}:
1161	      Rpar{}
1162	    case Lbrk{}:
1163	      Rbrk{}
1164	    case Lbrc{}:
1165	      Rbrc{}
1166	    case Lt{}:
1167	      Gt{}
1168	    case _:
1169	      Word{}
1170	
1171	def is_angled(prev: Maybe<&2, Token>, t: Token) -> Bool:
1172	  match prev:
1173	    case Some{+p}:
1174	      U32.is_eq(Token.end(p), Token.beg(t)) && Token.is_name(p)
1175	    case None{}:
1176	      False{}
1177	
1178	# Whether t opens a group: a glued < opens type arguments.
1179	def opens.of(s: Sym, t: Token, prev: Maybe<&2, Token>) -> Bool:
1180	  match s:
1181	    case Lpar{}:
1182	      True{}
1183	    case Lbrk{}:
1184	      True{}
1185	    case Lbrc{}:
1186	      True{}
1187	    case Lt{}:
1188	      is_angled(prev, t)
1189	    case _:
1190	      False{}
1191	
1192	def opens(+t: Token, prev: Maybe<&2, Token>) -> Bool:
1193	  opens.of(Token.sym(t), t, prev)
1194	
1195	def is_block_leaf(n: Tree) -> Bool:
1196	  match n:
1197	    case Leaf{t}:
1198	      is_block_word(Token.sym(t))
1199	    case _:
1200	      False{}
1201	
1202	def add(+n: Tree, stack: List<&2, Open>, root: List<&2, Tree>) -> Built:
1203	  match stack:
1204	    case Nil{}:
1205	      Built{Nil{}, Con{n, root}}
1206	    case Con{Open{t, close, children, block}, rest}:
1207	      Built{Con{Open{t, close, Con{n, children}, block || is_block_leaf(n)}, rest}, root}
1208	
1209	def waits(stack: List<&2, Open>, s: Sym) -> Bool:
1210	  match stack:
1211	    case Nil{}:
1212	      False{}
1213	    case Con{Open{t, close, children, block}, rest}:
1214	      is_sym(close, s)
1215	
1216	def pop(t: Token, stack: List<&2, Open>, root: List<&2, Tree>) -> Built:
1217	  match stack:
1218	    case Nil{}:
1219	      Built{Nil{}, root}
1220	    case Con{Open{open, close, children, block}, rest}:
1221	      add(Group{open, t, List.reverse(&2, Tree, children), block}, rest, root)
1222	
1223	def tree.close(closes: Bool, t: Token, stack: List<&2, Open>, root: List<&2, Tree>) -> Built:
1224	  match closes:
1225	    case True{}:
1226	      pop(t, stack, root)
1227	    case False{}:
1228	      add(Leaf{t}, stack, root)
1229	
1230	def tree.step(opens: Bool, +t: Token, +stack: List<&2, Open>, root: List<&2, Tree>) -> Built:
1231	  match opens:
1232	    case True{}:
1233	      Built{Con{Open{t, closer(Token.sym(t)), [], False{}}, stack}, root}
1234	    case False{}:
1235	      tree.close(waits(stack, Token.sym(t)), t, stack, root)
1236	
1237	def tree.go(ts: List<&2, Token>, prev: Maybe<&2, Token>, b: Built) -> Maybe<&2, List<&2, Tree>>:
1238	  match ts b:
1239	    case Nil{} Built{Nil{}, root}:
1240	      Some{List.reverse(&2, Tree, root)}
1241	    case Nil{} Built{Con{o, os}, root}:
1242	      None{}
1243	    case Con{+t, rest} Built{stack, root}:
1244	      tree.go(rest, Some{t}, tree.step(opens(t, prev), t, stack, root))
1245	
1246	# Docs
1247	# ----
1248	def measure(s: String, +n: U32, tail: Maybe<&2, U32>, keep: U32) -> Measure:
1249	  match s:
1250	    case SNil{}:
1251	      Measure{n, tail, keep}
1252	    case SCon{+c, rest}:
1253	      measure(
1254	        rest,
1255	        (n + 1: U32),
1256	        tail_after(c, tail),
1257	        Bool.pick(U32, is_blank(c), keep, (n + 1: U32))
1258	      )
1259	
1260	def str.split(whole: Bool, +s: String, width: U32, tail: Maybe<&2, U32>, +keep: U32) -> Doc:
1261	  match whole:
1262	    case True{}:
1263	      Str{s, "", width, tail}
1264	    case False{}:
1265	      Str{Strings.take(s, U32.to_nat(keep)), String.drop(s, U32.to_nat(keep)), width, tail}
1266	
1267	def str.of(s: String, m: Measure) -> Doc:
1268	  match m:
1269	    case Measure{+width, tail, +keep}:
1270	      str.split(U32.is_eq(width, keep), s, width, tail, keep)
1271	
1272	def str(+s: String) -> Doc:
1273	  str.of(s, measure(s, 0, None{}, 0))
1274	
1275	# A doc for text of this width, with no newline and no trailing whitespace.
1276	def text(s: String, width: U32) -> Doc:
1277	  Str{s, "", width, None{}}
1278	
1279	def space(s: String, width: U32) -> Doc:
1280	  Str{"", s, width, None{}}
1281	
1282	def nothing() -> Doc:
1283	  Str{"", "", 0, None{}}
1284	
1285	def soft(flat: String, width: U32) -> Doc:
1286	  Line{flat, width, False{}, 0}
1287	
1288	def hard(offset: U32) -> Doc:
1289	  Line{"", 0, True{}, offset}
1290	
1291	def flat_of(d: Doc) -> Flat:
1292	  match d:
1293	    case Str{body, blank, width, Some{t}}:
1294	      Flat{0, True{}}
1295	    case Str{body, blank, width, None{}}:
1296	      Flat{width, False{}}
1297	    case Line{text, width, True{}, offset}:
1298	      Flat{0, True{}}
1299	    case Line{text, width, False{}, offset}:
1300	      Flat{width, False{}}
1301	    case Grp{doc, f}:
1302	      f
1303	    case Nest{doc, amount, f}:
1304	      f
1305	    case Cat{docs, f}:
1306	      f
1307	
1308	# The Flat of a doc a, then of what follows it.
1309	def flat_then(a: Flat, rest: Flat) -> Flat:
1310	  match a rest:
1311	    case Flat{w, True{}} r:
1312	      Flat{w, True{}}
1313	    case Flat{w, False{}} Flat{v, b}:
1314	      Flat{(w + v: U32), b}
1315	
1316	def flat_rev(docs: List<&2, Doc>, acc: Flat) -> Flat:
1317	  match docs:
1318	    case Nil{}:
1319	      acc
1320	    case Con{d, rest}:
1321	      flat_rev(rest, flat_then(flat_of(d), acc))
1322	
1323	def grp(+d: Doc) -> Doc:
1324	  Grp{d, flat_of(d)}
1325	
1326	def nest(+d: Doc, amount: U32) -> Doc:
1327	  Nest{d, amount, flat_of(d)}
1328	
1329	# A Cat of docs last first.
1330	def cat_rev(+docs: List<&2, Doc>) -> Doc:
1331	  Cat{docs, flat_rev(docs, Flat{0, False{}})}
1332	
1333	# A Cat of a few docs, in order.
1334	def cat(docs: List<&2, Doc>) -> Doc:
1335	  cat_rev(List.reverse(&2, Doc, docs))
1336	
1337	def code(t: Token) -> Doc:
1338	  match t:
1339	    case Token{text, beg, end, col, lex, sym, name, tail, from}:
1340	      Str{text, "", (end - beg: U32), None{}}
1341	
1342	def is_glued_prefix(+a: Token, b: Maybe<&2, Tree>) -> Bool:
1343	  match b:
1344	    case Some{n}:
1345	      is_prefix(Token.sym(a)) && U32.is_eq(Token.end(a), Token.beg(first(n)))
1346	    case None{}:
1347	      False{}
1348	
1349	# Whether a group after x is its argument list or type arguments.
1350	def is_callee(+x: Token) -> Bool:
1351	  (
1352	    Token.is_name(x) || is_sym(Token.sym(x), Bang{}) || is_closer(Token.sym(x))
1353	  )
1354	    && Bool.not(is_keyword(Token.sym(x)))
1355	
1356	def is_inc(s: Sym) -> Bool:
1357	  match s:
1358	    case Inc{}:
1359	      True{}
1360	    case _:
1361	      False{}
1362	
1363	# What goes between x and the tree b that y starts. A constructor's brace
1364	# is glued to its name; a brace after a space can instead be the next
1365	# (annotated) argument of a call without commas, so the space stays. Other
1366	# atoms need a space.
1367	def separator.of(+x: Token, +y: Token, +group: Bool, b: Tree) -> Doc:
1368	  Bool.pick(
1369	    Doc,
1370	    is_comment(y),
1371	    space("  ", 2),
1372	    Bool.pick(
1373	      Doc,
1374	      is_tight(Token.sym(y)),
1375	      nothing(),
1376	      Bool.pick(
1377	        Doc,
1378	        is_punct(Token.sym(x)),
1379	        space(" ", 1),
1380	        Bool.pick(
1381	          Doc,
1382	          is_sigil(Token.sym(x)),
1383	          nothing(),
1384	          Bool.pick(
1385	            Doc,
1386	            is_glued_prefix(x, Some{b}),
1387	            nothing(),
1388	            Bool.pick(
1389	              Doc,
1390	              is_inc(Token.sym(x)),
1391	              nothing(),
1392	              Bool.pick(
1393	                Doc,
1394	                group && is_sym(Token.sym(y), Lbrc{}) && U32.is_ne(Token.end(x), Token.beg(y)),
1395	                space(" ", 1),
1396	                Bool.pick(
1397	                  Doc,
1398	                  group && is_opener(Token.sym(y)) && is_callee(x),
1399	                  nothing(),
1400	                  space(" ", 1)
1401	                )
1402	              )
1403	            )
1404	          )
1405	        )
1406	      )
1407	    )
1408	  )
1409	
1410	def separator(a: Tree, +b: Tree) -> Doc:
1411	  separator.of(last(a), first(b), Bool.not(is_leaf(b)), b)
1412	
1413	# "#x" gets a space; empty comments, whitespace, test expectations (#|),
1414	# directives (#!) and headings (##) stay as they are.
1415	def comment_text.after(rest: String, +keep: String) -> String:
1416	  match rest:
1417	    case SNil{}:
1418	      "#"
1419	    case SCon{+c, more}:
1420	      Bool.pick(
1421	        String,
1422	        is_blank(c) || Char.is_eq(c, '#') || Char.is_eq(c, '!') || Char.is_eq(c, '|'),
1423	        "#" ++ keep,
1424	        "# " ++ keep
1425	      )
1426	
1427	def comment_text(text: String, keep: String) -> String:
1428	  match text:
1429	    case SCon{'#', +rest}:
1430	      comment_text.after(rest, rest)
1431	    case _:
1432	      keep
1433	
1434	def leaf_doc(+t: Token) -> Doc:
1435	  match t:
1436	    case Token{text, beg, end, col, Newline{}, sym, name, tail, from}:
1437	      nothing()
1438	    case Token{+text, beg, end, col, Comment{}, sym, name, tail, from}:
1439	      str(comment_text(text, text))
1440	    case Token{text, beg, end, col, Literal{}, sym, name, tail, from}:
1441	      str(text)
1442	    case Token{text, beg, end, col, Code{}, sym, name, tail, from}:
1443	      code(t)
1444	
1445	# Levels
1446	# ------
1447	def should_pop(levels: List<&2, U32>, col: U32) -> Bool:
1448	  match levels:
1449	    case Con{top, Con{x, xs}}:
1450	      U32.is_lt(col, top)
1451	    case _:
1452	      False{}
1453	
1454	def pop_levels(levels: List<&2, U32>, +col: U32, go: Bool) -> List<&2, U32>:
1455	  match levels go:
1456	    case Con{top, +more} True{}:
1457	      pop_levels(more, col, should_pop(more, col))
1458	    case Con{top, more} False{}:
1459	      Con{top, more}
1460	    case Nil{} _:
1461	      Nil{}
1462	
1463	def deepen(levels: List<&2, U32>, +col: U32) -> List<&2, U32>:
1464	  match levels:
1465	    case Nil{}:
1466	      [col]
1467	    case Con{+top, +more}:
1468	      Bool.pick(List<&2, U32>, U32.is_gt(col, top), Con{col, Con{top, more}}, Con{top, more})
1469	
1470	# Closes the levels deeper than col, then opens col if it is deeper.
1471	def indented(+levels: List<&2, U32>, +col: U32) -> List<&2, U32>:
1472	  deepen(pop_levels(levels, col, should_pop(levels, col)), col)
1473	
1474	def depth.go(levels: List<&2, U32>, n: U32) -> U32:
1475	  match levels:
1476	    case Nil{}:
1477	      n
1478	    case Con{top, more}:
1479	      depth.go(more, (n + 1: U32))
1480	
1481	def depth(levels: List<&2, U32>) -> U32:
1482	  (depth.go(levels, 0) - 1: U32)
1483	
1484	# Sequences
1485	# ---------
1486	def fresh(base: U32) -> Seq:
1487	  Seq{[], None{}, None{}, [base], False{}}
1488	
1489	def Seq.put(s: Seq, d: Doc) -> Seq:
1490	  match s:
1491	    case Seq{out, None{}, prev, levels, skip}:
1492	      Seq{Con{d, out}, None{}, prev, levels, skip}
1493	    case Seq{out, Some{chain}, prev, levels, skip}:
1494	      Seq{out, Some{Con{d, chain}}, prev, levels, skip}
1495	
1496	def Seq.chain(s: Seq) -> Seq:
1497	  match s:
1498	    case Seq{out, None{}, prev, levels, skip}:
1499	      Seq{out, Some{[soft(" ", 1)]}, prev, levels, skip}
1500	    case Seq{out, Some{chain}, prev, levels, skip}:
1501	      Seq{out, Some{Con{soft(" ", 1), chain}}, prev, levels, skip}
1502	
1503	def Seq.doc(s: Seq, tab: U32) -> Doc:
1504	  match s:
1505	    case Seq{out, None{}, prev, levels, skip}:
1506	      grp(cat_rev(out))
1507	    case Seq{out, Some{chain}, prev, levels, skip}:
1508	      grp(cat_rev(Con{nest(cat_rev(chain), tab), out}))
1509	
1510	def is_prev_comment(prev: Maybe<&2, Tree>) -> Bool:
1511	  match prev:
1512	    case Some{p}:
1513	      is_comment(last(p))
1514	    case None{}:
1515	      False{}
1516	
1517	# A run of newlines breaks the line at the next tree's level.
1518	def Seq.level(
1519	  +levels: List<&2, U32>,
1520	  tab: U32,
1521	  out: List<&2, Doc>,
1522	  chain: Maybe<&2, List<&2, Doc>>
1523	) -> Seq:
1524	  Seq.put(Seq{out, chain, None{}, levels, True{}}, hard((depth(levels) * tab: U32)))
1525	
1526	def Seq.end(comment: Bool, s: Seq) -> Seq:
1527	  match comment:
1528	    case True{}:
1529	      Seq.put(s, hard(0))
1530	    case False{}:
1531	      s
1532	
1533	def Seq.break(up: Maybe<&2, Tree>, tab: U32, s: Seq) -> Seq:
1534	  match up s:
1535	    case Some{u} Seq{out, chain, prev, levels, skip}:
1536	      Seq.level(indented(levels, Token.col(first(u))), tab, out, chain)
1537	    case None{} Seq{out, chain, prev, levels, skip}:
1538	      Seq.end(is_prev_comment(prev), Seq{out, chain, None{}, levels, True{}})
1539	
1540	def Seq.newline.if(trigger: Bool, rest: List<&2, Tree>, tab: U32, s: Seq) -> Seq:
1541	  match trigger:
1542	    case True{}:
1543	      Seq.break(upcoming(rest), tab, s)
1544	    case False{}:
1545	      s
1546	
1547	def Seq.newline(rest: List<&2, Tree>, tab: U32, raw: Bool, s: Seq) -> Seq:
1548	  match s:
1549	    case Seq{out, chain, prev, levels, True{}}:
1550	      Seq{out, chain, prev, levels, True{}}
1551	    case Seq{out, chain, +prev, levels, False{}}:
1552	      Seq.newline.if(
1553	        raw || is_prev_comment(prev),
1554	        rest,
1555	        tab,
1556	        Seq{out, chain, prev, levels, False{}}
1557	      )
1558	
1559	def Seq.joint(chain: Bool, p: Tree, n: Tree, s: Seq) -> Seq:
1560	  match chain:
1561	    case True{}:
1562	      Seq.chain(s)
1563	    case False{}:
1564	      Seq.put(s, separator(p, n))
1565	
1566	def Seq.tree(+n: Tree, d: Doc, next: Maybe<&2, Tree>, raw: Bool, s: Seq) -> Seq:
1567	  match s:
1568	    case Seq{out, chain, None{}, levels, skip}:
1569	      Seq.put(Seq{out, chain, Some{n}, levels, False{}}, d)
1570	    case Seq{out, chain, Some{p}, levels, skip}:
1571	      Seq.put(
1572	        Seq.joint(
1573	          Bool.not(
1574	            raw
1575	          )
1576	            && is_leaf(n)
1577	            && is_operator(Token.sym(first(n)))
1578	            && Bool.not(is_glued_prefix(first(n), next)),
1579	          p,
1580	          n,
1581	          Seq{out, chain, Some{n}, levels, False{}}
1582	        ),
1583	        d
1584	      )
1585	
1586	def Seq.step(
1587	  newline: Bool,
1588	  n: Tree,
1589	  d: Doc,
1590	  rest: List<&2, Tree>,
1591	  tab: U32,
1592	  raw: Bool,
1593	  s: Seq
1594	) -> Seq:
1595	  match newline:
1596	    case True{}:
1597	      Seq.newline(rest, tab, raw, s)
1598	    case False{}:
1599	      Seq.tree(n, d, head(rest), raw, s)
1600	
1601	def Seq.visit(+n: Tree, d: Doc, rest: List<&2, Tree>, tab: U32, raw: Bool, s: Seq) -> Seq:
1602	  Seq.step(is_newline(n), n, d, rest, tab, raw, s)
1603	
1604	# Parts
1605	# -----
1606	def Split.fresh() -> Split:
1607	  Split{[], True{}, False{}, False{}, False{}}
1608	
1609	def Split.track(+n: Tree, attach: Bool, sp: Split) -> Split:
1610	  match sp:
1611	    case Split{parts, newlines, comment, a, comments}:
1612	      Split{
1613	        parts,
1614	        newlines && is_newline(n),
1615	        Bool.pick(Bool, is_newline(n), comment, is_comment(last(n))),
1616	        attach,
1617	        comments
1618	      }
1619	
1620	def Split.end(tab: U32, base: U32, st: State) -> State:
1621	  match st:
1622	    case State{seq, Split{parts, newlines, comment, attach, comments}}:
1623	      State{
1624	        fresh(base),
1625	        Split{
1626	          Con{Part{Seq.doc(seq, tab), newlines, comment}, parts},
1627	          True{},
1628	          False{},
1629	          False{},
1630	          comments
1631	        }
1632	      }
1633	
1634	def Split.comments(n: Tree, sp: Split) -> Split:
1635	  match sp:
1636	    case Split{parts, newlines, comment, attach, comments}:
1637	      Split{parts, newlines, comment, attach, comments || is_comment(first(n))}
1638	
1639	def has_head_comment(xs: List<&2, Tree>) -> Bool:
1640	  match xs:
1641	    case Con{x, rest}:
1642	      is_comment(first(x))
1643	    case Nil{}:
1644	      False{}
1645	
1646	def Split.act(n: Tree, rest: List<&2, Tree>, sp: Split) -> Act:
1647	  match sp:
1648	    case Split{parts, newlines, comment, True{}, comments}:
1649	      AddEnd{}
1650	    case Split{parts, newlines, comment, False{}, comments}:
1651	      Bool.pick(
1652	        Act,
1653	        is_leaf_of(n, Comma{}),
1654	        Bool.pick(Act, has_head_comment(rest), AddAttach{}, End{}),
1655	        Add{}
1656	      )
1657	
1658	def Split.apply(
1659	  act: Act,
1660	  +n: Tree,
1661	  d: Doc,
1662	  rest: List<&2, Tree>,
1663	  +tab: U32,
1664	  base: U32,
1665	  st: State
1666	) -> State:
1667	  match act st:
1668	    case Add{} State{seq, sp}:
1669	      State{Seq.visit(n, d, rest, tab, False{}, seq), Split.track(n, False{}, sp)}
1670	    case AddAttach{} State{seq, sp}:
1671	      State{Seq.visit(n, d, rest, tab, False{}, seq), Split.track(n, True{}, sp)}
1672	    case AddEnd{} State{seq, sp}:
1673	      Split.end(
1674	        tab,
1675	        base,
1676	        State{Seq.visit(n, d, rest, tab, False{}, seq), Split.track(n, False{}, sp)}
1677	      )
1678	    case End{} State{seq, sp}:
1679	      Split.end(tab, base, State{seq, sp})
1680	
1681	def Split.visit(+n: Tree, d: Doc, +rest: List<&2, Tree>, tab: U32, base: U32, st: State) -> State:
1682	  match st:
1683	    case State{seq, +sp}:
1684	      Split.apply(Split.act(n, rest, sp), n, d, rest, tab, base, State{seq, Split.comments(n, sp)})
1685	
1686	def should_drop(parts: List<&2, Part>) -> Bool:
1687	  match parts:
1688	    case Con{Part{d, True{}, c}, Con{p, ps}}:
1689	      True{}
1690	    case _:
1691	      False{}
1692	
1693	# Drops the trailing parts that hold only newlines, keeping one part.
1694	def drop_parts(parts: List<&2, Part>, go: Bool) -> List<&2, Part>:
1695	  match parts go:
1696	    case Con{p, +rest} True{}:
1697	      drop_parts(rest, should_drop(rest))
1698	    case ps False{}:
1699	      ps
1700	    case Nil{} _:
1701	      Nil{}
1702	
1703	def content.sep(comment: Bool, acc: List<&2, Doc>) -> List<&2, Doc>:
1704	  match comment:
1705	    case True{}:
1706	      Con{hard(0), acc}
1707	    case False{}:
1708	      Con{soft(" ", 1), Con{text(",", 1), acc}}
1709	
1710	def content.go(parts: List<&2, Part>, comment: Bool, acc: List<&2, Doc>) -> List<&2, Doc>:
1711	  match parts:
1712	    case Nil{}:
1713	      acc
1714	    case Con{Part{d, newlines, next}, rest}:
1715	      content.go(rest, next, Con{d, content.sep(comment, acc)})
1716	
1717	# The parts' docs with their separators, last first.
1718	def content(parts: List<&2, Part>) -> List<&2, Doc>:
1719	  match parts:
1720	    case Nil{}:
1721	      []
1722	    case Con{Part{d, newlines, comment}, rest}:
1723	      content.go(rest, comment, [d])
1724	
1725	def opening(comments: Bool) -> Doc:
1726	  match comments:
1727	    case True{}:
1728	      hard(0)
1729	    case False{}:
1730	      soft("", 0)
1731	
1732	# A generic's closing > stays glued to the term before it: Bend parses a
1733	# spaced > as a comparison, even across a newline.
1734	def closing(close: Token, comments: Bool) -> Doc:
1735	  Bool.pick(Doc, is_sym(Token.sym(close), Gt{}), nothing(), opening(comments))
1736	
1737	def Split.doc(open: Token, +close: Token, tab: U32, st: State) -> Doc:
1738	  match st:
1739	    case State{seq, Split{+parts, newlines, comment, attach, +comments}}:
1740	      grp(
1741	        cat(
1742	          [
1743	            code(open),
1744	            nest(
1745	              cat(
1746	                [
1747	                  opening(comments),
1748	                  cat_rev(content(List.reverse(&2, Part, drop_parts(parts, should_drop(parts)))))
1749	                ]
1750	              ),
1751	              tab
1752	            ),
1753	            closing(close, comments),
1754	            code(close)
1755	          ]
1756	        )
1757	      )
1758	
1759	# Build
1760	# -----
1761	def mode_of(open: Token, close: Token, children: List<&2, Tree>, block: Bool) -> Mode:
1762	  match children block:
1763	    case Nil{} _:
1764	      Bare{open, close}
1765	    case _ True{}:
1766	      Block{open, close}
1767	    case _ False{}:
1768	      Parts{open, close}
1769	
1770	def start(base: U32) -> State:
1771	  State{fresh(base), Split.fresh()}
1772	
1773	def visit(
1774	  +mode: Mode,
1775	  n: Tree,
1776	  d: Doc,
1777	  rest: List<&2, Tree>,
1778	  tab: U32,
1779	  base: U32,
1780	  st: State
1781	) -> State:
1782	  match mode st:
1783	    case Plain{} State{seq, sp}:
1784	      State{Seq.visit(n, d, rest, tab, False{}, seq), sp}
1785	    case Block{open, close} State{seq, sp}:
1786	      State{Seq.visit(n, d, rest, tab, True{}, seq), sp}
1787	    case Parts{open, close} st2:
1788	      Split.visit(n, d, rest, tab, base, st2)
1789	    case Bare{open, close} st2:
1790	      st2
1791	
1792	def finish(mode: Mode, st: State, +tab: U32, base: U32) -> Doc:
1793	  match mode st:
1794	    case Plain{} State{seq, sp}:
1795	      Seq.doc(seq, tab)
1796	    case Block{open, close} State{seq, sp}:
1797	      cat([code(open), Seq.doc(seq, tab), code(close)])
1798	    case Parts{open, close} st2:
1799	      Split.doc(open, close, tab, Split.end(tab, base, st2))
1800	    case Bare{open, close} st2:
1801	      cat([code(open), code(close)])
1802	
1803	# The doc of a list of trees, read as mode says. A group's children are
1804	# built first, by the same def, as a smaller part of the list.
1805	def build(nodes: List<&2, Tree>, +tab: U32, +base: U32, +mode: Mode, st: State) -> Doc:
1806	  match nodes:
1807	    case Nil{}:
1808	      finish(mode, st, tab, base)
1809	    case Con{Leaf{+t}, +rest}:
1810	      build(rest, tab, base, mode, visit(mode, Leaf{t}, leaf_doc(t), rest, tab, base, st))
1811	    case Con{Group{+open, +close, +children, +block}, +rest}:
1812	      build(
1813	        rest,
1814	        tab,
1815	        base,
1816	        mode,
1817	        visit(
1818	          mode,
1819	          Group{open, close, children, block},
1820	          build(children, tab, base, mode_of(open, close, children, block), start(base)),
1821	          rest,
1822	          tab,
1823	          base,
1824	          st
1825	        )
1826	      )
1827	
1828	def sequence(nodes: List<&2, Tree>, tab: U32, +base: U32) -> Doc:
1829	  build(nodes, tab, base, Plain{}, start(base))
1830	
1831	# Printer
1832	# -------
1833	# Jobs for a Cat's docs, last first, so its first doc ends on top.
1834	def push(docs: List<&2, Doc>, +indent: U32, +flat: Bool, jobs: List<&2, Job>) -> List<&2, Job>:
1835	  match docs:
1836	    case Nil{}:
1837	      jobs
1838	    case Con{d, rest}:
1839	      push(rest, indent, flat, Con{Job{d, indent, flat}, jobs})
1840	
1841	def fits.flat.of(over: Bool, brk: Bool, jobs: List<&2, Job>, left: U32) -> Fit:
1842	  match over brk:
1843	    case True{} _:
1844	      Stop{False{}}
1845	    case False{} True{}:
1846	      Stop{True{}}
1847	    case False{} False{}:
1848	      Go{jobs, left}
1849	
1850	# A doc printed flat, whole: past the width, or up to a break within it.
1851	def fits.flat(f: Flat, jobs: List<&2, Job>, +left: U32) -> Fit:
1852	  match f:
1853	    case Flat{+w, brk}:
1854	      fits.flat.of(U32.is_gt(w, left), brk, jobs, (left - w: U32))
1855	
1856	def fits.width(stop: Bool, +n: U32, jobs: List<&2, Job>, +left: U32) -> Fit:
1857	  match stop:
1858	    case True{}:
1859	      Stop{True{}}
1860	    case False{}:
1861	      Bool.pick(Fit, U32.is_gt(n, left), Stop{False{}}, Go{jobs, (left - n: U32)})
1862	
1863	def fits.step(jobs: List<&2, Job>, left: U32) -> Fit:
1864	  match jobs:
1865	    case Nil{}:
1866	      Stop{True{}}
1867	    case Con{Job{Str{body, blank, width, tail}, indent, flat}, rest}:
1868	      fits.width(Maybe.is_some(&2, U32, tail), width, rest, left)
1869	    case Con{Job{Line{text, width, hard, offset}, indent, flat}, rest}:
1870	      fits.width(hard || Bool.not(flat), width, rest, left)
1871	    case Con{Job{Grp{doc, f}, indent, flat}, rest}:
1872	      fits.flat(f, rest, left)
1873	    case Con{Job{Nest{doc, amount, f}, indent, flat}, rest}:
1874	      fits.flat(f, rest, left)
1875	    case Con{Job{Cat{docs, f}, indent, True{}}, rest}:
1876	      fits.flat(f, rest, left)
1877	    case Con{Job{Cat{docs, f}, indent, False{}}, rest}:
1878	      Go{push(docs, indent, False{}, rest), left}
1879	
1880	def fits.go(fuel: Nat, f: Fit) -> Bool:
1881	  match fuel f:
1882	    case _ Stop{b}:
1883	      b
1884	    case 0n Go{jobs, left}:
1885	      True{}
1886	    case 1n+k Go{jobs, left}:
1887	      fits.go(k, fits.step(jobs, left))
1888	
1889	def fits.from(over: Bool, fuel: Nat, left: U32, jobs: List<&2, Job>) -> Bool:
1890	  match over:
1891	    case True{}:
1892	      False{}
1893	    case False{}:
1894	      fits.go(fuel, Go{jobs, left})
1895	
1896	# Whether the jobs fit before their first break, from col.
1897	def fits(fuel: Nat, +width: U32, +col: U32, jobs: List<&2, Job>) -> Bool:
1898	  fits.from(U32.is_gt(col, width), fuel, (width - col: U32), jobs)
1899	
1900	def col_of(tail: Maybe<&2, U32>, col: U32, width: U32) -> U32:
1901	  match tail:
1902	    case Some{t}:
1903	      t
1904	    case None{}:
1905	      (col + width: U32)
1906	
1907	# Text goes out after the pending whitespace; its own trailing whitespace
1908	# becomes pending.
1909	def print.str(
1910	  body: String,
1911	  keep: String,
1912	  blank: String,
1913	  jobs: List<&2, Job>,
1914	  out: List<&2, String>,
1915	  pending: String,
1916	  col: U32
1917	) -> Print:
1918	  match body:
1919	    case SNil{}:
1920	      Print{jobs, out, pending ++ blank, col}
1921	    case _:
1922	      Print{jobs, Con{keep, Con{pending, out}}, blank, col}
1923	
1924	def print.line(
1925	  flat: Bool,
1926	  text: String,
1927	  +at: U32,
1928	  jobs: List<&2, Job>,
1929	  out: List<&2, String>,
1930	  pending: String,
1931	  col: U32,
1932	  width: U32,
1933	  newline: String
1934	) -> Print:
1935	  match flat:
1936	    case True{}:
1937	      Print{jobs, out, pending ++ text, (col + width: U32)}
1938	    case False{}:
1939	      Print{jobs, out, newline ++ pad(U32.to_nat(at), ""), at}
1940	
1941	def print.is_flat(
1942	  flat: Bool,
1943	  fuel: Nat,
1944	  +width: Maybe<&2, U32>,
1945	  col: U32,
1946	  jobs: List<&2, Job>
1947	) -> Bool:
1948	  match flat width:
1949	    case True{} _:
1950	      True{}
1951	    case False{} None{}:
1952	      True{}
1953	    case False{} Some{w}:
1954	      fits(fuel, w, col, jobs)
1955	
1956	def is_unbounded(width: Maybe<&2, U32>) -> Bool:
1957	  match width:
1958	    case None{}:
1959	      True{}
1960	    case Some{w}:
1961	      False{}
1962	
1963	def print.step(
1964	  jobs: List<&2, Job>,
1965	  out: List<&2, String>,
1966	  pending: String,
1967	  +col: U32,
1968	  width: Maybe<&2, U32>,
1969	  newline: String,
1970	  fuel: Nat
1971	) -> Print:
1972	  match jobs:
1973	    case Nil{}:
1974	      Print{Nil{}, out, pending, col}
1975	    case Con{Job{Str{+body, blank, w, tail}, indent, flat}, rest}:
1976	      print.str(body, body, blank, rest, out, pending, col_of(tail, col, w))
1977	    case Con{Job{Line{text, w, hard, offset}, +indent, +flat}, rest}:
1978	      print.line(
1979	        Bool.not(hard) && (flat || is_unbounded(width)),
1980	        text,
1981	        (indent + offset: U32),
1982	        rest,
1983	        out,
1984	        pending,
1985	        col,
1986	        w,
1987	        newline
1988	      )
1989	    case Con{Job{Nest{doc, amount, f}, indent, flat}, rest}:
1990	      Print{Con{Job{doc, (indent + amount: U32), flat}, rest}, out, pending, col}
1991	    case Con{Job{Grp{+doc, f}, +indent, +flat}, +rest}:
1992	      Print{
1993	        Con{
1994	          Job{
1995	            doc,
1996	            indent,
1997	            print.is_flat(flat, fuel, width, col, Con{Job{doc, indent, True{}}, rest})
1998	          },
1999	          rest
2000	        },
Lines 1-2000 of 2454. More: https://jend.leeeet.dev/read.txt?path=bend-lint-rules@0.2.1.0/layout/format.bend&start_line=2001