Fix SI-2712

Allows partially instantiated types as type constrictors when inferring higher-kinded
types.

6 files changed, 84 insertions, 18 deletions

diff --git a/src/dotty/tools/dotc/core/ConstraintHandling.scala b/src/dotty/tools/dotc/core/ConstraintHandling.scala
index d21f62440..1c3bd7384 100644
--- a/src/dotty/tools/dotc/core/ConstraintHandling.scala
+++ b/src/dotty/tools/dotc/core/ConstraintHandling.scala
@@ -35,6 +35,11 @@ trait ConstraintHandling {
   /** If the constraint is frozen we cannot add new bounds to the constraint. */
   protected var frozenConstraint = false
 
+  /** We are currently comparing lambdas. Used as a flag for
+   *  optimization: when `false`, no need to do an expensive `pruneLambdaParams`
+   */
+  protected var comparingLambdas = false
+
   private def addOneBound(param: PolyParam, bound: Type, isUpper: Boolean): Boolean =
     !constraint.contains(param) || {
       def occursIn(bound: Type): Boolean = {
@@ -289,6 +294,34 @@ trait ConstraintHandling {
     checkPropagated(s"added $description") {
       addConstraintInvocations += 1
 
+      /** When comparing lambdas we might get constraints such as
+       *  `A <: X0` or `A = List[X0]` where `A` is a constrained parameter
+       *  and `X0` is a lambda parameter. The constraint for `A` is not allowed
+       *  to refer to such a lambda parameter because the lambda parameter is
+       *  not visible where `A` is defined. Consequently, we need to
+       *  approximate the bound so that the lambda parameter does not appear in it.
+       *  Test case in neg/i94-nada.scala. This test crashes with an illegal instance
+       *  error when the rest of the SI-2712 fix is applied but `pruneLambdaParams` is
+       *  missing.
+       */
+      def pruneLambdaParams(tp: Type) =
+        if (comparingLambdas) {
+          val approx = new ApproximatingTypeMap {
+            def apply(t: Type): Type = t match {
+              case t @ PolyParam(tl: TypeLambda, n) =>
+                val effectiveVariance = if (fromBelow) -variance else variance
+                val bounds = tl.paramBounds(n)
+                if (effectiveVariance > 0) bounds.hi
+                else if (effectiveVariance < 0 ) bounds.lo
+                else NoType
+              case _ =>
+                mapOver(t)
+            }
+          }
+          approx(tp)
+        }
+        else tp
+
       def addParamBound(bound: PolyParam) =
         if (fromBelow) addLess(bound, param) else addLess(param, bound)
 
@@ -336,7 +369,7 @@ trait ConstraintHandling {
           prune(bound.underlying)
         case bound: PolyParam =>
           constraint.entry(bound) match {
-            case NoType => bound
+            case NoType => pruneLambdaParams(bound)
             case _: TypeBounds =>
               if (!addParamBound(bound)) NoType
               else if (fromBelow) defn.NothingType
@@ -345,7 +378,7 @@ trait ConstraintHandling {
               prune(inst)
           }
         case _ =>
-          bound
+          pruneLambdaParams(bound)
       }
 
       try bound match {
diff --git a/src/dotty/tools/dotc/core/Symbols.scala b/src/dotty/tools/dotc/core/Symbols.scala
index df8bc8116..ae88753d0 100644
--- a/src/dotty/tools/dotc/core/Symbols.scala
+++ b/src/dotty/tools/dotc/core/Symbols.scala
@@ -495,6 +495,7 @@ object Symbols {
     def paramBounds(implicit ctx: Context) = denot.info.bounds
     def paramBoundsAsSeenFrom(pre: Type)(implicit ctx: Context) = pre.memberInfo(this).bounds
     def paramVariance(implicit ctx: Context) = denot.variance
+    def paramRef(implicit ctx: Context) = denot.typeRef
 
 // -------- Printing --------------------------------------------------------
 
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index be0c08d15..6e0bf7786 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -341,11 +341,11 @@ class TypeApplications(val self: Type) extends AnyVal {
    *
    *  TODO: Handle parameterized lower bounds
    */
-  def LambdaAbstract(tparams: List[Symbol])(implicit ctx: Context): Type = {
+  def LambdaAbstract(tparams: List[TypeParamInfo])(implicit ctx: Context): Type = {
     def expand(tp: Type) =
       TypeLambda(
-        tpnme.syntheticLambdaParamNames(tparams.length), tparams.map(_.variance))(
-          tl => tparams.map(tparam => tl.lifted(tparams, tparam.info).bounds),
+        tpnme.syntheticLambdaParamNames(tparams.length), tparams.map(_.paramVariance))(
+          tl => tparams.map(tparam => tl.lifted(tparams, tparam.paramBounds).bounds),
           tl => tl.lifted(tparams, tp))
     assert(!isHK, self)
     self match {
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 3036cf878..3a0311977 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -398,7 +398,12 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
           // This wpuld mean that there is no convenient means anymore to express a kind
           // as a supertype. The fix is to delay the checking of bounds so that only
           // bounds of * types are checked.
-          variancesConform(tparams1, tparams2) && isSubType(body1, body2.subst(tp2, tp1))
+          val saved = comparingLambdas
+          comparingLambdas = true
+          try
+            variancesConform(tparams1, tparams2) &&
+            isSubType(body1, body2.subst(tp2, tp1))
+          finally comparingLambdas = saved
         case _ =>
           if (!tp1.isHK) {
             tp2 match {
@@ -592,32 +597,54 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
         false
     }
 
-    /** `param2` can be instantiated to the type constructor of the LHS
-     *  or to the type constructor of one of the LHS base class instances
+    /** `param2` can be instantiated to a type application prefix of the LHS
+     *  or to a type application prefix of one of the LHS base class instances
      *  and the resulting type application is a supertype of `tp1`,
      *  or fallback to fourthTry.
      */
     def canInstantiate(param2: PolyParam): Boolean = {
 
-      /** `param2` can be instantiated to `tycon1a`.
-       *  and the resulting type application is a supertype of `tp1`.
+      /** Let
+       *
+       *    `tparams_1, ..., tparams_k-1`    be the type parameters of the rhs
+       *    `tparams1_1, ..., tparams1_n-1`  be the type parameters of the constructor of the lhs
+       *    `args1_1, ..., args1_n-1`        be the type arguments of the lhs
+       *    `d  =  n - k`
+       *
+       *  Returns `true` iff `d >= 0` and `param2` can be instantiated to
+       *
+       *      [tparams1_d, ... tparams1_n-1] -> tycon1a[args_1, ..., args_d-1, tparams_d, ... tparams_n-1]
+       *
+       *  such that the resulting type application is a supertype of `tp1`.
        */
-      def tyconOK(tycon1a: Type) =
-        variancesConform(tycon1a.typeParams, tparams) && {
-          (ctx.mode.is(Mode.TypevarsMissContext) ||
-           tryInstantiate(param2, tycon1a.ensureHK)) &&
-          isSubType(tp1, tycon1a.appliedTo(args2))
+      def tyconOK(tycon1a: Type, args1: List[Type]) = {
+        var tycon1b = tycon1a
+        val tparams1a = tycon1a.typeParams
+        val lengthDiff = tparams1a.length - tparams.length
+        lengthDiff >= 0 && {
+          val tparams1 = tparams1a.drop(lengthDiff)
+          variancesConform(tparams1, tparams) && {
+            if (lengthDiff > 0)
+              tycon1b = tycon1a
+                .appliedTo(args1.take(lengthDiff) ++ tparams1.map(_.paramRef))
+                .LambdaAbstract(tparams1)
+            (ctx.mode.is(Mode.TypevarsMissContext) ||
+              tryInstantiate(param2, tycon1b.ensureHK)) &&
+              isSubType(tp1, tycon1b.appliedTo(args2))
+          }
         }
+      }
 
       tp1.widen match {
-        case tp1w @ HKApply(tycon1, _) =>
-          tyconOK(tycon1)
+        case tp1w @ HKApply(tycon1, args1) =>
+          tyconOK(tycon1, args1)
         case tp1w =>
           tp1w.typeSymbol.isClass && {
             val classBounds = tycon2.classSymbols
             def liftToBase(bcs: List[ClassSymbol]): Boolean = bcs match {
               case bc :: bcs1 =>
-                classBounds.exists(bc.derivesFrom) && tyconOK(tp1w.baseTypeRef(bc)) ||
+                classBounds.exists(bc.derivesFrom) &&
+                tyconOK(tp1w.baseTypeRef(bc), tp1w.baseArgInfos(bc)) ||
                 liftToBase(bcs1)
               case _ =>
                 false
diff --git a/src/dotty/tools/dotc/core/TypeParamInfo.scala b/src/dotty/tools/dotc/core/TypeParamInfo.scala
index ff3c8fca7..6bec2e0e0 100644
--- a/src/dotty/tools/dotc/core/TypeParamInfo.scala
+++ b/src/dotty/tools/dotc/core/TypeParamInfo.scala
@@ -26,4 +26,7 @@ trait TypeParamInfo {
 
   /** The variance of the type parameter */
   def paramVariance(implicit ctx: Context): Int
+
+  /** A type that refers to the parameter */
+  def paramRef(implicit ctx: Context): Type
 }
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 03fdcb957..728f7fc21 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -2614,12 +2614,14 @@ object Types {
     def paramBoundsAsSeenFrom(pre: Type)(implicit ctx: Context): TypeBounds = paramBounds
     def paramVariance(implicit ctx: Context): Int = tl.variances(n)
     def toArg: Type = PolyParam(tl, n)
+    def paramRef(implicit ctx: Context): Type = PolyParam(tl, n)
   }
 
   object TypeLambda {
     def apply(paramNames: List[TypeName], variances: List[Int])(paramBoundsExp: GenericType => List[TypeBounds], resultTypeExp: GenericType => Type)(implicit ctx: Context): TypeLambda = {
       unique(new TypeLambda(paramNames, variances)(paramBoundsExp, resultTypeExp))
     }
+
     def fromSymbols(tparams: List[Symbol], resultType: Type)(implicit ctx: Context) =
       if (tparams.isEmpty) resultType
       else apply(tparams map (_.name.asTypeName), tparams.map(_.variance))(