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 /*
  20  * Iterim macros (until we have C++0x range-based for) that simplify
  21  * writing loops of the form
  22  *
  23  * for (Container<data>::iterator i = c.begin(); i != c.end(); ++i) statement
  24  *
  25  * Just replace the above with:
  26  *
  27  * FOR_EACH (i, c) statement
  28  *
  29  * and everything is taken care of.
  30  *
  31  * The implementation is a bit convoluted to make sure the container is
  32  * evaluated only once (however, keep in mind that c.end() is evaluated
  33  * at every pass through the loop). To ensure the container is not
  34  * evaluated multiple times, the macro defines one do-nothing if
  35  * statement to inject the Boolean variable FOR_EACH_state1, and then a
  36  * for statement that is executed only once, which defines the variable
  37  * FOR_EACH_state2 holding an rvalue reference to the container being
  38  * iterated. The workhorse is the last loop, which uses the just-defined
  39  * rvalue reference FOR_EACH_state2.
  40  *
  41  * The state variables are nested so they don't interfere; you can use
  42  * FOR_EACH multiple times in the same scope, either at the same level or
  43  * nested.
  44  *
  45  * In optimized builds g++ eliminates the extra gymnastics entirely and
  46  * generates code 100% identical to the handwritten loop.
  47  */
  48
  49 #include <type_traits>
  50 #include <folly/Preprocessor.h>
  51
  52 /*
  53  * Form a local variable name from "FOR_EACH_" x __LINE__, so that
  54  * FOR_EACH can be nested without creating shadowed declarations.
  55  */
  56 #define _FE_ANON(x) FB_CONCATENATE(FOR_EACH_, FB_CONCATENATE(x, __LINE__))
  57
  58 /*
  59  * Shorthand for:
  60  *   for (auto i = c.begin(); i != c.end(); ++i)
  61  * except that c is evaluated only once.
  62  */
  63 #define FOR_EACH(i, c)                                  \
  64   if (bool _FE_ANON(s1_) = false) {} else               \
  65     for (auto && _FE_ANON(s2_) = (c);                   \
  66          !_FE_ANON(s1_); _FE_ANON(s1_) = true)          \
  67       for (auto i = _FE_ANON(s2_).begin();              \
  68            i != _FE_ANON(s2_).end(); ++i)
  69
  70 /*
  71  * Similar to FOR_EACH, but iterates the container backwards by
  72  * using rbegin() and rend().
  73  */
  74 #define FOR_EACH_R(i, c)                                \
  75   if (bool _FE_ANON(s1_) = false) {} else               \
  76     for (auto && _FE_ANON(s2_) = (c);                   \
  77          !_FE_ANON(s1_); _FE_ANON(s1_) = true)          \
  78       for (auto i = _FE_ANON(s2_).rbegin();             \
  79            i != _FE_ANON(s2_).rend(); ++i)
  80
  81 /*
  82  * Similar to FOR_EACH but also allows client to specify a 'count' variable
  83  * to track the current iteration in the loop (starting at zero).
  84  * Similar to python's enumerate() function.  For example:
  85  * string commaSeparatedValues = "VALUES: ";
  86  * FOR_EACH_ENUMERATE(ii, value, columns) {   // don't want comma at the end!
  87  *   commaSeparatedValues += (ii == 0) ? *value : string(",") + *value;
  88  * }
  89  */
  90 #define FOR_EACH_ENUMERATE(count, i, c)                                \
  91   if (bool _FE_ANON(s1_) = false) {} else                            \
  92     for (auto && FOR_EACH_state2 = (c);                                \
  93          !_FE_ANON(s1_); _FE_ANON(s1_) = true)                     \
  94       if (size_t _FE_ANON(n1_) = 0) {} else                            \
  95         if (const size_t& count = _FE_ANON(n1_)) {} else               \
  96           for (auto i = FOR_EACH_state2.begin();                       \
  97                i != FOR_EACH_state2.end(); ++_FE_ANON(n1_), ++i)
  98
  99 /**
 100  * Similar to FOR_EACH, but gives the user the key and value for each entry in
 101  * the container, instead of just the iterator to the entry. For example:
 102  *   map<string, string> testMap;
 103  *   FOR_EACH_KV(key, value, testMap) {
 104  *      cout << key << " " << value;
 105  *   }
 106  */
 107 #define FOR_EACH_KV(k, v, c)                                  \
 108   if (unsigned int _FE_ANON(s1_) = 0) {} else                 \
 109     for (auto && _FE_ANON(s2_) = (c);                         \
 110          !_FE_ANON(s1_); _FE_ANON(s1_) = 1)                   \
 111       for (auto _FE_ANON(s3_) = _FE_ANON(s2_).begin();        \
 112            _FE_ANON(s3_) != _FE_ANON(s2_).end();              \
 113            _FE_ANON(s1_) == 2                                 \
 114              ? ((_FE_ANON(s1_) = 0), ++_FE_ANON(s3_))         \
 115              : (_FE_ANON(s3_) = _FE_ANON(s2_).end()))         \
 116         for (auto &k = _FE_ANON(s3_)->first;                  \
 117              !_FE_ANON(s1_); ++_FE_ANON(s1_))                 \
 118           for (auto &v = _FE_ANON(s3_)->second;               \
 119                !_FE_ANON(s1_); ++_FE_ANON(s1_))
 120
 121 namespace folly { namespace detail {
 122
 123 // Boost 1.48 lacks has_less, we emulate a subset of it here.
 124 template <typename T, typename U>
 125 class HasLess {
 126   struct BiggerThanChar { char unused[2]; };
 127   template <typename C, typename D> static char test(decltype(C() < D())*);
 128   template <typename, typename> static BiggerThanChar test(...);
 129 public:
 130   enum { value = sizeof(test<T, U>(0)) == 1 };
 131 };
 132
 133 /**
 134  * notThereYet helps the FOR_EACH_RANGE macro by opportunistically
 135  * using "<" instead of "!=" whenever available when checking for loop
 136  * termination. This makes e.g. examples such as FOR_EACH_RANGE (i,
 137  * 10, 5) execute zero iterations instead of looping virtually
 138  * forever. At the same time, some iterator types define "!=" but not
 139  * "<". The notThereYet function will dispatch differently for those.
 140  *
 141  * Below is the correct implementation of notThereYet. It is disabled
 142  * because of a bug in Boost 1.46: The filesystem::path::iterator
 143  * defines operator< (via boost::iterator_facade), but that in turn
 144  * uses distance_to which is undefined for that particular
 145  * iterator. So HasLess (defined above) identifies
 146  * boost::filesystem::path as properly comparable with <, but in fact
 147  * attempting to do so will yield a compile-time error.
 148  *
 149  * The else branch (active) contains a conservative
 150  * implementation.
 151  */
 152
 153 #if 0
 154
 155 template <class T, class U>
 156 typename std::enable_if<HasLess<T, U>::value, bool>::type
 157 notThereYet(T& iter, const U& end) {
 158   return iter < end;
 159 }
 160
 161 template <class T, class U>
 162 typename std::enable_if<!HasLess<T, U>::value, bool>::type
 163 notThereYet(T& iter, const U& end) {
 164   return iter != end;
 165 }
 166
 167 #else
 168
 169 template <class T, class U>
 170 typename std::enable_if<
 171   (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
 172   (std::is_pointer<T>::value && std::is_pointer<U>::value),
 173   bool>::type
 174 notThereYet(T& iter, const U& end) {
 175   return iter < end;
 176 }
 177
 178 template <class T, class U>
 179 typename std::enable_if<
 180   !(
 181     (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
 182     (std::is_pointer<T>::value && std::is_pointer<U>::value)
 183   ),
 184   bool>::type
 185 notThereYet(T& iter, const U& end) {
 186   return iter != end;
 187 }
 188
 189 #endif
 190
 191
 192 /**
 193  * downTo is similar to notThereYet, but in reverse - it helps the
 194  * FOR_EACH_RANGE_R macro.
 195  */
 196 template <class T, class U>
 197 typename std::enable_if<HasLess<U, T>::value, bool>::type
 198 downTo(T& iter, const U& begin) {
 199   return begin < iter--;
 200 }
 201
 202 template <class T, class U>
 203 typename std::enable_if<!HasLess<U, T>::value, bool>::type
 204 downTo(T& iter, const U& begin) {
 205   if (iter == begin) return false;
 206   --iter;
 207   return true;
 208 }
 209
 210 } }
 211
 212 /*
 213  * Iteration with given limits. end is assumed to be reachable from
 214  * begin. end is evaluated every pass through the loop.
 215  *
 216  * NOTE: The type of the loop variable should be the common type of "begin"
 217  *       and "end". e.g. If "begin" is "int" but "end" is "long", we want "i"
 218  *       to be "long". This is done by getting the type of (true ? begin : end)
 219  */
 220 #define FOR_EACH_RANGE(i, begin, end)           \
 221   for (auto i = (true ? (begin) : (end));       \
 222        ::folly::detail::notThereYet(i, (end));  \
 223        ++i)
 224
 225 /*
 226  * Iteration with given limits. begin is assumed to be reachable from
 227  * end by successive decrements. begin is evaluated every pass through
 228  * the loop.
 229  *
 230  * NOTE: The type of the loop variable should be the common type of "begin"
 231  *       and "end". e.g. If "begin" is "int" but "end" is "long", we want "i"
 232  *       to be "long". This is done by getting the type of (false ? begin : end)
 233  */
 234 #define FOR_EACH_RANGE_R(i, begin, end) \
 235   for (auto i = (false ? (begin) : (end)); ::folly::detail::downTo(i, (begin));)