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 // Check that dereferencing works correctly adapting pointers and proxies. 56 template <class T> 57 struct PointerWrapper : public iterator_adaptor_base<PointerWrapper<T>, T *> { 58 PointerWrapper(T *I) : PointerWrapper::iterator_adaptor_base(I) {} 59 }; 60 struct IntProxy { 61 int &I; 62 IntProxy(int &I) : I(I) {} 63 void operator=(int NewValue) { I = NewValue; } 64 }; 65 struct ConstIntProxy { 66 const int &I; 67 ConstIntProxy(const int &I) : I(I) {} 68 }; 69 template <class T, class ProxyT> 70 struct PointerProxyWrapper 71 : public iterator_adaptor_base<PointerProxyWrapper<T, ProxyT>, T *, 72 std::random_access_iterator_tag, T, 73 ptrdiff_t, T *, ProxyT> { 74 PointerProxyWrapper(T *I) : PointerProxyWrapper::iterator_adaptor_base(I) {} 75 }; 76 using IntIterator = PointerWrapper<int>; 77 using ConstIntIterator = PointerWrapper<const int>; 78 using IntProxyIterator = PointerProxyWrapper<int, IntProxy>; 79 using ConstIntProxyIterator = PointerProxyWrapper<const int, ConstIntProxy>; 80 81 // There should only be a single (const-qualified) operator*, operator->, and 82 // operator[]. This test confirms that there isn't a non-const overload. Rather 83 // than adding those, users should double-check that T, PointerT, and ReferenceT 84 // have the right constness, and/or make fields mutable. 85 static_assert(&IntIterator::operator* == &IntIterator::operator*, ""); 86 static_assert(&IntIterator::operator-> == &IntIterator::operator->, ""); 87 static_assert(&IntIterator::operator[] == &IntIterator::operator[], ""); 88 89 template <class T, 90 std::enable_if_t<std::is_assignable<T, int>::value, bool> = false> 91 constexpr bool canAssignFromInt(T &&) { 92 return true; 93 } 94 template <class T, 95 std::enable_if_t<!std::is_assignable<T, int>::value, bool> = false> 96 constexpr bool canAssignFromInt(T &&) { 97 return false; 98 } 99 100 TEST(IteratorAdaptorTest, Dereference) { 101 int Number = 1; 102 103 // Construct some iterators and check whether they can be assigned to. 104 IntIterator I(&Number); 105 const IntIterator IC(&Number); 106 ConstIntIterator CI(&Number); 107 const ConstIntIterator CIC(&Number); 108 EXPECT_EQ(true, canAssignFromInt(*I)); // int * 109 EXPECT_EQ(true, canAssignFromInt(*IC)); // int *const 110 EXPECT_EQ(false, canAssignFromInt(*CI)); // const int * 111 EXPECT_EQ(false, canAssignFromInt(*CIC)); // const int *const 112 113 // Prove that dereference and assignment work. 114 EXPECT_EQ(1, *I); 115 EXPECT_EQ(1, *IC); 116 EXPECT_EQ(1, *CI); 117 EXPECT_EQ(1, *CIC); 118 *I = 2; 119 EXPECT_EQ(2, Number); 120 *IC = 3; 121 EXPECT_EQ(3, Number); 122 123 // Construct some proxy iterators and check whether they can be assigned to. 124 IntProxyIterator P(&Number); 125 const IntProxyIterator PC(&Number); 126 ConstIntProxyIterator CP(&Number); 127 const ConstIntProxyIterator CPC(&Number); 128 EXPECT_EQ(true, canAssignFromInt(*P)); // int * 129 EXPECT_EQ(true, canAssignFromInt(*PC)); // int *const 130 EXPECT_EQ(false, canAssignFromInt(*CP)); // const int * 131 EXPECT_EQ(false, canAssignFromInt(*CPC)); // const int *const 132 133 // Prove that dereference and assignment work. 134 EXPECT_EQ(3, (*P).I); 135 EXPECT_EQ(3, (*PC).I); 136 EXPECT_EQ(3, (*CP).I); 137 EXPECT_EQ(3, (*CPC).I); 138 *P = 4; 139 EXPECT_EQ(4, Number); 140 *PC = 5; 141 EXPECT_EQ(5, Number); 142 } 143 144 // pointeE_iterator 145 static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted, 146 RandomAccessIter>::value, ""); 147 static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted, 148 BidiIter>::value, ""); 149 // pointeR_iterator 150 static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted, 151 RandomAccessIter>::value, ""); 152 static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted, 153 BidiIter>::value, ""); 154 155 TEST(PointeeIteratorTest, Basic) { 156 int arr[4] = {1, 2, 3, 4}; 157 SmallVector<int *, 4> V; 158 V.push_back(&arr[0]); 159 V.push_back(&arr[1]); 160 V.push_back(&arr[2]); 161 V.push_back(&arr[3]); 162 163 typedef pointee_iterator<SmallVectorImpl<int *>::const_iterator> 164 test_iterator; 165 166 test_iterator Begin, End; 167 Begin = V.begin(); 168 End = test_iterator(V.end()); 169 170 test_iterator I = Begin; 171 for (int i = 0; i < 4; ++i) { 172 EXPECT_EQ(*V[i], *I); 173 174 EXPECT_EQ(I, Begin + i); 175 EXPECT_EQ(I, std::next(Begin, i)); 176 test_iterator J = Begin; 177 J += i; 178 EXPECT_EQ(I, J); 179 EXPECT_EQ(*V[i], Begin[i]); 180 181 EXPECT_NE(I, End); 182 EXPECT_GT(End, I); 183 EXPECT_LT(I, End); 184 EXPECT_GE(I, Begin); 185 EXPECT_LE(Begin, I); 186 187 EXPECT_EQ(i, I - Begin); 188 EXPECT_EQ(i, std::distance(Begin, I)); 189 EXPECT_EQ(Begin, I - i); 190 191 test_iterator K = I++; 192 EXPECT_EQ(K, std::prev(I)); 193 } 194 EXPECT_EQ(End, I); 195 } 196 197 TEST(PointeeIteratorTest, SmartPointer) { 198 SmallVector<std::unique_ptr<int>, 4> V; 199 V.push_back(std::make_unique<int>(1)); 200 V.push_back(std::make_unique<int>(2)); 201 V.push_back(std::make_unique<int>(3)); 202 V.push_back(std::make_unique<int>(4)); 203 204 typedef pointee_iterator< 205 SmallVectorImpl<std::unique_ptr<int>>::const_iterator> 206 test_iterator; 207 208 test_iterator Begin, End; 209 Begin = V.begin(); 210 End = test_iterator(V.end()); 211 212 test_iterator I = Begin; 213 for (int i = 0; i < 4; ++i) { 214 EXPECT_EQ(*V[i], *I); 215 216 EXPECT_EQ(I, Begin + i); 217 EXPECT_EQ(I, std::next(Begin, i)); 218 test_iterator J = Begin; 219 J += i; 220 EXPECT_EQ(I, J); 221 EXPECT_EQ(*V[i], Begin[i]); 222 223 EXPECT_NE(I, End); 224 EXPECT_GT(End, I); 225 EXPECT_LT(I, End); 226 EXPECT_GE(I, Begin); 227 EXPECT_LE(Begin, I); 228 229 EXPECT_EQ(i, I - Begin); 230 EXPECT_EQ(i, std::distance(Begin, I)); 231 EXPECT_EQ(Begin, I - i); 232 233 test_iterator K = I++; 234 EXPECT_EQ(K, std::prev(I)); 235 } 236 EXPECT_EQ(End, I); 237 } 238 239 TEST(PointeeIteratorTest, Range) { 240 int A[] = {1, 2, 3, 4}; 241 SmallVector<int *, 4> V{&A[0], &A[1], &A[2], &A[3]}; 242 243 int I = 0; 244 for (int II : make_pointee_range(V)) 245 EXPECT_EQ(A[I++], II); 246 } 247 248 TEST(PointeeIteratorTest, PointeeType) { 249 struct S { 250 int X; 251 bool operator==(const S &RHS) const { return X == RHS.X; }; 252 }; 253 S A[] = {S{0}, S{1}}; 254 SmallVector<S *, 2> V{&A[0], &A[1]}; 255 256 pointee_iterator<SmallVectorImpl<S *>::const_iterator, const S> I = V.begin(); 257 for (int j = 0; j < 2; ++j, ++I) { 258 EXPECT_EQ(*V[j], *I); 259 } 260 } 261 262 TEST(FilterIteratorTest, Lambda) { 263 auto IsOdd = [](int N) { return N % 2 == 1; }; 264 int A[] = {0, 1, 2, 3, 4, 5, 6}; 265 auto Range = make_filter_range(A, IsOdd); 266 SmallVector<int, 3> Actual(Range.begin(), Range.end()); 267 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); 268 } 269 270 TEST(FilterIteratorTest, Enumerate) { 271 auto IsOdd = [](auto N) { return N.value() % 2 == 1; }; 272 int A[] = {0, 1, 2, 3, 4, 5, 6}; 273 auto Enumerate = llvm::enumerate(A); 274 SmallVector<int> Actual; 275 for (auto IndexedValue : make_filter_range(Enumerate, IsOdd)) 276 Actual.push_back(IndexedValue.value()); 277 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); 278 } 279 280 TEST(FilterIteratorTest, CallableObject) { 281 int Counter = 0; 282 struct Callable { 283 int &Counter; 284 285 Callable(int &Counter) : Counter(Counter) {} 286 287 bool operator()(int N) { 288 Counter++; 289 return N % 2 == 1; 290 } 291 }; 292 Callable IsOdd(Counter); 293 int A[] = {0, 1, 2, 3, 4, 5, 6}; 294 auto Range = make_filter_range(A, IsOdd); 295 EXPECT_EQ(2, Counter); 296 SmallVector<int, 3> Actual(Range.begin(), Range.end()); 297 EXPECT_GE(Counter, 7); 298 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); 299 } 300 301 TEST(FilterIteratorTest, FunctionPointer) { 302 bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; }; 303 int A[] = {0, 1, 2, 3, 4, 5, 6}; 304 auto Range = make_filter_range(A, IsOdd); 305 SmallVector<int, 3> Actual(Range.begin(), Range.end()); 306 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); 307 } 308 309 TEST(FilterIteratorTest, Composition) { 310 auto IsOdd = [](int N) { return N % 2 == 1; }; 311 std::unique_ptr<int> A[] = {std::make_unique<int>(0), std::make_unique<int>(1), 312 std::make_unique<int>(2), std::make_unique<int>(3), 313 std::make_unique<int>(4), std::make_unique<int>(5), 314 std::make_unique<int>(6)}; 315 using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>; 316 auto Range = make_filter_range( 317 make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))), 318 IsOdd); 319 SmallVector<int, 3> Actual(Range.begin(), Range.end()); 320 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); 321 } 322 323 TEST(FilterIteratorTest, InputIterator) { 324 struct InputIterator 325 : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> { 326 InputIterator(int *It) : InputIterator::iterator_adaptor_base(It) {} 327 }; 328 329 auto IsOdd = [](int N) { return N % 2 == 1; }; 330 int A[] = {0, 1, 2, 3, 4, 5, 6}; 331 auto Range = make_filter_range( 332 make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))), 333 IsOdd); 334 SmallVector<int, 3> Actual(Range.begin(), Range.end()); 335 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); 336 } 337 338 TEST(FilterIteratorTest, ReverseFilterRange) { 339 auto IsOdd = [](int N) { return N % 2 == 1; }; 340 int A[] = {0, 1, 2, 3, 4, 5, 6}; 341 342 // Check basic reversal. 343 auto Range = reverse(make_filter_range(A, IsOdd)); 344 SmallVector<int, 3> Actual(Range.begin(), Range.end()); 345 EXPECT_EQ((SmallVector<int, 3>{5, 3, 1}), Actual); 346 347 // Check that the reverse of the reverse is the original. 348 auto Range2 = reverse(reverse(make_filter_range(A, IsOdd))); 349 SmallVector<int, 3> Actual2(Range2.begin(), Range2.end()); 350 EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual2); 351 352 // Check empty ranges. 353 auto Range3 = reverse(make_filter_range(ArrayRef<int>(), IsOdd)); 354 SmallVector<int, 0> Actual3(Range3.begin(), Range3.end()); 355 EXPECT_EQ((SmallVector<int, 0>{}), Actual3); 356 357 // Check that we don't skip the first element, provided it isn't filtered 358 // away. 359 auto IsEven = [](int N) { return N % 2 == 0; }; 360 auto Range4 = reverse(make_filter_range(A, IsEven)); 361 SmallVector<int, 4> Actual4(Range4.begin(), Range4.end()); 362 EXPECT_EQ((SmallVector<int, 4>{6, 4, 2, 0}), Actual4); 363 } 364 365 TEST(PointerIterator, Basic) { 366 int A[] = {1, 2, 3, 4}; 367 pointer_iterator<int *> Begin(std::begin(A)), End(std::end(A)); 368 EXPECT_EQ(A, *Begin); 369 ++Begin; 370 EXPECT_EQ(A + 1, *Begin); 371 ++Begin; 372 EXPECT_EQ(A + 2, *Begin); 373 ++Begin; 374 EXPECT_EQ(A + 3, *Begin); 375 ++Begin; 376 EXPECT_EQ(Begin, End); 377 } 378 379 TEST(PointerIterator, Const) { 380 int A[] = {1, 2, 3, 4}; 381 const pointer_iterator<int *> Begin(std::begin(A)); 382 EXPECT_EQ(A, *Begin); 383 EXPECT_EQ(A + 1, std::next(*Begin, 1)); 384 EXPECT_EQ(A + 2, std::next(*Begin, 2)); 385 EXPECT_EQ(A + 3, std::next(*Begin, 3)); 386 EXPECT_EQ(A + 4, std::next(*Begin, 4)); 387 } 388 389 TEST(PointerIterator, Range) { 390 int A[] = {1, 2, 3, 4}; 391 int I = 0; 392 for (int *P : make_pointer_range(A)) 393 EXPECT_EQ(A + I++, P); 394 } 395 396 TEST(ZipIteratorTest, Basic) { 397 using namespace std; 398 const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9}; 399 SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1}; 400 const char message[] = "yynyyy\0"; 401 402 for (auto tup : zip(pi, odd, message)) { 403 EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); 404 EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup)); 405 } 406 407 // note the rvalue 408 for (auto tup : zip(pi, SmallVector<bool, 0>{1, 1, 0, 1, 1})) { 409 EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); 410 } 411 } 412 413 TEST(ZipIteratorTest, ZipFirstBasic) { 414 using namespace std; 415 const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9}; 416 unsigned iters = 0; 417 418 for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) { 419 EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01); 420 iters += 1; 421 } 422 423 EXPECT_EQ(iters, 4u); 424 } 425 426 TEST(ZipIteratorTest, ZipLongestBasic) { 427 using namespace std; 428 const vector<unsigned> pi{3, 1, 4, 1, 5, 9}; 429 const vector<StringRef> e{"2", "7", "1", "8"}; 430 431 { 432 // Check left range longer than right. 433 const vector<tuple<Optional<unsigned>, Optional<StringRef>>> expected{ 434 make_tuple(3, StringRef("2")), make_tuple(1, StringRef("7")), 435 make_tuple(4, StringRef("1")), make_tuple(1, StringRef("8")), 436 make_tuple(5, None), make_tuple(9, None)}; 437 size_t iters = 0; 438 for (auto tup : zip_longest(pi, e)) { 439 EXPECT_EQ(tup, expected[iters]); 440 iters += 1; 441 } 442 EXPECT_EQ(iters, expected.size()); 443 } 444 445 { 446 // Check right range longer than left. 447 const vector<tuple<Optional<StringRef>, Optional<unsigned>>> expected{ 448 make_tuple(StringRef("2"), 3), make_tuple(StringRef("7"), 1), 449 make_tuple(StringRef("1"), 4), make_tuple(StringRef("8"), 1), 450 make_tuple(None, 5), make_tuple(None, 9)}; 451 size_t iters = 0; 452 for (auto tup : zip_longest(e, pi)) { 453 EXPECT_EQ(tup, expected[iters]); 454 iters += 1; 455 } 456 EXPECT_EQ(iters, expected.size()); 457 } 458 } 459 460 TEST(ZipIteratorTest, Mutability) { 461 using namespace std; 462 const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9}; 463 char message[] = "hello zip\0"; 464 465 for (auto tup : zip(pi, message, message)) { 466 EXPECT_EQ(get<1>(tup), get<2>(tup)); 467 get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n'; 468 } 469 470 // note the rvalue 471 for (auto tup : zip(message, "yynyyyzip\0")) { 472 EXPECT_EQ(get<0>(tup), get<1>(tup)); 473 } 474 } 475 476 TEST(ZipIteratorTest, ZipFirstMutability) { 477 using namespace std; 478 vector<unsigned> pi{3, 1, 4, 1, 5, 9}; 479 unsigned iters = 0; 480 481 for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) { 482 get<1>(tup) = get<0>(tup); 483 iters += 1; 484 } 485 486 EXPECT_EQ(iters, 4u); 487 488 for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) { 489 EXPECT_EQ(get<0>(tup), get<1>(tup)); 490 } 491 } 492 493 TEST(ZipIteratorTest, Filter) { 494 using namespace std; 495 vector<unsigned> pi{3, 1, 4, 1, 5, 9}; 496 497 unsigned iters = 0; 498 // pi is length 6, but the zip RHS is length 7. 499 auto zipped = zip_first(pi, vector<bool>{1, 1, 0, 1, 1, 1, 0}); 500 for (auto tup : make_filter_range( 501 zipped, [](decltype(zipped)::value_type t) { return get<1>(t); })) { 502 EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); 503 get<0>(tup) += 1; 504 iters += 1; 505 } 506 507 // Should have skipped pi[2]. 508 EXPECT_EQ(iters, 5u); 509 510 // Ensure that in-place mutation works. 511 EXPECT_TRUE(all_of(pi, [](unsigned n) { return (n & 0x01) == 0; })); 512 } 513 514 TEST(ZipIteratorTest, Reverse) { 515 using namespace std; 516 vector<unsigned> ascending{0, 1, 2, 3, 4, 5}; 517 518 auto zipped = zip_first(ascending, vector<bool>{0, 1, 0, 1, 0, 1}); 519 unsigned last = 6; 520 for (auto tup : reverse(zipped)) { 521 // Check that this is in reverse. 522 EXPECT_LT(get<0>(tup), last); 523 last = get<0>(tup); 524 EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); 525 } 526 527 auto odds = [](decltype(zipped)::value_type tup) { return get<1>(tup); }; 528 last = 6; 529 for (auto tup : make_filter_range(reverse(zipped), odds)) { 530 EXPECT_LT(get<0>(tup), last); 531 last = get<0>(tup); 532 EXPECT_TRUE(get<0>(tup) & 0x01); 533 get<0>(tup) += 1; 534 } 535 536 // Ensure that in-place mutation works. 537 EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; })); 538 } 539 540 TEST(RangeTest, Distance) { 541 std::vector<int> v1; 542 std::vector<int> v2{1, 2, 3}; 543 544 EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1)); 545 EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(v2)); 546 } 547 548 } // anonymous namespace 549