2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #define FOLLY_GEN_BASE_H_
24 #include <type_traits>
25 #include <unordered_map>
26 #include <unordered_set>
30 #include <folly/Conv.h>
31 #include <folly/Optional.h>
32 #include <folly/Range.h>
33 #include <folly/gen/Core.h>
36 * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ
37 * @author Tom Jackson <tjackson@fb.com>
39 * This library makes it possible to write declarative comprehensions for
40 * processing sequences of values efficiently in C++. The operators should be
41 * familiar to those with experience in functional programming, and the
42 * performance will be virtually identical to the equivalent, boilerplate C++
45 * Generator objects may be created from either an stl-like container (anything
46 * supporting begin() and end()), from sequences of values, or from another
47 * generator (see below). To create a generator that pulls values from a vector,
48 * for example, one could write:
50 * vector<string> names { "Jack", "Jill", "Sara", "Tom" };
51 * auto gen = from(names);
53 * Generators are composed by building new generators out of old ones through
54 * the use of operators. These are reminicent of shell pipelines, and afford
55 * similar composition. Lambda functions are used liberally to describe how to
56 * handle individual values:
59 * | mapped([](const fbstring& name) { return name.size(); });
61 * Generators are lazy; they don't actually perform any work until they need to.
62 * As an example, the 'lengths' generator (above) won't actually invoke the
63 * provided lambda until values are needed:
65 * auto lengthVector = lengths | as<std::vector>();
66 * auto totalLength = lengths | sum;
68 * 'auto' is useful in here because the actual types of the generators objects
69 * are usually complicated and implementation-sensitive.
71 * If a simpler type is desired (for returning, as an example), VirtualGen<T>
72 * may be used to wrap the generator in a polymorphic wrapper:
74 * VirtualGen<float> powersOfE() {
75 * return seq(1) | mapped(&expf);
78 * To learn more about this library, including the use of infinite generators,
79 * see the examples in the comments, or the docs (coming soon).
82 namespace folly { namespace gen {
88 auto operator()(const First& first, const Second& second) const ->
89 decltype(first < second) {
90 return first < second;
98 auto operator()(const First& first, const Second& second) const ->
99 decltype(first > second) {
100 return first > second;
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));
114 template<class Class,
116 class MemberFunction {
118 typedef Result (Class::*MemberPtr)();
122 explicit MemberFunction(MemberPtr member)
126 Result operator()(Class&& x) const {
127 return (x.*member_)();
130 Result operator()(Class& x) const {
131 return (x.*member_)();
134 Result operator()(Class* x) const {
135 return (x->*member_)();
139 template<class Class,
141 class ConstMemberFunction{
143 typedef Result (Class::*MemberPtr)() const;
147 explicit ConstMemberFunction(MemberPtr member)
151 Result operator()(const Class& x) const {
152 return (x.*member_)();
155 Result operator()(const Class* x) const {
156 return (x->*member_)();
160 template<class Class,
164 typedef FieldType (Class::*FieldPtr);
168 explicit Field(FieldPtr field)
172 const FieldType& operator()(const Class& x) const {
176 const FieldType& operator()(const Class* x) const {
180 FieldType& operator()(Class& x) const {
184 FieldType& operator()(Class* x) const {
188 FieldType&& operator()(Class&& x) const {
189 return std::move(x.*field_);
195 template<class Value>
196 auto operator()(Value&& value) const ->
197 decltype(std::move(std::forward<Value>(value))) {
198 return std::move(std::forward<Value>(value));
204 template<class Value>
205 auto operator()(Value&& value) const ->
206 decltype(std::forward<Value>(value)) {
207 return std::forward<Value>(value);
212 * Class and helper function for negating a boolean Predicate
214 template <class Predicate>
221 explicit Negate(Predicate pred)
222 : pred_(std::move(pred))
226 bool operator()(Arg&& arg) const {
227 return !pred_(std::forward<Arg>(arg));
230 template <class Predicate>
231 Negate<Predicate> negate(Predicate pred) {
232 return Negate<Predicate>(std::move(pred));
235 template <class Dest>
238 template <class Value>
239 Dest operator()(Value&& value) const {
240 return Dest(std::forward<Value>(value));
244 template <class Dest>
247 template <class Value>
248 Dest operator()(Value&& value) const {
249 return ::folly::to<Dest>(std::forward<Value>(value));
253 // Specialization to allow String->StringPiece conversion
255 class To<StringPiece> {
257 StringPiece operator()(StringPiece src) const {
262 template<class Key, class Value>
273 template<class Container>
274 struct ValueTypeOfRange {
276 using RefType = decltype(*std::begin(std::declval<Container&>()));
277 using StorageType = typename std::decay<RefType>::type;
284 template<class Container,
285 class Value = typename ValueTypeOfRange<Container>::RefType>
286 class ReferencedSource;
288 template<class Value,
289 class Container = std::vector<typename std::decay<Value>::type>>
292 template<class Value, class SequenceImpl>
295 template <class Value>
298 template <class Value, class Distance>
299 class RangeWithStepImpl;
301 template <class Value>
304 template <class Value, class Distance>
305 class SeqWithStepImpl;
307 template <class Value>
310 template<class Value, class Source>
313 template<class Value>
316 template<class Value>
317 class SingleReference;
319 template<class Value>
325 template<class Predicate>
328 template<class Predicate>
331 template<class Predicate>
343 template<class Selector, class Comparer = Less>
346 template<class Selector>
349 template<class Selector>
352 template<class Operators>
355 template<class Expected>
362 template <bool forever>
380 template <bool result>
383 template<class Reducer>
388 template<class Selector,
392 template<class Container>
395 template<template<class, class> class Collection = std::vector,
396 template<class> class Allocator = std::allocator>
397 class CollectTemplate;
399 template<class Collection>
402 template<class Value>
403 struct GeneratorBuilder;
405 template<class Needle>
408 template<class Exception,
420 * Polymorphic wrapper
422 template<class Value>
428 template<class Container,
429 class From = detail::ReferencedSource<const Container>>
430 From fromConst(const Container& source) {
431 return From(&source);
434 template<class Container,
435 class From = detail::ReferencedSource<Container>>
436 From from(Container& source) {
437 return From(&source);
440 template<class Container,
442 typename detail::ValueTypeOfRange<Container>::StorageType,
443 class CopyOf = detail::CopiedSource<Value>>
444 CopyOf fromCopy(Container&& source) {
445 return CopyOf(std::forward<Container>(source));
448 template<class Value,
449 class From = detail::CopiedSource<Value>>
450 From from(std::initializer_list<Value> source) {
454 template<class Container,
455 class From = detail::CopiedSource<typename Container::value_type,
457 From from(Container&& source) {
458 return From(std::move(source));
461 template<class Value, class Impl = detail::RangeImpl<Value>,
462 class Gen = detail::Sequence<Value, Impl>>
463 Gen range(Value begin, Value end) {
464 return Gen{std::move(begin), Impl{std::move(end)}};
467 template<class Value, class Distance,
468 class Impl = detail::RangeWithStepImpl<Value, Distance>,
469 class Gen = detail::Sequence<Value, Impl>>
470 Gen range(Value begin, Value end, Distance step) {
471 return Gen{std::move(begin), Impl{std::move(end), std::move(step)}};
474 template<class Value, class Impl = detail::SeqImpl<Value>,
475 class Gen = detail::Sequence<Value, Impl>>
476 Gen seq(Value first, Value last) {
477 return Gen{std::move(first), Impl{std::move(last)}};
480 template<class Value, class Distance,
481 class Impl = detail::SeqWithStepImpl<Value, Distance>,
482 class Gen = detail::Sequence<Value, Impl>>
483 Gen seq(Value first, Value last, Distance step) {
484 return Gen{std::move(first), Impl{std::move(last), std::move(step)}};
487 template<class Value, class Impl = detail::InfiniteImpl<Value>,
488 class Gen = detail::Sequence<Value, Impl>>
489 Gen seq(Value first) {
490 return Gen{std::move(first), Impl{}};
493 template<class Value,
495 class Yield = detail::Yield<Value, Source>>
496 Yield generator(Source&& source) {
497 return Yield(std::forward<Source>(source));
501 * Create inline generator, used like:
503 * auto gen = GENERATOR(int) { yield(1); yield(2); };
505 #define GENERATOR(TYPE) \
506 ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
507 [=](const std::function<void(TYPE)>& yield)
510 * empty() - for producing empty sequences.
512 template <class Value>
513 detail::Empty<Value> empty() {
519 class Just = typename std::conditional<
520 std::is_reference<Value>::value,
521 detail::SingleReference<typename std::remove_reference<Value>::type>,
522 detail::SingleCopy<Value>>::type>
523 Just just(Value&& value) {
524 return Just(std::forward<Value>(value));
530 template<class Predicate,
531 class Map = detail::Map<Predicate>>
532 Map mapped(Predicate pred = Predicate()) {
533 return Map(std::move(pred));
536 template<class Predicate,
537 class Map = detail::Map<Predicate>>
538 Map map(Predicate pred = Predicate()) {
539 return Map(std::move(pred));
543 * mapOp - Given a generator of generators, maps the application of the given
544 * operator on to each inner gen. Especially useful in aggregating nested data
547 * chunked(samples, 256)
548 * | mapOp(filter(sampleTest) | count)
551 template<class Operator,
552 class Map = detail::Map<detail::Composer<Operator>>>
553 Map mapOp(Operator op) {
554 return Map(detail::Composer<Operator>(std::move(op)));
558 * member(...) - For extracting a member from each value.
560 * vector<string> strings = ...;
561 * auto sizes = from(strings) | member(&string::size);
563 * If a member is const overridden (like 'front()'), pass template parameter
564 * 'Const' to select the const version, or 'Mutable' to select the non-const
567 * auto heads = from(strings) | member<Const>(&string::front);
575 * These exist because MSVC has problems with expression SFINAE in templates
576 * assignment and comparisons don't work properly without being pulled out
577 * of the template declaration
579 template <MemberType Constness> struct ExprIsConst {
581 value = Constness == Const
585 template <MemberType Constness> struct ExprIsMutable {
587 value = Constness == Mutable
591 template<MemberType Constness = Const,
594 class Mem = ConstMemberFunction<Class, Return>,
595 class Map = detail::Map<Mem>>
596 typename std::enable_if<ExprIsConst<Constness>::value, Map>::type
597 member(Return (Class::*member)() const) {
598 return Map(Mem(member));
601 template<MemberType Constness = Mutable,
604 class Mem = MemberFunction<Class, Return>,
605 class Map = detail::Map<Mem>>
606 typename std::enable_if<ExprIsMutable<Constness>::value, Map>::type
607 member(Return (Class::*member)()) {
608 return Map(Mem(member));
612 * field(...) - For extracting a field from each value.
614 * vector<Item> items = ...;
615 * auto names = from(items) | field(&Item::name);
617 * Note that if the values of the generator are rvalues, any non-reference
618 * fields will be rvalues as well. As an example, the code below does not copy
619 * any strings, only moves them:
621 * auto namesVector = from(items)
623 * | field(&Item::name)
626 template<class Class,
628 class Field = Field<Class, FieldType>,
629 class Map = detail::Map<Field>>
630 Map field(FieldType Class::*field) {
631 return Map(Field(field));
634 template <class Predicate = Identity,
635 class Filter = detail::Filter<Predicate>>
636 Filter filter(Predicate pred = Predicate()) {
637 return Filter(std::move(pred));
640 template<class Predicate,
641 class Until = detail::Until<Predicate>>
642 Until until(Predicate pred = Predicate()) {
643 return Until(std::move(pred));
646 template<class Selector = Identity,
647 class Comparer = Less,
648 class Order = detail::Order<Selector, Comparer>>
649 Order orderBy(Selector selector = Selector(),
650 Comparer comparer = Comparer()) {
651 return Order(std::move(selector),
652 std::move(comparer));
655 template<class Selector = Identity,
656 class Order = detail::Order<Selector, Greater>>
657 Order orderByDescending(Selector selector = Selector()) {
658 return Order(std::move(selector));
661 template <class Selector = Identity,
662 class GroupBy = detail::GroupBy<Selector>>
663 GroupBy groupBy(Selector selector = Selector()) {
664 return GroupBy(std::move(selector));
667 template<class Selector = Identity,
668 class Distinct = detail::Distinct<Selector>>
669 Distinct distinctBy(Selector selector = Selector()) {
670 return Distinct(std::move(selector));
674 class Get = detail::Map<Get<n>>>
679 // construct Dest from each value
680 template <class Dest,
681 class Cast = detail::Map<Cast<Dest>>>
686 // call folly::to on each value
687 template <class Dest,
688 class To = detail::Map<To<Dest>>>
693 template<class Value>
694 detail::TypeAssertion<Value> assert_type() {
703 * any() - For determining if any value in a sequence satisfies a predicate.
705 * The following is an example for checking if any computer is broken:
707 * bool schrepIsMad = from(computers) | any(isBroken);
709 * (because everyone knows Schrep hates broken computers).
711 * Note that if no predicate is provided, 'any()' checks if any of the values
712 * are true when cased to bool. To check if any of the scores are nonZero:
714 * bool somebodyScored = from(scores) | any();
716 * Note: Passing an empty sequence through 'any()' will always return false. In
717 * fact, 'any()' is equivilent to the composition of 'filter()' and 'notEmpty'.
719 * from(source) | any(pred) == from(source) | filter(pred) | notEmpty
722 template <class Predicate = Identity,
723 class Filter = detail::Filter<Predicate>,
724 class NotEmpty = detail::IsEmpty<false>,
725 class Composed = detail::Composed<Filter, NotEmpty>>
726 Composed any(Predicate pred = Predicate()) {
727 return Composed(Filter(std::move(pred)), NotEmpty());
731 * all() - For determining whether all values in a sequence satisfy a predicate.
733 * The following is an example for checking if all members of a team are cool:
735 * bool isAwesomeTeam = from(team) | all(isCool);
737 * Note that if no predicate is provided, 'all()'' checks if all of the values
738 * are true when cased to bool.
739 * The following makes sure none of 'pointers' are nullptr:
741 * bool allNonNull = from(pointers) | all();
743 * Note: Passing an empty sequence through 'all()' will always return true. In
744 * fact, 'all()' is equivilent to the composition of 'filter()' with the
745 * reversed predicate and 'isEmpty'.
747 * from(source) | all(pred) == from(source) | filter(negate(pred)) | isEmpty
750 template <class Predicate = Identity,
751 class Filter = detail::Filter<Negate<Predicate>>,
752 class IsEmpty = detail::IsEmpty<true>,
753 class Composed = detail::Composed<Filter, IsEmpty>>
754 Composed all(Predicate pred = Predicate()) {
755 return Composed(Filter(std::move(negate(pred))), IsEmpty());
760 class FoldLeft = detail::FoldLeft<Seed, Fold>>
761 FoldLeft foldl(Seed seed = Seed(),
762 Fold fold = Fold()) {
763 return FoldLeft(std::move(seed),
767 template<class Reducer,
768 class Reduce = detail::Reduce<Reducer>>
769 Reduce reduce(Reducer reducer = Reducer()) {
770 return Reduce(std::move(reducer));
773 template<class Selector = Identity,
774 class Min = detail::Min<Selector, Less>>
775 Min minBy(Selector selector = Selector()) {
776 return Min(std::move(selector));
779 template<class Selector,
780 class MaxBy = detail::Min<Selector, Greater>>
781 MaxBy maxBy(Selector selector = Selector()) {
782 return MaxBy(std::move(selector));
785 template<class Collection,
786 class Collect = detail::Collect<Collection>>
791 template<template<class, class> class Container = std::vector,
792 template<class> class Allocator = std::allocator,
793 class Collect = detail::CollectTemplate<Container, Allocator>>
798 template<class Collection,
799 class Append = detail::Append<Collection>>
800 Append appendTo(Collection& collection) {
801 return Append(&collection);
804 template<class Needle,
805 class Contains = detail::Contains<typename std::decay<Needle>::type>>
806 Contains contains(Needle&& needle) {
807 return Contains(std::forward<Needle>(needle));
810 template<class Exception,
815 typename std::decay<ErrorHandler>::type>>
816 GuardImpl guard(ErrorHandler&& handler) {
817 return GuardImpl(std::forward<ErrorHandler>(handler));
820 template<class Fallback,
821 class UnwrapOr = detail::UnwrapOr<typename std::decay<Fallback>::type>>
822 UnwrapOr unwrapOr(Fallback&& fallback) {
823 return UnwrapOr(std::forward<Fallback>(fallback));
828 #include <folly/gen/Base-inl.h>