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 #include "absl/container/internal/compressed_tuple.h"
16
17 #include <memory>
18 #include <string>
19
20 #include "gmock/gmock.h"
21 #include "gtest/gtest.h"
22 #include "absl/container/internal/test_instance_tracker.h"
23 #include "absl/memory/memory.h"
24 #include "absl/types/any.h"
25 #include "absl/types/optional.h"
26 #include "absl/utility/utility.h"
27
28 // These are declared at global scope purely so that error messages
29 // are smaller and easier to understand.
30 enum class CallType { kConstRef, kConstMove };
31
32 template <int>
33 struct Empty {
valueEmpty34 constexpr CallType value() const& { return CallType::kConstRef; }
valueEmpty35 constexpr CallType value() const&& { return CallType::kConstMove; }
36 };
37
38 template <typename T>
39 struct NotEmpty {
40 T value;
41 };
42
43 template <typename T, typename U>
44 struct TwoValues {
45 T value1;
46 U value2;
47 };
48
49
50 namespace absl {
51 ABSL_NAMESPACE_BEGIN
52 namespace container_internal {
53 namespace {
54
55 using absl::test_internal::CopyableMovableInstance;
56 using absl::test_internal::InstanceTracker;
57
TEST(CompressedTupleTest,Sizeof)58 TEST(CompressedTupleTest, Sizeof) {
59 EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int>));
60 EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int, Empty<0>>));
61 EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int, Empty<0>, Empty<1>>));
62 EXPECT_EQ(sizeof(int),
63 sizeof(CompressedTuple<int, Empty<0>, Empty<1>, Empty<2>>));
64
65 EXPECT_EQ(sizeof(TwoValues<int, double>),
66 sizeof(CompressedTuple<int, NotEmpty<double>>));
67 EXPECT_EQ(sizeof(TwoValues<int, double>),
68 sizeof(CompressedTuple<int, Empty<0>, NotEmpty<double>>));
69 EXPECT_EQ(sizeof(TwoValues<int, double>),
70 sizeof(CompressedTuple<int, Empty<0>, NotEmpty<double>, Empty<1>>));
71 }
72
TEST(CompressedTupleTest,OneMoveOnRValueConstructionTemp)73 TEST(CompressedTupleTest, OneMoveOnRValueConstructionTemp) {
74 InstanceTracker tracker;
75 CompressedTuple<CopyableMovableInstance> x1(CopyableMovableInstance(1));
76 EXPECT_EQ(tracker.instances(), 1);
77 EXPECT_EQ(tracker.copies(), 0);
78 EXPECT_LE(tracker.moves(), 1);
79 EXPECT_EQ(x1.get<0>().value(), 1);
80 }
81
TEST(CompressedTupleTest,OneMoveOnRValueConstructionMove)82 TEST(CompressedTupleTest, OneMoveOnRValueConstructionMove) {
83 InstanceTracker tracker;
84
85 CopyableMovableInstance i1(1);
86 CompressedTuple<CopyableMovableInstance> x1(std::move(i1));
87 EXPECT_EQ(tracker.instances(), 2);
88 EXPECT_EQ(tracker.copies(), 0);
89 EXPECT_LE(tracker.moves(), 1);
90 EXPECT_EQ(x1.get<0>().value(), 1);
91 }
92
TEST(CompressedTupleTest,OneMoveOnRValueConstructionMixedTypes)93 TEST(CompressedTupleTest, OneMoveOnRValueConstructionMixedTypes) {
94 InstanceTracker tracker;
95 CopyableMovableInstance i1(1);
96 CopyableMovableInstance i2(2);
97 Empty<0> empty;
98 CompressedTuple<CopyableMovableInstance, CopyableMovableInstance&, Empty<0>>
99 x1(std::move(i1), i2, empty);
100 EXPECT_EQ(x1.get<0>().value(), 1);
101 EXPECT_EQ(x1.get<1>().value(), 2);
102 EXPECT_EQ(tracker.copies(), 0);
103 EXPECT_EQ(tracker.moves(), 1);
104 }
105
106 struct IncompleteType;
107 CompressedTuple<CopyableMovableInstance, IncompleteType&, Empty<0>>
MakeWithIncomplete(CopyableMovableInstance i1,IncompleteType & t,Empty<0> empty)108 MakeWithIncomplete(CopyableMovableInstance i1,
109 IncompleteType& t, // NOLINT
110 Empty<0> empty) {
111 return CompressedTuple<CopyableMovableInstance, IncompleteType&, Empty<0>>{
112 std::move(i1), t, empty};
113 }
114
115 struct IncompleteType {};
TEST(CompressedTupleTest,OneMoveOnRValueConstructionWithIncompleteType)116 TEST(CompressedTupleTest, OneMoveOnRValueConstructionWithIncompleteType) {
117 InstanceTracker tracker;
118 CopyableMovableInstance i1(1);
119 Empty<0> empty;
120 struct DerivedType : IncompleteType {int value = 0;};
121 DerivedType fd;
122 fd.value = 7;
123
124 CompressedTuple<CopyableMovableInstance, IncompleteType&, Empty<0>> x1 =
125 MakeWithIncomplete(std::move(i1), fd, empty);
126
127 EXPECT_EQ(x1.get<0>().value(), 1);
128 EXPECT_EQ(static_cast<DerivedType&>(x1.get<1>()).value, 7);
129
130 EXPECT_EQ(tracker.copies(), 0);
131 EXPECT_EQ(tracker.moves(), 2);
132 }
133
TEST(CompressedTupleTest,OneMoveOnRValueConstructionMixedTypes_BraceInitPoisonPillExpected)134 TEST(CompressedTupleTest,
135 OneMoveOnRValueConstructionMixedTypes_BraceInitPoisonPillExpected) {
136 InstanceTracker tracker;
137 CopyableMovableInstance i1(1);
138 CopyableMovableInstance i2(2);
139 CompressedTuple<CopyableMovableInstance, CopyableMovableInstance&, Empty<0>>
140 x1(std::move(i1), i2, {}); // NOLINT
141 EXPECT_EQ(x1.get<0>().value(), 1);
142 EXPECT_EQ(x1.get<1>().value(), 2);
143 EXPECT_EQ(tracker.instances(), 3);
144 // We are forced into the `const Ts&...` constructor (invoking copies)
145 // because we need it to deduce the type of `{}`.
146 // std::tuple also has this behavior.
147 // Note, this test is proof that this is expected behavior, but it is not
148 // _desired_ behavior.
149 EXPECT_EQ(tracker.copies(), 1);
150 EXPECT_EQ(tracker.moves(), 0);
151 }
152
TEST(CompressedTupleTest,OneCopyOnLValueConstruction)153 TEST(CompressedTupleTest, OneCopyOnLValueConstruction) {
154 InstanceTracker tracker;
155 CopyableMovableInstance i1(1);
156
157 CompressedTuple<CopyableMovableInstance> x1(i1);
158 EXPECT_EQ(tracker.copies(), 1);
159 EXPECT_EQ(tracker.moves(), 0);
160
161 tracker.ResetCopiesMovesSwaps();
162
163 CopyableMovableInstance i2(2);
164 const CopyableMovableInstance& i2_ref = i2;
165 CompressedTuple<CopyableMovableInstance> x2(i2_ref);
166 EXPECT_EQ(tracker.copies(), 1);
167 EXPECT_EQ(tracker.moves(), 0);
168 }
169
TEST(CompressedTupleTest,OneMoveOnRValueAccess)170 TEST(CompressedTupleTest, OneMoveOnRValueAccess) {
171 InstanceTracker tracker;
172 CopyableMovableInstance i1(1);
173 CompressedTuple<CopyableMovableInstance> x(std::move(i1));
174 tracker.ResetCopiesMovesSwaps();
175
176 CopyableMovableInstance i2 = std::move(x).get<0>();
177 EXPECT_EQ(tracker.copies(), 0);
178 EXPECT_EQ(tracker.moves(), 1);
179 }
180
TEST(CompressedTupleTest,OneCopyOnLValueAccess)181 TEST(CompressedTupleTest, OneCopyOnLValueAccess) {
182 InstanceTracker tracker;
183
184 CompressedTuple<CopyableMovableInstance> x(CopyableMovableInstance(0));
185 EXPECT_EQ(tracker.copies(), 0);
186 EXPECT_EQ(tracker.moves(), 1);
187
188 CopyableMovableInstance t = x.get<0>();
189 EXPECT_EQ(tracker.copies(), 1);
190 EXPECT_EQ(tracker.moves(), 1);
191 }
192
TEST(CompressedTupleTest,ZeroCopyOnRefAccess)193 TEST(CompressedTupleTest, ZeroCopyOnRefAccess) {
194 InstanceTracker tracker;
195
196 CompressedTuple<CopyableMovableInstance> x(CopyableMovableInstance(0));
197 EXPECT_EQ(tracker.copies(), 0);
198 EXPECT_EQ(tracker.moves(), 1);
199
200 CopyableMovableInstance& t1 = x.get<0>();
201 const CopyableMovableInstance& t2 = x.get<0>();
202 EXPECT_EQ(tracker.copies(), 0);
203 EXPECT_EQ(tracker.moves(), 1);
204 EXPECT_EQ(t1.value(), 0);
205 EXPECT_EQ(t2.value(), 0);
206 }
207
TEST(CompressedTupleTest,Access)208 TEST(CompressedTupleTest, Access) {
209 struct S {
210 std::string x;
211 };
212 CompressedTuple<int, Empty<0>, S> x(7, {}, S{"ABC"});
213 EXPECT_EQ(sizeof(x), sizeof(TwoValues<int, S>));
214 EXPECT_EQ(7, x.get<0>());
215 EXPECT_EQ("ABC", x.get<2>().x);
216 }
217
TEST(CompressedTupleTest,NonClasses)218 TEST(CompressedTupleTest, NonClasses) {
219 CompressedTuple<int, const char*> x(7, "ABC");
220 EXPECT_EQ(7, x.get<0>());
221 EXPECT_STREQ("ABC", x.get<1>());
222 }
223
TEST(CompressedTupleTest,MixClassAndNonClass)224 TEST(CompressedTupleTest, MixClassAndNonClass) {
225 CompressedTuple<int, const char*, Empty<0>, NotEmpty<double>> x(7, "ABC", {},
226 {1.25});
227 struct Mock {
228 int v;
229 const char* p;
230 double d;
231 };
232 EXPECT_EQ(sizeof(x), sizeof(Mock));
233 EXPECT_EQ(7, x.get<0>());
234 EXPECT_STREQ("ABC", x.get<1>());
235 EXPECT_EQ(1.25, x.get<3>().value);
236 }
237
TEST(CompressedTupleTest,Nested)238 TEST(CompressedTupleTest, Nested) {
239 CompressedTuple<int, CompressedTuple<int>,
240 CompressedTuple<int, CompressedTuple<int>>>
241 x(1, CompressedTuple<int>(2),
242 CompressedTuple<int, CompressedTuple<int>>(3, CompressedTuple<int>(4)));
243 EXPECT_EQ(1, x.get<0>());
244 EXPECT_EQ(2, x.get<1>().get<0>());
245 EXPECT_EQ(3, x.get<2>().get<0>());
246 EXPECT_EQ(4, x.get<2>().get<1>().get<0>());
247
248 CompressedTuple<Empty<0>, Empty<0>,
249 CompressedTuple<Empty<0>, CompressedTuple<Empty<0>>>>
250 y;
251 std::set<Empty<0>*> empties{&y.get<0>(), &y.get<1>(), &y.get<2>().get<0>(),
252 &y.get<2>().get<1>().get<0>()};
253 #ifdef _MSC_VER
254 // MSVC has a bug where many instances of the same base class are layed out in
255 // the same address when using __declspec(empty_bases).
256 // This will be fixed in a future version of MSVC.
257 int expected = 1;
258 #else
259 int expected = 4;
260 #endif
261 EXPECT_EQ(expected, sizeof(y));
262 EXPECT_EQ(expected, empties.size());
263 EXPECT_EQ(sizeof(y), sizeof(Empty<0>) * empties.size());
264
265 EXPECT_EQ(4 * sizeof(char),
266 sizeof(CompressedTuple<CompressedTuple<char, char>,
267 CompressedTuple<char, char>>));
268 EXPECT_TRUE((std::is_empty<CompressedTuple<Empty<0>, Empty<1>>>::value));
269
270 // Make sure everything still works when things are nested.
271 struct CT_Empty : CompressedTuple<Empty<0>> {};
272 CompressedTuple<Empty<0>, CT_Empty> nested_empty;
273 auto contained = nested_empty.get<0>();
274 auto nested = nested_empty.get<1>().get<0>();
275 EXPECT_TRUE((std::is_same<decltype(contained), decltype(nested)>::value));
276 }
277
TEST(CompressedTupleTest,Reference)278 TEST(CompressedTupleTest, Reference) {
279 int i = 7;
280 std::string s = "Very long string that goes in the heap";
281 CompressedTuple<int, int&, std::string, std::string&> x(i, i, s, s);
282
283 // Sanity check. We should have not moved from `s`
284 EXPECT_EQ(s, "Very long string that goes in the heap");
285
286 EXPECT_EQ(x.get<0>(), x.get<1>());
287 EXPECT_NE(&x.get<0>(), &x.get<1>());
288 EXPECT_EQ(&x.get<1>(), &i);
289
290 EXPECT_EQ(x.get<2>(), x.get<3>());
291 EXPECT_NE(&x.get<2>(), &x.get<3>());
292 EXPECT_EQ(&x.get<3>(), &s);
293 }
294
TEST(CompressedTupleTest,NoElements)295 TEST(CompressedTupleTest, NoElements) {
296 CompressedTuple<> x;
297 static_cast<void>(x); // Silence -Wunused-variable.
298 EXPECT_TRUE(std::is_empty<CompressedTuple<>>::value);
299 }
300
TEST(CompressedTupleTest,MoveOnlyElements)301 TEST(CompressedTupleTest, MoveOnlyElements) {
302 CompressedTuple<std::unique_ptr<std::string>> str_tup(
303 absl::make_unique<std::string>("str"));
304
305 CompressedTuple<CompressedTuple<std::unique_ptr<std::string>>,
306 std::unique_ptr<int>>
307 x(std::move(str_tup), absl::make_unique<int>(5));
308
309 EXPECT_EQ(*x.get<0>().get<0>(), "str");
310 EXPECT_EQ(*x.get<1>(), 5);
311
312 std::unique_ptr<std::string> x0 = std::move(x.get<0>()).get<0>();
313 std::unique_ptr<int> x1 = std::move(x).get<1>();
314
315 EXPECT_EQ(*x0, "str");
316 EXPECT_EQ(*x1, 5);
317 }
318
TEST(CompressedTupleTest,MoveConstructionMoveOnlyElements)319 TEST(CompressedTupleTest, MoveConstructionMoveOnlyElements) {
320 CompressedTuple<std::unique_ptr<std::string>> base(
321 absl::make_unique<std::string>("str"));
322 EXPECT_EQ(*base.get<0>(), "str");
323
324 CompressedTuple<std::unique_ptr<std::string>> copy(std::move(base));
325 EXPECT_EQ(*copy.get<0>(), "str");
326 }
327
TEST(CompressedTupleTest,AnyElements)328 TEST(CompressedTupleTest, AnyElements) {
329 any a(std::string("str"));
330 CompressedTuple<any, any&> x(any(5), a);
331 EXPECT_EQ(absl::any_cast<int>(x.get<0>()), 5);
332 EXPECT_EQ(absl::any_cast<std::string>(x.get<1>()), "str");
333
334 a = 0.5f;
335 EXPECT_EQ(absl::any_cast<float>(x.get<1>()), 0.5);
336 }
337
TEST(CompressedTupleTest,Constexpr)338 TEST(CompressedTupleTest, Constexpr) {
339 struct NonTrivialStruct {
340 constexpr NonTrivialStruct() = default;
341 constexpr int value() const { return v; }
342 int v = 5;
343 };
344 struct TrivialStruct {
345 TrivialStruct() = default;
346 constexpr int value() const { return v; }
347 int v;
348 };
349 constexpr CompressedTuple<int, double, CompressedTuple<int>, Empty<0>> x(
350 7, 1.25, CompressedTuple<int>(5), {});
351 constexpr int x0 = x.get<0>();
352 constexpr double x1 = x.get<1>();
353 constexpr int x2 = x.get<2>().get<0>();
354 constexpr CallType x3 = x.get<3>().value();
355
356 EXPECT_EQ(x0, 7);
357 EXPECT_EQ(x1, 1.25);
358 EXPECT_EQ(x2, 5);
359 EXPECT_EQ(x3, CallType::kConstRef);
360
361 #if !defined(__GNUC__) || defined(__clang__) || __GNUC__ > 4
362 constexpr CompressedTuple<Empty<0>, TrivialStruct, int> trivial = {};
363 constexpr CallType trivial0 = trivial.get<0>().value();
364 constexpr int trivial1 = trivial.get<1>().value();
365 constexpr int trivial2 = trivial.get<2>();
366
367 EXPECT_EQ(trivial0, CallType::kConstRef);
368 EXPECT_EQ(trivial1, 0);
369 EXPECT_EQ(trivial2, 0);
370 #endif
371
372 constexpr CompressedTuple<Empty<0>, NonTrivialStruct, absl::optional<int>>
373 non_trivial = {};
374 constexpr CallType non_trivial0 = non_trivial.get<0>().value();
375 constexpr int non_trivial1 = non_trivial.get<1>().value();
376 constexpr absl::optional<int> non_trivial2 = non_trivial.get<2>();
377
378 EXPECT_EQ(non_trivial0, CallType::kConstRef);
379 EXPECT_EQ(non_trivial1, 5);
380 EXPECT_EQ(non_trivial2, absl::nullopt);
381
382 static constexpr char data[] = "DEF";
383 constexpr CompressedTuple<const char*> z(data);
384 constexpr const char* z1 = z.get<0>();
385 EXPECT_EQ(std::string(z1), std::string(data));
386
387 #if defined(__clang__)
388 // An apparent bug in earlier versions of gcc claims these are ambiguous.
389 constexpr int x2m = absl::move(x.get<2>()).get<0>();
390 constexpr CallType x3m = absl::move(x).get<3>().value();
391 EXPECT_EQ(x2m, 5);
392 EXPECT_EQ(x3m, CallType::kConstMove);
393 #endif
394 }
395
396 #if defined(__clang__) || defined(__GNUC__)
TEST(CompressedTupleTest,EmptyFinalClass)397 TEST(CompressedTupleTest, EmptyFinalClass) {
398 struct S final {
399 int f() const { return 5; }
400 };
401 CompressedTuple<S> x;
402 EXPECT_EQ(x.get<0>().f(), 5);
403 }
404 #endif
405
406 } // namespace
407 } // namespace container_internal
408 ABSL_NAMESPACE_END
409 } // namespace absl
410