Hunting down eliminable :: allocations.

With this commit, the number of :: allocations logged in total
after individually compiling each scala file in src/compiler
drops from 190,766,642 to 170,679,925.  Twenty million fewer
colon-colons in the world, it's a start.

For some heavily used lists like List(List()) I made vals so
we can reuse the same one every time, e.g.

  val ListOfNil = List(Nil)

The modifications in this patch were informed by logging call
frequency to List.apply and examining the heaviest users.

>> Origins tag 'listApply' logged 3041128 calls from 318 distinguished sources.

1497759   scala.reflect.internal.Definitions$ValueClassDefinitions$class.ScalaValueClasses(Definitions.scala:149)
 173737   scala.reflect.internal.Symbols$Symbol.alternatives(Symbols.scala:1525)
 148642   scala.tools.nsc.typechecker.SuperAccessors$SuperAccTransformer.transform(SuperAccessors.scala:306)
 141676   scala.tools.nsc.transform.SpecializeTypes$$anonfun$scala$tools$nsc$transform$SpecializeTypes$$specializedOn$3.apply(SpecializeTypes.scala:114)
  69049   scala.tools.nsc.transform.LazyVals$LazyValues$$anonfun$1.apply(LazyVals.scala:79)
  62854   scala.tools.nsc.transform.SpecializeTypes.specializedTypeVars(SpecializeTypes.scala:427)
  54781   scala.tools.nsc.typechecker.SuperAccessors$SuperAccTransformer.transform(SuperAccessors.scala:293)
  54486   scala.reflect.internal.Symbols$Symbol.newSyntheticValueParams(Symbols.scala:334)
  53843   scala.tools.nsc.backend.icode.Opcodes$opcodes$CZJUMP.<init>(Opcodes.scala:562)
  ...     etc.

7 files changed, 41 insertions, 35 deletions

