Own implementation of generic (lending-)iterator

Hello, rustaceans,

i have been trying to implement my own iterator trait.

trait Iterator<ItemType> {
    fn next(&mut self) -> Option<ItemType>;
    fn foreach<FunctionType: FnMut(ItemType) -> ()>(&mut self, mut function: FunctionType) {
        while let Some(item) = self.next() {
            function(item)
        }
    }
}

Explanation:
I know, that the std has one, but because of the association type, i would not be able to implement the iterator trait multiple times with different return types. For example, if i have iterator structs, that have a reference for a vector (copying or consuming the vector can be inefficient or not needed), i can implement the iterator trait twice for the IterMut: one returning immutable references and one mutable ones (and if ItemType: Clone, then also the item itself).

pub struct IterRef<'a, Type> {
    reference: &'a Vec<Type>,
    index: usize,
}
pub struct IterMut<'a, Type> {
    reference: &'a mut Vec<Type>,
    index: usize,
}
impl<'a, Type> Iterator<&'a Type> for IterRef<'a, Type> {
    fn next(&mut self) -> Option<&'a Type> {
        let reference = self.reference.get(self.index);
        self.index += 1;
        return reference;
    }
}
impl<'a, Type> Iterator<&'a Type> for IterMut<'a, Type> {
    fn next(&mut self) -> Option<&'a Type> {
        let reference: Option<&Type> = self.reference.get(self.index);
        self.index += 1;
        return reference; //compiler-error: lifetime may not live long enough
    }
}
impl<'a, Type> Iterator<&'a mut Type> for IterMut<'a, Type> {
    fn next(&mut self) -> Option<&'a mut Type> {
        let reference: Option<&mut Type> = self.reference.get_mut(self.index);
        self.index += 1;
        return reference; //compiler-error: lifetime may not live long enough
    }
}

But this implementations have two errors: the returned reference from the mutable iterator may not outlive the iterator. (And i know about the integer overflow, its an example code.)

From my lifetime understanding, the immutable iterator is compiling, as the all references are immutable and therefor the vector and its items are never reallocated. The mutable iterator on the other side is capable of changing the vector and the items, so references returned from the iterator should be dropped befor the next iter.next() is called. That is my understanding of the compiler error.

To fix the errors i have then added a lifetime for the &'a mut self reference in the next function:

