1	# src/syntax/tree: a source as a concrete syntax tree over its significant tokens:
2	# statements by line and indentation, groups by brackets. Built by one stack
3	# machine over the token list, so a half-written file still yields a tree:
4	#   - a bracket that never closes is closed by the next line at column 0
5	#     (so damage stays inside one item), or by the end of the file;
6	#   - a close bracket that matches nothing on the stack is a stray leaf;
7	#   - `<` opens type arguments only when glued to a name (`List<`, `Maybe<&`);
8	#     a `>`-only operator closes as many angle groups as it has `>`s, each
9	#     only while an angle group is the innermost open one: in
10	#     `List<f(a > b)>` the first `>` is an operator inside `(..)`.
11	# Trivia (spaces, newlines, comments) is not in the tree: read the tokens for
12	# that. The cells (NNil, NCons) live inside the type, as json/value does, so
13	# every walk is a structural recursion on one argument.
14	import Base
15	import ../lazy/lazy.bend as Lazy
16	import ./lex.bend as Lex
17	
18	# what a statement is, by its shape: SDef `def f(..)` (also `@unsafe def`),
19	# SType, SLaw, SImport, SCase `case p:`, SFor `for x: T` / `exs x: T`, SLet
20	# (a `=` or `<-` among its own tokens), else STerm (`match x:`, `do M<T>:`,
21	# `return e`, a call)
22	type StmtKind is Data:
23	  SDef{}
24	  SType{}
25	  SLaw{}
26	  SImport{}
27	  SCase{}
28	  SFor{}
29	  SLet{}
30	  STerm{}
31	
32	# a leaf holds one token; a group its bracket, what is inside, and its close
33	# (None when it never closed); a statement its own tokens and the statements
34	# under it; NNil and NCons chain nodes
35	type Node is Data:
36	  Leaf{tok: Lex.Tok}
37	  Group{open: Lex.Tok, kids: Node, close: Maybe<&2, Lex.Tok>}
38	  Stmt{kind: StmtKind, kids: Node, body: Node}
39	  NNil{}
40	  NCons{head: Node, tail: Node}
41	
42	# cells
43	# -----
44	
45	# a chain, reversed onto acc
46	def reverse(cells: Node, acc: Node) -> Node:
47	  match cells:
48	    case NCons{h, t}:
49	      reverse(t, NCons{h, acc})
50	    case other:
51	      acc
52	
53	# the token a leaf holds; a group's open, a statement's first token
54	def first(nn: Node) -> Maybe<&2, Lex.Tok>:
55	  match nn:
56	    case Leaf{tok}:
57	      Some{tok}
58	    case Group{open, kids, close}:
59	      Some{open}
60	    case Stmt{kind, kids, body}:
61	      first(kids)
62	    case NNil{}:
63	      None{}
64	    case NCons{h, t}:
65	      first(h)
66	
67	def text.of(mm: Maybe<&2, Lex.Tok>) -> String:
68	  match mm:
69	    case None{}:
70	      ""
71	    case Some{Lex.Tok{k, t, l, c}}:
72	      t
73	
74	# the text of a node's first token ("" for none)
75	def text(nn: Node) -> String:
76	  text.of(first(nn))
77	
78	def line.of(mm: Maybe<&2, Lex.Tok>) -> U32:
79	  match mm:
80	    case None{}:
81	      0
82	    case Some{Lex.Tok{k, t, l, c}}:
83	      l
84	
85	# the line of a node's first token (0 for none)
86	def line(nn: Node) -> U32:
87	  line.of(first(nn))
88	
89	def col.of(mm: Maybe<&2, Lex.Tok>) -> U32:
90	  match mm:
91	    case None{}:
92	      0
93	    case Some{Lex.Tok{k, t, l, c}}:
94	      c
95	
96	# the column of a node's first token (0 for none)
97	def col(nn: Node) -> U32:
98	  col.of(first(nn))
99	
100	# is it a group opened by this bracket?
101	def opens(nn: Node, +ss: String) -> Bool:
102	  match nn:
103	    case Group{Lex.Tok{k, t, l, c}, kids, close}:
104	      String.eq(t, ss)
105	    case other:
106	      False{}
107	
108	# the leaves of a tree, in order: the significant tokens
109	def leaf_close(close: Maybe<&2, Lex.Tok>, acc: List<&2, Lex.Tok>) -> List<&2, Lex.Tok>:
110	  match close:
111	    case None{}:
112	      acc
113	    case Some{tok}:
114	      tok <> acc
115	
116	def leaves.go(nn: Node, acc: List<&2, Lex.Tok>) -> List<&2, Lex.Tok>:
117	  match nn:
118	    case Leaf{tok}:
119	      tok <> acc
120	    case Group{open, kids, close}:
121	      leaf_close(close, leaves.go(kids, open <> acc))
122	    case Stmt{kind, kids, body}:
123	      leaves.go(body, leaves.go(kids, acc))
124	    case NNil{}:
125	      acc
126	    case NCons{h, t}:
127	      leaves.go(t, leaves.go(h, acc))
128	
129	# the leaves of a tree, in order: the significant tokens when the tree is faithful
130	def leaves(nn: Node) -> List<&2, Lex.Tok>:
131	  List.reverse(&2, Lex.Tok, leaves.go(nn, []))
132	
133	# building
134	# --------
135	
136	# an open group (its kids reversed), or an open statement (its kids and the
137	# finished statements under it, both reversed); the root holds the items
138	type Frame is Data:
139	  FGroup{open: Lex.Tok, kids: Node}
140	  FStmt{indent: U32, kids: Node, body: Node}
141	  FRoot{body: Node}
142	
143	# fresh: the next significant token starts a line
144	type B is Data:
145	  B{fresh: Bool, stack: List<&2, Frame>}
146	
147	# the bracket that closes an opener (`>` for `<` and `<&`)
148	def closer(+oo: String) -> String:
149	  Bool.pick(String, String.eq(oo, "("), ")",
150	    Bool.pick(String, String.eq(oo, "["), "]",
151	      Bool.pick(String, String.eq(oo, "{"), "}", ">")))
152	
153	# is every char a `>`?
154	def all_gt(cs: List<&2, Char>) -> Bool:
155	  match cs:
156	    case Nil{}:
157	      True{}
158	    case Con{+c, t}:
159	      Lazy.and_then(Char.is_eq(c, '>'), _u => all_gt(t))
160	
161	# a token that closes a group: `)`, `]`, `}` or a run of `>`
162	def closes_with(kk: Lex.TokKind, +tt: String) -> Bool:
163	  match kk:
164	    case Lex.TClose{}:
165	      True{}
166	    case Lex.TOp{}:
167	      Bool.and(Bool.not(String.is_empty(tt)), all_gt(String.to_list(tt)))
168	    case other:
169	      False{}
170	
171	# `<` or `<&` right after a name opens type arguments
172	def opens_angle(kk: Lex.TokKind, +tt: String, glued: Bool) -> Bool:
173	  match kk:
174	    case Lex.TOp{}:
175	      Bool.and(glued, Bool.or(String.eq(tt, "<"), String.eq(tt, "<&")))
176	    case other:
177	      False{}
178	
179	# a finished node lands in the frame below
180	def put(stack: List<&2, Frame>, nn: Node) -> List<&2, Frame>:
181	  match stack:
182	    case Nil{}:
183	      Nil{}
184	    case Con{FGroup{open, kids}, rest}:
185	      FGroup{open, NCons{nn, kids}} <> rest
186	    case Con{FStmt{indent, kids, body}, rest}:
187	      FStmt{indent, NCons{nn, kids}, body} <> rest
188	    case Con{FRoot{body}, rest}:
189	      FRoot{NCons{nn, body}} <> rest
190	
191	# the innermost open group, closed by close (None: never closed)
192	def close_one(stack: List<&2, Frame>, close: Maybe<&2, Lex.Tok>) -> List<&2, Frame>:
193	  match stack:
194	    case Con{FGroup{open, kids}, rest}:
195	      put(rest, Group{open, reverse(kids, NNil{}), close})
196	    case other:
197	      other
198	
199	# one more group above the one found below, when one was
200	def depth_to.up(below: Nat) -> Nat:
201	  match below:
202	    case Zero{}:
203	      0n
204	    case Succ{p}:
205	      Succ{Succ{p}}
206	
207	# how many groups sit open above the one that c closes (counting it); 0 when
208	# none does. A `>` closes only an angle group on top: inside `(..)`, `[..]`
209	# or `{..}` it is an operator, even within `<..>`
210	def depth_to(stack: List<&2, Frame>, +cc: String) -> Nat:
211	  match stack:
212	    case Nil{}:
213	      0n
214	    case Con{FGroup{Lex.Tok{k, +t, l, c2}, kids}, rest}:
215	      Lazy.stop(Nat, String.eq(closer(t), cc), 1n,
216	        _u => Lazy.stop(Nat, String.eq(cc, ">"), 0n, _v => depth_to.up(depth_to(rest, cc))))
217	    case Con{other, rest}:
218	      0n
219	
220	# how many groups sit open on top of the stack
221	def groups(stack: List<&2, Frame>) -> Nat:
222	  match stack:
223	    case Con{FGroup{open, kids}, rest}:
224	      Succ{groups(rest)}
225	    case other:
226	      0n
227	
228	# n groups close, innermost first; only the last gets the close token
229	def close_n(nn: Nat, stack: List<&2, Frame>, close: Maybe<&2, Lex.Tok>) -> List<&2, Frame>:
230	  match nn:
231	    case Zero{}:
232	      stack
233	    case Succ{Zero{}}:
234	      close_one(stack, close)
235	    case Succ{p}:
236	      close_n(p, close_one(stack, None{}), close)
237	
238	# every open group closes, unclosed
239	def close_all(+stack: List<&2, Frame>) -> List<&2, Frame>:
240	  close_n(groups(stack), stack, None{})
241	
242	# a close bracket: to its match if it has one, else a stray leaf
243	def close_tok(+stack: List<&2, Frame>, +close: Lex.Tok) -> List<&2, Frame>:
244	  Lex.Tok{k, +t, l, c} = close
245	  +n = depth_to(stack, t)
246	  Lazy.stop(List<&2, Frame>, Nat.is_eq(n, 0n), put(stack, Leaf{close}), _u => close_n(n, stack, Some{close}))
247	
248	# `>>` closes two angle groups
249	def close_gts(cs: List<&2, Char>, stack: List<&2, Frame>, +ll: U32, +cc: U32) -> List<&2, Frame>:
250	  match cs:
251	    case Nil{}:
252	      stack
253	    case Con{ch, t}:
254	      close_gts(t, close_tok(stack, Lex.Tok{Lex.TOp{}, ">", ll, cc}), ll, (cc + 1 : U32))
255	
256	# the close a bracket makes, given whether it is a run of `>`: a match, so
257	# only the side taken runs
258	def close_any.at(
259	  +gt: Bool,
260	  +stack: List<&2, Frame>,
261	  +close: Lex.Tok,
262	  +tt: String,
263	  +ll: U32,
264	  +cc: U32
265	) -> List<&2, Frame>:
266	  match gt:
267	    case True{}:
268	      close_gts(String.to_list(tt), stack, ll, cc)
269	    case False{}:
270	      close_tok(stack, close)
271	
272	# a close bracket, or a run of `>`, closes what it can
273	def close_any(+stack: List<&2, Frame>, +close: Lex.Tok) -> List<&2, Frame>:
274	  Lex.Tok{k, +t, +l, +c} = close
275	  close_any.at(String.starts_with(t, ">"), stack, close, t, l, c)
276	
277	# a finished statement lands in the body of the frame below
278	def put_stmt(stack: List<&2, Frame>, nn: Node) -> List<&2, Frame>:
279	  match stack:
280	    case Con{FStmt{indent, kids, body}, rest}:
281	      FStmt{indent, kids, NCons{nn, body}} <> rest
282	    case Con{FRoot{body}, rest}:
283	      FRoot{NCons{nn, body}} <> rest
284	    case other:
285	      other
286	
287	# a `=` or `<-` among a statement's own tokens
288	def binds_in(kids: Node) -> Bool:
289	  match kids:
290	    case NCons{Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
291	      True{}
292	    case NCons{Leaf{Lex.Tok{Lex.TBind{}, t, l, c}}, rest}:
293	      True{}
294	    case NCons{h, rest}:
295	      binds_in(rest)
296	    case other:
297	      False{}
298	
299	# the kind of a statement led by this keyword
300	def keyword_kind(+tt: String) -> StmtKind:
301	  Bool.pick(StmtKind, String.eq(tt, "def"), SDef{},
302	    Bool.pick(StmtKind, String.eq(tt, "type"), SType{},
303	      Bool.pick(StmtKind, String.eq(tt, "law"), SLaw{},
304	        Bool.pick(StmtKind, String.eq(tt, "import"), SImport{},
305	          Bool.pick(StmtKind, String.eq(tt, "case"), SCase{},
306	            Bool.pick(StmtKind, Bool.or(String.eq(tt, "for"), String.eq(tt, "exs")), SFor{}, STerm{}))))))
307	
308	# a statement's kind from its own tokens
309	def classify(kids: Node) -> StmtKind:
310	  match kids:
311	    case NCons{Leaf{Lex.Tok{Lex.TKey{}, t, l, c}}, rest}:
312	      keyword_kind(t)
313	    case NCons{Leaf{Lex.Tok{Lex.TAll{}, t, l, c}}, rest}:
314	      SDef{}
315	    case other:
316	      Bool.pick(StmtKind, binds_in(other), SLet{}, STerm{})
317	
318	# the innermost open statement is finished and lands in its parent
319	def end_stmt(stack: List<&2, Frame>) -> List<&2, Frame>:
320	  match stack:
321	    case Con{FStmt{indent, kids, body}, rest}:
322	      +ks = reverse(kids, NNil{})
323	      put_stmt(rest, Stmt{classify(ks), ks, reverse(body, NNil{})})
324	    case other:
325	      other
326	
327	# n statements finish, innermost first
328	def end_n(nn: Nat, stack: List<&2, Frame>) -> List<&2, Frame>:
329	  match nn:
330	    case Zero{}:
331	      stack
332	    case Succ{p}:
333	      end_n(p, end_stmt(stack))
334	
335	# the statements a line at column col ends: those not shallower than it
336	def deeper(stack: List<&2, Frame>, +col: U32) -> Nat:
337	  match stack:
338	    case Con{FStmt{+indent, kids, body}, rest}:
339	      +below = deeper(rest, col)
340	      Bool.pick(Nat, U32.is_ge(indent, col), Succ{below}, 0n)
341	    case other:
342	      0n
343	
344	# how many statements sit open on the stack
345	def stmts(stack: List<&2, Frame>) -> Nat:
346	  match stack:
347	    case Con{FStmt{indent, kids, body}, rest}:
348	      Succ{stmts(rest)}
349	    case other:
350	      0n
351	
352	# is the innermost frame an open group?
353	def in_group(stack: List<&2, Frame>) -> Bool:
354	  match stack:
355	    case Con{FGroup{open, kids}, rest}:
356	      True{}
357	    case other:
358	      False{}
359	
360	# a new statement at column c, once the ones it ends are finished; inside a
361	# group a line is just more tokens
362	def open_stmt(+stack: List<&2, Frame>, +cc: U32) -> List<&2, Frame>:
363	  Lazy.stop(List<&2, Frame>, in_group(stack), stack,
364	    _u => FStmt{cc, NNil{}, NNil{}} <> end_n(deeper(stack, cc), stack))
365	
366	# a significant token that starts a line: at column 0 it closes every open
367	# group (unless it is a bracket closing one of them); outside a group it opens
368	# a statement
369	def fresh(+stack: List<&2, Frame>, +tok: Lex.Tok) -> List<&2, Frame>:
370	  Lex.Tok{k, t, l, +c} = tok
371	  +cuts = Bool.and(Bool.and(in_group(stack), U32.is_eq(c, 0)), Nat.is_eq(depth_to(stack, t), 0n))
372	  open_stmt(Lazy.stop(List<&2, Frame>, Bool.not(cuts), stack, _u => close_all(stack)), c)
373	
374	# an open bracket or a leaf into the innermost frame
375	def push(+stack: List<&2, Frame>, +tok: Lex.Tok, glued: Bool) -> List<&2, Frame>:
376	  Lex.Tok{+k, +t, l, c} = tok
377	  Lazy.stop(List<&2, Frame>, Bool.not(closes_with(k, t)),
378	    Bool.pick(List<&2, Frame>, Bool.or(Lex.is_open(k), opens_angle(k, t, glued)), FGroup{tok, NNil{}} <> stack,
379	      put(stack, Leaf{tok})),
380	    _u => close_any(stack, tok))
381	
382	# glued: the previous token was a name with nothing between
383	def step(+tok: Lex.Tok, st: B, glued: Bool) -> B:
384	  Lex.Tok{+k, t, l, c} = tok
385	  B{+fr, +stack} = st
386	  Lazy.stop(B, Bool.not(Lex.significant(k)), B{Bool.or(fr, Lex.is_nl(k)), stack},
387	    _u => B{False{}, push(Lazy.stop(List<&2, Frame>, Bool.not(fr), stack, _u2 => fresh(stack, tok)), tok, glued)})
388	
389	# an identifier of any kind (what `<` glues to)
390	def is_name_tok(tok: Lex.Tok) -> Bool:
391	  Lex.Tok{k, t, l, c} = tok
392	  Lex.is_name(k)
393	
394	# every token, in order
395	def run(toks: List<&2, Lex.Tok>, st: B, glued: Bool) -> B:
396	  match toks:
397	    case Nil{}:
398	      st
399	    case Con{+tok, t}:
400	      +g = is_name_tok(tok)
401	      run(t, step(tok, st, glued), g)
402	
403	# the items gathered in the root frame
404	def root(stack: List<&2, Frame>) -> Node:
405	  match stack:
406	    case Con{FRoot{body}, rest}:
407	      reverse(body, NNil{})
408	    case other:
409	      NNil{}
410	
411	# the tree once the tokens are over: every group and statement closes
412	def finish(st: B) -> Node:
413	  B{fr, stack} = st
414	  +closed = close_all(stack)
415	  root(end_n(stmts(closed), closed))
416	
417	# the items of a source: a chain of statements
418	def of_tokens(toks: List<&2, Lex.Tok>) -> Node:
419	  finish(run(toks, B{True{}, [FRoot{NNil{}}]}, False{}))
420	
421	# the items of a source: a chain of statements
422	def parse(source: String) -> Node:
423	  of_tokens(Lex.tokens(source))
424	
425	# showing
426	# -------
427	
428	# a group's close bracket, `..` when it never closed
429	def show_close(close: Maybe<&2, Lex.Tok>) -> String:
430	  match close:
431	    case None{}:
432	      ".."
433	    case Some{Lex.Tok{k, t, l, c}}:
434	      t
435	
436	# `[def f (x : U32) -> U32 : {[match x {[case A {} : {[1]}]}]}]`: a statement
437	# in brackets, its body in braces, a group as its brackets (an unclosed one
438	# ends in `..`)
439	def show(nn: Node) -> String:
440	  match nn:
441	    case Leaf{Lex.Tok{k, t, l, c}}:
442	      t
443	    case Group{Lex.Tok{k, t, l, c}, kids, close}:
444	      t ++ show(kids) ++ show_close(close)
445	    case Stmt{kind, kids, body}:
446	      +b = show(body)
447	      "[" ++ show(kids) ++ Bool.pick(String, String.is_empty(b), "", " {" ++ b ++ "}") ++ "]"
448	    case NNil{}:
449	      ""
450	    case NCons{h, t}:
451	      +rest = show(t)
452	      show(h) ++ Bool.pick(String, String.is_empty(rest), "", " " ++ rest)