unittests/ADT/StringMapTest.cpp

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