unittests/ADT/StringMapTest.cpp

   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   StringMap<uint32_t>::value_type* entry =
 228       StringMap<uint32_t>::value_type::Create(
 229           StringRef(testKeyFirst, testKeyLength), 1u);
 230   EXPECT_STREQ(testKey, entry->first().data());
 231   EXPECT_EQ(1u, entry->second);
 232   free(entry);
 233 }
 234
 235 // Test insert() method.
 236 TEST_F(StringMapTest, InsertTest) {
 237   SCOPED_TRACE("InsertTest");
 238   testMap.insert(
 239       StringMap<uint32_t>::value_type::Create(
 240           StringRef(testKeyFirst, testKeyLength),
 241           testMap.getAllocator(), 1u));
 242   assertSingleItemMap();
 243 }
 244
 245 // Test insert(pair<K, V>) method
 246 TEST_F(StringMapTest, InsertPairTest) {
 247   bool Inserted;
 248   StringMap<uint32_t>::iterator NewIt;
 249   std::tie(NewIt, Inserted) =
 250       testMap.insert(std::make_pair(testKeyFirst, testValue));
 251   EXPECT_EQ(1u, testMap.size());
 252   EXPECT_EQ(testValue, testMap[testKeyFirst]);
 253   EXPECT_EQ(testKeyFirst, NewIt->first());
 254   EXPECT_EQ(testValue, NewIt->second);
 255   EXPECT_TRUE(Inserted);
 256
 257   StringMap<uint32_t>::iterator ExistingIt;
 258   std::tie(ExistingIt, Inserted) =
 259       testMap.insert(std::make_pair(testKeyFirst, testValue + 1));
 260   EXPECT_EQ(1u, testMap.size());
 261   EXPECT_EQ(testValue, testMap[testKeyFirst]);
 262   EXPECT_FALSE(Inserted);
 263   EXPECT_EQ(NewIt, ExistingIt);
 264 }
 265
 266 // Test insert(pair<K, V>) method when rehashing occurs
 267 TEST_F(StringMapTest, InsertRehashingPairTest) {
 268   // Check that the correct iterator is returned when the inserted element is
 269   // moved to a different bucket during internal rehashing. This depends on
 270   // the particular key, and the implementation of StringMap and HashString.
 271   // Changes to those might result in this test not actually checking that.
 272   StringMap<uint32_t> t(0);
 273   EXPECT_EQ(0u, t.getNumBuckets());
 274
 275   StringMap<uint32_t>::iterator It =
 276     t.insert(std::make_pair("abcdef", 42)).first;
 277   EXPECT_EQ(16u, t.getNumBuckets());
 278   EXPECT_EQ("abcdef", It->first());
 279   EXPECT_EQ(42u, It->second);
 280 }
 281
 282 TEST_F(StringMapTest, InsertOrAssignTest) {
 283   struct A : CountCopyAndMove {
 284     A(int v) : v(v) {}
 285     int v;
 286   };
 287   StringMap<A> t(0);
 288
 289   auto try1 = t.insert_or_assign("A", A(1));
 290   EXPECT_TRUE(try1.second);
 291   EXPECT_EQ(1, try1.first->second.v);
 292   EXPECT_EQ(1, try1.first->second.move);
 293
 294   auto try2 = t.insert_or_assign("A", A(2));
 295   EXPECT_FALSE(try2.second);
 296   EXPECT_EQ(2, try2.first->second.v);
 297   EXPECT_EQ(2, try1.first->second.move);
 298
 299   EXPECT_EQ(try1.first, try2.first);
 300   EXPECT_EQ(0, try1.first->second.copy);
 301 }
 302
 303 TEST_F(StringMapTest, IterMapKeys) {
 304   StringMap<int> Map;
 305   Map["A"] = 1;
 306   Map["B"] = 2;
 307   Map["C"] = 3;
 308   Map["D"] = 3;
 309
 310   auto Keys = to_vector<4>(Map.keys());
 311   llvm::sort(Keys);
 312
 313   SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"};
 314   EXPECT_EQ(Expected, Keys);
 315 }
 316
 317 // Create a non-default constructable value
 318 struct StringMapTestStruct {
 319   StringMapTestStruct(int i) : i(i) {}
 320   StringMapTestStruct() = delete;
 321   int i;
 322 };
 323
 324 TEST_F(StringMapTest, NonDefaultConstructable) {
 325   StringMap<StringMapTestStruct> t;
 326   t.insert(std::make_pair("Test", StringMapTestStruct(123)));
 327   StringMap<StringMapTestStruct>::iterator iter = t.find("Test");
 328   ASSERT_NE(iter, t.end());
 329   ASSERT_EQ(iter->second.i, 123);
 330 }
 331
 332 struct Immovable {
 333   Immovable() {}
 334   Immovable(Immovable&&) = delete; // will disable the other special members
 335 };
 336
 337 struct MoveOnly {
 338   int i;
 339   MoveOnly(int i) : i(i) {}
 340   MoveOnly(const Immovable&) : i(0) {}
 341   MoveOnly(MoveOnly &&RHS) : i(RHS.i) {}
 342   MoveOnly &operator=(MoveOnly &&RHS) {
 343     i = RHS.i;
 344     return *this;
 345   }
 346
 347 private:
 348   MoveOnly(const MoveOnly &) = delete;
 349   MoveOnly &operator=(const MoveOnly &) = delete;
 350 };
 351
 352 TEST_F(StringMapTest, MoveOnly) {
 353   StringMap<MoveOnly> t;
 354   t.insert(std::make_pair("Test", MoveOnly(42)));
 355   StringRef Key = "Test";
 356   StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42))
 357       ->Destroy();
 358 }
 359
 360 TEST_F(StringMapTest, CtorArg) {
 361   StringRef Key = "Test";
 362   StringMapEntry<MoveOnly>::Create(Key, Immovable())
 363       ->Destroy();
 364 }
 365
 366 TEST_F(StringMapTest, MoveConstruct) {
 367   StringMap<int> A;
 368   A["x"] = 42;
 369   StringMap<int> B = std::move(A);
 370   ASSERT_EQ(A.size(), 0u);
 371   ASSERT_EQ(B.size(), 1u);
 372   ASSERT_EQ(B["x"], 42);
 373   ASSERT_EQ(B.count("y"), 0u);
 374 }
 375
 376 TEST_F(StringMapTest, MoveAssignment) {
 377   StringMap<int> A;
 378   A["x"] = 42;
 379   StringMap<int> B;
 380   B["y"] = 117;
 381   A = std::move(B);
 382   ASSERT_EQ(A.size(), 1u);
 383   ASSERT_EQ(B.size(), 0u);
 384   ASSERT_EQ(A["y"], 117);
 385   ASSERT_EQ(B.count("x"), 0u);
 386 }
 387
 388 struct Countable {
 389   int &InstanceCount;
 390   int Number;
 391   Countable(int Number, int &InstanceCount)
 392       : InstanceCount(InstanceCount), Number(Number) {
 393     ++InstanceCount;
 394   }
 395   Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) {
 396     ++InstanceCount;
 397     C.Number = -1;
 398   }
 399   Countable(const Countable &C)
 400       : InstanceCount(C.InstanceCount), Number(C.Number) {
 401     ++InstanceCount;
 402   }
 403   Countable &operator=(Countable C) {
 404     Number = C.Number;
 405     return *this;
 406   }
 407   ~Countable() { --InstanceCount; }
 408 };
 409
 410 TEST_F(StringMapTest, MoveDtor) {
 411   int InstanceCount = 0;
 412   StringMap<Countable> A;
 413   A.insert(std::make_pair("x", Countable(42, InstanceCount)));
 414   ASSERT_EQ(InstanceCount, 1);
 415   auto I = A.find("x");
 416   ASSERT_NE(I, A.end());
 417   ASSERT_EQ(I->second.Number, 42);
 418
 419   StringMap<Countable> B;
 420   B = std::move(A);
 421   ASSERT_EQ(InstanceCount, 1);
 422   ASSERT_TRUE(A.empty());
 423   I = B.find("x");
 424   ASSERT_NE(I, B.end());
 425   ASSERT_EQ(I->second.Number, 42);
 426
 427   B = StringMap<Countable>();
 428   ASSERT_EQ(InstanceCount, 0);
 429   ASSERT_TRUE(B.empty());
 430 }
 431
 432 namespace {
 433 // Simple class that counts how many moves and copy happens when growing a map
 434 struct CountCtorCopyAndMove {
 435   static unsigned Ctor;
 436   static unsigned Move;
 437   static unsigned Copy;
 438   int Data = 0;
 439   CountCtorCopyAndMove(int Data) : Data(Data) { Ctor++; }
 440   CountCtorCopyAndMove() { Ctor++; }
 441
 442   CountCtorCopyAndMove(const CountCtorCopyAndMove &) { Copy++; }
 443   CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &) {
 444     Copy++;
 445     return *this;
 446   }
 447   CountCtorCopyAndMove(CountCtorCopyAndMove &&) { Move++; }
 448   CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &&) {
 449     Move++;
 450     return *this;
 451   }
 452 };
 453 unsigned CountCtorCopyAndMove::Copy = 0;
 454 unsigned CountCtorCopyAndMove::Move = 0;
 455 unsigned CountCtorCopyAndMove::Ctor = 0;
 456
 457 } // anonymous namespace
 458
 459 // Make sure creating the map with an initial size of N actually gives us enough
 460 // buckets to insert N items without increasing allocation size.
 461 TEST(StringMapCustomTest, InitialSizeTest) {
 462   // 1 is an "edge value", 32 is an arbitrary power of two, and 67 is an
 463   // arbitrary prime, picked without any good reason.
 464   for (auto Size : {1, 32, 67}) {
 465     StringMap<CountCtorCopyAndMove> Map(Size);
 466     auto NumBuckets = Map.getNumBuckets();
 467     CountCtorCopyAndMove::Move = 0;
 468     CountCtorCopyAndMove::Copy = 0;
 469     for (int i = 0; i < Size; ++i)
 470       Map.insert(std::pair<std::string, CountCtorCopyAndMove>(
 471           std::piecewise_construct, std::forward_as_tuple(Twine(i).str()),
 472           std::forward_as_tuple(i)));
 473     // After the initial move, the map will move the Elts in the Entry.
 474     EXPECT_EQ((unsigned)Size * 2, CountCtorCopyAndMove::Move);
 475     // We copy once the pair from the Elts vector
 476     EXPECT_EQ(0u, CountCtorCopyAndMove::Copy);
 477     // Check that the map didn't grow
 478     EXPECT_EQ(Map.getNumBuckets(), NumBuckets);
 479   }
 480 }
 481
 482 TEST(StringMapCustomTest, BracketOperatorCtor) {
 483   StringMap<CountCtorCopyAndMove> Map;
 484   CountCtorCopyAndMove::Ctor = 0;
 485   Map["abcd"];
 486   EXPECT_EQ(1u, CountCtorCopyAndMove::Ctor);
 487   // Test that operator[] does not create a value when it is already in the map
 488   CountCtorCopyAndMove::Ctor = 0;
 489   Map["abcd"];
 490   EXPECT_EQ(0u, CountCtorCopyAndMove::Ctor);
 491 }
 492
 493 namespace {
 494 struct NonMoveableNonCopyableType {
 495   int Data = 0;
 496   NonMoveableNonCopyableType() = default;
 497   NonMoveableNonCopyableType(int Data) : Data(Data) {}
 498   NonMoveableNonCopyableType(const NonMoveableNonCopyableType &) = delete;
 499   NonMoveableNonCopyableType(NonMoveableNonCopyableType &&) = delete;
 500 };
 501 }
 502
 503 // Test that we can "emplace" an element in the map without involving map/move
 504 TEST(StringMapCustomTest, EmplaceTest) {
 505   StringMap<NonMoveableNonCopyableType> Map;
 506   Map.try_emplace("abcd", 42);
 507   EXPECT_EQ(1u, Map.count("abcd"));
 508   EXPECT_EQ(42, Map["abcd"].Data);
 509 }
 510
 511 // Test that StringMapEntryBase can handle size_t wide sizes.
 512 TEST(StringMapCustomTest, StringMapEntryBaseSize) {
 513   size_t LargeValue;
 514
 515   // Test that the entry can represent max-unsigned.
 516   if (sizeof(size_t) <= sizeof(unsigned))
 517     LargeValue = std::numeric_limits<unsigned>::max();
 518   else
 519     LargeValue = std::numeric_limits<unsigned>::max() + 1ULL;
 520   StringMapEntryBase LargeBase(LargeValue);
 521   EXPECT_EQ(LargeValue, LargeBase.getKeyLength());
 522
 523   // Test that the entry can hold at least max size_t.
 524   LargeValue = std::numeric_limits<size_t>::max();
 525   StringMapEntryBase LargerBase(LargeValue);
 526   LargeValue = std::numeric_limits<size_t>::max();
 527   EXPECT_EQ(LargeValue, LargerBase.getKeyLength());
 528 }
 529
 530 // Test that StringMapEntry can handle size_t wide sizes.
 531 TEST(StringMapCustomTest, StringMapEntrySize) {
 532   size_t LargeValue;
 533
 534   // Test that the entry can represent max-unsigned.
 535   if (sizeof(size_t) <= sizeof(unsigned))
 536     LargeValue = std::numeric_limits<unsigned>::max();
 537   else
 538     LargeValue = std::numeric_limits<unsigned>::max() + 1ULL;
 539   StringMapEntry<int> LargeEntry(LargeValue);
 540   StringRef Key = LargeEntry.getKey();
 541   EXPECT_EQ(LargeValue, Key.size());
 542
 543   // Test that the entry can hold at least max size_t.
 544   LargeValue = std::numeric_limits<size_t>::max();
 545   StringMapEntry<int> LargerEntry(LargeValue);
 546   Key = LargerEntry.getKey();
 547   EXPECT_EQ(LargeValue, Key.size());
 548 }
 549
 550 } // end anonymous namespace