go/types: merge Named type loading and expansion

Named type expansion and loading were conceptually similar: a mechanism
for lazily resolving type information in a concurrency-safe manner.
Unify them into a 'resolve' method, that delegates to a resolver func to
produce type parameters, underlying, and methods.

By leveraging the sync.Once field on Named for instance expansion, we
get closer to making instance expansion concurrency-safe, and remove the
requirement that instPos guard instantiation. This will be cleaned up
in a follow-up CL.

This also fixes #47887 by causing substituted type instances to be
expanded (in the old code, this could be fixed by setting instPos when
substituting).

For #47910
Fixes #47887

Change-Id: Ifc52a420dde76e3a46ce494fea9bd289bc8aca4c
Reviewed-on: https://go-review.googlesource.com/c/go/+/349410
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, 114 insertions, 96 deletions

diff --git a/src/go/types/decl.go b/src/go/types/decl.go
index c1506f6dbd..7f157f528a 100644
--- a/src/go/types/decl.go
+++ b/src/go/types/decl.go
@@ -316,7 +316,7 @@ func (check *Checker) validType(typ Type, path []Object) typeInfo {
 		}
 
 	case *Named:
-		t.expand(check.conf.Environment)
+		t.resolve(check.conf.Environment)
 		// don't touch the type if it is from a different package or the Universe scope
 		// (doing so would lead to a race condition - was issue #35049)
 		if t.obj.pkg != check.pkg {
@@ -773,7 +773,7 @@ func (check *Checker) collectMethods(obj *TypeName) {
 		}
 
 		if base != nil {
-			base.load() // TODO(mdempsky): Probably unnecessary.
+			base.resolve(nil) // TODO(mdempsky): Probably unnecessary.
 			base.methods = append(base.methods, m)
 		}
 	}
diff --git a/src/go/types/instantiate.go b/src/go/types/instantiate.go
index 50be07b8fd..b74f0db466 100644
--- a/src/go/types/instantiate.go
+++ b/src/go/types/instantiate.go
@@ -116,9 +116,10 @@ func (check *Checker) instance(pos token.Pos, typ Type, targs []Type, env *Envir
 			}
 		}
 		tname := NewTypeName(pos, t.obj.pkg, t.obj.name, nil)
-		named := check.newNamed(tname, t, nil, nil, nil) // methods and tparams are set when named is loaded
+		named := check.newNamed(tname, t, nil, nil, nil) // methods and tparams are set when named is resolved
 		named.targs = NewTypeList(targs)
 		named.instPos = &pos
