[dev.typeparams] cmd/compile: support generic types (with stenciling of method calls)

A type may now have a type param in it, either because it has been
composed from a function type param, or it has been declared as or
derived from a reference to a generic type. No objects or types with
type params can be exported yet. No generic type has a runtime
descriptor (but will likely eventually be associated with a dictionary).

types.Type now has an RParam field, which for a Named type can specify
the type params (in order) that must be supplied to fully instantiate
the type. Also, there is a new flag HasTParam to indicate if there is
a type param (TTYPEPARAM) anywhere in the type.

An instantiated generic type (whether fully instantiated or
re-instantiated to new type params) is a defined type, even though there
was no explicit declaration. This allows us to handle recursive
instantiated types (and improves printing of types).

To avoid the need to transform later in the compiler, an instantiation
of a method of a generic type is immediately represented as a function
with the method as the first argument.

Added 5 tests on generic types to test/typeparams, including list.go,
which tests recursive generic types.

Change-Id: Ib7ff27abd369a06d1c8ea84edc6ca1fd74bbb7c2
Reviewed-on: https://go-review.googlesource.com/c/go/+/292652
Trust: Dan Scales <danscales@google.com>
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Dan Scales <danscales@google.com>
Reviewed-by: Robert Griesemer <gri@golang.org>

1 files changed, 52 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/types/type.go b/src/cmd/compile/internal/types/type.go
index 987aa11454..b6374e49a5 100644
--- a/src/cmd/compile/internal/types/type.go
+++ b/src/cmd/compile/internal/types/type.go
@@ -176,6 +176,11 @@ type Type struct {
 	Align uint8 // the required alignment of this type, in bytes (0 means Width and Align have not yet been computed)
 
 	flags bitset8
+
+	// Type params (in order) of this named type that need to be instantiated.
+	// TODO(danscales): for space reasons, should probably be a pointer to a
+	// slice, possibly change the name of this field.
+	RParams []*Type
 }
 
 func (*Type) CanBeAnSSAAux() {}
@@ -186,6 +191,7 @@ const (
 	typeNoalg                  // suppress hash and eq algorithm generation
 	typeDeferwidth             // width computation has been deferred and type is on deferredTypeStack
 	typeRecur
+	typeHasTParam // there is a typeparam somewhere in the type (generic function or type)
 )
 
 func (t *Type) NotInHeap() bool  { return t.flags&typeNotInHeap != 0 }
@@ -193,12 +199,14 @@ func (t *Type) Broke() bool      { return t.flags&typeBroke != 0 }
 func (t *Type) Noalg() bool      { return t.flags&typeNoalg != 0 }
 func (t *Type) Deferwidth() bool { return t.flags&typeDeferwidth != 0 }
 func (t *Type) Recur() bool      { return t.flags&typeRecur != 0 }
+func (t *Type) HasTParam() bool  { return t.flags&typeHasTParam != 0 }
 
 func (t *Type) SetNotInHeap(b bool)  { t.flags.set(typeNotInHeap, b) }
 func (t *Type) SetBroke(b bool)      { t.flags.set(typeBroke, b) }
 func (t *Type) SetNoalg(b bool)      { t.flags.set(typeNoalg, b) }
 func (t *Type) SetDeferwidth(b bool) { t.flags.set(typeDeferwidth, b) }
 func (t *Type) SetRecur(b bool)      { t.flags.set(typeRecur, b) }
+func (t *Type) SetHasTParam(b bool)  { t.flags.set(typeHasTParam, b) }
 
 // Kind returns the kind of type t.
 func (t *Type) Kind() Kind { return t.kind }
@@ -527,6 +535,9 @@ func NewArray(elem *Type, bound int64) *Type {
 	t := New(TARRAY)
 	t.Extra = &Array{Elem: elem, Bound: bound}
 	t.SetNotInHeap(elem.NotInHeap())
+	if elem.HasTParam() {
+		t.SetHasTParam(true)
+	}
 	return t
 }
 
