folly/Foreach.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 <folly/Portability.h>
  20 #include <folly/Preprocessor.h>
  21
  22 #include <type_traits>
  23
  24 namespace folly {
  25
  26 /**
  27  * @function for_each
  28  *
  29  * folly::for_each is a generalized iteration algorithm.  Example:
  30  *
  31  *  auto one = std::make_tuple(1, 2, 3);
  32  *  auto two = std::vector<int>{1, 2, 3};
  33  *  auto func = [](auto element, auto index) {
  34  *    cout << index << " : " << element << endl;
  35  *  };
  36  *  folly::for_each(one, func);
  37  *  folly::for_each(two, func);
  38  *
  39  * The for_each function allows iteration through sequences, these
  40  * can either be runtime sequences (i.e. entities for which std::begin and
  41  * std::end work) or compile time sequences (as deemed by the presence of
  42  * std::tuple_length<>, get<> (ADL resolved) functions)
  43  *
  44  * The function is made to provide a convenient library based alternative to
  45  * the proposal p0589r0, which aims to generalize the range based for loop
  46  * even further to work with compile time sequences.
  47  *
  48  * A drawback of using range based for loops is that sometimes you do not have
  49  * access to the index within the range.  This provides easy access to that,
  50  * even with compile time sequences.
  51  *
  52  * And breaking out is easy
  53  *
  54  *  auto range_one = std::vector<int>{1, 2, 3};
  55  *  auto range_two = std::make_tuple(1, 2, 3);
  56  *  auto func = [](auto ele, auto index) {
  57  *    cout << "Element at index " << index << " : " << ele;
  58  *    if (index == 1) {
  59  *      return folly::loop_break;
  60  *    }
  61  *    return folly::loop_continue;
  62  *  };
  63  *  folly_for_each(range_one, func);
  64  *  folly_for_each(range_two, func);
  65  *
  66  * A simple use case would be when using futures, if the user was doing calls
  67  * to n servers then they would accept the callback with the futures like this
  68  *
  69  *  auto vec = std::vector<std::future<int>>{request_one(), ...};
  70  *  when_all(vec.begin(), vec.end()).then([](auto futures) {
  71  *    folly::for_each(futures, [](auto& fut) { ... });
  72  *  });
  73  *
  74  * Now when this code switches to use tuples instead of the runtime
  75  * std::vector, then the loop does not need to change, the code will still
  76  * work just fine
  77  *
  78  *  when_all(future_one, future_two, future_three).then([](auto futures) {
  79  *    folly::for_each(futures, [](auto& fut) { ... });
  80  *  });
  81  */
  82 template <typename Range, typename Func>
  83 FOLLY_CPP14_CONSTEXPR Func for_each(Range&& range, Func func);
  84
  85 /**
  86  * The user should return loop_break and loop_continue if they want to iterate
  87  * in such a way that they can preemptively stop the loop and break out when
  88  * certain conditions are met
  89  */
  90 namespace for_each_detail {
  91 enum class LoopControl : bool { BREAK, CONTINUE };
  92 } // namespace for_each_detail
  93
  94 constexpr auto loop_break = for_each_detail::LoopControl::BREAK;
  95 constexpr auto loop_continue = for_each_detail::LoopControl::CONTINUE;
  96
  97 /**
  98  * Utility method to help access elements of a sequence with one uniform
  99  * interface
 100  *
 101  * This can be useful for example when you are looping through a sequence and
 102  * want to modify another sequence based on the information in the current
 103  * sequence
 104  *
 105  *  auto range_one = std::make_tuple(1, 2, 3);
 106  *  auto range_two = std::make_tuple(4, 5, 6);
 107  *  folly::for_each(range_one, [&range_two](auto ele, auto index) {
 108  *    folly::fetch(range_two, index) = ele;
 109  *  });
 110  *
 111  * For non-tuple like ranges, this works by first trying to use the iterator
 112  * class if the iterator has been marked to be a random access iterator.  This
 113  * should be inspectable via the std::iterator_traits traits class.  If the
 114  * iterator class is not present or is not a random access iterator then the
 115  * implementation falls back to trying to use the indexing operator
 116  * (operator[]) to fetch the required element
 117  */
 118 template <typename Sequence, typename Index>
 119 FOLLY_CPP14_CONSTEXPR decltype(auto) fetch(Sequence&& sequence, Index&& index);
 120
 121 } // namespace folly
 122
 123 /**
 124  * Everything below this is deprecated.  Use the folly::for_each algorithm above
 125  * instead
 126  */
 127 /*
 128  * Form a local variable name from "FOR_EACH_" x __LINE__, so that
 129  * FOR_EACH can be nested without creating shadowed declarations.
 130  */
 131 #define _FE_ANON(x) FB_CONCATENATE(FOR_EACH_, FB_CONCATENATE(x, __LINE__))
 132
 133 /*
 134  * If you just want the element values, please use:
 135  *
 136  *    for (auto&& element : collection)
 137  *
 138  * If you need access to the iterators please write an explicit iterator loop
 139  */
 140 #define FOR_EACH(i, c)                                  \
 141   if (bool _FE_ANON(s1_) = false) {} else               \
 142     for (auto && _FE_ANON(s2_) = (c);                   \
 143          !_FE_ANON(s1_); _FE_ANON(s1_) = true)          \
 144       for (auto i = _FE_ANON(s2_).begin();              \
 145            i != _FE_ANON(s2_).end(); ++i)
 146
 147 /*
 148  * If you just want the element values, please use this (ranges-v3) construct:
 149  *
 150  *    for (auto&& element : collection | view::reverse)
 151  *
 152  * If you need access to the iterators please write an explicit iterator loop
 153  */
 154 #define FOR_EACH_R(i, c)                                \
 155   if (bool _FE_ANON(s1_) = false) {} else               \
 156     for (auto && _FE_ANON(s2_) = (c);                   \
 157          !_FE_ANON(s1_); _FE_ANON(s1_) = true)          \
 158       for (auto i = _FE_ANON(s2_).rbegin();             \
 159            i != _FE_ANON(s2_).rend(); ++i)
 160
 161 /*
 162  * If you just want the element values, please use this (ranges-v3) construct:
 163  *
 164  *    for (auto&& element : collection | view::zip(view::ints))
 165  *
 166  * If you need access to the iterators please write an explicit iterator loop
 167  * and use a counter variable
 168  */
 169 #define FOR_EACH_ENUMERATE(count, i, c)                                \
 170   if (bool _FE_ANON(s1_) = false) {} else                            \
 171     for (auto && FOR_EACH_state2 = (c);                                \
 172          !_FE_ANON(s1_); _FE_ANON(s1_) = true)                     \
 173       if (size_t _FE_ANON(n1_) = 0) {} else                            \
 174         if (const size_t& count = _FE_ANON(n1_)) {} else               \
 175           for (auto i = FOR_EACH_state2.begin();                       \
 176                i != FOR_EACH_state2.end(); ++_FE_ANON(n1_), ++i)
 177 /**
 178  * If you just want the keys, please use this (ranges-v3) construct:
 179  *
 180  *    for (auto&& element : collection | view::keys)
 181  *
 182  * If you just want the values, please use this (ranges-v3) construct:
 183  *
 184  *    for (auto&& element : collection | view::values)
 185  *
 186  * If you need to see both, use:
 187  *
 188  *    for (auto&& element : collection) {
 189  *      auto const& key = element.first;
 190  *      auto& value = element.second;
 191  *      ......
 192  *    }
 193  *
 194  */
 195 #define FOR_EACH_KV(k, v, c)                                  \
 196   if (unsigned int _FE_ANON(s1_) = 0) {} else                 \
 197     for (auto && _FE_ANON(s2_) = (c);                         \
 198          !_FE_ANON(s1_); _FE_ANON(s1_) = 1)                   \
 199       for (auto _FE_ANON(s3_) = _FE_ANON(s2_).begin();        \
 200            _FE_ANON(s3_) != _FE_ANON(s2_).end();              \
 201            _FE_ANON(s1_) == 2                                 \
 202              ? ((_FE_ANON(s1_) = 0), ++_FE_ANON(s3_))         \
 203              : (_FE_ANON(s3_) = _FE_ANON(s2_).end()))         \
 204         for (auto &k = _FE_ANON(s3_)->first;                  \
 205              !_FE_ANON(s1_); ++_FE_ANON(s1_))                 \
 206           for (auto &v = _FE_ANON(s3_)->second;               \
 207                !_FE_ANON(s1_); ++_FE_ANON(s1_))
 208
 209 namespace folly { namespace detail {
 210
 211 // Boost 1.48 lacks has_less, we emulate a subset of it here.
 212 template <typename T, typename U>
 213 class HasLess {
 214   struct BiggerThanChar { char unused[2]; };
 215   template <typename C, typename D> static char test(decltype(C() < D())*);
 216   template <typename, typename> static BiggerThanChar test(...);
 217
 218  public:
 219   enum { value = sizeof(test<T, U>(nullptr)) == 1 };
 220 };
 221
 222 /**
 223  * notThereYet helps the FOR_EACH_RANGE macro by opportunistically
 224  * using "<" instead of "!=" whenever available when checking for loop
 225  * termination. This makes e.g. examples such as FOR_EACH_RANGE (i,
 226  * 10, 5) execute zero iterations instead of looping virtually
 227  * forever. At the same time, some iterator types define "!=" but not
 228  * "<". The notThereYet function will dispatch differently for those.
 229  *
 230  * Below is the correct implementation of notThereYet. It is disabled
 231  * because of a bug in Boost 1.46: The filesystem::path::iterator
 232  * defines operator< (via boost::iterator_facade), but that in turn
 233  * uses distance_to which is undefined for that particular
 234  * iterator. So HasLess (defined above) identifies
 235  * boost::filesystem::path as properly comparable with <, but in fact
 236  * attempting to do so will yield a compile-time error.
 237  *
 238  * The else branch (active) contains a conservative
 239  * implementation.
 240  */
 241
 242 #if 0
 243
 244 template <class T, class U>
 245 typename std::enable_if<HasLess<T, U>::value, bool>::type
 246 notThereYet(T& iter, const U& end) {
 247   return iter < end;
 248 }
 249
 250 template <class T, class U>
 251 typename std::enable_if<!HasLess<T, U>::value, bool>::type
 252 notThereYet(T& iter, const U& end) {
 253   return iter != end;
 254 }
 255
 256 #else
 257
 258 template <class T, class U>
 259 typename std::enable_if<
 260   (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
 261   (std::is_pointer<T>::value && std::is_pointer<U>::value),
 262   bool>::type
 263 notThereYet(T& iter, const U& end) {
 264   return iter < end;
 265 }
 266
 267 template <class T, class U>
 268 typename std::enable_if<
 269   !(
 270     (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
 271     (std::is_pointer<T>::value && std::is_pointer<U>::value)
 272   ),
 273   bool>::type
 274 notThereYet(T& iter, const U& end) {
 275   return iter != end;
 276 }
 277
 278 #endif
 279
 280
 281 /**
 282  * downTo is similar to notThereYet, but in reverse - it helps the
 283  * FOR_EACH_RANGE_R macro.
 284  */
 285 template <class T, class U>
 286 typename std::enable_if<HasLess<U, T>::value, bool>::type
 287 downTo(T& iter, const U& begin) {
 288   return begin < iter--;
 289 }
 290
 291 template <class T, class U>
 292 typename std::enable_if<!HasLess<U, T>::value, bool>::type
 293 downTo(T& iter, const U& begin) {
 294   if (iter == begin) {
 295     return false;
 296   }
 297   --iter;
 298   return true;
 299 }
 300
 301 } }
 302
 303 /*
 304  * Look at the Ranges-v3 views and you'll probably find an easier way to build
 305  * the view you want but the equivalent is roughly:
 306  *
 307  *    for (auto& element : make_iterator_range(begin, end))
 308  */
 309 #define FOR_EACH_RANGE(i, begin, end)           \
 310   for (auto i = (true ? (begin) : (end));       \
 311        ::folly::detail::notThereYet(i, (end));  \
 312        ++i)
 313
 314 /*
 315  * Look at the Ranges-v3 views and you'll probably find an easier way to build
 316  * the view you want but the equivalent is roughly:
 317  *
 318  *    for (auto& element : make_iterator_range(begin, end) | view::reverse)
 319  */
 320 #define FOR_EACH_RANGE_R(i, begin, end) \
 321   for (auto i = (false ? (begin) : (end)); ::folly::detail::downTo(i, (begin));)
 322
 323 #include <folly/Foreach-inl.h>