Borrow scope in GAT lending iterator seems to extend beyond where it should?

help
1

Hi everyone - I spent yesterday banging my head against an implementation of a lending iterator for a tree traversal with nested iterators. I found a workaround, but it's a little confusing to me why the first one (below) fails to compile.

I've provided a simplified, stripped down version of the code to demonstrate the borrow issue, the logic here doesn't fully match what I'm doing (nor really make sense), but it suffices to show the compilation issue.

If there are better or cleaner solutions/workarounds, I'd love to see them, but my main goal here is to understand why one of these works and one doesn't. I'm probably missing something obvious, but this is feeling like a borrow checker limitation - any advice or pointers you can give are much appreciated!

So imagine we have this lending iterator (using a GAT lending iterator pattern, i.e. type Item<'a> = &'a TreeNodeData where Self: 'a;), it contains nested iterators such that it can depth-first traverse a tree, and each iterator owns its current node and its current child iterator state.

pub struct TreeNodeIter {
    some_data: TreeNodeData, // Placeholder
    child_iter: Option<Box<TreeNodeIter>>,
    // Only used in "workaround" LendingIteratorB variant
    should_get_next: bool
}

impl TreeNodeIter {
    pub fn get_next_iter() -> Option<Box<TreeNodeIter>> {
        // Placeholder for actual logic to get the next iterator
        unimplemented!()
    }
}

Again, don't worry too much about the implementation logic here as I stripped it down, but suffice to say is if we have a child iterator, we exhaust that first, get the next one (self.child_iter = Self::get_next_iter()), rinse and repeat.

The following implementation fails to compile at the marked line, which breaks my intuition a little - I would have thought that the borrow scope ends at the return?

    fn next_a(&mut self) -> Option<Self::Item<'_>> {
        // Let's try and hoist all this into its own scope
        {
            // If we have a child iterator, yield all entries from that first
            let child_iter = self.child_iter.as_mut();
            let entry = child_iter.and_then(|iter| iter.next_a());

            if entry.is_some() {
                return entry
            }
        }

        // Error: `cannot assign to `self.child_iter` because it is borrowed`
        // This fails, though AFAICT self.child_iter shouldn't be borrowed any more here since the previous block returns?
        // BUT (see next implementation) if we defer the mutation to the next call, it works
        self.child_iter = Self::get_next_iter();
        Some(&self.some_data)
    }

However, if I defer the assignment of self.next_iter to the next iteration of the loop, it's fine and functionally identical I think?

    fn next_b(&mut self) -> Option<Self::Item<'_>> {
        // Deferring the mutation here avoids the assignment error
        if self.should_get_next {
            self.child_iter = Self::get_next_iter();
            self.should_get_next = false;
        }

        // If we have a child iterator, yield all entries from that first
        let child_iter = self.child_iter.as_mut();
        let entry = child_iter.and_then(|iter| iter.next_b());

        if entry.is_some() {
            entry
        } else {
            self.should_get_next = true;
            Some(&self.some_data)
        }

Full playground link here:

Thanks in advance for any insights!

2

I should have probably tried this first, but this seems to compile okay with Polonius enabled, so it's probably a borrow checker limitation? I'd still love to understand the details though if anyone wants to chime in with the inside scoop.

3

Yep, conditional return of a borrow.

Let's start with a simple example without conditional returns:

fn example<'a>(s: &'a mut String) -> &'a str {
    let borrow: &'a str = &**s;
    println!("{borrow}");

    s.push('!');
    &**s
}

error[E0502]: cannot borrow `*s` as mutable because it is also borrowed as immutable
 --> src/lib.rs:5:5
  |
1 | fn example<'a>(s: &'a mut String) -> &'a str {
  |            -- lifetime `'a` defined here
2 |     let borrow: &'a str = &**s;
  |                 -------     -- immutable borrow occurs here
  |                 |
  |                 type annotation requires that `*s` is borrowed for `'a`
...
5 |     s.push('!');
  |     ^^^^^^^^^^^ mutable borrow occurs here

Normally, borrows only last so long as a value related to the borrow is in use. So the borrow &**s on line 2 would have ended immediately after the println!. But in this case, our annotation borrow: &'a str forced it to be longer. It forced it to be 'a.

What does "being 'a" mean? Rust lifetimes represent a borrow duration. The duration of any borrow that is passed into a function (like 'a is here) always includes the entirety of the function call.[1] Otherwise there'd be some place in the function where you couldn't use s. So we've forced the borrow on line 2 to be last throughout the rest of the function -- and that conflicts with the push on line 5.

Now if we go to your code:

    fn next_a(&mut self) -> Option<Self::Item<'_>> {
        // Let's try and hoist all this into its own scope
        {
            // If we have a child iterator, yield all entries from that first
            let child_iter = self.child_iter.as_mut();
            let entry = child_iter.and_then(|iter| iter.next_a());

            if entry.is_some() {
                return entry
            }
        }
        // ...

In the case where entry is returned, the signature requires that its associated borrow be the same duration as the lifetime in the &mut Self. That in tern means the call to as_mut as to borrow self.child_iter for the same duration. That's a lifetime that's larger than the function body, so -- with the current borrow checker -- you get an error later, similar to the simple example above. The borrow lasts for the rest of the function (and beyond).

But in this case, the return is conditional. If you could "look ahead" and only create a local, temporary borrow when you don't return (but still create the long borrow when you do return), then everything would work out.

And that's what Polonius aims to do: have more flow sensitivity so that the duration of the borrow can depend on conditional returns and similar.

There are a couple other examples in this blog post.

  1. It's at least just longer than the function call and it includes everywhere within the function. ↩ī¸Ž

3 Likes
4

Fantastic! Thanks for the detailed response, I really appreciate it!