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: need to detect invalid recursive type instantiation #48098

Closed
griesemer opened this issue Aug 31, 2021 · 11 comments
Closed

types2, go/types: need to detect invalid recursive type instantiation #48098

griesemer opened this issue Aug 31, 2021 · 11 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@griesemer
Copy link
Contributor

Per the type parameters proposal:

A generic type can refer to itself in cases where a type can ordinarily refer to itself, but when it does so the type arguments must be the type parameters, listed in the same order.

The type checkers currently don't do this test. Reminder issue.

cc: @findleyr

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

findleyr commented Sep 2, 2021

Related: #45550.

@griesemer
Copy link
Contributor Author

Related: #48096.

@findleyr
Copy link
Contributor

This was just reported again in #48671, though in that case the recursion was through a method.

I don't think the same restriction should apply to methods. Consider the following:

func (*List[T]) ToInterfaceList() *List[interface{}]

Somewhat contrived, but one can imagine how something like this could be useful. Perhaps we need logic to detect infinitely expanding instantiation patterns.

@findleyr
Copy link
Contributor

I opened #48703 for infinite recursion through method signatures. It is similar to this issue but requires a different fix.

Also marking this issue as a release blocker.

@rogpeppe
Copy link
Contributor

rogpeppe commented Oct 8, 2021

Here's an example that hangs the compiler, but I can't work out if it's covered by this issue or not:

https://go2goplay.golang.org/p/3kUZ6L8amfd

func f[T any](n int) interface{} {
	if n > 0 {
		return f[*T](n - 1)
	}
	return *new(T)
}

@findleyr
Copy link
Contributor

findleyr commented Oct 8, 2021

@rogpeppe I think that's covered by #48018 and #48711: the *T pattern in your function body expands infinitely.

@mdempsky
Copy link
Member

In https://github.com/mdempsky/nomono, I've implemented a prototype of a check to detect non-monomorphizable type parameter cycles. It constructs a weighted graph representing data flow between type parameters (so really "type flow"). A zero-weight edge indicates that one type parameter is directly used to instantiate another (e.g., f[T]), whereas a positive-weight edge is used to indicate that a derived type is used (e.g., f[*T]). A package is rejected as non-monomorphisable if there are any positive cycles in the resulting graph.

I think this matches the "nomono" predicate from the Featherweight Go paper based on my intuitive understanding of their approach, but I don't fully understand the details of their algorithm so maybe I'm missing a detail. Though regardless, their algorithm doesn't need to worry about details like local types or nested generics.

I plan to write some more tests for it and optimize it, then perhaps we can consider incorporating it into go/types and types2.

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/357449 mentions this issue: go/types: add check that code is monomorphizable

gopherbot pushed a commit that referenced this issue Nov 2, 2021
This CL adds a check to ensure that generic Go code doesn't involve
any unbounded recursive instantiation, which are incompatible with an
implementation that uses static instantiation (i.e., monomorphization
or compile-time dictionary construction).

Updates #48098.

Change-Id: I9d051f0f9369ab881592a361a5d0e2a716788a6b
Reviewed-on: https://go-review.googlesource.com/c/go/+/357449
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Trust: Matthew Dempsky <mdempsky@google.com>
@gopherbot
Copy link
Contributor

Change https://golang.org/cl/360857 mentions this issue: cmd/compile/internal/types2: port nomono check from go/types

gopherbot pushed a commit that referenced this issue Nov 3, 2021
Same logic as CL 357449 (including CL 360815), just ported to types2.

Updates #48098.

Change-Id: I4578f7329bb4ffc42410025bb6cb97e24697ebfd
Reviewed-on: https://go-review.googlesource.com/c/go/+/360857
Trust: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Robert Griesemer <gri@golang.org>
@griesemer
Copy link
Contributor Author

@rogpeppe The compiler reports an error now for your example.

More generally, this general issue seems to have been addressed with the new nomono check in the type checkers. I believe @mdempsky wanted to add some more tests, so leaving this open for now but not a release blocker anymore.

@griesemer
Copy link
Contributor Author

I am going to close this as fixed at this point.

@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

5 participants