src/syntax/tree.bend
bolt@1.11.0.0 · 452 lines · 0 definitions
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.
14import Base
15import bolt@1.11.0.0/src/lazy/lazy.bend as Lazy
16import bolt@1.11.0.0/src/syntax/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)
22type 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
35type 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
46def 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
54def 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
67def 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)
75def text(nn: Node) -> String:
76 text.of(first(nn))
77
78def 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)
86def line(nn: Node) -> U32:
87 line.of(first(nn))
88
89def 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)
97def col(nn: Node) -> U32:
98 col.of(first(nn))
99
100# is it a group opened by this bracket?
101def 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
109def 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
116def 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
130def 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
138type 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
144type B is Data:
145 B{fresh: Bool, stack: List<&2, Frame>}
146
147# the bracket that closes an opener (`>` for `<` and `<&`)
148def 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 `>`?
154def 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 `>`
162def 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
172def 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
180def 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)
192def 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
200def 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 `<..>`
210def 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
221def 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
229def 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
239def 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
243def 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
249def 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
258def 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
273def 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
278def 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
288def 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
300def 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
309def 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
319def 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
328def 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
336def 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
345def 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?
353def 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
362def 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
369def 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
375def 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
383def 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)
390def 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
395def 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
404def 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
412def 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
418def 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
422def 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
429def 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 `..`)
439def 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)