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)
13 std::vector<T> sorted;
14 std::set<T> visited, parents;
16 std::function<void(
const T & path,
const T *
parent)> dfsVisit;
18 dfsVisit = [&](
const T & path,
const T *
parent) {
19 if (parents.count(path))
throw makeCycleError(path, *
parent);
21 if (!visited.insert(path).second)
return;
24 std::set<T> references = getChildren(path);
26 for (
auto &
i : references)
28 if (
i != path && items.count(
i))
31 sorted.push_back(path);
35 for (
auto &
i : items)
38 std::reverse(sorted.begin(), sorted.end());
This file defines two main structs/classes used in nix error handling.
std::optional< CanonPath > parent() const
auto i
Definition lexer.l:2745