getOrElseUpdate does not behave as it should on mutable.LongMap

[charpov]

Here's a self-contained example that shows the incorrect behavior:

import scala.collection.mutable
import scala.collection.immutable.SortedSet
import scala.util.Random

class Bug(m: mutable.Map[Long, Unit]):
   def test(useGetOrElseUpdate: Boolean): Set[Long] =
      val rand = Random(1)
      def n()  = rand.nextInt(30)

      def f(d: Int): Unit =
         if d > 0 then
            g(n(), d - 1)
            g(n(), d - 1)

      def g1(x: Long, d: Int): Unit = m.getOrElseUpdate(x, f(d)) // use getOrElseUpdate

      def g2(x: Long, d: Int): Unit = if !m.contains(x) then m(x) = f(d) // do it as in MapOps

      lazy val g = if useGetOrElseUpdate then g1 else g2

      f(10)
      m.keys.to(SortedSet)

@main def RunTest(): Unit =
   println(Bug(mutable.Map.empty[Long, Unit]).test(useGetOrElseUpdate = true))
   println(Bug(mutable.LongMap.empty[Unit]).test(useGetOrElseUpdate = true))
   println()
   println(Bug(mutable.Map.empty[Long, Unit]).test(useGetOrElseUpdate = false))
   println(Bug(mutable.LongMap.empty[Unit]).test(useGetOrElseUpdate = false))

(I use Scala 3 syntax but this is a Scala 2 library issue). The output is:

TreeSet(0, 2, 3, 4, 6, 7, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 27, 28, 29)
TreeSet(0, 2, 3, 4, 6, 7, 9, 10, 12, 13, 14, 15, 16, 19, 20, 23, 25, 26, 27, 28, 29)

TreeSet(0, 2, 3, 4, 6, 7, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 27, 28, 29)
TreeSet(0, 2, 3, 4, 6, 7, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 27, 28, 29)

Notice how mutable.Map and mutable.LongMap produce different outputs when getOrElseUpdate is used. When not used, it is replaced with an implementation similar to what's in MapOps (I use contains instead of get because I ignore values, but the behavior is the same with get).

I believe this is a bug because LongMap#getOrElseUpdate should behave as the default MapOps implementation and because LongMap[Unit] should behave like Map[Long,Unit] (in a single-threaded context).

One could argue that getOrElseUpdate makes no such guarantees when the by-value code modifies the map, but:

• the documentation is silent about that;
• it's not an unreasonable scenario (my actual application is a memoized recursive function, without randomness);
• there is a comment inside the LongMap#getOrElseUpdate source that says:

      // It is possible that the default value computation was side-effecting
      // Our hash table may have resized or even contain what we want now
      // (but if it does, we'll replace it)

  which suggests that an effort was made to handle this situation.

I'm using Scala 3.5.2 (which seems to be using the 2.13.14 collections) in my experiments.

[SethTisue]

@scala/collections

[som-snytt]

I just noticed 3-indent. 🤯

[charpov]

I just noticed 3-indent. 🤯

When Scala 3 was new, there was a discussion somewhere that 3-indent would be the norm (maybe it wasn't serious). I adopted it (including all the code examples in a book) and I'm very happy with it. Four is too much for me, and 2 (which I use in Java) not enough when omitting braces. BTW, it looks like ADA style guides recommend using a 3-indent... 😉