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/Portability.h>
26 #include <folly/Traits.h>
30 namespace for_each_detail {
42 * The adl_ functions below lookup the function name in the namespace of the
43 * type of the object being passed into the function. If no function with
44 * that name exists for the passed object then the default std:: versions are
47 template <std::size_t Index, typename Type>
48 auto adl_get(Type&& instance) -> decltype(get<Index>(std::declval<Type>())) {
49 return get<Index>(std::forward<Type>(instance));
51 template <typename Type>
52 auto adl_begin(Type&& instance) -> decltype(begin(instance)) {
53 return begin(instance);
55 template <typename Type>
56 auto adl_end(Type&& instance) -> decltype(end(instance)) {
63 * Enable if the range supports fetching via non member get<>()
66 using EnableIfNonMemberGetFound =
67 void_t<decltype(adl::adl_get<0>(std::declval<T>()))>;
69 * Enable if the range supports fetching via a member get<>()
72 using EnableIfMemberGetFound =
73 void_t<decltype(std::declval<T>().template get<0>())>;
76 * A get that tries ADL get<> first and if that is not found tries to execute
77 * a member function get<> on the instance, just as proposed by the structured
78 * bindings proposal here 11.5.3
79 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf
81 template <std::size_t Index, typename Type, typename = void>
84 static auto impl(T&& instance)
85 -> decltype(adl::adl_get<Index>(std::declval<T>())) {
86 return adl::adl_get<Index>(std::forward<T>(instance));
89 template <std::size_t Index, typename Type>
90 struct Get<Index, Type, EnableIfMemberGetFound<Type>> {
92 static auto impl(T&& instance)
93 -> decltype(std::declval<T>().template get<Index>()) {
94 return std::forward<T>(instance).template get<Index>();
102 * Check if the range is a tuple or a range
104 template <typename Type, typename T = typename std::decay<Type>::type>
105 using EnableIfTuple = void_t<
106 decltype(Get<0, T>::impl(std::declval<T>())),
107 decltype(std::tuple_size<T>::value)>;
110 * Check if the range is a range
112 template <typename Type, typename T = typename std::decay<Type>::type>
113 using EnableIfRange = void_t<
114 decltype(adl::adl_begin(std::declval<T>())),
115 decltype(adl::adl_end(std::declval<T>()))>;
118 * Forwards the return value of the first element of the range, used to
119 * determine the type of the first element in the range in SFINAE use cases
121 template <typename Sequence, typename = void>
122 struct DeclvalSequence {
123 using type = decltype(*(adl::adl_begin(std::declval<Sequence>())));
126 template <typename Sequence>
127 struct DeclvalSequence<Sequence, EnableIfTuple<Sequence>> {
128 using type = decltype(Get<0, Sequence>::impl(std::declval<Sequence>()));
132 * Check if the functor accepts one or two arguments, one of the first element
133 * in the range, assuming that all the other elements can also be passed to the
134 * functor, and the second being an instantiation of std::integral_constant,
135 * and the third being an instantiation of LoopControl, to provide
136 * breakability to the loop
138 template <typename Sequence, typename Func>
139 using EnableIfAcceptsOneArgument = void_t<decltype(std::declval<Func>()(
140 std::declval<typename DeclvalSequence<Sequence>::type>()))>;
141 template <typename Sequence, typename Func>
142 using EnableIfAcceptsTwoArguments = void_t<decltype(std::declval<Func>()(
143 std::declval<typename DeclvalSequence<Sequence>::type>(),
144 std::integral_constant<std::size_t, 0>{}))>;
145 template <typename Sequence, typename Func>
146 using EnableIfAcceptsThreeArguments = void_t<decltype(std::declval<Func>()(
147 std::declval<typename DeclvalSequence<Sequence>::type>(),
148 std::integral_constant<std::size_t, 0>{},
149 adl::adl_begin(std::declval<Sequence>())))>;
150 template <typename Sequence, typename Func>
151 using EnableIfBreaksRange = std::enable_if_t<std::is_same<
152 typename std::decay<decltype(std::declval<Func>()(
153 std::declval<typename DeclvalSequence<Sequence>::type>(),
155 adl::adl_begin(std::declval<Sequence>())))>::type,
156 LoopControl>::value>;
157 template <typename Sequence, typename Func>
158 using EnableIfBreaksTuple = std::enable_if_t<std::is_same<
159 typename std::decay<decltype(std::declval<Func>()(
160 std::declval<typename DeclvalSequence<Sequence>::type>(),
161 std::integral_constant<std::size_t, 0>{}))>::type,
162 LoopControl>::value>;
164 * Enables if the sequence has random access iterators
166 template <typename Sequence>
167 using EnableIfRandomAccessIterators = std::enable_if_t<std::is_same<
168 typename std::iterator_traits<typename std::decay<decltype(
169 adl::adl_begin(std::declval<Sequence>()))>::type>::iterator_category,
170 std::random_access_iterator_tag>::value>;
171 template <typename Sequence, typename Index>
172 using EnableIfHasIndexingOperator =
173 void_t<decltype(std::declval<Sequence>()[std::declval<Index>()])>;
176 * Implementation for the range iteration, this provides specializations in
177 * the case where the function returns a break or continue.
179 template <typename Seq, typename F, typename = void>
180 struct ForEachRange {
181 template <typename Sequence, typename Func>
182 static void impl(Sequence&& range, Func& func) {
183 auto first = adl::adl_begin(range);
184 auto last = adl::adl_end(range);
185 for (auto index = std::size_t{0}; first != last; ++index) {
186 auto next = std::next(first);
187 func(*first, index, first);
193 template <typename Seq, typename F>
194 struct ForEachRange<Seq, F, EnableIfBreaksRange<Seq, F>> {
195 template <typename Sequence, typename Func>
196 static void impl(Sequence&& range, Func& func) {
197 auto first = adl::adl_begin(range);
198 auto last = adl::adl_end(range);
199 for (auto index = std::size_t{0}; first != last; ++index) {
200 auto next = std::next(first);
201 if (loop_break == func(*first, index, first)) {
210 * Implementations for the runtime function
215 EnableIfAcceptsThreeArguments<Sequence, Func>* = nullptr>
216 void for_each_range_impl(Sequence&& range, Func& func) {
217 ForEachRange<Sequence, Func>::impl(std::forward<Sequence>(range), func);
222 EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
223 void for_each_range_impl(Sequence&& range, Func& func) {
224 // make a three arg adaptor for the function passed in so that the main
225 // implementation function can be used
226 auto three_arg_adaptor = [&func](
227 auto&& ele, auto index, auto) -> decltype(auto) {
228 return func(std::forward<decltype(ele)>(ele), index);
230 for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
236 EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
237 void for_each_range_impl(Sequence&& range, Func& func) {
238 // make a three argument adaptor for the function passed in that just ignores
239 // the second and third argument
240 auto three_arg_adaptor = [&func](auto&& ele, auto, auto) -> decltype(auto) {
241 return func(std::forward<decltype(ele)>(ele));
243 for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
247 * Handlers for iteration
250 * The class provides a way to tell whether the function passed in to the
251 * algorithm returns an instance of LoopControl, if it does then the break-able
252 * implementation will be used. If the function provided to the algorithm
253 * does not use the break API, then the basic no break, 0 overhead
254 * implementation will be used
256 template <typename Seq, typename F, typename = void>
257 struct ForEachTupleImpl {
258 template <typename Sequence, typename Func, std::size_t... Indices>
260 impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
261 // unroll the loop in an initializer list construction parameter expansion
263 static_cast<void>(std::initializer_list<int>{
265 Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
266 std::integral_constant<std::size_t, Indices>{}),
270 template <typename Seq, typename F>
271 struct ForEachTupleImpl<Seq, F, EnableIfBreaksTuple<Seq, F>> {
272 template <typename Sequence, typename Func, std::size_t... Indices>
274 impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
275 // unroll the loop in an initializer list construction parameter expansion
277 LoopControl break_or_not = LoopControl::CONTINUE;
279 // cast to void to ignore the result, use the initialzer list constructor
280 // to do the loop execution, the ternary conditional will decide whether
281 // or not to evaluate the result
282 static_cast<void>(std::initializer_list<int>{
283 (((break_or_not == loop_continue)
284 ? (break_or_not = func(
285 Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
286 std::integral_constant<std::size_t, Indices>{}))
293 * The two top level compile time loop iteration functions handle the dispatch
294 * based on the number of arguments the passed in function can be passed, if 2
295 * arguments can be passed then the implementation dispatches work further to
296 * the implementation classes above. If not then an adaptor is constructed
297 * which is passed on to the 2 argument specialization, which then in turn
298 * forwards implementation to the implementation classes above
303 EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
304 void for_each_tuple_impl(Sequence&& seq, Func& func) {
305 // pass the length as an index sequence to the implementation as an
306 // optimization over manual template "tail recursion" unrolling
307 constexpr auto length =
308 std::tuple_size<typename std::decay<Sequence>::type>::value;
309 ForEachTupleImpl<Sequence, Func>::impl(
310 std::forward<Sequence>(seq), func, std::make_index_sequence<length>{});
315 EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
316 void for_each_tuple_impl(Sequence&& seq, Func& func) {
317 // make an adaptor for the function passed in, in case it can only be passed
319 auto two_arg_adaptor = [&func](auto&& ele, auto) -> decltype(auto) {
320 return func(std::forward<decltype(ele)>(ele));
322 for_each_tuple_impl(std::forward<Sequence>(seq), two_arg_adaptor);
326 * Top level handlers for the for_each loop, the basic specialization handles
327 * ranges and the specialized version handles compile time ranges (tuple like)
329 * This implies that if a range is a compile time range, its compile time
330 * get<> API (whether through a member function or through a ADL looked up
331 * method) will be used in preference over iterators
333 template <typename R, typename = void>
335 template <typename Sequence, typename Func>
336 static void impl(Sequence&& range, Func& func) {
337 for_each_tuple_impl(std::forward<Sequence>(range), func);
340 template <typename R>
341 struct ForEachImpl<R, EnableIfRange<R>> {
342 template <typename Sequence, typename Func>
343 static void impl(Sequence&& range, Func& func) {
344 for_each_range_impl(std::forward<Sequence>(range), func);
348 template <typename S, typename I, typename = void>
349 struct FetchIteratorIndexImpl {
350 template <typename Sequence, typename Index>
351 static decltype(auto) impl(Sequence&& sequence, Index&& index) {
352 return std::forward<Sequence>(sequence)[std::forward<Index>(index)];
355 template <typename S, typename I>
356 struct FetchIteratorIndexImpl<S, I, EnableIfRandomAccessIterators<S>> {
357 template <typename Sequence, typename Index>
358 static decltype(auto) impl(Sequence&& sequence, Index index) {
359 return *(adl::adl_begin(std::forward<Sequence>(sequence)) + index);
362 template <typename S, typename = void>
364 template <typename Sequence, typename Index>
365 static decltype(auto) impl(Sequence&& sequence, Index index) {
366 return Get<static_cast<std::size_t>(index), Sequence>::impl(
367 std::forward<Sequence>(sequence));
370 template <typename S>
371 struct FetchImpl<S, EnableIfRange<S>> {
372 template <typename Sequence, typename Index>
373 static decltype(auto) impl(Sequence&& sequence, Index&& index) {
374 return FetchIteratorIndexImpl<Sequence, Index>::impl(
375 std::forward<Sequence>(sequence), std::forward<Index>(index));
379 } // namespace for_each_detail
381 template <typename Sequence, typename Func>
382 FOLLY_CPP14_CONSTEXPR Func for_each(Sequence&& range, Func func) {
383 for_each_detail::ForEachImpl<typename std::decay<Sequence>::type>::impl(
384 std::forward<Sequence>(range), func);
388 template <typename Sequence, typename Index>
389 FOLLY_CPP14_CONSTEXPR decltype(auto) fetch(Sequence&& sequence, Index&& index) {
390 return for_each_detail::FetchImpl<Sequence>::impl(
391 std::forward<Sequence>(sequence), std::forward<Index>(index));