From 4bad9f9b1380e33499b6f8e06531898d8b7d679f Mon Sep 17 00:00:00 2001 From: Harmen Stoppels Date: Wed, 2 Nov 2022 07:04:47 +0100 Subject: Consolidate DAG traversal in traverse.py, support DFS/BFS (#33406) This PR introduces breadth-first traversal, and moves depth-first traversal logic out of Spec's member functions, into `traverse.py`. It introduces a high-level API with three main methods: ```python spack.traverse.traverse_edges(specs, kwargs...) spack.traverse.traverse_nodes(specs, kwags...) spack.traverse.traverse_tree(specs, kwargs...) ``` with the usual `root`, `order`, `cover`, `direction`, `deptype`, `depth`, `key`, `visited` kwargs for the first two. What's new is that `order="breadth"` is added for breadth-first traversal. The lower level API is not exported, but is certainly useful for advanced use cases. The lower level API includes visitor classes for direction reversal and edge pruning, which can be used to create more advanced traversal methods, especially useful when the `deptype` is not constant but depends on the node or depth. --- There's a couple nice use-cases for breadth-first traversal: - Sometimes roots have to be handled differently (e.g. follow build edges of roots but not of deps). BFS ensures that root nodes are always discovered at depth 0, instead of at any depth > 1 as a dep of another root. - When printing a tree, it would be nice to reduce indent levels so it fits in the terminal, and ensure that e.g. `zlib` is not printed at indent level 10 as a dependency of a build dep of a build dep -- rather if it's a direct dep of my package, I wanna see it at depth 1. This basically requires one breadth-first traversal to construct a tree, which can then be printed with depth-first traversal. - In environments in general, it's sometimes inconvenient to have a double loop: first over the roots then over each root's deps, and maintain your own `visited` set outside. With BFS, you can simply init the queue with the environment root specs and it Just Works. [Example here](https://github.com/spack/spack/blob/3ec73046995d9504d6e135f564f1370cfe31ba34/lib/spack/spack/environment/environment.py#L1815-L1816) --- .../repos/builtin.mock/packages/chain-a/package.py | 34 ++++++++++++++++++++++ .../repos/builtin.mock/packages/chain-b/package.py | 32 ++++++++++++++++++++ .../repos/builtin.mock/packages/chain-c/package.py | 32 ++++++++++++++++++++ .../repos/builtin.mock/packages/chain-d/package.py | 31 ++++++++++++++++++++ 4 files changed, 129 insertions(+) create mode 100644 var/spack/repos/builtin.mock/packages/chain-a/package.py create mode 100644 var/spack/repos/builtin.mock/packages/chain-b/package.py create mode 100644 var/spack/repos/builtin.mock/packages/chain-c/package.py create mode 100644 var/spack/repos/builtin.mock/packages/chain-d/package.py (limited to 'var') diff --git a/var/spack/repos/builtin.mock/packages/chain-a/package.py b/var/spack/repos/builtin.mock/packages/chain-a/package.py new file mode 100644 index 0000000000..6dc7dc2c90 --- /dev/null +++ b/var/spack/repos/builtin.mock/packages/chain-a/package.py @@ -0,0 +1,34 @@ +# Copyright 2013-2022 Lawrence Livermore National Security, LLC and other +# Spack Project Developers. See the top-level COPYRIGHT file for details. +# +# SPDX-License-Identifier: (Apache-2.0 OR MIT) + +from spack.package import * + + +class ChainA(Package): + """ + Part of a collection of mock packages used for testing depth-first vs + breadth-first traversal. The DAG they form: + a --> b --> c --> d # a chain + a --> c # "skip" connection + a --> d # "skip" connection + Spack's edge order is based on the child package name. + In depth-first traversal we get a tree that looks like a chain: + a + b + c + d + In breadth-first we get the tree: + a + b + c + d + """ + + homepage = "https://example.com" + has_code = False + version("1.0") + depends_on("chain-b") + depends_on("chain-c") + depends_on("chain-d") diff --git a/var/spack/repos/builtin.mock/packages/chain-b/package.py b/var/spack/repos/builtin.mock/packages/chain-b/package.py new file mode 100644 index 0000000000..ede29c0e0f --- /dev/null +++ b/var/spack/repos/builtin.mock/packages/chain-b/package.py @@ -0,0 +1,32 @@ +# Copyright 2013-2022 Lawrence Livermore National Security, LLC and other +# Spack Project Developers. See the top-level COPYRIGHT file for details. +# +# SPDX-License-Identifier: (Apache-2.0 OR MIT) + +from spack.package import * + + +class ChainB(Package): + """ + Part of a collection of mock packages used for testing depth-first vs + breadth-first traversal. The DAG they form: + a --> b --> c --> d # a chain + a --> c # "skip" connection + a --> d # "skip" connection + Spack's edge order is based on the child package name. + In depth-first traversal we get a tree that looks like a chain: + a + b + c + d + In breadth-first we get the tree: + a + b + c + d + """ + + homepage = "https://example.com" + has_code = False + version("1.0") + depends_on("chain-c") diff --git a/var/spack/repos/builtin.mock/packages/chain-c/package.py b/var/spack/repos/builtin.mock/packages/chain-c/package.py new file mode 100644 index 0000000000..e9d919f0ba --- /dev/null +++ b/var/spack/repos/builtin.mock/packages/chain-c/package.py @@ -0,0 +1,32 @@ +# Copyright 2013-2022 Lawrence Livermore National Security, LLC and other +# Spack Project Developers. See the top-level COPYRIGHT file for details. +# +# SPDX-License-Identifier: (Apache-2.0 OR MIT) + +from spack.package import * + + +class ChainC(Package): + """ + Part of a collection of mock packages used for testing depth-first vs + breadth-first traversal. The DAG they form: + a --> b --> c --> d # a chain + a --> c # "skip" connection + a --> d # "skip" connection + Spack's edge order is based on the child package name. + In depth-first traversal we get a tree that looks like a chain: + a + b + c + d + In breadth-first we get the tree: + a + b + c + d + """ + + homepage = "https://example.com" + has_code = False + version("1.0") + depends_on("chain-d") diff --git a/var/spack/repos/builtin.mock/packages/chain-d/package.py b/var/spack/repos/builtin.mock/packages/chain-d/package.py new file mode 100644 index 0000000000..f2e04089ee --- /dev/null +++ b/var/spack/repos/builtin.mock/packages/chain-d/package.py @@ -0,0 +1,31 @@ +# Copyright 2013-2022 Lawrence Livermore National Security, LLC and other +# Spack Project Developers. See the top-level COPYRIGHT file for details. +# +# SPDX-License-Identifier: (Apache-2.0 OR MIT) + +from spack.package import * + + +class ChainD(Package): + """ + Part of a collection of mock packages used for testing depth-first vs + breadth-first traversal. The DAG they form: + a --> b --> c --> d # a chain + a --> c # "skip" connection + a --> d # "skip" connection + Spack's edge order is based on the child package name. + In depth-first traversal we get a tree that looks like a chain: + a + b + c + d + In breadth-first we get the tree: + a + b + c + d + """ + + homepage = "https://example.com" + has_code = False + version("1.0") -- cgit v1.2.3-70-g09d2