Remove some `@uncheckedVariance`s, introduce `empty` in `Iterable`. #7929

adriaanm · 2019-03-26T19:57:50Z

Avoid unexpected class casts due to protected type IterableCC[X] = CC[X] @uncheckedVariance -- when misused in subclasses. Risk 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)

adriaanm · 2019-03-26T20:03:34Z

Another random thought: can we select a type from the companion object that's returned by the factory, and hang the more precise collection type off of that?

src/library/scala/collection/Iterable.scala

src/library/scala/collection/MapView.scala

src/library/scala/collection/mutable/ArrayDeque.scala

src/library/scala/collection/mutable/Map.scala

julienrf · 2019-03-26T20:48:21Z

Another random thought: can we select a type from the companion object that's returned by the factory, and hang the more precise collection type off of that?

Something like that?

trait IterableOps[+A, +CC[_], +C] {
  val iterableFactory: IterableFactory[CC] { type Coll[X] <: C }
  def fromSpecific(source: IterableOnce[A]): C = iterableFactory.from(source)
}

trait IterableFactory[CC[_]] {
  type Coll[A] = CC[A]
  def from[A](source: IterableOnce[A]): CC[A]
}

The problem is that the Coll type member in IterableFactory is polymorphic, so it can not always be <: C. And anyway, Coll is really just CC, so maybe we want to add something like the following?

trait IterableOps[+A, +CC[_], +C] {
  implicit def ev: CC[A] <:< C
  def iterableFactory: IterableFactory[CC]
  def fromSpecific(source: IterableOnce[A]): C = ev(iterableFactory.from(source))
}

lrytz · 2019-03-27T10:53:55Z

  implicit def ev: CC[A] <:< C

I tried to get this working this morning, but failed

trait DefaultFromSpecific[+A, +CC[_], +C] {
  protected def ev: CC[A] @uncheckedVariance <:< C
  protected def fromSpecific(coll: It[A @uncheckedVariance]): C = ev(iterableFactory.from(coll))
  protected def newSpecificBuilder: Bldr[A @uncheckedVariance, C] = iterableFactory.newBuilder[A].mapResult(ev)
  def iterableFactory: ItFact[CC]
}

trait ItOps[+A, +CC[_], +C] {
  protected def newSpecificBuilder: Bldr[A @uncheckedVariance, C]
  protected def fromSpecific(coll: It[A @uncheckedVariance]): C
  def iterableFactory: ItFact[CC]
}
trait It[+A] extends ItOps[A, It, It[A]] with DefaultFromSpecific[A, It, It[A]] {
  protected def ev: It[A] @uncheckedVariance <:< It[A] = implicitly
  def iterableFactory: ItFact[It] = It
}
object It extends ItFact[It] {
  def from[A](source: It[A]): It[A] = new It[A]{}
  def newBuilder[A]: Bldr[A,It[A]] = new Bldr[A, It[A]] { def result(): It[A] = new It[A]{} }
}

So far so good, but it breaks down in subclasses

trait SqOps[A, +CC[_], +C] extends ItOps[A, CC, C]

trait Sq[A] extends It[A] with SqOps[A, Sq, Sq[A]] with DefaultFromSpecific[A, Sq, Sq[A]] {
  override protected def ev: Sq[A] @uncheckedVariance <:< Sq[A] = implicitly
  override def iterableFactory: ItFact[Sq] = Sq
}

object Sq extends ItFact[Sq] {
  def from[A](source: It[A]): Sq[A] = new Sq[A]{}
  def newBuilder[A]: Bldr[A, Sq[A]] = new Bldr[A, Sq[A]] { def result(): Sq[A] = new Sq[A]{} }
}

gives

Error:(129, 26) incompatible type in overriding
protected def ev: It[A] <:< It[A] (defined in trait It);
 found   : => Sq[A] <:< Sq[A]
 required: => It[A] <:< It[A]
  override protected def ev: Sq[A] @uncheckedVariance <:< Sq[A] = implicitly

Who can find a way to make this (or something similar) work?

lrytz · 2019-03-27T10:59:37Z

Here's a pragmatic version that would work, using a cast. Full example:

https://gist.github.com/lrytz/539040e992a09fcddab6e43138a00569

/** CAUTION: only use this mixin when CC[A] =:= C */
trait DefaultFromSpecific[+A, +CC[_], +C] {
  protected def fromSpecific(coll: It[A @uncheckedVariance]): C = iterableFactory.from(coll).asInstanceOf[C]
  protected def newSpecificBuilder: Bldr[A @uncheckedVariance, C] = iterableFactory.newBuilder[A].mapResult(_.asInstanceOf[C])
  def iterableFactory: ItFact[CC]
}

trait ItOps[+A, +CC[_], +C] {
  protected def newSpecificBuilder: Bldr[A @uncheckedVariance, C]
  protected def fromSpecific(coll: It[A @uncheckedVariance]): C
  def iterableFactory: ItFact[CC]

  def filter: C = fromSpecific(it)
  def strictFilter: C = newSpecificBuilder.result()
  def map[B](f: A => B): CC[B] = iterableFactory.newBuilder.result()
}


trait It[+A] extends ItOps[A, It, It[A]] with DefaultFromSpecific[A, It, It[A]] {
  def it: It[A] = this
  def iterableFactory: ItFact[It] = It
}

adriaanm · 2019-03-27T14:02:54Z

trait DefaultFromSpecific[A, +CC[_]] { self: ItOps[A, CC, CC[A]] =>
  protected def fromSpecific(coll: It[A]): CC[A] = iterableFactory.from(coll)
  protected def newSpecificBuilder: Bldr[A, CC[A]] = iterableFactory.newBuilder[A]
}

look ma, no casts!

one more diff to your gist:

