IndexMap::truncate leaves the map in an inconsistent state.

[Eh2406]

Hi,

I am on the Cargo Team and was recently hired by the Rust Foundation to help triage AI discovered bugs. This bug was found with AI, namely scrutineer and Fable. Except where specifically labeled this report was written by me.

This is similar to #559 but can be reproduced after #560.

    let mut map: FnvIndexMap<u16, u32, 4> = FnvIndexMap::new();
    map.insert(4, 444).unwrap();
    map.insert(2, 222).unwrap();
    map.insert(0, 0).unwrap();
    map.insert(7, 7).unwrap();

    assert_eq!(map.get(&2), Some(&222)); // ok before map.truncate(2);
    map.truncate(2);
    assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&4, &444), (&2, &222)]); // ok
    assert_eq!(map.get(&4), Some(&444)); // ok
    assert_eq!(map.get(&2), Some(&222)); // <-- key present in iter() but unreachable

Panics on the last line.

The AI explains what happens as:

truncate() calls entries.truncate(len) then iterates indices and sets to None only those Pos whose index()>=len. Surviving entries (index<len) keep their Pos, but any probe chain that passed THROUGH a now-nulled slot is broken: open-addressing find() stops at the first None slot (index_map.rs:190 let pos = self.indices[probe]?;). A surviving key whose desired_pos precedes a removed key's slot, and which was displaced past it, becomes unreachable. No backward-shift / rehash is performed, unlike remove_found and retain_in_order which correctly rebuild.