types2, go/types: missing errors for invalid parameterized type declarations #48962

griesemer · 2021-10-14T03:57:43Z

This is a new version of frozen #39938. The following code

package p

type T0[P any] struct {
        f P
}

type T1 struct { // <<< should get a cycle error here
        _ T0[T1]
}

is invalid because T1 would expand indefinitely. The previous fix (https://golang.org/cl/240519) could lead to infinite sequences of instantiations (see #48951).

Correct solution of this problem requires some form of type flow analysis and is related to (and may be addressed with) #48098.

The text was updated successfully, but these errors were encountered:

gopherbot · 2021-10-14T04:24:01Z

Change https://golang.org/cl/355732 mentions this issue: cmd/compile/internal/types2: avoid infinite expansion for invalid recursive generic types

griesemer · 2021-10-14T04:25:41Z

cc: @findleyr

@findleyr

…ursive generic types The algorithm for detecting invalid recursive types that expand indefinitely suffered from the exact problem is was intended to detect: if the indefinite expansion is happening through type parameters, the algorithm ended up in an infinite sequence of instantiations. (This is only a problem for generic types). Changed the algorithm to always only consider the "original" uninstantiated types. This avoids the problem but it will also not detect some invalid recursive generic types anymore. That requires a more sophisticated type flow analysis. Opened #48962 to track. Addressed with help from @findleyr. For #48951. Change-Id: Ie29cea8f810dae55153dbb1b17c9390cd823c2d9 Reviewed-on: https://go-review.googlesource.com/c/go/+/355732 Trust: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com>

griesemer · 2021-11-04T16:47:11Z

The above program currently crashes the compiler with a simple nil pointer panic. @danscales is there an easy way to address this?

More generally, could cases like these be detected in the type checker through some variation of the nomono checker? cc: @mdempsky

gopherbot · 2021-11-04T19:08:32Z

Change https://golang.org/cl/361398 mentions this issue: cmd/compile: fix TypeDefn to deal with node with no Ntype set

Adjust TypeDefn(), which is used by reportTypeLoop(), to work for nodes with no Ntype set (which are all nodes in -G=3 mode). Normally, reportTypeLoop() would not be called, because the types2 typechecker would have already caught it. This is a possible way to report an unusual type loop involving type params, which is not being caught by the types2 type checker. Updates #48962 Change-Id: I55edee46026eece2e8647c5b5b4d8dfb39eeb5f8 Reviewed-on: https://go-review.googlesource.com/c/go/+/361398 Trust: Dan Scales <danscales@google.com> Reviewed-by: Matthew Dempsky <mdempsky@google.com> Reviewed-by: Robert Griesemer <gri@golang.org>

danscales · 2021-11-04T20:25:41Z

OK, the compiler will no longer crash, and will report a type loop, though the position information is off. So no longer a release blocker. We will either fix things to make the position info more accurate, or Matthew may be able to update the nomono pass to catch this case earlier.

mdempsky · 2021-11-15T21:37:15Z

@griesemer @findleyr Looking into this now. Happy to extend the nomono check to handle this, but I'm wondering why this isn't caught by whatever logic is already responsible for rejecting type T struct{ _ T }?

griesemer · 2021-11-17T02:17:19Z

@mdempsky The logic (Checker.validType) that detects type T struct{ _ T } can (and used to) detect cases like this, but for this to work it will need to instantiate the types fully. This will lead to an infinite sequence of instantiations. I'm not sure there's an easy extension of the validType function to handle this case and avoid the infinite recursion.

griesemer · 2021-11-17T02:18:27Z

@mdempsky see also the description on CL 355732.

danscales · 2021-12-21T21:31:25Z

@mdempsky Assigning this issue to you, so you can comment as to whether you think it is feasible to change nomono to catch this recursive type in the beta time-frame (i.e. in the next couple weeks). You can assign it back to me, if you don't think it makes sense or is feasible to do for Go 1.18.

gopherbot · 2022-01-15T01:46:39Z

Change https://golang.org/cl/378176 mentions this issue: cmd/compile/internal/types2: use a map instead of a field for marking in validType

gopherbot · 2022-01-15T01:46:40Z

Change https://golang.org/cl/378675 mentions this issue: cmd/compile/internal/types2: remove special case for external types in validType

gopherbot · 2022-01-19T06:42:52Z

Change https://golang.org/cl/379414 mentions this issue: cmd/compile/internal/types2: consider type parameters for cycle detection

gopherbot · 2022-01-19T06:42:53Z

Change https://golang.org/cl/379434 mentions this issue: cmd/compile/internal/types2: validType argument must be *Named type

gopherbot · 2022-01-19T16:40:37Z

Change https://golang.org/cl/378674 mentions this issue: go/types, types2: move validType code into its own file

gopherbot · 2022-01-20T02:18:22Z

Change https://golang.org/cl/379694 mentions this issue: go/types, types2: in SetUnderlying, set Named.fromRHS if not set yet

The validType check is independent of the work of declaring objects. Move it into a separate file for better separation of concerns and code organization. No other changes - this is purely a code move. Preparation for fixing issue #48962. Change-Id: Ib08db2d009c4890882d0978b278e965ca3078851 Reviewed-on: https://go-review.googlesource.com/c/go/+/378674 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

With this change validType doesn't modify global state anymore. It also eliminates the need for an extra field in each object. Preparation for fixing issue #48962. Change-Id: If241ec77ff48911d5b43d89adabfb8ef54452c6b Reviewed-on: https://go-review.googlesource.com/c/go/+/378176 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

Now that we have a separate top-level entry point for validType we can use the more narrow type *Named (instead of Type) for its argument. Preparation for fixing issue #48962. Change-Id: I93aee4abc87036c6a68323dc970efe8e617a9103 Reviewed-on: https://go-review.googlesource.com/c/go/+/379434 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

Because validType doesn't modify global state anymore, there's no need to ignore imported types. When we start tracking type parameters, we need to include imported types because they may contribute to cycles that invalidate a type. This CL effectively reverts CL 202483 (issue #35049, which doesn't apply anymore because we don't change the state of imported objects). Preparation for fixing issue #48962. For #35049. For #48962. Change-Id: I06f15575ad197375c74ffd09c222250610186b15 Reviewed-on: https://go-review.googlesource.com/c/go/+/378675 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

This is necessary for cycle detection over imported types whose underlying types are set by importers with SetUnderlying. Preparation for fixing issue #48962. Change-Id: I3218cda7feb06440fdb8345c94bcaa5f7d64e94e Reviewed-on: https://go-review.googlesource.com/c/go/+/379694 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

The validType check is independent of the work of declaring objects. Move it into a separate file for better separation of concerns and code organization. No other changes - this is purely a code move. Preparation for fixing issue golang#48962. Change-Id: Ib08db2d009c4890882d0978b278e965ca3078851 Reviewed-on: https://go-review.googlesource.com/c/go/+/378674 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

With this change validType doesn't modify global state anymore. It also eliminates the need for an extra field in each object. Preparation for fixing issue golang#48962. Change-Id: If241ec77ff48911d5b43d89adabfb8ef54452c6b Reviewed-on: https://go-review.googlesource.com/c/go/+/378176 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

Now that we have a separate top-level entry point for validType we can use the more narrow type *Named (instead of Type) for its argument. Preparation for fixing issue golang#48962. Change-Id: I93aee4abc87036c6a68323dc970efe8e617a9103 Reviewed-on: https://go-review.googlesource.com/c/go/+/379434 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

Because validType doesn't modify global state anymore, there's no need to ignore imported types. When we start tracking type parameters, we need to include imported types because they may contribute to cycles that invalidate a type. This CL effectively reverts CL 202483 (issue golang#35049, which doesn't apply anymore because we don't change the state of imported objects). Preparation for fixing issue golang#48962. For golang#35049. For golang#48962. Change-Id: I06f15575ad197375c74ffd09c222250610186b15 Reviewed-on: https://go-review.googlesource.com/c/go/+/378675 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

This is necessary for cycle detection over imported types whose underlying types are set by importers with SetUnderlying. Preparation for fixing issue golang#48962. Change-Id: I3218cda7feb06440fdb8345c94bcaa5f7d64e94e Reviewed-on: https://go-review.googlesource.com/c/go/+/379694 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

In validType, when we see an instantiated type, proceed as with non-generic types but provide an environment in which to look up the values (the corresponding type arguments) of type parameters of the instantiated type. For each type parameter for which there is a type argument, proceed with validating that type argument. This corresponds to applying validType to the instantiated type without actually instantiating the type (and running into infinite instantiations in case of invalid recursive types). Also, when creating a type instance, use the correct source position for the instance (the start of the qualified identifier if we have an imported type). Fixes golang#48962. Change-Id: I196c78bf066e4a56284d53368b2eb71bd8d8a780 Reviewed-on: https://go-review.googlesource.com/c/go/+/379414 Trust: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Findley <rfindley@google.com>

griesemer added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 14, 2021

griesemer added this to the Go1.18 milestone Oct 14, 2021

griesemer self-assigned this Oct 14, 2021

griesemer added the release-blocker label Nov 4, 2021

griesemer assigned danscales Nov 4, 2021

danscales removed the release-blocker label Nov 4, 2021

danscales assigned mdempsky and unassigned danscales and griesemer Dec 21, 2021

griesemer self-assigned this Jan 6, 2022

griesemer unassigned mdempsky Jan 19, 2022

danscales mentioned this issue Jan 24, 2022

cmd/compile: infinite recursion in types2 #50782

Closed

gopherbot closed this as completed in 2abfa30 Jan 24, 2022

rsc unassigned griesemer Jun 23, 2022

golang locked and limited conversation to collaborators Jun 23, 2023

gopherbot added the FrozenDueToAge label Jun 23, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

types2, go/types: missing errors for invalid parameterized type declarations #48962

types2, go/types: missing errors for invalid parameterized type declarations #48962

griesemer commented Oct 14, 2021

gopherbot commented Oct 14, 2021

griesemer commented Oct 14, 2021

griesemer commented Nov 4, 2021

gopherbot commented Nov 4, 2021

danscales commented Nov 4, 2021

mdempsky commented Nov 15, 2021 •

edited

griesemer commented Nov 17, 2021

griesemer commented Nov 17, 2021

danscales commented Dec 21, 2021

gopherbot commented Jan 15, 2022

gopherbot commented Jan 15, 2022

gopherbot commented Jan 19, 2022

gopherbot commented Jan 19, 2022

gopherbot commented Jan 19, 2022

gopherbot commented Jan 20, 2022

types2, go/types: missing errors for invalid parameterized type declarations #48962

types2, go/types: missing errors for invalid parameterized type declarations #48962

Comments

griesemer commented Oct 14, 2021

gopherbot commented Oct 14, 2021

griesemer commented Oct 14, 2021

griesemer commented Nov 4, 2021

gopherbot commented Nov 4, 2021

danscales commented Nov 4, 2021

mdempsky commented Nov 15, 2021 • edited

griesemer commented Nov 17, 2021

griesemer commented Nov 17, 2021

danscales commented Dec 21, 2021

gopherbot commented Jan 15, 2022

gopherbot commented Jan 15, 2022

gopherbot commented Jan 19, 2022

gopherbot commented Jan 19, 2022

gopherbot commented Jan 19, 2022

gopherbot commented Jan 20, 2022

mdempsky commented Nov 15, 2021 •

edited