SI-8346 Re-established soundness of toSet (element type widening)

toSet needs to rebuild some child classes, but not others, as toSet is
allowed to widen element types (which the invariant Set normally cannot do),
and some sets rely upon their invariance.  Thus, sets that rely upon their
invariance now rebuild themselves into a generic set upon toSet, while those
that do not just sit there.

Note: there was a similar patch previously that fixed the same problem, but
this is a reimplementation to circumvent license issues.

Note: the newBuilder method was benchmarked as (surprisingly!) the most
efficient way to create small sets, so it is used where sets may need to
be rebuild.

6 files changed, 124 insertions, 5 deletions

diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index 6851ab6bc7..27b2bfdde7 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -194,6 +194,7 @@ class HashSet[A] extends AbstractSet[A]
 
   protected def writeReplace(): AnyRef = new HashSet.SerializationProxy(this)
 
+  override def toSet[B >: A]: Set[B] = this.asInstanceOf[HashSet[B]]
 }
 
 /** $factoryInfo
diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala
index 2e17677359..adc975479a 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -179,4 +179,6 @@ class ListSet[A] extends AbstractSet[A]
 
     override def tail: ListSet[A] = self
   }
+  
+  override def toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]]
 }
diff --git a/src/library/scala/collection/immutable/MapLike.scala b/src/library/scala/collection/immutable/MapLike.scala
index 94a5b7929a..bd5b9c9faf 100644
--- a/src/library/scala/collection/immutable/MapLike.scala
+++ b/src/library/scala/collection/immutable/MapLike.scala
@@ -113,6 +113,11 @@ self =>
     override def - (elem: A): immutable.Set[A] =
       if (this(elem)) immutable.Set[A]() ++ this - elem
       else this
+      
+    // ImmutableDefaultKeySet is only protected, so we won't warn on override.
+    // Someone could override in a way that makes widening not okay
+    // (e.g. by overriding +, though the version in this class is fine)
+    override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set[B]]
   }
 
   /** This function transforms all the values of mappings contained
diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala
index 0fbf7942d4..a115469b83 100644
--- a/src/library/scala/collection/immutable/Set.scala
+++ b/src/library/scala/collection/immutable/Set.scala
@@ -35,12 +35,22 @@ trait Set[A] extends Iterable[A]
   override def companion: GenericCompanion[Set] = Set
   
   
-  /** Returns this $coll as an immutable map.
-   *  
-   *  A new map will not be built; lazy collections will stay lazy.
+  /** Returns this $coll as an immutable set, perhaps accepting a
+   *  wider range of elements.  Since it already is an
+   *  immutable set, it will only be rebuilt if the underlying structure
+   *  cannot be expanded to include arbitrary element types.
+   *  For instance, `BitSet` and `SortedSet` will be rebuilt, as
+   *  they require `Int` and sortable elements respectively.
+   *
+   *  When in doubt, the set will be rebuilt.  Rebuilt sets never
+   *  need to be rebuilt again.
    */
-  @deprecatedOverriding("Immutable sets should do nothing on toSet but return themselves cast as a Set.", "2.11.0")
-  override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set[B]]
+  override def toSet[B >: A]: Set[B] = {
+      // This way of building sets typically has the best benchmarks, surprisingly!
+    val sb = Set.newBuilder[B]
+    foreach(sb += _)
+    sb.result()
+  }
   
   override def seq: Set[A] = this
   protected override def parCombiner = ParSet.newCombiner[A] // if `immutable.SetLike` gets introduced, please move this there!
@@ -62,6 +72,7 @@ object Set extends ImmutableSetFactory[Set] {
     def - (elem: Any): Set[Any] = this
     def iterator: Iterator[Any] = Iterator.empty
     override def foreach[U](f: Any =>  U): Unit = {}
+    override def toSet[B >: Any]: Set[B] = this.asInstanceOf[Set[B]]
   }
   private[collection] def emptyInstance: Set[Any] = EmptySet
 
@@ -92,6 +103,10 @@ object Set extends ImmutableSetFactory[Set] {
       if (f(elem1)) Some(elem1)
       else None
     }
+    // Why is Set1 non-final?  Need to fix that!
+    @deprecatedOverriding("This immutable set should do nothing on toSet but cast itself to a Set with a wider element type.", "2.11.8")
+    override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set1[B]]
+
   }
 
   /** An optimized representation for immutable sets of size 2 */
@@ -123,6 +138,9 @@ object Set extends ImmutableSetFactory[Set] {
       else if (f(elem2)) Some(elem2)
       else None
     }
+    // Why is Set2 non-final?  Need to fix that!
+    @deprecatedOverriding("This immutable set should do nothing on toSet but cast itself to a Set with a wider element type.", "2.11.8")
+    override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set2[B]]
   }
 
   /** An optimized representation for immutable sets of size 3 */
@@ -156,6 +174,9 @@ object Set extends ImmutableSetFactory[Set] {
       else if (f(elem3)) Some(elem3)
       else None
     }
