Consolidation of TyperState and Constraint

Removing undetVars and instTypes as separately assignable fields. This is better for maintaining invariants by design.

4 files changed, 122 insertions, 81 deletions

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)