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