folly/experimental/test/FutureDAGTest.cpp

   1 /*
   2  * Copyright 2017 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 <folly/portability/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& node : nodes) {
  57       node.second->dependencies.erase(a);
  58     }
  59     nodes.erase(a);
  60     dag->remove(a);
  61   }
  62
  63   void dependency(Handle a, Handle b) {
  64     nodes.at(b)->dependencies.insert(a);
  65     dag->dependency(a, b);
  66   }
  67
  68   void checkOrder() {
  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) {
  75         it++;
  76       }
  77       for (auto dep : node->dependencies) {
  78         EXPECT_TRUE(std::find(it, order.end(), dep) == order.end());
  79       }
  80     }
  81   }
  82
  83   struct TestNode {
  84     explicit TestNode(FutureDAGTest* test)
  85         : func([this, test] {
  86             test->order.push_back(handle);
  87             return Future<Unit>();
  88           }),
  89           handle(test->dag->add(func)) {}
  90
  91     const FutureDAG::FutureFunc func;
  92     const Handle handle;
  93     std::set<Handle> dependencies;
  94   };
  95
  96   const std::shared_ptr<FutureDAG> dag = FutureDAG::create();
  97   std::map<Handle, std::unique_ptr<TestNode>> nodes;
  98   std::vector<Handle> order;
  99 };
 100
 101 TEST_F(FutureDAGTest, SingleNode) {
 102   add();
 103   ASSERT_NO_THROW(dag->go().get());
 104   checkOrder();
 105 }
 106
 107 TEST_F(FutureDAGTest, RemoveSingleNode) {
 108   auto h1 = add();
 109   auto h2 = add();
 110   remove(h2);
 111   ASSERT_NO_THROW(dag->go().get());
 112   checkOrder();
 113 }
 114
 115 TEST_F(FutureDAGTest, RemoveNodeComplex) {
 116   auto h1 = add();
 117   auto h2 = add();
 118   auto h3 = add();
 119   dependency(h1, h3);
 120   dependency(h2, h1);
 121   remove(h3);
 122   remove(h2);
 123   remove(h1);
 124   ASSERT_NO_THROW(dag->go().get());
 125   checkOrder();
 126 }
 127
 128 TEST_F(FutureDAGTest, ResetDAG) {
 129   auto h1 = add();
 130   auto h2 = add();
 131   auto h3 = add();
 132   dependency(h3, h1);
 133   dependency(h2, h3);
 134
 135   reset();
 136   ASSERT_NO_THROW(dag->go().get());
 137   checkOrder();
 138 }
 139
 140 TEST_F(FutureDAGTest, FanOut) {
 141   auto h1 = add();
 142   auto h2 = add();
 143   auto h3 = add();
 144   dependency(h1, h2);
 145   dependency(h1, h3);
 146   ASSERT_NO_THROW(dag->go().get());
 147   checkOrder();
 148 }
 149
 150 TEST_F(FutureDAGTest, FanIn) {
 151   auto h1 = add();
 152   auto h2 = add();
 153   auto h3 = add();
 154   dependency(h1, h3);
 155   dependency(h2, h3);
 156   ASSERT_NO_THROW(dag->go().get());
 157   checkOrder();
 158 }
 159
 160 TEST_F(FutureDAGTest, FanOutFanIn) {
 161   auto h1 = add();
 162   auto h2 = add();
 163   auto h3 = add();
 164   auto h4 = add();
 165   dependency(h1, h3);
 166   dependency(h1, h2);
 167   dependency(h2, h4);
 168   dependency(h3, h4);
 169   ASSERT_NO_THROW(dag->go().get());
 170   checkOrder();
 171 }
 172
 173 TEST_F(FutureDAGTest, Complex) {
 174   auto A = add();
 175   auto B = add();
 176   auto C = add();
 177   auto D = add();
 178   auto E = add();
 179   auto F = add();
 180   auto G = add();
 181   auto H = add();
 182   auto I = add();
 183   auto J = add();
 184   auto K = add();
 185   auto L = add();
 186   auto M = add();
 187   auto N = add();
 188
 189   dependency(A, B);
 190   dependency(A, C);
 191   dependency(A, D);
 192   dependency(A, J);
 193   dependency(C, H);
 194   dependency(D, E);
 195   dependency(E, F);
 196   dependency(E, G);
 197   dependency(F, H);
 198   dependency(G, H);
 199   dependency(H, I);
 200   dependency(J, K);
 201   dependency(K, L);
 202   dependency(K, M);
 203   dependency(L, N);
 204   dependency(I, N);
 205
 206   ASSERT_NO_THROW(dag->go().get());
 207   checkOrder();
 208 }
 209
 210 FutureDAG::FutureFunc makeFutureFunc = [] { return makeFuture(); };
 211
 212 FutureDAG::FutureFunc throwFunc = [] {
 213   return makeFuture<Unit>(std::runtime_error("oops"));
 214 };
 215
 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);
 221 }
 222
 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);
 228 }
 229
 230 TEST_F(FutureDAGTest, Cycle1) {
 231   auto h1 = add();
 232   dependency(h1, h1);
 233   EXPECT_THROW(dag->go().get(), std::runtime_error);
 234 }
 235
 236 TEST_F(FutureDAGTest, Cycle2) {
 237   auto h1 = add();
 238   auto h2 = add();
 239   dependency(h1, h2);
 240   dependency(h2, h1);
 241   EXPECT_THROW(dag->go().get(), std::runtime_error);
 242 }
 243
 244 TEST_F(FutureDAGTest, Cycle3) {
 245   auto h1 = add();
 246   auto h2 = add();
 247   auto h3 = add();
 248   dependency(h1, h2);
 249   dependency(h2, h3);
 250   dependency(h3, h1);
 251   EXPECT_THROW(dag->go().get(), std::runtime_error);
 252 }
 253
 254 TEST_F(FutureDAGTest, DestroyBeforeComplete) {
 255   auto barrier = std::make_shared<boost::barrier>(2);
 256   Future<Unit> f;
 257   {
 258     auto localDag = FutureDAG::create();
 259     auto h1 = localDag->add([barrier] {
 260       auto p = std::make_shared<Promise<Unit>>();
 261       std::thread t([p, barrier] {
 262         barrier->wait();
 263         p->setValue();
 264       });
 265       t.detach();
 266       return p->getFuture();
 267     });
 268     auto h2 = localDag->add(makeFutureFunc);
 269     localDag->dependency(h1, h2);
 270     f = localDag->go();
 271   }
 272   barrier->wait();
 273   ASSERT_NO_THROW(f.get());
 274 }