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