[PATCH] libstdc++/71545 fix debug checks in binary search algorithms

Jonathan Wakely jwakely@redhat.com
Fri Jun 17 18:28:00 GMT 2016


	PR libstdc++/71545
	* include/bits/stl_algobase.h (lower_bound, lexicographical_compare):
	Remove irreflexive checks.
	* include/bits/stl_algo.h (lower_bound, upper_bound, equal_range,
	binary_search): Likewise.
	* testsuite/25_algorithms/equal_range/partitioned.cc: New test.
	* testsuite/25_algorithms/lexicographical_compare/71545.cc: New test.
	* testsuite/25_algorithms/lower_bound/partitioned.cc: New test.
	* testsuite/25_algorithms/upper_bound/partitioned.cc: New test.
	* testsuite/util/testsuite_iterators.h (__gnu_test::test_container):
	Add constructor from array.

The binary search algos and lexicographical_compare do not require the
comparison function to be irreflexive, so the recently-added debug
mode checks need to be removed.

Tested x86_64-linux, committed to trunk. gcc-6-branch commit to
follow.
-------------- next part --------------
commit e775b35ff6cb0b6843ec2f1c8bf3a136deb898dd
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Jun 17 11:09:18 2016 +0100

    libstdc++/71545 fix debug checks in binary search algorithms
    
    	PR libstdc++/71545
    	* include/bits/stl_algobase.h (lower_bound, lexicographical_compare):
    	Remove irreflexive checks.
    	* include/bits/stl_algo.h (lower_bound, upper_bound, equal_range,
    	binary_search): Likewise.
    	* testsuite/25_algorithms/equal_range/partitioned.cc: New test.
    	* testsuite/25_algorithms/lexicographical_compare/71545.cc: New test.
    	* testsuite/25_algorithms/lower_bound/partitioned.cc: New test.
    	* testsuite/25_algorithms/upper_bound/partitioned.cc: New test.
    	* testsuite/util/testsuite_iterators.h (__gnu_test::test_container):
    	Add constructor from array.

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index fbd03a7..c2ac031 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2026,7 +2026,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_requires_partitioned_lower_pred(__first, __last,
 						__val, __comp);
-      __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
 
       return std::__lower_bound(__first, __last, __val,
 				__gnu_cxx::__ops::__iter_comp_val(__comp));
@@ -2080,7 +2079,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanOpConcept<
 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_partitioned_upper(__first, __last, __val);
-      __glibcxx_requires_irreflexive2(__first, __last);
 
       return std::__upper_bound(__first, __last, __val,
 				__gnu_cxx::__ops::__val_less_iter());
@@ -2112,7 +2110,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
-      __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
 
       return std::__upper_bound(__first, __last, __val,
 				__gnu_cxx::__ops::__val_comp_iter(__comp));
@@ -2186,7 +2183,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_partitioned_lower(__first, __last, __val);
       __glibcxx_requires_partitioned_upper(__first, __last, __val);
