[NFC] Introduce llvm::to_vector_of to allow creation of SmallVector<T> from range of items convertible to type T

[yurai007]

Summary

It's https://reviews.llvm.org/D129565 follow-up.

[yurai007]

llvm/include/llvm/ADT/SmallVector.h

1290

TODO: add more tests to make sure there is no surprises coming from overloading rules

llvm/unittests/ADT/SmallVectorTest.cpp

1145

That's basically copy of STLExtrasTest.ToVector test body after removing enumerate() calls. I feel it make sense to have it here since to_vector belongs to SmallVector.

[nikic]

llvm/include/llvm/ADT/SmallVector.h

1285–1286

Why do we need to explicitly pass InlineSize<R>::value? Isn't that the default anyway?

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp

814 ↗

(On Diff #444678)

llvm prefix unnecessary

[nikic]

By the way, I think it would be worthwhile to add an ArrayRef constructor to SmallVector, or else drop the existing iterator_range ctor. I've wanted to switch an iterator_range to ArrayRef a few times in the past, and always gave up due to the SmallVector fallout. We should support both or neither.

[dexonsmith]

In D129781#3652424, @nikic wrote:

By the way, I think it would be worthwhile to add an ArrayRef constructor to SmallVector, or else drop the existing iterator_range ctor. I've wanted to switch an iterator_range to ArrayRef a few times in the past, and always gave up due to the SmallVector fallout. We should support both or neither.

“Neither” makes some sense to me, since to_vector and to_vector_of are clear and support any range naturally. @dblaikie, any thoughts?

[dblaikie]

In D129781#3652460, @dexonsmith wrote:

In D129781#3652424, @nikic wrote:

By the way, I think it would be worthwhile to add an ArrayRef constructor to SmallVector, or else drop the existing iterator_range ctor. I've wanted to switch an iterator_range to ArrayRef a few times in the past, and always gave up due to the SmallVector fallout. We should support both or neither.

“Neither” makes some sense to me, since to_vector and to_vector_of are clear and support any range naturally. @dblaikie, any thoughts?

Yeah, I'd tend to lean that way - if std::vector doesn't have generic range-based construction, I'm happy with SmallVector not having it either.

llvm/include/llvm/ADT/SmallVector.h

1295–1298

Rather than an overload, can the Size parameter have a default value in the other definition and this overload can be removed?

[yurai007]

Remove WIP tag since overall direction seem to be fine and now all tests are passing (at least locally). Address some comments.

[yurai007]

llvm/include/llvm/ADT/SmallVector.h

1285–1286

Yes, it's indeed redundant! Interesting, I didn't even bother thinking about removing it since it was present on to_vector before my change. And given that's about widely used SmallVector header I didn't expect that it could have anything superfluous.

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

1285–1286

Maybe it predates SmallVector itself having a default? Or maybe it has some hard-to-predict impact on compile time? You might be able to figure that out via a git-blame and/or a look at the original review thread, or you can ask the author that added it (if it was me, I don’t remember :)). Most likely it can just be skipped though.

[yurai007]

In D129781#3653012, @dblaikie wrote:

In D129781#3652460, @dexonsmith wrote:

In D129781#3652424, @nikic wrote:

By the way, I think it would be worthwhile to add an ArrayRef constructor to SmallVector, or else drop the existing iterator_range ctor. I've wanted to switch an iterator_range to ArrayRef a few times in the past, and always gave up due to the SmallVector fallout. We should support both or neither.

“Neither” makes some sense to me, since to_vector and to_vector_of are clear and support any range naturally. @dblaikie, any thoughts?

Yeah, I'd tend to lean that way - if std::vector doesn't have generic range-based construction, I'm happy with SmallVector not having it either.

All right, I will prepare separate change for this.

[yurai007]

llvm/include/llvm/ADT/SmallVector.h

1295–1298

The thing is we need to compute default Size from R which is Size's successor on template parameter list. We can reorder list and it would work as long as Size is default:

 template <typename Out, typename R, unsigned Size = CalculateSmallVectorDefaultInlinedElements<
             ValueTypeFromRangeType<R>>::value>
  SmallVector<Out, Size> to_vector_of(R &&Range) {
  return {std::begin(Range), std::end(Range)};
}

