Deleting elements from a map during forEach results in invalid iteration

[joshwd36]

Describe the bug
Map iteration uses an index based approach, based on insertion order. It does this, rather than using the built-in iterator, to avoid multiple borrowing errors (#1058, #1077). However, when an element is removed from a map, all subsequent indexes are decremented and the elements shifted down a step. This means that the next element will be missed out if this deletion happens during a forEach statement.

To Reproduce
This JavaScript code reproduces the issue:

let map = new Map([[0, "a"], [1, "b"], [2, "c"]]);
let index = 0;
map.forEach(function(value, key) {
    if (key === 0) {
        map.delete(0);
        map.set(3, "d");
    }
    console.log(index, key, value);
    index++;
})

This produces the following output:

0 0 a
1 2 c
2 3 d

This is also triggered by the iterates-values-deleted-then-readded test.

Expected behavior
The correct output should be:

0 0 a
1 1 b
2 2 c
3 3 d

This is because in the spec deleting an element should actually just set the key and value to empty, leaving the index intact. This could be implemented by using something like the following for our implementation of OrderedMap, the backing store we use for Map:

#[derive(Hash, PartialEq, Eq)]
enum MapKey<K: Hash + Eq> {
   Key(K),
   Empty(u64), // Necessary to ensure empty keys are still unique.
}

pub struct OrderedMap<K: Hash + Eq, V, S = RandomState> {
    map: IndexMap<MapKey, Option<Value>>,
    empty_count: u64,
    valid_elements: usize // This could be stored to provide a quick way of getting the size of a map
}

However, this would mean that the size of a Map would never decrease unless it was cleared. I may be possible to have a method that could remove the empty elements and re-index the map, but it's unclear when it would be valid for that method to be called. Another approach could be to detect when elements are deleted during iteration, but this seems very error-prone. Other suggestions and discussions would be very welcome.

[joshwd36]

I'm not very familiar with the SpiderMonkey source code, but from what I can gather it seems they use something similar by simply setting the data to empty, although it's possible that they are also reindexing the map at some point too.

[jevancc]

However, this would mean that the size of a Map would never decrease unless it was cleared. I may be possible to have a method that could remove the empty elements and re-index the map, but it's unclear when it would be valid for that method to be called. Another approach could be to detect when elements are deleted during iteration, but this seems very error-prone. Other suggestions and discussions would be very welcome.

For this specific question, you can have the following methods implemented for OrderedMap:

impl<K, V> OrderedMap<K, V> where K: Hash + Eq, {
   fn rehash(&mut self) { // Remove all the elements marked as `Empty` }
   fn lock_rehash(&mut self) { self.rehash_lock = true; } // `rehash_lock`  is a new field added to OrderedMap. This is unsafe, use recursive lock or something equivalent
   fn unlock_rehash(&mut self) { self.rehash_lock = false; }
   fn remove(&mut self, target: ...) {
          // Mark the target element or index with empty

          if !self.rehash_lock && some_condition {
                   self.rehash();
          }
   }
}

Then you can implement the for_each function as something like:

pub(crate) fn for_each(this: &Value, args: &[Value], context: &mut Context) -> Result<Value> {
    // let map = get the map object from this
    map.lock_rehash();
    // Iterate over elements and apply to function
    map.unlock_rehash();
    map.rehash();

    // return undefined
}

and for the normal delete operations not executed in for_each, just not calling the lock_rehash and unlock_rehash so that you can keep the map shrunk.

I am not familiar with the underlying type IndexMap of OrderedMap. Maybe there are other clever ways to implement the behavior you want.

[joshwd36]

That sounds like a very good idea. I haven't done any investigation into it, but one issue could be nested iteration, so perhaps using a counter for the lock would be more appropriate than just a bool.

I am not familiar with the underlying type IndexMap of OrderedMap. Maybe there are other clever ways to implement the behavior you want.

I have had a look at that, but unfortunately I don't think there is anything. The ideal situation would be one where removing elements would not modify the index, but that isn't possible with IndexMap.

[RageKnify]

Since I tried to copy from Map where possible the Set implementation in #1111 also has this issue, once a solution is reached it should be easy to apply it to Set.