[dev.typeparams] cmd/compile: get export/import of generic types & functions working

The general idea is that we now export/import typeparams, typeparam
lists for generic types and functions, and instantiated types
(instantiations of generic types with either new typeparams or concrete
types).

This changes the export format -- the next CL in the stack adds the
export versions and checks for it in the appropriate places.

We always export/import generic function bodies, using the same code
that we use for exporting/importing the bodies of inlineable functions.

To avoid complicated scoping, we consider all type params as unique and
give them unique names for types1. We therefore include the types2 ids
(subscripts) in the export format and re-create on import. We always
access the same unique types1 typeParam type for the same typeparam
name.

We create fully-instantiated generic types and functions in the original
source package. We do an extra NeedRuntimeType() call to make sure that
the correct DWARF information is written out. We call SetDupOK(true) for
the functions/methods to have the linker automatically drop duplicate
instantiations.

Other miscellaneous details:
 - Export/import of typeparam bounds works for methods (but not
   typelists) for now, but will change with the typeset changes.

 - Added a new types.Instantiate function roughly analogous to the
   types2.Instantiate function recently added.

 - Always access methods info from the original/base generic type, since
   the methods of an instantiated type are not filled in (in types2 or
   types1).

 - New field OrigSym in types.Type to keep track of base generic type
   that instantiated type was based on. We use the generic type's symbol
   (OrigSym) as the link, rather than a Type pointer, since we haven't
   always created the base type yet when we want to set the link (during
   types2 to types1 conversion).

 - Added types2.AsTypeParam(), (*types2.TypeParam).SetId()

 - New test minimp.dir, which tests use of generic function Min across
   packages. Another test stringimp.dir, which also exports a generic
   function Stringify across packages, where the type param has a bound
   (Stringer) as well. New test pairimp.dir, which tests use of generic
   type Pair (with no methods) across packages.

 - New test valimp.dir, which tests use of generic type (with methods
   and related functions) across packages.

 - Modified several other tests (adder.go, settable.go, smallest.go,
   stringable.go, struct.go, sum.go) to export their generic
   functions/types to show that generic functions/types can be exported
   successfully (but this doesn't test import).

Change-Id: Ie61ce9d54a46d368ddc7a76c41399378963bb57f
Reviewed-on: https://go-review.googlesource.com/c/go/+/319930
Trust: Dan Scales <danscales@google.com>
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Dan Scales <danscales@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

3 files changed, 255 insertions, 40 deletions

diff --git a/src/cmd/compile/internal/typecheck/iexport.go b/src/cmd/compile/internal/typecheck/iexport.go
index 3538c4d5a6..11b9755148 100644
--- a/src/cmd/compile/internal/typecheck/iexport.go
+++ b/src/cmd/compile/internal/typecheck/iexport.go
@@ -173,6 +173,8 @@
 //     }
 //
 //
+//  TODO(danscales): fill in doc for 'type TypeParamType' and 'type InstType'
+//
 //     type Signature struct {
 //         Params   []Param
 //         Results  []Param
@@ -244,6 +246,8 @@ const (
 	signatureType
 	structType
 	interfaceType
+	typeParamType
+	instType
 )
 
 const (
@@ -459,6 +463,13 @@ func (p *iexporter) doDecl(n *ir.Name) {
 			// Function.
 			w.tag('F')
 			w.pos(n.Pos())
+			// The tparam list of the function type is the
+			// declaration of the type params. So, write out the type
+			// params right now. Then those type params will be
+			// referenced via their type offset (via typOff) in all
+			// other places in the signature and function that they
+			// are used.
+			w.tparamList(n.Type().TParams().FieldSlice())
 			w.signature(n.Type())
 			w.funcExt(n)
 
@@ -491,6 +502,8 @@ func (p *iexporter) doDecl(n *ir.Name) {
 		w.tag('T')
 		w.pos(n.Pos())
 
+		// Export any new typeparams needed for this type
+		w.typeList(n.Type().RParams())
 		underlying := n.Type().Underlying()
 		if underlying == types.ErrorType.Underlying() {
 			// For "type T error", use error as the
@@ -803,8 +816,49 @@ func (w *exportWriter) startType(k itag) {
 }
 
 func (w *exportWriter) doTyp(t *types.Type) {
-	if t.Sym() != nil {
-		if t.Sym().Pkg == types.BuiltinPkg || t.Sym().Pkg == ir.Pkgs.Unsafe {
+	if t.Kind() == types.TTYPEPARAM {
+		// A typeparam has a name, but doesn't have an underlying type.
+		// Just write out the details of the type param here. All other
+		// uses of this typeparam type will be written out as its unique
+		// type offset.
+		w.startType(typeParamType)
+		s := t.Sym()
+		w.setPkg(s.Pkg, true)
+		w.pos(t.Pos())
+
+		// We are writing out the name with the subscript, so that the
+		// typeparam name is unique.
+		w.string(s.Name)
+		w.int64(int64(t.Index()))
+
+		w.typ(t.Bound())
+		return
+	}
+
+	s := t.Sym()
+	if s != nil && t.OrigSym != nil {
+		// This is an instantiated type - could be a re-instantiation like
+		// Value[T2] or a full instantiation like Value[int].
+		if strings.Index(s.Name, "[") < 0 {
+			base.Fatalf("incorrect name for instantiated type")
+		}
+		w.startType(instType)
+		w.pos(t.Pos())
+		// Export the type arguments for the instantiated type. The
+		// instantiated type could be in a method header (e.g. "func (v
+		// *Value[T2]) set (...) { ... }"), so the type args are "new"
+		// typeparams. Or the instantiated type could be in a
+		// function/method body, so the type args are either concrete
+		// types or existing typeparams from the function/method header.
+		w.typeList(t.RParams())
+		// Export a reference to the base type.
+		baseType := t.OrigSym.Def.(*ir.Name).Type()
+		w.typ(baseType)
+		return
+	}
+
+	if s != nil {
+		if s.Pkg == types.BuiltinPkg || s.Pkg == ir.Pkgs.Unsafe {
 			base.Fatalf("builtin type missing from typIndex: %v", t)
 		}
 
@@ -906,6 +960,23 @@ func (w *exportWriter) signature(t *types.Type) {
 	}
 }
 
+func (w *exportWriter) typeList(ts []*types.Type) {
+	w.uint64(uint64(len(ts)))
+	for _, rparam := range ts {
+		w.typ(rparam)
+	}
+}
+
+func (w *exportWriter) tparamList(fs []*types.Field) {
+	w.uint64(uint64(len(fs)))
+	for _, f := range fs {
+		if f.Type.Kind() != types.TTYPEPARAM {
+			base.Fatalf("unexpected non-typeparam")
+		}
+		w.typ(f.Type)
+	}
+}
+
 func (w *exportWriter) paramList(fs []*types.Field) {
 	w.uint64(uint64(len(fs)))
 	for _, f := range fs {
@@ -1186,9 +1257,21 @@ func (w *exportWriter) funcExt(n *ir.Name) {
 	}
 
 	// Inline body.
+	if n.Type().HasTParam() {
+		if n.Func.Inl != nil {
+			base.FatalfAt(n.Pos(), "generic function is marked inlineable")
+		}
+		// Populate n.Func.Inl, so body of exported generic function will
+		// be written out.
+		n.Func.Inl = &ir.Inline{
+			Cost: 1,
+			Dcl:  n.Func.Dcl,
+			Body: n.Func.Body,
+		}
+	}
 	if n.Func.Inl != nil {
 		w.uint64(1 + uint64(n.Func.Inl.Cost))
-		if n.Func.ExportInline() {
+		if n.Func.ExportInline() || n.Type().HasTParam() {
 			w.p.doInline(n)
 		}
 
@@ -1588,9 +1671,8 @@ func (w *exportWriter) expr(n ir.Node) {
 	case ir.OXDOT, ir.ODOT, ir.ODOTPTR, ir.ODOTINTER, ir.ODOTMETH, ir.OCALLPART, ir.OMETHEXPR:
 		n := n.(*ir.SelectorExpr)
 		if go117ExportTypes {
-			if n.Op() == ir.OXDOT {
-				base.Fatalf("shouldn't encounter XDOT  in new exporter")
-			}
+			// For go117ExportTypes, we usually see all ops except
+			// OXDOT, but we can see OXDOT for generic functions.
 			w.op(n.Op())
 		} else {
 			w.op(ir.OXDOT)
@@ -1604,7 +1686,8 @@ func (w *exportWriter) expr(n ir.Node) {
 				w.exoticField(n.Selection)
 			}
 			// n.Selection is not required for OMETHEXPR, ODOTMETH, and OCALLPART. It will
-			// be reconstructed during import.
+			// be reconstructed during import.  n.Selection is computed during
+			// transformDot() for OXDOT.
 		}
 
 	case ir.ODOTTYPE, ir.ODOTTYPE2:
diff --git a/src/cmd/compile/internal/typecheck/iimport.go b/src/cmd/compile/internal/typecheck/iimport.go
index a5ddbb5a74..b6f227bb00 100644
--- a/src/cmd/compile/internal/typecheck/iimport.go
+++ b/src/cmd/compile/internal/typecheck/iimport.go
@@ -8,6 +8,7 @@
 package typecheck
 
 import (
+	"bytes"
 	"encoding/binary"
 	"fmt"
 	"go/constant"
@@ -313,13 +314,16 @@ func (r *importReader) doDecl(sym *types.Sym) *ir.Name {
 		return n
 
 	case 'F':
-		typ := r.signature(nil)
+		tparams := r.tparamList()
+		typ := r.signature(nil, tparams)
 
 		n := importfunc(r.p.ipkg, pos, sym, typ)
 		r.funcExt(n)
 		return n
 
 	case 'T':
+		rparams := r.typeList()
+
 		// Types can be recursive. We need to setup a stub
 		// declaration before recursing.
 		n := importtype(r.p.ipkg, pos, sym)
@@ -332,6 +336,10 @@ func (r *importReader) doDecl(sym *types.Sym) *ir.Name {
 		t.SetUnderlying(underlying)
 		types.ResumeCheckSize()
 
+		if rparams != nil {
+			t.SetRParams(rparams)
+		}
+
 		if underlying.IsInterface() {
 			r.typeExt(t)
 			return n
@@ -342,7 +350,7 @@ func (r *importReader) doDecl(sym *types.Sym) *ir.Name {
 			mpos := r.pos()
 			msym := r.selector()
 			recv := r.param()
-			mtyp := r.signature(recv)
+			mtyp := r.signature(recv, nil)
 
 			// MethodSym already marked m.Sym as a function.
 			m := ir.NewNameAt(mpos, ir.MethodSym(recv.Type, msym))
@@ -680,7 +688,7 @@ func (r *importReader) typ1() *types.Type {
 
 	case signatureType:
 		r.setPkg()
-		return r.signature(nil)
+		return r.signature(nil, nil)
 
 	case structType:
 		r.setPkg()
@@ -718,7 +726,7 @@ func (r *importReader) typ1() *types.Type {
 		for i := range methods {
 			pos := r.pos()
 			sym := r.selector()
-			typ := r.signature(fakeRecvField())
+			typ := r.signature(fakeRecvField(), nil)
 
 			methods[i] = types.NewField(pos, sym, typ)
 		}
@@ -728,6 +736,40 @@ func (r *importReader) typ1() *types.Type {
 		// Ensure we expand the interface in the frontend (#25055).
 		types.CheckSize(t)
 		return t
+
+	case typeParamType:
+		r.setPkg()
+		pos := r.pos()
+		name := r.string()
+		sym := r.currPkg.Lookup(name)
+		index := int(r.int64())
+		bound := r.typ()
+		if sym.Def != nil {
+			// Make sure we use the same type param type for the same
+			// name, whether it is created during types1-import or
+			// this types2-to-types1 translation.
+			return sym.Def.Type()
+		}
+		t := types.NewTypeParam(sym, index)
+		// Nname needed to save the pos.
+		nname := ir.NewDeclNameAt(pos, ir.OTYPE, sym)
+		sym.Def = nname
+		nname.SetType(t)
+		t.SetNod(nname)
+
+		t.SetBound(bound)
+		return t
+
+	case instType:
+		pos := r.pos()
+		len := r.uint64()
+		targs := make([]*types.Type, len)
+		for i := range targs {
+			targs[i] = r.typ()
+		}
+		baseType := r.typ()
+		t := Instantiate(pos, baseType, targs)
+		return t
 	}
 }
 
@@ -735,13 +777,38 @@ func (r *importReader) kind() itag {
 	return itag(r.uint64())
 }
 
-func (r *importReader) signature(recv *types.Field) *types.Type {
+func (r *importReader) signature(recv *types.Field, tparams []*types.Field) *types.Type {
 	params := r.paramList()
 	results := r.paramList()
 	if n := len(params); n > 0 {
 		params[n-1].SetIsDDD(r.bool())
 	}
-	return types.NewSignature(r.currPkg, recv, nil, params, results)
+	return types.NewSignature(r.currPkg, recv, tparams, params, results)
+}
+
+func (r *importReader) typeList() []*types.Type {
+	n := r.uint64()
+	if n == 0 {
+		return nil
+	}
+	ts := make([]*types.Type, n)
+	for i := range ts {
+		ts[i] = r.typ()
+	}
+	return ts
+}
+
+func (r *importReader) tparamList() []*types.Field {
+	n := r.uint64()
+	if n == 0 {
+		return nil
+	}
+	fs := make([]*types.Field, n)
+	for i := range fs {
+		typ := r.typ()
+		fs[i] = types.NewField(typ.Pos(), typ.Sym(), typ)
+	}
+	return fs
 }
 
 func (r *importReader) paramList() []*types.Field {
@@ -809,7 +876,9 @@ func (r *importReader) funcExt(n *ir.Name) {
 
 	n.Func.ABI = obj.ABI(r.uint64())
 
-	n.SetPragma(ir.PragmaFlag(r.uint64()))
+	// Make sure //go:noinline pragma is imported (so stenciled functions have
+	// same noinline status as the corresponding generic function.)
+	n.Func.Pragma = ir.PragmaFlag(r.uint64())
 
 	// Escape analysis.
 	for _, fs := range &types.RecvsParams {
@@ -1117,7 +1186,7 @@ func (r *importReader) node() ir.Node {
 	case ir.OCLOSURE:
 		//println("Importing CLOSURE")
 		pos := r.pos()
-		typ := r.signature(nil)
+		typ := r.signature(nil, nil)
 
 		// All the remaining code below is similar to (*noder).funcLit(), but
 		// with Dcls and ClosureVars lists already set up
@@ -1202,35 +1271,32 @@ func (r *importReader) node() ir.Node {
 	// case OSTRUCTKEY:
 	//	unreachable - handled in case OSTRUCTLIT by elemList
 
-	case ir.OXDOT:
-		// see parser.new_dotname
-		if go117ExportTypes {
-			base.Fatalf("shouldn't encounter XDOT in new importer")
-		}
-		return ir.NewSelectorExpr(r.pos(), ir.OXDOT, r.expr(), r.exoticSelector())
-
-	case ir.ODOT, ir.ODOTPTR, ir.ODOTINTER, ir.ODOTMETH, ir.OCALLPART, ir.OMETHEXPR:
-		if !go117ExportTypes {
-			// unreachable - mapped to case OXDOT by exporter
+	case ir.OXDOT, ir.ODOT, ir.ODOTPTR, ir.ODOTINTER, ir.ODOTMETH, ir.OCALLPART, ir.OMETHEXPR:
+		// For !go117ExportTypes,  we should only see OXDOT.
+		// For go117ExportTypes, we usually see all the other ops, but can see
+		// OXDOT for generic functions.
+		if op != ir.OXDOT && !go117ExportTypes {
 			goto error
 		}
 		pos := r.pos()
 		expr := r.expr()
 		sel := r.exoticSelector()
 		n := ir.NewSelectorExpr(pos, op, expr, sel)
-		n.SetType(r.exoticType())
-		switch op {
-		case ir.ODOT, ir.ODOTPTR, ir.ODOTINTER:
-			n.Selection = r.exoticField()
-		case ir.ODOTMETH, ir.OCALLPART, ir.OMETHEXPR:
-			// These require a Lookup to link to the correct declaration.
-			rcvrType := expr.Type()
-			typ := n.Type()
-			n.Selection = Lookdot(n, rcvrType, 1)
-			if op == ir.OCALLPART || op == ir.OMETHEXPR {
-				// Lookdot clobbers the opcode and type, undo that.
-				n.SetOp(op)
-				n.SetType(typ)
+		if go117ExportTypes {
+			n.SetType(r.exoticType())
+			switch op {
+			case ir.ODOT, ir.ODOTPTR, ir.ODOTINTER:
+				n.Selection = r.exoticField()
+			case ir.ODOTMETH, ir.OCALLPART, ir.OMETHEXPR:
+				// These require a Lookup to link to the correct declaration.
+				rcvrType := expr.Type()
+				typ := n.Type()
+				n.Selection = Lookdot(n, rcvrType, 1)
+				if op == ir.OCALLPART || op == ir.OMETHEXPR {
+					// Lookdot clobbers the opcode and type, undo that.
+					n.SetOp(op)
+					n.SetType(typ)
+				}
 			}
 		}
 		return n
@@ -1544,3 +1610,63 @@ func builtinCall(pos src.XPos, op ir.Op) *ir.CallExpr {
 	}
 	return ir.NewCallExpr(pos, ir.OCALL, ir.NewIdent(base.Pos, types.BuiltinPkg.Lookup(ir.OpNames[op])), nil)
 }
+
+// InstTypeName creates a name for an instantiated type, based on the name of the
+// generic type and the type args.
+func InstTypeName(name string, targs []*types.Type) string {
+	b := bytes.NewBufferString(name)
+	b.WriteByte('[')
+	for i, targ := range targs {
+		if i > 0 {
+			b.WriteByte(',')
+		}
+		// WriteString() does not include the package name for the local
+		// package, but we want it to make sure type arguments (including
+		// type params) are uniquely specified.
+		if targ.Sym() != nil && targ.Sym().Pkg == types.LocalPkg {
+			b.WriteString(targ.Sym().Pkg.Name)
+			b.WriteByte('.')
+		}
+		b.WriteString(targ.String())
+	}
+	b.WriteByte(']')
+	return b.String()
+}
+
+// NewIncompleteNamedType returns a TFORW type t with name specified by sym, such
+// that t.nod and sym.Def are set correctly.
+func NewIncompleteNamedType(pos src.XPos, sym *types.Sym) *types.Type {
+	name := ir.NewDeclNameAt(pos, ir.OTYPE, sym)
+	forw := types.NewNamed(name)
+	name.SetType(forw)
+	sym.Def = name
+	return forw
+}
+
+// Instantiate creates a new named type which is the instantiation of the base
+// named generic type, with the specified type args.
+func Instantiate(pos src.XPos, baseType *types.Type, targs []*types.Type) *types.Type {
+	baseSym := baseType.Sym()
+	if strings.Index(baseSym.Name, "[") >= 0 {
+		base.Fatalf("arg to Instantiate is not a base generic type")
+	}
+	name := InstTypeName(baseSym.Name, targs)
+	instSym := baseSym.Pkg.Lookup(name)
+	if instSym.Def != nil {
+		return instSym.Def.Type()
+	}
+
+	t := NewIncompleteNamedType(baseType.Pos(), instSym)
+	t.SetRParams(targs)
+	// baseType may not yet be complete (since we are in the middle of
+	// importing it), but its underlying type will be updated when baseType's
+	// underlying type is finished.
+	t.SetUnderlying(baseType.Underlying())
+
+	// As with types2, the methods are the generic method signatures (without
+	// substitution).
+	t.Methods().Set(baseType.Methods().Slice())
+	t.OrigSym = baseSym
+
+	return t
+}
diff --git a/src/cmd/compile/internal/typecheck/subr.go b/src/cmd/compile/internal/typecheck/subr.go
index 97fb145132..9eac802dab 100644
--- a/src/cmd/compile/internal/typecheck/subr.go
+++ b/src/cmd/compile/internal/typecheck/subr.go
@@ -887,7 +887,7 @@ func TypesOf(x []ir.Node) []*types.Type {
 }
 
 // MakeInstName makes the unique name for a stenciled generic function or method,
-// based on the name of the function fy=nsym and the targs. It replaces any
+// 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.
 // TODO(danscales): remove the assertions and the hasBrackets argument later.
@@ -914,6 +914,12 @@ func MakeInstName(fnsym *types.Sym, targs []*types.Type, hasBrackets bool) *type
 		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('.')
+		}
 		b.WriteString(targ.String())
 	}
 	b.WriteString("]")
@@ -922,7 +928,7 @@ func MakeInstName(fnsym *types.Sym, targs []*types.Type, hasBrackets bool) *type
 		assert(i2 >= 0)
 		b.WriteString(name[i+i2+1:])
 	}
-	return Lookup(b.String())
+	return fnsym.Pkg.Lookup(b.String())
 }
 
 // For catching problems as we add more features