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
24namespace 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 */
85template <typename Range, typename Func>
86FOLLY_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 */
93namespace for_each_detail {
94enum class LoopControl : bool { BREAK, CONTINUE };
95} // namespace for_each_detail
96
97constexpr auto loop_break = for_each_detail::LoopControl::BREAK;
98constexpr 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 */
121template <typename Sequence, typename Index>
122FOLLY_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
208namespace folly {
209namespace detail {
210
211// Boost 1.48 lacks has_less, we emulate a subset of it here.
212template <typename T, typename U>
213class 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
248template <class T, class U>
249typename std::enable_if<HasLess<T, U>::value, bool>::type
250notThereYet(T& iter, const U& end) {
251 return iter < end;
252}
253
254template <class T, class U>
255typename std::enable_if<!HasLess<T, U>::value, bool>::type
256notThereYet(T& iter, const U& end) {
257 return iter != end;
258}
259
260#else
261
262template <class T, class U>
263typename 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
267notThereYet(T& iter, const U& end) {
268 return iter < end;
269}
270
271template <class T, class U>
272typename 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
276notThereYet(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 */
286template <class T, class U>
287typename std::enable_if<HasLess<U, T>::value, bool>::type downTo(
288 T& iter,
289 const U& begin) {
290 return begin < iter--;
291}
292
293template <class T, class U>
294typename 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