Attention is currently required from: Robert Griesemer, Robert Griesemer.
Robert Griesemer uploaded patch set #2 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Robert Griesemer, TryBot-Result+1 by Gopher Robot
go/types, types2: use exact unification for component types
This change defines two unification modes used to control
unification:
- assign set when unifying types being assigned to each other
- exact set when unification must be exact
Currently, unification is inexact: when a defined type is compared
against a type literal, the underlying type of the defined type is
considered (inexact match). When channel types are compared, the
channel direction is ignored. And when defined types are compared
where one (or both) are interfaces, interface unification is used.
By contrast, exact unification requires types to match exactly:
if they can be unified, the types must be identical (with suitable
type arguments).
Exact unification is required when comparing component types.
For instance, when unifying func(x P) with func(x Q), the two
signatures unify only if P is identical to Q per Go's assignment
rules.
Until now we have ignored exact unification and made due with inexact
unification everywhere, even for component types. In some cases this
led to infinite recursions in the unifier, which we guarded against
with a depth limit (and unification failure).
Go's assignmemt rules allow inexact matching at the top-level but
exact matching for element types.
This change passes 'assign' to the unifier when unifying parameter
against argument types because those follow assignment rules.
When comparing constraints, inexact unification is used as before.
In 'assign' mode, when comparing element types, the unifyier is
called recursively, this time with the 'exact' mode set, causing
element types to be compared exactly.
This change fixes #60460. It also fixes a bug in the test for
issue #60377. We also don't need to rely anymore on the recursion
depth limit (a temporary fix) for #59740. Finally, because we use
exact unification when comparing element types which are channels,
errors caused by assignment failures (due to inexact inference which
succeeded when it shouldn't have) now produce the correct inference
error.
Fixes #60460.
For #60377.
For #59740.
Change-Id: Icb6a9b4dbd34294f99328a06d52135cb499cab85
---
M src/cmd/compile/internal/types2/infer.go
M src/cmd/compile/internal/types2/unify.go
M src/go/types/infer.go
M src/go/types/unify.go
M src/internal/types/testdata/examples/functions.go
M src/internal/types/testdata/fixedbugs/issue60377.go
A src/internal/types/testdata/fixedbugs/issue60460.go
7 files changed, 151 insertions(+), 45 deletions(-)
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Robert Griesemer, Robert Griesemer.
Robert Griesemer uploaded patch set #3 to this change.
go/types, types2: use exact unification for component types
This change defines two unification modes used to control unification:
- assign set when unification follows assignmemt rules
- exact set when unification follows type identity rules
Currently, unification is inexact: when a defined type is compared
against a type literal, the underlying type of the defined type is
considered. When channel types are compared, the channel direction
is ignored. And when defined types are compared where one (or both)
are interfaces, interface unification is used.
By contrast, exact unification requires types to match exactly:
if they can be unified, the types must be identical (with suitable
type arguments).
Exact unification is required when comparing component types.
For instance, when unifying func(x P) with func(x Q), the two
signatures unify only if P is identical to Q per Go's assignment
rules.
Until now we have ignored exact unification and made due with inexact
unification everywhere, even for component types. In some cases this
led to infinite recursions in the unifier, which we guarded against
with a depth limit (and unification failure).
Go's assignmemt rules allow inexact matching at the top-level but
exact matching for element types.
This change passes 'assign' to the unifier when unifying parameter
against argument types because those follow assignment rules.
When comparing constraints, inexact unification is used as before.
In 'assign' mode, when comparing element types, the unifyier is
called recursively, this time with the 'exact' mode set, causing
element types to be compared exactly. If unification succeeds for
element types, they are identical (with suitable type arguments).
This change fixes #60460. It also fixes a bug in the test for
issue #60377. We also don't need to rely anymore on the recursion
depth limit (a temporary fix) for #59740. Finally, because we use
exact unification when comparing element types which are channels,
errors caused by assignment failures (due to inexact inference which
succeeded when it shouldn't have) now produce the correct inference
error.
Fixes #60460.
For #60377.
For #59740.
Change-Id: Icb6a9b4dbd34294f99328a06d52135cb499cab85
---
M src/cmd/compile/internal/types2/infer.go
M src/cmd/compile/internal/types2/unify.go
M src/go/types/infer.go
M src/go/types/unify.go
M src/internal/types/testdata/examples/functions.go
M src/internal/types/testdata/fixedbugs/issue60377.go
A src/internal/types/testdata/fixedbugs/issue60460.go
7 files changed, 139 insertions(+), 33 deletions(-)
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Robert Findley, Robert Griesemer.
Patch set 4:Run-TryBot +1Code-Review +1
Attention is currently required from: Robert Griesemer.
Patch set 4:Code-Review +2
1 comment:
File src/cmd/compile/internal/types2/unify.go:
assign unifyMode = 1 << iota // unification follows assignment rules
exact
I'm not sure what (assign|exact) means, so I feel like mode should simply have three values inexact, assign, and exact. (as opposed to 4 possible values with bit flags).
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Robert Griesemer, Robert Griesemer.
Robert Griesemer uploaded patch set #5 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Robert Griesemer, TryBot-Result+1 by Gopher Robot
go/types, types2: use exact unification for component types
This change defines two unification modes used to control unification:
- assign set when unifying types involved in an assignment
- exact if set, types unify if they can be made identical
Currently, unification is inexact: when a defined type is compared
against a type literal, the underlying type of the defined type is
considered. When channel types are compared, the channel direction
is ignored. And when defined types are compared where one (or both)
are interfaces, interface unification is used.
By contrast, exact unification requires types to match exactly:
if they can be unified, the types must be identical (with suitable
type arguments).
Exact unification is required when comparing component types.
For instance, when unifying func(x P) with func(x Q), the two
signatures unify only if P is identical to Q per Go's assignment
rules.
Until now we have ignored exact unification and made due with inexact
unification everywhere, even for component types. In some cases this
led to infinite recursions in the unifier, which we guarded against
with a depth limit (and unification failure).
Go's assignmemt rules allow inexact matching at the top-level but
require exact matching for element types.
7 files changed, 159 insertions(+), 33 deletions(-)
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Robert Griesemer, Robert Griesemer.
Patch set 4:Run-TryBot +1Code-Review +1
2 comments:
Patchset:
Thanks for the quick review!
File src/cmd/compile/internal/types2/unify.go:
assign unifyMode = 1 << iota // unification follows assignment rules
exact
I'm not sure what (assign|exact) means, so I feel like mode should simply have three values inexact, […]
I've tried the three-value approach (I used <0, 0, >0) and it is a bit more problematic: in "assign" mode we are inexact at the top-level, and exact at lower levels of types. That means we switch from assign to exact (and loose the information about assignments - which is fine now but perhaps useful in other ways). Also, we cannot test "mode == inexact", we must test "mode != exact" (or "mode == inexact || mode == assign"). The latter is more complicated than what we have now, and the former needs explanation: why is "mode != exact" not the same as "mode == inexact".
What we have now is two bits: one that says whether we're dealing with assignments or not, and another one that says whether comparison is exact or not. This seems clearer. (And in the future we may have other modes, irrespective of the exactness.)
I clarified the constant comments, but otherwise prefer to leave as is for now.
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Robert Griesemer.
Patch set 5:Run-TryBot +1Auto-Submit +1Code-Review +1
Attention is currently required from: Robert Griesemer.
Patch set 5:-Auto-Submit
Attention is currently required from: Robert Griesemer, Robert Griesemer.
Patch set 5:Code-Review +2
1 comment:
File src/cmd/compile/internal/types2/unify.go:
assign unifyMode = 1 << iota // unification follows assignment rules
exact
I've tried the three-value approach (I used <0, 0, >0) and it is a bit more problematic: in "assign" […]
Ok; I'm not sure what mode exactly is correct for constraints. Surely they need to have exact matching of components too? But I am willing to defer that discussion until later, and this change looks correct for assignment contexts.
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Robert Griesemer.
1 comment:
File src/cmd/compile/internal/types2/unify.go:
assign unifyMode = 1 << iota // unification follows assignment rules
exact
Ok; I'm not sure what mode exactly is correct for constraints. […]
Yes, I think we do. But it may be two levels down, instead of one. But agreed, this can wait for 1.22.
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Robert Griesemer, Robert Griesemer.
Robert Griesemer uploaded patch set #6 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Robert Griesemer, TryBot-Result+1 by Gopher Robot
The change is no longer submittable: TryBots-Pass is unsatisfied now.
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Robert Griesemer.
Patch set 6:Run-TryBot +1Auto-Submit +1Code-Review +1
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.
Gopher Robot submitted this change.
5 is the latest approved patch-set.
No files were changed between the latest approved patch-set and the submitted one.
Reviewed-on: https://go-review.googlesource.com/c/go/+/498895
Reviewed-by: Robert Findley <rfin...@google.com>
Auto-Submit: Robert Griesemer <g...@google.com>
Run-TryBot: Robert Griesemer <g...@google.com>
Reviewed-by: Robert Griesemer <g...@google.com>
TryBot-Result: Gopher Robot <go...@golang.org>
---
M src/cmd/compile/internal/types2/infer.go
M src/cmd/compile/internal/types2/unify.go
M src/go/types/infer.go
M src/go/types/unify.go
M src/internal/types/testdata/examples/functions.go
M src/internal/types/testdata/fixedbugs/issue60377.go
A src/internal/types/testdata/fixedbugs/issue60460.go
7 files changed, 159 insertions(+), 33 deletions(-)
diff --git a/src/cmd/compile/internal/types2/infer.go b/src/cmd/compile/internal/types2/infer.go
index efa5727..c323344 100644
--- a/src/cmd/compile/internal/types2/infer.go
+++ b/src/cmd/compile/internal/types2/infer.go
@@ -155,7 +155,7 @@
// Function parameters are always typed. Arguments may be untyped.
// Collect the indices of untyped arguments and handle them later.
if isTyped(arg.typ) {
- if !u.unify(par.typ, arg.typ, 0) {
+ if !u.unify(par.typ, arg.typ, assign) {
errorf("type", par.typ, arg.typ, arg)
return nil
}
@@ -340,7 +340,7 @@
arg := args[i]
typ := Default(arg.typ)
assert(isTyped(typ))
- if !u.unify(tpar, typ, 0) {
+ if !u.unify(tpar, typ, assign) {
errorf("default type", tpar, typ, arg)
return nil
}
diff --git a/src/cmd/compile/internal/types2/unify.go b/src/cmd/compile/internal/types2/unify.go
index 1d2b9d1..3f54a2c 100644
--- a/src/cmd/compile/internal/types2/unify.go
+++ b/src/cmd/compile/internal/types2/unify.go
@@ -47,7 +47,7 @@
// Whether to panic when unificationDepthLimit is reached.
// If disabled, a recursion depth overflow results in a (quiet)
// unification failure.
- panicAtUnificationDepthLimit = false // go.dev/issue/59740
+ panicAtUnificationDepthLimit = true
// If enableCoreTypeUnification is set, unification will consider
// the core types, if any, of non-local (unbound) type parameters.
@@ -109,8 +109,24 @@
// unifyMode controls the behavior of the unifier.
type unifyMode uint
+const (
+ // If assign is set, we are unifying types involved in an assignment:
+ // they may match inexactly at the top, but element types must match
+ // exactly.
+ assign unifyMode = 1 << iota
+
+ // If exact is set, types unify if they are identical (or can be
+ // made identical with suitable arguments for type parameters).
+ // Otherwise, a named type and a type literal unify if their
+ // underlying types unify, channel directions are ignored, and
+ // if there is an interface, the other type must implement the
+ // interface.
+ exact
+)
+
// unify attempts to unify x and y and reports whether it succeeded.
// As a side-effect, types may be inferred for type parameters.
+// The mode parameter controls how types are compared.
func (u *unifier) unify(x, y Type, mode unifyMode) bool {
return u.nify(x, y, mode, nil)
}
@@ -284,11 +300,11 @@
}
// Unification will fail if we match a defined type against a type literal.
- // Per the (spec) assignment rules, assignments of values to variables with
+ // If we are matching types in an assignment, at the top-level, types with
// the same type structure are permitted as long as at least one of them
// is not a defined type. To accommodate for that possibility, we continue
// unification with the underlying type of a defined type if the other type
- // is a type literal.
+ // is a type literal. This is controlled by the exact unification mode.
// We also continue if the other type is a basic type because basic types
// are valid underlying types and may appear as core types of type constraints.
// If we exclude them, inferred defined types for type parameters may not
@@ -300,7 +316,7 @@
// we will fail at function instantiation or argument assignment time.
//
// If we have at least one defined type, there is one in y.
- if ny, _ := y.(*Named); ny != nil && isTypeLit(x) && !(enableInterfaceInference && IsInterface(x)) {
+ if ny, _ := y.(*Named); mode&exact == 0 && ny != nil && isTypeLit(x) && !(enableInterfaceInference && IsInterface(x)) {
if traceInference {
u.tracef("%s ≡ under %s", x, ny)
}
@@ -365,7 +381,11 @@
}
// Type elements (array, slice, etc. elements) use emode for unification.
+ // Element types must match exactly if the types are used in an assignment.
emode := mode
+ if mode&assign != 0 {
+ emode |= exact
+ }
// If EnableInterfaceInference is set and both types are interfaces, one
// interface must have a subset of the methods of the other and corresponding
@@ -613,9 +633,11 @@
}
case *Chan:
- // Two channel types unify if their value types unify.
+ // Two channel types unify if their value types unify
+ // and if they have the same direction.
+ // The channel direction is ignored for inexact unification.
if y, ok := y.(*Chan); ok {
- return u.nify(x.elem, y.elem, emode, p)
+ return (mode&exact == 0 || x.dir == y.dir) && u.nify(x.elem, y.elem, emode, p)
}
case *Named:
@@ -625,7 +647,7 @@
// If one or both named types are interfaces, the types unify if the
// respective methods unify (per the rules for interface unification).
if y, ok := y.(*Named); ok {
- if enableInterfaceInference {
+ if enableInterfaceInference && mode&exact == 0 {
xi, _ := x.under().(*Interface)
yi, _ := y.under().(*Interface)
// If one or both of x and y are interfaces, use interface unification.
diff --git a/src/go/types/infer.go b/src/go/types/infer.go
index 7032aee..015edb5 100644
--- a/src/go/types/infer.go
+++ b/src/go/types/infer.go
@@ -157,7 +157,7 @@
// Function parameters are always typed. Arguments may be untyped.
// Collect the indices of untyped arguments and handle them later.
if isTyped(arg.typ) {
- if !u.unify(par.typ, arg.typ, 0) {
+ if !u.unify(par.typ, arg.typ, assign) {
errorf("type", par.typ, arg.typ, arg)
return nil
}
@@ -342,7 +342,7 @@
arg := args[i]
typ := Default(arg.typ)
assert(isTyped(typ))
- if !u.unify(tpar, typ, 0) {
+ if !u.unify(tpar, typ, assign) {
errorf("default type", tpar, typ, arg)
return nil
}
diff --git a/src/go/types/unify.go b/src/go/types/unify.go
index 1e9efee..217356f 100644
--- a/src/go/types/unify.go
+++ b/src/go/types/unify.go
@@ -49,7 +49,7 @@
// Whether to panic when unificationDepthLimit is reached.
// If disabled, a recursion depth overflow results in a (quiet)
// unification failure.
- panicAtUnificationDepthLimit = false // go.dev/issue/59740
+ panicAtUnificationDepthLimit = true
// If enableCoreTypeUnification is set, unification will consider
// the core types, if any, of non-local (unbound) type parameters.
@@ -111,8 +111,24 @@
// unifyMode controls the behavior of the unifier.
type unifyMode uint
+const (
+ // If assign is set, we are unifying types involved in an assignment:
+ // they may match inexactly at the top, but element types must match
+ // exactly.
+ assign unifyMode = 1 << iota
+
+ // If exact is set, types unify if they are identical (or can be
+ // made identical with suitable arguments for type parameters).
+ // Otherwise, a named type and a type literal unify if their
+ // underlying types unify, channel directions are ignored, and
+ // if there is an interface, the other type must implement the
+ // interface.
+ exact
+)
+
// unify attempts to unify x and y and reports whether it succeeded.
// As a side-effect, types may be inferred for type parameters.
+// The mode parameter controls how types are compared.
func (u *unifier) unify(x, y Type, mode unifyMode) bool {
return u.nify(x, y, mode, nil)
}
@@ -286,11 +302,11 @@
}
// Unification will fail if we match a defined type against a type literal.
- // Per the (spec) assignment rules, assignments of values to variables with
+ // If we are matching types in an assignment, at the top-level, types with
// the same type structure are permitted as long as at least one of them
// is not a defined type. To accommodate for that possibility, we continue
// unification with the underlying type of a defined type if the other type
- // is a type literal.
+ // is a type literal. This is controlled by the exact unification mode.
// We also continue if the other type is a basic type because basic types
// are valid underlying types and may appear as core types of type constraints.
// If we exclude them, inferred defined types for type parameters may not
@@ -302,7 +318,7 @@
// we will fail at function instantiation or argument assignment time.
//
// If we have at least one defined type, there is one in y.
- if ny, _ := y.(*Named); ny != nil && isTypeLit(x) && !(enableInterfaceInference && IsInterface(x)) {
+ if ny, _ := y.(*Named); mode&exact == 0 && ny != nil && isTypeLit(x) && !(enableInterfaceInference && IsInterface(x)) {
if traceInference {
u.tracef("%s ≡ under %s", x, ny)
}
@@ -367,7 +383,11 @@
}
// Type elements (array, slice, etc. elements) use emode for unification.
+ // Element types must match exactly if the types are used in an assignment.
emode := mode
+ if mode&assign != 0 {
+ emode |= exact
+ }
// If EnableInterfaceInference is set and both types are interfaces, one
// interface must have a subset of the methods of the other and corresponding
@@ -615,9 +635,11 @@
}
case *Chan:
- // Two channel types unify if their value types unify.
+ // Two channel types unify if their value types unify
+ // and if they have the same direction.
+ // The channel direction is ignored for inexact unification.
if y, ok := y.(*Chan); ok {
- return u.nify(x.elem, y.elem, emode, p)
+ return (mode&exact == 0 || x.dir == y.dir) && u.nify(x.elem, y.elem, emode, p)
}
case *Named:
@@ -627,7 +649,7 @@
// If one or both named types are interfaces, the types unify if the
// respective methods unify (per the rules for interface unification).
if y, ok := y.(*Named); ok {
- if enableInterfaceInference {
+ if enableInterfaceInference && mode&exact == 0 {
xi, _ := x.under().(*Interface)
yi, _ := y.under().(*Interface)
// If one or both of x and y are interfaces, use interface unification.
diff --git a/src/internal/types/testdata/examples/functions.go b/src/internal/types/testdata/examples/functions.go
index c9917ee..fdc67e7 100644
--- a/src/internal/types/testdata/examples/functions.go
+++ b/src/internal/types/testdata/examples/functions.go
@@ -150,15 +150,15 @@
var send func(chan<- int)
ffboth(both)
- ffboth(recv /* ERROR "cannot use" */ )
- ffboth(send /* ERROR "cannot use" */ )
+ ffboth(recv /* ERROR "does not match" */ )
+ ffboth(send /* ERROR "does not match" */ )
- ffrecv(both /* ERROR "cannot use" */ )
+ ffrecv(both /* ERROR "does not match" */ )
ffrecv(recv)
- ffrecv(send /* ERROR "cannot use" */ )
+ ffrecv(send /* ERROR "does not match" */ )
- ffsend(both /* ERROR "cannot use" */ )
- ffsend(recv /* ERROR "cannot use" */ )
+ ffsend(both /* ERROR "does not match" */ )
+ ffsend(recv /* ERROR "does not match" */ )
ffsend(send)
}
diff --git a/src/internal/types/testdata/fixedbugs/issue60377.go b/src/internal/types/testdata/fixedbugs/issue60377.go
index be37c51..b754f89 100644
--- a/src/internal/types/testdata/fixedbugs/issue60377.go
+++ b/src/internal/types/testdata/fixedbugs/issue60377.go
@@ -61,20 +61,14 @@
}
// This is similar to the first example but here T1 is a component
-// of a func type. In this case we should be able to infer a type
-// argument for P because component types must be identical even
-// in the case of interfaces.
-// This is a short-coming of type inference at the moment, but it
-// is better to not be able to infer a type here (we can always
-// supply one), than to infer the wrong type in other cases (see
-// below). Finally, if we decide to accept go.dev/issues/8082,
-// the behavior here is correct.
+// of a func type. In this case types must match exactly: P must
+// match int.
func g5[P any](func(T1[P])) {}
func _() {
var f func(T1[int])
- g5 /* ERROR "cannot infer P" */ (f)
+ g5(f)
g5[int](f)
g5[string](f /* ERROR "cannot use f (variable of type func(T1[int])) as func(T1[string]) value in argument to g5[string]" */)
}
diff --git a/src/internal/types/testdata/fixedbugs/issue60460.go b/src/internal/types/testdata/fixedbugs/issue60460.go
new file mode 100644
index 0000000..a9cb3d9
--- /dev/null
+++ b/src/internal/types/testdata/fixedbugs/issue60460.go
@@ -0,0 +1,88 @@
+// Copyright 2023 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package p
+
+// Simplified (representative) test case.
+
+func _() {
+ f(R1{})
+}
+
+func f[T any](R[T]) {}
+
+type R[T any] interface {
+ m(R[T])
+}
+
+type R1 struct{}
+
+func (R1) m(R[int]) {}
+
+// Test case from issue.
+
+func _() {
+ r := newTestRules()
+ NewSet(r)
+ r2 := newTestRules2()
+ NewSet(r2)
+}
+
+type Set[T any] struct {
+ rules Rules[T]
+}
+
+func NewSet[T any](rules Rules[T]) Set[T] {
+ return Set[T]{
+ rules: rules,
+ }
+}
+
+func (s Set[T]) Copy() Set[T] {
+ return NewSet(s.rules)
+}
+
+type Rules[T any] interface {
+ Hash(T) int
+ Equivalent(T, T) bool
+ SameRules(Rules[T]) bool
+}
+
+type testRules struct{}
+
+func newTestRules() Rules[int] {
+ return testRules{}
+}
+
+func (r testRules) Hash(val int) int {
+ return val % 16
+}
+
+func (r testRules) Equivalent(val1 int, val2 int) bool {
+ return val1 == val2
+}
+
+func (r testRules) SameRules(other Rules[int]) bool {
+ _, ok := other.(testRules)
+ return ok
+}
+
+type testRules2 struct{}
+
+func newTestRules2() Rules[string] {
+ return testRules2{}
+}
+
+func (r testRules2) Hash(val string) int {
+ return 16
+}
+
+func (r testRules2) Equivalent(val1 string, val2 string) bool {
+ return val1 == val2
+}
+
+func (r testRules2) SameRules(other Rules[string]) bool {
+ _, ok := other.(testRules2)
+ return ok
+}
To view, visit change 498895. To unsubscribe, or for help writing mail filters, visit settings.