Re: [PATCH] rust: list: make the cursor point between elements

From: Alice Ryhl
Date: Mon Jan 20 2025 - 10:53:17 EST


On Mon, Jan 20, 2025 at 12:55 PM Andreas Hindborg <a.hindborg@xxxxxxxxxx> wrote:
>
> Hi Alice,
>
> This looks like a nice improvement!

Thanks!

> This looks like a refactor of `push_front`, `push_back`. It looks like
> it is unrelated to the cursor change. Can you split this out into a
> separate patch?

I don't think it's unrelated. It extracts out common code that
previously only push_front/push_back have, but that the cursor now
also needs. Of course, it could still make sense to extract
insert_inner out in a separate patch.

> > @@ -489,17 +480,21 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
> > other.first = ptr::null_mut();
> > }
> >
> > - /// Returns a cursor to the first element of the list.
> > - ///
> > - /// If the list is empty, this returns `None`.
> > - pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
> > - if self.first.is_null() {
> > - None
> > - } else {
> > - Some(Cursor {
> > - current: self.first,
> > - list: self,
> > - })
> > - }
> > - }
> > + /// Returns a cursor that points before the first element of the list.
> > + pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
> > + // INVARIANT: `self.first` is in this list.
> > + Cursor {
> > + next: self.first,
> > + list: self,
> > + }
> > + }
> > +
> > + /// Returns a cursor that points after the last element in the list.
> > + pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
> > + // INVARIANT: `next` is allowed to be null.
> > + Cursor {
> > + next: core::ptr::null_mut(),
>
> I am slightly confused about why you need to track the beginning and end
> of the list. The cursor movement operations circle have wrapping
> semantics and the lists are circular. Could you remove some code by
> using this property?

I think the current API is much more intuitive. Yes, the list is
implemented in a circular manner, but you're not intended to think of
it that way. The linked list is a list of elements. With elements ABC
and cursors pointing between them, it makes sense that the cursor can
be |ABC, A|BC, AB|C, ABC|. In each case, you can add an element before
or after the cursor. To iterate the list, you keep calling `move_next`
until `next` returns `None`. That also makes sense. If the cursor
becomes circular, then you iterate by calling `next` until the next
element is the first element? Seems confusing to me.

I also don't think it's much less code. You still need to handle null
pointers because the list might be empty.

> > + list: self,
> > + }
> > + }
> >
> > @@ -579,69 +574,211 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
> >
> > /// A cursor into a [`List`].
> > ///
> > +/// A cursor always rests between two elements in the list. This means that a cursor has a previous
> > +/// and next element, but no current element. It also means that it's possible to have a cursor
> > +/// into an empty list.
> > +///
> > /// # Invariants
> > ///
> > -/// The `current` pointer points a value in `list`.
> > +/// The `next` pointer is null or points a value in `list`.
>
> Could you add an example of how to use this struct?
>
> Unrelated, but since you are at it, could you update the safety comment
> on first line in the `List::remove` function?

Okay, will look at this.

Alice