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