Borrow checker issue trying to pass a function pointer as paramerter

Question

I am seeking help to understand why the borrow checker fails for the following minimal non-working example, and I would be very happy to learn how to correctly implement what I was trying to do:

use std::collections::HashSet;

struct Foo {
    data: HashSet<usize>
}

impl Foo {
    fn test<'a, F, T>(&mut self, _operation: F) -> ()
    where F: Fn(&'a HashSet<usize>, &'a HashSet<usize>) -> T,
          T: Iterator<Item=&'a usize>
    {
        let update: HashSet<usize> = vec![4, 2, 9].into_iter().collect();
        self.data = _operation(&self.data, &update).copied().collect();
    }

    fn new() -> Self {
        Foo { data: HashSet::new() }
    }
}


fn main() {
    let mut foo: Foo = Foo::new();
    foo.test(HashSet::intersection);
}

My main source of confusion is that, if I replace the call to _operation with HashSet::intersection, the code compiles. I thought that the type of the parameter _operation would allow me to pass both HashSet::intersection and HashSet::union as operations here.

For the record, this is the error I receive:

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src\main.rs:13:32
   |
13 |         self.data = _operation(&self.data, &update).copied().collect();
   |                                ^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 8:23...
  --> src\main.rs:8:23
   |
8  |     fn test<'a, F, T>(&mut self, _operation: F) -> ()
   |                       ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src\main.rs:13:32
   |
13 |         self.data = _operation(&self.data, &update).copied().collect();
   |                                ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the method body at 8:13...
  --> src\main.rs:8:13
   |
8  |     fn test<'a, F, T>(&mut self, _operation: F) -> ()
   |             ^^
note: ...so that reference does not outlive borrowed content
  --> src\main.rs:13:32
   |
13 |         self.data = _operation(&self.data, &update).copied().collect();
   |                                ^^^^^^^^^^

For more information about this error, try `rustc --explain E0495`.
error: could not compile `aoc06` due to previous error

Answer 1

The arguments you are passing do not match the lifetime which you declared the Fn bound with.

fn test<'a, F, T>(&mut self, _operation: F) -> ()

'a is some arbitrary lifetime that may be specified by the caller,

    F: Fn(&'a HashSet<usize>, &'a HashSet<usize>) -> T,

which must be adequate for the references given to _operation,

        let update: HashSet<usize> = vec![4, 2, 9].into_iter().collect();
        self.data = _operation(&self.data, &update).copied().collect();

but here you pass in a borrow from self (whose lifetime is not specified to outlive 'a) and a borrow from update (which is a local variable, which cannot outlive 'a).

---

In order to correctly write this, you need to specify that _operation may be called with any lifetime (which thus includes the lifetimes of borrows of local variables). That's simple, by itself:

    fn test<F, T>(&mut self, _operation: F) -> ()
    where
        F: for<'a> Fn(&'a HashSet<usize>, &'a HashSet<usize>) -> T,

Note that 'a is no longer a lifetime parameter of test. Instead it's part of the bound on F: you can read this for<'a> notation as “for any lifetime, which we will call 'a, F may be called as a function with references &'a ...”.

However, this isn't actually a solution, because you also have T: Iterator<Item = &'a usize>, which uses 'a again. It isn't currently possible to write a where clause that expresses this relationship, particularly as even without the item being a reference, the iterator will be borrowing the &'a HashSets.

This is an unfortunate limitation of current Rust — it also comes up in trying to write a function that takes an async function which borrows an input (which is structurally the same as your situation, with Future in place of Iterator). However, there is a workaround: you can define a trait for the function, which has a single lifetime parameter that links everything together. (This doesn't impose any extra work on the caller of your function, because the trait is blanket implemented for all suitable functions.)

Here's your code with such a trait added and the needed modifications to fn test():

use std::collections::HashSet;

trait IteratorCallback<'a> {
    type Output: Iterator<Item = &'a usize> + 'a;
    fn call(self, a: &'a HashSet<usize>, b: &'a HashSet<usize>) -> Self::Output;
}

impl<'a, F, T> IteratorCallback<'a> for F
where
    F: FnOnce(&'a HashSet<usize>, &'a HashSet<usize>) -> T,
    T: Iterator<Item = &'a usize> + 'a,
{
    type Output = T;
    fn call(self, a: &'a HashSet<usize>, b: &'a HashSet<usize>) -> T {
        // Delegate to FnOnce
        self(a, b)
    }
}

struct Foo {
    data: HashSet<usize>,
}

impl Foo {
    fn test<F>(&mut self, _operation: F) -> ()
    where
        F: for<'a> IteratorCallback<'a>,
    {
        let update: HashSet<usize> = vec![4, 2, 9].into_iter().collect();
        self.data = _operation.call(&self.data, &update).copied().collect();
    }

    fn new() -> Self {
        Foo {
            data: HashSet::new(),
        }
    }
}

fn main() {
    let mut foo: Foo = Foo::new();
    foo.test(HashSet::intersection);
}

Note: I changed the function bound to FnOnce because that's more permissive than Fn and all you need in this case, but the same technique will work with Fn as long as you change fn call(self, to fn call(&self,.

Credit: I used this Reddit comment by user Lej77 as an example to work from for the trait technique.

Answer 2

The issue, as the (albeit cryptic) compiler message suggests, is that there is a lifetime mismatch: _operation expects HashSet references that live as long as 'a, but &self.data has a lifetime 'b, the elided lifetime of &mut self, and &update has a different lifetime that lasts the duration of the test function body.

To resolve this issue, we must specify that the function type F takes in HashMap references of arbitrary lifetimes, not just the specific lifetime 'a -- this lets the compiler infer the appropriate lifetime when _operation is invoked. This is why we need Higher-Rank Trait Bounds (HRTBs):

fn test<F, T>(&mut self, _operation: F) -> ()
    where F: for<'a> Fn(&'a HashSet<usize>, &'a HashSet<usize>) -> T,

However, this raises another issue. How do we apply the higher-ranked lifetime 'a to the type parameter T? Unfortunately Rust does not support higher-kinded types, but we can get away with "abstracting" out the the function type F and the higher-kinded type T to a trait and an associated type on said trait.

trait Operation<'a, T: 'a> {
    type Output: Iterator<Item = &'a T>;
    fn operate(self, a: &'a HashSet<T>, b: &'a HashSet<T>) -> Self::Output;
}

The Operation trait represents an operation on two HashSets that returns an iterator over references, equivalent to the functions HashSet::union, HashSet::intersection, and the like. We can achieve this using the following impl, which ensures that HashSet::intersection and the like implement Operation:

impl<'a, T: 'a, I, F> Operation<'a, T> for F
where
    I: Iterator<Item = &'a T>,
    F: FnOnce(&'a HashSet<T>, &'a HashSet<T>) -> I,
{
    type Output = I;

    fn operate(self, a: &'a HashSet<T>, b: &'a HashSet<T>) -> Self::Output {
        self(a, b)
    }
}

We can then use a HRTB on the Operation trait instead, which does not require any nested higher-kinded types:

fn test(&mut self, _operation: impl for<'a> Operation<'a, usize>) -> () {
    let update: HashSet<usize> = vec![4, 2, 9].into_iter().collect();
    self.data = _operation.operate(&self.data, &update).copied().collect();
    println!("{:?}", self.data);
}

Playground