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
assertEmptyMap()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
assertSingleItemMap()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.
TEST_F(StringMapTest,EmptyMapTest)81 TEST_F(StringMapTest, EmptyMapTest) {
82 assertEmptyMap();
83 }
84
85 // Constant map tests.
TEST_F(StringMapTest,ConstEmptyMapTest)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.
TEST_F(StringMapTest,SingleEntryMapTest)107 TEST_F(StringMapTest, SingleEntryMapTest) {
108 testMap[testKey] = testValue;
109 assertSingleItemMap();
110 }
111
112 // Test clear() method.
TEST_F(StringMapTest,ClearTest)113 TEST_F(StringMapTest, ClearTest) {
114 testMap[testKey] = testValue;
115 testMap.clear();
116 assertEmptyMap();
117 }
118
119 // Test erase(iterator) method.
TEST_F(StringMapTest,EraseIteratorTest)120 TEST_F(StringMapTest, EraseIteratorTest) {
121 testMap[testKey] = testValue;
122 testMap.erase(testMap.begin());
123 assertEmptyMap();
124 }
125
126 // Test erase(value) method.
TEST_F(StringMapTest,EraseValueTest)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.
TEST_F(StringMapTest,InsertAndEraseTest)134 TEST_F(StringMapTest, InsertAndEraseTest) {
135 testMap[testKey] = testValue;
136 testMap["otherKey"] = 2;
137 testMap.erase("otherKey");
138 assertSingleItemMap();
139 }
140
TEST_F(StringMapTest,SmallFullMapTest)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
TEST_F(StringMapTest,CopyCtorTest)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.
TEST_F(StringMapTest,IterationTest)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.
TEST_F(StringMapTest,StringMapEntryTest)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.
TEST_F(StringMapTest,InsertTest)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
TEST_F(StringMapTest,InsertPairTest)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
TEST_F(StringMapTest,InsertRehashingPairTest)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
TEST_F(StringMapTest,IterMapKeys)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 llvm::sort(Keys.begin(), Keys.end());
283
284 SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"};
285 EXPECT_EQ(Expected, Keys);
286 }
287
TEST_F(StringMapTest,IterSetKeys)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 llvm::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 {
StringMapTestStruct__anonca26aa8c0111::StringMapTestStruct304 StringMapTestStruct(int i) : i(i) {}
305 StringMapTestStruct() = delete;
306 int i;
307 };
308
TEST_F(StringMapTest,NonDefaultConstructable)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 {
Immovable__anonca26aa8c0111::Immovable318 Immovable() {}
319 Immovable(Immovable&&) = delete; // will disable the other special members
320 };
321
322 struct MoveOnly {
323 int i;
MoveOnly__anonca26aa8c0111::MoveOnly324 MoveOnly(int i) : i(i) {}
MoveOnly__anonca26aa8c0111::MoveOnly325 MoveOnly(const Immovable&) : i(0) {}
MoveOnly__anonca26aa8c0111::MoveOnly326 MoveOnly(MoveOnly &&RHS) : i(RHS.i) {}
operator =__anonca26aa8c0111::MoveOnly327 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
TEST_F(StringMapTest,MoveOnly)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
TEST_F(StringMapTest,CtorArg)345 TEST_F(StringMapTest, CtorArg) {
346 StringRef Key = "Test";
347 StringMapEntry<MoveOnly>::Create(Key, Immovable())
348 ->Destroy();
349 }
350
TEST_F(StringMapTest,MoveConstruct)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
TEST_F(StringMapTest,MoveAssignment)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;
Countable__anonca26aa8c0111::Countable376 Countable(int Number, int &InstanceCount)
377 : InstanceCount(InstanceCount), Number(Number) {
378 ++InstanceCount;
379 }
Countable__anonca26aa8c0111::Countable380 Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) {
381 ++InstanceCount;
382 C.Number = -1;
383 }
Countable__anonca26aa8c0111::Countable384 Countable(const Countable &C)
385 : InstanceCount(C.InstanceCount), Number(C.Number) {
386 ++InstanceCount;
387 }
operator =__anonca26aa8c0111::Countable388 Countable &operator=(Countable C) {
389 Number = C.Number;
390 return *this;
391 }
~Countable__anonca26aa8c0111::Countable392 ~Countable() { --InstanceCount; }
393 };
394
TEST_F(StringMapTest,MoveDtor)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;
CountCtorCopyAndMove__anonca26aa8c0111::__anonca26aa8c0211::CountCtorCopyAndMove424 CountCtorCopyAndMove(int Data) : Data(Data) { Ctor++; }
CountCtorCopyAndMove__anonca26aa8c0111::__anonca26aa8c0211::CountCtorCopyAndMove425 CountCtorCopyAndMove() { Ctor++; }
426
CountCtorCopyAndMove__anonca26aa8c0111::__anonca26aa8c0211::CountCtorCopyAndMove427 CountCtorCopyAndMove(const CountCtorCopyAndMove &) { Copy++; }
operator =__anonca26aa8c0111::__anonca26aa8c0211::CountCtorCopyAndMove428 CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &) {
429 Copy++;
430 return *this;
431 }
CountCtorCopyAndMove__anonca26aa8c0111::__anonca26aa8c0211::CountCtorCopyAndMove432 CountCtorCopyAndMove(CountCtorCopyAndMove &&) { Move++; }
operator =__anonca26aa8c0111::__anonca26aa8c0211::CountCtorCopyAndMove433 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.
TEST(StringMapCustomTest,InitialSizeTest)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
TEST(StringMapCustomTest,BracketOperatorCtor)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;
NonMoveableNonCopyableType__anonca26aa8c0111::__anonca26aa8c0311::NonMoveableNonCopyableType482 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
TEST(StringMapCustomTest,EmplaceTest)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.
TEST(StringMapCustomTest,StringMapEntryBaseSize)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.
TEST(StringMapCustomTest,StringMapEntrySize)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
536