[libc++] Unwrap reverse_iterator<reverse_iterator<Iter>> in __unwrap_iter

[philnik]

Summary

Simplify the implementation of std::copy and std::move by using __unwrap_iter and __rewrap_iter to unwrap and rewrap reverse_iterator<reverse_iterator<Iter>> instead of specializing __copy_impl and __move_impl.

[Mordante]

I like this approach! I think the test coverage should be a bit higher.

libcxx/include/__algorithm/unwrap_iter.h

69

In general we avoid using auto as return type.

libcxx/test/libcxx/algorithms/unwrap_iter.compile.pass.cpp

9 ↗

(On Diff #434264)

The unwrap iterator is supported in C++11 and C++14.

14 ↗

(On Diff #434264)

I would like to see some additional tests using Standard containers that use wrapped iterator.

I also would like to see some runtime tests for these containers verifying the result has the expected value. The copy test above only test with an array.

[philnik]

• Address comments

libcxx/test/libcxx/algorithms/unwrap_iter.compile.pass.cpp

14 ↗

(On Diff #434264)

What is the difference between the first and the second request?

[ldionne]

libcxx/include/__algorithm/unwrap_iter.h

14–15

We should include __iterator/iterator_traits.h here instead, and then specialize __unwrap_iter_impl for reverse_iterator<reverse_iterator<T>> from reverse_iterator.h. That way, we don't need to pull the whole world into unwrap_iter.h, and we don't need to overload __unwrap_iter(...), which wasn't meant for that (we used to overload it but then we moved to specializing __unwrap_iter_impl as a customization point instead).

108–112

I think it would be cleaner not to reuse the same __rewrap_iter overload set for this. We could have one "top level" entry point for reverse_iterator<reverse_iterator<...>> and then use a helper function to do the actual rewrapping.

One motivation for this is that I'd like to move to a specialization based customization point for this as well in the future.

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp

171

Since we handle more than 2 layers of reverse_iterator, we should test it.

libcxx/test/libcxx/algorithms/unwrap_iter.pass.cpp

1 ↗

(On Diff #435320)

libcxx/test/libcxx/iterators/<something>.pass.cpp?

[philnik]

• Address comments

[philnik]

Fix patch

[philnik]

• Try to fix CI

[ldionne]

LGTM pending CI

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp

158

test_normal_reveRse

[philnik]

• Try to fix CI

[philnik]

• Try to fix CI

libcxx/include/__algorithm/copy.h

__copy_impl(reverse_iterator<_InIter> __first,
   auto __first_base = std::__unwrap_iter(__first.base());
   auto __last_base = std::__unwrap_iter(__last.base());
   auto __result_base = std::__unwrap_iter(__result.base());
   auto __result_first = __result_base - (__first_base - __last_base);
   std::__copy_impl(__last_base, __first_base, __result_first);
   return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first)));
 }
 
-template <class _InIter, class _Sent, class _OutIter>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-pair<reverse_iterator<reverse_iterator<_InIter> >, reverse_iterator<reverse_iterator<_OutIter> > >
-__copy_impl(reverse_iterator<reverse_iterator<_InIter> > __first,
-            reverse_iterator<reverse_iterator<_Sent> > __last,
-            reverse_iterator<reverse_iterator<_OutIter> > __result);
-
 template <class _InIter, class _Sent, class _OutIter,
           __enable_if_t<!(is_copy_constructible<_InIter>::value
                        && is_copy_constructible<_Sent>::value
                        && is_copy_constructible<_OutIter>::value), int> = 0 >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
   return std::__copy_impl(std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _InIter, class _Sent, class _OutIter,
           __enable_if_t<is_copy_constructible<_InIter>::value
                      && is_copy_constructible<_Sent>::value
                      && is_copy_constructible<_OutIter>::value, int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_InIter, _OutIter>
 __copy(_InIter __first, _Sent __last, _OutIter __result) {
   auto __ret = std::__copy_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result));
   return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
 }
 
