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