(Lack of) Polymorphization can lead to an unnecessarily recursive type & make compilation fail

[danielhenrymantilla]

Main issue related to the "polymorphization" (or lack thereof) problem: #46477

---

Minimal repro:

fn foo<F : FnOnce()> (recurse: bool, f: F)
{
    if recurse {
        foo(false, || ())
    }
    f();
}

fn initial ()
{}

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

fails with:

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 Instantiate fewer copies of a closure inside a generic function #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!

  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:

  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 Instantiate fewer copies of a closure inside a generic function #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 that offers sugar for CPS, ::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...:

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, || ());
}

Less easy cases

• For the FnOnce() people, this will either require Boxing, or to use an internal helper function with a runtime-checked FnOnce-ness:

  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,

  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:

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

---

[danielhenrymantilla]

@rustbot modify labels: +T-compiler and +A-polymorphization and +A-suggestion-diagnostics and +D-terse and +C-enhancement

[chorman0773]

This is surprising, coming from C++. Dead code elimination should not affect generic instantiation or odr-use.

Reading through the code in the first example, instantiating foo::<R,F> should instantiate, foo::<R,&mut dyn FnMut()->R>, which then self-instantiates and would recurse indefinitely. This is the case even if the call is elided by dead-code elimination. Having the well-formedness of the program depend on an optimization would not be a good idea.

[sfzhu93]

This is also discussed in #43520. Specifically, for this particular example, it looks like to be only a namespace problem: #43520 (comment)