SI-9581 Fix overflow on Vector take and drop methods

ruippeixotog · ruippeixotog · commit c17b18e173e0 · 2015-12-06T19:25:00.000Z
Fixes the index/length comparison in `Vector#take` and `Vector#drop` so that they handle all possible integer values.

Given the collection's invariants `startIndex &gt;= endIndex` and `0 &gt;= startIndex, endIndex`, it is sufficient to change the arithmetic in the comparison as done in this commit to avoid overflows. As cases when `n &lt;= 0` are handled beforehand, `endIndex - n` cannot overflow, contrary to `startIndex + n`. If without the danger of overflows the condition yields true, on the other hand, `startIndex + n` cannot overflow as it is smaller than `endIndex` (as the previous formulation of the condition shows).
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
@@ -156,7 +156,7 @@ override def companion: GenericCompanion[Vector] = Vector
   override def take(n: Int): Vector[A] = {
     if (n <= 0)
       Vector.empty
-    else if (startIndex + n < endIndex)
+    else if (startIndex < endIndex - n)
       dropBack0(startIndex + n)
     else
       this
@@ -165,7 +165,7 @@ override def companion: GenericCompanion[Vector] = Vector
   override def drop(n: Int): Vector[A] = {
     if (n <= 0)
       this
-    else if (startIndex + n < endIndex)
+    else if (startIndex < endIndex - n)
       dropFront0(startIndex + n)
     else
       Vector.empty
diff --git a/test/junit/scala/collection/immutable/VectorTest.scala b/test/junit/scala/collection/immutable/VectorTest.scala
@@ -0,0 +1,30 @@
+package scala.collection.immutable
+
+import org.junit.Assert._
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.junit.Test
+
+@RunWith(classOf[JUnit4])
+class VectorTest {
+
+  @Test
+  def hasCorrectDropAndTakeMethods() {
+    val v = Vector(0) ++ Vector(1 to 64: _*)
+
+    assertEquals(Vector(0, 1), v take 2)
+    assertEquals(Vector(63, 64), v takeRight 2)
+    assertEquals(Vector(2 to 64: _*), v drop 2)
+    assertEquals(Vector(0 to 62: _*), v dropRight 2)
+
+    assertEquals(v, v take Int.MaxValue)
+    assertEquals(v, v takeRight Int.MaxValue)
+    assertEquals(Vector.empty[Int], v drop Int.MaxValue)
+    assertEquals(Vector.empty[Int], v dropRight Int.MaxValue)
+
+    assertEquals(Vector.empty[Int], v take Int.MinValue)
+    assertEquals(Vector.empty[Int], v takeRight Int.MinValue)
+    assertEquals(v, v drop Int.MinValue)
+    assertEquals(v, v dropRight Int.MinValue)
+  }
+}
