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
22 #include <type_traits>
27 #include <unordered_set>
29 #include <folly/Range.h>
30 #include <folly/Optional.h>
31 #include <folly/Conv.h>
32 #include <folly/gen/Core.h>
35 * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ
36 * @author Tom Jackson <tjackson@fb.com>
38 * This library makes it possible to write declarative comprehensions for
39 * processing sequences of values efficiently in C++. The operators should be
40 * familiar to those with experience in functional programming, and the
41 * performance will be virtually identical to the equivalent, boilerplate C++
44 * Generator objects may be created from either an stl-like container (anything
45 * supporting begin() and end()), from sequences of values, or from another
46 * generator (see below). To create a generator that pulls values from a vector,
47 * for example, one could write:
49 * vector<string> names { "Jack", "Jill", "Sara", "Tom" };
50 * auto gen = from(names);
52 * Generators are composed by building new generators out of old ones through
53 * the use of operators. These are reminicent of shell pipelines, and afford
54 * similar composition. Lambda functions are used liberally to describe how to
55 * handle individual values:
58 * | mapped([](const fbstring& name) { return name.size(); });
60 * Generators are lazy; they don't actually perform any work until they need to.
61 * As an example, the 'lengths' generator (above) won't actually invoke the
62 * provided lambda until values are needed:
64 * auto lengthVector = lengths | as<std::vector>();
65 * auto totalLength = lengths | sum;
67 * 'auto' is useful in here because the actual types of the generators objects
68 * are usually complicated and implementation-sensitive.
70 * If a simpler type is desired (for returning, as an example), VirtualGen<T>
71 * may be used to wrap the generator in a polymorphic wrapper:
73 * VirtualGen<float> powersOfE() {
74 * return seq(1) | mapped(&expf);
77 * To learn more about this library, including the use of infinite generators,
78 * see the examples in the comments, or the docs (coming soon).
81 namespace folly { namespace gen {
83 class EmptySequence : public std::exception {
85 virtual const char* what() const noexcept {
86 return "This operation cannot be called on an empty sequence";
94 auto operator()(const First& first, const Second& second) const ->
95 decltype(first < second) {
96 return first < second;
102 template<class First,
104 auto operator()(const First& first, const Second& second) const ->
105 decltype(first > second) {
106 return first > second;
113 template<class Value>
114 auto operator()(Value&& value) const ->
115 decltype(std::get<n>(std::forward<Value>(value))) {
116 return std::get<n>(std::forward<Value>(value));
120 template<class Class,
122 class MemberFunction {
124 typedef Result (Class::*MemberPtr)();
128 explicit MemberFunction(MemberPtr member)
132 Result operator()(Class&& x) const {
133 return (x.*member_)();
136 Result operator()(Class& x) const {
137 return (x.*member_)();
140 Result operator()(Class* x) const {
141 return (x->*member_)();
145 template<class Class,
147 class ConstMemberFunction{
149 typedef Result (Class::*MemberPtr)() const;
153 explicit ConstMemberFunction(MemberPtr member)
157 Result operator()(const Class& x) const {
158 return (x.*member_)();
161 Result operator()(const Class* x) const {
162 return (x->*member_)();
166 template<class Class,
170 typedef FieldType (Class::*FieldPtr);
174 explicit Field(FieldPtr field)
178 const FieldType& operator()(const Class& x) const {
182 const FieldType& operator()(const Class* x) const {
186 FieldType& operator()(Class& x) const {
190 FieldType& operator()(Class* x) const {
194 FieldType&& operator()(Class&& x) const {
195 return std::move(x.*field_);
201 template<class Value>
202 auto operator()(Value&& value) const ->
203 decltype(std::move(std::forward<Value>(value))) {
204 return std::move(std::forward<Value>(value));
210 template<class Value>
211 auto operator()(Value&& value) const ->
212 decltype(std::forward<Value>(value)) {
213 return std::forward<Value>(value);
217 template <class Dest>
220 template <class Value>
221 Dest operator()(Value&& value) const {
222 return Dest(std::forward<Value>(value));
226 template <class Dest>
229 template <class Value>
230 Dest operator()(Value&& value) const {
231 return ::folly::to<Dest>(std::forward<Value>(value));
235 // Specialization to allow String->StringPiece conversion
237 class To<StringPiece> {
239 StringPiece operator()(StringPiece src) const {
252 template<class Container>
253 struct ValueTypeOfRange {
255 static Container container_;
257 typedef decltype(*std::begin(container_))
259 typedef typename std::decay<decltype(*std::begin(container_))>::type
267 template<class Container,
268 class Value = typename ValueTypeOfRange<Container>::RefType>
269 class ReferencedSource;
271 template<class Value,
272 class Container = std::vector<typename std::decay<Value>::type>>
275 template<class Value, class SequenceImpl>
278 template <class Value>
281 template <class Value, class Distance>
282 class RangeWithStepImpl;
284 template <class Value>
287 template <class Value, class Distance>
288 class SeqWithStepImpl;
290 template <class Value>
293 template<class Value, class Source>
296 template<class Value>
299 template<class Value>
300 class SingleReference;
302 template<class Value>
308 template<class Predicate>
311 template<class Predicate>
314 template<class Predicate>
326 template<class Selector, class Comparer = Less>
329 template<class Selector>
332 template<class Operators>
335 template<class Expected>
361 template<class Predicate>
364 template<class Reducer>
369 template<class Selector,
373 template<class Container>
376 template<template<class, class> class Collection = std::vector,
377 template<class> class Allocator = std::allocator>
378 class CollectTemplate;
380 template<class Collection>
383 template<class Value>
384 struct GeneratorBuilder;
386 template<class Needle>
389 template<class Exception,
396 * Polymorphic wrapper
398 template<class Value>
404 template<class Container,
405 class From = detail::ReferencedSource<const Container>>
406 From fromConst(const Container& source) {
407 return From(&source);
410 template<class Container,
411 class From = detail::ReferencedSource<Container>>
412 From from(Container& source) {
413 return From(&source);
416 template<class Container,
418 typename detail::ValueTypeOfRange<Container>::StorageType,
419 class CopyOf = detail::CopiedSource<Value>>
420 CopyOf fromCopy(Container&& source) {
421 return CopyOf(std::forward<Container>(source));
424 template<class Value,
425 class From = detail::CopiedSource<Value>>
426 From from(std::initializer_list<Value> source) {
430 template<class Container,
431 class From = detail::CopiedSource<typename Container::value_type,
433 From from(Container&& source) {
434 return From(std::move(source));
437 template<class Value, class Impl = detail::RangeImpl<Value>,
438 class Gen = detail::Sequence<Value, Impl>>
439 Gen range(Value begin, Value end) {
440 return Gen{std::move(begin), Impl{std::move(end)}};
443 template<class Value, class Distance,
444 class Impl = detail::RangeWithStepImpl<Value, Distance>,
445 class Gen = detail::Sequence<Value, Impl>>
446 Gen range(Value begin, Value end, Distance step) {
447 return Gen{std::move(begin), Impl{std::move(end), std::move(step)}};
450 template<class Value, class Impl = detail::SeqImpl<Value>,
451 class Gen = detail::Sequence<Value, Impl>>
452 Gen seq(Value first, Value last) {
453 return Gen{std::move(first), Impl{std::move(last)}};
456 template<class Value, class Distance,
457 class Impl = detail::SeqWithStepImpl<Value, Distance>,
458 class Gen = detail::Sequence<Value, Impl>>
459 Gen seq(Value first, Value last, Distance step) {
460 return Gen{std::move(first), Impl{std::move(last), std::move(step)}};
463 template<class Value, class Impl = detail::InfiniteImpl<Value>,
464 class Gen = detail::Sequence<Value, Impl>>
465 Gen seq(Value first) {
466 return Gen{std::move(first), Impl{}};
469 template<class Value,
471 class Yield = detail::Yield<Value, Source>>
472 Yield generator(Source&& source) {
473 return Yield(std::forward<Source>(source));
477 * Create inline generator, used like:
479 * auto gen = GENERATOR(int) { yield(1); yield(2); };
481 #define GENERATOR(TYPE) \
482 ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
483 [=](const std::function<void(TYPE)>& yield)
486 * empty() - for producing empty sequences.
488 template <class Value>
489 detail::Empty<Value> empty() {
495 class Just = typename std::conditional<
496 std::is_reference<Value>::value,
497 detail::SingleReference<typename std::remove_reference<Value>::type>,
498 detail::SingleCopy<Value>>::type>
499 Just just(Value&& value) {
500 return Just(std::forward<Value>(value));
506 template<class Predicate,
507 class Map = detail::Map<Predicate>>
508 Map mapped(Predicate pred = Predicate()) {
509 return Map(std::move(pred));
512 template<class Predicate,
513 class Map = detail::Map<Predicate>>
514 Map map(Predicate pred = Predicate()) {
515 return Map(std::move(pred));
519 * mapOp - Given a generator of generators, maps the application of the given
520 * operator on to each inner gen. Especially useful in aggregating nested data
523 * chunked(samples, 256)
524 * | mapOp(filter(sampleTest) | count)
527 template<class Operator,
528 class Map = detail::Map<detail::Composer<Operator>>>
529 Map mapOp(Operator op) {
530 return Map(detail::Composer<Operator>(std::move(op)));
534 * member(...) - For extracting a member from each value.
536 * vector<string> strings = ...;
537 * auto sizes = from(strings) | member(&string::size);
539 * If a member is const overridden (like 'front()'), pass template parameter
540 * 'Const' to select the const version, or 'Mutable' to select the non-const
543 * auto heads = from(strings) | member<Const>(&string::front);
551 * These exist because MSVC has problems with expression SFINAE in templates
552 * assignment and comparisons don't work properly without being pulled out
553 * of the template declaration
555 template <MemberType Constness> struct ExprIsConst {
557 value = Constness == Const
561 template <MemberType Constness> struct ExprIsMutable {
563 value = Constness == Mutable
567 template<MemberType Constness = Const,
570 class Mem = ConstMemberFunction<Class, Return>,
571 class Map = detail::Map<Mem>>
572 typename std::enable_if<ExprIsConst<Constness>::value, Map>::type
573 member(Return (Class::*member)() const) {
574 return Map(Mem(member));
577 template<MemberType Constness = Mutable,
580 class Mem = MemberFunction<Class, Return>,
581 class Map = detail::Map<Mem>>
582 typename std::enable_if<ExprIsMutable<Constness>::value, Map>::type
583 member(Return (Class::*member)()) {
584 return Map(Mem(member));
588 * field(...) - For extracting a field from each value.
590 * vector<Item> items = ...;
591 * auto names = from(items) | field(&Item::name);
593 * Note that if the values of the generator are rvalues, any non-reference
594 * fields will be rvalues as well. As an example, the code below does not copy
595 * any strings, only moves them:
597 * auto namesVector = from(items)
599 * | field(&Item::name)
602 template<class Class,
604 class Field = Field<Class, FieldType>,
605 class Map = detail::Map<Field>>
606 Map field(FieldType Class::*field) {
607 return Map(Field(field));
610 template<class Predicate,
611 class Filter = detail::Filter<Predicate>>
612 Filter filter(Predicate pred = Predicate()) {
613 return Filter(std::move(pred));
616 template<class Predicate,
617 class All = detail::All<Predicate>>
618 All all(Predicate pred = Predicate()) {
619 return All(std::move(pred));
622 template<class Predicate,
623 class Until = detail::Until<Predicate>>
624 Until until(Predicate pred = Predicate()) {
625 return Until(std::move(pred));
628 template<class Selector,
629 class Comparer = Less,
630 class Order = detail::Order<Selector, Comparer>>
631 Order orderBy(Selector selector = Identity(),
632 Comparer comparer = Comparer()) {
633 return Order(std::move(selector),
634 std::move(comparer));
637 template<class Selector,
638 class Order = detail::Order<Selector, Greater>>
639 Order orderByDescending(Selector selector = Identity()) {
640 return Order(std::move(selector));
643 template<class Selector,
644 class Distinct = detail::Distinct<Selector>>
645 Distinct distinctBy(Selector selector = Identity()) {
646 return Distinct(std::move(selector));
650 class Get = detail::Map<Get<n>>>
655 // construct Dest from each value
656 template <class Dest,
657 class Cast = detail::Map<Cast<Dest>>>
662 // call folly::to on each value
663 template <class Dest,
664 class To = detail::Map<To<Dest>>>
669 template<class Value>
670 detail::TypeAssertion<Value> assert_type() {
679 class FoldLeft = detail::FoldLeft<Seed, Fold>>
680 FoldLeft foldl(Seed seed = Seed(),
681 Fold fold = Fold()) {
682 return FoldLeft(std::move(seed),
686 template<class Reducer,
687 class Reduce = detail::Reduce<Reducer>>
688 Reduce reduce(Reducer reducer = Reducer()) {
689 return Reduce(std::move(reducer));
692 template<class Selector = Identity,
693 class Min = detail::Min<Selector, Less>>
694 Min minBy(Selector selector = Selector()) {
695 return Min(std::move(selector));
698 template<class Selector,
699 class MaxBy = detail::Min<Selector, Greater>>
700 MaxBy maxBy(Selector selector = Selector()) {
701 return MaxBy(std::move(selector));
704 template<class Collection,
705 class Collect = detail::Collect<Collection>>
710 template<template<class, class> class Container = std::vector,
711 template<class> class Allocator = std::allocator,
712 class Collect = detail::CollectTemplate<Container, Allocator>>
717 template<class Collection,
718 class Append = detail::Append<Collection>>
719 Append appendTo(Collection& collection) {
720 return Append(&collection);
723 template<class Needle,
724 class Contains = detail::Contains<typename std::decay<Needle>::type>>
725 Contains contains(Needle&& needle) {
726 return Contains(std::forward<Needle>(needle));
729 template<class Exception,
734 typename std::decay<ErrorHandler>::type>>
735 GuardImpl guard(ErrorHandler&& handler) {
736 return GuardImpl(std::forward<ErrorHandler>(handler));
741 #include <folly/gen/Base-inl.h>
743 #endif // FOLLY_GEN_BASE_H