folly/gen/Core-inl.h

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