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