Extract a generic `computeClosure` function

Move the `closure` logic of `computeFSClosure` to its own (templated) function.

This doesn’t bring much by itself (except for the ability to properly
test the “closure” functionality independently from the rest), but it
allows reusing it (in particular for the realisations which will require
a very similar closure computation)

2 files changed, 139 insertions, 0 deletions

diff --git a/src/libutil/closure.hh b/src/libutil/closure.hh
new file mode 100644
index 000000000..779b9b2d5
--- /dev/null
+++ b/src/libutil/closure.hh
@@ -0,0 +1,69 @@
+#include <set>
+#include <future>
+#include "sync.hh"
+
+using std::set;
+
+namespace nix {
+
+template<typename T>
+using GetEdgesAsync = std::function<void(const T &, std::function<void(std::promise<set<T>> &)>)>;
+
+template<typename T>
+void computeClosure(
+    const set<T> startElts,
+    set<T> & res,
+    GetEdgesAsync<T> getEdgesAsync
+)
+{
+    struct State
+    {
+        size_t pending;
+        set<T> & res;
+        std::exception_ptr exc;
+    };
+
+    Sync<State> state_(State{0, res, 0});
+
+    std::function<void(const T &)> enqueue;
+
+    std::condition_variable done;
+
+    enqueue = [&](const T & current) -> void {
+        {
+            auto state(state_.lock());
+            if (state->exc) return;
+            if (!state->res.insert(current).second) return;
+            state->pending++;
+        }
+
+        getEdgesAsync(current, [&](std::promise<set<T>> & prom) {
+            try {
+                auto children = prom.get_future().get();
+                for (auto & child : children)
+                    enqueue(child);
+                {
+                    auto state(state_.lock());
+                    assert(state->pending);
+                    if (!--state->pending) done.notify_one();
+                }
+            } catch (...) {
+                auto state(state_.lock());
+                if (!state->exc) state->exc = std::current_exception();
+                assert(state->pending);
+                if (!--state->pending) done.notify_one();
+            };
+        });
+    };
+
+    for (auto & startElt : startElts)
+        enqueue(startElt);
+
+    {
+        auto state(state_.lock());
+        while (state->pending) state.wait(done);
+        if (state->exc) std::rethrow_exception(state->exc);
+    }
+}
+
+}
diff --git a/src/libutil/tests/closure.cc b/src/libutil/tests/closure.cc
new file mode 100644
index 000000000..7597e7807
--- /dev/null
+++ b/src/libutil/tests/closure.cc
@@ -0,0 +1,70 @@
+#include "closure.hh"
+#include <gtest/gtest.h>
+
+namespace nix {
+
+using namespace std;
+
+map<string, set<string>> testGraph = {
+    { "A", { "B", "C", "G" } },
+    { "B", { "A" } }, // Loops back to A
+    { "C", { "F" } }, // Indirect reference
+    { "D", { "A" } }, // Not reachable, but has backreferences
+    { "E", {} }, // Just not reachable
+    { "F", {} },
+    { "G", { "G" } }, // Self reference
+};
+
+TEST(closure, correctClosure) {
+    set<string> aClosure;
+    set<string> expectedClosure = {"A", "B", "C", "F", "G"};
+    computeClosure<string>(
+        {"A"},
+        aClosure,
+        [&](const string currentNode, function<void(promise<set<string>> &)> processEdges) {
+            promise<set<string>> promisedNodes;
+            promisedNodes.set_value(testGraph[currentNode]);
+            processEdges(promisedNodes);
+        }
+    );
+
+    ASSERT_EQ(aClosure, expectedClosure);
+}
+
+TEST(closure, properlyHandlesDirectExceptions) {
+    struct TestExn {};
+    set<string> aClosure;
+    EXPECT_THROW(
+        computeClosure<string>(
+            {"A"},
+            aClosure,
+            [&](const string currentNode, function<void(promise<set<string>> &)> processEdges) {
+                throw TestExn();
+            }
+        ),
+        TestExn
+    );
+}
+
+TEST(closure, properlyHandlesExceptionsInPromise) {
+    struct TestExn {};
+    set<string> aClosure;
+    EXPECT_THROW(
+        computeClosure<string>(
+            {"A"},
+            aClosure,
+            [&](const string currentNode, function<void(promise<set<string>> &)> processEdges) {
+                promise<set<string>> promise;
+                try {
+                    throw TestExn();
+                } catch (...) {
+                    promise.set_exception(std::current_exception());
+                }
+                processEdges(promise);
+            }
+        ),
+        TestExn
+    );
+}
+
+}