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]

7 files changed, 125 insertions, 7 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 =>
diff --git a/test/dotc/tests.scala b/test/dotc/tests.scala
index f98b8114c..4361ccc13 100644
--- a/test/dotc/tests.scala
+++ b/test/dotc/tests.scala
@@ -29,7 +29,6 @@ class tests extends CompilerTest {
     else List("-Ycheck:tailrec,resolveSuper,mixin,restoreScopes,labelDef")
   }
 
-
   val testPickling = List("-Xprint-types", "-Ytest-pickler", "-Ystop-after:pickler")
 
   val twice = List("#runs", "2")
diff --git a/tests/neg/existentials.scala b/tests/neg/existentials.scala
new file mode 100644
index 000000000..4798504d9
--- /dev/null
+++ b/tests/neg/existentials.scala
@@ -0,0 +1,61 @@
+object TestList {
+
+  var x: ([X] -> List[List[X]])[_] = List(List(1)) // error: unreducible
+  var y: ([X] -> List[Seq[X]])[_] = List(List(1)) // error: unreducible
+
+  x = x
+  y = y
+  y = x
+
+  val h = x.head
+  val x1: List[_] = h
+
+  var z: List[_] = x
+
+}
+object TestSet {
+
+  var x: ([Y] -> Set[Set[Y]])[_] = Set(Set("a")) // error: unreducible
+  var y: ([Y] -> Set[Iterable[Y]])[_] = Set(Set("a")) // error: unreducible
+
+  x = x
+  y = y
+
+  val h = x.head
+  val h1: Set[_] = h
+
+  // val p = x.+ // infinite loop in implicit search
+
+  var z: Set[_] = x
+
+}
+class TestX {
+
+  class C[T](x: T) {
+    def get: T = x
+    def cmp: T => Boolean = (x == _)
+  }
+
+  val x: ([Y] -> C[C[Y]])[_] = new C(new C("a")) // error: unreducible
+
+  type CC[X] = C[C[X]]
+  val y: CC[_] = ??? // error: unreducible
+
+  type D[X] <: C[X]
+
+  type DD = [X] -> D[D[X]]
+  val z: DD[_] = ??? // error: unreducible
+
+  val g = x.get
+
+  val c = x.cmp
+}
+
+object Test6014 {
+  case class CC[T](key: T)
+  type Alias[T] = Seq[CC[T]]
+
+  def f(xs: Seq[CC[_]]) = xs map { case CC(x) => CC(x) }    // ok
+  def g(xs: Alias[_])   = xs map { case CC(x) => CC(x) }    // error: unreducible application
+}
+
diff --git a/tests/pos/GenTraversableFactory.scala b/tests/pos-scala2/GenTraversableFactory.scala
index 2f93ab27b..2f93ab27b 100644
--- a/tests/pos/GenTraversableFactory.scala
+++ b/tests/pos-scala2/GenTraversableFactory.scala
diff --git a/tests/pos/t6014.scala b/tests/pos-scala2/t6014.scala
index 26e258a27..02535f377 100644
--- a/tests/pos/t6014.scala
+++ b/tests/pos-scala2/t6014.scala
@@ -3,7 +3,7 @@ object Test {
   type Alias[T] = Seq[CC[T]]
 
   def f(xs: Seq[CC[_]]) = xs map { case CC(x) => CC(x) }    // ok
-  def g(xs: Alias[_])   = xs map { case CC(x) => CC(x) }    // fails
+  def g(xs: Alias[_])   = xs map { case CC(x) => CC(x) }    // migration warning: unreducible application
   // ./a.scala:11: error: missing parameter type for expanded function
   // The argument types of an anonymous function must be fully known. (SLS 8.5)
   // Expected type was: ?