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: infinite loop typechecking (invalid) recursive generic struct #48951

Closed
mdempsky opened this issue Oct 13, 2021 · 5 comments
Closed
Assignees
Milestone

Comments

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Oct 13, 2021

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 this to the Go1.18 milestone Oct 13, 2021
@griesemer griesemer self-assigned this Oct 13, 2021
@griesemer
Copy link
Contributor

@griesemer griesemer commented Oct 13, 2021

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

@gopherbot gopherbot commented Oct 14, 2021

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

@gopherbot
Copy link

@gopherbot gopherbot commented Oct 14, 2021

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

@jkmpariab
Copy link

@jkmpariab jkmpariab commented Oct 14, 2021

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
…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>
@gopherbot gopherbot closed this in fbdf830 Oct 14, 2021
@griesemer
Copy link
Contributor

@griesemer griesemer commented Oct 14, 2021

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants