From 78e6cc748b4dcde30bdac3618c4804ff65f32e45 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 17 Mar 2017 14:02:29 +0100 Subject: Make PolyTypes subtypes of LambdaTypes Also, rename LambdaOver{Type,Term}s to {Type,Term}Lambda --- .../src/dotty/tools/dotc/core/Constraint.scala | 18 ++-- .../dotty/tools/dotc/core/OrderingConstraint.scala | 54 +++++----- .../src/dotty/tools/dotc/core/TyperState.scala | 6 +- compiler/src/dotty/tools/dotc/core/Types.scala | 109 ++++++++++----------- 4 files changed, 89 insertions(+), 98 deletions(-) (limited to 'compiler/src/dotty/tools/dotc/core') diff --git a/compiler/src/dotty/tools/dotc/core/Constraint.scala b/compiler/src/dotty/tools/dotc/core/Constraint.scala index fe14aa53c..7a0e6dece 100644 --- a/compiler/src/dotty/tools/dotc/core/Constraint.scala +++ b/compiler/src/dotty/tools/dotc/core/Constraint.scala @@ -13,17 +13,17 @@ import config.Printers.constr /** Constraint over undetermined type parameters. Constraints are built * over values of the following types: * - * - PolyType A constraint constrains the type parameters of a set of PolyTypes - * - TypeParamRef The parameters of the constrained polytypes - * - TypeVar Every constrained parameter might be associated with a TypeVar - * that has the TypeParamRef as origin. + * - TypeLambda A constraint constrains the type parameters of a set of TypeLambdas + * - TypeParamRef The parameters of the constrained polytypes + * - TypeVar Every constrained parameter might be associated with a TypeVar + * that has the TypeParamRef as origin. */ abstract class Constraint extends Showable { type This <: Constraint /** Does the constraint's domain contain the type parameters of `pt`? */ - def contains(pt: PolyType): Boolean + def contains(pt: TypeLambda): Boolean /** Does the constraint's domain contain the type parameter `param`? */ def contains(param: TypeParamRef): Boolean @@ -79,7 +79,7 @@ abstract class Constraint extends Showable { * satisfiability but will solved to give instances of * type variables. */ - def add(poly: PolyType, tvars: List[TypeVar])(implicit ctx: Context): This + def add(poly: TypeLambda, tvars: List[TypeVar])(implicit ctx: Context): This /** A new constraint which is derived from this constraint by updating * the entry for parameter `param` to `tp`. @@ -115,13 +115,13 @@ abstract class Constraint extends Showable { * all type parameters of the entry are associated with type variables * which have their `inst` fields set. */ - def isRemovable(pt: PolyType): Boolean + def isRemovable(pt: TypeLambda): Boolean /** A new constraint with all entries coming from `pt` removed. */ - def remove(pt: PolyType)(implicit ctx: Context): This + def remove(pt: TypeLambda)(implicit ctx: Context): This /** The polytypes constrained by this constraint */ - def domainPolys: List[PolyType] + def domainPolys: List[TypeLambda] /** The polytype parameters constrained by this constraint */ def domainParams: List[TypeParamRef] diff --git a/compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala b/compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala index dbb952369..2dff39c37 100644 --- a/compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala +++ b/compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala @@ -14,7 +14,7 @@ import annotation.tailrec object OrderingConstraint { - type ArrayValuedMap[T] = SimpleMap[PolyType, Array[T]] + type ArrayValuedMap[T] = SimpleMap[TypeLambda, Array[T]] /** The type of `OrderingConstraint#boundsMap` */ type ParamBounds = ArrayValuedMap[Type] @@ -32,11 +32,11 @@ object OrderingConstraint { /** A lens for updating a single entry array in one of the three constraint maps */ abstract class ConstraintLens[T <: AnyRef: ClassTag] { - def entries(c: OrderingConstraint, poly: PolyType): Array[T] - def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[T])(implicit ctx: Context): OrderingConstraint + def entries(c: OrderingConstraint, poly: TypeLambda): Array[T] + def updateEntries(c: OrderingConstraint, poly: TypeLambda, entries: Array[T])(implicit ctx: Context): OrderingConstraint def initial: T - def apply(c: OrderingConstraint, poly: PolyType, idx: Int) = { + def apply(c: OrderingConstraint, poly: TypeLambda, idx: Int) = { val es = entries(c, poly) if (es == null) initial else es(idx) } @@ -47,7 +47,7 @@ object OrderingConstraint { * parts of `current` which are not shared by `prev`. */ def update(prev: OrderingConstraint, current: OrderingConstraint, - poly: PolyType, idx: Int, entry: T)(implicit ctx: Context): OrderingConstraint = { + poly: TypeLambda, idx: Int, entry: T)(implicit ctx: Context): OrderingConstraint = { var es = entries(current, poly) if (es != null && (es(idx) eq entry)) current else { @@ -72,7 +72,7 @@ object OrderingConstraint { update(prev, current, param.binder, param.paramNum, entry) def map(prev: OrderingConstraint, current: OrderingConstraint, - poly: PolyType, idx: Int, f: T => T)(implicit ctx: Context): OrderingConstraint = + poly: TypeLambda, idx: Int, f: T => T)(implicit ctx: Context): OrderingConstraint = update(prev, current, poly, idx, f(apply(current, poly, idx))) def map(prev: OrderingConstraint, current: OrderingConstraint, @@ -81,25 +81,25 @@ object OrderingConstraint { } val boundsLens = new ConstraintLens[Type] { - def entries(c: OrderingConstraint, poly: PolyType): Array[Type] = + def entries(c: OrderingConstraint, poly: TypeLambda): Array[Type] = c.boundsMap(poly) - def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[Type])(implicit ctx: Context): OrderingConstraint = + def updateEntries(c: OrderingConstraint, poly: TypeLambda, entries: Array[Type])(implicit ctx: Context): OrderingConstraint = newConstraint(c.boundsMap.updated(poly, entries), c.lowerMap, c.upperMap) def initial = NoType } val lowerLens = new ConstraintLens[List[TypeParamRef]] { - def entries(c: OrderingConstraint, poly: PolyType): Array[List[TypeParamRef]] = + def entries(c: OrderingConstraint, poly: TypeLambda): Array[List[TypeParamRef]] = c.lowerMap(poly) - def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[List[TypeParamRef]])(implicit ctx: Context): OrderingConstraint = + def updateEntries(c: OrderingConstraint, poly: TypeLambda, entries: Array[List[TypeParamRef]])(implicit ctx: Context): OrderingConstraint = newConstraint(c.boundsMap, c.lowerMap.updated(poly, entries), c.upperMap) def initial = Nil } val upperLens = new ConstraintLens[List[TypeParamRef]] { - def entries(c: OrderingConstraint, poly: PolyType): Array[List[TypeParamRef]] = + def entries(c: OrderingConstraint, poly: TypeLambda): Array[List[TypeParamRef]] = c.upperMap(poly) - def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[List[TypeParamRef]])(implicit ctx: Context): OrderingConstraint = + def updateEntries(c: OrderingConstraint, poly: TypeLambda, entries: Array[List[TypeParamRef]])(implicit ctx: Context): OrderingConstraint = newConstraint(c.boundsMap, c.lowerMap, c.upperMap.updated(poly, entries)) def initial = Nil } @@ -109,19 +109,19 @@ import OrderingConstraint._ /** Constraint over undetermined type parameters that keeps separate maps to * reflect parameter orderings. - * @param boundsMap a map from PolyType to arrays. + * @param boundsMap a map from TypeLambda to arrays. * Each array contains twice the number of entries as there a type parameters - * in the PolyType. The first half of the array contains the type bounds that constrain the + * in the TypeLambda. The first half of the array contains the type bounds that constrain the * polytype's type parameters. The second half might contain type variables that * track the corresponding parameters, or is left empty (filled with nulls). * An instantiated type parameter is represented by having its instance type in * the corresponding array entry. The dual use of arrays for poly params * and typevars is to save space and hopefully gain some speed. * - * @param lowerMap a map from PolyTypes to arrays. Each array entry corresponds + * @param lowerMap a map from TypeLambdas to arrays. Each array entry corresponds * to a parameter P of the polytype; it contains all constrained parameters * Q that are known to be smaller than P, i.e. Q <: P. - * @param upperMap a map from PolyTypes to arrays. Each array entry corresponds + * @param upperMap a map from TypeLambdas to arrays. Each array entry corresponds * to a parameter P of the polytype; it contains all constrained parameters * Q that are known to be greater than P, i.e. P <: Q. */ @@ -149,7 +149,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, // ----------- Contains tests -------------------------------------------------- - def contains(pt: PolyType): Boolean = boundsMap(pt) != null + def contains(pt: TypeLambda): Boolean = boundsMap(pt) != null def contains(param: TypeParamRef): Boolean = { val entries = boundsMap(param.binder) @@ -212,7 +212,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, } } -// ---------- Adding PolyTypes -------------------------------------------------- +// ---------- Adding TypeLambdas -------------------------------------------------- /** The list of parameters P such that, for a fresh type parameter Q: * @@ -280,7 +280,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, stripParams(tp, paramBuf, isUpper) .orElse(if (isUpper) defn.AnyType else defn.NothingType) - def add(poly: PolyType, tvars: List[TypeVar])(implicit ctx: Context): This = { + def add(poly: TypeLambda, tvars: List[TypeVar])(implicit ctx: Context): This = { assert(!contains(poly)) val nparams = poly.paramNames.length val entries1 = new Array[Type](nparams * 2) @@ -293,7 +293,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, * Update all bounds to be normalized and update ordering to account for * dependent parameters. */ - private def init(poly: PolyType)(implicit ctx: Context): This = { + private def init(poly: TypeLambda)(implicit ctx: Context): This = { var current = this val loBuf, hiBuf = new mutable.ListBuffer[TypeParamRef] var i = 0 @@ -392,7 +392,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, def removeParam(ps: List[TypeParamRef]) = ps.filterNot(p => p.binder.eq(poly) && p.paramNum == idx) - def replaceParam(tp: Type, atPoly: PolyType, atIdx: Int): Type = tp match { + def replaceParam(tp: Type, atPoly: TypeLambda, atIdx: Int): Type = tp match { case bounds @ TypeBounds(lo, hi) => def recombine(andor: AndOrType, op: (Type, Boolean) => Type, isUpper: Boolean): Type = { @@ -432,9 +432,9 @@ class OrderingConstraint(private val boundsMap: ParamBounds, } } - def remove(pt: PolyType)(implicit ctx: Context): This = { + def remove(pt: TypeLambda)(implicit ctx: Context): This = { def removeFromOrdering(po: ParamOrdering) = { - def removeFromBoundss(key: PolyType, bndss: Array[List[TypeParamRef]]): Array[List[TypeParamRef]] = { + def removeFromBoundss(key: TypeLambda, bndss: Array[List[TypeParamRef]]): Array[List[TypeParamRef]] = { val bndss1 = bndss.map(_.filterConserve(_.binder ne pt)) if (bndss.corresponds(bndss1)(_ eq _)) bndss else bndss1 } @@ -443,7 +443,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, newConstraint(boundsMap.remove(pt), removeFromOrdering(lowerMap), removeFromOrdering(upperMap)) } - def isRemovable(pt: PolyType): Boolean = { + def isRemovable(pt: TypeLambda): Boolean = { val entries = boundsMap(pt) @tailrec def allRemovable(last: Int): Boolean = if (last < 0) true @@ -456,7 +456,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, // ---------- Exploration -------------------------------------------------------- - def domainPolys: List[PolyType] = boundsMap.keys + def domainPolys: List[TypeLambda] = boundsMap.keys def domainParams: List[TypeParamRef] = for { @@ -473,7 +473,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, true } - def foreachParam(p: (PolyType, Int) => Unit): Unit = + def foreachParam(p: (TypeLambda, Int) => Unit): Unit = boundsMap.foreachBinding { (poly, entries) => 0.until(poly.paramNames.length).foreach(p(poly, _)) } @@ -533,7 +533,7 @@ class OrderingConstraint(private val boundsMap: ParamBounds, override def checkClosed()(implicit ctx: Context): Unit = { def isFreeTypeParamRef(tp: Type) = tp match { - case TypeParamRef(binder: PolyType, _) => !contains(binder) + case TypeParamRef(binder: TypeLambda, _) => !contains(binder) case _ => false } def checkClosedType(tp: Type, where: String) = diff --git a/compiler/src/dotty/tools/dotc/core/TyperState.scala b/compiler/src/dotty/tools/dotc/core/TyperState.scala index 08bef86b7..b33b3aa29 100644 --- a/compiler/src/dotty/tools/dotc/core/TyperState.scala +++ b/compiler/src/dotty/tools/dotc/core/TyperState.scala @@ -155,14 +155,14 @@ extends TyperState(r) { } override def gc()(implicit ctx: Context): Unit = { - val toCollect = new mutable.ListBuffer[PolyType] + val toCollect = new mutable.ListBuffer[TypeLambda] constraint foreachTypeVar { tvar => if (!tvar.inst.exists) { val inst = instType(tvar) if (inst.exists && (tvar.owningState eq this)) { tvar.inst = inst - val poly = tvar.origin.binder - if (constraint.isRemovable(poly)) toCollect += poly + val lam = tvar.origin.binder + if (constraint.isRemovable(lam)) toCollect += lam } } } diff --git a/compiler/src/dotty/tools/dotc/core/Types.scala b/compiler/src/dotty/tools/dotc/core/Types.scala index 59c84910b..be861d863 100644 --- a/compiler/src/dotty/tools/dotc/core/Types.scala +++ b/compiler/src/dotty/tools/dotc/core/Types.scala @@ -2319,10 +2319,10 @@ object Types { /** The lambda type square: * - * LambdaType | LambdaOverTerms | LambdaOverTypes + * LambdaType | TermLambda | TypeLambda * ------------+-------------------+------------------ * Proxy (hk) | HKTermLambda | HKTypeLambda - * Ground (*) | MethodType | PolyType + * Ground (*) | MethodType | PolyType */ trait LambdaType extends BindingType with MethodOrPoly { self => type ThisName <: Name @@ -2346,6 +2346,8 @@ object Types { lazy val paramRefs: List[ParamRef] = paramNames.indices.toList.map(newParamRef) + protected def computeSignature(implicit ctx: Context) = resultSignature + def instantiate(argTypes: => List[Type])(implicit ctx: Context): Type = if (isDependent) resultType.substParams(this, argTypes) else resultType @@ -2364,13 +2366,16 @@ object Types { case _ => false } + + protected def prefixString: String + override def toString = s"$prefixString($paramNames, $paramInfos, $resType)" } - trait LambdaOverTerms extends LambdaType { thisLambdaType => - import LambdaOverTerms._ + trait TermLambda extends LambdaType { thisLambdaType => + import TermLambda._ type ThisName = TermName type PInfo = Type - type This = LambdaOverTerms + type This = TermLambda def paramNames: List[TermName] @@ -2465,7 +2470,7 @@ object Types { def newParamRef(n: Int) = TermParamRef(this, n) } - object LambdaOverTerms { + object TermLambda { private type DependencyStatus = Byte private final val Unknown: DependencyStatus = 0 // not yet computed private final val NoDeps: DependencyStatus = 1 // no dependent parameters found @@ -2475,12 +2480,10 @@ object Types { private final val Provisional: DependencyStatus = 4 // set if dependency status can still change due to type variable instantiations } - type LambdaOverTypes = PolyType // (for now) - abstract case class MethodType(paramNames: List[TermName])( paramInfosExp: MethodType => List[Type], resultTypeExp: MethodType => Type) - extends CachedGroundType with TermType with LambdaOverTerms with NarrowCached { thisMethodType => + extends CachedGroundType with TermType with TermLambda with NarrowCached { thisMethodType => import MethodType._ protected def companion: MethodTypeCompanion @@ -2492,7 +2495,7 @@ object Types { val resType = resultTypeExp(this) assert(resType.exists) - protected def computeSignature(implicit ctx: Context): Signature = + override def computeSignature(implicit ctx: Context): Signature = resultSignature.prepend(paramInfos, isJava) def derivedMethodType(paramNames: List[TermName] = this.paramNames, @@ -2508,7 +2511,6 @@ object Types { override def computeHash = doHash(paramNames, resType, paramInfos) protected def prefixString = "MethodType" - override def toString = s"$prefixString($paramNames, $paramInfos, $resType)" } final class CachedMethodType(paramNames: List[TermName])(paramInfosExp: MethodType => List[Type], resultTypeExp: MethodType => Type) @@ -2633,6 +2635,35 @@ object Types { } } + trait TypeLambda extends LambdaType { + type ThisName = TypeName + type PInfo = TypeBounds + type This = TypeLambda + + def isDependent(implicit ctx: Context): Boolean = true + + def newParamRef(n: Int) = TypeParamRef(this, n) + + lazy val typeParams: List[LambdaParam] = + paramNames.indices.toList.map(new LambdaParam(this, _)) + + /** Instantiate parameter bounds by substituting parameters with given arguments */ + final def instantiateBounds(argTypes: List[Type])(implicit ctx: Context): List[Type] = + paramInfos.mapConserve(_.substParams(this, argTypes)) + + def derivedLambdaAbstraction(paramNames: List[TypeName], paramInfos: List[TypeBounds], resType: Type)(implicit ctx: Context): Type = + resType match { + case resType @ TypeAlias(alias) => + resType.derivedTypeAlias(newLikeThis(paramNames, paramInfos, alias)) + case resType @ TypeBounds(lo, hi) => + resType.derivedTypeBounds( + if (lo.isRef(defn.NothingClass)) lo else newLikeThis(paramNames, paramInfos, lo), + newLikeThis(paramNames, paramInfos, hi)) + case _ => + derivedLambdaType(paramNames, paramInfos, resType) + } + } + /** A type lambda of the form `[X_0 B_0, ..., X_n B_n] => T` * This is used both as a type of a polymorphic method and as a type of * a higher-kinded type parameter. Variances are encoded in parameter @@ -2648,11 +2679,7 @@ object Types { */ class PolyType(val paramNames: List[TypeName])( paramInfosExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) - extends CachedProxyType with LambdaType { - - type ThisName = TypeName - type PInfo = TypeBounds - type This = PolyType + extends CachedProxyType with TypeLambda { /** The bounds of the type parameters */ val paramInfos: List[TypeBounds] = paramInfosExp(this) @@ -2663,22 +2690,8 @@ object Types { assert(resType.isInstanceOf[TermType], this) assert(paramNames.nonEmpty) - protected def computeSignature(implicit ctx: Context) = resultSignature - - lazy val typeParams: List[LambdaParam] = - paramNames.indices.toList.map(new LambdaParam(this, _)) - - override def resultType(implicit ctx: Context) = resType override def underlying(implicit ctx: Context) = resType - def isDependent(implicit ctx: Context) = true - def isParamDependent(implicit ctx: Context) = true - def newParamRef(n: Int) = TypeParamRef(this, n) - - /** Instantiate parameter bounds by substituting parameters with given arguments */ - final def instantiateBounds(argTypes: List[Type])(implicit ctx: Context): List[Type] = - paramInfos.mapConserve(_.substParams(this, argTypes)) - def newLikeThis(paramNames: List[TypeName], paramInfos: List[TypeBounds], resType: Type)(implicit ctx: Context): PolyType = PolyType.apply(paramNames)( x => paramInfos.mapConserve(_.subst(this, x).bounds), @@ -2687,20 +2700,7 @@ object Types { def derivedPolyType(paramNames: List[TypeName] = this.paramNames, paramInfos: List[TypeBounds] = this.paramInfos, resType: Type = this.resType)(implicit ctx: Context) = - if ((paramNames eq this.paramNames) && (paramInfos eq this.paramInfos) && (resType eq this.resType)) this - else newLikeThis(paramNames, paramInfos, resType) - - def derivedLambdaAbstraction(paramNames: List[TypeName], paramInfos: List[TypeBounds], resType: Type)(implicit ctx: Context): Type = - resType match { - case resType @ TypeAlias(alias) => - resType.derivedTypeAlias(newLikeThis(paramNames, paramInfos, alias)) - case resType @ TypeBounds(lo, hi) => - resType.derivedTypeBounds( - if (lo.isRef(defn.NothingClass)) lo else newLikeThis(paramNames, paramInfos, lo), - newLikeThis(paramNames, paramInfos, hi)) - case _ => - derivedPolyType(paramNames, paramInfos, resType) - } + derivedLambdaType(paramNames, paramInfos, resType) /** Merge nested polytypes into one polytype. nested polytypes are normally not supported * but can arise as temporary data structures. @@ -2729,16 +2729,7 @@ object Types { case tparams: List[Symbol @unchecked] => tp.subst(tparams, paramRefs) } - override def equals(other: Any) = other match { - case other: PolyType => - other.paramNames == this.paramNames && - other.paramInfos == this.paramInfos && - other.resType == this.resType - case _ => false - } - - override def toString = s"PolyType($paramNames, $paramInfos, $resType)" - + protected def prefixString = "PolyType" override def computeHash = doHash(paramNames, resType, paramInfos) } @@ -2760,7 +2751,7 @@ object Types { // ----- HK types: LambdaParam, HKApply --------------------- /** The parameter of a type lambda */ - case class LambdaParam(tl: PolyType, n: Int) extends ParamInfo { + case class LambdaParam(tl: TypeLambda, n: Int) extends ParamInfo { def isTypeParam(implicit ctx: Context) = tl.paramNames.head.isTypeName def paramName(implicit ctx: Context): TypeName = tl.paramNames(n) def paramInfo(implicit ctx: Context): Type = tl.paramInfos(n) @@ -2879,13 +2870,13 @@ object Types { } } - case class TermParamRef(binder: LambdaOverTerms, paramNum: Int) extends ParamRef { - type BT = LambdaOverTerms + case class TermParamRef(binder: TermLambda, paramNum: Int) extends ParamRef { + type BT = TermLambda def copyBoundType(bt: BT) = TermParamRef(bt, paramNum) } - case class TypeParamRef(binder: LambdaOverTypes, paramNum: Int) extends ParamRef { - type BT = LambdaOverTypes + case class TypeParamRef(binder: TypeLambda, paramNum: Int) extends ParamRef { + type BT = TypeLambda def copyBoundType(bt: BT) = TypeParamRef(bt, paramNum) /** Looking only at the structure of `bound`, is one of the following true? -- cgit v1.2.3