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