[libc++] Shrink variant's index type when possible

[EricWF]

Summary

Currently std::variant always uses an unsigned int to store the variant index. However this isn't nessesary and causes std::variant to be larger than it needs to be in most cases.

This patch changes the index type to be unsigned char when possible, and unsigned short or unsigned int otherwise, depending on the size (Although it's questionable if it's even possible to create a variant with 65535 elements.

Unfortunately this change is an ABI break, and as such is only enabled in ABI v2.

[mpark]

include/variant

296

s/_NumElem/_NumAlts/

301–304

Could we inline the whole thing and also avoid using the tuple utilities?
We should also add the #include <limits>

conditional_t<
  (_NumElem < numeric_limits<unsigned char>::max()),
  unsigned char,
  conditional_t<(_NumElem < numeric_limits<unsigned short>::max()),
                unsigned short,
                unsigned int>;

307

s/_IntType/_IndexType/ maybe?

test/libcxx/utilities/variant/variant.variant/variant_size.pass.cpp

18

Doesn't seem like this is used?

27

Hm, I see 15 instances of Indices and 7 instances of Indexes.
Can we use Indices everywhere?

53–54

I guess I asked you to remove this above. Is this an essential part of the test?

[EricWF]

include/variant

301–304

Not sure that's any cleaner or clearer. Plus it makes it harder to test.

Adding #include <limits> as suggested.

test/libcxx/utilities/variant/variant.variant/variant_size.pass.cpp

53–54

It is a nice part of it. I pushed back on removing the function as noted above. Perhaps this can stay then?

[EricWF]

• Address inline comments.

include/__config

 // instead of as a class simulating an enum. If this option is enabled
 // `pointer_safety` and `get_pointer_safety()` will no longer be available
 // in C++03.
 #define _LIBCPP_ABI_POINTER_SAFETY_ENUM_TYPE
 // Define a key function for `bad_function_call` in the library, to centralize
 // its vtable and typeinfo to libc++ rather than having all other libraries
 // using that class define their own copies.
 #define _LIBCPP_ABI_BAD_FUNCTION_CALL_KEY_FUNCTION
-
 // Enable optimized version of __do_get_(un)signed which avoids redundant copies.
 #define _LIBCPP_ABI_OPTIMIZED_LOCALE_NUM_GET
+// Use the smallest possible integer type to represent the index of the variant.
+// Previously libc++ used "unsigned int" exclusivly.
+#define _LIBCPP_ABI_VARIANT_INDEX_TYPE_OPTIMIZATION
 #elif _LIBCPP_ABI_VERSION == 1
 #if !defined(_LIBCPP_OBJECT_FORMAT_COFF)
 // Enable compiling copies of now inline methods into the dylib to support
 // applications compiled against older libraries. This is unnecessary with
 // COFF dllexport semantics, since dllexport forces a non-inline definition
 // of inline functions to be emitted anyway. Our own non-inline copy would
 // conflict with the dllexport-emitted copy, so we disable it.
 #define _LIBCPP_DEPRECATED_ABI_LEGACY_LIBRARY_DEFINITIONS_FOR_INLINE_FUNCTIONS

include/variant

 #include <array>
 #include <exception>
 #include <functional>
 #include <initializer_list>
 #include <new>
 #include <tuple>
 #include <type_traits>
 #include <utility>
+#include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 namespace std { // explicitly not using versioning namespace
 
 class _LIBCPP_EXCEPTION_ABI bad_variant_access : public exception {

 
 template <size_t _Ip, class... _Types>
 struct _LIBCPP_TEMPLATE_VIS variant_alternative<_Ip, variant<_Types...>> {
   static_assert(_Ip < sizeof...(_Types), "Index out of bounds in std::variant_alternative<>");
   using type = __type_pack_element<_Ip, _Types...>;
 };
 
 constexpr size_t variant_npos = static_cast<size_t>(-1);
-constexpr unsigned int __variant_npos = static_cast<unsigned int>(-1);
+
+constexpr int __choose_index_type(unsigned int __num_elem) {
+  if (__num_elem < std::numeric_limits<unsigned char>::max())
+    return 0;
+  if (__num_elem < std::numeric_limits<unsigned short>::max())
+    return 1;
+  return 2;
+}
+
+template <size_t _NumAlts>
+using __variant_index_t =
+#ifndef _LIBCPP_ABI_VARIANT_INDEX_TYPE_OPTIMIZATION
+  unsigned int;
+#else
+  std::tuple_element_t<
+      __choose_index_type(_NumAlts),
+      std::tuple<unsigned char, unsigned short, unsigned int>
+  >;
+#endif
+
+template <class _IndexType>
+constexpr _IndexType __variant_npos = static_cast<_IndexType>(-1);
 
 namespace __find_detail {
 
 template <class _Tp, class... _Types>
 inline _LIBCPP_INLINE_VISIBILITY
 constexpr size_t __find_index() {
   constexpr bool __matches[] = {is_same_v<_Tp, _Types>...};
   size_t __result = __not_found;

 _LIBCPP_VARIANT_UNION(_Trait::_Available, ~__union() {});
 _LIBCPP_VARIANT_UNION(_Trait::_Unavailable, ~__union() = delete;);
 
 #undef _LIBCPP_VARIANT_UNION
 
 template <_Trait _DestructibleTrait, class... _Types>
 class _LIBCPP_TEMPLATE_VIS __base {
 public:
+  using __index_t = __variant_index_t<sizeof...(_Types)>;
+
   inline _LIBCPP_INLINE_VISIBILITY
   explicit constexpr __base(__valueless_t tag) noexcept
-      : __data(tag), __index(__variant_npos) {}
+      : __data(tag), __index(__variant_npos<__index_t>) {}
 
   template <size_t _Ip, class... _Args>
   inline _LIBCPP_INLINE_VISIBILITY
   explicit constexpr __base(in_place_index_t<_Ip>, _Args&&... __args)
       :
         __data(in_place_index<_Ip>, _VSTD::forward<_Args>(__args)...),
         __index(_Ip) {}
 
   inline _LIBCPP_INLINE_VISIBILITY
   constexpr bool valueless_by_exception() const noexcept {
     return index() == variant_npos;
   }
 
   inline _LIBCPP_INLINE_VISIBILITY
   constexpr size_t index() const noexcept {
-    return __index == __variant_npos ? variant_npos : __index;
+    return __index == __variant_npos<__index_t> ? variant_npos : __index;
   }
 
 protected:
   inline _LIBCPP_INLINE_VISIBILITY
   constexpr auto&& __as_base() & { return *this; }
 
   inline _LIBCPP_INLINE_VISIBILITY
   constexpr auto&& __as_base() && { return _VSTD::move(*this); }
 
   inline _LIBCPP_INLINE_VISIBILITY
   constexpr auto&& __as_base() const & { return *this; }
 
   inline _LIBCPP_INLINE_VISIBILITY
   constexpr auto&& __as_base() const && { return _VSTD::move(*this); }
 
   inline _LIBCPP_INLINE_VISIBILITY
   static constexpr size_t __size() { return sizeof...(_Types); }
 
   __union<_DestructibleTrait, 0, _Types...> __data;
-  unsigned int __index;
+  __index_t __index;
 
   friend struct __access::__base;
   friend struct __visitation::__base;
 };
 
 template <class _Traits, _Trait = _Traits::__destructible_trait>
 class _LIBCPP_TEMPLATE_VIS __destructor;
 
 #define _LIBCPP_VARIANT_DESTRUCTOR(destructible_trait, destructor, destroy)    \
   template <class... _Types>                                                   \
-  class _LIBCPP_TEMPLATE_VIS __destructor<__traits<_Types...>,                \
+  class _LIBCPP_TEMPLATE_VIS __destructor<__traits<_Types...>,                 \
                                            destructible_trait>                 \
       : public __base<destructible_trait, _Types...> {                         \
     using __base_type = __base<destructible_trait, _Types...>;                 \
+    using __index_t = typename __base_type::__index_t;                         \
                                                                                \
   public:                                                                      \
     using __base_type::__base_type;                                            \
     using __base_type::operator=;                                              \
                                                                                \
     __destructor(const __destructor&) = default;                               \
     __destructor(__destructor&&) = default;                                    \
     destructor                                                                 \
     __destructor& operator=(const __destructor&) = default;                    \
     __destructor& operator=(__destructor&&) = default;                         \
                                                                                \
   protected:                                                                   \
     inline _LIBCPP_INLINE_VISIBILITY                                           \
     destroy                                                                    \
   }
 
 _LIBCPP_VARIANT_DESTRUCTOR(
     _Trait::_TriviallyAvailable,
     ~__destructor() = default;,
-    void __destroy() noexcept { this->__index = __variant_npos; });
+    void __destroy() noexcept { this->__index = __variant_npos<__index_t>; });
 
 _LIBCPP_VARIANT_DESTRUCTOR(
     _Trait::_Available,
     ~__destructor() { __destroy(); },
     void __destroy() noexcept {
       if (!this->valueless_by_exception()) {
         __visitation::__base::__visit_alt(
             [](auto& __alt) noexcept {
               using __alt_type = decay_t<decltype(__alt)>;
               __alt.~__alt_type();
             },
             *this);
       }
-      this->__index = __variant_npos;
+      this->__index = __variant_npos<__index_t>;
     });
 
 _LIBCPP_VARIANT_DESTRUCTOR(
     _Trait::_Unavailable,
     ~__destructor() = delete;,
     void __destroy() noexcept = delete;);
 
 #undef _LIBCPP_VARIANT_DESTRUCTOR

test/libcxx/utilities/variant/variant.variant/variant_size.pass.cpp

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <variant>
+
+// template <class ...Types> class variant;
+
+#include <limits>
+#include <type_traits>
+#include <utility>
+#include <variant>
+
+template <class Sequence>
+struct make_variant_imp;
+
+template <size_t ...Indices>
+struct make_variant_imp<std::integer_sequence<size_t, Indices...>> {
+  using type = std::variant<decltype((Indices, char(0)))...>;
+};
+
+template <size_t N>
+using make_variant_t = typename make_variant_imp<std::make_index_sequence<N>>::type;
+
+constexpr bool ExpectEqual =
+#ifdef _LIBCPP_ABI_VARIANT_INDEX_TYPE_OPTIMIZATION
+  false;
+#else
+  true;
+#endif
+
+template <class IndexType>
+void test_index_type() {
+  using Lim = std::numeric_limits<IndexType>;
+  using T1 = make_variant_t<Lim::max() - 1>;
+  using T2 = make_variant_t<Lim::max()>;
+  static_assert((sizeof(T1) == sizeof(T2)) == ExpectEqual, "");
+}
+
+template <class IndexType>
+void test_index_internals() {
+  using Lim = std::numeric_limits<IndexType>;
+  static_assert(std::__choose_index_type(Lim::max() -1) !=
+                std::__choose_index_type(Lim::max()), "");
+  static_assert(std::is_same_v<
+      std::__variant_index_t<Lim::max()-1>,
+      std::__variant_index_t<Lim::max()>
+    > == ExpectEqual, "");
+  using IndexT = std::__variant_index_t<Lim::max()-1>;
+  using IndexLim = std::numeric_limits<IndexT>;
+  static_assert(std::__variant_npos<IndexT> == IndexLim::max(), "");
+}
+
+int main() {
+  test_index_type<unsigned char>();
+  // This won't compile due to template depth issues.
+  //test_index_type<unsigned short>();
+  test_index_internals<unsigned char>();
+  test_index_internals<unsigned short>();
+}