commit 37a2290095a78cbe0f0137d3e0d40611f9509ef3
author Robert Griesemer <gri@golang.org> Wed Sep 18 16:49:20 2019 -0700
committer Robert Griesemer <gri@golang.org> Tue Oct 08 16:59:41 2019 +0000
tree 365a309a286da75bb3c2c9fa07506405d94d2171
parent 816ff44479ae1f1e9459221f63206e93f6f12824

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>