src/lsp/semantic.bend
bolt@1.19.0.0 · 419 lines · 0 definitions
1# lsp/semantic: every token of a document classified for the editor's
2# semantic highlighting, from the lexer's kinds and the binder's resolution.
3# A name's class comes from what it refers to: a parameter stays a parameter
4# at every use, a constructor of this file is one wherever it appears. A name
5# from elsewhere is read by its shape: `Bool.pick` a function, `U32` a type,
6# `Nil{` a constructor.
7import Base
8import bolt@1.19.0.0/src/lazy/lazy.bend as Lazy
9import bolt@1.19.0.0/src/syntax/lex.bend as Lex
10import bolt@1.19.0.0/src/syntax/bind.bend as Bind
11import bolt@1.19.0.0/src/lsp/enc.bend as Enc
12
13# the legend, by index: keyword 0, function 1, type 2, enumMember 3,
14# parameter 4, variable 5, property 6, string 7, number 8, comment 9,
15# typeParameter 10
16def legend() -> List<&2, String>:
17 ["keyword", "function", "type", "enumMember", "parameter", "variable", "property", "string", "number",
18 "comment", "typeParameter"]
19
20# a classified token: where, how long, which type of the legend
21type Sem is Data:
22 Sem{line: U32, col: U32, len: U32, typ: U32}
23
24# does the name start with a capital?
25def upper_first(cs: List<&2, Char>) -> Bool:
26 match cs:
27 case Nil{}:
28 False{}
29 case Con{c, t}:
30 Char.is_upper(c)
31
32# the last segment of a dotted name
33def last_segment(cs: List<&2, Char>, +acc: List<&2, Char>) -> List<&2, Char>:
34 match cs:
35 case Nil{}:
36 List.reverse(&2, Char, acc)
37 case Con{'.', t}:
38 last_segment(t, [])
39 case Con{c, t}:
40 last_segment(t, c <> acc)
41
42# the legend's type for a binder of this kind (an item is a type when
43# capitalized, else a function)
44def of_kind(kk: Bind.BindKind, +name: String) -> U32:
45 match kk:
46 case Bind.KItem{}:
47 Bool.pick(U32, upper_first(String.to_list(name)), 2, 1)
48 case Bind.KCtor{}:
49 3
50 case Bind.KParam{}:
51 4
52 case Bind.KLocal{}:
53 5
54 case Bind.KPat{}:
55 5
56 case Bind.KFor{}:
57 5
58 case Bind.KField{}:
59 6
60 case Bind.KTypeParam{}:
61 10
62 case Bind.KTypeVar{}:
63 10
64
65# the type for a binder that may not have been found (a variable then)
66def of_maybe_kind(mm: Maybe<&2, Bind.BindKind>, name: String) -> U32:
67 match mm:
68 case None{}:
69 5
70 case Some{k}:
71 of_kind(k, name)
72
73# a name from elsewhere: braced: a constructor; capitalized: a type; dotted:
74# a function; else a variable
75def by_shape(+name: String, braced: Bool) -> U32:
76 Bool.pick(U32, upper_first(last_segment(String.to_list(name), [])), Bool.pick(U32, braced, 3, 2),
77 Bool.pick(U32, String.contains(name, "."), 1, 5))
78
79# the binders and uses are in source order, as the tokens are: each token
80# takes the head of either list when it sits there, so a document classifies
81# in one pass
82type Cursor is Data:
83 Cursor{binds: List<&2, Bind.Bind>, uses: List<&2, Bind.Use>}
84
85# does the next binder sit at this position?
86def at_head_bind(binds: List<&2, Bind.Bind>, +line: U32, +col: U32) -> Bool:
87 match binds:
88 case Nil{}:
89 False{}
90 case Con{Bind.Bind{n, l, c, k, note}, rest}:
91 Bool.and(U32.is_eq(l, line), U32.is_eq(c, col))
92
93# does the next use sit at this position?
94def at_head_use(uses: List<&2, Bind.Use>, +line: U32, +col: U32) -> Bool:
95 match uses:
96 case Nil{}:
97 False{}
98 case Con{Bind.Use{n, l, c, tg}, rest}:
99 Bool.and(U32.is_eq(l, line), U32.is_eq(c, col))
100
101# a list's head is behind the token: it was never matched (a name the lexer
102# and the binder disagree on); it is dropped so the rest can line up again
103def behind_bind(binds: List<&2, Bind.Bind>, +line: U32, +col: U32) -> Bool:
104 match binds:
105 case Nil{}:
106 False{}
107 case Con{Bind.Bind{n, +l, c, k, note}, rest}:
108 Bool.or(U32.is_lt(l, line), Bool.and(U32.is_eq(l, line), U32.is_lt(c, col)))
109
110# is the next use behind this position?
111def behind_use(uses: List<&2, Bind.Use>, +line: U32, +col: U32) -> Bool:
112 match uses:
113 case Nil{}:
114 False{}
115 case Con{Bind.Use{n, +l, c, tg}, rest}:
116 Bool.or(U32.is_lt(l, line), Bool.and(U32.is_eq(l, line), U32.is_lt(c, col)))
117
118# the type of the next binder
119def head_bind_kind(binds: List<&2, Bind.Bind>) -> U32:
120 match binds:
121 case Nil{}:
122 5
123 case Con{Bind.Bind{n, l, c, k, note}, rest}:
124 of_kind(k, n)
125
126# a binder where the index keeps it: its name, position and kind
127type Entry is Data:
128 Entry{name: String, line: U32, col: U32, kind: Bind.BindKind}
129
130# binders as a binary trie on the low bits of a key (a binder's line, or its
131# name's hash), a leaf holding the entries that reach it in source order: a
132# lookup is a walk down and a short scan, and finds what a scan of every
133# binder from the front would, as a miss down the path is a miss everywhere
134type Index is Data:
135 INone{}
136 ILeaf{es: List<&2, Entry>}
137 INode{lo: Index, hi: Index}
138
139# how many bits of a key the index branches on
140def depth() -> Nat:
141 16n
142
143# a key's way down the index: its low bits, lowest first
144def path(dd: Nat, +key: U32) -> List<&2, Bool>:
145 match dd:
146 case 0n:
147 Nil{}
148 case 1n+p:
149 U32.is_even(key) <> path(p, U32.shr(key))
150
151# the entries at a leaf, none elsewhere
152def idx.es(ii: Index) -> List<&2, Entry>:
153 match ii:
154 case INone{}:
155 Nil{}
156 case ILeaf{es}:
157 es
158 case INode{_lo, _hi}:
159 Nil{}
160
161# the half of a node a bit goes down, empty elsewhere
162def idx.near(bb: Bool, ii: Index) -> Index:
163 match ii:
164 case INone{}:
165 INone{}
166 case ILeaf{_es}:
167 INone{}
168 case INode{lo, hi}:
169 Bool.pick(Index, bb, lo, hi)
170
171# a node whose half down a bit is sub, and the other half far
172def idx.join(bb: Bool, sub: Index, far: Index) -> Index:
173 match bb:
174 case True{}:
175 INode{sub, far}
176 case False{}:
177 INode{far, sub}
178
179# the index with an entry in front of the ones down its path
180def idx.put(pp: List<&2, Bool>, +ii: Index, +ee: Entry) -> Index:
181 match pp:
182 case Nil{}:
183 ILeaf{ee <> idx.es(ii)}
184 case Con{+bb, rest}:
185 idx.join(bb, idx.put(rest, idx.near(bb, ii), ee), idx.near(Bool.not(bb), ii))
186
187# the entries at the end of a key's path
188def idx.find(pp: List<&2, Bool>, ii: Index) -> List<&2, Entry>:
189 match pp:
190 case Nil{}:
191 idx.es(ii)
192 case Con{bb, rest}:
193 idx.find(rest, idx.near(bb, ii))
194
195# a name's key: its chars folded, base 31
196def hash(ss: String, +acc: U32) -> U32:
197 match ss:
198 case SNil{}:
199 acc
200 case SCon{c, t}:
201 hash(t, (acc * 31 + Char.to_u32(c) : U32))
202
203# every binder, keyed by its line, in source order
204def by_line(binds: List<&2, Bind.Bind>) -> Index:
205 match binds:
206 case Nil{}:
207 INone{}
208 case Con{Bind.Bind{name, +line, col, kind, _note}, rest}:
209 idx.put(path(depth(), line), by_line(rest), Entry{name, line, col, kind})
210
211# an item or constructor into the index by its name's key; other binders pass
212def by_name.one(+name: String, line: U32, col: U32, kk: Bind.BindKind, ii: Index) -> Index:
213 match kk:
214 case Bind.KItem{}:
215 idx.put(path(depth(), hash(name, 0)), ii, Entry{name, line, col, Bind.KItem{}})
216 case Bind.KCtor{}:
217 idx.put(path(depth(), hash(name, 0)), ii, Entry{name, line, col, Bind.KCtor{}})
218 case _other:
219 ii
220
221# the file's items and constructors, keyed by name, in source order
222def by_name(binds: List<&2, Bind.Bind>) -> Index:
223 match binds:
224 case Nil{}:
225 INone{}
226 case Con{Bind.Bind{name, line, col, kind, _note}, rest}:
227 by_name.one(name, line, col, kind, by_name(rest))
228
229# the first entry at a position, as Bind.kind_at finds it
230def at.go(es: List<&2, Entry>, +line: U32, +col: U32) -> Maybe<&2, Bind.BindKind>:
231 match es:
232 case Nil{}:
233 None{}
234 case Con{Entry{_n, l, c, k}, rest}:
235 Lazy.stop(Maybe<&2, Bind.BindKind>, Bool.and(U32.is_eq(l, line), U32.is_eq(c, col)), Some{k},
236 _u => at.go(rest, line, col))
237
238# the first entry of a name, as Bind.kind_of_item finds it
239def named.go(es: List<&2, Entry>, +name: String) -> Maybe<&2, Bind.BindKind>:
240 match es:
241 case Nil{}:
242 None{}
243 case Con{Entry{n, _l, _c, k}, rest}:
244 Lazy.stop(Maybe<&2, Bind.BindKind>, Bind.same(n, name), Some{k}, _u => named.go(rest, name))
245
246# a document's binders, indexed once for every use's lookup: by position,
247# and its items and constructors by name
248type Kinds is Data:
249 Kinds{at: Index, named: Index}
250
251# the kind of the binder at a position
252def kind_at(kk: Kinds, +line: U32, col: U32) -> Maybe<&2, Bind.BindKind>:
253 Kinds{at, _named} = kk
254 at.go(idx.find(path(depth(), line), at), line, col)
255
256# the kind of an item or constructor of the file, by name
257def kind_of_item(kk: Kinds, +name: String) -> Maybe<&2, Bind.BindKind>:
258 Kinds{_at, named} = kk
259 named.go(idx.find(path(depth(), hash(name, 0)), named), name)
260
261# the type of a use, from what it refers to
262def of_target(tg: Bind.Target, all: Kinds, name: String, braced: Bool) -> U32:
263 match tg:
264 case Bind.TLocal{tl, tc}:
265 of_maybe_kind(kind_at(all, tl, tc), name)
266 case Bind.TItem{i}:
267 of_maybe_kind(kind_of_item(all, i), name)
268 case other:
269 by_shape(name, braced)
270
271# the type of the next use
272def head_use_class(uses: List<&2, Bind.Use>, all: Kinds, braced: Bool) -> U32:
273 match uses:
274 case Nil{}:
275 5
276 case Con{Bind.Use{n, l, c, tg}, rest}:
277 of_target(tg, all, n, braced)
278
279# the binders after the next
280def tail_binds(binds: List<&2, Bind.Bind>) -> List<&2, Bind.Bind>:
281 match binds:
282 case Nil{}:
283 Nil{}
284 case Con{h, t}:
285 t
286
287# the uses after the next
288def tail_uses(uses: List<&2, Bind.Use>) -> List<&2, Bind.Use>:
289 match uses:
290 case Nil{}:
291 Nil{}
292 case Con{h, t}:
293 t
294
295# a token's class, when it has one, and the cursor after it
296type Step is Data:
297 Step{typ: Maybe<&2, U32>, cur: Cursor}
298
299# the class of a name: the use that sits on its head, else its own shape
300def use_class(+hu: Bool, +us: List<&2, Bind.Use>, +all: Kinds, +name: String, +braced: Bool) -> U32:
301 match hu:
302 case True{}:
303 head_use_class(us, all, braced)
304 case False{}:
305 by_shape(name, braced)
306
307# a name token's type, taking the binder or the use that sits on it, and the
308# cursor after it
309def name_step(cur: Cursor, +all: Kinds, +name: String, +line: U32, +col: U32, +braced: Bool) -> Step:
310 Cursor{+binds, +uses} = cur
311 +bs = Bool.pick(List<&2, Bind.Bind>, behind_bind(binds, line, col), tail_binds(binds), binds)
312 +us = Bool.pick(List<&2, Bind.Use>, behind_use(uses, line, col), tail_uses(uses), uses)
313 +hb = at_head_bind(bs, line, col)
314 +hu = at_head_use(us, line, col)
315 +of_use = use_class(hu, us, all, name, braced)
316 +typ = Bool.pick(U32, hb, head_bind_kind(bs), of_use)
317 Step{Some{typ}, Cursor{Bool.pick(List<&2, Bind.Bind>, hb, tail_binds(bs), bs),
318 Bool.pick(List<&2, Bind.Use>, hu, tail_uses(us), us)}}
319
320# names ask the binder; keywords are keywords; comments, strings and numbers
321# are left to the editor's grammar, which tells a doc comment from a plain one
322def of_tok(
323 kk: Lex.TokKind,
324 cur: Cursor,
325 all: Kinds,
326 name: String,
327 line: U32,
328 col: U32,
329 braced: Bool
330) -> Step:
331 match kk:
332 case Lex.TKey{}:
333 Step{Some{0}, cur}
334 case Lex.TName{}:
335 name_step(cur, all, name, line, col, braced)
336 case Lex.TUpper{}:
337 name_step(cur, all, name, line, col, braced)
338 case Lex.TDotted{}:
339 name_step(cur, all, name, line, col, braced)
340 case other:
341 Step{None{}, cur}
342
343# does the token list start with `{`?
344def opens_brace(toks: List<&2, Lex.Tok>) -> Bool:
345 match toks:
346 case Con{Lex.Tok{k, +t, l, c}, rest}:
347 String.eq(t, "{")
348 case Nil{}:
349 False{}
350
351# a step's type
352def typ_of(st: Step) -> Maybe<&2, U32>:
353 Step{typ, cur} = st
354 typ
355
356# a step's cursor
357def cur_of(st: Step) -> Cursor:
358 Step{typ, cur} = st
359 cur
360
361# a classified token onto the list, when it has a type
362def put(mm: Maybe<&2, U32>, +line: U32, +col: U32, +len: U32, rest: List<&2, Sem>) -> List<&2, Sem>:
363 match mm:
364 case None{}:
365 rest
366 case Some{typ}:
367 Sem{line, col, len, typ} <> rest
368
369# every token, in order, against the cursor
370def classify(toks: List<&2, Lex.Tok>, cur: Cursor, +all: Kinds) -> List<&2, Sem>:
371 match toks:
372 case Nil{}:
373 Nil{}
374 case Con{Lex.Tok{k, +t, +l, +c}, +rest}:
375 +st = of_tok(k, cur, all, t, l, c, opens_brace(rest))
376 put(typ_of(st), l, c, U32.from_nat(String.length(t)), classify(rest, cur_of(st), all))
377
378# a token's column and length in an encoding, on its line's chars
379def sent.one(+ee: Enc.Enc, +cs: List<&2, Char>, sem: Sem) -> Sem:
380 Sem{line, +col, +len, typ} = sem
381 +start = Enc.out.col(ee, cs, col)
382 Sem{line, start, (Enc.out.col(ee, cs, (col + len : U32)) - start : U32), typ}
383
384# the lines from a token's line on, from lines that start at line cur
385def sent.seek(lines: List<&2, String>, cur: U32, line: U32) -> List<&2, String>:
386 List.drop(&2, String, lines, U32.to_nat((line - cur : U32)))
387
388# the tokens, in order, with columns and lengths in the negotiated encoding
389# (enc.bend's out.col); lines starts at line cur, and the tokens never go
390# back a line
391def sent(sems: List<&2, Sem>, +ee: Enc.Enc, lines: List<&2, String>, cur: U32) -> List<&2, Sem>:
392 match sems:
393 case Nil{}:
394 Nil{}
395 case Con{Sem{+line, col, len, typ}, rest}:
396 +here = sent.seek(lines, cur, line)
397 +cs = String.to_list(Maybe.default(&2, String, List.head(&2, String, here), ""))
398 sent.one(ee, cs, Sem{line, col, len, typ}) <> sent(rest, ee, here, line)
399
400# LSP's encoding: five numbers a token, positions relative to the previous
401# token (a line delta, and a column delta on the same line, absolute on a new
402# one)
403def encode(sems: List<&2, Sem>, +pl: U32, +pc: U32) -> List<&2, U32>:
404 match sems:
405 case Nil{}:
406 Nil{}
407 case Con{Sem{+line, +col, len, typ}, rest}:
408 +same = U32.is_eq(line, pl)
409 +dcol = Bool.pick(U32, same, (col - pc : U32), col)
410 (line - pl : U32) <> (dcol <> (len <> (typ <> (0 <> encode(rest, line, col)))))
411
412def data.of(ee: Enc.Enc, +lines: List<&2, String>, bb: Bind.Bound, toks: List<&2, Lex.Tok>) -> List<&2, U32>:
413 Bind.Bound{+binds, uses, scopes} = bb
414 encode(sent(classify(toks, Cursor{binds, uses}, Kinds{by_line(binds), by_name(binds)}), ee, lines, 0), 0, 0)
415
416# a document's semantic tokens, encoded, their columns and lengths in the
417# negotiated encoding
418def data(ee: Enc.Enc, +text: String) -> List<&2, U32>:
419 data.of(ee, String.lines(text), Bind.bound(text), Lex.tokens(text))