SI-8910 BitSet sometimes uses exponential memory.

Because of an off-by-one error in scala.collection.mutable.BitSet, where a
function (ensureCapacity) is passed a list length instead of an index, when
^=, &=, |=, or &~= are passed BitSets with the same internal capacity as the
set the method is being invoked on, the size of the first BitSet is needlessly
doubled.

This patch simply changes the ensureCapacity calls to pass the last index of
the list, instead of the raw length. In addition, add documentation to
ensureCapacity to try and stop something similar from happening in the future.

2 files changed, 26 insertions, 4 deletions

diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala
index 43d23acc1a..faa4155317 100644
--- a/src/library/scala/collection/mutable/BitSet.scala
+++ b/src/library/scala/collection/mutable/BitSet.scala
@@ -110,7 +110,7 @@ class BitSet(protected final var elems: Array[Long]) extends AbstractSet[Int]
    *  @return  the bitset itself.
    */
   def |= (other: BitSet): this.type = {
-    ensureCapacity(other.nwords)
+    ensureCapacity(other.nwords - 1)
     for (i <- 0 until other.nwords)
       elems(i) = elems(i) | other.word(i)
     this
@@ -121,7 +121,7 @@ class BitSet(protected final var elems: Array[Long]) extends AbstractSet[Int]
    *  @return  the bitset itself.
    */
   def &= (other: BitSet): this.type = {
-    ensureCapacity(other.nwords)
+    ensureCapacity(other.nwords - 1)
     for (i <- 0 until other.nwords)
       elems(i) = elems(i) & other.word(i)
     this
@@ -132,7 +132,7 @@ class BitSet(protected final var elems: Array[Long]) extends AbstractSet[Int]
    *  @return  the bitset itself.
    */
   def ^= (other: BitSet): this.type = {
-    ensureCapacity(other.nwords)
+    ensureCapacity(other.nwords - 1)
     for (i <- 0 until other.nwords)
       elems(i) = elems(i) ^ other.word(i)
     this
@@ -143,7 +143,7 @@ class BitSet(protected final var elems: Array[Long]) extends AbstractSet[Int]
    *  @return  the bitset itself.
    */
   def &~= (other: BitSet): this.type = {
-    ensureCapacity(other.nwords)
+    ensureCapacity(other.nwords - 1)
     for (i <- 0 until other.nwords)
       elems(i) = elems(i) & ~other.word(i)
     this
diff --git a/test/junit/scala/collection/mutable/BitSetTest.scala b/test/junit/scala/collection/mutable/BitSetTest.scala
new file mode 100644
index 0000000000..8d164b50d4
--- /dev/null
+++ b/test/junit/scala/collection/mutable/BitSetTest.scala
@@ -0,0 +1,22 @@
+package scala.collection.mutable
+
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.junit.{Test, Ignore}
+
+@RunWith(classOf[JUnit4])
+class BitSetTest {
+  // Test for SI-8910
+  @Test def capacityExpansionTest() {
+    val bitSet = BitSet.empty
+    val size   = bitSet.toBitMask.length
+    bitSet ^= bitSet
+    assert(bitSet.toBitMask.length == size, "Capacity of bitset changed after ^=")
+    bitSet |= bitSet
+    assert(bitSet.toBitMask.length == size, "Capacity of bitset changed after |=")
+    bitSet &= bitSet
+    assert(bitSet.toBitMask.length == size, "Capacity of bitset changed after &=")
+    bitSet &~= bitSet
+    assert(bitSet.toBitMask.length == size, "Capacity of bitset changed after &~=")
+  }
+}