Eliminate allocations in Types.

At this commit the statistics when compiling src/library
are as follows. These counts are precise, collected by a
modified Function1 which counts every instantiation of every
implementing class. The net result is 27 million fewer
allocations, over a 20% drop.

  // master (5b5635ee9d), total and top five by count:
  Total Function1 allocations: 128,805,865

  scala.collection.immutable.$colon$colon 26781958
  scala.collection.mutable.ListBuffer 15365174
  scala.collection.TraversableLike$$anonfun$map$1 9127787
  scala.collection.generic.Growable$$anonfun$$plus$plus$eq$1 4636154
  scala.collection.mutable.StringBuilder 3531211

  // After these commits, total and top five by count:
  Total Function1 allocations: 101,865,721

  scala.collection.immutable.$colon$colon 26993704
  scala.collection.mutable.ListBuffer 15319656
  scala.collection.TraversableLike$$anonfun$map$1 7585019
  scala.reflect.internal.Types$MethodType$$anonfun$paramTypes$1 2447307
  scala.reflect.internal.Types$SubstSymMap 2436088

1 files changed, 41 insertions, 35 deletions

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index b706ef8abe..c82904ae67 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -5023,42 +5023,9 @@ trait Types extends api.Types { self: SymbolTable =>
     else if (bd <= 7) td max (bd - 2)
     else (td - 1) max (bd - 3)
 
-  /** The maximum depth of type `tp` */
-  def typeDepth(tp: Type): Int = tp match {
-    case TypeRef(pre, sym, args) =>
-      math.max(typeDepth(pre), typeDepth(args) + 1)
-    case RefinedType(parents, decls) =>
-      math.max(typeDepth(parents), symTypeDepth(decls.toList) + 1)
-    case TypeBounds(lo, hi) =>
-      math.max(typeDepth(lo), typeDepth(hi))
-    case MethodType(paramtypes, result) =>
-      typeDepth(result)
-    case NullaryMethodType(result) =>
-      typeDepth(result)
-    case PolyType(tparams, result) =>
-      math.max(typeDepth(result), symTypeDepth(tparams) + 1)
-    case ExistentialType(tparams, result) =>
-      math.max(typeDepth(result), symTypeDepth(tparams) + 1)
-    case _ =>
-      1
-  }
-
-  private def maxDepth(tps: List[Type], by: Type => Int): Int = {
-    //OPT replaced with tailrecursive function to save on #closures
-    // was:
-    //    var d = 0
-    //    for (tp <- tps) d = d max by(tp) //!!!OPT!!!
-    //    d
-    def loop(tps: List[Type], acc: Int): Int = tps match {
-      case tp :: rest => loop(rest, math.max(acc, by(tp)))
-      case _          => acc
-    }
-    loop(tps, 0)
-  }
-
   private def symTypeDepth(syms: List[Symbol]): Int  = typeDepth(syms map (_.info))
-  private def typeDepth(tps: List[Type]): Int        = maxDepth(tps, typeDepth)
-  private def baseTypeSeqDepth(tps: List[Type]): Int = maxDepth(tps, _.baseTypeSeqDepth)
+  private def typeDepth(tps: List[Type]): Int        = maxDepth(tps)
+  private def baseTypeSeqDepth(tps: List[Type]): Int = maxBaseTypeSeqDepth(tps)
 
   /** Is intersection of given types populated? That is,
    *  for all types tp1, tp2 in intersection
@@ -7006,6 +6973,45 @@ trait Types extends api.Types { self: SymbolTable =>
   private[scala] val typeIsAny = (tp: Type) => tp.typeSymbolDirect eq AnyClass
   private[scala] val typeIsHigherKinded = (tp: Type) => tp.isHigherKinded
 
+  /** The maximum depth of type `tp` */
+  def typeDepth(tp: Type): Int = tp match {
+    case TypeRef(pre, sym, args) =>
+      math.max(typeDepth(pre), typeDepth(args) + 1)
+    case RefinedType(parents, decls) =>
+      math.max(typeDepth(parents), symTypeDepth(decls.toList) + 1)
+    case TypeBounds(lo, hi) =>
+      math.max(typeDepth(lo), typeDepth(hi))
+    case MethodType(paramtypes, result) =>
+      typeDepth(result)
+    case NullaryMethodType(result) =>
+      typeDepth(result)
+    case PolyType(tparams, result) =>
+      math.max(typeDepth(result), symTypeDepth(tparams) + 1)
+    case ExistentialType(tparams, result) =>
+      math.max(typeDepth(result), symTypeDepth(tparams) + 1)
+    case _ =>
+      1
+  }
+  //OPT replaced with tailrecursive function to save on #closures
+  // was:
+  //    var d = 0
+  //    for (tp <- tps) d = d max by(tp) //!!!OPT!!!
+  //    d
+  private[scala] def maxDepth(tps: List[Type]): Int = {
+    @tailrec def loop(tps: List[Type], acc: Int): Int = tps match {
+      case tp :: rest => loop(rest, math.max(acc, typeDepth(tp)))
+      case _          => acc
+    }
+    loop(tps, 0)
+  }
+  private[scala] def maxBaseTypeSeqDepth(tps: List[Type]): Int = {
+    @tailrec def loop(tps: List[Type], acc: Int): Int = tps match {
+      case tp :: rest => loop(rest, math.max(acc, tp.baseTypeSeqDepth))
+      case _          => acc
+    }
+    loop(tps, 0)
+  }
+
   @tailrec private def typesContain(tps: List[Type], sym: Symbol): Boolean = tps match {
     case tp :: rest => (tp contains sym) || typesContain(rest, sym)
     case _ => false