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.
14 // MaxDeepCompletions limits deep completion results because in most cases
15 // there are too many to be useful.
16 const MaxDeepCompletions = 3
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.
25 // queueClosed is used to disable adding new sub-fields to search queue
26 // once we're running out of our time budget.
29 // searchQueue holds the current breadth first search queue.
30 searchQueue []candidate
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
36 // candidateCount is the count of unique deep candidates encountered
41 // enqueue adds a candidate to the search queue.
42 func (s *deepCompletionState) enqueue(cand candidate) {
43 s.searchQueue = append(s.searchQueue, cand)
46 // dequeue removes and returns the leftmost element from the search queue.
47 func (s *deepCompletionState) dequeue() *candidate {
49 cand, s.searchQueue = &s.searchQueue[0], s.searchQueue[1:]
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
57 func (s *deepCompletionState) scorePenalty(cand *candidate) float64 {
58 var deepPenalty float64
59 for _, dc := range cand.path {
66 if _, isSig := dc.Type().Underlying().(*types.Signature); isSig {
71 // Normalize penalty to a max depth of 10.
72 return deepPenalty / 10
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.
82 // If we beat an existing score then take its spot.
83 for i, deepScore := range s.highScores {
84 if score <= deepScore {
88 if deepScore != 0 && i != len(s.highScores)-1 {
89 // If this wasn't an empty slot then we need to scooch everyone
91 copy(s.highScores[i+1:], s.highScores[i:])
93 s.highScores[i] = score
100 // newPath returns path from search root for an object following a given
102 func (s *deepCompletionState) newPath(cand *candidate, obj types.Object, invoke bool) ([]types.Object, []string) {
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...)
112 return append(path, obj), append(names, name)
115 // deepSearch searches a candidate and its subordinate objects for completion
116 // items if deep completion is enabled and adds the valid candidates to
118 func (c *completer) deepSearch(ctx context.Context) {
120 for len(c.deepState.searchQueue) > 0 {
121 cand := c.deepState.dequeue()
124 // At the top level, dedupe by object.
125 if len(cand.path) == 0 {
126 if c.seen[cand.obj] {
129 c.seen[cand.obj] = true
132 // If obj is not accessible because it lives in another package and is
133 // not exported, don't treat it as a completion candidate unless it's
134 // a package completion candidate.
135 if !c.completionContext.packageCompletion &&
136 obj.Pkg() != nil && obj.Pkg() != c.pkg.GetTypes() && !obj.Exported() {
140 // If we want a type name, don't offer non-type name candidates.
141 // However, do offer package names since they can contain type names,
142 // and do offer any candidate without a type since we aren't sure if it
143 // is a type name or not (i.e. unimported candidate).
144 if c.wantTypeName() && obj.Type() != nil && !isTypeName(obj) && !isPkgName(obj) {
148 // When searching deep, make sure we don't have a cycle in our chain.
149 // We don't dedupe by object because we want to allow both "foo.Baz"
150 // and "bar.Baz" even though "Baz" is represented the same types.Object
152 for _, seenObj := range cand.path {
158 c.addCandidate(ctx, cand)
160 c.deepState.candidateCount++
161 if c.opts.budget > 0 && c.deepState.candidateCount%100 == 0 {
162 spent := float64(time.Since(c.startTime)) / float64(c.opts.budget)
167 // If we are almost out of budgeted time, no further elements
168 // should be added to the queue. This ensures remaining time is
169 // used for processing current queue.
170 if !c.deepState.queueClosed && spent >= 0.85 {
171 c.deepState.queueClosed = true
176 // if deep search is disabled, don't add any more candidates.
177 if !c.deepState.enabled || c.deepState.queueClosed {
181 // Searching members for a type name doesn't make sense.
185 if obj.Type() == nil {
189 // Don't search embedded fields because they were already included in their
191 if v, ok := obj.(*types.Var); ok && v.Embedded() {
195 if sig, ok := obj.Type().Underlying().(*types.Signature); ok {
196 // If obj is a function that takes no arguments and returns one
197 // value, keep searching across the function call.
198 if sig.Params().Len() == 0 && sig.Results().Len() == 1 {
199 path, names := c.deepState.newPath(cand, obj, true)
200 // The result of a function call is not addressable.
201 candidates := c.methodsAndFields(sig.Results().At(0).Type(), false, cand.imp)
202 for _, newCand := range candidates {
203 newCand.path, newCand.names = path, names
204 c.deepState.enqueue(newCand)
209 path, names := c.deepState.newPath(cand, obj, false)
210 switch obj := obj.(type) {
212 candidates := c.packageMembers(obj.Imported(), stdScore, cand.imp)
213 for _, newCand := range candidates {
214 newCand.path, newCand.names = path, names
215 c.deepState.enqueue(newCand)
218 candidates := c.methodsAndFields(obj.Type(), cand.addressable, cand.imp)
219 for _, newCand := range candidates {
220 newCand.path, newCand.names = path, names
221 c.deepState.enqueue(newCand)
227 // addCandidate adds a completion candidate to suggestions, without searching
228 // its members for more candidates.
229 func (c *completer) addCandidate(ctx context.Context, cand *candidate) {
231 if c.matchingCandidate(cand) {
232 cand.score *= highScore
234 if p := c.penalty(cand); p > 0 {
235 cand.score *= (1 - p)
237 } else if isTypeName(obj) {
238 // If obj is a *types.TypeName that didn't otherwise match, check
239 // if a literal object of this type makes a good candidate.
241 // We only care about named types (i.e. don't want builtin types).
242 if _, isNamed := obj.Type().(*types.Named); isNamed {
243 c.literal(ctx, obj.Type(), cand.imp)
247 // Lower score of method calls so we prefer fields and vars over calls.
248 if cand.expandFuncCall {
249 if sig, ok := obj.Type().Underlying().(*types.Signature); ok && sig.Recv() != nil {
254 // Prefer private objects over public ones.
255 if !obj.Exported() && obj.Parent() != types.Universe {
259 // Favor shallow matches by lowering score according to depth.
260 cand.score -= cand.score * c.deepState.scorePenalty(cand)
266 cand.name = strings.Join(append(cand.names, cand.obj.Name()), ".")
267 if item, err := c.item(ctx, *cand); err == nil {
268 c.items = append(c.items, item)
272 // penalty reports a score penalty for cand in the range (0, 1).
273 // For example, a candidate is penalized if it has already been used
274 // in another switch case statement.
275 func (c *completer) penalty(cand *candidate) float64 {
276 for _, p := range c.inference.penalized {
277 if c.objChainMatches(cand, p.objChain) {
285 // objChainMatches reports whether cand combined with the surrounding
286 // object prefix matches chain.
287 func (c *completer) objChainMatches(cand *candidate, chain []types.Object) bool {
288 // For example, when completing:
292 // If we are considering the deep candidate "bar.baz", cand is baz,
293 // objChain is [foo] and deepChain is [bar]. We would match the
294 // chain [foo, bar, baz].
295 if len(chain) != len(c.inference.objChain)+len(cand.path)+1 {
299 if chain[len(chain)-1] != cand.obj {
303 for i, o := range c.inference.objChain {
309 for i, o := range cand.path {
310 if chain[i+len(c.inference.objChain)] != o {