blob: c1beff828660976011c32ce5fe5149333cb40d39 [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/internal/lsp/source"
"golang.org/x/tools/internal/span"
)
// A metadataGraph holds information about a transtively closed import graph of
// Go packages, as obtained from go/packages.
//
// Currently a new metadata graph is created for each snapshot.
// TODO(rfindley): make this type immutable, so that it may be shared across
// snapshots.
type metadataGraph struct {
// metadata maps package IDs to their associated metadata.
metadata map[PackageID]*KnownMetadata
// 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]*KnownMetadata) *metadataGraph {
if len(updates) == 0 {
// Optimization: since the graph is immutable, we can return the receiver.
return g
}
result := &metadataGraph{metadata: make(map[PackageID]*KnownMetadata, 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 _, importID := range m.Deps {
g.importedBy[importID] = append(g.importedBy[importID], 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.
//
// We choose the first non-empty set of package associations out of the
// following. For simplicity, call a non-command-line-arguments package a
// "real" package.
//
// 1: valid real packages
// 2: a valid command-line-arguments package
// 3: invalid real packages
// 4: an invalid command-line-arguments package
for uri, ids := range g.ids {
sort.Slice(ids, func(i, j int) bool {
// 1. valid packages appear earlier.
validi := g.metadata[ids[i]].Valid
validj := g.metadata[ids[j]].Valid
if validi != validj {
return validi
}
// 2. command-line-args packages appear later.
cli := source.IsCommandLineArguments(string(ids[i]))
clj := source.IsCommandLineArguments(string(ids[j]))
if cli != clj {
return clj
}
// 3. 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.
// - Else, keep using all the invalid metadata.
//
// TODO(rfindley): it might be better to track all IDs here, and exclude
// them later in PackagesForFile, but this is the existing behavior.
hasValidMetadata := false
for i, id := range ids {
m := g.metadata[id]
if m.Valid {
hasValidMetadata = true
} else if hasValidMetadata {
g.ids[uri] = ids[:i]
break
}
// 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(string(id)) {
g.ids[uri] = ids[:i]
break
}
}
}
}
// 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
}