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

ListBuffer's remove computes bounds incorrectly, fails to throw exception, corrupts buffer

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.2, Scala 2.10.0-RC2, Scala 2.10.0, Scala 2.11.0-M1
    • Fix Version/s: Scala 2.10.1
    • Component/s: Collections
    • Labels:
      None
    • Environment:

      Scala version 2.11.0-20121010-013641-9bedb07350

      Description

      There is a off-by-one error in the computation of `count1`, which fails to trigger an exception in the following case:

      Removing one item from an invalid position where position == length works ...

      scala> val lb = ListBuffer('a, 'b , 'c)
      lb: scala.collection.mutable.ListBuffer[Symbol] = ListBuffer('a, 'b, 'c)
      
      scala> lb.remove(3, 1)
      
      scala> lb
      res21: scala.collection.mutable.ListBuffer[Symbol] = ListBuffer('a, 'b, 'c)
      

      ... but fails for a different invalid position, even if we don't actually remove an element ...

      scala> lb.remove(9, 0)
      java.lang.UnsupportedOperationException: tail of empty list
      	at scala.collection.immutable.Nil$.tail(List.scala:331)
      	at scala.collection.immutable.Nil$.tail(List.scala:326)
      	at scala.collection.mutable.ListBuffer.remove(ListBuffer.scala:283)
      

      Invalid position + removing more items than existing, is OK again:

      scala> lb.remove(3, 4)
      
      scala> lb
      res26: scala.collection.mutable.ListBuffer[Symbol] = ListBuffer('a, 'b, 'c)
      

      If position and amount of items to be removed == length, the operation succeeds, but the buffer is corrupted afterwards:

      scala> lb.remove(4, 4)
      
      scala> lb
      java.util.NoSuchElementException: head of empty list
      	at scala.collection.immutable.Nil$.head(List.scala:329)
      	at scala.collection.immutable.Nil$.head(List.scala:326)
      	at scala.collection.mutable.ListBuffer$$anon$1.next(ListBuffer.scala:406)
      	at scala.collection.Iterator$$anon$10.next(Iterator.scala:312)
      	at scala.collection.Iterator$$anon$11.next(Iterator.scala:328)
      	at scala.collection.Iterator$class.foreach(Iterator.scala:727)
      	at scala.collection.AbstractIterator.foreach(Iterator.scala:1156)
      	at scala.collection.TraversableOnce$class.addString(TraversableOnce.scala:306)
      	at scala.collection.AbstractIterator.addString(Iterator.scala:1156)
      	at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:272)
      	at scala.collection.AbstractIterator.mkString(Iterator.scala:1156)
      	at scala.runtime.ScalaRunTime$.scala$runtime$ScalaRunTime$$inner$1(ScalaRunTime.scala:323)
      	at scala.runtime.ScalaRunTime$.stringOf(ScalaRunTime.scala:332)
      	at scala.runtime.ScalaRunTime$.replStringOf(ScalaRunTime.scala:340)
      

      The underlying cause of this is that the whole bounds-fixing code is highly questionable, especially because it isn't mentioned in the documentation at all:

        override def remove(n: Int, count: Int) {
          val n1 = n max 0
          val count1 = count min (len - n1)
          ...
      

      Imho we should kill this behaviour completely and replace it with appropriate bound checks throwing IOOBEs.

      What do you think?

        Activity

        Hide
        Martin Odersky added a comment -

        I agree. ListBuffer.remove breaks the contract established by BufferLike.remove, which requires bounds checks. It's also inconsistent with the unary version of remove in ListBuffer. We just have to make sure that ListBuffer.remove's broken behavior is not assumed elsewhere in the libraries.

        Show
        Martin Odersky added a comment - I agree. ListBuffer.remove breaks the contract established by BufferLike.remove, which requires bounds checks. It's also inconsistent with the unary version of remove in ListBuffer. We just have to make sure that ListBuffer.remove's broken behavior is not assumed elsewhere in the libraries.
        Hide
        Simon Ochsenreither added a comment -

        As far as I see, there is only one alternative usage: People who used the remove method to say "remove all elements starting from this index", e. g. index valid, count too large:

        val lb = collection.mutable.ListBuffer('a, 'b, 'c, 'd, 'e)
        
        lb remove (4, Int.MaxValue) // "Remove all items starting from index 4"
        

        I would probably just rule out this usage (I checked ArrayBuffer and UnrolledBuffer and both don't have this behvaiour, too) and – only if people actually complain – add a special method for this use case similar to trimStart/trimEnd (maybe trimFrom?).

        Show
        Simon Ochsenreither added a comment - As far as I see, there is only one alternative usage: People who used the remove method to say "remove all elements starting from this index", e. g. index valid, count too large: val lb = collection.mutable.ListBuffer('a, 'b, 'c, 'd, 'e) lb remove (4, Int.MaxValue) // "Remove all items starting from index 4" I would probably just rule out this usage (I checked ArrayBuffer and UnrolledBuffer and both don't have this behvaiour, too) and – only if people actually complain – add a special method for this use case similar to trimStart/trimEnd (maybe trimFrom?).
        Hide
        Jason Zaugg added a comment -

        Simon, I'm closing this ticket on the assumption that we forgot to do so after your patch was merged. Please reopen or open a new ticket if there is a residual problem that I've missed.

        Show
        Jason Zaugg added a comment - Simon, I'm closing this ticket on the assumption that we forgot to do so after your patch was merged. Please reopen or open a new ticket if there is a residual problem that I've missed.
        Hide
        Simon Ochsenreither added a comment -

        Mhhh, as far as I remember the ticket was open to remind us that we need to properly specify the behavior in error cases and check that all collections conform to this behavior.

        Show
        Simon Ochsenreither added a comment - Mhhh, as far as I remember the ticket was open to remind us that we need to properly specify the behavior in error cases and check that all collections conform to this behavior.

          People

          • Assignee:
            Simon Ochsenreither
            Reporter:
            Simon Ochsenreither
          • Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development