gopls/internal/cache/metadata/graph.go - tools.git - Git at Google

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

 import (
 	"cmp"
 	"iter"
 	"maps"
 	"slices"
 	"sort"
 	"strings"

 	"golang.org/x/tools/go/packages"
 	"golang.org/x/tools/gopls/internal/protocol"
 	"golang.org/x/tools/gopls/internal/util/bug"
 )

 // A Graph is an immutable and transitively closed graph of [Package] data.
 type Graph struct {
 	// Packages maps package IDs to their associated Packages.
 	Packages map[PackageID]*Package

 	// Each of the three maps below is an index of the pointer values held
 	// by the Packages map. However, Package pointers are not generally canonical.

 	// ImportedBy maps package IDs to the list of packages that import them.
 	ImportedBy map[PackageID][]*Package

 	// ForPackagePath maps package by their package path to their package ID.
 	// Non-test packages appear before test packages, and within each of those
 	// categories, packages with fewer CompiledGoFiles appear first.
 	ForPackagePath map[PackagePath][]*Package

 	// ForFile maps file URIs to packages, sorted by (!valid, cli, packageID).
 	// A single file may belong to multiple packages due to tests packages.
 	ForFile map[protocol.DocumentURI][]*Package
 }

 // Metadata implements the [Source] interface
 func (g *Graph) Metadata(id PackageID) *Package {
 	return g.Packages[id]
 }

 // Update creates a new Graph containing the result of applying the given
 // updates to the receiver, though the receiver is not itself mutated. As a
 // special case, if updates is empty, Update just returns the receiver.
 //
 // A nil map value is used to indicate a deletion.
 func (g *Graph) Update(updates map[PackageID]*Package) *Graph {
 	if len(updates) == 0 {
 		// Optimization: since the graph is immutable, we can return the receiver.
 		return g
 	}

 	// Debugging golang/go#64227, golang/vscode-go#3126:
 	// Assert that the existing metadata graph is acyclic.
 	if cycle := cyclic(g.Packages); cycle != "" {
 		bug.Reportf("metadata is cyclic even before updates: %s", cycle)
 	}
 	// Assert that the updates contain no self-cycles.
 	for id, mp := range updates {
 		if mp != nil {
 			for _, depID := range mp.DepsByPkgPath {
 				if depID == id {
 					bug.Reportf("self-cycle in metadata update: %s", id)
 				}
 			}
 		}
 	}

 	// Copy pkgs map then apply updates.
 	pkgs := make(map[PackageID]*Package, len(g.Packages))
 	maps.Copy(pkgs, g.Packages)
 	for id, mp := range updates {
 		if mp == nil {
 			delete(pkgs, id)
 		} else {
 			pkgs[id] = mp
 		}
 	}

 	// Break import cycles involving updated nodes.
 	breakImportCycles(pkgs, updates)

 	return newGraph(pkgs)
 }

 // newGraph returns a new metadataGraph,
 // deriving relations from the specified metadata.
 func newGraph(pkgs map[PackageID]*Package) *Graph {
 	// Build the import graph.
 	importedBy := make(map[PackageID][]*Package)
 	byPackagePath := make(map[PackagePath][]*Package)
 	for _, mp := range pkgs {
 		for _, depID := range mp.DepsByPkgPath {
 			importedBy[depID] = append(importedBy[depID], mp)
 		}
 		byPackagePath[mp.PkgPath] = append(byPackagePath[mp.PkgPath], mp)
 	}

 	// Collect file associations.
 	uriPkgs := make(map[protocol.DocumentURI][]*Package)
 	for _, mp := range pkgs {
 		uris := map[protocol.DocumentURI]struct{}{}
 		for _, uri := range mp.CompiledGoFiles {
 			uris[uri] = struct{}{}
 		}
 		for _, uri := range mp.GoFiles {
 			uris[uri] = struct{}{}
 		}
 		for _, uri := range mp.OtherFiles {
 			if strings.HasSuffix(string(uri), ".s") { // assembly
 				uris[uri] = struct{}{}
 			}
 		}
 		for uri := range uris {
 			uriPkgs[uri] = append(uriPkgs[uri], mp)
 		}
 	}

 	// Sort and filter file associations.
 	for uri, pkgs := range uriPkgs {
 		sort.Slice(pkgs, func(i, j int) bool {
 			cli := IsCommandLineArguments(pkgs[i].ID)
 			clj := IsCommandLineArguments(pkgs[j].ID)
 			if cli != clj {
 				return clj
 			}

 			// 2. packages appear in name order.
 			return pkgs[i].ID < pkgs[j].ID
 		})

 		// Choose the best packages 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 packages here, and exclude
 		// them later when type checking, but this is the existing behavior.
 		for i, pkg := range pkgs {
 			// If we've seen *anything* prior to command-line arguments package, take
 			// it. Note that pkgs[0] may itself be command-line-arguments.
 			if i > 0 && IsCommandLineArguments(pkg.ID) {
 				uriPkgs[uri] = pkgs[:i]
 				break
 			}
 		}
 	}

 	for _, mps := range byPackagePath {
 		slices.SortFunc(mps, func(a, b *Package) int {
 			if (a.ForTest == "") != (b.ForTest == "") {
 				if a.ForTest == "" {
 					return -1
 				}
 				return 1
 			}
 			if c := cmp.Compare(len(a.CompiledGoFiles), len(b.CompiledGoFiles)); c != 0 {
 				return c
 			}
 			return cmp.Compare(a.ID, b.ID)
 		})
 	}

 	return &Graph{
 		Packages:       pkgs,
 		ImportedBy:     importedBy,
 		ForPackagePath: byPackagePath,
 		ForFile:        uriPkgs,
 	}
 }

 // 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, including all the initial packages.
 func (g *Graph) ReverseReflexiveTransitiveClosure(ids ...PackageID) map[PackageID]*Package {
 	seen := make(map[PackageID]*Package)
 	var visitAll func([]*Package)
 	visitAll = func(pkgs []*Package) {
 		for _, pkg := range pkgs {
 			if seen[pkg.ID] == nil {
 				seen[pkg.ID] = pkg
 				visitAll(g.ImportedBy[pkg.ID])
 			}
 		}
 	}
 	var initial []*Package
 	for _, id := range ids {
 		if pkg := g.Packages[id]; pkg != nil {
 			initial = append(initial, pkg)
 		}
 	}
 	visitAll(initial)
 	return seen
 }

 // ForwardReflexiveTransitiveClosure returns an iterator over the
 // specified nodes and all their forward dependencies, in an arbitrary
 // topological (dependencies-first) order. The order may vary.
 func (g *Graph) ForwardReflexiveTransitiveClosure(ids ...PackageID) iter.Seq[*Package] {
 	return func(yield func(*Package) bool) {
 		seen := make(map[PackageID]bool)
 		var visit func(PackageID) bool
 		visit = func(id PackageID) bool {
 			if !seen[id] {
 				seen[id] = true
 				if mp := g.Packages[id]; mp != nil {
 					for _, depID := range mp.DepsByPkgPath {
 						if !visit(depID) {
 							return false
 						}
 					}
 					if !yield(mp) {
 						return false
 					}
 				}
 			}
 			return true
 		}
 		for _, id := range ids {
 			visit(id)
 		}
 	}
 }

 // breakImportCycles breaks import cycles in the metadata by deleting
 // Deps* edges. It modifies only metadata present in the 'updates'
 // subset. This function has an internal test.
 func breakImportCycles(metadata, updates map[PackageID]*Package) {
 	// 'go list' should never report a cycle without flagging it
 	// as such, but we're extra cautious since we're combining
 	// information from multiple runs of 'go list'. Also, Bazel
 	// may silently report cycles.
 	cycles := detectImportCycles(metadata, updates)
 	if len(cycles) > 0 {
 		// There were cycles (uncommon). Break them.
 		//
 		// The naive way to break cycles would be to perform a
 		// depth-first traversal and to detect and delete
 		// cycle-forming edges as we encounter them.
 		// However, we're not allowed to modify the existing
 		// Metadata records, so we can only break edges out of
 		// the 'updates' subset.
 		//
 		// Another possibility would be to delete not the
 		// cycle forming edge but the topmost edge on the
 		// stack whose tail is an updated node.
 		// However, this would require that we retroactively
 		// undo all the effects of the traversals that
 		// occurred since that edge was pushed on the stack.
 		//
 		// We use a simpler scheme: we compute the set of cycles.
 		// All cyclic paths necessarily involve at least one
 		// updated node, so it is sufficient to break all
 		// edges from each updated node to other members of
 		// the strong component.
 		//
 		// This may result in the deletion of dominating
 		// edges, causing some dependencies to appear
 		// spuriously unreachable. Consider A <-> B -> C
 		// where updates={A,B}. The cycle is {A,B} so the
 		// algorithm will break both A->B and B->A, causing
 		// A to no longer depend on B or C.
 		//
 		// But that's ok: any error in Metadata.Errors is
 		// conservatively assumed by snapshot.clone to be a
 		// potential import cycle error, and causes special
 		// invalidation so that if B later drops its
 		// cycle-forming import of A, both A and B will be
 		// invalidated.
 		for _, cycle := range cycles {
 			cyclic := make(map[PackageID]bool)
 			for _, mp := range cycle {
 				cyclic[mp.ID] = true
 			}
 			for id := range cyclic {
 				if mp := updates[id]; mp != nil {
 					for path, depID := range mp.DepsByImpPath {
 						if cyclic[depID] {
 							delete(mp.DepsByImpPath, path)
 						}
 					}
 					for path, depID := range mp.DepsByPkgPath {
 						if cyclic[depID] {
 							delete(mp.DepsByPkgPath, path)
 						}
 					}

 					// Set m.Errors to enable special
 					// invalidation logic in snapshot.clone.
 					if len(mp.Errors) == 0 {
 						mp.Errors = []packages.Error{{
 							Msg:  "detected import cycle",
 							Kind: packages.ListError,
 						}}
 					}
 				}
 			}
 		}

 		// double-check when debugging
 		if false {
 			if cycles := detectImportCycles(metadata, updates); len(cycles) > 0 {
 				bug.Reportf("unbroken cycle: %v", cycles)
 			}
 		}
 	}
 }

 // cyclic returns a description of a cycle,
 // if the graph is cyclic, otherwise "".
 func cyclic(graph map[PackageID]*Package) string {
 	const (
 		unvisited = 0
 		visited   = 1
 		onstack   = 2
 	)
 	color := make(map[PackageID]int)
 	var visit func(id PackageID) string
 	visit = func(id PackageID) string {
 		switch color[id] {
 		case unvisited:
 			color[id] = onstack
 		case onstack:
 			return string(id) // cycle!
 		case visited:
 			return ""
 		}
 		if mp := graph[id]; mp != nil {
 			for _, depID := range mp.DepsByPkgPath {
 				if cycle := visit(depID); cycle != "" {
 					return string(id) + "->" + cycle
 				}
 			}
 		}
 		color[id] = visited
 		return ""
 	}
 	for id := range graph {
 		if cycle := visit(id); cycle != "" {
 			return cycle
 		}
 	}
 	return ""
 }

 // detectImportCycles reports cycles in the metadata graph. It returns a new
 // unordered array of all cycles (nontrivial strong components) in the
 // metadata graph reachable from a non-nil 'updates' value.
 func detectImportCycles(metadata, updates map[PackageID]*Package) [][]*Package {
 	// We use the depth-first algorithm of Tarjan.
 	// https://doi.org/10.1137/0201010
 	//
 	// TODO(adonovan): when we can use generics, consider factoring
 	// in common with the other implementation of Tarjan (in typerefs),
 	// abstracting over the node and edge representation.

 	// A node wraps a Metadata with its working state.
 	// (Unfortunately we can't intrude on shared Metadata.)
 	type node struct {
 		rep            *node
 		mp             *Package
 		index, lowlink int32
 		scc            int8 // TODO(adonovan): opt: cram these 1.5 bits into previous word
 	}
 	nodes := make(map[PackageID]*node, len(metadata))
 	nodeOf := func(id PackageID) *node {
 		n, ok := nodes[id]
 		if !ok {
 			mp := metadata[id]
 			if mp == nil {
 				// Dangling import edge.
 				// Not sure whether a go/packages driver ever
 				// emits this, but create a dummy node in case.
 				// Obviously it won't be part of any cycle.
 				mp = &Package{ID: id}
 			}
 			n = &node{mp: mp}
 			n.rep = n
 			nodes[id] = n
 		}
 		return n
 	}

 	// find returns the canonical node decl.
 	// (The nodes form a disjoint set forest.)
 	var find func(*node) *node
 	find = func(n *node) *node {
 		rep := n.rep
 		if rep != n {
 			rep = find(rep)
 			n.rep = rep // simple path compression (no union-by-rank)
 		}
 		return rep
 	}

 	// global state
 	var (
 		index int32 = 1
 		stack []*node
 		sccs  [][]*Package // set of nontrivial strongly connected components
 	)

 	// visit implements the depth-first search of Tarjan's SCC algorithm
 	// Precondition: x is canonical.
 	var visit func(*node)
 	visit = func(x *node) {
 		x.index = index
 		x.lowlink = index
 		index++

 		stack = append(stack, x) // push
 		x.scc = -1

 		for _, yid := range x.mp.DepsByPkgPath {
 			y := nodeOf(yid)
 			// Loop invariant: x is canonical.
 			y = find(y)
 			if x == y {
 				continue // nodes already combined (self-edges are impossible)
 			}

 			switch {
 			case y.scc > 0:
 				// y is already a collapsed SCC

 			case y.scc < 0:
 				// y is on the stack, and thus in the current SCC.
 				if y.index < x.lowlink {
 					x.lowlink = y.index
 				}

 			default:
 				// y is unvisited; visit it now.
 				visit(y)
 				// Note: x and y are now non-canonical.
 				x = find(x)
 				if y.lowlink < x.lowlink {
 					x.lowlink = y.lowlink
 				}
 			}
 		}

 		// Is x the root of an SCC?
 		if x.lowlink == x.index {
 			// Gather all metadata in the SCC (if nontrivial).
 			var scc []*Package
 			for {
 				// Pop y from stack.
 				i := len(stack) - 1
 				y := stack[i]
 				stack = stack[:i]
 				if x != y || scc != nil {
 					scc = append(scc, y.mp)
 				}
 				if x == y {
 					break // complete
 				}
 				// x becomes y's canonical representative.
 				y.rep = x
 			}
 			if scc != nil {
 				sccs = append(sccs, scc)
 			}
 			x.scc = 1
 		}
 	}

 	// Visit only the updated nodes:
 	// the existing metadata graph has no cycles,
 	// so any new cycle must involve an updated node.
 	for id, mp := range updates {
 		if mp != nil {
 			if n := nodeOf(id); n.index == 0 { // unvisited
 				visit(n)
 			}
 		}
 	}

 	return sccs
 }
	// 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 metadata

	import (
	"cmp"
	"iter"
	"maps"
	"slices"
	"sort"
	"strings"

	"golang.org/x/tools/go/packages"
	"golang.org/x/tools/gopls/internal/protocol"
	"golang.org/x/tools/gopls/internal/util/bug"
	)

	// A Graph is an immutable and transitively closed graph of [Package] data.
	type Graph struct {
	// Packages maps package IDs to their associated Packages.
	Packages map[PackageID]*Package

	// Each of the three maps below is an index of the pointer values held
	// by the Packages map. However, Package pointers are not generally canonical.

	// ImportedBy maps package IDs to the list of packages that import them.
	ImportedBy map[PackageID][]*Package

	// ForPackagePath maps package by their package path to their package ID.
	// Non-test packages appear before test packages, and within each of those
	// categories, packages with fewer CompiledGoFiles appear first.
	ForPackagePath map[PackagePath][]*Package

	// ForFile maps file URIs to packages, sorted by (!valid, cli, packageID).
	// A single file may belong to multiple packages due to tests packages.
	ForFile map[protocol.DocumentURI][]*Package
	}

	// Metadata implements the [Source] interface
	func (g Graph) Metadata(id PackageID) Package {
	return g.Packages[id]
	}

	// Update creates a new Graph containing the result of applying the given
	// updates to the receiver, though the receiver is not itself mutated. As a
	// special case, if updates is empty, Update just returns the receiver.
	//
	// A nil map value is used to indicate a deletion.
	func (g Graph) Update(updates map[PackageID]Package) *Graph {
	if len(updates) == 0 {
	// Optimization: since the graph is immutable, we can return the receiver.
	return g
	}

	// Debugging golang/go#64227, golang/vscode-go#3126:
	// Assert that the existing metadata graph is acyclic.
	if cycle := cyclic(g.Packages); cycle != "" {
	bug.Reportf("metadata is cyclic even before updates: %s", cycle)
	}
	// Assert that the updates contain no self-cycles.
	for id, mp := range updates {
	if mp != nil {
	for _, depID := range mp.DepsByPkgPath {
	if depID == id {
	bug.Reportf("self-cycle in metadata update: %s", id)
	}
	}
	}
	}

	// Copy pkgs map then apply updates.
	pkgs := make(map[PackageID]*Package, len(g.Packages))
	maps.Copy(pkgs, g.Packages)
	for id, mp := range updates {
	if mp == nil {
	delete(pkgs, id)
	} else {
	pkgs[id] = mp
	}
	}

	// Break import cycles involving updated nodes.
	breakImportCycles(pkgs, updates)

	return newGraph(pkgs)
	}

	// newGraph returns a new metadataGraph,
	// deriving relations from the specified metadata.
	func newGraph(pkgs map[PackageID]Package) Graph {
	// Build the import graph.
	importedBy := make(map[PackageID][]*Package)
	byPackagePath := make(map[PackagePath][]*Package)
	for _, mp := range pkgs {
	for _, depID := range mp.DepsByPkgPath {
	importedBy[depID] = append(importedBy[depID], mp)
	}
	byPackagePath[mp.PkgPath] = append(byPackagePath[mp.PkgPath], mp)
	}

	// Collect file associations.
	uriPkgs := make(map[protocol.DocumentURI][]*Package)
	for _, mp := range pkgs {
	uris := map[protocol.DocumentURI]struct{}{}
	for _, uri := range mp.CompiledGoFiles {
	uris[uri] = struct{}{}
	}
	for _, uri := range mp.GoFiles {
	uris[uri] = struct{}{}
	}
	for _, uri := range mp.OtherFiles {
	if strings.HasSuffix(string(uri), ".s") { // assembly
	uris[uri] = struct{}{}
	}
	}
	for uri := range uris {
	uriPkgs[uri] = append(uriPkgs[uri], mp)
	}
	}

	// Sort and filter file associations.
	for uri, pkgs := range uriPkgs {
	sort.Slice(pkgs, func(i, j int) bool {
	cli := IsCommandLineArguments(pkgs[i].ID)
	clj := IsCommandLineArguments(pkgs[j].ID)
	if cli != clj {
	return clj
	}

	// 2. packages appear in name order.
	return pkgs[i].ID < pkgs[j].ID
	})

	// Choose the best packages 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 packages here, and exclude
	// them later when type checking, but this is the existing behavior.
	for i, pkg := range pkgs {
	// If we've seen anything prior to command-line arguments package, take
	// it. Note that pkgs[0] may itself be command-line-arguments.
	if i > 0 && IsCommandLineArguments(pkg.ID) {
	uriPkgs[uri] = pkgs[:i]
	break
	}
	}
	}

	for _, mps := range byPackagePath {
	slices.SortFunc(mps, func(a, b *Package) int {
	if (a.ForTest == "") != (b.ForTest == "") {
	if a.ForTest == "" {
	return -1
	}
	return 1
	}
	if c := cmp.Compare(len(a.CompiledGoFiles), len(b.CompiledGoFiles)); c != 0 {
	return c
	}
	return cmp.Compare(a.ID, b.ID)
	})
	}

	return &Graph{
	Packages: pkgs,
	ImportedBy: importedBy,
	ForPackagePath: byPackagePath,
	ForFile: uriPkgs,
	}
	}

	// 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, including all the initial packages.
	func (g Graph) ReverseReflexiveTransitiveClosure(ids ...PackageID) map[PackageID]Package {
	seen := make(map[PackageID]*Package)
	var visitAll func([]*Package)
	visitAll = func(pkgs []*Package) {
	for _, pkg := range pkgs {
	if seen[pkg.ID] == nil {
	seen[pkg.ID] = pkg
	visitAll(g.ImportedBy[pkg.ID])
	}
	}
	}
	var initial []*Package
	for _, id := range ids {
	if pkg := g.Packages[id]; pkg != nil {
	initial = append(initial, pkg)
	}
	}
	visitAll(initial)
	return seen
	}

	// ForwardReflexiveTransitiveClosure returns an iterator over the
	// specified nodes and all their forward dependencies, in an arbitrary
	// topological (dependencies-first) order. The order may vary.
	func (g Graph) ForwardReflexiveTransitiveClosure(ids ...PackageID) iter.Seq[Package] {
	return func(yield func(*Package) bool) {
	seen := make(map[PackageID]bool)
	var visit func(PackageID) bool
	visit = func(id PackageID) bool {
	if !seen[id] {
	seen[id] = true
	if mp := g.Packages[id]; mp != nil {
	for _, depID := range mp.DepsByPkgPath {
	if !visit(depID) {
	return false
	}
	}
	if !yield(mp) {
	return false
	}
	}
	}
	return true
	}
	for _, id := range ids {
	visit(id)
	}
	}
	}

	// breakImportCycles breaks import cycles in the metadata by deleting
	// Deps* edges. It modifies only metadata present in the 'updates'
	// subset. This function has an internal test.
	func breakImportCycles(metadata, updates map[PackageID]*Package) {
	// 'go list' should never report a cycle without flagging it
	// as such, but we're extra cautious since we're combining
	// information from multiple runs of 'go list'. Also, Bazel
	// may silently report cycles.
	cycles := detectImportCycles(metadata, updates)
	if len(cycles) > 0 {
	// There were cycles (uncommon). Break them.
	//
	// The naive way to break cycles would be to perform a
	// depth-first traversal and to detect and delete
	// cycle-forming edges as we encounter them.
	// However, we're not allowed to modify the existing
	// Metadata records, so we can only break edges out of
	// the 'updates' subset.
	//
	// Another possibility would be to delete not the
	// cycle forming edge but the topmost edge on the
	// stack whose tail is an updated node.
	// However, this would require that we retroactively
	// undo all the effects of the traversals that
	// occurred since that edge was pushed on the stack.
	//
	// We use a simpler scheme: we compute the set of cycles.
	// All cyclic paths necessarily involve at least one
	// updated node, so it is sufficient to break all
	// edges from each updated node to other members of
	// the strong component.
	//
	// This may result in the deletion of dominating
	// edges, causing some dependencies to appear
	// spuriously unreachable. Consider A <-> B -> C
	// where updates={A,B}. The cycle is {A,B} so the
	// algorithm will break both A->B and B->A, causing
	// A to no longer depend on B or C.
	//
	// But that's ok: any error in Metadata.Errors is
	// conservatively assumed by snapshot.clone to be a
	// potential import cycle error, and causes special
	// invalidation so that if B later drops its
	// cycle-forming import of A, both A and B will be
	// invalidated.
	for _, cycle := range cycles {
	cyclic := make(map[PackageID]bool)
	for _, mp := range cycle {
	cyclic[mp.ID] = true
	}
	for id := range cyclic {
	if mp := updates[id]; mp != nil {
	for path, depID := range mp.DepsByImpPath {
	if cyclic[depID] {
	delete(mp.DepsByImpPath, path)
	}
	}
	for path, depID := range mp.DepsByPkgPath {
	if cyclic[depID] {
	delete(mp.DepsByPkgPath, path)
	}
	}

	// Set m.Errors to enable special
	// invalidation logic in snapshot.clone.
	if len(mp.Errors) == 0 {
	mp.Errors = []packages.Error{{
	Msg: "detected import cycle",
	Kind: packages.ListError,
	}}
	}
	}
	}
	}

	// double-check when debugging
	if false {
	if cycles := detectImportCycles(metadata, updates); len(cycles) > 0 {
	bug.Reportf("unbroken cycle: %v", cycles)
	}
	}
	}
	}

	// cyclic returns a description of a cycle,
	// if the graph is cyclic, otherwise "".
	func cyclic(graph map[PackageID]*Package) string {
	const (
	unvisited = 0
	visited = 1
	onstack = 2
	)
	color := make(map[PackageID]int)
	var visit func(id PackageID) string
	visit = func(id PackageID) string {
	switch color[id] {
	case unvisited:
	color[id] = onstack
	case onstack:
	return string(id) // cycle!
	case visited:
	return ""
	}
	if mp := graph[id]; mp != nil {
	for _, depID := range mp.DepsByPkgPath {
	if cycle := visit(depID); cycle != "" {
	return string(id) + "->" + cycle
	}
	}
	}
	color[id] = visited
	return ""
	}
	for id := range graph {
	if cycle := visit(id); cycle != "" {
	return cycle
	}
	}
	return ""
	}

	// detectImportCycles reports cycles in the metadata graph. It returns a new
	// unordered array of all cycles (nontrivial strong components) in the
	// metadata graph reachable from a non-nil 'updates' value.
	func detectImportCycles(metadata, updates map[PackageID]Package) [][]Package {
	// We use the depth-first algorithm of Tarjan.
	// https://doi.org/10.1137/0201010
	//
	// TODO(adonovan): when we can use generics, consider factoring
	// in common with the other implementation of Tarjan (in typerefs),
	// abstracting over the node and edge representation.

	// A node wraps a Metadata with its working state.
	// (Unfortunately we can't intrude on shared Metadata.)
	type node struct {
	rep *node
	mp *Package
	index, lowlink int32
	scc int8 // TODO(adonovan): opt: cram these 1.5 bits into previous word
	}
	nodes := make(map[PackageID]*node, len(metadata))
	nodeOf := func(id PackageID) *node {
	n, ok := nodes[id]
	if !ok {
	mp := metadata[id]
	if mp == nil {
	// Dangling import edge.
	// Not sure whether a go/packages driver ever
	// emits this, but create a dummy node in case.
	// Obviously it won't be part of any cycle.
	mp = &Package{ID: id}
	}
	n = &node{mp: mp}
	n.rep = n
	nodes[id] = n
	}
	return n
	}

	// find returns the canonical node decl.
	// (The nodes form a disjoint set forest.)
	var find func(node) node
	find = func(n node) node {
	rep := n.rep
	if rep != n {
	rep = find(rep)
	n.rep = rep // simple path compression (no union-by-rank)
	}
	return rep
	}

	// global state
	var (
	index int32 = 1
	stack []*node
	sccs [][]*Package // set of nontrivial strongly connected components
	)

	// visit implements the depth-first search of Tarjan's SCC algorithm
	// Precondition: x is canonical.
	var visit func(*node)
	visit = func(x *node) {
	x.index = index
	x.lowlink = index
	index++

	stack = append(stack, x) // push
	x.scc = -1

	for _, yid := range x.mp.DepsByPkgPath {
	y := nodeOf(yid)
	// Loop invariant: x is canonical.
	y = find(y)
	if x == y {
	continue // nodes already combined (self-edges are impossible)
	}

	switch {
	case y.scc > 0:
	// y is already a collapsed SCC

	case y.scc < 0:
	// y is on the stack, and thus in the current SCC.
	if y.index < x.lowlink {
	x.lowlink = y.index
	}

	default:
	// y is unvisited; visit it now.
	visit(y)
	// Note: x and y are now non-canonical.
	x = find(x)
	if y.lowlink < x.lowlink {
	x.lowlink = y.lowlink
	}
	}
	}

	// Is x the root of an SCC?
	if x.lowlink == x.index {
	// Gather all metadata in the SCC (if nontrivial).
	var scc []*Package
	for {
	// Pop y from stack.
	i := len(stack) - 1
	y := stack[i]
	stack = stack[:i]
	if x != y \|\| scc != nil {
	scc = append(scc, y.mp)
	}
	if x == y {
	break // complete
	}
	// x becomes y's canonical representative.
	y.rep = x
	}
	if scc != nil {
	sccs = append(sccs, scc)
	}
	x.scc = 1
	}
	}

	// Visit only the updated nodes:
	// the existing metadata graph has no cycles,
	// so any new cycle must involve an updated node.
	for id, mp := range updates {
	if mp != nil {
	if n := nodeOf(id); n.index == 0 { // unvisited
	visit(n)
	}
	}
	}

	return sccs
	}