folly/detail/TypeList.h

   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 = std::integral_constant<bool, 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