Skip to content

types2, go/types: infinite loop typechecking (invalid) recursive generic struct #48951

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.

Sign up for GitHub

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

Jump to bottom
Closed
mdempsky opened this issue Oct 13, 2021 · 5 comments
Closed

types2, go/types: infinite loop typechecking (invalid) recursive generic struct #48951

mdempsky opened this issue Oct 13, 2021 · 5 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Milestone
Go1.18

Comments

@mdempsky
Copy link
Contributor

This package sends the type checker into an infinite loop:

package x
type A[T any] struct { x A[*T] }

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

griesemer commented Oct 13, 2021 •
edited
Loading

Thanks. Looks like it's trying to report an error but then writing out a type for the error message leads to infinite recursion. Seems related to instantiation somehow. If that's cut out, an error gets reported correctly (but perhaps too late).

@griesemer griesemer mentioned this issue Oct 14, 2021
Closed
@griesemer griesemer changed the title go/types: infinite loop typechecking (invalid) recursive generic struct types2, go/types: infinite loop typechecking (invalid) recursive generic struct 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

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/355733 mentions this issue: go/types: avoid infinite expansion for invalid recursive generic types

@jkmpariab
Copy link

I ran into similar problem.
Compiler runs indefinitely until the os crashes of lack of resources.

Here is the reproducer:

type Fooer interface {
	Foo()
}

type Fooable[F Fooer] struct {
	ptr F
}

func (f *Fooable[F]) Adapter() *Fooable[*FooerImpl[F]] {
	return &Fooable[*FooerImpl[F]]{&FooerImpl[F]{}}
}

//
// By removing the 'F Fooer' type param, program compiles sucessfully
//            |||||||||
//            vvvvvvvvv
type FooerImpl[F Fooer] struct {
}

func (fi *FooerImpl[F]) Foo() {}

gopherbot pushed a commit that referenced this issue Oct 14, 2021
@griesemer
cmd/compile/internal/types2: avoid infinite expansion for invalid rec…

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Verified
Learn about vigilant mode
ad99d88 
…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 griesemer mentioned this issue Oct 14, 2021
Closed
@griesemer
Copy link
Contributor

@jkmpariab Thanks for your report. Your issue is not fixed yet, and may or may not be related to this issue. I've opened #48974 to track it.

@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.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Projects
None yet
Milestone
Go1.18
Development

No branches or pull requests
5 participants
@mdempsky @griesemer @gopherbot @jkmpariab @findleyr