Recursive call passes `cargo check` but fails with `cargo build`

[ryym]

Hi Rust team,
Thank you so much for the great language.

Problem

Today I encountered a strange behavior of Cargo, 2018 edition.
This code passes cargo check, but it fails with cargo build.

fn repeat(n: i64, f: impl Fn()) {
    if n > 0 {
        f();
        repeat(n - 1, &f);
    }
}

fn main() {
    repeat(3, || {});
}

cargo check output:

Finished dev [unoptimized + debuginfo] target(s) in 0.16s

cargo build --verbose output:

(collapsed)

   Compiling rust-err v0.1.0 (/Users/ryu/work/rust-err)
     Running `rustc --edition=2018 --crate-name rust_err src/main.rs --color never --crate-type bin --emit=dep-info,link -C debuginfo=2 -C metadata=330d5c8df6305891 -C extra-filename=-330d5c8df6305891 --out-dir /Users/ryu/work/rust-err/target/debug/deps -C incremental=/Users/ryu/work/rust-err/target/debug/incremental -L dependency=/Users/ryu/work/rust-err/target/debug/deps`
error[E0275]: overflow evaluating the requirement `[closure@src/main.rs:9:15: 9:20]: std::ops::Fn<()>`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`
  = note: required because of the requirements on the impl of `std::ops::Fn<()>` for `&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[closure@src/main.rs:9:15: 9:20]`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0275`.
error: Could not compile `rust-err`.

Caused by:
  process didn't exit successfully: `rustc --edition=2018 --crate-name rust_err src/main.rs --color never --crate-type bin --emit=dep-info,link -C debuginfo=2 -C metadata=330d5c8df6305891 -C extra-filename=-330d5c8df6305891 --out-dir /Users/ryu/work/rust-err/target/debug/deps -C incremental=/Users/ryu/work/rust-err/target/debug/incremental -L dependency=/Users/ryu/work/rust-err/target/debug/deps` (exit code: 1)

It seems that there is a recursive trait requirement, but I have no idea why this simple code causes it.

Meta

rustc --version --verbose:

rustc 1.31.0 (abe02cefd 2018-12-04)
binary: rustc
commit-hash: abe02cefd6cd1916df62ad7dc80161bea50b72e8
commit-date: 2018-12-04
host: x86_64-apple-darwin
release: 1.31.0
LLVM version: 8.0

[estebank]

The following code will do what you expect it to do:

fn repeat(n: i64, f: impl Fn()) {
    if n > 0 {
        f();
        repeat(n - 1, f);
    }
}

fn main() {
    repeat(3, || {});
}

The compiler is trying to create a new version of repeat for every possible input, and it's detecting on each recursive cycle that f is passed as &f, which makes the compiler first try to create a repeat(n: i64, || {}), then a repeat(n: i64, &(|| {})), then a repeat(n: i64, &&(|| {})) and so on. This is possibly a type checker error that should be fixed, where &&[closure XX] gets eagerly decomposed to &[closure XX].

[ryym]

@estebank Thank you, I got it. May I ask you another question?

In my actual code, I do recursive call inside of a for loop.

example:

fn repeat(n: i64, f: impl Fn()) {
    if n > 0 {
        f();
        for _ in 0..n {
            repeat(n - 1, f);
        }
    }
}

fn main() {
    repeat(3, || {});
}

But this causes the following error:

error[E0382]: use of moved value: `f`
 --> src/main.rs:5:27
  |
5 |             repeat(n - 1, f);
  |                           ^ value moved here, in previous iteration of loop
  |
  = note: move occurs because `f` has type `F`, which does not implement the `Copy` trait

error: aborting due to previous error

This is why I used a reference instead of passing a function as value.

I also tried to wrap it by a new function each time, but it causes a similar error:

for _ in 0..n {
    repeat(n - 1, || f());
}

error: reached the type-length limit while instantiating `repeat::<[closure@src/main.rs:6:27: 6:33 f:&[closure@src/main.rs...`                                                                           
 --> src/main.rs:1:1
  |
1 | / fn repeat(n: i64, f: impl Fn()) {
2 | |     if n > 0 {
3 | |         f();
4 | |         for _ in 0..n {
... |
8 | |     }
9 | | }
  | |_^
  |
  = note: consider adding a `#![type_length_limit="2097152"]` attribute to your crate

Is there a way to compile this code?

[estebank]

You have to tell the compiler that you want f to be a borrow of an Fn(), that way you will be able to use it multiple times:

fn repeat(n: i64, f: &impl Fn()) {
    if n > 0 {
        f();
        for _ in 0..n {
            repeat(n - 1, f); // `f` is of type &impl Fn()
        }
    }
}

fn main() {
    repeat(3, &|| {println!("hi")});
}

If you don't, the compiler wants to take ownership of f, which will be of type impl Fn(), which will not be able to be borrowed multiple times (think of the difference between String and &str).

You could argue that impl Fn() should imply &impl Fn(), so your original code would work, but that might need an RFC.

[ryym]

@estebank That makes sense. Thanks, it works!
It may be better if impl Fn() could imply &impl Fn(), but your solution is fine with me. Thank you for your help.

[WaffleLapkin]

Note that you can actually use just impl Fn() + Copy (or impl FnOnce() + Copy):

fn repeat(n: i64, f: impl FnOnce() + Copy) {
    if n > 0 {
        f();
        for _ in 0..n {
            repeat(n - 1, f);
        }
    }
}

fn main() {
    repeat(3, || {println!("hi")}); // works
    repeat(3, &|| {println!("hi")}); // also works
}

(playground)

By the way, the A-specialization doesn't seem to relate to this issue & this issue probably lacks A-diagnostics label