Implement two-way iterators and peekables #83
Conversation
Yeah, at some point I want to submit an RFC for that. It really feels like a missing API in Rust's iterators. It's also pretty surprising to me that In any case, I don't think it makes much sense to create traits for these things in Ropey itself. The point of traits in this case would be interoperability, and bespoke traits in Ropey doesn't achieve that. I think what probably makes the most sense is to implement |
| #[derive(Debug)] | ||
| enum Peeked<T> { | ||
| None, | ||
| Prev(Option<T>), // remember peeked value even if it was none | ||
| Next(Option<T>), | ||
| } | ||
|
|
||
| pub struct TwoWayPeekable<I> | ||
| where | ||
| I: TwoWayIterator, | ||
| I::Item: Copy, | ||
| { | ||
| itr: I, | ||
| peeked: Peeked<I::Item>, | ||
| } |
There was a problem hiding this comment.
If we're going to the trouble of storing peek values (rather than the simple "advance and then de-advance" approach discussed in #82), then instead of a single peeked field, I think we want both peeked_prev and peeked_next, both of which would be simple Options and would be maintained as the iterator progresses. And then the Peeked enum is unnecessary.
There was a problem hiding this comment.
Initially, that's what I did, but two options seemed redundant since, you can never have both of them be Some variant. Because if both of them are Some, that would mean, that iterator is before prev_peeked and after next_peeked at the same time
There was a problem hiding this comment.
I'm not sure I follow. I could be missing something, but isn't the idea that prev/next_peeked would simply store the value that peek_prev() and peek_next() would return? Or for that matter, what prev() and next() would return as well (since the only difference between them and the peek_* variants is whether the iterator gets advanced or not).
In other words, if we have the following rope, with the char iterator position represented with a vertical bar:
ab|cd
Then prev_peeked would contain Some('b') and next_peeked would contain Some('c').
There was a problem hiding this comment.
It's not caching what was returned by .next(), it is caching what was returned by .peek_next(), so that when we call .next(), we know that iterator is already advanced forward by the previous .peek_next() call, so instead of advancing it one more time, we returned the cached value, and set it to Peeked::None, so that next .next() call will just advance the iterator as normal. So if peeked == Peeked::Next('c'), it meens we already peeked at 'c' and iterator is now past it. But we still pretend that it is before it. This is the same way Peekable is implemented in std. Making it the way you described it would make it a lot more complicated, since we would need to keep track of where the iterator is after we moved it around for peeking.
Oops. I misremembered what Hmm. That makes me wonder if this functionality even belongs directly in Ropey, then. Maybe a separate crate that provides a I mean, I'm still happy to have |
Yeah, this whole thing is very generic and could be in a separate crate. (or the standard library?)
I agree. We can put the I think the best implementation for ropey would be if peek methods would actually get the value, but not advance the iterator. But that is not trivial to implement, and I don't have the knowledge to do that. If you think you might do that in the future, I can make a PR with the "placeholder" implementation |
|
I've been thinking about this more, and I'm actually thinking that maybe this functionality just doesn't belong directly in Ropey after all. The pattern in Ideally So as a compromise in the mean time, I think the best thing to do would be to add a peeking wrapper to Admittedly, this isn't ideal. But I think it's a reasonable compromise for the time being. |
Closes #82.
I decided to make a struct
TwoWayPeekablewhich will contain the iterator and the peeked value, similar tostd::iter::Peekable. This allows to eliminate code duplication and this way the peeking-related overhead will affect only those who need to peek. As a downside, this approach increases the API surface area. It introduces a new traitTwoWayIterator, which probably should be a standard library feature.I named the method that makes iterator peekable
.two_way_peekable(), because.peekable()would conflict withstd::iter::Iterator::peekable. Admittedly,two_way_peekableis not a very good name, so it probably should be changed, but I don't know to what. We could just name itpeekable, but that would be a breaking change, and would require a major version bump, so probably not worth it.