diff mbox series

libstdc++: Fix bogus use of memcmp in ranges::lexicographical_compare (PR 93972)

Message ID 20200228195901.1918627-1-ppalka@redhat.com
State New
Headers show
Series libstdc++: Fix bogus use of memcmp in ranges::lexicographical_compare (PR 93972) | expand

Commit Message

Patrick Palka Feb. 28, 2020, 7:59 p.m. UTC 
We were enabling the memcmp optimization in ranges::lexicographical_compare for
signed integral types and for integral types larger than a byte.  But memcmp
gives the wrong answer for arrays of such types.  This patch fixes this issue by
refining the condition that enables the memcmp optimization.  It's now
consistent with the corresponding condition used in
std::lexicographical_compare.

libstdc++-v3/ChangeLog:

	PR libstdc++/93972
	* include/bits/ranges_algo.h (__lexicographical_compare_fn::operator()):
	Fix condition for when to use memcmp, making it consistent with the
	corresponding condition used in std::lexicographical_compare.
	* testsuite/25_algorithms/lexicographical_compare/93972.cc: New test.
---
 libstdc++-v3/include/bits/ranges_algo.h       |   8 +-
 .../lexicographical_compare/93972.cc          | 169 ++++++++++++++++++
 2 files changed, 175 insertions(+), 2 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc

Comments

Jonathan Wakely Feb. 28, 2020, 9:53 p.m. UTC | #1 
On 28/02/20 14:59 -0500, Patrick Palka wrote:
>We were enabling the memcmp optimization in ranges::lexicographical_compare for
>signed integral types and for integral types larger than a byte.  But memcmp
>gives the wrong answer for arrays of such types.  This patch fixes this issue by
>refining the condition that enables the memcmp optimization.  It's now
>consistent with the corresponding condition used in
>std::lexicographical_compare.
>
>libstdc++-v3/ChangeLog:
>
>	PR libstdc++/93972
>	* include/bits/ranges_algo.h (__lexicographical_compare_fn::operator()):
>	Fix condition for when to use memcmp, making it consistent with the
>	corresponding condition used in std::lexicographical_compare.
>	* testsuite/25_algorithms/lexicographical_compare/93972.cc: New test.
>---
> libstdc++-v3/include/bits/ranges_algo.h       |   8 +-
> .../lexicographical_compare/93972.cc          | 169 ++++++++++++++++++
> 2 files changed, 175 insertions(+), 2 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc
>
>diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
>index 05c0851d411..8fa4a8a9161 100644
>--- a/libstdc++-v3/include/bits/ranges_algo.h
>+++ b/libstdc++-v3/include/bits/ranges_algo.h
>@@ -3466,9 +3466,13 @@ namespace ranges
> 	      {
> 		using _ValueType1 = iter_value_t<_Iter1>;
> 		using _ValueType2 = iter_value_t<_Iter2>;
>+		// This condition is consistent with the one in
>+		// __lexicographical_compare_aux in <bits/stl_algobase.h>.
> 		constexpr bool __use_memcmp
>-		  = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
>-		     && is_same_v<_ValueType1, _ValueType2>
>+		  = (__is_byte<_ValueType1>::__value
>+		     && __is_byte<_ValueType2>::__value
>+		     && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
>+		     && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed

I think this could be:

                      && !is_signed_v<_ValueType1>
                      && !is_signed_v<_ValueType2>

because this code doesn't need to be valid for C++98. But on the other
hand, there's value in being consistent with the condition in
std::lexicographical_compare.

OK for master, thanks for the quick fix.
Christophe Lyon March 2, 2020, 12:22 p.m. UTC | #2 
On Fri, 28 Feb 2020 at 22:53, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> On 28/02/20 14:59 -0500, Patrick Palka wrote:
> >We were enabling the memcmp optimization in ranges::lexicographical_compare for
> >signed integral types and for integral types larger than a byte.  But memcmp
> >gives the wrong answer for arrays of such types.  This patch fixes this issue by
> >refining the condition that enables the memcmp optimization.  It's now
> >consistent with the corresponding condition used in
> >std::lexicographical_compare.
> >
> >libstdc++-v3/ChangeLog:
> >
> >       PR libstdc++/93972
> >       * include/bits/ranges_algo.h (__lexicographical_compare_fn::operator()):
> >       Fix condition for when to use memcmp, making it consistent with the
> >       corresponding condition used in std::lexicographical_compare.
> >       * testsuite/25_algorithms/lexicographical_compare/93972.cc: New test.


Hi,

The new test fails on aarch64 and arm, and other targets according to
gcc-testresults.
On aarch64, my log says:
FAIL: 25_algorithms/lexicographical_compare/93972.cc (test for excess errors)
Excess errors:
/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
error: no matching function for call to '__memcmp(char*&, unsigned
char*&, const long int&)'
/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
error: no matching function for call to '__memcmp(char*&, unsigned
char*&, const long int&)'
/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
error: no matching function for call to '__memcmp(unsigned char*&,
char*&, const long int&)'
/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
error: no matching function for call to '__memcmp(unsigned char*&,
char*&, const long int&)'

