blob: 709f1abfb2f0c5ead6f7aaad4b08aad4f09ec1e8 [file] [log] [blame]
// Copyright 2022 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package cache
import (
"sort"
"golang.org/x/tools/gopls/internal/lsp/source"
"golang.org/x/tools/gopls/internal/span"
)
// A metadataGraph is an immutable and transitively closed import
// graph of Go packages, as obtained from go/packages.
type metadataGraph struct {
// metadata maps package IDs to their associated metadata.
metadata map[PackageID]*source.Metadata
// importedBy maps package IDs to the list of packages that import them.
importedBy map[PackageID][]PackageID
// ids maps file URIs to package IDs, sorted by (!valid, cli, packageID).
// A single file may belong to multiple packages due to tests packages.
ids map[span.URI][]PackageID
}
// Clone creates a new metadataGraph, applying the given updates to the
// receiver.
func (g *metadataGraph) Clone(updates map[PackageID]*source.Metadata) *metadataGraph {
if len(updates) == 0 {
// Optimization: since the graph is immutable, we can return the receiver.
return g
}
result := &metadataGraph{metadata: make(map[PackageID]*source.Metadata, len(g.metadata))}
// Copy metadata.
for id, m := range g.metadata {
result.metadata[id] = m
}
for id, m := range updates {
if m == nil {
delete(result.metadata, id)
} else {
result.metadata[id] = m
}
}
result.build()
return result
}
// build constructs g.importedBy and g.uris from g.metadata.
func (g *metadataGraph) build() {
// Build the import graph.
g.importedBy = make(map[PackageID][]PackageID)
for id, m := range g.metadata {
for _, depID := range m.DepsByPkgPath {
g.importedBy[depID] = append(g.importedBy[depID], id)
}
}
// Collect file associations.
g.ids = make(map[span.URI][]PackageID)
for id, m := range g.metadata {
uris := map[span.URI]struct{}{}
for _, uri := range m.CompiledGoFiles {
uris[uri] = struct{}{}
}
for _, uri := range m.GoFiles {
uris[uri] = struct{}{}
}
for uri := range uris {
g.ids[uri] = append(g.ids[uri], id)
}
}
// Sort and filter file associations.
for uri, ids := range g.ids {
sort.Slice(ids, func(i, j int) bool {
cli := source.IsCommandLineArguments(ids[i])
clj := source.IsCommandLineArguments(ids[j])
if cli != clj {
return clj
}
// 2. packages appear in name order.
return ids[i] < ids[j]
})
// Choose the best IDs for each URI, according to the following rules:
// - If there are any valid real packages, choose them.
// - Else, choose the first valid command-line-argument package, if it exists.
//
// TODO(rfindley): it might be better to track all IDs here, and exclude
// them later in PackagesForFile, but this is the existing behavior.
for i, id := range ids {
// If we've seen *anything* prior to command-line arguments package, take
// it. Note that ids[0] may itself be command-line-arguments.
if i > 0 && source.IsCommandLineArguments(id) {
g.ids[uri] = ids[:i]
break
}
}
}
}
// reverseTransitiveClosure calculates the set of packages that transitively
// import an id in ids. 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(ids ...PackageID) map[PackageID]bool {
seen := make(map[PackageID]bool)
var visitAll func([]PackageID)
visitAll = func(ids []PackageID) {
for _, id := range ids {
if seen[id] {
continue
}
m := g.metadata[id]
// Only use invalid metadata if we support it.
if m == nil {
continue
}
seen[id] = true
visitAll(g.importedBy[id])
}
}
visitAll(ids)
return seen
}