Optimization in asSeenFrom.

Eliminated about half the allocations of AsSeenFromMap by examining the
arguments more closely. The impact is not what one might conclude from
that statistic, because those were the cheap asSeenFrom calls - but now
they are cheaper. Also,

 - worked in some eager vals rather than lazy ones.
 - changed hot-spot comparison to use eq
 - simplified annotationArgRewriter
 - elimnated separate tracking of capturedPre

Statistics from compiling scala/collection/**.scala:

  - 4209382 calls to asSeenFrom
  - 1025945 maps created (instantiations of AsSeenFromMap)
  - 1525649 maps avoided (these were instantiations before this patch)

Review by most honorable performance-san @gkossakowski .

(Rebase of https://github.com/scala/scala/pull/835)

1 files changed, 58 insertions, 51 deletions

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index 0b3e125053..246e32a147 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -695,17 +695,25 @@ trait Types extends api.Types { self: SymbolTable =>
     def asSeenFrom(pre: Type, clazz: Symbol): Type = {
       if (isTrivial || phase.erasedTypes && pre.typeSymbol != ArrayClass) this
       else {
-//        scala.tools.nsc.util.trace.when(pre.isInstanceOf[ExistentialType])("X "+this+".asSeenfrom("+pre+","+clazz+" = ") {
+        // scala.tools.nsc.util.trace.when(pre.isInstanceOf[ExistentialType])("X "+this+".asSeenfrom("+pre+","+clazz+" = ")
         Statistics.incCounter(asSeenFromCount)
         val start = Statistics.pushTimer(typeOpsStack, asSeenFromNanos)
-        val m = new AsSeenFromMap(pre.normalize, clazz)
-        val tp = m apply this
-        val tp1 = existentialAbstraction(m.capturedParams, tp)
-        val result: Type =
-          if (m.capturedSkolems.isEmpty) tp1
-          else deriveType(m.capturedSkolems, _.cloneSymbol setFlag CAPTURED)(tp1)
+        val pre1 = pre.normalize
 
+        val result: Type = (
+          if (pre1.isTrivial && (clazz.isPackageClass || !clazz.isClass)) this
+          else {
+            val m = new AsSeenFromMap(pre1, clazz)
+            val tp = m apply this
+            val tp1 = existentialAbstraction(m.capturedParams, tp)
+            if (m.capturedSkolems.isEmpty) tp1
+            else deriveType(m.capturedSkolems, _.cloneSymbol setFlag CAPTURED)(tp1)
+          }
+        )
         Statistics.popTimer(typeOpsStack, start)
+        if ((result ne this) && pre1.isTrivial)
+          debuglog(s"asSeenFrom($pre1, $clazz)\n  old: ${this}\n  new: $result")
+
         result
       }
     }
@@ -1289,7 +1297,7 @@ trait Types extends api.Types { self: SymbolTable =>
   /** A class for this-types of the form <sym>.this.type
    */
   abstract case class ThisType(sym: Symbol) extends SingletonType with ThisTypeApi {
-    assert(sym.isClass)
+    assert(sym.isClass, sym)
     //assert(sym.isClass && !sym.isModuleClass || sym.isRoot, sym)
     override def isTrivial: Boolean = sym.isPackageClass
     override def isNotNull = true
@@ -2207,6 +2215,8 @@ trait Types extends api.Types { self: SymbolTable =>
    * @M: a higher-kinded type is represented as a TypeRef with sym.typeParams.nonEmpty, but args.isEmpty
    */
   abstract case class TypeRef(pre: Type, sym: Symbol, args: List[Type]) extends Type with TypeRefApi {
+    override val isTrivial: Boolean = !sym.isTypeParameter && pre.isTrivial && args.forall(_.isTrivial)
+
     private[reflect] var parentsCache: List[Type]      = _
     private[reflect] var parentsPeriod                 = NoPeriod
     private[reflect] var baseTypeSeqCache: BaseTypeSeq = _
@@ -2269,9 +2279,6 @@ trait Types extends api.Types { self: SymbolTable =>
     override def typeSymbol       = sym
     override def typeSymbolDirect = sym
 
-    override lazy val isTrivial: Boolean =
-      !sym.isTypeParameter && pre.isTrivial && args.forall(_.isTrivial)
-
     override def isNotNull =
       sym.isModuleClass || sym == NothingClass || (sym isNonBottomSubClass NotNullClass) || super.isNotNull
 
@@ -2435,11 +2442,15 @@ trait Types extends api.Types { self: SymbolTable =>
    */
   case class MethodType(override val params: List[Symbol],
                         override val resultType: Type) extends Type with MethodTypeApi {
-    override def isTrivial: Boolean = isTrivial0 && (resultType eq resultType.withoutAnnotations)
-    private lazy val isTrivial0 =
-      resultType.isTrivial && params.forall{p => p.tpe.isTrivial &&  (
-        !(params.exists(_.tpe.contains(p)) || resultType.contains(p)))
-      }
+
+    override lazy val isTrivial: Boolean =
+      isTrivialResult && (params forall isTrivialParam)
+
+    private def isTrivialResult =
+      resultType.isTrivial && (resultType eq resultType.withoutAnnotations)
+
+    private def isTrivialParam(p: Symbol) =
+      p.tpe.isTrivial && !(params.exists(_.tpe contains p) || (resultType contains p))
 
     def isImplicit = params.nonEmpty && params.head.isImplicit
     def isJava = false // can we do something like for implicits? I.e. do Java methods without parameters need to be recognized?
@@ -3211,8 +3222,7 @@ trait Types extends api.Types { self: SymbolTable =>
 
     override protected def rewrap(tp: Type) = copy(underlying = tp)
 
-    override def isTrivial: Boolean = isTrivial0
-    private lazy val isTrivial0 = underlying.isTrivial && annotations.forall(_.isTrivial)
+    override def isTrivial: Boolean = underlying.isTrivial && annotations.forall(_.isTrivial)
 
     override def safeToString = annotations.mkString(underlying + " @", " @", "")
 
@@ -4259,51 +4269,48 @@ trait Types extends api.Types { self: SymbolTable =>
   class AsSeenFromMap(pre: Type, clazz: Symbol) extends TypeMap with KeepOnlyTypeConstraints {
     var capturedSkolems: List[Symbol] = List()
     var capturedParams: List[Symbol] = List()
-    var capturedPre = emptySymMap
+
+    @inline private def skipPrefixOf(pre: Type, clazz: Symbol) = (
+      (pre eq NoType) || (pre eq NoPrefix) || !clazz.isClass
+    )
 
     override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
       object annotationArgRewriter extends TypeMapTransformer {
+        private def canRewriteThis(sym: Symbol) = (
+             (sym isNonBottomSubClass clazz)
+          && (pre.widen.typeSymbol isNonBottomSubClass sym)
+          && (pre.isStable || giveup())
+        )
+        // what symbol should really be used?
+        private def newTermSym() = {
+          val p = pre.typeSymbol
+          p.owner.newValue(p.name.toTermName, p.pos) setInfo pre
+        }
         /** Rewrite `This` trees in annotation argument trees */
-        def rewriteThis(tree: Tree): Tree =
-          tree match {
-            case This(_)
-            if (tree.symbol isNonBottomSubClass clazz) &&
-               (pre.widen.typeSymbol isNonBottomSubClass tree.symbol) =>
-              if (pre.isStable) { // XXX why is this in this method? pull it out and guard the call `annotationArgRewriter.transform(tree)`?
-                val termSym = (
-                  pre.typeSymbol.owner.newValue(pre.typeSymbol.name.toTermName, pre.typeSymbol.pos) // what symbol should really be used?
-                    setInfo pre
-                )
-                gen.mkAttributedQualifier(pre, termSym)
-              } else
-                giveup()
-
-            case tree => tree
-          }
-
-        override def transform(tree: Tree): Tree = {
-          val tree1 = rewriteThis(super.transform(tree))
-          tree1
+        override def transform(tree: Tree): Tree = super.transform(tree) match {
+          case This(_) if canRewriteThis(tree.symbol) => gen.mkAttributedQualifier(pre, newTermSym())
+          case tree                                   => tree
         }
       }
-
       annotationArgRewriter.transform(tree)
     }
 
-    def stabilize(pre: Type, clazz: Symbol): Type =
-      capturedPre.getOrElse(clazz, {
-          val qvar = clazz freshExistential ".type" setInfo singletonBounds(pre)
-          capturedPre += (clazz -> qvar)
-          capturedParams = qvar :: capturedParams
-          qvar
-      }).tpe
+    def stabilize(pre: Type, clazz: Symbol): Type = {
+      capturedParams find (_.owner == clazz) match {
+        case Some(qvar) => qvar.tpe
+        case _          =>
+          val qvar = clazz freshExistential nme.SINGLETON_SUFFIX setInfo singletonBounds(pre)
+          capturedParams ::= qvar
+          qvar.tpe
+      }
+    }
 
     def apply(tp: Type): Type =
-      if ((pre eq NoType) || (pre eq NoPrefix) || !clazz.isClass) tp
+      if (skipPrefixOf(pre, clazz)) tp
       else tp match {
         case ThisType(sym) =>
           def toPrefix(pre: Type, clazz: Symbol): Type =
-            if ((pre eq NoType) || (pre eq NoPrefix) || !clazz.isClass) tp
+            if (skipPrefixOf(pre, clazz)) tp
             else if ((sym isNonBottomSubClass clazz) &&
                      (pre.widen.typeSymbol isNonBottomSubClass sym)) {
               val pre1 = pre match {
@@ -4339,7 +4346,7 @@ trait Types extends api.Types { self: SymbolTable =>
         // (skolems also aren't affected: they are ruled out by the isTypeParameter check)
         case TypeRef(prefix, sym, args) if (sym.isTypeParameter && sym.owner.isClass) =>
           def toInstance(pre: Type, clazz: Symbol): Type =
-            if ((pre eq NoType) || (pre eq NoPrefix) || !clazz.isClass) mapOver(tp)
+            if (skipPrefixOf(pre, clazz)) mapOver(tp)
             //@M! see test pos/tcpoly_return_overriding.scala why mapOver is necessary
             else {
               def throwError = abort("" + tp + sym.locationString + " cannot be instantiated from " + pre.widen)
@@ -4609,7 +4616,7 @@ trait Types extends api.Types { self: SymbolTable =>
       if (existentials(pid) eq null) {
         val param = params(pid)
         existentials(pid) = (
-          param.owner.newExistential(newTypeName(param.name + ".type"), param.pos, param.flags)
+          param.owner.newExistential(param.name.toTypeName append nme.SINGLETON_SUFFIX, param.pos, param.flags)
             setInfo singletonBounds(actuals(pid))
         )
       }