UNRESOLVED: 25_algorithms/lexicographical_compare/93972.cc compilation
failed to produce executable

Christophe

> >---
> > libstdc++-v3/include/bits/ranges_algo.h       |   8 +-
> > .../lexicographical_compare/93972.cc          | 169 ++++++++++++++++++
> > 2 files changed, 175 insertions(+), 2 deletions(-)
> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc
> >
> >diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> >index 05c0851d411..8fa4a8a9161 100644
> >--- a/libstdc++-v3/include/bits/ranges_algo.h
> >+++ b/libstdc++-v3/include/bits/ranges_algo.h
> >@@ -3466,9 +3466,13 @@ namespace ranges
> >             {
> >               using _ValueType1 = iter_value_t<_Iter1>;
> >               using _ValueType2 = iter_value_t<_Iter2>;
> >+              // This condition is consistent with the one in
> >+              // __lexicographical_compare_aux in <bits/stl_algobase.h>.
> >               constexpr bool __use_memcmp
> >-                = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
> >-                   && is_same_v<_ValueType1, _ValueType2>
> >+                = (__is_byte<_ValueType1>::__value
> >+                   && __is_byte<_ValueType2>::__value
> >+                   && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
> >+                   && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
>
> I think this could be:
>
>                       && !is_signed_v<_ValueType1>
>                       && !is_signed_v<_ValueType2>
>
> because this code doesn't need to be valid for C++98. But on the other
> hand, there's value in being consistent with the condition in
> std::lexicographical_compare.
>
> OK for master, thanks for the quick fix.
>
Jonathan Wakely March 2, 2020, 1:12 p.m. UTC | #3 
On 02/03/20 13:22 +0100, Christophe Lyon wrote:
>On Fri, 28 Feb 2020 at 22:53, Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>> On 28/02/20 14:59 -0500, Patrick Palka wrote:
>> >We were enabling the memcmp optimization in ranges::lexicographical_compare for
>> >signed integral types and for integral types larger than a byte.  But memcmp
>> >gives the wrong answer for arrays of such types.  This patch fixes this issue by
>> >refining the condition that enables the memcmp optimization.  It's now
>> >consistent with the corresponding condition used in
>> >std::lexicographical_compare.
>> >
>> >libstdc++-v3/ChangeLog:
>> >
>> >       PR libstdc++/93972
>> >       * include/bits/ranges_algo.h (__lexicographical_compare_fn::operator()):
>> >       Fix condition for when to use memcmp, making it consistent with the
>> >       corresponding condition used in std::lexicographical_compare.
>> >       * testsuite/25_algorithms/lexicographical_compare/93972.cc: New test.
>
>
>Hi,
>
>The new test fails on aarch64 and arm, and other targets according to
>gcc-testresults.
>On aarch64, my log says:
>FAIL: 25_algorithms/lexicographical_compare/93972.cc (test for excess errors)
>Excess errors:
>/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
>error: no matching function for call to '__memcmp(char*&, unsigned
>char*&, const long int&)'
>/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
>error: no matching function for call to '__memcmp(char*&, unsigned
>char*&, const long int&)'
>/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
>error: no matching function for call to '__memcmp(unsigned char*&,
>char*&, const long int&)'
>/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
>error: no matching function for call to '__memcmp(unsigned char*&,
>char*&, const long int&)'
>
>UNRESOLVED: 25_algorithms/lexicographical_compare/93972.cc compilation
>failed to produce executable


