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 "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
50namespace absl {
51namespace container_internal {
52
53template <typename... Ts>
54class CompressedTuple;
55
56namespace internal_compressed_tuple {
57
58template <typename D, size_t I>
59struct Elem;
60template <typename... B, size_t I>
61struct Elem<CompressedTuple<B...>, I>
62 : std::tuple_element<I, std::tuple<B...>> {};
63template <typename D, size_t I>
64using ElemT = typename Elem<D, I>::type;
65
66// Use the __is_final intrinsic if available. Where it's not available, classes
67// declared with the 'final' specifier cannot be used as CompressedTuple
68// elements.
69// TODO(sbenza): Replace this with std::is_final in C++14.
70template <typename T>
71constexpr bool IsFinal() {
72#if defined(__clang__) || defined(__GNUC__)
73 return __is_final(T);
74#else
75 return false;
76#endif
77}
78
79// We can't use EBCO on other CompressedTuples because that would mean that we
80// derive from multiple Storage<> instantiations with the same I parameter,
81// and potentially from multiple identical Storage<> instantiations. So anytime
82// we use type inheritance rather than encapsulation, we mark
83// CompressedTupleImpl, to make this easy to detect.
84struct uses_inheritance {};
85
86template <typename T>
87constexpr bool ShouldUseBase() {
88 return std::is_class<T>::value && std::is_empty<T>::value && !IsFinal<T>() &&
89 !std::is_base_of<uses_inheritance, T>::value;
90}
91
92// The storage class provides two specializations:
93// - For empty classes, it stores T as a base class.
94// - For everything else, it stores T as a member.
95template <typename T, size_t I,
96#if defined(_MSC_VER)
97 bool UseBase =
98 ShouldUseBase<typename std::enable_if<true, T>::type>()>
99#else
100 bool UseBase = ShouldUseBase<T>()>
101#endif
102struct Storage {
103 T value;
104 constexpr Storage() = default;
105 explicit constexpr Storage(T&& v) : value(absl::forward<T>(v)) {}
106 constexpr const T& get() const& { return value; }
107 T& get() & { return value; }
108 constexpr const T&& get() const&& { return absl::move(*this).value; }
109 T&& get() && { return std::move(*this).value; }
110};
111
112template <typename T, size_t I>
113struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<T, I, true> : T {
114 constexpr Storage() = default;
115 explicit constexpr Storage(T&& v) : T(absl::forward<T>(v)) {}
116 constexpr const T& get() const& { return *this; }
117 T& get() & { return *this; }
118 constexpr const T&& get() const&& { return absl::move(*this); }
119 T&& get() && { return std::move(*this); }
120};
121
122template <typename D, typename I, bool ShouldAnyUseBase>
123struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl;
124
125template <typename... Ts, size_t... I, bool ShouldAnyUseBase>
126struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl<
127 CompressedTuple<Ts...>, absl::index_sequence<I...>, ShouldAnyUseBase>
128 // We use the dummy identity function through std::integral_constant to
129 // convince MSVC of accepting and expanding I in that context. Without it
130 // you would get:
131 // error C3548: 'I': parameter pack cannot be used in this context
132 : uses_inheritance,
133 Storage<Ts, std::integral_constant<size_t, I>::value>... {
134 constexpr CompressedTupleImpl() = default;
135 explicit constexpr CompressedTupleImpl(Ts&&... args)
136 : Storage<Ts, I>(absl::forward<Ts>(args))... {}
137 friend CompressedTuple<Ts...>;
138};
139
140template <typename... Ts, size_t... I>
141struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl<
142 CompressedTuple<Ts...>, absl::index_sequence<I...>, false>
143 // We use the dummy identity function as above...
144 : Storage<Ts, std::integral_constant<size_t, I>::value, false>... {
145 constexpr CompressedTupleImpl() = default;
146 explicit constexpr CompressedTupleImpl(Ts&&... args)
147 : Storage<Ts, I, false>(absl::forward<Ts>(args))... {}
148 friend CompressedTuple<Ts...>;
149};
150
151std::false_type Or(std::initializer_list<std::false_type>);
152std::true_type Or(std::initializer_list<bool>);
153
154// MSVC requires this to be done separately rather than within the declaration
155// of CompressedTuple below.
156template <typename... Ts>
157constexpr bool ShouldAnyUseBase() {
158 return decltype(
159 Or({std::integral_constant<bool, ShouldUseBase<Ts>()>()...})){};
160}
161
162} // namespace internal_compressed_tuple
163
164// Helper class to perform the Empty Base Class Optimization.
165// Ts can contain classes and non-classes, empty or not. For the ones that
166// are empty classes, we perform the CompressedTuple. If all types in Ts are
167// empty classes, then CompressedTuple<Ts...> is itself an empty class. (This
168// does not apply when one or more of those empty classes is itself an empty
169// CompressedTuple.)
170//
171// To access the members, use member .get<N>() function.
172//
173// Eg:
174// absl::container_internal::CompressedTuple<int, T1, T2, T3> value(7, t1, t2,
175// t3);
176// assert(value.get<0>() == 7);
177// T1& t1 = value.get<1>();
178// const T2& t2 = value.get<2>();
179// ...
180//
181// https://en.cppreference.com/w/cpp/language/ebo
182template <typename... Ts>
183class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple
184 : private internal_compressed_tuple::CompressedTupleImpl<
185 CompressedTuple<Ts...>, absl::index_sequence_for<Ts...>,
186 internal_compressed_tuple::ShouldAnyUseBase<Ts...>()> {
187 private:
188 template <int I>
189 using ElemT = internal_compressed_tuple::ElemT<CompressedTuple, I>;
190
191 public:
192 constexpr CompressedTuple() = default;
193 explicit constexpr CompressedTuple(Ts... base)
194 : CompressedTuple::CompressedTupleImpl(absl::forward<Ts>(base)...) {}
195
196 template <int I>
197 ElemT<I>& get() & {
198 return internal_compressed_tuple::Storage<ElemT<I>, I>::get();
199 }
200
201 template <int I>
202 constexpr const ElemT<I>& get() const& {
203 return internal_compressed_tuple::Storage<ElemT<I>, I>::get();
204 }
205
206 template <int I>
207 ElemT<I>&& get() && {
208 return std::move(*this)
209 .internal_compressed_tuple::template Storage<ElemT<I>, I>::get();
210 }
211
212 template <int I>
213 constexpr const ElemT<I>&& get() const&& {
214 return absl::move(*this)
215 .internal_compressed_tuple::template Storage<ElemT<I>, I>::get();
216 }
217};
218
219// Explicit specialization for a zero-element tuple
220// (needed to avoid ambiguous overloads for the default constructor).
221template <>
222class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple<> {};
223
224} // namespace container_internal
225} // namespace absl
226
227#undef ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC
228
229#endif // ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_
230