From 860f834aad0d6503057693b894d9996143dde312 Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Fri, 26 Dec 2014 13:52:31 -0800 Subject: spack graph allows plotting specific packages. --- lib/spack/llnl/util/lang.py | 22 ++++++++++++++++++++++ lib/spack/spack/cmd/graph.py | 11 ++++++++++- lib/spack/spack/packages.py | 16 +++++++++++++--- lib/spack/spack/spec.py | 17 +++++++++-------- 4 files changed, 54 insertions(+), 12 deletions(-) (limited to 'lib') diff --git a/lib/spack/llnl/util/lang.py b/lib/spack/llnl/util/lang.py index 049d158c6d..db15da0506 100644 --- a/lib/spack/llnl/util/lang.py +++ b/lib/spack/llnl/util/lang.py @@ -269,6 +269,28 @@ def in_function(function_name): del stack +def check_kwargs(kwargs, fun): + """Helper for making functions with kwargs. Checks whether the kwargs + are empty after all of them have been popped off. If they're + not, raises an error describing which kwargs are invalid. + + Example:: + + def foo(self, **kwargs): + x = kwargs.pop('x', None) + y = kwargs.pop('y', None) + z = kwargs.pop('z', None) + check_kwargs(kwargs, self.foo) + + # This raises a TypeError: + foo(w='bad kwarg') + """ + if kwargs: + raise TypeError( + "'%s' is an invalid keyword argument for function %s()." + % (next(kwargs.iterkeys()), fun.__name__)) + + class RequiredAttributeError(ValueError): def __init__(self, message): super(RequiredAttributeError, self).__init__(message) diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py index 39dbfbb150..955be51955 100644 --- a/lib/spack/spack/cmd/graph.py +++ b/lib/spack/spack/cmd/graph.py @@ -22,9 +22,18 @@ # along with this program; if not, write to the Free Software Foundation, # Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA ############################################################################## +from external import argparse import spack +import spack.cmd description = "Write out inter-package dependencies in dot graph format" +def setup_parser(subparser): + subparser.add_argument( + 'specs', nargs=argparse.REMAINDER, + help="specs of packages to graph. Default is all packages.") + + def graph(parser, args): - spack.db.graph_dependencies() + specs = spack.cmd.parse_specs(args.specs) + spack.db.graph_dependencies(*specs) diff --git a/lib/spack/spack/packages.py b/lib/spack/spack/packages.py index 25d01fe7eb..0aa8090b61 100644 --- a/lib/spack/spack/packages.py +++ b/lib/spack/spack/packages.py @@ -30,7 +30,7 @@ import imp import llnl.util.tty as tty from llnl.util.filesystem import join_path -from llnl.util.lang import memoized +from llnl.util.lang import * import spack.error import spack.spec @@ -214,9 +214,12 @@ class PackageDB(object): return cls - def graph_dependencies(self, out=sys.stdout): + def graph_dependencies(self, *specs, **kwargs): """Print out a graph of all the dependencies between package. Graph is in dot format.""" + out = kwargs.pop('out', sys.stdout) + check_kwargs(kwargs, self.graph_dependencies) + out.write('digraph G {\n') out.write(' label = "Spack Dependencies"\n') out.write(' labelloc = "b"\n') @@ -227,8 +230,15 @@ class PackageDB(object): def quote(string): return '"%s"' % string + if not specs: + packages = self.all_packages() + else: + packages = [] + for spec in specs: + packages.extend(s.package for s in spec.normalized().traverse()) + deps = [] - for pkg in self.all_packages(): + for pkg in packages: out.write(' %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name)) # Add edges for each depends_on in the package. diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index 570bb1191c..5f1385cc1b 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -858,7 +858,7 @@ class Spec(object): def normalized(self): """Return a normalized copy of this spec without modifying this spec.""" clone = self.copy() - clone.normalized() + clone.normalize() return clone @@ -1289,12 +1289,13 @@ class Spec(object): def tree(self, **kwargs): """Prints out this spec and its dependencies, tree-formatted with indentation.""" - color = kwargs.get('color', False) - depth = kwargs.get('depth', False) - showid = kwargs.get('ids', False) - cover = kwargs.get('cover', 'nodes') - indent = kwargs.get('indent', 0) - format = kwargs.get('format', '$_$@$%@$+$=') + color = kwargs.pop('color', False) + depth = kwargs.pop('depth', False) + showid = kwargs.pop('ids', False) + cover = kwargs.pop('cover', 'nodes') + indent = kwargs.pop('indent', 0) + fmt = kwargs.pop('format', '$_$@$%@$+$=') + check_kwargs(kwargs, self.tree) out = "" cur_id = 0 @@ -1311,7 +1312,7 @@ class Spec(object): out += (" " * d) if d > 0: out += "^" - out += node.format(format, color=color) + "\n" + out += node.format(fmt, color=color) + "\n" return out -- cgit v1.2.3-70-g09d2 From 6ffcdc1166642a70978a8631364aa8fd93560b62 Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Mon, 29 Dec 2014 00:03:35 -0800 Subject: Partially wroking ASCII dependency graph. --- lib/spack/spack/cmd/spec.py | 10 ++- lib/spack/spack/spec.py | 178 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 187 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/spack/spack/cmd/spec.py b/lib/spack/spack/cmd/spec.py index 5fcb0a9b5a..6f987d96d7 100644 --- a/lib/spack/spack/cmd/spec.py +++ b/lib/spack/spack/cmd/spec.py @@ -44,7 +44,15 @@ def spec(parser, args): print "Normalized" print "------------------------------" spec.normalize() - print spec.tree(color=True, indent=2) + print spec.tree(color=True, indent=2, cover='paths') + + print + print spec.topological_sort(reverse=True) + print + print "Graph" + print "------------------------------" + print spec.graph() + return print "Concretized" print "------------------------------" diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index 5f1385cc1b..9239bac08f 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -93,6 +93,7 @@ expansion when it is the first character in an id typed on the command line. import sys import itertools import hashlib +from heapq import * from StringIO import StringIO from operator import attrgetter @@ -712,6 +713,15 @@ class Spec(object): raise InconsistentSpecError("Invalid Spec DAG: %s" % e.message) + def index(self): + """Return DependencyMap that points to all the dependencies in this + spec.""" + dm = DependencyMap() + for spec in self.traverse(): + dm[spec.name] = spec + return dm + + def flatten(self): """Pull all dependencies up to the root (this spec). Merge constraints for dependencies with the same name, and if they @@ -1316,6 +1326,174 @@ class Spec(object): return out + def graph(self, **kwargs): + N = kwargs.get('node', 'o') # Node character + out = kwargs.get('out', sys.stdout) + indent = kwargs.get('indent', 0) + indent *= ' ' + + topo_order = self.topological_sort(reverse=True) + clone = self.copy() + nodes = clone.index() + + def ordered_deps(node): + deps = node.dependencies + return sorted((d for d in deps), reverse=True) + + frontier = [] + + debug = True + debug = False + + def back_edge(end, start): + assert(end < start) + + if (start - end) > 1: + if debug: + out.write(" " * 80) + + out.write(indent) + out.write("| " * (end + 1)) + out.write("|_" * (start - end - 2)) + out.write("|/ ") + out.write("/ " * (len(frontier) - start)) + out.write("\n") + + if debug: + out.write(" " * 80) + + out.write(indent) + out.write("| " * end) + out.write("|/") + out.write("| " * (start - end - 1)) + out.write(" /" * (len(frontier) - start)) + out.write("\n") + + + def connect_deps(i, deps): + if len(deps) == 1 and deps in frontier: + j = frontier.index(deps) + if j < i: + back_edge(j, i) + else: + if i < j: + frontier.pop(j) + frontier.insert(i, deps) + back_edge(i, j+1) + + elif deps: + frontier.insert(i, deps) + + + def add_deps_to_frontier(node, i): + deps = ordered_deps(node) + connect_deps(i, deps) + for d in deps: + del nodes[d].dependents[node.name] + + + name = topo_order.pop() + add_deps_to_frontier(nodes[name], 0) + + if debug: + out.write("%-80s" % frontier) + + out.write(indent) + out.write('%s %s\n' % (N, name)) + + while topo_order: + if debug: + out.write("%-80s" % frontier) + + # Find last i, len(frontier[i]) > 1 + i = len(frontier) - 1 + for f in frontier[-1::-1]: + if len(f) > 1: break + i -= 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") + + name = frontier[i].pop(0) + deps = [name] + + connect_deps(i, deps) + + else: + name = topo_order.pop() + node = 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. + i, elt = next(f for f in enumerate(frontier) if name in f[1]) + frontier.pop(i) + + out.write("| " * i) + out.write("%s " % N) + out.write("| " * (len(frontier) - i)) + out.write(" %s\n" % name) + + if node.dependencies: + add_deps_to_frontier(node, i) + elif frontier: + if debug: + out.write(" " * 80) + + out.write("| " * i) + out.write(" /" * (len(frontier) - i)) + out.write("\n") + + + out.write("\n") + out.write("%s\n" % frontier) + + # Reverse the lines in the output + #return '\n'.join(reversed(out.getvalue().split('\n'))) + + return "" #out.getvalue() + + + def topological_sort(self, **kwargs): + """Return a list of dependency specs sorted topologically. + This spec is not modified in the process.""" + reverse = kwargs.get('reverse', False) + if not reverse: + parents = lambda s: s.dependents + children = lambda s: s.dependencies + else: + parents = lambda s: s.dependencies + children = lambda s: s.dependents + + spec = self.copy() + nodes = spec.index() + + topo_order = [] + remaining = [name for name in nodes.keys() if not parents(nodes[name])] + heapify(remaining) + + while remaining: + name = heappop(remaining) + topo_order.append(name) + + node = nodes[name] + for dep in children(node).values(): + del parents(dep)[node.name] + if not parents(dep): + heappush(remaining, dep.name) + + if any(parents(s) for s in spec.traverse()): + raise ValueError("Spec has cycles!") + else: + return topo_order + + def __repr__(self): return str(self) -- cgit v1.2.3-70-g09d2 From a6e00f6086467eda633e099d3ed7696bd85184e7 Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Mon, 29 Dec 2014 01:05:21 -0800 Subject: Fix ColorStream --- lib/spack/llnl/util/tty/color.py | 21 ++++++++++++--------- lib/spack/spack/spec.py | 3 ++- 2 files changed, 14 insertions(+), 10 deletions(-) (limited to 'lib') diff --git a/lib/spack/llnl/util/tty/color.py b/lib/spack/llnl/util/tty/color.py index 598e9d44f5..81688d7f14 100644 --- a/lib/spack/llnl/util/tty/color.py +++ b/lib/spack/llnl/util/tty/color.py @@ -177,17 +177,20 @@ def cescape(string): class ColorStream(object): def __init__(self, stream, color=None): - self.__class__ = type(stream.__class__.__name__, - (self.__class__, stream.__class__), {}) - self.__dict__ = stream.__dict__ - self.color = color - self.stream = stream + self._stream = stream + self._color = color def write(self, string, **kwargs): - if kwargs.get('raw', False): - super(ColorStream, self).write(string) - else: - cwrite(string, self.stream, self.color) + raw = kwargs.get('raw', False) + raw_write = getattr(self._stream, 'write') + + color = self._color + if self._color is None: + if raw: + color=True + else: + color = self._stream.isatty() + raw_write(colorize(string, color=color)) def writelines(self, sequence, **kwargs): raw = kwargs.get('raw', False) diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index 9239bac08f..3386af8d7f 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -1328,7 +1328,8 @@ class Spec(object): def graph(self, **kwargs): N = kwargs.get('node', 'o') # Node character - out = kwargs.get('out', sys.stdout) + color = kwargs.get('color', True) + out = kwargs.get('out', ColorStream(sys.stdout, color=color)) indent = kwargs.get('indent', 0) indent *= ' ' -- cgit v1.2.3-70-g09d2 From 226de0a42d9a59c735edaf5075cbfc7ec3c53125 Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Mon, 29 Dec 2014 01:52:03 -0800 Subject: Spec graph works without color. --- lib/spack/spack/cmd/spec.py | 13 +++++-------- lib/spack/spack/spec.py | 18 +++++++----------- 2 files changed, 12 insertions(+), 19 deletions(-) (limited to 'lib') diff --git a/lib/spack/spack/cmd/spec.py b/lib/spack/spack/cmd/spec.py index 6f987d96d7..71bc12d6f5 100644 --- a/lib/spack/spack/cmd/spec.py +++ b/lib/spack/spack/cmd/spec.py @@ -46,15 +46,12 @@ def spec(parser, args): spec.normalize() print spec.tree(color=True, indent=2, cover='paths') - print - print spec.topological_sort(reverse=True) - print - print "Graph" - print "------------------------------" - print spec.graph() - return - print "Concretized" print "------------------------------" spec.concretize() print spec.tree(color=True, indent=2) + + print "Graph" + print "------------------------------" + spec.graph() + return diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index 3386af8d7f..0720fe6212 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -1343,7 +1343,6 @@ class Spec(object): frontier = [] - debug = True debug = False def back_edge(end, start): @@ -1367,7 +1366,10 @@ class Spec(object): out.write("| " * end) out.write("|/") out.write("| " * (start - end - 1)) - out.write(" /" * (len(frontier) - start)) + if (start - end) > 1: + out.write("| " * (len(frontier) - start)) + else: + out.write(" /" * (len(frontier) - start)) out.write("\n") @@ -1424,6 +1426,9 @@ class Spec(object): deps = [name] 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) else: name = topo_order.pop() @@ -1452,15 +1457,6 @@ class Spec(object): out.write("\n") - out.write("\n") - out.write("%s\n" % frontier) - - # Reverse the lines in the output - #return '\n'.join(reversed(out.getvalue().split('\n'))) - - return "" #out.getvalue() - - def topological_sort(self, **kwargs): """Return a list of dependency specs sorted topologically. This spec is not modified in the process.""" -- cgit v1.2.3-70-g09d2 From daf1e229f7a5b5210651d5beddaec6ef1ed125bf Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Mon, 29 Dec 2014 14:28:24 -0800 Subject: More compact graphs: do back edges before forward expansion. --- lib/spack/spack/spec.py | 126 ++++++++++++++++++++++++++++++------------------ 1 file changed, 80 insertions(+), 46 deletions(-) (limited to 'lib') 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") -- cgit v1.2.3-70-g09d2 From bb3dafa3b5d978b7e68eceeb7faf8b5d156f3058 Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Mon, 29 Dec 2014 20:55:02 -0800 Subject: Reduce number of immediate expand/contracts. --- lib/spack/spack/spec.py | 30 +++++++++++++++++++++--------- 1 file changed, 21 insertions(+), 9 deletions(-) (limited to 'lib') diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index 2cd7bfb6be..a8d080b0d2 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -1444,18 +1444,30 @@ class Spec(object): frontier.pop(i) elif len(frontier[i]) > 1: - name = frontier[i].pop(0) - deps = [name] - + # Expand forawrd after doing all back connections out.write(indent) out.write("| " * i) - out.write("|\ ") - out.write("\ " * (len(frontier) - i - 1)) - out.write("\n") + out.write("|\\") + + if (i+1 < len(frontier) and len(frontier[i+1]) == 1 + and frontier[i+1][0] in frontier[i]): + # We need to connect to the element to the right. + # Keep lines straight by connecting directly and + # avoiding immediate expand/contract. + name = frontier[i+1][0] + frontier[i].remove(name) + out.write("| " * (len(frontier) - i - 1)) + out.write("\n") - connect_deps(i, deps, label="expansion") - - # Handle any back edges to the right + else: + # Just allow the expansion here. + name = frontier[i].pop(0) + deps = [name] + out.write(" \\" * (len(frontier) - i - 1)) + out.write("\n") + connect_deps(i, deps, label="expansion") + + # Handle any remaining back edges to the right j = i+1 while j < len(frontier): deps = frontier.pop(j) -- cgit v1.2.3-70-g09d2 From dba5d020cdb7b4b306d68aff1a66430730c3b92b Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Tue, 30 Dec 2014 18:05:47 -0800 Subject: Pipelining back edges works, saves more space. --- lib/spack/spack/spec.py | 113 ++++++++++++++++++++++++++++++------------------ 1 file changed, 71 insertions(+), 42 deletions(-) (limited to 'lib') diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index a8d080b0d2..caa8b0972f 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -1349,57 +1349,71 @@ class Spec(object): return sorted((d for d in deps), reverse=True) - def back_edge(end, start, **kwargs): - assert(end < start) - collapse = kwargs.get('collapse', True) - label = kwargs.get('label', '') # debug label + def back_edge(prev_ends, end, start, collapse, label=None): + # Use prev & next for pipelining -- pipelined edges have + # the same start, and they're in sorted order e.g.:: + # + # start + # | |_|_|_|/| + # |/| | |_|/| + # | | |/| | | <-- when doing this line. + # prev end + # + out.write(indent) + f = len(frontier) - 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("|/") - if collapse: - out.write(" ") - out.write("/ " * (len(frontier) - start)) - else: - out.write("| " * (len(frontier) - start)) + def advance(to, fun): + for i in range(advance.pos, to): + fun() + advance.pos += 1 + advance.pos = 0 + + for p in prev_ends: + advance(p, lambda: out.write("| ")) + advance(p+1, lambda: out.write("|/")) - if debug: - out.write(" " * 20) - out.write("%s %s" % (frontier, label)) + if end >= 0: + advance(end + 1, lambda: out.write("| ")) + advance(start - 1, lambda: out.write("|_")) + else: + advance(start - 1, lambda: out.write("| ")) - out.write("\n") + if start >= 0: + advance(start, lambda: out.write("|/")) - # This part draws the final collapsing line - out.write(indent) - out.write("| " * end) - out.write("|/") - out.write("| " * (start - end - 1)) - if (start - end) > 1 or not collapse: - out.write("| " * (len(frontier) - start)) + if collapse: + advance(len(frontier), lambda: out.write(" /")) else: - out.write(" /" * (len(frontier) - start)) + advance(len(frontier), lambda: out.write("| ")) if debug: - out.write(" " * 20) - out.write("%s %s" % (frontier, label)) + out.write(" " * 10) + if label: out.write(label) + out.write("%s" % frontier) out.write("\n") - def connect_deps(i, deps, **kwargs): + def connect_deps(i, deps, collapse, label): + """Connect dependencies to frontier at position i.""" if len(deps) == 1 and deps in frontier: j = frontier.index(deps) + + # connect to the left if j < i: - back_edge(j, i, **kwargs) + if i-j > 1: # two lines if distance > 1 + back_edge([], j, i, True, label) + back_edge([j], -1, -1, (i-j == 1), label) + + # connect to the right else: if i < j: frontier.pop(j) frontier.insert(i, deps) - back_edge(i, j+1, **kwargs) + if j-i > 1: + back_edge([], i, j+1, collapse, label) + back_edge([i], -1, -1, not (j-i > 1) and collapse, label) return True elif deps: @@ -1408,8 +1422,10 @@ class Spec(object): def add_deps_to_frontier(node, i): + """Add dependencies to frontier, connecting them if they're fully + expanded, and deleting parent pointers.""" deps = ordered_deps(node) - connect_deps(i, deps, label="add_deps") + connect_deps(i, deps, True, "add_deps") for d in deps: del nodes[d].dependents[node.name] @@ -1432,13 +1448,26 @@ class Spec(object): # Expand frontier until there are enough columns for all children. if i >= 0: - # 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") + # Figure out how many back connections there are and + # sort them so we do them in order + back = [] + for d in frontier[i]: + b = find(frontier[:i], lambda f: f == [d]) + if b != -1: back.append((b, d)) + + # Do all back connections in sorted order so we can + # pipeline them and save space. + if back: + back.sort() + + prev_ends = [] + for j, (b, d) in enumerate(back): + if i-b > 1: + back_edge(prev_ends, b, i, False) + del prev_ends[:] + prev_ends.append(b) + frontier[i].remove(d) + back_edge(prev_ends, -1, -1, False) if not frontier[i]: frontier.pop(i) @@ -1465,7 +1494,7 @@ class Spec(object): deps = [name] out.write(" \\" * (len(frontier) - i - 1)) out.write("\n") - connect_deps(i, deps, label="expansion") + connect_deps(i, deps, True, "expansion") # Handle any remaining back edges to the right j = i+1 @@ -1474,7 +1503,7 @@ class Spec(object): # 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"): + if not connect_deps(j, deps, True, "rem_back"): j += 1 else: -- cgit v1.2.3-70-g09d2 From 478af54ccec497c58e408696dd8542ec9a8a82fb Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Wed, 31 Dec 2014 14:55:35 -0800 Subject: Color graph edges. --- lib/spack/spack/spec.py | 63 ++++++++++++++++++++++++++++++++----------------- 1 file changed, 42 insertions(+), 21 deletions(-) (limited to 'lib') diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index caa8b0972f..7aed82e239 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -1342,6 +1342,16 @@ class Spec(object): # Fast access to nodes in the spec. nodes = clone.index() + + # Colors associated with each node in the DAG. + # Edges are colored by the node they point to. + all_colors = 'rgbmcyRGBMCY' + colors = dict((name, all_colors[i % len(all_colors)]) + for i, name in enumerate(topo_order)) + def write_edge(string, index, sub=0): + edge = "@%s{%s}" % (colors[frontier[index][sub]], string) + out.write(edge) + frontier = [] def ordered_deps(node): @@ -1363,29 +1373,30 @@ class Spec(object): f = len(frontier) + self._pos = 0 def advance(to, fun): - for i in range(advance.pos, to): + for i in range(self._pos, to): fun() - advance.pos += 1 - advance.pos = 0 + self._pos += 1 for p in prev_ends: - advance(p, lambda: out.write("| ")) - advance(p+1, lambda: out.write("|/")) - + advance(p, lambda: write_edge("| ", self._pos)) + advance(p+1, lambda: write_edge("|/", self._pos)) if end >= 0: - advance(end + 1, lambda: out.write("| ")) - advance(start - 1, lambda: out.write("|_")) + advance(end + 1, lambda: write_edge("| ", self._pos)) + advance(start - 1, lambda: (write_edge("|", self._pos) or + write_edge("_", end))) else: - advance(start - 1, lambda: out.write("| ")) + advance(start - 1, lambda: write_edge("| ", self._pos)) if start >= 0: - advance(start, lambda: out.write("|/")) + advance(start, lambda: (write_edge("|", self._pos) or + write_edge("/", end))) if collapse: - advance(len(frontier), lambda: out.write(" /")) + advance(len(frontier), lambda: write_edge(" /", self._pos)) else: - advance(len(frontier), lambda: out.write("| ")) + advance(len(frontier), lambda: write_edge("| ", self._pos)) if debug: out.write(" " * 10) @@ -1462,11 +1473,11 @@ class Spec(object): prev_ends = [] for j, (b, d) in enumerate(back): + frontier[i].remove(d) if i-b > 1: back_edge(prev_ends, b, i, False) del prev_ends[:] prev_ends.append(b) - frontier[i].remove(d) back_edge(prev_ends, -1, -1, False) if not frontier[i]: @@ -1475,8 +1486,9 @@ class Spec(object): elif len(frontier[i]) > 1: # Expand forawrd after doing all back connections out.write(indent) - out.write("| " * i) - out.write("|\\") + for c in range(i): + write_edge("| ", c) + write_edge("|", i) if (i+1 < len(frontier) and len(frontier[i+1]) == 1 and frontier[i+1][0] in frontier[i]): @@ -1485,14 +1497,19 @@ class Spec(object): # avoiding immediate expand/contract. name = frontier[i+1][0] frontier[i].remove(name) - out.write("| " * (len(frontier) - i - 1)) + + write_edge("\\", i+1) + for c in range(i+1, len(frontier)): + write_edge("| ", c ) out.write("\n") else: # Just allow the expansion here. name = frontier[i].pop(0) deps = [name] - out.write(" \\" * (len(frontier) - i - 1)) + write_edge("\\", i) + for c in range(i+1, len(frontier)): + write_edge(" \\", c) out.write("\n") connect_deps(i, deps, True, "expansion") @@ -1518,17 +1535,21 @@ class Spec(object): frontier.pop(i) out.write(indent) - out.write("| " * i) + for c in range(i): + write_edge("| ", c) out.write("%s " % N) - out.write("| " * (len(frontier) - i)) + for c in range(i, len(frontier)): + write_edge("| ", c) out.write(" %s\n" % name) if node.dependencies: add_deps_to_frontier(node, i) elif frontier: out.write(indent) - out.write("| " * i) - out.write(" /" * (len(frontier) - i)) + for c in range(i): + write_edge("| ", c) + for c in range(i, len(frontier)): + write_edge(" /", c) out.write("\n") -- cgit v1.2.3-70-g09d2 From 0a0291678e283bf154081df67b0a1f5c909d1d19 Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Sat, 3 Jan 2015 17:45:54 -0800 Subject: Factor graph code out into its own module, rework spack graph. --- lib/spack/spack/cmd/graph.py | 32 ++- lib/spack/spack/cmd/location.py | 1 - lib/spack/spack/cmd/spec.py | 9 +- lib/spack/spack/graph.py | 480 ++++++++++++++++++++++++++++++++++++++++ lib/spack/spack/packages.py | 42 ---- lib/spack/spack/spec.py | 262 ---------------------- 6 files changed, 509 insertions(+), 317 deletions(-) create mode 100644 lib/spack/spack/graph.py (limited to 'lib') diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py index 955be51955..13efab5fe5 100644 --- a/lib/spack/spack/cmd/graph.py +++ b/lib/spack/spack/cmd/graph.py @@ -23,17 +23,39 @@ # Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA ############################################################################## from external import argparse + import spack import spack.cmd +from spack.graph import * -description = "Write out inter-package dependencies in dot graph format" +description = "Generate graphs of package dependency relationships." def setup_parser(subparser): + method = subparser.add_mutually_exclusive_group() + method.add_argument( + '--ascii', action='store_true', + help="Draw graph as ascii to stdout (default).") + method.add_argument( + '--dot', action='store_true', + help="Generate graph in dot format and print to stdout.") + + method.add_argument( + '--concretize', action='store_true', help="Concretize specs before graphing.") + subparser.add_argument( - 'specs', nargs=argparse.REMAINDER, - help="specs of packages to graph. Default is all packages.") + 'specs', nargs=argparse.REMAINDER, help="specs of packages to graph.") def graph(parser, args): - specs = spack.cmd.parse_specs(args.specs) - spack.db.graph_dependencies(*specs) + specs = spack.cmd.parse_specs( + args.specs, normalize=True, concretize=args.concretize) + + + if args.dot: # Dot graph only if asked for. + graph_dot(*specs) + + elif specs: # ascii is default: user doesn't need to provide it explicitly + graph_ascii(specs[0]) + for spec in specs[1:]: + print # extra line bt/w independent graphs + graph_ascii(spec) diff --git a/lib/spack/spack/cmd/location.py b/lib/spack/spack/cmd/location.py index 3fc05d471d..509c336b69 100644 --- a/lib/spack/spack/cmd/location.py +++ b/lib/spack/spack/cmd/location.py @@ -111,4 +111,3 @@ def location(parser, args): tty.die("Build directory does not exist yet. Run this to create it:", "spack stage " + " ".join(args.spec)) print pkg.stage.source_path - diff --git a/lib/spack/spack/cmd/spec.py b/lib/spack/spack/cmd/spec.py index 71bc12d6f5..e2cb5689c0 100644 --- a/lib/spack/spack/cmd/spec.py +++ b/lib/spack/spack/cmd/spec.py @@ -27,8 +27,8 @@ import spack.cmd import llnl.util.tty as tty -import spack.url as url import spack +import spack.url as url description = "print out abstract and concrete versions of a spec." @@ -44,14 +44,9 @@ def spec(parser, args): print "Normalized" print "------------------------------" spec.normalize() - print spec.tree(color=True, indent=2, cover='paths') + print spec.tree(color=True, indent=2) print "Concretized" print "------------------------------" spec.concretize() print spec.tree(color=True, indent=2) - - print "Graph" - print "------------------------------" - spec.graph() - return diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py new file mode 100644 index 0000000000..142c9c5c8f --- /dev/null +++ b/lib/spack/spack/graph.py @@ -0,0 +1,480 @@ +############################################################################## +# Copyright (c) 2013, Lawrence Livermore National Security, LLC. +# Produced at the Lawrence Livermore National Laboratory. +# +# This file is part of Spack. +# Written by Todd Gamblin, tgamblin@llnl.gov, All rights reserved. +# LLNL-CODE-647188 +# +# For details, see https://scalability-llnl.github.io/spack +# Please also see the LICENSE file for our notice and the LGPL. +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License (as published by +# the Free Software Foundation) version 2.1 dated February 1999. +# +# This program is distributed in the hope that it will be useful, but +# WITHOUT ANY WARRANTY; without even the IMPLIED WARRANTY OF +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the terms and +# conditions of the GNU General Public License for more details. +# +# You should have received a copy of the GNU Lesser General Public License +# along with this program; if not, write to the Free Software Foundation, +# Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +############################################################################## +"""Functions for graphing DAGs of dependencies. + +This file contains code for graphing DAGs of software packages +(i.e. Spack specs). There are two main functions you probably care +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". + +graph_dot() will output a graph of a spec (or multiple specs) in dot +format. + +Note that ``graph_ascii`` assumes a single spec while ``graph_dot`` +can take a number of specs as input. + +""" +__all__ = ['topological_sort', 'graph_ascii', 'AsciiGraph', 'graph_dot'] + +from heapq import * + +from llnl.util.lang import * +from llnl.util.tty.color import * + +import spack + + +def topological_sort(spec, **kwargs): + """Topological sort for specs. + + Return a list of dependency specs sorted topologically. The spec + argument is not modified in the process. + + """ + reverse = kwargs.get('reverse', False) + if not reverse: + parents = lambda s: s.dependents + children = lambda s: s.dependencies + else: + parents = lambda s: s.dependencies + children = lambda s: s.dependents + + # Work on a copy so this is nondestructive. + spec = spec.copy() + nodes = spec.index() + + topo_order = [] + remaining = [name for name in nodes.keys() if not parents(nodes[name])] + heapify(remaining) + + while remaining: + name = heappop(remaining) + topo_order.append(name) + + node = nodes[name] + for dep in children(node).values(): + del parents(dep)[node.name] + if not parents(dep): + heappush(remaining, dep.name) + + if any(parents(s) for s in spec.traverse()): + raise ValueError("Spec has cycles!") + else: + return topo_order + + +def find(seq, predicate): + """Find index in seq for which predicate is True. + + Searches the sequence and returns the index of the element for + which the predicate evaluates to True. Returns -1 if the + predicate does not evaluate to True for any element in seq. + + """ + for i, elt in enumerate(seq): + if predicate(elt): + return i + return -1 + + +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.debug = False + self.indent = 0 + + # These are colors in the order they'll be used for edges. + # See llnl.util.tty.color for details on color characters. + self.colors = 'rgbmcyRGBMCY' + + # Internal vars are used in the graph() function and are + # properly initialized there. + self._name_to_color = None # Node name to color + self._out = None # Output stream + self._frontier = None # frontier + self._nodes = None # dict from name -> node + + + def _indent(self): + self._out.write(self.indent * ' ') + + + def _write_edge(self, string, index, sub=0): + """Write a colored edge to the output stream.""" + name = self._frontier[index][sub] + edge = "@%s{%s}" % (self._name_to_color[name], string) + self._out.write(edge) + + + def _connect_deps(self, i, deps, collapse, label): + """Connect dependencies to existing edges in the frontier. + + ``deps`` are to be inserted at position i in the + frontier. This routine determines whether other open edges + should be merged with (if there are other open edges + pointing to the same place) or whether they should just be + inserted as a completely new open edge. + + Open edges that are not fully expanded (i.e. those that point + at multiple places) are left intact. + + 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 + (i.e. the frontier did not grow) and False if the deps were + NOT already in the frontier (i.e. they were inserted and the + frontier grew). + + """ + 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) + return True + + elif deps: + self._frontier.insert(i, deps) + 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 _back_edge(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. + For example, a single line edge:: + + | | | | o | + | | | |/ / <-- single-line edge connects two nodes. + | | | o | + + Or a multi-line edge (requires two calls to back_edge):: + + | | | | o | + | |_|_|/ / <-- multi-line edge crosses vertical edges. + |/| | | | + o | | | | + + Also handles "pipelined" edges, where the same line contains + parts of multiple edges:: + + o start + | |_|_|_|/| + |/| | |_|/| <-- this line has parts of 2 edges. + | | |/| | | + o o + + Arguments: + + prev_ends -- indices in frontier of previous edges that need + to be finished on this line. + + end -- end of the current edge on this line. + + start -- start index of the current edge. + + collapse -- whether the graph will be collapsing (i.e. whether + to slant the end of the line or keep it straight) + + label -- optional debug label to print after the line. + + """ + def advance(to_pos, edges): + """Write edges up to .""" + for i in range(self._pos, to_pos): + for e in edges(): + self._write_edge(*e) + self._pos += 1 + + flen = len(self._frontier) + self._pos = 0 + self._indent() + + for p in prev_ends: + advance(p, lambda: [("| ", self._pos)] ) + advance(p+1, lambda: [("|/", self._pos)] ) + + if end >= 0: + advance(end + 1, lambda: [("| ", self._pos)] ) + advance(start - 1, lambda: [("|", self._pos), ("_", end)] ) + else: + advance(start - 1, lambda: [("| ", self._pos)] ) + + if start >= 0: + advance(start, lambda: [("|", self._pos), ("/", end)] ) + + if collapse: + advance(flen, lambda: [(" /", self._pos)] ) + 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._out.write("\n") + + + def write(self, spec, **kwargs): + """Write out an ascii graph of the provided spec. + + Arguments: + spec -- spec to graph. This only handles one spec at a time. + + Optional arguments: + + out -- file object to write out to (default is sys.stdout) + + color -- whether to write in color. Default is to autodetect + based on output file. + + """ + out = kwargs.get('out', None) + if not out: + out = sys.stdout + + color = kwargs.get('color', None) + if not color: + color = out.isatty() + self._out = ColorStream(sys.stdout, color=color) + + # We'll traverse the spec in topo order as we graph it. + topo_order = topological_sort(spec, reverse=True) + + # Work on a copy to be nondestructive + spec = spec.copy() + self._nodes = spec.index() + + # Colors associated with each node in the DAG. + # Edges are colored by the node they point to. + 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() + + 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: + # 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)) + + # Do all back connections in sorted order so we can + # pipeline them and save space. + if back: + back.sort() + prev_ends = [] + for j, (b, d) in enumerate(back): + self._frontier[i].remove(d) + if i-b > 1: + self._back_edge(prev_ends, b, i, False) + del prev_ends[:] + prev_ends.append(b) + self._back_edge(prev_ends, -1, -1, False) + + 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) + + 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. + 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") + + 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") + + # 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"): + j += 1 + + else: + 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. + 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) + + if node.dependencies: + self._add_deps_to_frontier(node, i) + 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") + + +def graph_ascii(spec, **kwargs): + node_character = kwargs.get('node', 'o') + out = kwargs.pop('out', None) + debug = kwargs.pop('debug', False) + indent = kwargs.pop('indent', 0) + color = kwargs.pop('color', None) + check_kwargs(kwargs, graph_ascii) + + graph = AsciiGraph() + graph.debug = debug + graph.indent = indent + graph.node_character = node_character + + graph.write(spec, color=color, out=out) + + + +def graph_dot(*specs, **kwargs): + """Generate a graph in dot format of all provided specs. + + Print out a dot formatted graph of all the dependencies between + package. Output can be passed to graphviz, e.g.: + + spack graph --dot qt | dot -Tpdf > spack-graph.pdf + + """ + out = kwargs.pop('out', sys.stdout) + check_kwargs(kwargs, graph_dot) + + out.write('digraph G {\n') + out.write(' label = "Spack Dependencies"\n') + out.write(' labelloc = "b"\n') + out.write(' rankdir = "LR"\n') + out.write(' ranksep = "5"\n') + out.write('\n') + + def quote(string): + return '"%s"' % string + + if not specs: + packages = spack.db.all_packages() + else: + packages = [] + for spec in specs: + packages.extend(s.package for s in spec.normalized().traverse()) + + deps = [] + for pkg in packages: + out.write(' %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name)) + + # Add edges for each depends_on in the package. + for dep_name, dep in pkg.dependencies.iteritems(): + deps.append((pkg.name, dep_name)) + + # If the package provides something, add an edge for that. + for provider in set(p.name for p in pkg.provided): + deps.append((provider, pkg.name)) + + out.write('\n') + + for pair in deps: + out.write(' "%s" -> "%s"\n' % pair) + out.write('}\n') diff --git a/lib/spack/spack/packages.py b/lib/spack/spack/packages.py index 0aa8090b61..db43d3909a 100644 --- a/lib/spack/spack/packages.py +++ b/lib/spack/spack/packages.py @@ -214,48 +214,6 @@ class PackageDB(object): return cls - def graph_dependencies(self, *specs, **kwargs): - """Print out a graph of all the dependencies between package. - Graph is in dot format.""" - out = kwargs.pop('out', sys.stdout) - check_kwargs(kwargs, self.graph_dependencies) - - out.write('digraph G {\n') - out.write(' label = "Spack Dependencies"\n') - out.write(' labelloc = "b"\n') - out.write(' rankdir = "LR"\n') - out.write(' ranksep = "5"\n') - out.write('\n') - - def quote(string): - return '"%s"' % string - - if not specs: - packages = self.all_packages() - else: - packages = [] - for spec in specs: - packages.extend(s.package for s in spec.normalized().traverse()) - - deps = [] - for pkg in packages: - out.write(' %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name)) - - # Add edges for each depends_on in the package. - for dep_name, dep in pkg.dependencies.iteritems(): - deps.append((pkg.name, dep_name)) - - # If the package provides something, add an edge for that. - for provider in set(p.name for p in pkg.provided): - deps.append((provider, pkg.name)) - - out.write('\n') - - for pair in deps: - out.write(' "%s" -> "%s"\n' % pair) - out.write('}\n') - - class UnknownPackageError(spack.error.SpackError): """Raised when we encounter a package spack doesn't have.""" def __init__(self, name): diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index 7aed82e239..2f4fe9ca24 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -93,7 +93,6 @@ expansion when it is the first character in an id typed on the command line. import sys import itertools import hashlib -from heapq import * from StringIO import StringIO from operator import attrgetter @@ -1326,267 +1325,6 @@ class Spec(object): return out - def graph(self, **kwargs): - 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() - - # Colors associated with each node in the DAG. - # Edges are colored by the node they point to. - all_colors = 'rgbmcyRGBMCY' - colors = dict((name, all_colors[i % len(all_colors)]) - for i, name in enumerate(topo_order)) - def write_edge(string, index, sub=0): - edge = "@%s{%s}" % (colors[frontier[index][sub]], string) - out.write(edge) - - frontier = [] - - def ordered_deps(node): - deps = node.dependencies - return sorted((d for d in deps), reverse=True) - - - def back_edge(prev_ends, end, start, collapse, label=None): - # Use prev & next for pipelining -- pipelined edges have - # the same start, and they're in sorted order e.g.:: - # - # start - # | |_|_|_|/| - # |/| | |_|/| - # | | |/| | | <-- when doing this line. - # prev end - # - out.write(indent) - - f = len(frontier) - - self._pos = 0 - def advance(to, fun): - for i in range(self._pos, to): - fun() - self._pos += 1 - - for p in prev_ends: - advance(p, lambda: write_edge("| ", self._pos)) - advance(p+1, lambda: write_edge("|/", self._pos)) - if end >= 0: - advance(end + 1, lambda: write_edge("| ", self._pos)) - advance(start - 1, lambda: (write_edge("|", self._pos) or - write_edge("_", end))) - else: - advance(start - 1, lambda: write_edge("| ", self._pos)) - - if start >= 0: - advance(start, lambda: (write_edge("|", self._pos) or - write_edge("/", end))) - - if collapse: - advance(len(frontier), lambda: write_edge(" /", self._pos)) - else: - advance(len(frontier), lambda: write_edge("| ", self._pos)) - - if debug: - out.write(" " * 10) - if label: out.write(label) - out.write("%s" % frontier) - - out.write("\n") - - - def connect_deps(i, deps, collapse, label): - """Connect dependencies to frontier at position i.""" - if len(deps) == 1 and deps in frontier: - j = frontier.index(deps) - - # connect to the left - if j < i: - if i-j > 1: # two lines if distance > 1 - back_edge([], j, i, True, label) - back_edge([j], -1, -1, (i-j == 1), label) - - # connect to the right - else: - if i < j: - frontier.pop(j) - frontier.insert(i, deps) - if j-i > 1: - back_edge([], i, j+1, collapse, label) - back_edge([i], -1, -1, not (j-i > 1) and collapse, label) - return True - - elif deps: - frontier.insert(i, deps) - return False - - - def add_deps_to_frontier(node, i): - """Add dependencies to frontier, connecting them if they're fully - expanded, and deleting parent pointers.""" - deps = ordered_deps(node) - connect_deps(i, deps, True, "add_deps") - for d in deps: - del nodes[d].dependents[node.name] - - - def find(seq, predicate): - for i, elt in enumerate(seq): - if predicate(elt): - return i - return -1 - - - add_deps_to_frontier(self, 0) - out.write(indent) - out.write('%s %s\n' % (N, self.name)) - topo_order.pop() - - 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: - # Figure out how many back connections there are and - # sort them so we do them in order - back = [] - for d in frontier[i]: - b = find(frontier[:i], lambda f: f == [d]) - if b != -1: back.append((b, d)) - - # Do all back connections in sorted order so we can - # pipeline them and save space. - if back: - back.sort() - - prev_ends = [] - for j, (b, d) in enumerate(back): - frontier[i].remove(d) - if i-b > 1: - back_edge(prev_ends, b, i, False) - del prev_ends[:] - prev_ends.append(b) - back_edge(prev_ends, -1, -1, False) - - if not frontier[i]: - frontier.pop(i) - - elif len(frontier[i]) > 1: - # Expand forawrd after doing all back connections - out.write(indent) - for c in range(i): - write_edge("| ", c) - write_edge("|", i) - - if (i+1 < len(frontier) and len(frontier[i+1]) == 1 - and frontier[i+1][0] in frontier[i]): - # We need to connect to the element to the right. - # Keep lines straight by connecting directly and - # avoiding immediate expand/contract. - name = frontier[i+1][0] - frontier[i].remove(name) - - write_edge("\\", i+1) - for c in range(i+1, len(frontier)): - write_edge("| ", c ) - out.write("\n") - - else: - # Just allow the expansion here. - name = frontier[i].pop(0) - deps = [name] - write_edge("\\", i) - for c in range(i+1, len(frontier)): - write_edge(" \\", c) - out.write("\n") - connect_deps(i, deps, True, "expansion") - - # Handle any remaining 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, True, "rem_back"): - j += 1 - - else: - name = topo_order.pop() - node = 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. - i = find(frontier, lambda f: name in f) - frontier.pop(i) - - out.write(indent) - for c in range(i): - write_edge("| ", c) - out.write("%s " % N) - for c in range(i, len(frontier)): - write_edge("| ", c) - out.write(" %s\n" % name) - - if node.dependencies: - add_deps_to_frontier(node, i) - elif frontier: - out.write(indent) - for c in range(i): - write_edge("| ", c) - for c in range(i, len(frontier)): - write_edge(" /", c) - out.write("\n") - - - def topological_sort(self, **kwargs): - """Return a list of dependency specs sorted topologically. - This spec is not modified in the process.""" - reverse = kwargs.get('reverse', False) - if not reverse: - parents = lambda s: s.dependents - children = lambda s: s.dependencies - else: - parents = lambda s: s.dependencies - children = lambda s: s.dependents - - spec = self.copy() - nodes = spec.index() - - topo_order = [] - remaining = [name for name in nodes.keys() if not parents(nodes[name])] - heapify(remaining) - - while remaining: - name = heappop(remaining) - topo_order.append(name) - - node = nodes[name] - for dep in children(node).values(): - del parents(dep)[node.name] - if not parents(dep): - heappush(remaining, dep.name) - - if any(parents(s) for s in spec.traverse()): - raise ValueError("Spec has cycles!") - else: - return topo_order - - def __repr__(self): return str(self) -- cgit v1.2.3-70-g09d2 From b4b8339d0d13e508119813877559f33049eefbd1 Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Sat, 3 Jan 2015 17:58:37 -0800 Subject: bugfix for dot graphs of virtual packages. --- lib/spack/spack/cmd/graph.py | 2 +- lib/spack/spack/graph.py | 26 ++++++++++++++++---------- 2 files changed, 17 insertions(+), 11 deletions(-) (limited to 'lib') diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py index 13efab5fe5..58a411be71 100644 --- a/lib/spack/spack/cmd/graph.py +++ b/lib/spack/spack/cmd/graph.py @@ -39,7 +39,7 @@ def setup_parser(subparser): '--dot', action='store_true', help="Generate graph in dot format and print to stdout.") - method.add_argument( + subparser.add_argument( '--concretize', action='store_true', help="Concretize specs before graphing.") subparser.add_argument( diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py index 142c9c5c8f..08bd6f18bb 100644 --- a/lib/spack/spack/graph.py +++ b/lib/spack/spack/graph.py @@ -46,6 +46,7 @@ from llnl.util.lang import * from llnl.util.tty.color import * import spack +from spack.spec import Spec def topological_sort(spec, **kwargs): @@ -455,23 +456,28 @@ def graph_dot(*specs, **kwargs): return '"%s"' % string if not specs: - packages = spack.db.all_packages() + specs = [p.name for p in spack.db.all_packages()] else: - packages = [] - for spec in specs: - packages.extend(s.package for s in spec.normalized().traverse()) + roots = specs + specs = set() + for spec in roots: + specs.update(Spec(s.name) for s in spec.normalized().traverse()) deps = [] - for pkg in packages: - out.write(' %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name)) + for spec in specs: + out.write(' %-30s [label="%s"]\n' % (quote(spec.name), spec.name)) + + # Skip virtual specs (we'll find out about them from concrete ones. + if spec.virtual: + continue # Add edges for each depends_on in the package. - for dep_name, dep in pkg.dependencies.iteritems(): - deps.append((pkg.name, dep_name)) + for dep_name, dep in spec.package.dependencies.iteritems(): + deps.append((spec.name, dep_name)) # If the package provides something, add an edge for that. - for provider in set(p.name for p in pkg.provided): - deps.append((provider, pkg.name)) + for provider in set(s.name for s in spec.package.provided): + deps.append((provider, spec.name)) out.write('\n') -- cgit v1.2.3-70-g09d2 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(-) (limited to 'lib') 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 From 935eba23579af1d64e56fea38ab981846e127645 Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Mon, 5 Jan 2015 02:33:15 -0500 Subject: Allow commands to return error codes. --- bin/spack | 10 +++++++++- lib/spack/spack/cmd/graph.py | 5 +++++ lib/spack/spack/cmd/md5.py | 1 + 3 files changed, 15 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/bin/spack b/bin/spack index b345a5079d..626d9d9d11 100755 --- a/bin/spack +++ b/bin/spack @@ -103,7 +103,7 @@ if args.insecure: # Try to load the particular command asked for and run it command = spack.cmd.get_command(args.command) try: - command(parser, args) + return_val = command(parser, args) except SpackError, e: if spack.debug: # In debug mode, raise with a full stack trace. @@ -116,3 +116,11 @@ except SpackError, e: except KeyboardInterrupt: sys.stderr.write('\n') tty.die("Keyboard interrupt.") + +# Allow commands to return values if they want to exit with some ohter code. +if return_val is None: + sys.exit(0) +elif isinstance(return_val, int): + sys.exit(return_val) +else: + tty.die("Bad return value from command %s: %s" % (args.command, return_val)) diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py index f8cd18d91f..cb93a1b543 100644 --- a/lib/spack/spack/cmd/graph.py +++ b/lib/spack/spack/cmd/graph.py @@ -31,6 +31,8 @@ from spack.graph import * description = "Generate graphs of package dependency relationships." def setup_parser(subparser): + setup_parser.parser = subparser + method = subparser.add_mutually_exclusive_group() method.add_argument( '--ascii', action='store_true', @@ -50,6 +52,9 @@ def graph(parser, args): specs = spack.cmd.parse_specs( args.specs, normalize=True, concretize=args.concretize) + if not specs: + setup_parser.parser.print_help() + return 1 if args.dot: # Dot graph only if asked for. graph_dot(*specs) diff --git a/lib/spack/spack/cmd/md5.py b/lib/spack/spack/cmd/md5.py index 496835c64b..dfa1be412b 100644 --- a/lib/spack/spack/cmd/md5.py +++ b/lib/spack/spack/cmd/md5.py @@ -41,6 +41,7 @@ def setup_parser(subparser): def md5(parser, args): if not args.files: setup_parser.parser.print_help() + return 1 for f in args.files: if not os.path.isfile(f): -- cgit v1.2.3-70-g09d2 From 011f71a442deb8d78f0e55ef1e502e2d2426f48c Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Sat, 10 Jan 2015 19:09:03 -0800 Subject: Fix bug in STAT graph --- lib/spack/spack/graph.py | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-) (limited to 'lib') diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py index c4f5de1ebc..bebb68d06a 100644 --- a/lib/spack/spack/graph.py +++ b/lib/spack/spack/graph.py @@ -149,6 +149,7 @@ class AsciiGraph(object): self._frontier = None # frontier self._nodes = None # dict from name -> node self._prev_state = None # State of previous line + self._prev_index = None # Index of expansion point of prev line def _indent(self): @@ -195,15 +196,19 @@ class AsciiGraph(object): 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))) + # Special case where previous line expanded and i is off by 1. + self._back_edge_line([], j, i+1, True, label + "-1.5 " + str((i+1,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 + else: + # Previous node also expanded here, so i is off by one. + if self._prev_state == NODE and self._prev_index < i: + i += 1 + + if 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 @@ -213,10 +218,11 @@ class AsciiGraph(object): return False - def _set_state(self, state, label=None): + def _set_state(self, state, index, label=None): if state not in states: raise ValueError("Invalid graph state!") self._prev_state = state + self._prev_index = index if self.debug: self._out.write(" " * 20) @@ -296,7 +302,7 @@ class AsciiGraph(object): else: advance(flen, lambda: [("| ", self._pos)] ) - self._set_state(BACK_EDGE, label) + self._set_state(BACK_EDGE, end, label) self._out.write("\n") @@ -312,7 +318,7 @@ class AsciiGraph(object): self._write_edge("| ", c) self._out.write(" %s" % name) - self._set_state(NODE) + self._set_state(NODE, index) self._out.write("\n") @@ -324,7 +330,7 @@ class AsciiGraph(object): for c in range(index, len(self._frontier)): self._write_edge(" /", c) - self._set_state(COLLAPSE) + self._set_state(COLLAPSE, index) self._out.write("\n") @@ -338,7 +344,7 @@ class AsciiGraph(object): for c in range(index+1, len(self._frontier)): self._write_edge("| ", c ) - self._set_state(MERGE_RIGHT) + self._set_state(MERGE_RIGHT, index) self._out.write("\n") @@ -353,7 +359,7 @@ class AsciiGraph(object): for c in range(index+2, len(self._frontier)): self._write_edge(" \\", c) - self._set_state(EXPAND_RIGHT) + self._set_state(EXPAND_RIGHT, index) self._out.write("\n") -- cgit v1.2.3-70-g09d2 From 9db967be9827d44150a840f52ecd1e0f28b5bd4e Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Sat, 10 Jan 2015 19:23:07 -0800 Subject: Fix bug when all deps are back edges. - Happened with the graph for SAMRAI --- lib/spack/spack/graph.py | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py index bebb68d06a..5fb6a9cd23 100644 --- a/lib/spack/spack/graph.py +++ b/lib/spack/spack/graph.py @@ -426,10 +426,13 @@ class AsciiGraph(object): self._back_edge_line(prev_ends, b, i, False, 'left-1') del prev_ends[:] prev_ends.append(b) - self._back_edge_line(prev_ends, -1, -1, False, 'left-2') - if not self._frontier[i]: - self._frontier.pop(i) + # Check whether we did ALL the deps as back edges, + # in which case we're done. + collapse = not self._frontier[i] + if collapse: + self._frontier.pop(i) + self._back_edge_line(prev_ends, -1, -1, collapse, 'left-2') elif len(self._frontier[i]) > 1: # Expand forward after doing all back connections -- cgit v1.2.3-70-g09d2