From 88632e48069605f5a27740a5df49f0f4e3c285ec Mon Sep 17 00:00:00 2001 From: Nikolas Klauser Date: Tue, 6 Jun 2023 13:57:45 -0700 Subject: [PATCH] [libc++] Refactor __less This simplifies the usage of `__less` by making the class not depend on the types compared, but instead the `operator()`. We can't remove the template completely because we explicitly instantiate `std::__sort` with `__less`. Reviewed By: ldionne, #libc Spies: arichardson, EricWF, libcxx-commits, mgrang Differential Revision: https://reviews.llvm.org/D145285 --- libcxx/include/__algorithm/binary_search.h | 3 +- libcxx/include/__algorithm/clamp.h | 2 +- libcxx/include/__algorithm/comp.h | 46 ++++--------- libcxx/include/__algorithm/equal_range.h | 6 +- libcxx/include/__algorithm/includes.h | 8 +-- libcxx/include/__algorithm/inplace_merge.h | 3 +- libcxx/include/__algorithm/is_heap.h | 2 +- libcxx/include/__algorithm/is_heap_until.h | 2 +- libcxx/include/__algorithm/is_sorted.h | 2 +- libcxx/include/__algorithm/is_sorted_until.h | 2 +- .../include/__algorithm/lexicographical_compare.h | 4 +- libcxx/include/__algorithm/lower_bound.h | 3 +- libcxx/include/__algorithm/make_heap.h | 3 +- libcxx/include/__algorithm/max.h | 4 +- libcxx/include/__algorithm/max_element.h | 3 +- libcxx/include/__algorithm/merge.h | 4 +- libcxx/include/__algorithm/min.h | 4 +- libcxx/include/__algorithm/min_element.h | 3 +- libcxx/include/__algorithm/minmax.h | 4 +- libcxx/include/__algorithm/minmax_element.h | 2 +- libcxx/include/__algorithm/next_permutation.h | 3 +- libcxx/include/__algorithm/nth_element.h | 3 +- libcxx/include/__algorithm/partial_sort.h | 3 +- libcxx/include/__algorithm/partial_sort_copy.h | 3 +- libcxx/include/__algorithm/pop_heap.h | 3 +- libcxx/include/__algorithm/prev_permutation.h | 3 +- libcxx/include/__algorithm/push_heap.h | 3 +- libcxx/include/__algorithm/set_difference.h | 9 +-- libcxx/include/__algorithm/set_intersection.h | 3 +- .../include/__algorithm/set_symmetric_difference.h | 3 +- libcxx/include/__algorithm/set_union.h | 3 +- libcxx/include/__algorithm/sort.h | 9 +-- libcxx/include/__algorithm/sort_heap.h | 3 +- libcxx/include/__algorithm/stable_sort.h | 2 +- libcxx/include/__algorithm/upper_bound.h | 9 +-- libcxx/include/forward_list | 6 +- libcxx/include/list | 4 +- libcxx/src/algorithm.cpp | 5 +- ...inst_using_non_transparent_comparators.pass.cpp | 77 ++++++++++++++++++++++ .../containers/sequences/array/compare.verify.cpp | 4 ++ libcxx/utils/data/ignore_format.txt | 2 - 41 files changed, 142 insertions(+), 128 deletions(-) create mode 100644 libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp diff --git a/libcxx/include/__algorithm/binary_search.h b/libcxx/include/__algorithm/binary_search.h index 8f958c2c..0c8f554 100644 --- a/libcxx/include/__algorithm/binary_search.h +++ b/libcxx/include/__algorithm/binary_search.h @@ -37,8 +37,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::binary_search(__first, __last, __value, - __less::value_type, _Tp>()); + return std::binary_search(__first, __last, __value, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/clamp.h b/libcxx/include/__algorithm/clamp.h index 336b93f..ce57405 100644 --- a/libcxx/include/__algorithm/clamp.h +++ b/libcxx/include/__algorithm/clamp.h @@ -37,7 +37,7 @@ _LIBCPP_INLINE_VISIBILITY constexpr const _Tp& clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi) { - return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>()); + return _VSTD::clamp(__v, __lo, __hi, __less<>()); } #endif diff --git a/libcxx/include/__algorithm/comp.h b/libcxx/include/__algorithm/comp.h index 1001e42..9474536 100644 --- a/libcxx/include/__algorithm/comp.h +++ b/libcxx/include/__algorithm/comp.h @@ -29,41 +29,17 @@ struct __equal_to { template struct __is_trivial_equality_predicate<__equal_to, _Lhs, _Rhs> : true_type {}; -template -struct __less -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} -}; - -template -struct __less<_T1, _T1> -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template -struct __less -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template -struct __less<_T1, const _T1> -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} +// The definition is required because __less is part of the ABI, but it's empty +// because all comparisons should be transparent. +template +struct __less {}; + +template <> +struct __less { + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool operator()(const _Tp& __lhs, const _Up& __rhs) const { + return __lhs < __rhs; + } }; _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/equal_range.h b/libcxx/include/__algorithm/equal_range.h index 2075b03..b731dcc 100644 --- a/libcxx/include/__algorithm/equal_range.h +++ b/libcxx/include/__algorithm/equal_range.h @@ -75,11 +75,7 @@ equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __valu template _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_ForwardIterator, _ForwardIterator> equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::equal_range( - std::move(__first), - std::move(__last), - __value, - __less::value_type, _Tp>()); + return std::equal_range(std::move(__first), std::move(__last), __value, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/includes.h b/libcxx/include/__algorithm/includes.h index cc39f27..88253e2 100644 --- a/libcxx/include/__algorithm/includes.h +++ b/libcxx/include/__algorithm/includes.h @@ -61,13 +61,7 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { - return std::includes( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__last2), - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); + return std::includes(std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h index 5bbefc9..44a9425 100644 --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -246,8 +246,7 @@ inline _LIBCPP_HIDE_FROM_ABI void inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) { - std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), - __less::value_type>()); + std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_heap.h b/libcxx/include/__algorithm/is_heap.h index 2dcb4a2..93d84d3 100644 --- a/libcxx/include/__algorithm/is_heap.h +++ b/libcxx/include/__algorithm/is_heap.h @@ -36,7 +36,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - return _VSTD::is_heap(__first, __last, __less::value_type>()); + return _VSTD::is_heap(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_heap_until.h b/libcxx/include/__algorithm/is_heap_until.h index 6ed4cb2..d713111 100644 --- a/libcxx/include/__algorithm/is_heap_until.h +++ b/libcxx/include/__algorithm/is_heap_until.h @@ -58,7 +58,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) { - return _VSTD::__is_heap_until(__first, __last, __less::value_type>()); + return _VSTD::__is_heap_until(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_sorted.h b/libcxx/include/__algorithm/is_sorted.h index bf44f45..a321c2c 100644 --- a/libcxx/include/__algorithm/is_sorted.h +++ b/libcxx/include/__algorithm/is_sorted.h @@ -36,7 +36,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_sorted(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::is_sorted(__first, __last, __less::value_type>()); + return _VSTD::is_sorted(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_sorted_until.h b/libcxx/include/__algorithm/is_sorted_until.h index b668300..890b936 100644 --- a/libcxx/include/__algorithm/is_sorted_until.h +++ b/libcxx/include/__algorithm/is_sorted_until.h @@ -48,7 +48,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::is_sorted_until(__first, __last, __less::value_type>()); + return _VSTD::is_sorted_until(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/lexicographical_compare.h b/libcxx/include/__algorithm/lexicographical_compare.h index 0a13c5d..62b72ed 100644 --- a/libcxx/include/__algorithm/lexicographical_compare.h +++ b/libcxx/include/__algorithm/lexicographical_compare.h @@ -52,9 +52,7 @@ bool lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { - return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); + return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/lower_bound.h b/libcxx/include/__algorithm/lower_bound.h index 8109393..7a7a299 100644 --- a/libcxx/include/__algorithm/lower_bound.h +++ b/libcxx/include/__algorithm/lower_bound.h @@ -58,8 +58,7 @@ _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::lower_bound(__first, __last, __value, - __less::value_type, _Tp>()); + return std::lower_bound(__first, __last, __value, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h index d66cfe2..ee3b6d8 100644 --- a/libcxx/include/__algorithm/make_heap.h +++ b/libcxx/include/__algorithm/make_heap.h @@ -47,8 +47,7 @@ void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Com template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::make_heap(std::move(__first), std::move(__last), - __less::value_type>()); + std::make_heap(std::move(__first), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/max.h b/libcxx/include/__algorithm/max.h index 97f61f2..5d8e64c 100644 --- a/libcxx/include/__algorithm/max.h +++ b/libcxx/include/__algorithm/max.h @@ -39,7 +39,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 const _Tp& max(_LIBCPP_LIFETIMEBOUND const _Tp& __a, _LIBCPP_LIFETIMEBOUND const _Tp& __b) { - return _VSTD::max(__a, __b, __less<_Tp>()); + return _VSTD::max(__a, __b, __less<>()); } #ifndef _LIBCPP_CXX03_LANG @@ -59,7 +59,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp max(initializer_list<_Tp> __t) { - return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>()); + return *_VSTD::max_element(__t.begin(), __t.end(), __less<>()); } #endif // _LIBCPP_CXX03_LANG diff --git a/libcxx/include/__algorithm/max_element.h b/libcxx/include/__algorithm/max_element.h index f816a17..8fd52c7 100644 --- a/libcxx/include/__algorithm/max_element.h +++ b/libcxx/include/__algorithm/max_element.h @@ -48,8 +48,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::max_element(__first, __last, - __less::value_type>()); + return _VSTD::max_element(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/merge.h b/libcxx/include/__algorithm/merge.h index e54e430..7ee7aaa 100644 --- a/libcxx/include/__algorithm/merge.h +++ b/libcxx/include/__algorithm/merge.h @@ -60,9 +60,7 @@ _OutputIterator merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { - typedef typename iterator_traits<_InputIterator1>::value_type __v1; - typedef typename iterator_traits<_InputIterator2>::value_type __v2; - return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>()); + return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/min.h b/libcxx/include/__algorithm/min.h index d073a16..3c0debd 100644 --- a/libcxx/include/__algorithm/min.h +++ b/libcxx/include/__algorithm/min.h @@ -39,7 +39,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 const _Tp& min(_LIBCPP_LIFETIMEBOUND const _Tp& __a, _LIBCPP_LIFETIMEBOUND const _Tp& __b) { - return _VSTD::min(__a, __b, __less<_Tp>()); + return _VSTD::min(__a, __b, __less<>()); } #ifndef _LIBCPP_CXX03_LANG @@ -59,7 +59,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp min(initializer_list<_Tp> __t) { - return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>()); + return *_VSTD::min_element(__t.begin(), __t.end(), __less<>()); } #endif // _LIBCPP_CXX03_LANG diff --git a/libcxx/include/__algorithm/min_element.h b/libcxx/include/__algorithm/min_element.h index aeabd30..7d58e98 100644 --- a/libcxx/include/__algorithm/min_element.h +++ b/libcxx/include/__algorithm/min_element.h @@ -61,8 +61,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::min_element(__first, __last, - __less::value_type>()); + return _VSTD::min_element(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/minmax.h b/libcxx/include/__algorithm/minmax.h index f486de2e..bdcf57b 100644 --- a/libcxx/include/__algorithm/minmax.h +++ b/libcxx/include/__algorithm/minmax.h @@ -39,7 +39,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 pair minmax(_LIBCPP_LIFETIMEBOUND const _Tp& __a, _LIBCPP_LIFETIMEBOUND const _Tp& __b) { - return std::minmax(__a, __b, __less<_Tp>()); + return std::minmax(__a, __b, __less<>()); } #ifndef _LIBCPP_CXX03_LANG @@ -59,7 +59,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Tp, _Tp> minmax(initializer_list<_Tp> __t) { - return std::minmax(__t, __less<_Tp>()); + return std::minmax(__t, __less<>()); } #endif // _LIBCPP_CXX03_LANG diff --git a/libcxx/include/__algorithm/minmax_element.h b/libcxx/include/__algorithm/minmax_element.h index eca460de..5bcaf83 100644 --- a/libcxx/include/__algorithm/minmax_element.h +++ b/libcxx/include/__algorithm/minmax_element.h @@ -94,7 +94,7 @@ minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __com template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_ForwardIterator, _ForwardIterator> minmax_element(_ForwardIterator __first, _ForwardIterator __last) { - return std::minmax_element(__first, __last, __less::value_type>()); + return std::minmax_element(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/next_permutation.h b/libcxx/include/__algorithm/next_permutation.h index 73e8b99..d89768d 100644 --- a/libcxx/include/__algorithm/next_permutation.h +++ b/libcxx/include/__algorithm/next_permutation.h @@ -69,8 +69,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) { - return _VSTD::next_permutation(__first, __last, - __less::value_type>()); + return _VSTD::next_permutation(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/nth_element.h b/libcxx/include/__algorithm/nth_element.h index 9fdfb2c..c847698 100644 --- a/libcxx/include/__algorithm/nth_element.h +++ b/libcxx/include/__algorithm/nth_element.h @@ -249,8 +249,7 @@ void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Ra template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) { - std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less::value_type>()); + std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h index 4b8e0e7..4924d5a 100644 --- a/libcxx/include/__algorithm/partial_sort.h +++ b/libcxx/include/__algorithm/partial_sort.h @@ -88,8 +88,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) { - _VSTD::partial_sort(__first, __middle, __last, - __less::value_type>()); + _VSTD::partial_sort(__first, __middle, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partial_sort_copy.h b/libcxx/include/__algorithm/partial_sort_copy.h index 1aba071..b9635c5 100644 --- a/libcxx/include/__algorithm/partial_sort_copy.h +++ b/libcxx/include/__algorithm/partial_sort_copy.h @@ -79,8 +79,7 @@ _RandomAccessIterator partial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last) { - return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, - __less::value_type>()); + return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h index 4187523..1dda268 100644 --- a/libcxx/include/__algorithm/pop_heap.h +++ b/libcxx/include/__algorithm/pop_heap.h @@ -65,8 +65,7 @@ void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::pop_heap(std::move(__first), std::move(__last), - __less::value_type>()); + std::pop_heap(std::move(__first), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/prev_permutation.h b/libcxx/include/__algorithm/prev_permutation.h index 0b86ab7..187f1e3 100644 --- a/libcxx/include/__algorithm/prev_permutation.h +++ b/libcxx/include/__algorithm/prev_permutation.h @@ -70,8 +70,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) { - return _VSTD::prev_permutation(__first, __last, - __less::value_type>()); + return _VSTD::prev_permutation(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/push_heap.h b/libcxx/include/__algorithm/push_heap.h index e831162..5f5db79 100644 --- a/libcxx/include/__algorithm/push_heap.h +++ b/libcxx/include/__algorithm/push_heap.h @@ -69,8 +69,7 @@ void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Com template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::push_heap(std::move(__first), std::move(__last), - __less::value_type>()); + std::push_heap(std::move(__first), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_difference.h b/libcxx/include/__algorithm/set_difference.h index 5a7d3bc..26a3000 100644 --- a/libcxx/include/__algorithm/set_difference.h +++ b/libcxx/include/__algorithm/set_difference.h @@ -66,14 +66,7 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_d _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { - return std::__set_difference<_ClassicAlgPolicy>( - __first1, - __last1, - __first2, - __last2, - __result, - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()).second; + return std::__set_difference<_ClassicAlgPolicy>(__first1, __last1, __first2, __last2, __result, __less<>()).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_intersection.h b/libcxx/include/__algorithm/set_intersection.h index 9fa7799..f2603fe 100644 --- a/libcxx/include/__algorithm/set_intersection.h +++ b/libcxx/include/__algorithm/set_intersection.h @@ -89,8 +89,7 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_i std::move(__first2), std::move(__last2), std::move(__result), - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()) + __less<>()) .__out_; } diff --git a/libcxx/include/__algorithm/set_symmetric_difference.h b/libcxx/include/__algorithm/set_symmetric_difference.h index bcb0958..832c397 100644 --- a/libcxx/include/__algorithm/set_symmetric_difference.h +++ b/libcxx/include/__algorithm/set_symmetric_difference.h @@ -96,8 +96,7 @@ _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_symmetri std::move(__first2), std::move(__last2), std::move(__result), - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); + __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_union.h b/libcxx/include/__algorithm/set_union.h index 4d154b8..cf48ada 100644 --- a/libcxx/include/__algorithm/set_union.h +++ b/libcxx/include/__algorithm/set_union.h @@ -92,8 +92,7 @@ _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_union( std::move(__first2), std::move(__last2), std::move(__result), - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); + __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h index 3215c52..24fbd2a 100644 --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -124,8 +124,8 @@ _LIBCPP_HIDE_FROM_ABI void __sort5(_ForwardIterator __x1, _ForwardIterator __x2, // The comparator being simple is a prerequisite for using the branchless optimization. template struct __is_simple_comparator : false_type {}; -template -struct __is_simple_comparator<__less<_Tp>&> : true_type {}; +template <> +struct __is_simple_comparator<__less<>&> : true_type {}; template struct __is_simple_comparator&> : true_type {}; template @@ -885,7 +885,8 @@ using __sort_is_specialized_in_library = __is_any_of< long double>; template ::value, int> = 0> -_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<_Type>& __comp) { +_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<>&) { + __less<_Type> __comp; std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); } @@ -934,7 +935,7 @@ void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __c template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::sort(__first, __last, __less::value_type>()); + std::sort(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/sort_heap.h b/libcxx/include/__algorithm/sort_heap.h index ed72ff9..a82926e 100644 --- a/libcxx/include/__algorithm/sort_heap.h +++ b/libcxx/include/__algorithm/sort_heap.h @@ -50,8 +50,7 @@ void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Com template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::sort_heap(std::move(__first), std::move(__last), - __less::value_type>()); + std::sort_heap(std::move(__first), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h index 38fd2be..dc24218 100644 --- a/libcxx/include/__algorithm/stable_sort.h +++ b/libcxx/include/__algorithm/stable_sort.h @@ -272,7 +272,7 @@ void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C template inline _LIBCPP_HIDE_FROM_ABI void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::stable_sort(__first, __last, __less::value_type>()); + std::stable_sort(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/upper_bound.h b/libcxx/include/__algorithm/upper_bound.h index 96552ce..ef36a3c 100644 --- a/libcxx/include/__algorithm/upper_bound.h +++ b/libcxx/include/__algorithm/upper_bound.h @@ -47,8 +47,7 @@ __upper_bound(_Iter __first, _Sent __last, const _Tp& __value, _Compare&& __comp template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { - static_assert(is_copy_constructible<_ForwardIterator>::value, - "Iterator has to be copy constructible"); + static_assert(is_copy_constructible<_ForwardIterator>::value, "Iterator has to be copy constructible"); return std::__upper_bound<_ClassicAlgPolicy>( std::move(__first), std::move(__last), __value, std::move(__comp), std::__identity()); } @@ -56,11 +55,7 @@ upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __valu template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::upper_bound( - std::move(__first), - std::move(__last), - __value, - __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); + return std::upper_bound(std::move(__first), std::move(__last), __value, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/forward_list b/libcxx/include/forward_list index 5625a0b..10c9c15 100644 --- a/libcxx/include/forward_list +++ b/libcxx/include/forward_list @@ -865,18 +865,18 @@ public: _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY - void merge(forward_list&& __x) {merge(__x, __less());} + void merge(forward_list&& __x) {merge(__x, __less<>());} template _LIBCPP_INLINE_VISIBILITY void merge(forward_list&& __x, _Compare __comp) {merge(__x, _VSTD::move(__comp));} #endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY - void merge(forward_list& __x) {merge(__x, __less());} + void merge(forward_list& __x) {merge(__x, __less<>());} template _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp); _LIBCPP_INLINE_VISIBILITY - void sort() {sort(__less());} + void sort() {sort(__less<>());} template _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp); _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT; diff --git a/libcxx/include/list b/libcxx/include/list index dd56b89..a762b6b 100644 --- a/libcxx/include/list +++ b/libcxx/include/list @@ -2101,7 +2101,7 @@ inline void list<_Tp, _Alloc>::merge(list& __c) { - merge(__c, __less()); + merge(__c, __less<>()); } template @@ -2163,7 +2163,7 @@ inline void list<_Tp, _Alloc>::sort() { - sort(__less()); + sort(__less<>()); } template diff --git a/libcxx/src/algorithm.cpp b/libcxx/src/algorithm.cpp index 5a47558..af9d60a 100644 --- a/libcxx/src/algorithm.cpp +++ b/libcxx/src/algorithm.cpp @@ -19,9 +19,10 @@ void __sort(RandomAccessIterator first, RandomAccessIterator last, Comp comp) { // that the default comparator is in use so that we are sure that there are no // branches in the comparator. std::__introsort<_ClassicAlgPolicy, - Comp&, + ranges::less, RandomAccessIterator, - __use_branchless_sort::value>(first, last, comp, depth_limit); + __use_branchless_sort::value>( + first, last, ranges::less{}, depth_limit); } // clang-format off diff --git a/libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp new file mode 100644 index 0000000..66b620e --- /dev/null +++ b/libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include +#include + +#include "test_macros.h" + +template +struct Iterator { + using value_type = T; + using pointer = value_type*; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + struct reference { + T* ptr_; + + reference(T* ptr) : ptr_(ptr) {} + + friend bool operator<(reference a, reference b) { return *a.ptr_ < *b.ptr_; } + friend bool operator<(reference a, value_type const& b) { return *a.ptr_ < b; } + friend bool operator<(value_type const& a, reference b) { return a < *b.ptr_; } + + operator T&() const; + }; + + Iterator& operator++() { + ptr_++; + return *this; + } + + Iterator operator++(int) { + Iterator tmp = *this; + ptr_++; + return tmp; + } + + friend bool operator==(Iterator const& a, Iterator const& b) { return a.ptr_ == b.ptr_; } + friend bool operator!=(Iterator const& a, Iterator const& b) { return !(a == b); } + + reference operator*() const { return reference(ptr_); } + + explicit Iterator(T* ptr) : ptr_(ptr) {} + Iterator() = default; + Iterator(Iterator const&) = default; + Iterator(Iterator&&) = default; + + Iterator& operator=(Iterator const&) = default; + Iterator& operator=(Iterator&&) = default; + +private: + T* ptr_; +}; + +int main() { + int array[5] = {1, 2, 3, 4, 5}; + Iterator first(array); + Iterator middle(array + 3); + Iterator last(array + 5); + (void)std::binary_search(first, last, 3); + (void)std::equal_range(first, last, 3); + (void)std::includes(first, last, first, last); + (void)std::is_sorted_until(first, last); + (void)std::is_sorted(first, last); + (void)std::lexicographical_compare(first, last, first, last); + (void)std::lower_bound(first, last, 3); + (void)std::max_element(first, last); + (void)std::min_element(first, last); + (void)std::minmax_element(first, last); + (void)std::upper_bound(first, last, 3); +} diff --git a/libcxx/test/std/containers/sequences/array/compare.verify.cpp b/libcxx/test/std/containers/sequences/array/compare.verify.cpp index 4b00160..e03f001 100644 --- a/libcxx/test/std/containers/sequences/array/compare.verify.cpp +++ b/libcxx/test/std/containers/sequences/array/compare.verify.cpp @@ -28,6 +28,10 @@ template struct NoCompare {}; +#if TEST_STD_VER >= 14 && TEST_STD_VER <= 17 +// expected-error@*:* 3 {{no matching function for call to object of type 'std::__less'}} +#endif + int main(int, char**) { { typedef NoCompare<0> T; diff --git a/libcxx/utils/data/ignore_format.txt b/libcxx/utils/data/ignore_format.txt index 3e9728a..4da365b 100644 --- a/libcxx/utils/data/ignore_format.txt +++ b/libcxx/utils/data/ignore_format.txt @@ -37,7 +37,6 @@ libcxx/benchmarks/unordered_set_operations.bench.cpp libcxx/benchmarks/vector_operations.bench.cpp libcxx/include/__algorithm/binary_search.h libcxx/include/__algorithm/clamp.h -libcxx/include/__algorithm/comp.h libcxx/include/__algorithm/comp_ref_type.h libcxx/include/__algorithm/copy_backward.h libcxx/include/__algorithm/copy_if.h @@ -208,7 +207,6 @@ libcxx/include/__algorithm/transform.h libcxx/include/__algorithm/uniform_random_bit_generator_adaptor.h libcxx/include/__algorithm/unwrap_iter.h libcxx/include/__algorithm/unwrap_range.h -libcxx/include/__algorithm/upper_bound.h libcxx/include/any libcxx/include/array libcxx/include/__atomic/atomic_base.h -- 2.7.4