@@ -542,6 +553,9 @@ func NewSlice(elem *Type) *Type {
 	t := New(TSLICE)
 	t.Extra = Slice{Elem: elem}
 	elem.cache.slice = t
+	if elem.HasTParam() {
+		t.SetHasTParam(true)
+	}
 	return t
 }
 
@@ -551,6 +565,9 @@ func NewChan(elem *Type, dir ChanDir) *Type {
 	ct := t.ChanType()
 	ct.Elem = elem
 	ct.Dir = dir
+	if elem.HasTParam() {
+		t.SetHasTParam(true)
+	}
 	return t
 }
 
@@ -558,6 +575,9 @@ func NewTuple(t1, t2 *Type) *Type {
 	t := New(TTUPLE)
 	t.Extra.(*Tuple).first = t1
 	t.Extra.(*Tuple).second = t2
+	if t1.HasTParam() || t2.HasTParam() {
+		t.SetHasTParam(true)
+	}
 	return t
 }
 
@@ -579,6 +599,9 @@ func NewMap(k, v *Type) *Type {
 	mt := t.MapType()
 	mt.Key = k
 	mt.Elem = v
+	if k.HasTParam() || v.HasTParam() {
+		t.SetHasTParam(true)
+	}
 	return t
 }
 
@@ -597,6 +620,12 @@ func NewPtr(elem *Type) *Type {
 		if t.Elem() != elem {
 			base.Fatalf("NewPtr: elem mismatch")
 		}
+		if elem.HasTParam() {
+			// Extra check when reusing the cache, since the elem
+			// might have still been undetermined (i.e. a TFORW type)
+			// when this entry was cached.
+			t.SetHasTParam(true)
+		}
 		return t
 	}
 
@@ -607,6 +636,9 @@ func NewPtr(elem *Type) *Type {
 	if NewPtrCacheEnabled {
 		elem.cache.ptr = t
 	}
+	if elem.HasTParam() {
+		t.SetHasTParam(true)
+	}
 	return t
 }
 
@@ -1611,6 +1643,9 @@ func (t *Type) SetUnderlying(underlying *Type) {
 	if underlying.Broke() {
 		t.SetBroke(true)
 	}
+	if underlying.HasTParam() {
+		t.SetHasTParam(true)
+	}
 
 	// spec: "The declared type does not inherit any methods bound
 	// to the existing type, but the method set of an interface
@@ -1633,6 +1668,15 @@ func (t *Type) SetUnderlying(underlying *Type) {
 	}
 }
 
+func fieldsHasTParam(fields []*Field) bool {
+	for _, f := range fields {
+		if f.Type != nil && f.Type.HasTParam() {
+			return true
+		}
+	}
+	return false
+}
+
 // NewBasic returns a new basic type of the given kind.
 func NewBasic(kind Kind, obj Object) *Type {
 	t := New(kind)
@@ -1660,6 +1704,7 @@ func NewTypeParam(pkg *Pkg, constraint *Type) *Type {
 	constraint.wantEtype(TINTER)
 	t.methods = constraint.methods
 	t.Extra.(*Interface).pkg = pkg
+	t.SetHasTParam(true)
 	return t
 }
 
@@ -1688,6 +1733,10 @@ func NewSignature(pkg *Pkg, recv *Field, tparams, params, results []*Field) *Typ
 	ft.Params = funargs(params, FunargParams)
 	ft.Results = funargs(results, FunargResults)
 	ft.pkg = pkg
+	if len(tparams) > 0 || fieldsHasTParam(recvs) || fieldsHasTParam(params) ||
+		fieldsHasTParam(results) {
+		t.SetHasTParam(true)
+	}
 
 	return t
 }
@@ -1700,6 +1749,9 @@ func NewStruct(pkg *Pkg, fields []*Field) *Type {
 		t.SetBroke(true)
 	}
 	t.Extra.(*Struct).pkg = pkg
+	if fieldsHasTParam(fields) {
+		t.SetHasTParam(true)
+	}
 	return t
 }