1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 /* A template class for tagged unions. */ 8 9 #include <new> 10 11 #include "mozilla/Alignment.h" 12 #include "mozilla/Assertions.h" 13 #include "mozilla/Move.h" 14 15 #ifndef mozilla_Variant_h 16 #define mozilla_Variant_h 17 18 namespace mozilla { 19 20 template<typename... Ts> 21 class Variant; 22 23 namespace detail { 24 25 // MaxSizeOf computes the maximum sizeof(T) for each T in Ts. 26 27 template<typename T, typename... Ts> 28 struct MaxSizeOf 29 { 30 static const size_t size = sizeof(T) > MaxSizeOf<Ts...>::size 31 ? sizeof(T) 32 : MaxSizeOf<Ts...>::size; 33 }; 34 35 template<typename T> 36 struct MaxSizeOf<T> 37 { 38 static const size_t size = sizeof(T); 39 }; 40 41 // The `IsVariant` helper is used in conjunction with static_assert and 42 // `mozilla::EnableIf` to catch passing non-variant types to `Variant::is<T>()` 43 // and friends at compile time, rather than at runtime. It ensures that the 44 // given type `Needle` is one of the types in the set of types `Haystack`. 45 46 template<typename Needle, typename... Haystack> 47 struct IsVariant; 48 49 template<typename Needle> 50 struct IsVariant<Needle> 51 { 52 static const bool value = false; 53 }; 54 55 template<typename Needle, typename... Haystack> 56 struct IsVariant<Needle, Needle, Haystack...> 57 { 58 static const bool value = true; 59 }; 60 61 template<typename Needle, typename T, typename... Haystack> 62 struct IsVariant<Needle, T, Haystack...> : public IsVariant<Needle, Haystack...> { }; 63 64 // TagHelper gets the given sentinel tag value for the given type T. This has to 65 // be split out from VariantImplementation because you can't nest a partial template 66 // specialization within a template class. 67 68 template<size_t N, typename T, typename U, typename Next, bool isMatch> 69 struct TagHelper; 70 71 // In the case where T != U, we continue recursion. 72 template<size_t N, typename T, typename U, typename Next> 73 struct TagHelper<N, T, U, Next, false> 74 { 75 static size_t tag() { return Next::template tag<U>(); } 76 }; 77 78 // In the case where T == U, return the tag number. 79 template<size_t N, typename T, typename U, typename Next> 80 struct TagHelper<N, T, U, Next, true> 81 { 82 static size_t tag() { return N; } 83 }; 84 85 // The VariantImplementation template provides the guts of mozilla::Variant. We create 86 // an VariantImplementation for each T in Ts... which handles construction, 87 // destruction, etc for when the Variant's type is T. If the Variant's type is 88 // not T, it punts the request on to the next VariantImplementation. 89 90 template<size_t N, typename... Ts> 91 struct VariantImplementation; 92 93 // The singly typed Variant / recursion base case. 94 template<size_t N, typename T> 95 struct VariantImplementation<N, T> { 96 template<typename U> 97 static size_t tag() { 98 static_assert(mozilla::IsSame<T, U>::value, 99 "mozilla::Variant: tag: bad type!"); 100 return N; 101 } 102 103 template<typename Variant> 104 static void copyConstruct(void* aLhs, const Variant& aRhs) { 105 new (aLhs) T(aRhs.template as<T>()); 106 } 107 108 template<typename Variant> 109 static void moveConstruct(void* aLhs, Variant&& aRhs) { 110 new (aLhs) T(aRhs.template extract<T>()); 111 } 112 113 template<typename Variant> 114 static void destroy(Variant& aV) { 115 aV.template as<T>().~T(); 116 } 117 118 template<typename Variant> 119 static bool 120 equal(const Variant& aLhs, const Variant& aRhs) { 121 return aLhs.template as<T>() == aRhs.template as<T>(); 122 } 123 124 template<typename Matcher, typename ConcreteVariant> 125 static typename Matcher::ReturnType 126 match(Matcher& aMatcher, ConcreteVariant& aV) { 127 return aMatcher.match(aV.template as<T>()); 128 } 129 }; 130 131 // VariantImplementation for some variant type T. 132 template<size_t N, typename T, typename... Ts> 133 struct VariantImplementation<N, T, Ts...> 134 { 135 // The next recursive VariantImplementation. 136 using Next = VariantImplementation<N + 1, Ts...>; 137 138 template<typename U> 139 static size_t tag() { 140 return TagHelper<N, T, U, Next, IsSame<T, U>::value>::tag(); 141 } 142 143 template<typename Variant> 144 static void copyConstruct(void* aLhs, const Variant& aRhs) { 145 if (aRhs.template is<T>()) { 146 new (aLhs) T(aRhs.template as<T>()); 147 } else { 148 Next::copyConstruct(aLhs, aRhs); 149 } 150 } 151 152 template<typename Variant> 153 static void moveConstruct(void* aLhs, Variant&& aRhs) { 154 if (aRhs.template is<T>()) { 155 new (aLhs) T(aRhs.template extract<T>()); 156 } else { 157 Next::moveConstruct(aLhs, aRhs); 158 } 159 } 160 161 template<typename Variant> 162 static void destroy(Variant& aV) { 163 if (aV.template is<T>()) { 164 aV.template as<T>().~T(); 165 } else { 166 Next::destroy(aV); 167 } 168 } 169 170 template<typename Variant> 171 static bool equal(const Variant& aLhs, const Variant& aRhs) { 172 if (aLhs.template is<T>()) { 173 MOZ_ASSERT(aRhs.template is<T>()); 174 return aLhs.template as<T>() == aRhs.template as<T>(); 175 } else { 176 return Next::equal(aLhs, aRhs); 177 } 178 } 179 180 template<typename Matcher, typename ConcreteVariant> 181 static typename Matcher::ReturnType 182 match(Matcher& aMatcher, ConcreteVariant& aV) 183 { 184 if (aV.template is<T>()) { 185 return aMatcher.match(aV.template as<T>()); 186 } else { 187 // If you're seeing compilation errors here like "no matching 188 // function for call to 'match'" then that means that the 189 // Matcher doesn't exhaust all variant types. There must exist a 190 // Matcher::match(T&) for every variant type T. 191 // 192 // If you're seeing compilation errors here like "cannot 193 // initialize return object of type <...> with an rvalue of type 194 // <...>" then that means that the Matcher::match(T&) overloads 195 // are returning different types. They must all return the same 196 // Matcher::ReturnType type. 197 return Next::match(aMatcher, aV); 198 } 199 } 200 }; 201 202 } // namespace detail 203 204 /** 205 * # mozilla::Variant 206 * 207 * A variant / tagged union / heterogenous disjoint union / sum-type template 208 * class. Similar in concept to (but not derived from) `boost::variant`. 209 * 210 * Sometimes, you may wish to use a C union with non-POD types. However, this is 211 * forbidden in C++ because it is not clear which type in the union should have 212 * its constructor and destructor run on creation and deletion 213 * respectively. This is the problem that `mozilla::Variant` solves. 214 * 215 * ## Usage 216 * 217 * A `mozilla::Variant` instance is constructed (via move or copy) from one of 218 * its variant types (ignoring const and references). It does *not* support 219 * construction from subclasses of variant types or types that coerce to one of 220 * the variant types. 221 * 222 * Variant<char, uint32_t> v1('a'); 223 * Variant<UniquePtr<A>, B, C> v2(MakeUnique<A>()); 224 * 225 * All access to the contained value goes through type-safe accessors. 226 * 227 * void 228 * Foo(Variant<A, B, C> v) 229 * { 230 * if (v.is<A>()) { 231 * A& ref = v.as<A>(); 232 * ... 233 * } else { 234 * ... 235 * } 236 * } 237 * 238 * Attempting to use the contained value as type `T1` when the `Variant` 239 * instance contains a value of type `T2` causes an assertion failure. 240 * 241 * A a; 242 * Variant<A, B, C> v(a); 243 * v.as<B>(); // <--- Assertion failure! 244 * 245 * Trying to use a `Variant<Ts...>` instance as some type `U` that is not a 246 * member of the set of `Ts...` is a compiler error. 247 * 248 * A a; 249 * Variant<A, B, C> v(a); 250 * v.as<SomeRandomType>(); // <--- Compiler error! 251 * 252 * Additionally, you can turn a `Variant` that `is<T>` into a `T` by moving it 253 * out of the containing `Variant` instance with the `extract<T>` method: 254 * 255 * Variant<UniquePtr<A>, B, C> v(MakeUnique<A>()); 256 * auto ptr = v.extract<UniquePtr<A>>(); 257 * 258 * Finally, you can exhaustively match on the contained variant and branch into 259 * different code paths depending which type is contained. This is preferred to 260 * manually checking every variant type T with is<T>() because it provides 261 * compile-time checking that you handled every type, rather than runtime 262 * assertion failures. 263 * 264 * // Bad! 265 * char* foo(Variant<A, B, C, D>& v) { 266 * if (v.is<A>()) { 267 * return ...; 268 * } else if (v.is<B>()) { 269 * return ...; 270 * } else { 271 * return doSomething(v.as<C>()); // Forgot about case D! 272 * } 273 * } 274 * 275 * // Good! 276 * struct FooMatcher 277 * { 278 * using ReturnType = char*; 279 * ReturnType match(A& a) { ... } 280 * ReturnType match(B& b) { ... } 281 * ReturnType match(C& c) { ... } 282 * ReturnType match(D& d) { ... } // Compile-time error to forget D! 283 * } 284 * char* foo(Variant<A, B, C, D>& v) { 285 * return v.match(FooMatcher()); 286 * } 287 * 288 * ## Examples 289 * 290 * A tree is either an empty leaf, or a node with a value and two children: 291 * 292 * struct Leaf { }; 293 * 294 * template<typename T> 295 * struct Node 296 * { 297 * T value; 298 * Tree<T>* left; 299 * Tree<T>* right; 300 * }; 301 * 302 * template<typename T> 303 * using Tree = Variant<Leaf, Node<T>>; 304 * 305 * A copy-on-write string is either a non-owning reference to some existing 306 * string, or an owning reference to our copy: 307 * 308 * class CopyOnWriteString 309 * { 310 * Variant<const char*, UniquePtr<char[]>> string; 311 * 312 * ... 313 * }; 314 */ 315 template<typename... Ts> 316 class Variant 317 { 318 using Impl = detail::VariantImplementation<0, Ts...>; 319 using RawData = AlignedStorage<detail::MaxSizeOf<Ts...>::size>; 320 321 // Each type is given a unique size_t sentinel. This tag lets us keep track of 322 // the contained variant value's type. 323 size_t tag; 324 325 // Raw storage for the contained variant value. 326 RawData raw; 327 328 void* ptr() { 329 return reinterpret_cast<void*>(&raw); 330 } 331 332 public: 333 /** Perfect forwarding construction for some variant type T. */ 334 template<typename RefT, 335 // RefT captures both const& as well as && (as intended, to support 336 // perfect forwarding), so we have to remove those qualifiers here 337 // when ensuring that T is a variant of this type, and getting T's 338 // tag, etc. 339 typename T = typename RemoveReference<typename RemoveConst<RefT>::Type>::Type, 340 typename = typename EnableIf<detail::IsVariant<T, Ts...>::value, void>::Type> 341 explicit Variant(RefT&& aT) 342 : tag(Impl::template tag<T>()) 343 { 344 new (ptr()) T(Forward<T>(aT)); 345 } 346 347 /** Copy construction. */ 348 Variant(const Variant& aRhs) 349 : tag(aRhs.tag) 350 { 351 Impl::copyConstruct(ptr(), aRhs); 352 } 353 354 /** Move construction. */ 355 Variant(Variant&& aRhs) 356 : tag(aRhs.tag) 357 { 358 Impl::moveConstruct(ptr(), Move(aRhs)); 359 } 360 361 /** Copy assignment. */ 362 Variant& operator=(const Variant& aRhs) { 363 MOZ_ASSERT(&aRhs != this, "self-assign disallowed"); 364 this->~Variant(); 365 new (this) Variant(aRhs); 366 return *this; 367 } 368 369 /** Move assignment. */ 370 Variant& operator=(Variant&& aRhs) { 371 MOZ_ASSERT(&aRhs != this, "self-assign disallowed"); 372 this->~Variant(); 373 new (this) Variant(Move(aRhs)); 374 return *this; 375 } 376 377 ~Variant() 378 { 379 Impl::destroy(*this); 380 } 381 382 /** Check which variant type is currently contained. */ 383 template<typename T> 384 bool is() const { 385 static_assert(detail::IsVariant<T, Ts...>::value, 386 "provided a type not found in this Variant's type list"); 387 return Impl::template tag<T>() == tag; 388 } 389 390 /** 391 * Operator == overload that defers to the variant type's operator== 392 * implementation if the rhs is tagged as the same type as this one. 393 */ 394 bool operator==(const Variant& aRhs) const { 395 return tag == aRhs.tag && Impl::equal(*this, aRhs); 396 } 397 398 /** 399 * Operator != overload that defers to the negation of the variant type's 400 * operator== implementation if the rhs is tagged as the same type as this 401 * one. 402 */ 403 bool operator!=(const Variant& aRhs) const { 404 return !(*this == aRhs); 405 } 406 407 // Accessors for working with the contained variant value. 408 409 /** Mutable reference. */ 410 template<typename T> 411 T& as() { 412 static_assert(detail::IsVariant<T, Ts...>::value, 413 "provided a type not found in this Variant's type list"); 414 MOZ_ASSERT(is<T>()); 415 return *reinterpret_cast<T*>(&raw); 416 } 417 418 /** Immutable const reference. */ 419 template<typename T> 420 const T& as() const { 421 static_assert(detail::IsVariant<T, Ts...>::value, 422 "provided a type not found in this Variant's type list"); 423 MOZ_ASSERT(is<T>()); 424 return *reinterpret_cast<const T*>(&raw); 425 } 426 427 /** 428 * Extract the contained variant value from this container into a temporary 429 * value. On completion, the value in the variant will be in a 430 * safely-destructible state, as determined by the behavior of T's move 431 * constructor when provided the variant's internal value. 432 */ 433 template<typename T> 434 T extract() { 435 static_assert(detail::IsVariant<T, Ts...>::value, 436 "provided a type not found in this Variant's type list"); 437 MOZ_ASSERT(is<T>()); 438 return T(Move(as<T>())); 439 } 440 441 // Exhaustive matching of all variant types no the contained value. 442 443 /** Match on an immutable const reference. */ 444 template<typename Matcher> 445 typename Matcher::ReturnType 446 match(Matcher& aMatcher) const { 447 return Impl::match(aMatcher, *this); 448 } 449 450 /** Match on a mutable non-const reference. */ 451 template<typename Matcher> 452 typename Matcher::ReturnType 453 match(Matcher& aMatcher) { 454 return Impl::match(aMatcher, *this); 455 } 456 }; 457 458 } // namespace mozilla 459 460 #endif /* mozilla_Variant_h */ 461