Detect cycles and protected legal ones with LazyRefs

Cycles are now detected early, when an info is first completed.
Legal, f-bounded cycles are broken by a LazyRef, which will construct
its type lazily. This makes checkBounds validation of AppliedTypeTrees work
(in FirstTransform). Formerly, this stackoverflowed despite the laziness
precautions in findMember.

Todo: Do the same for class files coming from Java and Scala 2.x.

7 files changed, 179 insertions, 28 deletions

diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala
index fcc01503f..fd47ee4ec 100644
--- a/src/dotty/tools/dotc/core/SymDenotations.scala
+++ b/src/dotty/tools/dotc/core/SymDenotations.scala
@@ -1471,6 +1471,8 @@ object SymDenotations {
     def complete(denot: SymDenotation)(implicit ctx: Context): Unit = unsupported("complete")
   }
 
+  object NoCompleter extends NoCompleter
+
   /** A lazy type for modules that points to the module class.
    *  Needed so that `moduleClass` works before completion.
    *  Completion of modules is always completion of the underlying
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 1e1d02be2..797712459 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -315,7 +315,8 @@ class TypeComparer(initctx: Context) extends DotClass {
   private def rebase(tp: NamedType): Type = {
     def rebaseFrom(prefix: Type): Type = {
       rebaseQual(prefix, tp.name, considerBoth = true) match {
-        case rt: RefinedType if rt ne prefix => tp.derivedSelect(RefinedThis(rt))
+        case rt: RefinedType if rt ne prefix =>
+          tp.derivedSelect(RefinedThis(rt)).dealias // dealias to short-circuit cycles spanning type aliases or LazyRefs
         case _ => tp
       }
     }
@@ -511,6 +512,8 @@ class TypeComparer(initctx: Context) extends DotClass {
           case NoType => true
         }
         compareWild
+      case tp2: LazyRef =>
+        isSubType(tp1, tp2.ref)
       case tp2: AnnotatedType =>
         isSubType(tp1, tp2.tpe) // todo: refine?
       case AndType(tp21, tp22) =>
@@ -568,6 +571,8 @@ class TypeComparer(initctx: Context) extends DotClass {
         case _ => true
       }
       compareWild
+    case tp1: LazyRef =>
+      isSubType(tp1.ref, tp2)
     case tp1: AnnotatedType =>
       isSubType(tp1.tpe, tp2)
     case ErrorType =>
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 592b7b55f..a81d200d3 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -31,6 +31,8 @@ import language.implicitConversions
 
 object Types {
 
+  private var recCount = 0
+
   /** The class of types.
    *  The principal subclasses and sub-objects are as follows:
    *
@@ -379,6 +381,8 @@ object Types {
      *  flags in `excluded` from consideration.
      */
     final def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Denotation = try {
+      recCount += 1
+      assert(recCount < 20)
       @tailrec def go(tp: Type): Denotation = tp match {
         case tp: RefinedType =>
           if (name eq tp.refinedName) goRefined(tp) else go(tp.parent)
@@ -436,8 +440,10 @@ object Types {
       case ex: MergeError =>
         throw new MergeError(s"${ex.getMessage} as members of type ${pre.show}")
       case ex: Throwable =>
-        println(s"error occurred during: $this: ${this.widen} member $name")
+        println(i"findMember exception for $this: ${this.widen} member $name")
         throw ex // DEBUG
+    } finally {
+      recCount -= 1
     }
 
     /** The set of names of members of this type that pass the given name filter
@@ -599,7 +605,9 @@ object Types {
       case _ => this
     }
 
-    /** Follow aliases until type is no longer an alias type. */
+    /** Follow aliases and derefernces LazyRefs and instantiated TypeVars until type
+     *  is no longer alias type, LazyRef, or instantiated type variable.
+     */
     final def dealias(implicit ctx: Context): Type = this match {
       case tp: TypeRef =>
         tp.info match {
@@ -609,6 +617,8 @@ object Types {
       case tp: TypeVar =>
         val tp1 = tp.instanceOpt
         if (tp1.exists) tp1.dealias else tp
+      case tp: LazyRef =>
+        tp.ref.dealias
       case tp => tp
     }
 
@@ -643,6 +653,14 @@ object Types {
       case _ => NoType
     }
 
+    /** The chain of underlying types as long as type is a TypeProxy.
+     *  Useful for diagnostics
+     */
+    def underlyingChain(implicit ctx: Context): List[Type] = this match {
+      case tp: TypeProxy => tp :: tp.underlying.underlyingChain
+      case _ => Nil
+    }
+
     /** A prefix-less termRef to a new skolem symbol that has the given type as info */
     def narrow(implicit ctx: Context): TermRef = TermRef(NoPrefix, ctx.newSkolem(this))
 
@@ -1469,6 +1487,12 @@ object Types {
       unique(new CachedConstantType(value))
   }
 
+  case class LazyRef(refFn: () => Type) extends UncachedProxyType with TermType {
+    lazy val ref = refFn()
+    override def underlying(implicit ctx: Context) = ref
+    override def toString = s"LazyRef($ref)"
+  }
+
   // --- Refined Type ---------------------------------------------------------
 
   /** A refined type parent { refinement }
@@ -2408,6 +2432,9 @@ object Types {
         case tp @ SuperType(thistp, supertp) =>
           tp.derivedSuperType(this(thistp), this(supertp))
 
+        case tp: LazyRef =>
+          LazyRef(() => this(tp.ref))
+
         case tp: ClassInfo =>
           mapClassInfo(tp)
 
diff --git a/src/dotty/tools/dotc/transform/FirstTransform.scala b/src/dotty/tools/dotc/transform/FirstTransform.scala
index dbf4f3a2f..d7010e821 100644
--- a/src/dotty/tools/dotc/transform/FirstTransform.scala
+++ b/src/dotty/tools/dotc/transform/FirstTransform.scala
@@ -83,14 +83,11 @@ class FirstTransform extends TreeTransform with IdentityDenotTransformer { thisT
   override def transformOther(tree: Tree)(implicit ctx: Context, info: TransformerInfo) = tree match {
     case tree: Import => EmptyTree
     case tree: NamedArg => tree.arg
-/* not yet enabled
     case AppliedTypeTree(tycon, args) =>
-
       val tparams = tycon.tpe.typeSymbol.typeParams
       Checking.checkBounds(
         args, tparams.map(_.info.bounds), (tp, argTypes) => tp.substDealias(tparams, argTypes))
       TypeTree(tree.tpe).withPos(tree.pos)
-*/
     case tree =>
       if (tree.isType) TypeTree(tree.tpe, tree).withPos(tree.pos)
       else tree
diff --git a/src/dotty/tools/dotc/typer/Checking.scala b/src/dotty/tools/dotc/typer/Checking.scala
index 7da00e051..cd2e9b55f 100644
--- a/src/dotty/tools/dotc/typer/Checking.scala
+++ b/src/dotty/tools/dotc/typer/Checking.scala
@@ -4,8 +4,16 @@ package typer
 
 import core._
 import ast._
-import Contexts._, Types._, Flags._, Denotations._, Names._, StdNames._, NameOps._, Symbols._
-import Trees._, ProtoTypes._
+import Contexts._
+import Types._
+import Flags._
+import Denotations._
+import Names._
+import StdNames._
+import NameOps._
+import Symbols._
+import Trees._
+import ProtoTypes._
 import Constants._
 import Scopes._
 import annotation.unchecked
@@ -14,13 +22,125 @@ import util.{Stats, SimpleMap}
 import util.common._
 import Decorators._
 import Uniques._
-import ErrorReporting.{errorType, DiagnosticString}
+import ErrorReporting.{err, errorType, DiagnosticString}
 import config.Printers._
 import collection.mutable
+import SymDenotations.NoCompleter
+
+object Checking {
+  import tpd._
+
+  /** A general checkBounds method that can be used for TypeApply nodes as
+   *  well as for AppliedTypeTree nodes.
+   */
+  def checkBounds(args: List[tpd.Tree], bounds: List[TypeBounds], instantiate: (Type, List[Type]) => Type)(implicit ctx: Context) = {
+    val argTypes = args.tpes
+    for ((arg, bounds) <- args zip bounds) {
+      def notConforms(which: String, bound: Type) = {
+        ctx.error(
+          d"Type argument ${arg.tpe} does not conform to $which bound $bound ${err.whyNoMatchStr(arg.tpe, bound)}",
+          arg.pos)
+      }
+      def checkOverlapsBounds(lo: Type, hi: Type): Unit = {
+        //println(i"instantiating ${bounds.hi} with $argTypes")
+        //println(i" = ${instantiate(bounds.hi, argTypes)}")
+        val hiBound = instantiate(bounds.hi, argTypes)
+        if (!(lo <:< hiBound)) notConforms("upper", hiBound)
+        if (!(bounds.lo <:< hi)) notConforms("lower", bounds.lo)
+      }
+      arg.tpe match {
+        case TypeBounds(lo, hi) => checkOverlapsBounds(lo, hi)
+        case tp => checkOverlapsBounds(tp, tp)
+      }
+    }
+  }
+
+  /** A type map which checks that the only cycles in a type are F-bounds
+   *  and that protects all F-bounded references by LazyRefs.
+   */
+  class CheckNonCyclicMap(implicit ctx: Context) extends TypeMap {
+
+    /** Are cycles allowed within nested refinedInfos of currently checked type? */
+    private var nestedCycleOK = false
+
+    /** Are cycles allwoed within currently checked type? */
+    private var cycleOK = false
+
+    /** A diagnostic output string that indicates the position of the last
+     *  part of a type bounds checked by checkInfo. Possible choices:
+     *  alias, lower bound, upper bound.
+     */
+    var where: String = ""
+
+    /** Check info `tp` for cycles. Throw CyclicReference for illegal cycles,
+     *  break direct cycle with a LazyRef for legal, F-bounded cycles.
+     */
+    def checkInfo(tp: Type): Type = tp match {
+      case tp @ TypeBounds(lo, hi) =>
+        if (lo eq hi)
+          try tp.derivedTypeAlias(apply(lo))
+          finally where = "alias"
+        else {
+          val lo1 = try apply(lo) finally where = "lower bound"
+          val saved = nestedCycleOK
+          nestedCycleOK = true
+          try tp.derivedTypeBounds(lo1, apply(hi))
+          finally {
+            nestedCycleOK = saved
+            where = "upper bound"
+          }
+        }
+      case _ =>
+        tp
+    }
+
+    def apply(tp: Type) = tp match {
+      case tp @ RefinedType(parent, name) =>
+        val parent1 = this(parent)
+        val saved = cycleOK
+        cycleOK = nestedCycleOK
+        try tp.derivedRefinedType(parent1, name, this(tp.refinedInfo))
+        finally cycleOK = saved
+      case tp @ TypeRef(pre, name) =>
+        try {
+          // Check info of typeref recursively, marking the referred symbol
+          // with NoCompleter. This provokes a CyclicReference when the symbol
+          // is hit again. Without this precaution we could stackoverflow here.
+          val info = tp.info
+          val symInfo = tp.symbol.info
+          if (tp.symbol.exists) tp.symbol.info = SymDenotations.NoCompleter
+          try checkInfo(info)
+          finally if (tp.symbol.exists) tp.symbol.info = symInfo
+          tp
+        } catch {
+          case ex: CyclicReference =>
+            ctx.debuglog(i"cycle detected for $tp, $nestedCycleOK, $cycleOK")
+            if (cycleOK) LazyRef(() => tp) else throw ex
+        }
+      case _ => mapOver(tp)
+    }
+  }
+}
 
 trait Checking {
 
   import tpd._
+  import Checking._
+
+  /** Check that `info` of symbol `sym` is not cyclic.
+   *  @pre     sym is not yet initialized (i.e. its type is a Completer).
+   *  @return  `info` where every legal F-bounded reference is proctected
+   *                  by a `LazyRef`, or `ErrorType` if a cycle was detected and reported.
+   */
+  def checkNonCyclic(sym: Symbol, info: TypeBounds)(implicit ctx: Context): Type = {
+    val checker = new CheckNonCyclicMap
+    try checker.checkInfo(info)
+    catch {
+      case ex: CyclicReference =>
+        ctx.error(i"illegal cyclic reference: ${checker.where} $info of $sym refers back to the type itself", sym.pos)
+        ErrorType
+      }
+  }
 
   /** Check that Java statics and packages can only be used in selections.
    */
@@ -32,17 +152,13 @@ trait Checking {
     tree
   }
 
-  /** Check that type arguments `args` conform to corresponding bounds in `poly` */
-  def checkBounds(args: List[tpd.Tree], poly: PolyType, pos: Position)(implicit ctx: Context): Unit = {
-    val argTypes = args.tpes
-    def substituted(tp: Type) = tp.substParams(poly, argTypes)
-    for ((arg, bounds) <- args zip poly.paramBounds) {
-      def notConforms(which: String, bound: Type) =
-        ctx.error(d"Type argument ${arg.tpe} does not conform to $which bound $bound", arg.pos)
-      if (!(arg.tpe <:< substituted(bounds.hi))) notConforms("upper", bounds.hi)
-      if (!(bounds.lo <:< arg.tpe)) notConforms("lower", bounds.lo)
-    }
-  }
+  /** Check that type arguments `args` conform to corresponding bounds in `poly`
+   *  Note: This does not check the bounds of AppliedTypeTrees. These
+   *  are handled by method checkBounds in FirstTransform
+   *  TODO: remove pos parameter
+   */
+  def checkBounds(args: List[tpd.Tree], poly: PolyType, pos: Position)(implicit ctx: Context): Unit =    Checking.checkBounds(
+      args, poly.paramBounds, (tp, argTypes) => tp.substParams(poly, argTypes))
 
   /** Check that type `tp` is stable. */
   def checkStable(tp: Type, pos: Position)(implicit ctx: Context): Unit =
diff --git a/src/dotty/tools/dotc/typer/ErrorReporting.scala b/src/dotty/tools/dotc/typer/ErrorReporting.scala
index f20d25792..1f55df2bc 100644
--- a/src/dotty/tools/dotc/typer/ErrorReporting.scala
+++ b/src/dotty/tools/dotc/typer/ErrorReporting.scala
@@ -97,19 +97,21 @@ object ErrorReporting {
       errorTree(tree, typeMismatchStr(tree.tpe, pt) + implicitFailure.postscript)
     }
 
+    /** A subtype log explaining why `found` does not conform to `expected` */
+    def whyNoMatchStr(found: Type, expected: Type) =
+      if (ctx.settings.explaintypes.value)
+        "\n" + ctx.typerState.show + "\n" + TypeComparer.explained((found <:< expected)(_))
+      else
+        ""
+
     def typeMismatchStr(found: Type, expected: Type) = disambiguated { implicit ctx =>
-      val (typerStateStr, explanationStr) =
-        if (ctx.settings.explaintypes.value)
-          ("\n" + ctx.typerState.show, "\n" + TypeComparer.explained((found <:< expected)(_)))
-        else
-          ("", "")
       def infoStr = found match { // DEBUG
           case tp: TypeRef => s"with info ${tp.info} / ${tp.prefix.toString} / ${tp.prefix.dealias.toString}"
           case _ => ""
         }
       d"""type mismatch:
            | found   : $found
-           | required: $expected""".stripMargin + typerStateStr + explanationStr
+           | required: $expected""".stripMargin + whyNoMatchStr(found, expected)
     }
   }
 
diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala
index 14404e220..afa270d46 100644
--- a/src/dotty/tools/dotc/typer/Namer.scala
+++ b/src/dotty/tools/dotc/typer/Namer.scala
@@ -674,9 +674,11 @@ class Namer { typer: Typer =>
       if (needsLambda) rhsType.LambdaAbstract(tparamSyms)
       else if (toParameterize) rhsType.parameterizeWith(tparamSyms)
       else rhsType
-    rhsType match {
-      case _: TypeBounds => abstractedRhsType
+    val unsafeInfo = rhsType match {
+      case _: TypeBounds => abstractedRhsType.asInstanceOf[TypeBounds]
       case _ => TypeAlias(abstractedRhsType, if (sym is Local) sym.variance else 0)
     }
+    sym.info = NoCompleter
+    checkNonCyclic(sym, unsafeInfo)
   }
 }
\ No newline at end of file