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