Re: [committed] libstdc++: Optimize std::tuple_element and std::tuple_size_v

[Patrick Palka <ppalka@redhat.com>]

On Thu, Nov 4, 2021 at 2:34 PM Jonathan Wakely via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Tested powerpc64le-linux, committed to trunk.
>
>
> 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.
> ---
>  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;
> +#if __cplusplus >= 201703L
> +  template<typename... _Types>
> +    inline constexpr size_t tuple_size_v<tuple<_Types>>

Missing ... after _Types?

> +      = sizeof...(_Types);
> +
> +  template<typename... _Types>
> +    inline constexpr size_t tuple_size_v<const tuple<_Types>>

Same here.  (I guess now's a good time to fix PR100652!)

> +      = sizeof...(_Types);
>  #endif
>
> -  /**
> -   * 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...> > { };
> -
> -  /**
> -   * 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" }
> --
> 2.31.1
>