Trait for peekable iterators

libs
1

There's some useful methods on core::iter::Peekable, but those require making an adapter around your trait and then you can't ever get the original iterator back. Since many iterators could peek at their next element, it seems to me like it would be useful to make a trait that allows calling those methods without needing to use the wrapper.

I envision the trait looking pretty similar to the current Peekable struct, minus the methods that require mutating (peek_mut, next_if_map, next_if_map_mut):

trait PeekableIterator: Iterator {
     // Required method
     fn peek(&mut self) -> Option<&Self::Item>;

    // Optional methods
    pub fn next_if(
        &mut self,
        func: impl FnOnce(&Self::Item) -> bool,
    ) -> Option<<I as Iterator>::Item> { ... }

    fn next_if_eq(&mut self, expected: &Self::Item) -> Option<Self::Item>
    where
        Self::Item: PartialEq<Self::Item>,
    { ... }
}

I think most base iterators in the stdlib would be able to implement this, and some combinators would be able to implement this if the iterator(s) they wrap do (the biggest exception would be anything Iterator::map-like, since the function can't be called multiple times and there's no space to store the mapped value).

The current Peekable iterator would also implement this trait but otherwise be unchanged by this PR (it keeps inherent methods . I envision it having a similar status to the Fuse type and the FusedIterator trait, where it exists as a wrapper to make a normally-non-peekable iterator implement PeekableIterator, but also with the mutating methods.

The remaining methods I didn't include from Peekable could probably be put in a PeekableMutIterator trait, but imo that can be a future item if there's demand, since I've never needed to use any of those.

2 Likes
2

good idea, which is why we already made some progress on it

5 Likes
3

It does also seem like the current Peekable struct could pretty safely expose into_inner or into_parts to get the original iterator back out.

1 Like
4
4 Likes
5

Ha, two for two. I'll try to remember to search first next time!

6

Unfortunately most stdlib iterators cannot satisfy this signature.

For example consider std::slice::Iter: you can trivially peek it by cloning it and calling next, so it seems it might implement PeekableIterator. However with this approach you'll get a Option<Self::Item> (i.e. Option<&T>), and not a Option<&Self::Item> (i.e. Option<&&T>). Since the &T references are produced while iterating and don't exist somewhere in memory before that moment you cannot return a reference to them (i.e. the &&T).

The PeekableIterator proposed here instead doesn't have this issue, because it has a peek_with method taking a closure instead. This allows to materialize the Self::Item on the stack and call the closure with a borrow of it.

1 Like
7

This is one of the best arguments I've seen for separating the concepts of a shared reference and of a shared borrow (and I was already of the opinion that such a separation would be a good idea). In current Rust, the only way to do a shared borrow is to create a shared reference. However, it would in theory also be possible to do a shared borrow by value, i.e. the shared borrow is a copy of the bits of the thing that is being borrowed, but only allows operations on them that don't care about which memory address those bits are stored at. This is very similar to a shared reference (in particular, it has identical lifetime properties and supports most of the same operations, although it wouldn't work in FFI or for interior mutation).

In this case, you can't return a shared reference to a shared reference to T (which is not equivalent to a shared reference to T), but you could return a shared borrow of a shared reference to T (which is equivalent to a shared reference to T, and even allows interior mutation of the pointed-to T). It's interesting seeing an API that could be written with shared borrows (the signature would be fn peek(&mut self) -> Option<SharedBorrow<Self::Item>>) but can't be written with shared references.

The main problems with doing this are backwards compatibility, and syntax (because now you have two different types which both want to be called &T). Unfortunately, Rust picked the shared reference for the &T name, but most existing uses of &T only need a shared borrow, so it's hard to see how you could split the types nowadays.

1 Like
8

This has the very big downside of prohibiting any type with internal mutability.

Not to mention it would be quite inefficient to always copy around that value. References are much more efficient when the pointed value is "big" (e.g. compare passing a shared borrow of [u8; 1024] to passing a &[u8; 1024]!).