Nix 2.26.3
Nix, the purely functional package manager; unstable internal interfaces
 
Loading...
Searching...
No Matches
topo-sort.hh
Go to the documentation of this file.
1#pragma once
3
4#include "error.hh"
5
6namespace nix {
7
8template<typename T>
9std::vector<T> topoSort(std::set<T> items,
10 std::function<std::set<T>(const T &)> getChildren,
11 std::function<Error(const T &, const T &)> makeCycleError)
12{
13 std::vector<T> sorted;
14 std::set<T> visited, parents;
15
16 std::function<void(const T & path, const T * parent)> dfsVisit;
17
18 dfsVisit = [&](const T & path, const T * parent) {
19 if (parents.count(path)) throw makeCycleError(path, *parent);
20
21 if (!visited.insert(path).second) return;
22 parents.insert(path);
23
24 std::set<T> references = getChildren(path);
25
26 for (auto & i : references)
27 /* Don't traverse into items that don't exist in our starting set. */
28 if (i != path && items.count(i))
29 dfsVisit(i, &path);
30
31 sorted.push_back(path);
32 parents.erase(path);
33 };
34
35 for (auto & i : items)
36 dfsVisit(i, nullptr);
37
38 std::reverse(sorted.begin(), sorted.end());
39
40 return sorted;
41}
42
43}
This file defines two main structs/classes used in nix error handling.
std::optional< CanonPath > parent() const
auto i
Definition lexer.l:2745