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

@danscales

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.

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.

Can someone share a reference to the paper?

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

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.

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.

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

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.

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

@mdempsky is actively working on this.

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

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

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