reached the recursion limit while instantiating `function_name::<[closure]>`

[glandium]

Here is a shortened version of the code I hit this with: https://play.rust-lang.org/?gist=01e76f65024cbf57bb018547932aaef2&version=stable

The error message is everything but enlightening as to what is going wrong, and from a programmer perspective, there is nothing in there that should hit a recursion limit.

@bluss had this to say on irc:

So the first call is Arguments::from with F = U1 (some unique closure type for the initial closure) which recursively calls from with F = U2 (new type for || None) which calls from with F = U3 (new type for || None) And U2 and U3 are different because they are compiled in functions with different type parameters? U2 is compiled with F=U1 and U3 is compiled with F = U2 I think we can test if that's true with this we have a closure with an anonymous type still, but that doesn't depend on any type parameter. It's Self::nop() in this code. https://play.rust-lang.org/?gist=c82188fa9cf9c592b1956f6a5b5babe4&version=nightly so yeah, rustc could be a lot smarter in this case

Note that I worked around it by just manually inlining the recursion, which is also shorter.

[aylei]

I've got the same issue here: https://play.rust-lang.org/?gist=5253e1adb845862f26029cbf0423085c (I was trying to test if a given binary tree is a validate binary search tree)

[LukasKalbertodt]

Minimal example:

fn foo<F: Fn()>(x: bool, _: F) {
    if x {
        foo(false, || {})
    }
}

fn main() {
    foo(true, || {});
}

Error:

error: reached the recursion limit while instantiating `foo::<[closure@src/main.rs:3:20: 3:25]>`
 --> src/main.rs:1:1
  |
1 | / fn foo<F: Fn()>(x: bool, _: F) {
2 | |     if x {
3 | |         foo(false, || {})
4 | |     }
5 | | }
  | |_^

The error is gone if we use a function instead of a closure:

fn dummy() {}

fn foo<F: Fn()>(x: bool, _: F) {
    if x {
        foo(false, dummy)
    }
}

[Spoonbender]

Triage: no change

[sfzhu93]

This seems to be only a naming problem here, considering the following Go code can compile:

package main

type EmptyFunc func()

type FuncInterface interface {
    EmptyFunc
}

func bar(f EmptyFunc) EmptyFunc { return f }

func foo[T FuncInterface](flag bool, fp T) {
    if flag {
        foo(false, bar(func() {}))
    }
}

func main() {
    foo(false, bar(func() {}))
}

https://gotipplay.golang.org/p/k5ngVKP0XKE

but this code cannot:

fn bar<F: Fn()>(f: F) -> F {
    f
}

fn foo<F: Fn()>(x: bool, _: F) {
    if x {
        foo(false, bar(|| {}))
    }
}

fn main() {
    foo(true, bar(|| {}));
}

Also it is related to #77664

[CAD97]

considering the following Go code can compile

Go's generics are not monomorphized. Or more specifically, they're monomorphized per "GC shape," so in Rust terms you only have one instantiation foo::<fn()> rather than the actual recursive monomorphization of foo::<[closure@main]> calling foo::<[closure@foo::<[closure@main]>]> calling foo::<[closure@foo::<[closure@foo::<[closure@main]>]>]> etc.

[sfzhu93]

I checked the Go example's objdump result: func foo[T FuncInterface](flag bool, fp T) { is represented as <main.foo[go.shape.func()_0]>:. Looks like they figure out the GC shape at an early stage, and thus make the recursive monomorphization end early.

Go's generics are not monomorphized. Or more specifically, they're monomorphized per "GC shape," so in Rust terms you only have one instantiation foo::<fn()> rather than the actual recursive monomorphization of foo::<[closure@main]> calling foo::<[closure@foo::<[closure@main]>]> calling foo::<[closure@foo::<[closure@foo::<[closure@main]>]>]> etc.

We didn't observe reuse of monomorphized methods from real-world benchmarks in our recent paper. My understanding is, GC shape is an optimization similar to the contributions from Polymorphization Working Group. But, from this example, looks like the GC shape recognition happens eariler than Rust, which could be helpful in solving cases like this.