diff options
-rw-r--r-- | lib/spack/llnl/util/lang.py | 9 | ||||
-rw-r--r-- | lib/spack/spack/cmd/deactivate.py | 9 | ||||
-rw-r--r-- | lib/spack/spack/database.py | 21 | ||||
-rw-r--r-- | lib/spack/spack/dependency.py | 2 | ||||
-rw-r--r-- | lib/spack/spack/graph.py | 147 | ||||
-rw-r--r-- | lib/spack/spack/installer.py | 5 | ||||
-rw-r--r-- | lib/spack/spack/solver/asp.py | 23 | ||||
-rw-r--r-- | lib/spack/spack/spec.py | 456 | ||||
-rw-r--r-- | lib/spack/spack/test/concretize.py | 51 | ||||
-rw-r--r-- | lib/spack/spack/test/conftest.py | 3 | ||||
-rw-r--r-- | lib/spack/spack/test/database.py | 33 | ||||
-rw-r--r-- | lib/spack/spack/test/graph.py | 151 | ||||
-rw-r--r-- | lib/spack/spack/test/spec_dag.py | 184 | ||||
-rw-r--r-- | var/spack/repos/builtin/packages/petsc/package.py | 3 |
14 files changed, 776 insertions, 321 deletions
diff --git a/lib/spack/llnl/util/lang.py b/lib/spack/llnl/util/lang.py index 69e0c886fb..92e3a5c341 100644 --- a/lib/spack/llnl/util/lang.py +++ b/lib/spack/llnl/util/lang.py @@ -967,3 +967,12 @@ def nullcontext(*args, **kwargs): class UnhashableArguments(TypeError): """Raise when an @memoized function receives unhashable arg or kwarg values.""" + + +def enum(**kwargs): + """Return an enum-like class. + + Args: + **kwargs: explicit dictionary of enums + """ + return type('Enum', (object,), kwargs) diff --git a/lib/spack/spack/cmd/deactivate.py b/lib/spack/spack/cmd/deactivate.py index 132ede0850..df3c13fdea 100644 --- a/lib/spack/spack/cmd/deactivate.py +++ b/lib/spack/spack/cmd/deactivate.py @@ -8,9 +8,9 @@ import llnl.util.tty as tty import spack.cmd import spack.cmd.common.arguments as arguments import spack.environment as ev +import spack.graph import spack.store from spack.filesystem_view import YamlFilesystemView -from spack.graph import topological_sort description = "deactivate a package extension" section = "extensions" @@ -68,11 +68,8 @@ def deactivate(parser, args): tty.msg("Deactivating %s and all dependencies." % pkg.spec.short_spec) - topo_order = topological_sort(spec) - index = spec.index() - - for name in topo_order: - espec = index[name] + nodes_in_topological_order = spack.graph.topological_sort(spec) + for espec in reversed(nodes_in_topological_order): epkg = espec.package if epkg.extends(pkg.extendee_spec): if epkg.is_activated(view) or args.force: diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py index 53b5ec2ab2..3c264c5b0e 100644 --- a/lib/spack/spack/database.py +++ b/lib/spack/spack/database.py @@ -961,7 +961,7 @@ class Database(object): counts = {} for key, rec in self._data.items(): counts.setdefault(key, 0) - for dep in rec.spec.dependencies(_tracked_deps): + for dep in rec.spec.dependencies(deptype=_tracked_deps): dep_key = dep.dag_hash() counts.setdefault(dep_key, 0) counts[dep_key] += 1 @@ -1078,7 +1078,7 @@ class Database(object): # Retrieve optional arguments installation_time = installation_time or _now() - for dep in spec.dependencies(_tracked_deps): + for dep in spec.dependencies(deptype=_tracked_deps): dkey = dep.dag_hash() if dkey not in self._data: extra_args = { @@ -1120,9 +1120,7 @@ class Database(object): ) # Connect dependencies from the DB to the new copy. - for name, dep in six.iteritems( - spec.dependencies_dict(_tracked_deps) - ): + for dep in spec.edges_to_dependencies(deptype=_tracked_deps): dkey = dep.spec.dag_hash() upstream, record = self.query_by_spec_hash(dkey) new_spec._add_dependency(record.spec, dep.deptypes) @@ -1185,7 +1183,7 @@ class Database(object): if rec.ref_count == 0 and not rec.installed: del self._data[key] - for dep in spec.dependencies(_tracked_deps): + for dep in spec.dependencies(deptype=_tracked_deps): self._decrement_ref_count(dep) def _increment_ref_count(self, spec): @@ -1213,13 +1211,10 @@ class Database(object): del self._data[key] - for dep in rec.spec.dependencies(_tracked_deps): - # FIXME: the two lines below needs to be updated once #11983 is - # FIXME: fixed. The "if" statement should be deleted and specs are - # FIXME: to be removed from dependents by hash and not by name. - # FIXME: See https://github.com/spack/spack/pull/15777#issuecomment-607818955 - if dep._dependents.get(spec.name): - del dep._dependents[spec.name] + # Remove any reference to this node from dependencies and + # decrement the reference count + rec.spec.detach(deptype=_tracked_deps) + for dep in rec.spec.dependencies(deptype=_tracked_deps): self._decrement_ref_count(dep) if rec.deprecated_for: diff --git a/lib/spack/spack/dependency.py b/lib/spack/spack/dependency.py index 0287672254..ca0da06665 100644 --- a/lib/spack/spack/dependency.py +++ b/lib/spack/spack/dependency.py @@ -58,7 +58,7 @@ def canonical_deptype(deptype): if bad: raise ValueError( 'Invalid dependency types: %s' % ','.join(str(t) for t in bad)) - return tuple(sorted(deptype)) + return tuple(sorted(set(deptype))) raise ValueError('Invalid dependency type: %s' % repr(deptype)) diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py index 38d8580ba0..8be490a74d 100644 --- a/lib/spack/spack/graph.py +++ b/lib/spack/spack/graph.py @@ -42,54 +42,84 @@ Note that ``graph_ascii`` assumes a single spec while ``graph_dot`` can take a number of specs as input. """ +import heapq +import itertools import sys -from heapq import heapify, heappop, heappush -from llnl.util.tty.color import ColorStream +import llnl.util.tty.color -from spack.dependency import all_deptypes, canonical_deptype +import spack.dependency -__all__ = ['topological_sort', 'graph_ascii', 'AsciiGraph', 'graph_dot'] +__all__ = ['graph_ascii', 'AsciiGraph', 'graph_dot'] -def topological_sort(spec, reverse=False, deptype='all'): - """Topological sort for specs. +def node_label(spec): + return spec.format('{name}{@version}{/hash:7}') - Return a list of dependency specs sorted topologically. The spec - argument is not modified in the process. - """ - deptype = canonical_deptype(deptype) - - # Work on a copy so this is nondestructive. - spec = spec.copy(deps=deptype) - nodes = spec.index(deptype=deptype) +def topological_sort(spec, deptype='all'): + """Return a list of dependency specs in topological sorting order. - parents = lambda s: [p for p in s.dependents() if p.name in nodes] - children = lambda s: s.dependencies() + The spec argument is not modified in by the function. - if reverse: - parents, children = children, parents + This function assumes specs don't have cycles, i.e. that we are really + operating with a DAG. - topo_order = [] - par = dict((name, parents(nodes[name])) for name in nodes.keys()) - remaining = [name for name in nodes.keys() if not parents(nodes[name])] - heapify(remaining) + 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) - while remaining: - name = heappop(remaining) - topo_order.append(name) + # Work on a copy so this is nondestructive + spec = spec.copy(deps=True) + nodes = spec.index(deptype=deptype) - node = nodes[name] - for dep in children(node): - par[dep.name].remove(node) - if not par[dep.name]: - heappush(remaining, dep.name) + 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 + ))) - if any(par.get(s.name, []) for s in spec.traverse()): - raise ValueError("Spec has cycles!") - else: - return topo_order + 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 def find(seq, predicate): @@ -120,7 +150,7 @@ class AsciiGraph(object): self.node_character = 'o' self.debug = False self.indent = 0 - self.deptype = all_deptypes + self.deptype = spack.dependency.all_deptypes # These are colors in the order they'll be used for edges. # See llnl.util.tty.color for details on color characters. @@ -131,7 +161,6 @@ class AsciiGraph(object): 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 self._prev_state = None # State of previous line self._prev_index = None # Index of expansion point of prev line @@ -290,7 +319,10 @@ class AsciiGraph(object): self._set_state(BACK_EDGE, end, label) self._out.write("\n") - def _node_line(self, index, name): + def _node_label(self, node): + return node.format('{name}@@{version}{/hash:7}') + + def _node_line(self, index, node): """Writes a line with a node at index.""" self._indent() for c in range(index): @@ -301,7 +333,7 @@ class AsciiGraph(object): for c in range(index + 1, len(self._frontier)): self._write_edge("| ", c) - self._out.write(" %s" % name) + self._out.write(self._node_label(node)) self._set_state(NODE, index) self._out.write("\n") @@ -363,29 +395,29 @@ class AsciiGraph(object): if color is None: color = out.isatty() - self._out = ColorStream(out, color=color) + self._out = llnl.util.tty.color.ColorStream(out, color=color) - # We'll traverse the spec in topo order as we graph it. - topo_order = topological_sort(spec, reverse=True, deptype=self.deptype) + # We'll traverse the spec in topological order as we graph it. + nodes_in_topological_order = topological_sort(spec, deptype=self.deptype) # 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)) + self._name_to_color = { + spec.full_hash(): self.colors[i % len(self.colors)] + for i, spec in enumerate(nodes_in_topological_order) + } # Frontier tracks open edges of the graph as it's written out. - self._frontier = [[spec.name]] + self._frontier = [[spec.full_hash()]] while self._frontier: # Find an unexpanded part of frontier i = find(self._frontier, lambda f: len(f) > 1) if i >= 0: - # Expand frontier until there are enough columns for all - # children. + # 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 @@ -436,8 +468,8 @@ class AsciiGraph(object): else: # Just allow the expansion here. - name = self._frontier[i].pop(0) - deps = [name] + dep_hash = self._frontier[i].pop(0) + deps = [dep_hash] self._frontier.insert(i, deps) self._expand_right_line(i) @@ -453,18 +485,17 @@ class AsciiGraph(object): else: # Nothing to expand; add dependencies for a node. - name = topo_order.pop() - node = self._nodes[name] + node = nodes_in_topological_order.pop() # Find the named node in the frontier and draw it. - i = find(self._frontier, lambda f: name in f) - self._node_line(i, name) + i = find(self._frontier, lambda f: node.full_hash() in f) + self._node_line(i, node) # Replace node with its dependencies self._frontier.pop(i) - deps = node.dependencies(self.deptype) + deps = node.dependencies(deptype=self.deptype) if deps: - deps = sorted((d.name for d in deps), reverse=True) + deps = sorted((d.full_hash() for d in deps), reverse=True) self._connect_deps(i, deps, "new-deps") # anywhere. elif self._frontier: @@ -478,7 +509,7 @@ def graph_ascii(spec, node='o', out=None, debug=False, graph.indent = indent graph.node_character = node if deptype: - graph.deptype = canonical_deptype(deptype) + graph.deptype = spack.dependency.canonical_deptype(deptype) graph.write(spec, color=color, out=out) @@ -499,7 +530,7 @@ def graph_dot(specs, deptype='all', static=False, out=None): if out is None: out = sys.stdout - deptype = canonical_deptype(deptype) + deptype = spack.dependency.canonical_deptype(deptype) def static_graph(spec, deptype): pkg = spec.package @@ -517,7 +548,7 @@ def graph_dot(specs, deptype='all', static=False, out=None): 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(), s.name)) + 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) diff --git a/lib/spack/spack/installer.py b/lib/spack/spack/installer.py index 41e29814e0..41de608fff 100644 --- a/lib/spack/spack/installer.py +++ b/lib/spack/spack/installer.py @@ -227,8 +227,9 @@ def _packages_needed_to_bootstrap_compiler(compiler, architecture, pkgs): dep.concretize() # mark compiler as depended-on by the packages that use it for pkg in pkgs: - dep._dependents[pkg.name] = spack.spec.DependencySpec( - pkg.spec, dep, ('build',)) + dep._dependents.add( + spack.spec.DependencySpec(pkg.spec, dep, ('build',)) + ) packages = [(s.package, False) for s in dep.traverse(order='post', root=False)] packages.append((dep.package, True)) diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py index 4650255271..89c9108fc1 100644 --- a/lib/spack/spack/solver/asp.py +++ b/lib/spack/spack/solver/asp.py @@ -1259,9 +1259,10 @@ class SpackSolverSetup(object): # add all clauses from dependencies if transitive: if spec.concrete: - for dep_name, dep in spec.dependencies_dict().items(): - for dtype in dep.deptypes: - clauses.append(fn.depends_on(spec.name, dep_name, dtype)) + # TODO: We need to distinguish 2 specs from the same package later + for edge in spec.edges_to_dependencies(): + for dtype in edge.deptypes: + clauses.append(fn.depends_on(spec.name, edge.spec.name, dtype)) for dep in spec.traverse(root=False): if spec.concrete: @@ -1907,12 +1908,18 @@ class SpecBuilder(object): ) def depends_on(self, pkg, dep, type): - dependency = self._specs[pkg]._dependencies.get(dep) - if not dependency: - self._specs[pkg]._add_dependency( - self._specs[dep], (type,)) + dependencies = self._specs[pkg].edges_to_dependencies(name=dep) + + # TODO: assertion to be removed when cross-compilation is handled correctly + msg = ("Current solver does not handle multiple dependency edges " + "of the same name") + assert len(dependencies) < 2, msg + + if not dependencies: + self._specs[pkg].add_dependency_edge(self._specs[dep], (type,)) else: - dependency.add_type(type) + # TODO: This assumes that each solve unifies dependencies + dependencies[0].add_type(type) def reorder_flags(self): """Order compiler flags on specs in predefined order. diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index ad7a460c4c..5fc8b69f07 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -667,7 +667,7 @@ class DependencySpec(object): def __init__(self, parent, spec, deptypes): self.parent = parent self.spec = spec - self.deptypes = tuple(sorted(set(deptypes))) + self.deptypes = dp.canonical_deptype(deptypes) def update_deptypes(self, deptypes): deptypes = set(deptypes) @@ -696,6 +696,9 @@ class DependencySpec(object): self.deptypes, self.spec.name if self.spec else None) + def canonical(self): + return self.parent.dag_hash(), self.spec.dag_hash(), self.deptypes + _valid_compiler_flags = [ 'cflags', 'cxxflags', 'fflags', 'ldflags', 'ldlibs', 'cppflags'] @@ -766,13 +769,119 @@ class FlagMap(lang.HashableMap): for key in sorted_keys) + cond_symbol -class DependencyMap(lang.HashableMap): - """Each spec has a DependencyMap containing specs for its dependencies. - The DependencyMap is keyed by name. """ +def _sort_by_dep_types(dspec): + # Use negation since False < True for sorting + return tuple(t not in dspec.deptypes for t in ("link", "run", "build", "test")) + + +#: Enum for edge directions +EdgeDirection = lang.enum(parent=0, child=1) + + +@lang.lazy_lexicographic_ordering +class _EdgeMap(Mapping): + """Represent a collection of edges (DependencySpec objects) in the DAG. + + Objects of this class are used in Specs to track edges that are + outgoing towards direct dependencies, or edges that are incoming + from direct dependents. + + Edges are stored in a dictionary and keyed by package name. + """ + def __init__(self, store_by=EdgeDirection.child): + # Sanitize input arguments + msg = 'unexpected value for "store_by" argument' + assert store_by in (EdgeDirection.child, EdgeDirection.parent), msg + + #: This dictionary maps a package name to a list of edges + #: i.e. to a list of DependencySpec objects + self.edges = {} + self.store_by_child = (store_by == EdgeDirection.child) + + def __getitem__(self, key): + return self.edges[key] + + def __iter__(self): + return iter(self.edges) + + def __len__(self): + return len(self.edges) + + def add(self, edge): + """Adds a new edge to this object. + + Args: + edge (DependencySpec): edge to be added + """ + key = edge.spec.name if self.store_by_child else edge.parent.name + current_list = self.edges.setdefault(key, []) + current_list.append(edge) + current_list.sort(key=_sort_by_dep_types) def __str__(self): return "{deps: %s}" % ', '.join(str(d) for d in sorted(self.values())) + def _cmp_iter(self): + for item in sorted(itertools.chain.from_iterable(self.edges.values())): + yield item + + def copy(self): + """Copies this object and returns a clone""" + clone = type(self)() + clone.store_by_child = self.store_by_child + + # Copy everything from this dict into it. + for dspec in itertools.chain.from_iterable(self.values()): + clone.add(dspec.copy()) + + return clone + + def select(self, parent=None, child=None, deptypes=dp.all_deptypes): + """Select a list of edges and return them. + + If an edge: + - Has *any* of the dependency types passed as argument, + - Matches the parent and/or child name, if passed + then it is selected. + + The deptypes argument needs to be canonical, since the method won't + convert it for performance reason. + + Args: + parent (str): name of the parent package + child (str): name of the child package + deptypes (tuple): allowed dependency types in canonical form + + Returns: + List of DependencySpec objects + """ + if not deptypes: + return [] + + # Start from all the edges we store + selected = (d for d in itertools.chain.from_iterable(self.values())) + + # Filter by parent name + if parent: + selected = (d for d in selected if d.parent.name == parent) + + # Filter by child name + if child: + selected = (d for d in selected if d.spec.name == child) + + # Filter by allowed dependency types + if deptypes: + selected = ( + dep for dep in selected + if not dep.deptypes or + any(d in deptypes for d in dep.deptypes) + ) + + return list(selected) + + def clear(self): + self.edges.clear() + def _command_default_handler(descriptor, spec, cls): """Default handler when looking for the 'command' attribute. @@ -1016,7 +1125,9 @@ class SpecBuildInterface(lang.ObjectWrapper): super(SpecBuildInterface, self).__init__(spec) # Adding new attributes goes after super() call since the ObjectWrapper # resets __dict__ to behave like the passed object - self.token = spec, name, query_parameters + original_spec = getattr(spec, 'wrapped_obj', spec) + self.wrapped_obj = original_spec + self.token = original_spec, name, query_parameters is_virtual = spack.repo.path.is_virtual(name) self.last_query = QueryState( name=name, @@ -1027,6 +1138,9 @@ class SpecBuildInterface(lang.ObjectWrapper): def __reduce__(self): return SpecBuildInterface, self.token + def copy(self, *args, **kwargs): + return self.wrapped_obj.copy(*args, **kwargs) + @lang.lazy_lexicographic_ordering(set_hash=False) class Spec(object): @@ -1070,8 +1184,8 @@ class Spec(object): self.architecture = None self.compiler = None self.compiler_flags = FlagMap(self) - self._dependents = DependencyMap() - self._dependencies = DependencyMap() + self._dependents = _EdgeMap(store_by=EdgeDirection.parent) + self._dependencies = _EdgeMap(store_by=EdgeDirection.child) self.namespace = None self._hash = None @@ -1143,34 +1257,112 @@ class Spec(object): def external(self): return bool(self.external_path) or bool(self.external_modules) - def get_dependency(self, name): - dep = self._dependencies.get(name) - if dep is not None: - return dep - raise InvalidDependencyError(self.name, name) + def clear_dependencies(self): + """Trim the dependencies of this spec.""" + self._dependencies.clear() + + def clear_edges(self): + """Trim the dependencies and dependents of this spec.""" + self._dependencies.clear() + self._dependents.clear() + + def detach(self, deptype='all'): + """Remove any reference that dependencies have of this node. - def _find_deps(self, where, deptype): + Args: + deptype (str or tuple): dependency types tracked by the + current spec + """ + key = self.dag_hash() + # Go through the dependencies + for dep in self.dependencies(deptype=deptype): + # Remove the spec from dependents + if self.name in dep._dependents: + dependents_copy = dep._dependents.edges[self.name] + del dep._dependents.edges[self.name] + for edge in dependents_copy: + if edge.parent.dag_hash() == key: + continue + dep._dependents.add(edge) + + def _get_dependency(self, name): + # WARNING: This function is an implementation detail of the + # WARNING: original concretizer. Since with that greedy + # WARNING: algorithm we don't allow multiple nodes from + # WARNING: the same package in a DAG, here we hard-code + # WARNING: using index 0 i.e. we assume that we have only + # WARNING: one edge from package "name" + deps = self.edges_to_dependencies(name=name) + if len(deps) != 1: + err_msg = 'expected only 1 "{0}" dependency, but got {1}' + raise spack.error.SpecError(err_msg.format(name, len(deps))) + return deps[0] + + def edges_from_dependents(self, name=None, deptype='all'): + """Return a list of edges connecting this node in the DAG + to parents. + + Args: + name (str): filter dependents by package name + deptype (str or tuple): allowed dependency types + """ + deptype = dp.canonical_deptype(deptype) + return [ + d for d in + self._dependents.select(parent=name, deptypes=deptype) + ] + + def edges_to_dependencies(self, name=None, deptype='all'): + """Return a list of edges connecting this node in the DAG + to children. + + Args: + name (str): filter dependencies by package name + deptype (str or tuple): allowed dependency types + """ deptype = dp.canonical_deptype(deptype) + return [ + d for d in + self._dependencies.select(child=name, deptypes=deptype) + ] - return [dep for dep in where.values() - if deptype and (not dep.deptypes or - any(d in deptype for d in dep.deptypes))] + def dependencies(self, name=None, deptype='all'): + """Return a list of direct dependencies (nodes in the DAG). - def dependencies(self, deptype='all'): - return [d.spec - for d in self._find_deps(self._dependencies, deptype)] + Args: + name (str): filter dependencies by package name + deptype (str or tuple): allowed dependency types + """ + return [d.spec for d in self.edges_to_dependencies(name, deptype=deptype)] + + def dependents(self, name=None, deptype='all'): + """Return a list of direct dependents (nodes in the DAG). - def dependents(self, deptype='all'): - return [d.parent - for d in self._find_deps(self._dependents, deptype)] + Args: + name (str): filter dependents by package name + deptype (str or tuple): allowed dependency types + """ + return [d.parent for d in self.edges_from_dependents(name, deptype=deptype)] - def dependencies_dict(self, deptype='all'): - return dict((d.spec.name, d) - for d in self._find_deps(self._dependencies, deptype)) + def _dependencies_dict(self, deptype='all'): + """Return a dictionary, keyed by package name, of the direct + dependencies. - def dependents_dict(self, deptype='all'): - return dict((d.parent.name, d) - for d in self._find_deps(self._dependents, deptype)) + Each value in the dictionary is a list of edges. + + Args: + deptype: allowed dependency types + """ + _sort_fn = lambda x: (x.spec.name,) + _sort_by_dep_types(x) + _group_fn = lambda x: x.spec.name + deptype = dp.canonical_deptype(deptype) + selected_edges = self._dependencies.select(deptypes=deptype) + result = {} + for key, group in itertools.groupby( + sorted(selected_edges, key=_sort_fn), key=_group_fn + ): + result[key] = list(group) + return result # # Private routines here are called by the parser when building a spec. @@ -1248,18 +1440,43 @@ class Spec(object): raise DuplicateDependencyError( "Cannot depend on '%s' twice" % spec) - # create an edge and add to parent and child - dspec = DependencySpec(self, spec, deptypes) - self._dependencies[spec.name] = dspec - spec._dependents[self.name] = dspec + self.add_dependency_edge(spec, deptypes) + + def add_dependency_edge(self, dependency_spec, deptype): + """Add a dependency edge to this spec. + + Args: + dependency_spec (Spec): spec of the dependency + deptype (str or tuple): dependency types + """ + deptype = dp.canonical_deptype(deptype) + + # Check if we need to update edges that are already present + selected = self._dependencies.select(child=dependency_spec.name) + for edge in selected: + if any(d in edge.deptypes for d in deptype): + msg = ('cannot add a dependency on "{0.spec}" of {1} type ' + 'when the "{0.parent}" has the edge {0!s} already') + raise spack.error.SpecError(msg.format(edge, deptype)) + + for edge in selected: + if id(dependency_spec) == id(edge.spec): + # If we are here, it means the edge object was previously added to + # both the parent and the child. When we update this object they'll + # both see the deptype modification. + edge.add_type(deptype) + return + + edge = DependencySpec(self, dependency_spec, deptype) + self._dependencies.add(edge) + dependency_spec._dependents.add(edge) def _add_default_platform(self): """If a spec has an os or a target and no platform, give it - the default platform. - - This is private because it is used by the parser -- it's not - expected to be used outside of ``spec.py``. + the default platform. + This is private because it is used by the parser -- it's not + expected to be used outside of ``spec.py``. """ arch = self.architecture if arch and not arch.platform and (arch.os or arch.target): @@ -1280,10 +1497,12 @@ class Spec(object): Spack specs have a single root (the package being installed). """ + # FIXME: In the case of multiple parents this property does not + # FIXME: make sense. Should we revisit the semantics? if not self._dependents: return self - - return next(iter(self._dependents.values())).parent.root + edges_by_package = next(iter(self._dependents.values())) + return edges_by_package[0].parent.root @property def package(self): @@ -1448,21 +1667,24 @@ class Spec(object): # This code determines direction and yields the children/parents if direction == 'children': - where = self._dependencies + edges = self.edges_to_dependencies + key_fn = lambda dspec: dspec.spec.name succ = lambda dspec: dspec.spec elif direction == 'parents': - where = self._dependents + edges = self.edges_from_dependents + key_fn = lambda dspec: dspec.parent.name succ = lambda dspec: dspec.parent else: raise ValueError('Invalid traversal direction: %s' % direction) - for name, dspec in sorted(where.items()): + for dspec in sorted(edges(), key=key_fn): dt = dspec.deptypes if dt and not any(d in deptype for d in dt): continue for child in succ(dspec).traverse_edges( - visited, d + 1, deptype, dspec, **kwargs): + visited, d + 1, deptype, dspec, **kwargs + ): yield child # Postorder traversal yields after successors @@ -1684,17 +1906,17 @@ class Spec(object): d['package_hash'] = package_hash # Note: Relies on sorting dict by keys later in algorithm. - deps = self.dependencies_dict(deptype=hash.deptype) - + deps = self._dependencies_dict(deptype=hash.deptype) if deps: deps_list = [] - for name, dspec in sorted(deps.items()): + for name, edges_for_name in sorted(deps.items()): name_tuple = ('name', name) - hash_tuple = (hash.name, dspec.spec._cached_hash(hash)) - type_tuple = ('type', sorted(str(s) for s in dspec.deptypes)) - deps_list.append(syaml.syaml_dict([name_tuple, - hash_tuple, - type_tuple])) + for dspec in edges_for_name: + hash_tuple = (hash.name, dspec.spec._cached_hash(hash)) + type_tuple = ('type', sorted(str(s) for s in dspec.deptypes)) + deps_list.append(syaml.syaml_dict( + [name_tuple, hash_tuple, type_tuple] + )) d['dependencies'] = deps_list # Name is included in case this is replacing a virtual. @@ -2257,8 +2479,14 @@ class Spec(object): changed = False # Concretize deps first -- this is a bottom-up process. - for name in sorted(self._dependencies.keys()): - changed |= self._dependencies[name].spec._concretize_helper( + for name in sorted(self._dependencies): + # WARNING: This function is an implementation detail of the + # WARNING: original concretizer. Since with that greedy + # WARNING: algorithm we don't allow multiple nodes from + # WARNING: the same package in a DAG, here we hard-code + # WARNING: using index 0 i.e. we assume that we have only + # WARNING: one edge from package "name" + changed |= self._dependencies[name][0].spec._concretize_helper( concretizer, presets, visited ) @@ -2285,14 +2513,14 @@ class Spec(object): def _replace_with(self, concrete): """Replace this virtual spec with a concrete spec.""" - assert(self.virtual) - for name, dep_spec in self._dependents.items(): + assert self.virtual + for dep_spec in itertools.chain.from_iterable(self._dependents.values()): dependent = dep_spec.parent deptypes = dep_spec.deptypes # remove self from all dependents, unless it is already removed if self.name in dependent._dependencies: - del dependent._dependencies[self.name] + del dependent._dependencies.edges[self.name] # add the replacement, unless it is already a dep of dependent. if concrete.name not in dependent._dependencies: @@ -2363,12 +2591,12 @@ class Spec(object): # If replacement is external then trim the dependencies if replacement.external: - if (spec._dependencies): + if spec._dependencies: for dep in spec.dependencies(): - del dep._dependents[spec.name] + del dep._dependents.edges[spec.name] changed = True - spec._dependencies = DependencyMap() - replacement._dependencies = DependencyMap() + spec.clear_dependencies() + replacement.clear_dependencies() replacement.architecture = self.architecture # TODO: could this and the stuff in _dup be cleaned up? @@ -2715,9 +2943,8 @@ class Spec(object): if not copy: for spec in flat_deps.values(): if not spec.concrete: - spec._dependencies.clear() - spec._dependents.clear() - self._dependencies.clear() + spec.clear_edges() + self.clear_dependencies() return flat_deps @@ -2732,11 +2959,12 @@ class Spec(object): ) def index(self, deptype='all'): - """Return DependencyMap that points to all the dependencies in this - spec.""" - dm = DependencyMap() + """Return a dictionary that points to all the dependencies in this + spec. + """ + dm = collections.defaultdict(list) for spec in self.traverse(deptype=deptype): - dm[spec.name] = spec + dm[spec.name].append(spec) return dm def _evaluate_dependency_conditions(self, name): @@ -3222,12 +3450,19 @@ class Spec(object): for name in self.common_dependencies(other): changed |= self[name].constrain(other[name], deps=False) if name in self._dependencies: - changed |= self._dependencies[name].update_deptypes( - other._dependencies[name].deptypes) + # WARNING: This function is an implementation detail of the + # WARNING: original concretizer. Since with that greedy + # WARNING: algorithm we don't allow multiple nodes from + # WARNING: the same package in a DAG, here we hard-code + # WARNING: using index 0 i.e. we assume that we have only + # WARNING: one edge from package "name" + edges_from_name = self._dependencies[name] + changed |= edges_from_name[0].update_deptypes( + other._dependencies[name][0].deptypes) # Update with additional constraints from other spec for name in other.dep_difference(self): - dep_spec_copy = other.get_dependency(name) + dep_spec_copy = other._get_dependency(name) dep_copy = dep_spec_copy.spec deptypes = dep_spec_copy.deptypes self._add_dependency(dep_copy.copy(), deptypes) @@ -3490,8 +3725,8 @@ class Spec(object): else None self.compiler = other.compiler.copy() if other.compiler else None if cleardeps: - self._dependents = DependencyMap() - self._dependencies = DependencyMap() + self._dependents = _EdgeMap(store_by=EdgeDirection.parent) + self._dependencies = _EdgeMap(store_by=EdgeDirection.child) self.compiler_flags = other.compiler_flags.copy() self.compiler_flags.spec = self self.variants = other.variants.copy() @@ -3547,22 +3782,25 @@ class Spec(object): return changed def _dup_deps(self, other, deptypes, caches): - new_specs = {self.name: self} - for dspec in other.traverse_edges(cover='edges', - root=False): - if (dspec.deptypes and - not any(d in deptypes for d in dspec.deptypes)): + def spid(spec): + return id(spec) + + new_specs = {spid(other): self} + for edge in other.traverse_edges(cover='edges', root=False): + if edge.deptypes and not any(d in deptypes for d in edge.deptypes): continue - if dspec.parent.name not in new_specs: - new_specs[dspec.parent.name] = dspec.parent.copy( - deps=False, caches=caches) - if dspec.spec.name not in new_specs: - new_specs[dspec.spec.name] = dspec.spec.copy( - deps=False, caches=caches) + if spid(edge.parent) not in new_specs: + new_specs[spid(edge.parent)] = edge.parent.copy( + deps=False, caches=caches + ) + + if spid(edge.spec) not in new_specs: + new_specs[spid(edge.spec)] = edge.spec.copy(deps=False, caches=caches) - new_specs[dspec.parent.name]._add_dependency( - new_specs[dspec.spec.name], dspec.deptypes) + new_specs[spid(edge.parent)].add_dependency_edge( + new_specs[spid(edge.spec)], edge.deptypes + ) def copy(self, deps=True, **kwargs): """Make a copy of this spec. @@ -3679,8 +3917,10 @@ class Spec(object): for name in sorted(self._dependencies)] osorted = [other._dependencies[name] for name in sorted(other._dependencies)] - - for s_dspec, o_dspec in zip(ssorted, osorted): + for s_dspec, o_dspec in zip( + itertools.chain.from_iterable(ssorted), + itertools.chain.from_iterable(osorted) + ): if deptypes and s_dspec.deptypes != o_dspec.deptypes: return False @@ -3724,7 +3964,9 @@ class Spec(object): yield item def deps(): - for _, dep in sorted(self._dependencies.items()): + for dep in sorted( + itertools.chain.from_iterable(self._dependencies.values()) + ): yield dep.spec.name yield tuple(sorted(dep.deptypes)) yield hash(dep.spec) @@ -4302,7 +4544,8 @@ class Spec(object): # when only covering nodes, we merge dependency types # from all dependents before showing them. types = [ - ds.deptypes for ds in node.dependents_dict().values()] + ds.deptypes for ds in node.edges_from_dependents() + ] else: # when covering edges or paths, we show dependency # types only for the edge through which we visited @@ -4373,6 +4616,18 @@ class Spec(object): assert other.concrete assert other.name in self + # Check, for the time being, that we don't have DAG with multiple + # specs from the same package + def multiple_specs(root): + counter = collections.Counter([node.name for node in root.traverse()]) + _, max_number = counter.most_common()[0] + return max_number > 1 + + if multiple_specs(self) or multiple_specs(other): + msg = ('Either "{0}" or "{1}" contain multiple specs from the same ' + 'package, which cannot be handled by splicing at the moment') + raise ValueError(msg.format(self, other)) + # Multiple unique specs with the same name will collide, so the # _dependents of these specs should not be trusted. # Variants may also be ignored here for now... @@ -4398,19 +4653,22 @@ class Spec(object): nodes.update(self_nodes) for name in nodes: + # TODO: check if splice semantics is respected if name in self_nodes: - dependencies = self[name]._dependencies - for dep in dependencies: - nodes[name]._add_dependency(nodes[dep], - dependencies[dep].deptypes) - if any(dep not in self_nodes for dep in dependencies): + for edge in self[name].edges_to_dependencies(): + nodes[name].add_dependency_edge( + nodes[edge.spec.name], edge.deptypes + ) + if any(dep not in self_nodes + for dep in self[name]._dependencies): nodes[name].build_spec = self[name].build_spec else: - dependencies = other[name]._dependencies - for dep in dependencies: - nodes[name]._add_dependency(nodes[dep], - dependencies[dep].deptypes) - if any(dep not in other_nodes for dep in dependencies): + for edge in other[name].edges_to_dependencies(): + nodes[name].add_dependency_edge( + nodes[edge.spec.name], edge.deptypes + ) + if any(dep not in other_nodes + for dep in other[name]._dependencies): nodes[name].build_spec = other[name].build_spec ret = nodes[self.name] @@ -4491,7 +4749,7 @@ def merge_abstract_anonymous_specs(*abstract_specs): # Update with additional constraints from other spec for name in current_spec_constraint.dep_difference(merged_spec): - edge = current_spec_constraint.get_dependency(name) + edge = next(iter(current_spec_constraint.edges_to_dependencies(name))) merged_spec._add_dependency(edge.spec.copy(), edge.deptypes) return merged_spec diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py index fc24a1d972..a5eecd6f8c 100644 --- a/lib/spack/spack/test/concretize.py +++ b/lib/spack/spack/test/concretize.py @@ -176,13 +176,17 @@ class TestConcretize(object): def test_concretize_mention_build_dep(self): spec = check_concretize('cmake-client ^cmake@3.4.3') + # Check parent's perspective of child - dependency = spec.dependencies_dict()['cmake'] - assert set(dependency.deptypes) == set(['build']) + to_dependencies = spec.edges_to_dependencies(name='cmake') + assert len(to_dependencies) == 1 + assert set(to_dependencies[0].deptypes) == set(['build']) + # Check child's perspective of parent cmake = spec['cmake'] - dependent = cmake.dependents_dict()['cmake-client'] - assert set(dependent.deptypes) == set(['build']) + from_dependents = cmake.edges_from_dependents(name='cmake-client') + assert len(from_dependents) == 1 + assert set(from_dependents[0].deptypes) == set(['build']) def test_concretize_preferred_version(self): spec = check_concretize('python') @@ -379,30 +383,37 @@ class TestConcretize(object): def test_virtual_is_fully_expanded_for_callpath(self): # force dependence on fake "zmpi" by asking for MPI 10.0 spec = Spec('callpath ^mpi@10.0') - assert 'mpi' in spec._dependencies + assert len(spec.dependencies(name='mpi')) == 1 assert 'fake' not in spec + spec.concretize() - assert 'zmpi' in spec._dependencies - assert all('mpi' not in d._dependencies for d in spec.traverse()) - assert 'zmpi' in spec - assert 'mpi' in spec - assert 'fake' in spec._dependencies['zmpi'].spec + assert len(spec.dependencies(name='zmpi')) == 1 + assert all(not d.dependencies(name='mpi') for d in spec.traverse()) + assert all(x in spec for x in ('zmpi', 'mpi')) + + edges_to_zmpi = spec.edges_to_dependencies(name='zmpi') + assert len(edges_to_zmpi) == 1 + assert 'fake' in edges_to_zmpi[0].spec def test_virtual_is_fully_expanded_for_mpileaks( self ): spec = Spec('mpileaks ^mpi@10.0') - assert 'mpi' in spec._dependencies + assert len(spec.dependencies(name='mpi')) == 1 assert 'fake' not in spec + spec.concretize() - assert 'zmpi' in spec._dependencies - assert 'callpath' in spec._dependencies - assert 'zmpi' in spec._dependencies['callpath'].spec._dependencies - assert 'fake' in spec._dependencies['callpath'].spec._dependencies[ - 'zmpi'].spec._dependencies # NOQA: ignore=E501 - assert all('mpi' not in d._dependencies for d in spec.traverse()) - assert 'zmpi' in spec - assert 'mpi' in spec + assert len(spec.dependencies(name='zmpi')) == 1 + assert len(spec.dependencies(name='callpath')) == 1 + + callpath = spec.dependencies(name='callpath')[0] + assert len(callpath.dependencies(name='zmpi')) == 1 + + zmpi = callpath.dependencies(name='zmpi')[0] + assert len(zmpi.dependencies(name='fake')) == 1 + + assert all(not d.dependencies(name='mpi') for d in spec.traverse()) + assert all(x in spec for x in ('zmpi', 'mpi')) def test_my_dep_depends_on_provider_of_my_virtual_dep(self): spec = Spec('indirect-mpich') @@ -604,7 +615,7 @@ class TestConcretize(object): assert s.concrete # Remove the dependencies and reset caches - s._dependencies.clear() + s.clear_dependencies() s._concrete = False assert not s.concrete diff --git a/lib/spack/spack/test/conftest.py b/lib/spack/spack/test/conftest.py index 36a45bb637..45f034df26 100644 --- a/lib/spack/spack/test/conftest.py +++ b/lib/spack/spack/test/conftest.py @@ -754,10 +754,11 @@ def mock_store(tmpdir_factory, mock_repo_path, mock_configuration_scopes, @pytest.fixture(scope='function') -def database(mock_store, mock_packages, config, monkeypatch): +def database(mock_store, mock_packages, config): """This activates the mock store, packages, AND config.""" with spack.store.use_store(str(mock_store)) as store: yield store.db + # Force reading the database again between tests store.db.last_seen_verifier = '' diff --git a/lib/spack/spack/test/database.py b/lib/spack/spack/test/database.py index 1509dbb335..89359d2a44 100644 --- a/lib/spack/spack/test/database.py +++ b/lib/spack/spack/test/database.py @@ -973,3 +973,36 @@ def test_reindex_when_all_prefixes_are_removed(mutable_database, mock_store): mutable_database.remove(s) assert len(mutable_database.query_local(installed=False, explicit=True)) == 0 + + +@pytest.mark.parametrize('spec_str,parent_name,expected_nparents', [ + ('dyninst', 'callpath', 3), + ('libelf', 'dyninst', 1), + ('libelf', 'libdwarf', 1) +]) +@pytest.mark.regression('11983') +def test_check_parents(spec_str, parent_name, expected_nparents, database): + """Check that a spec returns the correct number of parents.""" + s = database.query_one(spec_str) + + parents = s.dependents(name=parent_name) + assert len(parents) == expected_nparents + + edges = s.edges_from_dependents(name=parent_name) + assert len(edges) == expected_nparents + + +def test_consistency_of_dependents_upon_remove(mutable_database): + # Check the initial state + s = mutable_database.query_one('dyninst') + parents = s.dependents(name='callpath') + assert len(parents) == 3 + + # Remove a dependent (and all its dependents) + mutable_database.remove('mpileaks ^callpath ^mpich2') + mutable_database.remove('callpath ^mpich2') + + # Check the final state + s = mutable_database.query_one('dyninst') + parents = s.dependents(name='callpath') + assert len(parents) == 2 diff --git a/lib/spack/spack/test/graph.py b/lib/spack/spack/test/graph.py index 6cd8b69d84..c836c9905a 100644 --- a/lib/spack/spack/test/graph.py +++ b/lib/spack/spack/test/graph.py @@ -2,43 +2,31 @@ # Spack Project Developers. See the top-level COPYRIGHT file for details. # # SPDX-License-Identifier: (Apache-2.0 OR MIT) +import sys -from six import StringIO +import pytest +import six +import spack.graph import spack.repo -from spack.graph import AsciiGraph, graph_dot, topological_sort -from spack.spec import Spec +import spack.spec -def test_topo_sort(mock_packages): - """Test topo sort gives correct order.""" - s = Spec('mpileaks').normalized() +@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:]) - topo = topological_sort(s) - assert topo.index('mpileaks') < topo.index('callpath') - assert topo.index('mpileaks') < topo.index('mpi') - assert topo.index('mpileaks') < topo.index('dyninst') - assert topo.index('mpileaks') < topo.index('libdwarf') - assert topo.index('mpileaks') < topo.index('libelf') - - assert topo.index('callpath') < topo.index('mpi') - assert topo.index('callpath') < topo.index('dyninst') - assert topo.index('callpath') < topo.index('libdwarf') - assert topo.index('callpath') < topo.index('libelf') - - assert topo.index('dyninst') < topo.index('libdwarf') - assert topo.index('dyninst') < topo.index('libelf') - - assert topo.index('libdwarf') < topo.index('libelf') - - -def test_static_graph_mpileaks(mock_packages): +def test_static_graph_mpileaks(config, mock_packages): """Test a static spack graph for a simple package.""" - s = Spec('mpileaks').normalized() + s = spack.spec.Spec('mpileaks').normalized() - stream = StringIO() - graph_dot([s], static=True, out=stream) + stream = six.StringIO() + spack.graph.graph_dot([s], static=True, out=stream) dot = stream.getvalue() @@ -62,72 +50,67 @@ def test_static_graph_mpileaks(mock_packages): def test_dynamic_dot_graph_mpileaks(mock_packages, config): """Test dynamically graphing the mpileaks package.""" - s = Spec('mpileaks').concretized() - - stream = StringIO() - graph_dot([s], static=False, out=stream) - + s = spack.spec.Spec('mpileaks').concretized() + stream = six.StringIO() + spack.graph.graph_dot([s], static=False, out=stream) dot = stream.getvalue() - print(dot) - - mpileaks_hash, mpileaks_lbl = s.dag_hash(), s.format('{name}') - mpi_hash, mpi_lbl = s['mpi'].dag_hash(), s['mpi'].format('{name}') - callpath_hash, callpath_lbl = ( - s['callpath'].dag_hash(), s['callpath'].format('{name}')) - dyninst_hash, dyninst_lbl = ( - s['dyninst'].dag_hash(), s['dyninst'].format('{name}')) - libdwarf_hash, libdwarf_lbl = ( - s['libdwarf'].dag_hash(), s['libdwarf'].format('{name}')) - libelf_hash, libelf_lbl = ( - s['libelf'].dag_hash(), s['libelf'].format('{name}')) - - assert ' "%s" [label="%s"]\n' % (mpileaks_hash, mpileaks_lbl) in dot - assert ' "%s" [label="%s"]\n' % (callpath_hash, callpath_lbl) in dot - assert ' "%s" [label="%s"]\n' % (mpi_hash, mpi_lbl) in dot - assert ' "%s" [label="%s"]\n' % (dyninst_hash, dyninst_lbl) in dot - assert ' "%s" [label="%s"]\n' % (libdwarf_hash, libdwarf_lbl) in dot - assert ' "%s" [label="%s"]\n' % (libelf_hash, libelf_lbl) in dot - - assert ' "%s" -> "%s"\n' % (dyninst_hash, libdwarf_hash) in dot - assert ' "%s" -> "%s"\n' % (callpath_hash, dyninst_hash) in dot - assert ' "%s" -> "%s"\n' % (mpileaks_hash, mpi_hash) in dot - assert ' "%s" -> "%s"\n' % (libdwarf_hash, libelf_hash) in dot - assert ' "%s" -> "%s"\n' % (callpath_hash, mpi_hash) in dot - assert ' "%s" -> "%s"\n' % (mpileaks_hash, callpath_hash) in dot - assert ' "%s" -> "%s"\n' % (dyninst_hash, libelf_hash) in dot - - -def test_ascii_graph_mpileaks(mock_packages): - """Test dynamically graphing the mpileaks package.""" - s = Spec('mpileaks').normalized() - stream = StringIO() - graph = AsciiGraph() + nodes_to_check = ['mpileaks', 'mpi', 'callpath', 'dyninst', 'libdwarf', 'libelf'] + hashes = {} + 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 + + dependencies_to_check = [ + ('dyninst', 'libdwarf'), + ('callpath', 'dyninst'), + ('mpileaks', 'mpi'), + ('libdwarf', 'libelf'), + ('callpath', 'mpi'), + ('mpileaks', 'callpath'), + ('dyninst', 'libelf') + ] + for parent, child in dependencies_to_check: + assert ' "{0}" -> "{1}"\n'.format(hashes[parent], hashes[child]) in dot + + +@pytest.mark.skipif( + sys.version_info < (3, 6), reason="Ordering might not be consistent" +) +def test_ascii_graph_mpileaks(config, mock_packages, monkeypatch): + monkeypatch.setattr( + spack.graph.AsciiGraph, '_node_label', + lambda self, node: node.name + ) + s = spack.spec.Spec('mpileaks').concretized() + + stream = six.StringIO() + graph = spack.graph.AsciiGraph() graph.write(s, out=stream, color=False) - string = stream.getvalue() + graph_str = stream.getvalue() + graph_str = '\n'.join([line.rstrip() for line in graph_str.split('\n')]) - # Some lines in spack graph still have trailing space - # TODO: fix this. - string = '\n'.join([line.rstrip() for line in string.split('\n')]) - - assert string == r'''o mpileaks + assert graph_str == r'''o mpileaks |\ -| o callpath +| o callpath |/| -o | mpi +o | mpich / -o dyninst +o dyninst |\ -| o libdwarf +o | libdwarf |/ -o libelf +o libelf ''' -def test_topo_sort_filtered(mock_packages): - """Test topo sort gives correct order when filtering link deps.""" - s = Spec('both-link-and-build-dep-a').normalized() - - topo = topological_sort(s, deptype=('link',)) +def test_topological_sort_filtering_dependency_types(config, mock_packages): + s = spack.spec.Spec('both-link-and-build-dep-a').concretized() - assert topo == ['both-link-and-build-dep-a', 'both-link-and-build-dep-c'] + 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'] diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py index 61ec9010d2..046ff7aad2 100644 --- a/lib/spack/spack/test/spec_dag.py +++ b/lib/spack/spack/test/spec_dag.py @@ -18,10 +18,10 @@ from spack.util.mock_package import MockPackageMultiRepo def check_links(spec_to_check): for spec in spec_to_check.traverse(): for dependent in spec.dependents(): - assert spec.name in dependent.dependencies_dict() + assert dependent.edges_to_dependencies(name=spec.name) for dependency in spec.dependencies(): - assert spec.name in dependency.dependents_dict() + assert dependency.edges_from_dependents(name=spec.name) @pytest.fixture() @@ -297,9 +297,16 @@ class TestSpecDag(object): # Normalize then add conflicting constraints to the DAG (this is an # extremely unlikely scenario, but we test for it anyway) mpileaks.normalize() - mpileaks._dependencies['mpich'].spec = Spec('mpich@1.0') - mpileaks._dependencies['callpath']. \ - spec._dependencies['mpich'].spec = Spec('mpich@2.0') + + mpileaks.edges_to_dependencies( + name='mpich' + )[0].spec = Spec('mpich@1.0') + + mpileaks.edges_to_dependencies( + name='callpath' + )[0].spec.edges_to_dependencies( + name='mpich' + )[0].spec = Spec('mpich@2.0') with pytest.raises(spack.spec.InconsistentSpecError): mpileaks.flat_dependencies(copy=False) @@ -617,6 +624,23 @@ class TestSpecDag(object): copy_ids = set(id(s) for s in copy.traverse()) assert not orig_ids.intersection(copy_ids) + def test_copy_through_spec_build_interface(self): + """Check that copying dependencies using id(node) as a fast identifier of the + node works when the spec is wrapped in a SpecBuildInterface object. + """ + s = Spec('mpileaks').concretized() + + c0 = s.copy() + assert c0 == s + + # Single indirection + c1 = s['mpileaks'].copy() + assert c0 == c1 == s + + # Double indirection + c2 = s['mpileaks']['mpileaks'].copy() + assert c0 == c1 == c2 == s + """ Here is the graph with deptypes labeled (assume all packages have a 'dt' prefix). Arrows are marked with the deptypes ('b' for 'build', 'l' for @@ -790,21 +814,25 @@ class TestSpecDag(object): } }) - assert s['b']._dependencies['c'].deptypes == ('build',) - assert s['d']._dependencies['e'].deptypes == ('build', 'link') - assert s['e']._dependencies['f'].deptypes == ('run',) - - assert s['b']._dependencies['c'].deptypes == ('build',) - assert s['d']._dependencies['e'].deptypes == ('build', 'link') - assert s['e']._dependencies['f'].deptypes == ('run',) - - assert s['c']._dependents['b'].deptypes == ('build',) - assert s['e']._dependents['d'].deptypes == ('build', 'link') - assert s['f']._dependents['e'].deptypes == ('run',) - - assert s['c']._dependents['b'].deptypes == ('build',) - assert s['e']._dependents['d'].deptypes == ('build', 'link') - assert s['f']._dependents['e'].deptypes == ('run',) + assert s['b'].edges_to_dependencies( + name='c' + )[0].deptypes == ('build',) + assert s['d'].edges_to_dependencies( + name='e' + )[0].deptypes == ('build', 'link') + assert s['e'].edges_to_dependencies( + name='f' + )[0].deptypes == ('run',) + + assert s['c'].edges_from_dependents( + name='b' + )[0].deptypes == ('build',) + assert s['e'].edges_from_dependents( + name='d' + )[0].deptypes == ('build', 'link') + assert s['f'].edges_from_dependents( + name='e' + )[0].deptypes == ('run',) def check_diamond_deptypes(self, spec): """Validate deptypes in dt-diamond spec. @@ -813,17 +841,21 @@ class TestSpecDag(object): depend on the same dependency in different ways. """ - assert spec['dt-diamond']._dependencies[ - 'dt-diamond-left'].deptypes == ('build', 'link') + assert spec['dt-diamond'].edges_to_dependencies( + name='dt-diamond-left' + )[0].deptypes == ('build', 'link') - assert spec['dt-diamond']._dependencies[ - 'dt-diamond-right'].deptypes == ('build', 'link') + assert spec['dt-diamond'].edges_to_dependencies( + name='dt-diamond-right' + )[0].deptypes == ('build', 'link') - assert spec['dt-diamond-left']._dependencies[ - 'dt-diamond-bottom'].deptypes == ('build',) + assert spec['dt-diamond-left'].edges_to_dependencies( + name='dt-diamond-bottom' + )[0].deptypes == ('build',) - assert spec['dt-diamond-right'] ._dependencies[ - 'dt-diamond-bottom'].deptypes == ('build', 'link', 'run') + assert spec['dt-diamond-right'].edges_to_dependencies( + name='dt-diamond-bottom' + )[0].deptypes == ('build', 'link', 'run') def check_diamond_normalized_dag(self, spec): @@ -989,3 +1021,99 @@ class TestSpecDag(object): assert 'version-test-pkg' in out out = s.tree(deptypes=('link', 'run')) assert 'version-test-pkg' not in out + + +def test_synthetic_construction_of_split_dependencies_from_same_package( + mock_packages, config +): + # Construct in a synthetic way (i.e. without using the solver) + # the following spec: + # + # b + # build / \ link,run + # c@2.0 c@1.0 + # + # To demonstrate that a spec can now hold two direct + # dependencies from the same package + root = Spec('b').concretized() + link_run_spec = Spec('c@1.0').concretized() + build_spec = Spec('c@2.0').concretized() + + root.add_dependency_edge(link_run_spec, deptype='link') + root.add_dependency_edge(link_run_spec, deptype='run') + root.add_dependency_edge(build_spec, deptype='build') + + # Check dependencies from the perspective of root + assert len(root.dependencies()) == 2 + assert all(x.name == 'c' for x in root.dependencies()) + + assert '@2.0' in root.dependencies(name='c', deptype='build')[0] + assert '@1.0' in root.dependencies(name='c', deptype=('link', 'run'))[0] + + # Check parent from the perspective of the dependencies + assert len(build_spec.dependents()) == 1 + assert len(link_run_spec.dependents()) == 1 + assert build_spec.dependents() == link_run_spec.dependents() + assert build_spec != link_run_spec + + +def test_synthetic_construction_bootstrapping(mock_packages, config): + # Construct the following spec: + # + # b@2.0 + # | build + # b@1.0 + # + root = Spec('b@2.0').concretized() + bootstrap = Spec('b@1.0').concretized() + + root.add_dependency_edge(bootstrap, deptype='build') + + assert len(root.dependencies()) == 1 + assert root.dependencies()[0].name == 'b' + assert root.name == 'b' + + +def test_addition_of_different_deptypes_in_multiple_calls(mock_packages, config): + # Construct the following spec: + # + # b@2.0 + # | build,link,run + # b@1.0 + # + # with three calls and check we always have a single edge + root = Spec('b@2.0').concretized() + bootstrap = Spec('b@1.0').concretized() + + for current_deptype in ('build', 'link', 'run'): + root.add_dependency_edge(bootstrap, deptype=current_deptype) + + # Check edges in dependencies + assert len(root.edges_to_dependencies()) == 1 + forward_edge = root.edges_to_dependencies(deptype=current_deptype)[0] + assert current_deptype in forward_edge.deptypes + assert id(forward_edge.parent) == id(root) + assert id(forward_edge.spec) == id(bootstrap) + + # Check edges from dependents + assert len(bootstrap.edges_from_dependents()) == 1 + backward_edge = bootstrap.edges_from_dependents(deptype=current_deptype)[0] + assert current_deptype in backward_edge.deptypes + assert id(backward_edge.parent) == id(root) + assert id(backward_edge.spec) == id(bootstrap) + + +@pytest.mark.parametrize('c1_deptypes,c2_deptypes', [ + ('link', ('build', 'link')), + (('link', 'run'), ('build', 'link')) +]) +def test_adding_same_deptype_with_the_same_name_raises( + mock_packages, config, c1_deptypes, c2_deptypes +): + p = Spec('b@2.0').concretized() + c1 = Spec('b@1.0').concretized() + c2 = Spec('b@2.0').concretized() + + p.add_dependency_edge(c1, deptype=c1_deptypes) + with pytest.raises(spack.error.SpackError): + p.add_dependency_edge(c2, deptype=c2_deptypes) diff --git a/var/spack/repos/builtin/packages/petsc/package.py b/var/spack/repos/builtin/packages/petsc/package.py index e7ea1f08d0..f95f428cef 100644 --- a/var/spack/repos/builtin/packages/petsc/package.py +++ b/var/spack/repos/builtin/packages/petsc/package.py @@ -415,6 +415,7 @@ class Petsc(Package, CudaPackage, ROCmPackage): # default: 'gmp', => ('gmp', 'gmp', True, True) # any other combination needs a full tuple # if not (useinc || uselib): usedir - i.e (False, False) + direct_dependencies = [x.name for x in spec.dependencies()] for library in ( ('cuda', 'cuda', False, False), ('hip', 'hip', True, False), @@ -465,7 +466,7 @@ class Petsc(Package, CudaPackage, ROCmPackage): useinc = True uselib = True - library_requested = spacklibname.split(':')[0] in spec.dependencies_dict() + library_requested = spacklibname.split(':')[0] in direct_dependencies options.append( '--with-{library}={value}'.format( library=petsclibname, |