diff options
author | Martin Odersky <odersky@gmail.com> | 2014-05-01 16:48:02 +0200 |
---|---|---|
committer | Dmitry Petrashko <dmitry.petrashko@gmail.com> | 2014-05-08 21:51:47 +0200 |
commit | 640feb1fe9de15dbf846c5a1ddc480c44523daa3 (patch) | |
tree | 9b2d1635f2038c24f5e3c1a5ca070444b1683e6b /src | |
parent | 94c13485c7ced4b2fe1fec2936d74291d657ab88 (diff) | |
download | dotty-640feb1fe9de15dbf846c5a1ddc480c44523daa3.tar.gz dotty-640feb1fe9de15dbf846c5a1ddc480c44523daa3.tar.bz2 dotty-640feb1fe9de15dbf846c5a1ddc480c44523daa3.zip |
Adding dependency tracking to constraint satisfaction
The previous scheme checked all constraint bounds twice everytime
the bounds for a parameter in a constraint were changed. The new scheme,
which can be disabled by unsetting `Config.trackContrDeps`, only
checks those cbounds that directly or indirectly mention the changed
parameter.
Diffstat (limited to 'src')
-rw-r--r-- | src/dotty/tools/dotc/config/Config.scala | 6 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Constraint.scala | 150 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/TypeComparer.scala | 81 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/TyperState.scala | 6 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 3 |
5 files changed, 206 insertions, 40 deletions
diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala index e77b10bfb..c247699da 100644 --- a/src/dotty/tools/dotc/config/Config.scala +++ b/src/dotty/tools/dotc/config/Config.scala @@ -37,4 +37,10 @@ object Config { /** The recursion depth for showing a summarized string */ final val summarizeDepth = 2 + + /** Track dependencies for constraint propagation satisfiability checking + * If turned off, constraint checking is simpler but potentially slower + * for large constraints. + */ + final val trackConstrDeps = true }
\ No newline at end of file diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala index a16c85316..339dbb64a 100644 --- a/src/dotty/tools/dotc/core/Constraint.scala +++ b/src/dotty/tools/dotc/core/Constraint.scala @@ -10,6 +10,55 @@ import printing.Texts._ import config.Config import config.Printers._ +object Constraint { + + /** The type of `Constraint#myMap` */ + type ParamInfo = SimpleMap[PolyType, Array[Type]] + + /** The type of `Constraint#dependents */ + type DependentMap = SimpleMap[PolyType, Array[Set[PolyParam]]] + + /** The type of functions that include or exclude a `PolyParam` in or from a set*/ + private type DepDelta = (Set[PolyParam], PolyParam) => Set[PolyParam] + + private val addDep: DepDelta = (_ + _) + private val removeDep: DepDelta = (_ - _) + + private val NoTypeBounds = new TypeBounds(WildcardType, WildcardType){} + + /** An accumulator that changes dependencies on `param`. + * @param param The parameter to which changed dependencies refer. + * @param ofVariance Include `PolyParams` occurring at this variance in the dependencies. + * @param delta The dependency change to perform (add or remove). + */ + private class ChangeDependencies(param: PolyParam, ofVariance: Int, delta: DepDelta)(implicit ctx: Context) + extends TypeAccumulator[DependentMap] { + def apply(deps: DependentMap, tp: Type): DependentMap = tp match { + case tp @ PolyParam(pt, n) if + this.variance == 0 || this.variance == ofVariance => + val oldDeps = deps(pt) + val original = safeSelect(oldDeps, n) + val changed = delta(original, param) + if (original eq changed) deps + else { + val newDeps = + if (oldDeps == null) new Array[Set[PolyParam]](pt.paramBounds.length) + else oldDeps.clone + newDeps(n) = changed + deps.updated(pt, newDeps) + } + case _ => foldOver(deps, tp) + } + } + + /** `deps(n)`, except that `Set()` is returned if `deps` or `deps(n)` are null */ + private def safeSelect(deps: Array[Set[PolyParam]], n: Int) : Set[PolyParam] = + if (deps == null || deps(n) == null) Set() + else deps(n) +} + +import Constraint._ + /** 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 @@ -18,8 +67,20 @@ import config.Printers._ * 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 dependents a map from PolyTypes to arrays of Sets of PolyParams. + * The i'th set in an array corresponding to polytype `pt` contains + * those dependent `PolyParam`s `dp` that have `PolyParam(pt, i)` in their bounds in + * significant position. A position is significant if solving the + * constraint for `(pt, i)` with a type higher than its lower bound + * would lead to a constraint for `dp` that was not looser than + * the existing constraint. Specifically, it means that all poly params + * appearing covariantly in the lower bound and contravariantly in the + * upper bound, as well as all poly params appearing nonvariantly are + * significant. + * The `dependents` map is maintained and queried only of `Config.trackConstrDeps` is set. */ -class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable { +class Constraint(private val myMap: ParamInfo, + private val dependents: DependentMap) extends Showable { /** Does the constraint's domain contain the type parameters of `pt`? */ def contains(pt: PolyType): Boolean = myMap(pt) != null @@ -72,15 +133,82 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable { } } + /** Change dependencies in map `deps` to reflect new parameter bounds. + * @param deps The map to change + * @param pt the polytype that contains the parameters which might have new bounds + * @param entries the entries for the parameters which might have new bounds + * @param delta the change operation, one of `addDep` or `removeDep`. + * @param cmpEntries the comparison entries or `null` if no such entries exist. + * As an optimization, only bounds that differ between `entries` + * and `cmpEntries` will record their dependencies. + */ + def changeDependencies(deps: DependentMap, pt: PolyType, entries: Array[Type], delta: DepDelta, cmpEntries: Array[Type])(implicit ctx: Context): DependentMap = { + val limit = paramCount(entries) + def loop(deps: DependentMap, n: Int): DependentMap = { + if (n >= limit) deps + else { + val newDeps = entries(n) match { + case bounds @ TypeBounds(lo, hi) => + val cmpBounds = + if (cmpEntries == null) NoTypeBounds + else cmpEntries(n) match { + case bounds: TypeBounds => bounds + case _ => NoTypeBounds + } + if (cmpBounds eq bounds) deps + else { + val param = PolyParam(pt, n) + val deps1 = + if (cmpBounds.lo eq lo) deps + else new ChangeDependencies(param, 1, delta).apply(deps, lo) + val deps2 = + if (cmpBounds.hi eq hi) deps1 + else new ChangeDependencies(param, -1, delta).apply(deps1, hi) + deps2 + } + case _ => + deps + } + loop(newDeps, n + 1) + } + } + if (Config.trackConstrDeps) loop(deps, 0) else deps + } + + /** Change dependencies to reflect all changes between the bounds in `oldMap` and `newMap`. + */ + def diffDependencies(deps: DependentMap, oldMap: ParamInfo, newMap: ParamInfo)(implicit ctx: Context): DependentMap = + if (Config.trackConstrDeps) { + var d = deps + oldMap foreachBinding { (poly, entries) => + val newEntries = newMap(poly) + if (newEntries ne entries) d = changeDependencies(d, poly, entries, removeDep, newEntries) + } + newMap foreachBinding { (poly, entries) => + val oldEntries = oldMap(poly) + if (oldEntries ne entries) d = changeDependencies(d, poly, entries, addDep, oldEntries) + } + d + } else deps + + /** The set of parameters that depend directly on `param` + * according to what's stored in `dependents`. + */ + def dependentParams(param: PolyParam): Set[PolyParam] = + safeSelect(dependents(param.binder), param.paramNum) + /** A new constraint which is derived from this constraint by adding or replacing * the entries corresponding to `pt` with `entries`. */ private def updateEntries(pt: PolyType, entries: Array[Type])(implicit ctx: Context) : Constraint = { - val res = new Constraint(myMap.updated(pt, entries)) + val res = new Constraint( + myMap.updated(pt, entries), + changeDependencies(dependents, pt, entries, addDep, myMap(pt))) + //assert(res.domainPolys.filter(pt => // pt.resultType.resultType.widen.classSymbol.name.toString == "Ensuring").length < 2) //DEBUG if (Config.checkConstraintsNonCyclic) checkNonCyclic(pt, entries) - ctx.runInfo.recordConstraintSize(res) + ctx.runInfo.recordConstraintSize(res, res.myMap.size) res } @@ -119,7 +247,10 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable { updateEntries(poly, myMap(poly) map op) /** A new constraint with all entries coming from `pt` removed. */ - def remove(pt: PolyType) = new Constraint(myMap remove pt) + def remove(pt: PolyType)(implicit ctx: Context) = + new Constraint( + myMap remove pt, + changeDependencies(dependents, pt, myMap(pt), removeDep, null)) /** Is entry associated with `pt` removable? * @param removedParam The index of a parameter which is still present in the @@ -190,7 +321,10 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable { val pt = param.binder val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updated(param, tp) - val result = new Constraint(constr1.myMap mapValues subst) + val substMap = constr1.myMap mapValues subst + val result = new Constraint( + substMap, + diffDependencies(constr1.dependents, constr1.myMap, substMap)) if (Config.checkConstraintsNonCyclic) result.checkNonCyclic() result } @@ -314,9 +448,9 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable { trait ConstraintRunInfo { self: RunInfo => private var maxSize = 0 private var maxConstraint: Constraint = _ - def recordConstraintSize(c: Constraint) = - if (c.myMap.size > maxSize) { - maxSize = c.myMap.size + def recordConstraintSize(c: Constraint, size: Int) = + if (size > maxSize) { + maxSize = size maxConstraint = c } def printMaxConstraint()(implicit ctx: Context) = diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 9003de3c1..2d66e7d2f 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -84,51 +84,77 @@ class TypeComparer(initctx: Context) extends DotClass { myAnyType } - /** Map that approximates each param in constraint by its lower bound */ + /** Map that approximates each param in constraint by its lower bound. + * Currently only used for diagnostics. + */ val approxParams = new TypeMap { def apply(tp: Type): Type = tp.stripTypeVar match { - case tp: PolyParam if !solvedConstraint && (constraint contains tp) => + case tp: PolyParam if constraint contains tp => this(constraint.bounds(tp).lo) case tp => mapOver(tp) } } - /** Propagate new constraint by comparing all bounds */ - def propagate: Boolean = - constraint.forallParams { poly => - val TypeBounds(lo, hi) = constraint.bounds(poly) + /** If `param` is contained in constraint, test whether its + * bounds are non-empty. Otherwise return `true`. + */ + private def checkBounds(param: PolyParam): Boolean = constraint.at(param) match { + case TypeBounds(lo, hi) => + if (Stats.monitored) Stats.record("checkBounds") isSubType(lo, hi) + case _ => true + } + + /** Test validity of constraint for parameter `changed` and of all + * parameters that depend on it. + */ + private def propagate(changed: PolyParam): Boolean = + if (Config.trackConstrDeps) + checkBounds(changed) && + propagate(constraint.dependentParams(changed) - changed, Set(changed)) + else + constraint forallParams checkBounds + + /** Ensure validity of constraints for parameters `params` and of all + * parameters that depend on them and that have not been tested + * now or before. If `trackConstrDeps` is not set, do this for all + * parameters in the constraint. + * @param seen the set of parameters that have been tested before. + */ + private def propagate(params: Set[PolyParam], seen: Set[PolyParam]): Boolean = + params.isEmpty || + (params forall checkBounds) && { + val seen1 = seen ++ params + val nextParams = (Set[PolyParam]() /: params) { (ps, p) => + ps ++ (constraint.dependentParams(p) -- seen1) + } + propagate(nextParams, seen1) } /** Check whether the lower bounds of all parameters in this * constraint are a solution to the constraint. + * As an optimization, when `trackConstrDeps` is set, we + * only test that the solutions satisfy the constraints `changed` + * and all parameters that depend on it. */ - def isSatisfiable(useSolved: Boolean): Boolean = { + def isSatisfiable(changed: PolyParam): Boolean = { val saved = solvedConstraint solvedConstraint = true try - constraint.forallParams { poly => - val TypeBounds(lo, hi) = constraint.bounds(poly) - isSubType(approxParams(lo), approxParams(hi)) || - { + if (Config.trackConstrDeps) propagate(changed) + else + constraint.forallParams { param => + checkBounds(param) || { + val TypeBounds(lo, hi) = constraint.bounds(param) ctx.log(i"sub fail $lo <:< $hi") - solvedConstraint = saved ctx.log(i"approximated = ${approxParams(lo)} <:< ${approxParams(hi)}") - ctx.log(TypeComparer.explained(implicit ctx => isSubType(approxParams(lo), approxParams(hi)))) false } - } + } finally solvedConstraint = saved } - def isSatisfiable: Boolean = { - val withSolved = isSatisfiable(true) - val withoutSolved = isSatisfiable(false) - assert(withSolved == withoutSolved, i"sat diff for $constraint, with solved: $withSolved, without: $withoutSolved") - withSolved - } - /** Update constraint for `param` to `bounds`, check that * new constraint is still satisfiable. */ @@ -136,13 +162,12 @@ class TypeComparer(initctx: Context) extends DotClass { val saved = constraint constraint = constraint.updated(param, bounds) - propagate && - { isSatisfiable || { - ctx.log(i"SAT $constraint produced by $param $bounds is not satisfiable") - false - } - } || - { constraint = saved; false } // don't leave the constraint in unsatisfiable state + if (propagate(param)) { + if (isSatisfiable(param)) return true + ctx.log(i"SAT $constraint produced by $param $bounds is not satisfiable") + } + constraint = saved // don't leave the constraint in unsatisfiable state + false } private def addConstraint1(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = { diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala index 65cebf967..59c934e0d 100644 --- a/src/dotty/tools/dotc/core/TyperState.scala +++ b/src/dotty/tools/dotc/core/TyperState.scala @@ -14,7 +14,7 @@ import collection.mutable class TyperState(val reporter: Reporter) extends DotClass with Showable { /** The current constraint set */ - def constraint: Constraint = new Constraint(SimpleMap.Empty) + def constraint: Constraint = new Constraint(SimpleMap.Empty, SimpleMap.Empty) def constraint_=(c: Constraint): Unit = {} /** The uninstantiated variables */ @@ -48,7 +48,7 @@ class TyperState(val reporter: Reporter) extends DotClass with Showable { * type variable instantiation cannot be retracted anymore. Then, remove * no-longer needed constraint entries. */ - def gc(): Unit = () + def gc()(implicit ctx: Context): Unit = () /** Is it allowed to commit this state? */ def isCommittable: Boolean = false @@ -96,7 +96,7 @@ extends TyperState(reporter) { reporter.flush() } - override def gc(): Unit = { + override def gc()(implicit ctx: Context): Unit = { val toCollect = new mutable.ListBuffer[PolyType] constraint foreachTypeVar { tvar => if (!tvar.inst.exists) { diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index bb882e36c..088a2e3af 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -2119,11 +2119,12 @@ object Types { override def toString = if (lo eq hi) s"TypeAlias($lo)" else s"TypeBounds($lo, $hi)" + + override def computeHash = unsupported("computeHash") } class CachedTypeBounds(lo: Type, hi: Type, hc: Int) extends TypeBounds(lo, hi) { myHash = hc - override def computeHash = unsupported("computeHash") } final class CoTypeBounds(lo: Type, hi: Type, hc: Int) extends CachedTypeBounds(lo, hi, hc) { |