IndexMap Soundness: Entry API can return references to incorrect entries

[shaunbennett]

Ran into this surprise while investigating a bug in another crate - there appears to be a bug in the soundness of the entry API, specifically under the robin-hood case where we steal a position.

Steps to reproduce:

fn main() {
    let keys = ["h", "d", "a", "c", "f", "z", "q", "r"];

    for key in keys {
        let entry = match test_map.entry(key) {
            Entry::Occupied(entry) => {
                println!("found occupied entry! - {} - {:?}", entry.key(), key);
                entry.into_mut()
            }
            Entry::Vacant(entry) => {
                println!("inserting empty entry for '{}'", key);
                entry.insert(Default::default()).expect("insertion")
            }
        };
        println!("entry we are modifying: {:?}", entry);
        *entry = Some(key);

        println!("entry is now '{:?}'", entry);
        println!("map is now: {:?}", test_map);
        println!();
        println!();
    }
}

This will print out:

inserting empty entry for 'h'
entry we are modifying: None
entry is now 'Some("h")'
map is now: {"h": Some("h")}


inserting empty entry for 'd'
entry we are modifying: None
entry is now 'Some("d")'
map is now: {"h": Some("h"), "d": Some("d")}


inserting empty entry for 'a'
entry we are modifying: None
entry is now 'Some("a")'
map is now: {"h": Some("h"), "d": Some("d"), "a": Some("a")}


inserting empty entry for 'c'
entry we are modifying: None
entry is now 'Some("c")'
map is now: {"h": Some("h"), "d": Some("d"), "a": Some("a"), "c": Some("c")}


inserting empty entry for 'f'
entry we are modifying: None
entry is now 'Some("f")'
map is now: {"h": Some("h"), "d": Some("d"), "a": Some("a"), "c": Some("c"), "f": Some("f")}


inserting empty entry for 'z'
entry we are modifying: None
entry is now 'Some("z")'
map is now: {"h": Some("h"), "d": Some("d"), "a": Some("a"), "c": Some("c"), "f": Some("f"), "z": Some("z")}


inserting empty entry for 'q'
entry we are modifying: Some("c")
entry is now 'Some("q")'
map is now: {"h": Some("h"), "d": Some("d"), "a": Some("a"), "c": Some("q"), "f": Some("f"), "z": Some("z"), "q": None}


inserting empty entry for 'r'
entry we are modifying: Some("z")
entry is now 'Some("r")'
map is now: {"h": Some("h"), "d": Some("d"), "a": Some("a"), "c": Some("q"), "f": Some("f"), "z": Some("r"), "q": None, "r": None}

Note that in the last two entries, we insert None but get back a reference to a different entry. These two cases are hitting the robin-hood insertion.

I'm opening an MR now to resolve the issue. This appears to have existed since the beginning of the entry api being added.