Warning

This post was published 42 days ago. The information described in this article may have changed.

Info

This post is auto-generated from RSS feed The Rust Programming Language Forum - Latest topics. Source: Borrow checker issues when implementing recursive mutable iterator over tree structure

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?

4 posts - 2 participants

Read full topic

🏷️ rust_feed