-// __unwrap_iter can't unwrap random_access_iterators, so we need to unwrap two reverse_iterators manually
-template <class _InIter, class _Sent, class _OutIter>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-pair<reverse_iterator<reverse_iterator<_InIter> >, reverse_iterator<reverse_iterator<_OutIter> > >
-__copy_impl(reverse_iterator<reverse_iterator<_InIter> > __first,
-            reverse_iterator<reverse_iterator<_Sent> > __last,
-            reverse_iterator<reverse_iterator<_OutIter> > __result) {
-  auto __ret = std::__copy(__first.base().base(), __last.base().base(), __result.base().base());
-  return std::make_pair(reverse_iterator<reverse_iterator<_InIter> >(reverse_iterator<_InIter>(__ret.first)),
-                        reverse_iterator<reverse_iterator<_OutIter> >(reverse_iterator<_OutIter>(__ret.second)));
-}
-
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
   return std::__copy(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_H

libcxx/include/__algorithm/unwrap_iter.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_UNWRAP_ITER_H
 #define _LIBCPP___ALGORITHM_UNWRAP_ITER_H
 
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__memory/pointer_traits.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // The job of __unwrap_iter is to lower contiguous iterators (such as

 template<class _Iter, class _Impl = __unwrap_iter_impl<_Iter> >
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 decltype(_Impl::__apply(declval<_Iter>()))
 __unwrap_iter(_Iter __i) _NOEXCEPT
 {
     return _Impl::__apply(__i);
 }
 
+template <class _OrigIter, class _UnwrappedIter>
+struct __rewrap_iter_impl {
+  static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter __first, _UnwrappedIter __result) {
+    // Precondition: __result is reachable from __first
+    // Precondition: _OrigIter is a contiguous iterator
+    return __first + (__result - std::__unwrap_iter(__first));
+  }
+};
+
+template <class _OrigIter>
+struct __rewrap_iter_impl<_OrigIter, _OrigIter> {
+  static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter, _OrigIter __result) {
+    return __result;
+  }
+};
+
 template<class _OrigIter>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
 _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result)
 {
     return __result;
 }
 
