Skip to content

Commit 2cd5c00

Browse files
alalazoalalazo
authored
Allow for multiple dependencies/dependents from the same package (spack#28673)
Change the internal representation of `Spec` to allow for multiple dependencies or dependents stemming from the same package. This change permits to represent cases which are frequent in cross compiled environments or to bootstrap compilers. Modifications: - [x] Substitute `DependencyMap` with `_EdgeMap`. The main differences are that the latter does not support direct item assignment and can be modified only through its API. It also provides a `select_by` method to query items. - [x] Reworked a few public APIs of `Spec` to get list of dependencies or related edges. - [x] Added unit tests to prevent regression on spack#11983 and prove the synthetic construction of specs with multiple deps from the same package. Since spack#22845 went in first, this PR reuses that format and thus it should not change hashes. The same package may be present multiple times in the list of dependencies with different associated specs (each with its own hash).
1 parent 3d624d2 commit 2cd5c00

14 files changed

Lines changed: 776 additions & 321 deletions

File tree

‎lib/spack/llnl/util/lang.py‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -967,3 +967,12 @@ def nullcontext(*args, **kwargs):
967967

968968
class UnhashableArguments(TypeError):
969969
"""Raise when an @memoized function receives unhashable arg or kwarg values."""
970+
971+
972+
def enum(**kwargs):
973+
"""Return an enum-like class.
974+
975+
Args:
976+
**kwargs: explicit dictionary of enums
977+
"""
978+
return type('Enum', (object,), kwargs)

‎lib/spack/spack/cmd/deactivate.py‎

Lines changed: 3 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,9 +8,9 @@
88
import spack.cmd
99
import spack.cmd.common.arguments as arguments
1010
import spack.environment as ev
11+
import spack.graph
1112
import spack.store
1213
from spack.filesystem_view import YamlFilesystemView
13-
from spack.graph import topological_sort
1414

1515
description = "deactivate a package extension"
1616
section = "extensions"
@@ -68,11 +68,8 @@ def deactivate(parser, args):
6868
tty.msg("Deactivating %s and all dependencies." %
6969
pkg.spec.short_spec)
7070

71-
topo_order = topological_sort(spec)
72-
index = spec.index()
73-
74-
for name in topo_order:
75-
espec = index[name]
71+
nodes_in_topological_order = spack.graph.topological_sort(spec)
72+
for espec in reversed(nodes_in_topological_order):
7673
epkg = espec.package
7774
if epkg.extends(pkg.extendee_spec):
7875
if epkg.is_activated(view) or args.force:

‎lib/spack/spack/database.py‎

Lines changed: 8 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -961,7 +961,7 @@ def _check_ref_counts(self):
961961
counts = {}
962962
for key, rec in self._data.items():
963963
counts.setdefault(key, 0)
964-
for dep in rec.spec.dependencies(_tracked_deps):
964+
for dep in rec.spec.dependencies(deptype=_tracked_deps):
965965
dep_key = dep.dag_hash()
966966
counts.setdefault(dep_key, 0)
967967
counts[dep_key] += 1
@@ -1078,7 +1078,7 @@ def _add(
10781078
# Retrieve optional arguments
10791079
installation_time = installation_time or _now()
10801080

1081-
for dep in spec.dependencies(_tracked_deps):
1081+
for dep in spec.dependencies(deptype=_tracked_deps):
10821082
dkey = dep.dag_hash()
10831083
if dkey not in self._data:
10841084
extra_args = {
@@ -1120,9 +1120,7 @@ def _add(
11201120
)
11211121

11221122
# Connect dependencies from the DB to the new copy.
1123-
for name, dep in six.iteritems(
1124-
spec.dependencies_dict(_tracked_deps)
1125-
):
1123+
for dep in spec.edges_to_dependencies(deptype=_tracked_deps):
11261124
dkey = dep.spec.dag_hash()
11271125
upstream, record = self.query_by_spec_hash(dkey)
11281126
new_spec._add_dependency(record.spec, dep.deptypes)
@@ -1185,7 +1183,7 @@ def _decrement_ref_count(self, spec):
11851183
if rec.ref_count == 0 and not rec.installed:
11861184
del self._data[key]
11871185

1188-
for dep in spec.dependencies(_tracked_deps):
1186+
for dep in spec.dependencies(deptype=_tracked_deps):
11891187
self._decrement_ref_count(dep)
11901188

11911189
def _increment_ref_count(self, spec):
@@ -1213,13 +1211,10 @@ def _remove(self, spec):
12131211

12141212
del self._data[key]
12151213

1216-
for dep in rec.spec.dependencies(_tracked_deps):
1217-
# FIXME: the two lines below needs to be updated once #11983 is
1218-
# FIXME: fixed. The "if" statement should be deleted and specs are
1219-
# FIXME: to be removed from dependents by hash and not by name.
1220-
# FIXME: See https://github.com/spack/spack/pull/15777#issuecomment-607818955
1221-
if dep._dependents.get(spec.name):
1222-
del dep._dependents[spec.name]
1214+
# Remove any reference to this node from dependencies and
1215+
# decrement the reference count
1216+
rec.spec.detach(deptype=_tracked_deps)
1217+
for dep in rec.spec.dependencies(deptype=_tracked_deps):
12231218
self._decrement_ref_count(dep)
12241219

12251220
if rec.deprecated_for:

‎lib/spack/spack/dependency.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,7 @@ def canonical_deptype(deptype):
5858
if bad:
5959
raise ValueError(
6060
'Invalid dependency types: %s' % ','.join(str(t) for t in bad))
61-
return tuple(sorted(deptype))
61+
return tuple(sorted(set(deptype)))
6262

6363
raise ValueError('Invalid dependency type: %s' % repr(deptype))
6464

‎lib/spack/spack/graph.py‎

Lines changed: 89 additions & 58 deletions
Original file line numberDiff line numberDiff line change
@@ -42,54 +42,84 @@
4242
can take a number of specs as input.
4343
4444
"""
45+
import heapq
46+
import itertools
4547
import sys
46-
from heapq import heapify, heappop, heappush
4748

48-
from llnl.util.tty.color import ColorStream
49+
import llnl.util.tty.color
4950

50-
from spack.dependency import all_deptypes, canonical_deptype
51+
import spack.dependency
5152

52-
__all__ = ['topological_sort', 'graph_ascii', 'AsciiGraph', 'graph_dot']
53+
__all__ = ['graph_ascii', 'AsciiGraph', 'graph_dot']
5354

5455

55-
def topological_sort(spec, reverse=False, deptype='all'):
56-
"""Topological sort for specs.
56+
def node_label(spec):
57+
return spec.format('{name}{@version}{/hash:7}')
5758

58-
Return a list of dependency specs sorted topologically. The spec
59-
argument is not modified in the process.
6059

61-
"""
62-
deptype = canonical_deptype(deptype)
63-
64-
# Work on a copy so this is nondestructive.
65-
spec = spec.copy(deps=deptype)
66-
nodes = spec.index(deptype=deptype)
60+
def topological_sort(spec, deptype='all'):
61+
"""Return a list of dependency specs in topological sorting order.
6762
68-
parents = lambda s: [p for p in s.dependents() if p.name in nodes]
69-
children = lambda s: s.dependencies()
63+
The spec argument is not modified in by the function.
7064
71-
if reverse:
72-
parents, children = children, parents
65+
This function assumes specs don't have cycles, i.e. that we are really
66+
operating with a DAG.
7367
74-
topo_order = []
75-
par = dict((name, parents(nodes[name])) for name in nodes.keys())
76-
remaining = [name for name in nodes.keys() if not parents(nodes[name])]
77-
heapify(remaining)
68+
Args:
69+
spec (spack.spec.Spec): the spec to be analyzed
70+
deptype (str or tuple): dependency types to account for when
71+
constructing the list
72+
"""
73+
deptype = spack.dependency.canonical_deptype(deptype)
7874

79-
while remaining:
80-
name = heappop(remaining)
81-
topo_order.append(name)
75+
# Work on a copy so this is nondestructive
76+
spec = spec.copy(deps=True)
77+
nodes = spec.index(deptype=deptype)
8278

83-
node = nodes[name]
84-
for dep in children(node):
85-
par[dep.name].remove(node)
86-
if not par[dep.name]:
87-
heappush(remaining, dep.name)
79+
def dependencies(specs):
80+
"""Return all the dependencies (including transitive) for a spec."""
81+
return list(set(itertools.chain.from_iterable(
82+
s.dependencies(deptype=deptype) for s in specs
83+
)))
8884

89-
if any(par.get(s.name, []) for s in spec.traverse()):
90-
raise ValueError("Spec has cycles!")
91-
else:
92-
return topo_order
85+
def dependents(specs):
86+
"""Return all the dependents (including those of transitive dependencies)
87+
for a spec.
88+
"""
89+
candidates = list(set(itertools.chain.from_iterable(
90+
s.dependents(deptype=deptype) for s in specs
91+
)))
92+
return [x for x in candidates if x.name in nodes]
93+
94+
topological_order, children = [], {}
95+
96+
# Map a spec encoded as (id, name) to a list of its transitive dependencies
97+
for spec in itertools.chain.from_iterable(nodes.values()):
98+
children[(id(spec), spec.name)] = [
99+
x for x in dependencies([spec]) if x.name in nodes
100+
]
101+
102+
# To return a result that is topologically ordered we need to add nodes
103+
# only after their dependencies. The first nodes we can add are leaf nodes,
104+
# i.e. nodes that have no dependencies.
105+
ready = [
106+
spec for spec in itertools.chain.from_iterable(nodes.values())
107+
if not dependencies([spec])
108+
]
109+
heapq.heapify(ready)
110+
111+
while ready:
112+
# Pop a "ready" node and add it to the topologically ordered list
113+
s = heapq.heappop(ready)
114+
topological_order.append(s)
115+
116+
# Check if adding the last node made other nodes "ready"
117+
for dep in dependents([s]):
118+
children[(id(dep), dep.name)].remove(s)
119+
if not children[(id(dep), dep.name)]:
120+
heapq.heappush(ready, dep)
121+
122+
return topological_order
93123

94124

95125
def find(seq, predicate):
@@ -120,7 +150,7 @@ def __init__(self):
120150
self.node_character = 'o'
121151
self.debug = False
122152
self.indent = 0
123-
self.deptype = all_deptypes
153+
self.deptype = spack.dependency.all_deptypes
124154

125155
# These are colors in the order they'll be used for edges.
126156
# See llnl.util.tty.color for details on color characters.
@@ -131,7 +161,6 @@ def __init__(self):
131161
self._name_to_color = None # Node name to color
132162
self._out = None # Output stream
133163
self._frontier = None # frontier
134-
self._nodes = None # dict from name -> node
135164
self._prev_state = None # State of previous line
136165
self._prev_index = None # Index of expansion point of prev line
137166

@@ -290,7 +319,10 @@ def advance(to_pos, edges):
290319
self._set_state(BACK_EDGE, end, label)
291320
self._out.write("\n")
292321

293-
def _node_line(self, index, name):
322+
def _node_label(self, node):
323+
return node.format('{name}@@{version}{/hash:7}')
324+
325+
def _node_line(self, index, node):
294326
"""Writes a line with a node at index."""
295327
self._indent()
296328
for c in range(index):
@@ -301,7 +333,7 @@ def _node_line(self, index, name):
301333
for c in range(index + 1, len(self._frontier)):
302334
self._write_edge("| ", c)
303335

304-
self._out.write(" %s" % name)
336+
self._out.write(self._node_label(node))
305337
self._set_state(NODE, index)
306338
self._out.write("\n")
307339

@@ -363,29 +395,29 @@ def write(self, spec, color=None, out=None):
363395
if color is None:
364396
color = out.isatty()
365397

366-
self._out = ColorStream(out, color=color)
398+
self._out = llnl.util.tty.color.ColorStream(out, color=color)
367399

368-
# We'll traverse the spec in topo order as we graph it.
369-
topo_order = topological_sort(spec, reverse=True, deptype=self.deptype)
400+
# We'll traverse the spec in topological order as we graph it.
401+
nodes_in_topological_order = topological_sort(spec, deptype=self.deptype)
370402

371403
# Work on a copy to be nondestructive
372404
spec = spec.copy()
373-
self._nodes = spec.index()
374405

375406
# Colors associated with each node in the DAG.
376407
# Edges are colored by the node they point to.
377-
self._name_to_color = dict((name, self.colors[i % len(self.colors)])
378-
for i, name in enumerate(topo_order))
408+
self._name_to_color = {
409+
spec.full_hash(): self.colors[i % len(self.colors)]
410+
for i, spec in enumerate(nodes_in_topological_order)
411+
}
379412

380413
# Frontier tracks open edges of the graph as it's written out.
381-
self._frontier = [[spec.name]]
414+
self._frontier = [[spec.full_hash()]]
382415
while self._frontier:
383416
# Find an unexpanded part of frontier
384417
i = find(self._frontier, lambda f: len(f) > 1)
385418

386419
if i >= 0:
387-
# Expand frontier until there are enough columns for all
388-
# children.
420+
# Expand frontier until there are enough columns for all children.
389421

390422
# Figure out how many back connections there are and
391423
# sort them so we do them in order
@@ -436,8 +468,8 @@ def write(self, spec, color=None, out=None):
436468

437469
else:
438470
# Just allow the expansion here.
439-
name = self._frontier[i].pop(0)
440-
deps = [name]
471+
dep_hash = self._frontier[i].pop(0)
472+
deps = [dep_hash]
441473
self._frontier.insert(i, deps)
442474
self._expand_right_line(i)
443475

@@ -453,18 +485,17 @@ def write(self, spec, color=None, out=None):
453485

454486
else:
455487
# Nothing to expand; add dependencies for a node.
456-
name = topo_order.pop()
457-
node = self._nodes[name]
488+
node = nodes_in_topological_order.pop()
458489

459490
# Find the named node in the frontier and draw it.
460-
i = find(self._frontier, lambda f: name in f)
461-
self._node_line(i, name)
491+
i = find(self._frontier, lambda f: node.full_hash() in f)
492+
self._node_line(i, node)
462493

463494
# Replace node with its dependencies
464495
self._frontier.pop(i)
465-
deps = node.dependencies(self.deptype)
496+
deps = node.dependencies(deptype=self.deptype)
466497
if deps:
467-
deps = sorted((d.name for d in deps), reverse=True)
498+
deps = sorted((d.full_hash() for d in deps), reverse=True)
468499
self._connect_deps(i, deps, "new-deps") # anywhere.
469500

470501
elif self._frontier:
@@ -478,7 +509,7 @@ def graph_ascii(spec, node='o', out=None, debug=False,
478509
graph.indent = indent
479510
graph.node_character = node
480511
if deptype:
481-
graph.deptype = canonical_deptype(deptype)
512+
graph.deptype = spack.dependency.canonical_deptype(deptype)
482513

483514
graph.write(spec, color=color, out=out)
484515

@@ -499,7 +530,7 @@ def graph_dot(specs, deptype='all', static=False, out=None):
499530

500531
if out is None:
501532
out = sys.stdout
502-
deptype = canonical_deptype(deptype)
533+
deptype = spack.dependency.canonical_deptype(deptype)
503534

504535
def static_graph(spec, deptype):
505536
pkg = spec.package
@@ -517,7 +548,7 @@ def dynamic_graph(spec, deptypes):
517548
nodes = set() # elements are (node key, node label)
518549
edges = set() # elements are (src key, dest key)
519550
for s in spec.traverse(deptype=deptype):
520-
nodes.add((s.dag_hash(), s.name))
551+
nodes.add((s.dag_hash(), node_label(s)))
521552
for d in s.dependencies(deptype=deptype):
522553
edge = (s.dag_hash(), d.dag_hash())
523554
edges.add(edge)

‎lib/spack/spack/installer.py‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -227,8 +227,9 @@ def _packages_needed_to_bootstrap_compiler(compiler, architecture, pkgs):
227227
dep.concretize()
228228
# mark compiler as depended-on by the packages that use it
229229
for pkg in pkgs:
230-
dep._dependents[pkg.name] = spack.spec.DependencySpec(
231-
pkg.spec, dep, ('build',))
230+
dep._dependents.add(
231+
spack.spec.DependencySpec(pkg.spec, dep, ('build',))
232+
)
232233
packages = [(s.package, False) for
233234
s in dep.traverse(order='post', root=False)]
234235
packages.append((dep.package, True))

0 commit comments

Comments
 (0)