From eb2b6bf420b24ac0307e17fc9fec38e91012d1af Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Mon, 18 Mar 2013 22:05:26 +0100 Subject: More changes for higher-kinded types emulation. --- .../annotation/internal/ContravariantBetween.scala | 3 ++ .../annotation/internal/CovariantBetween.scala | 3 ++ .../annotation/internal/InvariantBetween.scala | 3 ++ src/dotty/tools/dotc/core/Definitions.scala | 41 ++++++++++------ src/dotty/tools/dotc/core/NameOps.scala | 8 ++++ src/dotty/tools/dotc/core/TypeComparers.scala | 19 ++++---- src/dotty/tools/dotc/core/Types.scala | 54 +++++++++++++++++++--- src/dotty/tools/dotc/core/pickling/UnPickler.scala | 30 ++++++++---- 8 files changed, 123 insertions(+), 38 deletions(-) create mode 100644 src/dotty/annotation/internal/ContravariantBetween.scala create mode 100644 src/dotty/annotation/internal/CovariantBetween.scala create mode 100644 src/dotty/annotation/internal/InvariantBetween.scala diff --git a/src/dotty/annotation/internal/ContravariantBetween.scala b/src/dotty/annotation/internal/ContravariantBetween.scala new file mode 100644 index 000000000..7eb068b89 --- /dev/null +++ b/src/dotty/annotation/internal/ContravariantBetween.scala @@ -0,0 +1,3 @@ +package dotty.annotation.internal + +trait ContravariantBetween[-Lo, +Hi] \ No newline at end of file diff --git a/src/dotty/annotation/internal/CovariantBetween.scala b/src/dotty/annotation/internal/CovariantBetween.scala new file mode 100644 index 000000000..d65a5f1b9 --- /dev/null +++ b/src/dotty/annotation/internal/CovariantBetween.scala @@ -0,0 +1,3 @@ +package dotty.annotation.internal + +trait CovariantBetween[-Lo, +Hi] \ No newline at end of file diff --git a/src/dotty/annotation/internal/InvariantBetween.scala b/src/dotty/annotation/internal/InvariantBetween.scala new file mode 100644 index 000000000..bf572b66c --- /dev/null +++ b/src/dotty/annotation/internal/InvariantBetween.scala @@ -0,0 +1,3 @@ +package dotty.annotation.internal + +trait InvariantBetween[-Lo, +Hi] \ No newline at end of file diff --git a/src/dotty/tools/dotc/core/Definitions.scala b/src/dotty/tools/dotc/core/Definitions.scala index c728493dd..3d3a10d8e 100644 --- a/src/dotty/tools/dotc/core/Definitions.scala +++ b/src/dotty/tools/dotc/core/Definitions.scala @@ -136,6 +136,9 @@ class Definitions(implicit ctx: Context) { // Annotation classes lazy val AliasAnnot = requiredClass("dotty.annotation.internal.Alias") lazy val ChildAnnot = requiredClass("dotty.annotation.internal.Child") + lazy val InvariantBetweenClass = requiredClass("dotty.annotation.internal.InvariantBetween") + lazy val CovariantBetweenClass = requiredClass("dotty.annotation.internal.CovariantBetween") + lazy val ContravariantBetweenClass = requiredClass("dotty.annotation.internal.ContravariantBetween") lazy val ScalaSignatureAnnot = requiredClass("scala.reflect.ScalaSignature") lazy val ScalaLongSignatureAnnot = requiredClass("scala.reflect.ScalaLongSignature") lazy val DeprecatedAnnot = requiredClass("scala.deprecated") @@ -202,16 +205,15 @@ class Definitions(implicit ctx: Context) { lazy val PhantomClasses = Set[Symbol](AnyClass, AnyValClass, NullClass, NothingClass) + // ----- Higher kinds machinery ------------------------------------------ + private var _hkTraits: Set[Symbol] = Set() - private var _hkTraitOfArity: Map[Int, ClassSymbol] = Map() - private var _hkParamNames: Set[Name] = Set() - private var _hkParamArity: Map[Name, Int] = Map() + private var _hkTrait: Map[Int, ClassSymbol] = Map() + /** The set of all `HigherKinded_n` traits that are referred to in thos compilation run. */ def hkTraits: Set[Symbol] = _hkTraits - def hkParamNames = _hkParamNames - def hkParamArity = _hkParamArity - /** A trait `HigherKinded[Lo_1,...,Lo_n,Hi_1,...,Hi_n]` that represents + /** A trait `HigherKinded_n[B1, ..., Bn]` that represents * the bounds of a higher-kinded type. */ def hkTrait(n: Int): ClassSymbol = { @@ -219,24 +221,33 @@ class Definitions(implicit ctx: Context) { def complete(denot: SymDenotation): Unit = { val cls = denot.asClass.classSymbol val paramDecls = newScope - for (i <- 0 until n) newSyntheticTypeParam(cls, paramDecls, "Lo"+i) - for (i <- 0 until n) newSyntheticTypeParam(cls, paramDecls, "Hi"+i) + for (i <- 0 until n) + newSyntheticTypeParam(cls, paramDecls, "B"+i).setFlag(Covariant) denot.info = ClassInfo(ScalaPackageClass.thisType, cls, List(ObjectClass.typeConstructor), paramDecls) } } - _hkTraitOfArity get n match { - case Some(cls) => cls + _hkTrait get n match { + case Some(cls) => + cls case None => - val cls = ctx.newClassSymbol(ScalaPackageClass, tpnme.higherKindedTraitName(n), Synthetic, completer).entered + val cls = ctx.newClassSymbol( + ScalaPackageClass, + tpnme.higherKindedTraitName(n), + Trait | Interface | Synthetic, + completer).entered _hkTraits += cls - _hkTraitOfArity = _hkTraitOfArity.updated(n, cls) - val paramName = tpnme.higherKindedParamName(n) - _hkParamNames += paramName - _hkParamArity = _hkParamArity.updated(paramName, n) + _hkTrait = _hkTrait.updated(n, cls) cls } } + /** The bounds trait corresponding to the given variance */ + def hkBoundsClass(variance: Int) = variance match { + case 0 => InvariantBetweenClass + case 1 => CovariantBetweenClass + case -1 => ContravariantBetweenClass + } + // ----- Value class machinery ------------------------------------------ private[this] val _boxedClass = mutable.Map[Symbol, Symbol]() diff --git a/src/dotty/tools/dotc/core/NameOps.scala b/src/dotty/tools/dotc/core/NameOps.scala index e83278814..1045d0de9 100644 --- a/src/dotty/tools/dotc/core/NameOps.scala +++ b/src/dotty/tools/dotc/core/NameOps.scala @@ -83,6 +83,14 @@ object NameOps { name.last == '=' && name.head != '=' && isOperatorPart(name.head) } + /** Is this the name of a higher-kinded type parameter? */ + def isHkParamName: Boolean = name(0) == '_' && name.startsWith(HK_PARAM_PREFIX) + + /** The index of the higher-kinded type parameter with this name. + * Pre: isHkParamName. + */ + def hkParamIndex: Int = name.drop(name.lastIndexOf('$') + 1).toString.toInt + /** If the name ends with $nn where nn are * all digits, strip the $ and the digits. * Otherwise return the argument. diff --git a/src/dotty/tools/dotc/core/TypeComparers.scala b/src/dotty/tools/dotc/core/TypeComparers.scala index cdc9016cb..b5896df21 100644 --- a/src/dotty/tools/dotc/core/TypeComparers.scala +++ b/src/dotty/tools/dotc/core/TypeComparers.scala @@ -198,20 +198,21 @@ object TypeComparers { } */ /** Is `tp1` a subtype of a type `tp2` of the form - * `scala.HigerKindedN[Lo1, Hi1, ..., LoN, HiN]`? - * This is the case if `tp1` has N type parameters and - * for all I, type parameter #I's bounds are contained in - * `LoI..HiI`. + * `scala.HigerKindedN[xBetween_1[Lo_1, Hi_1], ..., xBetween_n[Lo_n, Hi_n]]`? + * This is the case if `tp1` has `n` type parameters and + * for all `0 <= i < n`, the i'th type parameter's bounds are contained in + * `Lo_i..Hi_i` and its variance corresponds to the xBetween_i class. */ def isSubTypeHK(tp1: Type, tp2: Type): Boolean = { val tparams = tp1.typeParams val hkArgs = tp2.typeArgs - val (loBounds, hiBounds) = hkArgs splitAt (hkArgs.length / 2) - (loBounds.length == tparams.length) && { + (hkArgs.length == tparams.length) && { val base = ctx.newSkolemSingleton(tp1) - (loBounds, hiBounds, tparams).zipped.forall { (lo, hi, tparam) => - val tparamBounds = base.memberInfo(tparam).bounds - lo <:< tparamBounds.lo && tparamBounds.hi <:< hi + (hkArgs, tparams).zipped.forall { (hkArg, tparam) => + val lo2 :: hi2 :: Nil = hkArg.typeArgs + val TypeBounds(lo1, hi1) = base.memberInfo(tparam) + lo2 <:< lo1 && hi1 <:< hi2 && + defn.hkBoundsClass(tparam.variance) == hkArg.typeSymbol } } } diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 690f0f476..2c7037a75 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -6,6 +6,7 @@ import Symbols._ import TypeComparers._ import Flags._ import Names._ +import StdNames._, NameOps._ import Scopes._ import Constants._ import Contexts._ @@ -76,6 +77,9 @@ object Types { /** Is this type different from NoType? */ def exists: Boolean = true + /** This type, if it exists, otherwise `that` type */ + def orElse(that: => Type) = if (exists) this else that + /** Is this type a value type? */ final def isValueType: Boolean = this.isInstanceOf[ValueType] @@ -522,10 +526,11 @@ object Types { /** Encode the type resulting from applying this type to given arguments */ final def appliedTo(args: List[Type])(implicit ctx: Context): Type = { + def recur(tp: Type, tparams: List[TypeSymbol], args: List[Type]): Type = args match { case arg :: args1 => if (tparams.isEmpty) { - println(s"applied type mismatch: $this $args, $typeParams = typeParams") + println(s"applied type mismatch: $this $args, $typeParams = typeParams") // !!! DEBUG println(s"precomplete decls = ${typeSymbol.preCompleteDecls.toList.map(_.denot).mkString("\n ")}") } val tparam = tparams.head @@ -533,12 +538,47 @@ object Types { recur(tp1, tparams.tail, args1) case nil => tp } + + def hkApp(tp: Type): Type = tp match { + case AndType(l, r) => + hkApp(l) orElse hkApp(r) + case tp: RefinedType if defn.hkTraits contains tp.typeSymbol => + tp + case tp: TypeProxy => + hkApp(tp.underlying) + } + + def hkRefinement(tp: TypeRef): Type = { + val hkArgs = hkApp(tp.info).typeArgs + ((tp: Type) /: hkArgs.zipWithIndex.zip(args)) { + case (parent, ((hkArg, idx), arg)) => + val vsym = hkArg.typeSymbol + val rhs = + if (vsym == defn.InvariantBetweenClass) + TypeAlias(arg) + else if (vsym == defn.CovariantBetweenClass) + TypeBounds.upper(arg) + else { + assert(vsym == defn.ContravariantBetweenClass) + TypeBounds.lower(arg) + } + RefinedType(parent, tpnme.higherKindedParamName(idx), rhs) + } + } + + // begin applied type if (args.isEmpty) this else this match { case tp: PolyType => tp.instantiate(args) - case tp: TypeRef if tp.symbol.isClass => - recur(tp, tp.typeParams, args) + case tp: TypeRef => + val tsym = tp.symbol + if (tsym.isClass) + recur(tp, tp.typeParams, args) + else if (tsym.isAliasType) + tp.underlying.appliedTo(args) + else + hkRefinement(tp) case tp: TypeProxy => tp.underlying.appliedTo(args) } @@ -1009,10 +1049,9 @@ object Types { 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 - else if ((defn.hkParamNames contains refinedName) && - (parent.typeParams.length >= defn.hkParamArity(refinedName))) + else if (refinedName.isHkParamName && typeParams.length > refinedName.hkParamIndex) derivedRefinedType( - parent, parent.typeParams.apply(defn.hkParamArity(refinedName)).name, refinedInfo) + parent, parent.typeParams.apply(refinedName.hkParamIndex).name, refinedInfo) else RefinedType(parent, refinedName, rt => refinedInfo.substThis(this, RefinedThis(rt))) @@ -1337,6 +1376,9 @@ object Types { TypeBounds(f(lo), f(hi)) override def computeHash = doHash(lo, hi) + + override def toString = + if (lo eq hi) s"TypeAlias($lo)" else s"TypeBounds($lo, $hi)" } final class CachedTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) diff --git a/src/dotty/tools/dotc/core/pickling/UnPickler.scala b/src/dotty/tools/dotc/core/pickling/UnPickler.scala index ddbc4b8e2..00c304196 100644 --- a/src/dotty/tools/dotc/core/pickling/UnPickler.scala +++ b/src/dotty/tools/dotc/core/pickling/UnPickler.scala @@ -34,11 +34,11 @@ object UnPickler { * If `forSym` is not an abstract type, this simply returns an equivalent `PolyType`. * If `forSym` is an abstract type, it converts a * - * TempPolyType(List(T_1, ..., T_n), lo..hi) + * TempPolyType(List(v_1 T_1, ..., v_n T_n), lo .. hi) * * to * - * Bottom..HigherKinded[lo_1, ..., lo_N, hi_1, ..., hi_N] & (lo..hi) + * lo .. HigherKinded_n[v_1Between[lo_1, hi_1],..., v_nBetween[lo_n, hi_n]] & hi * * where lo_i, hi_i are the lower/upper bounds of the type parameters T_i. * This works only as long as none of the type parameters T_i appears in any @@ -48,13 +48,21 @@ object UnPickler { def depoly(tp: Type, forSym: SymDenotation)(implicit ctx: Context): Type = tp match { case TempPolyType(tparams, restpe) => if (forSym.isAbstractType) { - val typeArgs = (tparams map (_.info.bounds.lo)) ++ (tparams map (_.info.bounds.hi)) + val typeArgs = for (tparam <- tparams) yield { + val TypeBounds(lo, hi) = tparam.info + defn.hkBoundsClass(tparam.variance).typeConstructor + .appliedTo(List(lo, hi)) + } val elimTparams: Type => Type = _.subst(tparams, tparams map (_ => defn.AnyType)) val correctedArgs = typeArgs.mapConserve(elimTparams) val correctedRes = elimTparams(restpe) - assert(correctedRes.isInstanceOf[TypeBounds]) - val hk = defn.hkTrait(tparams.length) - val result = TypeBounds.upper(hk.typeConstructor.appliedTo(correctedArgs)) & correctedRes + val hkBound = defn.hkTrait(tparams.length).typeConstructor + .appliedTo(correctedArgs) + val result = correctedRes match { + case TypeBounds(lo, hi) => + val hi1 = if (hi == defn.AnyType) hkBound else AndType(hkBound, hi) + TypeBounds(lo, hi1) //note: using & instead would be too eager + } if ((typeArgs ne correctedArgs) || (restpe ne correctedRes)) ctx.warning(s"""failure to import F-bounded higher-kinded type |original type definition: ${forSym.show}${tp.show} @@ -551,8 +559,14 @@ class UnPickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClassRoot: val pre = readTypeRef() val sym = readSymbolRef() val tycon = - if (isLocal(sym)) TypeRef(pre, sym.asType) - else TypeRef(pre, sym.name.asTypeName) + if (isLocal(sym)) { + TypeRef( + if ((pre eq NoPrefix) && (sym is TypeParam)) + sym.owner.thisType + else + pre, + sym.asType) + } else TypeRef(pre, sym.name.asTypeName) val args = until(end, readTypeRef) if (args.nonEmpty) println(s"reading app type $tycon ${tycon.typeSymbol.debugString} $args, owner = ${tycon.typeSymbol.owner.debugString}") // !!! DEBUG tycon.appliedTo(args) -- cgit v1.2.3