Take the N^2 out of the compiler's TreeSet.

The code responsible for this performance bug lives on somewhere
in the combination of Iterator.single and Iterator.++ and is
tracked by SI-7316. What this commit does is bypass the creation
and composition of iterators entirely in favor of applying foreach
to walking the tree.

The important lesson of a bug like this: the occurrence depends on
the existence of multiple implementations of basic structures like
Trees. For each redundant implementation, scrutiny and testing
are divided and "bug diversity" is increased. We should labor
hard to structure collections in such a way that people have no
good reason not to take advantage of the basic and hopefully
battle-tested logic - especially when those people are us.

I hope to remove util.TreeSet entirely. Until then, here is the
impact of this commit on the time to compile a piece of generated
test code.

  % time scalac3 ./target/generated/src.scala
  Mar 28 13:20:31 [running phase parser on src.scala]
  ...
  Mar 28 13:21:28 [running phase lazyvals on src.scala]
  Mar 28 13:21:28 [running phase lambdalift on src.scala]  <-- WHOA
  Mar 28 13:25:05 [running phase constructors on src.scala]
  ...
  Mar 28 13:25:19 [running phase jvm on icode]
  316.387 real, 438.182 user, 8.163 sys

To this:

  97.927 real, 211.015 user, 8.043 sys

  % time pscalac ./target/generated/src.scala
  Mar 28 13:18:47 [running phase parser on src.scala]
  ...
  Mar 28 13:19:44 [running phase lazyvals on src.scala]
  Mar 28 13:19:44 [running phase lambdalift on src.scala]
  Mar 28 13:19:46 [running phase constructors on src.scala]
  ...
  Mar 28 13:19:57 [running phase jvm on icode]
  99.909 real, 223.605 user, 7.847 sys

That's lambdalift dropping from 217 seconds to 2 seconds.

1 files changed, 15 insertions, 5 deletions

diff --git a/src/compiler/scala/tools/nsc/util/TreeSet.scala b/src/compiler/scala/tools/nsc/util/TreeSet.scala
index 3cdbcc5110..d2e9238e8f 100644
--- a/src/compiler/scala/tools/nsc/util/TreeSet.scala
+++ b/src/compiler/scala/tools/nsc/util/TreeSet.scala
@@ -40,12 +40,22 @@ class TreeSet[T >: Null <: AnyRef](less: (T, T) => Boolean) extends Set[T] {
     tree = add(tree)
   }
 
-  def iterator = {
-    def elems(t: Tree): Iterator[T] = {
-      if (t eq null) Iterator.empty
-      else elems(t.l) ++ (Iterator single t.elem) ++ elems(t.r)
+  def iterator = toList.iterator
+
+  override def foreach[U](f: T => U) {
+    def loop(t: Tree) {
+      if (t ne null) {
+        loop(t.l)
+        f(t.elem)
+        loop(t.r)
+      }
     }
-    elems(tree)
+    loop(tree)
+  }
+  override def toList = {
+    val xs = scala.collection.mutable.ListBuffer[T]()
+    foreach(xs += _)
+    xs.toList
   }
 
   override def toString(): String = {