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