gopls/internal/lsp/source: avoid unnecessary transitive rdeps
Most callers of ReverseDependencies need only the direct importers.
The new 'transitive bool' flag lets them express that and do less
work.
Change-Id: Ib0a6b1efc892424dde0e4d2c30ad67c91212fc56
Reviewed-on: https://go-review.googlesource.com/c/tools/+/458855
gopls-CI: kokoro <noreply+kokoro@google.com>
Run-TryBot: Alan Donovan <adonovan@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Alan Donovan <adonovan@google.com>
diff --git a/gopls/internal/lsp/cache/graph.go b/gopls/internal/lsp/cache/graph.go
index 5df0234..aaabbdf 100644
--- a/gopls/internal/lsp/cache/graph.go
+++ b/gopls/internal/lsp/cache/graph.go
@@ -103,10 +103,10 @@
}
}
-// reverseTransitiveClosure returns a new mapping containing the
+// reverseReflexiveTransitiveClosure returns a new mapping containing the
// metadata for the specified packages along with any package that
-// transitively imports one of them, keyed by ID.
-func (g *metadataGraph) reverseTransitiveClosure(ids ...PackageID) map[PackageID]*source.Metadata {
+// transitively imports one of them, keyed by ID, including all the initial packages.
+func (g *metadataGraph) reverseReflexiveTransitiveClosure(ids ...PackageID) map[PackageID]*source.Metadata {
seen := make(map[PackageID]*source.Metadata)
var visitAll func([]PackageID)
visitAll = func(ids []PackageID) {
diff --git a/gopls/internal/lsp/cache/snapshot.go b/gopls/internal/lsp/cache/snapshot.go
index ea57d57..bda3690 100644
--- a/gopls/internal/lsp/cache/snapshot.go
+++ b/gopls/internal/lsp/cache/snapshot.go
@@ -819,19 +819,32 @@
return metas, nil
}
-func (s *snapshot) ReverseDependencies(ctx context.Context, id PackageID) (map[PackageID]*source.Metadata, error) {
+func (s *snapshot) ReverseDependencies(ctx context.Context, id PackageID, transitive bool) (map[PackageID]*source.Metadata, error) {
if err := s.awaitLoaded(ctx); err != nil {
return nil, err
}
s.mu.Lock()
meta := s.meta
s.mu.Unlock()
- rdeps := meta.reverseTransitiveClosure(id)
- // Remove the original package ID from the map.
- // TODO(adonovan): we should make ReverseDependencies and
- // reverseTransitiveClosure consistent wrt reflexiveness.
- delete(rdeps, id)
+ var rdeps map[PackageID]*source.Metadata
+ if transitive {
+ rdeps = meta.reverseReflexiveTransitiveClosure(id)
+
+ // Remove the original package ID from the map.
+ // (Callers all want irreflexivity but it's easier
+ // to compute reflexively then subtract.)
+ delete(rdeps, id)
+
+ } else {
+ // direct reverse dependencies
+ rdeps = make(map[PackageID]*source.Metadata)
+ for _, rdepID := range meta.importedBy[id] {
+ if rdep := meta.metadata[rdepID]; rdep != nil {
+ rdeps[rdepID] = rdep
+ }
+ }
+ }
return rdeps, nil
}
diff --git a/gopls/internal/lsp/source/call_hierarchy.go b/gopls/internal/lsp/source/call_hierarchy.go
index b8e11bc..076aed0 100644
--- a/gopls/internal/lsp/source/call_hierarchy.go
+++ b/gopls/internal/lsp/source/call_hierarchy.go
@@ -96,19 +96,17 @@
event.Error(ctx, "error getting enclosing node", err, tag.Method.Of(ref.Name))
continue
}
+
loc := protocol.Location{
URI: callItem.URI,
Range: callItem.Range,
}
-
- if incomingCall, ok := incomingCalls[loc]; ok {
- incomingCall.FromRanges = append(incomingCall.FromRanges, refRange)
- continue
+ call, ok := incomingCalls[loc]
+ if !ok {
+ call = &protocol.CallHierarchyIncomingCall{From: callItem}
+ incomingCalls[loc] = call
}
- incomingCalls[loc] = &protocol.CallHierarchyIncomingCall{
- From: callItem,
- FromRanges: []protocol.Range{refRange},
- }
+ call.FromRanges = append(call.FromRanges, refRange)
}
incomingCallItems := make([]protocol.CallHierarchyIncomingCall, 0, len(incomingCalls))
diff --git a/gopls/internal/lsp/source/references.go b/gopls/internal/lsp/source/references.go
index 33ecdc3..f51f7f1 100644
--- a/gopls/internal/lsp/source/references.go
+++ b/gopls/internal/lsp/source/references.go
@@ -52,29 +52,14 @@
}
targetPkg := metas[len(metas)-1] // widest package
- // Find external references to the package.
- rdeps, err := snapshot.ReverseDependencies(ctx, targetPkg.ID)
+ // Find external direct references to the package (imports).
+ rdeps, err := snapshot.ReverseDependencies(ctx, targetPkg.ID, false)
if err != nil {
return nil, err
}
var refs []*ReferenceInfo
for _, rdep := range rdeps {
- // Optimization: skip this loop (parsing) if rdep
- // doesn't directly import the target package.
- // (This logic also appears in rename; perhaps we need
- // a ReverseDirectDependencies method?)
- direct := false
- for _, importedID := range rdep.DepsByImpPath {
- if importedID == targetPkg.ID {
- direct = true
- break
- }
- }
- if !direct {
- continue
- }
-
for _, uri := range rdep.CompiledGoFiles {
fh, err := snapshot.GetFile(ctx, uri)
if err != nil {
@@ -199,12 +184,16 @@
// Only search dependents if the object is exported.
if qo.obj.Exported() {
- rdeps, err := snapshot.ReverseDependencies(ctx, qo.pkg.ID())
+ // If obj is a package-level object, we need only search
+ // among direct reverse dependencies.
+ // TODO(adonovan): opt: this will still spuriously search
+ // transitively for (e.g.) capitalized local variables.
+ // We could do better by checking for an objectpath.
+ transitive := qo.obj.Pkg().Scope().Lookup(qo.obj.Name()) != qo.obj
+ rdeps, err := snapshot.ReverseDependencies(ctx, qo.pkg.ID(), transitive)
if err != nil {
return nil, err
}
- // TODO(adonovan): opt: if obj is a package-level object, we need
- // only search among direct reverse dependencies.
ids := make([]PackageID, 0, len(rdeps))
for _, rdep := range rdeps {
ids = append(ids, rdep.ID)
diff --git a/gopls/internal/lsp/source/rename.go b/gopls/internal/lsp/source/rename.go
index 93048e0..fa98f46 100644
--- a/gopls/internal/lsp/source/rename.go
+++ b/gopls/internal/lsp/source/rename.go
@@ -268,6 +268,7 @@
}
if m.Module == nil {
+ // This check will always fail under Bazel.
return nil, fmt.Errorf("cannot rename package: missing module information for package %q", m.PkgPath)
}
@@ -364,7 +365,7 @@
//
// Edits are written into the edits map.
func renameImports(ctx context.Context, snapshot Snapshot, m *Metadata, newPath ImportPath, newName PackageName, seen seenPackageRename, edits map[span.URI][]protocol.TextEdit) error {
- rdeps, err := snapshot.ReverseDependencies(ctx, m.ID)
+ rdeps, err := snapshot.ReverseDependencies(ctx, m.ID, false) // find direct importers
if err != nil {
return err
}
@@ -376,20 +377,6 @@
continue // for renaming, these variants are redundant
}
- // Optimization: skip packages that don't directly import m.
- // (This logic also appears in 'references'; perhaps we need
- // Snapshot.ReverseDirectDependencies?)
- direct := false
- for _, importedID := range rdep.DepsByImpPath {
- if importedID == m.ID {
- direct = true
- break
- }
- }
- if !direct {
- continue
- }
-
for _, uri := range rdep.CompiledGoFiles {
if seen.add(uri, m.PkgPath) {
continue
diff --git a/gopls/internal/lsp/source/view.go b/gopls/internal/lsp/source/view.go
index b6bab12..0aeac54 100644
--- a/gopls/internal/lsp/source/view.go
+++ b/gopls/internal/lsp/source/view.go
@@ -177,8 +177,9 @@
// ReverseDependencies returns a new mapping whose entries are
// the ID and Metadata of each package in the workspace that
- // transitively depends on the package denoted by id, excluding id itself.
- ReverseDependencies(ctx context.Context, id PackageID) (map[PackageID]*Metadata, error)
+ // directly or transitively depend on the package denoted by id,
+ // excluding id itself.
+ ReverseDependencies(ctx context.Context, id PackageID, transitive bool) (map[PackageID]*Metadata, error)
// CachedImportPaths returns all the imported packages loaded in this
// snapshot, indexed by their package path (not import path, despite the name)
diff --git a/gopls/internal/regtest/misc/references_test.go b/gopls/internal/regtest/misc/references_test.go
index 7cff19c..0e8ff45 100644
--- a/gopls/internal/regtest/misc/references_test.go
+++ b/gopls/internal/regtest/misc/references_test.go
@@ -40,6 +40,7 @@
t.Fatal(err)
}
if len(refs) != 2 {
+ // TODO(adonovan): make this assertion less maintainer-hostile.
t.Fatalf("got %v reference(s), want 2", len(refs))
}
// The first reference is guaranteed to be the definition.
@@ -152,6 +153,7 @@
pos := env.RegexpSearch(f, test.packageName)
refs := env.References(fmt.Sprintf("%s/a.go", test.packageName), pos)
if len(refs) != test.wantRefCount {
+ // TODO(adonovan): make this assertion less maintainer-hostile.
t.Fatalf("got %v reference(s), want %d", len(refs), test.wantRefCount)
}
var refURIs []string
