[gcc r12-4924] libstdc++: Optimize std::tuple_element and std::tuple_size_v

[gcc r12-4924] libstdc++: Optimize std::tuple_element and std::tuple_size_v

[Jonathan Wakely]

https://gcc.gnu.org/g:09aab7e699dcbd79fd64959cf259567bdca94022

commit r12-4924-g09aab7e699dcbd79fd64959cf259567bdca94022
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Nov 4 09:31:50 2021 +0000

    libstdc++: Optimize std::tuple_element and std::tuple_size_v
    
    This reduces the number of class template instantiations needed for code
    using tuples, by reusing _Nth_type in tuple_element and specializing
    tuple_size_v for tuple, pair and array (and const-qualified versions of
    them).
    
    Also define the _Nth_type primary template as a complete type (but with
    no nested 'type' member).  This avoids "invalid use of incomplete type"
    errors for out-of-range specializations of tuple_element. Those errors
    would probably be confusing and unhelpful for users. We already have
    a user-friendly static assert in tuple_element itself.
    
    Also ensure that tuple_size_v is available whenever tuple_size is (as
    proposed by LWG 3387). We already do that for tuple_element_t.
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/stl_pair.h (tuple_size_v): Define partial
            specializations for std::pair.
            * include/bits/utility.h (_Nth_type): Move definition here
            and define primary template.
            (tuple_size_v): Move definition here.
            * include/std/array (tuple_size_v): Define partial
            specializations for std::array.
            * include/std/tuple (tuple_size_v): Move primary template to
            <bits/utility.h>.  Define partial specializations for
            std::tuple.
            (tuple_element): Change definition to use _Nth_type.
            * include/std/variant (_Nth_type): Move to <bits/utility.h>.
            (variant_alternative, variant): Adjust qualification of
            _Nth_type.
            * testsuite/20_util/tuple/element_access/get_neg.cc: Prune
            additional errors from _Nth_type.

Diff:
---
 libstdc++-v3/include/bits/stl_pair.h               |  8 +++
 libstdc++-v3/include/bits/utility.h                | 51 ++++++++++++++++++-
 libstdc++-v3/include/std/array                     |  8 +++
 libstdc++-v3/include/std/tuple                     | 39 +++++----------
 libstdc++-v3/include/std/variant                   | 58 ++--------------------
 .../20_util/tuple/element_access/get_neg.cc        |  1 +
 6 files changed, 84 insertions(+), 81 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_pair.h b/libstdc++-v3/include/bits/stl_pair.h
index 5b400daf97f..6081e0c7fe9 100644
--- a/libstdc++-v3/include/bits/stl_pair.h
+++ b/libstdc++-v3/include/bits/stl_pair.h
@@ -771,6 +771,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     struct tuple_element<1, pair<_Tp1, _Tp2>>
     { typedef _Tp2 type; };
 
+#if __cplusplus >= 201703L
+  template<typename _Tp1, typename _Tp2>
+    inline constexpr size_t tuple_size_v<pair<_Tp1, _Tp2>> = 2;
+
+  template<typename _Tp1, typename _Tp2>
+    inline constexpr size_t tuple_size_v<const pair<_Tp1, _Tp2>> = 2;
+#endif
+
   /// @cond undocumented
   template<size_t _Int>
     struct __pair_get;
diff --git a/libstdc++-v3/include/bits/utility.h b/libstdc++-v3/include/bits/utility.h
index fce52a4530d..c9ffa008217 100644
--- a/libstdc++-v3/include/bits/utility.h
+++ b/libstdc++-v3/include/bits/utility.h
@@ -70,6 +70,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     struct tuple_size<const volatile __enable_if_has_tuple_size<_Tp>>
     : public tuple_size<_Tp> { };
 
+#if __cplusplus >= 201703L
+  template<typename _Tp>
+    inline constexpr size_t tuple_size_v = tuple_size<_Tp>::value;
+#endif
+
   /// Gives the type of the ith element of a given tuple type.
   template<size_t __i, typename _Tp>
     struct tuple_element;
@@ -97,8 +102,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 
 #if __cplusplus >= 201402L
-// The standard says this macro and alias template should be in <tuple>
-// but we define them here, to be available in <utility> and <array> too.
+// The standard says this macro and alias template should be in <tuple> but we
+// we define them here, to be available in <array>, <utility> and <ranges> too.
+// _GLIBCXX_RESOLVE_LIB_DEFECTS
+// 3378. tuple_size_v/tuple_element_t should be available when
+//       tuple_size/tuple_element are
 #define __cpp_lib_tuple_element_t 201402L
 
   template<size_t __i, typename _Tp>
@@ -195,6 +203,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif // C++17
 #endif // C++14
 
