Skip to content

Commit

Permalink
Get rid of unsafe type alias IterableCC and co
Browse files Browse the repository at this point in the history 
Avoid unexpected class casts due to potential misuse in
subclasses of the following cunning trick, which allowed
for centralized implementation of common factory methods,
assuming the right overrides are provided in subclasses:
`protected type IterableCC[X] = CC[X] @uncheckedVariance`

Risk of not overriding correctly illustrated by
https://gist.github.com/lrytz/fe09791208969f07e211c5c8601db125.
It's basically an encoding of MyType, which is only sound under
pretty severe restrictions, which are not enforced by the
compiler.

Instead, we mix in a default implementation of the various
factory methods whenever we are in a trait where the
collection's type is known (and of the regular shape CC[A] or
MapCC[K, V]). It would be nice if we could conditionally mix in
this trait into the *Ops traits whenever `C =:= CC[A]`, but we
don't have that kind of inheritance (private inheritance would
be nice too, I guess, since the `*FactoryDefaults` traits don't
really add much utility to the public signature of these
collection classes).

While we're at it, also add an `empty` method at the top of the
hierarchy to facilitate the switch to dotty's for comprehensions
(since we want the stdlibs between Scala 2 & 3 to be the same,
and 2.14 will try to only make backwards compatible changes from
2.13).

Motivated by the intersection of #7458, #7929, #7800 (better
refchecks and compiling with dotc revealed part of the problem)

🤯

Co-authored-by: Lukas Rytz <[email protected]>
  • Loading branch information
@adriaanm @lrytz
adriaanm and lrytz committed Apr 2, 2019
1 parent e29a44c commit a864ae0
Show file tree
Hide file tree
Showing 80 changed files with 494 additions and 320 deletions.
8 changes: 4 additions & 4 deletions src/library/scala/Enumeration.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -308,13 +308,13 @@ abstract class Enumeration (initial: Int) extends Serializable {
def flatMap(f: Value => IterableOnce[Value]): ValueSet = fromSpecific(new View.FlatMap(toIterable, f))

// necessary for disambiguation:
override def map[B](f: Value => B)(implicit @implicitNotFound(ValueSet.ordMsg) ev: Ordering[B]): SortedIterableCC[B] =
override def map[B](f: Value => B)(implicit @implicitNotFound(ValueSet.ordMsg) ev: Ordering[B]): immutable.SortedSet[B] =
super[SortedSet].map[B](f)
override def flatMap[B](f: Value => IterableOnce[B])(implicit @implicitNotFound(ValueSet.ordMsg) ev: Ordering[B]): SortedIterableCC[B] =
override def flatMap[B](f: Value => IterableOnce[B])(implicit @implicitNotFound(ValueSet.ordMsg) ev: Ordering[B]): immutable.SortedSet[B] =
super[SortedSet].flatMap[B](f)
override def zip[B](that: IterableOnce[B])(implicit @implicitNotFound(ValueSet.zipOrdMsg) ev: Ordering[(Value, B)]): SortedIterableCC[(Value, B)] =
override def zip[B](that: IterableOnce[B])(implicit @implicitNotFound(ValueSet.zipOrdMsg) ev: Ordering[(Value, B)]): immutable.SortedSet[(Value, B)] =
super[SortedSet].zip[B](that)
override def collect[B](pf: PartialFunction[Value, B])(implicit @implicitNotFound(ValueSet.ordMsg) ev: Ordering[B]): SortedIterableCC[B] =
override def collect[B](pf: PartialFunction[Value, B])(implicit @implicitNotFound(ValueSet.ordMsg) ev: Ordering[B]): immutable.SortedSet[B] =
super[SortedSet].collect[B](pf)
}

