folly/futures/helpers.h

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