folly/experimental/Gen.h

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