folly/gen/Core-inl.h

   1 /*
   2  * Copyright 2015 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* p) {
  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   static constexpr bool infinite = false;
 185 };
 186
 187 template<class LeftValue,
 188          class Left,
 189          class RightValue,
 190          class Right,
 191          class Chain = detail::Chain<LeftValue, Left, Right>>
 192 Chain operator+(const GenImpl<LeftValue, Left>& left,
 193                 const GenImpl<RightValue, Right>& right) {
 194   static_assert(
 195     std::is_same<LeftValue, RightValue>::value,
 196     "Generators may ony be combined if Values are the exact same type.");
 197   return Chain(left.self(), right.self());
 198 }
 199
 200 template<class LeftValue,
 201          class Left,
 202          class RightValue,
 203          class Right,
 204          class Chain = detail::Chain<LeftValue, Left, Right>>
 205 Chain operator+(const GenImpl<LeftValue, Left>& left,
 206                 GenImpl<RightValue, Right>&& right) {
 207   static_assert(
 208     std::is_same<LeftValue, RightValue>::value,
 209     "Generators may ony be combined if Values are the exact same type.");
 210   return Chain(left.self(), std::move(right.self()));
 211 }
 212
 213 template<class LeftValue,
 214          class Left,
 215          class RightValue,
 216          class Right,
 217          class Chain = detail::Chain<LeftValue, Left, Right>>
 218 Chain operator+(GenImpl<LeftValue, Left>&& left,
 219                 const GenImpl<RightValue, Right>& right) {
 220   static_assert(
 221     std::is_same<LeftValue, RightValue>::value,
 222     "Generators may ony be combined if Values are the exact same type.");
 223   return Chain(std::move(left.self()), right.self());
 224 }
 225
 226 template<class LeftValue,
 227          class Left,
 228          class RightValue,
 229          class Right,
 230          class Chain = detail::Chain<LeftValue, Left, Right>>
 231 Chain operator+(GenImpl<LeftValue, Left>&& left,
 232                 GenImpl<RightValue, Right>&& right) {
 233   static_assert(
 234     std::is_same<LeftValue, RightValue>::value,
 235     "Generators may ony be combined if Values are the exact same type.");
 236   return Chain(std::move(left.self()), std::move(right.self()));
 237 }
 238
 239 /**
 240  * operator|() which enables foreach-like usage:
 241  *   gen | [](Value v) -> void {...};
 242  */
 243 template<class Value,
 244          class Gen,
 245          class Handler>
 246 typename std::enable_if<
 247   IsCompatibleSignature<Handler, void(Value)>::value>::type
 248 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 249   static_assert(!Gen::infinite,
 250                 "Cannot pull all values from an infinite sequence.");
 251   gen.self().foreach(std::forward<Handler>(handler));
 252 }
 253
 254 /**
 255  * operator|() which enables foreach-like usage with 'break' support:
 256  *   gen | [](Value v) -> bool { return shouldContinue(); };
 257  */
 258 template<class Value,
 259          class Gen,
 260          class Handler>
 261 typename std::enable_if<
 262   IsCompatibleSignature<Handler, bool(Value)>::value, bool>::type
 263 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 264   return gen.self().apply(std::forward<Handler>(handler));
 265 }
 266
 267 /**
 268  * operator|() for composing generators with operators, similar to boosts' range
 269  * adaptors:
 270  *   gen | map(square) | sum
 271  */
 272 template<class Value,
 273          class Gen,
 274          class Op>
 275 auto operator|(const GenImpl<Value, Gen>& gen, const Operator<Op>& op) ->
 276 decltype(op.self().compose(gen.self())) {
 277   return op.self().compose(gen.self());
 278 }
 279
 280 template<class Value,
 281          class Gen,
 282          class Op>
 283 auto operator|(GenImpl<Value, Gen>&& gen, const Operator<Op>& op) ->
 284 decltype(op.self().compose(std::move(gen.self()))) {
 285   return op.self().compose(std::move(gen.self()));
 286 }
 287
 288 namespace detail {
 289
 290 /**
 291  * Composed - For building up a pipeline of operations to perform, absent any
 292  * particular source generator. Useful for building up custom pipelines.
 293  *
 294  * This type is usually used by just piping two operators together:
 295  *
 296  * auto valuesOf = filter([](Optional<int>& o) { return o.hasValue(); })
 297  *               | map([](Optional<int>& o) -> int& { return o.value(); });
 298  *
 299  *  auto valuesIncluded = from(optionals) | valuesOf | as<vector>();
 300  */
 301 template<class First,
 302          class Second>
 303 class Composed : public Operator<Composed<First, Second>> {
 304   First first_;
 305   Second second_;
 306  public:
 307   Composed() {}
 308
 309   Composed(First first, Second second)
 310     : first_(std::move(first))
 311     , second_(std::move(second)) {}
 312
 313   template<class Source,
 314            class Value,
 315            class FirstRet = decltype(std::declval<First>()
 316                                      .compose(std::declval<Source>())),
 317            class SecondRet = decltype(std::declval<Second>()
 318                                       .compose(std::declval<FirstRet>()))>
 319   SecondRet compose(const GenImpl<Value, Source>& source) const {
 320     return second_.compose(first_.compose(source.self()));
 321   }
 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(GenImpl<Value, Source>&& source) const {
 330     return second_.compose(first_.compose(std::move(source.self())));
 331   }
 332 };
 333
 334 /**
 335  * Chain - For concatenating the values produced by two Generators.
 336  *
 337  * This type is primarily used through using '+' to combine generators, like:
 338  *
 339  *   auto nums = seq(1, 10) + seq(20, 30);
 340  *   int total = nums | sum;
 341  */
 342 template<class Value, class First, class Second>
 343 class Chain : public GenImpl<Value,
 344                              Chain<Value, First, Second>> {
 345   First first_;
 346   Second second_;
 347 public:
 348   explicit Chain(First first, Second second)
 349       : first_(std::move(first))
 350       , second_(std::move(second)) {}
 351
 352   template<class Handler>
 353   bool apply(Handler&& handler) const {
 354     return first_.apply(std::forward<Handler>(handler))
 355         && second_.apply(std::forward<Handler>(handler));
 356   }
 357
 358   template<class Body>
 359   void foreach(Body&& body) const {
 360     first_.foreach(std::forward<Body>(body));
 361     second_.foreach(std::forward<Body>(body));
 362   }
 363
 364   static constexpr bool infinite = First::infinite || Second::infinite;
 365 };
 366
 367 } // detail
 368
 369 }} // folly::gen
 370
 371 #pragma GCC diagnostic pop