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