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