[adt] Add raw_pointer_iterator to iterate over std::unique_ptr<> collections

[dsanders]

Summary

raw_pointer_iterator adapts the usual iterator by calling get() on the
value when being dereferenced. This allows users to iterate over things
like std::vector<std::unique_ptr<foo>> while preserving ownership and not
calling the deleted copy constructor.

This is similar to pointer_iterator except that pointer_iterator will attempt
to copy the pointer which is not possible for unique_ptr.

[paquette]

Hmm, It might be nice to have this as a specialization of pointer_iterator if possible.

I think it might be a source of confusion/frustration to have both a raw_pointer_iterator and a pointer_iterator, where raw_pointer_iterator is specifically used for only unique_ptr.

[dsanders]

In D58088#1395226, @paquette wrote:

Hmm, It might be nice to have this as a specialization of pointer_iterator if possible.

I think it might be a source of confusion/frustration to have both a raw_pointer_iterator and a pointer_iterator, where raw_pointer_iterator is specifically used for only unique_ptr.

I can see a way to achieve that (std::to_address()) but it requires C++20. Without that, the closest I've been able to get is a raw_pointer_iterator alias to pointer_iterator that has specializations based on whether a third optional argument is true_type or false_type. The main thing I'm missing to fold the alias in is a way to specify the default value of T in a way that resolves to either pointer_iterator's default type T or raw_pointer_iterators default type T depending on whether *Iter is a std::unique_ptr<X>& or not. I can detect the type easily enough but selecting between the two defaults is proving troublesome as it resolves the true and false cases too early and ends up trying to do int::pointer and failing because int isn't a class type.

[paquette]

Since it doesn't look like there's really any way to unify these right now, I think this LGTM.

[dblaikie]

In D58088#1396951, @dsanders wrote:

In D58088#1395226, @paquette wrote:

Hmm, It might be nice to have this as a specialization of pointer_iterator if possible.

I think it might be a source of confusion/frustration to have both a raw_pointer_iterator and a pointer_iterator, where raw_pointer_iterator is specifically used for only unique_ptr.

I can see a way to achieve that (std::to_address()) but it requires C++20. Without that, the closest I've been able to get is a raw_pointer_iterator alias to pointer_iterator that has specializations based on whether a third optional argument is true_type or false_type. The main thing I'm missing to fold the alias in is a way to specify the default value of T in a way that resolves to either pointer_iterator's default type T or raw_pointer_iterators default type T depending on whether *Iter is a std::unique_ptr<X>& or not. I can detect the type easily enough but selecting between the two defaults is proving troublesome as it resolves the true and false cases too early and ends up trying to do int::pointer and failing because int isn't a class type.

Would it be difficult to have LLVM's own version of std::to_address (LLVM has had/does have various type traits implmented in-tree when they aren't available in the standard LLVM's using at the moment) or similar to use here?

[dsanders]

In D58088#1401583, @dblaikie wrote:

In D58088#1396951, @dsanders wrote:

In D58088#1395226, @paquette wrote:

Hmm, It might be nice to have this as a specialization of pointer_iterator if possible.

I think it might be a source of confusion/frustration to have both a raw_pointer_iterator and a pointer_iterator, where raw_pointer_iterator is specifically used for only unique_ptr.

I can see a way to achieve that (std::to_address()) but it requires C++20. Without that, the closest I've been able to get is a raw_pointer_iterator alias to pointer_iterator that has specializations based on whether a third optional argument is true_type or false_type. The main thing I'm missing to fold the alias in is a way to specify the default value of T in a way that resolves to either pointer_iterator's default type T or raw_pointer_iterators default type T depending on whether *Iter is a std::unique_ptr<X>& or not. I can detect the type easily enough but selecting between the two defaults is proving troublesome as it resolves the true and false cases too early and ends up trying to do int::pointer and failing because int isn't a class type.

