folly/test/ForeachTest.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <folly/Foreach.h>
  18
  19 #include <array>
  20 #include <initializer_list>
  21 #include <iterator>
  22 #include <list>
  23 #include <map>
  24 #include <string>
  25 #include <tuple>
  26 #include <vector>
  27
  28 #include <folly/portability/GTest.h>
  29
  30 using namespace folly;
  31 using namespace folly::detail;
  32
  33 namespace folly {
  34 namespace test {
  35
  36 class TestRValueConstruct {
  37  public:
  38   TestRValueConstruct() = default;
  39   TestRValueConstruct(TestRValueConstruct&&) noexcept {
  40     this->constructed_from_rvalue = true;
  41   }
  42   TestRValueConstruct(const TestRValueConstruct&) {
  43     this->constructed_from_rvalue = false;
  44   }
  45   TestRValueConstruct& operator=(const TestRValueConstruct&) = delete;
  46   TestRValueConstruct& operator=(TestRValueConstruct&&) = delete;
  47
  48   bool constructed_from_rvalue{false};
  49 };
  50
  51 class TestAdlIterable {
  52  public:
  53   std::vector<int> vec{0, 1, 2, 3};
  54 };
  55
  56 auto begin(TestAdlIterable& instance) {
  57   return instance.vec.begin();
  58 }
  59 auto begin(const TestAdlIterable& instance) {
  60   return instance.vec.begin();
  61 }
  62 auto end(TestAdlIterable& instance) {
  63   return instance.vec.end();
  64 }
  65 auto end(const TestAdlIterable& instance) {
  66   return instance.vec.end();
  67 }
  68
  69 class TestBothIndexingAndIter {
  70  public:
  71   class Iterator {
  72    public:
  73     using difference_type = std::size_t;
  74     using value_type = int;
  75     using pointer = int*;
  76     using reference = int&;
  77     using iterator_category = std::random_access_iterator_tag;
  78     int& operator*() {
  79       return this->val;
  80     }
  81     Iterator operator+(int) {
  82       return *this;
  83     }
  84     explicit Iterator(int& val_in) : val{val_in} {}
  85     int& val;
  86   };
  87   auto begin() {
  88     this->called_begin = true;
  89     return Iterator{val};
  90   }
  91   auto end() {
  92     return Iterator{val};
  93   }
  94   int& operator[](int) {
  95     return this->val;
  96   }
  97
  98   int val{0};
  99   bool called_begin = false;
 100 };
 101 } // namespace test
 102 } // namespace folly
 103
 104 TEST(Foreach, ForEachFunctionBasic) {
 105   auto range = std::make_tuple(1, 2, 3);
 106   auto result_range = std::vector<int>{};
 107   auto correct_result_range = std::vector<int>{1, 2, 3};
 108
 109   folly::for_each(range, [&](auto ele) { result_range.push_back(ele); });
 110
 111   EXPECT_TRUE(std::equal(
 112       result_range.begin(), result_range.end(), correct_result_range.begin()));
 113 }
 114
 115 TEST(Foreach, ForEachFunctionBasicRuntimeOneArg) {
 116   auto range = std::vector<int>{1, 2, 3};
 117   auto current = 0;
 118   folly::for_each(range, [&](auto ele) {
 119     if (current == 0) {
 120       EXPECT_EQ(ele, 1);
 121     } else if (current == 1) {
 122       EXPECT_EQ(ele, 2);
 123     } else {
 124       EXPECT_EQ(ele, 3);
 125     }
 126     ++current;
 127   });
 128 }
 129
 130 TEST(Foreach, ForEachFunctionBasicRuntimeTwoArg) {
 131   auto range = std::vector<int>{1, 2, 3};
 132   folly::for_each(range, [](auto ele, auto index) {
 133     EXPECT_TRUE(index < 3);
 134     if (index == 0) {
 135       EXPECT_EQ(ele, 1);
 136     } else if (index == 1) {
 137       EXPECT_EQ(ele, 2);
 138     } else if (index == 2) {
 139       EXPECT_EQ(ele, 3);
 140     }
 141   });
 142 }
 143
 144 TEST(Foreach, ForEachFunctionBasicRuntimeThreeArg) {
 145   auto range = std::list<int>{1, 2, 3};
 146   auto result_range = std::list<int>{1, 3};
 147   folly::for_each(range, [&](auto ele, auto, auto iter) {
 148     if (ele == 2) {
 149       range.erase(iter);
 150     }
 151   });
 152   EXPECT_TRUE(std::equal(range.begin(), range.end(), result_range.begin()));
 153 }
 154
 155 TEST(Foreach, ForEachFunctionBasicTupleOneArg) {
 156   auto range = std::make_tuple(1, 2, 3);
 157   auto current = 0;
 158   folly::for_each(range, [&](auto ele) {
 159     if (current == 0) {
 160       EXPECT_EQ(ele, 1);
 161     } else if (current == 1) {
 162       EXPECT_EQ(ele, 2);
 163     } else {
 164       EXPECT_EQ(ele, 3);
 165     }
 166     ++current;
 167   });
 168 }
 169
 170 TEST(Foreach, ForEachFunctionBasicTupleTwoArg) {
 171   auto range = std::make_tuple(1, 2, 3);
 172   folly::for_each(range, [](auto ele, auto index) {
 173     EXPECT_TRUE(index < 3);
 174     if (index == 0) {
 175       EXPECT_EQ(ele, 1);
 176     } else if (index == 1) {
 177       EXPECT_EQ(ele, 2);
 178     } else if (index == 2) {
 179       EXPECT_EQ(ele, 3);
 180     }
 181   });
 182 }
 183
 184 TEST(Foreach, ForEachFunctionBreakRuntimeOneArg) {
 185   auto range = std::vector<int>{1, 2, 3};
 186   auto iterations = 0;
 187   folly::for_each(range, [&](auto) {
 188     ++iterations;
 189     if (iterations == 1) {
 190       return folly::loop_break;
 191     }
 192     return folly::loop_continue;
 193   });
 194   EXPECT_EQ(iterations, 1);
 195 }
 196
 197 TEST(Foreach, ForEachFunctionBreakRuntimeTwoArg) {
 198   auto range = std::vector<int>{1, 2, 3};
 199   auto iterations = 0;
 200   folly::for_each(range, [&](auto, auto index) {
 201     ++iterations;
 202     if (index == 1) {
 203       return folly::loop_break;
 204     }
 205     return folly::loop_continue;
 206   });
 207   EXPECT_EQ(iterations, 2);
 208 }
 209
 210 TEST(Foreach, ForEachFunctionBreakRuntimeThreeArg) {
 211   auto range = std::vector<int>{1, 2, 3};
 212   auto iterations = 0;
 213   folly::for_each(range, [&](auto, auto index, auto) {
 214     ++iterations;
 215     if (index == 1) {
 216       return folly::loop_break;
 217     }
 218     return folly::loop_continue;
 219   });
 220   EXPECT_EQ(iterations, 2);
 221 }
 222
 223 TEST(Foreach, ForEachFunctionBreakTupleOneArg) {
 224   auto range = std::vector<int>{1, 2, 3};
 225   auto iterations = 0;
 226   folly::for_each(range, [&](auto) {
 227     ++iterations;
 228     if (iterations == 1) {
 229       return folly::loop_break;
 230     }
 231     return folly::loop_continue;
 232   });
 233   EXPECT_EQ(iterations, 1);
 234 }
 235
 236 TEST(Foreach, ForEachFunctionBreakTupleTwoArg) {
 237   auto range = std::vector<int>{1, 2, 3};
 238   auto iterations = 0;
 239   folly::for_each(range, [&](auto, auto index) {
 240     ++iterations;
 241     if (index == 1) {
 242       return folly::loop_break;
 243     }
 244     return folly::loop_continue;
 245   });
 246   EXPECT_EQ(iterations, 2);
 247 }
 248
 249 TEST(Foreach, ForEachFunctionArray) {
 250   auto range = std::array<int, 3>{{1, 2, 3}};
 251   auto iterations = 0;
 252   folly::for_each(range, [&](auto, auto index) {
 253     ++iterations;
 254     if (index == 1) {
 255       return folly::loop_break;
 256     }
 257     return folly::loop_continue;
 258   });
 259   EXPECT_EQ(iterations, 2);
 260 }
 261
 262 TEST(Foreach, ForEachFunctionInitializerListBasic) {
 263   folly::for_each(std::initializer_list<int>{1, 2, 3}, [](auto ele) { ++ele; });
 264 }
 265
 266 TEST(Foreach, ForEachFunctionTestForward) {
 267   using folly::test::TestRValueConstruct;
 268   auto range_one = std::vector<TestRValueConstruct>{};
 269   range_one.resize(3);
 270
 271   folly::for_each(std::move(range_one), [](auto ele) {
 272     EXPECT_FALSE(ele.constructed_from_rvalue);
 273   });
 274
 275   folly::for_each(
 276       std::make_tuple(TestRValueConstruct{}, TestRValueConstruct{}),
 277       [](auto ele) { EXPECT_TRUE(ele.constructed_from_rvalue); });
 278 }
 279
 280 TEST(Foreach, ForEachFunctionAdlIterable) {
 281   auto range = test::TestAdlIterable{};
 282   auto iterations = 0;
 283   folly::for_each(range, [&](auto ele, auto index) {
 284     ++iterations;
 285     EXPECT_EQ(ele, index);
 286   });
 287   EXPECT_EQ(iterations, 4);
 288 }
 289
 290 TEST(ForEach, FetchRandomAccessIterator) {
 291   auto vec = std::vector<int>{1, 2, 3};
 292   auto& second = folly::fetch(vec, 1);
 293   EXPECT_EQ(second, 2);
 294   second = 3;
 295   EXPECT_EQ(second, 3);
 296 }
 297
 298 TEST(ForEach, FetchIndexing) {
 299   auto mp = std::map<int, int>{{1, 2}};
 300   auto& ele = folly::fetch(mp, 1);
 301   EXPECT_EQ(ele, 2);
 302   ele = 3;
 303   EXPECT_EQ(ele, 3);
 304 }
 305
 306 TEST(ForEach, FetchTuple) {
 307   auto mp = std::make_tuple(1, 2, 3);
 308   auto& ele = folly::fetch(mp, std::integral_constant<int, 1>{});
 309   EXPECT_EQ(ele, 2);
 310   ele = 3;
 311   EXPECT_EQ(ele, 3);
 312 }
 313
 314 TEST(ForEach, FetchTestPreferIterator) {
 315   auto range = test::TestBothIndexingAndIter{};
 316   auto& ele = folly::fetch(range, 0);
 317   EXPECT_TRUE(range.called_begin);
 318   EXPECT_EQ(ele, 0);
 319   ele = 2;
 320   EXPECT_EQ(folly::fetch(range, 0), 2);
 321 }
 322
 323 TEST(Foreach, ForEachRvalue) {
 324   const char* const hello = "hello";
 325   int n = 0;
 326   FOR_EACH(it, std::string(hello)) {
 327     ++n;
 328   }
 329   EXPECT_EQ(strlen(hello), n);
 330   FOR_EACH_R(it, std::string(hello)) {
 331     --n;
 332     EXPECT_EQ(hello[n], *it);
 333   }
 334   EXPECT_EQ(0, n);
 335 }
 336
 337 TEST(Foreach, ForEachNested) {
 338   const std::string hello = "hello";
 339   size_t n = 0;
 340   FOR_EACH(i, hello) {
 341     FOR_EACH(j, hello) {
 342       ++n;
 343     }
 344   }
 345   auto len = hello.size();
 346   EXPECT_EQ(len * len, n);
 347 }
 348
 349 TEST(Foreach, ForEachKV) {
 350   std::map<std::string, int> testMap;
 351   testMap["abc"] = 1;
 352   testMap["def"] = 2;
 353   std::string keys = "";
 354   int values = 0;
 355   int numEntries = 0;
 356   FOR_EACH_KV (key, value, testMap) {
 357     keys += key;
 358     values += value;
 359     ++numEntries;
 360   }
 361   EXPECT_EQ("abcdef", keys);
 362   EXPECT_EQ(3, values);
 363   EXPECT_EQ(2, numEntries);
 364 }
 365
 366 TEST(Foreach, ForEachKVBreak) {
 367   std::map<std::string, int> testMap;
 368   testMap["abc"] = 1;
 369   testMap["def"] = 2;
 370   std::string keys = "";
 371   int values = 0;
 372   int numEntries = 0;
 373   FOR_EACH_KV (key, value, testMap) {
 374     keys += key;
 375     values += value;
 376     ++numEntries;
 377     break;
 378   }
 379   EXPECT_EQ("abc", keys);
 380   EXPECT_EQ(1, values);
 381   EXPECT_EQ(1, numEntries);
 382 }
 383
 384 TEST(Foreach, ForEachKvWithMultiMap) {
 385   std::multimap<std::string, int> testMap;
 386   testMap.insert(std::make_pair("abc", 1));
 387   testMap.insert(std::make_pair("abc", 2));
 388   testMap.insert(std::make_pair("def", 3));
 389   std::string keys = "";
 390   int values = 0;
 391   int numEntries = 0;
 392   FOR_EACH_KV (key, value, testMap) {
 393     keys += key;
 394     values += value;
 395     ++numEntries;
 396   }
 397   EXPECT_EQ("abcabcdef", keys);
 398   EXPECT_EQ(6, values);
 399   EXPECT_EQ(3, numEntries);
 400 }
 401
 402 TEST(Foreach, ForEachEnumerate) {
 403   std::vector<int> vv;
 404   int sumAA = 0;
 405   int sumIter = 0;
 406   int numIterations = 0;
 407   FOR_EACH_ENUMERATE(aa, iter, vv) {
 408     sumAA += aa;
 409     sumIter += *iter;
 410     ++numIterations;
 411   }
 412   EXPECT_EQ(sumAA, 0);
 413   EXPECT_EQ(sumIter, 0);
 414   EXPECT_EQ(numIterations, 0);
 415
 416   vv.push_back(1);
 417   vv.push_back(3);
 418   vv.push_back(5);
 419   FOR_EACH_ENUMERATE(aa, iter, vv) {
 420     sumAA += aa;
 421     sumIter += *iter;
 422     ++numIterations;
 423   }
 424   EXPECT_EQ(sumAA, 3);   // 0 + 1 + 2
 425   EXPECT_EQ(sumIter, 9); // 1 + 3 + 5
 426   EXPECT_EQ(numIterations, 3);
 427 }
 428
 429 TEST(Foreach, ForEachEnumerateBreak) {
 430   std::vector<int> vv;
 431   int sumAA = 0;
 432   int sumIter = 0;
 433   int numIterations = 0;
 434   vv.push_back(1);
 435   vv.push_back(2);
 436   vv.push_back(4);
 437   vv.push_back(8);
 438   FOR_EACH_ENUMERATE(aa, iter, vv) {
 439     sumAA += aa;
 440     sumIter += *iter;
 441     ++numIterations;
 442     if (aa == 1) {
 443       break;
 444     }
 445   }
 446   EXPECT_EQ(sumAA, 1);   // 0 + 1
 447   EXPECT_EQ(sumIter, 3); // 1 + 2
 448   EXPECT_EQ(numIterations, 2);
 449 }
 450
 451 TEST(Foreach, ForEachRangeR) {
 452   int sum = 0;
 453
 454   FOR_EACH_RANGE_R (i, 0, 0) {
 455     sum += i;
 456   }
 457   EXPECT_EQ(0, sum);
 458
 459   FOR_EACH_RANGE_R (i, 0, -1) {
 460     sum += i;
 461   }
 462   EXPECT_EQ(0, sum);
 463
 464   FOR_EACH_RANGE_R (i, 0, 5) {
 465     sum += i;
 466   }
 467   EXPECT_EQ(10, sum);
 468
 469   std::list<int> lst = { 0, 1, 2, 3, 4 };
 470   sum = 0;
 471   FOR_EACH_RANGE_R (i, lst.begin(), lst.end()) {
 472     sum += *i;
 473   }
 474   EXPECT_EQ(10, sum);
 475 }