Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
scabug opened this issue Nov 9, 2012 · 5 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Nov 9, 2012

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?

@scabug
Copy link
Author

scabug commented Nov 9, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6634?orig=1
Reporter: @soc
Affected Versions: 2.9.2, 2.10.0-RC2, 2.10.0, 2.11.0-M1

@scabug
Copy link
Author

scabug commented Nov 9, 2012

@odersky said:
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.

@scabug
Copy link
Author

scabug commented Nov 9, 2012

@soc said:
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?).

@scabug
Copy link
Author

scabug commented Nov 21, 2013

@retronym said:
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.

@scabug scabug closed this as completed Nov 21, 2013
@scabug
Copy link
Author

scabug commented Nov 21, 2013

@soc said:
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.

@scabug scabug added this to the 2.10.1 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants