diff options
| -rw-r--r-- | lib/spack/spack/cmd/graph.py | 32 | ||||
| -rw-r--r-- | lib/spack/spack/cmd/location.py | 1 | ||||
| -rw-r--r-- | lib/spack/spack/cmd/spec.py | 9 | ||||
| -rw-r--r-- | lib/spack/spack/graph.py | 480 | ||||
| -rw-r--r-- | lib/spack/spack/packages.py | 42 | ||||
| -rw-r--r-- | lib/spack/spack/spec.py | 262 |
6 files changed, 509 insertions, 317 deletions
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 <deps> (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 <node> 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 <to_pos>.""" + 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) |