"Closing" a container of `GhostCell`s

[Nadrieril]

One annoying aspect of GhostCell is having to keep the brand around everywhere. I'd like an API that allows "closing" a container of GhostCells to hide the brand and reopening it later.

Would this be sound:

pub trait GhostCellContainer {
    type Open<'brand>;
}
pub struct ClosedGhostCellContainer<C: GhostCellContainer> {
    // This lifetime is a lie.
    container: C::Open<'static>,
}
impl<C: GhostCellContainer> ClosedGhostCellContainer<C> {
    pub fn new(f: impl for<'brand> FnOnce() -> C::Open<'brand>) -> Self {
        Self { container: f() }
    }
    pub fn open<R>(
        &mut self,
        f: impl for<'brand> FnOnce(&mut C::Open<'brand>, &mut GhostToken<'brand>) -> R,
    ) -> R {
        GhostToken::new(|mut token| {
            // Safety: uhhh
            let container_ref: &mut C::Open<'_> = unsafe { std::mem::transmute(&mut self.container) };
            f(container_ref, &mut token)
        })
    }
}

To be used like:

struct MyGraphOpen<'brand> {
    nodes: Vec<Rc<GhostCell<'brand, Node<'brand>>>>,
}
struct Node<'brand> {
    edges: Vec<Weak<GhostCell<'brand, Node<'brand>>>>,
}

impl GhostCellContainer for MyGraph {
    type Open<'brand> = MyGraphOpen<'brand> ;
}
// Can be opened to manipulate the graph and closed when we're done.
pub struct MyGraph(ClosedGhostCellContainer<MyGraph>);

[matthieu-m]

I find the idea interesting, to the point I explored the area a bit back then in the context of the ghost_collections crate... but wasn't satisfied by what I came up with, so only ever offered collections for which the token was external.

I do find your proposed API pretty neat. I'd have at most have some naming proposals (perhaps Universe instead of Container, perhaps update instead of open).

Unfortunately, I have no idea whether it could be provably sound, or if there'd be some ways it'd break if the f passed to open were to itself contain one of those containers.

Maybe the author of the Ghost Cell would be interested in having a look at the idea?

One possibility otherwise would be to implement this under an experimental feature, so interested parties can play with it, and try to break it.

[Nadrieril]

@ralfjung what do you think of this?

[RalfJung]

I am confused, how'd you use this? new seems pretty hard to call.

[RalfJung]

Ah, I forgot that GhostCell::new does not require the token. But even then, can you really call open more than once?

A completely self-contained end-to-end example would be useful.

[Nadrieril]

Here's a complete example: https://gist.github.com/Nadrieril/3980ffcf3065a0ed9fe42a36ff3bfa66 .

Two interesting limitations: I would like NodeId to be a pointer into the structure to avoid a lookup, but it can't because it would need to be branded; I can't write an external iterator on the graph because again the iterator state would need to be branded (or I'd have to use id lookups).

[RalfJung]

So there's actually no owned token, the token gets synthesized each time you call open... interesting. This deeply relies on ClosedGhostCellContainer::new forcing the client to produce a C::Open for an arbitrary lifetime; therefore 'brand can't be a "real" lifetime (except possibly'static). But not all magic lifetimes are brands...

I honestly have no idea if this is sound, the proof seems like it would be rather non-trivial.^^

[matthieu-m]

I still think this idea is pretty cool, even in the absence of a proof.

The question, then, is how to move forward.

1. Your idea could be implemented in GhostCell itself, under a new experimental feature (there's already two). After thinking about it, I'd recommend for GhostUniverse and visit + visit_mut naming wise.
2. Your idea could be implemented in a separate crate, of your own, and a link to the new crate could be added to the README.md of GhostCell, emphasizing its experimental status.

What do you think of the second option? It'd be easier for you to be in control of the crate: you could spruce it up over time without having to wait on me every time, and the link from the README.md should help with discovery.

[Nadrieril]

This was just an thought experiment for me, I don't have plans to expand it further. It would feel right to have it as a feature here, if you are up for that.

[matthieu-m]

It would feel right to have it as a feature here, if you are up for that.

That's fine with me, as mentioned there's already two experimental features here so it'd fit right in.

[Nadrieril]

I recalled the existence of https://docs.rs/higher-kinded-types/0.1.1/higher_kinded_types/trait.ForLifetime.html which we should use for the higher-kinded types instead of rolling our own:

pub struct ClosedGhostCellContainer<C: ForLt> {
    // This lifetime is a lie.
    container: C::Of<'static>,
}
impl<C: ForLt> ClosedGhostCellContainer<C> {
    // The output lifetime needs to be mentioned in the output, hence the `PhantomData`.
    pub fn new(f: impl for<'brand> FnOnce(PhantomData<&'brand ()>) -> C::Of<'brand>) -> Self {
        Self {
            container: f(PhantomData),
        }
    }
    pub fn open_mut<R>(
        &mut self,
        f: impl for<'brand> FnOnce(&mut C::Of<'brand>, &mut GhostToken<'brand>) -> R,
    ) -> R {
        GhostToken::new(|mut token| {
            // Safety: uhhh
            let container_ref: &mut C::Of<'_> = unsafe { std::mem::transmute(&mut self.container) };
            f(container_ref, &mut token)
        })
    }
}
pub struct MyGraph(ClosedGhostCellContainer<ForLt!(MyGraphOpen<'_>)>);

[moulins]

As a data-point on the usefulness of this API, the gc-arena crate uses this technique (including the HKT macro trick) to implement a safe garbage collector (see the Arena type for the relevant parts).

Personally, here is how I would paint this particular bikeshed (with elided implementations, as they are all trivial at runtime):

pub struct GhostArena<T: ForLt> {
    inner: T::Of<'static>, // really: unsafe<'a> T::Of<'a>
}

impl<T: ForLt> GhostArena<T> {
    // Gives a token to the closure, both to make the signature valid and for user convenience.
    // Does *not* give out an owned `GhostToken`, which could be captured by `T::Of<'x>`.
    pub fn new(f: impl for<'x> FnOnce(&mut GhostToken<'x>) -> T::Of<'x>) -> Self;

    pub fn visit<R>(
        &self,
        f: impl for<'x> FnOnce(&T::Of<'x>, &GhostToken<'x>) -> R,
    ) -> R;

    pub fn visit_mut<R>(
        &mut self,
        f: impl for<'x> FnOnce(&mut T::Of<'x>, &mut GhostToken<'x>) -> R,
    ) -> R;

    // Less sure of the soundness of this method, as it allows witnessing the fungibility
    // of the branded lifetime in a much more direct way.
    //
    // Can be used together with `new` to map, merge, split, etc the contents of arenas.
    pub fn into_inner<'x>(self) -> T::Of<'x>;
}