More performant encoding of tree errors.

Stole two bits from Tree#id to record whether a tree contains an
error tree and whether its subtrees have been checked. This leaves us
with only a single gigatree of headroom for replaying trees in the
presentation compiler. Alert the media.

Review by odersky.

1 files changed, 33 insertions, 54 deletions

diff --git a/src/library/scala/reflect/api/Trees.scala b/src/library/scala/reflect/api/Trees.scala
index 9dc368a71c..4606d882e3 100644
--- a/src/library/scala/reflect/api/Trees.scala
+++ b/src/library/scala/reflect/api/Trees.scala
@@ -8,11 +8,23 @@ package api
 
 import scala.collection.mutable.ListBuffer
 
-//import scala.tools.nsc.util.{ FreshNameCreator, HashSet, SourceFile }
+object Trees {
+  private final val TreeIdMask   = 0x00FFFFFF
+  private final val Erroneous    = 1 << 31
+  private final val ErrorChecked = 1 << 30
+}
+import Trees._
 
 trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
 
-  private[scala] var nodeCount = 0
+  // Pretty convenient when you need it:
+  //
+  // implicit def treeOps(tree: Tree): TreeOps
+  // type TreeOps <: {
+  //   def summaryString: String
+  // }
+
+  private[scala] var nodeCount = -1
 
   type Modifiers <: AbsModifiers
 
@@ -76,8 +88,14 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    *  example is Parens, which is eliminated during parsing.
    */
   abstract class Tree extends Product {
-    val id = nodeCount
-    nodeCount += 1
+    private[this] var treebits: Int = { nodeCount += 1; nodeCount }
+
+    def id                               = (treebits & TreeIdMask)
+    def isErrorTree                      = (treebits & Erroneous) != 0
+    def isErrorChecked                   = (treebits & ErrorChecked) != 0
+    protected final def setErrorBit()    = treebits |= Erroneous
+    protected final def setCheckedBit()  = treebits |= ErrorChecked
+    private[scala] def resetErrorBits()  = treebits = id
 
     private[this] var rawpos: Position = NoPosition
 
@@ -210,6 +228,7 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
       pos = tree.pos
       tpe = tree.tpe
       if (hasSymbol) symbol = tree.symbol
+      if (tree.isErrorTree) setErrorBit()
       this
     }
 
@@ -217,12 +236,15 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     override def hashCode(): Int = System.identityHashCode(this)
     override def equals(that: Any) = this eq that.asInstanceOf[AnyRef]
 
