From d6df293d2120f2247198cb6646a23c338f7dcbbf Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 19 Mar 2014 17:56:03 +0100 Subject: 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. --- src/dotty/tools/dotc/config/Printers.scala | 1 + src/dotty/tools/dotc/core/Definitions.scala | 13 ++----- src/dotty/tools/dotc/core/NameOps.scala | 13 +++++++ src/dotty/tools/dotc/core/StdNames.scala | 8 +++-- src/dotty/tools/dotc/core/TypeApplications.scala | 2 ++ src/dotty/tools/dotc/core/TypeComparer.scala | 44 +++++++++++++++-------- src/dotty/tools/dotc/core/Types.scala | 22 ++++++------ src/dotty/tools/dotc/core/transform/Erasure.scala | 4 ++- src/dotty/tools/dotc/typer/Namer.scala | 2 ++ 9 files changed, 71 insertions(+), 38 deletions(-) (limited to 'src/dotty/tools') 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 } } -- cgit v1.2.3