Made TempTrees array-backed.

This is a first step towards going from List[Tree] to an array-backed solution with special cases for small numbers.

3 files changed, 97 insertions, 25 deletions

diff --git a/src/dotty/tools/dotc/ast/Trees.scala b/src/dotty/tools/dotc/ast/Trees.scala
index fc95b4ea0..f84d32712 100644
--- a/src/dotty/tools/dotc/ast/Trees.scala
+++ b/src/dotty/tools/dotc/ast/Trees.scala
@@ -6,8 +6,10 @@ import Types._, Names._, Flags._, util.Positions._, Contexts._, Constants._, Sym
 import Denotations._, StdNames._
 import annotation.tailrec
 import language.higherKinds
+import collection.IndexedSeqOptimized
+import collection.immutable.IndexedSeq
 import collection.mutable
-import collection.mutable.ArrayBuffer
+import collection.mutable.Builder
 import parsing.Tokens.Token
 import printing.Printer
 import util.Stats
@@ -639,28 +641,98 @@ object Trees {
    *  The contained trees will be integrated when transformed with
    *  a `transform(List[Tree])` call.
    */
-  case class TempTrees[T >: Untyped](trees: List[Tree[T]]) extends Tree[T] {
+  case class TempTrees[T >: Untyped](trees: Array[Tree[T]])
+    extends Tree[T] with IndexedSeq[Tree[T]] with IndexedSeqOptimized[Tree[T], TempTrees[T]] {
+
     type ThisTree[T >: Untyped] = TempTrees[T]
     override def tpe: T = unsupported("tpe")
-  }
 
-  // ----- Auxiliary creation methods ------------------
+    def apply(i: Int): Tree[T] = trees(i)
+    def length: Int = trees.length
+    override def isEmpty: Boolean = trees.isEmpty
+    override def newBuilder: Builder[Tree[T], TempTrees[T]] = new TreesBuilder
+
+    private def flattenArray(trees: Array[Tree[T]], nestedDelta: Int): Array[Tree[T]] = {
+      val flatTrees = new Array[Tree[T]](trees.length + nestedDelta)
+      var i = 0
+      var j = 0
+      while (i < trees.length) {
+        val x = trees(i)
+        i += 1
+        x match {
+          case TempTrees(ys) =>
+            ys.copyToArray(flatTrees, j, ys.length)
+            j += ys.length
+          case _ =>
+            flatTrees(j) = x
+            j += 1
+        }
+      }
+      flatTrees
+    }
 
-  /** Integrates nested TempTrees in given list of trees */
-  def flatten[T >: Untyped](trees: List[Tree[T]]): List[Tree[T]] =
-    if (trees exists isTempTrees)
-      trees flatMap {
-        case TempTrees(ts) => ts
-        case t => t :: Nil
+    def mapConserve(f: Tree[T] => Tree[T]): TempTrees[T] = {
+      var i = 0
+      var newTrees = trees
+      var nestedSeen = false
+      var nestedDelta = 0
+      while (i < trees.length) {
+        val x = trees(i)
+        val y = f(x)
+        if ((x ne y) && (newTrees eq trees)) {
+          newTrees = new Array[Tree[T]](trees.length)
+          trees.copyToArray(newTrees, 0, i)
+        }
+        y match {
+          case TempTrees(ys) =>
+            nestedSeen = true
+            nestedDelta += (ys.length - 1)
+          case _ =>
+        }
+        newTrees(i) = y
+        i += 1
       }
-    else trees
+      TempTrees(if (nestedSeen) flattenArray(newTrees, nestedDelta) else newTrees)
+    }
+  }
 
-  def combine[T >: Untyped](trees: List[Tree[T]]): Tree[T] = flatten(trees) match {
-    case tree :: Nil => tree
-    case ts => TempTrees[T](ts)
+  object TempTrees {
+    def fromList[T >: Untyped](elems: List[Tree[T]]): TempTrees[T] = apply(elems.toArray)
   }
 
-  private val isTempTrees: Any => Boolean = (_.isInstanceOf[TempTrees[_]])
+  private val defaultTreesBuilderSize = 10
+
+  class TreesBuilder[T >: Untyped] extends Builder[Tree[T], TempTrees[T]] {
+    private var elems: Array[Tree[T]] = null
+    private var length = 0
+
+    private def resizedElems(newLength: Int): Array[Tree[T]] = {
+      val newElems = new Array[Tree[T]](newLength)
+      elems.copyToArray(newElems)
+      newElems
+    }
+
+    private def ensureSize(targetLength: Int) =
+      while (elems.length < targetLength) elems = resizedElems(elems.length * 2)
+
+    override def += (elem: Tree[T]): this.type = {
+      if (elems == null) elems = new Array[Tree[T]](defaultTreesBuilderSize)
+      ensureSize(length + 1)
+      elems(length) = elem
+      length += 1
+      this
+    }
+
+    override def clear() = length = 0
+
+    def result(): TempTrees[T] =
+      TempTrees(if (length == elems.length) elems else resizedElems(length))
+
+    override def sizeHint(n: Int) =
+      if (elems == null) elems = new Array[Tree[T]](n)
+  }
+
+  // ----- Auxiliary creation methods ------------------
 
   def Block[T >: Untyped](stat: Tree[T], expr: Tree[T]): Block[T] =
     Block(stat :: Nil, expr)
@@ -902,7 +974,7 @@ object Trees {
       case tree: SharedTree[_] if (shared eq tree.shared) => tree
       case _ => SharedTree(shared).copyAttr(tree)
     }
-    def derivedTempTrees(trees: List[Tree[T]]): TempTrees[T] = tree match {
+    def derivedTempTrees(trees: Array[Tree[T]]): TempTrees[T] = tree match {
       case tree: TempTrees[_] if (trees eq tree.trees) => tree
       case _ => TempTrees(trees).copyAttr(tree)
     }
@@ -1006,7 +1078,7 @@ object Trees {
         tree, c, plugins)
     }
     def transform(trees: List[Tree[T]], c: C): List[Tree[T]] =
-      flatten(trees mapConserve (transform(_, c)))
+      /*flatten*/(trees mapConserve (transform(_, c)))
     def transformSub(tree: Tree[T], c: C): tree.ThisTree[T] =
       transform(tree, c).asInstanceOf[tree.ThisTree[T]]
     def transformSub[TT <: Tree[T]](trees: List[TT], c: C): List[TT] =
@@ -1154,11 +1226,11 @@ object Trees {
             sharedMemo = sharedMemo.updated(tree, tree1)
             tree1
         }
-      case TempTrees(trees) =>
-        tree.derivedTempTrees(transform(trees))
+      case trees: TempTrees[_] =>
+        trees.mapConserve(transform(_))
     }
     def transform(trees: List[Tree[T]]): List[Tree[T]] =
-      flatten(trees mapConserve (transform(_)))
+      /*flatten*/(trees mapConserve (transform(_)))
     def transformSub(tree: Tree[T]): tree.ThisTree[T] =
       transform(tree).asInstanceOf[tree.ThisTree[T]]
     def transformSub[TT <: Tree[T]](trees: List[TT]): List[TT] =
diff --git a/src/dotty/tools/dotc/ast/TypedTrees.scala b/src/dotty/tools/dotc/ast/TypedTrees.scala
index 860611b97..c46da61f2 100644
--- a/src/dotty/tools/dotc/ast/TypedTrees.scala
+++ b/src/dotty/tools/dotc/ast/TypedTrees.scala
@@ -305,7 +305,7 @@ object tpd extends Trees.Instance[Type] {
     val constr = DefDef(modcls.primaryConstructor.asTerm, EmptyTree)
     val clsdef = ClassDef(modcls, Nil, constr, body)
     val valdef = ValDef(sym, New(modcls.typeConstructor))
-    TempTrees(valdef :: clsdef :: Nil)
+    TempTrees(Array(valdef, clsdef))
   }
 
   private class FindLocalDummyAccumulator(cls: ClassSymbol)(implicit ctx: Context) extends TreeAccumulator[Symbol] {
diff --git a/src/dotty/tools/dotc/ast/UntypedTrees.scala b/src/dotty/tools/dotc/ast/UntypedTrees.scala
index ba67a0546..8f9ef59e1 100644
--- a/src/dotty/tools/dotc/ast/UntypedTrees.scala
+++ b/src/dotty/tools/dotc/ast/UntypedTrees.scala
@@ -292,7 +292,7 @@ object untpd extends Trees.Instance[Untyped] {
             val restDefs =
               for (((named, tpt), n) <- vars.zipWithIndex)
                 yield derivedValDef(mods, named, tpt, selector(n))
-            TempTrees(firstDef :: restDefs)
+            TempTrees.fromList(firstDef :: restDefs)
         }
     }
 
@@ -324,7 +324,7 @@ object untpd extends Trees.Instance[Untyped] {
         val clsSelf = self.derivedValDef(self.mods, self.name, SingletonTypeTree(Ident(name)), self.rhs)
         val clsTmpl = tmpl.derivedTemplate(constr, parents, clsSelf, body)
         val cls = ClassDef(mods.toTypeFlags & AccessFlags | ModuleClassCreationFlags, clsName, Nil, clsTmpl)
-        TempTrees(List(modul, cls))
+        TempTrees(Array[Tree](modul, cls))
       case SymbolLit(str) =>
         New(ref(defn.SymbolClass.typeConstructor), (Literal(Constant(str)) :: Nil) :: Nil)
       case InterpolatedString(id, strs, elems) =>
@@ -381,8 +381,8 @@ object untpd extends Trees.Instance[Untyped] {
       case ForYield(enums, body) =>
         makeFor(nme.map, nme.flatMap, enums, body) orElse tree
       case PatDef(mods, pats, tpt, rhs) =>
-        val pats1 = if (tpt.isEmpty) pats else pats map (Typed(_, tpt))
-        combine(pats1 map (makePatDef(mods, _, rhs)))
+        val pats1 = TempTrees.fromList(if (tpt.isEmpty) pats else pats map (Typed(_, tpt)))
+        pats1.mapConserve(makePatDef(mods, _, rhs))
       case _ =>
         tree
     }