Hmm, I think this was already broken in std::lexicographical_compare,
we just didn't have a test for it. I think the following will also
fail to compile on aarch64 and ARM (and any target where char is
unsigned):

#include <algorithm>
#include <assert.h>

int main()
{
   unsigned char a[] = {1, 2, 3, 4};
   char b[] = {1, 2, 3, 5};

   assert( std::lexicographical_compare(a, a+4, b, b+4) );
}

So Patrick's ranges::lexicographical_compare didn't introduce the bug,
it just found it by having better tests.

The std::__memcmp function is broken in a similar way to the
std::__memmove function that I removed last week. I'll fix that
today...
Jonathan Wakely March 2, 2020, 5:12 p.m. UTC | #4 
On 02/03/20 13:12 +0000, Jonathan Wakely wrote:
>On 02/03/20 13:22 +0100, Christophe Lyon wrote:
>>On Fri, 28 Feb 2020 at 22:53, Jonathan Wakely <jwakely@redhat.com> wrote:
>>>
>>>On 28/02/20 14:59 -0500, Patrick Palka wrote:
>>>>We were enabling the memcmp optimization in ranges::lexicographical_compare for
>>>>signed integral types and for integral types larger than a byte.  But memcmp
>>>>gives the wrong answer for arrays of such types.  This patch fixes this issue by
>>>>refining the condition that enables the memcmp optimization.  It's now
>>>>consistent with the corresponding condition used in
>>>>std::lexicographical_compare.
>>>>
>>>>libstdc++-v3/ChangeLog:
>>>>
>>>>       PR libstdc++/93972
>>>>       * include/bits/ranges_algo.h (__lexicographical_compare_fn::operator()):
>>>>       Fix condition for when to use memcmp, making it consistent with the
>>>>       corresponding condition used in std::lexicographical_compare.
>>>>       * testsuite/25_algorithms/lexicographical_compare/93972.cc: New test.
>>
>>
>>Hi,
>>
>>The new test fails on aarch64 and arm, and other targets according to
>>gcc-testresults.
>>On aarch64, my log says:
>>FAIL: 25_algorithms/lexicographical_compare/93972.cc (test for excess errors)
>>Excess errors:
>>/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
>>error: no matching function for call to '__memcmp(char*&, unsigned
>>char*&, const long int&)'
>>/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
>>error: no matching function for call to '__memcmp(char*&, unsigned
>>char*&, const long int&)'
>>/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
>>error: no matching function for call to '__memcmp(unsigned char*&,
>>char*&, const long int&)'
>>/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/ranges_algo.h:3490:
>>error: no matching function for call to '__memcmp(unsigned char*&,
>>char*&, const long int&)'
>>
>>UNRESOLVED: 25_algorithms/lexicographical_compare/93972.cc compilation
>>failed to produce executable
>
>
>Hmm, I think this was already broken in std::lexicographical_compare,
>we just didn't have a test for it. I think the following will also
>fail to compile on aarch64 and ARM (and any target where char is
>unsigned):
>
>#include <algorithm>
>#include <assert.h>
>
>int main()
>{
>  unsigned char a[] = {1, 2, 3, 4};
>  char b[] = {1, 2, 3, 5};
>
>  assert( std::lexicographical_compare(a, a+4, b, b+4) );
>}
>
>So Patrick's ranges::lexicographical_compare didn't introduce the bug,
>it just found it by having better tests.
>
>The std::__memcmp function is broken in a similar way to the
>std::__memmove function that I removed last week. I'll fix that
>today...

