From adcc240c565071b2a2b825e413579edddfa3ebd7 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sat, 31 Jan 2015 19:50:20 +0100 Subject: Removed TrackingConstraint It's too hard to keep fixes up-to-date in both constraint implementations. And anyway, OrderingConstraint is it for now. Also added comment suggested by @smarter. --- src/dotty/tools/dotc/core/OrderingConstraint.scala | 4 + src/dotty/tools/dotc/core/TrackingConstraint.scala | 480 --------------------- 2 files changed, 4 insertions(+), 480 deletions(-) delete mode 100644 src/dotty/tools/dotc/core/TrackingConstraint.scala (limited to 'src/dotty') diff --git a/src/dotty/tools/dotc/core/OrderingConstraint.scala b/src/dotty/tools/dotc/core/OrderingConstraint.scala index 65185ff4f..53378435e 100644 --- a/src/dotty/tools/dotc/core/OrderingConstraint.scala +++ b/src/dotty/tools/dotc/core/OrderingConstraint.scala @@ -288,6 +288,10 @@ class OrderingConstraint(private val boundsMap: ParamBounds, newConstraint(boundsMap.updated(poly, entries1), lowerMap, upperMap).init(poly) } + /** Split dependent parameters off the bounds for parameters in `poly`. + * Update all bounds to be normalized and update ordering to account for + * dependent parameters. + */ private def init(poly: PolyType)(implicit ctx: Context): This = { var current = this val loBuf, hiBuf = new mutable.ListBuffer[PolyParam] diff --git a/src/dotty/tools/dotc/core/TrackingConstraint.scala b/src/dotty/tools/dotc/core/TrackingConstraint.scala deleted file mode 100644 index fc8a083f4..000000000 --- a/src/dotty/tools/dotc/core/TrackingConstraint.scala +++ /dev/null @@ -1,480 +0,0 @@ -package dotty.tools -package dotc -package core - -import Types._, Contexts._, Symbols._, Decorators._ -import util.SimpleMap -import collection.mutable -import printing.{Printer, Showable} -import printing.Texts._ -import config.Config -import config.Printers._ -import collection.immutable.BitSet -import reflect.ClassTag - -object TrackingConstraint { - - /** The type of `Constraint#myMap` */ - type ParamInfo = SimpleMap[PolyType, Array[Type]] - -} - -import TrackingConstraint._ - -/** Constraint over undetermined type parameters - * @param myMap a map from PolyType 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 - * 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. - */ -class TrackingConstraint(private val myMap: ParamInfo, - private val less: Array[BitSet], - private val params: Array[PolyParam]) extends Constraint { - - type This = TrackingConstraint - - assert(less.length == params.length) - - /** A new constraint which is derived from this constraint by adding or replacing - * the entries corresponding to `pt` with `entries`. - */ - private def newConstraint(myMap: ParamInfo, less: Array[BitSet], params: Array[PolyParam])(implicit ctx: Context) : TrackingConstraint = { - val result = new TrackingConstraint(myMap, less, params) - if (Config.checkConstraintsNonCyclic) result.checkNonCyclic() - ctx.runInfo.recordConstraintSize(result, result.myMap.size) - result - } - -// ----------- Basic indices -------------------------------------------------- - - /** The immutable array of constrained polytypes */ - private val polyTypes = new Array[PolyType](myMap.size) - - /** The start positions of parameters of constrained polytypes in `params` and `less` */ - private val polyStart = new Array[Int](myMap.size) - - { - var idx = 0 - var count = 0 - myMap.foreachBinding { (pt, _) => - polyTypes(idx) = pt - polyStart(idx) = count - count += pt.paramNames.length - idx += 1 - } - assert(count == params.length) - } - - /** The index of given polytype `pt` in this constraint, - * or `polyTypes.length` if constraint does not contain `pt`. - */ - private def polyIndex(pt: PolyType): Int = { - var i = 0 - while (i < polyTypes.length && (polyTypes(i) ne pt)) i += 1 - i - } - - /** The index of the first parameter of given polytype `pt` in this constraint */ - private def polyStart(pt: PolyType): Int = this.polyStart.apply(polyIndex(pt)) - - /** The index of `param` in `params` and `less` */ - private def paramIndex(param: PolyParam): Int = { - assert(contains(param.binder)) - polyStart(param.binder) + param.paramNum - } - - /** The number of type parameters in the given entry array */ - private def paramCount(entries: Array[Type]) = entries.length >> 1 - - /** The type variable corresponding to parameter numbered `n`, null if none was created */ - private def typeVar(entries: Array[Type], n: Int): Type = - entries(paramCount(entries) + n) - - def entry(param: PolyParam): Type = { - val entries = myMap(param.binder) - if (entries == null) NoType - else entries(param.paramNum) - } - -// ----------- Contains tests -------------------------------------------------- - - def contains(pt: PolyType): Boolean = polyIndex(pt) < polyTypes.length - - def contains(param: PolyParam): Boolean = { - val entries = myMap(param.binder) - entries != null && entries(param.paramNum).isInstanceOf[TypeBounds] - } - - def contains(tvar: TypeVar): Boolean = { - val origin = tvar.origin - val entries = myMap(origin.binder) - val pnum = origin.paramNum - entries != null && isBounds(entries(pnum)) && (typeVar(entries, pnum) eq tvar) - } - - private def isBounds(tp: Type) = tp.isInstanceOf[TypeBounds] - -// ---------- Dependency handling ---------------------------------------------- - - private def upperBits(less: Array[BitSet], i: Int): BitSet = less(i) - - private def lowerBits(less: Array[BitSet], i: Int): BitSet = - (BitSet() /: less.indices) ((bits, j) => if (less(j)(i)) bits + j else bits) - - private def minUpperBits(less: Array[BitSet], i: Int): BitSet = { - val all = upperBits(less, i) - all.filterNot(j => all.exists(k => less(k)(j))) - } - - private def minLowerBits(less: Array[BitSet], i: Int): BitSet = { - val all = lowerBits(less, i) - all.filterNot(j => all.exists(k => less(j)(k))) - } - - private def overParams(op: (Array[BitSet], Int) => BitSet): PolyParam => List[PolyParam] = param => - op(less, paramIndex(param)).toList.map(params).filter(contains) - - val allUpper = overParams(upperBits) - val allLower = overParams(lowerBits) - val minUpper = overParams(minUpperBits) - val minLower = overParams(minLowerBits) - - def upper(param: PolyParam): List[PolyParam] = allUpper(param) - def lower(param: PolyParam): List[PolyParam] = allLower(param) - - def exclusiveLower(param: PolyParam, butNot: PolyParam): List[PolyParam] = { - val excluded = lowerBits(less, paramIndex(butNot)) - overParams(lowerBits(_, _) &~ excluded)(param) - } - - def exclusiveUpper(param: PolyParam, butNot: PolyParam): List[PolyParam] = { - val excluded = upperBits(less, paramIndex(butNot)) - overParams(upperBits(_, _) &~ excluded)(param) - } - -// ---------- Info related to PolyParams ------------------------------------------- - - def isLess(param1: PolyParam, param2: PolyParam): Boolean = - less(paramIndex(param1))(paramIndex(param2)) - - def nonParamBounds(param: PolyParam): TypeBounds = - entry(param).asInstanceOf[TypeBounds] - - def fullLowerBound(param: PolyParam)(implicit ctx: Context): Type = - (nonParamBounds(param).lo /: minLower(param))(_ | _) - - def fullUpperBound(param: PolyParam)(implicit ctx: Context): Type = - (nonParamBounds(param).hi /: minUpper(param))(_ & _) - - def fullBounds(param: PolyParam)(implicit ctx: Context): TypeBounds = - nonParamBounds(param).derivedTypeBounds(fullLowerBound(param), fullUpperBound(param)) - - def typeVarOfParam(param: PolyParam): Type = { - val entries = myMap(param.binder) - if (entries == null) NoType - else { - val tvar = typeVar(entries, param.paramNum) - if (tvar != null) tvar else NoType - } - } - -// ---------- Adding PolyTypes -------------------------------------------------- - - /** The bound type `tp` without dependent parameters - * NoType if type consists only of dependent parameters. - * @param seenFromBelow If true, `bound` is an upper bound, else a lower bound. - */ - private def stripParams(tp: Type, handleParam: (PolyParam, Boolean) => Type, - seenFromBelow: Boolean)(implicit ctx: Context): Type = tp match { - case tp: PolyParam => - handleParam(tp, seenFromBelow) - case tp: AndOrType if seenFromBelow == tp.isAnd => - val tp1 = stripParams(tp.tp1, handleParam, seenFromBelow) - val tp2 = stripParams(tp.tp2, handleParam, seenFromBelow) - if (tp1.exists) - if (tp2.exists) tp.derivedAndOrType(tp1, tp2) - else tp1 - else tp2 - case _ => - tp - } - - /** The bound type `tp` without dependent parameters. - * A top or bottom type if type consists only of dependent parameters. - * @param seenFromBelow If true, `bound` is an upper bound, else a lower bound. - */ - private def nonParamType(tp: Type, handleParam: (PolyParam, Boolean) => Type, - seenFromBelow: Boolean)(implicit ctx: Context): Type = - stripParams(tp, handleParam, seenFromBelow) - .orElse(if (seenFromBelow) defn.AnyType else defn.NothingType) - - /** The bounds of `tp1` without dependent parameters. - * @pre `tp` is a TypeBounds type. - */ - private def nonParamBounds(tp: Type, handleParam: (PolyParam, Boolean) => Type)(implicit ctx: Context): Type = tp match { - case tp @ TypeBounds(lo, hi) => - tp.derivedTypeBounds( - nonParamType(lo, handleParam, seenFromBelow = false), - nonParamType(hi, handleParam, seenFromBelow = true)) - } - - def add(poly: PolyType, tvars: List[TypeVar])(implicit ctx: Context): This = { - assert(!contains(poly)) - val nparams = poly.paramNames.length - val entries1 = new Array[Type](nparams * 2) - poly.paramBounds.copyToArray(entries1, 0) - tvars.copyToArray(entries1, nparams) - val is = poly.paramBounds.indices - val newParams = is.map(PolyParam(poly, _)) - val params1 = params ++ newParams - var less1 = less ++ is.map(Function.const(BitSet.empty)) - for (i <- is) { - def handleParam(param: PolyParam, seenFromBelow: Boolean): Type = { - def record(paramIdx: Int): Type = { - less1 = - if (seenFromBelow) updatedLess(less1, nparams + i, paramIdx) - else updatedLess(less1, paramIdx, nparams + i) - NoType - } - if (param.binder eq poly) record(nparams + param.paramNum) - else if (contains(param.binder)) record(paramIndex(param)) - else param - } - entries1(i) = nonParamBounds(entries1(i), handleParam) - } - newConstraint(myMap.updated(poly, entries1), less1, params1) - } - -// ---------- Updates ------------------------------------------------------------ - - /** An updated partial order matrix that incorporates `less` and also reflects that `param` relates - * to `p2` wrt <:< if `inOrder` is true, `>:>` otherwise. - */ - private def updatedLess(less: Array[BitSet], i1: Int, i2: Int): Array[BitSet] = { - if (i1 == i2 || less(i1)(i2)) less - else { - val result = less.clone - val newUpper = upperBits(less, i2) + i2 - def update(j: Int) = { - result(j) |= newUpper - assert(!result(j)(j)) - } - update(i1) - lowerBits(less, i1).foreach(update) - result - } - } - - def addLess(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): This = { - val less1 = updatedLess(less, paramIndex(p1), paramIndex(p2)) - if (less1 eq less) this else newConstraint(myMap, less1, params) - } - - def updateEntry(param: PolyParam, tp: Type)(implicit ctx: Context): This = { - val entries = myMap(param.binder) - val entry = entries(param.paramNum) - if (entry eq tp) this - else { - val entries1 = entries.clone - entries1(param.paramNum) = tp - newConstraint(myMap.updated(param.binder, entries1), less, params) - } - } - - def unify(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): This = { - val p1Bounds = (nonParamBounds(p1) & nonParamBounds(p2)).substParam(p2, p1) - updateEntry(p1, p1Bounds).replace(p2, p1) - } - - def narrowBound(param: PolyParam, bound: Type, isUpper: Boolean)(implicit ctx: Context): This = { - val oldBounds @ TypeBounds(lo, hi) = nonParamBounds(param) - val newBounds = - if (isUpper) oldBounds.derivedTypeBounds(lo, hi & bound) - else oldBounds.derivedTypeBounds(lo | bound, hi) - if (newBounds eq oldBounds) this - else updateEntry(param, newBounds) - } - -// ---------- Removals ------------------------------------------------------------ - - /** Drop parameter `PolyParam(poly, n)` from `bounds`, - * replacing with Nothing in the lower bound and by `Any` in the upper bound. - */ - private def dropParamIn(bounds: TypeBounds, poly: PolyType, n: Int)(implicit ctx: Context): TypeBounds = { - def drop(tp: Type): Type = tp match { - case tp: AndOrType => - val tp1 = drop(tp.tp1) - val tp2 = drop(tp.tp2) - if (!tp1.exists) tp2 - else if (!tp2.exists) tp1 - else tp - case PolyParam(`poly`, `n`) => NoType - case _ => tp - } - def approx(tp: Type, limit: Type): Type = { - val tp1 = drop(tp) - if (tp1.exists || !tp.exists) tp1 else limit - } - bounds.derivedTypeBounds( - approx(bounds.lo, defn.NothingType), approx(bounds.hi, defn.AnyType)) - } - - def replace(param: PolyParam, tp: Type)(implicit ctx: Context): TrackingConstraint = { - val replacement = tp.dealias.stripTypeVar - - def subst(poly: PolyType, entries: Array[Type]) = { - var result = entries - var i = 0 - while (i < paramCount(entries)) { - entries(i) match { - case oldBounds: TypeBounds => - val newBounds = oldBounds.substParam(param, replacement).asInstanceOf[TypeBounds] - if (oldBounds ne newBounds) { - if (result eq entries) result = entries.clone - result(i) = dropParamIn(newBounds, poly, i) - } - case _ => - } - i += 1 - } - result - } - - if (param == replacement) this - else { - assert(replacement.isValueType) - val pt = param.binder - val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updateEntry(param, replacement) - newConstraint(constr1.myMap mapValues subst, constr1.less, constr1.params) - } - } - - def remove(pt: PolyType)(implicit ctx: Context): This = { - val start = polyStart(pt) - val skipped = pt.paramNames.length - - def shrinkSet(bits: BitSet): BitSet = - (BitSet() /: bits) ((res, i) => - if (i < start) res + i - else if (i < start + skipped) res - else res + (i - skipped)) - def shrinkArray[T: ClassTag](src: Array[T]) = { - val dst = new Array[T](src.length - skipped) - Array.copy(src, 0, dst, 0, start) - Array.copy(src, start + skipped, dst, start, dst.length - start) - dst - } - newConstraint( - myMap = myMap remove pt, - less = shrinkArray(less).map(shrinkSet(_)), - params = shrinkArray(params)) - } - - def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = { - val entries = myMap(pt) - var noneLeft = true - var i = paramCount(entries) - while (noneLeft && i > 0) { - i -= 1 - if (i != removedParam && isBounds(entries(i))) noneLeft = false - else typeVar(entries, i) match { - case tv: TypeVar => - if (!tv.inst.exists) noneLeft = false // need to keep line around to compute instType - case _ => - } - } - noneLeft - } - -// ---------- Exploration -------------------------------------------------------- - - def domainPolys: List[PolyType] = polyTypes.toList - - def domainParams: List[PolyParam] = params.toList.filter(contains) - - def forallParams(p: PolyParam => Boolean): Boolean = { - myMap.foreachBinding { (poly, entries) => - for (i <- 0 until paramCount(entries)) - if (isBounds(entries(i)) && !p(PolyParam(poly, i))) return false - } - true - } - - def foreachTypeVar(op: TypeVar => Unit): Unit = - myMap.foreachBinding { (poly, entries) => - for (i <- 0 until paramCount(entries)) { - typeVar(entries, i) match { - case tv: TypeVar if !tv.inst.exists => op(tv) - case _ => - } - } - } - - private var myUninstVars: mutable.ArrayBuffer[TypeVar] = _ - - /** The uninstantiated typevars of this constraint */ - def uninstVars: collection.Seq[TypeVar] = { - if (myUninstVars == null) { - myUninstVars = new mutable.ArrayBuffer[TypeVar] - myMap.foreachBinding { (poly, entries) => - for (i <- 0 until paramCount(entries)) { - typeVar(entries, i) match { - case tv: TypeVar if !tv.inst.exists && isBounds(entries(i)) => myUninstVars += tv - case _ => - } - } - } - } - myUninstVars - } - -// ---------- Cyclic checking ------------------------------------------- - - private def checkNonCyclic(idx: Int)(implicit ctx: Context): Unit = - assert(!less(idx)(idx), i"cyclic constraint involving ${params(idx)}") - - def checkNonCyclic()(implicit ctx: Context): Unit = - for (i <- params.indices) checkNonCyclic(i) - -// ---------- toText ----------------------------------------------------- - - override def toText(printer: Printer): Text = { - def entryText(tp: Type) = tp match { - case tp: TypeBounds => - tp.toText(printer) - case _ => - " := " ~ tp.toText(printer) - } - val indent = 3 - val header: Text = "Constraint(" - val uninstVarsText = " uninstVars = " ~ - Text(uninstVars map (_.toText(printer)), ", ") ~ ";" - val constrainedText = - " constrained types = " ~ Text(domainPolys map (_.toText(printer)), ", ") - val boundsText = - " bounds = " ~ { - val assocs = - for (param <- domainParams) - yield (" " * indent) ~ param.toText(printer) ~ entryText(entry(param)) - Text(assocs, "\n") - } - val orderingText = - " ordering = " ~ { - val deps = - for { - param <- domainParams - ups = minUpper(param) - if ups.nonEmpty - } - yield - (" " * indent) ~ param.toText(printer) ~ " <: " ~ - Text(ups.map(_.toText(printer)), ", ") - Text(deps, "\n") - } - Text.lines(List(header, uninstVarsText, constrainedText, boundsText, orderingText, ")")) - } -} - -- cgit v1.2.3