However when Size is non-default both preceding types Out, R need to be passed explicitly during instantiation. If I understand it correctly, that was reason for having 2 definitions of to_vector function - for similar reason they couldn't be merged into one. It would be much easier if Size depended on Out instead but except some special scenarios when it's allowed (pointer types), in general I don't think we can rely on this.

[yurai007]

Replace to_vector_of usage with to_vector where possible, improve names in ToVectorOf test case. All comments should be addressed now.

[yurai007]

Some cosmetic changes in tests.

[yurai007]

Ping

[dblaikie]

Might be worth submitting this separately/without updating all the callers - so that if a caller has to be reverted for some reason we don't have to revert the functionality and testing, etc, itself? (callers could probably done in reasonable chunks - 10s, maybe 50 at a time? huge patches are a bit awkward (again, in terms of bisecting/reverting/etc) but doing one patch for each caller's probably excessive too - somewhere in between)

llvm/include/llvm/ADT/SmallVector.h

1285–1286

Patch might be easier to read if these were removed in a separate patch, if they can be separate? (looks like they should be/are unrelated to the addition of to_vector_of?

llvm/unittests/ADT/SmallVectorTest.cpp

1145

We shouldn't duplicate tests - if to_vector is in SmallVector.h, it should be tested in SmallVectorTest.cpp, not in STLExtrasTest.cpp - so it should probably be moved here, rather than copied - and that could be done in a preliminary/separate commit?

1169–1171

Generally prefer non-member overloads where possible to allow for equal conversions for LHS and RHS. In this case it could be a friend to make it easy to write inline

1174–1184

This seems a bit too specific? Emulating a particular LLVM data type like MDOperand - could this be named/designed more generally/abstractly so as not to be overloaded with the specifics of some LLVM detail?

[hiraditya]

would it be possible to specialize cast<> for this?

[dblaikie]

In D129781#3686041, @hiraditya wrote:

would it be possible to specialize cast<> for this?

Seems like a stretch for the concept/definition of cast<> though I recall there are some novel implementations of cast for other types - so I'm open to an argument to the contrary, that this conversion would be consistent with others implemented via cast<>.

[nikic]

I think cast<> comes with the implication that the conversion is zero-cost (in non-assert builds), which is not the case here. to_vector() is an expensive O(n) operation.

[yurai007]

llvm/include/llvm/ADT/SmallVector.h

1285–1286

You are right, I can extract it to separate patch.

llvm/unittests/ADT/SmallVectorTest.cpp

1145

We shouldn't duplicate tests - if to_vector is in SmallVector.h, it should be tested in SmallVectorTest.cpp, not in STLExtrasTest.cpp - so it should probably be moved here, rather than copied - and that could be done in a preliminary/separate commit?

I would agree except the fact that STLExtrasTest.ToVector is not exactly 1-1 copy because it has enumerate() call (STLExtras.h) and I believe it tests both to_vector and enumerate functions. There are following options I see right now:

1. We can cut and paste STLExtrasTest.ToVector here without any modification (well, except test case name), but it requires extra include for enumerate(). That enumerate is not really needed for purpose of testing to_vector function.
2. We can simply remove STLExtrasTest.ToVector and leave SmallVectorTest.ToVector as it is but I'm a bit paranoid about removing unit test covering enumerate since it smells like regression.
3. We can leave STLExtrasTest.ToVector as it is, and copy it to SmallVectorTest.ToVector with enumerate (because it's irrelevant) removal. That's chosen option.

1169–1171

Ok. I will fix it.

1174–1184

I thought there would be some value in referring to MDOperand/Metadata classes since that was background for this patch: https://reviews.llvm.org/D129565#3648665 But I get your point - what matters here is just property of MDOperand being convertible to Metadata. I can use 'From' and 'To' names as more appropriate in expressing conversion.
Short information about original, motivational use case can be simply put in 'Summary'/commit message.

[yurai007]

In D129781#3685752, @dblaikie wrote:

Might be worth submitting this separately/without updating all the callers - so that if a caller has to be reverted for some reason we don't have to revert the functionality and testing, etc, itself? (callers could probably done in reasonable chunks - 10s, maybe 50 at a time? huge patches are a bit awkward (again, in terms of bisecting/reverting/etc) but doing one patch for each caller's probably excessive too - somewhere in between)

Ok. I'm gonna split it in such way.

[yurai007]

Addressed comments.

[dblaikie]

llvm/unittests/ADT/SmallVectorTest.cpp

877–880

This could be a constexpr variable template, maybe? & then the EXPECT_TRUEs testing this could instead be static_assert rather than runtime tests?

1174–1184

Yep, that's the thinking!

Maybe we can even remove the fact that one side of this is a pointer, and the other a value? Have both sides be values (eg: SmallVector<From> -> SmallVector<To>)? Shouldn't be any need for so many operations on From or To either (eg: the operator *, operator From * (I'd expect the only conversion should be the To(From) ctor), get(), etc) - probably From and To can be structs, maybe with a single int member that gets copied on conversion, so that can be checked on the other side of the conversion?)

