From d5550513ae99ac1a9c59bb7a7dcd86e03739b890 Mon Sep 17 00:00:00 2001 From: Tudor Bosman Date: Thu, 21 May 2015 07:54:11 -0700 Subject: [PATCH] tupleRange, tuplePrepend Summary: tupleRange(tuple): return a tuple consisting of a range of elements from the given tuple tuplePrepend(x, tuple): return a tuple consisting of prepending x to the given tuple. For Lispies: std::get<0>(tuple) is car. tupleRange<1>(tuple) is cdr. tuplePrepend(x, tuple) is cons. Test Plan: test added Reviewed By: lesha@fb.com Subscribers: trunkagent, lesha, ilyam, folly-diffs@, yfeldblum, chalfant, jhj, alerer, kma, pamelavagata, tulloch FB internal diff: D2087568 Signature: t1:2087568:1432164681:18795d0e8bb01f38ffc6949ac233f514ab098355 --- folly/Makefile.am | 1 + folly/experimental/TupleOps.h | 127 +++++++++++++++++++ folly/experimental/test/TupleOpsTest.cpp | 148 +++++++++++++++++++++++ 3 files changed, 276 insertions(+) create mode 100644 folly/experimental/TupleOps.h create mode 100644 folly/experimental/test/TupleOpsTest.cpp diff --git a/folly/Makefile.am b/folly/Makefile.am index 3d656b78..2220ceca 100644 --- a/folly/Makefile.am +++ b/folly/Makefile.am @@ -110,6 +110,7 @@ nobase_follyinclude_HEADERS = \ experimental/StringKeyedUnorderedMap.h \ experimental/StringKeyedUnorderedSet.h \ experimental/TestUtil.h \ + experimental/TupleOps.h \ FBString.h \ FBVector.h \ File.h \ diff --git a/folly/experimental/TupleOps.h b/folly/experimental/TupleOps.h new file mode 100644 index 00000000..bf2e4bb8 --- /dev/null +++ b/folly/experimental/TupleOps.h @@ -0,0 +1,127 @@ +/* + * Copyright 2015 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_TUPLEOPS_H_ +#define FOLLY_TUPLEOPS_H_ + +#include +#include +#include + +// tupleRange(tuple): select n elements starting at index start +// in the given tuple +// tupleRange(tuple): select all elements starting at index start +// until the end of the given tuple +// tuplePrepend(x, tuple): return a tuple obtained by prepending x to the +// given tuple. +// +// In Lisp lingo, std::get<0> is car, tupleRange<1> is cdr, and tuplePrepend +// is cons. + +namespace folly { + +// TemplateSeq is a type parametrized by sizeof...(Xs) values of type +// T. Used to destructure the values into a template parameter pack; +// see the example in TupleSelect, below. +template +struct TemplateSeq { + template + using Prepend = TemplateSeq; +}; + +// TemplateRange::type is +// TemplateSeq +template struct TemplateRange; + +template +struct TemplateRange< + T, start, n, + typename std::enable_if<(n > 0)>::type> { + using type = + typename TemplateRange::type::template Prepend; +}; + +template +struct TemplateRange< + T, start, n, + typename std::enable_if<(n <= 0)>::type> { + using type = TemplateSeq; +}; + +// Similar to TemplateRange, given a tuple T, +// TemplateTupleRange::type is +// TemplateSeq +// where k = min(tuple_size::value - start, n) +// (that is, it's a TemplateSeq of at most n elements, but won't extend +// past the end of the given tuple) +template ::max(), + std::size_t size = + std::tuple_size::type>::value, + class Enable = typename std::enable_if<(start <= size)>::type> +struct TemplateTupleRange { + using type = typename TemplateRange< + std::size_t, + start, + (n <= size - start ? n : size - start)>::type; +}; + +namespace detail { + +// Helper class to select a subset of a tuple +template struct TupleSelect; +template +struct TupleSelect> { + template + static auto select(T&& v) + -> decltype(std::make_tuple(std::get(std::forward(v))...)) { + return std::make_tuple(std::get(std::forward(v))...); + } +}; + +} // namespace detail + +// Return a tuple consisting of the elements at a range of indices. +// +// Use as tupleRange(t) to return a tuple of (at most) n +// elements starting at index start in tuple t. +// If only start is specified (tupleRange(t)), returns all elements +// starting at index start until the end of the tuple t. +// Won't compile if start > size of t. +// Will return fewer elements (size - start) if start + n > size of t. +template < + std::size_t start = 0, + std::size_t n = std::numeric_limits::max(), + class T, + class Seq = typename TemplateTupleRange::type> +auto tupleRange(T&& v) +-> decltype(detail::TupleSelect::select(std::forward(v))) { + return detail::TupleSelect::select(std::forward(v)); +} + +// Return a tuple obtained by prepending car to the tuple cdr. +template +auto tuplePrepend(T&& car, U&& cdr) +-> decltype(std::tuple_cat(std::make_tuple(std::forward(car)), + std::forward(cdr))) { + return std::tuple_cat(std::make_tuple(std::forward(car)), + std::forward(cdr)); +} + +} // namespaces + +#endif /* FOLLY_TUPLEOPS_H_ */ diff --git a/folly/experimental/test/TupleOpsTest.cpp b/folly/experimental/test/TupleOpsTest.cpp new file mode 100644 index 00000000..7e044e49 --- /dev/null +++ b/folly/experimental/test/TupleOpsTest.cpp @@ -0,0 +1,148 @@ +/* + * Copyright 2015 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 + +namespace folly { namespace test { + +TEST(TupleOps, Copiable) { + auto t = std::make_tuple(10, std::string("hello"), 30); + + EXPECT_EQ(10, std::get<0>(t)); + auto t1 = tupleRange<1>(t); + EXPECT_EQ("hello", std::get<0>(t1)); + EXPECT_EQ(2, std::tuple_size::value); + auto t2 = tupleRange<1, 1>(t); + EXPECT_EQ(1, std::tuple_size::value); + EXPECT_EQ("hello", std::get<0>(t2)); + EXPECT_EQ(30, std::get<0>(tupleRange<1>(tupleRange<1>(t)))); + + EXPECT_TRUE(t == tuplePrepend(std::get<0>(t), tupleRange<1>(t))); +} + +class MovableInt { + public: + explicit MovableInt(int value) : value_(value) { } + int value() const { return value_; } + + MovableInt(MovableInt&&) = default; + MovableInt& operator=(MovableInt&&) = default; + MovableInt(const MovableInt&) = delete; + MovableInt& operator=(const MovableInt&) = delete; + + private: + int value_; +}; + +bool operator==(const MovableInt& a, const MovableInt& b) { + return a.value() == b.value(); +} + +TEST(TupleOps, Movable) { + auto t1 = std::make_tuple(MovableInt(10), std::string("hello"), 30); + auto t2 = std::make_tuple(MovableInt(10), std::string("hello"), 30); + auto t3 = std::make_tuple(MovableInt(10), std::string("hello"), 30); + + auto t1car = std::get<0>(std::move(t1)); + auto t2cdr = tupleRange<1>(std::move(t2)); + + EXPECT_TRUE(t3 == tuplePrepend(std::move(t1car), std::move(t2cdr))); +} + +// Given a tuple of As, convert to a tuple of Bs (of the same size) +// by calling folly::to on matching types. +// +// There are two example implementation: tupleTo (using tail recursion), which +// may create a lot of intermediate tuples, and tupleTo2, using +// TemplateTupleRange directly (below). +template +U tupleTo(const T& input); + +template struct TupleTo; + +// Base case: empty typle -> empty tuple +template <> +struct TupleTo, std::tuple<>> { + static std::tuple<> convert(const std::tuple<>& input) { + return std::make_tuple(); + } +}; + +// Induction case: split off head element and convert it, then call tupleTo on +// the tail. +template +struct TupleTo< + std::tuple, + T> { + static std::tuple convert(const T& input) { + return tuplePrepend( + folly::to(std::get<0>(input)), + tupleTo>(tupleRange<1>(input))); + } +}; + +template +U tupleTo(const T& input) { + return TupleTo::convert(input); +} + +template struct TupleTo2; + +// Destructure all indexes into Ns... and use parameter pack expansion +// to repeat the conversion for each individual element, then wrap +// all results with make_tuple. +template +struct TupleTo2> { + template + static U convert(const T& input) { + return std::make_tuple( + folly::to::type>( + std::get(input))...); + } +}; + +template ::type, + class Enable = typename std::enable_if< + (std::tuple_size::value == std::tuple_size::value)>::type> +U tupleTo2(const T& input) { + return TupleTo2::template convert(input); +} + +#define CHECK_TUPLE_TO(converter) \ + do { \ + auto src = std::make_tuple(42, "50", 10); \ + auto dest = converter>(src); \ + EXPECT_EQ("42", std::get<0>(dest)); \ + EXPECT_EQ(50, std::get<1>(dest)); \ + EXPECT_EQ(10, std::get<2>(dest)); \ + } while (false) + +TEST(TupleOps, TupleTo) { + CHECK_TUPLE_TO(tupleTo); +} + +TEST(TupleOps, TupleTo2) { + CHECK_TUPLE_TO(tupleTo2); +} + +#undef CHECK_TUPLE_TO + +}} // namespaces -- 2.34.1