From fb3477a4dab0fb75c4bac858c33e6006dcc173ea Mon Sep 17 00:00:00 2001 From: Nikolas Klauser Date: Fri, 17 Jun 2022 15:59:53 +0200 Subject: [PATCH] [libc++] Unwrap reverse_iterator> in __unwrap_iter Simplify the implementation of `std::copy` and `std::move` by using `__unwrap_iter` and `__rewrap_iter` to unwrap and rewrap `reverse_iterator>` instead of specializing `__copy_impl` and `__move_impl`. Reviewed By: ldionne, #libc Spies: wenlei, libcxx-commits Differential Revision: https://reviews.llvm.org/D127049 --- libcxx/include/__algorithm/copy.h | 19 ---- libcxx/include/__algorithm/unwrap_iter.h | 22 +++- libcxx/include/__iterator/reverse_iterator.h | 44 ++++++++ .../alg.modifying.operations/copy.pass.cpp | 113 ++++++++++++++++----- libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp | 63 ++++++++++++ 5 files changed, 214 insertions(+), 47 deletions(-) create mode 100644 libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp diff --git a/libcxx/include/__algorithm/copy.h b/libcxx/include/__algorithm/copy.h index 2a4e535..886a1ac 100644 --- a/libcxx/include/__algorithm/copy.h +++ b/libcxx/include/__algorithm/copy.h @@ -74,13 +74,6 @@ __copy_impl(reverse_iterator<_InIter> __first, return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); } -template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair >, reverse_iterator > > -__copy_impl(reverse_iterator > __first, - reverse_iterator > __last, - reverse_iterator > __result); - template ::value && is_copy_constructible<_Sent>::value @@ -101,18 +94,6 @@ __copy(_InIter __first, _Sent __last, _OutIter __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 -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair >, reverse_iterator > > -__copy_impl(reverse_iterator > __first, - reverse_iterator > __last, - reverse_iterator > __result) { - auto __ret = std::__copy(__first.base().base(), __last.base().base(), __result.base().base()); - return std::make_pair(reverse_iterator >(reverse_iterator<_InIter>(__ret.first)), - reverse_iterator >(reverse_iterator<_OutIter>(__ret.second))); -} - template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator diff --git a/libcxx/include/__algorithm/unwrap_iter.h b/libcxx/include/__algorithm/unwrap_iter.h index be33194..7d1807b 100644 --- a/libcxx/include/__algorithm/unwrap_iter.h +++ b/libcxx/include/__algorithm/unwrap_iter.h @@ -63,6 +63,22 @@ __unwrap_iter(_Iter __i) _NOEXCEPT return _Impl::__apply(__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)); + } +}; + +template +struct __rewrap_iter_impl<_OrigIter, _OrigIter> { + static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter, _OrigIter __result) { + return __result; + } +}; + template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) @@ -70,13 +86,11 @@ _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) return __result; } -template +template > _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 diff --git a/libcxx/include/__iterator/reverse_iterator.h b/libcxx/include/__iterator/reverse_iterator.h index bc07cf3..89bda19 100644 --- a/libcxx/include/__iterator/reverse_iterator.h +++ b/libcxx/include/__iterator/reverse_iterator.h @@ -10,6 +10,7 @@ #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> @@ -321,6 +322,49 @@ reverse_iterator<_Iter> make_reverse_iterator(_Iter __i) } #endif +template +using _ReverseWrapper = reverse_iterator >; + +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))); + } + + 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); + } + + _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 diff --git a/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp b/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp index d12a238..0eac954 100644 --- a/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp +++ b/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// // 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. @@ -19,6 +20,7 @@ #include #include #include +#include #include struct S { @@ -43,6 +45,7 @@ struct NotIncrementableIt { 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) { @@ -50,6 +53,7 @@ struct NotIncrementableIt { } constexpr T& operator*() { return *i; } + constexpr T& operator*() const { return *i; } constexpr T* operator->() { return i; } constexpr T* operator->() const { return i; } @@ -58,6 +62,11 @@ struct NotIncrementableIt { return *this; } + constexpr NotIncrementableIt& operator++(int) { + assert(false); + return *this; + } + constexpr NotIncrementableIt& operator--() { assert(false); return *this; @@ -70,39 +79,95 @@ struct NotIncrementableIt { static_assert(std::__is_cpp17_contiguous_iterator>::value); -template +template * = nullptr> +constexpr auto wrap_n_times(Iter i) { + return i; +} + +template * = nullptr> +constexpr auto wrap_n_times(Iter i) { + return std::make_reverse_iterator(wrap_n_times(i)); +} + +static_assert(std::is_same_v(std::declval())), + std::reverse_iterator>>); + +template constexpr void test_normal() { - S a[] = {1, 2, 3, 4}; - S b[] = {0, 0, 0, 0}; - std::copy(Iter(a), Iter(a + 4), Iter(b)); - assert(std::equal(a, a + 4, b)); + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + std::copy(wrap_n_times(Iter(a)), wrap_n_times(Iter(a + 4)), wrap_n_times(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(Iter(a)), + wrap_n_times(Iter(a + 4)), + wrap_n_times(Iter(b))); + 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(Iter(a)), wrap_n_times(Iter(a + 4))); + std::ranges::copy(range, Iter(b)); + assert(std::equal(a, a + 4, b)); + } } -template +template 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))); + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + std::copy(std::make_reverse_iterator(wrap_n_times(Iter(a + 4))), + std::make_reverse_iterator(wrap_n_times(Iter(a))), + std::make_reverse_iterator(wrap_n_times(Iter(b + 4)))); + assert(std::equal(a, a + 4, b)); + } + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + std::ranges::copy(std::make_reverse_iterator(wrap_n_times(Iter(a + 4))), + std::make_reverse_iterator(wrap_n_times(Iter(a))), + std::make_reverse_iterator(wrap_n_times(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(std::make_reverse_iterator(Iter(a + 4))), + wrap_n_times(std::make_reverse_iterator(Iter(a)))); + std::ranges::copy(range, std::make_reverse_iterator(wrap_n_times(Iter(b + 4)))); + assert(std::equal(a, a + 4, b)); + } +} + +template +constexpr void test_normal_reverse() { + test_normal(); + test_normal>(); + test_reverse(); + test_reverse>(); } -template -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)))); +template +constexpr void test_out_count() { + test_normal_reverse(); + test_normal_reverse(); + test_normal_reverse(); + test_normal_reverse(); + test_normal_reverse(); } constexpr bool test() { - test_normal(); - test_normal>(); - test_reverse(); - test_reverse>(); - test_reverse_reverse(); - test_reverse_reverse>(); + test_out_count<0>(); + test_out_count<2>(); + test_out_count<4>(); + test_out_count<6>(); + test_out_count<8>(); return true; } diff --git a/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp b/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp new file mode 100644 index 0000000..ff1a8d5 --- /dev/null +++ b/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// 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 +#include +#include +#include + +#include "test_iterators.h" +#include "test_macros.h" + +template +using UnwrapT = decltype(std::__unwrap_iter(std::declval())); + +template +using rev_iter = std::reverse_iterator; + +template +using rev_rev_iter = rev_iter >; + +static_assert(std::is_same, int*>::value, ""); +static_assert(std::is_same >, int*>::value, ""); +static_assert(std::is_same >, std::reverse_iterator >::value, ""); +static_assert(std::is_same >, int*>::value, ""); +static_assert(std::is_same > >, int*>::value, ""); +static_assert(std::is_same > > >, rev_iter > >::value, ""); + +static_assert(std::is_same >, random_access_iterator >::value, ""); +static_assert(std::is_same > >, rev_iter > >::value, ""); +static_assert(std::is_same > >, random_access_iterator >::value, ""); +static_assert(std::is_same > > >, rev_iter > >::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(rev_iter(str.begin()))) == str.data()); + assert(std::__unwrap_iter(rev_rev_iter(rev_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; +} -- 2.7.4