2 * Copyright 2013 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.
21 #include <type_traits>
26 #include <unordered_set>
28 #include "folly/Range.h"
29 #include "folly/Optional.h"
30 #include "folly/Conv.h"
33 * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ
34 * @author Tom Jackson <tjackson@fb.com>
36 * This library makes it possible to write declarative comprehensions for
37 * processing sequences of values efficiently in C++. The operators should be
38 * familiar to those with experience in functional programming, and the
39 * performance will be virtually identical to the equivalent, boilerplate C++
42 * Generator objects may be created from either an stl-like container (anything
43 * supporting begin() and end()), from sequences of values, or from another
44 * generator (see below). To create a generator that pulls values from a vector,
45 * for example, one could write:
47 * vector<string> names { "Jack", "Jill", "Sara", "Tom" };
48 * auto gen = from(names);
50 * Generators are composed by building new generators out of old ones through
51 * the use of operators. These are reminicent of shell pipelines, and afford
52 * similar composition. Lambda functions are used liberally to describe how to
53 * handle individual values:
56 * | mapped([](const fbstring& name) { return name.size(); });
58 * Generators are lazy; they don't actually perform any work until they need to.
59 * As an example, the 'lengths' generator (above) won't actually invoke the
60 * provided lambda until values are needed:
62 * auto lengthVector = lengths | as<std::vector>();
63 * auto totalLength = lengths | sum;
65 * 'auto' is useful in here because the actual types of the generators objects
66 * are usually complicated and implementation-sensitive.
68 * If a simpler type is desired (for returning, as an example), VirtualGen<T>
69 * may be used to wrap the generator in a polymorphic wrapper:
71 * VirtualGen<float> powersOfE() {
72 * return seq(1) | mapped(&expf);
75 * To learn more about this library, including the use of infinite generators,
76 * see the examples in the comments, or the docs (coming soon).
79 namespace folly { namespace gen {
81 template<class Value, class Self>
87 class EmptySequence : public std::exception {
89 virtual const char* what() const noexcept {
90 return "This operation cannot be called on an empty sequence";
98 auto operator()(const First& first, const Second& second) const ->
99 decltype(first < second) {
100 return first < second;
106 template<class First,
108 auto operator()(const First& first, const Second& second) const ->
109 decltype(first > second) {
110 return first > second;
117 template<class Value>
118 auto operator()(Value&& value) const ->
119 decltype(std::get<n>(std::forward<Value>(value))) {
120 return std::get<n>(std::forward<Value>(value));
124 template<class Class,
126 class MemberFunction {
128 typedef Result (Class::*MemberPtr)();
132 explicit MemberFunction(MemberPtr 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_)();
162 template<class Class,
166 typedef FieldType (Class::*FieldPtr);
170 explicit Field(FieldPtr field)
174 const FieldType& operator()(const Class& x) const {
178 FieldType& operator()(Class& x) const {
182 FieldType&& operator()(Class&& x) const {
183 return std::move(x.*field_);
189 template<class Value>
190 auto operator()(Value&& value) const ->
191 decltype(std::move(std::forward<Value>(value))) {
192 return std::move(std::forward<Value>(value));
198 template<class Value>
199 auto operator()(Value&& value) const ->
200 decltype(std::forward<Value>(value)) {
201 return std::forward<Value>(value);
205 template <class Dest>
208 template <class Value>
209 Dest operator()(Value&& value) const {
210 return Dest(std::forward<Value>(value));
214 template <class Dest>
217 template <class Value>
218 Dest operator()(Value&& value) const {
219 return ::folly::to<Dest>(std::forward<Value>(value));
223 // Specialization to allow String->StringPiece conversion
225 class To<StringPiece> {
227 StringPiece operator()(StringPiece src) const {
240 template<class Container>
241 struct ValueTypeOfRange {
243 static Container container_;
245 typedef decltype(*std::begin(container_))
247 typedef typename std::decay<decltype(*std::begin(container_))>::type
255 template<class Container,
256 class Value = typename ValueTypeOfRange<Container>::RefType>
257 class ReferencedSource;
259 template<class Value,
260 class Container = std::vector<typename std::decay<Value>::type>>
263 template<class Value, bool endless = false, bool endInclusive = false>
266 template<class Value, class First, class Second>
269 template<class Value, class Source>
272 template<class Value>
279 template<class Predicate>
282 template<class Predicate>
285 template<class Predicate>
295 template<class Selector, class Comparer = Less>
298 template<class Selector>
301 template<class First, class Second>
304 template<class Expected>
328 template<class Predicate>
331 template<class Reducer>
336 template<class Selector,
340 template<class Container>
343 template<template<class, class> class Collection = std::vector,
344 template<class> class Allocator = std::allocator>
345 class CollectTemplate;
347 template<class Collection>
350 template<class Value>
351 struct GeneratorBuilder;
353 template<class Needle>
356 template<class Exception,
363 * Polymorphic wrapper
365 template<class Value>
371 template<class Container,
372 class From = detail::ReferencedSource<const Container>>
373 From fromConst(const Container& source) {
374 return From(&source);
377 template<class Container,
378 class From = detail::ReferencedSource<Container>>
379 From from(Container& source) {
380 return From(&source);
383 template<class Container,
385 typename detail::ValueTypeOfRange<Container>::StorageType,
386 class CopyOf = detail::CopiedSource<Value>>
387 CopyOf fromCopy(Container&& source) {
388 return CopyOf(std::forward<Container>(source));
391 template<class Value,
392 class From = detail::CopiedSource<Value>>
393 From from(std::initializer_list<Value> source) {
397 template<class Container,
398 class From = detail::CopiedSource<typename Container::value_type,
400 From from(Container&& source) {
401 return From(std::move(source));
404 template<class Value, class Gen = detail::Sequence<Value, false, false>>
405 Gen range(Value begin, Value end) {
406 return Gen(begin, end);
409 template<class Value,
410 class Gen = detail::Sequence<Value, false, true>>
411 Gen seq(Value first, Value last) {
412 return Gen(first, last);
415 template<class Value,
416 class Gen = detail::Sequence<Value, true>>
417 Gen seq(Value begin) {
421 template<class Value,
423 class Yield = detail::Yield<Value, Source>>
424 Yield generator(Source&& source) {
425 return Yield(std::forward<Source>(source));
429 * Create inline generator, used like:
431 * auto gen = GENERATOR(int) { yield(1); yield(2); };
433 #define GENERATOR(TYPE) \
434 ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
435 [=](const std::function<void(TYPE)>& yield)
438 * empty() - for producing empty sequences.
440 template<class Value>
441 detail::Empty<Value> empty() {
448 template<class Predicate,
449 class Map = detail::Map<Predicate>>
450 Map mapped(Predicate pred = Predicate()) {
451 return Map(std::move(pred));
454 template<class Predicate,
455 class Map = detail::Map<Predicate>>
456 Map map(Predicate pred = Predicate()) {
457 return Map(std::move(pred));
461 * member(...) - For extracting a member from each value.
463 * vector<string> strings = ...;
464 * auto sizes = from(strings) | member(&string::size);
466 * If a member is const overridden (like 'front()'), pass template parameter
467 * 'Const' to select the const version, or 'Mutable' to select the non-const
470 * auto heads = from(strings) | member<Const>(&string::front);
477 template<MemberType Constness = Const,
480 class Mem = ConstMemberFunction<Class, Return>,
481 class Map = detail::Map<Mem>>
482 typename std::enable_if<Constness == Const, Map>::type
483 member(Return (Class::*member)() const) {
484 return Map(Mem(member));
487 template<MemberType Constness = Mutable,
490 class Mem = MemberFunction<Class, Return>,
491 class Map = detail::Map<Mem>>
492 typename std::enable_if<Constness == Mutable, Map>::type
493 member(Return (Class::*member)()) {
494 return Map(Mem(member));
498 * field(...) - For extracting a field from each value.
500 * vector<Item> items = ...;
501 * auto names = from(items) | field(&Item::name);
503 * Note that if the values of the generator are rvalues, any non-reference
504 * fields will be rvalues as well. As an example, the code below does not copy
505 * any strings, only moves them:
507 * auto namesVector = from(items)
509 * | field(&Item::name)
512 template<class Class,
514 class Field = Field<Class, FieldType>,
515 class Map = detail::Map<Field>>
516 Map field(FieldType Class::*field) {
517 return Map(Field(field));
520 template<class Predicate,
521 class Filter = detail::Filter<Predicate>>
522 Filter filter(Predicate pred = Predicate()) {
523 return Filter(std::move(pred));
526 template<class Predicate,
527 class All = detail::All<Predicate>>
528 All all(Predicate pred = Predicate()) {
529 return All(std::move(pred));
532 template<class Predicate,
533 class Until = detail::Until<Predicate>>
534 Until until(Predicate pred = Predicate()) {
535 return Until(std::move(pred));
538 template<class Selector,
539 class Comparer = Less,
540 class Order = detail::Order<Selector, Comparer>>
541 Order orderBy(Selector selector = Identity(),
542 Comparer comparer = Comparer()) {
543 return Order(std::move(selector),
544 std::move(comparer));
547 template<class Selector,
548 class Order = detail::Order<Selector, Greater>>
549 Order orderByDescending(Selector selector = Identity()) {
550 return Order(std::move(selector));
553 template<class Selector,
554 class Distinct = detail::Distinct<Selector>>
555 Distinct distinctBy(Selector selector = Identity()) {
556 return Distinct(std::move(selector));
560 class Get = detail::Map<Get<n>>>
565 // construct Dest from each value
566 template <class Dest,
567 class Cast = detail::Map<Cast<Dest>>>
572 // call folly::to on each value
573 template <class Dest,
574 class To = detail::Map<To<Dest>>>
579 template<class Value>
580 detail::TypeAssertion<Value> assert_type() {
589 class FoldLeft = detail::FoldLeft<Seed, Fold>>
590 FoldLeft foldl(Seed seed = Seed(),
591 Fold fold = Fold()) {
592 return FoldLeft(std::move(seed),
596 template<class Reducer,
597 class Reduce = detail::Reduce<Reducer>>
598 Reduce reduce(Reducer reducer = Reducer()) {
599 return Reduce(std::move(reducer));
602 template<class Selector = Identity,
603 class Min = detail::Min<Selector, Less>>
604 Min minBy(Selector selector = Selector()) {
605 return Min(std::move(selector));
608 template<class Selector,
609 class MaxBy = detail::Min<Selector, Greater>>
610 MaxBy maxBy(Selector selector = Selector()) {
611 return MaxBy(std::move(selector));
614 template<class Collection,
615 class Collect = detail::Collect<Collection>>
620 template<template<class, class> class Container = std::vector,
621 template<class> class Allocator = std::allocator,
622 class Collect = detail::CollectTemplate<Container, Allocator>>
627 template<class Collection,
628 class Append = detail::Append<Collection>>
629 Append appendTo(Collection& collection) {
630 return Append(&collection);
633 template<class Needle,
634 class Contains = detail::Contains<typename std::decay<Needle>::type>>
635 Contains contains(Needle&& needle) {
636 return Contains(std::forward<Needle>(needle));
639 template<class Exception,
644 typename std::decay<ErrorHandler>::type>>
645 GuardImpl guard(ErrorHandler&& handler) {
646 return GuardImpl(std::forward<ErrorHandler>(handler));
651 #include "folly/experimental/Gen-inl.h"