folly/gen/Base.h

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