go/types: instantiate methods when instantiating Named types

In the API proposal we decided that instantiation must also instantiate
methods. This CL does that, and eliminates the special handling for lazy
instantiation in lookupMethod.

It is possible that we expand an instance before all method signatures
have been type-checked, so for simplicity we introduce a new flag on
Func, 'isIncompleteMethod', which controls whether we must fully
substitute methods before using them. We could avoid this flag by using
some convention for the structure of an incomplete method (such as the
receiver has no position), but in practice using a flag was cleaner and
didn't increase the size of the Func struct.

Updates #47916

Change-Id: I352baa6664cd07f61b06924744382897805f9d29
Reviewed-on: https://go-review.googlesource.com/c/go/+/349412
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

9 files changed, 119 insertions, 89 deletions

diff --git a/src/go/types/call.go b/src/go/types/call.go
index 4de5fed46e..4d14e31730 100644
--- a/src/go/types/call.go
+++ b/src/go/types/call.go
@@ -532,54 +532,6 @@ func (check *Checker) selector(x *operand, e *ast.SelectorExpr) {
 	// methods may not have a fully set up signature yet
 	if m, _ := obj.(*Func); m != nil {
 		check.objDecl(m, nil)
-		// If m has a parameterized receiver type, infer the type arguments from
-		// the actual receiver provided and then substitute the type parameters in
-		// the signature accordingly.
-		// TODO(gri) factor this code out
-		sig := m.typ.(*Signature)
-		if sig.RecvTypeParams().Len() > 0 {
-			// For inference to work, we must use the receiver type
-			// matching the receiver in the actual method declaration.
-			// If the method is embedded, the matching receiver is the
-			// embedded struct or interface that declared the method.
-			// Traverse the embedding to find that type (issue #44688).
-			recv := x.typ
-			for i := 0; i < len(index)-1; i++ {
-				// The embedded type is either a struct or a pointer to
-				// a struct except for the last one (which we don't need).
-				recv = asStruct(derefStructPtr(recv)).Field(index[i]).typ
-			}
-
-			// The method may have a pointer receiver, but the actually provided receiver
-			// may be a (hopefully addressable) non-pointer value, or vice versa. Here we
-			// only care about inferring receiver type parameters; to make the inference
-			// work, match up pointer-ness of receiver and argument.
-			if ptrRecv := isPointer(sig.recv.typ); ptrRecv != isPointer(recv) {
-				if ptrRecv {
-					recv = NewPointer(recv)
-				} else {
-					recv = recv.(*Pointer).base
-				}
-			}
-			// Disable reporting of errors during inference below. If we're unable to infer
-			// the receiver type arguments here, the receiver must be be otherwise invalid
-			// and an error has been reported elsewhere.
-			arg := operand{mode: variable, expr: x.expr, typ: recv}
-			targs := check.infer(m, sig.RecvTypeParams().list(), nil, NewTuple(sig.recv), []*operand{&arg}, false /* no error reporting */)
-			if targs == nil {
-				// We may reach here if there were other errors (see issue #40056).
-				goto Error
-			}
-			// Don't modify m. Instead - for now - make a copy of m and use that instead.
-			// (If we modify m, some tests will fail; possibly because the m is in use.)
-			// TODO(gri) investigate and provide a correct explanation here
-			copy := *m
-			copy.typ = check.subst(e.Pos(), m.typ, makeSubstMap(sig.RecvTypeParams().list(), targs), nil)
-			obj = &copy
-		}
-		// TODO(gri) we also need to do substitution for parameterized interface methods
-		//           (this breaks code in testdata/linalg.go2 at the moment)
-		//           12/20/2019: Is this TODO still correct?
 	}
 
 	if x.mode == typexpr {
diff --git a/src/go/types/decl.go b/src/go/types/decl.go
index 7f157f528a..0fdcfa8023 100644
--- a/src/go/types/decl.go
+++ b/src/go/types/decl.go
@@ -65,6 +65,12 @@ func (check *Checker) objDecl(obj Object, def *Named) {
 		}()
 	}
 
+	// Funcs with m.instRecv set have not yet be completed. Complete them now
+	// so that they have a type when objDecl exits.
+	if m, _ := obj.(*Func); m != nil && m.instRecv != nil {
+		check.completeMethod(check.conf.Environment, m)
+	}
+
 	// Checking the declaration of obj means inferring its type
 	// (and possibly its value, for constants).
 	// An object's type (and thus the object) may be in one of
diff --git a/src/go/types/infer.go b/src/go/types/infer.go
index 7314a614d0..18c5119177 100644
--- a/src/go/types/infer.go
+++ b/src/go/types/infer.go
@@ -28,6 +28,7 @@ import (
 //
 // Constraint type inference is used after each step to expand the set of type arguments.
 //
+// TODO(rfindley): remove the report parameter: is no longer needed.
 func (check *Checker) infer(posn positioner, tparams []*TypeParam, targs []Type, params *Tuple, args []*operand, report bool) (result []Type) {
 	if debug {
 		defer func() {
diff --git a/src/go/types/instantiate_test.go b/src/go/types/instantiate_test.go
index 0b09bfebe3..851800e76d 100644
--- a/src/go/types/instantiate_test.go
+++ b/src/go/types/instantiate_test.go
@@ -70,3 +70,42 @@ func TestInstantiateNonEquality(t *testing.T) {
 		t.Errorf("instance from pkg1 (%s) is identical to instance from pkg2 (%s)", res1, res2)
 	}
 }
+
+func TestMethodInstantiation(t *testing.T) {
+	const prefix = genericPkg + `p
+
+type T[P any] struct{}
+
+var X T[int]
+
+`
+	tests := []struct {
+		decl string
+		want string
+	}{
+		{"func (r T[P]) m() P", "func (T[int]).m() int"},
+		{"func (r T[P]) m(P)", "func (T[int]).m(int)"},
+		{"func (r T[P]) m() func() P", "func (T[int]).m() func() int"},
+		{"func (r T[P]) m() T[P]", "func (T[int]).m() T[int]"},
+		{"func (r T[P]) m(T[P])", "func (T[int]).m(T[int])"},
+		{"func (r T[P]) m(T[P], P, string)", "func (T[int]).m(T[int], int, string)"},
+		{"func (r T[P]) m(T[P], T[string], T[int])", "func (T[int]).m(T[int], T[string], T[int])"},
+	}
+
+	for _, test := range tests {
+		src := prefix + test.decl
+		pkg, err := pkgFor(".", src, nil)
+		if err != nil {
+			t.Fatal(err)
+		}
+		typ := pkg.Scope().Lookup("X").Type().(*Named)
+		obj, _, _ := LookupFieldOrMethod(typ, false, pkg, "m")
+		m, _ := obj.(*Func)
+		if m == nil {
+			t.Fatalf(`LookupFieldOrMethod(%s, "m") = %v, want func m`, typ, obj)
+		}
+		if got := ObjectString(m, RelativeTo(pkg)); got != test.want {
+			t.Errorf("instantiated %q, want %q", got, test.want)
+		}
+	}
+}
diff --git a/src/go/types/lookup.go b/src/go/types/lookup.go
index cc7f24d97b..a270159499 100644
--- a/src/go/types/lookup.go
+++ b/src/go/types/lookup.go
@@ -6,8 +6,6 @@
 
 package types
 
-import "go/token"
-
 // Internal use of LookupFieldOrMethod: If the obj result is a method
 // associated with a concrete (non-interface) type, the method's signature
 // may not be fully set up. Call Checker.objDecl(obj, nil) before accessing
@@ -342,8 +340,6 @@ func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method,
 	}
 
 	// A concrete type implements T if it implements all methods of T.
-	Vd, _ := deref(V)
-	Vn := asNamed(Vd)
 	for _, m := range T.typeSet().methods {
 		// TODO(gri) should this be calling lookupFieldOrMethod instead (and why not)?
 		obj, _, _ := lookupFieldOrMethod(V, false, m.pkg, m.name)
@@ -378,26 +374,6 @@ func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method,
 			panic("method with type parameters")
 		}
 
-		// If V is a (instantiated) generic type, its methods are still
-		// parameterized using the original (declaration) receiver type
-		// parameters (subst simply copies the existing method list, it
-		// does not instantiate the methods).
-		// In order to compare the signatures, substitute the receiver
-		// type parameters of ftyp with V's instantiation type arguments.
-		// This lazily instantiates the signature of method f.
-		if Vn != nil && Vn.TypeParams().Len() > 0 {
-			// Be careful: The number of type arguments may not match
-			// the number of receiver parameters. If so, an error was
-			// reported earlier but the length discrepancy is still
-			// here. Exit early in this case to prevent an assertion
-			// failure in makeSubstMap.
-			// TODO(gri) Can we avoid this check by fixing the lengths?
-			if len(ftyp.RecvTypeParams().list()) != Vn.targs.Len() {
-				return
-			}
-			ftyp = check.subst(token.NoPos, ftyp, makeSubstMap(ftyp.RecvTypeParams().list(), Vn.targs.list()), nil).(*Signature)
-		}
-
 		// If the methods have type parameters we don't care whether they
 		// are the same or not, as long as they match up. Use unification
 		// to see if they can be made to match.
diff --git a/src/go/types/named.go b/src/go/types/named.go
index 943d52f0fe..66ae012379 100644
--- a/src/go/types/named.go
+++ b/src/go/types/named.go
@@ -221,16 +221,17 @@ func (n *Named) setUnderlying(typ Type) {
 
 // expandNamed ensures that the underlying type of n is instantiated.
 // The underlying type will be Typ[Invalid] if there was an error.
-func expandNamed(env *Environment, n *Named, instPos token.Pos) (*TypeParamList, Type, []*Func) {
+func expandNamed(env *Environment, n *Named, instPos token.Pos) (tparams *TypeParamList, underlying Type, methods []*Func) {
 	n.orig.resolve(env)
 
-	var u Type
-	if n.check.validateTArgLen(instPos, n.orig.tparams.Len(), n.targs.Len()) {
+	check := n.check
+
+	if check.validateTArgLen(instPos, n.orig.tparams.Len(), n.targs.Len()) {
 		// TODO(rfindley): handling an optional Checker and Environment here (and
 		// in subst) feels overly complicated. Can we simplify?
 		if env == nil {
-			if n.check != nil {
-				env = n.check.conf.Environment
+			if check != nil {
+				env = check.conf.Environment
 			} else {
 				// If we're instantiating lazily, we might be outside the scope of a
 				// type-checking pass. In that case we won't have a pre-existing
@@ -239,16 +240,72 @@ func expandNamed(env *Environment, n *Named, instPos token.Pos) (*TypeParamList,
 				env = NewEnvironment()
 			}
 			h := env.typeHash(n.orig, n.targs.list())
-			// add the instance to the environment to avoid infinite recursion.
-			// addInstance may return a different, existing instance, but we
-			// shouldn't return that instance from expand.
+			// ensure that an instance is recorded for h to avoid infinite recursion.
 			env.typeForHash(h, n)
 		}
-		u = n.check.subst(instPos, n.orig.underlying, makeSubstMap(n.orig.tparams.list(), n.targs.list()), env)
+		smap := makeSubstMap(n.orig.tparams.list(), n.targs.list())
+		underlying = n.check.subst(instPos, n.orig.underlying, smap, env)
+		for i := 0; i < n.orig.NumMethods(); i++ {
+			origm := n.orig.Method(i)
+
+			// During type checking origm may not have a fully set up type, so defer
+			// instantiation of its signature until later.
+			m := NewFunc(origm.pos, origm.pkg, origm.name, nil)
+			m.hasPtrRecv = origm.hasPtrRecv
+			// Setting instRecv here allows us to complete later (we need the
+			// instRecv to get targs and the original method).
+			m.instRecv = n
+
+			methods = append(methods, m)
+		}
+	} else {
+		underlying = Typ[Invalid]
+	}
+
+	// Methods should not escape the type checker API without being completed. If
+	// we're in the context of a type checking pass, we need to defer this until
+	// later (not all methods may have types).
+	completeMethods := func() {
+		for _, m := range methods {
+			if m.instRecv != nil {
+				check.completeMethod(env, m)
+			}
+		}
+	}
+	if check != nil {
+		check.later(completeMethods)
 	} else {
-		u = Typ[Invalid]
+		completeMethods()
 	}
-	return n.orig.tparams, u, n.orig.methods
+
+	return n.orig.tparams, underlying, methods
+}
+
+func (check *Checker) completeMethod(env *Environment, m *Func) {
+	assert(m.instRecv != nil)
+	rtyp := m.instRecv
+	m.instRecv = nil
+	m.setColor(black)
+
+	assert(rtyp.TypeArgs().Len() > 0)
+
+	// Look up the original method.
+	_, orig := lookupMethod(rtyp.orig.methods, rtyp.obj.pkg, m.name)
+	assert(orig != nil)
+	if check != nil {
+		check.objDecl(orig, nil)
+	}
+	origSig := orig.typ.(*Signature)
+	if origSig.RecvTypeParams().Len() != rtyp.targs.Len() {
+		m.typ = origSig // or new(Signature), but we can't use Typ[Invalid]: Funcs must have Signature type
+		return          // error reported elsewhere
+	}
+
+	smap := makeSubstMap(origSig.RecvTypeParams().list(), rtyp.targs.list())
+	sig := check.subst(orig.pos, origSig, smap, env).(*Signature)
+	sig.recv = NewParam(origSig.recv.pos, origSig.recv.pkg, origSig.recv.name, rtyp)
+
+	m.typ = sig
 }
 
 // safeUnderlying returns the underlying of typ without expanding instances, to
diff --git a/src/go/types/object.go b/src/go/types/object.go
index 7f6f8a2550..454b714458 100644
--- a/src/go/types/object.go
+++ b/src/go/types/object.go
@@ -317,7 +317,8 @@ func (*Var) isDependency() {} // a variable may be a dependency of an initializa
 // An abstract method may belong to many interfaces due to embedding.
 type Func struct {
 	object
-	hasPtrRecv bool // only valid for methods that don't have a type yet
+	instRecv   *Named // if non-nil, the receiver type for an incomplete instance method
+	hasPtrRecv bool   // only valid for methods that don't have a type yet
 }
 
 // NewFunc returns a new function with the given signature, representing
@@ -328,7 +329,7 @@ func NewFunc(pos token.Pos, pkg *Package, name string, sig *Signature) *Func {
 	if sig != nil {
 		typ = sig
 	}
-	return &Func{object{nil, pos, pkg, name, typ, 0, colorFor(typ), token.NoPos}, false}
+	return &Func{object{nil, pos, pkg, name, typ, 0, colorFor(typ), token.NoPos}, nil, false}
 }
 
 // FullName returns the package- or receiver-type-qualified name of
diff --git a/src/go/types/sizeof_test.go b/src/go/types/sizeof_test.go
index f418e037a9..0e3c0064a0 100644
--- a/src/go/types/sizeof_test.go
+++ b/src/go/types/sizeof_test.go
@@ -40,7 +40,7 @@ func TestSizeof(t *testing.T) {
 		{Const{}, 48, 88},
 		{TypeName{}, 40, 72},
 		{Var{}, 44, 80},
-		{Func{}, 44, 80},
+		{Func{}, 48, 88},
 		{Label{}, 44, 80},
 		{Builtin{}, 44, 80},
 		{Nil{}, 40, 72},
diff --git a/src/go/types/subst.go b/src/go/types/subst.go
index a063dd0a07..3491541dcb 100644
--- a/src/go/types/subst.go
+++ b/src/go/types/subst.go
@@ -70,7 +70,6 @@ func (check *Checker) subst(pos token.Pos, typ Type, smap substMap, env *Environ
 		env = NewEnvironment()
 	}
 	subst.env = env
-
 	return subst.typ(typ)
 }
 
@@ -125,8 +124,7 @@ func (subst *subster) typ(typ Type) Type {
 		if recv != t.recv || params != t.params || results != t.results {
 			return &Signature{
 				rparams: t.rparams,
-				// TODO(rFindley) why can't we nil out tparams here, rather than in
-				//                instantiate above?
+				// TODO(rFindley) why can't we nil out tparams here, rather than in instantiate?
 				tparams:  t.tparams,
 				scope:    t.scope,
 				recv:     recv,