From 3d961b9a1f129b1d1be98b4e50d6dafd7888097a Mon Sep 17 00:00:00 2001 From: Massimiliano Culpo Date: Tue, 27 Dec 2022 15:25:53 +0100 Subject: spack graph: rework to use Jinja templates and builders (#34637) `spack graph` has been reworked to use: - Jinja templates - builder objects to construct the template context when DOT graphs are requested. This allowed to add a new colored output for DOT graphs that highlights both the dependency types and the nodes that are needed at runtime for a given spec. --- lib/spack/docs/conf.py | 2 + lib/spack/spack/cmd/graph.py | 50 ++++-- lib/spack/spack/graph.py | 348 +++++++++++++++++++++--------------------- lib/spack/spack/test/graph.py | 32 +--- 4 files changed, 219 insertions(+), 213 deletions(-) (limited to 'lib') diff --git a/lib/spack/docs/conf.py b/lib/spack/docs/conf.py index cbac5a4f4d..fe6e081c7d 100644 --- a/lib/spack/docs/conf.py +++ b/lib/spack/docs/conf.py @@ -201,12 +201,14 @@ nitpick_ignore = [ ("py:class", "_frozen_importlib_external.SourceFileLoader"), ("py:class", "clingo.Control"), ("py:class", "six.moves.urllib.parse.ParseResult"), + ("py:class", "TextIO"), # Spack classes that are private and we don't want to expose ("py:class", "spack.provider_index._IndexBase"), ("py:class", "spack.repo._PrependFileLoader"), ("py:class", "spack.build_systems._checks.BaseBuilder"), # Spack classes that intersphinx is unable to resolve ("py:class", "spack.version.VersionBase"), + ("py:class", "spack.spec.DependencySpec"), ] # The reST default role (used for this markup: `text`) to use for all documents. diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py index a743f7258e..ca92776cf9 100644 --- a/lib/spack/spack/cmd/graph.py +++ b/lib/spack/spack/cmd/graph.py @@ -2,17 +2,20 @@ # Spack Project Developers. See the top-level COPYRIGHT file for details. # # SPDX-License-Identifier: (Apache-2.0 OR MIT) - -from __future__ import print_function - -import llnl.util.tty as tty +from llnl.util import tty import spack.cmd import spack.cmd.common.arguments as arguments import spack.config import spack.environment as ev import spack.store -from spack.graph import graph_ascii, graph_dot +from spack.graph import ( + DAGWithDependencyTypes, + SimpleDAG, + graph_ascii, + graph_dot, + static_graph_dot, +) description = "generate graphs of package dependency relationships" section = "basic" @@ -36,6 +39,12 @@ def setup_parser(subparser): action="store_true", help="graph static (possible) deps, don't concretize (implies --dot)", ) + subparser.add_argument( + "-c", + "--color", + action="store_true", + help="use different colors for different dependency types", + ) subparser.add_argument( "-i", @@ -48,11 +57,14 @@ def setup_parser(subparser): def graph(parser, args): + if args.installed and args.specs: + tty.die("cannot specify specs with --installed") + + if args.color and not args.dot: + tty.die("the --color option can be used only with --dot") + if args.installed: - if args.specs: - tty.die("Can't specify specs with --installed") args.dot = True - env = ev.active_environment() if env: specs = env.all_specs() @@ -68,13 +80,19 @@ def graph(parser, args): if args.static: args.dot = True + static_graph_dot(specs, deptype=args.deptype) + return if args.dot: - graph_dot(specs, static=args.static, deptype=args.deptype) - - elif specs: # ascii is default: user doesn't need to provide it explicitly - debug = spack.config.get("config:debug") - graph_ascii(specs[0], debug=debug, deptype=args.deptype) - for spec in specs[1:]: - print() # extra line bt/w independent graphs - graph_ascii(spec, debug=debug) + builder = SimpleDAG() + if args.color: + builder = DAGWithDependencyTypes() + graph_dot(specs, builder=builder, deptype=args.deptype) + return + + # ascii is default: user doesn't need to provide it explicitly + debug = spack.config.get("config:debug") + graph_ascii(specs[0], debug=debug, deptype=args.deptype) + for spec in specs[1:]: + print() # extra line bt/w independent graphs + graph_ascii(spec, debug=debug) diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py index 6c302544c4..481b699390 100644 --- a/lib/spack/spack/graph.py +++ b/lib/spack/spack/graph.py @@ -2,7 +2,6 @@ # Spack Project Developers. See the top-level COPYRIGHT file for details. # # SPDX-License-Identifier: (Apache-2.0 OR MIT) - r"""Functions for graphing DAGs of dependencies. This file contains code for graphing DAGs of software packages @@ -35,88 +34,17 @@ kind of like the graph git shows with "git log --graph", e.g.:: / o boost -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. - +graph_dot() will output a graph of a spec (or multiple specs) in dot format. """ -import heapq -import itertools +import enum import sys +from typing import List, Optional, Set, TextIO, Tuple, Union import llnl.util.tty.color import spack.dependency - -__all__ = ["graph_ascii", "AsciiGraph", "graph_dot"] - - -def node_label(spec): - return spec.format("{name}{@version}{/hash:7}") - - -def topological_sort(spec, deptype="all"): - """Return a list of dependency specs in topological sorting order. - - The spec argument is not modified in by the function. - - This function assumes specs don't have cycles, i.e. that we are really - operating with a DAG. - - Args: - spec (spack.spec.Spec): the spec to be analyzed - deptype (str or tuple): dependency types to account for when - constructing the list - """ - deptype = spack.dependency.canonical_deptype(deptype) - - # Work on a copy so this is nondestructive - spec = spec.copy(deps=True) - nodes = spec.index(deptype=deptype) - - def dependencies(specs): - """Return all the dependencies (including transitive) for a spec.""" - return list( - set(itertools.chain.from_iterable(s.dependencies(deptype=deptype) for s in specs)) - ) - - def dependents(specs): - """Return all the dependents (including those of transitive dependencies) - for a spec. - """ - candidates = list( - set(itertools.chain.from_iterable(s.dependents(deptype=deptype) for s in specs)) - ) - return [x for x in candidates if x.name in nodes] - - topological_order, children = [], {} - - # Map a spec encoded as (id, name) to a list of its transitive dependencies - for spec in itertools.chain.from_iterable(nodes.values()): - children[(id(spec), spec.name)] = [x for x in dependencies([spec]) if x.name in nodes] - - # To return a result that is topologically ordered we need to add nodes - # only after their dependencies. The first nodes we can add are leaf nodes, - # i.e. nodes that have no dependencies. - ready = [ - spec for spec in itertools.chain.from_iterable(nodes.values()) if not dependencies([spec]) - ] - heapq.heapify(ready) - - while ready: - # Pop a "ready" node and add it to the topologically ordered list - s = heapq.heappop(ready) - topological_order.append(s) - - # Check if adding the last node made other nodes "ready" - for dep in dependents([s]): - children[(id(dep), dep.name)].remove(s) - if not children[(id(dep), dep.name)]: - heapq.heappush(ready, dep) - - return topological_order +import spack.spec +import spack.tengine def find(seq, predicate): @@ -133,13 +61,17 @@ 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 _GraphLineState(enum.Enum): + """Names of different graph line states.""" + NODE = enum.auto() + COLLAPSE = enum.auto() + MERGE_RIGHT = enum.auto() + EXPAND_RIGHT = enum.auto() + BACK_EDGE = enum.auto() -class AsciiGraph(object): + +class AsciiGraph: def __init__(self): # These can be set after initialization or after a call to # graph() to change behavior. @@ -152,13 +84,13 @@ class AsciiGraph(object): # 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. + # Internal vars are used in the graph() function and are initialized there self._name_to_color = None # Node name to color self._out = None # Output stream self._frontier = None # frontier self._prev_state = None # State of previous line self._prev_index = None # Index of expansion point of prev line + self._pos = None def _indent(self): self._out.write(self.indent * " ") @@ -169,7 +101,7 @@ class AsciiGraph(object): if not self._frontier[index]: return name = self._frontier[index][sub] - edge = "@%s{%s}" % (self._name_to_color[name], string) + edge = f"@{self._name_to_color[name]}{{{string}}}" self._out.write(edge) def _connect_deps(self, i, deps, label=None): @@ -204,14 +136,14 @@ class AsciiGraph(object): return self._connect_deps(j, deps, label) collapse = True - if self._prev_state == EXPAND_RIGHT: + if self._prev_state == _GraphLineState.EXPAND_RIGHT: # 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 else: # Previous node also expanded here, so i is off by one. - if self._prev_state == NODE and self._prev_index < i: + if self._prev_state == _GraphLineState.NODE and self._prev_index < i: i += 1 if i - j > 1: @@ -222,21 +154,21 @@ class AsciiGraph(object): self._back_edge_line([j], -1, -1, collapse, label + "-2 " + str((i, j))) return True - elif deps: + if deps: self._frontier.insert(i, deps) return False + return False + 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) - 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) + self._out.write(f"{str(self._prev_state) if self._prev_state else '':<20}") + self._out.write(f"{str(label) if label else '':<20}") + self._out.write(f"{self._frontier}") def _back_edge_line(self, prev_ends, end, start, collapse, label=None): """Write part of a backwards edge in the graph. @@ -309,7 +241,7 @@ class AsciiGraph(object): else: advance(flen, lambda: [("| ", self._pos)]) - self._set_state(BACK_EDGE, end, label) + self._set_state(_GraphLineState.BACK_EDGE, end, label) self._out.write("\n") def _node_label(self, node): @@ -321,13 +253,13 @@ class AsciiGraph(object): for c in range(index): self._write_edge("| ", c) - self._out.write("%s " % self.node_character) + self._out.write(f"{self.node_character} ") for c in range(index + 1, len(self._frontier)): self._write_edge("| ", c) self._out.write(self._node_label(node)) - self._set_state(NODE, index) + self._set_state(_GraphLineState.NODE, index) self._out.write("\n") def _collapse_line(self, index): @@ -338,7 +270,7 @@ class AsciiGraph(object): for c in range(index, len(self._frontier)): self._write_edge(" /", c) - self._set_state(COLLAPSE, index) + self._set_state(_GraphLineState.COLLAPSE, index) self._out.write("\n") def _merge_right_line(self, index): @@ -351,7 +283,7 @@ class AsciiGraph(object): for c in range(index + 1, len(self._frontier)): self._write_edge("| ", c) - self._set_state(MERGE_RIGHT, index) + self._set_state(_GraphLineState.MERGE_RIGHT, index) self._out.write("\n") def _expand_right_line(self, index): @@ -365,7 +297,7 @@ class AsciiGraph(object): for c in range(index + 2, len(self._frontier)): self._write_edge(" \\", c) - self._set_state(EXPAND_RIGHT, index) + self._set_state(_GraphLineState.EXPAND_RIGHT, index) self._out.write("\n") def write(self, spec, color=None, out=None): @@ -391,7 +323,13 @@ class AsciiGraph(object): self._out = llnl.util.tty.color.ColorStream(out, color=color) # We'll traverse the spec in topological order as we graph it. - nodes_in_topological_order = topological_sort(spec, deptype=self.deptype) + nodes_in_topological_order = [ + edge.spec + for edge in spack.traverse.traverse_edges_topo( + [spec], direction="children", deptype=self.deptype + ) + ] + nodes_in_topological_order.reverse() # Work on a copy to be nondestructive spec = spec.copy() @@ -506,87 +444,153 @@ def graph_ascii(spec, node="o", out=None, debug=False, indent=0, color=None, dep graph.write(spec, color=color, out=out) -def graph_dot(specs, deptype="all", static=False, out=None): - """Generate a graph in dot format of all provided specs. +class DotGraphBuilder: + """Visit edges of a graph a build DOT options for nodes and edges""" + + def __init__(self): + self.nodes: Set[Tuple[str, str]] = set() + self.edges: Set[Tuple[str, str, str]] = set() + + def visit(self, edge: spack.spec.DependencySpec): + """Visit an edge and builds up entries to render the graph""" + if edge.parent is None: + self.nodes.add(self.node_entry(edge.spec)) + return + + self.nodes.add(self.node_entry(edge.parent)) + self.nodes.add(self.node_entry(edge.spec)) + self.edges.add(self.edge_entry(edge)) + + def node_entry(self, node: spack.spec.Spec) -> Tuple[str, str]: + """Return a tuple of (node_id, node_options)""" + raise NotImplementedError("Need to be implemented by derived classes") - Print out a dot formatted graph of all the dependencies between - package. Output can be passed to graphviz, e.g.: + def edge_entry(self, edge: spack.spec.DependencySpec) -> Tuple[str, str, str]: + """Return a tuple of (parent_id, child_id, edge_options)""" + raise NotImplementedError("Need to be implemented by derived classes") - .. code-block:: console + def context(self): + """Return the context to be used to render the DOT graph template""" + result = {"nodes": self.nodes, "edges": self.edges} + return result - spack graph --dot qt | dot -Tpdf > spack-graph.pdf + def render(self) -> str: + """Return a string with the output in DOT format""" + environment = spack.tengine.make_environment() + template = environment.get_template("misc/graph.dot") + return template.render(self.context()) + +class SimpleDAG(DotGraphBuilder): + """Simple DOT graph, with nodes colored uniformly and edges without properties""" + + def node_entry(self, node): + format_option = "{name}{@version}{%compiler}{/hash:7}" + return node.dag_hash(), f'[label="{node.format(format_option)}"]' + + def edge_entry(self, edge): + return edge.parent.dag_hash(), edge.spec.dag_hash(), None + + +class StaticDag(DotGraphBuilder): + """DOT graph for possible dependencies""" + + def node_entry(self, node): + return node.name, f'[label="{node.name}"]' + + def edge_entry(self, edge): + return edge.parent.name, edge.spec.name, None + + +class DAGWithDependencyTypes(DotGraphBuilder): + """DOT graph with link,run nodes grouped together and edges colored according to + the dependency types. + """ + + def __init__(self): + super().__init__() + self.main_unified_space: Set[str] = set() + + def visit(self, edge): + if edge.parent is None: + for node in spack.traverse.traverse_nodes([edge.spec], deptype=("link", "run")): + self.main_unified_space.add(node.dag_hash()) + super().visit(edge) + + def node_entry(self, node): + node_str = node.format("{name}{@version}{%compiler}{/hash:7}") + options = f'[label="{node_str}", group="build_dependencies", fillcolor="coral"]' + if node.dag_hash() in self.main_unified_space: + options = f'[label="{node_str}", group="main_psid"]' + return node.dag_hash(), options + + def edge_entry(self, edge): + colormap = {"build": "dodgerblue", "link": "crimson", "run": "goldenrod"} + return ( + edge.parent.dag_hash(), + edge.spec.dag_hash(), + f"[color=\"{':'.join(colormap[x] for x in edge.deptypes)}\"]", + ) + + +def _static_edges(specs, deptype): + for spec in specs: + pkg_cls = spack.repo.path.get_pkg_class(spec.name) + possible = pkg_cls.possible_dependencies(expand_virtuals=True, deptype=deptype) + + for parent_name, dependencies in possible.items(): + for dependency_name in dependencies: + yield spack.spec.DependencySpec( + spack.spec.Spec(parent_name), + spack.spec.Spec(dependency_name), + deptypes=deptype, + ) + + +def static_graph_dot( + specs: List[spack.spec.Spec], + deptype: Optional[Union[str, Tuple[str, ...]]] = "all", + out: Optional[TextIO] = None, +): + """Static DOT graph with edges to all possible dependencies. + + Args: + specs (list of spack.spec.Spec): abstract specs to be represented + deptype (str or tuple): dependency types to consider + out (TextIO or None): optional output stream. If None sys.stdout is used + """ + out = out or sys.stdout + builder = StaticDag() + for edge in _static_edges(specs, deptype): + builder.visit(edge) + out.write(builder.render()) + + +def graph_dot( + specs: List[spack.spec.Spec], + builder: Optional[DotGraphBuilder] = None, + deptype: Optional[Union[str, Tuple[str, ...]]] = "all", + out: Optional[TextIO] = None, +): + """DOT graph of the concrete specs passed as input. + + Args: + specs (list of spack.spec.Spec): specs to be represented + builder (DotGraphBuilder): builder to use to render the graph + deptype (str or tuple): dependency types to consider + out (TextIO or None): optional output stream. If None sys.stdout is used """ if not specs: raise ValueError("Must provide specs to graph_dot") if out is None: out = sys.stdout - deptype = spack.dependency.canonical_deptype(deptype) - def static_graph(spec, deptype): - pkg_cls = spack.repo.path.get_pkg_class(spec.name) - possible = pkg_cls.possible_dependencies(expand_virtuals=True, deptype=deptype) + deptype = spack.dependency.canonical_deptype(deptype) + builder = builder or SimpleDAG() + for edge in spack.traverse.traverse_edges( + specs, cover="edges", order="breadth", deptype=deptype + ): + builder.visit(edge) - nodes = set() # elements are (node name, node label) - edges = set() # elements are (src key, dest key) - for name, deps in possible.items(): - nodes.add((name, name)) - edges.update((name, d) for d in deps) - return nodes, edges - - def dynamic_graph(spec, deptypes): - nodes = set() # elements are (node key, node label) - edges = set() # elements are (src key, dest key) - for s in spec.traverse(deptype=deptype): - nodes.add((s.dag_hash(), node_label(s))) - for d in s.dependencies(deptype=deptype): - edge = (s.dag_hash(), d.dag_hash()) - edges.add(edge) - return nodes, edges - - nodes = set() - edges = set() - for spec in specs: - if static: - n, e = static_graph(spec, deptype) - else: - n, e = dynamic_graph(spec, deptype) - nodes.update(n) - edges.update(e) - - out.write("digraph G {\n") - out.write(' labelloc = "b"\n') - out.write(' rankdir = "TB"\n') - out.write(' ranksep = "1"\n') - out.write(" edge[\n") - out.write(" penwidth=4") - out.write(" ]\n") - out.write(" node[\n") - out.write(" fontname=Monaco,\n") - out.write(" penwidth=4,\n") - out.write(" fontsize=24,\n") - out.write(" margin=.2,\n") - out.write(" shape=box,\n") - out.write(" fillcolor=lightblue,\n") - out.write(' style="rounded,filled"') - out.write(" ]\n") - - # write nodes - out.write("\n") - for key, label in nodes: - out.write(' "%s" [label="%s"]\n' % (key, label)) - - # write edges - out.write("\n") - for src, dest in edges: - out.write(' "%s" -> "%s"\n' % (src, dest)) - - # ensure that roots are all at the top of the plot - dests = set([d for _, d in edges]) - roots = ['"%s"' % k for k, _ in nodes if k not in dests] - out.write("\n") - out.write(" { rank=min; %s; }" % "; ".join(roots)) - - out.write("\n") - out.write("}\n") + out.write(builder.render()) diff --git a/lib/spack/spack/test/graph.py b/lib/spack/spack/test/graph.py index b906548d7f..9163532ce9 100644 --- a/lib/spack/spack/test/graph.py +++ b/lib/spack/spack/test/graph.py @@ -12,21 +12,12 @@ import spack.repo import spack.spec -@pytest.mark.parametrize("spec_str", ["mpileaks", "callpath"]) -def test_topo_sort(spec_str, config, mock_packages): - """Ensure nodes are ordered topologically""" - s = spack.spec.Spec(spec_str).concretized() - nodes = spack.graph.topological_sort(s) - for idx, current in enumerate(nodes): - assert all(following not in current for following in nodes[idx + 1 :]) - - def test_static_graph_mpileaks(config, mock_packages): """Test a static spack graph for a simple package.""" s = spack.spec.Spec("mpileaks").normalized() stream = io.StringIO() - spack.graph.graph_dot([s], static=True, out=stream) + spack.graph.static_graph_dot([s], out=stream) dot = stream.getvalue() @@ -49,22 +40,21 @@ def test_static_graph_mpileaks(config, mock_packages): @pytest.mark.skipif(sys.platform == "win32", reason="Not supported on Windows (yet)") -def test_dynamic_dot_graph_mpileaks(mock_packages, config): +def test_dynamic_dot_graph_mpileaks(default_mock_concretization): """Test dynamically graphing the mpileaks package.""" - s = spack.spec.Spec("mpileaks").concretized() + s = default_mock_concretization("mpileaks") stream = io.StringIO() - spack.graph.graph_dot([s], static=False, out=stream) + spack.graph.graph_dot([s], out=stream) dot = stream.getvalue() nodes_to_check = ["mpileaks", "mpi", "callpath", "dyninst", "libdwarf", "libelf"] - hashes = {} + hashes, builder = {}, spack.graph.SimpleDAG() for name in nodes_to_check: current = s[name] current_hash = current.dag_hash() hashes[name] = current_hash - assert ( - ' "{0}" [label="{1}"]\n'.format(current_hash, spack.graph.node_label(current)) in dot - ) + node_options = builder.node_entry(current)[1] + assert node_options in dot dependencies_to_check = [ ("dyninst", "libdwarf"), @@ -117,11 +107,3 @@ o | libdwarf o libelf """ ) - - -def test_topological_sort_filtering_dependency_types(config, mock_packages): - s = spack.spec.Spec("both-link-and-build-dep-a").concretized() - - nodes = spack.graph.topological_sort(s, deptype=("link",)) - names = [s.name for s in nodes] - assert names == ["both-link-and-build-dep-c", "both-link-and-build-dep-a"] -- cgit v1.2.3-60-g2f50