ba744e8fffac4a8d3fb5520c8a1017d116389810
[folly.git] / folly / container / 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 } // namespace detail
302 } // namespace folly
303
304 /*
305  * Look at the Ranges-v3 views and you'll probably find an easier way to build
306  * the view you want but the equivalent is roughly:
307  *
308  *    for (auto& element : make_iterator_range(begin, end))
309  */
310 #define FOR_EACH_RANGE(i, begin, end)           \
311   for (auto i = (true ? (begin) : (end));       \
312        ::folly::detail::notThereYet(i, (end));  \
313        ++i)
314
315 /*
316  * Look at the Ranges-v3 views and you'll probably find an easier way to build
317  * the view you want but the equivalent is roughly:
318  *
319  *    for (auto& element : make_iterator_range(begin, end) | view::reverse)
320  */
321 #define FOR_EACH_RANGE_R(i, begin, end) \
322   for (auto i = (false ? (begin) : (end)); ::folly::detail::downTo(i, (begin));)
323
324 #include <folly/container/Foreach-inl.h>