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(-) 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