diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -107,7 +107,7 @@ add_library( cxx-benchmarks-flags-libcxx INTERFACE) target_link_libraries( cxx-benchmarks-flags-libcxx INTERFACE cxx-benchmarks-flags) target_compile_options(cxx-benchmarks-flags-libcxx INTERFACE ${SANITIZER_FLAGS} -Wno-user-defined-literals -Wno-suggest-override) -target_link_options( cxx-benchmarks-flags-libcxx INTERFACE -nodefaultlibs "-L${BENCHMARK_LIBCXX_INSTALL}/lib" ${SANITIZER_FLAGS}) +target_link_options( cxx-benchmarks-flags-libcxx INTERFACE -nodefaultlibs "-L${BENCHMARK_LIBCXX_INSTALL}/lib" "-L${BENCHMARK_LIBCXX_INSTALL}/lib64" ${SANITIZER_FLAGS}) set(libcxx_benchmark_targets) @@ -158,6 +158,7 @@ #============================================================================== set(BENCHMARK_TESTS algorithms.partition_point.bench.cpp + algorithms/equal.bench.cpp algorithms/lower_bound.bench.cpp algorithms/make_heap.bench.cpp algorithms/make_heap_then_sort_heap.bench.cpp diff --git a/libcxx/benchmarks/algorithms/equal.bench.cpp b/libcxx/benchmarks/algorithms/equal.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/equal.bench.cpp @@ -0,0 +1,46 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +static void bm_equal_iter(benchmark::State& state) { + std::vector vec1(state.range(), '1'); + std::vector vec2(state.range(), '1'); + for (auto _ : state) { + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize(vec2); + benchmark::DoNotOptimize(std::equal(vec1.begin(), vec1.end(), vec2.begin())); + } +} +BENCHMARK(bm_equal_iter)->DenseRange(1, 8)->Range(16, 1 << 20); + +static void bm_equal(benchmark::State& state) { + std::vector vec1(state.range(), '1'); + std::vector vec2(state.range(), '1'); + for (auto _ : state) { + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize(vec2); + benchmark::DoNotOptimize(std::equal(vec1.begin(), vec1.end(), vec2.begin(), vec2.end())); + } +} +BENCHMARK(bm_equal)->DenseRange(1, 8)->Range(16, 1 << 20); + +static void bm_ranges_equal(benchmark::State& state) { + std::vector vec1(state.range(), '1'); + std::vector vec2(state.range(), '1'); + for (auto _ : state) { + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize(vec2); + benchmark::DoNotOptimize(std::ranges::equal(vec1, vec2)); + } +} +BENCHMARK(bm_ranges_equal)->DenseRange(1, 8)->Range(16, 1 << 20); + +BENCHMARK_MAIN(); diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -42,6 +42,8 @@ Improvements and New Features ----------------------------- +- ``std::equal`` and ``std::ranges::equal`` are now forwarding to ``std::memcmp`` for integral types and pointers, + which can lead up to 40x performance improvements. - ``std::string_view`` now provides iterators that check for out-of-bounds accesses when the safe libc++ mode is enabled. diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -638,6 +638,7 @@ __type_traits/is_destructible.h __type_traits/is_empty.h __type_traits/is_enum.h + __type_traits/is_equality_comparable.h __type_traits/is_final.h __type_traits/is_floating_point.h __type_traits/is_function.h @@ -702,6 +703,7 @@ __type_traits/nat.h __type_traits/negation.h __type_traits/noexcept_move_assign_container.h + __type_traits/predicate_traits.h __type_traits/promote.h __type_traits/rank.h __type_traits/remove_all_extents.h diff --git a/libcxx/include/__algorithm/comp.h b/libcxx/include/__algorithm/comp.h --- a/libcxx/include/__algorithm/comp.h +++ b/libcxx/include/__algorithm/comp.h @@ -10,6 +10,8 @@ #define _LIBCPP___ALGORITHM_COMP_H #include <__config> +#include <__type_traits/integral_constant.h> +#include <__type_traits/predicate_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -24,6 +26,9 @@ } }; +template +struct __is_trivial_equality_predicate<__equal_to, _Lhs, _Rhs> : true_type {}; + template struct __less { diff --git a/libcxx/include/__algorithm/equal.h b/libcxx/include/__algorithm/equal.h --- a/libcxx/include/__algorithm/equal.h +++ b/libcxx/include/__algorithm/equal.h @@ -11,9 +11,20 @@ #define _LIBCPP___ALGORITHM_EQUAL_H #include <__algorithm/comp.h> +#include <__algorithm/unwrap_iter.h> #include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include <__string/constexpr_c_functions.h> +#include <__type_traits/enable_if.h> +#include <__type_traits/integral_constant.h> +#include <__type_traits/is_constant_evaluated.h> +#include <__type_traits/is_equality_comparable.h> +#include <__type_traits/is_volatile.h> +#include <__type_traits/predicate_traits.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -22,23 +33,42 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool -equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { +_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_iter_impl( + _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate& __pred) { for (; __first1 != __last1; ++__first1, (void)++__first2) if (!__pred(*__first1, *__first2)) return false; return true; } +template < + class _Tp, + class _Up, + class _BinaryPredicate, + __enable_if_t<__is_trivial_equality_predicate<_BinaryPredicate, _Tp, _Up>::value && !is_volatile<_Tp>::value && + !is_volatile<_Up>::value && __is_trivially_equality_comparable<_Tp, _Up>::value, + int> = 0> +_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +__equal_iter_impl(_Tp* __first1, _Tp* __last1, _Up* __first2, _BinaryPredicate&) { + return std::__constexpr_memcmp(__first1, __first2, (__last1 - __first1) * sizeof(_Tp)) == 0; +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { + return std::__equal_iter_impl( + std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2), __pred); +} + template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) { return std::equal(__first1, __last1, __first2, __equal_to()); } #if _LIBCPP_STD_VER >= 14 template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred, input_iterator_tag, input_iterator_tag) { for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2) @@ -47,19 +77,52 @@ return __first1 == __last1 && __first2 == __last2; } +template +_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl( + _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __comp, _Proj1& __proj1, _Proj2& __proj2) { + while (__first1 != __last1 && __first2 != __last2) { + if (!std::__invoke(__comp, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) + return false; + ++__first1; + ++__first2; + } + return __first1 == __last1 && __first2 == __last2; +} + +template ::value && __is_identity<_Proj1>::value && + __is_identity<_Proj2>::value && !is_volatile<_Tp>::value && !is_volatile<_Up>::value && + __is_trivially_equality_comparable<_Tp, _Up>::value, + int> = 0> +_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl( + _Tp* __first1, _Tp* __last1, _Up* __first2, _Up*, _Pred&, _Proj1&, _Proj2&) { + return std::__constexpr_memcmp(__first1, __first2, (__last1 - __first1) * sizeof(_Tp)) == 0; +} + template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) return false; - return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2, - _BinaryPredicate&>(__first1, __last1, __first2, __pred); + __identity __proj; + return std::__equal_impl( + std::__unwrap_iter(__first1), + std::__unwrap_iter(__last1), + std::__unwrap_iter(__first2), + std::__unwrap_iter(__last2), + __pred, + __proj, + __proj); } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred) { return _VSTD::__equal<_BinaryPredicate&>( @@ -68,7 +131,7 @@ } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { return std::__equal( __first1, diff --git a/libcxx/include/__algorithm/make_projected.h b/libcxx/include/__algorithm/make_projected.h --- a/libcxx/include/__algorithm/make_projected.h +++ b/libcxx/include/__algorithm/make_projected.h @@ -55,25 +55,12 @@ }; -template -struct __can_use_pristine_comp : false_type {}; - -template -struct __can_use_pristine_comp<_Pred, _Proj, __enable_if_t< - !is_member_pointer::type>::value && ( -#if _LIBCPP_STD_VER >= 20 - is_same::type, identity>::value || -#endif - is_same::type, __identity>::value - ) -> > : true_type {}; - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static -__enable_if_t< - !__can_use_pristine_comp<_Pred, _Proj>::value, - _ProjectedPred<_Pred, _Proj> -> +template ::type>::value && + __is_identity::type>::value), + int> = 0> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static _ProjectedPred<_Pred, _Proj> __make_projected(_Pred& __pred, _Proj& __proj) { return _ProjectedPred<_Pred, _Proj>(__pred, __proj); } @@ -81,13 +68,12 @@ // Avoid creating the functor and just use the pristine comparator -- for certain algorithms, this would enable // optimizations that rely on the type of the comparator. Additionally, this results in less layers of indirection in // the call stack when the comparator is invoked, even in an unoptimized build. -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static -__enable_if_t< - __can_use_pristine_comp<_Pred, _Proj>::value, - _Pred& -> -__make_projected(_Pred& __pred, _Proj&) { +template ::type>::value && + __is_identity::type>::value, + int> = 0> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static _Pred& __make_projected(_Pred& __pred, _Proj&) { return __pred; } @@ -102,7 +88,7 @@ template _LIBCPP_HIDE_FROM_ABI constexpr static decltype(auto) __make_projected_comp(_Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) { - if constexpr (same_as, identity> && same_as, identity> && + if constexpr (__is_identity>::value && __is_identity>::value && !is_member_pointer_v>) { // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable // optimizations that rely on the type of the comparator. diff --git a/libcxx/include/__algorithm/ranges_equal.h b/libcxx/include/__algorithm/ranges_equal.h --- a/libcxx/include/__algorithm/ranges_equal.h +++ b/libcxx/include/__algorithm/ranges_equal.h @@ -9,6 +9,8 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_EQUAL_H #define _LIBCPP___ALGORITHM_RANGES_EQUAL_H +#include <__algorithm/equal.h> +#include <__algorithm/unwrap_range.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> @@ -31,29 +33,6 @@ namespace ranges { namespace __equal { struct __fn { -private: - template - _LIBCPP_HIDE_FROM_ABI constexpr static - bool __equal_impl(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2) { - while (__first1 != __last1 && __first2 != __last2) { - if (!std::invoke(__pred, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__first2))) - return false; - ++__first1; - ++__first2; - } - return __first1 == __last1 && __first2 == __last2; - } - -public: - template _Sent1, input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, class _Pred = ranges::equal_to, @@ -70,11 +49,13 @@ if (__last1 - __first1 != __last2 - __first2) return false; } - return __equal_impl(std::move(__first1), std::move(__last1), - std::move(__first2), std::move(__last2), - __pred, - __proj1, - __proj2); + auto __unwrapped1 = std::__unwrap_range(std::move(__first1), std::move(__last1)); + auto __unwrapped2 = std::__unwrap_range(std::move(__first2), std::move(__last2)); + return std::__equal_impl(std::move(__unwrapped1.first), std::move(__unwrapped1.second), + std::move(__unwrapped2.first), std::move(__unwrapped2.second), + __pred, + __proj1, + __proj2); } template = 20 +template ::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI constexpr _Iter __unwrap_iter(_Iter __i) noexcept { + return __i; +} +#endif + template > _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _OrigIter __rewrap_iter(_OrigIter __orig_iter, _Iter __iter) _NOEXCEPT { return _Impl::__rewrap(std::move(__orig_iter), std::move(__iter)); diff --git a/libcxx/include/__algorithm/unwrap_range.h b/libcxx/include/__algorithm/unwrap_range.h --- a/libcxx/include/__algorithm/unwrap_range.h +++ b/libcxx/include/__algorithm/unwrap_range.h @@ -43,7 +43,7 @@ } _LIBCPP_HIDE_FROM_ABI static constexpr auto - __rewrap(_Iter __orig_iter, decltype(std::__unwrap_iter(__orig_iter)) __iter) + __rewrap(_Iter __orig_iter, decltype(std::__unwrap_iter(std::move(__orig_iter))) __iter) requires random_access_iterator<_Iter> && sized_sentinel_for<_Sent, _Iter> { return std::__rewrap_iter(std::move(__orig_iter), std::move(__iter)); diff --git a/libcxx/include/__functional/identity.h b/libcxx/include/__functional/identity.h --- a/libcxx/include/__functional/identity.h +++ b/libcxx/include/__functional/identity.h @@ -11,6 +11,7 @@ #define _LIBCPP___FUNCTIONAL_IDENTITY_H #include <__config> +#include <__type_traits/integral_constant.h> #include <__utility/forward.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -19,6 +20,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +struct __is_identity : false_type {}; + struct __identity { template _LIBCPP_NODISCARD _LIBCPP_CONSTEXPR _Tp&& operator()(_Tp&& __t) const _NOEXCEPT { @@ -28,6 +32,9 @@ using is_transparent = void; }; +template <> +struct __is_identity<__identity> : true_type {}; + #if _LIBCPP_STD_VER >= 20 struct identity { @@ -39,6 +46,10 @@ using is_transparent = void; }; + +template <> +struct __is_identity : true_type {}; + #endif // _LIBCPP_STD_VER >= 20 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__functional/operations.h b/libcxx/include/__functional/operations.h --- a/libcxx/include/__functional/operations.h +++ b/libcxx/include/__functional/operations.h @@ -13,6 +13,8 @@ #include <__config> #include <__functional/binary_function.h> #include <__functional/unary_function.h> +#include <__type_traits/integral_constant.h> +#include <__type_traits/predicate_traits.h> #include <__utility/forward.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -341,6 +343,14 @@ }; #endif +template +struct __is_trivial_equality_predicate, _Tp, _Tp> : true_type {}; + +#if _LIBCPP_STD_VER >= 14 +template +struct __is_trivial_equality_predicate, _Tp, _Tp> : true_type {}; +#endif + #if _LIBCPP_STD_VER >= 14 template #else diff --git a/libcxx/include/__functional/ranges_operations.h b/libcxx/include/__functional/ranges_operations.h --- a/libcxx/include/__functional/ranges_operations.h +++ b/libcxx/include/__functional/ranges_operations.h @@ -13,6 +13,8 @@ #include <__concepts/equality_comparable.h> #include <__concepts/totally_ordered.h> #include <__config> +#include <__type_traits/integral_constant.h> +#include <__type_traits/predicate_traits.h> #include <__utility/forward.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -93,6 +95,9 @@ } // namespace ranges +template +struct __is_trivial_equality_predicate : true_type {}; + #endif // _LIBCPP_STD_VER >= 20 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__string/constexpr_c_functions.h b/libcxx/include/__string/constexpr_c_functions.h --- a/libcxx/include/__string/constexpr_c_functions.h +++ b/libcxx/include/__string/constexpr_c_functions.h @@ -11,6 +11,8 @@ #include <__config> #include <__type_traits/is_constant_evaluated.h> +#include <__type_traits/is_equality_comparable.h> +#include <__type_traits/is_same.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -33,21 +35,32 @@ return __builtin_strlen(__str); } -template +template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 int -__constexpr_memcmp(const _Tp* __lhs, const _Tp* __rhs, size_t __count) { -#ifdef _LIBCPP_COMPILER_GCC +__constexpr_memcmp(const _Tp* __lhs, const _Up* __rhs, size_t __count) { + static_assert( + __is_trivially_equality_comparable<_Tp, _Up>::value, "_Tp and _Up have to be trivially equality comparable"); + if (__libcpp_is_constant_evaluated()) { - for (; __count; --__count, ++__lhs, ++__rhs) { +#ifdef _LIBCPP_COMPILER_CLANG_BASED + if (sizeof(_Tp) == 1 && !is_same<_Tp, bool>::value) + return __builtin_memcmp(__lhs, __rhs, __count); +#endif + + while (__count != 0) { if (*__lhs < *__rhs) return -1; if (*__rhs < *__lhs) return 1; + + __count -= sizeof(_Tp); + ++__lhs; + ++__rhs; } return 0; + } else { + return __builtin_memcmp(__lhs, __rhs, __count); } -#endif - return __builtin_memcmp(__lhs, __rhs, __count); } inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 const char* diff --git a/libcxx/include/__type_traits/is_equality_comparable.h b/libcxx/include/__type_traits/is_equality_comparable.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__type_traits/is_equality_comparable.h @@ -0,0 +1,62 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___TYPE_TRAITS_IS_EQUAILITY_COMPARABLE_H +#define _LIBCPP___TYPE_TRAITS_IS_EQUAILITY_COMPARABLE_H + +#include <__config> +#include <__type_traits/integral_constant.h> +#include <__type_traits/is_integral.h> +#include <__type_traits/is_same.h> +#include <__type_traits/is_void.h> +#include <__type_traits/remove_cv.h> +#include <__type_traits/void_t.h> +#include <__utility/declval.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct __is_equality_comparable : false_type {}; + +template +struct __is_equality_comparable<_Tp, _Up, __void_t() == std::declval<_Up>())> > : true_type { +}; + +// A type is_trivially_equality_comparable if the expression `a == b` is equivalent to `std::memcmp(&a, &b, sizeof(T))` +// (with `a` and `b` being of type `T`). There is no compiler built-in to check this, so we can only do this for known +// types. In particular, these are the integral types and raw pointers. +// +// The following types are not trivially equality comparable: +// floating-point types: different bit-patterns can compare equal. (e.g 0.0 and -0.0) +// enums: The user is allowed to specialize operator== for enums +// pointers that don't have the same type (ignoring cv-qualifiers): pointers to virtual bases are equality comparable, +// but don't have the same bit-pattern. An exception to this is comparing to a void-pointer. There the bit-pattern is +// always compared. + +template +struct __is_trivially_equality_comparable + : integral_constant::value && is_integral<_Tp>::value && + is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value> {}; + +// TODO: Use is_pointer_inverconvertible_base_of +template +struct __is_trivially_equality_comparable<_Tp*, _Up*> + : integral_constant< + bool, + __is_equality_comparable<_Tp*, _Up*>::value && + (is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value || is_void<_Tp>::value || is_void<_Up>::value)> { +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___TYPE_TRAITS_IS_EQUAILITY_COMPARABLE_H diff --git a/libcxx/include/__type_traits/predicate_traits.h b/libcxx/include/__type_traits/predicate_traits.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__type_traits/predicate_traits.h @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___TYPE_TRAITS_PREDICATE_TRAITS +#define _LIBCPP___TYPE_TRAITS_PREDICATE_TRAITS + +#include <__config> +#include <__type_traits/integral_constant.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct __is_trivial_equality_predicate : false_type {}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___TYPE_TRAITS_PREDICATE_TRAITS diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -604,7 +604,10 @@ module unique { private header "__algorithm/unique.h" } module unique_copy { private header "__algorithm/unique_copy.h" } module unwrap_iter { private header "__algorithm/unwrap_iter.h" } - module unwrap_range { private header "__algorithm/unwrap_range.h" } + module unwrap_range { + private header "__algorithm/unwrap_range.h" + export utility.__utility.pair + } module upper_bound { private header "__algorithm/upper_bound.h" } } } @@ -1491,6 +1494,10 @@ module is_destructible { private header "__type_traits/is_destructible.h" } module is_empty { private header "__type_traits/is_empty.h" } module is_enum { private header "__type_traits/is_enum.h" } + module is_equality_comparable { + private header "__type_traits/is_equality_comparable.h" + export integral_constant + } module is_final { private header "__type_traits/is_final.h" } module is_floating_point { private header "__type_traits/is_floating_point.h" } module is_function { private header "__type_traits/is_function.h" } @@ -1561,6 +1568,7 @@ module nat { private header "__type_traits/nat.h" } module negation { private header "__type_traits/negation.h" } module noexcept_move_assign_container { private header "__type_traits/noexcept_move_assign_container.h" } + module predicate_traits { private header "__type_traits/predicate_traits.h" } module promote { private header "__type_traits/promote.h" } module rank { private header "__type_traits/rank.h" } module remove_all_extents { private header "__type_traits/remove_all_extents.h" } diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -651,6 +651,7 @@ #include <__type_traits/is_destructible.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_destructible.h'}} #include <__type_traits/is_empty.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_empty.h'}} #include <__type_traits/is_enum.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_enum.h'}} +#include <__type_traits/is_equality_comparable.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_equality_comparable.h'}} #include <__type_traits/is_final.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_final.h'}} #include <__type_traits/is_floating_point.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_floating_point.h'}} #include <__type_traits/is_function.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_function.h'}} @@ -715,6 +716,7 @@ #include <__type_traits/nat.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/nat.h'}} #include <__type_traits/negation.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/negation.h'}} #include <__type_traits/noexcept_move_assign_container.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/noexcept_move_assign_container.h'}} +#include <__type_traits/predicate_traits.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/predicate_traits.h'}} #include <__type_traits/promote.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/promote.h'}} #include <__type_traits/rank.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/rank.h'}} #include <__type_traits/remove_all_extents.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/remove_all_extents.h'}} diff --git a/libcxx/test/libcxx/type_traits/is_trivially_comparable.compile.pass.cpp b/libcxx/test/libcxx/type_traits/is_trivially_comparable.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/type_traits/is_trivially_comparable.compile.pass.cpp @@ -0,0 +1,58 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// ADDITIONAL_COMPILE_FLAGS: -Wno-private-header + +#include <__type_traits/is_equality_comparable.h> + +enum Enum : int {}; +enum class EnumClass : int {}; + +static_assert(std::__is_trivially_equality_comparable::value, ""); +static_assert(std::__is_trivially_equality_comparable::value, ""); +static_assert(std::__is_trivially_equality_comparable::value, ""); + +static_assert(std::__is_trivially_equality_comparable::value, ""); +static_assert(std::__is_trivially_equality_comparable::value, ""); +static_assert(!std::__is_trivially_equality_comparable::value, ""); + +static_assert(!std::__is_trivially_equality_comparable::value, ""); +static_assert(!std::__is_trivially_equality_comparable::value, ""); + +static_assert(std::__is_trivially_equality_comparable::value, ""); +static_assert(std::__is_trivially_equality_comparable::value, ""); +static_assert(!std::__is_trivially_equality_comparable::value, ""); + +static_assert(!std::__is_trivially_equality_comparable::value, ""); +static_assert(!std::__is_trivially_equality_comparable::value, ""); + +static_assert(!std::__is_trivially_equality_comparable::value, ""); +static_assert(!std::__is_trivially_equality_comparable::value, ""); + +static_assert(!std::__is_trivially_equality_comparable::value, ""); + +static_assert(!std::__is_trivially_equality_comparable::value, ""); +static_assert(!std::__is_trivially_equality_comparable::value, ""); +static_assert(!std::__is_trivially_equality_comparable::value, ""); + +struct S { + char c; +}; + +struct S2 { + char c; +}; + +struct VirtualBase : virtual S {}; +struct NonVirtualBase : S, S2 {}; + +static_assert(!std::__is_trivially_equality_comparable::value, ""); +static_assert(!std::__is_trivially_equality_comparable::value, ""); + +// This is trivially_equality_comparable, but we can't detect it currently +static_assert(!std::__is_trivially_equality_comparable::value, ""); diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp @@ -20,68 +20,119 @@ #include #include +#include -#include "test_macros.h" #include "test_iterators.h" +#include "test_macros.h" +#include "type_algorithms.h" + +template +struct Test { + template + TEST_CONSTEXPR_CXX20 void operator()() { + UnderlyingType a[] = {0, 1, 2, 3, 4, 5}; + const unsigned s = sizeof(a) / sizeof(a[0]); + UnderlyingType b[s] = {0, 1, 2, 5, 4, 5}; + + assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a))); + assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b))); + +#if TEST_STD_VER >= 14 + assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), std::equal_to<>())); + assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), std::equal_to<>())); + + assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s))); + assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s - 1))); + assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), Iter2(b + s))); -template -void test_equal() { - int a[] = {0, 1, 2, 3, 4, 5}; - const unsigned s = sizeof(a) / sizeof(a[0]); - int b[s] = {0, 1, 2, 5, 4, 5}; + assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s), std::equal_to<>())); + assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s - 1), std::equal_to<>())); + assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), Iter2(b + s), std::equal_to<>())); +#endif + } +}; - assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a))); - assert(std::equal(Iter2(a), Iter2(a + s), Iter1(a))); - assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b))); +struct TestNarrowingEqualTo { + template + TEST_CONSTEXPR_CXX20 void operator()() { + UnderlyingType a[] = { + UnderlyingType(0x1000), + UnderlyingType(0x1001), + UnderlyingType(0x1002), + UnderlyingType(0x1003), + UnderlyingType(0x1004)}; + UnderlyingType b[] = { + UnderlyingType(0x1600), + UnderlyingType(0x1601), + UnderlyingType(0x1602), + UnderlyingType(0x1603), + UnderlyingType(0x1604)}; + assert(std::equal(a, a + 5, b, std::equal_to())); #if TEST_STD_VER >= 14 - assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s))); - assert(std::equal(Iter2(a), Iter2(a + s), Iter1(a), Iter1(a + s))); - assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s - 1))); - assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), Iter2(b + s))); + assert(std::equal(a, a + 5, b, b + 5, std::equal_to())); #endif + } +}; + +template +struct TestIter2 { + template + TEST_CONSTEXPR_CXX20 void operator()() { + meta::for_each(TypeList(), Test()); + } +}; + +struct AddressCompare { + int i = 0; + TEST_CONSTEXPR_CXX20 AddressCompare(int) {} + + operator char() { return static_cast(i); } + + friend TEST_CONSTEXPR_CXX20 bool operator==(const AddressCompare& lhs, const AddressCompare& rhs) { + return &lhs == &rhs; + } + + friend TEST_CONSTEXPR_CXX20 bool operator!=(const AddressCompare& lhs, const AddressCompare& rhs) { + return &lhs != &rhs; + } +}; + +TEST_CONSTEXPR_CXX20 bool test() { + meta::for_each(meta::cpp17_input_iterator_list(), TestIter2 >()); + meta::for_each(meta::cpp17_input_iterator_list(), TestIter2 >()); + meta::for_each(meta::cpp17_input_iterator_list(), + TestIter2 >()); + + meta::for_each(meta::integral_types(), TestNarrowingEqualTo()); + + return true; } -#if TEST_STD_VER > 17 -TEST_CONSTEXPR bool test_constexpr() { - int ia[] = {1, 3, 6, 7}; - int ib[] = {1, 3}; - int ic[] = {1, 3, 5, 7}; - typedef cpp17_input_iterator II; - typedef bidirectional_iterator BI; - - return !std::equal(std::begin(ia), std::end(ia), std::begin(ic)) - && !std::equal(std::begin(ia), std::end(ia), std::begin(ic), std::end(ic)) - && std::equal(std::begin(ib), std::end(ib), std::begin(ic)) - && !std::equal(std::begin(ib), std::end(ib), std::begin(ic), std::end(ic)) - - && std::equal(II(std::begin(ib)), II(std::end(ib)), II(std::begin(ic))) - && !std::equal(BI(std::begin(ib)), BI(std::end(ib)), BI(std::begin(ic)), BI(std::end(ic))) - ; - } +struct Base {}; +struct Derived : virtual Base {}; + +int main(int, char**) { + test(); +#if TEST_STD_VER >= 20 + static_assert(test()); #endif + meta::for_each(meta::as_pointers >(), + TestIter2 > >()); + meta::for_each(meta::as_pointers >(), + TestIter2 > >()); -int main(int, char**) -{ - test_equal >(); - test_equal >(); - - // Test all combinations of cv-qualifiers: - test_equal(); - test_equal(); - test_equal(); - test_equal(); - test_equal(); - test_equal(); - test_equal(); - test_equal(); - test_equal(); - test_equal(); - -#if TEST_STD_VER > 17 - static_assert(test_constexpr()); + { + Derived d; + Derived* a[] = {&d, nullptr}; + Base* b[] = {&d, nullptr}; + + assert(std::equal(a, a + 2, b)); +#if TEST_STD_VER >= 14 + assert(std::equal(a, a + 2, b, b + 2)); #endif + } return 0; } diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp @@ -88,6 +88,21 @@ } } + { // check that false is returned for non-equal ranges + { + int a[] = {1, 2, 3, 4}; + int b[] = {1, 2, 4, 4}; + assert(!std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)))); + } + { + int a[] = {1, 2, 3, 4}; + int b[] = {1, 2, 4, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); + assert(!std::ranges::equal(range1, range2)); + } + } + { // check that the predicate is used (return true) { int a[] = {1, 2, 3, 4}; diff --git a/libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp b/libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp --- a/libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp +++ b/libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp @@ -8,6 +8,11 @@ // +// https://buildkite.com/llvm-project/libcxx-ci/builds/15823#0184fc0b-d56b-4774-9e1d-35fe24e09e37 +// It seems like the CI gcc version is buggy. I can't reproduce the failure on my system or on +// godbolt (https://godbolt.org/z/rsPv8e8fn). +// UNSUPPORTED: gcc-12 + #include #include #include diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -1418,23 +1418,33 @@ requires std::ranges::viewable_range ProxyRange(R&&) -> ProxyRange>; +#endif // TEST_STD_VER > 17 + namespace meta { template -using random_access_iterator_list = type_list, random_access_iterator>; +using random_access_iterator_list = + type_list= 20 + contiguous_iterator, +#endif + random_access_iterator >; template using bidirectional_iterator_list = - concatenate_t, type_list>>; + concatenate_t, type_list > >; + +template +using forward_iterator_list = concatenate_t, type_list > >; template -using forward_iterator_list = concatenate_t, type_list>>; +using cpp17_input_iterator_list = concatenate_t, type_list > >; +#if TEST_STD_VER >= 20 template using cpp20_input_iterator_list = concatenate_t, type_list, cpp17_input_iterator>>; - +#endif } // namespace meta -#endif // TEST_STD_VER > 17 #endif // SUPPORT_TEST_ITERATORS_H diff --git a/libcxx/test/support/type_algorithms.h b/libcxx/test/support/type_algorithms.h --- a/libcxx/test/support/type_algorithms.h +++ b/libcxx/test/support/type_algorithms.h @@ -100,6 +100,20 @@ using floating_point_types = type_list; using arithmetic_types = concatenate_t; + +template +using cv_qualified_versions = type_list; + +template +struct type_list_as_pointers; + +template +struct type_list_as_pointers > { + using type = type_list; +}; + +template +using as_pointers = typename type_list_as_pointers::type; } // namespace meta #endif // TEST_SUPPORT_TYPE_ALGORITHMS_H