ADT: Fix pointer comparison UB in SmallVector

[dexonsmith]

Summary

The standard requires comparisons of pointers to unrelated storage to
use std::less. Split out some helpers that do that and update all the
code that was comparing using < and friends (mostly assertions).

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

636

Note that this assertion (and a couple of others) would start firing on I == this->end(), but in each case that has been handled by an early return.

[dblaikie]

llvm/include/llvm/ADT/SmallVector.h

142

155

Should be able to use std::less<>, I think? Though given the need for 3 calls, probably still nice to alias it like you have.

[dexonsmith]

Thanks for the review! Committed with your suggestions in 5ccff5aaa68ab789834c4463ce05b05e57593b34.

llvm/include/llvm/ADT/SmallVector.h

protected:
   bool isSmall() const { return this->BeginX == getFirstEl(); }
 
   /// Put this vector in a state of being small.
   void resetToSmall() {
     this->BeginX = getFirstEl();
     this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
   }
 
+  /// Return true if V is an internal reference to the given range.
+  bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
+    // Use std::less to avoid UB.
+    std::less<> LessThan;
+    return !LessThan(V, First) && LessThan(V, Last);
+  }
+
+  /// Return true if V is an internal reference to this vector.
+  bool isReferenceToStorage(const void *V) const {
+    return isReferenceToRange(V, this->begin(), this->end());
+  }
+
+  /// Return true if First and Last form a valid (possibly empty) range in this
+  /// vector's storage.
+  bool isRangeInStorage(const void *First, const void *Last) const {
+    // Use std::less to avoid UB.
+    std::less<> LessThan;
+    return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
+           !LessThan(this->end(), Last);
+  }
+
   /// Return true unless Elt will be invalidated by resizing the vector to
   /// NewSize.
   bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
     // Past the end.
-    if (LLVM_LIKELY(Elt < this->begin() || Elt >= this->end()))
+    if (LLVM_LIKELY(!isReferenceToStorage(Elt)))
       return true;
 
     // Return false if Elt will be destroyed by shrinking.
     if (NewSize <= this->size())
       return Elt < this->begin() + NewSize;
 
     // Return false if we need to grow.
     return NewSize <= this->capacity();
void assign(std::initializer_list<T> IL) {
     clear();
     append(IL);
   }
 
   iterator erase(const_iterator CI) {
     // Just cast away constness because this is a non-const member function.
     iterator I = const_cast<iterator>(CI);
 
-    assert(I >= this->begin() && "Iterator to erase is out of bounds.");
-    assert(I < this->end() && "Erasing at past-the-end iterator.");
+    assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.");
 
     iterator N = I;
     // Shift all elts down one.
     std::move(I+1, this->end(), I);
     // Drop the last elt.
     this->pop_back();
     return(N);
   }
 
   iterator erase(const_iterator CS, const_iterator CE) {
     // Just cast away constness because this is a non-const member function.
     iterator S = const_cast<iterator>(CS);
     iterator E = const_cast<iterator>(CE);
 
-    assert(S >= this->begin() && "Range to erase is out of bounds.");
-    assert(S <= E && "Trying to erase invalid range.");
-    assert(E <= this->end() && "Trying to erase past the end.");
+    assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.");
 
     iterator N = S;
     // Shift all elts down.
     iterator I = std::move(E, this->end(), S);
     // Drop the last elts.
     this->destroy_range(I, this->end());
     this->set_size(I - this->begin());
     return(N);
   }
 
 private:
   template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
     if (I == this->end()) {  // Important special case for empty vector.
       this->push_back(::std::forward<ArgType>(Elt));
       return this->end()-1;
     }
 
-    assert(I >= this->begin() && "Insertion iterator is out of bounds.");
-    assert(I <= this->end() && "Inserting past the end of the vector.");
+    assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
 
     // Check that adding an element won't invalidate Elt.
     this->assertSafeToAdd(&Elt);
 
     if (this->size() >= this->capacity()) {
       size_t EltNo = I-this->begin();
       this->grow();
       I = this->begin()+EltNo;
     }
 
     ::new ((void*) this->end()) T(::std::move(this->back()));
     // Push everything else over.
     std::move_backward(I, this->end()-1, this->end());
     this->set_size(this->size() + 1);
 
     // If we just moved the element we're inserting, be sure to update
     // the reference.
     std::remove_reference_t<ArgType> *EltPtr = &Elt;
-    if (I <= EltPtr && EltPtr < this->end())
+    if (this->isReferenceToRange(EltPtr, I, this->end()))
       ++EltPtr;
 
     *I = ::std::forward<ArgType>(*EltPtr);
     return I;
   }
 
 public:
   iterator insert(iterator I, T &&Elt) {
     return insert_one_impl(I, std::move(Elt));
   }
 
   iterator insert(iterator I, const T &Elt) { return insert_one_impl(I, Elt); }
 
   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
     // 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(NumToInsert, Elt);
       return this->begin()+InsertElt;
     }
 
-    assert(I >= this->begin() && "Insertion iterator is out of bounds.");
-    assert(I <= this->end() && "Inserting past the end of the vector.");
+    assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
 
     // Check that adding NumToInsert elements won't invalidate Elt.
     this->assertSafeToAdd(&Elt, NumToInsert);
 
     // Ensure there is enough space.
     reserve(this->size() + NumToInsert);
 
     // Uninvalidate the iterator.
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;
     }
 
-    assert(I >= this->begin() && "Insertion iterator is out of bounds.");
-    assert(I <= this->end() && "Inserting past the end of the vector.");
+    assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
 
     // Check that the reserve that follows doesn't invalidate the iterators.
     this->assertSafeToAddRange(From, To);
 
     size_t NumToInsert = std::distance(From, To);
 
     // Ensure there is enough space.
     reserve(this->size() + NumToInsert);