[dev.typeparams] cmd/compile: export/import of recursive generic types.

Deal with export/import of recursive generic types. This includes
typeparams which have bounds that reference the typeparam.

There are three main changes:

  - Change export/import of typeparams to have an implicit "declaration"
    (doDecl). We need to do a declaration of typeparams (via the
    typeparam's package and unique name), because it may be referenced
    within its bound during its own definition.

  - We delay most of the processing of the Instantiate call until we
    finish the creation of the top-most type (similar to the way we
    delay CheckSize). This is because we can't do the full instantiation
    properly until the base type is fully defined (with methods). The
    functions delayDoInst() and resumeDoInst() delay and resume the
    processing of the instantiations.

  - To do the full needed type substitutions for type instantiations
    during import, I had to separate out the type subster in stencil.go
    and move it to subr.go in the typecheck package. The subster in
    stencil.go now does node substitution and makes use of the type
    subster to do type substitutions.

Notable other changes:
 - In types/builtins.go, put the newly defined typeparam for a union type
   (related to use of real/imag, etc.) in the current package, rather
   than the builtin package, so exports/imports work properly.

 - In types2, allowed NewTypeParam() to be called with a nil bound, and
   allow setting the bound later. (Needed to import a typeparam whose
   bound refers to the typeparam itself.)

 - During import of typeparams in types2 (importer/import.go), we need
   to keep an index of the typeparams by their package and unique name
   (with id). Use a new map typParamIndex[] for that. Again, this is
   needed to deal with typeparams whose bounds refer to the typeparam
   itself.

 - Added several new tests absdiffimp.go and orderedmapsimp.go. Some of
   the orderemapsimp tests are commented out for now, because there are
   some issues with closures inside instantiations (relating to unexported
   names of closure structs).

 - Renamed some typeparams in test value.go to make them all T (to make
   typeparam uniqueness is working fine).

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

1 files changed, 137 insertions, 35 deletions

diff --git a/src/cmd/compile/internal/typecheck/iimport.go b/src/cmd/compile/internal/typecheck/iimport.go
index 96107b657b..9e6115cbf7 100644
--- a/src/cmd/compile/internal/typecheck/iimport.go
+++ b/src/cmd/compile/internal/typecheck/iimport.go
@@ -342,19 +342,22 @@ func (r *importReader) doDecl(sym *types.Sym) *ir.Name {
 		// declaration before recursing.
 		n := importtype(r.p.ipkg, pos, sym)
 		t := n.Type()
+		if rparams != nil {
+			t.SetRParams(rparams)
+		}
 
 		// We also need to defer width calculations until
 		// after the underlying type has been assigned.
 		types.DeferCheckSize()
+		deferDoInst()
 		underlying := r.typ()
 		t.SetUnderlying(underlying)
-		types.ResumeCheckSize()
-
-		if rparams != nil {
-			t.SetRParams(rparams)
-		}
 
 		if underlying.IsInterface() {
+			// Finish up all type instantiations and CheckSize calls
+			// now that a top-level type is fully constructed.
+			resumeDoInst()
+			types.ResumeCheckSize()
 			r.typeExt(t)
 			return n
 		}
@@ -380,12 +383,38 @@ func (r *importReader) doDecl(sym *types.Sym) *ir.Name {
 		}
 		t.Methods().Set(ms)
 
+		// Finish up all instantiations and CheckSize calls now
+		// that a top-level type is fully constructed.
+		resumeDoInst()
+		types.ResumeCheckSize()
+
 		r.typeExt(t)
 		for _, m := range ms {
 			r.methExt(m)
 		}
 		return n
 
+	case 'P':
+		if r.p.exportVersion < iexportVersionGenerics {
+			base.Fatalf("unexpected type param type")
+		}
+		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.(*ir.Name)
+		}
+		index := int(r.int64())
+		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(r.typ())
+		return nname
+
 	case 'V':
 		typ := r.typ()
 
@@ -545,7 +574,12 @@ func (r *importReader) pos() src.XPos {
 }
 
 func (r *importReader) typ() *types.Type {
-	return r.p.typAt(r.uint64())
+	// If this is a top-level type call, defer type instantiations until the
+	// type is fully constructed.
+	deferDoInst()
+	t := r.p.typAt(r.uint64())
+	resumeDoInst()
+	return t
 }
 
 func (r *importReader) exoticType() *types.Type {
@@ -683,7 +717,13 @@ func (p *iimporter) typAt(off uint64) *types.Type {
 		// are pushed to compile queue, then draining from the queue for compiling.
 		// During this process, the size calculation is disabled, so it is not safe for
 		// calculating size during SSA generation anymore. See issue #44732.
-		types.CheckSize(t)
+		//
+		// No need to calc sizes for re-instantiated generic types, and
+		// they are not necessarily resolved until the top-level type is
+		// defined (because of recursive types).
+		if t.OrigSym == nil || !t.HasTParam() {
+			types.CheckSize(t)
+		}
 		p.typCache[off] = t
 	}
 	return t
@@ -779,27 +819,18 @@ func (r *importReader) typ1() *types.Type {
 		if r.p.exportVersion < iexportVersionGenerics {
 			base.Fatalf("unexpected type param type")
 		}
-		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()
+		// Similar to code for defined types, since we "declared"
+		// typeparams to deal with recursion (typeparam is used within its
+		// own type bound).
+		ident := r.qualifiedIdent()
+		if ident.Sym().Def != nil {
+			return ident.Sym().Def.(*ir.Name).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
+		n := expandDecl(ident)
+		if n.Op() != ir.OTYPE {
+			base.Fatalf("expected OTYPE, got %v: %v, %v", n.Op(), n.Sym(), n)
+		}
+		return n.Type()
 
 	case instType:
 		if r.p.exportVersion < iexportVersionGenerics {
@@ -1758,20 +1789,91 @@ func Instantiate(pos src.XPos, baseType *types.Type, targs []*types.Type) *types
 	name := InstTypeName(baseSym.Name, targs)
 	instSym := baseSym.Pkg.Lookup(name)
 	if instSym.Def != nil {
+		// May match existing type from previous import or
+		// types2-to-types1 conversion, or from in-progress instantiation
+		// in the current type import stack.
 		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
 
+	// baseType may still be TFORW or its methods may not be fully filled in
+	// (since we are in the middle of importing it). So, delay call to
+	// substInstType until we get back up to the top of the current top-most
+	// type import.
+	deferredInstStack = append(deferredInstStack, t)
+
 	return t
 }
+
+var deferredInstStack []*types.Type
+var deferInst int
+
+// deferDoInst defers substitution on instantiated types until we are at the
+// top-most defined type, so the base types are fully defined.
+func deferDoInst() {
+	deferInst++
+}
+
+func resumeDoInst() {
+	if deferInst == 1 {
+		for len(deferredInstStack) > 0 {
+			t := deferredInstStack[0]
+			deferredInstStack = deferredInstStack[1:]
+			substInstType(t, t.OrigSym.Def.(*ir.Name).Type(), t.RParams())
+		}
+	}
+	deferInst--
+}
+
+// doInst creates a new instantiation type (which will be added to
+// deferredInstStack for completion later) for an incomplete type encountered
+// during a type substitution for an instantiation. This is needed for
+// instantiations of mutually recursive types.
+func doInst(t *types.Type) *types.Type {
+	return Instantiate(t.Pos(), t.OrigSym.Def.(*ir.Name).Type(), t.RParams())
+}
+
+// substInstType completes the instantiation of a generic type by doing a
+// substitution on the underlying type itself and any methods. t is the
+// instantiation being created, baseType is the base generic type, and targs are
+// the type arguments that baseType is being instantiated with.
+func substInstType(t *types.Type, baseType *types.Type, targs []*types.Type) {
+	subst := Tsubster{
+		Tparams:       baseType.RParams(),
+		Targs:         targs,
+		SubstForwFunc: doInst,
+	}
+	t.SetUnderlying(subst.Typ(baseType.Underlying()))
+
+	newfields := make([]*types.Field, baseType.Methods().Len())
+	for i, f := range baseType.Methods().Slice() {
+		recvType := f.Type.Recv().Type
+		if recvType.IsPtr() {
+			recvType = recvType.Elem()
+		}
+		// Substitute in the method using the type params used in the
+		// method (not the type params in the definition of the generic type).
+		subst := Tsubster{
+			Tparams:       recvType.RParams(),
+			Targs:         targs,
+			SubstForwFunc: doInst,
+		}
+		t2 := subst.Typ(f.Type)
+		oldsym := f.Nname.Sym()
+		newsym := MakeInstName(oldsym, 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
+	}
+	t.Methods().Set(newfields)
+}