From faf7b5c67ce08ec1fbdd847349bf6f95aa46dd86 Mon Sep 17 00:00:00 2001 From: Tom Jackson Date: Wed, 29 Jan 2014 13:50:24 -0800 Subject: [PATCH] Promoting out of experimental Summary: At long last, promoting this out of experimental. Also, while I'm at it, I've separated the tests and benchmarks into their corresponding parts. Redirect headers provided. Test Plan: Unit tests, contbuild. Reviewed By: marcelo.juchem@fb.com FB internal diff: D1151911 --- folly/experimental/CombineGen.h | 34 +- folly/experimental/FileGen.h | 60 +- folly/experimental/Gen.h | 638 +--------------- folly/experimental/StringGen.h | 143 +--- folly/experimental/test/GenBenchmark.cpp | 678 ------------------ .../Gen-inl.h => gen/Base-inl.h} | 354 +-------- folly/gen/Base.h | 642 +++++++++++++++++ .../CombineGen-inl.h => gen/Combine-inl.h} | 4 +- folly/gen/Combine.h | 45 ++ folly/gen/Core-inl.h | 364 ++++++++++ folly/gen/Core.h | 45 ++ .../FileGen-inl.h => gen/File-inl.h} | 6 +- folly/gen/File.h | 72 ++ .../StringGen-inl.h => gen/String-inl.h} | 4 +- folly/gen/String.h | 155 ++++ folly/gen/test/BaseBenchmark.cpp | 344 +++++++++ .../GenTest.cpp => gen/test/BaseTest.cpp} | 441 +----------- folly/gen/test/CombineTest.cpp | 167 +++++ folly/gen/test/FileBenchmark.cpp | 70 ++ folly/gen/test/FileTest.cpp | 80 +++ folly/gen/test/StringBenchmark.cpp | 329 +++++++++ folly/gen/test/StringTest.cpp | 286 ++++++++ 22 files changed, 2634 insertions(+), 2327 deletions(-) delete mode 100644 folly/experimental/test/GenBenchmark.cpp rename folly/{experimental/Gen-inl.h => gen/Base-inl.h} (82%) create mode 100644 folly/gen/Base.h rename folly/{experimental/CombineGen-inl.h => gen/Combine-inl.h} (98%) create mode 100644 folly/gen/Combine.h create mode 100644 folly/gen/Core-inl.h create mode 100644 folly/gen/Core.h rename folly/{experimental/FileGen-inl.h => gen/File-inl.h} (96%) create mode 100644 folly/gen/File.h rename folly/{experimental/StringGen-inl.h => gen/String-inl.h} (98%) create mode 100644 folly/gen/String.h create mode 100644 folly/gen/test/BaseBenchmark.cpp rename folly/{experimental/test/GenTest.cpp => gen/test/BaseTest.cpp} (68%) create mode 100644 folly/gen/test/CombineTest.cpp create mode 100644 folly/gen/test/FileBenchmark.cpp create mode 100644 folly/gen/test/FileTest.cpp create mode 100644 folly/gen/test/StringBenchmark.cpp create mode 100644 folly/gen/test/StringTest.cpp diff --git a/folly/experimental/CombineGen.h b/folly/experimental/CombineGen.h index b3bc3bb0..82e5b0d9 100644 --- a/folly/experimental/CombineGen.h +++ b/folly/experimental/CombineGen.h @@ -13,35 +13,5 @@ * See the License for the specific language governing permissions and * limitations under the License. */ - -#ifndef FOLLY_COMBINEGEN_H_ -#define FOLLY_COMBINEGEN_H_ - -#include "folly/experimental/Gen.h" - -namespace folly { -namespace gen { -namespace detail { - -template -class Interleave; - -template -class Zip; - -} // namespace detail - -template::type, - class Interleave = detail::Interleave> -Interleave interleave(Source2&& source2) { - return Interleave(std::forward(source2)); -} - -} // namespace gen -} // namespace folly - -#include "folly/experimental/CombineGen-inl.h" - -#endif /* FOLLY_COMBINEGEN_H_ */ - +#pragma GCC message "folly::gen has moved to folly/gen/*.h" +#include "folly/gen/Combine.h" diff --git a/folly/experimental/FileGen.h b/folly/experimental/FileGen.h index e9ecfa76..7b8ac658 100644 --- a/folly/experimental/FileGen.h +++ b/folly/experimental/FileGen.h @@ -13,61 +13,5 @@ * See the License for the specific language governing permissions and * limitations under the License. */ - -#ifndef FOLLY_FILEGEN_H_ -#define FOLLY_FILEGEN_H_ - -#include "folly/File.h" -#include "folly/experimental/Gen.h" -#include "folly/io/IOBuf.h" - -namespace folly { -namespace gen { - -namespace detail { -class FileReader; -class FileWriter; -} // namespace detail - -/** - * Generator that reads from a file with a buffer of the given size. - * Reads must be buffered (the generator interface expects the generator - * to hold each value). - */ -template -S fromFile(File file, size_t bufferSize=4096) { - return S(std::move(file), IOBuf::create(bufferSize)); -} - -/** - * Generator that reads from a file using a given buffer. - */ -template -S fromFile(File file, std::unique_ptr buffer) { - return S(std::move(file), std::move(buffer)); -} - -/** - * Sink that writes to a file with a buffer of the given size. - * If bufferSize is 0, writes will be unbuffered. - */ -template -S toFile(File file, size_t bufferSize=4096) { - return S(std::move(file), bufferSize ? nullptr : IOBuf::create(bufferSize)); -} - -/** - * Sink that writes to a file using a given buffer. - * If the buffer is nullptr, writes will be unbuffered. - */ -template -S toFile(File file, std::unique_ptr buffer) { - return S(std::move(file), std::move(buffer)); -} - -}} // !folly::gen - -#include "folly/experimental/FileGen-inl.h" - -#endif /* FOLLY_FILEGEN_H_ */ - +#pragma message "folly::gen has moved to folly/gen/*.h" +#include "folly/gen/File.h" diff --git a/folly/experimental/Gen.h b/folly/experimental/Gen.h index fdbb712c..3142b541 100644 --- a/folly/experimental/Gen.h +++ b/folly/experimental/Gen.h @@ -13,639 +13,5 @@ * See the License for the specific language governing permissions and * limitations under the License. */ - -#pragma once - -#include -#include -#include -#include -#include -#include -#include -#include - -#include "folly/Range.h" -#include "folly/Optional.h" -#include "folly/Conv.h" - -/** - * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ - * @author Tom Jackson - * - * This library makes it possible to write declarative comprehensions for - * processing sequences of values efficiently in C++. The operators should be - * familiar to those with experience in functional programming, and the - * performance will be virtually identical to the equivalent, boilerplate C++ - * implementations. - * - * Generator objects may be created from either an stl-like container (anything - * supporting begin() and end()), from sequences of values, or from another - * generator (see below). To create a generator that pulls values from a vector, - * for example, one could write: - * - * vector names { "Jack", "Jill", "Sara", "Tom" }; - * auto gen = from(names); - * - * Generators are composed by building new generators out of old ones through - * the use of operators. These are reminicent of shell pipelines, and afford - * similar composition. Lambda functions are used liberally to describe how to - * handle individual values: - * - * auto lengths = gen - * | mapped([](const fbstring& name) { return name.size(); }); - * - * Generators are lazy; they don't actually perform any work until they need to. - * As an example, the 'lengths' generator (above) won't actually invoke the - * provided lambda until values are needed: - * - * auto lengthVector = lengths | as(); - * auto totalLength = lengths | sum; - * - * 'auto' is useful in here because the actual types of the generators objects - * are usually complicated and implementation-sensitive. - * - * If a simpler type is desired (for returning, as an example), VirtualGen - * may be used to wrap the generator in a polymorphic wrapper: - * - * VirtualGen powersOfE() { - * return seq(1) | mapped(&expf); - * } - * - * To learn more about this library, including the use of infinite generators, - * see the examples in the comments, or the docs (coming soon). -*/ - -namespace folly { namespace gen { - -template -class GenImpl; - -template -class Operator; - -class EmptySequence : public std::exception { -public: - virtual const char* what() const noexcept { - return "This operation cannot be called on an empty sequence"; - } -}; - -class Less { -public: - template - auto operator()(const First& first, const Second& second) const -> - decltype(first < second) { - return first < second; - } -}; - -class Greater { -public: - template - auto operator()(const First& first, const Second& second) const -> - decltype(first > second) { - return first > second; - } -}; - -template -class Get { -public: - template - auto operator()(Value&& value) const -> - decltype(std::get(std::forward(value))) { - return std::get(std::forward(value)); - } -}; - -template -class MemberFunction { - public: - typedef Result (Class::*MemberPtr)(); - private: - MemberPtr member_; - public: - explicit MemberFunction(MemberPtr member) - : member_(member) - {} - - Result operator()(Class&& x) const { - return (x.*member_)(); - } - - Result operator()(Class& x) const { - return (x.*member_)(); - } -}; - -template -class ConstMemberFunction{ - public: - typedef Result (Class::*MemberPtr)() const; - private: - MemberPtr member_; - public: - explicit ConstMemberFunction(MemberPtr member) - : member_(member) - {} - - Result operator()(const Class& x) const { - return (x.*member_)(); - } -}; - -template -class Field { - public: - typedef FieldType (Class::*FieldPtr); - private: - FieldPtr field_; - public: - explicit Field(FieldPtr field) - : field_(field) - {} - - const FieldType& operator()(const Class& x) const { - return x.*field_; - } - - FieldType& operator()(Class& x) const { - return x.*field_; - } - - FieldType&& operator()(Class&& x) const { - return std::move(x.*field_); - } -}; - -class Move { -public: - template - auto operator()(Value&& value) const -> - decltype(std::move(std::forward(value))) { - return std::move(std::forward(value)); - } -}; - -class Identity { -public: - template - auto operator()(Value&& value) const -> - decltype(std::forward(value)) { - return std::forward(value); - } -}; - -template -class Cast { - public: - template - Dest operator()(Value&& value) const { - return Dest(std::forward(value)); - } -}; - -template -class To { - public: - template - Dest operator()(Value&& value) const { - return ::folly::to(std::forward(value)); - } -}; - -// Specialization to allow String->StringPiece conversion -template <> -class To { - public: - StringPiece operator()(StringPiece src) const { - return src; - } -}; - -namespace detail { - -template -struct FBounded; - -/* - * Type Traits - */ -template -struct ValueTypeOfRange { - private: - static Container container_; - public: - typedef decltype(*std::begin(container_)) - RefType; - typedef typename std::decay::type - StorageType; -}; - - -/* - * Sources - */ -template::RefType> -class ReferencedSource; - -template::type>> -class CopiedSource; - -template -class Sequence; - -template -class Chain; - -template -class Yield; - -template -class Empty; - - -/* - * Operators - */ -template -class Map; - -template -class Filter; - -template -class Until; - -class Take; - -template -class Sample; - -class Skip; - -template -class Order; - -template -class Distinct; - -template -class Composed; - -template -class TypeAssertion; - -class Concat; - -class RangeConcat; - -class Cycle; - -class Batch; - -class Dereference; - -/* - * Sinks - */ -template -class FoldLeft; - -class First; - -class Any; - -template -class All; - -template -class Reduce; - -class Sum; - -template -class Min; - -template -class Collect; - -template class Collection = std::vector, - template class Allocator = std::allocator> -class CollectTemplate; - -template -class Append; - -template -struct GeneratorBuilder; - -template -class Contains; - -template -class GuardImpl; - -} - -/** - * Polymorphic wrapper - **/ -template -class VirtualGen; - -/* - * Source Factories - */ -template> -From fromConst(const Container& source) { - return From(&source); -} - -template> -From from(Container& source) { - return From(&source); -} - -template::StorageType, - class CopyOf = detail::CopiedSource> -CopyOf fromCopy(Container&& source) { - return CopyOf(std::forward(source)); -} - -template> -From from(std::initializer_list source) { - return From(source); -} - -template> -From from(Container&& source) { - return From(std::move(source)); -} - -template> -Gen range(Value begin, Value end) { - return Gen(begin, end); -} - -template> -Gen seq(Value first, Value last) { - return Gen(first, last); -} - -template> -Gen seq(Value begin) { - return Gen(begin); -} - -template> -Yield generator(Source&& source) { - return Yield(std::forward(source)); -} - -/* - * Create inline generator, used like: - * - * auto gen = GENERATOR(int) { yield(1); yield(2); }; - */ -#define GENERATOR(TYPE) \ - ::folly::gen::detail::GeneratorBuilder() + \ - [=](const std::function& yield) - -/* - * empty() - for producing empty sequences. - */ -template -detail::Empty empty() { - return {}; -} - -/* - * Operator Factories - */ -template> -Map mapped(Predicate pred = Predicate()) { - return Map(std::move(pred)); -} - -template> -Map map(Predicate pred = Predicate()) { - return Map(std::move(pred)); -} - -/* - * member(...) - For extracting a member from each value. - * - * vector strings = ...; - * auto sizes = from(strings) | member(&string::size); - * - * If a member is const overridden (like 'front()'), pass template parameter - * 'Const' to select the const version, or 'Mutable' to select the non-const - * version: - * - * auto heads = from(strings) | member(&string::front); - */ -enum MemberType { - Const, - Mutable -}; - -template, - class Map = detail::Map> -typename std::enable_if::type -member(Return (Class::*member)() const) { - return Map(Mem(member)); -} - -template, - class Map = detail::Map> -typename std::enable_if::type -member(Return (Class::*member)()) { - return Map(Mem(member)); -} - -/* - * field(...) - For extracting a field from each value. - * - * vector items = ...; - * auto names = from(items) | field(&Item::name); - * - * Note that if the values of the generator are rvalues, any non-reference - * fields will be rvalues as well. As an example, the code below does not copy - * any strings, only moves them: - * - * auto namesVector = from(items) - * | move - * | field(&Item::name) - * | as(); - */ -template, - class Map = detail::Map> -Map field(FieldType Class::*field) { - return Map(Field(field)); -} - -template> -Filter filter(Predicate pred = Predicate()) { - return Filter(std::move(pred)); -} - -template> -All all(Predicate pred = Predicate()) { - return All(std::move(pred)); -} - -template> -Until until(Predicate pred = Predicate()) { - return Until(std::move(pred)); -} - -template> -Order orderBy(Selector selector = Identity(), - Comparer comparer = Comparer()) { - return Order(std::move(selector), - std::move(comparer)); -} - -template> -Order orderByDescending(Selector selector = Identity()) { - return Order(std::move(selector)); -} - -template> -Distinct distinctBy(Selector selector = Identity()) { - return Distinct(std::move(selector)); -} - -template>> -Get get() { - return Get(); -} - -// construct Dest from each value -template >> -Cast eachAs() { - return Cast(); -} - -// call folly::to on each value -template >> -To eachTo() { - return To(); -} - -template -detail::TypeAssertion assert_type() { - return {}; -} - -/* - * Sink Factories - */ -template> -FoldLeft foldl(Seed seed = Seed(), - Fold fold = Fold()) { - return FoldLeft(std::move(seed), - std::move(fold)); -} - -template> -Reduce reduce(Reducer reducer = Reducer()) { - return Reduce(std::move(reducer)); -} - -template> -Min minBy(Selector selector = Selector()) { - return Min(std::move(selector)); -} - -template> -MaxBy maxBy(Selector selector = Selector()) { - return MaxBy(std::move(selector)); -} - -template> -Collect as() { - return Collect(); -} - -template class Container = std::vector, - template class Allocator = std::allocator, - class Collect = detail::CollectTemplate> -Collect as() { - return Collect(); -} - -template> -Append appendTo(Collection& collection) { - return Append(&collection); -} - -template::type>> -Contains contains(Needle&& needle) { - return Contains(std::forward(needle)); -} - -template::type>> -GuardImpl guard(ErrorHandler&& handler) { - return GuardImpl(std::forward(handler)); -} - -}} // folly::gen - -#include "folly/experimental/Gen-inl.h" +#pragma message "folly::gen has moved to folly/gen/*.h" +#include "folly/gen/Base.h" diff --git a/folly/experimental/StringGen.h b/folly/experimental/StringGen.h index 55b945d2..c8a6571c 100644 --- a/folly/experimental/StringGen.h +++ b/folly/experimental/StringGen.h @@ -13,144 +13,5 @@ * See the License for the specific language governing permissions and * limitations under the License. */ - -#ifndef FOLLY_STRINGGEN_H_ -#define FOLLY_STRINGGEN_H_ - -#include "folly/Range.h" -#include "folly/experimental/Gen.h" - -namespace folly { -namespace gen { - -namespace detail { -class StringResplitter; -class SplitStringSource; - -template -class Unsplit; - -template -class UnsplitBuffer; - -template -class SplitTo; - -} // namespace detail - -/** - * Split the output from a generator into StringPiece "lines" delimited by - * the given delimiter. Delimters are NOT included in the output. - * - * resplit() behaves as if the input strings were concatenated into one long - * string and then split. - */ -// make this a template so we don't require StringResplitter to be complete -// until use -template -S resplit(char delimiter) { - return S(delimiter); -} - -template -S split(const StringPiece& source, char delimiter) { - return S(source, delimiter); -} - -/* - * Joins a sequence of tokens into a string, with the chosen delimiter. - * - * E.G. - * fbstring result = split("a,b,c", ",") | unsplit(","); - * assert(result == "a,b,c"); - * - * std::string result = split("a,b,c", ",") | unsplit(" "); - * assert(result == "a b c"); - */ - - -// NOTE: The template arguments are reversed to allow the user to cleanly -// specify the output type while still inferring the type of the delimiter. -template> -Unsplit unsplit(const Delimiter& delimiter) { - return Unsplit(delimiter); -} - -template> -Unsplit unsplit(const char* delimiter) { - return Unsplit(delimiter); -} - -/* - * Joins a sequence of tokens into a string, appending them to the output - * buffer. If the output buffer is empty, an initial delimiter will not be - * inserted at the start. - * - * E.G. - * std::string buffer; - * split("a,b,c", ",") | unsplit(",", &buffer); - * assert(buffer == "a,b,c"); - * - * std::string anotherBuffer("initial"); - * split("a,b,c", ",") | unsplit(",", &anotherbuffer); - * assert(anotherBuffer == "initial,a,b,c"); - */ -template> -UnsplitBuffer unsplit(Delimiter delimiter, OutputBuffer* outputBuffer) { - return UnsplitBuffer(delimiter, outputBuffer); -} - -template> -UnsplitBuffer unsplit(const char* delimiter, OutputBuffer* outputBuffer) { - return UnsplitBuffer(delimiter, outputBuffer); -} - - -template -detail::Map, char, Targets...>> -eachToTuple(char delim) { - return detail::Map< - detail::SplitTo, char, Targets...>>( - detail::SplitTo, char, Targets...>(delim)); -} - -template -detail::Map, fbstring, Targets...>> -eachToTuple(StringPiece delim) { - return detail::Map< - detail::SplitTo, fbstring, Targets...>>( - detail::SplitTo, fbstring, Targets...>(delim)); -} - -template -detail::Map, char, First, Second>> -eachToPair(char delim) { - return detail::Map< - detail::SplitTo, char, First, Second>>( - detail::SplitTo, char, First, Second>(delim)); -} - -template -detail::Map, fbstring, First, Second>> -eachToPair(StringPiece delim) { - return detail::Map< - detail::SplitTo, fbstring, First, Second>>( - detail::SplitTo, fbstring, First, Second>( - to(delim))); -} - -} // namespace gen -} // namespace folly - -#include "folly/experimental/StringGen-inl.h" - -#endif /* FOLLY_STRINGGEN_H_ */ - +#pragma message "folly::gen has moved to folly/gen/*.h" +#include "folly/gen/String.h" diff --git a/folly/experimental/test/GenBenchmark.cpp b/folly/experimental/test/GenBenchmark.cpp deleted file mode 100644 index 52f3e0a2..00000000 --- a/folly/experimental/test/GenBenchmark.cpp +++ /dev/null @@ -1,678 +0,0 @@ -/* - * Copyright 2014 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/Gen.h" -#include "folly/experimental/StringGen.h" -#include "folly/experimental/FileGen.h" -#include "folly/String.h" - -#include -#include - -#include - -#include "folly/Benchmark.h" - -using namespace folly; -using namespace folly::gen; -using std::ostream; -using std::pair; -using std::set; -using std::vector; -using std::tuple; - -static std::atomic testSize(1000); -static vector testVector = - seq(1, testSize.load()) - | mapped([](int) { return rand(); }) - | as(); - -static vector testStrVector = - seq(1, testSize.load()) - | eachTo() - | as(); - -static vector> testVectorVector = - seq(1, 100) - | map([](int i) { - return seq(1, i) | as(); - }) - | as(); -static vector strings = - from(testVector) - | eachTo() - | as(); - -auto square = [](int x) { return x * x; }; -auto add = [](int a, int b) { return a + b; }; -auto multiply = [](int a, int b) { return a * b; }; - -BENCHMARK(Sum_Basic_NoGen, iters) { - int limit = testSize.load(); - int s = 0; - while (iters--) { - for (int i = 0; i < limit; ++i) { - s += i; - } - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Sum_Basic_Gen, iters) { - int limit = testSize.load(); - int s = 0; - while (iters--) { - s += range(0, limit) | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(Sum_Vector_NoGen, iters) { - int s = 0; - while (iters--) { - for (auto& i : testVector) { - s += i; - } - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Sum_Vector_Gen, iters) { - int s = 0; - while (iters--) { - s += from(testVector) | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(Member, iters) { - int s = 0; - while(iters--) { - s += from(strings) - | member(&fbstring::size) - | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(MapMember, iters) { - int s = 0; - while(iters--) { - s += from(strings) - | map([](const fbstring& x) { return x.size(); }) - | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(Count_Vector_NoGen, iters) { - int s = 0; - while (iters--) { - for (auto& i : testVector) { - if (i * 2 < rand()) { - ++s; - } - } - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Count_Vector_Gen, iters) { - int s = 0; - while (iters--) { - s += from(testVector) - | filter([](int i) { - return i * 2 < rand(); - }) - | count; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(Fib_Sum_NoGen, iters) { - int s = 0; - while (iters--) { - auto fib = [](int limit) -> vector { - vector ret; - int a = 0; - int b = 1; - for (int i = 0; i * 2 < limit; ++i) { - ret.push_back(a += b); - ret.push_back(b += a); - } - return ret; - }; - for (auto& v : fib(testSize.load())) { - s += v; - } - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Fib_Sum_Gen, iters) { - int s = 0; - while (iters--) { - auto fib = GENERATOR(int) { - int a = 0; - int b = 1; - for (;;) { - yield(a += b); - yield(b += a); - } - }; - s += fib | take(testSize.load()) | sum; - } - folly::doNotOptimizeAway(s); -} - -struct FibYielder { - template - void operator()(Yield&& yield) const { - int a = 0; - int b = 1; - for (;;) { - yield(a += b); - yield(b += a); - } - } -}; - -BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) { - int s = 0; - while (iters--) { - auto fib = generator(FibYielder()); - s += fib | take(testSize.load()) | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(VirtualGen_0Virtual, iters) { - int s = 0; - while (iters--) { - auto numbers = seq(1, 10000); - auto squares = numbers | map(square); - auto quads = squares | map(square); - s += quads | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(VirtualGen_1Virtual, iters) { - int s = 0; - while (iters--) { - VirtualGen numbers = seq(1, 10000); - auto squares = numbers | map(square); - auto quads = squares | map(square); - s += quads | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(VirtualGen_2Virtual, iters) { - int s = 0; - while (iters--) { - VirtualGen numbers = seq(1, 10000); - VirtualGen squares = numbers | map(square); - auto quads = squares | map(square); - s += quads | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(VirtualGen_3Virtual, iters) { - int s = 0; - while (iters--) { - VirtualGen numbers = seq(1, 10000); - VirtualGen squares = numbers | map(square); - VirtualGen quads = squares | map(square); - s += quads | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(Concat_NoGen, iters) { - int s = 0; - while (iters--) { - for (auto& v : testVectorVector) { - for (auto& i : v) { - s += i; - } - } - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Concat_Gen, iters) { - int s = 0; - while (iters--) { - s += from(testVectorVector) | rconcat | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(Composed_NoGen, iters) { - int s = 0; - while (iters--) { - for (auto& i : testVector) { - s += i * i; - } - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Composed_Gen, iters) { - int s = 0; - auto sumSq = map(square) | sum; - while (iters--) { - s += from(testVector) | sumSq; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Composed_GenRegular, iters) { - int s = 0; - while (iters--) { - s += from(testVector) | map(square) | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(Sample, iters) { - size_t s = 0; - while (iters--) { - auto sampler = seq(1, 10 * 1000 * 1000) | sample(1000); - s += (sampler | sum); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -namespace { - -const char* const kLine = "The quick brown fox jumped over the lazy dog.\n"; -const size_t kLineCount = 10000; -std::string bigLines; -const size_t kSmallLineSize = 17; -std::vector smallLines; - -void initStringResplitterBenchmark() { - bigLines.reserve(kLineCount * strlen(kLine)); - for (size_t i = 0; i < kLineCount; ++i) { - bigLines += kLine; - } - size_t remaining = bigLines.size(); - size_t pos = 0; - while (remaining) { - size_t n = std::min(kSmallLineSize, remaining); - smallLines.push_back(bigLines.substr(pos, n)); - pos += n; - remaining -= n; - } -} - -size_t len(folly::StringPiece s) { return s.size(); } - -} // namespace - -BENCHMARK(StringResplitter_Big, iters) { - size_t s = 0; - while (iters--) { - s += from({bigLines}) | resplit('\n') | map(&len) | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(StringResplitter_Small, iters) { - size_t s = 0; - while (iters--) { - s += from(smallLines) | resplit('\n') | map(&len) | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(StringSplit_Old, iters) { - size_t s = 0; - std::string line(kLine); - while (iters--) { - std::vector parts; - split(' ', line, parts); - s += parts.size(); - } - folly::doNotOptimizeAway(s); -} - - -BENCHMARK_RELATIVE(StringSplit_Gen_Vector, iters) { - size_t s = 0; - StringPiece line(kLine); - while (iters--) { - s += (split(line, ' ') | as()).size(); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(StringSplit_Old_ReuseVector, iters) { - size_t s = 0; - std::string line(kLine); - std::vector parts; - while (iters--) { - parts.clear(); - split(' ', line, parts); - s += parts.size(); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(StringSplit_Gen_ReuseVector, iters) { - size_t s = 0; - StringPiece line(kLine); - std::vector parts; - while (iters--) { - parts.clear(); - split(line, ' ') | appendTo(parts); - s += parts.size(); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(StringSplit_Gen, iters) { - size_t s = 0; - StringPiece line(kLine); - while (iters--) { - s += split(line, ' ') | count; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(StringSplit_Gen_Take, iters) { - size_t s = 0; - StringPiece line(kLine); - while (iters--) { - s += split(line, ' ') | take(10) | count; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(StringUnsplit_Old, iters) { - size_t s = 0; - while (iters--) { - fbstring joined; - join(',', testStrVector, joined); - s += joined.size(); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(StringUnsplit_Old_ReusedBuffer, iters) { - size_t s = 0; - fbstring joined; - while (iters--) { - joined.clear(); - join(',', testStrVector, joined); - s += joined.size(); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(StringUnsplit_Gen, iters) { - size_t s = 0; - StringPiece line(kLine); - while (iters--) { - fbstring joined = from(testStrVector) | unsplit(','); - s += joined.size(); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(StringUnsplit_Gen_ReusedBuffer, iters) { - size_t s = 0; - fbstring buffer; - while (iters--) { - buffer.clear(); - from(testStrVector) | unsplit(',', &buffer); - s += buffer.size(); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -void StringUnsplit_Gen(size_t iters, size_t joinSize) { - std::vector v; - BENCHMARK_SUSPEND { - FOR_EACH_RANGE(i, 0, joinSize) { - v.push_back(to(rand())); - } - } - size_t s = 0; - fbstring buffer; - while (iters--) { - buffer.clear(); - from(v) | unsplit(',', &buffer); - s += buffer.size(); - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_PARAM(StringUnsplit_Gen, 1000) -BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 2000) -BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 4000) -BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 8000) - -BENCHMARK_DRAW_LINE() - -fbstring records -= seq(1, 1000) - | mapped([](size_t i) { - return folly::to(i, ' ', i * i, ' ', i * i * i); - }) - | unsplit('\n'); - -BENCHMARK(Records_EachToTuple, iters) { - size_t s = 0; - for (size_t i = 0; i < iters; i += 1000) { - s += split(records, '\n') - | eachToTuple(' ') - | get<1>() - | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Records_VectorStringPieceReused, iters) { - size_t s = 0; - std::vector fields; - for (size_t i = 0; i < iters; i += 1000) { - s += split(records, '\n') - | mapped([&](StringPiece line) { - fields.clear(); - folly::split(' ', line, fields); - CHECK(fields.size() == 3); - return std::make_tuple( - folly::to(fields[0]), - folly::to(fields[1]), - StringPiece(fields[2])); - }) - | get<1>() - | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Records_VectorStringPiece, iters) { - size_t s = 0; - for (size_t i = 0; i < iters; i += 1000) { - s += split(records, '\n') - | mapped([](StringPiece line) { - std::vector fields; - folly::split(' ', line, fields); - CHECK(fields.size() == 3); - return std::make_tuple( - folly::to(fields[0]), - folly::to(fields[1]), - StringPiece(fields[2])); - }) - | get<1>() - | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_RELATIVE(Records_VectorString, iters) { - size_t s = 0; - for (size_t i = 0; i < iters; i += 1000) { - s += split(records, '\n') - | mapped([](StringPiece line) { - std::vector fields; - folly::split(' ', line, fields); - CHECK(fields.size() == 3); - return std::make_tuple( - folly::to(fields[0]), - folly::to(fields[1]), - StringPiece(fields[2])); - }) - | get<1>() - | sum; - } - folly::doNotOptimizeAway(s); -} - -BENCHMARK_DRAW_LINE() - -BENCHMARK(ByLine_Pipes, iters) { - std::thread thread; - int rfd; - int wfd; - BENCHMARK_SUSPEND { - int p[2]; - CHECK_ERR(::pipe(p)); - rfd = p[0]; - wfd = p[1]; - thread = std::thread([wfd, iters] { - char x = 'x'; - PCHECK(::write(wfd, &x, 1) == 1); // signal startup - FILE* f = fdopen(wfd, "w"); - PCHECK(f); - for (int i = 1; i <= iters; ++i) { - fprintf(f, "%d\n", i); - } - fclose(f); - }); - char buf; - PCHECK(::read(rfd, &buf, 1) == 1); // wait for startup - } - - auto s = byLine(File(rfd)) | eachTo() | sum; - folly::doNotOptimizeAway(s); - - BENCHMARK_SUSPEND { - ::close(rfd); - CHECK_EQ(s, int64_t(iters) * (iters + 1) / 2); - thread.join(); - } -} - -// ============================================================================ -// folly/experimental/test/GenBenchmark.cpp relative time/iter iters/s -// ============================================================================ -// Sum_Basic_NoGen 374.39ns 2.67M -// Sum_Basic_Gen 101.05% 370.48ns 2.70M -// ---------------------------------------------------------------------------- -// Sum_Vector_NoGen 198.84ns 5.03M -// Sum_Vector_Gen 98.14% 202.60ns 4.94M -// ---------------------------------------------------------------------------- -// Member 4.56us 219.11K -// MapMember 400.21% 1.14us 876.89K -// ---------------------------------------------------------------------------- -// Count_Vector_NoGen 13.99us 71.47K -// Count_Vector_Gen 106.73% 13.11us 76.28K -// ---------------------------------------------------------------------------- -// Fib_Sum_NoGen 4.27us 234.07K -// Fib_Sum_Gen 43.18% 9.90us 101.06K -// Fib_Sum_Gen_Static 92.08% 4.64us 215.53K -// ---------------------------------------------------------------------------- -// VirtualGen_0Virtual 12.07us 82.83K -// VirtualGen_1Virtual 32.46% 37.19us 26.89K -// VirtualGen_2Virtual 24.36% 49.55us 20.18K -// VirtualGen_3Virtual 18.16% 66.49us 15.04K -// ---------------------------------------------------------------------------- -// Concat_NoGen 1.90us 527.40K -// Concat_Gen 86.73% 2.19us 457.39K -// ---------------------------------------------------------------------------- -// Composed_NoGen 546.18ns 1.83M -// Composed_Gen 100.41% 543.93ns 1.84M -// Composed_GenRegular 100.42% 543.92ns 1.84M -// ---------------------------------------------------------------------------- -// Sample 146.68ms 6.82 -// ---------------------------------------------------------------------------- -// StringResplitter_Big 124.80us 8.01K -// StringResplitter_Small 15.11% 825.74us 1.21K -// ---------------------------------------------------------------------------- -// StringSplit_Old 393.49ns 2.54M -// StringSplit_Gen_Vector 121.47% 323.93ns 3.09M -// ---------------------------------------------------------------------------- -// StringSplit_Old_ReuseVector 80.77ns 12.38M -// StringSplit_Gen_ReuseVector 102.02% 79.17ns 12.63M -// StringSplit_Gen 123.78% 65.25ns 15.32M -// StringSplit_Gen_Take 123.44% 65.43ns 15.28M -// ---------------------------------------------------------------------------- -// StringUnsplit_Old 29.36us 34.06K -// StringUnsplit_Old_ReusedBuffer 100.25% 29.29us 34.14K -// StringUnsplit_Gen 103.38% 28.40us 35.21K -// StringUnsplit_Gen_ReusedBuffer 109.85% 26.73us 37.41K -// ---------------------------------------------------------------------------- -// StringUnsplit_Gen(1000) 32.30us 30.96K -// StringUnsplit_Gen(2000) 49.75% 64.93us 15.40K -// StringUnsplit_Gen(4000) 24.74% 130.60us 7.66K -// StringUnsplit_Gen(8000) 12.31% 262.35us 3.81K -// ---------------------------------------------------------------------------- -// Records_EachToTuple 75.03ns 13.33M -// Records_VectorStringPieceReused 81.79% 91.74ns 10.90M -// Records_VectorStringPiece 36.47% 205.77ns 4.86M -// Records_VectorString 12.90% 581.70ns 1.72M -// ---------------------------------------------------------------------------- -// ByLine_Pipes 121.68ns 8.22M -// ============================================================================ - -int main(int argc, char *argv[]) { - google::ParseCommandLineFlags(&argc, &argv, true); - initStringResplitterBenchmark(); - runBenchmarks(); - return 0; -} diff --git a/folly/experimental/Gen-inl.h b/folly/gen/Base-inl.h similarity index 82% rename from folly/experimental/Gen-inl.h rename to folly/gen/Base-inl.h index c21529d8..d627ed55 100644 --- a/folly/experimental/Gen-inl.h +++ b/folly/gen/Base-inl.h @@ -14,278 +14,28 @@ * limitations under the License. */ +#ifndef FOLLY_GEN_BASE_H +#error This file may only be included from folly/gen/Base.h +#endif + // Ignore shadowing warnings within this file, so includers can use -Wshadow. #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wshadow" namespace folly { namespace gen { -/** - * IsCompatibleSignature - Trait type for testing whether a given Functor - * matches an expected signature. - * - * Usage: - * IsCompatibleSignature::value - */ -template -class IsCompatibleSignature { - static constexpr bool value = false; -}; - -template -class IsCompatibleSignature { - template()(std::declval()...)), - bool good = std::is_same::value> - static constexpr bool testArgs(int* p) { - return good; - } - - template - static constexpr bool testArgs(...) { - return false; - } -public: - static constexpr bool value = testArgs(nullptr); -}; - /** * ArgumentReference - For determining ideal argument type to receive a value. */ -template -struct ArgumentReference : - public std::conditional::value, - T, // T& -> T&, T&& -> T&&, const T& -> const T& - typename std::conditional< - std::is_const::value, - T&, // const int -> const int& - T&& // int -> int&& - >::type> {}; - -/** - * FBounded - Helper type for the curiously recurring template pattern, used - * heavily here to enable inlining and obviate virtual functions - */ -template -struct FBounded { - const Self& self() const { - return *static_cast(this); - } - - Self& self() { - return *static_cast(this); - } -}; - -/** - * Operator - Core abstraction of an operation which may be applied to a - * generator. All operators implement a method compose(), which takes a - * generator and produces an output generator. - */ -template -class Operator : public FBounded { - public: - /** - * compose() - Must be implemented by child class to compose a new Generator - * out of a given generator. This function left intentionally unimplemented. - */ - template - ResultGen compose(const GenImpl& source) const; - - protected: - Operator() = default; - Operator(const Operator&) = default; - Operator(Operator&&) = default; -}; - -/** - * operator|() - For composing two operators without binding it to a - * particular generator. - */ -template> -Composed operator|(const Operator& left, - const Operator& right) { - return Composed(left.self(), right.self()); -} - -template> -Composed operator|(const Operator& left, - Operator&& right) { - return Composed(left.self(), std::move(right.self())); -} - -template> -Composed operator|(Operator&& left, - const Operator& right) { - return Composed(std::move(left.self()), right.self()); -} - -template> -Composed operator|(Operator&& left, - Operator&& right) { - return Composed(std::move(left.self()), std::move(right.self())); -} - -/** - * GenImpl - Core abstraction of a generator, an object which produces values by - * passing them to a given handler lambda. All generator implementations must - * implement apply(). foreach() may also be implemented to special case the - * condition where the entire sequence is consumed. - */ -template -class GenImpl : public FBounded { - protected: - // To prevent slicing - GenImpl() = default; - GenImpl(const GenImpl&) = default; - GenImpl(GenImpl&&) = default; - - public: - typedef Value ValueType; - typedef typename std::decay::type StorageType; - - /** - * apply() - Send all values produced by this generator to given handler until - * the handler returns false. Returns false if and only if the handler passed - * in returns false. Note: It should return true even if it completes (without - * the handler returning false), as 'Chain' uses the return value of apply to - * determine if it should process the second object in its chain. - */ - template - bool apply(Handler&& handler) const; - - /** - * foreach() - Send all values produced by this generator to given lambda. - */ - template - void foreach(Body&& body) const { - this->self().apply([&](Value value) -> bool { - static_assert(!infinite, "Cannot call foreach on infinite GenImpl"); - body(std::forward(value)); - return true; - }); - } - - // Child classes should override if the sequence generated is *definitely* - // infinite. 'infinite' may be false_type for some infinite sequences - // (due the the Halting Problem). - static constexpr bool infinite = false; -}; - -template> -Chain operator+(const GenImpl& left, - const GenImpl& right) { - static_assert( - std::is_same::value, - "Generators may ony be combined if Values are the exact same type."); - return Chain(left.self(), right.self()); -} - -template> -Chain operator+(const GenImpl& left, - GenImpl&& right) { - static_assert( - std::is_same::value, - "Generators may ony be combined if Values are the exact same type."); - return Chain(left.self(), std::move(right.self())); -} - -template> -Chain operator+(GenImpl&& left, - const GenImpl& right) { - static_assert( - std::is_same::value, - "Generators may ony be combined if Values are the exact same type."); - return Chain(std::move(left.self()), right.self()); -} - -template> -Chain operator+(GenImpl&& left, - GenImpl&& right) { - static_assert( - std::is_same::value, - "Generators may ony be combined if Values are the exact same type."); - return Chain(std::move(left.self()), std::move(right.self())); -} - -/** - * operator|() which enables foreach-like usage: - * gen | [](Value v) -> void {...}; - */ -template -typename std::enable_if< - IsCompatibleSignature::value>::type -operator|(const GenImpl& gen, Handler&& handler) { - static_assert(!Gen::infinite, - "Cannot pull all values from an infinite sequence."); - gen.self().foreach(std::forward(handler)); -} - -/** - * operator|() which enables foreach-like usage with 'break' support: - * gen | [](Value v) -> bool { return shouldContinue(); }; - */ -template -typename std::enable_if< - IsCompatibleSignature::value, bool>::type -operator|(const GenImpl& gen, Handler&& handler) { - return gen.self().apply(std::forward(handler)); -} - -/** - * operator|() for composing generators with operators, similar to boosts' range - * adaptors: - * gen | map(square) | sum - */ -template -auto operator|(const GenImpl& gen, const Operator& op) -> -decltype(op.self().compose(gen.self())) { - return op.self().compose(gen.self()); -} - -template -auto operator|(GenImpl&& gen, const Operator& op) -> -decltype(op.self().compose(std::move(gen.self()))) { - return op.self().compose(std::move(gen.self())); -} +template +struct ArgumentReference + : public std::conditional< + std::is_reference::value, + T, // T& -> T&, T&& -> T&&, const T& -> const T& + typename std::conditional::value, + T&, // const int -> const int& + T&& // int -> int&& + >::type> {}; namespace detail { @@ -457,39 +207,6 @@ public: static constexpr bool infinite = endless; }; -/** - * Chain - For concatenating the values produced by two Generators. - * - * This type is primarily used through using '+' to combine generators, like: - * - * auto nums = seq(1, 10) + seq(20, 30); - * int total = nums | sum; - */ -template -class Chain : public GenImpl> { - First first_; - Second second_; -public: - explicit Chain(First first, Second second) - : first_(std::move(first)) - , second_(std::move(second)) {} - - template - bool apply(Handler&& handler) const { - return first_.apply(std::forward(handler)) - && second_.apply(std::forward(handler)); - } - - template - void foreach(Body&& body) const { - first_.foreach(std::forward(body)); - second_.foreach(std::forward(body)); - } - - static constexpr bool infinite = First::infinite || Second::infinite; -}; - /** * GenratorBuilder - Helper for GENERTATOR macro. **/ @@ -1238,51 +955,6 @@ class Batch : public Operator { return Gen(source.self(), batchSize_); } }; - -/** - * Composed - For building up a pipeline of operations to perform, absent any - * particular source generator. Useful for building up custom pipelines. - * - * This type is usually used by just piping two operators together: - * - * auto valuesOf = filter([](Optional& o) { return o.hasValue(); }) - * | map([](Optional& o) -> int& { return o.value(); }); - * - * auto valuesIncluded = from(optionals) | valuesOf | as(); - */ -template -class Composed : public Operator> { - First first_; - Second second_; - public: - Composed() {} - - Composed(First first, Second second) - : first_(std::move(first)) - , second_(std::move(second)) {} - - template() - .compose(std::declval())), - class SecondRet = decltype(std::declval() - .compose(std::declval()))> - SecondRet compose(const GenImpl& source) const { - return second_.compose(first_.compose(source.self())); - } - - template() - .compose(std::declval())), - class SecondRet = decltype(std::declval() - .compose(std::declval()))> - SecondRet compose(GenImpl&& source) const { - return second_.compose(first_.compose(std::move(source.self()))); - } -}; - /* * Sinks */ diff --git a/folly/gen/Base.h b/folly/gen/Base.h new file mode 100644 index 00000000..3b6cb7ca --- /dev/null +++ b/folly/gen/Base.h @@ -0,0 +1,642 @@ +/* + * Copyright 2013 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#ifndef FOLLY_GEN_BASE_H +#define FOLLY_GEN_BASE_H + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "folly/Range.h" +#include "folly/Optional.h" +#include "folly/Conv.h" +#include "folly/gen/Core.h" + +/** + * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ + * @author Tom Jackson + * + * This library makes it possible to write declarative comprehensions for + * processing sequences of values efficiently in C++. The operators should be + * familiar to those with experience in functional programming, and the + * performance will be virtually identical to the equivalent, boilerplate C++ + * implementations. + * + * Generator objects may be created from either an stl-like container (anything + * supporting begin() and end()), from sequences of values, or from another + * generator (see below). To create a generator that pulls values from a vector, + * for example, one could write: + * + * vector names { "Jack", "Jill", "Sara", "Tom" }; + * auto gen = from(names); + * + * Generators are composed by building new generators out of old ones through + * the use of operators. These are reminicent of shell pipelines, and afford + * similar composition. Lambda functions are used liberally to describe how to + * handle individual values: + * + * auto lengths = gen + * | mapped([](const fbstring& name) { return name.size(); }); + * + * Generators are lazy; they don't actually perform any work until they need to. + * As an example, the 'lengths' generator (above) won't actually invoke the + * provided lambda until values are needed: + * + * auto lengthVector = lengths | as(); + * auto totalLength = lengths | sum; + * + * 'auto' is useful in here because the actual types of the generators objects + * are usually complicated and implementation-sensitive. + * + * If a simpler type is desired (for returning, as an example), VirtualGen + * may be used to wrap the generator in a polymorphic wrapper: + * + * VirtualGen powersOfE() { + * return seq(1) | mapped(&expf); + * } + * + * To learn more about this library, including the use of infinite generators, + * see the examples in the comments, or the docs (coming soon). +*/ + +namespace folly { namespace gen { + +class EmptySequence : public std::exception { +public: + virtual const char* what() const noexcept { + return "This operation cannot be called on an empty sequence"; + } +}; + +class Less { +public: + template + auto operator()(const First& first, const Second& second) const -> + decltype(first < second) { + return first < second; + } +}; + +class Greater { +public: + template + auto operator()(const First& first, const Second& second) const -> + decltype(first > second) { + return first > second; + } +}; + +template +class Get { +public: + template + auto operator()(Value&& value) const -> + decltype(std::get(std::forward(value))) { + return std::get(std::forward(value)); + } +}; + +template +class MemberFunction { + public: + typedef Result (Class::*MemberPtr)(); + private: + MemberPtr member_; + public: + explicit MemberFunction(MemberPtr member) + : member_(member) + {} + + Result operator()(Class&& x) const { + return (x.*member_)(); + } + + Result operator()(Class& x) const { + return (x.*member_)(); + } +}; + +template +class ConstMemberFunction{ + public: + typedef Result (Class::*MemberPtr)() const; + private: + MemberPtr member_; + public: + explicit ConstMemberFunction(MemberPtr member) + : member_(member) + {} + + Result operator()(const Class& x) const { + return (x.*member_)(); + } +}; + +template +class Field { + public: + typedef FieldType (Class::*FieldPtr); + private: + FieldPtr field_; + public: + explicit Field(FieldPtr field) + : field_(field) + {} + + const FieldType& operator()(const Class& x) const { + return x.*field_; + } + + FieldType& operator()(Class& x) const { + return x.*field_; + } + + FieldType&& operator()(Class&& x) const { + return std::move(x.*field_); + } +}; + +class Move { +public: + template + auto operator()(Value&& value) const -> + decltype(std::move(std::forward(value))) { + return std::move(std::forward(value)); + } +}; + +class Identity { +public: + template + auto operator()(Value&& value) const -> + decltype(std::forward(value)) { + return std::forward(value); + } +}; + +template +class Cast { + public: + template + Dest operator()(Value&& value) const { + return Dest(std::forward(value)); + } +}; + +template +class To { + public: + template + Dest operator()(Value&& value) const { + return ::folly::to(std::forward(value)); + } +}; + +// Specialization to allow String->StringPiece conversion +template <> +class To { + public: + StringPiece operator()(StringPiece src) const { + return src; + } +}; + +namespace detail { + +template +struct FBounded; + +/* + * Type Traits + */ +template +struct ValueTypeOfRange { + private: + static Container container_; + public: + typedef decltype(*std::begin(container_)) + RefType; + typedef typename std::decay::type + StorageType; +}; + + +/* + * Sources + */ +template::RefType> +class ReferencedSource; + +template::type>> +class CopiedSource; + +template +class Sequence; + +template +class Yield; + +template +class Empty; + + +/* + * Operators + */ +template +class Map; + +template +class Filter; + +template +class Until; + +class Take; + +template +class Sample; + +class Skip; + +template +class Order; + +template +class Distinct; + +template +class TypeAssertion; + +class Concat; + +class RangeConcat; + +class Cycle; + +class Batch; + +class Dereference; + +/* + * Sinks + */ +template +class FoldLeft; + +class First; + +class Any; + +template +class All; + +template +class Reduce; + +class Sum; + +template +class Min; + +template +class Collect; + +template class Collection = std::vector, + template class Allocator = std::allocator> +class CollectTemplate; + +template +class Append; + +template +struct GeneratorBuilder; + +template +class Contains; + +template +class GuardImpl; + +} + +/** + * Polymorphic wrapper + **/ +template +class VirtualGen; + +/* + * Source Factories + */ +template> +From fromConst(const Container& source) { + return From(&source); +} + +template> +From from(Container& source) { + return From(&source); +} + +template::StorageType, + class CopyOf = detail::CopiedSource> +CopyOf fromCopy(Container&& source) { + return CopyOf(std::forward(source)); +} + +template> +From from(std::initializer_list source) { + return From(source); +} + +template> +From from(Container&& source) { + return From(std::move(source)); +} + +template> +Gen range(Value begin, Value end) { + return Gen(begin, end); +} + +template> +Gen seq(Value first, Value last) { + return Gen(first, last); +} + +template> +Gen seq(Value begin) { + return Gen(begin); +} + +template> +Yield generator(Source&& source) { + return Yield(std::forward(source)); +} + +/* + * Create inline generator, used like: + * + * auto gen = GENERATOR(int) { yield(1); yield(2); }; + */ +#define GENERATOR(TYPE) \ + ::folly::gen::detail::GeneratorBuilder() + \ + [=](const std::function& yield) + +/* + * empty() - for producing empty sequences. + */ +template +detail::Empty empty() { + return {}; +} + +/* + * Operator Factories + */ +template> +Map mapped(Predicate pred = Predicate()) { + return Map(std::move(pred)); +} + +template> +Map map(Predicate pred = Predicate()) { + return Map(std::move(pred)); +} + +/* + * member(...) - For extracting a member from each value. + * + * vector strings = ...; + * auto sizes = from(strings) | member(&string::size); + * + * If a member is const overridden (like 'front()'), pass template parameter + * 'Const' to select the const version, or 'Mutable' to select the non-const + * version: + * + * auto heads = from(strings) | member(&string::front); + */ +enum MemberType { + Const, + Mutable +}; + +template, + class Map = detail::Map> +typename std::enable_if::type +member(Return (Class::*member)() const) { + return Map(Mem(member)); +} + +template, + class Map = detail::Map> +typename std::enable_if::type +member(Return (Class::*member)()) { + return Map(Mem(member)); +} + +/* + * field(...) - For extracting a field from each value. + * + * vector items = ...; + * auto names = from(items) | field(&Item::name); + * + * Note that if the values of the generator are rvalues, any non-reference + * fields will be rvalues as well. As an example, the code below does not copy + * any strings, only moves them: + * + * auto namesVector = from(items) + * | move + * | field(&Item::name) + * | as(); + */ +template, + class Map = detail::Map> +Map field(FieldType Class::*field) { + return Map(Field(field)); +} + +template> +Filter filter(Predicate pred = Predicate()) { + return Filter(std::move(pred)); +} + +template> +All all(Predicate pred = Predicate()) { + return All(std::move(pred)); +} + +template> +Until until(Predicate pred = Predicate()) { + return Until(std::move(pred)); +} + +template> +Order orderBy(Selector selector = Identity(), + Comparer comparer = Comparer()) { + return Order(std::move(selector), + std::move(comparer)); +} + +template> +Order orderByDescending(Selector selector = Identity()) { + return Order(std::move(selector)); +} + +template> +Distinct distinctBy(Selector selector = Identity()) { + return Distinct(std::move(selector)); +} + +template>> +Get get() { + return Get(); +} + +// construct Dest from each value +template >> +Cast eachAs() { + return Cast(); +} + +// call folly::to on each value +template >> +To eachTo() { + return To(); +} + +template +detail::TypeAssertion assert_type() { + return {}; +} + +/* + * Sink Factories + */ +template> +FoldLeft foldl(Seed seed = Seed(), + Fold fold = Fold()) { + return FoldLeft(std::move(seed), + std::move(fold)); +} + +template> +Reduce reduce(Reducer reducer = Reducer()) { + return Reduce(std::move(reducer)); +} + +template> +Min minBy(Selector selector = Selector()) { + return Min(std::move(selector)); +} + +template> +MaxBy maxBy(Selector selector = Selector()) { + return MaxBy(std::move(selector)); +} + +template> +Collect as() { + return Collect(); +} + +template class Container = std::vector, + template class Allocator = std::allocator, + class Collect = detail::CollectTemplate> +Collect as() { + return Collect(); +} + +template> +Append appendTo(Collection& collection) { + return Append(&collection); +} + +template::type>> +Contains contains(Needle&& needle) { + return Contains(std::forward(needle)); +} + +template::type>> +GuardImpl guard(ErrorHandler&& handler) { + return GuardImpl(std::forward(handler)); +} + +}} // folly::gen + +#include "folly/gen/Base-inl.h" + +#endif // FOLLY_GEN_BASE_H diff --git a/folly/experimental/CombineGen-inl.h b/folly/gen/Combine-inl.h similarity index 98% rename from folly/experimental/CombineGen-inl.h rename to folly/gen/Combine-inl.h index 3b859df8..667de7f2 100644 --- a/folly/experimental/CombineGen-inl.h +++ b/folly/gen/Combine-inl.h @@ -14,8 +14,8 @@ * limitations under the License. */ -#ifndef FOLLY_COMBINEGEN_H_ -#error This file may only be included from folly/experimental/CombineGen.h +#ifndef FOLLY_GEN_COMBINE_H +#error This file may only be included from folly/gen/Combine.h #endif #include diff --git a/folly/gen/Combine.h b/folly/gen/Combine.h new file mode 100644 index 00000000..ff519c4d --- /dev/null +++ b/folly/gen/Combine.h @@ -0,0 +1,45 @@ +/* + * Copyright 2013 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#ifndef FOLLY_GEN_COMBINE_H +#define FOLLY_GEN_COMBINE_H + +#include "folly/gen/Base.h" + +namespace folly { +namespace gen { +namespace detail { + +template +class Interleave; + +template +class Zip; + +} // namespace detail + +template::type, + class Interleave = detail::Interleave> +Interleave interleave(Source2&& source2) { + return Interleave(std::forward(source2)); +} + +} // namespace gen +} // namespace folly + +#include "folly/gen/Combine-inl.h" + +#endif // FOLLY_GEN_COMBINE_H diff --git a/folly/gen/Core-inl.h b/folly/gen/Core-inl.h new file mode 100644 index 00000000..9808487f --- /dev/null +++ b/folly/gen/Core-inl.h @@ -0,0 +1,364 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FOLLY_GEN_CORE_H +#error This file may only be included from folly/gen/Core.h +#endif + +// Ignore shadowing warnings within this file, so includers can use -Wshadow. +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wshadow" + +namespace folly { namespace gen { + +/** + * IsCompatibleSignature - Trait type for testing whether a given Functor + * matches an expected signature. + * + * Usage: + * IsCompatibleSignature::value + */ +template +class IsCompatibleSignature { + static constexpr bool value = false; +}; + +template +class IsCompatibleSignature { + template()(std::declval()...)), + bool good = std::is_same::value> + static constexpr bool testArgs(int* p) { + return good; + } + + template + static constexpr bool testArgs(...) { + return false; + } +public: + static constexpr bool value = testArgs(nullptr); +}; + +/** + * FBounded - Helper type for the curiously recurring template pattern, used + * heavily here to enable inlining and obviate virtual functions + */ +template +struct FBounded { + const Self& self() const { + return *static_cast(this); + } + + Self& self() { + return *static_cast(this); + } +}; + +/** + * Operator - Core abstraction of an operation which may be applied to a + * generator. All operators implement a method compose(), which takes a + * generator and produces an output generator. + */ +template +class Operator : public FBounded { + public: + /** + * compose() - Must be implemented by child class to compose a new Generator + * out of a given generator. This function left intentionally unimplemented. + */ + template + ResultGen compose(const GenImpl& source) const; + + protected: + Operator() = default; + Operator(const Operator&) = default; + Operator(Operator&&) = default; +}; + +/** + * operator|() - For composing two operators without binding it to a + * particular generator. + */ +template> +Composed operator|(const Operator& left, + const Operator& right) { + return Composed(left.self(), right.self()); +} + +template> +Composed operator|(const Operator& left, + Operator&& right) { + return Composed(left.self(), std::move(right.self())); +} + +template> +Composed operator|(Operator&& left, + const Operator& right) { + return Composed(std::move(left.self()), right.self()); +} + +template> +Composed operator|(Operator&& left, + Operator&& right) { + return Composed(std::move(left.self()), std::move(right.self())); +} + +/** + * GenImpl - Core abstraction of a generator, an object which produces values by + * passing them to a given handler lambda. All generator implementations must + * implement apply(). foreach() may also be implemented to special case the + * condition where the entire sequence is consumed. + */ +template +class GenImpl : public FBounded { + protected: + // To prevent slicing + GenImpl() = default; + GenImpl(const GenImpl&) = default; + GenImpl(GenImpl&&) = default; + + public: + typedef Value ValueType; + typedef typename std::decay::type StorageType; + + /** + * apply() - Send all values produced by this generator to given handler until + * the handler returns false. Returns false if and only if the handler passed + * in returns false. Note: It should return true even if it completes (without + * the handler returning false), as 'Chain' uses the return value of apply to + * determine if it should process the second object in its chain. + */ + template + bool apply(Handler&& handler) const; + + /** + * foreach() - Send all values produced by this generator to given lambda. + */ + template + void foreach(Body&& body) const { + this->self().apply([&](Value value) -> bool { + static_assert(!infinite, "Cannot call foreach on infinite GenImpl"); + body(std::forward(value)); + return true; + }); + } + + // Child classes should override if the sequence generated is *definitely* + // infinite. 'infinite' may be false_type for some infinite sequences + // (due the the Halting Problem). + static constexpr bool infinite = false; +}; + +template> +Chain operator+(const GenImpl& left, + const GenImpl& right) { + static_assert( + std::is_same::value, + "Generators may ony be combined if Values are the exact same type."); + return Chain(left.self(), right.self()); +} + +template> +Chain operator+(const GenImpl& left, + GenImpl&& right) { + static_assert( + std::is_same::value, + "Generators may ony be combined if Values are the exact same type."); + return Chain(left.self(), std::move(right.self())); +} + +template> +Chain operator+(GenImpl&& left, + const GenImpl& right) { + static_assert( + std::is_same::value, + "Generators may ony be combined if Values are the exact same type."); + return Chain(std::move(left.self()), right.self()); +} + +template> +Chain operator+(GenImpl&& left, + GenImpl&& right) { + static_assert( + std::is_same::value, + "Generators may ony be combined if Values are the exact same type."); + return Chain(std::move(left.self()), std::move(right.self())); +} + +/** + * operator|() which enables foreach-like usage: + * gen | [](Value v) -> void {...}; + */ +template +typename std::enable_if< + IsCompatibleSignature::value>::type +operator|(const GenImpl& gen, Handler&& handler) { + static_assert(!Gen::infinite, + "Cannot pull all values from an infinite sequence."); + gen.self().foreach(std::forward(handler)); +} + +/** + * operator|() which enables foreach-like usage with 'break' support: + * gen | [](Value v) -> bool { return shouldContinue(); }; + */ +template +typename std::enable_if< + IsCompatibleSignature::value, bool>::type +operator|(const GenImpl& gen, Handler&& handler) { + return gen.self().apply(std::forward(handler)); +} + +/** + * operator|() for composing generators with operators, similar to boosts' range + * adaptors: + * gen | map(square) | sum + */ +template +auto operator|(const GenImpl& gen, const Operator& op) -> +decltype(op.self().compose(gen.self())) { + return op.self().compose(gen.self()); +} + +template +auto operator|(GenImpl&& gen, const Operator& op) -> +decltype(op.self().compose(std::move(gen.self()))) { + return op.self().compose(std::move(gen.self())); +} + +namespace detail { + +/** + * Composed - For building up a pipeline of operations to perform, absent any + * particular source generator. Useful for building up custom pipelines. + * + * This type is usually used by just piping two operators together: + * + * auto valuesOf = filter([](Optional& o) { return o.hasValue(); }) + * | map([](Optional& o) -> int& { return o.value(); }); + * + * auto valuesIncluded = from(optionals) | valuesOf | as(); + */ +template +class Composed : public Operator> { + First first_; + Second second_; + public: + Composed() {} + + Composed(First first, Second second) + : first_(std::move(first)) + , second_(std::move(second)) {} + + template() + .compose(std::declval())), + class SecondRet = decltype(std::declval() + .compose(std::declval()))> + SecondRet compose(const GenImpl& source) const { + return second_.compose(first_.compose(source.self())); + } + + template() + .compose(std::declval())), + class SecondRet = decltype(std::declval() + .compose(std::declval()))> + SecondRet compose(GenImpl&& source) const { + return second_.compose(first_.compose(std::move(source.self()))); + } +}; + +/** + * Chain - For concatenating the values produced by two Generators. + * + * This type is primarily used through using '+' to combine generators, like: + * + * auto nums = seq(1, 10) + seq(20, 30); + * int total = nums | sum; + */ +template +class Chain : public GenImpl> { + First first_; + Second second_; +public: + explicit Chain(First first, Second second) + : first_(std::move(first)) + , second_(std::move(second)) {} + + template + bool apply(Handler&& handler) const { + return first_.apply(std::forward(handler)) + && second_.apply(std::forward(handler)); + } + + template + void foreach(Body&& body) const { + first_.foreach(std::forward(body)); + second_.foreach(std::forward(body)); + } + + static constexpr bool infinite = First::infinite || Second::infinite; +}; + +} // detail + +}} // folly::gen + +#pragma GCC diagnostic pop diff --git a/folly/gen/Core.h b/folly/gen/Core.h new file mode 100644 index 00000000..d470199c --- /dev/null +++ b/folly/gen/Core.h @@ -0,0 +1,45 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FOLLY_GEN_CORE_H +#define FOLLY_GEN_CORE_H + +namespace folly { namespace gen { + +template +class GenImpl; + +template +class Operator; + +namespace detail { + +template +struct FBounded; + +template +class Composed; + +template +class Chain; + +} // detail + +}} // folly::gen + +#include "folly/gen/Core-inl.h" + +#endif // FOLLY_GEN_CORE_H diff --git a/folly/experimental/FileGen-inl.h b/folly/gen/File-inl.h similarity index 96% rename from folly/experimental/FileGen-inl.h rename to folly/gen/File-inl.h index c3a7f94b..268bd816 100644 --- a/folly/experimental/FileGen-inl.h +++ b/folly/gen/File-inl.h @@ -14,13 +14,13 @@ * limitations under the License. */ -#ifndef FOLLY_FILEGEN_H_ -#error This file may only be included from folly/experimental/FileGen.h +#ifndef FOLLY_GEN_FILE_H +#error This file may only be included from folly/gen/File.h #endif #include -#include "folly/experimental/StringGen.h" +#include "folly/gen/String.h" namespace folly { namespace gen { diff --git a/folly/gen/File.h b/folly/gen/File.h new file mode 100644 index 00000000..ded64c20 --- /dev/null +++ b/folly/gen/File.h @@ -0,0 +1,72 @@ +/* + * Copyright 2013 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FOLLY_GEN_FILE_H +#define FOLLY_GEN_FILE_H + +#include "folly/File.h" +#include "folly/gen/Base.h" +#include "folly/io/IOBuf.h" + +namespace folly { +namespace gen { + +namespace detail { +class FileReader; +class FileWriter; +} // namespace detail + +/** + * Generator that reads from a file with a buffer of the given size. + * Reads must be buffered (the generator interface expects the generator + * to hold each value). + */ +template +S fromFile(File file, size_t bufferSize=4096) { + return S(std::move(file), IOBuf::create(bufferSize)); +} + +/** + * Generator that reads from a file using a given buffer. + */ +template +S fromFile(File file, std::unique_ptr buffer) { + return S(std::move(file), std::move(buffer)); +} + +/** + * Sink that writes to a file with a buffer of the given size. + * If bufferSize is 0, writes will be unbuffered. + */ +template +S toFile(File file, size_t bufferSize=4096) { + return S(std::move(file), bufferSize ? nullptr : IOBuf::create(bufferSize)); +} + +/** + * Sink that writes to a file using a given buffer. + * If the buffer is nullptr, writes will be unbuffered. + */ +template +S toFile(File file, std::unique_ptr buffer) { + return S(std::move(file), std::move(buffer)); +} + +}} // !folly::gen + +#include "folly/gen/File-inl.h" + +#endif // FOLLY_GEN_FILE_H diff --git a/folly/experimental/StringGen-inl.h b/folly/gen/String-inl.h similarity index 98% rename from folly/experimental/StringGen-inl.h rename to folly/gen/String-inl.h index 98f9edc7..e29f2a57 100644 --- a/folly/experimental/StringGen-inl.h +++ b/folly/gen/String-inl.h @@ -14,8 +14,8 @@ * limitations under the License. */ -#ifndef FOLLY_STRINGGEN_H_ -#error This file may only be included from folly/experimental/StringGen.h +#ifndef FOLLY_GEN_STRING_H +#error This file may only be included from folly/gen/String.h #endif #include "folly/Conv.h" diff --git a/folly/gen/String.h b/folly/gen/String.h new file mode 100644 index 00000000..3f4497b1 --- /dev/null +++ b/folly/gen/String.h @@ -0,0 +1,155 @@ +/* + * Copyright 2013 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FOLLY_GEN_STRING_H +#define FOLLY_GEN_STRING_H + +#include "folly/Range.h" +#include "folly/gen/Base.h" + +namespace folly { +namespace gen { + +namespace detail { +class StringResplitter; +class SplitStringSource; + +template +class Unsplit; + +template +class UnsplitBuffer; + +template +class SplitTo; + +} // namespace detail + +/** + * Split the output from a generator into StringPiece "lines" delimited by + * the given delimiter. Delimters are NOT included in the output. + * + * resplit() behaves as if the input strings were concatenated into one long + * string and then split. + */ +// make this a template so we don't require StringResplitter to be complete +// until use +template +S resplit(char delimiter) { + return S(delimiter); +} + +template +S split(const StringPiece& source, char delimiter) { + return S(source, delimiter); +} + +/* + * Joins a sequence of tokens into a string, with the chosen delimiter. + * + * E.G. + * fbstring result = split("a,b,c", ",") | unsplit(","); + * assert(result == "a,b,c"); + * + * std::string result = split("a,b,c", ",") | unsplit(" "); + * assert(result == "a b c"); + */ + + +// NOTE: The template arguments are reversed to allow the user to cleanly +// specify the output type while still inferring the type of the delimiter. +template> +Unsplit unsplit(const Delimiter& delimiter) { + return Unsplit(delimiter); +} + +template> +Unsplit unsplit(const char* delimiter) { + return Unsplit(delimiter); +} + +/* + * Joins a sequence of tokens into a string, appending them to the output + * buffer. If the output buffer is empty, an initial delimiter will not be + * inserted at the start. + * + * E.G. + * std::string buffer; + * split("a,b,c", ",") | unsplit(",", &buffer); + * assert(buffer == "a,b,c"); + * + * std::string anotherBuffer("initial"); + * split("a,b,c", ",") | unsplit(",", &anotherbuffer); + * assert(anotherBuffer == "initial,a,b,c"); + */ +template> +UnsplitBuffer unsplit(Delimiter delimiter, OutputBuffer* outputBuffer) { + return UnsplitBuffer(delimiter, outputBuffer); +} + +template> +UnsplitBuffer unsplit(const char* delimiter, OutputBuffer* outputBuffer) { + return UnsplitBuffer(delimiter, outputBuffer); +} + + +template +detail::Map, char, Targets...>> +eachToTuple(char delim) { + return detail::Map< + detail::SplitTo, char, Targets...>>( + detail::SplitTo, char, Targets...>(delim)); +} + +template +detail::Map, fbstring, Targets...>> +eachToTuple(StringPiece delim) { + return detail::Map< + detail::SplitTo, fbstring, Targets...>>( + detail::SplitTo, fbstring, Targets...>(delim)); +} + +template +detail::Map, char, First, Second>> +eachToPair(char delim) { + return detail::Map< + detail::SplitTo, char, First, Second>>( + detail::SplitTo, char, First, Second>(delim)); +} + +template +detail::Map, fbstring, First, Second>> +eachToPair(StringPiece delim) { + return detail::Map< + detail::SplitTo, fbstring, First, Second>>( + detail::SplitTo, fbstring, First, Second>( + to(delim))); +} + +} // namespace gen +} // namespace folly + +#include "folly/gen/String-inl.h" + +#endif // FOLLY_GEN_STRING_H diff --git a/folly/gen/test/BaseBenchmark.cpp b/folly/gen/test/BaseBenchmark.cpp new file mode 100644 index 00000000..26009743 --- /dev/null +++ b/folly/gen/test/BaseBenchmark.cpp @@ -0,0 +1,344 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include +#include + +#include "folly/Benchmark.h" +#include "folly/gen/Base.h" + +using namespace folly; +using namespace folly::gen; +using std::pair; +using std::set; +using std::vector; +using std::tuple; + +static std::atomic testSize(1000); +static vector testVector = + seq(1, testSize.load()) + | mapped([](int) { return rand(); }) + | as(); + +static vector> testVectorVector = + seq(1, 100) + | map([](int i) { + return seq(1, i) | as(); + }) + | as(); +static vector strings = + from(testVector) + | eachTo() + | as(); + +auto square = [](int x) { return x * x; }; +auto add = [](int a, int b) { return a + b; }; +auto multiply = [](int a, int b) { return a * b; }; + +BENCHMARK(Sum_Basic_NoGen, iters) { + int limit = testSize.load(); + int s = 0; + while (iters--) { + for (int i = 0; i < limit; ++i) { + s += i; + } + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Sum_Basic_Gen, iters) { + int limit = testSize.load(); + int s = 0; + while (iters--) { + s += range(0, limit) | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(Sum_Vector_NoGen, iters) { + int s = 0; + while (iters--) { + for (auto& i : testVector) { + s += i; + } + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Sum_Vector_Gen, iters) { + int s = 0; + while (iters--) { + s += from(testVector) | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(Member, iters) { + int s = 0; + while(iters--) { + s += from(strings) + | member(&fbstring::size) + | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(MapMember, iters) { + int s = 0; + while(iters--) { + s += from(strings) + | map([](const fbstring& x) { return x.size(); }) + | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(Count_Vector_NoGen, iters) { + int s = 0; + while (iters--) { + for (auto& i : testVector) { + if (i * 2 < rand()) { + ++s; + } + } + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Count_Vector_Gen, iters) { + int s = 0; + while (iters--) { + s += from(testVector) + | filter([](int i) { + return i * 2 < rand(); + }) + | count; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(Fib_Sum_NoGen, iters) { + int s = 0; + while (iters--) { + auto fib = [](int limit) -> vector { + vector ret; + int a = 0; + int b = 1; + for (int i = 0; i * 2 < limit; ++i) { + ret.push_back(a += b); + ret.push_back(b += a); + } + return ret; + }; + for (auto& v : fib(testSize.load())) { + s += v; + } + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Fib_Sum_Gen, iters) { + int s = 0; + while (iters--) { + auto fib = GENERATOR(int) { + int a = 0; + int b = 1; + for (;;) { + yield(a += b); + yield(b += a); + } + }; + s += fib | take(testSize.load()) | sum; + } + folly::doNotOptimizeAway(s); +} + +struct FibYielder { + template + void operator()(Yield&& yield) const { + int a = 0; + int b = 1; + for (;;) { + yield(a += b); + yield(b += a); + } + } +}; + +BENCHMARK_RELATIVE(Fib_Sum_Gen_Static, iters) { + int s = 0; + while (iters--) { + auto fib = generator(FibYielder()); + s += fib | take(testSize.load()) | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(VirtualGen_0Virtual, iters) { + int s = 0; + while (iters--) { + auto numbers = seq(1, 10000); + auto squares = numbers | map(square); + auto quads = squares | map(square); + s += quads | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(VirtualGen_1Virtual, iters) { + int s = 0; + while (iters--) { + VirtualGen numbers = seq(1, 10000); + auto squares = numbers | map(square); + auto quads = squares | map(square); + s += quads | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(VirtualGen_2Virtual, iters) { + int s = 0; + while (iters--) { + VirtualGen numbers = seq(1, 10000); + VirtualGen squares = numbers | map(square); + auto quads = squares | map(square); + s += quads | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(VirtualGen_3Virtual, iters) { + int s = 0; + while (iters--) { + VirtualGen numbers = seq(1, 10000); + VirtualGen squares = numbers | map(square); + VirtualGen quads = squares | map(square); + s += quads | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(Concat_NoGen, iters) { + int s = 0; + while (iters--) { + for (auto& v : testVectorVector) { + for (auto& i : v) { + s += i; + } + } + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Concat_Gen, iters) { + int s = 0; + while (iters--) { + s += from(testVectorVector) | rconcat | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(Composed_NoGen, iters) { + int s = 0; + while (iters--) { + for (auto& i : testVector) { + s += i * i; + } + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Composed_Gen, iters) { + int s = 0; + auto sumSq = map(square) | sum; + while (iters--) { + s += from(testVector) | sumSq; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Composed_GenRegular, iters) { + int s = 0; + while (iters--) { + s += from(testVector) | map(square) | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(Sample, iters) { + size_t s = 0; + while (iters--) { + auto sampler = seq(1, 10 * 1000 * 1000) | sample(1000); + s += (sampler | sum); + } + folly::doNotOptimizeAway(s); +} + +// Results from an Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz +// ============================================================================ +// folly/gen/test/BaseBenchmark.cpp relative time/iter iters/s +// ============================================================================ +// Sum_Basic_NoGen 372.39ns 2.69M +// Sum_Basic_Gen 195.96% 190.03ns 5.26M +// ---------------------------------------------------------------------------- +// Sum_Vector_NoGen 200.41ns 4.99M +// Sum_Vector_Gen 77.14% 259.81ns 3.85M +// ---------------------------------------------------------------------------- +// Member 4.56us 219.42K +// MapMember 400.47% 1.14us 878.73K +// ---------------------------------------------------------------------------- +// Count_Vector_NoGen 13.96us 71.64K +// Count_Vector_Gen 86.05% 16.22us 61.65K +// ---------------------------------------------------------------------------- +// Fib_Sum_NoGen 2.21us 452.63K +// Fib_Sum_Gen 23.94% 9.23us 108.36K +// Fib_Sum_Gen_Static 48.77% 4.53us 220.73K +// ---------------------------------------------------------------------------- +// VirtualGen_0Virtual 9.60us 104.13K +// VirtualGen_1Virtual 28.00% 34.30us 29.15K +// VirtualGen_2Virtual 22.62% 42.46us 23.55K +// VirtualGen_3Virtual 16.96% 56.64us 17.66K +// ---------------------------------------------------------------------------- +// Concat_NoGen 2.20us 453.66K +// Concat_Gen 109.49% 2.01us 496.70K +// ---------------------------------------------------------------------------- +// Composed_NoGen 545.32ns 1.83M +// Composed_Gen 87.94% 620.07ns 1.61M +// Composed_GenRegular 88.13% 618.74ns 1.62M +// ---------------------------------------------------------------------------- +// Sample 176.48ms 5.67 +// ============================================================================ + +int main(int argc, char *argv[]) { + google::ParseCommandLineFlags(&argc, &argv, true); + runBenchmarks(); + return 0; +} diff --git a/folly/experimental/test/GenTest.cpp b/folly/gen/test/BaseTest.cpp similarity index 68% rename from folly/experimental/test/GenTest.cpp rename to folly/gen/test/BaseTest.cpp index 35c1414b..3a0b500c 100644 --- a/folly/experimental/test/GenTest.cpp +++ b/folly/gen/test/BaseTest.cpp @@ -16,21 +16,16 @@ #include #include -#include +#include #include #include #include -#include "folly/FBString.h" #include "folly/FBVector.h" -#include "folly/Format.h" #include "folly/MapUtil.h" #include "folly/Memory.h" #include "folly/dynamic.h" -#include "folly/experimental/CombineGen.h" -#include "folly/experimental/FileGen.h" -#include "folly/experimental/Gen.h" -#include "folly/experimental/StringGen.h" +#include "folly/gen/Base.h" #include "folly/experimental/TestUtil.h" using namespace folly::gen; @@ -356,136 +351,6 @@ TEST(Gen, Until) { */ } -auto even = [](int i) -> bool { return i % 2 == 0; }; -auto odd = [](int i) -> bool { return i % 2 == 1; }; - -TEST(CombineGen, Interleave) { - { // large (infinite) base, small container - auto base = seq(1) | filter(odd); - auto toInterleave = seq(1, 6) | filter(even); - auto interleaved = base | interleave(toInterleave | as()); - EXPECT_EQ(interleaved | as(), vector({1, 2, 3, 4, 5, 6})); - } - { // small base, large container - auto base = seq(1) | filter(odd) | take(3); - auto toInterleave = seq(1) | filter(even) | take(50); - auto interleaved = base | interleave(toInterleave | as()); - EXPECT_EQ(interleaved | as(), - vector({1, 2, 3, 4, 5, 6})); - } -} - -TEST(CombineGen, Zip) { - auto base0 = seq(1); - // We rely on std::move(fbvector) emptying the source vector - auto zippee = fbvector{"one", "two", "three"}; - { - auto combined = base0 - | zip(zippee) - | as(); - ASSERT_EQ(combined.size(), 3); - EXPECT_EQ(std::get<0>(combined[0]), 1); - EXPECT_EQ(std::get<1>(combined[0]), "one"); - EXPECT_EQ(std::get<0>(combined[1]), 2); - EXPECT_EQ(std::get<1>(combined[1]), "two"); - EXPECT_EQ(std::get<0>(combined[2]), 3); - EXPECT_EQ(std::get<1>(combined[2]), "three"); - ASSERT_FALSE(zippee.empty()); - EXPECT_FALSE(zippee.front().empty()); // shouldn't have been move'd - } - - { // same as top, but using std::move. - auto combined = base0 - | zip(std::move(zippee)) - | as(); - ASSERT_EQ(combined.size(), 3); - EXPECT_EQ(std::get<0>(combined[0]), 1); - EXPECT_TRUE(zippee.empty()); - } - - { // same as top, but base is truncated - auto baseFinite = seq(1) | take(1); - auto combined = baseFinite - | zip(vector{"one", "two", "three"}) - | as(); - ASSERT_EQ(combined.size(), 1); - EXPECT_EQ(std::get<0>(combined[0]), 1); - EXPECT_EQ(std::get<1>(combined[0]), "one"); - } -} - -TEST(CombineGen, TupleFlatten) { - vector> intStringTupleVec{ - tuple{1, "1"}, - tuple{2, "2"}, - tuple{3, "3"}, - }; - - vector> charTupleVec{ - tuple{'A'}, - tuple{'B'}, - tuple{'C'}, - tuple{'D'}, - }; - - vector doubleVec{ - 1.0, - 4.0, - 9.0, - 16.0, - 25.0, - }; - - auto zipped1 = from(intStringTupleVec) - | zip(charTupleVec) - | assert_type, tuple>>() - | as(); - EXPECT_EQ(std::get<0>(zipped1[0]), std::make_tuple(1, "1")); - EXPECT_EQ(std::get<1>(zipped1[0]), std::make_tuple('A')); - - auto zipped2 = from(zipped1) - | tuple_flatten - | assert_type&&>() - | as(); - ASSERT_EQ(zipped2.size(), 3); - EXPECT_EQ(zipped2[0], std::make_tuple(1, "1", 'A')); - - auto zipped3 = from(charTupleVec) - | zip(intStringTupleVec) - | tuple_flatten - | assert_type&&>() - | as(); - ASSERT_EQ(zipped3.size(), 3); - EXPECT_EQ(zipped3[0], std::make_tuple('A', 1, "1")); - - auto zipped4 = from(intStringTupleVec) - | zip(doubleVec) - | tuple_flatten - | assert_type&&>() - | as(); - ASSERT_EQ(zipped4.size(), 3); - EXPECT_EQ(zipped4[0], std::make_tuple(1, "1", 1.0)); - - auto zipped5 = from(doubleVec) - | zip(doubleVec) - | assert_type>() - | tuple_flatten // essentially a no-op - | assert_type&&>() - | as(); - ASSERT_EQ(zipped5.size(), 5); - EXPECT_EQ(zipped5[0], std::make_tuple(1.0, 1.0)); - - auto zipped6 = from(intStringTupleVec) - | zip(charTupleVec) - | tuple_flatten - | zip(doubleVec) - | tuple_flatten - | assert_type&&>() - | as(); - ASSERT_EQ(zipped6.size(), 3); - EXPECT_EQ(zipped6[0], std::make_tuple(1, "1", 'A', 1.0)); -} - TEST(Gen, Composed) { // Operator, Operator auto valuesOf = @@ -616,8 +481,8 @@ TEST(Gen, MaxBy) { } TEST(Gen, Append) { - fbstring expected = "facebook"; - fbstring actual = "face"; + string expected = "facebook"; + string actual = "face"; from(StringPiece("book")) | appendTo(actual); EXPECT_EQ(expected, actual); } @@ -628,7 +493,7 @@ TEST(Gen, FromRValue) { // reference of a std::vector when it is used as the 'other' for an rvalue // constructor. Use fbvector because we're sure its size will be zero in // this case. - folly::fbvector v({1,2,3,4}); + fbvector v({1,2,3,4}); auto q1 = from(v); EXPECT_EQ(v.size(), 4); // ensure that the lvalue version was called! auto expected = 1 * 2 * 3 * 4; @@ -894,9 +759,9 @@ TEST(Gen, FromStdArray) { TEST(Gen, StringConcat) { auto gen = seq(1, 10) - | map([](int n) { return folly::to(n); }) + | eachTo() | rconcat; - EXPECT_EQ("12345678910", gen | as()); + EXPECT_EQ("12345678910", gen | as()); } struct CopyCounter { @@ -975,33 +840,6 @@ TEST(Gen, Collect) { EXPECT_EQ(s.size(), 5); } -TEST(StringGen, EmptySplit) { - auto collect = eachTo() | as(); - { - auto pieces = split("", ',') | collect; - EXPECT_EQ(0, pieces.size()); - } - - // The last delimiter is eaten, just like std::getline - { - auto pieces = split(",", ',') | collect; - EXPECT_EQ(1, pieces.size()); - EXPECT_EQ("", pieces[0]); - } - - { - auto pieces = split(",,", ',') | collect; - EXPECT_EQ(2, pieces.size()); - EXPECT_EQ("", pieces[0]); - EXPECT_EQ("", pieces[1]); - } - - { - auto pieces = split(",,", ',') | take(1) | collect; - EXPECT_EQ(1, pieces.size()); - EXPECT_EQ("", pieces[0]); - } -} TEST(Gen, Cycle) { { @@ -1095,271 +933,6 @@ TEST(Gen, Dereference) { } } -TEST(StringGen, Split) { - auto collect = eachTo() | as(); - { - auto pieces = split("hello,, world, goodbye, meow", ',') | collect; - EXPECT_EQ(5, pieces.size()); - EXPECT_EQ("hello", pieces[0]); - EXPECT_EQ("", pieces[1]); - EXPECT_EQ(" world", pieces[2]); - EXPECT_EQ(" goodbye", pieces[3]); - EXPECT_EQ(" meow", pieces[4]); - } - - { - auto pieces = split("hello,, world, goodbye, meow", ',') - | take(3) | collect; - EXPECT_EQ(3, pieces.size()); - EXPECT_EQ("hello", pieces[0]); - EXPECT_EQ("", pieces[1]); - EXPECT_EQ(" world", pieces[2]); - } - - { - auto pieces = split("hello,, world, goodbye, meow", ',') - | take(5) | collect; - EXPECT_EQ(5, pieces.size()); - EXPECT_EQ("hello", pieces[0]); - EXPECT_EQ("", pieces[1]); - EXPECT_EQ(" world", pieces[2]); - } -} - -TEST(StringGen, EmptyResplit) { - auto collect = eachTo() | as(); - { - auto pieces = from({""}) | resplit(',') | collect; - EXPECT_EQ(0, pieces.size()); - } - - // The last delimiter is eaten, just like std::getline - { - auto pieces = from({","}) | resplit(',') | collect; - EXPECT_EQ(1, pieces.size()); - EXPECT_EQ("", pieces[0]); - } - - { - auto pieces = from({",,"}) | resplit(',') | collect; - EXPECT_EQ(2, pieces.size()); - EXPECT_EQ("", pieces[0]); - EXPECT_EQ("", pieces[1]); - } -} - -TEST(StringGen, EachToTuple) { - { - auto lines = "2:1.414:yo 3:1.732:hi"; - auto actual - = split(lines, ' ') - | eachToTuple(':') - | as(); - vector> expected { - make_tuple(2, 1.414, "yo"), - make_tuple(3, 1.732, "hi"), - }; - EXPECT_EQ(expected, actual); - } - { - auto lines = "2 3"; - auto actual - = split(lines, ' ') - | eachToTuple(',') - | as(); - vector> expected { - make_tuple(2), - make_tuple(3), - }; - EXPECT_EQ(expected, actual); - } - { - // StringPiece target - auto lines = "1:cat 2:dog"; - auto actual - = split(lines, ' ') - | eachToTuple(':') - | as(); - vector> expected { - make_tuple(1, "cat"), - make_tuple(2, "dog"), - }; - EXPECT_EQ(expected, actual); - } - { - // Empty field - auto lines = "2:tjackson:4 3::5"; - auto actual - = split(lines, ' ') - | eachToTuple(':') - | as(); - vector> expected { - make_tuple(2, "tjackson", 4), - make_tuple(3, "", 5), - }; - EXPECT_EQ(expected, actual); - } - { - // Excess fields - auto lines = "1:2 3:4:5"; - EXPECT_THROW((split(lines, ' ') - | eachToTuple(':') - | as()), - std::runtime_error); - } - { - // Missing fields - auto lines = "1:2:3 4:5"; - EXPECT_THROW((split(lines, ' ') - | eachToTuple(':') - | as()), - std::runtime_error); - } -} - -TEST(StringGen, EachToPair) { - { - // char delimiters - auto lines = "2:1.414 3:1.732"; - auto actual - = split(lines, ' ') - | eachToPair(':') - | as>(); - std::map expected { - { 3, 1.732 }, - { 2, 1.414 }, - }; - EXPECT_EQ(expected, actual); - } - { - // string delimiters - auto lines = "ab=>cd ef=>gh"; - auto actual - = split(lines, ' ') - | eachToPair("=>") - | as>(); - std::map expected { - { "ab", "cd" }, - { "ef", "gh" }, - }; - EXPECT_EQ(expected, actual); - } -} - -TEST(StringGen, Resplit) { - auto collect = eachTo() | as(); - { - auto pieces = from({"hello,, world, goodbye, meow"}) | - resplit(',') | collect; - EXPECT_EQ(5, pieces.size()); - EXPECT_EQ("hello", pieces[0]); - EXPECT_EQ("", pieces[1]); - EXPECT_EQ(" world", pieces[2]); - EXPECT_EQ(" goodbye", pieces[3]); - EXPECT_EQ(" meow", pieces[4]); - } - { - auto pieces = from({"hel", "lo,", ", world", ", goodbye, m", "eow"}) | - resplit(',') | collect; - EXPECT_EQ(5, pieces.size()); - EXPECT_EQ("hello", pieces[0]); - EXPECT_EQ("", pieces[1]); - EXPECT_EQ(" world", pieces[2]); - EXPECT_EQ(" goodbye", pieces[3]); - EXPECT_EQ(" meow", pieces[4]); - } -} - -template -void runUnsplitSuite(F fn) { - fn("hello, world"); - fn("hello,world,goodbye"); - fn(" "); - fn(""); - fn(", "); - fn(", a, b,c"); -} - -TEST(StringGen, Unsplit) { - - auto basicFn = [](const StringPiece& s) { - EXPECT_EQ(split(s, ',') | unsplit(','), s); - }; - - auto existingBuffer = [](const StringPiece& s) { - folly::fbstring buffer("asdf"); - split(s, ',') | unsplit(',', &buffer); - auto expected = folly::to( - "asdf", s.empty() ? "" : ",", s); - EXPECT_EQ(expected, buffer); - }; - - auto emptyBuffer = [](const StringPiece& s) { - std::string buffer; - split(s, ',') | unsplit(',', &buffer); - EXPECT_EQ(s, buffer); - }; - - auto stringDelim = [](const StringPiece& s) { - EXPECT_EQ(s, split(s, ',') | unsplit(",")); - std::string buffer; - split(s, ',') | unsplit(",", &buffer); - EXPECT_EQ(buffer, s); - }; - - runUnsplitSuite(basicFn); - runUnsplitSuite(existingBuffer); - runUnsplitSuite(emptyBuffer); - runUnsplitSuite(stringDelim); - EXPECT_EQ("1, 2, 3", seq(1, 3) | unsplit(", ")); -} - -TEST(FileGen, ByLine) { - auto collect = eachTo() | as(); - test::TemporaryFile file("ByLine"); - static const std::string lines( - "Hello world\n" - "This is the second line\n" - "\n" - "\n" - "a few empty lines above\n" - "incomplete last line"); - EXPECT_EQ(lines.size(), write(file.fd(), lines.data(), lines.size())); - - auto expected = from({lines}) | resplit('\n') | collect; - auto found = byLine(file.path().c_str()) | collect; - - EXPECT_TRUE(expected == found); -} - -class FileGenBufferedTest : public ::testing::TestWithParam { }; - -TEST_P(FileGenBufferedTest, FileWriter) { - size_t bufferSize = GetParam(); - test::TemporaryFile file("FileWriter"); - - static const std::string lines( - "Hello world\n" - "This is the second line\n" - "\n" - "\n" - "a few empty lines above\n"); - - auto src = from({lines, lines, lines, lines, lines, lines, lines, lines}); - auto collect = eachTo() | as(); - auto expected = src | resplit('\n') | collect; - - src | eachAs() | toFile(File(file.fd()), bufferSize); - auto found = byLine(file.path().c_str()) | collect; - - EXPECT_TRUE(expected == found); -} - -INSTANTIATE_TEST_CASE_P( - DifferentBufferSizes, - FileGenBufferedTest, - ::testing::Values(0, 1, 2, 4, 8, 64, 4096)); - TEST(Gen, Guard) { using std::runtime_error; EXPECT_THROW(from({"1", "a", "3"}) diff --git a/folly/gen/test/CombineTest.cpp b/folly/gen/test/CombineTest.cpp new file mode 100644 index 00000000..8f879888 --- /dev/null +++ b/folly/gen/test/CombineTest.cpp @@ -0,0 +1,167 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include +#include +#include +#include + +#include "folly/Range.h" +#include "folly/FBVector.h" +#include "folly/experimental/TestUtil.h" +#include "folly/gen/Base.h" +#include "folly/gen/Combine.h" + +using namespace folly::gen; +using namespace folly; +using std::string; +using std::vector; +using std::tuple; + +auto even = [](int i) -> bool { return i % 2 == 0; }; +auto odd = [](int i) -> bool { return i % 2 == 1; }; + +TEST(CombineGen, Interleave) { + { // large (infinite) base, small container + auto base = seq(1) | filter(odd); + auto toInterleave = seq(1, 6) | filter(even); + auto interleaved = base | interleave(toInterleave | as()); + EXPECT_EQ(interleaved | as(), vector({1, 2, 3, 4, 5, 6})); + } + { // small base, large container + auto base = seq(1) | filter(odd) | take(3); + auto toInterleave = seq(1) | filter(even) | take(50); + auto interleaved = base | interleave(toInterleave | as()); + EXPECT_EQ(interleaved | as(), + vector({1, 2, 3, 4, 5, 6})); + } +} + +TEST(CombineGen, Zip) { + auto base0 = seq(1); + // We rely on std::move(fbvector) emptying the source vector + auto zippee = fbvector{"one", "two", "three"}; + { + auto combined = base0 + | zip(zippee) + | as(); + ASSERT_EQ(combined.size(), 3); + EXPECT_EQ(std::get<0>(combined[0]), 1); + EXPECT_EQ(std::get<1>(combined[0]), "one"); + EXPECT_EQ(std::get<0>(combined[1]), 2); + EXPECT_EQ(std::get<1>(combined[1]), "two"); + EXPECT_EQ(std::get<0>(combined[2]), 3); + EXPECT_EQ(std::get<1>(combined[2]), "three"); + ASSERT_FALSE(zippee.empty()); + EXPECT_FALSE(zippee.front().empty()); // shouldn't have been move'd + } + + { // same as top, but using std::move. + auto combined = base0 + | zip(std::move(zippee)) + | as(); + ASSERT_EQ(combined.size(), 3); + EXPECT_EQ(std::get<0>(combined[0]), 1); + EXPECT_TRUE(zippee.empty()); + } + + { // same as top, but base is truncated + auto baseFinite = seq(1) | take(1); + auto combined = baseFinite + | zip(vector{"one", "two", "three"}) + | as(); + ASSERT_EQ(combined.size(), 1); + EXPECT_EQ(std::get<0>(combined[0]), 1); + EXPECT_EQ(std::get<1>(combined[0]), "one"); + } +} + +TEST(CombineGen, TupleFlatten) { + vector> intStringTupleVec{ + tuple{1, "1"}, + tuple{2, "2"}, + tuple{3, "3"}, + }; + + vector> charTupleVec{ + tuple{'A'}, + tuple{'B'}, + tuple{'C'}, + tuple{'D'}, + }; + + vector doubleVec{ + 1.0, + 4.0, + 9.0, + 16.0, + 25.0, + }; + + auto zipped1 = from(intStringTupleVec) + | zip(charTupleVec) + | assert_type, tuple>>() + | as(); + EXPECT_EQ(std::get<0>(zipped1[0]), std::make_tuple(1, "1")); + EXPECT_EQ(std::get<1>(zipped1[0]), std::make_tuple('A')); + + auto zipped2 = from(zipped1) + | tuple_flatten + | assert_type&&>() + | as(); + ASSERT_EQ(zipped2.size(), 3); + EXPECT_EQ(zipped2[0], std::make_tuple(1, "1", 'A')); + + auto zipped3 = from(charTupleVec) + | zip(intStringTupleVec) + | tuple_flatten + | assert_type&&>() + | as(); + ASSERT_EQ(zipped3.size(), 3); + EXPECT_EQ(zipped3[0], std::make_tuple('A', 1, "1")); + + auto zipped4 = from(intStringTupleVec) + | zip(doubleVec) + | tuple_flatten + | assert_type&&>() + | as(); + ASSERT_EQ(zipped4.size(), 3); + EXPECT_EQ(zipped4[0], std::make_tuple(1, "1", 1.0)); + + auto zipped5 = from(doubleVec) + | zip(doubleVec) + | assert_type>() + | tuple_flatten // essentially a no-op + | assert_type&&>() + | as(); + ASSERT_EQ(zipped5.size(), 5); + EXPECT_EQ(zipped5[0], std::make_tuple(1.0, 1.0)); + + auto zipped6 = from(intStringTupleVec) + | zip(charTupleVec) + | tuple_flatten + | zip(doubleVec) + | tuple_flatten + | assert_type&&>() + | as(); + ASSERT_EQ(zipped6.size(), 3); + EXPECT_EQ(zipped6[0], std::make_tuple(1, "1", 'A', 1.0)); +} + +int main(int argc, char *argv[]) { + testing::InitGoogleTest(&argc, argv); + google::ParseCommandLineFlags(&argc, &argv, true); + return RUN_ALL_TESTS(); +} diff --git a/folly/gen/test/FileBenchmark.cpp b/folly/gen/test/FileBenchmark.cpp new file mode 100644 index 00000000..339fd293 --- /dev/null +++ b/folly/gen/test/FileBenchmark.cpp @@ -0,0 +1,70 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include +#include + +#include "folly/Benchmark.h" +#include "folly/File.h" +#include "folly/gen/Base.h" +#include "folly/gen/File.h" + +using namespace folly::gen; + +BENCHMARK(ByLine_Pipes, iters) { + std::thread thread; + int rfd; + int wfd; + BENCHMARK_SUSPEND { + int p[2]; + CHECK_ERR(::pipe(p)); + rfd = p[0]; + wfd = p[1]; + thread = std::thread([wfd, iters] { + char x = 'x'; + PCHECK(::write(wfd, &x, 1) == 1); // signal startup + FILE* f = fdopen(wfd, "w"); + PCHECK(f); + for (int i = 1; i <= iters; ++i) { + fprintf(f, "%d\n", i); + } + fclose(f); + }); + char buf; + PCHECK(::read(rfd, &buf, 1) == 1); // wait for startup + } + + auto s = byLine(folly::File(rfd)) | eachTo() | sum; + folly::doNotOptimizeAway(s); + + BENCHMARK_SUSPEND { + ::close(rfd); + CHECK_EQ(s, int64_t(iters) * (iters + 1) / 2); + thread.join(); + } +} + +// Results from an Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz +// ============================================================================ +// folly/gen/test/FileBenchmark.cpp relative time/iter iters/s +// ============================================================================ +// ByLine_Pipes 148.63ns 6.73M +// ============================================================================ + +int main(int argc, char *argv[]) { + google::ParseCommandLineFlags(&argc, &argv, true); + folly::runBenchmarks(); + return 0; +} diff --git a/folly/gen/test/FileTest.cpp b/folly/gen/test/FileTest.cpp new file mode 100644 index 00000000..fe9b3540 --- /dev/null +++ b/folly/gen/test/FileTest.cpp @@ -0,0 +1,80 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include +#include +#include + +#include "folly/File.h" +#include "folly/Range.h" +#include "folly/experimental/TestUtil.h" +#include "folly/gen/Base.h" +#include "folly/gen/File.h" + +using namespace folly::gen; +using namespace folly; +using std::string; +using std::vector; + +TEST(FileGen, ByLine) { + auto collect = eachTo() | as(); + test::TemporaryFile file("ByLine"); + static const std::string lines( + "Hello world\n" + "This is the second line\n" + "\n" + "\n" + "a few empty lines above\n" + "incomplete last line"); + EXPECT_EQ(lines.size(), write(file.fd(), lines.data(), lines.size())); + + auto expected = from({lines}) | resplit('\n') | collect; + auto found = byLine(file.path().c_str()) | collect; + + EXPECT_TRUE(expected == found); +} + +class FileGenBufferedTest : public ::testing::TestWithParam { }; + +TEST_P(FileGenBufferedTest, FileWriter) { + size_t bufferSize = GetParam(); + test::TemporaryFile file("FileWriter"); + + static const std::string lines( + "Hello world\n" + "This is the second line\n" + "\n" + "\n" + "a few empty lines above\n"); + + auto src = from({lines, lines, lines, lines, lines, lines, lines, lines}); + auto collect = eachTo() | as(); + auto expected = src | resplit('\n') | collect; + + src | eachAs() | toFile(File(file.fd()), bufferSize); + auto found = byLine(file.path().c_str()) | collect; + + EXPECT_TRUE(expected == found); +} + +INSTANTIATE_TEST_CASE_P( + DifferentBufferSizes, + FileGenBufferedTest, + ::testing::Values(0, 1, 2, 4, 8, 64, 4096)); +int main(int argc, char *argv[]) { + testing::InitGoogleTest(&argc, argv); + google::ParseCommandLineFlags(&argc, &argv, true); + return RUN_ALL_TESTS(); +} diff --git a/folly/gen/test/StringBenchmark.cpp b/folly/gen/test/StringBenchmark.cpp new file mode 100644 index 00000000..5c143ec4 --- /dev/null +++ b/folly/gen/test/StringBenchmark.cpp @@ -0,0 +1,329 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include +#include + +#include "folly/Benchmark.h" +#include "folly/String.h" +#include "folly/gen/Base.h" +#include "folly/gen/String.h" + +using namespace folly; +using namespace folly::gen; +using std::pair; +using std::set; +using std::vector; +using std::tuple; + +namespace { + +static std::atomic testSize(1000); +static vector testStrVector + = seq(1, testSize.load()) + | eachTo() + | as(); + +const char* const kLine = "The quick brown fox jumped over the lazy dog.\n"; +const size_t kLineCount = 10000; +std::string bigLines; +const size_t kSmallLineSize = 17; +std::vector smallLines; + +void initStringResplitterBenchmark() { + bigLines.reserve(kLineCount * strlen(kLine)); + for (size_t i = 0; i < kLineCount; ++i) { + bigLines += kLine; + } + size_t remaining = bigLines.size(); + size_t pos = 0; + while (remaining) { + size_t n = std::min(kSmallLineSize, remaining); + smallLines.push_back(bigLines.substr(pos, n)); + pos += n; + remaining -= n; + } +} + +size_t len(folly::StringPiece s) { return s.size(); } + +} // namespace + +BENCHMARK(StringResplitter_Big, iters) { + size_t s = 0; + while (iters--) { + s += from({bigLines}) | resplit('\n') | map(&len) | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(StringResplitter_Small, iters) { + size_t s = 0; + while (iters--) { + s += from(smallLines) | resplit('\n') | map(&len) | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(StringSplit_Old, iters) { + size_t s = 0; + std::string line(kLine); + while (iters--) { + std::vector parts; + split(' ', line, parts); + s += parts.size(); + } + folly::doNotOptimizeAway(s); +} + + +BENCHMARK_RELATIVE(StringSplit_Gen_Vector, iters) { + size_t s = 0; + StringPiece line(kLine); + while (iters--) { + s += (split(line, ' ') | as()).size(); + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(StringSplit_Old_ReuseVector, iters) { + size_t s = 0; + std::string line(kLine); + std::vector parts; + while (iters--) { + parts.clear(); + split(' ', line, parts); + s += parts.size(); + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(StringSplit_Gen_ReuseVector, iters) { + size_t s = 0; + StringPiece line(kLine); + std::vector parts; + while (iters--) { + parts.clear(); + split(line, ' ') | appendTo(parts); + s += parts.size(); + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(StringSplit_Gen, iters) { + size_t s = 0; + StringPiece line(kLine); + while (iters--) { + s += split(line, ' ') | count; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(StringSplit_Gen_Take, iters) { + size_t s = 0; + StringPiece line(kLine); + while (iters--) { + s += split(line, ' ') | take(10) | count; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +BENCHMARK(StringUnsplit_Old, iters) { + size_t s = 0; + while (iters--) { + fbstring joined; + join(',', testStrVector, joined); + s += joined.size(); + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(StringUnsplit_Old_ReusedBuffer, iters) { + size_t s = 0; + fbstring joined; + while (iters--) { + joined.clear(); + join(',', testStrVector, joined); + s += joined.size(); + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(StringUnsplit_Gen, iters) { + size_t s = 0; + StringPiece line(kLine); + while (iters--) { + fbstring joined = from(testStrVector) | unsplit(','); + s += joined.size(); + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(StringUnsplit_Gen_ReusedBuffer, iters) { + size_t s = 0; + fbstring buffer; + while (iters--) { + buffer.clear(); + from(testStrVector) | unsplit(',', &buffer); + s += buffer.size(); + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_DRAW_LINE() + +void StringUnsplit_Gen(size_t iters, size_t joinSize) { + std::vector v; + BENCHMARK_SUSPEND { + FOR_EACH_RANGE(i, 0, joinSize) { + v.push_back(to(rand())); + } + } + size_t s = 0; + fbstring buffer; + while (iters--) { + buffer.clear(); + from(v) | unsplit(',', &buffer); + s += buffer.size(); + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_PARAM(StringUnsplit_Gen, 1000) +BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 2000) +BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 4000) +BENCHMARK_RELATIVE_PARAM(StringUnsplit_Gen, 8000) + +BENCHMARK_DRAW_LINE() + +fbstring records += seq(1, 1000) + | mapped([](size_t i) { + return folly::to(i, ' ', i * i, ' ', i * i * i); + }) + | unsplit('\n'); + +BENCHMARK(Records_EachToTuple, iters) { + size_t s = 0; + for (size_t i = 0; i < iters; i += 1000) { + s += split(records, '\n') + | eachToTuple(' ') + | get<1>() + | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Records_VectorStringPieceReused, iters) { + size_t s = 0; + std::vector fields; + for (size_t i = 0; i < iters; i += 1000) { + s += split(records, '\n') + | mapped([&](StringPiece line) { + fields.clear(); + folly::split(' ', line, fields); + CHECK(fields.size() == 3); + return std::make_tuple( + folly::to(fields[0]), + folly::to(fields[1]), + StringPiece(fields[2])); + }) + | get<1>() + | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Records_VectorStringPiece, iters) { + size_t s = 0; + for (size_t i = 0; i < iters; i += 1000) { + s += split(records, '\n') + | mapped([](StringPiece line) { + std::vector fields; + folly::split(' ', line, fields); + CHECK(fields.size() == 3); + return std::make_tuple( + folly::to(fields[0]), + folly::to(fields[1]), + StringPiece(fields[2])); + }) + | get<1>() + | sum; + } + folly::doNotOptimizeAway(s); +} + +BENCHMARK_RELATIVE(Records_VectorString, iters) { + size_t s = 0; + for (size_t i = 0; i < iters; i += 1000) { + s += split(records, '\n') + | mapped([](StringPiece line) { + std::vector fields; + folly::split(' ', line, fields); + CHECK(fields.size() == 3); + return std::make_tuple( + folly::to(fields[0]), + folly::to(fields[1]), + StringPiece(fields[2])); + }) + | get<1>() + | sum; + } + folly::doNotOptimizeAway(s); +} + +// Results from an Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz +// ============================================================================ +// folly/gen/test/StringBenchmark.cpp relative time/iter iters/s +// ============================================================================ +// StringResplitter_Big 108.58us 9.21K +// StringResplitter_Small 10.60% 1.02ms 976.48 +// ---------------------------------------------------------------------------- +// StringSplit_Old 357.82ns 2.79M +// StringSplit_Gen_Vector 105.10% 340.46ns 2.94M +// ---------------------------------------------------------------------------- +// StringSplit_Old_ReuseVector 96.45ns 10.37M +// StringSplit_Gen_ReuseVector 124.01% 77.78ns 12.86M +// StringSplit_Gen 140.10% 68.85ns 14.52M +// StringSplit_Gen_Take 122.97% 78.44ns 12.75M +// ---------------------------------------------------------------------------- +// StringUnsplit_Old 42.99us 23.26K +// StringUnsplit_Old_ReusedBuffer 100.48% 42.79us 23.37K +// StringUnsplit_Gen 96.37% 44.61us 22.42K +// StringUnsplit_Gen_ReusedBuffer 116.96% 36.76us 27.20K +// ---------------------------------------------------------------------------- +// StringUnsplit_Gen(1000) 44.71us 22.37K +// StringUnsplit_Gen(2000) 49.28% 90.72us 11.02K +// StringUnsplit_Gen(4000) 24.05% 185.91us 5.38K +// StringUnsplit_Gen(8000) 12.23% 365.42us 2.74K +// ---------------------------------------------------------------------------- +// Records_EachToTuple 101.43us 9.86K +// Records_VectorStringPieceReused 93.72% 108.22us 9.24K +// Records_VectorStringPiece 37.14% 273.11us 3.66K +// Records_VectorString 16.70% 607.47us 1.65K +// ============================================================================ + +int main(int argc, char *argv[]) { + google::ParseCommandLineFlags(&argc, &argv, true); + initStringResplitterBenchmark(); + runBenchmarks(); + return 0; +} diff --git a/folly/gen/test/StringTest.cpp b/folly/gen/test/StringTest.cpp new file mode 100644 index 00000000..17fb9c09 --- /dev/null +++ b/folly/gen/test/StringTest.cpp @@ -0,0 +1,286 @@ +/* + * Copyright 2014 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include +#include +#include + +#include "folly/gen/String.h" + +using namespace folly::gen; +using namespace folly; +using std::make_tuple; +using std::ostream; +using std::pair; +using std::string; +using std::tuple; +using std::unique_ptr; +using std::vector; + +TEST(StringGen, EmptySplit) { + auto collect = eachTo() | as(); + { + auto pieces = split("", ',') | collect; + EXPECT_EQ(0, pieces.size()); + } + + // The last delimiter is eaten, just like std::getline + { + auto pieces = split(",", ',') | collect; + EXPECT_EQ(1, pieces.size()); + EXPECT_EQ("", pieces[0]); + } + + { + auto pieces = split(",,", ',') | collect; + EXPECT_EQ(2, pieces.size()); + EXPECT_EQ("", pieces[0]); + EXPECT_EQ("", pieces[1]); + } + + { + auto pieces = split(",,", ',') | take(1) | collect; + EXPECT_EQ(1, pieces.size()); + EXPECT_EQ("", pieces[0]); + } +} + +TEST(StringGen, Split) { + auto collect = eachTo() | as(); + { + auto pieces = split("hello,, world, goodbye, meow", ',') | collect; + EXPECT_EQ(5, pieces.size()); + EXPECT_EQ("hello", pieces[0]); + EXPECT_EQ("", pieces[1]); + EXPECT_EQ(" world", pieces[2]); + EXPECT_EQ(" goodbye", pieces[3]); + EXPECT_EQ(" meow", pieces[4]); + } + + { + auto pieces = split("hello,, world, goodbye, meow", ',') + | take(3) | collect; + EXPECT_EQ(3, pieces.size()); + EXPECT_EQ("hello", pieces[0]); + EXPECT_EQ("", pieces[1]); + EXPECT_EQ(" world", pieces[2]); + } + + { + auto pieces = split("hello,, world, goodbye, meow", ',') + | take(5) | collect; + EXPECT_EQ(5, pieces.size()); + EXPECT_EQ("hello", pieces[0]); + EXPECT_EQ("", pieces[1]); + EXPECT_EQ(" world", pieces[2]); + } +} + +TEST(StringGen, EmptyResplit) { + auto collect = eachTo() | as(); + { + auto pieces = from({""}) | resplit(',') | collect; + EXPECT_EQ(0, pieces.size()); + } + + // The last delimiter is eaten, just like std::getline + { + auto pieces = from({","}) | resplit(',') | collect; + EXPECT_EQ(1, pieces.size()); + EXPECT_EQ("", pieces[0]); + } + + { + auto pieces = from({",,"}) | resplit(',') | collect; + EXPECT_EQ(2, pieces.size()); + EXPECT_EQ("", pieces[0]); + EXPECT_EQ("", pieces[1]); + } +} + +TEST(StringGen, EachToTuple) { + { + auto lines = "2:1.414:yo 3:1.732:hi"; + auto actual + = split(lines, ' ') + | eachToTuple(':') + | as(); + vector> expected { + make_tuple(2, 1.414, "yo"), + make_tuple(3, 1.732, "hi"), + }; + EXPECT_EQ(expected, actual); + } + { + auto lines = "2 3"; + auto actual + = split(lines, ' ') + | eachToTuple(',') + | as(); + vector> expected { + make_tuple(2), + make_tuple(3), + }; + EXPECT_EQ(expected, actual); + } + { + // StringPiece target + auto lines = "1:cat 2:dog"; + auto actual + = split(lines, ' ') + | eachToTuple(':') + | as(); + vector> expected { + make_tuple(1, "cat"), + make_tuple(2, "dog"), + }; + EXPECT_EQ(expected, actual); + } + { + // Empty field + auto lines = "2:tjackson:4 3::5"; + auto actual + = split(lines, ' ') + | eachToTuple(':') + | as(); + vector> expected { + make_tuple(2, "tjackson", 4), + make_tuple(3, "", 5), + }; + EXPECT_EQ(expected, actual); + } + { + // Excess fields + auto lines = "1:2 3:4:5"; + EXPECT_THROW((split(lines, ' ') + | eachToTuple(':') + | as()), + std::runtime_error); + } + { + // Missing fields + auto lines = "1:2:3 4:5"; + EXPECT_THROW((split(lines, ' ') + | eachToTuple(':') + | as()), + std::runtime_error); + } +} + +TEST(StringGen, EachToPair) { + { + // char delimiters + auto lines = "2:1.414 3:1.732"; + auto actual + = split(lines, ' ') + | eachToPair(':') + | as>(); + std::map expected { + { 3, 1.732 }, + { 2, 1.414 }, + }; + EXPECT_EQ(expected, actual); + } + { + // string delimiters + auto lines = "ab=>cd ef=>gh"; + auto actual + = split(lines, ' ') + | eachToPair("=>") + | as>(); + std::map expected { + { "ab", "cd" }, + { "ef", "gh" }, + }; + EXPECT_EQ(expected, actual); + } +} + +TEST(StringGen, Resplit) { + auto collect = eachTo() | as(); + { + auto pieces = from({"hello,, world, goodbye, meow"}) | + resplit(',') | collect; + EXPECT_EQ(5, pieces.size()); + EXPECT_EQ("hello", pieces[0]); + EXPECT_EQ("", pieces[1]); + EXPECT_EQ(" world", pieces[2]); + EXPECT_EQ(" goodbye", pieces[3]); + EXPECT_EQ(" meow", pieces[4]); + } + { + auto pieces = from({"hel", "lo,", ", world", ", goodbye, m", "eow"}) | + resplit(',') | collect; + EXPECT_EQ(5, pieces.size()); + EXPECT_EQ("hello", pieces[0]); + EXPECT_EQ("", pieces[1]); + EXPECT_EQ(" world", pieces[2]); + EXPECT_EQ(" goodbye", pieces[3]); + EXPECT_EQ(" meow", pieces[4]); + } +} + +template +void runUnsplitSuite(F fn) { + fn("hello, world"); + fn("hello,world,goodbye"); + fn(" "); + fn(""); + fn(", "); + fn(", a, b,c"); +} + +TEST(StringGen, Unsplit) { + + auto basicFn = [](StringPiece s) { + EXPECT_EQ(split(s, ',') | unsplit(','), s); + }; + + auto existingBuffer = [](StringPiece s) { + folly::fbstring buffer("asdf"); + split(s, ',') | unsplit(',', &buffer); + auto expected = folly::to( + "asdf", s.empty() ? "" : ",", s); + EXPECT_EQ(expected, buffer); + }; + + auto emptyBuffer = [](StringPiece s) { + std::string buffer; + split(s, ',') | unsplit(',', &buffer); + EXPECT_EQ(s, buffer); + }; + + auto stringDelim = [](StringPiece s) { + EXPECT_EQ(s, split(s, ',') | unsplit(",")); + std::string buffer; + split(s, ',') | unsplit(",", &buffer); + EXPECT_EQ(buffer, s); + }; + + runUnsplitSuite(basicFn); + runUnsplitSuite(existingBuffer); + runUnsplitSuite(emptyBuffer); + runUnsplitSuite(stringDelim); + EXPECT_EQ("1, 2, 3", seq(1, 3) | unsplit(", ")); +} + +int main(int argc, char *argv[]) { + testing::InitGoogleTest(&argc, argv); + google::ParseCommandLineFlags(&argc, &argv, true); + return RUN_ALL_TESTS(); +} -- 2.34.1