We currently have three main kinds of Iterators:
-
Iterator: Linearly consumes a “range” irreversibly -
DoubleEndedIterator: Linearly consumes a “range” irreversibly from both ends -
RandomAccessIterator: Yields elements from a range by index without consuming them
Iterator is great for for loops, and RandomAccessIterator is great for abstracting over indexable ranges of values. As far as I can tell, DoubleEndedIterator is basically just handy for consuming ranges in more elaborate ways; it’s primary use-case as far as I know is reversing a range.
However the restriction of consuming ranges irreversibly is often artificial. For a move_iter it is of course necessary, but for a range or ref-based iter or mut_iter, it is often trivial to reverse back to where you came from.
Cursors
Cursors allow seeking back and forth in a range without logically consuming the values of the range. MutCursors of course, by extension, provide methods for mutating the range. However, their precise implementation can take many forms.
Proposal 1: Cursors Are Iterators (Of All Kinds)
The perhaps most obvious option is to add Cursors as traits that extend Iterators. Minimally, we can introduce the following:
/// An iterator that supports revisiting old values. In contrast to a normal
/// `Iterator`, a `Cursor` is guaranteed to always yield None once it
/// has seeked past either end of its range.
/// However, one can always seek back into range by calling `next()`
/// or `prev()` when before or after the range, respectively.
/// When out of range, calling `next()` or `prev()` does not take
/// the head of the `Cursor` any further out of range than one "step".
/// Logically, a `Cursor`'s head always sits between two elements,
/// or on either end of the range.
trait Cursor<A>: Iterator<A> {
/// Advance the iterator backwards, and return the previous value.
/// Return `None` while the beginning is reached.
fn prev(&mut self) -> Option<A>;
}
/// A double-ended `Cursor`. In order to preserve the semantics of
/// a `DoubleEndedIterator`, from the perspective of each head of
/// the cursor, the other represents an "end" of the list,
/// and will return None whenever they overlap.
/// The heads of the cursor cannot seek past each other.
trait DoubleEndedCursor<A>: DoubledEndedIterator<A> + Cursor<A> {
/// Advance the back head of the Iterator backwards,
/// and return the previous value
fn prev_back(&mut self) -> Option<A>;
}
However one big usecase of Cursors is mutating, so we might also want:
/// A Cursor that can mutate its Range
trait MutableCursor<'a, A>: Cursor<&'a mut A> {
/// Insert an element into the range between the next element of the cursor
/// and itself
fn insert(&mut self, elem: A);
/// Remove the next element of the cursor, and return it or None if there
/// is no next element
fn pop(&mut self) -> Option<A>;
}
/// A DoubleEndedCursor that can mutate its Range
trait MutableDoubleEndedCursor<'a, A>: DoubleEndedCursor<&'a mut A> {
/// Insert an element into the range between the next element of the
/// back cursor, and itself.
fn insert_back(&mut self, elem: A);
/// Remove the next element of the of the back cursor, and return it,
/// or None if there is no next element. If the cursors overlap, this
/// does nothing.
fn pop_back(&mut self) -> Option<A>;
}
Most notable is that MutableCursor<A> is actually a Cursor<&mut A>. This seems necessary to correctly handle the desired usecase: collections. I might have messed up the type annotation here. I’m just writing this all out in discourse untested.
The Mutable variants are derived from the ListInsertion trait provided by DList. Interesting potential extensions I left out for simplicity, and to leave the core proposal minimal:
-
peek,peek_prev,peek_back, andpeek_prev_backare conceptually simple and handy -
update: can be emulated withpop(); push(new), or just abusing the fact that&mut Ais returned -
jump_to_frontandjump_to_backare worth considering, especially when you only have an iterator -
seek_with(fn)(and various directional variants) might be valuable extensions, although iterator adapters might handle this
If you’re wondering about the direction of insertion/deletion, it’s because it makes using Cursors to push/pop_front/back more natural. The operations also don’t move the cursors relative to their respective ends, which is nice. However, this direction means the iterators directly interfere with each other when adjacent, which is tricky and potentially confusing. The other direction of insertion/removal inverts these issues. It’s a toss-up IMO.
Regardless, I think this is probably the strongest proposal.
Proposal 2: Cursors Are Iterators (But Not DoubleEnded)
Basically, take Proposal 1 and ditch the DoubleEnded stuff. This removes the biggest source of issues/confusion when working with Cursors, but of course makes them less powerful. It also means that all doubled-ended structures, which are the primary candidates for Cursors, (e.g. DList) have to provide something different for Cursors anyway which sucks. Honestly, this is probably a worst-of-both-worlds compromise between Proposal 1 and Proposal 3.
However, I believe it leaves some mental headroom to add more functions like insert_before and remove_before to get finer control of mutation, which is cool.
Proposal 3: Cursors Are Their Own Thing
Simply make Cursors a distinct concept from Iterators. I have a PR in for doing exactly this on DList, which is what sparked this discussion. In this context, we are free to deviate from any iterator semantics. For the most part, the API looks a lot like Proposal 1. However, In my PR, I used this to have cursors heads point to elements, rather than between them.
This allows us to cleanly insert_left or insert_right, and pop_left or pop_right without interfering with what the Cursor is pointing at. However this makes being “off the ends” more of a special case conceptually, and leaves some room for ambiguity when you e.g. insert_left of the front of the list. At the time of my writing the PR, it made sense to me to just push_front, but that breaks the invariant that insert_left makes an element appear before it. The alternative is to push_front and then shift the cursor right one step. Neither is great, in my opinion. This problem doesn’t occur with any version of Proposal 1 or 2, because either you can’t insert in the “wrong” direction, or you can and getting shifted is standard procedure.
This also introduces more methods on collections, and has substantial code duplication. If we want to use this to provide DoubleEndedCursors, we could also potentially create some elaborate n-ary cursor structure, which would allow complex manipulation of collections. You could make a DList into an efficient Treque, for instance.
Miscellanea
Just some random stuff that didn’t really fit anywhere else
Primary Use Case: Collections, Particularly DList
The main motivator of this was Iterators making no sense for DList. The only reason outside of being super-resource-spike sensitive to actually use a DList is to freely manipulate its internals once you have iterated to there. Consuming iterators make this impossible.
Vec and RingBuf are certainly perfectly appropriate candidates for the immutable Cursors. The Mutable ones can also work, although they aren’t exactly the best for the job.
Tree* and Hash* seem perfectly appropriate for the Immutable Cursors, but the Mutable ones don’t make much sense.
Anything that’s RandomAccess like Ranges, could probably honestly be made into a Cursor (though making this automatic or mandatory is probably ill-advised).
How Other Languages Do It
- Java ListIterator: Similar to Proposal 2, because Java has completely different iterator semantics. However its direction of mutation is stateful in that it always interacts with the last element yielded. I’m not a fan of this, personally. It doesn’t add any power that I can think of, and adds mental overhead. I get it, though. It makes a kind of sense.
- C++ STL: Iterators are effectively references that a collection can take as an argument to an insert/remove call. This is a non-starter in Rust.
- Qt: continues to take the Kitchen Sink approach and offers both Java-style and C+±style iterators.
Adapters
I haven’t fully thought out which Iterator adapters are compatible with cursors and which aren’t. This may effect the usefulness of keeping them compatible with Iterators, although worst-case they just downgrade the Cursor to an equivalent Iterator and call it a day. However, if not, what exactly “skip(10)” means to a Cursor is unclear. Is the Cursor blocked from walking back? How does “take(10)” interact with mutatation?
What Are Your Thoughts?
I was tasked with posting this here to get community feedback on the issue, so please: feed us backs!
I’m afraid a go/focus split will force the cursor to do more than one conditional per loop iteration, and that would be bad. Further, the direciton enum idea doesn’t seem to fit with Rust – you’d want enum subclasses so that { Next, Prev } can be a subclass of just { Next }.