Implementing a replayable iterator

help
1

I ran into an interesting issue the other day and have been struggling to find a neat solution.

I have a type (let's call it Generator). It implements IntoIterator, but only for Generator, not for &Generator.

Now I need to use it somewhere that requires the iterator to be reusable, with the requirement that &T implements IntoIterator (specifically, the HRTB for<'a> &'a T: IntoIterator<Item = &'a I>).

To solve this, I want to create a wrapper that stores all encountered values and replays them, if no stored value is available, the next item from the real iterator is fetched.

However, I run into a lot of issues with shared/interior mutability and references to potentially moving memory addresses.

Here's the pseudoish-code idea:

struct BufferingIntoIterator<T>
where T: IntoIterator
{
    it: T::IntoIter,
    buffer: ???
}

struct BufferingIterator<T>
where T: IntoIterator
{
    it: &T::IntoITer,
    buffer: &???,
    index: usize,
}

impl<T> IntoIterator for &BufferingIterator<T> {
    type Item = &T::Item;
    type IntoITer = BufferingIterator<T>;

    fn into_iter(self) -> Self::IntoIter {
        BufferingIterator::new(self)
    }
}

impl<T> Iterator for BufferingIterator<T> {
    type Item = &T::Item;

    fn next(&mut self) -> Option<Self::Item> {
          if index == buffer.len() {
              if let Some(next) = self.it.next() {
                  self.buffer.push(next);
              } else {
                  return None;
              }
          }
          let item = buffer.get(index);
          self.index += 1;
          item
    }
}

I've tried with the buffer as Rc<RefCell<Vec<T::Item>>> but that both gives me a lifetime issue because the item is tied to the lifetime of the RefMut/Ref I get when borrowing the RefCell and even then, the Vec would move things around in memory when it runs out of capacity. I could solve the latter by storing Box<T> in the Vec, but then the lifetime is still tied to the Ref inside next().

Solutions should be lazy and, preferably, succinct, safe, and without dependencies (i.e., using an arena is undesirable). (I'm not sure you can actually hit all of those, so see it as a challenge :D)

In the real situation where this arose, I solved it by just collecting into a Vec and then passing that, but for a generic solution, I don't want it to be eager because that might be unnecessary and won't work with infinite iterators.

Here's a Playground that you can "solve"

2
  1. If you also want &T to implement IntoIterator, well, you'd have to implement it for that type.
  2. If your iterator can implement ExactSizeIterator, you can implement it for the iterator and then pass a cycled iterator to the consumer, which then can iterator.take(iterator.len()) and do that repeatedly.

As for your example use case, closing the iterable would be the simplest solution:

3

ExactSizeIterator won't work for infinite iterators, and cloning is cheating :slight_smile: (not everything can be expected to be cloneable).

cycle() additionally requires the iterable to implement Clone.

I specifically want a type that can wrap (i.e. take ownership of) any IntoIterable and implement IntoIterable for &Wrapper - that's the challenge :slight_smile:

4

you have written

fn iterate_twice<T, I>(it: T)
where
    for<'a> &'a I: IntoIterator<Item = &'a u32>,
{

i believe you meant

fn iterate_twice<I>(it: I)
where
    for<'a> &'a I: IntoIterator<Item = &'a u32>,
{

?

i have a solution, but it is pretty horrible, using a linked list :

it is slightly better with nightly features

to go further you would want something like FrozenVec in elsa::vec - Rust

2 Likes
5

It took me a few rereads to grasp, but I don't think it's that horrible :stuck_out_tongue:

Nice work.

6

I came up with a very similar solution as @Morgane55440 , but with a few different tradeoffs in the implementation:

struct BufferedIter<I:Iterator, const N:usize> {
    iter: RefCell<I>,
    buffer: Page<Option<I::Item>, N>
}

impl<'a, I:Iterator, const N:usize> IntoIterator for &'a BufferedIter<I,N> {
    type IntoIter = Cursor<'a,I,N>;
    type Item = &'a I::Item;
    fn into_iter(self)->Self::IntoIter {
        Cursor { iter: &self.iter, next: 0, page: &self.buffer }
    }
}

struct Cursor<'a,I:Iterator, const N:usize> {
    iter: &'a RefCell<I>,
    next: usize,
    page: &'a Page<Option<I::Item>, N>
}

impl<'a,I:Iterator,const N:usize> Iterator for Cursor<'a,I,N> {
    type Item = &'a I::Item;
    fn next(&mut self)->Option<Self::Item> {
        if self.next == N {
            self.next = 0;
            self.page = self.page.next_page();
        }
        let out = self.page.data[self.next]
            .get_or_init(|| self.iter.borrow_mut().next());
        self.next += 1;
        out.as_ref()
    }
}

struct Page<T, const N:usize> {
    data: [OnceCell<T>; N],
    next: OnceCell<Box<Self>>,
}

impl<T, const N:usize> Page<T,N> {
    fn new()->Self {
        Page {
            data: [const { OnceCell::new() }; N],
            next: Default::default()
        }
    }
    
    fn next_page(&self)->&Self {
        self.next.get_or_init(|| Box::new(Self::new()))
    }
}
1 Like