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, class ExpectedReturn, class... ArgTypes>
  46 class IsCompatibleSignature<Candidate, ExpectedReturn(ArgTypes...)> {
  47   template <
  48       class F,
  49       class ActualReturn =
  50           decltype(std::declval<F>()(std::declval<ArgTypes>()...)),
  51       bool good = std::is_same<ExpectedReturn, ActualReturn>::value>
  52   static constexpr bool testArgs(int*) {
  53     return good;
  54   }
  55
  56   template <class F>
  57   static constexpr bool testArgs(...) {
  58     return false;
  59   }
  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, class Value, 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 <
 108     class Left,
 109     class Right,
 110     class Composed = detail::Composed<Left, Right>>
 111 Composed operator|(const Operator<Left>& left,
 112                    const Operator<Right>& right) {
 113   return Composed(left.self(), right.self());
 114 }
 115
 116 template <
 117     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 <
 126     class Left,
 127     class Right,
 128     class Composed = detail::Composed<Left, Right>>
 129 Composed operator|(Operator<Left>&& left,
 130                    const Operator<Right>& right) {
 131   return Composed(std::move(left.self()), right.self());
 132 }
 133
 134 template <
 135     class Left,
 136     class Right,
 137     class Composed = detail::Composed<Left, Right>>
 138 Composed operator|(Operator<Left>&& left,
 139                    Operator<Right>&& right) {
 140   return Composed(std::move(left.self()), std::move(right.self()));
 141 }
 142
 143 /**
 144  * GenImpl - Core abstraction of a generator, an object which produces values by
 145  * passing them to a given handler lambda. All generator implementations must
 146  * implement apply(). foreach() may also be implemented to special case the
 147  * condition where the entire sequence is consumed.
 148  */
 149 template <class Value, class Self>
 150 class GenImpl : public FBounded<Self> {
 151  protected:
 152   // To prevent slicing
 153   GenImpl() = default;
 154   GenImpl(GenImpl&&) = default;
 155   GenImpl(const GenImpl&) = default;
 156   GenImpl& operator=(GenImpl&&) = default;
 157   GenImpl& operator=(const GenImpl&) = default;
 158
 159  public:
 160   typedef Value ValueType;
 161   typedef typename std::decay<Value>::type StorageType;
 162
 163   /**
 164    * apply() - Send all values produced by this generator to given handler until
 165    * the handler returns false. Returns false if and only if the handler passed
 166    * in returns false. Note: It should return true even if it completes (without
 167    * the handler returning false), as 'Chain' uses the return value of apply to
 168    * determine if it should process the second object in its chain.
 169    */
 170   template <class Handler>
 171   bool apply(Handler&& handler) const;
 172
 173   /**
 174    * foreach() - Send all values produced by this generator to given lambda.
 175    */
 176   template <class Body>
 177   void foreach(Body&& body) const {
 178     this->self().apply([&](Value value) -> bool {
 179         static_assert(!infinite, "Cannot call foreach on infinite GenImpl");
 180         body(std::forward<Value>(value));
 181         return true;
 182       });
 183   }
 184
 185   // Child classes should override if the sequence generated is *definitely*
 186   // infinite. 'infinite' may be false_type for some infinite sequences
 187   // (due the the Halting Problem).
 188   //
 189   // In general, almost all sources are finite (only seq(n) produces an infinite
 190   // source), almost all operators keep the finiteness of the source (only cycle
 191   // makes an infinite generator from a finite one, only until and take make a
 192   // finite generator from an infinite one, and concat needs both the inner and
 193   // outer generators to be finite to make a finite one), and most sinks
 194   // cannot accept and infinite generators (first being the expection).
 195   static constexpr bool infinite = false;
 196 };
 197
 198 template <
 199     class LeftValue,
 200     class Left,
 201     class RightValue,
 202     class Right,
 203     class Chain = detail::Chain<LeftValue, Left, Right>>
 204 Chain operator+(const GenImpl<LeftValue, Left>& left,
 205                 const GenImpl<RightValue, Right>& right) {
 206   static_assert(
 207     std::is_same<LeftValue, RightValue>::value,
 208     "Generators may ony be combined if Values are the exact same type.");
 209   return Chain(left.self(), right.self());
 210 }
 211
 212 template <
 213     class LeftValue,
 214     class Left,
 215     class RightValue,
 216     class Right,
 217     class Chain = detail::Chain<LeftValue, Left, Right>>
 218 Chain operator+(const GenImpl<LeftValue, Left>& left,
 219                 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(left.self(), std::move(right.self()));
 224 }
 225
 226 template <
 227     class LeftValue,
 228     class Left,
 229     class RightValue,
 230     class Right,
 231     class Chain = detail::Chain<LeftValue, Left, Right>>
 232 Chain operator+(GenImpl<LeftValue, Left>&& left,
 233                 const GenImpl<RightValue, Right>& right) {
 234   static_assert(
 235     std::is_same<LeftValue, RightValue>::value,
 236     "Generators may ony be combined if Values are the exact same type.");
 237   return Chain(std::move(left.self()), right.self());
 238 }
 239
 240 template <
 241     class LeftValue,
 242     class Left,
 243     class RightValue,
 244     class Right,
 245     class Chain = detail::Chain<LeftValue, Left, Right>>
 246 Chain operator+(GenImpl<LeftValue, Left>&& left,
 247                 GenImpl<RightValue, Right>&& right) {
 248   static_assert(
 249     std::is_same<LeftValue, RightValue>::value,
 250     "Generators may ony be combined if Values are the exact same type.");
 251   return Chain(std::move(left.self()), std::move(right.self()));
 252 }
 253
 254 /**
 255  * operator|() which enables foreach-like usage:
 256  *   gen | [](Value v) -> void {...};
 257  */
 258 template <class Value, class Gen, class Handler>
 259 typename std::enable_if<
 260   IsCompatibleSignature<Handler, void(Value)>::value>::type
 261 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 262   static_assert(!Gen::infinite,
 263                 "Cannot pull all values from an infinite sequence.");
 264   gen.self().foreach(std::forward<Handler>(handler));
 265 }
 266
 267 /**
 268  * operator|() which enables foreach-like usage with 'break' support:
 269  *   gen | [](Value v) -> bool { return shouldContinue(); };
 270  */
 271 template <class Value, class Gen, class Handler>
 272 typename std::enable_if<
 273   IsCompatibleSignature<Handler, bool(Value)>::value, bool>::type
 274 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 275   return gen.self().apply(std::forward<Handler>(handler));
 276 }
 277
 278 /**
 279  * operator|() for composing generators with operators, similar to boosts' range
 280  * adaptors:
 281  *   gen | map(square) | sum
 282  */
 283 template <class Value, class Gen, class Op>
 284 auto operator|(const GenImpl<Value, Gen>& gen, const Operator<Op>& op) ->
 285 decltype(op.self().compose(gen.self())) {
 286   return op.self().compose(gen.self());
 287 }
 288
 289 template <class Value, class Gen, 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, class Second>
 309 class Composed : public Operator<Composed<First, Second>> {
 310   First first_;
 311   Second second_;
 312  public:
 313   Composed() = default;
 314
 315   Composed(First first, Second second)
 316     : first_(std::move(first))
 317     , second_(std::move(second)) {}
 318
 319   template <
 320       class Source,
 321       class Value,
 322       class FirstRet =
 323           decltype(std::declval<First>().compose(std::declval<Source>())),
 324       class SecondRet =
 325           decltype(std::declval<Second>().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 <
 331       class Source,
 332       class Value,
 333       class FirstRet =
 334           decltype(std::declval<First>().compose(std::declval<Source>())),
 335       class SecondRet =
 336           decltype(std::declval<Second>().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
 356  public:
 357   explicit Chain(First first, Second second)
 358       : first_(std::move(first))
 359       , second_(std::move(second)) {}
 360
 361   template <class Handler>
 362   bool apply(Handler&& handler) const {
 363     return first_.apply(std::forward<Handler>(handler))
 364         && second_.apply(std::forward<Handler>(handler));
 365   }
 366
 367   template <class Body>
 368   void foreach(Body&& body) const {
 369     first_.foreach(std::forward<Body>(body));
 370     second_.foreach(std::forward<Body>(body));
 371   }
 372
 373   static constexpr bool infinite = First::infinite || Second::infinite;
 374 };
 375
 376 } // namespace detail
 377 } // namespace gen
 378 } // namespace folly
 379
 380 FOLLY_POP_WARNING