Re: [PATCH v8 5/6] rust: rbtree: add `RBTreeCursor`

[Benno Lossin <benno.lossin@proton.me>]

On 06.08.24 10:24, Alice Ryhl wrote:
> On Mon, Aug 5, 2024 at 9:35 PM Benno Lossin <benno.lossin@proton.me> wrote:
>> On 27.07.24 22:30, Matt Gilbride wrote:
>>> +        // SAFETY: `best` is a non-null node so it is valid by the type invariants.
>>> +        let links = unsafe { addr_of_mut!((*best.as_ptr()).links) };
>>> +
>>> +        NonNull::new(links).map(|current| {
>>
>> Why would `links` be a null pointer? AFAIK it just came from `best`
>> which is non-null. (I don't know if we want to use `new_unchecked`
>> instead, but wanted to mention it)
> 
> It's never a null pointer in this branch. Do you prefer an extra
> unsafe block to call new_unchecked?

No need, doesn't seem like this part is hot and this is something that
field projections could solve.

>>> +            // INVARIANT:
>>> +            // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
>>> +            // - Due to the type signature of this function, the returned [`RBTreeCursor`]
>>> +            //   borrows mutably from `self`.
>>> +            RBTreeCursor {
>>> +                current,
>>> +                tree: self,
>>> +            }
>>> +        })
>>> +    }
>>
>> [...]
>>
>>> +/// // Calling `remove_next` removes and returns the last element.
>>> +/// assert_eq!(cursor.remove_next().unwrap().to_key_value(), (30, 300));
>>> +///
>>> +/// # Ok::<(), Error>(())
>>> +/// ```
>>
>> I would put a newline here.
> 
> Ok.
> 
>>> +/// # Invariants
>>> +/// - `current` points to a node that is in the same [`RBTree`] as `tree`.
>>> +pub struct RBTreeCursor<'a, K, V> {
>>
>> I think we can name it just `Cursor`, since one can refer to it as
>> `rbtree::Cursor` and then it also follows the naming scheme for `Iter`
>> etc.
> 
> You are welcome to submit that as a follow-up change.
> 
>>> +    tree: &'a mut RBTree<K, V>,
>>> +    current: NonNull<bindings::rb_node>,
>>> +}
>>> +
>>> +// SAFETY: The [`RBTreeCursor`] gives out immutable references to K and mutable references to V,
>>> +// so it has the same thread safety requirements as mutable references.
>>> +unsafe impl<'a, K: Send, V: Send> Send for RBTreeCursor<'a, K, V> {}
>>
>> Again, do we want to use `K: Sync` here instead?
> 
> In this case, `K: Send` and `K: Sync` are both sufficient conditions,
> but `K: Send` will generally be less restrictive for the user.

What if `K = struct(RefCell<i32>, i32)` where only the second i32 is
used in `(Partial)Ord`? Then you can send `RBTreeCursor` to another
thread and call `borrow` there, even though `K: !Sync` (and the value
still lives on another thread).

---
Cheers,
Benno