Selective caching of SelectionProtos and ViewProtos

We cache SelectionProtos if their "compat" parameter is "NoViewsAllowed". We always cache ViewProtos.

That's important for implicit search, because this enables eligible refs to be better cached. To make this work, we add a case to WildApprox which massages SelectionProtos so they also get noViewsAllowed in the compat parameter.

6 files changed, 112 insertions, 74 deletions

diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala
index d9116d2b6..99f396e8b 100644
--- a/src/dotty/tools/dotc/core/Contexts.scala
+++ b/src/dotty/tools/dotc/core/Contexts.scala
@@ -429,7 +429,7 @@ object Contexts {
     }
 
     /** A table for hash consing unique refined types */
-    private[core] val uniqueRefinedTypes = new RefinedUniques
+    private[dotc] val uniqueRefinedTypes = new RefinedUniques
 
     /** A table for hash consing unique named types */
     private[core] val uniqueNamedTypes = new NamedTypeUniques
diff --git a/src/dotty/tools/dotc/core/Hashable.scala b/src/dotty/tools/dotc/core/Hashable.scala
index 2f55ef70a..fc3b7d0c7 100644
--- a/src/dotty/tools/dotc/core/Hashable.scala
+++ b/src/dotty/tools/dotc/core/Hashable.scala
@@ -35,8 +35,6 @@ trait Hashable {
 
   protected final def identityHash = avoidNotCached(System.identityHashCode(this))
 
-  protected final def avoidNotCached(h: Int) = if (h == NotCached) NotCachedAlt else h
-
   private def finishHash(seed: Int, arity: Int, tp: Type): Int = {
     val elemHash = tp.hash
     if (elemHash == NotCached) return NotCached
@@ -89,4 +87,8 @@ trait Hashable {
 
   protected final def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int =
     finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3)
+
+  protected final def addDelta(hc: Int, delta: Int) = avoidNotCached(hc + delta)
+
+  private def avoidNotCached(h: Int) = if (h == NotCached) NotCachedAlt else h
 }
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 4f740d2e5..63c26a6e7 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -961,8 +961,8 @@ object Types {
   /** A trait for proto-types, used as expected types in typer */
   trait ProtoType extends Type {
     def isMatchedBy(tp: Type)(implicit ctx: Context): Boolean
-    def fold[T](x: T, ta: TypeAccumulator[T]): T
-    def map(tm: TypeMap): ProtoType
+    def fold[T](x: T, ta: TypeAccumulator[T])(implicit ctx: Context): T
+    def map(tm: TypeMap)(implicit ctx: Context): ProtoType
   }
 
   /** Implementations of this trait cache the resukts of `narrow`. */
@@ -1491,7 +1491,7 @@ object Types {
     extends MethodType(paramNames, paramTypes)(resultTypeExp) {
     override def isJava = true
     override def equals(that: Any) = super.equals(that) && that.isInstanceOf[JavaMethodType]
-    override def computeHash = super.computeHash + 1
+    override def computeHash = addDelta(super.computeHash, 1)
     override protected def prefixString = "JavaMethodType"
   }
 
@@ -1499,7 +1499,7 @@ object Types {
     extends MethodType(paramNames, paramTypes)(resultTypeExp) {
     override def isImplicit = true
     override def equals(that: Any) = super.equals(that) && that.isInstanceOf[ImplicitMethodType]
-    override def computeHash = super.computeHash + 2
+    override def computeHash = addDelta(super.computeHash, 2)
     override protected def prefixString = "ImplicitMethodType"
   }
 
@@ -1612,7 +1612,7 @@ object Types {
     def copyBoundType(bt: BT) = MethodParam(bt, paramNum)
 
     // need to customize hashCode and equals to prevent infinite recursion for dep meth types.
-    override def computeHash = avoidNotCached(System.identityHashCode(binder) + paramNum)
+    override def computeHash = addDelta(System.identityHashCode(binder), paramNum)
     override def equals(that: Any) = that match {
       case that: MethodParam =>
         (this.binder eq that.binder) && this.paramNum == that.paramNum
@@ -2173,39 +2173,6 @@ object Types {
     def apply(tp: Type) = tp
   }
 
-  /** Approximate occurrences of parameter types and uninstantiated typevars
-   *  by wildcard types.
-   */
-  class WildApprox(implicit ctx: Context) extends TypeMap {
-    override def apply(tp: Type) = tp match {
-      case PolyParam(pt, pnum) =>
-        WildcardType(apply(pt.paramBounds(pnum)).bounds)
-      case MethodParam(mt, pnum) =>
-        WildcardType(TypeBounds.upper(apply(mt.paramTypes(pnum))))
-      case tp: TypeVar =>
-        val inst = tp.instanceOpt
-        apply(inst orElse WildcardType(ctx.typerState.constraint.bounds(tp.origin)))
-      case tp: AndType =>
-        val tp1a = apply(tp.tp1)
-        val tp2a = apply(tp.tp2)
-        def wildBounds(tp: Type) =
-          if (tp.isInstanceOf[WildcardType]) tp.bounds else TypeBounds.upper(tp)
-        if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType])
-          WildcardType(wildBounds(tp1a) & wildBounds(tp2a))
-        else
-          tp.derivedAndType(tp1a, tp2a)
-      case tp: OrType =>
-        val tp1a = apply(tp.tp1)
-        val tp2a = apply(tp.tp2)
-        if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType])
-          WildcardType(tp1a.bounds | tp2a.bounds)
-        else
-          tp.derivedOrType(tp1a, tp2a)
-      case _ =>
-        mapOver(tp)
-    }
-  }
-
   // ----- TypeAccumulators ----------------------------------------------------
 
   abstract class TypeAccumulator[T](implicit ctx: Context) extends ((T, Type) => T) {
diff --git a/src/dotty/tools/dotc/typer/Applications.scala b/src/dotty/tools/dotc/typer/Applications.scala
index f504ffacd..63117e2ac 100644
--- a/src/dotty/tools/dotc/typer/Applications.scala
+++ b/src/dotty/tools/dotc/typer/Applications.scala
@@ -449,7 +449,7 @@ trait Applications extends Compatibility { self: Typer =>
                 // implicit conversion around []. (an example is Int + BigInt).
                 tryEither { implicit ctx =>
                   val simpleFunProto = new FunProto(tree.args, WildcardType, this) // drop result type, because views are disabled
-                  val selProto = new SelectionProto(name, simpleFunProto, NoViewsAllowed)
+                  val selProto = SelectionProto(name, simpleFunProto, NoViewsAllowed)
                   val qual1 = adaptInterpolated(qual, selProto)
                   if (qual eq qual1) ctx.error("no progress")
                   if (ctx.reporter.hasErrors) qual1
diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala
index cc29ffe8a..e55bfb439 100644
--- a/src/dotty/tools/dotc/typer/Inferencing.scala
+++ b/src/dotty/tools/dotc/typer/Inferencing.scala
@@ -13,6 +13,7 @@ import util.Positions._
 import util.{Stats, SimpleMap}
 import util.common._
 import Decorators._
+import Uniques._
 import ErrorReporting.{errorType, InfoString}
 import config.Printers._
 import collection.mutable
@@ -72,7 +73,7 @@ object Inferencing {
    *
    *       [ ].name: proto
    */
-  class SelectionProto(val name: Name, proto: Type, compat: Compatibility)
+  abstract class SelectionProto(val name: Name, proto: Type, compat: Compatibility)
   extends RefinedType(WildcardType, name) with ProtoType {
     override val refinedInfo = proto
     override def isMatchedBy(tp1: Type)(implicit ctx: Context) =
@@ -86,22 +87,44 @@ object Inferencing {
       if (tp1 eq this) this
       else {
         assert(parent == WildcardType)
-        new SelectionProto(refinedName1, tp1.refinedInfo, compat)
+        SelectionProto(refinedName1, tp1.refinedInfo, compat)
       }
     }
-    def map(tm: TypeMap) = tm(this).asInstanceOf[SelectionProto]
-    def fold[T](x: T, ta: TypeAccumulator[T]) = ta(x, this)
+    def derivedSelectionProto(name: Name, proto: Type, compat: Compatibility)(implicit ctx: Context) =
+      if ((name eq this.name) && (proto eq this.proto) && (compat eq this.compat)) this
+      else SelectionProto(name, proto, compat)
+ /*
+    override def equals(that: Any): Boolean = that match {
+      case that: SelectionProto =>
+        (name eq that.name) && (refinedInfo eq that.refinedInfo) && (compat eq that.compat)
+    }
+
+*/
+    def map(tm: TypeMap)(implicit ctx: Context) = derivedSelectionProto(name, tm(proto), compat)
+    def fold[T](x: T, ta: TypeAccumulator[T])(implicit ctx: Context) = ta(x, this)
+  }
+
+  class CachedSelectionProto(name: Name, proto: Type, compat: Compatibility) extends SelectionProto(name, proto, compat) {
+    override def computeHash = addDelta(doHash(name, proto), if (compat == NoViewsAllowed) 1 else 0)
+  }
+
+  object SelectionProto {
+    def apply(name: Name, proto: Type, compat: Compatibility)(implicit ctx: Context): SelectionProto = {
+      val rt = new CachedSelectionProto(name, proto, compat)
+      if (compat eq NoViewsAllowed) ctx.uniqueRefinedTypes.enterIfNew(rt).asInstanceOf[SelectionProto]
+      else rt
+    }
   }
 
   /** Create a selection proto-type, but only one level deep;
    *  treat constructors specially
    */
-  def selectionProto(name: Name, tp: Type, typer: Typer) =
+  def selectionProto(name: Name, tp: Type, typer: Typer)(implicit ctx: Context) =
     if (name.isConstructorName) WildcardType
     else tp match {
       case tp: UnapplyFunProto => new UnapplySelectionProto(name)
-      case tp: ProtoType => new SelectionProto(name, WildcardType, typer)
-      case _ => new SelectionProto(name, tp, typer)
+      case tp: ProtoType => SelectionProto(name, WildcardType, typer)
+      case _ => SelectionProto(name, tp, typer)
     }
 
   /** A prototype for expressions [] that are in some unspecified selection operation
@@ -133,6 +156,10 @@ object Inferencing {
     def isMatchedBy(tp: Type)(implicit ctx: Context) =
       typer.isApplicable(tp, Nil, typedArgs, resultType)
 
+    def derivedFunProto(args: List[untpd.Tree], resultType: Type, typer: Typer) =
+      if ((args eq this.args) && (resultType eq this.resultType) && (typer eq this.typer)) this
+      else new FunProto(args, resultType, typer)
+
     def argsAreTyped: Boolean = myTypedArgs.nonEmpty || args.isEmpty
 
     /** The typed arguments. This takes any arguments already typed using
@@ -163,20 +190,17 @@ object Inferencing {
 
     override def toString = s"FunProto(${args mkString ","} => $resultType)"
 
-    def map(tm: TypeMap): FunProto = {
-      val resultType1 = tm(resultType)
-      if (resultType1 eq resultType) this
-      else FunProto(args, resultType1, typer)
-    }
+    def map(tm: TypeMap)(implicit ctx: Context): FunProto =
+      derivedFunProto(args, tm(resultType), typer)
 
-    def fold[T](x: T, ta: TypeAccumulator[T]): T = ta(x, resultType)
+    def fold[T](x: T, ta: TypeAccumulator[T])(implicit ctx: Context): T = ta(x, resultType)
   }
 
   /** A prototype for implicitly inferred views:
    *
    *    []: argType => resultType
    */
-  case class ViewProto(argType: Type, override val resultType: Type)(implicit ctx: Context)
+  abstract case class ViewProto(argType: Type, override val resultType: Type)(implicit ctx: Context)
   extends CachedGroundType with ApplyingProto {
  //   def lookingForInfo = resultType match {
  //     case rt: SelectionProto => rt.name.toString == "info"
@@ -186,20 +210,27 @@ object Inferencing {
       ctx.typer.isApplicable(tp, argType :: Nil, resultType)
     }
 
-    def map(tm: TypeMap): ViewProto = {
-      val argType1 = tm(argType)
-      val resultType1 = tm(resultType)
-      if ((argType1 eq argType) && (resultType1 eq resultType)) this
-      else ViewProto(argType1, resultType1)
-    }
+    def derivedViewProto(argType: Type, resultType: Type)(implicit ctx: Context) =
+      if ((argType eq this.argType) && (resultType eq this.resultType)) this
+      else ViewProto(argType, resultType)
+
+    def map(tm: TypeMap)(implicit ctx: Context): ViewProto = derivedViewProto(tm(argType), tm(resultType))
 
-    def fold[T](x: T, ta: TypeAccumulator[T]): T = ta(ta(x, argType), resultType)
+    def fold[T](x: T, ta: TypeAccumulator[T])(implicit ctx: Context): T = ta(ta(x, argType), resultType)
 
     override def namedPartsWith(p: NamedType => Boolean)(implicit ctx: Context): collection.Set[NamedType] =
       AndType.unchecked(argType, resultType).namedPartsWith(p) // this is more efficient than oring two namedParts sets
+  }
+
+  class CachedViewProto(argType: Type, resultType: Type)(implicit ctx: Context) extends ViewProto(argType, resultType) {
     override def computeHash = doHash(argType, resultType)
   }
 
+  object ViewProto {
+    def apply(argType: Type, resultType: Type)(implicit ctx: Context) =
+      unique(new CachedViewProto(argType, resultType))
+  }
+
   class UnapplyFunProto(typer: Typer)(implicit ctx: Context) extends FunProto(
       untpd.TypedSplice(dummyTreeOfType(WildcardType)) :: Nil, WildcardType, typer)
 
@@ -216,14 +247,14 @@ object Inferencing {
       isInstantiatable(tp) || tp.member(nme.apply).hasAltWith(d => isInstantiatable(d.info))
     }
 
-    def map(tm: TypeMap): PolyProto = {
-      val targs1 = targs mapConserve tm
-      val resultType1 = tm(resultType)
-      if ((targs1 eq targs) && (resultType1 eq resultType)) this
-      else PolyProto(targs1, resultType1)
-    }
+    def derivedPolyProto(targs: List[Type], resultType: Type) =
+      if ((targs eq this.targs) && (resultType eq this.resultType)) this
+      else PolyProto(targs, resultType)
+
+    def map(tm: TypeMap)(implicit ctx: Context): PolyProto =
+      derivedPolyProto(targs mapConserve tm, tm(resultType))
 
-    def fold[T](x: T, ta: TypeAccumulator[T]): T = ta((x /: targs)(ta), resultType)
+    def fold[T](x: T, ta: TypeAccumulator[T])(implicit ctx: Context): T = ta((x /: targs)(ta), resultType)
   }
 
   /** A prototype for expressions [] that are known to be functions:
@@ -232,8 +263,8 @@ object Inferencing {
    */
   object AnyFunctionProto extends UncachedGroundType with ProtoType {
     def isMatchedBy(tp: Type)(implicit ctx: Context) = true
-    def map(tm: TypeMap) = this
-    def fold[T](x: T, ta: TypeAccumulator[T]) = x
+    def map(tm: TypeMap)(implicit ctx: Context) = this
+    def fold[T](x: T, ta: TypeAccumulator[T])(implicit ctx: Context) = x
   }
 
   /** The normalized form of a type
@@ -256,7 +287,7 @@ object Inferencing {
       case mt: MethodType if !mt.isDependent /*&& !pt.isInstanceOf[ApplyingProto]*/ =>
         if (mt.isImplicit) mt.resultType
         else {
-          val rt = normalize(mt.resultType, pt)       
+          val rt = normalize(mt.resultType, pt)
           if (pt.isInstanceOf[ApplyingProto])
             mt.derivedMethodType(mt.paramNames, mt.paramTypes, rt)
           else {
@@ -470,6 +501,44 @@ object Inferencing {
     ??? // to be done in later phase: check that class `cls` is legal in a new.
   }
 
+  /** Approximate occurrences of parameter types and uninstantiated typevars
+   *  by wildcard types.
+   */
+  class WildApprox(implicit ctx: Context) extends TypeMap {
+    override def apply(tp: Type) = tp match {
+      case PolyParam(pt, pnum) =>
+        WildcardType(apply(pt.paramBounds(pnum)).bounds)
+      case MethodParam(mt, pnum) =>
+        WildcardType(TypeBounds.upper(apply(mt.paramTypes(pnum))))
+      case tp: TypeVar =>
+        val inst = tp.instanceOpt
+        apply(inst orElse WildcardType(ctx.typerState.constraint.bounds(tp.origin)))
+      case tp: AndType =>
+        val tp1a = apply(tp.tp1)
+        val tp2a = apply(tp.tp2)
+        def wildBounds(tp: Type) =
+          if (tp.isInstanceOf[WildcardType]) tp.bounds else TypeBounds.upper(tp)
+        if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType])
+          WildcardType(wildBounds(tp1a) & wildBounds(tp2a))
+        else
+          tp.derivedAndType(tp1a, tp2a)
+      case tp: OrType =>
+        val tp1a = apply(tp.tp1)
+        val tp2a = apply(tp.tp2)
+        if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType])
+          WildcardType(tp1a.bounds | tp2a.bounds)
+        else
+          tp.derivedOrType(tp1a, tp2a)
+      case tp: SelectionProto =>
+        tp.derivedSelectionProto(tp.name, this(tp.refinedInfo), NoViewsAllowed)
+      case tp: ViewProto =>
+        tp.derivedViewProto(this(tp.argType), this(tp.resultType))
+      case _ =>
+        mapOver(tp)
+    }
+  }
+
+
   /** Add all parameters in given polytype `pt` to the constraint's domain.
    *  If the constraint contains already some of these parameters in its domain,
    *  make a copy of the polytype and add the copy's type parameters instead.
diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala
index 92441d899..4dd400792 100644
--- a/src/dotty/tools/dotc/typer/Namer.scala
+++ b/src/dotty/tools/dotc/typer/Namer.scala
@@ -7,7 +7,7 @@ import ast._
 import Trees._, Constants._, StdNames._, Scopes._, Denotations._
 import Contexts._, Symbols._, Types._, SymDenotations._, Names._, NameOps._, Flags._, Decorators._
 import ast.desugar, ast.desugar._
-import Inferencing.{fullyDefinedType, AnySelectionProto, checkClassTypeWithStablePrefix, ensureFirstIsClass, forwardTypeParams}
+import Inferencing._
 import util.Positions._
 import util.SourcePosition
 import collection.mutable