Giant blob of minor changes
[dotfiles/.git] / .config / coc / extensions / coc-go-data / tools / pkg / mod / golang.org / x / tools@v0.0.0-20201028153306-37f0764111ff / internal / lsp / semantic.go
1 // Copyright 2020 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package lsp
6
7 import (
8         "bytes"
9         "context"
10         "fmt"
11         "go/ast"
12         "go/token"
13         "go/types"
14         "log"
15         "sort"
16         "strings"
17         "time"
18
19         "golang.org/x/tools/internal/event"
20         "golang.org/x/tools/internal/lsp/protocol"
21         "golang.org/x/tools/internal/lsp/source"
22         errors "golang.org/x/xerrors"
23 )
24
25 func (s *Server) semanticTokensFull(ctx context.Context, p *protocol.SemanticTokensParams) (*protocol.SemanticTokens, error) {
26         ret, err := s.computeSemanticTokens(ctx, p.TextDocument, nil)
27         return ret, err
28 }
29
30 func (s *Server) semanticTokensFullDelta(ctx context.Context, p *protocol.SemanticTokensDeltaParams) (interface{}, error) {
31         return nil, errors.Errorf("implement SemanticTokensFullDelta")
32 }
33
34 func (s *Server) semanticTokensRange(ctx context.Context, p *protocol.SemanticTokensRangeParams) (*protocol.SemanticTokens, error) {
35         ret, err := s.computeSemanticTokens(ctx, p.TextDocument, &p.Range)
36         return ret, err
37 }
38
39 func (s *Server) semanticTokensRefresh(ctx context.Context) error {
40         // in the code, but not in the protocol spec
41         return errors.Errorf("implement SemanticTokensRefresh")
42 }
43
44 func (s *Server) computeSemanticTokens(ctx context.Context, td protocol.TextDocumentIdentifier, rng *protocol.Range) (*protocol.SemanticTokens, error) {
45         ans := protocol.SemanticTokens{
46                 Data: []float64{},
47         }
48         snapshot, _, ok, release, err := s.beginFileRequest(ctx, td.URI, source.Go)
49         defer release()
50         if !ok {
51                 return nil, err
52         }
53         vv := snapshot.View()
54         if !vv.Options().SemanticTokens {
55                 // return an error, so if the option changes
56                 // the client won't remember the wrong answer
57                 return nil, errors.Errorf("semantictokens are disabled")
58         }
59         pkg, err := snapshot.PackageForFile(ctx, td.URI.SpanURI(), source.TypecheckFull, source.WidestPackage)
60         if err != nil {
61                 return nil, err
62         }
63         info := pkg.GetTypesInfo()
64         pgf, err := pkg.File(td.URI.SpanURI())
65         if err != nil {
66                 return nil, err
67         }
68         if pgf.ParseErr != nil {
69                 return nil, pgf.ParseErr
70         }
71         e := &encoded{
72                 ctx:  ctx,
73                 pgf:  pgf,
74                 rng:  rng,
75                 ti:   info,
76                 fset: snapshot.FileSet(),
77         }
78         if err := e.init(); err != nil {
79                 return nil, err
80         }
81         e.semantics()
82         ans.Data, err = e.Data()
83         if err != nil {
84                 // this is an internal error, likely caused by a typo
85                 // for a token or modifier
86                 return nil, err
87         }
88         // for small cache, some day. for now, the client ignores this
89         ans.ResultID = fmt.Sprintf("%v", time.Now())
90         return &ans, nil
91 }
92
93 func (e *encoded) semantics() {
94         f := e.pgf.File
95         e.token(f.Package, len("package"), tokKeyword, nil)
96         e.token(f.Name.NamePos, len(f.Name.Name), tokNamespace, nil)
97         inspect := func(n ast.Node) bool {
98                 return e.inspector(n)
99         }
100         for _, d := range f.Decls {
101                 // only look at the decls that overlap the range
102                 start, end := d.Pos(), d.End()
103                 if end <= e.start || start >= e.end {
104                         continue
105                 }
106                 ast.Inspect(d, inspect)
107         }
108 }
109
110 type tokenType string
111
112 const (
113         tokNamespace tokenType = "namespace"
114         tokType      tokenType = "type"
115         tokInterface tokenType = "interface"
116         tokParameter tokenType = "parameter"
117         tokVariable  tokenType = "variable"
118         tokMember    tokenType = "member"
119         tokFunction  tokenType = "function"
120         tokKeyword   tokenType = "keyword"
121         tokComment   tokenType = "comment"
122         tokString    tokenType = "string"
123         tokNumber    tokenType = "number"
124         tokOperator  tokenType = "operator"
125 )
126
127 var lastPosition token.Position
128
129 func (e *encoded) token(start token.Pos, leng int, typ tokenType, mods []string) {
130         if start == 0 {
131                 e.unexpected("token at token.NoPos")
132         }
133         if start >= e.end || start+token.Pos(leng) <= e.start {
134                 return
135         }
136         // want a line and column from start (in LSP coordinates)
137         // [//line directives should be ignored]
138         rng := source.NewMappedRange(e.fset, e.pgf.Mapper, start, start+token.Pos(leng))
139         lspRange, err := rng.Range()
140         if err != nil {
141                 // possibly a //line directive. TODO(pjw): fix this somehow
142                 // "column mapper is for file...instead of..."
143                 // "line is beyond end of file..."
144                 // see line 116 of internal/span/token.go which uses Position not PositionFor
145                 event.Error(e.ctx, "failed to convert to range", err)
146                 return
147         }
148         if lspRange.End.Line != lspRange.Start.Line {
149                 // abrupt end of file, without \n. TODO(pjw): fix?
150                 pos := e.fset.PositionFor(start, false)
151                 msg := fmt.Sprintf("token at %s:%d.%d overflows", pos.Filename, pos.Line, pos.Column)
152                 event.Log(e.ctx, msg)
153                 return
154         }
155         // token is all on one line
156         length := lspRange.End.Character - lspRange.Start.Character
157         e.add(lspRange.Start.Line, lspRange.Start.Character, length, typ, mods)
158 }
159
160 func (e *encoded) add(line, start float64, len float64, tok tokenType, mod []string) {
161         x := semItem{line, start, len, tok, mod}
162         e.items = append(e.items, x)
163 }
164
165 // semItem represents a token found walking the parse tree
166 type semItem struct {
167         line, start float64
168         len         float64
169         typeStr     tokenType
170         mods        []string
171 }
172
173 type encoded struct {
174         // the generated data
175         items []semItem
176
177         ctx  context.Context
178         pgf  *source.ParsedGoFile
179         rng  *protocol.Range
180         ti   *types.Info
181         fset *token.FileSet
182         // allowed starting and ending token.Pos, set by init
183         // used to avoid looking at declarations not in range
184         start, end token.Pos
185         // path from the root of the parse tree, used for debugging
186         stack []ast.Node
187 }
188
189 // convert the stack to a string, for debugging
190 func (e *encoded) strStack() string {
191         msg := []string{"["}
192         for _, s := range e.stack {
193                 msg = append(msg, fmt.Sprintf("%T", s)[5:])
194         }
195         if len(e.stack) > 0 {
196                 loc := e.stack[len(e.stack)-1].Pos()
197                 add := e.pgf.Tok.PositionFor(loc, false)
198                 msg = append(msg, fmt.Sprintf("(%d:%d)", add.Line, add.Column))
199         }
200         msg = append(msg, "]")
201         return strings.Join(msg, " ")
202 }
203
204 func (e *encoded) inspector(n ast.Node) bool {
205         pop := func() {
206                 e.stack = e.stack[:len(e.stack)-1]
207         }
208         if n == nil {
209                 pop()
210                 return true
211         }
212         e.stack = append(e.stack, n)
213         switch x := n.(type) {
214         case *ast.ArrayType:
215         case *ast.AssignStmt:
216                 e.token(x.TokPos, len(x.Tok.String()), tokOperator, nil)
217         case *ast.BasicLit:
218                 // if it extends across a line, skip it
219                 // better would be to mark each line as string TODO(pjw)
220                 if strings.Contains(x.Value, "\n") {
221                         break
222                 }
223                 ln := len(x.Value)
224                 what := tokNumber
225                 if x.Kind == token.STRING {
226                         what = tokString
227                         if _, ok := e.stack[len(e.stack)-2].(*ast.Field); ok {
228                                 // struct tags (this is probably pointless, as the
229                                 // TextMate grammar will treat all the other comments the same)
230                                 what = tokComment
231                         }
232                 }
233                 e.token(x.Pos(), ln, what, nil)
234         case *ast.BinaryExpr:
235                 e.token(x.OpPos, len(x.Op.String()), tokOperator, nil)
236         case *ast.BlockStmt:
237         case *ast.BranchStmt:
238                 e.token(x.TokPos, len(x.Tok.String()), tokKeyword, nil)
239                 // There's no semantic encoding for labels
240         case *ast.CallExpr:
241                 if x.Ellipsis != token.NoPos {
242                         e.token(x.Ellipsis, len("..."), tokOperator, nil)
243                 }
244         case *ast.CaseClause:
245                 iam := "case"
246                 if x.List == nil {
247                         iam = "default"
248                 }
249                 e.token(x.Case, len(iam), tokKeyword, nil)
250         case *ast.ChanType:
251                 // chan | chan <- | <- chan
252                 if x.Arrow == token.NoPos || x.Arrow != x.Begin {
253                         e.token(x.Begin, len("chan"), tokKeyword, nil)
254                         break
255                 }
256                 pos := e.findKeyword("chan", x.Begin+2, x.Value.Pos())
257                 e.token(pos, len("chan"), tokKeyword, nil)
258         case *ast.CommClause:
259                 iam := len("case")
260                 if x.Comm == nil {
261                         iam = len("default")
262                 }
263                 e.token(x.Case, iam, tokKeyword, nil)
264         case *ast.CompositeLit:
265         case *ast.DeclStmt:
266         case *ast.DeferStmt:
267                 e.token(x.Defer, len("defer"), tokKeyword, nil)
268         case *ast.Ellipsis:
269                 e.token(x.Ellipsis, len("..."), tokOperator, nil)
270         case *ast.EmptyStmt:
271         case *ast.ExprStmt:
272         case *ast.Field:
273         case *ast.FieldList:
274         case *ast.ForStmt:
275                 e.token(x.For, len("for"), tokKeyword, nil)
276         case *ast.FuncDecl:
277         case *ast.FuncLit:
278         case *ast.FuncType:
279                 if x.Func != token.NoPos {
280                         e.token(x.Func, len("func"), tokKeyword, nil)
281                 }
282         case *ast.GenDecl:
283                 e.token(x.TokPos, len(x.Tok.String()), tokKeyword, nil)
284         case *ast.GoStmt:
285                 e.token(x.Go, len("go"), tokKeyword, nil)
286         case *ast.Ident:
287                 e.ident(x)
288         case *ast.IfStmt:
289                 e.token(x.If, len("if"), tokKeyword, nil)
290                 if x.Else != nil {
291                         // x.Body.End() or x.Body.End()+1, not that it matters
292                         pos := e.findKeyword("else", x.Body.End(), x.Else.Pos())
293                         e.token(pos, len("else"), tokKeyword, nil)
294                 }
295         case *ast.ImportSpec:
296                 e.importSpec(x)
297                 pop()
298                 return false
299         case *ast.IncDecStmt:
300                 e.token(x.TokPos, len(x.Tok.String()), tokOperator, nil)
301         case *ast.IndexExpr:
302         case *ast.InterfaceType:
303                 e.token(x.Interface, len("interface"), tokKeyword, nil)
304         case *ast.KeyValueExpr:
305         case *ast.LabeledStmt:
306         case *ast.MapType:
307                 e.token(x.Map, len("map"), tokKeyword, nil)
308         case *ast.ParenExpr:
309         case *ast.RangeStmt:
310                 e.token(x.For, len("for"), tokKeyword, nil)
311                 // x.TokPos == token.NoPos is legal (for range foo {})
312                 offset := x.TokPos
313                 if offset == token.NoPos {
314                         offset = x.For
315                 }
316                 pos := e.findKeyword("range", offset, x.X.Pos())
317                 e.token(pos, len("range"), tokKeyword, nil)
318         case *ast.ReturnStmt:
319                 e.token(x.Return, len("return"), tokKeyword, nil)
320         case *ast.SelectStmt:
321                 e.token(x.Select, len("select"), tokKeyword, nil)
322         case *ast.SelectorExpr:
323         case *ast.SendStmt:
324                 e.token(x.Arrow, len("<-"), tokOperator, nil)
325         case *ast.SliceExpr:
326         case *ast.StarExpr:
327                 e.token(x.Star, len("*"), tokOperator, nil)
328         case *ast.StructType:
329                 e.token(x.Struct, len("struct"), tokKeyword, nil)
330         case *ast.SwitchStmt:
331                 e.token(x.Switch, len("switch"), tokKeyword, nil)
332         case *ast.TypeAssertExpr:
333                 if x.Type == nil {
334                         pos := e.findKeyword("type", x.Lparen, x.Rparen)
335                         e.token(pos, len("type"), tokKeyword, nil)
336                 }
337         case *ast.TypeSpec:
338         case *ast.TypeSwitchStmt:
339                 e.token(x.Switch, len("switch"), tokKeyword, nil)
340         case *ast.UnaryExpr:
341                 e.token(x.OpPos, len(x.Op.String()), tokOperator, nil)
342         case *ast.ValueSpec:
343         // things we won't see
344         case *ast.BadDecl, *ast.BadExpr, *ast.BadStmt,
345                 *ast.File, *ast.Package:
346                 log.Printf("implement %T %s", x, e.pgf.Tok.PositionFor(x.Pos(), false))
347         // things we knowingly ignore
348         case *ast.Comment, *ast.CommentGroup:
349                 pop()
350                 return false
351         default: // just to be super safe.
352                 e.unexpected(fmt.Sprintf("failed to implement %T", x))
353         }
354         return true
355 }
356 func (e *encoded) ident(x *ast.Ident) {
357         def := e.ti.Defs[x]
358         if def != nil {
359                 what, mods := e.definitionFor(x)
360                 if what != "" {
361                         e.token(x.Pos(), len(x.String()), what, mods)
362                 }
363                 return
364         }
365         use := e.ti.Uses[x]
366         switch y := use.(type) {
367         case nil:
368                 e.token(x.NamePos, len(x.Name), tokVariable, []string{"definition"})
369         case *types.Builtin:
370                 e.token(x.NamePos, len(x.Name), tokFunction, []string{"defaultLibrary"})
371         case *types.Const:
372                 mods := []string{"readonly"}
373                 tt := y.Type()
374                 if ttx, ok := tt.(*types.Basic); ok {
375                         switch bi := ttx.Info(); {
376                         case bi&types.IsNumeric != 0:
377                                 me := tokVariable
378                                 if x.String() == "iota" {
379                                         me = tokKeyword
380                                         mods = []string{}
381                                 }
382                                 e.token(x.Pos(), len(x.String()), me, mods)
383                         case bi&types.IsString != 0:
384                                 e.token(x.Pos(), len(x.String()), tokString, mods)
385                         case bi&types.IsBoolean != 0:
386                                 e.token(x.Pos(), len(x.Name), tokKeyword, nil)
387                         case bi == 0:
388                                 e.token(x.Pos(), len(x.String()), tokVariable, mods)
389                         default:
390                                 msg := fmt.Sprintf("unexpected %x at %s", bi, e.pgf.Tok.PositionFor(x.Pos(), false))
391                                 e.unexpected(msg)
392                         }
393                         break
394                 }
395                 if ttx, ok := tt.(*types.Named); ok {
396                         if x.String() == "iota" {
397                                 e.unexpected(fmt.Sprintf("iota:%T", ttx))
398                         }
399                         if _, ok := ttx.Underlying().(*types.Basic); ok {
400                                 e.token(x.Pos(), len(x.String()), tokVariable, mods)
401                                 break
402                         }
403                         e.unexpected(fmt.Sprintf("%q/%T", x.String(), tt))
404                 }
405                 // can this happen? Don't think so
406                 e.unexpected(fmt.Sprintf("%s %T %#v", x.String(), tt, tt))
407         case *types.Func:
408                 e.token(x.Pos(), len(x.Name), tokFunction, nil)
409         case *types.Label:
410                 // nothing to map it to
411         case *types.Nil:
412                 // nil is a predeclared identifier
413                 e.token(x.Pos(), len("nil"), tokKeyword, []string{"readonly"})
414         case *types.PkgName:
415                 e.token(x.Pos(), len(x.Name), tokNamespace, nil)
416         case *types.TypeName:
417                 e.token(x.Pos(), len(x.String()), tokType, nil)
418         case *types.Var:
419                 e.token(x.Pos(), len(x.Name), tokVariable, nil)
420         default:
421                 // replace with panic after extensive testing
422                 if use == nil {
423                         msg := fmt.Sprintf("%#v/%#v %#v %#v", x, x.Obj, e.ti.Defs[x], e.ti.Uses[x])
424                         e.unexpected(msg)
425                 }
426                 if use.Type() != nil {
427                         e.unexpected(fmt.Sprintf("%s %T/%T,%#v", x.String(), use, use.Type(), use))
428                 } else {
429                         e.unexpected(fmt.Sprintf("%s %T", x.String(), use))
430                 }
431         }
432 }
433
434 func (e *encoded) definitionFor(x *ast.Ident) (tokenType, []string) {
435         mods := []string{"definition"}
436         for i := len(e.stack) - 1; i >= 0; i-- {
437                 s := e.stack[i]
438                 switch y := s.(type) {
439                 case *ast.AssignStmt, *ast.RangeStmt:
440                         if x.Name == "_" {
441                                 return "", nil // not really a variable
442                         }
443                         return "variable", mods
444                 case *ast.GenDecl:
445                         if y.Tok == token.CONST {
446                                 mods = append(mods, "readonly")
447                         }
448                         return tokVariable, mods
449                 case *ast.FuncDecl:
450                         // If x is immediately under a FuncDecl, it is a function or method
451                         if i == len(e.stack)-2 {
452                                 if y.Recv != nil {
453                                         return tokMember, mods
454                                 }
455                                 return tokFunction, mods
456                         }
457                         // if x < ... < FieldList < FuncDecl, this is the receiver, a variable
458                         if _, ok := e.stack[i+1].(*ast.FieldList); ok {
459                                 return tokVariable, nil
460                         }
461                         // if x < ... < FieldList < FuncType < FuncDecl, this is a param
462                         return tokParameter, mods
463                 case *ast.InterfaceType:
464                         return tokMember, mods
465                 case *ast.TypeSpec:
466                         return tokType, mods
467                 }
468         }
469         // panic after extensive testing
470         msg := fmt.Sprintf("failed to find the decl for %s", e.pgf.Tok.PositionFor(x.Pos(), false))
471         e.unexpected(msg)
472         return "", []string{""}
473 }
474
475 // findKeyword finds a keyword rather than guessing its location
476 func (e *encoded) findKeyword(keyword string, start, end token.Pos) token.Pos {
477         offset := int(start) - e.pgf.Tok.Base()
478         last := int(end) - e.pgf.Tok.Base()
479         buf := e.pgf.Src
480         idx := bytes.Index(buf[offset:last], []byte(keyword))
481         if idx != -1 {
482                 return start + token.Pos(idx)
483         }
484         // can't happen
485         e.unexpected(fmt.Sprintf("not found:%s %v", keyword, e.fset.PositionFor(start, false)))
486         return token.NoPos
487 }
488
489 func (e *encoded) init() error {
490         e.start = token.Pos(e.pgf.Tok.Base())
491         e.end = e.start + token.Pos(e.pgf.Tok.Size())
492         if e.rng == nil {
493                 return nil
494         }
495         span, err := e.pgf.Mapper.RangeSpan(*e.rng)
496         if err != nil {
497                 return errors.Errorf("range span error for %s", e.pgf.File.Name)
498         }
499         e.end = e.start + token.Pos(span.End().Offset())
500         e.start += token.Pos(span.Start().Offset())
501         return nil
502 }
503
504 func (e *encoded) Data() ([]float64, error) {
505         // binary operators, at least, will be out of order
506         sort.Slice(e.items, func(i, j int) bool {
507                 if e.items[i].line != e.items[j].line {
508                         return e.items[i].line < e.items[j].line
509                 }
510                 return e.items[i].start < e.items[j].start
511         })
512         // each semantic token needs five values
513         // (see Integer Encoding for Tokens in the LSP spec)
514         x := make([]float64, 5*len(e.items))
515         for i := 0; i < len(e.items); i++ {
516                 j := 5 * i
517                 if i == 0 {
518                         x[0] = e.items[0].line
519                 } else {
520                         x[j] = e.items[i].line - e.items[i-1].line
521                 }
522                 x[j+1] = e.items[i].start
523                 if i > 0 && e.items[i].line == e.items[i-1].line {
524                         x[j+1] = e.items[i].start - e.items[i-1].start
525                 }
526                 x[j+2] = e.items[i].len
527                 x[j+3] = float64(SemanticMemo.TypeMap[e.items[i].typeStr])
528                 mask := 0
529                 for _, s := range e.items[i].mods {
530                         mask |= SemanticMemo.ModMap[s]
531                 }
532                 x[j+4] = float64(mask)
533         }
534         return x, nil
535 }
536
537 func (e *encoded) importSpec(d *ast.ImportSpec) {
538         // a local package name or the last component of the Path
539         if d.Name != nil {
540                 nm := d.Name.String()
541                 // import . x => x is not a namespace
542                 // import _ x => x is a namespace
543                 if nm != "_" && nm != "." {
544                         e.token(d.Name.Pos(), len(nm), tokNamespace, nil)
545                         return
546                 }
547                 if nm == "." {
548                         return
549                 }
550                 // and fall through for _
551         }
552         nm := d.Path.Value[1 : len(d.Path.Value)-1] // trailing "
553         v := strings.LastIndex(nm, "/")
554         if v != -1 {
555                 nm = nm[v+1:]
556         }
557         start := d.Path.End() - token.Pos(1+len(nm))
558         e.token(start, len(nm), tokNamespace, nil)
559 }
560
561 // panic on unexpected state
562 func (e *encoded) unexpected(msg string) {
563         log.Print(msg)
564         log.Print(e.strStack())
565         panic(msg)
566 }
567
568 // SemMemo supports semantic token translations between numbers and strings
569 type SemMemo struct {
570         tokTypes, tokMods []string
571         // these exported fields are used in the 'gopls semtok' command
572         TypeMap map[tokenType]int
573         ModMap  map[string]int
574 }
575
576 var SemanticMemo *SemMemo
577
578 // Type returns a string equivalent of the type, for gopls semtok
579 func (m *SemMemo) Type(n int) string {
580         if n >= 0 && n < len(m.tokTypes) {
581                 return m.tokTypes[n]
582         }
583         return fmt.Sprintf("?%d[%d,%d]?", n, len(m.tokTypes), len(m.tokMods))
584 }
585
586 // Mods returns the []string equivalent of the mods, for gopls semtok.
587 func (m *SemMemo) Mods(n int) []string {
588         mods := []string{}
589         for i := 0; i < len(m.tokMods); i++ {
590                 if (n & (1 << uint(i))) != 0 {
591                         mods = append(mods, m.tokMods[i])
592                 }
593         }
594         return mods
595 }
596
597 // save what the client sent
598 func rememberToks(toks []string, mods []string) {
599         SemanticMemo = &SemMemo{
600                 tokTypes: toks,
601                 tokMods:  mods,
602                 TypeMap:  make(map[tokenType]int),
603                 ModMap:   make(map[string]int),
604         }
605         for i, t := range toks {
606                 SemanticMemo.TypeMap[tokenType(t)] = i
607         }
608         for i, m := range mods {
609                 SemanticMemo.ModMap[m] = 1 << uint(i)
610         }
611         // we could have pruned or rearranged them.
612         // But then change the list in cmd.go too
613 }
614
615 // SemanticTypes to use in case there is no client, as in the command line, or tests
616 func SemanticTypes() []string {
617         return semanticTypes[:]
618 }
619
620 // SemanticModifiers to use in case there is no client.
621 func SemanticModifiers() []string {
622         return semanticModifiers[:]
623 }
624
625 var (
626         semanticTypes = [...]string{
627                 "namespace", "type", "class", "enum", "interface",
628                 "struct", "typeParameter", "parameter", "variable", "property", "enumMember",
629                 "event", "function", "member", "macro", "keyword", "modifier", "comment",
630                 "string", "number", "regexp", "operator"}
631         semanticModifiers = [...]string{
632                 "declaration", "definition", "readonly", "static",
633                 "deprecated", "abstract", "async", "modification", "documentation", "defaultLibrary"}
634 )