Refcounted slotmap idea

[orlp]

Right now slotmap only offers a zero-cost abstraction for what are essentially safe Copyable weak pointers as an interface. This gives control (but also the burden) of lifetimes back to the user, albeit in a completely safe way.

We could offer a similar interface for shared pointers, with a bit more overhead, in a RcSlotMap. In this new slot map variant slots also store reference counts. Keys for this slot map would no longer be Copy, only Clone. Each RcKey would be a (u32, Sender<usize, bool>) tuple, storing the index of the slot it refers to, and a communication channel back to the slot map to indicate changes to the relevant reference counter. A key could still be made weak and strong again using sm.make_weak(&rckey) and sm.make_strong(key).unwrap().

Advantages are automatic deletion from the slot map and infallible indexing. That is, sm[k] would be infallible and in fact be faster than vector indexing if k is an RcKey, because it would desugar to simply a slots.get_unchecked(k.idx) since the guarantees of a RcKey would ensure the slot exists and is occupied (although we would need enforced a singleton slot map per key type for this to be safe).

Disadvantages are that this slot map variant would not be (de-)serializable or Cloneable and keys would be more expensive to clone. Memory leaks would also occur if you create reference cycles.

A lot of bikeshedding is still needed, and it may be more trouble than it's worth.

[ylxdzsw]

I'm also wanting this feature. Though I have another idea about the RcKey. Currently keys do not have references to the map they belongs to, and they must be used together with a reference to the map. I'm not sure what you have in mind with the Sender, but essentially I think it would be a reference to the map. That means the key can now retrieve the associated value alone using the contained reference, and it is a significant overhead IMO.

What I'm thinking is to keep the key as is (index, version) , but making its drop panic. The user must explicitly call key.free(sm) to decrease the reference count and drop key (or explicitly leak the key if they want). The keys still cannot be Copy, though.

[ylxdzsw]

After thinking it more I now realize that including a reference to the map in the key might be preferable.

First, we no longer need that version field in the key as there won't be dangling keys anymore.

The problem is we need to somehow associate keys with its belonging map, to prevent from freeing a key of map A on map B, violating memory safety. There are two ways I can think of to do it:

1. using the "brands" trick as in https://github.com/matthieu-m/ghost-cell . Basically it creates a unique scope for each map and using the lifetime of the scope to make unique types for the map and its keys. This however complicates the API and restricts the use cases.
2. storing a unique identity of the map in the key and compare it every time.

For the second approach, the most obvious candidate for the identity is a pointer to the map (assuming the map is pinned). Though we still can't dereference it as the map may be dropped before the keys.

[evanrelf]

If I understand correctly, I believe the team working on the Zed text editor implemented something similar to this in their GPUI crate. They describe the concept in this blog post: https://zed.dev/blog/gpui-ownership

[qouteall]

@evanrelf GPUI's Model<T> is similar to Rc<QCell<T>> where AppContext is QCellOwner. https://docs.rs/qcell/latest/qcell/