Confusing diagnostic complains about lifetimes in a closure, when parameter type is missing

[mday64]

1. Create a new project with cargo new closure_lifetimes
2. cargo add pathfinding (in my case, it used pathfinding version 4.0.0 or 4.0.1)
3. Replace main.rs with:

use std::collections::HashMap;
use pathfinding::prelude::bfs;

fn main() {
    // Just enough to satisfy the compiler
    let input = Input { ending_point: (3,4), heights: HashMap::new() };

    let success = |node| input.heights[node] == 0;
    let successors = |node| {
        let node_height = input.heights[node];
        input.neighbors(node).into_iter()
            .filter(|other| input.heights[&other] >= node_height - 1)
            .collect::<Vec<Coord>>()
    };
    let answer = bfs(&input.ending_point, successors, success).unwrap().len();
    println!("answer = {answer}");
}

type Coord = (i32, i32);

struct Input {
    ending_point: Coord,
    heights: HashMap<Coord, u32>
}

impl Input {
    // Just do something to satisfy the compiler
    fn neighbors(&self, node: &Coord) -> Vec<Coord> {
        vec![(node.0, node.1 + 1), (node.0 + 1, node.1)]
    }
}

cargo check produces the following output:

    Checking closure_lifetimes v0.1.0 (/Users/mark/sources/closure_lifetimes)
error[E0308]: mismatched types
  --> src/main.rs:15:18
   |
15 |     let answer = bfs(&input.ending_point, successors, success).unwrap().len();
   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ one type is more general than the other
   |
   = note: expected trait `for<'r> FnMut<(&'r (i32, i32),)>`
              found trait `FnMut<(&(i32, i32),)>`
note: this closure does not fulfill the lifetime requirements
  --> src/main.rs:9:22
   |
9  |     let successors = |node| {
   |                      ^^^^^^
note: the lifetime requirement is introduced here
  --> /Users/mark/.cargo/registry/src/github.colasdn.workers.dev-1ecc6299db9ec823/pathfinding-4.0.1/src/directed/bfs.rs:69:9
   |
69 |     FN: FnMut(&N) -> IN,
   |         ^^^^^^^^^^^^^^^

error: implementation of `FnOnce` is not general enough
  --> src/main.rs:15:18
   |
15 |     let answer = bfs(&input.ending_point, successors, success).unwrap().len();
   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `FnOnce` is not general enough
   |
   = note: closure with signature `fn(&'2 (i32, i32)) -> Vec<(i32, i32)>` must implement `FnOnce<(&'1 (i32, i32),)>`, for any lifetime `'1`...
   = note: ...but it actually implements `FnOnce<(&'2 (i32, i32),)>`, for some specific lifetime `'2`

error[E0308]: mismatched types
  --> src/main.rs:15:18
   |
15 |     let answer = bfs(&input.ending_point, successors, success).unwrap().len();
   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ one type is more general than the other
   |
   = note: expected trait `for<'r> FnMut<(&'r (i32, i32),)>`
              found trait `FnMut<(&(i32, i32),)>`
note: this closure does not fulfill the lifetime requirements
  --> src/main.rs:8:19
   |
8  |     let success = |node| input.heights[node] == 0;
   |                   ^^^^^^
note: the lifetime requirement is introduced here
  --> /Users/mark/.cargo/registry/src/github.colasdn.workers.dev-1ecc6299db9ec823/pathfinding-4.0.1/src/directed/bfs.rs:71:9
   |
71 |     FS: FnMut(&N) -> bool,
   |         ^^^^^^^^^^^^^^^^^

error: implementation of `FnOnce` is not general enough
  --> src/main.rs:15:18
   |
15 |     let answer = bfs(&input.ending_point, successors, success).unwrap().len();
   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `FnOnce` is not general enough
   |
   = note: closure with signature `fn(&'2 (i32, i32)) -> bool` must implement `FnOnce<(&'1 (i32, i32),)>`, for any lifetime `'1`...
   = note: ...but it actually implements `FnOnce<(&'2 (i32, i32),)>`, for some specific lifetime `'2`

For more information about this error, try `rustc --explain E0308`.
error: could not compile `closure_lifetimes` due to 4 previous errors

For the two closures (success and successors), if I add a type for the parameter by changing |node| to |node: &Coord|, it builds without any errors. If it had told me that it needed type annotations, I would have understood the problem and been able to fix it right away. (I assumed that there was enough type information for it to infer the correct types.)

The first confusing bit is that both errors highlight the entire call to bfs(), including all parameters. This makes it harder to figure out which one it is complaining about (though the second note contains the line number). Does the first argument have something to do with the lifetimes it is complaining about?

I found this part of the message hard to understand:

   = note: closure with signature `fn(&'2 (i32, i32)) -> Vec<(i32, i32)>` must implement `FnOnce<(&'1 (i32, i32),)>`, for any lifetime `'1`...
   = note: ...but it actually implements `FnOnce<(&'2 (i32, i32),)>`, for some specific lifetime `'2`

The type parameters look almost identical, and the for some specific lifetime didn't make sense to me. Could it somehow indicate the bounds of that lifetime (2), or better explain why that lifetime doesn't last long enough?

FYI: found as part of solving Advent of Code 2022, Day 12.

[skyzh]

A smaller MCVE:

pub fn bfs<N, FN, IN, FS>(start: &N, successors: FN, success: FS) -> Option<Vec<N>>
where
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = N>,
    FS: FnMut(&N) -> bool,
{
    None
}

struct Test;

fn main() {
    let success = |node| true;
    let successors = |node| {
        vec![]
    };
    let answer = bfs(&Test, successors, success).unwrap().len();
    println!("answer = {answer}");
}

[skyzh]

I'm thinking whether we should fix this as a compiler bug (i.e., make it compile) or suggesting people write explicit type here 🤣

[skyzh]

maybe related: #105528

[skyzh]

Also if we move the closure to the parameter:

fn main() {
    let answer = bfs(&Test, |node| vec![],  |node| true).unwrap().len();
    println!("answer = {answer}");
}

This will also compile. Combined with #105528, I guess something is wrong with propagating lifetime of closures when we store it in a variable...

[skyzh]

@rustbot claim