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 | |
30 | namespace folly { |
31 | |
32 | namespace for_each_detail { |
33 | |
34 | namespace adl { |
35 | |
36 | /* using override */ |
37 | using std::begin; |
38 | /* using override */ |
39 | using std::end; |
40 | /* using override */ |
41 | using 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 | */ |
49 | template <std::size_t Index, typename Type> |
50 | auto adl_get(Type&& instance) -> decltype(get<Index>(std::declval<Type>())) { |
51 | return get<Index>(std::forward<Type>(instance)); |
52 | } |
53 | template <typename Type> |
54 | auto adl_begin(Type&& instance) -> decltype(begin(instance)) { |
55 | return begin(instance); |
56 | } |
57 | template <typename Type> |
58 | auto 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 | */ |
67 | template <typename T> |
68 | using EnableIfMemberGetFound = |
69 | void_t<decltype(std::declval<T>().template get<0>())>; |
70 | template <typename, typename T> |
71 | struct IsMemberGetFound : std::false_type {}; |
72 | template <typename T> |
73 | struct 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 | */ |
80 | template < |
81 | std::size_t Index, |
82 | typename Type, |
83 | std::enable_if_t<!IsMemberGetFound<void, Type>::value, int> = 0> |
84 | auto 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 | } |
88 | template < |
89 | std::size_t Index, |
90 | typename Type, |
91 | std::enable_if_t<IsMemberGetFound<void, Type>::value, int> = 0> |
92 | auto 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 | */ |
100 | template <typename Type, typename T = typename std::decay<Type>::type> |
101 | using EnableIfTuple = void_t< |
102 | decltype(get_impl<0>(std::declval<T>())), |
103 | decltype(std::tuple_size<T>::value)>; |
104 | template <typename, typename T> |
105 | struct IsTuple : std::false_type {}; |
106 | template <typename T> |
107 | struct IsTuple<EnableIfTuple<T>, T> : std::true_type {}; |
108 | |
109 | /** |
110 | * Check if the sequence is a range |
111 | */ |
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>()))>; |
116 | template <typename, typename T> |
117 | struct IsRange : std::false_type {}; |
118 | template <typename T> |
119 | struct IsRange<EnableIfRange<T>, T> : std::true_type {}; |
120 | |
121 | struct TupleTag {}; |
122 | struct RangeTag {}; |
123 | |
124 | /** |
125 | * Should ideally check if it is a tuple and if not return void, but msvc fails |
126 | */ |
127 | template <typename Sequence> |
128 | using SequenceTag = |
129 | std::conditional_t<IsRange<void, Sequence>::value, RangeTag, TupleTag>; |
130 | |
131 | struct BeginAddTag {}; |
132 | struct IndexingTag {}; |
133 | |
134 | template <typename Func, typename Item, typename Iter> |
135 | using 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 | |
146 | template < |
147 | typename Func, |
148 | typename... Args, |
149 | std::enable_if_t<is_invocable_r<LoopControl, Func, Args...>::value, int> = |
150 | 0> |
151 | LoopControl invoke_returning_loop_control(Func&& f, Args&&... a) { |
152 | return static_cast<Func&&>(f)(static_cast<Args&&>(a)...); |
153 | } |
154 | template < |
155 | typename Func, |
156 | typename... Args, |
157 | std::enable_if_t<!is_invocable_r<LoopControl, Func, Args...>::value, int> = |
158 | 0> |
159 | LoopControl 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 | */ |
169 | template <typename Sequence, typename Func> |
170 | void 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 | } |
182 | template <typename Sequence, typename Func> |
183 | void 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 | |
194 | template <typename Sequence, typename Func> |
195 | void 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 | */ |
208 | template <typename Sequence, typename Func, std::size_t... Indices> |
209 | void 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 | */ |
243 | template <typename Sequence, typename Func> |
244 | void 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 | } |
251 | template <typename Sequence, typename Func> |
252 | void 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 | */ |
269 | template <typename Sequence, typename Func> |
270 | static 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 | } |
276 | template <typename Sequence, typename Func> |
277 | static 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 | |
285 | template <typename Sequence, typename Index> |
286 | decltype(auto) fetch_impl(IndexingTag, Sequence&& sequence, Index&& index) { |
287 | return std::forward<Sequence>(sequence)[std::forward<Index>(index)]; |
288 | } |
289 | template <typename Sequence, typename Index> |
290 | decltype(auto) fetch_impl(BeginAddTag, Sequence&& sequence, Index index) { |
291 | return *(adl::adl_begin(std::forward<Sequence>(sequence)) + index); |
292 | } |
293 | |
294 | template <typename Sequence, typename Index> |
295 | decltype(auto) fetch_impl(TupleTag, Sequence&& sequence, Index index) { |
296 | return get_impl<index>(std::forward<Sequence>(sequence)); |
297 | } |
298 | template <typename Sequence, typename Index> |
299 | decltype(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 | |
313 | template <typename Sequence, typename Func> |
314 | FOLLY_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 | |
321 | template <typename Sequence, typename Index> |
322 | FOLLY_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 | |