diff options
| -rw-r--r-- | src/dotty/tools/dotc/config/Config.scala | 2 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/Constraint.scala | 2 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/OrderingConstraint.scala | 481 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/TrackingConstraint.scala | 122 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/TyperState.scala | 3 |
5 files changed, 546 insertions, 64 deletions
diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala index db0c3ce4a..fe4e88829 100644 --- a/src/dotty/tools/dotc/config/Config.scala +++ b/src/dotty/tools/dotc/config/Config.scala @@ -13,7 +13,7 @@ object Config { /** When updating a connstraint bound, check that the constrained parameter * does not appear at the top-level of either of its bounds. */ - final val checkConstraintsNonCyclic = true + final val checkConstraintsNonCyclic = false /** Like `checkConstraintsNonCyclic`, but all constrained parameters * are tested for direct or indirect dependencies, each time a diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala index 873a3c913..cedfb52eb 100644 --- a/src/dotty/tools/dotc/core/Constraint.scala +++ b/src/dotty/tools/dotc/core/Constraint.scala @@ -42,7 +42,7 @@ abstract class Constraint extends Showable { def typeVarOfParam(param: PolyParam): Type /** Is it known that `param1 <:< param2`? */ - def isLess(param1: PolyParam, param2: PolyParam)(implicit ctx: Context): Boolean + def isLess(param1: PolyParam, param2: PolyParam): Boolean /** The parameters that are known to be smaller wrt <: than `param` */ def lower(param: PolyParam): List[PolyParam] diff --git a/src/dotty/tools/dotc/core/OrderingConstraint.scala b/src/dotty/tools/dotc/core/OrderingConstraint.scala new file mode 100644 index 000000000..2deec51a8 --- /dev/null +++ b/src/dotty/tools/dotc/core/OrderingConstraint.scala @@ -0,0 +1,481 @@ +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 OrderingConstraint { + + /** The type of `Constraint#boundsMap` */ + type ParamBounds = SimpleMap[PolyType, Array[Type]] + + /** The type of `Constraint#lowerMap`, `Constraint#upperMap` */ + type ParamOrdering = SimpleMap[PolyType, Array[List[PolyParam]]] + + /** A new constraint with given maps */ + private def newConstraint(boundsMap: ParamBounds, lowerMap: ParamOrdering, upperMap: ParamOrdering)(implicit ctx: Context) : OrderingConstraint = { + val result = new OrderingConstraint(boundsMap, lowerMap, upperMap) + if (Config.checkConstraintsNonCyclic) result.checkNonCyclic() + ctx.runInfo.recordConstraintSize(result, result.boundsMap.size) + result + } + + /** 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 initial: T + + def apply(c: OrderingConstraint, poly: PolyType, idx: Int) = { + val es = entries(c, poly) + if (es == null) initial else es(idx) + } + + /** The `current` constraint but with the entry for `param` updated to `entry`. + * `current` is used linearly. If it is different from `prev` it is + * known to be dead after the call. Hence it is OK to update destructively + * 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 = { + var es = entries(current, poly) + if (es != null && (es(idx) eq entry)) current + else { + val result = + if (es == null) { + es = Array.fill(poly.paramNames.length)(initial) + updateEntries(current, poly, es) + } + else if (es ne entries(prev, poly)) + current // can re-use existing entries array. + else { + es = es.clone + updateEntries(current, poly, es) + } + es(idx) = entry + result + } + } + + def update(prev: OrderingConstraint, current: OrderingConstraint, + param: PolyParam, entry: T)(implicit ctx: Context): 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 = + update(prev, current, poly, idx, f(apply(current, poly, idx))) + + def map(prev: OrderingConstraint, current: OrderingConstraint, + param: PolyParam, f: T => T)(implicit ctx: Context): OrderingConstraint = + map(prev, current, param.binder, param.paramNum, f) + } + + val boundsLens = new ConstraintLens[Type] { + def entries(c: OrderingConstraint, poly: PolyType): Array[Type] = + c.boundsMap(poly) + def updateEntries(c: OrderingConstraint, poly: PolyType, 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[PolyParam]] { + def entries(c: OrderingConstraint, poly: PolyType): Array[List[PolyParam]] = + c.lowerMap(poly) + def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[List[PolyParam]])(implicit ctx: Context): OrderingConstraint = + newConstraint(c.boundsMap, c.lowerMap.updated(poly, entries), c.upperMap) + def initial = Nil + } + + val upperLens = new ConstraintLens[List[PolyParam]] { + def entries(c: OrderingConstraint, poly: PolyType): Array[List[PolyParam]] = + c.upperMap(poly) + def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[List[PolyParam]])(implicit ctx: Context): OrderingConstraint = + newConstraint(c.boundsMap, c.lowerMap, c.upperMap.updated(poly, entries)) + def initial = Nil + } +} + +import OrderingConstraint._ + +/** Constraint over undetermined type parameters that keeps separate maps to + * reflect parameter orderings. + * @param boundsMap 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. + * + * @param lowerMap a map from PolyTypes 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. P <: Q. + * @param upperMap a map from PolyTypes 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. Q <: P. + */ +class OrderingConstraint(private val boundsMap: ParamBounds, + private val lowerMap : ParamOrdering, + private val upperMap : ParamOrdering) extends Constraint { + + type This = OrderingConstraint + + +// ----------- Basic indices -------------------------------------------------- + + /** 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) + + /** The `boundsMap` entry corresponding to `param` */ + def entry(param: PolyParam): Type = { + val entries = boundsMap(param.binder) + if (entries == null) NoType + else entries(param.paramNum) + } + +// ----------- Contains tests -------------------------------------------------- + + def contains(pt: PolyType): Boolean = boundsMap(pt) != null + + def contains(param: PolyParam): Boolean = { + val entries = boundsMap(param.binder) + entries != null && entries(param.paramNum).isInstanceOf[TypeBounds] + } + + def contains(tvar: TypeVar): Boolean = { + val origin = tvar.origin + val entries = boundsMap(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 ---------------------------------------------- + + def lower(param: PolyParam): List[PolyParam] = lowerLens(this, param.binder, param.paramNum) + def upper(param: PolyParam): List[PolyParam] = upperLens(this, param.binder, param.paramNum) + + def minLower(param: PolyParam): List[PolyParam] = { + val all = lower(param) + all.filterNot(p => all.exists(isLess(p, _))) + } + + def minUpper(param: PolyParam): List[PolyParam] = { + val all = upper(param) + all.filterNot(p => all.exists(isLess(_, p))) + } + + def exclusiveLower(param: PolyParam, butNot: PolyParam): List[PolyParam] = + lower(param).filterNot(isLess(_, butNot)) + + def exclusiveUpper(param: PolyParam, butNot: PolyParam): List[PolyParam] = + upper(param).filterNot(isLess(butNot, _)) + +// ---------- Info related to PolyParams ------------------------------------------- + + def isLess(param1: PolyParam, param2: PolyParam): Boolean = + upper(param1).contains(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 = boundsMap(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, paramBuf: mutable.ListBuffer[PolyParam], + isUpper: Boolean)(implicit ctx: Context): Type = tp match { + case param: PolyParam if contains(param) => + if (!paramBuf.contains(param)) paramBuf += param + NoType + case tp: AndOrType if isUpper == tp.isAnd => + val tp1 = stripParams(tp.tp1, paramBuf, isUpper) + val tp2 = stripParams(tp.tp2, paramBuf, isUpper) + 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 normalizedType(tp: Type, paramBuf: mutable.ListBuffer[PolyParam], + isUpper: Boolean)(implicit ctx: Context): Type = + stripParams(tp, paramBuf, isUpper) + .orElse(if (isUpper) defn.AnyType else defn.NothingType) + + 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) + newConstraint(boundsMap.updated(poly, entries1), lowerMap, upperMap).init(poly) + } + + private def init(poly: PolyType)(implicit ctx: Context): This = { + var current = this + val loBuf, hiBuf = new mutable.ListBuffer[PolyParam] + var i = 0 + while (i < poly.paramNames.length) { + val param = PolyParam(poly, i) + val bounds = nonParamBounds(param) + val lo = normalizedType(bounds.lo, loBuf, isUpper = false) + val hi = normalizedType(bounds.hi, hiBuf, isUpper = true) + current = boundsLens.update(this, current, poly, i, bounds.derivedTypeBounds(lo, hi)) + current = (current /: loBuf)(order(_, _, param)) + current = (current /: hiBuf)(order(_, param, _)) + loBuf.clear() + hiBuf.clear() + i += 1 + } + if (Config.checkConstraintsNonCyclic) checkNonCyclic() + current + } + +// ---------- 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 order(current: This, param1: PolyParam, param2: PolyParam)(implicit ctx: Context): This = + if (param1 == param2 || current.isLess(param1, param2)) this + else { + assert(contains(param1)) + assert(contains(param2)) + val newUpper = param2 :: exclusiveUpper(param2, param1) + val newLower = param1 :: exclusiveLower(param1, param2) + val current1 = (current /: newLower)(upperLens.map(this, _, _, newUpper ::: _)) + val current2 = (current1 /: newUpper)(lowerLens.map(this, _, _, newLower ::: _)) + current2 + } + + def addLess(param1: PolyParam, param2: PolyParam)(implicit ctx: Context): This = + order(this, param1, param2) + + def updateEntry(param: PolyParam, tp: Type)(implicit ctx: Context): This = + boundsLens.update(this, this, param, tp) + + 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) + 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): OrderingConstraint = { + val replacement = tp.dealias.stripTypeVar + if (param == replacement) this + else { + assert(replacement.isValueType) + val poly = param.binder + val idx = param.paramNum + def removeParam(ps: List[PolyParam]) = + ps.filterNot(p => p.binder.eq(poly) && p.paramNum == idx) + def replaceParam(tp: Type, atPoly: PolyType, atIdx: Int) = tp match { + case bounds: TypeBounds => + val bounds1 = tp.substParam(param, replacement).asInstanceOf[TypeBounds] + if (bounds1 eq bounds) bounds + else dropParamIn(bounds1, atPoly, atIdx) + case _ => tp + } + var current = this + if (isRemovable(poly, idx)) current = remove(poly) + else { + current = updateEntry(param, replacement) + lowerLens.update(this, current, poly, idx, Nil) + upperLens.update(this, current, poly, idx, Nil) + } + current.foreachParam {(p, i) => + current = boundsLens.map(this, current, p, i, replaceParam(_, p, i)) + current = lowerLens.map(this, current, p, i, removeParam) + current = upperLens.map(this, current, p, i, removeParam) + } + current + } + } + + def remove(pt: PolyType)(implicit ctx: Context): This = + newConstraint(boundsMap.remove(pt), lowerMap.remove(pt), upperMap.remove(pt)) + + def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = { + val entries = boundsMap(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] = boundsMap.keys + + def domainParams: List[PolyParam] = + for { + (poly, entries) <- boundsMap.toList + n <- 0 until paramCount(entries) + if isBounds(entries(n)) + } yield PolyParam(poly, n) + + def forallParams(p: PolyParam => Boolean): Boolean = { + boundsMap.foreachBinding { (poly, entries) => + for (i <- 0 until paramCount(entries)) + if (isBounds(entries(i)) && !p(PolyParam(poly, i))) return false + } + true + } + + def foreachParam(p: (PolyType, Int) => Unit): Unit = + boundsMap.foreachBinding { (poly, entries) => + 0.until(poly.paramNames.length).foreach(p(poly, _)) + } + + def foreachTypeVar(op: TypeVar => Unit): Unit = + boundsMap.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] + boundsMap.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 ------------------------------------------- + + def checkNonCyclic()(implicit ctx: Context): Unit = + domainParams.foreach(checkNonCyclic) + + private def checkNonCyclic(param: PolyParam)(implicit ctx: Context): Unit = + assert(!isLess(param, param), i"cyclic constraint involving $param in $this") + +// ---------- 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, ")")) + } +}
\ No newline at end of file diff --git a/src/dotty/tools/dotc/core/TrackingConstraint.scala b/src/dotty/tools/dotc/core/TrackingConstraint.scala index 3f15f2b37..fc8a083f4 100644 --- a/src/dotty/tools/dotc/core/TrackingConstraint.scala +++ b/src/dotty/tools/dotc/core/TrackingConstraint.scala @@ -30,14 +30,14 @@ import TrackingConstraint._ * 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], +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`. */ @@ -47,19 +47,19 @@ class TrackingConstraint(private val myMap: ParamInfo, 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, _) => + myMap.foreachBinding { (pt, _) => polyTypes(idx) = pt polyStart(idx) = count count += pt.paramNames.length @@ -67,8 +67,8 @@ class TrackingConstraint(private val myMap: ParamInfo, } assert(count == params.length) } - - /** The index of given polytype `pt` in this constraint, + + /** The index of given polytype `pt` in this constraint, * or `polyTypes.length` if constraint does not contain `pt`. */ private def polyIndex(pt: PolyType): Int = { @@ -76,16 +76,16 @@ class TrackingConstraint(private val myMap: ParamInfo, 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 @@ -98,7 +98,7 @@ class TrackingConstraint(private val myMap: ParamInfo, if (entries == null) NoType else entries(param.paramNum) } - + // ----------- Contains tests -------------------------------------------------- def contains(pt: PolyType): Boolean = polyIndex(pt) < polyTypes.length @@ -116,59 +116,59 @@ class TrackingConstraint(private val myMap: ParamInfo, } 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 = + + 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)(implicit ctx: Context): Boolean = + def isLess(param1: PolyParam, param2: PolyParam): Boolean = less(paramIndex(param1))(paramIndex(param2)) - def nonParamBounds(param: PolyParam): TypeBounds = + 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 = + 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)) @@ -180,16 +180,16 @@ class TrackingConstraint(private val myMap: ParamInfo, 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, + private def stripParams(tp: Type, handleParam: (PolyParam, Boolean) => Type, seenFromBelow: Boolean)(implicit ctx: Context): Type = tp match { - case tp: PolyParam => + case tp: PolyParam => handleParam(tp, seenFromBelow) case tp: AndOrType if seenFromBelow == tp.isAnd => val tp1 = stripParams(tp.tp1, handleParam, seenFromBelow) @@ -200,17 +200,17 @@ class TrackingConstraint(private val myMap: ParamInfo, 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 = + 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. */ @@ -234,7 +234,7 @@ class TrackingConstraint(private val myMap: ParamInfo, for (i <- is) { def handleParam(param: PolyParam, seenFromBelow: Boolean): Type = { def record(paramIdx: Int): Type = { - less1 = + less1 = if (seenFromBelow) updatedLess(less1, nparams + i, paramIdx) else updatedLess(less1, paramIdx, nparams + i) NoType @@ -247,9 +247,9 @@ class TrackingConstraint(private val myMap: ParamInfo, } 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. */ @@ -267,31 +267,31 @@ class TrackingConstraint(private val myMap: ParamInfo, 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 + 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 = + 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 @@ -342,8 +342,8 @@ class TrackingConstraint(private val myMap: ParamInfo, } result } - - if (param == replacement) this + + if (param == replacement) this else { assert(replacement.isValueType) val pt = param.binder @@ -355,7 +355,7 @@ class TrackingConstraint(private val myMap: ParamInfo, 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 @@ -364,12 +364,12 @@ class TrackingConstraint(private val myMap: ParamInfo, 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) + Array.copy(src, start + skipped, dst, start, dst.length - start) dst } newConstraint( - myMap = myMap remove pt, - less = shrinkArray(less).map(shrinkSet(_)), + myMap = myMap remove pt, + less = shrinkArray(less).map(shrinkSet(_)), params = shrinkArray(params)) } @@ -438,14 +438,14 @@ class TrackingConstraint(private val myMap: ParamInfo, 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 => + case tp: TypeBounds => tp.toText(printer) - case _ => + case _ => " := " ~ tp.toText(printer) } val indent = 3 @@ -469,7 +469,7 @@ class TrackingConstraint(private val myMap: ParamInfo, ups = minUpper(param) if ups.nonEmpty } - yield + yield (" " * indent) ~ param.toText(printer) ~ " <: " ~ Text(ups.map(_.toText(printer)), ", ") Text(deps, "\n") diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala index bdba128a9..1079af510 100644 --- a/src/dotty/tools/dotc/core/TyperState.scala +++ b/src/dotty/tools/dotc/core/TyperState.scala @@ -17,7 +17,8 @@ class TyperState(r: Reporter) extends DotClass with Showable { def reporter = r /** The current constraint set */ - def constraint: Constraint = new TrackingConstraint(SimpleMap.Empty, Array(), Array()) + def constraint: Constraint = + new OrderingConstraint(SimpleMap.Empty, SimpleMap.Empty, SimpleMap.Empty) def constraint_=(c: Constraint): Unit = {} /** The uninstantiated variables */ |