From 27ce72f1b30a06f56782d88c6c4f96d261d4a44e Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 7 Jun 2013 16:14:05 +0200 Subject: Added support for eliminating type parameters from TypeDefs. (1) New scheme for higher-kinded types that deals also with F-bounds. (2) Type parameters in type aliases are eliminated in most cases by expressing as unparameterized aliases of some refinement type. We will issue an error where this is not possible. --- src/dotty/tools/dotc/core/Definitions.scala | 57 +++++++++++++-- src/dotty/tools/dotc/core/Types.scala | 105 ++++++++++++++++++++++++++++ src/dotty/tools/dotc/typer/Namer.scala | 12 +++- 3 files changed, 168 insertions(+), 6 deletions(-) (limited to 'src/dotty/tools/dotc') diff --git a/src/dotty/tools/dotc/core/Definitions.scala b/src/dotty/tools/dotc/core/Definitions.scala index 58878a493..ae8b7887f 100644 --- a/src/dotty/tools/dotc/core/Definitions.scala +++ b/src/dotty/tools/dotc/core/Definitions.scala @@ -20,11 +20,11 @@ class Definitions(implicit ctx: Context) { import ctx.{requiredClass, requiredModule, requiredPackage} - private def newSyntheticTypeParam(cls: ClassSymbol, scope: MutableScope, suffix: String = "T0") = { - val tname = suffix.toTypeName.expandedName(cls) - val tparam = ctx.newSymbol(cls, tname, TypeParamCreationFlags | ExpandedName, TypeBounds.empty) - scope.enter(tparam) - } + private def newTypeParam(cls: ClassSymbol, name: TypeName, flags: FlagSet, scope: MutableScope) = + scope.enter(ctx.newSymbol(cls, name, flags | TypeParamCreationFlags, TypeBounds.empty)) + + private def newSyntheticTypeParam(cls: ClassSymbol, scope: MutableScope, suffix: String = "T0") = + newTypeParam(cls, suffix.toTypeName.expandedName(cls), ExpandedName, scope) private def specialPolyClass(name: TypeName, flags: FlagSet, parentConstrs: Type*): ClassSymbol = { val completer = new LazyType { @@ -322,6 +322,53 @@ class Definitions(implicit ctx: Context) { } } + 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 hgiher-kinded parameter names, which are special treated in type application. + */ + def hkTrait(boundSyms: List[Symbol]) = { + + val completer = new LazyType { + def complete(denot: SymDenotation): Unit = { + val cls = denot.asClass.classSymbol + val paramDecls = newScope + for ((bsym, i) <- boundSyms.zipWithIndex) + newTypeParam(cls, tpnme.higherKindedParamName(i), bsym.flags & VarianceFlags, paramDecls) + denot.info = ClassInfo(ScalaPackageClass.thisType, cls, List(ObjectClass.typeConstructor), paramDecls) + } + } + + def varianceSuffix(v: Int) = v match { + case -1 => "N" + case 0 => "I" + case 1 => "P" + } + + val variances = boundSyms map (_.variance) + val traitName = + tpnme.higherKindedTraitName(boundSyms.length) ++ (variances map varianceSuffix).mkString + + def createTrait = ctx.newClassSymbol( + ScalaPackageClass, + traitName, + Trait | Interface | Synthetic, + completer).entered + + hkTraitOfArity.getOrElseUpdate(variances, createTrait) + } + + /** The bounds trait corresponding to the given variance */ def hkBoundsClass(variance: Int) = variance match { case 0 => InvariantBetweenClass diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 9c33fdca9..0acf084c5 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -15,6 +15,7 @@ import SymDenotations._ import Decorators._ import Denotations._ import Periods._ +import util.Positions.Position import ast.tpd._, printing.Texts._ import transform.Erasure import printing.Printer @@ -758,6 +759,70 @@ object Types { recur(0, this) } + /** Given a type alias + * + * type T[boundSyms] = p.C[targs] + * + * produce its equivalent right hand side RHS that makes no reference to the bound + * symbols on the left hand side. I.e. the type alias can be replaced by + * + * 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: + * + * Say we have: + * + * class Triple[type T1, type T2, type T3] + * type A[X] = Triple[(X, X), X, String] + * + * Then this is rewritable, as `X` appears as second type argument to `Triple`. + * Occurrences of `X` are rewritten to `this.T2` and the whole definition becomes: + * + * type A = Triple { type T1 = (this.T2, this.T2); type T3 = String } + */ + def LambdaAbstract(boundSyms: List[Symbol])(error: (String, Position) => Unit)(implicit ctx: Context): Type = { + val cls = typeSymbol + if (!cls.isClass) + error("right-hand side of parameterized alias type must be a class", cls.pos) + + /** Rewrite type. + * @param tp The type to rewrite + * @param symMap A map that associates bound symbols were seen to match a rhs type argument + * with the corresponding parameter reference (where the refined this is left open). + * @return The rewritten type, paired with + * the list of replacement types for bound symbols, parameterized by the actual refinement + */ + def rewrite(tp: Type, symMap: Map[Symbol, RefinedType => Type]): (Type, RefinedType => List[Type]) = tp match { + case tp @ RefinedType(parent, name: TypeName) => + tp.refinedInfo match { + case tr: TypeRef if boundSyms contains tr.symbol => + rewrite(tp.parent, symMap + (tr.symbol -> (rt => TypeRef(RefinedThis(rt), name)))) + case info => + val (parent1, replacements) = rewrite(tp.parent, symMap) + (RefinedType(parent1, name, rt => info.subst(boundSyms, replacements(rt))), + replacements) + } + case tp => + def replacements(rt: RefinedType): List[Type] = + for (sym <- boundSyms) yield { + symMap get sym match { + case Some(replacement) => + replacement(rt) + case None => + error(s"parameter $sym of type alias does not appear as type argument of the aliased $cls", sym.pos) + defn.AnyType + } + } + (tp, replacements) + } + rewrite(this, Map())._1 + } + // ----- misc ----------------------------------------------------------- /** The signature of this type. This is by default NotAMethod, @@ -1546,6 +1611,46 @@ object Types { def map(f: Type => Type)(implicit ctx: Context): TypeBounds = TypeBounds(f(lo), f(hi)) + /** Given a 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 `this._$hk$i`. + * - 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) = { + val parent = defn.hkTrait(boundSyms).typeConstructor + 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 computeHash = doHash(lo, hi) override def toString = diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala index 7308d3aa6..18a26e0cf 100644 --- a/src/dotty/tools/dotc/typer/Namer.scala +++ b/src/dotty/tools/dotc/typer/Namer.scala @@ -284,7 +284,17 @@ class Namer { typer: Typer => def typeDefSig(tdef: TypeDef, sym: Symbol)(implicit ctx: Context): Type = { completeParams(tdef.tparams) - ??? + val tparamSyms = tdef.tparams map symbolOfTree + val rhsType = typedAhead(tdef.rhs, Mode.Type).tpe + + rhsType match { + case bounds: TypeBounds => + if (tparamSyms.nonEmpty) bounds.higherKinded(tparamSyms) + else rhsType + case _ => + if (tparamSyms.nonEmpty) rhsType.LambdaAbstract(tparamSyms)(ctx.error(_, _)) + else TypeBounds(rhsType, rhsType) + } } /** The type signature of a ClassDef with given symbol */ -- cgit v1.2.3