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

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.

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

   Aylei at 2019-02-10 06:13:27

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

   Lukas Kalbertodt at 2019-02-10 11:26:59

3. Triage: no change

   Maayan Hanin at 2022-03-23 05:47:21

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

   sfzhu93 at 2022-10-04 09:09:36

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

   Crystal Durham at 2022-11-29 20:34:00

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

   sfzhu93 at 2022-11-29 22:50:08

7. For all readers who run into this not so helpful error message during cargo build of cargo check passed code: Do some Box<dyn ???> indirection to get out of it.

   rusty-snake at 2025-01-23 22:36:22