Add support for TinyPtrVector<PointerIntPair<...> >

[atrick]

Summary

PointerIntPair and PointerUnion already mostly support nesting pointer-like types, but support was incomplete. PointerUnion::isNull still assumed that a union member was a true C++ pointer type. The meaning of PointerUnion::isNull is that the nested pointer component is null regardless of any other spare bits recursively. To adhere to the original intention of this API and fully support nested pointer types, we PointerLikeTypesTraits needs a new isNull() static method.

Once we have PointerLikeTypesTraits::isNull(), it's easy to make TinyPtrVector generic over pointer-like values. We just call isNull instead of assuming that pointer-like things are convertible to bool

Note that we don't actually want all pointer-like things to be convertible to bool because that's ambiguous for PointerIntPair.

[atrick]

This breaks the clang build because there are a handful of PointerLikeTypeTraits specializations that specify higher alignment:

template<>
struct PointerLikeTypeTraits< ::clang::Type*> {
  static inline void *getAsVoidPointer(::clang::Type *P) { return P; }

  static inline ::clang::Type *getFromVoidPointer(void *P) {
    return static_cast< ::clang::Type*>(P);
  }

  enum { NumLowBitsAvailable = clang::TypeAlignmentInBits };
};

[atrick]

I'm abandoning this. Adding a member to PointerLikeTypeTraits is going to be a merge problem for some LLVM projects. I'm going back to the simpler way of converting to PtrToIntPair to an opaque pointers to check whether it can be an element in TinyPtrVector now that I've convinced myself that the simple way is still correct.

llvm/include/llvm/ADT/PointerIntPair.h

getFromVoidPointer(void *P) {
     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
   }
 
   static inline PointerIntPair<PointerTy, IntBits, IntType>
   getFromVoidPointer(const void *P) {
     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
   }
 
+  static inline bool
+  isNull(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
+    // Handles nested PointerIntPair or PointerUnion types.
+    return PtrTraits::isNull(P.getPointer());
+  }
+
   enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits };
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_POINTERINTPAIR_H

llvm/include/llvm/ADT/PointerUnion.h

