Message ID | 20191205124640.GA1500787@redhat.com |
---|---|
State | New |
Headers | show |
Series | libstdc++: Define std::lexicographical_compare_three_way for C++20 | expand |
On 05/12/2019 13:46, Jonathan Wakely wrote: > commit 5012548fd62526fdf5e04aeacee2b127efbac0e0 > Author: Jonathan Wakely <jwakely@redhat.com> > Date: Thu Dec 5 12:23:53 2019 +0000 > > libstdc++: Define std::lexicographical_compare_three_way for C++20 > > * include/bits/stl_algobase.h (lexicographical_compare_three_way): > Define for C++20. > * testsuite/25_algorithms/lexicographical_compare_three_way/1.cc: New > test. > * testsuite/25_algorithms/lexicographical_compare_three_way/ > constexpr.cc: New test. > > diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h > index 98d324827ed..a2fd306e6d0 100644 > --- a/libstdc++-v3/include/bits/stl_algobase.h > +++ b/libstdc++-v3/include/bits/stl_algobase.h [...] > @@ -1456,6 +1459,104 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO > __gnu_cxx::__ops::__iter_comp_iter(__comp)); > } > > +#if __cpp_lib_three_way_comparison > +#if __cpp_lib_concepts > + // Iter points to a contiguous range of unsigned narrow character type > + // or std::byte, suitable for comparison by memcmp. > + template<typename _Iter> > + concept __is_byte_iter = contiguous_iterator<_Iter> > + && __is_byte<iter_value_t<_Iter>>::__value != 0 > + && !__gnu_cxx::__numeric_traits<iter_value_t<_Iter>>::__is_signed; > + > + // Return a struct with two members, initialized to the smaller of x and y > + // (or x if they compare equal) and the result of the comparison x <=> y. > + template<typename _Tp> > + constexpr auto > + __min_cmp(_Tp __x, _Tp __y) > + { > + struct _Res { > + _Tp _M_min; > + decltype(__x <=> __y) _M_cmp; > + }; > + auto __c = __x <=> __y; > + if (__c > 0) > + return _Res{__y, __c}; > + return _Res{__x, __c}; > + } > +#endif [...] > + > + template<typename _InputIter1, typename _InputIter2> > + constexpr auto > + lexicographical_compare_three_way(_InputIter1 __first1, > + _InputIter1 __last1, > + _InputIter2 __first2, > + _InputIter2 __last2) > + { > + return std::lexicographical_compare_three_way(__first1, __last1, > + __first2, __last2, > + compare_three_way{}); FYI, the above fails with -std=c++2a and recent Clang trunk after <https://github.com/llvm/llvm-project/commit/bc633a42dd409dbeb456263e3388b8caa4680aa0> "Mark the major papers for C++20 consistent comparisons as 'done', and start publishing the corresponding feature-test macro": Clang now defines __cpp_impl_three_way_comparison (so libstdc++-v3/include/std/version defines __cpp_lib_three_way_comparison) but still doesn't define __cpp_lib_concepts, so libstdc++-v3/libsupc++/compare doesn't define compare_three_way. I locally managed that for now with extending the surrounding #if __cpp_lib_three_way_comparison with && __cpp_lib_concepts > + } > +#endif // three_way_comparison
On 29/12/19 12:07 +0100, Stephan Bergmann wrote: >On 05/12/2019 13:46, Jonathan Wakely wrote: >>commit 5012548fd62526fdf5e04aeacee2b127efbac0e0 >>Author: Jonathan Wakely <jwakely@redhat.com> >>Date: Thu Dec 5 12:23:53 2019 +0000 >> >> libstdc++: Define std::lexicographical_compare_three_way for C++20 >> * include/bits/stl_algobase.h (lexicographical_compare_three_way): >> Define for C++20. >> * testsuite/25_algorithms/lexicographical_compare_three_way/1.cc: New >> test. >> * testsuite/25_algorithms/lexicographical_compare_three_way/ >> constexpr.cc: New test. >> >>diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h >>index 98d324827ed..a2fd306e6d0 100644 >>--- a/libstdc++-v3/include/bits/stl_algobase.h >>+++ b/libstdc++-v3/include/bits/stl_algobase.h >[...] >>@@ -1456,6 +1459,104 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO >> __gnu_cxx::__ops::__iter_comp_iter(__comp)); >> } >>+#if __cpp_lib_three_way_comparison >>+#if __cpp_lib_concepts >>+ // Iter points to a contiguous range of unsigned narrow character type >>+ // or std::byte, suitable for comparison by memcmp. >>+ template<typename _Iter> >>+ concept __is_byte_iter = contiguous_iterator<_Iter> >>+ && __is_byte<iter_value_t<_Iter>>::__value != 0 >>+ && !__gnu_cxx::__numeric_traits<iter_value_t<_Iter>>::__is_signed; >>+ >>+ // Return a struct with two members, initialized to the smaller of x and y >>+ // (or x if they compare equal) and the result of the comparison x <=> y. >>+ template<typename _Tp> >>+ constexpr auto >>+ __min_cmp(_Tp __x, _Tp __y) >>+ { >>+ struct _Res { >>+ _Tp _M_min; >>+ decltype(__x <=> __y) _M_cmp; >>+ }; >>+ auto __c = __x <=> __y; >>+ if (__c > 0) >>+ return _Res{__y, __c}; >>+ return _Res{__x, __c}; >>+ } >>+#endif >[...] >>+ >>+ template<typename _InputIter1, typename _InputIter2> >>+ constexpr auto >>+ lexicographical_compare_three_way(_InputIter1 __first1, >>+ _InputIter1 __last1, >>+ _InputIter2 __first2, >>+ _InputIter2 __last2) >>+ { >>+ return std::lexicographical_compare_three_way(__first1, __last1, >>+ __first2, __last2, >>+ compare_three_way{}); > >FYI, the above fails with -std=c++2a and recent Clang trunk after <https://github.com/llvm/llvm-project/commit/bc633a42dd409dbeb456263e3388b8caa4680aa0> >"Mark the major papers for C++20 consistent comparisons as 'done', and >start publishing the corresponding feature-test macro": Clang now >defines __cpp_impl_three_way_comparison (so >libstdc++-v3/include/std/version defines >__cpp_lib_three_way_comparison) but still doesn't define >__cpp_lib_concepts, so libstdc++-v3/libsupc++/compare doesn't define >compare_three_way. > >I locally managed that for now with extending the surrounding > > #if __cpp_lib_three_way_comparison > >with > > && __cpp_lib_concepts > >>+ } >>+#endif // three_way_comparison Should be fixed at r279861 on trunk (also attached). This leaves the five-argument overload defined for Clang, just not the four-argument one that uses std::compare_three_way. We could define that overload unconditionally and do something like this, but I prefer to just omit it rather than define it badly: return std::lexicographical_compare_three_way(__first1, __last1, __first2, __last2, #if __cpp_lib_concepts compare_three_way{} #else [](auto&& __l, auto&& __r) { return __l <=> __r; } #endif // concepts );
On 03/01/20 14:54 +0000, Jonathan Wakely wrote: >On 29/12/19 12:07 +0100, Stephan Bergmann wrote: >>FYI, the above fails with -std=c++2a and recent Clang trunk after <https://github.com/llvm/llvm-project/commit/bc633a42dd409dbeb456263e3388b8caa4680aa0> >>"Mark the major papers for C++20 consistent comparisons as 'done', >>and start publishing the corresponding feature-test macro": Clang >>now defines __cpp_impl_three_way_comparison (so >>libstdc++-v3/include/std/version defines >>__cpp_lib_three_way_comparison) but still doesn't define >>__cpp_lib_concepts, so libstdc++-v3/libsupc++/compare doesn't define >>compare_three_way. >> >>I locally managed that for now with extending the surrounding >> >>#if __cpp_lib_three_way_comparison >> >>with >> >>&& __cpp_lib_concepts >> >>>+ } >>>+#endif // three_way_comparison > >Should be fixed at r279861 on trunk (also attached). This leaves the >five-argument overload defined for Clang, just not the four-argument >one that uses std::compare_three_way. > >We could define that overload unconditionally and do something like >this, but I prefer to just omit it rather than define it badly: > > return std::lexicographical_compare_three_way(__first1, __last1, > __first2, __last2, >#if __cpp_lib_concepts > compare_three_way{} >#else > [](auto&& __l, auto&& __r) > { return __l <=> __r; } >#endif // concepts > ); After writing that, I realised that a better approach might be: --- a/libstdc++-v3/libsupc++/compare +++ b/libstdc++-v3/libsupc++/compare @@ -40,7 +40,9 @@ namespace std { -#define __cpp_lib_three_way_comparison 201711L +#if __cpp_lib_concepts +# define __cpp_lib_three_way_comparison 201711L +#endif // [cmp.categories], comparison category types i.e. don't pretend the library supports three-way comparison if that support is incomplete. That will still fix the Clang problem because if that macro isn't defined then we don't define either overload of std::lexicographical_compare_three_way. That seems cleaner to me. Anybody disagree?
On 03/01/20 15:03 +0000, Jonathan Wakely wrote: >On 03/01/20 14:54 +0000, Jonathan Wakely wrote: >>On 29/12/19 12:07 +0100, Stephan Bergmann wrote: >>>FYI, the above fails with -std=c++2a and recent Clang trunk after <https://github.com/llvm/llvm-project/commit/bc633a42dd409dbeb456263e3388b8caa4680aa0> >>>"Mark the major papers for C++20 consistent comparisons as 'done', >>>and start publishing the corresponding feature-test macro": Clang >>>now defines __cpp_impl_three_way_comparison (so >>>libstdc++-v3/include/std/version defines >>>__cpp_lib_three_way_comparison) but still doesn't define >>>__cpp_lib_concepts, so libstdc++-v3/libsupc++/compare doesn't >>>define compare_three_way. >>> >>>I locally managed that for now with extending the surrounding >>> >>>#if __cpp_lib_three_way_comparison >>> >>>with >>> >>>&& __cpp_lib_concepts >>> >>>>+ } >>>>+#endif // three_way_comparison >> >>Should be fixed at r279861 on trunk (also attached). This leaves the >>five-argument overload defined for Clang, just not the four-argument >>one that uses std::compare_three_way. >> >>We could define that overload unconditionally and do something like >>this, but I prefer to just omit it rather than define it badly: >> >> return std::lexicographical_compare_three_way(__first1, __last1, >> __first2, __last2, >>#if __cpp_lib_concepts >> compare_three_way{} >>#else >> [](auto&& __l, auto&& __r) >> { return __l <=> __r; } >>#endif // concepts >> ); > >After writing that, I realised that a better approach might be: > >--- a/libstdc++-v3/libsupc++/compare >+++ b/libstdc++-v3/libsupc++/compare >@@ -40,7 +40,9 @@ > > namespace std > { >-#define __cpp_lib_three_way_comparison 201711L >+#if __cpp_lib_concepts >+# define __cpp_lib_three_way_comparison 201711L >+#endif > > // [cmp.categories], comparison category types > > >i.e. don't pretend the library supports three-way comparison if that >support is incomplete. That will still fix the Clang problem because >if that macro isn't defined then we don't define either overload of >std::lexicographical_compare_three_way. > >That seems cleaner to me. Anybody disagree? I'm committing this patch to do that. Tested powerpc64le-linux, committed to trunk.
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 98d324827ed..a2fd306e6d0 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -72,6 +72,9 @@ #if __cplusplus >= 201103L # include <type_traits> #endif +#if __cplusplus > 201703L +# include <compare> +#endif namespace std _GLIBCXX_VISIBILITY(default) { @@ -1456,6 +1459,104 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __gnu_cxx::__ops::__iter_comp_iter(__comp)); } +#if __cpp_lib_three_way_comparison +#if __cpp_lib_concepts + // Iter points to a contiguous range of unsigned narrow character type + // or std::byte, suitable for comparison by memcmp. + template<typename _Iter> + concept __is_byte_iter = contiguous_iterator<_Iter> + && __is_byte<iter_value_t<_Iter>>::__value != 0 + && !__gnu_cxx::__numeric_traits<iter_value_t<_Iter>>::__is_signed; + + // Return a struct with two members, initialized to the smaller of x and y + // (or x if they compare equal) and the result of the comparison x <=> y. + template<typename _Tp> + constexpr auto + __min_cmp(_Tp __x, _Tp __y) + { + struct _Res { + _Tp _M_min; + decltype(__x <=> __y) _M_cmp; + }; + auto __c = __x <=> __y; + if (__c > 0) + return _Res{__y, __c}; + return _Res{__x, __c}; + } +#endif + + /** + * @brief Performs dictionary comparison on ranges. + * @ingroup sorting_algorithms + * @param __first1 An input iterator. + * @param __last1 An input iterator. + * @param __first2 An input iterator. + * @param __last2 An input iterator. + * @param __comp A @link comparison_functors comparison functor@endlink. + * @return The comparison category that `__comp(*__first1, *__first2)` + * returns. + */ + template<typename _InputIter1, typename _InputIter2, typename _Comp> + constexpr auto + lexicographical_compare_three_way(_InputIter1 __first1, + _InputIter1 __last1, + _InputIter2 __first2, + _InputIter2 __last2, + _Comp __comp) + -> decltype(__comp(*__first1, *__first2)) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + +#if __cpp_lib_concepts && __cpp_lib_is_constant_evaluated + using _Cat = decltype(__comp(*__first1, *__first2)); + static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>); + + if (!std::is_constant_evaluated()) + if constexpr (same_as<_Comp, __detail::_Synth3way> + || same_as<_Comp, compare_three_way>) + if constexpr (__is_byte_iter<_InputIter1>) + if constexpr (__is_byte_iter<_InputIter2>) + { + const auto [__len, __lencmp] + = std::__min_cmp(__last1 - __first1, __last2 - __first2); + if (__len) + { + const auto __c + = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0; + if (__c != 0) + return __c; + } + return __lencmp; + } +#endif // concepts && is_constant_evaluated + while (__first1 != __last1 && __first2 != __last2) + { + if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0) + return __cmp; + ++__first1; + ++__first2; + } + return __first1 != __last1 ? strong_ordering::greater + : __first2 != __last2 ? strong_ordering::less : strong_ordering::equal; + } + + template<typename _InputIter1, typename _InputIter2> + constexpr auto + lexicographical_compare_three_way(_InputIter1 __first1, + _InputIter1 __last1, + _InputIter2 __first2, + _InputIter2 __last2) + { + return std::lexicographical_compare_three_way(__first1, __last1, + __first2, __last2, + compare_three_way{}); + } +#endif // three_way_comparison + template<typename _InputIterator1, typename _InputIterator2, typename _BinaryPredicate> _GLIBCXX20_CONSTEXPR diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc new file mode 100644 index 00000000000..b1e70e80de7 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc @@ -0,0 +1,129 @@ +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +// Lambda that calls lexicographical_compare_three_way on two ranges. +// Arguments are passed by value intentionally, so that a copy of the range +// is traversed and the original is not modified. Otherwise when the range +// has input iterators the range will be consumed after the first comparison. +auto lexicomp3 = [](auto r1, auto r2) { + return std::lexicographical_compare_three_way(r1.begin(), r1.end(), + r2.begin(), r2.end()); +}; + +void +test01() +{ + using __gnu_test::test_container; + using __gnu_test::input_iterator_wrapper; + using __gnu_test::forward_iterator_wrapper; + int arr1[] = { 0, 1, 2, 3, 4, 5, 6, 7 }; + int arr2[] = { 0, 1, 2, 3, 4, 5, 6, 777 }; + + { + test_container<int, input_iterator_wrapper> c1(arr1); + test_container<int, input_iterator_wrapper> c2(arr2); + VERIFY( lexicomp3(c1, c1) == 0 ); + VERIFY( lexicomp3(c1, c2) < 0 ); + VERIFY( lexicomp3(c2, c1) > 0 ); + } + + { + test_container<int, input_iterator_wrapper> c1(arr1, arr1+6); + test_container<int, input_iterator_wrapper> c2(arr2, arr2+6); + VERIFY( lexicomp3(c1, c1) == 0 ); + VERIFY( lexicomp3(c1, c2) == 0 ); + VERIFY( lexicomp3(c2, c1) == 0 ); + } + + { + test_container<int, input_iterator_wrapper> c1(arr1); + test_container<int, input_iterator_wrapper> c2(arr2, arr2+7); + VERIFY( lexicomp3(c1, c1) == 0 ); + VERIFY( lexicomp3(c1, c2) > 0 ); + VERIFY( lexicomp3(c2, c1) < 0 ); + } + + { + test_container<int, input_iterator_wrapper> c1(arr1); + test_container<int, forward_iterator_wrapper> c2(arr2); + VERIFY( lexicomp3(c1, c1) == 0 ); + VERIFY( lexicomp3(c1, c2) < 0 ); + VERIFY( lexicomp3(c2, c1) > 0 ); + } + + { + test_container<int, input_iterator_wrapper> c1(arr1); + test_container<int, forward_iterator_wrapper> c2(arr2, arr2+7); + VERIFY( lexicomp3(c1, c1) == 0 ); + VERIFY( lexicomp3(c2, c2) == 0 ); + VERIFY( lexicomp3(c1, c2) > 0 ); + VERIFY( lexicomp3(c2, c1) < 0 ); + } + + { + test_container<int, forward_iterator_wrapper> c1(arr1, arr1+7); + test_container<int, input_iterator_wrapper> c2(arr2); + VERIFY( lexicomp3(c1, c1) == 0 ); + VERIFY( lexicomp3(c2, c2) == 0 ); + VERIFY( lexicomp3(c1, c2) < 0 ); + VERIFY( lexicomp3(c2, c1) > 0 ); + } +} + +void +test02() +{ + using __gnu_test::test_container; + using __gnu_test::input_iterator_wrapper; + using __gnu_test::forward_iterator_wrapper; + std::array<unsigned char, 8> c1 = { 0, 1, 2, 3, 4, 5, 6, 7 }; + std::array<unsigned char, 8> c2 = { 0, 1, 2, 3, 4, 5, 6, 77 }; + + VERIFY( lexicomp3(c1, c1) == 0 ); + VERIFY( lexicomp3(c1, c2) < 0 ); + VERIFY( lexicomp3(c2, c1) > 0 ); + + std::array<unsigned char, 7> c3 = { 0, 1, 2, 3, 4, 5, 6 }; + VERIFY( lexicomp3(c3, c3) == 0 ); + VERIFY( lexicomp3(c1, c3) > 0 ); + VERIFY( lexicomp3(c3, c1) < 0 ); +} + +void +test03() +{ + unsigned char a[2] = { 1, 2 }; + unsigned char* p = nullptr; + // ensure memcmp not called with nullptr + VERIFY( std::lexicographical_compare_three_way(p, p, a, a+2) < 0 ); + VERIFY( std::lexicographical_compare_three_way(a, a+2, p, p) > 0 ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc new file mode 100644 index 00000000000..5d1e15cc4f3 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc @@ -0,0 +1,65 @@ +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do compile { target c++2a } } + +#include <algorithm> + +constexpr bool +test01(int i) +{ + int a1[] = { 0, 1, 2, 3, 4, 5, 6, i, 8 }; + long a2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; + + return std::lexicographical_compare_three_way(a1, a1+0, a2, a2+0) == 0 + && std::lexicographical_compare_three_way(a1, a1+9, a2, a2+9) == (i <=> 7) + && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+7) == 0 + && std::lexicographical_compare_three_way(a1, a1+8, a2, a2+7) > 0 + && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+8) < 0; +} + +static_assert( test01(~7) ); +static_assert( test01(7) ); +static_assert( test01(8) ); + +constexpr bool +test02(unsigned char i) +{ + unsigned char a1[] = { 0, 1, 2, 3, 4, 5, 6, i, 8 }; + unsigned char a2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; + + return std::lexicographical_compare_three_way(a1, a1+0, a2, a2+0) == 0 + && std::lexicographical_compare_three_way(a1, a1+9, a2, a2+9) == (i <=> 7) + && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+7) == 0 + && std::lexicographical_compare_three_way(a1, a1+8, a2, a2+7) > 0 + && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+8) < 0; +} + +static_assert( test02(248) ); +static_assert( test02(7) ); +static_assert( test02(8) ); + +constexpr bool +test03(unsigned char* p) +{ + unsigned char a[2] = { 1, 2 }; + return std::lexicographical_compare_three_way(p, p, a, a+2) < 0 + && std::lexicographical_compare_three_way(a, a+2, p, p) > 0; +} + +static_assert( test03(nullptr) ); // ensure memcmp not called with nullptr