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