1 // Copyright 2018 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // Helper class to perform the Empty Base Optimization. 16 // Ts can contain classes and non-classes, empty or not. For the ones that 17 // are empty classes, we perform the optimization. If all types in Ts are empty 18 // classes, then CompressedTuple<Ts...> is itself an empty class. 19 // 20 // To access the members, use member get<N>() function. 21 // 22 // Eg: 23 // absl::container_internal::CompressedTuple<int, T1, T2, T3> value(7, t1, t2, 24 // t3); 25 // assert(value.get<0>() == 7); 26 // T1& t1 = value.get<1>(); 27 // const T2& t2 = value.get<2>(); 28 // ... 29 // 30 // https://en.cppreference.com/w/cpp/language/ebo 31 32 #ifndef ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_ 33 #define ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_ 34 35 #include <initializer_list> 36 #include <tuple> 37 #include <type_traits> 38 #include <utility> 39 40 #include "third_party/abseil-cpp/absl/utility/utility.h" 41 42 #if defined(_MSC_VER) && !defined(__NVCC__) 43 // We need to mark these classes with this declspec to ensure that 44 // CompressedTuple happens. 45 #define ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC __declspec(empty_bases) 46 #else 47 #define ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC 48 #endif 49 50 namespace absl { 51 ABSL_NAMESPACE_BEGIN 52 namespace container_internal { 53 54 template <typename... Ts> 55 class CompressedTuple; 56 57 namespace internal_compressed_tuple { 58 59 template <typename D, size_t I> 60 struct Elem; 61 template <typename... B, size_t I> 62 struct Elem<CompressedTuple<B...>, I> 63 : std::tuple_element<I, std::tuple<B...>> {}; 64 template <typename D, size_t I> 65 using ElemT = typename Elem<D, I>::type; 66 67 // We can't use EBCO on other CompressedTuples because that would mean that we 68 // derive from multiple Storage<> instantiations with the same I parameter, 69 // and potentially from multiple identical Storage<> instantiations. So anytime 70 // we use type inheritance rather than encapsulation, we mark 71 // CompressedTupleImpl, to make this easy to detect. 72 struct uses_inheritance {}; 73 74 template <typename T> 75 constexpr bool ShouldUseBase() { 76 return std::is_class<T>::value && std::is_empty<T>::value && 77 !std::is_final<T>::value && 78 !std::is_base_of<uses_inheritance, T>::value; 79 } 80 81 // The storage class provides two specializations: 82 // - For empty classes, it stores T as a base class. 83 // - For everything else, it stores T as a member. 84 template <typename T, size_t I, bool UseBase = ShouldUseBase<T>()> 85 struct Storage { 86 T value; 87 constexpr Storage() = default; 88 template <typename V> 89 explicit constexpr Storage(absl::in_place_t, V&& v) 90 : value(std::forward<V>(v)) {} 91 constexpr const T& get() const& { return value; } 92 constexpr T& get() & { return value; } 93 constexpr const T&& get() const&& { return std::move(*this).value; } 94 constexpr T&& get() && { return std::move(*this).value; } 95 }; 96 97 template <typename T, size_t I> 98 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<T, I, true> : T { 99 constexpr Storage() = default; 100 101 template <typename V> 102 explicit constexpr Storage(absl::in_place_t, V&& v) : T(std::forward<V>(v)) {} 103 104 constexpr const T& get() const& { return *this; } 105 constexpr T& get() & { return *this; } 106 constexpr const T&& get() const&& { return std::move(*this); } 107 constexpr T&& get() && { return std::move(*this); } 108 }; 109 110 template <typename D, typename I, bool ShouldAnyUseBase> 111 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl; 112 113 template <typename... Ts, size_t... I, bool ShouldAnyUseBase> 114 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl< 115 CompressedTuple<Ts...>, absl::index_sequence<I...>, ShouldAnyUseBase> 116 // We use the dummy identity function through std::integral_constant to 117 // convince MSVC of accepting and expanding I in that context. Without it 118 // you would get: 119 // error C3548: 'I': parameter pack cannot be used in this context 120 : uses_inheritance, 121 Storage<Ts, std::integral_constant<size_t, I>::value>... { 122 constexpr CompressedTupleImpl() = default; 123 template <typename... Vs> 124 explicit constexpr CompressedTupleImpl(absl::in_place_t, Vs&&... args) 125 : Storage<Ts, I>(absl::in_place, std::forward<Vs>(args))... {} 126 friend CompressedTuple<Ts...>; 127 }; 128 129 template <typename... Ts, size_t... I> 130 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl< 131 CompressedTuple<Ts...>, absl::index_sequence<I...>, false> 132 // We use the dummy identity function as above... 133 : Storage<Ts, std::integral_constant<size_t, I>::value, false>... { 134 constexpr CompressedTupleImpl() = default; 135 template <typename... Vs> 136 explicit constexpr CompressedTupleImpl(absl::in_place_t, Vs&&... args) 137 : Storage<Ts, I, false>(absl::in_place, std::forward<Vs>(args))... {} 138 friend CompressedTuple<Ts...>; 139 }; 140 141 std::false_type Or(std::initializer_list<std::false_type>); 142 std::true_type Or(std::initializer_list<bool>); 143 144 // MSVC requires this to be done separately rather than within the declaration 145 // of CompressedTuple below. 146 template <typename... Ts> 147 constexpr bool ShouldAnyUseBase() { 148 return decltype( 149 Or({std::integral_constant<bool, ShouldUseBase<Ts>()>()...})){}; 150 } 151 152 template <typename T, typename V> 153 using TupleElementMoveConstructible = 154 typename std::conditional<std::is_reference<T>::value, 155 std::is_convertible<V, T>, 156 std::is_constructible<T, V&&>>::type; 157 158 template <bool SizeMatches, class T, class... Vs> 159 struct TupleMoveConstructible : std::false_type {}; 160 161 template <class... Ts, class... Vs> 162 struct TupleMoveConstructible<true, CompressedTuple<Ts...>, Vs...> 163 : std::integral_constant< 164 bool, absl::conjunction< 165 TupleElementMoveConstructible<Ts, Vs&&>...>::value> {}; 166 167 template <typename T> 168 struct compressed_tuple_size; 169 170 template <typename... Es> 171 struct compressed_tuple_size<CompressedTuple<Es...>> 172 : public std::integral_constant<std::size_t, sizeof...(Es)> {}; 173 174 template <class T, class... Vs> 175 struct TupleItemsMoveConstructible 176 : std::integral_constant< 177 bool, TupleMoveConstructible<compressed_tuple_size<T>::value == 178 sizeof...(Vs), 179 T, Vs...>::value> {}; 180 181 } // namespace internal_compressed_tuple 182 183 // Helper class to perform the Empty Base Class Optimization. 184 // Ts can contain classes and non-classes, empty or not. For the ones that 185 // are empty classes, we perform the CompressedTuple. If all types in Ts are 186 // empty classes, then CompressedTuple<Ts...> is itself an empty class. (This 187 // does not apply when one or more of those empty classes is itself an empty 188 // CompressedTuple.) 189 // 190 // To access the members, use member .get<N>() function. 191 // 192 // Eg: 193 // absl::container_internal::CompressedTuple<int, T1, T2, T3> value(7, t1, t2, 194 // t3); 195 // assert(value.get<0>() == 7); 196 // T1& t1 = value.get<1>(); 197 // const T2& t2 = value.get<2>(); 198 // ... 199 // 200 // https://en.cppreference.com/w/cpp/language/ebo 201 template <typename... Ts> 202 class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple 203 : private internal_compressed_tuple::CompressedTupleImpl< 204 CompressedTuple<Ts...>, absl::index_sequence_for<Ts...>, 205 internal_compressed_tuple::ShouldAnyUseBase<Ts...>()> { 206 private: 207 template <int I> 208 using ElemT = internal_compressed_tuple::ElemT<CompressedTuple, I>; 209 210 template <int I> 211 using StorageT = internal_compressed_tuple::Storage<ElemT<I>, I>; 212 213 public: 214 // There seems to be a bug in MSVC dealing in which using '=default' here will 215 // cause the compiler to ignore the body of other constructors. The work- 216 // around is to explicitly implement the default constructor. 217 #if defined(_MSC_VER) 218 constexpr CompressedTuple() : CompressedTuple::CompressedTupleImpl() {} 219 #else 220 constexpr CompressedTuple() = default; 221 #endif 222 explicit constexpr CompressedTuple(const Ts&... base) 223 : CompressedTuple::CompressedTupleImpl(absl::in_place, base...) {} 224 225 template <typename First, typename... Vs, 226 absl::enable_if_t< 227 absl::conjunction< 228 // Ensure we are not hiding default copy/move constructors. 229 absl::negation<std::is_same<void(CompressedTuple), 230 void(absl::decay_t<First>)>>, 231 internal_compressed_tuple::TupleItemsMoveConstructible< 232 CompressedTuple<Ts...>, First, Vs...>>::value, 233 bool> = true> 234 explicit constexpr CompressedTuple(First&& first, Vs&&... base) 235 : CompressedTuple::CompressedTupleImpl(absl::in_place, 236 std::forward<First>(first), 237 std::forward<Vs>(base)...) {} 238 239 template <int I> 240 constexpr ElemT<I>& get() & { 241 return StorageT<I>::get(); 242 } 243 244 template <int I> 245 constexpr const ElemT<I>& get() const& { 246 return StorageT<I>::get(); 247 } 248 249 template <int I> 250 constexpr ElemT<I>&& get() && { 251 return std::move(*this).StorageT<I>::get(); 252 } 253 254 template <int I> 255 constexpr const ElemT<I>&& get() const&& { 256 return std::move(*this).StorageT<I>::get(); 257 } 258 }; 259 260 // Explicit specialization for a zero-element tuple 261 // (needed to avoid ambiguous overloads for the default constructor). 262 template <> 263 class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple<> {}; 264 265 } // namespace container_internal 266 ABSL_NAMESPACE_END 267 } // namespace absl 268 269 #undef ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC 270 271 #endif // THIRD_PARTY_ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_