New constraint implementation: OrderingConstraint

This is one both a bit simpler and a faster than TrackingConstraint.
Main change is to replace the 2-d bitmap for ordering with two SimpleMaps
which record for each parameter the smaller and greater parameters.
This is faster in practice because the ordering relation is sparse.

4 files changed, 545 insertions, 63 deletions

diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala
index 873a3c913..cedfb52eb 100644
--- a/src/dotty/tools/dotc/core/Constraint.scala
+++ b/src/dotty/tools/dotc/core/Constraint.scala
@@ -42,7 +42,7 @@ abstract class Constraint extends Showable {
   def typeVarOfParam(param: PolyParam): Type
       
   /** Is it known that `param1 <:< param2`? */
-  def isLess(param1: PolyParam, param2: PolyParam)(implicit ctx: Context): Boolean
+  def isLess(param1: PolyParam, param2: PolyParam): Boolean
 
   /** The parameters that are known to be smaller wrt <: than `param` */ 
   def lower(param: PolyParam): List[PolyParam]
diff --git a/src/dotty/tools/dotc/core/OrderingConstraint.scala b/src/dotty/tools/dotc/core/OrderingConstraint.scala
new file mode 100644
index 000000000..2deec51a8
--- /dev/null
+++ b/src/dotty/tools/dotc/core/OrderingConstraint.scala
@@ -0,0 +1,481 @@
+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 OrderingConstraint {
+
+  /** The type of `Constraint#boundsMap` */
+  type ParamBounds = SimpleMap[PolyType, Array[Type]]
+  
+  /** The type of `Constraint#lowerMap`, `Constraint#upperMap` */
+  type ParamOrdering = SimpleMap[PolyType, Array[List[PolyParam]]]
+  
+  /** A new constraint with given maps */
+  private def newConstraint(boundsMap: ParamBounds, lowerMap: ParamOrdering, upperMap: ParamOrdering)(implicit ctx: Context) : OrderingConstraint = {
+    val result = new OrderingConstraint(boundsMap, lowerMap, upperMap)
+    if (Config.checkConstraintsNonCyclic) result.checkNonCyclic()
+    ctx.runInfo.recordConstraintSize(result, result.boundsMap.size)
+    result
+  }
+  
+  /** A lens for updating a single entry array in one of the three constraint maps */
+  abstract class ConstraintLens[T <: AnyRef: ClassTag] {
+    def entries(c: OrderingConstraint, poly: PolyType): Array[T] 
+    def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[T])(implicit ctx: Context): OrderingConstraint
+    def initial: T
+    
+    def apply(c: OrderingConstraint, poly: PolyType, idx: Int) = {
+      val es = entries(c, poly)
+      if (es == null) initial else es(idx)
+    }
+ 
+    /** The `current` constraint but with the entry for `param` updated to `entry`.
+     *  `current` is used linearly. If it is different from `prev` it is
+     *  known to be dead after the call. Hence it is OK to update destructively
+     *  parts of `current` which are not shared by `prev`.
+     */
+    def update(prev: OrderingConstraint, current: OrderingConstraint, 
+        poly: PolyType, idx: Int, entry: T)(implicit ctx: Context): OrderingConstraint = {
+      var es = entries(current, poly)
+      if (es != null && (es(idx) eq entry)) current
+      else {
+        val result = 
+          if (es == null) {
+            es = Array.fill(poly.paramNames.length)(initial)
+            updateEntries(current, poly, es)
+          }
+          else if (es ne entries(prev, poly))
+            current // can re-use existing entries array.
+          else {
+            es = es.clone
+            updateEntries(current, poly, es)
+          }
+        es(idx) = entry
+        result
+      }
+    }
+    
+    def update(prev: OrderingConstraint, current: OrderingConstraint, 
+        param: PolyParam, entry: T)(implicit ctx: Context): OrderingConstraint =
+      update(prev, current, param.binder, param.paramNum, entry)
+      
+    def map(prev: OrderingConstraint, current: OrderingConstraint, 
+        poly: PolyType, idx: Int, f: T => T)(implicit ctx: Context): OrderingConstraint = 
+     update(prev, current, poly, idx, f(apply(current, poly, idx)))
+
+    def map(prev: OrderingConstraint, current: OrderingConstraint, 
+        param: PolyParam, f: T => T)(implicit ctx: Context): OrderingConstraint = 
+      map(prev, current, param.binder, param.paramNum, f)
+  }
+
+  val boundsLens = new ConstraintLens[Type] {
+    def entries(c: OrderingConstraint, poly: PolyType): Array[Type] = 
+      c.boundsMap(poly)
+    def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[Type])(implicit ctx: Context): OrderingConstraint = 
+      newConstraint(c.boundsMap.updated(poly, entries), c.lowerMap, c.upperMap)
+    def initial = NoType
+  }
+  
+  val lowerLens = new ConstraintLens[List[PolyParam]] {
+    def entries(c: OrderingConstraint, poly: PolyType): Array[List[PolyParam]] = 
+      c.lowerMap(poly)
+    def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[List[PolyParam]])(implicit ctx: Context): OrderingConstraint = 
+      newConstraint(c.boundsMap, c.lowerMap.updated(poly, entries), c.upperMap)
+    def initial = Nil
+  }
+
+  val upperLens = new ConstraintLens[List[PolyParam]] {
+    def entries(c: OrderingConstraint, poly: PolyType): Array[List[PolyParam]] = 
+      c.upperMap(poly)
+    def updateEntries(c: OrderingConstraint, poly: PolyType, entries: Array[List[PolyParam]])(implicit ctx: Context): OrderingConstraint = 
+      newConstraint(c.boundsMap, c.lowerMap, c.upperMap.updated(poly, entries))
+    def initial = Nil
+  }
+}
+
+import OrderingConstraint._
+
+/** Constraint over undetermined type parameters that keeps separate maps to 
+ *  reflect parameter orderings.
+ *  @param boundsMap 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.
+ *               
+ *  @param lowerMap a map from PolyTypes to arrays. Each array entry corresponds
+ *               to a parameter P of the polytype; it contains all constrained parameters
+ *               Q that are known to be smaller than P, i.e. P <: Q. 
+ *  @param upperMap a map from PolyTypes to arrays. Each array entry corresponds
+ *               to a parameter P of the polytype; it contains all constrained parameters
+ *               Q that are known to be greater than P, i.e. Q <: P. 
+ */
+class OrderingConstraint(private val boundsMap: ParamBounds, 
+                         private val lowerMap : ParamOrdering, 
+                         private val upperMap : ParamOrdering) extends Constraint {
+  
+  type This = OrderingConstraint
+    
+  
+// ----------- Basic indices --------------------------------------------------
+  
+  /** 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)
+
+  /** The `boundsMap` entry corresponding to `param` */
+  def entry(param: PolyParam): Type = {
+    val entries = boundsMap(param.binder)
+    if (entries == null) NoType
+    else entries(param.paramNum)
+  }
+    
+// ----------- Contains tests --------------------------------------------------
+
+  def contains(pt: PolyType): Boolean = boundsMap(pt) != null
+
+  def contains(param: PolyParam): Boolean = {
+    val entries = boundsMap(param.binder)
+    entries != null && entries(param.paramNum).isInstanceOf[TypeBounds]
+  }
+
+  def contains(tvar: TypeVar): Boolean = {
+    val origin = tvar.origin
+    val entries = boundsMap(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 ----------------------------------------------
+    
+  def lower(param: PolyParam): List[PolyParam] = lowerLens(this, param.binder, param.paramNum)
+  def upper(param: PolyParam): List[PolyParam] = upperLens(this, param.binder, param.paramNum)
+    
+  def minLower(param: PolyParam): List[PolyParam] = {
+    val all = lower(param)
+    all.filterNot(p => all.exists(isLess(p, _)))
+  }
+  
+  def minUpper(param: PolyParam): List[PolyParam] = {
+    val all = upper(param)
+    all.filterNot(p => all.exists(isLess(_, p)))
+  }
+  
+  def exclusiveLower(param: PolyParam, butNot: PolyParam): List[PolyParam] =
+    lower(param).filterNot(isLess(_, butNot))
+    
+  def exclusiveUpper(param: PolyParam, butNot: PolyParam): List[PolyParam] =
+    upper(param).filterNot(isLess(butNot, _))
+  
+// ---------- Info related to PolyParams -------------------------------------------
+
+  def isLess(param1: PolyParam, param2: PolyParam): Boolean =
+    upper(param1).contains(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 = boundsMap(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, paramBuf: mutable.ListBuffer[PolyParam], 
+      isUpper: Boolean)(implicit ctx: Context): Type = tp match {
+    case param: PolyParam if contains(param) => 
+      if (!paramBuf.contains(param)) paramBuf += param
+      NoType
+    case tp: AndOrType if isUpper == tp.isAnd =>
+      val tp1 = stripParams(tp.tp1, paramBuf, isUpper)
+      val tp2 = stripParams(tp.tp2, paramBuf, isUpper)
+      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 normalizedType(tp: Type, paramBuf: mutable.ListBuffer[PolyParam], 
+      isUpper: Boolean)(implicit ctx: Context): Type = 
+    stripParams(tp, paramBuf, isUpper)
+      .orElse(if (isUpper) defn.AnyType else defn.NothingType)
+  
+  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)
+    newConstraint(boundsMap.updated(poly, entries1), lowerMap, upperMap).init(poly)
+  }
+    
+  private def init(poly: PolyType)(implicit ctx: Context): This = {
+    var current = this
+    val loBuf, hiBuf = new mutable.ListBuffer[PolyParam]
+    var i = 0
+    while (i < poly.paramNames.length) {
+      val param = PolyParam(poly, i)
+      val bounds = nonParamBounds(param)
+      val lo = normalizedType(bounds.lo, loBuf, isUpper = false)
+      val hi = normalizedType(bounds.hi, hiBuf, isUpper = true)
+      current = boundsLens.update(this, current, poly, i, bounds.derivedTypeBounds(lo, hi))
+      current = (current /: loBuf)(order(_, _, param))
+      current = (current /: hiBuf)(order(_, param, _))
+      loBuf.clear()
+      hiBuf.clear()
+      i += 1
+    }
+    if (Config.checkConstraintsNonCyclic) checkNonCyclic()
+    current
+  }
+  
+// ---------- 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 order(current: This, param1: PolyParam, param2: PolyParam)(implicit ctx: Context): This =
+    if (param1 == param2 || current.isLess(param1, param2)) this
+    else {
+      assert(contains(param1))
+      assert(contains(param2))
+      val newUpper = param2 :: exclusiveUpper(param2, param1)
+      val newLower = param1 :: exclusiveLower(param1, param2)
+      val current1 = (current /: newLower)(upperLens.map(this, _, _, newUpper ::: _))
+      val current2 = (current1 /: newUpper)(lowerLens.map(this, _, _, newLower ::: _))
+      current2
+    }
+
+  def addLess(param1: PolyParam, param2: PolyParam)(implicit ctx: Context): This =
+    order(this, param1, param2)
+      
+  def updateEntry(param: PolyParam, tp: Type)(implicit ctx: Context): This =
+    boundsLens.update(this, this, param, tp)
+    
+  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)
+    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): OrderingConstraint = {
+    val replacement = tp.dealias.stripTypeVar
+    if (param == replacement) this 
+    else {
+      assert(replacement.isValueType)
+      val poly = param.binder
+      val idx = param.paramNum
+      def removeParam(ps: List[PolyParam]) = 
+        ps.filterNot(p => p.binder.eq(poly) && p.paramNum == idx)
+      def replaceParam(tp: Type, atPoly: PolyType, atIdx: Int) = tp match {
+        case bounds: TypeBounds =>
+          val bounds1 = tp.substParam(param, replacement).asInstanceOf[TypeBounds]
+          if (bounds1 eq bounds) bounds
+          else dropParamIn(bounds1, atPoly, atIdx)
+        case _ => tp
+      }
+      var current = this
+      if (isRemovable(poly, idx)) current = remove(poly) 
+      else {
+        current = updateEntry(param, replacement)
+        lowerLens.update(this, current, poly, idx, Nil)
+        upperLens.update(this, current, poly, idx, Nil)
+      }
+      current.foreachParam {(p, i) =>
+        current = boundsLens.map(this, current, p, i, replaceParam(_, p, i))
+        current = lowerLens.map(this, current, p, i, removeParam)
+        current = upperLens.map(this, current, p, i, removeParam)
+      }
+      current
+    }
+  }
+
+  def remove(pt: PolyType)(implicit ctx: Context): This = 
+    newConstraint(boundsMap.remove(pt), lowerMap.remove(pt), upperMap.remove(pt))
+
+  def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = {
+    val entries = boundsMap(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] = boundsMap.keys
+
+  def domainParams: List[PolyParam] = 
+    for {
+      (poly, entries) <- boundsMap.toList
+      n <- 0 until paramCount(entries)
+      if isBounds(entries(n))
+    } yield PolyParam(poly, n)
+
+  def forallParams(p: PolyParam => Boolean): Boolean = {
+    boundsMap.foreachBinding { (poly, entries) =>
+      for (i <- 0 until paramCount(entries))
+        if (isBounds(entries(i)) && !p(PolyParam(poly, i))) return false
+    }
+    true
+  }
+  
+  def foreachParam(p: (PolyType, Int) => Unit): Unit =
+    boundsMap.foreachBinding { (poly, entries) =>
+      0.until(poly.paramNames.length).foreach(p(poly, _))
+    }
+
+  def foreachTypeVar(op: TypeVar => Unit): Unit =
+    boundsMap.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]
+      boundsMap.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 -------------------------------------------
+
+  def checkNonCyclic()(implicit ctx: Context): Unit =
+    domainParams.foreach(checkNonCyclic)
+  
+  private def checkNonCyclic(param: PolyParam)(implicit ctx: Context): Unit =
+    assert(!isLess(param, param), i"cyclic constraint involving $param in $this")
+  
+// ---------- 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, ")"))
+  }
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/TrackingConstraint.scala b/src/dotty/tools/dotc/core/TrackingConstraint.scala
index 3f15f2b37..fc8a083f4 100644
--- a/src/dotty/tools/dotc/core/TrackingConstraint.scala
+++ b/src/dotty/tools/dotc/core/TrackingConstraint.scala
@@ -30,14 +30,14 @@ import TrackingConstraint._
  *               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], 
