summaryrefslogtreecommitdiff
path: root/share
diff options
context:
space:
mode:
authorHarmen Stoppels <harmenstoppels@gmail.com>2022-11-02 07:04:47 +0100
committerGitHub <noreply@github.com>2022-11-01 23:04:47 -0700
commit4bad9f9b1380e33499b6f8e06531898d8b7d679f (patch)
treed3b169b9a5db7bc819dcc0abb8e3b1852d076878 /share
parent353e31e72a8fb56ec864897004eff72aecaf2417 (diff)
downloadspack-4bad9f9b1380e33499b6f8e06531898d8b7d679f.tar.gz
spack-4bad9f9b1380e33499b6f8e06531898d8b7d679f.tar.bz2
spack-4bad9f9b1380e33499b6f8e06531898d8b7d679f.tar.xz
spack-4bad9f9b1380e33499b6f8e06531898d8b7d679f.zip
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)
Diffstat (limited to 'share')
0 files changed, 0 insertions, 0 deletions