Avoid name table pollution with fresh existentials

During large compilations runs, the large numbers of globally unique
fresh names for existentials captured from prefixes of `asSeenFrom`.
is a) somewhat wasteful (all these names are interned in the name table)
, and, b) form a pathological case for the current implementation of
`Names#hashValue`, which leads to overfull hash-buckets in the name table.

`hashValue` should probably be improved, but my attempts to do so have
shown a small performance degradation in some benchmarks. So this commit
starts by being more frugal with these names, only uniquely naming
within an `asSeenFrom` operation.

References scala/scala-dev#246

11 files changed, 30 insertions, 16 deletions

diff --git a/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala b/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala
index 4ae97ce281..cb3759e5fa 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala
@@ -682,7 +682,7 @@ trait ScalaLogic extends Interface with Logic with TreeAndTypeAnalysis {
       private[TreesAndTypesDomain] def uniqueTpForTree(t: Tree): Type = {
         def freshExistentialSubtype(tp: Type): Type = {
           // SI-8611 tp.narrow is tempting, but unsuitable. See `testRefinedTypeSI8611` for an explanation.
-          NoSymbol.freshExistential("").setInfo(TypeBounds.upper(tp)).tpe
+          NoSymbol.freshExistential("", 0).setInfo(TypeBounds.upper(tp)).tpe
         }
 
         if (!t.symbol.isStable) {
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternTypers.scala b/src/compiler/scala/tools/nsc/typechecker/PatternTypers.scala
index 1df3449ce6..cd0c292d90 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatternTypers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatternTypers.scala
@@ -123,7 +123,7 @@ trait PatternTypers {
     }
 
     private def boundedArrayType(bound: Type): Type = {
-      val tparam = context.owner freshExistential "" setInfo (TypeBounds upper bound)
+      val tparam = context.owner.freshExistential("", 0) setInfo (TypeBounds upper bound)
       newExistentialType(tparam :: Nil, arrayType(tparam.tpe_*))
     }
 
diff --git a/src/reflect/scala/reflect/internal/Symbols.scala b/src/reflect/scala/reflect/internal/Symbols.scala
index 8d77e334db..5cac9fb465 100644
--- a/src/reflect/scala/reflect/internal/Symbols.scala
+++ b/src/reflect/scala/reflect/internal/Symbols.scala
@@ -34,9 +34,13 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
   def recursionTable = _recursionTable
   def recursionTable_=(value: immutable.Map[Symbol, Int]) = _recursionTable = value
 
+  @deprecated("Global existential IDs no longer used", "2.12.1")
   private var existentialIds = 0
+  @deprecated("Global existential IDs no longer used", "2.12.1")
   protected def nextExistentialId() = { existentialIds += 1; existentialIds }
-  protected def freshExistentialName(suffix: String) = newTypeName("_" + nextExistentialId() + suffix)
+  @deprecated("Use overload that accepts an id", "2.12.1")
+  protected def freshExistentialName(suffix: String): TypeName = freshExistentialName(suffix, nextExistentialId())
+  protected def freshExistentialName(suffix: String, id: Int): TypeName = newTypeName("_" + id + suffix)
 
   // Set the fields which point companions at one another.  Returns the module.
   def connectModuleToClass(m: ModuleSymbol, moduleClass: ClassSymbol): ModuleSymbol = {
@@ -440,8 +444,11 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
     def newGADTSkolem(name: TypeName, origin: Symbol, info: Type): TypeSkolem =
       newTypeSkolemSymbol(name, origin, origin.pos, origin.flags & ~(EXISTENTIAL | PARAM) | GADT_SKOLEM_FLAGS) setInfo info
 
+    @deprecated("Use overload that accepts an id", "2.12.1")
     final def freshExistential(suffix: String): TypeSymbol =
       newExistential(freshExistentialName(suffix), pos)
+    final def freshExistential(suffix: String, id: Int): TypeSymbol =
+      newExistential(freshExistentialName(suffix, id), pos)
 
     /** Type skolems are type parameters ''seen from the inside''
      *  Assuming a polymorphic method m[T], its type is a PolyType which has a TypeParameter
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index f8679616d1..5e1bf37b80 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -4487,6 +4487,7 @@ trait Types
               debuglog(s"transposed irregular matrix!? tps=$tps argss=$argss")
               NoType
             case Some(argsst) =>
+              var capturedParamIds = 0
               val args = map2(sym.typeParams, argsst) { (tparam, as0) =>
                 val as = as0.distinct
                 if (as.size == 1) as.head
@@ -4508,8 +4509,10 @@ trait Types
                     else { // Martin: I removed this, because incomplete. Not sure there is a good way to fix it. For the moment we
                       // just err on the conservative side, i.e. with a bound that is too high.
                       // if(!(tparam.info.bounds contains tparam))   //@M can't deal with f-bounds, see #2251
+                      capturedParamIds += 1
+                      val capturedParamId = capturedParamIds
 
-                      val qvar = commonOwner(as) freshExistential "" setInfo TypeBounds(g, l)
+                      val qvar = commonOwner(as).freshExistential("", capturedParamId) setInfo TypeBounds(g, l)
                       capturedParams += qvar
                       qvar.tpe
                     }
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala
index ba4f2bec4b..08219c0634 100644
--- a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala
+++ b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala
@@ -512,6 +512,8 @@ private[internal] trait TypeMaps {
         && isBaseClassOfEnclosingClass(sym.owner)
       )
 
+    private var capturedThisIds= 0
+    private def nextCapturedThisId() = { capturedThisIds += 1; capturedThisIds }
     /** Creates an existential representing a type parameter which appears
       *  in the prefix of a ThisType.
       */
@@ -519,7 +521,7 @@ private[internal] trait TypeMaps {
       capturedParams find (_.owner == clazz) match {
         case Some(p) => p.tpe
         case _       =>
-          val qvar = clazz freshExistential nme.SINGLETON_SUFFIX setInfo singletonBounds(pre)
+          val qvar = clazz.freshExistential(nme.SINGLETON_SUFFIX, nextCapturedThisId()) setInfo singletonBounds(pre)
           _capturedParams ::= qvar
           debuglog(s"Captured This(${clazz.fullNameString}) seen from $seenFromPrefix: ${qvar.defString}")
           qvar.tpe
diff --git a/src/reflect/scala/reflect/runtime/SynchronizedSymbols.scala b/src/reflect/scala/reflect/runtime/SynchronizedSymbols.scala
index 237afa082b..4e7ddda54e 100644
--- a/src/reflect/scala/reflect/runtime/SynchronizedSymbols.scala
+++ b/src/reflect/scala/reflect/runtime/SynchronizedSymbols.scala
@@ -10,7 +10,9 @@ private[reflect] trait SynchronizedSymbols extends internal.Symbols { self: Symb
   private lazy val atomicIds = new java.util.concurrent.atomic.AtomicInteger(0)
   override protected def nextId() = atomicIds.incrementAndGet()
 
+  @deprecated("Global existential IDs no longer used", "2.12.1")
   private lazy val atomicExistentialIds = new java.util.concurrent.atomic.AtomicInteger(0)
+  @deprecated("Global existential IDs no longer used", "2.12.1")
   override protected def nextExistentialId() = atomicExistentialIds.incrementAndGet()
 
   private lazy val _recursionTable = mkThreadLocalStorage(immutable.Map.empty[Symbol, Int])
diff --git a/test/files/neg/sabin2.check b/test/files/neg/sabin2.check
index aa0e8f734c..cd6fde4608 100644
--- a/test/files/neg/sabin2.check
+++ b/test/files/neg/sabin2.check
@@ -1,6 +1,6 @@
 sabin2.scala:22: error: type mismatch;
  found   : Test.Base#T
- required: _5.T where val _5: Test.Base
+ required: _1.T where val _1: Test.Base
    a.set(b.get()) // Error
               ^
 one error found
diff --git a/test/files/neg/t0764.check b/test/files/neg/t0764.check
index 830278e715..0c7cff1e1e 100644
--- a/test/files/neg/t0764.check
+++ b/test/files/neg/t0764.check
@@ -1,5 +1,5 @@
 t0764.scala:13: error: type mismatch;
- found   : Node{type T = _2.type} where val _2: Node{type T = NextType}
+ found   : Node{type T = _1.type} where val _1: Node{type T = NextType}
  required: Node{type T = Main.this.AType}
     (which expands to)  Node{type T = Node{type T = NextType}}
         new Main[AType]( (value: AType).prepend )
diff --git a/test/files/neg/t1010.check b/test/files/neg/t1010.check
index 2cc8f9d986..d412d8ac1e 100644
--- a/test/files/neg/t1010.check
+++ b/test/files/neg/t1010.check
@@ -1,6 +1,6 @@
 t1010.scala:14: error: type mismatch;
  found   : MailBox#Message
- required: _3.in.Message where val _3: Actor
+ required: _1.in.Message where val _1: Actor
    unstable.send(msg) // in.Message becomes unstable.Message, but that's ok since Message is a concrete type member
                  ^
 one error found
diff --git a/test/files/neg/t5120.check b/test/files/neg/t5120.check
index 34d4ebde31..b6a3cb96aa 100644
--- a/test/files/neg/t5120.check
+++ b/test/files/neg/t5120.check
@@ -6,7 +6,7 @@ t5120.scala:11: error: type mismatch;
 t5120.scala:25: error: type mismatch;
  found   : Thread
  required: h.T
-    (which expands to)  _2
+    (which expands to)  _1
   List(str, num).foreach(h => h.f1 = new Thread())
                                      ^
 two errors found
diff --git a/test/files/neg/t6829.check b/test/files/neg/t6829.check
index 274094f791..5ccd531be1 100644
--- a/test/files/neg/t6829.check
+++ b/test/files/neg/t6829.check
@@ -1,6 +1,6 @@
 t6829.scala:35: error: type mismatch;
  found   : AgentSimulation.this.state.type (with underlying type G#State)
- required: _9.State
+ required: _1.State
     lazy val actions: Map[G#Agent,G#Action] = agents.map(a => a -> a.chooseAction(state)).toMap
                                                                                   ^
 t6829.scala:45: error: trait AgentSimulation takes type parameters
@@ -17,32 +17,32 @@ t6829.scala:49: error: not found: value nextState
                                              ^
 t6829.scala:50: error: type mismatch;
  found   : s.type (with underlying type Any)
- required: _30.State where val _30: G
+ required: _1.State where val _1: G
         val r = rewards(agent).r(s,a,s2)
                                  ^
 t6829.scala:50: error: type mismatch;
  found   : a.type (with underlying type Any)
- required: _30.Action where val _30: G
+ required: _1.Action where val _1: G
         val r = rewards(agent).r(s,a,s2)
                                    ^
 t6829.scala:50: error: type mismatch;
  found   : s2.type (with underlying type Any)
- required: _30.State where val _30: G
+ required: _1.State where val _1: G
         val r = rewards(agent).r(s,a,s2)
                                      ^
 t6829.scala:51: error: type mismatch;
  found   : s.type (with underlying type Any)
- required: _25.State
+ required: _1.State
         agent.learn(s,a,s2,r): G#Agent
                     ^
 t6829.scala:51: error: type mismatch;
  found   : a.type (with underlying type Any)
- required: _25.Action
+ required: _1.Action
         agent.learn(s,a,s2,r): G#Agent
                       ^
 t6829.scala:51: error: type mismatch;
  found   : s2.type (with underlying type Any)
- required: _25.State
+ required: _1.State
         agent.learn(s,a,s2,r): G#Agent
                         ^
 t6829.scala:53: error: not found: value nextState