1/*
2 * Copyright 2017-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#include <cassert>
18#include <cstdint>
19#include <initializer_list>
20#include <iterator>
21#include <tuple>
22#include <type_traits>
23#include <utility>
24
25#include <folly/Portability.h>
26#include <folly/Traits.h>
27#include <folly/Utility.h>
28#include <folly/functional/Invoke.h>
29
30namespace folly {
31
32namespace for_each_detail {
33
34namespace adl {
35
36/* using override */
37using std::begin;
38/* using override */
39using std::end;
40/* using override */
41using std::get;
42
43/**
44 * The adl_ functions below lookup the function name in the namespace of the
45 * type of the object being passed into the function. If no function with that
46 * name exists for the passed object then the default std:: versions are going
47 * to be called
48 */
49template <std::size_t Index, typename Type>
50auto adl_get(Type&& instance) -> decltype(get<Index>(std::declval<Type>())) {
51 return get<Index>(std::forward<Type>(instance));
52}
53template <typename Type>
54auto adl_begin(Type&& instance) -> decltype(begin(instance)) {
55 return begin(instance);
56}
57template <typename Type>
58auto adl_end(Type&& instance) -> decltype(end(instance)) {
59 return end(instance);
60}
61
62} // namespace adl
63
64/**
65 * Enable if the tuple supports fetching via a member get<>()
66 */
67template <typename T>
68using EnableIfMemberGetFound =
69 void_t<decltype(std::declval<T>().template get<0>())>;
70template <typename, typename T>
71struct IsMemberGetFound : std::false_type {};
72template <typename T>
73struct IsMemberGetFound<EnableIfMemberGetFound<T>, T> : std::true_type {};
74
75/**
76 * A get that tries member get<> first and if that is not found tries ADL get<>.
77 * This mechanism is as found in the structured bindings proposal here 11.5.3.
78 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf
79 */
80template <
81 std::size_t Index,
82 typename Type,
83 std::enable_if_t<!IsMemberGetFound<void, Type>::value, int> = 0>
84auto get_impl(Type&& instance)
85 -> decltype(adl::adl_get<Index>(static_cast<Type&&>(instance))) {
86 return adl::adl_get<Index>(static_cast<Type&&>(instance));
87}
88template <
89 std::size_t Index,
90 typename Type,
91 std::enable_if_t<IsMemberGetFound<void, Type>::value, int> = 0>
92auto get_impl(Type&& instance)
93 -> decltype(static_cast<Type&&>(instance).template get<Index>()) {
94 return static_cast<Type&&>(instance).template get<Index>();
95}
96
97/**
98 * Check if the sequence is a tuple
99 */
100template <typename Type, typename T = typename std::decay<Type>::type>
101using EnableIfTuple = void_t<
102 decltype(get_impl<0>(std::declval<T>())),
103 decltype(std::tuple_size<T>::value)>;
104template <typename, typename T>
105struct IsTuple : std::false_type {};
106template <typename T>
107struct IsTuple<EnableIfTuple<T>, T> : std::true_type {};
108
109/**
110 * Check if the sequence is a range
111 */
112template <typename Type, typename T = typename std::decay<Type>::type>
113using EnableIfRange = void_t<
114 decltype(adl::adl_begin(std::declval<T>())),
115 decltype(adl::adl_end(std::declval<T>()))>;
116template <typename, typename T>
117struct IsRange : std::false_type {};
118template <typename T>
119struct IsRange<EnableIfRange<T>, T> : std::true_type {};
120
121struct TupleTag {};
122struct RangeTag {};
123
124/**
125 * Should ideally check if it is a tuple and if not return void, but msvc fails
126 */
127template <typename Sequence>
128using SequenceTag =
129 std::conditional_t<IsRange<void, Sequence>::value, RangeTag, TupleTag>;
130
131struct BeginAddTag {};
132struct IndexingTag {};
133
134template <typename Func, typename Item, typename Iter>
135using ForEachImplTag = std::conditional_t<
136 is_invocable<Func, Item, index_constant<0>, Iter>::value,
137 index_constant<3>,
138 std::conditional_t<
139 is_invocable<Func, Item, index_constant<0>>::value,
140 index_constant<2>,
141 std::conditional_t<
142 is_invocable<Func, Item>::value,
143 index_constant<1>,
144 void>>>;
145
146template <
147 typename Func,
148 typename... Args,
149 std::enable_if_t<is_invocable_r<LoopControl, Func, Args...>::value, int> =
150 0>
151LoopControl invoke_returning_loop_control(Func&& f, Args&&... a) {
152 return static_cast<Func&&>(f)(static_cast<Args&&>(a)...);
153}
154template <
155 typename Func,
156 typename... Args,
157 std::enable_if_t<!is_invocable_r<LoopControl, Func, Args...>::value, int> =
158 0>
159LoopControl invoke_returning_loop_control(Func&& f, Args&&... a) {
160 static_assert(
161 std::is_void<invoke_result_t<Func, Args...>>::value,
162 "return either LoopControl or void");
163 return static_cast<Func&&>(f)(static_cast<Args&&>(a)...), loop_continue;
164}
165
166/**
167 * Implementations for the runtime function
168 */
169template <typename Sequence, typename Func>
170void for_each_range_impl(index_constant<3>, Sequence&& range, Func& func) {
171 auto first = adl::adl_begin(range);
172 auto last = adl::adl_end(range);
173 for (auto index = std::size_t{0}; first != last; ++index) {
174 auto next = std::next(first);
175 auto control = invoke_returning_loop_control(func, *first, index, first);
176 if (loop_break == control) {
177 break;
178 }
179 first = next;
180 }
181}
182template <typename Sequence, typename Func>
183void for_each_range_impl(index_constant<2>, Sequence&& range, Func& func) {
184 // make a three arg adaptor for the function passed in so that the main
185 // implementation function can be used
186 auto three_arg_adaptor = [&func](
187 auto&& ele, auto index, auto) -> decltype(auto) {
188 return func(std::forward<decltype(ele)>(ele), index);
189 };
190 for_each_range_impl(
191 index_constant<3>{}, std::forward<Sequence>(range), three_arg_adaptor);
192}
193
194template <typename Sequence, typename Func>
195void for_each_range_impl(index_constant<1>, Sequence&& range, Func& func) {
196 // make a three argument adaptor for the function passed in that just ignores
197 // the second and third argument
198 auto three_arg_adaptor = [&func](auto&& ele, auto, auto) -> decltype(auto) {
199 return func(std::forward<decltype(ele)>(ele));
200 };
201 for_each_range_impl(
202 index_constant<3>{}, std::forward<Sequence>(range), three_arg_adaptor);
203}
204
205/**
206 * Handlers for iteration
207 */
208template <typename Sequence, typename Func, std::size_t... Indices>
209void for_each_tuple_impl(
210 index_sequence<Indices...>,
211 Sequence&& seq,
212 Func& func) {
213 using _ = int[];
214
215 // unroll the loop in an initializer list construction parameter expansion
216 // pack
217 auto control = loop_continue;
218
219 // cast to void to ignore the result; use the int[] initialization to do the
220 // loop execution, the ternary conditional will decide whether or not to
221 // evaluate the result
222 //
223 // if func does not return loop-control, expect the optimizer to see through
224 // invoke_returning_loop_control always returning loop_continue
225 void(
226 _{(((control == loop_continue)
227 ? (control = invoke_returning_loop_control(
228 func,
229 get_impl<Indices>(std::forward<Sequence>(seq)),
230 index_constant<Indices>{}))
231 : (loop_continue)),
232 0)...});
233}
234
235/**
236 * The two top level compile time loop iteration functions handle the dispatch
237 * based on the number of arguments the passed in function can be passed, if 2
238 * arguments can be passed then the implementation dispatches work further to
239 * the implementation classes above. If not then an adaptor is constructed
240 * which is passed on to the 2 argument specialization, which then in turn
241 * forwards implementation to the implementation classes above
242 */
243template <typename Sequence, typename Func>
244void for_each_tuple_impl(index_constant<2>, Sequence&& seq, Func& func) {
245 // pass the length as an index sequence to the implementation as an
246 // optimization over manual template "tail recursion" unrolling
247 using size = std::tuple_size<typename std::decay<Sequence>::type>;
248 for_each_tuple_impl(
249 make_index_sequence<size::value>{}, std::forward<Sequence>(seq), func);
250}
251template <typename Sequence, typename Func>
252void for_each_tuple_impl(index_constant<1>, Sequence&& seq, Func& func) {
253 // make an adaptor for the function passed in, in case it can only be passed
254 // on argument
255 auto two_arg_adaptor = [&func](auto&& ele, auto) -> decltype(auto) {
256 return func(std::forward<decltype(ele)>(ele));
257 };
258 for_each_tuple_impl(
259 index_constant<2>{}, std::forward<Sequence>(seq), two_arg_adaptor);
260}
261
262/**
263 * Top level handlers for the for_each loop, with one overload for tuples and
264 * one overload for ranges
265 *
266 * This implies that if type is both a range and a tuple, it is treated as a
267 * range rather than as a tuple
268 */
269template <typename Sequence, typename Func>
270static void for_each_impl(TupleTag, Sequence&& range, Func& func) {
271 using type = decltype(get_impl<0>(std::declval<Sequence>()));
272 using tag = ForEachImplTag<Func, type, void>;
273 static_assert(!std::is_same<tag, void>::value, "unknown invocability");
274 for_each_tuple_impl(tag{}, std::forward<Sequence>(range), func);
275}
276template <typename Sequence, typename Func>
277static void for_each_impl(RangeTag, Sequence&& range, Func& func) {
278 using iter = decltype(adl::adl_begin(std::declval<Sequence>()));
279 using type = decltype(*std::declval<iter>());
280 using tag = ForEachImplTag<Func, type, iter>;
281 static_assert(!std::is_same<tag, void>::value, "unknown invocability");
282 for_each_range_impl(tag{}, std::forward<Sequence>(range), func);
283}
284
285template <typename Sequence, typename Index>
286decltype(auto) fetch_impl(IndexingTag, Sequence&& sequence, Index&& index) {
287 return std::forward<Sequence>(sequence)[std::forward<Index>(index)];
288}
289template <typename Sequence, typename Index>
290decltype(auto) fetch_impl(BeginAddTag, Sequence&& sequence, Index index) {
291 return *(adl::adl_begin(std::forward<Sequence>(sequence)) + index);
292}
293
294template <typename Sequence, typename Index>
295decltype(auto) fetch_impl(TupleTag, Sequence&& sequence, Index index) {
296 return get_impl<index>(std::forward<Sequence>(sequence));
297}
298template <typename Sequence, typename Index>
299decltype(auto) fetch_impl(RangeTag, Sequence&& sequence, Index&& index) {
300 using iter = decltype(adl::adl_begin(std::declval<Sequence>()));
301 using iter_traits = std::iterator_traits<remove_cvref_t<iter>>;
302 using iter_cat = typename iter_traits::iterator_category;
303 using tag = std::conditional_t<
304 std::is_same<iter_cat, std::random_access_iterator_tag>::value,
305 BeginAddTag,
306 IndexingTag>;
307 return fetch_impl(
308 tag{}, std::forward<Sequence>(sequence), std::forward<Index>(index));
309}
310
311} // namespace for_each_detail
312
313template <typename Sequence, typename Func>
314FOLLY_CPP14_CONSTEXPR Func for_each(Sequence&& sequence, Func func) {
315 namespace fed = for_each_detail;
316 using tag = fed::SequenceTag<Sequence>;
317 fed::for_each_impl(tag{}, std::forward<Sequence>(sequence), func);
318 return func;
319}
320
321template <typename Sequence, typename Index>
322FOLLY_CPP14_CONSTEXPR decltype(auto) fetch(Sequence&& sequence, Index&& index) {
323 namespace fed = for_each_detail;
324 using tag = fed::SequenceTag<Sequence>;
325 return for_each_detail::fetch_impl(
326 tag{}, std::forward<Sequence>(sequence), std::forward<Index>(index));
327}
328
329} // namespace folly
330