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.
7	import Base
8	import ../lazy/lazy.bend as Lazy
9	import ../syntax/lex.bend as Lex
10	import ../syntax/bind.bend as Bind
11	import ./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
16	def 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
21	type Sem is Data:
22	  Sem{line: U32, col: U32, len: U32, typ: U32}
23	
24	# does the name start with a capital?
25	def 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
33	def 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)
44	def 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)
66	def 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
75	def 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
82	type 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?
86	def 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?
94	def 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
103	def 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?
111	def 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
119	def 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
127	type 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
134	type 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
140	def depth() -> Nat:
141	  16n
142	
143	# a key's way down the index: its low bits, lowest first
144	def 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
152	def 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
162	def 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
172	def 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
180	def 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
188	def 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
196	def 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
204	def 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
212	def 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
222	def 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
230	def 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
239	def 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
248	type Kinds is Data:
249	  Kinds{at: Index, named: Index}
250	
251	# the kind of the binder at a position
252	def 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
257	def 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
262	def 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
272	def 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
280	def 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
288	def 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
296	type 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
300	def 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
309	def 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
322	def 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 `{`?
344	def 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
352	def typ_of(st: Step) -> Maybe<&2, U32>:
353	  Step{typ, cur} = st
354	  typ
355	
356	# a step's cursor
357	def 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
362	def 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
370	def 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
379	def 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
385	def 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
391	def 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)
403	def 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	
412	def 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
418	def data(ee: Enc.Enc, +text: String) -> List<&2, U32>:
419	  data.of(ee, String.lines(text), Bind.bound(text), Lex.tokens(text))