Faster/leaner tree dumping. (Kevin Quick)

4 files changed, 96 insertions, 14 deletions

diff --git a/src/CHANGES.txt b/src/CHANGES.txt
index 4c23967..1bd5e01 100644
--- a/src/CHANGES.txt
+++ b/src/CHANGES.txt
@@ -273,6 +273,8 @@ RELEASE 0.97 - XXX
   - Handle Python stack traces consistently (stop at the SConscript stack
     frame, by default) even if the Python source code isn't available.
 
+  - Improve the performance of the --debug={tree,dtree} options.
+
   From Levi Stephen:
 
   - Allow $JARCHDIR to be expanded to other construction variables.
diff --git a/src/engine/SCons/Script/__init__.py b/src/engine/SCons/Script/__init__.py
index 712b4ba..a3d933d 100644
--- a/src/engine/SCons/Script/__init__.py
+++ b/src/engine/SCons/Script/__init__.py
@@ -125,10 +125,10 @@ class BuildTask(SCons.Taskmaster.Task):
         # this method is serialized, but execute isn't:
         if print_tree and self.top:
             print
-            print SCons.Util.render_tree(self.targets[0], get_all_children)
+            SCons.Util.print_tree(self.targets[0], get_all_children)
         if print_dtree and self.top:
             print
-            print SCons.Util.render_tree(self.targets[0], get_derived_children)
+            SCons.Util.print_tree(self.targets[0], get_derived_children)
         if print_includes and self.top:
             t = self.targets[0]
             tree = t.render_include_tree()
diff --git a/src/engine/SCons/Util.py b/src/engine/SCons/Util.py
index b2bae65..ec809b9 100644
--- a/src/engine/SCons/Util.py
+++ b/src/engine/SCons/Util.py
@@ -1018,7 +1018,9 @@ def render_tree(root, child_func, prune=0, margin=[0], visited={}):
        or in the whole tree if prune.
     """
 
-    if visited.has_key(root):
+    rname = str(root)
+
+    if visited.has_key(rname):
         return ""
 
     children = child_func(root)
@@ -1029,10 +1031,10 @@ def render_tree(root, child_func, prune=0, margin=[0], visited={}):
         else:
             retval = retval + "  "
 
-    retval = retval + "+-" + str(root) + "\n"
+    retval = retval + "+-" + rname + "\n"
     if not prune:
         visited = copy.copy(visited)
-    visited[root] = 1
+    visited[rname] = 1
 
     for i in range(len(children)):
         margin.append(i<len(children)-1)
@@ -1042,6 +1044,44 @@ def render_tree(root, child_func, prune=0, margin=[0], visited={}):
 
     return retval
 
+def print_tree(root, child_func, prune=0, margin=[0], visited={}):
+    """
+    Print a tree of nodes.  This is like render_tree, except it prints
+    lines directly instead of creating a string representation in memory,
+    so that huge trees can be printed.
+
+    root - the root node of the tree
+    child_func - the function called to get the children of a node
+    prune - don't visit the same node twice
+    margin - the format of the left margin to use for children of root.
+       1 results in a pipe, and 0 results in no pipe.
+    visited - a dictionary of visited nodes in the current branch if not prune,
+       or in the whole tree if prune.
+    """
+
+    rname = str(root)
+
+    if visited.has_key(rname):
+        return
+
+    def MMM(m):
+        return ["  ","| "][m]
+    print string.join(map(MMM, margin[:-1]), '') + "+-" + rname
+
+    if prune:
+        visited[rname] = 1
+        
+    children = child_func(root)
+    if children:
+        margin.append(1)
+        map(lambda C, cf=child_func, p=prune, m=margin, v=visited:
+                   print_tree(C, cf, p, m, v),
+            children[:-1])
+        margin[-1] = 0
+        print_tree(children[-1], child_func, prune, margin, visited)
+        margin.pop()
+                  
+
 def is_Dict(e):
     return type(e) is types.DictType or isinstance(e, UserDict)
 
diff --git a/src/engine/SCons/UtilTests.py b/src/engine/SCons/UtilTests.py
index cec89e1..18fd3c2 100644
--- a/src/engine/SCons/UtilTests.py
+++ b/src/engine/SCons/UtilTests.py
@@ -26,6 +26,7 @@ __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__"
 import os
 import os.path
 import string
+import StringIO
 import sys
 import types
 import unittest
@@ -941,7 +942,8 @@ class UtilTestCase(unittest.TestCase):
         q = quote_spaces('x\tx')
         assert q == '"x\tx"', q
 
-    def test_render_tree(self):
+    def tree_case_1(self):
+        """Fixture for the render_tree() and print_tree() tests."""
         class Node:
             def __init__(self, name, children=[]):
                 self.children = children
@@ -949,9 +951,6 @@ class UtilTestCase(unittest.TestCase):
             def __str__(self):
                 return self.name
 
-        def get_children(node):
-            return node.children
-
         windows_h = Node("windows.h")
         stdlib_h = Node("stdlib.h")
         stdio_h = Node("stdio.h")
@@ -972,9 +971,18 @@ class UtilTestCase(unittest.TestCase):
       +-windows.h
 """
 
-        actual = render_tree(foo, get_children)
-        assert expect == actual, (expect, actual)
+        return foo, expect
+
+    def tree_case_2(self):
+        """Fixture for the render_tree() and print_tree() tests."""
+        class Node:
+            def __init__(self, name, children=[]):
+                self.children = children
+                self.name = name
+            def __str__(self):
+                return self.name
 
+        stdlib_h = Node("stdlib.h")
         bar_h = Node('bar.h', [stdlib_h])
         blat_h = Node('blat.h', [stdlib_h])
         blat_c = Node('blat.c', [blat_h, bar_h])
@@ -988,9 +996,43 @@ class UtilTestCase(unittest.TestCase):
     +-bar.h
 """
 
-        actual = render_tree(blat_o, get_children, 1)
+        return blat_o, expect
+
+    def test_render_tree(self):
+        """Test the render_tree() function"""
+        def get_children(node):
+            return node.children
+
+        node, expect = self.tree_case_1()
+        actual = render_tree(node, get_children)
         assert expect == actual, (expect, actual)
 
+        node, expect = self.tree_case_2()
+        actual = render_tree(node, get_children, 1)
+        assert expect == actual, (expect, actual)
+
+    def test_print_tree(self):
+        """Test the print_tree() function"""
+        def get_children(node):
+            return node.children
+
+        save_stdout = sys.stdout
+
+        try:
+            sys.stdout = StringIO.StringIO()
+            node, expect = self.tree_case_1()
+            print_tree(node, get_children)
+            actual = sys.stdout.getvalue()
+            assert expect == actual, (expect, actual)
+
+            sys.stdout = StringIO.StringIO()
+            node, expect = self.tree_case_2()
+            print_tree(node, get_children, 1)
+            actual = sys.stdout.getvalue()
+            assert expect == actual, (expect, actual)
+        finally:
+            sys.stdout = save_stdout
+
     def test_is_Dict(self):
         assert is_Dict({})
         assert is_Dict(UserDict())
@@ -1585,8 +1627,6 @@ class UtilTestCase(unittest.TestCase):
 
     def test_LogicalLines(self):
         """Test the LogicalLines class"""
-        import StringIO
-
         fobj = StringIO.StringIO(r"""
 foo \
 bar \