Impl Fn, borrowing and lifetime error

[wkordalski]

I have the following code. Could you explain me why I get a lifetime error during building?
Note: here context is (), but it is crucial to get this error. In real-world application I have something more sensible than unit type.

struct Tree {
    parents: Vec<usize>,
}

#[derive(Clone)]
struct Node<'tree> {
    tree: &'tree Tree,
    idx: usize,
}

struct FindAtPathToRoot<'tree, F>
where
    F: for<'a> Fn(&'a Node<'tree>) -> bool,
{
    node: Option<Node<'tree>>,
    func: F,
}

impl<'tree, F> Iterator for FindAtPathToRoot<'tree, F>
where
    F: for<'a> Fn(&'a Node<'tree>) -> bool,
{
    type Item = Node<'tree>;

    fn next(&mut self) -> Option<Node<'tree>> {
        loop {
            let curr_node = self.node.take()?;
            let next_idx = curr_node.tree.parents[curr_node.idx];
            let next_node = if next_idx == curr_node.idx {
                None
            } else {
                Some(Node {
                    tree: curr_node.tree,
                    idx: next_idx,
                })
            };
            self.node = next_node;
            if (self.func)(&curr_node) {
                return Some(curr_node);
            }
        }
    }
}

fn find_by_key<'a, 't: 'a, K, C, F>(
    node: Node<'t>,
    key: &'a K,
    key_func: F,
    context: &'a C,
) -> impl Iterator<Item = Node<'t>> + 'a
where
    F: for<'c> Fn(&'c Node<'t>, &'a C) -> K + 'a,
    K: Eq,
{
    FindAtPathToRoot {
        node: Some(node.clone()),
        func: move |n: &Node| key_func(n, context) == *key,
    }
}

fn keys_sequence<'x: 'y, 'y, K, F>(
    key_sequence: &'y [K],
    key_func: F,
    mut node: Node<'x>,
) -> Option<Node<'x>>
where
    F: for<'v> Fn(&'v Node<'x>, &'y ()) -> K + 'y,
    K: Eq,
{
    for key in key_sequence {
        node = find_by_key(node, key, &key_func, &()).next()?;
    }

    Some(node)
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0597]: `key_func` does not live long enough
  --> src/lib.rs:64:39
   |
54 | fn keys_sequence<'x: 'y, 'y, K, F>(
   |                          -- lifetime `'y` defined here
...
64 |         node = find_by_key(node, key, &key_func, &()).next()?;
   |                -----------------------^^^^^^^^^------
   |                |                      |
   |                |                      borrowed value does not live long enough
   |                argument requires that `key_func` is borrowed for `'y`
...
68 | }
   | - `key_func` dropped here while still borrowed

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

[alice]

I haven't looked very closely at your code, but whatever it is you're trying to do, the correct implementation will have much fewer lifetime annotations than this.

One thing that might work is to redefine Node to drop the lifetime like this:

struct Node {
    idx: usize,
}

[steffahn]

With some trickery, you can adjust the signature to get rid of the F: 'a that’s causing problems here.

+ // helper trait to allow “mentioning” another lifetime in `impl` return type
+ // without it needing to be an “outlives” bound
+ trait CapturesLifetime<'a> {}
+ impl<T: ?Sized> CapturesLifetime<'_> for T {}

fn find_by_key<'a, 't: 'a, K, C, F>(
    node: Node<'t>,
    key: &'a K,
    key_func: F,
    context: &'a C,
- ) -> impl Iterator<Item = Node<'t>> + 'a
+ ) -> impl Iterator<Item = Node<'t>> + CapturesLifetime<'a>
where
-   F: for<'c> Fn(&'c Node<'t>, &'a C) -> K + 'a,
+   F: for<'c> Fn(&'c Node<'t>, &'a C) -> K,
    K: Eq,
{
    FindAtPathToRoot {
        node: Some(node.clone()),
        func: move |n: &Node| key_func(n, context) == *key,
    }
}

Rust Playground

---

(Removing further redundant bounds: after that change, the 't: 'a relation becomes unnecessary, too.)

[wkordalski]

@alice

One thing that might work is to redefine Node to drop the lifetime like this:

struct Node {
    idx: usize,
}

