Scala Programming Language
  1. Scala Programming Language
  2. SI-3796

SortedSet/SortedMap defect: invariance violation at Empty

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Misc Library
    • Labels:
      None

      Description

      This is Scala 2.8.0.final or equally a more recent snapshot like scala-2.8.0.r22830-b20100824020153.

      The following example makes the Redblack implementation behind SortedSet/SortedMap crash:

      import scala.collection.immutable.SortedSet
      
      abstract class OP
      case class A(i: Int) extends OP
      case class D(i: Int) extends OP
      case class R(i: Int, j: Int) extends OP
      
      val ops = List(A(6), A(10), A(12), A(14), A(16), A(17), A(19), A(21), A(22), A(24), A(29), D(10), A(10), D(10), A(10), D(12), A(12), D(12), A(12), R(16,30), D(17), D(19))
      
      (SortedSet.empty[Int] /: ops) { case (s, A(i)) => s + i case (s, D(i)) => s - i case (s, R(i, j)) => s.range(i, j) }
      

      Here is the JVM dump:

      java.lang.RuntimeException: Defect: invariance violation at Empty
      	at scala.collection.immutable.RedBlack$$NonEmpty.balRight$$1(RedBlack.scala:120)
      	at scala.collection.immutable.RedBlack$$NonEmpty.delRight$$1(RedBlack.scala:127)
      	at scala.collection.immutable.RedBlack$$NonEmpty.del(RedBlack.scala:149)
      	at scala.collection.immutable.RedBlack$$NonEmpty.delLeft$$1(RedBlack.scala:123)
      	at scala.collection.immutable.RedBlack$$NonEmpty.del(RedBlack.scala:148)
      	at scala.collection.immutable.RedBlack$$Tree.delete(RedBlack.scala:36)
      	at scala.collection.immutable.TreeSet.$$minus(TreeSet.scala:93)
      	at scala.collection.immutable.TreeSet.$$minus(TreeSet.scala:47)
      	at $$anonfun$$1.apply(<console>:17)
      	at $$anonfun$$1.apply(<console>:17)
      	at scala.collection.LinearSeqOptimized$$class.foldLeft(LinearSeqOptimized.sca...
      
      

      Maybe some mistake from some literature has been copied here. Something like this has happened to other libraries before.

      It might help to look at the following proven implementation
      http://isabelle.in.tum.de/dist/library/HOL/Library/RBT_Impl.html

      1. patch.txt
        11 kB
        Jira Admin
      2. redblack.scala
        8 kB
        Jira Admin

        Activity

        Hide
        Daniel Sobral added a comment -

        ScalaCheck test suite for RedBlack

        Show
        Daniel Sobral added a comment - ScalaCheck test suite for RedBlack
        Hide
        Daniel Sobral added a comment -

        I warned you you should have waited for my new test suite. As it happens, there was still one bug left. I made a pull request on the fix here: http://github.com/dcsobral/scala/pull/1

        Show
        Daniel Sobral added a comment - I warned you you should have waited for my new test suite. As it happens, there was still one bug left. I made a pull request on the fix here: http://github.com/dcsobral/scala/pull/1
        Hide
        Daniel Sobral added a comment -

        Curiously enough, once I had a proper test suite in place, doing the actual work was pretty quick. I reused most of the stuff from the previous broken patch, with just a few minor modifications.

        Patch is here: http://github.com/dcsobral/scala/commit/e87ed79e78378b864eacbc498554f224de177ccc

        However, even though it passed all tests from my test suite (and it didn't pass some when I had something wrong – which gives me some confidence on the test suite itself , it is rather big and a bit complex. Commit with care.

        Show
        Daniel Sobral added a comment - Curiously enough, once I had a proper test suite in place, doing the actual work was pretty quick. I reused most of the stuff from the previous broken patch, with just a few minor modifications. Patch is here: http://github.com/dcsobral/scala/commit/e87ed79e78378b864eacbc498554f224de177ccc However, even though it passed all tests from my test suite (and it didn't pass some when I had something wrong – which gives me some confidence on the test suite itself , it is rather big and a bit complex. Commit with care.
        Hide
        Daniel Sobral added a comment -

        I had to delete my scala fork and start over, because of a corruption problem. So here is the thew new link to a more efficient implementaton of range.

        https://github.com/dcsobral/scala/commit/6aa05edca40f586ab0eb739031e02bc2ff1191ad

        Show
        Daniel Sobral added a comment - I had to delete my scala fork and start over, because of a corruption problem. So here is the thew new link to a more efficient implementaton of range. https://github.com/dcsobral/scala/commit/6aa05edca40f586ab0eb739031e02bc2ff1191ad
        Hide
        Aleksandar Prokopec added a comment -

        (In r23551) Applying patch by Daniel Sobral for SI-3796. Closes SI-3796.

        No review.

        Show
        Aleksandar Prokopec added a comment - (In r23551) Applying patch by Daniel Sobral for SI-3796 . Closes SI-3796 . No review.

          People

          • Assignee:
            Aleksandar Prokopec
            Reporter:
            Makarius
            TracCC:
            Daniel Sobral, Makarius, Seth Tisue
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development