388 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11// UNSUPPORTED: c++03, c++11, c++14, c++1712 13// ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare14// MSVC warning C4242: 'argument': conversion from 'const _Ty' to 'ElementT', possible loss of data15// MSVC warning C4244: 'argument': conversion from 'const _Ty' to 'ElementT', possible loss of data16// ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4242 /wd424417// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000018// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=8000000019 20// template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>21// requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>22// constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});23// template<input_range R, class T, class Proj = identity>24// requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>25// constexpr borrowed_iterator_t<R>26// ranges::find(R&& r, const T& value, Proj proj = {});27 28#include <algorithm>29#include <array>30#include <cassert>31#include <cstddef>32#include <deque>33#include <ranges>34#include <vector>35 36#include "almost_satisfies_types.h"37#include "sized_allocator.h"38#include "test_iterators.h"39 40struct NotEqualityComparable {};41 42template <class It, class Sent = It>43concept HasFindIt = requires(It it, Sent sent) { std::ranges::find(it, sent, *it); };44static_assert(HasFindIt<int*>);45static_assert(!HasFindIt<NotEqualityComparable*>);46static_assert(!HasFindIt<InputIteratorNotDerivedFrom>);47static_assert(!HasFindIt<InputIteratorNotIndirectlyReadable>);48static_assert(!HasFindIt<InputIteratorNotInputOrOutputIterator>);49static_assert(!HasFindIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);50static_assert(!HasFindIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);51 52static_assert(!HasFindIt<int*, int>);53static_assert(!HasFindIt<int, int*>);54 55template <class Range, class ValT>56concept HasFindR = requires(Range r) { std::ranges::find(r, ValT{}); };57static_assert(HasFindR<std::array<int, 1>, int>);58static_assert(!HasFindR<int, int>);59static_assert(!HasFindR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>);60static_assert(!HasFindR<InputRangeNotDerivedFrom, int>);61static_assert(!HasFindR<InputRangeNotIndirectlyReadable, int>);62static_assert(!HasFindR<InputRangeNotInputOrOutputIterator, int>);63static_assert(!HasFindR<InputRangeNotSentinelSemiregular, int>);64static_assert(!HasFindR<InputRangeNotSentinelEqualityComparableWith, int>);65 66static std::vector<int> comparable_data;67 68template <class It, class Sent = It>69constexpr void test_iterators() {70 using ValueT = std::iter_value_t<It>;71 { // simple test72 {73 ValueT a[] = {1, 2, 3, 4};74 std::same_as<It> auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4);75 assert(base(ret) == a + 3);76 assert(*ret == 4);77 }78 {79 ValueT a[] = {1, 2, 3, 4};80 auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));81 std::same_as<It> auto ret = std::ranges::find(range, 4);82 assert(base(ret) == a + 3);83 assert(*ret == 4);84 }85 }86 87 { // check that an empty range works88 {89 std::array<ValueT, 0> a = {};90 auto ret = std::ranges::find(It(a.data()), Sent(It(a.data())), 1);91 assert(base(ret) == a.data());92 }93 {94 std::array<ValueT, 0> a = {};95 auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data())));96 auto ret = std::ranges::find(range, 1);97 assert(base(ret) == a.data());98 }99 }100 101 { // check that last is returned with no match102 {103 ValueT a[] = {1, 1, 1};104 auto ret = std::ranges::find(a, a + 3, 0);105 assert(ret == a + 3);106 }107 {108 ValueT a[] = {1, 1, 1};109 auto ret = std::ranges::find(a, 0);110 assert(ret == a + 3);111 }112 }113 114 if (!std::is_constant_evaluated())115 comparable_data.clear();116}117 118template <class ElementT>119class TriviallyComparable {120 ElementT el_;121 122public:123 TEST_CONSTEXPR TriviallyComparable(ElementT el) : el_(el) {}124 bool operator==(const TriviallyComparable&) const = default;125};126 127constexpr bool test() {128 types::for_each(types::type_list<char, wchar_t, int, long, TriviallyComparable<char>, TriviallyComparable<wchar_t>>{},129 []<class T> {130 types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> {131 if constexpr (std::forward_iterator<Iter>)132 test_iterators<Iter>();133 test_iterators<Iter, sentinel_wrapper<Iter>>();134 test_iterators<Iter, sized_sentinel<Iter>>();135 });136 });137 138#if TEST_STD_VER >= 20139 {140 std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};141 auto view = vec | std::views::join;142 assert(std::ranges::find(view.begin(), view.end(), 4) == std::next(view.begin(), 3));143 assert(std::ranges::find(view, 4) == std::next(view.begin(), 3));144 }145#endif146 147 { // check that the first element is returned148 {149 struct S {150 int comp;151 int other;152 };153 S a[] = {{0, 0}, {0, 2}, {0, 1}};154 auto ret = std::ranges::find(a, 0, &S::comp);155 assert(ret == a);156 assert(ret->comp == 0);157 assert(ret->other == 0);158 }159 {160 struct S {161 int comp;162 int other;163 };164 S a[] = {{0, 0}, {0, 2}, {0, 1}};165 auto ret = std::ranges::find(a, a + 3, 0, &S::comp);166 assert(ret == a);167 assert(ret->comp == 0);168 assert(ret->other == 0);169 }170 }171 172 {173 // check that an iterator is returned with a borrowing range174 int a[] = {1, 2, 3, 4};175 std::same_as<int*> auto ret = std::ranges::find(std::views::all(a), 1);176 assert(ret == a);177 assert(*ret == 1);178 }179 180 {181 // count invocations of the projection182 {183 int a[] = {1, 2, 3, 4};184 int projection_count = 0;185 auto ret = std::ranges::find(a, a + 4, 2, [&](int i) {186 ++projection_count;187 return i;188 });189 assert(ret == a + 1);190 assert(*ret == 2);191 assert(projection_count == 2);192 }193 {194 int a[] = {1, 2, 3, 4};195 int projection_count = 0;196 auto ret = std::ranges::find(a, 2, [&](int i) {197 ++projection_count;198 return i;199 });200 assert(ret == a + 1);201 assert(*ret == 2);202 assert(projection_count == 2);203 }204 }205 206 {207 // Test vector<bool>::iterator optimization208 std::vector<bool> vec(256 + 8);209 for (ptrdiff_t i = 8; i <= 256; i *= 2) {210 for (size_t offset = 0; offset < 8; offset += 2) {211 std::fill(vec.begin(), vec.end(), false);212 std::fill(vec.begin() + offset, vec.begin() + i + offset, true);213 214 // check both range and iterator-sentinel overloads215 assert(std::ranges::find(vec, true) == std::ranges::begin(vec) + offset);216 assert(std::ranges::find(std::ranges::begin(vec) + offset, std::ranges::end(vec), false) ==217 std::ranges::begin(vec) + offset + i);218 }219 }220 221 // Verify that the std::vector<bool>::iterator optimization works properly for allocators with custom size types222 // See https://llvm.org/PR122528223 {224 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;225 std::vector<bool, Alloc> in(100, false, Alloc(1));226 in[in.size() - 2] = true;227 assert(std::ranges::find(in, true) == in.end() - 2);228 }229 {230 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;231 std::vector<bool, Alloc> in(199, false, Alloc(1));232 in[in.size() - 2] = true;233 assert(std::ranges::find(in, true) == in.end() - 2);234 }235 {236 using Alloc = sized_allocator<bool, unsigned short, short>;237 std::vector<bool, Alloc> in(200, false, Alloc(1));238 in[in.size() - 2] = true;239 assert(std::ranges::find(in, true) == in.end() - 2);240 }241 {242 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;243 std::vector<bool, Alloc> in(205, false, Alloc(1));244 in[in.size() - 2] = true;245 assert(std::ranges::find(in, true) == in.end() - 2);246 }247 {248 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;249 std::vector<bool, Alloc> in(257, false, Alloc(1));250 in[in.size() - 2] = true;251 assert(std::ranges::find(in, true) == in.end() - 2);252 }253 }254 255 return true;256}257 258template <class IndexT>259class Comparable {260 IndexT index_;261 262public:263 Comparable(IndexT i)264 : index_([&]() {265 IndexT size = static_cast<IndexT>(comparable_data.size());266 comparable_data.push_back(i);267 return size;268 }()) {}269 270 bool operator==(const Comparable& other) const { return comparable_data[other.index_] == comparable_data[index_]; }271 272 friend bool operator==(const Comparable& lhs, long long rhs) { return comparable_data[lhs.index_] == rhs; }273};274 275void test_segmented_iterator_types() {276 // Test the optimized find algorithm for types that implement the segment iterator trait277 // deque278 {279 { // empty deque280 std::deque<int> data;281 assert(std::ranges::find(data, 4) == data.end());282 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end());283 }284 285 { // single element - match286 std::deque<int> data = {4};287 assert(std::ranges::find(data, 4) == data.begin());288 assert(std::ranges::find(data.begin(), data.end(), 4) == data.begin());289 }290 291 { // single element - no match292 std::deque<int> data = {3};293 assert(std::ranges::find(data, 4) == data.end());294 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end());295 }296 297 // many elements298 for (auto size : {2, 3, 1023, 1024, 1025, 2047, 2048, 2049}) {299 { // last element match300 std::deque<int> data;301 data.resize(size);302 std::fill(data.begin(), data.end(), 3);303 data[size - 1] = 4;304 assert(std::ranges::find(data, 4) == data.end() - 1);305 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end() - 1);306 }307 308 { // second-last element match309 std::deque<int> data;310 data.resize(size);311 std::fill(data.begin(), data.end(), 3);312 data[size - 2] = 4;313 assert(std::ranges::find(data, 4) == data.end() - 2);314 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end() - 2);315 }316 317 { // no match318 std::deque<int> data;319 data.resize(size);320 std::fill(data.begin(), data.end(), 3);321 assert(std::ranges::find(data, 4) == data.end());322 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end());323 }324 }325 }326 // join_view ranges adaptor327 {328 { // single element - match329 int data[1][1] = {{4}};330 auto joined = std::views::join(data);331 assert(std::ranges::find(joined, 4) == std::ranges::begin(joined));332 }333 { // single element - no match334 // (reproducer for https://llvm.org/PR158279, where the iterator would never reach the end sentinel)335 int data[1][1] = {{3}};336 auto joined = std::views::join(data);337 assert(std::ranges::find(joined, 4) == std::ranges::end(joined));338 }339 { // several sub-arrays of size 1 - match340 int data[3][1] = {{0}, {4}, {0}};341 auto joined = std::views::join(data);342 assert(std::ranges::find(joined, 4) == std::next(std::ranges::begin(joined)));343 }344 { // several sub-arrays of size 2 - match in second element of an array345 int data[3][2] = {{0, 0}, {0, 4}, {0, 0}};346 auto joined = std::views::join(data);347 assert(std::ranges::find(joined, 4) == std::ranges::next(std::ranges::begin(joined), 3));348 }349 { // vector of empty vectors350 std::vector<std::vector<int>> data = {{}, {}};351 auto joined = std::views::join(data);352 assert(std::ranges::find(joined, 4) == std::ranges::end(joined));353 }354 { // vector of variably sized vectors - match355 std::vector<std::vector<int>> data = {{}, {}, {3, 4}, {}, {}};356 auto joined = std::views::join(data);357 assert(std::ranges::find(joined, 4) == std::ranges::next(std::ranges::begin(joined)));358 }359 { // vector of variably sized vectors - no match360 std::vector<std::vector<int>> data = {{}, {}, {3, 5}, {}, {}};361 auto joined = std::views::join(data);362 assert(std::ranges::find(joined, 4) == std::ranges::end(joined));363 }364 }365}366 367int main(int, char**) {368 test_segmented_iterator_types();369 test();370 static_assert(test());371 372 types::for_each(types::cpp20_input_iterator_list<Comparable<char>*>{}, []<class Iter> {373 if constexpr (std::forward_iterator<Iter>)374 test_iterators<Iter>();375 test_iterators<Iter, sentinel_wrapper<Iter>>();376 test_iterators<Iter, sized_sentinel<Iter>>();377 });378 379 types::for_each(types::cpp20_input_iterator_list<Comparable<wchar_t>*>{}, []<class Iter> {380 if constexpr (std::forward_iterator<Iter>)381 test_iterators<Iter>();382 test_iterators<Iter, sentinel_wrapper<Iter>>();383 test_iterators<Iter, sized_sentinel<Iter>>();384 });385 386 return 0;387}388