go/types: guarantee that a finite number of distinct instances are reachable via the API

[findleyr]

In #52715, we see an example of unexpanded types escaping type-checking, that result in an infinite number of reachable types when interrogated via Underlying (though only a finite number of identical types).

It would be nice if we could avoid such infinite expansion, as it is bound to cause problems for our users (see e.g. https://go.dev/cl/404335). One way to achieve this would be to provide wrappers for Underlying and Method that accept a Context. Another option would be to enforce that unexpanded types do not escape the API, though this can result in a lot of unnecessary work when underlying types or instance methods are not needed.

CC @griesemer @adonovan @mdempsky

[mvdan]

My apologies, I meant to hit the "subscribe" button, not the "close" button!

[findleyr]

Just to add a bit more context:

Laziness serves at least three purposes:

1. To avoid type expansion before underlying types are fully set-up.
2. To avoid infinite recursion in the type checker.
3. To avoid inefficiency due to generic types that expand enormously. The way I think about this is: we want type checking to scale with the source being type-checked, not the expanded source after instantiating.

Of these:

• (1) is convenient but can lead to subtle bugs. We've seen this in the past with interface completion, and are seeing it now with type expansion (e.g. https://go.dev/issue/52529). We should probably work toward a more phased approach to type construction.
• (2) probably shouldn't be necessary anymore, with our checks for monomorphizability and infinite expansion.
• (3) is a real concern, and an argument for preserving laziness.

[dominikh]

With regard to point 3 it would be interesting to think about how many clients of the type-checker end up having to expand generic types, anyway.

Since #52715 spawned this conversation, I'm also curious how the type-checker, which itself needs to know method sets, can avoid expanding types?

[findleyr]

With regard to point 3 it would be interesting to think about how many clients of the type-checker end up having to expand generic types, anyway.

Yes, this is a good point. I would guess that in some clients (such as gopls) most types get expanded anyway.

I'm also curious how the type-checker, which itself needs to know method sets, can avoid expanding types?

The type-checker expands types whenever necessary. It just so happens that the method set is not needed in the example in question:
https://go.dev/play/p/hmJjiNWzm9G

[findleyr]

CC @timothy-king as well.

The more I think about this, the more I think it was just a mistake not to guarantee that reachable types are always finite. Because of instantiation we can't guarantee that instances are canonical, but we can guarantee that they are finite.

I think there's actually a way to achieve this lazily, without pinning the types.Context of the package. Right now during the type-checking pass we avoid type duplication during e.g. calls to Underlying by pinning a *Checker to the Named type. This allows us to use a regular API, but still share state during expansion. However, at the end of type-checking we nil-out the *Checker to avoid unnecessarily pinning memory to the created types.

It occurred to me that we can do something similar during lazy expansion, even if we don't have a *Checker available. We already create a new context during expansion. I would propose that we save that *Context to the Named type and any instances created during its expansion. We can nil it out when we detect that the *Named type is fully expanded, because it won't be necessary anymore.

In other words, we introduce a new invariant. Exactly one of the following hold for a named type N:

• N is fully expanded, meaning its underlying and all methods have been instantiated.
• N has a pinned *Checker
• N has a pinned *Context

As a result of this change, we would guarantee that any instance reachable from N shares a context with N. In the specific example of #52715, it would work as follows:

• <Tree[int]> would initially have a pinned *Checker.
• When we clean up after type-checking, we replace the *Checker with a *Context containing exactly one instance (<Tree[int]>), which we can call C. (N.B. we could probably create this context upon the first expansion, but for simplicity of the invariant let's assume that it is created now).
• When we call NewMethodSet, we access <Tree[int]>.Underlying(), which triggers an expansion and creation of Node[int]. We save C as the context of <Node[int]>. C now has two instances: <Tree[int]> and <Node[int]>.
• We then access <Node[int]>.Underlying() for the <Node[int]> instance above. Since it has C pinned, it finds (and re-uses) <Tree[int]>.

In other words, each instance is expanded in a shared *Context. During type-checking, this is shared across the package. After type-checking this is shared across a "lineage", starting with the first type that was expanded. It's still possible to have identical named types with different pointer identity, but there will be a finite set of such types. While expanding it's true that this lineage grows, but anyway its maximum size is proportional to the number of types that would be created if we were to expand eagerly. This seems like a reasonable compromize.

[griesemer]

This seems like it could work. Worth a try.

[gopherbot]

Change https://go.dev/cl/404885 mentions this issue: go/types: ensure that named types never expand infinitely

[findleyr]

This seemed to work out well in the associated stack of CLs, but of course these sorts of changes require great care. It is possible that I will land this stack on Monday (within the parameters of the freeze grace period, since the stack was mailed before the freeze), but even if I don't I think this is a sufficiently severe problem that it warrants being made a release blocker for 1.19. I am not sure if it should be back-ported to 1.18, since the fix is not small and the problem with NewMethodSet and LookupFieldOrMethod has been avoided.