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 | |
46 | namespace kj { |
47 | namespace _ { // private |
48 | |
49 | template <size_t index, typename... T> |
50 | struct TypeByIndex_; |
51 | template <typename First, typename... Rest> |
52 | struct TypeByIndex_<0, First, Rest...> { |
53 | typedef First Type; |
54 | }; |
55 | template <size_t index, typename First, typename... Rest> |
56 | struct TypeByIndex_<index, First, Rest...> |
57 | : public TypeByIndex_<index - 1, Rest...> {}; |
58 | template <size_t index> |
59 | struct TypeByIndex_<index> { |
60 | static_assert(index != index, "Index out-of-range." ); |
61 | }; |
62 | template <size_t index, typename... T> |
63 | using TypeByIndex = typename TypeByIndex_<index, T...>::Type; |
64 | // Chose a particular type out of a list of types, by index. |
65 | |
66 | template <size_t... s> |
67 | struct 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 | |
71 | template <size_t end, size_t... prefix> |
72 | struct MakeIndexes_: public MakeIndexes_<end - 1, end - 1, prefix...> {}; |
73 | template <size_t... prefix> |
74 | struct MakeIndexes_<0, prefix...> { |
75 | typedef Indexes<prefix...> Type; |
76 | }; |
77 | template <size_t end> |
78 | using MakeIndexes = typename MakeIndexes_<end>::Type; |
79 | // Equivalent to Indexes<0, 1, 2, ..., end>. |
80 | |
81 | template <typename... T> |
82 | class Tuple; |
83 | template <size_t index, typename... U> |
84 | inline TypeByIndex<index, U...>& getImpl(Tuple<U...>& tuple); |
85 | template <size_t index, typename... U> |
86 | inline TypeByIndex<index, U...>&& getImpl(Tuple<U...>&& tuple); |
87 | template <size_t index, typename... U> |
88 | inline const TypeByIndex<index, U...>& getImpl(const Tuple<U...>& tuple); |
89 | |
90 | template <uint index, typename T> |
91 | struct 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 | |
101 | template <uint index, typename T> |
102 | struct 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 | |
109 | template <uint index, typename... T> |
110 | struct TupleElement<index, Tuple<T...>> { |
111 | static_assert(sizeof(Tuple<T...>*) == 0, |
112 | "Tuples cannot contain other tuples -- they should be flattened." ); |
113 | }; |
114 | |
115 | template <typename Indexes, typename... Types> |
116 | struct TupleImpl; |
117 | |
118 | template <size_t... indexes, typename... Types> |
119 | struct 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 | |
148 | struct MakeTupleFunc; |
149 | struct MakeRefTupleFunc; |
150 | |
151 | template <typename... T> |
152 | class Tuple { |
153 | // The actual Tuple class (used for tuples of size other than 1). |
154 | |
155 | public: |
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 | |
165 | private: |
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 | |
181 | template <> |
182 | class Tuple<> { |
183 | // Simplified zero-member version of Tuple. In particular this is important to make sure that |
184 | // Tuple<>() is constexpr. |
185 | }; |
186 | |
187 | template <typename T> |
188 | class Tuple<T>; |
189 | // Single-element tuple should never be used. The public API should ensure this. |
190 | |
191 | template <size_t index, typename... T> |
192 | inline 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 | } |
197 | template <size_t index, typename... T> |
198 | inline 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 | } |
203 | template <size_t index, typename... T> |
204 | inline 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 | } |
209 | template <size_t index, typename T> |
210 | inline 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 | |
219 | template <typename Func, typename SoFar, typename... T> |
220 | struct 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 | |
225 | template <typename Func, typename First, typename... Rest, typename... T> |
226 | struct ExpandAndApplyResult_<Func, Tuple<T...>, First, Rest...> |
227 | : public ExpandAndApplyResult_<Func, Tuple<T..., First>, Rest...> {}; |
228 | template <typename Func, typename... FirstTypes, typename... Rest, typename... T> |
229 | struct ExpandAndApplyResult_<Func, Tuple<T...>, Tuple<FirstTypes...>, Rest...> |
230 | : public ExpandAndApplyResult_<Func, Tuple<T...>, FirstTypes&&..., Rest...> {}; |
231 | template <typename Func, typename... FirstTypes, typename... Rest, typename... T> |
232 | struct ExpandAndApplyResult_<Func, Tuple<T...>, Tuple<FirstTypes...>&, Rest...> |
233 | : public ExpandAndApplyResult_<Func, Tuple<T...>, FirstTypes&..., Rest...> {}; |
234 | template <typename Func, typename... FirstTypes, typename... Rest, typename... T> |
235 | struct ExpandAndApplyResult_<Func, Tuple<T...>, const Tuple<FirstTypes...>&, Rest...> |
236 | : public ExpandAndApplyResult_<Func, Tuple<T...>, const FirstTypes&..., Rest...> {}; |
237 | template <typename Func, typename... T> |
238 | struct ExpandAndApplyResult_<Func, Tuple<T...>> { |
239 | typedef decltype(instance<Func>()(instance<T&&>()...)) Type; |
240 | }; |
241 | template <typename Func, typename... T> |
242 | using ExpandAndApplyResult = typename ExpandAndApplyResult_<Func, Tuple<>, T...>::Type; |
243 | // Computes the expected return type of `expandAndApply()`. |
244 | |
245 | template <typename Func> |
246 | inline auto expandAndApply(Func&& func) -> ExpandAndApplyResult<Func> { |
247 | return func(); |
248 | } |
249 | |
250 | template <typename Func, typename First, typename... Rest> |
251 | struct 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 | |
263 | template <typename Func, typename First, typename... Rest> |
264 | inline 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 | |
272 | template <typename Func, typename... FirstTypes, typename... Rest> |
273 | inline 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 | |
279 | template <typename Func, typename... FirstTypes, typename... Rest> |
280 | inline 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 | |
286 | template <typename Func, typename... FirstTypes, typename... Rest> |
287 | inline 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 | |
293 | template <typename Func, typename... FirstTypes, typename... Rest, size_t... indexes> |
294 | inline 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 | |
301 | template <typename Func, typename... FirstTypes, typename... Rest, size_t... indexes> |
302 | inline 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 | |
309 | struct 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 | |
320 | struct 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 | |
333 | template <typename... T> struct Tuple_ { typedef _::Tuple<T...> Type; }; |
334 | template <typename T> struct Tuple_<T> { typedef T Type; }; |
335 | |
336 | template <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 | |
345 | template <typename... Params> |
346 | inline 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 | |
353 | template <typename... Params> |
354 | inline 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 | |
361 | template <size_t index, typename Tuple> |
362 | inline 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 | |
368 | template <typename Func, typename... Params> |
369 | inline 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 | |
375 | template <typename T> struct TupleSize_ { static constexpr size_t size = 1; }; |
376 | template <typename... T> struct TupleSize_<_::Tuple<T...>> { |
377 | static constexpr size_t size = sizeof...(T); |
378 | }; |
379 | |
380 | template <typename T> |
381 | constexpr size_t tupleSize() { return TupleSize_<T>::size; } |
382 | // Returns size of the tuple T. |
383 | |
384 | template <typename T, typename Tuple> |
385 | struct IndexOfType_; |
386 | template <typename T, typename Tuple> |
387 | struct HasType_ { |
388 | static constexpr bool value = false; |
389 | }; |
390 | |
391 | template <typename T> |
392 | struct IndexOfType_<T, T> { |
393 | static constexpr size_t value = 0; |
394 | }; |
395 | template <typename T> |
396 | struct HasType_<T, T> { |
397 | static constexpr bool value = true; |
398 | }; |
399 | |
400 | template <typename T, typename... U> |
401 | struct 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 | }; |
406 | template <typename T, typename... U> |
407 | struct HasType_<T, _::Tuple<T, U...>> { |
408 | static constexpr bool value = true; |
409 | }; |
410 | |
411 | template <typename T, typename U, typename... V> |
412 | struct IndexOfType_<T, _::Tuple<U, V...>> { |
413 | static constexpr size_t value = IndexOfType_<T, _::Tuple<V...>>::value + 1; |
414 | }; |
415 | template <typename T, typename U, typename... V> |
416 | struct HasType_<T, _::Tuple<U, V...>> { |
417 | static constexpr bool value = HasType_<T, _::Tuple<V...>>::value; |
418 | }; |
419 | |
420 | template <typename T, typename U> |
421 | inline constexpr size_t indexOfType() { |
422 | static_assert(HasType_<T, U>::value, "type not present" ); |
423 | return IndexOfType_<T, U>::value; |
424 | } |
425 | |
426 | template <size_t i, typename T> |
427 | struct TypeOfIndex_; |
428 | template <typename T> |
429 | struct TypeOfIndex_<0, T> { |
430 | typedef T Type; |
431 | }; |
432 | template <size_t i, typename T, typename... U> |
433 | struct TypeOfIndex_<i, _::Tuple<T, U...>> |
434 | : public TypeOfIndex_<i - 1, _::Tuple<U...>> {}; |
435 | template <typename T, typename... U> |
436 | struct TypeOfIndex_<0, _::Tuple<T, U...>> { |
437 | typedef T Type; |
438 | }; |
439 | |
440 | template <size_t i, typename Tuple> |
441 | using TypeOfIndex = typename TypeOfIndex_<i, Tuple>::Type; |
442 | |
443 | } // namespace kj |
444 | |