base/stl_util_unittest.cc

   1 // Copyright 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "base/stl_util.h"
   6
   7 #include <array>
   8 #include <deque>
   9 #include <forward_list>
  10 #include <functional>
  11 #include <initializer_list>
  12 #include <iterator>
  13 #include <list>
  14 #include <map>
  15 #include <queue>
  16 #include <set>
  17 #include <stack>
  18 #include <string>
  19 #include <type_traits>
  20 #include <unordered_map>
  21 #include <unordered_set>
  22 #include <vector>
  23
  24 #include "base/containers/queue.h"
  25 #include "base/strings/string16.h"
  26 #include "base/strings/utf_string_conversions.h"
  27 #include "testing/gmock/include/gmock/gmock.h"
  28 #include "testing/gtest/include/gtest/gtest.h"
  29
  30 namespace {
  31
  32 // Used as test case to ensure the various base::STLXxx functions don't require
  33 // more than operators "<" and "==" on values stored in containers.
  34 class ComparableValue {
  35  public:
  36   explicit ComparableValue(int value) : value_(value) {}
  37
  38   bool operator==(const ComparableValue& rhs) const {
  39     return value_ == rhs.value_;
  40   }
  41
  42   bool operator<(const ComparableValue& rhs) const {
  43     return value_ < rhs.value_;
  44   }
  45
  46  private:
  47   int value_;
  48 };
  49
  50 template <typename Container>
  51 void RunEraseTest() {
  52   const std::pair<Container, Container> test_data[] = {
  53       {Container(), Container()}, {{1, 2, 3}, {1, 3}}, {{1, 2, 3, 2}, {1, 3}}};
  54
  55   for (auto test_case : test_data) {
  56     base::Erase(test_case.first, 2);
  57     EXPECT_EQ(test_case.second, test_case.first);
  58   }
  59 }
  60
  61 // This test is written for containers of std::pair<int, int> to support maps.
  62 template <typename Container>
  63 void RunEraseIfTest() {
  64   struct {
  65     Container input;
  66     Container erase_even;
  67     Container erase_odd;
  68   } test_data[] = {
  69       {Container(), Container(), Container()},
  70       {{{1, 1}, {2, 2}, {3, 3}}, {{1, 1}, {3, 3}}, {{2, 2}}},
  71       {{{1, 1}, {2, 2}, {3, 3}, {4, 4}}, {{1, 1}, {3, 3}}, {{2, 2}, {4, 4}}},
  72   };
  73
  74   for (auto test_case : test_data) {
  75     base::EraseIf(test_case.input, [](const std::pair<int, int>& elem) {
  76       return !(elem.first & 1);
  77     });
  78     EXPECT_EQ(test_case.erase_even, test_case.input);
  79   }
  80
  81   for (auto test_case : test_data) {
  82     base::EraseIf(test_case.input, [](const std::pair<int, int>& elem) {
  83       return elem.first & 1;
  84     });
  85     EXPECT_EQ(test_case.erase_odd, test_case.input);
  86   }
  87 }
  88
  89 struct CustomIntHash {
  90   size_t operator()(int elem) const { return std::hash<int>()(elem) + 1; }
  91 };
  92
  93 struct HashByFirst {
  94   size_t operator()(const std::pair<int, int>& elem) const {
  95     return std::hash<int>()(elem.first);
  96   }
  97 };
  98
  99 }  // namespace
 100
 101 namespace base {
 102 namespace {
 103
 104 TEST(STLUtilTest, Size) {
 105   {
 106     std::vector<int> vector = {1, 2, 3, 4, 5};
 107     static_assert(
 108         std::is_same<decltype(base::size(vector)),
 109                      decltype(vector.size())>::value,
 110         "base::size(vector) should have the same type as vector.size()");
 111     EXPECT_EQ(vector.size(), base::size(vector));
 112   }
 113
 114   {
 115     std::string empty_str;
 116     static_assert(
 117         std::is_same<decltype(base::size(empty_str)),
 118                      decltype(empty_str.size())>::value,
 119         "base::size(empty_str) should have the same type as empty_str.size()");
 120     EXPECT_EQ(0u, base::size(empty_str));
 121   }
 122
 123   {
 124     std::array<int, 4> array = {{1, 2, 3, 4}};
 125     static_assert(
 126         std::is_same<decltype(base::size(array)),
 127                      decltype(array.size())>::value,
 128         "base::size(array) should have the same type as array.size()");
 129     static_assert(base::size(array) == array.size(),
 130                   "base::size(array) should be equal to array.size()");
 131   }
 132
 133   {
 134     int array[] = {1, 2, 3};
 135     static_assert(std::is_same<size_t, decltype(base::size(array))>::value,
 136                   "base::size(array) should be of type size_t");
 137     static_assert(3u == base::size(array), "base::size(array) should be 3");
 138   }
 139 }
 140
 141 TEST(STLUtilTest, Empty) {
 142   {
 143     std::vector<int> vector;
 144     static_assert(
 145         std::is_same<decltype(base::empty(vector)),
 146                      decltype(vector.empty())>::value,
 147         "base::empty(vector) should have the same type as vector.empty()");
 148     EXPECT_EQ(vector.empty(), base::empty(vector));
 149   }
 150
 151   {
 152     std::array<int, 4> array = {{1, 2, 3, 4}};
 153     static_assert(
 154         std::is_same<decltype(base::empty(array)),
 155                      decltype(array.empty())>::value,
 156         "base::empty(array) should have the same type as array.empty()");
 157     static_assert(base::empty(array) == array.empty(),
 158                   "base::empty(array) should be equal to array.empty()");
 159   }
 160
 161   {
 162     int array[] = {1, 2, 3};
 163     static_assert(std::is_same<bool, decltype(base::empty(array))>::value,
 164                   "base::empty(array) should be of type bool");
 165     static_assert(!base::empty(array), "base::empty(array) should be false");
 166   }
 167
 168   {
 169     constexpr std::initializer_list<int> il;
 170     static_assert(std::is_same<bool, decltype(base::empty(il))>::value,
 171                   "base::empty(il) should be of type bool");
 172     static_assert(base::empty(il), "base::empty(il) should be true");
 173   }
 174 }
 175
 176 TEST(STLUtilTest, Data) {
 177   {
 178     std::vector<int> vector = {1, 2, 3, 4, 5};
 179     static_assert(
 180         std::is_same<decltype(base::data(vector)),
 181                      decltype(vector.data())>::value,
 182         "base::data(vector) should have the same type as vector.data()");
 183     EXPECT_EQ(vector.data(), base::data(vector));
 184   }
 185
 186   {
 187     const std::string cstr = "const string";
 188     static_assert(
 189         std::is_same<decltype(base::data(cstr)), decltype(cstr.data())>::value,
 190         "base::data(cstr) should have the same type as cstr.data()");
 191
 192     EXPECT_EQ(cstr.data(), base::data(cstr));
 193   }
 194
 195   {
 196     std::string str = "mutable string";
 197     static_assert(std::is_same<decltype(base::data(str)), char*>::value,
 198                   "base::data(str) should be of type char*");
 199     EXPECT_EQ(str.data(), base::data(str));
 200   }
 201
 202   {
 203     std::string empty_str;
 204     static_assert(std::is_same<decltype(base::data(empty_str)), char*>::value,
 205                   "base::data(empty_str) should be of type char*");
 206     EXPECT_EQ(empty_str.data(), base::data(empty_str));
 207   }
 208
 209   {
 210     std::array<int, 4> array = {{1, 2, 3, 4}};
 211     static_assert(
 212         std::is_same<decltype(base::data(array)),
 213                      decltype(array.data())>::value,
 214         "base::data(array) should have the same type as array.data()");
 215     // std::array::data() is not constexpr prior to C++17, hence the runtime
 216     // check.
 217     EXPECT_EQ(array.data(), base::data(array));
 218   }
 219
 220   {
 221     constexpr int array[] = {1, 2, 3};
 222     static_assert(std::is_same<const int*, decltype(base::data(array))>::value,
 223                   "base::data(array) should be of type const int*");
 224     static_assert(array == base::data(array),
 225                   "base::data(array) should be array");
 226   }
 227
 228   {
 229     constexpr std::initializer_list<int> il;
 230     static_assert(
 231         std::is_same<decltype(il.begin()), decltype(base::data(il))>::value,
 232         "base::data(il) should have the same type as il.begin()");
 233     static_assert(il.begin() == base::data(il),
 234                   "base::data(il) should be equal to il.begin()");
 235   }
 236 }
 237
 238 TEST(STLUtilTest, GetUnderlyingContainer) {
 239   {
 240     std::queue<int> queue({1, 2, 3, 4, 5});
 241     static_assert(std::is_same<decltype(GetUnderlyingContainer(queue)),
 242                                const std::deque<int>&>::value,
 243                   "GetUnderlyingContainer(queue) should be of type deque");
 244     EXPECT_THAT(GetUnderlyingContainer(queue),
 245                 testing::ElementsAre(1, 2, 3, 4, 5));
 246   }
 247
 248   {
 249     std::queue<int> queue;
 250     EXPECT_THAT(GetUnderlyingContainer(queue), testing::ElementsAre());
 251   }
 252
 253   {
 254     base::queue<int> queue({1, 2, 3, 4, 5});
 255     static_assert(
 256         std::is_same<decltype(GetUnderlyingContainer(queue)),
 257                      const base::circular_deque<int>&>::value,
 258         "GetUnderlyingContainer(queue) should be of type circular_deque");
 259     EXPECT_THAT(GetUnderlyingContainer(queue),
 260                 testing::ElementsAre(1, 2, 3, 4, 5));
 261   }
 262
 263   {
 264     std::vector<int> values = {1, 2, 3, 4, 5};
 265     std::priority_queue<int> queue(values.begin(), values.end());
 266     static_assert(std::is_same<decltype(GetUnderlyingContainer(queue)),
 267                                const std::vector<int>&>::value,
 268                   "GetUnderlyingContainer(queue) should be of type vector");
 269     EXPECT_THAT(GetUnderlyingContainer(queue),
 270                 testing::UnorderedElementsAre(1, 2, 3, 4, 5));
 271   }
 272
 273   {
 274     std::stack<int> stack({1, 2, 3, 4, 5});
 275     static_assert(std::is_same<decltype(GetUnderlyingContainer(stack)),
 276                                const std::deque<int>&>::value,
 277                   "GetUnderlyingContainer(stack) should be of type deque");
 278     EXPECT_THAT(GetUnderlyingContainer(stack),
 279                 testing::ElementsAre(1, 2, 3, 4, 5));
 280   }
 281 }
 282
 283 TEST(STLUtilTest, STLIsSorted) {
 284   {
 285     std::set<int> set;
 286     set.insert(24);
 287     set.insert(1);
 288     set.insert(12);
 289     EXPECT_TRUE(STLIsSorted(set));
 290   }
 291
 292   {
 293     std::set<ComparableValue> set;
 294     set.insert(ComparableValue(24));
 295     set.insert(ComparableValue(1));
 296     set.insert(ComparableValue(12));
 297     EXPECT_TRUE(STLIsSorted(set));
 298   }
 299
 300   {
 301     std::vector<int> vector;
 302     vector.push_back(1);
 303     vector.push_back(1);
 304     vector.push_back(4);
 305     vector.push_back(64);
 306     vector.push_back(12432);
 307     EXPECT_TRUE(STLIsSorted(vector));
 308     vector.back() = 1;
 309     EXPECT_FALSE(STLIsSorted(vector));
 310   }
 311 }
 312
 313 TEST(STLUtilTest, STLSetDifference) {
 314   std::set<int> a1;
 315   a1.insert(1);
 316   a1.insert(2);
 317   a1.insert(3);
 318   a1.insert(4);
 319
 320   std::set<int> a2;
 321   a2.insert(3);
 322   a2.insert(4);
 323   a2.insert(5);
 324   a2.insert(6);
 325   a2.insert(7);
 326
 327   {
 328     std::set<int> difference;
 329     difference.insert(1);
 330     difference.insert(2);
 331     EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a1, a2));
 332   }
 333
 334   {
 335     std::set<int> difference;
 336     difference.insert(5);
 337     difference.insert(6);
 338     difference.insert(7);
 339     EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a2, a1));
 340   }
 341
 342   {
 343     std::vector<int> difference;
 344     difference.push_back(1);
 345     difference.push_back(2);
 346     EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a1, a2));
 347   }
 348
 349   {
 350     std::vector<int> difference;
 351     difference.push_back(5);
 352     difference.push_back(6);
 353     difference.push_back(7);
 354     EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a2, a1));
 355   }
 356 }
 357
 358 TEST(STLUtilTest, STLSetUnion) {
 359   std::set<int> a1;
 360   a1.insert(1);
 361   a1.insert(2);
 362   a1.insert(3);
 363   a1.insert(4);
 364
 365   std::set<int> a2;
 366   a2.insert(3);
 367   a2.insert(4);
 368   a2.insert(5);
 369   a2.insert(6);
 370   a2.insert(7);
 371
 372   {
 373     std::set<int> result;
 374     result.insert(1);
 375     result.insert(2);
 376     result.insert(3);
 377     result.insert(4);
 378     result.insert(5);
 379     result.insert(6);
 380     result.insert(7);
 381     EXPECT_EQ(result, STLSetUnion<std::set<int> >(a1, a2));
 382   }
 383
 384   {
 385     std::set<int> result;
 386     result.insert(1);
 387     result.insert(2);
 388     result.insert(3);
 389     result.insert(4);
 390     result.insert(5);
 391     result.insert(6);
 392     result.insert(7);
 393     EXPECT_EQ(result, STLSetUnion<std::set<int> >(a2, a1));
 394   }
 395
 396   {
 397     std::vector<int> result;
 398     result.push_back(1);
 399     result.push_back(2);
 400     result.push_back(3);
 401     result.push_back(4);
 402     result.push_back(5);
 403     result.push_back(6);
 404     result.push_back(7);
 405     EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a1, a2));
 406   }
 407
 408   {
 409     std::vector<int> result;
 410     result.push_back(1);
 411     result.push_back(2);
 412     result.push_back(3);
 413     result.push_back(4);
 414     result.push_back(5);
 415     result.push_back(6);
 416     result.push_back(7);
 417     EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a2, a1));
 418   }
 419 }
 420
 421 TEST(STLUtilTest, STLSetIntersection) {
 422   std::set<int> a1;
 423   a1.insert(1);
 424   a1.insert(2);
 425   a1.insert(3);
 426   a1.insert(4);
 427
 428   std::set<int> a2;
 429   a2.insert(3);
 430   a2.insert(4);
 431   a2.insert(5);
 432   a2.insert(6);
 433   a2.insert(7);
 434
 435   {
 436     std::set<int> result;
 437     result.insert(3);
 438     result.insert(4);
 439     EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a1, a2));
 440   }
 441
 442   {
 443     std::set<int> result;
 444     result.insert(3);
 445     result.insert(4);
 446     EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a2, a1));
 447   }
 448
 449   {
 450     std::vector<int> result;
 451     result.push_back(3);
 452     result.push_back(4);
 453     EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a1, a2));
 454   }
 455
 456   {
 457     std::vector<int> result;
 458     result.push_back(3);
 459     result.push_back(4);
 460     EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a2, a1));
 461   }
 462 }
 463
 464 TEST(STLUtilTest, STLIncludes) {
 465   std::set<int> a1;
 466   a1.insert(1);
 467   a1.insert(2);
 468   a1.insert(3);
 469   a1.insert(4);
 470
 471   std::set<int> a2;
 472   a2.insert(3);
 473   a2.insert(4);
 474
 475   std::set<int> a3;
 476   a3.insert(3);
 477   a3.insert(4);
 478   a3.insert(5);
 479
 480   EXPECT_TRUE(STLIncludes<std::set<int> >(a1, a2));
 481   EXPECT_FALSE(STLIncludes<std::set<int> >(a1, a3));
 482   EXPECT_FALSE(STLIncludes<std::set<int> >(a2, a1));
 483   EXPECT_FALSE(STLIncludes<std::set<int> >(a2, a3));
 484   EXPECT_FALSE(STLIncludes<std::set<int> >(a3, a1));
 485   EXPECT_TRUE(STLIncludes<std::set<int> >(a3, a2));
 486 }
 487
 488 TEST(Erase, String) {
 489   const std::pair<std::string, std::string> test_data[] = {
 490       {"", ""}, {"abc", "bc"}, {"abca", "bc"},
 491   };
 492
 493   for (auto test_case : test_data) {
 494     Erase(test_case.first, 'a');
 495     EXPECT_EQ(test_case.second, test_case.first);
 496   }
 497
 498   for (auto test_case : test_data) {
 499     EraseIf(test_case.first, [](char elem) { return elem < 'b'; });
 500     EXPECT_EQ(test_case.second, test_case.first);
 501   }
 502 }
 503
 504 TEST(Erase, String16) {
 505   std::pair<base::string16, base::string16> test_data[] = {
 506       {base::string16(), base::string16()},
 507       {UTF8ToUTF16("abc"), UTF8ToUTF16("bc")},
 508       {UTF8ToUTF16("abca"), UTF8ToUTF16("bc")},
 509   };
 510
 511   const base::string16 letters = UTF8ToUTF16("ab");
 512   for (auto test_case : test_data) {
 513     Erase(test_case.first, letters[0]);
 514     EXPECT_EQ(test_case.second, test_case.first);
 515   }
 516
 517   for (auto test_case : test_data) {
 518     EraseIf(test_case.first, [&](short elem) { return elem < letters[1]; });
 519     EXPECT_EQ(test_case.second, test_case.first);
 520   }
 521 }
 522
 523 TEST(Erase, Deque) {
 524   RunEraseTest<std::deque<int>>();
 525   RunEraseIfTest<std::deque<std::pair<int, int>>>();
 526 }
 527
 528 TEST(Erase, Vector) {
 529   RunEraseTest<std::vector<int>>();
 530   RunEraseIfTest<std::vector<std::pair<int, int>>>();
 531 }
 532
 533 TEST(Erase, ForwardList) {
 534   RunEraseTest<std::forward_list<int>>();
 535   RunEraseIfTest<std::forward_list<std::pair<int, int>>>();
 536 }
 537
 538 TEST(Erase, List) {
 539   RunEraseTest<std::list<int>>();
 540   RunEraseIfTest<std::list<std::pair<int, int>>>();
 541 }
 542
 543 TEST(Erase, Map) {
 544   RunEraseIfTest<std::map<int, int>>();
 545   RunEraseIfTest<std::map<int, int, std::greater<int>>>();
 546 }
 547
 548 TEST(Erase, Multimap) {
 549   RunEraseIfTest<std::multimap<int, int>>();
 550   RunEraseIfTest<std::multimap<int, int, std::greater<int>>>();
 551 }
 552
 553 TEST(Erase, Set) {
 554   RunEraseIfTest<std::set<std::pair<int, int>>>();
 555   RunEraseIfTest<
 556       std::set<std::pair<int, int>, std::greater<std::pair<int, int>>>>();
 557 }
 558
 559 TEST(Erase, Multiset) {
 560   RunEraseIfTest<std::multiset<std::pair<int, int>>>();
 561   RunEraseIfTest<
 562       std::multiset<std::pair<int, int>, std::greater<std::pair<int, int>>>>();
 563 }
 564
 565 TEST(Erase, UnorderedMap) {
 566   RunEraseIfTest<std::unordered_map<int, int>>();
 567   RunEraseIfTest<std::unordered_map<int, int, CustomIntHash>>();
 568 }
 569
 570 TEST(Erase, UnorderedMultimap) {
 571   RunEraseIfTest<std::unordered_multimap<int, int>>();
 572   RunEraseIfTest<std::unordered_multimap<int, int, CustomIntHash>>();
 573 }
 574
 575 TEST(Erase, UnorderedSet) {
 576   RunEraseIfTest<std::unordered_set<std::pair<int, int>, HashByFirst>>();
 577 }
 578
 579 TEST(Erase, UnorderedMultiset) {
 580   RunEraseIfTest<std::unordered_multiset<std::pair<int, int>, HashByFirst>>();
 581 }
 582
 583 TEST(Erase, IsNotIn) {
 584   // Should keep both '2' but only one '4', like std::set_intersection.
 585   std::vector<int> lhs = {0, 2, 2, 4, 4, 4, 6, 8, 10};
 586   std::vector<int> rhs = {1, 2, 2, 4, 5, 6, 7};
 587   std::vector<int> expected = {2, 2, 4, 6};
 588   EraseIf(lhs, IsNotIn<std::vector<int>>(rhs));
 589   EXPECT_EQ(expected, lhs);
 590 }
 591
 592 TEST(ContainsValue, OrdinaryArrays) {
 593   const char allowed_chars[] = {'a', 'b', 'c', 'd'};
 594   EXPECT_TRUE(ContainsValue(allowed_chars, 'a'));
 595   EXPECT_FALSE(ContainsValue(allowed_chars, 'z'));
 596   EXPECT_FALSE(ContainsValue(allowed_chars, 0));
 597
 598   const char allowed_chars_including_nul[] = "abcd";
 599   EXPECT_TRUE(ContainsValue(allowed_chars_including_nul, 0));
 600 }
 601
 602 TEST(STLUtilTest, OptionalOrNullptr) {
 603   Optional<float> optional;
 604   EXPECT_EQ(nullptr, base::OptionalOrNullptr(optional));
 605
 606   optional = 0.1f;
 607   EXPECT_EQ(&optional.value(), base::OptionalOrNullptr(optional));
 608   EXPECT_NE(nullptr, base::OptionalOrNullptr(optional));
 609 }
 610
 611 }  // namespace
 612 }  // namespace base