TypeList.h

Go to the documentation of this file.

/*
 * Copyright 2017-present Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <cstddef>
#include <utility>

#include <folly/Traits.h>
#include <folly/Utility.h>

namespace folly {
namespace detail {

template <bool B>
using Bool = bool_constant<B>;
using True = std::true_type;
using False = std::false_type;

template <class Fn, class... Ts>
using MetaApply = typename Fn::template apply<Ts...>;

template <class... Ts>
struct TypeList {
  using type = TypeList;

  static constexpr std::size_t size() noexcept {
    return sizeof...(Ts);
  }

  template <class Fn>
  using apply = MetaApply<Fn, Ts...>;
};

template <class T>
struct Type {
  using type = T;

  template <class...>
  using apply = T;
};

struct Empty {};

namespace impl {
template <bool B>
struct If_ {
  template <class T, class U>
  using apply = T;
};
template <>
struct If_<false> {
  template <class T, class U>
  using apply = U;
};
} // namespace impl

template <bool If_, class Then, class Else>
using If = MetaApply<impl::If_<If_>, Then, Else>;

template <template <class...> class C, class... Ts>
class MetaDefer {
  template <template <class...> class D = C, class = D<Ts...>>
  static char (&try_(int))[1];
  static char (&try_(long))[2];
  struct Result {
    using type = C<Ts...>;
  };

 public:
  template <class... Us>
  using apply = _t<If<sizeof(try_(0)) - 1 || sizeof...(Us), Empty, Result>>;
};

template <class P, class Q>
struct MetaCompose {
  template <class... Ts>
  using apply = MetaApply<P, MetaApply<Q, Ts...>>;
};

struct MetaIdentity {
  template <class T>
  using apply = T;
};

template <template <class...> class C>
struct MetaQuote {
  template <class... Ts>
  using apply = MetaApply<MetaDefer<C, Ts...>>;
};

// Specialization for TypeList since it doesn't need to go through MetaDefer
template <>
struct MetaQuote<TypeList> {
  template <class... Ts>
  using apply = TypeList<Ts...>;
};

template <template <class...> class C>
using MetaQuoteTrait = MetaCompose<MetaQuote<_t>, MetaQuote<C>>;

template <class Fn, class... Ts>
struct MetaBindFront {
  template <class... Us>
  using apply = MetaApply<Fn, Ts..., Us...>;
};

template <class Fn, class... Ts>
struct MetaBindBack {
  template <class... Us>
  using apply = MetaApply<Fn, Us..., Ts...>;
};

template <class Fn>
using MetaCurry = MetaCompose<Fn, MetaQuote<TypeList>>;

template <class Fn>
using MetaUncurry = MetaBindBack<MetaQuote<MetaApply>, Fn>;

template <class List, class... Ts>
using TypePushBack = MetaApply<List, MetaBindBack<MetaQuote<TypeList>, Ts...>>;

template <class List, class... Ts>
using TypePushFront =
    MetaApply<List, MetaBindFront<MetaQuote<TypeList>, Ts...>>;

template <class Fn, class List>
using MetaUnpack = MetaApply<List, Fn>;

namespace impl {
template <class Fn>
struct TypeTransform_ {
  template <class... Ts>
  using apply = TypeList<MetaApply<Fn, Ts>...>;
};
} // namespace impl

template <class List, class Fn>
using TypeTransform = MetaApply<List, impl::TypeTransform_<Fn>>;

template <class Fn>
struct MetaFlip {
  template <class A, class B>
  using apply = MetaApply<Fn, B, A>;
};

namespace impl {
template <class Fn>
struct FoldR_ {
  template <class... Ts>
  struct Lambda : MetaIdentity {};
  template <class A, class... Ts>
  struct Lambda<A, Ts...> {
    template <class State>
    using apply = MetaApply<Fn, A, MetaApply<Lambda<Ts...>, State>>;
  };
  template <class A, class B, class C, class D, class... Ts>
  struct Lambda<A, B, C, D, Ts...> { // manually unroll 4 elements
    template <class State>
    using apply = MetaApply<
        Fn,
        A,
        MetaApply<
            Fn,
            B,
            MetaApply<
                Fn,
                C,
                MetaApply<Fn, D, MetaApply<Lambda<Ts...>, State>>>>>;
  };
  template <class... Ts>
  using apply = Lambda<Ts...>;
};
} // namespace impl

template <class List, class State, class Fn>
using TypeFold = MetaApply<MetaApply<List, impl::FoldR_<Fn>>, State>;

namespace impl {
template <class Fn>
struct FoldL_ {
  template <class... Ts>
  struct Lambda : MetaIdentity {};
  template <class A, class... Ts>
  struct Lambda<A, Ts...> {
    template <class State>
    using apply = MetaApply<Lambda<Ts...>, MetaApply<Fn, State, A>>;
  };
  template <class A, class B, class C, class D, class... Ts>
  struct Lambda<A, B, C, D, Ts...> { // manually unroll 4 elements
    template <class State>
    using apply = MetaApply<
        Lambda<Ts...>,
        MetaApply<
            Fn,
            MetaApply<Fn, MetaApply<Fn, MetaApply<Fn, State, A>, B>, C>,
            D>>;
  };
  template <class... Ts>
  using apply = Lambda<Ts...>;
};
} // namespace impl

template <class List, class State, class Fn>
using TypeReverseFold = MetaApply<MetaApply<List, impl::FoldL_<Fn>>, State>;

namespace impl {
template <class List>
struct Inherit_;
template <class... Ts>
struct Inherit_<TypeList<Ts...>> : Ts... {
  using type = Inherit_;
};
} // namespace impl

template <class List>
using Inherit = impl::Inherit_<List>;

namespace impl {
// Avoid instantiating std::is_base_of when we have an intrinsic.
#if defined(__GNUC__) || defined(_MSC_VER)
template <class T, class... Set>
using In_ = Bool<__is_base_of(Type<T>, Inherit<TypeList<Type<Set>...>>)>;
#else
template <class T, class... Set>
using In_ = std::is_base_of<Type<T>, Inherit<TypeList<Type<Set>...>>>;
#endif

template <class T>
struct InsertFront_ {
  template <class... Set>
  using apply =
      If<In_<T, Set...>::value, TypeList<Set...>, TypeList<T, Set...>>;
};

struct Unique_ {
  template <class T, class List>
  using apply = MetaApply<List, impl::InsertFront_<T>>;
};
} // namespace impl

template <class List>
using TypeUnique = TypeFold<List, TypeList<>, impl::Unique_>;

template <class List>
using TypeReverseUnique =
    TypeReverseFold<List, TypeList<>, MetaFlip<impl::Unique_>>;

namespace impl {
template <class T>
struct AsTypeList_ {};
template <template <class...> class T, class... Ts>
struct AsTypeList_<T<Ts...>> {
  using type = TypeList<Ts...>;
};
template <class T, T... Is>
struct AsTypeList_<folly::integer_sequence<T, Is...>> {
  using type = TypeList<std::integral_constant<T, Is>...>;
};
} // namespace impl

template <class T>
using AsTypeList = _t<impl::AsTypeList_<T>>;

namespace impl {
// TODO For a list of N lists, this algorithm is O(N). It does no unrolling.
struct Join_ {
  template <class Fn>
  struct Lambda {
    template <class... Ts>
    using apply = MetaBindBack<Fn, Ts...>;
  };
  template <class List, class Fn>
  using apply = MetaApply<List, Lambda<Fn>>;
};
} // namespace impl

template <class List>
using TypeJoin = MetaApply<TypeFold<List, MetaQuote<TypeList>, impl::Join_>>;

template <class... Ts>
using TypeConcat = TypeJoin<TypeList<Ts...>>;
} // namespace detail
} // namespace folly