565 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// template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,14// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>15// requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>16// constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,17// Pred pred = {},18// Proj1 proj1 = {}, Proj2 proj2 = {});19// template<input_range R1, input_range R2, class Pred = ranges::equal_to,20// class Proj1 = identity, class Proj2 = identity>21// requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>22// constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},23// Proj1 proj1 = {}, Proj2 proj2 = {});24 25#include <algorithm>26#include <array>27#include <cassert>28#include <concepts>29#include <functional>30#include <ranges>31#include <vector>32 33#include "almost_satisfies_types.h"34#include "sized_allocator.h"35#include "test_iterators.h"36#include "test_macros.h"37 38template <class Iter1,39 class Sent1 = sentinel_wrapper<Iter1>,40 class Iter2 = Iter1,41 class Sent2 = sentinel_wrapper<Iter2>>42concept HasEqualIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {43 std::ranges::equal(first1, last1, first2, last2);44};45 46static_assert(HasEqualIt<int*>);47static_assert(!HasEqualIt<InputIteratorNotDerivedFrom>);48static_assert(!HasEqualIt<InputIteratorNotIndirectlyReadable>);49static_assert(!HasEqualIt<InputIteratorNotInputOrOutputIterator>);50static_assert(!HasEqualIt<int*, int*, InputIteratorNotDerivedFrom>);51static_assert(!HasEqualIt<int*, int*, InputIteratorNotIndirectlyReadable>);52static_assert(!HasEqualIt<int*, int*, InputIteratorNotInputOrOutputIterator>);53static_assert(!HasEqualIt<int*, SentinelForNotSemiregular>);54static_assert(!HasEqualIt<int*, SentinelForNotWeaklyEqualityComparableWith>);55static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotSemiregular>);56static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);57static_assert(!HasEqualIt<int*, int*, int**>);58 59template <class Range1, class Range2>60concept HasEqualR = requires(Range1 range1, Range2 range2) { std::ranges::equal(range1, range2); };61 62static_assert(HasEqualR<UncheckedRange<int*>, UncheckedRange<int*>>);63static_assert(!HasEqualR<InputRangeNotDerivedFrom, UncheckedRange<int*>>);64static_assert(!HasEqualR<InputRangeNotIndirectlyReadable, UncheckedRange<int*>>);65static_assert(!HasEqualR<InputRangeNotInputOrOutputIterator, UncheckedRange<int*>>);66static_assert(!HasEqualR<InputRangeNotSentinelSemiregular, UncheckedRange<int*>>);67static_assert(!HasEqualR<InputRangeNotSentinelEqualityComparableWith, UncheckedRange<int*>>);68static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotDerivedFrom>);69static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotIndirectlyReadable>);70static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotInputOrOutputIterator>);71static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>);72static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>);73static_assert(!HasEqualR<UncheckedRange<int*>, UncheckedRange<int**>>);74 75template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>76constexpr void test_iterators() {77 { // simple test78 {79 int a[] = {1, 2, 3, 4};80 int b[] = {1, 2, 3, 4};81 std::same_as<bool> decltype(auto) ret =82 std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)));83 assert(ret);84 }85 {86 int a[] = {1, 2, 3, 4};87 int b[] = {1, 2, 3, 4};88 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));89 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));90 std::same_as<bool> decltype(auto) ret = std::ranges::equal(range1, range2);91 assert(ret);92 }93 }94 95 { // check that false is returned for non-equal ranges96 {97 int a[] = {1, 2, 3, 4};98 int b[] = {1, 2, 4, 4};99 assert(!std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4))));100 }101 {102 int a[] = {1, 2, 3, 4};103 int b[] = {1, 2, 4, 4};104 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));105 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));106 assert(!std::ranges::equal(range1, range2));107 }108 }109 110 { // check that the predicate is used (return true)111 {112 int a[] = {1, 2, 3, 4};113 int b[] = {2, 3, 4, 5};114 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), [](int l, int r) {115 return l != r;116 });117 assert(ret);118 }119 {120 int a[] = {1, 2, 3, 4};121 int b[] = {2, 3, 4, 5};122 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));123 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));124 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; });125 assert(ret);126 }127 }128 129 { // check that the predicate is used (return false)130 {131 int a[] = {1, 2, 3, 4};132 int b[] = {2, 3, 3, 5};133 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), [](int l, int r) {134 return l != r;135 });136 assert(!ret);137 }138 {139 int a[] = {1, 2, 3, 4};140 int b[] = {2, 3, 3, 5};141 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));142 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));143 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; });144 assert(!ret);145 }146 }147 148 { // check that the projections are used149 {150 int a[] = {1, 2, 3, 4, 5};151 int b[] = {6, 10, 14, 18, 22};152 auto ret = std::ranges::equal(153 Iter1(a),154 Sent1(Iter1(a + 5)),155 Iter2(b),156 Sent2(Iter2(b + 5)),157 {},158 [](int i) { return i * 4; },159 [](int i) { return i - 2; });160 assert(ret);161 }162 {163 int a[] = {1, 2, 3, 4, 5};164 int b[] = {6, 10, 14, 18, 22};165 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));166 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5)));167 auto ret = std::ranges::equal(range1, range2, {}, [](int i) { return i * 4; }, [](int i) { return i - 2; });168 assert(ret);169 }170 }171 172 { // check that different sized ranges work173 {174 int a[] = {4, 3, 2, 1};175 int b[] = {4, 3, 2, 1, 5, 6, 7};176 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 7)));177 assert(!ret);178 }179 {180 int a[] = {4, 3, 2, 1};181 int b[] = {4, 3, 2, 1, 5, 6, 7};182 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));183 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 7)));184 auto ret = std::ranges::equal(range1, range2);185 assert(!ret);186 }187 }188 189 { // check that two ranges with the same size but different values are different190 {191 int a[] = {4, 6, 34, 76, 5};192 int b[] = {4, 6, 34, 67, 5};193 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), Iter2(b), Sent2(Iter2(b + 5)));194 assert(!ret);195 }196 {197 int a[] = {4, 6, 34, 76, 5};198 int b[] = {4, 6, 34, 67, 5};199 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));200 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5)));201 auto ret = std::ranges::equal(range1, range2);202 assert(!ret);203 }204 }205 206 { // check that two empty ranges work207 {208 std::array<int, 0> a = {};209 std::array<int, 0> b = {};210 auto ret = std::ranges::equal(Iter1(a.data()), Sent1(Iter1(a.data())), Iter2(b.data()), Sent2(Iter2(b.data())));211 assert(ret);212 }213 {214 std::array<int, 0> a = {};215 std::array<int, 0> b = {};216 auto range1 = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));217 auto range2 = std::ranges::subrange(Iter2(b.data()), Sent2(Iter2(b.data())));218 auto ret = std::ranges::equal(range1, range2);219 assert(ret);220 }221 }222 223 { // check that it works with the first range empty224 {225 std::array<int, 0> a = {};226 int b[] = {1, 2};227 auto ret = std::ranges::equal(Iter1(a.data()), Sent1(Iter1(a.data())), Iter2(b), Sent2(Iter2(b + 2)));228 assert(!ret);229 }230 {231 std::array<int, 0> a = {};232 int b[] = {1, 2};233 auto range1 = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));234 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 2)));235 auto ret = std::ranges::equal(range1, range2);236 assert(!ret);237 }238 }239 240 { // check that it works with the second range empty241 {242 int a[] = {1, 2};243 std::array<int, 0> b = {};244 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 2)), Iter2(b.data()), Sent2(Iter2(b.data())));245 assert(!ret);246 }247 {248 int a[] = {1, 2};249 std::array<int, 0> b = {};250 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 2)));251 auto range2 = std::ranges::subrange(Iter2(b.data()), Sent2(Iter2(b.data())));252 auto ret = std::ranges::equal(range1, range2);253 assert(!ret);254 }255 }256}257 258template <class Iter1, class Sent1 = Iter1>259constexpr void test_iterators2() {260 test_iterators<Iter1, Sent1, cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();261 test_iterators<Iter1, Sent1, cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();262 test_iterators<Iter1, Sent1, forward_iterator<int*>>();263 test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();264 test_iterators<Iter1, Sent1, random_access_iterator<int*>>();265 test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();266 test_iterators<Iter1, Sent1, int*>();267 test_iterators<Iter1, Sent1, const int*>();268}269 270template <std::size_t N>271constexpr void test_vector_bool() {272 std::vector<bool> in(N, false);273 for (std::size_t i = 0; i < N; i += 2)274 in[i] = true;275 { // Test equal() with aligned bytes276 std::vector<bool> out = in;277 assert(std::ranges::equal(in, out));278 }279 { // Test equal() with unaligned bytes280 std::vector<bool> out(N + 8);281 std::copy(in.begin(), in.end(), out.begin() + 4);282 assert(std::ranges::equal(in.begin(), in.end(), out.begin() + 4, out.end() - 4));283 }284}285 286constexpr bool test() {287 test_iterators2<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();288 test_iterators2<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();289 test_iterators2<forward_iterator<int*>>();290 test_iterators2<bidirectional_iterator<int*>>();291 test_iterators2<random_access_iterator<int*>>();292 test_iterators2<contiguous_iterator<int*>>();293 test_iterators2<int*>();294 test_iterators2<const int*>();295 296 { // check that std::invoke is used297 struct S {298 constexpr S(int i_) : i(i_) {}299 constexpr bool equal(int o) { return i == o; }300 constexpr S& identity() { return *this; }301 int i;302 };303 {304 S a[] = {7, 8, 9};305 S b[] = {7, 8, 9};306 auto ret = std::ranges::equal(a, a + 3, b, b + 3, &S::equal, &S::identity, &S::i);307 assert(ret);308 }309 {310 S a[] = {7, 8, 9};311 S b[] = {7, 8, 9};312 auto ret = std::ranges::equal(a, b, &S::equal, &S::identity, &S::i);313 assert(ret);314 }315 }316 317 { // check that the complexity requirements are met318 { // different size319 {320 int a[] = {1, 2, 3};321 int b[] = {1, 2, 3, 4};322 int predCount = 0;323 int projCount = 0;324 auto pred = [&](int l, int r) {325 ++predCount;326 return l == r;327 };328 auto proj = [&](int i) {329 ++projCount;330 return i;331 };332 auto ret = std::ranges::equal(a, a + 3, b, b + 4, pred, proj, proj);333 assert(!ret);334 assert(predCount == 0);335 assert(projCount == 0);336 }337 {338 int a[] = {1, 2, 3};339 int b[] = {1, 2, 3, 4};340 int predCount = 0;341 int projCount = 0;342 auto pred = [&](int l, int r) {343 ++predCount;344 return l == r;345 };346 auto proj = [&](int i) {347 ++projCount;348 return i;349 };350 auto ret = std::ranges::equal(a, b, pred, proj, proj);351 assert(!ret);352 assert(predCount == 0);353 assert(projCount == 0);354 }355 }356 357 { // not a sized sentinel358 {359 int a[] = {1, 2, 3};360 int b[] = {1, 2, 3, 4};361 int predCount = 0;362 int projCount = 0;363 auto pred = [&](int l, int r) {364 ++predCount;365 return l == r;366 };367 auto proj = [&](int i) {368 ++projCount;369 return i;370 };371 auto ret = std::ranges::equal(a, sentinel_wrapper(a + 3), b, sentinel_wrapper(b + 4), pred, proj, proj);372 assert(!ret);373 assert(predCount <= 4);374 assert(projCount <= 7);375 }376 {377 int a[] = {1, 2, 3};378 int b[] = {1, 2, 3, 4};379 int predCount = 0;380 int projCount = 0;381 auto pred = [&](int l, int r) {382 ++predCount;383 return l == r;384 };385 auto proj = [&](int i) {386 ++projCount;387 return i;388 };389 auto range1 = std::ranges::subrange(a, sentinel_wrapper(a + 3));390 auto range2 = std::ranges::subrange(b, sentinel_wrapper(b + 4));391 auto ret = std::ranges::equal(range1, range2, pred, proj, proj);392 assert(!ret);393 assert(predCount <= 4);394 assert(projCount <= 7);395 }396 }397 398 { // same size399 {400 int a[] = {1, 2, 3};401 int b[] = {1, 2, 3};402 int predCount = 0;403 int projCount = 0;404 auto pred = [&](int l, int r) {405 ++predCount;406 return l == r;407 };408 auto proj = [&](int i) {409 ++projCount;410 return i;411 };412 auto ret = std::ranges::equal(a, a + 3, b, b + 3, pred, proj, proj);413 assert(ret);414 assert(predCount == 3);415 assert(projCount == 6);416 }417 {418 int a[] = {1, 2, 3};419 int b[] = {1, 2, 3};420 int predCount = 0;421 int projCount = 0;422 auto pred = [&](int l, int r) {423 ++predCount;424 return l == r;425 };426 auto proj = [&](int i) {427 ++projCount;428 return i;429 };430 auto ret = std::ranges::equal(a, b, pred, proj, proj);431 assert(ret);432 assert(predCount == 3);433 assert(projCount == 6);434 }435 }436 }437 438 { // Test vector<bool>::iterator optimization439 test_vector_bool<8>();440 test_vector_bool<19>();441 test_vector_bool<32>();442 test_vector_bool<49>();443 test_vector_bool<64>();444 test_vector_bool<199>();445 test_vector_bool<256>();446 }447 448 // Make sure std::equal behaves properly with std::vector<bool> iterators with custom size types.449 // See issue: https://llvm.org/PR126369.450 {451 //// Tests for std::equal with aligned bits452 453 { // Test the first (partial) word for uint8_t454 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;455 std::vector<bool, Alloc> in(6, true, Alloc(1));456 std::vector<bool, Alloc> expected(8, true, Alloc(1));457 auto a = std::ranges::subrange(in.begin() + 4, in.end());458 auto b = std::ranges::subrange(expected.begin() + 4, expected.begin() + 4 + a.size());459 assert(std::ranges::equal(a, b));460 }461 { // Test the last word for uint8_t462 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;463 std::vector<bool, Alloc> in(12, true, Alloc(1));464 std::vector<bool, Alloc> expected(16, true, Alloc(1));465 auto a = std::ranges::subrange(in.begin(), in.end());466 auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());467 assert(std::ranges::equal(a, b));468 }469 { // Test middle words for uint8_t470 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;471 std::vector<bool, Alloc> in(24, true, Alloc(1));472 std::vector<bool, Alloc> expected(29, true, Alloc(1));473 auto a = std::ranges::subrange(in.begin(), in.end());474 auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());475 assert(std::ranges::equal(a, b));476 }477 478 { // Test the first (partial) word for uint16_t479 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;480 std::vector<bool, Alloc> in(12, true, Alloc(1));481 std::vector<bool, Alloc> expected(16, true, Alloc(1));482 auto a = std::ranges::subrange(in.begin() + 4, in.end());483 auto b = std::ranges::subrange(expected.begin() + 4, expected.begin() + 4 + a.size());484 assert(std::ranges::equal(a, b));485 }486 { // Test the last word for uint16_t487 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;488 std::vector<bool, Alloc> in(24, true, Alloc(1));489 std::vector<bool, Alloc> expected(32, true, Alloc(1));490 auto a = std::ranges::subrange(in.begin(), in.end());491 auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());492 assert(std::ranges::equal(a, b));493 }494 { // Test middle words for uint16_t495 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;496 std::vector<bool, Alloc> in(48, true, Alloc(1));497 std::vector<bool, Alloc> expected(55, true, Alloc(1));498 auto a = std::ranges::subrange(in.begin(), in.end());499 auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());500 assert(std::ranges::equal(a, b));501 }502 503 //// Tests for std::equal with unaligned bits504 505 { // Test the first (partial) word for uint8_t506 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;507 std::vector<bool, Alloc> in(6, true, Alloc(1));508 std::vector<bool, Alloc> expected(8, true, Alloc(1));509 auto a = std::ranges::subrange(in.begin() + 4, in.end());510 auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());511 assert(std::ranges::equal(a, b));512 }513 { // Test the last word for uint8_t514 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;515 std::vector<bool, Alloc> in(4, true, Alloc(1));516 std::vector<bool, Alloc> expected(8, true, Alloc(1));517 auto a = std::ranges::subrange(in.begin(), in.end());518 auto b = std::ranges::subrange(expected.begin() + 3, expected.begin() + 3 + a.size());519 assert(std::ranges::equal(a, b));520 }521 { // Test middle words for uint8_t522 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;523 std::vector<bool, Alloc> in(16, true, Alloc(1));524 std::vector<bool, Alloc> expected(24, true, Alloc(1));525 auto a = std::ranges::subrange(in.begin(), in.end());526 auto b = std::ranges::subrange(expected.begin() + 4, expected.begin() + 4 + a.size());527 assert(std::ranges::equal(a, b));528 }529 530 { // Test the first (partial) word for uint16_t531 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;532 std::vector<bool, Alloc> in(12, true, Alloc(1));533 std::vector<bool, Alloc> expected(16, true, Alloc(1));534 auto a = std::ranges::subrange(in.begin() + 4, in.end());535 auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());536 assert(std::ranges::equal(a, b));537 }538 { // Test the last word for uint16_t539 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;540 std::vector<bool, Alloc> in(12, true, Alloc(1));541 std::vector<bool, Alloc> expected(16, true, Alloc(1));542 auto a = std::ranges::subrange(in.begin(), in.end());543 auto b = std::ranges::subrange(expected.begin() + 3, expected.begin() + 3 + a.size());544 assert(std::ranges::equal(a, b));545 }546 { // Test the middle words for uint16_t547 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;548 std::vector<bool, Alloc> in(32, true, Alloc(1));549 std::vector<bool, Alloc> expected(64, true, Alloc(1));550 auto a = std::ranges::subrange(in.begin(), in.end());551 auto b = std::ranges::subrange(expected.begin() + 4, expected.begin() + 4 + a.size());552 assert(std::ranges::equal(a, b));553 }554 }555 556 return true;557}558 559int main(int, char**) {560 test();561 static_assert(test());562 563 return 0;564}565