internal/lsp/cache: invalidate reverse closure when loading packages
When setting new metadata for a package ID, we invalidate the
corresponding type-checked packages. Whenever we invalidate a package,
we must also invalidate its reverse transitive closure. Otherwise we may
end up in a scenario where the go/types import graph does not match
gopls' view of the import graph.
Change-Id: I8db6ff3e4a722656e6dde7907e7c0470375c4847
Reviewed-on: https://go-review.googlesource.com/c/tools/+/413683
Run-TryBot: Robert Findley <rfindley@google.com>
Reviewed-by: Alan Donovan <adonovan@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
diff --git a/internal/lsp/cache/graph.go b/internal/lsp/cache/graph.go
index 3f24773..dc7d4fa 100644
--- a/internal/lsp/cache/graph.go
+++ b/internal/lsp/cache/graph.go
@@ -128,3 +128,44 @@
}
}
}
+
+// reverseTransitiveClosure calculates the set of packages that transitively
+// reach an id in ids via their Deps. The result also includes given ids.
+//
+// If includeInvalid is false, the algorithm ignores packages with invalid
+// metadata (including those in the given list of ids).
+func (g *metadataGraph) reverseTransitiveClosure(includeInvalid bool, ids ...PackageID) map[PackageID]struct{} {
+ seen := make(map[PackageID]struct{})
+ var visitAll func([]PackageID)
+ visitAll = func(ids []PackageID) {
+ for _, id := range ids {
+ if _, ok := seen[id]; ok {
+ continue
+ }
+ m := g.metadata[id]
+ // Only use invalid metadata if we support it.
+ if m == nil || !(m.Valid || includeInvalid) {
+ continue
+ }
+ seen[id] = struct{}{}
+ visitAll(g.importedBy[id])
+ }
+ }
+ visitAll(ids)
+ return seen
+}
+
+func collectReverseTransitiveClosure(g *metadataGraph, includeInvalid bool, ids []PackageID, seen map[PackageID]struct{}) {
+ for _, id := range ids {
+ if _, ok := seen[id]; ok {
+ continue
+ }
+ m := g.metadata[id]
+ // Only use invalid metadata if we support it.
+ if m == nil || !(m.Valid || includeInvalid) {
+ continue
+ }
+ seen[id] = struct{}{}
+ collectReverseTransitiveClosure(g, includeInvalid, g.importedBy[id], seen)
+ }
+}
diff --git a/internal/lsp/cache/load.go b/internal/lsp/cache/load.go
index bdafdcd..db9a06d 100644
--- a/internal/lsp/cache/load.go
+++ b/internal/lsp/cache/load.go
@@ -204,18 +204,28 @@
}
}
+ var loadedIDs []PackageID
+ for id := range updates {
+ loadedIDs = append(loadedIDs, id)
+ }
+
s.mu.Lock()
+
+ // invalidate the reverse transitive closure of packages that have changed.
+ invalidatedPackages := s.meta.reverseTransitiveClosure(true, loadedIDs...)
s.meta = s.meta.Clone(updates)
+
// Invalidate any packages we may have associated with this metadata.
//
- // TODO(rfindley): if we didn't already invalidate these in snapshot.clone,
- // shouldn't we invalidate the reverse transitive closure?
- for _, m := range updates {
+ // TODO(rfindley): this should not be necessary, as we should have already
+ // invalidated in snapshot.clone.
+ for id := range invalidatedPackages {
for _, mode := range []source.ParseMode{source.ParseHeader, source.ParseExported, source.ParseFull} {
- key := packageKey{mode, m.ID}
+ key := packageKey{mode, id}
delete(s.packages, key)
}
}
+
s.workspacePackages = computeWorkspacePackagesLocked(s, s.meta)
s.dumpWorkspace("load")
s.mu.Unlock()
diff --git a/internal/lsp/cache/snapshot.go b/internal/lsp/cache/snapshot.go
index 05f8928..8194750 100644
--- a/internal/lsp/cache/snapshot.go
+++ b/internal/lsp/cache/snapshot.go
@@ -70,6 +70,10 @@
builtin span.URI
// meta holds loaded metadata.
+ //
+ // meta is guarded by mu, but the metadataGraph itself is immutable.
+ // TODO(rfindley): in many places we hold mu while operating on meta, even
+ // though we only need to hold mu while reading the pointer.
meta *metadataGraph
// files maps file URIs to their corresponding FileHandles.
@@ -627,8 +631,10 @@
if err := s.awaitLoaded(ctx); err != nil {
return nil, err
}
- ids := make(map[PackageID]struct{})
- s.transitiveReverseDependencies(PackageID(id), ids)
+ s.mu.Lock()
+ meta := s.meta
+ s.mu.Unlock()
+ ids := meta.reverseTransitiveClosure(s.useInvalidMetadata(), PackageID(id))
// Make sure to delete the original package ID from the map.
delete(ids, PackageID(id))
@@ -652,24 +658,6 @@
return ph.check(ctx, s)
}
-// transitiveReverseDependencies populates the ids map with package IDs
-// belonging to the provided package and its transitive reverse dependencies.
-func (s *snapshot) transitiveReverseDependencies(id PackageID, ids map[PackageID]struct{}) {
- if _, ok := ids[id]; ok {
- return
- }
- m := s.getMetadata(id)
- // Only use invalid metadata if we support it.
- if m == nil || !(m.Valid || s.useInvalidMetadata()) {
- return
- }
- ids[id] = struct{}{}
- importedBy := s.getImportedBy(id)
- for _, parentID := range importedBy {
- s.transitiveReverseDependencies(parentID, ids)
- }
-}
-
func (s *snapshot) getGoFile(key parseKey) *parseGoHandle {
s.mu.Lock()
defer s.mu.Unlock()
@@ -1879,7 +1867,6 @@
}
// Invalidate reverse dependencies too.
- // TODO(heschi): figure out the locking model and use transitiveReverseDeps?
// idsToInvalidate keeps track of transitive reverse dependencies.
// If an ID is present in the map, invalidate its types.
// If an ID's value is true, invalidate its metadata too.
