.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.1.0/internal/lsp/source/completion/deep_completion.go

   1 // Copyright 2019 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 completion
   6
   7 import (
   8         "context"
   9         "go/types"
  10         "strings"
  11         "time"
  12 )
  13
  14 // MaxDeepCompletions limits deep completion results because in most cases
  15 // there are too many to be useful.
  16 const MaxDeepCompletions = 3
  17
  18 // deepCompletionState stores our state as we search for deep completions.
  19 // "deep completion" refers to searching into objects' fields and methods to
  20 // find more completion candidates.
  21 type deepCompletionState struct {
  22         // enabled indicates wether deep completion is permitted.
  23         enabled bool
  24
  25         // queueClosed is used to disable adding new sub-fields to search queue
  26         // once we're running out of our time budget.
  27         queueClosed bool
  28
  29         // searchQueue holds the current breadth first search queue.
  30         searchQueue []candidate
  31
  32         // highScores tracks the highest deep candidate scores we have found
  33         // so far. This is used to avoid work for low scoring deep candidates.
  34         highScores [MaxDeepCompletions]float64
  35
  36         // candidateCount is the count of unique deep candidates encountered
  37         // so far.
  38         candidateCount int
  39 }
  40
  41 // enqueue adds a candidate to the search queue.
  42 func (s *deepCompletionState) enqueue(cand candidate) {
  43         s.searchQueue = append(s.searchQueue, cand)
  44 }
  45
  46 // dequeue removes and returns the leftmost element from the search queue.
  47 func (s *deepCompletionState) dequeue() *candidate {
  48         var cand *candidate
  49         cand, s.searchQueue = &s.searchQueue[0], s.searchQueue[1:]
  50         return cand
  51 }
  52
  53 // scorePenalty computes a deep candidate score penalty. A candidate is
  54 // penalized based on depth to favor shallower candidates. We also give a
  55 // slight bonus to unexported objects and a slight additional penalty to
  56 // function objects.
  57 func (s *deepCompletionState) scorePenalty(cand *candidate) float64 {
  58         var deepPenalty float64
  59         for _, dc := range cand.path {
  60                 deepPenalty++
  61
  62                 if !dc.Exported() {
  63                         deepPenalty -= 0.1
  64                 }
  65
  66                 if _, isSig := dc.Type().Underlying().(*types.Signature); isSig {
  67                         deepPenalty += 0.1
  68                 }
  69         }
  70
  71         // Normalize penalty to a max depth of 10.
  72         return deepPenalty / 10
  73 }
  74
  75 // isHighScore returns whether score is among the top MaxDeepCompletions deep
  76 // candidate scores encountered so far. If so, it adds score to highScores,
  77 // possibly displacing an existing high score.
  78 func (s *deepCompletionState) isHighScore(score float64) bool {
  79         // Invariant: s.highScores is sorted with highest score first. Unclaimed
  80         // positions are trailing zeros.
  81
  82         // If we beat an existing score then take its spot.
  83         for i, deepScore := range s.highScores {
  84                 if score <= deepScore {
  85                         continue
  86                 }
  87
  88                 if deepScore != 0 && i != len(s.highScores)-1 {
  89                         // If this wasn't an empty slot then we need to scooch everyone
  90                         // down one spot.
  91                         copy(s.highScores[i+1:], s.highScores[i:])
  92                 }
  93                 s.highScores[i] = score
  94                 return true
  95         }
  96
  97         return false
  98 }
  99
 100 // newPath returns path from search root for an object following a given
 101 // candidate.
 102 func (s *deepCompletionState) newPath(cand *candidate, obj types.Object, invoke bool) ([]types.Object, []string) {
 103         name := obj.Name()
 104         if invoke {
 105                 name += "()"
 106         }
 107
 108         // copy the slice since we don't want to overwrite the original slice.
 109         path := append([]types.Object{}, cand.path...)
 110         names := append([]string{}, cand.names...)
 111
 112         return append(path, obj), append(names, name)
 113 }
 114
 115 // deepSearch searches a candidate and its subordinate objects for completion
 116 // items if deep completion is enabled and adds the valid candidates to
 117 // completion items.
 118 func (c *completer) deepSearch(ctx context.Context) {
 119 outer:
 120         for len(c.deepState.searchQueue) > 0 {
 121                 cand := c.deepState.dequeue()
 122                 obj := cand.obj
 123
 124                 if obj == nil {
 125                         continue
 126                 }
 127
 128                 // At the top level, dedupe by object.
 129                 if len(cand.path) == 0 {
 130                         if c.seen[obj] {
 131                                 continue
 132                         }
 133                         c.seen[obj] = true
 134                 }
 135
 136                 // If obj is not accessible because it lives in another package and is
 137                 // not exported, don't treat it as a completion candidate unless it's
 138                 // a package completion candidate.
 139                 if !c.completionContext.packageCompletion &&
 140                         obj.Pkg() != nil && obj.Pkg() != c.pkg.GetTypes() && !obj.Exported() {
 141                         continue
 142                 }
 143
 144                 // If we want a type name, don't offer non-type name candidates.
 145                 // However, do offer package names since they can contain type names,
 146                 // and do offer any candidate without a type since we aren't sure if it
 147                 // is a type name or not (i.e. unimported candidate).
 148                 if c.wantTypeName() && obj.Type() != nil && !isTypeName(obj) && !isPkgName(obj) {
 149                         continue
 150                 }
 151
 152                 // When searching deep, make sure we don't have a cycle in our chain.
 153                 // We don't dedupe by object because we want to allow both "foo.Baz"
 154                 // and "bar.Baz" even though "Baz" is represented the same types.Object
 155                 // in both.
 156                 for _, seenObj := range cand.path {
 157                         if seenObj == obj {
 158                                 continue outer
 159                         }
 160                 }
 161
 162                 c.addCandidate(ctx, cand)
 163
 164                 c.deepState.candidateCount++
 165                 if c.opts.budget > 0 && c.deepState.candidateCount%100 == 0 {
 166                         spent := float64(time.Since(c.startTime)) / float64(c.opts.budget)
 167                         select {
 168                         case <-ctx.Done():
 169                                 return
 170                         default:
 171                                 // If we are almost out of budgeted time, no further elements
 172                                 // should be added to the queue. This ensures remaining time is
 173                                 // used for processing current queue.
 174                                 if !c.deepState.queueClosed && spent >= 0.85 {
 175                                         c.deepState.queueClosed = true
 176                                 }
 177                         }
 178                 }
 179
 180                 // if deep search is disabled, don't add any more candidates.
 181                 if !c.deepState.enabled || c.deepState.queueClosed {
 182                         continue
 183                 }
 184
 185                 // Searching members for a type name doesn't make sense.
 186                 if isTypeName(obj) {
 187                         continue
 188                 }
 189                 if obj.Type() == nil {
 190                         continue
 191                 }
 192
 193                 // Don't search embedded fields because they were already included in their
 194                 // parent's fields.
 195                 if v, ok := obj.(*types.Var); ok && v.Embedded() {
 196                         continue
 197                 }
 198
 199                 if sig, ok := obj.Type().Underlying().(*types.Signature); ok {
 200                         // If obj is a function that takes no arguments and returns one
 201                         // value, keep searching across the function call.
 202                         if sig.Params().Len() == 0 && sig.Results().Len() == 1 {
 203                                 path, names := c.deepState.newPath(cand, obj, true)
 204                                 // The result of a function call is not addressable.
 205                                 candidates := c.methodsAndFields(sig.Results().At(0).Type(), false, cand.imp)
 206                                 for _, newCand := range candidates {
 207                                         newCand.path, newCand.names = path, names
 208                                         c.deepState.enqueue(newCand)
 209                                 }
 210                         }
 211                 }
 212
 213                 path, names := c.deepState.newPath(cand, obj, false)
 214                 switch obj := obj.(type) {
 215                 case *types.PkgName:
 216                         candidates := c.packageMembers(obj.Imported(), stdScore, cand.imp)
 217                         for _, newCand := range candidates {
 218                                 newCand.path, newCand.names = path, names
 219                                 c.deepState.enqueue(newCand)
 220                         }
 221                 default:
 222                         candidates := c.methodsAndFields(obj.Type(), cand.addressable, cand.imp)
 223                         for _, newCand := range candidates {
 224                                 newCand.path, newCand.names = path, names
 225                                 c.deepState.enqueue(newCand)
 226                         }
 227                 }
 228         }
 229 }
 230
 231 // addCandidate adds a completion candidate to suggestions, without searching
 232 // its members for more candidates.
 233 func (c *completer) addCandidate(ctx context.Context, cand *candidate) {
 234         obj := cand.obj
 235         if c.matchingCandidate(cand) {
 236                 cand.score *= highScore
 237
 238                 if p := c.penalty(cand); p > 0 {
 239                         cand.score *= (1 - p)
 240                 }
 241         } else if isTypeName(obj) {
 242                 // If obj is a *types.TypeName that didn't otherwise match, check
 243                 // if a literal object of this type makes a good candidate.
 244
 245                 // We only care about named types (i.e. don't want builtin types).
 246                 if _, isNamed := obj.Type().(*types.Named); isNamed {
 247                         c.literal(ctx, obj.Type(), cand.imp)
 248                 }
 249         }
 250
 251         // Lower score of method calls so we prefer fields and vars over calls.
 252         if cand.expandFuncCall {
 253                 if sig, ok := obj.Type().Underlying().(*types.Signature); ok && sig.Recv() != nil {
 254                         cand.score *= 0.9
 255                 }
 256         }
 257
 258         // Prefer private objects over public ones.
 259         if !obj.Exported() && obj.Parent() != types.Universe {
 260                 cand.score *= 1.1
 261         }
 262
 263         // Favor shallow matches by lowering score according to depth.
 264         cand.score -= cand.score * c.deepState.scorePenalty(cand)
 265
 266         if cand.score < 0 {
 267                 cand.score = 0
 268         }
 269
 270         cand.name = strings.Join(append(cand.names, cand.obj.Name()), ".")
 271         if item, err := c.item(ctx, *cand); err == nil {
 272                 c.items = append(c.items, item)
 273         }
 274 }
 275
 276 // penalty reports a score penalty for cand in the range (0, 1).
 277 // For example, a candidate is penalized if it has already been used
 278 // in another switch case statement.
 279 func (c *completer) penalty(cand *candidate) float64 {
 280         for _, p := range c.inference.penalized {
 281                 if c.objChainMatches(cand, p.objChain) {
 282                         return p.penalty
 283                 }
 284         }
 285
 286         return 0
 287 }
 288
 289 // objChainMatches reports whether cand combined with the surrounding
 290 // object prefix matches chain.
 291 func (c *completer) objChainMatches(cand *candidate, chain []types.Object) bool {
 292         // For example, when completing:
 293         //
 294         //   foo.ba<>
 295         //
 296         // If we are considering the deep candidate "bar.baz", cand is baz,
 297         // objChain is [foo] and deepChain is [bar]. We would match the
 298         // chain [foo, bar, baz].
 299         if len(chain) != len(c.inference.objChain)+len(cand.path)+1 {
 300                 return false
 301         }
 302
 303         if chain[len(chain)-1] != cand.obj {
 304                 return false
 305         }
 306
 307         for i, o := range c.inference.objChain {
 308                 if chain[i] != o {
 309                         return false
 310                 }
 311         }
 312
 313         for i, o := range cand.path {
 314                 if chain[i+len(c.inference.objChain)] != o {
 315                         return false
 316                 }
 317         }
 318
 319         return true
 320 }