folly/experimental/test/FutureDAGTest.cpp

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16 #include <boost/thread/barrier.hpp>
  17 #include <folly/experimental/FutureDAG.h>
  18 #include <gtest/gtest.h>
  19
  20 using namespace folly;
  21
  22 struct FutureDAGTest : public testing::Test {
  23   typedef FutureDAG::Handle Handle;
  24
  25   Handle add() {
  26     auto node = folly::make_unique<TestNode>(this);
  27     auto handle = node->handle;
  28     nodes.emplace(handle, std::move(node));
  29     return handle;
  30   }
  31
  32   void reset() {
  33     Handle source_node;
  34     std::unordered_set<Handle> memo;
  35     for (auto& node : nodes) {
  36       for (Handle handle : node.second->dependencies) {
  37         memo.insert(handle);
  38       }
  39     }
  40     for (auto& node : nodes) {
  41       if (memo.find(node.first) == memo.end()) {
  42         source_node = node.first;
  43       }
  44     }
  45     for (auto it = nodes.cbegin(); it != nodes.cend();) {
  46       if (it->first != source_node) {
  47         it = nodes.erase(it);
  48       } else {
  49         ++it;
  50       }
  51     }
  52     dag->reset();
  53   }
  54
  55   void remove(Handle a) {
  56     for (auto itr = nodes.begin(); itr != nodes.end(); itr++) {
  57       auto& deps = itr->second->dependencies;
  58       if (std::find(deps.begin(), deps.end(), a) != deps.end()) {
  59         deps.erase(deps.begin() + a);
  60       }
  61     }
  62     nodes.erase(a);
  63     dag->remove(a);
  64   }
  65   void dependency(Handle a, Handle b) {
  66     nodes.at(b)->dependencies.push_back(a);
  67     dag->dependency(a, b);
  68   }
  69
  70   void checkOrder() {
  71     EXPECT_EQ(nodes.size(), order.size());
  72     for (auto& kv : nodes) {
  73       auto handle = kv.first;
  74       auto& node = kv.second;
  75       auto it = order.begin();
  76       while (*it != handle) {
  77         it++;
  78       }
  79       for (auto dep : node->dependencies) {
  80         EXPECT_TRUE(std::find(it, order.end(), dep) == order.end());
  81       }
  82     }
  83   }
  84
  85   struct TestNode {
  86     explicit TestNode(FutureDAGTest* test) {
  87       func = [this, test] {
  88         test->order.push_back(handle);
  89         return Future<Unit>();
  90       };
  91       handle = test->dag->add(func);
  92     }
  93
  94     FutureDAG::FutureFunc func;
  95     Handle handle;
  96     std::vector<Handle> dependencies;
  97   };
  98
  99   std::shared_ptr<FutureDAG> dag = FutureDAG::create();
 100   std::map<Handle, std::unique_ptr<TestNode>> nodes;
 101   std::vector<Handle> order;
 102 };
 103
 104 TEST_F(FutureDAGTest, SingleNode) {
 105   add();
 106   ASSERT_NO_THROW(dag->go().get());
 107   checkOrder();
 108 }
 109
 110 TEST_F(FutureDAGTest, RemoveSingleNode) {
 111   auto h1 = add();
 112   auto h2 = add();
 113   remove(h2);
 114   ASSERT_NO_THROW(dag->go().get());
 115   checkOrder();
 116 }
 117
 118 TEST_F(FutureDAGTest, RemoveNodeComplex) {
 119   auto h1 = add();
 120   auto h2 = add();
 121   auto h3 = add();
 122   dependency(h1, h3);
 123   dependency(h2, h1);
 124   remove(h1);
 125   remove(h2);
 126   ASSERT_NO_THROW(dag->go().get());
 127   checkOrder();
 128 }
 129
 130 TEST_F(FutureDAGTest, ResetDAG) {
 131   auto h1 = add();
 132   auto h2 = add();
 133   auto h3 = add();
 134   dependency(h3, h1);
 135   dependency(h2, h3);
 136
 137   reset();
 138   ASSERT_NO_THROW(dag->go().get());
 139   checkOrder();
 140 }
 141
 142 TEST_F(FutureDAGTest, FanOut) {
 143   auto h1 = add();
 144   auto h2 = add();
 145   auto h3 = add();
 146   dependency(h1, h2);
 147   dependency(h1, h3);
 148   ASSERT_NO_THROW(dag->go().get());
 149   checkOrder();
 150 }
 151
 152 TEST_F(FutureDAGTest, FanIn) {
 153   auto h1 = add();
 154   auto h2 = add();
 155   auto h3 = add();
 156   dependency(h1, h3);
 157   dependency(h2, h3);
 158   ASSERT_NO_THROW(dag->go().get());
 159   checkOrder();
 160 }
 161
 162 TEST_F(FutureDAGTest, FanOutFanIn) {
 163   auto h1 = add();
 164   auto h2 = add();
 165   auto h3 = add();
 166   auto h4 = add();
 167   dependency(h1, h3);
 168   dependency(h1, h2);
 169   dependency(h2, h4);
 170   dependency(h3, h4);
 171   ASSERT_NO_THROW(dag->go().get());
 172   checkOrder();
 173 }
 174
 175 TEST_F(FutureDAGTest, Complex) {
 176   auto A = add();
 177   auto B = add();
 178   auto C = add();
 179   auto D = add();
 180   auto E = add();
 181   auto F = add();
 182   auto G = add();
 183   auto H = add();
 184   auto I = add();
 185   auto J = add();
 186   auto K = add();
 187   auto L = add();
 188   auto M = add();
 189   auto N = add();
 190
 191   dependency(A, B);
 192   dependency(A, C);
 193   dependency(A, D);
 194   dependency(A, J);
 195   dependency(C, H);
 196   dependency(D, E);
 197   dependency(E, F);
 198   dependency(E, G);
 199   dependency(F, H);
 200   dependency(G, H);
 201   dependency(H, I);
 202   dependency(J, K);
 203   dependency(K, L);
 204   dependency(K, M);
 205   dependency(L, N);
 206   dependency(I, N);
 207
 208   ASSERT_NO_THROW(dag->go().get());
 209   checkOrder();
 210 }
 211
 212 FutureDAG::FutureFunc makeFutureFunc = [] { return makeFuture(); };
 213
 214 FutureDAG::FutureFunc throwFunc = [] {
 215   return makeFuture<Unit>(std::runtime_error("oops"));
 216 };
 217
 218 TEST_F(FutureDAGTest, ThrowBegin) {
 219   auto h1 = dag->add(throwFunc);
 220   auto h2 = dag->add(makeFutureFunc);
 221   dag->dependency(h1, h2);
 222   EXPECT_THROW(dag->go().get(), std::runtime_error);
 223 }
 224
 225 TEST_F(FutureDAGTest, ThrowEnd) {
 226   auto h1 = dag->add(makeFutureFunc);
 227   auto h2 = dag->add(throwFunc);
 228   dag->dependency(h1, h2);
 229   EXPECT_THROW(dag->go().get(), std::runtime_error);
 230 }
 231
 232 TEST_F(FutureDAGTest, Cycle1) {
 233   auto h1 = add();
 234   dependency(h1, h1);
 235   EXPECT_THROW(dag->go().get(), std::runtime_error);
 236 }
 237
 238 TEST_F(FutureDAGTest, Cycle2) {
 239   auto h1 = add();
 240   auto h2 = add();
 241   dependency(h1, h2);
 242   dependency(h2, h1);
 243   EXPECT_THROW(dag->go().get(), std::runtime_error);
 244 }
 245
 246 TEST_F(FutureDAGTest, Cycle3) {
 247   auto h1 = add();
 248   auto h2 = add();
 249   auto h3 = add();
 250   dependency(h1, h2);
 251   dependency(h2, h3);
 252   dependency(h3, h1);
 253   EXPECT_THROW(dag->go().get(), std::runtime_error);
 254 }
 255
 256 TEST_F(FutureDAGTest, DestroyBeforeComplete) {
 257   auto barrier = std::make_shared<boost::barrier>(2);
 258   Future<Unit> f;
 259   {
 260     auto dag = FutureDAG::create();
 261     auto h1 = dag->add([barrier] {
 262       auto p = std::make_shared<Promise<Unit>>();
 263       std::thread t([p, barrier] {
 264         barrier->wait();
 265         p->setValue();
 266       });
 267       t.detach();
 268       return p->getFuture();
 269     });
 270     auto h2 = dag->add(makeFutureFunc);
 271     dag->dependency(h1, h2);
 272     f = dag->go();
 273   }
 274   barrier->wait();
 275   ASSERT_NO_THROW(f.get());
 276 }