1187–1189

Oh, looks like this is backwards, maybe? I'd expect the source type to be To and the destination type to be From, so more like to_vector_of<To>(SomeFromVector)?

1188–1227

I guess this is how the other to_vectors were already tested? But if you're up for it in a pre or post commit, might be nice to simplify this - like I'm not sure it's necessary to test all these variants. The implementation is generic - it tests anything you can do begin(x) and end(x) on, so we probably only need to test one such type? But if we really want to test 4, perhaps we can avoid rewriting the code and use a type expansion in gunit?)

[yurai007]

Address all recent comments.

[yurai007]

llvm/unittests/ADT/SmallVectorTest.cpp

1188–1227

I agree it's not necessary so eventually decided to remove ArrayRef variants.

[yurai007]

llvm/unittests/ADT/SmallVectorTest.cpp

1150

For now message argument is required, soon after https://reviews.llvm.org/D130689 could be removed. Anyway if needed may be done in separate NFC.

[yurai007]

Rebase and adjust to C++17 (static_asserts)

[dblaikie]

Looks good

[yurai007]

In D129781#3713421, @dblaikie wrote:

Looks good

@nikic @dblaikie @dexonsmith: Great. Thank you all for the review!

llvm/include/llvm/ADT/SmallVector.h

 
 /// Given a range of type R, iterate the entire range and return a
 /// SmallVector with elements of the vector.  This is useful, for example,
 /// when you want to iterate a range and then sort the results.
 template <unsigned Size, typename R>
 SmallVector<ValueTypeFromRangeType<R>, Size> to_vector(R &&Range) {
   return {std::begin(Range), std::end(Range)};
 }
 template <typename R>
 SmallVector<ValueTypeFromRangeType<R>> to_vector(R &&Range) {
   return {std::begin(Range), std::end(Range)};
 }
 
