Handling typevars in inference.

Fleshed out handling of typevars for type inference. Also added some more methods to typer, for blocks, ifs and assignments. (Closures are still wip).

5 files changed, 153 insertions, 37 deletions

diff --git a/src/dotty/tools/dotc/core/Denotations.scala b/src/dotty/tools/dotc/core/Denotations.scala
index 16c75e38b..8b5dcc5dc 100644
--- a/src/dotty/tools/dotc/core/Denotations.scala
+++ b/src/dotty/tools/dotc/core/Denotations.scala
@@ -659,7 +659,7 @@ object Denotations {
       def recur(path: Name, len: Int): Denotation = {
         val point = path.lastIndexOf('.', len - 1)
         val owner =
-          if (point > 0) recur(path.toTermName, point).disambiguate(_.isParameterless)
+          if (point > 0) recur(path.toTermName, point).disambiguate(_.info.isParameterless)
           else if (path.isTermName) defn.RootClass.denot
           else defn.EmptyPackageClass.denot
         if (!owner.exists) owner
diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala
index 258604df4..d2be45444 100644
--- a/src/dotty/tools/dotc/core/SymDenotations.scala
+++ b/src/dotty/tools/dotc/core/SymDenotations.scala
@@ -287,12 +287,6 @@ object SymDenotations {
     /** Is this a user defined "def" method? Excluded are accessors and stable values */
     final def isSourceMethod = this is (Method, butNot = Accessor)
 
-    /** Is this either not a method at all, or a parameterless method? */
-    final def isParameterless(implicit ctx: Context) = info match {
-      case _: MethodType | _: PolyType => false
-      case _ => true
-    }
-
     /** Is this a setter? */
     final def isGetter = (this is Accessor) && !originalName.isSetterName
 
diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala
index e492eee60..b00e55e29 100644
--- a/src/dotty/tools/dotc/core/TyperState.scala
+++ b/src/dotty/tools/dotc/core/TyperState.scala
@@ -14,10 +14,17 @@ class TyperState(val reporter: Reporter = ThrowingReporter) extends DotClass {
   def constraint: Constraint = new Constraint(SimpleMap.Empty)
 
   /** The currently uninstantiated TypeVars */
-  def undetVars: List[TypeVar] = Nil
+  def undetVars: Set[TypeVar] = Set()
+
+  /** 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. 
+   */
+  def instType: SimpleMap[TypeVar, Type] = SimpleMap.Empty
 
   def constraint_=(c: Constraint): Unit = {}
-  def undetVars_=(vs: List[TypeVar]): Unit = unsupported("undetVars_=")
+  def undetVars_=(vs: Set[TypeVar]): Unit = unsupported("undetVars_=")
+  def instType_=(m: SimpleMap[TypeVar, Type]): Unit = unsupported("instType_=")
 
   def fresh: TyperState = this
 
@@ -28,19 +35,42 @@ class MutableTyperState(previous: TyperState, reporter: Reporter)
 extends TyperState(reporter) {
 
   private var myConstraint: Constraint = previous.constraint
-  private var myUndetVars: List[TypeVar] = previous.undetVars
+  private var myUndetVars: Set[TypeVar] = previous.undetVars
+  private var myInstType: SimpleMap[TypeVar, Type] = previous.instType
 
   override def constraint = myConstraint
   override def undetVars = myUndetVars
+  override def instType = myInstType
 
   override def constraint_=(c: Constraint) = myConstraint = c
-  override def undetVars_=(vs: List[TypeVar]) = myUndetVars = vs
+  override def undetVars_=(vs: Set[TypeVar]) = myUndetVars = vs
+  override def instType_=(m: SimpleMap[TypeVar, Type]): Unit = myInstType = m
 
   override def fresh: TyperState = new MutableTyperState(this, new StoreReporter)
 
+  /** Commit typer state so that its information is copied into current typer state
+   *  In addition (1) the owning state of undetermined or temporarily instantiated
+   *  type variables changes from this typer state to the current one. (2) Variables
+   *  that were temporarily instantiated in the current typer state are permanently
+   *  instantiated instead.
+   */
   override def commit()(implicit ctx: Context) = {
-    ctx.typerState.constraint = constraint
-    ctx.typerState.undetVars = undetVars
+    var targetState = ctx.typerState
+    targetState.constraint = constraint
+    targetState.undetVars = undetVars
+    targetState.instType = instType
+
+    def adjustOwningState(tvar: TypeVar) =
+      if (tvar.owningState eq this) tvar.owningState = targetState
+    undetVars foreach adjustOwningState
+    instType foreachKey { case tvar: TypeVar =>
+      adjustOwningState(tvar)
+      if (tvar.owningState == targetState) {
+        tvar.inst = instType(tvar)
+        targetState.instType = targetState.instType remove tvar
+      }
+    }
+
     reporter.flush()
   }
 }
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index c3e15d94c..8df651180 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -150,7 +150,8 @@ object Types {
     }
 
     /** Does this type occur as a part of type `that`? */
-    final def occursIn(that: Type): Boolean = that.existsPart(this == _)
+    final def occursIn(that: Type)(implicit ctx: Context): Boolean =
+      that.existsPart(this == _)
 
     def isRepeatedParam(implicit ctx: Context): Boolean =
       defn.RepeatedParamAliases contains typeSymbol
@@ -159,16 +160,21 @@ object Types {
 
     /** Returns true if there is a part of this type that satisfies predicate `p`.
      */
-    final def existsPart(p: Type => Boolean): Boolean =
-      new ExistsAccumulator(p)(false, this)
+    final def existsPart(p: Type => Boolean)(implicit ctx: Context): Boolean =
+      new ExistsAccumulator(p).apply(false, this)
 
     /** Returns true if all parts of this type satisfy predicate `p`.
      */
-    final def forallParts(p: Type => Boolean): Boolean = !existsPart(!p(_))
+    final def forallParts(p: Type => Boolean)(implicit ctx: Context): Boolean = !existsPart(!p(_))
 
     /** The parts of this type which are type or term refs */
     final def namedParts(implicit ctx: Context): Set[NamedType] =
-      new PartsAccumulator().apply(Set(), this)
+      namedPartsWith(Function.const(true))
+
+    final def namedPartsWith(p: NamedType => Boolean)(implicit ctx: Context): Set[NamedType] =
+      new NamedPartsAccumulator(p).apply(Set(), this)
+
+    final def foreach(f: Type => Unit): Unit = ???
 
     /** Map function over elements of an AndType, rebuilding with & */
     def mapAnd(f: Type => Type)(implicit ctx: Context): Type = thisInstance match {
@@ -498,7 +504,7 @@ object Types {
     /** Map a TypeVar to either its instance if it is instantiated, or its origin,
      *  if not. Identity on all other types.
      */
-    def thisInstance: Type = this
+    def thisInstance(implicit ctx: Context): Type = this
 
     /** Widen from singleton type to its underlying non-singleton
      *  base type by applying one or more `underlying` dereferences,
@@ -535,7 +541,7 @@ object Types {
     /** If this is a refinement type, the unrefined parent,
      *  else the type itself.
      */
-    final def unrefine: Type = thisInstance match {
+    final def unrefine(implicit ctx: Context): Type = thisInstance match {
       case tp @ RefinedType(tycon, _) => tycon.unrefine
       case tp => tp
     }
@@ -594,6 +600,15 @@ object Types {
       case pt: PolyType => pt.resultType.paramTypess
       case _ => Nil
     }
+
+    /** Is this either not a method at all, or a parameterless method? */
+    final def isParameterless: Boolean = this match {
+      case mt: MethodType => false
+      case pt: PolyType => pt.resultType.isParameterless
+      case _ => true
+    }
+
+
 /* Not sure whether we'll need this
     final def firstParamTypes: List[Type] = this match {
       case mt: MethodType => mt.paramTypes
@@ -908,6 +923,12 @@ object Types {
 
     def toText(printer: Printer): Text = printer.toText(this)
 
+    /** `tp` is either a type variable or poly param. Returns
+     *  Covariant      if all occurrences of `tp` in this type are covariant
+     *  Contravariant  if all occurrences of `tp` in this type are contravariant
+     *  Covariant | Contravariant  if there are no occurrences of `tp` in this type
+     *  EmptyFlags     if `tp` occurs noon-variantly in this type
+     */
     def varianceOf(tp: Type): FlagSet = ???
 
 // ----- hashing ------------------------------------------------------
@@ -1403,9 +1424,18 @@ object Types {
     def isJava = false
     def isImplicit = false
 
-    lazy val isDependent = resultType existsPart {
-      case MethodParam(mt, _) => mt eq this
-      case _ => false
+    private[this] var myIsDependent: Boolean = _
+    private[this] var isDepKnown = false
+
+    def isDependent(implicit ctx: Context) = {
+      if (!isDepKnown) {
+        myIsDependent = resultType existsPart {
+          case MethodParam(mt, _) => mt eq this
+          case _ => false
+        }
+        isDepKnown = true
+      }
+      myIsDependent
     }
 
     private[this] var _signature: Signature = _
@@ -1623,14 +1653,76 @@ object Types {
     override def toString = s"RefinedThis(${binder.hashCode})"
   }
 
-  final case class TypeVar(origin: PolyParam) extends UncachedProxyType with ValueType {
-    private var inst: Type = NoType
-    def isInstantiated = inst ne NoType
-    def instantiateWith(tp: Type) = inst = tp
-    override def thisInstance = if (isInstantiated) inst else origin
+  /** A type variable is essentially a switch that models some part of a substitution.
+   *  It is first linked to `origin`, a poly param that's in the current constraint set.
+   *  It can then be (once) instantiated to some other type. The instantiation is
+   *  recorded in the type variable itself, or else, if the current type state
+   *  is different from the variable's creation state (meaning unrolls are possible)
+   *  in the current typer state. Every type variable is referred to by exactly
+   *  one inferred type parameter in a TypeApply tree.
+   *
+   *  @param  origin        The parameter that's tracked by the type variable.
+   *  @param  creatorState  The typer state in which the variable was created.
+   *  @param  pos           The position of the TypeApply tree that introduces
+   *                        the type variable.
+   */
+  final class TypeVar(val origin: PolyParam, creatorState: TyperState, val pos: Position) extends UncachedProxyType with ValueType {
+
+    /** The permanent instance type of the the variable, or NoType is none is given yet */
+    private[core] var inst: Type = NoType
+
+    /** The state owning the variable. This is at first creationState, but it can
+     *  be changed to an enclosing state on a commit
+     */
+    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
+      }
+
+    /** Is the variable already instantiated? */
+    def isInstantiated(implicit ctx: Context) = instanceOpt.exists
+
+    /** Instantiate variable with given type */
+    def instantiateWith(tp: Type)(implicit ctx: Context): Type = {
+      assert(owningState.undetVars contains this)
+      owningState.undetVars -= this
+      if (ctx.typerState eq creatorState) inst = tp
+      else ctx.typerState.instType = ctx.typerState.instType.updated(this, tp)
+      tp
+    }
+
+    /** Instantiate variable from the constraints over its `origin`.
+     *  If `fromBelow` is true, the variable is instantiated to the lub
+     *  of its lower bounds in the current constraint; otherwie it is
+     *  instantiated to the glb of its upper bounds.
+     */
+    def instantiate(fromBelow: Boolean)(implicit ctx: Context): Type =
+      instantiateWith(ctx.typeComparer.approximate(origin, fromBelow))
+
+    /** If the variable is instantiated, its instance, otherwise its origin */
+    override def thisInstance(implicit ctx: Context) = {
+      val inst = instanceOpt
+      if (inst.exists) inst else origin
+    }
+
+    /** Same as `thisInstance` */
     override def underlying(implicit ctx: Context): Type = thisInstance
+
+    override def hashCode: Int = System.identityHashCode(this)
     override def equals(that: Any) = this eq that.asInstanceOf[AnyRef]
-    override def toString = thisInstance.toString
+
+    override def toString =
+      if (inst.exists) inst.toString else s"TypeVar($origin)"
   }
 
   // ------ ClassInfo, Type Bounds ------------------------------------------------------------
@@ -1871,12 +1963,12 @@ object Types {
       case _ =>
         false
     }
-    def unapply(tp: Type)(implicit ctx: Context): Option[(SingleDenotation, List[Type], Type)] =
+    def unapply(tp: Type)(implicit ctx: Context): Option[SingleDenotation] =
       if (isInstantiatable(tp)) {
         val absMems = tp.abstractTermMembers
         if (absMems.size == 1)
           absMems.head.info match {
-            case mt: MethodType if !mt.isDependent => Some((absMems.head, mt.paramTypes, mt.resultType))
+            case mt: MethodType if !mt.isDependent => Some(absMems.head)
             case _=> None
           }
         else None
@@ -1927,7 +2019,7 @@ object Types {
       case tp @ AnnotatedType(annot, underlying) =>
         tp.derivedAnnotatedType(mapOver(annot), this(underlying))
 
-      case tp @ TypeVar(_) =>
+      case tp: TypeVar =>
         apply(tp.thisInstance)
 
       case tp @ WildcardType =>
@@ -1980,7 +2072,7 @@ object Types {
 
   // ----- TypeAccumulators ----------------------------------------------------
 
-  abstract class TypeAccumulator[T] extends ((T, Type) => T) {
+  abstract class TypeAccumulator[T](implicit ctx: Context) extends ((T, Type) => T) {
     def apply(x: T, tp: Type): T
 
     protected def apply(x: T, annot: Annotation): T = x // don't go into annotations
@@ -2024,13 +2116,13 @@ object Types {
     }
   }
 
-  class ExistsAccumulator(p: Type => Boolean) extends TypeAccumulator[Boolean] {
+  class ExistsAccumulator(p: Type => Boolean)(implicit ctx: Context) extends TypeAccumulator[Boolean] {
     def apply(x: Boolean, tp: Type) = x || p(tp) || foldOver(x, tp)
   }
 
-  class PartsAccumulator(implicit ctx: Context) extends TypeAccumulator[Set[NamedType]] {
+  class NamedPartsAccumulator(p: NamedType => Boolean)(implicit ctx: Context) extends TypeAccumulator[Set[NamedType]] {
     def apply(x: Set[NamedType], tp: Type): Set[NamedType] = tp match {
-      case tp: NamedType =>
+      case tp: NamedType if (p(tp)) =>
         foldOver(x + tp, tp)
       case tp: ThisType =>
         apply(x, tp.underlying)
diff --git a/src/dotty/tools/dotc/core/pickling/UnPickler.scala b/src/dotty/tools/dotc/core/pickling/UnPickler.scala
index a488e0e18..4c96c5e4b 100644
--- a/src/dotty/tools/dotc/core/pickling/UnPickler.scala
+++ b/src/dotty/tools/dotc/core/pickling/UnPickler.scala
@@ -596,7 +596,7 @@ class UnPickler(bytes: Array[Byte], classRoot: ClassDenotation, moduleClassRoot:
         else ThisType(cls)
       case SINGLEtpe =>
         val pre = readTypeRef()
-        val sym = readDisambiguatedSymbolRef(_.isParameterless)
+        val sym = readDisambiguatedSymbolRef(_.info.isParameterless)
         if (isLocal(sym) || (pre == NoPrefix)) TermRef.withSym(pre, sym.asTerm)
         else TermRef.withSig(pre, sym.name.asTermName, NotAMethod)
       case SUPERtpe =>