| 1 |
//===- llvm/unittest/ADT/SmallVectorTest.cpp ------------------------------===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// SmallVector unit tests. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
|
| 13 |
#include "llvm/ADT/SmallVector.h" |
| 14 |
#include "llvm/ADT/ArrayRef.h" |
| 15 |
#include "llvm/Support/Compiler.h" |
| 16 |
#include "gtest/gtest.h" |
| 17 |
#include <list> |
| 18 |
#include <stdarg.h> |
| 19 |
|
| 20 |
using namespace llvm; |
| 21 |
|
| 22 |
namespace { |
| 23 |
|
| 24 |
/// A helper class that counts the total number of constructor and |
| 25 |
/// destructor calls. |
| 26 |
class Constructable { |
| 27 |
private: |
| 28 |
static int numConstructorCalls; |
| 29 |
static int numMoveConstructorCalls; |
| 30 |
static int numCopyConstructorCalls; |
| 31 |
static int numDestructorCalls; |
| 32 |
static int numAssignmentCalls; |
| 33 |
static int numMoveAssignmentCalls; |
| 34 |
static int numCopyAssignmentCalls; |
| 35 |
|
| 36 |
bool constructed; |
| 37 |
int value; |
| 38 |
|
| 39 |
public: |
| 40 |
Constructable() : constructed(true), value(0) { |
| 41 |
++numConstructorCalls; |
| 42 |
} |
| 43 |
|
| 44 |
Constructable(int val) : constructed(true), value(val) { |
| 45 |
++numConstructorCalls; |
| 46 |
} |
| 47 |
|
| 48 |
Constructable(const Constructable & src) : constructed(true) { |
| 49 |
value = src.value; |
| 50 |
++numConstructorCalls; |
| 51 |
++numCopyConstructorCalls; |
| 52 |
} |
| 53 |
|
| 54 |
Constructable(Constructable && src) : constructed(true) { |
| 55 |
value = src.value; |
| 56 |
src.value = 0; |
| 57 |
++numConstructorCalls; |
| 58 |
++numMoveConstructorCalls; |
| 59 |
} |
| 60 |
|
| 61 |
~Constructable() { |
| 62 |
EXPECT_TRUE(constructed); |
| 63 |
++numDestructorCalls; |
| 64 |
constructed = false; |
| 65 |
} |
| 66 |
|
| 67 |
Constructable & operator=(const Constructable & src) { |
| 68 |
EXPECT_TRUE(constructed); |
| 69 |
value = src.value; |
| 70 |
++numAssignmentCalls; |
| 71 |
++numCopyAssignmentCalls; |
| 72 |
return *this; |
| 73 |
} |
| 74 |
|
| 75 |
Constructable & operator=(Constructable && src) { |
| 76 |
EXPECT_TRUE(constructed); |
| 77 |
value = src.value; |
| 78 |
src.value = 0; |
| 79 |
++numAssignmentCalls; |
| 80 |
++numMoveAssignmentCalls; |
| 81 |
return *this; |
| 82 |
} |
| 83 |
|
| 84 |
int getValue() const { |
| 85 |
return abs(value); |
| 86 |
} |
| 87 |
|
| 88 |
static void reset() { |
| 89 |
numConstructorCalls = 0; |
| 90 |
numMoveConstructorCalls = 0; |
| 91 |
numCopyConstructorCalls = 0; |
| 92 |
numDestructorCalls = 0; |
| 93 |
numAssignmentCalls = 0; |
| 94 |
numMoveAssignmentCalls = 0; |
| 95 |
numCopyAssignmentCalls = 0; |
| 96 |
} |
| 97 |
|
| 98 |
static int getNumConstructorCalls() { |
| 99 |
return numConstructorCalls; |
| 100 |
} |
| 101 |
|
| 102 |
static int getNumMoveConstructorCalls() { |
| 103 |
return numMoveConstructorCalls; |
| 104 |
} |
| 105 |
|
| 106 |
static int getNumCopyConstructorCalls() { |
| 107 |
return numCopyConstructorCalls; |
| 108 |
} |
| 109 |
|
| 110 |
static int getNumDestructorCalls() { |
| 111 |
return numDestructorCalls; |
| 112 |
} |
| 113 |
|
| 114 |
static int getNumAssignmentCalls() { |
| 115 |
return numAssignmentCalls; |
| 116 |
} |
| 117 |
|
| 118 |
static int getNumMoveAssignmentCalls() { |
| 119 |
return numMoveAssignmentCalls; |
| 120 |
} |
| 121 |
|
| 122 |
static int getNumCopyAssignmentCalls() { |
| 123 |
return numCopyAssignmentCalls; |
| 124 |
} |
| 125 |
|
| 126 |
friend bool operator==(const Constructable &c0, const Constructable &c1) { |
| 127 |
return c0.getValue() == c1.getValue(); |
| 128 |
} |
| 129 |
|
| 130 |
friend bool LLVM_ATTRIBUTE_UNUSED operator!=(const Constructable &c0, |
| 131 |
const Constructable &c1) { |
| 132 |
return c0.getValue() != c1.getValue(); |
| 133 |
} |
| 134 |
|
| 135 |
friend bool operator<(const Constructable &c0, const Constructable &c1) { |
| 136 |
return c0.getValue() < c1.getValue(); |
| 137 |
} |
| 138 |
friend bool LLVM_ATTRIBUTE_UNUSED operator<=(const Constructable &c0, |
| 139 |
const Constructable &c1) { |
| 140 |
return c0.getValue() <= c1.getValue(); |
| 141 |
} |
| 142 |
friend bool LLVM_ATTRIBUTE_UNUSED operator>(const Constructable &c0, |
| 143 |
const Constructable &c1) { |
| 144 |
return c0.getValue() > c1.getValue(); |
| 145 |
} |
| 146 |
friend bool LLVM_ATTRIBUTE_UNUSED operator>=(const Constructable &c0, |
| 147 |
const Constructable &c1) { |
| 148 |
return c0.getValue() >= c1.getValue(); |
| 149 |
} |
| 150 |
}; |
| 151 |
|
| 152 |
int Constructable::numConstructorCalls; |
| 153 |
int Constructable::numCopyConstructorCalls; |
| 154 |
int Constructable::numMoveConstructorCalls; |
| 155 |
int Constructable::numDestructorCalls; |
| 156 |
int Constructable::numAssignmentCalls; |
| 157 |
int Constructable::numCopyAssignmentCalls; |
| 158 |
int Constructable::numMoveAssignmentCalls; |
| 159 |
|
| 160 |
struct NonCopyable { |
| 161 |
NonCopyable() {} |
| 162 |
NonCopyable(NonCopyable &&) {} |
| 163 |
NonCopyable &operator=(NonCopyable &&) { return *this; } |
| 164 |
private: |
| 165 |
NonCopyable(const NonCopyable &) = delete; |
| 166 |
NonCopyable &operator=(const NonCopyable &) = delete; |
| 167 |
}; |
| 168 |
|
| 169 |
LLVM_ATTRIBUTE_USED void CompileTest() { |
| 170 |
SmallVector<NonCopyable, 0> V; |
| 171 |
V.resize(42); |
| 172 |
} |
| 173 |
|
| 174 |
// Assert that v contains the specified values, in order. |
| 175 |
template <typename VectorT> |
| 176 |
void assertValuesInOrder(VectorT &v, size_t size, ...) { |
| 177 |
EXPECT_EQ(size, v.size()); |
| 178 |
|
| 179 |
va_list ap; |
| 180 |
va_start(ap, size); |
| 181 |
for (size_t i = 0; i < size; ++i) { |
| 182 |
int value = va_arg(ap, int); |
| 183 |
EXPECT_EQ(value, v[i].getValue()); |
| 184 |
} |
| 185 |
|
| 186 |
va_end(ap); |
| 187 |
} |
| 188 |
|
| 189 |
template <typename VectorT> void assertEmpty(VectorT &v) { |
| 190 |
// Size tests |
| 191 |
EXPECT_EQ(0u, v.size()); |
| 192 |
EXPECT_TRUE(v.empty()); |
| 193 |
|
| 194 |
// Iterator tests |
| 195 |
EXPECT_TRUE(v.begin() == v.end()); |
| 196 |
} |
| 197 |
|
| 198 |
// Generate a sequence of values to initialize the vector. |
| 199 |
template <typename VectorT> void makeSequence(VectorT &v, int start, int end) { |
| 200 |
for (int i = start; i <= end; ++i) { |
| 201 |
v.push_back(Constructable(i)); |
| 202 |
} |
| 203 |
} |
| 204 |
|
| 205 |
template <typename T, unsigned N> |
| 206 |
constexpr static unsigned NumBuiltinElts(const SmallVector<T, N> &) { |
| 207 |
return N; |
| 208 |
} |
| 209 |
|
| 210 |
class SmallVectorTestBase : public testing::Test { |
| 211 |
protected: |
| 212 |
void SetUp() override { Constructable::reset(); } |
| 213 |
}; |
| 214 |
|
| 215 |
// Test fixture class |
| 216 |
template <typename VectorT> |
| 217 |
class SmallVectorTest : public SmallVectorTestBase { |
| 218 |
protected: |
| 219 |
VectorT theVector; |
| 220 |
VectorT otherVector; |
| 221 |
}; |
| 222 |
|
| 223 |
|
| 224 |
typedef ::testing::Types<SmallVector<Constructable, 0>, |
| 225 |
SmallVector<Constructable, 1>, |
| 226 |
SmallVector<Constructable, 2>, |
| 227 |
SmallVector<Constructable, 4>, |
| 228 |
SmallVector<Constructable, 5> |
| 229 |
> SmallVectorTestTypes; |
| 230 |
TYPED_TEST_SUITE(SmallVectorTest, SmallVectorTestTypes, ); |
| 231 |
|
| 232 |
// Constructor test. |
| 233 |
TYPED_TEST(SmallVectorTest, ConstructorNonIterTest) { |
| 234 |
SCOPED_TRACE("ConstructorTest"); |
| 235 |
auto &V = this->theVector; |
| 236 |
V = SmallVector<Constructable, 2>(2, 2); |
| 237 |
assertValuesInOrder(V, 2u, 2, 2); |
| 238 |
} |
| 239 |
|
| 240 |
// Constructor test. |
| 241 |
TYPED_TEST(SmallVectorTest, ConstructorIterTest) { |
| 242 |
SCOPED_TRACE("ConstructorTest"); |
| 243 |
int arr[] = {1, 2, 3}; |
| 244 |
auto &V = this->theVector; |
| 245 |
V = SmallVector<Constructable, 4>(std::begin(arr), std::end(arr)); |
| 246 |
assertValuesInOrder(V, 3u, 1, 2, 3); |
| 247 |
} |
| 248 |
|
| 249 |
// Constructor test. |
| 250 |
TYPED_TEST(SmallVectorTest, ConstructorFromArrayRefSimpleTest) { |
| 251 |
SCOPED_TRACE("ConstructorFromArrayRefSimpleTest"); |
| 252 |
std::array<Constructable, 3> StdArray = {Constructable(1), Constructable(2), |
| 253 |
Constructable(3)}; |
| 254 |
ArrayRef<Constructable> Array = StdArray; |
| 255 |
auto &V = this->theVector; |
| 256 |
V = SmallVector<Constructable, 4>(Array); |
| 257 |
assertValuesInOrder(V, 3u, 1, 2, 3); |
| 258 |
ASSERT_EQ(NumBuiltinElts(TypeParam{}), NumBuiltinElts(V)); |
| 259 |
} |
| 260 |
|
| 261 |
// New vector test. |
| 262 |
TYPED_TEST(SmallVectorTest, EmptyVectorTest) { |
| 263 |
SCOPED_TRACE("EmptyVectorTest"); |
| 264 |
auto &V = this->theVector; |
| 265 |
assertEmpty(V); |
| 266 |
EXPECT_TRUE(V.rbegin() == V.rend()); |
| 267 |
EXPECT_EQ(0, Constructable::getNumConstructorCalls()); |
| 268 |
EXPECT_EQ(0, Constructable::getNumDestructorCalls()); |
| 269 |
} |
| 270 |
|
| 271 |
// Simple insertions and deletions. |
| 272 |
TYPED_TEST(SmallVectorTest, PushPopTest) { |
| 273 |
SCOPED_TRACE("PushPopTest"); |
| 274 |
auto &V = this->theVector; |
| 275 |
// Track whether the vector will potentially have to grow. |
| 276 |
bool RequiresGrowth = V.capacity() < 3; |
| 277 |
|
| 278 |
// Push an element |
| 279 |
V.push_back(Constructable(1)); |
| 280 |
|
| 281 |
// Size tests |
| 282 |
assertValuesInOrder(V, 1u, 1); |
| 283 |
EXPECT_FALSE(V.begin() == V.end()); |
| 284 |
EXPECT_FALSE(V.empty()); |
| 285 |
|
| 286 |
// Push another element |
| 287 |
V.push_back(Constructable(2)); |
| 288 |
assertValuesInOrder(V, 2u, 1, 2); |
| 289 |
|
| 290 |
// Insert at beginning. Reserve space to avoid reference invalidation from |
| 291 |
// V[1]. |
| 292 |
V.reserve(V.size() + 1); |
| 293 |
V.insert(V.begin(), V[1]); |
| 294 |
assertValuesInOrder(V, 3u, 2, 1, 2); |
| 295 |
|
| 296 |
// Pop one element |
| 297 |
V.pop_back(); |
| 298 |
assertValuesInOrder(V, 2u, 2, 1); |
| 299 |
|
| 300 |
// Pop remaining elements |
| 301 |
V.pop_back_n(2); |
| 302 |
assertEmpty(V); |
| 303 |
|
| 304 |
// Check number of constructor calls. Should be 2 for each list element, |
| 305 |
// one for the argument to push_back, one for the argument to insert, |
| 306 |
// and one for the list element itself. |
| 307 |
if (!RequiresGrowth) { |
| 308 |
EXPECT_EQ(5, Constructable::getNumConstructorCalls()); |
| 309 |
EXPECT_EQ(5, Constructable::getNumDestructorCalls()); |
| 310 |
} else { |
| 311 |
// If we had to grow the vector, these only have a lower bound, but should |
| 312 |
// always be equal. |
| 313 |
EXPECT_LE(5, Constructable::getNumConstructorCalls()); |
| 314 |
EXPECT_EQ(Constructable::getNumConstructorCalls(), |
| 315 |
Constructable::getNumDestructorCalls()); |
| 316 |
} |
| 317 |
} |
| 318 |
|
| 319 |
// Clear test. |
| 320 |
TYPED_TEST(SmallVectorTest, ClearTest) { |
| 321 |
SCOPED_TRACE("ClearTest"); |
| 322 |
auto &V = this->theVector; |
| 323 |
V.reserve(2); |
| 324 |
makeSequence(V, 1, 2); |
| 325 |
V.clear(); |
| 326 |
|
| 327 |
assertEmpty(V); |
| 328 |
EXPECT_EQ(4, Constructable::getNumConstructorCalls()); |
| 329 |
EXPECT_EQ(4, Constructable::getNumDestructorCalls()); |
| 330 |
} |
| 331 |
|
| 332 |
// Resize smaller test. |
| 333 |
TYPED_TEST(SmallVectorTest, ResizeShrinkTest) { |
| 334 |
SCOPED_TRACE("ResizeShrinkTest"); |
| 335 |
auto &V = this->theVector; |
| 336 |
V.reserve(3); |
| 337 |
makeSequence(V, 1, 3); |
| 338 |
V.resize(1); |
| 339 |
|
| 340 |
assertValuesInOrder(V, 1u, 1); |
| 341 |
EXPECT_EQ(6, Constructable::getNumConstructorCalls()); |
| 342 |
EXPECT_EQ(5, Constructable::getNumDestructorCalls()); |
| 343 |
} |
| 344 |
|
| 345 |
// Truncate test. |
| 346 |
TYPED_TEST(SmallVectorTest, TruncateTest) { |
| 347 |
SCOPED_TRACE("TruncateTest"); |
| 348 |
auto &V = this->theVector; |
| 349 |
V.reserve(3); |
| 350 |
makeSequence(V, 1, 3); |
| 351 |
V.truncate(1); |
| 352 |
|
| 353 |
assertValuesInOrder(V, 1u, 1); |
| 354 |
EXPECT_EQ(6, Constructable::getNumConstructorCalls()); |
| 355 |
EXPECT_EQ(5, Constructable::getNumDestructorCalls()); |
| 356 |
|
| 357 |
#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST |
| 358 |
EXPECT_DEATH(V.truncate(2), "Cannot increase size"); |
| 359 |
#endif |
| 360 |
V.truncate(1); |
| 361 |
assertValuesInOrder(V, 1u, 1); |
| 362 |
EXPECT_EQ(6, Constructable::getNumConstructorCalls()); |
| 363 |
EXPECT_EQ(5, Constructable::getNumDestructorCalls()); |
| 364 |
|
| 365 |
V.truncate(0); |
| 366 |
assertEmpty(V); |
| 367 |
EXPECT_EQ(6, Constructable::getNumConstructorCalls()); |
| 368 |
EXPECT_EQ(6, Constructable::getNumDestructorCalls()); |
| 369 |
} |
| 370 |
|
| 371 |
// Resize bigger test. |
| 372 |
TYPED_TEST(SmallVectorTest, ResizeGrowTest) { |
| 373 |
SCOPED_TRACE("ResizeGrowTest"); |
| 374 |
auto &V = this->theVector; |
| 375 |
V.resize(2); |
| 376 |
|
| 377 |
EXPECT_EQ(2, Constructable::getNumConstructorCalls()); |
| 378 |
EXPECT_EQ(0, Constructable::getNumDestructorCalls()); |
| 379 |
EXPECT_EQ(2u, V.size()); |
| 380 |
} |
| 381 |
|
| 382 |
TYPED_TEST(SmallVectorTest, ResizeWithElementsTest) { |
| 383 |
auto &V = this->theVector; |
| 384 |
V.resize(2); |
| 385 |
|
| 386 |
Constructable::reset(); |
| 387 |
|
| 388 |
V.resize(4); |
| 389 |
|
| 390 |
size_t Ctors = Constructable::getNumConstructorCalls(); |
| 391 |
EXPECT_TRUE(Ctors == 2 || Ctors == 4); |
| 392 |
size_t MoveCtors = Constructable::getNumMoveConstructorCalls(); |
| 393 |
EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2); |
| 394 |
size_t Dtors = Constructable::getNumDestructorCalls(); |
| 395 |
EXPECT_TRUE(Dtors == 0 || Dtors == 2); |
| 396 |
} |
| 397 |
|
| 398 |
// Resize with fill value. |
| 399 |
TYPED_TEST(SmallVectorTest, ResizeFillTest) { |
| 400 |
SCOPED_TRACE("ResizeFillTest"); |
| 401 |
auto &V = this->theVector; |
| 402 |
V.resize(3, Constructable(77)); |
| 403 |
assertValuesInOrder(V, 3u, 77, 77, 77); |
| 404 |
} |
| 405 |
|
| 406 |
TEST(SmallVectorTest, ResizeForOverwrite) { |
| 407 |
{ |
| 408 |
// Heap allocated storage. |
| 409 |
SmallVector<unsigned, 0> V; |
| 410 |
V.push_back(5U); |
| 411 |
V.pop_back(); |
| 412 |
V.resize_for_overwrite(V.size() + 1U); |
| 413 |
EXPECT_EQ(5U, V.back()); |
| 414 |
V.pop_back(); |
| 415 |
V.resize(V.size() + 1); |
| 416 |
EXPECT_EQ(0U, V.back()); |
| 417 |
} |
| 418 |
{ |
| 419 |
// Inline storage. |
| 420 |
SmallVector<unsigned, 2> V; |
| 421 |
V.push_back(5U); |
| 422 |
V.pop_back(); |
| 423 |
V.resize_for_overwrite(V.size() + 1U); |
| 424 |
EXPECT_EQ(5U, V.back()); |
| 425 |
V.pop_back(); |
| 426 |
V.resize(V.size() + 1); |
| 427 |
EXPECT_EQ(0U, V.back()); |
| 428 |
} |
| 429 |
} |
| 430 |
|
| 431 |
// Overflow past fixed size. |
| 432 |
TYPED_TEST(SmallVectorTest, OverflowTest) { |
| 433 |
SCOPED_TRACE("OverflowTest"); |
| 434 |
auto &V = this->theVector; |
| 435 |
// Push more elements than the fixed size. |
| 436 |
makeSequence(V, 1, 10); |
| 437 |
|
| 438 |
// Test size and values. |
| 439 |
EXPECT_EQ(10u, V.size()); |
| 440 |
for (int i = 0; i < 10; ++i) { |
| 441 |
EXPECT_EQ(i + 1, V[i].getValue()); |
| 442 |
} |
| 443 |
|
| 444 |
// Now resize back to fixed size. |
| 445 |
V.resize(1); |
| 446 |
|
| 447 |
assertValuesInOrder(V, 1u, 1); |
| 448 |
} |
| 449 |
|
| 450 |
// Iteration tests. |
| 451 |
TYPED_TEST(SmallVectorTest, IterationTest) { |
| 452 |
auto &V = this->theVector; |
| 453 |
makeSequence(V, 1, 2); |
| 454 |
|
| 455 |
// Forward Iteration |
| 456 |
typename TypeParam::iterator it = V.begin(); |
| 457 |
EXPECT_TRUE(*it == V.front()); |
| 458 |
EXPECT_TRUE(*it == V[0]); |
| 459 |
EXPECT_EQ(1, it->getValue()); |
| 460 |
++it; |
| 461 |
EXPECT_TRUE(*it == V[1]); |
| 462 |
EXPECT_TRUE(*it == V.back()); |
| 463 |
EXPECT_EQ(2, it->getValue()); |
| 464 |
++it; |
| 465 |
EXPECT_TRUE(it == V.end()); |
| 466 |
--it; |
| 467 |
EXPECT_TRUE(*it == V[1]); |
| 468 |
EXPECT_EQ(2, it->getValue()); |
| 469 |
--it; |
| 470 |
EXPECT_TRUE(*it == V[0]); |
| 471 |
EXPECT_EQ(1, it->getValue()); |
| 472 |
|
| 473 |
// Reverse Iteration |
| 474 |
typename TypeParam::reverse_iterator rit = V.rbegin(); |
| 475 |
EXPECT_TRUE(*rit == V[1]); |
| 476 |
EXPECT_EQ(2, rit->getValue()); |
| 477 |
++rit; |
| 478 |
EXPECT_TRUE(*rit == V[0]); |
| 479 |
EXPECT_EQ(1, rit->getValue()); |
| 480 |
++rit; |
| 481 |
EXPECT_TRUE(rit == V.rend()); |
| 482 |
--rit; |
| 483 |
EXPECT_TRUE(*rit == V[0]); |
| 484 |
EXPECT_EQ(1, rit->getValue()); |
| 485 |
--rit; |
| 486 |
EXPECT_TRUE(*rit == V[1]); |
| 487 |
EXPECT_EQ(2, rit->getValue()); |
| 488 |
} |
| 489 |
|
| 490 |
// Swap test. |
| 491 |
TYPED_TEST(SmallVectorTest, SwapTest) { |
| 492 |
SCOPED_TRACE("SwapTest"); |
| 493 |
auto &V = this->theVector; |
| 494 |
auto &U = this->otherVector; |
| 495 |
makeSequence(V, 1, 2); |
| 496 |
std::swap(V, U); |
| 497 |
|
| 498 |
assertEmpty(V); |
| 499 |
assertValuesInOrder(U, 2u, 1, 2); |
| 500 |
} |
| 501 |
|
| 502 |
// Append test |
| 503 |
TYPED_TEST(SmallVectorTest, AppendTest) { |
| 504 |
SCOPED_TRACE("AppendTest"); |
| 505 |
auto &V = this->theVector; |
| 506 |
auto &U = this->otherVector; |
| 507 |
makeSequence(U, 2, 3); |
| 508 |
|
| 509 |
V.push_back(Constructable(1)); |
| 510 |
V.append(U.begin(), U.end()); |
| 511 |
|
| 512 |
assertValuesInOrder(V, 3u, 1, 2, 3); |
| 513 |
} |
| 514 |
|
| 515 |
// Append repeated test |
| 516 |
TYPED_TEST(SmallVectorTest, AppendRepeatedTest) { |
| 517 |
SCOPED_TRACE("AppendRepeatedTest"); |
| 518 |
auto &V = this->theVector; |
| 519 |
V.push_back(Constructable(1)); |
| 520 |
V.append(2, Constructable(77)); |
| 521 |
assertValuesInOrder(V, 3u, 1, 77, 77); |
| 522 |
} |
| 523 |
|
| 524 |
// Append test |
| 525 |
TYPED_TEST(SmallVectorTest, AppendNonIterTest) { |
| 526 |
SCOPED_TRACE("AppendRepeatedTest"); |
| 527 |
auto &V = this->theVector; |
| 528 |
V.push_back(Constructable(1)); |
| 529 |
V.append(2, 7); |
| 530 |
assertValuesInOrder(V, 3u, 1, 7, 7); |
| 531 |
} |
| 532 |
|
| 533 |
struct output_iterator { |
| 534 |
typedef std::output_iterator_tag iterator_category; |
| 535 |
typedef int value_type; |
| 536 |
typedef int difference_type; |
| 537 |
typedef value_type *pointer; |
| 538 |
typedef value_type &reference; |
| 539 |
operator int() { return 2; } |
| 540 |
operator Constructable() { return 7; } |
| 541 |
}; |
| 542 |
|
| 543 |
TYPED_TEST(SmallVectorTest, AppendRepeatedNonForwardIterator) { |
| 544 |
SCOPED_TRACE("AppendRepeatedTest"); |
| 545 |
auto &V = this->theVector; |
| 546 |
V.push_back(Constructable(1)); |
| 547 |
V.append(output_iterator(), output_iterator()); |
| 548 |
assertValuesInOrder(V, 3u, 1, 7, 7); |
| 549 |
} |
| 550 |
|
| 551 |
TYPED_TEST(SmallVectorTest, AppendSmallVector) { |
| 552 |
SCOPED_TRACE("AppendSmallVector"); |
| 553 |
auto &V = this->theVector; |
| 554 |
SmallVector<Constructable, 3> otherVector = {7, 7}; |
| 555 |
V.push_back(Constructable(1)); |
| 556 |
V.append(otherVector); |
| 557 |
assertValuesInOrder(V, 3u, 1, 7, 7); |
| 558 |
} |
| 559 |
|
| 560 |
// Assign test |
| 561 |
TYPED_TEST(SmallVectorTest, AssignTest) { |
| 562 |
SCOPED_TRACE("AssignTest"); |
| 563 |
auto &V = this->theVector; |
| 564 |
V.push_back(Constructable(1)); |
| 565 |
V.assign(2, Constructable(77)); |
| 566 |
assertValuesInOrder(V, 2u, 77, 77); |
| 567 |
} |
| 568 |
|
| 569 |
// Assign test |
| 570 |
TYPED_TEST(SmallVectorTest, AssignRangeTest) { |
| 571 |
SCOPED_TRACE("AssignTest"); |
| 572 |
auto &V = this->theVector; |
| 573 |
V.push_back(Constructable(1)); |
| 574 |
int arr[] = {1, 2, 3}; |
| 575 |
V.assign(std::begin(arr), std::end(arr)); |
| 576 |
assertValuesInOrder(V, 3u, 1, 2, 3); |
| 577 |
} |
| 578 |
|
| 579 |
// Assign test |
| 580 |
TYPED_TEST(SmallVectorTest, AssignNonIterTest) { |
| 581 |
SCOPED_TRACE("AssignTest"); |
| 582 |
auto &V = this->theVector; |
| 583 |
V.push_back(Constructable(1)); |
| 584 |
V.assign(2, 7); |
| 585 |
assertValuesInOrder(V, 2u, 7, 7); |
| 586 |
} |
| 587 |
|
| 588 |
TYPED_TEST(SmallVectorTest, AssignSmallVector) { |
| 589 |
SCOPED_TRACE("AssignSmallVector"); |
| 590 |
auto &V = this->theVector; |
| 591 |
SmallVector<Constructable, 3> otherVector = {7, 7}; |
| 592 |
V.push_back(Constructable(1)); |
| 593 |
V.assign(otherVector); |
| 594 |
assertValuesInOrder(V, 2u, 7, 7); |
| 595 |
} |
| 596 |
|
| 597 |
// Move-assign test |
| 598 |
TYPED_TEST(SmallVectorTest, MoveAssignTest) { |
| 599 |
SCOPED_TRACE("MoveAssignTest"); |
| 600 |
auto &V = this->theVector; |
| 601 |
auto &U = this->otherVector; |
| 602 |
// Set up our vector with a single element, but enough capacity for 4. |
| 603 |
V.reserve(4); |
| 604 |
V.push_back(Constructable(1)); |
| 605 |
|
| 606 |
// Set up the other vector with 2 elements. |
| 607 |
U.push_back(Constructable(2)); |
| 608 |
U.push_back(Constructable(3)); |
| 609 |
|
| 610 |
// Move-assign from the other vector. |
| 611 |
V = std::move(U); |
| 612 |
|
| 613 |
// Make sure we have the right result. |
| 614 |
assertValuesInOrder(V, 2u, 2, 3); |
| 615 |
|
| 616 |
// Make sure the # of constructor/destructor calls line up. There |
| 617 |
// are two live objects after clearing the other vector. |
| 618 |
U.clear(); |
| 619 |
EXPECT_EQ(Constructable::getNumConstructorCalls()-2, |
| 620 |
Constructable::getNumDestructorCalls()); |
| 621 |
|
| 622 |
// There shouldn't be any live objects any more. |
| 623 |
V.clear(); |
| 624 |
EXPECT_EQ(Constructable::getNumConstructorCalls(), |
| 625 |
Constructable::getNumDestructorCalls()); |
| 626 |
} |
| 627 |
|
| 628 |
// Erase a single element |
| 629 |
TYPED_TEST(SmallVectorTest, EraseTest) { |
| 630 |
SCOPED_TRACE("EraseTest"); |
| 631 |
auto &V = this->theVector; |
| 632 |
makeSequence(V, 1, 3); |
| 633 |
const auto &theConstVector = V; |
| 634 |
V.erase(theConstVector.begin()); |
| 635 |
assertValuesInOrder(V, 2u, 2, 3); |
| 636 |
} |
| 637 |
|
| 638 |
// Erase a range of elements |
| 639 |
TYPED_TEST(SmallVectorTest, EraseRangeTest) { |
| 640 |
SCOPED_TRACE("EraseRangeTest"); |
| 641 |
auto &V = this->theVector; |
| 642 |
makeSequence(V, 1, 3); |
| 643 |
const auto &theConstVector = V; |
| 644 |
V.erase(theConstVector.begin(), theConstVector.begin() + 2); |
| 645 |
assertValuesInOrder(V, 1u, 3); |
| 646 |
} |
| 647 |
|
| 648 |
// Insert a single element. |
| 649 |
TYPED_TEST(SmallVectorTest, InsertTest) { |
| 650 |
SCOPED_TRACE("InsertTest"); |
| 651 |
auto &V = this->theVector; |
| 652 |
makeSequence(V, 1, 3); |
| 653 |
typename TypeParam::iterator I = V.insert(V.begin() + 1, Constructable(77)); |
| 654 |
EXPECT_EQ(V.begin() + 1, I); |
| 655 |
assertValuesInOrder(V, 4u, 1, 77, 2, 3); |
| 656 |
} |
| 657 |
|
| 658 |
// Insert a copy of a single element. |
| 659 |
TYPED_TEST(SmallVectorTest, InsertCopy) { |
| 660 |
SCOPED_TRACE("InsertTest"); |
| 661 |
auto &V = this->theVector; |
| 662 |
makeSequence(V, 1, 3); |
| 663 |
Constructable C(77); |
| 664 |
typename TypeParam::iterator I = V.insert(V.begin() + 1, C); |
| 665 |
EXPECT_EQ(V.begin() + 1, I); |
| 666 |
assertValuesInOrder(V, 4u, 1, 77, 2, 3); |
| 667 |
} |
| 668 |
|
| 669 |
// Insert repeated elements. |
| 670 |
TYPED_TEST(SmallVectorTest, InsertRepeatedTest) { |
| 671 |
SCOPED_TRACE("InsertRepeatedTest"); |
| 672 |
auto &V = this->theVector; |
| 673 |
makeSequence(V, 1, 4); |
| 674 |
Constructable::reset(); |
| 675 |
auto I = V.insert(V.begin() + 1, 2, Constructable(16)); |
| 676 |
// Move construct the top element into newly allocated space, and optionally |
| 677 |
// reallocate the whole buffer, move constructing into it. |
| 678 |
// FIXME: This is inefficient, we shouldn't move things into newly allocated |
| 679 |
// space, then move them up/around, there should only be 2 or 4 move |
| 680 |
// constructions here. |
| 681 |
EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || |
| 682 |
Constructable::getNumMoveConstructorCalls() == 6); |
| 683 |
// Move assign the next two to shift them up and make a gap. |
| 684 |
EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); |
| 685 |
// Copy construct the two new elements from the parameter. |
| 686 |
EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); |
| 687 |
// All without any copy construction. |
| 688 |
EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); |
| 689 |
EXPECT_EQ(V.begin() + 1, I); |
| 690 |
assertValuesInOrder(V, 6u, 1, 16, 16, 2, 3, 4); |
| 691 |
} |
| 692 |
|
| 693 |
TYPED_TEST(SmallVectorTest, InsertRepeatedNonIterTest) { |
| 694 |
SCOPED_TRACE("InsertRepeatedTest"); |
| 695 |
auto &V = this->theVector; |
| 696 |
makeSequence(V, 1, 4); |
| 697 |
Constructable::reset(); |
| 698 |
auto I = V.insert(V.begin() + 1, 2, 7); |
| 699 |
EXPECT_EQ(V.begin() + 1, I); |
| 700 |
assertValuesInOrder(V, 6u, 1, 7, 7, 2, 3, 4); |
| 701 |
} |
| 702 |
|
| 703 |
TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) { |
| 704 |
SCOPED_TRACE("InsertRepeatedTest"); |
| 705 |
auto &V = this->theVector; |
| 706 |
makeSequence(V, 1, 4); |
| 707 |
Constructable::reset(); |
| 708 |
auto I = V.insert(V.end(), 2, Constructable(16)); |
| 709 |
// Just copy construct them into newly allocated space |
| 710 |
EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); |
| 711 |
// Move everything across if reallocation is needed. |
| 712 |
EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || |
| 713 |
Constructable::getNumMoveConstructorCalls() == 4); |
| 714 |
// Without ever moving or copying anything else. |
| 715 |
EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); |
| 716 |
EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); |
| 717 |
|
| 718 |
EXPECT_EQ(V.begin() + 4, I); |
| 719 |
assertValuesInOrder(V, 6u, 1, 2, 3, 4, 16, 16); |
| 720 |
} |
| 721 |
|
| 722 |
TYPED_TEST(SmallVectorTest, InsertRepeatedEmptyTest) { |
| 723 |
SCOPED_TRACE("InsertRepeatedTest"); |
| 724 |
auto &V = this->theVector; |
| 725 |
makeSequence(V, 10, 15); |
| 726 |
|
| 727 |
// Empty insert. |
| 728 |
EXPECT_EQ(V.end(), V.insert(V.end(), 0, Constructable(42))); |
| 729 |
EXPECT_EQ(V.begin() + 1, V.insert(V.begin() + 1, 0, Constructable(42))); |
| 730 |
} |
| 731 |
|
| 732 |
// Insert range. |
| 733 |
TYPED_TEST(SmallVectorTest, InsertRangeTest) { |
| 734 |
SCOPED_TRACE("InsertRangeTest"); |
| 735 |
auto &V = this->theVector; |
| 736 |
Constructable Arr[3] = |
| 737 |
{ Constructable(77), Constructable(77), Constructable(77) }; |
| 738 |
|
| 739 |
makeSequence(V, 1, 3); |
| 740 |
Constructable::reset(); |
| 741 |
auto I = V.insert(V.begin() + 1, Arr, Arr + 3); |
| 742 |
// Move construct the top 3 elements into newly allocated space. |
| 743 |
// Possibly move the whole sequence into new space first. |
| 744 |
// FIXME: This is inefficient, we shouldn't move things into newly allocated |
| 745 |
// space, then move them up/around, there should only be 2 or 3 move |
| 746 |
// constructions here. |
| 747 |
EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || |
| 748 |
Constructable::getNumMoveConstructorCalls() == 5); |
| 749 |
// Copy assign the lower 2 new elements into existing space. |
| 750 |
EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); |
| 751 |
// Copy construct the third element into newly allocated space. |
| 752 |
EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); |
| 753 |
EXPECT_EQ(V.begin() + 1, I); |
| 754 |
assertValuesInOrder(V, 6u, 1, 77, 77, 77, 2, 3); |
| 755 |
} |
| 756 |
|
| 757 |
|
| 758 |
TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) { |
| 759 |
SCOPED_TRACE("InsertRangeTest"); |
| 760 |
auto &V = this->theVector; |
| 761 |
Constructable Arr[3] = |
| 762 |
{ Constructable(77), Constructable(77), Constructable(77) }; |
| 763 |
|
| 764 |
makeSequence(V, 1, 3); |
| 765 |
|
| 766 |
// Insert at end. |
| 767 |
Constructable::reset(); |
| 768 |
auto I = V.insert(V.end(), Arr, Arr + 3); |
| 769 |
// Copy construct the 3 elements into new space at the top. |
| 770 |
EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls()); |
| 771 |
// Don't copy/move anything else. |
| 772 |
EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); |
| 773 |
// Reallocation might occur, causing all elements to be moved into the new |
| 774 |
// buffer. |
| 775 |
EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || |
| 776 |
Constructable::getNumMoveConstructorCalls() == 3); |
| 777 |
EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); |
| 778 |
EXPECT_EQ(V.begin() + 3, I); |
| 779 |
assertValuesInOrder(V, 6u, 1, 2, 3, 77, 77, 77); |
| 780 |
} |
| 781 |
|
| 782 |
TYPED_TEST(SmallVectorTest, InsertEmptyRangeTest) { |
| 783 |
SCOPED_TRACE("InsertRangeTest"); |
| 784 |
auto &V = this->theVector; |
| 785 |
makeSequence(V, 1, 3); |
| 786 |
|
| 787 |
// Empty insert. |
| 788 |
EXPECT_EQ(V.end(), V.insert(V.end(), V.begin(), V.begin())); |
| 789 |
EXPECT_EQ(V.begin() + 1, V.insert(V.begin() + 1, V.begin(), V.begin())); |
| 790 |
} |
| 791 |
|
| 792 |
// Comparison tests. |
| 793 |
TYPED_TEST(SmallVectorTest, ComparisonEqualityTest) { |
| 794 |
SCOPED_TRACE("ComparisonEqualityTest"); |
| 795 |
auto &V = this->theVector; |
| 796 |
auto &U = this->otherVector; |
| 797 |
makeSequence(V, 1, 3); |
| 798 |
makeSequence(U, 1, 3); |
| 799 |
|
| 800 |
EXPECT_TRUE(V == U); |
| 801 |
EXPECT_FALSE(V != U); |
| 802 |
|
| 803 |
U.clear(); |
| 804 |
makeSequence(U, 2, 4); |
| 805 |
|
| 806 |
EXPECT_FALSE(V == U); |
| 807 |
EXPECT_TRUE(V != U); |
| 808 |
} |
| 809 |
|
| 810 |
// Comparison tests. |
| 811 |
TYPED_TEST(SmallVectorTest, ComparisonLessThanTest) { |
| 812 |
SCOPED_TRACE("ComparisonLessThanTest"); |
| 813 |
auto &V = this->theVector; |
| 814 |
auto &U = this->otherVector; |
| 815 |
V = {1, 2, 4}; |
| 816 |
U = {1, 4}; |
| 817 |
|
| 818 |
EXPECT_TRUE(V < U); |
| 819 |
EXPECT_TRUE(V <= U); |
| 820 |
EXPECT_FALSE(V > U); |
| 821 |
EXPECT_FALSE(V >= U); |
| 822 |
|
| 823 |
EXPECT_FALSE(U < V); |
| 824 |
EXPECT_FALSE(U <= V); |
| 825 |
EXPECT_TRUE(U > V); |
| 826 |
EXPECT_TRUE(U >= V); |
| 827 |
|
| 828 |
U = {1, 2, 4}; |
| 829 |
|
| 830 |
EXPECT_FALSE(V < U); |
| 831 |
EXPECT_TRUE(V <= U); |
| 832 |
EXPECT_FALSE(V > U); |
| 833 |
EXPECT_TRUE(V >= U); |
| 834 |
|
| 835 |
EXPECT_FALSE(U < V); |
| 836 |
EXPECT_TRUE(U <= V); |
| 837 |
EXPECT_FALSE(U > V); |
| 838 |
EXPECT_TRUE(U >= V); |
| 839 |
} |
| 840 |
|
| 841 |
// Constant vector tests. |
| 842 |
TYPED_TEST(SmallVectorTest, ConstVectorTest) { |
| 843 |
const TypeParam constVector; |
| 844 |
|
| 845 |
EXPECT_EQ(0u, constVector.size()); |
| 846 |
EXPECT_TRUE(constVector.empty()); |
| 847 |
EXPECT_TRUE(constVector.begin() == constVector.end()); |
| 848 |
} |
| 849 |
|
| 850 |
// Direct array access. |
| 851 |
TYPED_TEST(SmallVectorTest, DirectVectorTest) { |
| 852 |
auto &V = this->theVector; |
| 853 |
EXPECT_EQ(0u, V.size()); |
| 854 |
V.reserve(4); |
| 855 |
EXPECT_LE(4u, V.capacity()); |
| 856 |
EXPECT_EQ(0, Constructable::getNumConstructorCalls()); |
| 857 |
V.push_back(1); |
| 858 |
V.push_back(2); |
| 859 |
V.push_back(3); |
| 860 |
V.push_back(4); |
| 861 |
EXPECT_EQ(4u, V.size()); |
| 862 |
EXPECT_EQ(8, Constructable::getNumConstructorCalls()); |
| 863 |
EXPECT_EQ(1, V[0].getValue()); |
| 864 |
EXPECT_EQ(2, V[1].getValue()); |
| 865 |
EXPECT_EQ(3, V[2].getValue()); |
| 866 |
EXPECT_EQ(4, V[3].getValue()); |
| 867 |
} |
| 868 |
|
| 869 |
TYPED_TEST(SmallVectorTest, IteratorTest) { |
| 870 |
auto &V = this->theVector; |
| 871 |
std::list<int> L; |
| 872 |
V.insert(V.end(), L.begin(), L.end()); |
| 873 |
} |
| 874 |
|
| 875 |
template <typename InvalidType> class DualSmallVectorsTest; |
| 876 |
|
| 877 |
template <typename VectorT1, typename VectorT2> |
| 878 |
class DualSmallVectorsTest<std::pair<VectorT1, VectorT2>> : public SmallVectorTestBase { |
| 879 |
protected: |
| 880 |
VectorT1 theVector; |
| 881 |
VectorT2 otherVector; |
| 882 |
}; |
| 883 |
|
| 884 |
typedef ::testing::Types< |
| 885 |
// Small mode -> Small mode. |
| 886 |
std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 4>>, |
| 887 |
// Small mode -> Big mode. |
| 888 |
std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 2>>, |
| 889 |
// Big mode -> Small mode. |
| 890 |
std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 4>>, |
| 891 |
// Big mode -> Big mode. |
| 892 |
std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 2>> |
| 893 |
> DualSmallVectorTestTypes; |
| 894 |
|
| 895 |
TYPED_TEST_SUITE(DualSmallVectorsTest, DualSmallVectorTestTypes, ); |
| 896 |
|
| 897 |
TYPED_TEST(DualSmallVectorsTest, MoveAssignment) { |
| 898 |
SCOPED_TRACE("MoveAssignTest-DualVectorTypes"); |
| 899 |
auto &V = this->theVector; |
| 900 |
auto &U = this->otherVector; |
| 901 |
// Set up our vector with four elements. |
| 902 |
for (unsigned I = 0; I < 4; ++I) |
| 903 |
U.push_back(Constructable(I)); |
| 904 |
|
| 905 |
const Constructable *OrigDataPtr = U.data(); |
| 906 |
|
| 907 |
// Move-assign from the other vector. |
| 908 |
V = std::move(static_cast<SmallVectorImpl<Constructable> &>(U)); |
| 909 |
|
| 910 |
// Make sure we have the right result. |
| 911 |
assertValuesInOrder(V, 4u, 0, 1, 2, 3); |
| 912 |
|
| 913 |
// Make sure the # of constructor/destructor calls line up. There |
| 914 |
// are two live objects after clearing the other vector. |
| 915 |
U.clear(); |
| 916 |
EXPECT_EQ(Constructable::getNumConstructorCalls()-4, |
| 917 |
Constructable::getNumDestructorCalls()); |
| 918 |
|
| 919 |
// If the source vector (otherVector) was in small-mode, assert that we just |
| 920 |
// moved the data pointer over. |
| 921 |
EXPECT_TRUE(NumBuiltinElts(U) == 4 || V.data() == OrigDataPtr); |
| 922 |
|
| 923 |
// There shouldn't be any live objects any more. |
| 924 |
V.clear(); |
| 925 |
EXPECT_EQ(Constructable::getNumConstructorCalls(), |
| 926 |
Constructable::getNumDestructorCalls()); |
| 927 |
|
| 928 |
// We shouldn't have copied anything in this whole process. |
| 929 |
EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0); |
| 930 |
} |
| 931 |
|
| 932 |
struct notassignable { |
| 933 |
int &x; |
| 934 |
notassignable(int &x) : x(x) {} |
| 935 |
}; |
| 936 |
|
| 937 |
TEST(SmallVectorCustomTest, NoAssignTest) { |
| 938 |
int x = 0; |
| 939 |
SmallVector<notassignable, 2> vec; |
| 940 |
vec.push_back(notassignable(x)); |
| 941 |
x = 42; |
| 942 |
EXPECT_EQ(42, vec.pop_back_val().x); |
| 943 |
} |
| 944 |
|
| 945 |
struct MovedFrom { |
| 946 |
bool hasValue; |
| 947 |
MovedFrom() : hasValue(true) { |
| 948 |
} |
| 949 |
MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) { |
| 950 |
m.hasValue = false; |
| 951 |
} |
| 952 |
MovedFrom &operator=(MovedFrom&& m) { |
| 953 |
hasValue = m.hasValue; |
| 954 |
m.hasValue = false; |
| 955 |
return *this; |
| 956 |
} |
| 957 |
}; |
| 958 |
|
| 959 |
TEST(SmallVectorTest, MidInsert) { |
| 960 |
SmallVector<MovedFrom, 3> v; |
| 961 |
v.push_back(MovedFrom()); |
| 962 |
v.insert(v.begin(), MovedFrom()); |
| 963 |
for (MovedFrom &m : v) |
| 964 |
EXPECT_TRUE(m.hasValue); |
| 965 |
} |
| 966 |
|
| 967 |
enum EmplaceableArgState { |
| 968 |
EAS_Defaulted, |
| 969 |
EAS_Arg, |
| 970 |
EAS_LValue, |
| 971 |
EAS_RValue, |
| 972 |
EAS_Failure |
| 973 |
}; |
| 974 |
template <int I> struct EmplaceableArg { |
| 975 |
EmplaceableArgState State; |
| 976 |
EmplaceableArg() : State(EAS_Defaulted) {} |
| 977 |
EmplaceableArg(EmplaceableArg &&X) |
| 978 |
: State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {} |
| 979 |
EmplaceableArg(EmplaceableArg &X) |
| 980 |
: State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {} |
| 981 |
|
| 982 |
explicit EmplaceableArg(bool) : State(EAS_Arg) {} |
| 983 |
|
| 984 |
private: |
| 985 |
EmplaceableArg &operator=(EmplaceableArg &&) = delete; |
| 986 |
EmplaceableArg &operator=(const EmplaceableArg &) = delete; |
| 987 |
}; |
| 988 |
|
| 989 |
enum EmplaceableState { ES_Emplaced, ES_Moved }; |
| 990 |
struct Emplaceable { |
| 991 |
EmplaceableArg<0> A0; |
| 992 |
EmplaceableArg<1> A1; |
| 993 |
EmplaceableArg<2> A2; |
| 994 |
EmplaceableArg<3> A3; |
| 995 |
EmplaceableState State; |
| 996 |
|
| 997 |
Emplaceable() : State(ES_Emplaced) {} |
| 998 |
|
| 999 |
template <class A0Ty> |
| 1000 |
explicit Emplaceable(A0Ty &&A0) |
| 1001 |
: A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {} |
| 1002 |
|
| 1003 |
template <class A0Ty, class A1Ty> |
| 1004 |
Emplaceable(A0Ty &&A0, A1Ty &&A1) |
| 1005 |
: A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), |
| 1006 |
State(ES_Emplaced) {} |
| 1007 |
|
| 1008 |
template <class A0Ty, class A1Ty, class A2Ty> |
| 1009 |
Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2) |
| 1010 |
: A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), |
| 1011 |
A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {} |
| 1012 |
|
| 1013 |
template <class A0Ty, class A1Ty, class A2Ty, class A3Ty> |
| 1014 |
Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3) |
| 1015 |
: A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), |
| 1016 |
A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)), |
| 1017 |
State(ES_Emplaced) {} |
| 1018 |
|
| 1019 |
Emplaceable(Emplaceable &&) : State(ES_Moved) {} |
| 1020 |
Emplaceable &operator=(Emplaceable &&) { |
| 1021 |
State = ES_Moved; |
| 1022 |
return *this; |
| 1023 |
} |
| 1024 |
|
| 1025 |
private: |
| 1026 |
Emplaceable(const Emplaceable &) = delete; |
| 1027 |
Emplaceable &operator=(const Emplaceable &) = delete; |
| 1028 |
}; |
| 1029 |
|
| 1030 |
TEST(SmallVectorTest, EmplaceBack) { |
| 1031 |
EmplaceableArg<0> A0(true); |
| 1032 |
EmplaceableArg<1> A1(true); |
| 1033 |
EmplaceableArg<2> A2(true); |
| 1034 |
EmplaceableArg<3> A3(true); |
| 1035 |
{ |
| 1036 |
SmallVector<Emplaceable, 3> V; |
| 1037 |
Emplaceable &back = V.emplace_back(); |
| 1038 |
EXPECT_TRUE(&back == &V.back()); |
| 1039 |
EXPECT_TRUE(V.size() == 1); |
| 1040 |
EXPECT_TRUE(back.State == ES_Emplaced); |
| 1041 |
EXPECT_TRUE(back.A0.State == EAS_Defaulted); |
| 1042 |
EXPECT_TRUE(back.A1.State == EAS_Defaulted); |
| 1043 |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); |
| 1044 |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); |
| 1045 |
} |
| 1046 |
{ |
| 1047 |
SmallVector<Emplaceable, 3> V; |
| 1048 |
Emplaceable &back = V.emplace_back(std::move(A0)); |
| 1049 |
EXPECT_TRUE(&back == &V.back()); |
| 1050 |
EXPECT_TRUE(V.size() == 1); |
| 1051 |
EXPECT_TRUE(back.State == ES_Emplaced); |
| 1052 |
EXPECT_TRUE(back.A0.State == EAS_RValue); |
| 1053 |
EXPECT_TRUE(back.A1.State == EAS_Defaulted); |
| 1054 |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); |
| 1055 |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); |
| 1056 |
} |
| 1057 |
{ |
| 1058 |
SmallVector<Emplaceable, 3> V; |
| 1059 |
Emplaceable &back = V.emplace_back(A0); |
| 1060 |
EXPECT_TRUE(&back == &V.back()); |
| 1061 |
EXPECT_TRUE(V.size() == 1); |
| 1062 |
EXPECT_TRUE(back.State == ES_Emplaced); |
| 1063 |
EXPECT_TRUE(back.A0.State == EAS_LValue); |
| 1064 |
EXPECT_TRUE(back.A1.State == EAS_Defaulted); |
| 1065 |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); |
| 1066 |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); |
| 1067 |
} |
| 1068 |
{ |
| 1069 |
SmallVector<Emplaceable, 3> V; |
| 1070 |
Emplaceable &back = V.emplace_back(A0, A1); |
| 1071 |
EXPECT_TRUE(&back == &V.back()); |
| 1072 |
EXPECT_TRUE(V.size() == 1); |
| 1073 |
EXPECT_TRUE(back.State == ES_Emplaced); |
| 1074 |
EXPECT_TRUE(back.A0.State == EAS_LValue); |
| 1075 |
EXPECT_TRUE(back.A1.State == EAS_LValue); |
| 1076 |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); |
| 1077 |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); |
| 1078 |
} |
| 1079 |
{ |
| 1080 |
SmallVector<Emplaceable, 3> V; |
| 1081 |
Emplaceable &back = V.emplace_back(std::move(A0), std::move(A1)); |
| 1082 |
EXPECT_TRUE(&back == &V.back()); |
| 1083 |
EXPECT_TRUE(V.size() == 1); |
| 1084 |
EXPECT_TRUE(back.State == ES_Emplaced); |
| 1085 |
EXPECT_TRUE(back.A0.State == EAS_RValue); |
| 1086 |
EXPECT_TRUE(back.A1.State == EAS_RValue); |
| 1087 |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); |
| 1088 |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); |
| 1089 |
} |
| 1090 |
{ |
| 1091 |
SmallVector<Emplaceable, 3> V; |
| 1092 |
Emplaceable &back = V.emplace_back(std::move(A0), A1, std::move(A2), A3); |
| 1093 |
EXPECT_TRUE(&back == &V.back()); |
| 1094 |
EXPECT_TRUE(V.size() == 1); |
| 1095 |
EXPECT_TRUE(back.State == ES_Emplaced); |
| 1096 |
EXPECT_TRUE(back.A0.State == EAS_RValue); |
| 1097 |
EXPECT_TRUE(back.A1.State == EAS_LValue); |
| 1098 |
EXPECT_TRUE(back.A2.State == EAS_RValue); |
| 1099 |
EXPECT_TRUE(back.A3.State == EAS_LValue); |
| 1100 |
} |
| 1101 |
{ |
| 1102 |
SmallVector<int, 1> V; |
| 1103 |
V.emplace_back(); |
| 1104 |
V.emplace_back(42); |
| 1105 |
EXPECT_EQ(2U, V.size()); |
| 1106 |
EXPECT_EQ(0, V[0]); |
| 1107 |
EXPECT_EQ(42, V[1]); |
| 1108 |
} |
| 1109 |
} |
| 1110 |
|
| 1111 |
TEST(SmallVectorTest, DefaultInlinedElements) { |
| 1112 |
SmallVector<int> V; |
| 1113 |
EXPECT_TRUE(V.empty()); |
| 1114 |
V.push_back(7); |
| 1115 |
EXPECT_EQ(V[0], 7); |
| 1116 |
|
| 1117 |
// Check that at least a couple layers of nested SmallVector<T>'s are allowed |
| 1118 |
// by the default inline elements policy. This pattern happens in practice |
| 1119 |
// with some frequency, and it seems fairly harmless even though each layer of |
| 1120 |
// SmallVector's will grow the total sizeof by a vector header beyond the |
| 1121 |
// "preferred" maximum sizeof. |
| 1122 |
SmallVector<SmallVector<SmallVector<int>>> NestedV; |
| 1123 |
NestedV.emplace_back().emplace_back().emplace_back(42); |
| 1124 |
EXPECT_EQ(NestedV[0][0][0], 42); |
| 1125 |
} |
| 1126 |
|
| 1127 |
TEST(SmallVectorTest, InitializerList) { |
| 1128 |
SmallVector<int, 2> V1 = {}; |
| 1129 |
EXPECT_TRUE(V1.empty()); |
| 1130 |
V1 = {0, 0}; |
| 1131 |
EXPECT_TRUE(ArrayRef(V1).equals({0, 0})); |
| 1132 |
V1 = {-1, -1}; |
| 1133 |
EXPECT_TRUE(ArrayRef(V1).equals({-1, -1})); |
| 1134 |
|
| 1135 |
SmallVector<int, 2> V2 = {1, 2, 3, 4}; |
| 1136 |
EXPECT_TRUE(ArrayRef(V2).equals({1, 2, 3, 4})); |
| 1137 |
V2.assign({4}); |
| 1138 |
EXPECT_TRUE(ArrayRef(V2).equals({4})); |
| 1139 |
V2.append({3, 2}); |
| 1140 |
EXPECT_TRUE(ArrayRef(V2).equals({4, 3, 2})); |
| 1141 |
V2.insert(V2.begin() + 1, 5); |
| 1142 |
EXPECT_TRUE(ArrayRef(V2).equals({4, 5, 3, 2})); |
| 1143 |
} |
| 1144 |
|
| 1145 |
TEST(SmallVectorTest, ToVector) { |
| 1146 |
{ |
| 1147 |
std::vector<char> v = {'a', 'b', 'c'}; |
| 1148 |
auto Vector = to_vector<4>(v); |
| 1149 |
static_assert(NumBuiltinElts(Vector) == 4u); |
| 1150 |
ASSERT_EQ(3u, Vector.size()); |
| 1151 |
for (size_t I = 0; I < v.size(); ++I) |
| 1152 |
EXPECT_EQ(v[I], Vector[I]); |
| 1153 |
} |
| 1154 |
{ |
| 1155 |
std::vector<char> v = {'a', 'b', 'c'}; |
| 1156 |
auto Vector = to_vector(v); |
| 1157 |
static_assert(NumBuiltinElts(Vector) != 4u); |
| 1158 |
ASSERT_EQ(3u, Vector.size()); |
| 1159 |
for (size_t I = 0; I < v.size(); ++I) |
| 1160 |
EXPECT_EQ(v[I], Vector[I]); |
| 1161 |
} |
| 1162 |
} |
| 1163 |
|
| 1164 |
struct To { |
| 1165 |
int Content; |
| 1166 |
friend bool operator==(const To &LHS, const To &RHS) { |
| 1167 |
return LHS.Content == RHS.Content; |
| 1168 |
} |
| 1169 |
}; |
| 1170 |
|
| 1171 |
class From { |
| 1172 |
public: |
| 1173 |
From() = default; |
| 1174 |
From(To M) { T = M; } |
| 1175 |
operator To() const { return T; } |
| 1176 |
|
| 1177 |
private: |
| 1178 |
To T; |
| 1179 |
}; |
| 1180 |
|
| 1181 |
TEST(SmallVectorTest, ConstructFromArrayRefOfConvertibleType) { |
| 1182 |
To to1{1}, to2{2}, to3{3}; |
| 1183 |
std::vector<From> StdVector = {From(to1), From(to2), From(to3)}; |
| 1184 |
ArrayRef<From> Array = StdVector; |
| 1185 |
{ |
| 1186 |
llvm::SmallVector<To> Vector(Array); |
| 1187 |
|
| 1188 |
ASSERT_EQ(Array.size(), Vector.size()); |
| 1189 |
for (size_t I = 0; I < Array.size(); ++I) |
| 1190 |
EXPECT_EQ(Array[I], Vector[I]); |
| 1191 |
} |
| 1192 |
{ |
| 1193 |
llvm::SmallVector<To, 4> Vector(Array); |
| 1194 |
|
| 1195 |
ASSERT_EQ(Array.size(), Vector.size()); |
| 1196 |
ASSERT_EQ(4u, NumBuiltinElts(Vector)); |
| 1197 |
for (size_t I = 0; I < Array.size(); ++I) |
| 1198 |
EXPECT_EQ(Array[I], Vector[I]); |
| 1199 |
} |
| 1200 |
} |
| 1201 |
|
| 1202 |
TEST(SmallVectorTest, ToVectorOf) { |
| 1203 |
To to1{1}, to2{2}, to3{3}; |
| 1204 |
std::vector<From> StdVector = {From(to1), From(to2), From(to3)}; |
| 1205 |
{ |
| 1206 |
llvm::SmallVector<To> Vector = llvm::to_vector_of<To>(StdVector); |
| 1207 |
|
| 1208 |
ASSERT_EQ(StdVector.size(), Vector.size()); |
| 1209 |
for (size_t I = 0; I < StdVector.size(); ++I) |
| 1210 |
EXPECT_EQ(StdVector[I], Vector[I]); |
| 1211 |
} |
| 1212 |
{ |
| 1213 |
auto Vector = llvm::to_vector_of<To, 4>(StdVector); |
| 1214 |
|
| 1215 |
ASSERT_EQ(StdVector.size(), Vector.size()); |
| 1216 |
static_assert(NumBuiltinElts(Vector) == 4u); |
| 1217 |
for (size_t I = 0; I < StdVector.size(); ++I) |
| 1218 |
EXPECT_EQ(StdVector[I], Vector[I]); |
| 1219 |
} |
| 1220 |
} |
| 1221 |
|
| 1222 |
template <class VectorT> |
| 1223 |
class SmallVectorReferenceInvalidationTest : public SmallVectorTestBase { |
| 1224 |
protected: |
| 1225 |
const char *AssertionMessage = |
| 1226 |
"Attempting to reference an element of the vector in an operation \" " |
| 1227 |
"\"that invalidates it"; |
| 1228 |
|
| 1229 |
VectorT V; |
| 1230 |
|
| 1231 |
template <class T> static bool isValueType() { |
| 1232 |
return std::is_same_v<T, typename VectorT::value_type>; |
| 1233 |
} |
| 1234 |
|
| 1235 |
void SetUp() override { |
| 1236 |
SmallVectorTestBase::SetUp(); |
| 1237 |
|
| 1238 |
// Fill up the small size so that insertions move the elements. |
| 1239 |
for (int I = 0, E = NumBuiltinElts(V); I != E; ++I) |
| 1240 |
V.emplace_back(I + 1); |
| 1241 |
} |
| 1242 |
}; |
| 1243 |
|
| 1244 |
// Test one type that's trivially copyable (int) and one that isn't |
| 1245 |
// (Constructable) since reference invalidation may be fixed differently for |
| 1246 |
// each. |
| 1247 |
using SmallVectorReferenceInvalidationTestTypes = |
| 1248 |
::testing::Types<SmallVector<int, 3>, SmallVector<Constructable, 3>>; |
| 1249 |
|
| 1250 |
TYPED_TEST_SUITE(SmallVectorReferenceInvalidationTest, |
| 1251 |
SmallVectorReferenceInvalidationTestTypes, ); |
| 1252 |
|
| 1253 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBack) { |
| 1254 |
// Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. |
| 1255 |
auto &V = this->V; |
| 1256 |
int N = NumBuiltinElts(V); |
| 1257 |
|
| 1258 |
// Push back a reference to last element when growing from small storage. |
| 1259 |
V.push_back(V.back()); |
| 1260 |
EXPECT_EQ(N, V.back()); |
| 1261 |
|
| 1262 |
// Check that the old value is still there (not moved away). |
| 1263 |
EXPECT_EQ(N, V[V.size() - 2]); |
| 1264 |
|
| 1265 |
// Fill storage again. |
| 1266 |
V.back() = V.size(); |
| 1267 |
while (V.size() < V.capacity()) |
| 1268 |
V.push_back(V.size() + 1); |
| 1269 |
|
| 1270 |
// Push back a reference to last element when growing from large storage. |
| 1271 |
V.push_back(V.back()); |
| 1272 |
EXPECT_EQ(int(V.size()) - 1, V.back()); |
| 1273 |
} |
| 1274 |
|
| 1275 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) { |
| 1276 |
// Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. |
| 1277 |
auto &V = this->V; |
| 1278 |
int N = NumBuiltinElts(V); |
| 1279 |
|
| 1280 |
// Push back a reference to last element when growing from small storage. |
| 1281 |
V.push_back(std::move(V.back())); |
| 1282 |
EXPECT_EQ(N, V.back()); |
| 1283 |
if (this->template isValueType<Constructable>()) { |
| 1284 |
// Check that the value was moved (not copied). |
| 1285 |
EXPECT_EQ(0, V[V.size() - 2]); |
| 1286 |
} |
| 1287 |
|
| 1288 |
// Fill storage again. |
| 1289 |
V.back() = V.size(); |
| 1290 |
while (V.size() < V.capacity()) |
| 1291 |
V.push_back(V.size() + 1); |
| 1292 |
|
| 1293 |
// Push back a reference to last element when growing from large storage. |
| 1294 |
V.push_back(std::move(V.back())); |
| 1295 |
|
| 1296 |
// Check the values. |
| 1297 |
EXPECT_EQ(int(V.size()) - 1, V.back()); |
| 1298 |
if (this->template isValueType<Constructable>()) { |
| 1299 |
// Check the value got moved out. |
| 1300 |
EXPECT_EQ(0, V[V.size() - 2]); |
| 1301 |
} |
| 1302 |
} |
| 1303 |
|
| 1304 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, Resize) { |
| 1305 |
auto &V = this->V; |
| 1306 |
(void)V; |
| 1307 |
int N = NumBuiltinElts(V); |
| 1308 |
V.resize(N + 1, V.back()); |
| 1309 |
EXPECT_EQ(N, V.back()); |
| 1310 |
|
| 1311 |
// Resize to add enough elements that V will grow again. If reference |
| 1312 |
// invalidation breaks in the future, sanitizers should be able to catch a |
| 1313 |
// use-after-free here. |
| 1314 |
V.resize(V.capacity() + 1, V.front()); |
| 1315 |
EXPECT_EQ(1, V.back()); |
| 1316 |
} |
| 1317 |
|
| 1318 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, Append) { |
| 1319 |
auto &V = this->V; |
| 1320 |
(void)V; |
| 1321 |
V.append(1, V.back()); |
| 1322 |
int N = NumBuiltinElts(V); |
| 1323 |
EXPECT_EQ(N, V[N - 1]); |
| 1324 |
|
| 1325 |
// Append enough more elements that V will grow again. This tests growing |
| 1326 |
// when already in large mode. |
| 1327 |
// |
| 1328 |
// If reference invalidation breaks in the future, sanitizers should be able |
| 1329 |
// to catch a use-after-free here. |
| 1330 |
V.append(V.capacity() - V.size() + 1, V.front()); |
| 1331 |
EXPECT_EQ(1, V.back()); |
| 1332 |
} |
| 1333 |
|
| 1334 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, AppendRange) { |
| 1335 |
auto &V = this->V; |
| 1336 |
(void)V; |
| 1337 |
#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST |
| 1338 |
EXPECT_DEATH(V.append(V.begin(), V.begin() + 1), this->AssertionMessage); |
| 1339 |
|
| 1340 |
ASSERT_EQ(3u, NumBuiltinElts(V)); |
| 1341 |
ASSERT_EQ(3u, V.size()); |
| 1342 |
V.pop_back(); |
| 1343 |
ASSERT_EQ(2u, V.size()); |
| 1344 |
|
| 1345 |
// Confirm this checks for growth when there's more than one element |
| 1346 |
// appended. |
| 1347 |
EXPECT_DEATH(V.append(V.begin(), V.end()), this->AssertionMessage); |
| 1348 |
#endif |
| 1349 |
} |
| 1350 |
|
| 1351 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, Assign) { |
| 1352 |
// Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. |
| 1353 |
auto &V = this->V; |
| 1354 |
(void)V; |
| 1355 |
int N = NumBuiltinElts(V); |
| 1356 |
ASSERT_EQ(unsigned(N), V.size()); |
| 1357 |
ASSERT_EQ(unsigned(N), V.capacity()); |
| 1358 |
|
| 1359 |
// Check assign that shrinks in small mode. |
| 1360 |
V.assign(1, V.back()); |
| 1361 |
EXPECT_EQ(1u, V.size()); |
| 1362 |
EXPECT_EQ(N, V[0]); |
| 1363 |
|
| 1364 |
// Check assign that grows within small mode. |
| 1365 |
ASSERT_LT(V.size(), V.capacity()); |
| 1366 |
V.assign(V.capacity(), V.back()); |
| 1367 |
for (int I = 0, E = V.size(); I != E; ++I) { |
| 1368 |
EXPECT_EQ(N, V[I]); |
| 1369 |
|
| 1370 |
// Reset to [1, 2, ...]. |
| 1371 |
V[I] = I + 1; |
| 1372 |
} |
| 1373 |
|
| 1374 |
// Check assign that grows to large mode. |
| 1375 |
ASSERT_EQ(2, V[1]); |
| 1376 |
V.assign(V.capacity() + 1, V[1]); |
| 1377 |
for (int I = 0, E = V.size(); I != E; ++I) { |
| 1378 |
EXPECT_EQ(2, V[I]); |
| 1379 |
|
| 1380 |
// Reset to [1, 2, ...]. |
| 1381 |
V[I] = I + 1; |
| 1382 |
} |
| 1383 |
|
| 1384 |
// Check assign that shrinks in large mode. |
| 1385 |
V.assign(1, V[1]); |
| 1386 |
EXPECT_EQ(2, V[0]); |
| 1387 |
} |
| 1388 |
|
| 1389 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, AssignRange) { |
| 1390 |
auto &V = this->V; |
| 1391 |
#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST |
| 1392 |
EXPECT_DEATH(V.assign(V.begin(), V.end()), this->AssertionMessage); |
| 1393 |
EXPECT_DEATH(V.assign(V.begin(), V.end() - 1), this->AssertionMessage); |
| 1394 |
#endif |
| 1395 |
V.assign(V.begin(), V.begin()); |
| 1396 |
EXPECT_TRUE(V.empty()); |
| 1397 |
} |
| 1398 |
|
| 1399 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, Insert) { |
| 1400 |
// Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. |
| 1401 |
auto &V = this->V; |
| 1402 |
(void)V; |
| 1403 |
|
| 1404 |
// Insert a reference to the back (not at end() or else insert delegates to |
| 1405 |
// push_back()), growing out of small mode. Confirm the value was copied out |
| 1406 |
// (moving out Constructable sets it to 0). |
| 1407 |
V.insert(V.begin(), V.back()); |
| 1408 |
EXPECT_EQ(int(V.size() - 1), V.front()); |
| 1409 |
EXPECT_EQ(int(V.size() - 1), V.back()); |
| 1410 |
|
| 1411 |
// Fill up the vector again. |
| 1412 |
while (V.size() < V.capacity()) |
| 1413 |
V.push_back(V.size() + 1); |
| 1414 |
|
| 1415 |
// Grow again from large storage to large storage. |
| 1416 |
V.insert(V.begin(), V.back()); |
| 1417 |
EXPECT_EQ(int(V.size() - 1), V.front()); |
| 1418 |
EXPECT_EQ(int(V.size() - 1), V.back()); |
| 1419 |
} |
| 1420 |
|
| 1421 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertMoved) { |
| 1422 |
// Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. |
| 1423 |
auto &V = this->V; |
| 1424 |
(void)V; |
| 1425 |
|
| 1426 |
// Insert a reference to the back (not at end() or else insert delegates to |
| 1427 |
// push_back()), growing out of small mode. Confirm the value was copied out |
| 1428 |
// (moving out Constructable sets it to 0). |
| 1429 |
V.insert(V.begin(), std::move(V.back())); |
| 1430 |
EXPECT_EQ(int(V.size() - 1), V.front()); |
| 1431 |
if (this->template isValueType<Constructable>()) { |
| 1432 |
// Check the value got moved out. |
| 1433 |
EXPECT_EQ(0, V.back()); |
| 1434 |
} |
| 1435 |
|
| 1436 |
// Fill up the vector again. |
| 1437 |
while (V.size() < V.capacity()) |
| 1438 |
V.push_back(V.size() + 1); |
| 1439 |
|
| 1440 |
// Grow again from large storage to large storage. |
| 1441 |
V.insert(V.begin(), std::move(V.back())); |
| 1442 |
EXPECT_EQ(int(V.size() - 1), V.front()); |
| 1443 |
if (this->template isValueType<Constructable>()) { |
| 1444 |
// Check the value got moved out. |
| 1445 |
EXPECT_EQ(0, V.back()); |
| 1446 |
} |
| 1447 |
} |
| 1448 |
|
| 1449 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertN) { |
| 1450 |
auto &V = this->V; |
| 1451 |
(void)V; |
| 1452 |
|
| 1453 |
// Cover NumToInsert <= this->end() - I. |
| 1454 |
V.insert(V.begin() + 1, 1, V.back()); |
| 1455 |
int N = NumBuiltinElts(V); |
| 1456 |
EXPECT_EQ(N, V[1]); |
| 1457 |
|
| 1458 |
// Cover NumToInsert > this->end() - I, inserting enough elements that V will |
| 1459 |
// also grow again; V.capacity() will be more elements than necessary but |
| 1460 |
// it's a simple way to cover both conditions. |
| 1461 |
// |
| 1462 |
// If reference invalidation breaks in the future, sanitizers should be able |
| 1463 |
// to catch a use-after-free here. |
| 1464 |
V.insert(V.begin(), V.capacity(), V.front()); |
| 1465 |
EXPECT_EQ(1, V.front()); |
| 1466 |
} |
| 1467 |
|
| 1468 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertRange) { |
| 1469 |
auto &V = this->V; |
| 1470 |
(void)V; |
| 1471 |
#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST |
| 1472 |
EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.begin() + 1), |
| 1473 |
this->AssertionMessage); |
| 1474 |
|
| 1475 |
ASSERT_EQ(3u, NumBuiltinElts(V)); |
| 1476 |
ASSERT_EQ(3u, V.size()); |
| 1477 |
V.pop_back(); |
| 1478 |
ASSERT_EQ(2u, V.size()); |
| 1479 |
|
| 1480 |
// Confirm this checks for growth when there's more than one element |
| 1481 |
// inserted. |
| 1482 |
EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.end()), this->AssertionMessage); |
| 1483 |
#endif |
| 1484 |
} |
| 1485 |
|
| 1486 |
TYPED_TEST(SmallVectorReferenceInvalidationTest, EmplaceBack) { |
| 1487 |
// Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. |
| 1488 |
auto &V = this->V; |
| 1489 |
int N = NumBuiltinElts(V); |
| 1490 |
|
| 1491 |
// Push back a reference to last element when growing from small storage. |
| 1492 |
V.emplace_back(V.back()); |
| 1493 |
EXPECT_EQ(N, V.back()); |
| 1494 |
|
| 1495 |
// Check that the old value is still there (not moved away). |
| 1496 |
EXPECT_EQ(N, V[V.size() - 2]); |
| 1497 |
|
| 1498 |
// Fill storage again. |
| 1499 |
V.back() = V.size(); |
| 1500 |
while (V.size() < V.capacity()) |
| 1501 |
V.push_back(V.size() + 1); |
| 1502 |
|
| 1503 |
// Push back a reference to last element when growing from large storage. |
| 1504 |
V.emplace_back(V.back()); |
| 1505 |
EXPECT_EQ(int(V.size()) - 1, V.back()); |
| 1506 |
} |
| 1507 |
|
| 1508 |
template <class VectorT> |
| 1509 |
class SmallVectorInternalReferenceInvalidationTest |
| 1510 |
: public SmallVectorTestBase { |
| 1511 |
protected: |
| 1512 |
const char *AssertionMessage = |
| 1513 |
"Attempting to reference an element of the vector in an operation \" " |
| 1514 |
"\"that invalidates it"; |
| 1515 |
|
| 1516 |
VectorT V; |
| 1517 |
|
| 1518 |
void SetUp() override { |
| 1519 |
SmallVectorTestBase::SetUp(); |
| 1520 |
|
| 1521 |
// Fill up the small size so that insertions move the elements. |
| 1522 |
for (int I = 0, E = NumBuiltinElts(V); I != E; ++I) |
| 1523 |
V.emplace_back(I + 1, I + 1); |
| 1524 |
} |
| 1525 |
}; |
| 1526 |
|
| 1527 |
// Test pairs of the same types from SmallVectorReferenceInvalidationTestTypes. |
| 1528 |
using SmallVectorInternalReferenceInvalidationTestTypes = |
| 1529 |
::testing::Types<SmallVector<std::pair<int, int>, 3>, |
| 1530 |
SmallVector<std::pair<Constructable, Constructable>, 3>>; |
| 1531 |
|
| 1532 |
TYPED_TEST_SUITE(SmallVectorInternalReferenceInvalidationTest, |
| 1533 |
SmallVectorInternalReferenceInvalidationTestTypes, ); |
| 1534 |
|
| 1535 |
TYPED_TEST(SmallVectorInternalReferenceInvalidationTest, EmplaceBack) { |
| 1536 |
// Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. |
| 1537 |
auto &V = this->V; |
| 1538 |
int N = NumBuiltinElts(V); |
| 1539 |
|
| 1540 |
// Push back a reference to last element when growing from small storage. |
| 1541 |
V.emplace_back(V.back().first, V.back().second); |
| 1542 |
EXPECT_EQ(N, V.back().first); |
| 1543 |
EXPECT_EQ(N, V.back().second); |
| 1544 |
|
| 1545 |
// Check that the old value is still there (not moved away). |
| 1546 |
EXPECT_EQ(N, V[V.size() - 2].first); |
| 1547 |
EXPECT_EQ(N, V[V.size() - 2].second); |
| 1548 |
|
| 1549 |
// Fill storage again. |
| 1550 |
V.back().first = V.back().second = V.size(); |
| 1551 |
while (V.size() < V.capacity()) |
| 1552 |
V.emplace_back(V.size() + 1, V.size() + 1); |
| 1553 |
|
| 1554 |
// Push back a reference to last element when growing from large storage. |
| 1555 |
V.emplace_back(V.back().first, V.back().second); |
| 1556 |
EXPECT_EQ(int(V.size()) - 1, V.back().first); |
| 1557 |
EXPECT_EQ(int(V.size()) - 1, V.back().second); |
| 1558 |
} |
| 1559 |
|
| 1560 |
} // end namespace |