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, Min) {
 595   auto odds = seq(2,10) | filter([](int i){ return i % 2; });
 596
 597   EXPECT_EQ(3, odds | min);
 598 }
 599
 600 TEST(Gen, Max) {
 601   auto odds = seq(2,10) | filter([](int i){ return i % 2; });
 602
 603   EXPECT_EQ(9, odds | max);
 604 }
 605
 606 TEST(Gen, Append) {
 607   string expected = "facebook";
 608   string actual = "face";
 609   from(StringPiece("book")) | appendTo(actual);
 610   EXPECT_EQ(expected, actual);
 611 }
 612
 613 TEST(Gen, FromRValue) {
 614   {
 615     // AFAICT The C++ Standard does not specify what happens to the rvalue
 616     // reference of a std::vector when it is used as the 'other' for an rvalue
 617     // constructor.  Use fbvector because we're sure its size will be zero in
 618     // this case.
 619     fbvector<int> v({1,2,3,4});
 620     auto q1 = from(v);
 621     EXPECT_EQ(v.size(), 4);  // ensure that the lvalue version was called!
 622     auto expected = 1 * 2 * 3 * 4;
 623     EXPECT_EQ(expected, q1 | product);
 624
 625     auto q2 = from(std::move(v));
 626     EXPECT_EQ(v.size(), 0);  // ensure that rvalue version was called
 627     EXPECT_EQ(expected, q2 | product);
 628   }
 629   {
 630     auto expected = 7;
 631     auto q = from([] {return vector<int>({3,7,5}); }());
 632     EXPECT_EQ(expected, q | max);
 633   }
 634   {
 635     for (auto size: {5, 1024, 16384, 1<<20}) {
 636       auto q1 = from(vector<int>(size, 2));
 637       auto q2 = from(vector<int>(size, 3));
 638       // If the rvalue specialization is broken/gone, then the compiler will
 639       // (disgustingly!) just store a *reference* to the temporary object,
 640       // which is bad.  Try to catch this by allocating two temporary vectors
 641       // of the same size, so that they'll probably use the same underlying
 642       // buffer if q1's vector is destructed before q2's vector is constructed.
 643       EXPECT_EQ(size * 2 + size * 3, (q1 | sum) + (q2 | sum));
 644     }
 645   }
 646   {
 647     auto q = from(set<int>{1,2,3,2,1});
 648     EXPECT_EQ(q | sum, 6);
 649   }
 650 }
 651
 652 TEST(Gen, OrderBy) {
 653   auto expected = vector<int>{5, 6, 4, 7, 3, 8, 2, 9, 1, 10};
 654   auto actual =
 655       seq(1, 10)
 656     | orderBy([](int x) { return (5.1 - x) * (5.1 - x); })
 657     | as<vector>();
 658   EXPECT_EQ(expected, actual);
 659
 660   expected = seq(1, 10) | as<vector>();
 661   actual =
 662       from(expected)
 663     | map([] (int x) { return 11 - x; })
 664     | orderBy()
 665     | as<vector>();
 666   EXPECT_EQ(expected, actual);
 667 }
 668
 669 TEST(Gen, Foldl) {
 670   int expected = 2 * 3 * 4 * 5;
 671   auto actual =
 672       seq(2, 5)
 673     | foldl(1, multiply);
 674   EXPECT_EQ(expected, actual);
 675 }
 676
 677 TEST(Gen, Reduce) {
 678   int expected = 2 + 3 + 4 + 5;
 679   auto actual = seq(2, 5) | reduce(add);
 680   EXPECT_EQ(expected, actual);
 681 }
 682
 683 TEST(Gen, ReduceBad) {
 684   auto gen = seq(1) | take(0);
 685   try {
 686     EXPECT_TRUE(true);
 687     gen | reduce(add);
 688     EXPECT_TRUE(false);
 689   } catch (...) {
 690   }
 691 }
 692
 693 TEST(Gen, Moves) {
 694   std::vector<unique_ptr<int>> ptrs;
 695   ptrs.emplace_back(new int(1));
 696   EXPECT_NE(ptrs.front().get(), nullptr);
 697   auto ptrs2 = from(ptrs) | move | as<vector>();
 698   EXPECT_EQ(ptrs.front().get(), nullptr);
 699   EXPECT_EQ(**ptrs2.data(), 1);
 700 }
 701
 702 TEST(Gen, First) {
 703   auto gen =
 704       seq(0)
 705     | filter([](int x) { return x > 3; });
 706   EXPECT_EQ(4, gen | first);
 707 }
 708
 709 TEST(Gen, FromCopy) {
 710   vector<int> v {3, 5};
 711   auto src = from(v);
 712   auto copy = fromCopy(v);
 713   EXPECT_EQ(8, src | sum);
 714   EXPECT_EQ(8, copy | sum);
 715   v[1] = 7;
 716   EXPECT_EQ(10, src | sum);
 717   EXPECT_EQ(8, copy | sum);
 718 }
 719
 720 TEST(Gen, Get) {
 721   std::map<int, int> pairs {
 722     {1, 1},
 723     {2, 4},
 724     {3, 9},
 725     {4, 16},
 726   };
 727   auto pairSrc = from(pairs);
 728   auto keys = pairSrc | get<0>();
 729   auto values = pairSrc | get<1>();
 730   EXPECT_EQ(10, keys | sum);
 731   EXPECT_EQ(30, values | sum);
 732   EXPECT_EQ(30, keys | map(square) | sum);
 733   pairs[5] = 25;
 734   EXPECT_EQ(15, keys | sum);
 735   EXPECT_EQ(55, values | sum);
 736
 737   vector<tuple<int, int, int>> tuples {
 738     make_tuple(1, 1, 1),
 739     make_tuple(2, 4, 8),
 740     make_tuple(3, 9, 27),
 741   };
 742   EXPECT_EQ(36, from(tuples) | get<2>() | sum);
 743 }
 744
 745 TEST(Gen, notEmpty) {
 746   EXPECT_TRUE(seq(0) | notEmpty);
 747   EXPECT_TRUE(seq(0, 1) | notEmpty);
 748   EXPECT_TRUE(just(1) | notEmpty);
 749   EXPECT_FALSE(gen::range(0, 0) | notEmpty);
 750   EXPECT_FALSE(from({1}) | take(0) | notEmpty);
 751   EXPECT_TRUE(seq(1, 3) | cycle | notEmpty);
 752 }
 753
 754 TEST(Gen, isEmpty) {
 755   EXPECT_FALSE(seq(0) | isEmpty);
 756   EXPECT_FALSE(seq(0, 1) | isEmpty);
 757   EXPECT_FALSE(just(1) | isEmpty);
 758   EXPECT_TRUE(gen::range(0, 0) | isEmpty);
 759   EXPECT_TRUE(from({1}) | take(0) | isEmpty);
 760   EXPECT_FALSE(seq(1, 3) | cycle | isEmpty);
 761 }
 762
 763 TEST(Gen, Any) {
 764   EXPECT_TRUE(seq(0, 10) | any([](int i) { return i == 7; }));
 765   EXPECT_FALSE(seq(0, 10) | any([](int i) { return i == 11; }));
 766 }
 767
 768 TEST(Gen, All) {
 769   EXPECT_TRUE(seq(0, 10) | all([](int i) { return i < 11; }));
 770   EXPECT_FALSE(seq(0, 10) | all([](int i) { return i < 5; }));
 771   EXPECT_FALSE(seq(0) | take(9999) | all([](int i) { return i < 10; }));
 772
 773   // empty lists satisfies all
 774   EXPECT_TRUE(seq(0) | take(0) | all([](int i) { return i < 50; }));
 775   EXPECT_TRUE(seq(0) | take(0) | all([](int i) { return i > 50; }));
 776 }
 777
 778 TEST(Gen, Yielders) {
 779   auto gen = GENERATOR(int) {
 780     for (int i = 1; i <= 5; ++i) {
 781       yield(i);
 782     }
 783     yield(7);
 784     for (int i = 3; ; ++i) {
 785       yield(i * i);
 786     }
 787   };
 788   vector<int> expected {
 789     1, 2, 3, 4, 5, 7, 9, 16, 25
 790   };
 791   EXPECT_EQ(expected, gen | take(9) | as<vector>());
 792 }
 793
 794 TEST(Gen, NestedYield) {
 795   auto nums = GENERATOR(int) {
 796     for (int i = 1; ; ++i) {
 797       yield(i);
 798     }
 799   };
 800   auto gen = GENERATOR(int) {
 801     nums | take(10) | yield;
 802     seq(1, 5) | [&](int i) {
 803       yield(i);
 804     };
 805   };
 806   EXPECT_EQ(70, gen | sum);
 807 }
 808
 809 TEST(Gen, MapYielders) {
 810   auto gen = seq(1, 5)
 811            | map([](int n) {
 812                return GENERATOR(int) {
 813                  int i;
 814                  for (i = 1; i < n; ++i)
 815                    yield(i);
 816                  for (; i >= 1; --i)
 817                    yield(i);
 818                };
 819              })
 820            | concat;
 821   vector<int> expected {
 822                 1,
 823              1, 2, 1,
 824           1, 2, 3, 2, 1,
 825        1, 2, 3, 4, 3, 2, 1,
 826     1, 2, 3, 4, 5, 4, 3, 2, 1,
 827   };
 828   EXPECT_EQ(expected, gen | as<vector>());
 829 }
 830
 831 TEST(Gen, VirtualGen) {
 832   VirtualGen<int> v(seq(1, 10));
 833   EXPECT_EQ(55, v | sum);
 834   v = v | map(square);
 835   EXPECT_EQ(385, v | sum);
 836   v = v | take(5);
 837   EXPECT_EQ(55, v | sum);
 838   EXPECT_EQ(30, v | take(4) | sum);
 839 }
 840
 841
 842 TEST(Gen, CustomType) {
 843   struct Foo{
 844     int y;
 845   };
 846   auto gen = from({Foo{2}, Foo{3}})
 847            | map([](const Foo& f) { return f.y; });
 848   EXPECT_EQ(5, gen | sum);
 849 }
 850
 851 TEST(Gen, NoNeedlessCopies) {
 852   auto gen = seq(1, 5)
 853            | map([](int x) { return unique_ptr<int>(new int(x)); })
 854            | map([](unique_ptr<int> p) { return p; })
 855            | map([](unique_ptr<int>&& p) { return std::move(p); })
 856            | map([](const unique_ptr<int>& p) { return *p; });
 857   EXPECT_EQ(15, gen | sum);
 858   EXPECT_EQ(6, gen | take(3) | sum);
 859 }
 860
 861 namespace {
 862
 863 class TestIntSeq : public GenImpl<int, TestIntSeq> {
 864  public:
 865   TestIntSeq() { }
 866
 867   template <class Body>
 868   bool apply(Body&& body) const {
 869     for (int i = 1; i < 6; ++i) {
 870       if (!body(i)) {
 871         return false;
 872       }
 873     }
 874     return true;
 875   }
 876
 877   TestIntSeq(TestIntSeq&&) noexcept = default;
 878   TestIntSeq& operator=(TestIntSeq&&) noexcept = default;
 879   TestIntSeq(const TestIntSeq&) = delete;
 880   TestIntSeq& operator=(const TestIntSeq&) = delete;
 881 };
 882
 883 }  // namespace
 884
 885 TEST(Gen, NoGeneratorCopies) {
 886   EXPECT_EQ(15, TestIntSeq() | sum);
 887   auto x = TestIntSeq() | take(3);
 888   EXPECT_EQ(6, std::move(x) | sum);
 889 }
 890
 891 TEST(Gen, FromArray) {
 892   int source[] = {2, 3, 5, 7};
 893   auto gen = from(source);
 894   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 895 }
 896
 897 TEST(Gen, FromStdArray) {
 898   std::array<int,4> source {{2, 3, 5, 7}};
 899   auto gen = from(source);
 900   EXPECT_EQ(2 * 3 * 5 * 7, gen | product);
 901 }
 902
 903 TEST(Gen, StringConcat) {
 904   auto gen = seq(1, 10)
 905            | eachTo<string>()
 906            | rconcat;
 907   EXPECT_EQ("12345678910", gen | as<string>());
 908 }
 909
 910 struct CopyCounter {
 911   static int alive;
 912   int copies;
 913   int moves;
 914
 915   CopyCounter() : copies(0), moves(0) {
 916     ++alive;
 917   }
 918
 919   CopyCounter(CopyCounter&& source) noexcept {
 920     *this = std::move(source);
 921     ++alive;
 922   }
 923
 924   CopyCounter(const CopyCounter& source) {
 925     *this = source;
 926     ++alive;
 927   }
 928
 929   ~CopyCounter() {
 930     --alive;
 931   }
 932
 933   CopyCounter& operator=(const CopyCounter& source) {
 934     this->copies = source.copies + 1;
 935     this->moves = source.moves;
 936     return *this;
 937   }
 938
 939   CopyCounter& operator=(CopyCounter&& source) {
 940     this->copies = source.copies;
 941     this->moves = source.moves + 1;
 942     return *this;
 943   }
 944 };
 945
 946 int CopyCounter::alive = 0;
 947
 948 TEST(Gen, CopyCount) {
 949   vector<CopyCounter> originals;
 950   originals.emplace_back();
 951   EXPECT_EQ(1, originals.size());
 952   EXPECT_EQ(0, originals.back().copies);
 953
 954   vector<CopyCounter> copies = from(originals) | as<vector>();
 955   EXPECT_EQ(1, copies.back().copies);
 956   EXPECT_EQ(0, copies.back().moves);
 957
 958   vector<CopyCounter> moves = from(originals) | move | as<vector>();
 959   EXPECT_EQ(0, moves.back().copies);
 960   EXPECT_EQ(1, moves.back().moves);
 961 }
 962
 963 // test dynamics with various layers of nested arrays.
 964 TEST(Gen, Dynamic) {
 965   dynamic array1 = {1, 2};
 966   EXPECT_EQ(dynamic(3), from(array1) | sum);
 967   dynamic array2 = {{1}, {1, 2}};
 968   EXPECT_EQ(dynamic(4), from(array2) | rconcat | sum);
 969   dynamic array3 = {{{1}}, {{1}, {1, 2}}};
 970   EXPECT_EQ(dynamic(5), from(array3) | rconcat | rconcat | sum);
 971 }
 972
 973 TEST(Gen, DynamicObject) {
 974   const dynamic obj = dynamic::object(1, 2)(3, 4);
 975   EXPECT_EQ(dynamic(4), from(obj.keys()) | sum);
 976   EXPECT_EQ(dynamic(6), from(obj.values()) | sum);
 977   EXPECT_EQ(dynamic(4), from(obj.items()) | get<0>() | sum);
 978   EXPECT_EQ(dynamic(6), from(obj.items()) | get<1>() | sum);
 979 }
 980
 981 TEST(Gen, Collect) {
 982   auto s = from({7, 6, 5, 4, 3}) | as<set<int>>();
 983   EXPECT_EQ(s.size(), 5);
 984 }
 985
 986
 987 TEST(Gen, Cycle) {
 988   {
 989     auto s = from({1, 2});
 990     EXPECT_EQ((vector<int> { 1, 2, 1, 2, 1 }),
 991               s | cycle | take(5) | as<vector>());
 992   }
 993   {
 994     auto s = from({1, 2});
 995     EXPECT_EQ((vector<int> { 1, 2, 1, 2 }),
 996               s | cycle(2) | as<vector>());
 997   }
 998   {
 999     auto s = from({1, 2, 3});
1000     EXPECT_EQ((vector<int> { 1, 2, 1, 2, 1 }),
1001               s | take(2) | cycle | take(5) | as<vector>());
1002   }
1003   {
1004     auto s = empty<int>();
1005     EXPECT_EQ((vector<int> { }),
1006               s | cycle | take(4) | as<vector>());
1007   }
1008   {
1009     int count = 3;
1010     int* pcount = &count;
1011     auto countdown = GENERATOR(int) {
1012       ASSERT_GE(*pcount, 0)
1013         << "Cycle should have stopped when it didnt' get values!";
1014       for (int i = 1; i <= *pcount; ++i) {
1015         yield(i);
1016       }
1017       --*pcount;
1018     };
1019     auto s = countdown;
1020     EXPECT_EQ((vector<int> { 1, 2, 3, 1, 2, 1}),
1021               s | cycle | as<vector>());
1022   }
1023 }
1024
1025 TEST(Gen, Dereference) {
1026   {
1027     const int x = 4, y = 2;
1028     auto s = from(std::initializer_list<const int*>({&x, nullptr, &y}));
1029     EXPECT_EQ(6, s | dereference | sum);
1030   }
1031   {
1032     vector<int> a { 1, 2 };
1033     vector<int> b { 3, 4 };
1034     vector<vector<int>*> pv { &a, nullptr, &b };
1035     from(pv)
1036       | dereference
1037       | [&](vector<int>& v) {
1038           v.push_back(5);
1039         };
1040     EXPECT_EQ(3, a.size());
1041     EXPECT_EQ(3, b.size());
1042     EXPECT_EQ(5, a.back());
1043     EXPECT_EQ(5, b.back());
1044   }
1045   {
1046     vector<std::map<int, int>> maps {
1047       {
1048         { 2, 31 },
1049         { 3, 41 },
1050       },
1051       {
1052         { 3, 52 },
1053         { 4, 62 },
1054       },
1055       {
1056         { 4, 73 },
1057         { 5, 83 },
1058       },
1059     };
1060     EXPECT_EQ(
1061       93,
1062       from(maps)
1063       | map([](std::map<int, int>& m) {
1064           return get_ptr(m, 3);
1065         })
1066       | dereference
1067       | sum);
1068   }
1069   {
1070     vector<unique_ptr<int>> ups;
1071     ups.emplace_back(new int(3));
1072     ups.emplace_back();
1073     ups.emplace_back(new int(7));
1074     EXPECT_EQ(10, from(ups) | dereference | sum);
1075     EXPECT_EQ(10, from(ups) | move | dereference | sum);
1076   }
1077 }
1078
1079 TEST(Gen, Indirect) {
1080   vector<int> vs{1};
1081   EXPECT_EQ(&vs[0], from(vs) | indirect | first);
1082 }
1083
1084 TEST(Gen, Guard) {
1085   using std::runtime_error;
1086   EXPECT_THROW(from({"1", "a", "3"})
1087                | eachTo<int>()
1088                | sum,
1089                runtime_error);
1090   EXPECT_EQ(4,
1091             from({"1", "a", "3"})
1092             | guard<runtime_error>([](runtime_error&, const char*) {
1093                 return true; // continue
1094               })
1095             | eachTo<int>()
1096             | sum);
1097   EXPECT_EQ(1,
1098             from({"1", "a", "3"})
1099             | guard<runtime_error>([](runtime_error&, const char*) {
1100                 return false; // break
1101               })
1102             | eachTo<int>()
1103             | sum);
1104   EXPECT_THROW(from({"1", "a", "3"})
1105                 | guard<runtime_error>([](runtime_error&, const char* v) {
1106                     if (v[0] == 'a') {
1107                       throw;
1108                     }
1109                     return true;
1110                   })
1111                | eachTo<int>()
1112                | sum,
1113                runtime_error);
1114 }
1115
1116 TEST(Gen, Batch) {
1117   EXPECT_EQ((vector<vector<int>> { {1} }),
1118             seq(1, 1) | batch(5) | as<vector>());
1119   EXPECT_EQ((vector<vector<int>> { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11} }),
1120             seq(1, 11) | batch(3) | as<vector>());
1121   EXPECT_THROW(seq(1, 1) | batch(0) | as<vector>(),
1122                std::invalid_argument);
1123 }
1124
1125 TEST(Gen, BatchMove) {
1126   auto expected = vector<vector<int>>{ {0, 1}, {2, 3}, {4} };
1127   auto actual =
1128       seq(0, 4)
1129     | mapped([](int i) { return std::unique_ptr<int>(new int(i)); })
1130     | batch(2)
1131     | mapped([](std::vector<std::unique_ptr<int>>& pVector) {
1132         std::vector<int> iVector;
1133         for (const auto& p : pVector) {
1134           iVector.push_back(*p);
1135         };
1136         return iVector;
1137       })
1138     | as<vector>();
1139   EXPECT_EQ(expected, actual);
1140 }
1141
1142 TEST(Gen, Just) {
1143   {
1144     int x = 3;
1145     auto j = just(x);
1146     EXPECT_EQ(&x, j | indirect | first);
1147     x = 4;
1148     EXPECT_EQ(4, j | first);
1149   }
1150   {
1151     int x = 3;
1152     const int& cx = x;
1153     auto j = just(cx);
1154     EXPECT_EQ(&x, j | indirect | first);
1155     x = 5;
1156     EXPECT_EQ(5, j | first);
1157   }
1158   {
1159     int x = 3;
1160     auto j = just(std::move(x));
1161     EXPECT_NE(&x, j | indirect | first);
1162     x = 5;
1163     EXPECT_EQ(3, j | first);
1164   }
1165 }
1166
1167 TEST(Gen, GroupBy) {
1168   vector<string> strs{"zero", "one", "two",   "three", "four",
1169                       "five", "six", "seven", "eight", "nine"};
1170
1171   auto gb = from(strs) | groupBy([](const string& str) { return str.size(); });
1172
1173   EXPECT_EQ(10, gb | mapOp(count) | sum);
1174   EXPECT_EQ(3, gb | count);
1175
1176   vector<string> mode{"zero", "four", "five", "nine"};
1177   EXPECT_EQ(
1178       mode,
1179       gb | maxBy([](const Group<size_t, string>& g) { return g.size(); })
1180          | as<vector>());
1181
1182   vector<string> largest{"three", "seven", "eight"};
1183   EXPECT_EQ(
1184       largest,
1185       gb | maxBy([](const Group<size_t, string>& g) { return g.key(); })
1186          | as<vector>());
1187 }
1188
1189 int main(int argc, char *argv[]) {
1190   testing::InitGoogleTest(&argc, argv);
1191   gflags::ParseCommandLineFlags(&argc, &argv, true);
1192   return RUN_ALL_TESTS();
1193 }