.gitignore added
[dotfiles/.git] / .config / coc / extensions / coc-go-data / tools / pkg / mod / golang.org / x / tools@v0.1.0 / internal / lsp / source / workspace_symbol.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 source
6
7 import (
8         "context"
9         "fmt"
10         "go/ast"
11         "go/token"
12         "go/types"
13         "sort"
14         "strings"
15         "unicode"
16         "unicode/utf8"
17
18         "golang.org/x/tools/internal/event"
19         "golang.org/x/tools/internal/lsp/fuzzy"
20         "golang.org/x/tools/internal/lsp/protocol"
21         "golang.org/x/tools/internal/span"
22 )
23
24 // maxSymbols defines the maximum number of symbol results that should ever be
25 // sent in response to a client.
26 const maxSymbols = 100
27
28 // WorkspaceSymbols matches symbols across all views using the given query,
29 // according to the match semantics parameterized by matcherType and style.
30 //
31 // The workspace symbol method is defined in the spec as follows:
32 //
33 //   The workspace symbol request is sent from the client to the server to
34 //   list project-wide symbols matching the query string.
35 //
36 // It is unclear what "project-wide" means here, but given the parameters of
37 // workspace/symbol do not include any workspace identifier, then it has to be
38 // assumed that "project-wide" means "across all workspaces".  Hence why
39 // WorkspaceSymbols receives the views []View.
40 //
41 // However, it then becomes unclear what it would mean to call WorkspaceSymbols
42 // with a different configured SymbolMatcher per View. Therefore we assume that
43 // Session level configuration will define the SymbolMatcher to be used for the
44 // WorkspaceSymbols method.
45 func WorkspaceSymbols(ctx context.Context, matcherType SymbolMatcher, style SymbolStyle, views []View, query string) ([]protocol.SymbolInformation, error) {
46         ctx, done := event.Start(ctx, "source.WorkspaceSymbols")
47         defer done()
48         if query == "" {
49                 return nil, nil
50         }
51         sc := newSymbolCollector(matcherType, style, query)
52         return sc.walk(ctx, views)
53 }
54
55 // A matcherFunc determines the matching score of a symbol.
56 //
57 // See the comment for symbolCollector for more information.
58 type matcherFunc func(name string) float64
59
60 // A symbolizer returns the best symbol match for name with pkg, according to
61 // some heuristic.
62 //
63 // See the comment for symbolCollector for more information.
64 type symbolizer func(name string, pkg Package, m matcherFunc) (string, float64)
65
66 func fullyQualifiedSymbolMatch(name string, pkg Package, matcher matcherFunc) (string, float64) {
67         _, score := dynamicSymbolMatch(name, pkg, matcher)
68         if score > 0 {
69                 return pkg.PkgPath() + "." + name, score
70         }
71         return "", 0
72 }
73
74 func dynamicSymbolMatch(name string, pkg Package, matcher matcherFunc) (string, float64) {
75         // Prefer any package-qualified match.
76         pkgQualified := pkg.Name() + "." + name
77         if match, score := bestMatch(pkgQualified, matcher); match != "" {
78                 return match, score
79         }
80         fullyQualified := pkg.PkgPath() + "." + name
81         if match, score := bestMatch(fullyQualified, matcher); match != "" {
82                 return match, score
83         }
84         return "", 0
85 }
86
87 func packageSymbolMatch(name string, pkg Package, matcher matcherFunc) (string, float64) {
88         qualified := pkg.Name() + "." + name
89         if matcher(qualified) > 0 {
90                 return qualified, 1
91         }
92         return "", 0
93 }
94
95 // bestMatch returns the highest scoring symbol suffix of fullPath, starting
96 // from the right and splitting on selectors and path components.
97 //
98 // e.g. given a symbol path of the form 'host.com/dir/pkg.type.field', we
99 // check the match quality of the following:
100 //  - field
101 //  - type.field
102 //  - pkg.type.field
103 //  - dir/pkg.type.field
104 //  - host.com/dir/pkg.type.field
105 //
106 // and return the best match, along with its score.
107 //
108 // This is used to implement the 'dynamic' symbol style.
109 func bestMatch(fullPath string, matcher matcherFunc) (string, float64) {
110         pathParts := strings.Split(fullPath, "/")
111         dottedParts := strings.Split(pathParts[len(pathParts)-1], ".")
112
113         var best string
114         var score float64
115
116         for i := 0; i < len(dottedParts); i++ {
117                 path := strings.Join(dottedParts[len(dottedParts)-1-i:], ".")
118                 if match := matcher(path); match > score {
119                         best = path
120                         score = match
121                 }
122         }
123         for i := 0; i < len(pathParts); i++ {
124                 path := strings.Join(pathParts[len(pathParts)-1-i:], "/")
125                 if match := matcher(path); match > score {
126                         best = path
127                         score = match
128                 }
129         }
130         return best, score
131 }
132
133 // symbolCollector holds context as we walk Packages, gathering symbols that
134 // match a given query.
135 //
136 // How we match symbols is parameterized by two interfaces:
137 //  * A matcherFunc determines how well a string symbol matches a query. It
138 //    returns a non-negative score indicating the quality of the match. A score
139 //    of zero indicates no match.
140 //  * A symbolizer determines how we extract the symbol for an object. This
141 //    enables the 'symbolStyle' configuration option.
142 type symbolCollector struct {
143         // These types parameterize the symbol-matching pass.
144         matcher    matcherFunc
145         symbolizer symbolizer
146
147         // current holds metadata for the package we are currently walking.
148         current *pkgView
149         curFile *ParsedGoFile
150
151         res [maxSymbols]symbolInformation
152 }
153
154 func newSymbolCollector(matcher SymbolMatcher, style SymbolStyle, query string) *symbolCollector {
155         var m matcherFunc
156         switch matcher {
157         case SymbolFuzzy:
158                 m = parseQuery(query)
159         case SymbolCaseSensitive:
160                 m = func(s string) float64 {
161                         if strings.Contains(s, query) {
162                                 return 1
163                         }
164                         return 0
165                 }
166         case SymbolCaseInsensitive:
167                 q := strings.ToLower(query)
168                 m = func(s string) float64 {
169                         if strings.Contains(strings.ToLower(s), q) {
170                                 return 1
171                         }
172                         return 0
173                 }
174         default:
175                 panic(fmt.Errorf("unknown symbol matcher: %v", matcher))
176         }
177         var s symbolizer
178         switch style {
179         case DynamicSymbols:
180                 s = dynamicSymbolMatch
181         case FullyQualifiedSymbols:
182                 s = fullyQualifiedSymbolMatch
183         case PackageQualifiedSymbols:
184                 s = packageSymbolMatch
185         default:
186                 panic(fmt.Errorf("unknown symbol style: %v", style))
187         }
188         return &symbolCollector{
189                 matcher:    m,
190                 symbolizer: s,
191         }
192 }
193
194 // parseQuery parses a field-separated symbol query, extracting the special
195 // characters listed below, and returns a matcherFunc corresponding to the AND
196 // of all field queries.
197 //
198 // Special characters:
199 //   ^  match exact prefix
200 //   $  match exact suffix
201 //   '  match exact
202 //
203 // In all three of these special queries, matches are 'smart-cased', meaning
204 // they are case sensitive if the symbol query contains any upper-case
205 // characters, and case insensitive otherwise.
206 func parseQuery(q string) matcherFunc {
207         fields := strings.Fields(q)
208         if len(fields) == 0 {
209                 return func(string) float64 { return 0 }
210         }
211         var funcs []matcherFunc
212         for _, field := range fields {
213                 var f matcherFunc
214                 switch {
215                 case strings.HasPrefix(field, "^"):
216                         prefix := field[1:]
217                         f = smartCase(prefix, func(s string) float64 {
218                                 if strings.HasPrefix(s, prefix) {
219                                         return 1
220                                 }
221                                 return 0
222                         })
223                 case strings.HasPrefix(field, "'"):
224                         exact := field[1:]
225                         f = smartCase(exact, func(s string) float64 {
226                                 if strings.Contains(s, exact) {
227                                         return 1
228                                 }
229                                 return 0
230                         })
231                 case strings.HasSuffix(field, "$"):
232                         suffix := field[0 : len(field)-1]
233                         f = smartCase(suffix, func(s string) float64 {
234                                 if strings.HasSuffix(s, suffix) {
235                                         return 1
236                                 }
237                                 return 0
238                         })
239                 default:
240                         fm := fuzzy.NewMatcher(field)
241                         f = func(s string) float64 {
242                                 return float64(fm.Score(s))
243                         }
244                 }
245                 funcs = append(funcs, f)
246         }
247         return comboMatcher(funcs).match
248 }
249
250 // smartCase returns a matcherFunc that is case-sensitive if q contains any
251 // upper-case characters, and case-insensitive otherwise.
252 func smartCase(q string, m matcherFunc) matcherFunc {
253         insensitive := strings.ToLower(q) == q
254         return func(s string) float64 {
255                 if insensitive {
256                         s = strings.ToLower(s)
257                 }
258                 return m(s)
259         }
260 }
261
262 type comboMatcher []matcherFunc
263
264 func (c comboMatcher) match(s string) float64 {
265         score := 1.0
266         for _, f := range c {
267                 score *= f(s)
268         }
269         return score
270 }
271
272 // walk walks views, gathers symbols, and returns the results.
273 func (sc *symbolCollector) walk(ctx context.Context, views []View) (_ []protocol.SymbolInformation, err error) {
274         toWalk, err := sc.collectPackages(ctx, views)
275         if err != nil {
276                 return nil, err
277         }
278         // Make sure we only walk files once (we might see them more than once due to
279         // build constraints).
280         seen := make(map[span.URI]bool)
281         for _, pv := range toWalk {
282                 sc.current = pv
283                 for _, pgf := range pv.pkg.CompiledGoFiles() {
284                         if seen[pgf.URI] {
285                                 continue
286                         }
287                         seen[pgf.URI] = true
288                         sc.curFile = pgf
289                         sc.walkFilesDecls(pgf.File.Decls)
290                 }
291         }
292         return sc.results(), nil
293 }
294
295 func (sc *symbolCollector) results() []protocol.SymbolInformation {
296         var res []protocol.SymbolInformation
297         for _, si := range sc.res {
298                 if si.score <= 0 {
299                         return res
300                 }
301                 res = append(res, si.asProtocolSymbolInformation())
302         }
303         return res
304 }
305
306 // collectPackages gathers all known packages and sorts for stability.
307 func (sc *symbolCollector) collectPackages(ctx context.Context, views []View) ([]*pkgView, error) {
308         var toWalk []*pkgView
309         for _, v := range views {
310                 snapshot, release := v.Snapshot(ctx)
311                 defer release()
312                 knownPkgs, err := snapshot.KnownPackages(ctx)
313                 if err != nil {
314                         return nil, err
315                 }
316                 workspacePackages, err := snapshot.WorkspacePackages(ctx)
317                 if err != nil {
318                         return nil, err
319                 }
320                 isWorkspacePkg := make(map[Package]bool)
321                 for _, wp := range workspacePackages {
322                         isWorkspacePkg[wp] = true
323                 }
324                 for _, pkg := range knownPkgs {
325                         toWalk = append(toWalk, &pkgView{
326                                 pkg:         pkg,
327                                 isWorkspace: isWorkspacePkg[pkg],
328                         })
329                 }
330         }
331         // Now sort for stability of results. We order by
332         // (pkgView.isWorkspace, pkgView.p.ID())
333         sort.Slice(toWalk, func(i, j int) bool {
334                 lhs := toWalk[i]
335                 rhs := toWalk[j]
336                 switch {
337                 case lhs.isWorkspace == rhs.isWorkspace:
338                         return lhs.pkg.ID() < rhs.pkg.ID()
339                 case lhs.isWorkspace:
340                         return true
341                 default:
342                         return false
343                 }
344         })
345         return toWalk, nil
346 }
347
348 func (sc *symbolCollector) walkFilesDecls(decls []ast.Decl) {
349         for _, decl := range decls {
350                 switch decl := decl.(type) {
351                 case *ast.FuncDecl:
352                         kind := protocol.Function
353                         var recv *ast.Ident
354                         if decl.Recv != nil {
355                                 kind = protocol.Method
356                                 switch typ := decl.Recv.List[0].Type.(type) {
357                                 case *ast.StarExpr:
358                                         recv = typ.X.(*ast.Ident)
359                                 case *ast.Ident:
360                                         recv = typ
361                                 }
362                         }
363                         if recv != nil {
364                                 sc.match(decl.Name.Name, kind, decl.Name, recv)
365                         } else {
366                                 sc.match(decl.Name.Name, kind, decl.Name)
367                         }
368                 case *ast.GenDecl:
369                         for _, spec := range decl.Specs {
370                                 switch spec := spec.(type) {
371                                 case *ast.TypeSpec:
372                                         sc.match(spec.Name.Name, typeToKind(sc.current.pkg.GetTypesInfo().TypeOf(spec.Type)), spec.Name)
373                                         sc.walkType(spec.Type, spec.Name)
374                                 case *ast.ValueSpec:
375                                         for _, name := range spec.Names {
376                                                 kind := protocol.Variable
377                                                 if decl.Tok == token.CONST {
378                                                         kind = protocol.Constant
379                                                 }
380                                                 sc.match(name.Name, kind, name)
381                                         }
382                                 }
383                         }
384                 }
385         }
386 }
387
388 // walkType processes symbols related to a type expression. path is path of
389 // nested type identifiers to the type expression.
390 func (sc *symbolCollector) walkType(typ ast.Expr, path ...*ast.Ident) {
391         switch st := typ.(type) {
392         case *ast.StructType:
393                 for _, field := range st.Fields.List {
394                         sc.walkField(field, protocol.Field, protocol.Field, path...)
395                 }
396         case *ast.InterfaceType:
397                 for _, field := range st.Methods.List {
398                         sc.walkField(field, protocol.Interface, protocol.Method, path...)
399                 }
400         }
401 }
402
403 // walkField processes symbols related to the struct field or interface method.
404 //
405 // unnamedKind and namedKind are the symbol kinds if the field is resp. unnamed
406 // or named. path is the path of nested identifiers containing the field.
407 func (sc *symbolCollector) walkField(field *ast.Field, unnamedKind, namedKind protocol.SymbolKind, path ...*ast.Ident) {
408         if len(field.Names) == 0 {
409                 sc.match(types.ExprString(field.Type), unnamedKind, field, path...)
410         }
411         for _, name := range field.Names {
412                 sc.match(name.Name, namedKind, name, path...)
413                 sc.walkType(field.Type, append(path, name)...)
414         }
415 }
416
417 func typeToKind(typ types.Type) protocol.SymbolKind {
418         switch typ := typ.Underlying().(type) {
419         case *types.Interface:
420                 return protocol.Interface
421         case *types.Struct:
422                 return protocol.Struct
423         case *types.Signature:
424                 if typ.Recv() != nil {
425                         return protocol.Method
426                 }
427                 return protocol.Function
428         case *types.Named:
429                 return typeToKind(typ.Underlying())
430         case *types.Basic:
431                 i := typ.Info()
432                 switch {
433                 case i&types.IsNumeric != 0:
434                         return protocol.Number
435                 case i&types.IsBoolean != 0:
436                         return protocol.Boolean
437                 case i&types.IsString != 0:
438                         return protocol.String
439                 }
440         }
441         return protocol.Variable
442 }
443
444 // match finds matches and gathers the symbol identified by name, kind and node
445 // via the symbolCollector's matcher after first de-duping against previously
446 // seen symbols.
447 //
448 // path specifies the identifier path to a nested field or interface method.
449 func (sc *symbolCollector) match(name string, kind protocol.SymbolKind, node ast.Node, path ...*ast.Ident) {
450         if !node.Pos().IsValid() || !node.End().IsValid() {
451                 return
452         }
453
454         isExported := isExported(name)
455         if len(path) > 0 {
456                 var nameBuilder strings.Builder
457                 for _, ident := range path {
458                         nameBuilder.WriteString(ident.Name)
459                         nameBuilder.WriteString(".")
460                         if !ident.IsExported() {
461                                 isExported = false
462                         }
463                 }
464                 nameBuilder.WriteString(name)
465                 name = nameBuilder.String()
466         }
467
468         // Factors to apply to the match score for the purpose of downranking
469         // results.
470         //
471         // These numbers were crudely calibrated based on trial-and-error using a
472         // small number of sample queries. Adjust as necessary.
473         //
474         // All factors are multiplicative, meaning if more than one applies they are
475         // multiplied together.
476         const (
477                 // nonWorkspaceFactor is applied to symbols outside of any active
478                 // workspace. Developers are less likely to want to jump to code that they
479                 // are not actively working on.
480                 nonWorkspaceFactor = 0.5
481                 // nonWorkspaceUnexportedFactor is applied to unexported symbols outside of
482                 // any active workspace. Since one wouldn't usually jump to unexported
483                 // symbols to understand a package API, they are particularly irrelevant.
484                 nonWorkspaceUnexportedFactor = 0.5
485                 // fieldFactor is applied to fields and interface methods. One would
486                 // typically jump to the type definition first, so ranking fields highly
487                 // can be noisy.
488                 fieldFactor = 0.5
489         )
490         symbol, score := sc.symbolizer(name, sc.current.pkg, sc.matcher)
491
492         // Downrank symbols outside of the workspace.
493         if !sc.current.isWorkspace {
494                 score *= nonWorkspaceFactor
495                 if !isExported {
496                         score *= nonWorkspaceUnexportedFactor
497                 }
498         }
499
500         // Downrank fields.
501         if len(path) > 0 {
502                 score *= fieldFactor
503         }
504
505         // Avoid the work below if we know this score will not be sorted into the
506         // results.
507         if score <= sc.res[len(sc.res)-1].score {
508                 return
509         }
510
511         rng, err := fileRange(sc.curFile, node.Pos(), node.End())
512         if err != nil {
513                 return
514         }
515         si := symbolInformation{
516                 score:     score,
517                 name:      name,
518                 symbol:    symbol,
519                 container: sc.current.pkg.PkgPath(),
520                 kind:      kind,
521                 location: protocol.Location{
522                         URI:   protocol.URIFromSpanURI(sc.curFile.URI),
523                         Range: rng,
524                 },
525         }
526         insertAt := sort.Search(len(sc.res), func(i int) bool {
527                 return sc.res[i].score < score
528         })
529         if insertAt < len(sc.res)-1 {
530                 copy(sc.res[insertAt+1:], sc.res[insertAt:len(sc.res)-1])
531         }
532         sc.res[insertAt] = si
533 }
534
535 func fileRange(pgf *ParsedGoFile, start, end token.Pos) (protocol.Range, error) {
536         s, err := span.FileSpan(pgf.Tok, pgf.Mapper.Converter, start, end)
537         if err != nil {
538                 return protocol.Range{}, nil
539         }
540         return pgf.Mapper.Range(s)
541 }
542
543 // isExported reports if a token is exported. Copied from
544 // token.IsExported (go1.13+).
545 //
546 // TODO: replace usage with token.IsExported once go1.12 is no longer
547 // supported.
548 func isExported(name string) bool {
549         ch, _ := utf8.DecodeRuneInString(name)
550         return unicode.IsUpper(ch)
551 }
552
553 // pkgView holds information related to a package that we are going to walk.
554 type pkgView struct {
555         pkg         Package
556         isWorkspace bool
557 }
558
559 // symbolInformation is a cut-down version of protocol.SymbolInformation that
560 // allows struct values of this type to be used as map keys.
561 type symbolInformation struct {
562         score     float64
563         name      string
564         symbol    string
565         container string
566         kind      protocol.SymbolKind
567         location  protocol.Location
568 }
569
570 // asProtocolSymbolInformation converts s to a protocol.SymbolInformation value.
571 //
572 // TODO: work out how to handle tags if/when they are needed.
573 func (s symbolInformation) asProtocolSymbolInformation() protocol.SymbolInformation {
574         return protocol.SymbolInformation{
575                 Name:          s.symbol,
576                 Kind:          s.kind,
577                 Location:      s.location,
578                 ContainerName: s.container,
579         }
580 }