+  template<size_t _Np, typename... _Types>
+    struct _Nth_type
+    { };
+
+  template<typename _Tp0, typename... _Rest>
+    struct _Nth_type<0, _Tp0, _Rest...>
+    { using type = _Tp0; };
+
+  template<typename _Tp0, typename _Tp1, typename... _Rest>
+    struct _Nth_type<1, _Tp0, _Tp1, _Rest...>
+    { using type = _Tp1; };
+
+  template<typename _Tp0, typename _Tp1, typename _Tp2, typename... _Rest>
+    struct _Nth_type<2, _Tp0, _Tp1, _Tp2, _Rest...>
+    { using type = _Tp2; };
+
+  template<size_t _Np, typename _Tp0, typename _Tp1, typename _Tp2,
+	   typename... _Rest>
+#if __cpp_concepts
+    requires (_Np >= 3)
+#endif
+    struct _Nth_type<_Np, _Tp0, _Tp1, _Tp2, _Rest...>
+    : _Nth_type<_Np - 3, _Rest...>
+    { };
+
+#if ! __cpp_concepts // Need additional specializations to avoid ambiguities.
+  template<typename _Tp0, typename _Tp1, typename... _Rest>
+    struct _Nth_type<0, _Tp0, _Tp1, _Rest...>
+    { using type = _Tp0; };
+
+  template<typename _Tp0, typename _Tp1, typename _Tp2, typename... _Rest>
+    struct _Nth_type<0, _Tp0, _Tp1, _Tp2, _Rest...>
+    { using type = _Tp0; };
+
+  template<typename _Tp0, typename _Tp1, typename _Tp2, typename... _Rest>
+    struct _Nth_type<1, _Tp0, _Tp1, _Tp2, _Rest...>
+    { using type = _Tp1; };
+#endif
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 
diff --git a/libstdc++-v3/include/std/array b/libstdc++-v3/include/std/array
index 3e12d35157c..413f8e2be01 100644
--- a/libstdc++-v3/include/std/array
+++ b/libstdc++-v3/include/std/array
@@ -481,6 +481,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       using type = _Tp;
     };
 
+#if __cplusplus >= 201703L
+  template<typename _Tp, size_t _Nm>
+    inline constexpr size_t tuple_size_v<array<_Tp, _Nm>> = _Nm;
+
+  template<typename _Tp, size_t _Nm>
+    inline constexpr size_t tuple_size_v<const array<_Tp, _Nm>> = _Nm;
+#endif
+
   template<typename _Tp, size_t _Nm>
     struct __is_tuple_like_impl<array<_Tp, _Nm>> : true_type
     { };
diff --git a/libstdc++-v3/include/std/tuple b/libstdc++-v3/include/std/tuple
index aaee0b8826a..b82cdf12569 100644
--- a/libstdc++-v3/include/std/tuple
+++ b/libstdc++-v3/include/std/tuple
@@ -1344,36 +1344,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     struct tuple_size<tuple<_Elements...>>
     : public integral_constant<size_t, sizeof...(_Elements)> { };
 
-#if __cplusplus > 201402L
-  template <typename _Tp>
-    inline constexpr size_t tuple_size_v = tuple_size<_Tp>::value;
-#endif
+#if __cplusplus >= 201703L
+  template<typename... _Types>
+    inline constexpr size_t tuple_size_v<tuple<_Types>>
+      = sizeof...(_Types);
 
-  /**
-   * Recursive case for tuple_element: strip off the first element in
-   * the tuple and retrieve the (i-1)th element of the remaining tuple.
-   */
-  template<size_t __i, typename _Head, typename... _Tail>
-    struct tuple_element<__i, tuple<_Head, _Tail...> >
-    : tuple_element<__i - 1, tuple<_Tail...> > { };
+  template<typename... _Types>
+    inline constexpr size_t tuple_size_v<const tuple<_Types>>
+      = sizeof...(_Types);
+#endif
 
-  /**
-   * Basis case for tuple_element: The first element is the one we're seeking.
-   */
-  template<typename _Head, typename... _Tail>
-    struct tuple_element<0, tuple<_Head, _Tail...> >
+  /// Trait to get the Ith element type from a tuple.
+  template<size_t __i, typename... _Types>
+    struct tuple_element<__i, tuple<_Types...>>
     {
-      typedef _Head type;
-    };
+      static_assert(__i < sizeof...(_Types), "tuple index must be in range");
 
-  /**
-   * Error case for tuple_element: invalid index.
-   */
-  template<size_t __i>
-    struct tuple_element<__i, tuple<>>
-    {
-      static_assert(__i < tuple_size<tuple<>>::value,
-	  "tuple index must be in range");
+      using type = typename _Nth_type<__i, _Types...>::type;
     };
 
   template<size_t __i, typename _Head, typename... _Tail>
