Big realizability refactoring

Move logic from TypeOps to new file CheckRealizable.scala.
Also check realizable fields under strict mode.
Check at phase PostTyper rather than Typer to avoid cycles.
New tests for imports and deep paths.

6 files changed, 164 insertions, 124 deletions

diff --git a/src/dotty/tools/dotc/core/CheckRealizable.scala b/src/dotty/tools/dotc/core/CheckRealizable.scala
new file mode 100644
index 000000000..ce922635b
--- /dev/null
+++ b/src/dotty/tools/dotc/core/CheckRealizable.scala
@@ -0,0 +1,140 @@
+package dotty.tools
+package dotc
+package core
+
+import Contexts._, Types._, Symbols._, Names._, Flags._, Scopes._
+import SymDenotations._, Denotations.SingleDenotation
+import config.Printers._
+import util.Positions._
+import Decorators._
+import StdNames._
+import Annotations._
+import collection.mutable
+import ast.tpd._
+
+/** Realizability status */
+object CheckRealizable {
+
+  abstract class Realizability(val msg: String) {
+    def andAlso(other: => Realizability) =
+      if (this == Realizable) other else this
+    def mapError(f: Realizability => Realizability) =
+      if (this == Realizable) this else f(this)
+  }
+
+  object Realizable extends Realizability("")
+
+  object NotConcrete extends Realizability(" is not a concrete type")
+
+  object NotStable extends Realizability(" is not a stable reference")
+
+  class NotFinal(sym: Symbol)(implicit ctx: Context)
+  extends Realizability(i" refers to nonfinal $sym")
+
+  class HasProblemBounds(typ: SingleDenotation)(implicit ctx: Context)
+  extends Realizability(i" has a member $typ with possibly conflicting bounds ${typ.info.bounds.lo} <: ... <: ${typ.info.bounds.hi}")
+
+  class HasProblemField(fld: SingleDenotation, problem: Realizability)(implicit ctx: Context)
+  extends Realizability(i" has a member $fld which is not a legal path\n since ${fld.symbol.name}: ${fld.info}${problem.msg}")
+
+  class ProblemInUnderlying(tp: Type, problem: Realizability)(implicit ctx: Context)
+  extends Realizability(i"s underlying type ${tp}${problem.msg}") {
+    assert(problem != Realizable)
+  }
+
+  def realizability(tp: Type)(implicit ctx: Context) =
+    new CheckRealizable().realizability(tp)
+
+  def boundsRealizability(tp: Type)(implicit ctx: Context) =
+    new CheckRealizable().boundsRealizability(tp)
+}
+
+/** Compute realizability status */
+class CheckRealizable(implicit ctx: Context) {
+  import CheckRealizable._
+
+  /** A set of all fields that have already been checked. Used
+   *  to avoid infinite recursions when analyzing recursive types.
+   */
+  private val checkedFields: mutable.Set[Symbol] = mutable.LinkedHashSet[Symbol]()
+
+  /** Is this type a path with some part that is initialized on use? */
+  private def isLateInitialized(tp: Type): Boolean = tp.dealias match {
+    case tp: TermRef =>
+      tp.symbol.isLateInitialized || isLateInitialized(tp.prefix)
+    case _: SingletonType | NoPrefix =>
+      false
+    case tp: TypeRef =>
+      true
+    case tp: TypeProxy =>
+      isLateInitialized(tp.underlying)
+    case tp: AndOrType =>
+      isLateInitialized(tp.tp1) || isLateInitialized(tp.tp2)
+    case _ =>
+      true
+  }
+
+  /** The realizability status of given type `tp`*/
+  def realizability(tp: Type): Realizability = tp.dealias match {
+    case tp: TermRef =>
+      val sym = tp.symbol
+      if (sym.is(Stable)) realizability(tp.prefix)
+      else {
+        val r =
+          if (!sym.isStable) NotStable
+          else if (!sym.isLateInitialized) realizability(tp.prefix)
+          else if (!sym.isEffectivelyFinal) new NotFinal(sym)
+          else realizability(tp.info).mapError(r => new ProblemInUnderlying(tp.info, r))
+        if (r == Realizable) sym.setFlag(Stable)
+        r
+      }
+    case _: SingletonType | NoPrefix =>
+      Realizable
+    case tp =>
+      def isConcrete(tp: Type): Boolean = tp.dealias match {
+        case tp: TypeRef => tp.symbol.isClass
+        case tp: TypeProxy => isConcrete(tp.underlying)
+        case tp: AndOrType => isConcrete(tp.tp1) && isConcrete(tp.tp2)
+        case _ => false
+      }
+      if (!isConcrete(tp)) NotConcrete
+      else boundsRealizability(tp).andAlso(memberRealizability(tp))
+  }
+
+  /** `Realizable` if `tp` has good bounds, a `HasProblemBounds` instance
+   *  pointing to a bad bounds member otherwise.
+   */
+  private def boundsRealizability(tp: Type) = {
+    def hasBadBounds(mbr: SingleDenotation) = {
+      val bounds = mbr.info.bounds
+      !(bounds.lo <:< bounds.hi)
+    }
+    tp.nonClassTypeMembers.find(hasBadBounds) match {
+      case Some(mbr) => new HasProblemBounds(mbr)
+      case _ => Realizable
+    }
+  }
+
+  /** `Realizable` if `tp` all of `tp`'s non-struct fields have realizable types,
+   *  a `HasProblemField` instance pointing to a bad field otherwise.
+   */
+  private def memberRealizability(tp: Type) = {
+    def checkField(sofar: Realizability, fld: SingleDenotation): Realizability =
+      sofar andAlso {
+        if (checkedFields.contains(fld.symbol) || fld.symbol.is(Private | Mutable | Lazy))
+          Realizable
+        else {
+          checkedFields += fld.symbol
+          realizability(fld.info).mapError(r => new HasProblemField(fld, r))
+        }
+      }
+    if (ctx.settings.strict.value)
+      // check fields only under strict mode for now.
+      // Reason: We do track nulls, so an embedded field could well be nullable
+      // which means it is not a path and need not be checked; but we cannot recognize
+      // this situation until we have a typesystem that tracks nullability.
+      ((Realizable: Realizability) /: tp.fields)(checkField)
+    else
+      Realizable
+  }
+}
diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala
index fb59cae59..a4082607c 100644
--- a/src/dotty/tools/dotc/core/SymDenotations.scala
+++ b/src/dotty/tools/dotc/core/SymDenotations.scala
@@ -12,6 +12,7 @@ import scala.reflect.io.AbstractFile
 import Decorators.SymbolIteratorDecorator
 import ast._
 import annotation.tailrec
