folly/futures/Future-inl.h

   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
  17 #pragma once
  18
  19 #include <algorithm>
  20 #include <cassert>
  21 #include <chrono>
  22 #include <thread>
  23
  24 #include <folly/Baton.h>
  25 #include <folly/Optional.h>
  26 #include <folly/executors/InlineExecutor.h>
  27 #include <folly/futures/Timekeeper.h>
  28 #include <folly/futures/detail/Core.h>
  29
  30 #ifndef FOLLY_FUTURE_USING_FIBER
  31 #if FOLLY_MOBILE || defined(__APPLE__)
  32 #define FOLLY_FUTURE_USING_FIBER 0
  33 #else
  34 #define FOLLY_FUTURE_USING_FIBER 1
  35 #include <folly/fibers/Baton.h>
  36 #endif
  37 #endif
  38
  39 namespace folly {
  40
  41 class Timekeeper;
  42
  43 namespace futures {
  44 namespace detail {
  45 #if FOLLY_FUTURE_USING_FIBER
  46 typedef folly::fibers::Baton FutureBatonType;
  47 #else
  48 typedef folly::Baton<> FutureBatonType;
  49 #endif
  50 } // namespace detail
  51 } // namespace futures
  52
  53 namespace detail {
  54 std::shared_ptr<Timekeeper> getTimekeeperSingleton();
  55 } // namespace detail
  56
  57 namespace futures {
  58 namespace detail {
  59 //  Guarantees that the stored functor is destructed before the stored promise
  60 //  may be fulfilled. Assumes the stored functor to be noexcept-destructible.
  61 template <typename T, typename F>
  62 class CoreCallbackState {
  63  public:
  64   template <typename FF>
  65   CoreCallbackState(Promise<T>&& promise, FF&& func) noexcept(
  66       noexcept(F(std::declval<FF>())))
  67       : func_(std::forward<FF>(func)), promise_(std::move(promise)) {
  68     assert(before_barrier());
  69   }
  70
  71   CoreCallbackState(CoreCallbackState&& that) noexcept(
  72       noexcept(F(std::declval<F>()))) {
  73     if (that.before_barrier()) {
  74       new (&func_) F(std::move(that.func_));
  75       promise_ = that.stealPromise();
  76     }
  77   }
  78
  79   CoreCallbackState& operator=(CoreCallbackState&&) = delete;
  80
  81   ~CoreCallbackState() {
  82     if (before_barrier()) {
  83       stealPromise();
  84     }
  85   }
  86
  87   template <typename... Args>
  88   auto invoke(Args&&... args) noexcept(
  89       noexcept(std::declval<F&&>()(std::declval<Args&&>()...))) {
  90     assert(before_barrier());
  91     return std::move(func_)(std::forward<Args>(args)...);
  92   }
  93
  94   template <typename... Args>
  95   auto tryInvoke(Args&&... args) noexcept {
  96     return makeTryWith([&] { return invoke(std::forward<Args>(args)...); });
  97   }
  98
  99   void setTry(Try<T>&& t) {
 100     stealPromise().setTry(std::move(t));
 101   }
 102
 103   void setException(exception_wrapper&& ew) {
 104     stealPromise().setException(std::move(ew));
 105   }
 106
 107   Promise<T> stealPromise() noexcept {
 108     assert(before_barrier());
 109     func_.~F();
 110     return std::move(promise_);
 111   }
 112
 113  private:
 114   bool before_barrier() const noexcept {
 115     return !promise_.isFulfilled();
 116   }
 117
 118   union {
 119     F func_;
 120   };
 121   Promise<T> promise_{Promise<T>::makeEmpty()};
 122 };
 123
 124 template <typename T, typename F>
 125 inline auto makeCoreCallbackState(Promise<T>&& p, F&& f) noexcept(
 126     noexcept(CoreCallbackState<T, _t<std::decay<F>>>(
 127         std::declval<Promise<T>&&>(),
 128         std::declval<F&&>()))) {
 129   return CoreCallbackState<T, _t<std::decay<F>>>(
 130       std::move(p), std::forward<F>(f));
 131 }
 132
 133 template <class T>
 134 FutureBase<T>::FutureBase(SemiFuture<T>&& other) noexcept : core_(other.core_) {
 135   other.core_ = nullptr;
 136 }
 137
 138 template <class T>
 139 FutureBase<T>::FutureBase(Future<T>&& other) noexcept : core_(other.core_) {
 140   other.core_ = nullptr;
 141 }
 142
 143 template <class T>
 144 template <class T2, typename>
 145 FutureBase<T>::FutureBase(T2&& val)
 146     : core_(new futures::detail::Core<T>(Try<T>(std::forward<T2>(val)))) {}
 147
 148 template <class T>
 149 template <typename T2>
 150 FutureBase<T>::FutureBase(
 151     typename std::enable_if<std::is_same<Unit, T2>::value>::type*)
 152     : core_(new futures::detail::Core<T>(Try<T>(T()))) {}
 153
 154 template <class T>
 155 template <
 156     class... Args,
 157     typename std::enable_if<std::is_constructible<T, Args&&...>::value, int>::
 158         type>
 159 FutureBase<T>::FutureBase(in_place_t, Args&&... args)
 160     : core_(
 161           new futures::detail::Core<T>(in_place, std::forward<Args>(args)...)) {
 162 }
 163
 164 template <class T>
 165 template <class FutureType>
 166 void FutureBase<T>::assign(FutureType& other) noexcept {
 167   std::swap(core_, other.core_);
 168 }
 169
 170 template <class T>
 171 FutureBase<T>::~FutureBase() {
 172   detach();
 173 }
 174
 175 template <class T>
 176 T& FutureBase<T>::value() & {
 177   throwIfInvalid();
 178
 179   return core_->getTry().value();
 180 }
 181
 182 template <class T>
 183 T const& FutureBase<T>::value() const& {
 184   throwIfInvalid();
 185
 186   return core_->getTry().value();
 187 }
 188
 189 template <class T>
 190 T&& FutureBase<T>::value() && {
 191   throwIfInvalid();
 192
 193   return std::move(core_->getTry().value());
 194 }
 195
 196 template <class T>
 197 T const&& FutureBase<T>::value() const&& {
 198   throwIfInvalid();
 199
 200   return std::move(core_->getTry().value());
 201 }
 202
 203 template <class T>
 204 inline Future<T> FutureBase<T>::via(Executor* executor, int8_t priority) && {
 205   throwIfInvalid();
 206
 207   setExecutor(executor, priority);
 208
 209   auto newFuture = Future<T>(core_);
 210   core_ = nullptr;
 211   return newFuture;
 212 }
 213
 214 template <class T>
 215 bool FutureBase<T>::isReady() const {
 216   throwIfInvalid();
 217   return core_->ready();
 218 }
 219
 220 template <class T>
 221 bool FutureBase<T>::hasValue() {
 222   return getTry().hasValue();
 223 }
 224
 225 template <class T>
 226 bool FutureBase<T>::hasException() {
 227   return getTry().hasException();
 228 }
 229
 230 template <class T>
 231 void FutureBase<T>::detach() {
 232   if (core_) {
 233     core_->detachFuture();
 234     core_ = nullptr;
 235   }
 236 }
 237
 238 template <class T>
 239 Try<T>& FutureBase<T>::getTry() {
 240   throwIfInvalid();
 241
 242   return core_->getTry();
 243 }
 244
 245 template <class T>
 246 void FutureBase<T>::throwIfInvalid() const {
 247   if (!core_) {
 248     throwNoState();
 249   }
 250 }
 251
 252 template <class T>
 253 Optional<Try<T>> FutureBase<T>::poll() {
 254   Optional<Try<T>> o;
 255   if (core_->ready()) {
 256     o = std::move(core_->getTry());
 257   }
 258   return o;
 259 }
 260
 261 template <class T>
 262 void FutureBase<T>::raise(exception_wrapper exception) {
 263   core_->raise(std::move(exception));
 264 }
 265
 266 template <class T>
 267 template <class F>
 268 void FutureBase<T>::setCallback_(F&& func) {
 269   throwIfInvalid();
 270   core_->setCallback(std::forward<F>(func));
 271 }
 272
 273 template <class T>
 274 FutureBase<T>::FutureBase(futures::detail::EmptyConstruct) noexcept
 275     : core_(nullptr) {}
 276
 277 // then
 278
 279 // Variant: returns a value
 280 // e.g. f.then([](Try<T>&& t){ return t.value(); });
 281 template <class T>
 282 template <typename F, typename R, bool isTry, typename... Args>
 283 typename std::enable_if<!R::ReturnsFuture::value, typename R::Return>::type
 284 FutureBase<T>::thenImplementation(
 285     F&& func,
 286     futures::detail::argResult<isTry, F, Args...>) {
 287   static_assert(sizeof...(Args) <= 1, "Then must take zero/one argument");
 288   typedef typename R::ReturnsFuture::Inner B;
 289
 290   this->throwIfInvalid();
 291
 292   Promise<B> p;
 293   p.core_->setInterruptHandlerNoLock(this->core_->getInterruptHandler());
 294
 295   // grab the Future now before we lose our handle on the Promise
 296   auto f = p.getFuture();
 297   f.core_->setExecutorNoLock(this->getExecutor());
 298
 299   /* This is a bit tricky.
 300
 301      We can't just close over *this in case this Future gets moved. So we
 302      make a new dummy Future. We could figure out something more
 303      sophisticated that avoids making a new Future object when it can, as an
 304      optimization. But this is correct.
 305
 306      core_ can't be moved, it is explicitly disallowed (as is copying). But
 307      if there's ever a reason to allow it, this is one place that makes that
 308      assumption and would need to be fixed. We use a standard shared pointer
 309      for core_ (by copying it in), which means in essence obj holds a shared
 310      pointer to itself.  But this shouldn't leak because Promise will not
 311      outlive the continuation, because Promise will setException() with a
 312      broken Promise if it is destructed before completed. We could use a
 313      weak pointer but it would have to be converted to a shared pointer when
 314      func is executed (because the Future returned by func may possibly
 315      persist beyond the callback, if it gets moved), and so it is an
 316      optimization to just make it shared from the get-go.
 317
 318      Two subtle but important points about this design. futures::detail::Core
 319      has no back pointers to Future or Promise, so if Future or Promise get
 320      moved (and they will be moved in performant code) we don't have to do
 321      anything fancy. And because we store the continuation in the
 322      futures::detail::Core, not in the Future, we can execute the continuation
 323      even after the Future has gone out of scope. This is an intentional design
 324      decision. It is likely we will want to be able to cancel a continuation
 325      in some circumstances, but I think it should be explicit not implicit
 326      in the destruction of the Future used to create it.
 327      */
 328   this->setCallback_(
 329       [state = futures::detail::makeCoreCallbackState(
 330            std::move(p), std::forward<F>(func))](Try<T>&& t) mutable {
 331
 332         if (!isTry && t.hasException()) {
 333           state.setException(std::move(t.exception()));
 334         } else {
 335           state.setTry(makeTryWith(
 336               [&] { return state.invoke(t.template get<isTry, Args>()...); }));
 337         }
 338       });
 339   return f;
 340 }
 341
 342 // Variant: returns a Future
 343 // e.g. f.then([](T&& t){ return makeFuture<T>(t); });
 344 template <class T>
 345 template <typename F, typename R, bool isTry, typename... Args>
 346 typename std::enable_if<R::ReturnsFuture::value, typename R::Return>::type
 347 FutureBase<T>::thenImplementation(
 348     F&& func,
 349     futures::detail::argResult<isTry, F, Args...>) {
 350   static_assert(sizeof...(Args) <= 1, "Then must take zero/one argument");
 351   typedef typename R::ReturnsFuture::Inner B;
 352   this->throwIfInvalid();
 353
 354   Promise<B> p;
 355   p.core_->setInterruptHandlerNoLock(this->core_->getInterruptHandler());
 356
 357   // grab the Future now before we lose our handle on the Promise
 358   auto f = p.getFuture();
 359   f.core_->setExecutorNoLock(this->getExecutor());
 360
 361   this->setCallback_(
 362       [state = futures::detail::makeCoreCallbackState(
 363            std::move(p), std::forward<F>(func))](Try<T>&& t) mutable {
 364         if (!isTry && t.hasException()) {
 365           state.setException(std::move(t.exception()));
 366         } else {
 367           auto tf2 = state.tryInvoke(t.template get<isTry, Args>()...);
 368           if (tf2.hasException()) {
 369             state.setException(std::move(tf2.exception()));
 370           } else {
 371             tf2->setCallback_([p = state.stealPromise()](Try<B> && b) mutable {
 372               p.setTry(std::move(b));
 373             });
 374           }
 375         }
 376       });
 377
 378   return f;
 379 }
 380 } // namespace detail
 381 } // namespace futures
 382
 383 template <class T>
 384 SemiFuture<typename std::decay<T>::type> makeSemiFuture(T&& t) {
 385   return makeSemiFuture(Try<typename std::decay<T>::type>(std::forward<T>(t)));
 386 }
 387
 388 // makeSemiFutureWith(SemiFuture<T>()) -> SemiFuture<T>
 389 template <class F>
 390 typename std::enable_if<
 391     isSemiFuture<typename std::result_of<F()>::type>::value,
 392     typename std::result_of<F()>::type>::type
 393 makeSemiFutureWith(F&& func) {
 394   using InnerType =
 395       typename isSemiFuture<typename std::result_of<F()>::type>::Inner;
 396   try {
 397     return std::forward<F>(func)();
 398   } catch (std::exception& e) {
 399     return makeSemiFuture<InnerType>(
 400         exception_wrapper(std::current_exception(), e));
 401   } catch (...) {
 402     return makeSemiFuture<InnerType>(
 403         exception_wrapper(std::current_exception()));
 404   }
 405 }
 406
 407 // makeSemiFutureWith(T()) -> SemiFuture<T>
 408 // makeSemiFutureWith(void()) -> SemiFuture<Unit>
 409 template <class F>
 410 typename std::enable_if<
 411     !(isSemiFuture<typename std::result_of<F()>::type>::value),
 412     SemiFuture<Unit::LiftT<typename std::result_of<F()>::type>>>::type
 413 makeSemiFutureWith(F&& func) {
 414   using LiftedResult = Unit::LiftT<typename std::result_of<F()>::type>;
 415   return makeSemiFuture<LiftedResult>(
 416       makeTryWith([&func]() mutable { return std::forward<F>(func)(); }));
 417 }
 418
 419 template <class T>
 420 SemiFuture<T> makeSemiFuture(std::exception_ptr const& e) {
 421   return makeSemiFuture(Try<T>(e));
 422 }
 423
 424 template <class T>
 425 SemiFuture<T> makeSemiFuture(exception_wrapper ew) {
 426   return makeSemiFuture(Try<T>(std::move(ew)));
 427 }
 428
 429 template <class T, class E>
 430 typename std::
 431     enable_if<std::is_base_of<std::exception, E>::value, SemiFuture<T>>::type
 432     makeSemiFuture(E const& e) {
 433   return makeSemiFuture(Try<T>(make_exception_wrapper<E>(e)));
 434 }
 435
 436 template <class T>
 437 SemiFuture<T> makeSemiFuture(Try<T>&& t) {
 438   return SemiFuture<T>(new futures::detail::Core<T>(std::move(t)));
 439 }
 440
 441 // This must be defined after the constructors to avoid a bug in MSVC
 442 // https://connect.microsoft.com/VisualStudio/feedback/details/3142777/out-of-line-constructor-definition-after-implicit-reference-causes-incorrect-c2244
 443 inline SemiFuture<Unit> makeSemiFuture() {
 444   return makeSemiFuture(Unit{});
 445 }
 446
 447 template <class T>
 448 SemiFuture<T> SemiFuture<T>::makeEmpty() {
 449   return SemiFuture<T>(futures::detail::EmptyConstruct{});
 450 }
 451
 452 template <class T>
 453 SemiFuture<T>::SemiFuture(SemiFuture<T>&& other) noexcept
 454     : futures::detail::FutureBase<T>(std::move(other)) {}
 455
 456 template <class T>
 457 SemiFuture<T>::SemiFuture(Future<T>&& other) noexcept
 458     : futures::detail::FutureBase<T>(std::move(other)) {
 459   // SemiFuture should not have an executor on construction
 460   if (this->core_) {
 461     this->setExecutor(nullptr);
 462   }
 463 }
 464
 465 template <class T>
 466 SemiFuture<T>& SemiFuture<T>::operator=(SemiFuture<T>&& other) noexcept {
 467   this->assign(other);
 468   return *this;
 469 }
 470
 471 template <class T>
 472 SemiFuture<T>& SemiFuture<T>::operator=(Future<T>&& other) noexcept {
 473   this->assign(other);
 474   // SemiFuture should not have an executor on construction
 475   if (this->core_) {
 476     this->setExecutor(nullptr);
 477   }
 478   return *this;
 479 }
 480
 481 template <class T>
 482 Future<T> Future<T>::makeEmpty() {
 483   return Future<T>(futures::detail::EmptyConstruct{});
 484 }
 485
 486 template <class T>
 487 Future<T>::Future(Future<T>&& other) noexcept
 488     : futures::detail::FutureBase<T>(std::move(other)) {}
 489
 490 template <class T>
 491 Future<T>& Future<T>::operator=(Future<T>&& other) noexcept {
 492   this->assign(other);
 493   return *this;
 494 }
 495
 496 template <class T>
 497 template <
 498     class T2,
 499     typename std::enable_if<
 500         !std::is_same<T, typename std::decay<T2>::type>::value &&
 501             std::is_constructible<T, T2&&>::value &&
 502             std::is_convertible<T2&&, T>::value,
 503         int>::type>
 504 Future<T>::Future(Future<T2>&& other)
 505     : Future(std::move(other).then([](T2&& v) { return T(std::move(v)); })) {}
 506
 507 template <class T>
 508 template <
 509     class T2,
 510     typename std::enable_if<
 511         !std::is_same<T, typename std::decay<T2>::type>::value &&
 512             std::is_constructible<T, T2&&>::value &&
 513             !std::is_convertible<T2&&, T>::value,
 514         int>::type>
 515 Future<T>::Future(Future<T2>&& other)
 516     : Future(std::move(other).then([](T2&& v) { return T(std::move(v)); })) {}
 517
 518 template <class T>
 519 template <
 520     class T2,
 521     typename std::enable_if<
 522         !std::is_same<T, typename std::decay<T2>::type>::value &&
 523             std::is_constructible<T, T2&&>::value,
 524         int>::type>
 525 Future<T>& Future<T>::operator=(Future<T2>&& other) {
 526   return operator=(
 527       std::move(other).then([](T2&& v) { return T(std::move(v)); }));
 528 }
 529
 530 // unwrap
 531
 532 template <class T>
 533 template <class F>
 534 typename std::
 535     enable_if<isFuture<F>::value, Future<typename isFuture<T>::Inner>>::type
 536     Future<T>::unwrap() {
 537   return then([](Future<typename isFuture<T>::Inner> internal_future) {
 538     return internal_future;
 539   });
 540 }
 541
 542 template <class T>
 543 inline Future<T> Future<T>::via(Executor* executor, int8_t priority) & {
 544   this->throwIfInvalid();
 545   Promise<T> p;
 546   auto f = p.getFuture();
 547   auto func = [p = std::move(p)](Try<T>&& t) mutable {
 548     p.setTry(std::move(t));
 549   };
 550   using R = futures::detail::callableResult<T, decltype(func)>;
 551   this->template thenImplementation<decltype(func), R>(
 552       std::move(func), typename R::Arg());
 553   return std::move(f).via(executor, priority);
 554 }
 555
 556 template <typename T>
 557 template <typename R, typename Caller, typename... Args>
 558   Future<typename isFuture<R>::Inner>
 559 Future<T>::then(R(Caller::*func)(Args...), Caller *instance) {
 560   typedef typename std::remove_cv<typename std::remove_reference<
 561       typename futures::detail::ArgType<Args...>::FirstArg>::type>::type
 562       FirstArg;
 563
 564   return then([instance, func](Try<T>&& t){
 565     return (instance->*func)(t.template get<isTry<FirstArg>::value, Args>()...);
 566   });
 567 }
 568
 569 template <class T>
 570 Future<Unit> Future<T>::then() {
 571   return then([] () {});
 572 }
 573
 574 // onError where the callback returns T
 575 template <class T>
 576 template <class F>
 577 typename std::enable_if<
 578     !futures::detail::callableWith<F, exception_wrapper>::value &&
 579         !futures::detail::callableWith<F, exception_wrapper&>::value &&
 580         !futures::detail::Extract<F>::ReturnsFuture::value,
 581     Future<T>>::type
 582 Future<T>::onError(F&& func) {
 583   typedef std::remove_reference_t<
 584       typename futures::detail::Extract<F>::FirstArg>
 585       Exn;
 586   static_assert(
 587       std::is_same<typename futures::detail::Extract<F>::RawReturn, T>::value,
 588       "Return type of onError callback must be T or Future<T>");
 589
 590   Promise<T> p;
 591   p.core_->setInterruptHandlerNoLock(this->core_->getInterruptHandler());
 592   auto f = p.getFuture();
 593
 594   this->setCallback_(
 595       [state = futures::detail::makeCoreCallbackState(
 596            std::move(p), std::forward<F>(func))](Try<T>&& t) mutable {
 597         if (auto e = t.template tryGetExceptionObject<Exn>()) {
 598           state.setTry(makeTryWith([&] { return state.invoke(*e); }));
 599         } else {
 600           state.setTry(std::move(t));
 601         }
 602       });
 603
 604   return f;
 605 }
 606
 607 // onError where the callback returns Future<T>
 608 template <class T>
 609 template <class F>
 610 typename std::enable_if<
 611     !futures::detail::callableWith<F, exception_wrapper>::value &&
 612         !futures::detail::callableWith<F, exception_wrapper&>::value &&
 613         futures::detail::Extract<F>::ReturnsFuture::value,
 614     Future<T>>::type
 615 Future<T>::onError(F&& func) {
 616   static_assert(
 617       std::is_same<typename futures::detail::Extract<F>::Return, Future<T>>::
 618           value,
 619       "Return type of onError callback must be T or Future<T>");
 620   typedef std::remove_reference_t<
 621       typename futures::detail::Extract<F>::FirstArg>
 622       Exn;
 623
 624   Promise<T> p;
 625   auto f = p.getFuture();
 626
 627   this->setCallback_(
 628       [state = futures::detail::makeCoreCallbackState(
 629            std::move(p), std::forward<F>(func))](Try<T>&& t) mutable {
 630         if (auto e = t.template tryGetExceptionObject<Exn>()) {
 631           auto tf2 = state.tryInvoke(*e);
 632           if (tf2.hasException()) {
 633             state.setException(std::move(tf2.exception()));
 634           } else {
 635             tf2->setCallback_([p = state.stealPromise()](Try<T> && t3) mutable {
 636               p.setTry(std::move(t3));
 637             });
 638           }
 639         } else {
 640           state.setTry(std::move(t));
 641         }
 642       });
 643
 644   return f;
 645 }
 646
 647 template <class T>
 648 template <class F>
 649 Future<T> Future<T>::ensure(F&& func) {
 650   return this->then([funcw = std::forward<F>(func)](Try<T> && t) mutable {
 651     std::move(funcw)();
 652     return makeFuture(std::move(t));
 653   });
 654 }
 655
 656 template <class T>
 657 template <class F>
 658 Future<T> Future<T>::onTimeout(Duration dur, F&& func, Timekeeper* tk) {
 659   return within(dur, tk).onError([funcw = std::forward<F>(func)](
 660       TimedOut const&) { return std::move(funcw)(); });
 661 }
 662
 663 template <class T>
 664 template <class F>
 665 typename std::enable_if<
 666     futures::detail::callableWith<F, exception_wrapper>::value &&
 667         futures::detail::Extract<F>::ReturnsFuture::value,
 668     Future<T>>::type
 669 Future<T>::onError(F&& func) {
 670   static_assert(
 671       std::is_same<typename futures::detail::Extract<F>::Return, Future<T>>::
 672           value,
 673       "Return type of onError callback must be T or Future<T>");
 674
 675   Promise<T> p;
 676   auto f = p.getFuture();
 677   this->setCallback_(
 678       [state = futures::detail::makeCoreCallbackState(
 679            std::move(p), std::forward<F>(func))](Try<T> t) mutable {
 680         if (t.hasException()) {
 681           auto tf2 = state.tryInvoke(std::move(t.exception()));
 682           if (tf2.hasException()) {
 683             state.setException(std::move(tf2.exception()));
 684           } else {
 685             tf2->setCallback_([p = state.stealPromise()](Try<T> && t3) mutable {
 686               p.setTry(std::move(t3));
 687             });
 688           }
 689         } else {
 690           state.setTry(std::move(t));
 691         }
 692       });
 693
 694   return f;
 695 }
 696
 697 // onError(exception_wrapper) that returns T
 698 template <class T>
 699 template <class F>
 700 typename std::enable_if<
 701     futures::detail::callableWith<F, exception_wrapper>::value &&
 702         !futures::detail::Extract<F>::ReturnsFuture::value,
 703     Future<T>>::type
 704 Future<T>::onError(F&& func) {
 705   static_assert(
 706       std::is_same<typename futures::detail::Extract<F>::Return, Future<T>>::
 707           value,
 708       "Return type of onError callback must be T or Future<T>");
 709
 710   Promise<T> p;
 711   auto f = p.getFuture();
 712   this->setCallback_(
 713       [state = futures::detail::makeCoreCallbackState(
 714            std::move(p), std::forward<F>(func))](Try<T>&& t) mutable {
 715         if (t.hasException()) {
 716           state.setTry(makeTryWith(
 717               [&] { return state.invoke(std::move(t.exception())); }));
 718         } else {
 719           state.setTry(std::move(t));
 720         }
 721       });
 722
 723   return f;
 724 }
 725
 726 template <class T>
 727 Try<T>& Future<T>::getTryVia(DrivableExecutor* e) {
 728   return waitVia(e).getTry();
 729 }
 730
 731 template <class Func>
 732 auto via(Executor* x, Func&& func)
 733     -> Future<typename isFuture<decltype(std::declval<Func>()())>::Inner> {
 734   // TODO make this actually more performant. :-P #7260175
 735   return via(x).then(std::forward<Func>(func));
 736 }
 737
 738 // makeFuture
 739
 740 template <class T>
 741 Future<typename std::decay<T>::type> makeFuture(T&& t) {
 742   return makeFuture(Try<typename std::decay<T>::type>(std::forward<T>(t)));
 743 }
 744
 745 inline Future<Unit> makeFuture() {
 746   return makeFuture(Unit{});
 747 }
 748
 749 // makeFutureWith(Future<T>()) -> Future<T>
 750 template <class F>
 751 typename std::enable_if<isFuture<typename std::result_of<F()>::type>::value,
 752                         typename std::result_of<F()>::type>::type
 753 makeFutureWith(F&& func) {
 754   using InnerType =
 755       typename isFuture<typename std::result_of<F()>::type>::Inner;
 756   try {
 757     return std::forward<F>(func)();
 758   } catch (std::exception& e) {
 759     return makeFuture<InnerType>(
 760         exception_wrapper(std::current_exception(), e));
 761   } catch (...) {
 762     return makeFuture<InnerType>(exception_wrapper(std::current_exception()));
 763   }
 764 }
 765
 766 // makeFutureWith(T()) -> Future<T>
 767 // makeFutureWith(void()) -> Future<Unit>
 768 template <class F>
 769 typename std::enable_if<
 770     !(isFuture<typename std::result_of<F()>::type>::value),
 771     Future<Unit::LiftT<typename std::result_of<F()>::type>>>::type
 772 makeFutureWith(F&& func) {
 773   using LiftedResult = Unit::LiftT<typename std::result_of<F()>::type>;
 774   return makeFuture<LiftedResult>(
 775       makeTryWith([&func]() mutable { return std::forward<F>(func)(); }));
 776 }
 777
 778 template <class T>
 779 Future<T> makeFuture(std::exception_ptr const& e) {
 780   return makeFuture(Try<T>(e));
 781 }
 782
 783 template <class T>
 784 Future<T> makeFuture(exception_wrapper ew) {
 785   return makeFuture(Try<T>(std::move(ew)));
 786 }
 787
 788 template <class T, class E>
 789 typename std::enable_if<std::is_base_of<std::exception, E>::value,
 790                         Future<T>>::type
 791 makeFuture(E const& e) {
 792   return makeFuture(Try<T>(make_exception_wrapper<E>(e)));
 793 }
 794
 795 template <class T>
 796 Future<T> makeFuture(Try<T>&& t) {
 797   return Future<T>(new futures::detail::Core<T>(std::move(t)));
 798 }
 799
 800 // via
 801 Future<Unit> via(Executor* executor, int8_t priority) {
 802   return makeFuture().via(executor, priority);
 803 }
 804
 805 // mapSetCallback calls func(i, Try<T>) when every future completes
 806
 807 template <class T, class InputIterator, class F>
 808 void mapSetCallback(InputIterator first, InputIterator last, F func) {
 809   for (size_t i = 0; first != last; ++first, ++i) {
 810     first->setCallback_([func, i](Try<T>&& t) {
 811       func(i, std::move(t));
 812     });
 813   }
 814 }
 815
 816 // collectAll (variadic)
 817
 818 template <typename... Fs>
 819 typename futures::detail::CollectAllVariadicContext<
 820     typename std::decay<Fs>::type::value_type...>::type
 821 collectAll(Fs&&... fs) {
 822   auto ctx = std::make_shared<futures::detail::CollectAllVariadicContext<
 823       typename std::decay<Fs>::type::value_type...>>();
 824   futures::detail::collectVariadicHelper<
 825       futures::detail::CollectAllVariadicContext>(ctx, std::forward<Fs>(fs)...);
 826   return ctx->p.getFuture();
 827 }
 828
 829 // collectAll (iterator)
 830
 831 template <class InputIterator>
 832 Future<
 833   std::vector<
 834   Try<typename std::iterator_traits<InputIterator>::value_type::value_type>>>
 835 collectAll(InputIterator first, InputIterator last) {
 836   typedef
 837     typename std::iterator_traits<InputIterator>::value_type::value_type T;
 838
 839   struct CollectAllContext {
 840     CollectAllContext(size_t n) : results(n) {}
 841     ~CollectAllContext() {
 842       p.setValue(std::move(results));
 843     }
 844     Promise<std::vector<Try<T>>> p;
 845     std::vector<Try<T>> results;
 846   };
 847
 848   auto ctx =
 849       std::make_shared<CollectAllContext>(size_t(std::distance(first, last)));
 850   mapSetCallback<T>(first, last, [ctx](size_t i, Try<T>&& t) {
 851     ctx->results[i] = std::move(t);
 852   });
 853   return ctx->p.getFuture();
 854 }
 855
 856 // collect (iterator)
 857
 858 namespace futures {
 859 namespace detail {
 860
 861 template <typename T>
 862 struct CollectContext {
 863   struct Nothing {
 864     explicit Nothing(int /* n */) {}
 865   };
 866
 867   using Result = typename std::conditional<
 868     std::is_void<T>::value,
 869     void,
 870     std::vector<T>>::type;
 871
 872   using InternalResult = typename std::conditional<
 873     std::is_void<T>::value,
 874     Nothing,
 875     std::vector<Optional<T>>>::type;
 876
 877   explicit CollectContext(size_t n) : result(n) {}
 878   ~CollectContext() {
 879     if (!threw.exchange(true)) {
 880       // map Optional<T> -> T
 881       std::vector<T> finalResult;
 882       finalResult.reserve(result.size());
 883       std::transform(result.begin(), result.end(),
 884                      std::back_inserter(finalResult),
 885                      [](Optional<T>& o) { return std::move(o.value()); });
 886       p.setValue(std::move(finalResult));
 887     }
 888   }
 889   inline void setPartialResult(size_t i, Try<T>& t) {
 890     result[i] = std::move(t.value());
 891   }
 892   Promise<Result> p;
 893   InternalResult result;
 894   std::atomic<bool> threw {false};
 895 };
 896
 897 } // namespace detail
 898 } // namespace futures
 899
 900 template <class InputIterator>
 901 Future<typename futures::detail::CollectContext<typename std::iterator_traits<
 902     InputIterator>::value_type::value_type>::Result>
 903 collect(InputIterator first, InputIterator last) {
 904   typedef
 905     typename std::iterator_traits<InputIterator>::value_type::value_type T;
 906
 907   auto ctx = std::make_shared<futures::detail::CollectContext<T>>(
 908       std::distance(first, last));
 909   mapSetCallback<T>(first, last, [ctx](size_t i, Try<T>&& t) {
 910     if (t.hasException()) {
 911        if (!ctx->threw.exchange(true)) {
 912          ctx->p.setException(std::move(t.exception()));
 913        }
 914      } else if (!ctx->threw) {
 915        ctx->setPartialResult(i, t);
 916      }
 917   });
 918   return ctx->p.getFuture();
 919 }
 920
 921 // collect (variadic)
 922
 923 template <typename... Fs>
 924 typename futures::detail::CollectVariadicContext<
 925     typename std::decay<Fs>::type::value_type...>::type
 926 collect(Fs&&... fs) {
 927   auto ctx = std::make_shared<futures::detail::CollectVariadicContext<
 928       typename std::decay<Fs>::type::value_type...>>();
 929   futures::detail::collectVariadicHelper<
 930       futures::detail::CollectVariadicContext>(ctx, std::forward<Fs>(fs)...);
 931   return ctx->p.getFuture();
 932 }
 933
 934 // collectAny (iterator)
 935
 936 template <class InputIterator>
 937 Future<
 938   std::pair<size_t,
 939             Try<
 940               typename
 941               std::iterator_traits<InputIterator>::value_type::value_type>>>
 942 collectAny(InputIterator first, InputIterator last) {
 943   typedef
 944     typename std::iterator_traits<InputIterator>::value_type::value_type T;
 945
 946   struct CollectAnyContext {
 947     CollectAnyContext() {}
 948     Promise<std::pair<size_t, Try<T>>> p;
 949     std::atomic<bool> done {false};
 950   };
 951
 952   auto ctx = std::make_shared<CollectAnyContext>();
 953   mapSetCallback<T>(first, last, [ctx](size_t i, Try<T>&& t) {
 954     if (!ctx->done.exchange(true)) {
 955       ctx->p.setValue(std::make_pair(i, std::move(t)));
 956     }
 957   });
 958   return ctx->p.getFuture();
 959 }
 960
 961 // collectAnyWithoutException (iterator)
 962
 963 template <class InputIterator>
 964 Future<std::pair<
 965     size_t,
 966     typename std::iterator_traits<InputIterator>::value_type::value_type>>
 967 collectAnyWithoutException(InputIterator first, InputIterator last) {
 968   typedef
 969       typename std::iterator_traits<InputIterator>::value_type::value_type T;
 970
 971   struct CollectAnyWithoutExceptionContext {
 972     CollectAnyWithoutExceptionContext(){}
 973     Promise<std::pair<size_t, T>> p;
 974     std::atomic<bool> done{false};
 975     std::atomic<size_t> nFulfilled{0};
 976     size_t nTotal;
 977   };
 978
 979   auto ctx = std::make_shared<CollectAnyWithoutExceptionContext>();
 980   ctx->nTotal = size_t(std::distance(first, last));
 981
 982   mapSetCallback<T>(first, last, [ctx](size_t i, Try<T>&& t) {
 983     if (!t.hasException() && !ctx->done.exchange(true)) {
 984       ctx->p.setValue(std::make_pair(i, std::move(t.value())));
 985     } else if (++ctx->nFulfilled == ctx->nTotal) {
 986       ctx->p.setException(t.exception());
 987     }
 988   });
 989   return ctx->p.getFuture();
 990 }
 991
 992 // collectN (iterator)
 993
 994 template <class InputIterator>
 995 Future<std::vector<std::pair<size_t, Try<typename
 996   std::iterator_traits<InputIterator>::value_type::value_type>>>>
 997 collectN(InputIterator first, InputIterator last, size_t n) {
 998   typedef typename
 999     std::iterator_traits<InputIterator>::value_type::value_type T;
1000   typedef std::vector<std::pair<size_t, Try<T>>> V;
1001
1002   struct CollectNContext {
1003     V v;
1004     std::atomic<size_t> completed = {0};
1005     Promise<V> p;
1006   };
1007   auto ctx = std::make_shared<CollectNContext>();
1008
1009   if (size_t(std::distance(first, last)) < n) {
1010     ctx->p.setException(std::runtime_error("Not enough futures"));
1011   } else {
1012     // for each completed Future, increase count and add to vector, until we
1013     // have n completed futures at which point we fulfil our Promise with the
1014     // vector
1015     mapSetCallback<T>(first, last, [ctx, n](size_t i, Try<T>&& t) {
1016       auto c = ++ctx->completed;
1017       if (c <= n) {
1018         assert(ctx->v.size() < n);
1019         ctx->v.emplace_back(i, std::move(t));
1020         if (c == n) {
1021           ctx->p.setTry(Try<V>(std::move(ctx->v)));
1022         }
1023       }
1024     });
1025   }
1026
1027   return ctx->p.getFuture();
1028 }
1029
1030 // reduce (iterator)
1031
1032 template <class It, class T, class F>
1033 Future<T> reduce(It first, It last, T&& initial, F&& func) {
1034   if (first == last) {
1035     return makeFuture(std::move(initial));
1036   }
1037
1038   typedef typename std::iterator_traits<It>::value_type::value_type ItT;
1039   typedef typename std::conditional<
1040       futures::detail::callableWith<F, T&&, Try<ItT>&&>::value,
1041       Try<ItT>,
1042       ItT>::type Arg;
1043   typedef isTry<Arg> IsTry;
1044
1045   auto sfunc = std::make_shared<F>(std::move(func));
1046
1047   auto f = first->then(
1048       [ minitial = std::move(initial), sfunc ](Try<ItT> & head) mutable {
1049         return (*sfunc)(
1050             std::move(minitial), head.template get<IsTry::value, Arg&&>());
1051       });
1052
1053   for (++first; first != last; ++first) {
1054     f = collectAll(f, *first).then([sfunc](std::tuple<Try<T>, Try<ItT>>& t) {
1055       return (*sfunc)(std::move(std::get<0>(t).value()),
1056                   // Either return a ItT&& or a Try<ItT>&& depending
1057                   // on the type of the argument of func.
1058                   std::get<1>(t).template get<IsTry::value, Arg&&>());
1059     });
1060   }
1061
1062   return f;
1063 }
1064
1065 // window (collection)
1066
1067 template <class Collection, class F, class ItT, class Result>
1068 std::vector<Future<Result>>
1069 window(Collection input, F func, size_t n) {
1070   // Use global inline executor singleton
1071   auto executor = &InlineExecutor::instance();
1072   return window(executor, std::move(input), std::move(func), n);
1073 }
1074
1075 template <class Collection, class F, class ItT, class Result>
1076 std::vector<Future<Result>>
1077 window(Executor* executor, Collection input, F func, size_t n) {
1078   struct WindowContext {
1079     WindowContext(Executor* executor_, Collection&& input_, F&& func_)
1080         : executor(executor_),
1081           input(std::move(input_)),
1082           promises(input.size()),
1083           func(std::move(func_)) {}
1084     std::atomic<size_t> i{0};
1085     Executor* executor;
1086     Collection input;
1087     std::vector<Promise<Result>> promises;
1088     F func;
1089
1090     static inline void spawn(std::shared_ptr<WindowContext> ctx) {
1091       size_t i = ctx->i++;
1092       if (i < ctx->input.size()) {
1093         auto fut = ctx->func(std::move(ctx->input[i]));
1094         fut.setCallback_([ctx = std::move(ctx), i](Try<Result>&& t) mutable {
1095           const auto executor_ = ctx->executor;
1096           executor_->add([ctx = std::move(ctx), i, t = std::move(t)]() mutable {
1097             ctx->promises[i].setTry(std::move(t));
1098             // Chain another future onto this one
1099             spawn(std::move(ctx));
1100           });
1101         });
1102       }
1103     }
1104   };
1105
1106   auto max = std::min(n, input.size());
1107
1108   auto ctx = std::make_shared<WindowContext>(
1109       executor, std::move(input), std::move(func));
1110
1111   // Start the first n Futures
1112   for (size_t i = 0; i < max; ++i) {
1113     executor->add([ctx]() mutable { WindowContext::spawn(std::move(ctx)); });
1114   }
1115
1116   std::vector<Future<Result>> futures;
1117   futures.reserve(ctx->promises.size());
1118   for (auto& promise : ctx->promises) {
1119     futures.emplace_back(promise.getFuture());
1120   }
1121
1122   return futures;
1123 }
1124
1125 // reduce
1126
1127 template <class T>
1128 template <class I, class F>
1129 Future<I> Future<T>::reduce(I&& initial, F&& func) {
1130   return then([
1131     minitial = std::forward<I>(initial),
1132     mfunc = std::forward<F>(func)
1133   ](T& vals) mutable {
1134     auto ret = std::move(minitial);
1135     for (auto& val : vals) {
1136       ret = mfunc(std::move(ret), std::move(val));
1137     }
1138     return ret;
1139   });
1140 }
1141
1142 // unorderedReduce (iterator)
1143
1144 template <class It, class T, class F, class ItT, class Arg>
1145 Future<T> unorderedReduce(It first, It last, T initial, F func) {
1146   if (first == last) {
1147     return makeFuture(std::move(initial));
1148   }
1149
1150   typedef isTry<Arg> IsTry;
1151
1152   struct UnorderedReduceContext {
1153     UnorderedReduceContext(T&& memo, F&& fn, size_t n)
1154         : lock_(), memo_(makeFuture<T>(std::move(memo))),
1155           func_(std::move(fn)), numThens_(0), numFutures_(n), promise_()
1156       {}
1157     folly::MicroSpinLock lock_; // protects memo_ and numThens_
1158     Future<T> memo_;
1159     F func_;
1160     size_t numThens_; // how many Futures completed and called .then()
1161     size_t numFutures_; // how many Futures in total
1162     Promise<T> promise_;
1163   };
1164
1165   auto ctx = std::make_shared<UnorderedReduceContext>(
1166     std::move(initial), std::move(func), std::distance(first, last));
1167
1168   mapSetCallback<ItT>(
1169       first,
1170       last,
1171       [ctx](size_t /* i */, Try<ItT>&& t) {
1172         // Futures can be completed in any order, simultaneously.
1173         // To make this non-blocking, we create a new Future chain in
1174         // the order of completion to reduce the values.
1175         // The spinlock just protects chaining a new Future, not actually
1176         // executing the reduce, which should be really fast.
1177         folly::MSLGuard lock(ctx->lock_);
1178         ctx->memo_ =
1179             ctx->memo_.then([ ctx, mt = std::move(t) ](T && v) mutable {
1180               // Either return a ItT&& or a Try<ItT>&& depending
1181               // on the type of the argument of func.
1182               return ctx->func_(std::move(v),
1183                                 mt.template get<IsTry::value, Arg&&>());
1184             });
1185         if (++ctx->numThens_ == ctx->numFutures_) {
1186           // After reducing the value of the last Future, fulfill the Promise
1187           ctx->memo_.setCallback_(
1188               [ctx](Try<T>&& t2) { ctx->promise_.setValue(std::move(t2)); });
1189         }
1190       });
1191
1192   return ctx->promise_.getFuture();
1193 }
1194
1195 // within
1196
1197 template <class T>
1198 Future<T> Future<T>::within(Duration dur, Timekeeper* tk) {
1199   return within(dur, TimedOut(), tk);
1200 }
1201
1202 template <class T>
1203 template <class E>
1204 Future<T> Future<T>::within(Duration dur, E e, Timekeeper* tk) {
1205
1206   struct Context {
1207     Context(E ex) : exception(std::move(ex)), promise() {}
1208     E exception;
1209     Future<Unit> thisFuture;
1210     Promise<T> promise;
1211     std::atomic<bool> token {false};
1212   };
1213
1214   if (this->isReady()) {
1215     return std::move(*this);
1216   }
1217
1218   std::shared_ptr<Timekeeper> tks;
1219   if (LIKELY(!tk)) {
1220     tks = folly::detail::getTimekeeperSingleton();
1221     tk = tks.get();
1222   }
1223
1224   if (UNLIKELY(!tk)) {
1225     return makeFuture<T>(NoTimekeeper());
1226   }
1227
1228   auto ctx = std::make_shared<Context>(std::move(e));
1229
1230   ctx->thisFuture = this->then([ctx](Try<T>&& t) mutable {
1231     if (ctx->token.exchange(true) == false) {
1232       ctx->promise.setTry(std::move(t));
1233     }
1234   });
1235
1236   // Have time keeper use a weak ptr to hold ctx,
1237   // so that ctx can be deallocated as soon as the future job finished.
1238   tk->after(dur).then([weakCtx = to_weak_ptr(ctx)](Try<Unit> const& t) mutable {
1239     auto lockedCtx = weakCtx.lock();
1240     if (!lockedCtx) {
1241       // ctx already released. "this" completed first, cancel "after"
1242       return;
1243     }
1244     // "after" completed first, cancel "this"
1245     lockedCtx->thisFuture.raise(TimedOut());
1246     if (lockedCtx->token.exchange(true) == false) {
1247       if (t.hasException()) {
1248         lockedCtx->promise.setException(std::move(t.exception()));
1249       } else {
1250         lockedCtx->promise.setException(std::move(lockedCtx->exception));
1251       }
1252     }
1253   });
1254
1255   return ctx->promise.getFuture().via(this->getExecutor());
1256 }
1257
1258 // delayed
1259
1260 template <class T>
1261 Future<T> Future<T>::delayed(Duration dur, Timekeeper* tk) {
1262   return collectAll(*this, futures::sleep(dur, tk))
1263       .then([](std::tuple<Try<T>, Try<Unit>> tup) {
1264         Try<T>& t = std::get<0>(tup);
1265         return makeFuture<T>(std::move(t));
1266       });
1267 }
1268
1269 namespace futures {
1270 namespace detail {
1271
1272 template <class FutureType, typename T = typename FutureType::value_type>
1273 void waitImpl(FutureType& f) {
1274   // short-circuit if there's nothing to do
1275   if (f.isReady()) {
1276     return;
1277   }
1278
1279   FutureBatonType baton;
1280   f.setCallback_([&](const Try<T>& /* t */) { baton.post(); });
1281   baton.wait();
1282   assert(f.isReady());
1283 }
1284
1285 template <class FutureType, typename T = typename FutureType::value_type>
1286 void waitImpl(FutureType& f, Duration dur) {
1287   // short-circuit if there's nothing to do
1288   if (f.isReady()) {
1289     return;
1290   }
1291
1292   Promise<T> promise;
1293   auto ret = promise.getFuture();
1294   auto baton = std::make_shared<FutureBatonType>();
1295   f.setCallback_([baton, promise = std::move(promise)](Try<T>&& t) mutable {
1296     promise.setTry(std::move(t));
1297     baton->post();
1298   });
1299   f = std::move(ret);
1300   if (baton->timed_wait(dur)) {
1301     assert(f.isReady());
1302   }
1303 }
1304
1305 template <class T>
1306 void waitViaImpl(Future<T>& f, DrivableExecutor* e) {
1307   // Set callback so to ensure that the via executor has something on it
1308   // so that once the preceding future triggers this callback, drive will
1309   // always have a callback to satisfy it
1310   if (f.isReady()) {
1311     return;
1312   }
1313   f = f.via(e).then([](T&& t) { return std::move(t); });
1314   while (!f.isReady()) {
1315     e->drive();
1316   }
1317   assert(f.isReady());
1318 }
1319
1320 } // namespace detail
1321 } // namespace futures
1322
1323 template <class T>
1324 SemiFuture<T>& SemiFuture<T>::wait() & {
1325   futures::detail::waitImpl(*this);
1326   return *this;
1327 }
1328
1329 template <class T>
1330 SemiFuture<T>&& SemiFuture<T>::wait() && {
1331   futures::detail::waitImpl(*this);
1332   return std::move(*this);
1333 }
1334
1335 template <class T>
1336 SemiFuture<T>& SemiFuture<T>::wait(Duration dur) & {
1337   futures::detail::waitImpl(*this, dur);
1338   return *this;
1339 }
1340
1341 template <class T>
1342 SemiFuture<T>&& SemiFuture<T>::wait(Duration dur) && {
1343   futures::detail::waitImpl(*this, dur);
1344   return std::move(*this);
1345 }
1346
1347 template <class T>
1348 T SemiFuture<T>::get() && {
1349   return std::move(wait().value());
1350 }
1351
1352 template <class T>
1353 T SemiFuture<T>::get(Duration dur) && {
1354   wait(dur);
1355   if (this->isReady()) {
1356     return std::move(this->value());
1357   } else {
1358     throwTimedOut();
1359   }
1360 }
1361
1362 template <class T>
1363 Future<T>& Future<T>::wait() & {
1364   futures::detail::waitImpl(*this);
1365   return *this;
1366 }
1367
1368 template <class T>
1369 Future<T>&& Future<T>::wait() && {
1370   futures::detail::waitImpl(*this);
1371   return std::move(*this);
1372 }
1373
1374 template <class T>
1375 Future<T>& Future<T>::wait(Duration dur) & {
1376   futures::detail::waitImpl(*this, dur);
1377   return *this;
1378 }
1379
1380 template <class T>
1381 Future<T>&& Future<T>::wait(Duration dur) && {
1382   futures::detail::waitImpl(*this, dur);
1383   return std::move(*this);
1384 }
1385
1386 template <class T>
1387 Future<T>& Future<T>::waitVia(DrivableExecutor* e) & {
1388   futures::detail::waitViaImpl(*this, e);
1389   return *this;
1390 }
1391
1392 template <class T>
1393 Future<T>&& Future<T>::waitVia(DrivableExecutor* e) && {
1394   futures::detail::waitViaImpl(*this, e);
1395   return std::move(*this);
1396 }
1397
1398 template <class T>
1399 T Future<T>::get() {
1400   return std::move(wait().value());
1401 }
1402
1403 template <class T>
1404 T Future<T>::get(Duration dur) {
1405   wait(dur);
1406   if (this->isReady()) {
1407     return std::move(this->value());
1408   } else {
1409     throwTimedOut();
1410   }
1411 }
1412
1413 template <class T>
1414 T Future<T>::getVia(DrivableExecutor* e) {
1415   return std::move(waitVia(e).value());
1416 }
1417
1418 namespace futures {
1419 namespace detail {
1420 template <class T>
1421 struct TryEquals {
1422   static bool equals(const Try<T>& t1, const Try<T>& t2) {
1423     return t1.value() == t2.value();
1424   }
1425 };
1426 } // namespace detail
1427 } // namespace futures
1428
1429 template <class T>
1430 Future<bool> Future<T>::willEqual(Future<T>& f) {
1431   return collectAll(*this, f).then([](const std::tuple<Try<T>, Try<T>>& t) {
1432     if (std::get<0>(t).hasValue() && std::get<1>(t).hasValue()) {
1433       return futures::detail::TryEquals<T>::equals(
1434           std::get<0>(t), std::get<1>(t));
1435     } else {
1436       return false;
1437       }
1438   });
1439 }
1440
1441 template <class T>
1442 template <class F>
1443 Future<T> Future<T>::filter(F&& predicate) {
1444   return this->then([p = std::forward<F>(predicate)](T val) {
1445     T const& valConstRef = val;
1446     if (!p(valConstRef)) {
1447       throwPredicateDoesNotObtain();
1448     }
1449     return val;
1450   });
1451 }
1452
1453 template <class F>
1454 inline Future<Unit> when(bool p, F&& thunk) {
1455   return p ? std::forward<F>(thunk)().unit() : makeFuture();
1456 }
1457
1458 template <class P, class F>
1459 Future<Unit> whileDo(P&& predicate, F&& thunk) {
1460   if (predicate()) {
1461     auto future = thunk();
1462     return future.then([
1463       predicate = std::forward<P>(predicate),
1464       thunk = std::forward<F>(thunk)
1465     ]() mutable {
1466       return whileDo(std::forward<P>(predicate), std::forward<F>(thunk));
1467     });
1468   }
1469   return makeFuture();
1470 }
1471
1472 template <class F>
1473 Future<Unit> times(const int n, F&& thunk) {
1474   return folly::whileDo(
1475       [ n, count = std::make_unique<std::atomic<int>>(0) ]() mutable {
1476         return count->fetch_add(1) < n;
1477       },
1478       std::forward<F>(thunk));
1479 }
1480
1481 namespace futures {
1482 template <class It, class F, class ItT, class Result>
1483 std::vector<Future<Result>> map(It first, It last, F func) {
1484   std::vector<Future<Result>> results;
1485   for (auto it = first; it != last; it++) {
1486     results.push_back(it->then(func));
1487   }
1488   return results;
1489 }
1490 } // namespace futures
1491
1492 // Instantiate the most common Future types to save compile time
1493 extern template class Future<Unit>;
1494 extern template class Future<bool>;
1495 extern template class Future<int>;
1496 extern template class Future<int64_t>;
1497 extern template class Future<std::string>;
1498 extern template class Future<double>;
1499 } // namespace folly