folly/experimental/test/GenTest.cpp

   1 /*
   2  * Copyright 2013 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 <random>
  21 #include <set>
  22 #include <vector>
  23 #include "folly/experimental/Gen.h"
  24 #include "folly/experimental/StringGen.h"
  25 #include "folly/experimental/CombineGen.h"
  26 #include "folly/experimental/FileGen.h"
  27 #include "folly/experimental/TestUtil.h"
  28 #include "folly/FBString.h"
  29 #include "folly/FBVector.h"
  30 #include "folly/Format.h"
  31 #include "folly/dynamic.h"
  32
  33 using namespace folly::gen;
  34 using namespace folly;
  35 using std::ostream;
  36 using std::pair;
  37 using std::set;
  38 using std::unique_ptr;
  39 using std::vector;
  40 using std::string;
  41 using std::tuple;
  42 using std::make_tuple;
  43
  44 #define EXPECT_SAME(A, B) \
  45   static_assert(std::is_same<A, B>::value, "Mismatched: " #A ", " #B)
  46 EXPECT_SAME(int&&, typename ArgumentReference<int>::type);
  47 EXPECT_SAME(int&, typename ArgumentReference<int&>::type);
  48 EXPECT_SAME(const int&, typename ArgumentReference<const int&>::type);
  49 EXPECT_SAME(const int&, typename ArgumentReference<const int>::type);
  50
  51 template<typename T>
  52 ostream& operator<<(ostream& os, const set<T>& values) {
  53   return os << from(values);
  54 }
  55
  56 template<typename T>
  57 ostream& operator<<(ostream& os, const vector<T>& values) {
  58   os << "[";
  59   for (auto& value : values) {
  60     if (&value != &values.front()) {
  61       os << " ";
  62     }
  63     os << value;
  64   }
  65   return os << "]";
  66 }
  67
  68 auto square = [](int x) { return x * x; };
  69 auto add = [](int a, int b) { return a + b; };
  70 auto multiply = [](int a, int b) { return a * b; };
  71
  72 auto product = foldl(1, multiply);
  73
  74 template<typename A, typename B>
  75 ostream& operator<<(ostream& os, const pair<A, B>& pair) {
  76   return os << "(" << pair.first << ", " << pair.second << ")";
  77 }
  78
  79 TEST(Gen, Count) {
  80   auto gen = seq(1, 10);
  81   EXPECT_EQ(10, gen | count);
  82   EXPECT_EQ(5, gen | take(5) | count);
  83 }
  84
  85 TEST(Gen, Sum) {
  86   auto gen = seq(1, 10);
  87   EXPECT_EQ((1 + 10) * 10 / 2, gen | sum);
  88   EXPECT_EQ((1 + 5) * 5 / 2, gen | take(5) | sum);
  89 }
  90
  91 TEST(Gen, Foreach) {
  92   auto gen = seq(1, 4);
  93   int accum = 0;
  94   gen | [&](int x) { accum += x; };
  95   EXPECT_EQ(10, accum);
  96   int accum2 = 0;
  97   gen | take(3) | [&](int x) { accum2 += x; };
  98   EXPECT_EQ(6, accum2);
  99 }
 100
 101 TEST(Gen, Map) {
 102   auto expected = vector<int>{4, 9, 16};
 103   auto gen = from({2, 3, 4}) | map(square);
 104   EXPECT_EQ((vector<int>{4, 9, 16}), gen | as<vector>());
 105   EXPECT_EQ((vector<int>{4, 9}), gen | take(2) | as<vector>());
 106 }
 107
 108 TEST(Gen, Member) {
 109   struct Counter {
 110     Counter(int start = 0)
 111       : c(start)
 112     {}
 113
 114     int count() const { return c; }
 115     int incr() { return ++c; }
 116
 117     int& ref() { return c; }
 118     const int& ref() const { return c; }
 119    private:
 120     int c;
 121   };
 122   auto counters = seq(1, 10) | eachAs<Counter>() | as<vector>();
 123   EXPECT_EQ(10 * (1 + 10) / 2,
 124             from(counters)
 125           | member(&Counter::count)
 126           | sum);
 127   EXPECT_EQ(10 * (2 + 11) / 2,
 128             from(counters)
 129           | member(&Counter::incr)
 130           | sum);
 131   EXPECT_EQ(10 * (2 + 11) / 2,
 132             from(counters)
 133           | member(&Counter::count)
 134           | sum);
 135
 136   // type-verifications
 137   auto m = empty<Counter&>();
 138   auto c = empty<const Counter&>();
 139   m | member(&Counter::incr) | assert_type<int&&>();
 140   m | member(&Counter::count) | assert_type<int&&>();
 141   m | member(&Counter::count) | assert_type<int&&>();
 142   m | member<Const>(&Counter::ref) | assert_type<const int&>();
 143   m | member<Mutable>(&Counter::ref) | assert_type<int&>();
 144   c | member<Const>(&Counter::ref) | assert_type<const int&>();
 145 }
 146
 147 TEST(Gen, Field) {
 148   struct X {
 149     X() : a(2), b(3), c(4), d(b) {}
 150
 151     const int a;
 152     int b;
 153     mutable int c;
 154     int& d; // can't access this with a field pointer.
 155   };
 156
 157   std::vector<X> xs(1);
 158   EXPECT_EQ(2, from(xs)
 159              | field(&X::a)
 160              | first);
 161   EXPECT_EQ(3, from(xs)
 162              | field(&X::b)
 163              | first);
 164   EXPECT_EQ(4, from(xs)
 165              | field(&X::c)
 166              | first);
 167   // type-verification
 168   empty<X&>() | field(&X::a) | assert_type<const int&>();
 169   empty<X&>() | field(&X::b) | assert_type<int&>();
 170   empty<X&>() | field(&X::c) | assert_type<int&>();
 171   empty<X&&>() | field(&X::a) | assert_type<const int&&>();
 172   empty<X&&>() | field(&X::b) | assert_type<int&&>();
 173   empty<X&&>() | field(&X::c) | assert_type<int&&>();
 174   // references don't imply ownership so they're not moved
 175   empty<const X&>() | field(&X::a) | assert_type<const int&>();
 176   empty<const X&>() | field(&X::b) | assert_type<const int&>();
 177   // 'mutable' has no effect on field pointers, by C++ spec
 178   empty<const X&>() | field(&X::c) | assert_type<const int&>();
 179
 180   // can't form pointer-to-reference field: empty<X&>() | field(&X::d)
 181 }
 182
 183 TEST(Gen, Seq) {
 184   // cover the fenceposts of the loop unrolling
 185   for (int n = 1; n < 100; ++n) {
 186     EXPECT_EQ(n, seq(1, n) | count);
 187     EXPECT_EQ(n + 1, seq(1) | take(n + 1) | count);
 188   }
 189 }
 190
 191 TEST(Gen, Range) {
 192   // cover the fenceposts of the loop unrolling
 193   for (int n = 1; n < 100; ++n) {
 194     EXPECT_EQ(range(0, n) | count, n);
 195   }
 196 }
 197
 198 TEST(Gen, FromIterators) {
 199   vector<int> source {2, 3, 5, 7, 11};
 200   auto gen = from(makeRange(source.begin() + 1, source.end() - 1));
 201   EXPECT_EQ(3 * 5 * 7, gen | product);
 202 }
 203
 204 TEST(Gen, FromMap) {
 205   auto source = seq(0, 10)
 206               | map([](int i) { return std::make_pair(i, i * i); })
 207               | as<std::map<int, int>>();
 208   auto gen = fromConst(source)
 209            | map([&](const std::pair<const int, int>& p) {
 210                return p.second - p.first;
 211              });
 212   EXPECT_EQ(330, gen | sum);
 213 }
 214
 215 TEST(Gen, Filter) {
 216   const auto expected = vector<int>{1, 2, 4, 5, 7, 8};
 217   auto actual =
 218       seq(1, 9)
 219     | filter([](int x) { return x % 3; })
 220     | as<vector<int>>();
 221   EXPECT_EQ(expected, actual);
 222 }
 223
 224 TEST(Gen, Contains) {
 225   {
 226     auto gen =
 227         seq(1, 9)
 228       | map(square);
 229     EXPECT_TRUE(gen | contains(49));
 230     EXPECT_FALSE(gen | contains(50));
 231   }
 232   {
 233     auto gen =
 234         seq(1) // infinite, to prove laziness
 235       | map(square)
 236       | eachTo<std::string>();
 237
 238     // std::string gen, const char* needle
 239     EXPECT_TRUE(gen | take(9999) | contains("49"));
 240   }
 241 }
 242
 243 TEST(Gen, Take) {
 244   auto expected = vector<int>{1, 4, 9, 16};
 245   auto actual =
 246       seq(1, 1000)
 247     | mapped([](int x) { return x * x; })
 248     | take(4)
 249     | as<vector<int>>();
 250   EXPECT_EQ(expected, actual);
 251 }
 252
 253 TEST(Gen, Sample) {
 254   std::mt19937 rnd(42);
 255
 256   auto sampler =
 257       seq(1, 100)
 258     | sample(50, rnd);
 259   std::unordered_map<int,int> hits;
 260   const int kNumIters = 80;
 261   for (int i = 0; i < kNumIters; i++) {
 262     auto vec = sampler | as<vector<int>>();
 263     EXPECT_EQ(vec.size(), 50);
 264     auto uniq = fromConst(vec) | as<set<int>>();
 265     EXPECT_EQ(uniq.size(), vec.size());  // sampling without replacement
 266     for (auto v: vec) {
 267       ++hits[v];
 268     }
 269   }
 270
 271   // In 80 separate samples of our range, we should have seen every value
 272   // at least once and no value all 80 times. (The odds of either of those
 273   // events is 1/2^80).
 274   EXPECT_EQ(hits.size(), 100);
 275   for (auto hit: hits) {
 276     EXPECT_GT(hit.second, 0);
 277     EXPECT_LT(hit.second, kNumIters);
 278   }
 279
 280   auto small =
 281       seq(1, 5)
 282     | sample(10);
 283   EXPECT_EQ((small | sum), 15);
 284   EXPECT_EQ((small | take(3) | count), 3);
 285 }
 286
 287 TEST(Gen, Skip) {
 288   auto gen =
 289       seq(1, 1000)
 290     | mapped([](int x) { return x * x; })
 291     | skip(4)
 292     | take(4);
 293   EXPECT_EQ((vector<int>{25, 36, 49, 64}), gen | as<vector>());
 294 }
 295
 296 TEST(Gen, Until) {
 297   auto gen =
 298       seq(1) //infinite
 299     | mapped([](int x) { return x * x; })
 300     | until([](int x) { return x >= 1000; });
 301   EXPECT_EQ(31, gen | count);
 302 }
 303
 304 auto even = [](int i) -> bool { return i % 2 == 0; };
 305 auto odd = [](int i) -> bool { return i % 2 == 1; };
 306
 307 TEST(CombineGen, Interleave) {
 308   { // large (infinite) base, small container
 309     auto base = seq(1) | filter(odd);
 310     auto toInterleave = seq(1, 6) | filter(even);
 311     auto interleaved = base | interleave(toInterleave | as<vector>());
 312     EXPECT_EQ(interleaved | as<vector>(), vector<int>({1, 2, 3, 4, 5, 6}));
 313   }
 314   { // small base, large container
 315     auto base = seq(1) | filter(odd) | take(3);
 316     auto toInterleave = seq(1) | filter(even) | take(50);
 317     auto interleaved = base | interleave(toInterleave | as<vector>());
 318     EXPECT_EQ(interleaved | as<vector>(),
 319               vector<int>({1, 2, 3, 4, 5, 6}));
 320   }
 321 }
 322
 323 TEST(CombineGen, Zip) {
 324   auto base0 = seq(1);
 325   // We rely on std::move(fbvector) emptying the source vector
 326   auto zippee = fbvector<string>{"one", "two", "three"};
 327   {
 328     auto combined = base0
 329       | zip(zippee)
 330       | as<vector>();
 331     ASSERT_EQ(combined.size(), 3);
 332     EXPECT_EQ(std::get<0>(combined[0]), 1);
 333     EXPECT_EQ(std::get<1>(combined[0]), "one");
 334     EXPECT_EQ(std::get<0>(combined[1]), 2);
 335     EXPECT_EQ(std::get<1>(combined[1]), "two");
 336     EXPECT_EQ(std::get<0>(combined[2]), 3);
 337     EXPECT_EQ(std::get<1>(combined[2]), "three");
 338     ASSERT_FALSE(zippee.empty());
 339     EXPECT_FALSE(zippee.front().empty());  // shouldn't have been move'd
 340   }
 341
 342   { // same as top, but using std::move.
 343     auto combined = base0
 344       | zip(std::move(zippee))
 345       | as<vector>();
 346     ASSERT_EQ(combined.size(), 3);
 347     EXPECT_EQ(std::get<0>(combined[0]), 1);
 348     EXPECT_TRUE(zippee.empty());
 349   }
 350
 351   { // same as top, but base is truncated
 352     auto baseFinite = seq(1) | take(1);
 353     auto combined = baseFinite
 354       | zip(vector<string>{"one", "two", "three"})
 355       | as<vector>();
 356     ASSERT_EQ(combined.size(), 1);
 357     EXPECT_EQ(std::get<0>(combined[0]), 1);
 358     EXPECT_EQ(std::get<1>(combined[0]), "one");
 359   }
 360 }
 361
 362 TEST(CombineGen, TupleFlatten) {
 363   vector<tuple<int,string>> intStringTupleVec{
 364     tuple<int,string>{1, "1"},
 365     tuple<int,string>{2, "2"},
 366     tuple<int,string>{3, "3"},
 367   };
 368
 369   vector<tuple<char>> charTupleVec{
 370     tuple<char>{'A'},
 371     tuple<char>{'B'},
 372     tuple<char>{'C'},
 373     tuple<char>{'D'},
 374   };
 375
 376   vector<double> doubleVec{
 377     1.0,
 378     4.0,
 379     9.0,
 380     16.0,
 381     25.0,
 382   };
 383
 384   auto zipped1 = from(intStringTupleVec)
 385     | zip(charTupleVec)
 386     | assert_type<tuple<tuple<int, string>, tuple<char>>>()
 387     | as<vector>();
 388   EXPECT_EQ(std::get<0>(zipped1[0]), std::make_tuple(1, "1"));
 389   EXPECT_EQ(std::get<1>(zipped1[0]), std::make_tuple('A'));
 390
 391   auto zipped2 = from(zipped1)
 392     | tuple_flatten
 393     | assert_type<tuple<int, string, char>&&>()
 394     | as<vector>();
 395   ASSERT_EQ(zipped2.size(), 3);
 396   EXPECT_EQ(zipped2[0], std::make_tuple(1, "1", 'A'));
 397
 398   auto zipped3 = from(charTupleVec)
 399     | zip(intStringTupleVec)
 400     | tuple_flatten
 401     | assert_type<tuple<char, int, string>&&>()
 402     | as<vector>();
 403   ASSERT_EQ(zipped3.size(), 3);
 404   EXPECT_EQ(zipped3[0], std::make_tuple('A', 1, "1"));
 405
 406   auto zipped4 = from(intStringTupleVec)
 407     | zip(doubleVec)
 408     | tuple_flatten
 409     | assert_type<tuple<int, string, double>&&>()
 410     | as<vector>();
 411   ASSERT_EQ(zipped4.size(), 3);
 412   EXPECT_EQ(zipped4[0], std::make_tuple(1, "1", 1.0));
 413
 414   auto zipped5 = from(doubleVec)
 415     | zip(doubleVec)
 416     | assert_type<tuple<double, double>>()
 417     | tuple_flatten  // essentially a no-op
 418     | assert_type<tuple<double, double>&&>()
 419     | as<vector>();
 420   ASSERT_EQ(zipped5.size(), 5);
 421   EXPECT_EQ(zipped5[0], std::make_tuple(1.0, 1.0));
 422
 423   auto zipped6 = from(intStringTupleVec)
 424     | zip(charTupleVec)
 425     | tuple_flatten
 426     | zip(doubleVec)
 427     | tuple_flatten
 428     | assert_type<tuple<int, string, char, double>&&>()
 429     | as<vector>();
 430   ASSERT_EQ(zipped6.size(), 3);
 431   EXPECT_EQ(zipped6[0], std::make_tuple(1, "1", 'A', 1.0));
 432 }
 433
 434 TEST(Gen, Composed) {
 435   // Operator, Operator
 436   auto valuesOf =
 437       filter([](Optional<int>& o) { return o.hasValue(); })
 438     | map([](Optional<int>& o) -> int& { return o.value(); });
 439   std::vector<Optional<int>> opts {
 440     none, 4, none, 6, none
 441   };
 442   EXPECT_EQ(4 * 4 + 6 * 6, from(opts) | valuesOf | map(square) | sum);
 443   // Operator, Sink
 444   auto sumOpt = valuesOf | sum;
 445   EXPECT_EQ(10, from(opts) | sumOpt);
 446 }
 447
 448 TEST(Gen, Chain) {
 449   std::vector<int> nums {2, 3, 5, 7};
 450   std::map<int, int> mappings { { 3, 9}, {5, 25} };
 451   auto gen = from(nums) + (from(mappings) | get<1>());
 452   EXPECT_EQ(51, gen | sum);
 453   EXPECT_EQ(5, gen | take(2) | sum);
 454   EXPECT_EQ(26, gen | take(5) | sum);
 455 }
 456
 457 TEST(Gen, Concat) {
 458   std::vector<std::vector<int>> nums {{2, 3}, {5, 7}};
 459   auto gen = from(nums) | rconcat;
 460   EXPECT_EQ(17, gen | sum);
 461   EXPECT_EQ(10, gen | take(3) | sum);
 462 }
 463
 464 TEST(Gen, ConcatGen) {
 465   auto gen = seq(1, 10)
 466            | map([](int i) { return seq(1, i); })
 467            | concat;
 468   EXPECT_EQ(220, gen | sum);
 469   EXPECT_EQ(10, gen | take(6) | sum);
 470 }
 471
 472 TEST(Gen, ConcatAlt) {
 473   std::vector<std::vector<int>> nums {{2, 3}, {5, 7}};
 474   auto actual = from(nums)
 475               | map([](std::vector<int>& v) { return from(v); })
 476               | concat
 477               | sum;
 478   auto expected = 17;
 479   EXPECT_EQ(expected, actual);
 480 }
 481
 482 TEST(Gen, Order) {
 483   auto expected = vector<int>{0, 3, 5, 6, 7, 8, 9};
 484   auto actual =
 485       from({8, 6, 7, 5, 3, 0, 9})
 486     | order
 487     | as<vector>();
 488   EXPECT_EQ(expected, actual);
 489 }
 490
 491 TEST(Gen, OrderMoved) {
 492   auto expected = vector<int>{0, 9, 25, 36, 49, 64, 81};
 493   auto actual =
 494       from({8, 6, 7, 5, 3, 0, 9})
 495     | move
 496     | order
 497     | map(square)
 498     | as<vector>();
 499   EXPECT_EQ(expected, actual);
 500 }
 501
 502 TEST(Gen, OrderTake) {
 503   auto expected = vector<int>{9, 8, 7};
 504   auto actual =
 505       from({8, 6, 7, 5, 3, 0, 9})
 506     | orderByDescending(square)
 507     | take(3)
 508     | as<vector>();
 509   EXPECT_EQ(expected, actual);
 510 }
 511
 512 TEST(Gen, Distinct) {
 513   auto expected = vector<int>{3, 1, 2};
 514   auto actual =
 515       from({3, 1, 3, 2, 1, 2, 3})
 516     | distinct
 517     | as<vector>();
 518   EXPECT_EQ(expected, actual);
 519 }
 520
 521 TEST(Gen, DistinctBy) {   //  0  1  4  9  6  5  6  9  4  1  0
 522   auto expected = vector<int>{0, 1, 2, 3, 4, 5};
 523   auto actual =
 524       seq(0, 100)
 525     | distinctBy([](int i) { return i * i % 10; })
 526     | as<vector>();
 527   EXPECT_EQ(expected, actual);
 528 }
 529
 530 TEST(Gen, DistinctMove) {   //  0  1  4  9  6  5  6  9  4  1  0
 531   auto expected = vector<int>{0, 1, 2, 3, 4, 5};
 532   auto actual =
 533       seq(0, 100)
 534     | mapped([](int i) { return std::unique_ptr<int>(new int(i)); })
 535       // see comment below about selector parameters for Distinct
 536     | distinctBy([](const std::unique_ptr<int>& pi) { return *pi * *pi % 10; })
 537     | mapped([](std::unique_ptr<int> pi) { return *pi; })
 538     | as<vector>();
 539
 540   // NOTE(tjackson): the following line intentionally doesn't work:
 541   //  | distinctBy([](std::unique_ptr<int> pi) { return *pi * *pi % 10; })
 542   // This is because distinctBy because the selector intentionally requires a
 543   // const reference.  If it required a move-reference, the value might get
 544   // gutted by the selector before said value could be passed to downstream
 545   // operators.
 546   EXPECT_EQ(expected, actual);
 547 }
 548
 549 TEST(Gen, MinBy) {
 550   EXPECT_EQ(7, seq(1, 10)
 551              | minBy([](int i) -> double {
 552                  double d = i - 6.8;
 553                  return d * d;
 554                }));
 555 }
 556
 557 TEST(Gen, MaxBy) {
 558   auto gen = from({"three", "eleven", "four"});
 559
 560   EXPECT_EQ("eleven", gen | maxBy(&strlen));
 561 }
 562
 563 TEST(Gen, Append) {
 564   fbstring expected = "facebook";
 565   fbstring actual = "face";
 566   from(StringPiece("book")) | appendTo(actual);
 567   EXPECT_EQ(expected, actual);
 568 }
 569
 570 TEST(Gen, FromRValue) {
 571   {
 572     // AFAICT The C++ Standard does not specify what happens to the rvalue
 573     // reference of a std::vector when it is used as the 'other' for an rvalue
 574     // constructor.  Use fbvector because we're sure its size will be zero in
 575     // this case.
 576     folly::fbvector<int> v({1,2,3,4});
 577     auto q1 = from(v);
 578     EXPECT_EQ(v.size(), 4);  // ensure that the lvalue version was called!
 579     auto expected = 1 * 2 * 3 * 4;
 580     EXPECT_EQ(expected, q1 | product);
 581
 582     auto q2 = from(std::move(v));
 583     EXPECT_EQ(v.size(), 0);  // ensure that rvalue version was called
 584     EXPECT_EQ(expected, q2 | product);
 585   }
 586   {
 587     auto expected = 7;
 588     auto q = from([] {return vector<int>({3,7,5}); }());
 589     EXPECT_EQ(expected, q | max);
 590   }
 591   {
 592     for (auto size: {5, 1024, 16384, 1<<20}) {
 593       auto q1 = from(vector<int>(size, 2));
 594       auto q2 = from(vector<int>(size, 3));
 595       // If the rvalue specialization is broken/gone, then the compiler will
 596       // (disgustingly!) just store a *reference* to the temporary object,
 597       // which is bad.  Try to catch this by allocating two temporary vectors
 598       // of the same size, so that they'll probably use the same underlying
 599       // buffer if q1's vector is destructed before q2's vector is constructed.
 600       EXPECT_EQ(size * 2 + size * 3, (q1 | sum) + (q2 | sum));
 601     }
 602   }
 603   {
 604     auto q = from(set<int>{1,2,3,2,1});
 605     EXPECT_EQ(q | sum, 6);
 606   }
 607 }
 608
 609 TEST(Gen, OrderBy) {
 610   auto expected = vector<int>{5, 6, 4, 7, 3, 8, 2, 9, 1, 10};
 611   auto actual =
 612       seq(1, 10)
 613     | orderBy([](int x) { return (5.1 - x) * (5.1 - x); })
 614     | as<vector>();
 615   EXPECT_EQ(expected, actual);
 616 }
 617
 618 TEST(Gen, Foldl) {
 619   int expected = 2 * 3 * 4 * 5;
 620   auto actual =
 621       seq(2, 5)
 622     | foldl(1, multiply);
 623   EXPECT_EQ(expected, actual);
 624 }
 625
 626 TEST(Gen, Reduce) {
 627   int expected = 2 + 3 + 4 + 5;
 628   auto actual = seq(2, 5) | reduce(add);
 629   EXPECT_EQ(expected, actual);
 630 }
 631
 632 TEST(Gen, ReduceBad) {
 633   auto gen = seq(1) | take(0);
 634   try {
 635     EXPECT_TRUE(true);
 636     gen | reduce(add);
 637     EXPECT_TRUE(false);
 638   } catch (...) {
 639   }
 640 }
 641
 642 TEST(Gen, Moves) {
 643   std::vector<unique_ptr<int>> ptrs;
 644   ptrs.emplace_back(new int(1));
 645   EXPECT_NE(ptrs.front().get(), nullptr);
 646   auto ptrs2 = from(ptrs) | move | as<vector>();
 647   EXPECT_EQ(ptrs.front().get(), nullptr);
 648   EXPECT_EQ(**ptrs2.data(), 1);
 649 }
 650
 651 TEST(Gen, First) {
 652   auto gen =
 653       seq(0)
 654     | filter([](int x) { return x > 3; });
 655   EXPECT_EQ(4, gen | first);
 656 }
 657
 658 TEST(Gen, FromCopy) {
 659   vector<int> v {3, 5};
 660   auto src = from(v);
 661   auto copy = fromCopy(v);
 662   EXPECT_EQ(8, src | sum);
 663   EXPECT_EQ(8, copy | sum);
 664   v[1] = 7;
 665   EXPECT_EQ(10, src | sum);
 666   EXPECT_EQ(8, copy | sum);
 667 }
 668
 669 TEST(Gen, Get) {
 670   std::map<int, int> pairs {
 671     {1, 1},
 672     {2, 4},
 673     {3, 9},
 674     {4, 16},
 675   };
 676   auto pairSrc = from(pairs);
 677   auto keys = pairSrc | get<0>();
 678   auto values = pairSrc | get<1>();
 679   EXPECT_EQ(10, keys | sum);
 680   EXPECT_EQ(30, values | sum);
 681   EXPECT_EQ(30, keys | map(square) | sum);
 682   pairs[5] = 25;
 683   EXPECT_EQ(15, keys | sum);
 684   EXPECT_EQ(55, values | sum);
 685
 686   vector<tuple<int, int, int>> tuples {
 687     make_tuple(1, 1, 1),
 688     make_tuple(2, 4, 8),
 689     make_tuple(3, 9, 27),
 690   };
 691   EXPECT_EQ(36, from(tuples) | get<2>() | sum);
 692 }
 693
 694 TEST(Gen, Any) {
 695   EXPECT_TRUE(seq(0) | any);
 696   EXPECT_TRUE(seq(0, 1) | any);
 697   EXPECT_TRUE(seq(0, 10) | any([](int i) { return i == 7; }));
 698   EXPECT_FALSE(seq(0, 10) | any([](int i) { return i == 11; }));
 699
 700   EXPECT_TRUE(from({1}) | any);
 701   EXPECT_FALSE(range(0, 0) | any);
 702   EXPECT_FALSE(from({1}) | take(0) | any);
 703 }
 704
 705 TEST(Gen, All) {
 706   EXPECT_TRUE(seq(0, 10) | all([](int i) { return i < 11; }));
 707   EXPECT_FALSE(seq(0, 10) | all([](int i) { return i < 5; }));
 708   EXPECT_FALSE(seq(0) | take(9999) | all([](int i) { return i < 10; }));
 709
 710   // empty lists satisfies all
 711   EXPECT_TRUE(seq(0) | take(0) | all([](int i) { return i < 50; }));
 712   EXPECT_TRUE(seq(0) | take(0) | all([](int i) { return i > 50; }));
 713 }
 714
 715 TEST(Gen, Yielders) {
 716   auto gen = GENERATOR(int) {
 717     for (int i = 1; i <= 5; ++i) {
 718       yield(i);
 719     }
 720     yield(7);
 721     for (int i = 3; ; ++i) {
 722       yield(i * i);
 723     }
 724   };
 725   vector<int> expected {
 726     1, 2, 3, 4, 5, 7, 9, 16, 25
 727   };
 728   EXPECT_EQ(expected, gen | take(9) | as<vector>());
 729 }
 730
 731 TEST(Gen, NestedYield) {
 732   auto nums = GENERATOR(int) {
 733     for (int i = 1; ; ++i) {
 734       yield(i);
 735     }
 736   };
 737   auto gen = GENERATOR(int) {
 738     nums | take(10) | yield;
 739     seq(1, 5) | [&](int i) {
 740       yield(i);
 741     };
 742   };
 743   EXPECT_EQ(70, gen | sum);
 744 }
 745
 746 TEST(Gen, MapYielders) {
 747   auto gen = seq(1, 5)
 748            | map([](int n) {
 749                return GENERATOR(int) {
 750                  int i;
 751                  for (i = 1; i < n; ++i)
 752                    yield(i);
 753                  for (; i >= 1; --i)
 754                    yield(i);
 755                };
 756              })
 757            | concat;
 758   vector<int> expected {
 759                 1,
 760              1, 2, 1,
 761           1, 2, 3, 2, 1,
 762        1, 2, 3, 4, 3, 2, 1,
 763     1, 2, 3, 4, 5, 4, 3, 2, 1,
 764   };
 765   EXPECT_EQ(expected, gen | as<vector>());
 766 }
 767
 768 TEST(Gen, VirtualGen) {
 769   VirtualGen<int> v(seq(1, 10));
 770   EXPECT_EQ(55, v | sum);
 771   v = v | map(square);
 772   EXPECT_EQ(385, v | sum);
 773   v = v | take(5);
 774   EXPECT_EQ(55, v | sum);
 775   EXPECT_EQ(30, v | take(4) | sum);
 776 }
 777
 778
 779 TEST(Gen, CustomType) {
 780   struct Foo{
 781     int y;
 782   };
 783   auto gen = from({Foo{2}, Foo{3}})
 784            | map([](const Foo& f) { return f.y; });
 785   EXPECT_EQ(5, gen | sum);
 786 }
 787
 788 TEST(Gen, NoNeedlessCopies) {
 789   auto gen = seq(1, 5)
 790            | map([](int x) { return unique_ptr<int>(new int(x)); })
 791            | map([](unique_ptr<int> p) { return p; })
 792            | map([](unique_ptr<int>&& p) { return std::move(p); })
 793            | map([](const unique_ptr<int>& p) { return *p; });
 794   EXPECT_EQ(15, gen | sum);
 795   EXPECT_EQ(6, gen | take(3) | sum);
 796 }
 797
 798 namespace {
 799
 800 class TestIntSeq : public GenImpl<int, TestIntSeq> {
 801  public:
 802   TestIntSeq() { }
 803
 804   template <class Body>
 805   bool apply(Body&& body) const {
 806     for (int i = 1; i < 6; ++i) {
 807       if (!body(i)) {
 808         return false;
 809       }
 810     }
 811     return true;
 812   }
 813
 814   TestIntSeq(TestIntSeq&&) = default;
 815   TestIntSeq& operator=(TestIntSeq&&) = default;
 816   TestIntSeq(const TestIntSeq&) = delete;
 817   TestIntSeq& operator=(const TestIntSeq&) = delete;
 818 };
 819
 820 }  // namespace
 821
 822 TEST(Gen, NoGeneratorCopies) {
 823   EXPECT_EQ(15, TestIntSeq() | sum);
 824   auto x = TestIntSeq() | take(3);
 825   EXPECT_EQ(6, std::move(x) | sum);
 826 }
 827
 828 TEST(Gen, FromArray) {
 829   int source[] = {2, 3, 5, 7};
 830   auto gen = from(source);
 831   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 832 }
 833
 834 TEST(Gen, FromStdArray) {
 835   std::array<int,4> source {{2, 3, 5, 7}};
 836   auto gen = from(source);
 837   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 838 }
 839
 840 TEST(Gen, StringConcat) {
 841   auto gen = seq(1, 10)
 842            | map([](int n) { return folly::to<fbstring>(n); })
 843            | rconcat;
 844   EXPECT_EQ("12345678910", gen | as<fbstring>());
 845 }
 846
 847 struct CopyCounter {
 848   static int alive;
 849   int copies;
 850   int moves;
 851
 852   CopyCounter() : copies(0), moves(0) {
 853     ++alive;
 854   }
 855
 856   CopyCounter(CopyCounter&& source) {
 857     *this = std::move(source);
 858     ++alive;
 859   }
 860
 861   CopyCounter(const CopyCounter& source) {
 862     *this = source;
 863     ++alive;
 864   }
 865
 866   ~CopyCounter() {
 867     --alive;
 868   }
 869
 870   CopyCounter& operator=(const CopyCounter& source) {
 871     this->copies = source.copies + 1;
 872     this->moves = source.moves;
 873     return *this;
 874   }
 875
 876   CopyCounter& operator=(CopyCounter&& source) {
 877     this->copies = source.copies;
 878     this->moves = source.moves + 1;
 879     return *this;
 880   }
 881 };
 882
 883 int CopyCounter::alive = 0;
 884
 885 TEST(Gen, CopyCount) {
 886   vector<CopyCounter> originals;
 887   originals.emplace_back();
 888   EXPECT_EQ(1, originals.size());
 889   EXPECT_EQ(0, originals.back().copies);
 890
 891   vector<CopyCounter> copies = from(originals) | as<vector>();
 892   EXPECT_EQ(1, copies.back().copies);
 893   EXPECT_EQ(0, copies.back().moves);
 894
 895   vector<CopyCounter> moves = from(originals) | move | as<vector>();
 896   EXPECT_EQ(0, moves.back().copies);
 897   EXPECT_EQ(1, moves.back().moves);
 898 }
 899
 900 // test dynamics with various layers of nested arrays.
 901 TEST(Gen, Dynamic) {
 902   dynamic array1 = {1, 2};
 903   EXPECT_EQ(dynamic(3), from(array1) | sum);
 904   dynamic array2 = {{1}, {1, 2}};
 905   EXPECT_EQ(dynamic(4), from(array2) | rconcat | sum);
 906   dynamic array3 = {{{1}}, {{1}, {1, 2}}};
 907   EXPECT_EQ(dynamic(5), from(array3) | rconcat | rconcat | sum);
 908 }
 909
 910 TEST(Gen, DynamicObject) {
 911   const dynamic obj = dynamic::object(1, 2)(3, 4);
 912   EXPECT_EQ(dynamic(4), from(obj.keys()) | sum);
 913   EXPECT_EQ(dynamic(6), from(obj.values()) | sum);
 914   EXPECT_EQ(dynamic(4), from(obj.items()) | get<0>() | sum);
 915   EXPECT_EQ(dynamic(6), from(obj.items()) | get<1>() | sum);
 916 }
 917
 918 TEST(Gen, Collect) {
 919   auto s = from({7, 6, 5, 4, 3}) | as<set<int>>();
 920   EXPECT_EQ(s.size(), 5);
 921 }
 922
 923 TEST(StringGen, EmptySplit) {
 924   auto collect = eachTo<std::string>() | as<vector>();
 925   {
 926     auto pieces = split("", ',') | collect;
 927     EXPECT_EQ(0, pieces.size());
 928   }
 929
 930   // The last delimiter is eaten, just like std::getline
 931   {
 932     auto pieces = split(",", ',') | collect;
 933     EXPECT_EQ(1, pieces.size());
 934     EXPECT_EQ("", pieces[0]);
 935   }
 936
 937   {
 938     auto pieces = split(",,", ',') | collect;
 939     EXPECT_EQ(2, pieces.size());
 940     EXPECT_EQ("", pieces[0]);
 941     EXPECT_EQ("", pieces[1]);
 942   }
 943
 944   {
 945     auto pieces = split(",,", ',') | take(1) | collect;
 946     EXPECT_EQ(1, pieces.size());
 947     EXPECT_EQ("", pieces[0]);
 948   }
 949 }
 950
 951 TEST(StringGen, Split) {
 952   auto collect = eachTo<std::string>() | as<vector>();
 953   {
 954     auto pieces = split("hello,, world, goodbye, meow", ',') | collect;
 955     EXPECT_EQ(5, pieces.size());
 956     EXPECT_EQ("hello", pieces[0]);
 957     EXPECT_EQ("", pieces[1]);
 958     EXPECT_EQ(" world", pieces[2]);
 959     EXPECT_EQ(" goodbye", pieces[3]);
 960     EXPECT_EQ(" meow", pieces[4]);
 961   }
 962
 963   {
 964     auto pieces = split("hello,, world, goodbye, meow", ',')
 965                 | take(3) | collect;
 966     EXPECT_EQ(3, pieces.size());
 967     EXPECT_EQ("hello", pieces[0]);
 968     EXPECT_EQ("", pieces[1]);
 969     EXPECT_EQ(" world", pieces[2]);
 970   }
 971
 972   {
 973     auto pieces = split("hello,, world, goodbye, meow", ',')
 974                 | take(5) | collect;
 975     EXPECT_EQ(5, pieces.size());
 976     EXPECT_EQ("hello", pieces[0]);
 977     EXPECT_EQ("", pieces[1]);
 978     EXPECT_EQ(" world", pieces[2]);
 979   }
 980 }
 981
 982 TEST(StringGen, EmptyResplit) {
 983   auto collect = eachTo<std::string>() | as<vector>();
 984   {
 985     auto pieces = from({""}) | resplit(',') | collect;
 986     EXPECT_EQ(0, pieces.size());
 987   }
 988
 989   // The last delimiter is eaten, just like std::getline
 990   {
 991     auto pieces = from({","}) | resplit(',') | collect;
 992     EXPECT_EQ(1, pieces.size());
 993     EXPECT_EQ("", pieces[0]);
 994   }
 995
 996   {
 997     auto pieces = from({",,"}) | resplit(',') | collect;
 998     EXPECT_EQ(2, pieces.size());
 999     EXPECT_EQ("", pieces[0]);
1000     EXPECT_EQ("", pieces[1]);
1001   }
1002 }
1003
1004 TEST(StringGen, EachToTuple) {
1005   {
1006     auto lines = "2:1.414:yo 3:1.732:hi";
1007     auto actual
1008       = split(lines, ' ')
1009       | eachToTuple<int, double, std::string>(':')
1010       | as<vector>();
1011     vector<tuple<int, double, std::string>> expected {
1012       make_tuple(2, 1.414, "yo"),
1013       make_tuple(3, 1.732, "hi"),
1014     };
1015     EXPECT_EQ(expected, actual);
1016   }
1017   {
1018     auto lines = "2 3";
1019     auto actual
1020       = split(lines, ' ')
1021       | eachToTuple<int>(',')
1022       | as<vector>();
1023     vector<tuple<int>> expected {
1024       make_tuple(2),
1025       make_tuple(3),
1026     };
1027     EXPECT_EQ(expected, actual);
1028   }
1029   {
1030     // StringPiece target
1031     auto lines = "1:cat 2:dog";
1032     auto actual
1033       = split(lines, ' ')
1034       | eachToTuple<int, StringPiece>(':')
1035       | as<vector>();
1036     vector<tuple<int, StringPiece>> expected {
1037       make_tuple(1, "cat"),
1038       make_tuple(2, "dog"),
1039     };
1040     EXPECT_EQ(expected, actual);
1041   }
1042   {
1043     // Empty field
1044     auto lines = "2:tjackson:4 3::5";
1045     auto actual
1046       = split(lines, ' ')
1047       | eachToTuple<int, fbstring, int>(':')
1048       | as<vector>();
1049     vector<tuple<int, fbstring, int>> expected {
1050       make_tuple(2, "tjackson", 4),
1051       make_tuple(3, "", 5),
1052     };
1053     EXPECT_EQ(expected, actual);
1054   }
1055   {
1056     // Excess fields
1057     auto lines = "1:2 3:4:5";
1058     EXPECT_THROW((split(lines, ' ')
1059                     | eachToTuple<int, int>(':')
1060                     | as<vector>()),
1061                  std::runtime_error);
1062   }
1063   {
1064     // Missing fields
1065     auto lines = "1:2:3 4:5";
1066     EXPECT_THROW((split(lines, ' ')
1067                     | eachToTuple<int, int, int>(':')
1068                     | as<vector>()),
1069                  std::runtime_error);
1070   }
1071 }
1072
1073 TEST(StringGen, EachToPair) {
1074   {
1075     // char delimiters
1076     auto lines = "2:1.414 3:1.732";
1077     auto actual
1078       = split(lines, ' ')
1079       | eachToPair<int, double>(':')
1080       | as<std::map<int, double>>();
1081     std::map<int, double> expected {
1082       { 3, 1.732 },
1083       { 2, 1.414 },
1084     };
1085     EXPECT_EQ(expected, actual);
1086   }
1087   {
1088     // string delimiters
1089     auto lines = "ab=>cd ef=>gh";
1090     auto actual
1091       = split(lines, ' ')
1092       | eachToPair<string, string>("=>")
1093       | as<std::map<string, string>>();
1094     std::map<string, string> expected {
1095       { "ab", "cd" },
1096       { "ef", "gh" },
1097     };
1098     EXPECT_EQ(expected, actual);
1099   }
1100 }
1101
1102
1103 TEST(StringGen, Resplit) {
1104   auto collect = eachTo<std::string>() | as<vector>();
1105   {
1106     auto pieces = from({"hello,, world, goodbye, meow"}) |
1107       resplit(',') | collect;
1108     EXPECT_EQ(5, pieces.size());
1109     EXPECT_EQ("hello", pieces[0]);
1110     EXPECT_EQ("", pieces[1]);
1111     EXPECT_EQ(" world", pieces[2]);
1112     EXPECT_EQ(" goodbye", pieces[3]);
1113     EXPECT_EQ(" meow", pieces[4]);
1114   }
1115   {
1116     auto pieces = from({"hel", "lo,", ", world", ", goodbye, m", "eow"}) |
1117       resplit(',') | collect;
1118     EXPECT_EQ(5, pieces.size());
1119     EXPECT_EQ("hello", pieces[0]);
1120     EXPECT_EQ("", pieces[1]);
1121     EXPECT_EQ(" world", pieces[2]);
1122     EXPECT_EQ(" goodbye", pieces[3]);
1123     EXPECT_EQ(" meow", pieces[4]);
1124   }
1125 }
1126
1127 template<typename F>
1128 void runUnsplitSuite(F fn) {
1129   fn("hello, world");
1130   fn("hello,world,goodbye");
1131   fn(" ");
1132   fn("");
1133   fn(", ");
1134   fn(", a, b,c");
1135 }
1136
1137 TEST(StringGen, Unsplit) {
1138
1139   auto basicFn = [](const StringPiece& s) {
1140     EXPECT_EQ(split(s, ',') | unsplit(','), s);
1141   };
1142
1143   auto existingBuffer = [](const StringPiece& s) {
1144     folly::fbstring buffer("asdf");
1145     split(s, ',') | unsplit(',', &buffer);
1146     auto expected = folly::to<folly::fbstring>(
1147         "asdf", s.empty() ? "" : ",", s);
1148     EXPECT_EQ(expected, buffer);
1149   };
1150
1151   auto emptyBuffer = [](const StringPiece& s) {
1152     std::string buffer;
1153     split(s, ',') | unsplit(',', &buffer);
1154     EXPECT_EQ(s, buffer);
1155   };
1156
1157   auto stringDelim = [](const StringPiece& s) {
1158     EXPECT_EQ(s, split(s, ',') | unsplit(","));
1159     std::string buffer;
1160     split(s, ',') | unsplit(",", &buffer);
1161     EXPECT_EQ(buffer, s);
1162   };
1163
1164   runUnsplitSuite(basicFn);
1165   runUnsplitSuite(existingBuffer);
1166   runUnsplitSuite(emptyBuffer);
1167   runUnsplitSuite(stringDelim);
1168   EXPECT_EQ("1, 2, 3", seq(1, 3) | unsplit(", "));
1169 }
1170
1171 TEST(FileGen, ByLine) {
1172   auto collect = eachTo<std::string>() | as<vector>();
1173   test::TemporaryFile file("ByLine");
1174   static const std::string lines(
1175       "Hello world\n"
1176       "This is the second line\n"
1177       "\n"
1178       "\n"
1179       "a few empty lines above\n"
1180       "incomplete last line");
1181   EXPECT_EQ(lines.size(), write(file.fd(), lines.data(), lines.size()));
1182
1183   auto expected = from({lines}) | resplit('\n') | collect;
1184   auto found = byLine(file.path().c_str()) | collect;
1185
1186   EXPECT_TRUE(expected == found);
1187 }
1188
1189 class FileGenBufferedTest : public ::testing::TestWithParam<int> { };
1190
1191 TEST_P(FileGenBufferedTest, FileWriter) {
1192   size_t bufferSize = GetParam();
1193   test::TemporaryFile file("FileWriter");
1194
1195   static const std::string lines(
1196       "Hello world\n"
1197       "This is the second line\n"
1198       "\n"
1199       "\n"
1200       "a few empty lines above\n");
1201
1202   auto src = from({lines, lines, lines, lines, lines, lines, lines, lines});
1203   auto collect = eachTo<std::string>() | as<vector>();
1204   auto expected = src | resplit('\n') | collect;
1205
1206   src | eachAs<StringPiece>() | toFile(file.fd(), bufferSize);
1207   auto found = byLine(file.path().c_str()) | collect;
1208
1209   EXPECT_TRUE(expected == found);
1210 }
1211
1212 INSTANTIATE_TEST_CASE_P(
1213     DifferentBufferSizes,
1214     FileGenBufferedTest,
1215     ::testing::Values(0, 1, 2, 4, 8, 64, 4096));
1216
1217 TEST(Gen, Guard) {
1218   using std::runtime_error;
1219   EXPECT_THROW(from({"1", "a", "3"})
1220                | eachTo<int>()
1221                | sum,
1222                runtime_error);
1223   EXPECT_EQ(4,
1224             from({"1", "a", "3"})
1225             | guard<runtime_error>([](runtime_error&, const char*) {
1226                 return true; // continue
1227               })
1228             | eachTo<int>()
1229             | sum);
1230   EXPECT_EQ(1,
1231             from({"1", "a", "3"})
1232             | guard<runtime_error>([](runtime_error&, const char*) {
1233                 return false; // break
1234               })
1235             | eachTo<int>()
1236             | sum);
1237   EXPECT_THROW(from({"1", "a", "3"})
1238                 | guard<runtime_error>([](runtime_error&, const char* v) {
1239                     if (v[0] == 'a') {
1240                       throw;
1241                     }
1242                     return true;
1243                   })
1244                | eachTo<int>()
1245                | sum,
1246                runtime_error);
1247 }
1248
1249 int main(int argc, char *argv[]) {
1250   testing::InitGoogleTest(&argc, argv);
1251   google::ParseCommandLineFlags(&argc, &argv, true);
1252   return RUN_ALL_TESTS();
1253 }