go/types: return an error from Instantiate

This is a port of CL 342152 to go/types. Additionally, a panic was
removed from interface substitution, which is a fix from CL 333155 that
was previously missed.

A check for a nil Checker was also removed from types2.instantiate,
since check must not be nil in that method.

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

8 files changed, 203 insertions, 133 deletions

diff --git a/src/cmd/compile/internal/types2/instantiate.go b/src/cmd/compile/internal/types2/instantiate.go
index e0d889aa85..fdb8c40572 100644
--- a/src/cmd/compile/internal/types2/instantiate.go
+++ b/src/cmd/compile/internal/types2/instantiate.go
@@ -53,7 +53,8 @@ func Instantiate(check *Checker, typ Type, targs []Type, validate bool) (Type, e
 // later in the type checking pass. For Named types the resulting instance will
 // be unexpanded.
 func (check *Checker) instantiate(pos syntax.Pos, typ Type, targs []Type, posList []syntax.Pos) (res Type) {
-	if check != nil && check.conf.Trace {
+	assert(check != nil)
+	if check.conf.Trace {
 		check.trace(pos, "-- instantiating %s with %s", typ, typeListString(targs))
 		check.indent++
 		defer func() {
@@ -69,7 +70,6 @@ func (check *Checker) instantiate(pos syntax.Pos, typ Type, targs []Type, posLis
 		}()
 	}
 
-	assert(check != nil)
 	inst := check.instance(pos, typ, targs)
 
 	assert(len(posList) <= len(targs))
diff --git a/src/go/types/api.go b/src/go/types/api.go
index 315f77f362..b8e772ada0 100644
--- a/src/go/types/api.go
+++ b/src/go/types/api.go
@@ -62,6 +62,18 @@ func (err Error) Error() string {
 	return fmt.Sprintf("%s: %s", err.Fset.Position(err.Pos), err.Msg)
 }
 
+// An ArgumentError holds an error associated with an argument index.
+type ArgumentError struct {
+	index int
+	error
+}
+
+// Index returns the positional index of the argument associated with the
+// error.
+func (e ArgumentError) Index() int {
+	return e.index
+}
+
 // An Importer resolves import paths to Packages.
 //
 // CAUTION: This interface does not support the import of locally
diff --git a/src/go/types/api_test.go b/src/go/types/api_test.go
index a49f2113b9..7a0419bfd5 100644
--- a/src/go/types/api_test.go
+++ b/src/go/types/api_test.go
@@ -1856,8 +1856,10 @@ func TestInstantiate(t *testing.T) {
 
 	// instantiation should succeed (no endless recursion)
 	// even with a nil *Checker
-	var check *Checker
-	res := check.Instantiate(token.NoPos, T, []Type{Typ[Int]}, nil, false)
+	res, err := Instantiate(nil, T, []Type{Typ[Int]}, false)
+	if err != nil {
+		t.Fatal(err)
+	}
 
 	// instantiated type should point to itself
 	if p := res.Underlying().(*Pointer).Elem(); p != res {
@@ -1865,6 +1867,39 @@ func TestInstantiate(t *testing.T) {
 	}
 }
 
+func TestInstantiateErrors(t *testing.T) {
+	tests := []struct {
+		src    string // by convention, T must be the type being instantiated
+		targs  []Type
+		wantAt int // -1 indicates no error
+	}{
+		{"type T[P interface{~string}] int", []Type{Typ[Int]}, 0},
+		{"type T[P1 interface{int}, P2 interface{~string}] int", []Type{Typ[Int], Typ[Int]}, 1},
+		{"type T[P1 any, P2 interface{~[]P1}] int", []Type{Typ[Int], NewSlice(Typ[String])}, 1},
+		{"type T[P1 interface{~[]P2}, P2 any] int", []Type{NewSlice(Typ[String]), Typ[Int]}, 0},
+	}
+
+	for _, test := range tests {
+		src := genericPkg + "p; " + test.src
+		pkg, err := pkgFor(".", src, nil)
+		if err != nil {
+			t.Fatal(err)
+		}
+
+		T := pkg.Scope().Lookup("T").Type().(*Named)
+
+		_, err = Instantiate(nil, T, test.targs, true)
+		if err == nil {
+			t.Fatalf("Instantiate(%v, %v) returned nil error, want non-nil", T, test.targs)
+		}
+
+		gotAt := err.(ArgumentError).Index()
+		if gotAt != test.wantAt {
+			t.Errorf("Instantate(%v, %v): error at index %d, want index %d", T, test.targs, gotAt, test.wantAt)
+		}
+	}
+}
+
 func TestInstanceIdentity(t *testing.T) {
 	imports := make(testImporter)
 	conf := Config{Importer: imports}
diff --git a/src/go/types/call.go b/src/go/types/call.go
index 08ef2451bf..87eeef444b 100644
--- a/src/go/types/call.go
+++ b/src/go/types/call.go
@@ -60,7 +60,7 @@ func (check *Checker) funcInst(x *operand, ix *typeparams.IndexExpr) {
 	}
 
 	// instantiate function signature
-	res := check.Instantiate(x.Pos(), sig, targs, poslist, true).(*Signature)
+	res := check.instantiate(x.Pos(), sig, targs, poslist).(*Signature)
 	assert(res.TParams().Len() == 0) // signature is not generic anymore
 	if inferred {
 		check.recordInferred(ix.Orig, targs, res)
@@ -332,7 +332,7 @@ func (check *Checker) arguments(call *ast.CallExpr, sig *Signature, targs []Type
 		}
 
 		// compute result signature
-		rsig = check.Instantiate(call.Pos(), sig, targs, nil, true).(*Signature)
+		rsig = check.instantiate(call.Pos(), sig, targs, nil).(*Signature)
 		assert(rsig.TParams().Len() == 0) // signature is not generic anymore
 		check.recordInferred(call, targs, rsig)
 
diff --git a/src/go/types/instantiate.go b/src/go/types/instantiate.go
index 86e5e202c4..50341e064c 100644
--- a/src/go/types/instantiate.go
+++ b/src/go/types/instantiate.go
@@ -13,25 +13,124 @@ import (
 	"go/token"
 )
 
-// Instantiate instantiates the type typ with the given type arguments
-// targs. To check type constraint satisfaction, verify must be set.
-// pos and posList correspond to the instantiation and type argument
-// positions respectively; posList may be nil or shorter than the number
-// of type arguments provided.
-// typ must be a *Named or a *Signature type, and its number of type
-// parameters must match the number of provided type arguments.
-// The receiver (check) may be nil if and only if verify is not set.
-// The result is a new, instantiated (not generic) type of the same kind
-// (either a *Named or a *Signature).
-// Any methods attached to a *Named are simply copied; they are not
-// instantiated.
-func (check *Checker) Instantiate(pos token.Pos, typ Type, targs []Type, posList []token.Pos, verify bool) (res Type) {
-	var inst Type
+// Instantiate instantiates the type typ with the given type arguments targs.
+// typ must be a *Named or a *Signature type, and its number of type parameters
+// must match the number of provided type arguments. The result is a new,
+// instantiated (not parameterized) type of the same kind (either a *Named or a
+// *Signature). Any methods attached to a *Named are simply copied; they are
+// not instantiated.
+//
+// If check is non-nil, it will be used to de-dupe the instance against
+// previous instances with the same identity.
+//
+// If verify is set and constraint satisfaction fails, the returned error may
+// be of dynamic type ArgumentError indicating which type argument did not
+// satisfy its corresponding type parameter constraint, and why.
+//
+// TODO(rfindley): change this function to also return an error if lengths of
+// tparams and targs do not match.
+func Instantiate(check *Checker, typ Type, targs []Type, validate bool) (Type, error) {
+	inst := check.instance(token.NoPos, typ, targs)
+
+	var err error
+	if validate {
+		var tparams []*TypeName
+		switch t := typ.(type) {
+		case *Named:
+			tparams = t.TParams().list()
+		case *Signature:
+			tparams = t.TParams().list()
+		}
+		if i, err := check.verify(token.NoPos, tparams, targs); err != nil {
+			return inst, ArgumentError{i, err}
+		}
+	}
+
+	return inst, err
+}
+
+// instantiate creates an instance and defers verification of constraints to
+// later in the type checking pass. For Named types the resulting instance will
+// be unexpanded.
+func (check *Checker) instantiate(pos token.Pos, typ Type, targs []Type, posList []token.Pos) (res Type) {
+	assert(check != nil)
+	if trace {
+		check.trace(pos, "-- instantiating %s with %s", typ, typeListString(targs))
+		check.indent++
+		defer func() {
+			check.indent--
+			var under Type
+			if res != nil {
+				// 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 = safeUnderlying(res)
+			}
+			check.trace(pos, "=> %s (under = %s)", res, under)
+		}()
+	}
+
+	inst := check.instance(pos, typ, targs)
+
+	assert(len(posList) <= len(targs))
+	check.later(func() {
+		// Collect tparams again because lazily loaded *Named types may not have
+		// had tparams set up above.
+		var tparams []*TypeName
+		switch t := typ.(type) {
+		case *Named:
+			tparams = t.TParams().list()
+		case *Signature:
+			tparams = t.TParams().list()
+		}
+		// Avoid duplicate errors; instantiate will have complained if tparams
+		// and targs do not have the same length.
+		if len(tparams) == len(targs) {
+			if i, err := check.verify(pos, tparams, targs); err != nil {
+				// best position for error reporting
+				pos := pos
+				if i < len(posList) {
+					pos = posList[i]
+				}
+				check.softErrorf(atPos(pos), _Todo, err.Error())
+			}
+		}
+	})
+	return inst
+}
+
+// instance creates a type or function instance using the given original type
+// typ and arguments targs. For Named types the resulting instance will be
+// unexpanded.
+func (check *Checker) instance(pos token.Pos, typ Type, targs []Type) (res Type) {
+	// TODO(gri) What is better here: work with TypeParams, or work with TypeNames?
 	switch t := typ.(type) {
 	case *Named:
-		inst = check.instantiateLazy(pos, t, targs)
+		h := instantiatedHash(t, targs)
+		if check != nil {
+			// typ may already have been instantiated with identical type arguments. In
+			// that case, re-use the existing instance.
+			if named := check.typMap[h]; named != nil {
+				return named
+			}
+		}
+
+		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.targs = targs
+		named.instance = &instance{pos}
+		if check != nil {
+			check.typMap[h] = named
+		}
+		res = named
 	case *Signature:
-		tparams := t.TParams().list()
+		tparams := t.TParams()
+		if !check.validateTArgLen(pos, tparams, targs) {
+			return Typ[Invalid]
+		}
+		if tparams.Len() == 0 {
+			return typ // nothing to do (minor optimization)
+		}
 		defer func() {
 			// If we had an unexpected failure somewhere don't panic below when
 			// asserting res.(*Signature). Check for *Signature in case Typ[Invalid]
@@ -50,103 +149,27 @@ func (check *Checker) Instantiate(pos token.Pos, typ Type, targs []Type, posList
 			// anymore; we need to set tparams to nil.
 			res.(*Signature).tparams = nil
 		}()
-		inst = check.instantiate(pos, typ, tparams, targs, nil)
+		res = check.subst(pos, typ, makeSubstMap(tparams.list(), targs), nil)
 	default:
 		// only types and functions can be generic
 		panic(fmt.Sprintf("%v: cannot instantiate %v", pos, typ))
 	}
-
-	if verify {
-		if check == nil {
-			panic("cannot have nil Checker if verifying constraints")
-		}
-		assert(len(posList) <= len(targs))
-		check.later(func() {
-			// Collect tparams again because lazily loaded *Named types may not have
-			// had tparams set up above.
-			var tparams []*TypeName
-			switch t := typ.(type) {
-			case *Named:
-				tparams = t.TParams().list()
-			case *Signature:
-				tparams = t.TParams().list()
-			}
-			// Avoid duplicate errors; instantiate will have complained if tparams
-			// and targs do not have the same length.
-			if len(tparams) == len(targs) {
-				if i, err := check.verify(pos, tparams, targs); err != nil {
-					// best position for error reporting
-					pos := pos
-					if i < len(posList) {
-						pos = posList[i]
-					}
-					check.softErrorf(atPos(pos), _Todo, err.Error())
-				}
-			}
-		})
-	}
-
-	return inst
+	return res
 }
 
-func (check *Checker) instantiate(pos token.Pos, typ Type, tparams []*TypeName, targs []Type, typMap map[string]*Named) (res Type) {
-	// the number of supplied types must match the number of type parameters
-	if len(targs) != len(tparams) {
+// validateTArgLen verifies that the length of targs and tparams matches,
+// reporting an error if not. If validation fails and check is nil,
+// validateTArgLen panics.
+func (check *Checker) validateTArgLen(pos token.Pos, tparams *TParamList, targs []Type) bool {
+	if len(targs) != tparams.Len() {
 		// TODO(gri) provide better error message
 		if check != nil {
-			check.errorf(atPos(pos), _Todo, "got %d arguments but %d type parameters", len(targs), len(tparams))
-			return Typ[Invalid]
+			check.errorf(atPos(pos), _Todo, "got %d arguments but %d type parameters", len(targs), tparams.Len())
+			return false
 		}
-		panic(fmt.Sprintf("%v: got %d arguments but %d type parameters", pos, len(targs), len(tparams)))
+		panic(fmt.Sprintf("%v: got %d arguments but %d type parameters", pos, len(targs), tparams.Len()))
 	}
-
-	if check != nil && trace {
-		check.trace(pos, "-- instantiating %s with %s", typ, typeListString(targs))
-		check.indent++
-		defer func() {
-			check.indent--
-			var under Type
-			if res != nil {
-				// 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 = safeUnderlying(res)
-			}
-			check.trace(pos, "=> %s (under = %s)", res, under)
-		}()
-	}
-
-	// TODO(gri) What is better here: work with TypeParams, or work with TypeNames?
-
-	if len(tparams) == 0 {
-		return typ // nothing to do (minor optimization)
-	}
-
-	return check.subst(pos, typ, makeSubstMap(tparams, targs), typMap)
-}
-
-// instantiateLazy avoids actually instantiating the type until needed. typ
-// must be a *Named type.
-func (check *Checker) instantiateLazy(pos token.Pos, orig *Named, targs []Type) Type {
-	h := instantiatedHash(orig, targs)
-	if check != nil {
-		// typ may already have been instantiated with identical type arguments. In
-		// that case, re-use the existing instance.
-		if named := check.typMap[h]; named != nil {
-			return named
-		}
-	}
-
-	tname := NewTypeName(pos, orig.obj.pkg, orig.obj.name, nil)
-	named := check.newNamed(tname, orig, nil, nil, nil) // methods and tparams are set when named is loaded
-	named.targs = targs
-	named.instance = &instance{pos}
-
-	if check != nil {
-		check.typMap[h] = named
-	}
-
-	return named
+	return true
 }
 
 func (check *Checker) verify(pos token.Pos, tparams []*TypeName, targs []Type) (int, error) {
diff --git a/src/go/types/named.go b/src/go/types/named.go
index d621e5ef21..d547c47f8e 100644
--- a/src/go/types/named.go
+++ b/src/go/types/named.go
@@ -262,22 +262,26 @@ func (n *Named) expand(typMap map[string]*Named) *Named {
 		// tparams. This is done implicitly by the call to n.TParams, but making it
 		// explicit is harmless: load is idempotent.
 		n.load()
-		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}
+		var u Type
+		if n.check.validateTArgLen(n.instance.pos, n.tparams, n.targs) {
+			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}
+				}
 			}
+			u = n.check.subst(n.instance.pos, n.orig.underlying, makeSubstMap(n.TParams().list(), n.targs), typMap)
+		} else {
+			u = Typ[Invalid]
 		}
-
-		inst := n.check.instantiate(n.instance.pos, n.orig.underlying, n.TParams().list(), n.targs, typMap)
-		n.underlying = inst
-		n.fromRHS = inst
+		n.underlying = u
+		n.fromRHS = u
 		n.instance = nil
 	}
 	return n
diff --git a/src/go/types/subst.go b/src/go/types/subst.go
index e47d20774f..72d5cac671 100644
--- a/src/go/types/subst.go
+++ b/src/go/types/subst.go
@@ -38,13 +38,12 @@ func (m substMap) lookup(tpar *TypeParam) Type {
 	return tpar
 }
 
-// subst returns the type typ with its type parameters tpars replaced by
-// the corresponding type arguments targs, recursively.
-// 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.
+// subst returns the type typ with its type parameters tpars replaced by the
+// corresponding type arguments targs, recursively. subst is pure 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.
 //
-// If the given typMap is nil and check is non-nil, check.typMap is used.
+// If the given typMap is non-nil, it is used in lieu of check.typMap.
 func (check *Checker) subst(pos token.Pos, typ Type, smap substMap, typMap map[string]*Named) Type {
 	if smap.empty() {
 		return typ
@@ -157,9 +156,6 @@ func (subst *subster) typ(typ Type) Type {
 		embeddeds, ecopied := subst.typeList(t.embeddeds)
 		if mcopied || ecopied {
 			iface := &Interface{methods: methods, embeddeds: embeddeds, complete: t.complete}
-			if subst.check == nil {
-				panic("internal error: cannot instantiate interfaces yet")
-			}
 			return iface
 		}
 
diff --git a/src/go/types/typexpr.go b/src/go/types/typexpr.go
index def5871ce7..baa4e3c2d0 100644
--- a/src/go/types/typexpr.go
+++ b/src/go/types/typexpr.go
@@ -433,7 +433,7 @@ func (check *Checker) instantiatedType(x ast.Expr, targsx []ast.Expr, def *Named
 		posList[i] = arg.Pos()
 	}
 
-	typ := check.Instantiate(x.Pos(), base, targs, posList, true)
+	typ := check.instantiate(x.Pos(), base, targs, posList)
 	def.setUnderlying(typ)
 
 	// make sure we check instantiation works at least once