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