blob: be29973ae8c7fe0d70a2a08663421f9f006c84b5 [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
import (
"context"
"errors"
"fmt"
"go/ast"
"go/token"
"go/types"
"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/event"
)
var ErrNotAType = errors.New("not a type name or method")
// implementations returns the concrete implementations of the specified
// interface, or the interfaces implemented by the specified concrete type.
// It populates only the definition-related fields of qualifiedObject.
// (Arguably it should return a smaller data type.)
//
// This is the legacy implementation using the type-check-the-world
// strategy. It is still needed by the 'references' command for now,
// but we are moving one step at a time. See implementation2.go for
// the incremental algorithm used by the 'implementations' command.
// TODO(adonovan): eliminate this implementation.
func implementations(ctx context.Context, s Snapshot, f FileHandle, pp protocol.Position) ([]qualifiedObject, error) {
// Find all named types, even local types
// (which can have methods due to promotion).
var (
allNamed []*types.Named
pkgs = make(map[*types.Package]Package)
)
metas, err := s.AllMetadata(ctx)
if err != nil {
return nil, err
}
ids := make([]PackageID, len(metas))
for i, m := range metas {
ids[i] = m.ID
}
packages, err := s.TypeCheck(ctx, TypecheckFull, ids...)
if err != nil {
return nil, err
}
for _, pkg := range packages {
pkgs[pkg.GetTypes()] = pkg
for _, obj := range pkg.GetTypesInfo().Defs {
obj, ok := obj.(*types.TypeName)
// We ignore aliases 'type M = N' to avoid duplicate reporting
// of the Named type N.
if !ok || obj.IsAlias() {
continue
}
if named, ok := obj.Type().(*types.Named); ok {
allNamed = append(allNamed, named)
}
}
}
qos, err := qualifiedObjsAtProtocolPos(ctx, s, f.URI(), pp)
if err != nil {
return nil, err
}
var (
impls []qualifiedObject
seen = make(map[token.Position]bool)
)
for _, qo := range qos {
// Ascertain the query identifier (type or method).
var (
queryType types.Type
queryMethod *types.Func
)
switch obj := qo.obj.(type) {
case *types.Func:
queryMethod = obj
if recv := obj.Type().(*types.Signature).Recv(); recv != nil {
queryType = methodsets.EnsurePointer(recv.Type())
}
case *types.TypeName:
queryType = methodsets.EnsurePointer(obj.Type())
}
if queryType == nil {
return nil, ErrNotAType
}
if types.NewMethodSet(queryType).Len() == 0 {
return nil, nil
}
// Find all the named types that match our query.
for _, named := range allNamed {
var (
candObj types.Object = named.Obj()
candType = methodsets.EnsurePointer(named)
)
if !concreteImplementsIntf(candType, queryType) {
continue
}
ms := types.NewMethodSet(candType)
if ms.Len() == 0 {
// Skip empty interfaces.
continue
}
// If client queried a method, look up corresponding candType method.
if queryMethod != nil {
sel := ms.Lookup(queryMethod.Pkg(), queryMethod.Name())
if sel == nil {
continue
}
candObj = sel.Obj()
}
pos := safetoken.StartPosition(s.FileSet(), candObj.Pos())
if candObj == queryMethod || seen[pos] {
continue
}
pkg := pkgs[candObj.Pkg()] // may be nil (e.g. error)
// TODO(adonovan): the logic below assumes there is only one
// predeclared (pkg=nil) object of interest, the error type.
// That could change in a future version of Go.
var posn token.Position
if pkg != nil {
posn = safetoken.StartPosition(pkg.FileSet(), candObj.Pos())
}
if seen[posn] {
continue
}
seen[posn] = true
impls = append(impls, qualifiedObject{
obj: candObj,
pkg: pkg,
})
}
}
return impls, nil
}
// concreteImplementsIntf returns true if a is an interface type implemented by
// concrete type b, or vice versa.
func concreteImplementsIntf(a, b types.Type) bool {
aIsIntf, bIsIntf := types.IsInterface(a), types.IsInterface(b)
// Make sure exactly one is an interface type.
if aIsIntf == bIsIntf {
return false
}
// Rearrange if needed so "a" is the concrete type.
if aIsIntf {
a, b = b, a
}
// TODO(adonovan): this should really use GenericAssignableTo
// to report (e.g.) "ArrayList[T] implements List[T]", but
// GenericAssignableTo doesn't work correctly on pointers to
// generic named types. Thus the legacy implementation and the
// "local" part of implementation2 fail to report generics.
// The global algorithm based on subsets does the right thing.
return types.AssignableTo(a, b)
}
// A qualifiedObject is the result of resolving a reference from an
// identifier to an object.
type qualifiedObject struct {
// definition
obj types.Object // the referenced object
pkg Package // the Package that defines the object (nil => universe)
// reference (optional)
node ast.Node // the reference (*ast.Ident or *ast.ImportSpec) to the object
sourcePkg Package // the Package containing node
}
var (
errBuiltin = errors.New("builtin object")
errNoObjectFound = errors.New("no object found")
)
// qualifiedObjsAtProtocolPos returns info for all the types.Objects referenced
// at the given position, for the following selection of packages:
//
// 1. all packages (including all test variants), in their workspace parse mode
// 2. if not included above, at least one package containing uri in full parse mode
//
// Finding objects in (1) ensures that we locate references within all
// workspace packages, including in x_test packages. Including (2) ensures that
// we find local references in the current package, for non-workspace packages
// that may be open.
func qualifiedObjsAtProtocolPos(ctx context.Context, s Snapshot, uri span.URI, pp protocol.Position) ([]qualifiedObject, error) {
fh, err := s.GetFile(ctx, uri)
if err != nil {
return nil, err
}
content, err := fh.Read()
if err != nil {
return nil, err
}
m := protocol.NewMapper(uri, content)
offset, err := m.PositionOffset(pp)
if err != nil {
return nil, err
}
return qualifiedObjsAtLocation(ctx, s, positionKey{uri, offset}, map[positionKey]bool{})
}
// A positionKey identifies a byte offset within a file (URI).
//
// When a file has been parsed multiple times in the same FileSet,
// there may be multiple token.Pos values denoting the same logical
// position. In such situations, a positionKey may be used for
// de-duplication.
type positionKey struct {
uri span.URI
offset int
}
// qualifiedObjsAtLocation finds all objects referenced at offset in uri,
// across all packages in the snapshot.
func qualifiedObjsAtLocation(ctx context.Context, s Snapshot, key positionKey, seen map[positionKey]bool) ([]qualifiedObject, error) {
if seen[key] {
return nil, nil
}
seen[key] = true
// We search for referenced objects starting with all packages containing the
// current location, and then repeating the search for every distinct object
// location discovered.
//
// In the common case, there should be at most one additional location to
// consider: the definition of the object referenced by the location. But we
// try to be comprehensive in case we ever support variations on build
// constraints.
metas, err := s.MetadataForFile(ctx, key.uri)
if err != nil {
return nil, err
}
ids := make([]PackageID, len(metas))
for i, m := range metas {
ids[i] = m.ID
}
pkgs, err := s.TypeCheck(ctx, TypecheckWorkspace, ids...)
if err != nil {
return nil, err
}
// In order to allow basic references/rename/implementations to function when
// non-workspace packages are open, ensure that we have at least one fully
// parsed package for the current file. This allows us to find references
// inside the open package. Use WidestPackage to capture references in test
// files.
hasFullPackage := false
for _, pkg := range pkgs {
if pkg.ParseMode() == ParseFull {
hasFullPackage = true
break
}
}
if !hasFullPackage {
pkg, _, err := PackageForFile(ctx, s, key.uri, TypecheckFull, WidestPackage)
if err != nil {
return nil, err
}
pkgs = append(pkgs, pkg)
}
// report objects in the order we encounter them. This ensures that the first
// result is at the cursor...
var qualifiedObjs []qualifiedObject
// ...but avoid duplicates.
seenObjs := map[types.Object]bool{}
for _, searchpkg := range pkgs {
pgf, err := searchpkg.File(key.uri)
if err != nil {
return nil, err
}
pos := pgf.Tok.Pos(key.offset)
// TODO(adonovan): replace this section with a call to objectsAt().
path := pathEnclosingObjNode(pgf.File, pos)
if path == nil {
continue
}
var objs []types.Object
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(searchpkg.GetTypesInfo(), path); len(implicits) > 0 {
objs = append(objs, implicits...)
} else {
obj := searchpkg.GetTypesInfo().ObjectOf(leaf)
if obj == nil {
return nil, fmt.Errorf("%w for %q", errNoObjectFound, leaf.Name)
}
objs = append(objs, obj)
}
case *ast.ImportSpec:
// Look up the implicit *types.PkgName.
obj := searchpkg.GetTypesInfo().Implicits[leaf]
if obj == nil {
return nil, fmt.Errorf("%w for import %s", errNoObjectFound, UnquoteImportPath(leaf))
}
objs = append(objs, obj)
}
// Get all of the transitive dependencies of the search package.
pkgs := make(map[*types.Package]Package)
var addPkg func(pkg Package)
addPkg = func(pkg Package) {
pkgs[pkg.GetTypes()] = pkg
for _, imp := range pkg.Imports() {
if _, ok := pkgs[imp.GetTypes()]; !ok {
addPkg(imp)
}
}
}
addPkg(searchpkg)
for _, obj := range objs {
if obj.Parent() == types.Universe {
return nil, fmt.Errorf("%q: %w", obj.Name(), errBuiltin)
}
pkg, ok := pkgs[obj.Pkg()]
if !ok {
event.Error(ctx, fmt.Sprintf("no package for obj %s: %v", obj, obj.Pkg()), err)
continue
}
qualifiedObjs = append(qualifiedObjs, qualifiedObject{
obj: obj,
pkg: pkg,
sourcePkg: searchpkg,
node: path[0],
})
seenObjs[obj] = true
// If the qualified object is in another file (or more likely, another
// package), it's possible that there is another copy of it in a package
// that we haven't searched, e.g. a test variant. See golang/go#47564.
//
// In order to be sure we've considered all packages, call
// qualifiedObjsAtLocation recursively for all locations we encounter. We
// could probably be more precise here, only continuing the search if obj
// is in another package, but this should be good enough to find all
// uses.
if key, found := packagePositionKey(pkg, obj.Pos()); found {
otherObjs, err := qualifiedObjsAtLocation(ctx, s, key, seen)
if err != nil {
return nil, err
}
for _, other := range otherObjs {
if !seenObjs[other.obj] {
qualifiedObjs = append(qualifiedObjs, other)
seenObjs[other.obj] = true
}
}
} else {
return nil, fmt.Errorf("missing file for position of %q in %q", obj.Name(), obj.Pkg().Name())
}
}
}
// Return an error if no objects were found since callers will assume that
// the slice has at least 1 element.
if len(qualifiedObjs) == 0 {
return nil, errNoObjectFound
}
return qualifiedObjs, nil
}
// packagePositionKey finds the positionKey for the given pos.
//
// The second result reports whether the position was found.
func packagePositionKey(pkg Package, pos token.Pos) (positionKey, bool) {
for _, pgf := range pkg.CompiledGoFiles() {
offset, err := safetoken.Offset(pgf.Tok, pos)
if err == nil {
return positionKey{pgf.URI, offset}, true
}
}
return positionKey{}, false
}
// pathEnclosingObjNode returns the AST path to the object-defining
// node associated with pos. "Object-defining" means either an
// *ast.Ident mapped directly to a types.Object or an ast.Node mapped
// implicitly to a types.Object.
func pathEnclosingObjNode(f *ast.File, pos token.Pos) []ast.Node {
var (
path []ast.Node
found bool
)
ast.Inspect(f, func(n ast.Node) bool {
if found {
return false
}
if n == nil {
path = path[:len(path)-1]
return false
}
path = append(path, n)
switch n := n.(type) {
case *ast.Ident:
// Include the position directly after identifier. This handles
// the common case where the cursor is right after the
// identifier the user is currently typing. Previously we
// handled this by calling astutil.PathEnclosingInterval twice,
// once for "pos" and once for "pos-1".
found = n.Pos() <= pos && pos <= n.End()
case *ast.ImportSpec:
if n.Path.Pos() <= pos && pos < n.Path.End() {
found = true
// If import spec has a name, add name to path even though
// position isn't in the name.
if n.Name != nil {
path = append(path, n.Name)
}
}
case *ast.StarExpr:
// Follow star expressions to the inner identifier.
if pos == n.Star {
pos = n.X.Pos()
}
}
return !found
})
if len(path) == 0 {
return nil
}
// Reverse path so leaf is first element.
for i := 0; i < len(path)/2; i++ {
path[i], path[len(path)-1-i] = path[len(path)-1-i], path[i]
}
return path
}