folly/futures/helpers.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 #pragma once
  17
  18 #include <atomic>
  19 #include <tuple>
  20 #include <utility>
  21
  22 #include <folly/Portability.h>
  23 #include <folly/Try.h>
  24 #include <folly/futures/Future.h>
  25 #include <folly/futures/Promise.h>
  26
  27 namespace folly {
  28
  29 namespace detail {
  30 template <typename... Ts>
  31 struct CollectAllVariadicContext {
  32   CollectAllVariadicContext() {}
  33   template <typename T, size_t I>
  34   inline void setPartialResult(Try<T>& t) {
  35     std::get<I>(results) = std::move(t);
  36   }
  37   ~CollectAllVariadicContext() {
  38     p.setValue(std::move(results));
  39   }
  40   Promise<std::tuple<Try<Ts>...>> p;
  41   std::tuple<Try<Ts>...> results;
  42   typedef Future<std::tuple<Try<Ts>...>> type;
  43 };
  44
  45 template <typename... Ts>
  46 struct CollectVariadicContext {
  47   CollectVariadicContext() {}
  48   template <typename T, size_t I>
  49   inline void setPartialResult(Try<T>& t) {
  50     if (t.hasException()) {
  51       if (!threw.exchange(true)) {
  52         p.setException(std::move(t.exception()));
  53       }
  54     } else if (!threw) {
  55       std::get<I>(results) = std::move(t);
  56     }
  57   }
  58   ~CollectVariadicContext() noexcept {
  59     if (!threw.exchange(true)) {
  60       p.setValue(unwrapTryTuple(std::move(results)));
  61     }
  62   }
  63   Promise<std::tuple<Ts...>> p;
  64   std::tuple<folly::Try<Ts>...> results;
  65   std::atomic<bool> threw{false};
  66   typedef Future<std::tuple<Ts...>> type;
  67 };
  68 }
  69
  70 /// This namespace is for utility functions that would usually be static
  71 /// members of Future, except they don't make sense there because they don't
  72 /// depend on the template type (rather, on the type of their arguments in
  73 /// some cases). This is the least-bad naming scheme we could think of. Some
  74 /// of the functions herein have really-likely-to-collide names, like "map"
  75 /// and "sleep".
  76 namespace futures {
  77   /// Returns a Future that will complete after the specified duration. The
  78   /// Duration typedef of a `std::chrono` duration type indicates the
  79   /// resolution you can expect to be meaningful (milliseconds at the time of
  80   /// writing). Normally you wouldn't need to specify a Timekeeper, we will
  81   /// use the global futures timekeeper (we run a thread whose job it is to
  82   /// keep time for futures timeouts) but we provide the option for power
  83   /// users.
  84   ///
  85   /// The Timekeeper thread will be lazily created the first time it is
  86   /// needed. If your program never uses any timeouts or other time-based
  87   /// Futures you will pay no Timekeeper thread overhead.
  88   Future<Unit> sleep(Duration, Timekeeper* = nullptr);
  89
  90   /**
  91    * Set func as the callback for each input Future and return a vector of
  92    * Futures containing the results in the input order.
  93    */
  94   template <class It, class F,
  95             class ItT = typename std::iterator_traits<It>::value_type,
  96             class Result
  97       = typename decltype(std::declval<ItT>().then(std::declval<F>()))::value_type>
  98   std::vector<Future<Result>> map(It first, It last, F func);
  99
 100   // Sugar for the most common case
 101   template <class Collection, class F>
 102   auto map(Collection&& c, F&& func)
 103       -> decltype(map(c.begin(), c.end(), func)) {
 104     return map(c.begin(), c.end(), std::forward<F>(func));
 105   }
 106
 107 } // namespace futures
 108
 109 /**
 110   Make a completed Future by moving in a value. e.g.
 111
 112     string foo = "foo";
 113     auto f = makeFuture(std::move(foo));
 114
 115   or
 116
 117     auto f = makeFuture<string>("foo");
 118 */
 119 template <class T>
 120 Future<typename std::decay<T>::type> makeFuture(T&& t);
 121
 122 /** Make a completed void Future. */
 123 Future<Unit> makeFuture();
 124
 125 /**
 126   Make a Future by executing a function.
 127
 128   If the function returns a value of type T, makeFutureWith
 129   returns a completed Future<T>, capturing the value returned
 130   by the function.
 131
 132   If the function returns a Future<T> already, makeFutureWith
 133   returns just that.
 134
 135   Either way, if the function throws, a failed Future is
 136   returned that captures the exception.
 137
 138   Calling makeFutureWith(func) is equivalent to calling
 139   makeFuture().then(func).
 140 */
 141
 142 // makeFutureWith(Future<T>()) -> Future<T>
 143 template <class F>
 144 typename std::enable_if<isFuture<typename std::result_of<F()>::type>::value,
 145                         typename std::result_of<F()>::type>::type
 146 makeFutureWith(F&& func);
 147
 148 // makeFutureWith(T()) -> Future<T>
 149 // makeFutureWith(void()) -> Future<Unit>
 150 template <class F>
 151 typename std::enable_if<
 152     !(isFuture<typename std::result_of<F()>::type>::value),
 153     Future<typename Unit::Lift<typename std::result_of<F()>::type>::type>>::type
 154 makeFutureWith(F&& func);
 155
 156 /// Make a failed Future from an exception_ptr.
 157 /// Because the Future's type cannot be inferred you have to specify it, e.g.
 158 ///
 159 ///   auto f = makeFuture<string>(std::current_exception());
 160 template <class T>
 161 FOLLY_DEPRECATED("use makeFuture(exception_wrapper)")
 162 Future<T> makeFuture(std::exception_ptr const& e);
 163
 164 /// Make a failed Future from an exception_wrapper.
 165 template <class T>
 166 Future<T> makeFuture(exception_wrapper ew);
 167
 168 /** Make a Future from an exception type E that can be passed to
 169   std::make_exception_ptr(). */
 170 template <class T, class E>
 171 typename std::enable_if<std::is_base_of<std::exception, E>::value,
 172                         Future<T>>::type
 173 makeFuture(E const& e);
 174
 175 /** Make a Future out of a Try */
 176 template <class T>
 177 Future<T> makeFuture(Try<T>&& t);
 178
 179 /*
 180  * Return a new Future that will call back on the given Executor.
 181  * This is just syntactic sugar for makeFuture().via(executor)
 182  *
 183  * @param executor the Executor to call back on
 184  * @param priority optionally, the priority to add with. Defaults to 0 which
 185  * represents medium priority.
 186  *
 187  * @returns a void Future that will call back on the given executor
 188  */
 189 inline Future<Unit> via(
 190     Executor* executor,
 191     int8_t priority = Executor::MID_PRI);
 192
 193 /// Execute a function via the given executor and return a future.
 194 /// This is semantically equivalent to via(executor).then(func), but
 195 /// easier to read and slightly more efficient.
 196 template <class Func>
 197 auto via(Executor*, Func&& func)
 198     -> Future<typename isFuture<decltype(std::declval<Func>()())>::Inner>;
 199
 200 /** When all the input Futures complete, the returned Future will complete.
 201   Errors do not cause early termination; this Future will always succeed
 202   after all its Futures have finished (whether successfully or with an
 203   error).
 204
 205   The Futures are moved in, so your copies are invalid. If you need to
 206   chain further from these Futures, use the variant with an output iterator.
 207
 208   This function is thread-safe for Futures running on different threads. But
 209   if you are doing anything non-trivial after, you will probably want to
 210   follow with `via(executor)` because it will complete in whichever thread the
 211   last Future completes in.
 212
 213   The return type for Future<T> input is a Future<std::vector<Try<T>>>
 214   */
 215 template <class InputIterator>
 216 Future<std::vector<Try<
 217   typename std::iterator_traits<InputIterator>::value_type::value_type>>>
 218 collectAll(InputIterator first, InputIterator last);
 219
 220 /// Sugar for the most common case
 221 template <class Collection>
 222 auto collectAll(Collection&& c) -> decltype(collectAll(c.begin(), c.end())) {
 223   return collectAll(c.begin(), c.end());
 224 }
 225
 226 /// This version takes a varying number of Futures instead of an iterator.
 227 /// The return type for (Future<T1>, Future<T2>, ...) input
 228 /// is a Future<std::tuple<Try<T1>, Try<T2>, ...>>.
 229 /// The Futures are moved in, so your copies are invalid.
 230 template <typename... Fs>
 231 typename detail::CollectAllVariadicContext<
 232   typename std::decay<Fs>::type::value_type...>::type
 233 collectAll(Fs&&... fs);
 234
 235 /// Like collectAll, but will short circuit on the first exception. Thus, the
 236 /// type of the returned Future is std::vector<T> instead of
 237 /// std::vector<Try<T>>
 238 template <class InputIterator>
 239 Future<typename detail::CollectContext<
 240   typename std::iterator_traits<InputIterator>::value_type::value_type
 241 >::result_type>
 242 collect(InputIterator first, InputIterator last);
 243
 244 /// Sugar for the most common case
 245 template <class Collection>
 246 auto collect(Collection&& c) -> decltype(collect(c.begin(), c.end())) {
 247   return collect(c.begin(), c.end());
 248 }
 249
 250 /// Like collectAll, but will short circuit on the first exception. Thus, the
 251 /// type of the returned Future is std::tuple<T1, T2, ...> instead of
 252 /// std::tuple<Try<T1>, Try<T2>, ...>
 253 template <typename... Fs>
 254 typename detail::CollectVariadicContext<
 255   typename std::decay<Fs>::type::value_type...>::type
 256 collect(Fs&&... fs);
 257
 258 /** The result is a pair of the index of the first Future to complete and
 259   the Try. If multiple Futures complete at the same time (or are already
 260   complete when passed in), the "winner" is chosen non-deterministically.
 261
 262   This function is thread-safe for Futures running on different threads.
 263   */
 264 template <class InputIterator>
 265 Future<std::pair<
 266   size_t,
 267   Try<typename std::iterator_traits<InputIterator>::value_type::value_type>>>
 268 collectAny(InputIterator first, InputIterator last);
 269
 270 /// Sugar for the most common case
 271 template <class Collection>
 272 auto collectAny(Collection&& c) -> decltype(collectAny(c.begin(), c.end())) {
 273   return collectAny(c.begin(), c.end());
 274 }
 275
 276 /** Similar to collectAny, collectAnyWithoutException return the first Future to
 277  * complete without exceptions. If none of the future complete without
 278  * excpetions, the last exception will be returned as a result.
 279   */
 280 template <class InputIterator>
 281 Future<std::pair<
 282     size_t,
 283     typename std::iterator_traits<InputIterator>::value_type::value_type>>
 284 collectAnyWithoutException(InputIterator first, InputIterator last);
 285
 286 /// Sugar for the most common case
 287 template <class Collection>
 288 auto collectAnyWithoutException(Collection&& c)
 289     -> decltype(collectAnyWithoutException(c.begin(), c.end())) {
 290   return collectAnyWithoutException(c.begin(), c.end());
 291 }
 292
 293 /** when n Futures have completed, the Future completes with a vector of
 294   the index and Try of those n Futures (the indices refer to the original
 295   order, but the result vector will be in an arbitrary order)
 296
 297   Not thread safe.
 298   */
 299 template <class InputIterator>
 300 Future<std::vector<std::pair<
 301   size_t,
 302   Try<typename std::iterator_traits<InputIterator>::value_type::value_type>>>>
 303 collectN(InputIterator first, InputIterator last, size_t n);
 304
 305 /// Sugar for the most common case
 306 template <class Collection>
 307 auto collectN(Collection&& c, size_t n)
 308     -> decltype(collectN(c.begin(), c.end(), n)) {
 309   return collectN(c.begin(), c.end(), n);
 310 }
 311
 312 /** window creates up to n Futures using the values
 313     in the collection, and then another Future for each Future
 314     that completes
 315
 316     this is basically a sliding window of Futures of size n
 317
 318     func must return a Future for each value in input
 319   */
 320 template <class Collection, class F,
 321           class ItT = typename std::iterator_traits<
 322             typename Collection::iterator>::value_type,
 323           class Result = typename detail::resultOf<F, ItT&&>::value_type>
 324 std::vector<Future<Result>>
 325 window(Collection input, F func, size_t n);
 326
 327 template <typename F, typename T, typename ItT>
 328 using MaybeTryArg = typename std::conditional<
 329   detail::callableWith<F, T&&, Try<ItT>&&>::value, Try<ItT>, ItT>::type;
 330
 331 template<typename F, typename T, typename Arg>
 332 using isFutureResult = isFuture<typename std::result_of<F(T&&, Arg&&)>::type>;
 333
 334 /** repeatedly calls func on every result, e.g.
 335     reduce(reduce(reduce(T initial, result of first), result of second), ...)
 336
 337     The type of the final result is a Future of the type of the initial value.
 338
 339     Func can either return a T, or a Future<T>
 340
 341     func is called in order of the input, see unorderedReduce if that is not
 342     a requirement
 343   */
 344 template <class It, class T, class F>
 345 Future<T> reduce(It first, It last, T&& initial, F&& func);
 346
 347 /// Sugar for the most common case
 348 template <class Collection, class T, class F>
 349 auto reduce(Collection&& c, T&& initial, F&& func)
 350     -> decltype(reduce(c.begin(), c.end(), std::forward<T>(initial),
 351                 std::forward<F>(func))) {
 352   return reduce(
 353       c.begin(),
 354       c.end(),
 355       std::forward<T>(initial),
 356       std::forward<F>(func));
 357 }
 358
 359 /** like reduce, but calls func on finished futures as they complete
 360     does NOT keep the order of the input
 361   */
 362 template <class It, class T, class F,
 363           class ItT = typename std::iterator_traits<It>::value_type::value_type,
 364           class Arg = MaybeTryArg<F, T, ItT>>
 365 Future<T> unorderedReduce(It first, It last, T initial, F func);
 366
 367 /// Sugar for the most common case
 368 template <class Collection, class T, class F>
 369 auto unorderedReduce(Collection&& c, T&& initial, F&& func)
 370     -> decltype(unorderedReduce(c.begin(), c.end(), std::forward<T>(initial),
 371                 std::forward<F>(func))) {
 372   return unorderedReduce(
 373       c.begin(),
 374       c.end(),
 375       std::forward<T>(initial),
 376       std::forward<F>(func));
 377 }
 378
 379 namespace futures {
 380
 381 /**
 382  *  retrying
 383  *
 384  *  Given a policy and a future-factory, creates futures according to the
 385  *  policy.
 386  *
 387  *  The policy must be moveable - retrying will move it a lot - and callable of
 388  *  either of the two forms:
 389  *  - Future<bool>(size_t, exception_wrapper)
 390  *  - bool(size_t, exception_wrapper)
 391  *  Internally, the latter is transformed into the former in the obvious way.
 392  *  The first parameter is the attempt number of the next prospective attempt;
 393  *  the second parameter is the most recent exception. The policy returns a
 394  *  Future<bool> which, when completed with true, indicates that a retry is
 395  *  desired.
 396  *
 397  *  We provide a few generic policies:
 398  *  - Basic
 399  *  - CappedJitteredexponentialBackoff
 400  *
 401  *  Custom policies may use the most recent try number and exception to decide
 402  *  whether to retry and optionally to do something interesting like delay
 403  *  before the retry. Users may pass inline lambda expressions as policies, or
 404  *  may define their own data types meeting the above requirements. Users are
 405  *  responsible for managing the lifetimes of anything pointed to or referred to
 406  *  from inside the policy.
 407  *
 408  *  For example, one custom policy may try up to k times, but only if the most
 409  *  recent exception is one of a few types or has one of a few error codes
 410  *  indicating that the failure was transitory.
 411  *
 412  *  Cancellation is not supported.
 413  *
 414  *  If both FF and Policy inline executes, then it is possible to hit a stack
 415  *  overflow due to the recursive nature of the retry implementation
 416  */
 417 template <class Policy, class FF>
 418 typename std::result_of<FF(size_t)>::type
 419 retrying(Policy&& p, FF&& ff);
 420
 421 /**
 422  *  generic retrying policies
 423  */
 424
 425 inline
 426 std::function<bool(size_t, const exception_wrapper&)>
 427 retryingPolicyBasic(
 428     size_t max_tries);
 429
 430 template <class Policy, class URNG>
 431 std::function<Future<bool>(size_t, const exception_wrapper&)>
 432 retryingPolicyCappedJitteredExponentialBackoff(
 433     size_t max_tries,
 434     Duration backoff_min,
 435     Duration backoff_max,
 436     double jitter_param,
 437     URNG&& rng,
 438     Policy&& p);
 439
 440 inline
 441 std::function<Future<bool>(size_t, const exception_wrapper&)>
 442 retryingPolicyCappedJitteredExponentialBackoff(
 443     size_t max_tries,
 444     Duration backoff_min,
 445     Duration backoff_max,
 446     double jitter_param);
 447
 448 }
 449
 450 } // namespace