Argument with type impl FnMut combined with recursion and closures causes inifinite recursion in compiler

[AngelicosPhosphoros]

I tried this code:

pub enum ObjectOrVec {
    Object(u8),
    V(Vec<ObjectOrVec>),
}

pub fn gen(gen_random_num: fn() -> u8) -> ObjectOrVec {
    use ObjectOrVec::*;
    fn gen_recursively(
        gen_random_num: fn() -> u8,
        recurses: usize,
        mut visitor: impl FnMut(ObjectOrVec),
    ) {
        match gen_random_num() {
            1 if recurses > 0 => {
                let mut v = Vec::new();
                gen_recursively(gen_random_num, recurses - 1, |x| v.push(x));
                visitor(V(v));
            }
            n => visitor(Object(gen_random_num())),
        }
    }

    let mut v = Vec::new();
    gen_recursively(gen_random_num, 3, |x| v.push(x));
    V(v)
}

I expected to see this happen: Code compiles and generates 2 versions of function gen.

Instead, this happened: compiler errors by reaching recursion limit. Increasing recursion limit causes stack overflow.

Error message:

error: reached the recursion limit while instantiating `gen_recursively::<{closure@src/lib.rs:16:63: 16:66}>`
  --> src/lib.rs:16:17
   |
16 |                 gen_recursively(gen_random_num, recurses - 1, |x| v.push(x));
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: `gen_recursively` defined here
  --> src/lib.rs:8:5
   |
8  | /     fn gen_recursively(
9  | |         gen_random_num: fn() -> u8,
10 | |         recurses: usize,
11 | |         mut visitor: impl FnMut(ObjectOrVec),
12 | |     ) {
   | |_____^

Link to playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=571ea952b43ae93438a8f4bf9c2b0ec3

Meta

rustc --version --verbose:

rustc 1.81.0 (eeb90cda1 2024-09-04)
binary: rustc
commit-hash: eeb90cda1969383f56a2637cbd3037bdf598841c
commit-date: 2024-09-04
host: x86_64-pc-windows-msvc
release: 1.81.0
LLVM version: 18.1.7

[zirconium-n]

Minimized:

fn recurse(_: impl Fn()) {
    if false {
        recurse(|| {});
    }
}

fn main() {
    recurse(|| {});
}

Workaround:

pub enum ObjectOrVec {
    Object(u8),
    V(Vec<ObjectOrVec>),
}

fn make_f(v: &mut Vec<ObjectOrVec>) -> impl FnMut(ObjectOrVec) + '_ {
    move |x| v.push(x)
}

pub fn gen(gen_random_num: fn() -> u8) -> ObjectOrVec {
    use ObjectOrVec::*;
    fn gen_recursively(
        gen_random_num: fn() -> u8,
        recurses: usize,
        mut visitor: impl FnMut(ObjectOrVec),
    ) {
        match gen_random_num() {
            1 if recurses > 0 => {
                let mut v = Vec::new();
                gen_recursively(gen_random_num, recurses - 1, make_f(&mut v));
                visitor(V(v));
            }
            n => visitor(Object(gen_random_num())),
        }
    }

    let mut v = Vec::new();
    gen_recursively(gen_random_num, 3, |x| v.push(x));
    V(v)
}

Apparently closure inside a generic function is implemented as an associated type of the function, and it's not checking whether the closure actually used the generic parameter. The end result is that the compiler is trying to instantiate gen_recursively::<{closure}> and gen_recursively::<gen_recursively::<{closure}>::{closure}> and so on without realizing they are actually the same.

[zirconium-n]

Duplicate of #77664