folly/experimental/test/GenTest.cpp

   1 /*
   2  * Copyright 2012 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 <glog/logging.h>
  18 #include <gtest/gtest.h>
  19 #include <iostream>
  20 #include <set>
  21 #include <vector>
  22 #include "folly/experimental/Gen.h"
  23 #include "folly/FBVector.h"
  24 #include "folly/dynamic.h"
  25
  26 using namespace folly::gen;
  27 using namespace folly;
  28 using std::ostream;
  29 using std::pair;
  30 using std::set;
  31 using std::unique_ptr;
  32 using std::vector;
  33 using std::tuple;
  34 using std::make_tuple;
  35 //using std::unordered_map;
  36
  37 #define EXPECT_SAME(A, B) \
  38   static_assert(std::is_same<A, B>::value, "Mismatched: " #A ", " #B)
  39 EXPECT_SAME(int&&, typename ArgumentReference<int>::type);
  40 EXPECT_SAME(int&, typename ArgumentReference<int&>::type);
  41 EXPECT_SAME(const int&, typename ArgumentReference<const int&>::type);
  42 EXPECT_SAME(const int&, typename ArgumentReference<const int>::type);
  43
  44 template<typename T>
  45 ostream& operator<<(ostream& os, const set<T>& values) {
  46   return os << from(values);
  47 }
  48
  49 template<typename T>
  50 ostream& operator<<(ostream& os, const vector<T>& values) {
  51   os << "[";
  52   for (auto& value : values) {
  53     if (&value != &values.front()) {
  54       os << " ";
  55     }
  56     os << value;
  57   }
  58   return os << "]";
  59 }
  60
  61 auto square = [](int x) { return x * x; };
  62 auto add = [](int a, int b) { return a + b; };
  63 auto multiply = [](int a, int b) { return a * b; };
  64
  65 auto product = foldl(1, multiply);
  66
  67 template<typename A, typename B>
  68 ostream& operator<<(ostream& os, const pair<A, B>& pair) {
  69   return os << "(" << pair.first << ", " << pair.second << ")";
  70 }
  71
  72 TEST(Gen, Count) {
  73   auto gen = seq(1, 10);
  74   EXPECT_EQ(10, gen | count);
  75   EXPECT_EQ(5, gen | take(5) | count);
  76 }
  77
  78 TEST(Gen, Sum) {
  79   auto gen = seq(1, 10);
  80   EXPECT_EQ((1 + 10) * 10 / 2, gen | sum);
  81   EXPECT_EQ((1 + 5) * 5 / 2, gen | take(5) | sum);
  82 }
  83
  84 TEST(Gen, Foreach) {
  85   auto gen = seq(1, 4);
  86   int accum = 0;
  87   gen | [&](int x) { accum += x; };
  88   EXPECT_EQ(10, accum);
  89   int accum2 = 0;
  90   gen | take(3) | [&](int x) { accum2 += x; };
  91   EXPECT_EQ(6, accum2);
  92 }
  93
  94 TEST(Gen, Map) {
  95   auto expected = vector<int>{4, 9, 16};
  96   auto gen = from({2, 3, 4}) | map(square);
  97   EXPECT_EQ((vector<int>{4, 9, 16}), gen | as<vector>());
  98   EXPECT_EQ((vector<int>{4, 9}), gen | take(2) | as<vector>());
  99 }
 100
 101 TEST(Gen, Seq) {
 102   // cover the fenceposts of the loop unrolling
 103   for (int n = 1; n < 100; ++n) {
 104     EXPECT_EQ(n, seq(1, n) | count);
 105     EXPECT_EQ(n + 1, seq(1) | take(n + 1) | count);
 106   }
 107 }
 108
 109 TEST(Gen, Range) {
 110   // cover the fenceposts of the loop unrolling
 111   for (int n = 1; n < 100; ++n) {
 112     EXPECT_EQ(range(0, n) | count, n);
 113   }
 114 }
 115
 116 TEST(Gen, FromIterators) {
 117   vector<int> source {2, 3, 5, 7, 11};
 118   auto gen = from(makeRange(source.begin() + 1, source.end() - 1));
 119   EXPECT_EQ(3 * 5 * 7, gen | product);
 120 }
 121
 122 TEST(Gen, FromMap) {
 123   auto source = seq(0, 10)
 124               | map([](int i) { return std::make_pair(i, i * i); })
 125               | as<std::map<int, int>>();
 126   auto gen = fromConst(source)
 127            | map([&](const std::pair<const int, int>& p) {
 128                return p.second - p.first;
 129              });
 130   EXPECT_EQ(330, gen | sum);
 131 }
 132
 133 TEST(Gen, Filter) {
 134   const auto expected = vector<int>{1, 2, 4, 5, 7, 8};
 135   auto actual =
 136       seq(1, 9)
 137     | filter([](int x) { return x % 3; })
 138     | as<vector<int>>();
 139   EXPECT_EQ(expected, actual);
 140 }
 141
 142 TEST(Gen, Take) {
 143   auto expected = vector<int>{1, 4, 9, 16};
 144   auto actual =
 145       seq(1, 1000)
 146     | mapped([](int x) { return x * x; })
 147     | take(4)
 148     | as<vector<int>>();
 149   EXPECT_EQ(expected, actual);
 150 }
 151
 152 TEST(Gen, Skip) {
 153   auto gen =
 154       seq(1, 1000)
 155     | mapped([](int x) { return x * x; })
 156     | skip(4)
 157     | take(4);
 158   EXPECT_EQ((vector<int>{25, 36, 49, 64}), gen | as<vector>());
 159 }
 160
 161 TEST(Gen, Until) {
 162   auto gen =
 163       seq(1) //infinite
 164     | mapped([](int x) { return x * x; })
 165     | until([](int x) { return x >= 1000; });
 166   EXPECT_EQ(31, gen | count);
 167 }
 168
 169 TEST(Gen, Composed) {
 170   // Operator, Operator
 171   auto valuesOf =
 172       filter([](Optional<int>& o) { return o.hasValue(); })
 173     | map([](Optional<int>& o) -> int& { return o.value(); });
 174   std::vector<Optional<int>> opts {
 175     none, 4, none, 6, none
 176   };
 177   EXPECT_EQ(4 * 4 + 6 * 6, from(opts) | valuesOf | map(square) | sum);
 178   // Operator, Sink
 179   auto sumOpt = valuesOf | sum;
 180   EXPECT_EQ(10, from(opts) | sumOpt);
 181 }
 182
 183 TEST(Gen, Chain) {
 184   std::vector<int> nums {2, 3, 5, 7};
 185   std::map<int, int> mappings { { 3, 9}, {5, 25} };
 186   auto gen = from(nums) + (from(mappings) | get<1>());
 187   EXPECT_EQ(51, gen | sum);
 188   EXPECT_EQ(5, gen | take(2) | sum);
 189   EXPECT_EQ(26, gen | take(5) | sum);
 190 }
 191
 192 TEST(Gen, Concat) {
 193   std::vector<std::vector<int>> nums {{2, 3}, {5, 7}};
 194   auto gen = from(nums) | rconcat;
 195   EXPECT_EQ(17, gen | sum);
 196   EXPECT_EQ(10, gen | take(3) | sum);
 197 }
 198
 199 TEST(Gen, ConcatGen) {
 200   auto gen = seq(1, 10)
 201            | map([](int i) { return seq(1, i); })
 202            | concat;
 203   EXPECT_EQ(220, gen | sum);
 204   EXPECT_EQ(10, gen | take(6) | sum);
 205 }
 206
 207 TEST(Gen, ConcatAlt) {
 208   std::vector<std::vector<int>> nums {{2, 3}, {5, 7}};
 209   auto actual = from(nums)
 210               | map([](std::vector<int>& v) { return from(v); })
 211               | concat
 212               | sum;
 213   auto expected = 17;
 214   EXPECT_EQ(expected, actual);
 215 }
 216
 217 TEST(Gen, Order) {
 218   auto expected = vector<int>{0, 3, 5, 6, 7, 8, 9};
 219   auto actual =
 220       from({8, 6, 7, 5, 3, 0, 9})
 221     | order
 222     | as<vector>();
 223   EXPECT_EQ(expected, actual);
 224 }
 225
 226 TEST(Gen, OrderMoved) {
 227   auto expected = vector<int>{0, 9, 25, 36, 49, 64, 81};
 228   auto actual =
 229       from({8, 6, 7, 5, 3, 0, 9})
 230     | move
 231     | order
 232     | map(square)
 233     | as<vector>();
 234   EXPECT_EQ(expected, actual);
 235 }
 236
 237 TEST(Gen, OrderTake) {
 238   auto expected = vector<int>{9, 8, 7};
 239   auto actual =
 240       from({8, 6, 7, 5, 3, 0, 9})
 241     | orderByDescending(square)
 242     | take(3)
 243     | as<vector>();
 244   EXPECT_EQ(expected, actual);
 245 }
 246
 247 TEST(Gen, MinBy) {
 248   EXPECT_EQ(7, seq(1, 10)
 249              | minBy([](int i) {
 250                  auto d = i - 6.8;
 251                  return d * d;
 252                }));
 253 }
 254
 255 TEST(Gen, MaxBy) {
 256   auto gen = from({"three", "eleven", "four"});
 257
 258   EXPECT_EQ("eleven", gen | maxBy(&strlen));
 259 }
 260
 261 TEST(Gen, Append) {
 262   fbstring expected = "facebook";
 263   fbstring actual = "face";
 264   from(StringPiece("book")) | appendTo(actual);
 265   EXPECT_EQ(expected, actual);
 266 }
 267
 268 TEST(Gen, FromRValue) {
 269   {
 270     // AFAICT The C++ Standard does not specify what happens to the rvalue
 271     // reference of a std::vector when it is used as the 'other' for an rvalue
 272     // constructor.  Use fbvector because we're sure its size will be zero in
 273     // this case.
 274     folly::fbvector<int> v({1,2,3,4});
 275     auto q1 = from(v);
 276     EXPECT_EQ(v.size(), 4);  // ensure that the lvalue version was called!
 277     auto expected = 1 * 2 * 3 * 4;
 278     EXPECT_EQ(expected, q1 | product);
 279
 280     auto q2 = from(std::move(v));
 281     EXPECT_EQ(v.size(), 0);  // ensure that rvalue version was called
 282     EXPECT_EQ(expected, q2 | product);
 283   }
 284   {
 285     auto expected = 7;
 286     auto q = from([] {return vector<int>({3,7,5}); }());
 287     EXPECT_EQ(expected, q | max);
 288   }
 289   {
 290     for (auto size: {5, 1024, 16384, 1<<20}) {
 291       auto q1 = from(vector<int>(size, 2));
 292       auto q2 = from(vector<int>(size, 3));
 293       // If the rvalue specialization is broken/gone, then the compiler will
 294       // (disgustingly!) just store a *reference* to the temporary object,
 295       // which is bad.  Try to catch this by allocating two temporary vectors
 296       // of the same size, so that they'll probably use the same underlying
 297       // buffer if q1's vector is destructed before q2's vector is constructed.
 298       EXPECT_EQ(size * 2 + size * 3, (q1 | sum) + (q2 | sum));
 299     }
 300   }
 301   {
 302     auto q = from(set<int>{1,2,3,2,1});
 303     EXPECT_EQ(q | sum, 6);
 304   }
 305 }
 306
 307 TEST(Gen, OrderBy) {
 308   auto expected = vector<int>{5, 6, 4, 7, 3, 8, 2, 9, 1, 10};
 309   auto actual =
 310       seq(1, 10)
 311     | orderBy([](int x) { return (5.1 - x) * (5.1 - x); })
 312     | as<vector>();
 313   EXPECT_EQ(expected, actual);
 314 }
 315
 316 TEST(Gen, Foldl) {
 317   int expected = 2 * 3 * 4 * 5;
 318   auto actual =
 319       seq(2, 5)
 320     | foldl(1, multiply);
 321   EXPECT_EQ(expected, actual);
 322 }
 323
 324 TEST(Gen, Reduce) {
 325   int expected = 2 + 3 + 4 + 5;
 326   auto actual = seq(2, 5) | reduce(add);
 327   EXPECT_EQ(expected, actual);
 328 }
 329
 330 TEST(Gen, ReduceBad) {
 331   auto gen = seq(1) | take(0);
 332   try {
 333     EXPECT_TRUE(true);
 334     gen | reduce(add);
 335     EXPECT_TRUE(false);
 336   } catch (...) {
 337   }
 338 }
 339
 340 TEST(Gen, Moves) {
 341   std::vector<unique_ptr<int>> ptrs;
 342   ptrs.emplace_back(new int(1));
 343   EXPECT_NE(ptrs.front().get(), nullptr);
 344   auto ptrs2 = from(ptrs) | move | as<vector>();
 345   EXPECT_EQ(ptrs.front().get(), nullptr);
 346   EXPECT_EQ(**ptrs2.data(), 1);
 347 }
 348
 349 TEST(Gen, First) {
 350   auto gen =
 351       seq(0)
 352     | filter([](int x) { return x > 3; });
 353   EXPECT_EQ(4, gen | first);
 354 }
 355
 356 TEST(Gen, FromCopy) {
 357   vector<int> v {3, 5};
 358   auto src = from(v);
 359   auto copy = fromCopy(v);
 360   EXPECT_EQ(8, src | sum);
 361   EXPECT_EQ(8, copy | sum);
 362   v[1] = 7;
 363   EXPECT_EQ(10, src | sum);
 364   EXPECT_EQ(8, copy | sum);
 365 }
 366
 367 TEST(Gen, Get) {
 368   std::map<int, int> pairs {
 369     {1, 1},
 370     {2, 4},
 371     {3, 9},
 372     {4, 16},
 373   };
 374   auto pairSrc = from(pairs);
 375   auto keys = pairSrc | get<0>();
 376   auto values = pairSrc | get<1>();
 377   EXPECT_EQ(10, keys | sum);
 378   EXPECT_EQ(30, values | sum);
 379   EXPECT_EQ(30, keys | map(square) | sum);
 380   pairs[5] = 25;
 381   EXPECT_EQ(15, keys | sum);
 382   EXPECT_EQ(55, values | sum);
 383
 384   vector<tuple<int, int, int>> tuples {
 385     make_tuple(1, 1, 1),
 386     make_tuple(2, 4, 8),
 387     make_tuple(3, 9, 27),
 388   };
 389   EXPECT_EQ(36, from(tuples) | get<2>() | sum);
 390 }
 391
 392 TEST(Gen, Any) {
 393   EXPECT_TRUE(seq(0) | any);
 394   EXPECT_TRUE(seq(0, 1) | any);
 395   EXPECT_TRUE(from({1}) | any);
 396   EXPECT_FALSE(range(0, 0) | any);
 397   EXPECT_FALSE(from({1}) | take(0) | any);
 398 }
 399
 400 TEST(Gen, Yielders) {
 401   auto gen = GENERATOR(int, {
 402     for (int i = 1; i <= 5; ++i) {
 403       yield(i);
 404     }
 405     yield(7);
 406     for (int i = 3; ; ++i) {
 407       yield(i * i);
 408     }
 409   });
 410   vector<int> expected {
 411     1, 2, 3, 4, 5, 7, 9, 16, 25
 412   };
 413   EXPECT_EQ(expected, gen | take(9) | as<vector>());
 414 }
 415
 416 TEST(Gen, NestedYield) {
 417   auto nums = GENERATOR(int, {
 418     for (int i = 1; ; ++i) {
 419       yield(i);
 420     }
 421   });
 422   auto gen = GENERATOR(int, {
 423     nums | take(10) | yield;
 424     seq(1, 5) | [&](int i) {
 425       yield(i);
 426     };
 427   });
 428   EXPECT_EQ(70, gen | sum);
 429 }
 430
 431 TEST(Gen, MapYielders) {
 432   auto gen = seq(1, 5)
 433            | map([](int n) {
 434                return GENERATOR(int, {
 435                  int i;
 436                  for (i = 1; i < n; ++i)
 437                    yield(i);
 438                  for (; i >= 1; --i)
 439                    yield(i);
 440                });
 441              })
 442            | concat;
 443   vector<int> expected {
 444                 1,
 445              1, 2, 1,
 446           1, 2, 3, 2, 1,
 447        1, 2, 3, 4, 3, 2, 1,
 448     1, 2, 3, 4, 5, 4, 3, 2, 1,
 449   };
 450   EXPECT_EQ(expected, gen | as<vector>());
 451 }
 452
 453 TEST(Gen, VirtualGen) {
 454   VirtualGen<int> v(seq(1, 10));
 455   EXPECT_EQ(55, v | sum);
 456   v = v | map(square);
 457   EXPECT_EQ(385, v | sum);
 458   v = v | take(5);
 459   EXPECT_EQ(55, v | sum);
 460   EXPECT_EQ(30, v | take(4) | sum);
 461 }
 462
 463
 464 TEST(Gen, CustomType) {
 465   struct Foo{
 466     int y;
 467   };
 468   auto gen = from({Foo{2}, Foo{3}})
 469            | map([](const Foo& f) { return f.y; });
 470   EXPECT_EQ(5, gen | sum);
 471 }
 472
 473 TEST(Gen, NoNeedlessCopies) {
 474   auto gen = seq(1, 5)
 475            | map([](int x) { return unique_ptr<int>(new int(x)); })
 476            | map([](unique_ptr<int> p) { return p; })
 477            | map([](unique_ptr<int>&& p) { return std::move(p); })
 478            | map([](const unique_ptr<int>& p) { return *p; });
 479   EXPECT_EQ(15, gen | sum);
 480   EXPECT_EQ(6, gen | take(3) | sum);
 481 }
 482
 483 TEST(Gen, FromArray) {
 484   int source[] = {2, 3, 5, 7};
 485   auto gen = from(source);
 486   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 487 }
 488
 489 TEST(Gen, FromStdArray) {
 490   std::array<int,4> source {{2, 3, 5, 7}};
 491   auto gen = from(source);
 492   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 493 }
 494
 495 TEST(Gen, StringConcat) {
 496   auto gen = seq(1, 10)
 497            | map([](int n) { return folly::to<fbstring>(n); })
 498            | rconcat;
 499   EXPECT_EQ("12345678910", gen | as<fbstring>());
 500 }
 501
 502 struct CopyCounter {
 503   static int alive;
 504   int copies;
 505   int moves;
 506
 507   CopyCounter() : copies(0), moves(0) {
 508     ++alive;
 509   }
 510
 511   CopyCounter(CopyCounter&& source) {
 512     *this = std::move(source);
 513     ++alive;
 514   }
 515
 516   CopyCounter(const CopyCounter& source) {
 517     *this = source;
 518     ++alive;
 519   }
 520
 521   ~CopyCounter() {
 522     --alive;
 523   }
 524
 525   CopyCounter& operator=(const CopyCounter& source) {
 526     this->copies = source.copies + 1;
 527     this->moves = source.moves;
 528     return *this;
 529   }
 530
 531   CopyCounter& operator=(CopyCounter&& source) {
 532     this->copies = source.copies;
 533     this->moves = source.moves + 1;
 534     return *this;
 535   }
 536 };
 537
 538 int CopyCounter::alive = 0;
 539
 540 TEST(Gen, CopyCount) {
 541   vector<CopyCounter> originals;
 542   originals.emplace_back();
 543   EXPECT_EQ(1, originals.size());
 544   EXPECT_EQ(0, originals.back().copies);
 545
 546   vector<CopyCounter> copies = from(originals) | as<vector>();
 547   EXPECT_EQ(1, copies.back().copies);
 548   EXPECT_EQ(0, copies.back().moves);
 549
 550   vector<CopyCounter> moves = from(originals) | move | as<vector>();
 551   EXPECT_EQ(0, moves.back().copies);
 552   EXPECT_EQ(1, moves.back().moves);
 553 }
 554
 555 // test dynamics with various layers of nested arrays.
 556 TEST(Gen, Dynamic) {
 557   dynamic array1 = {1, 2};
 558   EXPECT_EQ(dynamic(3), from(array1) | sum);
 559   dynamic array2 = {{1}, {1, 2}};
 560   EXPECT_EQ(dynamic(4), from(array2) | rconcat | sum);
 561   dynamic array3 = {{{1}}, {{1}, {1, 2}}};
 562   EXPECT_EQ(dynamic(5), from(array3) | rconcat | rconcat | sum);
 563 }
 564
 565 int main(int argc, char *argv[]) {
 566   testing::InitGoogleTest(&argc, argv);
 567   google::ParseCommandLineFlags(&argc, &argv, true);
 568   return RUN_ALL_TESTS();
 569 }