cmd/compile/internal/types2: merge Instantiate and InstantiateLazy

Instantiate and InstantiateLazy have the same signature; on first
principles, if Instantiate should work for importers it should be
possible to consolidate these APIs.

This CL does this. In order to make it work, a typMap needs to be
threaded through type expansion to prevent infinite recursion in the
case that the Checker is nil.

Notably, Named types now must be expanded before returning from
Underlying(). This makes Underlying generally unsafe to call while type
checking a package, so a helper function safeUnderlying is added to
provide the previous behavior. This is probably overly conservative at
most call sites, but cleanup is deferred to a later CL.

Change-Id: I03cfb75bea0750862cd6eea4e3cdc875a7daa989
Reviewed-on: https://go-review.googlesource.com/c/go/+/341855
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>

15 files changed, 87 insertions, 56 deletions

diff --git a/src/cmd/compile/internal/noder/reader2.go b/src/cmd/compile/internal/noder/reader2.go
index 5637196dc0..97ea4fcb76 100644
--- a/src/cmd/compile/internal/noder/reader2.go
+++ b/src/cmd/compile/internal/noder/reader2.go
@@ -229,7 +229,7 @@ func (r *reader2) doTyp() (res types2.Type) {
 		obj, targs := r.obj()
 		name := obj.(*types2.TypeName)
 		if len(targs) != 0 {
-			return r.p.check.InstantiateLazy(syntax.Pos{}, name.Type(), targs, nil, false)
+			return r.p.check.Instantiate(syntax.Pos{}, name.Type(), targs, nil, false)
 		}
 		return name.Type()
 
diff --git a/src/cmd/compile/internal/types2/api_test.go b/src/cmd/compile/internal/types2/api_test.go
index d8844956af..dfa4de1175 100644
--- a/src/cmd/compile/internal/types2/api_test.go
+++ b/src/cmd/compile/internal/types2/api_test.go
@@ -1875,7 +1875,7 @@ func TestInstantiate(t *testing.T) {
 	res := check.Instantiate(nopos, T, []Type{Typ[Int]}, nil, false)
 
 	// instantiated type should point to itself
-	if res.Underlying().(*Pointer).Elem() != res {
-		t.Fatalf("unexpected result type: %s", res)
+	if p := res.Underlying().(*Pointer).Elem(); p != res {
+		t.Fatalf("unexpected result type: %s points to %s", res, p)
 	}
 }
diff --git a/src/cmd/compile/internal/types2/call.go b/src/cmd/compile/internal/types2/call.go
index 049d80dd9e..94bcc4870b 100644
--- a/src/cmd/compile/internal/types2/call.go
+++ b/src/cmd/compile/internal/types2/call.go
@@ -334,7 +334,7 @@ func (check *Checker) arguments(call *syntax.CallExpr, sig *Signature, targs []T
 		// need to compute it from the adjusted list; otherwise we can
 		// simply use the result signature's parameter list.
 		if adjusted {
-			sigParams = check.subst(call.Pos(), sigParams, makeSubstMap(sig.TParams().list(), targs)).(*Tuple)
+			sigParams = check.subst(call.Pos(), sigParams, makeSubstMap(sig.TParams().list(), targs), nil).(*Tuple)
 		} else {
 			sigParams = rsig.params
 		}
@@ -555,7 +555,7 @@ func (check *Checker) selector(x *operand, e *syntax.SelectorExpr) {
 			// (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.RParams().list(), targs))
+			copy.typ = check.subst(e.Pos(), m.typ, makeSubstMap(sig.RParams().list(), targs), nil)
 			obj = &copy
 		}
 		// TODO(gri) we also need to do substitution for parameterized interface methods
diff --git a/src/cmd/compile/internal/types2/decl.go b/src/cmd/compile/internal/types2/decl.go
index bfccbc5dbf..24ec4cd029 100644
--- a/src/cmd/compile/internal/types2/decl.go
+++ b/src/cmd/compile/internal/types2/decl.go
@@ -317,7 +317,7 @@ func (check *Checker) validType(typ Type, path []Object) typeInfo {
 		}
 
 	case *Named:
-		t.expand()
+		t.expand(check.typMap)
 
 		// 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)
@@ -650,7 +650,8 @@ func (check *Checker) collectMethods(obj *TypeName) {
 	// and field names must be distinct."
 	base := asNamed(obj.typ) // shouldn't fail but be conservative
 	if base != nil {
-		if t, _ := base.Underlying().(*Struct); t != nil {
+		u := safeUnderlying(base) // base should be expanded, but use safeUnderlying to be conservative
+		if t, _ := u.(*Struct); t != nil {
 			for _, fld := range t.fields {
 				if fld.name != "_" {
 					assert(mset.insert(fld) == nil)
diff --git a/src/cmd/compile/internal/types2/expr.go b/src/cmd/compile/internal/types2/expr.go
index 3c2b10cd7e..6d8b423714 100644
--- a/src/cmd/compile/internal/types2/expr.go
+++ b/src/cmd/compile/internal/types2/expr.go
@@ -661,7 +661,7 @@ func (check *Checker) updateExprVal(x syntax.Expr, val constant.Value) {
 func (check *Checker) convertUntyped(x *operand, target Type) {
 	newType, val, code := check.implicitTypeAndValue(x, target)
 	if code != 0 {
-		check.invalidConversion(code, x, target.Underlying())
+		check.invalidConversion(code, x, safeUnderlying(target))
 		x.mode = invalid
 		return
 	}
diff --git a/src/cmd/compile/internal/types2/infer.go b/src/cmd/compile/internal/types2/infer.go
index ff4bb3ea17..7bf507471d 100644
--- a/src/cmd/compile/internal/types2/infer.go
+++ b/src/cmd/compile/internal/types2/infer.go
@@ -87,7 +87,7 @@ func (check *Checker) infer(pos syntax.Pos, tparams []*TypeName, targs []Type, p
 	//           but that doesn't impact the isParameterized check for now).
 	if params.Len() > 0 {
 		smap := makeSubstMap(tparams, targs)
-		params = check.subst(nopos, params, smap).(*Tuple)
+		params = check.subst(nopos, params, smap, nil).(*Tuple)
 	}
 
 	// --- 2 ---
@@ -127,7 +127,7 @@ func (check *Checker) infer(pos syntax.Pos, tparams []*TypeName, targs []Type, p
 			}
 		}
 		smap := makeSubstMap(tparams, targs)
-		inferred := check.subst(arg.Pos(), tpar, smap)
+		inferred := check.subst(arg.Pos(), tpar, smap, nil)
 		if inferred != tpar {
 			check.errorf(arg, "%s %s of %s does not match inferred type %s for %s", kind, targ, arg.expr, inferred, tpar)
 		} else {
@@ -427,7 +427,7 @@ func (check *Checker) inferB(tparams []*TypeName, targs []Type, report bool) (ty
 		n := 0
 		for _, index := range dirty {
 			t0 := types[index]
-			if t1 := check.subst(nopos, t0, smap); t1 != t0 {
+			if t1 := check.subst(nopos, t0, smap, nil); t1 != t0 {
 				types[index] = t1
 				dirty[n] = index
 				n++
diff --git a/src/cmd/compile/internal/types2/instantiate.go b/src/cmd/compile/internal/types2/instantiate.go
index 0bb4ac956b..a648a3c38c 100644
--- a/src/cmd/compile/internal/types2/instantiate.go
+++ b/src/cmd/compile/internal/types2/instantiate.go
@@ -29,7 +29,7 @@ func (check *Checker) Instantiate(pos syntax.Pos, typ Type, targs []Type, posLis
 	var tparams []*TypeName
 	switch t := typ.(type) {
 	case *Named:
-		tparams = t.TParams().list()
+		return check.instantiateLazy(pos, t, targs, posList, verify)
 	case *Signature:
 		tparams = t.TParams().list()
 		defer func() {
@@ -55,14 +55,14 @@ func (check *Checker) Instantiate(pos syntax.Pos, typ Type, targs []Type, posLis
 		panic(fmt.Sprintf("%v: cannot instantiate %v", pos, typ))
 	}
 
-	inst := check.instantiate(pos, typ, tparams, targs, posList)
+	inst := check.instantiate(pos, typ, tparams, targs, posList, nil)
 	if verify && len(tparams) == len(targs) {
 		check.verify(pos, tparams, targs, posList)
 	}
 	return inst
 }
 
-func (check *Checker) instantiate(pos syntax.Pos, typ Type, tparams []*TypeName, targs []Type, posList []syntax.Pos) (res Type) {
+func (check *Checker) instantiate(pos syntax.Pos, typ Type, tparams []*TypeName, targs []Type, posList []syntax.Pos, typMap map[string]*Named) (res Type) {
 	// the number of supplied types must match the number of type parameters
 	if len(targs) != len(tparams) {
 		// TODO(gri) provide better error message
@@ -83,7 +83,7 @@ func (check *Checker) instantiate(pos syntax.Pos, typ Type, tparams []*TypeName,
 				// Calling under() here may lead to endless instantiations.
 				// Test case: type T[P any] T[P]
 				// TODO(gri) investigate if that's a bug or to be expected.
-				under = res.Underlying()
+				under = safeUnderlying(res)
 			}
 			check.trace(pos, "=> %s (under = %s)", res, under)
 		}()
@@ -95,21 +95,14 @@ func (check *Checker) instantiate(pos syntax.Pos, typ Type, tparams []*TypeName,
 		return typ // nothing to do (minor optimization)
 	}
 
-	return check.subst(pos, typ, makeSubstMap(tparams, targs))
+	return check.subst(pos, typ, makeSubstMap(tparams, targs), typMap)
 }
 
-// InstantiateLazy is like Instantiate, but avoids actually
-// instantiating the type until needed. typ must be a *Named
-// type.
-func (check *Checker) InstantiateLazy(pos syntax.Pos, typ Type, targs []Type, posList []syntax.Pos, verify bool) Type {
-	// Don't use asNamed here: we don't want to expand the base during lazy
-	// instantiation.
-	base := typ.(*Named)
-	if base == nil {
-		panic(fmt.Sprintf("%v: cannot instantiate %v", pos, typ))
-	}
-
+// instantiateLazy avoids actually instantiating the type until needed. typ
+// must be a *Named type.
+func (check *Checker) instantiateLazy(pos syntax.Pos, base *Named, targs []Type, posList []syntax.Pos, verify bool) Type {
 	if verify && base.TParams().Len() == len(targs) {
+		// TODO: lift the nil check in verify to here.
 		check.later(func() {
 			check.verify(pos, base.tparams.list(), targs, posList)
 		})
@@ -169,7 +162,7 @@ func (check *Checker) satisfies(pos syntax.Pos, targ Type, tpar *TypeParam, smap
 	// as the instantiated type; before we can use it for bounds checking we
 	// need to instantiate it with the type arguments with which we instantiate
 	// the parameterized type.
-	iface = check.subst(pos, iface, smap).(*Interface)
+	iface = check.subst(pos, iface, smap, nil).(*Interface)
 
 	// if iface is comparable, targ must be comparable
 	// TODO(gri) the error messages needs to be better, here
diff --git a/src/cmd/compile/internal/types2/lookup.go b/src/cmd/compile/internal/types2/lookup.go
index 0363008ad9..3779d17b3d 100644
--- a/src/cmd/compile/internal/types2/lookup.go
+++ b/src/cmd/compile/internal/types2/lookup.go
@@ -46,7 +46,7 @@ func LookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (o
 	// pointer type but discard the result if it is a method since we would
 	// not have found it for T (see also issue 8590).
 	if t := asNamed(T); t != nil {
-		if p, _ := t.Underlying().(*Pointer); p != nil {
+		if p, _ := safeUnderlying(t).(*Pointer); p != nil {
 			obj, index, indirect = lookupFieldOrMethod(p, false, pkg, name)
 			if _, ok := obj.(*Func); ok {
 				return nil, nil, false
@@ -394,7 +394,7 @@ func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method,
 			if len(ftyp.RParams().list()) != len(Vn.targs) {
 				return
 			}
-			ftyp = check.subst(nopos, ftyp, makeSubstMap(ftyp.RParams().list(), Vn.targs)).(*Signature)
+			ftyp = check.subst(nopos, ftyp, makeSubstMap(ftyp.RParams().list(), Vn.targs), nil).(*Signature)
 		}
 
 		// If the methods have type parameters we don't care whether they
diff --git a/src/cmd/compile/internal/types2/named.go b/src/cmd/compile/internal/types2/named.go
index adf3eb3822..b12e59b586 100644
--- a/src/cmd/compile/internal/types2/named.go
+++ b/src/cmd/compile/internal/types2/named.go
@@ -153,7 +153,7 @@ func (t *Named) AddMethod(m *Func) {
 	}
 }
 
-func (t *Named) Underlying() Type { return t.load().underlying }
+func (t *Named) Underlying() Type { return t.load().expand(nil).underlying }
 func (t *Named) String() string   { return TypeString(t, nil) }
 
 // ----------------------------------------------------------------------------
@@ -166,9 +166,9 @@ func (t *Named) String() string   { return TypeString(t, nil) }
 // is detected, the result is Typ[Invalid]. If a cycle is detected and
 // n0.check != nil, the cycle is reported.
 func (n0 *Named) under() Type {
-	n0.expand()
+	n0.expand(nil)
 
-	u := n0.Underlying()
+	u := n0.load().underlying
 
 	if u == Typ[Invalid] {
 		return u
@@ -206,7 +206,7 @@ func (n0 *Named) under() Type {
 	seen := map[*Named]int{n0: 0}
 	path := []Object{n0.obj}
 	for {
-		u = n.Underlying()
+		u = n.load().underlying
 		if u == nil {
 			u = Typ[Invalid]
 			break
@@ -214,7 +214,7 @@ func (n0 *Named) under() Type {
 		var n1 *Named
 		switch u1 := u.(type) {
 		case *Named:
-			u1.expand()
+			u1.expand(nil)
 			n1 = u1
 		}
 		if n1 == nil {
@@ -264,15 +264,40 @@ type instance struct {
 
 // expand 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() {
+func (n *Named) expand(typMap map[string]*Named) *Named {
 	if n.instance != nil {
 		// n must be loaded before instantiation, in order to have accurate
 		// tparams. This is done implicitly by the call to n.TParams, but making it
 		// explicit is harmless: load is idempotent.
 		n.load()
-		inst := n.check.instantiate(n.instance.pos, n.orig.underlying, n.TParams().list(), n.targs, n.instance.posList)
+		if typMap == nil {
+			if n.check != nil {
+				typMap = n.check.typMap
+			} 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
+				// typMap, but don't want to create a duplicate of the current instance
+				// in the process of expansion.
+				h := instantiatedHash(n.orig, n.targs)
+				typMap = map[string]*Named{h: n}
+			}
+		}
+
+		inst := n.check.instantiate(n.instance.pos, n.orig.underlying, n.TParams().list(), n.targs, n.instance.posList, typMap)
 		n.underlying = inst
 		n.fromRHS = inst
 		n.instance = nil
 	}
+	return n
+}
+
+// safeUnderlying returns the underlying of typ without expanding instances, to
+// avoid infinite recursion.
+//
+// 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 typ.Underlying()
 }
diff --git a/src/cmd/compile/internal/types2/predicates.go b/src/cmd/compile/internal/types2/predicates.go
index 1541b3f416..070a0b3932 100644
--- a/src/cmd/compile/internal/types2/predicates.go
+++ b/src/cmd/compile/internal/types2/predicates.go
@@ -302,8 +302,8 @@ func identical(x, y Type, cmpTags bool, p *ifacePair) bool {
 		// Two named types are identical if their type names originate
 		// in the same type declaration.
 		if y, ok := y.(*Named); ok {
-			x.expand()
-			y.expand()
+			x.expand(nil)
+			y.expand(nil)
 			// TODO(gri) Why is x == y not sufficient? And if it is,
 			//           we can just return false here because x == y
 			//           is caught in the very beginning of this function.
diff --git a/src/cmd/compile/internal/types2/signature.go b/src/cmd/compile/internal/types2/signature.go
index 48b11b289c..c4c209b357 100644
--- a/src/cmd/compile/internal/types2/signature.go
+++ b/src/cmd/compile/internal/types2/signature.go
@@ -153,7 +153,7 @@ func (check *Checker) funcType(sig *Signature, recvPar *syntax.Field, tparams []
 					// TODO(gri) should we assume now that bounds always exist?
 					//           (no bound == empty interface)
 					if bound != nil {
-						bound = check.subst(tname.pos, bound, smap)
+						bound = check.subst(tname.pos, bound, smap, nil)
 						tname.typ.(*TypeParam).bound = bound
 					}
 				}
@@ -215,7 +215,7 @@ func (check *Checker) funcType(sig *Signature, recvPar *syntax.Field, tparams []
 			var err string
 			switch T := rtyp.(type) {
 			case *Named:
-				T.expand()
+				T.expand(nil)
 				// spec: "The type denoted by T is called the receiver base type; it must not
 				// be a pointer or interface type and it must be declared in the same package
 				// as the method."
diff --git a/src/cmd/compile/internal/types2/subst.go b/src/cmd/compile/internal/types2/subst.go
index 26796fc604..044544f1f9 100644
--- a/src/cmd/compile/internal/types2/subst.go
+++ b/src/cmd/compile/internal/types2/subst.go
@@ -51,7 +51,9 @@ func (m *substMap) lookup(tpar *TypeParam) Type {
 // subst is functional in the sense that it doesn't modify the incoming
 // type. If a substitution took place, the result type is different from
 // from the incoming type.
-func (check *Checker) subst(pos syntax.Pos, typ Type, smap *substMap) Type {
+//
+// If the given typMap is nil and check is non-nil, check.typMap is used.
+func (check *Checker) subst(pos syntax.Pos, typ Type, smap *substMap, typMap map[string]*Named) Type {
 	if smap.empty() {
 		return typ
 	}
@@ -68,16 +70,21 @@ func (check *Checker) subst(pos syntax.Pos, typ Type, smap *substMap) Type {
 	var subst subster
 	subst.pos = pos
 	subst.smap = smap
+
 	if check != nil {
 		subst.check = check
-		subst.typMap = check.typMap
-	} else {
+		if typMap == nil {
+			typMap = check.typMap
+		}
+	}
+	if typMap == nil {
 		// If we don't have a *Checker and its global type map,
 		// use a local version. Besides avoiding duplicate work,
 		// the type map prevents infinite recursive substitution
 		// for recursive types (example: type T[P any] *T[P]).
-		subst.typMap = make(map[string]*Named)
+		typMap = make(map[string]*Named)
 	}
+	subst.typMap = typMap
 
 	return subst.typ(typ)
 }
@@ -234,14 +241,15 @@ func (subst *subster) typ(typ Type) Type {
 
 		// create a new named type and populate typMap to avoid endless recursion
 		tname := NewTypeName(subst.pos, t.obj.pkg, t.obj.name, nil)
-		named := subst.check.newNamed(tname, t, t.Underlying(), t.TParams(), t.methods) // method signatures are updated lazily
+		t.load()
+		named := subst.check.newNamed(tname, t.orig, t.underlying, t.TParams(), t.methods) // method signatures are updated lazily
 		named.targs = new_targs
 		subst.typMap[h] = named
-		t.expand() // must happen after typMap update to avoid infinite recursion
+		t.expand(subst.typMap) // must happen after typMap update to avoid infinite recursion
 
 		// do the substitution
 		dump(">>> subst %s with %s (new: %s)", t.underlying, subst.smap, new_targs)
-		named.underlying = subst.typOrNil(t.Underlying())
+		named.underlying = subst.typOrNil(t.underlying)
 		dump(">>> underlying: %v", named.underlying)
 		assert(named.underlying != nil)
 		named.fromRHS = named.underlying // for cycle detection (Checker.validType)
diff --git a/src/cmd/compile/internal/types2/type.go b/src/cmd/compile/internal/types2/type.go
index 637829613b..4b8642aa96 100644
--- a/src/cmd/compile/internal/types2/type.go
+++ b/src/cmd/compile/internal/types2/type.go
@@ -116,7 +116,7 @@ func asInterface(t Type) *Interface {
 func asNamed(t Type) *Named {
 	e, _ := t.(*Named)
 	if e != nil {
-		e.expand()
+		e.expand(nil)
 	}
 	return e
 }
diff --git a/src/cmd/compile/internal/types2/typexpr.go b/src/cmd/compile/internal/types2/typexpr.go
index 6a9eacd31d..a53319c153 100644
--- a/src/cmd/compile/internal/types2/typexpr.go
+++ b/src/cmd/compile/internal/types2/typexpr.go
@@ -225,7 +225,7 @@ func (check *Checker) typInternal(e0 syntax.Expr, def *Named) (T Type) {
 				// Test case: type T[P any] *T[P]
 				// TODO(gri) investigate if that's a bug or to be expected
 				// (see also analogous comment in Checker.instantiate).
-				under = T.Underlying()
+				under = safeUnderlying(T)
 			}
 			if T == under {
 				check.trace(e0.Pos(), "=> %s // %s", T, goTypeName(T))
@@ -422,9 +422,13 @@ func (check *Checker) typOrNil(e syntax.Expr) Type {
 }
 
 func (check *Checker) instantiatedType(x syntax.Expr, targsx []syntax.Expr, def *Named) Type {
-	base := check.genericType(x, true)
-	if base == Typ[Invalid] {
-		return base // error already reported
+	gtyp := check.genericType(x, true)
+	if gtyp == Typ[Invalid] {
+		return gtyp // error already reported
+	}
+	base, _ := gtyp.(*Named)
+	if base == nil {
+		panic(fmt.Sprintf("%v: cannot instantiate %v", x.Pos(), gtyp))
 	}
 
 	// evaluate arguments
@@ -440,7 +444,7 @@ func (check *Checker) instantiatedType(x syntax.Expr, targsx []syntax.Expr, def
 		posList[i] = syntax.StartPos(arg)
 	}
 
-	typ := check.InstantiateLazy(x.Pos(), base, targs, posList, true)
+	typ := check.instantiateLazy(x.Pos(), base, targs, posList, true)
 	def.setUnderlying(typ)
 
 	// make sure we check instantiation works at least once
diff --git a/src/cmd/compile/internal/types2/unify.go b/src/cmd/compile/internal/types2/unify.go
index ae81382fb0..28f9cf751c 100644
--- a/src/cmd/compile/internal/types2/unify.go
+++ b/src/cmd/compile/internal/types2/unify.go
@@ -432,8 +432,8 @@ func (u *unifier) nify(x, y Type, p *ifacePair) bool {
 		// 	return x.obj == y.obj
 		// }
 		if y, ok := y.(*Named); ok {
-			x.expand()
-			y.expand()
+			x.expand(nil)
+			y.expand(nil)
 			// TODO(gri) This is not always correct: two types may have the same names
 			//           in the same package if one of them is nested in a function.
 			//           Extremely unlikely but we need an always correct solution.