gopls/internal/lsp/source/typerefs/pkgrefs.go

// Copyright 2023 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 typerefs

import (
	"context"
	"go/token"
	"runtime"
	"sync"

	"golang.org/x/sync/errgroup"
	"golang.org/x/tools/gopls/internal/lsp/source"
	"golang.org/x/tools/gopls/internal/span"
)

const (
	// trace enables additional trace output to stdout, for debugging.
	//
	// Warning: produces a lot of output! Best to run with small package queries.
	trace = false
)

// A Package holds reference information for a single package.
type Package struct {
	idx packageIdx // memoized index of this package's ID, to save map lookups

	// Metadata holds metadata about this package and its dependencies.
	Metadata *source.Metadata

	// Refs records syntactic edges between declarations in this package and
	// declarations in this package or another package. See the package
	// documentation for a detailed description of what these edges do (and do
	// not) represent.
	Refs map[string][]Ref

	// TransitiveRefs records, for each declaration in the package, the
	// transitive set of packages within the containing graph that are
	// transitively reachable through references, starting with the given decl.
	TransitiveRefs map[string]*PackageSet

	// ReachesViaDeps records the set of packages in the containing graph whose
	// syntax may affect the current package's types. See the package
	// documentation for more details of what this means.
	ReachesByDeps *PackageSet
}

// A Ref is a referenced declaration.
//
// Unpack it using the Unpack method, with the PackageIndex instance that was
// used to construct the references.
type Ref struct {
	pkg  packageIdx
	name string
}

// UnpackRef unpacks the actual PackageID an name encoded in ref.
func (r Ref) Unpack(index *PackageIndex) (PackageID source.PackageID, name string) {
	return index.id(r.pkg), r.name
}

// A PackageGraph represents a fully analyzed graph of packages and their
// dependencies.
type PackageGraph struct {
	pkgIndex *PackageIndex
	meta     source.MetadataSource
	parse    func(context.Context, span.URI) (*source.ParsedGoFile, error)

	mu       sync.Mutex
	packages map[source.PackageID]*futurePackage
}

// BuildPackageGraph analyzes the package graph for the requested ids, whose
// metadata is described by meta.
//
// The provided parse function is used to parse the CompiledGoFiles of each package.
//
// The resulting PackageGraph is fully evaluated, and may be investigated using
// the Package method.
//
// See the package documentation for more information on the package reference
// algorithm.
func BuildPackageGraph(ctx context.Context, meta source.MetadataSource, ids []source.PackageID, parse func(context.Context, span.URI) (*source.ParsedGoFile, error)) (*PackageGraph, error) {
	g := &PackageGraph{
		pkgIndex: NewPackageIndex(),
		meta:     meta,
		parse:    parse,
		packages: make(map[source.PackageID]*futurePackage),
	}
	source.SortPostOrder(meta, ids)

	workers := runtime.GOMAXPROCS(0)
	if trace {
		workers = 1
	}

	var eg errgroup.Group
	eg.SetLimit(workers)
	for _, id := range ids {
		id := id
		eg.Go(func() error {
			_, err := g.Package(ctx, id)
			return err
		})
	}
	return g, eg.Wait()
}

// futurePackage is a future result of analyzing a package, for use from Package only.
type futurePackage struct {
	done chan struct{}
	pkg  *Package
	err  error
}

// Package gets the result of analyzing references for a single package.
func (g *PackageGraph) Package(ctx context.Context, id source.PackageID) (*Package, error) {
	g.mu.Lock()
	fut, ok := g.packages[id]
	if ok {
		g.mu.Unlock()
		select {
		case <-fut.done:
		case <-ctx.Done():
			return nil, ctx.Err()
		}
	} else {
		fut = &futurePackage{done: make(chan struct{})}
		g.packages[id] = fut
		g.mu.Unlock()
		fut.pkg, fut.err = g.buildPackage(ctx, id)
		close(fut.done)
	}
	return fut.pkg, fut.err
}