Would it be difficult to have LLVM's own version of std::to_address (LLVM has had/does have various type traits implmented in-tree when they aren't available in the standard LLVM's using at the moment) or similar to use here?

That looks simple enough. I haven't gone through the spec but something as simple as:

namespace llvm {
template<class Ptr>
auto to_address(const Ptr &P) noexcept { return P.operator->(); }
template<class T>
constexpr T* to_address(T* P) noexcept { return P; }
}

seems to cover the majority of it (and definitely the bits I need). It's just the std::pointer_traits<Ptr>::to_address(p) based implementation of the fancy pointer overload that's missing.

[dblaikie]

In D58088#1401651, @dsanders wrote:

In D58088#1401583, @dblaikie wrote:

In D58088#1396951, @dsanders wrote:

In D58088#1395226, @paquette wrote:

Hmm, It might be nice to have this as a specialization of pointer_iterator if possible.

I think it might be a source of confusion/frustration to have both a raw_pointer_iterator and a pointer_iterator, where raw_pointer_iterator is specifically used for only unique_ptr.

I can see a way to achieve that (std::to_address()) but it requires C++20. Without that, the closest I've been able to get is a raw_pointer_iterator alias to pointer_iterator that has specializations based on whether a third optional argument is true_type or false_type. The main thing I'm missing to fold the alias in is a way to specify the default value of T in a way that resolves to either pointer_iterator's default type T or raw_pointer_iterators default type T depending on whether *Iter is a std::unique_ptr<X>& or not. I can detect the type easily enough but selecting between the two defaults is proving troublesome as it resolves the true and false cases too early and ends up trying to do int::pointer and failing because int isn't a class type.

Would it be difficult to have LLVM's own version of std::to_address (LLVM has had/does have various type traits implmented in-tree when they aren't available in the standard LLVM's using at the moment) or similar to use here?

That looks simple enough. I haven't gone through the spec but something as simple as:

namespace llvm {
template<class Ptr>
auto to_address(const Ptr &P) noexcept { return P.operator->(); }
template<class T>
constexpr T* to_address(T* P) noexcept { return P; }
}

seems to cover the majority of it (and definitely the bits I need). It's just the std::pointer_traits<Ptr>::to_address(p) based implementation of the fancy pointer overload that's missing.

Probably OK to skip that for now & we can add our own LLVM name for that if we need it one day/before we get the standardized version.

Probably easy enough/worth adding to_address as a separate patch before this one, with some unit testing.

[dsanders]

The std::to_address implementation is in https://reviews.llvm.org/D58421. I had to add another limitation to it as it accidentally used C++14 which prevents the deduction of the return type.

[dsanders]

I just noticed a big simplification that doesn't need C++20 features or new classes. This:

template <typename WrappedIteratorT,
          typename T1 = typename std::remove_reference<decltype(**std::declval<WrappedIteratorT>())>::type,
          typename T2 = typename std::add_pointer<T1>::type>
using raw_pointer_iterator = pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;

is functionally equivalent to the raw_pointer_iterator in this patch. pointee_iterator derefs the unique_ptr, while pointer_iterator produces the raw_pointer. If that version sounds good to you then I think it makes sense to revert the llvm::to_address() patch, switch to this implementation and fold this into the GISel Combiner patch as at that point it's too trivial to warrant a dedicated patch. Does that sound good?

[dblaikie]

In D58088#1404769, @dsanders wrote:

I just noticed a big simplification that doesn't need C++20 features or new classes. This:

template <typename WrappedIteratorT,
          typename T1 = typename std::remove_reference<decltype(**std::declval<WrappedIteratorT>())>::type,
          typename T2 = typename std::add_pointer<T1>::type>
using raw_pointer_iterator = pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;

is functionally equivalent to the raw_pointer_iterator in this patch. pointee_iterator derefs the unique_ptr, while pointer_iterator produces the raw_pointer. If that version sounds good to you then I think it makes sense to revert the llvm::to_address() patch, switch to this implementation and fold this into the GISel Combiner patch as at that point it's too trivial to warrant a dedicated patch. Does that sound good?

