Removed TrackingConstraint

It's too hard to keep fixes up-to-date in both constraint implementations.
And anyway, OrderingConstraint is it for now.

Also added comment suggested by @smarter.

2 files changed, 4 insertions, 480 deletions

diff --git a/src/dotty/tools/dotc/core/OrderingConstraint.scala b/src/dotty/tools/dotc/core/OrderingConstraint.scala
index 65185ff4f..53378435e 100644
--- a/src/dotty/tools/dotc/core/OrderingConstraint.scala
+++ b/src/dotty/tools/dotc/core/OrderingConstraint.scala
@@ -288,6 +288,10 @@ class OrderingConstraint(private val boundsMap: ParamBounds,
     newConstraint(boundsMap.updated(poly, entries1), lowerMap, upperMap).init(poly)
   }
     
+  /** Split dependent parameters off the bounds for parameters in `poly`.
+   *  Update all bounds to be normalized and update ordering to account for
+   *  dependent parameters.
+   */
   private def init(poly: PolyType)(implicit ctx: Context): This = {
     var current = this
     val loBuf, hiBuf = new mutable.ListBuffer[PolyParam]
diff --git a/src/dotty/tools/dotc/core/TrackingConstraint.scala b/src/dotty/tools/dotc/core/TrackingConstraint.scala
deleted file mode 100644
index fc8a083f4..000000000
--- a/src/dotty/tools/dotc/core/TrackingConstraint.scala
+++ /dev/null
@@ -1,480 +0,0 @@
-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 TrackingConstraint {
-
-  /** The type of `Constraint#myMap` */
-  type ParamInfo = SimpleMap[PolyType, Array[Type]]
-
-}
-
-import TrackingConstraint._
-
-/** 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
- *               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 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`.
-   */
-  private def newConstraint(myMap: ParamInfo, less: Array[BitSet], params: Array[PolyParam])(implicit ctx: Context) : TrackingConstraint = {
-    val result = new TrackingConstraint(myMap, less, params)
-    if (Config.checkConstraintsNonCyclic) result.checkNonCyclic()
-    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, _) =>
-      polyTypes(idx) = pt
-      polyStart(idx) = count
-      count += pt.paramNames.length
-      idx += 1
-    }
-    assert(count == params.length)
-  }
-
-  /** The index of given polytype `pt` in this constraint,
-   *  or `polyTypes.length` if constraint does not contain `pt`.
-   */
-  private def polyIndex(pt: PolyType): Int = {
-    var i = 0
-    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
-
-  /** 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)
-
-  def entry(param: PolyParam): Type = {
-    val entries = myMap(param.binder)
-    if (entries == null) NoType
-    else entries(param.paramNum)
-  }
-
-// ----------- Contains tests --------------------------------------------------
-
-  def contains(pt: PolyType): Boolean = polyIndex(pt) < polyTypes.length
-
-  def contains(param: PolyParam): Boolean = {
-    val entries = myMap(param.binder)
-    entries != null && entries(param.paramNum).isInstanceOf[TypeBounds]
-  }
-
-  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)
-  }
-
-  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 =
-    (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): Boolean =
-    less(paramIndex(param1))(paramIndex(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 = myMap(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, handleParam: (PolyParam, Boolean) => Type,
-      seenFromBelow: Boolean)(implicit ctx: Context): Type = tp match {
-    case tp: PolyParam =>
-      handleParam(tp, seenFromBelow)
-    case tp: AndOrType if seenFromBelow == tp.isAnd =>
-      val tp1 = stripParams(tp.tp1, handleParam, seenFromBelow)
-      val tp2 = stripParams(tp.tp2, handleParam, seenFromBelow)
-      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 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.
-   */
-  private def nonParamBounds(tp: Type, handleParam: (PolyParam, Boolean) => Type)(implicit ctx: Context): Type = tp match {
-    case tp @ TypeBounds(lo, hi) =>
-      tp.derivedTypeBounds(
-        nonParamType(lo, handleParam, seenFromBelow = false),
-        nonParamType(hi, handleParam, seenFromBelow = true))
-  }
-
-  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)
-    val is = poly.paramBounds.indices
-    val newParams = is.map(PolyParam(poly, _))
-    val params1 = params ++ newParams
-    var less1 = less ++ is.map(Function.const(BitSet.empty))
-    for (i <- is) {
-      def handleParam(param: PolyParam, seenFromBelow: Boolean): Type = {
-        def record(paramIdx: Int): Type = {
-          less1 =
-            if (seenFromBelow) updatedLess(less1, nparams + i, paramIdx)
-            else updatedLess(less1, paramIdx, nparams + i)
-          NoType
-        }
-        if (param.binder eq poly) record(nparams + param.paramNum)
-        else if (contains(param.binder)) record(paramIndex(param))
-        else param
-      }
-      entries1(i) = nonParamBounds(entries1(i), handleParam)
-    }
-    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.
-   */
-  private def updatedLess(less: Array[BitSet], i1: Int, i2: Int): Array[BitSet] = {
-      if (i1 == i2 || less(i1)(i2)) less
-      else {
-        val result = less.clone
-        val newUpper = upperBits(less, i2) + i2
-        def update(j: Int) = {
-          result(j) |= newUpper
-          assert(!result(j)(j))
-        }
-        update(i1)
-        lowerBits(less, i1).foreach(update)
-        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
-    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 =
-      if (isUpper) oldBounds.derivedTypeBounds(lo, hi & bound)
-      else oldBounds.derivedTypeBounds(lo | bound, hi)
-    if (newBounds eq oldBounds) this
-    else 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): TrackingConstraint = {
-    val replacement = tp.dealias.stripTypeVar
-
-    def subst(poly: PolyType, entries: Array[Type]) = {
-      var result = entries
-      var i = 0
-      while (i < paramCount(entries)) {
-        entries(i) match {
-          case oldBounds: TypeBounds =>
-            val newBounds = oldBounds.substParam(param, replacement).asInstanceOf[TypeBounds]
-            if (oldBounds ne newBounds) {
-              if (result eq entries) result = entries.clone
-              result(i) = dropParamIn(newBounds, poly, i)
-            }
-          case _ =>
-        }
-        i += 1
-      }
-      result
-    }
-
-    if (param == replacement) this
-    else {
-      assert(replacement.isValueType)
-      val pt = param.binder
-      val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updateEntry(param, replacement)
-      newConstraint(constr1.myMap mapValues subst, constr1.less, constr1.params)
-    }
-  }
-
-  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
-        else if (i < start + skipped) res
-        else res + (i - skipped))
-    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)
-      dst
-    }
-    newConstraint(
-      myMap = myMap remove pt,
-      less = shrinkArray(less).map(shrinkSet(_)),
-      params = shrinkArray(params))
-  }
-
-  def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = {
-    val entries = myMap(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] = polyTypes.toList
-
-  def domainParams: List[PolyParam] = params.toList.filter(contains)
-
-  def forallParams(p: PolyParam => Boolean): Boolean = {
-    myMap.foreachBinding { (poly, entries) =>
-      for (i <- 0 until paramCount(entries))
-        if (isBounds(entries(i)) && !p(PolyParam(poly, i))) return false
-    }
-    true
-  }
-
-  def foreachTypeVar(op: TypeVar => Unit): Unit =
-    myMap.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]
-      myMap.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 -------------------------------------------
-
-  private def checkNonCyclic(idx: Int)(implicit ctx: Context): Unit =
-    assert(!less(idx)(idx), i"cyclic constraint involving ${params(idx)}")
-
-  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 =>
-        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, ")"))
-  }
-}
-