tuple.h (17817B)
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 than `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 #include "common.h" 41 42 KJ_BEGIN_HEADER 43 44 namespace kj { 45 namespace _ { // private 46 47 template <size_t index, typename... T> 48 struct TypeByIndex_; 49 template <typename First, typename... Rest> 50 struct TypeByIndex_<0, First, Rest...> { 51 typedef First Type; 52 }; 53 template <size_t index, typename First, typename... Rest> 54 struct TypeByIndex_<index, First, Rest...> 55 : public TypeByIndex_<index - 1, Rest...> {}; 56 template <size_t index> 57 struct TypeByIndex_<index> { 58 static_assert(index != index, "Index out-of-range."); 59 }; 60 template <size_t index, typename... T> 61 using TypeByIndex = typename TypeByIndex_<index, T...>::Type; 62 // Chose a particular type out of a list of types, by index. 63 64 template <size_t... s> 65 struct Indexes {}; 66 // Dummy helper type that just encapsulates a sequential list of indexes, so that we can match 67 // templates against them and unpack them with '...'. 68 69 template <size_t end, size_t... prefix> 70 struct MakeIndexes_: public MakeIndexes_<end - 1, end - 1, prefix...> {}; 71 template <size_t... prefix> 72 struct MakeIndexes_<0, prefix...> { 73 typedef Indexes<prefix...> Type; 74 }; 75 template <size_t end> 76 using MakeIndexes = typename MakeIndexes_<end>::Type; 77 // Equivalent to Indexes<0, 1, 2, ..., end>. 78 79 template <typename... T> 80 class Tuple; 81 template <size_t index, typename... U> 82 inline TypeByIndex<index, U...>& getImpl(Tuple<U...>& 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 const TypeByIndex<index, U...>& getImpl(const Tuple<U...>& tuple); 87 88 template <uint index, typename T> 89 struct TupleElement { 90 // Encapsulates one element of a tuple. The actual tuple implementation multiply-inherits 91 // from a TupleElement for each element, which is more efficient than a recursive definition. 92 93 T value; 94 TupleElement() = default; 95 constexpr inline TupleElement(const T& value): value(value) {} 96 constexpr inline TupleElement(T&& value): value(kj::mv(value)) {} 97 }; 98 99 template <uint index, typename T> 100 struct TupleElement<index, T&> { 101 // A tuple containing references can be constucted using refTuple(). 102 103 T& value; 104 constexpr inline TupleElement(T& value): value(value) {} 105 }; 106 107 template <uint index, typename... T> 108 struct TupleElement<index, Tuple<T...>> { 109 static_assert(sizeof(Tuple<T...>*) == 0, 110 "Tuples cannot contain other tuples -- they should be flattened."); 111 }; 112 113 template <typename Indexes, typename... Types> 114 struct TupleImpl; 115 116 template <size_t... indexes, typename... Types> 117 struct TupleImpl<Indexes<indexes...>, Types...> 118 : public TupleElement<indexes, Types>... { 119 // Implementation of Tuple. The only reason we need this rather than rolling this into class 120 // Tuple (below) is so that we can get "indexes" as an unpackable list. 121 122 static_assert(sizeof...(indexes) == sizeof...(Types), "Incorrect use of TupleImpl."); 123 124 TupleImpl() = default; 125 126 template <typename... Params> 127 inline TupleImpl(Params&&... params) 128 : TupleElement<indexes, Types>(kj::fwd<Params>(params))... { 129 // Work around Clang 3.2 bug 16303 where this is not detected. (Unfortunately, Clang sometimes 130 // segfaults instead.) 131 static_assert(sizeof...(params) == sizeof...(indexes), 132 "Wrong number of parameters to Tuple constructor."); 133 } 134 135 template <typename... U> 136 constexpr inline TupleImpl(Tuple<U...>&& other) 137 : TupleElement<indexes, Types>(kj::fwd<U>(getImpl<indexes>(other)))... {} 138 template <typename... U> 139 constexpr inline TupleImpl(Tuple<U...>& other) 140 : TupleElement<indexes, Types>(getImpl<indexes>(other))... {} 141 template <typename... U> 142 constexpr inline TupleImpl(const Tuple<U...>& other) 143 : TupleElement<indexes, Types>(getImpl<indexes>(other))... {} 144 }; 145 146 struct MakeTupleFunc; 147 struct MakeRefTupleFunc; 148 149 template <typename... T> 150 class Tuple { 151 // The actual Tuple class (used for tuples of size other than 1). 152 153 public: 154 Tuple() = default; 155 156 template <typename... U> 157 constexpr inline Tuple(Tuple<U...>&& other): impl(kj::mv(other)) {} 158 template <typename... U> 159 constexpr inline Tuple(Tuple<U...>& other): impl(other) {} 160 template <typename... U> 161 constexpr inline Tuple(const Tuple<U...>& other): impl(other) {} 162 163 private: 164 template <typename... Params> 165 constexpr Tuple(Params&&... params): impl(kj::fwd<Params>(params)...) {} 166 167 TupleImpl<MakeIndexes<sizeof...(T)>, T...> impl; 168 169 template <size_t index, typename... U> 170 friend inline TypeByIndex<index, U...>& getImpl(Tuple<U...>& tuple); 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 const TypeByIndex<index, U...>& getImpl(const Tuple<U...>& tuple); 175 friend struct MakeTupleFunc; 176 friend struct MakeRefTupleFunc; 177 }; 178 179 template <> 180 class Tuple<> { 181 // Simplified zero-member version of Tuple. In particular this is important to make sure that 182 // Tuple<>() is constexpr. 183 }; 184 185 template <typename T> 186 class Tuple<T>; 187 // Single-element tuple should never be used. The public API should ensure this. 188 189 template <size_t index, typename... T> 190 inline TypeByIndex<index, T...>& getImpl(Tuple<T...>& tuple) { 191 // Get member of a Tuple by index, e.g. `get<2>(myTuple)`. 192 static_assert(index < sizeof...(T), "Tuple element index out-of-bounds."); 193 return implicitCast<TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value; 194 } 195 template <size_t index, typename... T> 196 inline TypeByIndex<index, T...>&& getImpl(Tuple<T...>&& tuple) { 197 // Get member of a Tuple by index, e.g. `get<2>(myTuple)`. 198 static_assert(index < sizeof...(T), "Tuple element index out-of-bounds."); 199 return kj::mv(implicitCast<TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value); 200 } 201 template <size_t index, typename... T> 202 inline const TypeByIndex<index, T...>& getImpl(const Tuple<T...>& tuple) { 203 // Get member of a Tuple by index, e.g. `get<2>(myTuple)`. 204 static_assert(index < sizeof...(T), "Tuple element index out-of-bounds."); 205 return implicitCast<const TupleElement<index, TypeByIndex<index, T...>>&>(tuple.impl).value; 206 } 207 template <size_t index, typename T> 208 inline T&& getImpl(T&& value) { 209 // Get member of a Tuple by index, e.g. `getImpl<2>(myTuple)`. 210 211 // Non-tuples are equivalent to one-element tuples. 212 static_assert(index == 0, "Tuple element index out-of-bounds."); 213 return kj::fwd<T>(value); 214 } 215 216 217 template <typename Func, typename SoFar, typename... T> 218 struct ExpandAndApplyResult_; 219 // Template which computes the return type of applying Func to T... after flattening tuples. 220 // SoFar starts as Tuple<> and accumulates the flattened parameter types -- so after this template 221 // is recursively expanded, T... is empty and SoFar is a Tuple containing all the parameters. 222 223 template <typename Func, typename First, typename... Rest, typename... T> 224 struct ExpandAndApplyResult_<Func, Tuple<T...>, First, Rest...> 225 : public ExpandAndApplyResult_<Func, Tuple<T..., First>, Rest...> {}; 226 template <typename Func, typename... FirstTypes, typename... Rest, typename... T> 227 struct ExpandAndApplyResult_<Func, Tuple<T...>, Tuple<FirstTypes...>, Rest...> 228 : public ExpandAndApplyResult_<Func, Tuple<T...>, FirstTypes&&..., Rest...> {}; 229 template <typename Func, typename... FirstTypes, typename... Rest, typename... T> 230 struct ExpandAndApplyResult_<Func, Tuple<T...>, Tuple<FirstTypes...>&, Rest...> 231 : public ExpandAndApplyResult_<Func, Tuple<T...>, FirstTypes&..., Rest...> {}; 232 template <typename Func, typename... FirstTypes, typename... Rest, typename... T> 233 struct ExpandAndApplyResult_<Func, Tuple<T...>, const Tuple<FirstTypes...>&, Rest...> 234 : public ExpandAndApplyResult_<Func, Tuple<T...>, const FirstTypes&..., Rest...> {}; 235 template <typename Func, typename... T> 236 struct ExpandAndApplyResult_<Func, Tuple<T...>> { 237 typedef decltype(instance<Func>()(instance<T&&>()...)) Type; 238 }; 239 template <typename Func, typename... T> 240 using ExpandAndApplyResult = typename ExpandAndApplyResult_<Func, Tuple<>, T...>::Type; 241 // Computes the expected return type of `expandAndApply()`. 242 243 template <typename Func> 244 inline auto expandAndApply(Func&& func) -> ExpandAndApplyResult<Func> { 245 return func(); 246 } 247 248 template <typename Func, typename First, typename... Rest> 249 struct ExpandAndApplyFunc { 250 Func&& func; 251 First&& first; 252 ExpandAndApplyFunc(Func&& func, First&& first) 253 : func(kj::fwd<Func>(func)), first(kj::fwd<First>(first)) {} 254 template <typename... T> 255 auto operator()(T&&... params) 256 -> decltype(this->func(kj::fwd<First>(first), kj::fwd<T>(params)...)) { 257 return this->func(kj::fwd<First>(first), kj::fwd<T>(params)...); 258 } 259 }; 260 261 template <typename Func, typename First, typename... Rest> 262 inline auto expandAndApply(Func&& func, First&& first, Rest&&... rest) 263 -> ExpandAndApplyResult<Func, First, Rest...> { 264 265 return expandAndApply( 266 ExpandAndApplyFunc<Func, First, Rest...>(kj::fwd<Func>(func), kj::fwd<First>(first)), 267 kj::fwd<Rest>(rest)...); 268 } 269 270 template <typename Func, typename... FirstTypes, typename... Rest> 271 inline auto expandAndApply(Func&& func, Tuple<FirstTypes...>&& first, Rest&&... rest) 272 -> ExpandAndApplyResult<Func, FirstTypes&&..., Rest...> { 273 return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(), 274 kj::fwd<Func>(func), kj::mv(first), kj::fwd<Rest>(rest)...); 275 } 276 277 template <typename Func, typename... FirstTypes, typename... Rest> 278 inline auto expandAndApply(Func&& func, Tuple<FirstTypes...>& first, Rest&&... rest) 279 -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> { 280 return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(), 281 kj::fwd<Func>(func), first, kj::fwd<Rest>(rest)...); 282 } 283 284 template <typename Func, typename... FirstTypes, typename... Rest> 285 inline auto expandAndApply(Func&& func, const Tuple<FirstTypes...>& first, Rest&&... rest) 286 -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> { 287 return expandAndApplyWithIndexes(MakeIndexes<sizeof...(FirstTypes)>(), 288 kj::fwd<Func>(func), first, kj::fwd<Rest>(rest)...); 289 } 290 291 template <typename Func, typename... FirstTypes, typename... Rest, size_t... indexes> 292 inline auto expandAndApplyWithIndexes( 293 Indexes<indexes...>, Func&& func, Tuple<FirstTypes...>&& first, Rest&&... rest) 294 -> ExpandAndApplyResult<Func, FirstTypes&&..., Rest...> { 295 return expandAndApply(kj::fwd<Func>(func), kj::mv(getImpl<indexes>(first))..., 296 kj::fwd<Rest>(rest)...); 297 } 298 299 template <typename Func, typename... FirstTypes, typename... Rest, size_t... indexes> 300 inline auto expandAndApplyWithIndexes( 301 Indexes<indexes...>, Func&& func, const Tuple<FirstTypes...>& first, Rest&&... rest) 302 -> ExpandAndApplyResult<Func, FirstTypes..., Rest...> { 303 return expandAndApply(kj::fwd<Func>(func), getImpl<indexes>(first)..., 304 kj::fwd<Rest>(rest)...); 305 } 306 307 struct MakeTupleFunc { 308 template <typename... Params> 309 Tuple<Decay<Params>...> operator()(Params&&... params) { 310 return Tuple<Decay<Params>...>(kj::fwd<Params>(params)...); 311 } 312 template <typename Param> 313 Decay<Param> operator()(Param&& param) { 314 return kj::fwd<Param>(param); 315 } 316 }; 317 318 struct MakeRefTupleFunc { 319 template <typename... Params> 320 Tuple<Params...> operator()(Params&&... params) { 321 return Tuple<Params...>(kj::fwd<Params>(params)...); 322 } 323 template <typename Param> 324 Param operator()(Param&& param) { 325 return kj::fwd<Param>(param); 326 } 327 }; 328 329 } // namespace _ (private) 330 331 template <typename... T> struct Tuple_ { typedef _::Tuple<T...> Type; }; 332 template <typename T> struct Tuple_<T> { typedef T Type; }; 333 334 template <typename... T> using Tuple = typename Tuple_<T...>::Type; 335 // Tuple type. `Tuple<T>` (i.e. a single-element tuple) is a synonym for `T`. Tuples of size 336 // other than 1 expand to an internal type. Either way, you can construct a Tuple using 337 // `kj::tuple(...)`, get an element by index `i` using `kj::get<i>(myTuple)`, and expand the tuple 338 // as arguments to a function using `kj::apply(func, myTuple)`. 339 // 340 // Tuples are always flat -- that is, no element of a Tuple is ever itself a Tuple. If you 341 // construct a tuple from other tuples, the elements are flattened and concatenated. 342 343 template <typename... Params> 344 inline auto tuple(Params&&... params) 345 -> decltype(_::expandAndApply(_::MakeTupleFunc(), kj::fwd<Params>(params)...)) { 346 // Construct a new tuple from the given values. Any tuples in the argument list will be 347 // flattened into the result. 348 return _::expandAndApply(_::MakeTupleFunc(), kj::fwd<Params>(params)...); 349 } 350 351 template <typename... Params> 352 inline auto refTuple(Params&&... params) 353 -> decltype(_::expandAndApply(_::MakeRefTupleFunc(), kj::fwd<Params>(params)...)) { 354 // Like tuple(), but if the params include lvalue references, they will be captured as 355 // references. rvalue references will still be captured as whole values (moved). 356 return _::expandAndApply(_::MakeRefTupleFunc(), kj::fwd<Params>(params)...); 357 } 358 359 template <size_t index, typename Tuple> 360 inline auto get(Tuple&& tuple) -> decltype(_::getImpl<index>(kj::fwd<Tuple>(tuple))) { 361 // Unpack and return the tuple element at the given index. The index is specified as a template 362 // parameter, e.g. `kj::get<3>(myTuple)`. 363 return _::getImpl<index>(kj::fwd<Tuple>(tuple)); 364 } 365 366 template <typename Func, typename... Params> 367 inline auto apply(Func&& func, Params&&... params) 368 -> decltype(_::expandAndApply(kj::fwd<Func>(func), kj::fwd<Params>(params)...)) { 369 // Apply a function to some arguments, expanding tuples into separate arguments. 370 return _::expandAndApply(kj::fwd<Func>(func), kj::fwd<Params>(params)...); 371 } 372 373 template <typename T> struct TupleSize_ { static constexpr size_t size = 1; }; 374 template <typename... T> struct TupleSize_<_::Tuple<T...>> { 375 static constexpr size_t size = sizeof...(T); 376 }; 377 378 template <typename T> 379 constexpr size_t tupleSize() { return TupleSize_<T>::size; } 380 // Returns size of the tuple T. 381 382 template <typename T, typename Tuple> 383 struct IndexOfType_; 384 template <typename T, typename Tuple> 385 struct HasType_ { 386 static constexpr bool value = false; 387 }; 388 389 template <typename T> 390 struct IndexOfType_<T, T> { 391 static constexpr size_t value = 0; 392 }; 393 template <typename T> 394 struct HasType_<T, T> { 395 static constexpr bool value = true; 396 }; 397 398 template <typename T, typename... U> 399 struct IndexOfType_<T, _::Tuple<T, U...>> { 400 static constexpr size_t value = 0; 401 static_assert(!HasType_<T, _::Tuple<U...>>::value, 402 "requested type appears multiple times in tuple"); 403 }; 404 template <typename T, typename... U> 405 struct HasType_<T, _::Tuple<T, U...>> { 406 static constexpr bool value = true; 407 }; 408 409 template <typename T, typename U, typename... V> 410 struct IndexOfType_<T, _::Tuple<U, V...>> { 411 static constexpr size_t value = IndexOfType_<T, _::Tuple<V...>>::value + 1; 412 }; 413 template <typename T, typename U, typename... V> 414 struct HasType_<T, _::Tuple<U, V...>> { 415 static constexpr bool value = HasType_<T, _::Tuple<V...>>::value; 416 }; 417 418 template <typename T, typename U> 419 inline constexpr size_t indexOfType() { 420 static_assert(HasType_<T, U>::value, "type not present"); 421 return IndexOfType_<T, U>::value; 422 } 423 424 template <size_t i, typename T> 425 struct TypeOfIndex_; 426 template <typename T> 427 struct TypeOfIndex_<0, T> { 428 typedef T Type; 429 }; 430 template <size_t i, typename T, typename... U> 431 struct TypeOfIndex_<i, _::Tuple<T, U...>> 432 : public TypeOfIndex_<i - 1, _::Tuple<U...>> {}; 433 template <typename T, typename... U> 434 struct TypeOfIndex_<0, _::Tuple<T, U...>> { 435 typedef T Type; 436 }; 437 438 template <size_t i, typename Tuple> 439 using TypeOfIndex = typename TypeOfIndex_<i, Tuple>::Type; 440 441 } // namespace kj 442 443 KJ_END_HEADER