[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>

6 files changed, 88 insertions, 54 deletions

diff --git a/src/cmd/compile/internal/noder/decl.go b/src/cmd/compile/internal/noder/decl.go
index 3e55437afa..40cbe50aff 100644
--- a/src/cmd/compile/internal/noder/decl.go
+++ b/src/cmd/compile/internal/noder/decl.go
@@ -148,11 +148,15 @@ func (g *irgen) typeDecl(out *ir.Nodes, decl *syntax.TypeDecl) {
 	// [mdempsky: Subtleties like these are why I always vehemently
 	// object to new type pragmas.]
 	ntyp.SetUnderlying(g.typeExpr(decl.Type))
-	if len(decl.TParamList) > 0 {
-		// Set HasTParam if there are any tparams, even if no tparams are
-		// used in the type itself (e.g., if it is an empty struct, or no
-		// fields in the struct use the tparam).
-		ntyp.SetHasTParam(true)
+
+	tparams := otyp.(*types2.Named).TParams()
+	if len(tparams) > 0 {
+		rparams := make([]*types.Type, len(tparams))
+		for i := range rparams {
+			rparams[i] = g.typ(tparams[i].Type())
+		}
+		// This will set hasTParam flag if any rparams are not concrete types.
+		ntyp.SetRParams(rparams)
 	}
 	types.ResumeCheckSize()
 
diff --git a/src/cmd/compile/internal/noder/expr.go b/src/cmd/compile/internal/noder/expr.go
index b7f7a34953..f96144f8d7 100644
--- a/src/cmd/compile/internal/noder/expr.go
+++ b/src/cmd/compile/internal/noder/expr.go
@@ -264,8 +264,12 @@ func (g *irgen) selectorExpr(pos src.XPos, typ types2.Type, expr *syntax.Selecto
 				// instantiated for this method call.
 				// selinfo.Recv() is the instantiated type
 				recvType2 = recvType2Base
-				// method is the generic method associated with the gen type
-				method := g.obj(types2.AsNamed(recvType2).Method(last))
+				recvTypeSym := g.pkg(method2.Pkg()).Lookup(recvType2.(*types2.Named).Obj().Name())
+				recvType := recvTypeSym.Def.(*ir.Name).Type()
+				// method is the generic method associated with
+				// the base generic type. The instantiated type may not
+				// have method bodies filled in, if it was imported.
+				method := recvType.Methods().Index(last).Nname.(*ir.Name)
 				n = ir.NewSelectorExpr(pos, ir.OCALLPART, x, typecheck.Lookup(expr.Sel.Value))
 				n.(*ir.SelectorExpr).Selection = types.NewField(pos, method.Sym(), method.Type())
 				n.(*ir.SelectorExpr).Selection.Nname = method
diff --git a/src/cmd/compile/internal/noder/irgen.go b/src/cmd/compile/internal/noder/irgen.go
index 2a9f0e99d8..f02246111f 100644
--- a/src/cmd/compile/internal/noder/irgen.go
+++ b/src/cmd/compile/internal/noder/irgen.go
@@ -185,9 +185,9 @@ Outer:
 	// Create any needed stencils of generic functions
 	g.stencil()
 
-	// For now, remove all generic functions from g.target.Decl, since they
-	// have been used for stenciling, but don't compile. TODO: We will
-	// eventually export any exportable generic functions.
+	// Remove all generic functions from g.target.Decl, since they have been
+	// used for stenciling, but don't compile. Generic functions will already
+	// have been marked for export as appropriate.
 	j := 0
 	for i, decl := range g.target.Decls {
 		if decl.Op() != ir.ODCLFUNC || !decl.Type().HasTParam() {
diff --git a/src/cmd/compile/internal/noder/object.go b/src/cmd/compile/internal/noder/object.go
index 7af2fe6715..a1a10e4eaa 100644
--- a/src/cmd/compile/internal/noder/object.go
+++ b/src/cmd/compile/internal/noder/object.go
@@ -49,6 +49,11 @@ func (g *irgen) obj(obj types2.Object) *ir.Name {
 	// For imported objects, we use iimport directly instead of mapping
 	// the types2 representation.
 	if obj.Pkg() != g.self {
+		if sig, ok := obj.Type().(*types2.Signature); ok && sig.Recv() != nil {
+			// We can't import a method by name - must import the type
+			// and access the method from it.
+			base.FatalfAt(g.pos(obj), "tried to import a method directly")
+		}
 		sym := g.sym(obj)
 		if sym.Def != nil {
 			return sym.Def.(*ir.Name)
@@ -165,9 +170,8 @@ func (g *irgen) objFinish(name *ir.Name, class ir.Class, typ *types.Type) {
 			break // methods are exported with their receiver type
 		}
 		if types.IsExported(sym.Name) {
-			if name.Class == ir.PFUNC && name.Type().NumTParams() > 0 {
-				base.FatalfAt(name.Pos(), "Cannot export a generic function (yet): %v", name)
-			}
+			// Generic functions can be marked for export here, even
+			// though they will not be compiled until instantiated.
 			typecheck.Export(name)
 		}
 		if base.Flag.AsmHdr != "" && !name.Sym().Asm() {
diff --git a/src/cmd/compile/internal/noder/stencil.go b/src/cmd/compile/internal/noder/stencil.go
index f9cf6d8a1a..7a7c05280d 100644
--- a/src/cmd/compile/internal/noder/stencil.go
+++ b/src/cmd/compile/internal/noder/stencil.go
@@ -8,12 +8,10 @@
 package noder
 
 import (
-	"bytes"
 	"cmd/compile/internal/base"
 	"cmd/compile/internal/ir"
 	"cmd/compile/internal/typecheck"
 	"cmd/compile/internal/types"
-	"cmd/internal/src"
 	"fmt"
 	"strings"
 )
@@ -160,9 +158,14 @@ func (g *irgen) stencil() {
 func (g *irgen) instantiateMethods() {
 	for i := 0; i < len(g.instTypeList); i++ {
 		typ := g.instTypeList[i]
-		// Get the base generic type by looking up the symbol of the
-		// generic (uninstantiated) name.
-		baseSym := typ.Sym().Pkg.Lookup(genericTypeName(typ.Sym()))
+		// Mark runtime type as needed, since this ensures that the
+		// compiler puts out the needed DWARF symbols, when this
+		// instantiated type has a different package from the local
+		// package.
+		typecheck.NeedRuntimeType(typ)
+		// Lookup the method on the base generic type, since methods may
+		// not be set on imported instantiated types.
+		baseSym := typ.OrigSym
 		baseType := baseSym.Def.(*ir.Name).Type()
 		for j, m := range typ.Methods().Slice() {
 			name := m.Nname.(*ir.Name)
@@ -199,12 +202,24 @@ func (g *irgen) getInstantiationForNode(inst *ir.InstExpr) *ir.Func {
 // with the type arguments targs. If the instantiated function is not already
 // cached, then it calls genericSubst to create the new instantiation.
 func (g *irgen) getInstantiation(nameNode *ir.Name, targs []*types.Type, isMeth bool) *ir.Func {
+	if nameNode.Func.Body == nil && nameNode.Func.Inl != nil {
+		// If there is no body yet but Func.Inl exists, then we can can
+		// import the whole generic body.
+		assert(nameNode.Func.Inl.Cost == 1 && nameNode.Sym().Pkg != types.LocalPkg)
+		typecheck.ImportBody(nameNode.Func)
+		assert(nameNode.Func.Inl.Body != nil)
+		nameNode.Func.Body = nameNode.Func.Inl.Body
+		nameNode.Func.Dcl = nameNode.Func.Inl.Dcl
+	}
 	sym := typecheck.MakeInstName(nameNode.Sym(), targs, isMeth)
 	st := g.target.Stencils[sym]
 	if st == nil {
 		// If instantiation doesn't exist yet, create it and add
 		// to the list of decls.
 		st = g.genericSubst(sym, nameNode, targs, isMeth)
+		// This ensures that the linker drops duplicates of this instantiation.
+		// All just works!
+		st.SetDupok(true)
 		g.target.Stencils[sym] = st
 		g.target.Decls = append(g.target.Decls, st)
 		if base.Flag.W > 1 {
@@ -626,21 +641,6 @@ func (subst *subster) tinter(t *types.Type) *types.Type {
 	return t
 }
 
-// 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(',')
-		}
-		b.WriteString(targ.String())
-	}
-	b.WriteByte(']')
-	return b.String()
-}
-
 // 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
@@ -696,7 +696,7 @@ func (subst *subster) typ(t *types.Type) *types.Type {
 		// already seen this type during this substitution or other
 		// definitions/substitutions.
 		genName := genericTypeName(t.Sym())
-		newsym = t.Sym().Pkg.Lookup(instTypeName(genName, neededTargs))
+		newsym = t.Sym().Pkg.Lookup(typecheck.InstTypeName(genName, neededTargs))
 		if newsym.Def != nil {
 			// We've already created this instantiated defined type.
 			return newsym.Def.Type()
@@ -705,9 +705,13 @@ func (subst *subster) typ(t *types.Type) *types.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)
+		forw = typecheck.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
@@ -865,11 +869,14 @@ func (subst *subster) fields(class ir.Class, oldfields []*types.Field, dcl []*ir
 	for j := range oldfields {
 		newfields[j] = oldfields[j].Copy()
 		newfields[j].Type = subst.typ(oldfields[j].Type)
-		// A param field will be missing from dcl if its name is
+		// A PPARAM field will be missing from dcl if its name is
 		// unspecified or specified as "_". So, we compare the dcl sym
-		// with the field sym. If they don't match, this dcl (if there is
-		// one left) must apply to a later field.
-		if i < len(dcl) && dcl[i].Sym() == oldfields[j].Sym {
+		// with the field sym (or sym of the field's Nname node). (Unnamed
+		// results still have a name like ~r2 in their Nname node.) If
+		// they don't match, this dcl (if there is one left) must apply to
+		// a later field.
+		if i < len(dcl) && (dcl[i].Sym() == oldfields[j].Sym ||
+			(oldfields[j].Nname != nil && dcl[i].Sym() == oldfields[j].Nname.Sym())) {
 			newfields[j].Nname = dcl[i]
 			i++
 		}
@@ -884,13 +891,3 @@ func deref(t *types.Type) *types.Type {
 	}
 	return t
 }
-
-// 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
-}
diff --git a/src/cmd/compile/internal/noder/types.go b/src/cmd/compile/internal/noder/types.go
index 35ba1cd238..7fdad29e16 100644
--- a/src/cmd/compile/internal/noder/types.go
+++ b/src/cmd/compile/internal/noder/types.go
@@ -68,8 +68,10 @@ func instTypeName2(name string, targs []types2.Type) string {
 		if i > 0 {
 			b.WriteByte(',')
 		}
+		// Include package names for all types, including typeparams, to
+		// make sure type arguments are uniquely specified.
 		tname := types2.TypeString(targ,
-			func(*types2.Package) string { return "" })
+			func(pkg *types2.Package) string { return pkg.Name() })
 		if strings.Index(tname, ", ") >= 0 {
 			// types2.TypeString puts spaces after a comma in a type
 			// list, but we don't want spaces in our actual type names
@@ -120,7 +122,7 @@ func (g *irgen) typ0(typ types2.Type) *types.Type {
 			// which may set HasTParam) before translating the
 			// underlying type itself, so we handle recursion
 			// correctly, including via method signatures.
-			ntyp := newIncompleteNamedType(g.pos(typ.Obj().Pos()), s)
+			ntyp := typecheck.NewIncompleteNamedType(g.pos(typ.Obj().Pos()), s)
 			g.typs[typ] = ntyp
 
 			// If ntyp still has type params, then we must be
@@ -143,6 +145,8 @@ func (g *irgen) typ0(typ types2.Type) *types.Type {
 
 			ntyp.SetUnderlying(g.typ1(typ.Underlying()))
 			g.fillinMethods(typ, ntyp)
+			// Save the symbol for the base generic type.
+			ntyp.OrigSym = g.pkg(typ.Obj().Pkg()).Lookup(typ.Obj().Name())
 			return ntyp
 		}
 		obj := g.obj(typ.Obj())
@@ -206,8 +210,19 @@ func (g *irgen) typ0(typ types2.Type) *types.Type {
 	case *types2.TypeParam:
 		// Save the name of the type parameter in the sym of the type.
 		// Include the types2 subscript in the sym name
-		sym := g.pkg(typ.Obj().Pkg()).Lookup(types2.TypeString(typ, func(*types2.Package) string { return "" }))
+		pkg := g.tpkg(typ)
+		sym := pkg.Lookup(types2.TypeString(typ, func(*types2.Package) string { return "" }))
+		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()
+		}
 		tp := types.NewTypeParam(sym, typ.Index())
+		nname := ir.NewDeclNameAt(g.pos(typ.Obj().Pos()), ir.OTYPE, sym)
+		sym.Def = nname
+		nname.SetType(tp)
+		tp.SetNod(nname)
 		// Set g.typs[typ] in case the bound methods reference typ.
 		g.typs[typ] = tp
 
@@ -248,12 +263,20 @@ func (g *irgen) fillinMethods(typ *types2.Named, ntyp *types.Type) {
 		methods := make([]*types.Field, typ.NumMethods())
 		for i := range methods {
 			m := typ.Method(i)
-			meth := g.obj(m)
 			recvType := types2.AsSignature(m.Type()).Recv().Type()
 			ptr := types2.AsPointer(recvType)
 			if ptr != nil {
 				recvType = ptr.Elem()
 			}
+			var meth *ir.Name
+			if m.Pkg() != g.self {
+				// Imported methods cannot be loaded by name (what
+				// g.obj() does) - they must be loaded via their
+				// type.
+				meth = g.obj(recvType.(*types2.Named).Obj()).Type().Methods().Index(i).Nname.(*ir.Name)
+			} else {
+				meth = g.obj(m)
+			}
 			if recvType != types2.Type(typ) {
 				// Unfortunately, meth is the type of the method of the
 				// generic type, so we have to do a substitution to get
@@ -343,7 +366,7 @@ func (g *irgen) selector(obj types2.Object) *types.Sym {
 	return pkg.Lookup(name)
 }
 
-// tpkg returns the package that a function, interface, or struct type
+// tpkg returns the package that a function, interface, struct, or typeparam type
 // expression appeared in.
 //
 // Caveat: For the degenerate types "func()", "interface{}", and
@@ -373,6 +396,8 @@ func (g *irgen) tpkg(typ types2.Type) *types.Pkg {
 			if typ.NumExplicitMethods() > 0 {
 				return typ.ExplicitMethod(0)
 			}
+		case *types2.TypeParam:
+			return typ.Obj()
 		}
 		return nil
 	}