blob: 1a01eb98a85b6231b53b917b2bae11dbe8eac372 [file] [log] [blame]
// Copyright 2019 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 source
// This file defines a new implementation of the 'references' query
// based on a serializable (and eventually file-based) index
// constructed during type checking, thus avoiding the need to
// type-check packages at search time. In due course it will replace
// the old implementation, which is also used by renaming.
//
// See the ./xrefs/ subpackage for the index construction and lookup.
//
// This implementation does not intermingle objects from distinct
// calls to TypeCheck.
import (
"context"
"fmt"
"go/ast"
"go/token"
"go/types"
"sort"
"strings"
"sync"
"golang.org/x/sync/errgroup"
"golang.org/x/tools/go/types/objectpath"
"golang.org/x/tools/gopls/internal/lsp/protocol"
"golang.org/x/tools/gopls/internal/lsp/safetoken"
"golang.org/x/tools/gopls/internal/lsp/source/methodsets"
"golang.org/x/tools/gopls/internal/span"
"golang.org/x/tools/internal/bug"
"golang.org/x/tools/internal/event"
)
// A ReferenceInfoV2 describes an identifier that refers to the same
// object as the subject of a References query.
type ReferenceInfoV2 struct {
IsDeclaration bool
Location protocol.Location
// TODO(adonovan): these are the same for all elements; factor out of the slice.
// TODO(adonovan): Name is currently unused. If it's still unused when we
// eliminate 'references' (v1), delete it. Or replace both fields by a *Metadata.
PkgPath PackagePath
Name string
}
// References returns a list of all references (sorted with
// definitions before uses) to the object denoted by the identifier at
// the given file/position, searching the entire workspace.
func References(ctx context.Context, snapshot Snapshot, fh FileHandle, pp protocol.Position, includeDeclaration bool) ([]protocol.Location, error) {
references, err := referencesV2(ctx, snapshot, fh, pp, includeDeclaration)
if err != nil {
return nil, err
}
locations := make([]protocol.Location, len(references))
for i, ref := range references {
locations[i] = ref.Location
}
return locations, nil
}
// referencesV2 returns a list of all references (sorted with
// definitions before uses) to the object denoted by the identifier at
// the given file/position, searching the entire workspace.
func referencesV2(ctx context.Context, snapshot Snapshot, f FileHandle, pp protocol.Position, includeDeclaration bool) ([]*ReferenceInfoV2, error) {
ctx, done := event.Start(ctx, "source.References2")
defer done()
// Is the cursor within the package name declaration?
_, inPackageName, err := parsePackageNameDecl(ctx, snapshot, f, pp)
if err != nil {
return nil, err
}
var refs []*ReferenceInfoV2
if inPackageName {
refs, err = packageReferences(ctx, snapshot, f.URI())
} else {
refs, err = ordinaryReferences(ctx, snapshot, f.URI(), pp)
}
if err != nil {
return nil, err
}
sort.Slice(refs, func(i, j int) bool {
x, y := refs[i], refs[j]
if x.IsDeclaration != y.IsDeclaration {
return x.IsDeclaration // decls < refs
}
return protocol.CompareLocation(x.Location, y.Location) < 0
})
// De-duplicate by location, and optionally remove declarations.
out := refs[:0]
for _, ref := range refs {
if !includeDeclaration && ref.IsDeclaration {
continue
}
if len(out) == 0 || out[len(out)-1].Location != ref.Location {
out = append(out, ref)
}
}
refs = out
return refs, nil
}
// packageReferences returns a list of references to the package
// declaration of the specified name and uri by searching among the
// import declarations of all packages that directly import the target
// package.
func packageReferences(ctx context.Context, snapshot Snapshot, uri span.URI) ([]*ReferenceInfoV2, error) {
metas, err := snapshot.MetadataForFile(ctx, uri)
if err != nil {
return nil, err
}
if len(metas) == 0 {
return nil, fmt.Errorf("found no package containing %s", uri)
}
var refs []*ReferenceInfoV2
// Find external references to the package declaration
// from each direct import of the package.
//
// The narrowest package is the most broadly imported,
// so we choose it for the external references.
//
// But if the file ends with _test.go then we need to
// find the package it is testing; there's no direct way
// to do that, so pick a file from the same package that
// doesn't end in _test.go and start over.
narrowest := metas[0]
if narrowest.ForTest != "" && strings.HasSuffix(string(uri), "_test.go") {
for _, f := range narrowest.CompiledGoFiles {
if !strings.HasSuffix(string(f), "_test.go") {
return packageReferences(ctx, snapshot, f)
}
}
// This package has no non-test files.
// Skip the search for external references.
// (Conceivably one could blank-import an empty package, but why?)
} else {
rdeps, err := snapshot.ReverseDependencies(ctx, narrowest.ID, false) // direct
if err != nil {
return nil, err
}
for _, rdep := range rdeps {
for _, uri := range rdep.CompiledGoFiles {
fh, err := snapshot.GetFile(ctx, uri)
if err != nil {
return nil, err
}
f, err := snapshot.ParseGo(ctx, fh, ParseHeader)
if err != nil {
return nil, err
}
for _, imp := range f.File.Imports {
if rdep.DepsByImpPath[UnquoteImportPath(imp)] == narrowest.ID {
refs = append(refs, &ReferenceInfoV2{
IsDeclaration: false,
Location: mustLocation(f, imp),
PkgPath: narrowest.PkgPath,
Name: string(narrowest.Name),
})
}
}
}
}
}
// Find internal "references" to the package from
// of each package declaration in the target package itself.
//
// The widest package (possibly a test variant) has the
// greatest number of files and thus we choose it for the
// "internal" references.
widest := metas[len(metas)-1]
for _, uri := range widest.CompiledGoFiles {
fh, err := snapshot.GetFile(ctx, uri)
if err != nil {
return nil, err
}
f, err := snapshot.ParseGo(ctx, fh, ParseHeader)
if err != nil {
return nil, err
}
refs = append(refs, &ReferenceInfoV2{
IsDeclaration: true, // (one of many)
Location: mustLocation(f, f.File.Name),
PkgPath: widest.PkgPath,
Name: string(widest.Name),
})
}
return refs, nil
}
// ordinaryReferences computes references for all ordinary objects (not package declarations).
func ordinaryReferences(ctx context.Context, snapshot Snapshot, uri span.URI, pp protocol.Position) ([]*ReferenceInfoV2, error) {
// Strategy: use the reference information computed by the
// type checker to find the declaration. First type-check this
// package to find the declaration, then type check the
// declaring package (which may be different), plus variants,
// to find local (in-package) references.
// Global references are satisfied by the index.
// Strictly speaking, a wider package could provide a different
// declaration (e.g. because the _test.go files can change the
// meaning of a field or method selection), but the narrower
// package reports the more broadly referenced object.
pkg, pgf, err := PackageForFile(ctx, snapshot, uri, TypecheckFull, NarrowestPackage)
if err != nil {
return nil, err
}
// Find the selected object (declaration or reference).
pos, err := pgf.PositionPos(pp)
if err != nil {
return nil, err
}
candidates, err := objectsAt(pkg.GetTypesInfo(), pgf.File, pos)
if err != nil {
return nil, err
}
// Pick first object arbitrarily.
// The case variables of a type switch have different
// types but that difference is immaterial here.
var obj types.Object
for obj = range candidates {
break
}
if obj == nil {
return nil, ErrNoIdentFound // can't happen
}
// nil, error, error.Error, iota, or other built-in?
if obj.Pkg() == nil {
// For some reason, existing tests require that iota has no references,
// nor an error. TODO(adonovan): do something more principled.
if obj.Name() == "iota" {
return nil, nil
}
return nil, fmt.Errorf("references to builtin %q are not supported", obj.Name())
}
// Find metadata of all packages containing the object's defining file.
// This may include the query pkg, and possibly other variants.
declPosn := safetoken.StartPosition(pkg.FileSet(), obj.Pos())
declURI := span.URIFromPath(declPosn.Filename)
variants, err := snapshot.MetadataForFile(ctx, declURI)
if err != nil {
return nil, err
}
if len(variants) == 0 {
return nil, fmt.Errorf("no packages for file %q", declURI) // can't happen
}
// Is object exported?
// If so, compute scope and targets of the global search.
var (
globalScope = make(map[PackageID]*Metadata)
globalTargets map[PackagePath]map[objectpath.Path]unit
)
// TODO(adonovan): what about generic functions. Need to consider both
// uninstantiated and instantiated. The latter have no objectpath. Use Origin?
if path, err := objectpath.For(obj); err == nil && obj.Exported() {
pkgPath := variants[0].PkgPath // (all variants have same package path)
globalTargets = map[PackagePath]map[objectpath.Path]unit{
pkgPath: {path: {}}, // primary target
}
// How far need we search?
// For package-level objects, we need only search the direct importers.
// For fields and methods, we must search transitively.
transitive := obj.Pkg().Scope().Lookup(obj.Name()) != obj
// The scope is the union of rdeps of each variant.
// (Each set is disjoint so there's no benefit to
// to combining the metadata graph traversals.)
for _, m := range variants {
rdeps, err := snapshot.ReverseDependencies(ctx, m.ID, transitive)
if err != nil {
return nil, err
}
for id, rdep := range rdeps {
globalScope[id] = rdep
}
}
// Is object a method?
//
// If so, expand the search so that the targets include
// all methods that correspond to it through interface
// satisfaction, and the scope includes the rdeps of
// the package that declares each corresponding type.
if recv := effectiveReceiver(obj); recv != nil {
if err := expandMethodSearch(ctx, snapshot, obj.(*types.Func), recv, globalScope, globalTargets); err != nil {
return nil, err
}
}
}
// The search functions will call report(loc) for each hit.
var (
refsMu sync.Mutex
refs []*ReferenceInfoV2
)
report := func(loc protocol.Location, isDecl bool) {
ref := &ReferenceInfoV2{
IsDeclaration: isDecl,
Location: loc,
PkgPath: pkg.Metadata().PkgPath,
Name: obj.Name(),
}
refsMu.Lock()
refs = append(refs, ref)
refsMu.Unlock()
}
// Loop over the variants of the declaring package,
// and perform both the local (in-package) and global
// (cross-package) searches, in parallel.
//
// TODO(adonovan): opt: support LSP reference streaming. See:
// - https://github.com/microsoft/vscode-languageserver-node/pull/164
// - https://github.com/microsoft/language-server-protocol/pull/182
//
// Careful: this goroutine must not return before group.Wait.
var group errgroup.Group
// Compute local references for each variant.
for _, m := range variants {
// We want the ordinary importable package,
// plus any test-augmented variants, since
// declarations in _test.go files may change
// the reference of a selection, or even a
// field into a method or vice versa.
//
// But we don't need intermediate test variants,
// as their local references will be covered
// already by other variants.
if m.IsIntermediateTestVariant() {
continue
}
m := m
group.Go(func() error {
return localReferences(ctx, snapshot, declURI, declPosn.Offset, m, report)
})
}
// Compute global references for selected reverse dependencies.
for _, m := range globalScope {
m := m
group.Go(func() error {
return globalReferences(ctx, snapshot, m, globalTargets, report)
})
}
if err := group.Wait(); err != nil {
return nil, err
}
return refs, nil
}
// expandMethodSearch expands the scope and targets of a global search
// for an exported method to include all methods that correspond to
// it through interface satisfaction.
//
// recv is the method's effective receiver type, for method-set computations.
func expandMethodSearch(ctx context.Context, snapshot Snapshot, method *types.Func, recv types.Type, scope map[PackageID]*Metadata, targets map[PackagePath]map[objectpath.Path]unit) error {
// Compute the method-set fingerprint used as a key to the global search.
key, hasMethods := methodsets.KeyOf(recv)
if !hasMethods {
return bug.Errorf("KeyOf(%s)={} yet %s is a method", recv, method)
}
metas, err := snapshot.AllMetadata(ctx)
if err != nil {
return err
}
allIDs := make([]PackageID, 0, len(metas))
for _, m := range metas {
allIDs = append(allIDs, m.ID)
}
// Search the methodset index of each package in the workspace.
allPkgs, err := snapshot.TypeCheck(ctx, TypecheckFull, allIDs...)
if err != nil {
return err
}
var group errgroup.Group
for _, pkg := range allPkgs {
pkg := pkg
group.Go(func() error {
// Consult index for matching methods.
results := pkg.MethodSetsIndex().Search(key, method.Name())
// Expand global search scope to include rdeps of this pkg.
if len(results) > 0 {
rdeps, err := snapshot.ReverseDependencies(ctx, pkg.Metadata().ID, true)
if err != nil {
return err
}
for _, rdep := range rdeps {
scope[rdep.ID] = rdep
}
}
// Add each corresponding method the to set of global search targets.
for _, res := range results {
methodPkg := PackagePath(res.PkgPath)
opaths, ok := targets[methodPkg]
if !ok {
opaths = make(map[objectpath.Path]unit)
targets[methodPkg] = opaths
}
opaths[res.ObjectPath] = unit{}
}
return nil
})
}
return group.Wait()
}
// localReferences reports each reference to the object
// declared at the specified URI/offset within its enclosing package m.
func localReferences(ctx context.Context, snapshot Snapshot, declURI span.URI, declOffset int, m *Metadata, report func(loc protocol.Location, isDecl bool)) error {
pkgs, err := snapshot.TypeCheck(ctx, TypecheckFull, m.ID)
if err != nil {
return err
}
pkg := pkgs[0] // narrowest
// Find declaration of corresponding object
// in this package based on (URI, offset).
pgf, err := pkg.File(declURI)
if err != nil {
return err
}
pos, err := safetoken.Pos(pgf.Tok, declOffset)
if err != nil {
return err
}
targets, err := objectsAt(pkg.GetTypesInfo(), pgf.File, pos)
if err != nil {
return err // unreachable? (probably caught earlier)
}
// Report the locations of the declaration(s).
// TODO(adonovan): what about for corresponding methods? Add tests.
for _, node := range targets {
report(mustLocation(pgf, node), true)
}
// If we're searching for references to a method, broaden the
// search to include references to corresponding methods of
// mutually assignable receiver types.
// (We use a slice, but objectsAt never returns >1 methods.)
var methodRecvs []types.Type
var methodName string // name of an arbitrary target, iff a method
for obj := range targets {
if t := effectiveReceiver(obj); t != nil {
methodRecvs = append(methodRecvs, t)
methodName = obj.Name()
}
}
// matches reports whether obj either is or corresponds to a target.
// (Correspondence is defined as usual for interface methods.)
matches := func(obj types.Object) bool {
if targets[obj] != nil {
return true
} else if methodRecvs != nil && obj.Name() == methodName {
if orecv := effectiveReceiver(obj); orecv != nil {
for _, mrecv := range methodRecvs {
if concreteImplementsIntf(orecv, mrecv) {
return true
}
}
}
}
return false
}
// Scan through syntax looking for uses of one of the target objects.
for _, pgf := range pkg.CompiledGoFiles() {
ast.Inspect(pgf.File, func(n ast.Node) bool {
if id, ok := n.(*ast.Ident); ok {
if obj, ok := pkg.GetTypesInfo().Uses[id]; ok && matches(obj) {
report(mustLocation(pgf, id), false)
}
}
return true
})
}
return nil
}
// effectiveReceiver returns the effective receiver type for method-set
// comparisons for obj, if it is a method, or nil otherwise.
func effectiveReceiver(obj types.Object) types.Type {
if fn, ok := obj.(*types.Func); ok {
if recv := fn.Type().(*types.Signature).Recv(); recv != nil {
return methodsets.EnsurePointer(recv.Type())
}
}
return nil
}
// objectsAt returns the non-empty set of objects denoted (def or use)
// by the specified position within a file syntax tree, or an error if
// none were found.
//
// The result may contain more than one element because all case
// variables of a type switch appear to be declared at the same
// position.
//
// Each object is mapped to the syntax node that was treated as an
// identifier, which is not always an ast.Ident.
func objectsAt(info *types.Info, file *ast.File, pos token.Pos) (map[types.Object]ast.Node, error) {
path := pathEnclosingObjNode(file, pos)
if path == nil {
return nil, ErrNoIdentFound
}
targets := make(map[types.Object]ast.Node)
switch leaf := path[0].(type) {
case *ast.Ident:
// If leaf represents an implicit type switch object or the type
// switch "assign" variable, expand to all of the type switch's
// implicit objects.
if implicits, _ := typeSwitchImplicits(info, path); len(implicits) > 0 {
for _, obj := range implicits {
targets[obj] = leaf
}
} else {
obj := info.ObjectOf(leaf)
if obj == nil {
return nil, fmt.Errorf("%w for %q", errNoObjectFound, leaf.Name)
}
targets[obj] = leaf
}
case *ast.ImportSpec:
// Look up the implicit *types.PkgName.
obj := info.Implicits[leaf]
if obj == nil {
return nil, fmt.Errorf("%w for import %s", errNoObjectFound, UnquoteImportPath(leaf))
}
targets[obj] = leaf
}
if len(targets) == 0 {
return nil, fmt.Errorf("objectAt: internal error: no targets") // can't happen
}
return targets, nil
}
// globalReferences reports each cross-package reference to one of the
// target objects denoted by (package path, object path).
func globalReferences(ctx context.Context, snapshot Snapshot, m *Metadata, targets map[PackagePath]map[objectpath.Path]unit, report func(loc protocol.Location, isDecl bool)) error {
// TODO(adonovan): opt: don't actually type-check here,
// since we quite intentionally don't look at type information.
// Instead, access the reference index computed during
// type checking that will in due course be a file-based cache.
pkgs, err := snapshot.TypeCheck(ctx, TypecheckFull, m.ID)
if err != nil {
return err
}
for _, loc := range pkgs[0].ReferencesTo(targets) {
report(loc, false)
}
return nil
}
// mustLocation reports the location interval a syntax node,
// which must belong to m.File.
//
// Safe for use only by references2 and implementations2.
func mustLocation(pgf *ParsedGoFile, n ast.Node) protocol.Location {
loc, err := pgf.PosLocation(n.Pos(), n.End())
if err != nil {
panic(err) // can't happen in references2 or implementations2
}
return loc
}