a550393554a6fa490b633753886b1b417c03ee97
[folly.git] / folly / gen / Base.h
1 /*
2  * Copyright 2017 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 reminicent 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
83 namespace folly {
84 namespace gen {
85
86 class 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
95 class 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
104 template <int n>
105 class 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
114 template <class Class, class Result>
115 class MemberFunction {
116  public:
117   typedef Result (Class::*MemberPtr)();
118  private:
119   MemberPtr member_;
120  public:
121   explicit MemberFunction(MemberPtr member)
122     : member_(member)
123   {}
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
138 template <class Class, class Result>
139 class ConstMemberFunction{
140  public:
141   typedef Result (Class::*MemberPtr)() const;
142  private:
143   MemberPtr member_;
144  public:
145   explicit ConstMemberFunction(MemberPtr member)
146     : member_(member)
147   {}
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
158 template <class Class, class FieldType>
159 class Field {
160  public:
161   typedef FieldType (Class::*FieldPtr);
162  private:
163   FieldPtr field_;
164  public:
165   explicit Field(FieldPtr field)
166     : field_(field)
167   {}
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
190 class 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  */
202 template <class Predicate>
203 class Negate {
204   Predicate pred_;
205
206  public:
207   Negate() = default;
208
209   explicit Negate(Predicate pred)
210     : pred_(std::move(pred))
211   {}
212
213   template <class Arg>
214   bool operator()(Arg&& arg) const {
215     return !pred_(std::forward<Arg>(arg));
216   }
217 };
218 template <class Predicate>
219 Negate<Predicate> negate(Predicate pred) {
220   return Negate<Predicate>(std::move(pred));
221 }
222
223 template <class Dest>
224 class Cast {
225  public:
226   template <class Value>
227   Dest operator()(Value&& value) const {
228     return Dest(std::forward<Value>(value));
229   }
230 };
231
232 template <class Dest>
233 class To {
234  public:
235   template <class Value>
236   Dest operator()(Value&& value) const {
237     return ::folly::to<Dest>(std::forward<Value>(value));
238   }
239 };
240
241 // Specialization to allow String->StringPiece conversion
242 template <>
243 class To<StringPiece> {
244  public:
245   StringPiece operator()(StringPiece src) const {
246     return src;
247   }
248 };
249
250 template <class Key, class Value>
251 class Group;
252
253 namespace detail {
254
255 template <class Self>
256 struct FBounded;
257
258 /*
259  * Type Traits
260  */
261 template <class Container>
262 struct ValueTypeOfRange {
263  public:
264   using RefType = decltype(*std::begin(std::declval<Container&>()));
265   using StorageType = typename std::decay<RefType>::type;
266 };
267
268
269 /*
270  * Sources
271  */
272 template <
273     class Container,
274     class Value = typename ValueTypeOfRange<Container>::RefType>
275 class ReferencedSource;
276
277 template <
278     class Value,
279     class Container = std::vector<typename std::decay<Value>::type>>
280 class CopiedSource;
281
282 template <class Value, class SequenceImpl>
283 class Sequence;
284
285 template <class Value>
286 class RangeImpl;
287
288 template <class Value, class Distance>
289 class RangeWithStepImpl;
290
291 template <class Value>
292 class SeqImpl;
293
294 template <class Value, class Distance>
295 class SeqWithStepImpl;
296
297 template <class Value>
298 class InfiniteImpl;
299
300 template <class Value, class Source>
301 class Yield;
302
303 template <class Value>
304 class Empty;
305
306 template <class Value>
307 class SingleReference;
308
309 template <class Value>
310 class SingleCopy;
311
312 /*
313  * Operators
314  */
315 template <class Predicate>
316 class Map;
317
318 template <class Predicate>
319 class Filter;
320
321 template <class Predicate>
322 class Until;
323
324 class Take;
325
326 class Stride;
327
328 template <class Rand>
329 class Sample;
330
331 class Skip;
332
333 template <class Visitor>
334 class Visit;
335
336 template <class Selector, class Comparer = Less>
337 class Order;
338
339 template <class Selector>
340 class GroupBy;
341
342 template <class Selector>
343 class Distinct;
344
345 template <class Operators>
346 class Composer;
347
348 template <class Expected>
349 class TypeAssertion;
350
351 class Concat;
352
353 class RangeConcat;
354
355 template <bool forever>
356 class Cycle;
357
358 class Batch;
359
360 class Window;
361
362 class Dereference;
363
364 class Indirect;
365
366 /*
367  * Sinks
368  */
369 template <class Seed, class Fold>
370 class FoldLeft;
371
372 class First;
373
374 template <bool result>
375 class IsEmpty;
376
377 template <class Reducer>
378 class Reduce;
379
380 class Sum;
381
382 template <class Selector, class Comparer>
383 class Min;
384
385 template <class Container>
386 class Collect;
387
388 template <
389     template <class, class> class Collection = std::vector,
390     template <class> class Allocator = std::allocator>
391 class CollectTemplate;
392
393 template <class Collection>
394 class Append;
395
396 template <class Value>
397 struct GeneratorBuilder;
398
399 template <class Needle>
400 class Contains;
401
402 template <class Exception, class ErrorHandler>
403 class GuardImpl;
404
405 template <class T>
406 class UnwrapOr;
407
408 class Unwrap;
409
410 } // namespace detail
411
412 /**
413  * Polymorphic wrapper
414  **/
415 template <class Value>
416 class VirtualGen;
417
418 /*
419  * Source Factories
420  */
421 template <
422     class Container,
423     class From = detail::ReferencedSource<const Container>>
424 From fromConst(const Container& source) {
425   return From(&source);
426 }
427
428 template <class Container, class From = detail::ReferencedSource<Container>>
429 From from(Container& source) {
430   return From(&source);
431 }
432
433 template <
434     class Container,
435     class Value = typename detail::ValueTypeOfRange<Container>::StorageType,
436     class CopyOf = detail::CopiedSource<Value>>
437 CopyOf fromCopy(Container&& source) {
438   return CopyOf(std::forward<Container>(source));
439 }
440
441 template <class Value, class From = detail::CopiedSource<Value>>
442 From from(std::initializer_list<Value> source) {
443   return From(source);
444 }
445
446 template <
447     class Container,
448     class From =
449         detail::CopiedSource<typename Container::value_type, Container>>
450 From from(Container&& source) {
451   return From(std::move(source));
452 }
453
454 template <
455     class Value,
456     class Impl = detail::RangeImpl<Value>,
457     class Gen = detail::Sequence<Value, Impl>>
458 Gen range(Value begin, Value end) {
459   return Gen{std::move(begin), Impl{std::move(end)}};
460 }
461
462 template <
463     class Value,
464     class Distance,
465     class Impl = detail::RangeWithStepImpl<Value, Distance>,
466     class Gen = detail::Sequence<Value, Impl>>
467 Gen range(Value begin, Value end, Distance step) {
468   return Gen{std::move(begin), Impl{std::move(end), std::move(step)}};
469 }
470
471 template <
472     class Value,
473     class Impl = detail::SeqImpl<Value>,
474     class Gen = detail::Sequence<Value, Impl>>
475 Gen seq(Value first, Value last) {
476   return Gen{std::move(first), Impl{std::move(last)}};
477 }
478
479 template <
480     class Value,
481     class Distance,
482     class Impl = detail::SeqWithStepImpl<Value, Distance>,
483     class Gen = detail::Sequence<Value, Impl>>
484 Gen seq(Value first, Value last, Distance step) {
485   return Gen{std::move(first), Impl{std::move(last), std::move(step)}};
486 }
487
488 template <
489     class Value,
490     class Impl = detail::InfiniteImpl<Value>,
491     class Gen = detail::Sequence<Value, Impl>>
492 Gen seq(Value first) {
493   return Gen{std::move(first), Impl{}};
494 }
495
496 template <class Value, class Source, class Yield = detail::Yield<Value, Source>>
497 Yield generator(Source&& source) {
498   return Yield(std::forward<Source>(source));
499 }
500
501 /*
502  * Create inline generator, used like:
503  *
504  *  auto gen = GENERATOR(int) { yield(1); yield(2); };
505  */
506 #define GENERATOR(TYPE)                            \
507   ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
508    [=](const std::function<void(TYPE)>& yield)
509
510 /*
511  * empty() - for producing empty sequences.
512  */
513 template <class Value>
514 detail::Empty<Value> empty() {
515   return {};
516 }
517
518 template <
519     class Value,
520     class Just = typename std::conditional<
521         std::is_reference<Value>::value,
522         detail::SingleReference<typename std::remove_reference<Value>::type>,
523         detail::SingleCopy<Value>>::type>
524 Just just(Value&& value) {
525   return Just(std::forward<Value>(value));
526 }
527
528 /*
529  * Operator Factories
530  */
531 template <class Predicate, class Map = detail::Map<Predicate>>
532 Map mapped(Predicate pred = Predicate()) {
533   return Map(std::move(pred));
534 }
535
536 template <class Predicate, class Map = detail::Map<Predicate>>
537 Map map(Predicate pred = Predicate()) {
538   return Map(std::move(pred));
539 }
540
541 /**
542  * mapOp - Given a generator of generators, maps the application of the given
543  * operator on to each inner gen. Especially useful in aggregating nested data
544  * structures:
545  *
546  *   chunked(samples, 256)
547  *     | mapOp(filter(sampleTest) | count)
548  *     | sum;
549  */
550 template <class Operator, class Map = detail::Map<detail::Composer<Operator>>>
551 Map mapOp(Operator op) {
552   return Map(detail::Composer<Operator>(std::move(op)));
553 }
554
555 /*
556  * member(...) - For extracting a member from each value.
557  *
558  *  vector<string> strings = ...;
559  *  auto sizes = from(strings) | member(&string::size);
560  *
561  * If a member is const overridden (like 'front()'), pass template parameter
562  * 'Const' to select the const version, or 'Mutable' to select the non-const
563  * version:
564  *
565  *  auto heads = from(strings) | member<Const>(&string::front);
566  */
567 enum MemberType {
568   Const,
569   Mutable
570 };
571
572 /**
573  * These exist because MSVC has problems with expression SFINAE in templates
574  * assignment and comparisons don't work properly without being pulled out
575  * of the template declaration
576  */
577 template <MemberType Constness>
578 struct ExprIsConst {
579   enum {
580     value = Constness == Const
581   };
582 };
583
584 template <MemberType Constness>
585 struct ExprIsMutable {
586   enum {
587     value = Constness == Mutable
588   };
589 };
590
591 template <
592     MemberType Constness = Const,
593     class Class,
594     class Return,
595     class Mem = ConstMemberFunction<Class, Return>,
596     class Map = detail::Map<Mem>>
597 typename std::enable_if<ExprIsConst<Constness>::value, Map>::type
598 member(Return (Class::*member)() const) {
599   return Map(Mem(member));
600 }
601
602 template <
603     MemberType Constness = Mutable,
604     class Class,
605     class Return,
606     class Mem = MemberFunction<Class, Return>,
607     class Map = detail::Map<Mem>>
608 typename std::enable_if<ExprIsMutable<Constness>::value, Map>::type
609 member(Return (Class::*member)()) {
610   return Map(Mem(member));
611 }
612
613 /*
614  * field(...) - For extracting a field from each value.
615  *
616  *  vector<Item> items = ...;
617  *  auto names = from(items) | field(&Item::name);
618  *
619  * Note that if the values of the generator are rvalues, any non-reference
620  * fields will be rvalues as well. As an example, the code below does not copy
621  * any strings, only moves them:
622  *
623  *  auto namesVector = from(items)
624  *                   | move
625  *                   | field(&Item::name)
626  *                   | as<vector>();
627  */
628 template <
629     class Class,
630     class FieldType,
631     class Field = Field<Class, FieldType>,
632     class Map = detail::Map<Field>>
633 Map field(FieldType Class::*field) {
634   return Map(Field(field));
635 }
636
637 template <class Predicate = Identity, class Filter = detail::Filter<Predicate>>
638 Filter filter(Predicate pred = Predicate()) {
639   return Filter(std::move(pred));
640 }
641
642 template <class Visitor = Ignore, class Visit = detail::Visit<Visitor>>
643 Visit visit(Visitor visitor = Visitor()) {
644   return Visit(std::move(visitor));
645 }
646
647 template <class Predicate, class Until = detail::Until<Predicate>>
648 Until until(Predicate pred = Predicate()) {
649   return Until(std::move(pred));
650 }
651
652 template <
653     class Selector = Identity,
654     class Comparer = Less,
655     class Order = detail::Order<Selector, Comparer>>
656 Order orderBy(Selector selector = Selector(),
657               Comparer comparer = Comparer()) {
658   return Order(std::move(selector),
659                std::move(comparer));
660 }
661
662 template <
663     class Selector = Identity,
664     class Order = detail::Order<Selector, Greater>>
665 Order orderByDescending(Selector selector = Selector()) {
666   return Order(std::move(selector));
667 }
668
669 template <class Selector = Identity, class GroupBy = detail::GroupBy<Selector>>
670 GroupBy groupBy(Selector selector = Selector()) {
671   return GroupBy(std::move(selector));
672 }
673
674 template <
675     class Selector = Identity,
676     class Distinct = detail::Distinct<Selector>>
677 Distinct distinctBy(Selector selector = Selector()) {
678   return Distinct(std::move(selector));
679 }
680
681 template <int n, class Get = detail::Map<Get<n>>>
682 Get get() {
683   return Get();
684 }
685
686 // construct Dest from each value
687 template <class Dest, class Cast = detail::Map<Cast<Dest>>>
688 Cast eachAs() {
689   return Cast();
690 }
691
692 // call folly::to on each value
693 template <class Dest, class To = detail::Map<To<Dest>>>
694 To eachTo() {
695   return To();
696 }
697
698 template <class Value>
699 detail::TypeAssertion<Value> assert_type() {
700   return {};
701 }
702
703 /*
704  * Sink Factories
705  */
706
707 /**
708  * any() - For determining if any value in a sequence satisfies a predicate.
709  *
710  * The following is an example for checking if any computer is broken:
711  *
712  *   bool schrepIsMad = from(computers) | any(isBroken);
713  *
714  * (because everyone knows Schrep hates broken computers).
715  *
716  * Note that if no predicate is provided, 'any()' checks if any of the values
717  * are true when cased to bool. To check if any of the scores are nonZero:
718  *
719  *   bool somebodyScored = from(scores) | any();
720  *
721  * Note: Passing an empty sequence through 'any()' will always return false. In
722  * fact, 'any()' is equivilent to the composition of 'filter()' and 'notEmpty'.
723  *
724  *   from(source) | any(pred) == from(source) | filter(pred) | notEmpty
725  */
726
727 template <
728     class Predicate = Identity,
729     class Filter = detail::Filter<Predicate>,
730     class NotEmpty = detail::IsEmpty<false>,
731     class Composed = detail::Composed<Filter, NotEmpty>>
732 Composed any(Predicate pred = Predicate()) {
733   return Composed(Filter(std::move(pred)), NotEmpty());
734 }
735
736 /**
737  * all() - For determining whether all values in a sequence satisfy a predicate.
738  *
739  * The following is an example for checking if all members of a team are cool:
740  *
741  *   bool isAwesomeTeam = from(team) | all(isCool);
742  *
743  * Note that if no predicate is provided, 'all()'' checks if all of the values
744  * are true when cased to bool.
745  * The following makes sure none of 'pointers' are nullptr:
746  *
747  *   bool allNonNull = from(pointers) | all();
748  *
749  * Note: Passing an empty sequence through 'all()' will always return true. In
750  * fact, 'all()' is equivilent to the composition of 'filter()' with the
751  * reversed predicate and 'isEmpty'.
752  *
753  *   from(source) | all(pred) == from(source) | filter(negate(pred)) | isEmpty
754  */
755 template <
756     class Predicate = Identity,
757     class Filter = detail::Filter<Negate<Predicate>>,
758     class IsEmpty = detail::IsEmpty<true>,
759     class Composed = detail::Composed<Filter, IsEmpty>>
760 Composed all(Predicate pred = Predicate()) {
761   return Composed(Filter(std::move(negate(pred))), IsEmpty());
762 }
763
764 template <class Seed, class Fold, class FoldLeft = detail::FoldLeft<Seed, Fold>>
765 FoldLeft foldl(Seed seed = Seed(),
766                Fold fold = Fold()) {
767   return FoldLeft(std::move(seed),
768                   std::move(fold));
769 }
770
771 template <class Reducer, class Reduce = detail::Reduce<Reducer>>
772 Reduce reduce(Reducer reducer = Reducer()) {
773   return Reduce(std::move(reducer));
774 }
775
776 template <class Selector = Identity, class Min = detail::Min<Selector, Less>>
777 Min minBy(Selector selector = Selector()) {
778   return Min(std::move(selector));
779 }
780
781 template <class Selector, class MaxBy = detail::Min<Selector, Greater>>
782 MaxBy maxBy(Selector selector = Selector()) {
783   return MaxBy(std::move(selector));
784 }
785
786 template <class Collection, class Collect = detail::Collect<Collection>>
787 Collect as() {
788   return Collect();
789 }
790
791 template <
792     template <class, class> class Container = std::vector,
793     template <class> class Allocator = std::allocator,
794     class Collect = detail::CollectTemplate<Container, Allocator>>
795 Collect as() {
796   return Collect();
797 }
798
799 template <class Collection, class Append = detail::Append<Collection>>
800 Append appendTo(Collection& collection) {
801   return Append(&collection);
802 }
803
804 template <
805     class Needle,
806     class Contains = detail::Contains<typename std::decay<Needle>::type>>
807 Contains contains(Needle&& needle) {
808   return Contains(std::forward<Needle>(needle));
809 }
810
811 template <
812     class Exception,
813     class ErrorHandler,
814     class GuardImpl =
815         detail::GuardImpl<Exception, typename std::decay<ErrorHandler>::type>>
816 GuardImpl guard(ErrorHandler&& handler) {
817   return GuardImpl(std::forward<ErrorHandler>(handler));
818 }
819
820 template <
821     class Fallback,
822     class UnwrapOr = detail::UnwrapOr<typename std::decay<Fallback>::type>>
823 UnwrapOr unwrapOr(Fallback&& fallback) {
824   return UnwrapOr(std::forward<Fallback>(fallback));
825 }
826
827 } // namespace gen
828 } // namespace folly
829
830 #include <folly/gen/Base-inl.h>