Annotating closure parameter foces use of Higher-Rank Trait Bounds

Question

In this naive snippet (playground), using the unannotated version of the closure does not compile, while annotating with the type does:

fn bounded(items: &[&u8]) -> bool {
    items.iter().all(|item| **item <= 10)
}

fn check(check_function: &dyn Fn(&[&u8]) -> bool, items: &[&u8]) -> bool {
    check_function(items)
}

fn main() {
    let a = [1, 45, 7, 2];
    let b = [&a[2], &a[0], &a[0]];
    
    let func = |items| bounded(items); // E0308
    // let func = |items: &[&u8]| bounded(items);
    
    println!("{:?}", check(&func, &b));
}

   Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/main.rs:28:35
   |
28 |     println!("{:?}", Checker::new(&func).check(&b));
   |                                   ^^^^^ one type is more general than the other
   |
   = note: expected trait `for<'a, 'b> Fn<(&'a [&'b u8],)>`
              found trait `Fn<(&[&u8],)>`
note: this closure does not fulfill the lifetime requirements
  --> src/main.rs:25:16
   |
25 |     let func = |items| bounded(items);
   |                ^^^^^^^

error: implementation of `FnOnce` is not general enough
  --> src/main.rs:28:35
   |
28 |     println!("{:?}", Checker::new(&func).check(&b));
   |                                   ^^^^^ implementation of `FnOnce` is not general enough
   |
   = note: closure with signature `fn(&'2 [&u8]) -> bool` must implement `FnOnce<(&'1 [&u8],)>`, for any lifetime `'1`...
   = note: ...but it actually implements `FnOnce<(&'2 [&u8],)>`, for some specific lifetime `'2`

error: implementation of `FnOnce` is not general enough
  --> src/main.rs:28:35
   |
28 |     println!("{:?}", Checker::new(&func).check(&b));
   |                                   ^^^^^ implementation of `FnOnce` is not general enough
   |
   = note: closure with signature `fn(&[&'2 u8]) -> bool` must implement `FnOnce<(&[&'1 u8],)>`, for any lifetime `'1`...
   = note: ...but it actually implements `FnOnce<(&[&'2 u8],)>`, for some specific lifetime `'2`

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` (bin "playground") due to 3 previous errors

I am now aware that I could use fn to store a function pointer directly (playground), but want to investigate the error caused from using closures.

fn check(check_function: fn(&[&u8]) -> bool, items: &[&u8]) -> bool {
    check_function(items)
}

This question also deals with the explicit annotation of the closure compiling, but is about the borrow checker, whereas I do not borrow twice in my code.

---

I have read the Rustonomicon's lifetime chapters, as well as the Book's lifetime chapters. I roughly understand the mechanics, but need help with the conceptual reasoning for lifetime elision, and specific/general lifetimes.

1. Why isn't &'c [&'c u8] sufficient for &'a [&'b u8]?

The latter is from lifetime elision, but it seems to me like if 'a is invalidated, 'b is also invalidated, so any function receiving the former (which gets the shortest lifetime of the two) should also work.

I don't think this is a over-conservative check, since the Rustonomicon mentions that references can be re-initialized. Here is my attempt explaining why (playground):

fn print(vec: &[&u8]) {
    println!("{vec:?}")
}

fn main() {
    let x = [1, 2, 3, 4];
    let mut y = vec![&x[1], &x[2], &x[3]];
    print(&y); // &y is &'b [&'a u8, &'a u8, &'a u8]
    y.insert(0, &x[0]); // lifetime of 'b is invalidated and 'c is initialized
    print(&y); // &y is &'d [&'c u8, &'a u8, &'a u8, &'a u8]
}

Although this does re-initialize the reference, it seems like I could still run both print functions by binding the all references from &y to the shorter lifetime('b and 'd respectively).

2. What are the lifetimes of the value captured by the closure?

Using rust-analyzer, it correctly deduces that the type of items is &[&u8]. Looking at the errors, this is also the type captured:

found trait Fn<(&[&u8],)>

But referring to HRTB and this explanation, it seems like Fn should be desugared to some for<...> Fn(...), this isn't done to func here.

The other errors also hint at the closure being implemented for some specific lifetime (the lifetime of main()?). Is this the reason why no explicit lifetime marker is given?

Related: Lifetime elision/annotation cannot be applied to closures.

3. Why does annotating the closure with &[&u8] work?

This one I don't have many clues about. I'm guessing that this allows the compiler to explicitly bind the captured value to a HRTB, and that allows the closure to be general enough.

Answer 1

Answer

---

I believe that isaactfa is correct in that the compiler is inferring the wrong type without the annotation, and when you annotate it, the compiler is able to infer a more correct type.

It is also possible to get it to infer the correct types by adding lifetimes to check instead of adding an annotation to the closure as seen here. Adding these annotations helps the compiler to realize that your arguments live long enough to be used by the the closure, and to figure out the closure's lifetime.

fn check<'b1, 'b2, 'a1: 'b1, 'a2: 'b2>(check_function: &dyn Fn(&'b1 [&'b2 u8]) -> bool, items: &'a1 [&'a2 u8]) -> bool {
    check_function(items)
}

Correction

---

There is however some information that isn't correct in your post that I do want to correct real quick:

fn main() {
    let x = [1, 2, 3, 4];
    let mut y = vec![&x[1], &x[2], &x[3]];
    print(&y); // &y is &'b [&'a u8, &'a u8, &'a u8]
    y.insert(0, &x[0]); // lifetime of 'b is invalidated and 'c is initialized
    print(&y); // &y is &'d [&'c u8, &'a u8, &'a u8, &'a u8]
}

In this snippet, you write that the lifetime of &y is of type &'d [&'c u8, &'a u8, &'a u8, &'a u8], however this isn't accurate. It is still of the type &'d [&'a u8]. Pushing the value &x[0] does not introduce a new lifetime, because you are referencing x, just like you did when you initialized y. You can verify this by putting the insert line into another block. In order for it to compile, the lifetime 'c has to be as long (or longer) than the lifetime 'a, because y is used later. Running this on the playground shows that the borrow is not related to the & itself, but to the lifetime of the object that is being borrowed from.

let x = [1, 2, 3, 4];
let mut y = vec![&x[1], &x[2], &x[3]];
println!("{:?}", &y);
{
    // If the lifetime was related to this `&` and not `x`,
    // then this wouldn't be able to compile because
    // the `&` is within a shorter scope.
    y.insert(0, &x[0]);
}
println!("{:?}", &y);

If you were to instead push a reference of an item inside the block, then the lifetime of y could be shortened:

fn main() {
    let x = [1, 2, 3, 4];
    let mut y = vec![&x[1], &x[2], &x[3]];
    println!("{:?}", &y);
    {
        let inner = [1,2,3,4];
        y.insert(0, &inner[0]);
        println!("{:?}", &y);
    }
    // Requires that `y` and all it's elements live as long as `x`, because
    // `y` was initialized with values from `x`.
    println!("{:?}", &y);
}

This fails because inner doesn't live long enough. If you were to comment out the last println! then it would run, because the lifetime of the borrows of x (inside of y) can be shorted to the lifetime of inner.