From f8d82c2634dcf9d94037b107d49d088e89f7070f Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 4 Dec 2015 17:55:21 +0100 Subject: Switch to new hk scheme. --- src/dotty/tools/dotc/core/ConstraintHandling.scala | 10 + src/dotty/tools/dotc/core/TypeApplications.scala | 303 ++++++++++----------- src/dotty/tools/dotc/core/TypeComparer.scala | 146 +++++++--- src/dotty/tools/dotc/core/Types.scala | 36 +-- src/dotty/tools/dotc/core/tasty/TreePickler.scala | 42 ++- .../dotc/core/unpickleScala2/Scala2Unpickler.scala | 7 +- src/dotty/tools/dotc/typer/Applications.scala | 4 +- src/dotty/tools/dotc/typer/Typer.scala | 7 +- 8 files changed, 307 insertions(+), 248 deletions(-) (limited to 'src/dotty/tools/dotc') diff --git a/src/dotty/tools/dotc/core/ConstraintHandling.scala b/src/dotty/tools/dotc/core/ConstraintHandling.scala index 577b958c8..ff7afe99a 100644 --- a/src/dotty/tools/dotc/core/ConstraintHandling.scala +++ b/src/dotty/tools/dotc/core/ConstraintHandling.scala @@ -232,6 +232,16 @@ trait ConstraintHandling { } } + /** Instantiate `param` to `tp` if the constraint stays satisfiable */ + protected def tryInstantiate(param: PolyParam, tp: Type): Boolean = { + val saved = constraint + constraint = + if (addConstraint(param, tp, fromBelow = true) && + addConstraint(param, tp, fromBelow = false)) constraint.replace(param, tp) + else saved + constraint ne saved + } + /** Check that constraint is fully propagated. See comment in Config.checkConstraintsPropagated */ def checkPropagated(msg: => String)(result: Boolean): Boolean = { if (Config.checkConstraintsPropagated && result && addConstraintInvocations == 0) { diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala index 4c9746c39..0f9cb8230 100644 --- a/src/dotty/tools/dotc/core/TypeApplications.scala +++ b/src/dotty/tools/dotc/core/TypeApplications.scala @@ -37,6 +37,15 @@ object TypeApplications { case _ => tp } + /** Does the variance of `sym1` conform to the variance of `sym2`? + * This is the case if the variances are the same or `sym` is nonvariant. + */ + def varianceConforms(sym1: TypeSymbol, sym2: TypeSymbol)(implicit ctx: Context) = + sym1.variance == sym2.variance || sym2.variance == 0 + + def variancesConform(syms1: List[TypeSymbol], syms2: List[TypeSymbol])(implicit ctx: Context) = + syms1.corresponds(syms2)(varianceConforms) + /** Extractor for * * [v1 X1: B1, ..., vn Xn: Bn] -> T @@ -123,25 +132,7 @@ object TypeApplications { * T { ... } # $Apply */ object AppliedType { - def apply(tp: Type, args: List[Type])(implicit ctx: Context): Type = { - def matchParams(tp: Type, tparams: List[TypeSymbol], args: List[Type]): Type = args match { - case arg :: args1 => - try { - val tparam :: tparams1 = tparams - matchParams(RefinedType(tp, tparam.name, arg.toBounds(tparam)), tparams1, args1) - } catch { - case ex: MatchError => - println(s"applied type mismatch: $tp $args, typeParams = ${tp.classSymbol.typeParams}") // !!! DEBUG - println(s"precomplete decls = ${tp.typeSymbol.unforcedDecls.toList.map(_.denot).mkString("\n ")}") - throw ex - } - case nil => tp - } - assert(args.nonEmpty) - val cls = tp.classSymbol - val refined = matchParams(tp, cls.typeParams, args) - if (cls.isLambdaTrait) TypeRef(refined, tpnme.hkApply) else refined - } + def apply(tp: Type, args: List[Type])(implicit ctx: Context): Type = tp.appliedTo(args) def unapply(tp: Type)(implicit ctx: Context): Option[(Type, List[Type])] = tp match { case TypeRef(prefix, tpnme.hkApply) => unapp(prefix) @@ -204,18 +195,22 @@ class TypeApplications(val self: Type) extends AnyVal { case self: ClassInfo => self.cls.typeParams case self: TypeRef => - val tsym = self.typeSymbol + val tsym = self.symbol if (tsym.isClass) tsym.typeParams else if (tsym.isAliasType) self.underlying.typeParams - else { - val lam = LambdaClass(forcing = false) - if (lam.exists) lam.typeParams else Nil - } + else if (tsym.isCompleting) + // We are facing a problem when computing the type parameters of an uncompleted + // abstract type. We can't access the bounds of the symbol yet because that + // would cause a cause a cyclic reference. So we return `Nil` instead + // and try to make up for it later. The acrobatics in Scala2Unpicker#readType + // for reading a TypeRef show what's neeed. + Nil + else tsym.info.typeParams case self: RefinedType => val hkParams = self.hkTypeParams if (hkParams.nonEmpty) hkParams else self.parent.typeParams.filterNot(_.name == self.refinedName) - case self: SingletonType => + case self: SingletonType => Nil case self: TypeProxy => self.underlying.typeParams @@ -224,20 +219,15 @@ class TypeApplications(val self: Type) extends AnyVal { } } - /** The type parameters of the underlying class. - * This is like `typeParams`, except for 3 differences. - * First, it does not adjust type parameters in refined types. I.e. type arguments - * do not remove corresponding type parameters. - * Second, it will return Nil for BoundTypes because we might get a NullPointer exception - * on PolyParam#underlying otherwise (demonstrated by showClass test). - * Third, it won't return abstract higher-kinded type parameters, i.e. the type parameters of - * an abstract type are always empty. + /** The higherkinded type parameters in case this is a type lambda + * + * [X1, ..., Xn] -> T + * + * These are the parameters of the underlying lambda class. + * Returns `Nil` for all other types. */ - final def hkTypeParams(implicit ctx: Context): List[TypeSymbol] = self match { - case TypeLambda(_, _, body) => self.typeSymbol.typeParams.head :: body.hkTypeParams - case TypeBounds(lo, hi) => hi.hkTypeParams - case _ => Nil - } + final def hkTypeParams(implicit ctx: Context): List[TypeSymbol] = + self.LambdaTrait.typeParams final def paramBounds(implicit ctx: Context): List[TypeBounds] = typeParams.map(self.memberInfo(_).bounds) @@ -251,11 +241,41 @@ class TypeApplications(val self: Type) extends AnyVal { case _ => NoSymbol } + /** A type ref is eta expandable if it refers to a non-lambda class. + * In that case we can look for parameterized base types fo the type + * to eta expand them. + */ def isEtaExpandable(implicit ctx: Context) = self match { case self: TypeRef => self.symbol.isClass && !self.name.isLambdaTraitName case _ => false } + /** Lambda abstract `self` with given type parameters. Examples: + * + * type T[X] = U becomes type T = [X] -> U + * type T[X] >: L <: U becomes type T >: L <: ([X] -> _ <: U) + */ + def LambdaAbstract(tparams: List[Symbol])(implicit ctx: Context): Type = { + def expand(tp: Type) = { + TypeLambda(tparams.map(_.variance), tparams.map(_.info.bounds), + rt => new ctx.SafeSubstMap(tparams, argRefs(rt, tparams.length)).apply(tp)) + } + self match { + case self: TypeAlias => + self.derivedTypeAlias(expand(self.alias)) + case self @ TypeBounds(lo, hi) => + self.derivedTypeBounds(lo, expand(TypeBounds.upper(hi))) + case _ => expand(self) + } + } +/* + def betaReduce(implicit ctx: Context): Type = self.stripTypeVar match { + case TypeRef(prefix, tpnme.hkApply) => + prefix.betaReduce + case self @ RefinedType(parent, tpnme.hkArg) if parent.isTypeLambda => + HKApplication(parent, self.refinedInfo.dropAlias) + } +*/ /** Adapt argument A to type parameter P in the case P is higher-kinded. * This means: * (1) Make sure that A is a type lambda, if necessary by eta-expanding it. @@ -305,6 +325,7 @@ class TypeApplications(val self: Type) extends AnyVal { } } + /* /** If type `self` is equal, aliased-to, or upperbounded-by a type of the form * `LambdaXYZ { ... }`, the class symbol of that type, otherwise NoSymbol. * symbol of that type, otherwise NoSymbol. @@ -338,11 +359,11 @@ class TypeApplications(val self: Type) extends AnyVal { /** Is type `self` a Lambda with all hk$i fields fully instantiated? */ def isInstantiatedLambda(implicit ctx: Context): Boolean = isSafeLambda && typeParams.isEmpty - +*/ /** Is receiver type higher-kinded (i.e. of kind != "*")? */ def isHK(implicit ctx: Context): Boolean = self.dealias match { case self: TypeRef => self.info.isHK - case RefinedType(_, name) => name == tpnme.hkApply || name.isHkArgName + case RefinedType(_, name) => name == tpnme.hkApply case TypeBounds(_, hi) => hi.isHK case _ => false } @@ -361,14 +382,14 @@ class TypeApplications(val self: Type) extends AnyVal { * * but without forcing anything. */ - def noHK(implicit ctx: Context): Boolean = self.stripTypeVar match { + def classNotLambda(implicit ctx: Context): Boolean = self.stripTypeVar match { case self: RefinedType => - self.parent.noHK + self.parent.classNotLambda case self: TypeRef => - (self.denot.exists) && { + self.denot.exists && { val sym = self.symbol if (sym.isClass) !sym.isLambdaTrait - else sym.isCompleted && self.info.isAlias && self.info.bounds.hi.noHK + else sym.isCompleted && self.info.isAlias && self.info.bounds.hi.classNotLambda } case _ => false @@ -376,72 +397,66 @@ class TypeApplications(val self: Type) extends AnyVal { /** Encode the type resulting from applying this type to given arguments */ final def appliedTo(args: List[Type])(implicit ctx: Context): Type = /*>|>*/ track("appliedTo") /*<|<*/ { - def matchParams(tp: Type, tparams: List[TypeSymbol], args: List[Type]): Type = args match { - case arg :: args1 => - if (tparams.isEmpty) { - println(s"applied type mismatch: $self $args, typeParams = $typeParams, tsym = ${self.typeSymbol.debugString}") // !!! DEBUG - println(s"precomplete decls = ${self.typeSymbol.unforcedDecls.toList.map(_.denot).mkString("\n ")}") - } - val tparam = tparams.head - val tp1 = RefinedType(tp, tparam.name, arg.toBounds(tparam)) - matchParams(tp1, tparams.tail, args1) - case nil => tp + def substHkArgs = new TypeMap { + def apply(tp: Type): Type = tp match { + case TypeRef(RefinedThis(rt), name) if rt.eq(self) && name.isHkArgName => + args(name.hkArgIndex) + case _ => + mapOver(tp) + } + } + if (args.isEmpty || ctx.erasedTypes) self + else self.stripTypeVar match { + case EtaExpansion(self1) => + self1.appliedTo(args) + case TypeLambda(_, _, body) if !args.exists(_.isInstanceOf[TypeBounds]) => + substHkArgs(body) + case self: PolyType => + self.instantiate(args) + case _ => + appliedTo(args, typeParams) } + } - /** Instantiate type `tp` with `args`. - * @param original The original type for which we compute the type parameters - * This makes a difference for refinement types, because - * refinements bind type parameters and thereby remove them - * from `typeParams`. - */ - def instantiate(tp: Type, original: Type): Type = tp match { - case tp: TypeRef => - val tsym = tp.symbol - if (tsym.isAliasType) tp.underlying.appliedTo(args) - else { - val safeTypeParams = - if (tsym.isClass || !tp.typeSymbol.isCompleting) original.typeParams - else { - ctx.warning(i"encountered F-bounded higher-kinded type parameters for $tsym; assuming they are invariant") - defn.LambdaTrait(args map alwaysZero).typeParams // @@@ can we force? - } - matchParams(tp, safeTypeParams, args) + def appliedTo(args: List[Type], typParams: List[TypeSymbol])(implicit ctx: Context): Type = { + def matchParams(t: Type, tparams: List[TypeSymbol], args: List[Type])(implicit ctx: Context): Type = args match { + case arg :: args1 => + try { + val tparam :: tparams1 = tparams + matchParams(RefinedType(t, tparam.name, arg.toBounds(tparam)), tparams1, args1) + } catch { + case ex: MatchError => + println(s"applied type mismatch: $self $args, typeParams = $typParams") // !!! DEBUG + //println(s"precomplete decls = ${self.typeSymbol.unforcedDecls.toList.map(_.denot).mkString("\n ")}") + throw ex } - case tp: RefinedType => - val redux = tp.EtaReduce - if (redux.exists) redux.appliedTo(args) // Rewrite ([hk$0] => C[hk$0])(T) to C[T] - else tp.derivedRefinedType( - instantiate(tp.parent, original), - tp.refinedName, - tp.refinedInfo) - case tp: TypeProxy => - instantiate(tp.underlying, original) - case tp: PolyType => - tp.instantiate(args) - case ErrorType => - tp + case nil => t } - - /** Same as isHK, except we classify all abstract types as HK, - * (they must be, because they are applied). This avoids some forcing and - * CyclicReference errors of the standard isHK. - */ - def isKnownHK(tp: Type): Boolean = tp match { - case tp: TypeRef => - val sym = tp.symbol - if (sym.isClass) sym.isLambdaTrait - else !sym.isAliasType || isKnownHK(tp.info) - case tp: TypeProxy => isKnownHK(tp.underlying) - case _ => false + assert(args.nonEmpty) + matchParams(self, typParams, args) match { + case refined @ RefinedType(_, pname) if pname.isHkArgName => + TypeRef(refined, tpnme.hkApply) + case refined => + refined } + } - if (args.isEmpty || ctx.erasedTypes) self - else { - val res = instantiate(self, self) - if (isKnownHK(res)) TypeRef(res, tpnme.hkApply) else res + + final def appliedTo(arg: Type)(implicit ctx: Context): Type = appliedTo(arg :: Nil) + final def appliedTo(arg1: Type, arg2: Type)(implicit ctx: Context): Type = appliedTo(arg1 :: arg2 :: Nil) + + final def safeAppliedTo(args: List[Type])(implicit ctx: Context) = { + val safeTypeParams = self match { + case self: TypeRef if !self.symbol.isClass && self.symbol.isCompleting => + // This happens when unpickling e.g. scala$collection$generic$GenMapFactory$$CC + ctx.warning(i"encountered F-bounded higher-kinded type parameters for ${self.symbol}; assuming they are invariant") + defn.LambdaTrait(args map alwaysZero).typeParams + case _ => + typeParams } + appliedTo(args, safeTypeParams) } - +/* /** Simplify a fully instantiated type of the form `LambdaX{... type Apply = T } # Apply` to `T`. */ def simplifyApply(implicit ctx: Context): Type = self match { @@ -452,9 +467,7 @@ class TypeApplications(val self: Type) extends AnyVal { } case _ => self } - - final def appliedTo(arg: Type)(implicit ctx: Context): Type = appliedTo(arg :: Nil) - final def appliedTo(arg1: Type, arg2: Type)(implicit ctx: Context): Type = appliedTo(arg1 :: arg2 :: Nil) +*/ /** Turn this type, which is used as an argument for * type parameter `tparam`, into a TypeBounds RHS @@ -558,26 +571,9 @@ class TypeApplications(val self: Type) extends AnyVal { * otherwise return Nil. * Existential types in arguments are returned as TypeBounds instances. */ - final def argInfos(implicit ctx: Context): List[Type] = { - var tparams: List[TypeSymbol] = null - def recur(tp: Type, refineCount: Int): mutable.ListBuffer[Type] = tp.stripTypeVar match { - case tp @ RefinedType(tycon, name) => - val buf = recur(tycon, refineCount + 1) - if (buf == null) null - else { - if (tparams == null) tparams = tycon.typeParams - if (buf.size < tparams.length) { - val tparam = tparams(buf.size) - if (name == tparam.name) buf += tp.refinedInfo.argInfo - else null - } else null - } - case _ => - if (refineCount == 0) null - else new mutable.ListBuffer[Type] - } - val buf = recur(self, 0) - if (buf == null || buf.size != tparams.length) Nil else buf.toList + final def argInfos(implicit ctx: Context): List[Type] = self match { + case AppliedType(tycon, args) => args + case _ => Nil } /** Argument types where existential types in arguments are disallowed */ @@ -600,6 +596,11 @@ class TypeApplications(val self: Type) extends AnyVal { self } + final def typeConstructor(implicit ctx: Context): Type = self.stripTypeVar match { + case AppliedType(tycon, _) => tycon + case self => self + } + /** If this is the image of a type argument; recover the type argument, * otherwise NoType. */ @@ -609,6 +610,11 @@ class TypeApplications(val self: Type) extends AnyVal { case _ => NoType } + def dropAlias(implicit ctx: Context): Type = self match { + case TypeAlias(alias) => alias + case _ => self + } + /** The element type of a sequence or array */ def elemType(implicit ctx: Context): Type = self match { case defn.ArrayOf(elemtp) => elemtp @@ -639,7 +645,7 @@ class TypeApplications(val self: Type) extends AnyVal { } recur(self) } - +/* /** The typed lambda abstraction of this type `T` relative to `boundSyms`. * This is: * @@ -690,7 +696,7 @@ class TypeApplications(val self: Type) extends AnyVal { expand(self) } } - +*/ /** Convert a type constructor `TC` which has type parameters `T1, ..., Tn` * in a context where type parameters `U1,...,Un` are expected to * @@ -701,20 +707,17 @@ class TypeApplications(val self: Type) extends AnyVal { * - `T1,...,Tn` otherwise. * v1 is compatible with v2, if v1 = v2 or v2 is non-variant. */ - def EtaExpand(tparams: List[Symbol])(implicit ctx: Context): Type = { - def varianceCompatible(actual: Symbol, formal: Symbol) = - formal.variance == 0 || actual.variance == formal.variance - val tparamsToUse = - if (typeParams.corresponds(tparams)(varianceCompatible)) tparams else typeParams + def EtaExpand(tparams: List[TypeSymbol])(implicit ctx: Context): Type = { + val tparamsToUse = if (variancesConform(typeParams, tparams)) tparams else typeParams self.appliedTo(tparams map (_.typeRef)).LambdaAbstract(tparamsToUse) //.ensuring(res => res.EtaReduce =:= self, s"res = $res, core = ${res.EtaReduce}, self = $self, hc = ${res.hashCode}") } - +/* /** Eta expand if `bound` is a higher-kinded type */ def EtaExpandIfHK(bound: Type)(implicit ctx: Context): Type = if (bound.isHK && !isHK && self.typeSymbol.isClass && typeParams.nonEmpty) EtaExpand(bound.typeParams) else self - +*/ /** Eta expand the prefix in front of any refinements. */ def EtaExpandCore(implicit ctx: Context): Type = self.stripTypeVar match { case self: RefinedType => @@ -722,7 +725,7 @@ class TypeApplications(val self: Type) extends AnyVal { case _ => self.EtaExpand(self.typeParams) } - +/* /** If `self` is a (potentially partially instantiated) eta expansion of type T, return T, * otherwise NoType. More precisely if `self` is of the form * @@ -809,31 +812,21 @@ class TypeApplications(val self: Type) extends AnyVal { * @param classBounds A hint to bound the search. Only types that derive from one of the * classes in classBounds are considered. */ - def testLifted(tparams: List[Symbol], p: Type => Boolean, classBounds: List[ClassSymbol])(implicit ctx: Context): Boolean = { - def tryLift(bcs: List[ClassSymbol]): Boolean = bcs match { + def testLifted(tparams: List[Symbol], p: Type => Boolean, classBounds: List[ClassSymbol] = Nil)(implicit ctx: Context): Boolean = { + def recur(bcs: List[ClassSymbol]): Boolean = bcs match { case bc :: bcs1 => - val tp = self.baseTypeWithArgs(bc) - val targs = tp.argInfos - val tycon = tp.withoutArgs(targs) + val baseRef = self.baseTypeRef(bc) def variancesMatch(param1: Symbol, param2: Symbol) = param2.variance == param2.variance || param2.variance == 0 - if (classBounds.exists(tycon.derivesFrom(_)) && - tycon.typeParams.corresponds(tparams)(variancesMatch)) { - val expanded = tycon.EtaExpand(tparams) - val lifted = (expanded /: targs) { (partialInst, targ) => - val tparam = partialInst.typeParams.head - RefinedType(partialInst, tparam.name, targ.bounds.withVariance(tparam.variance)) - } - ctx.traceIndented(i"eta lifting $self --> $lifted", hk) { - p(lifted) || tryLift(bcs1) - } - } - else tryLift(bcs1) + (classBounds.exists(bc.derivesFrom) && + baseRef.typeParams.corresponds(tparams)(variancesMatch) && + p(baseRef.appliedTo(self.baseArgInfos(bc))) + || + recur(bcs1)) case nil => false } - tparams.nonEmpty && - (typeParams.hasSameLengthAs(tparams) && p(EtaExpand(tparams)) || - classBounds.nonEmpty && tryLift(self.baseClasses)) + classBounds.nonEmpty && recur(self.baseClasses) } + */ } diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 6b37227b2..bdabca8df 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -12,6 +12,7 @@ import util.{Stats, DotClass, SimpleMap} import config.Config import config.Printers._ import TypeErasure.{erasedLub, erasedGlb} +import TypeApplications._ import scala.util.control.NonFatal /** Provides methods to compare types. @@ -150,20 +151,21 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case info1: TypeAlias => compareNamed(info1.alias, tp2) case _ => val sym1 = tp1.symbol - (if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol)) - ctx.erasedTypes || - sym1.isStaticOwner || - isSubType(tp1.prefix, tp2.prefix) || - thirdTryNamed(tp1, tp2) - else - (tp1.name eq tp2.name) && - isSubType(tp1.prefix, tp2.prefix) && - (tp1.signature == tp2.signature) && - !tp1.isInstanceOf[WithFixedSym] && - !tp2.isInstanceOf[WithFixedSym] || - compareHK(tp1, tp2, inOrder = true) || - compareHK(tp2, tp1, inOrder = false) || - thirdTryNamed(tp1, tp2)) + if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol)) + ctx.erasedTypes || + sym1.isStaticOwner || + isSubType(tp1.prefix, tp2.prefix) || + thirdTryNamed(tp1, tp2) + else + ( (tp1.name eq tp2.name) + && isSubType(tp1.prefix, tp2.prefix) + && tp1.signature == tp2.signature + && !tp1.isInstanceOf[WithFixedSym] + && !tp2.isInstanceOf[WithFixedSym] + ) || + compareHK(tp1, tp2, inOrder = true) || + compareHK(tp2, tp1, inOrder = false) || + thirdTryNamed(tp1, tp2) } case _ => compareHK(tp2, tp1, inOrder = false) || @@ -239,9 +241,9 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp1: NamedType => tp1.info match { case info1: TypeAlias => isSubType(info1.alias, tp2) - case _ => compareHK(tp1, tp2, inOrder = true) || thirdTry(tp1, tp2) - // Note: If we change the order here, doing compareHK first and following aliases second, - // we get a -Ycheck error when compiling dotc/transform. Need to investigate. + case _ => + compareHK(tp1, tp2, inOrder = true) || + thirdTry(tp1, tp2) } case tp1: PolyParam => def flagNothingBound = { @@ -344,12 +346,16 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp1: AndType => // Delay calling `compareRefinedSlow` because looking up a member // of an `AndType` can lead to a cascade of subtyping checks + // This twist is needed to make collection/generic/ParFactory.scala compile fourthTry(tp1, tp2) || compareRefinedSlow case _ => compareRefinedSlow || fourthTry(tp1, tp2) } + def etaExpandedSubType(tp1: Type) = + isSubType(tp1.typeConstructor.EtaExpand(tp2.typeParams), tp2) normalPath || - needsEtaLift(tp1, tp2) && tp1.testLifted(tp2.typeParams, isSubType(_, tp2), classBounds(tp2)) + needsEtaLift(tp1, tp2) && + testLifted(tp1, tp2, tp2.typeParams, etaExpandedSubType) } else // fast path, in particular for refinements resulting from parameterization. isSubType(tp1, skipped2) && @@ -471,7 +477,9 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { isNewSubType(tp1.underlying.widenExpr, tp2) || comparePaths case tp1: RefinedType => isNewSubType(tp1.parent, tp2) || - needsEtaLift(tp2, tp1) && tp2.testLifted(tp1.typeParams, isSubType(tp1, _), Nil) + needsEtaLift(tp2, tp1) && + tp2.typeParams.length == tp1.typeParams.length && + isSubType(tp1, tp2.EtaExpand(tp1.typeParams)) case AndType(tp11, tp12) => // Rewrite (T111 | T112) & T12 <: T2 to (T111 & T12) <: T2 and (T112 | T12) <: T2 // and analogously for T11 & (T121 | T122) & T12 <: T2 @@ -502,19 +510,89 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { false } - /** If `projection` is a hk projection T#$apply - * and `other` is not a hk projection, then convert `other` to a hk projection `U`, and - * continue with `T <:< U` if `inOrder` is true and `U <:< T` otherwise. + /** Does `tp` need to be eta lifted to be comparable to `target`? + * This is the case if: + * - target is a type lambda, and + * - `tp` is eta-expandable (i.e. is a non-lambda class ref) */ - def compareHK(projection: NamedType, other: Type, inOrder: Boolean) = - projection.name == tpnme.hkApply && - !other.isHKApply && - other.testLifted(projection.prefix.LambdaClass(forcing = true).typeParams, - if (inOrder) isSubType(projection.prefix, _) else isSubType(_, projection.prefix), - if (inOrder) Nil else classBounds(projection.prefix)) + private def needsEtaLift(tp: Type, target: RefinedType): Boolean = + target.refinedName == tpnme.hkApply && tp.isEtaExpandable - /** The class symbols bounding the type of the `Apply` member of `tp` */ - private def classBounds(tp: Type) = tp.member(tpnme.hkApply).info.classSymbols + /** Test whether `tp1` has a base type of the form `B[T1, ..., Tn]` where + * - `B` derives from one of the class symbols of `tp2`, + * - the type parameters of `B` match one-by-one the variances of `tparams`, + * - `B` satisfies predicate `p`. + */ + private def testLifted[T](tp1: Type, tp2: Type, tparams: List[TypeSymbol], p: Type => Boolean): Boolean = { + val classBounds = tp2.member(tpnme.hkApply).info.classSymbols + def recur(bcs: List[ClassSymbol]): Boolean = bcs match { + case bc :: bcs1 => + val baseRef = tp1.baseTypeRef(bc) + (classBounds.exists(bc.derivesFrom) && + variancesConform(baseRef.typeParams, tparams) && + p(baseRef.appliedTo(tp1.baseArgInfos(bc))) + || + recur(bcs1)) + case nil => + false + } + recur(tp1.baseClasses) + } + + /** If `projection` is a hk projection T#$apply with a constrainable poly param + * as type constructor and `other` is not a hk projection, then perform the following + * steps: + * + * (1) If not `inOrder` then perform the next steps until they all succeed + * for each base type of other which + * - derives from a class bound of `projection`, + * - has the same number of type parameters than `projection` + * - has type parameter variances which conform to those of `projection`. + * If `inOrder` then perform the same steps on the original `other` type. + * + * (2) Try to eta expand the constructor of `other`. + * + * (3a) In mode `TypeVarsMissConetxt` replace the projection's hk constructor parameter + * by the eta expansion of step (2) reapplied to the projection's arguments. + * (3b) In normal mode, try to unify the projection's hk constructor parameter with + * the eta expansion of step(2) + * + * (4) If `inOrder`, test `projection <: other` else test `other <: projection`. + */ + def compareHK(projection: NamedType, other: Type, inOrder: Boolean): Boolean = { + def tryInfer(tp: Type): Boolean = ctx.traceIndented(i"compareHK($projection, $other, inOrder = $inOrder, constr = $tp)", subtyping) { + tp match { + case tp: TypeVar => tryInfer(tp.underlying) + case param: PolyParam if canConstrain(param) => + + def unifyWith(liftedOther: Type): Boolean = { + subtyping.println(i"unify with $liftedOther") + liftedOther.typeConstructor.widen match { + case tycon: TypeRef if tycon.isEtaExpandable && tycon.typeParams.nonEmpty => + val (ok, projection1) = + if (ctx.mode.is(Mode.TypevarsMissContext)) + (true, EtaExpansion(tycon).appliedTo(projection.argInfos)) + else + (tryInstantiate(param, EtaExpansion(tycon)), projection) + ok && + (if (inOrder) isSubType(projection1, other) else isSubType(other, projection1)) // ### move out? + case _ => + false + } + } + val hkTypeParams = param.typeParams + subtyping.println(i"classBounds = ${projection.prefix.member(tpnme.hkApply).info.classSymbols}") + subtyping.println(i"base classes = ${other.baseClasses}") + subtyping.println(i"type params = $hkTypeParams") + if (inOrder) unifyWith(other) + else testLifted(other, projection.prefix, hkTypeParams, unifyWith) + case _ => + false + } + } + projection.name == tpnme.hkApply && !other.isHKApply && + tryInfer(projection.prefix.typeConstructor.dealias) + } /** Returns true iff either `tp11 <:< tp21` or `tp12 <:< tp22`, trying at the same time * to keep the constraint as wide as possible. Specifically, if @@ -665,14 +743,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case _ => false } - /** Does `tp` need to be eta lifted to be comparable to `target`? */ - private def needsEtaLift(tp: Type, target: RefinedType): Boolean = { - // if (tp.isLambda != tp.isHK) println(i"discrepancy for $tp, isLambda = ${tp.isLambda}, isHK = ${tp.isHK}") - val name = target.refinedName - (name.isHkArgName || (name eq tpnme.hkApply)) && - tp.exists && !tp.isLambda // we do encounter Lambda classes without any arguments here - } - /** Narrow gadt.bounds for the type parameter referenced by `tr` to include * `bound` as an upper or lower bound (which depends on `isUpper`). * Test that the resulting bounds are still satisfiable. diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 4af4d0c14..54e6397bb 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -893,7 +893,7 @@ object Types { else if (!pre.refinementRefersToThis) alias else alias match { case TypeRef(RefinedThis(`pre`), aliasName) => lookupRefined(aliasName) // (1) - case _ => if (name == tpnme.hkApply) betaReduce(alias) else NoType // (2) + case _ => if (name == tpnme.hkApply) betaReduce(alias) else NoType // (2) // ### use TypeApplication's betaReduce } case _ => loop(pre.parent) } @@ -1513,7 +1513,12 @@ object Types { else { val res = prefix.lookupRefined(name) if (res.exists) res - else if (name == tpnme.hkApply && prefix.noHK) derivedSelect(prefix.EtaExpandCore) + else if (name == tpnme.hkApply && prefix.classNotLambda) { + // After substitution we might end up with a type like + // `C { type hk$0 = T0; ...; type hk$n = Tn } # $Apply` + // where C is a class. In that case we eta expand `C`. + derivedSelect(prefix.EtaExpandCore) + } else newLikeThis(prefix) } @@ -1753,8 +1758,8 @@ object Types { object TypeRef { def checkProjection(prefix: Type, name: TypeName)(implicit ctx: Context) = - if (name == tpnme.hkApply && prefix.noHK) - assert(false, s"bad type : $prefix.$name should not be $$applied") + if (name == tpnme.hkApply && prefix.classNotLambda) + assert(false, s"bad type : $prefix.$name does not allow $$Apply projection") /** Create type ref with given prefix and name */ def apply(prefix: Type, name: TypeName)(implicit ctx: Context): TypeRef = { @@ -1894,22 +1899,7 @@ object Types { override def underlying(implicit ctx: Context) = parent - private def checkInst(implicit ctx: Context): this.type = { - if (Config.checkLambdaVariance) - refinedInfo match { - case refinedInfo: TypeBounds if refinedInfo.variance != 0 && refinedName.isHkArgName => - val cls = parent.LambdaClass(forcing = false) - if (cls.exists) - assert(refinedInfo.variance == cls.typeParams.apply(refinedName.hkArgIndex).variance, - s"variance mismatch for $this, $cls, ${cls.typeParams}, ${cls.typeParams.apply(refinedName.hkArgIndex).variance}, ${refinedInfo.variance}") - case _ => - } - if (Config.checkProjections && - (refinedName == tpnme.hkApply || refinedName.isHkArgName) && - parent.noHK) - assert(false, s"illegal refinement of first-order type: $this") - this - } + private def checkInst(implicit ctx: Context): this.type = this def derivedRefinedType(parent: Type, refinedName: Name, refinedInfo: Type)(implicit ctx: Context): RefinedType = if ((parent eq this.parent) && (refinedName eq this.refinedName) && (refinedInfo eq this.refinedInfo)) this @@ -2743,9 +2733,9 @@ object Types { abstract class TypeAlias(val alias: Type, override val variance: Int) extends TypeBounds(alias, alias) { /** pre: this is a type alias */ - def derivedTypeAlias(tp: Type, variance: Int = this.variance)(implicit ctx: Context) = - if ((lo eq tp) && (variance == this.variance)) this - else TypeAlias(tp, variance) + def derivedTypeAlias(alias: Type, variance: Int = this.variance)(implicit ctx: Context) = + if ((alias eq this.alias) && (variance == this.variance)) this + else TypeAlias(alias, variance) override def & (that: TypeBounds)(implicit ctx: Context): TypeBounds = { val v = this commonVariance that diff --git a/src/dotty/tools/dotc/core/tasty/TreePickler.scala b/src/dotty/tools/dotc/core/tasty/TreePickler.scala index c0136538b..8fccb8973 100644 --- a/src/dotty/tools/dotc/core/tasty/TreePickler.scala +++ b/src/dotty/tools/dotc/core/tasty/TreePickler.scala @@ -9,6 +9,7 @@ import Contexts._, Symbols._, Types._, Names._, Constants._, Decorators._, Annot import collection.mutable import NameOps._ import TastyBuffer._ +import TypeApplications._ class TreePickler(pickler: TastyPickler) { val buf = new TreeBuffer @@ -142,6 +143,9 @@ class TreePickler(pickler: TastyPickler) { } def pickleNewType(tpe: Type, richTypes: Boolean): Unit = try { tpe match { + case AppliedType(tycon, args) => + writeByte(APPLIEDtype) + withLength { pickleType(tycon); args.foreach(pickleType(_)) } case ConstantType(value) => pickleConstant(value) case tpe: TypeRef if tpe.info.isAlias && tpe.symbol.is(Flags.AliasPreferred) => @@ -181,17 +185,16 @@ class TreePickler(pickler: TastyPickler) { pickleNameAndSig(tpe.name, tpe.signature); pickleType(tpe.prefix) } case tpe: NamedType => - if (tpe.name == tpnme.hkApply && tpe.prefix.argInfos.nonEmpty && tpe.prefix.isInstantiatedLambda) - // instantiated lambdas are pickled as APPLIEDTYPE; #Apply will - // be reconstituted when unpickling. - pickleType(tpe.prefix) - else if (isLocallyDefined(tpe.symbol)) { - writeByte(if (tpe.isType) TYPEREFsymbol else TERMREFsymbol) - pickleSymRef(tpe.symbol); pickleType(tpe.prefix) - } - else { - writeByte(if (tpe.isType) TYPEREF else TERMREF) - pickleName(tpe.name); pickleType(tpe.prefix) + tpe match { + case _ => + if (isLocallyDefined(tpe.symbol)) { + writeByte(if (tpe.isType) TYPEREFsymbol else TERMREFsymbol) + pickleSymRef(tpe.symbol); pickleType(tpe.prefix) + } + else { + writeByte(if (tpe.isType) TYPEREF else TERMREF) + pickleName(tpe.name); pickleType(tpe.prefix) + } } case tpe: ThisType => if (tpe.cls.is(Flags.Package) && !tpe.cls.isEffectiveRoot) @@ -211,18 +214,11 @@ class TreePickler(pickler: TastyPickler) { case tpe: SkolemType => pickleType(tpe.info) case tpe: RefinedType => - val args = tpe.argInfos - if (args.isEmpty) { - writeByte(REFINEDtype) - withLength { - pickleType(tpe.parent) - pickleName(tpe.refinedName) - pickleType(tpe.refinedInfo, richTypes = true) - } - } - else { - writeByte(APPLIEDtype) - withLength { pickleType(tpe.withoutArgs(args)); args.foreach(pickleType(_)) } + writeByte(REFINEDtype) + withLength { + pickleType(tpe.parent) + pickleName(tpe.refinedName) + pickleType(tpe.refinedInfo, richTypes = true) } case tpe: TypeAlias => writeByte(TYPEALIAS) diff --git a/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala b/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala index 747d73ea9..b0e31202f 100644 --- a/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala +++ b/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala @@ -53,7 +53,7 @@ object Scala2Unpickler { case TempPolyType(tparams, restpe) => if (denot.isType) { assert(!denot.isClass) - restpe.LambdaAbstract(tparams, cycleParanoid = true) + restpe.LambdaAbstract(tparams) } else PolyType.fromSymbols(tparams, restpe) @@ -715,8 +715,9 @@ class Scala2Unpickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClas else TypeRef(pre, sym.name.asTypeName) val args = until(end, readTypeRef) if (sym == defn.ByNameParamClass2x) ExprType(args.head) - else if (args.isEmpty && sym.typeParams.nonEmpty) tycon.EtaExpand(sym.typeParams) - else tycon.appliedTo(adaptArgs(sym.typeParams, args)) + else if (args.nonEmpty) tycon.safeAppliedTo(adaptArgs(sym.typeParams, args)) + else if (sym.typeParams.nonEmpty) tycon.EtaExpand(sym.typeParams) + else tycon case TYPEBOUNDStpe => TypeBounds(readTypeRef(), readTypeRef()) case REFINEDtpe => diff --git a/src/dotty/tools/dotc/typer/Applications.scala b/src/dotty/tools/dotc/typer/Applications.scala index e8ba3b07b..d119658be 100644 --- a/src/dotty/tools/dotc/typer/Applications.scala +++ b/src/dotty/tools/dotc/typer/Applications.scala @@ -614,10 +614,10 @@ trait Applications extends Compatibility { self: Typer => } def adaptTypeArg(tree: tpd.Tree, bound: Type)(implicit ctx: Context): tpd.Tree = { - val was = tree.tpe.EtaExpandIfHK(bound) + //val was = tree.tpe.EtaExpandIfHK(bound) //val now = tree.tpe.adaptIfHK(bound) // ### //if (was != now) println(i"diff adapt ${tree.tpe} to $bound, was: $was, now: $now") - tree.withType(was)//tree.tpe.adaptIfHK(bound)) + tree.withType(tree.tpe.adaptIfHK(bound)) } /** Rewrite `new Array[T](....)` trees to calls of newXYZArray methods. */ diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala index 3f5c4f47e..f857a2504 100644 --- a/src/dotty/tools/dotc/typer/Typer.scala +++ b/src/dotty/tools/dotc/typer/Typer.scala @@ -348,10 +348,9 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit typed(cpy.Block(tree)(clsDef :: Nil, New(Ident(x), Nil)), pt) case _ => var tpt1 = typedType(tree.tpt) - if (tpt1.tpe.isHK) { - val deAliased = tpt1.tpe.dealias.EtaReduce - if (deAliased.exists && deAliased.ne(tpt1.tpe)) - tpt1 = tpt1.withType(deAliased) + tpt1.tpe.dealias match { + case TypeApplications.EtaExpansion(tycon) => tpt1 = tpt1.withType(tycon) + case _ => } checkClassTypeWithStablePrefix(tpt1.tpe, tpt1.pos, traitReq = false) assignType(cpy.New(tree)(tpt1), tpt1) -- cgit v1.2.3