diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -159,6 +159,7 @@ set(BENCHMARK_TESTS algorithms.partition_point.bench.cpp algorithms/equal.bench.cpp + algorithms/find.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/find.bench.cpp b/libcxx/benchmarks/algorithms/find.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/find.bench.cpp @@ -0,0 +1,49 @@ +//===----------------------------------------------------------------------===// +// +// 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 +#include + +template +static void bm_find(benchmark::State& state) { + std::vector vec1(state.range(), '1'); + std::mt19937_64 rng(std::random_device{}()); + + for (auto _ : state) { + auto idx = rng() % vec1.size(); + vec1[idx] = '2'; + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize(std::find(vec1.begin(), vec1.end(), T('2'))); + vec1[idx] = '1'; + } +} +BENCHMARK(bm_find)->DenseRange(1, 8)->Range(16, 1 << 20); +BENCHMARK(bm_find)->DenseRange(1, 8)->Range(16, 1 << 20); +BENCHMARK(bm_find)->DenseRange(1, 8)->Range(16, 1 << 20); + +template +static void bm_ranges_find(benchmark::State& state) { + std::vector vec1(state.range(), '1'); + std::mt19937_64 rng(std::random_device{}()); + + for (auto _ : state) { + auto idx = rng() % vec1.size(); + vec1[idx] = '2'; + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize(std::ranges::find(vec1, T('2'))); + vec1[idx] = '1'; + } +} +BENCHMARK(bm_ranges_find)->DenseRange(1, 8)->Range(16, 1 << 20); +BENCHMARK(bm_ranges_find)->DenseRange(1, 8)->Range(16, 1 << 20); +BENCHMARK(bm_ranges_find)->DenseRange(1, 8)->Range(16, 1 << 20); + +BENCHMARK_MAIN(); diff --git a/libcxx/include/__algorithm/find.h b/libcxx/include/__algorithm/find.h --- a/libcxx/include/__algorithm/find.h +++ b/libcxx/include/__algorithm/find.h @@ -10,7 +10,16 @@ #ifndef _LIBCPP___ALGORITHM_FIND_H #define _LIBCPP___ALGORITHM_FIND_H +#include <__algorithm/unwrap_iter.h> #include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__string/constexpr_c_functions.h> +#include <__type_traits/is_same.h> + +#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS +# include +#endif #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -18,15 +27,51 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _InputIterator -find(_InputIterator __first, _InputIterator __last, const _Tp& __value) { +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter +__find_impl(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) { for (; __first != __last; ++__first) - if (*__first == __value) + if (std::__invoke(__proj, *__first) == __value) break; return __first; } +template ::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value && + sizeof(_Tp) == 1, + int> = 0> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* +__find_impl(_Tp* __first, _Tp* __last, const _Up& __value, _Proj&) { + if (auto __ret = std::__constexpr_memchr(__first, __value, __last - __first)) + return __ret; + return __last; +} + +#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS +template ::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value && + sizeof(_Tp) == sizeof(wchar_t) && _LIBCPP_ALIGNOF(_Tp) >= _LIBCPP_ALIGNOF(wchar_t), + int> = 0> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* +__find_impl(_Tp* __first, _Tp* __last, const _Up& __value, _Proj&) { + if (auto __ret = std::__constexpr_wmemchr(__first, __value, __last - __first)) + return __ret; + return __last; +} +#endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _InputIterator +find(_InputIterator __first, _InputIterator __last, const _Tp& __value) { + __identity __proj; + return std::__rewrap_iter( + __first, std::__find_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __value, __proj)); +} + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ALGORITHM_FIND_H diff --git a/libcxx/include/__algorithm/ranges_find.h b/libcxx/include/__algorithm/ranges_find.h --- a/libcxx/include/__algorithm/ranges_find.h +++ b/libcxx/include/__algorithm/ranges_find.h @@ -9,7 +9,9 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_FIND_H #define _LIBCPP___ALGORITHM_RANGES_FIND_H +#include <__algorithm/find.h> #include <__algorithm/ranges_find_if.h> +#include <__algorithm/unwrap_range.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> @@ -33,20 +35,30 @@ namespace ranges { namespace __find { struct __fn { + template + _LIBCPP_HIDE_FROM_ABI static constexpr _Iter + __find_unwrap(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) { + if constexpr (forward_iterator<_Iter>) { + auto [__first_un, __last_un] = std::__unwrap_range(__first, std::move(__last)); + return std::__rewrap_range<_Sent>( + std::move(__first), std::__find_impl(std::move(__first_un), std::move(__last_un), __value, __proj)); + } else { + return std::__find_impl(std::move(__first), std::move(__last), __value, __proj); + } + } + template _Sp, class _Tp, class _Proj = identity> requires indirect_binary_predicate, const _Tp*> _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const { - auto __pred = [&](auto&& __e) { return std::forward(__e) == __value; }; - return ranges::__find_if_impl(std::move(__first), std::move(__last), __pred, __proj); + return __find_unwrap(std::move(__first), std::move(__last), __value, __proj); } template requires indirect_binary_predicate, _Proj>, const _Tp*> _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const { - auto __pred = [&](auto&& __e) { return std::forward(__e) == __value; }; - return ranges::__find_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + return __find_unwrap(ranges::begin(__r), ranges::end(__r), __value, __proj); } }; } // namespace __find diff --git a/libcxx/include/__string/char_traits.h b/libcxx/include/__string/char_traits.h --- a/libcxx/include/__string/char_traits.h +++ b/libcxx/include/__string/char_traits.h @@ -244,7 +244,7 @@ const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { if (__n == 0) return nullptr; - return std::__constexpr_char_memchr(__s, static_cast(__a), __n); + return std::__constexpr_memchr(__s, __a, __n); } static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 @@ -14,6 +14,7 @@ #include <__type_traits/is_equality_comparable.h> #include <__type_traits/is_same.h> #include <__type_traits/is_trivially_lexicographically_comparable.h> +#include <__type_traits/remove_cv.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -95,20 +96,29 @@ } } -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 const char* -__constexpr_char_memchr(const char* __str, int __char, size_t __count) { -#if __has_builtin(__builtin_char_memchr) - return __builtin_char_memchr(__str, __char, __count); -#else - if (!__libcpp_is_constant_evaluated()) - return static_cast(__builtin_memchr(__str, __char, __count)); - for (; __count; --__count) { - if (*__str == __char) - return __str; - ++__str; - } - return nullptr; +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __constexpr_memchr(_Tp* __str, _Up __value, size_t __count) { + static_assert(sizeof(_Tp) == 1 && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value, + "Calling memchr on non-trivially equality comparable types is unsafe."); + + if (__libcpp_is_constant_evaluated()) { +// use __builtin_char_memchr to optimize constexpr evaluation if we can +#if _LIBCPP_STD_VER >= 17 && __has_builtin(__builtin_char_memchr) + if constexpr (is_same_v, char> && is_same_v, char>) + return __builtin_char_memchr(__str, __value, __count); #endif + + for (; __count; --__count) { + if (*__str == __value) + return __str; + ++__str; + } + return nullptr; + } else { + char __value_buffer; + __builtin_memcpy(&__value_buffer, &__value, sizeof(char)); + return static_cast<_Tp*>(__builtin_memchr(__str, __value_buffer, __count)); + } } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/cwchar b/libcxx/include/cwchar --- a/libcxx/include/cwchar +++ b/libcxx/include/cwchar @@ -104,7 +104,11 @@ #include <__assert> // all public C++ headers provide the assertion handler #include <__config> +#include <__type_traits/apply_cv.h> #include <__type_traits/is_constant_evaluated.h> +#include <__type_traits/is_equality_comparable.h> +#include <__type_traits/is_same.h> +#include <__type_traits/remove_cv.h> #include #include @@ -222,21 +226,31 @@ #endif } -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 const wchar_t* -__constexpr_wmemchr(const wchar_t* __str, wchar_t __char, size_t __count) { -#if __has_feature(cxx_constexpr_string_builtins) - return __builtin_wmemchr(__str, __char, __count); -#else - if (!__libcpp_is_constant_evaluated()) - return std::wmemchr(__str, __char, __count); +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __constexpr_wmemchr(_Tp* __str, _Up __value, size_t __count) { + static_assert(sizeof(_Tp) == sizeof(wchar_t)&& _LIBCPP_ALIGNOF(_Tp) >= _LIBCPP_ALIGNOF(wchar_t) && + __libcpp_is_trivially_equality_comparable<_Tp, _Tp>::value, + "Calling wmemchr on non-trivially equality comparable types is unsafe."); + +#if __has_builtin(__builtin_wmemchr) + if (!__libcpp_is_constant_evaluated()) { + wchar_t __value_buffer = 0; + __builtin_memcpy(&__value_buffer, &__value, sizeof(wchar_t)); + return reinterpret_cast<_Tp*>( + __builtin_wmemchr(reinterpret_cast<__apply_cv_t<_Tp, wchar_t>*>(__str), __value_buffer, __count)); + } +# if _LIBCPP_STD_VER >= 17 + else if constexpr (is_same_v, wchar_t>) + return __builtin_wmemchr(__str, __value, __count); +# endif +#endif // __has_builtin(__builtin_wmemchr) for (; __count; --__count) { - if (*__str == __char) + if (*__str == __value) return __str; ++__str; } return nullptr; -#endif } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/test/libcxx/strings/c.strings/constexpr.cstring.compile.pass.cpp b/libcxx/test/libcxx/strings/c.strings/constexpr.cstring.compile.pass.cpp --- a/libcxx/test/libcxx/strings/c.strings/constexpr.cstring.compile.pass.cpp +++ b/libcxx/test/libcxx/strings/c.strings/constexpr.cstring.compile.pass.cpp @@ -29,6 +29,6 @@ constexpr bool test_constexpr_wmemchr() { const char str[] = "Banane"; - return std::__constexpr_char_memchr(str, 'n', 6) == str + 2; + return std::__constexpr_memchr(str, 'n', 6) == str + 2; } static_assert(test_constexpr_wmemchr(), ""); diff --git a/libcxx/test/libcxx/transitive_includes/cxx03.csv b/libcxx/test/libcxx/transitive_includes/cxx03.csv --- a/libcxx/test/libcxx/transitive_includes/cxx03.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx03.csv @@ -7,6 +7,7 @@ algorithm cstdlib algorithm cstring algorithm ctime +algorithm cwchar algorithm execution algorithm initializer_list algorithm iosfwd @@ -191,6 +192,7 @@ cstddef version ctgmath ccomplex ctgmath cmath +cwchar cstddef cwchar cwctype cwctype cctype deque algorithm @@ -201,6 +203,7 @@ deque cstdint deque cstdlib deque cstring +deque cwchar deque functional deque initializer_list deque iosfwd @@ -944,6 +947,7 @@ vector cstdint vector cstdlib vector cstring +vector cwchar vector initializer_list vector iosfwd vector limits diff --git a/libcxx/test/libcxx/transitive_includes/cxx11.csv b/libcxx/test/libcxx/transitive_includes/cxx11.csv --- a/libcxx/test/libcxx/transitive_includes/cxx11.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx11.csv @@ -7,6 +7,7 @@ algorithm cstdlib algorithm cstring algorithm ctime +algorithm cwchar algorithm execution algorithm initializer_list algorithm iosfwd @@ -191,6 +192,7 @@ cstddef version ctgmath ccomplex ctgmath cmath +cwchar cstddef cwchar cwctype cwctype cctype deque algorithm @@ -201,6 +203,7 @@ deque cstdint deque cstdlib deque cstring +deque cwchar deque functional deque initializer_list deque iosfwd @@ -945,6 +948,7 @@ vector cstdint vector cstdlib vector cstring +vector cwchar vector initializer_list vector iosfwd vector limits diff --git a/libcxx/test/libcxx/transitive_includes/cxx14.csv b/libcxx/test/libcxx/transitive_includes/cxx14.csv --- a/libcxx/test/libcxx/transitive_includes/cxx14.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx14.csv @@ -191,6 +191,7 @@ cstddef version ctgmath ccomplex ctgmath cmath +cwchar cstddef cwchar cwctype cwctype cctype deque algorithm @@ -201,6 +202,7 @@ deque cstdint deque cstdlib deque cstring +deque cwchar deque functional deque initializer_list deque iosfwd @@ -650,6 +652,7 @@ ranges compare ranges cstddef ranges cstdlib +ranges cwchar ranges initializer_list ranges iosfwd ranges iterator @@ -947,6 +950,7 @@ vector cstdint vector cstdlib vector cstring +vector cwchar vector initializer_list vector iosfwd vector limits diff --git a/libcxx/test/libcxx/transitive_includes/cxx17.csv b/libcxx/test/libcxx/transitive_includes/cxx17.csv --- a/libcxx/test/libcxx/transitive_includes/cxx17.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx17.csv @@ -191,6 +191,7 @@ cstddef version ctgmath ccomplex ctgmath cmath +cwchar cstddef cwchar cwctype cwctype cctype deque algorithm @@ -201,6 +202,7 @@ deque cstdint deque cstdlib deque cstring +deque cwchar deque functional deque initializer_list deque iosfwd @@ -650,6 +652,7 @@ ranges compare ranges cstddef ranges cstdlib +ranges cwchar ranges initializer_list ranges iosfwd ranges iterator @@ -947,6 +950,7 @@ vector cstdint vector cstdlib vector cstring +vector cwchar vector initializer_list vector iosfwd vector limits diff --git a/libcxx/test/libcxx/transitive_includes/cxx20.csv b/libcxx/test/libcxx/transitive_includes/cxx20.csv --- a/libcxx/test/libcxx/transitive_includes/cxx20.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx20.csv @@ -7,6 +7,7 @@ algorithm cstdlib algorithm cstring algorithm ctime +algorithm cwchar algorithm execution algorithm initializer_list algorithm iosfwd @@ -198,6 +199,7 @@ cstddef version ctgmath ccomplex ctgmath cmath +cwchar cstddef cwchar cwctype cwctype cctype deque algorithm @@ -208,6 +210,7 @@ deque cstdint deque cstdlib deque cstring +deque cwchar deque functional deque initializer_list deque iosfwd @@ -952,6 +955,7 @@ vector cstdint vector cstdlib vector cstring +vector cwchar vector initializer_list vector iosfwd vector limits diff --git a/libcxx/test/libcxx/transitive_includes/cxx2b.csv b/libcxx/test/libcxx/transitive_includes/cxx2b.csv --- a/libcxx/test/libcxx/transitive_includes/cxx2b.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx2b.csv @@ -3,6 +3,7 @@ algorithm cstdint algorithm cstring algorithm ctime +algorithm cwchar algorithm execution algorithm initializer_list algorithm iosfwd @@ -127,12 +128,14 @@ cstddef version ctgmath ccomplex ctgmath cmath +cwchar cstddef cwchar cwctype cwctype cctype deque compare deque cstddef deque cstdint deque cstring +deque cwchar deque initializer_list deque limits deque new @@ -436,6 +439,7 @@ random version ranges compare ranges cstddef +ranges cwchar ranges initializer_list ranges iosfwd ranges iterator @@ -634,6 +638,7 @@ vector cstdint vector cstdlib vector cstring +vector cwchar vector initializer_list vector iosfwd vector limits diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find.pass.cpp --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find.pass.cpp @@ -6,6 +6,8 @@ // //===----------------------------------------------------------------------===// +// ADDITIONAL_COMPILE_FLAGS: -Wno-sign-compare + // // template @@ -15,33 +17,122 @@ #include #include +#include +#include #include "test_macros.h" #include "test_iterators.h" +#include "type_algorithms.h" + +static std::vector comparable_data; + +template +struct Test { + template + TEST_CONSTEXPR_CXX20 void operator()() { + ArrayT arr[] = { + ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(8), ArrayT(9), ArrayT(10)}; + + static_assert(std::is_same::value, ""); + + { // first element matches + Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(1)); + assert(*iter == ArrayT(1)); + assert(base(iter) == arr); + } + + { // range is empty; return last + Iter iter = std::find(Iter(arr), Iter(arr), CompareT(1)); + assert(base(iter) == arr); + } + + { // if multiple elements match, return the first match + ArrayT data[] = { + ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(5), ArrayT(4)}; + Iter iter = std::find(Iter(std::begin(data)), Iter(std::end(data)), CompareT(5)); + assert(*iter == ArrayT(5)); + assert(base(iter) == data + 4); + } + + { // some element matches + Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(6)); + assert(*iter == ArrayT(6)); + assert(base(iter) == arr + 5); + } + + { // last element matches + Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(10)); + assert(*iter == ArrayT(10)); + assert(base(iter) == arr + 9); + } -#if TEST_STD_VER > 17 -TEST_CONSTEXPR bool test_constexpr() { - int ia[] = {1, 3, 5, 2, 4, 6}; - int ib[] = {1, 2, 3, 4, 5, 6}; - return (std::find(std::begin(ia), std::end(ia), 5) == ia+2) - && (std::find(std::begin(ib), std::end(ib), 9) == ib+6) - ; + { // if no element matches, last is returned + Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(20)); + assert(base(iter) == arr + 10); } + + if (!TEST_IS_CONSTANT_EVALUATED) + comparable_data.clear(); + } +}; + +template +class Comparable { + IndexT index_; + + static IndexT init_index(IndexT i) { + IndexT size = static_cast(comparable_data.size()); + comparable_data.push_back(i); + return size; + } + +public: + Comparable(IndexT i) : index_(init_index(i)) {} + + friend bool operator==(const Comparable& lhs, const Comparable& rhs) { + return comparable_data[lhs.index_] == comparable_data[rhs.index_]; + } +}; + +#if TEST_STD_VER >= 20 +template +class TriviallyComparable { + ElementT el_; + +public: + explicit constexpr TriviallyComparable(ElementT el) : el_(el) {} + bool operator==(const TriviallyComparable&) const = default; +}; #endif -int main(int, char**) -{ - int ia[] = {0, 1, 2, 3, 4, 5}; - const unsigned s = sizeof(ia)/sizeof(ia[0]); - cpp17_input_iterator r = std::find(cpp17_input_iterator(ia), - cpp17_input_iterator(ia+s), 3); - assert(*r == 3); - r = std::find(cpp17_input_iterator(ia), cpp17_input_iterator(ia+s), 10); - assert(r == cpp17_input_iterator(ia+s)); - -#if TEST_STD_VER > 17 - static_assert(test_constexpr()); +template +struct TestTypes { + template + TEST_CONSTEXPR_CXX20 void operator()() { + types::for_each(types::cpp17_input_iterator_list(), Test()); + } +}; + +TEST_CONSTEXPR_CXX20 bool test() { + types::for_each(types::integer_types(), TestTypes()); + types::for_each(types::integer_types(), TestTypes()); + types::for_each(types::integer_types(), TestTypes()); +#if TEST_STD_VER >= 20 + Test, TriviallyComparable>().operator()*>(); + Test, TriviallyComparable>().operator()*>(); +#endif + + return true; +} + +int main(int, char**) { + test(); +#if TEST_STD_VER >= 20 + static_assert(test()); #endif + Test, Comparable >().operator()*>(); + Test, Comparable >().operator()*>(); + return 0; } diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp @@ -8,6 +8,8 @@ // +// ADDITIONAL_COMPILE_FLAGS: -Wno-sign-compare + // UNSUPPORTED: c++03, c++11, c++14, c++17 // template S, class T, class Proj = identity> @@ -22,6 +24,7 @@ #include #include #include +#include #include "almost_satisfies_types.h" #include "boolean_testable.h" @@ -53,65 +56,78 @@ static_assert(!HasFindR); static_assert(!HasFindR); +static std::vector comparable_data; + template constexpr void test_iterators() { - { - int a[] = {1, 2, 3, 4}; - std::same_as auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4); - assert(base(ret) == a + 3); - assert(*ret == 4); - } - { - int a[] = {1, 2, 3, 4}; - auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); - std::same_as auto ret = std::ranges::find(range, 4); - assert(base(ret) == a + 3); - assert(*ret == 4); + using ValueT = std::iter_value_t; + { // simple test + { + ValueT a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4); + assert(base(ret) == a + 3); + assert(*ret == 4); + } + { + ValueT a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = std::ranges::find(range, 4); + assert(base(ret) == a + 3); + assert(*ret == 4); + } } -} -struct OneWayComparable { - bool isLeft; - friend constexpr bool operator==(OneWayComparable l, OneWayComparable) { return l.isLeft; } -}; - -struct NonConstComparableLValue { - friend constexpr bool operator==(const NonConstComparableLValue&, const NonConstComparableLValue&) { return false; } - friend constexpr bool operator==(NonConstComparableLValue&, NonConstComparableLValue&) { return false; } - friend constexpr bool operator==(const NonConstComparableLValue&, NonConstComparableLValue&) { return false; } - friend constexpr bool operator==(NonConstComparableLValue&, const NonConstComparableLValue&) { return true; } -}; - -struct NonConstComparableRValue { - friend constexpr bool operator==(const NonConstComparableRValue&, const NonConstComparableRValue&) { return false; } - friend constexpr bool operator==(const NonConstComparableRValue&&, const NonConstComparableRValue&&) { return false; } - friend constexpr bool operator==(NonConstComparableRValue&&, NonConstComparableRValue&&) { return false; } - friend constexpr bool operator==(NonConstComparableRValue&&, const NonConstComparableRValue&) { return true; } -}; - -constexpr bool test() { - test_iterators(); - test_iterators(); - test_iterators, sentinel_wrapper>>(); - test_iterators>(); - test_iterators>(); - test_iterators>(); - test_iterators>(); + { // check that an empty range works + { + std::array a = {}; + auto ret = std::ranges::find(It(a.data()), Sent(It(a.data())), 1); + assert(base(ret) == a.data()); + } + { + std::array a = {}; + auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data()))); + auto ret = std::ranges::find(range, 1); + assert(base(ret) == a.data()); + } + } - { - // check that projections are used properly and that they are called with the iterator directly + { // check that last is returned with no match { - int a[] = {1, 2, 3, 4}; - auto ret = std::ranges::find(a, a + 4, a + 3, [](int& i) { return &i; }); + ValueT a[] = {1, 1, 1}; + auto ret = std::ranges::find(a, a + 3, 0); assert(ret == a + 3); } { - int a[] = {1, 2, 3, 4}; - auto ret = std::ranges::find(a, a + 3, [](int& i) { return &i; }); + ValueT a[] = {1, 1, 1}; + auto ret = std::ranges::find(a, 0); assert(ret == a + 3); } } + if (!std::is_constant_evaluated()) + comparable_data.clear(); +} + +template +class TriviallyComparable { + ElementT el_; + +public: + TEST_CONSTEXPR TriviallyComparable(ElementT el) : el_(el) {} + bool operator==(const TriviallyComparable&) const = default; +}; + +constexpr bool test() { + types::for_each(types::type_list, TriviallyComparable>{}, + [] { + types::for_each(types::cpp20_input_iterator_list{}, [] { + if constexpr (std::forward_iterator) + test_iterators(); + test_iterators>(); + test_iterators>(); + }); + }); + { // check that the first element is returned { struct S { @@ -137,25 +153,6 @@ } } - { // check that end + 1 iterator is returned with no match - { - int a[] = {1, 1, 1}; - auto ret = std::ranges::find(a, a + 3, 0); - assert(ret == a + 3); - } - { - int a[] = {1, 1, 1}; - auto ret = std::ranges::find(a, 0); - assert(ret == a + 3); - } - } - - { - // check that ranges::dangling is returned - [[maybe_unused]] std::same_as auto ret = - std::ranges::find(std::array{1, 2}, 3); - } - { // check that an iterator is returned with a borrowing range int a[] = {1, 2, 3, 4}; @@ -164,14 +161,6 @@ assert(*ret == 1); } - { - // check that std::invoke is used - struct S { int i; }; - S a[] = { S{1}, S{3}, S{2} }; - std::same_as auto ret = std::ranges::find(a, 4, &S::i); - assert(ret == a + 3); - } - { // count invocations of the projection { @@ -192,81 +181,45 @@ } } - { - // check comparison order - { - OneWayComparable a[] = { OneWayComparable{true} }; - auto ret = std::ranges::find(a, a + 1, OneWayComparable{false}); - assert(ret == a); - } - { - OneWayComparable a[] = { OneWayComparable{true} }; - auto ret = std::ranges::find(a, OneWayComparable{false}); - assert(ret == a); - } - } + return true; +} - { - // check that the return type of `iter::operator*` doesn't change - { - NonConstComparableLValue a[] = { NonConstComparableLValue{} }; - auto ret = std::ranges::find(a, a + 1, NonConstComparableLValue{}); - assert(ret == a); - } - { - using It = std::move_iterator; - NonConstComparableRValue a[] = { NonConstComparableRValue{} }; - auto ret = std::ranges::find(It(a), It(a + 1), NonConstComparableRValue{}); - assert(ret.base() == a); - } - { - NonConstComparableLValue a[] = { NonConstComparableLValue{} }; - auto ret = std::ranges::find(a, NonConstComparableLValue{}); - assert(ret == a); - } - { - using It = std::move_iterator; - NonConstComparableRValue a[] = { NonConstComparableRValue{} }; - auto range = std::ranges::subrange(It(a), It(a + 1)); - auto ret = std::ranges::find(range, NonConstComparableRValue{}); - assert(ret.base() == a); - } - } +template +class Comparable { + IndexT index_; - { - // check that an empty range works - { - std::array a = {}; - auto ret = std::ranges::find(a.begin(), a.end(), 1); - assert(ret == a.begin()); - } - { - std::array a = {}; - auto ret = std::ranges::find(a, 1); - assert(ret == a.begin()); - } - } +public: + Comparable(IndexT i) + : index_([&]() { + IndexT size = static_cast(comparable_data.size()); + comparable_data.push_back(i); + return size; + }()) {} - { - // check that the implicit conversion to bool works - { - StrictComparable a[] = {1, 2, 3, 4}; - auto ret = std::ranges::find(a, a + 4, StrictComparable{2}); - assert(ret == a + 1); - } - { - StrictComparable a[] = {1, 2, 3, 4}; - auto ret = std::ranges::find(a, StrictComparable{2}); - assert(ret == a + 1); - } + bool operator==(const Comparable& other) const { + return comparable_data[other.index_] == comparable_data[index_]; } - return true; -} + friend bool operator==(const Comparable& lhs, long long rhs) { return comparable_data[lhs.index_] == rhs; } +}; int main(int, char**) { test(); static_assert(test()); + types::for_each(types::cpp20_input_iterator_list*>{}, [] { + if constexpr (std::forward_iterator) + test_iterators(); + test_iterators>(); + test_iterators>(); + }); + + types::for_each(types::cpp20_input_iterator_list*>{}, [] { + if constexpr (std::forward_iterator) + test_iterators(); + test_iterators>(); + test_iterators>(); + }); + return 0; } 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 @@ -95,7 +95,9 @@ #endif >; -using integral_types = concatenate_t >; +using integer_types = concatenate_t; + +using integral_types = concatenate_t >; using floating_point_types = type_list;