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/cxx20_erase_vector.h"
  25 #include "base/containers/queue.h"
  26 #include "testing/gmock/include/gmock/gmock.h"
  27 #include "testing/gtest/include/gtest/gtest.h"
  28 #include "third_party/abseil-cpp/absl/types/optional.h"
  29
  30 namespace {
  31
  32 using ::testing::IsNull;
  33 using ::testing::Pair;
  34
  35 template <typename Container>
  36 void RunConstCastIteratorTest() {
  37   using std::begin;
  38   using std::cbegin;
  39
  40   Container c = {1, 2, 3, 4, 5};
  41   auto c_it = std::next(cbegin(c), 3);
  42   auto it = base::ConstCastIterator(c, c_it);
  43   static_assert(std::is_same<decltype(cbegin(std::declval<Container&>())),
  44                              decltype(c_it)>::value,
  45                 "c_it is not a constant iterator.");
  46   static_assert(std::is_same<decltype(begin(std::declval<Container&>())),
  47                              decltype(it)>::value,
  48                 "it is not a iterator.");
  49   EXPECT_EQ(c_it, it);
  50   // Const casting the iterator should not modify the underlying container.
  51   Container other = {1, 2, 3, 4, 5};
  52   EXPECT_THAT(c, testing::ContainerEq(other));
  53 }
  54
  55 }  // namespace
  56
  57 namespace base {
  58 namespace {
  59
  60 TEST(STLUtilTest, ToUnderlying) {
  61   enum Enum : int {
  62     kOne = 1,
  63     kTwo = 2,
  64   };
  65
  66   enum class ScopedEnum : char {
  67     kOne = 1,
  68     kTwo = 2,
  69   };
  70
  71   static_assert(std::is_same<decltype(to_underlying(kOne)), int>::value, "");
  72   static_assert(std::is_same<decltype(to_underlying(kTwo)), int>::value, "");
  73   static_assert(to_underlying(kOne) == 1, "");
  74   static_assert(to_underlying(kTwo) == 2, "");
  75
  76   static_assert(
  77       std::is_same<decltype(to_underlying(ScopedEnum::kOne)), char>::value, "");
  78   static_assert(
  79       std::is_same<decltype(to_underlying(ScopedEnum::kTwo)), char>::value, "");
  80   static_assert(to_underlying(ScopedEnum::kOne) == 1, "");
  81   static_assert(to_underlying(ScopedEnum::kTwo) == 2, "");
  82 }
  83
  84 TEST(STLUtilTest, GetUnderlyingContainer) {
  85   {
  86     std::queue<int> queue({1, 2, 3, 4, 5});
  87     static_assert(std::is_same<decltype(GetUnderlyingContainer(queue)),
  88                                const std::deque<int>&>::value,
  89                   "GetUnderlyingContainer(queue) should be of type deque");
  90     EXPECT_THAT(GetUnderlyingContainer(queue),
  91                 testing::ElementsAre(1, 2, 3, 4, 5));
  92   }
  93
  94   {
  95     std::queue<int> queue;
  96     EXPECT_THAT(GetUnderlyingContainer(queue), testing::ElementsAre());
  97   }
  98
  99   {
 100     base::queue<int> queue({1, 2, 3, 4, 5});
 101     static_assert(
 102         std::is_same<decltype(GetUnderlyingContainer(queue)),
 103                      const base::circular_deque<int>&>::value,
 104         "GetUnderlyingContainer(queue) should be of type circular_deque");
 105     EXPECT_THAT(GetUnderlyingContainer(queue),
 106                 testing::ElementsAre(1, 2, 3, 4, 5));
 107   }
 108
 109   {
 110     std::vector<int> values = {1, 2, 3, 4, 5};
 111     std::priority_queue<int> queue(values.begin(), values.end());
 112     static_assert(std::is_same<decltype(GetUnderlyingContainer(queue)),
 113                                const std::vector<int>&>::value,
 114                   "GetUnderlyingContainer(queue) should be of type vector");
 115     EXPECT_THAT(GetUnderlyingContainer(queue),
 116                 testing::UnorderedElementsAre(1, 2, 3, 4, 5));
 117   }
 118
 119   {
 120     std::stack<int> stack({1, 2, 3, 4, 5});
 121     static_assert(std::is_same<decltype(GetUnderlyingContainer(stack)),
 122                                const std::deque<int>&>::value,
 123                   "GetUnderlyingContainer(stack) should be of type deque");
 124     EXPECT_THAT(GetUnderlyingContainer(stack),
 125                 testing::ElementsAre(1, 2, 3, 4, 5));
 126   }
 127 }
 128
 129 TEST(STLUtilTest, ConstCastIterator) {
 130   // Sequence Containers
 131   RunConstCastIteratorTest<std::forward_list<int>>();
 132   RunConstCastIteratorTest<std::list<int>>();
 133   RunConstCastIteratorTest<std::deque<int>>();
 134   RunConstCastIteratorTest<std::vector<int>>();
 135   RunConstCastIteratorTest<std::array<int, 5>>();
 136   RunConstCastIteratorTest<int[5]>();
 137
 138   // Associative Containers
 139   RunConstCastIteratorTest<std::set<int>>();
 140   RunConstCastIteratorTest<std::multiset<int>>();
 141
 142   // Unordered Associative Containers
 143   RunConstCastIteratorTest<std::unordered_set<int>>();
 144   RunConstCastIteratorTest<std::unordered_multiset<int>>();
 145 }
 146
 147 TEST(STLUtilTest, STLSetDifference) {
 148   std::set<int> a1;
 149   a1.insert(1);
 150   a1.insert(2);
 151   a1.insert(3);
 152   a1.insert(4);
 153
 154   std::set<int> a2;
 155   a2.insert(3);
 156   a2.insert(4);
 157   a2.insert(5);
 158   a2.insert(6);
 159   a2.insert(7);
 160
 161   {
 162     std::set<int> difference;
 163     difference.insert(1);
 164     difference.insert(2);
 165     EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a1, a2));
 166   }
 167
 168   {
 169     std::set<int> difference;
 170     difference.insert(5);
 171     difference.insert(6);
 172     difference.insert(7);
 173     EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a2, a1));
 174   }
 175
 176   {
 177     std::vector<int> difference;
 178     difference.push_back(1);
 179     difference.push_back(2);
 180     EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a1, a2));
 181   }
 182
 183   {
 184     std::vector<int> difference;
 185     difference.push_back(5);
 186     difference.push_back(6);
 187     difference.push_back(7);
 188     EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a2, a1));
 189   }
 190 }
 191
 192 TEST(STLUtilTest, STLSetUnion) {
 193   std::set<int> a1;
 194   a1.insert(1);
 195   a1.insert(2);
 196   a1.insert(3);
 197   a1.insert(4);
 198
 199   std::set<int> a2;
 200   a2.insert(3);
 201   a2.insert(4);
 202   a2.insert(5);
 203   a2.insert(6);
 204   a2.insert(7);
 205
 206   {
 207     std::set<int> result;
 208     result.insert(1);
 209     result.insert(2);
 210     result.insert(3);
 211     result.insert(4);
 212     result.insert(5);
 213     result.insert(6);
 214     result.insert(7);
 215     EXPECT_EQ(result, STLSetUnion<std::set<int> >(a1, a2));
 216   }
 217
 218   {
 219     std::set<int> result;
 220     result.insert(1);
 221     result.insert(2);
 222     result.insert(3);
 223     result.insert(4);
 224     result.insert(5);
 225     result.insert(6);
 226     result.insert(7);
 227     EXPECT_EQ(result, STLSetUnion<std::set<int> >(a2, a1));
 228   }
 229
 230   {
 231     std::vector<int> result;
 232     result.push_back(1);
 233     result.push_back(2);
 234     result.push_back(3);
 235     result.push_back(4);
 236     result.push_back(5);
 237     result.push_back(6);
 238     result.push_back(7);
 239     EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a1, a2));
 240   }
 241
 242   {
 243     std::vector<int> result;
 244     result.push_back(1);
 245     result.push_back(2);
 246     result.push_back(3);
 247     result.push_back(4);
 248     result.push_back(5);
 249     result.push_back(6);
 250     result.push_back(7);
 251     EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a2, a1));
 252   }
 253 }
 254
 255 TEST(STLUtilTest, STLSetIntersection) {
 256   std::set<int> a1;
 257   a1.insert(1);
 258   a1.insert(2);
 259   a1.insert(3);
 260   a1.insert(4);
 261
 262   std::set<int> a2;
 263   a2.insert(3);
 264   a2.insert(4);
 265   a2.insert(5);
 266   a2.insert(6);
 267   a2.insert(7);
 268
 269   {
 270     std::set<int> result;
 271     result.insert(3);
 272     result.insert(4);
 273     EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a1, a2));
 274   }
 275
 276   {
 277     std::set<int> result;
 278     result.insert(3);
 279     result.insert(4);
 280     EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a2, a1));
 281   }
 282
 283   {
 284     std::vector<int> result;
 285     result.push_back(3);
 286     result.push_back(4);
 287     EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a1, a2));
 288   }
 289
 290   {
 291     std::vector<int> result;
 292     result.push_back(3);
 293     result.push_back(4);
 294     EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a2, a1));
 295   }
 296 }
 297
 298 TEST(Erase, IsNotIn) {
 299   // Should keep both '2' but only one '4', like std::set_intersection.
 300   std::vector<int> lhs = {0, 2, 2, 4, 4, 4, 6, 8, 10};
 301   std::vector<int> rhs = {1, 2, 2, 4, 5, 6, 7};
 302   std::vector<int> expected = {2, 2, 4, 6};
 303   EXPECT_EQ(5u, EraseIf(lhs, IsNotIn<std::vector<int>>(rhs)));
 304   EXPECT_EQ(expected, lhs);
 305 }
 306
 307 TEST(STLUtilTest, InsertOrAssign) {
 308   std::map<std::string, int> my_map;
 309   auto result = InsertOrAssign(my_map, "Hello", 42);
 310   EXPECT_THAT(*result.first, Pair("Hello", 42));
 311   EXPECT_TRUE(result.second);
 312
 313   result = InsertOrAssign(my_map, "Hello", 43);
 314   EXPECT_THAT(*result.first, Pair("Hello", 43));
 315   EXPECT_FALSE(result.second);
 316 }
 317
 318 TEST(STLUtilTest, InsertOrAssignHint) {
 319   std::map<std::string, int> my_map;
 320   auto result = InsertOrAssign(my_map, my_map.end(), "Hello", 42);
 321   EXPECT_THAT(*result, Pair("Hello", 42));
 322
 323   result = InsertOrAssign(my_map, my_map.begin(), "Hello", 43);
 324   EXPECT_THAT(*result, Pair("Hello", 43));
 325 }
 326
 327 TEST(STLUtilTest, InsertOrAssignWrongHints) {
 328   std::map<int, int> my_map;
 329   // Since we insert keys in sorted order, my_map.begin() will be a wrong hint
 330   // after the first iteration. Check that insertion happens anyway.
 331   for (int i = 0; i < 10; ++i) {
 332     SCOPED_TRACE(i);
 333     auto result = InsertOrAssign(my_map, my_map.begin(), i, i);
 334     EXPECT_THAT(*result, Pair(i, i));
 335   }
 336
 337   // Overwrite the keys we just inserted. Since we no longer insert into the
 338   // map, my_map.end() will be a wrong hint for all iterations but the last.
 339   for (int i = 0; i < 10; ++i) {
 340     SCOPED_TRACE(10 + i);
 341     auto result = InsertOrAssign(my_map, my_map.end(), i, 10 + i);
 342     EXPECT_THAT(*result, Pair(i, 10 + i));
 343   }
 344 }
 345
 346 TEST(STLUtilTest, TryEmplace) {
 347   std::map<std::string, std::unique_ptr<int>> my_map;
 348   auto result = TryEmplace(my_map, "Hello", nullptr);
 349   EXPECT_THAT(*result.first, Pair("Hello", IsNull()));
 350   EXPECT_TRUE(result.second);
 351
 352   auto new_value = std::make_unique<int>(42);
 353   result = TryEmplace(my_map, "Hello", std::move(new_value));
 354   EXPECT_THAT(*result.first, Pair("Hello", IsNull()));
 355   EXPECT_FALSE(result.second);
 356   // |new_value| should not be touched following a failed insertion.
 357   ASSERT_NE(nullptr, new_value);
 358   EXPECT_EQ(42, *new_value);
 359
 360   result = TryEmplace(my_map, "World", std::move(new_value));
 361   EXPECT_EQ("World", result.first->first);
 362   EXPECT_EQ(42, *result.first->second);
 363   EXPECT_TRUE(result.second);
 364   EXPECT_EQ(nullptr, new_value);
 365 }
 366
 367 TEST(STLUtilTest, TryEmplaceHint) {
 368   std::map<std::string, std::unique_ptr<int>> my_map;
 369   auto result = TryEmplace(my_map, my_map.begin(), "Hello", nullptr);
 370   EXPECT_THAT(*result, Pair("Hello", IsNull()));
 371
 372   auto new_value = std::make_unique<int>(42);
 373   result = TryEmplace(my_map, result, "Hello", std::move(new_value));
 374   EXPECT_THAT(*result, Pair("Hello", IsNull()));
 375   // |new_value| should not be touched following a failed insertion.
 376   ASSERT_NE(nullptr, new_value);
 377   EXPECT_EQ(42, *new_value);
 378
 379   result = TryEmplace(my_map, result, "World", std::move(new_value));
 380   EXPECT_EQ("World", result->first);
 381   EXPECT_EQ(42, *result->second);
 382   EXPECT_EQ(nullptr, new_value);
 383 }
 384
 385 TEST(STLUtilTest, TryEmplaceWrongHints) {
 386   std::map<int, int> my_map;
 387   // Since we emplace keys in sorted order, my_map.begin() will be a wrong hint
 388   // after the first iteration. Check that emplacement happens anyway.
 389   for (int i = 0; i < 10; ++i) {
 390     SCOPED_TRACE(i);
 391     auto result = TryEmplace(my_map, my_map.begin(), i, i);
 392     EXPECT_THAT(*result, Pair(i, i));
 393   }
 394
 395   // Fail to overwrite the keys we just inserted. Since we no longer emplace
 396   // into the map, my_map.end() will be a wrong hint for all tried emplacements
 397   // but the last.
 398   for (int i = 0; i < 10; ++i) {
 399     SCOPED_TRACE(10 + i);
 400     auto result = TryEmplace(my_map, my_map.end(), i, 10 + i);
 401     EXPECT_THAT(*result, Pair(i, i));
 402   }
 403 }
 404
 405 TEST(STLUtilTest, OptionalOrNullptr) {
 406   absl::optional<float> optional;
 407   EXPECT_EQ(nullptr, base::OptionalOrNullptr(optional));
 408
 409   optional = 0.1f;
 410   EXPECT_EQ(&optional.value(), base::OptionalOrNullptr(optional));
 411   EXPECT_NE(nullptr, base::OptionalOrNullptr(optional));
 412 }
 413
 414 }  // namespace
 415 }  // namespace base