folly/gen/Base.h

   1 /*
   2  * Copyright 2017 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 #pragma once
  18 #define FOLLY_GEN_BASE_H_
  19
  20 #include <algorithm>
  21 #include <functional>
  22 #include <memory>
  23 #include <random>
  24 #include <type_traits>
  25 #include <unordered_map>
  26 #include <unordered_set>
  27 #include <utility>
  28 #include <vector>
  29
  30 #include <folly/Conv.h>
  31 #include <folly/Optional.h>
  32 #include <folly/Range.h>
  33 #include <folly/Utility.h>
  34 #include <folly/gen/Core.h>
  35
  36 /**
  37  * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ
  38  * @author Tom Jackson <tjackson@fb.com>
  39  *
  40  * This library makes it possible to write declarative comprehensions for
  41  * processing sequences of values efficiently in C++. The operators should be
  42  * familiar to those with experience in functional programming, and the
  43  * performance will be virtually identical to the equivalent, boilerplate C++
  44  * implementations.
  45  *
  46  * Generator objects may be created from either an stl-like container (anything
  47  * supporting begin() and end()), from sequences of values, or from another
  48  * generator (see below). To create a generator that pulls values from a vector,
  49  * for example, one could write:
  50  *
  51  *   vector<string> names { "Jack", "Jill", "Sara", "Tom" };
  52  *   auto gen = from(names);
  53  *
  54  * Generators are composed by building new generators out of old ones through
  55  * the use of operators. These are reminicent of shell pipelines, and afford
  56  * similar composition. Lambda functions are used liberally to describe how to
  57  * handle individual values:
  58  *
  59  *   auto lengths = gen
  60  *                | mapped([](const fbstring& name) { return name.size(); });
  61  *
  62  * Generators are lazy; they don't actually perform any work until they need to.
  63  * As an example, the 'lengths' generator (above) won't actually invoke the
  64  * provided lambda until values are needed:
  65  *
  66  *   auto lengthVector = lengths | as<std::vector>();
  67  *   auto totalLength = lengths | sum;
  68  *
  69  * 'auto' is useful in here because the actual types of the generators objects
  70  * are usually complicated and implementation-sensitive.
  71  *
  72  * If a simpler type is desired (for returning, as an example), VirtualGen<T>
  73  * may be used to wrap the generator in a polymorphic wrapper:
  74  *
  75  *  VirtualGen<float> powersOfE() {
  76  *    return seq(1) | mapped(&expf);
  77  *  }
  78  *
  79  * To learn more about this library, including the use of infinite generators,
  80  * see the examples in the comments, or the docs (coming soon).
  81 */
  82
  83 namespace folly { namespace gen {
  84
  85 class Less {
  86 public:
  87   template<class First,
  88            class Second>
  89   auto operator()(const First& first, const Second& second) const ->
  90   decltype(first < second) {
  91     return first < second;
  92   }
  93 };
  94
  95 class Greater {
  96 public:
  97   template<class First,
  98            class Second>
  99   auto operator()(const First& first, const Second& second) const ->
 100   decltype(first > second) {
 101     return first > second;
 102   }
 103 };
 104
 105 template<int n>
 106 class Get {
 107 public:
 108   template<class Value>
 109   auto operator()(Value&& value) const ->
 110   decltype(std::get<n>(std::forward<Value>(value))) {
 111     return std::get<n>(std::forward<Value>(value));
 112   }
 113 };
 114
 115 template<class Class,
 116          class Result>
 117 class MemberFunction {
 118  public:
 119   typedef Result (Class::*MemberPtr)();
 120  private:
 121   MemberPtr member_;
 122  public:
 123   explicit MemberFunction(MemberPtr member)
 124     : member_(member)
 125   {}
 126
 127   Result operator()(Class&& x) const {
 128     return (x.*member_)();
 129   }
 130
 131   Result operator()(Class& x) const {
 132     return (x.*member_)();
 133   }
 134
 135   Result operator()(Class* x) const {
 136     return (x->*member_)();
 137   }
 138 };
 139
 140 template<class Class,
 141          class Result>
 142 class ConstMemberFunction{
 143  public:
 144   typedef Result (Class::*MemberPtr)() const;
 145  private:
 146   MemberPtr member_;
 147  public:
 148   explicit ConstMemberFunction(MemberPtr member)
 149     : member_(member)
 150   {}
 151
 152   Result operator()(const Class& x) const {
 153     return (x.*member_)();
 154   }
 155
 156   Result operator()(const Class* x) const {
 157     return (x->*member_)();
 158   }
 159 };
 160
 161 template<class Class,
 162          class FieldType>
 163 class Field {
 164  public:
 165   typedef FieldType (Class::*FieldPtr);
 166  private:
 167   FieldPtr field_;
 168  public:
 169   explicit Field(FieldPtr field)
 170     : field_(field)
 171   {}
 172
 173   const FieldType& operator()(const Class& x) const {
 174     return x.*field_;
 175   }
 176
 177   const FieldType& operator()(const Class* x) const {
 178     return x->*field_;
 179   }
 180
 181   FieldType& operator()(Class& x) const {
 182     return x.*field_;
 183   }
 184
 185   FieldType& operator()(Class* x) const {
 186     return x->*field_;
 187   }
 188
 189   FieldType&& operator()(Class&& x) const {
 190     return std::move(x.*field_);
 191   }
 192 };
 193
 194 class Move {
 195 public:
 196   template<class Value>
 197   auto operator()(Value&& value) const ->
 198   decltype(std::move(std::forward<Value>(value))) {
 199     return std::move(std::forward<Value>(value));
 200   }
 201 };
 202
 203 /**
 204  * Class and helper function for negating a boolean Predicate
 205  */
 206 template <class Predicate>
 207 class Negate {
 208   Predicate pred_;
 209
 210  public:
 211   Negate() = default;
 212
 213   explicit Negate(Predicate pred)
 214     : pred_(std::move(pred))
 215   {}
 216
 217   template <class Arg>
 218   bool operator()(Arg&& arg) const {
 219     return !pred_(std::forward<Arg>(arg));
 220   }
 221 };
 222 template <class Predicate>
 223 Negate<Predicate> negate(Predicate pred) {
 224   return Negate<Predicate>(std::move(pred));
 225 }
 226
 227 template <class Dest>
 228 class Cast {
 229  public:
 230   template <class Value>
 231   Dest operator()(Value&& value) const {
 232     return Dest(std::forward<Value>(value));
 233   }
 234 };
 235
 236 template <class Dest>
 237 class To {
 238  public:
 239   template <class Value>
 240   Dest operator()(Value&& value) const {
 241     return ::folly::to<Dest>(std::forward<Value>(value));
 242   }
 243 };
 244
 245 // Specialization to allow String->StringPiece conversion
 246 template <>
 247 class To<StringPiece> {
 248  public:
 249   StringPiece operator()(StringPiece src) const {
 250     return src;
 251   }
 252 };
 253
 254 template<class Key, class Value>
 255 class Group;
 256
 257 namespace detail {
 258
 259 template<class Self>
 260 struct FBounded;
 261
 262 /*
 263  * Type Traits
 264  */
 265 template<class Container>
 266 struct ValueTypeOfRange {
 267  public:
 268   using RefType = decltype(*std::begin(std::declval<Container&>()));
 269   using StorageType = typename std::decay<RefType>::type;
 270 };
 271
 272
 273 /*
 274  * Sources
 275  */
 276 template<class Container,
 277          class Value = typename ValueTypeOfRange<Container>::RefType>
 278 class ReferencedSource;
 279
 280 template<class Value,
 281          class Container = std::vector<typename std::decay<Value>::type>>
 282 class CopiedSource;
 283
 284 template<class Value, class SequenceImpl>
 285 class Sequence;
 286
 287 template <class Value>
 288 class RangeImpl;
 289
 290 template <class Value, class Distance>
 291 class RangeWithStepImpl;
 292
 293 template <class Value>
 294 class SeqImpl;
 295
 296 template <class Value, class Distance>
 297 class SeqWithStepImpl;
 298
 299 template <class Value>
 300 class InfiniteImpl;
 301
 302 template<class Value, class Source>
 303 class Yield;
 304
 305 template<class Value>
 306 class Empty;
 307
 308 template<class Value>
 309 class SingleReference;
 310
 311 template<class Value>
 312 class SingleCopy;
 313
 314 /*
 315  * Operators
 316  */
 317 template<class Predicate>
 318 class Map;
 319
 320 template<class Predicate>
 321 class Filter;
 322
 323 template<class Predicate>
 324 class Until;
 325
 326 class Take;
 327
 328 class Stride;
 329
 330 template<class Rand>
 331 class Sample;
 332
 333 class Skip;
 334
 335 template<class Selector, class Comparer = Less>
 336 class Order;
 337
 338 template<class Selector>
 339 class GroupBy;
 340
 341 template<class Selector>
 342 class Distinct;
 343
 344 template<class Operators>
 345 class Composer;
 346
 347 template<class Expected>
 348 class TypeAssertion;
 349
 350 class Concat;
 351
 352 class RangeConcat;
 353
 354 template <bool forever>
 355 class Cycle;
 356
 357 class Batch;
 358
 359 class Dereference;
 360
 361 class Indirect;
 362
 363 /*
 364  * Sinks
 365  */
 366 template<class Seed,
 367          class Fold>
 368 class FoldLeft;
 369
 370 class First;
 371
 372 template <bool result>
 373 class IsEmpty;
 374
 375 template<class Reducer>
 376 class Reduce;
 377
 378 class Sum;
 379
 380 template<class Selector,
 381          class Comparer>
 382 class Min;
 383
 384 template<class Container>
 385 class Collect;
 386
 387 template<template<class, class> class Collection = std::vector,
 388          template<class> class Allocator = std::allocator>
 389 class CollectTemplate;
 390
 391 template<class Collection>
 392 class Append;
 393
 394 template<class Value>
 395 struct GeneratorBuilder;
 396
 397 template<class Needle>
 398 class Contains;
 399
 400 template<class Exception,
 401          class ErrorHandler>
 402 class GuardImpl;
 403
 404 template <class T>
 405 class UnwrapOr;
 406
 407 class Unwrap;
 408
 409 }
 410
 411 /**
 412  * Polymorphic wrapper
 413  **/
 414 template<class Value>
 415 class VirtualGen;
 416
 417 /*
 418  * Source Factories
 419  */
 420 template<class Container,
 421          class From = detail::ReferencedSource<const Container>>
 422 From fromConst(const Container& source) {
 423   return From(&source);
 424 }
 425
 426 template<class Container,
 427          class From = detail::ReferencedSource<Container>>
 428 From from(Container& source) {
 429   return From(&source);
 430 }
 431
 432 template<class Container,
 433          class Value =
 434            typename detail::ValueTypeOfRange<Container>::StorageType,
 435          class CopyOf = detail::CopiedSource<Value>>
 436 CopyOf fromCopy(Container&& source) {
 437   return CopyOf(std::forward<Container>(source));
 438 }
 439
 440 template<class Value,
 441          class From = detail::CopiedSource<Value>>
 442 From from(std::initializer_list<Value> source) {
 443   return From(source);
 444 }
 445
 446 template<class Container,
 447          class From = detail::CopiedSource<typename Container::value_type,
 448                                            Container>>
 449 From from(Container&& source) {
 450   return From(std::move(source));
 451 }
 452
 453 template<class Value, class Impl = detail::RangeImpl<Value>,
 454          class Gen = detail::Sequence<Value, Impl>>
 455 Gen range(Value begin, Value end) {
 456   return Gen{std::move(begin), Impl{std::move(end)}};
 457 }
 458
 459 template<class Value, class Distance,
 460          class Impl = detail::RangeWithStepImpl<Value, Distance>,
 461          class Gen = detail::Sequence<Value, Impl>>
 462 Gen range(Value begin, Value end, Distance step) {
 463   return Gen{std::move(begin), Impl{std::move(end), std::move(step)}};
 464 }
 465
 466 template<class Value, class Impl = detail::SeqImpl<Value>,
 467          class Gen = detail::Sequence<Value, Impl>>
 468 Gen seq(Value first, Value last) {
 469   return Gen{std::move(first), Impl{std::move(last)}};
 470 }
 471
 472 template<class Value, class Distance,
 473          class Impl = detail::SeqWithStepImpl<Value, Distance>,
 474          class Gen = detail::Sequence<Value, Impl>>
 475 Gen seq(Value first, Value last, Distance step) {
 476   return Gen{std::move(first), Impl{std::move(last), std::move(step)}};
 477 }
 478
 479 template<class Value, class Impl = detail::InfiniteImpl<Value>,
 480          class Gen = detail::Sequence<Value, Impl>>
 481 Gen seq(Value first) {
 482   return Gen{std::move(first), Impl{}};
 483 }
 484
 485 template<class Value,
 486          class Source,
 487          class Yield = detail::Yield<Value, Source>>
 488 Yield generator(Source&& source) {
 489   return Yield(std::forward<Source>(source));
 490 }
 491
 492 /*
 493  * Create inline generator, used like:
 494  *
 495  *  auto gen = GENERATOR(int) { yield(1); yield(2); };
 496  */
 497 #define GENERATOR(TYPE)                            \
 498   ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
 499    [=](const std::function<void(TYPE)>& yield)
 500
 501 /*
 502  * empty() - for producing empty sequences.
 503  */
 504 template <class Value>
 505 detail::Empty<Value> empty() {
 506   return {};
 507 }
 508
 509 template <
 510     class Value,
 511     class Just = typename std::conditional<
 512         std::is_reference<Value>::value,
 513         detail::SingleReference<typename std::remove_reference<Value>::type>,
 514         detail::SingleCopy<Value>>::type>
 515 Just just(Value&& value) {
 516   return Just(std::forward<Value>(value));
 517 }
 518
 519 /*
 520  * Operator Factories
 521  */
 522 template<class Predicate,
 523          class Map = detail::Map<Predicate>>
 524 Map mapped(Predicate pred = Predicate()) {
 525   return Map(std::move(pred));
 526 }
 527
 528 template<class Predicate,
 529          class Map = detail::Map<Predicate>>
 530 Map map(Predicate pred = Predicate()) {
 531   return Map(std::move(pred));
 532 }
 533
 534 /**
 535  * mapOp - Given a generator of generators, maps the application of the given
 536  * operator on to each inner gen. Especially useful in aggregating nested data
 537  * structures:
 538  *
 539  *   chunked(samples, 256)
 540  *     | mapOp(filter(sampleTest) | count)
 541  *     | sum;
 542  */
 543 template<class Operator,
 544          class Map = detail::Map<detail::Composer<Operator>>>
 545 Map mapOp(Operator op) {
 546   return Map(detail::Composer<Operator>(std::move(op)));
 547 }
 548
 549 /*
 550  * member(...) - For extracting a member from each value.
 551  *
 552  *  vector<string> strings = ...;
 553  *  auto sizes = from(strings) | member(&string::size);
 554  *
 555  * If a member is const overridden (like 'front()'), pass template parameter
 556  * 'Const' to select the const version, or 'Mutable' to select the non-const
 557  * version:
 558  *
 559  *  auto heads = from(strings) | member<Const>(&string::front);
 560  */
 561 enum MemberType {
 562   Const,
 563   Mutable
 564 };
 565
 566 /**
 567  * These exist because MSVC has problems with expression SFINAE in templates
 568  * assignment and comparisons don't work properly without being pulled out
 569  * of the template declaration
 570  */
 571 template <MemberType Constness> struct ExprIsConst {
 572   enum {
 573     value = Constness == Const
 574   };
 575 };
 576
 577 template <MemberType Constness> struct ExprIsMutable {
 578   enum {
 579     value = Constness == Mutable
 580   };
 581 };
 582
 583 template<MemberType Constness = Const,
 584          class Class,
 585          class Return,
 586          class Mem = ConstMemberFunction<Class, Return>,
 587          class Map = detail::Map<Mem>>
 588 typename std::enable_if<ExprIsConst<Constness>::value, Map>::type
 589 member(Return (Class::*member)() const) {
 590   return Map(Mem(member));
 591 }
 592
 593 template<MemberType Constness = Mutable,
 594          class Class,
 595          class Return,
 596          class Mem = MemberFunction<Class, Return>,
 597          class Map = detail::Map<Mem>>
 598 typename std::enable_if<ExprIsMutable<Constness>::value, Map>::type
 599 member(Return (Class::*member)()) {
 600   return Map(Mem(member));
 601 }
 602
 603 /*
 604  * field(...) - For extracting a field from each value.
 605  *
 606  *  vector<Item> items = ...;
 607  *  auto names = from(items) | field(&Item::name);
 608  *
 609  * Note that if the values of the generator are rvalues, any non-reference
 610  * fields will be rvalues as well. As an example, the code below does not copy
 611  * any strings, only moves them:
 612  *
 613  *  auto namesVector = from(items)
 614  *                   | move
 615  *                   | field(&Item::name)
 616  *                   | as<vector>();
 617  */
 618 template<class Class,
 619          class FieldType,
 620          class Field = Field<Class, FieldType>,
 621          class Map = detail::Map<Field>>
 622 Map field(FieldType Class::*field) {
 623   return Map(Field(field));
 624 }
 625
 626 template <class Predicate = Identity,
 627           class Filter = detail::Filter<Predicate>>
 628 Filter filter(Predicate pred = Predicate()) {
 629   return Filter(std::move(pred));
 630 }
 631
 632 template<class Predicate,
 633          class Until = detail::Until<Predicate>>
 634 Until until(Predicate pred = Predicate()) {
 635   return Until(std::move(pred));
 636 }
 637
 638 template<class Selector = Identity,
 639          class Comparer = Less,
 640          class Order = detail::Order<Selector, Comparer>>
 641 Order orderBy(Selector selector = Selector(),
 642               Comparer comparer = Comparer()) {
 643   return Order(std::move(selector),
 644                std::move(comparer));
 645 }
 646
 647 template<class Selector = Identity,
 648          class Order = detail::Order<Selector, Greater>>
 649 Order orderByDescending(Selector selector = Selector()) {
 650   return Order(std::move(selector));
 651 }
 652
 653 template <class Selector = Identity,
 654           class GroupBy = detail::GroupBy<Selector>>
 655 GroupBy groupBy(Selector selector = Selector()) {
 656   return GroupBy(std::move(selector));
 657 }
 658
 659 template<class Selector = Identity,
 660          class Distinct = detail::Distinct<Selector>>
 661 Distinct distinctBy(Selector selector = Selector()) {
 662   return Distinct(std::move(selector));
 663 }
 664
 665 template<int n,
 666          class Get = detail::Map<Get<n>>>
 667 Get get() {
 668   return Get();
 669 }
 670
 671 // construct Dest from each value
 672 template <class Dest,
 673           class Cast = detail::Map<Cast<Dest>>>
 674 Cast eachAs() {
 675   return Cast();
 676 }
 677
 678 // call folly::to on each value
 679 template <class Dest,
 680           class To = detail::Map<To<Dest>>>
 681 To eachTo() {
 682   return To();
 683 }
 684
 685 template<class Value>
 686 detail::TypeAssertion<Value> assert_type() {
 687   return {};
 688 }
 689
 690 /*
 691  * Sink Factories
 692  */
 693
 694 /**
 695  * any() - For determining if any value in a sequence satisfies a predicate.
 696  *
 697  * The following is an example for checking if any computer is broken:
 698  *
 699  *   bool schrepIsMad = from(computers) | any(isBroken);
 700  *
 701  * (because everyone knows Schrep hates broken computers).
 702  *
 703  * Note that if no predicate is provided, 'any()' checks if any of the values
 704  * are true when cased to bool. To check if any of the scores are nonZero:
 705  *
 706  *   bool somebodyScored = from(scores) | any();
 707  *
 708  * Note: Passing an empty sequence through 'any()' will always return false. In
 709  * fact, 'any()' is equivilent to the composition of 'filter()' and 'notEmpty'.
 710  *
 711  *   from(source) | any(pred) == from(source) | filter(pred) | notEmpty
 712  */
 713
 714 template <class Predicate = Identity,
 715           class Filter = detail::Filter<Predicate>,
 716           class NotEmpty = detail::IsEmpty<false>,
 717           class Composed = detail::Composed<Filter, NotEmpty>>
 718 Composed any(Predicate pred = Predicate()) {
 719   return Composed(Filter(std::move(pred)), NotEmpty());
 720 }
 721
 722 /**
 723  * all() - For determining whether all values in a sequence satisfy a predicate.
 724  *
 725  * The following is an example for checking if all members of a team are cool:
 726  *
 727  *   bool isAwesomeTeam = from(team) | all(isCool);
 728  *
 729  * Note that if no predicate is provided, 'all()'' checks if all of the values
 730  * are true when cased to bool.
 731  * The following makes sure none of 'pointers' are nullptr:
 732  *
 733  *   bool allNonNull = from(pointers) | all();
 734  *
 735  * Note: Passing an empty sequence through 'all()' will always return true. In
 736  * fact, 'all()' is equivilent to the composition of 'filter()' with the
 737  * reversed predicate and 'isEmpty'.
 738  *
 739  *   from(source) | all(pred) == from(source) | filter(negate(pred)) | isEmpty
 740  */
 741
 742 template <class Predicate = Identity,
 743           class Filter = detail::Filter<Negate<Predicate>>,
 744           class IsEmpty = detail::IsEmpty<true>,
 745           class Composed = detail::Composed<Filter, IsEmpty>>
 746 Composed all(Predicate pred = Predicate()) {
 747   return Composed(Filter(std::move(negate(pred))), IsEmpty());
 748 }
 749
 750 template<class Seed,
 751          class Fold,
 752          class FoldLeft = detail::FoldLeft<Seed, Fold>>
 753 FoldLeft foldl(Seed seed = Seed(),
 754                Fold fold = Fold()) {
 755   return FoldLeft(std::move(seed),
 756                   std::move(fold));
 757 }
 758
 759 template<class Reducer,
 760          class Reduce = detail::Reduce<Reducer>>
 761 Reduce reduce(Reducer reducer = Reducer()) {
 762   return Reduce(std::move(reducer));
 763 }
 764
 765 template<class Selector = Identity,
 766          class Min = detail::Min<Selector, Less>>
 767 Min minBy(Selector selector = Selector()) {
 768   return Min(std::move(selector));
 769 }
 770
 771 template<class Selector,
 772          class MaxBy = detail::Min<Selector, Greater>>
 773 MaxBy maxBy(Selector selector = Selector()) {
 774   return MaxBy(std::move(selector));
 775 }
 776
 777 template<class Collection,
 778          class Collect = detail::Collect<Collection>>
 779 Collect as() {
 780   return Collect();
 781 }
 782
 783 template<template<class, class> class Container = std::vector,
 784          template<class> class Allocator = std::allocator,
 785          class Collect = detail::CollectTemplate<Container, Allocator>>
 786 Collect as() {
 787   return Collect();
 788 }
 789
 790 template<class Collection,
 791          class Append = detail::Append<Collection>>
 792 Append appendTo(Collection& collection) {
 793   return Append(&collection);
 794 }
 795
 796 template<class Needle,
 797          class Contains = detail::Contains<typename std::decay<Needle>::type>>
 798 Contains contains(Needle&& needle) {
 799   return Contains(std::forward<Needle>(needle));
 800 }
 801
 802 template<class Exception,
 803          class ErrorHandler,
 804          class GuardImpl =
 805            detail::GuardImpl<
 806              Exception,
 807              typename std::decay<ErrorHandler>::type>>
 808 GuardImpl guard(ErrorHandler&& handler) {
 809   return GuardImpl(std::forward<ErrorHandler>(handler));
 810 }
 811
 812 template<class Fallback,
 813          class UnwrapOr = detail::UnwrapOr<typename std::decay<Fallback>::type>>
 814 UnwrapOr unwrapOr(Fallback&& fallback) {
 815   return UnwrapOr(std::forward<Fallback>(fallback));
 816 }
 817
 818 }} // folly::gen
 819
 820 #include <folly/gen/Base-inl.h>