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 template <class Dest>
 219 class Cast {
 220  public:
 221   template <class Value>
 222   Dest operator()(Value&& value) const {
 223     return Dest(std::forward<Value>(value));
 224   }
 225 };
 226
 227 template <class Dest>
 228 class To {
 229  public:
 230   template <class Value>
 231   Dest operator()(Value&& value) const {
 232     return ::folly::to<Dest>(std::forward<Value>(value));
 233   }
 234 };
 235
 236 // Specialization to allow String->StringPiece conversion
 237 template <>
 238 class To<StringPiece> {
 239  public:
 240   StringPiece operator()(StringPiece src) const {
 241     return src;
 242   }
 243 };
 244
 245 template<class Key, class Value>
 246 class Group;
 247
 248 namespace detail {
 249
 250 template<class Self>
 251 struct FBounded;
 252
 253 /*
 254  * Type Traits
 255  */
 256 template<class Container>
 257 struct ValueTypeOfRange {
 258  private:
 259   static Container container_;
 260  public:
 261   typedef decltype(*std::begin(container_))
 262     RefType;
 263   typedef typename std::decay<decltype(*std::begin(container_))>::type
 264     StorageType;
 265 };
 266
 267
 268 /*
 269  * Sources
 270  */
 271 template<class Container,
 272          class Value = typename ValueTypeOfRange<Container>::RefType>
 273 class ReferencedSource;
 274
 275 template<class Value,
 276          class Container = std::vector<typename std::decay<Value>::type>>
 277 class CopiedSource;
 278
 279 template<class Value, class SequenceImpl>
 280 class Sequence;
 281
 282 template <class Value>
 283 class RangeImpl;
 284
 285 template <class Value, class Distance>
 286 class RangeWithStepImpl;
 287
 288 template <class Value>
 289 class SeqImpl;
 290
 291 template <class Value, class Distance>
 292 class SeqWithStepImpl;
 293
 294 template <class Value>
 295 class InfiniteImpl;
 296
 297 template<class Value, class Source>
 298 class Yield;
 299
 300 template<class Value>
 301 class Empty;
 302
 303 template<class Value>
 304 class SingleReference;
 305
 306 template<class Value>
 307 class SingleCopy;
 308
 309 /*
 310  * Operators
 311  */
 312 template<class Predicate>
 313 class Map;
 314
 315 template<class Predicate>
 316 class Filter;
 317
 318 template<class Predicate>
 319 class Until;
 320
 321 class Take;
 322
 323 class Stride;
 324
 325 template<class Rand>
 326 class Sample;
 327
 328 class Skip;
 329
 330 template<class Selector, class Comparer = Less>
 331 class Order;
 332
 333 template<class Selector>
 334 class GroupBy;
 335
 336 template<class Selector>
 337 class Distinct;
 338
 339 template<class Operators>
 340 class Composer;
 341
 342 template<class Expected>
 343 class TypeAssertion;
 344
 345 class Concat;
 346
 347 class RangeConcat;
 348
 349 class Cycle;
 350
 351 class Batch;
 352
 353 class Dereference;
 354
 355 class Indirect;
 356
 357 /*
 358  * Sinks
 359  */
 360 template<class Seed,
 361          class Fold>
 362 class FoldLeft;
 363
 364 class First;
 365
 366 class Any;
 367
 368 template<class Predicate>
 369 class All;
 370
 371 template<class Reducer>
 372 class Reduce;
 373
 374 class Sum;
 375
 376 template<class Selector,
 377          class Comparer>
 378 class Min;
 379
 380 template<class Container>
 381 class Collect;
 382
 383 template<template<class, class> class Collection = std::vector,
 384          template<class> class Allocator = std::allocator>
 385 class CollectTemplate;
 386
 387 template<class Collection>
 388 class Append;
 389
 390 template<class Value>
 391 struct GeneratorBuilder;
 392
 393 template<class Needle>
 394 class Contains;
 395
 396 template<class Exception,
 397          class ErrorHandler>
 398 class GuardImpl;
 399
 400 }
 401
 402 /**
 403  * Polymorphic wrapper
 404  **/
 405 template<class Value>
 406 class VirtualGen;
 407
 408 /*
 409  * Source Factories
 410  */
 411 template<class Container,
 412          class From = detail::ReferencedSource<const Container>>
 413 From fromConst(const Container& source) {
 414   return From(&source);
 415 }
 416
 417 template<class Container,
 418          class From = detail::ReferencedSource<Container>>
 419 From from(Container& source) {
 420   return From(&source);
 421 }
 422
 423 template<class Container,
 424          class Value =
 425            typename detail::ValueTypeOfRange<Container>::StorageType,
 426          class CopyOf = detail::CopiedSource<Value>>
 427 CopyOf fromCopy(Container&& source) {
 428   return CopyOf(std::forward<Container>(source));
 429 }
 430
 431 template<class Value,
 432          class From = detail::CopiedSource<Value>>
 433 From from(std::initializer_list<Value> source) {
 434   return From(source);
 435 }
 436
 437 template<class Container,
 438          class From = detail::CopiedSource<typename Container::value_type,
 439                                            Container>>
 440 From from(Container&& source) {
 441   return From(std::move(source));
 442 }
 443
 444 template<class Value, class Impl = detail::RangeImpl<Value>,
 445          class Gen = detail::Sequence<Value, Impl>>
 446 Gen range(Value begin, Value end) {
 447   return Gen{std::move(begin), Impl{std::move(end)}};
 448 }
 449
 450 template<class Value, class Distance,
 451          class Impl = detail::RangeWithStepImpl<Value, Distance>,
 452          class Gen = detail::Sequence<Value, Impl>>
 453 Gen range(Value begin, Value end, Distance step) {
 454   return Gen{std::move(begin), Impl{std::move(end), std::move(step)}};
 455 }
 456
 457 template<class Value, class Impl = detail::SeqImpl<Value>,
 458          class Gen = detail::Sequence<Value, Impl>>
 459 Gen seq(Value first, Value last) {
 460   return Gen{std::move(first), Impl{std::move(last)}};
 461 }
 462
 463 template<class Value, class Distance,
 464          class Impl = detail::SeqWithStepImpl<Value, Distance>,
 465          class Gen = detail::Sequence<Value, Impl>>
 466 Gen seq(Value first, Value last, Distance step) {
 467   return Gen{std::move(first), Impl{std::move(last), std::move(step)}};
 468 }
 469
 470 template<class Value, class Impl = detail::InfiniteImpl<Value>,
 471          class Gen = detail::Sequence<Value, Impl>>
 472 Gen seq(Value first) {
 473   return Gen{std::move(first), Impl{}};
 474 }
 475
 476 template<class Value,
 477          class Source,
 478          class Yield = detail::Yield<Value, Source>>
 479 Yield generator(Source&& source) {
 480   return Yield(std::forward<Source>(source));
 481 }
 482
 483 /*
 484  * Create inline generator, used like:
 485  *
 486  *  auto gen = GENERATOR(int) { yield(1); yield(2); };
 487  */
 488 #define GENERATOR(TYPE)                            \
 489   ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
 490    [=](const std::function<void(TYPE)>& yield)
 491
 492 /*
 493  * empty() - for producing empty sequences.
 494  */
 495 template <class Value>
 496 detail::Empty<Value> empty() {
 497   return {};
 498 }
 499
 500 template <
 501     class Value,
 502     class Just = typename std::conditional<
 503         std::is_reference<Value>::value,
 504         detail::SingleReference<typename std::remove_reference<Value>::type>,
 505         detail::SingleCopy<Value>>::type>
 506 Just just(Value&& value) {
 507   return Just(std::forward<Value>(value));
 508 }
 509
 510 /*
 511  * Operator Factories
 512  */
 513 template<class Predicate,
 514          class Map = detail::Map<Predicate>>
 515 Map mapped(Predicate pred = Predicate()) {
 516   return Map(std::move(pred));
 517 }
 518
 519 template<class Predicate,
 520          class Map = detail::Map<Predicate>>
 521 Map map(Predicate pred = Predicate()) {
 522   return Map(std::move(pred));
 523 }
 524
 525 /**
 526  * mapOp - Given a generator of generators, maps the application of the given
 527  * operator on to each inner gen. Especially useful in aggregating nested data
 528  * structures:
 529  *
 530  *   chunked(samples, 256)
 531  *     | mapOp(filter(sampleTest) | count)
 532  *     | sum;
 533  */
 534 template<class Operator,
 535          class Map = detail::Map<detail::Composer<Operator>>>
 536 Map mapOp(Operator op) {
 537   return Map(detail::Composer<Operator>(std::move(op)));
 538 }
 539
 540 /*
 541  * member(...) - For extracting a member from each value.
 542  *
 543  *  vector<string> strings = ...;
 544  *  auto sizes = from(strings) | member(&string::size);
 545  *
 546  * If a member is const overridden (like 'front()'), pass template parameter
 547  * 'Const' to select the const version, or 'Mutable' to select the non-const
 548  * version:
 549  *
 550  *  auto heads = from(strings) | member<Const>(&string::front);
 551  */
 552 enum MemberType {
 553   Const,
 554   Mutable
 555 };
 556
 557 /**
 558  * These exist because MSVC has problems with expression SFINAE in templates
 559  * assignment and comparisons don't work properly without being pulled out
 560  * of the template declaration
 561  */
 562 template <MemberType Constness> struct ExprIsConst {
 563   enum {
 564     value = Constness == Const
 565   };
 566 };
 567
 568 template <MemberType Constness> struct ExprIsMutable {
 569   enum {
 570     value = Constness == Mutable
 571   };
 572 };
 573
 574 template<MemberType Constness = Const,
 575          class Class,
 576          class Return,
 577          class Mem = ConstMemberFunction<Class, Return>,
 578          class Map = detail::Map<Mem>>
 579 typename std::enable_if<ExprIsConst<Constness>::value, Map>::type
 580 member(Return (Class::*member)() const) {
 581   return Map(Mem(member));
 582 }
 583
 584 template<MemberType Constness = Mutable,
 585          class Class,
 586          class Return,
 587          class Mem = MemberFunction<Class, Return>,
 588          class Map = detail::Map<Mem>>
 589 typename std::enable_if<ExprIsMutable<Constness>::value, Map>::type
 590 member(Return (Class::*member)()) {
 591   return Map(Mem(member));
 592 }
 593
 594 /*
 595  * field(...) - For extracting a field from each value.
 596  *
 597  *  vector<Item> items = ...;
 598  *  auto names = from(items) | field(&Item::name);
 599  *
 600  * Note that if the values of the generator are rvalues, any non-reference
 601  * fields will be rvalues as well. As an example, the code below does not copy
 602  * any strings, only moves them:
 603  *
 604  *  auto namesVector = from(items)
 605  *                   | move
 606  *                   | field(&Item::name)
 607  *                   | as<vector>();
 608  */
 609 template<class Class,
 610          class FieldType,
 611          class Field = Field<Class, FieldType>,
 612          class Map = detail::Map<Field>>
 613 Map field(FieldType Class::*field) {
 614   return Map(Field(field));
 615 }
 616
 617 template <class Predicate = Identity,
 618           class Filter = detail::Filter<Predicate>>
 619 Filter filter(Predicate pred = Predicate()) {
 620   return Filter(std::move(pred));
 621 }
 622
 623 template<class Predicate,
 624          class All = detail::All<Predicate>>
 625 All all(Predicate pred = Predicate()) {
 626   return All(std::move(pred));
 627 }
 628
 629 template<class Predicate,
 630          class Until = detail::Until<Predicate>>
 631 Until until(Predicate pred = Predicate()) {
 632   return Until(std::move(pred));
 633 }
 634
 635 template<class Selector = Identity,
 636          class Comparer = Less,
 637          class Order = detail::Order<Selector, Comparer>>
 638 Order orderBy(Selector selector = Selector(),
 639               Comparer comparer = Comparer()) {
 640   return Order(std::move(selector),
 641                std::move(comparer));
 642 }
 643
 644 template<class Selector = Identity,
 645          class Order = detail::Order<Selector, Greater>>
 646 Order orderByDescending(Selector selector = Selector()) {
 647   return Order(std::move(selector));
 648 }
 649
 650 template<class Selector,
 651          class GroupBy = detail::GroupBy<Selector>>
 652 GroupBy groupBy(Selector selector = Identity()) {
 653   return GroupBy(std::move(selector));
 654 }
 655
 656 template<class Selector = Identity,
 657          class Distinct = detail::Distinct<Selector>>
 658 Distinct distinctBy(Selector selector = Selector()) {
 659   return Distinct(std::move(selector));
 660 }
 661
 662 template<int n,
 663          class Get = detail::Map<Get<n>>>
 664 Get get() {
 665   return Get();
 666 }
 667
 668 // construct Dest from each value
 669 template <class Dest,
 670           class Cast = detail::Map<Cast<Dest>>>
 671 Cast eachAs() {
 672   return Cast();
 673 }
 674
 675 // call folly::to on each value
 676 template <class Dest,
 677           class To = detail::Map<To<Dest>>>
 678 To eachTo() {
 679   return To();
 680 }
 681
 682 template<class Value>
 683 detail::TypeAssertion<Value> assert_type() {
 684   return {};
 685 }
 686
 687 /*
 688  * Sink Factories
 689  */
 690 template<class Seed,
 691          class Fold,
 692          class FoldLeft = detail::FoldLeft<Seed, Fold>>
 693 FoldLeft foldl(Seed seed = Seed(),
 694                Fold fold = Fold()) {
 695   return FoldLeft(std::move(seed),
 696                   std::move(fold));
 697 }
 698
 699 template<class Reducer,
 700          class Reduce = detail::Reduce<Reducer>>
 701 Reduce reduce(Reducer reducer = Reducer()) {
 702   return Reduce(std::move(reducer));
 703 }
 704
 705 template<class Selector = Identity,
 706          class Min = detail::Min<Selector, Less>>
 707 Min minBy(Selector selector = Selector()) {
 708   return Min(std::move(selector));
 709 }
 710
 711 template<class Selector,
 712          class MaxBy = detail::Min<Selector, Greater>>
 713 MaxBy maxBy(Selector selector = Selector()) {
 714   return MaxBy(std::move(selector));
 715 }
 716
 717 template<class Collection,
 718          class Collect = detail::Collect<Collection>>
 719 Collect as() {
 720   return Collect();
 721 }
 722
 723 template<template<class, class> class Container = std::vector,
 724          template<class> class Allocator = std::allocator,
 725          class Collect = detail::CollectTemplate<Container, Allocator>>
 726 Collect as() {
 727   return Collect();
 728 }
 729
 730 template<class Collection,
 731          class Append = detail::Append<Collection>>
 732 Append appendTo(Collection& collection) {
 733   return Append(&collection);
 734 }
 735
 736 template<class Needle,
 737          class Contains = detail::Contains<typename std::decay<Needle>::type>>
 738 Contains contains(Needle&& needle) {
 739   return Contains(std::forward<Needle>(needle));
 740 }
 741
 742 template<class Exception,
 743          class ErrorHandler,
 744          class GuardImpl =
 745            detail::GuardImpl<
 746              Exception,
 747              typename std::decay<ErrorHandler>::type>>
 748 GuardImpl guard(ErrorHandler&& handler) {
 749   return GuardImpl(std::forward<ErrorHandler>(handler));
 750 }
 751
 752 }} // folly::gen
 753
 754 #include <folly/gen/Base-inl.h>
 755
 756 #endif // FOLLY_GEN_BASE_H