From 5d033fbd0aed96770bd6802dbece6df1a5c8540e Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Sun, 4 Jan 2015 18:49:22 -0800 Subject: Expansion works properly, simplified graph code. --- lib/spack/spack/cmd/graph.py | 4 +- lib/spack/spack/graph.py | 234 +++++++++++++++++++++++++++---------------- 2 files changed, 148 insertions(+), 90 deletions(-) diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py index 58a411be71..f8cd18d91f 100644 --- a/lib/spack/spack/cmd/graph.py +++ b/lib/spack/spack/cmd/graph.py @@ -55,7 +55,7 @@ def graph(parser, args): graph_dot(*specs) elif specs: # ascii is default: user doesn't need to provide it explicitly - graph_ascii(specs[0]) + graph_ascii(specs[0], debug=spack.debug) for spec in specs[1:]: print # extra line bt/w independent graphs - graph_ascii(spec) + graph_ascii(spec, debug=spack.debug) diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py index 08bd6f18bb..c4f5de1ebc 100644 --- a/lib/spack/spack/graph.py +++ b/lib/spack/spack/graph.py @@ -29,7 +29,30 @@ This file contains code for graphing DAGs of software packages about: graph_ascii() will output a colored graph of a spec in ascii format, -knd of like the graph git shows with "git log --graph". +kind of like the graph git shows with "git log --graph", e.g.:: + + o mpileaks + |\ + | |\ + | o | callpath + |/| | + | |\| + | |\ \ + | | |\ \ + | | | | o adept-utils + | |_|_|/| + |/| | | | + o | | | | mpi + / / / / + | | o | dyninst + | |/| | + |/|/| | + | | |/ + | o | libdwarf + |/ / + o | libelf + / + o boost graph_dot() will output a graph of a spec (or multiple specs) in dot format. @@ -102,11 +125,16 @@ def find(seq, predicate): return -1 +# Names of different graph line states. We Record previous line +# states so that we can easily determine what to do when connecting. +states = ('node', 'collapse', 'merge-right', 'expand-right', 'back-edge') +NODE, COLLAPSE, MERGE_RIGHT, EXPAND_RIGHT, BACK_EDGE = states + class AsciiGraph(object): def __init__(self): # These can be set after initialization or after a call to # graph() to change behavior. - self.node_character = 'o' + self.node_character = '*' self.debug = False self.indent = 0 @@ -120,6 +148,7 @@ class AsciiGraph(object): self._out = None # Output stream self._frontier = None # frontier self._nodes = None # dict from name -> node + self._prev_state = None # State of previous line def _indent(self): @@ -133,7 +162,7 @@ class AsciiGraph(object): self._out.write(edge) - def _connect_deps(self, i, deps, collapse, label): + def _connect_deps(self, i, deps, label=None): """Connect dependencies to existing edges in the frontier. ``deps`` are to be inserted at position i in the @@ -147,9 +176,6 @@ class AsciiGraph(object): Parameters: - collapse -- whether the frontier is collapsing or staying the - same size. - label -- optional debug label for the connection. Returns: True if the deps were connected to another edge @@ -161,20 +187,25 @@ class AsciiGraph(object): if len(deps) == 1 and deps in self._frontier: j = self._frontier.index(deps) - # connect to the left - if j < i: - if i-j > 1: # two lines if distance > 1 - self._back_edge([], j, i, True, label) - self._back_edge([j], -1, -1, (i-j == 1), label) - - # connect to the right - else: - if i < j: - self._frontier.pop(j) - self._frontier.insert(i, deps) - if j-i > 1: - self._back_edge([], i, j+1, collapse, label) - self._back_edge([i], -1, -1, not (j-i > 1) and collapse, label) + # convert a right connection into a left connection + if i < j: + self._frontier.pop(j) + self._frontier.insert(i, deps) + return self._connect_deps(j, deps, label) + + collapse = True + if self._prev_state == EXPAND_RIGHT: + # Special case for when prev. line expanded (spacing is off by 1) + # Need two lines here even when distance in frontier is 1. + self._back_edge_line([], j, i+1, True, label + "-1.5 " + str((i,j))) + collapse = False + + elif i-j > 1: + # We need two lines to connect if distance > 1 + self._back_edge_line([], j, i, True, label + "-1 " + str((i,j))) + collapse = False + + self._back_edge_line([j], -1, -1, collapse, label + "-2 " + str((i,j))) return True elif deps: @@ -182,22 +213,20 @@ class AsciiGraph(object): return False - def _add_deps_to_frontier(self, node, i): - """Add dependencies to frontier. - - Adds the dependencies of to the frontier, and connects - them to other open edges if they match. Also deletes parent - pointers in the node to mark edges as covered. - - """ - deps = sorted((d for d in node.dependencies), reverse=True) - self._connect_deps(i, deps, True, "add_deps") - for d in deps: - del self._nodes[d].dependents[node.name] + def _set_state(self, state, label=None): + if state not in states: + raise ValueError("Invalid graph state!") + self._prev_state = state + if self.debug: + self._out.write(" " * 20) + self._out.write("%-20s" % ( + str(self._prev_state) if self._prev_state else '')) + self._out.write("%-20s" % (str(label) if label else '')) + self._out.write("%s" % self._frontier) - def _back_edge(self, prev_ends, end, start, collapse, label=None): + def _back_edge_line(self, prev_ends, end, start, collapse, label=None): """Write part of a backwards edge in the graph. Writes single- or multi-line backward edges in an ascii graph. @@ -267,12 +296,64 @@ class AsciiGraph(object): else: advance(flen, lambda: [("| ", self._pos)] ) - if self.debug: - self._out.write(" " * 10) - if label: - self._out.write(label) - self._out.write("%s" % self._frontier) + self._set_state(BACK_EDGE, label) + self._out.write("\n") + + + def _node_line(self, index, name): + """Writes a line with a node at index.""" + self._indent() + for c in range(index): + self._write_edge("| ", c) + + self._out.write("%s " % self.node_character) + + for c in range(index+1, len(self._frontier)): + self._write_edge("| ", c) + + self._out.write(" %s" % name) + self._set_state(NODE) + self._out.write("\n") + + + def _collapse_line(self, index): + """Write a collapsing line after a node was added at index.""" + self._indent() + for c in range(index): + self._write_edge("| ", c) + for c in range(index, len(self._frontier)): + self._write_edge(" /", c) + self._set_state(COLLAPSE) + self._out.write("\n") + + + def _merge_right_line(self, index): + """Edge at index is same as edge to right. Merge directly with '\'""" + self._indent() + for c in range(index): + self._write_edge("| ", c) + self._write_edge("|", index) + self._write_edge("\\", index+1) + for c in range(index+1, len(self._frontier)): + self._write_edge("| ", c ) + + self._set_state(MERGE_RIGHT) + self._out.write("\n") + + + def _expand_right_line(self, index): + self._indent() + for c in range(index): + self._write_edge("| ", c) + + self._write_edge("|", index) + self._write_edge("\\", index+1) + + for c in range(index+2, len(self._frontier)): + self._write_edge(" \\", c) + + self._set_state(EXPAND_RIGHT) self._out.write("\n") @@ -311,27 +392,22 @@ class AsciiGraph(object): self._name_to_color = dict((name, self.colors[i % len(self.colors)]) for i, name in enumerate(topo_order)) - # This array tracks the open edges at the frontier of the - # graph we're writing out. - self._frontier = [] - - self._add_deps_to_frontier(spec, 0) - self._indent() - self._out.write('%s %s\n' % (self.node_character, spec.name)) - topo_order.pop() - + # Frontier tracks open edges of the graph as it's written out. + self._frontier = [[spec.name]] while self._frontier: # Find an unexpanded part of frontier i = find(self._frontier, lambda f: len(f) > 1) - # Expand frontier until there are enough columns for all children. if i >= 0: + # Expand frontier until there are enough columns for all children. + # Figure out how many back connections there are and # sort them so we do them in order back = [] for d in self._frontier[i]: b = find(self._frontier[:i], lambda f: f == [d]) - if b != -1: back.append((b, d)) + if b != -1: + back.append((b, d)) # Do all back connections in sorted order so we can # pipeline them and save space. @@ -341,79 +417,61 @@ class AsciiGraph(object): for j, (b, d) in enumerate(back): self._frontier[i].remove(d) if i-b > 1: - self._back_edge(prev_ends, b, i, False) + self._back_edge_line(prev_ends, b, i, False, 'left-1') del prev_ends[:] prev_ends.append(b) - self._back_edge(prev_ends, -1, -1, False) + self._back_edge_line(prev_ends, -1, -1, False, 'left-2') if not self._frontier[i]: self._frontier.pop(i) elif len(self._frontier[i]) > 1: - # Expand forawrd after doing all back connections - self._indent() - for c in range(i): - self._write_edge("| ", c) - self._write_edge("|", i) + # Expand forward after doing all back connections if (i+1 < len(self._frontier) and len(self._frontier[i+1]) == 1 and self._frontier[i+1][0] in self._frontier[i]): # We need to connect to the element to the right. # Keep lines straight by connecting directly and - # avoiding immediate expand/contract. + # avoiding unnecessary expand/contract. name = self._frontier[i+1][0] self._frontier[i].remove(name) - - self._write_edge("\\", i+1) - for c in range(i+1, len(self._frontier)): - self._write_edge("| ", c ) - self._out.write("\n") + self._merge_right_line(i) else: # Just allow the expansion here. name = self._frontier[i].pop(0) deps = [name] - self._write_edge("\\", i) - for c in range(i+1, len(self._frontier)): - self._write_edge(" \\", c) - self._out.write("\n") - self._connect_deps(i, deps, True, "expansion") + self._frontier.insert(i, deps) + self._expand_right_line(i) + + self._frontier.pop(i) + self._connect_deps(i, deps, "post-expand") + # Handle any remaining back edges to the right j = i+1 while j < len(self._frontier): deps = self._frontier.pop(j) - if not self._connect_deps(j, deps, True, "rem_back"): + if not self._connect_deps(j, deps, "back-from-right"): j += 1 else: + # Nothing to expand; add dependencies for a node. name = topo_order.pop() node = self._nodes[name] - # Find the next node in topo order and remove it from - # 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. + # Find the named node in the frontier and draw it. i = find(self._frontier, lambda f: name in f) - self._frontier.pop(i) - - self._indent() - for c in range(i): - self._write_edge("| ", c) - self._out.write("%s " % self.node_character) - for c in range(i, len(self._frontier)): - self._write_edge("| ", c) - self._out.write(" %s\n" % name) + self._node_line(i, name) + # Replace node with its dependencies + self._frontier.pop(i) if node.dependencies: - self._add_deps_to_frontier(node, i) + deps = sorted((d for d in node.dependencies), reverse=True) + self._connect_deps(i, deps, "new-deps") # anywhere. + elif self._frontier: - self._indent() - for c in range(i): - self._write_edge("| ", c) - for c in range(i, len(self._frontier)): - self._write_edge(" /", c) - self._out.write("\n") + self._collapse_line(i) def graph_ascii(spec, **kwargs): -- cgit v1.2.3-70-g09d2