diff options
author | Martin Odersky <odersky@gmail.com> | 2013-06-29 18:32:29 +0200 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2013-06-29 22:30:37 +0200 |
commit | 0af96c0f5179104fca02cf1aa144c6176bdb71eb (patch) | |
tree | 78a94297b1df8c7c26a369e4e68ea301166aa2c3 /src/dotty | |
parent | 880c2c1ecf34bd18c3385f146e451ce7abcff9bb (diff) | |
download | dotty-0af96c0f5179104fca02cf1aa144c6176bdb71eb.tar.gz dotty-0af96c0f5179104fca02cf1aa144c6176bdb71eb.tar.bz2 dotty-0af96c0f5179104fca02cf1aa144c6176bdb71eb.zip |
Adding TypeVars and adapting constrints accordingly.
A TypeVar is essentially a container whose contents can be "flipped" from a PolyParam to an instantiated type.
Adding TypeVars avoids subtitutions of large trees and all their types which would otherwise be necessary when a type parameter is instantiated at some point.
Diffstat (limited to 'src/dotty')
-rw-r--r-- | src/dotty/tools/dotc/core/TypeComparers.scala | 125 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 59 |
2 files changed, 102 insertions, 82 deletions
diff --git a/src/dotty/tools/dotc/core/TypeComparers.scala b/src/dotty/tools/dotc/core/TypeComparers.scala index 780f9a722..7afeb6388 100644 --- a/src/dotty/tools/dotc/core/TypeComparers.scala +++ b/src/dotty/tools/dotc/core/TypeComparers.scala @@ -11,48 +11,32 @@ object TypeComparers { /** Constraints over undetermined type parameters * @param map a map from PolyType to the type bounds that constrain the * polytype's type parameters. A type parameter that does not - * have a constraint is represented by a `null` in the corresponding + * have a constraint is represented by a `NoType` in the corresponding * array entry. */ - class Constraints(val map: SimpleMap[PolyType, Array[TypeBounds]]) extends AnyVal { + class Constraints(val map: SimpleMap[PolyType, Array[Type]]) extends AnyVal { - /** Does the constraint's domain contain the given type paraneter? */ - def contains(param: PolyParam): Boolean = { - val boundss = map(param.binder) - boundss != null && boundss(param.paramNum) != null - } - - /** Does the constraint's domain contain some type parameter of `pt`? */ + /** Does the constraint's domain contain the type parameters of `pt`? */ def contains(pt: PolyType): Boolean = map(pt) != null - /** The constraints for guven type parameter `param`. - * @pre The type paraneter is contained in the constraint's domain. + /** The constraints for given type parameter `param`, or NoType if `param` is not part of + * the constraint domain. */ - def apply(param: PolyParam): TypeBounds = - map(param.binder)(param.paramNum) + def apply(param: PolyParam): Type = { + val entries = map(param.binder) + if (entries == null) NoType else entries(param.paramNum) + } /** The constraints for the type parameters of `pt`. - * @pre At least one of the polytype's parameters is contained in the constraint's domain. + * @pre The polytype's type parameters are contained in the constraint's domain. */ - def apply(pt: PolyType): Array[TypeBounds] = - map(pt) - - /** A new constraint which is derived from this constraint by adding - * the type bounds `bounds` added to the type parameter `param`. - */ - def updated(param: PolyParam, bounds: TypeBounds): Constraints = { - val pt = param.binder - val boundss = map(pt).clone - boundss(param.paramNum) = bounds - updated(pt, boundss) - } + def apply(pt: PolyType): Array[Type] = map(pt) - /** A new constraint which is derived from this constraint by adding - * all the type bounds in `boundss` to the corresponding type parameters - * in `pt`. + /** A new constraint which is derived from this constraint by adding or replacing + * the entries corresponding to `pt` with `entries`. */ - def updated(pt: PolyType, boundss: Array[TypeBounds]) = - new Constraints(map.updated(pt, boundss)) + def updated(pt: PolyType, entries: Array[Type]) = + new Constraints(map.updated(pt, entries)) /** A new constraint which is derived from this constraint by removing * the type parameter `param` from the domain. @@ -60,19 +44,19 @@ object TypeComparers { def - (param: PolyParam) = { val pt = param.binder val pnum = param.paramNum - val boundss = map(pt) + val entries = map(pt) var noneLeft = true var i = 0 - while (noneLeft && (i < boundss.length)) { - noneLeft = boundss(i) == null || i == pnum + while (noneLeft && (i < entries.length)) { + noneLeft = (entries(i) eq NoType) || i == pnum i += 1 } new Constraints( if (noneLeft) map remove pt else { - val newBoundss = boundss.clone - newBoundss(pnum) = null - map.updated(pt, newBoundss) + val newEntries = entries.clone + newEntries(pnum) = NoType + map.updated(pt, newEntries) }) } @@ -84,24 +68,24 @@ object TypeComparers { * of the parameter elsewhere in the constraint by type `tpe`. */ def replace(param: PolyParam, tpe: Type)(implicit ctx: Context) = { - val constr = this - param - def subst(boundss: Array[TypeBounds]) = { - var result = boundss + def subst(entries: Array[Type]) = { + var result = entries var i = 0 - while (i < boundss.length) { - val oldBounds = boundss(i) - if (oldBounds != null) { - val newBounds = oldBounds.subst(param, tpe).asInstanceOf[TypeBounds] - if (oldBounds ne newBounds) { - if (result eq boundss) result = boundss.clone - result(i) = newBounds - } + while (i < entries.length) { + entries(i) match { + case oldBounds: TypeBounds => + val newBounds = oldBounds.subst(param, tpe) + if (oldBounds ne newBounds) { + if (result eq entries) result = entries.clone + result(i) = newBounds + } + case _ => } i += 1 } result } - new Constraints(constr.map mapValues subst) + new Constraints((this - param).map mapValues subst) } } @@ -110,7 +94,13 @@ object TypeComparers { * The constraint set is updated when undetermined type parameters * in the constraint's domain are compared. */ - class TypeComparer(var constraints: Constraints = new Constraints(SimpleMap.Empty))(implicit val ctx: Context) extends DotClass { + class TypeComparer(initConstraints: Constraints = new Constraints(SimpleMap.Empty)) + (implicit val ctx: Context) extends DotClass { + + private var constrs = initConstraints + + final def constraints = constrs + private def constraints_=(c: Constraints) = constrs = c private var pendingSubTypes: mutable.Set[(Type, Type)] = null private var recCount = 0 @@ -122,13 +112,13 @@ object TypeComparers { def addConstraint(param: PolyParam, bounds: TypeBounds): Boolean = { val pt = param.binder val pnum = param.paramNum - val oldBoundss = constraints(pt) - val oldBounds = oldBoundss(pnum) + val oldEntries = constraints(pt) + val oldBounds = oldEntries(pnum).asInstanceOf[TypeBounds] val newBounds = oldBounds & bounds if (oldBounds ne newBounds) { - val newBoundss = oldBoundss.clone - newBoundss(pnum) = newBounds - constraints.updated(pt, newBoundss) + val newEntries = oldEntries.clone + newEntries(pnum) = newBounds + constraints.updated(pt, newEntries) } isSubType(newBounds.lo, newBounds.hi) } @@ -153,7 +143,8 @@ object TypeComparers { * (Such occurrences can arise for F-bounded types). * The type parameter is removed from the constraint's domain and all its * occurrences are replaced by its approximation. - * Returns the approximating type. + * @return the instantiating type + * @pre `param` is associated with type bounds in the current constraint. */ def approximate(param: PolyParam, fromBelow: Boolean): Type = { val removeParam = new TypeMap { @@ -164,7 +155,7 @@ object TypeComparers { } } } - val bounds = constraints(param) + val bounds = constraints(param).asInstanceOf[TypeBounds] val bound = if (fromBelow) bounds.lo else bounds.hi val inst = removeParam(bound) constraints = constraints.replace(param, inst) @@ -233,11 +224,14 @@ object TypeComparers { } case WildcardType | ErrorType => true + case tp2: TypeVar => + firstTry(tp1, tp2.thisInstance) case tp2: PolyParam => - val bounds = constraints(tp2) - if (bounds == null) secondTry(tp1, tp2) - else isSubType(tp1, bounds.lo) || addConstraint(tp2, TypeBounds.lower(tp1)) - case _ => + constraints(tp2) match { + case TypeBounds(lo, _) => isSubType(tp1, lo) || addConstraint(tp2, TypeBounds.lower(tp1)) + case _ => secondTry(tp1, tp2) + } + case _ => secondTry(tp1, tp2) } } @@ -245,10 +239,13 @@ object TypeComparers { def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match { case WildcardType | ErrorType => true + case tp1: TypeVar => + secondTry(tp1.thisInstance, tp2) case tp1: PolyParam => - val bounds = constraints(tp1) - if (bounds == null) thirdTry(tp1, tp2) - else isSubType(bounds.hi, tp2) || addConstraint(tp1, TypeBounds.upper(tp2)) + constraints(tp1) match { + case TypeBounds(_, hi) => isSubType(hi, tp2) || addConstraint(tp1, TypeBounds.upper(tp2)) + case _ => thirdTry(tp1, tp2) + } case _ => thirdTry(tp1, tp2) } diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 37b9b19a5..ce889ecd2 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -117,9 +117,9 @@ object Types { classSymbol is ModuleClass /** Is this type produced as a repair for an error? */ - final def isError(implicit ctx: Context): Boolean = this match { + final def isError(implicit ctx: Context): Boolean = thisInstance match { case ErrorType => true - case _ => (typeSymbol is Erroneous) || (termSymbol is Erroneous) + case tp => (tp.typeSymbol is Erroneous) || (tp.termSymbol is Erroneous) } /** Is some part of this type produced as a repair for an error? */ @@ -144,7 +144,7 @@ object Types { ctx.isVolatile(this) /** Does the type carry an annotation that is an instance of `cls`? */ - final def hasAnnotation(cls: ClassSymbol)(implicit ctx: Context): Boolean = this match { + final def hasAnnotation(cls: ClassSymbol)(implicit ctx: Context): Boolean = thisInstance match { case AnnotatedType(annot, tp) => annot.symbol == cls || tp.hasAnnotation(cls) case _ => false } @@ -159,20 +159,20 @@ object Types { final def existsPart(p: Type => Boolean): Boolean = new ExistsAccumulator(p)(false, this) - /** Returns true if all parts of this type that satisfy predicate `p`. + /** Returns true if all parts of this type satisfy predicate `p`. */ final def forallParts(p: Type => Boolean): Boolean = !existsPart(!p(_)) /** Map function over elements of an AndType, rebuilding with & */ - def mapAnd(f: Type => Type)(implicit ctx: Context): Type = this match { + def mapAnd(f: Type => Type)(implicit ctx: Context): Type = thisInstance match { case AndType(tp1, tp2) => tp1.mapAnd(f) & tp2.mapAnd(f) - case _ => f(this) + case tp => f(tp) } /** Map function over elements of an OrType, rebuilding with | */ - final def mapOr(f: Type => Type)(implicit ctx: Context): Type = this match { + final def mapOr(f: Type => Type)(implicit ctx: Context): Type = thisInstance match { case OrType(tp1, tp2) => tp1.mapOr(f) | tp2.mapOr(f) - case _ => f(this) + case tp => f(tp) } // ----- Associated symbols ---------------------------------------------- @@ -466,6 +466,11 @@ object Types { // ----- Unwrapping types ----------------------------------------------- + /** Map a TypeVar to either its instance if it is instantiated, or its origin, + * if not. Identity on all other types. + */ + def thisInstance: Type = this + /** Widen from singleton type to its underlying non-singleton * base type by applying one or more `underlying` dereferences, * Also go from => T to T. @@ -477,15 +482,15 @@ 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: TypeBounds => tp.hi.widen // needed? case tp: ExprType => tp.resultType.widen case _ => this } /** If this is an alias type, its alias, otherwise the type itself */ - final def dealias(implicit ctx: Context): Type = this match { + final def dealias(implicit ctx: Context): Type = thisInstance match { case tp: TypeRef if (tp.symbol.isAliasType) => tp.info.bounds.hi - case _ => this + case tp => tp } /** Widen from constant type to its underlying non-constant @@ -499,9 +504,9 @@ object Types { /** If this is a refinement type, the unrefined parent, * else the type itself. */ - final def unrefine: Type = this match { + final def unrefine: Type = thisInstance match { case tp @ RefinedType(tycon, _) => tycon.unrefine - case _ => this + case tp => tp } /** Map references to Object to references to Any; needed for Java interop */ @@ -705,7 +710,7 @@ object Types { if (refineCount == 0) null else new mutable.ListBuffer[Type] } - val buf = recur(this, 0) + val buf = recur(thisInstance, 0) if (buf == null) Nil else buf.toList } @@ -737,7 +742,7 @@ object Types { case _ => (n, tp) } - recur(0, this) + recur(0, thisInstance) } /** Given a type alias @@ -822,6 +827,8 @@ object Types { def toText(printer: Printer): Text = printer.toText(this) + def varianceOf(tp: Type): FlagSet = ??? + // ----- hashing ------------------------------------------------------ /** customized hash code of this type. @@ -1477,7 +1484,7 @@ object Types { case class MethodParam(binder: MethodType, paramNum: Int) extends BoundType with SingletonType { type BT = MethodType - override def underlying(implicit ctx: Context) = binder.paramTypes(paramNum) + override def underlying(implicit ctx: Context): Type = binder.paramTypes(paramNum) def copy(bt: BT) = MethodParam(bt, paramNum) // need to customize hashCode and equals to prevent infinite recursion for dep meth types. @@ -1495,11 +1502,11 @@ object Types { case class PolyParam(binder: PolyType, paramNum: Int) extends BoundType { type BT = PolyType - override def underlying(implicit ctx: Context) = binder.paramBounds(paramNum) def copy(bt: BT) = PolyParam(bt, paramNum) + override def underlying(implicit ctx: Context): Type = binder.paramBounds(paramNum) // no customized hashCode/equals 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 @@ -1515,6 +1522,16 @@ object Types { override def toString = s"RefinedThis(${binder.hashCode})" } + final case class TypeVar(origin: PolyParam) extends UncachedProxyType with ValueType { + private var inst: Type = NoType + def isInstantiated = inst ne NoType + def instantiateWith(tp: Type) = inst = tp + override def thisInstance = if (isInstantiated) inst else origin + override def underlying(implicit ctx: Context): Type = thisInstance + override def equals(that: Any) = this eq that.asInstanceOf[AnyRef] + override def toString = thisInstance.toString + } + // ------ ClassInfo, Type Bounds ------------------------------------------------------------ /** The info of a class during a period, roughly @@ -1757,6 +1774,9 @@ object Types { case tp @ AnnotatedType(annot, underlying) => tp.derivedAnnotatedType(mapOver(annot), this(underlying)) + case tp @ TypeVar(_) => + apply(tp.thisInstance) + case _ => tp } @@ -1836,6 +1856,9 @@ object Types { case AnnotatedType(annot, underlying) => this(this(x, annot), underlying) + case tp: TypeVar => + foldOver(x, tp.thisInstance) + case _ => x } } |