rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
98.49k stars 12.73k forks source link

Implement a Peekable trait for Chars, CharIndices, slice::Iter etc. #33881

Closed sandeep-datta closed 6 years ago

sandeep-datta commented 8 years ago

If you want to peek an iterator right now then you have do something on the following lines...

let chars = "abc".chars();
let mut peekable = chars.peekable();
println!("{:?}", peekable.peek());

This is unnecessarily complicated and unergonomic in the case of iterators like Chars, CharIndices, slice::Iter etc. IMO it would be better to define a Peekable trait as follows...

trait Peekable : Iterator {
    fn peek(&mut self) -> Option<&Self::Item>;
}

and using this iterator as a bound on the aforementioned concrete iterators (perhaps replacing the Iterator bound). Doing so will not only improve the ergonomics for the library user but also help in providing a less roundabout implementation for the peek() method. Iterators which cannot implement Peekable directly should continue to use the Peekable adapter.

This will change the first snippet as follows...

let chars = "abc".chars();
println!("{:?}", chars.peek());
Stebalien commented 8 years ago

Nit: It would probably be called Peek, not Peekable.

Note: Peekable could specialize on Peek (lower overhead).

sandeep-datta commented 8 years ago

@Stebalien thanks for your comment. I am okay with Peek as the trait name. I am afraid I don't know enough rust yet to understand what you mean by specialize here? Does rust have template (partial) specialization like C++?

Stebalien commented 8 years ago

@sandeep-datta Currently, Peekable introduces some runtime overhead (it has to check if something has been peeked and has to store peeked elements). Adding a Peek trait would allow the Peekable struct forward the peek call to the inner iterator if it implements peek instead of implementing the peek logic itself.

sandeep-datta commented 8 years ago

@Stebalien going through the list of iterators it appears that any trait which derives from the Iterator trait ends with an Iterator in its name. Examples: DoubleEndedIterator, ExactSizeIterator. I propose renaming Peek to PeekableIterator. What do you say?

Stebalien commented 8 years ago

Sigh... You're right. This is an iterator thing from the days before the convention. For everything else, traits are named after their primary function (Write, Read, From, Into, AsRef, Borrow, ...).

sandeep-datta commented 8 years ago

Okay so I tried to implement PeekableIterator for Chars but it seems the best I could do was ...

impl<'a> PeekableIterator for Chars<'a> {
    #[inline]
    fn peek(&self) -> Option<Self::Item> {
        self.clone().next()
    } 
}

since I do not want to store the peeked valued in an extra field inside Chars. Doing so would replicate what the Peekable struct already does and also violate the pay as you go principle for people who are not interested in peeking an iterator.

I think Peekable may the best we can do for now, at least for iterators like Chars, CharIndices. These iterators do not simply return a value from an underlying backing store they need to compute the next() value hence you may need to clone the inferior iterator. I think it is better that the users do this explicitly.

However PeekableIterator may still be useful for things like slices.

sandeep-datta commented 8 years ago

Okay revisiting this topic I feel PeakableIterator on Chars still makes sense because Peekable takes ownership of the inferior iterator and hides it. There is no way of accessing its as_str() method.

dtolnay commented 6 years ago

I think the idea of a peek trait is super promising. Thanks for filing this! Other iterators have started to handle peek in an ad-hoc way, for example linked_list::IterMut::peek_next. It would be great to generalize these and make them usable in a generic context using a trait.

There are a lot of difficult design tradeoffs though and I am not confident that we will be able to arrive at a consensus on a design here, so I would prefer to see this addressed in an RFC.

aslilac commented 2 years ago

has there been any further discussion on this? this'd be super handy

bluebear94 commented 1 year ago

This would also allow using the peek methods on Chars while still being able to call as_str() on the iterator at the end.