-template<class _OrigIter, class _UnwrappedIter>
+template<class _OrigIter, class _UnwrappedIter, class _Impl = __rewrap_iter_impl<_OrigIter, _UnwrappedIter> >
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
 _OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result)
 {
-    // Precondition: __result is reachable from __first
-    // Precondition: _OrigIter is a contiguous iterator
-    return __first + (__result - _VSTD::__unwrap_iter(__first));
+  return _Impl::__apply(__first, __result);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_UNWRAP_ITER_H

libcxx/include/__iterator/reverse_iterator.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ITERATOR_REVERSE_ITERATOR_H
 #define _LIBCPP___ITERATOR_REVERSE_ITERATOR_H
 
+#include <__algorithm/unwrap_iter.h>
 #include <__compare/compare_three_way_result.h>
 #include <__compare/three_way_comparable.h>
 #include <__concepts/convertible_to.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>

 template <class _Iter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
 {
     return reverse_iterator<_Iter>(__i);
 }
 #endif
 
+template <class _Iter>
+using _ReverseWrapper = reverse_iterator<reverse_iterator<_Iter> >;
+
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<_ReverseWrapper<_Iter>, __b> {
+  static _LIBCPP_CONSTEXPR decltype(std::__unwrap_iter(std::declval<_Iter>()))
+  __apply(_ReverseWrapper<_Iter> __i) _NOEXCEPT {
+    return std::__unwrap_iter(__i.base().base());
+  }
+};
+
+template <class _OrigIter, class _UnwrappedIter>
+struct __rewrap_iter_impl<_ReverseWrapper<_OrigIter>, _UnwrappedIter> {
+  template <class _Iter>
+  struct _ReverseWrapperCount {
+    static _LIBCPP_CONSTEXPR const size_t value = 1;
+  };
+
+  template <class _Iter>
+  struct _ReverseWrapperCount<_ReverseWrapper<_Iter> > {
+    static _LIBCPP_CONSTEXPR const size_t value = 1 + _ReverseWrapperCount<_Iter>::value;
+  };
+
+  template <size_t _RewrapCount, class _OIter, class _UIter, __enable_if_t<_RewrapCount != 0, int> = 0>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR _ReverseWrapper<_OIter> __rewrap(_ReverseWrapper<_OIter> __iter1,
+                                                                                  _UIter __iter2) {
+    return _ReverseWrapper<_OIter>(
+        reverse_iterator<_OIter>(__rewrap<_RewrapCount - 1>(__iter1.base().base(), __iter2)));
+  }
+
+  template <size_t _RewrapCount, class _OIter, class _UIter, __enable_if_t<_RewrapCount == 0, int> = 0>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR decltype(std::__rewrap_iter(std::declval<_OIter>(),
+                                                                             std::declval<_UIter>()))
+  __rewrap(_OIter __iter1, _UIter __iter2) {
+    return std::__rewrap_iter(__iter1, __iter2);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR _ReverseWrapper<_OrigIter> __apply(_ReverseWrapper<_OrigIter> __iter1,
+                                                                                    _UnwrappedIter __iter2) {
+    return __rewrap<_ReverseWrapperCount<_OrigIter>::value>(__iter1, __iter2);
+  }
+};
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
 
 // When the debug mode is enabled, we don't unwrap iterators in std::copy
 // so we don't get this optimization.
 // UNSUPPORTED: libcpp-has-debug-mode
 
 // <algorithm>
 
 // This test checks that std::copy forwards to memmove when appropriate.
 
 #include <algorithm>
 #include <cassert>
 #include <iterator>
+#include <ranges>
 #include <type_traits>
 
 struct S {
   int i;
   constexpr S(int i_) : i(i_) {}
   S(const S&) = default;
   S(S&&) = delete;
   constexpr S& operator=(const S&) = default;
   S& operator=(S&&) = delete;
   constexpr bool operator==(const S&) const = default;
 };
 
 static_assert(std::is_trivially_copyable_v<S>);
 
 template <class T>
 struct NotIncrementableIt {
   T* i;
   using iterator_category = std::contiguous_iterator_tag;
   using iterator_concept = std::contiguous_iterator_tag;
   using value_type = T;
   using difference_type = ptrdiff_t;
   using pointer = T*;
   using reference = T&;
 
+  constexpr NotIncrementableIt() = default;
   constexpr NotIncrementableIt(T* i_) : i(i_) {}
 
   friend constexpr bool operator==(const NotIncrementableIt& lhs, const NotIncrementableIt& rhs) {
     return lhs.i == rhs.i;
   }
 
   constexpr T& operator*() { return *i; }
+  constexpr T& operator*() const { return *i; }
   constexpr T* operator->() { return i; }
   constexpr T* operator->() const { return i; }
 
   constexpr NotIncrementableIt& operator++() {
     assert(false);
     return *this;
   }
 
+  constexpr NotIncrementableIt& operator++(int) {
+    assert(false);
+    return *this;
+  }
+
   constexpr NotIncrementableIt& operator--() {
     assert(false);
     return *this;
   }
 
   friend constexpr NotIncrementableIt operator+(const NotIncrementableIt& it, difference_type size) { return it.i + size; }
   friend constexpr difference_type operator-(const NotIncrementableIt& x, const NotIncrementableIt& y) { return x.i - y.i; }
   friend constexpr NotIncrementableIt operator-(const NotIncrementableIt& x, difference_type size) { return NotIncrementableIt(x.i - size); }
 };
 
 static_assert(std::__is_cpp17_contiguous_iterator<NotIncrementableIt<S>>::value);
 
-template <class Iter>
+template <size_t N, class Iter, std::enable_if_t<N == 0>* = nullptr>
+constexpr auto wrap_n_times(Iter i) {
+  return i;
+}
+
+template <size_t N, class Iter, std::enable_if_t<N != 0>* = nullptr>
+constexpr auto wrap_n_times(Iter i) {
+  return std::make_reverse_iterator(wrap_n_times<N - 1>(i));
+}
+
+static_assert(std::is_same_v<decltype(wrap_n_times<2>(std::declval<int*>())),
+                             std::reverse_iterator<std::reverse_iterator<int*>>>);
+
+template <size_t InCount, size_t OutCount, class Iter>
 constexpr void test_normal() {
+  {
+    S a[] = {1, 2, 3, 4};
+    S b[] = {0, 0, 0, 0};
+    std::copy(wrap_n_times<InCount>(Iter(a)), wrap_n_times<InCount>(Iter(a + 4)), wrap_n_times<OutCount>(Iter(b)));
+    assert(std::equal(a, a + 4, b));
+  }
+  {
+    S a[] = {1, 2, 3, 4};
+    S b[] = {0, 0, 0, 0};
+    std::ranges::copy(wrap_n_times<InCount>(Iter(a)),
+                      wrap_n_times<InCount>(Iter(a + 4)),
+                      wrap_n_times<OutCount>(Iter(b)));
+    assert(std::equal(a, a + 4, b));
+  }
+  {
     S a[] = {1, 2, 3, 4};
     S b[] = {0, 0, 0, 0};
-  std::copy(Iter(a), Iter(a + 4), Iter(b));
+    auto range = std::ranges::subrange(wrap_n_times<InCount>(Iter(a)), wrap_n_times<InCount>(Iter(a + 4)));
+    std::ranges::copy(range, Iter(b));
     assert(std::equal(a, a + 4, b));
   }
+}
 
-template <class Iter>
+template <size_t InCount, size_t OutCount, class Iter>
 constexpr void test_reverse() {
+  {
     S a[] = {1, 2, 3, 4};
     S b[] = {0, 0, 0, 0};
-  std::copy(std::make_reverse_iterator(Iter(a + 4)),
-            std::make_reverse_iterator(Iter(a)),
-            std::make_reverse_iterator(Iter(b + 4)));
+    std::copy(std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a + 4))),
+              std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a))),
+              std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4))));
+    assert(std::equal(a, a + 4, b));
   }
