From 3ebacabd0ec9e8460212c5d4f57dc1d733445915 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Fri, 17 Jun 2016 19:28:34 +0100 Subject: [PATCH] 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. From-SVN: r237560 --- libstdc++-v3/ChangeLog | 14 +++ libstdc++-v3/include/bits/stl_algo.h | 7 -- libstdc++-v3/include/bits/stl_algobase.h | 5 - .../binary_search/partitioned.cc | 67 ++++++++++++ .../25_algorithms/equal_range/partitioned.cc | 66 ++++++++++++ .../lexicographical_compare/71545.cc | 35 ++++++ .../25_algorithms/lower_bound/partitioned.cc | 100 ++++++++++++++++++ .../25_algorithms/upper_bound/partitioned.cc | 98 +++++++++++++++++ .../testsuite/util/testsuite_iterators.h | 7 ++ 9 files changed, 387 insertions(+), 12 deletions(-) create mode 100644 libstdc++-v3/testsuite/25_algorithms/binary_search/partitioned.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/equal_range/partitioned.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/71545.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/lower_bound/partitioned.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/upper_bound/partitioned.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 753fb9824b7..a9748517114 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,17 @@ +2016-06-17 Jonathan Wakely + + 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. + 2016-06-16 François Dumont * include/debug/debug.h diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index fbd03a79e1e..c2ac0317f17 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 d95ea513a59..210b1734545 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 00000000000..63a6cada97e --- /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 +// . + +// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" } + +#include +#include +#include +#include + +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 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{}); + 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{}); + 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{}); + 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 00000000000..d3a43d06a58 --- /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 +// . + +// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" } + +#include +#include +#include +#include + +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 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{}); + 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{}); + 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 00000000000..6c9cd12cfef --- /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 +// . + +// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" } +// { dg-do link } + +#include + +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 00000000000..bba0b66ea80 --- /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 +// . + +// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" } + +#include +#include +#include +#include + +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 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{}); + 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{}); + 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 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{}); + 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{}); + 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 00000000000..96cfb2e2ded --- /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 +// . + +// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" } + +#include +#include +#include +#include + +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 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{}); + 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{}); + 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 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{}); + 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{}); + 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 a1c71a23cdd..53c9b3d4f64 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 + explicit + test_container(T (&arr)[N]) : test_container(arr, arr+N) + { } +#endif + ItType it(int pos) { -- 2.30.2