1703 lines · cpp
1//===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/STLExtras.h"10#include "llvm/ADT/ArrayRef.h"11#include "llvm/ADT/StringRef.h"12#include "gmock/gmock.h"13#include "gtest/gtest.h"14 15#include <array>16#include <climits>17#include <cstddef>18#include <functional>19#include <initializer_list>20#include <iterator>21#include <list>22#include <tuple>23#include <type_traits>24#include <unordered_set>25#include <utility>26#include <vector>27 28using namespace llvm;29 30using testing::ElementsAre;31using testing::ElementsAreArray;32using testing::UnorderedElementsAre;33 34namespace {35 36int f(rank<0>) { return 0; }37int f(rank<1>) { return 1; }38int f(rank<2>) { return 2; }39int f(rank<4>) { return 4; }40 41TEST(STLExtrasTest, Rank) {42 // We shouldn't get ambiguities and should select the overload of the same43 // rank as the argument.44 EXPECT_EQ(0, f(rank<0>()));45 EXPECT_EQ(1, f(rank<1>()));46 EXPECT_EQ(2, f(rank<2>()));47 48 // This overload is missing so we end up back at 2.49 EXPECT_EQ(2, f(rank<3>()));50 51 // But going past 3 should work fine.52 EXPECT_EQ(4, f(rank<4>()));53 54 // And we can even go higher and just fall back to the last overload.55 EXPECT_EQ(4, f(rank<5>()));56 EXPECT_EQ(4, f(rank<6>()));57}58 59TEST(STLExtrasTest, EnumerateLValue) {60 // Test that a simple LValue can be enumerated and gives correct results with61 // multiple types, including the empty container.62 std::vector<char> foo = {'a', 'b', 'c'};63 using CharPairType = std::pair<std::size_t, char>;64 std::vector<CharPairType> CharResults;65 66 for (auto [index, value] : llvm::enumerate(foo)) {67 CharResults.emplace_back(index, value);68 }69 70 EXPECT_THAT(CharResults,71 ElementsAre(CharPairType(0u, 'a'), CharPairType(1u, 'b'),72 CharPairType(2u, 'c')));73 74 // Test a const range of a different type.75 using IntPairType = std::pair<std::size_t, int>;76 std::vector<IntPairType> IntResults;77 const std::vector<int> bar = {1, 2, 3};78 for (auto [index, value] : llvm::enumerate(bar)) {79 IntResults.emplace_back(index, value);80 }81 EXPECT_THAT(IntResults, ElementsAre(IntPairType(0u, 1), IntPairType(1u, 2),82 IntPairType(2u, 3)));83 84 // Test an empty range.85 IntResults.clear();86 const std::vector<int> baz{};87 for (auto [index, value] : llvm::enumerate(baz)) {88 IntResults.emplace_back(index, value);89 }90 EXPECT_TRUE(IntResults.empty());91}92 93TEST(STLExtrasTest, EnumerateModifyLValue) {94 // Test that you can modify the underlying entries of an lvalue range through95 // the enumeration iterator.96 std::vector<char> foo = {'a', 'b', 'c'};97 98 for (auto X : llvm::enumerate(foo)) {99 ++X.value();100 }101 EXPECT_THAT(foo, ElementsAre('b', 'c', 'd'));102 103 // Also test if this works with structured bindings.104 foo = {'a', 'b', 'c'};105 106 for (auto [index, value] : llvm::enumerate(foo)) {107 ++value;108 }109 EXPECT_THAT(foo, ElementsAre('b', 'c', 'd'));110}111 112TEST(STLExtrasTest, EnumerateRValueRef) {113 // Test that an rvalue can be enumerated.114 using PairType = std::pair<std::size_t, int>;115 std::vector<PairType> Results;116 117 auto Enumerator = llvm::enumerate(std::vector<int>{1, 2, 3});118 119 for (auto X : llvm::enumerate(std::vector<int>{1, 2, 3})) {120 Results.emplace_back(X.index(), X.value());121 }122 123 EXPECT_THAT(Results,124 ElementsAre(PairType(0u, 1), PairType(1u, 2), PairType(2u, 3)));125 126 // Also test if this works with structured bindings.127 Results.clear();128 129 for (auto [index, value] : llvm::enumerate(std::vector<int>{1, 2, 3})) {130 Results.emplace_back(index, value);131 }132 133 EXPECT_THAT(Results,134 ElementsAre(PairType(0u, 1), PairType(1u, 2), PairType(2u, 3)));135}136 137TEST(STLExtrasTest, EnumerateModifyRValue) {138 // Test that when enumerating an rvalue, modification still works (even if139 // this isn't terribly useful, it at least shows that we haven't snuck an140 // extra const in there somewhere.141 using PairType = std::pair<std::size_t, char>;142 std::vector<PairType> Results;143 144 for (auto X : llvm::enumerate(std::vector<char>{'1', '2', '3'})) {145 ++X.value();146 Results.emplace_back(X.index(), X.value());147 }148 149 EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),150 PairType(2u, '4')));151 152 // Also test if this works with structured bindings.153 Results.clear();154 155 for (auto [index, value] :156 llvm::enumerate(std::vector<char>{'1', '2', '3'})) {157 ++value;158 Results.emplace_back(index, value);159 }160 161 EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),162 PairType(2u, '4')));163}164 165TEST(STLExtrasTest, EnumerateTwoRanges) {166 using Tuple = std::tuple<size_t, int, bool>;167 168 std::vector<int> Ints = {1, 2};169 std::vector<bool> Bools = {true, false};170 EXPECT_THAT(llvm::enumerate(Ints, Bools),171 ElementsAre(Tuple(0, 1, true), Tuple(1, 2, false)));172 173 // Check that we can modify the values when the temporary is a const174 // reference.175 for (const auto &[Idx, Int, Bool] : llvm::enumerate(Ints, Bools)) {176 (void)Idx;177 Bool = false;178 Int = -1;179 }180 181 EXPECT_THAT(Ints, ElementsAre(-1, -1));182 EXPECT_THAT(Bools, ElementsAre(false, false));183 184 // Check that we can modify the values when the result gets copied.185 for (auto [Idx, Bool, Int] : llvm::enumerate(Bools, Ints)) {186 (void)Idx;187 Int = 3;188 Bool = true;189 }190 191 EXPECT_THAT(Ints, ElementsAre(3, 3));192 EXPECT_THAT(Bools, ElementsAre(true, true));193 194 // Check that we can modify the values through `.value()`.195 size_t Iters = 0;196 for (auto It : llvm::enumerate(Bools, Ints)) {197 EXPECT_EQ(It.index(), Iters);198 ++Iters;199 200 std::get<0>(It.value()) = false;201 std::get<1>(It.value()) = 4;202 }203 204 EXPECT_THAT(Ints, ElementsAre(4, 4));205 EXPECT_THAT(Bools, ElementsAre(false, false));206}207 208TEST(STLExtrasTest, EnumerateThreeRanges) {209 using Tuple = std::tuple<size_t, int, bool, char>;210 211 std::vector<int> Ints = {1, 2};212 std::vector<bool> Bools = {true, false};213 char Chars[] = {'X', 'D'};214 EXPECT_THAT(llvm::enumerate(Ints, Bools, Chars),215 ElementsAre(Tuple(0, 1, true, 'X'), Tuple(1, 2, false, 'D')));216 217 for (auto [Idx, Int, Bool, Char] : llvm::enumerate(Ints, Bools, Chars)) {218 (void)Idx;219 Int = 0;220 Bool = true;221 Char = '!';222 }223 224 EXPECT_THAT(Ints, ElementsAre(0, 0));225 EXPECT_THAT(Bools, ElementsAre(true, true));226 EXPECT_THAT(Chars, ElementsAre('!', '!'));227 228 // Check that we can modify the values through `.values()`.229 size_t Iters = 0;230 for (auto It : llvm::enumerate(Ints, Bools, Chars)) {231 EXPECT_EQ(It.index(), Iters);232 ++Iters;233 auto [Int, Bool, Char] = It.value();234 Int = 42;235 Bool = false;236 Char = '$';237 }238 239 EXPECT_THAT(Ints, ElementsAre(42, 42));240 EXPECT_THAT(Bools, ElementsAre(false, false));241 EXPECT_THAT(Chars, ElementsAre('$', '$'));242}243 244TEST(STLExtrasTest, EnumerateTemporaries) {245 using Tuple = std::tuple<size_t, int, bool>;246 247 EXPECT_THAT(248 llvm::enumerate(llvm::SmallVector<int>({1, 2, 3}),249 std::vector<bool>({true, false, true})),250 ElementsAre(Tuple(0, 1, true), Tuple(1, 2, false), Tuple(2, 3, true)));251 252 size_t Iters = 0;253 // This is fine from the point of view of range lifetimes because `zippy` will254 // move all temporaries into its storage. No lifetime extension is necessary.255 for (auto [Idx, Int, Bool] :256 llvm::enumerate(llvm::SmallVector<int>({1, 2, 3}),257 std::vector<bool>({true, false, true}))) {258 EXPECT_EQ(Idx, Iters);259 ++Iters;260 Int = 0;261 Bool = true;262 }263 264 Iters = 0;265 // The same thing but with the result as a const reference.266 for (const auto &[Idx, Int, Bool] :267 llvm::enumerate(llvm::SmallVector<int>({1, 2, 3}),268 std::vector<bool>({true, false, true}))) {269 EXPECT_EQ(Idx, Iters);270 ++Iters;271 Int = 0;272 Bool = true;273 }274}275 276#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)277TEST(STLExtrasTest, EnumerateDifferentLengths) {278 std::vector<int> Ints = {0, 1};279 bool Bools[] = {true, false, true};280 std::string Chars = "abc";281 EXPECT_DEATH(llvm::enumerate(Ints, Bools, Chars),282 "Ranges have different length");283 EXPECT_DEATH(llvm::enumerate(Bools, Ints, Chars),284 "Ranges have different length");285 EXPECT_DEATH(llvm::enumerate(Bools, Chars, Ints),286 "Ranges have different length");287}288#endif289 290template <bool B> struct CanMove {};291template <> struct CanMove<false> {292 CanMove(CanMove &&) = delete;293 294 CanMove() = default;295 CanMove(const CanMove &) = default;296};297 298template <bool B> struct CanCopy {};299template <> struct CanCopy<false> {300 CanCopy(const CanCopy &) = delete;301 302 CanCopy() = default;303 CanCopy(CanCopy &&) = default;304};305 306template <bool Moveable, bool Copyable>307class Counted : CanMove<Moveable>, CanCopy<Copyable> {308 int &C;309 int &M;310 int &D;311 312public:313 explicit Counted(int &C, int &M, int &D) : C(C), M(M), D(D) {}314 Counted(const Counted &O) : CanCopy<Copyable>(O), C(O.C), M(O.M), D(O.D) {315 ++C;316 }317 Counted(Counted &&O)318 : CanMove<Moveable>(std::move(O)), C(O.C), M(O.M), D(O.D) {319 ++M;320 }321 ~Counted() { ++D; }322};323 324template <bool Moveable, bool Copyable>325struct Range : Counted<Moveable, Copyable> {326 using Counted<Moveable, Copyable>::Counted;327 int *begin() const { return nullptr; }328 int *end() const { return nullptr; }329};330 331TEST(STLExtrasTest, EnumerateLifetimeSemanticsPRValue) {332 int Copies = 0;333 int Moves = 0;334 int Destructors = 0;335 {336 auto E = enumerate(Range<true, false>(Copies, Moves, Destructors));337 (void)E;338 // Doesn't compile. rvalue ranges must be moveable.339 // auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));340 EXPECT_EQ(0, Copies);341 EXPECT_EQ(1, Moves);342 EXPECT_EQ(1, Destructors);343 }344 EXPECT_EQ(0, Copies);345 EXPECT_EQ(1, Moves);346 EXPECT_EQ(2, Destructors);347}348 349TEST(STLExtrasTest, EnumerateLifetimeSemanticsRValue) {350 // With an rvalue, it should not be destroyed until the end of the scope.351 int Copies = 0;352 int Moves = 0;353 int Destructors = 0;354 {355 Range<true, false> R(Copies, Moves, Destructors);356 {357 auto E = enumerate(std::move(R));358 (void)E;359 // Doesn't compile. rvalue ranges must be moveable.360 // auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));361 EXPECT_EQ(0, Copies);362 EXPECT_EQ(1, Moves);363 EXPECT_EQ(0, Destructors);364 }365 EXPECT_EQ(0, Copies);366 EXPECT_EQ(1, Moves);367 EXPECT_EQ(1, Destructors);368 }369 EXPECT_EQ(0, Copies);370 EXPECT_EQ(1, Moves);371 EXPECT_EQ(2, Destructors);372}373 374TEST(STLExtrasTest, EnumerateLifetimeSemanticsLValue) {375 // With an lvalue, it should not be destroyed even after the end of the scope.376 // lvalue ranges need be neither copyable nor moveable.377 int Copies = 0;378 int Moves = 0;379 int Destructors = 0;380 {381 Range<false, false> R(Copies, Moves, Destructors);382 {383 auto E = enumerate(R);384 (void)E;385 EXPECT_EQ(0, Copies);386 EXPECT_EQ(0, Moves);387 EXPECT_EQ(0, Destructors);388 }389 EXPECT_EQ(0, Copies);390 EXPECT_EQ(0, Moves);391 EXPECT_EQ(0, Destructors);392 }393 EXPECT_EQ(0, Copies);394 EXPECT_EQ(0, Moves);395 EXPECT_EQ(1, Destructors);396}397 398namespace some_namespace {399struct some_struct {400 std::vector<int> data;401 std::string swap_val;402};403 404struct derives_from_some_struct : some_struct {};405 406std::vector<int>::const_iterator begin(const some_struct &s) {407 return s.data.begin();408}409 410std::vector<int>::const_iterator end(const some_struct &s) {411 return s.data.end();412}413 414std::vector<int>::const_reverse_iterator rbegin(const some_struct &s) {415 return s.data.rbegin();416}417 418std::vector<int>::const_reverse_iterator rend(const some_struct &s) {419 return s.data.rend();420}421 422void swap(some_struct &lhs, some_struct &rhs) {423 // make swap visible as non-adl swap would even seem to424 // work with std::swap which defaults to moving425 lhs.swap_val = "lhs";426 rhs.swap_val = "rhs";427}428 429struct List {430 std::list<int> data;431};432 433std::list<int>::const_iterator begin(const List &list) {434 return list.data.begin();435}436std::list<int>::const_iterator end(const List &list) { return list.data.end(); }437 438struct Pairs {439 std::vector<std::pair<std::string, int>> data;440 using const_iterator =441 std::vector<std::pair<std::string, int>>::const_iterator;442};443 444Pairs::const_iterator begin(const Pairs &p) { return p.data.begin(); }445Pairs::const_iterator end(const Pairs &p) { return p.data.end(); }446 447struct requires_move {};448int *begin(requires_move &&) { return nullptr; }449int *end(requires_move &&) { return nullptr; }450} // namespace some_namespace451 452TEST(STLExtrasTest, EnumerateCustomBeginEnd) {453 // Check that `enumerate` uses ADL to find `begin`/`end` iterators454 // of the enumerated type.455 some_namespace::some_struct X{};456 X.data = {1, 2, 3};457 458 unsigned Iters = 0;459 for (auto [Idx, Val] : enumerate(X)) {460 EXPECT_EQ(Val, X.data[Idx]);461 ++Iters;462 }463 EXPECT_EQ(Iters, 3u);464}465 466TEST(STLExtrasTest, CountAdaptor) {467 std::vector<int> v;468 469 v.push_back(1);470 v.push_back(2);471 v.push_back(1);472 v.push_back(4);473 v.push_back(3);474 v.push_back(2);475 v.push_back(1);476 477 EXPECT_EQ(3, count(v, 1));478 EXPECT_EQ(2, count(v, 2));479 EXPECT_EQ(1, count(v, 3));480 EXPECT_EQ(1, count(v, 4));481}482 483TEST(STLExtrasTest, for_each) {484 std::vector<int> v{0, 1, 2, 3, 4};485 int count = 0;486 487 llvm::for_each(v, [&count](int) { ++count; });488 EXPECT_EQ(5, count);489}490 491TEST(STLExtrasTest, ToVector) {492 std::vector<char> v = {'a', 'b', 'c'};493 auto Enumerated = to_vector<4>(enumerate(v));494 ASSERT_EQ(3u, Enumerated.size());495 for (size_t I = 0; I < v.size(); ++I) {496 EXPECT_EQ(I, Enumerated[I].index());497 EXPECT_EQ(v[I], Enumerated[I].value());498 }499 500 auto EnumeratedImplicitSize = to_vector(enumerate(v));501 ASSERT_EQ(3u, EnumeratedImplicitSize.size());502 for (size_t I = 0; I < v.size(); ++I) {503 EXPECT_EQ(I, EnumeratedImplicitSize[I].index());504 EXPECT_EQ(v[I], EnumeratedImplicitSize[I].value());505 }506}507 508TEST(STLExtrasTest, AllTypesEqual) {509 static_assert(all_types_equal_v<>);510 static_assert(all_types_equal_v<int>);511 static_assert(all_types_equal_v<int, int, int>);512 513 static_assert(!all_types_equal_v<int, int, unsigned int>);514 static_assert(!all_types_equal_v<int, int, float>);515}516 517TEST(STLExtrasTest, ConcatRange) {518 std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8};519 std::vector<int> Test;520 521 std::vector<int> V1234 = {1, 2, 3, 4};522 std::list<int> L56 = {5, 6};523 SmallVector<int, 2> SV78 = {7, 8};524 525 // Use concat across different sized ranges of different types with different526 // iterators.527 for (int &i : concat<int>(V1234, L56, SV78))528 Test.push_back(i);529 EXPECT_EQ(Expected, Test);530 531 // Use concat between a temporary, an L-value, and an R-value to make sure532 // complex lifetimes work well.533 Test.clear();534 for (int &i : concat<int>(std::vector<int>(V1234), L56, std::move(SV78)))535 Test.push_back(i);536 EXPECT_EQ(Expected, Test);537}538 539TEST(STLExtrasTest, ConcatRangeADL) {540 // Make sure that we use the `begin`/`end` functions from `some_namespace`,541 // using ADL.542 some_namespace::some_struct S0;543 S0.data = {1, 2};544 some_namespace::some_struct S1;545 S1.data = {3, 4};546 EXPECT_THAT(concat<const int>(S0, S1), ElementsAre(1, 2, 3, 4));547}548 549TEST(STLExtrasTest, ConcatRangePtrToSameClass) {550 some_namespace::some_struct S0{};551 some_namespace::some_struct S1{};552 SmallVector<some_namespace::some_struct *> V0{&S0};553 SmallVector<some_namespace::some_struct *> V1{&S1, &S1};554 555 // Dereferencing all iterators yields `some_namespace::some_struct *&`; no556 // conversion takes place, `reference_type` is557 // `some_namespace::some_struct *&`.558 auto C = concat<some_namespace::some_struct *>(V0, V1);559 static_assert(560 std::is_same_v<decltype(*C.begin()), some_namespace::some_struct *&>);561 EXPECT_THAT(C, ElementsAre(&S0, &S1, &S1));562 // `reference_type` should still allow container modification.563 for (auto &i : C)564 if (i == &S0)565 i = nullptr;566 EXPECT_THAT(C, ElementsAre(nullptr, &S1, &S1));567}568 569TEST(STLExtrasTest, ConcatRangePtrToDerivedClass) {570 some_namespace::some_struct S0{};571 some_namespace::derives_from_some_struct S1{};572 SmallVector<some_namespace::some_struct *> V0{&S0};573 SmallVector<some_namespace::derives_from_some_struct *> V1{&S1, &S1};574 575 // Dereferencing all iterators yields different (but convertible types);576 // conversion takes place, `reference_type` is577 // `some_namespace::some_struct *`.578 auto C = concat<some_namespace::some_struct *>(V0, V1);579 static_assert(580 std::is_same_v<decltype(*C.begin()), some_namespace::some_struct *>);581 EXPECT_THAT(C,582 ElementsAre(&S0, static_cast<some_namespace::some_struct *>(&S1),583 static_cast<some_namespace::some_struct *>(&S1)));584}585 586TEST(STLExtrasTest, MakeFirstSecondRangeADL) {587 // Make sure that we use the `begin`/`end` functions from `some_namespace`,588 // using ADL.589 some_namespace::Pairs Pairs;590 Pairs.data = {{"foo", 1}, {"bar", 2}};591 EXPECT_THAT(make_first_range(Pairs), ElementsAre("foo", "bar"));592 EXPECT_THAT(make_second_range(Pairs), ElementsAre(1, 2));593}594 595template <typename T> struct Iterator {596 int i = 0;597 T operator*() const { return i; }598 Iterator &operator++() {599 ++i;600 return *this;601 }602 bool operator==(Iterator RHS) const { return i == RHS.i; }603};604 605template <typename T> struct RangeWithValueType {606 int i;607 RangeWithValueType(int i) : i(i) {}608 Iterator<T> begin() { return Iterator<T>{0}; }609 Iterator<T> end() { return Iterator<T>{i}; }610};611 612TEST(STLExtrasTest, ValueReturn) {613 RangeWithValueType<int> R(1);614 auto C = concat<int>(R, R);615 auto I = C.begin();616 ASSERT_NE(I, C.end());617 static_assert(std::is_same_v<decltype((*I)), int>);618 auto V = *I;619 ASSERT_EQ(V, 0);620}621 622TEST(STLExtrasTest, ReferenceReturn) {623 RangeWithValueType<const int&> R(1);624 auto C = concat<const int>(R, R);625 auto I = C.begin();626 ASSERT_NE(I, C.end());627 static_assert(std::is_same_v<decltype((*I)), const int &>);628 auto V = *I;629 ASSERT_EQ(V, 0);630}631 632TEST(STLExtrasTest, PartitionAdaptor) {633 std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};634 635 auto I = partition(V, [](int i) { return i % 2 == 0; });636 ASSERT_EQ(V.begin() + 4, I);637 638 // Sort the two halves as partition may have messed with the order.639 llvm::sort(V.begin(), I);640 llvm::sort(I, V.end());641 642 EXPECT_EQ(2, V[0]);643 EXPECT_EQ(4, V[1]);644 EXPECT_EQ(6, V[2]);645 EXPECT_EQ(8, V[3]);646 EXPECT_EQ(1, V[4]);647 EXPECT_EQ(3, V[5]);648 EXPECT_EQ(5, V[6]);649 EXPECT_EQ(7, V[7]);650}651 652TEST(STLExtrasTest, EraseIf) {653 std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};654 655 erase_if(V, [](int i) { return i % 2 == 0; });656 EXPECT_EQ(4u, V.size());657 EXPECT_EQ(1, V[0]);658 EXPECT_EQ(3, V[1]);659 EXPECT_EQ(5, V[2]);660 EXPECT_EQ(7, V[3]);661}662 663TEST(STLExtrasTest, AppendRange) {664 std::vector<int> V = {1, 2};665 auto AppendVals1 = {3};666 append_range(V, AppendVals1);667 EXPECT_THAT(V, ElementsAre(1, 2, 3));668 669 int AppendVals2[] = {4, 5};670 append_range(V, AppendVals2);671 EXPECT_THAT(V, ElementsAre(1, 2, 3, 4, 5));672 673 std::string Str;674 append_range(Str, "abc");675 EXPECT_THAT(Str, ElementsAre('a', 'b', 'c', '\0'));676 append_range(Str, "def");677 EXPECT_THAT(Str, ElementsAre('a', 'b', 'c', '\0', 'd', 'e', 'f', '\0'));678}679 680TEST(STLExtrasTest, AppendValues) {681 std::vector<int> Vals = {1, 2};682 append_values(Vals, 3);683 EXPECT_THAT(Vals, ElementsAre(1, 2, 3));684 685 append_values(Vals, 4, 5);686 EXPECT_THAT(Vals, ElementsAre(1, 2, 3, 4, 5));687 688 std::vector<StringRef> Strs;689 std::string A = "A";690 std::string B = "B";691 std::string C = "C";692 append_values(Strs, A, B);693 EXPECT_THAT(Strs, ElementsAre(A, B));694 append_values(Strs, C);695 EXPECT_THAT(Strs, ElementsAre(A, B, C));696 697 std::unordered_set<int> Set;698 append_values(Set, 1, 2);699 EXPECT_THAT(Set, UnorderedElementsAre(1, 2));700 append_values(Set, 3, 1);701 EXPECT_THAT(Set, UnorderedElementsAre(1, 2, 3));702}703 704TEST(STLExtrasTest, ADLTest) {705 some_namespace::some_struct s{{1, 2, 3, 4, 5}, ""};706 some_namespace::some_struct s2{{2, 4, 6, 8, 10}, ""};707 708 EXPECT_EQ(*adl_begin(s), 1);709 EXPECT_EQ(*(adl_end(s) - 1), 5);710 EXPECT_EQ(*adl_rbegin(s), 5);711 EXPECT_EQ(*(adl_rend(s) - 1), 1);712 713 adl_swap(s, s2);714 EXPECT_EQ(s.swap_val, "lhs");715 EXPECT_EQ(s2.swap_val, "rhs");716 717 int count = 0;718 llvm::for_each(s, [&count](int) { ++count; });719 EXPECT_EQ(count, 5);720}721 722TEST(STLExtrasTest, ADLTestTemporaryRange) {723 EXPECT_EQ(adl_begin(some_namespace::requires_move{}), nullptr);724 EXPECT_EQ(adl_end(some_namespace::requires_move{}), nullptr);725}726 727TEST(STLExtrasTest, ADLTestConstexpr) {728 // `std::begin`/`std::end` are marked as `constexpr`; check that729 // `adl_begin`/`adl_end` also work in constant-evaluated contexts.730 static constexpr int c_arr[] = {7, 8, 9};731 static_assert(adl_begin(c_arr) == c_arr);732 static_assert(adl_end(c_arr) == c_arr + 3);733 734 static constexpr std::array<int, 2> std_arr = {1, 2};735 static_assert(adl_begin(std_arr) == std_arr.begin());736 static_assert(adl_end(std_arr) == std_arr.end());737 SUCCEED();738}739 740struct FooWithMemberSize {741 size_t size() const { return 42; }742 auto begin() { return Data.begin(); }743 auto end() { return Data.end(); }744 745 std::set<int> Data;746};747 748namespace some_namespace {749struct FooWithFreeSize {750 auto begin() { return Data.begin(); }751 auto end() { return Data.end(); }752 753 std::set<int> Data;754};755 756size_t size(const FooWithFreeSize &) { return 13; }757} // namespace some_namespace758 759TEST(STLExtrasTest, ADLSizeTest) {760 FooWithMemberSize foo1;761 EXPECT_EQ(adl_size(foo1), 42u);762 763 some_namespace::FooWithFreeSize foo2;764 EXPECT_EQ(adl_size(foo2), 13u);765 766 static constexpr int c_arr[] = {1, 2, 3};767 static_assert(adl_size(c_arr) == 3u);768 769 static constexpr std::array<int, 4> cpp_arr = {};770 static_assert(adl_size(cpp_arr) == 4u);771}772 773TEST(STLExtrasTest, DropBeginTest) {774 SmallVector<int, 5> vec{0, 1, 2, 3, 4};775 776 for (int n = 0; n < 5; ++n) {777 EXPECT_THAT(drop_begin(vec, n),778 ElementsAreArray(ArrayRef(&vec[n], vec.size() - n)));779 }780}781 782TEST(STLExtrasTest, DropBeginDefaultTest) {783 SmallVector<int, 5> vec{0, 1, 2, 3, 4};784 785 EXPECT_THAT(drop_begin(vec), ElementsAre(1, 2, 3, 4));786}787 788TEST(STLExtrasTest, DropEndTest) {789 SmallVector<int, 5> vec{0, 1, 2, 3, 4};790 791 for (int n = 0; n < 5; ++n) {792 EXPECT_THAT(drop_end(vec, n),793 ElementsAreArray(ArrayRef(vec.data(), vec.size() - n)));794 }795}796 797TEST(STLExtrasTest, DropEndDefaultTest) {798 SmallVector<int, 5> vec{0, 1, 2, 3, 4};799 800 EXPECT_THAT(drop_end(vec), ElementsAre(0, 1, 2, 3));801}802 803TEST(STLExtrasTest, MapRangeTest) {804 SmallVector<int, 5> Vec{0, 1, 2};805 EXPECT_THAT(map_range(Vec, [](int V) { return V + 1; }),806 ElementsAre(1, 2, 3));807 808 // Make sure that we use the `begin`/`end` functions809 // from `some_namespace`, using ADL.810 some_namespace::some_struct S;811 S.data = {3, 4, 5};812 EXPECT_THAT(map_range(S, [](int V) { return V * 2; }), ElementsAre(6, 8, 10));813}814 815TEST(STLExtrasTest, EarlyIncrementTest) {816 std::list<int> L = {1, 2, 3, 4};817 818 auto EIR = make_early_inc_range(L);819 820 auto I = EIR.begin();821 auto EI = EIR.end();822 EXPECT_NE(I, EI);823 824 EXPECT_EQ(1, *I);825#if LLVM_ENABLE_ABI_BREAKING_CHECKS826#ifndef NDEBUG827 // Repeated dereferences are not allowed.828 EXPECT_DEATH(*I, "Cannot dereference");829 // Comparison after dereference is not allowed.830 EXPECT_DEATH((void)(I == EI), "Cannot compare");831 EXPECT_DEATH((void)(I != EI), "Cannot compare");832#endif833#endif834 835 ++I;836 EXPECT_NE(I, EI);837#if LLVM_ENABLE_ABI_BREAKING_CHECKS838#ifndef NDEBUG839 // You cannot increment prior to dereference.840 EXPECT_DEATH(++I, "Cannot increment");841#endif842#endif843 EXPECT_EQ(2, *I);844#if LLVM_ENABLE_ABI_BREAKING_CHECKS845#ifndef NDEBUG846 // Repeated dereferences are not allowed.847 EXPECT_DEATH(*I, "Cannot dereference");848#endif849#endif850 851 // Inserting shouldn't break anything. We should be able to keep dereferencing852 // the current iterator and increment. The increment to go to the "next"853 // iterator from before we inserted.854 L.insert(std::next(L.begin(), 2), -1);855 ++I;856 EXPECT_EQ(3, *I);857 858 // Erasing the front including the current doesn't break incrementing.859 L.erase(L.begin(), std::prev(L.end()));860 ++I;861 EXPECT_EQ(4, *I);862 ++I;863 EXPECT_EQ(EIR.end(), I);864}865 866TEST(STLExtrasTest, EarlyIncADLTest) {867 // Make sure that we use the `begin`/`end` functions from `some_namespace`,868 // using ADL.869 some_namespace::some_struct S;870 S.data = {1, 2, 3};871 EXPECT_THAT(make_early_inc_range(S), ElementsAre(1, 2, 3));872}873 874// A custom iterator that returns a pointer when dereferenced. This is used to875// test make_early_inc_range with iterators that do not return a reference on876// dereferencing.877struct CustomPointerIterator878 : public iterator_adaptor_base<CustomPointerIterator,879 std::list<int>::iterator,880 std::forward_iterator_tag> {881 using base_type =882 iterator_adaptor_base<CustomPointerIterator, std::list<int>::iterator,883 std::forward_iterator_tag>;884 885 explicit CustomPointerIterator(std::list<int>::iterator I) : base_type(I) {}886 887 // Retrieve a pointer to the current int.888 int *operator*() const { return &*base_type::wrapped(); }889};890 891// Make sure make_early_inc_range works with iterators that do not return a892// reference on dereferencing. The test is similar to EarlyIncrementTest, but893// uses CustomPointerIterator.894TEST(STLExtrasTest, EarlyIncrementTestCustomPointerIterator) {895 std::list<int> L = {1, 2, 3, 4};896 897 auto CustomRange = make_range(CustomPointerIterator(L.begin()),898 CustomPointerIterator(L.end()));899 auto EIR = make_early_inc_range(CustomRange);900 901 auto I = EIR.begin();902 auto EI = EIR.end();903 EXPECT_NE(I, EI);904 905 EXPECT_EQ(&*L.begin(), *I);906#if LLVM_ENABLE_ABI_BREAKING_CHECKS907#ifndef NDEBUG908 // Repeated dereferences are not allowed.909 EXPECT_DEATH(*I, "Cannot dereference");910 // Comparison after dereference is not allowed.911 EXPECT_DEATH((void)(I == EI), "Cannot compare");912 EXPECT_DEATH((void)(I != EI), "Cannot compare");913#endif914#endif915 916 ++I;917 EXPECT_NE(I, EI);918#if LLVM_ENABLE_ABI_BREAKING_CHECKS919#ifndef NDEBUG920 // You cannot increment prior to dereference.921 EXPECT_DEATH(++I, "Cannot increment");922#endif923#endif924 EXPECT_EQ(&*std::next(L.begin()), *I);925#if LLVM_ENABLE_ABI_BREAKING_CHECKS926#ifndef NDEBUG927 // Repeated dereferences are not allowed.928 EXPECT_DEATH(*I, "Cannot dereference");929#endif930#endif931 932 // Inserting shouldn't break anything. We should be able to keep dereferencing933 // the currrent iterator and increment. The increment to go to the "next"934 // iterator from before we inserted.935 L.insert(std::next(L.begin(), 2), -1);936 ++I;937 EXPECT_EQ(&*std::next(L.begin(), 3), *I);938 939 // Erasing the front including the current doesn't break incrementing.940 L.erase(L.begin(), std::prev(L.end()));941 ++I;942 EXPECT_EQ(&*L.begin(), *I);943 ++I;944 EXPECT_EQ(EIR.end(), I);945}946 947TEST(STLExtrasTest, ReplaceADL) {948 // Make sure that we use the `begin`/`end` functions from `some_namespace`,949 // using ADL.950 std::vector<int> Cont = {0, 1, 2, 3, 4, 5};951 some_namespace::some_struct S;952 S.data = {42, 43, 44};953 replace(Cont, Cont.begin() + 2, Cont.begin() + 5, S);954 EXPECT_THAT(Cont, ElementsAre(0, 1, 42, 43, 44, 5));955}956 957TEST(STLExtrasTest, AllEqual) {958 std::vector<int> V;959 EXPECT_TRUE(all_equal(V));960 961 V.push_back(1);962 EXPECT_TRUE(all_equal(V));963 964 V.push_back(1);965 V.push_back(1);966 EXPECT_TRUE(all_equal(V));967 968 V.push_back(2);969 EXPECT_FALSE(all_equal(V));970}971 972// Test to verify that all_equal works with a container that does not973// model the random access iterator concept.974TEST(STLExtrasTest, AllEqualNonRandomAccess) {975 std::list<int> V;976 static_assert(!std::is_convertible_v<977 std::iterator_traits<decltype(V)::iterator>::iterator_category,978 std::random_access_iterator_tag>);979 EXPECT_TRUE(all_equal(V));980 981 V.push_back(1);982 EXPECT_TRUE(all_equal(V));983 984 V.push_back(1);985 V.push_back(1);986 EXPECT_TRUE(all_equal(V));987 988 V.push_back(2);989 EXPECT_FALSE(all_equal(V));990}991 992TEST(STLExtrasTest, AllEqualInitializerList) {993 EXPECT_TRUE(all_equal({1}));994 EXPECT_TRUE(all_equal({1, 1}));995 EXPECT_FALSE(all_equal({1, 2}));996 EXPECT_FALSE(all_equal({2, 1}));997 EXPECT_TRUE(all_equal({1, 1, 1}));998}999 1000TEST(STLExtrasTest, to_address) {1001 int *V1 = new int;1002 EXPECT_EQ(V1, to_address(V1));1003 1004 // Check fancy pointer overload for unique_ptr1005 std::unique_ptr<int> V2 = std::make_unique<int>(0);1006 EXPECT_EQ(V2.get(), llvm::to_address(V2));1007 1008 V2.reset(V1);1009 EXPECT_EQ(V1, llvm::to_address(V2));1010 V2.release();1011 1012 // Check fancy pointer overload for shared_ptr1013 std::shared_ptr<int> V3 = std::make_shared<int>(0);1014 std::shared_ptr<int> V4 = V3;1015 EXPECT_EQ(V3.get(), V4.get());1016 EXPECT_EQ(V3.get(), llvm::to_address(V3));1017 EXPECT_EQ(V4.get(), llvm::to_address(V4));1018 1019 V3.reset(V1);1020 EXPECT_EQ(V1, llvm::to_address(V3));1021}1022 1023TEST(STLExtrasTest, partition_point) {1024 std::vector<int> V = {1, 3, 5, 7, 9};1025 1026 // Range version.1027 EXPECT_EQ(V.begin() + 3,1028 partition_point(V, [](unsigned X) { return X < 7; }));1029 EXPECT_EQ(V.begin(), partition_point(V, [](unsigned X) { return X < 1; }));1030 EXPECT_EQ(V.end(), partition_point(V, [](unsigned X) { return X < 50; }));1031}1032 1033TEST(STLExtrasTest, hasSingleElement) {1034 const std::vector<int> V0 = {}, V1 = {1}, V2 = {1, 2};1035 const std::vector<int> V10(10);1036 1037 EXPECT_FALSE(hasSingleElement(V0));1038 EXPECT_TRUE(hasSingleElement(V1));1039 EXPECT_FALSE(hasSingleElement(V2));1040 EXPECT_FALSE(hasSingleElement(V10));1041 1042 // Make sure that we use the `begin`/`end` functions1043 // from `some_namespace`, using ADL.1044 some_namespace::some_struct S;1045 EXPECT_FALSE(hasSingleElement(S));1046 S.data = V1;1047 EXPECT_TRUE(hasSingleElement(S));1048 S.data = V2;1049 EXPECT_FALSE(hasSingleElement(S));1050}1051 1052TEST(STLExtrasTest, getSingleElement) {1053 // Test const and non-const containers.1054 const std::vector<int> V1 = {7};1055 EXPECT_EQ(getSingleElement(V1), 7);1056 std::vector<int> V2 = {8};1057 EXPECT_EQ(getSingleElement(V2), 8);1058 1059 // Test LLVM container.1060 SmallVector<int> V3{9};1061 EXPECT_EQ(getSingleElement(V3), 9);1062 1063 // Test that the returned element is a reference.1064 getSingleElement(V3) = 11;1065 EXPECT_EQ(V3[0], 11);1066 1067 // Test non-random access container.1068 std::list<int> L1 = {10};1069 EXPECT_EQ(getSingleElement(L1), 10);1070 1071 // Make sure that we use the `begin`/`end` functions from `some_namespace`,1072 // using ADL.1073 some_namespace::some_struct S;1074 S.data = V2;1075 EXPECT_EQ(getSingleElement(S), 8);1076 1077#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)1078 // Make sure that we crash on empty or too many elements.1079 SmallVector<int> V4;1080 EXPECT_DEATH(getSingleElement(V4), "expected container with single element");1081 SmallVector<int> V5{12, 13, 14};1082 EXPECT_DEATH(getSingleElement(V5), "expected container with single element");1083 std::list<int> L2;1084 EXPECT_DEATH(getSingleElement(L2), "expected container with single element");1085#endif1086}1087 1088TEST(STLExtrasTest, hasNItems) {1089 const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};1090 const std::list<int> V3 = {1, 3, 5};1091 1092 EXPECT_TRUE(hasNItems(V0, 0));1093 EXPECT_FALSE(hasNItems(V0, 2));1094 EXPECT_TRUE(hasNItems(V1, 1));1095 EXPECT_FALSE(hasNItems(V1, 2));1096 1097 EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 3, [](int x) { return x < 10; }));1098 EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 0, [](int x) { return x > 10; }));1099 EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));1100 1101 // Make sure that we use the `begin`/`end` functions from `some_namespace`,1102 // using ADL.1103 some_namespace::List L;1104 L.data = {0, 1, 2};1105 EXPECT_FALSE(hasNItems(L, 2));1106 EXPECT_TRUE(hasNItems(L, 3));1107}1108 1109TEST(STLExtras, hasNItemsOrMore) {1110 const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};1111 const std::list<int> V3 = {1, 3, 5};1112 1113 EXPECT_TRUE(hasNItemsOrMore(V1, 1));1114 EXPECT_FALSE(hasNItemsOrMore(V1, 2));1115 1116 EXPECT_TRUE(hasNItemsOrMore(V2, 1));1117 EXPECT_TRUE(hasNItemsOrMore(V2, 2));1118 EXPECT_FALSE(hasNItemsOrMore(V2, 3));1119 1120 EXPECT_TRUE(hasNItemsOrMore(V3, 3));1121 EXPECT_FALSE(hasNItemsOrMore(V3, 4));1122 1123 EXPECT_TRUE(1124 hasNItemsOrMore(V3.begin(), V3.end(), 3, [](int x) { return x < 10; }));1125 EXPECT_FALSE(1126 hasNItemsOrMore(V3.begin(), V3.end(), 3, [](int x) { return x > 10; }));1127 EXPECT_TRUE(1128 hasNItemsOrMore(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));1129 1130 // Make sure that we use the `begin`/`end` functions from `some_namespace`,1131 // using ADL.1132 some_namespace::List L;1133 L.data = {0, 1, 2};1134 EXPECT_TRUE(hasNItemsOrMore(L, 1));1135 EXPECT_FALSE(hasNItems(L, 4));1136}1137 1138TEST(STLExtras, hasNItemsOrLess) {1139 const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};1140 const std::list<int> V3 = {1, 3, 5};1141 1142 EXPECT_TRUE(hasNItemsOrLess(V0, 0));1143 EXPECT_TRUE(hasNItemsOrLess(V0, 1));1144 EXPECT_TRUE(hasNItemsOrLess(V0, 2));1145 1146 EXPECT_FALSE(hasNItemsOrLess(V1, 0));1147 EXPECT_TRUE(hasNItemsOrLess(V1, 1));1148 EXPECT_TRUE(hasNItemsOrLess(V1, 2));1149 1150 EXPECT_FALSE(hasNItemsOrLess(V2, 0));1151 EXPECT_FALSE(hasNItemsOrLess(V2, 1));1152 EXPECT_TRUE(hasNItemsOrLess(V2, 2));1153 EXPECT_TRUE(hasNItemsOrLess(V2, 3));1154 1155 EXPECT_FALSE(hasNItemsOrLess(V3, 0));1156 EXPECT_FALSE(hasNItemsOrLess(V3, 1));1157 EXPECT_FALSE(hasNItemsOrLess(V3, 2));1158 EXPECT_TRUE(hasNItemsOrLess(V3, 3));1159 EXPECT_TRUE(hasNItemsOrLess(V3, 4));1160 1161 EXPECT_TRUE(1162 hasNItemsOrLess(V3.begin(), V3.end(), 1, [](int x) { return x == 1; }));1163 EXPECT_TRUE(1164 hasNItemsOrLess(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));1165 EXPECT_TRUE(1166 hasNItemsOrLess(V3.begin(), V3.end(), 5, [](int x) { return x < 5; }));1167 EXPECT_FALSE(1168 hasNItemsOrLess(V3.begin(), V3.end(), 2, [](int x) { return x < 10; }));1169 1170 // Make sure that we use the `begin`/`end` functions from `some_namespace`,1171 // using ADL.1172 some_namespace::List L;1173 L.data = {0, 1, 2};1174 EXPECT_FALSE(hasNItemsOrLess(L, 1));1175 EXPECT_TRUE(hasNItemsOrLess(L, 4));1176}1177 1178TEST(STLExtras, MoveRange) {1179 class Foo {1180 bool A;1181 1182 public:1183 Foo() : A(true) {}1184 Foo(const Foo &) = delete;1185 Foo(Foo &&Other) : A(Other.A) { Other.A = false; }1186 Foo &operator=(const Foo &) = delete;1187 Foo &operator=(Foo &&Other) {1188 if (this != &Other) {1189 A = Other.A;1190 Other.A = false;1191 }1192 return *this;1193 }1194 operator bool() const { return A; }1195 };1196 SmallVector<Foo, 4U> V1, V2, V3, V4;1197 auto HasVal = [](const Foo &Item) { return static_cast<bool>(Item); };1198 auto Build = [&] {1199 SmallVector<Foo, 4U> Foos;1200 Foos.resize(4U);1201 return Foos;1202 };1203 1204 V1.resize(4U);1205 EXPECT_TRUE(llvm::all_of(V1, HasVal));1206 1207 llvm::move(V1, std::back_inserter(V2));1208 1209 // Ensure input container is same size, but its contents were moved out.1210 EXPECT_EQ(V1.size(), 4U);1211 EXPECT_TRUE(llvm::none_of(V1, HasVal));1212 1213 // Ensure output container has the contents of the input container.1214 EXPECT_EQ(V2.size(), 4U);1215 EXPECT_TRUE(llvm::all_of(V2, HasVal));1216 1217 llvm::move(std::move(V2), std::back_inserter(V3));1218 1219 EXPECT_TRUE(llvm::none_of(V2, HasVal));1220 EXPECT_EQ(V3.size(), 4U);1221 EXPECT_TRUE(llvm::all_of(V3, HasVal));1222 1223 llvm::move(Build(), std::back_inserter(V4));1224 EXPECT_EQ(V4.size(), 4U);1225 EXPECT_TRUE(llvm::all_of(V4, HasVal));1226}1227 1228TEST(STLExtras, Unique) {1229 std::vector<int> V = {1, 5, 5, 4, 3, 3, 3};1230 1231 auto I = llvm::unique(V, [](int a, int b) { return a == b; });1232 1233 EXPECT_EQ(I, V.begin() + 4);1234 1235 EXPECT_EQ(1, V[0]);1236 EXPECT_EQ(5, V[1]);1237 EXPECT_EQ(4, V[2]);1238 EXPECT_EQ(3, V[3]);1239}1240 1241TEST(STLExtras, UniqueNoPred) {1242 std::vector<int> V = {1, 5, 5, 4, 3, 3, 3};1243 1244 auto I = llvm::unique(V);1245 1246 EXPECT_EQ(I, V.begin() + 4);1247 1248 EXPECT_EQ(1, V[0]);1249 EXPECT_EQ(5, V[1]);1250 EXPECT_EQ(4, V[2]);1251 EXPECT_EQ(3, V[3]);1252}1253 1254TEST(STLExtrasTest, MakeVisitorOneCallable) {1255 auto IdentityLambda = [](auto X) { return X; };1256 auto IdentityVisitor = makeVisitor(IdentityLambda);1257 EXPECT_EQ(IdentityLambda(1), IdentityVisitor(1));1258 EXPECT_EQ(IdentityLambda(2.0f), IdentityVisitor(2.0f));1259 EXPECT_TRUE((std::is_same<decltype(IdentityLambda(IdentityLambda)),1260 decltype(IdentityLambda)>::value));1261 EXPECT_TRUE((std::is_same<decltype(IdentityVisitor(IdentityVisitor)),1262 decltype(IdentityVisitor)>::value));1263}1264 1265TEST(STLExtrasTest, MakeVisitorTwoCallables) {1266 auto Visitor =1267 makeVisitor([](int) { return 0; }, [](std::string) { return 1; });1268 EXPECT_EQ(Visitor(42), 0);1269 EXPECT_EQ(Visitor("foo"), 1);1270}1271 1272TEST(STLExtrasTest, MakeVisitorCallableMultipleOperands) {1273 auto Second = makeVisitor([](int I, float F) { return F; },1274 [](float F, int I) { return I; });1275 EXPECT_EQ(Second(1.f, 1), 1);1276 EXPECT_EQ(Second(1, 1.f), 1.f);1277}1278 1279TEST(STLExtrasTest, MakeVisitorDefaultCase) {1280 {1281 auto Visitor = makeVisitor([](int I) { return I + 100; },1282 [](float F) { return F * 2; },1283 [](auto) { return -1; });1284 EXPECT_EQ(Visitor(24), 124);1285 EXPECT_EQ(Visitor(2.f), 4.f);1286 EXPECT_EQ(Visitor(2.), -1);1287 EXPECT_EQ(Visitor(Visitor), -1);1288 }1289 {1290 auto Visitor = makeVisitor([](auto) { return -1; },1291 [](int I) { return I + 100; },1292 [](float F) { return F * 2; });1293 EXPECT_EQ(Visitor(24), 124);1294 EXPECT_EQ(Visitor(2.f), 4.f);1295 EXPECT_EQ(Visitor(2.), -1);1296 EXPECT_EQ(Visitor(Visitor), -1);1297 }1298}1299 1300template <bool Moveable, bool Copyable>1301struct Functor : Counted<Moveable, Copyable> {1302 using Counted<Moveable, Copyable>::Counted;1303 void operator()() {}1304};1305 1306TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsPRValue) {1307 int Copies = 0;1308 int Moves = 0;1309 int Destructors = 0;1310 {1311 auto V = makeVisitor(Functor<true, false>(Copies, Moves, Destructors));1312 (void)V;1313 EXPECT_EQ(0, Copies);1314 EXPECT_EQ(1, Moves);1315 EXPECT_EQ(1, Destructors);1316 }1317 EXPECT_EQ(0, Copies);1318 EXPECT_EQ(1, Moves);1319 EXPECT_EQ(2, Destructors);1320}1321 1322TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsRValue) {1323 int Copies = 0;1324 int Moves = 0;1325 int Destructors = 0;1326 {1327 Functor<true, false> F(Copies, Moves, Destructors);1328 {1329 auto V = makeVisitor(std::move(F));1330 (void)V;1331 EXPECT_EQ(0, Copies);1332 EXPECT_EQ(1, Moves);1333 EXPECT_EQ(0, Destructors);1334 }1335 EXPECT_EQ(0, Copies);1336 EXPECT_EQ(1, Moves);1337 EXPECT_EQ(1, Destructors);1338 }1339 EXPECT_EQ(0, Copies);1340 EXPECT_EQ(1, Moves);1341 EXPECT_EQ(2, Destructors);1342}1343 1344TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsLValue) {1345 int Copies = 0;1346 int Moves = 0;1347 int Destructors = 0;1348 {1349 Functor<true, true> F(Copies, Moves, Destructors);1350 {1351 auto V = makeVisitor(F);1352 (void)V;1353 EXPECT_EQ(1, Copies);1354 EXPECT_EQ(0, Moves);1355 EXPECT_EQ(0, Destructors);1356 }1357 EXPECT_EQ(1, Copies);1358 EXPECT_EQ(0, Moves);1359 EXPECT_EQ(1, Destructors);1360 }1361 EXPECT_EQ(1, Copies);1362 EXPECT_EQ(0, Moves);1363 EXPECT_EQ(2, Destructors);1364}1365 1366TEST(STLExtrasTest, AllOfZip) {1367 std::vector<int> v1 = {0, 4, 2, 1};1368 std::vector<int> v2 = {1, 4, 3, 6};1369 EXPECT_TRUE(all_of_zip(v1, v2, [](int v1, int v2) { return v1 <= v2; }));1370 EXPECT_FALSE(all_of_zip(v1, v2, [](int L, int R) { return L < R; }));1371 1372 // Triple vectors1373 std::vector<int> v3 = {1, 6, 5, 7};1374 EXPECT_EQ(true, all_of_zip(v1, v2, v3, [](int a, int b, int c) {1375 return a <= b && b <= c;1376 }));1377 EXPECT_EQ(false, all_of_zip(v1, v2, v3, [](int a, int b, int c) {1378 return a < b && b < c;1379 }));1380 1381 // Shorter vector should fail even with an always-true predicate.1382 std::vector<int> v_short = {1, 4};1383 EXPECT_EQ(false, all_of_zip(v1, v_short, [](int, int) { return true; }));1384 EXPECT_EQ(false,1385 all_of_zip(v1, v2, v_short, [](int, int, int) { return true; }));1386}1387 1388TEST(STLExtrasTest, TypesAreDistinct) {1389 EXPECT_TRUE((llvm::TypesAreDistinct<>::value));1390 EXPECT_TRUE((llvm::TypesAreDistinct<int>::value));1391 EXPECT_FALSE((llvm::TypesAreDistinct<int, int>::value));1392 EXPECT_TRUE((llvm::TypesAreDistinct<int, float>::value));1393 EXPECT_FALSE((llvm::TypesAreDistinct<int, float, int>::value));1394 EXPECT_TRUE((llvm::TypesAreDistinct<int, float, double>::value));1395 EXPECT_FALSE((llvm::TypesAreDistinct<int, float, double, float>::value));1396 EXPECT_TRUE((llvm::TypesAreDistinct<int, int *>::value));1397 EXPECT_TRUE((llvm::TypesAreDistinct<int, int &>::value));1398 EXPECT_TRUE((llvm::TypesAreDistinct<int, int &&>::value));1399 EXPECT_TRUE((llvm::TypesAreDistinct<int, const int>::value));1400}1401 1402TEST(STLExtrasTest, FirstIndexOfType) {1403 EXPECT_EQ((llvm::FirstIndexOfType<int, int>::value), 0u);1404 EXPECT_EQ((llvm::FirstIndexOfType<int, int, int>::value), 0u);1405 EXPECT_EQ((llvm::FirstIndexOfType<int, float, int>::value), 1u);1406 EXPECT_EQ((llvm::FirstIndexOfType<int const *, float, int, int const *,1407 const int>::value),1408 2u);1409}1410 1411TEST(STLExtrasTest, TypeAtIndex) {1412 EXPECT_TRUE((std::is_same<int, llvm::TypeAtIndex<0, int>>::value));1413 EXPECT_TRUE((std::is_same<int, llvm::TypeAtIndex<0, int, float>>::value));1414 EXPECT_TRUE((std::is_same<float, llvm::TypeAtIndex<1, int, float>>::value));1415 EXPECT_TRUE(1416 (std::is_same<float, llvm::TypeAtIndex<1, int, float, double>>::value));1417 EXPECT_TRUE(1418 (std::is_same<float, llvm::TypeAtIndex<1, int, float, double>>::value));1419 EXPECT_TRUE(1420 (std::is_same<double, llvm::TypeAtIndex<2, int, float, double>>::value));1421}1422 1423enum Doggos {1424 Floofer,1425 Woofer,1426 SubWoofer,1427 Pupper,1428 Pupperino,1429 Longboi,1430};1431 1432struct WooferCmp {1433 // Not copyable.1434 WooferCmp() = default;1435 WooferCmp(const WooferCmp &) = delete;1436 WooferCmp &operator=(const WooferCmp &) = delete;1437 1438 friend bool operator==(const Doggos &Doggo, const WooferCmp &) {1439 return Doggo == Doggos::Woofer;1440 }1441};1442 1443TEST(STLExtrasTest, IsContainedInitializerList) {1444 EXPECT_TRUE(is_contained({Woofer, SubWoofer}, Woofer));1445 EXPECT_TRUE(is_contained({Woofer, SubWoofer}, SubWoofer));1446 EXPECT_FALSE(is_contained({Woofer, SubWoofer}, Pupper));1447 1448 // Check that the initializer list type and the element type do not have to1449 // match exactly.1450 EXPECT_TRUE(is_contained({Floofer, Woofer, SubWoofer}, WooferCmp{}));1451 EXPECT_FALSE(is_contained({Floofer, SubWoofer}, WooferCmp{}));1452 1453 EXPECT_TRUE(is_contained({"a", "bb", "ccc", "dddd"}, llvm::StringRef("ccc")));1454 EXPECT_FALSE(is_contained({"a", "bb", "ccc", "dddd"}, llvm::StringRef("x")));1455 1456 static_assert(is_contained({Woofer, SubWoofer}, SubWoofer), "SubWoofer!");1457 static_assert(!is_contained({Woofer, SubWoofer}, Pupper), "Missing Pupper!");1458 1459 EXPECT_TRUE(is_contained({1, 2, 3, 4}, 3));1460 EXPECT_FALSE(is_contained({1, 2, 3, 4}, 5));1461 1462 static_assert(is_contained({1, 2, 3, 4}, 3), "It's there!");1463 static_assert(!is_contained({1, 2, 3, 4}, 5), "It's not there :(");1464}1465 1466TEST(STLExtrasTest, IsContainedMemberContains) {1467 // Check that `llvm::is_contained` uses the member `.contains()` when1468 // available. Check that `.contains()` is preferred over `.find()`.1469 struct Foo {1470 bool contains(int) const {1471 ++NumContainsCalls;1472 return ContainsResult;1473 }1474 int *begin() { return nullptr; }1475 int *end() { return nullptr; }1476 int *find(int) { return nullptr; }1477 1478 bool ContainsResult = false;1479 mutable unsigned NumContainsCalls = 0;1480 } Container;1481 1482 EXPECT_EQ(Container.NumContainsCalls, 0u);1483 EXPECT_FALSE(is_contained(Container, 1));1484 EXPECT_EQ(Container.NumContainsCalls, 1u);1485 1486 Container.ContainsResult = true;1487 EXPECT_TRUE(is_contained(Container, 1));1488 EXPECT_EQ(Container.NumContainsCalls, 2u);1489}1490 1491TEST(STLExtrasTest, IsContainedMemberFind) {1492 // Check that `llvm::is_contained` uses the member `.find(x)` when available.1493 struct Foo {1494 auto begin() { return Data.begin(); }1495 auto end() { return Data.end(); }1496 auto find(int X) {1497 ++NumFindCalls;1498 return std::find(begin(), end(), X);1499 }1500 1501 std::vector<int> Data;1502 mutable unsigned NumFindCalls = 0;1503 } Container;1504 1505 Container.Data = {1, 2, 3};1506 1507 EXPECT_EQ(Container.NumFindCalls, 0u);1508 EXPECT_TRUE(is_contained(Container, 1));1509 EXPECT_TRUE(is_contained(Container, 3));1510 EXPECT_EQ(Container.NumFindCalls, 2u);1511 1512 EXPECT_FALSE(is_contained(Container, 4));1513 EXPECT_EQ(Container.NumFindCalls, 3u);1514}1515 1516TEST(STLExtrasTest, addEnumValues) {1517 enum A { Zero = 0, One = 1 };1518 enum B { IntMax = INT_MAX, ULongLongMax = ULLONG_MAX };1519 enum class C : unsigned { Two = 2 };1520 1521 // Non-fixed underlying types, with same underlying types1522 static_assert(addEnumValues(Zero, One) == 1,1523 "addEnumValues(Zero, One) failed.");1524 static_assert(addEnumValues(IntMax, ULongLongMax) ==1525 INT_MAX + static_cast<unsigned long long>(ULLONG_MAX),1526 "addEnumValues(IntMax, ULongLongMax) failed.");1527 // Non-fixed underlying types, with different underlying types1528 static_assert(addEnumValues(Zero, IntMax) == INT_MAX,1529 "addEnumValues(Zero, IntMax) failed.");1530 static_assert(addEnumValues(One, ULongLongMax) ==1531 1 + static_cast<unsigned long long>(ULLONG_MAX),1532 "addEnumValues(One, ULongLongMax) failed.");1533 // Non-fixed underlying type enum and fixed underlying type enum, with same1534 // underlying types1535 static_assert(addEnumValues(One, C::Two) == 3,1536 "addEnumValues(One, C::Two) failed.");1537 // Non-fixed underlying type enum and fixed underlying type enum, with1538 // different underlying types1539 static_assert(addEnumValues(ULongLongMax, C::Two) ==1540 static_cast<unsigned long long>(ULLONG_MAX) + 2,1541 "addEnumValues(ULongLongMax, C::Two) failed.");1542}1543 1544TEST(STLExtrasTest, LessFirst) {1545 {1546 std::pair<int, int> A(0, 1);1547 std::pair<int, int> B(1, 0);1548 EXPECT_TRUE(less_first()(A, B));1549 EXPECT_FALSE(less_first()(B, A));1550 }1551 1552 {1553 std::tuple<int, int> A(0, 1);1554 std::tuple<int, int> B(1, 0);1555 EXPECT_TRUE(less_first()(A, B));1556 EXPECT_FALSE(less_first()(B, A));1557 }1558}1559 1560TEST(STLExtrasTest, LessSecond) {1561 {1562 std::pair<int, int> A(0, 1);1563 std::pair<int, int> B(1, 0);1564 EXPECT_FALSE(less_second()(A, B));1565 EXPECT_TRUE(less_second()(B, A));1566 }1567 1568 {1569 std::tuple<int, int> A(0, 1);1570 std::tuple<int, int> B(1, 0);1571 EXPECT_FALSE(less_second()(A, B));1572 EXPECT_TRUE(less_second()(B, A));1573 }1574}1575 1576TEST(STLExtrasTest, Mismatch) {1577 {1578 const int MMIndex = 5;1579 StringRef First = "FooBar";1580 StringRef Second = "FooBaz";1581 auto [MMFirst, MMSecond] = mismatch(First, Second);1582 EXPECT_EQ(MMFirst, First.begin() + MMIndex);1583 EXPECT_EQ(MMSecond, Second.begin() + MMIndex);1584 }1585 1586 {1587 SmallVector<int> First = {0, 1, 2};1588 SmallVector<int> Second = {0, 1, 2, 3};1589 auto [MMFirst, MMSecond] = mismatch(First, Second);1590 EXPECT_EQ(MMFirst, First.end());1591 EXPECT_EQ(MMSecond, Second.begin() + 3);1592 }1593 1594 {1595 SmallVector<int> First = {0, 1};1596 SmallVector<int> Empty;1597 auto [MMFirst, MMEmpty] = mismatch(First, Empty);1598 EXPECT_EQ(MMFirst, First.begin());1599 EXPECT_EQ(MMEmpty, Empty.begin());1600 }1601}1602 1603TEST(STLExtrasTest, Includes) {1604 {1605 std::vector<int> V1 = {1, 2};1606 std::vector<int> V2;1607 EXPECT_TRUE(includes(V1, V2));1608 EXPECT_FALSE(includes(V2, V1));1609 V2.push_back(1);1610 EXPECT_TRUE(includes(V1, V2));1611 V2.push_back(3);1612 EXPECT_FALSE(includes(V1, V2));1613 }1614 1615 {1616 std::vector<int> V1 = {3, 2, 1};1617 std::vector<int> V2;1618 EXPECT_TRUE(includes(V1, V2, std::greater<>()));1619 EXPECT_FALSE(includes(V2, V1, std::greater<>()));1620 V2.push_back(3);1621 EXPECT_TRUE(includes(V1, V2, std::greater<>()));1622 V2.push_back(0);1623 EXPECT_FALSE(includes(V1, V2, std::greater<>()));1624 }1625}1626 1627TEST(STLExtrasTest, Fill) {1628 std::vector<int> V1 = {1, 2, 3};1629 std::vector<int> V2;1630 int Val = 4;1631 fill(V1, Val);1632 EXPECT_THAT(V1, ElementsAre(Val, Val, Val));1633 V2.resize(4);1634 fill(V2, Val);1635 EXPECT_THAT(V2, ElementsAre(Val, Val, Val, Val));1636}1637 1638TEST(STLExtrasTest, Accumulate) {1639 EXPECT_EQ(accumulate(std::vector<int>(), 0), 0);1640 EXPECT_EQ(accumulate(std::vector<int>(), 3), 3);1641 std::vector<int> V1 = {1, 2, 3, 4, 5};1642 EXPECT_EQ(accumulate(V1, 0), std::accumulate(V1.begin(), V1.end(), 0));1643 EXPECT_EQ(accumulate(V1, 10), std::accumulate(V1.begin(), V1.end(), 10));1644 EXPECT_EQ(accumulate(drop_begin(V1), 7),1645 std::accumulate(V1.begin() + 1, V1.end(), 7));1646 1647 EXPECT_EQ(accumulate(V1, 2, std::multiplies<>{}), 240);1648}1649 1650TEST(STLExtrasTest, SumOf) {1651 EXPECT_EQ(sum_of(std::vector<int>()), 0);1652 EXPECT_EQ(sum_of(std::vector<int>(), 1), 1);1653 std::vector<int> V1 = {1, 2, 3, 4, 5};1654 static_assert(std::is_same_v<decltype(sum_of(V1)), int>);1655 static_assert(std::is_same_v<decltype(sum_of(V1, 1)), int>);1656 EXPECT_EQ(sum_of(V1), 15);1657 EXPECT_EQ(sum_of(V1, 1), 16);1658 1659 std::vector<float> V2 = {1.0f, 2.0f, 4.0f};1660 static_assert(std::is_same_v<decltype(sum_of(V2)), float>);1661 static_assert(std::is_same_v<decltype(sum_of(V2), 1.0f), float>);1662 static_assert(std::is_same_v<decltype(sum_of(V2), 1.0), double>);1663 EXPECT_EQ(sum_of(V2), 7.0f);1664 EXPECT_EQ(sum_of(V2, 1.0f), 8.0f);1665 1666 // Make sure that for a const argument the return value is non-const.1667 const std::vector<float> V3 = {1.0f, 2.0f};1668 static_assert(std::is_same_v<decltype(sum_of(V3)), float>);1669 EXPECT_EQ(sum_of(V3), 3.0f);1670}1671 1672TEST(STLExtrasTest, ProductOf) {1673 EXPECT_EQ(product_of(std::vector<int>()), 1);1674 EXPECT_EQ(product_of(std::vector<int>(), 0), 0);1675 EXPECT_EQ(product_of(std::vector<int>(), 1), 1);1676 std::vector<int> V1 = {1, 2, 3, 4, 5};1677 static_assert(std::is_same_v<decltype(product_of(V1)), int>);1678 static_assert(std::is_same_v<decltype(product_of(V1, 1)), int>);1679 EXPECT_EQ(product_of(V1), 120);1680 EXPECT_EQ(product_of(V1, 1), 120);1681 EXPECT_EQ(product_of(V1, 2), 240);1682 1683 std::vector<float> V2 = {1.0f, 2.0f, 4.0f};1684 static_assert(std::is_same_v<decltype(product_of(V2)), float>);1685 static_assert(std::is_same_v<decltype(product_of(V2), 1.0f), float>);1686 static_assert(std::is_same_v<decltype(product_of(V2), 1.0), double>);1687 EXPECT_EQ(product_of(V2), 8.0f);1688 EXPECT_EQ(product_of(V2, 4.0f), 32.0f);1689 1690 // Make sure that for a const argument the return value is non-const.1691 const std::vector<float> V3 = {1.0f, 2.0f};1692 static_assert(std::is_same_v<decltype(product_of(V3)), float>);1693 EXPECT_EQ(product_of(V3), 2.0f);1694}1695 1696struct Foo;1697struct Bar {};1698 1699static_assert(is_incomplete_v<Foo>, "Foo is incomplete");1700static_assert(!is_incomplete_v<Bar>, "Bar is defined");1701 1702} // namespace1703