summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTodd Gamblin <tgamblin@llnl.gov>2015-01-03 17:45:54 -0800
committerTodd Gamblin <tgamblin@llnl.gov>2015-01-03 17:45:54 -0800
commit0a0291678e283bf154081df67b0a1f5c909d1d19 (patch)
tree94ca39cbfefaacfb11d2396c5eae5b5a499abda9
parent478af54ccec497c58e408696dd8542ec9a8a82fb (diff)
downloadspack-0a0291678e283bf154081df67b0a1f5c909d1d19.tar.gz
spack-0a0291678e283bf154081df67b0a1f5c909d1d19.tar.bz2
spack-0a0291678e283bf154081df67b0a1f5c909d1d19.tar.xz
spack-0a0291678e283bf154081df67b0a1f5c909d1d19.zip
Factor graph code out into its own module, rework spack graph.
-rw-r--r--lib/spack/spack/cmd/graph.py32
-rw-r--r--lib/spack/spack/cmd/location.py1
-rw-r--r--lib/spack/spack/cmd/spec.py9
-rw-r--r--lib/spack/spack/graph.py480
-rw-r--r--lib/spack/spack/packages.py42
-rw-r--r--lib/spack/spack/spec.py262
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)