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

cmd/compile: endless compilation for code that cannot be monomorphised #48018

Closed
griesemer opened this issue Aug 27, 2021 · 15 comments
Closed

cmd/compile: endless compilation for code that cannot be monomorphised #48018

griesemer opened this issue Aug 27, 2021 · 15 comments
Labels
generics NeedsInvestigation okay-after-beta1 release-blocker
Milestone

Comments

@griesemer
Copy link
Contributor

@griesemer griesemer commented Aug 27, 2021

This code corresponds to Fig. 10 in the paper "Featherweight Go" ("FGG"); it's an example of a program that cannot be monomorphised.

The type checker (types2, go/types) accept this fine, but the compiler runs "forever".

package main

type Box[A any] struct {
	value A
}

func Nest[A any](b Box[A], n int) interface{} {
	if n == 0 {
		return b
	}
	return Nest(Box[Box[A]]{b}, n-1)
}

func main() {
	Nest(Box[int]{0}, 10)
}

The FGG paper suggests a check to detect such cases. We may want to implement that eventually. For 1.18, maybe we can have some sort of "time-out" with a suitable error message for now.

cc: @randall77

@griesemer griesemer added the NeedsInvestigation label Aug 27, 2021
@griesemer griesemer added this to the Go1.18 milestone Aug 27, 2021
@griesemer griesemer self-assigned this Aug 27, 2021
@griesemer griesemer changed the title cmd/compile: cmd/compile: endless compilation for code that cannot be monomorphised Aug 27, 2021
@randall77
Copy link
Contributor

@randall77 randall77 commented Aug 27, 2021

This makes the stenciler go into an infinite loop, making deeper and deeper dictionaries:

=== Creating dictionary .dict.Nest[int]
 * int
 - Box[int]
 - func(Box[main.Box[int]], int) interface {}
 - Box[main.Box[int]]
=== Creating dictionary .dict.Nest[main.Box[int]]
 * Box[int]
 - Box[main.Box[int]]
 - func(Box[main.Box[main.Box[int]]], int) interface {}
 - Box[main.Box[main.Box[int]]]
=== Creating dictionary .dict.Nest[main.Box[main.Box[int]]]
 * Box[main.Box[int]]
 - Box[main.Box[main.Box[int]]]
 - func(Box[main.Box[main.Box[main.Box[int]]]], int) interface {}
 - Box[main.Box[main.Box[main.Box[int]]]]
=== Creating dictionary .dict.Nest[main.Box[main.Box[main.Box[int]]]]
 * Box[main.Box[main.Box[int]]]
 - Box[main.Box[main.Box[main.Box[int]]]]
 - func(Box[main.Box[main.Box[main.Box[main.Box[int]]]]], int) interface {}
 - Box[main.Box[main.Box[main.Box[main.Box[int]]]]]
=== Creating dictionary .dict.Nest[main.Box[main.Box[main.Box[main.Box[int]]]]]
 * Box[main.Box[main.Box[main.Box[int]]]]
 - Box[main.Box[main.Box[main.Box[main.Box[int]]]]]
 - func(Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]], int) interface {}
 - Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]
=== Creating dictionary .dict.Nest[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]
 * Box[main.Box[main.Box[main.Box[main.Box[int]]]]]
 - Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]
 - func(Box[main.Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]], int) interface {}
 - Box[main.Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]]
=== Creating dictionary .dict.Nest[main.Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]]
 * Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]
 - Box[main.Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]]
 - func(Box[main.Box[main.Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]]], int) interface {}
 - Box[main.Box[main.Box[main.Box[main.Box[main.Box[main.Box[main.Box[int]]]]]]]]

@randall77
Copy link
Contributor

@randall77 randall77 commented Aug 27, 2021

@danscales

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Aug 27, 2021

Is it reasonable for go/types / types2 to implement the "nomono" check from the paper? If monomorphisation is supposed to be an acceptable implementation strategy for generic Go, then it seems like the type checker should enforce that for consistency across implementations.

@griesemer
Copy link
Contributor Author

@griesemer griesemer commented Aug 27, 2021

I'd have to study the nomono check again, but I'd say yes, the type checker should decide. There's also the issue of then having to explain that in the spec somehow, which may be the harder part.

For 1.18 it may be good enough to have an upper limit for stenciling, to avoid endless compilations/stack overflow.

@scott-cotton
Copy link

