go/types, types2: use type nest to detect type cycles (fix validType)
validType was using a global type info map to detect invalid recursive
types, which was incorrect. Instead, change the algorithm as follows:
- Rather than using a "seen" (or typeInfo) map which is cumbersome to
update correctly, use the stack of embedding types (the type nest)
to check whether a type is embedded within itself, directly or
indirectly.
- Use Identical for type comparisons which correctly considers identity
of instantiated generic types.
- As before, maintain the full path of types leading to a cycle. But
unlike before, track the named types rather than their objects, for
a smaller slice ([]*Named rather than []Object), and convert to an
object list only when needed for error reporting.
- As an optimization, keep track of valid *Named types (Checker.valids).
This prevents pathological cases from consuming excessive computation
time.
- Add clarifying comments and document invariants.
Based on earlier insights by David Chase (see also CL 408818).
Fixes #52698.
Change-Id: I5e4598c58afcf4ab987a426c5c4b7b28bdfcf5ea
Reviewed-on: https://go-review.googlesource.com/c/go/+/409694 Reviewed-by: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Griesemer <gri@google.com> Reviewed-by: David Chase <drchase@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>