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