[libc++] Fix unwrapping ranges with different iterators and sentinels

[huixie90]

libcxx/include/__algorithm/copy.h

91–96

is it ok pass nullptr to __rewrap_iter. The implementation below seems that __first_un.second can be nullptr

libcxx/include/__algorithm/unwrap_range.h

15

unused?

33

random_access_iterator implies copy_constructible
(forward + are copyable)

35

not sure about the variable name __sent. because there is a template parameter called _Sent, at the first glance, I thought __sent is of type _Sent because of the name. but actually, it is of type _Iter

40

I'd be really cautious about nullptr, which is comparable with pointers. if any of the logic goes wrong, it could result in a runtime UB. Is it possible to avoid nullptr?

[philnik]

• Address comments

[philnik]

libcxx/include/__algorithm/unwrap_range.h

40

How exactly would anything go wrong at runtime? This results in pair<pair<_Iter, nullptr_t>, _Sent>. The nullptr_t should only ever be passed back to __rewrap_iter. If that weren't the case there would be type mismatches all over the place. (i.e. __rewrap_iter would just return the unwrapped pointer) But anyways, just to make it really hard to break I'll change it to a tag type, since there isn't any downside to do so.

[philnik]

Upload correct diff

[Mordante]

I really would like to encourage you to add a bit more comments to new code. Historically we haven't done that a lot, but IMO that makes some older parts of the code harder to understand.

libcxx/include/__algorithm/copy.h

13

Please also add this to the top level algorithm header.

70

Can we use fewer autos here. It's quite hard to understand the types without looking at other places.

74

__last has been moved from at line 70. It there a test that fails, if not please add a test.

libcxx/include/__algorithm/unwrap_range.h

31

Please don't use the automatically deduced auto.

35

Based on the code in __algorithm/copy.h with all .first.first and the like. I would prefer to use a small struct with good names for the types instead of a pair. I think that will aid the readability of the code in __algorithm/copy.h.

[huixie90]

LGTM.

Regarding testing, I am wondering if the tests cover those cases:
iterators that model c++20's random_access_range but only model c++17's InputIterator (this is very common though)
iterators that model c++17's RandomAccessIterator but only model C++20's input_or_output_iterator (or input_iterator) (this is not very common and I guess we need to define member typedef iterator_category and iterator_concept to make one)

Since the tests in D128611 and D128983 depend on this fix and currently commented with TODO. Depending the order of which patch land first, we need to update those tests

libcxx/include/__algorithm/unwrap_range.h

40

yeah I agree changing it to a tag type is better, at least more obvious to the readers. It is unclear to me what __rewrap_iter would do for nullptr. Since it is a pair, I would guess it might compare the first with second (since pointers are comparable with nullptr_t). With the tag type it is obvious that it is not going to be compared with first

[philnik]

libcxx/include/__algorithm/copy.h

13

Why should we do that? It's an implementation detail, and adding the include to the top level header just exposes that implementation detail (even for modules users).

74

See D129044.

libcxx/include/__algorithm/unwrap_range.h

31

I can see you point about readability in general, but in this case I don't think it helps in any way. It would essentially be pair<decltype(std::__unwrap_iter(std::move(std::declval<_Iter>()))), decltype(std::__unwrap_iter(std::move(std::declval<_Iter>())).first)> which is just a really long way to write "Find it out yourself". (The std::moves might be unnecessary, but removing them wouldn't make it any better)

35

I've got

template <class _OrigIter, class _Iter>
struct _UnwrappedRange {
  _OrigIter __rewrap;
  _Iter __first;
  _Iter __last;
};

right now, but that loses the information that you can only rewrap __first. That might be acceptable, Idk. I also really dislike __rewrap. WDYT?

[Mordante]

libcxx/include/__algorithm/copy.h

13

Are other header not allowed to use this? unwrap_iter is also in <algorithm> so IMO this should be there too.

libcxx/include/__algorithm/unwrap_range.h

31

I agree that's also not nice to read. But I think we should give some thought about whether we can do better. I feel this entire unwrapping looks quite hard to understand. The original unwrap code already took some effort to understand, but I feel it gets worse with ranges.

I will give it some more thought.

35

Maybe rename __rewrap to __base?
When it's not possible to rewrap __last we can add some comment why it's not possible.

[philnik]

Rebased and updated to new style

[ldionne]

Please ping me on Discord once you have implemented all comments just so I can do another quick pass, and we can ship this in time for LLVM 15.

libcxx/.clang-format

71 ↗

