diff options
author | Martin Odersky <odersky@gmail.com> | 2016-06-29 20:03:38 +0200 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2016-07-11 13:35:03 +0200 |
commit | f6efd99e09843d54150f4c5e0f723087ba92007e (patch) | |
tree | 0fb5d0f84c3ed99e5a403437fd7321fe5a783cc6 /src | |
parent | 3490e018e8b11a9d30629e8d415cbae5efd4abf4 (diff) | |
download | dotty-f6efd99e09843d54150f4c5e0f723087ba92007e.tar.gz dotty-f6efd99e09843d54150f4c5e0f723087ba92007e.tar.bz2 dotty-f6efd99e09843d54150f4c5e0f723087ba92007e.zip |
Fix appliedTo and typeParams, and higher kinded subtyping tests
Add existential type elimination for HKApply
Diffstat (limited to 'src')
-rw-r--r-- | src/dotty/tools/dotc/core/TypeApplications.scala | 55 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/TypeComparer.scala | 198 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala | 8 |
3 files changed, 196 insertions, 65 deletions
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala index 12b42642d..60d01c125 100644 --- a/src/dotty/tools/dotc/core/TypeApplications.scala +++ b/src/dotty/tools/dotc/core/TypeApplications.scala @@ -245,16 +245,22 @@ class TypeApplications(val self: Type) extends AnyVal { self match { case self: ClassInfo => self.cls.typeParams + case self: TypeLambda => + self.typeParams case self: TypeRef => val tsym = self.symbol - if (tsym.isClass) tsym.typeParams else tsym.info.typeParams + if (tsym.isClass) tsym.typeParams + else if (!tsym.isCompleting) tsym.info.typeParams + else Nil case self: RefinedType => val precedingParams = self.parent.typeParams.filterNot(_.memberName == self.refinedName) if (self.isTypeParam) precedingParams :+ self else precedingParams case self: RecType => self.parent.typeParams - case self: SingletonType => + case _: HKApply | _: SingletonType => Nil + case self: WildcardType => + self.optBounds.typeParams case self: TypeProxy => self.underlying.typeParams case _ => @@ -342,7 +348,7 @@ class TypeApplications(val self: Type) extends AnyVal { case self: TypeLambda => true case self: HKApply => false case self: SingletonType => false - case self: TypeVar => self.origin.isHK + case self: TypeVar => self.origin.isHK // discrepancy with typeParams, why? case self: WildcardType => self.optBounds.isHK case self: TypeProxy => self.underlying.isHK case _ => false @@ -439,7 +445,11 @@ class TypeApplications(val self: Type) extends AnyVal { */ def LambdaAbstract(tparams: List[Symbol])(implicit ctx: Context): Type = { def expand(tp: Type) = - if (Config.newHK) TypeLambda.fromSymbols(tparams, tp) + if (Config.newHK) + TypeLambda( + tpnme.syntheticLambdaParamNames(tparams.length), tparams.map(_.variance))( + tl => tparams.map(tparam => tl.lifted(tparams, tparam.info).bounds), + tl => tl.lifted(tparams, tp)) else TypeLambdaOLD( tparams.map(tparam => @@ -579,6 +589,10 @@ class TypeApplications(val self: Type) extends AnyVal { self.EtaExpand(self.typeParamSymbols) } + /** If self is not higher-kinded, eta expand it. */ + def ensureHK(implicit ctx: Context): Type = + if (isHK) self else EtaExpansion(self) + /** Eta expand if `self` is a (non-lambda) class reference and `bound` is a higher-kinded type */ def etaExpandIfHK(bound: Type)(implicit ctx: Context): Type = { val hkParams = bound.hkTypeParams @@ -687,8 +701,10 @@ class TypeApplications(val self: Type) extends AnyVal { } } substHkArgs(body) - case self1 => - self1.safeDealias.appliedTo(args, typeParams) + case self1: WildcardType => + self1 + case _ => + self.safeDealias.appliedTo(args, typeParams) } } @@ -712,18 +728,31 @@ class TypeApplications(val self: Type) extends AnyVal { case nil => t } assert(args.nonEmpty) - if (Config.newHK && self.isHK) AppliedType(self, args) - else matchParams(self, typParams, args) match { - case refined @ RefinedType(_, pname, _) if !Config.newHK && pname.isHkArgNameOLD => - refined.betaReduceOLD - case refined => - refined + self.stripTypeVar match { + case self: TypeLambda if !args.exists(_.isInstanceOf[TypeBounds]) => + self.instantiate(args) + case self: AndOrType => + self.derivedAndOrType(self.tp1.appliedTo(args), self.tp2.appliedTo(args)) + case self: LazyRef => + LazyRef(() => self.ref.appliedTo(args, typParams)) + case _ if typParams.isEmpty || typParams.head.isInstanceOf[LambdaParam] => + HKApply(self, args) + case _ => + matchParams(self, typParams, args) match { + case refined @ RefinedType(_, pname, _) if !Config.newHK && pname.isHkArgNameOLD => + refined.betaReduceOLD + case refined => + refined + } } } 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 applyIfParameterized(args: List[Type])(implicit ctx: Context): Type = + if (typeParams.nonEmpty) appliedTo(args) else self + /** A cycle-safe version of `appliedTo` where computing type parameters do not force * the typeconstructor. Instead, if the type constructor is completing, we make * up hk type parameters matching the arguments. This is needed when unpickling @@ -733,7 +762,7 @@ class TypeApplications(val self: Type) extends AnyVal { if (Config.newHK) self match { case self: TypeRef if !self.symbol.isClass && self.symbol.isCompleting => - AppliedType(self, args) + HKApply(self, args) case _ => appliedTo(args, typeParams) } diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 566865eb4..9449787c1 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -390,40 +390,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { isSubType(fixRecs(tp1stable, tp1stable.widenExpr), tp2.parent.substRecThis(tp2, tp1stable)) } case tp2 @ HKApply(tycon2, args2) => - def compareHkApply(tycon2: Type): Boolean = tycon2 match { - case tycon2: TypeVar => compareHkApply(tycon2.underlying) - case param2: PolyParam if canConstrain(param2) => - val tparams2 = tycon2.typeParams - - def tyconOK(tycon1a: Type) = - variancesConform(tycon1a.typeParams, tparams2) && { - if (ctx.mode.is(Mode.TypevarsMissContext)) isSubType(tp1, tycon1a.appliedTo(args2)) - else tryInstantiate(param2, tycon1a) && isSubType(tp1, tp2) - } - - tp1 match { - case tp1 @ HKApply(tycon1, _) => - tyconOK(tycon1) || isSubType(tp1.upperBound, tp2) - case _ if tp1.widenDealias.typeSymbol.isClass => - val classBounds = tp2.classSymbols - def liftToBase(bcs: List[ClassSymbol]): Boolean = bcs match { - case bc :: bcs1 => - classBounds.exists(bc.derivesFrom) && tyconOK(tp1.baseTypeRef(bc)) || - liftToBase(bcs1) - case _ => - false - } - liftToBase(tp1.baseClasses) - case tp1: TypeProxy => - isSubType(tp1.underlying, tp2) - case _ => - false - } - case _ => - // TODO handle lower bounds of hk params here - false - } - compareHkApply(tycon2) || fourthTry(tp1, tp2) + compareHkApply2(tp1, tp2, tycon2, args2) case tp2 @ TypeLambda(tparams2, body2) => def compareHkLambda = tp1.stripTypeVar match { case tp1 @ TypeLambda(tparams1, body1) => @@ -452,7 +419,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { return isSubType(tp1, OrType(tp21, tp221)) && isSubType(tp1, OrType(tp21, tp222)) case _ => } - eitherIsSubType(tp1, tp21, tp1, tp22) || fourthTry(tp1, tp2) + either(isSubType(tp1, tp21), isSubType(tp1, tp22)) || fourthTry(tp1, tp2) case tp2 @ MethodType(_, formals2) => def compareMethod = tp1 match { case tp1 @ MethodType(_, formals1) => @@ -555,14 +522,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp1: RecType => isNewSubType(tp1.parent, tp2) case HKApply(tycon1, args1) => - tp2 match { - case AppliedType(tycon2, args2) => - assert(!tycon2.isHK) // this should have been handled by thirdTry - isSubType(tycon1, EtaExpansion(tycon2)) && - isSubArgs(args1, args2, tycon2.typeParams) - case _ => - false - } + compareHkApply1(tp1, tycon1, args1, tp2) case EtaExpansion(tycon1) => isSubType(tycon1, tp2) case AndType(tp11, tp12) => @@ -581,7 +541,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { return isSubType(AndType(tp11, tp121), tp2) && isSubType(AndType(tp11, tp122), tp2) case _ => } - eitherIsSubType(tp11, tp2, tp12, tp2) + either(isSubType(tp11, tp2), isSubType(tp12, tp2)) case JavaArrayType(elem1) => def compareJavaArray = tp2 match { case JavaArrayType(elem2) => isSubType(elem1, elem2) @@ -595,6 +555,128 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { false } + /** Subtype test for the hk application `tp2 = tycon2[args2]`. + */ + def compareHkApply2(tp1: Type, tp2: Type, tycon2: Type, args2: List[Type]): Boolean = { + val tparams = tycon2.typeParams + + def isMatchingApply(tp1: Type): Boolean = tp1 match { + case HKApply(tycon1, args1) => + tycon1 match { + case tycon1: PolyParam => + (tycon1 == tycon2 || + canConstrain(tycon1) && tryInstantiate(tycon1, tycon2)) && + isSubArgs(args1, args2, tparams) + case tycon1: TypeRef => + tycon2 match { + case tycon2: TypeRef if tycon1.symbol == tycon2.symbol => + isSubType(tycon1.prefix, tycon2.prefix) && + isSubArgs(args1, args2, tparams) + case _ => + false + } + case tycon1: TypeVar => + isMatchingApply(tycon1.underlying) + case tycon1: AnnotatedType => + isMatchingApply(tycon1.underlying) + case _ => + false + } + case _ => + 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 + * 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`. + */ + def tyconOK(tycon1a: Type) = + variancesConform(tycon1a.typeParams, tparams) && { + (ctx.mode.is(Mode.TypevarsMissContext) || + tryInstantiate(param2, tycon1a.ensureHK)) && + isSubType(tp1, tycon1a.appliedTo(args2)) + } + + tp1.widen match { + case tp1w @ HKApply(tycon1, _) => + tyconOK(tycon1) + 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)) || + liftToBase(bcs1) + case _ => + false + } + liftToBase(tp1w.baseClasses) + } || + fourthTry(tp1, tp2) + } + } + + /** Let `tycon2bounds` be the bounds of the RHS type constructor `tycon2`. + * Let `app2 = tp2` where the type constructor of `tp2` is replaced by + * `tycon2bounds.lo`. + * If both bounds are the same, continue with `tp1 <:< app2`. + * otherwise continue with either + * + * tp1 <:< tp2 using fourthTry (this might instantiate params in tp1) + * tp1 <:< app2 using isSubType (this might instantiate params in tp2) + */ + def compareLower(tycon2bounds: TypeBounds): Boolean = { + val app2 = tycon2bounds.lo.applyIfParameterized(args2) + if (tycon2bounds.lo eq tycon2bounds.hi) isSubType(tp1, app2) + else either(fourthTry(tp1, tp2), isSubType(tp1, app2)) + } + + tycon2 match { + case param2: PolyParam => + isMatchingApply(tp1) || { + if (canConstrain(param2)) canInstantiate(param2) + else compareLower(bounds(param2)) + } + case tycon2: TypeRef => + isMatchingApply(tp1) || + compareLower(tycon2.info.bounds) + case tycon2: TypeVar => + isSubType(tp1, tycon2.underlying.appliedTo(args2)) + case tycon2: AnnotatedType => + compareHkApply2(tp1, tp2, tycon2.underlying, args2) + case _ => + false + } + } + + /** Subtype test for the hk application `tp1 = tycon1[args1]`. + */ + def compareHkApply1(tp1: Type, tycon1: Type, args1: List[Type], tp2: Type): Boolean = + tycon1 match { + case param1: PolyParam => + def canInstantiate = tp2 match { + case AppliedType(tycon2, args2) => + tryInstantiate(param1, tycon2.ensureHK) && isSubArgs(args1, args2, tycon2.typeParams) + case _ => + false + } + canConstrain(param1) && canInstantiate || + isSubType(bounds(param1).hi.applyIfParameterized(args1), tp2) + case tycon1: TypeProxy => + isSubType(tycon1.underlying.applyIfParameterized(args1), tp2) + case _ => + false + } + + /** Subtype test for corresponding arguments in `args1`, `args2` according to + * variances in type parameters `tparams`. + */ def isSubArgs(args1: List[Type], args2: List[Type], tparams: List[MemberBinding]): Boolean = if (args1.isEmpty) args2.isEmpty else args2.nonEmpty && { @@ -678,7 +760,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { val hkTypeParams = param.typeParams subtyping.println(i"classBounds = ${app.classSymbols}") subtyping.println(i"base classes = ${other.baseClasses}") - subtyping.println(i"type params = $hkTypeParams") + subtyping.println(i"type params = $hkTypeParams, ${app.classSymbol}") if (inOrder) unifyWith(other) else testLifted(other, app, hkTypeParams, unifyWith) case _ => @@ -775,8 +857,9 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { /** The symbol referred to in the refinement of `rt` */ private def refinedSymbol(rt: RefinedType) = rt.parent.member(rt.refinedName).symbol - /** Returns true iff either `tp11 <:< tp21` or `tp12 <:< tp22`, trying at the same time - * to keep the constraint as wide as possible. Specifically, if + /** Returns true iff the result of evaluating either `op1` or `op2` is true, + * trying at the same time to keep the constraint as wide as possible. + * E.g, if * * tp11 <:< tp12 = true with post-constraint c1 * tp12 <:< tp22 = true with post-constraint c2 @@ -803,15 +886,15 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { * Here, each precondition leads to a different constraint, and neither of * the two post-constraints subsumes the other. */ - private def eitherIsSubType(tp11: Type, tp21: Type, tp12: Type, tp22: Type) = { + private def either(op1: => Boolean, op2: => Boolean): Boolean = { val preConstraint = constraint - isSubType(tp11, tp21) && { + op1 && { val leftConstraint = constraint constraint = preConstraint - if (!(isSubType(tp12, tp22) && subsumes(leftConstraint, constraint, preConstraint))) + if (!(op2 && subsumes(leftConstraint, constraint, preConstraint))) constraint = leftConstraint true - } || isSubType(tp12, tp22) + } || op2 } /** Like tp1 <:< tp2, but returns false immediately if we know that @@ -1533,12 +1616,23 @@ class ExplainingTypeComparer(initctx: Context) extends TypeComparer(initctx) { } override def addConstraint(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = - traceIndented(s"add constraint $param ${if (fromBelow) ">:" else "<:"} $bound $frozenConstraint") { + traceIndented(i"add constraint $param ${if (fromBelow) ">:" else "<:"} $bound $frozenConstraint") { super.addConstraint(param, bound, fromBelow) } override def copyIn(ctx: Context) = new ExplainingTypeComparer(ctx) + override def compareHkApply2(tp1: Type, tp2: Type, tycon2: Type, args2: List[Type]): Boolean = { + def addendum = tycon2 match { + case param2: PolyParam => + i": it's a polyparam with entry ${ctx.typerState.constraint.entry(param2)}" + case _ => + } + traceIndented(i"compareHkApply $tp1, $tp2, $addendum") { + super.compareHkApply2(tp1, tp2, tycon2, args2) + } + } + override def compareHkApplyOLD(app: RefinedType, other: Type, inOrder: Boolean) = if (app.isHKApplyOLD) traceIndented(i"compareHkApply $app, $other, $inOrder, ${app.normalizeHkApplyOLD}") { diff --git a/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala b/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala index 18a4e83b6..aa660f73e 100644 --- a/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala +++ b/src/dotty/tools/dotc/core/unpickleScala2/Scala2Unpickler.scala @@ -632,6 +632,14 @@ class Scala2Unpickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClas case info => tp.derivedRefinedType(parent1, name, info) } + case tp @ HKApply(tycon, args) => + val tycon1 = tycon.safeDealias + def mapArg(arg: Type) = arg match { + case arg: TypeRef if isBound(arg) => arg.symbol.info + case _ => arg + } + if (tycon1 ne tycon) elim(tycon1.appliedTo(args)) + else tp.derivedAppliedType(tycon, args.map(mapArg)) case _ => tp } |