1 // Copyright 2019 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/inlined_vector.h"
16
17 #include "absl/base/config.h"
18
19 #if defined(ABSL_HAVE_EXCEPTIONS)
20
21 #include <array>
22 #include <initializer_list>
23 #include <iterator>
24 #include <memory>
25 #include <utility>
26
27 #include "gtest/gtest.h"
28 #include "absl/base/internal/exception_safety_testing.h"
29
30 namespace {
31
32 constexpr size_t kInlinedCapacity = 4;
33 constexpr size_t kLargeSize = kInlinedCapacity * 2;
34 constexpr size_t kSmallSize = kInlinedCapacity / 2;
35
36 using Thrower = testing::ThrowingValue<>;
37 using MovableThrower = testing::ThrowingValue<testing::TypeSpec::kNoThrowMove>;
38 using ThrowAlloc = testing::ThrowingAllocator<Thrower>;
39
40 using ThrowerVec = absl::InlinedVector<Thrower, kInlinedCapacity>;
41 using MovableThrowerVec = absl::InlinedVector<MovableThrower, kInlinedCapacity>;
42
43 using ThrowAllocThrowerVec =
44 absl::InlinedVector<Thrower, kInlinedCapacity, ThrowAlloc>;
45 using ThrowAllocMovableThrowerVec =
46 absl::InlinedVector<MovableThrower, kInlinedCapacity, ThrowAlloc>;
47
48 // In GCC, if an element of a `std::initializer_list` throws during construction
49 // the elements that were constructed before it are not destroyed. This causes
50 // incorrect exception safety test failures. Thus, `testing::nothrow_ctor` is
51 // required. See: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66139
52 #define ABSL_INTERNAL_MAKE_INIT_LIST(T, N) \
53 (N > kInlinedCapacity \
54 ? std::initializer_list<T>{T(0, testing::nothrow_ctor), \
55 T(1, testing::nothrow_ctor), \
56 T(2, testing::nothrow_ctor), \
57 T(3, testing::nothrow_ctor), \
58 T(4, testing::nothrow_ctor), \
59 T(5, testing::nothrow_ctor), \
60 T(6, testing::nothrow_ctor), \
61 T(7, testing::nothrow_ctor)} \
62 \
63 : std::initializer_list<T>{T(0, testing::nothrow_ctor), \
64 T(1, testing::nothrow_ctor)})
65 static_assert(kLargeSize == 8, "Must update ABSL_INTERNAL_MAKE_INIT_LIST(...)");
66 static_assert(kSmallSize == 2, "Must update ABSL_INTERNAL_MAKE_INIT_LIST(...)");
67
68 template <typename TheVecT, size_t... TheSizes>
69 class TestParams {
70 public:
71 using VecT = TheVecT;
GetSizeAt(size_t i)72 constexpr static size_t GetSizeAt(size_t i) { return kSizes[1 + i]; }
73
74 private:
75 constexpr static size_t kSizes[1 + sizeof...(TheSizes)] = {1, TheSizes...};
76 };
77
78 using NoSizeTestParams =
79 ::testing::Types<TestParams<ThrowerVec>, TestParams<MovableThrowerVec>,
80 TestParams<ThrowAllocThrowerVec>,
81 TestParams<ThrowAllocMovableThrowerVec>>;
82
83 using OneSizeTestParams =
84 ::testing::Types<TestParams<ThrowerVec, kLargeSize>,
85 TestParams<ThrowerVec, kSmallSize>,
86 TestParams<MovableThrowerVec, kLargeSize>,
87 TestParams<MovableThrowerVec, kSmallSize>,
88 TestParams<ThrowAllocThrowerVec, kLargeSize>,
89 TestParams<ThrowAllocThrowerVec, kSmallSize>,
90 TestParams<ThrowAllocMovableThrowerVec, kLargeSize>,
91 TestParams<ThrowAllocMovableThrowerVec, kSmallSize>>;
92
93 using TwoSizeTestParams = ::testing::Types<
94 TestParams<ThrowerVec, kLargeSize, kLargeSize>,
95 TestParams<ThrowerVec, kLargeSize, kSmallSize>,
96 TestParams<ThrowerVec, kSmallSize, kLargeSize>,
97 TestParams<ThrowerVec, kSmallSize, kSmallSize>,
98 TestParams<MovableThrowerVec, kLargeSize, kLargeSize>,
99 TestParams<MovableThrowerVec, kLargeSize, kSmallSize>,
100 TestParams<MovableThrowerVec, kSmallSize, kLargeSize>,
101 TestParams<MovableThrowerVec, kSmallSize, kSmallSize>,
102 TestParams<ThrowAllocThrowerVec, kLargeSize, kLargeSize>,
103 TestParams<ThrowAllocThrowerVec, kLargeSize, kSmallSize>,
104 TestParams<ThrowAllocThrowerVec, kSmallSize, kLargeSize>,
105 TestParams<ThrowAllocThrowerVec, kSmallSize, kSmallSize>,
106 TestParams<ThrowAllocMovableThrowerVec, kLargeSize, kLargeSize>,
107 TestParams<ThrowAllocMovableThrowerVec, kLargeSize, kSmallSize>,
108 TestParams<ThrowAllocMovableThrowerVec, kSmallSize, kLargeSize>,
109 TestParams<ThrowAllocMovableThrowerVec, kSmallSize, kSmallSize>>;
110
111 template <typename>
112 struct NoSizeTest : ::testing::Test {};
113 TYPED_TEST_SUITE(NoSizeTest, NoSizeTestParams);
114
115 template <typename>
116 struct OneSizeTest : ::testing::Test {};
117 TYPED_TEST_SUITE(OneSizeTest, OneSizeTestParams);
118
119 template <typename>
120 struct TwoSizeTest : ::testing::Test {};
121 TYPED_TEST_SUITE(TwoSizeTest, TwoSizeTestParams);
122
123 template <typename VecT>
InlinedVectorInvariants(VecT * vec)124 bool InlinedVectorInvariants(VecT* vec) {
125 if (*vec != *vec) return false;
126 if (vec->size() > vec->capacity()) return false;
127 if (vec->size() > vec->max_size()) return false;
128 if (vec->capacity() > vec->max_size()) return false;
129 if (vec->data() != std::addressof(vec->at(0))) return false;
130 if (vec->data() != vec->begin()) return false;
131 if (*vec->data() != *vec->begin()) return false;
132 if (vec->begin() > vec->end()) return false;
133 if ((vec->end() - vec->begin()) != vec->size()) return false;
134 if (std::distance(vec->begin(), vec->end()) != vec->size()) return false;
135 return true;
136 }
137
138 // Function that always returns false is correct, but refactoring is required
139 // for clarity. It's needed to express that, as a contract, certain operations
140 // should not throw at all. Execution of this function means an exception was
141 // thrown and thus the test should fail.
142 // TODO(johnsoncj): Add `testing::NoThrowGuarantee` to the framework
143 template <typename VecT>
NoThrowGuarantee(VecT *)144 bool NoThrowGuarantee(VecT* /* vec */) {
145 return false;
146 }
147
TYPED_TEST(NoSizeTest,DefaultConstructor)148 TYPED_TEST(NoSizeTest, DefaultConstructor) {
149 using VecT = typename TypeParam::VecT;
150 using allocator_type = typename VecT::allocator_type;
151
152 testing::TestThrowingCtor<VecT>();
153
154 testing::TestThrowingCtor<VecT>(allocator_type{});
155 }
156
TYPED_TEST(OneSizeTest,SizeConstructor)157 TYPED_TEST(OneSizeTest, SizeConstructor) {
158 using VecT = typename TypeParam::VecT;
159 using allocator_type = typename VecT::allocator_type;
160 constexpr static auto size = TypeParam::GetSizeAt(0);
161
162 testing::TestThrowingCtor<VecT>(size);
163
164 testing::TestThrowingCtor<VecT>(size, allocator_type{});
165 }
166
TYPED_TEST(OneSizeTest,SizeRefConstructor)167 TYPED_TEST(OneSizeTest, SizeRefConstructor) {
168 using VecT = typename TypeParam::VecT;
169 using value_type = typename VecT::value_type;
170 using allocator_type = typename VecT::allocator_type;
171 constexpr static auto size = TypeParam::GetSizeAt(0);
172
173 testing::TestThrowingCtor<VecT>(size, value_type{});
174
175 testing::TestThrowingCtor<VecT>(size, value_type{}, allocator_type{});
176 }
177
TYPED_TEST(OneSizeTest,InitializerListConstructor)178 TYPED_TEST(OneSizeTest, InitializerListConstructor) {
179 using VecT = typename TypeParam::VecT;
180 using value_type = typename VecT::value_type;
181 using allocator_type = typename VecT::allocator_type;
182 constexpr static auto size = TypeParam::GetSizeAt(0);
183
184 testing::TestThrowingCtor<VecT>(
185 ABSL_INTERNAL_MAKE_INIT_LIST(value_type, size));
186
187 testing::TestThrowingCtor<VecT>(
188 ABSL_INTERNAL_MAKE_INIT_LIST(value_type, size), allocator_type{});
189 }
190
TYPED_TEST(OneSizeTest,RangeConstructor)191 TYPED_TEST(OneSizeTest, RangeConstructor) {
192 using VecT = typename TypeParam::VecT;
193 using value_type = typename VecT::value_type;
194 using allocator_type = typename VecT::allocator_type;
195 constexpr static auto size = TypeParam::GetSizeAt(0);
196
197 std::array<value_type, size> arr{};
198
199 testing::TestThrowingCtor<VecT>(arr.begin(), arr.end());
200
201 testing::TestThrowingCtor<VecT>(arr.begin(), arr.end(), allocator_type{});
202 }
203
TYPED_TEST(OneSizeTest,CopyConstructor)204 TYPED_TEST(OneSizeTest, CopyConstructor) {
205 using VecT = typename TypeParam::VecT;
206 using allocator_type = typename VecT::allocator_type;
207 constexpr static auto size = TypeParam::GetSizeAt(0);
208
209 VecT other_vec{size};
210
211 testing::TestThrowingCtor<VecT>(other_vec);
212
213 testing::TestThrowingCtor<VecT>(other_vec, allocator_type{});
214 }
215
TYPED_TEST(OneSizeTest,MoveConstructor)216 TYPED_TEST(OneSizeTest, MoveConstructor) {
217 using VecT = typename TypeParam::VecT;
218 using allocator_type = typename VecT::allocator_type;
219 constexpr static auto size = TypeParam::GetSizeAt(0);
220
221 if (!absl::allocator_is_nothrow<allocator_type>::value) {
222 testing::TestThrowingCtor<VecT>(VecT{size});
223
224 testing::TestThrowingCtor<VecT>(VecT{size}, allocator_type{});
225 }
226 }
227
TYPED_TEST(TwoSizeTest,Assign)228 TYPED_TEST(TwoSizeTest, Assign) {
229 using VecT = typename TypeParam::VecT;
230 using value_type = typename VecT::value_type;
231 constexpr static auto from_size = TypeParam::GetSizeAt(0);
232 constexpr static auto to_size = TypeParam::GetSizeAt(1);
233
234 auto tester = testing::MakeExceptionSafetyTester()
235 .WithInitialValue(VecT{from_size})
236 .WithContracts(InlinedVectorInvariants<VecT>);
237
238 EXPECT_TRUE(tester.Test([](VecT* vec) {
239 *vec = ABSL_INTERNAL_MAKE_INIT_LIST(value_type, to_size);
240 }));
241
242 EXPECT_TRUE(tester.Test([](VecT* vec) {
243 VecT other_vec{to_size};
244 *vec = other_vec;
245 }));
246
247 EXPECT_TRUE(tester.Test([](VecT* vec) {
248 VecT other_vec{to_size};
249 *vec = std::move(other_vec);
250 }));
251
252 EXPECT_TRUE(tester.Test([](VecT* vec) {
253 value_type val{};
254 vec->assign(to_size, val);
255 }));
256
257 EXPECT_TRUE(tester.Test([](VecT* vec) {
258 vec->assign(ABSL_INTERNAL_MAKE_INIT_LIST(value_type, to_size));
259 }));
260
261 EXPECT_TRUE(tester.Test([](VecT* vec) {
262 std::array<value_type, to_size> arr{};
263 vec->assign(arr.begin(), arr.end());
264 }));
265 }
266
TYPED_TEST(TwoSizeTest,Resize)267 TYPED_TEST(TwoSizeTest, Resize) {
268 using VecT = typename TypeParam::VecT;
269 using value_type = typename VecT::value_type;
270 constexpr static auto from_size = TypeParam::GetSizeAt(0);
271 constexpr static auto to_size = TypeParam::GetSizeAt(1);
272
273 auto tester = testing::MakeExceptionSafetyTester()
274 .WithInitialValue(VecT{from_size})
275 .WithContracts(InlinedVectorInvariants<VecT>,
276 testing::strong_guarantee);
277
278 EXPECT_TRUE(tester.Test([](VecT* vec) {
279 vec->resize(to_size); //
280 }));
281
282 EXPECT_TRUE(tester.Test([](VecT* vec) {
283 vec->resize(to_size, value_type{}); //
284 }));
285 }
286
TYPED_TEST(OneSizeTest,Insert)287 TYPED_TEST(OneSizeTest, Insert) {
288 using VecT = typename TypeParam::VecT;
289 using value_type = typename VecT::value_type;
290 constexpr static auto from_size = TypeParam::GetSizeAt(0);
291
292 auto tester = testing::MakeExceptionSafetyTester()
293 .WithInitialValue(VecT{from_size})
294 .WithContracts(InlinedVectorInvariants<VecT>);
295
296 EXPECT_TRUE(tester.Test([](VecT* vec) {
297 auto it = vec->begin();
298 vec->insert(it, value_type{});
299 }));
300 EXPECT_TRUE(tester.Test([](VecT* vec) {
301 auto it = vec->begin() + (vec->size() / 2);
302 vec->insert(it, value_type{});
303 }));
304 EXPECT_TRUE(tester.Test([](VecT* vec) {
305 auto it = vec->end();
306 vec->insert(it, value_type{});
307 }));
308 }
309
TYPED_TEST(TwoSizeTest,Insert)310 TYPED_TEST(TwoSizeTest, Insert) {
311 using VecT = typename TypeParam::VecT;
312 using value_type = typename VecT::value_type;
313 constexpr static auto from_size = TypeParam::GetSizeAt(0);
314 constexpr static auto count = TypeParam::GetSizeAt(1);
315
316 auto tester = testing::MakeExceptionSafetyTester()
317 .WithInitialValue(VecT{from_size})
318 .WithContracts(InlinedVectorInvariants<VecT>);
319
320 EXPECT_TRUE(tester.Test([](VecT* vec) {
321 auto it = vec->begin();
322 vec->insert(it, count, value_type{});
323 }));
324 EXPECT_TRUE(tester.Test([](VecT* vec) {
325 auto it = vec->begin() + (vec->size() / 2);
326 vec->insert(it, count, value_type{});
327 }));
328 EXPECT_TRUE(tester.Test([](VecT* vec) {
329 auto it = vec->end();
330 vec->insert(it, count, value_type{});
331 }));
332
333 EXPECT_TRUE(tester.Test([](VecT* vec) {
334 auto it = vec->begin();
335 vec->insert(it, ABSL_INTERNAL_MAKE_INIT_LIST(value_type, count));
336 }));
337 EXPECT_TRUE(tester.Test([](VecT* vec) {
338 auto it = vec->begin() + (vec->size() / 2);
339 vec->insert(it, ABSL_INTERNAL_MAKE_INIT_LIST(value_type, count));
340 }));
341 EXPECT_TRUE(tester.Test([](VecT* vec) {
342 auto it = vec->end();
343 vec->insert(it, ABSL_INTERNAL_MAKE_INIT_LIST(value_type, count));
344 }));
345
346 EXPECT_TRUE(tester.Test([](VecT* vec) {
347 auto it = vec->begin();
348 std::array<value_type, count> arr{};
349 vec->insert(it, arr.begin(), arr.end());
350 }));
351 EXPECT_TRUE(tester.Test([](VecT* vec) {
352 auto it = vec->begin() + (vec->size() / 2);
353 std::array<value_type, count> arr{};
354 vec->insert(it, arr.begin(), arr.end());
355 }));
356 EXPECT_TRUE(tester.Test([](VecT* vec) {
357 auto it = vec->end();
358 std::array<value_type, count> arr{};
359 vec->insert(it, arr.begin(), arr.end());
360 }));
361 }
362
TYPED_TEST(OneSizeTest,EmplaceBack)363 TYPED_TEST(OneSizeTest, EmplaceBack) {
364 using VecT = typename TypeParam::VecT;
365 constexpr static auto size = TypeParam::GetSizeAt(0);
366
367 // For testing calls to `emplace_back(...)` that reallocate.
368 VecT full_vec{size};
369 full_vec.resize(full_vec.capacity());
370
371 // For testing calls to `emplace_back(...)` that don't reallocate.
372 VecT nonfull_vec{size};
373 nonfull_vec.reserve(size + 1);
374
375 auto tester = testing::MakeExceptionSafetyTester().WithContracts(
376 InlinedVectorInvariants<VecT>);
377
378 EXPECT_TRUE(tester.WithInitialValue(nonfull_vec).Test([](VecT* vec) {
379 vec->emplace_back();
380 }));
381
382 EXPECT_TRUE(tester.WithInitialValue(full_vec).Test(
383 [](VecT* vec) { vec->emplace_back(); }));
384 }
385
TYPED_TEST(OneSizeTest,PopBack)386 TYPED_TEST(OneSizeTest, PopBack) {
387 using VecT = typename TypeParam::VecT;
388 constexpr static auto size = TypeParam::GetSizeAt(0);
389
390 auto tester = testing::MakeExceptionSafetyTester()
391 .WithInitialValue(VecT{size})
392 .WithContracts(NoThrowGuarantee<VecT>);
393
394 EXPECT_TRUE(tester.Test([](VecT* vec) {
395 vec->pop_back(); //
396 }));
397 }
398
TYPED_TEST(OneSizeTest,Erase)399 TYPED_TEST(OneSizeTest, Erase) {
400 using VecT = typename TypeParam::VecT;
401 constexpr static auto size = TypeParam::GetSizeAt(0);
402
403 auto tester = testing::MakeExceptionSafetyTester()
404 .WithInitialValue(VecT{size})
405 .WithContracts(InlinedVectorInvariants<VecT>);
406
407 EXPECT_TRUE(tester.Test([](VecT* vec) {
408 auto it = vec->begin();
409 vec->erase(it);
410 }));
411 EXPECT_TRUE(tester.Test([](VecT* vec) {
412 auto it = vec->begin() + (vec->size() / 2);
413 vec->erase(it);
414 }));
415 EXPECT_TRUE(tester.Test([](VecT* vec) {
416 auto it = vec->begin() + (vec->size() - 1);
417 vec->erase(it);
418 }));
419
420 EXPECT_TRUE(tester.Test([](VecT* vec) {
421 auto it = vec->begin();
422 vec->erase(it, it);
423 }));
424 EXPECT_TRUE(tester.Test([](VecT* vec) {
425 auto it = vec->begin() + (vec->size() / 2);
426 vec->erase(it, it);
427 }));
428 EXPECT_TRUE(tester.Test([](VecT* vec) {
429 auto it = vec->begin() + (vec->size() - 1);
430 vec->erase(it, it);
431 }));
432
433 EXPECT_TRUE(tester.Test([](VecT* vec) {
434 auto it = vec->begin();
435 vec->erase(it, it + 1);
436 }));
437 EXPECT_TRUE(tester.Test([](VecT* vec) {
438 auto it = vec->begin() + (vec->size() / 2);
439 vec->erase(it, it + 1);
440 }));
441 EXPECT_TRUE(tester.Test([](VecT* vec) {
442 auto it = vec->begin() + (vec->size() - 1);
443 vec->erase(it, it + 1);
444 }));
445 }
446
TYPED_TEST(OneSizeTest,Clear)447 TYPED_TEST(OneSizeTest, Clear) {
448 using VecT = typename TypeParam::VecT;
449 constexpr static auto size = TypeParam::GetSizeAt(0);
450
451 auto tester = testing::MakeExceptionSafetyTester()
452 .WithInitialValue(VecT{size})
453 .WithContracts(NoThrowGuarantee<VecT>);
454
455 EXPECT_TRUE(tester.Test([](VecT* vec) {
456 vec->clear(); //
457 }));
458 }
459
TYPED_TEST(TwoSizeTest,Reserve)460 TYPED_TEST(TwoSizeTest, Reserve) {
461 using VecT = typename TypeParam::VecT;
462 constexpr static auto from_size = TypeParam::GetSizeAt(0);
463 constexpr static auto to_capacity = TypeParam::GetSizeAt(1);
464
465 auto tester = testing::MakeExceptionSafetyTester()
466 .WithInitialValue(VecT{from_size})
467 .WithContracts(InlinedVectorInvariants<VecT>);
468
469 EXPECT_TRUE(tester.Test([](VecT* vec) { vec->reserve(to_capacity); }));
470 }
471
TYPED_TEST(OneSizeTest,ShrinkToFit)472 TYPED_TEST(OneSizeTest, ShrinkToFit) {
473 using VecT = typename TypeParam::VecT;
474 constexpr static auto size = TypeParam::GetSizeAt(0);
475
476 auto tester = testing::MakeExceptionSafetyTester()
477 .WithInitialValue(VecT{size})
478 .WithContracts(InlinedVectorInvariants<VecT>);
479
480 EXPECT_TRUE(tester.Test([](VecT* vec) {
481 vec->shrink_to_fit(); //
482 }));
483 }
484
TYPED_TEST(TwoSizeTest,Swap)485 TYPED_TEST(TwoSizeTest, Swap) {
486 using VecT = typename TypeParam::VecT;
487 constexpr static auto from_size = TypeParam::GetSizeAt(0);
488 constexpr static auto to_size = TypeParam::GetSizeAt(1);
489
490 auto tester = testing::MakeExceptionSafetyTester()
491 .WithInitialValue(VecT{from_size})
492 .WithContracts(InlinedVectorInvariants<VecT>);
493
494 EXPECT_TRUE(tester.Test([](VecT* vec) {
495 VecT other_vec{to_size};
496 vec->swap(other_vec);
497 }));
498
499 EXPECT_TRUE(tester.Test([](VecT* vec) {
500 using std::swap;
501 VecT other_vec{to_size};
502 swap(*vec, other_vec);
503 }));
504 }
505
506 } // namespace
507
508 #endif // defined(ABSL_HAVE_EXCEPTIONS)
509