folly/Foreach.h

   1 /*
   2  * Copyright 2016 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  * only evaluated 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 a 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
  51 /*
  52  * Shorthand for:
  53  *   for (auto i = c.begin(); i != c.end(); ++i)
  54  * except that c is only evaluated once.
  55  */
  56 #define FOR_EACH(i, c)                              \
  57   if (bool FOR_EACH_state1 = false) {} else         \
  58     for (auto && FOR_EACH_state2 = (c);             \
  59          !FOR_EACH_state1; FOR_EACH_state1 = true)  \
  60       for (auto i = FOR_EACH_state2.begin();        \
  61            i != FOR_EACH_state2.end(); ++i)
  62
  63 /*
  64  * Similar to FOR_EACH, but iterates the container backwards by
  65  * using rbegin() and rend().
  66  */
  67 #define FOR_EACH_R(i, c)                                \
  68   if (bool FOR_EACH_R_state1 = false) {} else           \
  69     for (auto && FOR_EACH_R_state2 = (c);               \
  70          !FOR_EACH_R_state1; FOR_EACH_R_state1 = true)  \
  71       for (auto i = FOR_EACH_R_state2.rbegin();         \
  72            i != FOR_EACH_R_state2.rend(); ++i)
  73
  74 /*
  75  * Similar to FOR_EACH but also allows client to specify a 'count' variable
  76  * to track the current iteration in the loop (starting at zero).
  77  * Similar to python's enumerate() function.  For example:
  78  * string commaSeparatedValues = "VALUES: ";
  79  * FOR_EACH_ENUMERATE(ii, value, columns) {   // don't want comma at the end!
  80  *   commaSeparatedValues += (ii == 0) ? *value : string(",") + *value;
  81  * }
  82  */
  83 #define FOR_EACH_ENUMERATE(count, i, c)                                \
  84   if (bool FOR_EACH_state1 = false) {} else                            \
  85     for (auto && FOR_EACH_state2 = (c);                                \
  86          !FOR_EACH_state1; FOR_EACH_state1 = true)                     \
  87       if (size_t FOR_EACH_privateCount = 0) {} else                    \
  88         if (const size_t& count = FOR_EACH_privateCount) {} else       \
  89           for (auto i = FOR_EACH_state2.begin();                       \
  90                i != FOR_EACH_state2.end(); ++FOR_EACH_privateCount, ++i)
  91
  92 /**
  93  * Similar to FOR_EACH, but gives the user the key and value for each entry in
  94  * the container, instead of just the iterator to the entry. For example:
  95  *   map<string, string> testMap;
  96  *   FOR_EACH_KV(key, value, testMap) {
  97  *      cout << key << " " << value;
  98  *   }
  99  */
 100 #define FOR_EACH_KV(k, v, c)                                    \
 101   if (unsigned int FOR_EACH_state1 = 0) {} else                 \
 102     for (auto && FOR_EACH_state2 = (c);                         \
 103          !FOR_EACH_state1; FOR_EACH_state1 = 1)                 \
 104       for (auto FOR_EACH_state3 = FOR_EACH_state2.begin();      \
 105            FOR_EACH_state3 != FOR_EACH_state2.end();            \
 106            FOR_EACH_state1 == 2                                 \
 107              ? ((FOR_EACH_state1 = 0), ++FOR_EACH_state3)       \
 108              : (FOR_EACH_state3 = FOR_EACH_state2.end()))       \
 109         for (auto &k = FOR_EACH_state3->first;                  \
 110              !FOR_EACH_state1; ++FOR_EACH_state1)               \
 111           for (auto &v = FOR_EACH_state3->second;               \
 112                !FOR_EACH_state1; ++FOR_EACH_state1)
 113
 114 namespace folly { namespace detail {
 115
 116 // Boost 1.48 lacks has_less, we emulate a subset of it here.
 117 template <typename T, typename U>
 118 class HasLess {
 119   struct BiggerThanChar { char unused[2]; };
 120   template <typename C, typename D> static char test(decltype(C() < D())*);
 121   template <typename, typename> static BiggerThanChar test(...);
 122 public:
 123   enum { value = sizeof(test<T, U>(0)) == 1 };
 124 };
 125
 126 /**
 127  * notThereYet helps the FOR_EACH_RANGE macro by opportunistically
 128  * using "<" instead of "!=" whenever available when checking for loop
 129  * termination. This makes e.g. examples such as FOR_EACH_RANGE (i,
 130  * 10, 5) execute zero iterations instead of looping virtually
 131  * forever. At the same time, some iterator types define "!=" but not
 132  * "<". The notThereYet function will dispatch differently for those.
 133  *
 134  * Below is the correct implementation of notThereYet. It is disabled
 135  * because of a bug in Boost 1.46: The filesystem::path::iterator
 136  * defines operator< (via boost::iterator_facade), but that in turn
 137  * uses distance_to which is undefined for that particular
 138  * iterator. So HasLess (defined above) identifies
 139  * boost::filesystem::path as properly comparable with <, but in fact
 140  * attempting to do so will yield a compile-time error.
 141  *
 142  * The else branch (active) contains a conservative
 143  * implementation.
 144  */
 145
 146 #if 0
 147
 148 template <class T, class U>
 149 typename std::enable_if<HasLess<T, U>::value, bool>::type
 150 notThereYet(T& iter, const U& end) {
 151   return iter < end;
 152 }
 153
 154 template <class T, class U>
 155 typename std::enable_if<!HasLess<T, U>::value, bool>::type
 156 notThereYet(T& iter, const U& end) {
 157   return iter != end;
 158 }
 159
 160 #else
 161
 162 template <class T, class U>
 163 typename std::enable_if<
 164   (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
 165   (std::is_pointer<T>::value && std::is_pointer<U>::value),
 166   bool>::type
 167 notThereYet(T& iter, const U& end) {
 168   return iter < end;
 169 }
 170
 171 template <class T, class U>
 172 typename std::enable_if<
 173   !(
 174     (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
 175     (std::is_pointer<T>::value && std::is_pointer<U>::value)
 176   ),
 177   bool>::type
 178 notThereYet(T& iter, const U& end) {
 179   return iter != end;
 180 }
 181
 182 #endif
 183
 184
 185 /**
 186  * downTo is similar to notThereYet, but in reverse - it helps the
 187  * FOR_EACH_RANGE_R macro.
 188  */
 189 template <class T, class U>
 190 typename std::enable_if<HasLess<U, T>::value, bool>::type
 191 downTo(T& iter, const U& begin) {
 192   return begin < iter--;
 193 }
 194
 195 template <class T, class U>
 196 typename std::enable_if<!HasLess<U, T>::value, bool>::type
 197 downTo(T& iter, const U& begin) {
 198   if (iter == begin) return false;
 199   --iter;
 200   return true;
 201 }
 202
 203 } }
 204
 205 /*
 206  * Iteration with given limits. end is assumed to be reachable from
 207  * begin. end is evaluated every pass through the loop.
 208  *
 209  * NOTE: The type of the loop variable should be the common type of "begin"
 210  *       and "end". e.g. If "begin" is "int" but "end" is "long", we want "i"
 211  *       to be "long". This is done by getting the type of (true ? begin : end)
 212  */
 213 #define FOR_EACH_RANGE(i, begin, end)           \
 214   for (auto i = (true ? (begin) : (end));       \
 215        ::folly::detail::notThereYet(i, (end));  \
 216        ++i)
 217
 218 /*
 219  * Iteration with given limits. begin is assumed to be reachable from
 220  * end by successive decrements. begin is evaluated every pass through
 221  * the loop.
 222  *
 223  * NOTE: The type of the loop variable should be the common type of "begin"
 224  *       and "end". e.g. If "begin" is "int" but "end" is "long", we want "i"
 225  *       to be "long". This is done by getting the type of (false ? begin : end)
 226  */
 227 #define FOR_EACH_RANGE_R(i, begin, end) \
 228   for (auto i = (false ? (begin) : (end)); ::folly::detail::downTo(i, (begin));)