folly/futures/Future-inl.h

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