go/types, types2: eliminate need to sort arguments for type inference
When unifying types, we always consider underlying types if inference
would fail otherwise. If a type parameter has a (non-defined) type
inferred and later matches against a defined type, make sure to keep
that defined type instead.
For #43056.
Change-Id: I24e4cd2939df7c8069e505be10914017c1c1c288
Reviewed-on: https://go-review.googlesource.com/c/go/+/464348
Reviewed-by: 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>
Run-TryBot: Robert Griesemer <gri@google.com>
diff --git a/src/cmd/compile/internal/types2/infer.go b/src/cmd/compile/internal/types2/infer.go
index 671ce6a..6bf7c55 100644
--- a/src/cmd/compile/internal/types2/infer.go
+++ b/src/cmd/compile/internal/types2/infer.go
@@ -56,51 +56,6 @@
// Rename type parameters to avoid conflicts in recursive instantiation scenarios.
tparams, params = check.renameTParams(pos, tparams, params)
- // If we have more than 2 arguments, we may have arguments with named and unnamed types.
- // If that is the case, permutate params and args such that the arguments with named
- // types are first in the list. This doesn't affect type inference if all types are taken
- // as is. But when we have inexact unification enabled (as is the case for function type
- // inference), when a named type is unified with an unnamed type, unification proceeds
- // with the underlying type of the named type because otherwise unification would fail
- // right away. This leads to an asymmetry in type inference: in cases where arguments of
- // named and unnamed types are passed to parameters with identical type, different types
- // (named vs underlying) may be inferred depending on the order of the arguments.
- // By ensuring that named types are seen first, order dependence is avoided and unification
- // succeeds where it can (go.dev/issue/43056).
- const enableArgSorting = true
- if m := len(args); m >= 2 && enableArgSorting {
- // Determine indices of arguments with named and unnamed types.
- var named, unnamed []int
- for i, arg := range args {
- if hasName(arg.typ) {
- named = append(named, i)
- } else {
- unnamed = append(unnamed, i)
- }
- }
-
- // If we have named and unnamed types, move the arguments with
- // named types first. Update the parameter list accordingly.
- // Make copies so as not to clobber the incoming slices.
- if len(named) != 0 && len(unnamed) != 0 {
- params2 := make([]*Var, m)
- args2 := make([]*operand, m)
- i := 0
- for _, j := range named {
- params2[i] = params.At(j)
- args2[i] = args[j]
- i++
- }
- for _, j := range unnamed {
- params2[i] = params.At(j)
- args2[i] = args[j]
- i++
- }
- params = NewTuple(params2...)
- args = args2
- }
- }
-
// --- 1 ---
// Continue with the type arguments we have. Avoid matching generic
// parameters that already have type arguments against function arguments:
diff --git a/src/cmd/compile/internal/types2/infer2.go b/src/cmd/compile/internal/types2/infer2.go
index 6f0c1dd..f8a96c9 100644
--- a/src/cmd/compile/internal/types2/infer2.go
+++ b/src/cmd/compile/internal/types2/infer2.go
@@ -68,51 +68,6 @@
// Rename type parameters to avoid conflicts in recursive instantiation scenarios.
tparams, params = check.renameTParams(pos, tparams, params)
- // If we have more than 2 arguments, we may have arguments with named and unnamed types.
- // If that is the case, permutate params and args such that the arguments with named
- // types are first in the list. This doesn't affect type inference if all types are taken
- // as is. But when we have inexact unification enabled (as is the case for function type
- // inference), when a named type is unified with an unnamed type, unification proceeds
- // with the underlying type of the named type because otherwise unification would fail
- // right away. This leads to an asymmetry in type inference: in cases where arguments of
- // named and unnamed types are passed to parameters with identical type, different types
- // (named vs underlying) may be inferred depending on the order of the arguments.
- // By ensuring that named types are seen first, order dependence is avoided and unification
- // succeeds where it can (go.dev/issue/43056).
- const enableArgSorting = true
- if m := len(args); m >= 2 && enableArgSorting {
- // Determine indices of arguments with named and unnamed types.
- var named, unnamed []int
- for i, arg := range args {
- if hasName(arg.typ) {
- named = append(named, i)
- } else {
- unnamed = append(unnamed, i)
- }
- }
-
- // If we have named and unnamed types, move the arguments with
- // named types first. Update the parameter list accordingly.
- // Make copies so as not to clobber the incoming slices.
- if len(named) != 0 && len(unnamed) != 0 {
- params2 := make([]*Var, m)
- args2 := make([]*operand, m)
- i := 0
- for _, j := range named {
- params2[i] = params.At(j)
- args2[i] = args[j]
- i++
- }
- for _, j := range unnamed {
- params2[i] = params.At(j)
- args2[i] = args[j]
- i++
- }
- params = NewTuple(params2...)
- args = args2
- }
- }
-
// Make sure we have a "full" list of type arguments, some of which may
// be nil (unknown). Make a copy so as to not clobber the incoming slice.
if len(targs) < n {
diff --git a/src/cmd/compile/internal/types2/unify.go b/src/cmd/compile/internal/types2/unify.go
index 48be5ae..e73fd80 100644
--- a/src/cmd/compile/internal/types2/unify.go
+++ b/src/cmd/compile/internal/types2/unify.go
@@ -161,15 +161,13 @@
}
// set sets the type t for type parameter x;
-// t must not be nil and it must not have been set before.
+// t must not be nil.
func (u *unifier) set(x *TypeParam, t Type) {
assert(t != nil)
if traceInference {
u.tracef("%s ➞ %s", x, t)
}
- h := u.handles[x]
- assert(*h == nil)
- *h = t
+ *u.handles[x] = t
}
// unknowns returns the number of type parameters for which no type has been set yet.
@@ -259,7 +257,7 @@
}
// Cases where at least one of x or y is a type parameter recorded with u.
- // If we have ar least one type parameter, there is one in x.
+ // If we have at least one type parameter, there is one in x.
switch px, py := u.asTypeParam(x), u.asTypeParam(y); {
case px != nil && py != nil:
// both x and y are type parameters
@@ -271,8 +269,19 @@
case px != nil:
// x is a type parameter, y is not
- if tx := u.at(px); tx != nil {
- return u.nifyEq(tx, y, p)
+ if x := u.at(px); x != nil {
+ // x has an inferred type which must match y
+ if u.nifyEq(x, y, p) {
+ // If we have a match, possibly through underlying types,
+ // and y is a defined type, make sure we record that type
+ // for type parameter x, which may have until now only
+ // recorded an underlying type (go.dev/issue/43056).
+ if _, ok := y.(*Named); ok {
+ u.set(px, y)
+ }
+ return true
+ }
+ return false
}
// otherwise, infer type from y
u.set(px, y)
diff --git a/src/go/types/infer.go b/src/go/types/infer.go
index 93a43d3..a65cdce 100644
--- a/src/go/types/infer.go
+++ b/src/go/types/infer.go
@@ -58,51 +58,6 @@
// Rename type parameters to avoid conflicts in recursive instantiation scenarios.
tparams, params = check.renameTParams(posn.Pos(), tparams, params)
- // If we have more than 2 arguments, we may have arguments with named and unnamed types.
- // If that is the case, permutate params and args such that the arguments with named
- // types are first in the list. This doesn't affect type inference if all types are taken
- // as is. But when we have inexact unification enabled (as is the case for function type
- // inference), when a named type is unified with an unnamed type, unification proceeds
- // with the underlying type of the named type because otherwise unification would fail
- // right away. This leads to an asymmetry in type inference: in cases where arguments of
- // named and unnamed types are passed to parameters with identical type, different types
- // (named vs underlying) may be inferred depending on the order of the arguments.
- // By ensuring that named types are seen first, order dependence is avoided and unification
- // succeeds where it can (go.dev/issue/43056).
- const enableArgSorting = true
- if m := len(args); m >= 2 && enableArgSorting {
- // Determine indices of arguments with named and unnamed types.
- var named, unnamed []int
- for i, arg := range args {
- if hasName(arg.typ) {
- named = append(named, i)
- } else {
- unnamed = append(unnamed, i)
- }
- }
-
- // If we have named and unnamed types, move the arguments with
- // named types first. Update the parameter list accordingly.
- // Make copies so as not to clobber the incoming slices.
- if len(named) != 0 && len(unnamed) != 0 {
- params2 := make([]*Var, m)
- args2 := make([]*operand, m)
- i := 0
- for _, j := range named {
- params2[i] = params.At(j)
- args2[i] = args[j]
- i++
- }
- for _, j := range unnamed {
- params2[i] = params.At(j)
- args2[i] = args[j]
- i++
- }
- params = NewTuple(params2...)
- args = args2
- }
- }
-
// --- 1 ---
// Continue with the type arguments we have. Avoid matching generic
// parameters that already have type arguments against function arguments:
diff --git a/src/go/types/infer2.go b/src/go/types/infer2.go
index a0c2ac1..d763e3b 100644
--- a/src/go/types/infer2.go
+++ b/src/go/types/infer2.go
@@ -70,51 +70,6 @@
// Rename type parameters to avoid conflicts in recursive instantiation scenarios.
tparams, params = check.renameTParams(posn.Pos(), tparams, params)
- // If we have more than 2 arguments, we may have arguments with named and unnamed types.
- // If that is the case, permutate params and args such that the arguments with named
- // types are first in the list. This doesn't affect type inference if all types are taken
- // as is. But when we have inexact unification enabled (as is the case for function type
- // inference), when a named type is unified with an unnamed type, unification proceeds
- // with the underlying type of the named type because otherwise unification would fail
- // right away. This leads to an asymmetry in type inference: in cases where arguments of
- // named and unnamed types are passed to parameters with identical type, different types
- // (named vs underlying) may be inferred depending on the order of the arguments.
- // By ensuring that named types are seen first, order dependence is avoided and unification
- // succeeds where it can (go.dev/issue/43056).
- const enableArgSorting = true
- if m := len(args); m >= 2 && enableArgSorting {
- // Determine indices of arguments with named and unnamed types.
- var named, unnamed []int
- for i, arg := range args {
- if hasName(arg.typ) {
- named = append(named, i)
- } else {
- unnamed = append(unnamed, i)
- }
- }
-
- // If we have named and unnamed types, move the arguments with
- // named types first. Update the parameter list accordingly.
- // Make copies so as not to clobber the incoming slices.
- if len(named) != 0 && len(unnamed) != 0 {
- params2 := make([]*Var, m)
- args2 := make([]*operand, m)
- i := 0
- for _, j := range named {
- params2[i] = params.At(j)
- args2[i] = args[j]
- i++
- }
- for _, j := range unnamed {
- params2[i] = params.At(j)
- args2[i] = args[j]
- i++
- }
- params = NewTuple(params2...)
- args = args2
- }
- }
-
// Make sure we have a "full" list of type arguments, some of which may
// be nil (unknown). Make a copy so as to not clobber the incoming slice.
if len(targs) < n {
diff --git a/src/go/types/unify.go b/src/go/types/unify.go
index e104938..2e341b3 100644
--- a/src/go/types/unify.go
+++ b/src/go/types/unify.go
@@ -163,15 +163,13 @@
}
// set sets the type t for type parameter x;
-// t must not be nil and it must not have been set before.
+// t must not be nil.
func (u *unifier) set(x *TypeParam, t Type) {
assert(t != nil)
if traceInference {
u.tracef("%s ➞ %s", x, t)
}
- h := u.handles[x]
- assert(*h == nil)
- *h = t
+ *u.handles[x] = t
}
// unknowns returns the number of type parameters for which no type has been set yet.
@@ -261,7 +259,7 @@
}
// Cases where at least one of x or y is a type parameter recorded with u.
- // If we have ar least one type parameter, there is one in x.
+ // If we have at least one type parameter, there is one in x.
switch px, py := u.asTypeParam(x), u.asTypeParam(y); {
case px != nil && py != nil:
// both x and y are type parameters
@@ -273,8 +271,19 @@
case px != nil:
// x is a type parameter, y is not
- if tx := u.at(px); tx != nil {
- return u.nifyEq(tx, y, p)
+ if x := u.at(px); x != nil {
+ // x has an inferred type which must match y
+ if u.nifyEq(x, y, p) {
+ // If we have a match, possibly through underlying types,
+ // and y is a defined type, make sure we record that type
+ // for type parameter x, which may have until now only
+ // recorded an underlying type (go.dev/issue/43056).
+ if _, ok := y.(*Named); ok {
+ u.set(px, y)
+ }
+ return true
+ }
+ return false
}
// otherwise, infer type from y
u.set(px, y)
diff --git a/src/internal/types/testdata/examples/functions.go b/src/internal/types/testdata/examples/functions.go
index 4f58bb5..effb66c 100644
--- a/src/internal/types/testdata/examples/functions.go
+++ b/src/internal/types/testdata/examples/functions.go
@@ -174,15 +174,15 @@
func g3[T any](*T, ...T) {}
func _() {
- type intSlize []int
+ type intSlice []int
g1([]int{})
- g1(intSlize{})
+ g1(intSlice{})
g2(nil, 0)
type myString string
var s1 string
g3(nil, "1", myString("2"), "3")
- g3(& /* ERROR "does not match" */ s1, "1", myString("2"), "3")
+ g3(&s1, "1", myString /* ERROR `type myString of myString("2") does not match inferred type string for T` */ ("2"), "3")
_ = s1
type myStruct struct{x int}