-    // TODO: implementation of more aggresive caching still needs
-    // more testing
-    //protected var hasErrorTree: List[ErrorTree] = null
-    protected def errorSubtrees: List[Tree]
-    private lazy val hasErrorTree: Boolean = errorSubtrees exists (_.containsError())
-    def containsError(): Boolean = hasErrorTree
+    def containsError(): Boolean = {
+      if (!isErrorChecked) {
+        for (t <- this ; if (t ne this) && t.containsError())
+          setErrorBit()
+
+        setCheckedBit()
+      }
+      isErrorTree
+    }
   }
 
   trait AbsErrorTree extends Tree {
@@ -269,7 +291,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     override def tpe_=(t: Type) =
       if (t != NoType) throw new UnsupportedOperationException("tpe_=("+t+") inapplicable for <empty>")
     override def isEmpty = true
-    def errorSubtrees = Nil
   }
 
   /** Common base class for all member definitions: types, classes,
@@ -296,7 +317,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     def name = pid.name
     def mods = Modifiers()
 
-    protected def errorSubtrees = stats
   }
 
   /** A common base class for class and object definitions.
@@ -309,7 +329,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class ClassDef(mods: Modifiers, name: TypeName, tparams: List[TypeDef], impl: Template)
        extends ImplDef {
-    protected def errorSubtrees = tparams :+ impl
   }
 
   /** An object definition, e.g. `object Foo`.  Internally, objects are
@@ -317,7 +336,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class ModuleDef(mods: Modifiers, name: TermName, impl: Template)
        extends ImplDef {
-    protected def errorSubtrees = List(impl)
   }
 
   /** A common base class for ValDefs and DefDefs.
@@ -332,21 +350,18 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    *  vals only in having the MUTABLE flag set in their Modifiers.)
    */
   case class ValDef(mods: Modifiers, name: TermName, tpt: Tree, rhs: Tree) extends ValOrDefDef {
-    protected def errorSubtrees = List(tpt, rhs)
   }
 
   /** A method definition.
    */
   case class DefDef(mods: Modifiers, name: TermName, tparams: List[TypeDef],
                     vparamss: List[List[ValDef]], tpt: Tree, rhs: Tree) extends ValOrDefDef {
-    protected def errorSubtrees = tparams ++ vparamss.flatten ++ List(tpt, rhs)
   }
 
   /** An abstract type, a type parameter, or a type alias.
    */
   case class TypeDef(mods: Modifiers, name: TypeName, tparams: List[TypeDef], rhs: Tree)
        extends MemberDef {
-    protected def errorSubtrees = tparams :+ rhs
   }
 
   /** A labelled expression.  Not expressible in language syntax, but
@@ -365,7 +380,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class LabelDef(name: TermName, params: List[Ident], rhs: Tree)
        extends DefTree with TermTree {
-    protected def errorSubtrees = params :+ rhs
   }
 
   /** Import selector
@@ -386,7 +400,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class Import(expr: Tree, selectors: List[ImportSelector])
        extends SymTree {
-    protected def errorSubtrees = List(expr)
   }
     // The symbol of an Import is an import symbol @see Symbol.newImport
     // It's used primarily as a marker to check that the import has been typechecked.
@@ -409,13 +422,11 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     //      def bar  // owner is local dummy
     //   }
     // System.err.println("TEMPLATE: " + parents)
-    protected def errorSubtrees = self::parents:::body
   }
 
   /** Block of expressions (semicolon separated expressions) */
   case class Block(stats: List[Tree], expr: Tree)
        extends TermTree {
-    protected def errorSubtrees = stats :+ expr
   }
 
   /** Case clause in a pattern match, eliminated during explicitouter
@@ -423,7 +434,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class CaseDef(pat: Tree, guard: Tree, body: Tree)
        extends Tree {
-    protected def errorSubtrees = List(pat, guard, body)
   }
 
   /** Alternatives of patterns, eliminated by explicitouter, except for
@@ -431,13 +441,11 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class Alternative(trees: List[Tree])
        extends TermTree {
-    protected def errorSubtrees = trees
   }
 
   /** Repetition of pattern, eliminated by explicitouter */
   case class Star(elem: Tree)
        extends TermTree {
-    protected def errorSubtrees = List(elem)
   }
 
   /** Bind of a variable to a rhs pattern, eliminated by explicitouter
@@ -447,25 +455,21 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class Bind(name: Name, body: Tree)
        extends DefTree {
-    protected def errorSubtrees = List(body)
   }
 
   case class UnApply(fun: Tree, args: List[Tree])
        extends TermTree {
-    protected def errorSubtrees = fun::args
   }
 
   /** Array of expressions, needs to be translated in backend,
    */
   case class ArrayValue(elemtpt: Tree, elems: List[Tree])
        extends TermTree {
-    protected def errorSubtrees = elemtpt::elems
   }
 
   /** Anonymous function, eliminated by analyzer */
   case class Function(vparams: List[ValDef], body: Tree)
        extends TermTree with SymTree  {
-    protected def errorSubtrees = vparams :+ body
   }
     // The symbol of a Function is a synthetic value of name nme.ANON_FUN_NAME
     // It is the owner of the function's parameters.
@@ -473,13 +477,11 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
   /** Assignment */
   case class Assign(lhs: Tree, rhs: Tree)
        extends TermTree {
-    protected def errorSubtrees = List(lhs, rhs)
   }
 
   /** Conditional expression */
   case class If(cond: Tree, thenp: Tree, elsep: Tree)
        extends TermTree {
-    protected def errorSubtrees = List(cond, thenp, elsep)
   }
 
   /** - Pattern matching expression  (before explicitouter)
@@ -495,25 +497,21 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class Match(selector: Tree, cases: List[CaseDef])
        extends TermTree {
-    protected def errorSubtrees = selector::cases
   }
 
   /** Return expression */
   case class Return(expr: Tree)
        extends TermTree with SymTree {
-    protected def errorSubtrees = List(expr)
   }
     // The symbol of a Return node is the enclosing method.
 
   case class Try(block: Tree, catches: List[CaseDef], finalizer: Tree)
        extends TermTree {
-    protected def errorSubtrees = block +: catches :+ finalizer
   }
 
   /** Throw expression */
   case class Throw(expr: Tree)
        extends TermTree {
-    protected def errorSubtrees = List(expr)
   }
 
   /** Object instantiation
@@ -522,13 +520,11 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    *  @param tpt    a class type
    */
   case class New(tpt: Tree) extends TermTree {
-    protected def errorSubtrees = List(tpt)
   }
 
   /** Type annotation, eliminated by explicit outer */
   case class Typed(expr: Tree, tpt: Tree)
        extends TermTree {
-    protected def errorSubtrees = List(expr, tpt)
   }
 
   /** Common base class for Apply and TypeApply. This could in principle
@@ -549,7 +545,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     override def symbol: Symbol = fun.symbol
     override def symbol_=(sym: Symbol) { fun.symbol = sym }
 
-    protected def errorSubtrees = fun::args
   }
 
   /** Value application */
