1 files changed, 121 insertions, 260 deletions

diff --git a/src/go/types/subst.go b/src/go/types/subst.go
index 931375f1f2..8b8d6fb82a 100644
--- a/src/go/types/subst.go
+++ b/src/go/types/subst.go
@@ -2,218 +2,49 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// This file implements instantiation of generic types
-// through substitution of type parameters by actual
-// types.
+// This file implements type parameter substitution.
 
 package types
 
 import (
 	"bytes"
-	"fmt"
 	"go/token"
 )
 
 // TODO(rFindley) decide error codes for the errors in this file, and check
 //                if error spans can be improved
 
-type substMap struct {
-	// The targs field is currently needed for *Named type substitution.
-	// TODO(gri) rewrite that code, get rid of this field, and make this
-	//           struct just the map (proj)
-	targs []Type
-	proj  map[*_TypeParam]Type
-}
+type substMap map[*TypeParam]Type
 
 // makeSubstMap creates a new substitution map mapping tpars[i] to targs[i].
 // If targs[i] is nil, tpars[i] is not substituted.
-func makeSubstMap(tpars []*TypeName, targs []Type) *substMap {
+func makeSubstMap(tpars []*TypeParam, targs []Type) substMap {
 	assert(len(tpars) == len(targs))
-	proj := make(map[*_TypeParam]Type, len(tpars))
+	proj := make(substMap, len(tpars))
 	for i, tpar := range tpars {
-		// We must expand type arguments otherwise *instance
-		// types end up as components in composite types.
-		// TODO(gri) explain why this causes problems, if it does
-		targ := expand(targs[i]) // possibly nil
-		targs[i] = targ
-		proj[tpar.typ.(*_TypeParam)] = targ
+		proj[tpar] = targs[i]
 	}
-	return &substMap{targs, proj}
-}
-
-func (m *substMap) String() string {
-	return fmt.Sprintf("%s", m.proj)
+	return proj
 }
 
-func (m *substMap) empty() bool {
-	return len(m.proj) == 0
+func (m substMap) empty() bool {
+	return len(m) == 0
 }
 
-func (m *substMap) lookup(tpar *_TypeParam) Type {
-	if t := m.proj[tpar]; t != nil {
+func (m substMap) lookup(tpar *TypeParam) Type {
+	if t := m[tpar]; t != nil {
 		return t
 	}
 	return tpar
 }
 
-func (check *Checker) instantiate(pos token.Pos, typ Type, targs []Type, poslist []token.Pos) (res Type) {
-	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 = res.Underlying()
-			}
-			check.trace(pos, "=> %s (under = %s)", res, under)
-		}()
-	}
-
-	assert(len(poslist) <= len(targs))
-
-	// TODO(gri) What is better here: work with TypeParams, or work with TypeNames?
-	var tparams []*TypeName
-	switch t := typ.(type) {
-	case *Named:
-		tparams = t.tparams
-	case *Signature:
-		tparams = t.tparams
-		defer func() {
-			// If we had an unexpected failure somewhere don't panic below when
-			// asserting res.(*Signature). Check for *Signature in case Typ[Invalid]
-			// is returned.
-			if _, ok := res.(*Signature); !ok {
-				return
-			}
-			// If the signature doesn't use its type parameters, subst
-			// will not make a copy. In that case, make a copy now (so
-			// we can set tparams to nil w/o causing side-effects).
-			if t == res {
-				copy := *t
-				res = &copy
-			}
-			// After instantiating a generic signature, it is not generic
-			// anymore; we need to set tparams to nil.
-			res.(*Signature).tparams = nil
-		}()
-
-	default:
-		check.dump("%v: cannot instantiate %v", pos, typ)
-		unreachable() // only defined types and (defined) functions can be generic
-	}
-
-	// the number of supplied types must match the number of type parameters
-	if len(targs) != len(tparams) {
-		// TODO(gri) provide better error message
-		check.errorf(atPos(pos), _Todo, "got %d arguments but %d type parameters", len(targs), len(tparams))
-		return Typ[Invalid]
-	}
-
-	if len(tparams) == 0 {
-		return typ // nothing to do (minor optimization)
-	}
-
-	smap := makeSubstMap(tparams, targs)
-
-	// check bounds
-	for i, tname := range tparams {
-		tpar := tname.typ.(*_TypeParam)
-		iface := tpar.Bound()
-		if iface.Empty() {
-			continue // no type bound
-		}
-
-		targ := targs[i]
-
-		// best position for error reporting
-		pos := pos
-		if i < len(poslist) {
-			pos = poslist[i]
-		}
-
-		// The type parameter bound is parameterized with the same type parameters
-		// 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)
-
-		// targ must implement iface (methods)
-		// - check only if we have methods
-		check.completeInterface(token.NoPos, iface)
-		if len(iface.allMethods) > 0 {
-			// If the type argument is a pointer to a type parameter, the type argument's
-			// method set is empty.
-			// TODO(gri) is this what we want? (spec question)
-			if base, isPtr := deref(targ); isPtr && asTypeParam(base) != nil {
-				check.errorf(atPos(pos), 0, "%s has no methods", targ)
-				break
-			}
-			if m, wrong := check.missingMethod(targ, iface, true); m != nil {
-				// TODO(gri) needs to print updated name to avoid major confusion in error message!
-				//           (print warning for now)
-				// Old warning:
-				// check.softErrorf(pos, "%s does not satisfy %s (warning: name not updated) = %s (missing method %s)", targ, tpar.bound, iface, m)
-				if m.name == "==" {
-					// We don't want to report "missing method ==".
-					check.softErrorf(atPos(pos), 0, "%s does not satisfy comparable", targ)
-				} else if wrong != nil {
-					// TODO(gri) This can still report uninstantiated types which makes the error message
-					//           more difficult to read then necessary.
-					// TODO(rFindley) should this use parentheses rather than ':' for qualification?
-					check.softErrorf(atPos(pos), _Todo,
-						"%s does not satisfy %s: wrong method signature\n\tgot  %s\n\twant %s",
-						targ, tpar.bound, wrong, m,
-					)
-				} else {
-					check.softErrorf(atPos(pos), 0, "%s does not satisfy %s (missing method %s)", targ, tpar.bound, m.name)
-				}
-				break
-			}
-		}
-
-		// targ's underlying type must also be one of the interface types listed, if any
-		if iface.allTypes == nil {
-			continue // nothing to do
-		}
-
-		// If targ is itself a type parameter, each of its possible types, but at least one, must be in the
-		// list of iface types (i.e., the targ type list must be a non-empty subset of the iface types).
-		if targ := asTypeParam(targ); targ != nil {
-			targBound := targ.Bound()
-			if targBound.allTypes == nil {
-				check.softErrorf(atPos(pos), _Todo, "%s does not satisfy %s (%s has no type constraints)", targ, tpar.bound, targ)
-				break
-			}
-			for _, t := range unpackType(targBound.allTypes) {
-				if !iface.isSatisfiedBy(t) {
-					// TODO(gri) match this error message with the one below (or vice versa)
-					check.softErrorf(atPos(pos), 0, "%s does not satisfy %s (%s type constraint %s not found in %s)", targ, tpar.bound, targ, t, iface.allTypes)
-					break
-				}
-			}
-			break
-		}
-
-		// Otherwise, targ's type or underlying type must also be one of the interface types listed, if any.
-		if !iface.isSatisfiedBy(targ) {
-			check.softErrorf(atPos(pos), _Todo, "%s does not satisfy %s (%s or %s not found in %s)", targ, tpar.bound, targ, under(targ), iface.allTypes)
-			break
-		}
-	}
-
-	return check.subst(pos, typ, smap)
-}
-
-// 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.
-func (check *Checker) subst(pos token.Pos, typ Type, smap *substMap) 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 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
 	}
