[ADT] Fix a bug in DenseSet's initializer_list constructor.

[lhames]

Summary

Without this fix, DenseSet crashes with an assertion if constructed with an
initializer_list whose length is not a power of two.

[dblaikie]

unittests/ADT/DenseSetTest.cpp

83–87

"Don't crash" tests always look a bit suspect to me (like "test that this does anything other than crash" is not a particularly strong constraint). Maybe test that it contains the desired contents after such construction, and/or that the capacity or buckets or whatever is the expected power of two?

[craig.topper]

include/llvm/ADT/DenseSet.h

71

Shouldn’t this be PowerOf2Ceil? NextPowerOf2 will change a number that is already a power of 2.

[lhames]

include/llvm/ADT/DenseSet.h

71

Yes it should. Thanks!

unittests/ADT/DenseSetTest.cpp

83–87

I only use a "don't crash" test if the other aspects are tested elsewhere. In this case they're covered by the test above, which just happened to have a power-of-two length initializer (or we would have noticed this bug earlier).

I do not suppose there's any harm in doing a sanity check on the content in the non power-of-two case though. I'll add one.

[lhames]

Use PowerOf2Ceil as per Craig's suggestion, and validate set contents in the non power-of-two length initializer list unit test as per Dave's suggestion.

[dblaikie]

Looks good to me (I guess the capacity thing there could be tested too - ensuring that it didn't roll up to a larger capacity than intended?)

[lhames]

Committed as r344542.

In D53260#1265686, @dblaikie wrote:

Looks good to me (I guess the capacity thing there could be tested too - ensuring that it didn't roll up to a larger capacity than intended?)

Unfortunately DenseSet / DenseMap do not expose a capacity function at the moment. I believe it's just getNumBuckets, so unless there is some reason not to I would be in favor of adding a public 'capacity' function that returns that. Then we could add that check to the unit test.

[dexonsmith]

In D53260#1265712, @lhames wrote:

Committed as r344542.

In D53260#1265686, @dblaikie wrote:

Looks good to me (I guess the capacity thing there could be tested too - ensuring that it didn't roll up to a larger capacity than intended?)

Unfortunately DenseSet / DenseMap do not expose a capacity function at the moment. I believe it's just getNumBuckets, so unless there is some reason not to I would be in favor of adding a public 'capacity' function that returns that. Then we could add that check to the unit test.

Capacity is the number of elements that can be held without additional allocation, right? So that would be closer to getNumBuckets()/4*3.

include/llvm/ADT/DenseSet.h

 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Support/type_traits.h"
 #include <algorithm>
 #include <cstddef>

   explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
 
   DenseSetImpl(std::initializer_list<ValueT> Elems)
-      : DenseSetImpl(Elems.size()) {
+      : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
     insert(Elems.begin(), Elems.end());
   }
 

unittests/ADT/DenseSetTest.cpp

   EXPECT_EQ(0u, set.count(3));
 }
 
+TYPED_TEST(DenseSetTest, InitializerListWithNonPowerOfTwoLength) {
+  TypeParam set({1, 2, 3});
+  EXPECT_EQ(3u, set.size());
+  EXPECT_EQ(1u, set.count(1));
+  EXPECT_EQ(1u, set.count(2));
+  EXPECT_EQ(1u, set.count(3));
+}
+
 TYPED_TEST(DenseSetTest, ConstIteratorComparison) {
   TypeParam set({1});
   const TypeParam &cset = set;