[dev.typeparams] cmd/compile/internal/types2: avoid endless recursion in Comparable predicate

Use a map to detect recursive types.
With this we can now typecheck fixedbugs/issue8501.go.

Updates #43088.

Change-Id: I7fad6ccf6c94268473ff72b09a3158e13a7f4cc3
Reviewed-on: https://go-review.googlesource.com/c/go/+/276374
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>

1 files changed, 15 insertions, 2 deletions

diff --git a/src/cmd/compile/internal/types2/predicates.go b/src/cmd/compile/internal/types2/predicates.go
index f3a5818b3f..048519471c 100644
--- a/src/cmd/compile/internal/types2/predicates.go
+++ b/src/cmd/compile/internal/types2/predicates.go
@@ -87,6 +87,11 @@ func IsInterface(typ Type) bool {
 
 // Comparable reports whether values of type T are comparable.
 func Comparable(T Type) bool {
+	return comparable(T, nil)
+}
+
+// comparable should only be called by Comparable.
+func comparable(T Type, seen map[Type]bool) bool {
 	// If T is a type parameter not constraint by any type
 	// list (i.e., it's underlying type is the top type),
 	// T is comparable if it has the == method. Otherwise,
@@ -99,6 +104,14 @@ func Comparable(T Type) bool {
 		return t.Bound().IsComparable()
 	}
 
+	if seen[T] {
+		return true
+	}
+	if seen == nil {
+		seen = make(map[Type]bool)
+	}
+	seen[T] = true
+
 	switch t := optype(T.Under()).(type) {
 	case *Basic:
 		// assume invalid types to be comparable
@@ -108,13 +121,13 @@ func Comparable(T Type) bool {
 		return true
 	case *Struct:
 		for _, f := range t.fields {
-			if !Comparable(f.typ) {
+			if !comparable(f.typ, seen) {
 				return false
 			}
 		}
 		return true
 	case *Array:
-		return Comparable(t.elem)
+		return comparable(t.elem, seen)
 	case *Sum:
 		return t.is(Comparable)
 	case *TypeParam: