Make asSeenFrom idempotent

Let asSeenFrom generate a marker annotated type
for any unsafe instantiation. Then cleanup in
typedSelect.

6 files changed, 88 insertions, 35 deletions

diff --git a/src/dotty/annotation/internal/UnsafeNonvariant.scala b/src/dotty/annotation/internal/UnsafeNonvariant.scala
new file mode 100644
index 000000000..43a0a114b
--- /dev/null
+++ b/src/dotty/annotation/internal/UnsafeNonvariant.scala
@@ -0,0 +1,8 @@
+package dotty.annotation.internal
+
+import scala.annotation.Annotation
+
+/** This annotation is used as a marker for unsafe
+ *  instantiations in asSeenFrom. See TypeOps.asSeenfrom for an explanation.
+ */
+class UnsafeNonvariant extends Annotation
diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala
index 1a471537e..ae221cc3e 100644
--- a/src/dotty/tools/dotc/core/Contexts.scala
+++ b/src/dotty/tools/dotc/core/Contexts.scala
@@ -600,10 +600,16 @@ object Contexts {
      *  of underlying during a controlled operation exists. */
     private[core] val pendingUnderlying = new mutable.HashSet[Type]
 
+    /** A flag that some unsafe nonvariant instantiation was encountered
+     *  in this run. Used as a shortcut to a avoid scans of types in
+     *  Typer.typedSelect.
+     */
+    private[dotty] var unsafeNonvariant: RunId = NoRunId
+
+    // Phases state
 
     private[core] var phasesPlan: List[List[Phase]] = _
 
-    // Phases state
     /** Phases by id */
     private[core] var phases: Array[Phase] = _
 
diff --git a/src/dotty/tools/dotc/core/Definitions.scala b/src/dotty/tools/dotc/core/Definitions.scala
index 5f794f2d5..609cce189 100644
--- a/src/dotty/tools/dotc/core/Definitions.scala
+++ b/src/dotty/tools/dotc/core/Definitions.scala
@@ -475,6 +475,8 @@ class Definitions {
   def UncheckedStableAnnot(implicit ctx: Context) = UncheckedStableAnnotType.symbol.asClass
   lazy val UncheckedVarianceAnnotType = ctx.requiredClassRef("scala.annotation.unchecked.uncheckedVariance")
   def UncheckedVarianceAnnot(implicit ctx: Context) = UncheckedVarianceAnnotType.symbol.asClass
+  lazy val UnsafeNonvariantAnnotType = ctx.requiredClassRef("dotty.annotation.internal.UnsafeNonvariant")
+  def UnsafeNonvariantAnnot(implicit ctx: Context) = UnsafeNonvariantAnnotType.symbol.asClass
   lazy val VolatileAnnotType = ctx.requiredClassRef("scala.volatile")
   def VolatileAnnot(implicit ctx: Context) = VolatileAnnotType.symbol.asClass
   lazy val FieldMetaAnnotType = ctx.requiredClassRef("scala.annotation.meta.field")
diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala
index 3dfe698f0..9232bd185 100644
--- a/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/src/dotty/tools/dotc/core/TypeOps.scala
@@ -8,6 +8,7 @@ import config.Printers._
 import util.Positions._
 import Decorators._
 import StdNames._
+import Annotations._
 import util.SimpleMap
 import collection.mutable
 import ast.tpd._
@@ -23,31 +24,29 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
    *
    *  and an expression `e` of type `C`. Then computing the type of `e.f` leads
    *  to the query asSeenFrom(`C`, `(x: T)T`). What should its result be? The
-   *  naive answer `(x: C.T)C.T` is incorrect given that we treat `C.T` as the existential
+   *  naive answer `(x: C#T)C#T` is incorrect given that we treat `C#T` as the existential
    *  `exists(c: C)c.T`. What we need to do instead is to skolemize the existential. So
    *  the answer would be `(x: c.T)c.T` for some (unknown) value `c` of type `C`.
    *  `c.T` is expressed in the compiler as a skolem type `Skolem(C)`.
    *
    *  Now, skolemization is messy and expensive, so we want to do it only if we absolutely
-   *  must. We must skolemize if an unstable prefix is used in nonvariant or
-   *  contravariant position of the return type of asSeenFrom.
+   *  must. Also, skolemizing immediately would mean that asSeenFrom was no longer
+   *  idempotent - each call would return a type with a different skolem.
+   *  Instead we produce an annotated type that marks the prefix as unsafe:
    *
-   *  In the implementation of asSeenFrom, we first try to run asSeenFrom without
-   *  skolemizing. If that would be incorrect we will be told by the fact that
-   *  `unstable` is set in the passed AsSeenFromMap. In that case we run asSeenFrom
-   *  again with a skolemized prefix.
+   *     (x: (C @ UnsafeNonvariant)#T)C#T
+   
+   *  We also set a global state flag `unsafeNonvariant` to the current run.
+   *  When typing a Select node, typer will check that flag, and if it
+   *  points to the current run will scan the result type of the select for
+   *  @UnsafeNonvariant annotations. If it finds any, it will introduce a skolem
+   *  constant for the prefix and try again.
    *
-   *  In the interest of speed we want to avoid creating an AsSeenFromMap every time
-   *  asSeenFrom is called. So we do this here only if the prefix is unstable
-   *  (because then we need the map as a container for the unstable field). For
-   *  stable prefixes the map is `null`; it might however be instantiated later
-   *  for more complicated types.
+   *  The scheme is efficient in particular because we expect that unsafe situations are rare;
+   *  most compiles would contain none, so no scanning would be necessary.
    */
-  final def asSeenFrom(tp: Type, pre: Type, cls: Symbol): Type = {
-    val m = if (isLegalPrefix(pre)) null else new AsSeenFromMap(pre, cls)
-    var res = asSeenFrom(tp, pre, cls, m)
-    if (m != null && m.unstable) asSeenFrom(tp, SkolemType(pre), cls) else res
-  }
+  final def asSeenFrom(tp: Type, pre: Type, cls: Symbol): Type =
+    asSeenFrom(tp, pre, cls, null)
 
   /** Helper method, taking a map argument which is instantiated only for more
    *  complicated cases of asSeenFrom.
@@ -65,9 +64,11 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
         case pre: SuperType => toPrefix(pre.thistpe, cls, thiscls)
         case _ =>
           if (thiscls.derivesFrom(cls) && pre.baseTypeRef(thiscls).exists) {
-            if (theMap != null && theMap.currentVariance <= 0 && !isLegalPrefix(pre))
-              theMap.unstable = true
-            pre
+            if (theMap != null && theMap.currentVariance <= 0 && !isLegalPrefix(pre)) {
+              ctx.base.unsafeNonvariant = ctx.runId
+              AnnotatedType(pre, Annotation(defn.UnsafeNonvariantAnnot, Nil))
+            }
+            else pre
           }
           else if ((pre.termSymbol is Package) && !(thiscls is Package))
             toPrefix(pre.select(nme.PACKAGE), cls, thiscls)
@@ -82,17 +83,14 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
           val sym = tp.symbol
           if (sym.isStatic) tp
           else {
-            val prevStable = theMap == null || !theMap.unstable
             val pre1 = asSeenFrom(tp.prefix, pre, cls, theMap)
-            if (theMap != null && theMap.unstable && prevStable) {
+            if (pre1.isUnsafeNonvariant)
               pre1.member(tp.name).info match {
                 case TypeAlias(alias) =>
                   // try to follow aliases of this will avoid skolemization.
-                  theMap.unstable = false
                   return alias
                 case _ =>
               }
-            }
             tp.derivedSelect(pre1)
           }
         case tp: ThisType =>
@@ -122,11 +120,6 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
 
     /** A method to export the current variance of the map */
     def currentVariance = variance
-
-    /** A field which indicates whether an unstable argument in nonvariant
-     *  or contravariant position was encountered.
-     */
-    var unstable = false
   }
 
   /** Approximate a type `tp` with a type that does not contain skolem types.
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 624549bac..e0e9a535f 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -190,6 +190,16 @@ object Types {
     def isRepeatedParam(implicit ctx: Context): Boolean =
       typeSymbol eq defn.RepeatedParamClass
 
+    /** Does this type carry an UnsafeNonvariant annotation? */
+    final def isUnsafeNonvariant(implicit ctx: Context): Boolean = this match {
+      case AnnotatedType(_, annot) => annot.symbol == defn.UnsafeNonvariantAnnot
+      case _ => false
+    }
+
+    /** Does this type have an UnsafeNonvariant annotation on one of its parts? */
+    final def hasUnsafeNonvariant(implicit ctx: Context): Boolean =
+      new HasUnsafeNonAccumulator().apply(false, this)
+
     /** Is this the type of a method that has a repeated parameter type as
      *  last parameter type?
      */
@@ -755,6 +765,12 @@ object Types {
       case _ => this
     }
 
+    /** If this is a skolem, its underlying type, otherwise the type itself */
+    final def widenSkolem(implicit ctx: Context): Type = this match {
+      case tp: SkolemType => tp.underlying
+      case _ => this
+    }
+
     /** Follow aliases and dereferences LazyRefs and instantiated TypeVars until type
      *  is no longer alias type, LazyRef, or instantiated type variable.
      */
@@ -3239,6 +3255,10 @@ object Types {
     def apply(x: Unit, tp: Type): Unit = foldOver(p(tp), tp)
   }
 
+  class HasUnsafeNonAccumulator(implicit ctx: Context) extends TypeAccumulator[Boolean] {
+    def apply(x: Boolean, tp: Type) = x || tp.isUnsafeNonvariant || foldOver(x, tp)
+  }
+
   class NamedPartsAccumulator(p: NamedType => Boolean)(implicit ctx: Context) extends TypeAccumulator[mutable.Set[NamedType]] {
     override def stopAtStatic = false
     def maybeAdd(x: mutable.Set[NamedType], tp: NamedType) = if (p(tp)) x += tp else x
diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala
index e5509d50f..1747d1442 100644
--- a/src/dotty/tools/dotc/typer/Typer.scala
+++ b/src/dotty/tools/dotc/typer/Typer.scala
@@ -282,12 +282,35 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
     checkValue(tree1, pt)
   }
 
+  private def typedSelect(tree: untpd.Select, pt: Type, qual: Tree)(implicit ctx: Context): Select =
+    healNonvariant(
+      checkValue(assignType(cpy.Select(tree)(qual, tree.name), qual), pt),
+      pt)
+
+  /** Let `tree = p.n` where `p: T`. If tree's type is an unsafe instantiation
+   *  (see TypeOps#asSeenFrom for how this can happen), rewrite the prefix `p`
+   *  to `(p: <unknown skolem of type T>)` and try again with the new (stable)
+   *  prefix. If the result has another unsafe instantiation, raise an error.
+   */
+  private def healNonvariant[T <: Tree](tree: T, pt: Type)(implicit ctx: Context): T  =
+    if (ctx.unsafeNonvariant == ctx.runId && tree.tpe.widen.hasUnsafeNonvariant)
+      tree match {
+        case tree @ Select(qual, _) if !qual.tpe.isStable =>
+          val alt = typedSelect(tree, pt, Typed(qual, TypeTree(SkolemType(qual.tpe.widen))))
+          /*typr.*/println(d"healed type: ${tree.tpe} --> $alt")
+          alt.asInstanceOf[T]
+        case _ =>
+          ctx.error(d"unsafe instantiation of type ${tree.tpe}", tree.pos)
+          tree
+      }
+    else tree
+
   def typedSelect(tree: untpd.Select, pt: Type)(implicit ctx: Context): Tree = track("typedSelect") {
     def asSelect(implicit ctx: Context): Tree = {
       val qual1 = typedExpr(tree.qualifier, selectionProto(tree.name, pt, this))
       if (tree.name.isTypeName) checkStable(qual1.tpe, qual1.pos)
-      checkValue(assignType(cpy.Select(tree)(qual1, tree.name), qual1), pt)
-    }
+      typedSelect(tree, pt, qual1)
+   }
 
     def asJavaSelectFromTypeTree(implicit ctx: Context): Tree = {
       // Translate names in Select/Ident nodes to type names.
@@ -382,7 +405,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
           checkSimpleKinded(typedType(tree.tpt))
       val expr1 =
         if (isWildcard) tree.expr withType tpt1.tpe
-        else typed(tree.expr, tpt1.tpe)
+        else typed(tree.expr, tpt1.tpe.widenSkolem)
       assignType(cpy.Typed(tree)(expr1, tpt1), tpt1)
     }
     tree.expr match {
@@ -438,9 +461,10 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
                 val setter = pre.member(setterName)
                 lhsCore match {
                   case lhsCore: RefTree if setter.exists =>
-                    val setterTypeRaw = pre select (setterName, setter)
+                    val setterTypeRaw = pre.select(setterName, setter)
                     val setterType = ensureAccessible(setterTypeRaw, isSuperSelection(lhsCore), tree.pos)
-                    val lhs2 = untpd.rename(lhsCore, setterName).withType(setterType)
+                    val lhs2 = healNonvariant(
+                      untpd.rename(lhsCore, setterName).withType(setterType), WildcardType)
                     typedUnadapted(cpy.Apply(tree)(untpd.TypedSplice(lhs2), tree.rhs :: Nil))
                   case _ =>
                     reassignmentToVal