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