folly/gen/Base.h

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