Cross-SlotMap usage of Key tracking issue

[orlp]

Currently there is no compile-time or run-time protection of using a Key from one SlotMap on another. There is no unsafe behavior if this occurs, but it might be worth catching this error somehow anyway.

Some approaches were suggested.

1. Changing Key to Key<T>, of the type of the slot map. This offers a little protection, but not much - you can still use keys between slot maps storing the same type of value. If you take into account that values are also actually used after retrieval, with typechecking, any undetected errors of using a key on the wrong slot map probably already stored values of the same type.

2. Storing a unique id per slot map inside it and in the key as well and checking for equality when used. Quite expensive, so possibly only when debug mode is enabled. Arises questions of how such an unique id should be generated, and how the error should be reported. E.g. should sm1.get(k2) return None or panic? (Probably panic).

3. Starting the version field of each slot map on a random location to reduce the chance of a valid result when crossing keys. Not a fan of this, as it might actually make the problem harder and more spurious to detect, while still leaving the possibility of the error.

4. Adding a marker type M to both SlotMap<T, M=()> and Key<M=()> that can be used to distinguish a slot map from any other if the user desires with their own new type. Stops all errors and is elegant, but has two issues. Users have to make their own newtypes to get this protection and it blows up code size (until this is fixed [WIP] Deduplicate instances rust-lang/rust#48139).

5. Add a key type for the slot map, such that SlotMap<T, K=Key> where K: Copy + From<Key> + Into<Key>. This allows people to make key newtypes that can't be mixed/matched. Very similar to number 4.

[orlp]

I'm currently leaning towards option 4. A possible remedy for the blowup in code size is to recommend users to do the following:

#[cfg(debug_assertions)]
struct EntitiesMarker;

#[cfg(not(debug_assertions))]
type EntitiesMarker = ();

fn main() {
    let mut sm: SlotMap<Entity, EntitiesMarker> = SlotMap::new();
}

So that you get the added type checking in debug mode but no code size blowup in release mode. Possibly providing a macro for this as well.

[orlp]

Never mind the code blowing up in size, that appears to be fixed: rust-lang/rust#49479.

[rebo]

A fix of type 4 would be great. I just had to fix a trivial error that typed keys would have prevented.

Basically I had a function that took two keys as parameters. I passed them in as keyA keyB but wrote the method as keyB keyA, couldn’t figure out what was going wrong for a while.

That said it’s not a major major problem and I know to double check these things going forward.

[orlp]

I chose to go with option 5, and a first implementation is done in aa0a676 (you can see how much work this has been).

This breaks most code, but the fixes are very simple, and make people more aware of their key type, which is good.

Marker types felt just a bit too... sketchy. They're kinda abusing the type system, and break in non-obvious ways (e.g. derives).

[orlp]

Fixed with release 0.3.0.