libstdc++-v3/include/std/variant

   1 // <variant> -*- C++ -*-
   2
   3 // Copyright (C) 2016-2019 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file variant
  26  *  This is the <variant> C++ Library header.
  27  */
  28
  29 #ifndef _GLIBCXX_VARIANT
  30 #define _GLIBCXX_VARIANT 1
  31
  32 #pragma GCC system_header
  33
  34 #if __cplusplus >= 201703L
  35
  36 #include <type_traits>
  37 #include <utility>
  38 #include <bits/enable_special_members.h>
  39 #include <bits/functexcept.h>
  40 #include <bits/move.h>
  41 #include <bits/functional_hash.h>
  42 #include <bits/invoke.h>
  43 #include <ext/aligned_buffer.h>
  44 #include <bits/parse_numbers.h>
  45 #include <bits/stl_iterator_base_types.h>
  46 #include <bits/stl_iterator_base_funcs.h>
  47 #include <bits/stl_construct.h>
  48
  49 namespace std _GLIBCXX_VISIBILITY(default)
  50 {
  51 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  52
  53 namespace __detail
  54 {
  55 namespace __variant
  56 {
  57   template<size_t _Np, typename... _Types>
  58     struct _Nth_type;
  59
  60   template<size_t _Np, typename _First, typename... _Rest>
  61     struct _Nth_type<_Np, _First, _Rest...>
  62     : _Nth_type<_Np-1, _Rest...> { };
  63
  64   template<typename _First, typename... _Rest>
  65     struct _Nth_type<0, _First, _Rest...>
  66     { using type = _First; };
  67
  68 } // namespace __variant
  69 } // namespace __detail
  70
  71 #define __cpp_lib_variant 201606L
  72
  73   template<typename... _Types> class tuple;
  74   template<typename... _Types> class variant;
  75   template <typename> struct hash;
  76
  77   template<typename _Variant>
  78     struct variant_size;
  79
  80   template<typename _Variant>
  81     struct variant_size<const _Variant> : variant_size<_Variant> {};
  82
  83   template<typename _Variant>
  84     struct variant_size<volatile _Variant> : variant_size<_Variant> {};
  85
  86   template<typename _Variant>
  87     struct variant_size<const volatile _Variant> : variant_size<_Variant> {};
  88
  89   template<typename... _Types>
  90     struct variant_size<variant<_Types...>>
  91     : std::integral_constant<size_t, sizeof...(_Types)> {};
  92
  93   template<typename _Variant>
  94     inline constexpr size_t variant_size_v = variant_size<_Variant>::value;
  95
  96   template<size_t _Np, typename _Variant>
  97     struct variant_alternative;
  98
  99   template<size_t _Np, typename _First, typename... _Rest>
 100     struct variant_alternative<_Np, variant<_First, _Rest...>>
 101     : variant_alternative<_Np-1, variant<_Rest...>> {};
 102
 103   template<typename _First, typename... _Rest>
 104     struct variant_alternative<0, variant<_First, _Rest...>>
 105     { using type = _First; };
 106
 107   template<size_t _Np, typename _Variant>
 108     using variant_alternative_t =
 109       typename variant_alternative<_Np, _Variant>::type;
 110
 111   template<size_t _Np, typename _Variant>
 112     struct variant_alternative<_Np, const _Variant>
 113     { using type = add_const_t<variant_alternative_t<_Np, _Variant>>; };
 114
 115   template<size_t _Np, typename _Variant>
 116     struct variant_alternative<_Np, volatile _Variant>
 117     { using type = add_volatile_t<variant_alternative_t<_Np, _Variant>>; };
 118
 119   template<size_t _Np, typename _Variant>
 120     struct variant_alternative<_Np, const volatile _Variant>
 121     { using type = add_cv_t<variant_alternative_t<_Np, _Variant>>; };
 122
 123   inline constexpr size_t variant_npos = -1;
 124
 125   template<size_t _Np, typename... _Types>
 126     constexpr variant_alternative_t<_Np, variant<_Types...>>&
 127     get(variant<_Types...>&);
 128
 129   template<size_t _Np, typename... _Types>
 130     constexpr variant_alternative_t<_Np, variant<_Types...>>&&
 131     get(variant<_Types...>&&);
 132
 133   template<size_t _Np, typename... _Types>
 134     constexpr variant_alternative_t<_Np, variant<_Types...>> const&
 135     get(const variant<_Types...>&);
 136
 137   template<size_t _Np, typename... _Types>
 138     constexpr variant_alternative_t<_Np, variant<_Types...>> const&&
 139     get(const variant<_Types...>&&);
 140
 141   template<typename _Result_type, typename _Visitor, typename... _Variants>
 142     constexpr decltype(auto)
 143     __do_visit(_Visitor&& __visitor, _Variants&&... __variants);
 144
 145   template <typename... _Types, typename _Tp>
 146     decltype(auto)
 147     __variant_cast(_Tp&& __rhs)
 148     {
 149       if constexpr (is_lvalue_reference_v<_Tp>)
 150         {
 151           if constexpr (is_const_v<remove_reference_t<_Tp>>)
 152             return static_cast<const variant<_Types...>&>(__rhs);
 153           else
 154             return static_cast<variant<_Types...>&>(__rhs);
 155         }
 156       else
 157         return static_cast<variant<_Types...>&&>(__rhs);
 158     }
 159
 160 namespace __detail
 161 {
 162 namespace __variant
 163 {
 164   // Returns the first apparence of _Tp in _Types.
 165   // Returns sizeof...(_Types) if _Tp is not in _Types.
 166   template<typename _Tp, typename... _Types>
 167     struct __index_of : std::integral_constant<size_t, 0> {};
 168
 169   template<typename _Tp, typename... _Types>
 170     inline constexpr size_t __index_of_v = __index_of<_Tp, _Types...>::value;
 171
 172   template<typename _Tp, typename _First, typename... _Rest>
 173     struct __index_of<_Tp, _First, _Rest...> :
 174       std::integral_constant<size_t, is_same_v<_Tp, _First>
 175         ? 0 : __index_of_v<_Tp, _Rest...> + 1> {};
 176
 177   // used for raw visitation
 178   struct __variant_cookie {};
 179   // used for raw visitation with indices passed in
 180   struct __variant_idx_cookie { using type = __variant_idx_cookie; };
 181   // Used to enable deduction (and same-type checking) for std::visit:
 182   template<typename> struct __deduce_visit_result { };
 183
 184   // Visit variants that might be valueless.
 185   template<typename _Visitor, typename... _Variants>
 186     constexpr void
 187     __raw_visit(_Visitor&& __visitor, _Variants&&... __variants)
 188     {
 189       std::__do_visit<__variant_cookie>(std::forward<_Visitor>(__visitor),
 190                                         std::forward<_Variants>(__variants)...);
 191     }
 192
 193   // Visit variants that might be valueless, passing indices to the visitor.
 194   template<typename _Visitor, typename... _Variants>
 195     constexpr void
 196     __raw_idx_visit(_Visitor&& __visitor, _Variants&&... __variants)
 197     {
 198       std::__do_visit<__variant_idx_cookie>(std::forward<_Visitor>(__visitor),
 199           std::forward<_Variants>(__variants)...);
 200     }
 201
 202   // _Uninitialized<T> is guaranteed to be a literal type, even if T is not.
 203   // We have to do this, because [basic.types]p10.5.3 (n4606) is not implemented
 204   // yet. When it's implemented, _Uninitialized<T> can be changed to the alias
 205   // to T, therefore equivalent to being removed entirely.
 206   //
 207   // Another reason we may not want to remove _Uninitialzied<T> may be that, we
 208   // want _Uninitialized<T> to be trivially destructible, no matter whether T
 209   // is; but we will see.
 210   template<typename _Type, bool = std::is_literal_type_v<_Type>>
 211     struct _Uninitialized;
 212
 213   template<typename _Type>
 214     struct _Uninitialized<_Type, true>
 215     {
 216       template<typename... _Args>
 217         constexpr
 218         _Uninitialized(in_place_index_t<0>, _Args&&... __args)
 219         : _M_storage(std::forward<_Args>(__args)...)
 220         { }
 221
 222       constexpr const _Type& _M_get() const & noexcept
 223       { return _M_storage; }
 224
 225       constexpr _Type& _M_get() & noexcept
 226       { return _M_storage; }
 227
 228       constexpr const _Type&& _M_get() const && noexcept
 229       { return std::move(_M_storage); }
 230
 231       constexpr _Type&& _M_get() && noexcept
 232       { return std::move(_M_storage); }
 233
 234       _Type _M_storage;
 235     };
 236
 237   template<typename _Type>
 238     struct _Uninitialized<_Type, false>
 239     {
 240       template<typename... _Args>
 241         constexpr
 242         _Uninitialized(in_place_index_t<0>, _Args&&... __args)
 243         {
 244           ::new ((void*)std::addressof(_M_storage))
 245             _Type(std::forward<_Args>(__args)...);
 246         }
 247
 248       const _Type& _M_get() const & noexcept
 249       { return *_M_storage._M_ptr(); }
 250
 251       _Type& _M_get() & noexcept
 252       { return *_M_storage._M_ptr(); }
 253
 254       const _Type&& _M_get() const && noexcept
 255       { return std::move(*_M_storage._M_ptr()); }
 256
 257       _Type&& _M_get() && noexcept
 258       { return std::move(*_M_storage._M_ptr()); }
 259
 260       __gnu_cxx::__aligned_membuf<_Type> _M_storage;
 261     };
 262
 263   template<typename _Union>
 264     constexpr decltype(auto)
 265     __get(in_place_index_t<0>, _Union&& __u) noexcept
 266     { return std::forward<_Union>(__u)._M_first._M_get(); }
 267
 268   template<size_t _Np, typename _Union>
 269     constexpr decltype(auto)
 270     __get(in_place_index_t<_Np>, _Union&& __u) noexcept
 271     {
 272       return __variant::__get(in_place_index<_Np-1>,
 273                               std::forward<_Union>(__u)._M_rest);
 274     }
 275
 276   // Returns the typed storage for __v.
 277   template<size_t _Np, typename _Variant>
 278     constexpr decltype(auto)
 279     __get(_Variant&& __v) noexcept
 280     {
 281       return __variant::__get(std::in_place_index<_Np>,
 282                               std::forward<_Variant>(__v)._M_u);
 283     }
 284
 285   template<typename... _Types>
 286     struct _Traits
 287     {
 288       static constexpr bool _S_default_ctor =
 289           is_default_constructible_v<typename _Nth_type<0, _Types...>::type>;
 290       static constexpr bool _S_copy_ctor =
 291           (is_copy_constructible_v<_Types> && ...);
 292       static constexpr bool _S_move_ctor =
 293           (is_move_constructible_v<_Types> && ...);
 294       static constexpr bool _S_copy_assign =
 295           _S_copy_ctor
 296           && (is_copy_assignable_v<_Types> && ...);
 297       static constexpr bool _S_move_assign =
 298           _S_move_ctor
 299           && (is_move_assignable_v<_Types> && ...);
 300
 301       static constexpr bool _S_trivial_dtor =
 302           (is_trivially_destructible_v<_Types> && ...);
 303       static constexpr bool _S_trivial_copy_ctor =
 304           (is_trivially_copy_constructible_v<_Types> && ...);
 305       static constexpr bool _S_trivial_move_ctor =
 306           (is_trivially_move_constructible_v<_Types> && ...);
 307       static constexpr bool _S_trivial_copy_assign =
 308           _S_trivial_dtor && _S_trivial_copy_ctor
 309           && (is_trivially_copy_assignable_v<_Types> && ...);
 310       static constexpr bool _S_trivial_move_assign =
 311           _S_trivial_dtor && _S_trivial_move_ctor
 312           && (is_trivially_move_assignable_v<_Types> && ...);
 313
 314       // The following nothrow traits are for non-trivial SMFs. Trivial SMFs
 315       // are always nothrow.
 316       static constexpr bool _S_nothrow_default_ctor =
 317           is_nothrow_default_constructible_v<
 318               typename _Nth_type<0, _Types...>::type>;
 319       static constexpr bool _S_nothrow_copy_ctor = false;
 320       static constexpr bool _S_nothrow_move_ctor =
 321           (is_nothrow_move_constructible_v<_Types> && ...);
 322       static constexpr bool _S_nothrow_copy_assign = false;
 323       static constexpr bool _S_nothrow_move_assign =
 324           _S_nothrow_move_ctor
 325           && (is_nothrow_move_assignable_v<_Types> && ...);
 326     };
 327
 328   // Defines members and ctors.
 329   template<typename... _Types>
 330     union _Variadic_union { };
 331
 332   template<typename _First, typename... _Rest>
 333     union _Variadic_union<_First, _Rest...>
 334     {
 335       constexpr _Variadic_union() : _M_rest() { }
 336
 337       template<typename... _Args>
 338         constexpr _Variadic_union(in_place_index_t<0>, _Args&&... __args)
 339         : _M_first(in_place_index<0>, std::forward<_Args>(__args)...)
 340         { }
 341
 342       template<size_t _Np, typename... _Args>
 343         constexpr _Variadic_union(in_place_index_t<_Np>, _Args&&... __args)
 344         : _M_rest(in_place_index<_Np-1>, std::forward<_Args>(__args)...)
 345         { }
 346
 347       _Uninitialized<_First> _M_first;
 348       _Variadic_union<_Rest...> _M_rest;
 349     };
 350
 351   // _Never_valueless_alt is true for variant alternatives that can
 352   // always be placed in a variant without it becoming valueless.
 353
 354   // For suitably-small, trivially copyable types we can create temporaries
 355   // on the stack and then memcpy them into place.
 356   template<typename _Tp>
 357     struct _Never_valueless_alt
 358     : __and_<bool_constant<sizeof(_Tp) <= 256>, is_trivially_copyable<_Tp>>
 359     { };
 360
 361   // Specialize _Never_valueless_alt for other types which have a
 362   // non-throwing and cheap move construction and move assignment operator,
 363   // so that emplacing the type will provide the strong exception-safety
 364   // guarantee, by creating and moving a temporary.
 365   // Whether _Never_valueless_alt<T> is true or not affects the ABI of a
 366   // variant using that alternative, so we can't change the value later!
 367
 368   // True if every alternative in _Types... can be emplaced in a variant
 369   // without it becoming valueless. If this is true, variant<_Types...>
 370   // can never be valueless, which enables some minor optimizations.
 371   template <typename... _Types>
 372     constexpr bool __never_valueless()
 373     {
 374       return _Traits<_Types...>::_S_move_assign
 375         && (_Never_valueless_alt<_Types>::value && ...);
 376     }
 377
 378   // Defines index and the dtor, possibly trivial.
 379   template<bool __trivially_destructible, typename... _Types>
 380     struct _Variant_storage;
 381
 382   template <typename... _Types>
 383     using __select_index =
 384       typename __select_int::_Select_int_base<sizeof...(_Types),
 385                                               unsigned char,
 386                                               unsigned short>::type::value_type;
 387
 388   template<typename... _Types>
 389     struct _Variant_storage<false, _Types...>
 390     {
 391       constexpr _Variant_storage() : _M_index(variant_npos) { }
 392
 393       template<size_t _Np, typename... _Args>
 394         constexpr _Variant_storage(in_place_index_t<_Np>, _Args&&... __args)
 395         : _M_u(in_place_index<_Np>, std::forward<_Args>(__args)...),
 396         _M_index(_Np)
 397         { }
 398
 399       constexpr void _M_reset_impl()
 400       {
 401         __variant::__raw_visit([](auto&& __this_mem) mutable
 402           {
 403             if constexpr (!is_same_v<remove_reference_t<decltype(__this_mem)>,
 404                           __variant_cookie>)
 405               std::_Destroy(std::__addressof(__this_mem));
 406           }, __variant_cast<_Types...>(*this));
 407       }
 408
 409       void _M_reset()
 410       {
 411         _M_reset_impl();
 412         _M_index = variant_npos;
 413       }
 414
 415       ~_Variant_storage()
 416       { _M_reset(); }
 417
 418       void*
 419       _M_storage() const noexcept
 420       {
 421         return const_cast<void*>(static_cast<const void*>(
 422             std::addressof(_M_u)));
 423       }
 424
 425       constexpr bool
 426       _M_valid() const noexcept
 427       {
 428         if constexpr (__never_valueless<_Types...>())
 429           return true;
 430         return this->_M_index != __index_type(variant_npos);
 431       }
 432
 433       _Variadic_union<_Types...> _M_u;
 434       using __index_type = __select_index<_Types...>;
 435       __index_type _M_index;
 436     };
 437
 438   template<typename... _Types>
 439     struct _Variant_storage<true, _Types...>
 440     {
 441       constexpr _Variant_storage() : _M_index(variant_npos) { }
 442
 443       template<size_t _Np, typename... _Args>
 444         constexpr _Variant_storage(in_place_index_t<_Np>, _Args&&... __args)
 445         : _M_u(in_place_index<_Np>, std::forward<_Args>(__args)...),
 446         _M_index(_Np)
 447         { }
 448
 449       void _M_reset() noexcept
 450       { _M_index = variant_npos; }
 451
 452       void*
 453       _M_storage() const noexcept
 454       {
 455         return const_cast<void*>(static_cast<const void*>(
 456             std::addressof(_M_u)));
 457       }
 458
 459       constexpr bool
 460       _M_valid() const noexcept
 461       {
 462         if constexpr (__never_valueless<_Types...>())
 463           return true;
 464         return this->_M_index != __index_type(variant_npos);
 465       }
 466
 467       _Variadic_union<_Types...> _M_u;
 468       using __index_type = __select_index<_Types...>;
 469       __index_type _M_index;
 470     };
 471
 472   template<typename... _Types>
 473     using _Variant_storage_alias =
 474         _Variant_storage<_Traits<_Types...>::_S_trivial_dtor, _Types...>;
 475
 476   template<typename _Tp, typename _Up>
 477     void __variant_construct_single(_Tp&& __lhs, _Up&& __rhs_mem)
 478     {
 479       void* __storage = std::addressof(__lhs._M_u);
 480       using _Type = remove_reference_t<decltype(__rhs_mem)>;
 481       if constexpr (!is_same_v<_Type, __variant_cookie>)
 482         ::new (__storage)
 483           _Type(std::forward<decltype(__rhs_mem)>(__rhs_mem));
 484     }
 485
 486   template<typename... _Types, typename _Tp, typename _Up>
 487     void __variant_construct(_Tp&& __lhs, _Up&& __rhs)
 488     {
 489       __lhs._M_index = __rhs._M_index;
 490       __variant::__raw_visit([&__lhs](auto&& __rhs_mem) mutable
 491         {
 492           __variant_construct_single(std::forward<_Tp>(__lhs),
 493               std::forward<decltype(__rhs_mem)>(__rhs_mem));
 494         }, __variant_cast<_Types...>(std::forward<_Up>(__rhs)));
 495     }
 496
 497   // The following are (Copy|Move) (ctor|assign) layers for forwarding
 498   // triviality and handling non-trivial SMF behaviors.
 499
 500   template<bool, typename... _Types>
 501     struct _Copy_ctor_base : _Variant_storage_alias<_Types...>
 502     {
 503       using _Base = _Variant_storage_alias<_Types...>;
 504       using _Base::_Base;
 505
 506       _Copy_ctor_base(const _Copy_ctor_base& __rhs)
 507           noexcept(_Traits<_Types...>::_S_nothrow_copy_ctor)
 508       {
 509         __variant_construct<_Types...>(*this, __rhs);
 510       }
 511
 512       _Copy_ctor_base(_Copy_ctor_base&&) = default;
 513       _Copy_ctor_base& operator=(const _Copy_ctor_base&) = default;
 514       _Copy_ctor_base& operator=(_Copy_ctor_base&&) = default;
 515     };
 516
 517   template<typename... _Types>
 518     struct _Copy_ctor_base<true, _Types...> : _Variant_storage_alias<_Types...>
 519     {
 520       using _Base = _Variant_storage_alias<_Types...>;
 521       using _Base::_Base;
 522     };
 523
 524   template<typename... _Types>
 525     using _Copy_ctor_alias =
 526         _Copy_ctor_base<_Traits<_Types...>::_S_trivial_copy_ctor, _Types...>;
 527
 528   template<bool, typename... _Types>
 529     struct _Move_ctor_base : _Copy_ctor_alias<_Types...>
 530     {
 531       using _Base = _Copy_ctor_alias<_Types...>;
 532       using _Base::_Base;
 533
 534       _Move_ctor_base(_Move_ctor_base&& __rhs)
 535           noexcept(_Traits<_Types...>::_S_nothrow_move_ctor)
 536       {
 537         __variant_construct<_Types...>(*this, std::move(__rhs));
 538       }
 539
 540       template<typename _Up>
 541         void _M_destructive_move(unsigned short __rhs_index, _Up&& __rhs)
 542         {
 543           this->_M_reset();
 544           __variant_construct_single(*this, std::forward<_Up>(__rhs));
 545           this->_M_index = __rhs_index;
 546         }
 547
 548       template<typename _Up>
 549         void _M_destructive_copy(unsigned short __rhs_index, const _Up& __rhs)
 550         {
 551           this->_M_reset();
 552           __variant_construct_single(*this, __rhs);
 553           this->_M_index = __rhs_index;
 554         }
 555
 556       _Move_ctor_base(const _Move_ctor_base&) = default;
 557       _Move_ctor_base& operator=(const _Move_ctor_base&) = default;
 558       _Move_ctor_base& operator=(_Move_ctor_base&&) = default;
 559     };
 560
 561   template<typename... _Types>
 562     struct _Move_ctor_base<true, _Types...> : _Copy_ctor_alias<_Types...>
 563     {
 564       using _Base = _Copy_ctor_alias<_Types...>;
 565       using _Base::_Base;
 566
 567       template<typename _Up>
 568         void _M_destructive_move(unsigned short __rhs_index, _Up&& __rhs)
 569         {
 570           this->_M_reset();
 571           __variant_construct_single(*this, std::forward<_Up>(__rhs));
 572           this->_M_index = __rhs_index;
 573         }
 574
 575       template<typename _Up>
 576         void _M_destructive_copy(unsigned short __rhs_index, const _Up& __rhs)
 577         {
 578           this->_M_reset();
 579           __variant_construct_single(*this, __rhs);
 580           this->_M_index = __rhs_index;
 581         }
 582     };
 583
 584   template<typename... _Types>
 585     using _Move_ctor_alias =
 586         _Move_ctor_base<_Traits<_Types...>::_S_trivial_move_ctor, _Types...>;
 587
 588   template<bool, typename... _Types>
 589     struct _Copy_assign_base : _Move_ctor_alias<_Types...>
 590     {
 591       using _Base = _Move_ctor_alias<_Types...>;
 592       using _Base::_Base;
 593
 594       _Copy_assign_base&
 595       operator=(const _Copy_assign_base& __rhs)
 596           noexcept(_Traits<_Types...>::_S_nothrow_copy_assign)
 597       {
 598         __variant::__raw_idx_visit(
 599           [this](auto&& __rhs_mem, auto __rhs_index) mutable
 600           {
 601             if constexpr (__rhs_index != variant_npos)
 602               {
 603                 if (this->_M_index == __rhs_index)
 604                   __variant::__get<__rhs_index>(*this) = __rhs_mem;
 605                 else
 606                   {
 607                     using __rhs_type = __remove_cvref_t<decltype(__rhs_mem)>;
 608                     if constexpr (is_nothrow_copy_constructible_v<__rhs_type>
 609                         || !is_nothrow_move_constructible_v<__rhs_type>)
 610                       // The standard says this->emplace<__rhs_type>(__rhs_mem)
 611                       // should be used here, but _M_destructive_copy is
 612                       // equivalent in this case. Either copy construction
 613                       // doesn't throw, so _M_destructive_copy gives strong
 614                       // exception safety guarantee, or both copy construction
 615                       // and move construction can throw, so emplace only gives
 616                       // basic exception safety anyway.
 617                       this->_M_destructive_copy(__rhs_index, __rhs_mem);
 618                     else
 619                       __variant_cast<_Types...>(*this)
 620                         = variant<_Types...>(__rhs_mem);
 621                   }
 622               }
 623             else
 624               this->_M_reset();
 625           }, __variant_cast<_Types...>(__rhs));
 626         return *this;
 627       }
 628
 629       _Copy_assign_base(const _Copy_assign_base&) = default;
 630       _Copy_assign_base(_Copy_assign_base&&) = default;
 631       _Copy_assign_base& operator=(_Copy_assign_base&&) = default;
 632     };
 633
 634   template<typename... _Types>
 635     struct _Copy_assign_base<true, _Types...> : _Move_ctor_alias<_Types...>
 636     {
 637       using _Base = _Move_ctor_alias<_Types...>;
 638       using _Base::_Base;
 639     };
 640
 641   template<typename... _Types>
 642     using _Copy_assign_alias =
 643       _Copy_assign_base<_Traits<_Types...>::_S_trivial_copy_assign, _Types...>;
 644
 645   template<bool, typename... _Types>
 646     struct _Move_assign_base : _Copy_assign_alias<_Types...>
 647     {
 648       using _Base = _Copy_assign_alias<_Types...>;
 649       using _Base::_Base;
 650
 651       _Move_assign_base&
 652       operator=(_Move_assign_base&& __rhs)
 653           noexcept(_Traits<_Types...>::_S_nothrow_move_assign)
 654       {
 655         __variant::__raw_idx_visit(
 656           [this](auto&& __rhs_mem, auto __rhs_index) mutable
 657           {
 658             if constexpr (__rhs_index != variant_npos)
 659               {
 660                 if (this->_M_index == __rhs_index)
 661                   __variant::__get<__rhs_index>(*this) = std::move(__rhs_mem);
 662                 else
 663                   __variant_cast<_Types...>(*this)
 664                     .template emplace<__rhs_index>(std::move(__rhs_mem));
 665               }
 666             else
 667               this->_M_reset();
 668           }, __variant_cast<_Types...>(__rhs));
 669         return *this;
 670       }
 671
 672       _Move_assign_base(const _Move_assign_base&) = default;
 673       _Move_assign_base(_Move_assign_base&&) = default;
 674       _Move_assign_base& operator=(const _Move_assign_base&) = default;
 675     };
 676
 677   template<typename... _Types>
 678     struct _Move_assign_base<true, _Types...> : _Copy_assign_alias<_Types...>
 679     {
 680       using _Base = _Copy_assign_alias<_Types...>;
 681       using _Base::_Base;
 682     };
 683
 684   template<typename... _Types>
 685     using _Move_assign_alias =
 686       _Move_assign_base<_Traits<_Types...>::_S_trivial_move_assign, _Types...>;
 687
 688   template<typename... _Types>
 689     struct _Variant_base : _Move_assign_alias<_Types...>
 690     {
 691       using _Base = _Move_assign_alias<_Types...>;
 692
 693       constexpr
 694       _Variant_base()
 695           noexcept(_Traits<_Types...>::_S_nothrow_default_ctor)
 696       : _Variant_base(in_place_index<0>) { }
 697
 698       template<size_t _Np, typename... _Args>
 699         constexpr explicit
 700         _Variant_base(in_place_index_t<_Np> __i, _Args&&... __args)
 701         : _Base(__i, std::forward<_Args>(__args)...)
 702         { }
 703
 704       _Variant_base(const _Variant_base&) = default;
 705       _Variant_base(_Variant_base&&) = default;
 706       _Variant_base& operator=(const _Variant_base&) = default;
 707       _Variant_base& operator=(_Variant_base&&) = default;
 708     };
 709
 710   // For how many times does _Tp appear in _Tuple?
 711   template<typename _Tp, typename _Tuple>
 712     struct __tuple_count;
 713
 714   template<typename _Tp, typename _Tuple>
 715     inline constexpr size_t __tuple_count_v =
 716       __tuple_count<_Tp, _Tuple>::value;
 717
 718   template<typename _Tp, typename... _Types>
 719     struct __tuple_count<_Tp, tuple<_Types...>>
 720     : integral_constant<size_t, 0> { };
 721
 722   template<typename _Tp, typename _First, typename... _Rest>
 723     struct __tuple_count<_Tp, tuple<_First, _Rest...>>
 724     : integral_constant<
 725         size_t,
 726         __tuple_count_v<_Tp, tuple<_Rest...>> + is_same_v<_Tp, _First>> { };
 727
 728   // TODO: Reuse this in <tuple> ?
 729   template<typename _Tp, typename... _Types>
 730     inline constexpr bool __exactly_once =
 731       __tuple_count_v<_Tp, tuple<_Types...>> == 1;
 732
 733   // Takes _Types and create an overloaded _S_fun for each type.
 734   // If a type appears more than once in _Types, create only one overload.
 735   template<typename... _Types>
 736     struct __overload_set
 737     { static void _S_fun(); };
 738
 739   template<typename _First, typename... _Rest>
 740     struct __overload_set<_First, _Rest...> : __overload_set<_Rest...>
 741     {
 742       using __overload_set<_Rest...>::_S_fun;
 743       static integral_constant<size_t, sizeof...(_Rest)> _S_fun(_First);
 744     };
 745
 746   template<typename... _Rest>
 747     struct __overload_set<void, _Rest...> : __overload_set<_Rest...>
 748     {
 749       using __overload_set<_Rest...>::_S_fun;
 750     };
 751
 752   // Helper for variant(_Tp&&) and variant::operator=(_Tp&&).
 753   // __accepted_index maps an arbitrary _Tp to an alternative type in _Variant
 754   // (or to variant_npos).
 755   template<typename _Tp, typename _Variant, typename = void>
 756     struct __accepted_index
 757     { static constexpr size_t value = variant_npos; };
 758
 759   template<typename _Tp, typename... _Types>
 760     struct __accepted_index<
 761       _Tp, variant<_Types...>,
 762       void_t<decltype(__overload_set<_Types...>::_S_fun(std::declval<_Tp>()))>>
 763     {
 764       static constexpr size_t value = sizeof...(_Types) - 1
 765         - decltype(__overload_set<_Types...>::
 766                    _S_fun(std::declval<_Tp>()))::value;
 767     };
 768
 769   // Returns the raw storage for __v.
 770   template<typename _Variant>
 771     void* __get_storage(_Variant&& __v) noexcept
 772     { return __v._M_storage(); }
 773
 774   template <typename _Maybe_variant_cookie, typename _Variant>
 775     struct _Extra_visit_slot_needed
 776     {
 777       template <typename> struct _Variant_never_valueless;
 778
 779       template <typename... _Types>
 780         struct _Variant_never_valueless<variant<_Types...>>
 781         : bool_constant<__never_valueless<_Types...>()> {};
 782
 783       static constexpr bool value =
 784         (is_same_v<_Maybe_variant_cookie, __variant_cookie>
 785          || is_same_v<_Maybe_variant_cookie, __variant_idx_cookie>)
 786         && !_Variant_never_valueless<__remove_cvref_t<_Variant>>::value;
 787     };
 788
 789   // Used for storing a multi-dimensional vtable.
 790   template<typename _Tp, size_t... _Dimensions>
 791     struct _Multi_array;
 792
 793   // Partial specialization with rank zero, stores a single _Tp element.
 794   template<typename _Tp>
 795     struct _Multi_array<_Tp>
 796     {
 797       template<typename>
 798         struct __untag_result
 799         : false_type
 800         { using element_type = _Tp; };
 801
 802       template <typename... _Args>
 803         struct __untag_result<const void(*)(_Args...)>
 804         : false_type
 805         { using element_type = void(*)(_Args...); };
 806
 807       template <typename... _Args>
 808         struct __untag_result<__variant_cookie(*)(_Args...)>
 809         : false_type
 810         { using element_type = void(*)(_Args...); };
 811
 812       template <typename... _Args>
 813         struct __untag_result<__variant_idx_cookie(*)(_Args...)>
 814         : false_type
 815         { using element_type = void(*)(_Args...); };
 816
 817       template <typename _Res, typename... _Args>
 818         struct __untag_result<__deduce_visit_result<_Res>(*)(_Args...)>
 819         : true_type
 820         { using element_type = _Res(*)(_Args...); };
 821
 822       using __result_is_deduced = __untag_result<_Tp>;
 823
 824       constexpr const typename __untag_result<_Tp>::element_type&
 825       _M_access() const
 826       { return _M_data; }
 827
 828       typename __untag_result<_Tp>::element_type _M_data;
 829     };
 830
 831   // Partial specialization with rank >= 1.
 832   template<typename _Ret,
 833            typename _Visitor,
 834            typename... _Variants,
 835            size_t __first, size_t... __rest>
 836     struct _Multi_array<_Ret(*)(_Visitor, _Variants...), __first, __rest...>
 837     {
 838       static constexpr size_t __index =
 839         sizeof...(_Variants) - sizeof...(__rest) - 1;
 840
 841       using _Variant = typename _Nth_type<__index, _Variants...>::type;
 842
 843       static constexpr int __do_cookie =
 844         _Extra_visit_slot_needed<_Ret, _Variant>::value ? 1 : 0;
 845
 846       using _Tp = _Ret(*)(_Visitor, _Variants...);
 847
 848       template<typename... _Args>
 849         constexpr decltype(auto)
 850         _M_access(size_t __first_index, _Args... __rest_indices) const
 851         {
 852           return _M_arr[__first_index + __do_cookie]
 853             ._M_access(__rest_indices...);
 854         }
 855
 856       _Multi_array<_Tp, __rest...> _M_arr[__first + __do_cookie];
 857     };
 858
 859   // Creates a multi-dimensional vtable recursively.
 860   //
 861   // For example,
 862   // visit([](auto, auto){},
 863   //       variant<int, char>(),  // typedef'ed as V1
 864   //       variant<float, double, long double>())  // typedef'ed as V2
 865   // will trigger instantiations of:
 866   // __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&), 2, 3>,
 867   //                   tuple<V1&&, V2&&>, std::index_sequence<>>
 868   //   __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&), 3>,
 869   //                     tuple<V1&&, V2&&>, std::index_sequence<0>>
 870   //     __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&)>,
 871   //                       tuple<V1&&, V2&&>, std::index_sequence<0, 0>>
 872   //     __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&)>,
 873   //                       tuple<V1&&, V2&&>, std::index_sequence<0, 1>>
 874   //     __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&)>,
 875   //                       tuple<V1&&, V2&&>, std::index_sequence<0, 2>>
 876   //   __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&), 3>,
 877   //                     tuple<V1&&, V2&&>, std::index_sequence<1>>
 878   //     __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&)>,
 879   //                       tuple<V1&&, V2&&>, std::index_sequence<1, 0>>
 880   //     __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&)>,
 881   //                       tuple<V1&&, V2&&>, std::index_sequence<1, 1>>
 882   //     __gen_vtable_impl<_Multi_array<void(*)(V1&&, V2&&)>,
 883   //                       tuple<V1&&, V2&&>, std::index_sequence<1, 2>>
 884   // The returned multi-dimensional vtable can be fast accessed by the visitor
 885   // using index calculation.
 886   template<typename _Array_type, typename _Index_seq>
 887     struct __gen_vtable_impl;
 888
 889   // Defines the _S_apply() member that returns a _Multi_array populated
 890   // with function pointers that perform the visitation expressions e(m)
 891   // for each valid pack of indexes into the variant types _Variants.
 892   //
 893   // This partial specialization builds up the index sequences by recursively
 894   // calling _S_apply() on the next specialization of __gen_vtable_impl.
 895   // The base case of the recursion defines the actual function pointers.
 896   template<typename _Result_type, typename _Visitor, size_t... __dimensions,
 897            typename... _Variants, size_t... __indices>
 898     struct __gen_vtable_impl<
 899         _Multi_array<_Result_type (*)(_Visitor, _Variants...), __dimensions...>,
 900         std::index_sequence<__indices...>>
 901     {
 902       using _Next =
 903           remove_reference_t<typename _Nth_type<sizeof...(__indices),
 904                              _Variants...>::type>;
 905       using _Array_type =
 906           _Multi_array<_Result_type (*)(_Visitor, _Variants...),
 907                        __dimensions...>;
 908
 909       static constexpr _Array_type
 910       _S_apply()
 911       {
 912         _Array_type __vtable{};
 913         _S_apply_all_alts(
 914           __vtable, make_index_sequence<variant_size_v<_Next>>());
 915         return __vtable;
 916       }
 917
 918       template<size_t... __var_indices>
 919         static constexpr void
 920         _S_apply_all_alts(_Array_type& __vtable,
 921                           std::index_sequence<__var_indices...>)
 922         {
 923           if constexpr (_Extra_visit_slot_needed<_Result_type, _Next>::value)
 924             (_S_apply_single_alt<true, __var_indices>(
 925               __vtable._M_arr[__var_indices + 1],
 926               &(__vtable._M_arr[0])), ...);
 927           else
 928             (_S_apply_single_alt<false, __var_indices>(
 929               __vtable._M_arr[__var_indices]), ...);
 930         }
 931
 932       template<bool __do_cookie, size_t __index, typename _Tp>
 933         static constexpr void
 934         _S_apply_single_alt(_Tp& __element, _Tp* __cookie_element = nullptr)
 935         {
 936           if constexpr (__do_cookie)
 937             {
 938               __element = __gen_vtable_impl<
 939                 _Tp,
 940                 std::index_sequence<__indices..., __index>>::_S_apply();
 941               *__cookie_element = __gen_vtable_impl<
 942                 _Tp,
 943                 std::index_sequence<__indices..., variant_npos>>::_S_apply();
 944             }
 945           else
 946             {
 947               __element = __gen_vtable_impl<
 948                 remove_reference_t<decltype(__element)>,
 949                 std::index_sequence<__indices..., __index>>::_S_apply();
 950             }
 951         }
 952     };
 953
 954   // This partial specialization is the base case for the recursion.
 955   // It populates a _Multi_array element with the address of a function
 956   // that invokes the visitor with the alternatives specified by __indices.
 957   template<typename _Result_type, typename _Visitor, typename... _Variants,
 958            size_t... __indices>
 959     struct __gen_vtable_impl<
 960       _Multi_array<_Result_type (*)(_Visitor, _Variants...)>,
 961                    std::index_sequence<__indices...>>
 962     {
 963       using _Array_type =
 964           _Multi_array<_Result_type (*)(_Visitor, _Variants...)>;
 965
 966       template<size_t __index, typename _Variant>
 967         static constexpr decltype(auto)
 968         __element_by_index_or_cookie(_Variant&& __var) noexcept
 969         {
 970           if constexpr (__index != variant_npos)
 971             return __variant::__get<__index>(std::forward<_Variant>(__var));
 972           else
 973             return __variant_cookie{};
 974         }
 975
 976       static constexpr decltype(auto)
 977       __visit_invoke(_Visitor&& __visitor, _Variants... __vars)
 978       {
 979         if constexpr (is_same_v<_Result_type, __variant_idx_cookie>)
 980           // For raw visitation using indices, pass the indices to the visitor
 981           // and discard the return value:
 982           std::__invoke(std::forward<_Visitor>(__visitor),
 983               __element_by_index_or_cookie<__indices>(
 984                 std::forward<_Variants>(__vars))...,
 985               integral_constant<size_t, __indices>()...);
 986         else if constexpr (is_same_v<_Result_type, __variant_cookie>)
 987           // For raw visitation without indices, and discard the return value:
 988           std::__invoke(std::forward<_Visitor>(__visitor),
 989               __element_by_index_or_cookie<__indices>(
 990                 std::forward<_Variants>(__vars))...);
 991         else if constexpr (_Array_type::__result_is_deduced::value)
 992           // For the usual std::visit case deduce the return value:
 993           return std::__invoke(std::forward<_Visitor>(__visitor),
 994               __element_by_index_or_cookie<__indices>(
 995                 std::forward<_Variants>(__vars))...);
 996         else // for std::visit<R> use INVOKE<R>
 997           return std::__invoke_r<_Result_type>(
 998               std::forward<_Visitor>(__visitor),
 999               __variant::__get<__indices>(std::forward<_Variants>(__vars))...);
1000       }
1001
1002       static constexpr auto
1003       _S_apply()
1004       { return _Array_type{&__visit_invoke}; }
1005     };
1006
1007   template<typename _Result_type, typename _Visitor, typename... _Variants>
1008     struct __gen_vtable
1009     {
1010       using _Array_type =
1011           _Multi_array<_Result_type (*)(_Visitor, _Variants...),
1012                        variant_size_v<remove_reference_t<_Variants>>...>;
1013
1014       static constexpr _Array_type _S_vtable
1015         = __gen_vtable_impl<_Array_type, std::index_sequence<>>::_S_apply();
1016     };
1017
1018   template<size_t _Np, typename _Tp>
1019     struct _Base_dedup : public _Tp { };
1020
1021   template<typename _Variant, typename __indices>
1022     struct _Variant_hash_base;
1023
1024   template<typename... _Types, size_t... __indices>
1025     struct _Variant_hash_base<variant<_Types...>,
1026                               std::index_sequence<__indices...>>
1027     : _Base_dedup<__indices, __poison_hash<remove_const_t<_Types>>>... { };
1028
1029 } // namespace __variant
1030 } // namespace __detail
1031
1032   template<size_t _Np, typename _Variant, typename... _Args>
1033     void __variant_construct_by_index(_Variant& __v, _Args&&... __args)
1034     {
1035       __v._M_index = _Np;
1036       auto&& __storage = __detail::__variant::__get<_Np>(__v);
1037       ::new ((void*)std::addressof(__storage))
1038         remove_reference_t<decltype(__storage)>
1039           (std::forward<_Args>(__args)...);
1040     }
1041
1042   template<typename _Tp, typename... _Types>
1043     constexpr bool
1044     holds_alternative(const variant<_Types...>& __v) noexcept
1045     {
1046       static_assert(__detail::__variant::__exactly_once<_Tp, _Types...>,
1047                     "T should occur for exactly once in alternatives");
1048       return __v.index() == __detail::__variant::__index_of_v<_Tp, _Types...>;
1049     }
1050
1051   template<typename _Tp, typename... _Types>
1052     constexpr _Tp& get(variant<_Types...>& __v)
1053     {
1054       static_assert(__detail::__variant::__exactly_once<_Tp, _Types...>,
1055                     "T should occur for exactly once in alternatives");
1056       static_assert(!is_void_v<_Tp>, "_Tp should not be void");
1057       return std::get<__detail::__variant::__index_of_v<_Tp, _Types...>>(__v);
1058     }
1059
1060   template<typename _Tp, typename... _Types>
1061     constexpr _Tp&& get(variant<_Types...>&& __v)
1062     {
1063       static_assert(__detail::__variant::__exactly_once<_Tp, _Types...>,
1064                     "T should occur for exactly once in alternatives");
1065       static_assert(!is_void_v<_Tp>, "_Tp should not be void");
1066       return std::get<__detail::__variant::__index_of_v<_Tp, _Types...>>(
1067         std::move(__v));
1068     }
1069
1070   template<typename _Tp, typename... _Types>
1071     constexpr const _Tp& get(const variant<_Types...>& __v)
1072     {
1073       static_assert(__detail::__variant::__exactly_once<_Tp, _Types...>,
1074                     "T should occur for exactly once in alternatives");
1075       static_assert(!is_void_v<_Tp>, "_Tp should not be void");
1076       return std::get<__detail::__variant::__index_of_v<_Tp, _Types...>>(__v);
1077     }
1078
1079   template<typename _Tp, typename... _Types>
1080     constexpr const _Tp&& get(const variant<_Types...>&& __v)
1081     {
1082       static_assert(__detail::__variant::__exactly_once<_Tp, _Types...>,
1083                     "T should occur for exactly once in alternatives");
1084       static_assert(!is_void_v<_Tp>, "_Tp should not be void");
1085       return std::get<__detail::__variant::__index_of_v<_Tp, _Types...>>(
1086         std::move(__v));
1087     }
1088
1089   template<size_t _Np, typename... _Types>
1090     constexpr add_pointer_t<variant_alternative_t<_Np, variant<_Types...>>>
1091     get_if(variant<_Types...>* __ptr) noexcept
1092     {
1093       using _Alternative_type = variant_alternative_t<_Np, variant<_Types...>>;
1094       static_assert(_Np < sizeof...(_Types),
1095                     "The index should be in [0, number of alternatives)");
1096       static_assert(!is_void_v<_Alternative_type>, "_Tp should not be void");
1097       if (__ptr && __ptr->index() == _Np)
1098         return std::addressof(__detail::__variant::__get<_Np>(*__ptr));
1099       return nullptr;
1100     }
1101
1102   template<size_t _Np, typename... _Types>
1103     constexpr
1104     add_pointer_t<const variant_alternative_t<_Np, variant<_Types...>>>
1105     get_if(const variant<_Types...>* __ptr) noexcept
1106     {
1107       using _Alternative_type = variant_alternative_t<_Np, variant<_Types...>>;
1108       static_assert(_Np < sizeof...(_Types),
1109                     "The index should be in [0, number of alternatives)");
1110       static_assert(!is_void_v<_Alternative_type>, "_Tp should not be void");
1111       if (__ptr && __ptr->index() == _Np)
1112         return std::addressof(__detail::__variant::__get<_Np>(*__ptr));
1113       return nullptr;
1114     }
1115
1116   template<typename _Tp, typename... _Types>
1117     constexpr add_pointer_t<_Tp>
1118     get_if(variant<_Types...>* __ptr) noexcept
1119     {
1120       static_assert(__detail::__variant::__exactly_once<_Tp, _Types...>,
1121                     "T should occur for exactly once in alternatives");
1122       static_assert(!is_void_v<_Tp>, "_Tp should not be void");
1123       return std::get_if<__detail::__variant::__index_of_v<_Tp, _Types...>>(
1124           __ptr);
1125     }
1126
1127   template<typename _Tp, typename... _Types>
1128     constexpr add_pointer_t<const _Tp>
1129     get_if(const variant<_Types...>* __ptr) noexcept
1130     {
1131       static_assert(__detail::__variant::__exactly_once<_Tp, _Types...>,
1132                     "T should occur for exactly once in alternatives");
1133       static_assert(!is_void_v<_Tp>, "_Tp should not be void");
1134       return std::get_if<__detail::__variant::__index_of_v<_Tp, _Types...>>(
1135           __ptr);
1136     }
1137
1138   struct monostate { };
1139
1140 #define _VARIANT_RELATION_FUNCTION_TEMPLATE(__OP, __NAME) \
1141   template<typename... _Types> \
1142     constexpr bool operator __OP(const variant<_Types...>& __lhs, \
1143                                  const variant<_Types...>& __rhs) \
1144     { \
1145       bool __ret = true; \
1146       __detail::__variant::__raw_idx_visit( \
1147         [&__ret, &__lhs] (auto&& __rhs_mem, auto __rhs_index) mutable \
1148         { \
1149           if constexpr (__rhs_index != variant_npos) \
1150             { \
1151               if (__lhs.index() == __rhs_index) \
1152                 { \
1153                   auto& __this_mem = std::get<__rhs_index>(__lhs);      \
1154                   __ret = __this_mem __OP __rhs_mem; \
1155                 } \
1156               else \
1157                 __ret = (__lhs.index() + 1) __OP (__rhs_index + 1); \
1158             } \
1159           else \
1160             __ret = (__lhs.index() + 1) __OP (__rhs_index + 1); \
1161         }, __rhs); \
1162       return __ret; \
1163     } \
1164 \
1165   constexpr bool operator __OP(monostate, monostate) noexcept \
1166   { return 0 __OP 0; }
1167
1168   _VARIANT_RELATION_FUNCTION_TEMPLATE(<, less)
1169   _VARIANT_RELATION_FUNCTION_TEMPLATE(<=, less_equal)
1170   _VARIANT_RELATION_FUNCTION_TEMPLATE(==, equal)
1171   _VARIANT_RELATION_FUNCTION_TEMPLATE(!=, not_equal)
1172   _VARIANT_RELATION_FUNCTION_TEMPLATE(>=, greater_equal)
1173   _VARIANT_RELATION_FUNCTION_TEMPLATE(>, greater)
1174
1175 #undef _VARIANT_RELATION_FUNCTION_TEMPLATE
1176
1177   template<typename _Visitor, typename... _Variants>
1178     constexpr decltype(auto) visit(_Visitor&&, _Variants&&...);
1179
1180   template<typename... _Types>
1181     inline enable_if_t<(is_move_constructible_v<_Types> && ...)
1182                         && (is_swappable_v<_Types> && ...)>
1183     swap(variant<_Types...>& __lhs, variant<_Types...>& __rhs)
1184     noexcept(noexcept(__lhs.swap(__rhs)))
1185     { __lhs.swap(__rhs); }
1186
1187   template<typename... _Types>
1188     enable_if_t<!((is_move_constructible_v<_Types> && ...)
1189                    && (is_swappable_v<_Types> && ...))>
1190     swap(variant<_Types...>&, variant<_Types...>&) = delete;
1191
1192   class bad_variant_access : public exception
1193   {
1194   public:
1195     bad_variant_access() noexcept : _M_reason("Unknown reason") { }
1196     const char* what() const noexcept override
1197     { return _M_reason; }
1198
1199   private:
1200     bad_variant_access(const char* __reason) : _M_reason(__reason) { }
1201
1202     const char* _M_reason;
1203
1204     friend void __throw_bad_variant_access(const char* __what);
1205   };
1206
1207   inline void
1208   __throw_bad_variant_access(const char* __what)
1209   { _GLIBCXX_THROW_OR_ABORT(bad_variant_access(__what)); }
1210
1211   template<typename... _Types>
1212     class variant
1213     : private __detail::__variant::_Variant_base<_Types...>,
1214       private _Enable_default_constructor<
1215         __detail::__variant::_Traits<_Types...>::_S_default_ctor,
1216           variant<_Types...>>,
1217       private _Enable_copy_move<
1218         __detail::__variant::_Traits<_Types...>::_S_copy_ctor,
1219         __detail::__variant::_Traits<_Types...>::_S_copy_assign,
1220         __detail::__variant::_Traits<_Types...>::_S_move_ctor,
1221         __detail::__variant::_Traits<_Types...>::_S_move_assign,
1222         variant<_Types...>>
1223     {
1224     private:
1225       template <typename... _UTypes, typename _Tp>
1226         friend decltype(auto) __variant_cast(_Tp&&);
1227       template<size_t _Np, typename _Variant, typename... _Args>
1228         friend void __variant_construct_by_index(_Variant& __v,
1229                                                  _Args&&... __args);
1230
1231       static_assert(sizeof...(_Types) > 0,
1232                     "variant must have at least one alternative");
1233       static_assert(!(std::is_reference_v<_Types> || ...),
1234                     "variant must have no reference alternative");
1235       static_assert(!(std::is_void_v<_Types> || ...),
1236                     "variant must have no void alternative");
1237
1238       using _Base = __detail::__variant::_Variant_base<_Types...>;
1239       using _Default_ctor_enabler =
1240         _Enable_default_constructor<
1241           __detail::__variant::_Traits<_Types...>::_S_default_ctor,
1242             variant<_Types...>>;
1243
1244       template<typename _Tp>
1245         static constexpr bool __not_self
1246           = !is_same_v<__remove_cvref_t<_Tp>, variant>;
1247
1248       template<typename _Tp>
1249         static constexpr bool
1250         __exactly_once = __detail::__variant::__exactly_once<_Tp, _Types...>;
1251
1252       template<typename _Tp>
1253         static constexpr size_t __accepted_index =
1254           __detail::__variant::__accepted_index<_Tp&&, variant>::value;
1255
1256       template<size_t _Np, typename = enable_if_t<(_Np < sizeof...(_Types))>>
1257         using __to_type = variant_alternative_t<_Np, variant>;
1258
1259       template<typename _Tp, typename = enable_if_t<__not_self<_Tp>>>
1260         using __accepted_type = __to_type<__accepted_index<_Tp>>;
1261
1262       template<typename _Tp>
1263         static constexpr size_t __index_of =
1264           __detail::__variant::__index_of_v<_Tp, _Types...>;
1265
1266       using _Traits = __detail::__variant::_Traits<_Types...>;
1267
1268       template<typename _Tp>
1269         struct __is_in_place_tag : false_type { };
1270       template<typename _Tp>
1271         struct __is_in_place_tag<in_place_type_t<_Tp>> : true_type { };
1272       template<size_t _Np>
1273         struct __is_in_place_tag<in_place_index_t<_Np>> : true_type { };
1274
1275       template<typename _Tp>
1276         static constexpr bool __not_in_place_tag
1277           = !__is_in_place_tag<__remove_cvref_t<_Tp>>::value;
1278
1279     public:
1280       variant() = default;
1281       variant(const variant& __rhs) = default;
1282       variant(variant&&) = default;
1283       variant& operator=(const variant&) = default;
1284       variant& operator=(variant&&) = default;
1285       ~variant() = default;
1286
1287       template<typename _Tp,
1288                typename = enable_if_t<sizeof...(_Types) != 0>,
1289                typename = enable_if_t<__not_in_place_tag<_Tp>>,
1290                typename _Tj = __accepted_type<_Tp&&>,
1291                typename = enable_if_t<__exactly_once<_Tj>
1292                                       && is_constructible_v<_Tj, _Tp>>>
1293         constexpr
1294         variant(_Tp&& __t)
1295         noexcept(is_nothrow_constructible_v<_Tj, _Tp>)
1296         : variant(in_place_index<__accepted_index<_Tp&&>>,
1297                   std::forward<_Tp>(__t))
1298         { }
1299
1300       template<typename _Tp, typename... _Args,
1301                typename = enable_if_t<__exactly_once<_Tp>
1302                                       && is_constructible_v<_Tp, _Args...>>>
1303         constexpr explicit
1304         variant(in_place_type_t<_Tp>, _Args&&... __args)
1305         : variant(in_place_index<__index_of<_Tp>>,
1306                   std::forward<_Args>(__args)...)
1307         { }
1308
1309       template<typename _Tp, typename _Up, typename... _Args,
1310                typename = enable_if_t<__exactly_once<_Tp>
1311                                       && is_constructible_v<_Tp,
1312                                            initializer_list<_Up>&, _Args...>>>
1313         constexpr explicit
1314         variant(in_place_type_t<_Tp>, initializer_list<_Up> __il,
1315                 _Args&&... __args)
1316         : variant(in_place_index<__index_of<_Tp>>, __il,
1317                   std::forward<_Args>(__args)...)
1318         { }
1319
1320       template<size_t _Np, typename... _Args,
1321                typename _Tp = __to_type<_Np>,
1322                typename = enable_if_t<is_constructible_v<_Tp, _Args...>>>
1323         constexpr explicit
1324         variant(in_place_index_t<_Np>, _Args&&... __args)
1325         : _Base(in_place_index<_Np>, std::forward<_Args>(__args)...),
1326         _Default_ctor_enabler(_Enable_default_constructor_tag{})
1327         { }
1328
1329       template<size_t _Np, typename _Up, typename... _Args,
1330                typename _Tp = __to_type<_Np>,
1331                typename = enable_if_t<is_constructible_v<_Tp,
1332                                                          initializer_list<_Up>&,
1333                                                          _Args...>>>
1334         constexpr explicit
1335         variant(in_place_index_t<_Np>, initializer_list<_Up> __il,
1336                 _Args&&... __args)
1337         : _Base(in_place_index<_Np>, __il, std::forward<_Args>(__args)...),
1338         _Default_ctor_enabler(_Enable_default_constructor_tag{})
1339         { }
1340
1341       template<typename _Tp>
1342         enable_if_t<__exactly_once<__accepted_type<_Tp&&>>
1343                     && is_constructible_v<__accepted_type<_Tp&&>, _Tp>
1344                     && is_assignable_v<__accepted_type<_Tp&&>&, _Tp>,
1345                     variant&>
1346         operator=(_Tp&& __rhs)
1347         noexcept(is_nothrow_assignable_v<__accepted_type<_Tp&&>&, _Tp>
1348                  && is_nothrow_constructible_v<__accepted_type<_Tp&&>, _Tp>)
1349         {
1350           constexpr auto __index = __accepted_index<_Tp&&>;
1351           if (index() == __index)
1352             std::get<__index>(*this) = std::forward<_Tp>(__rhs);
1353           else
1354             {
1355               using _Tj = __accepted_type<_Tp&&>;
1356               if constexpr (is_nothrow_constructible_v<_Tj, _Tp>
1357                             || !is_nothrow_move_constructible_v<_Tj>)
1358                 this->emplace<__index>(std::forward<_Tp>(__rhs));
1359               else
1360                 operator=(variant(std::forward<_Tp>(__rhs)));
1361             }
1362           return *this;
1363         }
1364
1365       template<typename _Tp, typename... _Args>
1366         enable_if_t<is_constructible_v<_Tp, _Args...> && __exactly_once<_Tp>,
1367                     _Tp&>
1368         emplace(_Args&&... __args)
1369         {
1370           constexpr size_t __index = __index_of<_Tp>;
1371           return this->emplace<__index>(std::forward<_Args>(__args)...);
1372         }
1373
1374       template<typename _Tp, typename _Up, typename... _Args>
1375         enable_if_t<is_constructible_v<_Tp, initializer_list<_Up>&, _Args...>
1376                     && __exactly_once<_Tp>,
1377                     _Tp&>
1378         emplace(initializer_list<_Up> __il, _Args&&... __args)
1379         {
1380           constexpr size_t __index = __index_of<_Tp>;
1381           return this->emplace<__index>(__il, std::forward<_Args>(__args)...);
1382         }
1383
1384       template<size_t _Np, typename... _Args>
1385         enable_if_t<is_constructible_v<variant_alternative_t<_Np, variant>,
1386                                        _Args...>,
1387                     variant_alternative_t<_Np, variant>&>
1388         emplace(_Args&&... __args)
1389         {
1390           static_assert(_Np < sizeof...(_Types),
1391                         "The index should be in [0, number of alternatives)");
1392           using type = variant_alternative_t<_Np, variant>;
1393           // Provide the strong exception-safety guarantee when possible,
1394           // to avoid becoming valueless.
1395           if constexpr (is_nothrow_constructible_v<type, _Args...>)
1396             {
1397               this->_M_reset();
1398               __variant_construct_by_index<_Np>(*this,
1399                   std::forward<_Args>(__args)...);
1400             }
1401           else if constexpr (is_scalar_v<type>)
1402             {
1403               // This might invoke a potentially-throwing conversion operator:
1404               const type __tmp(std::forward<_Args>(__args)...);
1405               // But these steps won't throw:
1406               this->_M_reset();
1407               __variant_construct_by_index<_Np>(*this, __tmp);
1408             }
1409           else if constexpr (__detail::__variant::_Never_valueless_alt<type>()
1410               && _Traits::_S_move_assign)
1411             {
1412               // This construction might throw:
1413               variant __tmp(in_place_index<_Np>,
1414                             std::forward<_Args>(__args)...);
1415               // But _Never_valueless_alt<type> means this won't:
1416               *this = std::move(__tmp);
1417             }
1418           else
1419             {
1420               // This case only provides the basic exception-safety guarantee,
1421               // i.e. the variant can become valueless.
1422               this->_M_reset();
1423               __try
1424                 {
1425                   __variant_construct_by_index<_Np>(*this,
1426                     std::forward<_Args>(__args)...);
1427                 }
1428               __catch (...)
1429                 {
1430                   this->_M_index = variant_npos;
1431                   __throw_exception_again;
1432                 }
1433             }
1434           return std::get<_Np>(*this);
1435         }
1436
1437       template<size_t _Np, typename _Up, typename... _Args>
1438         enable_if_t<is_constructible_v<variant_alternative_t<_Np, variant>,
1439                                        initializer_list<_Up>&, _Args...>,
1440                     variant_alternative_t<_Np, variant>&>
1441         emplace(initializer_list<_Up> __il, _Args&&... __args)
1442         {
1443           static_assert(_Np < sizeof...(_Types),
1444                         "The index should be in [0, number of alternatives)");
1445           using type = variant_alternative_t<_Np, variant>;
1446           // Provide the strong exception-safety guarantee when possible,
1447           // to avoid becoming valueless.
1448           if constexpr (is_nothrow_constructible_v<type,
1449                                                    initializer_list<_Up>&,
1450                                                    _Args...>)
1451             {
1452               this->_M_reset();
1453               __variant_construct_by_index<_Np>(*this, __il,
1454                   std::forward<_Args>(__args)...);
1455             }
1456           else if constexpr (__detail::__variant::_Never_valueless_alt<type>()
1457               && _Traits::_S_move_assign)
1458             {
1459               // This construction might throw:
1460               variant __tmp(in_place_index<_Np>, __il,
1461                             std::forward<_Args>(__args)...);
1462               // But _Never_valueless_alt<type> means this won't:
1463               *this = std::move(__tmp);
1464             }
1465           else
1466             {
1467               // This case only provides the basic exception-safety guarantee,
1468               // i.e. the variant can become valueless.
1469               this->_M_reset();
1470               __try
1471                 {
1472                   __variant_construct_by_index<_Np>(*this, __il,
1473                     std::forward<_Args>(__args)...);
1474                 }
1475               __catch (...)
1476                 {
1477                   this->_M_index = variant_npos;
1478                   __throw_exception_again;
1479                 }
1480             }
1481           return std::get<_Np>(*this);
1482         }
1483
1484       constexpr bool valueless_by_exception() const noexcept
1485       { return !this->_M_valid(); }
1486
1487       constexpr size_t index() const noexcept
1488       {
1489         if (this->_M_index ==
1490             typename _Base::__index_type(variant_npos))
1491           return variant_npos;
1492         return this->_M_index;
1493       }
1494
1495       void
1496       swap(variant& __rhs)
1497       noexcept((__is_nothrow_swappable<_Types>::value && ...)
1498                && is_nothrow_move_constructible_v<variant>)
1499       {
1500         __detail::__variant::__raw_idx_visit(
1501           [this, &__rhs](auto&& __rhs_mem, auto __rhs_index) mutable
1502           {
1503             if constexpr (__rhs_index != variant_npos)
1504               {
1505                 if (this->index() == __rhs_index)
1506                   {
1507                     auto& __this_mem =
1508                       std::get<__rhs_index>(*this);
1509                     using std::swap;
1510                     swap(__this_mem, __rhs_mem);
1511                   }
1512                 else
1513                   {
1514                     if (this->index() != variant_npos)
1515                       {
1516                         auto __tmp(std::move(__rhs_mem));
1517                         __rhs = std::move(*this);
1518                         this->_M_destructive_move(__rhs_index,
1519                                                   std::move(__tmp));
1520                       }
1521                     else
1522                       {
1523                         this->_M_destructive_move(__rhs_index,
1524                                                   std::move(__rhs_mem));
1525                         __rhs._M_reset();
1526                       }
1527                   }
1528               }
1529             else
1530               {
1531                 if (this->index() != variant_npos)
1532                   {
1533                     __rhs = std::move(*this);
1534                     this->_M_reset();
1535                   }
1536               }
1537           }, __rhs);
1538       }
1539
1540     private:
1541
1542 #if defined(__clang__) && __clang_major__ <= 7
1543     public:
1544       using _Base::_M_u; // See https://bugs.llvm.org/show_bug.cgi?id=31852
1545     private:
1546 #endif
1547
1548       template<size_t _Np, typename _Vp>
1549         friend constexpr decltype(auto)
1550         __detail::__variant::__get(_Vp&& __v) noexcept;
1551
1552       template<typename _Vp>
1553         friend void*
1554         __detail::__variant::__get_storage(_Vp&& __v) noexcept;
1555
1556 #define _VARIANT_RELATION_FUNCTION_TEMPLATE(__OP) \
1557       template<typename... _Tp> \
1558         friend constexpr bool \
1559         operator __OP(const variant<_Tp...>& __lhs, \
1560                       const variant<_Tp...>& __rhs);
1561
1562       _VARIANT_RELATION_FUNCTION_TEMPLATE(<)
1563       _VARIANT_RELATION_FUNCTION_TEMPLATE(<=)
1564       _VARIANT_RELATION_FUNCTION_TEMPLATE(==)
1565       _VARIANT_RELATION_FUNCTION_TEMPLATE(!=)
1566       _VARIANT_RELATION_FUNCTION_TEMPLATE(>=)
1567       _VARIANT_RELATION_FUNCTION_TEMPLATE(>)
1568
1569 #undef _VARIANT_RELATION_FUNCTION_TEMPLATE
1570     };
1571
1572   template<size_t _Np, typename... _Types>
1573     constexpr variant_alternative_t<_Np, variant<_Types...>>&
1574     get(variant<_Types...>& __v)
1575     {
1576       static_assert(_Np < sizeof...(_Types),
1577                     "The index should be in [0, number of alternatives)");
1578       if (__v.index() != _Np)
1579         __throw_bad_variant_access("Unexpected index");
1580       return __detail::__variant::__get<_Np>(__v);
1581     }
1582
1583   template<size_t _Np, typename... _Types>
1584     constexpr variant_alternative_t<_Np, variant<_Types...>>&&
1585     get(variant<_Types...>&& __v)
1586     {
1587       static_assert(_Np < sizeof...(_Types),
1588                     "The index should be in [0, number of alternatives)");
1589       if (__v.index() != _Np)
1590         __throw_bad_variant_access("Unexpected index");
1591       return __detail::__variant::__get<_Np>(std::move(__v));
1592     }
1593
1594   template<size_t _Np, typename... _Types>
1595     constexpr const variant_alternative_t<_Np, variant<_Types...>>&
1596     get(const variant<_Types...>& __v)
1597     {
1598       static_assert(_Np < sizeof...(_Types),
1599                     "The index should be in [0, number of alternatives)");
1600       if (__v.index() != _Np)
1601         __throw_bad_variant_access("Unexpected index");
1602       return __detail::__variant::__get<_Np>(__v);
1603     }
1604
1605   template<size_t _Np, typename... _Types>
1606     constexpr const variant_alternative_t<_Np, variant<_Types...>>&&
1607     get(const variant<_Types...>&& __v)
1608     {
1609       static_assert(_Np < sizeof...(_Types),
1610                     "The index should be in [0, number of alternatives)");
1611       if (__v.index() != _Np)
1612         __throw_bad_variant_access("Unexpected index");
1613       return __detail::__variant::__get<_Np>(std::move(__v));
1614     }
1615
1616   template<typename _Result_type, typename _Visitor, typename... _Variants>
1617     constexpr decltype(auto)
1618     __do_visit(_Visitor&& __visitor, _Variants&&... __variants)
1619     {
1620       constexpr auto& __vtable = __detail::__variant::__gen_vtable<
1621         _Result_type, _Visitor&&, _Variants&&...>::_S_vtable;
1622
1623       auto __func_ptr = __vtable._M_access(__variants.index()...);
1624       return (*__func_ptr)(std::forward<_Visitor>(__visitor),
1625                            std::forward<_Variants>(__variants)...);
1626     }
1627
1628   template<typename _Visitor, typename... _Variants>
1629     constexpr decltype(auto)
1630     visit(_Visitor&& __visitor, _Variants&&... __variants)
1631     {
1632       if ((__variants.valueless_by_exception() || ...))
1633         __throw_bad_variant_access("Unexpected index");
1634
1635       using _Result_type = std::invoke_result_t<_Visitor,
1636         decltype(std::get<0>(std::declval<_Variants>()))...>;
1637
1638       using _Tag = __detail::__variant::__deduce_visit_result<_Result_type>;
1639
1640       return __do_visit<_Tag>(std::forward<_Visitor>(__visitor),
1641                               std::forward<_Variants>(__variants)...);
1642     }
1643
1644 #if __cplusplus > 201703L
1645   template<typename _Res, typename _Visitor, typename... _Variants>
1646     constexpr _Res
1647     visit(_Visitor&& __visitor, _Variants&&... __variants)
1648     {
1649       if ((__variants.valueless_by_exception() || ...))
1650         __throw_bad_variant_access("Unexpected index");
1651
1652       return __do_visit<_Res>(std::forward<_Visitor>(__visitor),
1653                               std::forward<_Variants>(__variants)...);
1654     }
1655 #endif
1656
1657   template<bool, typename... _Types>
1658     struct __variant_hash_call_base_impl
1659     {
1660       size_t
1661       operator()(const variant<_Types...>& __t) const
1662       noexcept((is_nothrow_invocable_v<hash<decay_t<_Types>>, _Types> && ...))
1663       {
1664         size_t __ret;
1665         __detail::__variant::__raw_visit(
1666           [&__t, &__ret](auto&& __t_mem) mutable
1667           {
1668             using _Type = __remove_cvref_t<decltype(__t_mem)>;
1669             if constexpr (!is_same_v<_Type,
1670                                      __detail::__variant::__variant_cookie>)
1671               __ret = std::hash<size_t>{}(__t.index())
1672                       + std::hash<_Type>{}(__t_mem);
1673             else
1674               __ret = std::hash<size_t>{}(__t.index());
1675           }, __t);
1676         return __ret;
1677       }
1678     };
1679
1680   template<typename... _Types>
1681     struct __variant_hash_call_base_impl<false, _Types...> {};
1682
1683   template<typename... _Types>
1684     using __variant_hash_call_base =
1685     __variant_hash_call_base_impl<(__poison_hash<remove_const_t<_Types>>::
1686                                    __enable_hash_call &&...), _Types...>;
1687
1688   template<typename... _Types>
1689     struct hash<variant<_Types...>>
1690     : private __detail::__variant::_Variant_hash_base<
1691         variant<_Types...>, std::index_sequence_for<_Types...>>,
1692       public __variant_hash_call_base<_Types...>
1693     {
1694       using result_type [[__deprecated__]] = size_t;
1695       using argument_type [[__deprecated__]] = variant<_Types...>;
1696     };
1697
1698   template<>
1699     struct hash<monostate>
1700     {
1701       using result_type [[__deprecated__]] = size_t;
1702       using argument_type [[__deprecated__]] = monostate;
1703
1704       size_t
1705       operator()(const monostate& __t) const noexcept
1706       {
1707         constexpr size_t __magic_monostate_hash = -7777;
1708         return __magic_monostate_hash;
1709       }
1710     };
1711
1712   template<typename... _Types>
1713     struct __is_fast_hash<hash<variant<_Types...>>>
1714     : bool_constant<(__is_fast_hash<_Types>::value && ...)>
1715     { };
1716
1717 _GLIBCXX_END_NAMESPACE_VERSION
1718 } // namespace std
1719
1720 #endif // C++17
1721
1722 #endif // _GLIBCXX_VARIANT