-      __glibcxx_requires_irreflexive2(__first, __last);
 
       return std::__equal_range(__first, __last, __val,
 				__gnu_cxx::__ops::__iter_less_val(),
@@ -2225,7 +2221,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 						__val, __comp);
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
-      __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
 
       return std::__equal_range(__first, __last, __val,
 				__gnu_cxx::__ops::__iter_comp_val(__comp),
@@ -2255,7 +2250,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_partitioned_lower(__first, __last, __val);
       __glibcxx_requires_partitioned_upper(__first, __last, __val);
-      __glibcxx_requires_irreflexive2(__first, __last);
 
       _ForwardIterator __i
 	= std::__lower_bound(__first, __last, __val,
@@ -2291,7 +2285,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 						__val, __comp);
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
-      __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
 
       _ForwardIterator __i
 	= std::__lower_bound(__first, __last, __val,
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index d95ea51..210b173 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -989,7 +989,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanOpConcept<
 	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_requires_partitioned_lower(__first, __last, __val);
-      __glibcxx_requires_irreflexive2(__first, __last);
 
       return std::__lower_bound(__first, __last, __val,
 				__gnu_cxx::__ops::__iter_less_val());
@@ -1214,9 +1213,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
       __glibcxx_requires_valid_range(__first1, __last1);
-      __glibcxx_requires_irreflexive2(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
-      __glibcxx_requires_irreflexive2(__first2, __last2);
 
       return std::__lexicographical_compare_aux(std::__niter_base(__first1),
 						std::__niter_base(__last1),
@@ -1246,9 +1243,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
       __glibcxx_requires_valid_range(__first1, __last1);
-      __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
       __glibcxx_requires_valid_range(__first2, __last2);
-      __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
 
       return std::__lexicographical_compare_impl
 	(__first1, __last1, __first2, __last2,
diff --git a/libstdc++-v3/testsuite/25_algorithms/binary_search/partitioned.cc b/libstdc++-v3/testsuite/25_algorithms/binary_search/partitioned.cc
new file mode 100644
index 0000000..63a6cad
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/binary_search/partitioned.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2016 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++11 -D_GLIBCXX_DEBUG" }
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+struct X
+{
+  int val;
+
+  bool odd() const { return val % 2; }
+
+  // Partitioned so that all odd values come before even values:
+  bool operator<(const X& x) const { return this->odd() && !x.odd(); }
+};
+
+void
+test01()
+{
+  bool test __attribute((unused)) = true;
+
+  // Test with range that is partitioned, but not sorted.
+  X seq[] = { 1, 3, 5, 7, 1, 6, 4 };
+  test_container<X, forward_iterator_wrapper> c(seq);
+
+  auto b1 = std::binary_search(c.begin(), c.end(), X{2});
+  VERIFY( b1 );
+  auto b2 = std::binary_search(c.begin(), c.end(), X{2}, std::less<X>{});
+  VERIFY( b2 );
+
+  auto b3 = std::binary_search(c.begin(), c.end(), X{9});
+  VERIFY( b3 );
+  auto b4 = std::binary_search(c.begin(), c.end(), X{9}, std::less<X>{});
+  VERIFY( b4 );
+
+  auto b5 = std::binary_search(seq, seq+5, X{2});
+  VERIFY( !b5 );
+  auto b6 = std::binary_search(seq, seq+5, X{2}, std::less<X>{});
+  VERIFY( !b6 );
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal_range/partitioned.cc b/libstdc++-v3/testsuite/25_algorithms/equal_range/partitioned.cc
new file mode 100644
index 0000000..d3a43d0
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal_range/partitioned.cc
@@ -0,0 +1,66 @@
+// Copyright (C) 2016 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++11 -D_GLIBCXX_DEBUG" }
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+struct X
+{
+  int val;
+
+  bool odd() const { return val % 2; }
+
+  // Partitioned so that all odd values come before even values:
+  bool operator<(const X& x) const { return this->odd() && !x.odd(); }
+};
+
+void
+test01()
+{
+  bool test __attribute((unused)) = true;
+
+  // Test with range that is partitioned, but not sorted.
+  X seq[] = { 1, 3, 5, 7, 1, 6, 4, 2 };
+  test_container<X, forward_iterator_wrapper> c(seq);
+
+  auto part1 = std::equal_range(c.begin(), c.end(), X{2});
+  VERIFY( part1.first != c.end() && part1.second == c.end() );
+  VERIFY( part1.first->val == 6 );
+  auto part2 = std::equal_range(c.begin(), c.end(), X{2}, std::less<X>{});
+  VERIFY( part2.first != c.end() && part1.second == c.end() );
+  VERIFY( part2.first->val == 6 );
+
+  auto part3 = std::equal_range(c.begin(), c.end(), X{9});
+  VERIFY( part3.first == c.begin() && part3.second != c.end() );
+  VERIFY( part3.second->val == 6 );
+  auto part4 = std::equal_range(c.begin(), c.end(), X{9}, std::less<X>{});
+  VERIFY( part4.first == c.begin() && part4.second != c.end() );
+  VERIFY( part4.second->val == 6 );
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/71545.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/71545.cc
new file mode 100644
index 0000000..6c9cd12
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/71545.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2016 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++11 -D_GLIBCXX_DEBUG" }
+// { dg-do link }
+
+#include <algorithm>
+
+struct X { };
+
+bool operator<(X, int) { return true; }
+bool operator<(int, X) { return false; }
+
+bool operator<(X, X); // undefined (PR libstdc++/71545)
+
+int main()
+{
+  X x[1];
+  int i[1];
+  std::lexicographical_compare(x, x+1, i, i+1);
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lower_bound/partitioned.cc b/libstdc++-v3/testsuite/25_algorithms/lower_bound/partitioned.cc
new file mode 100644
index 0000000..bba0b66
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lower_bound/partitioned.cc
@@ -0,0 +1,100 @@
+// Copyright (C) 2016 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++11 -D_GLIBCXX_DEBUG" }
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+struct X
+{
+  int val;
+
+  bool odd() const { return val % 2; }
+
+  // Partitioned so that all odd values come before even values:
+  bool operator<(const X& x) const { return this->odd() && !x.odd(); }
+};
+
+void
+test01()
+{
+  bool test __attribute((unused)) = true;
+
+  // Test with range that is partitioned, but not sorted.
+  X seq[] = { 1, 3, 5, 7, 1, 6, 4, 2 };
+  test_container<X, forward_iterator_wrapper> c(seq);
+
+  auto part1 = std::lower_bound(c.begin(), c.end(), X{2});
+  VERIFY( part1 != c.end() );
+  VERIFY( part1->val == 6 );
+  auto part2 = std::lower_bound(c.begin(), c.end(), X{2}, std::less<X>{});
+  VERIFY( part2 != c.end() );
+  VERIFY( part2->val == 6 );
+
+  auto part3 = std::lower_bound(c.begin(), c.end(), X{9});
+  VERIFY( part3 != c.end() );
+  VERIFY( part3->val == 1 );
+  auto part4 = std::lower_bound(c.begin(), c.end(), X{9}, std::less<X>{});
+  VERIFY( part4 != c.end() );
+  VERIFY( part4->val == 1 );
+}
+
+struct Y
+{
+  double val;
+
+  // Not irreflexive, so not a strict weak order.
+  bool operator<(const Y& y) const { return val < int(y.val); }
+};
+
+void
+test02()
+{
+  bool test __attribute((unused)) = true;
+
+  // Test that Debug Mode checks don't fire (libstdc++/71545)
+
+  Y seq[] = { -0.1, 1.2, 5.0, 5.2, 5.1, 5.9, 5.5, 6.0 };
+  test_container<Y, forward_iterator_wrapper> c(seq);
+
+  auto part1 = std::lower_bound(c.begin(), c.end(), Y{5.5});
+  VERIFY( part1 != c.end() );
+  VERIFY( part1->val == 5.0 );
+  auto part2 = std::lower_bound(c.begin(), c.end(), Y{5.5}, std::less<Y>{});
+  VERIFY( part2 != c.end() );
+  VERIFY( part2->val == 5.0 );
+
+  auto part3 = std::lower_bound(c.begin(), c.end(), Y{1.0});
+  VERIFY( part3 != c.end() );
+  VERIFY( part3->val == 1.2 );
+  auto part4 = std::lower_bound(c.begin(), c.end(), Y{1.0}, std::less<Y>{});
+  VERIFY( part4 != c.end() );
+  VERIFY( part4->val == 1.2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/upper_bound/partitioned.cc b/libstdc++-v3/testsuite/25_algorithms/upper_bound/partitioned.cc
new file mode 100644
index 0000000..96cfb2e
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/upper_bound/partitioned.cc
@@ -0,0 +1,98 @@
+// Copyright (C) 2016 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++11 -D_GLIBCXX_DEBUG" }
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+struct X
+{
+  int val;
+
+  bool odd() const { return val % 2; }
+
+  // Partitioned so that all odd values come before even values:
+  bool operator<(const X& x) const { return this->odd() && !x.odd(); }
+};
+
+void
+test01()
+{
+  bool test __attribute((unused)) = true;
+
+  // Test with range that is partitioned, but not sorted.
+  X seq[] = { 1, 3, 5, 7, 1, 6, 4, 2 };
+  test_container<X, forward_iterator_wrapper> c(seq);
+
+  auto part1 = std::upper_bound(c.begin(), c.end(), X{2});
+  VERIFY( part1 == c.end() );
+  auto part2 = std::upper_bound(c.begin(), c.end(), X{2}, std::less<X>{});
+  VERIFY( part2 == c.end() );
+
+  auto part3 = std::upper_bound(c.begin(), c.end(), X{9});
+  VERIFY( part3 != c.end() );
+  VERIFY( part3->val == 6 );
+  auto part4 = std::upper_bound(c.begin(), c.end(), X{9}, std::less<X>{});
+  VERIFY( part3 != c.end() );
+  VERIFY( part4->val == 6 );
+}
+
+struct Y
+{
+  double val;
+
+  // Not irreflexive, so not a strict weak order.
+  bool operator<(const Y& y) const { return val < (int)y.val; }
+};
+
+void
+test02()
+{
+  bool test __attribute((unused)) = true;
+
+  // Test that Debug Mode checks don't fire (libstdc++/71545)
+
+  Y seq[] = { -0.1, 1.2, 5.0, 5.2, 5.1, 5.9, 5.5, 6.0 };
+  test_container<Y, forward_iterator_wrapper> c(seq);
+
+  auto part1 = std::upper_bound(c.begin(), c.end(), Y{5.5});
+  VERIFY( part1 != c.end() );
+  VERIFY( part1->val == 6.0 );
+  auto part2 = std::upper_bound(c.begin(), c.end(), Y{5.5}, std::less<Y>{});
+  VERIFY( part2 != c.end() );
+  VERIFY( part2->val == 6.0 );
+
+  auto part3 = std::upper_bound(c.begin(), c.end(), Y{1.0});
+  VERIFY( part3 != c.end() );
+  VERIFY( part3->val == 5.0 );
+  auto part4 = std::upper_bound(c.begin(), c.end(), Y{1.0}, std::less<Y>{});
+  VERIFY( part4 != c.end() );
+  VERIFY( part4->val == 5.0 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h b/libstdc++-v3/testsuite/util/testsuite_iterators.h
index a1c71a2..53c9b3d 100644
--- a/libstdc++-v3/testsuite/util/testsuite_iterators.h
+++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h
@@ -542,6 +542,13 @@ namespace __gnu_test
     test_container(T* _first, T* _last):bounds(_first, _last)
     { }
 
+#if __cplusplus >= 201103L
+      template<std::size_t N>
+	explicit
+	test_container(T (&arr)[N]) : test_container(arr, arr+N)
+	{ }
+#endif
+
     ItType<T>
     it(int pos)
     {


More information about the Gcc-patches mailing list