1 files changed, 539 insertions, 12 deletions

diff --git a/src/cmd/compile/internal/typecheck/subr.go b/src/cmd/compile/internal/typecheck/subr.go
index 9ee7a94b1f..e86c4c6bca 100644
--- a/src/cmd/compile/internal/typecheck/subr.go
+++ b/src/cmd/compile/internal/typecheck/subr.go
@@ -5,6 +5,7 @@
 package typecheck
 
 import (
+	"bytes"
 	"fmt"
 	"sort"
 	"strconv"
@@ -352,9 +353,10 @@ func Assignop(src, dst *types.Type) (ir.Op, string) {
 		return ir.OCONVNOP, ""
 	}
 
-	// 2. src and dst have identical underlying types
-	// and either src or dst is not a named type or
-	// both are empty interface types.
+	// 2. src and dst have identical underlying types and
+	//   a. either src or dst is not a named type, or
+	//   b. both are empty interface types, or
+	//   c. at least one is a gcshape type.
 	// For assignable but different non-empty interface types,
 	// we want to recompute the itab. Recomputing the itab ensures
 	// that itabs are unique (thus an interface with a compile-time
@@ -371,21 +373,24 @@ func Assignop(src, dst *types.Type) (ir.Op, string) {
 			// which need to have their itab updated.
 			return ir.OCONVNOP, ""
 		}
+		if src.IsShape() || dst.IsShape() {
+			// Conversion between a shape type and one of the types
+			// it represents also needs no conversion.
+			return ir.OCONVNOP, ""
+		}
 	}
 
 	// 3. dst is an interface type and src implements dst.
 	if dst.IsInterface() && src.Kind() != types.TNIL {
 		var missing, have *types.Field
 		var ptr int
+		if src.IsShape() {
+			// Shape types implement things they have already
+			// been typechecked to implement, even if they
+			// don't have the methods for them.
+			return ir.OCONVIFACE, ""
+		}
 		if implements(src, dst, &missing, &have, &ptr) {
-			// Call NeedITab/ITabAddr so that (src, dst)
-			// gets added to itabs early, which allows
-			// us to de-virtualize calls through this
-			// type/interface pair later. See CompileITabs in reflect.go
-			if types.IsDirectIface(src) && !dst.IsEmptyInterface() {
-				NeedITab(src, dst)
-			}
-
 			return ir.OCONVIFACE, ""
 		}
 
@@ -722,13 +727,23 @@ func ifacelookdot(s *types.Sym, t *types.Type, ignorecase bool) (m *types.Field,
 	return m, followptr
 }
 
+// implements reports whether t implements the interface iface. t can be
+// an interface, a type parameter, or a concrete type. If implements returns
+// false, it stores a method of iface that is not implemented in *m. If the
+// method name matches but the type is wrong, it additionally stores the type
+// of the method (on t) in *samename.
 func implements(t, iface *types.Type, m, samename **types.Field, ptr *int) bool {
 	t0 := t
 	if t == nil {
 		return false
 	}
 
-	if t.IsInterface() {
+	if t.IsInterface() || t.IsTypeParam() {
+		if t.IsTypeParam() {
+			// A typeparam satisfies an interface if its type bound
+			// has all the methods of that interface.
+			t = t.Bound()
+		}
 		i := 0
 		tms := t.AllMethods().Slice()
 		for _, im := range iface.AllMethods().Slice() {
@@ -874,3 +889,515 @@ var slist []symlink
 type symlink struct {
 	field *types.Field
 }
+
+// TypesOf converts a list of nodes to a list
+// of types of those nodes.
+func TypesOf(x []ir.Node) []*types.Type {
+	r := make([]*types.Type, len(x))
+	for i, n := range x {
+		r[i] = n.Type()
+	}
+	return r
+}
+
+// makeGenericName returns the name of the generic function instantiated
+// with the given types.
+// name is the name of the generic function or method.
+func makeGenericName(name string, targs []*types.Type, hasBrackets bool) string {
+	b := bytes.NewBufferString("")
+
+	// Determine if the type args are concrete types or new typeparams.
+	hasTParam := false
+	for _, targ := range targs {
+		if hasTParam {
+			assert(targ.HasTParam() || targ.HasShape())
+		} else if targ.HasTParam() || targ.HasShape() {
+			hasTParam = true
+		}
+	}
+
+	// Marker to distinguish generic instantiations from fully stenciled wrapper functions.
+	// Once we move to GC shape implementations, this prefix will not be necessary as the
+	// GC shape naming will distinguish them.
+	// e.g. f[8bytenonpointer] vs. f[int].
+	// For now, we use .inst.f[int] vs. f[int].
+	if !hasTParam {
+		b.WriteString(".inst.")
+	}
+
+	i := strings.Index(name, "[")
+	assert(hasBrackets == (i >= 0))
+	if i >= 0 {
+		b.WriteString(name[0:i])
+	} else {
+		b.WriteString(name)
+	}
+	b.WriteString("[")
+	for i, targ := range targs {
+		if i > 0 {
+			b.WriteString(",")
+		}
+		// WriteString() does not include the package name for the local
+		// package, but we want it for uniqueness.
+		if targ.Sym() != nil && targ.Sym().Pkg == types.LocalPkg {
+			b.WriteString(targ.Sym().Pkg.Name)
+			b.WriteByte('.')
+		}
+		// types1 uses "interface {" and types2 uses "interface{" - convert
+		// to consistent types2 format.
+		tstring := targ.String()
+		tstring = strings.Replace(tstring, "interface {", "interface{", -1)
+		b.WriteString(tstring)
+	}
+	b.WriteString("]")
+	if i >= 0 {
+		i2 := strings.LastIndex(name[i:], "]")
+		assert(i2 >= 0)
+		b.WriteString(name[i+i2+1:])
+	}
+	if strings.HasPrefix(b.String(), ".inst..inst.") {
+		panic(fmt.Sprintf("multiple .inst. prefix in %s", b.String()))
+	}
+	return b.String()
+}
+
+// MakeInstName makes the unique name for a stenciled generic function or method,
+// based on the name of the function fnsym and the targs. It replaces any
+// existing bracket type list in the name. makeInstName asserts that fnsym has
+// brackets in its name if and only if hasBrackets is true.
+//
+// Names of declared generic functions have no brackets originally, so hasBrackets
+// should be false. Names of generic methods already have brackets, since the new
+// type parameter is specified in the generic type of the receiver (e.g. func
+// (func (v *value[T]).set(...) { ... } has the original name (*value[T]).set.
+//
+// The standard naming is something like: 'genFn[int,bool]' for functions and
+// '(*genType[int,bool]).methodName' for methods
+func MakeInstName(gf *types.Sym, targs []*types.Type, hasBrackets bool) *types.Sym {
+	return gf.Pkg.Lookup(makeGenericName(gf.Name, targs, hasBrackets))
+}
+
+func MakeDictName(gf *types.Sym, targs []*types.Type, hasBrackets bool) *types.Sym {
+	for _, targ := range targs {
+		if targ.HasTParam() {
+			fmt.Printf("FUNCTION %s\n", gf.Name)
+			for _, targ := range targs {
+				fmt.Printf("  PARAM %+v\n", targ)
+			}
+			panic("dictionary should always have concrete type args")
+		}
+	}
+	name := makeGenericName(gf.Name, targs, hasBrackets)
+	name = ".dict." + name[6:]
+	return gf.Pkg.Lookup(name)
+}
+
+func assert(p bool) {
+	base.Assert(p)
+}
+
+// General type substituter, for replacing typeparams with type args.
+type Tsubster struct {
+	Tparams []*types.Type
+	Targs   []*types.Type
+	// If non-nil, the substitution map from name nodes in the generic function to the
+	// name nodes in the new stenciled function.
+	Vars map[*ir.Name]*ir.Name
+	// New fully-instantiated generic types whose methods should be instantiated.
+	InstTypeList []*types.Type
+	// If non-nil, function to substitute an incomplete (TFORW) type.
+	SubstForwFunc func(*types.Type) *types.Type
+}
+
+// Typ computes the type obtained by substituting any type parameter in t with the
+// corresponding type argument in subst. If t contains no type parameters, the
+// result is t; otherwise the result is a new type. It deals with recursive types
+// by using TFORW types and finding partially or fully created types via sym.Def.
+func (ts *Tsubster) Typ(t *types.Type) *types.Type {
+	if !t.HasTParam() && !t.HasShape() && t.Kind() != types.TFUNC {
+		// Note: function types need to be copied regardless, as the
+		// types of closures may contain declarations that need
+		// to be copied. See #45738.
+		return t
+	}
+
+	if t.IsTypeParam() || t.IsShape() {
+		for i, tp := range ts.Tparams {
+			if tp == t {
+				return ts.Targs[i]
+			}
+		}
+		// If t is a simple typeparam T, then t has the name/symbol 'T'
+		// and t.Underlying() == t.
+		//
+		// However, consider the type definition: 'type P[T any] T'. We
+		// might use this definition so we can have a variant of type T
+		// that we can add new methods to. Suppose t is a reference to
+		// P[T]. t has the name 'P[T]', but its kind is TTYPEPARAM,
+		// because P[T] is defined as T. If we look at t.Underlying(), it
+		// is different, because the name of t.Underlying() is 'T' rather
+		// than 'P[T]'. But the kind of t.Underlying() is also TTYPEPARAM.
+		// In this case, we do the needed recursive substitution in the
+		// case statement below.
+		if t.Underlying() == t {
+			// t is a simple typeparam that didn't match anything in tparam
+			return t
+		}
+		// t is a more complex typeparam (e.g. P[T], as above, whose
+		// definition is just T).
+		assert(t.Sym() != nil)
+	}
+
+	var newsym *types.Sym
+	var neededTargs []*types.Type
+	var targsChanged bool
+	var forw *types.Type
+
+	if t.Sym() != nil {
+		// Translate the type params for this type according to
+		// the tparam/targs mapping from subst.
+		neededTargs = make([]*types.Type, len(t.RParams()))
+		for i, rparam := range t.RParams() {
+			neededTargs[i] = ts.Typ(rparam)
+			if !types.Identical(neededTargs[i], rparam) {
+				targsChanged = true
+			}
+		}
+		// For a named (defined) type, we have to change the name of the
+		// type as well. We do this first, so we can look up if we've
+		// already seen this type during this substitution or other
+		// definitions/substitutions.
+		genName := genericTypeName(t.Sym())
+		newsym = t.Sym().Pkg.Lookup(InstTypeName(genName, neededTargs))
+		if newsym.Def != nil {
+			// We've already created this instantiated defined type.
+			return newsym.Def.Type()
+		}
+
+		// In order to deal with recursive generic types, create a TFORW
+		// type initially and set the Def field of its sym, so it can be
+		// found if this type appears recursively within the type.
+		forw = NewIncompleteNamedType(t.Pos(), newsym)
+		//println("Creating new type by sub", newsym.Name, forw.HasTParam())
+		forw.SetRParams(neededTargs)
+		// Copy the OrigSym from the re-instantiated type (which is the sym of
+		// the base generic type).
+		assert(t.OrigSym != nil)
+		forw.OrigSym = t.OrigSym
+	}
+
+	var newt *types.Type
+
+	switch t.Kind() {
+	case types.TTYPEPARAM:
+		if t.Sym() == newsym && !targsChanged {
+			// The substitution did not change the type.
+			return t
+		}
+		// Substitute the underlying typeparam (e.g. T in P[T], see
+		// the example describing type P[T] above).
+		newt = ts.Typ(t.Underlying())
+		assert(newt != t)
+
+	case types.TARRAY:
+		elem := t.Elem()
+		newelem := ts.Typ(elem)
+		if newelem != elem || targsChanged {
+			newt = types.NewArray(newelem, t.NumElem())
+		}
+
+	case types.TPTR:
+		elem := t.Elem()
+		newelem := ts.Typ(elem)
+		if newelem != elem || targsChanged {
+			newt = types.NewPtr(newelem)
+		}
+
+	case types.TSLICE:
+		elem := t.Elem()
+		newelem := ts.Typ(elem)
+		if newelem != elem || targsChanged {
+			newt = types.NewSlice(newelem)
+		}
+
+	case types.TSTRUCT:
+		newt = ts.tstruct(t, targsChanged)
+		if newt == t {
+			newt = nil
+		}
+
+	case types.TFUNC:
+		newrecvs := ts.tstruct(t.Recvs(), false)
+		newparams := ts.tstruct(t.Params(), false)
+		newresults := ts.tstruct(t.Results(), false)
+		// Translate the tparams of a signature.
+		newtparams := ts.tstruct(t.TParams(), false)
+		if newrecvs != t.Recvs() || newparams != t.Params() ||
+			newresults != t.Results() || newtparams != t.TParams() || targsChanged {
+			// If any types have changed, then the all the fields of
+			// of recv, params, and results must be copied, because they have
+			// offset fields that are dependent, and so must have an
+			// independent copy for each new signature.
+			var newrecv *types.Field
+			if newrecvs.NumFields() > 0 {
+				if newrecvs == t.Recvs() {
+					newrecvs = ts.tstruct(t.Recvs(), true)
+				}
+				newrecv = newrecvs.Field(0)
+			}
+			if newparams == t.Params() {
+				newparams = ts.tstruct(t.Params(), true)
+			}
+			if newresults == t.Results() {
+				newresults = ts.tstruct(t.Results(), true)
+			}
+			var tparamfields []*types.Field
+			if newtparams.HasTParam() {
+				tparamfields = newtparams.FieldSlice()
+			} else {
+				// Completely remove the tparams from the resulting
+				// signature, if the tparams are now concrete types.
+				tparamfields = nil
+			}
+			newt = types.NewSignature(t.Pkg(), newrecv, tparamfields,
+				newparams.FieldSlice(), newresults.FieldSlice())
+		}
+
+	case types.TINTER:
+		newt = ts.tinter(t)
+		if newt == t && !targsChanged {
+			newt = nil
+		}
+
+	case types.TMAP:
+		newkey := ts.Typ(t.Key())
+		newval := ts.Typ(t.Elem())
+		if newkey != t.Key() || newval != t.Elem() || targsChanged {
+			newt = types.NewMap(newkey, newval)
+		}
+
+	case types.TCHAN:
+		elem := t.Elem()
+		newelem := ts.Typ(elem)
+		if newelem != elem || targsChanged {
+			newt = types.NewChan(newelem, t.ChanDir())
+			if !newt.HasTParam() {
+				// TODO(danscales): not sure why I have to do this
+				// only for channels.....
+				types.CheckSize(newt)
+			}
+		}
+	case types.TFORW:
+		if ts.SubstForwFunc != nil {
+			newt = ts.SubstForwFunc(t)
+		} else {
+			assert(false)
+		}
+	case types.TINT, types.TINT8, types.TINT16, types.TINT32, types.TINT64,
+		types.TUINT, types.TUINT8, types.TUINT16, types.TUINT32, types.TUINT64,
+		types.TUINTPTR, types.TBOOL, types.TSTRING, types.TFLOAT32, types.TFLOAT64, types.TCOMPLEX64, types.TCOMPLEX128:
+		newt = t.Underlying()
+	case types.TUNION:
+		nt := t.NumTerms()
+		newterms := make([]*types.Type, nt)
+		tildes := make([]bool, nt)
+		changed := false
+		for i := 0; i < nt; i++ {
+			term, tilde := t.Term(i)
+			tildes[i] = tilde
+			newterms[i] = ts.Typ(term)
+			if newterms[i] != term {
+				changed = true
+			}
+		}
+		if changed {
+			newt = types.NewUnion(newterms, tildes)
+		}
+	default:
+		panic(fmt.Sprintf("Bad type in (*TSubster).Typ: %v", t.Kind()))
+	}
+	if newt == nil {
+		// Even though there were typeparams in the type, there may be no
+		// change if this is a function type for a function call (which will
+		// have its own tparams/targs in the function instantiation).
+		return t
+	}
+
+	if t.Sym() == nil && t.Kind() != types.TINTER {
+		// Not a named type or interface type, so there was no forwarding type
+		// and there are no methods to substitute.
+		assert(t.Methods().Len() == 0)
+		return newt
+	}
+
+	if forw != nil {
+		forw.SetUnderlying(newt)
+		newt = forw
+	}
+
+	if t.Kind() != types.TINTER && t.Methods().Len() > 0 {
+		// Fill in the method info for the new type.
+		var newfields []*types.Field
+		newfields = make([]*types.Field, t.Methods().Len())
+		for i, f := range t.Methods().Slice() {
+			t2 := ts.Typ(f.Type)
+			oldsym := f.Nname.Sym()
+			newsym := MakeInstName(oldsym, ts.Targs, true)
+			var nname *ir.Name
+			if newsym.Def != nil {
+				nname = newsym.Def.(*ir.Name)
+			} else {
+				nname = ir.NewNameAt(f.Pos, newsym)
+				nname.SetType(t2)
+				newsym.Def = nname
+			}
+			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
+			newfields[i].Nname = nname
+		}
+		newt.Methods().Set(newfields)
+		if !newt.HasTParam() && !newt.HasShape() {
+			// Generate all the methods for a new fully-instantiated type.
+			ts.InstTypeList = append(ts.InstTypeList, newt)
+		}
+	}
+	return newt
+}
+
+// tstruct substitutes type params in types of the fields of a structure type. For
+// each field, tstruct copies the Nname, and translates it if Nname is in
+// ts.vars. To always force the creation of a new (top-level) struct,
+// regardless of whether anything changed with the types or names of the struct's
+// fields, set force to true.
+func (ts *Tsubster) tstruct(t *types.Type, force bool) *types.Type {
+	if t.NumFields() == 0 {
+		if t.HasTParam() {
+			// For an empty struct, we need to return a new type,
+			// since it may now be fully instantiated (HasTParam
+			// becomes false).
+			return types.NewStruct(t.Pkg(), nil)
+		}
+		return t
+	}
+	var newfields []*types.Field
+	if force {
+		newfields = make([]*types.Field, t.NumFields())
+	}
+	for i, f := range t.Fields().Slice() {
+		t2 := ts.Typ(f.Type)
+		if (t2 != f.Type || f.Nname != nil) && newfields == nil {
+			newfields = make([]*types.Field, t.NumFields())
+			for j := 0; j < i; j++ {
+				newfields[j] = t.Field(j)
+			}
+		}
+		if newfields != nil {
+			// TODO(danscales): make sure this works for the field
+			// names of embedded types (which should keep the name of
+			// the type param, not the instantiated type).
+			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
+			newfields[i].Embedded = f.Embedded
+			if f.IsDDD() {
+				newfields[i].SetIsDDD(true)
+			}
+			if f.Nointerface() {
+				newfields[i].SetNointerface(true)
+			}
+			if f.Nname != nil && ts.Vars != nil {
+				v := ts.Vars[f.Nname.(*ir.Name)]
+				if v != nil {
+					// This is the case where we are
+					// translating the type of the function we
+					// are substituting, so its dcls are in
+					// the subst.ts.vars table, and we want to
+					// change to reference the new dcl.
+					newfields[i].Nname = v
+				} else {
+					// This is the case where we are
+					// translating the type of a function
+					// reference inside the function we are
+					// substituting, so we leave the Nname
+					// value as is.
+					newfields[i].Nname = f.Nname
+				}
+			}
+		}
+	}
+	if newfields != nil {
+		return types.NewStruct(t.Pkg(), newfields)
+	}
+	return t
+
+}
+
+// tinter substitutes type params in types of the methods of an interface type.
+func (ts *Tsubster) tinter(t *types.Type) *types.Type {
+	if t.Methods().Len() == 0 {
+		return t
+	}
+	var newfields []*types.Field
+	for i, f := range t.Methods().Slice() {
+		t2 := ts.Typ(f.Type)
+		if (t2 != f.Type || f.Nname != nil) && newfields == nil {
+			newfields = make([]*types.Field, t.Methods().Len())
+			for j := 0; j < i; j++ {
+				newfields[j] = t.Methods().Index(j)
+			}
+		}
+		if newfields != nil {
+			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
+		}
+	}
+	if newfields != nil {
+		return types.NewInterface(t.Pkg(), newfields)
+	}
+	return t
+}
+
+// genericSym returns the name of the base generic type for the type named by
+// sym. It simply returns the name obtained by removing everything after the
+// first bracket ("[").
+func genericTypeName(sym *types.Sym) string {
+	return sym.Name[0:strings.Index(sym.Name, "[")]
+}
+
+// Shapify takes a concrete type and returns a GCshape type that can
+// be used in place of the input type and still generate identical code.
+// No methods are added - all methods calls directly on a shape should
+// be done by converting to an interface using the dictionary.
+//
+// TODO: this could take the generic function and base its decisions
+// on how that generic function uses this type argument. For instance,
+// if it doesn't use it as a function argument/return value, then
+// we don't need to distinguish int64 and float64 (because they only
+// differ in how they get passed as arguments). For now, we only
+// unify two different types if they are identical in every possible way.
+func Shapify(t *types.Type) *types.Type {
+	assert(!t.HasShape())
+	// Map all types with the same underlying type to the same shape.
+	u := t.Underlying()
+
+	// All pointers have the same shape.
+	// TODO: Make unsafe.Pointer the same shape as normal pointers.
+	if u.Kind() == types.TPTR {
+		u = types.Types[types.TUINT8].PtrTo()
+	}
+
+	if s := shaped[u]; s != nil {
+		return s
+	}
+
+	sym := shapePkg.Lookup(u.LinkString())
+	name := ir.NewDeclNameAt(u.Pos(), ir.OTYPE, sym)
+	s := types.NewNamed(name)
+	s.SetUnderlying(u)
+	s.SetIsShape(true)
+	s.SetHasShape(true)
+	name.SetType(s)
+	name.SetTypecheck(1)
+	shaped[u] = s
+	return s
+}
+
+var shaped = map[*types.Type]*types.Type{}
+
+var shapePkg = types.NewPkg(".shape", ".shape")