Trying to understand GhostCursor

[RalfJung]

Hi @matthieu-m, I am trying to understand GhostCursor, but I am somewhat stuck, so I'd appreciate some help. :) First and foremost, I am trying to understand the problem that GhostCursor is solving. From the docs, that is not clear to me. There is a "broken example" but it talks about half-ownership of some points so this already seems to be specific to static-rc... is there some way to phrase this just in terms of standard Rust types? Then I figured, maybe I need to look at how GhostCursor is used. So I looked at the linked list cursor based on this. Just from staring at the code I did not see the problem, so I tried to implement a cursor for our own toy linked list... and I think I have the same API as what you have, but without a GhostCursor. (I even added peek_next_mut on top and that works, too.) You can find it here. Am I missing something? One difference is that this linked list is based on an arena, which makes some things simpler than reference counting -- is that where the problem arises?

[RalfJung]

Okay, when I try to do the same with the Arc-based list I need to clone on each step. I suppose that is what you avoid via GhostCursor.

[matthieu-m]

There is a "broken example" but it talks about half-ownership of some points so this already seems to be specific to static-rc... is there some way to phrase this just in terms of standard Rust types?

The use of static-rc is a red herring; you can substitute Rc or Arc for it if you wish, they have the same API -- static-rc is just slightly more restrictive but that's about it.

Okay, when I try to do the same with the Arc-based list I need to clone on each step. I suppose that is what you avoid via GhostCursor.

Yes, that is the idea. It's a small cost, but I was trying to see if cost-free was possible.

One difference is that this linked list is based on an arena, which makes some things simpler than reference counting -- is that where the problem arises?

I think so.

The difference between an arena-based solution and a Rc-based solution is the owner:

• In an arena-based solution, the arena owns all, and outlives all, therefore there is never a worry of an operation on one Node causing another Node to be dropped prematurely.
• In a Rc-based, the Nodes own each others, so dropping node.next may cause a ripple of drops to occur.

Using immutable borrows, there's no issue: there is a stack variable which is borrows, and a chain of borrowed Nodes up until the current reference, and due to the borrow all of those are borrowed with the lifetime of the original stack variable.

Using mutable borrows, however, it's quite possible that the "chain" is severed when mutating a Node. Your example of peek_next_mut is such an example:

• Using peek_next_mut I remove the pointer to the current node from the next.
• Using peek_prev_mut I remove the pointer to the current node from the previous.

There is now no pointer to the current node, it is dropped, so how do I have a reference?

The "bet" of GhostCursor is that if the window of mutability is restrictive enough, it may be possible to prevent the drop of all the references to the current node, which in turn would lead to UB.

Whether it is actually possible, and the current design is actually sound -- that is the question.

[RalfJung]

Finally taking a closer look at GhostCell.

The first thing that stands out to me is https://github.com/matthieu-m/ghost-cell/blob/afe49c724a9a44991ffa772d4504a92286092ba1/src/ghost_cursor.rs#L48 Why is this not a &'a mut? I assume the idea is that GhostCursor does exclusively borrow the GhostToken for lifetime 'a, otherwise the API seems very unsound.

Why does into_parts only return a shared reference to the token? https://github.com/matthieu-m/ghost-cell/blob/afe49c724a9a44991ffa772d4504a92286092ba1/src/ghost_cursor.rs#L80 Conceptually, a GhostCursor seems to be a package of a mutable reference to the token, and an optional reference to a GhostCell (and that is required for into_inner to make sense).

This one seems suspicious: https://github.com/matthieu-m/ghost-cell/blob/afe49c724a9a44991ffa772d4504a92286092ba1/src/ghost_cursor.rs#L185-L187 fun obtains a (copyable) shared ref with a very long lifetime. This is unsound for reasons similar to how the original Ref::map was unsound (until the closure was made lifetime polymorphic as it is today). Here is a counterexample:

    GhostToken::new(|mut token| {
        let cell = GhostCell::new(1);
        let leak = Cell::new(None);
        let mut cursor = GhostCursor::new(&mut token, Some(&cell));

        cursor.move_mut(|cell_ref| {
            leak.set(Some(cell_ref));
            None
        }).ok();
        let cell_ref: &i32 = leak.get().unwrap();
        
        // cell_ref is a shared reference, but the value it points to can change -- this is unsound
        assert_eq!(*cell_ref, 1);
        *cursor.borrow_mut().unwrap() = 42;
        assert_eq!(*cell_ref, 42);
    });

[matthieu-m]

Thanks for the questions.

Why is this not a &'a mut? I assume the idea is that GhostCursor does exclusively borrow the GhostToken for lifetime 'a, otherwise the API seems very unsound.

Indeed, and the constructor takes a &'a mut to enforce this invariant so I'm not sure why I went to all the trouble of using NonNull here.

I wonder if I was running into borrowing issues, as obtaining a reference to a GhostCell through another GhostCell may be borrowing the token?

Why does into_parts only return a shared reference to the token?

Seems like a spurious mistake, I see no reason for it seeing as the cursor had a mutable reference.

This one seems suspicious:

Damned! You are spot on. Luckily the fix shouldn't invalidate any legitimate code.

[RalfJung]

Luckily the fix shouldn't invalidate any legitimate code.

Yeah, there is the "obvious" fix of making the callback lifetime-generic. This works for Ref::map but I don't understand GhostCursor yet so I cannot quite say if it would also work here.

Please let me know once that is fixed so I can make another attemp at getting intuition for this type without being distracted by unrelated soundness issues. :)

[matthieu-m]

Sorry, I completely forgot about this. Thankfully @wackbyte didn't and fixed move_mut in #12, on top of tweaking into_parts to return a mutable token as discussed.