//===- IteratorTest.cpp - Unit tests for iterator utilities ---------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #include "llvm/ADT/ilist.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "gtest/gtest.h" using namespace llvm; namespace { template struct Shadow; struct WeirdIter : std::iterator, Shadow<1>, Shadow<2>, Shadow<3>> {}; struct AdaptedIter : iterator_adaptor_base {}; // Test that iterator_adaptor_base forwards typedefs, if value_type is // unchanged. static_assert(std::is_same>::value, ""); static_assert( std::is_same>::value, ""); static_assert(std::is_same>::value, ""); static_assert(std::is_same>::value, ""); // Ensure that pointe{e,r}_iterator adaptors correctly forward the category of // the underlying iterator. using RandomAccessIter = SmallVectorImpl::iterator; using BidiIter = ilist::iterator; template using pointee_iterator_defaulted = pointee_iterator; template using pointer_iterator_defaulted = pointer_iterator; // Ensures that an iterator and its adaptation have the same iterator_category. template class A, typename It> using IsAdaptedIterCategorySame = std::is_same::iterator_category, typename std::iterator_traits>::iterator_category>; // pointeE_iterator static_assert(IsAdaptedIterCategorySame::value, ""); static_assert(IsAdaptedIterCategorySame::value, ""); // pointeR_iterator static_assert(IsAdaptedIterCategorySame::value, ""); static_assert(IsAdaptedIterCategorySame::value, ""); TEST(PointeeIteratorTest, Basic) { int arr[4] = {1, 2, 3, 4}; SmallVector V; V.push_back(&arr[0]); V.push_back(&arr[1]); V.push_back(&arr[2]); V.push_back(&arr[3]); typedef pointee_iterator::const_iterator> test_iterator; test_iterator Begin, End; Begin = V.begin(); End = test_iterator(V.end()); test_iterator I = Begin; for (int i = 0; i < 4; ++i) { EXPECT_EQ(*V[i], *I); EXPECT_EQ(I, Begin + i); EXPECT_EQ(I, std::next(Begin, i)); test_iterator J = Begin; J += i; EXPECT_EQ(I, J); EXPECT_EQ(*V[i], Begin[i]); EXPECT_NE(I, End); EXPECT_GT(End, I); EXPECT_LT(I, End); EXPECT_GE(I, Begin); EXPECT_LE(Begin, I); EXPECT_EQ(i, I - Begin); EXPECT_EQ(i, std::distance(Begin, I)); EXPECT_EQ(Begin, I - i); test_iterator K = I++; EXPECT_EQ(K, std::prev(I)); } EXPECT_EQ(End, I); } TEST(PointeeIteratorTest, SmartPointer) { SmallVector, 4> V; V.push_back(std::make_unique(1)); V.push_back(std::make_unique(2)); V.push_back(std::make_unique(3)); V.push_back(std::make_unique(4)); typedef pointee_iterator< SmallVectorImpl>::const_iterator> test_iterator; test_iterator Begin, End; Begin = V.begin(); End = test_iterator(V.end()); test_iterator I = Begin; for (int i = 0; i < 4; ++i) { EXPECT_EQ(*V[i], *I); EXPECT_EQ(I, Begin + i); EXPECT_EQ(I, std::next(Begin, i)); test_iterator J = Begin; J += i; EXPECT_EQ(I, J); EXPECT_EQ(*V[i], Begin[i]); EXPECT_NE(I, End); EXPECT_GT(End, I); EXPECT_LT(I, End); EXPECT_GE(I, Begin); EXPECT_LE(Begin, I); EXPECT_EQ(i, I - Begin); EXPECT_EQ(i, std::distance(Begin, I)); EXPECT_EQ(Begin, I - i); test_iterator K = I++; EXPECT_EQ(K, std::prev(I)); } EXPECT_EQ(End, I); } TEST(PointeeIteratorTest, Range) { int A[] = {1, 2, 3, 4}; SmallVector V{&A[0], &A[1], &A[2], &A[3]}; int I = 0; for (int II : make_pointee_range(V)) EXPECT_EQ(A[I++], II); } TEST(PointeeIteratorTest, PointeeType) { struct S { int X; bool operator==(const S &RHS) const { return X == RHS.X; }; }; S A[] = {S{0}, S{1}}; SmallVector V{&A[0], &A[1]}; pointee_iterator::const_iterator, const S> I = V.begin(); for (int j = 0; j < 2; ++j, ++I) { EXPECT_EQ(*V[j], *I); } } TEST(FilterIteratorTest, Lambda) { auto IsOdd = [](int N) { return N % 2 == 1; }; int A[] = {0, 1, 2, 3, 4, 5, 6}; auto Range = make_filter_range(A, IsOdd); SmallVector Actual(Range.begin(), Range.end()); EXPECT_EQ((SmallVector{1, 3, 5}), Actual); } TEST(FilterIteratorTest, CallableObject) { int Counter = 0; struct Callable { int &Counter; Callable(int &Counter) : Counter(Counter) {} bool operator()(int N) { Counter++; return N % 2 == 1; } }; Callable IsOdd(Counter); int A[] = {0, 1, 2, 3, 4, 5, 6}; auto Range = make_filter_range(A, IsOdd); EXPECT_EQ(2, Counter); SmallVector Actual(Range.begin(), Range.end()); EXPECT_GE(Counter, 7); EXPECT_EQ((SmallVector{1, 3, 5}), Actual); } TEST(FilterIteratorTest, FunctionPointer) { bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; }; int A[] = {0, 1, 2, 3, 4, 5, 6}; auto Range = make_filter_range(A, IsOdd); SmallVector Actual(Range.begin(), Range.end()); EXPECT_EQ((SmallVector{1, 3, 5}), Actual); } TEST(FilterIteratorTest, Composition) { auto IsOdd = [](int N) { return N % 2 == 1; }; std::unique_ptr A[] = {std::make_unique(0), std::make_unique(1), std::make_unique(2), std::make_unique(3), std::make_unique(4), std::make_unique(5), std::make_unique(6)}; using PointeeIterator = pointee_iterator *>; auto Range = make_filter_range( make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))), IsOdd); SmallVector Actual(Range.begin(), Range.end()); EXPECT_EQ((SmallVector{1, 3, 5}), Actual); } TEST(FilterIteratorTest, InputIterator) { struct InputIterator : iterator_adaptor_base { using BaseT = iterator_adaptor_base; InputIterator(int *It) : BaseT(It) {} }; auto IsOdd = [](int N) { return N % 2 == 1; }; int A[] = {0, 1, 2, 3, 4, 5, 6}; auto Range = make_filter_range( make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))), IsOdd); SmallVector Actual(Range.begin(), Range.end()); EXPECT_EQ((SmallVector{1, 3, 5}), Actual); } TEST(FilterIteratorTest, ReverseFilterRange) { auto IsOdd = [](int N) { return N % 2 == 1; }; int A[] = {0, 1, 2, 3, 4, 5, 6}; // Check basic reversal. auto Range = reverse(make_filter_range(A, IsOdd)); SmallVector Actual(Range.begin(), Range.end()); EXPECT_EQ((SmallVector{5, 3, 1}), Actual); // Check that the reverse of the reverse is the original. auto Range2 = reverse(reverse(make_filter_range(A, IsOdd))); SmallVector Actual2(Range2.begin(), Range2.end()); EXPECT_EQ((SmallVector{1, 3, 5}), Actual2); // Check empty ranges. auto Range3 = reverse(make_filter_range(ArrayRef(), IsOdd)); SmallVector Actual3(Range3.begin(), Range3.end()); EXPECT_EQ((SmallVector{}), Actual3); // Check that we don't skip the first element, provided it isn't filtered // away. auto IsEven = [](int N) { return N % 2 == 0; }; auto Range4 = reverse(make_filter_range(A, IsEven)); SmallVector Actual4(Range4.begin(), Range4.end()); EXPECT_EQ((SmallVector{6, 4, 2, 0}), Actual4); } TEST(PointerIterator, Basic) { int A[] = {1, 2, 3, 4}; pointer_iterator Begin(std::begin(A)), End(std::end(A)); EXPECT_EQ(A, *Begin); ++Begin; EXPECT_EQ(A + 1, *Begin); ++Begin; EXPECT_EQ(A + 2, *Begin); ++Begin; EXPECT_EQ(A + 3, *Begin); ++Begin; EXPECT_EQ(Begin, End); } TEST(PointerIterator, Const) { int A[] = {1, 2, 3, 4}; const pointer_iterator Begin(std::begin(A)); EXPECT_EQ(A, *Begin); EXPECT_EQ(A + 1, std::next(*Begin, 1)); EXPECT_EQ(A + 2, std::next(*Begin, 2)); EXPECT_EQ(A + 3, std::next(*Begin, 3)); EXPECT_EQ(A + 4, std::next(*Begin, 4)); } TEST(PointerIterator, Range) { int A[] = {1, 2, 3, 4}; int I = 0; for (int *P : make_pointer_range(A)) EXPECT_EQ(A + I++, P); } TEST(ZipIteratorTest, Basic) { using namespace std; const SmallVector pi{3, 1, 4, 1, 5, 9}; SmallVector odd{1, 1, 0, 1, 1, 1}; const char message[] = "yynyyy\0"; for (auto tup : zip(pi, odd, message)) { EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup)); } // note the rvalue for (auto tup : zip(pi, SmallVector{1, 1, 0, 1, 1})) { EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); } } TEST(ZipIteratorTest, ZipFirstBasic) { using namespace std; const SmallVector pi{3, 1, 4, 1, 5, 9}; unsigned iters = 0; for (auto tup : zip_first(SmallVector{1, 1, 0, 1}, pi)) { EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01); iters += 1; } EXPECT_EQ(iters, 4u); } TEST(ZipIteratorTest, ZipLongestBasic) { using namespace std; const vector pi{3, 1, 4, 1, 5, 9}; const vector e{"2", "7", "1", "8"}; { // Check left range longer than right. const vector, Optional>> expected{ make_tuple(3, StringRef("2")), make_tuple(1, StringRef("7")), make_tuple(4, StringRef("1")), make_tuple(1, StringRef("8")), make_tuple(5, None), make_tuple(9, None)}; size_t iters = 0; for (auto tup : zip_longest(pi, e)) { EXPECT_EQ(tup, expected[iters]); iters += 1; } EXPECT_EQ(iters, expected.size()); } { // Check right range longer than left. const vector, Optional>> expected{ make_tuple(StringRef("2"), 3), make_tuple(StringRef("7"), 1), make_tuple(StringRef("1"), 4), make_tuple(StringRef("8"), 1), make_tuple(None, 5), make_tuple(None, 9)}; size_t iters = 0; for (auto tup : zip_longest(e, pi)) { EXPECT_EQ(tup, expected[iters]); iters += 1; } EXPECT_EQ(iters, expected.size()); } } TEST(ZipIteratorTest, Mutability) { using namespace std; const SmallVector pi{3, 1, 4, 1, 5, 9}; char message[] = "hello zip\0"; for (auto tup : zip(pi, message, message)) { EXPECT_EQ(get<1>(tup), get<2>(tup)); get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n'; } // note the rvalue for (auto tup : zip(message, "yynyyyzip\0")) { EXPECT_EQ(get<0>(tup), get<1>(tup)); } } TEST(ZipIteratorTest, ZipFirstMutability) { using namespace std; vector pi{3, 1, 4, 1, 5, 9}; unsigned iters = 0; for (auto tup : zip_first(SmallVector{1, 1, 0, 1}, pi)) { get<1>(tup) = get<0>(tup); iters += 1; } EXPECT_EQ(iters, 4u); for (auto tup : zip_first(SmallVector{1, 1, 0, 1}, pi)) { EXPECT_EQ(get<0>(tup), get<1>(tup)); } } TEST(ZipIteratorTest, Filter) { using namespace std; vector pi{3, 1, 4, 1, 5, 9}; unsigned iters = 0; // pi is length 6, but the zip RHS is length 7. auto zipped = zip_first(pi, vector{1, 1, 0, 1, 1, 1, 0}); for (auto tup : make_filter_range( zipped, [](decltype(zipped)::value_type t) { return get<1>(t); })) { EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); get<0>(tup) += 1; iters += 1; } // Should have skipped pi[2]. EXPECT_EQ(iters, 5u); // Ensure that in-place mutation works. EXPECT_TRUE(all_of(pi, [](unsigned n) { return (n & 0x01) == 0; })); } TEST(ZipIteratorTest, Reverse) { using namespace std; vector ascending{0, 1, 2, 3, 4, 5}; auto zipped = zip_first(ascending, vector{0, 1, 0, 1, 0, 1}); unsigned last = 6; for (auto tup : reverse(zipped)) { // Check that this is in reverse. EXPECT_LT(get<0>(tup), last); last = get<0>(tup); EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); } auto odds = [](decltype(zipped)::value_type tup) { return get<1>(tup); }; last = 6; for (auto tup : make_filter_range(reverse(zipped), odds)) { EXPECT_LT(get<0>(tup), last); last = get<0>(tup); EXPECT_TRUE(get<0>(tup) & 0x01); get<0>(tup) += 1; } // Ensure that in-place mutation works. EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; })); } TEST(RangeTest, Distance) { std::vector v1; std::vector v2{1, 2, 3}; EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1)); EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(v2)); } } // anonymous namespace