From a4d5fbc3a48b63f19fcd2a4d040a85c75a2709b5 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Thu, 9 Feb 2023 09:23:41 -0800 Subject: [PATCH] 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 Run-TryBot: Robert Griesemer TryBot-Result: Gopher Robot Reviewed-by: Robert Findley Auto-Submit: Robert Griesemer --- src/cmd/compile/internal/types2/unify.go | 25 ++++++++++++++++++------ src/go/types/unify.go | 25 ++++++++++++++++++------ 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 -- 2.50.0