@@ -222,20 +53,38 @@ func (check *Checker) subst(pos token.Pos, typ Type, smap *substMap) Type {
 	switch t := typ.(type) {
 	case *Basic:
 		return typ // nothing to do
-	case *_TypeParam:
+	case *TypeParam:
 		return smap.lookup(t)
 	}
 
 	// general case
-	subst := subster{check, pos, make(map[Type]Type), smap}
+	var subst subster
+	subst.pos = pos
+	subst.smap = smap
+
+	if check != nil {
+		subst.check = check
+		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]).
+		typMap = make(map[string]*Named)
+	}
+	subst.typMap = typMap
+
 	return subst.typ(typ)
 }
 
 type subster struct {
-	check *Checker
-	pos   token.Pos
-	cache map[Type]Type
-	smap  *substMap
+	pos    token.Pos
+	smap   substMap
+	check  *Checker // nil if called via Instantiate
+	typMap map[string]*Named
 }
 
 func (subst *subster) typ(typ Type) Type {
@@ -244,7 +93,7 @@ func (subst *subster) typ(typ Type) Type {
 		// Call typOrNil if it's possible that typ is nil.
 		panic("nil typ")
 
-	case *Basic, *bottom, *top:
+	case *Basic, *top:
 		// nothing to do
 
 	case *Array:
@@ -293,26 +142,20 @@ func (subst *subster) typ(typ Type) Type {
 			}
 		}
 
-	case *_Sum:
-		types, copied := subst.typeList(t.types)
+	case *Union:
+		terms, copied := subst.termlist(t.terms)
 		if copied {
-			// Don't do it manually, with a Sum literal: the new
-			// types list may not be unique and NewSum may remove
-			// duplicates.
-			return _NewSum(types)
+			// term list substitution may introduce duplicate terms (unlikely but possible).
+			// This is ok; lazy type set computation will determine the actual type set
+			// in normal form.
+			return &Union{terms, nil}
 		}
 
 	case *Interface:
 		methods, mcopied := subst.funcList(t.methods)
-		types := t.types
-		if t.types != nil {
-			types = subst.typ(t.types)
-		}
 		embeddeds, ecopied := subst.typeList(t.embeddeds)
-		if mcopied || types != t.types || ecopied {
-			iface := &Interface{methods: methods, types: types, embeddeds: embeddeds}
-			subst.check.posMap[iface] = subst.check.posMap[t] // satisfy completeInterface requirement
-			subst.check.completeInterface(token.NoPos, iface)
+		if mcopied || ecopied {
+			iface := &Interface{methods: methods, embeddeds: embeddeds, complete: t.complete}
 			return iface
 		}
 
@@ -330,85 +173,82 @@ func (subst *subster) typ(typ Type) Type {
 		}
 
 	case *Named:
-		subst.check.indent++
-		defer func() {
-			subst.check.indent--
-		}()
-		dump := func(format string, args ...interface{}) {
-			if trace {
+		// dump is for debugging
+		dump := func(string, ...interface{}) {}
+		if subst.check != nil && trace {
+			subst.check.indent++
+			defer func() {
+				subst.check.indent--
+			}()
+			dump = func(format string, args ...interface{}) {
 				subst.check.trace(subst.pos, format, args...)
 			}
 		}
 
-		if t.tparams == nil {
+		if t.TParams().Len() == 0 {
 			dump(">>> %s is not parameterized", t)
 			return t // type is not parameterized
 		}
 
-		var newTargs []Type
-
-		if len(t.targs) > 0 {
-			// already instantiated
-			dump(">>> %s already instantiated", t)
-			assert(len(t.targs) == len(t.tparams))
-			// For each (existing) type argument targ, determine if it needs
-			// to be substituted; i.e., if it is or contains a type parameter
-			// that has a type argument for it.
-			for i, targ := range t.targs {
-				dump(">>> %d targ = %s", i, targ)
-				newTarg := subst.typ(targ)
-				if newTarg != targ {
-					dump(">>> substituted %d targ %s => %s", i, targ, newTarg)
-					if newTargs == nil {
-						newTargs = make([]Type, len(t.tparams))
-						copy(newTargs, t.targs)
-					}
-					newTargs[i] = newTarg
+		var newTArgs []Type
+		assert(t.targs.Len() == t.TParams().Len())
+
+		// already instantiated
+		dump(">>> %s already instantiated", t)
+		// For each (existing) type argument targ, determine if it needs
+		// to be substituted; i.e., if it is or contains a type parameter
+		// that has a type argument for it.
+		for i, targ := range t.targs.list() {
+			dump(">>> %d targ = %s", i, targ)
+			new_targ := subst.typ(targ)
+			if new_targ != targ {
+				dump(">>> substituted %d targ %s => %s", i, targ, new_targ)
+				if newTArgs == nil {
+					newTArgs = make([]Type, t.TParams().Len())
+					copy(newTArgs, t.targs.list())
 				}
+				newTArgs[i] = new_targ
 			}
+		}
 
-			if newTargs == nil {
-				dump(">>> nothing to substitute in %s", t)
-				return t // nothing to substitute
-			}
-		} else {
-			// not yet instantiated
-			dump(">>> first instantiation of %s", t)
-			// TODO(rFindley) can we instead subst the tparam types here?
-			newTargs = subst.smap.targs
+		if newTArgs == nil {
+			dump(">>> nothing to substitute in %s", t)
+			return t // nothing to substitute
 		}
 
 		// before creating a new named type, check if we have this one already
-		h := instantiatedHash(t, newTargs)
+		h := instantiatedHash(t, newTArgs)
 		dump(">>> new type hash: %s", h)
-		if named, found := subst.check.typMap[h]; found {
+		if named, found := subst.typMap[h]; found {
 			dump(">>> found %s", named)
-			subst.cache[t] = named
 			return named
 		}
 
-		// create a new named type and populate caches to avoid endless recursion
+		// Create a new named type and populate typMap 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)
-		named := subst.check.newNamed(tname, t.underlying, t.methods) // method signatures are updated lazily
-		named.tparams = t.tparams                                     // new type is still parameterized
-		named.targs = newTargs
-		subst.check.typMap[h] = named
-		subst.cache[t] = named
+		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 = &TypeList{newTArgs}
+		subst.typMap[h] = named
+		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, newTargs)
+		dump(">>> subst %s with %s (new: %s)", t.underlying, subst.smap, newTArgs)
 		named.underlying = subst.typOrNil(t.underlying)
-		named.orig = named.underlying // for cycle detection (Checker.validType)
+		dump(">>> underlying: %v", named.underlying)
+		assert(named.underlying != nil)
+		named.fromRHS = named.underlying // for consistency, though no cycle detection is necessary
 
 		return named
 
-	case *_TypeParam:
+	case *TypeParam:
 		return subst.smap.lookup(t)
 
-	case *instance:
-		// TODO(gri) can we avoid the expansion here and just substitute the type parameters?
-		return subst.typ(t.expand())
-
 	default:
 		panic("unimplemented")
 	}
@@ -416,14 +256,17 @@ func (subst *subster) typ(typ Type) Type {
 	return typ
 }
 
-// TODO(gri) Eventually, this should be more sophisticated.
-//           It won't work correctly for locally declared types.
+var instanceHashing = 0
+
 func instantiatedHash(typ *Named, targs []Type) string {
+	assert(instanceHashing == 0)
+	instanceHashing++
 	var buf bytes.Buffer
 	writeTypeName(&buf, typ.obj, nil)
 	buf.WriteByte('[')
 	writeTypeList(&buf, targs, nil, nil)
 	buf.WriteByte(']')
+	instanceHashing--
 
 	// With respect to the represented type, whether a
 	// type is fully expanded or stored as instance
@@ -541,3 +384,21 @@ func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
 	}
 	return
 }
+
+func (subst *subster) termlist(in []*Term) (out []*Term, copied bool) {
+	out = in
+	for i, t := range in {
+		if u := subst.typ(t.typ); u != t.typ {
+			if !copied {
+				// first function that got substituted => allocate new out slice
+				// and copy all functions
+				new := make([]*Term, len(in))
+				copy(new, out)
+				out = new
+				copied = true
+			}
+			out[i] = NewTerm(t.tilde, u)
+		}
+	}
+	return
+}