Disallow higher-kinded types that simulate general existential types

We cannot handle such types in general. So we now check that a hk application

   C[args]

where some of the arguments are wildcards does not have as a supertype
a hk application

   ([X] -> B)[args]

3 files changed, 63 insertions, 5 deletions

diff --git a/src/dotty/tools/dotc/core/Mode.scala b/src/dotty/tools/dotc/core/Mode.scala
index 0e188ace2..3e9b7effe 100644
--- a/src/dotty/tools/dotc/core/Mode.scala
+++ b/src/dotty/tools/dotc/core/Mode.scala
@@ -84,5 +84,10 @@ object Mode {
   /** Use Scala2 scheme for overloading and implicit resolution */
   val OldOverloadingResolution = newMode(14, "OldOverloadingResolution")
 
+  /** Allow hk applications of type lambdas to wildcard arguments;
+   *  used for checking that such applications do not normally arise
+   */
+  val AllowLambdaWildcardApply = newMode(15, "AllowHKApplyToWildcards")
+
   val PatternOrType = Pattern | Type
 }
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index 580cd6569..be0c08d15 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -129,8 +129,10 @@ object TypeApplications {
   /** A type map that tries to reduce a (part of) the result type of the type lambda `tycon`
    *  with the given `args`(some of which are wildcard arguments represented by type bounds).
    *  Non-wildcard arguments are substituted everywhere as usual. A wildcard argument
-   *  `>: L <: H` is substituted for a type lambda parameter `X` only if `X` appears
-   *  in a toplevel refinement of the form
+   *  `>: L <: H` is substituted for a type lambda parameter `X` only under certain conditions.
+   *
+   *  1. If Mode.AllowLambdaWildcardApply is set:
+   *  The wildcard argument is substituted only if `X` appears in a toplevel refinement of the form
    *
    *        { type A = X }
    *
@@ -141,19 +143,48 @@ object TypeApplications {
    *
    *  The `allReplaced` field indicates whether all occurrences of type lambda parameters
    *  in the reduced type have been replaced with arguments.
+   *
+   *  2. If Mode.AllowLambdaWildcardApply is not set:
+   *  All refinements of the form
+   *
+   *        { type A = X }
+   *
+   *  are replaced by:
+   *
+   *        { type A >: L <: U }
+   *
+   *  Any other occurrence of `X` in `tycon` is replaced by `U`, if the
+   *  occurrence of `X` in `tycon` is covariant, or nonvariant, or by `L`,
+   *  if the occurrence is contravariant.
+   *
+   *  The idea is that the `AllowLambdaWildcardApply` mode is used to check whether
+   *  a type can be soundly reduced, and to give an error or warning if that
+   *  is not the case. By contrast, the default mode, with `AllowLambdaWildcardApply`
+   *  not set, reduces all applications even if this yields a different type, so
+   *  its postcondition is that no type parameters of `tycon` appear in the
+   *  result type. Using this mode, we can guarantee that `appliedTo` will never
+   *  produce a higher-kinded application with a type lambda as type constructor.
    */
   class Reducer(tycon: TypeLambda, args: List[Type])(implicit ctx: Context) extends TypeMap {
     private var available = Set((0 until args.length): _*)
     var allReplaced = true
     def hasWildcardArg(p: PolyParam) =
       p.binder == tycon && args(p.paramNum).isInstanceOf[TypeBounds]
+    def canReduceWildcard(p: PolyParam) =
+      !ctx.mode.is(Mode.AllowLambdaWildcardApply) || available.contains(p.paramNum)
     def apply(t: Type) = t match {
-      case t @ TypeAlias(p: PolyParam) if hasWildcardArg(p) && available.contains(p.paramNum) =>
+      case t @ TypeAlias(p: PolyParam) if hasWildcardArg(p) && canReduceWildcard(p) =>
         available -= p.paramNum
         args(p.paramNum)
       case p: PolyParam if p.binder == tycon =>
-        if (hasWildcardArg(p)) { allReplaced = false; p }
-        else args(p.paramNum)
+        args(p.paramNum) match {
+          case TypeBounds(lo, hi) =>
+            if (ctx.mode.is(Mode.AllowLambdaWildcardApply)) { allReplaced = false; p }
+            else if (variance < 0) lo
+            else hi
+          case arg =>
+            arg
+        }
       case _: TypeBounds | _: HKApply =>
         val saved = available
         available = Set()
diff --git a/src/dotty/tools/dotc/typer/Checking.scala b/src/dotty/tools/dotc/typer/Checking.scala
index 3aa63aeeb..aa13bdc3d 100644
--- a/src/dotty/tools/dotc/typer/Checking.scala
+++ b/src/dotty/tools/dotc/typer/Checking.scala
@@ -55,6 +55,24 @@ object Checking {
   def checkBounds(args: List[tpd.Tree], poly: GenericType)(implicit ctx: Context): Unit =
     checkBounds(args, poly.paramBounds, _.substParams(poly, _))
 
+  /** If type is a higher-kinded application with wildcard arguments,
+   *  check that it or one of its supertypes can be reduced to a normal application.
+   *  Unreducible applications correspond to general existentials, and we
+   *  cannot handle those.
+   */
+  def checkWildcardHKApply(tp: Type, pos: Position)(implicit ctx: Context): Unit = tp match {
+    case tp @ HKApply(tycon, args) if args.exists(_.isInstanceOf[TypeBounds]) =>
+      tycon match {
+        case tycon: TypeLambda =>
+          ctx.errorOrMigrationWarning(
+            d"unreducible application of higher-kinded type $tycon to wildcard arguments",
+            pos)
+        case _ =>
+          checkWildcardHKApply(tp.superType, pos)
+      }
+    case _ =>
+  }
+
   /** Traverse type tree, performing the following checks:
    *  1. All arguments of applied type trees must conform to their bounds.
    *  2. Prefixes of type selections and singleton types must be realizable.
@@ -74,6 +92,10 @@ object Checking {
           val bounds = tparams.map(tparam =>
             tparam.info.asSeenFrom(tycon.tpe.normalizedPrefix, tparam.owner.owner).bounds)
           checkBounds(args, bounds, _.substDealias(tparams, _))
+
+          def checkValidIfHKApply(implicit ctx: Context): Unit =
+            checkWildcardHKApply(tycon.tpe.appliedTo(args.map(_.tpe)), tree.pos)
+          checkValidIfHKApply(ctx.addMode(Mode.AllowLambdaWildcardApply))
         case Select(qual, name) if name.isTypeName =>
           checkRealizable(qual.tpe, qual.pos)
         case SelectFromTypeTree(qual, name) if name.isTypeName =>