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