summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHarmen Stoppels <harmenstoppels@gmail.com>2022-10-26 07:55:05 +0200
committerGitHub <noreply@github.com>2022-10-25 22:55:05 -0700
commitd039744a5be714d476e8c41e38ec6a789dfe6de7 (patch)
treed0cee01a996db8f98b2b5ca4902c68bca7927663
parent57c1d6c410a7328518ee242336df181b2b156c61 (diff)
downloadspack-d039744a5be714d476e8c41e38ec6a789dfe6de7.tar.gz
spack-d039744a5be714d476e8c41e38ec6a789dfe6de7.tar.bz2
spack-d039744a5be714d476e8c41e38ec6a789dfe6de7.tar.xz
spack-d039744a5be714d476e8c41e38ec6a789dfe6de7.zip
dfs traversal: simplify edges in reverse mode (#33481)
In the dfs code, flip edges so that `parent` means `from` and `spec` means `to` in the direction of traversal. This makes it slightly easier to write generic/composable code. For example when using visitors where one visitor reverses direction, and another only cares about accepting particular edges or not depending on whether the target node is seen before, it would be good if the second visitor didn't have to know whether the order was changed or not.
-rw-r--r--lib/spack/spack/spec.py53
1 files changed, 26 insertions, 27 deletions
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 9256be5803..2f4120a5f8 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -734,6 +734,9 @@ class DependencySpec(object):
def canonical(self):
return self.parent.dag_hash(), self.spec.dag_hash(), self.deptypes
+ def flip(self):
+ return DependencySpec(parent=self.spec, spec=self.parent, deptypes=self.deptypes)
+
_valid_compiler_flags = ["cflags", "cxxflags", "fflags", "ldflags", "ldlibs", "cppflags"]
@@ -812,6 +815,10 @@ def _sort_by_dep_types(dspec):
return tuple(t not in dspec.deptypes for t in ("link", "run", "build", "test"))
+def _sort_edges_by_pkg_name(edges):
+ edges.sort(key=lambda edge: edge.spec.name)
+
+
#: Enum for edge directions
EdgeDirection = lang.enum(parent=0, child=1)
@@ -1604,29 +1611,28 @@ class Spec(object):
return upstream
def traverse(self, **kwargs):
- direction = kwargs.get("direction", "children")
depth = kwargs.get("depth", False)
- get_spec = lambda s: s.spec
- if direction == "parents":
- get_spec = lambda s: s.parent
-
if depth:
- for d, dspec in self.traverse_edges(**kwargs):
- yield d, get_spec(dspec)
+ for d, edge in self.traverse_edges(**kwargs):
+ yield d, edge.spec
else:
- for dspec in self.traverse_edges(**kwargs):
- yield get_spec(dspec)
+ for edge in self.traverse_edges(**kwargs):
+ yield edge.spec
def traverse_edges(self, visited=None, d=0, deptype="all", dep_spec=None, **kwargs):
"""Generic traversal of the DAG represented by this spec.
This yields ``DependencySpec`` objects as they are traversed.
- When traversing top-down, an imaginary incoming edge to the root
- is yielded first as ``DependencySpec(None, root, ())``. When
- traversing bottom-up, imaginary edges to leaves are yielded first
- as ``DependencySpec(left, None, ())`` objects.
+ An imaginary incoming edge to the root is yielded first as
+ ``DependencySpec(None, root, ())``.
+
+ Note: the edges are traversed from ``edge.parent`` to ``edge.spec``,
+ even if the direction is reversed. When ``direction="children"`` the
+ parent points to the dependent, and spec to the dependency. Conversely
+ when ``direction="parents"`` parent points to the dependency, and spec
+ to the dependent.
Options:
@@ -1711,10 +1717,7 @@ class Spec(object):
def return_val(dspec):
if not dspec:
# make a fake dspec for the root.
- if direction == "parents":
- dspec = DependencySpec(self, None, ())
- else:
- dspec = DependencySpec(None, self, ())
+ dspec = DependencySpec(None, self, ())
return (d, dspec) if depth else dspec
yield_me = yield_root or d > 0
@@ -1729,22 +1732,18 @@ class Spec(object):
# This code determines direction and yields the children/parents
if direction == "children":
- edges = self.edges_to_dependencies
- key_fn = lambda dspec: dspec.spec.name
- succ = lambda dspec: dspec.spec
- elif direction == "parents":
- edges = self.edges_from_dependents
- key_fn = lambda dspec: dspec.parent.name
- succ = lambda dspec: dspec.parent
+ edges = self.edges_to_dependencies()
else:
- raise ValueError("Invalid traversal direction: %s" % direction)
+ edges = [edge.flip() for edge in self.edges_from_dependents()]
+
+ _sort_edges_by_pkg_name(edges)
- for dspec in sorted(edges(), key=key_fn):
+ for dspec in edges:
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):
+ for child in dspec.spec.traverse_edges(visited, d + 1, deptype, dspec, **kwargs):
yield child
# Postorder traversal yields after successors