[gcc/devel/c++-modules] libstdc++: Fix bogus use of memcmp in ranges::lexicographical_compare (PR 93972)

Nathan Sidwell nathan@gcc.gnu.org
Tue Mar 10 13:02:20 GMT 2020


https://gcc.gnu.org/g:ce33801fe4c2272b31c64288b34c67a61529ce37

commit ce33801fe4c2272b31c64288b34c67a61529ce37
Author: Patrick Palka <ppalka@redhat.com>
Date:   Fri Feb 28 14:16:06 2020 -0500

    libstdc++: Fix bogus use of memcmp in ranges::lexicographical_compare (PR 93972)
    
    We were enabling the memcmp optimization in ranges::lexicographical_compare for
    signed integral types and for integral types wider 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.

Diff:
---
 libstdc++-v3/ChangeLog                             |   6 +
 libstdc++-v3/include/bits/ranges_algo.h            |   8 +-
 .../25_algorithms/lexicographical_compare/93972.cc | 169 +++++++++++++++++++++
 3 files changed, 181 insertions(+), 2 deletions(-)

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 6484e499b96..efbe1dafdf5 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,11 @@
 2020-02-28  Patrick Palka  <ppalka@redhat.com>
 
+	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.
+
 	* testsuite/26_numerics/headers/numeric/synopsis.cc: Add signatures for
 	functions introduced in C++11, C++17 and C++2a.  Add 'constexpr' to
 	existing signatures for C++2a.
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();
+}


More information about the Libstdc++-cvs mailing list