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 <folly/experimental/FutureDAG.h>
  17 #include <gtest/gtest.h>
  18 #include <boost/thread/barrier.hpp>
  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 dependency(Handle a, Handle b) {
  33     nodes.at(b)->dependencies.push_back(a);
  34     dag->dependency(a, b);
  35   }
  36
  37   void checkOrder() {
  38     EXPECT_EQ(nodes.size(), order.size());
  39     for (auto& kv : nodes) {
  40       auto handle = kv.first;
  41       auto& node = kv.second;
  42       auto it = order.begin();
  43       while (*it != handle) {
  44         it++;
  45       }
  46       for (auto dep : node->dependencies) {
  47         EXPECT_TRUE(std::find(it, order.end(), dep) == order.end());
  48       }
  49     }
  50   }
  51
  52   struct TestNode {
  53     explicit TestNode(FutureDAGTest* test) {
  54       func = [this, test] {
  55         test->order.push_back(handle);
  56         return Future<Unit>();
  57       };
  58       handle = test->dag->add(func);
  59     }
  60
  61     FutureDAG::FutureFunc func;
  62     Handle handle;
  63     std::vector<Handle> dependencies;
  64   };
  65
  66   std::shared_ptr<FutureDAG> dag = FutureDAG::create();
  67   std::map<Handle, std::unique_ptr<TestNode>> nodes;
  68   std::vector<Handle> order;
  69 };
  70
  71
  72 TEST_F(FutureDAGTest, SingleNode) {
  73   add();
  74   ASSERT_NO_THROW(dag->go().get());
  75   checkOrder();
  76 }
  77
  78 TEST_F(FutureDAGTest, FanOut) {
  79   auto h1 = add();
  80   auto h2 = add();
  81   auto h3 = add();
  82   dependency(h1, h2);
  83   dependency(h1, h3);
  84   ASSERT_NO_THROW(dag->go().get());
  85   checkOrder();
  86 }
  87
  88 TEST_F(FutureDAGTest, FanIn) {
  89   auto h1 = add();
  90   auto h2 = add();
  91   auto h3 = add();
  92   dependency(h1, h3);
  93   dependency(h2, h3);
  94   ASSERT_NO_THROW(dag->go().get());
  95   checkOrder();
  96 }
  97
  98 TEST_F(FutureDAGTest, FanOutFanIn) {
  99   auto h1 = add();
 100   auto h2 = add();
 101   auto h3 = add();
 102   auto h4 = add();
 103   dependency(h1, h3);
 104   dependency(h1, h2);
 105   dependency(h2, h4);
 106   dependency(h3, h4);
 107   ASSERT_NO_THROW(dag->go().get());
 108   checkOrder();
 109 }
 110
 111 TEST_F(FutureDAGTest, Complex) {
 112   auto A = add();
 113   auto B = add();
 114   auto C = add();
 115   auto D = add();
 116   auto E = add();
 117   auto F = add();
 118   auto G = add();
 119   auto H = add();
 120   auto I = add();
 121   auto J = add();
 122   auto K = add();
 123   auto L = add();
 124   auto M = add();
 125   auto N = add();
 126
 127   dependency(A, B);
 128   dependency(A, C);
 129   dependency(A, D);
 130   dependency(A, J);
 131   dependency(C, H);
 132   dependency(D, E);
 133   dependency(E, F);
 134   dependency(E, G);
 135   dependency(F, H);
 136   dependency(G, H);
 137   dependency(H, I);
 138   dependency(J, K);
 139   dependency(K, L);
 140   dependency(K, M);
 141   dependency(L, N);
 142   dependency(I, N);
 143
 144   ASSERT_NO_THROW(dag->go().get());
 145   checkOrder();
 146 }
 147
 148 FutureDAG::FutureFunc makeFutureFunc = []{
 149   return makeFuture();
 150 };
 151
 152 FutureDAG::FutureFunc throwFunc = []{
 153   return makeFuture<Unit>(std::runtime_error("oops"));
 154 };
 155
 156 TEST_F(FutureDAGTest, ThrowBegin) {
 157   auto h1 = dag->add(throwFunc);
 158   auto h2 = dag->add(makeFutureFunc);
 159   dag->dependency(h1, h2);
 160   EXPECT_THROW(dag->go().get(), std::runtime_error);
 161 }
 162
 163 TEST_F(FutureDAGTest, ThrowEnd) {
 164   auto h1 = dag->add(makeFutureFunc);
 165   auto h2 = dag->add(throwFunc);
 166   dag->dependency(h1, h2);
 167   EXPECT_THROW(dag->go().get(), std::runtime_error);
 168 }
 169
 170 TEST_F(FutureDAGTest, Cycle1) {
 171   auto h1 = add();
 172   dependency(h1, h1);
 173   EXPECT_THROW(dag->go().get(), std::runtime_error);
 174 }
 175
 176 TEST_F(FutureDAGTest, Cycle2) {
 177   auto h1 = add();
 178   auto h2 = add();
 179   dependency(h1, h2);
 180   dependency(h2, h1);
 181   EXPECT_THROW(dag->go().get(), std::runtime_error);
 182 }
 183
 184 TEST_F(FutureDAGTest, Cycle3) {
 185   auto h1 = add();
 186   auto h2 = add();
 187   auto h3 = add();
 188   dependency(h1, h2);
 189   dependency(h2, h3);
 190   dependency(h3, h1);
 191   EXPECT_THROW(dag->go().get(), std::runtime_error);
 192 }
 193
 194 TEST_F(FutureDAGTest, DestroyBeforeComplete) {
 195   auto barrier = std::make_shared<boost::barrier>(2);
 196   Future<Unit> f;
 197   {
 198     auto dag = FutureDAG::create();
 199     auto h1 = dag->add([barrier] {
 200       auto p = std::make_shared<Promise<Unit>>();
 201       std::thread t([p, barrier]{
 202         barrier->wait();
 203         p->setValue();
 204       });
 205       t.detach();
 206       return p->getFuture();
 207     });
 208     auto h2 = dag->add(makeFutureFunc);
 209     dag->dependency(h1, h2);
 210     f = dag->go();
 211   }
 212   barrier->wait();
 213   ASSERT_NO_THROW(f.get());
 214 }