Why does std::iter::Peekable::peek mutably borrow the self argument?

Question

I am struggling to understand why the peek() method is borrowing the self argument mutably.

The documentation says:

"Returns a reference to the next() value without advancing the iterator."

Since it is not advancing the iterator, what is the point behind borrowing the argument as mutable?

I looked at the implementation of peek() and noticed it is calling a next() method.

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn peek(&mut self) -> Option<&I::Item> {
    let iter = &mut self.iter;
    self.peeked.get_or_insert_with(|| iter.next()).as_ref()
}

Is it because of the use of the next() method, the peek() method is designed to borrow mutably or is there another semantic behind the peek() method that really requires the mutable borrow?

In other words, what is it that gets mutated when the peek() method is called?

Answer 1

As you have already done, let's look at its source, which reveals a little about how it works internally:

pub struct Peekable<I: Iterator> {
    iter: I,
    /// Remember a peeked value, even if it was None.
    peeked: Option<Option<I::Item>>,
}

Together with its implementation for next():

impl<I: Iterator> Iterator for Peekable<I> {
    // ...

    fn next(&mut self) -> Option<I::Item> {
        match self.peeked.take() {
            Some(v) => v,
            None => self.iter.next(),
        }
    }

    // ...
}

and it's implementation for peek():

impl<I: Iterator> Peekable<I> {
    // ...

    pub fn peek(&mut self) -> Option<&I::Item> {
        let iter = &mut self.iter;
        self.peeked.get_or_insert_with(|| iter.next()).as_ref()
    }

    // ...
}

Peek wraps an existing iterator. And existing iterators are not peekable.

So what peek does, is:

• on peek():
  • take the next() item from the wrapped iterator and store it in self.peeked (if self.peeked does not yet contain the next item already)
  • return a reference to the peeked item
• on next():
  • see if we currently have a self.peeked item
  • if yes, return that one
  • if no, take the next() item from the underlaying iterator.

So as you already realized, the peek() action needs &mut self because it might have to generate the next peeked item by calling next() on the underlying iterator.

So here is the reason, if you look at it from a more abstract point of view: The next item might not even exist yet. So peeking might involve actually generating that next item, which is definitely a mutating action on the underlying iterator.

Not all iterators are over arrays/slices where the items already exist; an iterator might by anything that generates a number of items, including lazy generators that only create said items as they are asked for it.

Could they have implemented it differently?

Yes, there absolutely is the possibility to do it differently. They could have next()ed the underlying iterator during new(). Then, when someone calls next() on the Peekable, it could return the currently peeked value and query the next one right away. Then, peeking would have been a &self method.

Why they went that way is unclear, but most certainly to keep the iterator as lazy as possible. Lazy iterators are a good thing in most cases.

---

That said, here is a proof of concept how a prefetching peekable iterator could be implemented that doesn't require &mut for peek():

pub struct PrefetchingPeekingIterator<I: Iterator> {
    iter: I,
    next_item: Option<I::Item>,
}

impl<I: Iterator> PrefetchingPeekingIterator<I> {
    fn new(mut iter: I) -> Self {
        let next_item = iter.next();
        Self { iter, next_item }
    }

    fn peek(&self) -> Option<&I::Item> {
        self.next_item.as_ref()
    }
}

impl<I: Iterator> Iterator for PrefetchingPeekingIterator<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        std::mem::replace(&mut self.next_item, self.iter.next())
    }
}

fn main() {
    let mut range = PrefetchingPeekingIterator::new(1..10);
    dbg!(range.next().unwrap());
    dbg!(range.peek().unwrap());
    dbg!(range.next().unwrap());
    dbg!(range.peek().unwrap());
    dbg!(range.next().unwrap());
    dbg!(range.peek().unwrap());
}

[src/main.rs:27] range.next().unwrap() = 1
[src/main.rs:28] range.peek().unwrap() = 2
[src/main.rs:29] range.next().unwrap() = 2
[src/main.rs:30] range.peek().unwrap() = 3
[src/main.rs:31] range.next().unwrap() = 3
[src/main.rs:32] range.peek().unwrap() = 4