2 * Copyright 2015-present 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 = std::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) {
112 ASSERT_NO_THROW(dag->go().get());
116 TEST_F(FutureDAGTest, RemoveNodeComplex) {
125 ASSERT_NO_THROW(dag->go().get());
129 TEST_F(FutureDAGTest, ResetDAG) {
137 ASSERT_NO_THROW(dag->go().get());
141 TEST_F(FutureDAGTest, FanOut) {
147 ASSERT_NO_THROW(dag->go().get());
151 TEST_F(FutureDAGTest, FanIn) {
157 ASSERT_NO_THROW(dag->go().get());
161 TEST_F(FutureDAGTest, FanOutFanIn) {
170 ASSERT_NO_THROW(dag->go().get());
174 TEST_F(FutureDAGTest, Complex) {
207 ASSERT_NO_THROW(dag->go().get());
211 FutureDAG::FutureFunc makeFutureFunc = [] { return makeFuture(); };
213 FutureDAG::FutureFunc throwFunc = [] {
214 return makeFuture<Unit>(std::runtime_error("oops"));
217 TEST_F(FutureDAGTest, ThrowBegin) {
218 auto h1 = dag->add(throwFunc);
219 auto h2 = dag->add(makeFutureFunc);
220 dag->dependency(h1, h2);
221 EXPECT_THROW(dag->go().get(), std::runtime_error);
224 TEST_F(FutureDAGTest, ThrowEnd) {
225 auto h1 = dag->add(makeFutureFunc);
226 auto h2 = dag->add(throwFunc);
227 dag->dependency(h1, h2);
228 EXPECT_THROW(dag->go().get(), std::runtime_error);
231 TEST_F(FutureDAGTest, Cycle1) {
234 EXPECT_THROW(dag->go().get(), std::runtime_error);
237 TEST_F(FutureDAGTest, Cycle2) {
242 EXPECT_THROW(dag->go().get(), std::runtime_error);
245 TEST_F(FutureDAGTest, Cycle3) {
252 EXPECT_THROW(dag->go().get(), std::runtime_error);
255 TEST_F(FutureDAGTest, DestroyBeforeComplete) {
256 auto barrier = std::make_shared<boost::barrier>(2);
259 auto localDag = FutureDAG::create();
260 auto h1 = localDag->add([barrier] {
261 auto p = std::make_shared<Promise<Unit>>();
262 std::thread t([p, barrier] {
267 return p->getFuture();
269 auto h2 = localDag->add(makeFutureFunc);
270 localDag->dependency(h1, h2);
274 ASSERT_NO_THROW(f.get());