Fix of t1236: higher-kinded

(and also of t0625, which reappeared).

Several fixes were made. In summary:

1. Naming and representation of KigherKinded traits changed. It's now $HigherKinded$NIP where
the letters after the second $ indicate variance (N)egative, (I)nvariant, (P)ositive. The HKtraits
themselves are always non-variant in their parameters.

2. When deriving refined types over higher-kinded types, the variance of a type alias
is the variance of the new type constructor.

3. isSubTypeHK was changed, as was the position from where it is called.

4. appliedTo also works for PolyTypes.

10 files changed, 72 insertions, 39 deletions

diff --git a/src/dotty/tools/dotc/config/Printers.scala b/src/dotty/tools/dotc/config/Printers.scala
index 853049b04..d06eb2ece 100644
--- a/src/dotty/tools/dotc/config/Printers.scala
+++ b/src/dotty/tools/dotc/config/Printers.scala
@@ -22,6 +22,7 @@ object Printers {
   val unapp: Printer = noPrinter
   val completions = noPrinter
   val gadts = noPrinter
+  val hk = noPrinter
   val incremental = noPrinter
   val config = noPrinter
 }
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Definitions.scala b/src/dotty/tools/dotc/core/Definitions.scala
index a58bfc058..0ec770149 100644
--- a/src/dotty/tools/dotc/core/Definitions.scala
+++ b/src/dotty/tools/dotc/core/Definitions.scala
@@ -359,12 +359,6 @@ class Definitions {
    */
   def hkTrait(vcs: List[Int]) = {
 
-    def varianceSuffix(v: Int) = v match {
-      case -1 => "N"
-      case  0 => "I"
-      case  1 => "P"
-    }
-
     def varianceFlags(v: Int) = v match {
       case -1 => Contravariant
       case  0 => Covariant
@@ -375,14 +369,13 @@ class Definitions {
       def complete(denot: SymDenotation)(implicit ctx: Context): Unit = {
         val cls = denot.asClass.classSymbol
         val paramDecls = newScope
-        for ((v, i) <- vcs.zipWithIndex)
-          newTypeParam(cls, tpnme.higherKindedParamName(i), varianceFlags(v), paramDecls)
+        for (i <- 0 until vcs.length)
+          newTypeParam(cls, tpnme.higherKindedParamName(i), EmptyFlags, paramDecls)
         denot.info = ClassInfo(ScalaPackageClass.thisType, cls, List(ObjectClass.typeRef), paramDecls)
       }
     }
 
-    val traitName =
-      tpnme.higherKindedTraitName(vcs.length) ++ (vcs map varianceSuffix).mkString
+    val traitName = tpnme.higherKindedTraitName(vcs)
 
     def createTrait = {
       val cls = newClassSymbol(
diff --git a/src/dotty/tools/dotc/core/NameOps.scala b/src/dotty/tools/dotc/core/NameOps.scala
index 1a9e5eddb..b9df8f6ed 100644
--- a/src/dotty/tools/dotc/core/NameOps.scala
+++ b/src/dotty/tools/dotc/core/NameOps.scala
@@ -168,6 +168,19 @@ object NameOps {
       }
     }
 
+    /** The variances of the higherKinded parameters of the trait named
+     *  by this name.
+     *  @pre The name is a higher-kinded trait name, i.e. it starts with HK_TRAIT_PREFIX
+     */
+    def hkVariances: List[Int] = {
+      def varianceOfSuffix(suffix: Char): Int = {
+        val idx = tpnme.varianceSuffixes.indexOf(suffix)
+        assert(idx >= 0)
+        idx - 1
+      }
+      name.drop(tpnme.HK_TRAIT_PREFIX.length).toList.map(varianceOfSuffix)
+    }
+
     /** If name length exceeds allowable limit, replace part of it by hash */
     def compactified(implicit ctx: Context): TermName = termName(compactify(name.toString))
   }
diff --git a/src/dotty/tools/dotc/core/StdNames.scala b/src/dotty/tools/dotc/core/StdNames.scala
index 6cd9da4b5..3982c51f0 100644
--- a/src/dotty/tools/dotc/core/StdNames.scala
+++ b/src/dotty/tools/dotc/core/StdNames.scala
@@ -248,6 +248,7 @@ object StdNames {
     val SPECIALIZED_INSTANCE: N     = "specInstance$"
     val THIS: N                     = "_$this"
     val HK_PARAM_PREFIX: N          = "_$hk$"
+    val HK_TRAIT_PREFIX: N          = "$HigherKinded$"
 
     final val Nil: N                = "Nil"
     final val Predef: N             = "Predef"
@@ -281,7 +282,6 @@ object StdNames {
     val ConstantType: N         = "ConstantType"
     val ExistentialTypeTree: N  = "ExistentialTypeTree"
     val Flag : N                = "Flag"
-    val HigherKinded: N         = "HigherKinded"
     val Ident: N                = "Ident"
     val Import: N               = "Import"
     val Literal: N              = "Literal"
@@ -645,10 +645,14 @@ object StdNames {
     def syntheticTypeParamNames(num: Int): List[TypeName] =
       (0 until num).map(syntheticTypeParamName)(breakOut)
 
-    def higherKindedTraitName(n: Int) = HigherKinded ++ n.toString
+    def higherKindedTraitName(vcs: List[Int]): TypeName = HK_TRAIT_PREFIX ++ vcs.map(varianceSuffix).mkString
     def higherKindedParamName(n: Int) = HK_PARAM_PREFIX ++ n.toString
 
     final val Conforms = encode("<:<")
+
+    def varianceSuffix(v: Int): Char = varianceSuffixes.charAt(v + 1)
+
+    val varianceSuffixes = "NIP"
   }
 
   abstract class JavaNames[N <: Name] extends DefinedNames[N] {
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index 0abd28a71..2e936e2f1 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -137,6 +137,8 @@ class TypeApplications(val self: Type) extends AnyVal {
         tp.underlying.appliedTo(args)
       case AndType(l, r) =>
         l.appliedTo(args) & r
+      case tp: PolyType =>
+        tp.instantiate(args)
       case ErrorType =>
         self
     }
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index b0fc68ba8..753a72dd0 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -412,8 +412,7 @@ class TypeComparer(initctx: Context) extends DotClass {
             val base = tp1.baseTypeRef(cls2)
             if (base.exists && (base ne tp1)) return isSubType(base, tp2)
             if ( cls2 == defn.SingletonClass && tp1.isStable
-              || cls2 == defn.NotNullClass && tp1.isNotNull
-              || (defn.hkTraits contains cls2) && isSubTypeHK(tp1, tp2)) return true
+               || cls2 == defn.NotNullClass && tp1.isNotNull) return true
           }
           fourthTry(tp1, tp2)
       }
@@ -430,7 +429,9 @@ class TypeComparer(initctx: Context) extends DotClass {
           }
         case _ => tp2
       }
-      def compareRefined: Boolean = tp1.widen match {
+      def compareRefined: Boolean =
+        if (defn.hkTraits contains parent2.typeSymbol) isSubTypeHK(tp1, tp2)
+        else tp1.widen match {
         case tp1 @ RefinedType(parent1, name1) if nameMatches(name1, name2, tp1, tp2) =>
           // optimized case; all info on tp1.name2 is in refinement tp1.refinedInfo.
           isSubType(tp1.refinedInfo, tp2.refinedInfo) && {
@@ -443,7 +444,7 @@ class TypeComparer(initctx: Context) extends DotClass {
             case mbr: SingleDenotation => qualifies(mbr)
             case _ => mbr hasAltWith qualifies
           }
-          def hasMatchingMember(name: Name): Boolean = /*>|>*/ ctx.traceIndented(s"hasMatchingMember($name) ${tp1.member(name)}", subtyping) /*<|<*/ (
+          def hasMatchingMember(name: Name): Boolean = /*>|>*/ ctx.traceIndented(s"hasMatchingMember($name) ${tp1.member(name).info.show}", subtyping) /*<|<*/ (
                memberMatches(tp1 member name)
             ||
                { // special case for situations like:
@@ -629,20 +630,33 @@ class TypeComparer(initctx: Context) extends DotClass {
    *  This is the case if `tp1` and `tp2` have the same number
    *  of type parameters, the bounds of tp1's paremeters
    *  are contained in the corresponding bounds of tp2's parameters
-   *  and the variances of correesponding parameters agree.
+   *  and the variances of the parameters agree.
+   *  The variances agree if the supertype parameter is invariant,
+   *  or both parameters have the same variance.
+   *
+   *  Note: When we get to isSubTypeHK, it might be that tp1 is
+   *  instantiated, or not. If it is instantiated, we compare
+   *  actual argument infos against higher-kinded bounds,
+   *  if it is not instantiated we compare type parameter bounds
+   *  and also compare variances.
    */
-  def isSubTypeHK(tp1: Type, tp2: Type): Boolean = {
+  def isSubTypeHK(tp1: Type, tp2: Type): Boolean = ctx.traceIndented(s"isSubTypeHK(${tp1.show}, ${tp2.show}") {
     val tparams = tp1.typeParams
+    val argInfos1 = tp1.argInfos
+    val args1 =
+      if (argInfos1.nonEmpty) argInfos1 // tp1 is instantiated, use the argument infos
+      else { // tp1 is uninstantiated, use the parameter bounds
+        val base = tp1.narrow
+        tparams.map(base.memberInfo) 
+      }
     val hkArgs = tp2.argInfos
-    (hkArgs.length == tparams.length) && {
-      val base = tp1.narrow
-      (tparams, hkArgs).zipped.forall { (tparam, hkArg) =>
-        isSubType(base.memberInfo(tparam), hkArg.bounds) // TODO: base.memberInfo needed?
-      } &&
-        (tparams, tp2.typeSymbol.typeParams).zipped.forall { (tparam, tparam2) =>
-          tparam.variance == tparam2.variance
-        }
-    }
+    hk.println(s"isSubTypeHK: args1 = $args1, hkargs = $hkArgs")
+    val boundsOK = (args1 corresponds hkArgs)(isSubType)
+    val variancesOK =
+      argInfos1.nonEmpty || (tparams corresponds tp2.typeSymbol.name.hkVariances) { (tparam, v) =>
+        v == 0 || tparam.variance == v
+      }
+    boundsOK && variancesOK
   }
 
   def trySetType(tr: NamedType, bounds: TypeBounds): Boolean =
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 967421f2b..38c07d99a 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -123,7 +123,7 @@ object Types {
     final def isLegalPrefix(implicit ctx: Context): Boolean =
       isStable || {
         val absTypeNames = memberNames(abstractTypeNameFilter)
-        if (absTypeNames.nonEmpty) typr.println(s"abstract type members of ${this.showWithUnderlying}: $absTypeNames")
+        if (absTypeNames.nonEmpty) typr.println(s"abstract type members of ${this.showWithUnderlying()}: $absTypeNames")
         absTypeNames.isEmpty
       }
 
@@ -815,11 +815,11 @@ object Types {
     /** Convert to text */
     def toText(printer: Printer): Text = printer.toText(this)
 
-    /** Utility method to show the underlying type of a TypeProxy together
+    /** Utility method to show the underlying type of a TypeProxy chain together
      *  with the proxy type itself.
      */
-    def showWithUnderlying(implicit ctx: Context): String = this match {
-      case tp: TypeProxy => s"$show with underlying ${tp.underlying.show}"
+    def showWithUnderlying(n: Int = 1)(implicit ctx: Context): String = this match {
+      case tp: TypeProxy if n > 0 => s"$show with underlying ${tp.underlying.showWithUnderlying(n - 1)}"
       case _ => show
     }
 
@@ -1309,12 +1309,13 @@ object Types {
       lazy val underlyingTypeParams = parent.safeUnderlyingTypeParams
       lazy val originalTypeParam = underlyingTypeParams(refinedName.hkParamIndex)
 
-      /** drop any co/contra variance in refined info if variance disagrees
-       *  with new type param
+      /** Use variance of newly instantiated type parameter rather than the old hk argument
        */
-      def adjustedHKRefinedInfo(hkBounds: TypeBounds) = {
-        if (hkBounds.variance == originalTypeParam.info.bounds.variance) hkBounds
-        else TypeBounds(hkBounds.lo, hkBounds.hi)
+      def adjustedHKRefinedInfo(hkBounds: TypeBounds, underlyingTypeParam: TypeSymbol) = hkBounds match {
+        case tp @ TypeBounds(lo, hi) if lo eq hi =>
+          tp.derivedTypeBounds(lo, hi, underlyingTypeParam.variance)
+        case _ =>
+          hkBounds
       }
 
       if ((parent eq this.parent) && (refinedName eq this.refinedName) && (refinedInfo eq this.refinedInfo))
@@ -1323,7 +1324,8 @@ object Types {
  //            && { println(s"deriving $refinedName $parent $underlyingTypeParams"); true }
                && refinedName.hkParamIndex < underlyingTypeParams.length
                && originalTypeParam.name != refinedName)
-        derivedRefinedType(parent, originalTypeParam.name, adjustedHKRefinedInfo(refinedInfo.bounds))
+        derivedRefinedType(parent, originalTypeParam.name,
+            adjustedHKRefinedInfo(refinedInfo.bounds, underlyingTypeParams(refinedName.hkParamIndex)))
       else
         RefinedType(parent, refinedName, rt => refinedInfo.substThis(this, RefinedThis(rt)))
     }
diff --git a/src/dotty/tools/dotc/core/transform/Erasure.scala b/src/dotty/tools/dotc/core/transform/Erasure.scala
index eaeb3c8e7..093b59ae8 100644
--- a/src/dotty/tools/dotc/core/transform/Erasure.scala
+++ b/src/dotty/tools/dotc/core/transform/Erasure.scala
@@ -126,7 +126,9 @@ object Erasure {
       sigName(tp1)
     case OrType(tp1, tp2) =>
       lubClass(tp1, tp2).name
-    case ErrorType | WildcardType =>
+    case tp: WildcardType =>
+      tpnme.WILDCARD
+    case ErrorType =>
       tpnme.WILDCARD
   }
 
diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala
index 7885e85ac..361de802c 100644
--- a/src/dotty/tools/dotc/typer/Namer.scala
+++ b/src/dotty/tools/dotc/typer/Namer.scala
@@ -549,6 +549,8 @@ class Namer { typer: Typer =>
                   else NoType
               }
               val iResType = iInstInfo.finalResultType.asSeenFrom(site, cls)
+              if (iResType.exists)
+                typr.println(s"using inherited type; raw: $iRawInfo, inst: $iInstInfo, inherited: $iResType")
               tp & iResType
             }
           }
diff --git a/tests/pending/pos/t1236.scala b/tests/pos/t1236.scala
index eee1cbf02..a84cad0fb 100644
--- a/tests/pending/pos/t1236.scala
+++ b/tests/pos/t1236.scala
@@ -4,7 +4,7 @@ trait Empty[E[_]] {
 
 object T {
   val ListEmpty = new Empty[List] {
-    def e[A]/*: List*/ = Nil  // uncomment to get crash
+    def e[B] = Nil
   }
 
   def foo[F[_]](q:(String,String)) = "hello"