gopls/internal/golang: Implementations for func types
This CL adds support to the Implementations query for function
types. The query relates two sets of locations:
1. the "func" token of each function declaration (FuncDecl or
FuncLit). These are analogous to declarations of concrete
methods.
2. uses of abstract functions:
(a) the "func" token of each FuncType that is not part of
Func{Decl,Lit}. These are analogous to interface{...} types.
(b) the "(" paren of each dynamic call on a value of an
abstract function type. These are analogous to references to
interface method names, but no names are involved, which has
historically made them hard to search for.
An Implementations query on a location in set 1 returns set 2,
and vice versa.
Only the local algorithm is implemented for now; the global
one (using an index analogous to methodsets) will follow.
This CL supersedes CL 448035 and CL 619515, both of which attempt
to unify the treatment of functions and interfaces in the methodsets
algorithm and in the index; but the two problems are not precisely
analogous, and I think we'll end up with more but simpler code
if we implement themn separately.
+ tests, docs, relnotes
Updates golang/go#56572
Change-Id: I18e1a7cc2f6c320112b9f3589323d04f9a52ef3c
Reviewed-on: https://go-review.googlesource.com/c/tools/+/654556
Commit-Queue: Alan Donovan <adonovan@google.com>
Reviewed-by: Jonathan Amsterdam <jba@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Alan Donovan <adonovan@google.com>
diff --git a/gopls/doc/features/navigation.md b/gopls/doc/features/navigation.md
index f46f293..f3454f7 100644
--- a/gopls/doc/features/navigation.md
+++ b/gopls/doc/features/navigation.md
@@ -85,7 +85,10 @@
The LSP
[`textDocument/implementation`](https://microsoft.github.io/language-server-protocol/specifications/lsp/3.17/specification/#textDocument_implementation)
-request queries the "implements" relation between interfaces and concrete types:
+request queries the relation between abstract and concrete types and
+their methods.
+
+Interfaces and concrete types are matched using method sets:
- When invoked on a reference to an **interface type**, it returns the
location of the declaration of each type that implements
@@ -111,6 +114,17 @@
but that is not consistent with the "scalable" gopls design.
-->
+Functions, `func` types, and dynamic function calls are matched using signatures:
+
+- When invoked on the `func` token of a **function definition**,
+ it returns the locations of the matching signature types
+ and dynamic call expressions.
+- When invoked on the `func` token of a **signature type**,
+ it returns the locations of the matching concrete function definitions.
+- When invoked on the `(` token of a **dynamic function call**,
+ it returns the locations of the matching concrete function
+ definitions.
+
If either the target type or the candidate type are generic, the
results will include the candidate type if there is any instantiation
of the two types that would allow one to implement the other.
@@ -120,6 +134,12 @@
method set or even within a single method.
This may lead to occasional spurious matches.)
+Since a type may be both a function type and a named type with methods
+(for example, `http.HandlerFunc`), it may participate in both kinds of
+implementation queries (by method-sets and function signatures).
+Queries using method-sets should be invoked on the type or method name,
+and queries using signatures should be invoked on a `func` or `(` token.
+
Client support:
- **VS Code**: Use [Go to Implementations](https://code.visualstudio.com/docs/editor/editingevolved#_go-to-implementation) (`⌘F12`).
- **Emacs + eglot**: Use `M-x eglot-find-implementation`.
diff --git a/gopls/doc/release/v0.19.0.md b/gopls/doc/release/v0.19.0.md
index 1808873..149a474 100644
--- a/gopls/doc/release/v0.19.0.md
+++ b/gopls/doc/release/v0.19.0.md
@@ -7,6 +7,33 @@
# New features
+## "Implementations" supports signature types
+
+The Implementations query reports the correspondence between abstract
+and concrete types and their methods based on their method sets.
+Now, it also reports the correspondence between function types,
+dynamic function calls, and function definitions, based on their signatures.
+
+To use it, invoke an Implementations query on the `func` token of the
+definition of a named function, named method, or function literal.
+Gopls reports the set of function signature types that abstract this
+function, and the set of dynamic calls through values of such types.
+
+Conversely, an Implementations query on the `func` token of a
+signature type, or on the `(` paren of a dynamic function call,
+reports the set of concrete functions that the signature abstracts
+or that the call dispatches to.
+
+Since a type may be both a function type and a named type with methods
+(for example, `http.HandlerFunc`), it may participate in both kinds of
+Implements queries (method-sets and function signatures).
+Queries using method-sets should be invoked on the type or method name,
+and queries using signatures should be invoked on a `func` or `(` token.
+
+Only the local (same-package) algorithm is currently supported.
+TODO: implement global.
+
+
## "Eliminate dot import" code action
This code action, available on a dotted import, will offer to replace
diff --git a/gopls/internal/golang/implementation.go b/gopls/internal/golang/implementation.go
index a7a7e66..2d9a1e9 100644
--- a/gopls/internal/golang/implementation.go
+++ b/gopls/internal/golang/implementation.go
@@ -12,6 +12,7 @@
"go/token"
"go/types"
"reflect"
+ "slices"
"sort"
"strings"
"sync"
@@ -21,10 +22,13 @@
"golang.org/x/tools/gopls/internal/cache"
"golang.org/x/tools/gopls/internal/cache/metadata"
"golang.org/x/tools/gopls/internal/cache/methodsets"
+ "golang.org/x/tools/gopls/internal/cache/parsego"
"golang.org/x/tools/gopls/internal/file"
"golang.org/x/tools/gopls/internal/protocol"
"golang.org/x/tools/gopls/internal/util/bug"
"golang.org/x/tools/gopls/internal/util/safetoken"
+ "golang.org/x/tools/internal/astutil/cursor"
+ "golang.org/x/tools/internal/astutil/edge"
"golang.org/x/tools/internal/event"
)
@@ -74,9 +78,26 @@
}
func implementations(ctx context.Context, snapshot *cache.Snapshot, fh file.Handle, pp protocol.Position) ([]protocol.Location, error) {
- // First, find the object referenced at the cursor by type checking the
- // current package.
- obj, pkg, err := implementsObj(ctx, snapshot, fh.URI(), pp)
+ // Type check the current package.
+ pkg, pgf, err := NarrowestPackageForFile(ctx, snapshot, fh.URI())
+ if err != nil {
+ return nil, err
+ }
+ pos, err := pgf.PositionPos(pp)
+ if err != nil {
+ return nil, err
+ }
+
+ // Find implementations based on func signatures.
+ if locs, err := implFuncs(pkg, pgf, pos); err != errNotHandled {
+ return locs, err
+ }
+
+ // Find implementations based on method sets.
+
+ // First, find the object referenced at the cursor.
+ // The object may be declared in a different package.
+ obj, err := implementsObj(pkg, pgf, pos)
if err != nil {
return nil, err
}
@@ -272,21 +293,9 @@
return m.OffsetLocation(start, end)
}
-// implementsObj returns the object to query for implementations, which is a
-// type name or method.
-//
-// The returned Package is the narrowest package containing ppos, which is the
-// package using the resulting obj but not necessarily the declaring package.
-func implementsObj(ctx context.Context, snapshot *cache.Snapshot, uri protocol.DocumentURI, ppos protocol.Position) (types.Object, *cache.Package, error) {
- pkg, pgf, err := NarrowestPackageForFile(ctx, snapshot, uri)
- if err != nil {
- return nil, nil, err
- }
- pos, err := pgf.PositionPos(ppos)
- if err != nil {
- return nil, nil, err
- }
-
+// implementsObj returns the object to query for implementations,
+// which is a type name or method.
+func implementsObj(pkg *cache.Package, pgf *parsego.File, pos token.Pos) (types.Object, error) {
// This function inherits the limitation of its predecessor in
// requiring the selection to be an identifier (of a type or
// method). But there's no fundamental reason why one could
@@ -299,11 +308,11 @@
// TODO(adonovan): simplify: use objectsAt?
path := pathEnclosingObjNode(pgf.File, pos)
if path == nil {
- return nil, nil, ErrNoIdentFound
+ return nil, ErrNoIdentFound
}
id, ok := path[0].(*ast.Ident)
if !ok {
- return nil, nil, ErrNoIdentFound
+ return nil, ErrNoIdentFound
}
// Is the object a type or method? Reject other kinds.
@@ -319,17 +328,18 @@
// ok
case *types.Func:
if obj.Signature().Recv() == nil {
- return nil, nil, fmt.Errorf("%s is a function, not a method", id.Name)
+ return nil, fmt.Errorf("%s is a function, not a method (query at 'func' token to find matching signatures)", id.Name)
}
case nil:
- return nil, nil, fmt.Errorf("%s denotes unknown object", id.Name)
+ return nil, fmt.Errorf("%s denotes unknown object", id.Name)
default:
// e.g. *types.Var -> "var".
kind := strings.ToLower(strings.TrimPrefix(reflect.TypeOf(obj).String(), "*types."))
- return nil, nil, fmt.Errorf("%s is a %s, not a type", id.Name, kind)
+ // TODO(adonovan): improve upon "nil is a nil, not a type".
+ return nil, fmt.Errorf("%s is a %s, not a type", id.Name, kind)
}
- return obj, pkg, nil
+ return obj, nil
}
// localImplementations searches within pkg for declarations of all
@@ -679,9 +689,236 @@
}
// 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]
- }
+ slices.Reverse(path)
return path
}
+
+// --- Implementations based on signature types --
+
+// implFuncs finds Implementations based on func types.
+//
+// Just as an interface type abstracts a set of concrete methods, a
+// function type abstracts a set of concrete functions. Gopls provides
+// analogous operations for navigating from abstract to concrete and
+// back in the domain of function types.
+//
+// A single type (for example http.HandlerFunc) can have both an
+// underlying type of function (types.Signature) and have methods that
+// cause it to implement an interface. To avoid a confusing user
+// interface we want to separate the two operations so that the user
+// can unambiguously specify the query they want.
+//
+// So, whereas Implementations queries on interface types are usually
+// keyed by an identifier of a named type, Implementations queries on
+// function types are keyed by the "func" keyword, or by the "(" of a
+// call expression. The query relates two sets of locations:
+//
+// 1. the "func" token of each function declaration (FuncDecl or
+// FuncLit). These are analogous to declarations of concrete
+// methods.
+//
+// 2. uses of abstract functions:
+//
+// (a) the "func" token of each FuncType that is not part of
+// Func{Decl,Lit}. These are analogous to interface{...} types.
+//
+// (b) the "(" paren of each dynamic call on a value of an
+// abstract function type. These are analogous to references to
+// interface method names, but no names are involved, which has
+// historically made them hard to search for.
+//
+// An Implementations query on a location in set 1 returns set 2,
+// and vice versa.
+//
+// implFuncs returns errNotHandled to indicate that we should try the
+// regular method-sets algorithm.
+func implFuncs(pkg *cache.Package, pgf *parsego.File, pos token.Pos) ([]protocol.Location, error) {
+ curSel, ok := pgf.Cursor.FindPos(pos, pos)
+ if !ok {
+ return nil, fmt.Errorf("no code selected")
+ }
+
+ info := pkg.TypesInfo()
+
+ // Find innermost enclosing FuncType or CallExpr.
+ //
+ // We are looking for specific tokens (FuncType.Func and
+ // CallExpr.Lparen), but FindPos prefers an adjoining
+ // subexpression: given f(x) without additional spaces between
+ // tokens, FindPos always returns either f or x, never the
+ // CallExpr itself. Thus we must ascend the tree.
+ //
+ // Another subtlety: due to an edge case in go/ast, FindPos at
+ // FuncDecl.Type.Func does not return FuncDecl.Type, only the
+ // FuncDecl, because the orders of tree positions and tokens
+ // are inconsistent. Consequently, the ancestors for a "func"
+ // token of Func{Lit,Decl} do not include FuncType, hence the
+ // explicit cases below.
+ for _, cur := range curSel.Stack(nil) {
+ switch n := cur.Node().(type) {
+ case *ast.FuncDecl, *ast.FuncLit:
+ if inToken(n.Pos(), "func", pos) {
+ // Case 1: concrete function declaration.
+ // Report uses of corresponding function types.
+ switch n := n.(type) {
+ case *ast.FuncDecl:
+ return funcUses(pkg, info.Defs[n.Name].Type())
+ case *ast.FuncLit:
+ return funcUses(pkg, info.TypeOf(n.Type))
+ }
+ }
+
+ case *ast.FuncType:
+ if n.Func.IsValid() && inToken(n.Func, "func", pos) && !beneathFuncDef(cur) {
+ // Case 2a: function type.
+ // Report declarations of corresponding concrete functions.
+ return funcDefs(pkg, info.TypeOf(n))
+ }
+
+ case *ast.CallExpr:
+ if inToken(n.Lparen, "(", pos) {
+ t := dynamicFuncCallType(info, n)
+ if t == nil {
+ return nil, fmt.Errorf("not a dynamic function call")
+ }
+ // Case 2b: dynamic call of function value.
+ // Report declarations of corresponding concrete functions.
+ return funcDefs(pkg, t)
+ }
+ }
+ }
+
+ // It's probably a query of a named type or method.
+ // Fall back to the method-sets computation.
+ return nil, errNotHandled
+}
+
+var errNotHandled = errors.New("not handled")
+
+// funcUses returns all locations in the workspace that are dynamic
+// uses of the specified function type.
+func funcUses(pkg *cache.Package, t types.Type) ([]protocol.Location, error) {
+ var locs []protocol.Location
+
+ // local search
+ for _, pgf := range pkg.CompiledGoFiles() {
+ for cur := range pgf.Cursor.Preorder((*ast.CallExpr)(nil), (*ast.FuncType)(nil)) {
+ var pos, end token.Pos
+ var ftyp types.Type
+ switch n := cur.Node().(type) {
+ case *ast.CallExpr:
+ ftyp = dynamicFuncCallType(pkg.TypesInfo(), n)
+ pos, end = n.Lparen, n.Lparen+token.Pos(len("("))
+
+ case *ast.FuncType:
+ if !beneathFuncDef(cur) {
+ // func type (not def)
+ ftyp = pkg.TypesInfo().TypeOf(n)
+ pos, end = n.Func, n.Func+token.Pos(len("func"))
+ }
+ }
+ if ftyp == nil {
+ continue // missing type information
+ }
+ if unify(t, ftyp) {
+ loc, err := pgf.PosLocation(pos, end)
+ if err != nil {
+ return nil, err
+ }
+ locs = append(locs, loc)
+ }
+ }
+ }
+
+ // TODO(adonovan): implement global search
+
+ return locs, nil
+}
+
+// funcDefs returns all locations in the workspace that define
+// functions of the specified type.
+func funcDefs(pkg *cache.Package, t types.Type) ([]protocol.Location, error) {
+ var locs []protocol.Location
+
+ // local search
+ for _, pgf := range pkg.CompiledGoFiles() {
+ for curFn := range pgf.Cursor.Preorder((*ast.FuncDecl)(nil), (*ast.FuncLit)(nil)) {
+ fn := curFn.Node()
+ var ftyp types.Type
+ switch fn := fn.(type) {
+ case *ast.FuncDecl:
+ ftyp = pkg.TypesInfo().Defs[fn.Name].Type()
+ case *ast.FuncLit:
+ ftyp = pkg.TypesInfo().TypeOf(fn)
+ }
+ if ftyp == nil {
+ continue // missing type information
+ }
+ if unify(t, ftyp) {
+ pos := fn.Pos()
+ loc, err := pgf.PosLocation(pos, pos+token.Pos(len("func")))
+ if err != nil {
+ return nil, err
+ }
+ locs = append(locs, loc)
+ }
+ }
+ }
+
+ // TODO(adonovan): implement global search, by analogy with
+ // methodsets algorithm.
+ //
+ // One optimization: if any signature type has free package
+ // names, look for matches only in packages among the rdeps of
+ // those packages.
+
+ return locs, nil
+}
+
+// beneathFuncDef reports whether the specified FuncType cursor is a
+// child of Func{Decl,Lit}.
+func beneathFuncDef(cur cursor.Cursor) bool {
+ ek, _ := cur.Edge()
+ switch ek {
+ case edge.FuncDecl_Type, edge.FuncLit_Type:
+ return true
+ }
+ return false
+}
+
+// dynamicFuncCallType reports whether call is a dynamic (non-method) function call.
+// If so, it returns the function type, otherwise nil.
+//
+// Tested via ../test/marker/testdata/implementation/signature.txt.
+func dynamicFuncCallType(info *types.Info, call *ast.CallExpr) types.Type {
+ fun := ast.Unparen(call.Fun)
+ tv := info.Types[fun]
+
+ // Reject conversion, or call to built-in.
+ if !tv.IsValue() {
+ return nil
+ }
+
+ // Reject call to named func/method.
+ if id, ok := fun.(*ast.Ident); ok && is[*types.Func](info.Uses[id]) {
+ return nil
+ }
+
+ // Reject method selections (T.method() or x.method())
+ if sel, ok := fun.(*ast.SelectorExpr); ok {
+ seln, ok := info.Selections[sel]
+ if !ok || seln.Kind() != types.FieldVal {
+ return nil
+ }
+ }
+
+ // TODO(adonovan): consider x() where x : TypeParam.
+ return tv.Type.Underlying() // e.g. x() or x.field()
+}
+
+// inToken reports whether pos is within the token of
+// the specified position and string.
+func inToken(tokPos token.Pos, tokStr string, pos token.Pos) bool {
+ return tokPos <= pos && pos <= tokPos+token.Pos(len(tokStr))
+}
diff --git a/gopls/internal/test/marker/doc.go b/gopls/internal/test/marker/doc.go
index dff8dfa..2fc3e04 100644
--- a/gopls/internal/test/marker/doc.go
+++ b/gopls/internal/test/marker/doc.go
@@ -212,9 +212,10 @@
- hovererr(src, sm stringMatcher): performs a textDocument/hover at the src
location, and checks that the error matches the given stringMatcher.
- - implementations(src location, want ...location): makes a
- textDocument/implementation query at the src location and
- checks that the resulting set of locations matches want.
+ - implementation(src location, want ...location, err=stringMatcher):
+ makes a textDocument/implementation query at the src location and
+ checks that the resulting set of locations matches want. If err is
+ set, the implementation query must fail with the expected error.
- incomingcalls(src location, want ...location): makes a
callHierarchy/incomingCalls query at the src location, and checks that
diff --git a/gopls/internal/test/marker/marker_test.go b/gopls/internal/test/marker/marker_test.go
index a3e62d3..3ff7da6 100644
--- a/gopls/internal/test/marker/marker_test.go
+++ b/gopls/internal/test/marker/marker_test.go
@@ -584,7 +584,7 @@
"highlightall": actionMarkerFunc(highlightAllMarker),
"hover": actionMarkerFunc(hoverMarker),
"hovererr": actionMarkerFunc(hoverErrMarker),
- "implementation": actionMarkerFunc(implementationMarker),
+ "implementation": actionMarkerFunc(implementationMarker, "err"),
"incomingcalls": actionMarkerFunc(incomingCallsMarker),
"inlayhints": actionMarkerFunc(inlayhintsMarker),
"outgoingcalls": actionMarkerFunc(outgoingCallsMarker),
@@ -2375,13 +2375,19 @@
// implementationMarker implements the @implementation marker.
func implementationMarker(mark marker, src protocol.Location, want ...protocol.Location) {
+ wantErr := namedArgFunc(mark, "err", convertStringMatcher, stringMatcher{})
+
got, err := mark.server().Implementation(mark.ctx(), &protocol.ImplementationParams{
TextDocumentPositionParams: protocol.LocationTextDocumentPositionParams(src),
})
- if err != nil {
+ if err != nil && wantErr.empty() {
mark.errorf("implementation at %s failed: %v", src, err)
return
}
+ if !wantErr.empty() {
+ wantErr.checkErr(mark, err)
+ return
+ }
if err := compareLocations(mark, got, want); err != nil {
mark.errorf("implementation: %v", err)
}
diff --git a/gopls/internal/test/marker/testdata/implementation/signature.txt b/gopls/internal/test/marker/testdata/implementation/signature.txt
new file mode 100644
index 0000000..b94d048
--- /dev/null
+++ b/gopls/internal/test/marker/testdata/implementation/signature.txt
@@ -0,0 +1,79 @@
+Test of local Implementation queries using function signatures.
+
+Assertions:
+- Query on "func" of a function type returns the corresponding concrete functions.
+- Query on "func" of a concrete function returns corresponding function types.
+- Query on "(" of a dynamic function call returns corresponding function types.
+- Different signatures (Nullary vs Handler) don't correspond.
+
+The @loc markers use the suffixes Func, Type, Call for the three kinds.
+Each query maps between these two sets: {Func} <=> {Type,Call}.
+
+-- go.mod --
+module example.com
+go 1.18
+
+-- a/a.go --
+package a
+
+// R is short for Record.
+type R struct{}
+
+// H is short for Handler.
+type H func(*R) //@ loc(HType, "func"), implementation("func", aFunc, bFunc, cFunc)
+
+func aFunc(*R) {} //@ loc(aFunc, "func"), implementation("func", HType, hParamType, hCall)
+
+var bFunc = func(*R) {} //@ loc(bFunc, "func"), implementation("func", hParamType, hCall, HType)
+
+func nullary() { //@ loc(nullaryFunc, "func"), implementation("func", Nullary, fieldCall)
+ cFunc := func(*R) {} //@ loc(cFunc, "func"), implementation("func", hParamType, hCall, HType)
+ _ = cFunc
+}
+
+type Nullary func() //@ loc(Nullary, "func")
+
+func _(
+ h func(*R)) { //@ loc(hParamType, "func"), implementation("func", aFunc, bFunc, cFunc)
+
+ _ = aFunc // pacify unusedfunc
+ _ = nullary // pacify unusedfunc
+ _ = h
+
+ h(nil) //@ loc(hCall, "("), implementation("(", aFunc, bFunc, cFunc)
+}
+
+// generics:
+
+func _[T any](complex128) {
+ f1 := func(T) int { return 0 } //@ loc(f1Func, "func"), implementation("func", fParamType, fCall, f1Call, f2Call)
+ f2 := func(string) int { return 0 } //@ loc(f2Func, "func"), implementation("func", fParamType, fCall, f1Call, f2Call)
+ f3 := func(int) int { return 0 } //@ loc(f3Func, "func"), implementation("func", f1Call)
+
+ f1(*new(T)) //@ loc(f1Call, "("), implementation("(", f1Func, f2Func, f3Func, f4Func)
+ f2("") //@ loc(f2Call, "("), implementation("(", f1Func, f2Func, f4Func)
+ _ = f3 // not called
+}
+
+func f4[T any](T) int { return 0 } //@ loc(f4Func, "func"), implementation("func", fParamType, fCall, f1Call, f2Call)
+
+var _ = f4[string] // pacify unusedfunc
+
+func _(
+ f func(string) int, //@ loc(fParamType, "func"), implementation("func", f1Func, f2Func, f4Func)
+ err error) {
+
+ f("") //@ loc(fCall, "("), implementation("(", f1Func, f2Func, f4Func)
+
+ struct{x Nullary}{}.x() //@ loc(fieldCall, "("), implementation("(", nullaryFunc)
+
+ // Calls that are not dynamic function calls:
+ _ = len("") //@ implementation("(", err="not a dynamic function call")
+ _ = int(0) //@ implementation("(", err="not a dynamic function call")
+ _ = error.Error(nil) //@ implementation("(", err="not a dynamic function call")
+ _ = err.Error() //@ implementation("(", err="not a dynamic function call")
+ _ = f4(0) //@ implementation("(", err="not a dynamic function call"), loc(f4Call, "(")
+}
+
+
+