Beyond probably some annoying compile-time complexity/overhead (& maybe similar debugging confusion with the extra layers of abstraction) - I'm guessing this wouldn't support null pointers (because pointee_iterator probably dereferences unconditionally?) which would be a bit problematic, I'd reckon?

[glenjofe]

That looks simple enough. I haven't gone through the spec but something as simple as:

namespace llvm {
template<class Ptr>
auto to_address(const Ptr &P) noexcept { return P.operator->(); }
template<class T>
constexpr T* to_address(T* P) noexcept { return P; }
}

seems to cover the majority of it (and definitely the bits I need). It's just the std::pointer_traits<Ptr>::to_address(p) based implementation of the fancy pointer overload that's missing.

If it is named to_address and intended to convert any pointer to a raw pointer then it should be:

namespace llvm {
template<class T>
constexpr T* to_address(T* p) noexcept { return p; }
template<class Ptr>
typename std::pointer_traits<Ptr>::element_type* to_address(const Ptr &p) noexcept { return llvm::to_address(p.operator->()); }
}

[dsanders]

In D58088#1404872, @dblaikie wrote:

In D58088#1404769, @dsanders wrote:

I just noticed a big simplification that doesn't need C++20 features or new classes. This:

template <typename WrappedIteratorT,
          typename T1 = typename std::remove_reference<decltype(**std::declval<WrappedIteratorT>())>::type,
          typename T2 = typename std::add_pointer<T1>::type>
using raw_pointer_iterator = pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;

is functionally equivalent to the raw_pointer_iterator in this patch. pointee_iterator derefs the unique_ptr, while pointer_iterator produces the raw_pointer. If that version sounds good to you then I think it makes sense to revert the llvm::to_address() patch, switch to this implementation and fold this into the GISel Combiner patch as at that point it's too trivial to warrant a dedicated patch. Does that sound good?

Beyond probably some annoying compile-time complexity/overhead (& maybe similar debugging confusion with the extra layers of abstraction) - I'm guessing this wouldn't support null pointers (because pointee_iterator probably dereferences unconditionally?) which would be a bit problematic, I'd reckon?

It's not a problem for my intended uses at least. I can just make it specific to the GISel Combiner rather than put it in a common header.

[dsanders]

In D58088#1405089, @glenjofe wrote:

That looks simple enough. I haven't gone through the spec but something as simple as:

namespace llvm {
template<class Ptr>
auto to_address(const Ptr &P) noexcept { return P.operator->(); }
template<class T>
constexpr T* to_address(T* P) noexcept { return P; }
}

seems to cover the majority of it (and definitely the bits I need). It's just the std::pointer_traits<Ptr>::to_address(p) based implementation of the fancy pointer overload that's missing.

If it is named to_address and intended to convert any pointer to a raw pointer then it should be:

namespace llvm {
template<class T>
constexpr T* to_address(T* p) noexcept { return p; }
template<class Ptr>
typename std::pointer_traits<Ptr>::element_type* to_address(const Ptr &p) noexcept { return llvm::to_address(p.operator->()); }
}

Well spotted. I'm about to revert the patch though as I've found a way of doing this without using C++20 or defining any new classes that's good enough (because there's no nullptrs) for the GISel Combiner code that wants to use this

[dblaikie]

In D58088#1406356, @dsanders wrote:

In D58088#1405089, @glenjofe wrote:

That looks simple enough. I haven't gone through the spec but something as simple as:

namespace llvm {
template<class Ptr>
auto to_address(const Ptr &P) noexcept { return P.operator->(); }
template<class T>
constexpr T* to_address(T* P) noexcept { return P; }
}

seems to cover the majority of it (and definitely the bits I need). It's just the std::pointer_traits<Ptr>::to_address(p) based implementation of the fancy pointer overload that's missing.

If it is named to_address and intended to convert any pointer to a raw pointer then it should be:

