2 * Copyright 2015 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.
17 #ifndef FOLLY_GEN_BASE_H
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 {
84 class EmptySequence : public std::exception {
86 virtual const char* what() const noexcept {
87 return "This operation cannot be called on an empty sequence";
95 auto operator()(const First& first, const Second& second) const ->
96 decltype(first < second) {
97 return first < second;
103 template<class First,
105 auto operator()(const First& first, const Second& second) const ->
106 decltype(first > second) {
107 return first > second;
114 template<class Value>
115 auto operator()(Value&& value) const ->
116 decltype(std::get<n>(std::forward<Value>(value))) {
117 return std::get<n>(std::forward<Value>(value));
121 template<class Class,
123 class MemberFunction {
125 typedef Result (Class::*MemberPtr)();
129 explicit MemberFunction(MemberPtr member)
133 Result operator()(Class&& x) const {
134 return (x.*member_)();
137 Result operator()(Class& x) const {
138 return (x.*member_)();
141 Result operator()(Class* x) const {
142 return (x->*member_)();
146 template<class Class,
148 class ConstMemberFunction{
150 typedef Result (Class::*MemberPtr)() const;
154 explicit ConstMemberFunction(MemberPtr member)
158 Result operator()(const Class& x) const {
159 return (x.*member_)();
162 Result operator()(const Class* x) const {
163 return (x->*member_)();
167 template<class Class,
171 typedef FieldType (Class::*FieldPtr);
175 explicit Field(FieldPtr field)
179 const FieldType& operator()(const Class& x) const {
183 const FieldType& operator()(const Class* x) const {
187 FieldType& operator()(Class& x) const {
191 FieldType& operator()(Class* x) const {
195 FieldType&& operator()(Class&& x) const {
196 return std::move(x.*field_);
202 template<class Value>
203 auto operator()(Value&& value) const ->
204 decltype(std::move(std::forward<Value>(value))) {
205 return std::move(std::forward<Value>(value));
211 template<class Value>
212 auto operator()(Value&& value) const ->
213 decltype(std::forward<Value>(value)) {
214 return std::forward<Value>(value);
218 template <class Dest>
221 template <class Value>
222 Dest operator()(Value&& value) const {
223 return Dest(std::forward<Value>(value));
227 template <class Dest>
230 template <class Value>
231 Dest operator()(Value&& value) const {
232 return ::folly::to<Dest>(std::forward<Value>(value));
236 // Specialization to allow String->StringPiece conversion
238 class To<StringPiece> {
240 StringPiece operator()(StringPiece src) const {
245 template<class Key, class Value>
256 template<class Container>
257 struct ValueTypeOfRange {
259 static Container container_;
261 typedef decltype(*std::begin(container_))
263 typedef typename std::decay<decltype(*std::begin(container_))>::type
271 template<class Container,
272 class Value = typename ValueTypeOfRange<Container>::RefType>
273 class ReferencedSource;
275 template<class Value,
276 class Container = std::vector<typename std::decay<Value>::type>>
279 template<class Value, class SequenceImpl>
282 template <class Value>
285 template <class Value, class Distance>
286 class RangeWithStepImpl;
288 template <class Value>
291 template <class Value, class Distance>
292 class SeqWithStepImpl;
294 template <class Value>
297 template<class Value, class Source>
300 template<class Value>
303 template<class Value>
304 class SingleReference;
306 template<class Value>
312 template<class Predicate>
315 template<class Predicate>
318 template<class Predicate>
330 template<class Selector, class Comparer = Less>
333 template<class Selector>
336 template<class Selector>
339 template<class Operators>
342 template<class Expected>
368 template<class Predicate>
371 template<class Reducer>
376 template<class Selector,
380 template<class Container>
383 template<template<class, class> class Collection = std::vector,
384 template<class> class Allocator = std::allocator>
385 class CollectTemplate;
387 template<class Collection>
390 template<class Value>
391 struct GeneratorBuilder;
393 template<class Needle>
396 template<class Exception,
403 * Polymorphic wrapper
405 template<class Value>
411 template<class Container,
412 class From = detail::ReferencedSource<const Container>>
413 From fromConst(const Container& source) {
414 return From(&source);
417 template<class Container,
418 class From = detail::ReferencedSource<Container>>
419 From from(Container& source) {
420 return From(&source);
423 template<class Container,
425 typename detail::ValueTypeOfRange<Container>::StorageType,
426 class CopyOf = detail::CopiedSource<Value>>
427 CopyOf fromCopy(Container&& source) {
428 return CopyOf(std::forward<Container>(source));
431 template<class Value,
432 class From = detail::CopiedSource<Value>>
433 From from(std::initializer_list<Value> source) {
437 template<class Container,
438 class From = detail::CopiedSource<typename Container::value_type,
440 From from(Container&& source) {
441 return From(std::move(source));
444 template<class Value, class Impl = detail::RangeImpl<Value>,
445 class Gen = detail::Sequence<Value, Impl>>
446 Gen range(Value begin, Value end) {
447 return Gen{std::move(begin), Impl{std::move(end)}};
450 template<class Value, class Distance,
451 class Impl = detail::RangeWithStepImpl<Value, Distance>,
452 class Gen = detail::Sequence<Value, Impl>>
453 Gen range(Value begin, Value end, Distance step) {
454 return Gen{std::move(begin), Impl{std::move(end), std::move(step)}};
457 template<class Value, class Impl = detail::SeqImpl<Value>,
458 class Gen = detail::Sequence<Value, Impl>>
459 Gen seq(Value first, Value last) {
460 return Gen{std::move(first), Impl{std::move(last)}};
463 template<class Value, class Distance,
464 class Impl = detail::SeqWithStepImpl<Value, Distance>,
465 class Gen = detail::Sequence<Value, Impl>>
466 Gen seq(Value first, Value last, Distance step) {
467 return Gen{std::move(first), Impl{std::move(last), std::move(step)}};
470 template<class Value, class Impl = detail::InfiniteImpl<Value>,
471 class Gen = detail::Sequence<Value, Impl>>
472 Gen seq(Value first) {
473 return Gen{std::move(first), Impl{}};
476 template<class Value,
478 class Yield = detail::Yield<Value, Source>>
479 Yield generator(Source&& source) {
480 return Yield(std::forward<Source>(source));
484 * Create inline generator, used like:
486 * auto gen = GENERATOR(int) { yield(1); yield(2); };
488 #define GENERATOR(TYPE) \
489 ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
490 [=](const std::function<void(TYPE)>& yield)
493 * empty() - for producing empty sequences.
495 template <class Value>
496 detail::Empty<Value> empty() {
502 class Just = typename std::conditional<
503 std::is_reference<Value>::value,
504 detail::SingleReference<typename std::remove_reference<Value>::type>,
505 detail::SingleCopy<Value>>::type>
506 Just just(Value&& value) {
507 return Just(std::forward<Value>(value));
513 template<class Predicate,
514 class Map = detail::Map<Predicate>>
515 Map mapped(Predicate pred = Predicate()) {
516 return Map(std::move(pred));
519 template<class Predicate,
520 class Map = detail::Map<Predicate>>
521 Map map(Predicate pred = Predicate()) {
522 return Map(std::move(pred));
526 * mapOp - Given a generator of generators, maps the application of the given
527 * operator on to each inner gen. Especially useful in aggregating nested data
530 * chunked(samples, 256)
531 * | mapOp(filter(sampleTest) | count)
534 template<class Operator,
535 class Map = detail::Map<detail::Composer<Operator>>>
536 Map mapOp(Operator op) {
537 return Map(detail::Composer<Operator>(std::move(op)));
541 * member(...) - For extracting a member from each value.
543 * vector<string> strings = ...;
544 * auto sizes = from(strings) | member(&string::size);
546 * If a member is const overridden (like 'front()'), pass template parameter
547 * 'Const' to select the const version, or 'Mutable' to select the non-const
550 * auto heads = from(strings) | member<Const>(&string::front);
558 * These exist because MSVC has problems with expression SFINAE in templates
559 * assignment and comparisons don't work properly without being pulled out
560 * of the template declaration
562 template <MemberType Constness> struct ExprIsConst {
564 value = Constness == Const
568 template <MemberType Constness> struct ExprIsMutable {
570 value = Constness == Mutable
574 template<MemberType Constness = Const,
577 class Mem = ConstMemberFunction<Class, Return>,
578 class Map = detail::Map<Mem>>
579 typename std::enable_if<ExprIsConst<Constness>::value, Map>::type
580 member(Return (Class::*member)() const) {
581 return Map(Mem(member));
584 template<MemberType Constness = Mutable,
587 class Mem = MemberFunction<Class, Return>,
588 class Map = detail::Map<Mem>>
589 typename std::enable_if<ExprIsMutable<Constness>::value, Map>::type
590 member(Return (Class::*member)()) {
591 return Map(Mem(member));
595 * field(...) - For extracting a field from each value.
597 * vector<Item> items = ...;
598 * auto names = from(items) | field(&Item::name);
600 * Note that if the values of the generator are rvalues, any non-reference
601 * fields will be rvalues as well. As an example, the code below does not copy
602 * any strings, only moves them:
604 * auto namesVector = from(items)
606 * | field(&Item::name)
609 template<class Class,
611 class Field = Field<Class, FieldType>,
612 class Map = detail::Map<Field>>
613 Map field(FieldType Class::*field) {
614 return Map(Field(field));
617 template<class Predicate,
618 class Filter = detail::Filter<Predicate>>
619 Filter filter(Predicate pred = Predicate()) {
620 return Filter(std::move(pred));
623 template<class Predicate,
624 class All = detail::All<Predicate>>
625 All all(Predicate pred = Predicate()) {
626 return All(std::move(pred));
629 template<class Predicate,
630 class Until = detail::Until<Predicate>>
631 Until until(Predicate pred = Predicate()) {
632 return Until(std::move(pred));
635 template<class Selector = Identity,
636 class Comparer = Less,
637 class Order = detail::Order<Selector, Comparer>>
638 Order orderBy(Selector selector = Selector(),
639 Comparer comparer = Comparer()) {
640 return Order(std::move(selector),
641 std::move(comparer));
644 template<class Selector = Identity,
645 class Order = detail::Order<Selector, Greater>>
646 Order orderByDescending(Selector selector = Selector()) {
647 return Order(std::move(selector));
650 template<class Selector,
651 class GroupBy = detail::GroupBy<Selector>>
652 GroupBy groupBy(Selector selector = Identity()) {
653 return GroupBy(std::move(selector));
656 template<class Selector = Identity,
657 class Distinct = detail::Distinct<Selector>>
658 Distinct distinctBy(Selector selector = Selector()) {
659 return Distinct(std::move(selector));
663 class Get = detail::Map<Get<n>>>
668 // construct Dest from each value
669 template <class Dest,
670 class Cast = detail::Map<Cast<Dest>>>
675 // call folly::to on each value
676 template <class Dest,
677 class To = detail::Map<To<Dest>>>
682 template<class Value>
683 detail::TypeAssertion<Value> assert_type() {
692 class FoldLeft = detail::FoldLeft<Seed, Fold>>
693 FoldLeft foldl(Seed seed = Seed(),
694 Fold fold = Fold()) {
695 return FoldLeft(std::move(seed),
699 template<class Reducer,
700 class Reduce = detail::Reduce<Reducer>>
701 Reduce reduce(Reducer reducer = Reducer()) {
702 return Reduce(std::move(reducer));
705 template<class Selector = Identity,
706 class Min = detail::Min<Selector, Less>>
707 Min minBy(Selector selector = Selector()) {
708 return Min(std::move(selector));
711 template<class Selector,
712 class MaxBy = detail::Min<Selector, Greater>>
713 MaxBy maxBy(Selector selector = Selector()) {
714 return MaxBy(std::move(selector));
717 template<class Collection,
718 class Collect = detail::Collect<Collection>>
723 template<template<class, class> class Container = std::vector,
724 template<class> class Allocator = std::allocator,
725 class Collect = detail::CollectTemplate<Container, Allocator>>
730 template<class Collection,
731 class Append = detail::Append<Collection>>
732 Append appendTo(Collection& collection) {
733 return Append(&collection);
736 template<class Needle,
737 class Contains = detail::Contains<typename std::decay<Needle>::type>>
738 Contains contains(Needle&& needle) {
739 return Contains(std::forward<Needle>(needle));
742 template<class Exception,
747 typename std::decay<ErrorHandler>::type>>
748 GuardImpl guard(ErrorHandler&& handler) {
749 return GuardImpl(std::forward<ErrorHandler>(handler));
754 #include <folly/gen/Base-inl.h>
756 #endif // FOLLY_GEN_BASE_H