Allow collection and cursor to be safely contained in the same struct

[sockmaster27]

At the moment it doesn't appear to be possible to create a struct which represents an owned collection and a position in it without the use of raw pointers. Ideally this would be done like this:

struct Object {
    collection: RBTree<...>,
    cursor: Cursor<'?, ...>,
}

However, this isn't possible because of the self-referential nature of this struct.

Instead I propose a new type of cursor, CursorOwning, to coexist with Cursor and CursorMut. It would be mostly functionally equivalent to CursorMut, except its lifetime wouldn't be bounded by that of the collection, as it would own it rather than borrow it.

For now I've implemented this for the RBTree collection, and I'm willing to do the same for the rest of the library if accepted.

[Amanieu]

To avoid massive code duplication, have you considered using a crate like ouroboros instead?

[sockmaster27]

Yes, that does make it technically possible, however, it adds a lot of complexity. First of all, if any control of the interface exposed by the struct is desired, a new struct would have to be introduced that would basically just be a reimplementation of CursorOwning:

#[self_referencing]
struct CursorOwning<A: Adapter + 'static>
where
    <A as intrusive_collections::Adapter>::LinkOps: RBTreeOps,
{
    tree: RBTree<A>,
    #[borrows(mut tree)]
    #[covariant]
    cursor: CursorMut<'this, A>,
}

Removing the excess generics would of course cut this down slightly. This struct has the interface generated by Ouroboros instead of a custom one, which results in some slight oddities, like how accessing the &mut CursorOwning can only be done in a closure through with_cursor_mut(), and construction is done like:

CursorOwning::new(RBTree::new(MyAdapter::new()), |tree| {
    tree.cursor_mut()
}

A point that I've only thought about just now is that things only get worse if Send and Sync are involved, as they are in my particular case. I don't see any reason for why a CursorOwning shouldn't be at least Send if the tree is as well (in contrast to CursorMut). Here I don't see any way around an unsafe implementation of Send:

unsafe impl<A: Adapter + Send> Send for CursorOwning<A>
where
    <A::PointerOps as PointerOps>::Pointer: Send,
    A::LinkOps: RBTreeOps,
{
}

Now if this is only relevant to me this is obviously fine, but I feel like this isn't a super obscure problem to have, and it would be a great thing for the library to offer.

[Amanieu]

My main concern with your proposed implementation of CursorOwning is the bloat caused by duplicating all of the methods of CursorMut. Instead would it be possible to have a different design when a CursorOwning doesn't provide these methods but instead provides a way to get a temporary CursorMut?

impl CursorOwning<A> {
    pub fn with_cursor<T>(&mut self, f: impl FnOnce(&mut CursorMut<A>) -> T) -> T {
        let mut cursor = self.tree.cursor_mut_from_ptr(self.ptr);
        let ret = f(&mut cursor);
        self.ptr = cursor.get();
        ret
    }
}

[sockmaster27]

Sure! This was an attempt to make CursorMut as similar as possible to the others, but it can certainly be done like that too.

[Amanieu]

CI is failing.

[Amanieu]

Thanks!