diff --git a/libstdc++-v3/include/std/variant b/libstdc++-v3/include/std/variant
index c4c307b7bb2..993ce3dba91 100644
--- a/libstdc++-v3/include/std/variant
+++ b/libstdc++-v3/include/std/variant
@@ -54,51 +54,6 @@ namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
-namespace __detail
-{
-namespace __variant
-{
-  template<size_t _Np, typename... _Types>
-    struct _Nth_type;
-
-  template<typename _Tp0, typename... _Rest>
-    struct _Nth_type<0, _Tp0, _Rest...>
-    { using type = _Tp0; };
-
-  template<typename _Tp0, typename _Tp1, typename... _Rest>
-    struct _Nth_type<1, _Tp0, _Tp1, _Rest...>
-    { using type = _Tp1; };
-
-  template<typename _Tp0, typename _Tp1, typename _Tp2, typename... _Rest>
-    struct _Nth_type<2, _Tp0, _Tp1, _Tp2, _Rest...>
-    { using type = _Tp2; };
-
-  template<size_t _Np, typename _Tp0, typename _Tp1, typename _Tp2,
-	   typename... _Rest>
-#if __cpp_concepts
-    requires (_Np >= 3)
-#endif
-    struct _Nth_type<_Np, _Tp0, _Tp1, _Tp2, _Rest...>
-    : _Nth_type<_Np - 3, _Rest...>
-    { };
-
-#if ! __cpp_concepts // Need additional specializations to avoid ambiguities.
-  template<typename _Tp0, typename _Tp1, typename... _Rest>
-    struct _Nth_type<0, _Tp0, _Tp1, _Rest...>
-    { using type = _Tp0; };
-
-  template<typename _Tp0, typename _Tp1, typename _Tp2, typename... _Rest>
-    struct _Nth_type<0, _Tp0, _Tp1, _Tp2, _Rest...>
-    { using type = _Tp0; };
-
-  template<typename _Tp0, typename _Tp1, typename _Tp2, typename... _Rest>
-    struct _Nth_type<1, _Tp0, _Tp1, _Tp2, _Rest...>
-    { using type = _Tp1; };
-#endif
-
-} // namespace __variant
-} // namespace __detail
-
 #if __cplusplus >= 202002L && __cpp_concepts
 // P2231R1 constexpr needs constexpr unions and constrained destructors.
 # define __cpp_lib_variant 202106L
@@ -145,8 +100,7 @@ namespace __variant
     {
       static_assert(_Np < sizeof...(_Types));
 
-      using type
-	= typename __detail::__variant::_Nth_type<_Np, _Types...>::type;
+      using type = typename _Nth_type<_Np, _Types...>::type;
     };
 
   template<size_t _Np, typename _Variant>
@@ -1442,8 +1396,7 @@ namespace __variant
 	  = __detail::__variant::__accepted_index<_Tp, variant>::value;
 
       template<size_t _Np, typename = enable_if_t<(_Np < sizeof...(_Types))>>
-	using __to_type
-	  = typename __detail::__variant::_Nth_type<_Np, _Types...>::type;
+	using __to_type = typename _Nth_type<_Np, _Types...>::type;
 
       template<typename _Tp, typename = enable_if_t<__not_self<_Tp>>>
 	using __accepted_type = __to_type<__accepted_index<_Tp>>;
@@ -1580,7 +1533,7 @@ namespace __variant
 	emplace(_Args&&... __args)
 	{
 	  namespace __variant = std::__detail::__variant;
-	  using type = typename __variant::_Nth_type<_Np, _Types...>::type;
+	  using type = typename _Nth_type<_Np, _Types...>::type;
 	  // Provide the strong exception-safety guarantee when possible,
 	  // to avoid becoming valueless.
 	  if constexpr (is_nothrow_constructible_v<type, _Args...>)
@@ -1620,7 +1573,7 @@ namespace __variant
 	emplace(initializer_list<_Up> __il, _Args&&... __args)
 	{
 	  namespace __variant = std::__detail::__variant;
-	  using type = typename __variant::_Nth_type<_Np, _Types...>::type;
+	  using type = typename _Nth_type<_Np, _Types...>::type;
 	  // Provide the strong exception-safety guarantee when possible,
 	  // to avoid becoming valueless.
 	  if constexpr (is_nothrow_constructible_v<type,
@@ -1803,8 +1756,7 @@ namespace __variant
 	  constexpr size_t __max = 11; // "These go to eleven."
 
 	  // The type of the first variant in the pack.
-	  using _V0
-	    = typename __detail::__variant::_Nth_type<0, _Variants...>::type;
+	  using _V0 = typename _Nth_type<0, _Variants...>::type;
 	  // The number of alternatives in that first variant.
 	  constexpr auto __n = variant_size_v<remove_reference_t<_V0>>;
 
diff --git a/libstdc++-v3/testsuite/20_util/tuple/element_access/get_neg.cc b/libstdc++-v3/testsuite/20_util/tuple/element_access/get_neg.cc
index 225bb6245a6..113a7fd62de 100644
--- a/libstdc++-v3/testsuite/20_util/tuple/element_access/get_neg.cc
+++ b/libstdc++-v3/testsuite/20_util/tuple/element_access/get_neg.cc
@@ -60,3 +60,4 @@ test03()
 }
 
 // { dg-error "tuple index must be in range" "" { target *-*-* } 0 }
+// { dg-prune-output "no type named 'type' in .*_Nth_type" }