+template <typename Out, unsigned Size, typename R>
+SmallVector<Out, Size> to_vector_of(R &&Range) {
+  return {std::begin(Range), std::end(Range)};
+}
+
+template <typename Out, typename R> SmallVector<Out> to_vector_of(R &&Range) {
+  return {std::begin(Range), std::end(Range)};
+}
+
 } // end namespace llvm
 
 namespace std {
 
   /// Implement std::swap in terms of SmallVector swap.
   template<typename T>
   inline void
   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {

llvm/unittests/ADT/SmallVectorTest.cpp

 // Generate a sequence of values to initialize the vector.
 template <typename VectorT> void makeSequence(VectorT &v, int start, int end) {
   for (int i = start; i <= end; ++i) {
     v.push_back(Constructable(i));
   }
 }
 
 template <typename T, unsigned N>
-static unsigned NumBuiltinElts(const SmallVector<T, N> &) {
+constexpr static unsigned NumBuiltinElts(const SmallVector<T, N> &) {
   return N;
 }
 
 class SmallVectorTestBase : public testing::Test {
 protected:
   void SetUp() override { Constructable::reset(); }
 };
 

 TYPED_TEST(SmallVectorTest, IteratorTest) {
   auto &V = this->theVector;
   std::list<int> L;
   V.insert(V.end(), L.begin(), L.end());
 }
 
 template <typename InvalidType> class DualSmallVectorsTest;
 
 template <typename VectorT1, typename VectorT2>
 class DualSmallVectorsTest<std::pair<VectorT1, VectorT2>> : public SmallVectorTestBase {
 protected:
   VectorT1 theVector;
   VectorT2 otherVector;
 };
 
 typedef ::testing::Types<
     // Small mode -> Small mode.
     std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 4>>,
     // Small mode -> Big mode.
     std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 2>>,
TEST(SmallVectorTest, InitializerList) {
   V2.assign({4});
   EXPECT_TRUE(makeArrayRef(V2).equals({4}));
   V2.append({3, 2});
   EXPECT_TRUE(makeArrayRef(V2).equals({4, 3, 2}));
   V2.insert(V2.begin() + 1, 5);
   EXPECT_TRUE(makeArrayRef(V2).equals({4, 5, 3, 2}));
 }
 
+TEST(SmallVectorTest, ToVector) {
+  {
+    std::vector<char> v = {'a', 'b', 'c'};
+    auto Vector = to_vector<4>(v);
+    static_assert(NumBuiltinElts(Vector) == 4u);
+    ASSERT_EQ(3u, Vector.size());
+    for (size_t I = 0; I < v.size(); ++I)
+      EXPECT_EQ(v[I], Vector[I]);
+  }
+  {
+    std::vector<char> v = {'a', 'b', 'c'};
+    auto Vector = to_vector(v);
+    static_assert(NumBuiltinElts(Vector) != 4u);
+    ASSERT_EQ(3u, Vector.size());
+    for (size_t I = 0; I < v.size(); ++I)
+      EXPECT_EQ(v[I], Vector[I]);
+  }
+}
+
 struct To {
   int Content;
   friend bool operator==(const To &LHS, const To &RHS) {
     return LHS.Content == RHS.Content;
   }
 };
 
 class From {
 public:
   From() = default;
   From(To M) { T = M; }
   operator To() const { return T; }
 
 private:
   To T;
 };
 
 TEST(SmallVectorTest, ConstructFromArrayRefOfConvertibleType) {
   To to1{1}, to2{2}, to3{3};
   std::vector<From> StdVector = {From(to1), From(to2), From(to3)};
   ArrayRef<From> Array = StdVector;
   {
     llvm::SmallVector<To> Vector(Array);
 
     ASSERT_EQ(Array.size(), Vector.size());
     for (size_t I = 0; I < Array.size(); ++I)
       EXPECT_EQ(Array[I], Vector[I]);
   }
   {
     llvm::SmallVector<To, 4> Vector(Array);
 
     ASSERT_EQ(Array.size(), Vector.size());
     ASSERT_EQ(4u, NumBuiltinElts(Vector));
     for (size_t I = 0; I < Array.size(); ++I)
       EXPECT_EQ(Array[I], Vector[I]);
   }
 }
 
+TEST(SmallVectorTest, ToVectorOf) {
+  To to1{1}, to2{2}, to3{3};
+  std::vector<From> StdVector = {From(to1), From(to2), From(to3)};
+  {
+    llvm::SmallVector<To> Vector = llvm::to_vector_of<To>(StdVector);
+
+    ASSERT_EQ(StdVector.size(), Vector.size());
+    for (size_t I = 0; I < StdVector.size(); ++I)
+      EXPECT_EQ(StdVector[I], Vector[I]);
+  }
+  {
+    auto Vector = llvm::to_vector_of<To, 4>(StdVector);
+
+    ASSERT_EQ(StdVector.size(), Vector.size());
+    static_assert(NumBuiltinElts(Vector) == 4u);
+    for (size_t I = 0; I < StdVector.size(); ++I)
+      EXPECT_EQ(StdVector[I], Vector[I]);
+  }
+}
+
 template <class VectorT>
 class SmallVectorReferenceInvalidationTest : public SmallVectorTestBase {
 protected:
   const char *AssertionMessage =
       "Attempting to reference an element of the vector in an operation \" "
       "\"that invalidates it";
 
   VectorT V;
 
   template <class T> static bool isValueType() {
     return std::is_same<T, typename VectorT::value_type>::value;
   }
 
   void SetUp() override {
class SmallVectorInternalReferenceInvalidationTest
     : public SmallVectorTestBase {
 protected:
   const char *AssertionMessage =
       "Attempting to reference an element of the vector in an operation \" "
       "\"that invalidates it";
 
   VectorT V;
 
-  template <typename T, unsigned N>
-  static unsigned NumBuiltinElts(const SmallVector<T, N> &) {
-    return N;
-  }
-
   void SetUp() override {
     SmallVectorTestBase::SetUp();
 
     // Fill up the small size so that insertions move the elements.
     for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)
       V.emplace_back(I + 1, I + 1);
   }
 };