Unfortunatelly I cannot modify Tree and Node types, as they are not defined by me.

@steffahn

With some trickery, you can adjust the signature to get rid of the F: 'a that’s causing problems here.

Thanks! It works.
However, I still do not understand why my code is not accepted by the compiler.
I would greatly appreciate some hint that would help me understand this case of "the lifetime calculus".

[steffahn]

Well okay… there’s a lot of places with lifetime involved here. I think the problem is that F: … Fn(…, &'a C) means that F nails down the lifetime 'a in find_by_key (lifetime arguments in trait parameters are invariant) to be exactly the same as the 'y in keys_sequence; but then there’s the F: 'a bound which thus translates to a bound : 'y on the type of &key_func, which is a reference to the parameter of type F in keys_sequence. Say, the borrow lasts for 'lt, so &key_func is of type &'lt F, then the F: 'a bound (on the F of find_by_key) materializes as a &'lt F: 'y bound, which requires two things: F: 'y (which you have), and 'lt: 'y which is the problematic part, since you cannot borrow key_func for the lifetime 'y, hence the error message.

As to why the solution works, well, obviously removing the F: 'a removes the problem; but why is it no longer necessary and what does the CapturesLifetime trait have to to with it? In order to fully understand this, one has to read through the details of this RFC 1951-expand-impl-trait - The Rust RFC Book. Just removing the F: 'a

fn find_by_key<'a, 't: 'a, K, C, F>(
    node: Node<'t>,
    key: &'a K,
    key_func: F,
    context: &'a C,
) -> impl Iterator<Item = Node<'t>> + 'a
where
    F: for<'c> Fn(&'c Node<'t>, &'a C) -> K,
    K: Eq,
{
    FindAtPathToRoot {
        node: Some(node.clone()),
        func: move |n: &Node| key_func(n, context) == *key,
    }
}

would lead to

error[E0309]: the parameter type `F` may not live long enough
  --> src/lib.rs:50:6
   |
50 | ) -> impl Iterator<Item = Node<'t>> + 'a
   |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...so that the type `FindAtPathToRoot<'_, [closure@src/lib.rs:57:15: 57:59]>` will meet its required lifetime bounds
   |
help: consider adding an explicit lifetime bound...
   |
52 |     F: for<'c> Fn(&'c Node<'t>, &'a C) -> K + 'a,
   |                                             ++++

The problem being that the returned type contains a value of type F, and thus the impl … + 'a in the return type means we need F: 'a. Or remove that + 'a in the return type! Leading to

fn find_by_key<'a, 't: 'a, K, C, F>(
    node: Node<'t>,
    key: &'a K,
    key_func: F,
    context: &'a C,
) -> impl Iterator<Item = Node<'t>>
where
    F: for<'c> Fn(&'c Node<'t>, &'a C) -> K,
    K: Eq,
{
    FindAtPathToRoot {
        node: Some(node.clone()),
        func: move |n: &Node| key_func(n, context) == *key,
    }
}

error[E0700]: hidden type for `impl Trait` captures lifetime that does not appear in bounds
  --> src/lib.rs:55:5
   |
45 |   fn find_by_key<'a, 't: 'a, K, C, F>(
   |                  -- hidden type `FindAtPathToRoot<'t, [closure@src/lib.rs:57:15: 57:59]>` captures the lifetime `'a` as defined here
...
55 | /     FindAtPathToRoot {
56 | |         node: Some(node.clone()),
57 | |         func: move |n: &Node| key_func(n, context) == *key,
58 | |     }
   | |_____^
   |
help: to declare that the `impl Trait` captures `'a`, you can add an explicit `'a` lifetime bound
   |
50 | ) -> impl Iterator<Item = Node<'t>> + 'a
   |                                     ++++

Admitted, it’s a bit harsh to go against the compiler suggesting to undo our first change, and then do a different change, where the follow-up compilation error is also containing a suggestion to undo that second change… but we’re smarter than compiler suggestions here: The problem is not that we have any reason for actually requiring the returned type to outlive 'a, no, the problem is that it “captures [a] lifetime that does not appear [anywhere] in [the] bounds”; it doesn’t need to be in the form + 'a, but any syntactical appearance would count! Including the + CapturesLifetime<'a> approach, which has the huge advantage of not entailing the RETURN_TYPE: 'a bound that in-turn led to us needing F: 'a. Why are the rules like this!? Well, I agree it’s confusing and seems a bit arbitrary, but at least the abovelinked RFC explains how they are in detail. I’m not particularly happy with it either, but at least I know how to work around it.

