From 7f721438b5bccc8ca9dd68cef273c8cac8199e1a Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 18 Jun 2014 18:20:14 +0200 Subject: Handling higher-kinded types with lambdas Switch to the new scheme where higher-kinded types (and also some polymorphic type aliases) are represented as instances of Lambda traits. --- src/dotty/tools/dotc/core/Definitions.scala | 55 ----- src/dotty/tools/dotc/core/NameOps.scala | 18 +- src/dotty/tools/dotc/core/StdNames.scala | 6 +- src/dotty/tools/dotc/core/TypeApplications.scala | 222 +++++++++++++-------- src/dotty/tools/dotc/core/TypeComparer.scala | 156 ++++++--------- src/dotty/tools/dotc/core/Types.scala | 80 ++------ src/dotty/tools/dotc/core/pickling/UnPickler.scala | 10 +- src/dotty/tools/dotc/typer/Applications.scala | 11 +- src/dotty/tools/dotc/typer/Namer.scala | 29 +-- 9 files changed, 258 insertions(+), 329 deletions(-) (limited to 'src/dotty/tools') diff --git a/src/dotty/tools/dotc/core/Definitions.scala b/src/dotty/tools/dotc/core/Definitions.scala index 08588818f..bd323bab5 100644 --- a/src/dotty/tools/dotc/core/Definitions.scala +++ b/src/dotty/tools/dotc/core/Definitions.scala @@ -424,61 +424,6 @@ class Definitions { def functionArity(tp: Type) = tp.dealias.argInfos.length - 1 - // ----- Higher kinds machinery ------------------------------------------ - // tbr - private var _hkTraits: Set[Symbol] = Set() - - /** The set of HigherKindedXYZ traits encountered so far */ - def hkTraits: Set[Symbol] = _hkTraits - - private var hkTraitOfArity = mutable.Map[List[Int], ClassSymbol]() - - /** The HigherKinded trait corresponding to symbols `boundSyms` (which are assumed - * to be the type parameters of a higher-kided type). This is a class symbol that - * would be generated by the following schema. - * - * class HigherKindedXYZ { type v_n _$hk$0; ...; type v_n _$Hk$n } - * - * Here: - * - * - XYZ is a string with one letter for each variant of a bound symbols, - * using `P` (positive variance), `N` (negative variance), `I` (invariant). - * - v_i are the variances of the bound symbols (i.e. +, -, or empty). - * - _$hk$i are higher-kinded parameter names, which are specially treated in type application. - */ - def hkTrait(vcs: List[Int]) = { - - def varianceFlags(v: Int) = v match { - case -1 => Contravariant - case 0 => Covariant - case 1 => EmptyFlags - } - - val completer = new LazyType { - def complete(denot: SymDenotation)(implicit ctx: Context): Unit = { - val cls = denot.asClass.classSymbol - val paramDecls = newScope - 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) - - def createTrait = { - val cls = newClassSymbol( - ScalaPackageClass, - traitName, - Trait | Interface | Synthetic, - completer) - _hkTraits += cls - cls - } - - hkTraitOfArity.getOrElseUpdate(vcs, createTrait) - } - // ----- LambdaXYZ traits ------------------------------------------ private var myLambdaTraits: Set[Symbol] = Set() diff --git a/src/dotty/tools/dotc/core/NameOps.scala b/src/dotty/tools/dotc/core/NameOps.scala index 187946590..55354cc17 100644 --- a/src/dotty/tools/dotc/core/NameOps.scala +++ b/src/dotty/tools/dotc/core/NameOps.scala @@ -88,14 +88,13 @@ object NameOps { } /** Is this the name of a higher-kinded type parameter of a Lambda? */ - def isLambdaArgName = name.startsWith(tpnme.LAMBDA_ARG_PREFIX) - def isHkParamName: Boolean = name(0) == '_' && name.startsWith(HK_PARAM_PREFIX) // tbr + def isLambdaArgName = + name(0) == tpnme.LAMBDA_ARG_PREFIXhead && name.startsWith(tpnme.LAMBDA_ARG_PREFIX) /** The index of the higher-kinded type parameter with this name. * Pre: isLambdaArgName. */ def lambdaArgIndex: Int = name.drop(name.lastIndexOf('$') + 1).toString.toInt - def hkParamIndex: Int = name.drop(name.lastIndexOf('$') + 1).toString.toInt // tbr /** If the name ends with $nn where nn are * all digits, strip the $ and the digits. @@ -179,19 +178,6 @@ 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] = { // tbr - 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) - } - /** The name of the generic runtime operation corresponding to an array operation */ def genericArrayOp: TermName = name match { case nme.apply => nme.array_apply diff --git a/src/dotty/tools/dotc/core/StdNames.scala b/src/dotty/tools/dotc/core/StdNames.scala index 3b1cb63f1..3ab0ec36e 100644 --- a/src/dotty/tools/dotc/core/StdNames.scala +++ b/src/dotty/tools/dotc/core/StdNames.scala @@ -167,6 +167,7 @@ object StdNames { final val REIFY_TREECREATOR_PREFIX: N = "$treecreator" final val REIFY_TYPECREATOR_PREFIX: N = "$typecreator" final val LAMBDA_ARG_PREFIX: N = "$hkArg$" + final val LAMBDA_ARG_PREFIXhead: Char = LAMBDA_ARG_PREFIX.head final val Any: N = "Any" final val AnyVal: N = "AnyVal" @@ -250,8 +251,6 @@ object StdNames { val SKOLEM: N = "" val SPECIALIZED_INSTANCE: N = "specInstance$" val THIS: N = "_$this" - val HK_PARAM_PREFIX: N = "_$hk$" // tbr - val HK_TRAIT_PREFIX: N = "$HigherKinded$" // tbr final val Nil: N = "Nil" final val Predef: N = "Predef" @@ -647,9 +646,6 @@ object StdNames { def syntheticTypeParamNames(num: Int): List[TypeName] = (0 until num).map(syntheticTypeParamName)(breakOut) - def higherKindedTraitName(vcs: List[Int]): TypeName = HK_TRAIT_PREFIX ++ vcs.map(varianceSuffix).mkString // tbr - def higherKindedParamName(n: Int) = HK_PARAM_PREFIX ++ n.toString //tbr - def lambdaTraitName(vcs: List[Int]): TypeName = LambdaPrefix ++ vcs.map(varianceSuffix).mkString def lambdaArgName(n: Int) = LAMBDA_ARG_PREFIX ++ n.toString diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala index 428178b81..9411ed004 100644 --- a/src/dotty/tools/dotc/core/TypeApplications.scala +++ b/src/dotty/tools/dotc/core/TypeApplications.scala @@ -46,13 +46,12 @@ class TypeApplications(val self: Type) extends AnyVal { /** The type parameters of this type are: * For a ClassInfo type, the type parameters of its class. * For a typeref referring to a class, the type parameters of the class. - * For a typeref referring to an alias type, the type parameters of the aliased type. - * For a typeref referring to an abstract type with a HigherKindedXYZ bound, the - * type parameters of the HigherKinded class. + * For a typeref referring to an alias or abstract type, the type parameters of + * its right hand side or upper bound. * For a refinement type, the type parameters of its parent, unless there's a - * refinement with the same name. Inherited by all other type proxies. - * For an intersection type A & B, the type parameters of its left operand, A. - * Empty list for all other types. + * refinement with the same name. + * For any other non-singleton type proxy, the type parameters of its underlying type. + * For any other type, the empty list. */ final def typeParams(implicit ctx: Context): List[TypeSymbol] = /*>|>*/ track("typeParams") /*<|<*/ { self match { @@ -61,56 +60,50 @@ class TypeApplications(val self: Type) extends AnyVal { case tp: TypeRef => val tsym = tp.typeSymbol if (tsym.isClass) tsym.typeParams - else if (tsym.info.isAlias) tp.underlying.typeParams - else tp.info.bounds.hi match { - case AndType(hkBound, other) if defn.hkTraits contains hkBound.typeSymbol => - hkBound.typeSymbol.typeParams - case _ => - Nil - } + else tp.underlying.typeParams case tp: RefinedType => - tp.parent.typeParams filterNot (_.name == tp.refinedName) + val tparams = tp.parent.typeParams + tp.refinedInfo match { + case TypeBounds(lo, hi) if lo eq hi => tparams.filterNot(_.name == tp.refinedName) + case _ => tparams + } + case tp: SingletonType => + Nil case tp: TypeProxy => tp.underlying.typeParams - case tp: AndType => - tp.tp1.typeParams case _ => Nil } } + /** 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 higher-kinded type parameters. + * Third, it won't return higher-kinded type parameters, i.e. the type parameters of + * an abstract type are always empty. */ - final def safeUnderlyingTypeParams(implicit ctx: Context): List[TypeSymbol] = { - def ifCompleted(sym: Symbol): Symbol = if (sym.isCompleted) sym else NoSymbol + final def rawTypeParams(implicit ctx: Context): List[TypeSymbol] = { self match { case tp: ClassInfo => tp.cls.typeParams case tp: TypeRef => val tsym = tp.typeSymbol if (tsym.isClass) tsym.typeParams - else if (tsym.isAliasType) tp.underlying.safeUnderlyingTypeParams + else if (tsym.isAliasType) tp.underlying.rawTypeParams else Nil - case tp: BoundType => + case _: BoundType | _: SingletonType => Nil case tp: TypeProxy => - tp.underlying.safeUnderlyingTypeParams - case tp: AndType => - tp.tp1.safeUnderlyingTypeParams + tp.underlying.rawTypeParams case _ => Nil } } - def uninstantiatedTypeParams(implicit ctx: Context): List[TypeSymbol] = - typeParams filter (tparam => self.member(tparam.name).symbol == tparam) - - /** If type `tp` is equal, aliased-to, or upperbounded-by a type of the form + /** If type `tp` is equal, aliased-to, or upperbounded-by a type of the form * `LambdaXYZ { ... }`, the class symbol of that type, otherwise NoSymbol. * @param forcing if set, might force completion. If not, never forces * but returns NoSymbol when it would have to otherwise. @@ -143,11 +136,10 @@ class TypeApplications(val self: Type) extends AnyVal { /** Is type `tp` a Lambda with all Arg$ fields fully instantiated? */ def isInstantiatedLambda(tp: Type)(implicit ctx: Context): Boolean = - tp.isSafeLambda && tp.typeParams.forall(_.name == tpnme.Apply) + tp.isSafeLambda && tp.typeParams.isEmpty /** 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) { @@ -155,7 +147,11 @@ class TypeApplications(val self: Type) extends AnyVal { println(s"precomplete decls = ${self.typeSymbol.decls.toList.map(_.denot).mkString("\n ")}") } val tparam = tparams.head - val tp1 = RefinedType(tp, tparam.name, arg.toBounds(tparam)) + val arg1 = + if ((tparam is HigherKinded) && !arg.isLambda && arg.typeParams.nonEmpty) + arg.EtaExpand + else arg + val tp1 = RefinedType(tp, tparam.name, arg1.toBounds(tparam)) matchParams(tp1, tparams.tail, args1) case nil => tp } @@ -174,8 +170,8 @@ class TypeApplications(val self: Type) extends AnyVal { val safeTypeParams = if (tsym.isClass || !tp.typeSymbol.isCompleting) original.typeParams else { - ctx.warning("encountered F-bounded higher-kinded type parameters; assuming they are invariant") - defn.hkTrait(args map alwaysZero).typeParams + ctx.warning(i"encountered F-bounded higher-kinded type parameters for $tsym; assuming they are invariant") + defn.lambdaTrait(args map alwaysZero).typeParams } matchParams(tp, safeTypeParams, args) } @@ -186,8 +182,6 @@ class TypeApplications(val self: Type) extends AnyVal { tp.refinedInfo) case tp: TypeProxy => instantiate(tp.underlying, original) - case AndType(l, r) => - l.appliedTo(args) & r case tp: PolyType => tp.instantiate(args) case ErrorType => @@ -195,7 +189,10 @@ class TypeApplications(val self: Type) extends AnyVal { } if (args.isEmpty || !canHaveTypeParams) self - else instantiate(self, self) + else { + val res = instantiate(self, self) + if (isInstantiatedLambda(res)) res.select(tpnme.Apply) else res + } } final def appliedTo(arg: Type)(implicit ctx: Context): Type = appliedTo(arg :: Nil) @@ -363,12 +360,11 @@ class TypeApplications(val self: Type) extends AnyVal { * * type T = RHS * - * It is required that `C` is a class and that every bound symbol in `boundSyms` appears - * as an argument in `targs`. If these requirements are not met an error is - * signalled by calling the parameter `error`. - * - * The rewriting replaces bound symbols by references to the - * parameters of class C. Example: + * There are two strategies how this is achieved. + + * 1st strategy: Applies if `C` is a class such that every bound symbol in `boundSyms` + * appears as an argument in `targs`, and in the same order. Then the rewriting replaces + * bound symbols by references to the parameters of class C. Example: * * Say we have: * @@ -380,48 +376,114 @@ class TypeApplications(val self: Type) extends AnyVal { * * type A = Triple { type T1 = (this.T2, this.T2); type T3 = String } * - * If the RHS is an intersection type A & B, we Lambda abstract on A instead and - * then recombine with & B. + * 2nd strategy: Used as a fallback if 1st strategy does not apply. It rewrites + * the RHS to a typed lambda abstraction. */ - def LambdaAbstract(boundSyms: List[Symbol])(error: (String, Position) => Unit)(implicit ctx: Context): Type = self match { - case AndType(l, r) => - AndType(l.LambdaAbstract(boundSyms)(error), r) - case _ => - val cls = self.typeSymbol - if (!cls.isClass) - error("right-hand side of parameterized alias type must refer to a class", cls.pos) - - val correspondingParamName: Map[Symbol, TypeName] = { - for { - (tparam, targ: TypeRef) <- cls.typeParams zip argInfos - if boundSyms contains targ.symbol - } yield targ.symbol -> tparam.name - }.toMap - - val correspondingNames = correspondingParamName.values.toSet - - def replacements(rt: RefinedType): List[Type] = - for (sym <- boundSyms) yield { - correspondingParamName get sym match { - case Some(name) => - TypeRef(RefinedThis(rt), name) - case None => - error(s"parameter $sym of type alias does not appear as type argument of the aliased $cls", sym.pos) - defn.AnyType - } + def parameterizeWith(boundSyms: List[Symbol])(implicit ctx: Context): Type = { + def matchParams(bsyms: List[Symbol], tparams: List[Symbol], targs: List[Type], + correspondingParamName: Map[Symbol, TypeName]): Type = { + if (bsyms.isEmpty) { + val correspondingNames = correspondingParamName.values.toSet + + def replacements(rt: RefinedType): List[Type] = + for (sym <- boundSyms) + yield TypeRef(RefinedThis(rt), correspondingParamName(sym)) + + def rewrite(tp: Type): Type = tp match { + case tp @ RefinedType(parent, name: TypeName) => + if (correspondingNames contains name) rewrite(parent) + else RefinedType( + rewrite(parent), + name, + rt => tp.refinedInfo.subst(boundSyms, replacements(rt))) + case tp => + tp } - def rewrite(tp: Type): Type = tp match { - case tp @ RefinedType(parent, name: TypeName) => - if (correspondingNames contains name) rewrite(parent) - else RefinedType( - rewrite(parent), - name, - rt => tp.refinedInfo.subst(boundSyms, replacements(rt))) - case tp => - tp + rewrite(self) + } + else if (tparams.isEmpty || targs.isEmpty) + LambdaAbstract(boundSyms) + else if (bsyms.head == targs.head.typeSymbol) + matchParams(bsyms.tail, tparams.tail, targs.tail, + correspondingParamName + (bsyms.head -> tparams.head.name.asTypeName)) + else + matchParams(bsyms, tparams.tail, targs.tail, correspondingParamName) + } + val cls = self.typeSymbol + if (cls.isClass) matchParams(boundSyms, cls.typeParams, argInfos, Map()) + else LambdaAbstract(boundSyms) + } + + /** The typed lambda abstraction of this type `T` relative to `boundSyms`. + * This is: + * + * LambdaXYZ{ type Apply = subst(T) } + * + * where XYZ reflets that variances of the bound symbols and + * `subst` is a substitution that replaces every bound symbol sym_i by + * `this.Arg$i`. + * + * TypeBounds are lambda abstracting by lambda abstracting their upper bound. + */ + def LambdaAbstract(boundSyms: List[Symbol])(implicit ctx: Context): Type = { + def expand(tp: Type) = { + val lambda = defn.lambdaTrait(boundSyms.map(_.variance)) + val substitutedRHS = (rt: RefinedType) => { + val argRefs = boundSyms.indices.toList.map(i => + RefinedThis(rt).select(tpnme.lambdaArgName(i))) + tp.bounds.subst(boundSyms, argRefs) } + val res = RefinedType(lambda.typeRef, tpnme.Apply, substitutedRHS) + //println(i"lambda abstract $self wrt $boundSyms%, % --> $res") + res + } + self match { + case self @ TypeBounds(lo, hi) => + self.derivedTypeBounds(lo, expand(TypeBounds.upper(hi))) + case _ => + expand(self) + } + } - rewrite(self) + /** Convert a type constructor `TC` with type parameters `T1, ..., Tn` to + * + * LambdaXYZ { Apply = TC[$hkArg$0, ..., $hkArg$n] } + * + * where XYZ is a corresponds to the variances of the type parameters. + */ + def EtaExpand(implicit ctx: Context): Type = { + val tparams = typeParams + self.appliedTo(tparams map (_.typeRef)).LambdaAbstract(tparams) + } + + /** If this type has a base type `B[T1, ..., Tn]` where the type parameters + * of `B` match one-by-one the variances of `tparams`, convert it to + * + * LambdaXYZ { type Apply = B[$hkArg$0, ..., $hkArg$n] } + * { type $hkArg$0 = T1; ...; type $hkArg$n = Tn } + * + * A type parameter matches a varianve V if it has V as its variance or if V == 0. + */ + def EtaLiftTo(tparams: List[Symbol])(implicit ctx: Context): Type = { + def tryLift(bcs: List[ClassSymbol]): Type = bcs match { + case bc :: bcs1 => + val tp = self.baseTypeWithArgs(bc) + val targs = tp.argInfos + val tycon = tp.withoutArgs(targs) + def variancesMatch(param1: Symbol, param2: Symbol) = + param2.variance == param2.variance || param2.variance == 0 + if ((tycon.typeParams corresponds tparams)(variancesMatch)) { + val expanded = tycon.EtaExpand + val res = (expanded /: targs)((partialInst, arg) => + RefinedType(partialInst, partialInst.typeParams.head.name, arg.bounds)) + hk.println(i"eta lifting $self --> $res") + res + } + else tryLift(bcs1) + case nil => + NoType + } + if (tparams.isEmpty) NoType else tryLift(self.baseClasses) } } \ No newline at end of file diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 30e243aca..de03ad6e4 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -438,26 +438,52 @@ class TypeComparer(initctx: Context) extends DotClass { def firstTry(tp1: Type, tp2: Type): Boolean = { tp2 match { case tp2: NamedType => + // We treat two prefixes A.this, B.this as equivalent if + // A's selftype derives from B and B's selftype derives from A. + def equivalentThisTypes(tp1: Type, tp2: Type) = tp1 match { + case ThisType(cls1) => + tp2 match { + case ThisType(cls2) => + cls1.classInfo.selfType.derivesFrom(cls2) && + cls2.classInfo.selfType.derivesFrom(cls1) + case _ => false + } + case _ => false + } + def isHKSubType = { + val lambda2 = tp2.prefix.LambdaClass(forcing = true) + lambda2.exists && isSubType(tp1.EtaLiftTo(lambda2.typeParams), tp2.prefix) + } def compareNamed = { implicit val ctx: Context = this.ctx // Dotty deviation: implicits need explicit type tp1 match { case tp1: NamedType => val sym1 = tp1.symbol (if (sym1 eq tp2.symbol) ( - ctx.erasedTypes + ctx.erasedTypes || sym1.isStaticOwner - || { - val pre1 = tp1.prefix - val pre2 = tp2.prefix - isSubType(pre1, pre2) || - pre1.isInstanceOf[ThisType] && pre2.isInstanceOf[ThisType] - }) - else - (tp1.name eq tp2.name) && isSubType(tp1.prefix, tp2.prefix)) || secondTryNamed(tp1, tp2) + || { // Implements: A # X <: B # X + // if either A =:= B (i.e. A <: B and B <: A), or the following three conditions hold: + // 1. X is a class type, + // 2. B is a class type without abstract type members. + // 3. A <: B. + // Dealiasing is taken care of elsewhere. + val pre1 = tp1.prefix + val pre2 = tp2.prefix + ( isSameType(pre1, pre2) + || equivalentThisTypes(pre1, pre2) + || sym1.isClass + && pre2.classSymbol.exists + && pre2.abstractTypeMembers.isEmpty + ) + } + ) + else (tp1.name eq tp2.name) && isSameType(tp1.prefix, tp2.prefix) + ) || secondTryNamed(tp1, tp2) case ThisType(cls) if cls eq tp2.symbol.moduleClass => isSubType(cls.owner.thisType, tp2.prefix) case _ => - secondTry(tp1, tp2) + tp2.name == tpnme.Apply && isHKSubType || secondTry(tp1, tp2) } } compareNamed @@ -599,8 +625,7 @@ class TypeComparer(initctx: Context) extends DotClass { compareNamed case tp2 @ RefinedType(parent2, name2) => def compareRefined: Boolean = tp1.widen match { - case tp1 @ RefinedType(parent1, name1) - if nameMatches(name1, name2, tp1, tp2) => + case tp1 @ RefinedType(parent1, name1) if name1 == name2 && name1.isTypeName => // optimized case; all info on tp1.name1 is in refinement tp1.refinedInfo. isSubType(normalizedInfo(tp1), tp2.refinedInfo) && { val saved = pendingRefinedBases @@ -627,12 +652,6 @@ class TypeComparer(initctx: Context) extends DotClass { case _ => false } } - || - name.isHkParamName && { - val idx = name.hkParamIndex - val tparams = tp1.typeParams - idx < tparams.length && hasMatchingMember(tparams(idx).name) - } ) } val matchesParent = { @@ -643,10 +662,13 @@ class TypeComparer(initctx: Context) extends DotClass { } finally pendingRefinedBases = saved } - matchesParent && ( - name2 == nme.WILDCARD - || hasMatchingMember(name2) - || fourthTry(tp1, tp2)) + ( matchesParent && ( + name2 == nme.WILDCARD + || hasMatchingMember(name2) + || fourthTry(tp1, tp2) + ) + || needsEtaLift(tp1, tp2) && isSubType(tp1.EtaLiftTo(tp2.typeParams), tp2) + ) } compareRefined case OrType(tp21, tp22) => @@ -734,12 +756,13 @@ class TypeComparer(initctx: Context) extends DotClass { } } case tp1: RefinedType => - val saved = pendingRefinedBases - try { - addPendingName(tp1.refinedName, tp1, tp1) - isNewSubType(tp1.parent, tp2) - } - finally pendingRefinedBases = saved + { val saved = pendingRefinedBases + try { + addPendingName(tp1.refinedName, tp1, tp1) + isNewSubType(tp1.parent, tp2) + } + finally pendingRefinedBases = saved + } || needsEtaLift(tp2, tp1) && isSubType(tp1, tp2.EtaLiftTo(tp1.typeParams)) case AndType(tp11, tp12) => isNewSubType(tp11, tp2) || isNewSubType(tp12, tp2) case _ => @@ -747,7 +770,7 @@ class TypeComparer(initctx: Context) extends DotClass { } /** Like tp1 <:< tp2, but returns false immediately if we know that - * the case was covered previouslky during subtyping. + * the case was covered previously during subtyping. */ private def isNewSubType(tp1: Type, tp2: Type): Boolean = if (isCovered(tp1) && isCovered(tp2)) { @@ -781,30 +804,6 @@ class TypeComparer(initctx: Context) extends DotClass { case _ => proto.isMatchedBy(tp) } - /** Tow refinement names match if they are the same or one is the - * name of a type parameter of its parent type, and the other is - * the corresponding higher-kinded parameter name - */ - private def nameMatches(name1: Name, name2: Name, tp1: Type, tp2: Type) = - name1.isTypeName && - (name1 == name2 || isHKAlias(name1, name2, tp2) || isHKAlias(name2, name1, tp1)) - - /** Is name1 a higher-kinded parameter name and name2 a corresponding - * type parameter name? - */ - private def isHKAlias(name1: Name, name2: Name, tp2: Type) = - name1.isHkParamName && { - val i = name1.hkParamIndex - val tparams = tp2.safeUnderlyingTypeParams - i < tparams.length && tparams(i).name == name2 - } - - /** Is type `tp` a TypeRef referring to a higher-kinded parameter? */ - private def isHKRef(tp: Type) = tp match { - case TypeRef(_, name) => name.isHkParamName - case _ => false - } - /** Can type `tp` be constrained from above by adding a constraint to * a typevar that it refers to? In that case we have to be careful not * to approximate with the lower bound of a type in `thirdTry`. Instead, @@ -818,38 +817,11 @@ class TypeComparer(initctx: Context) extends DotClass { case _ => false } - /** Is `tp1` a subtype of a type `tp2` of the form - * `scala.HigerKindedXYZ { ... }? - * 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 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 = ctx.traceIndented(s"isSubTypeHK(${tp1.show}, ${tp2.show}", subtyping) { - 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 hkBounds = tp2.argInfos.map(_.asInstanceOf[TypeBounds]) - val boundsOK = (hkBounds corresponds args1)(_ contains _) - val variancesOK = - argInfos1.nonEmpty || (tparams corresponds tp2.typeSymbol.name.hkVariances) { (tparam, v) => - v == 0 || tparam.variance == v - } - hk.println(s"isSubTypeHK: args1 = $args1, hk-bounds = $hkBounds $boundsOK $variancesOK") - boundsOK && variancesOK || fourthTry(tp1, tp2) + /** Does `tp` need to be eta lifted to be comparable to `target`? */ + def needsEtaLift(tp: Type, target: RefinedType) = { + val name = target.refinedName + (name.isLambdaArgName || (name eq tpnme.Apply)) && target.isLambda && + tp.exists && !tp.isLambda } def trySetType(tr: NamedType, bounds: TypeBounds): Boolean = @@ -1093,9 +1065,10 @@ class TypeComparer(initctx: Context) extends DotClass { val t2 = distributeAnd(tp2, tp1) if (t2.exists) t2 else { - if (isHKRef(tp1)) tp2 - else if (isHKRef(tp2)) tp1 - else AndType(tp1, tp2) + //if (isHKRef(tp1)) tp2 + //else if (isHKRef(tp2)) tp1 + //else + AndType(tp1, tp2) } } } @@ -1117,9 +1090,10 @@ class TypeComparer(initctx: Context) extends DotClass { val t2 = distributeOr(tp2, tp1) if (t2.exists) t2 else { - if (isHKRef(tp1)) tp1 - else if (isHKRef(tp2)) tp2 - else OrType(tp1, tp2) + //if (isHKRef(tp1)) tp1 + //else if (isHKRef(tp2)) tp2 + //else + OrType(tp1, tp2) } } } diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index a9bbde407..794f05319 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -164,15 +164,19 @@ object Types { case _ => false } - /** Is this type a transitive refinement of the given type or class symbol? + /** Is this type a transitive refinement of the given type? * This is true if the type consists of 0 or more refinements or other - * non-singleton proxies that lead to the `prefix` type, or, if - * `prefix` is a class symbol, lead to an instance type of this class. + * non-singleton proxies that lead to the `prefix` type. ClassInfos with + * the same class are counted as equal for this purpose. */ - def refines(prefix: AnyRef /* RefinedType | ClassSymbol */)(implicit ctx: Context): Boolean = + def refines(prefix: Type)(implicit ctx: Context): Boolean = (this eq prefix) || { this match { - case base: ClassInfo => base.cls eq prefix + case base: ClassInfo => + prefix match { + case prefix: ClassInfo => base.cls eq prefix.cls + case _ => false + } case base: SingletonType => false case base: TypeProxy => base.underlying refines prefix case _ => false @@ -502,7 +506,7 @@ object Types { } /** Is this type close enough to that type so that members - * with the two type would override each other? + * with the two type would override each other?d * This means: * - Either both types are polytypes with the same number of * type parameters and their result types match after renaming @@ -1466,26 +1470,15 @@ object Types { * is transformed to a refinement of the original type parameter if that one exists. */ def derivedRefinedType(parent: Type, refinedName: Name, refinedInfo: Type)(implicit ctx: Context): RefinedType = { - lazy val underlyingTypeParams = parent.safeUnderlyingTypeParams - lazy val originalTypeParam = underlyingTypeParams(refinedName.hkParamIndex) - - /** Use variance of newly instantiated type parameter rather than the old hk argument - */ - 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 - } + lazy val underlyingTypeParams = parent.rawTypeParams if ((parent eq this.parent) && (refinedName eq this.refinedName) && (refinedInfo eq this.refinedInfo)) this - else if ( refinedName.isHkParamName - // && { println(s"deriving $refinedName $parent $underlyingTypeParams"); true } - && refinedName.hkParamIndex < underlyingTypeParams.length - && originalTypeParam.name != refinedName) - derivedRefinedType(parent, originalTypeParam.name, - adjustedHKRefinedInfo(refinedInfo.bounds, underlyingTypeParams(refinedName.hkParamIndex))) + else if ( refinedName.isLambdaArgName + //&& { println(s"deriving $refinedName $parent $underlyingTypeParams"); true } + && refinedName.lambdaArgIndex < underlyingTypeParams.length + && !parent.isLambda) + derivedRefinedType(parent.EtaExpand, refinedName, refinedInfo) else RefinedType(parent, refinedName, rt => refinedInfo.substThis(this, RefinedThis(rt))) } @@ -2137,47 +2130,6 @@ object Types { /** If this type and that type have the same variance, this variance, otherwise 0 */ final def commonVariance(that: TypeBounds): Int = (this.variance + that.variance) / 2 - /** Given a the typebounds L..H of higher-kinded abstract type - * - * type T[boundSyms] >: L <: H - * - * produce its equivalent bounds L'..R that make no reference to the bound - * symbols on the left hand side. The idea is to rewrite the declaration to - * - * type T >: L' <: HigherKindedXYZ { type _$hk$i >: bL_i <: bH_i } & H' - * - * where - * - * - XYZ encodes the variants of the bound symbols using `P` (positive variance) - * `N` (negative variance), `I` (invariant). - * - bL_i is the lower bound of bound symbol #i under substitution `substBoundSyms` - * - bH_i is the upper bound of bound symbol #i under substitution `substBoundSyms` - * - `substBoundSyms` is the substitution that maps every bound symbol #i to the - * reference `._$hk$i`, where `` is the RefinedThis referring to the - * previous HigherKindedXYZ refined type. - * - L' = substBoundSyms(L), H' = substBoundSyms(H) - * - * Example: - * - * type T[X <: F[X]] <: Traversable[X, T] - * - * is rewritten to: - * - * type T <: HigherKindedP { type _$hk$0 <: F[$_hk$0] } & Traversable[._$hk$0, T] - * - * @see Definitions.hkTrait - */ - def higherKinded(boundSyms: List[Symbol])(implicit ctx: Context): TypeBounds = { - val parent = defn.hkTrait(boundSyms map (_.variance)).typeRef - val hkParamNames = boundSyms.indices.toList map tpnme.higherKindedParamName - def substBoundSyms(tp: Type)(rt: RefinedType): Type = - tp.subst(boundSyms, hkParamNames map (TypeRef(RefinedThis(rt), _))) - val hkParamInfoFns: List[RefinedType => Type] = - for (bsym <- boundSyms) yield substBoundSyms(bsym.info) _ - val hkBound = RefinedType.make(parent, hkParamNames, hkParamInfoFns).asInstanceOf[RefinedType] - TypeBounds(substBoundSyms(lo)(hkBound), AndType(hkBound, substBoundSyms(hi)(hkBound))) - } - override def toString = if (lo eq hi) s"TypeAlias($lo)" else s"TypeBounds($lo, $hi)" diff --git a/src/dotty/tools/dotc/core/pickling/UnPickler.scala b/src/dotty/tools/dotc/core/pickling/UnPickler.scala index 622752570..dd26b20df 100644 --- a/src/dotty/tools/dotc/core/pickling/UnPickler.scala +++ b/src/dotty/tools/dotc/core/pickling/UnPickler.scala @@ -42,15 +42,15 @@ object UnPickler { * * TempPolyType(List(v_1 T_1, ..., v_n T_n), lo .. hi) * - * to a higher-kinded type appoximation (@see TypeBounds.higherKinded) - */ + * to a type lambda using `parameterizeWith/LambdaAbstract`. + */ def depoly(tp: Type, denot: SymDenotation)(implicit ctx: Context): Type = tp match { case TempPolyType(tparams, restpe) => if (denot.isAbstractType) - restpe.bounds.higherKinded(tparams) + restpe.LambdaAbstract(tparams) // bounds needed? else if (denot.isAliasType) { var err: Option[(String, Position)] = None - val result = restpe.LambdaAbstract(tparams) { (msg, pos) => err = Some((msg, pos)) } + val result = restpe.parameterizeWith(tparams) for ((msg, pos) <- err) ctx.warning( s"""$msg @@ -571,6 +571,8 @@ class UnPickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClassRoot: case info => tp.derivedRefinedType(parent1, name, info) } + case tp @ TypeRef(pre, tpnme.Apply) if pre.isLambda => + elim(pre) case _ => tp } diff --git a/src/dotty/tools/dotc/typer/Applications.scala b/src/dotty/tools/dotc/typer/Applications.scala index aaceac0e0..91f4ce9a5 100644 --- a/src/dotty/tools/dotc/typer/Applications.scala +++ b/src/dotty/tools/dotc/typer/Applications.scala @@ -510,10 +510,17 @@ trait Applications extends Compatibility { self: Typer => } def typedTypeApply(tree: untpd.TypeApply, pt: Type)(implicit ctx: Context): Tree = track("typedTypeApply") { - val typedArgs = tree.args mapconserve (typedType(_)) + var typedArgs = tree.args mapconserve (typedType(_)) val typedFn = typedExpr(tree.fun, PolyProto(typedArgs.tpes, pt)) typedFn.tpe.widen match { - case pt: PolyType => checkBounds(typedArgs, pt, tree.pos) + case pt: PolyType => + def adaptTypeArg(tree: tpd.Tree, bound: Type): tpd.Tree = + if (bound.isLambda && !tree.tpe.isLambda && tree.tpe.typeParams.nonEmpty) + tree.withType(tree.tpe.EtaExpand) + else tree + if (typedArgs.length <= pt.paramBounds.length) + typedArgs = typedArgs.zipWithConserve(pt.paramBounds)(adaptTypeArg) + checkBounds(typedArgs, pt, tree.pos) case _ => } assignType(cpy.TypeApply(tree, typedFn, typedArgs), typedFn, typedArgs) diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala index 681523bd2..14404e220 100644 --- a/src/dotty/tools/dotc/typer/Namer.scala +++ b/src/dotty/tools/dotc/typer/Namer.scala @@ -226,8 +226,13 @@ class Namer { typer: Typer => case tree: MemberDef => val name = tree.name.encode checkNoConflict(name) - val deferred = if (lacksDefinition(tree)) Deferred else EmptyFlags + val isDeferred = lacksDefinition(tree) + val deferred = if (isDeferred) Deferred else EmptyFlags val method = if (tree.isInstanceOf[DefDef]) Method else EmptyFlags + val higherKinded = tree match { + case tree: TypeDef if tree.tparams.nonEmpty && isDeferred => HigherKinded + case _ => EmptyFlags + } // to complete a constructor, move one context further out -- this // is the context enclosing the class. Note that the context in which a @@ -238,7 +243,7 @@ class Namer { typer: Typer => val cctx = if (tree.name == nme.CONSTRUCTOR) ctx.outer else ctx record(ctx.newSymbol( - ctx.owner, name, tree.mods.flags | deferred | method, + ctx.owner, name, tree.mods.flags | deferred | method | higherKinded, adjustIfModule(new Completer(tree)(cctx), tree), privateWithinClass(tree.mods), tree.pos)) case tree: Import => @@ -453,7 +458,7 @@ class Namer { typer: Typer => val Select(New(tpt), nme.CONSTRUCTOR) = core val targs1 = targs map (typedAheadType(_)) val ptype = typedAheadType(tpt).tpe appliedTo targs1.tpes - if (ptype.uninstantiatedTypeParams.isEmpty) ptype + if (ptype.typeParams.isEmpty) ptype else typedAheadExpr(parent).tpe } @@ -661,17 +666,17 @@ class Namer { typer: Typer => completeParams(tdef.tparams) sym.info = TypeBounds.empty // avoid cyclic reference errors for F-bounds val tparamSyms = tdef.tparams map symbolOfTree + val isDerived = tdef.rhs.isInstanceOf[untpd.DerivedTypeTree] + val toParameterize = tparamSyms.nonEmpty && !isDerived + val needsLambda = sym.allOverriddenSymbols.exists(_ is HigherKinded) && !isDerived val rhsType = typedAheadType(tdef.rhs).tpe - + def abstractedRhsType = + if (needsLambda) rhsType.LambdaAbstract(tparamSyms) + else if (toParameterize) rhsType.parameterizeWith(tparamSyms) + else rhsType rhsType match { - case bounds: TypeBounds => - if (tparamSyms.nonEmpty) bounds.higherKinded(tparamSyms) - else rhsType - case _ => - val abstractedRhsType = - if (tparamSyms.nonEmpty) rhsType.LambdaAbstract(tparamSyms)(ctx.error(_, _)) - else rhsType - TypeAlias(abstractedRhsType, if (sym is Local) sym.variance else 0) + case _: TypeBounds => abstractedRhsType + case _ => TypeAlias(abstractedRhsType, if (sym is Local) sym.variance else 0) } } } \ No newline at end of file -- cgit v1.2.3