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