cannam@147: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
cannam@147: // Licensed under the MIT License:
cannam@147: //
cannam@147: // Permission is hereby granted, free of charge, to any person obtaining a copy
cannam@147: // of this software and associated documentation files (the "Software"), to deal
cannam@147: // in the Software without restriction, including without limitation the rights
cannam@147: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
cannam@147: // copies of the Software, and to permit persons to whom the Software is
cannam@147: // furnished to do so, subject to the following conditions:
cannam@147: //
cannam@147: // The above copyright notice and this permission notice shall be included in
cannam@147: // all copies or substantial portions of the Software.
cannam@147: //
cannam@147: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
cannam@147: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
cannam@147: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
cannam@147: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
cannam@147: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
cannam@147: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
cannam@147: // THE SOFTWARE.
cannam@147: 
cannam@147: // This file defines a notion of tuples that is simpler that `std::tuple`.  It works as follows:
cannam@147: // - `kj::Tuple<A, B, C> is the type of a tuple of an A, a B, and a C.
cannam@147: // - `kj::tuple(a, b, c)` returns a tuple containing a, b, and c.  If any of these are themselves
cannam@147: //   tuples, they are flattened, so `tuple(a, tuple(b, c), d)` is equivalent to `tuple(a, b, c, d)`.
cannam@147: // - `kj::get<n>(myTuple)` returns the element of `myTuple` at index n.
cannam@147: // - `kj::apply(func, ...)` calls func on the following arguments after first expanding any tuples
cannam@147: //   in the argument list.  So `kj::apply(foo, a, tuple(b, c), d)` would call `foo(a, b, c, d)`.
cannam@147: //
cannam@147: // Note that:
cannam@147: // - The type `Tuple<T>` is a synonym for T.  This is why `get` and `apply` are not members of the
cannam@147: //   type.
cannam@147: // - It is illegal for an element of `Tuple` to itself be a tuple, as tuples are meant to be
cannam@147: //   flattened.
cannam@147: // - It is illegal for an element of `Tuple` to be a reference, due to problems this would cause
cannam@147: //   with type inference and `tuple()`.
cannam@147: 
cannam@147: #ifndef KJ_TUPLE_H_
cannam@147: #define KJ_TUPLE_H_
cannam@147: 
cannam@147: #if defined(__GNUC__) && !KJ_HEADER_WARNINGS
cannam@147: #pragma GCC system_header
cannam@147: #endif
cannam@147: 
cannam@147: #include "common.h"
cannam@147: 
cannam@147: namespace kj {
cannam@147: namespace _ {  // private
cannam@147: 
cannam@147: template <size_t index, typename... T>
cannam@147: struct TypeByIndex_;
cannam@147: template <typename First, typename... Rest>
cannam@147: struct TypeByIndex_<0, First, Rest...> {
cannam@147:   typedef First Type;
cannam@147: };
cannam@147: template <size_t index, typename First, typename... Rest>
cannam@147: struct TypeByIndex_<index, First, Rest...>
cannam@147:     : public TypeByIndex_<index - 1, Rest...> {};
cannam@147: template <size_t index>
cannam@147: struct TypeByIndex_<index> {
cannam@147:   static_assert(index != index, "Index out-of-range.");
cannam@147: };
cannam@147: template <size_t index, typename... T>
cannam@147: using TypeByIndex = typename TypeByIndex_<index, T...>::Type;
cannam@147: // Chose a particular type out of a list of types, by index.
cannam@147: 
cannam@147: template <size_t... s>
cannam@147: struct Indexes {};
cannam@147: // Dummy helper type that just encapsulates a sequential list of indexes, so that we can match
cannam@147: // templates against them and unpack them with '...'.
cannam@147: 
cannam@147: template <size_t end, size_t... prefix>
cannam@147: struct MakeIndexes_: public MakeIndexes_<end - 1, end - 1, prefix...> {};
cannam@147: template <size_t... prefix>
cannam@147: struct MakeIndexes_<0, prefix...> {
cannam@147:   typedef Indexes<prefix...> Type;
cannam@147: };
cannam@147: template <size_t end>
cannam@147: using MakeIndexes = typename MakeIndexes_<end>::Type;
cannam@147: // Equivalent to Indexes<0, 1, 2, ..., end>.
cannam@147: 
cannam@147: template <typename... T>
cannam@147: class Tuple;
cannam@147: template <size_t index, typename... U>
cannam@147: inline TypeByIndex<index, U...>& getImpl(Tuple<U...>& tuple);
cannam@147: template <size_t index, typename... U>
cannam@147: inline TypeByIndex<index, U...>&& getImpl(Tuple<U...>&& tuple);
cannam@147: template <size_t index, typename... U>
cannam@147: inline const TypeByIndex<index, U...>& getImpl(const Tuple<U...>& tuple);
cannam@147: 
cannam@147: template <uint index, typename T>
cannam@147: struct TupleElement {
cannam@147:   // Encapsulates one element of a tuple.  The actual tuple implementation multiply-inherits
cannam@147:   // from a TupleElement for each element, which is more efficient than a recursive definition.
cannam@147: 
cannam@147:   T value;
cannam@147:   TupleElement() = default;
cannam@147:   constexpr inline TupleElement(const T& value): value(value) {}
cannam@147:   constexpr inline TupleElement(T&& value): value(kj::mv(value)) {}
cannam@147: };
cannam@147: 
cannam@147: template <uint index, typename T>
cannam@147: struct TupleElement<index, T&> {
cannam@147:   // If tuples contained references, one of the following would have to be true:
cannam@147:   // - `auto x = tuple(y, z)` would cause x to be a tuple of references to y and z, which is
cannam@147:   //   probably not what you expected.
cannam@147:   // - `Tuple<Foo&, Bar&> x = tuple(a, b)` would not work, because `tuple()` returned
cannam@147:   //   Tuple<Foo, Bar>.
cannam@147:   static_assert(sizeof(T*) == 0, "Sorry, tuples cannot contain references.");
cannam@147: };
cannam@147: 
cannam@147: template <uint index, typename... T>
cannam@147: struct TupleElement<index, Tuple<T...>> {
cannam@147:   static_assert(sizeof(Tuple<T...>*) == 0,
cannam@147:                 "Tuples cannot contain other tuples -- they should be flattened.");
cannam@147: };
cannam@147: 
cannam@147: template <typename Indexes, typename... Types>
cannam@147: struct TupleImpl;
cannam@147: 
cannam@147: template <size_t... indexes, typename... Types>
cannam@147: struct TupleImpl<Indexes<indexes...>, Types...>
cannam@147:     : public TupleElement<indexes, Types>... {
cannam@147:   // Implementation of Tuple.  The only reason we need this rather than rolling this into class
cannam@147:   // Tuple (below) is so that we can get "indexes" as an unpackable list.
cannam@147: 
cannam@147:   static_assert(sizeof...(indexes) == sizeof...(Types), "Incorrect use of TupleImpl.");
cannam@147: 
cannam@147:   template <typename... Params>
cannam@147:   inline TupleImpl(Params&&... params)
cannam@147:       : TupleElement<indexes, Types>(kj::fwd<Params>(params))... {
cannam@147:     // Work around Clang 3.2 bug 16303 where this is not detected.  (Unfortunately, Clang sometimes
cannam@147:     // segfaults instead.)
cannam@147:     static_assert(sizeof...(params) == sizeof...(indexes),
cannam@147:                   "Wrong number of parameters to Tuple constructor.");
cannam@147:   }
cannam@147: 
cannam@147:   template <typename... U>
cannam@147:   constexpr inline TupleImpl(Tuple<U...>&& other)
cannam@147:       : TupleElement<indexes, Types>(kj::mv(getImpl<indexes>(other)))... {}
cannam@147:   template <typename... U>
cannam@147:   constexpr inline TupleImpl(Tuple<U...>& other)
cannam@147:       : TupleElement<indexes, Types>(getImpl<indexes>(other))... {}
cannam@147:   template <typename... U>
cannam@147:   constexpr inline TupleImpl(const Tuple<U...>& other)
cannam@147:       : TupleElement<indexes, Types>(getImpl<indexes>(other))... {}
cannam@147: };
cannam@147: 
cannam@147: struct MakeTupleFunc;
cannam@147: 
cannam@147: template <typename... T>
cannam@147: class Tuple {
cannam@147:   // The actual Tuple class (used for tuples of size other than 1).
cannam@147: 
cannam@147: public:
cannam@147:   template <typename... U>
cannam@147:   constexpr inline Tuple(Tuple<U...>&& other): impl(kj::mv(other)) {}
cannam@147:   template <typename... U>
cannam@147:   constexpr inline Tuple(Tuple<U...>& other): impl(other) {}
cannam@147:   template <typename... U>
cannam@147:   constexpr inline Tuple(const Tuple<U...>& other): impl(other) {}
cannam@147: 
cannam@147: private:
cannam@147:   template <typename... Params>
cannam@147:   constexpr Tuple(Params&&... params): impl(kj::fwd<Params>(params)...) {}
cannam@147: 
cannam@147:   TupleImpl<MakeIndexes<sizeof...(T)>, T...> impl;
cannam@147: 
cannam@147:   template <size_t index, typename... U>
cannam@147:   friend inline TypeByIndex<index, U...>& getImpl(Tuple<U...>& tuple);
cannam@147:   template <size_t index, typename... U>
cannam@147:   friend inline TypeByIndex<index, U...>&& getImpl(Tuple<U...>&& tuple);
cannam@147:   template <size_t index, typename... U>
cannam@147:   friend inline const TypeByIndex<index, U...>& getImpl(const Tuple<U...>& tuple);
cannam@147:   friend struct MakeTupleFunc;
cannam@147: };
cannam@147: 
cannam@147: template <>
cannam@147: class Tuple<> {
cannam@147:   // Simplified zero-member version of Tuple.  In particular this is important to make sure that
cannam@147:   // Tuple<>() is constexpr.
cannam@147: };
cannam@147: 
cannam@147: template <typename T>
cannam@147: class Tuple<T>;
cannam@147: // Single-element tuple should never be used.  The public API should ensure this.
cannam@147: 
cannam@147: template <size_t index, typename... T>
cannam@147: inline TypeByIndex<index, T...>& getImpl(Tuple<T...>& tuple) {
cannam@147:   // Get member of a Tuple by index, e.g. `get<2>(myTuple)`.
cannam@147:   static_assert(index < sizeof...(T), "Tuple element index out-of-bounds.");
cannam@147:   return implicitCast<TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value;
cannam@147: }
cannam@147: template <size_t index, typename... T>
cannam@147: inline TypeByIndex<index, T...>&& getImpl(Tuple<T...>&& tuple) {
cannam@147:   // Get member of a Tuple by index, e.g. `get<2>(myTuple)`.
cannam@147:   static_assert(index < sizeof...(T), "Tuple element index out-of-bounds.");
cannam@147:   return kj::mv(implicitCast<TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value);
cannam@147: }
cannam@147: template <size_t index, typename... T>
cannam@147: inline const TypeByIndex<index, T...>& getImpl(const Tuple<T...>& tuple) {
cannam@147:   // Get member of a Tuple by index, e.g. `get<2>(myTuple)`.
cannam@147:   static_assert(index < sizeof...(T), "Tuple element index out-of-bounds.");
cannam@147:   return implicitCast<const TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value;
cannam@147: }
cannam@147: template <size_t index, typename T>
cannam@147: inline T&& getImpl(T&& value) {
cannam@147:   // Get member of a Tuple by index, e.g. `getImpl<2>(myTuple)`.
cannam@147: 
cannam@147:   // Non-tuples are equivalent to one-element tuples.
cannam@147:   static_assert(index == 0, "Tuple element index out-of-bounds.");
cannam@147:   return kj::fwd<T>(value);
cannam@147: }
cannam@147: 
cannam@147: 
cannam@147: template <typename Func, typename SoFar, typename... T>
cannam@147: struct ExpandAndApplyResult_;
cannam@147: // Template which computes the return type of applying Func to T... after flattening tuples.
cannam@147: // SoFar starts as Tuple<> and accumulates the flattened parameter types -- so after this template
cannam@147: // is recursively expanded, T... is empty and SoFar is a Tuple containing all the parameters.
cannam@147: 
cannam@147: template <typename Func, typename First, typename... Rest, typename... T>
cannam@147: struct ExpandAndApplyResult_<Func, Tuple<T...>, First, Rest...>
cannam@147:     : public ExpandAndApplyResult_<Func, Tuple<T..., First>, Rest...> {};
cannam@147: template <typename Func, typename... FirstTypes, typename... Rest, typename... T>
cannam@147: struct ExpandAndApplyResult_<Func, Tuple<T...>, Tuple<FirstTypes...>, Rest...>
cannam@147:     : public ExpandAndApplyResult_<Func, Tuple<T...>, FirstTypes&&..., Rest...> {};
cannam@147: template <typename Func, typename... FirstTypes, typename... Rest, typename... T>
cannam@147: struct ExpandAndApplyResult_<Func, Tuple<T...>, Tuple<FirstTypes...>&, Rest...>
cannam@147:     : public ExpandAndApplyResult_<Func, Tuple<T...>, FirstTypes&..., Rest...> {};
cannam@147: template <typename Func, typename... FirstTypes, typename... Rest, typename... T>
cannam@147: struct ExpandAndApplyResult_<Func, Tuple<T...>, const Tuple<FirstTypes...>&, Rest...>
cannam@147:     : public ExpandAndApplyResult_<Func, Tuple<T...>, const FirstTypes&..., Rest...> {};
cannam@147: template <typename Func, typename... T>
cannam@147: struct ExpandAndApplyResult_<Func, Tuple<T...>> {
cannam@147:   typedef decltype(instance<Func>()(instance<T&&>()...)) Type;
cannam@147: };
cannam@147: template <typename Func, typename... T>
cannam@147: using ExpandAndApplyResult = typename ExpandAndApplyResult_<Func, Tuple<>, T...>::Type;
cannam@147: // Computes the expected return type of `expandAndApply()`.
cannam@147: 
cannam@147: template <typename Func>
cannam@147: inline auto expandAndApply(Func&& func) -> ExpandAndApplyResult<Func> {
cannam@147:   return func();
cannam@147: }
cannam@147: 
cannam@147: template <typename Func, typename First, typename... Rest>
cannam@147: struct ExpandAndApplyFunc {
cannam@147:   Func&& func;
cannam@147:   First&& first;
cannam@147:   ExpandAndApplyFunc(Func&& func, First&& first)
cannam@147:       : func(kj::fwd<Func>(func)), first(kj::fwd<First>(first)) {}
cannam@147:   template <typename... T>
cannam@147:   auto operator()(T&&... params)
cannam@147:       -> decltype(this->func(kj::fwd<First>(first), kj::fwd<T>(params)...)) {
cannam@147:     return this->func(kj::fwd<First>(first), kj::fwd<T>(params)...);
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: template <typename Func, typename First, typename... Rest>
cannam@147: inline auto expandAndApply(Func&& func, First&& first, Rest&&... rest)
cannam@147:     -> ExpandAndApplyResult<Func, First, Rest...> {
cannam@147: 
cannam@147:   return expandAndApply(
cannam@147:       ExpandAndApplyFunc<Func, First, Rest...>(kj::fwd<Func>(func), kj::fwd<First>(first)),
cannam@147:       kj::fwd<Rest>(rest)...);
cannam@147: }
cannam@147: 
cannam@147: template <typename Func, typename... FirstTypes, typename... Rest>
cannam@147: inline auto expandAndApply(Func&& func, Tuple<FirstTypes...>&& first, Rest&&... rest)
cannam@147:     -> ExpandAndApplyResult<Func, FirstTypes&&..., Rest...> {
cannam@147:   return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(),
cannam@147:       kj::fwd<Func>(func), kj::mv(first), kj::fwd<Rest>(rest)...);
cannam@147: }
cannam@147: 
cannam@147: template <typename Func, typename... FirstTypes, typename... Rest>
cannam@147: inline auto expandAndApply(Func&& func, Tuple<FirstTypes...>& first, Rest&&... rest)
cannam@147:     -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> {
cannam@147:   return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(),
cannam@147:       kj::fwd<Func>(func), first, kj::fwd<Rest>(rest)...);
cannam@147: }
cannam@147: 
cannam@147: template <typename Func, typename... FirstTypes, typename... Rest>
cannam@147: inline auto expandAndApply(Func&& func, const Tuple<FirstTypes...>& first, Rest&&... rest)
cannam@147:     -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> {
cannam@147:   return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(),
cannam@147:       kj::fwd<Func>(func), first, kj::fwd<Rest>(rest)...);
cannam@147: }
cannam@147: 
cannam@147: template <typename Func, typename... FirstTypes, typename... Rest, size_t... indexes>
cannam@147: inline auto expandAndApplyWithIndexes(
cannam@147:     Indexes<indexes...>, Func&& func, Tuple<FirstTypes...>&& first, Rest&&... rest)
cannam@147:     -> ExpandAndApplyResult<Func, FirstTypes&&..., Rest...> {
cannam@147:   return expandAndApply(kj::fwd<Func>(func), kj::mv(getImpl<indexes>(first))...,
cannam@147:                         kj::fwd<Rest>(rest)...);
cannam@147: }
cannam@147: 
cannam@147: template <typename Func, typename... FirstTypes, typename... Rest, size_t... indexes>
cannam@147: inline auto expandAndApplyWithIndexes(
cannam@147:     Indexes<indexes...>, Func&& func, const Tuple<FirstTypes...>& first, Rest&&... rest)
cannam@147:     -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> {
cannam@147:   return expandAndApply(kj::fwd<Func>(func), getImpl<indexes>(first)...,
cannam@147:                        kj::fwd<Rest>(rest)...);
cannam@147: }
cannam@147: 
cannam@147: struct MakeTupleFunc {
cannam@147:   template <typename... Params>
cannam@147:   Tuple<Decay<Params>...> operator()(Params&&... params) {
cannam@147:     return Tuple<Decay<Params>...>(kj::fwd<Params>(params)...);
cannam@147:   }
cannam@147:   template <typename Param>
cannam@147:   Decay<Param> operator()(Param&& param) {
cannam@147:     return kj::fwd<Param>(param);
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: }  // namespace _ (private)
cannam@147: 
cannam@147: template <typename... T> struct Tuple_ { typedef _::Tuple<T...> Type; };
cannam@147: template <typename T> struct Tuple_<T> { typedef T Type; };
cannam@147: 
cannam@147: template <typename... T> using Tuple = typename Tuple_<T...>::Type;
cannam@147: // Tuple type.  `Tuple<T>` (i.e. a single-element tuple) is a synonym for `T`.  Tuples of size
cannam@147: // other than 1 expand to an internal type.  Either way, you can construct a Tuple using
cannam@147: // `kj::tuple(...)`, get an element by index `i` using `kj::get<i>(myTuple)`, and expand the tuple
cannam@147: // as arguments to a function using `kj::apply(func, myTuple)`.
cannam@147: //
cannam@147: // Tuples are always flat -- that is, no element of a Tuple is ever itself a Tuple.  If you
cannam@147: // construct a tuple from other tuples, the elements are flattened and concatenated.
cannam@147: 
cannam@147: template <typename... Params>
cannam@147: inline auto tuple(Params&&... params)
cannam@147:     -> decltype(_::expandAndApply(_::MakeTupleFunc(), kj::fwd<Params>(params)...)) {
cannam@147:   // Construct a new tuple from the given values.  Any tuples in the argument list will be
cannam@147:   // flattened into the result.
cannam@147:   return _::expandAndApply(_::MakeTupleFunc(), kj::fwd<Params>(params)...);
cannam@147: }
cannam@147: 
cannam@147: template <size_t index, typename Tuple>
cannam@147: inline auto get(Tuple&& tuple) -> decltype(_::getImpl<index>(kj::fwd<Tuple>(tuple))) {
cannam@147:   // Unpack and return the tuple element at the given index.  The index is specified as a template
cannam@147:   // parameter, e.g. `kj::get<3>(myTuple)`.
cannam@147:   return _::getImpl<index>(kj::fwd<Tuple>(tuple));
cannam@147: }
cannam@147: 
cannam@147: template <typename Func, typename... Params>
cannam@147: inline auto apply(Func&& func, Params&&... params)
cannam@147:     -> decltype(_::expandAndApply(kj::fwd<Func>(func), kj::fwd<Params>(params)...)) {
cannam@147:   // Apply a function to some arguments, expanding tuples into separate arguments.
cannam@147:   return _::expandAndApply(kj::fwd<Func>(func), kj::fwd<Params>(params)...);
cannam@147: }
cannam@147: 
cannam@147: template <typename T> struct TupleSize_ { static constexpr size_t size = 1; };
cannam@147: template <typename... T> struct TupleSize_<_::Tuple<T...>> {
cannam@147:   static constexpr size_t size = sizeof...(T);
cannam@147: };
cannam@147: 
cannam@147: template <typename T>
cannam@147: constexpr size_t tupleSize() { return TupleSize_<T>::size; }
cannam@147: // Returns size of the tuple T.
cannam@147: 
cannam@147: }  // namespace kj
cannam@147: 
cannam@147: #endif  // KJ_TUPLE_H_