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#pragma once
18#define FOLLY_GEN_BASE_H_
19
20#include <algorithm>
21#include <functional>
22#include <memory>
23#include <random>
24#include <type_traits>
25#include <unordered_map>
26#include <unordered_set>
27#include <utility>
28#include <vector>
29
30#include <folly/Conv.h>
31#include <folly/Optional.h>
32#include <folly/Range.h>
33#include <folly/Utility.h>
34#include <folly/gen/Core.h>
35
36/**
37 * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ
38 * @author Tom Jackson <tjackson@fb.com>
39 *
40 * This library makes it possible to write declarative comprehensions for
41 * processing sequences of values efficiently in C++. The operators should be
42 * familiar to those with experience in functional programming, and the
43 * performance will be virtually identical to the equivalent, boilerplate C++
44 * implementations.
45 *
46 * Generator objects may be created from either an stl-like container (anything
47 * supporting begin() and end()), from sequences of values, or from another
48 * generator (see below). To create a generator that pulls values from a vector,
49 * for example, one could write:
50 *
51 * vector<string> names { "Jack", "Jill", "Sara", "Tom" };
52 * auto gen = from(names);
53 *
54 * Generators are composed by building new generators out of old ones through
55 * the use of operators. These are reminiscent of shell pipelines, and afford
56 * similar composition. Lambda functions are used liberally to describe how to
57 * handle individual values:
58 *
59 * auto lengths = gen
60 * | mapped([](const fbstring& name) { return name.size(); });
61 *
62 * Generators are lazy; they don't actually perform any work until they need to.
63 * As an example, the 'lengths' generator (above) won't actually invoke the
64 * provided lambda until values are needed:
65 *
66 * auto lengthVector = lengths | as<std::vector>();
67 * auto totalLength = lengths | sum;
68 *
69 * 'auto' is useful in here because the actual types of the generators objects
70 * are usually complicated and implementation-sensitive.
71 *
72 * If a simpler type is desired (for returning, as an example), VirtualGen<T>
73 * may be used to wrap the generator in a polymorphic wrapper:
74 *
75 * VirtualGen<float> powersOfE() {
76 * return seq(1) | mapped(&expf);
77 * }
78 *
79 * To learn more about this library, including the use of infinite generators,
80 * see the examples in the comments, or the docs (coming soon).
81 */
82
83namespace folly {
84namespace gen {
85
86class Less {
87 public:
88 template <class First, class Second>
89 auto operator()(const First& first, const Second& second) const
90 -> decltype(first < second) {
91 return first < second;
92 }
93};
94
95class Greater {
96 public:
97 template <class First, class Second>
98 auto operator()(const First& first, const Second& second) const
99 -> decltype(first > second) {
100 return first > second;
101 }
102};
103
104template <int n>
105class Get {
106 public:
107 template <class Value>
108 auto operator()(Value&& value) const
109 -> decltype(std::get<n>(std::forward<Value>(value))) {
110 return std::get<n>(std::forward<Value>(value));
111 }
112};
113
114template <class Class, class Result>
115class MemberFunction {
116 public:
117 typedef Result (Class::*MemberPtr)();
118
119 private:
120 MemberPtr member_;
121
122 public:
123 explicit MemberFunction(MemberPtr member) : member_(member) {}
124
125 Result operator()(Class&& x) const {
126 return (x.*member_)();
127 }
128
129 Result operator()(Class& x) const {
130 return (x.*member_)();
131 }
132
133 Result operator()(Class* x) const {
134 return (x->*member_)();
135 }
136};
137
138template <class Class, class Result>
139class ConstMemberFunction {
140 public:
141 typedef Result (Class::*MemberPtr)() const;
142
143 private:
144 MemberPtr member_;
145
146 public:
147 explicit ConstMemberFunction(MemberPtr member) : member_(member) {}
148
149 Result operator()(const Class& x) const {
150 return (x.*member_)();
151 }
152
153 Result operator()(const Class* x) const {
154 return (x->*member_)();
155 }
156};
157
158template <class Class, class FieldType>
159class Field {
160 public:
161 typedef FieldType(Class::*FieldPtr);
162
163 private:
164 FieldPtr field_;
165
166 public:
167 explicit Field(FieldPtr field) : field_(field) {}
168
169 const FieldType& operator()(const Class& x) const {
170 return x.*field_;
171 }
172
173 const FieldType& operator()(const Class* x) const {
174 return x->*field_;
175 }
176
177 FieldType& operator()(Class& x) const {
178 return x.*field_;
179 }
180
181 FieldType& operator()(Class* x) const {
182 return x->*field_;
183 }
184
185 FieldType&& operator()(Class&& x) const {
186 return std::move(x.*field_);
187 }
188};
189
190class Move {
191 public:
192 template <class Value>
193 auto operator()(Value&& value) const
194 -> decltype(std::move(std::forward<Value>(value))) {
195 return std::move(std::forward<Value>(value));
196 }
197};
198
199/**
200 * Class and helper function for negating a boolean Predicate
201 */
202template <class Predicate>
203class Negate {
204 Predicate pred_;
205
206 public:
207 Negate() = default;
208
209 explicit Negate(Predicate pred) : pred_(std::move(pred)) {}
210
211 template <class Arg>
212 bool operator()(Arg&& arg) const {
213 return !pred_(std::forward<Arg>(arg));
214 }
215};
216template <class Predicate>
217Negate<Predicate> negate(Predicate pred) {
218 return Negate<Predicate>(std::move(pred));
219}
220
221template <class Dest>
222class Cast {
223 public:
224 template <class Value>
225 Dest operator()(Value&& value) const {
226 return Dest(std::forward<Value>(value));
227 }
228};
229
230template <class Dest>
231class To {
232 public:
233 template <class Value>
234 Dest operator()(Value&& value) const {
235 return ::folly::to<Dest>(std::forward<Value>(value));
236 }
237};
238
239template <class Dest>
240class TryTo {
241 public:
242 template <class Value>
243 Expected<Dest, ConversionCode> operator()(Value&& value) const {
244 return ::folly::tryTo<Dest>(std::forward<Value>(value));
245 }
246};
247
248// Specialization to allow String->StringPiece conversion
249template <>
250class To<StringPiece> {
251 public:
252 StringPiece operator()(StringPiece src) const {
253 return src;
254 }
255};
256
257template <class Key, class Value>
258class Group;
259
260namespace detail {
261
262template <class Self>
263struct FBounded;
264
265/*
266 * Type Traits
267 */
268template <class Container>
269struct ValueTypeOfRange {
270 public:
271 using RefType = decltype(*std::begin(std::declval<Container&>()));
272 using StorageType = typename std::decay<RefType>::type;
273};
274
275/*
276 * Sources
277 */
278template <
279 class Container,
280 class Value = typename ValueTypeOfRange<Container>::RefType>
281class ReferencedSource;
282
283template <
284 class Value,
285 class Container = std::vector<typename std::decay<Value>::type>>
286class CopiedSource;
287
288template <class Value, class SequenceImpl>
289class Sequence;
290
291template <class Value>
292class RangeImpl;
293
294template <class Value, class Distance>
295class RangeWithStepImpl;
296
297template <class Value>
298class SeqImpl;
299
300template <class Value, class Distance>
301class SeqWithStepImpl;
302
303template <class Value>
304class InfiniteImpl;
305
306template <class Value, class Source>
307class Yield;
308
309template <class Value>
310class Empty;
311
312template <class Value>
313class SingleReference;
314
315template <class Value>
316class SingleCopy;
317
318/*
319 * Operators
320 */
321template <class Predicate>
322class Map;
323
324template <class Predicate>
325class Filter;
326
327template <class Predicate>
328class Until;
329
330class Take;
331
332class Stride;
333
334template <class Rand>
335class Sample;
336
337class Skip;
338
339template <class Visitor>
340class Visit;
341
342template <class Selector, class Comparer = Less>
343class Order;
344
345template <class Selector>
346class GroupBy;
347
348template <class Selector>
349class GroupByAdjacent;
350
351template <class Selector>
352class Distinct;
353
354template <class Operators>
355class Composer;
356
357template <class Expected>
358class TypeAssertion;
359
360class Concat;
361
362class RangeConcat;
363
364template <bool forever>
365class Cycle;
366
367class Batch;
368
369class Window;
370
371class Dereference;
372
373class Indirect;
374
375/*
376 * Sinks
377 */
378template <class Seed, class Fold>
379class FoldLeft;
380
381class First;
382
383template <bool result>
384class IsEmpty;
385
386template <class Reducer>
387class Reduce;
388
389class Sum;
390
391template <class Selector, class Comparer>
392class Min;
393
394template <class Container>
395class Collect;
396
397template <
398 template <class, class> class Collection = std::vector,
399 template <class> class Allocator = std::allocator>
400class CollectTemplate;
401
402template <class Collection>
403class Append;
404
405template <class Value>
406struct GeneratorBuilder;
407
408template <class Needle>
409class Contains;
410
411template <class Exception, class ErrorHandler>
412class GuardImpl;
413
414template <class T>
415class UnwrapOr;
416
417class Unwrap;
418
419} // namespace detail
420
421/**
422 * Polymorphic wrapper
423 **/
424template <class Value>
425class VirtualGen;
426
427/*
428 * Source Factories
429 */
430template <
431 class Container,
432 class From = detail::ReferencedSource<const Container>>
433From fromConst(const Container& source) {
434 return From(&source);
435}
436
437template <class Container, class From = detail::ReferencedSource<Container>>
438From from(Container& source) {
439 return From(&source);
440}
441
442template <
443 class Container,
444 class Value = typename detail::ValueTypeOfRange<Container>::StorageType,
445 class CopyOf = detail::CopiedSource<Value>>
446CopyOf fromCopy(Container&& source) {
447 return CopyOf(std::forward<Container>(source));
448}
449
450template <class Value, class From = detail::CopiedSource<Value>>
451From from(std::initializer_list<Value> source) {
452 return From(source);
453}
454
455template <
456 class Container,
457 class From =
458 detail::CopiedSource<typename Container::value_type, Container>>
459From from(Container&& source) {
460 return From(std::move(source));
461}
462
463template <
464 class Value,
465 class Impl = detail::RangeImpl<Value>,
466 class Gen = detail::Sequence<Value, Impl>>
467Gen range(Value begin, Value end) {
468 return Gen{std::move(begin), Impl{std::move(end)}};
469}
470
471template <
472 class Value,
473 class Distance,
474 class Impl = detail::RangeWithStepImpl<Value, Distance>,
475 class Gen = detail::Sequence<Value, Impl>>
476Gen range(Value begin, Value end, Distance step) {
477 return Gen{std::move(begin), Impl{std::move(end), std::move(step)}};
478}
479
480template <
481 class Value,
482 class Impl = detail::SeqImpl<Value>,
483 class Gen = detail::Sequence<Value, Impl>>
484Gen seq(Value first, Value last) {
485 return Gen{std::move(first), Impl{std::move(last)}};
486}
487
488template <
489 class Value,
490 class Distance,
491 class Impl = detail::SeqWithStepImpl<Value, Distance>,
492 class Gen = detail::Sequence<Value, Impl>>
493Gen seq(Value first, Value last, Distance step) {
494 return Gen{std::move(first), Impl{std::move(last), std::move(step)}};
495}
496
497template <
498 class Value,
499 class Impl = detail::InfiniteImpl<Value>,
500 class Gen = detail::Sequence<Value, Impl>>
501Gen seq(Value first) {
502 return Gen{std::move(first), Impl{}};
503}
504
505template <class Value, class Source, class Yield = detail::Yield<Value, Source>>
506Yield generator(Source&& source) {
507 return Yield(std::forward<Source>(source));
508}
509
510/*
511 * Create inline generator, used like:
512 *
513 * auto gen = GENERATOR(int) { yield(1); yield(2); };
514 */
515#define GENERATOR(TYPE) \
516 ::folly::gen::detail::GeneratorBuilder<TYPE>() + [=](auto&& yield)
517
518/*
519 * empty() - for producing empty sequences.
520 */
521template <class Value>
522detail::Empty<Value> empty() {
523 return {};
524}
525
526template <
527 class Value,
528 class Just = typename std::conditional<
529 std::is_reference<Value>::value,
530 detail::SingleReference<typename std::remove_reference<Value>::type>,
531 detail::SingleCopy<Value>>::type>
532Just just(Value&& value) {
533 return Just(std::forward<Value>(value));
534}
535
536/*
537 * Operator Factories
538 */
539template <class Predicate, class Map = detail::Map<Predicate>>
540Map mapped(Predicate pred = Predicate()) {
541 return Map(std::move(pred));
542}
543
544template <class Predicate, class Map = detail::Map<Predicate>>
545Map map(Predicate pred = Predicate()) {
546 return Map(std::move(pred));
547}
548
549/**
550 * mapOp - Given a generator of generators, maps the application of the given
551 * operator on to each inner gen. Especially useful in aggregating nested data
552 * structures:
553 *
554 * chunked(samples, 256)
555 * | mapOp(filter(sampleTest) | count)
556 * | sum;
557 */
558template <class Operator, class Map = detail::Map<detail::Composer<Operator>>>
559Map mapOp(Operator op) {
560 return Map(detail::Composer<Operator>(std::move(op)));
561}
562
563/*
564 * member(...) - For extracting a member from each value.
565 *
566 * vector<string> strings = ...;
567 * auto sizes = from(strings) | member(&string::size);
568 *
569 * If a member is const overridden (like 'front()'), pass template parameter
570 * 'Const' to select the const version, or 'Mutable' to select the non-const
571 * version:
572 *
573 * auto heads = from(strings) | member<Const>(&string::front);
574 */
575enum MemberType {
576 Const,
577 Mutable,
578};
579
580/**
581 * These exist because MSVC has problems with expression SFINAE in templates
582 * assignment and comparisons don't work properly without being pulled out
583 * of the template declaration
584 */
585template <MemberType Constness>
586struct ExprIsConst {
587 enum {
588 value = Constness == Const,
589 };
590};
591
592template <MemberType Constness>
593struct ExprIsMutable {
594 enum {
595 value = Constness == Mutable,
596 };
597};
598
599template <
600 MemberType Constness = Const,
601 class Class,
602 class Return,
603 class Mem = ConstMemberFunction<Class, Return>,
604 class Map = detail::Map<Mem>>
605typename std::enable_if<ExprIsConst<Constness>::value, Map>::type member(
606 Return (Class::*member)() const) {
607 return Map(Mem(member));
608}
609
610template <
611 MemberType Constness = Mutable,
612 class Class,
613 class Return,
614 class Mem = MemberFunction<Class, Return>,
615 class Map = detail::Map<Mem>>
616typename std::enable_if<ExprIsMutable<Constness>::value, Map>::type member(
617 Return (Class::*member)()) {
618 return Map(Mem(member));
619}
620
621/*
622 * field(...) - For extracting a field from each value.
623 *
624 * vector<Item> items = ...;
625 * auto names = from(items) | field(&Item::name);
626 *
627 * Note that if the values of the generator are rvalues, any non-reference
628 * fields will be rvalues as well. As an example, the code below does not copy
629 * any strings, only moves them:
630 *
631 * auto namesVector = from(items)
632 * | move
633 * | field(&Item::name)
634 * | as<vector>();
635 */
636template <
637 class Class,
638 class FieldType,
639 class Field = Field<Class, FieldType>,
640 class Map = detail::Map<Field>>
641Map field(FieldType Class::*field) {
642 return Map(Field(field));
643}
644
645template <class Predicate = Identity, class Filter = detail::Filter<Predicate>>
646Filter filter(Predicate pred = Predicate()) {
647 return Filter(std::move(pred));
648}
649
650template <class Visitor = Ignore, class Visit = detail::Visit<Visitor>>
651Visit visit(Visitor visitor = Visitor()) {
652 return Visit(std::move(visitor));
653}
654
655template <class Predicate = Identity, class Until = detail::Until<Predicate>>
656Until until(Predicate pred = Predicate()) {
657 return Until(std::move(pred));
658}
659
660template <
661 class Predicate = Identity,
662 class TakeWhile = detail::Until<Negate<Predicate>>>
663TakeWhile takeWhile(Predicate pred = Predicate()) {
664 return TakeWhile(Negate<Predicate>(std::move(pred)));
665}
666
667template <
668 class Selector = Identity,
669 class Comparer = Less,
670 class Order = detail::Order<Selector, Comparer>>
671Order orderBy(Selector selector = Selector(), Comparer comparer = Comparer()) {
672 return Order(std::move(selector), std::move(comparer));
673}
674
675template <
676 class Selector = Identity,
677 class Order = detail::Order<Selector, Greater>>
678Order orderByDescending(Selector selector = Selector()) {
679 return Order(std::move(selector));
680}
681
682template <class Selector = Identity, class GroupBy = detail::GroupBy<Selector>>
683GroupBy groupBy(Selector selector = Selector()) {
684 return GroupBy(std::move(selector));
685}
686
687template <
688 class Selector = Identity,
689 class GroupByAdjacent = detail::GroupByAdjacent<Selector>>
690GroupByAdjacent groupByAdjacent(Selector selector = Selector()) {
691 return GroupByAdjacent(std::move(selector));
692}
693
694template <
695 class Selector = Identity,
696 class Distinct = detail::Distinct<Selector>>
697Distinct distinctBy(Selector selector = Selector()) {
698 return Distinct(std::move(selector));
699}
700
701template <int n, class Get = detail::Map<Get<n>>>
702Get get() {
703 return Get();
704}
705
706// construct Dest from each value
707template <class Dest, class Cast = detail::Map<Cast<Dest>>>
708Cast eachAs() {
709 return Cast();
710}
711
712// call folly::to on each value
713template <class Dest, class EachTo = detail::Map<To<Dest>>>
714EachTo eachTo() {
715 return EachTo();
716}
717
718// call folly::tryTo on each value
719template <class Dest, class EachTryTo = detail::Map<TryTo<Dest>>>
720EachTryTo eachTryTo() {
721 return EachTryTo();
722}
723
724template <class Value>
725detail::TypeAssertion<Value> assert_type() {
726 return {};
727}
728
729/*
730 * Sink Factories
731 */
732
733/**
734 * any() - For determining if any value in a sequence satisfies a predicate.
735 *
736 * The following is an example for checking if any computer is broken:
737 *
738 * bool schrepIsMad = from(computers) | any(isBroken);
739 *
740 * (because everyone knows Schrep hates broken computers).
741 *
742 * Note that if no predicate is provided, 'any()' checks if any of the values
743 * are true when cased to bool. To check if any of the scores are nonZero:
744 *
745 * bool somebodyScored = from(scores) | any();
746 *
747 * Note: Passing an empty sequence through 'any()' will always return false. In
748 * fact, 'any()' is equivilent to the composition of 'filter()' and 'notEmpty'.
749 *
750 * from(source) | any(pred) == from(source) | filter(pred) | notEmpty
751 */
752
753template <
754 class Predicate = Identity,
755 class Filter = detail::Filter<Predicate>,
756 class NotEmpty = detail::IsEmpty<false>,
757 class Composed = detail::Composed<Filter, NotEmpty>>
758Composed any(Predicate pred = Predicate()) {
759 return Composed(Filter(std::move(pred)), NotEmpty());
760}
761
762/**
763 * all() - For determining whether all values in a sequence satisfy a predicate.
764 *
765 * The following is an example for checking if all members of a team are cool:
766 *
767 * bool isAwesomeTeam = from(team) | all(isCool);
768 *
769 * Note that if no predicate is provided, 'all()'' checks if all of the values
770 * are true when cased to bool.
771 * The following makes sure none of 'pointers' are nullptr:
772 *
773 * bool allNonNull = from(pointers) | all();
774 *
775 * Note: Passing an empty sequence through 'all()' will always return true. In
776 * fact, 'all()' is equivilent to the composition of 'filter()' with the
777 * reversed predicate and 'isEmpty'.
778 *
779 * from(source) | all(pred) == from(source) | filter(negate(pred)) | isEmpty
780 */
781template <
782 class Predicate = Identity,
783 class Filter = detail::Filter<Negate<Predicate>>,
784 class IsEmpty = detail::IsEmpty<true>,
785 class Composed = detail::Composed<Filter, IsEmpty>>
786Composed all(Predicate pred = Predicate()) {
787 return Composed(Filter(std::move(negate(pred))), IsEmpty());
788}
789
790template <class Seed, class Fold, class FoldLeft = detail::FoldLeft<Seed, Fold>>
791FoldLeft foldl(Seed seed = Seed(), Fold fold = Fold()) {
792 return FoldLeft(std::move(seed), std::move(fold));
793}
794
795template <class Reducer, class Reduce = detail::Reduce<Reducer>>
796Reduce reduce(Reducer reducer = Reducer()) {
797 return Reduce(std::move(reducer));
798}
799
800template <class Selector = Identity, class Min = detail::Min<Selector, Less>>
801Min minBy(Selector selector = Selector()) {
802 return Min(std::move(selector));
803}
804
805template <class Selector, class MaxBy = detail::Min<Selector, Greater>>
806MaxBy maxBy(Selector selector = Selector()) {
807 return MaxBy(std::move(selector));
808}
809
810template <class Collection, class Collect = detail::Collect<Collection>>
811Collect as() {
812 return Collect();
813}
814
815template <
816 template <class, class> class Container = std::vector,
817 template <class> class Allocator = std::allocator,
818 class Collect = detail::CollectTemplate<Container, Allocator>>
819Collect as() {
820 return Collect();
821}
822
823template <class Collection, class Append = detail::Append<Collection>>
824Append appendTo(Collection& collection) {
825 return Append(&collection);
826}
827
828template <
829 class Needle,
830 class Contains = detail::Contains<typename std::decay<Needle>::type>>
831Contains contains(Needle&& needle) {
832 return Contains(std::forward<Needle>(needle));
833}
834
835template <
836 class Exception,
837 class ErrorHandler,
838 class GuardImpl =
839 detail::GuardImpl<Exception, typename std::decay<ErrorHandler>::type>>
840GuardImpl guard(ErrorHandler&& handler) {
841 return GuardImpl(std::forward<ErrorHandler>(handler));
842}
843
844template <
845 class Fallback,
846 class UnwrapOr = detail::UnwrapOr<typename std::decay<Fallback>::type>>
847UnwrapOr unwrapOr(Fallback&& fallback) {
848 return UnwrapOr(std::forward<Fallback>(fallback));
849}
850
851} // namespace gen
852} // namespace folly
853
854#include <folly/gen/Base-inl.h>
855