Lifetime in Fn is so confusing and puzzling

[TechHara]

I am having hard time understanding lifetime in Fn. Consider the following:

fn foo<F, T, U>(f: F) where F: Fn(&T) -> U {}

For some helper struct, let's say we have

struct Pair {
   key: String,
   value: String,
}

Is it just me who can't seem to figure out why each line below compiles or not?

  foo(|x: &Pair| x); // 1
  foo(|x: &Pair| &x.key); // 2
  foo(|x: &&Pair| x); // 3
  foo(|x: &&Pair| *x); // 4
  foo(|x: &&Pair| &x.key); // 5

What is even more interesting is if I try to do the same but w/o foo()

    let f = |x: &Pair| x; // 6
    let f = |x: &Pair| &x.key; // 7
    let f = |x: &&Pair| x; // 8
    let f = |x: &&Pair| *x; // 9
    let f = |x: &&Pair| &x.key; // 10

Only 4 and 5 compiles while the rest don't. Here are things I don't understand

• why 1 cannot compile while 4 can? I suppose the same applies to why 2 cannot but 5 can compile.
• why 4 & 5 compile but not 9 & 10? they are exactly the same closures.
• when the return type U is of some reference, how does its lifetime relate to the input &T?

Could someone help me understand this very puzzling lifetime behavior?

[quinedot]

Let's start by being a little more explicit:

fn foo<F, T, U>(f: F)
where 
    F: for<'any> Fn(&'any T) -> U 
{}

The higher-ranked binder -- for<'any> -- means F has to accept any input lifetime.

Another important thing to know is that generic type parameters like U must resolve to a single, particular type. Additionally, types that differ by lifetime are distinct types.

So F has to take in &T with any lifetime, but for every input lifetime, has to output the same singular type U. That means the output type can't contain ("capture") the input lifetime -- because that would be a different output type per lifetime.

Hopefully that explains why 1, 2, and 3 don't compile.

4 and 5 can compile because the compiler infers a single lifetime for the inner reference (which you effectively return a copy of). It has to, because the inner &Pair corresponds to T, a generic type parameter -- which has to resolve to a single type.

---

9 and 10 don't compile because they are created outside of a context annotated with a Fn bound, where the compiler uses heuristics to try to determine the closure "signature" that aren't influenced by passing it to foo later. (The heuristics are particularly bad around higher-ranked signatures.)

[TechHara]

Thank you @quinedot so much. Your explanation is exactly what I needed. I really appreciate it!