namespace llvm {
template<class T>
constexpr T* to_address(T* p) noexcept { return p; }
template<class Ptr>
typename std::pointer_traits<Ptr>::element_type* to_address(const Ptr &p) noexcept { return llvm::to_address(p.operator->()); }
}

Well spotted. I'm about to revert the patch though as I've found a way of doing this without using C++20 or defining any new classes that's good enough (because there's no nullptrs) for the GISel Combiner code that wants to use this

I'd probably still go with this - seems like a nice general utility to have. (& I replied on the to_address review that I'm not sure the extra generality suggested is super important for LLVM so I'd be just as fine leaving it as-is for now) But up to you, for sure.

include/llvm/ADT/iterator.h

public:
   }
 
   NodeRef &operator*() const {
     NR.second = *this->I;
     return NR;
   }
 };
 
+// Iterator to convert std::unique_ptr to raw pointers.
+template <typename WrappedIteratorT,
+          typename T = typename std::remove_reference<decltype(*std::declval<WrappedIteratorT>())>::type::pointer>
+class raw_pointer_iterator
+    : public iterator_adaptor_base<
+          raw_pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
+          typename std::iterator_traits<WrappedIteratorT>::iterator_category,
+          T> {
+  mutable T Ptr;
+
+public:
+  raw_pointer_iterator() = default;
+
+  explicit raw_pointer_iterator(WrappedIteratorT u)
+      : raw_pointer_iterator::iterator_adaptor_base(std::move(u)) {}
+
+  T &operator*() { return Ptr = this->I->get(); }
+  const T &operator*() const { return Ptr = this->I->get(); }
+};
+
+template <typename RangeT, typename WrappedIteratorT =
+                               decltype(std::begin(std::declval<RangeT>()))>
+iterator_range<raw_pointer_iterator<WrappedIteratorT>>
+make_raw_pointer_range(RangeT &&Range) {
+  using RawPointerIteratorT = raw_pointer_iterator<WrappedIteratorT>;
+  return make_range(RawPointerIteratorT(std::begin(std::forward<RangeT>(Range))),
+                    RawPointerIteratorT(std::end(std::forward<RangeT>(Range))));
+}
 } // end namespace llvm
 
 #endif // LLVM_ADT_ITERATOR_H

unittests/ADT/IteratorTest.cpp

 
 TEST(PointerIterator, Range) {
   int A[] = {1, 2, 3, 4};
   int I = 0;
   for (int *P : make_pointer_range(A))
     EXPECT_EQ(A + I++, P);
 }
 
+TEST(RawPointerIterator, Basic) {
+  std::unique_ptr<int> A[] = {
+      make_unique<int>(1),
+      make_unique<int>(2),
+      make_unique<int>(3),
+      make_unique<int>(4),
+  };
+  raw_pointer_iterator<std::unique_ptr<int> *> Begin(std::begin(A)),
+      End(std::end(A));
+  EXPECT_EQ(A->get(), *Begin);
+  ++Begin;
+  EXPECT_EQ((A + 1)->get(), *Begin);
+  ++Begin;
+  EXPECT_EQ((A + 2)->get(), *Begin);
+  ++Begin;
+  EXPECT_EQ((A + 3)->get(), *Begin);
+  ++Begin;
+  EXPECT_EQ(Begin, End);
+}
+
+TEST(RawPointerIterator, Range) {
+  std::unique_ptr<int> A[] = {
+      make_unique<int>(1),
+      make_unique<int>(2),
+      make_unique<int>(3),
+      make_unique<int>(4),
+  };
+  int I = 0;
+  for (int *P : make_raw_pointer_range(A))
+    EXPECT_EQ((A + I++)->get(), P);
+}
+
 TEST(ZipIteratorTest, Basic) {
   using namespace std;
   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
   SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1};
   const char message[] = "yynyyy\0";
 
   for (auto tup : zip(pi, odd, message)) {
     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));