diff --git a/src/reflect/scala/reflect/internal/Definitions.scala b/src/reflect/scala/reflect/internal/Definitions.scala
index fcbe7d0ed9..7fa098a328 100644
--- a/src/reflect/scala/reflect/internal/Definitions.scala
+++ b/src/reflect/scala/reflect/internal/Definitions.scala
@@ -137,9 +137,8 @@ trait Definitions extends api.StandardDefinitions {
     lazy val BooleanTpe = BooleanClass.toTypeConstructor
 
     lazy val ScalaNumericValueClasses = ScalaValueClasses filterNot Set[Symbol](UnitClass, BooleanClass)
-
-    def ScalaValueClassesNoUnit = ScalaValueClasses filterNot (_ eq UnitClass)
-    def ScalaValueClasses: List[ClassSymbol] = List(
+    lazy val ScalaValueClassesNoUnit  = ScalaValueClasses filterNot (_ eq UnitClass)
+    lazy val ScalaValueClasses: List[ClassSymbol] = List(
       UnitClass,
       BooleanClass,
       ByteClass,
diff --git a/src/reflect/scala/reflect/internal/Symbols.scala b/src/reflect/scala/reflect/internal/Symbols.scala
index d52afed28a..5da4942a89 100644
--- a/src/reflect/scala/reflect/internal/Symbols.scala
+++ b/src/reflect/scala/reflect/internal/Symbols.scala
@@ -294,14 +294,31 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
     final def newExistential(name: TypeName, pos: Position = NoPosition, newFlags: Long = 0L): TypeSymbol =
       newAbstractType(name, pos, EXISTENTIAL | newFlags)
 
-    /** Synthetic value parameters when parameter symbols are not available
-     */
-    final def newSyntheticValueParamss(argtypess: List[List[Type]]): List[List[TermSymbol]] = {
+    private def freshNamer: () => TermName = {
       var cnt = 0
-      def freshName() = { cnt += 1; nme.syntheticParamName(cnt) }
-      mmap(argtypess)(tp => newValueParameter(freshName(), owner.pos.focus, SYNTHETIC) setInfo tp)
+      () => { cnt += 1; nme.syntheticParamName(cnt) }
     }
 
+    /** Synthetic value parameters when parameter symbols are not available
+     */
+    final def newSyntheticValueParamss(argtypess: List[List[Type]]): List[List[TermSymbol]] =
+      argtypess map (xs => newSyntheticValueParams(xs, freshNamer))
+
+    /** Synthetic value parameters when parameter symbols are not available.
+     *  Calling this method multiple times will re-use the same parameter names.
+     */
+    final def newSyntheticValueParams(argtypes: List[Type]): List[TermSymbol] =
+      newSyntheticValueParams(argtypes, freshNamer)
+
+    final def newSyntheticValueParams(argtypes: List[Type], freshName: () => TermName): List[TermSymbol] =
+      argtypes map (tp => newSyntheticValueParam(tp, freshName()))
+
+    /** Synthetic value parameter when parameter symbol is not available.
+     *  Calling this method multiple times will re-use the same parameter name.
+     */
+    final def newSyntheticValueParam(argtype: Type, name: TermName = nme.syntheticParamName(1)): TermSymbol =
+      newValueParameter(name, owner.pos.focus, SYNTHETIC) setInfo argtype
+
     def newSyntheticTypeParam(): TypeSymbol                             = newSyntheticTypeParam("T0", 0L)
     def newSyntheticTypeParam(name: String, newFlags: Long): TypeSymbol = newTypeParameter(newTypeName(name), NoPosition, newFlags) setInfo TypeBounds.empty
     def newSyntheticTypeParams(num: Int): List[TypeSymbol]              = (0 until num).toList map (n => newSyntheticTypeParam("T" + n, 0L))
@@ -328,18 +345,6 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
     final def freshExistential(suffix: String): TypeSymbol =
       newExistential(freshExistentialName(suffix), pos)
 
-    /** Synthetic value parameters when parameter symbols are not available.
-     *  Calling this method multiple times will re-use the same parameter names.
-     */
-    final def newSyntheticValueParams(argtypes: List[Type]): List[TermSymbol] =
-      newSyntheticValueParamss(List(argtypes)).head
-
-    /** Synthetic value parameter when parameter symbol is not available.
-     *  Calling this method multiple times will re-use the same parameter name.
-     */
-    final def newSyntheticValueParam(argtype: Type): Symbol =
-      newSyntheticValueParams(List(argtype)).head
-
     /** Type skolems are type parameters ''seen from the inside''
      *  Assuming a polymorphic method m[T], its type is a PolyType which has a TypeParameter
      *  with name `T` in its typeParams list. While type checking the parameters, result type and
@@ -1522,7 +1527,7 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
 
     def alternatives: List[Symbol] =
       if (isOverloaded) info.asInstanceOf[OverloadedType].alternatives
-      else List(this)
+      else this :: Nil
 
     def filter(cond: Symbol => Boolean): Symbol =
       if (isOverloaded) {
@@ -1626,7 +1631,7 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
       (info.decls filter (_.isCaseAccessorMethod)).toList
 
     final def constrParamAccessors: List[Symbol] =
-      info.decls.toList filter (sym => !sym.isMethod && sym.isParamAccessor)
+      info.decls.filter(sym => !sym.isMethod && sym.isParamAccessor).toList
 
     /** The symbol accessed by this accessor (getter or setter) function. */
     final def accessed: Symbol = accessed(owner.info)
diff --git a/src/reflect/scala/reflect/internal/TreeGen.scala b/src/reflect/scala/reflect/internal/TreeGen.scala
index d160695e67..f953e9b757 100644
--- a/src/reflect/scala/reflect/internal/TreeGen.scala
+++ b/src/reflect/scala/reflect/internal/TreeGen.scala
@@ -194,7 +194,7 @@ abstract class TreeGen extends macros.TreeBuilder {
     mkTypeApply(mkAttributedSelect(target, method), targs map TypeTree)
 
   private def mkSingleTypeApply(value: Tree, tpe: Type, what: Symbol, wrapInApply: Boolean) = {
-    val tapp = mkAttributedTypeApply(value, what, List(tpe.normalize))
+    val tapp = mkAttributedTypeApply(value, what, tpe.normalize :: Nil)
     if (wrapInApply) Apply(tapp, Nil) else tapp
   }
   private def typeTestSymbol(any: Boolean) = if (any) Any_isInstanceOf else Object_isInstanceOf
diff --git a/src/reflect/scala/reflect/internal/TreeInfo.scala b/src/reflect/scala/reflect/internal/TreeInfo.scala
index 19f264f60e..5e3f0c2aee 100644
--- a/src/reflect/scala/reflect/internal/TreeInfo.scala
+++ b/src/reflect/scala/reflect/internal/TreeInfo.scala
@@ -521,20 +521,18 @@ abstract class TreeInfo {
    */
   def noPredefImportForUnit(body: Tree) = {
     // Top-level definition whose leading imports include Predef.
-    def containsLeadingPredefImport(defs: List[Tree]): Boolean = defs match {
-      case PackageDef(_, defs1) :: _ => containsLeadingPredefImport(defs1)
-      case Import(expr, _) :: rest   => isReferenceToPredef(expr) || containsLeadingPredefImport(rest)
-      case _                         => false
+    def isLeadingPredefImport(defn: Tree): Boolean = defn match {
+      case PackageDef(_, defs1) => defs1 exists isLeadingPredefImport
+      case Import(expr, _)      => isReferenceToPredef(expr)
+      case _                    => false
     }
-
     // Compilation unit is class or object 'name' in package 'scala'
     def isUnitInScala(tree: Tree, name: Name) = tree match {
       case PackageDef(Ident(nme.scala_), defs) => firstDefinesClassOrObject(defs, name)
       case _                                   => false
     }
 
-    (  isUnitInScala(body, nme.Predef)
-    || containsLeadingPredefImport(List(body)))
+    isUnitInScala(body, nme.Predef) || isLeadingPredefImport(body)
   }
 
   def isAbsTypeDef(tree: Tree) = tree match {
diff --git a/src/reflect/scala/reflect/internal/Trees.scala b/src/reflect/scala/reflect/internal/Trees.scala
index 3894870252..b21a28eea8 100644
--- a/src/reflect/scala/reflect/internal/Trees.scala
+++ b/src/reflect/scala/reflect/internal/Trees.scala
@@ -230,6 +230,7 @@ trait Trees extends api.Trees { self: SymbolTable =>
   }
 
   case object EmptyTree extends TermTree {
+    val asList = List(this)
     super.tpe_=(NoType)
     override def tpe_=(t: Type) =
       if (t != NoType) throw new UnsupportedOperationException("tpe_=("+t+") inapplicable for <empty>")
@@ -290,7 +291,10 @@ trait Trees extends api.Trees { self: SymbolTable =>
   object LabelDef extends LabelDefExtractor
 
   case class ImportSelector(name: Name, namePos: Int, rename: Name, renamePos: Int) extends ImportSelectorApi
-  object ImportSelector extends ImportSelectorExtractor
+  object ImportSelector extends ImportSelectorExtractor {
+    val wild     = ImportSelector(nme.WILDCARD, -1, null, -1)
+    val wildList = List(wild)
+  }
 
   case class Import(expr: Tree, selectors: List[ImportSelector])
        extends SymTree with ImportApi
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index 56506246ca..657b6b0517 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -442,7 +442,7 @@ trait Types extends api.Types { self: SymbolTable =>
       if (phase.erasedTypes) this
       else {
         val cowner = commonOwner(this)
-        refinedType(List(this), cowner, EmptyScope, cowner.pos).narrow
+        refinedType(this :: Nil, cowner, EmptyScope, cowner.pos).narrow
       }
 
     /** For a TypeBounds type, itself;
@@ -1007,7 +1007,7 @@ trait Types extends api.Types { self: SymbolTable =>
         if (!e.sym.hasFlag(excludedFlags)) {
           if (sym == NoSymbol) sym = e.sym
           else {
-            if (alts.isEmpty) alts = List(sym)
+            if (alts.isEmpty) alts = sym :: Nil
             alts = e.sym :: alts
           }
         }
diff --git a/src/reflect/scala/reflect/internal/util/Collections.scala b/src/reflect/scala/reflect/internal/util/Collections.scala
index 2ac0e64edd..14b5d3003d 100644
--- a/src/reflect/scala/reflect/internal/util/Collections.scala
+++ b/src/reflect/scala/reflect/internal/util/Collections.scala
@@ -69,7 +69,7 @@ trait Collections {
     }
     lb.toList
   }
-  
+
   final def flatCollect[A, B](elems: List[A])(pf: PartialFunction[A, Traversable[B]]): List[B] = {
     val lb = new ListBuffer[B]
     for (x <- elems ; if pf isDefinedAt x)
@@ -104,7 +104,7 @@ trait Collections {
       index += 1
     }
   }
-  
+
   // @inline
   final def findOrElse[A](xs: TraversableOnce[A])(p: A => Boolean)(orElse: => A): A = {
     xs find p getOrElse orElse