2 * Copyright 2016 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
16 #include <boost/thread/barrier.hpp>
17 #include <folly/experimental/FutureDAG.h>
18 #include <folly/portability/GTest.h>
20 using namespace folly;
22 struct FutureDAGTest : public testing::Test {
23 typedef FutureDAG::Handle Handle;
26 auto node = folly::make_unique<TestNode>(this);
27 auto handle = node->handle;
28 nodes.emplace(handle, std::move(node));
34 std::unordered_set<Handle> memo;
35 for (auto& node : nodes) {
36 for (Handle handle : node.second->dependencies) {
40 for (auto& node : nodes) {
41 if (memo.find(node.first) == memo.end()) {
42 source_node = node.first;
45 for (auto it = nodes.cbegin(); it != nodes.cend();) {
46 if (it->first != source_node) {
55 void remove(Handle a) {
56 for (auto& node : nodes) {
57 node.second->dependencies.erase(a);
63 void dependency(Handle a, Handle b) {
64 nodes.at(b)->dependencies.insert(a);
65 dag->dependency(a, b);
69 EXPECT_EQ(nodes.size(), order.size());
70 for (auto& kv : nodes) {
71 auto handle = kv.first;
72 auto& node = kv.second;
73 auto it = order.begin();
74 while (*it != handle) {
77 for (auto dep : node->dependencies) {
78 EXPECT_TRUE(std::find(it, order.end(), dep) == order.end());
84 explicit TestNode(FutureDAGTest* test)
86 test->order.push_back(handle);
87 return Future<Unit>();
89 handle(test->dag->add(func)) {}
91 const FutureDAG::FutureFunc func;
93 std::set<Handle> dependencies;
96 const std::shared_ptr<FutureDAG> dag = FutureDAG::create();
97 std::map<Handle, std::unique_ptr<TestNode>> nodes;
98 std::vector<Handle> order;
101 TEST_F(FutureDAGTest, SingleNode) {
103 ASSERT_NO_THROW(dag->go().get());
107 TEST_F(FutureDAGTest, RemoveSingleNode) {
111 ASSERT_NO_THROW(dag->go().get());
115 TEST_F(FutureDAGTest, RemoveNodeComplex) {
124 ASSERT_NO_THROW(dag->go().get());
128 TEST_F(FutureDAGTest, ResetDAG) {
136 ASSERT_NO_THROW(dag->go().get());
140 TEST_F(FutureDAGTest, FanOut) {
146 ASSERT_NO_THROW(dag->go().get());
150 TEST_F(FutureDAGTest, FanIn) {
156 ASSERT_NO_THROW(dag->go().get());
160 TEST_F(FutureDAGTest, FanOutFanIn) {
169 ASSERT_NO_THROW(dag->go().get());
173 TEST_F(FutureDAGTest, Complex) {
206 ASSERT_NO_THROW(dag->go().get());
210 FutureDAG::FutureFunc makeFutureFunc = [] { return makeFuture(); };
212 FutureDAG::FutureFunc throwFunc = [] {
213 return makeFuture<Unit>(std::runtime_error("oops"));
216 TEST_F(FutureDAGTest, ThrowBegin) {
217 auto h1 = dag->add(throwFunc);
218 auto h2 = dag->add(makeFutureFunc);
219 dag->dependency(h1, h2);
220 EXPECT_THROW(dag->go().get(), std::runtime_error);
223 TEST_F(FutureDAGTest, ThrowEnd) {
224 auto h1 = dag->add(makeFutureFunc);
225 auto h2 = dag->add(throwFunc);
226 dag->dependency(h1, h2);
227 EXPECT_THROW(dag->go().get(), std::runtime_error);
230 TEST_F(FutureDAGTest, Cycle1) {
233 EXPECT_THROW(dag->go().get(), std::runtime_error);
236 TEST_F(FutureDAGTest, Cycle2) {
241 EXPECT_THROW(dag->go().get(), std::runtime_error);
244 TEST_F(FutureDAGTest, Cycle3) {
251 EXPECT_THROW(dag->go().get(), std::runtime_error);
254 TEST_F(FutureDAGTest, DestroyBeforeComplete) {
255 auto barrier = std::make_shared<boost::barrier>(2);
258 auto dag = FutureDAG::create();
259 auto h1 = dag->add([barrier] {
260 auto p = std::make_shared<Promise<Unit>>();
261 std::thread t([p, barrier] {
266 return p->getFuture();
268 auto h2 = dag->add(makeFutureFunc);
269 dag->dependency(h1, h2);
273 ASSERT_NO_THROW(f.get());