public:
   PointerUnion(std::nullptr_t) : PointerUnion() {}
   using Base::Base;
 
   /// Test if the pointer held in the union is null, regardless of
   /// which type it is.
   bool isNull() const {
     // Convert from the void* to one of the pointer types, to make sure that
     // we recursively strip off low bits if we have a nested PointerUnion.
-    return !PointerLikeTypeTraits<First>::getFromVoidPointer(
-        this->Val.getPointer());
+    return PointerLikeTypeTraits<First>::isNull(
+        PointerLikeTypeTraits<First>::getFromVoidPointer(
+            this->Val.getPointer()));
   }
 
   explicit operator bool() const { return !isNull(); }
 
   /// Test if the Union currently holds the type matching T.
   template <typename T> int is() const {
     constexpr int Index = pointer_union_detail::TypeIndex<T, PTs...>::Index;
     static_assert(Index < sizeof...(PTs),
public:
   First const *getAddrOfPtr1() const {
     return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
   }
 
   /// If the union is set to the first pointer type get an address pointing to
   /// it.
   First *getAddrOfPtr1() {
     assert(is<First>() && "Val is not the first pointer");
-    assert(
-        get<First>() == this->Val.getPointer() &&
-        "Can't get the address because PointerLikeTypeTraits changes the ptr");
+    assert(PointerLikeTypeTraits<First>::getAsVoidPointer(get<First>())
+               == this->Val.getPointer()
+           && "Can't get the address because PointerLikeTypeTraits changes the "
+              "ptr");
     return const_cast<First *>(
         reinterpret_cast<const First *>(this->Val.getAddrOfPointer()));
   }
 
   /// Assignment from nullptr which just clears the union.
   const PointerUnion &operator=(std::nullptr_t) {
     this->Val.initWithPointer(nullptr);
     return *this;

llvm/include/llvm/ADT/TinyPtrVector.h

 /// NOTE: This container doesn't allow you to store a null pointer into it.
 ///
 template <typename EltTy>
 class TinyPtrVector {
 public:
   using VecTy = SmallVector<EltTy, 4>;
   using value_type = typename VecTy::value_type;
   using PtrUnion = PointerUnion<EltTy, VecTy *>;
+  using EltPtrTraits = PointerLikeTypeTraits<EltTy>;
 
 private:
   PtrUnion Val;
 
 public:
   TinyPtrVector() = default;
 
   ~TinyPtrVector() {
public:
   }
 
   const_reverse_iterator rend() const {
     return const_reverse_iterator(begin());
   }
 
   EltTy operator[](unsigned i) const {
     assert(!Val.isNull() && "can't index into an empty vector");
-    if (EltTy V = Val.template dyn_cast<EltTy>()) {
+    EltTy V = Val.template dyn_cast<EltTy>();
+    if (!EltPtrTraits::isNull(V)) {
       assert(i == 0 && "tinyvector index out of range");
       return V;
     }
 
     assert(i < Val.template get<VecTy*>()->size() &&
            "tinyvector index out of range");
     return (*Val.template get<VecTy*>())[i];
   }
 
   EltTy front() const {
     assert(!empty() && "vector empty");
-    if (EltTy V = Val.template dyn_cast<EltTy>())
+    EltTy V = Val.template dyn_cast<EltTy>();
+    if (!EltPtrTraits::isNull(V))
       return V;
     return Val.template get<VecTy*>()->front();
   }
 
   EltTy back() const {
     assert(!empty() && "vector empty");
     if (EltTy V = Val.template dyn_cast<EltTy>())
       return V;
     return Val.template get<VecTy*>()->back();
   }
 
   void push_back(EltTy NewVal) {
-    assert(NewVal && "Can't add a null value");
+    assert(!EltPtrTraits::isNull(NewVal) && "Can't add a null value");
 
     // If we have nothing, add something.
     if (Val.isNull()) {
       Val = NewVal;
       return;
     }
 
     // If we have a single value, convert to a vector.
-    if (EltTy V = Val.template dyn_cast<EltTy>()) {
+    EltTy V = Val.template dyn_cast<EltTy>();
+    if (!EltPtrTraits::isNull(V)) {
       Val = new VecTy();
       Val.template get<VecTy*>()->push_back(V);
     }
 
     // Add the new value, we know we have a vector.
     Val.template get<VecTy*>()->push_back(NewVal);
   }
 
public:
   iterator insert(iterator I, const EltTy &Elt) {
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
     if (I == end()) {
       push_back(Elt);
       return std::prev(end());
     }
     assert(!Val.isNull() && "Null value with non-end insert iterator.");
-    if (EltTy V = Val.template dyn_cast<EltTy>()) {
+    EltTy V = Val.template dyn_cast<EltTy>();
+    if (!EltPtrTraits::isNull(V)) {
       assert(I == begin());
       Val = Elt;
       push_back(V);
       return begin();
     }
 
     return Val.template get<VecTy*>()->insert(I, Elt);
   }
iterator insert(iterator I, ItTy From, ItTy To) {
     ptrdiff_t Offset = I - begin();
     if (Val.isNull()) {
       if (std::next(From) == To) {
         Val = *From;
         return begin();
       }
 
       Val = new VecTy();
-    } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
+    } else {
+      EltTy V = Val.template dyn_cast<EltTy>();
+      if (!EltPtrTraits::isNull(V)) {
         Val = new VecTy();
-      Val.template get<VecTy*>()->push_back(V);
+        Val.template get<VecTy *>()->push_back(V);
       }
+    }
     return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
   }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_TINYPTRVECTOR_H

llvm/include/llvm/Support/PointerLikeTypeTraits.h

template <typename T> struct IsPointerLike<T *> {
   static const bool value = true;
 };
 } // namespace detail
 
 // Provide PointerLikeTypeTraits for non-cvr pointers.
 template <typename T> struct PointerLikeTypeTraits<T *> {
   static inline void *getAsVoidPointer(T *P) { return P; }
   static inline T *getFromVoidPointer(void *P) { return static_cast<T *>(P); }
+  static inline bool isNull(T *P) { return !P; }
 
   enum { NumLowBitsAvailable = detail::ConstantLog2<alignof(T)>::value };
 };
 
 template <> struct PointerLikeTypeTraits<void *> {
   static inline void *getAsVoidPointer(void *P) { return P; }
   static inline void *getFromVoidPointer(void *P) { return P; }
+  static inline bool isNull(void *P) { return !P; }
 
   /// Note, we assume here that void* is related to raw malloc'ed memory and
   /// that malloc returns objects at least 4-byte aligned. However, this may be
   /// wrong, or pointers may be from something other than malloc. In this case,
   /// you should specify a real typed pointer or avoid this template.
   ///
   /// All clients should use assertions to do a run-time check to ensure that
   /// this is actually true.
   enum { NumLowBitsAvailable = 2 };
 };
 
 // Provide PointerLikeTypeTraits for const things.
 template <typename T> struct PointerLikeTypeTraits<const T> {
   typedef PointerLikeTypeTraits<T> NonConst;
 
   static inline const void *getAsVoidPointer(const T P) {
     return NonConst::getAsVoidPointer(P);
   }
   static inline const T getFromVoidPointer(const void *P) {
     return NonConst::getFromVoidPointer(const_cast<void *>(P));
   }
+  static inline bool isNull(const T P) { return NonConst::isNull(P); }
   enum { NumLowBitsAvailable = NonConst::NumLowBitsAvailable };
 };
 
 // Provide PointerLikeTypeTraits for const pointers.
 template <typename T> struct PointerLikeTypeTraits<const T *> {
   typedef PointerLikeTypeTraits<T *> NonConst;
 
   static inline const void *getAsVoidPointer(const T *P) {
     return NonConst::getAsVoidPointer(const_cast<T *>(P));
   }
   static inline const T *getFromVoidPointer(const void *P) {
     return NonConst::getFromVoidPointer(const_cast<void *>(P));
   }
+  static inline bool isNull(const T *P) {
+    return NonConst::isNull(const_cast<T *>(P));
+  }
   enum { NumLowBitsAvailable = NonConst::NumLowBitsAvailable };
 };
 
 // Provide PointerLikeTypeTraits for uintptr_t.
 template <> struct PointerLikeTypeTraits<uintptr_t> {
   static inline void *getAsVoidPointer(uintptr_t P) {
     return reinterpret_cast<void *>(P);
   }
   static inline uintptr_t getFromVoidPointer(void *P) {
     return reinterpret_cast<uintptr_t>(P);
   }
+  static inline bool isNull(const uintptr_t P) { return !P; }
   // No bits are available!
   enum { NumLowBitsAvailable = 0 };
 };
 
 /// Provide suitable custom traits struct for function pointers.
 ///
 /// Function pointers can't be directly given these traits as functions can't
 /// have their alignment computed with `alignof` and we need different casting.
 ///
 /// To rely on higher alignment for a specialized use, you can provide a
 /// customized form of this template explicitly with higher alignment, and
 /// potentially use alignment attributes on functions to satisfy that.
 template <int Alignment, typename FunctionPointerT>
 struct FunctionPointerLikeTypeTraits {
   enum { NumLowBitsAvailable = detail::ConstantLog2<Alignment>::value };
   static inline void *getAsVoidPointer(FunctionPointerT P) {
     assert((reinterpret_cast<uintptr_t>(P) &
             ~((uintptr_t)-1 << NumLowBitsAvailable)) == 0 &&
            "Alignment not satisfied for an actual function pointer!");
     return reinterpret_cast<void *>(P);
   }
   static inline FunctionPointerT getFromVoidPointer(void *P) {
     return reinterpret_cast<FunctionPointerT>(P);
   }
+  static inline bool isNull(FunctionPointerT P) { return !P; }
 };
 
 /// Provide a default specialization for function pointers that assumes 4-byte
 /// alignment.
 ///
 /// We assume here that functions used with this are always at least 4-byte
 /// aligned. This means that, for example, thumb functions won't work or systems
 /// with weird unaligned function pointers won't work. But all practical systems
 /// we support satisfy this requirement.
 template <typename ReturnT, typename... ParamTs>
 struct PointerLikeTypeTraits<ReturnT (*)(ParamTs...)>
     : FunctionPointerLikeTypeTraits<4, ReturnT (*)(ParamTs...)> {};
 
 } // end namespace llvm
 
 #endif

llvm/unittests/ADT/TinyPtrVectorTest.cpp

 #include "gtest/gtest.h"
 #include <algorithm>
 #include <random>
 #include <vector>
 
 using namespace llvm;
 
 namespace {
+template <typename T> struct RemovePointer : std::remove_pointer<T> {};
+
+template <typename PointerTy, unsigned IntBits, typename IntType,
+          typename PtrTraits, typename Info>
+struct RemovePointer<
+    PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>> {
+  typedef typename RemovePointer<PointerTy>::type type;
+};
 
 template <typename VectorT>
 class TinyPtrVectorTest : public testing::Test {
 protected:
   typedef typename VectorT::value_type PtrT;
-  typedef typename std::remove_pointer<PtrT>::type ValueT;
+  typedef typename RemovePointer<PtrT>::type ValueT;
+  using PtrTraits = PointerLikeTypeTraits<PtrT>;
 
   VectorT V;
   VectorT V2;
 
   ValueT TestValues[1024];
   std::vector<PtrT> TestPtrs;
 
   TinyPtrVectorTest() {
     for (size_t i = 0, e = array_lengthof(TestValues); i != e; ++i)
-      TestPtrs.push_back(&TestValues[i]);
+      TestPtrs.push_back(PtrT(&TestValues[i]));
 
     std::shuffle(TestPtrs.begin(), TestPtrs.end(), std::mt19937{});
   }
 
+  PtrT makePtr(ValueT *V) { return PtrT(V); }
+
   ArrayRef<PtrT> testArray(size_t N) {
     return makeArrayRef(&TestPtrs[0], N);
   }
 
   void appendValues(VectorT &V, ArrayRef<PtrT> Values) {
     for (size_t i = 0, e = Values.size(); i != e; ++i)
       V.push_back(Values[i]);
   }
void expectValues(const VectorT &V, ArrayRef<PtrT> Values) {
     for (size_t i = 0, e = Values.size(); i != e; ++i) {
       EXPECT_EQ(Values[i], V[i]);
       EXPECT_EQ(Values[i], *std::next(V.begin(), i));
     }
     EXPECT_EQ(V.end(), std::next(V.begin(), Values.size()));
   }
 };
 
-typedef ::testing::Types<TinyPtrVector<int*>,
-                         TinyPtrVector<double*>
-                         > TinyPtrVectorTestTypes;
+typedef ::testing::Types<TinyPtrVector<int *>, TinyPtrVector<double *>,
+                         TinyPtrVector<PointerIntPair<int *, 1>>>
+    TinyPtrVectorTestTypes;
 TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes);
 
 TYPED_TEST(TinyPtrVectorTest, EmptyTest) {
   this->expectValues(this->V, this->testArray(0));
 }
 
 TYPED_TEST(TinyPtrVectorTest, PushPopBack) {
   this->V.push_back(this->TestPtrs[0]);
   this->expectValues(this->V, this->testArray(1));
   this->V.push_back(this->TestPtrs[1]);
   this->expectValues(this->V, this->testArray(2));
   this->V.push_back(this->TestPtrs[2]);
   this->expectValues(this->V, this->testArray(3));
   this->V.push_back(this->TestPtrs[3]);
   this->expectValues(this->V, this->testArray(4));
   this->V.push_back(this->TestPtrs[4]);
   this->expectValues(this->V, this->testArray(5));
 
   // Pop and clobber a few values to keep things interesting.
   this->V.pop_back();
   this->expectValues(this->V, this->testArray(4));
   this->V.pop_back();
   this->expectValues(this->V, this->testArray(3));
-  this->TestPtrs[3] = &this->TestValues[42];
-  this->TestPtrs[4] = &this->TestValues[43];
+  this->TestPtrs[3] = this->makePtr(&this->TestValues[42]);
+  this->TestPtrs[4] = this->makePtr(&this->TestValues[43]);
   this->V.push_back(this->TestPtrs[3]);
   this->expectValues(this->V, this->testArray(4));
   this->V.push_back(this->TestPtrs[4]);
   this->expectValues(this->V, this->testArray(5));
 
   this->V.pop_back();
   this->expectValues(this->V, this->testArray(4));
   this->V.pop_back();