From e8c85a37186b65561a3826b9889c9d06a69650da Mon Sep 17 00:00:00 2001
From: Heejong Lee <heejong@gmail.com>
Date: Sat, 6 Apr 2013 01:48:31 +0900
Subject: SI-7080 improve boundary value checking for BitSet

When BitSet accepts a very large integer such as Int.MaxValue,
integer overflow possibly occurs in the calculation of boundary
value "nwords * WordLength". This faulty boundary condition
causes empty-iterator problem like following:

scala> import collection.mutable.BitSet
import collection.mutable.BitSet

scala> val x = BitSet(Int.MaxValue)
x: scala.collection.mutable.BitSet = BitSet()

scala> x.iterator
res0: Iterator[Int] = empty iterator
---
 src/library/scala/collection/BitSetLike.scala     | 16 ++++++++++++----
 src/library/scala/collection/mutable/BitSet.scala |  5 +++--
 2 files changed, 15 insertions(+), 6 deletions(-)

(limited to 'src')

diff --git a/src/library/scala/collection/BitSetLike.scala b/src/library/scala/collection/BitSetLike.scala
index 034ed2b24a..9c4e710558 100644
--- a/src/library/scala/collection/BitSetLike.scala
+++ b/src/library/scala/collection/BitSetLike.scala
@@ -106,8 +106,8 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
     private var current = start
     private val end = nwords * WordLength
     def hasNext: Boolean = {
-      while (current < end && !self.contains(current)) current += 1
-      current < end
+      while (current != end && !self.contains(current)) current += 1
+      current != end
     }
     def next(): Int =
       if (hasNext) { val r = current; current += 1; r }
@@ -117,7 +117,10 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
   override def foreach[B](f: Int => B) {
     for (i <- 0 until nwords) {
       val w = word(i)
-      for (j <- i * WordLength until (i + 1) * WordLength) {
+      /* NOTE: `until` instead of `to` will not work here because
+         the maximum value of `(i + 1) * WordLength` could be
+         `Int.MaxValue + 1` (i.e. `Int.MinValue`). */
+      for (j <- i * WordLength to (i + 1) * WordLength - 1) {
         if ((w & (1L << j)) != 0L) f(j)
       }
     }
@@ -197,11 +200,15 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
   override def addString(sb: StringBuilder, start: String, sep: String, end: String) = {
     sb append start
     var pre = ""
-    for (i <- 0 until nwords * WordLength)
+    val max = nwords * WordLength
+    var i = 0
+    while(i != max) {
       if (contains(i)) {
         sb append pre append i
         pre = sep
       }
+      i += 1
+    }
     sb append end
   }
 
@@ -212,6 +219,7 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
 object BitSetLike {
   private[collection] val LogWL = 6
   private val WordLength = 64
+  private[collection] val MaxSize = (Int.MaxValue >> LogWL) + 1
 
   private[collection] def updateArray(elems: Array[Long], idx: Int, w: Long): Array[Long] = {
     var len = elems.length
diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala
index 397f8099eb..29c341590d 100644
--- a/src/library/scala/collection/mutable/BitSet.scala
+++ b/src/library/scala/collection/mutable/BitSet.scala
@@ -12,7 +12,7 @@ package scala.collection
 package mutable
 
 import generic._
-import BitSetLike.{LogWL, updateArray}
+import BitSetLike.{LogWL, MaxSize, updateArray}
 
 /** A class for mutable bitsets.
  *
@@ -63,9 +63,10 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int]
   }
 
   private def ensureCapacity(idx: Int) {
+    require(idx < MaxSize)
     if (idx >= nwords) {
       var newlen = nwords
-      while (idx >= newlen) newlen = newlen * 2
+      while (idx >= newlen) newlen = (newlen * 2) min MaxSize
       val elems1 = new Array[Long](newlen)
       Array.copy(elems, 0, elems1, 0, nwords)
       elems = elems1
-- 
cgit v1.2.3