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/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