Expand Down
16 changes: 8 additions & 8 deletions src/library/scala/collection/BuildFrom.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -42,14 +42,14 @@ object BuildFrom extends BuildFromLowPriority1 {
/** Build the source collection type from a MapOps */
implicit def buildFromMapOps[CC[X, Y] <: Map[X, Y] with MapOps[X, Y, CC, _], K0, V0, K, V]: BuildFrom[CC[K0, V0], (K, V), CC[K, V]] = new BuildFrom[CC[K0, V0], (K, V), CC[K, V]] {
//TODO: Reuse a prototype instance
def newBuilder(from: CC[K0, V0]): Builder[(K, V), CC[K, V]] = from.mapFactory.newBuilder[K, V]
def fromSpecific(from: CC[K0, V0])(it: IterableOnce[(K, V)]): CC[K, V] = from.mapFactory.from(it)
def newBuilder(from: CC[K0, V0]): Builder[(K, V), CC[K, V]] = (from: MapOps[K0, V0, CC, _]).mapFactory.newBuilder[K, V]
def fromSpecific(from: CC[K0, V0])(it: IterableOnce[(K, V)]): CC[K, V] = (from: MapOps[K0, V0, CC, _]).mapFactory.from(it)
}

/** Build the source collection type from a SortedMapOps */
implicit def buildFromSortedMapOps[CC[X, Y] <: SortedMap[X, Y] with SortedMapOps[X, Y, CC, _], K0, V0, K : Ordering, V]: BuildFrom[CC[K0, V0], (K, V), CC[K, V]] = new BuildFrom[CC[K0, V0], (K, V), CC[K, V]] {
def newBuilder(from: CC[K0, V0]): Builder[(K, V), CC[K, V]] = from.sortedMapFactory.newBuilder[K, V]
def fromSpecific(from: CC[K0, V0])(it: IterableOnce[(K, V)]): CC[K, V] = from.sortedMapFactory.from(it)
def newBuilder(from: CC[K0, V0]): Builder[(K, V), CC[K, V]] = (from: SortedMapOps[K0, V0, CC, _]).sortedMapFactory.newBuilder[K, V]
def fromSpecific(from: CC[K0, V0])(it: IterableOnce[(K, V)]): CC[K, V] = (from: SortedMapOps[K0, V0, CC, _]).sortedMapFactory.from(it)
}

implicit def buildFromBitSet[C <: BitSet with BitSetOps[C]]: BuildFrom[C, Int, C] =
Expand Down Expand Up @@ -88,8 +88,8 @@ trait BuildFromLowPriority1 extends BuildFromLowPriority2 {

/** Build the source collection type from an Iterable with SortedOps */
implicit def buildFromSortedSetOps[CC[X] <: SortedSet[X] with SortedSetOps[X, CC, _], A0, A : Ordering]: BuildFrom[CC[A0], A, CC[A]] = new BuildFrom[CC[A0], A, CC[A]] {
def newBuilder(from: CC[A0]): Builder[A, CC[A]] = from.sortedIterableFactory.newBuilder[A]
def fromSpecific(from: CC[A0])(it: IterableOnce[A]): CC[A] = from.sortedIterableFactory.from(it)
def newBuilder(from: CC[A0]): Builder[A, CC[A]] = (from: SortedSetOps[A0, CC, _]).sortedIterableFactory.newBuilder[A]
def fromSpecific(from: CC[A0])(it: IterableOnce[A]): CC[A] = (from: SortedSetOps[A0, CC, _]).sortedIterableFactory.from(it)
}

implicit def fallbackStringCanBuildFrom[A]: BuildFrom[String, A, immutable.IndexedSeq[A]] =
Expand All @@ -103,8 +103,8 @@ trait BuildFromLowPriority2 {
/** Build the source collection type from an IterableOps */
implicit def buildFromIterableOps[CC[X] <: Iterable[X] with IterableOps[X, CC, _], A0, A]: BuildFrom[CC[A0], A, CC[A]] = new BuildFrom[CC[A0], A, CC[A]] {
//TODO: Reuse a prototype instance
def newBuilder(from: CC[A0]): Builder[A, CC[A]] = from.iterableFactory.newBuilder[A]
def fromSpecific(from: CC[A0])(it: IterableOnce[A]): CC[A] = from.iterableFactory.from(it)
def newBuilder(from: CC[A0]): Builder[A, CC[A]] = (from: IterableOps[A0, CC, _]).iterableFactory.newBuilder[A]
def fromSpecific(from: CC[A0])(it: IterableOnce[A]): CC[A] = (from: IterableOps[A0, CC, _]).iterableFactory.from(it)
}

implicit def buildFromIterator[A]: BuildFrom[Iterator[_], A, Iterator[A]] = new BuildFrom[Iterator[_], A, Iterator[A]] {
Expand Down
7 changes: 6 additions & 1 deletion src/library/scala/collection/IndexedSeq.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -14,15 +14,20 @@ package scala
package collection

import scala.annotation.tailrec
import scala.annotation.unchecked.uncheckedVariance
import scala.collection.Searching.{Found, InsertionPoint, SearchResult}
import scala.collection.Stepper.EfficientSplit
import scala.language.higherKinds
import scala.math.Ordering

/** Base trait for indexed sequences that have efficient `apply` and `length` */
trait IndexedSeq[+A] extends Seq[A] with IndexedSeqOps[A, IndexedSeq, IndexedSeq[A]] {
trait IndexedSeq[+A] extends Seq[A]
with IndexedSeqOps[A, IndexedSeq, IndexedSeq[A]]
with IterableFactoryDefaults[A @uncheckedVariance, IndexedSeq] {
@deprecatedOverriding("Compatibility override", since="2.13.0")
override protected[this] def stringPrefix: String = "IndexedSeq"

override def iterableFactory: SeqFactory[IndexedSeq] = IndexedSeq
}

@SerialVersionUID(3L)
Expand Down
179 changes: 139 additions & 40 deletions src/library/scala/collection/Iterable.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -25,25 +25,16 @@ import scala.collection.View.{LeftPartitionMapped, RightPartitionMapped}
* @define Coll `Iterable`
* @define coll iterable collection
*/
trait Iterable[+A] extends IterableOnce[A] with IterableOps[A, Iterable, Iterable[A]] {
trait Iterable[+A] extends IterableOnce[A]
with IterableOps[A, Iterable, Iterable[A]]
with IterableFactoryDefaults[A @uncheckedVariance, Iterable] {

// The collection itself
final def toIterable: this.type = this

final protected def coll: this.type = this

protected def fromSpecific(coll: IterableOnce[A @uncheckedVariance]): IterableC @uncheckedVariance = iterableFactory.from(coll)
protected def newSpecificBuilder: Builder[A, IterableC] @uncheckedVariance = iterableFactory.newBuilder[A]

/**
* @note This operation '''has''' to be overridden by concrete collection classes to effectively
* return an `IterableFactory[IterableCC]`. The implementation in `Iterable` only returns
* an `IterableFactory[Iterable]`, but the compiler will '''not''' throw an error if the
* effective `IterableCC` type constructor is more specific than `Iterable`.
*
* @return The factory of this collection.
*/
def iterableFactory: IterableFactory[IterableCC] = Iterable
def iterableFactory: IterableFactory[Iterable] = Iterable

@deprecated("Iterable.seq always returns the iterable itself", "2.13.0")
def seq: this.type = this
Expand Down Expand Up @@ -140,25 +131,6 @@ trait Iterable[+A] extends IterableOnce[A] with IterableOps[A, Iterable, Iterabl
* and may be nondeterministic.
*/
trait IterableOps[+A, +CC[_], +C] extends Any with IterableOnce[A] with IterableOnceOps[A, CC, C] {

/**
* Type alias to `CC`. It is used to provide a default implementation of the `iterableFactory`
* operation.
*
* Due to the `@uncheckedVariance` annotation, usage of this type member can be unsound and is
* therefore not recommended.
*/
protected type IterableCC[X] = CC[X] @uncheckedVariance

/**
* Type alias to `C`. It is used to provide a default implementation of the `fromSpecific`
* and `newSpecificBuilder` operations.
*
* Due to the `@uncheckedVariance` annotation, usage of this type member can be unsound and is
* therefore not recommended.
*/
protected type IterableC = C @uncheckedVariance

/**
* @return This collection as an `Iterable[A]`. No new collection will be built if `this` is already an `Iterable[A]`.
*/
Expand Down Expand Up @@ -188,21 +160,30 @@ trait IterableOps[+A, +CC[_], +C] extends Any with IterableOnce[A] with Iterable
* the elements of the resulting collections). In other words, this methods defines
* the evaluation model of the collection.
*
* @note When implementing a custom collection type and refining `C` to the new type, this
* method needs to be overridden (the compiler will issue an error otherwise). In the
* common case where `C =:= CC[A]`, this can be done by mixing in the
* [[IterableFactoryDefaults]] trait, which implements the method using
* [[iterableFactory]].
*
* @note As witnessed by the `@uncheckedVariance` annotation, using this method
* might be unsound. However, as long as it is called with an
* `Iterable[A]` obtained from `this` collection (as it is the case in the
* implementations of operations where we use a `View[A]`), it is safe.
*/
protected def fromSpecific(coll: IterableOnce[A @uncheckedVariance]): C

/**
* @return The companion object of this ${coll}, providing various factory methods.
/** The companion object of this ${coll}, providing various factory methods.
*
* @note When implementing a custom collection type and refining `CC` to the new type, this
* method needs to be overridden to return a factory for the new type (the compiler will
* issue an error otherwise).
*/
def iterableFactory: IterableFactory[IterableCC]
def iterableFactory: IterableFactory[CC]

@deprecated("Use iterableFactory instead", "2.13.0")
@deprecatedOverriding("Use iterableFactory instead", "2.13.0")
@`inline` def companion: IterableFactory[IterableCC] = iterableFactory
@`inline` def companion: IterableFactory[CC] = iterableFactory

/**
* @return a strict builder for the same collection type.
Expand All @@ -212,12 +193,24 @@ trait IterableOps[+A, +CC[_], +C] extends Any with IterableOnce[A] with Iterable
* As a consequence, operations should preferably be implemented with `fromSpecific`
* instead of this method.
*
* @note When implementing a custom collection type and refining `C` to the new type, this
* method needs to be overridden (the compiler will issue an error otherwise). In the
* common case where `C =:= CC[A]`, this can be done by mixing in the
* [[IterableFactoryDefaults]] trait, which implements the method using
* [[iterableFactory]].
*
* @note As witnessed by the `@uncheckedVariance` annotation, using this method might
* be unsound. However, as long as the returned builder is only fed
* with `A` values taken from `this` instance, it is safe.
*/
protected def newSpecificBuilder: Builder[A @uncheckedVariance, C]

/** The empty iterable of the same type as this iterable
*
* @return an empty iterable of type `C`.
*/
def empty: C = fromSpecific(Nil)

/** Selects the first element of this $coll.
* $orderDependent
* @return the first element of this $coll.
Expand Down Expand Up @@ -830,10 +823,10 @@ trait IterableOps[+A, +CC[_], +C] extends Any with IterableOnce[A] with Iterable
}

@deprecated("Use ++ instead of ++: for collections of type Iterable", "2.13.0")
def ++:[B >: A](that: IterableOnce[B]): IterableCC[B] =
(iterableFactory.from(that).asInstanceOf[Iterable[B]] ++ coll.asInstanceOf[Iterable[B]]).asInstanceOf[IterableCC[B]]
// These casts are needed because C and CC do not have the proper constraints.
// Adding those constraints would require a lot of boilerplate in many classes.
def ++:[B >: A](that: IterableOnce[B]): CC[B] = iterableFactory.from(that match {
case xs: Iterable[B] => new View.Concat(xs, this)
case _ => that.iterator ++ iterator
})
}

object IterableOps {
Expand Down Expand Up @@ -912,3 +905,109 @@ object Iterable extends IterableFactory.Delegate[Iterable](immutable.Iterable) {

/** Explicit instantiation of the `Iterable` trait to reduce class file size in subclasses. */
abstract class AbstractIterable[+A] extends Iterable[A]

/** This trait provides default implementations for the factory methods `fromSpecific` and
* `newSpecificBuilder` that need to be refined when implementing a collection type that refines
* the `CC` and `C` type parameters.
*
* The default implementations in this trait can be used in the common case when `CC[A]` is the
* same as `C`.
*/
trait IterableFactoryDefaults[A, +CC[x] <: IterableOps[x, CC, CC[x]]] extends IterableOps[A, CC, CC[A]] {
protected def fromSpecific(coll: IterableOnce[A]): CC[A] = iterableFactory.from(coll)
protected def newSpecificBuilder: Builder[A, CC[A]] = iterableFactory.newBuilder[A]

// overridden for efficiency, since we know CC[A] =:= C
override def empty: CC[A] = iterableFactory.empty
}

/** This trait provides default implementations for the factory methods `fromSpecific` and
* `newSpecificBuilder` that need to be refined when implementing a collection type that refines
* the `CC` and `C` type parameters. It is used for collections that have an additional constraint,
* expressed by the `evidenceIterableFactory` method.
*
* The default implementations in this trait can be used in the common case when `CC[A]` is the
* same as `C`.
*/
trait EvidenceIterableFactoryDefaults[A, +CC[x] <: IterableOps[x, CC, CC[x]], Ev[_]] extends IterableOps[A, CC, CC[A]] {
protected def evidenceIterableFactory: EvidenceIterableFactory[CC, Ev]
implicit protected def iterableEvidence: Ev[A]
override protected def fromSpecific(coll: IterableOnce[A]): CC[A] = evidenceIterableFactory.from(coll)
override protected def newSpecificBuilder: Builder[A, CC[A]] = evidenceIterableFactory.newBuilder[A]
override def empty: CC[A] = evidenceIterableFactory.empty
}

/** This trait provides default implementations for the factory methods `fromSpecific` and
* `newSpecificBuilder` that need to be refined when implementing a collection type that refines
* the `CC` and `C` type parameters. It is used for sorted sets.
*
* Note that in sorted sets, the `CC` type of the set is not the same as the `CC` type for the
* underlying iterable (which is fixed to `Set` in [[SortedSetOps]]). This trait has therefore
* two type parameters `CC` and `WithFilterCC`. The `withFilter` method inherited from
* `IterableOps` is overridden with a compatible default implementation.
*
* The default implementations in this trait can be used in the common case when `CC[A]` is the
* same as `C`.
*/
trait SortedSetFactoryDefaults[A,
+CC[X] <: SortedSet[X] with SortedSetOps[X, CC, CC[X]],
+WithFilterCC[x] <: IterableOps[x, WithFilterCC, WithFilterCC[x]] with Set[x]] extends SortedSetOps[A, CC, CC[A]] {
self: IterableOps[A, WithFilterCC, _] =>

override protected def fromSpecific(coll: IterableOnce[A]): CC[A] = sortedIterableFactory.from(coll)
override protected def newSpecificBuilder: mutable.Builder[A, CC[A]] = sortedIterableFactory.newBuilder[A]
override def empty: CC[A] = sortedIterableFactory.empty

override def withFilter(p: A => Boolean): SortedSetOps.WithFilter[A, WithFilterCC, CC] =
new SortedSetOps.WithFilter[A, WithFilterCC, CC](this, p)
}


/** This trait provides default implementations for the factory methods `fromSpecific` and
* `newSpecificBuilder` that need to be refined when implementing a collection type that refines
* the `CC` and `C` type parameters. It is used for maps.
*
* Note that in maps, the `CC` type of the map is not the same as the `CC` type for the
* underlying iterable (which is fixed to `Map` in [[MapOps]]). This trait has therefore
* two type parameters `CC` and `WithFilterCC`. The `withFilter` method inherited from
* `IterableOps` is overridden with a compatible default implementation.
*
* The default implementations in this trait can be used in the common case when `CC[A]` is the
* same as `C`.
*/
trait MapFactoryDefaults[K, V,
+CC[x, y] <: IterableOps[(x, y), Iterable, Iterable[(x, y)]],
+WithFilterCC[x] <: IterableOps[x, WithFilterCC, WithFilterCC[x]] with Iterable[x]] extends MapOps[K, V, CC, CC[K, V]] with IterableOps[(K, V), WithFilterCC, CC[K, V]] {
override protected def fromSpecific(coll: IterableOnce[(K, V)]): CC[K, V] = mapFactory.from(coll)
override protected def newSpecificBuilder: mutable.Builder[(K, V), CC[K, V]] = mapFactory.newBuilder[K, V]
override def empty: CC[K, V] = mapFactory.empty

override def withFilter(p: ((K, V)) => Boolean): MapOps.WithFilter[K, V, WithFilterCC, CC] =
new MapOps.WithFilter[K, V, WithFilterCC, CC](this, p)
}

/** This trait provides default implementations for the factory methods `fromSpecific` and
* `newSpecificBuilder` that need to be refined when implementing a collection type that refines
* the `CC` and `C` type parameters. It is used for sorted maps.
*
* Note that in sorted maps, the `CC` type of the map is not the same as the `CC` type for the
* underlying map (which is fixed to `Map` in [[SortedMapOps]]). This trait has therefore
* three type parameters `CC`, `WithFilterCC` and `UnsortedCC`. The `withFilter` method inherited
* from `IterableOps` is overridden with a compatible default implementation.
*
* The default implementations in this trait can be used in the common case when `CC[A]` is the
* same as `C`.
*/
trait SortedMapFactoryDefaults[K, V,
+CC[x, y] <: Map[x, y] with SortedMapOps[x, y, CC, CC[x, y]] with UnsortedCC[x, y],
+WithFilterCC[x] <: IterableOps[x, WithFilterCC, WithFilterCC[x]] with Iterable[x],
+UnsortedCC[x, y] <: Map[x, y]] extends SortedMapOps[K, V, CC, CC[K, V]] with MapOps[K, V, UnsortedCC, CC[K, V]] {
self: IterableOps[(K, V), WithFilterCC, _] =>

override def empty: CC[K, V] = sortedMapFactory.empty
override protected def fromSpecific(coll: IterableOnce[(K, V@uncheckedVariance)]): CC[K, V] = sortedMapFactory.from(coll)
override protected def newSpecificBuilder: mutable.Builder[(K, V@uncheckedVariance), CC[K, V@uncheckedVariance]] = sortedMapFactory.newBuilder[K, V]

override def withFilter(p: ((K, V)) => Boolean): collection.SortedMapOps.WithFilter[K, V, WithFilterCC, UnsortedCC, CC] =
new collection.SortedMapOps.WithFilter[K, V, WithFilterCC, UnsortedCC, CC](this, p)
}
7 changes: 6 additions & 1 deletion src/library/scala/collection/LinearSeq.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -14,15 +14,20 @@ package scala
package collection

import scala.annotation.tailrec
import scala.annotation.unchecked.uncheckedVariance
import scala.language.higherKinds

/** Base trait for linearly accessed sequences that have efficient `head` and
* `tail` operations.
* Known subclasses: List, LazyList
*/
trait LinearSeq[+A] extends Seq[A] with LinearSeqOps[A, LinearSeq, LinearSeq[A]] {
trait LinearSeq[+A] extends Seq[A]
with LinearSeqOps[A, LinearSeq, LinearSeq[A]]
with IterableFactoryDefaults[A @uncheckedVariance, LinearSeq] {
@deprecatedOverriding("Compatibility override", since="2.13.0")
override protected[this] def stringPrefix: String = "LinearSeq"

override def iterableFactory: SeqFactory[LinearSeq] = LinearSeq
}

@SerialVersionUID(3L)
Expand Down
Loading

0 comments on commit a864ae0

Please sign in to comment.