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