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

[Boqun Feng <boqun.feng@gmail.com>]

On Tue, Jan 21, 2025 at 10:14:24AM +0000, Alice Ryhl wrote:
[...]
> +/// References the element in the list next to the cursor.
> +///
> +/// # Invariants
> +///
> +/// * `ptr` is an element in `self.cursor.list`.
> +/// * `ISNEXT == (self.ptr == self.cursor.next)`.
> +pub struct CursorPeek<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> {
> +    cursor: &'a mut Cursor<'b, T, ID>,
> +    ptr: *mut ListLinksFields,
> +}
> +
> +impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64>
> +    CursorPeek<'a, 'b, T, ISNEXT, ID>
> +{
> +    /// Remove the element from the list.
>      pub fn remove(self) -> ListArc<T, ID> {
> -        // SAFETY: The `current` pointer always points at a member of the list.
> -        unsafe { self.list.remove_internal(self.current) }
> +        if ISNEXT {
> +            self.cursor.move_next();
> +        }
> +
> +        // INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next`
> +        // call.
> +        // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of
> +        // `self.cursor.list` by the type invariants of `Cursor`.
> +        unsafe { self.cursor.list.remove_internal(self.ptr) }
> +    }
> +
> +    /// Access this value as an [`ArcBorrow`].
> +    pub fn arc(&self) -> ArcBorrow<'_, T> {
> +        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
> +        let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
> +        // SAFETY:
> +        // * All values in a list are stored in an `Arc`.
> +        // * The value cannot be removed from the list for the duration of the lifetime annotated
> +        //   on the returned `ArcBorrow`, because removing it from the list would require mutable
> +        //   access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds
> +        //   an immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
> +        //   `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable
> +        //   access requires first releasing the immutable borrow on the `CursorPeek`.
> +        // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
> +        //   reference, and `UniqueArc` references must be unique.
> +        unsafe { ArcBorrow::from_raw(me) }
> +    }
> +}
> +
> +impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> core::ops::Deref
> +    for CursorPeek<'a, 'b, T, ISNEXT, ID>
> +{
> +    // This can't use `ArcBorrow<'a, T>` as the target type because 'a is too long. It would let
> +    // you obtain an `ArcBorrow<'a, T>` and then call `CursorPeek::remove` without giving up the
> +    // `ArcBorrow<'a, T>`.

I'm not sure whether we want to mention `ArcBorrow<'a, T>` here, because
`ArcBorrow<'a, T>` is a (smart) pointer type, which should never be used
as a `Deref::Target`, otherwise CursorPeek::deref() would return a
&ArcBorrow<'a, T>, which doesn't make sense, and a bit challenging to
implement I think?

> +    type Target = T;
> +
> +    fn deref(&self) -> &T {
> +        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
> +        let me = unsafe { T::view_value(ListLinks::from_fields(self.cursor.next)) };

Shouldn't this be `self.ptr` instead of `self.cursor.next`?

Regards,
Boqun

> +
> +        // SAFETY: The value cannot be removed from the list for the duration of the lifetime
> +        // annotated on the returned `&T`, because removing it from the list would require mutable
> +        // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an
> +        // immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
> +        // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access
> +        // requires first releasing the immutable borrow on the `CursorPeek`.
> +        unsafe { &*me }
>      }
>  }
>  
> 
> -- 
> 2.48.0.rc2.279.g1de40edade-goog
>