New type lambda scheme for hk types

7 files changed, 85 insertions, 3 deletions

diff --git a/src/dotty/tools/dotc/ast/Trees.scala b/src/dotty/tools/dotc/ast/Trees.scala
index 7463449c5..20ae02994 100644
--- a/src/dotty/tools/dotc/ast/Trees.scala
+++ b/src/dotty/tools/dotc/ast/Trees.scala
@@ -594,6 +594,12 @@ object Trees {
     def forwardTo = tpt
   }
 
+  /** [typeparams] -> tpt */
+  case class TypeLambdaTree[-T >: Untyped] private[ast] (tparams: List[TypeDef[T]], body: Tree[T])
+    extends TypTree[T] {
+    type ThisTree[-T >: Untyped] = TypeLambdaTree[T]
+  }
+
   /** => T */
   case class ByNameTypeTree[-T >: Untyped] private[ast] (result: Tree[T])
   extends TypTree[T] {
@@ -851,6 +857,7 @@ object Trees {
     type OrTypeTree = Trees.OrTypeTree[T]
     type RefinedTypeTree = Trees.RefinedTypeTree[T]
     type AppliedTypeTree = Trees.AppliedTypeTree[T]
+    type TypeLambdaTree = Trees.TypeLambdaTree[T]
     type ByNameTypeTree = Trees.ByNameTypeTree[T]
     type TypeBoundsTree = Trees.TypeBoundsTree[T]
     type Bind = Trees.Bind[T]
@@ -1028,6 +1035,10 @@ object Trees {
         case tree: AppliedTypeTree if (tpt eq tree.tpt) && (args eq tree.args) => tree
         case _ => finalize(tree, untpd.AppliedTypeTree(tpt, args))
       }
+      def TypeLambdaTree(tree: Tree)(tparams: List[TypeDef], body: Tree): TypeLambdaTree = tree match {
+        case tree: TypeLambdaTree if (tparams eq tree.tparams) && (body eq tree.body) => tree
+        case _ => finalize(tree, untpd.TypeLambdaTree(tparams, body))
+      }
       def ByNameTypeTree(tree: Tree)(result: Tree): ByNameTypeTree = tree match {
         case tree: ByNameTypeTree if result eq tree.result => tree
         case _ => finalize(tree, untpd.ByNameTypeTree(result))
@@ -1160,6 +1171,8 @@ object Trees {
           cpy.RefinedTypeTree(tree)(transform(tpt), transformSub(refinements))
         case AppliedTypeTree(tpt, args) =>
           cpy.AppliedTypeTree(tree)(transform(tpt), transform(args))
+        case TypeLambdaTree(tparams, body) =>
+          cpy.TypeLambdaTree(tree)(transformSub(tparams), transform(body))
         case ByNameTypeTree(result) =>
           cpy.ByNameTypeTree(tree)(transform(result))
         case TypeBoundsTree(lo, hi) =>
@@ -1264,6 +1277,9 @@ object Trees {
             this(this(x, tpt), refinements)
           case AppliedTypeTree(tpt, args) =>
             this(this(x, tpt), args)
+          case TypeLambdaTree(tparams, body) =>
+            implicit val ctx: Context = localCtx
+            this(this(x, tparams), body)
           case ByNameTypeTree(result) =>
             this(x, result)
           case TypeBoundsTree(lo, hi) =>
diff --git a/src/dotty/tools/dotc/ast/untpd.scala b/src/dotty/tools/dotc/ast/untpd.scala
index c7a7036c3..b3f8747dc 100644
--- a/src/dotty/tools/dotc/ast/untpd.scala
+++ b/src/dotty/tools/dotc/ast/untpd.scala
@@ -137,6 +137,7 @@ object untpd extends Trees.Instance[Untyped] with UntypedTreeInfo {
   def OrTypeTree(left: Tree, right: Tree): OrTypeTree = new OrTypeTree(left, right)
   def RefinedTypeTree(tpt: Tree, refinements: List[Tree]): RefinedTypeTree = new RefinedTypeTree(tpt, refinements)
   def AppliedTypeTree(tpt: Tree, args: List[Tree]): AppliedTypeTree = new AppliedTypeTree(tpt, args)
+  def TypeLambdaTree(tparams: List[TypeDef], body: Tree): TypeLambdaTree = new TypeLambdaTree(tparams, body)
   def ByNameTypeTree(result: Tree): ByNameTypeTree = new ByNameTypeTree(result)
   def TypeBoundsTree(lo: Tree, hi: Tree): TypeBoundsTree = new TypeBoundsTree(lo, hi)
   def Bind(name: Name, body: Tree): Bind = new Bind(name, body)
diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala
index 3cc3091b5..be8a367d7 100644
--- a/src/dotty/tools/dotc/config/Config.scala
+++ b/src/dotty/tools/dotc/config/Config.scala
@@ -8,6 +8,8 @@ object Config {
   final val cacheMemberNames = true
   final val cacheImplicitScopes = true
 
+  final val newHK = false
+
   final val checkCacheMembersNamed = false
 
   /** When updating a constraint bound, check that the constrained parameter
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index 8ab5fbf02..2411e0bb2 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -15,8 +15,35 @@ import StdNames.tpnme
 import util.Positions.Position
 import config.Printers._
 import collection.mutable
+   import dotty.tools.dotc.config.Config
 import java.util.NoSuchElementException
 
+object TypeApplicationsNewHK {
+  import TypeApplications._
+
+  object TypeLambda {
+    def apply(argBindingFns: List[RefinedType => TypeBounds],
+              bodyFn: RefinedType => Type)(implicit ctx: Context): Type = {
+      val argNames = argBindingFns.indices.toList.map(tpnme.hkArg)
+      RefinedType.recursive(bodyFn, argNames, argBindingFns)
+    }
+
+    def unapply(tp: Type)(implicit ctx: Context): Option[(List[TypeBounds], Type)] = {
+      def decompose(t: Type, acc: List[TypeBounds]): (List[TypeBounds], Type) = t match {
+        case t @ RefinedType(p, rname, rinfo: TypeBounds)
+        if rname.isHkArgName && rinfo.isBinding =>
+          decompose(p, rinfo.bounds :: acc)
+        case _ =>
+          (acc, t)
+      }
+      decompose(tp, Nil) match {
+        case (Nil, _) => None
+        case x => Some(x)
+      }
+    }
+  }
+}
+
 object TypeApplications {
 
   /** Assert type is not a TypeBounds instance and return it unchanged */
@@ -51,6 +78,14 @@ 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 {
     def apply(variances: List[Int],
@@ -388,9 +423,9 @@ class TypeApplications(val self: Type) extends AnyVal {
   /** Replace references to type parameters with references to hk arguments `this.$hk_i`
    * Care is needed not to cause cyclic reference errors, hence `SafeSubstMap`.
    */
-  private[TypeApplications] def internalizeFrom[T <: Type](tparams: List[Symbol])(implicit ctx: Context): RefinedType => T =
+  def internalizeFrom[T <: Type](tparams: List[Symbol])(implicit ctx: Context): RefinedType => T =
     (rt: RefinedType) =>
-      new ctx.SafeSubstMap(tparams , argRefs(rt, tparams.length))
+      new ctx.SafeSubstMap(tparams, argRefs(rt, tparams.length))
         .apply(self).asInstanceOf[T]
 
   /** Lambda abstract `self` with given type parameters. Examples:
diff --git a/src/dotty/tools/dotc/parsing/Parsers.scala b/src/dotty/tools/dotc/parsing/Parsers.scala
index ded17c67c..0cc392bad 100644
--- a/src/dotty/tools/dotc/parsing/Parsers.scala
+++ b/src/dotty/tools/dotc/parsing/Parsers.scala
@@ -223,7 +223,9 @@ object Parsers {
       } // DEBUG
 
     private def expectedMsg(token: Int): String =
-      showToken(token) + " expected but " + showToken(in.token) + " found."
+      expectedMessage(showToken(token))
+    private def expectedMessage(what: String): String =
+      s"$what expected but ${showToken(in.token)} found"
 
     /** Consume one token of the specified type, or
       * signal an error if it is not there.
@@ -648,6 +650,7 @@ object Parsers {
 /* ------------- TYPES ------------------------------------------------------ */
 
     /** Type        ::= FunArgTypes `=>' Type
+     *                |  HkTypeParamClause `->' Type
      *                | InfixType
      *  FunArgTypes ::=  InfixType
      *                | `(' [ FunArgType {`,' FunArgType } ] `)'
@@ -677,6 +680,12 @@ object Parsers {
             }
           }
         }
+        else if (in.token == LBRACKET) {
+          val tparams = typeParamClause(ParamOwner.TypeParam)
+          if (isIdent && in.name.toString == "->")
+            atPos(in.skipToken())(TypeLambdaTree(tparams, typ()))
+          else { syntaxErrorOrIncomplete(expectedMessage("`->'")); typ() }
+        }
         else infixType()
 
       in.token match {
diff --git a/src/dotty/tools/dotc/typer/TypeAssigner.scala b/src/dotty/tools/dotc/typer/TypeAssigner.scala
index f439c4c99..b686e6eed 100644
--- a/src/dotty/tools/dotc/typer/TypeAssigner.scala
+++ b/src/dotty/tools/dotc/typer/TypeAssigner.scala
@@ -425,6 +425,16 @@ trait TypeAssigner {
     tree.withType(ownType)
   }
 
+  def assignType(tree: untpd.TypeLambdaTree, tparamDefs: List[TypeDef], body: Tree)(implicit ctx: Context) = {
+    val tparams = tparamDefs.map(_.symbol)
+    val argBindingFns = tparams.map(tparam =>
+      tparam.info.bounds
+        .withBindingKind(BindingKind.fromVariance(tparam.variance))
+        .internalizeFrom(tparams))
+    val bodyFn = body.tpe.internalizeFrom(tparams)
+    tree.withType(TypeApplicationsNewHK.TypeLambda(argBindingFns, bodyFn))
+  }
+
   def assignType(tree: untpd.ByNameTypeTree, result: Tree)(implicit ctx: Context) =
     tree.withType(ExprType(result.tpe))
 
diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala
index 268020ec5..d5a32dbc0 100644
--- a/src/dotty/tools/dotc/typer/Typer.scala
+++ b/src/dotty/tools/dotc/typer/Typer.scala
@@ -958,6 +958,14 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
     }
   }
 
+  def typedTypeLambdaTree(tree: untpd.TypeLambdaTree)(implicit ctx: Context): Tree = track("typedTypeLambdaTree") {
+    val TypeLambdaTree(tparams, body) = tree
+    index(tparams)
+    val tparams1 = tparams.mapconserve(typed(_).asInstanceOf[TypeDef])
+    val body1 = typedType(tree.body)
+    assignType(cpy.TypeLambdaTree(tree)(tparams1, body1), tparams1, body1)
+  }
+
   def typedByNameTypeTree(tree: untpd.ByNameTypeTree)(implicit ctx: Context): ByNameTypeTree = track("typedByNameTypeTree") {
     val result1 = typed(tree.result)
     assignType(cpy.ByNameTypeTree(tree)(result1), result1)
@@ -1272,6 +1280,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit
           case tree: untpd.OrTypeTree => typedOrTypeTree(tree)
           case tree: untpd.RefinedTypeTree => typedRefinedTypeTree(tree)
           case tree: untpd.AppliedTypeTree => typedAppliedTypeTree(tree)
+          case tree: untpd.TypeLambdaTree => typedTypeLambdaTree(tree)(localContext(tree, NoSymbol).setNewScope)
           case tree: untpd.ByNameTypeTree => typedByNameTypeTree(tree)
           case tree: untpd.TypeBoundsTree => typedTypeBoundsTree(tree)
           case tree: untpd.Alternative => typedAlternative(tree, pt)