I'm trying to learn Rust. A pattern that I've used in other languages is to wrap an iterator with a data structure that allows me to call .peek() or .next(). The result looks like an iterator, except that it can be peeked at any number of times before moving on. (An example where this pattern is useful is in a parser.) Here is a partial failed attempt to do something similar in Rust.
pub struct PeekableIter<'a, T> {
head: &'a Option<T>,
tail: &'a mut Box<dyn Iterator<Item = T>>,
}
impl<'a, T> PeekableIter<'a, T> {
pub fn next (&mut self) -> &Option<T> {
let value = self.head;
self.head = &self.tail.next();
value
}
pub fn peek (&mut self) -> &Option<T> {
self.head
}
}
This doesn't work. The reason why it doesn't work is that the line self.head = &self.tail.next(); is trying to borrow the value for as long as the iterator that self.tail points at exists. However that iterator borrows that value from its underlying collection for a shorter lifetime. Is there any way to indicate that I only need self.head to be borrowed for as long as the underlying iterator borrows it? (I would also need to indicate this shorter lifetime in peek.)
(Of course I can successfully borrow it for the time of the function call, but that doesn't leave the value available for peek to get later.)
Alternately I can try to .copy() the value. However Iterator<Item = T> doesn't implement .copy(). (That's also ignoring efficiency.)
Is there any approach to do this pattern in Rust, or it is a design pattern that simply can't work with the borrow checker?
(This is partial because I didn't try to implement new. I was going to do that after next, then write some tests, but I failed to get next to compile.)
First, the short answer is that this pattern—as written—isn’t going to work in Rust the way it would in a garbage-collected or reference-counted language. In Rust, once you call self.tail.next(), the returned Option<T> is only guaranteed to live until the end of that statement unless you explicitly store its T somewhere owned. You can’t keep taking references out of thin air once the original item is gone or has changed owners.
This is fundamentally why &self.tail.next() can’t be stored in head: the item from the iterator is ephemeral unless you take ownership of it (by value). Storing a reference requires that the thing you’re referencing live long enough. In this case, it doesn’t.
If you look at the standard library’s Peekable, it works by storing the peeked item by value (in an Option<T>). That is, when you ask for the next item, it moves ownership from the underlying iterator into your Peekable’s internal buffer. Then, when you ask for the item via peek(), the Peekable can return Option<&T> by referencing the owned buffer:
use std::iter::Peekable;
let iter = vec![1, 2, 3].into_iter().peekable();
Under the hood, it’s doing something like:
pub struct MyPeekable<I>
where
I: Iterator,
{
iter: I,
peeked: Option<I::Item>,
}
impl<I> MyPeekable<I>
where
I: Iterator,
{
pub fn new(iter: I) -> Self {
MyPeekable { iter, peeked: None }
}
// This is how the std lib does it (simplified):
pub fn peek(&mut self) -> Option<&I::Item> {
if self.peeked.is_none() {
self.peeked = self.iter.next();
}
self.peeked.as_ref()
}
pub fn next(&mut self) -> Option<I::Item> {
if self.peeked.is_some() {
return self.peeked.take();
}
self.iter.next()
}
}
When you call next(), if peeked already has something, we return that. Otherwise, we pull the next item from iter. Importantly, the item belongs to MyPeekable<I> (which owns it), so returning a reference inside peek() is trivially safe as long as MyPeekable<I> is alive.
Your original attempt tries to store:
pub struct PeekableIter<'a, T> {
head: &'a Option<T>,
tail: &'a mut Box<dyn Iterator<Item = T>>,
}
But any item that comes out of tail.next() is only valid until the end of that call (unless we store it in some owned variable). You’re trying to store a reference to something whose lifetime is not guaranteed to match the PeekableIter struct’s lifetime. In fact, the item’s lifetime is typically “just the expression” that calls tail.next()—the compiler sees that you want to keep borrowing it afterward and complains.
Rust generally requires that either:
T in your struct, e.g. Option<T>).&T (e.g. slice::Iter). In that scenario, the underlying data is in memory your struct owns, so it’s safe to keep those references.But if dyn Iterator<Item = T> is pulling items from who-knows-where, the only safe way in generic Rust is to own the items that come out if you need them to live across method calls.
It’s not that the pattern of peeking is impossible—it’s that you can’t do it by storing references into ephemeral iterator items. You can replicate a peekable iterator by storing ownership of the item. Essentially, the solution is:
Option<T> for the “peeked” item..peek(), fill that Option<T> if it’s empty, then return an Option<&T> reference to it..next(), if you already peeked, you return the owned item from that Option<T> and set it back to None; otherwise, you just grab a new one from the underlying iterator.The std library Peekable does exactly that. If you really must keep references, then you need your underlying data to be stable in memory for the entire lifetime of your struct (like referencing a slice or some other structure that’s guaranteed to outlive the iterator). But as soon as you try to do this with a generic Iterator<Item = T> that yields owned items, you must store those items by value to continue peeking them later.
Hence, in most Rust code, one simply uses:
let mut peekable = some_iterator.peekable();
if let Some(x) = peekable.peek() {
println!("Next element is: {}", x);
}
and the standard library takes care of the mechanics. If you want a custom approach, replicate the standard library’s pattern of owning the peeked value instead of borrowing it.