Reverted removal of TreeSet to fix stability.

5 files changed, 68 insertions, 10 deletions

diff --git a/src/compiler/scala/tools/nsc/transform/Constructors.scala b/src/compiler/scala/tools/nsc/transform/Constructors.scala
index 7e15e4f0e4..9bccf5c95f 100644
--- a/src/compiler/scala/tools/nsc/transform/Constructors.scala
+++ b/src/compiler/scala/tools/nsc/transform/Constructors.scala
@@ -6,8 +6,9 @@
 
 package scala.tools.nsc.transform
 
-import scala.collection.mutable.{HashSet, ListBuffer}
+import scala.collection.mutable.ListBuffer
 import symtab.Flags._
+import util.TreeSet
 
 /** This phase converts classes with parameters into Java-like classes with
  *  fields, which are assigned to from constructors.
@@ -209,7 +210,7 @@ abstract class Constructors extends Transform {
       // ----------- avoid making fields for symbols that are not accessed --------------
 
       // A sorted set of symbols that are known to be accessed outside the primary constructor.
-      val accessedSyms = new HashSet[Symbol]
+      val accessedSyms = new TreeSet[Symbol]((x, y) => x isLess y)
 
       // a list of outer accessor symbols and their bodies
       var outerAccessors: List[(Symbol, Tree)] = List()
diff --git a/src/compiler/scala/tools/nsc/transform/LambdaLift.scala b/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
index e62bdba3be..38be297d4c 100644
--- a/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
+++ b/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
@@ -8,7 +8,8 @@ package scala.tools.nsc.transform
 
 import symtab._
 import Flags._
-import scala.collection.mutable.{HashSet, HashMap, ListBuffer}
+import util.TreeSet
+import scala.collection.mutable.{HashMap, ListBuffer}
 import scala.tools.nsc.util.{Position, NoPosition}
 
 abstract class LambdaLift extends InfoTransform {
@@ -61,9 +62,9 @@ abstract class LambdaLift extends InfoTransform {
     /** Buffers for lifted out classes and methods */
     private val liftedDefs = new HashMap[Symbol, ListBuffer[Tree]]
 
-    private type SymSet = HashSet[Symbol]
+    private type SymSet = TreeSet[Symbol]
 
-    private def newSymSet = new HashSet[Symbol]
+    private def newSymSet = new TreeSet[Symbol]((x, y) => x.isLess(y))
 
     private def symSet(f: HashMap[Symbol, SymSet], sym: Symbol): SymSet = f.get(sym) match {
       case Some(ss) => ss
diff --git a/src/compiler/scala/tools/nsc/transform/LiftCode.scala b/src/compiler/scala/tools/nsc/transform/LiftCode.scala
index 35bd1abaed..e3e9d70384 100644
--- a/src/compiler/scala/tools/nsc/transform/LiftCode.scala
+++ b/src/compiler/scala/tools/nsc/transform/LiftCode.scala
@@ -10,8 +10,8 @@ import symtab._
 import Flags._
 import symtab.Flags._
 import scala.collection.immutable.ListMap
-import scala.collection.mutable.{HashSet, HashMap, ListBuffer}
-import scala.tools.nsc.util.{FreshNameCreator}
+import scala.collection.mutable.{HashMap, ListBuffer}
+import scala.tools.nsc.util.{FreshNameCreator, TreeSet}
 
 /** Translate expressions of the form reflect.Code.lift(exp)
  *  to the lifted "reflect trees" representation of exp.
diff --git a/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala b/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
index c983717dc9..4217cc32ce 100644
--- a/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
+++ b/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
@@ -6,8 +6,9 @@
 
 package scala.tools.nsc.transform
 
-import collection.mutable.{HashSet, HashMap}
+import collection.mutable.HashMap
 import symtab.Flags._
+import util.HashSet
 
 /** This abstract class ...
  *
@@ -98,8 +99,7 @@ abstract class OverridingPairs {
       intersectionContainsElementLeq(subParents(index1), subParents(index2), minindex)
     }
 
-    private val visited =
-      new HashSet[ScopeEntry] { override def initialSize = 256 }
+    private val visited = new HashSet[ScopeEntry](256)
     private var curEntry = decls.elems
     private var nextEntry = curEntry
 
diff --git a/src/compiler/scala/tools/nsc/util/TreeSet.scala b/src/compiler/scala/tools/nsc/util/TreeSet.scala
new file mode 100644
index 0000000000..54ff5e2dd3
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/util/TreeSet.scala
@@ -0,0 +1,56 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2007 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+// $Id$
+
+package scala.tools.nsc.util
+
+/** Sets implemented as binary trees.
+ *
+ *  @author Martin Odersky
+ *  @version 1.0
+ */
+class TreeSet[T >: Null <: AnyRef](less: (T, T) => Boolean) extends Set[T] {
+
+  private class Tree(val elem: T) {
+    var l: Tree = null
+    var r: Tree = null
+  }
+
+  private var tree: Tree = null
+
+  def findEntry(x: T): T = {
+    def find(t: Tree): T = {
+      if (t eq null) null
+      else if (less(x, t.elem)) find(t.l)
+      else if (less(t.elem, x)) find(t.r)
+      else t.elem
+    }
+    find(tree)
+  }
+
+  def addEntry(x: T) {
+    def add(t: Tree): Tree = {
+      if (t eq null) new Tree(x)
+      else if (less(x, t.elem)) { t.l = add(t.l); t }
+      else if (less(t.elem, x)) { t.r = add(t.r); t }
+      else t
+    }
+    tree = add(tree)
+  }
+
+  def elements = {
+    def elems(t: Tree): Iterator[T] = {
+      var it = Iterator.single(t.elem)
+      if (t.l ne null) it = elems(t.l) append it
+      if (t.r ne null) it = it append elems(t.r)
+      it
+    }
+    if (tree eq null) Iterator.empty else elems(tree)
+  }
+
+  override def toString(): String = {
+    if (tree eq null) "<empty>" else "(..." + tree.elem + "...)"
+  }
+}