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.

5 files changed, 43 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.