1/*
2 * Copyright 2014-present 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.
27FOLLY_PUSH_WARNING
28FOLLY_GNU_DISABLE_WARNING("-Wshadow")
29
30namespace folly {
31namespace 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 */
40template <class Candidate, class Expected>
41class IsCompatibleSignature {
42 static constexpr bool value = false;
43};
44
45template <class Candidate, class ExpectedReturn, class... ArgTypes>
46class 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 */
69template <class Self>
70struct 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 */
85template <class Self>
86class 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 */
107template <
108 class Left,
109 class Right,
110 class Composed = detail::Composed<Left, Right>>
111Composed operator|(const Operator<Left>& left, const Operator<Right>& right) {
112 return Composed(left.self(), right.self());
113}
114
115template <
116 class Left,
117 class Right,
118 class Composed = detail::Composed<Left, Right>>
119Composed operator|(const Operator<Left>& left, Operator<Right>&& right) {
120 return Composed(left.self(), std::move(right.self()));
121}
122
123template <
124 class Left,
125 class Right,
126 class Composed = detail::Composed<Left, Right>>
127Composed operator|(Operator<Left>&& left, const Operator<Right>& right) {
128 return Composed(std::move(left.self()), right.self());
129}
130
131template <
132 class Left,
133 class Right,
134 class Composed = detail::Composed<Left, Right>>
135Composed operator|(Operator<Left>&& left, 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 */
145template <class Value, class Self>
146class 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
194template <
195 class LeftValue,
196 class Left,
197 class RightValue,
198 class Right,
199 class Chain = detail::Chain<LeftValue, Left, Right>>
200Chain operator+(
201 const GenImpl<LeftValue, Left>& left,
202 const GenImpl<RightValue, Right>& right) {
203 static_assert(
204 std::is_same<LeftValue, RightValue>::value,
205 "Generators may ony be combined if Values are the exact same type.");
206 return Chain(left.self(), right.self());
207}
208
209template <
210 class LeftValue,
211 class Left,
212 class RightValue,
213 class Right,
214 class Chain = detail::Chain<LeftValue, Left, Right>>
215Chain operator+(
216 const GenImpl<LeftValue, Left>& left,
217 GenImpl<RightValue, Right>&& right) {
218 static_assert(
219 std::is_same<LeftValue, RightValue>::value,
220 "Generators may ony be combined if Values are the exact same type.");
221 return Chain(left.self(), std::move(right.self()));
222}
223
224template <
225 class LeftValue,
226 class Left,
227 class RightValue,
228 class Right,
229 class Chain = detail::Chain<LeftValue, Left, Right>>
230Chain operator+(
231 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
239template <
240 class LeftValue,
241 class Left,
242 class RightValue,
243 class Right,
244 class Chain = detail::Chain<LeftValue, Left, Right>>
245Chain operator+(
246 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 */
258template <class Value, class Gen, class Handler>
259typename std::enable_if<
260 IsCompatibleSignature<Handler, void(Value)>::value>::type
261operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
262 static_assert(
263 !Gen::infinite, "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 */
271template <class Value, class Gen, class Handler>
272typename std::
273 enable_if<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 */
283template <class Value, class Gen, class Op>
284auto 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
289template <class Value, class Gen, class Op>
290auto 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
295namespace 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 */
308template <class First, class Second>
309class Composed : public Operator<Composed<First, Second>> {
310 First first_;
311 Second second_;
312
313 public:
314 Composed() = default;
315
316 Composed(First first, Second second)
317 : first_(std::move(first)), 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 */
350template <class Value, class First, class Second>
351class Chain : public GenImpl<Value, Chain<Value, First, Second>> {
352 First first_;
353 Second second_;
354
355 public:
356 explicit Chain(First first, Second second)
357 : first_(std::move(first)), 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} // namespace detail
375} // namespace gen
376} // namespace folly
377
378FOLLY_POP_WARNING
379