+    // Why is Set3 non-final?  Need to fix that!
+    @deprecatedOverriding("This immutable set should do nothing on toSet but cast itself to a Set with a wider element type.", "2.11.8")
+    override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set3[B]]
   }
 
   /** An optimized representation for immutable sets of size 4 */
@@ -191,6 +212,9 @@ object Set extends ImmutableSetFactory[Set] {
       else if (f(elem4)) Some(elem4)
       else None
     }
+    // Why is Set4 non-final?  Need to fix that!
+    @deprecatedOverriding("This immutable set should do nothing on toSet but cast itself to a Set with a wider element type.", "2.11.8")
+    override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set4[B]]
   }
 }
 
diff --git a/src/library/scala/collection/immutable/SortedMap.scala b/src/library/scala/collection/immutable/SortedMap.scala
index f1493551ab..682788e18e 100644
--- a/src/library/scala/collection/immutable/SortedMap.scala
+++ b/src/library/scala/collection/immutable/SortedMap.scala
@@ -53,6 +53,12 @@ self =>
       val map = self.rangeImpl(from, until)
       new map.DefaultKeySortedSet
     }
+    override def toSet[C >: A]: Set[C] = {
+      // This way of building sets typically has the best benchmarks, surprisingly!
+      val sb = Set.newBuilder[C]
+      foreach(sb += _)
+      sb.result()
+    }
   }
 
   /** Add a key/value pair to this map.
diff --git a/test/junit/scala/collection/immutable/SetTests.scala b/test/junit/scala/collection/immutable/SetTests.scala
new file mode 100644
index 0000000000..28c7864359
--- /dev/null
+++ b/test/junit/scala/collection/immutable/SetTests.scala
@@ -0,0 +1,81 @@
+package scala.collection.immutable
+
+import org.junit.Assert._
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+
+@RunWith(classOf[JUnit4])
+class SetTests {
+  @Test
+  def test_SI8346_toSet_soundness(): Unit = {
+    val any2stringadd = "Disabled string conversions so as not to get confused!"
+    
+    def any[A](set: Set[A]): Set[Any] = {
+      val anyset = set.toSet[Any]
+      assert((anyset + "fish") contains "fish")
+      anyset
+    }
+
+    // Make sure default immutable Set does not rebuild itself on widening with toSet
+    // Need to cover 0, 1, 2, 3, 4 elements as special cases
+    var si = Set.empty[Int]
+    assert(si eq si.toSet[Any])
+    for (i <- 1 to 5) {
+      val s1 = Set(Array.range(1, i+1): _*)
+      val s2 = si + i
+      val s1a = any(s1)
+      val s2a = any(s2)
+      assert(s1 eq s1a)
+      assert(s2 eq s2a)
+      si = s2
+    }
+
+    // Make sure BitSet correctly rebuilds itself on widening with toSet
+    // Need to cover empty, values 0-63, values 0-127 as special cases
+    val bitsets = Seq(BitSet.empty, BitSet(23), BitSet(23, 99), BitSet(23, 99, 141))
+    bitsets.foreach{ b =>
+      val ba = any(b)
+      assert(b ne ba)
+      assertEquals(b, ba)
+    }
+
+    // Make sure HashSet (and by extension, its implementing class HashTrieSet)
+    // does not rebuild itself on widening by toSet
+    val hashset = HashSet(1, 3, 5, 7)
+    val hashseta = any(hashset)
+    assert(hashset eq hashseta)
+
+    // Make sure ListSet does not rebuild itself on widening by toSet
+    // (Covers Node also, since it subclasses ListSet)
+    val listset = ListSet(1, 3, 5, 7)
+    val listseta = any(listset)
+    assert(listset eq listseta)
+
+    // Make sure SortedSets correctly rebuild themselves on widening with toSet
+    // Covers TreeSet and keySet of SortedMap also
+    val sortedsets = Seq(
+      SortedSet.empty[Int], SortedSet(5), SortedSet(1,2,3,5,4),
+      SortedMap(1 -> "cod", 2 -> "herring").keySet
+    )
+    sortedsets.foreach{ set => 
+      val seta = any(set)
+      assert(set ne seta)
+      assertEquals(set, seta)
+    }
+
+    // Make sure ValueSets correctly rebuild themselves on widening with toSet
+    object WeekDay extends Enumeration {
+      type WeekDay = Value
+      val Mon, Tue, Wed, Thu, Fri, Sat, Sun = Value
+    }
+    val valuesa = any(WeekDay.values)
+    assert(WeekDay.values ne valuesa)
+    assertEquals(WeekDay.values, valuesa)
+
+    // Make sure regular Map keySets do not rebuild themselves on widening with toSet
+    val mapset = Map(1 -> "cod", 2 -> "herring").keySet
+    val mapseta = any(mapset)
+    assert(mapset eq mapseta)
+  }
+}