+import CheckRealizable._
 import typer.Mode
 import util.SimpleMap
 import util.Stats
@@ -522,15 +523,6 @@ object SymDenotations {
     final def isStable(implicit ctx: Context) =
       isType || !is(UnstableValue, butNot = Stable)
 
-    /** Is this a denotation of a realizable term (or an arbitrary type)? */
-    final def isRealizable(implicit ctx: Context) =
-      is(Stable) || isType || {
-        val isRealizable =
-          !isLateInitialized ||
-          isEffectivelyFinal && ctx.realizability(info) == TypeOps.Realizable
-        isRealizable && { setFlag(Stable); true }
-      }
-
     /** Field is initialized on use, not on definition;
      *  we do not count modules as fields here.
      */
diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala
index 925ebcbcd..4251648a3 100644
--- a/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/src/dotty/tools/dotc/core/TypeOps.scala
@@ -14,7 +14,6 @@ import collection.mutable
 import ast.tpd._
 
 trait TypeOps { this: Context => // TODO: Make standalone object.
-  import TypeOps._
 
   /** The type `tp` as seen from prefix `pre` and owner `cls`. See the spec
    *  for what this means. Called very often, so the code is optimized heavily.
@@ -342,73 +341,6 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
     }
   }
 
-  /** Is this type a path with some part that is initialized on use? */
-  def isLateInitialized(tp: Type): Boolean = tp.dealias match {
-    case tp: TermRef =>
-      tp.symbol.isLateInitialized || isLateInitialized(tp.prefix)
-    case _: SingletonType | NoPrefix =>
-      false
-    case tp: TypeRef =>
-      true
-    case tp: TypeProxy =>
-      isLateInitialized(tp.underlying)
-    case tp: AndOrType =>
-      isLateInitialized(tp.tp1) || isLateInitialized(tp.tp2)
-    case _ =>
-      true
-  }
-
-  /** The realizability status of given type `tp`*/
-  def realizability(tp: Type): Realizability = tp.dealias match {
-    case tp: TermRef =>
-      if (tp.symbol.isRealizable)
-        if (tp.symbol.isLateInitialized || // we already checked realizability of info in that case
-            !isLateInitialized(tp.prefix)) // symbol was definitely constructed in that case
-          Realizable
-        else
-          realizability(tp.info)
-      else if (!tp.symbol.isStable) NotStable
-      else if (!tp.symbol.isEffectivelyFinal) new NotFinal(tp.symbol)
-      else new ProblemInUnderlying(tp.info, realizability(tp.info))
-    case _: SingletonType | NoPrefix =>
-      Realizable
-    case tp =>
-      def isConcrete(tp: Type): Boolean = tp.dealias match {
-        case tp: TypeRef => tp.symbol.isClass
-        case tp: TypeProxy => isConcrete(tp.underlying)
-        case tp: AndOrType => isConcrete(tp.tp1) && isConcrete(tp.tp2)
-        case _ => false
-      }
-      if (!isConcrete(tp)) NotConcrete
-      else boundsRealizability(tp)
-  }
-
-  /** `Realizable` if `tp` has good bounds, a `HasProblemBounds` instance
-   *  pointing to a bad bounds member otherwise.
-   */
-  def boundsRealizability(tp: Type)(implicit ctx: Context) = {
-    def hasBadBounds(mbr: SingleDenotation) = {
-      val bounds = mbr.info.bounds
-      !(bounds.lo <:< bounds.hi)
-    }
-    tp.nonClassTypeMembers.find(hasBadBounds) match {
-      case Some(mbr) => new HasProblemBounds(mbr)
-      case _ => Realizable
-    }
-  }
-
-  /* Might need at some point in the future
-  def memberRealizability(tp: Type)(implicit ctx: Context) = {
-    println(i"check member rel of $tp")
-    def isUnrealizable(fld: SingleDenotation) =
-      !fld.symbol.is(Lazy) && realizability(fld.info) != Realizable
-    tp.fields.find(isUnrealizable) match {
-      case Some(fld) => new HasProblemField(fld)
-      case _ => Realizable
-    }
-  }
-  */
-
   private def enterArgBinding(formal: Symbol, info: Type, cls: ClassSymbol, decls: Scope) = {
     val lazyInfo = new LazyType { // needed so we do not force `formal`.
       def complete(denot: SymDenotation)(implicit ctx: Context): Unit = {
@@ -625,30 +557,5 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
 }
 
 object TypeOps {
-  val emptyDNF = (Nil, Set[Name]()) :: Nil
   @sharable var track = false // !!!DEBUG
-
-  // ----- Realizibility Status -----------------------------------------------------
-
-  abstract class Realizability(val msg: String)
-
-  object Realizable extends Realizability("")
-
-  object NotConcrete extends Realizability(" is not a concrete type")
-
-  object NotStable extends Realizability(" is not a stable reference")
-
-  class NotFinal(sym: Symbol)(implicit ctx: Context)
-  extends Realizability(i" refers to nonfinal $sym")
-
-  class HasProblemBounds(typ: SingleDenotation)(implicit ctx: Context)
-  extends Realizability(i" has a member $typ with possibly conflicting bounds ${typ.info.bounds.lo} <: ... <: ${typ.info.bounds.hi}")
-
-  /* Might need at some point in the future
-  class HasProblemField(fld: SingleDenotation)(implicit ctx: Context)
-  extends Realizability(i" has a member $fld which is uneligible as a path since ${fld.symbol.name}${ctx.realizability(fld.info)}")
-  */
-  
-  class ProblemInUnderlying(tp: Type, problem: Realizability)(implicit ctx: Context)
-  extends Realizability(i"s underlying type ${tp}${problem.msg}")
 }
diff --git a/src/dotty/tools/dotc/transform/PostTyper.scala b/src/dotty/tools/dotc/transform/PostTyper.scala
index f9862bb95..14edaa7b5 100644
--- a/src/dotty/tools/dotc/transform/PostTyper.scala
+++ b/src/dotty/tools/dotc/transform/PostTyper.scala
@@ -101,7 +101,7 @@ class PostTyper extends MacroTransform with IdentityDenotTransformer  { thisTran
     case tree: TypeTree => tree
     case _ =>
       if (tree.isType) {
-        Checking.boundsChecker.traverse(tree)
+        Checking.typeChecker.traverse(tree)
         TypeTree(tree.tpe).withPos(tree.pos)
       }
       else tree.tpe.widenTermRefExpr match {
@@ -180,7 +180,7 @@ class PostTyper extends MacroTransform with IdentityDenotTransformer  { thisTran
           val tree1 =
             if (sym.isClass) tree
             else {
-              Checking.boundsChecker.traverse(tree.rhs)
+              Checking.typeChecker.traverse(tree.rhs)
               cpy.TypeDef(tree)(rhs = TypeTree(tree.symbol.info))
             }
           super.transform(tree1)
diff --git a/src/dotty/tools/dotc/typer/Checking.scala b/src/dotty/tools/dotc/typer/Checking.scala
index 7e90d755b..437902d05 100644
--- a/src/dotty/tools/dotc/typer/Checking.scala
+++ b/src/dotty/tools/dotc/typer/Checking.scala
@@ -16,6 +16,7 @@ import Trees._
 import ProtoTypes._
 import Constants._
 import Scopes._
+import CheckRealizable._
 import ErrorReporting.errorTree
 import annotation.unchecked
 import util.Positions._
@@ -49,7 +50,7 @@ object Checking {
     checkBounds(args, poly.paramBounds, _.substParams(poly, _))
 
   /** Check all AppliedTypeTree nodes in this tree for legal bounds */
-  val boundsChecker = new TreeTraverser {
+  val typeChecker = new TreeTraverser {
     def traverse(tree: Tree)(implicit ctx: Context) = {
       tree match {
         case AppliedTypeTree(tycon, args) =>
@@ -57,6 +58,12 @@ object Checking {
           val bounds = tparams.map(tparam =>
             tparam.info.asSeenFrom(tycon.tpe.normalizedPrefix, tparam.owner.owner).bounds)
           checkBounds(args, bounds, _.substDealias(tparams, _))
+        case Select(qual, name) if name.isTypeName =>
+          checkRealizable(qual.tpe, qual.pos)
+        case SelectFromTypeTree(qual, name) if name.isTypeName =>
+          checkRealizable(qual.tpe, qual.pos)
+        case SingletonTypeTree(ref) =>
+          checkRealizable(ref.tpe, ref.pos)
         case _ =>
       }
       traverseChildren(tree)
@@ -83,6 +90,15 @@ object Checking {
       case _ =>
     }
 
+  /** Check that type `tp` is realizable. */
+  def checkRealizable(tp: Type, pos: Position)(implicit ctx: Context): Unit = {
+    val rstatus = realizability(tp)
+    if (rstatus ne Realizable) {
+      def msg = d"$tp is not a legal path\n since it${rstatus.msg}"
+      if (ctx.scala2Mode) ctx.migrationWarning(msg, pos) else ctx.error(msg, pos)
+    }
+  }
+
   /** A type map which checks that the only cycles in a type are F-bounds
    *  and that protects all F-bounded references by LazyRefs.
    */
@@ -321,19 +337,10 @@ trait Checking {
   def checkStable(tp: Type, pos: Position)(implicit ctx: Context): Unit =
     if (!tp.isStable) ctx.error(d"$tp is not stable", pos)
 
-  /** Check that type `tp` is realizable. */
-  def checkRealizable(tp: Type, pos: Position)(implicit ctx: Context): Unit = {
-    val rstatus = ctx.realizability(tp)
-    if (rstatus ne TypeOps.Realizable) {
-      def msg = d"$tp is not a legal path since it${rstatus.msg}"
-      if (ctx.scala2Mode) ctx.migrationWarning(msg, pos) else ctx.error(msg, pos)
-    }
-  }
-
   /** Check that all type members of `tp` have realizable bounds */
   def checkRealizableBounds(tp: Type, pos: Position)(implicit ctx: Context): Unit = {
-    val rstatus = ctx.boundsRealizability(tp)
-    if (rstatus ne TypeOps.Realizable)
+    val rstatus = boundsRealizability(tp)
+    if (rstatus ne Realizable)
       ctx.error(i"$tp cannot be instantiated since it${rstatus.msg}", pos)
   }
 
@@ -449,7 +456,6 @@ trait NoChecking extends Checking {
   override def checkNonCyclic(sym: Symbol, info: TypeBounds, reportErrors: Boolean)(implicit ctx: Context): Type = info
   override def checkValue(tree: Tree, proto: Type)(implicit ctx: Context): tree.type = tree
   override def checkStable(tp: Type, pos: Position)(implicit ctx: Context): Unit = ()
-  override def checkRealizable(tp: Type, pos: Position)(implicit ctx: Context): Unit = ()
   override def checkClassTypeWithStablePrefix(tp: Type, pos: Position, traitReq: Boolean)(implicit ctx: Context): Type = tp
   override def checkImplicitParamsNotSingletons(vparamss: List[List[ValDef]])(implicit ctx: Context): Unit = ()
   override def checkFeasible(tp: Type, pos: Position, where: => String = "")(implicit ctx: Context): Type = tp
diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala
index 7894a5b5f..542f78f94 100644
--- a/src/dotty/tools/dotc/typer/Typer.scala
+++ b/src/dotty/tools/dotc/typer/Typer.scala
@@ -274,7 +274,6 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
 
     val tree1 = ownType match {
       case ownType: NamedType if !prefixIsElidable(ownType) =>
-        checkRealizable(ownType.prefix, tree.pos)
         ref(ownType).withPos(tree.pos)
       case _ =>
         tree.withType(ownType)
@@ -309,10 +308,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
   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)
-        checkRealizable(qual1.tpe, qual1.pos)
-      }
+      if (tree.name.isTypeName) checkStable(qual1.tpe, qual1.pos)
       typedSelect(tree, pt, qual1)
    }
 
@@ -346,7 +342,6 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
 
   def typedSelectFromTypeTree(tree: untpd.SelectFromTypeTree, pt: Type)(implicit ctx: Context): Tree = track("typedSelectFromTypeTree") {
     val qual1 = typedType(tree.qualifier, selectionProto(tree.name, pt, this))
-    checkRealizable(qual1.tpe, qual1.pos)
     assignType(cpy.SelectFromTypeTree(tree)(qual1, tree.name), qual1)
   }
 
@@ -828,7 +823,6 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
   def typedSingletonTypeTree(tree: untpd.SingletonTypeTree)(implicit ctx: Context): SingletonTypeTree = track("typedSingletonTypeTree") {
     val ref1 = typedExpr(tree.ref)
     checkStable(ref1.tpe, tree.pos)
-    checkRealizable(ref1.tpe, tree.pos)
     assignType(cpy.SingletonTypeTree(tree)(ref1), ref1)
   }
 
@@ -1064,6 +1058,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
   def typedImport(imp: untpd.Import, sym: Symbol)(implicit ctx: Context): Import = track("typedImport") {
     val expr1 = typedExpr(imp.expr, AnySelectionProto)
     checkStable(expr1.tpe, imp.expr.pos)
+    checkRealizable(expr1.tpe, imp.expr.pos)
     assignType(cpy.Import(imp)(expr1, imp.selectors), sym)
   }