cmd/compile: apparent infinite expansion of recursive function

[findleyr]

The following program type-checks, but appears to grow unbounded during compilation:

package main

func f[T interface{~[]P}, P any](t T) {
	if t == nil {
		return
	}
	f[[]T,T]([]T{t})
}

func main() {
	f[[]int](nil)
}

This is not surprising: the program was constructed to require an infinitely growing number of function instances. See also #48098 and #48703: infinitely expanding instances are generally problematic.

Not sure where it is best to handle this. It seems like something that could be detected by the type-checker, but there can be an arbitrary number of functions involved in this infinite expansion. Maybe it would be easier for the compiler to enforce a limit on recursive instantiation.

CC @griesemer @danscales @randall77 @timothy-king

[danscales]

This is pretty similar to #48018 , which I am planning to fix by having a limit on the depth or number of instantiations for the same function/method. This case should be handled by the same fix that I add for #48018.

(Both this case and #48018 could possibly be handled if we computed some/all dictionaries and type descriptors at run time, but we compute all dictionaries at compile time and don't want to change that.)

[findleyr]

Thanks, please feel free to close this as a dupe of #48018 if that would be helpful, I missed that in my search for dupes. They might be slightly different but I agree that the fix should probably be the same.

Interestingly I see that @griesemer and I both suggested that the type checker could/should detect this, but I think that might be overly optimistic. Detecting this would require a lot more machinery than we currently have.

This came up because @timothy-king and I were talking about recursive instantiation. go/ssa will need a similar limit.

[toothrot]

Friendly ping that this is a release-blocking issue for Go 1.18.

[griesemer]

CL addressing this is in progress.
cc: @mdempsky

[gopherbot]

Change https://golang.org/cl/362394 mentions this issue: test: add regress test for reported non-monomorphizable example