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.
22 #include <folly/Traits.h>
23 #include <folly/Utility.h>
27 * \author Eric Niebler
29 * The file contains facilities for manipulating lists of types, and for
30 * defining and composing operations over types.
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.)
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.
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:
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
60 * using AddPointer = folly::MetaQuote<std::add_pointer_t>;
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`.
70 * [1] Boost.MPL Metafunction Class:
71 * http://www.boost.org/libs/mpl/doc/refmanual/metafunction-class.html
78 * Handy shortcuts for some standard facilities
81 using Bool = std::integral_constant<bool, B>;
82 using True = std::true_type;
83 using False = std::false_type;
86 * Given a metafunction class `Fn` and arguments `Ts...`, invoke `Fn`
89 template <class Fn, class... Ts>
90 using MetaApply = typename Fn::template apply<Ts...>;
95 template <class... Ts>
98 * An alias for this list of types
100 using type = TypeList;
103 * \return the number of types in this list.
105 static constexpr std::size_t size() noexcept {
106 return sizeof...(Ts);
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.
114 using apply = MetaApply<Fn, Ts...>;
118 * A wrapper for a type
123 * An alias for the wrapped type
128 * This wrapper is a metafunction class that, when applied with any number
129 * of arguments, returns the wrapped type.
144 template <class T, class U>
149 template <class T, class U>
156 * Like std::conditional, but with fewer template instantiations
158 template <bool If_, class Then, class Else>
159 using If = MetaApply<impl::If_<If_>, Then, Else>;
162 * Defers the evaluation of an alias.
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.
169 template <template <class...> class C, class... Ts>
171 template <template <class...> class D = C, class = D<Ts...>>
172 static char (&try_(int))[1];
173 static char (&try_(long))[2];
175 using type = C<Ts...>;
179 template <class... Us>
180 using apply = _t<If<sizeof(try_(0)) - 1 || sizeof...(Us), Empty, Result>>;
184 * Compose two metafunction classes into one by chaining.
186 * `MetaApply<MetaCompose<P, Q>, Ts...>` is equivalent to
187 * `MetaApply<P, MetaApply<Q, Ts...>>`.
189 template <class P, class Q>
191 template <class... Ts>
192 using apply = MetaApply<P, MetaApply<Q, Ts...>>;
196 * A metafunction class that always returns its argument unmodified.
198 * `MetaApply<MetaIdentity, int>` is equivalent to `int`.
200 struct MetaIdentity {
206 * Lifts a class template or an alias template to be a metafunction class.
208 * `MetaApply<MetaQuote<C>, Ts...>` is equivalent to `C<Ts...>`.
210 template <template <class...> class C>
212 template <class... Ts>
213 using apply = MetaApply<MetaDefer<C, Ts...>>;
217 // Specialization for TypeList since it doesn't need to go through MetaDefer
219 struct MetaQuote<TypeList> {
220 template <class... Ts>
221 using apply = TypeList<Ts...>;
226 * Lifts a trait class template to be a metafunction class.
228 * `MetaApply<MetaQuoteTrait<C>, Ts...>` is equivalent to
229 * `typename C<Ts...>::type`.
231 template <template <class...> class C>
232 using MetaQuoteTrait = MetaCompose<MetaQuote<_t>, MetaQuote<C>>;
235 * Partially evaluate the metafunction class `Fn` by binding the arguments
236 * `Ts...` to the front of the argument list.
238 * `MetaApply<MetaBindFront<Fn, Ts...>, Us...>` is equivalent to
239 * `MetaApply<Fn, Ts..., Us...>`.
241 template <class Fn, class... Ts>
242 struct MetaBindFront {
243 template <class... Us>
244 using apply = MetaApply<Fn, Ts..., Us...>;
248 * Partially evaluate the metafunction class `Fn` by binding the arguments
249 * `Ts...` to the back of the argument list.
251 * `MetaApply<MetaBindBack<Fn, Ts...>, Us...>` is equivalent to
252 * `MetaApply<Fn, Us..., Ts...>`.
254 template <class Fn, class... Ts>
255 struct MetaBindBack {
256 template <class... Us>
257 using apply = MetaApply<Fn, Us..., Ts...>;
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.
265 * `MetaApply<MetaCurry<Fn>, Ts...>` is equivalent to
266 * `MetaApply<Fn, TypeList<Ts...>>`.
269 using MetaCurry = MetaCompose<Fn, MetaQuote<TypeList>>;
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`.
276 * `MetaApply<MetaUncurry<Fn>, TypeList<Ts...>>` is equivalent to
277 * `MetaApply<Fn, Ts...>`.
280 using MetaUncurry = MetaBindBack<MetaQuote<MetaApply>, Fn>;
283 * Given a `TypeList` and some arguments, append those arguments to the end of
286 * `TypePushBack<TypeList<Ts...>, Us...>` is equivalent to
287 * `TypeList<Ts..., Us...>`.
289 template <class List, class... Ts>
290 using TypePushBack = MetaApply<List, MetaBindBack<MetaQuote<TypeList>, Ts...>>;
293 * Given a `TypeList` and some arguments, prepend those arguments to the start
296 * `TypePushFront<TypeList<Ts...>, Us...>` is equivalent to
297 * `TypeList<Us..., Ts...>`.
299 template <class List, class... Ts>
300 using TypePushFront =
301 MetaApply<List, MetaBindFront<MetaQuote<TypeList>, Ts...>>;
304 * Given a metafunction class `Fn` and a `TypeList`, call `Fn` with the types
307 template <class Fn, class List>
308 using MetaUnpack = MetaApply<List, Fn>;
313 struct TypeTransform_ {
314 template <class... Ts>
315 using apply = TypeList<MetaApply<Fn, Ts>...>;
321 * Transform all the elements in a `TypeList` with the metafunction class `Fn`.
323 * `TypeTransform<TypeList<Ts..>, Fn>` is equivalent to
324 * `TypeList<MetaApply<Fn, Ts>...>`.
326 template <class List, class Fn>
327 using TypeTransform = MetaApply<List, impl::TypeTransform_<Fn>>;
330 * Given a binary metafunction class, convert it to another binary metafunction
331 * class with the argument order reversed.
335 template <class A, class B>
336 using apply = MetaApply<Fn, B, A>;
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>>;
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<
362 MetaApply<Fn, D, MetaApply<Lambda<Ts...>, State>>>>>;
364 template <class... Ts>
365 using apply = Lambda<Ts...>;
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.
376 * `TypeFold<TypeList<A, B, C>, X, Fn>` is equivalent to
377 * `MetaApply<Fn, A, MetaApply<Fn, B, MetaApply<Fn, C, X>>>`.
379 template <class List, class State, class Fn>
380 using TypeFold = MetaApply<MetaApply<List, impl::FoldR_<Fn>>, State>;
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>>;
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<
400 MetaApply<Fn, MetaApply<Fn, MetaApply<Fn, State, A>, B>, C>,
403 template <class... Ts>
404 using apply = Lambda<Ts...>;
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.
415 * `TypeReverseFold<TypeList<A, B, C>, X, Fn>` is equivalent to
416 * `MetaApply<Fn, MetaApply<Fn, MetaApply<Fn, X, C>, B, A>`.
418 template <class List, class State, class Fn>
419 using TypeReverseFold = MetaApply<MetaApply<List, impl::FoldL_<Fn>>, State>;
422 template <class List>
424 template <class... Ts>
425 struct Inherit_<TypeList<Ts...>> : Ts... {
426 using type = Inherit_;
431 * Given a `TypeList`, create a type that inherits from all the types in the
434 * Requires: all of the types in the list are non-final class types, and the
435 * types are all unique.
437 template <class List>
438 using Inherit = impl::Inherit_<List>;
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>...>>)>;
447 template <class T, class... Set>
448 using In_ = std::is_base_of<Type<T>, Inherit<TypeList<Type<Set>...>>>;
452 struct InsertFront_ {
453 template <class... Set>
455 If<In_<T, Set...>::value, TypeList<Set...>, TypeList<T, Set...>>;
459 template <class T, class List>
460 using apply = MetaApply<List, impl::InsertFront_<T>>;
466 * Given a `TypeList`, produce a new list of types removing duplicates, keeping
467 * the first seen element.
469 * `TypeUnique<TypeList<int, short, int>>` is equivalent to
470 * `TypeList<int, short>`.
472 * \note This algorithm is O(N^2).
474 template <class List>
475 using TypeUnique = TypeFold<List, TypeList<>, impl::Unique_>;
478 * Given a `TypeList`, produce a new list of types removing duplicates, keeping
479 * the last seen element.
481 * `TypeUnique<TypeList<int, short, int>>` is equivalent to
482 * `TypeList<short, int>`.
484 * \note This algorithm is O(N^2).
486 template <class List>
487 using TypeReverseUnique =
488 TypeReverseFold<List, TypeList<>, MetaFlip<impl::Unique_>>;
493 struct AsTypeList_ {};
494 template <template <class...> class T, class... Ts>
495 struct AsTypeList_<T<Ts...>> {
496 using type = TypeList<Ts...>;
498 template <class T, T... Is>
499 struct AsTypeList_<folly::integer_sequence<T, Is...>> {
500 using type = TypeList<std::integral_constant<T, Is>...>;
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.
514 using AsTypeList = _t<impl::AsTypeList_<T>>;
518 // TODO For a list of N lists, this algorithm is O(N). It does no unrolling.
522 template <class... Ts>
523 using apply = MetaBindBack<Fn, Ts...>;
525 template <class List, class Fn>
526 using apply = MetaApply<List, Lambda<Fn>>;
532 * Given a `TypeList` of `TypeList`s, flatten the lists into a single list.
534 * `TypeJoin<TypeList<TypeList<As...>, TypeList<Bs...>>>` is equivalent to
535 * `TypeList<As..., Bs...>`
537 template <class List>
538 using TypeJoin = MetaApply<TypeFold<List, MetaQuote<TypeList>, impl::Join_>>;
541 * Given several `TypeList`s, flatten the lists into a single list.
543 * \note This is just the curried form of `TypeJoin`. (See `MetaCurry`.)
545 * `TypeConcat<TypeList<As...>, TypeList<Bs...>>` is equivalent to
546 * `TypeList<As..., Bs...>`
548 template <class... Ts>
549 using TypeConcat = TypeJoin<TypeList<Ts...>>;
550 } // namespace detail