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
  25 #include "folly/Range.h"
  26 #include "folly/Optional.h"
  27 #include "folly/Conv.h"
  28
  29 /**
  30  * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ
  31  * @author Tom Jackson <tjackson@fb.com>
  32  *
  33  * This library makes it possible to write declarative comprehensions for
  34  * processing sequences of values efficiently in C++. The operators should be
  35  * familiar to those with experience in functional programming, and the
  36  * performance will be virtually identical to the equivalent, boilerplate C++
  37  * implementations.
  38  *
  39  * Generator objects may be created from either an stl-like container (anything
  40  * supporting begin() and end()), from sequences of values, or from another
  41  * generator (see below). To create a generator that pulls values from a vector,
  42  * for example, one could write:
  43  *
  44  *   vector<string> names { "Jack", "Jill", "Sara", "Tom" };
  45  *   auto gen = from(names);
  46  *
  47  * Generators are composed by building new generators out of old ones through
  48  * the use of operators. These are reminicent of shell pipelines, and afford
  49  * similar composition. Lambda functions are used liberally to describe how to
  50  * handle individual values:
  51  *
  52  *   auto lengths = gen
  53  *                | mapped([](const fbstring& name) { return name.size(); });
  54  *
  55  * Generators are lazy; they don't actually perform any work until they need to.
  56  * As an example, the 'lengths' generator (above) won't actually invoke the
  57  * provided lambda until values are needed:
  58  *
  59  *   auto lengthVector = lengths | as<std::vector>();
  60  *   auto totalLength = lengths | sum;
  61  *
  62  * 'auto' is useful in here because the actual types of the generators objects
  63  * are usually complicated and implementation-sensitive.
  64  *
  65  * If a simpler type is desired (for returning, as an example), VirtualGen<T>
  66  * may be used to wrap the generator in a polymorphic wrapper:
  67  *
  68  *  VirtualGen<float> powersOfE() {
  69  *    return seq(1) | mapped(&expf);
  70  *  }
  71  *
  72  * To learn more about this library, including the use of infinite generators,
  73  * see the examples in the comments, or the docs (coming soon).
  74 */
  75
  76 namespace folly { namespace gen {
  77
  78 template<class Value, class Self>
  79 class GenImpl;
  80
  81 template<class Self>
  82 class Operator;
  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 class Move {
 122 public:
 123   template<class Value>
 124   auto operator()(Value&& value) const ->
 125   decltype(std::move(std::forward<Value>(value))) {
 126     return std::move(std::forward<Value>(value));
 127   }
 128 };
 129
 130 class Identity {
 131 public:
 132   template<class Value>
 133   auto operator()(Value&& value) const ->
 134   decltype(std::forward<Value>(value)) {
 135     return std::forward<Value>(value);
 136   }
 137 };
 138
 139 template <class Dest>
 140 class Cast {
 141  public:
 142   template <class Value>
 143   Dest operator()(Value&& value) const {
 144     return Dest(std::forward<Value>(value));
 145   }
 146 };
 147
 148 template <class Dest>
 149 class To {
 150  public:
 151   template <class Value>
 152   Dest operator()(Value&& value) const {
 153     return ::folly::to<Dest>(std::forward<Value>(value));
 154   }
 155 };
 156
 157 namespace detail {
 158
 159 template<class Self>
 160 struct FBounded;
 161
 162 /*
 163  * Type Traits
 164  */
 165 template<class Container>
 166 struct ValueTypeOfRange {
 167  private:
 168   static Container container_;
 169  public:
 170   typedef decltype(*std::begin(container_))
 171     RefType;
 172   typedef typename std::decay<decltype(*std::begin(container_))>::type
 173     StorageType;
 174 };
 175
 176
 177 /*
 178  * Sources
 179  */
 180 template<class Container,
 181          class Value = typename ValueTypeOfRange<Container>::RefType>
 182 class ReferencedSource;
 183
 184 template<class Value,
 185          class Container = std::vector<typename std::decay<Value>::type>>
 186 class CopiedSource;
 187
 188 template<class Value, bool endless = false, bool endInclusive = false>
 189 class Sequence;
 190
 191 template<class Value, class First, class Second>
 192 class Chain;
 193
 194 template<class Value, class Source>
 195 class Yield;
 196
 197 /*
 198  * Operators
 199  */
 200 template<class Predicate>
 201 class Map;
 202
 203 template<class Predicate>
 204 class Filter;
 205
 206 template<class Predicate>
 207 class Until;
 208
 209 class Take;
 210
 211 class Skip;
 212
 213 template<class Selector, class Comparer = Less>
 214 class Order;
 215
 216 template<class First, class Second>
 217 class Composed;
 218
 219 /*
 220  * Sinks
 221  */
 222 template<class Seed,
 223          class Fold>
 224 class FoldLeft;
 225
 226 class First;
 227
 228 class Any;
 229
 230 template<class Predicate>
 231 class All;
 232
 233 template<class Reducer>
 234 class Reduce;
 235
 236 class Sum;
 237
 238 template<class Selector,
 239          class Comparer>
 240 class Min;
 241
 242 template<class Container>
 243 class Collect;
 244
 245 template<template<class, class> class Collection = std::vector,
 246          template<class> class Allocator = std::allocator>
 247 class CollectTemplate;
 248
 249 template<class Collection>
 250 class Append;
 251
 252 template<class Value>
 253 class GeneratorBuilder;
 254
 255 template<class Needle>
 256 class Contains;
 257
 258 }
 259
 260 /**
 261  * Polymorphic wrapper
 262  **/
 263 template<class Value>
 264 class VirtualGen;
 265
 266 /*
 267  * Source Factories
 268  */
 269 template<class Container,
 270          class From = detail::ReferencedSource<const Container>>
 271 From fromConst(const Container& source) {
 272   return From(&source);
 273 }
 274
 275 template<class Container,
 276          class From = detail::ReferencedSource<Container>>
 277 From from(Container& source) {
 278   return From(&source);
 279 }
 280
 281 template<class Container,
 282          class Value =
 283            typename detail::ValueTypeOfRange<Container>::StorageType,
 284          class CopyOf = detail::CopiedSource<Value>>
 285 CopyOf fromCopy(Container&& source) {
 286   return CopyOf(std::forward<Container>(source));
 287 }
 288
 289 template<class Value,
 290          class From = detail::CopiedSource<Value>>
 291 From from(std::initializer_list<Value> source) {
 292   return From(source);
 293 }
 294
 295 template<class Container,
 296          class From = detail::CopiedSource<typename Container::value_type,
 297                                          Container>>
 298 From from(Container&& source) {
 299   return From(std::move(source));
 300 }
 301
 302 template<class Value, class Gen = detail::Sequence<Value, false, false>>
 303 Gen range(Value begin, Value end) {
 304   return Gen(begin, end);
 305 }
 306
 307 template<class Value,
 308          class Gen = detail::Sequence<Value, false, true>>
 309 Gen seq(Value first, Value last) {
 310   return Gen(first, last);
 311 }
 312
 313 template<class Value,
 314          class Gen = detail::Sequence<Value, true>>
 315 Gen seq(Value begin) {
 316   return Gen(begin);
 317 }
 318
 319 template<class Value,
 320          class Source,
 321          class Yield = detail::Yield<Value, Source>>
 322 Yield generator(Source&& source) {
 323   return Yield(std::forward<Source>(source));
 324 }
 325
 326 /*
 327  * Create inline generator, used like:
 328  *
 329  * auto gen = GENERATOR(int) { yield(1); yield(2); };
 330  */
 331 #define GENERATOR(TYPE)                            \
 332   ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
 333    [=](const std::function<void(TYPE)>& yield)
 334
 335 /*
 336  * Operator Factories
 337  */
 338 template<class Predicate,
 339          class Map = detail::Map<Predicate>>
 340 Map mapped(Predicate pred = Predicate()) {
 341   return Map(std::move(pred));
 342 }
 343
 344 template<class Predicate,
 345          class Map = detail::Map<Predicate>>
 346 Map map(Predicate pred = Predicate()) {
 347   return Map(std::move(pred));
 348 }
 349
 350 template<class Predicate,
 351          class Filter = detail::Filter<Predicate>>
 352 Filter filter(Predicate pred = Predicate()) {
 353   return Filter(std::move(pred));
 354 }
 355
 356 template<class Predicate,
 357          class All = detail::All<Predicate>>
 358 All all(Predicate pred = Predicate()) {
 359   return All(std::move(pred));
 360 }
 361
 362 template<class Predicate,
 363          class Until = detail::Until<Predicate>>
 364 Until until(Predicate pred = Predicate()) {
 365   return Until(std::move(pred));
 366 }
 367
 368 template<class Selector,
 369          class Comparer = Less,
 370          class Order = detail::Order<Selector, Comparer>>
 371 Order orderBy(Selector selector = Identity(),
 372               Comparer comparer = Comparer()) {
 373   return Order(std::move(selector),
 374                std::move(comparer));
 375 }
 376
 377 template<class Selector,
 378          class Order = detail::Order<Selector, Greater>>
 379 Order orderByDescending(Selector selector = Identity()) {
 380   return Order(std::move(selector));
 381 }
 382
 383 template<int n,
 384          class Get = detail::Map<Get<n>>>
 385 Get get() {
 386   return Get();
 387 }
 388
 389 // construct Dest from each value
 390 template <class Dest,
 391           class Cast = detail::Map<Cast<Dest>>>
 392 Cast eachAs() {
 393   return Cast();
 394 }
 395
 396 // call folly::to on each value
 397 template <class Dest,
 398           class To = detail::Map<To<Dest>>>
 399 To eachTo() {
 400   return To();
 401 }
 402
 403 /*
 404  * Sink Factories
 405  */
 406 template<class Seed,
 407          class Fold,
 408          class FoldLeft = detail::FoldLeft<Seed, Fold>>
 409 FoldLeft foldl(Seed seed = Seed(),
 410                Fold fold = Fold()) {
 411   return FoldLeft(std::move(seed),
 412                   std::move(fold));
 413 }
 414
 415 template<class Reducer,
 416          class Reduce = detail::Reduce<Reducer>>
 417 Reduce reduce(Reducer reducer = Reducer()) {
 418   return Reduce(std::move(reducer));
 419 }
 420
 421 template<class Selector = Identity,
 422          class Min = detail::Min<Selector, Less>>
 423 Min minBy(Selector selector = Selector()) {
 424   return Min(std::move(selector));
 425 }
 426
 427 template<class Selector,
 428          class MaxBy = detail::Min<Selector, Greater>>
 429 MaxBy maxBy(Selector selector = Selector()) {
 430   return MaxBy(std::move(selector));
 431 }
 432
 433 template<class Collection,
 434          class Collect = detail::Collect<Collection>>
 435 Collect as() {
 436   return Collect();
 437 }
 438
 439 template<template<class, class> class Container = std::vector,
 440          template<class> class Allocator = std::allocator,
 441          class Collect = detail::CollectTemplate<Container, Allocator>>
 442 Collect as() {
 443   return Collect();
 444 }
 445
 446 template<class Collection,
 447          class Append = detail::Append<Collection>>
 448 Append appendTo(Collection& collection) {
 449   return Append(&collection);
 450 }
 451
 452 template<class Needle,
 453          class Contains = detail::Contains<typename std::decay<Needle>::type>>
 454 Contains contains(Needle&& needle) {
 455   return Contains(std::forward<Needle>(needle));
 456 }
 457
 458 }} // folly::gen
 459
 460 #include "folly/experimental/Gen-inl.h"