Mutable iterator for a struct

Hi all,

I'm fighting with the compiler to implement a mutable iterator for a struct. In case of non-mutable, it works perfectly. The iterator just returns the second field if first is None , first and then second if not.

pub struct Queue<'a, T> {
    first: Option<&'a mut T>,
    second: &'a mut T,
}

// helper structs
pub struct IterHelper<'a, T> {
    index: usize,
    queue: &'a Queue<'a, T>,
}

// IntoIter()
impl<'a, T> IntoIterator for &'a Queue<'a, T> {
    type Item = &'a &'a mut T;
    type IntoIter = IterHelper<'a, T>;

    // note that into_iter() is consuming self
    fn into_iter(self) -> Self::IntoIter {
        IterHelper {
            index: 0,
            queue: &self,
        }
    }
}

// now, implements Iterator trait for the helper structs, to be used by adapters
impl<'a, T> Iterator for IterHelper<'a, T> {
    type Item = &'a &'a mut T;

    // just return the reference
    fn next(&mut self) -> Option<Self::Item> {
        match self.index {
            0 => {
                if self.queue.first.is_some() {
                    self.index = 1;
                    return Some(self.queue.first.as_ref().unwrap());
                } else {
                    self.index = 2;
                    return Some(&self.queue.second);
                }
            }
            1 => {
                self.index = 2;
                return Some(&self.queue.second);
            }
            _ => return None,
        };
    }
}

But the mutable version doesn't compile:

// helper structs
pub struct IterMutHelper<'a, T: 'a> {
    index: usize,
    queue: &'a mut Queue<'a, T>,
}

// IntoIter()
impl<'a, T> IntoIterator for &'a mut Queue<'a, T> {
    type Item = &'a mut &'a mut T;
    type IntoIter = IterMutHelper<'a, T>;

    // note that into_iter() is consuming self
    fn into_iter(self) -> Self::IntoIter {
        IterMutHelper {
            index: 0,
            queue: &mut self,
        }
    }
}

// now, implements Iterator trait for the helper structs, to be used by adapters
impl<'a, T> Iterator for IterMutHelper<'a, T> {
    type Item = &'a mut &'a mut T;

    // just return the str reference
    fn next(&mut self) -> Option<Self::Item> {
        match self.index {
            0 => {
                if self.queue.first.is_some() {
                    self.index = 1;
                    //return Some(self.queue.first.as_mut().unwrap());
                    return None;
                } else {
                    self.index = 2;
                    //return Some(&mut self.queue.second);
                    return None;
                }
            }
            1 => {
                self.index = 2;
                return Some(&mut self.queue.second);
            }
            _ => return None,
        };
    }
}

with the following error:

   --> src/main.rs:112:29
    |
112 |                 return Some(&mut self.queue.second);
    |                             ^^^^^^^^^^^^^^^^^^^^^^
    |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 97:5...
   --> src/main.rs:97:5
    |
