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, Self> {
        NodesIterMut::new(self) // implements Iterator<Item = &mut Self>
    }

    // ... other methods omitted
}

The immutable iterator works, but I can't figure out how to implement the mutable iterator.

I implemented the recursion with a Vec that contains references to all ancestors of the current node. But that doesn't work for the mutable version, since mutable references can't alias.

Does anyone have an idea how this could be solved?

I'm not asking for a complete solution, just an idea to nudge me into the right direction :slight_smile:

Here's a playground link with all my code.

In general, you can't implement mutable iterators abstractly. They require you to know how your types operate concretely, and so you usually can't specify a mutable iterator abstractly. Moreover what you are trying to achieve is fundementally at odds with Rust's aliasing model*.

You seem to want to yield entire sub-trees from your iterator, so let's say you return a reference to the sub-tree , and store the children or ancestors in order to continue traversing the tree. What happens when someone tries to access those same children or ancestors? You would have aliasing &mut T! This is forbidden. This is a large reason why trees require unsafe code to implement efficiently.

Now there may be another way around this! What if instead of yielding entire sub-trees from your iterator, you only yielded values? You would also need a way to split a tree node into it's parts (something like fn split_mut(&'a mut self) -> (&'a mut Self::Value, Self::MutIter)). With this you could implement a mutable iterator.

(note) * Rust doesn't have a formal aliasing model yet, but we do have 1 thing we guarantee, &mut T are exclusive references that cannot be aliased except by pointers derived from it. (And is inactive while those derived pointers are active). The best we got right now can be seen in the unsafe working group's UCG


edit: On a separate note, you don't need to annotate the lifetimes of any method that doesn't interact with RefIter or MutIter because that's unnecessarily restrictive. (for example, is_empty, first, last, etc.). This will require that you remove the default impls, but in exchange Tree will be far more useful.

1 Like