From 630a286ab6c4514c4cc4ff154cf68bf150f164f2 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Tue, 25 Aug 2015 20:27:03 +0000 Subject: [PATCH] re PR libstdc++/60519 (Debug mode should check comparators for irreflexivity) MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2015-08-24 François Dumont PR libstdc++/60519 * include/debug/formatter.h (_Debug_msg_id::__msg_irreflexive_ordering): New enum entry. * include/debug/functions.h (_Irreflexive_checker): New. (__is_irreflexive, __is_irreflexive_pred): New. * include/debug/macros.h (__glibcxx_check_irreflexive, __glibcxx_check_irreflexive_pred): New macros. (__glibcxx_check_irreflexive2, __glibcxx_check_irreflexive_pred2): New macros limited to post-C++11 mode. * include/debug/debug.h (__glibcxx_requires_irreflexive, __glibcxx_requires_irreflexive_pred): New macros, use latter. (__glibcxx_requires_irreflexive2, __glibcxx_requires_irreflexive_pred2): Likewise. * include/bits/stl_algo.h (partial_sort_copy): Add irreflexive debug check. (partial_sort_copy): Likewise. (lower_bound): Likewise. (upper_bound): Likewise. (equal_range): Likewise. (binary_search): Likewise. (inplace_merge): Likewise. (includes): Likewise. (next_permutation): Likewise. (prev_permutation): Likewise. (is_sorted_until): Likewise. (minmax_element): Likewise. (partial_sort): Likewise. (nth_element): Likewise. (sort): Likewise. (merge): Likewise. (stable_sort): Likewise. (set_union): Likewise. (set_intersection): Likewise. (set_difference): Likewise. (set_symmetric_difference): Likewise. (min_element): Likewise. (max_element): Likewise. * include/bits/stl_algobase.h (lower_bound): Likewise. (lexicographical_compare): Likewise. * include/bits/stl_heap.h (push_heap): Likewise. (pop_heap): Likewise. (make_heap): Likewise. (sort_heap): Likewise. (is_heap_until): Likewise. * testsuite/25_algorithms/lexicographical_compare/debug/ irreflexive_neg.cc: New. * testsuite/25_algorithms/lower_bound/debug/irreflexive.cc: New. * testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc: New. From-SVN: r227189 --- libstdc++-v3/ChangeLog | 56 +++++++++++++++++ libstdc++-v3/include/bits/stl_algo.h | 57 +++++++++++++++++- libstdc++-v3/include/bits/stl_algobase.h | 5 ++ libstdc++-v3/include/bits/stl_heap.h | 10 ++++ libstdc++-v3/include/debug/debug.h | 52 +++++++++------- libstdc++-v3/include/debug/formatter.h | 3 +- libstdc++-v3/include/debug/functions.h | 43 +++++++++++++ libstdc++-v3/include/debug/macros.h | 33 ++++++++++ libstdc++-v3/src/c++11/debug.cc | 10 +++- .../debug/irreflexive_neg.cc | 70 ++++++++++++++++++++++ .../25_algorithms/lower_bound/debug/irreflexive.cc | 47 +++++++++++++++ .../partial_sort_copy/debug/irreflexive_neg.cc | 43 +++++++++++++ 12 files changed, 405 insertions(+), 24 deletions(-) create mode 100644 libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/irreflexive_neg.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/lower_bound/debug/irreflexive.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index f6f68a8..44e0320 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,59 @@ +2015-08-24 François Dumont + + PR libstdc++/60519 + * include/debug/formatter.h (_Debug_msg_id::__msg_irreflexive_ordering): + New enum entry. + * include/debug/functions.h (_Irreflexive_checker): New. + (__is_irreflexive, __is_irreflexive_pred): New. + * include/debug/macros.h + (__glibcxx_check_irreflexive, __glibcxx_check_irreflexive_pred): New + macros. + (__glibcxx_check_irreflexive2, __glibcxx_check_irreflexive_pred2): New + macros limited to post-C++11 mode. + * include/debug/debug.h + (__glibcxx_requires_irreflexive, __glibcxx_requires_irreflexive_pred): + New macros, use latter. + (__glibcxx_requires_irreflexive2, __glibcxx_requires_irreflexive_pred2): + Likewise. + * include/bits/stl_algo.h + (partial_sort_copy): Add irreflexive debug check. + (partial_sort_copy): Likewise. + (lower_bound): Likewise. + (upper_bound): Likewise. + (equal_range): Likewise. + (binary_search): Likewise. + (inplace_merge): Likewise. + (includes): Likewise. + (next_permutation): Likewise. + (prev_permutation): Likewise. + (is_sorted_until): Likewise. + (minmax_element): Likewise. + (partial_sort): Likewise. + (nth_element): Likewise. + (sort): Likewise. + (merge): Likewise. + (stable_sort): Likewise. + (set_union): Likewise. + (set_intersection): Likewise. + (set_difference): Likewise. + (set_symmetric_difference): Likewise. + (min_element): Likewise. + (max_element): Likewise. + * include/bits/stl_algobase.h + (lower_bound): Likewise. + (lexicographical_compare): Likewise. + * include/bits/stl_heap.h + (push_heap): Likewise. + (pop_heap): Likewise. + (make_heap): Likewise. + (sort_heap): Likewise. + (is_heap_until): Likewise. + * testsuite/25_algorithms/lexicographical_compare/debug/ + irreflexive_neg.cc: New. + * testsuite/25_algorithms/lower_bound/debug/irreflexive.cc: New. + * testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc: + New. + 2015-08-24 Jonathan Wakely PR libstdc++/65049 diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 93e834a..f7f3e84 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -1750,6 +1750,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _OutputValueType>) __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); __glibcxx_requires_valid_range(__result_first, __result_last); return std::__partial_sort_copy(__first, __last, @@ -1803,6 +1804,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _OutputValueType, _OutputValueType>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); __glibcxx_requires_valid_range(__result_first, __result_last); return std::__partial_sort_copy(__first, __last, @@ -2027,6 +2029,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _ValueType, _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)); @@ -2082,6 +2085,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) __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()); @@ -2116,6 +2120,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Tp, _ValueType>) __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)); @@ -2189,7 +2194,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) __glibcxx_requires_partitioned_lower(__first, __last, __val); - __glibcxx_requires_partitioned_upper(__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(), @@ -2231,6 +2237,7 @@ _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), @@ -2262,6 +2269,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) __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, @@ -2300,6 +2308,7 @@ _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, @@ -2594,6 +2603,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_BidirectionalIterator>::value_type>) __glibcxx_requires_sorted(__first, __middle); __glibcxx_requires_sorted(__middle, __last); + __glibcxx_requires_irreflexive(__first, __last); std::__inplace_merge(__first, __middle, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -2636,6 +2646,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_BidirectionalIterator>::value_type>) __glibcxx_requires_sorted_pred(__first, __middle, __comp); __glibcxx_requires_sorted_pred(__middle, __last, __comp); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); std::__inplace_merge(__first, __middle, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -2847,6 +2858,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set(__first1, __last1, __first2); __glibcxx_requires_sorted_set(__first2, __last2, __first1); + __glibcxx_requires_irreflexive2(__first1, __last1); + __glibcxx_requires_irreflexive2(__first2, __last2); return std::__includes(__first1, __last1, __first2, __last2, __gnu_cxx::__ops::__iter_less_iter()); @@ -2891,6 +2904,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); + __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); + __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); return std::__includes(__first1, __last1, __first2, __last2, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -2966,6 +2981,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_BidirectionalIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); return std::__next_permutation (__first, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -2998,6 +3014,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_BidirectionalIterator>::value_type, typename iterator_traits<_BidirectionalIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); return std::__next_permutation (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -3064,6 +3081,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_BidirectionalIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); return std::__prev_permutation(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -3096,6 +3114,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_BidirectionalIterator>::value_type, typename iterator_traits<_BidirectionalIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); return std::__prev_permutation(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -3258,6 +3277,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); return std::__is_sorted_until(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -3283,6 +3303,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_ForwardIterator>::value_type, typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); return std::__is_sorted_until(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -3407,6 +3428,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); return std::__minmax_element(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -3436,6 +3458,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_ForwardIterator>::value_type, typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); return std::__minmax_element(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -4556,6 +4579,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __middle); __glibcxx_requires_valid_range(__middle, __last); + __glibcxx_requires_irreflexive(__first, __last); std::__partial_sort(__first, __middle, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -4595,6 +4619,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __middle); __glibcxx_requires_valid_range(__middle, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); std::__partial_sort(__first, __middle, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -4627,6 +4652,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __nth); __glibcxx_requires_valid_range(__nth, __last); + __glibcxx_requires_irreflexive(__first, __last); if (__first == __last || __nth == __last) return; @@ -4666,6 +4692,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __nth); __glibcxx_requires_valid_range(__nth, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); if (__first == __last || __nth == __last) return; @@ -4699,6 +4726,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); } @@ -4730,6 +4758,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_RandomAccessIterator>::value_type, typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); } @@ -4797,6 +4826,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set(__first1, __last1, __first2); __glibcxx_requires_sorted_set(__first2, __last2, __first1); + __glibcxx_requires_irreflexive2(__first1, __last1); + __glibcxx_requires_irreflexive2(__first2, __last2); return _GLIBCXX_STD_A::__merge(__first1, __last1, __first2, __last2, __result, @@ -4845,6 +4876,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); + __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); + __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); return _GLIBCXX_STD_A::__merge(__first1, __last1, __first2, __last2, __result, @@ -4898,6 +4931,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); _GLIBCXX_STD_A::__stable_sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -4933,6 +4967,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_RandomAccessIterator>::value_type, typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); _GLIBCXX_STD_A::__stable_sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -5010,6 +5045,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set(__first1, __last1, __first2); __glibcxx_requires_sorted_set(__first2, __last2, __first1); + __glibcxx_requires_irreflexive2(__first1, __last1); + __glibcxx_requires_irreflexive2(__first2, __last2); return _GLIBCXX_STD_A::__set_union(__first1, __last1, __first2, __last2, __result, @@ -5057,6 +5094,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); + __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); + __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); return _GLIBCXX_STD_A::__set_union(__first1, __last1, __first2, __last2, __result, @@ -5123,6 +5162,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set(__first1, __last1, __first2); __glibcxx_requires_sorted_set(__first2, __last2, __first1); + __glibcxx_requires_irreflexive2(__first1, __last1); + __glibcxx_requires_irreflexive2(__first2, __last2); return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, __first2, __last2, __result, @@ -5169,6 +5210,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); + __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); + __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, __first2, __last2, __result, @@ -5239,6 +5282,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set(__first1, __last1, __first2); __glibcxx_requires_sorted_set(__first2, __last2, __first1); + __glibcxx_requires_irreflexive2(__first1, __last1); + __glibcxx_requires_irreflexive2(__first2, __last2); return _GLIBCXX_STD_A::__set_difference(__first1, __last1, __first2, __last2, __result, @@ -5287,6 +5332,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); + __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); + __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); return _GLIBCXX_STD_A::__set_difference(__first1, __last1, __first2, __last2, __result, @@ -5365,6 +5412,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set(__first1, __last1, __first2); __glibcxx_requires_sorted_set(__first2, __last2, __first1); + __glibcxx_requires_irreflexive2(__first1, __last1); + __glibcxx_requires_irreflexive2(__first2, __last2); return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, __first2, __last2, __result, @@ -5414,6 +5463,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_InputIterator1>::value_type>) __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); + __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); + __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, __first2, __last2, __result, @@ -5452,6 +5503,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); return _GLIBCXX_STD_A::__min_element(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -5478,6 +5530,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_ForwardIterator>::value_type, typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); return _GLIBCXX_STD_A::__min_element(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -5514,6 +5567,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); return _GLIBCXX_STD_A::__max_element(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -5540,6 +5594,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_ForwardIterator>::value_type, typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); return _GLIBCXX_STD_A::__max_element(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 75a1516..99f3cc4 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -985,6 +985,7 @@ _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()); @@ -1209,7 +1210,9 @@ _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), @@ -1239,7 +1242,9 @@ _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/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h index 3ab37c75..e13b6be 100644 --- a/libstdc++-v3/include/bits/stl_heap.h +++ b/libstdc++-v3/include/bits/stl_heap.h @@ -159,6 +159,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); __glibcxx_requires_heap(__first, __last - 1); _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); @@ -193,6 +194,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); __glibcxx_requires_heap_pred(__first, __last - 1, __comp); _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); @@ -271,6 +273,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) __glibcxx_requires_non_empty_range(__first, __last); __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); __glibcxx_requires_heap(__first, __last); if (__last - __first > 1) @@ -301,6 +304,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); __glibcxx_requires_non_empty_range(__first, __last); __glibcxx_requires_heap_pred(__first, __last, __comp); @@ -356,6 +360,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); std::__make_heap(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); @@ -380,6 +385,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); std::__make_heap(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); @@ -415,6 +421,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); __glibcxx_requires_heap(__first, __last); std::__sort_heap(__first, __last, @@ -440,6 +447,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); __glibcxx_requires_heap_pred(__first, __last, __comp); std::__sort_heap(__first, __last, @@ -467,6 +475,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive(__first, __last); return __first + std::__is_heap_until(__first, std::distance(__first, __last), @@ -493,6 +502,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_irreflexive_pred(__first, __last, __comp); return __first + std::__is_heap_until(__first, std::distance(__first, __last), diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h index b6623e6..6b52b0a 100644 --- a/libstdc++-v3/include/debug/debug.h +++ b/libstdc++-v3/include/debug/debug.h @@ -77,41 +77,53 @@ namespace __gnu_debug # define __glibcxx_requires_string(_String) # define __glibcxx_requires_string_len(_String,_Len) # define __glibcxx_requires_subscript(_N) +# define __glibcxx_requires_irreflexive(_First,_Last) +# define __glibcxx_requires_irreflexive2(_First,_Last) +# define __glibcxx_requires_irreflexive_pred(_First,_Last,_Pred) +# define __glibcxx_requires_irreflexive_pred2(_First,_Last,_Pred) #else # include # define __glibcxx_requires_cond(_Cond,_Msg) _GLIBCXX_DEBUG_VERIFY(_Cond,_Msg) -# define __glibcxx_requires_valid_range(_First,_Last) \ - __glibcxx_check_valid_range(_First,_Last) -# define __glibcxx_requires_non_empty_range(_First,_Last) \ - __glibcxx_check_non_empty_range(_First,_Last) -# define __glibcxx_requires_sorted(_First,_Last) \ - __glibcxx_check_sorted(_First,_Last) -# define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \ - __glibcxx_check_sorted_pred(_First,_Last,_Pred) -# define __glibcxx_requires_sorted_set(_First1,_Last1,_First2) \ - __glibcxx_check_sorted_set(_First1,_Last1,_First2) +# define __glibcxx_requires_valid_range(_First,_Last) \ + __glibcxx_check_valid_range(_First,_Last) +# define __glibcxx_requires_non_empty_range(_First,_Last) \ + __glibcxx_check_non_empty_range(_First,_Last) +# define __glibcxx_requires_sorted(_First,_Last) \ + __glibcxx_check_sorted(_First,_Last) +# define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \ + __glibcxx_check_sorted_pred(_First,_Last,_Pred) +# define __glibcxx_requires_sorted_set(_First1,_Last1,_First2) \ + __glibcxx_check_sorted_set(_First1,_Last1,_First2) # define __glibcxx_requires_sorted_set_pred(_First1,_Last1,_First2,_Pred) \ - __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred) + __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred) # define __glibcxx_requires_partitioned_lower(_First,_Last,_Value) \ - __glibcxx_check_partitioned_lower(_First,_Last,_Value) + __glibcxx_check_partitioned_lower(_First,_Last,_Value) # define __glibcxx_requires_partitioned_upper(_First,_Last,_Value) \ - __glibcxx_check_partitioned_upper(_First,_Last,_Value) + __glibcxx_check_partitioned_upper(_First,_Last,_Value) # define __glibcxx_requires_partitioned_lower_pred(_First,_Last,_Value,_Pred) \ - __glibcxx_check_partitioned_lower_pred(_First,_Last,_Value,_Pred) + __glibcxx_check_partitioned_lower_pred(_First,_Last,_Value,_Pred) # define __glibcxx_requires_partitioned_upper_pred(_First,_Last,_Value,_Pred) \ - __glibcxx_check_partitioned_upper_pred(_First,_Last,_Value,_Pred) -# define __glibcxx_requires_heap(_First,_Last) \ - __glibcxx_check_heap(_First,_Last) -# define __glibcxx_requires_heap_pred(_First,_Last,_Pred) \ - __glibcxx_check_heap_pred(_First,_Last,_Pred) + __glibcxx_check_partitioned_upper_pred(_First,_Last,_Value,_Pred) +# define __glibcxx_requires_heap(_First,_Last) \ + __glibcxx_check_heap(_First,_Last) +# define __glibcxx_requires_heap_pred(_First,_Last,_Pred) \ + __glibcxx_check_heap_pred(_First,_Last,_Pred) # define __glibcxx_requires_nonempty() __glibcxx_check_nonempty() # define __glibcxx_requires_string(_String) __glibcxx_check_string(_String) # define __glibcxx_requires_string_len(_String,_Len) \ - __glibcxx_check_string_len(_String,_Len) + __glibcxx_check_string_len(_String,_Len) # define __glibcxx_requires_subscript(_N) __glibcxx_check_subscript(_N) +# define __glibcxx_requires_irreflexive(_First,_Last) \ + __glibcxx_check_irreflexive(_First,_Last) +# define __glibcxx_requires_irreflexive2(_First,_Last) \ + __glibcxx_check_irreflexive2(_First,_Last) +# define __glibcxx_requires_irreflexive_pred(_First,_Last,_Pred) \ + __glibcxx_check_irreflexive_pred(_First,_Last,_Pred) +# define __glibcxx_requires_irreflexive_pred2(_First,_Last,_Pred) \ + __glibcxx_check_irreflexive_pred2(_First,_Last,_Pred) # include diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h index 56ee807..9fc23c8 100644 --- a/libstdc++-v3/include/debug/formatter.h +++ b/libstdc++-v3/include/debug/formatter.h @@ -126,7 +126,8 @@ namespace __gnu_debug __msg_valid_load_factor, // others __msg_equal_allocs, - __msg_insert_range_from_self + __msg_insert_range_from_self, + __msg_irreflexive_ordering }; class _Error_formatter diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h index a9f234b..218092a 100644 --- a/libstdc++-v3/include/debug/functions.h +++ b/libstdc++-v3/include/debug/functions.h @@ -445,6 +445,49 @@ namespace __gnu_debug return __first == __last; } +#if __cplusplus >= 201103L + struct _Irreflexive_checker + { + template + static typename std::iterator_traits<_It>::reference + __deref(); + + template() < __deref<_It>())> + static bool + _S_is_valid(_It __it) + { return !(*__it < *__it); } + + // Fallback method if operator doesn't exist. + template + static bool + _S_is_valid(_Args...) + { return true; } + + template()(__deref<_It>(), __deref<_It>()))> + static bool + _S_is_valid_pred(_It __it, _Pred __pred) + { return !__pred(*__it, *__it); } + + // Fallback method if predicate can't be invoked. + template + static bool + _S_is_valid_pred(_Args...) + { return true; } + }; + + template + inline bool + __is_irreflexive(_Iterator __it) + { return _Irreflexive_checker::_S_is_valid(__it); } + + template + inline bool + __is_irreflexive_pred(_Iterator __it, _Pred __pred) + { return _Irreflexive_checker::_S_is_valid_pred(__it, __pred); } +#endif + } // namespace __gnu_debug #endif diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h index a4c2649..c636663 100644 --- a/libstdc++-v3/include/debug/macros.h +++ b/libstdc++-v3/include/debug/macros.h @@ -362,4 +362,37 @@ _GLIBCXX_DEBUG_VERIFY(_This.get_allocator() == _Other.get_allocator(), \ #define __glibcxx_check_string_len(_String,_Len) \ _GLIBCXX_DEBUG_PEDASSERT(_String != 0 || _Len == 0) +// Verify that a predicate is irreflexive +#define __glibcxx_check_irreflexive(_First,_Last) \ + _GLIBCXX_DEBUG_VERIFY(_First == _Last || !(*_First < *_First), \ + _M_message(__gnu_debug::__msg_irreflexive_ordering) \ + ._M_iterator_value_type(_First, "< operator type")) + +#if __cplusplus >= 201103L +# define __glibcxx_check_irreflexive2(_First,_Last) \ + _GLIBCXX_DEBUG_VERIFY(_First == _Last \ + || __gnu_debug::__is_irreflexive(_First), \ + _M_message(__gnu_debug::__msg_irreflexive_ordering) \ + ._M_iterator_value_type(_First, "< operator type")) +#else +# define __glibcxx_check_irreflexive2(_First,_Last) +#endif + +#define __glibcxx_check_irreflexive_pred(_First,_Last,_Pred) \ + _GLIBCXX_DEBUG_VERIFY(_First == _Last || !_Pred(*_First, *_First), \ + _M_message(__gnu_debug::__msg_irreflexive_ordering) \ + ._M_instance(_Pred, "functor") \ + ._M_iterator_value_type(_First, "ordered type")) + +#if __cplusplus >= 201103L +# define __glibcxx_check_irreflexive_pred2(_First,_Last,_Pred) \ + _GLIBCXX_DEBUG_VERIFY(_First == _Last \ + ||__gnu_debug::__is_irreflexive_pred(_First, _Pred), \ + _M_message(__gnu_debug::__msg_irreflexive_ordering) \ + ._M_instance(_Pred, "functor") \ + ._M_iterator_value_type(_First, "ordered type")) +#else +# define __glibcxx_check_irreflexive_pred2(_First,_Last,_Pred) +#endif + #endif diff --git a/libstdc++-v3/src/c++11/debug.cc b/libstdc++-v3/src/c++11/debug.cc index f60e31f..997c0f3 100644 --- a/libstdc++-v3/src/c++11/debug.cc +++ b/libstdc++-v3/src/c++11/debug.cc @@ -185,7 +185,8 @@ namespace __gnu_debug "load factor shall be positive", "allocators must be equal", "attempt to insert with an iterator range [%1.name;, %2.name;) from this" - " container" + " container", + "comparison doesn't meet irreflexive requirements, assert(!(a < a))" }; void @@ -592,11 +593,13 @@ namespace { const int __bufsize = 64; char __buf[__bufsize]; - __formatter->_M_format_word(__buf, __bufsize, "\"%s\" ", + __formatter->_M_format_word(__buf, __bufsize, "\"%s\"", __variant._M_name); __formatter->_M_print_word(__buf); } + __formatter->_M_print_word(" {\n"); + if (__variant._M_type) { __formatter->_M_print_word(" type = "); @@ -768,6 +771,7 @@ namespace __gnu_debug _M_variant._M_iterator._M_sequence); __formatter->_M_print_word(__buf); } + __formatter->_M_print_word("}\n"); break; case __sequence: @@ -786,10 +790,12 @@ namespace __gnu_debug if (_M_variant._M_instance._M_type) __formatter->_M_print_word(";\n"); + __formatter->_M_print_word("}\n"); break; case __iterator_value_type: __formatter->_M_print_word("iterator::value_type "); print_description(__formatter, _M_variant._M_iterator_value_type); + __formatter->_M_print_word("}\n"); break; default: break; diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/irreflexive_neg.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/irreflexive_neg.cc new file mode 100644 index 0000000..07ee8be --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/irreflexive_neg.cc @@ -0,0 +1,70 @@ +// Copyright (C) 2015 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" } +// { dg-require-debug-mode "" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +struct A +{ + A(int i) : _i(i) + { } + + int _i; +}; + +bool +operator<(A a, int i) +{ return a._i < i; } + +bool +operator<(int i, A a) +{ return i < a._i; } + +void test01() +{ + bool test __attribute__((unused)) = true; + + A as[] { 0, 1, 2, 3 }; + int is[] { 0, 1, 2, 3 }; + VERIFY( !std::lexicographical_compare(as, as + 4, is, is + 4) ); +} + +bool +bad_lower(int lhs, int rhs) +{ + if (lhs == 0) + return true; + + return lhs < rhs; +} + +void test02() +{ + int is[] { 0, 1, 2, 3 }; + std::lexicographical_compare(is, is + 4, is, is + 4, bad_lower); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/lower_bound/debug/irreflexive.cc b/libstdc++-v3/testsuite/25_algorithms/lower_bound/debug/irreflexive.cc new file mode 100644 index 0000000..c87b3e1 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/lower_bound/debug/irreflexive.cc @@ -0,0 +1,47 @@ +// Copyright (C) 2015 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-require-debug-mode "" } +// { dg-do compile } + +#include + +struct A +{ + A(int i) : _i(i) + { } + + int _i; +}; + +// Only knowns how to compare an A with an int. +struct A_int_comparer +{ + bool + operator()(A a, int i) const + { return a._i < i; } + + bool + operator()(int i, A a) const + { return i < a._i; } +}; + +void test01() +{ + A as[] { 0, 1, 2, 3 }; + std::lower_bound(as, as + 4, 1, A_int_comparer()); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc new file mode 100644 index 0000000..0218a26 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc @@ -0,0 +1,43 @@ +// Copyright (C) 2015 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-require-debug-mode "" } +// { dg-do run { xfail *-*-* } } + +#include + +bool +bad_lower(int lhs, int rhs) +{ + if (lhs == 0) + return true; + + return lhs < rhs; +} + +void test01() +{ + int ins[] { 0, 1, 2, 3 }; + int outs[] { 9, 9 }; + std::partial_sort_copy(ins, ins + 4, outs, outs + 2, bad_lower); +} + +int main() +{ + test01(); + return 0; +} -- 2.7.4