diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1639,12 +1639,22 @@ __value_, __equal_to<__v, _Tp>()); } -// __unwrap_iter +// __unwrap_iter, __rewrap_iter -// The job of __unwrap_iter is to lower iterators-that-are-tantamount-to-pointers -// (such as vector::iterator) into pointers, to reduce the number of template +// The job of __unwrap_iter is to lower contiguous iterators (such as +// vector::iterator) into pointers, to reduce the number of template // instantiations and to enable pointer-based optimizations e.g. in std::copy. +// For iterators that are not contiguous, it must be a no-op. // In debug mode, we don't do this. +// +// __unwrap_iter is non-constexpr for user-defined iterators whose +// `to_address` and/or `operator->` is non-constexpr. This is okay; but we +// try to avoid doing __unwrap_iter in constant-evaluated contexts anyway. +// +// Some algorithms (e.g. std::copy, but not std::sort) need to convert an +// "unwrapped" result back into a contiguous iterator. Since contiguous iterators +// are random-access, we can do this portably using iterator arithmetic; this +// is the job of __rewrap_iter. template ::value> struct __unwrap_iter_impl { @@ -1674,6 +1684,20 @@ return _Impl::__apply(__i); } +template +_OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) +{ + return __result; +} + +template +_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)); +} + // copy template @@ -1716,11 +1740,12 @@ copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { if (__libcpp_is_constant_evaluated()) { - return _VSTD::__copy_constexpr( - _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); + return _VSTD::__copy_constexpr(__first, __last, __result); } else { - return _VSTD::__copy( - _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); + return _VSTD::__rewrap_iter(__result, + _VSTD::__copy(_VSTD::__unwrap_iter(__first), + _VSTD::__unwrap_iter(__last), + _VSTD::__unwrap_iter(__result))); } } @@ -1770,13 +1795,12 @@ _BidirectionalIterator2 __result) { if (__libcpp_is_constant_evaluated()) { - return _VSTD::__copy_backward_constexpr(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result)); + return _VSTD::__copy_backward_constexpr(__first, __last, __result); } else { - return _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result)); + return _VSTD::__rewrap_iter(__result, + _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first), + _VSTD::__unwrap_iter(__last), + _VSTD::__unwrap_iter(__result))); } } @@ -1843,8 +1867,6 @@ // move -// __move_constexpr exists so that __move doesn't call itself when delegating to the constexpr -// version of __move. template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _OutputIterator @@ -1873,8 +1895,6 @@ >::type __move(_Tp* __first, _Tp* __last, _Up* __result) { - if (__libcpp_is_constant_evaluated()) - return _VSTD::__move_constexpr(__first, __last, __result); const size_t __n = static_cast(__last - __first); if (__n > 0) _VSTD::memmove(__result, __first, __n * sizeof(_Up)); @@ -1886,13 +1906,18 @@ _OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return _VSTD::__move(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); + if (__libcpp_is_constant_evaluated()) { + return _VSTD::__move_constexpr(__first, __last, __result); + } else { + return _VSTD::__rewrap_iter(__result, + _VSTD::__move(_VSTD::__unwrap_iter(__first), + _VSTD::__unwrap_iter(__last), + _VSTD::__unwrap_iter(__result))); + } } // move_backward -// __move_backward_constexpr exists so that __move_backward doesn't call itself when delegating to -// the constexpr version of __move_backward. template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _OutputIterator @@ -1921,8 +1946,6 @@ >::type __move_backward(_Tp* __first, _Tp* __last, _Up* __result) { - if (__libcpp_is_constant_evaluated()) - return _VSTD::__move_backward_constexpr(__first, __last, __result); const size_t __n = static_cast(__last - __first); if (__n > 0) { @@ -1938,7 +1961,14 @@ move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - return _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); + 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))); + } } // iter_swap diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy.pass.cpp @@ -40,40 +40,49 @@ test() { test_copy, output_iterator >(); - test_copy, input_iterator >(); test_copy, forward_iterator >(); test_copy, bidirectional_iterator >(); test_copy, random_access_iterator >(); test_copy, int*>(); test_copy, output_iterator >(); - test_copy, input_iterator >(); test_copy, forward_iterator >(); test_copy, bidirectional_iterator >(); test_copy, random_access_iterator >(); test_copy, int*>(); test_copy, output_iterator >(); - test_copy, input_iterator >(); test_copy, forward_iterator >(); test_copy, bidirectional_iterator >(); test_copy, random_access_iterator >(); test_copy, int*>(); test_copy, output_iterator >(); - test_copy, input_iterator >(); test_copy, forward_iterator >(); test_copy, bidirectional_iterator >(); test_copy, random_access_iterator >(); test_copy, int*>(); test_copy >(); - test_copy >(); test_copy >(); test_copy >(); test_copy >(); test_copy(); +#if TEST_STD_VER > 17 + test_copy, contiguous_iterator>(); + test_copy, contiguous_iterator>(); + test_copy, contiguous_iterator>(); + test_copy, contiguous_iterator>(); + test_copy>(); + + test_copy, output_iterator>(); + test_copy, forward_iterator>(); + test_copy, bidirectional_iterator>(); + test_copy, random_access_iterator>(); + test_copy, int*>(); +#endif + return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy_backward.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy_backward.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy_backward.pass.cpp @@ -53,6 +53,17 @@ test_copy_backward >(); test_copy_backward(); +#if TEST_STD_VER > 17 + test_copy_backward, bidirectional_iterator>(); + test_copy_backward, random_access_iterator>(); + test_copy_backward, int*>(); + + test_copy_backward, contiguous_iterator>(); + test_copy_backward, contiguous_iterator>(); + test_copy_backward, contiguous_iterator>(); + test_copy_backward>(); +#endif + return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp @@ -64,35 +64,30 @@ int main(int, char**) { test, output_iterator >(); - test, input_iterator >(); test, forward_iterator >(); test, bidirectional_iterator >(); test, random_access_iterator >(); test, int*>(); test, output_iterator >(); - test, input_iterator >(); test, forward_iterator >(); test, bidirectional_iterator >(); test, random_access_iterator >(); test, int*>(); test, output_iterator >(); - test, input_iterator >(); test, forward_iterator >(); test, bidirectional_iterator >(); test, random_access_iterator >(); test, int*>(); test, output_iterator >(); - test, input_iterator >(); test, forward_iterator >(); test, bidirectional_iterator >(); test, random_access_iterator >(); test, int*>(); test >(); - test >(); test >(); test >(); test >(); @@ -100,35 +95,30 @@ #if TEST_STD_VER >= 11 test1*>, output_iterator*> >(); - test1*>, input_iterator*> >(); test1*>, forward_iterator*> >(); test1*>, bidirectional_iterator*> >(); test1*>, random_access_iterator*> >(); test1*>, std::unique_ptr*>(); test1*>, output_iterator*> >(); - test1*>, input_iterator*> >(); test1*>, forward_iterator*> >(); test1*>, bidirectional_iterator*> >(); test1*>, random_access_iterator*> >(); test1*>, std::unique_ptr*>(); test1*>, output_iterator*> >(); - test1*>, input_iterator*> >(); test1*>, forward_iterator*> >(); test1*>, bidirectional_iterator*> >(); test1*>, random_access_iterator*> >(); test1*>, std::unique_ptr*>(); test1*>, output_iterator*> >(); - test1*>, input_iterator*> >(); test1*>, forward_iterator*> >(); test1*>, bidirectional_iterator*> >(); test1*>, random_access_iterator*> >(); test1*>, std::unique_ptr*>(); test1*, output_iterator*> >(); - test1*, input_iterator*> >(); test1*, forward_iterator*> >(); test1*, bidirectional_iterator*> >(); test1*, random_access_iterator*> >(); @@ -136,34 +126,70 @@ #endif // TEST_STD_VER >= 11 #if TEST_STD_VER > 17 + test, contiguous_iterator>(); + test, contiguous_iterator>(); + test, contiguous_iterator>(); + test, contiguous_iterator>(); + test>(); + test, output_iterator>(); + test, forward_iterator>(); + test, bidirectional_iterator>(); + test, random_access_iterator>(); + test, int*>(); + test, contiguous_iterator>(); + + test1*>, contiguous_iterator*>>(); + test1*>, contiguous_iterator*>>(); + test1*>, contiguous_iterator*>>(); + test1*>, contiguous_iterator*>>(); + test1*, contiguous_iterator*>>(); + test1*>, output_iterator*>>(); + test1*>, forward_iterator*>>(); + test1*>, bidirectional_iterator*>>(); + test1*>, random_access_iterator*>>(); + test1*>, std::unique_ptr*>(); + test1*>, contiguous_iterator*>>(); + static_assert(test, input_iterator >()); static_assert(test, forward_iterator >()); static_assert(test, bidirectional_iterator >()); static_assert(test, random_access_iterator >()); + static_assert(test, contiguous_iterator >()); static_assert(test, int*>()); static_assert(test, input_iterator >()); static_assert(test, forward_iterator >()); static_assert(test, bidirectional_iterator >()); static_assert(test, random_access_iterator >()); + static_assert(test, contiguous_iterator >()); static_assert(test, int*>()); static_assert(test, input_iterator >()); static_assert(test, forward_iterator >()); static_assert(test, bidirectional_iterator >()); static_assert(test, random_access_iterator >()); + static_assert(test, contiguous_iterator >()); static_assert(test, int*>()); static_assert(test, input_iterator >()); static_assert(test, forward_iterator >()); static_assert(test, bidirectional_iterator >()); static_assert(test, random_access_iterator >()); + static_assert(test, contiguous_iterator >()); static_assert(test, int*>()); + static_assert(test, input_iterator >()); + static_assert(test, forward_iterator >()); + static_assert(test, bidirectional_iterator >()); + static_assert(test, random_access_iterator >()); + static_assert(test, contiguous_iterator >()); + static_assert(test, int*>()); + static_assert(test >()); static_assert(test >()); static_assert(test >()); static_assert(test >()); + static_assert(test >()); static_assert(test()); #endif // TEST_STD_VER > 17 diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp @@ -89,16 +89,40 @@ #endif // TEST_STD_VER >= 11 #if TEST_STD_VER > 17 + test, contiguous_iterator>(); + test, contiguous_iterator>(); + test>(); + test, bidirectional_iterator>(); + test, random_access_iterator>(); + test, int*>(); + test, contiguous_iterator>(); + + test1*>, contiguous_iterator*>>(); + test1*>, contiguous_iterator*>>(); + test1*, contiguous_iterator*>>(); + test1*>, bidirectional_iterator*>>(); + test1*>, random_access_iterator*>>(); + test1*>, std::unique_ptr*>(); + test1*>, contiguous_iterator*>>(); + static_assert(test, bidirectional_iterator >()); static_assert(test, random_access_iterator >()); + static_assert(test, contiguous_iterator >()); static_assert(test, int*>()); static_assert(test, bidirectional_iterator >()); static_assert(test, random_access_iterator >()); + static_assert(test, contiguous_iterator >()); static_assert(test, int*>()); + static_assert(test, bidirectional_iterator >()); + static_assert(test, random_access_iterator >()); + static_assert(test, contiguous_iterator >()); + static_assert(test, int*>()); + static_assert(test >()); static_assert(test >()); + static_assert(test >()); static_assert(test()); #endif // TEST_STD_VER > 17 diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp @@ -79,22 +79,37 @@ test_pointers<17, int, random_access_iterator >(); #if TEST_STD_VER >= 20 + test<7, int, contiguous_iterator>(); + test<257, int, contiguous_iterator>(); + test<7, MoveOnly, contiguous_iterator>(); + test<257, MoveOnly, contiguous_iterator>(); + test_pointers<17, char, contiguous_iterator>(); + test_pointers<17, const char, contiguous_iterator>(); + test_pointers<17, int, contiguous_iterator>(); + static_assert(test<7, int, int*>()); static_assert(test<7, int, random_access_iterator>()); + static_assert(test<7, int, contiguous_iterator>()); static_assert(test<257, int, int*>()); static_assert(test<257, int, random_access_iterator>()); + static_assert(test<257, int, contiguous_iterator>()); static_assert(test<7, MoveOnly, MoveOnly*>()); static_assert(test<7, MoveOnly, random_access_iterator>()); + static_assert(test<7, MoveOnly, contiguous_iterator>()); static_assert(test<257, MoveOnly, MoveOnly*>()); static_assert(test<257, MoveOnly, random_access_iterator>()); + static_assert(test<257, MoveOnly, contiguous_iterator>()); static_assert(test_pointers<17, char, char**>()); static_assert(test_pointers<17, char, random_access_iterator>()); + static_assert(test_pointers<17, char, contiguous_iterator>()); static_assert(test_pointers<17, const char, const char**>()); static_assert(test_pointers<17, const char, random_access_iterator>()); + static_assert(test_pointers<17, const char, contiguous_iterator>()); static_assert(test_pointers<17, int, int**>()); static_assert(test_pointers<17, int, random_access_iterator>()); + static_assert(test_pointers<17, int, contiguous_iterator>()); #endif return 0; diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp @@ -80,22 +80,37 @@ test_pointers<17, int, random_access_iterator >(); #if TEST_STD_VER >= 20 + test<7, int, contiguous_iterator>(); + test<257, int, contiguous_iterator>(); + test<7, MoveOnly, contiguous_iterator>(); + test<257, MoveOnly, contiguous_iterator>(); + test_pointers<17, char, contiguous_iterator>(); + test_pointers<17, const char, contiguous_iterator>(); + test_pointers<17, int, contiguous_iterator>(); + static_assert(test<7, int, int*>()); static_assert(test<7, int, random_access_iterator>()); + static_assert(test<7, int, contiguous_iterator>()); static_assert(test<257, int, int*>()); static_assert(test<257, int, random_access_iterator>()); + static_assert(test<257, int, contiguous_iterator>()); static_assert(test<7, MoveOnly, MoveOnly*>()); static_assert(test<7, MoveOnly, random_access_iterator>()); + static_assert(test<7, MoveOnly, contiguous_iterator>()); static_assert(test<257, MoveOnly, MoveOnly*>()); static_assert(test<257, MoveOnly, random_access_iterator>()); + static_assert(test<257, MoveOnly, contiguous_iterator>()); static_assert(test_pointers<17, char, char**>()); static_assert(test_pointers<17, char, random_access_iterator>()); + static_assert(test_pointers<17, char, contiguous_iterator>()); static_assert(test_pointers<17, const char, const char**>()); static_assert(test_pointers<17, const char, random_access_iterator>()); + static_assert(test_pointers<17, const char, contiguous_iterator>()); static_assert(test_pointers<17, int, int**>()); static_assert(test_pointers<17, int, random_access_iterator>()); + static_assert(test_pointers<17, int, contiguous_iterator>()); #endif return 0; diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -315,6 +315,8 @@ template class contiguous_iterator { + static_assert(std::is_pointer_v, "Things probably break in this case"); + It it_; template friend class contiguous_iterator; @@ -324,14 +326,14 @@ typedef typename std::iterator_traits::difference_type difference_type; typedef It pointer; typedef typename std::iterator_traits::reference reference; - typedef typename std::iterator_traits::value_type element_type; + typedef typename std::remove_pointer::type element_type; TEST_CONSTEXPR_CXX14 It base() const {return it_;} TEST_CONSTEXPR_CXX14 contiguous_iterator() : it_() {} explicit TEST_CONSTEXPR_CXX14 contiguous_iterator(It it) : it_(it) {} template - TEST_CONSTEXPR_CXX14 contiguous_iterator(const contiguous_iterator& u) :it_(u.it_) {} + TEST_CONSTEXPR_CXX14 contiguous_iterator(const contiguous_iterator& u) : it_(u.it_) {} TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;} TEST_CONSTEXPR_CXX14 pointer operator->() const {return it_;}