trait It[+A] extends ItOps[A, It, It[A]] with DefaultFromSpecific[A @uncheckedVariance, It] {
// ...
trait Sq[A] extends It[A] with SqOps[A, Sq, Sq[A]] with DefaultFromSpecific[A, Sq] {

lrytz · 2019-03-27T14:12:28Z

Ah nice, I didn't see that :-) It might be slightly nicer to make +A covariant in DefaultFromSpecific, so all the @uncheckedVariance are pushed down into DefaultFromSpecific.

adriaanm · 2019-03-27T14:17:17Z

True, but it's a good reminder your'e doing something dicey. Plus, you don't always need the "variance cast" either (Sq)

adriaanm · 2019-03-27T14:18:36Z

I'll refactor the PR using DefaultFromSpecific -- the self type wouldn't have occurred to me without the nice example.

adriaanm · 2019-03-28T10:16:53Z

empty sig before this PR:

Details

| Class | empty's signature | | ------------- | ------------- | | scala.collection.MapView | scala.collection.MapView[K,V] | | scala.collection.SortedMap | scala.collection.SortedMap[K,V] | | **scala.collection.AbstractSet** | **scala.collection.Set[A]** | | **scala.collection.DefaultMap** | **scala.collection.Map[K,V]** | | **scala.collection.AbstractMapView** | **scala.collection.MapView[K,V]** | | scala.collection.Set | scala.collection.Set[A] | | scala.collection.SortedSet | scala.collection.SortedSet[A] | | scala.collection.BitSet | scala.collection.BitSet | | **scala.collection.AbstractMap** | **scala.collection.Map[K,V]** | | scala.collection.Map | scala.collection.Map[K,V] | | scala.collection.immutable.ListSet | scala.collection.immutable.ListSet[A] | | scala.collection.immutable.Set | scala.collection.immutable.Set[A] | | scala.collection.immutable.SortedMap | scala.collection.immutable.SortedMap[K,V] | | scala.collection.immutable.SortedSet | scala.collection.immutable.SortedSet[A] | | scala.collection.immutable.TreeSet | scala.collection.immutable.TreeSet[A] | | scala.collection.immutable.BitSet | scala.collection.immutable.BitSet | | **scala.collection.immutable.AbstractSet** | **scala.collection.immutable.Set[A]** | | scala.collection.immutable.VectorMap | scala.collection.immutable.VectorMap[K,V] | | scala.collection.immutable.HashMap | scala.collection.immutable.HashMap[K,V] | | scala.collection.immutable.TreeMap | scala.collection.immutable.TreeMap[K,V] | | scala.collection.immutable.HashSet | scala.collection.immutable.HashSet[A] | | **scala.collection.immutable.AbstractMap** | **scala.collection.immutable.Map[K,V]** | | scala.collection.immutable.TreeSeqMap | scala.collection.immutable.TreeSeqMap[K,V] | | scala.collection.immutable.Map | scala.collection.immutable.Map[K,V] | | scala.collection.immutable.LongMap | scala.collection.immutable.LongMap[T] | | scala.collection.immutable.IntMap | scala.collection.immutable.IntMap[T] | | scala.collection.immutable.ListMap | scala.collection.immutable.ListMap[K,V] | | scala.collection.immutable.SeqMap | scala.collection.immutable.SeqMap[K,V] | | scala.collection.mutable.SortedSet | scala.collection.mutable.SortedSet[A] | | scala.collection.mutable.TreeSet | scala.collection.mutable.TreeSet[A] | | scala.collection.mutable.LinkedHashSet | scala.collection.mutable.LinkedHashSet[A] | | scala.collection.mutable.BitSet | scala.collection.mutable.BitSet | | scala.collection.mutable.LinkedHashMap | scala.collection.mutable.LinkedHashMap[K,V] | | **scala.collection.mutable.AbstractSet** | **scala.collection.mutable.Set[A]** | | scala.collection.mutable.OpenHashMap | scala.collection.mutable.OpenHashMap[Key,Value] | | **scala.collection.mutable.MultiMap** | **scala.collection.mutable.Map[K,scala.collection.mutable.Set[V]]** | | scala.collection.mutable.CollisionProofHashMap | scala.collection.mutable.CollisionProofHashMap[K,V] | | scala.collection.mutable.HashMap | scala.collection.mutable.HashMap[K,V] | | scala.collection.mutable.TreeMap | scala.collection.mutable.TreeMap[K,V] | | scala.collection.mutable.HashSet | scala.collection.mutable.HashSet[A] | | **scala.collection.mutable.AbstractMap** | **scala.collection.mutable.Map[K,V]** | | scala.collection.mutable.Map | scala.collection.mutable.Map[K,V] | | scala.collection.mutable.LongMap | scala.collection.mutable.LongMap[V] | | scala.collection.mutable.Set | scala.collection.mutable.Set[A] | | scala.collection.mutable.ListMap | scala.collection.mutable.ListMap[K,V] | | scala.collection.mutable.SortedMap | scala.collection.mutable.SortedMap[K,V] | | scala.collection.mutable.WeakHashMap | scala.collection.mutable.WeakHashMap[K,V] | | scala.collection.mutable.AnyRefMap | scala.collection.mutable.AnyRefMap[K,V] | | scala.collection.mutable.SeqMap | scala.collection.mutable.SeqMap[K,V] |

adriaanm · 2019-03-28T10:17:18Z

Generated in the repl with:

:power

val Iter = typeOf[scala.collection.Iterable[_]]
val ImmutIter = typeOf[scala.collection.immutable.Iterable[_]]
val MutIter = typeOf[scala.collection.mutable.Iterable[_]]
val IterSym = Iter.typeSymbol
val ImmutIterSym = ImmutIter.typeSymbol
val MutIterSym = MutIter.typeSymbol

def isIterSubclass(sym: Symbol) = sym.isClass && !sym.isSpecialized && sym.thisType.baseClasses.contains(IterSym)

val iterSubs = (IterSym.owner.info.decls.toList ++ ImmutIterSym.owner.info.decls.toList ++ MutIterSym.owner.info.decls.toList).filter(isIterSubclass)

val sigs = iterSubs.map(cls => (cls,cls.thisType.memberType(cls.thisType.member(newTermName("empty"))).resultType.dealias))

println("| Class  | empty's signature |\n| ------------- | ------------- |") ; sigs foreach {
  case (cls, tp) if (tp ne NoType) =>
    val uhoh = if (tp.typeSymbol != cls) "**" else ""
    println(s"| ${uhoh}${cls.fullName}${uhoh}  |  ${uhoh}$tp${uhoh} |")
  case _ =>
}

adriaanm · 2019-03-28T10:41:29Z

It's kind of strange that Iterable itself does not define def empty whereas the other immediate subclasses do.

julienrf · 2019-03-28T10:51:38Z

@adriaanm There is a plan to pull it to Iterable as well: scala/scala3#2573

adriaanm · 2019-03-28T11:14:09Z

Ah cool, then I think we may as well add it now. I already have it locally

src/library/scala/collection/convert/Accumulator.scala

lrytz · 2019-04-02T05:34:59Z

pull up IterableFactoryDefaults to the traits, away from the Abstract* classes

yay! 🎉

lrytz

I looked through the diff again, this LGTM now.

adriaanm · 2019-04-02T12:35:59Z

Ok, I think it's time for some squashing then.

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 scala#7458, scala#7929, scala#7800 (better refchecks and compiling with dotc revealed part of the problem) 🤯 Co-authored-by: Lukas Rytz <[email protected]>

So far I have not been able to come up with a correct optimization for this check. Since it doesn't seem to be performance critical after all, I'm disabling the optimization. I'd be glad to bring a sound version back, but it will have to come with a pretty compelling formal explanation of how to reason about overriding pairs. On the reporting side, we could try to be a bit less redundant in the presence of errors, by only reporting on similar pairs of overriding errors once (e.g., track pairs of symbol + info as seen from the current base, kind of like we already do for mixin errors.) (Note that for bridges we still need to exclude certain combos for correctness.)

szeiger · 2019-04-02T13:32:59Z

src/library/scala/collection/Map.scala

+    *       method needs to be overridden to return a factory for the new type (the compiler will
+    *       issue an error otherwise).
+    */
+  def mapFactory: MapFactory[CC]


Iterable.iterableFactory has a default implementation so you can just extends Iterable in simple cases. It should probably be the same for mapFactory.

This abstract method is in MapOps, the default implementation is in Map (https://github.com/scala/scala/pull/7929/files#diff-7e4a5aff40ea5ded3e138d24f2e3cacaR29). Or did I misunderstand?

Oh, right. I blame it on the low contrast of the screen in the sun when working outdoors :-)

szeiger · 2019-04-02T13:34:31Z

src/library/scala/collection/Iterable.scala

+  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] =


Having withFilter in these traits seems odd, but then again, withFilter was always the ugliest and most problematic part of the new collections design.

Otherwise things like the following wouldn't compile ``` class Top; class Sub extends Top class Ok { (??? : Seq[Sub]) match { case _: List[Top] => case _ => } } ``` as soon as there's an invariant superclass in an otherwise covariant class, the isPopulated check will bail unless type arguments are equal, whereas for variant positions it ignores the type arguments. TODO: ignore `@uncheckedVariance` type args in isPopulated? Give `VectorPointer` the same treatment since it's mixed into the covariant Vector. This leaves us with one unexplained test update in BuildFromTest. I cannot figure out why this type ascription to a super type is needed.

adriaanm · 2019-04-02T19:21:35Z

The test failures in previous commits were intentional to motivate the final commit.

scala/scala#7929

See scala/scala#7929.

adriaanm requested review from julienrf, lrytz and szeiger March 26, 2019 19:57

scala-jenkins added this to the 2.13.1 milestone Mar 26, 2019

adriaanm modified the milestones: 2.13.1, 2.13.0-RC1 Mar 26, 2019

adriaanm force-pushed the de-un-checked branch from d0d81c6 to 3a7137b Compare March 26, 2019 19:59

This comment has been minimized.

Sign in to view

julienrf reviewed Mar 26, 2019

View reviewed changes

adriaanm force-pushed the de-un-checked branch from 3a7137b to 278e4e2 Compare March 26, 2019 21:16

This comment has been minimized.

Sign in to view

diesalbla added library:base Changes to the base library, i.e. Function Tuples Try library:collections PRs involving changes to the standard collection library labels Mar 26, 2019

adriaanm changed the title ~~wip: remove some uncheckedVariances~~ wip: remove some uncheckedVariances [ci: last-only] Mar 27, 2019

adriaanm force-pushed the de-un-checked branch 2 times, most recently from af9d20c to 73e8f43 Compare March 27, 2019 22:22

This comment has been minimized.

Sign in to view

adriaanm force-pushed the de-un-checked branch from 96b193b to cad60e8 Compare April 1, 2019 20:45

lrytz reviewed Apr 2, 2019

View reviewed changes

src/library/scala/collection/convert/Accumulator.scala Outdated Show resolved Hide resolved

lrytz force-pushed the de-un-checked branch from 4df818e to b1e2e7c Compare April 2, 2019 07:55

julienrf mentioned this pull request Apr 2, 2019

Update to Scala 2.13.0-RC1 scala/scala-collection-contrib#15

Merged

lrytz force-pushed the de-un-checked branch from 455d44e to 81e4e4b Compare April 2, 2019 10:04

lrytz approved these changes Apr 2, 2019

View reviewed changes

adriaanm and others added 2 commits April 2, 2019 15:21

szeiger reviewed Apr 2, 2019

View reviewed changes

adriaanm changed the title ~~wip: remove some uncheckedVariances [ci: last-only]~~ Remove some @uncheckedVariances, introduce empty in Iterable. Apr 2, 2019

adriaanm force-pushed the de-un-checked branch from 824661f to 915e844 Compare April 2, 2019 14:44

This was referenced Apr 2, 2019

isPopulated's isConsistent should ignore type args annotated as @uncheckedVariance scala/bug#11464

Open

DO NOT MERGE Fix the overriding-pairs Cursor used by PrepJSInterop for 2.13. scala-js/scala-js#3600

Closed

adriaanm force-pushed the de-un-checked branch from 915e844 to 878e2f3 Compare April 2, 2019 17:48

adriaanm merged commit 041fc23 into scala:2.13.x Apr 2, 2019

sjrd added a commit to sjrd/scala-js that referenced this pull request Apr 2, 2019

WiP Deal with scala/scala#7929

d407dd2

scala/scala#7929

adriaanm added a commit to scalacommunitybuild/scala-xml that referenced this pull request Apr 3, 2019

Add empty method to NodeSeq for scala/scala#7929

1983436

adriaanm added a commit to scalacommunitybuild/scala-xml that referenced this pull request Apr 3, 2019

Add empty method to NodeSeq for scala/scala#7929

830864a

sjrd added a commit to sjrd/scala-js that referenced this pull request Apr 3, 2019

Update new collection impls to the upstream IterableCC refactoring.

165622d

See scala/scala#7929.

adriaanm added a commit to scala/scala-parallel-collections that referenced this pull request Apr 3, 2019

adapt to scala/scala#7929

3647df7

This was referenced Apr 25, 2019

Upgrade to Scala 2.13.0-RC1 akka/akka-core#26691

Closed

Drop uncheckedVariance type alias from BitSet #8002

Merged

hrhino mentioned this pull request Apr 30, 2019

Java interop: no more static 'empty' for collections scala/bug#11509

Open

SethTisue mentioned this pull request Jun 17, 2019

[java-interop] Compilation error "incompatible type in overriding" when inheriting from a Java subclass with different field type to parent class (regression in 2.13) scala/bug#11575

Closed

eed3si9n mentioned this pull request Jul 26, 2019

Backport Scaladoc jQuery update to 2.12.9? scala/bug#11651

Closed

lrytz mentioned this pull request Sep 27, 2019

VerifyError on unclear overrides scala/bug#11749

Closed

Remove some @uncheckedVariances, introduce empty in Iterable. #7929

Remove some @uncheckedVariances, introduce empty in Iterable. #7929

Uh oh!

Conversation

adriaanm commented Mar 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

This comment has been minimized.

adriaanm commented Mar 26, 2019

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

julienrf commented Mar 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

This comment has been minimized.

lrytz commented Mar 27, 2019

Uh oh!

lrytz commented Mar 27, 2019

Uh oh!

adriaanm commented Mar 27, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

lrytz commented Mar 27, 2019

Uh oh!

adriaanm commented Mar 27, 2019

Uh oh!

adriaanm commented Mar 27, 2019

Uh oh!

This comment has been minimized.

adriaanm commented Mar 28, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

adriaanm commented Mar 28, 2019

Uh oh!

adriaanm commented Mar 28, 2019

Uh oh!

julienrf commented Mar 28, 2019

Uh oh!

adriaanm commented Mar 28, 2019

Uh oh!

Uh oh!

lrytz commented Apr 2, 2019

Uh oh!

lrytz left a comment

Choose a reason for hiding this comment

Uh oh!

adriaanm commented Apr 2, 2019

Uh oh!

szeiger Apr 2, 2019

Choose a reason for hiding this comment

Uh oh!

lrytz Apr 2, 2019

Choose a reason for hiding this comment

Uh oh!

szeiger Apr 2, 2019

Choose a reason for hiding this comment

Uh oh!

szeiger Apr 2, 2019

Choose a reason for hiding this comment

Uh oh!

adriaanm commented Apr 2, 2019

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

8 participants

Remove some `@uncheckedVariance`s, introduce `empty` in `Iterable`. #7929

Remove some `@uncheckedVariance`s, introduce `empty` in `Iterable`. #7929

adriaanm commented Mar 26, 2019 •

edited

Loading

julienrf commented Mar 26, 2019 •

edited

Loading

adriaanm commented Mar 27, 2019 •

edited

Loading

adriaanm commented Mar 28, 2019 •

edited

Loading