diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -141,6 +141,7 @@ __algorithm/unique.h __algorithm/unique_copy.h __algorithm/unwrap_iter.h + __algorithm/unwrap_range.h __algorithm/upper_bound.h __assert __availability diff --git a/libcxx/include/__algorithm/copy.h b/libcxx/include/__algorithm/copy.h --- a/libcxx/include/__algorithm/copy.h +++ b/libcxx/include/__algorithm/copy.h @@ -10,6 +10,7 @@ #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> @@ -66,32 +67,29 @@ __copy_impl(reverse_iterator<_InIter> __first, reverse_iterator<_InIter> __last, reverse_iterator<_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 __unwrapped_range = std::__unwrap_range(std::move(__first).base(), std::move(__last).base()); + auto __first_base = __unwrapped_range.first.first; + auto __last_base = __unwrapped_range.second; + auto __result_un = std::__unwrap_iter(std::move(__result).base()); + + auto __result_base = __result_un.first; + 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))); + return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result_un.second, __result_first))); } -template ::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 ::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> +template +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)); + auto __unwrapped_range = std::__unwrap_range(std::move(__first), std::move(__last)); + auto __first_un = std::move(__unwrapped_range.first); + auto __result_un = std::__unwrap_iter(std::move(__result)); + auto __ret = + std::__copy_impl(std::move(__first_un.first), std::move(__unwrapped_range.second), std::move(__result_un.first)); + return std::make_pair( + std::__rewrap_iter(__first_un.second, std::move(__ret.first)), + std::__rewrap_iter(__result_un.second, std::move(__ret.second))); } template diff --git a/libcxx/include/__algorithm/copy_backward.h b/libcxx/include/__algorithm/copy_backward.h --- a/libcxx/include/__algorithm/copy_backward.h +++ b/libcxx/include/__algorithm/copy_backward.h @@ -14,6 +14,7 @@ #include <__config> #include <__iterator/iterator_traits.h> #include <__iterator/reverse_iterator.h> +#include <__utility/move.h> #include #include @@ -35,10 +36,13 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) { - auto __ret = std::__copy_backward_impl(std::__unwrap_iter(__first), - std::__unwrap_iter(__last), - std::__unwrap_iter(__result)); - return pair<_Iter1, _Iter2>(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); + auto __first_un = std::__unwrap_iter(std::move(__first)); + auto __result_un = std::__unwrap_iter(std::move(__result)); + auto __ret = std::__copy_backward_impl(__first_un.first, + std::__unwrap_iter(__last).first, + __result_un.first); + return pair<_Iter1, _Iter2>( + std::__rewrap_iter(__first_un.second, __ret.first), std::__rewrap_iter(__result_un.second, __ret.second)); } template diff --git a/libcxx/include/__algorithm/move.h b/libcxx/include/__algorithm/move.h --- a/libcxx/include/__algorithm/move.h +++ b/libcxx/include/__algorithm/move.h @@ -77,31 +77,25 @@ __move_impl(reverse_iterator<_InIter> __first, reverse_iterator<_InIter> __last, reverse_iterator<_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); + auto __first_base = std::__unwrap_iter(__first.base()).first; + auto __last_base = std::__unwrap_iter(__last.base()).first; + auto __result_un = std::__unwrap_iter(__result.base()); + auto __result_first = __result_un.first - (__first_base - __last_base); std::__move_impl(__last_base, __first_base, __result_first); - return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); + return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result_un.second, __result_first))); } template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -__enable_if_t::value - && is_copy_constructible<_Sent>::value - && is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > +pair<_InIter, _OutIter> __move(_InIter __first, _Sent __last, _OutIter __result) { - auto __ret = std::__move_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)); -} - -template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -__enable_if_t::value - || !is_copy_constructible<_Sent>::value - || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > -__move(_InIter __first, _Sent __last, _OutIter __result) { - return std::__move_impl(std::move(__first), std::move(__last), std::move(__result)); + auto __first_un = std::__unwrap_iter(std::move(__first)); + auto __result_un = std::__unwrap_iter(std::move(__result)); + auto __ret = + std::__move_impl(std::move(__first_un.first), std::__unwrap_iter(__last).first, std::move(__result_un.first)); + return std::make_pair( + std::__rewrap_iter(__first_un.second, std::move(__ret.first)), + std::__rewrap_iter(__result_un.second, std::move(__ret.second))); } template diff --git a/libcxx/include/__algorithm/move_backward.h b/libcxx/include/__algorithm/move_backward.h --- a/libcxx/include/__algorithm/move_backward.h +++ b/libcxx/include/__algorithm/move_backward.h @@ -67,10 +67,11 @@ if (__libcpp_is_constant_evaluated()) { return _VSTD::__move_backward_constexpr(__first, __last, __result); } else { - return _VSTD::__rewrap_iter(__result, - _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); + auto __result_un = _VSTD::__unwrap_iter(__result); + return std::__rewrap_iter(__result_un.second, + _VSTD::__move_backward(_VSTD::__unwrap_iter(__first).first, + _VSTD::__unwrap_iter(__last).first, + __result_un.first)); } } diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -587,7 +587,7 @@ if (__libcpp_is_constant_evaluated()) { std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); } else { - std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp)); + std::__sort<_Comp_ref>(std::__unwrap_iter(__first).first, std::__unwrap_iter(__last).first, _Comp_ref(__comp)); } } diff --git a/libcxx/include/__algorithm/unwrap_iter.h b/libcxx/include/__algorithm/unwrap_iter.h --- a/libcxx/include/__algorithm/unwrap_iter.h +++ b/libcxx/include/__algorithm/unwrap_iter.h @@ -12,6 +12,8 @@ #include <__config> #include <__iterator/iterator_traits.h> #include <__memory/pointer_traits.h> +#include <__utility/move.h> +#include <__utility/pair.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -37,60 +39,54 @@ template ::value> struct __unwrap_iter_impl { - static _LIBCPP_CONSTEXPR _Iter - __apply(_Iter __i) _NOEXCEPT { - return __i; - } + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __rewrap(_Iter, _Iter __iter) { return __iter; } + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __unwrap(_Iter __i) _NOEXCEPT { return __i; } }; #ifndef _LIBCPP_ENABLE_DEBUG_MODE template struct __unwrap_iter_impl<_Iter, true> { - static _LIBCPP_CONSTEXPR decltype(_VSTD::__to_address(declval<_Iter>())) - __apply(_Iter __i) _NOEXCEPT { - return _VSTD::__to_address(__i); - } + using _ToAddressT = decltype(std::__to_address(declval<_Iter>())); + + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __rewrap(_Iter __orig_iter, _ToAddressT __unwrapped_iter) { + return __orig_iter + (__unwrapped_iter - std::__to_address(__orig_iter)); + } + + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ToAddressT __unwrap(_Iter __i) _NOEXCEPT { + return std::__to_address(__i); + } }; #endif // !_LIBCPP_ENABLE_DEBUG_MODE -template > -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -decltype(_Impl::__apply(declval<_Iter>())) -__unwrap_iter(_Iter __i) _NOEXCEPT -{ - return _Impl::__apply(__i); +template, + __enable_if_t::value, int> = 0> +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair())), _Iter> +__unwrap_iter(_Iter __i) _NOEXCEPT { + auto __unwrapped = _Impl::__unwrap(__i); + return std::make_pair(std::move(__unwrapped), std::move(__i)); } -template -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)); - } -}; +struct __move_only_iterator_tag {}; -template -struct __rewrap_iter_impl<_OrigIter, _OrigIter> { - static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter, _OrigIter __result) { - return __result; - } -}; +template::value, int> = 0> +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +pair<_Iter, nullptr_t> __unwrap_iter(_Iter __i) _NOEXCEPT { + return std::make_pair(std::move(__i), __move_only_iterator_tag{}); +} -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR -_OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) -{ - return __result; +template > +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _OrigIter __rewrap_iter(_OrigIter __orig_iter, _Iter __iter) _NOEXCEPT { + return _Impl::__rewrap(std::move(__orig_iter), std::move(__iter)); } -template > -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR -_OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result) -{ - return _Impl::__apply(__first, __result); +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __rewrap_iter(__move_only_iterator_tag, _Iter __iter) _NOEXCEPT { + return __iter; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/unwrap_range.h b/libcxx/include/__algorithm/unwrap_range.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/unwrap_range.h @@ -0,0 +1,58 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#if _LIBCPP_STD_VER > 17 +template +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)).first}; + } + + _LIBCPP_HIDE_FROM_ABI static constexpr auto __unwrap(_Iter __first, _Sent __last) { + return pair{pair{std::move(__first), __move_only_iterator_tag{}}, std::move(__last)}; + } +}; +#endif + +template ()))> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR pair<_Unwrapped, decltype(_Unwrapped::first)> +__unwrap_range(_Iter __first, _Iter __last) { + return std::make_pair(std::__unwrap_iter(__first), std::__unwrap_iter(__last).first); +} + +#if _LIBCPP_STD_VER > 17 +template +_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)); +} +#endif // _LIBCPP_STD_VER > 17 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_UNWRAP_RANGE_H diff --git a/libcxx/include/__format/buffer.h b/libcxx/include/__format/buffer.h --- a/libcxx/include/__format/buffer.h +++ b/libcxx/include/__format/buffer.h @@ -229,7 +229,7 @@ _LIBCPP_HIDE_FROM_ABI explicit __format_buffer(_OutIt __out_it) requires( same_as<_Storage, __direct_storage<_CharT>>) - : __output_(_VSTD::__unwrap_iter(__out_it), size_t(-1), this), + : __output_(std::__unwrap_iter(__out_it).first, size_t(-1), this), __writer_(_VSTD::move(__out_it)) {} _LIBCPP_HIDE_FROM_ABI auto make_output_iterator() { @@ -311,7 +311,7 @@ public: _LIBCPP_HIDE_FROM_ABI explicit __format_to_n_buffer_base(_OutIt __out_it, _Size __n) - : __output_(_VSTD::__unwrap_iter(__out_it), __n, this), __writer_(_VSTD::move(__out_it)) { + : __output_(std::__unwrap_iter(__out_it).first, __n, this), __writer_(_VSTD::move(__out_it)) { if (__n <= 0) [[unlikely]] __output_.reset(__storage_.begin(), __storage_.__buffer_size); } diff --git a/libcxx/include/__iterator/reverse_iterator.h b/libcxx/include/__iterator/reverse_iterator.h --- a/libcxx/include/__iterator/reverse_iterator.h +++ b/libcxx/include/__iterator/reverse_iterator.h @@ -327,41 +327,16 @@ template 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 -struct __rewrap_iter_impl<_ReverseWrapper<_OrigIter>, _UnwrappedIter> { - template - struct _ReverseWrapperCount { - static _LIBCPP_CONSTEXPR const size_t value = 1; - }; - - template - struct _ReverseWrapperCount<_ReverseWrapper<_Iter> > { - static _LIBCPP_CONSTEXPR const size_t value = 1 + _ReverseWrapperCount<_Iter>::value; - }; - - template = 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))); - } + using _UnwrappedIter = decltype(__unwrap_iter_impl<_Iter>::__unwrap(std::declval<_Iter>())); - template = 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); + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ReverseWrapper<_Iter> + __rewrap(_ReverseWrapper<_Iter> __orig_iter, _UnwrappedIter __unwrapped_iter) { + return _ReverseWrapper<_Iter>( + reverse_iterator<_Iter>(__unwrap_iter_impl<_Iter>::__rewrap(__orig_iter.base().base(), __unwrapped_iter))); } - _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR _ReverseWrapper<_OrigIter> __apply(_ReverseWrapper<_OrigIter> __iter1, - _UnwrappedIter __iter2) { - return __rewrap<_ReverseWrapperCount<_OrigIter>::value>(__iter1, __iter2); + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _UnwrappedIter __unwrap(_ReverseWrapper<_Iter> __i) _NOEXCEPT { + return __unwrap_iter_impl<_Iter>::__unwrap(__i.base().base()); } }; diff --git a/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp b/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp --- a/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp +++ b/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp @@ -21,7 +21,7 @@ #include "test_macros.h" template -using UnwrapT = decltype(std::__unwrap_iter(std::declval())); +using UnwrapT = decltype(std::__unwrap_iter(std::declval()).first); template using rev_iter = std::reverse_iterator; @@ -45,10 +45,10 @@ 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(rev_iter(str.begin()))) == str.data()); - assert(std::__unwrap_iter(rev_rev_iter(rev_iter(str.end()))) == str.data() + str.size()); + assert(std::__unwrap_iter(str.begin()).first == str.data()); + assert(std::__unwrap_iter(str.end()).first == str.data() + str.size()); + assert(std::__unwrap_iter(rev_rev_iter(rev_iter(str.begin()))).first == str.data()); + assert(std::__unwrap_iter(rev_rev_iter(rev_iter(str.end()))).first == str.data() + str.size()); return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp @@ -95,13 +95,20 @@ } } +template +constexpr void test_sentinels() { + test_iterators(); + test_iterators>(); + test_iterators>(); +} + template constexpr void test_in_iterators() { test_iterators, Out, sentinel_wrapper>>(); - test_iterators, Out>(); - test_iterators, Out>(); - test_iterators, Out>(); - test_iterators, Out>(); + test_sentinels, Out>(); + test_sentinels, Out>(); + test_sentinels, Out>(); + test_sentinels, Out>(); } constexpr bool test() {