1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#pragma once
///@file

#include "lix/libutil/async.hh"
#include "lix/libutil/result.hh"
#include <functional>
#include <kj/async.h>
#include <set>

namespace nix {

template<typename T>
std::set<T> computeClosure(
    std::set<T> startElts,
    std::function<std::set<T>(const T &)> getEdges
)
{
    std::set<T> res, queue = std::move(startElts);

    while (!queue.empty()) {
        std::set<T> next;

        for (auto & e : queue) {
            if (res.insert(e).second) {
                next.merge(getEdges(e));
            }
        }

        queue = std::move(next);
    }

    return res;
}

template<typename T>
kj::Promise<Result<std::set<T>>> computeClosureAsync(
    std::set<T> startElts,
    std::function<kj::Promise<Result<std::set<T>>>(const T &)> getEdges
)
try {
    std::set<T> res, queue = std::move(startElts);

    while (!queue.empty()) {
        std::set<T> next;

        for (auto & e : queue) {
            if (res.insert(e).second) {
                next.merge(LIX_TRY_AWAIT(getEdges(e)));
            }
        }

        queue = std::move(next);
    }

    co_return res;
} catch (...) {
    co_return result::current_exception();
}

}