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
74namespace folly {
75namespace detail {
76
77/**
78 * Handy shortcuts for some standard facilities
79 */
80template <bool B>
81using Bool = bool_constant<B>;
82using True = std::true_type;
83using False = std::false_type;
84
85/**
86 * Given a metafunction class `Fn` and arguments `Ts...`, invoke `Fn`
87 * with `Ts...`.
88 */
89template <class Fn, class... Ts>
90using MetaApply = typename Fn::template apply<Ts...>;
91
92/**
93 * A list of types.
94 */
95template <class... Ts>
96struct 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 */
120template <class T>
121struct 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 */
138struct Empty {};
139
140/// \cond
141namespace impl {
142template <bool B>
143struct If_ {
144 template <class T, class U>
145 using apply = T;
146};
147template <>
148struct 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 */
158template <bool If_, class Then, class Else>
159using 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 */
169template <template <class...> class C, class... Ts>
170class 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 */
189template <class P, class Q>
190struct 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 */
200struct 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 */
210template <template <class...> class C>
211struct 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
218template <>
219struct 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 */
231template <template <class...> class C>
232using 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 */
241template <class Fn, class... Ts>
242struct 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 */
254template <class Fn, class... Ts>
255struct 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 */
268template <class Fn>
269using 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 */
279template <class Fn>
280using 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 */
289template <class List, class... Ts>
290using 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 */
299template <class List, class... Ts>
300using 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 */
307template <class Fn, class List>
308using MetaUnpack = MetaApply<List, Fn>;
309
310/// \cond
311namespace impl {
312template <class Fn>
313struct 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 */
326template <class List, class Fn>
327using 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 */
333template <class Fn>
334struct MetaFlip {
335 template <class A, class B>
336 using apply = MetaApply<Fn, B, A>;
337};
338
339/// \cond
340namespace impl {
341template <class Fn>
342struct 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 */
379template <class List, class State, class Fn>
380using TypeFold = MetaApply<MetaApply<List, impl::FoldR_<Fn>>, State>;
381
382/// \cond
383namespace impl {
384template <class Fn>
385struct 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 */
418template <class List, class State, class Fn>
419using TypeReverseFold = MetaApply<MetaApply<List, impl::FoldL_<Fn>>, State>;
420
421namespace impl {
422template <class List>
423struct Inherit_;
424template <class... Ts>
425struct 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 */
437template <class List>
438using Inherit = impl::Inherit_<List>;
439
440/// \cond
441namespace impl {
442// Avoid instantiating std::is_base_of when we have an intrinsic.
443#if defined(__GNUC__) || defined(_MSC_VER)
444template <class T, class... Set>
445using In_ = Bool<__is_base_of(Type<T>, Inherit<TypeList<Type<Set>...>>)>;
446#else
447template <class T, class... Set>
448using In_ = std::is_base_of<Type<T>, Inherit<TypeList<Type<Set>...>>>;
449#endif
450
451template <class T>
452struct InsertFront_ {
453 template <class... Set>
454 using apply =
455 If<In_<T, Set...>::value, TypeList<Set...>, TypeList<T, Set...>>;
456};
457
458struct 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 */
474template <class List>
475using 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 */
486template <class List>
487using TypeReverseUnique =
488 TypeReverseFold<List, TypeList<>, MetaFlip<impl::Unique_>>;
489
490/// \cond
491namespace impl {
492template <class T>
493struct AsTypeList_ {};
494template <template <class...> class T, class... Ts>
495struct AsTypeList_<T<Ts...>> {
496 using type = TypeList<Ts...>;
497};
498template <class T, T... Is>
499struct 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 */
513template <class T>
514using AsTypeList = _t<impl::AsTypeList_<T>>;
515
516/// \cond
517namespace impl {
518// TODO For a list of N lists, this algorithm is O(N). It does no unrolling.
519struct 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 */
537template <class List>
538using 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 */
548template <class... Ts>
549using TypeConcat = TypeJoin<TypeList<Ts...>>;
550} // namespace detail
551} // namespace folly
552