Borrow checker issues when implementing recursive mutable iterator over tree structure

[sseemayer]

Playground link

I have a tree structure like this:

pub struct Group {
    pub name: String,
    pub children: Vec<Node>,
}

pub struct Entry {
    pub data: String,
}

pub enum Node {
    Group(Group),
    Entry(Entry),
}

with reference types:

pub enum NodeRef<'a> {
    Group(&'a Group),
    Entry(&'a Entry),
}

pub enum NodeRefMut<'a> {
    Group(&'a mut Group),
    Entry(&'a mut Entry),
}

I want to implement NodeIter and NodeIterMut so that I can recursively iterate over all nodes in a given tree structure:

pub struct NodeIter<'a> {
    queue: VecDeque<NodeRef<'a>>,
}

impl<'a> NodeIter<'a> {
    pub fn new(node: &'a Node) -> Self {
        let mut queue = VecDeque::new();
        queue.push_front(node.into());

        Self { queue }
    }
}

impl<'a> Iterator for NodeIter<'a> {
    type Item = NodeRef<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        let head = self.queue.pop_front();

        if let Some(NodeRef::Group(group)) = head {
            for node in group.children.iter().rev() {
                self.queue.push_front(node.into());
            }
        }

        head
    }
}

however, when I do the equivalent for NodeIterMut,

pub struct NodeIterMut<'a> {
    queue: VecDeque<NodeRefMut<'a>>,
}

impl<'a> NodeIterMut<'a> {
    pub fn new(node: &'a mut Node) -> Self {
        let mut queue = VecDeque::new();
        queue.push_front(node.into());

        Self { queue }
    }
}

impl<'a> Iterator for NodeIterMut<'a> {
    type Item = NodeRefMut<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        let head = self.queue.pop_front();

        if let Some(NodeRefMut::Group(group)) = head {
            for node in group.children.iter_mut().rev() {
                self.queue.push_front(node.into());
            }
        }

        head
    }
}

I cannot get around a borrow checker issue:

error[E0382]: use of partially moved value: `head`
   --> src/main.rs:114:9
    |
107 |         if let Some(NodeRefMut::Group(group)) = head {
    |                                       ----- value partially moved here
...
114 |         head
    |         ^^^^ value used here after partial move
    |
    = note: partial move occurs because value has type `&mut Group`, which does not implement the `Copy` trait
help: borrow this binding in the pattern to avoid moving the value
    |
107 |         if let Some(NodeRefMut::Group(ref group)) = head {
    |                                       +++

Can anyone suggest an alternate design for NodeIterMut, preferably without unsafe code, that compiles?

[sseemayer]

I have found these threads but they didn't get me any further

Help: Implement recursive, mutable tree iterator

I'm writing a Tree trait that provides methods to recursively iterate over all nodes: pub trait Tree<'a>: Sized + 'a { type RefIter: Iterator<Item = &'a Self> + 'a; type MutIter: Iterator<Item = &'a mut Self> + 'a; fn children(&'a self) -> Self::RefIter; fn children_mut(&'a mut self) -> Self::MutIter; fn nodes(&'a self) -> NodesIter<'a, Self> { NodesIter::new(self) // implements Iterator<Item = &Self> } fn nodes_mut(&'a mut self) -> NodesIterMut<'a, Sel…

Traversing recursive type with a mutable reference

I'm working with a binary tree type (simplified here): enum Node { Good { left: Option<Box<Node>>, right: Option<Box<Node>>, }, Bad, } To get a mutable reference to the leftmost node, what would be the minimal element in a BST, I wrote this code: impl Node { fn left_child_mut(&mut self) -> Option<&mut Node> { match *self { Node::Good { left: Some(ref mut child), .. } => Some(child), _ => None, } } fn leftmost_mut…

Implementing an Iterator of mutable references

Your chaining approach was correct. Unfortunately, implementing this directly is impossible without using unsafe because rust can't statically guarantee that you won't call get_mut twice with the same index (getting two mutable references to the same item). use std::iter; use std::slice::IterMut; struct NE<T> { head: T, rest: Vec<T> } impl<T> NE<T> { pub fn get(&self, idx: usize) -> Option<&T> { if idx == 0 { Some(&self.head) } else { self.…

I have also found the chapter in the linked lists book but don't know how I could apply the trick here.

[steffahn]

You iterator is impossible to implement because it would be unsound. This is because you're trying to have it return mutable references to tree nodes and then also to their children. But the Iterator trait doesn't actually restrict its users in any way on how they can use the items of the iterator, do they get to handle them all at the same time (e. g. .collect() couldn't exist if this wasn't the case).

So the iterator items having some &mut Group contained in one item, and then some NodeRefMut to any of the children in another item is plainly an instance of aliasing mutable references, at least in the logical sense of how these types are composed. And the former &mut Group can of course also be projected (via field access) to an actually aliasing reference, in safe code, e. g. producing a second NodeRefMut to the same child.

---

Now the space of possible solutions is relatively wide. But there's two general directions to take in restricting the API you're implementing, in order to gain a sound interface:

One solution is to plainly avoid producing any reference with access to children, for the higher-up nodes, in the first place! E. g. for Group, only let them access name.

The other direction would be to not let users consume items non-sequentially. You would need to abandon the Iterator trait entirely. Instead, the easiest might be to simply offer something like a for_each iteration method (taking a callback) which can be plenty sufficient for many use cases - or look into traits supporting some form of "lending iterator" or "streaming iterator" kind of interfaces, if you're interested in relevant keywords to search for more discussion

[sseemayer]

Thanks for the quick reply, that makes sense! I will re-think what I am trying to do on a fundamental level.

---

I wanted to implement a "find entry by key" method in a generic way and ended up implementing the concrete version of it instead.