More compact graphs: do back edges before forward expansion.

1 files changed, 80 insertions, 46 deletions

diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 0720fe6212..2cd7bfb6be 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -1330,105 +1330,140 @@ class Spec(object):
         N      = kwargs.get('node', 'o')        # Node character
         color  = kwargs.get('color', True)
         out    = kwargs.get('out', ColorStream(sys.stdout, color=color))
+        debug  = kwargs.get('debug', False)
         indent = kwargs.get('indent', 0)
         indent *= ' '
 
         topo_order = self.topological_sort(reverse=True)
+
+        # Work on a clone so the spec is self contained (no incoming
+        # parent edges), and so we don't destroy this spec.
         clone = self.copy()
+
+        # Fast access to nodes in the spec.
         nodes = clone.index()
+        frontier = []
 
         def ordered_deps(node):
             deps = node.dependencies
             return sorted((d for d in deps), reverse=True)
 
-        frontier = []
-
-        debug = False
 
-        def back_edge(end, start):
+        def back_edge(end, start, **kwargs):
             assert(end < start)
+            collapse = kwargs.get('collapse', True)
+            label    = kwargs.get('label', '')  # debug label
 
-            if (start - end) > 1:
-                if debug:
-                    out.write(" " * 80)
 
+            if (start - end) > 1:
+                # This part draws a long back edge.
                 out.write(indent)
                 out.write("| " * (end + 1))
                 out.write("|_" * (start - end - 2))
-                out.write("|/ ")
-                out.write("/ " * (len(frontier) - start))
-                out.write("\n")
+                out.write("|/")
+                if collapse:
+                    out.write(" ")
+                    out.write("/ " * (len(frontier) - start))
+                else:
+                    out.write("| " * (len(frontier) - start))
 
-            if debug:
-                out.write(" " * 80)
+                if debug:
+                    out.write(" " * 20)
+                    out.write("%s  %s" % (frontier, label))
 
+                out.write("\n")
+
+            # This part draws the final collapsing line
             out.write(indent)
             out.write("| " * end)
             out.write("|/")
             out.write("| " * (start - end - 1))
-            if (start - end) > 1:
+            if (start - end) > 1 or not collapse:
                 out.write("| " * (len(frontier) - start))
             else:
                 out.write(" /" * (len(frontier) - start))
+
+            if debug:
+                out.write(" " * 20)
+                out.write("%s  %s" % (frontier, label))
+
             out.write("\n")
 
 
-        def connect_deps(i, deps):
+        def connect_deps(i, deps, **kwargs):
             if len(deps) == 1 and deps in frontier:
                 j = frontier.index(deps)
                 if j < i:
-                    back_edge(j, i)
+                    back_edge(j, i, **kwargs)
                 else:
                     if i < j:
                         frontier.pop(j)
                         frontier.insert(i, deps)
-                    back_edge(i, j+1)
+                    back_edge(i, j+1, **kwargs)
+                return True
 
             elif deps:
                 frontier.insert(i, deps)
+                return False
 
 
         def add_deps_to_frontier(node, i):
             deps = ordered_deps(node)
-            connect_deps(i, deps)
+            connect_deps(i, deps, label="add_deps")
             for d in deps:
                 del nodes[d].dependents[node.name]
 
 
-        name = topo_order.pop()
-        add_deps_to_frontier(nodes[name], 0)
+        def find(seq, predicate):
+            for i, elt in enumerate(seq):
+                if predicate(elt):
+                    return i
+            return -1
 
-        if debug:
-            out.write("%-80s" % frontier)
 
+        add_deps_to_frontier(self, 0)
         out.write(indent)
-        out.write('%s  %s\n' % (N, name))
-
-        while topo_order:
-            if debug:
-                out.write("%-80s" % frontier)
+        out.write('%s  %s\n' % (N, self.name))
+        topo_order.pop()
 
-            # Find last i, len(frontier[i]) > 1
-            i = len(frontier) - 1
-            for f in frontier[-1::-1]:
-                if len(f) > 1: break
-                i -= 1
+        while frontier:
+            # Find an unexpanded part of frontier
+            i = find(frontier, lambda f: len(f) > 1)
 
             # Expand frontier until there are enough columns for all children.
             if i >= 0:
-                out.write(indent)
-                out.write("| " * i)
-                out.write("|\ ")
-                out.write("\ " * (len(frontier) - i - 1))
-                out.write("\n")
+                # Do all back connections possible from this element
+                # before expanding.
+                back_connect = [d for d in frontier[i] if [d] in frontier[:i]]
+                for d in back_connect:
+                    j = frontier.index([d])
+                    frontier[i].remove(d)
+                    connect_deps(i, [d], collapse=False, label="back_connect")
+
+                if not frontier[i]:
+                    frontier.pop(i)
+
+                elif len(frontier[i]) > 1:
+                    name = frontier[i].pop(0)
+                    deps = [name]
+
+                    out.write(indent)
+                    out.write("| " * i)
+                    out.write("|\ ")
+                    out.write("\ " * (len(frontier) - i - 1))
+                    out.write("\n")
 
-                name = frontier[i].pop(0)
-                deps = [name]
+                    connect_deps(i, deps, label="expansion")
 
-                connect_deps(i, deps)
-                if i+1 < len(frontier) and len(frontier[i+1]) == 1:
-                    deps = frontier.pop(i+1)
-                    connect_deps(i+1, deps)
+                # Handle any back edges to the right
+                j = i+1
+                while j < len(frontier):
+                    deps = frontier.pop(j)
+                    # TODO: semantics of connect_deps are weird.
+                    # TODO: false return means the popped item was put
+                    # TODO: back & not connected.
+                    if not connect_deps(j, deps, label="ending"):
+                        j += 1
 
             else:
                 name = topo_order.pop()
@@ -1438,9 +1473,10 @@ class Spec(object):
                 # the frontier. Since specs are single-rooted DAGs,
                 # the node is always there. If the graph had multiple
                 # roots, we'd need to handle that case case of a new root.
-                i, elt = next(f for f in enumerate(frontier) if name in f[1])
+                i = find(frontier, lambda f: name in f)
                 frontier.pop(i)
 
+                out.write(indent)
                 out.write("| " * i)
                 out.write("%s " % N)
                 out.write("| " * (len(frontier) - i))
@@ -1449,9 +1485,7 @@ class Spec(object):
                 if node.dependencies:
                     add_deps_to_frontier(node, i)
                 elif frontier:
-                    if debug:
-                        out.write(" " * 80)
-
+                    out.write(indent)
                     out.write("| " * i)
                     out.write(" /" * (len(frontier) - i))
                     out.write("\n")