Repository: rust
Issue: (Lack of) Polymorphization can lead to an unnecessarily recursive type & make compilation fail
Labels: C-enhancement,A-trait-system,T-compiler,A-suggestion-diagnostics,D-terse,-Zpolymorphize,C-optimization

Main issue related to the "[polymorphization](https://rust-lang.github.io/compiler-team/working-groups/polymorphization/)" (or lack thereof) problem: #46477

___

Minimal repro:

```rust
fn foo<F : FnOnce()> (recurse: bool, f: F)
{
    if recurse {
        foo(false, || ())
    }
    f();
}

fn initial ()
{}

fn main ()
{
    foo(true, initial);
}
```

[fails with](https://rust.godbolt.org/z/hYbzGW):

```text
error: reached the recursion limit while instantiating `foo::<[closure@src/main.rs:4:20: 4:25]>`
 --> src/main.rs:4:9
  |
4 |         foo(false, || ())
  |         ^^^^^^^^^^^^^^^^^
  |
```

___

The issue seems to stem from the fact that the closure created inside `foo`, `|| ()`, despite not using `f` and thus not having anything of type `F` inside, has nevertheless a type that is infected with all the generic parameters in scope. So this leads to that closure being generic over the type parameter `F`.

So, the initial call `foo::<F = fn {initial}>` causes Rust to go and monomorphize `foo` for that given `F`, which requires monomorphizing the next call to `foo()`, and because of the above, whereby the closure is infected with the `F` type parameter, it will end up monomorphizing something like `foo::<F = Closure<fn {initial}>>`. And that call, in and on itself, leads to monomorphizing the next call, `foo::<F = Closure<Closure<fn {initial}>>>`, and so on, …, _ad infinitum_, causing the type recursion limit to be reached.

Granted, we could say that this is an issue with "badly done" recursion, and so we may ask:

### Why report this

I think it is worth doing it for several reasons:

  - Mainly, because it causes a compilation error! And the error message is not very helpful 😬

      - For instance, the first time I've encountered this issue, it is definitely an obscure one, and it's taken me a while to figure out what the root cause for the compilation error was.

        Thus, having this be available may serve for future reference for other people, rather than the linked canonical issue #46477, or specific problems that some people had with iterator adaptors.

  - This is not "intended behavior" in that replacing a capture-less closure with an isomorphic **function item avoids the compilation error**!

    ```rust
    fn foo<F : FnOnce()> (recurse: bool, f: F)
    {
        if recurse {
            foo(false, { fn no_op(){}; no_op })
        }
        f();
    }

    fn main ()
    {
        foo(true, || ());
    }
    ```

  - Another odd thing is that the compilation error happens **at usage site** rather than at definition site, which I think has also been part of the confusion (I was getting `cargo check` to pass fine, and the compilation errors only happened with `cargo test` calling that function). Worse, even a call site, if it can be proven unreachable by the compiler, can trigger dead code elimination and the whole recursive-monomorphization to be skipped altogether. That is, the following code compiles fine:

    ```rust
    fn foo<F : FnOnce()> (recurse: bool, f: F)
    {
        if recurse {
            foo(false, || ())
        }
        f();
    }

    fn main ()
    {
        if false { foo(true, || ()); }
    }
    ```

  - This issue is also here to raise awareness about the semver implications of Rust supporting polymorphization: it is not only a matter of binary size and code bloat (as mentioned in #46477), it is actually a matter of compilation erroring or not. That means that if some version of the compiler were to support polymorphization and effectively make this code compile, then regressing with that polymorphization functionality would be breaking change ⚠️.

  - Finally, this is also to suggest a workaround for those stumbling upon it.

### The workaround

  - I have had to [use these workarounds to be able to support recursion within my crate](https://github.com/danielhenrymantilla/with_locals.rs/pull/6) that offers sugar for CPS, [`::with_locals`](https://docs.rs/with_locals)

Some of you may have figured it by now, given how the `fn()...` item was not infected by the type `F`.

Similarly, in the case of a stateful closure, especially one actually capturing `f`, not even polymorphization would solve the issue. The real way to solve it would be introduce type erasure, similar to `fn()`, but for closures. That is, `dyn Fn...`:

```rust
fn foo<F : FnMut()> (recurse: bool, mut f: F)
{
    if recurse {
        // monomorphization for the `&mut dyn FnMut()` is terminal / ends the recursion.
        foo::<&mut dyn FnMut()>(false, &mut || {
             println!("Recursed!");
             f();
        });
    } else {
        f();
    }
}

fn main ()
{
    foo(true, || ());
}
```

<details><summary>Less easy cases</summary>

  - For the `FnOnce()` people, this will either require `Box`ing, or to use an internal helper function with a runtime-checked `FnOnce`-ness:

    ```rust
    fn foo<F : FnOnce()> (recurse: bool, f: F)
    {
        fn helper (recurse: bool, f: &mut dyn FnMut())
        {
            if recurse { helper(false, &mut || { ... }); } else { f(); }
        }
        let mut f = Some(f);
        helper(
            recurse,
            &mut move || {
                f   .take()
                    .expect("Attempted to call a `FnOnce()` multiple times")
                    ()
            },
        );
    }
    ```

    Note that the "fallibility" of the `FnMut()` would be solved with unsized locals, and/or, equivalently, with a `RefMove<'_, T>`, `StackBox<'_, T>`, `Own<'_, T>`, `&'_ own T` owning reference type (instanced with `T = dyn FnOnce()`).

  - Finally, If the closure happens to return a value, then care should be take not to wrap the return type.

    That is,

    ```rust
    fn foo<R> (recurse: bool, f: &mut dyn FnMut() -> R) -> R
    {
        if recurse {
            foo(false, &mut || (f(), 42)).0
        } else {
            f()
        }
    }
    ```

    will also fail since we hit the same issue as before but this time with `R -> (R, i32) -> ((R, i32), i32) -> …`

    The workaround, is to (ab)use the mutability of the closure to return the value elsewhere:

    ```rust
    fn foo<R, F : FnOnce() -> R> (recurse: bool, f: F) -> R
    {
        fn helper<R> (recurse: bool, f: &mut dyn FnMut() -> R) -> R
        {
            if recurse {
                let mut out_slot = None;
                // fixed `R = ()` terminates the recursion.
                helper(false, &mut || -> () {
                    out_slot = Some((f(), 42));
                });
                out_slot.unwrap().0
            } else {
                f()
            }
        }
        let mut f = Some(f);
        helper(recurse, &mut || f.take().unwrap()())
    }

___

</details>