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