[quinedot]

However, I still do not understand why my code is not accepted by the compiler.

I've written up my own journey looking at your playground, in case it's helpful.

I'm guessing the confusion because on keys_sequence, you have

    F: for<'v> Fn(&'v Node<'x>, &'y ()) -> K + 'y,

but you're still getting the following?

71 |         node = find_by_key(node, key, &key_func, &()).next()?;
   |                -----------------------^^^^^^^^^------
   |                |                      |
   |                |                      borrowed value does not live long enough
   |                argument requires that `key_func` is borrowed for `'y`

The immediate problem is that

• 'y is a lifetime parameter to your function
  • That means the caller chooses 'y. All you know is that it's at least just longer than your function body (so it's valid everywhere in your function), plus any other bounds (like 'x: 'y) are met.
• You took key_func: F by value.
• You're apparently (from the error) trying to borrow F for 'y.

You can't take a reference to a local value (key_func) for longer than the function body, and 'y is necessarily longer; that's why it's an error. That is what I got from the error and code alone, on a first go. And incidentally, it doesn't matter that F: 'y -- that F is valid for 'y -- it's still a local value that's going to go away at the end of your function body.

Why does the reference you take to key_func have to be at least 'y though? Because otherwise the reference you pass doesn't meet the + 'a bound on find_by_key (which corresponds to 'y in keys_sequence). So that's at least nominally the reason for the error: the bounds on find_by_key dictate you take a reference to a local variable longer than the function body (for the length of a lifetime parameter).

At this point of the investigation, you could

-key_func: F,
+key_func: &'y F,
 // ...
-        node = find_by_key(node, key, &key_func, &()).next()?;
+        node = find_by_key(node, key, key_func, &()).next()?;

But this isn't actually an ideal fix and probably just pushes the problems into callers of keys_sequence, who will run into the same sort of problems. Or you could add a + Clone bound and clone every time through the loop etc... but again this is dodging the deeper issue. find_by_key has pushed its problems onto keys_sequence.

---

So why is that + 'a bound on find_by_key there then? Based on what happens when I remove it, presumably because the compiler told you to add it, so that impl Iterator<...> + 'a would work. And in turn, I'm going to assume that you added + 'a to

// find_by_key
) -> impl Iterator<Item = Node<'t>> + 'a

not out of intuition or specifically thinking "I need the iterator to be valid for all of 'a", but because you got an error about capturing some hidden lifetime ^[1]. IMO the key points to understand at this point are

• + 'a imposes a lower bound on the region of validity -- it can only increase the required validity -- and so multiple + 'x act like a union of the lifetime regions

  • and thus if there are other lifetimes involved, they must outlive all + 'a + 'b
  • which is an additional constraint you don't want

• What you actually want is for the iterator to only be required to be valid for whichever lifetime happens to be shortest (without imposing further outlives requirements between them)

  • i.e. the intersection of the lifetimes
  • like how multiple unbound lifetimes on types work

And thus the compiler suggestion was in fact a poor one. Honestly, I wonder if "the compiler's telling me to add + 'x to return-position impl Trait" should instantly be considered a "bad hint" flag, the way "add 'static to T" is.

Anyway, for the workaround, you also need to realize that

• In the context of return-position impl Trait, the additional lifebound trait bound acts in the intersection-like manner

So where can you read up more about this? Unfortunately, I'm unaware of any "lifetime calculus" guide for Rust. The knowledge is scattered all over the place (RFCs, tracking issues because of issues that weren't covered by the RFC or the RFC was deviated from, some key yet non-official blog posts, et cetera). As far as I'm aware, the main practical way to learn is experience and participating in threads, or other forms of troubleshooting, like this one.

---

1. as again that's what I got when I removed it ↩︎

[wkordalski]

Thanks both of you very much!
Now, after reading both answers and some more about variance, I intuitively understand this. But only intuitively

The main point is that I was not aware of the difference between T: 'a and T: Trait<'a> (and their different semantics).