diff --git a/libcxx/docs/Cxx2aStatusIssuesStatus.csv b/libcxx/docs/Cxx2aStatusIssuesStatus.csv --- a/libcxx/docs/Cxx2aStatusIssuesStatus.csv +++ b/libcxx/docs/Cxx2aStatusIssuesStatus.csv @@ -176,7 +176,7 @@ "`3244 `__","Constraints for ``Source``\ in |sect|\ [fs.path.req] insufficiently constrainty","Belfast","","" "`3241 `__","``chrono-spec``\ grammar ambiguity in |sect|\ [time.format]","Belfast","","" "`3257 `__","Missing feature testing macro update from P0858","Belfast","","" -"`3256 `__","Feature testing macro for ``constexpr``\ algorithms","Belfast","","" +"`3256 `__","Feature testing macro for ``constexpr``\ algorithms","Belfast","|Complete|","12.0" "`3273 `__","Specify ``weekday_indexed``\ to range of ``[0, 7]``\ ","Belfast","","" "`3070 `__","``path::lexically_relative``\ causes surprising results if a filename can also be a *root-name*","Belfast","","" "`3266 `__","``to_chars(bool)``\ should be deleted","Belfast","","" diff --git a/libcxx/docs/Cxx2aStatusPaperStatus.csv b/libcxx/docs/Cxx2aStatusPaperStatus.csv --- a/libcxx/docs/Cxx2aStatusPaperStatus.csv +++ b/libcxx/docs/Cxx2aStatusPaperStatus.csv @@ -40,7 +40,7 @@ "`P0759R1 `__","LWG","fpos Requirements","Rapperswil","|Complete|","11.0" "`P0769R2 `__","LWG","Add shift to ","Rapperswil","|Complete|","12.0" "`P0788R3 `__","LWG","Standard Library Specification in a Concepts and Contracts World","Rapperswil","*Removed in Cologne*","n/a" -"`P0879R0 `__","LWG","Constexpr for swap and swap related functions Also resolves LWG issue 2800.","Rapperswil","","" +"`P0879R0 `__","LWG","Constexpr for swap and swap related functions Also resolves LWG issue 2800.","Rapperswil","|Complete|","13.0" "`P0887R1 `__","LWG","The identity metafunction","Rapperswil","|Complete|","8.0" "`P0892R2 `__","CWG","explicit(bool)","Rapperswil","","" "`P0898R3 `__","LWG","Standard Library Concepts","Rapperswil","|In Progress|","" diff --git a/libcxx/docs/FeatureTestMacroTable.rst b/libcxx/docs/FeatureTestMacroTable.rst --- a/libcxx/docs/FeatureTestMacroTable.rst +++ b/libcxx/docs/FeatureTestMacroTable.rst @@ -200,7 +200,7 @@ ------------------------------------------------- ----------------- ``__cpp_lib_concepts`` *unimplemented* ------------------------------------------------- ----------------- - ``__cpp_lib_constexpr_algorithms`` *unimplemented* + ``__cpp_lib_constexpr_algorithms`` ``201806L`` ------------------------------------------------- ----------------- ``__cpp_lib_constexpr_complex`` *unimplemented* ------------------------------------------------- ----------------- diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -351,11 +351,11 @@ is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); template - void + constexpr void // constexpr in C++20 sort(RandomAccessIterator first, RandomAccessIterator last); template - void + constexpr void // constexpr in C++20 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template @@ -4073,7 +4073,6 @@ void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - // _Compare is known to be a reference type typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; const difference_type __limit = is_trivially_copy_constructible::value && @@ -4262,47 +4261,13 @@ } } -// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare -template +template inline _LIBCPP_INLINE_VISIBILITY void -sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) +__sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) { - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__sort<_Comp_ref>(__first, __last, _Comp_ref(__comp)); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -void -sort(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::sort(__first, __last, __less::value_type>()); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -void -sort(_Tp** __first, _Tp** __last) -{ - _VSTD::sort((uintptr_t*)__first, (uintptr_t*)__last, __less()); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -void -sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last) -{ - _VSTD::sort(__first.base(), __last.base()); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -void -sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp) -{ - typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; - _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp); + __less __comp; + _VSTD::__sort<__less&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); } _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less&, char*>(char*, char*, __less&)) @@ -5277,6 +5242,11 @@ __less::value_type>()); } +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 void +__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, + _Compare __comp); + // nth_element template @@ -5504,6 +5474,45 @@ _VSTD::nth_element(__first, __nth, __last, __less::value_type>()); } +// sort + +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 void +__sort_constexpr(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) +{ + if (__libcpp_is_constant_evaluated()) { + _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp); + } else { + _VSTD::__sort<_Compare>(__first, __last, __comp); + } +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +void +sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) +{ + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + _VSTD::__sort_constexpr<_Comp_ref>(__first, __last, _Comp_ref(__comp)); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +void +sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp) +{ + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + _VSTD::__sort_constexpr<_Comp_ref>(__first.base(), __last.base(), _Comp_ref(__comp)); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +void +sort(_RandomAccessIterator __first, _RandomAccessIterator __last) +{ + _VSTD::sort(__first, __last, __less::value_type>()); +} + // includes template diff --git a/libcxx/include/version b/libcxx/include/version --- a/libcxx/include/version +++ b/libcxx/include/version @@ -293,7 +293,7 @@ # define __cpp_lib_char8_t 201811L # endif // # define __cpp_lib_concepts 202002L -// # define __cpp_lib_constexpr_algorithms 201806L +# define __cpp_lib_constexpr_algorithms 201806L // # define __cpp_lib_constexpr_complex 201711L # define __cpp_lib_constexpr_dynamic_alloc 201907L # define __cpp_lib_constexpr_functional 201907L 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 new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp @@ -0,0 +1,101 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// template +// requires ShuffleIterator +// && LessThanComparable +// void +// sort(Iter first, Iter last); + +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" +#include "MoveOnly.h" + +template +TEST_CONSTEXPR_CXX20 bool test() +{ + int orig[N] = {}; + unsigned x = 1; + for (int i=0; i < N; ++i) { + x = (x * 1664525) + 1013904223; + orig[i] = x % 1000; + } + T work[N] = {}; + std::copy(orig, orig+N, work); + std::sort(Iter(work), Iter(work+N)); + assert(std::is_sorted(work, work+N)); + assert(std::is_permutation(work, work+N, orig)); + + return true; +} + +template +TEST_CONSTEXPR_CXX20 bool test_pointers() +{ + T data[N] = {}; + T *orig[N] = {}; + unsigned x = 1; + for (int i=0; i < N; ++i) { + orig[i] = &data[x % 258]; + } + T *work[N] = {}; + std::copy(orig, orig+N, work); + std::sort(Iter(work), Iter(work+N)); + assert(std::is_sorted(work, work+N)); + assert(std::is_permutation(work, work+N, orig)); + + return true; +} + +int main(int, char**) +{ + test<7, int, int*>(); + test<7, int, random_access_iterator >(); + test<257, int, int*>(); + test<257, int, random_access_iterator >(); + +#if TEST_STD_VER >= 11 + test<7, MoveOnly, MoveOnly*>(); + test<7, MoveOnly, random_access_iterator >(); + test<257, MoveOnly, MoveOnly*>(); + test<257, MoveOnly, random_access_iterator >(); +#endif + + test_pointers<17, char, char**>(); + test_pointers<17, char, random_access_iterator >(); + test_pointers<17, const char, const char**>(); + test_pointers<17, const char, random_access_iterator >(); + test_pointers<17, int, int**>(); + test_pointers<17, int, random_access_iterator >(); + +#if TEST_STD_VER >= 20 + static_assert(test<7, int, int*>()); + static_assert(test<7, int, random_access_iterator>()); + static_assert(test<257, int, int*>()); + static_assert(test<257, int, random_access_iterator>()); + + static_assert(test<7, MoveOnly, MoveOnly*>()); + static_assert(test<7, MoveOnly, random_access_iterator>()); + static_assert(test<257, MoveOnly, MoveOnly*>()); + static_assert(test<257, MoveOnly, random_access_iterator>()); + + static_assert(test_pointers<17, char, char**>()); + static_assert(test_pointers<17, char, random_access_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, int, int**>()); + static_assert(test_pointers<17, int, random_access_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 new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp @@ -0,0 +1,102 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// template Compare> +// requires ShuffleIterator +// && CopyConstructible +// void +// sort(Iter first, Iter last, Compare comp); + +#include +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" +#include "MoveOnly.h" + +template +TEST_CONSTEXPR_CXX20 bool test() +{ + int orig[N] = {}; + unsigned x = 1; + for (int i=0; i < N; ++i) { + x = (x * 1664525) + 1013904223; + orig[i] = x % 1000; + } + T work[N] = {}; + std::copy(orig, orig+N, work); + std::sort(Iter(work), Iter(work+N), std::greater()); + assert(std::is_sorted(work, work+N, std::greater())); + assert(std::is_permutation(work, work+N, orig)); + + return true; +} + +template +TEST_CONSTEXPR_CXX20 bool test_pointers() +{ + T data[N] = {}; + T *orig[N] = {}; + unsigned x = 1; + for (int i=0; i < N; ++i) { + orig[i] = &data[x % 258]; + } + T *work[N] = {}; + std::copy(orig, orig+N, work); + std::sort(Iter(work), Iter(work+N), std::greater()); + assert(std::is_sorted(work, work+N, std::greater())); + assert(std::is_permutation(work, work+N, orig)); + + return true; +} + +int main(int, char**) +{ + test<7, int, int*>(); + test<7, int, random_access_iterator >(); + test<257, int, int*>(); + test<257, int, random_access_iterator >(); + +#if TEST_STD_VER >= 11 + test<7, MoveOnly, MoveOnly*>(); + test<7, MoveOnly, random_access_iterator >(); + test<257, MoveOnly, MoveOnly*>(); + test<257, MoveOnly, random_access_iterator >(); +#endif + + test_pointers<17, char, char**>(); + test_pointers<17, char, random_access_iterator >(); + test_pointers<17, const char, const char**>(); + test_pointers<17, const char, random_access_iterator >(); + test_pointers<17, int, int**>(); + test_pointers<17, int, random_access_iterator >(); + +#if TEST_STD_VER >= 20 + static_assert(test<7, int, int*>()); + static_assert(test<7, int, random_access_iterator>()); + static_assert(test<257, int, int*>()); + static_assert(test<257, int, random_access_iterator>()); + + static_assert(test<7, MoveOnly, MoveOnly*>()); + static_assert(test<7, MoveOnly, random_access_iterator>()); + static_assert(test<257, MoveOnly, MoveOnly*>()); + static_assert(test<257, MoveOnly, random_access_iterator>()); + + static_assert(test_pointers<17, char, char**>()); + static_assert(test_pointers<17, char, random_access_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, int, int**>()); + static_assert(test_pointers<17, int, random_access_iterator>()); +#endif + + return 0; +} diff --git a/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp b/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp --- a/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp +++ b/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp @@ -148,17 +148,11 @@ # error "__cpp_lib_clamp should have the value 201603L in c++20" # endif -# if !defined(_LIBCPP_VERSION) -# ifndef __cpp_lib_constexpr_algorithms -# error "__cpp_lib_constexpr_algorithms should be defined in c++20" -# endif -# if __cpp_lib_constexpr_algorithms != 201806L -# error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20" -# endif -# else // _LIBCPP_VERSION -# ifdef __cpp_lib_constexpr_algorithms -# error "__cpp_lib_constexpr_algorithms should not be defined because it is unimplemented in libc++!" -# endif +# ifndef __cpp_lib_constexpr_algorithms +# error "__cpp_lib_constexpr_algorithms should be defined in c++20" +# endif +# if __cpp_lib_constexpr_algorithms != 201806L +# error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20" # endif # if !defined(_LIBCPP_VERSION) @@ -217,17 +211,11 @@ # error "__cpp_lib_clamp should have the value 201603L in c++2b" # endif -# if !defined(_LIBCPP_VERSION) -# ifndef __cpp_lib_constexpr_algorithms -# error "__cpp_lib_constexpr_algorithms should be defined in c++2b" -# endif -# if __cpp_lib_constexpr_algorithms != 201806L -# error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b" -# endif -# else // _LIBCPP_VERSION -# ifdef __cpp_lib_constexpr_algorithms -# error "__cpp_lib_constexpr_algorithms should not be defined because it is unimplemented in libc++!" -# endif +# ifndef __cpp_lib_constexpr_algorithms +# error "__cpp_lib_constexpr_algorithms should be defined in c++2b" +# endif +# if __cpp_lib_constexpr_algorithms != 201806L +# error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b" # endif # if !defined(_LIBCPP_VERSION) diff --git a/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp b/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp --- a/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp +++ b/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp @@ -2376,17 +2376,11 @@ # endif # endif -# if !defined(_LIBCPP_VERSION) -# ifndef __cpp_lib_constexpr_algorithms -# error "__cpp_lib_constexpr_algorithms should be defined in c++20" -# endif -# if __cpp_lib_constexpr_algorithms != 201806L -# error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20" -# endif -# else // _LIBCPP_VERSION -# ifdef __cpp_lib_constexpr_algorithms -# error "__cpp_lib_constexpr_algorithms should not be defined because it is unimplemented in libc++!" -# endif +# ifndef __cpp_lib_constexpr_algorithms +# error "__cpp_lib_constexpr_algorithms should be defined in c++20" +# endif +# if __cpp_lib_constexpr_algorithms != 201806L +# error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20" # endif # if !defined(_LIBCPP_VERSION) @@ -3582,17 +3576,11 @@ # endif # endif -# if !defined(_LIBCPP_VERSION) -# ifndef __cpp_lib_constexpr_algorithms -# error "__cpp_lib_constexpr_algorithms should be defined in c++2b" -# endif -# if __cpp_lib_constexpr_algorithms != 201806L -# error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b" -# endif -# else // _LIBCPP_VERSION -# ifdef __cpp_lib_constexpr_algorithms -# error "__cpp_lib_constexpr_algorithms should not be defined because it is unimplemented in libc++!" -# endif +# ifndef __cpp_lib_constexpr_algorithms +# error "__cpp_lib_constexpr_algorithms should be defined in c++2b" +# endif +# if __cpp_lib_constexpr_algorithms != 201806L +# error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b" # endif # if !defined(_LIBCPP_VERSION) diff --git a/libcxx/utils/generate_feature_test_macro_components.py b/libcxx/utils/generate_feature_test_macro_components.py --- a/libcxx/utils/generate_feature_test_macro_components.py +++ b/libcxx/utils/generate_feature_test_macro_components.py @@ -182,7 +182,6 @@ "name": "__cpp_lib_constexpr_algorithms", "values": { "c++20": 201806 }, "headers": ["algorithm"], - "unimplemented": True, }, { "name": "__cpp_lib_constexpr_complex", "values": { "c++20": 201711 },