folly/gen/test/BaseTest.cpp

   1 /*
   2  * Copyright 2014 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           | mapped([](const Counter& c) { return &c; })
 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           | mapped([](Counter& c) { return &c; })
 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 TEST(Gen, Sample) {
 312   std::mt19937 rnd(42);
 313
 314   auto sampler =
 315       seq(1, 100)
 316     | sample(50, rnd);
 317   std::unordered_map<int,int> hits;
 318   const int kNumIters = 80;
 319   for (int i = 0; i < kNumIters; i++) {
 320     auto vec = sampler | as<vector<int>>();
 321     EXPECT_EQ(vec.size(), 50);
 322     auto uniq = fromConst(vec) | as<set<int>>();
 323     EXPECT_EQ(uniq.size(), vec.size());  // sampling without replacement
 324     for (auto v: vec) {
 325       ++hits[v];
 326     }
 327   }
 328
 329   // In 80 separate samples of our range, we should have seen every value
 330   // at least once and no value all 80 times. (The odds of either of those
 331   // events is 1/2^80).
 332   EXPECT_EQ(hits.size(), 100);
 333   for (auto hit: hits) {
 334     EXPECT_GT(hit.second, 0);
 335     EXPECT_LT(hit.second, kNumIters);
 336   }
 337
 338   auto small =
 339       seq(1, 5)
 340     | sample(10);
 341   EXPECT_EQ((small | sum), 15);
 342   EXPECT_EQ((small | take(3) | count), 3);
 343 }
 344
 345 TEST(Gen, Skip) {
 346   auto gen =
 347       seq(1, 1000)
 348     | mapped([](int x) { return x * x; })
 349     | skip(4)
 350     | take(4);
 351   EXPECT_EQ((vector<int>{25, 36, 49, 64}), gen | as<vector>());
 352 }
 353
 354 TEST(Gen, Until) {
 355   {
 356     auto expected = vector<int>{1, 4, 9, 16};
 357     auto actual
 358       = seq(1, 1000)
 359       | mapped([](int x) { return x * x; })
 360       | until([](int x) { return x > 20; })
 361       | as<vector<int>>();
 362     EXPECT_EQ(expected, actual);
 363   }
 364   {
 365     auto expected = vector<int>{ 0, 1, 4, 5, 8 };
 366     auto actual
 367       = ((seq(0) | until([](int i) { return i > 1; })) +
 368          (seq(4) | until([](int i) { return i > 5; })) +
 369          (seq(8) | until([](int i) { return i > 9; })))
 370       | until([](int i) { return i > 8; })
 371       | as<vector<int>>();
 372     EXPECT_EQ(expected, actual);
 373   }
 374   /*
 375   {
 376     auto expected = vector<int>{ 0, 1, 5, 6, 10 };
 377     auto actual
 378       = seq(0)
 379       | mapped([](int i) {
 380           return seq(i * 5) | until([=](int j) { return j > i * 5 + 1; });
 381         })
 382       | concat
 383       | until([](int i) { return i > 10; })
 384       | as<vector<int>>();
 385     EXPECT_EQ(expected, actual);
 386   }
 387   */
 388 }
 389
 390 TEST(Gen, Composed) {
 391   // Operator, Operator
 392   auto valuesOf =
 393       filter([](Optional<int>& o) { return o.hasValue(); })
 394     | map([](Optional<int>& o) -> int& { return o.value(); });
 395   std::vector<Optional<int>> opts {
 396     none, 4, none, 6, none
 397   };
 398   EXPECT_EQ(4 * 4 + 6 * 6, from(opts) | valuesOf | map(square) | sum);
 399   // Operator, Sink
 400   auto sumOpt = valuesOf | sum;
 401   EXPECT_EQ(10, from(opts) | sumOpt);
 402 }
 403
 404 TEST(Gen, Chain) {
 405   std::vector<int> nums {2, 3, 5, 7};
 406   std::map<int, int> mappings { { 3, 9}, {5, 25} };
 407   auto gen = from(nums) + (from(mappings) | get<1>());
 408   EXPECT_EQ(51, gen | sum);
 409   EXPECT_EQ(5, gen | take(2) | sum);
 410   EXPECT_EQ(26, gen | take(5) | sum);
 411 }
 412
 413 TEST(Gen, Concat) {
 414   std::vector<std::vector<int>> nums {{2, 3}, {5, 7}};
 415   auto gen = from(nums) | rconcat;
 416   EXPECT_EQ(17, gen | sum);
 417   EXPECT_EQ(10, gen | take(3) | sum);
 418 }
 419
 420 TEST(Gen, ConcatGen) {
 421   auto gen = seq(1, 10)
 422            | map([](int i) { return seq(1, i); })
 423            | concat;
 424   EXPECT_EQ(220, gen | sum);
 425   EXPECT_EQ(10, gen | take(6) | sum);
 426 }
 427
 428 TEST(Gen, ConcatAlt) {
 429   std::vector<std::vector<int>> nums {{2, 3}, {5, 7}};
 430   auto actual = from(nums)
 431               | map([](std::vector<int>& v) { return from(v); })
 432               | concat
 433               | sum;
 434   auto expected = 17;
 435   EXPECT_EQ(expected, actual);
 436 }
 437
 438 TEST(Gen, Order) {
 439   auto expected = vector<int>{0, 3, 5, 6, 7, 8, 9};
 440   auto actual =
 441       from({8, 6, 7, 5, 3, 0, 9})
 442     | order
 443     | as<vector>();
 444   EXPECT_EQ(expected, actual);
 445 }
 446
 447 TEST(Gen, OrderMoved) {
 448   auto expected = vector<int>{0, 9, 25, 36, 49, 64, 81};
 449   auto actual =
 450       from({8, 6, 7, 5, 3, 0, 9})
 451     | move
 452     | order
 453     | map(square)
 454     | as<vector>();
 455   EXPECT_EQ(expected, actual);
 456 }
 457
 458 TEST(Gen, OrderTake) {
 459   auto expected = vector<int>{9, 8, 7};
 460   auto actual =
 461       from({8, 6, 7, 5, 3, 0, 9})
 462     | orderByDescending(square)
 463     | take(3)
 464     | as<vector>();
 465   EXPECT_EQ(expected, actual);
 466 }
 467
 468 TEST(Gen, Distinct) {
 469   auto expected = vector<int>{3, 1, 2};
 470   auto actual =
 471       from({3, 1, 3, 2, 1, 2, 3})
 472     | distinct
 473     | as<vector>();
 474   EXPECT_EQ(expected, actual);
 475 }
 476
 477 TEST(Gen, DistinctBy) {   //  0  1  4  9  6  5  6  9  4  1  0
 478   auto expected = vector<int>{0, 1, 2, 3, 4, 5};
 479   auto actual =
 480       seq(0, 100)
 481     | distinctBy([](int i) { return i * i % 10; })
 482     | as<vector>();
 483   EXPECT_EQ(expected, actual);
 484 }
 485
 486 TEST(Gen, DistinctMove) {   //  0  1  4  9  6  5  6  9  4  1  0
 487   auto expected = vector<int>{0, 1, 2, 3, 4, 5};
 488   auto actual =
 489       seq(0, 100)
 490     | mapped([](int i) { return std::unique_ptr<int>(new int(i)); })
 491       // see comment below about selector parameters for Distinct
 492     | distinctBy([](const std::unique_ptr<int>& pi) { return *pi * *pi % 10; })
 493     | mapped([](std::unique_ptr<int> pi) { return *pi; })
 494     | as<vector>();
 495
 496   // NOTE(tjackson): the following line intentionally doesn't work:
 497   //  | distinctBy([](std::unique_ptr<int> pi) { return *pi * *pi % 10; })
 498   // This is because distinctBy because the selector intentionally requires a
 499   // const reference.  If it required a move-reference, the value might get
 500   // gutted by the selector before said value could be passed to downstream
 501   // operators.
 502   EXPECT_EQ(expected, actual);
 503 }
 504
 505 TEST(Gen, MinBy) {
 506   EXPECT_EQ(7, seq(1, 10)
 507              | minBy([](int i) -> double {
 508                  double d = i - 6.8;
 509                  return d * d;
 510                }));
 511 }
 512
 513 TEST(Gen, MaxBy) {
 514   auto gen = from({"three", "eleven", "four"});
 515
 516   EXPECT_EQ("eleven", gen | maxBy(&strlen));
 517 }
 518
 519 TEST(Gen, Append) {
 520   string expected = "facebook";
 521   string actual = "face";
 522   from(StringPiece("book")) | appendTo(actual);
 523   EXPECT_EQ(expected, actual);
 524 }
 525
 526 TEST(Gen, FromRValue) {
 527   {
 528     // AFAICT The C++ Standard does not specify what happens to the rvalue
 529     // reference of a std::vector when it is used as the 'other' for an rvalue
 530     // constructor.  Use fbvector because we're sure its size will be zero in
 531     // this case.
 532     fbvector<int> v({1,2,3,4});
 533     auto q1 = from(v);
 534     EXPECT_EQ(v.size(), 4);  // ensure that the lvalue version was called!
 535     auto expected = 1 * 2 * 3 * 4;
 536     EXPECT_EQ(expected, q1 | product);
 537
 538     auto q2 = from(std::move(v));
 539     EXPECT_EQ(v.size(), 0);  // ensure that rvalue version was called
 540     EXPECT_EQ(expected, q2 | product);
 541   }
 542   {
 543     auto expected = 7;
 544     auto q = from([] {return vector<int>({3,7,5}); }());
 545     EXPECT_EQ(expected, q | max);
 546   }
 547   {
 548     for (auto size: {5, 1024, 16384, 1<<20}) {
 549       auto q1 = from(vector<int>(size, 2));
 550       auto q2 = from(vector<int>(size, 3));
 551       // If the rvalue specialization is broken/gone, then the compiler will
 552       // (disgustingly!) just store a *reference* to the temporary object,
 553       // which is bad.  Try to catch this by allocating two temporary vectors
 554       // of the same size, so that they'll probably use the same underlying
 555       // buffer if q1's vector is destructed before q2's vector is constructed.
 556       EXPECT_EQ(size * 2 + size * 3, (q1 | sum) + (q2 | sum));
 557     }
 558   }
 559   {
 560     auto q = from(set<int>{1,2,3,2,1});
 561     EXPECT_EQ(q | sum, 6);
 562   }
 563 }
 564
 565 TEST(Gen, OrderBy) {
 566   auto expected = vector<int>{5, 6, 4, 7, 3, 8, 2, 9, 1, 10};
 567   auto actual =
 568       seq(1, 10)
 569     | orderBy([](int x) { return (5.1 - x) * (5.1 - x); })
 570     | as<vector>();
 571   EXPECT_EQ(expected, actual);
 572 }
 573
 574 TEST(Gen, Foldl) {
 575   int expected = 2 * 3 * 4 * 5;
 576   auto actual =
 577       seq(2, 5)
 578     | foldl(1, multiply);
 579   EXPECT_EQ(expected, actual);
 580 }
 581
 582 TEST(Gen, Reduce) {
 583   int expected = 2 + 3 + 4 + 5;
 584   auto actual = seq(2, 5) | reduce(add);
 585   EXPECT_EQ(expected, actual);
 586 }
 587
 588 TEST(Gen, ReduceBad) {
 589   auto gen = seq(1) | take(0);
 590   try {
 591     EXPECT_TRUE(true);
 592     gen | reduce(add);
 593     EXPECT_TRUE(false);
 594   } catch (...) {
 595   }
 596 }
 597
 598 TEST(Gen, Moves) {
 599   std::vector<unique_ptr<int>> ptrs;
 600   ptrs.emplace_back(new int(1));
 601   EXPECT_NE(ptrs.front().get(), nullptr);
 602   auto ptrs2 = from(ptrs) | move | as<vector>();
 603   EXPECT_EQ(ptrs.front().get(), nullptr);
 604   EXPECT_EQ(**ptrs2.data(), 1);
 605 }
 606
 607 TEST(Gen, First) {
 608   auto gen =
 609       seq(0)
 610     | filter([](int x) { return x > 3; });
 611   EXPECT_EQ(4, gen | first);
 612 }
 613
 614 TEST(Gen, FromCopy) {
 615   vector<int> v {3, 5};
 616   auto src = from(v);
 617   auto copy = fromCopy(v);
 618   EXPECT_EQ(8, src | sum);
 619   EXPECT_EQ(8, copy | sum);
 620   v[1] = 7;
 621   EXPECT_EQ(10, src | sum);
 622   EXPECT_EQ(8, copy | sum);
 623 }
 624
 625 TEST(Gen, Get) {
 626   std::map<int, int> pairs {
 627     {1, 1},
 628     {2, 4},
 629     {3, 9},
 630     {4, 16},
 631   };
 632   auto pairSrc = from(pairs);
 633   auto keys = pairSrc | get<0>();
 634   auto values = pairSrc | get<1>();
 635   EXPECT_EQ(10, keys | sum);
 636   EXPECT_EQ(30, values | sum);
 637   EXPECT_EQ(30, keys | map(square) | sum);
 638   pairs[5] = 25;
 639   EXPECT_EQ(15, keys | sum);
 640   EXPECT_EQ(55, values | sum);
 641
 642   vector<tuple<int, int, int>> tuples {
 643     make_tuple(1, 1, 1),
 644     make_tuple(2, 4, 8),
 645     make_tuple(3, 9, 27),
 646   };
 647   EXPECT_EQ(36, from(tuples) | get<2>() | sum);
 648 }
 649
 650 TEST(Gen, Any) {
 651   EXPECT_TRUE(seq(0) | any);
 652   EXPECT_TRUE(seq(0, 1) | any);
 653   EXPECT_TRUE(seq(0, 10) | any([](int i) { return i == 7; }));
 654   EXPECT_FALSE(seq(0, 10) | any([](int i) { return i == 11; }));
 655
 656   EXPECT_TRUE(from({1}) | any);
 657   EXPECT_FALSE(gen::range(0, 0) | any);
 658   EXPECT_FALSE(from({1}) | take(0) | any);
 659 }
 660
 661 TEST(Gen, All) {
 662   EXPECT_TRUE(seq(0, 10) | all([](int i) { return i < 11; }));
 663   EXPECT_FALSE(seq(0, 10) | all([](int i) { return i < 5; }));
 664   EXPECT_FALSE(seq(0) | take(9999) | all([](int i) { return i < 10; }));
 665
 666   // empty lists satisfies all
 667   EXPECT_TRUE(seq(0) | take(0) | all([](int i) { return i < 50; }));
 668   EXPECT_TRUE(seq(0) | take(0) | all([](int i) { return i > 50; }));
 669 }
 670
 671 TEST(Gen, Yielders) {
 672   auto gen = GENERATOR(int) {
 673     for (int i = 1; i <= 5; ++i) {
 674       yield(i);
 675     }
 676     yield(7);
 677     for (int i = 3; ; ++i) {
 678       yield(i * i);
 679     }
 680   };
 681   vector<int> expected {
 682     1, 2, 3, 4, 5, 7, 9, 16, 25
 683   };
 684   EXPECT_EQ(expected, gen | take(9) | as<vector>());
 685 }
 686
 687 TEST(Gen, NestedYield) {
 688   auto nums = GENERATOR(int) {
 689     for (int i = 1; ; ++i) {
 690       yield(i);
 691     }
 692   };
 693   auto gen = GENERATOR(int) {
 694     nums | take(10) | yield;
 695     seq(1, 5) | [&](int i) {
 696       yield(i);
 697     };
 698   };
 699   EXPECT_EQ(70, gen | sum);
 700 }
 701
 702 TEST(Gen, MapYielders) {
 703   auto gen = seq(1, 5)
 704            | map([](int n) {
 705                return GENERATOR(int) {
 706                  int i;
 707                  for (i = 1; i < n; ++i)
 708                    yield(i);
 709                  for (; i >= 1; --i)
 710                    yield(i);
 711                };
 712              })
 713            | concat;
 714   vector<int> expected {
 715                 1,
 716              1, 2, 1,
 717           1, 2, 3, 2, 1,
 718        1, 2, 3, 4, 3, 2, 1,
 719     1, 2, 3, 4, 5, 4, 3, 2, 1,
 720   };
 721   EXPECT_EQ(expected, gen | as<vector>());
 722 }
 723
 724 TEST(Gen, VirtualGen) {
 725   VirtualGen<int> v(seq(1, 10));
 726   EXPECT_EQ(55, v | sum);
 727   v = v | map(square);
 728   EXPECT_EQ(385, v | sum);
 729   v = v | take(5);
 730   EXPECT_EQ(55, v | sum);
 731   EXPECT_EQ(30, v | take(4) | sum);
 732 }
 733
 734
 735 TEST(Gen, CustomType) {
 736   struct Foo{
 737     int y;
 738   };
 739   auto gen = from({Foo{2}, Foo{3}})
 740            | map([](const Foo& f) { return f.y; });
 741   EXPECT_EQ(5, gen | sum);
 742 }
 743
 744 TEST(Gen, NoNeedlessCopies) {
 745   auto gen = seq(1, 5)
 746            | map([](int x) { return unique_ptr<int>(new int(x)); })
 747            | map([](unique_ptr<int> p) { return p; })
 748            | map([](unique_ptr<int>&& p) { return std::move(p); })
 749            | map([](const unique_ptr<int>& p) { return *p; });
 750   EXPECT_EQ(15, gen | sum);
 751   EXPECT_EQ(6, gen | take(3) | sum);
 752 }
 753
 754 namespace {
 755
 756 class TestIntSeq : public GenImpl<int, TestIntSeq> {
 757  public:
 758   TestIntSeq() { }
 759
 760   template <class Body>
 761   bool apply(Body&& body) const {
 762     for (int i = 1; i < 6; ++i) {
 763       if (!body(i)) {
 764         return false;
 765       }
 766     }
 767     return true;
 768   }
 769
 770   TestIntSeq(TestIntSeq&&) = default;
 771   TestIntSeq& operator=(TestIntSeq&&) = default;
 772   TestIntSeq(const TestIntSeq&) = delete;
 773   TestIntSeq& operator=(const TestIntSeq&) = delete;
 774 };
 775
 776 }  // namespace
 777
 778 TEST(Gen, NoGeneratorCopies) {
 779   EXPECT_EQ(15, TestIntSeq() | sum);
 780   auto x = TestIntSeq() | take(3);
 781   EXPECT_EQ(6, std::move(x) | sum);
 782 }
 783
 784 TEST(Gen, FromArray) {
 785   int source[] = {2, 3, 5, 7};
 786   auto gen = from(source);
 787   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 788 }
 789
 790 TEST(Gen, FromStdArray) {
 791   std::array<int,4> source {{2, 3, 5, 7}};
 792   auto gen = from(source);
 793   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 794 }
 795
 796 TEST(Gen, StringConcat) {
 797   auto gen = seq(1, 10)
 798            | eachTo<string>()
 799            | rconcat;
 800   EXPECT_EQ("12345678910", gen | as<string>());
 801 }
 802
 803 struct CopyCounter {
 804   static int alive;
 805   int copies;
 806   int moves;
 807
 808   CopyCounter() : copies(0), moves(0) {
 809     ++alive;
 810   }
 811
 812   CopyCounter(CopyCounter&& source) {
 813     *this = std::move(source);
 814     ++alive;
 815   }
 816
 817   CopyCounter(const CopyCounter& source) {
 818     *this = source;
 819     ++alive;
 820   }
 821
 822   ~CopyCounter() {
 823     --alive;
 824   }
 825
 826   CopyCounter& operator=(const CopyCounter& source) {
 827     this->copies = source.copies + 1;
 828     this->moves = source.moves;
 829     return *this;
 830   }
 831
 832   CopyCounter& operator=(CopyCounter&& source) {
 833     this->copies = source.copies;
 834     this->moves = source.moves + 1;
 835     return *this;
 836   }
 837 };
 838
 839 int CopyCounter::alive = 0;
 840
 841 TEST(Gen, CopyCount) {
 842   vector<CopyCounter> originals;
 843   originals.emplace_back();
 844   EXPECT_EQ(1, originals.size());
 845   EXPECT_EQ(0, originals.back().copies);
 846
 847   vector<CopyCounter> copies = from(originals) | as<vector>();
 848   EXPECT_EQ(1, copies.back().copies);
 849   EXPECT_EQ(0, copies.back().moves);
 850
 851   vector<CopyCounter> moves = from(originals) | move | as<vector>();
 852   EXPECT_EQ(0, moves.back().copies);
 853   EXPECT_EQ(1, moves.back().moves);
 854 }
 855
 856 // test dynamics with various layers of nested arrays.
 857 TEST(Gen, Dynamic) {
 858   dynamic array1 = {1, 2};
 859   EXPECT_EQ(dynamic(3), from(array1) | sum);
 860   dynamic array2 = {{1}, {1, 2}};
 861   EXPECT_EQ(dynamic(4), from(array2) | rconcat | sum);
 862   dynamic array3 = {{{1}}, {{1}, {1, 2}}};
 863   EXPECT_EQ(dynamic(5), from(array3) | rconcat | rconcat | sum);
 864 }
 865
 866 TEST(Gen, DynamicObject) {
 867   const dynamic obj = dynamic::object(1, 2)(3, 4);
 868   EXPECT_EQ(dynamic(4), from(obj.keys()) | sum);
 869   EXPECT_EQ(dynamic(6), from(obj.values()) | sum);
 870   EXPECT_EQ(dynamic(4), from(obj.items()) | get<0>() | sum);
 871   EXPECT_EQ(dynamic(6), from(obj.items()) | get<1>() | sum);
 872 }
 873
 874 TEST(Gen, Collect) {
 875   auto s = from({7, 6, 5, 4, 3}) | as<set<int>>();
 876   EXPECT_EQ(s.size(), 5);
 877 }
 878
 879
 880 TEST(Gen, Cycle) {
 881   {
 882     auto s = from({1, 2});
 883     EXPECT_EQ((vector<int> { 1, 2, 1, 2, 1 }),
 884               s | cycle | take(5) | as<vector>());
 885   }
 886   {
 887     auto s = from({1, 2});
 888     EXPECT_EQ((vector<int> { 1, 2, 1, 2 }),
 889               s | cycle(2) | as<vector>());
 890   }
 891   {
 892     auto s = from({1, 2, 3});
 893     EXPECT_EQ((vector<int> { 1, 2, 1, 2, 1 }),
 894               s | take(2) | cycle | take(5) | as<vector>());
 895   }
 896   {
 897     auto s = empty<int>();
 898     EXPECT_EQ((vector<int> { }),
 899               s | cycle | take(4) | as<vector>());
 900   }
 901   {
 902     int count = 3;
 903     int* pcount = &count;
 904     auto countdown = GENERATOR(int) {
 905       ASSERT_GE(*pcount, 0)
 906         << "Cycle should have stopped when it didnt' get values!";
 907       for (int i = 1; i <= *pcount; ++i) {
 908         yield(i);
 909       }
 910       --*pcount;
 911     };
 912     auto s = countdown;
 913     EXPECT_EQ((vector<int> { 1, 2, 3, 1, 2, 1}),
 914               s | cycle | as<vector>());
 915   }
 916 }
 917
 918 TEST(Gen, Dereference) {
 919   {
 920     const int x = 4, y = 2;
 921     auto s = from(std::initializer_list<const int*>({&x, nullptr, &y}));
 922     EXPECT_EQ(6, s | dereference | sum);
 923   }
 924   {
 925     vector<int> a { 1, 2 };
 926     vector<int> b { 3, 4 };
 927     vector<vector<int>*> pv { &a, nullptr, &b };
 928     from(pv)
 929       | dereference
 930       | [&](vector<int>& v) {
 931           v.push_back(5);
 932         };
 933     EXPECT_EQ(3, a.size());
 934     EXPECT_EQ(3, b.size());
 935     EXPECT_EQ(5, a.back());
 936     EXPECT_EQ(5, b.back());
 937   }
 938   {
 939     vector<std::map<int, int>> maps {
 940       {
 941         { 2, 31 },
 942         { 3, 41 },
 943       },
 944       {
 945         { 3, 52 },
 946         { 4, 62 },
 947       },
 948       {
 949         { 4, 73 },
 950         { 5, 83 },
 951       },
 952     };
 953     EXPECT_EQ(
 954       93,
 955       from(maps)
 956       | map([](std::map<int, int>& m) {
 957           return get_ptr(m, 3);
 958         })
 959       | dereference
 960       | sum);
 961   }
 962   {
 963     vector<unique_ptr<int>> ups;
 964     ups.emplace_back(new int(3));
 965     ups.emplace_back();
 966     ups.emplace_back(new int(7));
 967     EXPECT_EQ(10, from(ups) | dereference | sum);
 968     EXPECT_EQ(10, from(ups) | move | dereference | sum);
 969   }
 970 }
 971
 972 TEST(Gen, Guard) {
 973   using std::runtime_error;
 974   EXPECT_THROW(from({"1", "a", "3"})
 975                | eachTo<int>()
 976                | sum,
 977                runtime_error);
 978   EXPECT_EQ(4,
 979             from({"1", "a", "3"})
 980             | guard<runtime_error>([](runtime_error&, const char*) {
 981                 return true; // continue
 982               })
 983             | eachTo<int>()
 984             | sum);
 985   EXPECT_EQ(1,
 986             from({"1", "a", "3"})
 987             | guard<runtime_error>([](runtime_error&, const char*) {
 988                 return false; // break
 989               })
 990             | eachTo<int>()
 991             | sum);
 992   EXPECT_THROW(from({"1", "a", "3"})
 993                 | guard<runtime_error>([](runtime_error&, const char* v) {
 994                     if (v[0] == 'a') {
 995                       throw;
 996                     }
 997                     return true;
 998                   })
 999                | eachTo<int>()
1000                | sum,
1001                runtime_error);
1002 }
1003
1004 TEST(Gen, Batch) {
1005   EXPECT_EQ((vector<vector<int>> { {1} }),
1006             seq(1, 1) | batch(5) | as<vector>());
1007   EXPECT_EQ((vector<vector<int>> { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11} }),
1008             seq(1, 11) | batch(3) | as<vector>());
1009   EXPECT_THROW(seq(1, 1) | batch(0) | as<vector>(),
1010                std::invalid_argument);
1011 }
1012
1013 TEST(Gen, BatchMove) {
1014   auto expected = vector<vector<int>>{ {0, 1}, {2, 3}, {4} };
1015   auto actual =
1016       seq(0, 4)
1017     | mapped([](int i) { return std::unique_ptr<int>(new int(i)); })
1018     | batch(2)
1019     | mapped([](std::vector<std::unique_ptr<int>>& pVector) {
1020         std::vector<int> iVector;
1021         for (const auto& p : pVector) {
1022           iVector.push_back(*p);
1023         };
1024         return iVector;
1025       })
1026     | as<vector>();
1027   EXPECT_EQ(expected, actual);
1028 }
1029
1030 int main(int argc, char *argv[]) {
1031   testing::InitGoogleTest(&argc, argv);
1032   google::ParseCommandLineFlags(&argc, &argv, true);
1033   return RUN_ALL_TESTS();
1034 }