Introduce recursive types

Map self-references in refinements to recursive types. This
commit does this for refinement types appearing in source.
We still have to do it for unpickled refinements.

Test apply-equiv got moved to pending because it simulates
the old higher-kinded type encoding in source, which relies
on the old representation in terms of self-referential refinement
types. The plan is not to adapt this encoding to the new
representation, but to replace it with a different encoding
that makes critical use of the added power of recursive types.

Use recursive types also when unpickling from Scala 2.x.

Add mapInfo method to Denotations.

16 files changed, 292 insertions, 37 deletions

diff --git a/src/dotty/tools/dotc/core/Denotations.scala b/src/dotty/tools/dotc/core/Denotations.scala
index 5ce8cbcd8..494df7547 100644
--- a/src/dotty/tools/dotc/core/Denotations.scala
+++ b/src/dotty/tools/dotc/core/Denotations.scala
@@ -146,6 +146,9 @@ object Denotations {
     /** Is this denotation different from NoDenotation or an ErrorDenotation? */
     def exists: Boolean = true
 
+    /** A denotation with the info of this denotation transformed using `f` */
+    def mapInfo(f: Type => Type)(implicit ctx: Context): Denotation
+
     /** If this denotation does not exist, fallback to alternative */
     final def orElse(that: => Denotation) = if (this.exists) this else that
 
@@ -242,7 +245,7 @@ object Denotations {
       }
       else if (exists && !qualifies(symbol)) NoDenotation
       else asSingleDenotation
-     }
+    }
 
     /** Form a denotation by conjoining with denotation `that`.
      *
@@ -456,6 +459,8 @@ object Denotations {
       else if (!d2.exists) d1
       else derivedMultiDenotation(d1, d2)
     }
+    def mapInfo(f: Type => Type)(implicit ctx: Context): Denotation =
+      derivedMultiDenotation(denot1.mapInfo(f), denot2.mapInfo(f))
     def derivedMultiDenotation(d1: Denotation, d2: Denotation) =
       if ((d1 eq denot1) && (d2 eq denot2)) this else MultiDenotation(d1, d2)
     override def toString = alternatives.mkString(" <and> ")
@@ -488,6 +493,9 @@ object Denotations {
       if ((symbol eq this.symbol) && (info eq this.info)) this
       else newLikeThis(symbol, info)
 
+    def mapInfo(f: Type => Type)(implicit ctx: Context): SingleDenotation =
+      derivedSingleDenotation(symbol, f(info))
+
     def orElse(that: => SingleDenotation) = if (this.exists) this else that
 
     def altsWith(p: Symbol => Boolean): List[SingleDenotation] =
diff --git a/src/dotty/tools/dotc/core/Substituters.scala b/src/dotty/tools/dotc/core/Substituters.scala
index 0083ac626..4598aaa20 100644
--- a/src/dotty/tools/dotc/core/Substituters.scala
+++ b/src/dotty/tools/dotc/core/Substituters.scala
@@ -197,6 +197,24 @@ trait Substituters { this: Context =>
           .mapOver(tp)
     }
 
+  final def substRecThis(tp: Type, from: Type, to: Type, theMap: SubstRecThisMap): Type =
+    tp match {
+      case tp @ RecThis(binder) =>
+        if (binder eq from) to else tp
+      case tp: NamedType =>
+        if (tp.currentSymbol.isStatic) tp
+        else tp.derivedSelect(substRecThis(tp.prefix, from, to, theMap))
+      case _: ThisType | _: BoundType | NoPrefix =>
+        tp
+      case tp: RefinedType =>
+        tp.derivedRefinedType(substRecThis(tp.parent, from, to, theMap), tp.refinedName, substRecThis(tp.refinedInfo, from, to, theMap))
+      case tp: TypeAlias =>
+        tp.derivedTypeAlias(substRecThis(tp.alias, from, to, theMap))
+      case _ =>
+        (if (theMap != null) theMap else new SubstRecThisMap(from, to))
+          .mapOver(tp)
+    }
+
   final def substParam(tp: Type, from: ParamType, to: Type, theMap: SubstParamMap): Type =
     tp match {
       case tp: BoundType =>
@@ -270,6 +288,10 @@ trait Substituters { this: Context =>
     def apply(tp: Type): Type = substRefinedThis(tp, from, to, this)
   }
 
+  final class SubstRecThisMap(from: Type, to: Type) extends DeepTypeMap {
+    def apply(tp: Type): Type = substRecThis(tp, from, to, this)
+  }
+
   final class SubstParamMap(from: ParamType, to: Type) extends DeepTypeMap {
     def apply(tp: Type) = substParam(tp, from, to, this)
   }
diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala
index 5c4e120a8..7715885c4 100644
--- a/src/dotty/tools/dotc/core/SymDenotations.scala
+++ b/src/dotty/tools/dotc/core/SymDenotations.scala
@@ -1121,10 +1121,11 @@ object SymDenotations {
 
     def debugString = toString + "#" + symbol.id // !!! DEBUG
 
-        def hasSkolems(tp: Type): Boolean = tp match {
+    def hasSkolems(tp: Type): Boolean = tp match {
       case tp: SkolemType => true
       case tp: NamedType => hasSkolems(tp.prefix)
       case tp: RefinedType => hasSkolems(tp.parent) || hasSkolems(tp.refinedInfo)
+      case tp: RecType => hasSkolems(tp.parent)
       case tp: PolyType => tp.paramBounds.exists(hasSkolems) || hasSkolems(tp.resType)
       case tp: MethodType => tp.paramTypes.exists(hasSkolems) || hasSkolems(tp.resType)
       case tp: ExprType => hasSkolems(tp.resType)
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index 2411e0bb2..bd115fefb 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -22,10 +22,16 @@ object TypeApplicationsNewHK {
   import TypeApplications._
 
   object TypeLambda {
-    def apply(argBindingFns: List[RefinedType => TypeBounds],
-              bodyFn: RefinedType => Type)(implicit ctx: Context): Type = {
+    def apply(argBindingFns: List[RecType => TypeBounds],
+              bodyFn: RecType => Type)(implicit ctx: Context): Type = {
       val argNames = argBindingFns.indices.toList.map(tpnme.hkArg)
-      RefinedType.recursive(bodyFn, argNames, argBindingFns)
+      var idx = 0
+      RecType.closeOver(rt =>
+        (bodyFn(rt) /: argBindingFns) { (parent, argBindingFn) =>
+          val res = RefinedType(parent, tpnme.hkArg(idx), argBindingFn(rt))
+          idx += 1
+          res
+        })
     }
 
     def unapply(tp: Type)(implicit ctx: Context): Option[(List[TypeBounds], Type)] = {
@@ -33,6 +39,8 @@ object TypeApplicationsNewHK {
         case t @ RefinedType(p, rname, rinfo: TypeBounds)
         if rname.isHkArgName && rinfo.isBinding =>
           decompose(p, rinfo.bounds :: acc)
+        case t: RecType =>
+          decompose(t.parent, acc)
         case _ =>
           (acc, t)
       }
@@ -78,13 +86,13 @@ object TypeApplications {
    *    [v1 X1: B1, ..., vn Xn: Bn] -> T
    *    ==>
    *    ([X_i := this.$hk_i] T) { type v_i $hk_i: (new)B_i }
-   *    
+   *
    *    [X] -> List[X]
-   *    
+   *
    *    List { type List$A = this.$hk_0 } { type $hk_0 }
-   *    
+   *
    *    [X] -> X
-   *    
+   *
    *    mu(this) this.$hk_0 & { type $hk_0 }
    */
   object TypeLambda {
@@ -212,6 +220,10 @@ object TypeApplications {
   def argRefs(rt: RefinedType, n: Int)(implicit ctx: Context) =
     List.range(0, n).map(i => RefinedThis(rt).select(tpnme.hkArg(i)))
 
+  /** The references `<rt>.this.$hk0, ..., <rt>.this.$hk<n-1>`. */
+  def argRefs(rt: RecType, n: Int)(implicit ctx: Context) =
+    List.range(0, n).map(i => RecThis(rt).select(tpnme.hkArg(i)))
+
   /** Merge `tp1` and `tp2` under a common lambda, combining them with `op`.
    *  @param tparams1   The type parameters of `tp1`
    *  @param tparams2   The type parameters of `tp2`
@@ -400,7 +412,7 @@ class TypeApplications(val self: Type) extends AnyVal {
    *  but without forcing anything.
    */
   def classNotLambda(implicit ctx: Context): Boolean = self.stripTypeVar match {
-    case self: RefinedType =>
+    case self: RefinedOrRecType =>
       self.parent.classNotLambda
     case self: TypeRef =>
       self.denot.exists && {
@@ -428,6 +440,14 @@ class TypeApplications(val self: Type) extends AnyVal {
       new ctx.SafeSubstMap(tparams, argRefs(rt, tparams.length))
         .apply(self).asInstanceOf[T]
 
+  /** Replace references to type parameters with references to hk arguments `this.$hk_i`
+   * Care is needed not to cause cyclic reference errors, hence `SafeSubstMap`.
+   */
+  def recursify[T <: Type](tparams: List[Symbol])(implicit ctx: Context): RecType => T =
+    (rt: RecType) =>
+      new ctx.SafeSubstMap(tparams, argRefs(rt, tparams.length))
+        .apply(self).asInstanceOf[T]
+
   /** Lambda abstract `self` with given type parameters. Examples:
    *
    *      type T[X] = U        becomes    type T = [X] -> U
@@ -546,6 +566,8 @@ class TypeApplications(val self: Type) extends AnyVal {
           arg.prefix.select(boundLambda)
         case arg: RefinedType =>
           arg.derivedRefinedType(adaptArg(arg.parent), arg.refinedName, arg.refinedInfo)
+        case arg: RecType =>
+          arg.derivedRecType(adaptArg(arg.parent))
         case arg @ TypeAlias(alias) =>
           arg.derivedTypeAlias(adaptArg(alias))
         case arg @ TypeBounds(lo, hi) =>
@@ -814,6 +836,8 @@ class TypeApplications(val self: Type) extends AnyVal {
         }
       case tp: RefinedType =>
         recur(tp.refinedInfo) || recur(tp.parent)
+      case tp: RecType =>
+        recur(tp.parent)
       case tp: TypeBounds =>
         recur(tp.lo) || recur(tp.hi)
       case tp: AnnotatedType =>
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index d1dc4069d..9909c9e8a 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -378,6 +378,9 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
           isSubRefinements(tp1w.asInstanceOf[RefinedType], tp2, skipped2)
       }
       compareRefined
+    case tp2: RecType =>
+      val tp1stable = ensureStableSingleton(tp1)
+      isSubType(fixRecs(tp1stable, tp1stable.widenExpr), tp2.substRecThis(tp2, tp1stable))
     case OrType(tp21, tp22) =>
       // Rewrite T1 <: (T211 & T212) | T22 to T1 <: (T211 | T22) and T1 <: (T212 | T22)
       // and analogously for T1 <: T21 | (T221 & T222)
@@ -465,7 +468,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
         case _ =>
           def isNullable(tp: Type): Boolean = tp.dealias match {
             case tp: TypeRef => tp.symbol.isNullableClass
-            case tp: RefinedType => isNullable(tp.parent)
+            case tp: RefinedOrRecType => isNullable(tp.parent)
             case AndType(tp1, tp2) => isNullable(tp1) && isNullable(tp2)
             case OrType(tp1, tp2) => isNullable(tp1) || isNullable(tp2)
             case _ => false
@@ -494,6 +497,8 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       isNewSubType(tp1.parent, tp2) ||
       compareHkLambda(tp1, tp2, inOrder = true) ||
       compareAliasedRefined(tp1, tp2, inOrder = true)
+    case tp1: RecType =>
+      isNewSubType(tp1.parent, tp2)
     case AndType(tp11, tp12) =>
       // Rewrite (T111 | T112) & T12 <: T2 to (T111 & T12) <: T2 and (T112 | T12) <: T2
       // and analogously for T11 & (T121 | T122) & T12 <: T2
@@ -642,6 +647,25 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
     }
   }
 
+  /** Replace any top-level recursive type `{ z => T }` in `tp` with 
+   *  `[z := anchor]T`.
+   */
+  private def fixRecs(anchor: SingletonType, tp: Type): Type = {
+    def fix(tp: Type): Type = tp.stripTypeVar match {
+      case tp: RecType => fix(tp.parent).substRecThis(tp, anchor)
+      case tp @ RefinedType(parent, rname, rinfo) => tp.derivedRefinedType(fix(parent), rname, rinfo)
+      case tp: PolyParam => fixOrElse(bounds(tp).hi, tp)
+      case tp: TypeProxy => fixOrElse(tp.underlying, tp)
+      case tp: AndOrType => tp.derivedAndOrType(fix(tp.tp1), fix(tp.tp2))
+      case tp => tp
+    }
+    def fixOrElse(tp: Type, fallback: Type) = {
+      val tp1 = fix(tp)
+      if (tp1 ne tp) tp1 else fallback
+    }
+    fix(tp)
+  }
+
   /** The symbol referred to in the refinement of `rt` */
   private def refinedSymbol(rt: RefinedType) = rt.parent.member(rt.refinedName).symbol
 
@@ -772,7 +796,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
 
   /** A type has been covered previously in subtype checking if it
    *  is some combination of TypeRefs that point to classes, where the
-   *  combiners are RefinedTypes, AndTypes or AnnotatedTypes.
+   *  combiners are RefinedTypes, RecTypes, AndTypes or AnnotatedTypes.
    *  One exception: Refinements referring to basetype args are never considered
    *  to be already covered. This is necessary because such refined types might
    *  still need to be compared with a compareAliasRefined.
@@ -781,6 +805,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
     case tp: TypeRef => tp.symbol.isClass && tp.symbol != NothingClass && tp.symbol != NullClass
     case tp: ProtoType => false
     case tp: RefinedType => isCovered(tp.parent) && !refinedSymbol(tp).is(BaseTypeArg)
+    case tp: RecType => isCovered(tp.parent)
     case tp: AnnotatedType => isCovered(tp.underlying)
     case AndType(tp1, tp2) => isCovered(tp1) && isCovered(tp2)
     case _ => false
@@ -1118,6 +1143,8 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
         case _ =>
           NoType
       }
+    case tp1: RecType =>
+      tp1.rebind(distributeAnd(tp1.parent, tp2))
     case tp1: TypeBounds =>
       tp2 match {
         case tp2: TypeBounds => tp1 & tp2
diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala
index 72b0c87c4..54846087f 100644
--- a/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/src/dotty/tools/dotc/core/TypeOps.scala
@@ -232,11 +232,16 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
           }
         case _ =>
       }
+
       tp1 match {
+        case tp1: RecType =>
+          tp1.rebind(approximateOr(tp1.parent, tp2))
         case tp1: TypeProxy if !isClassRef(tp1) =>
           approximateUnion(next(tp1) | tp2)
         case _ =>
           tp2 match {
+            case tp2: RecType =>
+              tp2.rebind(approximateOr(tp1, tp2.parent))
             case tp2: TypeProxy if !isClassRef(tp2) =>
               approximateUnion(tp1 | next(tp2))
             case _ =>
@@ -252,16 +257,32 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
     if (ctx.featureEnabled(defn.LanguageModuleClass, nme.keepUnions)) tp
     else tp match {
       case tp: OrType =>
-        approximateOr(tp.tp1, tp.tp2)
+        approximateOr(tp.tp1, tp.tp2)  // Maybe refactor using liftToRec?
       case tp @ AndType(tp1, tp2) =>
         tp derived_& (approximateUnion(tp1), approximateUnion(tp2))
       case tp: RefinedType =>
         tp.derivedRefinedType(approximateUnion(tp.parent), tp.refinedName, tp.refinedInfo)
+      case tp: RecType =>
+        tp.rebind(approximateUnion(tp.parent))
       case _ =>
         tp
     }
   }
 
+  /** Not currently needed:
+   *
+  def liftToRec(f: (Type, Type) => Type)(tp1: Type, tp2: Type)(implicit ctx: Context) = {
+    def f2(tp1: Type, tp2: Type): Type = tp2 match {
+      case tp2: RecType => tp2.rebind(f(tp1, tp2.parent))
+      case _ => f(tp1, tp2)
+    }
+    tp1 match {
+      case tp1: RecType => tp1.rebind(f2(tp1.parent, tp2))
+      case _ => f2(tp1, tp2)
+    }
+  }
+  */
+
   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 = {
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 8eae84a51..5252a9149 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -54,7 +54,8 @@ object Types {
    *        |              |                +----RefinedThis
    *        |              |                +--- SkolemType
    *        |              +- PolyParam
-   *        |              +- RefinedType
+   *        |              +- RefinedOrRecType -+-- RefinedType
+   *        |              |                   -+-- RecType
    *        |              +- TypeBounds
    *        |              +- ExprType
    *        |              +- AnnotatedType
@@ -97,7 +98,7 @@ object Types {
     final def isStable(implicit ctx: Context): Boolean = stripTypeVar match {
       case tp: TermRef => tp.termSymbol.isStable && tp.prefix.isStable
       case _: SingletonType | NoPrefix => true
-      case tp: RefinedType => tp.parent.isStable
+      case tp: RefinedOrRecType => tp.parent.isStable
       case _ => false
     }
 
@@ -113,7 +114,7 @@ object Types {
           case TypeAlias(tp) => tp.isRef(sym)
           case _ =>  this1.symbol eq sym
         }
-      case this1: RefinedType =>
+      case this1: RefinedOrRecType =>
         this1.parent.isRef(sym)
       case _ =>
         false
@@ -447,6 +448,8 @@ object Types {
           })
         case tp: PolyParam =>
           goParam(tp)
+        case tp: RecType =>
+          goRec(tp)
         case tp: TypeProxy =>
           go(tp.underlying)
         case tp: ClassInfo =>
@@ -462,6 +465,8 @@ object Types {
         case _ =>
           NoDenotation
       }
+      def goRec(tp: RecType) =
+        go(tp.parent).mapInfo(_.substRecThis(tp, pre))
       def goRefined(tp: RefinedType) = {
         val pdenot = go(tp.parent)
         val rinfo =
@@ -864,6 +869,7 @@ object Types {
         def isParamName = tp.classSymbol.typeParams.exists(_.name == tp.refinedName)
         if (refinementOK || isParamName) tp.underlying.underlyingClassRef(refinementOK)
         else NoType
+      case tp: RecType if refinementOK => tp.parent 
       case _ => NoType
     }
 
@@ -958,6 +964,13 @@ object Types {
               }
             case _ => loop(pre.parent)
           }
+        case pre: RecType =>
+          val candidate = loop(pre.parent)
+          if (candidate.exists && !pre.isReferredToBy(candidate)) {
+            //println(s"lookupRefined ${this.toString} . $name, pre: $pre ---> $candidate / ${candidate.toString}")
+            candidate
+          }
+          else NoType
         case RefinedThis(binder) =>
           binder.lookupRefined(name)
         case SkolemType(tp) =>
@@ -1152,6 +1165,10 @@ object Types {
     final def substRefinedThis(binder: Type, tp: Type)(implicit ctx: Context): Type =
       ctx.substRefinedThis(this, binder, tp, null)
 
+    /** Substitute all occurrences of `RecThis(binder)` by `tp` */
+    final def substRecThis(binder: RecType, tp: Type)(implicit ctx: Context): Type =
+      ctx.substRecThis(this, binder, tp, null)
+
     /** Substitute a bound type by some other type */
     final def substParam(from: ParamType, to: Type)(implicit ctx: Context): Type =
       ctx.substParam(this, from, to, null)
@@ -2022,7 +2039,11 @@ object Types {
     override def hashCode = ref.hashCode + 37
   }
 
-  // --- Refined Type ---------------------------------------------------------
+  // --- Refined Type and RecType ------------------------------------------------
+
+  abstract class RefinedOrRecType extends CachedProxyType with ValueType {
+    def parent: Type
+  }
 
   /** A refined type parent { refinement }
    *  @param refinedName  The name of the refinement declaration
@@ -2030,7 +2051,7 @@ object Types {
    *                 given the refined type itself.
    */
   abstract case class RefinedType(private var myParent: Type, refinedName: Name, private var myRefinedInfo: Type)
-    extends CachedProxyType with BindingType with ValueType {
+    extends RefinedOrRecType with BindingType {
 
     final def parent = myParent
     final def refinedInfo = myRefinedInfo
@@ -2082,7 +2103,7 @@ object Types {
       doHash(refinedName, refinedInfo, parent)
     }
 
-    override def toString = s"RefinedType($parent, $refinedName, $refinedInfo | $hashCode)"
+    override def toString = s"RefinedType($parent, $refinedName, $refinedInfo)"
   }
 
   class CachedRefinedType(refinedName: Name) extends RefinedType(NoType, refinedName, NoType)
@@ -2122,6 +2143,73 @@ object Types {
     }
   }
 
+  class RecType(parentExp: RecType => Type) extends RefinedOrRecType with BindingType {
+
+    val parent = parentExp(this)
+
+    override def underlying(implicit ctx: Context): Type = parent
+
+    def derivedRecType(parent: Type)(implicit ctx: Context): RecType =
+      if (parent eq this.parent) this
+      else RecType(rt => parent.substRecThis(this, RecThis(rt)))
+
+    def rebind(parent: Type)(implicit ctx: Context): Type =
+      if (parent eq this.parent) this
+      else RecType.closeOver(rt => parent.substRecThis(this, RecThis(rt)))
+
+    override def equals(other: Any) = other match {
+      case other: RecType => other.parent == this.parent
+      case _ => false
+    }
+
+    def isReferredToBy(tp: Type)(implicit ctx: Context): Boolean = {
+      val refacc = new TypeAccumulator[Boolean] {
+        override def apply(x: Boolean, tp: Type) = x || {
+          tp match {
+            case tp: TypeRef => apply(x, tp.prefix)
+            case tp: RecThis => RecType.this eq tp.binder
+            case _ => foldOver(x, tp)
+          }
+        }
+      }
+      refacc.apply(false, tp)
+    }
+
+    override def computeHash = doHash(parent)
+
+    override def toString = s"RecType($parent | $hashCode)"
+  }
+
+  object RecType {
+    def checkInst(tp: Type)(implicit ctx: Context): tp.type = {
+      var binders: List[RecType] = Nil
+      tp.foreachPart {
+        case rt: RecType => binders = rt :: binders
+        case rt: RecThis => assert(binders contains rt.binder, tp)
+        case _ =>
+      }
+      tp
+    }
+    def apply(parentExp: RecType => Type)(implicit ctx: Context): RecType = checkInst {
+      var rt = new RecType(parentExp)
+      rt.parent match {
+        case rt2: RecType =>
+          rt = rt2.derivedRecType(rt2.parent.substRecThis(rt, RecThis(rt2)))
+        case _ =>
+      }
+      unique(rt)
+    }
+    def closeOver(parentExp: RecType => Type)(implicit ctx: Context) = checkInst {
+      val rt = this(parentExp)
+      //val self = RecThis(rt)
+      def isSelfRef(t: Type) = t match {
+        case RecThis(binder) => binder eq rt
+        case _ => false
+      }
+      if (rt.existsPart(isSelfRef)) rt else rt.parent
+    }
+  }
+
   // --- AndType/OrType ---------------------------------------------------------------
 
   trait AndOrType extends ValueType { // todo: check where we can simplify using AndOrType
@@ -2587,6 +2675,22 @@ object Types {
     override def toString = s"RefinedThis(${binder.hashCode})"
   }
 
+  /** a self-reference to an enclosing recursive type. */
+  case class RecThis(binder: RecType) extends BoundType with SingletonType {
+    type BT = RecType
+    override def underlying(implicit ctx: Context) = binder
+    def copyBoundType(bt: BT) = RecThis(bt)
+
+    // need to customize hashCode and equals to prevent infinite recursion
+    // between RecTypes and RecRefs.
+    override def computeHash = addDelta(binder.identityHash, 41)
+    override def equals(that: Any) = that match {
+      case that: RecThis => this.binder eq that.binder
+      case _ => false
+    }
+    override def toString = s"RecThis(${binder.hashCode})"
+  }
+
   // ----- Skolem types -----------------------------------------------
 
   /** A skolem type reference with underlying type `binder`. */
@@ -2691,7 +2795,7 @@ object Types {
       }
       def isOrType(tp: Type): Boolean = tp.stripTypeVar.dealias match {
         case tp: OrType => true
-        case tp: RefinedType => isOrType(tp.parent)
+        case tp: RefinedOrRecType => isOrType(tp.parent)
         case AndType(tp1, tp2) => isOrType(tp1) | isOrType(tp2)
         case WildcardType(bounds: TypeBounds) => isOrType(bounds.hi)
         case _ => false
@@ -3160,6 +3264,8 @@ object Types {
       tp.derivedSelect(pre)
     protected def derivedRefinedType(tp: RefinedType, parent: Type, info: Type): Type =
       tp.derivedRefinedType(parent, tp.refinedName, info)
+    protected def derivedRecType(tp: RecType, parent: Type): Type =
+      tp.rebind(parent)
     protected def derivedTypeAlias(tp: TypeAlias, alias: Type): Type =
       tp.derivedTypeAlias(alias)
     protected def derivedTypeBounds(tp: TypeBounds, lo: Type, hi: Type): Type =
@@ -3234,6 +3340,9 @@ object Types {
           }
           mapOverPoly
 
+        case tp: RecType =>
+          derivedRecType(tp, this(tp.parent))
+
         case tp @ SuperType(thistp, supertp) =>
           derivedSuperType(tp, this(thistp), this(supertp))
 
@@ -3335,6 +3444,9 @@ object Types {
     override protected def derivedRefinedType(tp: RefinedType, parent: Type, info: Type) =
       if (parent.exists && info.exists) tp.derivedRefinedType(parent, tp.refinedName, info)
       else approx(hi = parent)
+    override protected def derivedRecType(tp: RecType, parent: Type) =
+      if (parent.exists) tp.rebind(parent)
+      else approx()
     override protected def derivedTypeAlias(tp: TypeAlias, alias: Type) =
       if (alias.exists) tp.derivedTypeAlias(alias)
       else approx(NoType, TypeBounds.empty)
@@ -3433,6 +3545,9 @@ object Types {
         variance = -variance
         this(y, tp.resultType)
 
+      case tp: RecType =>
+        this(x, tp.parent)
+
       case SuperType(thistp, supertp) =>
         this(this(x, thistp), supertp)
 
diff --git a/src/dotty/tools/dotc/core/tasty/TastyFormat.scala b/src/dotty/tools/dotc/core/tasty/TastyFormat.scala
index a42958e75..e9708961a 100644
--- a/src/dotty/tools/dotc/core/tasty/TastyFormat.scala
+++ b/src/dotty/tools/dotc/core/tasty/TastyFormat.scala
@@ -103,7 +103,7 @@ Standard-Section: "ASTs" TopLevelStat*
                   TERMREFpkg            fullyQualified_NameRef
                   TERMREF               possiblySigned_NameRef qual_Type
                   THIS                  clsRef_Type
-                  REFINEDthis           refinedType_ASTRef
+                  RECthis               recType_ASTRef
                   SHARED                path_ASTRef
 
   Constant      = UNITconst
@@ -126,6 +126,7 @@ Standard-Section: "ASTs" TopLevelStat*
                   TYPEREFsymbol         sym_ASTRef qual_Type
                   TYPEREFpkg            fullyQualified_NameRef
                   TYPEREF               possiblySigned_NameRef qual_Type
+                  RECtype               parent_Type
                   SUPERtype      Length this_Type underlying_Type
                   REFINEDtype    Length underlying_Type refinement_NameRef info_Type
                   APPLIEDtype    Length tycon_Type arg_Type*
@@ -259,6 +260,7 @@ object TastyFormat {
   final val TERMREFpkg = 67
   final val TYPEREFpkg = 68
   final val REFINEDthis = 69
+  final val RECthis = REFINEDthis // !!!
   final val BYTEconst = 70
   final val SHORTconst = 71
   final val CHARconst = 72
@@ -277,6 +279,7 @@ object TastyFormat {
   final val IMPLICITarg = 101
   final val PRIVATEqualified = 102
   final val PROTECTEDqualified = 103
+  final val RECtype = 104
 
   final val IDENT = 112
   final val SELECT = 113
@@ -417,7 +420,7 @@ object TastyFormat {
     case TYPEREFdirect => "TYPEREFdirect"
     case TERMREFpkg => "TERMREFpkg"
     case TYPEREFpkg => "TYPEREFpkg"
-    case REFINEDthis => "REFINEDthis"
+    case RECthis => "RECthis"
     case BYTEconst => "BYTEconst"
     case SHORTconst => "SHORTconst"
     case CHARconst => "CHARconst"
@@ -426,6 +429,7 @@ object TastyFormat {
     case FLOATconst => "FLOATconst"
     case DOUBLEconst => "DOUBLEconst"
     case STRINGconst => "STRINGconst"
+    case RECtype => "RECtype"
 
     case IDENT => "IDENT"
     case SELECT => "SELECT"
diff --git a/src/dotty/tools/dotc/core/tasty/TreePickler.scala b/src/dotty/tools/dotc/core/tasty/TreePickler.scala
index 0cc08f2d9..9f703b5af 100644
--- a/src/dotty/tools/dotc/core/tasty/TreePickler.scala
+++ b/src/dotty/tools/dotc/core/tasty/TreePickler.scala
@@ -212,6 +212,11 @@ class TreePickler(pickler: TastyPickler) {
       val binderAddr = pickledTypes.get(tpe.binder)
       assert(binderAddr != null, tpe.binder)
       writeRef(binderAddr.asInstanceOf[Addr])
+    case tpe: RecThis =>
+      writeByte(RECthis)
+      val binderAddr = pickledTypes.get(tpe.binder)
+      assert(binderAddr != null, tpe.binder)
+      writeRef(binderAddr.asInstanceOf[Addr])
     case tpe: SkolemType =>
       pickleType(tpe.info)
     case tpe: RefinedType =>
@@ -221,6 +226,9 @@ class TreePickler(pickler: TastyPickler) {
         pickleType(tpe.parent)
         pickleType(tpe.refinedInfo, richTypes = true)
       }
+    case tpe: RecType =>
+      writeByte(RECtype)
+      pickleType(tpe.parent)
     case tpe: TypeAlias =>
       writeByte(TYPEALIAS)
       withLength {
diff --git a/src/dotty/tools/dotc/core/tasty/TreeUnpickler.scala b/src/dotty/tools/dotc/core/tasty/TreeUnpickler.scala
index 2b8e5f019..1b4e7845a 100644
--- a/src/dotty/tools/dotc/core/tasty/TreeUnpickler.scala
+++ b/src/dotty/tools/dotc/core/tasty/TreeUnpickler.scala
@@ -335,8 +335,13 @@ class TreeUnpickler(reader: TastyReader, tastyName: TastyName.Table) {
           }
         case THIS =>
           ThisType.raw(readType().asInstanceOf[TypeRef])
+        case RECtype =>
+          RecType(rt => registeringType(rt, readType()))
         case REFINEDthis =>
-          RefinedThis(readTypeRef().asInstanceOf[RefinedType])
+          readTypeRef() match {
+            case t: RefinedType => RefinedThis(t)
+            case t: RecType => RecThis(t)
+          }
         case SHARED =>
           val ref = readAddr()
           typeAtAddr.getOrElseUpdate(ref, forkAt(ref).readType())
diff --git a/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala b/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala
index 687e9279b..2663777af 100644
--- a/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala
+++ b/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala
@@ -722,13 +722,12 @@ class Scala2Unpickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClas
         val parent = parents.reduceLeft(AndType(_, _))
         if (decls.isEmpty) parent
         else {
-          def addRefinement(tp: Type, sym: Symbol) = {
-            def subst(info: Type, rt: RefinedType) =
-              if (clazz.isClass) info.substThis(clazz.asClass, RefinedThis(rt))
-              else info // turns out some symbols read into `clazz` are not classes, not sure why this is the case.
-            RefinedType(tp, sym.name, subst(sym.info, _))
-          }
-          (parent /: decls.toList)(addRefinement).asInstanceOf[RefinedType]
+          def subst(info: Type, rt: RecType) =
+            if (clazz.isClass) info.substThis(clazz.asClass, RecThis(rt))
+            else info // turns out some symbols read into `clazz` are not classes, not sure why this is the case.
+          def addRefinement(tp: Type, sym: Symbol) = RefinedType(tp, sym.name, sym.info)
+          val refined = (parent /: decls.toList)(addRefinement)
+          RecType.closeOver(rt => subst(refined, rt))
         }
       case CLASSINFOtpe =>
         val clazz = readSymbolRef()
diff --git a/src/dotty/tools/dotc/printing/PlainPrinter.scala b/src/dotty/tools/dotc/printing/PlainPrinter.scala
index 7053a0ea3..59f1608db 100644
--- a/src/dotty/tools/dotc/printing/PlainPrinter.scala
+++ b/src/dotty/tools/dotc/printing/PlainPrinter.scala
@@ -13,6 +13,8 @@ import scala.annotation.switch
 class PlainPrinter(_ctx: Context) extends Printer {
   protected[this] implicit def ctx: Context = _ctx.addMode(Mode.Printing)
 
+  private var openRecs: List[RecType] = Nil
+
   protected def maxToTextRecursions = 100
 
   protected final def controlled(op: => Text): Text =
@@ -58,6 +60,8 @@ class PlainPrinter(_ctx: Context) extends Printer {
       }
     else tp
 
+  private def selfRecName(n: Int) = s"z$n"
+
   /** Render elements alternating with `sep` string */
   protected def toText(elems: Traversable[Showable], sep: String) =
     Text(elems map (_ toText this), sep)
@@ -130,6 +134,12 @@ class PlainPrinter(_ctx: Context) extends Printer {
         val parent :: (refined: List[RefinedType @unchecked]) =
           refinementChain(tp).reverse
         toTextLocal(parent) ~ "{" ~ Text(refined map toTextRefinement, "; ").close ~ "}"
+      case tp: RecType =>
+        try {
+          openRecs = tp :: openRecs
+          "{" ~ selfRecName(openRecs.length) ~ " => " ~ toTextGlobal(tp.parent) ~ "}"
+        }
+        finally openRecs = openRecs.tail
       case AndType(tp1, tp2) =>
         changePrec(AndPrec) { toText(tp1) ~ " & " ~ toText(tp2) }
       case OrType(tp1, tp2) =>
@@ -232,6 +242,10 @@ class PlainPrinter(_ctx: Context) extends Printer {
         toText(value)
       case MethodParam(mt, idx) =>
         nameString(mt.paramNames(idx))
+      case tp: RecThis =>
+        val idx = openRecs.reverse.indexOf(tp.binder)
+        if (idx >= 0) selfRecName(idx + 1)
+        else "{...}.this" // TODO move underlying type to an addendum, e.g. ... z3 ... where z3: ...
       case tp: RefinedThis =>
         s"${nameString(tp.binder.typeSymbol)}{...}.this"
       case tp: SkolemType =>
diff --git a/src/dotty/tools/dotc/typer/Checking.scala b/src/dotty/tools/dotc/typer/Checking.scala
index 37753fe65..6944197a1 100644
--- a/src/dotty/tools/dotc/typer/Checking.scala
+++ b/src/dotty/tools/dotc/typer/Checking.scala
@@ -174,6 +174,8 @@ object Checking {
         mapOver(tp)
       case tp @ RefinedType(parent, name, rinfo) =>
         tp.derivedRefinedType(this(parent), name, this(rinfo, nestedCycleOK, nestedCycleOK))
+      case tp: RecType =>
+        tp.rebind(this(tp.parent))
       case tp @ TypeRef(pre, name) =>
         try {
           // A prefix is interesting if it might contain (transitively) a reference
@@ -187,7 +189,7 @@ object Checking {
             case SuperType(thistp, _) => isInteresting(thistp)
             case AndType(tp1, tp2) => isInteresting(tp1) || isInteresting(tp2)
             case OrType(tp1, tp2) => isInteresting(tp1) && isInteresting(tp2)
-            case _: RefinedType => true
+            case _: RefinedOrRecType => true
             case _ => false
           }
           if (isInteresting(pre)) {
@@ -433,12 +435,14 @@ trait Checking {
   }
 
   /** Check that any top-level type arguments in this type are feasible, i.e. that
-   *  their lower bound conforms to their upper cound. If a type argument is
+   *  their lower bound conforms to their upper bound. If a type argument is
    *  infeasible, issue and error and continue with upper bound.
    */
   def checkFeasible(tp: Type, pos: Position, where: => String = "")(implicit ctx: Context): Type = tp match {
     case tp: RefinedType =>
       tp.derivedRefinedType(tp.parent, tp.refinedName, checkFeasible(tp.refinedInfo, pos, where))
+    case tp: RecType =>
+      tp.rebind(tp.parent)
     case tp @ TypeBounds(lo, hi) if !(lo <:< hi) =>
       ctx.error(d"no type exists between low bound $lo and high bound $hi$where", pos)
       TypeAlias(hi)
diff --git a/src/dotty/tools/dotc/typer/TypeAssigner.scala b/src/dotty/tools/dotc/typer/TypeAssigner.scala
index b686e6eed..47c3631b8 100644
--- a/src/dotty/tools/dotc/typer/TypeAssigner.scala
+++ b/src/dotty/tools/dotc/typer/TypeAssigner.scala
@@ -430,8 +430,8 @@ trait TypeAssigner {
     val argBindingFns = tparams.map(tparam =>
       tparam.info.bounds
         .withBindingKind(BindingKind.fromVariance(tparam.variance))
-        .internalizeFrom(tparams))
-    val bodyFn = body.tpe.internalizeFrom(tparams)
+        .recursify(tparams))
+    val bodyFn = body.tpe.recursify(tparams)
     tree.withType(TypeApplicationsNewHK.TypeLambda(argBindingFns, bodyFn))
   }
 
diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala
index d5a32dbc0..fb3418563 100644
--- a/src/dotty/tools/dotc/typer/Typer.scala
+++ b/src/dotty/tools/dotc/typer/Typer.scala
@@ -917,11 +917,12 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
       if ((rsym.is(Method) || rsym.isType) && rsym.allOverriddenSymbols.isEmpty)
         ctx.error(i"refinement $rsym without matching type in parent $parent", refinement.pos)
       val rinfo = if (rsym is Accessor) rsym.info.resultType else rsym.info
-      RefinedType(parent, rsym.name, rt => rinfo.substThis(refineCls, RefinedThis(rt)))
+      RefinedType(parent, rsym.name, rinfo)
       // todo later: check that refinement is within bounds
     }
-    val res = cpy.RefinedTypeTree(tree)(tpt1, refinements1) withType
-      (tpt1.tpe /: refinements1)(addRefinement)
+    val refined = (tpt1.tpe /: refinements1)(addRefinement)
+    val res = cpy.RefinedTypeTree(tree)(tpt1, refinements1).withType(
+      RecType.closeOver(rt => refined.substThis(refineCls, RecThis(rt))))
     typr.println(i"typed refinement: ${res.tpe}")
     res
   }
diff --git a/src/dotty/tools/dotc/typer/Variances.scala b/src/dotty/tools/dotc/typer/Variances.scala
index bc9730140..e88423f98 100644
--- a/src/dotty/tools/dotc/typer/Variances.scala
+++ b/src/dotty/tools/dotc/typer/Variances.scala
@@ -77,6 +77,8 @@ object Variances {
       else flip(varianceInType(lo)(tparam)) & varianceInType(hi)(tparam)
     case tp @ RefinedType(parent, _, rinfo) =>
       varianceInType(parent)(tparam) & varianceInType(rinfo)(tparam)
+    case tp: RecType =>
+      varianceInType(tp.parent)(tparam)
     case tp @ MethodType(_, paramTypes) =>
       flip(varianceInTypes(paramTypes)(tparam)) & varianceInType(tp.resultType)(tparam)
     case ExprType(restpe) =>