@@ -558,7 +553,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     override def symbol: Symbol = fun.symbol
     override def symbol_=(sym: Symbol) { fun.symbol = sym }
 
-    protected def errorSubtrees = fun::args
   }
 
   class ApplyToImplicitArgs(fun: Tree, args: List[Tree]) extends Apply(fun, args)
@@ -573,7 +567,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    */
   case class ApplyDynamic(qual: Tree, args: List[Tree])
        extends TermTree with SymTree {
-    protected def errorSubtrees = qual::args
   }
     // The symbol of an ApplyDynamic is the function symbol of `qual`, or NoSymbol, if there is none.
 
@@ -584,14 +577,12 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     override def symbol: Symbol = qual.symbol
     override def symbol_=(sym: Symbol) { qual.symbol = sym }
 
-    protected def errorSubtrees = List(qual)
   }
 
   /** Self reference */
   case class This(qual: TypeName)
         extends TermTree with SymTree {
     // TODO should check qual name, symbol?
-    def errorSubtrees = Nil
   }
     // The symbol of a This is the class to which the this refers.
     // For instance in C.this, it would be C.
@@ -599,12 +590,10 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
   /** Designator <qualifier> . <name> */
   case class Select(qualifier: Tree, name: Name)
        extends RefTree {
-    protected def errorSubtrees = List(qualifier)
   }
 
   /** Identifier <name> */
   case class Ident(name: Name) extends RefTree {
-    def errorSubtrees = Nil
   }
 
   class BackQuotedIdent(name: Name) extends Ident(name)
@@ -613,7 +602,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
   case class Literal(value: Constant)
         extends TermTree {
     assert(value ne null)
-    def errorSubtrees = Nil
   }
 
 //  @deprecated("will be removed and then be re-introduced with changed semantics, use Literal(Constant(x)) instead")
@@ -625,27 +613,23 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
    *  an AnnotatedType.
    */
   case class Annotated(annot: Tree, arg: Tree) extends Tree {
-    protected def errorSubtrees = List(annot, arg)
   }
 
   /** Singleton type, eliminated by RefCheck */
   case class SingletonTypeTree(ref: Tree)
         extends TypTree {
 
-    protected def errorSubtrees = List(ref)
   }
 
   /** Type selection <qualifier> # <name>, eliminated by RefCheck */
   case class SelectFromTypeTree(qualifier: Tree, name: TypeName)
        extends TypTree with RefTree {
-    protected def errorSubtrees = List(qualifier)
   }
 
   /** Intersection type <parent1> with ... with <parentN> { <decls> }, eliminated by RefCheck */
   case class CompoundTypeTree(templ: Template)
        extends TypTree {
 
-    protected def errorSubtrees = List(templ)
   }
 
   /** Applied type <tpt> [ <args> ], eliminated by RefCheck */
@@ -654,19 +638,16 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     override def symbol: Symbol = tpt.symbol
     override def symbol_=(sym: Symbol) { tpt.symbol = sym }
 
-    protected def errorSubtrees = tpt::args
   }
 
   case class TypeBoundsTree(lo: Tree, hi: Tree)
        extends TypTree {
 
-    protected def errorSubtrees = List(lo, hi)
   }
 
   case class ExistentialTypeTree(tpt: Tree, whereClauses: List[Tree])
        extends TypTree {
 
-    protected def errorSubtrees = tpt::whereClauses
   }
 
   /** A synthetic tree holding an arbitrary type.  Not to be confused with
@@ -698,6 +679,7 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
     def setErrorCause(tree: Tree): this.type = {
       assert(tree != null)
       errorCause = tree
+      setErrorBit()
       this
     }
 
@@ -705,9 +687,6 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe =>
       wasEmpty = isEmpty
       setType(tp)
     }
-
-    def errorSubtrees = Nil
-    override def containsError() = errorCause != null
   }
 
   def TypeTree(tp: Type): TypeTree = TypeTree() setType tp