internal/lsp/source/completion: convert deep completion to bfs
This change converts deep completion from depth first search to breadth
first search.
Change-Id: Iebc7ba8d3acb44928220596065d4e8de53ea9b48
Reviewed-on: https://go-review.googlesource.com/c/tools/+/254542
Run-TryBot: Danish Dua <danishdua@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Danish Dua <danishdua@google.com>
Reviewed-by: Heschi Kreinick <heschi@google.com>
diff --git a/internal/lsp/source/completion/completion.go b/internal/lsp/source/completion/completion.go
index fc34802..3bfa588 100644
--- a/internal/lsp/source/completion/completion.go
+++ b/internal/lsp/source/completion/completion.go
@@ -89,7 +89,6 @@
// completionOptions holds completion specific configuration.
type completionOptions struct {
- deepCompletion bool
unimported bool
documentation bool
fullDocumentation bool
@@ -318,114 +317,6 @@
return c.surrounding
}
-// found adds a candidate completion. We will also search through the object's
-// members for more candidates.
-func (c *completer) found(ctx context.Context, cand candidate) {
- obj := cand.obj
-
- if obj.Pkg() != nil && obj.Pkg() != c.pkg.GetTypes() && !obj.Exported() {
- // obj is not accessible because it lives in another package and is not
- // exported. Don't treat it as a completion candidate.
- return
- }
-
- if c.inDeepCompletion() {
- // When searching deep, just make sure we don't have a cycle in our chain.
- // We don't dedupe by object because we want to allow both "foo.Baz" and
- // "bar.Baz" even though "Baz" is represented the same types.Object in both.
- for _, seenObj := range c.deepState.chain {
- if seenObj == obj {
- return
- }
- }
- } else {
- // At the top level, dedupe by object.
- if c.seen[obj] {
- return
- }
- c.seen[obj] = true
- }
-
- // If we are running out of budgeted time we must limit our search for deep
- // completion candidates.
- if c.shouldPrune() {
- return
- }
-
- // If we know we want a type name, don't offer non-type name
- // candidates. However, do offer package names since they can
- // contain type names, and do offer any candidate without a type
- // since we aren't sure if it is a type name or not (i.e. unimported
- // candidate).
- if c.wantTypeName() && obj.Type() != nil && !isTypeName(obj) && !isPkgName(obj) {
- return
- }
-
- if c.matchingCandidate(&cand) {
- cand.score *= highScore
-
- if p := c.penalty(&cand); p > 0 {
- cand.score *= (1 - p)
- }
- } else if isTypeName(obj) {
- // If obj is a *types.TypeName that didn't otherwise match, check
- // if a literal object of this type makes a good candidate.
-
- // We only care about named types (i.e. don't want builtin types).
- if _, isNamed := obj.Type().(*types.Named); isNamed {
- c.literal(ctx, obj.Type(), cand.imp)
- }
- }
-
- // Lower score of method calls so we prefer fields and vars over calls.
- if cand.expandFuncCall {
- if sig, ok := obj.Type().Underlying().(*types.Signature); ok && sig.Recv() != nil {
- cand.score *= 0.9
- }
- }
-
- // Prefer private objects over public ones.
- if !obj.Exported() && obj.Parent() != types.Universe {
- cand.score *= 1.1
- }
-
- // Favor shallow matches by lowering score according to depth.
- cand.score -= cand.score * c.deepState.scorePenalty()
-
- if cand.score < 0 {
- cand.score = 0
- }
-
- cand.name = c.deepState.chainString(obj.Name())
- matchScore := c.matcher.Score(cand.name)
- if matchScore > 0 {
- cand.score *= float64(matchScore)
-
- // Avoid calling c.item() for deep candidates that wouldn't be in the top
- // MaxDeepCompletions anyway.
- if !c.inDeepCompletion() || c.deepState.isHighScore(cand.score) {
- if item, err := c.item(ctx, cand); err == nil {
- c.items = append(c.items, item)
- }
- }
- }
-
- c.deepSearch(ctx, cand)
-}
-
-// penalty reports a score penalty for cand in the range (0, 1).
-// For example, a candidate is penalized if it has already been used
-// in another switch case statement.
-func (c *completer) penalty(cand *candidate) float64 {
- for _, p := range c.inference.penalized {
- if c.objChainMatches(cand.obj, p.objChain) {
- return p.penalty
- }
- }
-
- return 0
-}
-
// candidate represents a completion candidate.
type candidate struct {
// obj is the types.Object to complete to.
@@ -486,7 +377,7 @@
// the client to score the quality of the completion. For instance, some clients
// may tolerate imperfect matches as valid completion results, since users may make typos.
func Completion(ctx context.Context, snapshot source.Snapshot, fh source.FileHandle, protoPos protocol.Position, triggerCharacter string) ([]CompletionItem, *Selection, error) {
- ctx, done := event.Start(ctx, "source.Completion")
+ ctx, done := event.Start(ctx, "completion.Completion")
defer done()
startTime := time.Now()
@@ -571,9 +462,12 @@
seen: make(map[types.Object]bool),
enclosingFunc: enclosingFunction(path, pkg.GetTypesInfo()),
enclosingCompositeLiteral: enclosingCompositeLiteral(path, rng.Start, pkg.GetTypesInfo()),
+ deepState: deepCompletionState{
+ enabled: opts.DeepCompletion,
+ curPath: &searchPath{},
+ },
opts: &completionOptions{
matcher: opts.Matcher,
- deepCompletion: opts.DeepCompletion,
unimported: opts.CompleteUnimported,
documentation: opts.CompletionDocumentation,
fullDocumentation: opts.HoverKind == source.FullDocumentation,
@@ -588,11 +482,6 @@
startTime: startTime,
}
- if c.opts.deepCompletion {
- // Initialize max search depth to unlimited.
- c.deepState.maxDepth = -1
- }
-
var cancel context.CancelFunc
if c.opts.budget == 0 {
ctx, cancel = context.WithCancel(ctx)
@@ -623,9 +512,9 @@
// Inside comments, offer completions for the name of the relevant symbol.
for _, comment := range pgf.File.Comments {
if comment.Pos() < rng.Start && rng.Start <= comment.End() {
- // deep completion doesn't work properly in comments since we don't
- // have a type object to complete further
- c.deepState.maxDepth = 0
+ // Deep completion doesn't work properly in comments since we don't
+ // have a type object to complete further.
+ c.deepState.enabled = false
c.populateCommentCompletions(ctx, comment)
return c.items, c.getSurrounding(), nil
}
@@ -633,6 +522,11 @@
// Struct literals are handled entirely separately.
if c.wantStructFieldCompletions() {
+ // If we are definitely completing a struct field name, deep completions
+ // don't make sense.
+ if c.enclosingCompositeLiteral.inKey {
+ c.deepState.enabled = false
+ }
if err := c.structLiteralFieldName(ctx); err != nil {
return nil, nil, err
}
@@ -1104,7 +998,10 @@
// Is sel a qualified identifier?
if id, ok := sel.X.(*ast.Ident); ok {
if pkgName, ok := c.pkg.GetTypesInfo().Uses[id].(*types.PkgName); ok {
- c.packageMembers(ctx, pkgName.Imported(), stdScore, nil)
+ candidates := c.packageMembers(ctx, pkgName.Imported(), stdScore, nil)
+ for _, cand := range candidates {
+ c.found(ctx, cand)
+ }
return nil
}
}
@@ -1112,7 +1009,11 @@
// Invariant: sel is a true selector.
tv, ok := c.pkg.GetTypesInfo().Types[sel.X]
if ok {
- return c.methodsAndFields(ctx, tv.Type, tv.Addressable(), nil)
+ candidates := c.methodsAndFields(ctx, tv.Type, tv.Addressable(), nil)
+ for _, cand := range candidates {
+ c.found(ctx, cand)
+ }
+ return nil
}
// Try unimported packages.
@@ -1165,7 +1066,10 @@
if imports.ImportPathToAssumedName(path) != pkg.GetTypes().Name() {
imp.name = pkg.GetTypes().Name()
}
- c.packageMembers(ctx, pkg.GetTypes(), unimportedScore(relevances[path]), imp)
+ candidates := c.packageMembers(ctx, pkg.GetTypes(), unimportedScore(relevances[path]), imp)
+ for _, cand := range candidates {
+ c.found(ctx, cand)
+ }
if len(c.items) >= unimportedMemberTarget {
return nil
}
@@ -1210,20 +1114,22 @@
return (stdScore + .1*float64(relevance)) / 2
}
-func (c *completer) packageMembers(ctx context.Context, pkg *types.Package, score float64, imp *importInfo) {
+func (c *completer) packageMembers(ctx context.Context, pkg *types.Package, score float64, imp *importInfo) []candidate {
+ var candidates []candidate
scope := pkg.Scope()
for _, name := range scope.Names() {
obj := scope.Lookup(name)
- c.found(ctx, candidate{
+ candidates = append(candidates, candidate{
obj: obj,
score: score,
imp: imp,
addressable: isVar(obj),
})
}
+ return candidates
}
-func (c *completer) methodsAndFields(ctx context.Context, typ types.Type, addressable bool, imp *importInfo) error {
+func (c *completer) methodsAndFields(ctx context.Context, typ types.Type, addressable bool, imp *importInfo) []candidate {
mset := c.methodSetCache[methodSetKey{typ, addressable}]
if mset == nil {
if addressable && !types.IsInterface(typ) && !isPointer(typ) {
@@ -1236,8 +1142,9 @@
c.methodSetCache[methodSetKey{typ, addressable}] = mset
}
+ var candidates []candidate
for i := 0; i < mset.Len(); i++ {
- c.found(ctx, candidate{
+ candidates = append(candidates, candidate{
obj: mset.At(i).Obj(),
score: stdScore,
imp: imp,
@@ -1247,7 +1154,7 @@
// Add fields of T.
eachField(typ, func(v *types.Var) {
- c.found(ctx, candidate{
+ candidates = append(candidates, candidate{
obj: v,
score: stdScore - 0.01,
imp: imp,
@@ -1255,7 +1162,7 @@
})
})
- return nil
+ return candidates
}
// lexical finds completions in the lexical environment.
@@ -2474,40 +2381,6 @@
return false
}
-// objChainMatches reports whether cand combined with the surrounding
-// object prefix matches chain.
-func (c *completer) objChainMatches(cand types.Object, chain []types.Object) bool {
- // For example, when completing:
- //
- // foo.ba<>
- //
- // If we are considering the deep candidate "bar.baz", cand is baz,
- // objChain is [foo] and deepChain is [bar]. We would match the
- // chain [foo, bar, baz].
-
- if len(chain) != len(c.inference.objChain)+len(c.deepState.chain)+1 {
- return false
- }
-
- if chain[len(chain)-1] != cand {
- return false
- }
-
- for i, o := range c.inference.objChain {
- if chain[i] != o {
- return false
- }
- }
-
- for i, o := range c.deepState.chain {
- if chain[i+len(c.inference.objChain)] != o {
- return false
- }
- }
-
- return true
-}
-
// candTypeMatches reports whether cand makes a good completion
// candidate given the candidate inference. cand's score may be
// mutated to downrank the candidate in certain situations.
diff --git a/internal/lsp/source/completion/completion_format.go b/internal/lsp/source/completion/completion_format.go
index 793f1ec..35d5f5a 100644
--- a/internal/lsp/source/completion/completion_format.go
+++ b/internal/lsp/source/completion/completion_format.go
@@ -160,7 +160,7 @@
Detail: detail,
Kind: kind,
Score: cand.score,
- Depth: len(c.deepState.chain),
+ Depth: len(c.deepState.curPath.path),
snippet: snip,
obj: obj,
}
diff --git a/internal/lsp/source/completion/completion_snippet.go b/internal/lsp/source/completion/completion_snippet.go
index c254c65..a88be01 100644
--- a/internal/lsp/source/completion/completion_snippet.go
+++ b/internal/lsp/source/completion/completion_snippet.go
@@ -19,7 +19,7 @@
// If we are in a deep completion then we can't be completing a field
// name (e.g. "Foo{f<>}" completing to "Foo{f.Bar}" should not generate
// a snippet).
- if c.inDeepCompletion() {
+ if c.deepState.inDeepCompletion() {
return nil
}
diff --git a/internal/lsp/source/completion/deep_completion.go b/internal/lsp/source/completion/deep_completion.go
index 3f06d13..c7754ac 100644
--- a/internal/lsp/source/completion/deep_completion.go
+++ b/internal/lsp/source/completion/deep_completion.go
@@ -11,6 +11,19 @@
"time"
)
+// searchItem represents a candidate in deep completion search queue.
+type searchItem struct {
+ *searchPath
+ cand candidate
+}
+
+// searchPath holds the path from search root (excluding the item itself) for
+// a searchItem.
+type searchPath struct {
+ path []types.Object
+ names []string
+}
+
// MaxDeepCompletions limits deep completion results because in most cases
// there are too many to be useful.
const MaxDeepCompletions = 3
@@ -19,17 +32,19 @@
// "deep completion" refers to searching into objects' fields and methods to
// find more completion candidates.
type deepCompletionState struct {
- // maxDepth limits the deep completion search depth. 0 means
- // disabled and -1 means unlimited.
- maxDepth int
+ // enabled indicates wether deep completion is permitted. It should be
+ // reset to original value if manually disabled for an individual case.
+ enabled bool
- // chain holds the traversal path as we do a depth-first search through
- // objects' members looking for exact type matches.
- chain []types.Object
+ // queueClosed is used to disable adding new items to search queue once
+ // we're running out of our time budget.
+ queueClosed bool
- // chainNames holds the names of the chain objects. This allows us to
- // save allocations as we build many deep completion items.
- chainNames []string
+ // searchQueue holds the current breadth first search queue.
+ searchQueue []searchItem
+
+ // curPath tracks the current deep completion search path.
+ curPath *searchPath
// highScores tracks the highest deep candidate scores we have found
// so far. This is used to avoid work for low scoring deep candidates.
@@ -40,35 +55,45 @@
candidateCount int
}
-// push pushes obj onto our search stack. If invoke is true then
-// invocation parens "()" will be appended to the object name.
-func (s *deepCompletionState) push(obj types.Object, invoke bool) {
- s.chain = append(s.chain, obj)
-
- name := obj.Name()
- if invoke {
- name += "()"
+// enqueue adds candidates to the search queue.
+func (s *deepCompletionState) enqueue(path *searchPath, candidates ...candidate) {
+ for _, cand := range candidates {
+ s.searchQueue = append(s.searchQueue, searchItem{path, cand})
}
- s.chainNames = append(s.chainNames, name)
}
-// pop pops the last object off our search stack.
-func (s *deepCompletionState) pop() {
- s.chain = s.chain[:len(s.chain)-1]
- s.chainNames = s.chainNames[:len(s.chainNames)-1]
+// dequeue removes and returns the leftmost element from the search queue.
+func (s *deepCompletionState) dequeue() *searchItem {
+ var item *searchItem
+ item, s.searchQueue = &s.searchQueue[0], s.searchQueue[1:]
+ return item
}
-// chainString joins the chain of objects' names together on ".".
-func (s *deepCompletionState) chainString(finalName string) string {
- s.chainNames = append(s.chainNames, finalName)
- chainStr := strings.Join(s.chainNames, ".")
- s.chainNames = s.chainNames[:len(s.chainNames)-1]
- return chainStr
+// scorePenalty computes a deep candidate score penalty. A candidate is
+// penalized based on depth to favor shallower candidates. We also give a
+// slight bonus to unexported objects and a slight additional penalty to
+// function objects.
+func (s *deepCompletionState) scorePenalty() float64 {
+ var deepPenalty float64
+ for _, dc := range s.curPath.path {
+ deepPenalty++
+
+ if !dc.Exported() {
+ deepPenalty -= 0.1
+ }
+
+ if _, isSig := dc.Type().Underlying().(*types.Signature); isSig {
+ deepPenalty += 0.1
+ }
+ }
+
+ // Normalize penalty to a max depth of 10.
+ return deepPenalty / 10
}
-// isHighScore returns whether score is among the top MaxDeepCompletions
-// deep candidate scores encountered so far. If so, it adds score to
-// highScores, possibly displacing an existing high score.
+// isHighScore returns whether score is among the top MaxDeepCompletions deep
+// candidate scores encountered so far. If so, it adds score to highScores,
+// possibly displacing an existing high score.
func (s *deepCompletionState) isHighScore(score float64) bool {
// Invariant: s.highScores is sorted with highest score first. Unclaimed
// positions are trailing zeros.
@@ -91,126 +116,240 @@
return false
}
-// scorePenalty computes a deep candidate score penalty. A candidate
-// is penalized based on depth to favor shallower candidates. We also
-// give a slight bonus to unexported objects and a slight additional
-// penalty to function objects.
-func (s *deepCompletionState) scorePenalty() float64 {
- var deepPenalty float64
- for _, dc := range s.chain {
- deepPenalty += 1
+// inDeepCompletion returns if we're currently searching an object's members.
+func (s *deepCompletionState) inDeepCompletion() bool {
+ return len(s.curPath.path) > 0
+}
- if !dc.Exported() {
- deepPenalty -= 0.1
+// reset resets deepCompletionState since found might be called multiple times.
+// We don't reset high scores since multiple calls to found still respect the
+// same MaxDeepCompletions count.
+func (s *deepCompletionState) reset() {
+ s.searchQueue = nil
+ s.curPath = &searchPath{}
+}
+
+// appendToSearchPath appends an object to a given searchPath.
+func appendToSearchPath(oldPath searchPath, obj types.Object, invoke bool) *searchPath {
+ name := obj.Name()
+ if invoke {
+ name += "()"
+ }
+
+ // copy the slice since we don't want to overwrite the original slice.
+ path := append([]types.Object{}, oldPath.path...)
+ names := append([]string{}, oldPath.names...)
+
+ return &searchPath{
+ path: append(path, obj),
+ names: append(names, name),
+ }
+}
+
+// found adds a candidate to completion items if it's a valid suggestion and
+// searches the candidate's subordinate objects for more completion items if
+// deep completion is enabled.
+func (c *completer) found(ctx context.Context, cand candidate) {
+ // reset state at the end so current state doesn't affect completions done
+ // outside c.found.
+ defer c.deepState.reset()
+
+ // At the top level, dedupe by object.
+ if c.seen[cand.obj] {
+ return
+ }
+ c.seen[cand.obj] = true
+
+ c.deepState.enqueue(&searchPath{}, cand)
+outer:
+ for len(c.deepState.searchQueue) > 0 {
+ item := c.deepState.dequeue()
+ curCand := item.cand
+ obj := curCand.obj
+
+ // If obj is not accessible because it lives in another package and is
+ // not exported, don't treat it as a completion candidate.
+ if obj.Pkg() != nil && obj.Pkg() != c.pkg.GetTypes() && !obj.Exported() {
+ continue
}
- if _, isSig := dc.Type().Underlying().(*types.Signature); isSig {
- deepPenalty += 0.1
+ // If we want a type name, don't offer non-type name candidates.
+ // However, do offer package names since they can contain type names,
+ // and do offer any candidate without a type since we aren't sure if it
+ // is a type name or not (i.e. unimported candidate).
+ if c.wantTypeName() && obj.Type() != nil && !isTypeName(obj) && !isPkgName(obj) {
+ continue
+ }
+
+ // When searching deep, make sure we don't have a cycle in our chain.
+ // We don't dedupe by object because we want to allow both "foo.Baz"
+ // and "bar.Baz" even though "Baz" is represented the same types.Object
+ // in both.
+ for _, seenObj := range item.path {
+ if seenObj == obj {
+ continue outer
+ }
+ }
+
+ // update tracked current path since other functions might check it.
+ c.deepState.curPath = item.searchPath
+
+ c.addCandidate(ctx, curCand)
+
+ c.deepState.candidateCount++
+ if c.opts.budget > 0 && c.deepState.candidateCount%100 == 0 {
+ spent := float64(time.Since(c.startTime)) / float64(c.opts.budget)
+ if spent > 1.0 {
+ return
+ }
+ // If we are almost out of budgeted time, no further elements
+ // should be added to the queue. This ensures remaining time is
+ // used for processing current queue.
+ if !c.deepState.queueClosed && spent >= 0.85 {
+ c.deepState.queueClosed = true
+ }
+ }
+
+ // if deep search is disabled, don't add any more candidates.
+ if !c.deepState.enabled || c.deepState.queueClosed {
+ continue
+ }
+
+ // Searching members for a type name doesn't make sense.
+ if isTypeName(obj) {
+ continue
+ }
+ if obj.Type() == nil {
+ continue
+ }
+
+ // Don't search embedded fields because they were already included in their
+ // parent's fields.
+ if v, ok := obj.(*types.Var); ok && v.Embedded() {
+ continue
+ }
+
+ if sig, ok := obj.Type().Underlying().(*types.Signature); ok {
+ // If obj is a function that takes no arguments and returns one
+ // value, keep searching across the function call.
+ if sig.Params().Len() == 0 && sig.Results().Len() == 1 {
+ newSearchPath := appendToSearchPath(*item.searchPath, obj, true)
+ // The result of a function call is not addressable.
+ candidates := c.methodsAndFields(ctx, sig.Results().At(0).Type(), false, curCand.imp)
+ c.deepState.enqueue(newSearchPath, candidates...)
+ }
+ }
+
+ newSearchPath := appendToSearchPath(*item.searchPath, obj, false)
+ switch obj := obj.(type) {
+ case *types.PkgName:
+ candidates := c.packageMembers(ctx, obj.Imported(), stdScore, curCand.imp)
+ c.deepState.enqueue(newSearchPath, candidates...)
+ default:
+ candidates := c.methodsAndFields(ctx, obj.Type(), curCand.addressable, curCand.imp)
+ c.deepState.enqueue(newSearchPath, candidates...)
+ }
+ }
+}
+
+// addCandidate adds a completion candidate to suggestions, without searching
+// its members for more candidates.
+func (c *completer) addCandidate(ctx context.Context, cand candidate) {
+ obj := cand.obj
+ if c.matchingCandidate(&cand) {
+ cand.score *= highScore
+
+ if p := c.penalty(&cand); p > 0 {
+ cand.score *= (1 - p)
+ }
+ } else if isTypeName(obj) {
+ // If obj is a *types.TypeName that didn't otherwise match, check
+ // if a literal object of this type makes a good candidate.
+
+ // We only care about named types (i.e. don't want builtin types).
+ if _, isNamed := obj.Type().(*types.Named); isNamed {
+ c.literal(ctx, obj.Type(), cand.imp)
}
}
- // Normalize penalty to a max depth of 10.
- return deepPenalty / 10
+ // Lower score of method calls so we prefer fields and vars over calls.
+ if cand.expandFuncCall {
+ if sig, ok := obj.Type().Underlying().(*types.Signature); ok && sig.Recv() != nil {
+ cand.score *= 0.9
+ }
+ }
+
+ // Prefer private objects over public ones.
+ if !obj.Exported() && obj.Parent() != types.Universe {
+ cand.score *= 1.1
+ }
+
+ // Favor shallow matches by lowering score according to depth.
+ cand.score -= cand.score * c.deepState.scorePenalty()
+
+ if cand.score < 0 {
+ cand.score = 0
+ }
+
+ cand.name = strings.Join(append(c.deepState.curPath.names, cand.obj.Name()), ".")
+ matchScore := c.matcher.Score(cand.name)
+ if matchScore > 0 {
+ cand.score *= float64(matchScore)
+
+ // Avoid calling c.item() for deep candidates that wouldn't be in the top
+ // MaxDeepCompletions anyway.
+ if !c.deepState.inDeepCompletion() || c.deepState.isHighScore(cand.score) {
+ if item, err := c.item(ctx, cand); err == nil {
+ c.items = append(c.items, item)
+ }
+ }
+ }
+
}
-func (c *completer) inDeepCompletion() bool {
- return len(c.deepState.chain) > 0
+// penalty reports a score penalty for cand in the range (0, 1).
+// For example, a candidate is penalized if it has already been used
+// in another switch case statement.
+func (c *completer) penalty(cand *candidate) float64 {
+ for _, p := range c.inference.penalized {
+ if c.objChainMatches(cand.obj, p.objChain) {
+ return p.penalty
+ }
+ }
+
+ return 0
}
-// shouldPrune returns whether we should prune the current deep
-// candidate search to reduce the overall search scope. The
-// maximum search depth is reduced gradually as we use up our
-// completionBudget.
-func (c *completer) shouldPrune() bool {
- if !c.inDeepCompletion() {
+// objChainMatches reports whether cand combined with the surrounding
+// object prefix matches chain.
+func (c *completer) objChainMatches(cand types.Object, chain []types.Object) bool {
+ // For example, when completing:
+ //
+ // foo.ba<>
+ //
+ // If we are considering the deep candidate "bar.baz", cand is baz,
+ // objChain is [foo] and deepChain is [bar]. We would match the
+ // chain [foo, bar, baz].
+
+ if len(chain) != len(c.inference.objChain)+len(c.deepState.curPath.path)+1 {
return false
}
- // Check our remaining budget every 100 candidates.
- if c.opts.budget > 0 && c.deepState.candidateCount%100 == 0 {
- spent := float64(time.Since(c.startTime)) / float64(c.opts.budget)
+ if chain[len(chain)-1] != cand {
+ return false
+ }
- switch {
- case spent >= 0.90:
- // We are close to exhausting our budget. Disable deep completions.
- c.deepState.maxDepth = 0
- case spent >= 0.75:
- // We are running out of budget, reduce max depth again.
- c.deepState.maxDepth = 2
- case spent >= 0.5:
- // We have used half our budget, reduce max depth again.
- c.deepState.maxDepth = 3
- case spent >= 0.25:
- // We have used a good chunk of our budget, so start limiting our search.
- // By default the search depth is unlimited, so this limit, while still
- // generous, is normally a huge reduction in search scope that will result
- // in our search completing very soon.
- c.deepState.maxDepth = 4
+ for i, o := range c.inference.objChain {
+ if chain[i] != o {
+ return false
}
}
- c.deepState.candidateCount++
-
- if c.deepState.maxDepth >= 0 {
- return len(c.deepState.chain) >= c.deepState.maxDepth
- }
-
- return false
-}
-
-// deepSearch searches through cand's subordinate objects for more
-// completion items.
-func (c *completer) deepSearch(ctx context.Context, cand candidate) {
- if c.deepState.maxDepth == 0 {
- return
- }
-
- obj := cand.obj
-
- // If we are definitely completing a struct field name, deep completions
- // don't make sense.
- if c.wantStructFieldCompletions() && c.enclosingCompositeLiteral.inKey {
- return
- }
-
- // Don't search into type names.
- if isTypeName(obj) {
- return
- }
-
- if obj.Type() == nil {
- return
- }
-
- // Don't search embedded fields because they were already included in their
- // parent's fields.
- if v, ok := obj.(*types.Var); ok && v.Embedded() {
- return
- }
-
- if sig, ok := obj.Type().Underlying().(*types.Signature); ok {
- // If obj is a function that takes no arguments and returns one
- // value, keep searching across the function call.
- if sig.Params().Len() == 0 && sig.Results().Len() == 1 {
- // Pass invoke=true since the function needs to be invoked in
- // the deep chain.
- c.deepState.push(obj, true)
- // The result of a function call is not addressable.
- c.methodsAndFields(ctx, sig.Results().At(0).Type(), false, cand.imp)
- c.deepState.pop()
+ for i, o := range c.deepState.curPath.path {
+ if chain[i+len(c.inference.objChain)] != o {
+ return false
}
}
- // Push this object onto our search stack.
- c.deepState.push(obj, false)
-
- switch obj := obj.(type) {
- case *types.PkgName:
- c.packageMembers(ctx, obj.Imported(), stdScore, cand.imp)
- default:
- c.methodsAndFields(ctx, obj.Type(), cand.addressable, cand.imp)
- }
-
- // Pop the object off our search stack.
- c.deepState.pop()
+ return true
}