Fixed with this patch, tested powerpc64le-linux and committed to
master.

Thanks for noticing the new FAIL.
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 05c0851d411..8fa4a8a9161 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3466,9 +3466,13 @@  namespace ranges
 	      {
 		using _ValueType1 = iter_value_t<_Iter1>;
 		using _ValueType2 = iter_value_t<_Iter2>;
+		// This condition is consistent with the one in
+		// __lexicographical_compare_aux in <bits/stl_algobase.h>.
 		constexpr bool __use_memcmp
-		  = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
-		     && is_same_v<_ValueType1, _ValueType2>
+		  = (__is_byte<_ValueType1>::__value
+		     && __is_byte<_ValueType2>::__value
+		     && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
+		     && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
 		     && is_pointer_v<_Iter1>
 		     && is_pointer_v<_Iter2>
 		     && (is_same_v<_Comp, ranges::less>
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc
new file mode 100644
index 00000000000..53c4e0daddc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc
@@ -0,0 +1,169 @@ 
+// 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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using std::signed_integral;
+
+namespace ranges = std::ranges;
+
+template<signed_integral T>
+void
+test01()
+{
+  T i[] = { -1 };
+  T j[] = { 1 };
+
+  VERIFY( ranges::lexicographical_compare(i, j) );
+  VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( !ranges::lexicographical_compare(j, i) );
+  VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+template<signed_integral T>
+void
+test02()
+{
+  T i[] = { -5 };
+  T j[] = { -5, 3 };
+
+  VERIFY( ranges::lexicographical_compare(i, j) );
+  VERIFY( ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( !ranges::lexicographical_compare(j, i) );
+  VERIFY( !ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+template<signed_integral T>
+void
+test03()
+{
+  T i[] = { -10 };
+  T j[] = { -5, 3 };
+
+  VERIFY( ranges::lexicographical_compare(i, j) );
+  VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( !ranges::lexicographical_compare(j, i) );
+  VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+template<signed_integral T>
+void
+test04()
+{
+  T i[] = { -2 };
+  T j[] = { -5, 3 };
+
+  VERIFY( !ranges::lexicographical_compare(i, j) );
+  VERIFY( ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( ranges::lexicographical_compare(j, i) );
+  VERIFY( !ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+void
+test05()
+{
+  unsigned i[] = { 1 };
+  unsigned j[] = { 256 };
+
+  VERIFY( ranges::lexicographical_compare(i, j) );
+  VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( !ranges::lexicographical_compare(j, i) );
+  VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+void
+test06()
+{
+  signed char i[] = { 100, 1 };
+  unsigned char j[] = { 100 };
+
+  VERIFY( !ranges::lexicographical_compare(i, j) );
+  VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( ranges::lexicographical_compare(j, i) );
+  VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+void
+test07()
+{
+  char i[] = { 95, 1 };
+  unsigned char j[] = { 100 };
+
+  VERIFY( ranges::lexicographical_compare(i, j) );
+  VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( !ranges::lexicographical_compare(j, i) );
+  VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+void
+test08()
+{
+  signed char i[] = { 112, 1 };
+  signed char j[] = { 87 };
+
+  VERIFY( !ranges::lexicographical_compare(i, j) );
+  VERIFY( ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( ranges::lexicographical_compare(j, i) );
+  VERIFY( !ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+void
+test09()
+{
+  char i[] = { 1 };
+  unsigned char j[] = { 100 };
+
+  VERIFY( ranges::lexicographical_compare(i, j) );
+  VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) );
+
+  VERIFY( !ranges::lexicographical_compare(j, i) );
+  VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) );
+}
+
+int
+main()
+{
+  test01<signed char>();
+  test01<int>();
+
+  test02<signed char>();
+  test02<int>();
+
+  test03<signed char>();
+  test03<int>();
+
+  test04<signed char>();
+  test04<int>();
+
+  test05();
+  test06();
+  test07();
+  test08();
+  test09();
+}