folly/gen/Core-inl.h

   1 /*
   2  * Copyright 2017 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_CORE_H_
  18 #error This file may only be included from folly/gen/Core.h
  19 #endif
  20
  21 #include <type_traits>
  22 #include <utility>
  23
  24 #include <folly/Portability.h>
  25
  26 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
  27 FOLLY_PUSH_WARNING
  28 FOLLY_GCC_DISABLE_WARNING("-Wshadow")
  29
  30 namespace folly {
  31 namespace gen {
  32
  33 /**
  34  * IsCompatibleSignature - Trait type for testing whether a given Functor
  35  * matches an expected signature.
  36  *
  37  * Usage:
  38  *   IsCompatibleSignature<FunctorType, bool(int, float)>::value
  39  */
  40 template<class Candidate, class Expected>
  41 class IsCompatibleSignature {
  42   static constexpr bool value = false;
  43 };
  44
  45 template<class Candidate,
  46          class ExpectedReturn,
  47          class... ArgTypes>
  48 class IsCompatibleSignature<Candidate, ExpectedReturn(ArgTypes...)> {
  49   template<class F,
  50            class ActualReturn =
  51              decltype(std::declval<F>()(std::declval<ArgTypes>()...)),
  52            bool good = std::is_same<ExpectedReturn, ActualReturn>::value>
  53   static constexpr bool testArgs(int*) {
  54     return good;
  55   }
  56
  57   template<class F>
  58   static constexpr bool testArgs(...) {
  59     return false;
  60   }
  61 public:
  62   static constexpr bool value = testArgs<Candidate>(nullptr);
  63 };
  64
  65 /**
  66  * FBounded - Helper type for the curiously recurring template pattern, used
  67  * heavily here to enable inlining and obviate virtual functions
  68  */
  69 template<class Self>
  70 struct FBounded {
  71   const Self& self() const {
  72     return *static_cast<const Self*>(this);
  73   }
  74
  75   Self& self() {
  76     return *static_cast<Self*>(this);
  77   }
  78 };
  79
  80 /**
  81  * Operator - Core abstraction of an operation which may be applied to a
  82  * generator. All operators implement a method compose(), which takes a
  83  * generator and produces an output generator.
  84  */
  85 template<class Self>
  86 class Operator : public FBounded<Self> {
  87  public:
  88   /**
  89    * compose() - Must be implemented by child class to compose a new Generator
  90    * out of a given generator. This function left intentionally unimplemented.
  91    */
  92   template<class Source,
  93            class Value,
  94            class ResultGen = void>
  95   ResultGen compose(const GenImpl<Value, Source>& source) const;
  96
  97  protected:
  98   Operator() = default;
  99   Operator(Operator&&) noexcept = default;
 100   Operator(const Operator&) = default;
 101   Operator& operator=(Operator&&) noexcept = default;
 102   Operator& operator=(const Operator&) = default;
 103 };
 104
 105 /**
 106  * operator|() - For composing two operators without binding it to a
 107  * particular generator.
 108  */
 109 template<class Left,
 110          class Right,
 111          class Composed = detail::Composed<Left, Right>>
 112 Composed operator|(const Operator<Left>& left,
 113                    const Operator<Right>& right) {
 114   return Composed(left.self(), right.self());
 115 }
 116
 117 template<class Left,
 118          class Right,
 119          class Composed = detail::Composed<Left, Right>>
 120 Composed operator|(const Operator<Left>& left,
 121                    Operator<Right>&& right) {
 122   return Composed(left.self(), std::move(right.self()));
 123 }
 124
 125 template<class Left,
 126          class Right,
 127          class Composed = detail::Composed<Left, Right>>
 128 Composed operator|(Operator<Left>&& left,
 129                    const Operator<Right>& right) {
 130   return Composed(std::move(left.self()), right.self());
 131 }
 132
 133 template<class Left,
 134          class Right,
 135          class Composed = detail::Composed<Left, Right>>
 136 Composed operator|(Operator<Left>&& left,
 137                    Operator<Right>&& right) {
 138   return Composed(std::move(left.self()), std::move(right.self()));
 139 }
 140
 141 /**
 142  * GenImpl - Core abstraction of a generator, an object which produces values by
 143  * passing them to a given handler lambda. All generator implementations must
 144  * implement apply(). foreach() may also be implemented to special case the
 145  * condition where the entire sequence is consumed.
 146  */
 147 template<class Value,
 148          class Self>
 149 class GenImpl : public FBounded<Self> {
 150  protected:
 151   // To prevent slicing
 152   GenImpl() = default;
 153   GenImpl(GenImpl&&) = default;
 154   GenImpl(const GenImpl&) = default;
 155   GenImpl& operator=(GenImpl&&) = default;
 156   GenImpl& operator=(const GenImpl&) = default;
 157
 158  public:
 159   typedef Value ValueType;
 160   typedef typename std::decay<Value>::type StorageType;
 161
 162   /**
 163    * apply() - Send all values produced by this generator to given handler until
 164    * the handler returns false. Returns false if and only if the handler passed
 165    * in returns false. Note: It should return true even if it completes (without
 166    * the handler returning false), as 'Chain' uses the return value of apply to
 167    * determine if it should process the second object in its chain.
 168    */
 169   template<class Handler>
 170   bool apply(Handler&& handler) const;
 171
 172   /**
 173    * foreach() - Send all values produced by this generator to given lambda.
 174    */
 175   template<class Body>
 176   void foreach(Body&& body) const {
 177     this->self().apply([&](Value value) -> bool {
 178         static_assert(!infinite, "Cannot call foreach on infinite GenImpl");
 179         body(std::forward<Value>(value));
 180         return true;
 181       });
 182   }
 183
 184   // Child classes should override if the sequence generated is *definitely*
 185   // infinite. 'infinite' may be false_type for some infinite sequences
 186   // (due the the Halting Problem).
 187   //
 188   // In general, almost all sources are finite (only seq(n) produces an infinite
 189   // source), almost all operators keep the finiteness of the source (only cycle
 190   // makes an infinite generator from a finite one, only until and take make a
 191   // finite generator from an infinite one, and concat needs both the inner and
 192   // outer generators to be finite to make a finite one), and most sinks
 193   // cannot accept and infinite generators (first being the expection).
 194   static constexpr bool infinite = false;
 195 };
 196
 197 template<class LeftValue,
 198          class Left,
 199          class RightValue,
 200          class Right,
 201          class Chain = detail::Chain<LeftValue, Left, Right>>
 202 Chain operator+(const GenImpl<LeftValue, Left>& left,
 203                 const GenImpl<RightValue, Right>& right) {
 204   static_assert(
 205     std::is_same<LeftValue, RightValue>::value,
 206     "Generators may ony be combined if Values are the exact same type.");
 207   return Chain(left.self(), right.self());
 208 }
 209
 210 template<class LeftValue,
 211          class Left,
 212          class RightValue,
 213          class Right,
 214          class Chain = detail::Chain<LeftValue, Left, Right>>
 215 Chain operator+(const GenImpl<LeftValue, Left>& left,
 216                 GenImpl<RightValue, Right>&& right) {
 217   static_assert(
 218     std::is_same<LeftValue, RightValue>::value,
 219     "Generators may ony be combined if Values are the exact same type.");
 220   return Chain(left.self(), std::move(right.self()));
 221 }
 222
 223 template<class LeftValue,
 224          class Left,
 225          class RightValue,
 226          class Right,
 227          class Chain = detail::Chain<LeftValue, Left, Right>>
 228 Chain operator+(GenImpl<LeftValue, Left>&& left,
 229                 const GenImpl<RightValue, Right>& right) {
 230   static_assert(
 231     std::is_same<LeftValue, RightValue>::value,
 232     "Generators may ony be combined if Values are the exact same type.");
 233   return Chain(std::move(left.self()), right.self());
 234 }
 235
 236 template<class LeftValue,
 237          class Left,
 238          class RightValue,
 239          class Right,
 240          class Chain = detail::Chain<LeftValue, Left, Right>>
 241 Chain operator+(GenImpl<LeftValue, Left>&& left,
 242                 GenImpl<RightValue, Right>&& right) {
 243   static_assert(
 244     std::is_same<LeftValue, RightValue>::value,
 245     "Generators may ony be combined if Values are the exact same type.");
 246   return Chain(std::move(left.self()), std::move(right.self()));
 247 }
 248
 249 /**
 250  * operator|() which enables foreach-like usage:
 251  *   gen | [](Value v) -> void {...};
 252  */
 253 template<class Value,
 254          class Gen,
 255          class Handler>
 256 typename std::enable_if<
 257   IsCompatibleSignature<Handler, void(Value)>::value>::type
 258 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 259   static_assert(!Gen::infinite,
 260                 "Cannot pull all values from an infinite sequence.");
 261   gen.self().foreach(std::forward<Handler>(handler));
 262 }
 263
 264 /**
 265  * operator|() which enables foreach-like usage with 'break' support:
 266  *   gen | [](Value v) -> bool { return shouldContinue(); };
 267  */
 268 template<class Value,
 269          class Gen,
 270          class Handler>
 271 typename std::enable_if<
 272   IsCompatibleSignature<Handler, bool(Value)>::value, bool>::type
 273 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 274   return gen.self().apply(std::forward<Handler>(handler));
 275 }
 276
 277 /**
 278  * operator|() for composing generators with operators, similar to boosts' range
 279  * adaptors:
 280  *   gen | map(square) | sum
 281  */
 282 template<class Value,
 283          class Gen,
 284          class Op>
 285 auto operator|(const GenImpl<Value, Gen>& gen, const Operator<Op>& op) ->
 286 decltype(op.self().compose(gen.self())) {
 287   return op.self().compose(gen.self());
 288 }
 289
 290 template<class Value,
 291          class Gen,
 292          class Op>
 293 auto operator|(GenImpl<Value, Gen>&& gen, const Operator<Op>& op) ->
 294 decltype(op.self().compose(std::move(gen.self()))) {
 295   return op.self().compose(std::move(gen.self()));
 296 }
 297
 298 namespace detail {
 299
 300 /**
 301  * Composed - For building up a pipeline of operations to perform, absent any
 302  * particular source generator. Useful for building up custom pipelines.
 303  *
 304  * This type is usually used by just piping two operators together:
 305  *
 306  * auto valuesOf = filter([](Optional<int>& o) { return o.hasValue(); })
 307  *               | map([](Optional<int>& o) -> int& { return o.value(); });
 308  *
 309  *  auto valuesIncluded = from(optionals) | valuesOf | as<vector>();
 310  */
 311 template<class First,
 312          class Second>
 313 class Composed : public Operator<Composed<First, Second>> {
 314   First first_;
 315   Second second_;
 316  public:
 317   Composed() = default;
 318
 319   Composed(First first, Second second)
 320     : first_(std::move(first))
 321     , second_(std::move(second)) {}
 322
 323   template<class Source,
 324            class Value,
 325            class FirstRet = decltype(std::declval<First>()
 326                                      .compose(std::declval<Source>())),
 327            class SecondRet = decltype(std::declval<Second>()
 328                                       .compose(std::declval<FirstRet>()))>
 329   SecondRet compose(const GenImpl<Value, Source>& source) const {
 330     return second_.compose(first_.compose(source.self()));
 331   }
 332
 333   template<class Source,
 334            class Value,
 335            class FirstRet = decltype(std::declval<First>()
 336                                      .compose(std::declval<Source>())),
 337            class SecondRet = decltype(std::declval<Second>()
 338                                       .compose(std::declval<FirstRet>()))>
 339   SecondRet compose(GenImpl<Value, Source>&& source) const {
 340     return second_.compose(first_.compose(std::move(source.self())));
 341   }
 342 };
 343
 344 /**
 345  * Chain - For concatenating the values produced by two Generators.
 346  *
 347  * This type is primarily used through using '+' to combine generators, like:
 348  *
 349  *   auto nums = seq(1, 10) + seq(20, 30);
 350  *   int total = nums | sum;
 351  */
 352 template<class Value, class First, class Second>
 353 class Chain : public GenImpl<Value,
 354                              Chain<Value, First, Second>> {
 355   First first_;
 356   Second second_;
 357 public:
 358   explicit Chain(First first, Second second)
 359       : first_(std::move(first))
 360       , second_(std::move(second)) {}
 361
 362   template<class Handler>
 363   bool apply(Handler&& handler) const {
 364     return first_.apply(std::forward<Handler>(handler))
 365         && second_.apply(std::forward<Handler>(handler));
 366   }
 367
 368   template<class Body>
 369   void foreach(Body&& body) const {
 370     first_.foreach(std::forward<Body>(body));
 371     second_.foreach(std::forward<Body>(body));
 372   }
 373
 374   static constexpr bool infinite = First::infinite || Second::infinite;
 375 };
 376
 377 } // detail
 378 } // gen
 379 } // folly
 380
 381 FOLLY_POP_WARNING