diff --git a/libcxx/.clang-format b/libcxx/.clang-format --- a/libcxx/.clang-format +++ b/libcxx/.clang-format @@ -68,7 +68,7 @@ NamespaceIndentation: Inner PackConstructorInitializers: NextLine -PenaltyIndentedWhitespace: 61 +PenaltyIndentedWhitespace: 2 Language: Cpp Standard: c++20 diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -154,6 +154,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> @@ -88,10 +89,11 @@ && 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 diff --git a/libcxx/include/__algorithm/set_intersection.h b/libcxx/include/__algorithm/set_intersection.h --- a/libcxx/include/__algorithm/set_intersection.h +++ b/libcxx/include/__algorithm/set_intersection.h @@ -14,6 +14,7 @@ #include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 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,7 @@ #include <__config> #include <__iterator/iterator_traits.h> #include <__memory/pointer_traits.h> +#include <__utility/move.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -20,77 +21,50 @@ _LIBCPP_BEGIN_NAMESPACE_STD -// 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. +// TODO: Change the name of __unwrap_iter_impl to something more appropriate +// The job of __unwrap_iter is to remove iterator wrappers (like reverse_iterator or __wrap_iter), +// to reduce the number of template instantiations and to enable pointer-based optimizations e.g. in std::copy. // 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. +// "unwrapped" result back into the original iterator type. Doing that is the job of __rewrap_iter. +// Default case - we can't unwrap anything 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 +// It's a contiguous iterator, so we can use a raw pointer instead 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(std::declval<_Iter>())); -#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 -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)); + 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)); } -}; -template -struct __rewrap_iter_impl<_OrigIter, _OrigIter> { - static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter, _OrigIter __result) { - return __result; + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ToAddressT __unwrap(_Iter __i) _NOEXCEPT { + return std::__to_address(__i); } }; -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR -_OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) -{ - return __result; +#endif // !_LIBCPP_ENABLE_DEBUG_MODE + +template, + __enable_if_t::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +decltype(_Impl::__unwrap(std::declval<_Iter>())) __unwrap_iter(_Iter __i) _NOEXCEPT { + return _Impl::__unwrap(__i); } -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 _OrigIter __rewrap_iter(_OrigIter __orig_iter, _Iter __iter) _NOEXCEPT { + return _Impl::__rewrap(std::move(__orig_iter), std::move(__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,88 @@ +//===----------------------------------------------------------------------===// +// +// 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))}; + } + + _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(__orig_iter, __iter); + } + + _LIBCPP_HIDE_FROM_ABI static constexpr auto __rewrap(_Iter, _Iter __iter) { return __iter; } +}; + +template +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(__orig_iter, __iter); + } +}; + +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)); +} + +template (), 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 +template ()))> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR pair<_Unwrapped, _Unwrapped> __unwrap_range(_Iter __first, _Iter __last) { + return std::make_pair(std::__unwrap_iter(__first), std::__unwrap_iter(__last)); +} + +template ()))> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __rewrap_range(_Iter __orig_iter, _Unwrapped __iter) { + return std::__rewrap_iter(__orig_iter, __iter); +} +#endif + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_UNWRAP_RANGE_H 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 @@ -332,41 +332,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/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -191,6 +191,7 @@ #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'}} 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>(); } template diff --git a/libcxx/utils/libcxx/test/params.py b/libcxx/utils/libcxx/test/params.py --- a/libcxx/utils/libcxx/test/params.py +++ b/libcxx/utils/libcxx/test/params.py @@ -38,6 +38,9 @@ # TODO(mordante) investigate a solution for this issue. '-Wno-tautological-compare', + # -Wstringop-overread seems to be a bit buggy currently + '-Wno-stringop-overread', + # These warnings should be enabled in order to support the MSVC # team using the test suite; They enable the warnings below and # expect the test suite to be clean.