RedBlackTree regressions need merge from 2.12.x for 2.13.3

[dwijnand]

Duplicate of #12039, to track it as a blocker of 2.13.3.

[retronym]

Versions of Akka compatible with 2.13.x contain a fix to to avoid this problem: akka/akka@d274e03#diff-2223f4fc82176be1aa846ce301a60c80R212 so we can close this ticket and unblock 2.13.3.

[retronym]

Re-opening while we consider @lrytz's analysis on the linked ticket.

[SethTisue]

re-opening since the related bug #12047 is also a 2.13.3 blocker (but milestoned 2.12.12)

[SethTisue]

@retronym @Ichoran it's reassuring that scala-collection-laws (running as part of the 2.13 community build) caught this. at least, it looks like the same thing:

https://scala-ci.typesafe.com/job/scala-2.13.x-jdk11-integrate-community-build/1566/artifact/logs/scala-collection-laws-build.log

[scala-collection-laws] ****** Test_ImmKV_SortedMap_Long_String ******
[scala-collection-laws] Fail(x.`++`(y) sameAs (x.toSeq ++ y.toSeq).toMap
...
[scala-collection-laws] ****** Test_ImmKV_TreeMap_Long_String ******
[scala-collection-laws] Fail(x.`++`(y) sameAs (x.toSeq ++ y.toSeq).toMap
...

once there's a fix I'll of course verify that this goes green again before we 🚢 2.13.3

@retronym note that the 2.12 community build does not run scala-collection-laws — you might want to do that before the 2.12.12 release, maybe add it to the release steps?

[retronym]

REPL version of the regression:

scala> import collection.immutable._; val M = TreeMap; val x = M(1 -> "herring", 2 -> "cod", 3 -> "salmon"); val y = M(3 -> "wish"); val r1 = x ++ y; val r2 = (x.toSeq ++ y.toSeq).toMap
import collection.immutable._
val M: scala.collection.immutable.TreeMap.type = scala.collection.immutable.TreeMap$@4e6280de
val x: scala.collection.immutable.TreeMap[Int,String] = TreeMap(1 -> herring, 2 -> cod, 3 -> salmon)
val y: scala.collection.immutable.TreeMap[Int,String] = TreeMap(3 -> wish)
val r1: scala.collection.immutable.TreeMap[Int,String] = TreeMap(1 -> herring, 2 -> cod, 3 -> salmon)
val r2: scala.collection.immutable.Map[Int,String] = Map(1 -> herring, 2 -> cod, 3 -> wish)

// c.f HashMap which works
scala> import collection.immutable._; val M = HashMap; val x = M(1 -> "herring", 2 -> "cod", 3 -> "salmon"); val y = M(3 -> "wish"); val r1 = x ++ y; val r2 = (x.toSeq ++ y.toSeq).toMap
import collection.immutable._
val M: scala.collection.immutable.HashMap.type = scala.collection.immutable.HashMap$@4aea57dc
val x: scala.collection.immutable.HashMap[Int,String] = HashMap(1 -> herring, 2 -> cod, 3 -> salmon)
val y: scala.collection.immutable.HashMap[Int,String] = HashMap(3 -> wish)
val r1: scala.collection.immutable.HashMap[Int,String] = HashMap(1 -> herring, 2 -> cod, 3 -> wish)
val r2: scala.collection.immutable.Map[Int,String] = Map(1 -> herring, 2 -> cod, 3 -> wish)