| // 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 |
| } |