cmd/compile: report type loop for invalid recursive types

Similar to how we report initialization loops in initorder.go and type
alias loops in typecheck.go, this CL updates align.go to warn about
invalid recursive types. The code is based on the loop code from
initorder.go, with minimal changes to adapt from detecting
variable/function initialization loops to detecting type declaration
loops.

Thanks to Cuong Manh Le for investigating this, helping come up with
test cases, and exploring solutions.

Fixes #41575
Updates #41669.

Change-Id: Idb2cb8c5e1d645e62900e178fcb50af33e1700a1
Reviewed-on: https://go-review.googlesource.com/c/go/+/258177
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Trust: Matthew Dempsky <mdempsky@google.com>
Trust: Cuong Manh Le <cuong.manhle.vn@gmail.com>

4 files changed, 48 insertions, 11 deletions

diff --git a/test/fixedbugs/bug195.go b/test/fixedbugs/bug195.go
index 496c0be610..aef7bd2d89 100644
--- a/test/fixedbugs/bug195.go
+++ b/test/fixedbugs/bug195.go
@@ -6,22 +6,22 @@
 
 package main
 
-type I1 interface { I2 }	// ERROR "interface"
+type I1 interface{ I2 } // ERROR "interface"
 type I2 int
 
-type I3 interface { int }	// ERROR "interface"
+type I3 interface{ int } // ERROR "interface"
 
 type S struct {
-	x interface{ S }	// ERROR "interface"
+	x interface{ S } // ERROR "interface"
 }
-type I4 interface { // GC_ERROR "invalid recursive type"
-	I4	// GCCGO_ERROR "interface"
+type I4 interface { // GC_ERROR "invalid recursive type I4\n\tLINE: I4 refers to\n\tLINE: I4$"
+	I4 // GCCGO_ERROR "interface"
 }
 
-type I5 interface { // GC_ERROR "invalid recursive type"
-	I6	// GCCGO_ERROR "interface"
+type I5 interface { // GC_ERROR "invalid recursive type I5\n\tLINE: I5 refers to\n\tLINE+4: I6 refers to\n\tLINE: I5$"
+	I6 // GCCGO_ERROR "interface"
 }
 
 type I6 interface {
-	I5	// GCCGO_ERROR "interface"
+	I5 // GCCGO_ERROR "interface"
 }
diff --git a/test/fixedbugs/issue22904.go b/test/fixedbugs/issue22904.go
index 46cb7c048a..09f4a2118e 100644
--- a/test/fixedbugs/issue22904.go
+++ b/test/fixedbugs/issue22904.go
@@ -9,8 +9,8 @@
 
 package p
 
-type a struct{ b }
-type b struct{ a } // ERROR "invalid recursive type"
+type a struct{ b } // ERROR "invalid recursive type"
+type b struct{ a }
 
 var x interface{}
 
diff --git a/test/fixedbugs/issue23823.go b/test/fixedbugs/issue23823.go
index 2f802d0988..fe6cef1fb4 100644
--- a/test/fixedbugs/issue23823.go
+++ b/test/fixedbugs/issue23823.go
@@ -10,6 +10,7 @@ type I1 = interface {
 	I2
 }
 
-type I2 interface { // ERROR "invalid recursive type"
+// BAD: type loop should mention I1; see also #41669
+type I2 interface { // ERROR "invalid recursive type I2\n\tLINE: I2 refers to\n\tLINE: I2$"
 	I1
 }
diff --git a/test/fixedbugs/issue41575.go b/test/fixedbugs/issue41575.go
new file mode 100644
index 0000000000..d03d1c8b3e
--- /dev/null
+++ b/test/fixedbugs/issue41575.go
@@ -0,0 +1,36 @@
+// errorcheck
+
+// 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 T1 struct { // ERROR "invalid recursive type T1\n\tLINE: T1 refers to\n\tLINE+4: T2 refers to\n\tLINE: T1$"
+	f2 T2
+}
+
+type T2 struct {
+	f1 T1
+}
+
+type a b
+type b c // ERROR "invalid recursive type b\n\tLINE: b refers to\n\tLINE+1: c refers to\n\tLINE: b$"
+type c b
+
+type d e
+type e f
+type f f // ERROR "invalid recursive type f\n\tLINE: f refers to\n\tLINE: f$"
+
+type g struct { // ERROR "invalid recursive type g\n\tLINE: g refers to\n\tLINE: g$"
+	h struct {
+		g
+	}
+}
+
+type w x
+type x y // ERROR "invalid recursive type x\n\tLINE: x refers to\n\tLINE+1: y refers to\n\tLINE+2: z refers to\n\tLINE: x$"
+type y struct{ z }
+type z [10]x
+
+type w2 w // refer to the type loop again