@scott-cotton scott-cotton commented Aug 28, 2021

Can someone share a reference to the paper?

@griesemer
Copy link
Contributor Author

@griesemer griesemer commented Aug 28, 2021

See link in first comment. Or search for "featherweight go" using your favorite search engine.

@danscales
Copy link
Contributor

@danscales danscales commented Aug 29, 2021

This example also doesn't work with our current method of implementing dictionaries (as can be seen by the failure). That is because we don't create dictionaries on the fly, but require that all needed dictionaries can be computed at compile time. If we compute some/all dictionaries at run-time (maybe using proto-dictionary templates, like one of Keith's original ideas), then I think we could support this case. But, of course, it's not really worth it, especially if we want to allow implementations to do stenciling (monomorphisation) only.

@griesemer
Copy link
Contributor Author

@griesemer griesemer commented Aug 29, 2021

I am not suggesting that we make this work (certainly not in the near term). Ideally, the type checker detects this case, but in the interest of expediency (we don't need to support everything for 1.18 - there's more urgent issues at the moment) it's probably much easier to just have an upper limit for dictionary depth/size and bail out with an error message if the bound is exceeded. We may be able to point at the offending piece of code as well.

The primary goal is to avoid an endless compilation that leaves a user in the dark about what's going on.

@danscales
Copy link
Contributor

@danscales danscales commented Aug 29, 2021

Yes, absolutely, we can implement the depth limit in the dictionary code for 1.18. I was just pointing out that this could work with some dictionary implementation (but not ours as it stands), but definitely not worth it at all for now (or maybe ever).

@findleyr
Copy link
Contributor

@findleyr findleyr commented Oct 1, 2021

Should this be a release-blocker? I wasn't sure about whether to apply that label for #48711, but it does seem like this could occur in real programs and the user experience is not great.

@toothrot
Copy link
Contributor

@toothrot toothrot commented Oct 13, 2021

Is this still a release-blocker? Friendly ping that this is a release-blocking issue for Go 1.18.

@toothrot toothrot added generics okay-after-beta1 labels Oct 13, 2021
@griesemer
Copy link
Contributor Author

@griesemer griesemer commented Oct 13, 2021

@mdempsky is actively working on this.

@gopherbot
Copy link

@gopherbot gopherbot commented Nov 3, 2021

Change https://golang.org/cl/361262 mentions this issue: cmd/compile: add extra test for the non-mono pass

@danscales
Copy link
Contributor

@danscales danscales commented Nov 4, 2021

@mdempsky fixed this with his new no-mono pass: https://go-review.googlesource.com/c/go/+/360857

gopherbot pushed a commit that referenced this issue Nov 4, 2021
Just add a test for another function that is not monomorphisable, which
comes from the Featherweight Go paper.

Updates #48018

Change-Id: I664e3f48412b02678e32b50204dc4befae90374c
Reviewed-on: https://go-review.googlesource.com/c/go/+/361262
Trust: Dan Scales <danscales@google.com>
Run-TryBot: Dan Scales <danscales@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
@fweimer-rh
Copy link

@fweimer-rh fweimer-rh commented Nov 8, 2021

I am not suggesting that we make this work (certainly not in the near term). Ideally, the type checker detects this case, but in the interest of expediency (we don't need to support everything for 1.18 - there's more urgent issues at the moment) it's probably much easier to just have an upper limit for dictionary depth/size and bail out with an error message if the bound is exceeded.

A depth limit may be prudent to add anyway. There is probably not much difference between a very large type and an infinite type from a user point of view. Maybe it's easier to create an infinite type by accident.

For example, this program requires more than 60G of memory to compile (as of 9e6ad46), and its types are finite.

package main

type Q[T1 any, T2 any, T3 any, T4 any] struct {
	t1 T1
	t2 T2
	t3 T3
	t4 T4
}

func F[T any](x T) Q[*[1]T, *[2]T, *[3]T, *[4]T] {
	return Q[*[1]T, *[2]T, *[3]T, *[4]T]{
		&[1]T{x}, &[2]T{x,x}, &[3]T{x,x,x}, &[4]T{x,x,x,x}}
}

func main() {
	F(F(F(F(F(F(F(F(F(F(F(F(F(F(1))))))))))))))
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
generics NeedsInvestigation okay-after-beta1 release-blocker
Projects
None yet
Development

No branches or pull requests

9 participants