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
 170 TEST(Gen, Chain) {
 171   std::vector<int> nums {2, 3, 5, 7};
 172   std::map<int, int> mappings { { 3, 9}, {5, 25} };
 173   auto gen = from(nums) + (from(mappings) | get<1>());
 174   EXPECT_EQ(51, gen | sum);
 175   EXPECT_EQ(5, gen | take(2) | sum);
 176   EXPECT_EQ(26, gen | take(5) | sum);
 177 }
 178
 179 TEST(Gen, Concat) {
 180   std::vector<std::vector<int>> nums {{2, 3}, {5, 7}};
 181   auto gen = from(nums) | rconcat;
 182   EXPECT_EQ(17, gen | sum);
 183   EXPECT_EQ(10, gen | take(3) | sum);
 184 }
 185
 186 TEST(Gen, ConcatGen) {
 187   auto gen = seq(1, 10)
 188            | map([](int i) { return seq(1, i); })
 189            | concat;
 190   EXPECT_EQ(220, gen | sum);
 191   EXPECT_EQ(10, gen | take(6) | sum);
 192 }
 193
 194 TEST(Gen, ConcatAlt) {
 195   std::vector<std::vector<int>> nums {{2, 3}, {5, 7}};
 196   auto actual = from(nums)
 197               | map([](std::vector<int>& v) { return from(v); })
 198               | concat
 199               | sum;
 200   auto expected = 17;
 201   EXPECT_EQ(expected, actual);
 202 }
 203
 204 TEST(Gen, Order) {
 205   auto expected = vector<int>{0, 3, 5, 6, 7, 8, 9};
 206   auto actual =
 207       from({8, 6, 7, 5, 3, 0, 9})
 208     | order
 209     | as<vector>();
 210   EXPECT_EQ(expected, actual);
 211 }
 212
 213 TEST(Gen, OrderMoved) {
 214   auto expected = vector<int>{0, 9, 25, 36, 49, 64, 81};
 215   auto actual =
 216       from({8, 6, 7, 5, 3, 0, 9})
 217     | move
 218     | order
 219     | map(square)
 220     | as<vector>();
 221   EXPECT_EQ(expected, actual);
 222 }
 223
 224 TEST(Gen, OrderTake) {
 225   auto expected = vector<int>{9, 8, 7};
 226   auto actual =
 227       from({8, 6, 7, 5, 3, 0, 9})
 228     | orderByDescending(square)
 229     | take(3)
 230     | as<vector>();
 231   EXPECT_EQ(expected, actual);
 232 }
 233
 234 TEST(Gen, MinBy) {
 235   EXPECT_EQ(7, seq(1, 10)
 236              | minBy([](int i) {
 237                  auto d = i - 6.8;
 238                  return d * d;
 239                }));
 240 }
 241
 242 TEST(Gen, MaxBy) {
 243   auto gen = from({"three", "eleven", "four"});
 244
 245   EXPECT_EQ("eleven", gen | maxBy(&strlen));
 246 }
 247
 248 TEST(Gen, Append) {
 249   fbstring expected = "facebook";
 250   fbstring actual = "face";
 251   from(StringPiece("book")) | appendTo(actual);
 252   EXPECT_EQ(expected, actual);
 253 }
 254
 255 TEST(Gen, FromRValue) {
 256   {
 257     // AFAICT The C++ Standard does not specify what happens to the rvalue
 258     // reference of a std::vector when it is used as the 'other' for an rvalue
 259     // constructor.  Use fbvector because we're sure its size will be zero in
 260     // this case.
 261     folly::fbvector<int> v({1,2,3,4});
 262     auto q1 = from(v);
 263     EXPECT_EQ(v.size(), 4);  // ensure that the lvalue version was called!
 264     auto expected = 1 * 2 * 3 * 4;
 265     EXPECT_EQ(expected, q1 | product);
 266
 267     auto q2 = from(std::move(v));
 268     EXPECT_EQ(v.size(), 0);  // ensure that rvalue version was called
 269     EXPECT_EQ(expected, q2 | product);
 270   }
 271   {
 272     auto expected = 7;
 273     auto q = from([] {return vector<int>({3,7,5}); }());
 274     EXPECT_EQ(expected, q | max);
 275   }
 276   {
 277     for (auto size: {5, 1024, 16384, 1<<20}) {
 278       auto q1 = from(vector<int>(size, 2));
 279       auto q2 = from(vector<int>(size, 3));
 280       // If the rvalue specialization is broken/gone, then the compiler will
 281       // (disgustingly!) just store a *reference* to the temporary object,
 282       // which is bad.  Try to catch this by allocating two temporary vectors
 283       // of the same size, so that they'll probably use the same underlying
 284       // buffer if q1's vector is destructed before q2's vector is constructed.
 285       EXPECT_EQ(size * 2 + size * 3, (q1 | sum) + (q2 | sum));
 286     }
 287   }
 288   {
 289     auto q = from(set<int>{1,2,3,2,1});
 290     EXPECT_EQ(q | sum, 6);
 291   }
 292 }
 293
 294 TEST(Gen, OrderBy) {
 295   auto expected = vector<int>{5, 6, 4, 7, 3, 8, 2, 9, 1, 10};
 296   auto actual =
 297       seq(1, 10)
 298     | orderBy([](int x) { return (5.1 - x) * (5.1 - x); })
 299     | as<vector>();
 300   EXPECT_EQ(expected, actual);
 301 }
 302
 303 TEST(Gen, Foldl) {
 304   int expected = 2 * 3 * 4 * 5;
 305   auto actual =
 306       seq(2, 5)
 307     | foldl(1, multiply);
 308   EXPECT_EQ(expected, actual);
 309 }
 310
 311 TEST(Gen, Reduce) {
 312   int expected = 2 + 3 + 4 + 5;
 313   auto actual = seq(2, 5) | reduce(add);
 314   EXPECT_EQ(expected, actual);
 315 }
 316
 317 TEST(Gen, ReduceBad) {
 318   auto gen = seq(1) | take(0);
 319   try {
 320     EXPECT_TRUE(true);
 321     gen | reduce(add);
 322     EXPECT_TRUE(false);
 323   } catch (...) {
 324   }
 325 }
 326
 327 TEST(Gen, Moves) {
 328   std::vector<unique_ptr<int>> ptrs;
 329   ptrs.emplace_back(new int(1));
 330   EXPECT_NE(ptrs.front().get(), nullptr);
 331   auto ptrs2 = from(ptrs) | move | as<vector>();
 332   EXPECT_EQ(ptrs.front().get(), nullptr);
 333   EXPECT_EQ(**ptrs2.data(), 1);
 334 }
 335
 336 TEST(Gen, First) {
 337   auto gen =
 338       seq(0)
 339     | filter([](int x) { return x > 3; });
 340   EXPECT_EQ(4, gen | first);
 341 }
 342
 343 TEST(Gen, FromCopy) {
 344   vector<int> v {3, 5};
 345   auto src = from(v);
 346   auto copy = fromCopy(v);
 347   EXPECT_EQ(8, src | sum);
 348   EXPECT_EQ(8, copy | sum);
 349   v[1] = 7;
 350   EXPECT_EQ(10, src | sum);
 351   EXPECT_EQ(8, copy | sum);
 352 }
 353
 354 TEST(Gen, Get) {
 355   std::map<int, int> pairs {
 356     {1, 1},
 357     {2, 4},
 358     {3, 9},
 359     {4, 16},
 360   };
 361   auto pairSrc = from(pairs);
 362   auto keys = pairSrc | get<0>();
 363   auto values = pairSrc | get<1>();
 364   EXPECT_EQ(10, keys | sum);
 365   EXPECT_EQ(30, values | sum);
 366   EXPECT_EQ(30, keys | map(square) | sum);
 367   pairs[5] = 25;
 368   EXPECT_EQ(15, keys | sum);
 369   EXPECT_EQ(55, values | sum);
 370
 371   vector<tuple<int, int, int>> tuples {
 372     make_tuple(1, 1, 1),
 373     make_tuple(2, 4, 8),
 374     make_tuple(3, 9, 27),
 375   };
 376   EXPECT_EQ(36, from(tuples) | get<2>() | sum);
 377 }
 378
 379 TEST(Gen, Any) {
 380   EXPECT_TRUE(seq(0) | any);
 381   EXPECT_TRUE(seq(0, 1) | any);
 382   EXPECT_TRUE(from({1}) | any);
 383   EXPECT_FALSE(range(0, 0) | any);
 384   EXPECT_FALSE(from({1}) | take(0) | any);
 385 }
 386
 387 TEST(Gen, Yielders) {
 388   auto gen = GENERATOR(int, {
 389     for (int i = 1; i <= 5; ++i) {
 390       yield(i);
 391     }
 392     yield(7);
 393     for (int i = 3; ; ++i) {
 394       yield(i * i);
 395     }
 396   });
 397   vector<int> expected {
 398     1, 2, 3, 4, 5, 7, 9, 16, 25
 399   };
 400   EXPECT_EQ(expected, gen | take(9) | as<vector>());
 401 }
 402
 403 TEST(Gen, NestedYield) {
 404   auto nums = GENERATOR(int, {
 405     for (int i = 1; ; ++i) {
 406       yield(i);
 407     }
 408   });
 409   auto gen = GENERATOR(int, {
 410     nums | take(10) | yield;
 411     seq(1, 5) | [&](int i) {
 412       yield(i);
 413     };
 414   });
 415   EXPECT_EQ(70, gen | sum);
 416 }
 417
 418 TEST(Gen, MapYielders) {
 419   auto gen = seq(1, 5)
 420            | map([](int n) {
 421                return GENERATOR(int, {
 422                  int i;
 423                  for (i = 1; i < n; ++i)
 424                    yield(i);
 425                  for (; i >= 1; --i)
 426                    yield(i);
 427                });
 428              })
 429            | concat;
 430   vector<int> expected {
 431                 1,
 432              1, 2, 1,
 433           1, 2, 3, 2, 1,
 434        1, 2, 3, 4, 3, 2, 1,
 435     1, 2, 3, 4, 5, 4, 3, 2, 1,
 436   };
 437   EXPECT_EQ(expected, gen | as<vector>());
 438 }
 439
 440 TEST(Gen, VirtualGen) {
 441   VirtualGen<int> v(seq(1, 10));
 442   EXPECT_EQ(55, v | sum);
 443   v = v | map(square);
 444   EXPECT_EQ(385, v | sum);
 445   v = v | take(5);
 446   EXPECT_EQ(55, v | sum);
 447   EXPECT_EQ(30, v | take(4) | sum);
 448 }
 449
 450
 451 TEST(Gen, CustomType) {
 452   struct Foo{
 453     int y;
 454   };
 455   auto gen = from({Foo{2}, Foo{3}})
 456            | map([](const Foo& f) { return f.y; });
 457   EXPECT_EQ(5, gen | sum);
 458 }
 459
 460 TEST(Gen, NoNeedlessCopies) {
 461   auto gen = seq(1, 5)
 462            | map([](int x) { return unique_ptr<int>(new int(x)); })
 463            | map([](unique_ptr<int> p) { return p; })
 464            | map([](unique_ptr<int>&& p) { return std::move(p); })
 465            | map([](const unique_ptr<int>& p) { return *p; });
 466   EXPECT_EQ(15, gen | sum);
 467   EXPECT_EQ(6, gen | take(3) | sum);
 468 }
 469
 470 TEST(Gen, FromArray) {
 471   int source[] = {2, 3, 5, 7};
 472   auto gen = from(source);
 473   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 474 }
 475
 476 TEST(Gen, FromStdArray) {
 477   std::array<int,4> source {{2, 3, 5, 7}};
 478   auto gen = from(source);
 479   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 480 }
 481
 482 TEST(Gen, StringConcat) {
 483   auto gen = seq(1, 10)
 484            | map([](int n) { return folly::to<fbstring>(n); })
 485            | rconcat;
 486   EXPECT_EQ("12345678910", gen | as<fbstring>());
 487 }
 488
 489 struct CopyCounter {
 490   static int alive;
 491   int copies;
 492   int moves;
 493
 494   CopyCounter() : copies(0), moves(0) {
 495     ++alive;
 496   }
 497
 498   CopyCounter(CopyCounter&& source) {
 499     *this = std::move(source);
 500     ++alive;
 501   }
 502
 503   CopyCounter(const CopyCounter& source) {
 504     *this = source;
 505     ++alive;
 506   }
 507
 508   ~CopyCounter() {
 509     --alive;
 510   }
 511
 512   CopyCounter& operator=(const CopyCounter& source) {
 513     this->copies = source.copies + 1;
 514     this->moves = source.moves;
 515     return *this;
 516   }
 517
 518   CopyCounter& operator=(CopyCounter&& source) {
 519     this->copies = source.copies;
 520     this->moves = source.moves + 1;
 521     return *this;
 522   }
 523 };
 524
 525 int CopyCounter::alive = 0;
 526
 527 TEST(Gen, CopyCount) {
 528   vector<CopyCounter> originals;
 529   originals.emplace_back();
 530   EXPECT_EQ(1, originals.size());
 531   EXPECT_EQ(0, originals.back().copies);
 532
 533   vector<CopyCounter> copies = from(originals) | as<vector>();
 534   EXPECT_EQ(1, copies.back().copies);
 535   EXPECT_EQ(0, copies.back().moves);
 536
 537   vector<CopyCounter> moves = from(originals) | move | as<vector>();
 538   EXPECT_EQ(0, moves.back().copies);
 539   EXPECT_EQ(1, moves.back().moves);
 540 }
 541
 542 // test dynamics with various layers of nested arrays.
 543 TEST(Gen, Dynamic) {
 544   dynamic array1 = {1, 2};
 545   EXPECT_EQ(dynamic(3), from(array1) | sum);
 546   dynamic array2 = {{1}, {1, 2}};
 547   EXPECT_EQ(dynamic(4), from(array2) | rconcat | sum);
 548   dynamic array3 = {{{1}}, {{1}, {1, 2}}};
 549   EXPECT_EQ(dynamic(5), from(array3) | rconcat | rconcat | sum);
 550 }
 551
 552 int main(int argc, char *argv[]) {
 553   testing::InitGoogleTest(&argc, argv);
 554   google::ParseCommandLineFlags(&argc, &argv, true);
 555   return RUN_ALL_TESTS();
 556 }