-
-template <class Iter>
-constexpr void test_reverse_reverse() {
+  {
     S a[] = {1, 2, 3, 4};
     S b[] = {0, 0, 0, 0};
-  std::copy(std::make_reverse_iterator(std::make_reverse_iterator(Iter(a))),
-            std::make_reverse_iterator(std::make_reverse_iterator(Iter(a + 4))),
-            std::make_reverse_iterator(std::make_reverse_iterator(Iter(b))));
+    std::ranges::copy(std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a + 4))),
+                      std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a))),
+                      std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4))));
+    assert(std::equal(a, a + 4, b));
+  }
+  {
+    S a[] = {1, 2, 3, 4};
+    S b[] = {0, 0, 0, 0};
+    auto range = std::ranges::subrange(wrap_n_times<InCount>(std::make_reverse_iterator(Iter(a + 4))),
+                                       wrap_n_times<InCount>(std::make_reverse_iterator(Iter(a))));
+    std::ranges::copy(range, std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4))));
+    assert(std::equal(a, a + 4, b));
+  }
+}
+
+template <size_t InCount, size_t OutCount>
+constexpr void test_normal_reverse() {
+  test_normal<InCount, OutCount, S*>();
+  test_normal<InCount, OutCount, NotIncrementableIt<S>>();
+  test_reverse<InCount, OutCount, S*>();
+  test_reverse<InCount, OutCount, NotIncrementableIt<S>>();
+}
+
+template <size_t InCount>
+constexpr void test_out_count() {
+  test_normal_reverse<InCount, 0>();
+  test_normal_reverse<InCount, 2>();
+  test_normal_reverse<InCount, 4>();
+  test_normal_reverse<InCount, 6>();
+  test_normal_reverse<InCount, 8>();
 }
 
 constexpr bool test() {
-  test_normal<S*>();
-  test_normal<NotIncrementableIt<S>>();
-  test_reverse<S*>();
-  test_reverse<NotIncrementableIt<S>>();
-  test_reverse_reverse<S*>();
-  test_reverse_reverse<NotIncrementableIt<S>>();
+  test_out_count<0>();
+  test_out_count<2>();
+  test_out_count<4>();
+  test_out_count<6>();
+  test_out_count<8>();
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// When the debug mode is enabled, we don't unwrap iterators in std::copy
+// so we don't get this optimization.
+// UNSUPPORTED: libcpp-has-debug-mode
+
+// check that std::__unwrap_iter() returns the correct type
+
+#include <algorithm>
+#include <cassert>
+#include <string>
+#include <type_traits>
+
+#include "test_iterators.h"
+#include "test_macros.h"
+
+template <class Iter>
+using UnwrapT = decltype(std::__unwrap_iter(std::declval<Iter>()));
+
+template <class Iter>
+using rev_iter = std::reverse_iterator<Iter>;
+
+template <class Iter>
+using rev_rev_iter = rev_iter<rev_iter<Iter> >;
+
+static_assert(std::is_same<UnwrapT<int*>, int*>::value, "");
+static_assert(std::is_same<UnwrapT<std::__wrap_iter<int*> >, int*>::value, "");
+static_assert(std::is_same<UnwrapT<rev_iter<int*> >, std::reverse_iterator<int*> >::value, "");
+static_assert(std::is_same<UnwrapT<rev_rev_iter<int*> >, int*>::value, "");
+static_assert(std::is_same<UnwrapT<rev_rev_iter<std::__wrap_iter<int*> > >, int*>::value, "");
+static_assert(std::is_same<UnwrapT<rev_rev_iter<rev_iter<std::__wrap_iter<int*> > > >, rev_iter<std::__wrap_iter<int*> > >::value, "");
+
+static_assert(std::is_same<UnwrapT<random_access_iterator<int*> >, random_access_iterator<int*> >::value, "");
+static_assert(std::is_same<UnwrapT<rev_iter<random_access_iterator<int*> > >, rev_iter<random_access_iterator<int*> > >::value, "");
+static_assert(std::is_same<UnwrapT<rev_rev_iter<random_access_iterator<int*> > >, random_access_iterator<int*> >::value, "");
+static_assert(std::is_same<UnwrapT<rev_rev_iter<rev_iter<random_access_iterator<int*> > > >, rev_iter<random_access_iterator<int*> > >::value, "");
+
+TEST_CONSTEXPR_CXX20 bool test() {
+  std::string str = "Banane";
+  using Iter = std::string::iterator;
+
+  assert(std::__unwrap_iter(str.begin()) == str.data());
+  assert(std::__unwrap_iter(str.end()) == str.data() + str.size());
+  assert(std::__unwrap_iter(rev_rev_iter<Iter>(rev_iter<Iter>(str.begin()))) == str.data());
+  assert(std::__unwrap_iter(rev_rev_iter<Iter>(rev_iter<Iter>(str.end()))) == str.data() + str.size());
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+#if TEST_STD_VER > 17
+  static_assert(test());
+#endif
+
+  return 0;
+}