97  |     fn next(&mut self) -> Option<Self::Item> {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
   --> src/main.rs:112:29
    |
112 |                 return Some(&mut self.queue.second);
    |                             ^^^^^^^^^^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 93:6...
   --> src/main.rs:93:6
    |
93  | impl<'a, T> Iterator for IterMutHelper<'a, T> {
    |      ^^
note: ...so that the types are compatible
   --> src/main.rs:97:46
    |
97  |       fn next(&mut self) -> Option<Self::Item> {
    |  ______________________________________________^
98  | |         match self.index {
99  | |             0 => {
100 | |                 if self.queue.first.is_some() {
...   |
115 | |         };
116 | |     }
    | |_____^
    = note: expected `std::iter::Iterator`
               found `std::iter::Iterator`

What I don't understand is what makes the mutable version so different from the non-mutable one, in terms of references, because the non-mutable works ?

Playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=998b2889287d4409a6e298d17251e8c4

Thanks for your help.

The fundamental difference is the non-aliasing guarantee that Rust enforces for &mut references: To ensure that nothing sees a partially-updated state of the object, no other references are allowed to exist while an &mut exists.

In the case of an iterator, the downstream user is allowed to keep the first result when calling next() to get the second, so the compiler requires all of the iterator’s results to be able to coexist at the same time.

2 Likes

@2e71828 Thanks for your comment. This means there's no solution ?

It should be possible by splitting the borrow, but I'm having trouble coming up with the right way to do it for your example.


Edit: I've got something that works, but it doesn't feel great. Maybe it can give you some ideas, at least:

// helper structs
pub struct IterMutHelper<'a, T: 'a> {
    data: Vec<&'a mut T>
}

// IntoIter()
impl<'a,'b:'a, T> IntoIterator for &'a mut Queue<'b, T> {
    type Item = &'a mut T;
    type IntoIter = IterMutHelper<'a, T>;

    // note that into_iter() is consuming self
    fn into_iter(self) -> Self::IntoIter {
        let mut data = Vec::new();
        data.push(&mut *self.second);
        if let Some(x) = self.first.as_mut() {
            data.push(x);
        }
        IterMutHelper { data }
    }
}

// now, implements Iterator trait for the helper structs, to be used by adapters
impl<'a, T> Iterator for IterMutHelper<'a, T> {
    type Item = &'a mut T;

    // just return the str reference
    fn next(&mut self) -> Option<Self::Item> {
        self.data.pop()
    }
}

(Playground)

@2e71828 Thanks for your hint. I was reluctant to use a Vec, it was overkill for me. Using a Vector, I already done it in one of my tutorial on dev.to (https://dev.to/dandyvica/yarit-yet-another-rust-iterators-tutorial-46dk).

There's nothing special about the Vec; it was just the most convenient container for several &muts that could then transfer them by ownership later. You could do the same thing with a bunch of Options and a match statement.

The key is to, for each node in your data structure, produce the references to its fields at the same time and then store them for later if necessary.

One such elaboration.

impl<'a, 'b: 'a, T> IntoIterator for &'a mut Queue<'b, T> {
    type Item = &'a mut T;
    type IntoIter =
        std::iter::Chain<std::option::IntoIter<&'a mut T>, std::option::IntoIter<&'a mut T>>;

    fn into_iter(self) -> Self::IntoIter {
        let tail = Some(&mut *self.second).into_iter();
        if self.first.is_some() {
            self.first.as_deref_mut().into_iter().chain(tail)
        } else {
            tail.chain(None.into_iter())
        }
    }
}

The use of chain, as @quinedot already suggested, is a great option. I would suggest using iter::once, too. (Even though it should not really make a difference at all internally/implementation-wise.)

Also you’d need to consider if you want an &'b mut Queue<'a, T> to turn into an iterator of &'b mut &'a mut T or an iterator of &'b mut T (the former would allow modifying the references in the queue themselves, e.g. make them point at something different). Similarly, your immutable iterator could/should support different lifetimes &'b Queue<'a, T>. For that one the item type should definitely be &'b T then though since &'b &'a mut T doesn’t have any actual advantages (i.e. anything more you can do with it, but it is one more indirection).

A version for Item = &'b mut &'a mut T:

use std::{iter, option};
impl<'b, 'a, T> IntoIterator for &'b mut Queue<'a, T> {
    type Item = &'b mut &'a mut T;
    type IntoIter = iter::Chain<option::IterMut<'b, &'a mut T>, iter::Once<&'b mut &'a mut T>>;
    fn into_iter(self) -> Self::IntoIter {
        (&mut self.first).into_iter().chain(iter::once(&mut self.second))
    }
}

A version for Item = &'b mut T:

use std::{iter, option};
impl<'b, T> IntoIterator for &'b mut Queue<'_, T> {
    type Item = &'b mut T;
    type IntoIter = iter::Chain<option::IntoIter<&'b mut T>, iter::Once<&'b mut T>>;
    fn into_iter(self) -> Self::IntoIter {
        self.first.as_deref_mut().into_iter().chain(iter::once(&mut *self.second))
    }
}

One disadvantage of such an IntoIterator implementation is that changing the type IntoIter later could be seen as a breaking change. A newtype-pattern for encapsulating the IntoIter type is a possibility to solve this issue.

use std::{
    iter::{self, DoubleEndedIterator},
    marker::PhantomData,
    option,
};
impl<'b, 'a, T> IntoIterator for &'b mut Queue<'a, T> {
    type Item = &'b mut T;
    type IntoIter = IterMut<'b, 'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        Self::IntoIter::new(self)
    }
}

// The `'a` parameter is to make sure you really can’t have any
// breakage when `Queue` and/or the iterator implementation changes
pub struct IterMut<'b, 'a, T>(
    iter::Chain<option::IntoIter<&'b mut T>, iter::Once<&'b mut T>>,
    PhantomData<&'b mut Queue<'a, T>>,
);
impl<'b, 'a, T> IterMut<'b, 'a, T> {
    fn new(q: &'b mut Queue<'a, T>) -> Self {
        Self(
            q.first
                .as_deref_mut()
                .into_iter()
                .chain(iter::once(&mut *q.second)),
            PhantomData,
        )
    }
}
impl<'b, T> Iterator for IterMut<'b, '_, T> {
    type Item = &'b mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}
impl<T> iter::FusedIterator for IterMut<'_, '_, T> {}
impl<T> DoubleEndedIterator for IterMut<'_, '_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back()
    }
}
impl<T> iter::ExactSizeIterator for IterMut<'_, '_, T> {}

