container/internal/compressed_tuple.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014 //
0015 // Helper class to perform the Empty Base Optimization.
0016 // Ts can contain classes and non-classes, empty or not. For the ones that
0017 // are empty classes, we perform the optimization. If all types in Ts are empty
0018 // classes, then CompressedTuple<Ts...> is itself an empty class.
0019 //
0020 // To access the members, use member get<N>() function.
0021 //
0022 // Eg:
0023 //   absl::container_internal::CompressedTuple<int, T1, T2, T3> value(7, t1, t2,
0024 //                                                                    t3);
0025 //   assert(value.get<0>() == 7);
0026 //   T1& t1 = value.get<1>();
0027 //   const T2& t2 = value.get<2>();
0028 //   ...
0029 //
0030 // https://en.cppreference.com/w/cpp/language/ebo
0031
0032 #ifndef ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_
0033 #define ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_
0034
0035 #include <initializer_list>
0036 #include <tuple>
0037 #include <type_traits>
0038 #include <utility>
0039
0040 #include "absl/utility/utility.h"
0041
0042 #if defined(_MSC_VER) && !defined(__NVCC__)
0043 // We need to mark these classes with this declspec to ensure that
0044 // CompressedTuple happens.
0045 #define ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC __declspec(empty_bases)
0046 #else
0047 #define ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC
0048 #endif
0049
0050 namespace absl {
0051 ABSL_NAMESPACE_BEGIN
0052 namespace container_internal {
0053
0054 template <typename... Ts>
0055 class CompressedTuple;
0056
0057 namespace internal_compressed_tuple {
0058
0059 template <typename D, size_t I>
0060 struct Elem;
0061 template <typename... B, size_t I>
0062 struct Elem<CompressedTuple<B...>, I>
0063     : std::tuple_element<I, std::tuple<B...>> {};
0064 template <typename D, size_t I>
0065 using ElemT = typename Elem<D, I>::type;
0066
0067 // We can't use EBCO on other CompressedTuples because that would mean that we
0068 // derive from multiple Storage<> instantiations with the same I parameter,
0069 // and potentially from multiple identical Storage<> instantiations.  So anytime
0070 // we use type inheritance rather than encapsulation, we mark
0071 // CompressedTupleImpl, to make this easy to detect.
0072 struct uses_inheritance {};
0073
0074 template <typename T>
0075 constexpr bool ShouldUseBase() {
0076   return std::is_class<T>::value && std::is_empty<T>::value &&
0077          !std::is_final<T>::value &&
0078          !std::is_base_of<uses_inheritance, T>::value;
0079 }
0080
0081 // The storage class provides two specializations:
0082 //  - For empty classes, it stores T as a base class.
0083 //  - For everything else, it stores T as a member.
0084 template <typename T, size_t I, bool UseBase = ShouldUseBase<T>()>
0085 struct Storage {
0086   T value;
0087   constexpr Storage() = default;
0088   template <typename V>
0089   explicit constexpr Storage(absl::in_place_t, V&& v)
0090       : value(std::forward<V>(v)) {}
0091   constexpr const T& get() const& { return value; }
0092   constexpr T& get() & { return value; }
0093   constexpr const T&& get() const&& { return std::move(*this).value; }
0094   constexpr T&& get() && { return std::move(*this).value; }
0095 };
0096
0097 template <typename T, size_t I>
0098 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<T, I, true> : T {
0099   constexpr Storage() = default;
0100
0101   template <typename V>
0102   explicit constexpr Storage(absl::in_place_t, V&& v) : T(std::forward<V>(v)) {}
0103
0104   constexpr const T& get() const& { return *this; }
0105   constexpr T& get() & { return *this; }
0106   constexpr const T&& get() const&& { return std::move(*this); }
0107   constexpr T&& get() && { return std::move(*this); }
0108 };
0109
0110 template <typename D, typename I, bool ShouldAnyUseBase>
0111 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl;
0112
0113 template <typename... Ts, size_t... I, bool ShouldAnyUseBase>
0114 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl<
0115     CompressedTuple<Ts...>, absl::index_sequence<I...>, ShouldAnyUseBase>
0116     // We use the dummy identity function through std::integral_constant to
0117     // convince MSVC of accepting and expanding I in that context. Without it
0118     // you would get:
0119     //   error C3548: 'I': parameter pack cannot be used in this context
0120     : uses_inheritance,
0121       Storage<Ts, std::integral_constant<size_t, I>::value>... {
0122   constexpr CompressedTupleImpl() = default;
0123   template <typename... Vs>
0124   explicit constexpr CompressedTupleImpl(absl::in_place_t, Vs&&... args)
0125       : Storage<Ts, I>(absl::in_place, std::forward<Vs>(args))... {}
0126   friend CompressedTuple<Ts...>;
0127 };
0128
0129 template <typename... Ts, size_t... I>
0130 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl<
0131     CompressedTuple<Ts...>, absl::index_sequence<I...>, false>
0132     // We use the dummy identity function as above...
0133     : Storage<Ts, std::integral_constant<size_t, I>::value, false>... {
0134   constexpr CompressedTupleImpl() = default;
0135   template <typename... Vs>
0136   explicit constexpr CompressedTupleImpl(absl::in_place_t, Vs&&... args)
0137       : Storage<Ts, I, false>(absl::in_place, std::forward<Vs>(args))... {}
0138   friend CompressedTuple<Ts...>;
0139 };
0140
0141 std::false_type Or(std::initializer_list<std::false_type>);
0142 std::true_type Or(std::initializer_list<bool>);
0143
0144 // MSVC requires this to be done separately rather than within the declaration
0145 // of CompressedTuple below.
0146 template <typename... Ts>
0147 constexpr bool ShouldAnyUseBase() {
0148   return decltype(
0149       Or({std::integral_constant<bool, ShouldUseBase<Ts>()>()...})){};
0150 }
0151
0152 template <typename T, typename V>
0153 using TupleElementMoveConstructible =
0154     typename std::conditional<std::is_reference<T>::value,
0155                               std::is_convertible<V, T>,
0156                               std::is_constructible<T, V&&>>::type;
0157
0158 template <bool SizeMatches, class T, class... Vs>
0159 struct TupleMoveConstructible : std::false_type {};
0160
0161 template <class... Ts, class... Vs>
0162 struct TupleMoveConstructible<true, CompressedTuple<Ts...>, Vs...>
0163     : std::integral_constant<
0164           bool, absl::conjunction<
0165                     TupleElementMoveConstructible<Ts, Vs&&>...>::value> {};
0166
0167 template <typename T>
0168 struct compressed_tuple_size;
0169
0170 template <typename... Es>
0171 struct compressed_tuple_size<CompressedTuple<Es...>>
0172     : public std::integral_constant<std::size_t, sizeof...(Es)> {};
0173
0174 template <class T, class... Vs>
0175 struct TupleItemsMoveConstructible
0176     : std::integral_constant<
0177           bool, TupleMoveConstructible<compressed_tuple_size<T>::value ==
0178                                            sizeof...(Vs),
0179                                        T, Vs...>::value> {};
0180
0181 }  // namespace internal_compressed_tuple
0182
0183 // Helper class to perform the Empty Base Class Optimization.
0184 // Ts can contain classes and non-classes, empty or not. For the ones that
0185 // are empty classes, we perform the CompressedTuple. If all types in Ts are
0186 // empty classes, then CompressedTuple<Ts...> is itself an empty class.  (This
0187 // does not apply when one or more of those empty classes is itself an empty
0188 // CompressedTuple.)
0189 //
0190 // To access the members, use member .get<N>() function.
0191 //
0192 // Eg:
0193 //   absl::container_internal::CompressedTuple<int, T1, T2, T3> value(7, t1, t2,
0194 //                                                                    t3);
0195 //   assert(value.get<0>() == 7);
0196 //   T1& t1 = value.get<1>();
0197 //   const T2& t2 = value.get<2>();
0198 //   ...
0199 //
0200 // https://en.cppreference.com/w/cpp/language/ebo
0201 template <typename... Ts>
0202 class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple
0203     : private internal_compressed_tuple::CompressedTupleImpl<
0204           CompressedTuple<Ts...>, absl::index_sequence_for<Ts...>,
0205           internal_compressed_tuple::ShouldAnyUseBase<Ts...>()> {
0206  private:
0207   template <int I>
0208   using ElemT = internal_compressed_tuple::ElemT<CompressedTuple, I>;
0209
0210   template <int I>
0211   using StorageT = internal_compressed_tuple::Storage<ElemT<I>, I>;
0212
0213  public:
0214   // There seems to be a bug in MSVC dealing in which using '=default' here will
0215   // cause the compiler to ignore the body of other constructors. The work-
0216   // around is to explicitly implement the default constructor.
0217 #if defined(_MSC_VER)
0218   constexpr CompressedTuple() : CompressedTuple::CompressedTupleImpl() {}
0219 #else
0220   constexpr CompressedTuple() = default;
0221 #endif
0222   explicit constexpr CompressedTuple(const Ts&... base)
0223       : CompressedTuple::CompressedTupleImpl(absl::in_place, base...) {}
0224
0225   template <typename First, typename... Vs,
0226             absl::enable_if_t<
0227                 absl::conjunction<
0228                     // Ensure we are not hiding default copy/move constructors.
0229                     absl::negation<std::is_same<void(CompressedTuple),
0230                                                 void(absl::decay_t<First>)>>,
0231                     internal_compressed_tuple::TupleItemsMoveConstructible<
0232                         CompressedTuple<Ts...>, First, Vs...>>::value,
0233                 bool> = true>
0234   explicit constexpr CompressedTuple(First&& first, Vs&&... base)
0235       : CompressedTuple::CompressedTupleImpl(absl::in_place,
0236                                              std::forward<First>(first),
0237                                              std::forward<Vs>(base)...) {}
0238
0239   template <int I>
0240   constexpr ElemT<I>& get() & {
0241     return StorageT<I>::get();
0242   }
0243
0244   template <int I>
0245   constexpr const ElemT<I>& get() const& {
0246     return StorageT<I>::get();
0247   }
0248
0249   template <int I>
0250   constexpr ElemT<I>&& get() && {
0251     return std::move(*this).StorageT<I>::get();
0252   }
0253
0254   template <int I>
0255   constexpr const ElemT<I>&& get() const&& {
0256     return std::move(*this).StorageT<I>::get();
0257   }
0258 };
0259
0260 // Explicit specialization for a zero-element tuple
0261 // (needed to avoid ambiguous overloads for the default constructor).
0262 template <>
0263 class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple<> {};
0264
0265 }  // namespace container_internal
0266 ABSL_NAMESPACE_END
0267 }  // namespace absl
0268
0269 #undef ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC
0270
0271 #endif  // ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_