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