From f87153bc5d74f66e2fcf22dc7282da31813430da Mon Sep 17 00:00:00 2001
From: Martin Odersky <odersky@gmail.com>
Date: Thu, 7 Aug 2014 20:25:23 +0200
Subject: 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.
---
 src/dotty/tools/dotc/core/SymDenotations.scala |  2 ++
 src/dotty/tools/dotc/core/TypeComparer.scala   |  7 +++++-
 src/dotty/tools/dotc/core/Types.scala          | 31 ++++++++++++++++++++++++--
 3 files changed, 37 insertions(+), 3 deletions(-)

(limited to 'src/dotty/tools/dotc/core')

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)
 
-- 
cgit v1.2.3