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. |
27 | FOLLY_PUSH_WARNING |
28 | FOLLY_GNU_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, 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, Operator<Right>&& right) { |
120 | return Composed(left.self(), std::move(right.self())); |
121 | } |
122 | |
123 | template < |
124 | class Left, |
125 | class Right, |
126 | class Composed = detail::Composed<Left, Right>> |
127 | Composed operator|(Operator<Left>&& left, const Operator<Right>& right) { |
128 | return Composed(std::move(left.self()), right.self()); |
129 | } |
130 | |
131 | template < |
132 | class Left, |
133 | class Right, |
134 | class Composed = detail::Composed<Left, Right>> |
135 | Composed 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 | */ |
145 | template <class Value, 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 | // |
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 | |
194 | template < |
195 | class LeftValue, |
196 | class Left, |
197 | class RightValue, |
198 | class Right, |
199 | class Chain = detail::Chain<LeftValue, Left, Right>> |
200 | Chain 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 | |
209 | template < |
210 | class LeftValue, |
211 | class Left, |
212 | class RightValue, |
213 | class Right, |
214 | class Chain = detail::Chain<LeftValue, Left, Right>> |
215 | Chain 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 | |
224 | template < |
225 | class LeftValue, |
226 | class Left, |
227 | class RightValue, |
228 | class Right, |
229 | class Chain = detail::Chain<LeftValue, Left, Right>> |
230 | Chain 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 | |
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+( |
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 | */ |
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( |
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 | */ |
271 | template <class Value, class Gen, class Handler> |
272 | typename 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 | */ |
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 | |
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 | */ |
350 | template <class Value, class First, class Second> |
351 | class 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 | |
378 | FOLLY_POP_WARNING |
379 | |