go/types: fix cycle detection

For Go 1.13, we rewrote the go/types cycle detection scheme. Unfortunately,
it was a bit too clever and introduced a bug (#34333). Here's an example:

type A struct {
	f1 *B
	f2 B
}

type B A

When type-checking this code, the first cycle A->*B->B->A (via field f1)
is ok because there's a pointer indirection. Though in the process B is
considered "type-checked" (and painted/marked from "grey" to black").
When type-checking f2, since B is already completely set up, go/types
doesn't complain about the invalid cycle A->B->A (via field f2) anymore.
On the other hand, with the fields f1, f2 swapped:

type A struct {
	f2 B
	f1 *B
}

go/types reports an error because the cycle A->B->A is type-checked first.
In general, we cannot know the "right" order in which types need to be
type-checked.

This CL fixes the issue as follows:

1) The global object path cycle detection does not take (pointer, function,
   reference type) indirections into account anymore for cycle detection.
   That mechanism was incorrect to start with and the primary cause for this
   issue. As a consequence we don't need Checker.indirectType and indir anymore.

2) After processing type declarations, Checker.validType is called to
   verify that a type doesn't expand indefinitively. This corresponds
   essentially to cmd/compile's dowidth computation (without size computation).

3) Cycles involving only defined types (e.g.: type (A B; B C; C A))
   require separate attention as those must now be detected when resolving
   "forward chains" of type declarations. Checker.underlying was changed
   to detect these cycles.

All three cycle detection mechanism use an object path ([]Object) to
report cycles. The cycle error reporting mechanism is now factored out
into Checker.cycleError and used by all three mechanisms. It also makes
an attempt to report the cycle starting with the "first" (earliest in the
source) object.

Fixes #34333.

Change-Id: I2c6446445e47344cc2cd034d3c74b1c345b8c1e6
Reviewed-on: https://go-review.googlesource.com/c/go/+/196338
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

1 files changed, 3 insertions, 6 deletions

diff --git a/src/go/types/expr.go b/src/go/types/expr.go
index 0edd2789fb..d49ccdf67e 100644
--- a/src/go/types/expr.go
+++ b/src/go/types/expr.go
@@ -1157,12 +1157,9 @@ func (check *Checker) exprInternal(x *operand, e ast.Expr, hint Type) exprKind {
 			}
 
 		case *Array:
-			// Prevent crash if the array referred to is not yet set up.
-			// This is a stop-gap solution; a better approach would use the mechanism of
-			// Checker.ident (typexpr.go) using a path of types. But that would require
-			// passing the path everywhere (all expression-checking methods, not just
-			// type expression checking), and we're not set up for that (quite possibly
-			// an indication that cycle detection needs to be rethought). Was issue #18643.
+			// Prevent crash if the array referred to is not yet set up. Was issue #18643.
+			// This is a stop-gap solution. Should use Checker.objPath to report entire
+			// path starting with earliest declaration in the source. TODO(gri) fix this.
 			if utyp.elem == nil {
 				check.error(e.Pos(), "illegal cycle in type declaration")
 				goto Error