Mutable iterator for tree like struct?

If I have simple tree like structure:

struct Foo {
    description: String,
    childs: Vec<Foo>,
}

there is simple way to implement read-only iterator for it:

struct LinearContentIterator<'a> {
    stack: Vec<&'a Foo>,
}

impl<'a> LinearContentIterator<'a> {
    fn new(root: &'a Foo) -> LinearContentIterator<'a> {
        let mut stack = Vec::with_capacity(100);
        stack.push(root);
        LinearContentIterator { stack }
    }
}

impl<'a> Iterator for LinearContentIterator<'a> {
    type Item = &'a Foo;
    fn next(&mut self) -> Option<Self::Item> {
        let item: Self::Item = self.stack.pop()?;
        for entry in item.childs.iter().rev() {
            self.stack.push(&*entry);
        }
        Some(item)
    }
}

but how should I implement mutable iterator, that allows change only description field in it?

The obvious way is not possible to compile, because of it takes two mut reference,
plus if it is possible to compile, I can see how to disable the way to change tree structure during iteration?

struct LinearContentIterator<'a> {
    stack: Vec<&'a mut Foo>,
}

impl<'a> LinearContentIterator<'a> {
    fn new(root: &'a mut Foo) -> LinearContentIterator<'a> {
        let mut stack = Vec::with_capacity(100);
        stack.push(root);
        LinearContentIterator { stack }
    }
}

impl<'a> Iterator for LinearContentIterator<'a> {
    type Item = &'a mut Foo;
    fn next(&mut self) -> Option<Self::Item> {
        let item: Self::Item = self.stack.pop()?;
        for entry in item.childs.iter_mut().rev() {
            self.stack.push(&mut *entry);
        }
        Some(item)
    }
}

You can’t write this Iterator because it would break Rust’s aliasing rules of &mut T. Because when you yield an element from your LinearContentIterator, you are yielding a &mut Foo, which must be unique. But you are also trying to store it’s children. Then one could use the &mut Foo that you yielded to alias the children still on the stack, thus breaking Rust’s aliasing rules.

Just use the field as the item.

impl<'a> Iterator for LinearContentIterator<'a> {
    type Item = &'a mut String;
    fn next(&mut self) -> Option<Self::Item> {
        self.stack.pop().map(|foo| {
            for entry in foo.childs.iter_mut().rev() {
                self.stack.push(entry);
            }
            &mut foo.description
        })
    }
}
4 Likes

Using the ? operator and Vec::extend, you can rewrite this to

impl<'a> Iterator for LinearContentIterator<'a> {
    type Item = &'a mut String;
    
    fn next(&mut self) -> Option<Self::Item> {
        let foo = self.stack.pop()?;

        self.stack.extend(foo.childs.iter_mut().rev());
        
        Some(&mut foo.description)
    }
}

Which is cleaner in my opinion

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.