From e38813ac1362a1d528dfa1ee79f0f8b0d6f7ccb8 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 21 Nov 2013 23:44:32 +0100 Subject: Consolidation of TyperState and Constraint Removing undetVars and instTypes as separately assignable fields. This is better for maintaining invariants by design. --- src/dotty/tools/dotc/core/Constraint.scala | 118 ++++++++++++++++++++++------- 1 file changed, 90 insertions(+), 28 deletions(-) (limited to 'src/dotty/tools/dotc/core/Constraint.scala') diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala index 55aff9851..8ffdce71c 100644 --- a/src/dotty/tools/dotc/core/Constraint.scala +++ b/src/dotty/tools/dotc/core/Constraint.scala @@ -4,15 +4,18 @@ package core import Types._, Contexts._ import util.SimpleMap -import collection.mutable.ListBuffer +import collection.mutable import printing.{Printer, Showable} import printing.Texts._ /** Constraint over undetermined type parameters - * @param myMap 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 `NoType` in the corresponding - * array entry. + * @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 Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal with Showable { @@ -25,6 +28,23 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit entries != null && entries(param.paramNum).exists } + /** Does this constraint contain the type variable `tvar` and is it uninstantiated? */ + 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) + } + + /** 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) + + private def isBounds(tp: Type) = tp.isInstanceOf[TypeBounds] + /** The constraint for given type parameter `param`, or NoType if `param` is not part of * the constraint domain. */ @@ -52,7 +72,7 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit } /** A new constraint which is derived from this constraint by updating - * the the entry for parameter `param` to `tpe`. + * the entry for parameter `param` to `tpe`. * @pre `this contains param`. */ def updated(param: PolyParam, tpe: Type): Constraint = { @@ -68,38 +88,39 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit def transformed(poly: PolyType, op: Type => Type): Constraint = updateEntries(poly, myMap(poly) map op) - /** A new constraint which is derived from this constraint by removing - * the type parameter `param` from the domain. + /** A new constraint with all entries coming from `pt` removed. */ + def remove(pt: PolyType) = new Constraint(myMap remove pt) + + /** Is entry associated with `pt` removable? + * @param removedParam The index of a parameter which is still present in the + * entry array, but is going to be removed at the same step, + * or -1 if no such parameter exists. */ - def - (param: PolyParam)(implicit ctx: Context) = { - val pt = param.binder - val pnum = param.paramNum + def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = { val entries = myMap(pt) var noneLeft = true - var i = 0 - while (noneLeft && (i < entries.length)) { - noneLeft = (entries(i) eq NoType) || i == pnum - i += 1 + 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 _ => + } } - if (noneLeft) new Constraint(myMap remove pt) - else updated(param, NoType) + noneLeft } - /** A new constraint which is derived from this constraint by adding - * entries for all type parameters of `poly`. - */ - def +(poly: PolyType) = - updateEntries(poly, poly.paramBounds.toArray[Type]) - /** A new constraint which is derived from this constraint by removing * the type parameter `param` from the domain and replacing all occurrences * of the parameter elsewhere in the constraint by type `tp`. */ - def replace(param: PolyParam, tp: Type)(implicit ctx: Context) = { + def replace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = { def subst(entries: Array[Type]) = { var result = entries var i = 0 - while (i < entries.length) { + while (i < paramCount(entries)) { entries(i) match { case oldBounds: TypeBounds => val newBounds = oldBounds.substParam(param, tp) @@ -113,19 +134,60 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit } result } + val pt = param.binder + val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updated(param, tp) + new Constraint(constr1.myMap mapValues subst) + } + - new Constraint((this - param).myMap mapValues subst) + /** A new constraint which is derived from this constraint by adding + * entries for all type parameters of `poly`. + */ + def add(poly: PolyType, tvars: List[TypeVar] = Nil): Constraint = { + val nparams = poly.paramNames.length + val entries = new Array[Type](nparams * 2) + poly.paramBounds.copyToArray(entries, 0) + tvars.copyToArray(entries, nparams) + updateEntries(poly, entries) } + /** The polytypes constrained by this constraint */ def domainPolys: List[PolyType] = myMap.keys + /** The polytype parameters constrained by this constraint */ def domainParams: List[PolyParam] = for { (poly, entries) <- myMap.toList - n <- 0 until entries.length - if entries(n).exists + n <- 0 until paramCount(entries) + if isBounds(entries(n)) } yield PolyParam(poly, n) + /** Perform operation `op` on all typevars, or only on uninstantiated + * typevars, depending on whether `uninstOnly` is set or not. + */ + def foreachTypeVar(op: TypeVar => Unit, uninstOnly: Boolean = false): Unit = myMap.foreachKey { poly => + val entries = myMap(poly) + for (i <- 0 until paramCount(entries)) { + def qualifies(tv: TypeVar) = + if (uninstOnly) isBounds(entries(i)) else !tv.inst.exists + typeVar(entries, i) match { + case tv: TypeVar if qualifies(tv) => op(tv) + case _ => + } + } + } + + /** Perform operation `op` on all uninstantiated typevars. + */ + def foreachUninstVar(op: TypeVar => Unit): Unit = foreachTypeVar(op, uninstOnly = true) + + /** The uninstantiated typevars of this constraint */ + def uninstVars: collection.Seq[TypeVar] = { + val buf = new mutable.ArrayBuffer[TypeVar] + foreachUninstVar(buf += _) + buf + } + def constrainedTypesText(printer: Printer): Text = Text(domainPolys map (_.toText(printer)), ", ") -- cgit v1.2.3