1// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
2// Licensed under the MIT License:
3//
4// Permission is hereby granted, free of charge, to any person obtaining a copy
5// of this software and associated documentation files (the "Software"), to deal
6// in the Software without restriction, including without limitation the rights
7// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8// copies of the Software, and to permit persons to whom the Software is
9// furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20// THE SOFTWARE.
21
22// This file defines a notion of tuples that is simpler that `std::tuple`. It works as follows:
23// - `kj::Tuple<A, B, C> is the type of a tuple of an A, a B, and a C.
24// - `kj::tuple(a, b, c)` returns a tuple containing a, b, and c. If any of these are themselves
25// tuples, they are flattened, so `tuple(a, tuple(b, c), d)` is equivalent to `tuple(a, b, c, d)`.
26// - `kj::get<n>(myTuple)` returns the element of `myTuple` at index n.
27// - `kj::apply(func, ...)` calls func on the following arguments after first expanding any tuples
28// in the argument list. So `kj::apply(foo, a, tuple(b, c), d)` would call `foo(a, b, c, d)`.
29//
30// Note that:
31// - The type `Tuple<T>` is a synonym for T. This is why `get` and `apply` are not members of the
32// type.
33// - It is illegal for an element of `Tuple` to itself be a tuple, as tuples are meant to be
34// flattened.
35// - It is illegal for an element of `Tuple` to be a reference, due to problems this would cause
36// with type inference and `tuple()`.
37
38#pragma once
39
40#if defined(__GNUC__) && !KJ_HEADER_WARNINGS
41#pragma GCC system_header
42#endif
43
44#include "common.h"
45
46namespace kj {
47namespace _ { // private
48
49template <size_t index, typename... T>
50struct TypeByIndex_;
51template <typename First, typename... Rest>
52struct TypeByIndex_<0, First, Rest...> {
53 typedef First Type;
54};
55template <size_t index, typename First, typename... Rest>
56struct TypeByIndex_<index, First, Rest...>
57 : public TypeByIndex_<index - 1, Rest...> {};
58template <size_t index>
59struct TypeByIndex_<index> {
60 static_assert(index != index, "Index out-of-range.");
61};
62template <size_t index, typename... T>
63using TypeByIndex = typename TypeByIndex_<index, T...>::Type;
64// Chose a particular type out of a list of types, by index.
65
66template <size_t... s>
67struct Indexes {};
68// Dummy helper type that just encapsulates a sequential list of indexes, so that we can match
69// templates against them and unpack them with '...'.
70
71template <size_t end, size_t... prefix>
72struct MakeIndexes_: public MakeIndexes_<end - 1, end - 1, prefix...> {};
73template <size_t... prefix>
74struct MakeIndexes_<0, prefix...> {
75 typedef Indexes<prefix...> Type;
76};
77template <size_t end>
78using MakeIndexes = typename MakeIndexes_<end>::Type;
79// Equivalent to Indexes<0, 1, 2, ..., end>.
80
81template <typename... T>
82class Tuple;
83template <size_t index, typename... U>
84inline TypeByIndex<index, U...>& getImpl(Tuple<U...>& tuple);
85template <size_t index, typename... U>
86inline TypeByIndex<index, U...>&& getImpl(Tuple<U...>&& tuple);
87template <size_t index, typename... U>
88inline const TypeByIndex<index, U...>& getImpl(const Tuple<U...>& tuple);
89
90template <uint index, typename T>
91struct TupleElement {
92 // Encapsulates one element of a tuple. The actual tuple implementation multiply-inherits
93 // from a TupleElement for each element, which is more efficient than a recursive definition.
94
95 T value;
96 TupleElement() KJ_DEFAULT_CONSTRUCTOR_VS2015_BUGGY
97 constexpr inline TupleElement(const T& value): value(value) {}
98 constexpr inline TupleElement(T&& value): value(kj::mv(value)) {}
99};
100
101template <uint index, typename T>
102struct TupleElement<index, T&> {
103 // A tuple containing references can be constucted using refTuple().
104
105 T& value;
106 constexpr inline TupleElement(T& value): value(value) {}
107};
108
109template <uint index, typename... T>
110struct TupleElement<index, Tuple<T...>> {
111 static_assert(sizeof(Tuple<T...>*) == 0,
112 "Tuples cannot contain other tuples -- they should be flattened.");
113};
114
115template <typename Indexes, typename... Types>
116struct TupleImpl;
117
118template <size_t... indexes, typename... Types>
119struct TupleImpl<Indexes<indexes...>, Types...>
120 : public TupleElement<indexes, Types>... {
121 // Implementation of Tuple. The only reason we need this rather than rolling this into class
122 // Tuple (below) is so that we can get "indexes" as an unpackable list.
123
124 static_assert(sizeof...(indexes) == sizeof...(Types), "Incorrect use of TupleImpl.");
125
126 TupleImpl() KJ_DEFAULT_CONSTRUCTOR_VS2015_BUGGY
127
128 template <typename... Params>
129 inline TupleImpl(Params&&... params)
130 : TupleElement<indexes, Types>(kj::fwd<Params>(params))... {
131 // Work around Clang 3.2 bug 16303 where this is not detected. (Unfortunately, Clang sometimes
132 // segfaults instead.)
133 static_assert(sizeof...(params) == sizeof...(indexes),
134 "Wrong number of parameters to Tuple constructor.");
135 }
136
137 template <typename... U>
138 constexpr inline TupleImpl(Tuple<U...>&& other)
139 : TupleElement<indexes, Types>(kj::fwd<U>(getImpl<indexes>(other)))... {}
140 template <typename... U>
141 constexpr inline TupleImpl(Tuple<U...>& other)
142 : TupleElement<indexes, Types>(getImpl<indexes>(other))... {}
143 template <typename... U>
144 constexpr inline TupleImpl(const Tuple<U...>& other)
145 : TupleElement<indexes, Types>(getImpl<indexes>(other))... {}
146};
147
148struct MakeTupleFunc;
149struct MakeRefTupleFunc;
150
151template <typename... T>
152class Tuple {
153 // The actual Tuple class (used for tuples of size other than 1).
154
155public:
156 Tuple() KJ_DEFAULT_CONSTRUCTOR_VS2015_BUGGY
157
158 template <typename... U>
159 constexpr inline Tuple(Tuple<U...>&& other): impl(kj::mv(other)) {}
160 template <typename... U>
161 constexpr inline Tuple(Tuple<U...>& other): impl(other) {}
162 template <typename... U>
163 constexpr inline Tuple(const Tuple<U...>& other): impl(other) {}
164
165private:
166 template <typename... Params>
167 constexpr Tuple(Params&&... params): impl(kj::fwd<Params>(params)...) {}
168
169 TupleImpl<MakeIndexes<sizeof...(T)>, T...> impl;
170
171 template <size_t index, typename... U>
172 friend inline TypeByIndex<index, U...>& getImpl(Tuple<U...>& tuple);
173 template <size_t index, typename... U>
174 friend inline TypeByIndex<index, U...>&& getImpl(Tuple<U...>&& tuple);
175 template <size_t index, typename... U>
176 friend inline const TypeByIndex<index, U...>& getImpl(const Tuple<U...>& tuple);
177 friend struct MakeTupleFunc;
178 friend struct MakeRefTupleFunc;
179};
180
181template <>
182class Tuple<> {
183 // Simplified zero-member version of Tuple. In particular this is important to make sure that
184 // Tuple<>() is constexpr.
185};
186
187template <typename T>
188class Tuple<T>;
189// Single-element tuple should never be used. The public API should ensure this.
190
191template <size_t index, typename... T>
192inline TypeByIndex<index, T...>& getImpl(Tuple<T...>& tuple) {
193 // Get member of a Tuple by index, e.g. `get<2>(myTuple)`.
194 static_assert(index < sizeof...(T), "Tuple element index out-of-bounds.");
195 return implicitCast<TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value;
196}
197template <size_t index, typename... T>
198inline TypeByIndex<index, T...>&& getImpl(Tuple<T...>&& tuple) {
199 // Get member of a Tuple by index, e.g. `get<2>(myTuple)`.
200 static_assert(index < sizeof...(T), "Tuple element index out-of-bounds.");
201 return kj::mv(implicitCast<TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value);
202}
203template <size_t index, typename... T>
204inline const TypeByIndex<index, T...>& getImpl(const Tuple<T...>& tuple) {
205 // Get member of a Tuple by index, e.g. `get<2>(myTuple)`.
206 static_assert(index < sizeof...(T), "Tuple element index out-of-bounds.");
207 return implicitCast<const TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value;
208}
209template <size_t index, typename T>
210inline T&& getImpl(T&& value) {
211 // Get member of a Tuple by index, e.g. `getImpl<2>(myTuple)`.
212
213 // Non-tuples are equivalent to one-element tuples.
214 static_assert(index == 0, "Tuple element index out-of-bounds.");
215 return kj::fwd<T>(value);
216}
217
218
219template <typename Func, typename SoFar, typename... T>
220struct ExpandAndApplyResult_;
221// Template which computes the return type of applying Func to T... after flattening tuples.
222// SoFar starts as Tuple<> and accumulates the flattened parameter types -- so after this template
223// is recursively expanded, T... is empty and SoFar is a Tuple containing all the parameters.
224
225template <typename Func, typename First, typename... Rest, typename... T>
226struct ExpandAndApplyResult_<Func, Tuple<T...>, First, Rest...>
227 : public ExpandAndApplyResult_<Func, Tuple<T..., First>, Rest...> {};
228template <typename Func, typename... FirstTypes, typename... Rest, typename... T>
229struct ExpandAndApplyResult_<Func, Tuple<T...>, Tuple<FirstTypes...>, Rest...>
230 : public ExpandAndApplyResult_<Func, Tuple<T...>, FirstTypes&&..., Rest...> {};
231template <typename Func, typename... FirstTypes, typename... Rest, typename... T>
232struct ExpandAndApplyResult_<Func, Tuple<T...>, Tuple<FirstTypes...>&, Rest...>
233 : public ExpandAndApplyResult_<Func, Tuple<T...>, FirstTypes&..., Rest...> {};
234template <typename Func, typename... FirstTypes, typename... Rest, typename... T>
235struct ExpandAndApplyResult_<Func, Tuple<T...>, const Tuple<FirstTypes...>&, Rest...>
236 : public ExpandAndApplyResult_<Func, Tuple<T...>, const FirstTypes&..., Rest...> {};
237template <typename Func, typename... T>
238struct ExpandAndApplyResult_<Func, Tuple<T...>> {
239 typedef decltype(instance<Func>()(instance<T&&>()...)) Type;
240};
241template <typename Func, typename... T>
242using ExpandAndApplyResult = typename ExpandAndApplyResult_<Func, Tuple<>, T...>::Type;
243// Computes the expected return type of `expandAndApply()`.
244
245template <typename Func>
246inline auto expandAndApply(Func&& func) -> ExpandAndApplyResult<Func> {
247 return func();
248}
249
250template <typename Func, typename First, typename... Rest>
251struct ExpandAndApplyFunc {
252 Func&& func;
253 First&& first;
254 ExpandAndApplyFunc(Func&& func, First&& first)
255 : func(kj::fwd<Func>(func)), first(kj::fwd<First>(first)) {}
256 template <typename... T>
257 auto operator()(T&&... params)
258 -> decltype(this->func(kj::fwd<First>(first), kj::fwd<T>(params)...)) {
259 return this->func(kj::fwd<First>(first), kj::fwd<T>(params)...);
260 }
261};
262
263template <typename Func, typename First, typename... Rest>
264inline auto expandAndApply(Func&& func, First&& first, Rest&&... rest)
265 -> ExpandAndApplyResult<Func, First, Rest...> {
266
267 return expandAndApply(
268 ExpandAndApplyFunc<Func, First, Rest...>(kj::fwd<Func>(func), kj::fwd<First>(first)),
269 kj::fwd<Rest>(rest)...);
270}
271
272template <typename Func, typename... FirstTypes, typename... Rest>
273inline auto expandAndApply(Func&& func, Tuple<FirstTypes...>&& first, Rest&&... rest)
274 -> ExpandAndApplyResult<Func, FirstTypes&&..., Rest...> {
275 return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(),
276 kj::fwd<Func>(func), kj::mv(first), kj::fwd<Rest>(rest)...);
277}
278
279template <typename Func, typename... FirstTypes, typename... Rest>
280inline auto expandAndApply(Func&& func, Tuple<FirstTypes...>& first, Rest&&... rest)
281 -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> {
282 return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(),
283 kj::fwd<Func>(func), first, kj::fwd<Rest>(rest)...);
284}
285
286template <typename Func, typename... FirstTypes, typename... Rest>
287inline auto expandAndApply(Func&& func, const Tuple<FirstTypes...>& first, Rest&&... rest)
288 -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> {
289 return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(),
290 kj::fwd<Func>(func), first, kj::fwd<Rest>(rest)...);
291}
292
293template <typename Func, typename... FirstTypes, typename... Rest, size_t... indexes>
294inline auto expandAndApplyWithIndexes(
295 Indexes<indexes...>, Func&& func, Tuple<FirstTypes...>&& first, Rest&&... rest)
296 -> ExpandAndApplyResult<Func, FirstTypes&&..., Rest...> {
297 return expandAndApply(kj::fwd<Func>(func), kj::mv(getImpl<indexes>(first))...,
298 kj::fwd<Rest>(rest)...);
299}
300
301template <typename Func, typename... FirstTypes, typename... Rest, size_t... indexes>
302inline auto expandAndApplyWithIndexes(
303 Indexes<indexes...>, Func&& func, const Tuple<FirstTypes...>& first, Rest&&... rest)
304 -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> {
305 return expandAndApply(kj::fwd<Func>(func), getImpl<indexes>(first)...,
306 kj::fwd<Rest>(rest)...);
307}
308
309struct MakeTupleFunc {
310 template <typename... Params>
311 Tuple<Decay<Params>...> operator()(Params&&... params) {
312 return Tuple<Decay<Params>...>(kj::fwd<Params>(params)...);
313 }
314 template <typename Param>
315 Decay<Param> operator()(Param&& param) {
316 return kj::fwd<Param>(param);
317 }
318};
319
320struct MakeRefTupleFunc {
321 template <typename... Params>
322 Tuple<Params...> operator()(Params&&... params) {
323 return Tuple<Params...>(kj::fwd<Params>(params)...);
324 }
325 template <typename Param>
326 Param operator()(Param&& param) {
327 return kj::fwd<Param>(param);
328 }
329};
330
331} // namespace _ (private)
332
333template <typename... T> struct Tuple_ { typedef _::Tuple<T...> Type; };
334template <typename T> struct Tuple_<T> { typedef T Type; };
335
336template <typename... T> using Tuple = typename Tuple_<T...>::Type;
337// Tuple type. `Tuple<T>` (i.e. a single-element tuple) is a synonym for `T`. Tuples of size
338// other than 1 expand to an internal type. Either way, you can construct a Tuple using
339// `kj::tuple(...)`, get an element by index `i` using `kj::get<i>(myTuple)`, and expand the tuple
340// as arguments to a function using `kj::apply(func, myTuple)`.
341//
342// Tuples are always flat -- that is, no element of a Tuple is ever itself a Tuple. If you
343// construct a tuple from other tuples, the elements are flattened and concatenated.
344
345template <typename... Params>
346inline auto tuple(Params&&... params)
347 -> decltype(_::expandAndApply(_::MakeTupleFunc(), kj::fwd<Params>(params)...)) {
348 // Construct a new tuple from the given values. Any tuples in the argument list will be
349 // flattened into the result.
350 return _::expandAndApply(_::MakeTupleFunc(), kj::fwd<Params>(params)...);
351}
352
353template <typename... Params>
354inline auto refTuple(Params&&... params)
355 -> decltype(_::expandAndApply(_::MakeRefTupleFunc(), kj::fwd<Params>(params)...)) {
356 // Like tuple(), but if the params include lvalue references, they will be captured as
357 // references. rvalue references will still be captured as whole values (moved).
358 return _::expandAndApply(_::MakeRefTupleFunc(), kj::fwd<Params>(params)...);
359}
360
361template <size_t index, typename Tuple>
362inline auto get(Tuple&& tuple) -> decltype(_::getImpl<index>(kj::fwd<Tuple>(tuple))) {
363 // Unpack and return the tuple element at the given index. The index is specified as a template
364 // parameter, e.g. `kj::get<3>(myTuple)`.
365 return _::getImpl<index>(kj::fwd<Tuple>(tuple));
366}
367
368template <typename Func, typename... Params>
369inline auto apply(Func&& func, Params&&... params)
370 -> decltype(_::expandAndApply(kj::fwd<Func>(func), kj::fwd<Params>(params)...)) {
371 // Apply a function to some arguments, expanding tuples into separate arguments.
372 return _::expandAndApply(kj::fwd<Func>(func), kj::fwd<Params>(params)...);
373}
374
375template <typename T> struct TupleSize_ { static constexpr size_t size = 1; };
376template <typename... T> struct TupleSize_<_::Tuple<T...>> {
377 static constexpr size_t size = sizeof...(T);
378};
379
380template <typename T>
381constexpr size_t tupleSize() { return TupleSize_<T>::size; }
382// Returns size of the tuple T.
383
384template <typename T, typename Tuple>
385struct IndexOfType_;
386template <typename T, typename Tuple>
387struct HasType_ {
388 static constexpr bool value = false;
389};
390
391template <typename T>
392struct IndexOfType_<T, T> {
393 static constexpr size_t value = 0;
394};
395template <typename T>
396struct HasType_<T, T> {
397 static constexpr bool value = true;
398};
399
400template <typename T, typename... U>
401struct IndexOfType_<T, _::Tuple<T, U...>> {
402 static constexpr size_t value = 0;
403 static_assert(!HasType_<T, _::Tuple<U...>>::value,
404 "requested type appears multiple times in tuple");
405};
406template <typename T, typename... U>
407struct HasType_<T, _::Tuple<T, U...>> {
408 static constexpr bool value = true;
409};
410
411template <typename T, typename U, typename... V>
412struct IndexOfType_<T, _::Tuple<U, V...>> {
413 static constexpr size_t value = IndexOfType_<T, _::Tuple<V...>>::value + 1;
414};
415template <typename T, typename U, typename... V>
416struct HasType_<T, _::Tuple<U, V...>> {
417 static constexpr bool value = HasType_<T, _::Tuple<V...>>::value;
418};
419
420template <typename T, typename U>
421inline constexpr size_t indexOfType() {
422 static_assert(HasType_<T, U>::value, "type not present");
423 return IndexOfType_<T, U>::value;
424}
425
426template <size_t i, typename T>
427struct TypeOfIndex_;
428template <typename T>
429struct TypeOfIndex_<0, T> {
430 typedef T Type;
431};
432template <size_t i, typename T, typename... U>
433struct TypeOfIndex_<i, _::Tuple<T, U...>>
434 : public TypeOfIndex_<i - 1, _::Tuple<U...>> {};
435template <typename T, typename... U>
436struct TypeOfIndex_<0, _::Tuple<T, U...>> {
437 typedef T Type;
438};
439
440template <size_t i, typename Tuple>
441using TypeOfIndex = typename TypeOfIndex_<i, Tuple>::Type;
442
443} // namespace kj
444