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.

1 files changed, 32 insertions, 8 deletions

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 =>