Possible bug in MutableMap inside recursive function and...can/should I remove current item inside a foreach?

1

Hi.
The following code will enter an infinite loop if you remove other than the first item.
Is this the correct behavior?
Is removing items while iterating a no-no?
Should I just use Js.Global.setTimeout(() => step() ,0) instead?
Thanks

let map = Belt.MutableMap.Int.fromArray([(1, "a"), (2, "b"), (3, "c")])

let rec step = () => {
  Js.log("-----STEP-----")
  map->Belt.MutableMap.Int.forEach((k, v) => {
    Js.log((k, v))
    Js.log(map->Belt.MutableMap.Int.size)

    if k == 1 { //change to 2 and it will enter an infinite loop
        map->Belt.MutableMap.Int.remove(k)
    }

    Js.log(map->Belt.MutableMap.Int.size)

    if(map->Belt.MutableMap.Int.size > 2) {
        step()
    }
  })

}

step()

…works on JS

const myMap = new Map([
  [1, "one"],
  [2, "two"],
  [3, "three"],
])

let step = () => {

	console.log("-----STEP------")

	myMap.forEach((v, k) => {

		console.log(v, k)

		console.log(myMap.size)

		myMap.delete(2)

		console.log(myMap.size)

		if(myMap.size > 2) {
			step()
		}

	})


}

step()
2

Looks like a bug in your code and not in Belt lib.

Consider that your JS code is not doing the same thing as your rescript code. In your JS, you enter the forEach do some stuff then myMap.delete(2) that first iteration and so the map size is no longer > 2 and the loop finishes.

Contrast that to the rescript code where you only delete an element when the key is a certain value. The code you show has k == 1 { ...delete...}. The first iteration through the forEach k will indeed be 1, so the element is removed, size falls, step is not called, and iteration stops.

But if you change it to 2 as in your comment…the code inside the if will never be called because the forEach starts with the first element (k ==1) each time step is called, so an element is never removed, so the size is always 3, so you always call the step until you blow up the stack, and the program terminates that way.

3 Likes
3

Hi Ryan.
The rescript and js code should be doing the same thing.
Also ‘k’ is not an index but a key.
Pay attention that there is an iteration and a recursion.
The problem seams to be that if you remove an item from the collection and then “recurse” the step function doesn’t get the updated collection.

4

The two code snippets you show are not functionally equivalent. You either need to (1) add the key check before deleting in the javascript version, or (2) remove the key check before deleting in the rescript version. If you do that they will have the same behavior. Option 1 will cause the JS code to stack overflow and crash, and option 2 will cause the rescript code to print out the first and third k-v pairs in the map and then terminate normally.

In the JS version you show, recursion never happens because you delete the k-v pair the first iteration of the forEach “loop”. In the rescript version with k == 1, recursion never happens because the first k-v pair is deleted the first iteration and the size is 2 before it has a chance to recurse. In the rescript version with k == 2, it recurses until exhausting the stack because no k-v pair is ever deleted and the size is always 3. So that is the problem not anything with the recursion per-se.

Here’s an interesting aside.

One thing to keep in mind is the iteration order of the Belt map and the JS map may not be the same. So while you can get the same behavior between the two scripts you show given the order you added the keys to the map in the JS version, it may not always hold.

In Belt’s forEach, “The bindings are passed to f in increasing order with respect to the ordering over the type of the keys.” (docs) (Because the AVL tree is used in its implementation.)

On the other hand the JS forEach will use insertion order according to the ECMAScript Language Specification for the Map (and at least in Node that is the case).

1 Like
5

Yes, you’re right!! My bad :-
Guess one shouldn’t use recursion when changing an external variable??
Well…it surely isn’t very functional.

6

Yeah, Rescript doesn’t stop you from mutating mutable Map structures will “iterating” on them, but as you see it can be tricky. So whether it’s good style to or not, that’s up to you.

Just for fun, here is what some other languages do when you modify the map/ht/dict/thing you’re iterating over:

  • OCaml Hashtbl (not a mutable map like rescript, but hash table …not using tree afaik)
    • unspecified behavior while modifying a Hashtbl during iteration (docs)
  • OCaml Base Hashtbl (Base is a stdlib replacement for OCaml)
    • modifying during iteration will raise an error (docs).
  • JavaScript (Map):
    • “New keys added after the call to forEach begins are visited. A key will be revisited if it is deleted after it has been visited and then re-added before the forEach call completes. Keys that are deleted after the call to forEach begins and before being visited are not visited unless the key is added again before the forEach call completes.” (docs)
  • Java (iterable)
    • unspecified: “The behavior of this method is unspecified if the action performs side-effects that modify the underlying source of elements, unless an overriding class has specified a concurrent modification policy.”
  • Python (dict)
    • "Iterating views while adding or deleting entries in the dictionary may raise a RuntimeError or fail to iterate over all entries."docs
2 Likes
7

Hi Ryan. Thanks for the info.
I guess the recursion part of the code is also a mess.
The recursion should also be made after the complete iteration otherwise the infinite loop is the correct outcome.
Sorry for the confusion :-\

1 Like