Want way to get stale keys and values out of SecondaryMap, when new keys reuse slots

[ijackson]

Hi. I have an application where I want to mix up some IDs. I plan to do this by having two slotmaps, which allow me to map IDs (slotmap keys) forward and backward. The input IDs for the forward operation come from some other slotmap, so the forward map is a SecondarySlotMap and the reverse map is a SlotMap.

I would prefer not to have to explicitly hunt down the reverse map entries when something is removed from the original primary SlotMap. That complicates the ownership and makes the code more fragile because there's another invariant to maintain.

Helpfully, the forward SecondaryMap will know when I insert a new key using the same slot, that the existing entry must be stale. I could delete the stale entry from the reverse map when that occurs.

Unfortunately, this information is not available in the API at the moment. For this to work, when I insert a new value, I need to be able to get back not only the overwritten key but also the overwritten value from the corresponding slot, if there is one.

The value from the slot contains the key for my reverse map, and with that I can remove the old data from the reverse map. That way I won't leak the reverse map entries - at least, not indefinitely.

I have thought a bit about what this API would look like, and I think the best one is probably for VacantEntry to have a retrieve_stale_entry method which simply gives you the stale key and corresponding value, if any. It would leave the slot empty. These are the values that will be ovewritten anyway if you use insert.

For now I'll try making this function to see what it's like and see if it indeed helps me in my application.

[orlp]

Hey, sorry for the late response. I do understand the use case but I want to think a bit more about the interface. I'm also a bit uncertain since many operations silently remove stale entries, so users might expect the stale entry to be there when it's already removed.

[ijackson]

Hey, sorry for the late response

No problem.

I'm also a bit uncertain since many operations silently remove stale entries, so users might expect the stale entry to be there when it's already removed.

That's certainly a risk. In my application the slotmaps are encapsulated and carefully managed, so that "random code" doesn't get a chance to cause this to happen. Perhaps this issue could be dealt with in documentation.

In the meantime I have rebased my branch for #56 onto current master.

Thanks.

[abonander]

@orlp I have a similar, but much simpler use-case. I just need a variant of insert() that returns the stale value if one was replaced, instead of silently dropping it.

Would you accept an API like this?

/// Returned by [`SecondaryMap::insert_or_replace()`].
pub enum Replaced<K, V> {
    /// The value replaced was at the same version as the given key.
    Fresh(V),
    /// The value replaced was for a previous version. The key is included for reference.
    Stale(K, V),
}

impl<K: Key, V> SecondarySlotMap<K, V> {
    /// Insert a value into the secondary map at a given key or replace the existing value.
    /// 
    /// Returns `None` if the slot was not occupied or if the key was removed from the originating slot map.
    /// Returns `Some(Fresh(value))` if the value replaced is the same version as the given key.
    /// Returns `Some(Stale(key, value))` if the key replaced an older version at the same slot. The old key is included for reference.
    pub fn insert_or_replace(&mut self, key: K, value: V) -> Option<Replaced<K, V>> {
        //...
    }
}