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 ++++++++++++++++++++------- src/dotty/tools/dotc/core/TypeComparer.scala | 6 +- src/dotty/tools/dotc/core/TyperState.scala | 63 ++++++-------- src/dotty/tools/dotc/core/Types.scala | 16 +--- src/dotty/tools/dotc/typer/Inferencing.scala | 46 ++++++----- src/dotty/tools/dotc/typer/Typer.scala | 5 +- 6 files changed, 148 insertions(+), 106 deletions(-) (limited to 'src/dotty') 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)), ", ") diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 88f563cb9..b1081e433 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -79,12 +79,11 @@ class TypeComparer(initctx: Context) extends DotClass { * otherwise it is approximated by its upper bound. However, any occurrences * of the parameter in a refinement somewhere in the bound are removed. * (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. + * The constraint is left unchanged. * @return the instantiating type * @pre `param` is associated with type bounds in the current constraint. */ - def approximate(param: PolyParam, fromBelow: Boolean): Type = { + def approximation(param: PolyParam, fromBelow: Boolean): Type = { val avoidParam = new TypeMap { override def apply(tp: Type) = mapOver { tp match { @@ -97,7 +96,6 @@ class TypeComparer(initctx: Context) extends DotClass { val bound = if (fromBelow) bounds.lo else bounds.hi val inst = avoidParam(bound) println(s"approx ${param.show}, from below = $fromBelow, bound = ${bound.show}, inst = ${inst.show}") - constraint = constraint.replace(param, inst) inst } diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala index 626c1227f..8b5e2c85e 100644 --- a/src/dotty/tools/dotc/core/TyperState.scala +++ b/src/dotty/tools/dotc/core/TyperState.scala @@ -9,6 +9,7 @@ import util.SimpleMap import reporting._ import printing.{Showable, Printer} import printing.Texts._ +import collection.mutable import annotation.elidable class TyperState(val reporter: Reporter) extends DotClass with Showable { @@ -16,18 +17,18 @@ class TyperState(val reporter: Reporter) extends DotClass with Showable { /** The current constraint set */ def constraint: Constraint = new Constraint(SimpleMap.Empty) - /** The currently uninstantiated TypeVars */ - def undetVars: Set[TypeVar] = collection.immutable.ListSet() + def uninstVars = constraint.uninstVars /** A map that records for instantiated type vars their instance type. * Used only in a temporary way for contexts that may be retracted * without also retracting the type var as a whole. */ - def instType: SimpleMap[TypeVar, Type] = SimpleMap.Empty + def instType(tvar: TypeVar): Type = constraint.at(tvar.origin) match { + case _: TypeBounds => NoType + case tp => tp + } def constraint_=(c: Constraint): Unit = {} - def undetVars_=(vs: Set[TypeVar]): Unit = unsupported("undetVars_=") - def instType_=(m: SimpleMap[TypeVar, Type]): Unit = unsupported("instType_=") def fresh(isCommittable: Boolean): TyperState = this @@ -49,23 +50,13 @@ class MutableTyperState(previous: TyperState, reporter: Reporter, override val i extends TyperState(reporter) { private var myConstraint: Constraint = previous.constraint - private var myUndetVars: Set[TypeVar] = previous.undetVars - private var myInstType: SimpleMap[TypeVar, Type] = previous.instType private var checkingEnabled: Boolean = true override def constraint = myConstraint - override def undetVars = myUndetVars - override def instType = myInstType - override def constraint_=(c: Constraint) = { myConstraint = c checkConsistent() } - override def undetVars_=(vs: Set[TypeVar]) = { - myUndetVars = vs - checkConsistent() - } - override def instType_=(m: SimpleMap[TypeVar, Type]): Unit = myInstType = m override def fresh(isCommittable: Boolean): TyperState = new MutableTyperState(this, new StoreReporter, isCommittable) @@ -81,20 +72,24 @@ extends TyperState(reporter) { val targetState = ctx.typerState val prev = targetState.enableChecking(false) targetState.constraint = constraint - targetState.undetVars = undetVars - targetState.instType = instType targetState.enableChecking(prev) - def adjustOwningState(tvar: TypeVar) = - if (tvar.owningState eq this) tvar.owningState = targetState - undetVars foreach adjustOwningState - instType foreachKey { tvar => - adjustOwningState(tvar) - if (tvar.owningState == targetState) { - tvar.inst = instType(tvar) - targetState.instType = targetState.instType remove tvar + val toCollect = new mutable.ListBuffer[PolyType] + constraint foreachTypeVar { tvar => + if (tvar.owningState eq this) + tvar.owningState = targetState + if (!tvar.inst.exists) { + val inst = instType(tvar) + if (inst.exists && (tvar.owningState eq targetState)) { + tvar.inst = inst + val poly = tvar.origin.binder + if (targetState.constraint.isRemovable(poly)) toCollect += poly + } } } + for (poly <- toCollect) + targetState.constraint = targetState.constraint.remove(poly) + targetState.checkConsistent // !!! DEBUG reporter.flush() @@ -103,15 +98,12 @@ extends TyperState(reporter) { @elidable(elidable.FINER) def checkConsistent(show: Showable => String = MutableTyperState.toStr): Unit = if (checkingEnabled) { def err(msg: String, what: Showable) = s"$msg: ${show(what)}\n${show(this)}" - for (tvar <- undetVars) + for (tvar <- uninstVars) assert(constraint contains tvar.origin, err("unconstrained type var", tvar.origin)) if (isCommittable) { - val undetParams = undetVars map (_.origin) + val undetParams = uninstVars map (_.origin) for (param <- constraint.domainParams) assert(undetParams contains param, err("junk constraint on", param)) - instType.foreachKey { tvar => - assert(!(undetVars contains tvar), err("duplicate undetVar and instType", tvar)) - } } } @@ -142,17 +134,14 @@ extends TyperState(reporter) { override def toText(printer: Printer): Text = { val header: Text = "Typer state:" - val undetVarsText = - " undetVars: " ~ - Text(undetVars map (_.toText(printer)), ", ") ~ "." + val uninstVarsText = + " uninstVars: " ~ + Text(uninstVars map (_.toText(printer)), ", ") ~ "." val constrainedText = " constrained types: " ~ constraint.constrainedTypesText(printer) ~ "." val constraintText = " constraint: " ~ constraint.constraintText(3, printer) - val instTypeText = - " instType: " ~ - Text(instType.map2((k, v) => s"${k.toText(printer)} -> ${v.toText(printer)}"), ", ") ~ "." - Text.lines(List(header, undetVarsText, constrainedText, constraintText, instTypeText)) + Text.lines(List(header, uninstVarsText, constrainedText, constraintText)) } } diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 1b880b86f..f530ff986 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -1998,18 +1998,11 @@ object Types { */ private[core] var owningState = creatorState - assert(!(creatorState.undetVars contains this)) - creatorState.undetVars += this - /** The instance type of this variable, or NoType if the variable is currently * uninstantiated */ def instanceOpt(implicit ctx: Context): Type = - if (inst.exists) inst - else { - val i = ctx.typerState.instType(this) - if (i == null) NoType else i - } + if (inst.exists) inst else ctx.typerState.instType(this) /** Is the variable already instantiated? */ def isInstantiated(implicit ctx: Context) = instanceOpt.exists @@ -2018,10 +2011,9 @@ object Types { def instantiateWith(tp: Type)(implicit ctx: Context): Type = { assert(tp ne this) println(s"instantiating ${this.show} with ${tp.show}") // !!!DEBUG - assert(ctx.typerState.undetVars contains this) - ctx.typerState.undetVars -= this + assert(ctx.typerState.constraint contains this) // !!! DEBUG if (ctx.typerState eq owningState) inst = tp - else ctx.typerState.instType = ctx.typerState.instType.updated(this, tp) + ctx.typerState.constraint = ctx.typerState.constraint.replace(origin, tp) tp } @@ -2041,7 +2033,7 @@ object Types { case _ => false } ctx.typerState.withCheckingDisabled { - var inst = ctx.typeComparer.approximate(origin, fromBelow) + var inst = ctx.typeComparer.approximation(origin, fromBelow) if (fromBelow && isSingleton(inst) && !isSingleton(upperBound)) inst = inst.widen instantiateWith(inst.simplified) diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala index ebbd6cd41..8b3c19b71 100644 --- a/src/dotty/tools/dotc/typer/Inferencing.scala +++ b/src/dotty/tools/dotc/typer/Inferencing.scala @@ -204,15 +204,31 @@ object Inferencing { * If the constraint contains already some of these parameters in its domain, * make a copy of the polytype and add the copy's type parameters instead. * Return either the original polytype, or the copy, if one was made. + * Also, if `owningTree` is non-empty, add a type variable for each parameter. + * @return The tracked polytype, and the list of created type variables. */ - def track(pt: PolyType): PolyType = { + def track(pt: PolyType, owningTree: untpd.Tree): (PolyType, List[TypeVar]) = { val tracked = if (state.constraint contains pt) pt.copy(pt.paramNames, pt.paramBounds, pt.resultType) else pt - state.constraint = state.constraint + tracked - tracked + val tvars = if (owningTree.isEmpty) Nil else newTypeVars(tracked, owningTree) + state.constraint = state.constraint.add(tracked, tvars) + //if (!owningTree.isEmpty) + // state.constraint = state.constraint.transformed(pt, _.substParams(pt, tvars)) + (tracked, tvars) } + /** Create new type variables for the parameters of a poly type. + * @param pos The position of the new type variables (relevant for + * interpolateUndetVars + */ + private def newTypeVars(pt: PolyType, owningTree: untpd.Tree): List[TypeVar] = + for (n <- (0 until pt.paramNames.length).toList) + yield new TypeVar(PolyParam(pt, n), ctx.typerState, owningTree) + + /** Same as `track(pt, EmptyTree)`, but returns just the created polytype */ + def track(pt: PolyType): PolyType = track(pt, EmptyTree)._1 + /** Interpolate those undetermined type variables in the widened type of this tree * which are introduced by type application contained in the tree. * If such a variable appears covariantly in type `tp` or does not appear at all, @@ -222,14 +238,14 @@ object Inferencing { def interpolateUndetVars(tree: Tree): Unit = Stats.track("interpolateUndetVars") { val tp = tree.tpe.widen - println(s"interpolate undet vars in ${tp.show}, pos = ${tree.pos}, mode = ${ctx.mode}, undets = ${ctx.typerState.undetVars map (tvar => s"${tvar.show}@${tvar.owningTree.pos}")}") - println(s"qualifying undet vars: ${ctx.typerState.undetVars filter qualifies map (_.show)}") + println(s"interpolate undet vars in ${tp.show}, pos = ${tree.pos}, mode = ${ctx.mode}, undets = ${ctx.typerState.uninstVars map (tvar => s"${tvar.show}@${tvar.owningTree.pos}")}") + println(s"qualifying undet vars: ${ctx.typerState.uninstVars filter qualifies map (_.show)}") println(s"fulltype: $tp") // !!! DEBUG println(s"constraint: ${ctx.typerState.constraint.show}") def qualifies(tvar: TypeVar) = tree contains tvar.owningTree val vs = tp.variances(tvar => - (ctx.typerState.undetVars contains tvar) && qualifies(tvar)) + (ctx.typerState.constraint contains tvar) && qualifies(tvar)) println(s"variances = $vs") var changed = false for ((tvar, v) <- vs) @@ -241,11 +257,12 @@ object Inferencing { if (changed) interpolateUndetVars(tree) else - for (tvar <- ctx.typerState.undetVars) + ctx.typerState.constraint.foreachUninstVar { tvar => if (!(vs contains tvar) && qualifies(tvar)) { println(s"instantiating non-occurring $tvar in $tp") tvar.instantiate(fromBelow = true) } + } } /** Instantiate undetermined type variables to that type `tp` is @@ -253,7 +270,7 @@ object Inferencing { * typevar is not uniquely determined, return that typevar in a Some. */ def maximizeType(tp: Type): Option[TypeVar] = Stats.track("maximizeType") { - val vs = tp.variances(tvar => ctx.typerState.undetVars contains tvar) + val vs = tp.variances(tvar => ctx.typerState.constraint contains tvar) var result: Option[TypeVar] = None for ((tvar, v) <- vs) if (v == 1) tvar.instantiate(fromBelow = false) @@ -266,19 +283,6 @@ object Inferencing { result } - /** Create new type variables for the parameters of a poly type. - * @param pos The position of the new type variables (relevant for - * interpolateUndetVars - */ - def newTypeVars(pt: PolyType, owningTree: untpd.Tree): List[TypeVar] = { - val state = ctx.typerState - val tvars = - for (n <- (0 until pt.paramNames.length).toList) - yield new TypeVar(PolyParam(pt, n), state, owningTree) - state.constraint = state.constraint.transformed(pt, _.substParams(pt, tvars)) - tvars - } - def isSubTypes(actuals: List[Type], formals: List[Type])(implicit ctx: Context): Boolean = formals match { case formal :: formals1 => actuals match { diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala index 9780e8d2e..4242b5c99 100644 --- a/src/dotty/tools/dotc/typer/Typer.scala +++ b/src/dotty/tools/dotc/typer/Typer.scala @@ -1100,10 +1100,7 @@ class Typer extends Namer with Applications with Implicits { case poly: PolyType => if (pt.isInstanceOf[PolyProto]) tree else { - val tvars = ctx.typerState.withCheckingDisabled { - val tracked = ctx.track(poly) - ctx.newTypeVars(tracked, tree) - } + val (_, tvars) = ctx.track(poly, tree) adaptInterpolated(tree appliedToTypes tvars, pt) } case wtp => -- cgit v1.2.3