Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
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)
- Loading branch information
1 parent
57f321f
commit 4bcb217
Showing
3 changed files
with
198 additions
and
84 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -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); | ||
} | ||
} | ||
|
||
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -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 | ||
); | ||
} | ||
|
||
} |