Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
griesemer opened this issue Oct 14, 2021 · 15 comments
Closed
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@griesemer
Copy link
Contributor

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.

@griesemer griesemer added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 14, 2021
@griesemer griesemer added this to the Go1.18 milestone Oct 14, 2021
@griesemer griesemer self-assigned this Oct 14, 2021
@gopherbot
Copy link
Contributor

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

@griesemer
Copy link
Contributor Author

cc: @findleyr

gopherbot pushed a commit that referenced this issue Oct 14, 2021
…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
Copy link
Contributor Author

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
Copy link
Contributor

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

gopherbot pushed a commit that referenced this issue Nov 4, 2021
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
Copy link
Contributor

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
Copy link
Member

mdempsky commented Nov 15, 2021

@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
Copy link
Contributor Author

@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
Copy link
Contributor Author

@mdempsky see also the description on CL 355732.

@danscales
Copy link
Contributor

@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.

@danscales danscales assigned mdempsky and unassigned danscales and griesemer Dec 21, 2021
@griesemer griesemer self-assigned this Jan 6, 2022
@gopherbot
Copy link
Contributor

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
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

gopherbot pushed a commit that referenced this issue Jan 24, 2022
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>
gopherbot pushed a commit that referenced this issue Jan 24, 2022
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>
gopherbot pushed a commit that referenced this issue Jan 24, 2022
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>
gopherbot pushed a commit that referenced this issue Jan 24, 2022
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>
gopherbot pushed a commit that referenced this issue Jan 24, 2022
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>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
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>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
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>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
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>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
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>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
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>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
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>
@golang golang locked and limited conversation to collaborators Jun 23, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests

4 participants