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/ilist.h"
  10 #include "llvm/ADT/iterator.h"
  11 #include "llvm/ADT/ArrayRef.h"
  12 #include "llvm/ADT/STLExtras.h"
  13 #include "llvm/ADT/SmallVector.h"
  14 #include "gtest/gtest.h"
  15
  16 using namespace llvm;
  17
  18 namespace {
  19
  20 template <int> struct Shadow;
  21
  22 struct WeirdIter : std::iterator<std::input_iterator_tag, Shadow<0>, Shadow<1>,
  23                                  Shadow<2>, Shadow<3>> {};
  24
  25 struct AdaptedIter : iterator_adaptor_base<AdaptedIter, WeirdIter> {};
  26
  27 // Test that iterator_adaptor_base forwards typedefs, if value_type is
  28 // unchanged.
  29 static_assert(std::is_same<typename AdaptedIter::value_type, Shadow<0>>::value,
  30               "");
  31 static_assert(
  32     std::is_same<typename AdaptedIter::difference_type, Shadow<1>>::value, "");
  33 static_assert(std::is_same<typename AdaptedIter::pointer, Shadow<2>>::value,
  34               "");
  35 static_assert(std::is_same<typename AdaptedIter::reference, Shadow<3>>::value,
  36               "");
  37
  38 // Ensure that pointe{e,r}_iterator adaptors correctly forward the category of
  39 // the underlying iterator.
  40
  41 using RandomAccessIter = SmallVectorImpl<int*>::iterator;
  42 using BidiIter = ilist<int*>::iterator;
  43
  44 template<class T>
  45 using pointee_iterator_defaulted = pointee_iterator<T>;
  46 template<class T>
  47 using pointer_iterator_defaulted = pointer_iterator<T>;
  48
  49 // Ensures that an iterator and its adaptation have the same iterator_category.
  50 template<template<typename> class A, typename It>
  51 using IsAdaptedIterCategorySame =
  52   std::is_same<typename std::iterator_traits<It>::iterator_category,
  53                typename std::iterator_traits<A<It>>::iterator_category>;
  54
  55 // pointeE_iterator
  56 static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,
  57                                         RandomAccessIter>::value, "");
  58 static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,
  59                                         BidiIter>::value, "");
  60 // pointeR_iterator
  61 static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,
  62                                         RandomAccessIter>::value, "");
  63 static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,
  64                                         BidiIter>::value, "");
  65
  66 TEST(PointeeIteratorTest, Basic) {
  67   int arr[4] = {1, 2, 3, 4};
  68   SmallVector<int *, 4> V;
  69   V.push_back(&arr[0]);
  70   V.push_back(&arr[1]);
  71   V.push_back(&arr[2]);
  72   V.push_back(&arr[3]);
  73
  74   typedef pointee_iterator<SmallVectorImpl<int *>::const_iterator>
  75       test_iterator;
  76
  77   test_iterator Begin, End;
  78   Begin = V.begin();
  79   End = test_iterator(V.end());
  80
  81   test_iterator I = Begin;
  82   for (int i = 0; i < 4; ++i) {
  83     EXPECT_EQ(*V[i], *I);
  84
  85     EXPECT_EQ(I, Begin + i);
  86     EXPECT_EQ(I, std::next(Begin, i));
  87     test_iterator J = Begin;
  88     J += i;
  89     EXPECT_EQ(I, J);
  90     EXPECT_EQ(*V[i], Begin[i]);
  91
  92     EXPECT_NE(I, End);
  93     EXPECT_GT(End, I);
  94     EXPECT_LT(I, End);
  95     EXPECT_GE(I, Begin);
  96     EXPECT_LE(Begin, I);
  97
  98     EXPECT_EQ(i, I - Begin);
  99     EXPECT_EQ(i, std::distance(Begin, I));
 100     EXPECT_EQ(Begin, I - i);
 101
 102     test_iterator K = I++;
 103     EXPECT_EQ(K, std::prev(I));
 104   }
 105   EXPECT_EQ(End, I);
 106 }
 107
 108 TEST(PointeeIteratorTest, SmartPointer) {
 109   SmallVector<std::unique_ptr<int>, 4> V;
 110   V.push_back(std::make_unique<int>(1));
 111   V.push_back(std::make_unique<int>(2));
 112   V.push_back(std::make_unique<int>(3));
 113   V.push_back(std::make_unique<int>(4));
 114
 115   typedef pointee_iterator<
 116       SmallVectorImpl<std::unique_ptr<int>>::const_iterator>
 117       test_iterator;
 118
 119   test_iterator Begin, End;
 120   Begin = V.begin();
 121   End = test_iterator(V.end());
 122
 123   test_iterator I = Begin;
 124   for (int i = 0; i < 4; ++i) {
 125     EXPECT_EQ(*V[i], *I);
 126
 127     EXPECT_EQ(I, Begin + i);
 128     EXPECT_EQ(I, std::next(Begin, i));
 129     test_iterator J = Begin;
 130     J += i;
 131     EXPECT_EQ(I, J);
 132     EXPECT_EQ(*V[i], Begin[i]);
 133
 134     EXPECT_NE(I, End);
 135     EXPECT_GT(End, I);
 136     EXPECT_LT(I, End);
 137     EXPECT_GE(I, Begin);
 138     EXPECT_LE(Begin, I);
 139
 140     EXPECT_EQ(i, I - Begin);
 141     EXPECT_EQ(i, std::distance(Begin, I));
 142     EXPECT_EQ(Begin, I - i);
 143
 144     test_iterator K = I++;
 145     EXPECT_EQ(K, std::prev(I));
 146   }
 147   EXPECT_EQ(End, I);
 148 }
 149
 150 TEST(PointeeIteratorTest, Range) {
 151   int A[] = {1, 2, 3, 4};
 152   SmallVector<int *, 4> V{&A[0], &A[1], &A[2], &A[3]};
 153
 154   int I = 0;
 155   for (int II : make_pointee_range(V))
 156     EXPECT_EQ(A[I++], II);
 157 }
 158
 159 TEST(PointeeIteratorTest, PointeeType) {
 160   struct S {
 161     int X;
 162     bool operator==(const S &RHS) const { return X == RHS.X; };
 163   };
 164   S A[] = {S{0}, S{1}};
 165   SmallVector<S *, 2> V{&A[0], &A[1]};
 166
 167   pointee_iterator<SmallVectorImpl<S *>::const_iterator, const S> I = V.begin();
 168   for (int j = 0; j < 2; ++j, ++I) {
 169     EXPECT_EQ(*V[j], *I);
 170   }
 171 }
 172
 173 TEST(FilterIteratorTest, Lambda) {
 174   auto IsOdd = [](int N) { return N % 2 == 1; };
 175   int A[] = {0, 1, 2, 3, 4, 5, 6};
 176   auto Range = make_filter_range(A, IsOdd);
 177   SmallVector<int, 3> Actual(Range.begin(), Range.end());
 178   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
 179 }
 180
 181 TEST(FilterIteratorTest, CallableObject) {
 182   int Counter = 0;
 183   struct Callable {
 184     int &Counter;
 185
 186     Callable(int &Counter) : Counter(Counter) {}
 187
 188     bool operator()(int N) {
 189       Counter++;
 190       return N % 2 == 1;
 191     }
 192   };
 193   Callable IsOdd(Counter);
 194   int A[] = {0, 1, 2, 3, 4, 5, 6};
 195   auto Range = make_filter_range(A, IsOdd);
 196   EXPECT_EQ(2, Counter);
 197   SmallVector<int, 3> Actual(Range.begin(), Range.end());
 198   EXPECT_GE(Counter, 7);
 199   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
 200 }
 201
 202 TEST(FilterIteratorTest, FunctionPointer) {
 203   bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; };
 204   int A[] = {0, 1, 2, 3, 4, 5, 6};
 205   auto Range = make_filter_range(A, IsOdd);
 206   SmallVector<int, 3> Actual(Range.begin(), Range.end());
 207   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
 208 }
 209
 210 TEST(FilterIteratorTest, Composition) {
 211   auto IsOdd = [](int N) { return N % 2 == 1; };
 212   std::unique_ptr<int> A[] = {std::make_unique<int>(0), std::make_unique<int>(1),
 213                               std::make_unique<int>(2), std::make_unique<int>(3),
 214                               std::make_unique<int>(4), std::make_unique<int>(5),
 215                               std::make_unique<int>(6)};
 216   using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>;
 217   auto Range = make_filter_range(
 218       make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))),
 219       IsOdd);
 220   SmallVector<int, 3> Actual(Range.begin(), Range.end());
 221   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
 222 }
 223
 224 TEST(FilterIteratorTest, InputIterator) {
 225   struct InputIterator
 226       : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> {
 227     using BaseT =
 228         iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag>;
 229
 230     InputIterator(int *It) : BaseT(It) {}
 231   };
 232
 233   auto IsOdd = [](int N) { return N % 2 == 1; };
 234   int A[] = {0, 1, 2, 3, 4, 5, 6};
 235   auto Range = make_filter_range(
 236       make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))),
 237       IsOdd);
 238   SmallVector<int, 3> Actual(Range.begin(), Range.end());
 239   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
 240 }
 241
 242 TEST(FilterIteratorTest, ReverseFilterRange) {
 243   auto IsOdd = [](int N) { return N % 2 == 1; };
 244   int A[] = {0, 1, 2, 3, 4, 5, 6};
 245
 246   // Check basic reversal.
 247   auto Range = reverse(make_filter_range(A, IsOdd));
 248   SmallVector<int, 3> Actual(Range.begin(), Range.end());
 249   EXPECT_EQ((SmallVector<int, 3>{5, 3, 1}), Actual);
 250
 251   // Check that the reverse of the reverse is the original.
 252   auto Range2 = reverse(reverse(make_filter_range(A, IsOdd)));
 253   SmallVector<int, 3> Actual2(Range2.begin(), Range2.end());
 254   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual2);
 255
 256   // Check empty ranges.
 257   auto Range3 = reverse(make_filter_range(ArrayRef<int>(), IsOdd));
 258   SmallVector<int, 0> Actual3(Range3.begin(), Range3.end());
 259   EXPECT_EQ((SmallVector<int, 0>{}), Actual3);
 260
 261   // Check that we don't skip the first element, provided it isn't filtered
 262   // away.
 263   auto IsEven = [](int N) { return N % 2 == 0; };
 264   auto Range4 = reverse(make_filter_range(A, IsEven));
 265   SmallVector<int, 4> Actual4(Range4.begin(), Range4.end());
 266   EXPECT_EQ((SmallVector<int, 4>{6, 4, 2, 0}), Actual4);
 267 }
 268
 269 TEST(PointerIterator, Basic) {
 270   int A[] = {1, 2, 3, 4};
 271   pointer_iterator<int *> Begin(std::begin(A)), End(std::end(A));
 272   EXPECT_EQ(A, *Begin);
 273   ++Begin;
 274   EXPECT_EQ(A + 1, *Begin);
 275   ++Begin;
 276   EXPECT_EQ(A + 2, *Begin);
 277   ++Begin;
 278   EXPECT_EQ(A + 3, *Begin);
 279   ++Begin;
 280   EXPECT_EQ(Begin, End);
 281 }
 282
 283 TEST(PointerIterator, Const) {
 284   int A[] = {1, 2, 3, 4};
 285   const pointer_iterator<int *> Begin(std::begin(A));
 286   EXPECT_EQ(A, *Begin);
 287   EXPECT_EQ(A + 1, std::next(*Begin, 1));
 288   EXPECT_EQ(A + 2, std::next(*Begin, 2));
 289   EXPECT_EQ(A + 3, std::next(*Begin, 3));
 290   EXPECT_EQ(A + 4, std::next(*Begin, 4));
 291 }
 292
 293 TEST(PointerIterator, Range) {
 294   int A[] = {1, 2, 3, 4};
 295   int I = 0;
 296   for (int *P : make_pointer_range(A))
 297     EXPECT_EQ(A + I++, P);
 298 }
 299
 300 TEST(ZipIteratorTest, Basic) {
 301   using namespace std;
 302   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
 303   SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1};
 304   const char message[] = "yynyyy\0";
 305
 306   for (auto tup : zip(pi, odd, message)) {
 307     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
 308     EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup));
 309   }
 310
 311   // note the rvalue
 312   for (auto tup : zip(pi, SmallVector<bool, 0>{1, 1, 0, 1, 1})) {
 313     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
 314   }
 315 }
 316
 317 TEST(ZipIteratorTest, ZipFirstBasic) {
 318   using namespace std;
 319   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
 320   unsigned iters = 0;
 321
 322   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
 323     EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01);
 324     iters += 1;
 325   }
 326
 327   EXPECT_EQ(iters, 4u);
 328 }
 329
 330 TEST(ZipIteratorTest, ZipLongestBasic) {
 331   using namespace std;
 332   const vector<unsigned> pi{3, 1, 4, 1, 5, 9};
 333   const vector<StringRef> e{"2", "7", "1", "8"};
 334
 335   {
 336     // Check left range longer than right.
 337     const vector<tuple<Optional<unsigned>, Optional<StringRef>>> expected{
 338         make_tuple(3, StringRef("2")), make_tuple(1, StringRef("7")),
 339         make_tuple(4, StringRef("1")), make_tuple(1, StringRef("8")),
 340         make_tuple(5, None),           make_tuple(9, None)};
 341     size_t iters = 0;
 342     for (auto tup : zip_longest(pi, e)) {
 343       EXPECT_EQ(tup, expected[iters]);
 344       iters += 1;
 345     }
 346     EXPECT_EQ(iters, expected.size());
 347   }
 348
 349   {
 350     // Check right range longer than left.
 351     const vector<tuple<Optional<StringRef>, Optional<unsigned>>> expected{
 352         make_tuple(StringRef("2"), 3), make_tuple(StringRef("7"), 1),
 353         make_tuple(StringRef("1"), 4), make_tuple(StringRef("8"), 1),
 354         make_tuple(None, 5),           make_tuple(None, 9)};
 355     size_t iters = 0;
 356     for (auto tup : zip_longest(e, pi)) {
 357       EXPECT_EQ(tup, expected[iters]);
 358       iters += 1;
 359     }
 360     EXPECT_EQ(iters, expected.size());
 361   }
 362 }
 363
 364 TEST(ZipIteratorTest, Mutability) {
 365   using namespace std;
 366   const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9};
 367   char message[] = "hello zip\0";
 368
 369   for (auto tup : zip(pi, message, message)) {
 370     EXPECT_EQ(get<1>(tup), get<2>(tup));
 371     get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n';
 372   }
 373
 374   // note the rvalue
 375   for (auto tup : zip(message, "yynyyyzip\0")) {
 376     EXPECT_EQ(get<0>(tup), get<1>(tup));
 377   }
 378 }
 379
 380 TEST(ZipIteratorTest, ZipFirstMutability) {
 381   using namespace std;
 382   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
 383   unsigned iters = 0;
 384
 385   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
 386     get<1>(tup) = get<0>(tup);
 387     iters += 1;
 388   }
 389
 390   EXPECT_EQ(iters, 4u);
 391
 392   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
 393     EXPECT_EQ(get<0>(tup), get<1>(tup));
 394   }
 395 }
 396
 397 TEST(ZipIteratorTest, Filter) {
 398   using namespace std;
 399   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
 400
 401   unsigned iters = 0;
 402   // pi is length 6, but the zip RHS is length 7.
 403   auto zipped = zip_first(pi, vector<bool>{1, 1, 0, 1, 1, 1, 0});
 404   for (auto tup : make_filter_range(
 405            zipped, [](decltype(zipped)::value_type t) { return get<1>(t); })) {
 406     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
 407     get<0>(tup) += 1;
 408     iters += 1;
 409   }
 410
 411   // Should have skipped pi[2].
 412   EXPECT_EQ(iters, 5u);
 413
 414   // Ensure that in-place mutation works.
 415   EXPECT_TRUE(all_of(pi, [](unsigned n) { return (n & 0x01) == 0; }));
 416 }
 417
 418 TEST(ZipIteratorTest, Reverse) {
 419   using namespace std;
 420   vector<unsigned> ascending{0, 1, 2, 3, 4, 5};
 421
 422   auto zipped = zip_first(ascending, vector<bool>{0, 1, 0, 1, 0, 1});
 423   unsigned last = 6;
 424   for (auto tup : reverse(zipped)) {
 425     // Check that this is in reverse.
 426     EXPECT_LT(get<0>(tup), last);
 427     last = get<0>(tup);
 428     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
 429   }
 430
 431   auto odds = [](decltype(zipped)::value_type tup) { return get<1>(tup); };
 432   last = 6;
 433   for (auto tup : make_filter_range(reverse(zipped), odds)) {
 434     EXPECT_LT(get<0>(tup), last);
 435     last = get<0>(tup);
 436     EXPECT_TRUE(get<0>(tup) & 0x01);
 437     get<0>(tup) += 1;
 438   }
 439
 440   // Ensure that in-place mutation works.
 441   EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; }));
 442 }
 443
 444 TEST(RangeTest, Distance) {
 445   std::vector<int> v1;
 446   std::vector<int> v2{1, 2, 3};
 447
 448   EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1));
 449   EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(v2));
 450 }
 451
 452 TEST(IteratorRangeTest, DropBegin) {
 453   SmallVector<int, 5> vec{0, 1, 2, 3, 4};
 454
 455   for (int n = 0; n < 5; ++n) {
 456     int i = n;
 457     for (auto &v : drop_begin(vec, n)) {
 458       EXPECT_EQ(v, i);
 459       i += 1;
 460     }
 461     EXPECT_EQ(i, 5);
 462   }
 463 }
 464
 465 } // anonymous namespace