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 public:
  61   static constexpr bool value = testArgs<Candidate>(nullptr);
  62 };
  63
  64 /**
  65  * FBounded - Helper type for the curiously recurring template pattern, used
  66  * heavily here to enable inlining and obviate virtual functions
  67  */
  68 template <class Self>
  69 struct FBounded {
  70   const Self& self() const {
  71     return *static_cast<const Self*>(this);
  72   }
  73
  74   Self& self() {
  75     return *static_cast<Self*>(this);
  76   }
  77 };
  78
  79 /**
  80  * Operator - Core abstraction of an operation which may be applied to a
  81  * generator. All operators implement a method compose(), which takes a
  82  * generator and produces an output generator.
  83  */
  84 template <class Self>
  85 class Operator : public FBounded<Self> {
  86  public:
  87   /**
  88    * compose() - Must be implemented by child class to compose a new Generator
  89    * out of a given generator. This function left intentionally unimplemented.
  90    */
  91   template <class Source, class Value, 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 <
 107     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 <
 116     class Left,
 117     class Right,
 118     class Composed = detail::Composed<Left, Right>>
 119 Composed operator|(const Operator<Left>& left,
 120                    Operator<Right>&& right) {
 121   return Composed(left.self(), std::move(right.self()));
 122 }
 123
 124 template <
 125     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 <
 134     class Left,
 135     class Right,
 136     class Composed = detail::Composed<Left, Right>>
 137 Composed operator|(Operator<Left>&& left,
 138                    Operator<Right>&& right) {
 139   return Composed(std::move(left.self()), std::move(right.self()));
 140 }
 141
 142 /**
 143  * GenImpl - Core abstraction of a generator, an object which produces values by
 144  * passing them to a given handler lambda. All generator implementations must
 145  * implement apply(). foreach() may also be implemented to special case the
 146  * condition where the entire sequence is consumed.
 147  */
 148 template <class Value, 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 <
 198     class LeftValue,
 199     class Left,
 200     class RightValue,
 201     class Right,
 202     class Chain = detail::Chain<LeftValue, Left, Right>>
 203 Chain operator+(const GenImpl<LeftValue, Left>& left,
 204                 const GenImpl<RightValue, Right>& right) {
 205   static_assert(
 206     std::is_same<LeftValue, RightValue>::value,
 207     "Generators may ony be combined if Values are the exact same type.");
 208   return Chain(left.self(), right.self());
 209 }
 210
 211 template <
 212     class LeftValue,
 213     class Left,
 214     class RightValue,
 215     class Right,
 216     class Chain = detail::Chain<LeftValue, Left, Right>>
 217 Chain operator+(const GenImpl<LeftValue, Left>& left,
 218                 GenImpl<RightValue, Right>&& right) {
 219   static_assert(
 220     std::is_same<LeftValue, RightValue>::value,
 221     "Generators may ony be combined if Values are the exact same type.");
 222   return Chain(left.self(), std::move(right.self()));
 223 }
 224
 225 template <
 226     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                 const 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()), right.self());
 237 }
 238
 239 template <
 240     class LeftValue,
 241     class Left,
 242     class RightValue,
 243     class Right,
 244     class Chain = detail::Chain<LeftValue, Left, Right>>
 245 Chain operator+(GenImpl<LeftValue, Left>&& left,
 246                 GenImpl<RightValue, Right>&& right) {
 247   static_assert(
 248     std::is_same<LeftValue, RightValue>::value,
 249     "Generators may ony be combined if Values are the exact same type.");
 250   return Chain(std::move(left.self()), std::move(right.self()));
 251 }
 252
 253 /**
 254  * operator|() which enables foreach-like usage:
 255  *   gen | [](Value v) -> void {...};
 256  */
 257 template <class Value, class Gen, class Handler>
 258 typename std::enable_if<
 259   IsCompatibleSignature<Handler, void(Value)>::value>::type
 260 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 261   static_assert(!Gen::infinite,
 262                 "Cannot pull all values from an infinite sequence.");
 263   gen.self().foreach(std::forward<Handler>(handler));
 264 }
 265
 266 /**
 267  * operator|() which enables foreach-like usage with 'break' support:
 268  *   gen | [](Value v) -> bool { return shouldContinue(); };
 269  */
 270 template <class Value, class Gen, 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, class Gen, 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, class Gen, class Op>
 289 auto operator|(GenImpl<Value, Gen>&& gen, const Operator<Op>& op) ->
 290 decltype(op.self().compose(std::move(gen.self()))) {
 291   return op.self().compose(std::move(gen.self()));
 292 }
 293
 294 namespace detail {
 295
 296 /**
 297  * Composed - For building up a pipeline of operations to perform, absent any
 298  * particular source generator. Useful for building up custom pipelines.
 299  *
 300  * This type is usually used by just piping two operators together:
 301  *
 302  * auto valuesOf = filter([](Optional<int>& o) { return o.hasValue(); })
 303  *               | map([](Optional<int>& o) -> int& { return o.value(); });
 304  *
 305  *  auto valuesIncluded = from(optionals) | valuesOf | as<vector>();
 306  */
 307 template <class First, class Second>
 308 class Composed : public Operator<Composed<First, Second>> {
 309   First first_;
 310   Second second_;
 311  public:
 312   Composed() = default;
 313
 314   Composed(First first, Second second)
 315     : first_(std::move(first))
 316     , second_(std::move(second)) {}
 317
 318   template <
 319       class Source,
 320       class Value,
 321       class FirstRet =
 322           decltype(std::declval<First>().compose(std::declval<Source>())),
 323       class SecondRet =
 324           decltype(std::declval<Second>().compose(std::declval<FirstRet>()))>
 325   SecondRet compose(const GenImpl<Value, Source>& source) const {
 326     return second_.compose(first_.compose(source.self()));
 327   }
 328
 329   template <
 330       class Source,
 331       class Value,
 332       class FirstRet =
 333           decltype(std::declval<First>().compose(std::declval<Source>())),
 334       class SecondRet =
 335           decltype(std::declval<Second>().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 } // gen
 376 } // folly
 377
 378 FOLLY_POP_WARNING