(On Diff #444034)

Shouldn't be here.

libcxx/include/__algorithm/unwrap_range.h

46

std::move?

49

This would avoid a copy?

54

Please leave at least some sort of documentation explaining what this file and group of functions do. And in particular, it would be useful to explain why they are useful/needed.

60

Would it make sense to std::move here?

75

I had completely missed this because it's a large-ish block.

78

std::move

83

std::move

libcxx/include/__iterator/reverse_iterator.h

335–339 ↗

(On Diff #444034)

I think this diff doesn't belong here.

[philnik]

• Address comments

[ldionne]

libcxx/include/__algorithm/unwrap_range.h

28

[philnik]

• Address comments

libcxx/include/__algorithm/copy.h

13

Other headers are allowed to use this, but they should include __algorithm/unwrap_range.h and not algorithm.

libcxx/include/__algorithm/unwrap_range.h

49

It turns out that this causes the overloads to be ambiguous. I'll try to improve it later, since this code probably still needs sum debugging.

[philnik]

• Try to fix CI

[philnik]

• Try to fix CI

[philnik]

• Next try

libcxx/include/CMakeLists.txt

set(files
   __algorithm/sort_heap.h
   __algorithm/stable_partition.h
   __algorithm/stable_sort.h
   __algorithm/swap_ranges.h
   __algorithm/transform.h
   __algorithm/unique.h
   __algorithm/unique_copy.h
   __algorithm/unwrap_iter.h
+  __algorithm/unwrap_range.h
   __algorithm/upper_bound.h
   __assert
   __availability
   __bit/bit_cast.h
   __bit/byteswap.h
   __bit_reference
   __bits
   __bsd_locale_defaults.h

libcxx/include/__algorithm/copy.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_COPY_H
 #define _LIBCPP___ALGORITHM_COPY_H
 
 #include <__algorithm/unwrap_iter.h>
+#include <__algorithm/unwrap_range.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <cstring>
 #include <type_traits>
 
template <class _InIter, class _OutIter,
                       && __is_cpp17_contiguous_iterator<typename _InIter::iterator_type>::value
                       && __is_cpp17_contiguous_iterator<typename _OutIter::iterator_type>::value
                       && is_trivially_copy_assignable<__iter_value_type<_OutIter> >::value
                       && __is_reverse_iterator<_InIter>::value
                       && __is_reverse_iterator<_OutIter>::value, int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_InIter, _OutIter>
 __copy_impl(_InIter __first, _InIter __last, _OutIter __result) {
   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, _OutIter(std::__rewrap_iter(__result.base(), __result_first)));
 }
 
 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));
+pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
+  auto __range = std::__unwrap_range(__first, __last);
+  auto __ret   = std::__copy_impl(std::move(__range.first), std::move(__range.second), std::__unwrap_iter(__result));
+  return std::make_pair(
+      std::__rewrap_range<_Sent>(__first, __ret.first), std::__rewrap_iter(__result, __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_range.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_RANGE_H
+#define _LIBCPP___ALGORITHM_UNWRAP_RANGE_H
+
+#include <__algorithm/unwrap_iter.h>
+#include <__concepts/constructible.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/next.h>
+#include <__utility/declval.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// __unwrap_range and __rewrap_range are used to unwrap ranges which may have different iterator and sentinel types.
+// __unwrap_iter and __rewrap_iter don't working for this, because they assume that the iterator and sentinel have
+// the same type. __unwrap_range tries to get two iterators and then forward to __unwrap_iter.
+
+#if _LIBCPP_STD_VER > 17
+template <class _Iter, class _Sent>
+struct __unwrap_range_impl {
+  _LIBCPP_HIDE_FROM_ABI static constexpr auto __unwrap(_Iter __first, _Sent __sent)
+    requires random_access_iterator<_Iter> && sized_sentinel_for<_Sent, _Iter>
+  {
+    auto __last = ranges::next(__first, __sent);
+    return pair{std::__unwrap_iter(std::move(__first)), std::__unwrap_iter(std::move(__last))};
+  }
+
+  _LIBCPP_HIDE_FROM_ABI static constexpr auto __unwrap(_Iter __first, _Sent __last) {
+    return pair{std::move(__first), std::move(__last)};
+  }
+
+  _LIBCPP_HIDE_FROM_ABI static constexpr auto
+  __rewrap(_Iter __orig_iter, decltype(std::__unwrap_iter(__orig_iter)) __iter)
+    requires random_access_iterator<_Iter> && sized_sentinel_for<_Sent, _Iter>
+  {
+    return std::__rewrap_iter(std::move(__orig_iter), std::move(__iter));
+  }
+
+  _LIBCPP_HIDE_FROM_ABI static constexpr auto __rewrap(const _Iter&, _Iter __iter) { return __iter; }
+};
+
+template <class _Iter>
+struct __unwrap_range_impl<_Iter, _Iter> {
+  _LIBCPP_HIDE_FROM_ABI static constexpr auto __unwrap(_Iter __first, _Iter __last) {
+    return pair{std::__unwrap_iter(std::move(__first)), std::__unwrap_iter(std::move(__last))};
+  }
+
+  _LIBCPP_HIDE_FROM_ABI static constexpr auto
+  __rewrap(_Iter __orig_iter, decltype(std::__unwrap_iter(__orig_iter)) __iter) {
+    return std::__rewrap_iter(std::move(__orig_iter), std::move(__iter));
+  }
+};
+
+template <class _Iter, class _Sent>
+_LIBCPP_HIDE_FROM_ABI constexpr auto __unwrap_range(_Iter __first, _Sent __last) {
+  return __unwrap_range_impl<_Iter, _Sent>::__unwrap(std::move(__first), std::move(__last));
+}
+
+template <class _Sent,
+          class _Iter,
+          class _Unwrapped = decltype(std::__unwrap_range(std::declval<_Iter>(), std::declval<_Sent>()))>
+_LIBCPP_HIDE_FROM_ABI constexpr _Iter __rewrap_range(_Iter __orig_iter, _Unwrapped __iter) {
+  return __unwrap_range_impl<_Iter, _Sent>::__rewrap(std::move(__orig_iter), std::move(__iter));
+}
+#else // _LIBCPP_STD_VER > 17
+template <class _Iter, class _Unwrapped = decltype(std::__unwrap_iter(std::declval<_Iter>()))>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR pair<_Unwrapped, _Unwrapped> __unwrap_range(_Iter __first, _Iter __last) {
+  return std::make_pair(std::__unwrap_iter(std::move(__first)), std::__unwrap_iter(std::move(__last)));
+}
+
+template <class _Iter, class _Unwrapped = decltype(std::__unwrap_iter(std::declval<_Iter>()))>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __rewrap_range(_Iter __orig_iter, _Unwrapped __iter) {
+  return std::__rewrap_iterstd::move((__orig_iter), std::move(__iter));
+}
+#endif // _LIBCPP_STD_VER > 17
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_UNWRAP_RANGE_H

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/sort_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/sort_heap.h'}}
 #include <__algorithm/stable_partition.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/stable_partition.h'}}
 #include <__algorithm/stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/stable_sort.h'}}
 #include <__algorithm/swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/swap_ranges.h'}}
 #include <__algorithm/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/transform.h'}}
 #include <__algorithm/unique.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unique.h'}}
 #include <__algorithm/unique_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unique_copy.h'}}
 #include <__algorithm/unwrap_iter.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unwrap_iter.h'}}
+#include <__algorithm/unwrap_range.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unwrap_range.h'}}
 #include <__algorithm/upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/upper_bound.h'}}
 #include <__availability> // expected-error@*:* {{use of private header from outside its module: '__availability'}}
 #include <__bit/bit_cast.h> // expected-error@*:* {{use of private header from outside its module: '__bit/bit_cast.h'}}
 #include <__bit/byteswap.h> // expected-error@*:* {{use of private header from outside its module: '__bit/byteswap.h'}}
 #include <__bit_reference> // expected-error@*:* {{use of private header from outside its module: '__bit_reference'}}
 #include <__bits> // expected-error@*:* {{use of private header from outside its module: '__bits'}}
 #include <__charconv/chars_format.h> // expected-error@*:* {{use of private header from outside its module: '__charconv/chars_format.h'}}
 #include <__charconv/from_chars_result.h> // expected-error@*:* {{use of private header from outside its module: '__charconv/from_chars_result.h'}}

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

constexpr void test_iterators() {
       auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
       auto ret = std::ranges::copy(range, Out(out.data()));
       assert(base(ret.in) == in.data());
       assert(base(ret.out) == out.data());
     }
   }
 }
 
+template <class In, class Out>
+constexpr void test_sentinels() {
+  test_iterators<In, Out>();
+  test_iterators<In, Out, sized_sentinel<In>>();
+  test_iterators<In, Out, sentinel_wrapper<In>>();
+}
+
 template <class Out>
 constexpr void test_in_iterators() {
   test_iterators<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>();
-  test_iterators<forward_iterator<int*>, Out>();
-  test_iterators<bidirectional_iterator<int*>, Out>();
-  test_iterators<random_access_iterator<int*>, Out>();
-  test_iterators<contiguous_iterator<int*>, Out>();
+  test_sentinels<forward_iterator<int*>, Out>();
+  test_sentinels<bidirectional_iterator<int*>, Out>();
+  test_sentinels<random_access_iterator<int*>, Out>();
+  test_sentinels<contiguous_iterator<int*>, Out>();
 }
 
 template <class Out>
 constexpr void test_proxy_in_iterators() {
   test_iterators<ProxyIterator<cpp20_input_iterator<int*>>, Out, sentinel_wrapper<ProxyIterator<cpp20_input_iterator<int*>>>>();
   test_iterators<ProxyIterator<forward_iterator<int*>>, Out>();
   test_iterators<ProxyIterator<bidirectional_iterator<int*>>, Out>();
   test_iterators<ProxyIterator<random_access_iterator<int*>>, Out>();