836 lines · cpp
1//===- IteratorTest.cpp - Unit tests for iterator utilities ---------------===//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#include "llvm/ADT/iterator.h"10#include "llvm/ADT/ArrayRef.h"11#include "llvm/ADT/STLExtras.h"12#include "llvm/ADT/SmallVector.h"13#include "llvm/ADT/ilist.h"14#include "gmock/gmock.h"15#include "gtest/gtest.h"16#include <optional>17#include <type_traits>18#include <vector>19 20using namespace llvm;21using testing::ElementsAre;22 23namespace {24 25namespace adl_test {26struct WithFreeBeginEnd {27 int data[3] = {21, 22, 23};28};29 30auto begin(const WithFreeBeginEnd &X) { return std::begin(X.data); }31auto end(const WithFreeBeginEnd &X) { return std::end(X.data); }32 33struct WithFreeRBeginREnd {34 int data[3] = {42, 43, 44};35};36 37auto rbegin(const WithFreeRBeginREnd &X) { return std::rbegin(X.data); }38auto rend(const WithFreeRBeginREnd &X) { return std::rend(X.data); }39} // namespace adl_test40 41template <int> struct Shadow;42 43struct WeirdIter44 : llvm::iterator_facade_base<WeirdIter, std::input_iterator_tag, Shadow<0>,45 Shadow<1>, Shadow<2>, Shadow<3>> {};46 47struct AdaptedIter : iterator_adaptor_base<AdaptedIter, WeirdIter> {};48 49// Test that iterator_adaptor_base forwards typedefs, if value_type is50// unchanged.51static_assert(std::is_same_v<AdaptedIter::value_type, Shadow<0>>, "");52static_assert(std::is_same_v<AdaptedIter::difference_type, Shadow<1>>, "");53static_assert(std::is_same_v<AdaptedIter::pointer, Shadow<2>>, "");54static_assert(std::is_same_v<AdaptedIter::reference, Shadow<3>>, "");55 56// Ensure that pointe{e,r}_iterator adaptors correctly forward the category of57// the underlying iterator.58 59using RandomAccessIter = SmallVectorImpl<int*>::iterator;60using BidiIter = ilist<int*>::iterator;61 62template<class T>63using pointee_iterator_defaulted = pointee_iterator<T>;64template<class T>65using pointer_iterator_defaulted = pointer_iterator<T>;66 67// Ensures that an iterator and its adaptation have the same iterator_category.68template<template<typename> class A, typename It>69using IsAdaptedIterCategorySame =70 std::is_same<typename std::iterator_traits<It>::iterator_category,71 typename std::iterator_traits<A<It>>::iterator_category>;72 73// Check that dereferencing works correctly adapting pointers and proxies.74template <class T>75struct PointerWrapper : public iterator_adaptor_base<PointerWrapper<T>, T *> {76 PointerWrapper(T *I) : PointerWrapper::iterator_adaptor_base(I) {}77};78struct IntProxy {79 int &I;80 IntProxy(int &I) : I(I) {}81 void operator=(int NewValue) { I = NewValue; }82};83struct ConstIntProxy {84 const int &I;85 ConstIntProxy(const int &I) : I(I) {}86};87template <class T, class ProxyT>88struct PointerProxyWrapper89 : public iterator_adaptor_base<PointerProxyWrapper<T, ProxyT>, T *,90 std::random_access_iterator_tag, T,91 ptrdiff_t, T *, ProxyT> {92 PointerProxyWrapper(T *I) : PointerProxyWrapper::iterator_adaptor_base(I) {}93};94using IntIterator = PointerWrapper<int>;95using ConstIntIterator = PointerWrapper<const int>;96using IntProxyIterator = PointerProxyWrapper<int, IntProxy>;97using ConstIntProxyIterator = PointerProxyWrapper<const int, ConstIntProxy>;98 99// There should only be a single (const-qualified) operator*, operator->, and100// operator[]. This test confirms that there isn't a non-const overload. Rather101// than adding those, users should double-check that T, PointerT, and ReferenceT102// have the right constness, and/or make fields mutable.103static_assert(&IntIterator::operator* == &IntIterator::operator*, "");104static_assert(&IntIterator::operator-> == &IntIterator::operator->, "");105static_assert(&IntIterator::operator[] == &IntIterator::operator[], "");106 107template <class T, std::enable_if_t<std::is_assignable_v<T, int>, bool> = false>108constexpr bool canAssignFromInt(T &&) {109 return true;110}111template <class T,112 std::enable_if_t<!std::is_assignable_v<T, int>, bool> = false>113constexpr bool canAssignFromInt(T &&) {114 return false;115}116 117TEST(IteratorAdaptorTest, Dereference) {118 int Number = 1;119 120 // Construct some iterators and check whether they can be assigned to.121 IntIterator I(&Number);122 const IntIterator IC(&Number);123 ConstIntIterator CI(&Number);124 const ConstIntIterator CIC(&Number);125 EXPECT_EQ(true, canAssignFromInt(*I)); // int *126 EXPECT_EQ(true, canAssignFromInt(*IC)); // int *const127 EXPECT_EQ(false, canAssignFromInt(*CI)); // const int *128 EXPECT_EQ(false, canAssignFromInt(*CIC)); // const int *const129 130 // Prove that dereference and assignment work.131 EXPECT_EQ(1, *I);132 EXPECT_EQ(1, *IC);133 EXPECT_EQ(1, *CI);134 EXPECT_EQ(1, *CIC);135 *I = 2;136 EXPECT_EQ(2, Number);137 *IC = 3;138 EXPECT_EQ(3, Number);139 140 // Construct some proxy iterators and check whether they can be assigned to.141 IntProxyIterator P(&Number);142 const IntProxyIterator PC(&Number);143 ConstIntProxyIterator CP(&Number);144 const ConstIntProxyIterator CPC(&Number);145 EXPECT_EQ(true, canAssignFromInt(*P)); // int *146 EXPECT_EQ(true, canAssignFromInt(*PC)); // int *const147 EXPECT_EQ(false, canAssignFromInt(*CP)); // const int *148 EXPECT_EQ(false, canAssignFromInt(*CPC)); // const int *const149 150 // Prove that dereference and assignment work.151 EXPECT_EQ(3, (*P).I);152 EXPECT_EQ(3, (*PC).I);153 EXPECT_EQ(3, (*CP).I);154 EXPECT_EQ(3, (*CPC).I);155 *P = 4;156 EXPECT_EQ(4, Number);157 *PC = 5;158 EXPECT_EQ(5, Number);159}160 161// pointeE_iterator162static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,163 RandomAccessIter>::value, "");164static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,165 BidiIter>::value, "");166// pointeR_iterator167static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,168 RandomAccessIter>::value, "");169static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,170 BidiIter>::value, "");171 172TEST(PointeeIteratorTest, Basic) {173 int arr[4] = {1, 2, 3, 4};174 SmallVector<int *, 4> V;175 V.push_back(&arr[0]);176 V.push_back(&arr[1]);177 V.push_back(&arr[2]);178 V.push_back(&arr[3]);179 180 using test_iterator =181 pointee_iterator<SmallVectorImpl<int *>::const_iterator>;182 183 test_iterator Begin, End;184 Begin = V.begin();185 End = test_iterator(V.end());186 187 test_iterator I = Begin;188 for (int i = 0; i < 4; ++i) {189 EXPECT_EQ(*V[i], *I);190 191 EXPECT_EQ(I, Begin + i);192 EXPECT_EQ(I, std::next(Begin, i));193 test_iterator J = Begin;194 J += i;195 EXPECT_EQ(I, J);196 EXPECT_EQ(*V[i], Begin[i]);197 198 EXPECT_NE(I, End);199 EXPECT_GT(End, I);200 EXPECT_LT(I, End);201 EXPECT_GE(I, Begin);202 EXPECT_LE(Begin, I);203 204 EXPECT_EQ(i, I - Begin);205 EXPECT_EQ(i, std::distance(Begin, I));206 EXPECT_EQ(Begin, I - i);207 208 test_iterator K = I++;209 EXPECT_EQ(K, std::prev(I));210 }211 EXPECT_EQ(End, I);212}213 214TEST(PointeeIteratorTest, SmartPointer) {215 SmallVector<std::unique_ptr<int>, 4> V;216 V.push_back(std::make_unique<int>(1));217 V.push_back(std::make_unique<int>(2));218 V.push_back(std::make_unique<int>(3));219 V.push_back(std::make_unique<int>(4));220 221 using test_iterator =222 pointee_iterator<SmallVectorImpl<std::unique_ptr<int>>::const_iterator>;223 224 test_iterator Begin, End;225 Begin = V.begin();226 End = test_iterator(V.end());227 228 test_iterator I = Begin;229 for (int i = 0; i < 4; ++i) {230 EXPECT_EQ(*V[i], *I);231 232 EXPECT_EQ(I, Begin + i);233 EXPECT_EQ(I, std::next(Begin, i));234 test_iterator J = Begin;235 J += i;236 EXPECT_EQ(I, J);237 EXPECT_EQ(*V[i], Begin[i]);238 239 EXPECT_NE(I, End);240 EXPECT_GT(End, I);241 EXPECT_LT(I, End);242 EXPECT_GE(I, Begin);243 EXPECT_LE(Begin, I);244 245 EXPECT_EQ(i, I - Begin);246 EXPECT_EQ(i, std::distance(Begin, I));247 EXPECT_EQ(Begin, I - i);248 249 test_iterator K = I++;250 EXPECT_EQ(K, std::prev(I));251 }252 EXPECT_EQ(End, I);253}254 255TEST(PointeeIteratorTest, Range) {256 int A[] = {1, 2, 3, 4};257 SmallVector<int *, 4> V{&A[0], &A[1], &A[2], &A[3]};258 259 int I = 0;260 for (int II : make_pointee_range(V))261 EXPECT_EQ(A[I++], II);262}263 264TEST(PointeeIteratorTest, PointeeType) {265 struct S {266 int X;267 bool operator==(const S &RHS) const { return X == RHS.X; };268 };269 S A[] = {S{0}, S{1}};270 SmallVector<S *, 2> V{&A[0], &A[1]};271 272 pointee_iterator<SmallVectorImpl<S *>::const_iterator, const S> I = V.begin();273 for (int j = 0; j < 2; ++j, ++I) {274 EXPECT_EQ(*V[j], *I);275 }276}277 278TEST(FilterIteratorTest, Lambda) {279 auto IsOdd = [](int N) { return N % 2 == 1; };280 int A[] = {0, 1, 2, 3, 4, 5, 6};281 auto Range = make_filter_range(A, IsOdd);282 SmallVector<int, 3> Actual(Range.begin(), Range.end());283 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);284}285 286TEST(FilterIteratorTest, Enumerate) {287 auto IsOdd = [](auto N) { return N.value() % 2 == 1; };288 int A[] = {0, 1, 2, 3, 4, 5, 6};289 auto Enumerate = llvm::enumerate(A);290 SmallVector<int> Actual;291 for (const auto &IndexedValue : make_filter_range(Enumerate, IsOdd))292 Actual.push_back(IndexedValue.value());293 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);294}295 296TEST(FilterIteratorTest, CallableObject) {297 int Counter = 0;298 struct Callable {299 int &Counter;300 301 Callable(int &Counter) : Counter(Counter) {}302 303 bool operator()(int N) {304 Counter++;305 return N % 2 == 1;306 }307 };308 Callable IsOdd(Counter);309 int A[] = {0, 1, 2, 3, 4, 5, 6};310 auto Range = make_filter_range(A, IsOdd);311 EXPECT_EQ(2, Counter);312 SmallVector<int, 3> Actual(Range.begin(), Range.end());313 EXPECT_GE(Counter, 7);314 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);315}316 317TEST(FilterIteratorTest, FunctionPointer) {318 bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; };319 int A[] = {0, 1, 2, 3, 4, 5, 6};320 auto Range = make_filter_range(A, IsOdd);321 SmallVector<int, 3> Actual(Range.begin(), Range.end());322 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);323}324 325TEST(FilterIteratorTest, Composition) {326 auto IsOdd = [](int N) { return N % 2 == 1; };327 std::unique_ptr<int> A[] = {std::make_unique<int>(0), std::make_unique<int>(1),328 std::make_unique<int>(2), std::make_unique<int>(3),329 std::make_unique<int>(4), std::make_unique<int>(5),330 std::make_unique<int>(6)};331 using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>;332 auto Range = make_filter_range(333 make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))),334 IsOdd);335 SmallVector<int, 3> Actual(Range.begin(), Range.end());336 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);337}338 339TEST(FilterIteratorTest, InputIterator) {340 struct InputIterator341 : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> {342 InputIterator(int *It) : InputIterator::iterator_adaptor_base(It) {}343 };344 345 auto IsOdd = [](int N) { return N % 2 == 1; };346 int A[] = {0, 1, 2, 3, 4, 5, 6};347 auto Range = make_filter_range(348 make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))),349 IsOdd);350 SmallVector<int, 3> Actual(Range.begin(), Range.end());351 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);352}353 354TEST(FilterIteratorTest, ReverseFilterRange) {355 auto IsOdd = [](int N) { return N % 2 == 1; };356 int A[] = {0, 1, 2, 3, 4, 5, 6};357 358 // Check basic reversal.359 auto Range = reverse(make_filter_range(A, IsOdd));360 SmallVector<int, 3> Actual(Range.begin(), Range.end());361 EXPECT_EQ((SmallVector<int, 3>{5, 3, 1}), Actual);362 363 // Check that the reverse of the reverse is the original.364 auto Range2 = reverse(reverse(make_filter_range(A, IsOdd)));365 SmallVector<int, 3> Actual2(Range2.begin(), Range2.end());366 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual2);367 368 // Check empty ranges.369 auto Range3 = reverse(make_filter_range(ArrayRef<int>(), IsOdd));370 SmallVector<int, 0> Actual3(Range3.begin(), Range3.end());371 EXPECT_EQ((SmallVector<int, 0>{}), Actual3);372 373 // Check that we don't skip the first element, provided it isn't filtered374 // away.375 auto IsEven = [](int N) { return N % 2 == 0; };376 auto Range4 = reverse(make_filter_range(A, IsEven));377 SmallVector<int, 4> Actual4(Range4.begin(), Range4.end());378 EXPECT_EQ((SmallVector<int, 4>{6, 4, 2, 0}), Actual4);379}380 381TEST(FilterIteratorTest, ADL) {382 // Make sure that we use the `begin`/`end` functions383 // from `adl_test`, using ADL.384 adl_test::WithFreeBeginEnd R;385 auto IsOdd = [](int N) { return N % 2 != 0; };386 EXPECT_THAT(make_filter_range(R, IsOdd), ElementsAre(21, 23));387}388 389TEST(PointerIterator, Basic) {390 int A[] = {1, 2, 3, 4};391 pointer_iterator<int *> Begin(std::begin(A)), End(std::end(A));392 EXPECT_EQ(A, *Begin);393 ++Begin;394 EXPECT_EQ(A + 1, *Begin);395 ++Begin;396 EXPECT_EQ(A + 2, *Begin);397 ++Begin;398 EXPECT_EQ(A + 3, *Begin);399 ++Begin;400 EXPECT_EQ(Begin, End);401}402 403TEST(PointerIterator, Const) {404 int A[] = {1, 2, 3, 4};405 const pointer_iterator<int *> Begin(std::begin(A));406 EXPECT_EQ(A, *Begin);407 EXPECT_EQ(A + 1, std::next(*Begin, 1));408 EXPECT_EQ(A + 2, std::next(*Begin, 2));409 EXPECT_EQ(A + 3, std::next(*Begin, 3));410 EXPECT_EQ(A + 4, std::next(*Begin, 4));411}412 413TEST(PointerIterator, Range) {414 int A[] = {1, 2, 3, 4};415 int I = 0;416 for (int *P : make_pointer_range(A))417 EXPECT_EQ(A + I++, P);418}419 420TEST(ReverseTest, ADL) {421 // Check that we can find the rbegin/rend functions via ADL.422 adl_test::WithFreeRBeginREnd Foo;423 EXPECT_THAT(reverse(Foo), ElementsAre(44, 43, 42));424}425 426TEST(ZipIteratorTest, Basic) {427 using namespace std;428 const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};429 SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1};430 const char message[] = "yynyyy\0";431 std::array<int, 2> shortArr = {42, 43};432 433 for (auto tup : zip(pi, odd, message)) {434 EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));435 EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup));436 }437 438 // Note the rvalue.439 for (auto tup : zip(pi, SmallVector<bool, 0>{1, 1, 0, 1, 1})) {440 EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));441 }442 443 // Iterate until we run out elements in the *shortest* range.444 for (auto [idx, elem] : enumerate(zip(odd, shortArr))) {445 EXPECT_LT(idx, static_cast<size_t>(2));446 }447 for (auto [idx, elem] : enumerate(zip(shortArr, odd))) {448 EXPECT_LT(idx, static_cast<size_t>(2));449 }450}451 452TEST(ZipIteratorTest, ZipEqualBasic) {453 const SmallVector<unsigned, 6> pi = {3, 1, 4, 1, 5, 8};454 const SmallVector<bool, 6> vals = {1, 1, 0, 1, 1, 0};455 unsigned iters = 0;456 457 for (auto [lhs, rhs] : zip_equal(vals, pi)) {458 EXPECT_EQ(lhs, rhs & 0x01);459 ++iters;460 }461 462 EXPECT_EQ(iters, 6u);463}464 465template <typename T>466constexpr bool IsConstRef =467 std::is_reference_v<T> && std::is_const_v<std::remove_reference_t<T>>;468 469template <typename T>470constexpr bool IsBoolConstRef =471 std::is_same_v<llvm::remove_cvref_t<T>, std::vector<bool>::const_reference>;472 473/// Returns a `const` copy of the passed value. The `const` on the returned474/// value is intentional here so that `MakeConst` can be used in range-for475/// loops.476template <typename T> const T MakeConst(T &&value) {477 return std::forward<T>(value);478}479 480TEST(ZipIteratorTest, ZipEqualConstCorrectness) {481 const std::vector<unsigned> c_first = {3, 1, 4};482 std::vector<unsigned> first = c_first;483 const SmallVector<bool> c_second = {1, 1, 0};484 SmallVector<bool> second = c_second;485 486 for (auto [a, b, c, d] : zip_equal(c_first, first, c_second, second)) {487 b = 0;488 d = true;489 static_assert(IsConstRef<decltype(a)>);490 static_assert(!IsConstRef<decltype(b)>);491 static_assert(IsConstRef<decltype(c)>);492 static_assert(!IsConstRef<decltype(d)>);493 }494 495 EXPECT_THAT(first, ElementsAre(0, 0, 0));496 EXPECT_THAT(second, ElementsAre(true, true, true));497 498 std::vector<bool> nemesis = {true, false, true};499 const std::vector<bool> c_nemesis = nemesis;500 501 for (auto &&[a, b, c, d] : zip_equal(first, c_first, nemesis, c_nemesis)) {502 a = 2;503 c = true;504 static_assert(!IsConstRef<decltype(a)>);505 static_assert(IsConstRef<decltype(b)>);506 static_assert(!IsBoolConstRef<decltype(c)>);507 static_assert(IsBoolConstRef<decltype(d)>);508 }509 510 EXPECT_THAT(first, ElementsAre(2, 2, 2));511 EXPECT_THAT(nemesis, ElementsAre(true, true, true));512 513 unsigned iters = 0;514 for (const auto &[a, b, c, d] :515 zip_equal(first, c_first, nemesis, c_nemesis)) {516 static_assert(!IsConstRef<decltype(a)>);517 static_assert(IsConstRef<decltype(b)>);518 static_assert(!IsBoolConstRef<decltype(c)>);519 static_assert(IsBoolConstRef<decltype(d)>);520 ++iters;521 }522 EXPECT_EQ(iters, 3u);523 iters = 0;524 525 for (const auto &[a, b, c, d] :526 MakeConst(zip_equal(first, c_first, nemesis, c_nemesis))) {527 static_assert(!IsConstRef<decltype(a)>);528 static_assert(IsConstRef<decltype(b)>);529 static_assert(!IsBoolConstRef<decltype(c)>);530 static_assert(IsBoolConstRef<decltype(d)>);531 ++iters;532 }533 EXPECT_EQ(iters, 3u);534}535 536TEST(ZipIteratorTest, ZipEqualTemporaries) {537 unsigned iters = 0;538 539 // These temporary ranges get moved into the `tuple<...> storage;` inside540 // `zippy`. From then on, we can use references obtained from this storage to541 // access them. This does not rely on any lifetime extensions on the542 // temporaries passed to `zip_equal`.543 for (auto [a, b, c] : zip_equal(SmallVector<int>{1, 2, 3}, std::string("abc"),544 std::vector<bool>{true, false, true})) {545 a = 3;546 b = 'c';547 c = false;548 static_assert(!IsConstRef<decltype(a)>);549 static_assert(!IsConstRef<decltype(b)>);550 static_assert(!IsBoolConstRef<decltype(c)>);551 ++iters;552 }553 EXPECT_EQ(iters, 3u);554 iters = 0;555 556 for (auto [a, b, c] :557 MakeConst(zip_equal(SmallVector<int>{1, 2, 3}, std::string("abc"),558 std::vector<bool>{true, false, true}))) {559 static_assert(IsConstRef<decltype(a)>);560 static_assert(IsConstRef<decltype(b)>);561 static_assert(IsBoolConstRef<decltype(c)>);562 ++iters;563 }564 EXPECT_EQ(iters, 3u);565}566 567#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST568// Check that an assertion is triggered when ranges passed to `zip_equal` differ569// in length.570TEST(ZipIteratorTest, ZipEqualNotEqual) {571 const SmallVector<unsigned, 6> pi = {3, 1, 4, 1, 5, 8};572 const SmallVector<bool, 2> vals = {1, 1};573 574 EXPECT_DEATH(zip_equal(pi, vals), "Iteratees do not have equal length");575 EXPECT_DEATH(zip_equal(vals, pi), "Iteratees do not have equal length");576 EXPECT_DEATH(zip_equal(pi, pi, vals), "Iteratees do not have equal length");577 EXPECT_DEATH(zip_equal(vals, vals, pi), "Iteratees do not have equal length");578}579#endif580 581TEST(ZipIteratorTest, ZipFirstBasic) {582 using namespace std;583 const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};584 unsigned iters = 0;585 586 for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {587 EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01);588 iters += 1;589 }590 591 EXPECT_EQ(iters, 4u);592}593 594#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST595// Make sure that we can detect when the first range is not the shortest.596TEST(ZipIteratorTest, ZipFirstNotShortest) {597 const std::array<unsigned, 6> longer = {};598 const std::array<unsigned, 4> shorter = {};599 600 EXPECT_DEATH(zip_first(longer, shorter),601 "First iteratee is not the shortest");602 EXPECT_DEATH(zip_first(longer, shorter, longer),603 "First iteratee is not the shortest");604 EXPECT_DEATH(zip_first(longer, longer, shorter),605 "First iteratee is not the shortest");606}607#endif608 609TEST(ZipIteratorTest, ZipLongestBasic) {610 using namespace std;611 const vector<unsigned> pi{3, 1, 4, 1, 5, 9};612 const vector<StringRef> e{"2", "7", "1", "8"};613 614 {615 // Check left range longer than right.616 const vector<tuple<optional<unsigned>, optional<StringRef>>> expected{617 make_tuple(3, StringRef("2")), make_tuple(1, StringRef("7")),618 make_tuple(4, StringRef("1")), make_tuple(1, StringRef("8")),619 make_tuple(5, std::nullopt), make_tuple(9, std::nullopt)};620 size_t iters = 0;621 for (auto tup : zip_longest(pi, e)) {622 EXPECT_EQ(tup, expected[iters]);623 iters += 1;624 }625 EXPECT_EQ(iters, expected.size());626 }627 628 {629 // Check right range longer than left.630 const vector<tuple<optional<StringRef>, optional<unsigned>>> expected{631 make_tuple(StringRef("2"), 3), make_tuple(StringRef("7"), 1),632 make_tuple(StringRef("1"), 4), make_tuple(StringRef("8"), 1),633 make_tuple(std::nullopt, 5), make_tuple(std::nullopt, 9)};634 size_t iters = 0;635 for (auto tup : zip_longest(e, pi)) {636 EXPECT_EQ(tup, expected[iters]);637 iters += 1;638 }639 EXPECT_EQ(iters, expected.size());640 }641}642 643TEST(ZipIteratorTest, Mutability) {644 using namespace std;645 const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9};646 char message[] = "hello zip\0";647 648 for (auto tup : zip(pi, message, message)) {649 EXPECT_EQ(get<1>(tup), get<2>(tup));650 get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n';651 }652 653 // note the rvalue654 for (auto tup : zip(message, "yynyyyzip\0")) {655 EXPECT_EQ(get<0>(tup), get<1>(tup));656 }657}658 659TEST(ZipIteratorTest, ZipFirstMutability) {660 using namespace std;661 vector<unsigned> pi{3, 1, 4, 1, 5, 9};662 unsigned iters = 0;663 664 for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {665 get<1>(tup) = get<0>(tup);666 iters += 1;667 }668 669 EXPECT_EQ(iters, 4u);670 671 for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {672 EXPECT_EQ(get<0>(tup), get<1>(tup));673 }674}675 676TEST(ZipIteratorTest, Filter) {677 using namespace std;678 vector<unsigned> pi{3, 1, 4, 1, 5, 9};679 680 unsigned iters = 0;681 // pi is length 6, but the zip RHS is length 7.682 auto zipped = zip_first(pi, vector<bool>{1, 1, 0, 1, 1, 1, 0});683 for (auto tup : make_filter_range(684 zipped, [](decltype(zipped)::value_type t) { return get<1>(t); })) {685 EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));686 get<0>(tup) += 1;687 iters += 1;688 }689 690 // Should have skipped pi[2].691 EXPECT_EQ(iters, 5u);692 693 // Ensure that in-place mutation works.694 EXPECT_TRUE(all_of(pi, [](unsigned n) { return (n & 0x01) == 0; }));695}696 697TEST(ZipIteratorTest, Reverse) {698 using namespace std;699 vector<unsigned> ascending{0, 1, 2, 3, 4, 5};700 701 auto zipped = zip_first(ascending, vector<bool>{0, 1, 0, 1, 0, 1});702 unsigned last = 6;703 for (auto tup : reverse(zipped)) {704 // Check that this is in reverse.705 EXPECT_LT(get<0>(tup), last);706 last = get<0>(tup);707 EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));708 }709 710 auto odds = [](decltype(zipped)::value_type tup) { return get<1>(tup); };711 last = 6;712 for (auto tup : make_filter_range(reverse(zipped), odds)) {713 EXPECT_LT(get<0>(tup), last);714 last = get<0>(tup);715 EXPECT_TRUE(get<0>(tup) & 0x01);716 get<0>(tup) += 1;717 }718 719 // Ensure that in-place mutation works.720 EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; }));721}722 723// Int iterator that keeps track of the number of its copies.724struct CountingIntIterator : IntIterator {725 unsigned *cnt;726 727 CountingIntIterator(int *it, unsigned &counter)728 : IntIterator(it), cnt(&counter) {}729 730 CountingIntIterator(const CountingIntIterator &other)731 : IntIterator(other.I), cnt(other.cnt) {732 ++(*cnt);733 }734 CountingIntIterator &operator=(const CountingIntIterator &other) {735 this->I = other.I;736 this->cnt = other.cnt;737 ++(*cnt);738 return *this;739 }740};741 742// Check that the iterators do not get copied with each `zippy` iterator743// increment.744TEST(ZipIteratorTest, IteratorCopies) {745 std::vector<int> ints(1000, 42);746 unsigned total_copy_count = 0;747 CountingIntIterator begin(ints.data(), total_copy_count);748 CountingIntIterator end(ints.data() + ints.size(), total_copy_count);749 750 size_t iters = 0;751 auto zippy = zip_equal(ints, llvm::make_range(begin, end));752 const unsigned creation_copy_count = total_copy_count;753 754 for (auto [a, b] : zippy) {755 EXPECT_EQ(a, b);756 ++iters;757 }758 EXPECT_EQ(iters, ints.size());759 760 // We expect the number of copies to be much smaller than the number of loop761 // iterations.762 unsigned loop_copy_count = total_copy_count - creation_copy_count;763 EXPECT_LT(loop_copy_count, 10u);764}765 766TEST(RangeTest, Distance) {767 std::vector<int> v1;768 std::vector<int> v2{1, 2, 3};769 770 EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1));771 EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(v2));772}773 774TEST(RangeSizeTest, CommonRangeTypes) {775 SmallVector<int> v1 = {1, 2, 3};776 EXPECT_EQ(range_size(v1), 3u);777 778 std::map<int, int> m1 = {{1, 1}, {2, 2}};779 EXPECT_EQ(range_size(m1), 2u);780 781 auto it_range = llvm::make_range(m1.begin(), m1.end());782 EXPECT_EQ(range_size(it_range), 2u);783 784 static constexpr int c_arr[5] = {};785 static_assert(range_size(c_arr) == 5u);786 787 static constexpr std::array<int, 6> cpp_arr = {};788 static_assert(range_size(cpp_arr) == 6u);789}790 791struct FooWithMemberSize {792 size_t size() const { return 42; }793 auto begin() { return Data.begin(); }794 auto end() { return Data.end(); }795 796 std::set<int> Data;797};798 799TEST(RangeSizeTest, MemberSize) {800 // Make sure that member `.size()` is preferred over the free fuction and801 // `std::distance`.802 FooWithMemberSize container;803 EXPECT_EQ(range_size(container), 42u);804}805 806struct FooWithFreeSize {807 friend size_t size(const FooWithFreeSize &) { return 13; }808 auto begin() { return Data.begin(); }809 auto end() { return Data.end(); }810 811 std::set<int> Data;812};813 814TEST(RangeSizeTest, FreeSize) {815 // Make sure that `size(x)` is preferred over `std::distance`.816 FooWithFreeSize container;817 EXPECT_EQ(range_size(container), 13u);818}819 820struct FooWithDistance {821 auto begin() { return Data.begin(); }822 auto end() { return Data.end(); }823 824 std::set<int> Data;825};826 827TEST(RangeSizeTest, Distance) {828 // Make sure that we can fall back to `std::distance` even the iterator is not829 // random-access.830 FooWithDistance container;831 EXPECT_EQ(range_size(container), 0u);832 container.Data = {1, 2, 3, 4};833 EXPECT_EQ(range_size(container), 4u);834}835} // anonymous namespace836