+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`.
    */
@@ -47,19 +47,19 @@ class TrackingConstraint(private val myMap: ParamInfo,
     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, _) => 
+    myMap.foreachBinding { (pt, _) =>
       polyTypes(idx) = pt
       polyStart(idx) = count
       count += pt.paramNames.length
@@ -67,8 +67,8 @@ class TrackingConstraint(private val myMap: ParamInfo,
     }
     assert(count == params.length)
   }
-  
-  /** The index of given polytype `pt` in this constraint, 
+
+  /** The index of given polytype `pt` in this constraint,
    *  or `polyTypes.length` if constraint does not contain `pt`.
    */
   private def polyIndex(pt: PolyType): Int = {
@@ -76,16 +76,16 @@ class TrackingConstraint(private val myMap: ParamInfo,
     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
 
@@ -98,7 +98,7 @@ class TrackingConstraint(private val myMap: ParamInfo,
     if (entries == null) NoType
     else entries(param.paramNum)
   }
-    
+
 // ----------- Contains tests --------------------------------------------------
 
   def contains(pt: PolyType): Boolean = polyIndex(pt) < polyTypes.length
@@ -116,59 +116,59 @@ class TrackingConstraint(private val myMap: ParamInfo,
   }
 
   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 = 
+
+  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)(implicit ctx: Context): Boolean =
+  def isLess(param1: PolyParam, param2: PolyParam): Boolean =
     less(paramIndex(param1))(paramIndex(param2))
 
-  def nonParamBounds(param: PolyParam): TypeBounds = 
+  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 = 
+  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))
 
@@ -180,16 +180,16 @@ class TrackingConstraint(private val myMap: ParamInfo,
       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, 
+  private def stripParams(tp: Type, handleParam: (PolyParam, Boolean) => Type,
       seenFromBelow: Boolean)(implicit ctx: Context): Type = tp match {
-    case tp: PolyParam => 
+    case tp: PolyParam =>
       handleParam(tp, seenFromBelow)
     case tp: AndOrType if seenFromBelow == tp.isAnd =>
       val tp1 = stripParams(tp.tp1, handleParam, seenFromBelow)
@@ -200,17 +200,17 @@ class TrackingConstraint(private val myMap: ParamInfo,
       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 = 
+  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.
    */
@@ -234,7 +234,7 @@ class TrackingConstraint(private val myMap: ParamInfo,
     for (i <- is) {
       def handleParam(param: PolyParam, seenFromBelow: Boolean): Type = {
         def record(paramIdx: Int): Type = {
-          less1 = 
+          less1 =
             if (seenFromBelow) updatedLess(less1, nparams + i, paramIdx)
             else updatedLess(less1, paramIdx, nparams + i)
           NoType
@@ -247,9 +247,9 @@ class TrackingConstraint(private val myMap: ParamInfo,
     }
     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.
    */
@@ -267,31 +267,31 @@ class TrackingConstraint(private val myMap: ParamInfo,
         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 
+    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 = 
+    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
@@ -342,8 +342,8 @@ class TrackingConstraint(private val myMap: ParamInfo,
       }
       result
     }
-    
-    if (param == replacement) this 
+
+    if (param == replacement) this
     else {
       assert(replacement.isValueType)
       val pt = param.binder
@@ -355,7 +355,7 @@ class TrackingConstraint(private val myMap: ParamInfo,
   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
@@ -364,12 +364,12 @@ class TrackingConstraint(private val myMap: ParamInfo,
     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) 
+      Array.copy(src, start + skipped, dst, start, dst.length - start)
       dst
     }
     newConstraint(
-      myMap = myMap remove pt, 
-      less = shrinkArray(less).map(shrinkSet(_)), 
+      myMap = myMap remove pt,
+      less = shrinkArray(less).map(shrinkSet(_)),
       params = shrinkArray(params))
   }
 
@@ -438,14 +438,14 @@ class TrackingConstraint(private val myMap: ParamInfo,
 
   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 => 
+      case tp: TypeBounds =>
         tp.toText(printer)
-      case _ => 
+      case _ =>
         " := " ~ tp.toText(printer)
     }
     val indent = 3
@@ -469,7 +469,7 @@ class TrackingConstraint(private val myMap: ParamInfo,
             ups = minUpper(param)
             if ups.nonEmpty
           }
-          yield 
+          yield
             (" " * indent) ~ param.toText(printer) ~ " <: " ~
               Text(ups.map(_.toText(printer)), ", ")
         Text(deps, "\n")
diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala
index bdba128a9..1079af510 100644
--- a/src/dotty/tools/dotc/core/TyperState.scala
+++ b/src/dotty/tools/dotc/core/TyperState.scala
@@ -17,7 +17,8 @@ class TyperState(r: Reporter) extends DotClass with Showable {
   def reporter = r
 
   /** The current constraint set */
-  def constraint: Constraint = new TrackingConstraint(SimpleMap.Empty, Array(), Array())
+  def constraint: Constraint = 
+    new OrderingConstraint(SimpleMap.Empty, SimpleMap.Empty, SimpleMap.Empty)
   def constraint_=(c: Constraint): Unit = {}
 
   /** The uninstantiated variables */