Performance improvements: Changes to TypeAccumulators and variances.

4 files changed, 95 insertions, 36 deletions

diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala
index 272e93dd3..6070b4f49 100644
--- a/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/src/dotty/tools/dotc/core/TypeOps.scala
@@ -113,6 +113,54 @@ 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 b15068d81..c1d3de582 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -838,18 +838,7 @@ object Types {
      *  0 means: mixed or non-variant occurrences
      */
     def variances(include: TypeVar => Boolean)(implicit ctx: Context): VarianceMap = track("variances") {
-      val accu = new TypeAccumulator[VarianceMap] {
-        def apply(vmap: VarianceMap, t: Type): VarianceMap = t match {
-          case t: TypeVar if !t.isInstantiated && 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)
+      ctx.addVariances(SimpleMap.Empty, this, +1, include, null)
     }
 
     /** A simplified version of this type which is equivalent wrt =:= to this type.
@@ -2089,7 +2078,7 @@ object Types {
 
   // ----- TypeMaps --------------------------------------------------------------------
 
-  abstract class TypeMap(implicit ctx: Context) extends (Type => Type) { thisMap =>
+  abstract class TypeMap(implicit protected val ctx: Context) extends (Type => Type) { thisMap =>
 
     protected def stopAtStatic = true
 
@@ -2110,6 +2099,20 @@ object Types {
       case tp: RefinedType =>
         tp.derivedRefinedType(this(tp.parent), tp.refinedName, this(tp.refinedInfo))
 
+      case tp @ TypeBounds(lo, hi) =>
+        if (lo eq hi) {
+          val saved = variance
+          variance = variance * tp.variance
+          val lo1 = this(lo)
+          variance = saved
+          tp.derivedTypeAlias(lo1)
+        } else {
+          variance = -variance
+          val lo1 = this(lo)
+          variance = -variance
+          tp.derivedTypeBounds(lo1, this(hi))
+        }
+
       case tp @ MethodType(pnames, ptypes) =>
         variance = -variance
         val ptypes1 = ptypes mapConserve this
@@ -2129,20 +2132,6 @@ object Types {
       case tp @ SuperType(thistp, supertp) =>
         tp.derivedSuperType(this(thistp), this(supertp))
 
-      case tp @ TypeBounds(lo, hi) =>
-        if (lo eq hi) {
-          val saved = variance
-          variance = variance * tp.variance
-          val lo1 = this(lo)
-          variance = saved
-          tp.derivedTypeAlias(lo1)
-        } else {
-          variance = -variance
-          val lo1 = this(lo)
-          variance = -variance
-          tp.derivedTypeBounds(lo1, this(hi))
-        }
-
       case tp: ClassInfo =>
         mapClassInfo(tp)
 
@@ -2213,7 +2202,10 @@ object Types {
 
   // ----- TypeAccumulators ----------------------------------------------------
 
-  abstract class TypeAccumulator[T](implicit ctx: Context) extends ((T, Type) => T) {
+  abstract class TypeAccumulator[T](implicit protected val ctx: Context) extends ((T, Type) => T) {
+
+    protected def stopAtStatic = true
+
     def apply(x: T, tp: Type): T
 
     protected def applyToAnnot(x: T, annot: Annotation): T = x // don't go into annotations
@@ -2222,11 +2214,14 @@ object Types {
 
     def foldOver(x: T, tp: Type): T = tp match {
       case tp: TypeRef =>
-        val tp1 = tp.lookupRefined(tp.prefix, tp.name)
-        this(x, if (tp1.exists) tp1 else tp.prefix)
-
+        if (stopAtStatic && tp.symbol.isStatic) x
+        else {
+          val tp1 = tp.lookupRefined(tp.prefix, tp.name)
+          this(x, if (tp1.exists) tp1 else tp.prefix)
+        }
       case tp: TermRef =>
-        this(x, tp.prefix)
+        if (stopAtStatic && tp.symbol.isStatic) x
+        else this(x, tp.prefix)
 
       case _: ThisType
          | _: BoundType
@@ -2235,6 +2230,21 @@ object Types {
       case tp: RefinedType =>
         this(this(x, tp.parent), tp.refinedInfo)
 
+      case bounds @ TypeBounds(lo, hi) =>
+        if (lo eq hi) {
+          val saved = variance
+          variance = variance * bounds.variance
+          val result = this(x, lo)
+          variance = saved
+          result
+        }
+        else {
+          variance = -variance
+          val y = this(x, lo)
+          variance = -variance
+          this(y, hi)
+        }
+
       case tp @ MethodType(pnames, ptypes) =>
         variance = -variance
         val y = foldOver(x, ptypes)
@@ -2296,10 +2306,12 @@ object Types {
   }
 
   class ExistsAccumulator(p: Type => Boolean)(implicit ctx: Context) extends TypeAccumulator[Boolean] {
+    override def stopAtStatic = false
     def apply(x: Boolean, tp: Type) = x || p(tp) || foldOver(x, tp)
   }
 
   class NamedPartsAccumulator(p: NamedType => Boolean)(implicit ctx: Context) extends TypeAccumulator[mutable.Set[NamedType]] {
+    override def stopAtStatic = false
     def maybeAdd(x: mutable.Set[NamedType], tp: NamedType) = if (p(tp)) x += tp else x
     val seen: mutable.Set[Type] = mutable.Set()
     def apply(x: mutable.Set[NamedType], tp: Type): mutable.Set[NamedType] =
diff --git a/src/dotty/tools/dotc/typer/Implicits.scala b/src/dotty/tools/dotc/typer/Implicits.scala
index a66864269..7d03b1edf 100644
--- a/src/dotty/tools/dotc/typer/Implicits.scala
+++ b/src/dotty/tools/dotc/typer/Implicits.scala
@@ -269,7 +269,7 @@ trait ImplicitRunInfo { self: RunInfo =>
      *  abstract types are eliminated.
      */
     object liftToClasses extends TypeMap {
-      private implicit val ctx: Context = liftingCtx
+      override implicit protected val ctx: Context = liftingCtx
       override def stopAtStatic = true
       def apply(tp: Type) = tp match {
         case tp: TypeRef if tp.symbol.isAbstractOrAliasType =>
diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala
index 19a6f3bb5..763904ac4 100644
--- a/src/dotty/tools/dotc/typer/Inferencing.scala
+++ b/src/dotty/tools/dotc/typer/Inferencing.scala
@@ -610,7 +610,7 @@ object Inferencing {
     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(tvar => (constraint contains tvar) && qualifies(tvar))
+    val vs = tp.variances(qualifies)
     var changed = false
     vs foreachBinding { (tvar, v) =>
       if (v != 0) {
@@ -634,8 +634,7 @@ object Inferencing {
    *  typevar is not uniquely determined, return that typevar in a Some.
    */
   def maximizeType(tp: Type)(implicit ctx: Context): Option[TypeVar] = Stats.track("maximizeType") {
-    val constraint = ctx.typerState.constraint
-    val vs = tp.variances(constraint contains _)
+    val vs = tp.variances(alwaysTrue)
     var result: Option[TypeVar] = None
     vs foreachBinding { (tvar, v) =>
       if (v == 1) tvar.instantiate(fromBelow = false)