Is it possible to implement an iterator with borrowed items?

Question

I am implementing a cursor over space grids, e.g. for a space [2, 2] the cursor should visit [0, 0], [1, 0], [0, 1], [1, 1] respectively. I have the code written below, but when I use for cursor in SpaceCursor::<2>::new(&[2, 2]), I noticed the cursor is not borrowed, but copied. Since the cursor will always within the SpaceCursor lifetime, I am wondering if I could have its type &[i32; 2] rather than [i32; 2]?

struct SpaceCursor<const D: usize> {
    cursor: [i32; D],
    boundary: [usize; D],
}

impl<const D: usize> SpaceCursor<D> {
    pub fn new(boundary: &[usize]) -> Self {
        let mut result = SpaceCursor::<D> {
            cursor: [0; D],
            boundary: boundary.try_into().expect("Bad boundary"),
        };
        if D >= 1 {
            result.cursor[0] = -1;
        }
        result
    }
}

impl<const D: usize> Iterator for SpaceCursor<D> {
    type Item = [i32; D];
    fn next(&mut self) -> Option<Self::Item> {
        let mut index = 0;
        while index < D {
            self.cursor[index] += 1;
            if self.cursor[index] < self.boundary[index] as i32 {
                break;
            }
            index += 1;
        }
        if index == D {
            None
        } else {
            for i in 0..index {
                self.cursor[i] = 0;
            }
            Some(self.cursor)
        }
    }
}

Answer 1

If you need an iterator to yield references then the iterator itself must hold a reference to the underlying data. This is due to the design of the Iterator trait:

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

When implementing Iterator where Item is a reference, you would need to give it a lifetime. But you need to pick just one lifetime which then must be valid for all items, and that lifetime must outlive the iterator. This only works if all of the items are already held somewhere in memory and will live longer than the time that the iterator is being used.

In Rust 1.65 this will (sort of) change. A new feature, generic associated types (GATs), will be available in stable, which will allow you to define a "streaming" iterator like this:

trait StreamingIterator {
    type Item<'a> where Self: 'a;
    fn stream_next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

The difference here is that the lifetime 'a is instantiated every call to stream_next and therefore can be different each time. The caller also gets to choose how long they want to keep the reference for and is only limited by the mutable borrow of the streaming iterator itself. The mutability also means you can only borrow one item at a time, so you couldn't do things like collect them into a Vec without cloning them.

Your iterator could be ported like this:

impl<const D: usize> StreamingIterator for SpaceCursor<D> {
    type Item<'a> = &'a [i32; D];
    fn stream_next<'a>(&'a mut self) -> Option<Self::Item<'a>> {
        let mut index = 0;
        while index < D {
            self.cursor[index] += 1;
            if self.cursor[index] < self.boundary[index] as i32 {
                break;
            }
            index += 1;
        }
        if index == D {
            None
        } else {
            for i in 0..index {
                self.cursor[i] = 0;
            }
            Some(&self.cursor)
        }
    }
}

Note that the "limitation" of only being able to borrow one item at a time, is really critical to this working, because you're overwriting the cursor value. This also should be another hint for why this couldn't have worked with the non-streaming Iterator trait.

Since StreamingIterator is not a built-in trait, there is no syntactic support for it in loops, so you must use it explicitly:

let data = vec![1,3,7,9];
let mut cursor = SpaceCursor::<4>::new(&data);

while let Some(i) = cursor.stream_next() {
    println!("{i:?}"); 
}

You can try this now in Rust 1.64 beta, in nightly, or wait about 2 weeks for Rust 1.65.