cmd/compile/internal/types2: avoid infinite expansion for invalid recursive generic types
The algorithm for detecting invalid recursive types that
expand indefinitely suffered from the exact problem is was
intended to detect: if the indefinite expansion is happening
through type parameters, the algorithm ended up in an infinite
sequence of instantiations. (This is only a problem for generic
types).
Changed the algorithm to always only consider the "original"
uninstantiated types. This avoids the problem but it will also
not detect some invalid recursive generic types anymore. That
requires a more sophisticated type flow analysis.
Opened #48962 to track.
Addressed with help from @findleyr.
For #48951.
Change-Id: Ie29cea8f810dae55153dbb1b17c9390cd823c2d9
Reviewed-on: https://go-review.googlesource.com/c/go/+/355732
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
diff --git a/src/cmd/compile/internal/types2/decl.go b/src/cmd/compile/internal/types2/decl.go
index 26a16d9..9fd60d6 100644
--- a/src/cmd/compile/internal/types2/decl.go
+++ b/src/cmd/compile/internal/types2/decl.go
@@ -330,7 +330,16 @@
}
case *Named:
- t.resolve(check.conf.Context)
+ // If t is parameterized, we should be considering the instantiated (expanded)
+ // form of t, but in general we can't with this algorithm: if t is an invalid
+ // type it may be so because it infinitely expands through a type parameter.
+ // Instantiating such a type would lead to an infinite sequence of instantiations.
+ // In general, we need "type flow analysis" to recognize those cases.
+ // Example: type A[T any] struct{ x A[*T] } (issue #48951)
+ // In this algorithm we always only consider the orginal, uninstantiated type.
+ // This won't recognize some invalid cases with parameterized types, but it
+ // will terminate.
+ t = t.orig
// don't touch the type if it is from a different package or the Universe scope
// (doing so would lead to a race condition - was issue #35049)
@@ -359,7 +368,7 @@
check.cycleError(path[i:])
t.info = invalid
t.underlying = Typ[Invalid]
- return t.info
+ return invalid
}
}
panic("cycle start not found")
diff --git a/src/cmd/compile/internal/types2/testdata/check/issues.go2 b/src/cmd/compile/internal/types2/testdata/check/issues.go2
index effc2db..7c5659b 100644
--- a/src/cmd/compile/internal/types2/testdata/check/issues.go2
+++ b/src/cmd/compile/internal/types2/testdata/check/issues.go2
@@ -145,8 +145,8 @@
}
// Infinite generic type declarations must lead to an error.
-type inf1[T any] struct{ _ inf1 /* ERROR illegal cycle */ [T] }
-type inf2[T any] struct{ inf2 /* ERROR illegal cycle */ [T] }
+type inf1 /* ERROR illegal cycle */ [T any] struct{ _ inf1[T] }
+type inf2 /* ERROR illegal cycle */ [T any] struct{ inf2[T] }
// The implementation of conversions T(x) between integers and floating-point
// numbers checks that both T and x have either integer or floating-point
diff --git a/src/cmd/compile/internal/types2/testdata/fixedbugs/issue39634.go2 b/src/cmd/compile/internal/types2/testdata/fixedbugs/issue39634.go2
index 8e6bd97..200484b 100644
--- a/src/cmd/compile/internal/types2/testdata/fixedbugs/issue39634.go2
+++ b/src/cmd/compile/internal/types2/testdata/fixedbugs/issue39634.go2
@@ -37,8 +37,8 @@
// func main8() {}
// crash 9
-type foo9[A any] interface { foo9 /* ERROR illegal cycle */ [A] }
-func _() { var _ = new(foo9 /* ERROR illegal cycle */ [int]) }
+type foo9 /* ERROR illegal cycle */ [A any] interface { foo9[A] }
+func _() { var _ = new(foo9[int]) }
// crash 12
var u /* ERROR cycle */ , i [func /* ERROR used as value */ /* ERROR used as value */ (u, c /* ERROR undeclared */ /* ERROR undeclared */ ) {}(0, len /* ERROR must be called */ /* ERROR must be called */ )]c /* ERROR undeclared */ /* ERROR undeclared */
diff --git a/src/cmd/compile/internal/types2/testdata/fixedbugs/issue39938.go2 b/src/cmd/compile/internal/types2/testdata/fixedbugs/issue39938.go2
index 0da6e10..31bec5f 100644
--- a/src/cmd/compile/internal/types2/testdata/fixedbugs/issue39938.go2
+++ b/src/cmd/compile/internal/types2/testdata/fixedbugs/issue39938.go2
@@ -3,6 +3,8 @@
// license that can be found in the LICENSE file.
// Check "infinite expansion" cycle errors across instantiated types.
+// We can't detect these errors anymore at the moment. See #48962 for
+// details.
package p
@@ -11,11 +13,11 @@
type E2[P any] struct{ _ P }
type E3[P any] struct{ _ *P }
-type T0 /* ERROR illegal cycle */ struct {
+type T0 /* illegal cycle */ struct {
_ E0[T0]
}
-type T0_ /* ERROR illegal cycle */ struct {
+type T0_ /* illegal cycle */ struct {
E0[T0_]
}
@@ -23,7 +25,7 @@
_ E1[T1]
}
-type T2 /* ERROR illegal cycle */ struct {
+type T2 /* illegal cycle */ struct {
_ E2[T2]
}
@@ -33,7 +35,7 @@
// some more complex cases
-type T4 /* ERROR illegal cycle */ struct {
+type T4 /* illegal cycle */ struct {
_ E0[E2[T4]]
}
@@ -41,7 +43,7 @@
_ E0[E2[E0[E1[E2[[10]T5]]]]]
}
-type T6 /* ERROR illegal cycle */ struct {
+type T6 /* illegal cycle */ struct {
_ E0[[10]E2[E0[E2[E2[T6]]]]]
}
diff --git a/src/cmd/compile/internal/types2/testdata/fixedbugs/issue48951.go2 b/src/cmd/compile/internal/types2/testdata/fixedbugs/issue48951.go2
new file mode 100644
index 0000000..cf02cc1
--- /dev/null
+++ b/src/cmd/compile/internal/types2/testdata/fixedbugs/issue48951.go2
@@ -0,0 +1,21 @@
+// Copyright 2020 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
+
+type (
+ A1 /* ERROR illegal cycle */ [P any] [10]A1[P]
+ A2 /* ERROR illegal cycle */ [P any] [10]A2[*P]
+ A3[P any] [10]*A3[P]
+
+ L1[P any] []L1[P]
+
+ S1 /* ERROR illegal cycle */ [P any] struct{ f S1[P] }
+ S2 /* ERROR illegal cycle */ [P any] struct{ f S2[*P] } // like example in issue
+ S3[P any] struct{ f *S3[P] }
+
+ I1 /* ERROR illegal cycle */ [P any] interface{ I1[P] }
+ I2 /* ERROR illegal cycle */ [P any] interface{ I2[*P] }
+ I3[P any] interface{ *I3 /* ERROR interface contains type constraints */ [P] }
+)
