From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2181) id 8EBAA393C851; Wed, 2 Sep 2020 14:50:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8EBAA393C851 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1599058259; bh=3HlSG0Z5xEn6kqB5lqMKJ8BP5TrOYgQ8pvY3Wsgra0k=; h=From:To:Subject:Date:From; b=tB5ZfB+ceUPdZM7J1zvWk+st2uEB23ATLlkJs3T0SZF3LQbC90R1t568h7NtID+K+ R4fMCQ2tokhJufmfO8agK9rqUFhWEkCQzB4hIjRfTiSnnAfU4QqZmdgoIZ3qkub73V PrFG4hUMzI3iYS6sBjcTgCV0G14KbZB1e9+8pupQ= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Jonathan Wakely To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r11-2981] libstdc++: Fix three-way comparison for std::array [PR 96851] X-Act-Checkin: gcc X-Git-Author: Jonathan Wakely X-Git-Refname: refs/heads/master X-Git-Oldrev: d45a6c7099a346153e970476688be5bd6a016cef X-Git-Newrev: 2f983fa69005b603ea1758a013b4134d5b0f24a8 Message-Id: <20200902145059.8EBAA393C851@sourceware.org> Date: Wed, 2 Sep 2020 14:50:59 +0000 (GMT) X-BeenThere: libstdc++-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 02 Sep 2020 14:50:59 -0000 https://gcc.gnu.org/g:2f983fa69005b603ea1758a013b4134d5b0f24a8 commit r11-2981-g2f983fa69005b603ea1758a013b4134d5b0f24a8 Author: Jonathan Wakely Date: Wed Sep 2 15:17:24 2020 +0100 libstdc++: Fix three-way comparison for std::array [PR 96851] The spaceship operator for std::array uses memcmp when the __is_byte trait is true, but memcmp isn't usable in constexpr contexts. Also, memcmp should only be used for unsigned byte types, because it gives the wrong answer for signed chars with negative values. We can simply check std::is_constant_evaluated() so that we don't use memcmp during constant evaluation. To fix the problem of using memcmp for inappropriate types, this patch adds new __is_memcmp_ordered and __is_memcmp_ordered_with traits. These say whether using memcmp will give the right answer for ordering operations such as lexicographical_compare and three-way comparisons. The new traits can be used in several places, and can also be used to implement my suggestion in PR 93059 comment 37 to use memcmp for unsigned integers larger than one byte on big endian targets. libstdc++-v3/ChangeLog: PR libstdc++/96851 * include/bits/cpp_type_traits.h (__is_memcmp_ordered): New trait that says if memcmp can be used for ordering. (__is_memcmp_ordered_with): Likewise, for two types. * include/bits/deque.tcc (__lex_cmp_dit): Use new traits instead of __is_byte and __numeric_traits. (__lexicographical_compare_aux1): Likewise. * include/bits/ranges_algo.h (__lexicographical_compare_fn): Likewise. * include/bits/stl_algobase.h (__lexicographical_compare_aux1) (__is_byte_iter): Likewise. * include/std/array (operator<=>): Likewise. Only use memcmp when std::is_constant_evaluated() is false. * testsuite/23_containers/array/comparison_operators/96851.cc: New test. * testsuite/23_containers/array/tuple_interface/get_neg.cc: Adjust dg-error line numbers. Diff: --- libstdc++-v3/include/bits/cpp_type_traits.h | 60 +++++++++++ libstdc++-v3/include/bits/deque.tcc | 8 +- libstdc++-v3/include/bits/ranges_algo.h | 5 +- libstdc++-v3/include/bits/stl_algobase.h | 7 +- libstdc++-v3/include/std/array | 22 ++-- .../array/comparison_operators/96851.cc | 119 +++++++++++++++++++++ .../23_containers/array/tuple_interface/get_neg.cc | 6 +- 7 files changed, 200 insertions(+), 27 deletions(-) diff --git a/libstdc++-v3/include/bits/cpp_type_traits.h b/libstdc++-v3/include/bits/cpp_type_traits.h index 979ad9c2c69..b48d1adc63c 100644 --- a/libstdc++-v3/include/bits/cpp_type_traits.h +++ b/libstdc++-v3/include/bits/cpp_type_traits.h @@ -482,6 +482,66 @@ __INT_N(__GLIBCXX_TYPE_INT_N_3) : __is_nonvolatile_trivially_copyable<_Tp> { }; + // Whether memcmp can be used to determine ordering for a type + // e.g. in std::lexicographical_compare or three-way comparisons. + // True for unsigned integer-like types where comparing each byte in turn + // as an unsigned char yields the right result. This is true for all + // unsigned integers on big endian targets, but only unsigned narrow + // character types (and std::byte) on little endian targets. + template::__value +#else + __is_byte<_Tp>::__value +#endif + > + struct __is_memcmp_ordered + { + static const bool __value = _Tp(-1) > _Tp(1); // is unsigned + }; + + template + struct __is_memcmp_ordered<_Tp, false> + { + static const bool __value = false; + }; + + // Whether two types can be compared using memcmp. + template + struct __is_memcmp_ordered_with + { + static const bool __value = __is_memcmp_ordered<_Tp>::__value + && __is_memcmp_ordered<_Up>::__value; + }; + + template + struct __is_memcmp_ordered_with<_Tp, _Up, false> + { + static const bool __value = false; + }; + +#if __cplusplus >= 201703L +#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ + // std::byte is not an integer, but it can be compared using memcmp. + template<> + struct __is_memcmp_ordered + { static constexpr bool __value = true; }; +#endif + + // std::byte can only be compared to itself, not to other types. + template<> + struct __is_memcmp_ordered_with + { static constexpr bool __value = true; }; + + template + struct __is_memcmp_ordered_with<_Tp, std::byte, _SameSize> + { static constexpr bool __value = false; }; + + template + struct __is_memcmp_ordered_with + { static constexpr bool __value = false; }; +#endif + // // Move iterator type // diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index 7d1ec86456a..651ae70a84b 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -1269,9 +1269,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER const _Tp2* __first2, const _Tp2* __last2) { const bool __simple = - (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value - && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed - && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed + (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value && __is_pointer<_Ptr>::__value #if __cplusplus > 201703L && __cpp_lib_concepts // For C++20 iterator_traits::value_type is non-volatile @@ -1327,9 +1325,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) { const bool __simple = - (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value - && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed - && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed + (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value && __is_pointer<_Ptr1>::__value && __is_pointer<_Ptr2>::__value #if __cplusplus > 201703L && __cpp_lib_concepts diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 94ca7b6488d..a5539650edc 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3475,10 +3475,7 @@ namespace ranges // This condition is consistent with the one in // __lexicographical_compare_aux in . constexpr bool __use_memcmp - = (__is_byte<_ValueType1>::__value - && __is_byte<_ValueType2>::__value - && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed - && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed + = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value && __ptr_to_nonvolatile<_Iter1> && __ptr_to_nonvolatile<_Iter2> && (is_same_v<_Comp, ranges::less> diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index ff5b4505a08..3e9ec32340e 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -1368,9 +1368,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER typedef typename iterator_traits<_II1>::value_type _ValueType1; typedef typename iterator_traits<_II2>::value_type _ValueType2; const bool __simple = - (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value - && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed - && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed + (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value && __is_pointer<_II1>::__value && __is_pointer<_II2>::__value #if __cplusplus > 201703L && __cpp_lib_concepts @@ -1785,8 +1783,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO // or std::byte, suitable for comparison by memcmp. template concept __is_byte_iter = contiguous_iterator<_Iter> - && __is_byte>::__value != 0 - && !__gnu_cxx::__numeric_traits>::__is_signed; + && __is_memcmp_ordered>::__value; // 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. diff --git a/libstdc++-v3/include/std/array b/libstdc++-v3/include/std/array index f7b0dca48b1..3bb6f48c432 100644 --- a/libstdc++-v3/include/std/array +++ b/libstdc++-v3/include/std/array @@ -258,16 +258,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER constexpr __detail::__synth3way_t<_Tp> operator<=>(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b) { - if constexpr (_Nm && __is_byte<_Tp>::__value) - return __builtin_memcmp(__a.data(), __b.data(), _Nm) <=> 0; - else +#ifdef __cpp_lib_is_constant_evaluated + if constexpr (_Nm && __is_memcmp_ordered<_Tp>::__value) + if (!std::is_constant_evaluated()) + { + constexpr size_t __n = _Nm * sizeof(_Tp); + return __builtin_memcmp(__a.data(), __b.data(), __n) <=> 0; + } +#endif + + for (size_t __i = 0; __i < _Nm; ++__i) { - for (size_t __i = 0; __i < _Nm; ++__i) - { - auto __c = __detail::__synth3way(__a[__i], __b[__i]); - if (__c != 0) - return __c; - } + auto __c = __detail::__synth3way(__a[__i], __b[__i]); + if (__c != 0) + return __c; } return strong_ordering::equal; } diff --git a/libstdc++-v3/testsuite/23_containers/array/comparison_operators/96851.cc b/libstdc++-v3/testsuite/23_containers/array/comparison_operators/96851.cc new file mode 100644 index 00000000000..b2a464b8f68 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/array/comparison_operators/96851.cc @@ -0,0 +1,119 @@ +// Copyright (C) 2020 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 +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +template +constexpr auto +cmp_array(T t) +{ + std::array a{ T{1}, t }; + std::array b{ T{1}, T{2} }; + return a <=> b; +} + +void +test01() +{ + static_assert( cmp_array((unsigned char)1) < 0 ); + static_assert( cmp_array((unsigned char)2) == 0 ); + static_assert( cmp_array((unsigned char)3) > 0 ); + + static_assert( cmp_array((signed char)-1) < 0 ); + static_assert( cmp_array((signed char)2) == 0 ); + static_assert( cmp_array((signed char)3) > 0 ); + + static_assert( cmp_array(std::byte{1}) < 0 ); + static_assert( cmp_array(std::byte{2}) == 0 ); + static_assert( cmp_array(std::byte{3}) > 0 ); + + static_assert( cmp_array((unsigned int)1) < 0 ); + static_assert( cmp_array((unsigned int)2) == 0 ); + static_assert( cmp_array((unsigned int)333) > 0 ); + static_assert( cmp_array((unsigned int)4444) > 0 ); + static_assert( cmp_array((unsigned int)55555) > 0 ); + static_assert( cmp_array((unsigned int)0x66666666) > 0 ); + + static_assert( cmp_array((signed int)-1) < 0 ); + static_assert( cmp_array((signed int)2) == 0 ); + static_assert( cmp_array((signed int)333) > 0 ); + static_assert( cmp_array((signed int)-4444) < 0 ); + static_assert( cmp_array((signed int)55555) > 0 ); + static_assert( cmp_array((signed int)-0x66666666) < 0 ); +} + +void +test02() +{ + unsigned char uc = 1; + VERIFY( cmp_array(uc) < 0 ); + uc = 2; + VERIFY( cmp_array(uc) == 0 ); + uc = 3; + VERIFY( cmp_array(uc) > 0 ); + + signed char sc = -1; + VERIFY( cmp_array(sc) < 0 ); + sc = 2; + VERIFY( cmp_array(sc) == 0 ); + sc = 3; + VERIFY( cmp_array(sc) > 0 ); + + std::byte b{1}; + VERIFY( cmp_array(b) < 0 ); + b = std::byte{2}; + VERIFY( cmp_array(b) == 0 ); + b = std::byte{3}; + VERIFY( cmp_array(b) > 0 ); + + unsigned int ui = 1; + VERIFY( cmp_array(ui) < 0 ); + ui = 2; + VERIFY( cmp_array(ui) == 0 ); + ui = 333; + VERIFY( cmp_array(ui) > 0 ); + ui = 4444; + VERIFY( cmp_array(ui) > 0 ); + ui = 555555; + VERIFY( cmp_array(ui) > 0 ); + ui = 0x66666666; + VERIFY( cmp_array(ui) > 0 ); + + signed int si = -1; + VERIFY( cmp_array(si) < 0 ); + si = 2; + VERIFY( cmp_array(si) == 0 ); + si = 333; + VERIFY( cmp_array(si) > 0 ); + si = -4444; + VERIFY( cmp_array(si) < 0 ); + si = 555555; + VERIFY( cmp_array(si) > 0 ); + si = -0x66666666; + VERIFY( cmp_array(si) < 0 ); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/23_containers/array/tuple_interface/get_neg.cc b/libstdc++-v3/testsuite/23_containers/array/tuple_interface/get_neg.cc index 6072d070f64..a2640318617 100644 --- a/libstdc++-v3/testsuite/23_containers/array/tuple_interface/get_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/array/tuple_interface/get_neg.cc @@ -27,6 +27,6 @@ int n1 = std::get<1>(a); int n2 = std::get<1>(std::move(a)); int n3 = std::get<1>(ca); -// { dg-error "static assertion failed" "" { target *-*-* } 336 } -// { dg-error "static assertion failed" "" { target *-*-* } 345 } -// { dg-error "static assertion failed" "" { target *-*-* } 353 } +// { dg-error "static assertion failed" "" { target *-*-* } 340 } +// { dg-error "static assertion failed" "" { target *-*-* } 349 } +// { dg-error "static assertion failed" "" { target *-*-* } 357 }