294 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// ADDITIONAL_COMPILE_FLAGS(gcc): -Wno-bool-compare10// ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare11// ADDITIONAL_COMPILE_FLAGS(character-conversion-warnings): -Wno-character-conversion12// MSVC warning C4245: conversion from 'int' to 'wchar_t', signed/unsigned mismatch13// MSVC warning C4305: truncation from 'int' to 'bool'14// MSVC warning C4310: cast truncates constant value15// MSVC warning C4389: '==': signed/unsigned mismatch16// MSVC warning C4805: '==': unsafe mix of type 'char' and type 'bool' in operation17// ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4245 /wd4305 /wd4310 /wd4389 /wd480518// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000019// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=8000000020 21// <algorithm>22 23// template<InputIterator Iter, class T>24// requires HasEqualTo<Iter::value_type, T>25// constexpr Iter // constexpr after C++1726// find(Iter first, Iter last, const T& value);27 28#include <algorithm>29#include <cassert>30#include <cstddef>31#include <deque>32#include <vector>33#include <type_traits>34 35#include "sized_allocator.h"36#include "test_macros.h"37#include "test_iterators.h"38#include "type_algorithms.h"39 40static std::vector<int> comparable_data;41 42template <class ArrayT, class CompareT>43struct Test {44 template <class Iter>45 TEST_CONSTEXPR_CXX20 void operator()() {46 ArrayT arr[] = {47 ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(8), ArrayT(9), ArrayT(10)};48 49 static_assert(std::is_same<decltype(std::find(Iter(arr), Iter(arr), 0)), Iter>::value, "");50 51 { // first element matches52 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(1));53 assert(*iter == ArrayT(1));54 assert(base(iter) == arr);55 }56 57 { // range is empty; return last58 Iter iter = std::find(Iter(arr), Iter(arr), CompareT(1));59 assert(base(iter) == arr);60 }61 62 { // if multiple elements match, return the first match63 ArrayT data[] = {64 ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(5), ArrayT(4)};65 Iter iter = std::find(Iter(std::begin(data)), Iter(std::end(data)), CompareT(5));66 assert(*iter == ArrayT(5));67 assert(base(iter) == data + 4);68 }69 70 { // some element matches71 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(6));72 assert(*iter == ArrayT(6));73 assert(base(iter) == arr + 5);74 }75 76 { // last element matches77 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(10));78 assert(*iter == ArrayT(10));79 assert(base(iter) == arr + 9);80 }81 82 { // if no element matches, last is returned83 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(20));84 assert(base(iter) == arr + 10);85 }86 87 if (!TEST_IS_CONSTANT_EVALUATED)88 comparable_data.clear();89 }90};91 92template <class IndexT>93class Comparable {94 IndexT index_;95 96 static IndexT init_index(IndexT i) {97 IndexT size = static_cast<IndexT>(comparable_data.size());98 comparable_data.push_back(i);99 return size;100 }101 102public:103 Comparable(IndexT i) : index_(init_index(i)) {}104 105 friend bool operator==(const Comparable& lhs, const Comparable& rhs) {106 return comparable_data[lhs.index_] == comparable_data[rhs.index_];107 }108};109 110#if TEST_STD_VER >= 20111template <class ElementT>112class TriviallyComparable {113 ElementT el_;114 115public:116 explicit constexpr TriviallyComparable(ElementT el) : el_(el) {}117 bool operator==(const TriviallyComparable&) const = default;118};119#endif120 121template <class CompareT>122struct TestTypes {123 template <class T>124 TEST_CONSTEXPR_CXX20 void operator()() {125 types::for_each(types::cpp17_input_iterator_list<T*>(), Test<T, CompareT>());126 }127};128 129void test_deque() {130 { // empty deque131 std::deque<int> data;132 assert(std::find(data.begin(), data.end(), 4) == data.end());133 }134 135 { // single element - match136 std::deque<int> data;137 data.push_back(4);138 assert(std::find(data.begin(), data.end(), 4) == data.begin());139 }140 141 { // single element - no match142 std::deque<int> data;143 data.push_back(3);144 assert(std::find(data.begin(), data.end(), 4) == data.end());145 }146 147 // many elements148 int sizes[] = {2, 3, 1023, 1024, 1025, 2047, 2048, 2049};149 for (auto size : sizes) {150 { // last element match151 std::deque<int> data;152 data.resize(size);153 std::fill(data.begin(), data.end(), 3);154 data[size - 1] = 4;155 assert(std::find(data.begin(), data.end(), 4) == data.end() - 1);156 }157 158 { // second-last element match159 std::deque<int> data;160 data.resize(size);161 std::fill(data.begin(), data.end(), 3);162 data[size - 2] = 4;163 assert(std::find(data.begin(), data.end(), 4) == data.end() - 2);164 }165 166 { // no match167 std::deque<int> data;168 data.resize(size);169 std::fill(data.begin(), data.end(), 3);170 assert(std::find(data.begin(), data.end(), 4) == data.end());171 }172 }173}174 175template <class T>176struct TestIntegerPromotions1 {177 template <class U>178 TEST_CONSTEXPR_CXX20 void test(T val, U to_find) {179 bool expect_match = val == to_find;180 assert(std::find(&val, &val + 1, to_find) == (expect_match ? &val : &val + 1));181 }182 183 template <class U>184 TEST_CONSTEXPR_CXX20 void operator()() {185 test<U>(0, 0);186 test<U>(0, 1);187 test<U>(1, 1);188 test<U>(0, -1);189 test<U>(-1, -1);190 test<U>(0, U(-127));191 test<U>(T(-127), U(-127));192 test<U>(T(-128), U(-128));193 test<U>(T(-129), U(-129));194 test<U>(T(255), U(255));195 test<U>(T(256), U(256));196 test<U>(T(257), U(257));197 test<U>(0, std::numeric_limits<U>::min());198 test<U>(T(std::numeric_limits<U>::min()), std::numeric_limits<U>::min());199 test<U>(0, std::numeric_limits<U>::min() + 1);200 test<U>(T(std::numeric_limits<U>::min() + 1), std::numeric_limits<U>::min() + 1);201 test<U>(0, std::numeric_limits<U>::max());202 test<U>(T(std::numeric_limits<U>::max()), std::numeric_limits<U>::max());203 test<U>(T(std::numeric_limits<U>::max() - 1), std::numeric_limits<U>::max() - 1);204 }205};206 207struct TestIntegerPromotions {208 template <class T>209 TEST_CONSTEXPR_CXX20 void operator()() {210 types::for_each(types::integral_types(), TestIntegerPromotions1<T>());211 }212};213 214TEST_CONSTEXPR_CXX20 bool test() {215 types::for_each(types::integer_types(), TestTypes<char>());216 types::for_each(types::integer_types(), TestTypes<int>());217 types::for_each(types::integer_types(), TestTypes<long long>());218#if TEST_STD_VER >= 20219 Test<TriviallyComparable<char>, TriviallyComparable<char>>().operator()<TriviallyComparable<char>*>();220 Test<TriviallyComparable<wchar_t>, TriviallyComparable<wchar_t>>().operator()<TriviallyComparable<wchar_t>*>();221#endif222 223#if TEST_STD_VER >= 20224 {225 std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};226 auto view = vec | std::views::join;227 assert(std::find(view.begin(), view.end(), 4) == std::next(view.begin(), 3));228 }229#endif230 231 types::for_each(types::integral_types(), TestIntegerPromotions());232 233 {234 // Test vector<bool>::iterator optimization235 std::vector<bool> vec(256 + 8);236 for (ptrdiff_t i = 8; i <= 256; i *= 2) {237 for (size_t offset = 0; offset < 8; offset += 2) {238 std::fill(vec.begin(), vec.end(), false);239 std::fill(vec.begin() + offset, vec.begin() + i + offset, true);240 assert(std::find(vec.begin(), vec.end(), true) == vec.begin() + offset);241 assert(std::find(vec.begin() + offset, vec.end(), false) == vec.begin() + offset + i);242 }243 }244 245 // Verify that the std::vector<bool>::iterator optimization works properly for allocators with custom size types246 // Fix https://llvm.org/PR122528247 {248 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;249 std::vector<bool, Alloc> in(100, false, Alloc(1));250 in[in.size() - 2] = true;251 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);252 }253 {254 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;255 std::vector<bool, Alloc> in(199, false, Alloc(1));256 in[in.size() - 2] = true;257 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);258 }259 {260 using Alloc = sized_allocator<bool, unsigned short, short>;261 std::vector<bool, Alloc> in(200, false, Alloc(1));262 in[in.size() - 2] = true;263 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);264 }265 {266 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;267 std::vector<bool, Alloc> in(205, false, Alloc(1));268 in[in.size() - 2] = true;269 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);270 }271 {272 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;273 std::vector<bool, Alloc> in(257, false, Alloc(1));274 in[in.size() - 2] = true;275 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);276 }277 }278 279 return true;280}281 282int main(int, char**) {283 test_deque();284 test();285#if TEST_STD_VER >= 20286 static_assert(test());287#endif288 289 Test<Comparable<char>, Comparable<char> >().operator()<Comparable<char>*>();290 Test<Comparable<wchar_t>, Comparable<wchar_t> >().operator()<Comparable<wchar_t>*>();291 292 return 0;293}294