From 52d740d120cd197ee816aa0a06732ccdb5d5ab29 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sun, 17 Mar 2013 20:12:16 +0100 Subject: Added emulation of higher-kinded types. Also improvements to toString. --- src/dotty/tools/dotc/core/Definitions.scala | 36 +++++++++++++++++++++- src/dotty/tools/dotc/core/Flags.scala | 2 +- src/dotty/tools/dotc/core/NameOps.scala | 6 ++-- src/dotty/tools/dotc/core/Printers.scala | 6 ++-- src/dotty/tools/dotc/core/StdNames.scala | 6 ++++ src/dotty/tools/dotc/core/Symbols.scala | 11 +++++++ src/dotty/tools/dotc/core/TypeComparers.scala | 20 ++++++++++++ src/dotty/tools/dotc/core/TypeOps.scala | 4 ++- src/dotty/tools/dotc/core/Types.scala | 29 ++++++++++++++--- .../tools/dotc/core/pickling/ClassfileParser.scala | 2 +- src/dotty/tools/dotc/core/pickling/UnPickler.scala | 33 +++++++++++++++----- src/test/showClass.scala | 2 +- 12 files changed, 136 insertions(+), 21 deletions(-) (limited to 'src') diff --git a/src/dotty/tools/dotc/core/Definitions.scala b/src/dotty/tools/dotc/core/Definitions.scala index ded45548d..471510e6f 100644 --- a/src/dotty/tools/dotc/core/Definitions.scala +++ b/src/dotty/tools/dotc/core/Definitions.scala @@ -22,7 +22,7 @@ class Definitions(implicit ctx: Context) { private def newSyntheticTypeParam(cls: ClassSymbol, scope: MutableScope, suffix: String = "T0") = { val tname = suffix.toTypeName.expandedName(cls) - val tparam = ctx.newSymbol(cls, tname, TypeParamCreationFlags, TypeBounds.empty) + val tparam = ctx.newSymbol(cls, tname, TypeParamCreationFlags | ExpandedName, TypeBounds.empty) scope.enter(tparam) } @@ -202,6 +202,40 @@ class Definitions(implicit ctx: Context) { lazy val PhantomClasses = Set[Symbol](AnyClass, AnyValClass, NullClass, NothingClass) + 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() + + def hkTraits: Set[Symbol] = _hkTraits + def hkParamNames = _hkParamNames + def hkParamArity = _hkParamArity + + def hkTrait(n: Int): ClassSymbol = { + val completer = new LazyType { + def complete(denot: SymDenotation): Unit = { + val cls = denot.asClass.classSymbol + val paramDecls = newScope + for (i <- 0 until n) { + newSyntheticTypeParam(cls, paramDecls, "Lo"+i) + newSyntheticTypeParam(cls, paramDecls, "Hi"+i) + } + denot.info = ClassInfo(ScalaPackageClass.thisType, cls, List(ObjectClass.typeConstructor), paramDecls) + } + } + _hkTraitOfArity get n match { + case Some(cls) => cls + case None => + val cls = ctx.newClassSymbol(ScalaPackageClass, tpnme.higherKindedTraitName(n), Synthetic, completer).entered + _hkTraits += cls + _hkTraitOfArity = _hkTraitOfArity.updated(n, cls) + val paramName = tpnme.higherKindedParamName(n) + _hkParamNames += paramName + _hkParamArity = _hkParamArity.updated(paramName, n) + cls + } + } + // ----- Value class machinery ------------------------------------------ private[this] val _boxedClass = mutable.Map[Symbol, Symbol]() diff --git a/src/dotty/tools/dotc/core/Flags.scala b/src/dotty/tools/dotc/core/Flags.scala index 116eacab2..ff0a2e0ee 100644 --- a/src/dotty/tools/dotc/core/Flags.scala +++ b/src/dotty/tools/dotc/core/Flags.scala @@ -369,7 +369,7 @@ object Flags { /** Flags guaranteed to be set upon symbol creation */ final val FromStartFlags = AccessFlags | Module | Package | Deferred | Param | Scala2ExistentialCommon | Touched | - CovariantCommon | ContravariantCommon + Static | CovariantCommon | ContravariantCommon | ExpandedName assert(FromStartFlags.isTermFlags && FromStartFlags.isTypeFlags) // TODO: Should check that FromStartFlags do not changed in completion diff --git a/src/dotty/tools/dotc/core/NameOps.scala b/src/dotty/tools/dotc/core/NameOps.scala index f50b44ac8..e83278814 100644 --- a/src/dotty/tools/dotc/core/NameOps.scala +++ b/src/dotty/tools/dotc/core/NameOps.scala @@ -103,8 +103,10 @@ object NameOps { /** The expanded name of `name` relative to this class `base` with given `separator` */ - def expandedName(base: Symbol, separator: Name = nme.EXPAND_SEPARATOR)(implicit ctx: Context): N = - name.fromName(base.fullName('$') ++ separator ++ name).asInstanceOf[N] + def expandedName(base: Symbol, separator: Name = nme.EXPAND_SEPARATOR)(implicit ctx: Context): N = { + val prefix = if (base is Flags.ExpandedName) base.name else base.fullName('$') + name.fromName(prefix ++ separator ++ name).asInstanceOf[N] + } def unexpandedName(separator: Name = nme.EXPAND_SEPARATOR): N = { val idx = name.lastIndexOfSlice(separator) diff --git a/src/dotty/tools/dotc/core/Printers.scala b/src/dotty/tools/dotc/core/Printers.scala index 2e0d03082..06e96593f 100644 --- a/src/dotty/tools/dotc/core/Printers.scala +++ b/src/dotty/tools/dotc/core/Printers.scala @@ -261,10 +261,10 @@ object Printers { tp match { case TypeBounds(lo, hi) => if (lo eq hi) - " = " + lo + " = " + lo.show else - (if (lo.typeSymbol == defn.NothingClass) "" else " >: " + lo) + - (if (hi.typeSymbol == defn.AnyClass) "" else " <: " + hi) + (if (lo.typeSymbol == defn.NothingClass) "" else " >: " + lo.show) + + (if (hi.typeSymbol == defn.AnyClass) "" else " <: " + hi.show) case ClassInfo(pre, cdenot, cparents, decls, optSelfType) => val preStr = showLocal(pre) val selfStr = diff --git a/src/dotty/tools/dotc/core/StdNames.scala b/src/dotty/tools/dotc/core/StdNames.scala index e73aeaea9..f5c3fb845 100644 --- a/src/dotty/tools/dotc/core/StdNames.scala +++ b/src/dotty/tools/dotc/core/StdNames.scala @@ -238,9 +238,11 @@ object StdNames { val SELECTOR_DUMMY: N = "" val SELF: N = "$this" val SETTER_SUFFIX: N = encode("_=") + val SKOLEM: N = "" val SPECIALIZED_INSTANCE: N = "specInstance$" val STAR: N = "*" val THIS: N = "_$this" + val HK_PARAM_PREFIX: N = "_$hk$" final val Nil: N = "Nil" final val Predef: N = "Predef" @@ -276,6 +278,7 @@ object StdNames { val EmptyPackageClass: N = "EmptyPackageClass" val ExistentialTypeTree: N = "ExistentialTypeTree" val Flag : N = "Flag" + val HigherKinded: N = "HigherKinded" val Ident: N = "Ident" val Import: N = "Import" val Literal: N = "Literal" @@ -620,6 +623,9 @@ object StdNames { class ScalaTypeNames extends ScalaNames[TypeName] { protected def fromString(s: String) = typeName(s) + + def higherKindedTraitName(n: Int) = HigherKinded ++ n.toString + def higherKindedParamName(n: Int) = HK_PARAM_PREFIX ++ n.toString } abstract class JavaNames[N <: Name] extends DefinedNames[N] { diff --git a/src/dotty/tools/dotc/core/Symbols.scala b/src/dotty/tools/dotc/core/Symbols.scala index e76de6bdf..089d41be7 100644 --- a/src/dotty/tools/dotc/core/Symbols.scala +++ b/src/dotty/tools/dotc/core/Symbols.scala @@ -229,6 +229,8 @@ trait Symbols { this: Context => tparams } + def newSkolem(tp: Type) = newSymbol(defn.RootClass, nme.SKOLEM, SyntheticArtifact, tp) + type OwnerMap = Symbol => Symbol /** Map given symbols, subjecting all types to given type map and owner map. @@ -367,6 +369,13 @@ object Symbols { private def pickFile(file: AbstractFile, classFile: Boolean): AbstractFile = if ((file eq null) || classFile != (file.path endsWith ".class")) null else file + /** The prefix string to be used when displaying this symbol without denotation */ + protected def prefixString = "Symbol" + + override def toString: String = + if (lastDenot == null) s"Naked$prefixString#$id" + else lastDenot.toString + def show(implicit ctx: Context): String = ctx.show(this) def showLocated(implicit ctx: Context): String = ctx.showLocated(this) def showDcl(implicit ctx: Context): String = ctx.showDcl(this) @@ -415,6 +424,8 @@ object Symbols { /** Have we seen a subclass of this class? */ def hasChildren = superIdHint >= 0 + + override protected def prefixString = "ClassSymbol" } class ErrorSymbol(val underlying: Symbol, msg: => String)(implicit ctx: Context) extends Symbol(NoCoord) { diff --git a/src/dotty/tools/dotc/core/TypeComparers.scala b/src/dotty/tools/dotc/core/TypeComparers.scala index 5f92d65c9..d3c00e818 100644 --- a/src/dotty/tools/dotc/core/TypeComparers.scala +++ b/src/dotty/tools/dotc/core/TypeComparers.scala @@ -103,6 +103,7 @@ object TypeComparers { val cls2 = tp2.symbol ( cls2 == defn.SingletonClass && tp1.isStable || cls2 == defn.NotNullClass && tp1.isNotNull + || (defn.hkTraits contains cls2) && isSubTypeHK(tp1, tp2) || fourthTry(tp1, tp2) ) } @@ -196,6 +197,25 @@ object TypeComparers { true } */ + /** 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`. + */ + def isSubTypeHK(tp1: Type, tp2: Type): Boolean = { + val tparams = tp1.typeParams + val hkargs = tp2.typeArgs + def toBounds(args: List[Type]): List[TypeBounds] = (args: @unchecked) match { + case lo :: hi :: args1 => TypeBounds(lo, hi) :: toBounds(args1) + case Nil => Nil + } + val base = ctx.newSkolemSingleton(tp1) + val hkbounds = toBounds(hkargs) + (hkbounds.length == tparams.length) && + (hkbounds, tparams map (base.memberInfo(_).bounds)).zipped.forall(_ contains _) + } + /** A function implementing `tp1` matches `tp2`. */ final def matchesType(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = tp1 match { case tp1: MethodType => diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala index 48bb91a1e..aa786d451 100644 --- a/src/dotty/tools/dotc/core/TypeOps.scala +++ b/src/dotty/tools/dotc/core/TypeOps.scala @@ -4,6 +4,8 @@ import Contexts._, Types._, Symbols._, Names._, Flags._, Scopes._ trait TypeOps { this: Context => + def newSkolemSingleton(underlying: Type) = TermRef(NoPrefix, newSkolem(underlying)) + final def asSeenFrom(tp: Type, pre: Type, cls: Symbol, theMap: AsSeenFromMap): Type = { def toPrefix(pre: Type, cls: Symbol, thiscls: ClassSymbol): Type = @@ -183,7 +185,7 @@ trait TypeOps { this: Context => val parentRefs = parents map normalizeToRef for ((name, tpe) <- refinements) decls.enter { val formal = formals(name) - val bounds = tpe.toRHS(formal) + val bounds = tpe //.toRHS(formal) ctx.newSymbol(cls, name, formal.flags & RetainedTypeArgFlags, bounds) } parentRefs diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 28ecdb805..690f0f476 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -11,6 +11,7 @@ import Constants._ import Contexts._ import Annotations._ import SymDenotations._ +import Decorators._ import Denotations._ import Periods._ import TypedTrees.tpd._, TypedTrees.TreeMapper @@ -187,7 +188,8 @@ object Types { case tp: TypeRef => val tsym = tp.typeSymbol if (tsym.isClass) tsym.typeParams - else tp.underlying.typeParams + else if (tsym.isAliasType) tp.underlying.typeParams + else Nil case tp: TypeProxy => tp.underlying.typeParams case _ => @@ -368,6 +370,7 @@ object Types { */ final def widen(implicit ctx: Context): Type = this match { case tp: SingletonType => tp.underlying.widen + case tp: TypeBounds => tp.hi.widen case tp: ExprType => tp.resultType.widen case _ => this } @@ -1004,10 +1007,17 @@ object Types { override def underlying(implicit ctx: Context) = parent 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 RefinedType(parent, refinedName, rt => refinedInfo.substThis(this, RefinedThis(rt))) + 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))) + derivedRefinedType( + parent, parent.typeParams.apply(defn.hkParamArity(refinedName)).name, refinedInfo) + else + RefinedType(parent, refinedName, rt => refinedInfo.substThis(this, RefinedThis(rt))) override def computeHash = doHash(refinedName, refinedInfo, parent) + override def toString = s"RefinedType($parent, $refinedName, $refinedInfo | hash = $hashCode)" } class CachedRefinedType(parent: Type, refinedName: Name, infoFn: RefinedType => Type) extends RefinedType(parent, refinedName)(infoFn) @@ -1111,6 +1121,8 @@ object Types { else resultType override def computeHash = doHash(paramNames, resultType, paramTypes) + protected def prefixString = "MethodType" + override def toString = s"$prefixString($paramNames, $paramTypes, $resultType)" } final class CachedMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) @@ -1123,6 +1135,7 @@ object Types { override def isJava = true override def equals(that: Any) = super.equals(that) && that.isInstanceOf[JavaMethodType] override def computeHash = super.computeHash + 1 + override protected def prefixString = "JavaMethodType" } final class ImplicitMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) @@ -1130,6 +1143,7 @@ object Types { override def isImplicit = true override def equals(that: Any) = super.equals(that) && that.isInstanceOf[ImplicitMethodType] override def computeHash = super.computeHash + 2 + override protected def prefixString = "ImplicitMethodType" } abstract class MethodTypeCompanion { @@ -1201,6 +1215,7 @@ object Types { case that: PolyType => this eq that case _ => false } + override def toString = s"PolyType($paramNames, $paramBounds, $resultType)" } object PolyType { @@ -1225,6 +1240,7 @@ object Types { def copy(bt: BT) = MethodParam(bt, paramNum) // need to customize hashCode to prevent infinite recursion for dep meth types. override def hashCode = doHash(System.identityHashCode(binder) + paramNum) + override def toString = s"MethodParam(${binder.paramNames(paramNum)})" } case class PolyParam(binder: PolyType, paramNum: Int) extends BoundType { @@ -1232,7 +1248,8 @@ object Types { override def underlying(implicit ctx: Context) = binder.paramBounds(paramNum) def copy(bt: BT) = PolyParam(bt, paramNum) // no customized hashCode needed because cycle is broken in PolyType - } + override def toString = s"PolyParam(${binder.paramNames(paramNum)})" + } case class RefinedThis(binder: RefinedType) extends BoundType with SingletonType { type BT = RefinedType @@ -1241,6 +1258,7 @@ object Types { // need to customize hashCode to prevent infinite recursion for // refinements that refer to the refinement type via this override def hashCode = doHash(System.identityHashCode(binder)) + override def toString = s"RefinedThis(${binder.hashCode})" } // ------ ClassInfo, Type Bounds ------------------------------------------------------------ @@ -1298,6 +1316,9 @@ object Types { /** Type bounds >: lo <: hi */ abstract case class TypeBounds(lo: Type, hi: Type) extends CachedProxyType with TypeType { + assert(!lo.isInstanceOf[TypeBounds], lo+" "+lo.getClass) + assert(!hi.isInstanceOf[TypeBounds], hi+" "+hi.getClass) + override def underlying(implicit ctx: Context): Type = hi def derivedTypeBounds(lo: Type, hi: Type)(implicit ctx: Context) = diff --git a/src/dotty/tools/dotc/core/pickling/ClassfileParser.scala b/src/dotty/tools/dotc/core/pickling/ClassfileParser.scala index 51be5b329..7d885eaf1 100644 --- a/src/dotty/tools/dotc/core/pickling/ClassfileParser.scala +++ b/src/dotty/tools/dotc/core/pickling/ClassfileParser.scala @@ -181,7 +181,7 @@ class ClassfileParser( case _ => } setPrivateWithin(denot, jflags) - denot.info = depoly(parseAttributes(sym, info)) + denot.info = depoly(parseAttributes(sym, info), denot) if ((denot is Flags.Method) && (jflags & JAVA_ACC_VARARGS) != 0) denot.info = arrayToRepeated(denot.info) diff --git a/src/dotty/tools/dotc/core/pickling/UnPickler.scala b/src/dotty/tools/dotc/core/pickling/UnPickler.scala index dc4494e4e..d4e27f11a 100644 --- a/src/dotty/tools/dotc/core/pickling/UnPickler.scala +++ b/src/dotty/tools/dotc/core/pickling/UnPickler.scala @@ -21,13 +21,31 @@ object UnPickler { /** Exception thrown if classfile is corrupted */ class BadSignature(msg: String) extends RuntimeException(msg) - case class TempPolyType(tparams: List[Symbol], tpe: Type) extends UncachedGroundType + case class TempPolyType(tparams: List[Symbol], tpe: Type) extends UncachedGroundType { + override def show(implicit ctx: Context): String = + s"[${ctx.showDcls(tparams, ", ")}]${tpe.show}" + } /** Temporary type for classinfos, will be decomposed on completion of the class */ case class TempClassInfoType(parentTypes: List[Type], decls: MutableScope, clazz: Symbol) extends UncachedGroundType - def depoly(tp: Type)(implicit ctx: Context): Type = tp match { - case TempPolyType(tparams, restpe) => PolyType.fromSymbols(tparams, restpe) + def depoly(tp: Type, forSym: SymDenotation)(implicit ctx: Context): Type = tp match { + case TempPolyType(tparams, restpe) => + if (forSym.isAbstractType) { + val typeArgs = tparams flatMap { tparam => + List(tparam.info.bounds.lo, tparam.info.bounds.hi) + } + val correctedArgs = typeArgs.mapConserve( + _.subst(tparams, tparams map (_ => defn.AnyType))) + val hk = defn.hkTrait(tparams.length) + if (typeArgs ne correctedArgs) + ctx.warning(s"""failure to import F-bounded higher-kinded type + |original type definition: ${forSym.show}${tp.show} + |definition used instead : ${forSym.show} <: $hk[${correctedArgs.map(_.show).mkString(", ")}] + |proceed at own risk.""".stripMargin) + hk.typeConstructor.appliedTo(typeArgs) + } else + PolyType.fromSymbols(tparams, restpe) case tp => tp } @@ -371,9 +389,8 @@ class UnPickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClassRoot: var name1 = name.asTypeName var flags1 = flags if (flags is TypeParam) { - // println(s"expanding name of type parameter $name, owner = ${owner.denot}, completed = ${owner.isCompleted}") // !!! DEBUG name1 = name1.expandedName(owner) - flags1 |= TypeParamCreationFlags + flags1 |= TypeParamCreationFlags | ExpandedName } cctx.newSymbol(owner, name1, flags1, localMemberUnpickler, coord = start) case CLASSsym => @@ -406,13 +423,14 @@ class UnPickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClassRoot: inforef = readNat() pw } + println("reading type for "+denot) val tp = at(inforef, () => readType(forceProperType = denot.isTerm)) denot match { case denot: ClassDenotation => val optSelfType = if (atEnd) NoType else readTypeRef() setClassInfo(denot, tp, optSelfType) case denot => - val tp1 = depoly(tp) + val tp1 = depoly(tp, denot) denot.info = if (tag == ALIASsym) TypeAlias(tp1) else tp1 if (atEnd) { assert(!(denot is SuperAccessor), denot) @@ -424,6 +442,7 @@ class UnPickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClassRoot: denot.addAnnotation(Annotation.makeAlias(alias)) } } + println(s"unpicked ${denot.debugString}, info = ${denot.info}") } def startCoord(denot: SymDenotation): Coord = denot.symbol.coord def complete(denot: SymDenotation): Unit = try { @@ -518,7 +537,7 @@ class UnPickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClassRoot: if (isLocal(sym)) TypeRef(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 + if (args.nonEmpty) println(s"reading app type $tycon ${tycon.typeSymbol.debugString} $args, owner = ${tycon.typeSymbol.owner.debugString}") // !!! DEBUG tycon.appliedTo(args) case TYPEBOUNDStpe => TypeBounds(readTypeRef(), readTypeRef()) diff --git a/src/test/showClass.scala b/src/test/showClass.scala index 2ddf0599f..e7e01ae84 100644 --- a/src/test/showClass.scala +++ b/src/test/showClass.scala @@ -18,7 +18,7 @@ object showClass { println(s"self = ${c.show}") println(s"parents = ${cps.map(_.show).mkString(",")}") println(s"decls = ${decls.show}") - println(s"selftype = $optSelfType") + println(s"selftype = ${optSelfType.show}") } } -- cgit v1.2.3