1 //===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===// 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 #include "llvm/ADT/StringMap.h" 10 #include "llvm/ADT/Twine.h" 11 #include "llvm/Support/DataTypes.h" 12 #include "gtest/gtest.h" 13 #include <limits> 14 #include <tuple> 15 using namespace llvm; 16 17 namespace { 18 19 // Test fixture 20 class StringMapTest : public testing::Test { 21 protected: 22 StringMap<uint32_t> testMap; 23 24 static const char testKey[]; 25 static const uint32_t testValue; 26 static const char* testKeyFirst; 27 static size_t testKeyLength; 28 static const std::string testKeyStr; 29 30 void assertEmptyMap() { 31 // Size tests 32 EXPECT_EQ(0u, testMap.size()); 33 EXPECT_TRUE(testMap.empty()); 34 35 // Iterator tests 36 EXPECT_TRUE(testMap.begin() == testMap.end()); 37 38 // Lookup tests 39 EXPECT_EQ(0u, testMap.count(testKey)); 40 EXPECT_EQ(0u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 41 EXPECT_EQ(0u, testMap.count(testKeyStr)); 42 EXPECT_TRUE(testMap.find(testKey) == testMap.end()); 43 EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 44 testMap.end()); 45 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end()); 46 } 47 48 void assertSingleItemMap() { 49 // Size tests 50 EXPECT_EQ(1u, testMap.size()); 51 EXPECT_FALSE(testMap.begin() == testMap.end()); 52 EXPECT_FALSE(testMap.empty()); 53 54 // Iterator tests 55 StringMap<uint32_t>::iterator it = testMap.begin(); 56 EXPECT_STREQ(testKey, it->first().data()); 57 EXPECT_EQ(testValue, it->second); 58 ++it; 59 EXPECT_TRUE(it == testMap.end()); 60 61 // Lookup tests 62 EXPECT_EQ(1u, testMap.count(testKey)); 63 EXPECT_EQ(1u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 64 EXPECT_EQ(1u, testMap.count(testKeyStr)); 65 EXPECT_TRUE(testMap.find(testKey) == testMap.begin()); 66 EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 67 testMap.begin()); 68 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin()); 69 } 70 }; 71 72 const char StringMapTest::testKey[] = "key"; 73 const uint32_t StringMapTest::testValue = 1u; 74 const char* StringMapTest::testKeyFirst = testKey; 75 size_t StringMapTest::testKeyLength = sizeof(testKey) - 1; 76 const std::string StringMapTest::testKeyStr(testKey); 77 78 struct CountCopyAndMove { 79 CountCopyAndMove() = default; 80 CountCopyAndMove(const CountCopyAndMove &) { copy = 1; } 81 CountCopyAndMove(CountCopyAndMove &&) { move = 1; } 82 void operator=(const CountCopyAndMove &) { ++copy; } 83 void operator=(CountCopyAndMove &&) { ++move; } 84 int copy = 0; 85 int move = 0; 86 }; 87 88 // Empty map tests. 89 TEST_F(StringMapTest, EmptyMapTest) { 90 assertEmptyMap(); 91 } 92 93 // Constant map tests. 94 TEST_F(StringMapTest, ConstEmptyMapTest) { 95 const StringMap<uint32_t>& constTestMap = testMap; 96 97 // Size tests 98 EXPECT_EQ(0u, constTestMap.size()); 99 EXPECT_TRUE(constTestMap.empty()); 100 101 // Iterator tests 102 EXPECT_TRUE(constTestMap.begin() == constTestMap.end()); 103 104 // Lookup tests 105 EXPECT_EQ(0u, constTestMap.count(testKey)); 106 EXPECT_EQ(0u, constTestMap.count(StringRef(testKeyFirst, testKeyLength))); 107 EXPECT_EQ(0u, constTestMap.count(testKeyStr)); 108 EXPECT_TRUE(constTestMap.find(testKey) == constTestMap.end()); 109 EXPECT_TRUE(constTestMap.find(StringRef(testKeyFirst, testKeyLength)) == 110 constTestMap.end()); 111 EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end()); 112 } 113 114 // A map with a single entry. 115 TEST_F(StringMapTest, SingleEntryMapTest) { 116 testMap[testKey] = testValue; 117 assertSingleItemMap(); 118 } 119 120 // Test clear() method. 121 TEST_F(StringMapTest, ClearTest) { 122 testMap[testKey] = testValue; 123 testMap.clear(); 124 assertEmptyMap(); 125 } 126 127 // Test erase(iterator) method. 128 TEST_F(StringMapTest, EraseIteratorTest) { 129 testMap[testKey] = testValue; 130 testMap.erase(testMap.begin()); 131 assertEmptyMap(); 132 } 133 134 // Test erase(value) method. 135 TEST_F(StringMapTest, EraseValueTest) { 136 testMap[testKey] = testValue; 137 testMap.erase(testKey); 138 assertEmptyMap(); 139 } 140 141 // Test inserting two values and erasing one. 142 TEST_F(StringMapTest, InsertAndEraseTest) { 143 testMap[testKey] = testValue; 144 testMap["otherKey"] = 2; 145 testMap.erase("otherKey"); 146 assertSingleItemMap(); 147 } 148 149 TEST_F(StringMapTest, SmallFullMapTest) { 150 // StringMap has a tricky corner case when the map is small (<8 buckets) and 151 // it fills up through a balanced pattern of inserts and erases. This can 152 // lead to inf-loops in some cases (PR13148) so we test it explicitly here. 153 llvm::StringMap<int> Map(2); 154 155 Map["eins"] = 1; 156 Map["zwei"] = 2; 157 Map["drei"] = 3; 158 Map.erase("drei"); 159 Map.erase("eins"); 160 Map["veir"] = 4; 161 Map["funf"] = 5; 162 163 EXPECT_EQ(3u, Map.size()); 164 EXPECT_EQ(0, Map.lookup("eins")); 165 EXPECT_EQ(2, Map.lookup("zwei")); 166 EXPECT_EQ(0, Map.lookup("drei")); 167 EXPECT_EQ(4, Map.lookup("veir")); 168 EXPECT_EQ(5, Map.lookup("funf")); 169 } 170 171 TEST_F(StringMapTest, CopyCtorTest) { 172 llvm::StringMap<int> Map; 173 174 Map["eins"] = 1; 175 Map["zwei"] = 2; 176 Map["drei"] = 3; 177 Map.erase("drei"); 178 Map.erase("eins"); 179 Map["veir"] = 4; 180 Map["funf"] = 5; 181 182 EXPECT_EQ(3u, Map.size()); 183 EXPECT_EQ(0, Map.lookup("eins")); 184 EXPECT_EQ(2, Map.lookup("zwei")); 185 EXPECT_EQ(0, Map.lookup("drei")); 186 EXPECT_EQ(4, Map.lookup("veir")); 187 EXPECT_EQ(5, Map.lookup("funf")); 188 189 llvm::StringMap<int> Map2(Map); 190 EXPECT_EQ(3u, Map2.size()); 191 EXPECT_EQ(0, Map2.lookup("eins")); 192 EXPECT_EQ(2, Map2.lookup("zwei")); 193 EXPECT_EQ(0, Map2.lookup("drei")); 194 EXPECT_EQ(4, Map2.lookup("veir")); 195 EXPECT_EQ(5, Map2.lookup("funf")); 196 } 197 198 // A more complex iteration test. 199 TEST_F(StringMapTest, IterationTest) { 200 bool visited[100]; 201 202 // Insert 100 numbers into the map 203 for (int i = 0; i < 100; ++i) { 204 std::stringstream ss; 205 ss << "key_" << i; 206 testMap[ss.str()] = i; 207 visited[i] = false; 208 } 209 210 // Iterate over all numbers and mark each one found. 211 for (StringMap<uint32_t>::iterator it = testMap.begin(); 212 it != testMap.end(); ++it) { 213 std::stringstream ss; 214 ss << "key_" << it->second; 215 ASSERT_STREQ(ss.str().c_str(), it->first().data()); 216 visited[it->second] = true; 217 } 218 219 // Ensure every number was visited. 220 for (int i = 0; i < 100; ++i) { 221 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 222 } 223 } 224 225 // Test StringMapEntry::Create() method. 226 TEST_F(StringMapTest, StringMapEntryTest) { 227 MallocAllocator Allocator; 228 StringMap<uint32_t>::value_type *entry = 229 StringMap<uint32_t>::value_type::Create( 230 StringRef(testKeyFirst, testKeyLength), Allocator, 1u); 231 EXPECT_STREQ(testKey, entry->first().data()); 232 EXPECT_EQ(1u, entry->second); 233 entry->Destroy(Allocator); 234 } 235 236 // Test insert() method. 237 TEST_F(StringMapTest, InsertTest) { 238 SCOPED_TRACE("InsertTest"); 239 testMap.insert( 240 StringMap<uint32_t>::value_type::Create( 241 StringRef(testKeyFirst, testKeyLength), 242 testMap.getAllocator(), 1u)); 243 assertSingleItemMap(); 244 } 245 246 // Test insert(pair<K, V>) method 247 TEST_F(StringMapTest, InsertPairTest) { 248 bool Inserted; 249 StringMap<uint32_t>::iterator NewIt; 250 std::tie(NewIt, Inserted) = 251 testMap.insert(std::make_pair(testKeyFirst, testValue)); 252 EXPECT_EQ(1u, testMap.size()); 253 EXPECT_EQ(testValue, testMap[testKeyFirst]); 254 EXPECT_EQ(testKeyFirst, NewIt->first()); 255 EXPECT_EQ(testValue, NewIt->second); 256 EXPECT_TRUE(Inserted); 257 258 StringMap<uint32_t>::iterator ExistingIt; 259 std::tie(ExistingIt, Inserted) = 260 testMap.insert(std::make_pair(testKeyFirst, testValue + 1)); 261 EXPECT_EQ(1u, testMap.size()); 262 EXPECT_EQ(testValue, testMap[testKeyFirst]); 263 EXPECT_FALSE(Inserted); 264 EXPECT_EQ(NewIt, ExistingIt); 265 } 266 267 // Test insert(pair<K, V>) method when rehashing occurs 268 TEST_F(StringMapTest, InsertRehashingPairTest) { 269 // Check that the correct iterator is returned when the inserted element is 270 // moved to a different bucket during internal rehashing. This depends on 271 // the particular key, and the implementation of StringMap and HashString. 272 // Changes to those might result in this test not actually checking that. 273 StringMap<uint32_t> t(0); 274 EXPECT_EQ(0u, t.getNumBuckets()); 275 276 StringMap<uint32_t>::iterator It = 277 t.insert(std::make_pair("abcdef", 42)).first; 278 EXPECT_EQ(16u, t.getNumBuckets()); 279 EXPECT_EQ("abcdef", It->first()); 280 EXPECT_EQ(42u, It->second); 281 } 282 283 TEST_F(StringMapTest, InsertOrAssignTest) { 284 struct A : CountCopyAndMove { 285 A(int v) : v(v) {} 286 int v; 287 }; 288 StringMap<A> t(0); 289 290 auto try1 = t.insert_or_assign("A", A(1)); 291 EXPECT_TRUE(try1.second); 292 EXPECT_EQ(1, try1.first->second.v); 293 EXPECT_EQ(1, try1.first->second.move); 294 295 auto try2 = t.insert_or_assign("A", A(2)); 296 EXPECT_FALSE(try2.second); 297 EXPECT_EQ(2, try2.first->second.v); 298 EXPECT_EQ(2, try1.first->second.move); 299 300 EXPECT_EQ(try1.first, try2.first); 301 EXPECT_EQ(0, try1.first->second.copy); 302 } 303 304 TEST_F(StringMapTest, IterMapKeys) { 305 StringMap<int> Map; 306 Map["A"] = 1; 307 Map["B"] = 2; 308 Map["C"] = 3; 309 Map["D"] = 3; 310 311 auto Keys = to_vector<4>(Map.keys()); 312 llvm::sort(Keys); 313 314 SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"}; 315 EXPECT_EQ(Expected, Keys); 316 } 317 318 // Create a non-default constructable value 319 struct StringMapTestStruct { 320 StringMapTestStruct(int i) : i(i) {} 321 StringMapTestStruct() = delete; 322 int i; 323 }; 324 325 TEST_F(StringMapTest, NonDefaultConstructable) { 326 StringMap<StringMapTestStruct> t; 327 t.insert(std::make_pair("Test", StringMapTestStruct(123))); 328 StringMap<StringMapTestStruct>::iterator iter = t.find("Test"); 329 ASSERT_NE(iter, t.end()); 330 ASSERT_EQ(iter->second.i, 123); 331 } 332 333 struct Immovable { 334 Immovable() {} 335 Immovable(Immovable&&) = delete; // will disable the other special members 336 }; 337 338 struct MoveOnly { 339 int i; 340 MoveOnly(int i) : i(i) {} 341 MoveOnly(const Immovable&) : i(0) {} 342 MoveOnly(MoveOnly &&RHS) : i(RHS.i) {} 343 MoveOnly &operator=(MoveOnly &&RHS) { 344 i = RHS.i; 345 return *this; 346 } 347 348 private: 349 MoveOnly(const MoveOnly &) = delete; 350 MoveOnly &operator=(const MoveOnly &) = delete; 351 }; 352 353 TEST_F(StringMapTest, MoveOnly) { 354 StringMap<MoveOnly> t; 355 t.insert(std::make_pair("Test", MoveOnly(42))); 356 StringRef Key = "Test"; 357 StringMapEntry<MoveOnly>::Create(Key, t.getAllocator(), MoveOnly(42)) 358 ->Destroy(t.getAllocator()); 359 } 360 361 TEST_F(StringMapTest, CtorArg) { 362 StringRef Key = "Test"; 363 MallocAllocator Allocator; 364 StringMapEntry<MoveOnly>::Create(Key, Allocator, Immovable()) 365 ->Destroy(Allocator); 366 } 367 368 TEST_F(StringMapTest, MoveConstruct) { 369 StringMap<int> A; 370 A["x"] = 42; 371 StringMap<int> B = std::move(A); 372 ASSERT_EQ(A.size(), 0u); 373 ASSERT_EQ(B.size(), 1u); 374 ASSERT_EQ(B["x"], 42); 375 ASSERT_EQ(B.count("y"), 0u); 376 } 377 378 TEST_F(StringMapTest, MoveAssignment) { 379 StringMap<int> A; 380 A["x"] = 42; 381 StringMap<int> B; 382 B["y"] = 117; 383 A = std::move(B); 384 ASSERT_EQ(A.size(), 1u); 385 ASSERT_EQ(B.size(), 0u); 386 ASSERT_EQ(A["y"], 117); 387 ASSERT_EQ(B.count("x"), 0u); 388 } 389 390 TEST_F(StringMapTest, EqualEmpty) { 391 StringMap<int> A; 392 StringMap<int> B; 393 ASSERT_TRUE(A == B); 394 ASSERT_FALSE(A != B); 395 ASSERT_TRUE(A == A); // self check 396 } 397 398 TEST_F(StringMapTest, EqualWithValues) { 399 StringMap<int> A; 400 A["A"] = 1; 401 A["B"] = 2; 402 A["C"] = 3; 403 A["D"] = 3; 404 405 StringMap<int> B; 406 B["A"] = 1; 407 B["B"] = 2; 408 B["C"] = 3; 409 B["D"] = 3; 410 411 ASSERT_TRUE(A == B); 412 ASSERT_TRUE(B == A); 413 ASSERT_FALSE(A != B); 414 ASSERT_FALSE(B != A); 415 ASSERT_TRUE(A == A); // self check 416 } 417 418 TEST_F(StringMapTest, NotEqualMissingKeys) { 419 StringMap<int> A; 420 A["A"] = 1; 421 A["B"] = 2; 422 423 StringMap<int> B; 424 B["A"] = 1; 425 B["B"] = 2; 426 B["C"] = 3; 427 B["D"] = 3; 428 429 ASSERT_FALSE(A == B); 430 ASSERT_FALSE(B == A); 431 ASSERT_TRUE(A != B); 432 ASSERT_TRUE(B != A); 433 } 434 435 TEST_F(StringMapTest, NotEqualWithDifferentValues) { 436 StringMap<int> A; 437 A["A"] = 1; 438 A["B"] = 2; 439 A["C"] = 100; 440 A["D"] = 3; 441 442 StringMap<int> B; 443 B["A"] = 1; 444 B["B"] = 2; 445 B["C"] = 3; 446 B["D"] = 3; 447 448 ASSERT_FALSE(A == B); 449 ASSERT_FALSE(B == A); 450 ASSERT_TRUE(A != B); 451 ASSERT_TRUE(B != A); 452 } 453 454 struct Countable { 455 int &InstanceCount; 456 int Number; 457 Countable(int Number, int &InstanceCount) 458 : InstanceCount(InstanceCount), Number(Number) { 459 ++InstanceCount; 460 } 461 Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) { 462 ++InstanceCount; 463 C.Number = -1; 464 } 465 Countable(const Countable &C) 466 : InstanceCount(C.InstanceCount), Number(C.Number) { 467 ++InstanceCount; 468 } 469 Countable &operator=(Countable C) { 470 Number = C.Number; 471 return *this; 472 } 473 ~Countable() { --InstanceCount; } 474 }; 475 476 TEST_F(StringMapTest, MoveDtor) { 477 int InstanceCount = 0; 478 StringMap<Countable> A; 479 A.insert(std::make_pair("x", Countable(42, InstanceCount))); 480 ASSERT_EQ(InstanceCount, 1); 481 auto I = A.find("x"); 482 ASSERT_NE(I, A.end()); 483 ASSERT_EQ(I->second.Number, 42); 484 485 StringMap<Countable> B; 486 B = std::move(A); 487 ASSERT_EQ(InstanceCount, 1); 488 ASSERT_TRUE(A.empty()); 489 I = B.find("x"); 490 ASSERT_NE(I, B.end()); 491 ASSERT_EQ(I->second.Number, 42); 492 493 B = StringMap<Countable>(); 494 ASSERT_EQ(InstanceCount, 0); 495 ASSERT_TRUE(B.empty()); 496 } 497 498 namespace { 499 // Simple class that counts how many moves and copy happens when growing a map 500 struct CountCtorCopyAndMove { 501 static unsigned Ctor; 502 static unsigned Move; 503 static unsigned Copy; 504 int Data = 0; 505 CountCtorCopyAndMove(int Data) : Data(Data) { Ctor++; } 506 CountCtorCopyAndMove() { Ctor++; } 507 508 CountCtorCopyAndMove(const CountCtorCopyAndMove &) { Copy++; } 509 CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &) { 510 Copy++; 511 return *this; 512 } 513 CountCtorCopyAndMove(CountCtorCopyAndMove &&) { Move++; } 514 CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &&) { 515 Move++; 516 return *this; 517 } 518 }; 519 unsigned CountCtorCopyAndMove::Copy = 0; 520 unsigned CountCtorCopyAndMove::Move = 0; 521 unsigned CountCtorCopyAndMove::Ctor = 0; 522 523 } // anonymous namespace 524 525 // Make sure creating the map with an initial size of N actually gives us enough 526 // buckets to insert N items without increasing allocation size. 527 TEST(StringMapCustomTest, InitialSizeTest) { 528 // 1 is an "edge value", 32 is an arbitrary power of two, and 67 is an 529 // arbitrary prime, picked without any good reason. 530 for (auto Size : {1, 32, 67}) { 531 StringMap<CountCtorCopyAndMove> Map(Size); 532 auto NumBuckets = Map.getNumBuckets(); 533 CountCtorCopyAndMove::Move = 0; 534 CountCtorCopyAndMove::Copy = 0; 535 for (int i = 0; i < Size; ++i) 536 Map.insert(std::pair<std::string, CountCtorCopyAndMove>( 537 std::piecewise_construct, std::forward_as_tuple(Twine(i).str()), 538 std::forward_as_tuple(i))); 539 // After the initial move, the map will move the Elts in the Entry. 540 EXPECT_EQ((unsigned)Size * 2, CountCtorCopyAndMove::Move); 541 // We copy once the pair from the Elts vector 542 EXPECT_EQ(0u, CountCtorCopyAndMove::Copy); 543 // Check that the map didn't grow 544 EXPECT_EQ(Map.getNumBuckets(), NumBuckets); 545 } 546 } 547 548 TEST(StringMapCustomTest, BracketOperatorCtor) { 549 StringMap<CountCtorCopyAndMove> Map; 550 CountCtorCopyAndMove::Ctor = 0; 551 Map["abcd"]; 552 EXPECT_EQ(1u, CountCtorCopyAndMove::Ctor); 553 // Test that operator[] does not create a value when it is already in the map 554 CountCtorCopyAndMove::Ctor = 0; 555 Map["abcd"]; 556 EXPECT_EQ(0u, CountCtorCopyAndMove::Ctor); 557 } 558 559 namespace { 560 struct NonMoveableNonCopyableType { 561 int Data = 0; 562 NonMoveableNonCopyableType() = default; 563 NonMoveableNonCopyableType(int Data) : Data(Data) {} 564 NonMoveableNonCopyableType(const NonMoveableNonCopyableType &) = delete; 565 NonMoveableNonCopyableType(NonMoveableNonCopyableType &&) = delete; 566 }; 567 } 568 569 // Test that we can "emplace" an element in the map without involving map/move 570 TEST(StringMapCustomTest, EmplaceTest) { 571 StringMap<NonMoveableNonCopyableType> Map; 572 Map.try_emplace("abcd", 42); 573 EXPECT_EQ(1u, Map.count("abcd")); 574 EXPECT_EQ(42, Map["abcd"].Data); 575 } 576 577 // Test that StringMapEntryBase can handle size_t wide sizes. 578 TEST(StringMapCustomTest, StringMapEntryBaseSize) { 579 size_t LargeValue; 580 581 // Test that the entry can represent max-unsigned. 582 if (sizeof(size_t) <= sizeof(unsigned)) 583 LargeValue = std::numeric_limits<unsigned>::max(); 584 else 585 LargeValue = std::numeric_limits<unsigned>::max() + 1ULL; 586 StringMapEntryBase LargeBase(LargeValue); 587 EXPECT_EQ(LargeValue, LargeBase.getKeyLength()); 588 589 // Test that the entry can hold at least max size_t. 590 LargeValue = std::numeric_limits<size_t>::max(); 591 StringMapEntryBase LargerBase(LargeValue); 592 LargeValue = std::numeric_limits<size_t>::max(); 593 EXPECT_EQ(LargeValue, LargerBase.getKeyLength()); 594 } 595 596 // Test that StringMapEntry can handle size_t wide sizes. 597 TEST(StringMapCustomTest, StringMapEntrySize) { 598 size_t LargeValue; 599 600 // Test that the entry can represent max-unsigned. 601 if (sizeof(size_t) <= sizeof(unsigned)) 602 LargeValue = std::numeric_limits<unsigned>::max(); 603 else 604 LargeValue = std::numeric_limits<unsigned>::max() + 1ULL; 605 StringMapEntry<int> LargeEntry(LargeValue); 606 StringRef Key = LargeEntry.getKey(); 607 EXPECT_EQ(LargeValue, Key.size()); 608 609 // Test that the entry can hold at least max size_t. 610 LargeValue = std::numeric_limits<size_t>::max(); 611 StringMapEntry<int> LargerEntry(LargeValue); 612 Key = LargerEntry.getKey(); 613 EXPECT_EQ(LargeValue, Key.size()); 614 } 615 616 } // end anonymous namespace 617