+		named.resolver = expandNamed
 		if env != nil {
 			// It's possible that we've lost a race to add named to the environment.
 			// In this case, use whichever instance is recorded in the environment.
diff --git a/src/go/types/lookup.go b/src/go/types/lookup.go
index 4664a0b33b..cc7f24d97b 100644
--- a/src/go/types/lookup.go
+++ b/src/go/types/lookup.go
@@ -124,7 +124,7 @@ func lookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (o
 				seen[named] = true
 
 				// look for a matching attached method
-				named.load()
+				named.resolve(nil)
 				if i, m := lookupMethod(named.methods, pkg, name); m != nil {
 					// potential match
 					// caution: method may not have a proper signature yet
diff --git a/src/go/types/named.go b/src/go/types/named.go
index 74681ab2d4..fd9e1f4461 100644
--- a/src/go/types/named.go
+++ b/src/go/types/named.go
@@ -22,8 +22,9 @@ type Named struct {
 	targs      *TypeList      // type arguments (after instantiation), or nil
 	methods    []*Func        // methods declared for this type (not the method set of this type); signatures are type-checked lazily
 
-	resolve func(*Named) ([]*TypeParam, Type, []*Func)
-	once    sync.Once
+	// resolver may be provided to lazily resolve type parameters, underlying, and methods.
+	resolver func(*Environment, *Named) (tparams *TypeParamList, underlying Type, methods []*Func)
+	once     sync.Once // ensures that tparams, underlying, and methods are resolved before accessing
 }
 
 // NewNamed returns a new named type for the given type name, underlying type, and associated methods.
@@ -36,43 +37,22 @@ func NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named {
 	return (*Checker)(nil).newNamed(obj, nil, underlying, nil, methods)
 }
 
-func (t *Named) load() *Named {
-	// If t is an instantiated type, it derives its methods and tparams from its
-	// base type. Since we expect type parameters and methods to be set after a
-	// call to load, we must load the base and copy here.
-	//
-	// underlying is set when t is expanded.
-	//
-	// By convention, a type instance is loaded iff its tparams are set.
-	if t.targs.Len() > 0 && t.tparams == nil {
-		t.orig.load()
-		t.tparams = t.orig.tparams
-		t.methods = t.orig.methods
-	}
-	if t.resolve == nil {
+func (t *Named) resolve(env *Environment) *Named {
+	if t.resolver == nil {
 		return t
 	}
 
 	t.once.Do(func() {
-		// TODO(mdempsky): Since we're passing t to resolve anyway
+		// TODO(mdempsky): Since we're passing t to the resolver anyway
 		// (necessary because types2 expects the receiver type for methods
 		// on defined interface types to be the Named rather than the
 		// underlying Interface), maybe it should just handle calling
 		// SetTypeParams, SetUnderlying, and AddMethod instead?  Those
-		// methods would need to support reentrant calls though.  It would
+		// methods would need to support reentrant calls though. It would
 		// also make the API more future-proof towards further extensions
 		// (like SetTypeParams).
-
-		tparams, underlying, methods := t.resolve(t)
-
-		switch underlying.(type) {
-		case nil, *Named:
-			panic("invalid underlying type")
-		}
-
-		t.tparams = bindTParams(tparams)
-		t.underlying = underlying
-		t.methods = methods
+		t.tparams, t.underlying, t.methods = t.resolver(env, t)
+		t.fromRHS = t.underlying // for cycle detection
 	})
 	return t
 }
@@ -121,19 +101,19 @@ func (t *Named) _Orig() *Named { return t.orig }
 
 // TypeParams returns the type parameters of the named type t, or nil.
 // The result is non-nil for an (originally) parameterized type even if it is instantiated.
-func (t *Named) TypeParams() *TypeParamList { return t.load().tparams }
+func (t *Named) TypeParams() *TypeParamList { return t.resolve(nil).tparams }
 
 // SetTypeParams sets the type parameters of the named type t.
-func (t *Named) SetTypeParams(tparams []*TypeParam) { t.load().tparams = bindTParams(tparams) }
+func (t *Named) SetTypeParams(tparams []*TypeParam) { t.resolve(nil).tparams = bindTParams(tparams) }
 
 // TypeArgs returns the type arguments used to instantiate the named type t.
 func (t *Named) TypeArgs() *TypeList { return t.targs }
 
 // NumMethods returns the number of explicit methods whose receiver is named type t.
-func (t *Named) NumMethods() int { return len(t.load().methods) }
+func (t *Named) NumMethods() int { return len(t.resolve(nil).methods) }
 
 // Method returns the i'th method of named type t for 0 <= i < t.NumMethods().
-func (t *Named) Method(i int) *Func { return t.load().methods[i] }
+func (t *Named) Method(i int) *Func { return t.resolve(nil).methods[i] }
 
 // SetUnderlying sets the underlying type and marks t as complete.
 func (t *Named) SetUnderlying(underlying Type) {
@@ -143,18 +123,18 @@ func (t *Named) SetUnderlying(underlying Type) {
 	if _, ok := underlying.(*Named); ok {
 		panic("underlying type must not be *Named")
 	}
-	t.load().underlying = underlying
+	t.resolve(nil).underlying = underlying
 }
 
 // AddMethod adds method m unless it is already in the method list.
 func (t *Named) AddMethod(m *Func) {
-	t.load()
+	t.resolve(nil)
 	if i, _ := lookupMethod(t.methods, m.pkg, m.name); i < 0 {
 		t.methods = append(t.methods, m)
 	}
 }
 
-func (t *Named) Underlying() Type { return t.load().expand(nil).underlying }
+func (t *Named) Underlying() Type { return t.resolve(nil).underlying }
 func (t *Named) String() string   { return TypeString(t, nil) }
 
 // ----------------------------------------------------------------------------
@@ -240,43 +220,37 @@ func (n *Named) setUnderlying(typ Type) {
 	}
 }
 
-// expand ensures that the underlying type of n is instantiated.
+// expandNamed ensures that the underlying type of n is instantiated.
 // The underlying type will be Typ[Invalid] if there was an error.
-func (n *Named) expand(env *Environment) *Named {
-	if n.instPos != nil {
-		// n must be loaded before instantiation, in order to have accurate
-		// tparams. This is done implicitly by the call to n.TypeParams, but making
-		// it explicit is harmless: load is idempotent.
-		n.load()
-		var u Type
-		if n.check.validateTArgLen(*n.instPos, n.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
-				} 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
-					// environment, but don't want to create a duplicate of the current
-					// instance in the process of expansion.
-					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.
-				env.typeForHash(h, n)
+func expandNamed(env *Environment, n *Named) (*TypeParamList, Type, []*Func) {
+	n.orig.resolve(env)
+
+	var u Type
+	if n.check.validateTArgLen(*n.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
+			} 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
+				// environment, but don't want to create a duplicate of the current
+				// instance in the process of expansion.
+				env = NewEnvironment()
 			}
-			u = n.check.subst(*n.instPos, n.orig.underlying, makeSubstMap(n.TypeParams().list(), n.targs.list()), env)
-		} else {
-			u = Typ[Invalid]
+			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.
+			env.typeForHash(h, n)
 		}
-		n.underlying = u
-		n.fromRHS = u
-		n.instPos = nil
+		u = n.check.subst(*n.instPos, n.orig.underlying, makeSubstMap(n.orig.tparams.list(), n.targs.list()), env)
+	} else {
+		u = Typ[Invalid]
 	}
-	return n
+	n.instPos = nil
+	return n.orig.tparams, u, n.orig.methods
 }
 
 // safeUnderlying returns the underlying of typ without expanding instances, to
@@ -285,7 +259,7 @@ func (n *Named) expand(env *Environment) *Named {
 // TODO(rfindley): eliminate this function or give it a better name.
 func safeUnderlying(typ Type) Type {
 	if t, _ := typ.(*Named); t != nil {
-		return t.load().underlying
+		return t.resolve(nil).underlying
 	}
 	return typ.Underlying()
 }
diff --git a/src/go/types/object.go b/src/go/types/object.go
index b25fffdf5c..7f6f8a2550 100644
--- a/src/go/types/object.go
+++ b/src/go/types/object.go
@@ -232,9 +232,21 @@ func NewTypeName(pos token.Pos, pkg *Package, name string, typ Type) *TypeName {
 
 // _NewTypeNameLazy returns a new defined type like NewTypeName, but it
 // lazily calls resolve to finish constructing the Named object.
-func _NewTypeNameLazy(pos token.Pos, pkg *Package, name string, resolve func(named *Named) (tparams []*TypeParam, underlying Type, methods []*Func)) *TypeName {
+func _NewTypeNameLazy(pos token.Pos, pkg *Package, name string, load func(named *Named) (tparams []*TypeParam, underlying Type, methods []*Func)) *TypeName {
 	obj := NewTypeName(pos, pkg, name, nil)
-	NewNamed(obj, nil, nil).resolve = resolve
+
+	resolve := func(_ *Environment, t *Named) (*TypeParamList, Type, []*Func) {
+		tparams, underlying, methods := load(t)
+
+		switch underlying.(type) {
+		case nil, *Named:
+			panic(fmt.Sprintf("invalid underlying type %T", t.underlying))
+		}
+
+		return bindTParams(tparams), underlying, methods
+	}
+
+	NewNamed(obj, nil, nil).resolver = resolve
 	return obj
 }
 
diff --git a/src/go/types/signature.go b/src/go/types/signature.go
index 37811828ee..bf6c775b89 100644
--- a/src/go/types/signature.go
+++ b/src/go/types/signature.go
@@ -200,7 +200,7 @@ func (check *Checker) funcType(sig *Signature, recvPar *ast.FieldList, ftyp *ast
 			var err string
 			switch T := rtyp.(type) {
 			case *Named:
-				T.expand(nil)
+				T.resolve(check.conf.Environment)
 				// The receiver type may be an instantiated type referred to
 				// by an alias (which cannot have receiver parameters for now).
 				if T.TypeArgs() != nil && sig.RecvTypeParams() == nil {
diff --git a/src/go/types/subst.go b/src/go/types/subst.go
index 07fe6a6b6e..d9dab10e00 100644
--- a/src/go/types/subst.go
+++ b/src/go/types/subst.go
@@ -182,13 +182,19 @@ func (subst *subster) typ(typ Type) Type {
 			}
 		}
 
-		if t.TypeParams().Len() == 0 {
+		// subst is called by expandNamed, so in this function we need to be
+		// careful not to call any methods that would cause t to be expanded: doing
+		// so would result in deadlock.
+		//
+		// So we call t.orig.TypeParams() rather than t.TypeParams() here and
+		// below.
+		if t.orig.TypeParams().Len() == 0 {
 			dump(">>> %s is not parameterized", t)
 			return t // type is not parameterized
 		}
 
 		var newTArgs []Type
-		assert(t.targs.Len() == t.TypeParams().Len())
+		assert(t.targs.Len() == t.orig.TypeParams().Len())
 
 		// already instantiated
 		dump(">>> %s already instantiated", t)
@@ -201,7 +207,7 @@ func (subst *subster) typ(typ Type) Type {
 			if new_targ != targ {
 				dump(">>> substituted %d targ %s => %s", i, targ, new_targ)
 				if newTArgs == nil {
-					newTArgs = make([]Type, t.TypeParams().Len())
+					newTArgs = make([]Type, t.orig.TypeParams().Len())
 					copy(newTArgs, t.targs.list())
 				}
 				newTArgs[i] = new_targ
@@ -221,25 +227,22 @@ func (subst *subster) typ(typ Type) Type {
 			return named
 		}
 
-		// Create a new named type and populate the environment to avoid endless
+		t.orig.resolve(subst.env)
+		// Create a new instance and populate the environment to avoid endless
 		// recursion. The position used here is irrelevant because validation only
 		// occurs on t (we don't call validType on named), but we use subst.pos to
 		// help with debugging.
-		tname := NewTypeName(subst.pos, t.obj.pkg, t.obj.name, nil)
-		t.load()
-		// It's ok to provide a nil *Checker because the newly created type
-		// doesn't need to be (lazily) expanded; it's expanded below.
-		named := (*Checker)(nil).newNamed(tname, t.orig, nil, t.tparams, t.methods) // t is loaded, so tparams and methods are available
-		named.targs = NewTypeList(newTArgs)
-		subst.env.typeForHash(h, named)
-		t.expand(subst.env) // must happen after env update to avoid infinite recursion
-
-		// do the substitution
-		dump(">>> subst %s with %s (new: %s)", t.underlying, subst.smap, newTArgs)
-		named.underlying = subst.typOrNil(t.underlying)
-		dump(">>> underlying: %v", named.underlying)
+		named := subst.check.instance(subst.pos, t.orig, newTArgs, subst.env).(*Named)
+		// TODO(rfindley): we probably don't need to resolve here. Investigate if
+		// this can be removed.
+		named.resolve(subst.env)
 		assert(named.underlying != nil)
-		named.fromRHS = named.underlying // for consistency, though no cycle detection is necessary
+
+		// Note that if we were to expose substitution more generally (not just in
+		// the context of a declaration), we'd have to substitute in
+		// named.underlying as well.
+		//
+		// But this is unnecessary for now.
 
 		return named
 
diff --git a/src/go/types/testdata/fixedbugs/issue47887.go2 b/src/go/types/testdata/fixedbugs/issue47887.go2
new file mode 100644
index 0000000000..4c4fc2fda8
--- /dev/null
+++ b/src/go/types/testdata/fixedbugs/issue47887.go2
@@ -0,0 +1,28 @@
+// Copyright 2021 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 p
+
+type Fooer[t any] interface {
+	foo(Barer[t])
+}
+type Barer[t any] interface {
+	bar(Bazer[t])
+}
+type Bazer[t any] interface {
+	Fooer[t]
+	baz(t)
+}
+
+type Int int
+
+func (n Int) baz(int) {}
+func (n Int) foo(b Barer[int]) { b.bar(n) }
+
+type F[t any] interface { f(G[t]) }
+type G[t any] interface { g(H[t]) }
+type H[t any] interface { F[t] }
+
+type T struct{}
+func (n T) f(b G[T]) { b.g(n) }
diff --git a/src/go/types/type.go b/src/go/types/type.go
index b9634cf6f6..31149cfd36 100644
--- a/src/go/types/type.go
+++ b/src/go/types/type.go
@@ -114,7 +114,7 @@ func asInterface(t Type) *Interface {
 func asNamed(t Type) *Named {
 	e, _ := t.(*Named)
 	if e != nil {
-		e.expand(nil)
+		e.resolve(nil)
 	}
 	return e
 }