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 namespace rbegin_detail {
 399 struct WithFreeRBegin {
 400   int data[3] = {42, 43, 44};
 401 };
 402
 403 auto rbegin(const WithFreeRBegin &X) { return std::rbegin(X.data); }
 404 auto rend(const WithFreeRBegin &X) { return std::rend(X.data); }
 405 } // namespace rbegin_detail
 406
 407 TEST(ReverseTest, ADL) {
 408   // Check that we can find the rbegin/rend functions via ADL.
 409   rbegin_detail::WithFreeRBegin Foo;
 410   EXPECT_THAT(reverse(Foo), ElementsAre(44, 43, 42));
 411 }
 412
 413 TEST(ZipIteratorTest, Basic) {
 414   using namespace std;
 415   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
 416   SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1};
 417   const char message[] = "yynyyy\0";
 418   std::array<int, 2> shortArr = {42, 43};
 419
 420   for (auto tup : zip(pi, odd, message)) {
 421     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
 422     EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup));
 423   }
 424
 425   // Note the rvalue.
 426   for (auto tup : zip(pi, SmallVector<bool, 0>{1, 1, 0, 1, 1})) {
 427     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
 428   }
 429
 430   // Iterate until we run out elements in the *shortest* range.
 431   for (auto [idx, elem] : enumerate(zip(odd, shortArr))) {
 432     EXPECT_LT(idx, static_cast<size_t>(2));
 433   }
 434   for (auto [idx, elem] : enumerate(zip(shortArr, odd))) {
 435     EXPECT_LT(idx, static_cast<size_t>(2));
 436   }
 437 }
 438
 439 TEST(ZipIteratorTest, ZipEqualBasic) {
 440   const SmallVector<unsigned, 6> pi = {3, 1, 4, 1, 5, 8};
 441   const SmallVector<bool, 6> vals = {1, 1, 0, 1, 1, 0};
 442   unsigned iters = 0;
 443
 444   for (auto [lhs, rhs] : zip_equal(vals, pi)) {
 445     EXPECT_EQ(lhs, rhs & 0x01);
 446     ++iters;
 447   }
 448
 449   EXPECT_EQ(iters, 6u);
 450 }
 451
 452 template <typename T>
 453 constexpr bool IsConstRef =
 454     std::is_reference_v<T> && std::is_const_v<std::remove_reference_t<T>>;
 455
 456 template <typename T>
 457 constexpr bool IsBoolConstRef =
 458     std::is_same_v<llvm::remove_cvref_t<T>, std::vector<bool>::const_reference>;
 459
 460 /// Returns a `const` copy of the passed value. The `const` on the returned
 461 /// value is intentional here so that `MakeConst` can be used in range-for
 462 /// loops.
 463 template <typename T> const T MakeConst(T &&value) {
 464   return std::forward<T>(value);
 465 }
 466
 467 TEST(ZipIteratorTest, ZipEqualConstCorrectness) {
 468   const std::vector<unsigned> c_first = {3, 1, 4};
 469   std::vector<unsigned> first = c_first;
 470   const SmallVector<bool> c_second = {1, 1, 0};
 471   SmallVector<bool> second = c_second;
 472
 473   for (auto [a, b, c, d] : zip_equal(c_first, first, c_second, second)) {
 474     b = 0;
 475     d = true;
 476     static_assert(IsConstRef<decltype(a)>);
 477     static_assert(!IsConstRef<decltype(b)>);
 478     static_assert(IsConstRef<decltype(c)>);
 479     static_assert(!IsConstRef<decltype(d)>);
 480   }
 481
 482   EXPECT_THAT(first, ElementsAre(0, 0, 0));
 483   EXPECT_THAT(second, ElementsAre(true, true, true));
 484
 485   std::vector<bool> nemesis = {true, false, true};
 486   const std::vector<bool> c_nemesis = nemesis;
 487
 488   for (auto &&[a, b, c, d] : zip_equal(first, c_first, nemesis, c_nemesis)) {
 489     a = 2;
 490     c = true;
 491     static_assert(!IsConstRef<decltype(a)>);
 492     static_assert(IsConstRef<decltype(b)>);
 493     static_assert(!IsBoolConstRef<decltype(c)>);
 494     static_assert(IsBoolConstRef<decltype(d)>);
 495   }
 496
 497   EXPECT_THAT(first, ElementsAre(2, 2, 2));
 498   EXPECT_THAT(nemesis, ElementsAre(true, true, true));
 499
 500   unsigned iters = 0;
 501   for (const auto &[a, b, c, d] :
 502        zip_equal(first, c_first, nemesis, c_nemesis)) {
 503     static_assert(!IsConstRef<decltype(a)>);
 504     static_assert(IsConstRef<decltype(b)>);
 505     static_assert(!IsBoolConstRef<decltype(c)>);
 506     static_assert(IsBoolConstRef<decltype(d)>);
 507     ++iters;
 508   }
 509   EXPECT_EQ(iters, 3u);
 510   iters = 0;
 511
 512   for (const auto &[a, b, c, d] :
 513        MakeConst(zip_equal(first, c_first, nemesis, c_nemesis))) {
 514     static_assert(!IsConstRef<decltype(a)>);
 515     static_assert(IsConstRef<decltype(b)>);
 516     static_assert(!IsBoolConstRef<decltype(c)>);
 517     static_assert(IsBoolConstRef<decltype(d)>);
 518     ++iters;
 519   }
 520   EXPECT_EQ(iters, 3u);
 521 }
 522
 523 TEST(ZipIteratorTest, ZipEqualTemporaries) {
 524   unsigned iters = 0;
 525
 526   // These temporary ranges get moved into the `tuple<...> storage;` inside
 527   // `zippy`. From then on, we can use references obtained from this storage to
 528   // access them. This does not rely on any lifetime extensions on the
 529   // temporaries passed to `zip_equal`.
 530   for (auto [a, b, c] : zip_equal(SmallVector<int>{1, 2, 3}, std::string("abc"),
 531                                   std::vector<bool>{true, false, true})) {
 532     a = 3;
 533     b = 'c';
 534     c = false;
 535     static_assert(!IsConstRef<decltype(a)>);
 536     static_assert(!IsConstRef<decltype(b)>);
 537     static_assert(!IsBoolConstRef<decltype(c)>);
 538     ++iters;
 539   }
 540   EXPECT_EQ(iters, 3u);
 541   iters = 0;
 542
 543   for (auto [a, b, c] :
 544        MakeConst(zip_equal(SmallVector<int>{1, 2, 3}, std::string("abc"),
 545                            std::vector<bool>{true, false, true}))) {
 546     static_assert(IsConstRef<decltype(a)>);
 547     static_assert(IsConstRef<decltype(b)>);
 548     static_assert(IsBoolConstRef<decltype(c)>);
 549     ++iters;
 550   }
 551   EXPECT_EQ(iters, 3u);
 552 }
 553
 554 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
 555 // Check that an assertion is triggered when ranges passed to `zip_equal` differ
 556 // in length.
 557 TEST(ZipIteratorTest, ZipEqualNotEqual) {
 558   const SmallVector<unsigned, 6> pi = {3, 1, 4, 1, 5, 8};
 559   const SmallVector<bool, 2> vals = {1, 1};
 560
 561   EXPECT_DEATH(zip_equal(pi, vals), "Iteratees do not have equal length");
 562   EXPECT_DEATH(zip_equal(vals, pi), "Iteratees do not have equal length");
 563   EXPECT_DEATH(zip_equal(pi, pi, vals), "Iteratees do not have equal length");
 564   EXPECT_DEATH(zip_equal(vals, vals, pi), "Iteratees do not have equal length");
 565 }
 566 #endif
 567
 568 TEST(ZipIteratorTest, ZipFirstBasic) {
 569   using namespace std;
 570   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
 571   unsigned iters = 0;
 572
 573   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
 574     EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01);
 575     iters += 1;
 576   }
 577
 578   EXPECT_EQ(iters, 4u);
 579 }
 580
 581 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
 582 // Make sure that we can detect when the first range is not the shortest.
 583 TEST(ZipIteratorTest, ZipFirstNotShortest) {
 584   const std::array<unsigned, 6> longer = {};
 585   const std::array<unsigned, 4> shorter = {};
 586
 587   EXPECT_DEATH(zip_first(longer, shorter),
 588                "First iteratee is not the shortest");
 589   EXPECT_DEATH(zip_first(longer, shorter, longer),
 590                "First iteratee is not the shortest");
 591   EXPECT_DEATH(zip_first(longer, longer, shorter),
 592                "First iteratee is not the shortest");
 593 }
 594 #endif
 595
 596 TEST(ZipIteratorTest, ZipLongestBasic) {
 597   using namespace std;
 598   const vector<unsigned> pi{3, 1, 4, 1, 5, 9};
 599   const vector<StringRef> e{"2", "7", "1", "8"};
 600
 601   {
 602     // Check left range longer than right.
 603     const vector<tuple<optional<unsigned>, optional<StringRef>>> expected{
 604         make_tuple(3, StringRef("2")), make_tuple(1, StringRef("7")),
 605         make_tuple(4, StringRef("1")), make_tuple(1, StringRef("8")),
 606         make_tuple(5, std::nullopt),   make_tuple(9, std::nullopt)};
 607     size_t iters = 0;
 608     for (auto tup : zip_longest(pi, e)) {
 609       EXPECT_EQ(tup, expected[iters]);
 610       iters += 1;
 611     }
 612     EXPECT_EQ(iters, expected.size());
 613   }
 614
 615   {
 616     // Check right range longer than left.
 617     const vector<tuple<optional<StringRef>, optional<unsigned>>> expected{
 618         make_tuple(StringRef("2"), 3), make_tuple(StringRef("7"), 1),
 619         make_tuple(StringRef("1"), 4), make_tuple(StringRef("8"), 1),
 620         make_tuple(std::nullopt, 5),   make_tuple(std::nullopt, 9)};
 621     size_t iters = 0;
 622     for (auto tup : zip_longest(e, pi)) {
 623       EXPECT_EQ(tup, expected[iters]);
 624       iters += 1;
 625     }
 626     EXPECT_EQ(iters, expected.size());
 627   }
 628 }
 629
 630 TEST(ZipIteratorTest, Mutability) {
 631   using namespace std;
 632   const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9};
 633   char message[] = "hello zip\0";
 634
 635   for (auto tup : zip(pi, message, message)) {
 636     EXPECT_EQ(get<1>(tup), get<2>(tup));
 637     get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n';
 638   }
 639
 640   // note the rvalue
 641   for (auto tup : zip(message, "yynyyyzip\0")) {
 642     EXPECT_EQ(get<0>(tup), get<1>(tup));
 643   }
 644 }
 645
 646 TEST(ZipIteratorTest, ZipFirstMutability) {
 647   using namespace std;
 648   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
 649   unsigned iters = 0;
 650
 651   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
 652     get<1>(tup) = get<0>(tup);
 653     iters += 1;
 654   }
 655
 656   EXPECT_EQ(iters, 4u);
 657
 658   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
 659     EXPECT_EQ(get<0>(tup), get<1>(tup));
 660   }
 661 }
 662
 663 TEST(ZipIteratorTest, Filter) {
 664   using namespace std;
 665   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
 666
 667   unsigned iters = 0;
 668   // pi is length 6, but the zip RHS is length 7.
 669   auto zipped = zip_first(pi, vector<bool>{1, 1, 0, 1, 1, 1, 0});
 670   for (auto tup : make_filter_range(
 671            zipped, [](decltype(zipped)::value_type t) { return get<1>(t); })) {
 672     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
 673     get<0>(tup) += 1;
 674     iters += 1;
 675   }
 676
 677   // Should have skipped pi[2].
 678   EXPECT_EQ(iters, 5u);
 679
 680   // Ensure that in-place mutation works.
 681   EXPECT_TRUE(all_of(pi, [](unsigned n) { return (n & 0x01) == 0; }));
 682 }
 683
 684 TEST(ZipIteratorTest, Reverse) {
 685   using namespace std;
 686   vector<unsigned> ascending{0, 1, 2, 3, 4, 5};
 687
 688   auto zipped = zip_first(ascending, vector<bool>{0, 1, 0, 1, 0, 1});
 689   unsigned last = 6;
 690   for (auto tup : reverse(zipped)) {
 691     // Check that this is in reverse.
 692     EXPECT_LT(get<0>(tup), last);
 693     last = get<0>(tup);
 694     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
 695   }
 696
 697   auto odds = [](decltype(zipped)::value_type tup) { return get<1>(tup); };
 698   last = 6;
 699   for (auto tup : make_filter_range(reverse(zipped), odds)) {
 700     EXPECT_LT(get<0>(tup), last);
 701     last = get<0>(tup);
 702     EXPECT_TRUE(get<0>(tup) & 0x01);
 703     get<0>(tup) += 1;
 704   }
 705
 706   // Ensure that in-place mutation works.
 707   EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; }));
 708 }
 709
 710 // Int iterator that keeps track of the number of its copies.
 711 struct CountingIntIterator : IntIterator {
 712   unsigned *cnt;
 713
 714   CountingIntIterator(int *it, unsigned &counter)
 715       : IntIterator(it), cnt(&counter) {}
 716
 717   CountingIntIterator(const CountingIntIterator &other)
 718       : IntIterator(other.I), cnt(other.cnt) {
 719     ++(*cnt);
 720   }
 721   CountingIntIterator &operator=(const CountingIntIterator &other) {
 722     this->I = other.I;
 723     this->cnt = other.cnt;
 724     ++(*cnt);
 725     return *this;
 726   }
 727 };
 728
 729 // Check that the iterators do not get copied with each `zippy` iterator
 730 // increment.
 731 TEST(ZipIteratorTest, IteratorCopies) {
 732   std::vector<int> ints(1000, 42);
 733   unsigned total_copy_count = 0;
 734   CountingIntIterator begin(ints.data(), total_copy_count);
 735   CountingIntIterator end(ints.data() + ints.size(), total_copy_count);
 736
 737   size_t iters = 0;
 738   auto zippy = zip_equal(ints, llvm::make_range(begin, end));
 739   const unsigned creation_copy_count = total_copy_count;
 740
 741   for (auto [a, b] : zippy) {
 742     EXPECT_EQ(a, b);
 743     ++iters;
 744   }
 745   EXPECT_EQ(iters, ints.size());
 746
 747   // We expect the number of copies to be much smaller than the number of loop
 748   // iterations.
 749   unsigned loop_copy_count = total_copy_count - creation_copy_count;
 750   EXPECT_LT(loop_copy_count, 10u);
 751 }
 752
 753 TEST(RangeTest, Distance) {
 754   std::vector<int> v1;
 755   std::vector<int> v2{1, 2, 3};
 756
 757   EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1));
 758   EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(v2));
 759 }
 760
 761 TEST(RangeSizeTest, CommonRangeTypes) {
 762   SmallVector<int> v1 = {1, 2, 3};
 763   EXPECT_EQ(range_size(v1), 3u);
 764
 765   std::map<int, int> m1 = {{1, 1}, {2, 2}};
 766   EXPECT_EQ(range_size(m1), 2u);
 767
 768   auto it_range = llvm::make_range(m1.begin(), m1.end());
 769   EXPECT_EQ(range_size(it_range), 2u);
 770
 771   static constexpr int c_arr[5] = {};
 772   static_assert(range_size(c_arr) == 5u);
 773
 774   static constexpr std::array<int, 6> cpp_arr = {};
 775   static_assert(range_size(cpp_arr) == 6u);
 776 }
 777
 778 struct FooWithMemberSize {
 779   size_t size() const { return 42; }
 780   auto begin() { return Data.begin(); }
 781   auto end() { return Data.end(); }
 782
 783   std::set<int> Data;
 784 };
 785
 786 TEST(RangeSizeTest, MemberSize) {
 787   // Make sure that member `.size()` is preferred over the free fuction and
 788   // `std::distance`.
 789   FooWithMemberSize container;
 790   EXPECT_EQ(range_size(container), 42u);
 791 }
 792
 793 struct FooWithFreeSize {
 794   friend size_t size(const FooWithFreeSize &) { return 13; }
 795   auto begin() { return Data.begin(); }
 796   auto end() { return Data.end(); }
 797
 798   std::set<int> Data;
 799 };
 800
 801 TEST(RangeSizeTest, FreeSize) {
 802   // Make sure that `size(x)` is preferred over `std::distance`.
 803   FooWithFreeSize container;
 804   EXPECT_EQ(range_size(container), 13u);
 805 }
 806
 807 struct FooWithDistance {
 808   auto begin() { return Data.begin(); }
 809   auto end() { return Data.end(); }
 810
 811   std::set<int> Data;
 812 };
 813
 814 TEST(RangeSizeTest, Distance) {
 815   // Make sure that we can fall back to `std::distance` even the iterator is not
 816   // random-access.
 817   FooWithDistance container;
 818   EXPECT_EQ(range_size(container), 0u);
 819   container.Data = {1, 2, 3, 4};
 820   EXPECT_EQ(range_size(container), 4u);
 821 }
 822 } // anonymous namespace