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 | #pragma once |
18 | |
19 | #include <cstddef> |
20 | #include <utility> |
21 | |
22 | #include <folly/Traits.h> |
23 | #include <folly/Utility.h> |
24 | |
25 | /** |
26 | * \file TypeList.h |
27 | * \author Eric Niebler |
28 | * |
29 | * The file contains facilities for manipulating lists of types, and for |
30 | * defining and composing operations over types. |
31 | * |
32 | * The type-operations behave like compile-time functions: they accept types as |
33 | * input and produce types as output. A simple example is a template alias, like |
34 | * `std::add_pointer_t`. However, templates are not themselves first class |
35 | * citizens of the language; they cannot be easily "returned" from a |
36 | * metafunction, and passing them to a metafunction is awkward and often |
37 | * requires the user to help the C++ parser by adding hints like `typename` |
38 | * and `template` to disambiguate the syntax. That makes higher-ordered |
39 | * metaprogramming difficult. (There is no simple way to e.g., compose two |
40 | * template aliases and pass the result as an argument to another template.) |
41 | * |
42 | * Instead, we wrap template aliases in a ordinary class, which _can_ be passed |
43 | * and returned simply from metafunctions. This is like Boost.MPL's notion of a |
44 | * "metafunction class"[1], and we adopt that terminology here. |
45 | * |
46 | * For the Folly.TypeList library, a metafunction class is a protocol that |
47 | * all the components of Folly.TypeList expect and agree upon. It is a class |
48 | * type that has a nested template alias called `Apply`. So for instance, |
49 | * `std::add_pointer_t` as a Folly metafunction class would look like this: |
50 | * |
51 | * struct AddPointer { |
52 | * template <class T> |
53 | * using apply = T*; |
54 | * }; |
55 | * |
56 | * Folly.TypeList gives a simple way to "lift" an ordinary template alias into |
57 | * a metafunction class: `MetaQuote`. The above `AddPointer` could instead be |
58 | * written as: |
59 | * |
60 | * using AddPointer = folly::MetaQuote<std::add_pointer_t>; |
61 | * |
62 | * \par Naming |
63 | * |
64 | * A word about naming. Components in Folly.TypeList fall into two buckets: |
65 | * utilities for manipulating lists of types, and utilities for manipulating |
66 | * metafunction classes. The former have names that start with `Type`, as in |
67 | * `TypeList` and `TypeTransform`. The latter have names that start with `Meta`, |
68 | * as in `MetaQuote` and `MetaApply`. |
69 | * |
70 | * [1] Boost.MPL Metafunction Class: |
71 | * http://www.boost.org/libs/mpl/doc/refmanual/metafunction-class.html |
72 | */ |
73 | |
74 | namespace folly { |
75 | namespace detail { |
76 | |
77 | /** |
78 | * Handy shortcuts for some standard facilities |
79 | */ |
80 | template <bool B> |
81 | using Bool = bool_constant<B>; |
82 | using True = std::true_type; |
83 | using False = std::false_type; |
84 | |
85 | /** |
86 | * Given a metafunction class `Fn` and arguments `Ts...`, invoke `Fn` |
87 | * with `Ts...`. |
88 | */ |
89 | template <class Fn, class... Ts> |
90 | using MetaApply = typename Fn::template apply<Ts...>; |
91 | |
92 | /** |
93 | * A list of types. |
94 | */ |
95 | template <class... Ts> |
96 | struct TypeList { |
97 | /** |
98 | * An alias for this list of types |
99 | */ |
100 | using type = TypeList; |
101 | |
102 | /** |
103 | * \return the number of types in this list. |
104 | */ |
105 | static constexpr std::size_t size() noexcept { |
106 | return sizeof...(Ts); |
107 | } |
108 | |
109 | /** |
110 | * This list of types is also a metafunction class that accepts another |
111 | * metafunction class and invokes it with all the types in the list. |
112 | */ |
113 | template <class Fn> |
114 | using apply = MetaApply<Fn, Ts...>; |
115 | }; |
116 | |
117 | /** |
118 | * A wrapper for a type |
119 | */ |
120 | template <class T> |
121 | struct Type { |
122 | /** |
123 | * An alias for the wrapped type |
124 | */ |
125 | using type = T; |
126 | |
127 | /** |
128 | * This wrapper is a metafunction class that, when applied with any number |
129 | * of arguments, returns the wrapped type. |
130 | */ |
131 | template <class...> |
132 | using apply = T; |
133 | }; |
134 | |
135 | /** |
136 | * An empty struct. |
137 | */ |
138 | struct Empty {}; |
139 | |
140 | /// \cond |
141 | namespace impl { |
142 | template <bool B> |
143 | struct If_ { |
144 | template <class T, class U> |
145 | using apply = T; |
146 | }; |
147 | template <> |
148 | struct If_<false> { |
149 | template <class T, class U> |
150 | using apply = U; |
151 | }; |
152 | } // namespace impl |
153 | /// \endcond |
154 | |
155 | /** |
156 | * Like std::conditional, but with fewer template instantiations |
157 | */ |
158 | template <bool If_, class Then, class Else> |
159 | using If = MetaApply<impl::If_<If_>, Then, Else>; |
160 | |
161 | /** |
162 | * Defers the evaluation of an alias. |
163 | * |
164 | * Given a template `C` and arguments `Ts...`, then |
165 | * - If `C<Ts...>` is well-formed, `MetaApply<MetaDefer<C, Ts...>>` is well- |
166 | * formed and is an alias for `C<Ts...>`. |
167 | * - Otherwise, `MetaApply<MetaDefer<C, Ts...>>` is ill-formed. |
168 | */ |
169 | template <template <class...> class C, class... Ts> |
170 | class MetaDefer { |
171 | template <template <class...> class D = C, class = D<Ts...>> |
172 | static char (&try_(int))[1]; |
173 | static char (&try_(long))[2]; |
174 | struct Result { |
175 | using type = C<Ts...>; |
176 | }; |
177 | |
178 | public: |
179 | template <class... Us> |
180 | using apply = _t<If<sizeof(try_(0)) - 1 || sizeof...(Us), Empty, Result>>; |
181 | }; |
182 | |
183 | /** |
184 | * Compose two metafunction classes into one by chaining. |
185 | * |
186 | * `MetaApply<MetaCompose<P, Q>, Ts...>` is equivalent to |
187 | * `MetaApply<P, MetaApply<Q, Ts...>>`. |
188 | */ |
189 | template <class P, class Q> |
190 | struct MetaCompose { |
191 | template <class... Ts> |
192 | using apply = MetaApply<P, MetaApply<Q, Ts...>>; |
193 | }; |
194 | |
195 | /** |
196 | * A metafunction class that always returns its argument unmodified. |
197 | * |
198 | * `MetaApply<MetaIdentity, int>` is equivalent to `int`. |
199 | */ |
200 | struct MetaIdentity { |
201 | template <class T> |
202 | using apply = T; |
203 | }; |
204 | |
205 | /** |
206 | * Lifts a class template or an alias template to be a metafunction class. |
207 | * |
208 | * `MetaApply<MetaQuote<C>, Ts...>` is equivalent to `C<Ts...>`. |
209 | */ |
210 | template <template <class...> class C> |
211 | struct MetaQuote { |
212 | template <class... Ts> |
213 | using apply = MetaApply<MetaDefer<C, Ts...>>; |
214 | }; |
215 | |
216 | /// \cond |
217 | // Specialization for TypeList since it doesn't need to go through MetaDefer |
218 | template <> |
219 | struct MetaQuote<TypeList> { |
220 | template <class... Ts> |
221 | using apply = TypeList<Ts...>; |
222 | }; |
223 | /// \endcond |
224 | |
225 | /** |
226 | * Lifts a trait class template to be a metafunction class. |
227 | * |
228 | * `MetaApply<MetaQuoteTrait<C>, Ts...>` is equivalent to |
229 | * `typename C<Ts...>::type`. |
230 | */ |
231 | template <template <class...> class C> |
232 | using MetaQuoteTrait = MetaCompose<MetaQuote<_t>, MetaQuote<C>>; |
233 | |
234 | /** |
235 | * Partially evaluate the metafunction class `Fn` by binding the arguments |
236 | * `Ts...` to the front of the argument list. |
237 | * |
238 | * `MetaApply<MetaBindFront<Fn, Ts...>, Us...>` is equivalent to |
239 | * `MetaApply<Fn, Ts..., Us...>`. |
240 | */ |
241 | template <class Fn, class... Ts> |
242 | struct MetaBindFront { |
243 | template <class... Us> |
244 | using apply = MetaApply<Fn, Ts..., Us...>; |
245 | }; |
246 | |
247 | /** |
248 | * Partially evaluate the metafunction class `Fn` by binding the arguments |
249 | * `Ts...` to the back of the argument list. |
250 | * |
251 | * `MetaApply<MetaBindBack<Fn, Ts...>, Us...>` is equivalent to |
252 | * `MetaApply<Fn, Us..., Ts...>`. |
253 | */ |
254 | template <class Fn, class... Ts> |
255 | struct MetaBindBack { |
256 | template <class... Us> |
257 | using apply = MetaApply<Fn, Us..., Ts...>; |
258 | }; |
259 | |
260 | /** |
261 | * Given a metafunction class `Fn` that expects a single `TypeList` argument, |
262 | * turn it into a metafunction class that takes `N` arguments, wraps them in |
263 | * a `TypeList`, and calls `Fn` with it. |
264 | * |
265 | * `MetaApply<MetaCurry<Fn>, Ts...>` is equivalent to |
266 | * `MetaApply<Fn, TypeList<Ts...>>`. |
267 | */ |
268 | template <class Fn> |
269 | using MetaCurry = MetaCompose<Fn, MetaQuote<TypeList>>; |
270 | |
271 | /** |
272 | * Given a metafunction class `Fn` that expects `N` arguments, |
273 | * turn it into a metafunction class that takes a single `TypeList` arguments |
274 | * and calls `Fn` with the types in the `TypeList`. |
275 | * |
276 | * `MetaApply<MetaUncurry<Fn>, TypeList<Ts...>>` is equivalent to |
277 | * `MetaApply<Fn, Ts...>`. |
278 | */ |
279 | template <class Fn> |
280 | using MetaUncurry = MetaBindBack<MetaQuote<MetaApply>, Fn>; |
281 | |
282 | /** |
283 | * Given a `TypeList` and some arguments, append those arguments to the end of |
284 | * the `TypeList`. |
285 | * |
286 | * `TypePushBack<TypeList<Ts...>, Us...>` is equivalent to |
287 | * `TypeList<Ts..., Us...>`. |
288 | */ |
289 | template <class List, class... Ts> |
290 | using TypePushBack = MetaApply<List, MetaBindBack<MetaQuote<TypeList>, Ts...>>; |
291 | |
292 | /** |
293 | * Given a `TypeList` and some arguments, prepend those arguments to the start |
294 | * of the `TypeList`. |
295 | * |
296 | * `TypePushFront<TypeList<Ts...>, Us...>` is equivalent to |
297 | * `TypeList<Us..., Ts...>`. |
298 | */ |
299 | template <class List, class... Ts> |
300 | using TypePushFront = |
301 | MetaApply<List, MetaBindFront<MetaQuote<TypeList>, Ts...>>; |
302 | |
303 | /** |
304 | * Given a metafunction class `Fn` and a `TypeList`, call `Fn` with the types |
305 | * in the `TypeList`. |
306 | */ |
307 | template <class Fn, class List> |
308 | using MetaUnpack = MetaApply<List, Fn>; |
309 | |
310 | /// \cond |
311 | namespace impl { |
312 | template <class Fn> |
313 | struct TypeTransform_ { |
314 | template <class... Ts> |
315 | using apply = TypeList<MetaApply<Fn, Ts>...>; |
316 | }; |
317 | } // namespace impl |
318 | /// \endcond |
319 | |
320 | /** |
321 | * Transform all the elements in a `TypeList` with the metafunction class `Fn`. |
322 | * |
323 | * `TypeTransform<TypeList<Ts..>, Fn>` is equivalent to |
324 | * `TypeList<MetaApply<Fn, Ts>...>`. |
325 | */ |
326 | template <class List, class Fn> |
327 | using TypeTransform = MetaApply<List, impl::TypeTransform_<Fn>>; |
328 | |
329 | /** |
330 | * Given a binary metafunction class, convert it to another binary metafunction |
331 | * class with the argument order reversed. |
332 | */ |
333 | template <class Fn> |
334 | struct MetaFlip { |
335 | template <class A, class B> |
336 | using apply = MetaApply<Fn, B, A>; |
337 | }; |
338 | |
339 | /// \cond |
340 | namespace impl { |
341 | template <class Fn> |
342 | struct FoldR_ { |
343 | template <class... Ts> |
344 | struct Lambda : MetaIdentity {}; |
345 | template <class A, class... Ts> |
346 | struct Lambda<A, Ts...> { |
347 | template <class State> |
348 | using apply = MetaApply<Fn, A, MetaApply<Lambda<Ts...>, State>>; |
349 | }; |
350 | template <class A, class B, class C, class D, class... Ts> |
351 | struct Lambda<A, B, C, D, Ts...> { // manually unroll 4 elements |
352 | template <class State> |
353 | using apply = MetaApply< |
354 | Fn, |
355 | A, |
356 | MetaApply< |
357 | Fn, |
358 | B, |
359 | MetaApply< |
360 | Fn, |
361 | C, |
362 | MetaApply<Fn, D, MetaApply<Lambda<Ts...>, State>>>>>; |
363 | }; |
364 | template <class... Ts> |
365 | using apply = Lambda<Ts...>; |
366 | }; |
367 | } // namespace impl |
368 | /// \endcond |
369 | |
370 | /** |
371 | * Given a `TypeList`, an initial state, and a binary function, reduce the |
372 | * `TypeList` by applying the function to each element and the current state, |
373 | * producing a new state to be used with the next element. This is a "right" |
374 | * fold in functional parlance. |
375 | * |
376 | * `TypeFold<TypeList<A, B, C>, X, Fn>` is equivalent to |
377 | * `MetaApply<Fn, A, MetaApply<Fn, B, MetaApply<Fn, C, X>>>`. |
378 | */ |
379 | template <class List, class State, class Fn> |
380 | using TypeFold = MetaApply<MetaApply<List, impl::FoldR_<Fn>>, State>; |
381 | |
382 | /// \cond |
383 | namespace impl { |
384 | template <class Fn> |
385 | struct FoldL_ { |
386 | template <class... Ts> |
387 | struct Lambda : MetaIdentity {}; |
388 | template <class A, class... Ts> |
389 | struct Lambda<A, Ts...> { |
390 | template <class State> |
391 | using apply = MetaApply<Lambda<Ts...>, MetaApply<Fn, State, A>>; |
392 | }; |
393 | template <class A, class B, class C, class D, class... Ts> |
394 | struct Lambda<A, B, C, D, Ts...> { // manually unroll 4 elements |
395 | template <class State> |
396 | using apply = MetaApply< |
397 | Lambda<Ts...>, |
398 | MetaApply< |
399 | Fn, |
400 | MetaApply<Fn, MetaApply<Fn, MetaApply<Fn, State, A>, B>, C>, |
401 | D>>; |
402 | }; |
403 | template <class... Ts> |
404 | using apply = Lambda<Ts...>; |
405 | }; |
406 | } // namespace impl |
407 | /// \endcond |
408 | |
409 | /** |
410 | * Given a `TypeList`, an initial state, and a binary function, reduce the |
411 | * `TypeList` by applying the function to each element and the current state, |
412 | * producing a new state to be used with the next element. This is a "left" |
413 | * fold, in functional parlance. |
414 | * |
415 | * `TypeReverseFold<TypeList<A, B, C>, X, Fn>` is equivalent to |
416 | * `MetaApply<Fn, MetaApply<Fn, MetaApply<Fn, X, C>, B, A>`. |
417 | */ |
418 | template <class List, class State, class Fn> |
419 | using TypeReverseFold = MetaApply<MetaApply<List, impl::FoldL_<Fn>>, State>; |
420 | |
421 | namespace impl { |
422 | template <class List> |
423 | struct Inherit_; |
424 | template <class... Ts> |
425 | struct Inherit_<TypeList<Ts...>> : Ts... { |
426 | using type = Inherit_; |
427 | }; |
428 | } // namespace impl |
429 | |
430 | /** |
431 | * Given a `TypeList`, create a type that inherits from all the types in the |
432 | * list. |
433 | * |
434 | * Requires: all of the types in the list are non-final class types, and the |
435 | * types are all unique. |
436 | */ |
437 | template <class List> |
438 | using Inherit = impl::Inherit_<List>; |
439 | |
440 | /// \cond |
441 | namespace impl { |
442 | // Avoid instantiating std::is_base_of when we have an intrinsic. |
443 | #if defined(__GNUC__) || defined(_MSC_VER) |
444 | template <class T, class... Set> |
445 | using In_ = Bool<__is_base_of(Type<T>, Inherit<TypeList<Type<Set>...>>)>; |
446 | #else |
447 | template <class T, class... Set> |
448 | using In_ = std::is_base_of<Type<T>, Inherit<TypeList<Type<Set>...>>>; |
449 | #endif |
450 | |
451 | template <class T> |
452 | struct InsertFront_ { |
453 | template <class... Set> |
454 | using apply = |
455 | If<In_<T, Set...>::value, TypeList<Set...>, TypeList<T, Set...>>; |
456 | }; |
457 | |
458 | struct Unique_ { |
459 | template <class T, class List> |
460 | using apply = MetaApply<List, impl::InsertFront_<T>>; |
461 | }; |
462 | } // namespace impl |
463 | /// \endcond |
464 | |
465 | /** |
466 | * Given a `TypeList`, produce a new list of types removing duplicates, keeping |
467 | * the first seen element. |
468 | * |
469 | * `TypeUnique<TypeList<int, short, int>>` is equivalent to |
470 | * `TypeList<int, short>`. |
471 | * |
472 | * \note This algorithm is O(N^2). |
473 | */ |
474 | template <class List> |
475 | using TypeUnique = TypeFold<List, TypeList<>, impl::Unique_>; |
476 | |
477 | /** |
478 | * Given a `TypeList`, produce a new list of types removing duplicates, keeping |
479 | * the last seen element. |
480 | * |
481 | * `TypeUnique<TypeList<int, short, int>>` is equivalent to |
482 | * `TypeList<short, int>`. |
483 | * |
484 | * \note This algorithm is O(N^2). |
485 | */ |
486 | template <class List> |
487 | using TypeReverseUnique = |
488 | TypeReverseFold<List, TypeList<>, MetaFlip<impl::Unique_>>; |
489 | |
490 | /// \cond |
491 | namespace impl { |
492 | template <class T> |
493 | struct AsTypeList_ {}; |
494 | template <template <class...> class T, class... Ts> |
495 | struct AsTypeList_<T<Ts...>> { |
496 | using type = TypeList<Ts...>; |
497 | }; |
498 | template <class T, T... Is> |
499 | struct AsTypeList_<folly::integer_sequence<T, Is...>> { |
500 | using type = TypeList<std::integral_constant<T, Is>...>; |
501 | }; |
502 | } // namespace impl |
503 | /// \endcond |
504 | |
505 | /** |
506 | * Convert a type to a list of types. Given a type `T`: |
507 | * - If `T` is of the form `C<Ts...>`, where `C` is a class template and |
508 | * `Ts...` is a list of types, the result is `TypeList<Ts...>`. |
509 | * - Else, if `T` is of the form `std::integer_sequence<T, Is...>`, then |
510 | * the result is `TypeList<std::integral_constant<T, Is>...>`. |
511 | * - Otherwise, `asTypeList<T>` is ill-formed. |
512 | */ |
513 | template <class T> |
514 | using AsTypeList = _t<impl::AsTypeList_<T>>; |
515 | |
516 | /// \cond |
517 | namespace impl { |
518 | // TODO For a list of N lists, this algorithm is O(N). It does no unrolling. |
519 | struct Join_ { |
520 | template <class Fn> |
521 | struct Lambda { |
522 | template <class... Ts> |
523 | using apply = MetaBindBack<Fn, Ts...>; |
524 | }; |
525 | template <class List, class Fn> |
526 | using apply = MetaApply<List, Lambda<Fn>>; |
527 | }; |
528 | } // namespace impl |
529 | /// \endcond |
530 | |
531 | /** |
532 | * Given a `TypeList` of `TypeList`s, flatten the lists into a single list. |
533 | * |
534 | * `TypeJoin<TypeList<TypeList<As...>, TypeList<Bs...>>>` is equivalent to |
535 | * `TypeList<As..., Bs...>` |
536 | */ |
537 | template <class List> |
538 | using TypeJoin = MetaApply<TypeFold<List, MetaQuote<TypeList>, impl::Join_>>; |
539 | |
540 | /** |
541 | * Given several `TypeList`s, flatten the lists into a single list. |
542 | * |
543 | * \note This is just the curried form of `TypeJoin`. (See `MetaCurry`.) |
544 | * |
545 | * `TypeConcat<TypeList<As...>, TypeList<Bs...>>` is equivalent to |
546 | * `TypeList<As..., Bs...>` |
547 | */ |
548 | template <class... Ts> |
549 | using TypeConcat = TypeJoin<TypeList<Ts...>>; |
550 | } // namespace detail |
551 | } // namespace folly |
552 | |