aboutsummaryrefslogtreecommitdiff
path: root/go/types/objectpath/objectpath.go
diff options
context:
space:
mode:
Diffstat (limited to 'go/types/objectpath/objectpath.go')
-rw-r--r--go/types/objectpath/objectpath.go261
1 files changed, 198 insertions, 63 deletions
diff --git a/go/types/objectpath/objectpath.go b/go/types/objectpath/objectpath.go
index 557202b4d..be8f5a867 100644
--- a/go/types/objectpath/objectpath.go
+++ b/go/types/objectpath/objectpath.go
@@ -14,8 +14,10 @@
// distinct but logically equivalent.
//
// A single object may have multiple paths. In this example,
-// type A struct{ X int }
-// type B A
+//
+// type A struct{ X int }
+// type B A
+//
// the field X has two paths due to its membership of both A and B.
// The For(obj) function always returns one of these paths, arbitrarily
// but consistently.
@@ -29,6 +31,8 @@ import (
"strings"
"golang.org/x/tools/internal/typeparams"
+
+ _ "unsafe" // for go:linkname
)
// A Path is an opaque name that identifies a types.Object
@@ -45,30 +49,30 @@ type Path string
// The sequences represent a path through the package/object/type graph.
// We classify these operators by their type:
//
-// PO package->object Package.Scope.Lookup
-// OT object->type Object.Type
-// TT type->type Type.{Elem,Key,Params,Results,Underlying} [EKPRU]
-// TO type->object Type.{At,Field,Method,Obj} [AFMO]
+// PO package->object Package.Scope.Lookup
+// OT object->type Object.Type
+// TT type->type Type.{Elem,Key,Params,Results,Underlying} [EKPRU]
+// TO type->object Type.{At,Field,Method,Obj} [AFMO]
//
// All valid paths start with a package and end at an object
// and thus may be defined by the regular language:
//
-// objectpath = PO (OT TT* TO)*
+// objectpath = PO (OT TT* TO)*
//
// The concrete encoding follows directly:
-// - The only PO operator is Package.Scope.Lookup, which requires an identifier.
-// - The only OT operator is Object.Type,
-// which we encode as '.' because dot cannot appear in an identifier.
-// - The TT operators are encoded as [EKPRUTC];
-// one of these (TypeParam) requires an integer operand,
-// which is encoded as a string of decimal digits.
-// - The TO operators are encoded as [AFMO];
-// three of these (At,Field,Method) require an integer operand,
-// which is encoded as a string of decimal digits.
-// These indices are stable across different representations
-// of the same package, even source and export data.
-// The indices used are implementation specific and may not correspond to
-// the argument to the go/types function.
+// - The only PO operator is Package.Scope.Lookup, which requires an identifier.
+// - The only OT operator is Object.Type,
+// which we encode as '.' because dot cannot appear in an identifier.
+// - The TT operators are encoded as [EKPRUTC];
+// one of these (TypeParam) requires an integer operand,
+// which is encoded as a string of decimal digits.
+// - The TO operators are encoded as [AFMO];
+// three of these (At,Field,Method) require an integer operand,
+// which is encoded as a string of decimal digits.
+// These indices are stable across different representations
+// of the same package, even source and export data.
+// The indices used are implementation specific and may not correspond to
+// the argument to the go/types function.
//
// In the example below,
//
@@ -81,15 +85,14 @@ type Path string
// field X has the path "T.UM0.RA1.F0",
// representing the following sequence of operations:
//
-// p.Lookup("T") T
-// .Type().Underlying().Method(0). f
-// .Type().Results().At(1) b
-// .Type().Field(0) X
+// p.Lookup("T") T
+// .Type().Underlying().Method(0). f
+// .Type().Results().At(1) b
+// .Type().Field(0) X
//
// The encoding is not maximally compact---every R or P is
// followed by an A, for example---but this simplifies the
// encoder and decoder.
-//
const (
// object->type operators
opType = '.' // .Type() (Object)
@@ -110,7 +113,7 @@ const (
opObj = 'O' // .Obj() (Named, TypeParam)
)
-// The For function returns the path to an object relative to its package,
+// For returns the path to an object relative to its package,
// or an error if the object is not accessible from the package's Scope.
//
// The For function guarantees to return a path only for the following objects:
@@ -136,13 +139,30 @@ const (
//
// For(X) would return a path that denotes the following sequence of operations:
//
-// p.Scope().Lookup("T") (TypeName T)
-// .Type().Underlying().Method(0). (method Func f)
-// .Type().Results().At(1) (field Var b)
-// .Type().Field(0) (field Var X)
+// p.Scope().Lookup("T") (TypeName T)
+// .Type().Underlying().Method(0). (method Func f)
+// .Type().Results().At(1) (field Var b)
+// .Type().Field(0) (field Var X)
//
// where p is the package (*types.Package) to which X belongs.
func For(obj types.Object) (Path, error) {
+ return newEncoderFor()(obj)
+}
+
+// An encoder amortizes the cost of encoding the paths of multiple objects.
+// Nonexported pending approval of proposal 58668.
+type encoder struct {
+ scopeNamesMemo map[*types.Scope][]string // memoization of Scope.Names()
+ namedMethodsMemo map[*types.Named][]*types.Func // memoization of namedMethods()
+}
+
+// Exposed to gopls via golang.org/x/tools/internal/typesinternal
+// pending approval of proposal 58668.
+//
+//go:linkname newEncoderFor
+func newEncoderFor() func(types.Object) (Path, error) { return new(encoder).For }
+
+func (enc *encoder) For(obj types.Object) (Path, error) {
pkg := obj.Pkg()
// This table lists the cases of interest.
@@ -223,10 +243,11 @@ func For(obj types.Object) (Path, error) {
if recv := obj.Type().(*types.Signature).Recv(); recv == nil {
return "", fmt.Errorf("func is not a method: %v", obj)
}
- // TODO(adonovan): opt: if the method is concrete,
- // do a specialized version of the rest of this function so
- // that it's O(1) not O(|scope|). Basically 'find' is needed
- // only for struct fields and interface methods.
+
+ if path, ok := enc.concreteMethod(obj); ok {
+ // Fast path for concrete methods that avoids looping over scope.
+ return path, nil
+ }
default:
panic(obj)
@@ -239,7 +260,7 @@ func For(obj types.Object) (Path, error) {
// the best paths because non-types may
// refer to types, but not the reverse.
empty := make([]byte, 0, 48) // initial space
- names := scope.Names()
+ names := enc.scopeNames(scope)
for _, name := range names {
o := scope.Lookup(name)
tname, ok := o.(*types.TypeName)
@@ -292,9 +313,7 @@ func For(obj types.Object) (Path, error) {
// Note that method index here is always with respect
// to canonical ordering of methods, regardless of how
// they appear in the underlying type.
- canonical := canonicalize(T)
- for i := 0; i < len(canonical); i++ {
- m := canonical[i]
+ for i, m := range enc.namedMethods(T) {
path2 := appendOpArg(path, opMethod, i)
if m == obj {
return Path(path2), nil // found declared method
@@ -315,6 +334,96 @@ func appendOpArg(path []byte, op byte, arg int) []byte {
return path
}
+// concreteMethod returns the path for meth, which must have a non-nil receiver.
+// The second return value indicates success and may be false if the method is
+// an interface method or if it is an instantiated method.
+//
+// This function is just an optimization that avoids the general scope walking
+// approach. You are expected to fall back to the general approach if this
+// function fails.
+func (enc *encoder) concreteMethod(meth *types.Func) (Path, bool) {
+ // Concrete methods can only be declared on package-scoped named types. For
+ // that reason we can skip the expensive walk over the package scope: the
+ // path will always be package -> named type -> method. We can trivially get
+ // the type name from the receiver, and only have to look over the type's
+ // methods to find the method index.
+ //
+ // Methods on generic types require special consideration, however. Consider
+ // the following package:
+ //
+ // L1: type S[T any] struct{}
+ // L2: func (recv S[A]) Foo() { recv.Bar() }
+ // L3: func (recv S[B]) Bar() { }
+ // L4: type Alias = S[int]
+ // L5: func _[T any]() { var s S[int]; s.Foo() }
+ //
+ // The receivers of methods on generic types are instantiations. L2 and L3
+ // instantiate S with the type-parameters A and B, which are scoped to the
+ // respective methods. L4 and L5 each instantiate S with int. Each of these
+ // instantiations has its own method set, full of methods (and thus objects)
+ // with receivers whose types are the respective instantiations. In other
+ // words, we have
+ //
+ // S[A].Foo, S[A].Bar
+ // S[B].Foo, S[B].Bar
+ // S[int].Foo, S[int].Bar
+ //
+ // We may thus be trying to produce object paths for any of these objects.
+ //
+ // S[A].Foo and S[B].Bar are the origin methods, and their paths are S.Foo
+ // and S.Bar, which are the paths that this function naturally produces.
+ //
+ // S[A].Bar, S[B].Foo, and both methods on S[int] are instantiations that
+ // don't correspond to the origin methods. For S[int], this is significant.
+ // The most precise object path for S[int].Foo, for example, is Alias.Foo,
+ // not S.Foo. Our function, however, would produce S.Foo, which would
+ // resolve to a different object.
+ //
+ // For S[A].Bar and S[B].Foo it could be argued that S.Bar and S.Foo are
+ // still the correct paths, since only the origin methods have meaningful
+ // paths. But this is likely only true for trivial cases and has edge cases.
+ // Since this function is only an optimization, we err on the side of giving
+ // up, deferring to the slower but definitely correct algorithm. Most users
+ // of objectpath will only be giving us origin methods, anyway, as referring
+ // to instantiated methods is usually not useful.
+
+ if typeparams.OriginMethod(meth) != meth {
+ return "", false
+ }
+
+ recvT := meth.Type().(*types.Signature).Recv().Type()
+ if ptr, ok := recvT.(*types.Pointer); ok {
+ recvT = ptr.Elem()
+ }
+
+ named, ok := recvT.(*types.Named)
+ if !ok {
+ return "", false
+ }
+
+ if types.IsInterface(named) {
+ // Named interfaces don't have to be package-scoped
+ //
+ // TODO(dominikh): opt: if scope.Lookup(name) == named, then we can apply this optimization to interface
+ // methods, too, I think.
+ return "", false
+ }
+
+ // Preallocate space for the name, opType, opMethod, and some digits.
+ name := named.Obj().Name()
+ path := make([]byte, 0, len(name)+8)
+ path = append(path, name...)
+ path = append(path, opType)
+ for i, m := range enc.namedMethods(named) {
+ if m == meth {
+ path = appendOpArg(path, opMethod, i)
+ return Path(path), true
+ }
+ }
+
+ panic(fmt.Sprintf("couldn't find method %s on type %s", meth, named))
+}
+
// find finds obj within type T, returning the path to it, or nil if not found.
//
// The seen map is used to short circuit cycles through type parameters. If
@@ -570,15 +679,23 @@ func Object(pkg *types.Package, p Path) (types.Object, error) {
t = nil
case opMethod:
- hasMethods, ok := t.(hasMethods) // Interface or Named
- if !ok {
+ switch t := t.(type) {
+ case *types.Interface:
+ if index >= t.NumMethods() {
+ return nil, fmt.Errorf("method index %d out of range [0-%d)", index, t.NumMethods())
+ }
+ obj = t.Method(index) // Id-ordered
+
+ case *types.Named:
+ methods := namedMethods(t) // (unmemoized)
+ if index >= len(methods) {
+ return nil, fmt.Errorf("method index %d out of range [0-%d)", index, len(methods))
+ }
+ obj = methods[index] // Id-ordered
+
+ default:
return nil, fmt.Errorf("cannot apply %q to %s (got %T, want interface or named)", code, t, t)
}
- canonical := canonicalize(hasMethods)
- if n := len(canonical); index >= n {
- return nil, fmt.Errorf("method index %d out of range [0-%d)", index, n)
- }
- obj = canonical[index]
t = nil
case opObj:
@@ -601,27 +718,45 @@ func Object(pkg *types.Package, p Path) (types.Object, error) {
return obj, nil // success
}
-// hasMethods is an abstraction of *types.{Interface,Named}. This is pulled up
-// because it is used by methodOrdering, which is in turn used by both encoding
-// and decoding.
-type hasMethods interface {
- Method(int) *types.Func
- NumMethods() int
+// namedMethods returns the methods of a Named type in ascending Id order.
+func namedMethods(named *types.Named) []*types.Func {
+ methods := make([]*types.Func, named.NumMethods())
+ for i := range methods {
+ methods[i] = named.Method(i)
+ }
+ sort.Slice(methods, func(i, j int) bool {
+ return methods[i].Id() < methods[j].Id()
+ })
+ return methods
}
-// canonicalize returns a canonical order for the methods in a hasMethod.
-func canonicalize(hm hasMethods) []*types.Func {
- count := hm.NumMethods()
- if count <= 0 {
- return nil
+// scopeNames is a memoization of scope.Names. Callers must not modify the result.
+func (enc *encoder) scopeNames(scope *types.Scope) []string {
+ m := enc.scopeNamesMemo
+ if m == nil {
+ m = make(map[*types.Scope][]string)
+ enc.scopeNamesMemo = m
}
- canon := make([]*types.Func, count)
- for i := 0; i < count; i++ {
- canon[i] = hm.Method(i)
+ names, ok := m[scope]
+ if !ok {
+ names = scope.Names() // allocates and sorts
+ m[scope] = names
}
- less := func(i, j int) bool {
- return canon[i].Id() < canon[j].Id()
+ return names
+}
+
+// namedMethods is a memoization of the namedMethods function. Callers must not modify the result.
+func (enc *encoder) namedMethods(named *types.Named) []*types.Func {
+ m := enc.namedMethodsMemo
+ if m == nil {
+ m = make(map[*types.Named][]*types.Func)
+ enc.namedMethodsMemo = m
}
- sort.Slice(canon, less)
- return canon
+ methods, ok := m[named]
+ if !ok {
+ methods = namedMethods(named) // allocates and sorts
+ m[named] = methods
+ }
+ return methods
+
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-25 03:04:59 +0000