2 * Copyright 2017-present Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include <initializer_list>
22 #include <type_traits>
25 #include <folly/Traits.h>
29 namespace for_each_detail {
41 * The adl_ functions below lookup the function name in the namespace of the
42 * type of the object being passed into the function. If no function with
43 * that name exists for the passed object then the default std:: versions are
46 template <std::size_t Index, typename Type>
47 auto adl_get(Type&& instance) -> decltype(get<Index>(std::declval<Type>())) {
48 return get<Index>(std::forward<Type>(instance));
50 template <typename Type>
51 auto adl_begin(Type&& instance) -> decltype(begin(instance)) {
52 return begin(instance);
54 template <typename Type>
55 auto adl_end(Type&& instance) -> decltype(end(instance)) {
62 * Enable if the range supports fetching via non member get<>()
65 using EnableIfNonMemberGetFound =
66 void_t<decltype(adl::adl_get<0>(std::declval<T>()))>;
68 * Enable if the range supports fetching via a member get<>()
71 using EnableIfMemberGetFound =
72 void_t<decltype(std::declval<T>().template get<0>())>;
75 * A get that tries ADL get<> first and if that is not found tries to execute
76 * a member function get<> on the instance, just as proposed by the structured
77 * bindings proposal here 11.5.3
78 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf
80 template <std::size_t Index, typename Type, typename = void>
83 static auto impl(T&& instance)
84 -> decltype(adl::adl_get<Index>(std::declval<T>())) {
85 return adl::adl_get<Index>(std::forward<T>(instance));
88 template <std::size_t Index, typename Type>
89 struct Get<Index, Type, EnableIfMemberGetFound<Type>> {
91 static auto impl(T&& instance)
92 -> decltype(std::declval<T>().template get<Index>()) {
93 return std::forward<T>(instance).template get<Index>();
101 * Check if the range is a tuple or a range
103 template <typename Type, typename T = typename std::decay<Type>::type>
104 using EnableIfTuple = void_t<
105 decltype(Get<0, T>::impl(std::declval<T>())),
106 decltype(std::tuple_size<T>::value)>;
109 * Check if the range is a range
111 template <typename Type, typename T = typename std::decay<Type>::type>
112 using EnableIfRange = void_t<
113 decltype(adl::adl_begin(std::declval<T>())),
114 decltype(adl::adl_end(std::declval<T>()))>;
117 * Forwards the return value of the first element of the range, used to
118 * determine the type of the first element in the range in SFINAE use cases
120 template <typename Sequence, typename = void>
121 struct DeclvalSequence {
122 using type = decltype(*(adl::adl_begin(std::declval<Sequence>())));
125 template <typename Sequence>
126 struct DeclvalSequence<Sequence, EnableIfTuple<Sequence>> {
127 using type = decltype(Get<0, Sequence>::impl(std::declval<Sequence>()));
131 * Check if the functor accepts one or two arguments, one of the first element
132 * in the range, assuming that all the other elements can also be passed to the
133 * functor, and the second being an instantiation of std::integral_constant,
134 * and the third being an instantiation of LoopControl, to provide
135 * breakability to the loop
137 template <typename Sequence, typename Func>
138 using EnableIfAcceptsOneArgument = void_t<decltype(std::declval<Func>()(
139 std::declval<typename DeclvalSequence<Sequence>::type>()))>;
140 template <typename Sequence, typename Func>
141 using EnableIfAcceptsTwoArguments = void_t<decltype(std::declval<Func>()(
142 std::declval<typename DeclvalSequence<Sequence>::type>(),
143 std::integral_constant<std::size_t, 0>{}))>;
144 template <typename Sequence, typename Func>
145 using EnableIfAcceptsThreeArguments = void_t<decltype(std::declval<Func>()(
146 std::declval<typename DeclvalSequence<Sequence>::type>(),
147 std::integral_constant<std::size_t, 0>{},
148 adl::adl_begin(std::declval<Sequence>())))>;
149 template <typename Sequence, typename Func>
150 using EnableIfBreaksRange = std::enable_if_t<std::is_same<
151 typename std::decay<decltype(std::declval<Func>()(
152 std::declval<typename DeclvalSequence<Sequence>::type>(),
154 adl::adl_begin(std::declval<Sequence>())))>::type,
155 LoopControl>::value>;
156 template <typename Sequence, typename Func>
157 using EnableIfBreaksTuple = std::enable_if_t<std::is_same<
158 typename std::decay<decltype(std::declval<Func>()(
159 std::declval<typename DeclvalSequence<Sequence>::type>(),
160 std::integral_constant<std::size_t, 0>{}))>::type,
161 LoopControl>::value>;
163 * Enables if the sequence has random access iterators
165 template <typename Sequence>
166 using EnableIfRandomAccessIterators = std::enable_if_t<std::is_same<
167 typename std::iterator_traits<typename std::decay<decltype(
168 adl::adl_begin(std::declval<Sequence>()))>::type>::iterator_category,
169 std::random_access_iterator_tag>::value>;
170 template <typename Sequence, typename Index>
171 using EnableIfHasIndexingOperator =
172 void_t<decltype(std::declval<Sequence>()[std::declval<Index>()])>;
175 * Implementation for the range iteration, this provides specializations in
176 * the case where the function returns a break or continue.
178 template <typename Seq, typename F, typename = void>
179 struct ForEachRange {
180 template <typename Sequence, typename Func>
181 static void impl(Sequence&& range, Func& func) {
182 auto first = adl::adl_begin(range);
183 auto last = adl::adl_end(range);
184 for (auto index = std::size_t{0}; first != last; ++index) {
185 auto next = std::next(first);
186 func(*first, index, first);
192 template <typename Seq, typename F>
193 struct ForEachRange<Seq, F, EnableIfBreaksRange<Seq, F>> {
194 template <typename Sequence, typename Func>
195 static void impl(Sequence&& range, Func& func) {
196 auto first = adl::adl_begin(range);
197 auto last = adl::adl_end(range);
198 for (auto index = std::size_t{0}; first != last; ++index) {
199 auto next = std::next(first);
200 if (loop_break == func(*first, index, first)) {
209 * Implementations for the runtime function
214 EnableIfAcceptsThreeArguments<Sequence, Func>* = nullptr>
215 void for_each_range_impl(Sequence&& range, Func& func) {
216 ForEachRange<Sequence, Func>::impl(std::forward<Sequence>(range), func);
221 EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
222 void for_each_range_impl(Sequence&& range, Func& func) {
223 // make a three arg adaptor for the function passed in so that the main
224 // implementation function can be used
225 auto three_arg_adaptor = [&func](
226 auto&& ele, auto index, auto) -> decltype(auto) {
227 return func(std::forward<decltype(ele)>(ele), index);
229 for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
235 EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
236 void for_each_range_impl(Sequence&& range, Func& func) {
237 // make a three argument adaptor for the function passed in that just ignores
238 // the second and third argument
239 auto three_arg_adaptor = [&func](auto&& ele, auto, auto) -> decltype(auto) {
240 return func(std::forward<decltype(ele)>(ele));
242 for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
246 * Handlers for iteration
249 * The class provides a way to tell whether the function passed in to the
250 * algorithm returns an instance of LoopControl, if it does then the break-able
251 * implementation will be used. If the function provided to the algorithm
252 * does not use the break API, then the basic no break, 0 overhead
253 * implementation will be used
255 template <typename Seq, typename F, typename = void>
256 struct ForEachTupleImpl {
257 template <typename Sequence, typename Func, std::size_t... Indices>
259 impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
260 // unroll the loop in an initializer list construction parameter expansion
262 static_cast<void>(std::initializer_list<int>{
264 Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
265 std::integral_constant<std::size_t, Indices>{}),
269 template <typename Seq, typename F>
270 struct ForEachTupleImpl<Seq, F, EnableIfBreaksTuple<Seq, F>> {
271 template <typename Sequence, typename Func, std::size_t... Indices>
273 impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
274 // unroll the loop in an initializer list construction parameter expansion
276 LoopControl break_or_not = LoopControl::CONTINUE;
278 // cast to void to ignore the result, use the initialzer list constructor
279 // to do the loop execution, the ternary conditional will decide whether
280 // or not to evaluate the result
281 static_cast<void>(std::initializer_list<int>{
282 (((break_or_not == loop_continue)
283 ? (break_or_not = func(
284 Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
285 std::integral_constant<std::size_t, Indices>{}))
292 * The two top level compile time loop iteration functions handle the dispatch
293 * based on the number of arguments the passed in function can be passed, if 2
294 * arguments can be passed then the implementation dispatches work further to
295 * the implementation classes above. If not then an adaptor is constructed
296 * which is passed on to the 2 argument specialization, which then in turn
297 * forwards implementation to the implementation classes above
302 EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
303 void for_each_tuple_impl(Sequence&& seq, Func& func) {
304 // pass the length as an index sequence to the implementation as an
305 // optimization over manual template "tail recursion" unrolling
306 constexpr auto length =
307 std::tuple_size<typename std::decay<Sequence>::type>::value;
308 ForEachTupleImpl<Sequence, Func>::impl(
309 std::forward<Sequence>(seq), func, std::make_index_sequence<length>{});
314 EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
315 void for_each_tuple_impl(Sequence&& seq, Func& func) {
316 // make an adaptor for the function passed in, in case it can only be passed
318 auto two_arg_adaptor = [&func](auto&& ele, auto) -> decltype(auto) {
319 return func(std::forward<decltype(ele)>(ele));
321 for_each_tuple_impl(std::forward<Sequence>(seq), two_arg_adaptor);
325 * Top level handlers for the for_each loop, the basic specialization handles
326 * ranges and the specialized version handles compile time ranges (tuple like)
328 * This implies that if a range is a compile time range, its compile time
329 * get<> API (whether through a member function or through a ADL looked up
330 * method) will be used in preference over iterators
332 template <typename R, typename = void>
334 template <typename Sequence, typename Func>
335 static void impl(Sequence&& range, Func& func) {
336 for_each_tuple_impl(std::forward<Sequence>(range), func);
339 template <typename R>
340 struct ForEachImpl<R, EnableIfRange<R>> {
341 template <typename Sequence, typename Func>
342 static void impl(Sequence&& range, Func& func) {
343 for_each_range_impl(std::forward<Sequence>(range), func);
347 template <typename S, typename I, typename = void>
348 struct FetchIteratorIndexImpl {
349 template <typename Sequence, typename Index>
350 static decltype(auto) impl(Sequence&& sequence, Index&& index) {
351 return std::forward<Sequence>(sequence)[std::forward<Index>(index)];
354 template <typename S, typename I>
355 struct FetchIteratorIndexImpl<S, I, EnableIfRandomAccessIterators<S>> {
356 template <typename Sequence, typename Index>
357 static decltype(auto) impl(Sequence&& sequence, Index index) {
358 return *(adl::adl_begin(std::forward<Sequence>(sequence)) + index);
361 template <typename S, typename = void>
363 template <typename Sequence, typename Index>
364 static decltype(auto) impl(Sequence&& sequence, Index index) {
365 return Get<static_cast<std::size_t>(index), Sequence>::impl(
366 std::forward<Sequence>(sequence));
369 template <typename S>
370 struct FetchImpl<S, EnableIfRange<S>> {
371 template <typename Sequence, typename Index>
372 static decltype(auto) impl(Sequence&& sequence, Index&& index) {
373 return FetchIteratorIndexImpl<Sequence, Index>::impl(
374 std::forward<Sequence>(sequence), std::forward<Index>(index));
378 } // namespace for_each_detail
380 template <typename Sequence, typename Func>
381 constexpr Func for_each(Sequence&& range, Func func) {
382 for_each_detail::ForEachImpl<typename std::decay<Sequence>::type>::impl(
383 std::forward<Sequence>(range), func);
387 template <typename Sequence, typename Index>
388 constexpr decltype(auto) fetch(Sequence&& sequence, Index&& index) {
389 return for_each_detail::FetchImpl<Sequence>::impl(
390 std::forward<Sequence>(sequence), std::forward<Index>(index));