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!

4 posts - 2 participants

Read full topic