Null pointer exception in `RedBlackTree`

[OndrejSpanel]

Reproduction steps

Scala version: 2.13.12, 3.3.1

scala>  (collection.immutable.SortedSet(6, 1, 11, 9, 10, 8).rangeFrom(2) ++ Seq(7, 3, 5)).rangeFrom(4)

Problem

The expression above throws NullPointerException

java.lang.NullPointerExceptions

java.lang.NullPointerException at scala.collection.immutable.RedBlackTree$.joinRight(RedBlackTree.scala:1131) at scala.collection.immutable.RedBlackTree$.joinRight(RedBlackTree.scala:1131) at scala.collection.immutable.RedBlackTree$.scala$collection$immutable$RedBlackTree$$join(RedBlackTree.scala:1161) at scala.collection.immutable.RedBlackTree$.doFrom(RedBlackTree.scala:441) at scala.collection.immutable.RedBlackTree$.from(RedBlackTree.scala:184) at scala.collection.immutable.RedBlackTree$.rangeImpl(RedBlackTree.scala:179) at scala.collection.immutable.TreeSet.rangeImpl(TreeSet.scala:155) at scala.collection.immutable.TreeSet.rangeImpl(TreeSet.scala:39) at scala.collection.SortedOps.rangeFrom(SortedOps.scala:65) at scala.collection.SortedOps.rangeFrom$(SortedOps.scala:65) at scala.collection.immutable.TreeSet.rangeFrom(TreeSet.scala:39)

[SethTisue]

@scala/collections

[som-snytt]

On a modern JVM,

[error] Test scala.collection.immutable.SortedSetTest.rangeFromNPE failed: java.lang.NullPointerException: Cannot invoke "scala.collection.immutable.RedBlackTree$Tree.right()" because "tl" is null, took 0.006 sec

[lrytz]

I assume we have the standard invariants for red-black trees? https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties

A red node does not have a red child.

    val s1 = collection.immutable.TreeSet(6, 1, 11, 9, 10, 8)
    println(s1.tree)

    val s2 = s1.rangeFrom(2)
    println(s2.tree)

gives

BlackTree(
  9,
  null,
  BlackTree(
    6,
    null,
    RedTree(1, null, null, null),
    RedTree(8, null, null, null)
  ),
  BlackTree(11, null, RedTree(10, null, null, null), null)
)

BlackTree(
  10,
  null,
  BlackTree(
    9,
    null,
    RedTree(8, null, RedTree(6, null, null, null), null), // oops?
    null
  ),
  BlackTree(11, null, null, null)
)

[som-snytt]

I also spent some time with wikipedia and had the same question. I almost DMd Stefan about it, but intended to return to it. As the movie line says, I picked a helluva week to give up coffee.

[lrytz]

Found the properties here: https://github.com/scala/scala/blob/v2.13.12/test/scalacheck/redblacktree.scala#L123-L127

[SethTisue]

Is this a 2.13-only bug? If 2.12 is affected, we should backport.

[noresttherein]

RBT lobby strikes again. Why, for immutable sets, not AVLs in the first place? A higher number of rotations doesn't hurt when you need to create log(n) nodes on the way back anyway, and they are both more balanced and much simpler to implement, which is an optimization in itself.

[som-snytt]

avl-set.com

OK, I see AVL tree in a Sedgewick exercise. 2024 is the year I am not a brutish cretin. I had just pulled the book out again an hour ago on the path to offer meaningful assistance.

Obviously RBT is supported by RoBoTs.

[SethTisue]

@OndrejSpanel great catch — thank you for isolating and reporting 🙏