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.

1 files changed, 142 insertions, 8 deletions

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) =