[ADT] Make iterable SmallVector template overrides more specific

[fjricci]

Summary

This prevents the iterator overrides from being selected in
the case where non-iterator types are used as arguments, which
is of particular importance in cases where other overrides with
identical types exist.

[efriedma]

include/llvm/ADT/SmallVector.h

429 ↗

(On Diff #101474)

This change doesn't do anything; typename and class are equivalent in this context. From your description, maybe you want something using std::enable_if?

[fjricci]

Enforce that template arguments are not integral types

The only possible conflicting override takes a size_type, and enforcing that the
type is not an integral type is much more straightforward than enforcing that it is
either an iterator, const iterator, pointer, or const pointer.

[fjricci]

Accidentally removed a subscriber, re-adding

[fjricci]

Add unit test and migrate to iterator SFINAE checks

[fjricci]

Add test cases for all 3 specialized methods

[fjricci]

Use input_iterator_tag

[dblaikie]

I think this is just about right - but the current SFINAE is only an exact match, so it wouldn't work for something that's, say, a RandomAccessIterator.

I believe you want to use std::is_convertible_to, rather than std::is_same (& maybe add coverage/a test case for a non-forward (for example, a random access - such as pointers to the begin/end of an array) for this).

I'm guessing using is_same should've broken some existing code in LLVM - I'm surprised it didn't break the unit test? So maybe I'm misunderstantding something about how this is working.

(I really appreciate your patience as we go around on this - sorry it's taken a few iterations)

[fjricci]

The llvm test suite passes with this change, although I haven't verified clang's does yet. I'll add a test for a random access iterator, and update the enable_if if it doesn't work correctly.

[fjricci]

assign(&arr[0], &arr[2]) fails both with is_same and is_convertible. Is that an acceptable usage of assign (and what you meant by random access iterator)? There's already a test case for assign(std::begin(arr), std::end(arr)), and that works fine with is_same.

It looks like random_access_iterator_tag inherits from input_iterator_tag (http://en.cppreference.com/w/cpp/iterator/iterator_tags), so maybe that's why is_same works?

[fjricci]

Use is_convertible and ::type

[dblaikie]

Please add a test case using a non-forward iterator to demonstrate that the traits checking is working as intended.

I think something like this, maybe:

TYPED_TEST(SmallVectorTest, InsertRepeatedNonForwardIterator) {
  struct output_iterator {
    typedef std::output_iterator_tag iterator_category;
    typedef int        value_type;
    typedef int   difference_type;
    typedef value_type*        pointer;
    typedef value_type&        reference;
    // In theory other operations would be needed here, but they shouldn't be used in this test
    operator int() { return 2; }
  };
  
  ...
  append(output_iterator(), output_iterator())
  check that the vector describes the sequence {2, 2}
}

I suppose in theory this should be tested for all 4 operations you're updating here - if there's a tidy way to do that, great, but otherwise I'd probably just test one of them.

Also there seem to be 3 test cases but 4 code changes. The ctor change isn't tested at all - could you test that?

[fjricci]

Add more testing

[dblaikie]

Looks great - thanks again for all your patience/help!

llvm/trunk/include/llvm/ADT/SmallVector.h

LLVM_NODISCARD T pop_back_val() {
     T Result = ::std::move(this->back());
     this->pop_back();
     return Result;
   }
 
   void swap(SmallVectorImpl &RHS);
 
   /// Add the specified range to the end of the SmallVector.
-  template<typename in_iter>
+  template <typename in_iter,
+            typename = typename std::enable_if<std::is_convertible<
+                typename std::iterator_traits<in_iter>::iterator_category,
+                std::input_iterator_tag>::value>::type>
   void append(in_iter in_start, in_iter in_end) {
     size_type NumInputs = std::distance(in_start, in_end);
     // Grow allocated space if needed.
     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
       this->grow(this->size()+NumInputs);
 
     // Copy the new elements over.
     this->uninitialized_copy(in_start, in_end, this->end());
public:
   void assign(size_type NumElts, const T &Elt) {
     clear();
     if (this->capacity() < NumElts)
       this->grow(NumElts);
     this->setEnd(this->begin()+NumElts);
     std::uninitialized_fill(this->begin(), this->end(), Elt);
   }
 
-  template <typename in_iter> void assign(in_iter in_start, in_iter in_end) {
+  template <typename in_iter,
+            typename = typename std::enable_if<std::is_convertible<
+                typename std::iterator_traits<in_iter>::iterator_category,
+                std::input_iterator_tag>::value>::type>
+  void assign(in_iter in_start, in_iter in_end) {
     clear();
     append(in_start, in_end);
   }
 
   void assign(std::initializer_list<T> IL) {
     clear();
     append(IL);
   }
iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
     // Replace the overwritten part.
     std::fill_n(I, NumOverwritten, Elt);
 
     // Insert the non-overwritten middle part.
     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
     return I;
   }
 
-  template<typename ItTy>
+  template <typename ItTy,
+            typename = typename std::enable_if<std::is_convertible<
+                typename std::iterator_traits<ItTy>::iterator_category,
+                std::input_iterator_tag>::value>::type>
   iterator insert(iterator I, ItTy From, ItTy To) {
     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
     size_t InsertElt = I - this->begin();
 
     if (I == this->end()) {  // Important special case for empty vector.
       append(From, To);
       return this->begin()+InsertElt;
     }

 public:
   SmallVector() : SmallVectorImpl<T>(N) {}
 
   explicit SmallVector(size_t Size, const T &Value = T())
     : SmallVectorImpl<T>(N) {
     this->assign(Size, Value);
   }
 
-  template<typename ItTy>
+  template <typename ItTy,
+            typename = typename std::enable_if<std::is_convertible<
+                typename std::iterator_traits<ItTy>::iterator_category,
+                std::input_iterator_tag>::value>::type>
   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
     this->append(S, E);
   }
 
   template <typename RangeTy>
   explicit SmallVector(const iterator_range<RangeTy> &R)
       : SmallVectorImpl<T>(N) {
     this->append(R.begin(), R.end());

llvm/trunk/unittests/ADT/SmallVectorTest.cpp

 typedef ::testing::Types<SmallVector<Constructable, 0>,
                          SmallVector<Constructable, 1>,
                          SmallVector<Constructable, 2>,
                          SmallVector<Constructable, 4>,
                          SmallVector<Constructable, 5>
                          > SmallVectorTestTypes;
 TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes);
 
+// Constructor test.
+TYPED_TEST(SmallVectorTest, ConstructorNonIterTest) {
+  SCOPED_TRACE("ConstructorTest");
+  this->theVector = SmallVector<Constructable, 2>(2, 2);
+  this->assertValuesInOrder(this->theVector, 2u, 2, 2);
+}
+
+// Constructor test.
+TYPED_TEST(SmallVectorTest, ConstructorIterTest) {
+  SCOPED_TRACE("ConstructorTest");
+  int arr[] = {1, 2, 3};
+  this->theVector =
+      SmallVector<Constructable, 4>(std::begin(arr), std::end(arr));
+  this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
+}
+
 // New vector test.
 TYPED_TEST(SmallVectorTest, EmptyVectorTest) {
   SCOPED_TRACE("EmptyVectorTest");
   this->assertEmpty(this->theVector);
   EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend());
   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 }

 TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
   SCOPED_TRACE("AppendRepeatedTest");
 
   this->theVector.push_back(Constructable(1));
   this->theVector.append(2, Constructable(77));
   this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
 }
 
+// Append test
+TYPED_TEST(SmallVectorTest, AppendNonIterTest) {
+  SCOPED_TRACE("AppendRepeatedTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(2, 7);
+  this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7);
+}
+
+TYPED_TEST(SmallVectorTest, AppendRepeatedNonForwardIterator) {
+  SCOPED_TRACE("AppendRepeatedTest");
+
+  struct output_iterator {
+    typedef std::output_iterator_tag iterator_category;
+    typedef int value_type;
+    typedef int difference_type;
+    typedef value_type *pointer;
+    typedef value_type &reference;
+    operator int() { return 2; }
+    operator Constructable() { return 7; }
+  };
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(output_iterator(), output_iterator());
+  this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7);
+}
+
 // Assign test
 TYPED_TEST(SmallVectorTest, AssignTest) {
   SCOPED_TRACE("AssignTest");
 
   this->theVector.push_back(Constructable(1));
   this->theVector.assign(2, Constructable(77));
   this->assertValuesInOrder(this->theVector, 2u, 77, 77);
 }
 
 // Assign test
 TYPED_TEST(SmallVectorTest, AssignRangeTest) {
   SCOPED_TRACE("AssignTest");
 
   this->theVector.push_back(Constructable(1));
   int arr[] = {1, 2, 3};
   this->theVector.assign(std::begin(arr), std::end(arr));
   this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
 }
 
+// Assign test
+TYPED_TEST(SmallVectorTest, AssignNonIterTest) {
+  SCOPED_TRACE("AssignTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.assign(2, 7);
+  this->assertValuesInOrder(this->theVector, 2u, 7, 7);
+}
+
 // Move-assign test
 TYPED_TEST(SmallVectorTest, MoveAssignTest) {
   SCOPED_TRACE("MoveAssignTest");
 
   // Set up our vector with a single element, but enough capacity for 4.
   this->theVector.reserve(4);
   this->theVector.push_back(Constructable(1));
   
TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
   // Copy construct the two new elements from the parameter.
   EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
   // All without any copy construction.
   EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());
   EXPECT_EQ(this->theVector.begin() + 1, I);
   this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4);
 }
 
+TYPED_TEST(SmallVectorTest, InsertRepeatedNonIterTest) {
+  SCOPED_TRACE("InsertRepeatedTest");
+
+  this->makeSequence(this->theVector, 1, 4);
+  Constructable::reset();
+  auto I = this->theVector.insert(this->theVector.begin() + 1, 2, 7);
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 6u, 1, 7, 7, 2, 3, 4);
+}
 
 TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) {
   SCOPED_TRACE("InsertRepeatedTest");
 
   this->makeSequence(this->theVector, 1, 4);
   Constructable::reset();
   auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16));
   // Just copy construct them into newly allocated space