// buildPackage parses a package and extracts its reference graph. It should
// only be called from Package.
func (g *PackageGraph) buildPackage(ctx context.Context, id source.PackageID) (*Package, error) {
	p := &Package{
		idx:            g.pkgIndex.idx(id),
		Metadata:       g.meta.Metadata(id),
		Refs:           make(map[string][]Ref),
		TransitiveRefs: make(map[string]*PackageSet),
	}
	var files []*source.ParsedGoFile
	for _, filename := range p.Metadata.CompiledGoFiles {
		f, err := g.parse(ctx, filename)
		if err != nil {
			return nil, err
		}
		files = append(files, f)
	}
	imports := make(map[source.ImportPath]*source.Metadata)
	for impPath, depID := range p.Metadata.DepsByImpPath {
		if depID != "" {
			imports[impPath] = g.meta.Metadata(depID)
		}
	}
	p.Refs = Refs(files, id, imports, g.pkgIndex)

	// Compute packages reachable from each exported symbol of this package.
	for name := range p.Refs {
		if token.IsExported(name) {
			set := g.pkgIndex.New()
			g.reachableByName(ctx, p, name, set, make(map[string]bool))
			p.TransitiveRefs[name] = set
		}
	}

	var err error
	p.ReachesByDeps, err = g.reachesByDeps(ctx, p.Metadata)
	if err != nil {
		return nil, err
	}
	return p, nil
}

// ExternalRefs returns a new map whose keys are the exported symbols
// of the package (of the specified id, pkgIndex, and refs). The
// corresponding value of each key is the set of exported symbols
// indirectly referenced by it.
//
// TODO(adonovan): simplify the API once the SCC-based optimization lands.
func ExternalRefs(pkgIndex *PackageIndex, id source.PackageID, refs map[string][]Ref) map[string]map[Ref]bool {
	// (This intrapackage recursion will go away in a follow-up CL.)
	var visit func(name string, res map[Ref]bool, seen map[string]bool)
	visit = func(name string, res map[Ref]bool, seen map[string]bool) {
		if !seen[name] {
			seen[name] = true
			for _, ref := range refs[name] {
				if pkgIndex.id(ref.pkg) == id {
					visit(ref.name, res, seen) // intrapackage recursion
				} else {
					res[ref] = true // cross-package ref
				}
			}
		}
	}

	results := make(map[string]map[Ref]bool)
	for name := range refs {
		if token.IsExported(name) {
			res := make(map[Ref]bool)
			seen := make(map[string]bool)
			visit(name, res, seen)
			results[name] = res
		}
	}
	return results
}

// reachableByName computes the set of packages that are reachable through
// references, starting with the declaration for name in package p.
func (g *PackageGraph) reachableByName(ctx context.Context, p *Package, name string, set *PackageSet, seen map[string]bool) error {
	if seen[name] {
		return nil
	}
	seen[name] = true

	// Opt: when we compact reachable edges inside the Refs algorithm, we handle
	// all edges to a given package in a batch, so they should be adjacent to
	// each other in the resulting slice. Therefore remembering the last P here
	// can save on lookups.
	depP := p
	for _, node := range p.Refs[name] {
		if node.pkg == p.idx {
			// same package
			g.reachableByName(ctx, p, node.name, set, seen)
		} else {
			// cross-package ref
			if depP.idx != node.pkg {
				id := g.pkgIndex.id(node.pkg)
				var err error
				depP, err = g.Package(ctx, id)
				if err != nil {
					return err
				}
			}
			set.add(node.pkg)
			set.Union(depP.TransitiveRefs[node.name])
		}
	}

	return nil
}

// reachesByDeps computes the set of packages that are reachable through
// dependencies of the package m.
func (g *PackageGraph) reachesByDeps(ctx context.Context, m *source.Metadata) (*PackageSet, error) {
	transitive := g.pkgIndex.New()
	for _, depID := range m.DepsByPkgPath {
		dep, err := g.Package(ctx, depID)
		if err != nil {
			return nil, err
		}
		transitive.add(dep.idx)
		for name, set := range dep.TransitiveRefs {
			if token.IsExported(name) {
				transitive.Union(set)
			}
		}
	}
	return transitive, nil
}