[Pre-RFC] Make Peekable trait for Iterator

[ZerothLaw]

Currently, Peekable is a struct returned by Iterator.peekable(), which implements Iterator, ExactSizeIterator, Clone, Debug, and FusedIterator.

Implementations of Iterator should be able to provide their own Peekable implementation, especially in the case of streams.

I’m not sure what else needs to be stated here, so please, provide your feedback!

[cuviper]

Sounds nice, but can you sketch out the implementation without any breaking changes?

[ZerothLaw]

I’ll make an attempt either tonight or tomorrow.

[oooutlk]

Should an std::Iterator always be Peekable? That is the reason I gave up impl std::Iterator for a depth-first-search iterator on a tree

[scottmcm]

Should an std::Iterator always be Peekable ?

No, because that has a space cost even in places that don’t need it.

(I do like the idea of Peekable being like Fused, though, and being free for many cases.)

[Nemo157]

@oooutlk your issue there is that you want a “streaming iterator” that can yield borrows from the source object, i.e.

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

Because of the lifetime there would be no way to have a peekable adaptor for this (along with others that require multiple items at the same time like collect or max), so it could make more sense to have these as additional traits that a streaming iterator could implement if it wanted.

As far as I know this trait is just blocked on generic associated types, so maybe at some point in 2019 we could get a prototype to play with.

[ZerothLaw]

Quick question: what form should the sketched implementation look like?

[cuviper]

We currently have two things that are stable interfaces:

• Iterator's method fn peekable(self) -> Peekable<Self>
• struct Peekable itself with a peek method and various trait implementations

So I’m primarily interested in what changes would need to be made to those, if any. If they do need to change, we need to carefully justify the compatibility of those changes.

Then you’re proposing a new trait, so what might that trait look like, and how would it be used?

Maybe the current interfaces don’t need to change at all. The new trait might just be something that struct Peekable uses to specialize its implementation, if we can make that work.

[ZerothLaw]

Yes, I was thinking of a trait that Peekable would implement (also a handy implementation reference) so that people can implement their own peekable iterator adapters. I looked at the source - and the implementation body of Peekable is easily converted to an impl<I: Iterator> PeekableIterator body.

I’ll download the relevant source file and then post a gist with the sketch.

[ZerothLaw]

So a small sketch: https://gist.github.com/ZerothLaw/77a3f185ec4bd963b878300b5f4b51ad

Basically, turn the struct impl into a trait impl. Then the struct works the same, especially throughout the parsing code.

[cuviper]

pub trait PeekableIterator<I: Iterator>: Iterator {
	fn peek(&mut self) -> Option<&I::Item>;
}

I don’t think this needs to be parameterized on I at all. What would something like slice::Iter even put there? The implementer already must be an Iterator itself, so just return Option<&Self::Item>.

On struct Peekable, we still need the inherent (non-trait) method, otherwise you remove the ability to call peek() without importing the new trait. But we can implement the trait method by calling the inherent method, or vice versa.

Later we can specialize Peekable<I> where I: PeekableIterator such that it doesn’t need to use its own peeked field at all, just forward to I::peek(). I don’t think it’s possible to eliminate the field, but it can be ignored in this case.

We might also want a trait for peek_back(), and then it’s possible to have something like:

impl<T> PeekableIterator for Rev<I>
    where I: DoubleEndedPeekableIterator

But maybe I’m over-thinking it.

[ZerothLaw]

Good points! Should I start working on the RFC then?

And yes, in my use case where I needed peekaboo, I also implemented a prev_token. See here: https://github.com/ZerothLaw/prattle-rs/blob/master/src/lexer.rs

That’s why I wanted to see if there was a trait, and saw there wasn’t. But yeah, peeking backwards and forwards can be useful, specifically with parsers.

That’s where Peekable is used a lot in the rustc code, is the macro and other assorted parsing code.

[oooutlk]

Lifetime is indeed an issue here. But the more interesting concern is what a peekable DFS-like tree iterator should be.

In my project, there are more operations other than getting next() node, such as going back to_parent(), skipping to_sib() node and revisit() current node, which changes the next node in normal DFS.

But std::iter::Peekable only knows the next() method, having no way of invalidating the prefetched item and trying to fetch the correct one brought out by to_parent()/to_sib()/revisit(), etc. It is not very useful in this case.

[CAD97]

Related: https://docs.rs/itertools/0.7.8/itertools/trait.PeekingNext.html (loosely)

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.