Performance improvement: Avoid most operations in interpolateUndetVars

Perform the operation only if there are qualifying type variables, which is rarely the case.
Reverted variances optimization to simpler and shorter previous implementation, because variances
is no longer hot.

4 files changed, 39 insertions, 73 deletions

diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala
index 6070b4f49..272e93dd3 100644
--- a/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/src/dotty/tools/dotc/core/TypeOps.scala
@@ -113,54 +113,6 @@ trait TypeOps { this: Context =>
     }
   }
 
-  type VarianceMap = SimpleMap[TypeVar, Integer]
-
-  /** Add occurrences of type variables in type `tp` to variance map `vmap` */
-  final def addVariances(vmap: VarianceMap, tp: Type, variance: Int, include: TypeVar => Boolean, accu: VariancesAccumulator): VarianceMap = tp match {
-    case tp: TypeRef =>
-      if (tp.symbol.isStatic) vmap
-      else {
-        val prefix = tp.prefix
-        val tp1 = tp.lookupRefined(prefix, tp.name)
-        addVariances(vmap, if (tp1.exists) tp1 else prefix, variance, include, accu)
-      }
-    case tp: TermRef =>
-      if (tp.symbol.isStatic) vmap
-      else addVariances(vmap, tp.prefix, variance, include, accu)
-
-    case _: ThisType
-      | _: BoundType
-      | NoPrefix => vmap
-
-    case tp: RefinedType =>
-      addVariances(
-        addVariances(vmap, tp.parent, variance, include, accu),
-        tp.refinedInfo, variance, include, accu)
-
-    case bounds @ TypeBounds(lo, hi) if lo eq hi =>
-      addVariances(vmap, lo, variance * bounds.variance, include, accu)
-
-    case tp: TypeVar if !tp.isInstantiated && (typerState.constraint contains tp) && include(tp) =>
-      val v = vmap(tp)
-      if (v == null) vmap.updated(tp, variance)
-      else if (v == variance) vmap
-      else vmap.updated(tp, 0)
-
-    case _ =>
-      (if (accu != null) accu else new VariancesAccumulator(include)).runOver(vmap, tp, variance)
-  }
-
-  class VariancesAccumulator(include: TypeVar => Boolean) extends TypeAccumulator[VarianceMap] {
-    def apply(vmap: VarianceMap, tp: Type): VarianceMap = addVariances(vmap, tp, variance, include, this)
-    def runOver(vmap: VarianceMap, tp: Type, variance: Int): VarianceMap = {
-      val saved = this.variance
-      this.variance = variance
-      val result = foldOver(vmap, tp)
-      this.variance = saved
-      result
-    }
-  }
-
   private def enterArgBinding(formal: Symbol, info: Type, cls: ClassSymbol, decls: Scope) = {
     val lazyInfo = new LazyType { // needed so we do not force `formal`.
       def complete(denot: SymDenotation)(implicit ctx: Context): Unit = {
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 00d719acb..5c65b7ede 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -838,7 +838,19 @@ object Types {
      *  0 means: mixed or non-variant occurrences
      */
     def variances(include: TypeVar => Boolean)(implicit ctx: Context): VarianceMap = track("variances") {
-      ctx.addVariances(SimpleMap.Empty, this, +1, include, null)
+      val accu = new TypeAccumulator[VarianceMap] {
+        def apply(vmap: VarianceMap, t: Type): VarianceMap = t match {
+          case t: TypeVar
+          if !t.isInstantiated && (ctx.typerState.constraint contains t) && include(t) =>
+            val v = vmap(t)
+            if (v == null) vmap.updated(t, variance)
+            else if (v == variance) vmap
+            else vmap.updated(t, 0)
+          case _ =>
+            foldOver(vmap, t)
+        }
+      }
+      accu(SimpleMap.Empty, this)
     }
 
     /** A simplified version of this type which is equivalent wrt =:= to this type.
diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala
index 763904ac4..986ddf570 100644
--- a/src/dotty/tools/dotc/typer/Inferencing.scala
+++ b/src/dotty/tools/dotc/typer/Inferencing.scala
@@ -602,31 +602,33 @@ object Inferencing {
    *  approximate it by its lower bound. Otherwise, if it appears contravariantly
    *  in type `tp` approximate it by its upper bound.
    */
-  def interpolateUndetVars(tree: Tree)(implicit ctx: Context): Unit = Stats.track("interpolateUndetVars") {
-    val tp = tree.tpe.widen
+  def interpolateUndetVars(tree: Tree)(implicit ctx: Context): Unit = {
     val constraint = ctx.typerState.constraint
-
-    constr.println(s"interpolate undet vars in ${tp.show}, pos = ${tree.pos}, mode = ${ctx.mode}, undets = ${constraint.uninstVars map (tvar => s"${tvar.show}@${tvar.owningTree.pos}")}")
-    constr.println(s"qualifying undet vars: ${constraint.uninstVars filter qualifies map (tvar => s"$tvar / ${tvar.show}")}, constraint: ${constraint.show}")
-
-    def qualifies(tvar: TypeVar) = tree contains tvar.owningTree
-    val vs = tp.variances(qualifies)
-    var changed = false
-    vs foreachBinding { (tvar, v) =>
-      if (v != 0) {
-        typr.println(s"interpolate ${if (v == 1) "co" else "contra"}variant ${tvar.show} in ${tp.show}")
-        tvar.instantiate(fromBelow = v == 1)
-        changed = true
+    val qualifies = (tvar: TypeVar) => tree contains tvar.owningTree
+    def interpolate() = Stats.track("interpolateUndetVars") {
+      val tp = tree.tpe.widen
+      constr.println(s"interpolate undet vars in ${tp.show}, pos = ${tree.pos}, mode = ${ctx.mode}, undets = ${constraint.uninstVars map (tvar => s"${tvar.show}@${tvar.owningTree.pos}")}")
+      constr.println(s"qualifying undet vars: ${constraint.uninstVars filter qualifies map (tvar => s"$tvar / ${tvar.show}")}, constraint: ${constraint.show}")
+
+      val vs = tp.variances(qualifies)
+      var changed = false
+      vs foreachBinding { (tvar, v) =>
+        if (v != 0) {
+          typr.println(s"interpolate ${if (v == 1) "co" else "contra"}variant ${tvar.show} in ${tp.show}")
+          tvar.instantiate(fromBelow = v == 1)
+          changed = true
+        }
       }
+      if (changed) // instantiations might have uncovered new typevars to interpolate
+        interpolateUndetVars(tree)
+      else
+        for (tvar <- constraint.uninstVars)
+          if (!(vs contains tvar) && qualifies(tvar)) {
+            typr.println(s"instantiating non-occurring ${tvar.show} in ${tp.show}")
+            tvar.instantiate(fromBelow = true)
+          }
     }
-    if (changed) // instantiations might have uncovered new typevars to interpolate
-      interpolateUndetVars(tree)
-    else
-      for (tvar <- constraint.uninstVars)
-        if (!(vs contains tvar) && qualifies(tvar)) {
-          typr.println(s"instantiating non-occurring ${tvar.show} in ${tp.show}")
-          tvar.instantiate(fromBelow = true)
-        }
+    if (constraint.uninstVars exists qualifies) interpolate()
   }
 
   /** Instantiate undetermined type variables to that type `tp` is
diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala
index 49792cb73..7e44f6a76 100644
--- a/src/dotty/tools/dotc/typer/Typer.scala
+++ b/src/dotty/tools/dotc/typer/Typer.scala
@@ -84,8 +84,8 @@ class Typer extends Namer with Applications with Implicits {
   /** The type of a selection with `name` of a tree with type `site`.
    */
   def selectionType(site: Type, name: Name, pos: Position)(implicit ctx: Context): Type = {
-    val refDenot = site.member(name)
-    if (reallyExists(refDenot)) site.select(name, refDenot)
+    val mbr = site.member(name)
+    if (reallyExists(mbr)) site.select(name, mbr)
     else {
       if (!site.isErroneous) {
         typr.println(s"site = $site, baseClasses = ${site.baseClasses}")