go/types, types2: remove need to store type parameter list in unifier

For unification we only need the handles map.
The type parameter list was stored for reproducible printing only,
but we can achieve the same effect with sorting.

This opens the door to adding type parameters from different
types/functions that we may want to infer together. They may
be added through separate "addTypeParams" calls in the future.
Printing (which is used for debugging only) will remain reproducible.

Change-Id: I23b56c63fa45a7d687761f2efcf558e61b004584
Reviewed-on: https://go-review.googlesource.com/c/go/+/466955
Reviewed-by: Robert Griesemer <gri@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>

2 files changed, 38 insertions, 12 deletions

diff --git a/src/cmd/compile/internal/types2/unify.go b/src/cmd/compile/internal/types2/unify.go
index fd9c71b1ec..c591ab9c39 100644
--- a/src/cmd/compile/internal/types2/unify.go
+++ b/src/cmd/compile/internal/types2/unify.go
@@ -9,6 +9,7 @@ package types2
 import (
 	"bytes"
 	"fmt"
+	"sort"
 	"strings"
 )
 
@@ -40,9 +41,6 @@ const (
 // corresponding types inferred for each type parameter.
 // A unifier is created by calling newUnifier.
 type unifier struct {
-	// tparams is the initial list of type parameters provided.
-	// Only used to print types in reproducible order.
-	tparams []*TypeParam
 	// handles maps each type parameter to its inferred type through
 	// an indirection *Type called (inferred type) "handle".
 	// Initially, each type parameter has its own, separate handle,
@@ -74,7 +72,7 @@ func newUnifier(tparams []*TypeParam, targs []Type) *unifier {
 		}
 		handles[x] = &t
 	}
-	return &unifier{tparams, handles, 0}
+	return &unifier{handles, 0}
 }
 
 // unify attempts to unify x and y and reports whether it succeeded.
@@ -90,10 +88,19 @@ func (u *unifier) tracef(format string, args ...interface{}) {
 // String returns a string representation of the current mapping
 // from type parameters to types.
 func (u *unifier) String() string {
+	// sort type parameters for reproducible strings
+	tparams := make(typeParamsById, len(u.handles))
+	i := 0
+	for tpar := range u.handles {
+		tparams[i] = tpar
+		i++
+	}
+	sort.Sort(tparams)
+
 	var buf bytes.Buffer
 	w := newTypeWriter(&buf, nil)
 	w.byte('[')
-	for i, x := range u.tparams {
+	for i, x := range tparams {
 		if i > 0 {
 			w.string(", ")
 		}
@@ -105,6 +112,12 @@ func (u *unifier) String() string {
 	return buf.String()
 }
 
+type typeParamsById []*TypeParam
+
+func (s typeParamsById) Len() int           { return len(s) }
+func (s typeParamsById) Less(i, j int) bool { return s[i].id < s[j].id }
+func (s typeParamsById) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
+
 // join unifies the given type parameters x and y.
 // If both type parameters already have a type associated with them
 // and they are not joined, join fails and returns false.
@@ -504,7 +517,7 @@ func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) {
 		// avoid a crash in case of nil type
 
 	default:
-		panic(sprintf(nil, true, "u.nify(%s, %s), u.tparams = %s", x, y, u.tparams))
+		panic(sprintf(nil, true, "u.nify(%s, %s)", x, y))
 	}
 
 	return false
diff --git a/src/go/types/unify.go b/src/go/types/unify.go
index 863a5c1093..0bb3e3960e 100644
--- a/src/go/types/unify.go
+++ b/src/go/types/unify.go
@@ -11,6 +11,7 @@ package types
 import (
 	"bytes"
 	"fmt"
+	"sort"
 	"strings"
 )
 
@@ -42,9 +43,6 @@ const (
 // corresponding types inferred for each type parameter.
 // A unifier is created by calling newUnifier.
 type unifier struct {
-	// tparams is the initial list of type parameters provided.
-	// Only used to print types in reproducible order.
-	tparams []*TypeParam
 	// handles maps each type parameter to its inferred type through
 	// an indirection *Type called (inferred type) "handle".
 	// Initially, each type parameter has its own, separate handle,
@@ -76,7 +74,7 @@ func newUnifier(tparams []*TypeParam, targs []Type) *unifier {
 		}
 		handles[x] = &t
 	}
-	return &unifier{tparams, handles, 0}
+	return &unifier{handles, 0}
 }
 
 // unify attempts to unify x and y and reports whether it succeeded.
@@ -92,10 +90,19 @@ func (u *unifier) tracef(format string, args ...interface{}) {
 // String returns a string representation of the current mapping
 // from type parameters to types.
 func (u *unifier) String() string {
+	// sort type parameters for reproducible strings
+	tparams := make(typeParamsById, len(u.handles))
+	i := 0
+	for tpar := range u.handles {
+		tparams[i] = tpar
+		i++
+	}
+	sort.Sort(tparams)
+
 	var buf bytes.Buffer
 	w := newTypeWriter(&buf, nil)
 	w.byte('[')
-	for i, x := range u.tparams {
+	for i, x := range tparams {
 		if i > 0 {
 			w.string(", ")
 		}
@@ -107,6 +114,12 @@ func (u *unifier) String() string {
 	return buf.String()
 }
 
+type typeParamsById []*TypeParam
+
+func (s typeParamsById) Len() int           { return len(s) }
+func (s typeParamsById) Less(i, j int) bool { return s[i].id < s[j].id }
+func (s typeParamsById) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
+
 // join unifies the given type parameters x and y.
 // If both type parameters already have a type associated with them
 // and they are not joined, join fails and returns false.
@@ -506,7 +519,7 @@ func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) {
 		// avoid a crash in case of nil type
 
 	default:
-		panic(sprintf(nil, nil, true, "u.nify(%s, %s), u.tparams = %s", x, y, u.tparams))
+		panic(sprintf(nil, nil, true, "u.nify(%s, %s)", x, y))
 	}
 
 	return false