Another disjoint get idea

[orlp]

The problem with get_disjoint_mut is that we must have all the keys we want to disjointly get ahead of time. But when traversing a tree structure this might not be possible or convenient.

As an alternate idea, an explicit incremental "disjoint tracker". It would work something like this:

let mut sm = SlotMap::new();
let x = sm.insert(0);
let y = sm.insert(100);

let mut disjoint_guard = sm.multiget(); // Borrow sm mutably
disjoint_guard.get_mut(x); // Some(&mut 0)
disjoint_guard.get_mut(y); // Some(&mut 100)
disjoint_guard.get_mut(x); // None - already taken
// disjoint_guard dropped

We would track this internally using the version field like the current get_disjoint_mut impl.

[orlp]

Alternatively (and/or additionally) I could make the leak and unleak functions:

pub fn leak(&mut self, key: K) -> Option<(Leaked<K>, T)>;
pub fn unleak(&mut self, leaked_key: Leaked<K>, val: T);

leak would empty the slot without adding it to the freelist. Leaked<K> would just be a newtype that disallows copying. These functions would not be available for the DenseSlotMap or HopSlotMap.

[orlp]

A refinement of the leak idea, detach/reattach. We must make sure dynamically that a key is detached by setting/checking the freelist.next field to core::u32::MAX (and limit max number of elements to core::u32::MAX - 1).

pub fn detach(&mut self, key: K) -> Option<T>;
pub fn reattach(&mut self, detached_key: K, val: Option<T>);
pub fn map(&mut self, key: K, f: F)
where F: FnOnce((&mut SlotMap<K, V>, V) -> V) {
    if let Some(val) = self.detach(key) {
        self.sm.reattach(key, Some(f(self, val)));
    }
}

Here reattach(k, None) would remove the leaked key from the slotmap.

[polygon]

I am very much in favor of this proposal. I implemented a tree datastructure using SlotMap and wanted to write a mutable iterator that starts at some Node of the tree and returns all nodes up to the top. I looked at get_disjoint_mut but it seems that collecting all keys before is not enough. Since keys is [K; N], the array size needs to be known at compile time which is not possible in my case.

This change would likely fix both issues, the need to collect all keys in advance, and the need to size known at compile time.

[orlp]

Small refinement:

There's no need for reattach to take an Option argument. We can just change remove to detect detached slots. So the above would be:

pub fn detach(&mut self, key: K) -> Option<T>;
pub fn reattach(&mut self, detached_key: K, val: T);
pub fn map(&mut self, key: K, f: F)
where F: FnOnce((&mut Self, V) -> V) {
    if let Some(val) = self.detach(key) {
        self.sm.reattach(key, f(self, val));
    }
}

although if we want to prevent leaking a slot on a panic we'd need:

pub fn map(&mut self, key: K, f: F)
where F: FnOnce((&mut Self, V) -> V) {
    if let Some(val) = self.detach(key) {
        struct RemoveOnPanic {
            sm: &mut Self,
            key: K,
        }

        impl Drop for RemoveOnPanic {
            fn drop(&mut self) {
                self.sm.remove(key)
            }
        }

        let remove_on_panic = RemoveOnPanic { sm: self, key };
        self.sm.reattach(key, f(remove_on_panic.sm, val));
        core::mem::forget(remove_on_panic);
    }
}

although I'm not sure if the extra overhead is worth it to stop the leaking of a single slot in the rare case someone wants to catch panics started during SlotMap::map. Probably not.

Where you would write sm.reattach(key, None) before to delete a detached key you would simply write sm.remove(key).

In sadder news, I'm pushing this back to slotmap 2.0 because it changes the serialization format and some data layouts in changes that would be bigger than I initially anticipated.