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