~/bend-docscommunity

src/lsp/semantic.bend source

src/lsp/semantic.bend on the hub · documented module

# lsp/semantic: every token of a document classified for the editor's# semantic highlighting, from the lexer's kinds and the binder's resolution.# A name's class comes from what it refers to: a parameter stays a parameter# at every use, a constructor of this file is one wherever it appears. A name# from elsewhere is read by its shape: `Bool.pick` a function, `U32` a type,# `Nil{` a constructor.import Baseimport ../lazy/lazy.bend as Lazyimport ../syntax/lex.bend as Leximport ../syntax/bind.bend as Bindimport ./enc.bend as Enc# the legend, by index: keyword 0, function 1, type 2, enumMember 3,# parameter 4, variable 5, property 6, string 7, number 8, comment 9,# typeParameter 10def legend() -> List<&2, String>:  ["keyword", "function", "type", "enumMember", "parameter", "variable", "property", "string", "number",   "comment", "typeParameter"]# a classified token: where, how long, which type of the legendtype Sem is Data:  Sem{line: U32, col: U32, len: U32, typ: U32}# does the name start with a capital?def upper_first(cs: List<&2, Char>) -> Bool:  match cs:    case Nil{}:      False{}    case Con{c, t}:      Char.is_upper(c)# the last segment of a dotted namedef last_segment(cs: List<&2, Char>, +acc: List<&2, Char>) -> List<&2, Char>:  match cs:    case Nil{}:      List.reverse(&2, Char, acc)    case Con{'.', t}:      last_segment(t, [])    case Con{c, t}:      last_segment(t, c <> acc)# the legend's type for a binder of this kind (an item is a type when# capitalized, else a function)def of_kind(kk: Bind.BindKind, +name: String) -> U32:  match kk:    case Bind.KItem{}:      Bool.pick(U32, upper_first(String.to_list(name)), 2, 1)    case Bind.KCtor{}:      3    case Bind.KParam{}:      4    case Bind.KLocal{}:      5    case Bind.KPat{}:      5    case Bind.KFor{}:      5    case Bind.KField{}:      6    case Bind.KTypeParam{}:      10    case Bind.KTypeVar{}:      10# the type for a binder that may not have been found (a variable then)def of_maybe_kind(mm: Maybe<&2, Bind.BindKind>, name: String) -> U32:  match mm:    case None{}:      5    case Some{k}:      of_kind(k, name)# a name from elsewhere: braced: a constructor; capitalized: a type; dotted:# a function; else a variabledef by_shape(+name: String, braced: Bool) -> U32:  Bool.pick(U32, upper_first(last_segment(String.to_list(name), [])), Bool.pick(U32, braced, 3, 2),    Bool.pick(U32, String.contains(name, "."), 1, 5))# the binders and uses are in source order, as the tokens are: each token# takes the head of either list when it sits there, so a document classifies# in one passtype Cursor is Data:  Cursor{binds: List<&2, Bind.Bind>, uses: List<&2, Bind.Use>}# does the next binder sit at this position?def at_head_bind(binds: List<&2, Bind.Bind>, +line: U32, +col: U32) -> Bool:  match binds:    case Nil{}:      False{}    case Con{Bind.Bind{n, l, c, k, note}, rest}:      Bool.and(U32.is_eq(l, line), U32.is_eq(c, col))# does the next use sit at this position?def at_head_use(uses: List<&2, Bind.Use>, +line: U32, +col: U32) -> Bool:  match uses:    case Nil{}:      False{}    case Con{Bind.Use{n, l, c, tg}, rest}:      Bool.and(U32.is_eq(l, line), U32.is_eq(c, col))# a list's head is behind the token: it was never matched (a name the lexer# and the binder disagree on); it is dropped so the rest can line up againdef behind_bind(binds: List<&2, Bind.Bind>, +line: U32, +col: U32) -> Bool:  match binds:    case Nil{}:      False{}    case Con{Bind.Bind{n, +l, c, k, note}, rest}:      Bool.or(U32.is_lt(l, line), Bool.and(U32.is_eq(l, line), U32.is_lt(c, col)))# is the next use behind this position?def behind_use(uses: List<&2, Bind.Use>, +line: U32, +col: U32) -> Bool:  match uses:    case Nil{}:      False{}    case Con{Bind.Use{n, +l, c, tg}, rest}:      Bool.or(U32.is_lt(l, line), Bool.and(U32.is_eq(l, line), U32.is_lt(c, col)))# the type of the next binderdef head_bind_kind(binds: List<&2, Bind.Bind>) -> U32:  match binds:    case Nil{}:      5    case Con{Bind.Bind{n, l, c, k, note}, rest}:      of_kind(k, n)# a binder where the index keeps it: its name, position and kindtype Entry is Data:  Entry{name: String, line: U32, col: U32, kind: Bind.BindKind}# binders as a binary trie on the low bits of a key (a binder's line, or its# name's hash), a leaf holding the entries that reach it in source order: a# lookup is a walk down and a short scan, and finds what a scan of every# binder from the front would, as a miss down the path is a miss everywheretype Index is Data:  INone{}  ILeaf{es: List<&2, Entry>}  INode{lo: Index, hi: Index}# how many bits of a key the index branches ondef depth() -> Nat:  16n# a key's way down the index: its low bits, lowest firstdef path(dd: Nat, +key: U32) -> List<&2, Bool>:  match dd:    case 0n:      Nil{}    case 1n+p:      U32.is_even(key) <> path(p, U32.shr(key))# the entries at a leaf, none elsewheredef idx.es(ii: Index) -> List<&2, Entry>:  match ii:    case INone{}:      Nil{}    case ILeaf{es}:      es    case INode{_lo, _hi}:      Nil{}# the half of a node a bit goes down, empty elsewheredef idx.near(bb: Bool, ii: Index) -> Index:  match ii:    case INone{}:      INone{}    case ILeaf{_es}:      INone{}    case INode{lo, hi}:      Bool.pick(Index, bb, lo, hi)# a node whose half down a bit is sub, and the other half fardef idx.join(bb: Bool, sub: Index, far: Index) -> Index:  match bb:    case True{}:      INode{sub, far}    case False{}:      INode{far, sub}# the index with an entry in front of the ones down its pathdef idx.put(pp: List<&2, Bool>, +ii: Index, +ee: Entry) -> Index:  match pp:    case Nil{}:      ILeaf{ee <> idx.es(ii)}    case Con{+bb, rest}:      idx.join(bb, idx.put(rest, idx.near(bb, ii), ee), idx.near(Bool.not(bb), ii))# the entries at the end of a key's pathdef idx.find(pp: List<&2, Bool>, ii: Index) -> List<&2, Entry>:  match pp:    case Nil{}:      idx.es(ii)    case Con{bb, rest}:      idx.find(rest, idx.near(bb, ii))# a name's key: its chars folded, base 31def hash(ss: String, +acc: U32) -> U32:  match ss:    case SNil{}:      acc    case SCon{c, t}:      hash(t, (acc * 31 + Char.to_u32(c) : U32))# every binder, keyed by its line, in source orderdef by_line(binds: List<&2, Bind.Bind>) -> Index:  match binds:    case Nil{}:      INone{}    case Con{Bind.Bind{name, +line, col, kind, _note}, rest}:      idx.put(path(depth(), line), by_line(rest), Entry{name, line, col, kind})# an item or constructor into the index by its name's key; other binders passdef by_name.one(+name: String, line: U32, col: U32, kk: Bind.BindKind, ii: Index) -> Index:  match kk:    case Bind.KItem{}:      idx.put(path(depth(), hash(name, 0)), ii, Entry{name, line, col, Bind.KItem{}})    case Bind.KCtor{}:      idx.put(path(depth(), hash(name, 0)), ii, Entry{name, line, col, Bind.KCtor{}})    case _other:      ii# the file's items and constructors, keyed by name, in source orderdef by_name(binds: List<&2, Bind.Bind>) -> Index:  match binds:    case Nil{}:      INone{}    case Con{Bind.Bind{name, line, col, kind, _note}, rest}:      by_name.one(name, line, col, kind, by_name(rest))# the first entry at a position, as Bind.kind_at finds itdef at.go(es: List<&2, Entry>, +line: U32, +col: U32) -> Maybe<&2, Bind.BindKind>:  match es:    case Nil{}:      None{}    case Con{Entry{_n, l, c, k}, rest}:      Lazy.stop(Maybe<&2, Bind.BindKind>, Bool.and(U32.is_eq(l, line), U32.is_eq(c, col)), Some{k},        _u => at.go(rest, line, col))# the first entry of a name, as Bind.kind_of_item finds itdef named.go(es: List<&2, Entry>, +name: String) -> Maybe<&2, Bind.BindKind>:  match es:    case Nil{}:      None{}    case Con{Entry{n, _l, _c, k}, rest}:      Lazy.stop(Maybe<&2, Bind.BindKind>, Bind.same(n, name), Some{k}, _u => named.go(rest, name))# a document's binders, indexed once for every use's lookup: by position,# and its items and constructors by nametype Kinds is Data:  Kinds{at: Index, named: Index}# the kind of the binder at a positiondef kind_at(kk: Kinds, +line: U32, col: U32) -> Maybe<&2, Bind.BindKind>:  Kinds{at, _named} = kk  at.go(idx.find(path(depth(), line), at), line, col)# the kind of an item or constructor of the file, by namedef kind_of_item(kk: Kinds, +name: String) -> Maybe<&2, Bind.BindKind>:  Kinds{_at, named} = kk  named.go(idx.find(path(depth(), hash(name, 0)), named), name)# the type of a use, from what it refers todef of_target(tg: Bind.Target, all: Kinds, name: String, braced: Bool) -> U32:  match tg:    case Bind.TLocal{tl, tc}:      of_maybe_kind(kind_at(all, tl, tc), name)    case Bind.TItem{i}:      of_maybe_kind(kind_of_item(all, i), name)    case other:      by_shape(name, braced)# the type of the next usedef head_use_class(uses: List<&2, Bind.Use>, all: Kinds, braced: Bool) -> U32:  match uses:    case Nil{}:      5    case Con{Bind.Use{n, l, c, tg}, rest}:      of_target(tg, all, n, braced)# the binders after the nextdef tail_binds(binds: List<&2, Bind.Bind>) -> List<&2, Bind.Bind>:  match binds:    case Nil{}:      Nil{}    case Con{h, t}:      t# the uses after the nextdef tail_uses(uses: List<&2, Bind.Use>) -> List<&2, Bind.Use>:  match uses:    case Nil{}:      Nil{}    case Con{h, t}:      t# a token's class, when it has one, and the cursor after ittype Step is Data:  Step{typ: Maybe<&2, U32>, cur: Cursor}# the class of a name: the use that sits on its head, else its own shapedef use_class(+hu: Bool, +us: List<&2, Bind.Use>, +all: Kinds, +name: String, +braced: Bool) -> U32:  match hu:    case True{}:      head_use_class(us, all, braced)    case False{}:      by_shape(name, braced)# a name token's type, taking the binder or the use that sits on it, and the# cursor after itdef name_step(cur: Cursor, +all: Kinds, +name: String, +line: U32, +col: U32, +braced: Bool) -> Step:  Cursor{+binds, +uses} = cur  +bs = Bool.pick(List<&2, Bind.Bind>, behind_bind(binds, line, col), tail_binds(binds), binds)  +us = Bool.pick(List<&2, Bind.Use>, behind_use(uses, line, col), tail_uses(uses), uses)  +hb = at_head_bind(bs, line, col)  +hu = at_head_use(us, line, col)  +of_use = use_class(hu, us, all, name, braced)  +typ = Bool.pick(U32, hb, head_bind_kind(bs), of_use)  Step{Some{typ}, Cursor{Bool.pick(List<&2, Bind.Bind>, hb, tail_binds(bs), bs),    Bool.pick(List<&2, Bind.Use>, hu, tail_uses(us), us)}}# names ask the binder; keywords are keywords; comments, strings and numbers# are left to the editor's grammar, which tells a doc comment from a plain onedef of_tok(  kk: Lex.TokKind,  cur: Cursor,  all: Kinds,  name: String,  line: U32,  col: U32,  braced: Bool) -> Step:  match kk:    case Lex.TKey{}:      Step{Some{0}, cur}    case Lex.TName{}:      name_step(cur, all, name, line, col, braced)    case Lex.TUpper{}:      name_step(cur, all, name, line, col, braced)    case Lex.TDotted{}:      name_step(cur, all, name, line, col, braced)    case other:      Step{None{}, cur}# does the token list start with `{`?def opens_brace(toks: List<&2, Lex.Tok>) -> Bool:  match toks:    case Con{Lex.Tok{k, +t, l, c}, rest}:      String.eq(t, "{")    case Nil{}:      False{}# a step's typedef typ_of(st: Step) -> Maybe<&2, U32>:  Step{typ, cur} = st  typ# a step's cursordef cur_of(st: Step) -> Cursor:  Step{typ, cur} = st  cur# a classified token onto the list, when it has a typedef put(mm: Maybe<&2, U32>, +line: U32, +col: U32, +len: U32, rest: List<&2, Sem>) -> List<&2, Sem>:  match mm:    case None{}:      rest    case Some{typ}:      Sem{line, col, len, typ} <> rest# every token, in order, against the cursordef classify(toks: List<&2, Lex.Tok>, cur: Cursor, +all: Kinds) -> List<&2, Sem>:  match toks:    case Nil{}:      Nil{}    case Con{Lex.Tok{k, +t, +l, +c}, +rest}:      +st = of_tok(k, cur, all, t, l, c, opens_brace(rest))      put(typ_of(st), l, c, U32.from_nat(String.length(t)), classify(rest, cur_of(st), all))# a token's column and length in an encoding, on its line's charsdef sent.one(+ee: Enc.Enc, +cs: List<&2, Char>, sem: Sem) -> Sem:  Sem{line, +col, +len, typ} = sem  +start = Enc.out.col(ee, cs, col)  Sem{line, start, (Enc.out.col(ee, cs, (col + len : U32)) - start : U32), typ}# the lines from a token's line on, from lines that start at line curdef sent.seek(lines: List<&2, String>, cur: U32, line: U32) -> List<&2, String>:  List.drop(&2, String, lines, U32.to_nat((line - cur : U32)))# the tokens, in order, with columns and lengths in the negotiated encoding# (enc.bend's out.col); lines starts at line cur, and the tokens never go# back a linedef sent(sems: List<&2, Sem>, +ee: Enc.Enc, lines: List<&2, String>, cur: U32) -> List<&2, Sem>:  match sems:    case Nil{}:      Nil{}    case Con{Sem{+line, col, len, typ}, rest}:      +here = sent.seek(lines, cur, line)      +cs = String.to_list(Maybe.default(&2, String, List.head(&2, String, here), ""))      sent.one(ee, cs, Sem{line, col, len, typ}) <> sent(rest, ee, here, line)# LSP's encoding: five numbers a token, positions relative to the previous# token (a line delta, and a column delta on the same line, absolute on a new# one)def encode(sems: List<&2, Sem>, +pl: U32, +pc: U32) -> List<&2, U32>:  match sems:    case Nil{}:      Nil{}    case Con{Sem{+line, +col, len, typ}, rest}:      +same = U32.is_eq(line, pl)      +dcol = Bool.pick(U32, same, (col - pc : U32), col)      (line - pl : U32) <> (dcol <> (len <> (typ <> (0 <> encode(rest, line, col)))))def data.of(ee: Enc.Enc, +lines: List<&2, String>, bb: Bind.Bound, toks: List<&2, Lex.Tok>) -> List<&2, U32>:  Bind.Bound{+binds, uses, scopes} = bb  encode(sent(classify(toks, Cursor{binds, uses}, Kinds{by_line(binds), by_name(binds)}), ee, lines, 0), 0, 0)# a document's semantic tokens, encoded, their columns and lengths in the# negotiated encodingdef data(ee: Enc.Enc, +text: String) -> List<&2, U32>:  data.of(ee, String.lines(text), Bind.bound(text), Lex.tokens(text))