The disadvantage over just exposing the type is that you need to write all those impls. One advantage is that you can implement ExactSizeIterator which Chain doesn’t support in general for very subtle corner-case-issue reasons that don’t apply here.

Finally, for a take on how one could manually implement an iterator (I’m showing just the next() method of Interator; you could however take this further and implement DoubleEndedIterator, and size_hint and even fold and nth, etc... I actually think this would be a great exercise to practice implementing iterators):

use std::mem;
impl<'b, 'a, T> IntoIterator for &'b mut Queue<'a, T> {
    type Item = &'b mut T;
    type IntoIter = IterMut<'b, 'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        Self::IntoIter::new(self)
    }
}

// See how the 'a parameter in the previous example makes this
// implementation a 100% compatible drop-in replacement?
pub struct IterMut<'b, 'a, T>(IterMutInner<'b, 'a, T>);
enum IterMutInner<'b, 'a, T> {
    AllItems(&'b mut Queue<'a, T>),
    OneItem(&'b mut T),
    Empty,
}
impl<T> Default for IterMutInner<'_, '_, T> {
    fn default() -> Self {
        IterMutInner::Empty
    }
}
impl<'b, 'a, T> IterMut<'b, 'a, T> {
    fn new(q: &'b mut Queue<'a, T>) -> Self {
        Self(IterMutInner::AllItems(q))
    }
}
impl<'b, T> Iterator for IterMut<'b, '_, T> {
    type Item = &'b mut T;
    // Fun fact: changing the Item type to &'b mut &'a mut T
    // does require changes to the IterMutInner type, but the
    // code for the `next` method below does not need to change at all!
    fn next(&mut self) -> Option<Self::Item> {
        use IterMutInner::*;
        match mem::take(&mut self.0) {
            AllItems(r) => match r.first.as_mut() {
                Some(item) => {
                    self.0 = OneItem(&mut r.second);
                    Some(item)
                }
                None => Some(&mut r.second)
            }
            OneItem(item) => Some(item),
            Empty => None,
        }
    }
}
2 Likes

@steffahn Thanks a lot for your suggestion ! This is a lot of code :wink:

Actually this may be too fancy for my simple usage. Anyway, I'll try out those options.

You’re welcome. I was trying to demonstrate a bit what might go into defining a fully-fledged iterator, with size_hint and some extra iterator-related traits.. And I wanted to demonstrate how an iterator could be created by hand here.

The most simple usage would just use one of my first two code sections, both similar to the previous answer. Stability guarantees only really play a role if you’re exposing the IntoIterator implementation publically across crate boundaries. (And even then, it probably only really starts to matter in a public crate and when you’re getting closer to a ≥1.0 release.)