trait Iterator<'a, ItemType> {
    fn next(&'a mut self) -> Option<ItemType>;
    ...
}
impl<'a, Type> Iterator<'a, &'a Type> for IterMut<'a, Type> {
    fn next(&'a mut self) -> Option<&'a Type> {...}
}
impl<'a, Type> Iterator<'a, &'a mut Type> for IterMut<'a, Type> {
    fn next(&'a mut self) -> Option<&'a mut Type> {...}
}

The compiler complains now, that in the foreach function the &mut self dont outlives the 'a lifetime requiered by the next function. I dont understand this exactly, but it may be required by some outer code / lifetimes:

Error:
4 |         while let Some(item) = self.next() {
  |                                ^^^^^^^^^^^ argument requires that `'1` must outlive `'a`
Fix:
    fn foreach<FunctionType: FnMut(ItemType) -> ()>(&'a mut self, mut function: FunctionType) {

But one error is still present:

  |                -- lifetime `'a` defined here
...
4 |         while let Some(item) = self.next() {
  |                                ^^^^^^^^^^^
  |                                |
  |                                `*self` was mutably borrowed here in the previous iteration of the loop
  |                                argument requires that `*self` is borrowed for `'a`

and i could'nt find any solution for this one. I know about loop unrolling and tried therefor to wrap the while content in {...} brackets to drop the returned items. I also tried just to call self.next() multiple times in a row (and wrapping in {...}), nothing helped. I went so far introducing new lifetimes and subtyping them (and fn next<'b>(&'b mut self) -> Option<ItemType> is the same as fn next(&mut self) -> Option<ItemType>, if i introduce the subtyping i get the first or the third error depending on the bounds).

Summery:
I would like to have an iterator trait, which i can implement multiple times with different ItemTypes returned for the same struct (i am using them in my code alot and creating a struct for each ItemType necessary, and macros will make the code very complex as i would have to use them a lot, including inside generics). Implementing such iterator produces one of two errors:

  • the returned reference dont outlive the iterator, or
  • the next() function cannot be called more than once.

I would like to ask, if the goal i am aiming for is achivable in rust (may be with nightly?) by correcting my lifetimes / other code, if i should use other code structure or is this not achivable in rust at all?

Thanks in advantage for your time and your help.

There's a few things going on. A big one is that for a lending iterator, you need a contract that says the borrowed items you hand out must be dropped before the next call to next. You do that with a signature like so:

fn next(&mut self) -> Option<&mut X>; // NOT &'a mut x

The iterators in std return specific lifetimes because they are non-lending. By the standard Iterator trait, items must be able to outlive the consumption of the entire iterator -- you can hold all the items at once, even once the iterator drops. That's not possible with a lending iterator -- for example it'd be unsound since your data structures hold on to the same &mut _s they're handing out.[1]

The way a typical lending iterator design looks is to use a GAT for this...

trait LendingIterator {
    type Item<'a> where Self: 'a; // e.g. &'a mut X
    fn next(&mut self) -> Option<Self::Item<'_>>;
}

...but you want to support multiple implementations, each with it's distinct Item GAT. Rust doesn't have generic type constructors,[2] so you need some sort of indirection here -- a representative type associated with a GAT (via helper trait), which you can use as a type parameter to your iterator trait.

trait IteratorLoan {
    type Item<'a> where Self: 'a;
}

trait Iterator<BorrowOf: IteratorLoan> {
    fn next(&mut self) -> Option<BorrowOf::Item<'_>>;
}

And how about some helpers for common cases...

struct RefOf<T: ?Sized>(PhantomData<T>);
struct MutOf<T: ?Sized>(PhantomData<T>);

impl<T: ?Sized> IteratorLoan for RefOf<T> {
    type Item<'a> = &'a T where Self: 'a;
}

impl<T: ?Sized> IteratorLoan for MutOf<T> {
    type Item<'a> = &'a mut T where Self: 'a;
}

And finally let's take a look a foreach. You need to be able to pass it an Item<'i> for some arbitrarily short lifetime 'i that's created in the method of a body. That's too short for the caller to name. The solution is to take a closure which accepts any lifetime by using a higher-ranked trait bound.

    fn foreach<F: FnMut(BorrowOf::Item<'_>)>(&mut self, mut function: F) {
    // Short for: `F: for<'any> FnMut(BorrowOf::Item<'any>)`

And here it is all put together.

(I didn't excercise it beyond what you see, so there's possibly still some usability issues -- combining GATs and HRTB[3] still has some rough edges.)


  1. In std, &mut iterators modify themselves in such a way that this doesn't happen, e.g. splitting a &mut [T] ↩︎

  2. no direct support for a GAT as a generic parameter of your trait ↩︎

  3. higher-ranked trait bounds ↩︎

2 Likes

Let me circle back to your errors too.

(Playground.)

It's possible you don't actually want a lending iterator, and this is just an issue with how you've implemented the example. First let's explain the error, and then see if we can fix them by making these iterators not loan.

The problem is that you can't get a &'long _ out from a &'short mut &'long mut _, because once the &'short mut "expires", both 'long references would be usable at the same time -- and &mut _ must be exclusive. (&'short mut &'long _ doesn't have this problem because you can just copy the shared &'long _ out.)

There's still a way forward though -- if you can get the &'a mut _ which you hold out from underneath &mut self temporarily, you can work with it directly, avoiding the nested &mut &mut situation. This is possible with slices, so let's change your data structures:

+// Only showing this one
 pub struct IterMut<'a, Type> {
+    reference: &'a mut [T],
-    reference: &'a mut Vec<Type>,
-    index: usize,
}

We'll shrink the slice as we go to avoid the aliasing problem of holding on to a &'a mut _ which we can still reach, so we don't need the index anymore either. Then you can implement the iterator like so:

impl<'a, Type> Iterator<&'a mut Type> for IterMut<'a, Type> {
    fn next(&mut self) -> Option<&'a mut Type> {
        // Temororarily replace our slice with an empty one
        let reference = std::mem::take(&mut self.reference);
        // Split off the first item (or return `None` if there isn't one)
        let (item, rest) = reference.split_first_mut()?;
        // Replace the slice with the remaining items
        self.reference = rest;
        // And return the first item
        Some(item)
    }
}

The temporary replacement is possible because &mut [T] implements Default (you can conjure empty slice borrows out of nowhere, including &mut ones, because they don't actually alias any memory).

This is a common pattern for std-Iterators with Item = &mut _.

It all works out, so this is another possible solution depending on what you want to do.


I haven't covered the other error yet, but see you typing so let me post this now and see what you say :slight_smile:

2 Likes

Thank you for your fast replying!

After i red your solution i started implementing it im my own library to test if i have any problems that i cannot solve on my own. And, as long as i can see, my library compiles with the foreach and next functions. That were my biggest problem. So that took a little while to write the code.

The other functions (constructors, dereferer, etc.) i can implement by my own.

About the second solution (i just red it and didnt implement it), so i cant say now, if it will solve my way better. But the problem i have is, that the underlying sturcture is not necessary a vector. As a (mathematical) graph library the underlying type can range from solid structs to other "strange" structures, like (little bit of pseudo code):

struct boolean_relations
{
    first: option<address>,
    second: option<address>,
}

so iterating over them as slices wont work, i think.

And thank a lot again, you really helped my here out! :slightly_smiling_face: :+1:

1 Like

OK I wrote up the last one in the meanwhile :slight_smile:. TLDR, my first reply is a fix for this one.


When you add the lifetime to the trait, you're sort of trying to shove a GAT into the parameters and end up with a lending iterator again (the return type is a borrow of &mut self).

There's a lifetime red-flag here: You're implementations have &'a mut self (and &'a self), where Self contains 'a. You can loosen up the implementations to help with that one.

impl<'a: 's, 's, Type> Iterator<'s, &'s mut Type> for IterMut<'a, Type> {

The problem with foreach is that you need some form of HRTB, because this is a lending iterator pattern -- the lifetime has to end before the next loop iteration. But the named lifetime 'a must be longer than the function body. That's why you can only call next once in foreach, even with the looser implementations above.

So you want something like...

    fn foreach<FunctionType>(&'a mut self, mut function: FunctionType)
    where //                                ??? vvvvvvvvvvvvvvvvvvvvv
        for<'s where 'a: 's> Self: Iterator<'s, ItemTypeWithLifetimeS>,
        for<'s where 'a: 's> FunctionType: FnMut(Self::ItemTypeWithLifetimeS) -> (),

But there's no way to do that without refactoring; ItemType is a type parameter and not a type constructor (and there's no support for where clauses in for<...> binders either).

Basically by marrying 'a and ItemType you've locked yourself into only being able to "reason" about a single call, or such.

My first reply is one such refactor.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.