folly/gen/test/BaseTest.cpp

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