[Bug c++/100157] New: Support `__type_pack_element` like Clang

[Bug c++/100157] New: Support `__type_pack_element` like Clang

[vittorio.romeo at outlook dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

            Bug ID: 100157
           Summary: Support `__type_pack_element` like Clang
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vittorio.romeo at outlook dot com
  Target Milestone: ---

Clang provides a `__type_pack_element` builtin which allows efficient indexing
of parameter packs in variadic templates, and it seems that GCC has no
equivalent.

This forces users interested in minimizing compilation times to resort to
arcane implemenations such as these ones:
https://github.com/kvasir-io/mpl/blob/development/src/kvasir/mpl/sequence/lookup.hpp

A builtin like `__type_pack_element` would not only allow user code to compile
faster, but also anything inside libstdc++ that needs to index a type list
(e.g. `std::tuple_element_t`) would benefit from it.

This is the Clang test driver, to show an usage example:
https://github.com/llvm-mirror/clang/blob/master/test/SemaCXX/type_pack_element.cpp

This is the Clang pull request:
https://reviews.llvm.org/D15421

[Bug c++/100157] Support `__type_pack_element` like Clang

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |12.0
           Severity|normal                      |enhancement

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-06-29
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
GCC doesn't support template-like built-ins, but I have a patch to add a
function-like __builtin_type_pack_element(N, T...) instead. I don't like the
name "type pack element" much though. To me that doesn't really suggest
selecting an element by its index.

[Bug c++/100157] Support `__type_pack_element` like Clang

[m.cencora at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

m.cencora at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |m.cencora at gmail dot com

--- Comment #2 from m.cencora at gmail dot com ---
Please consider also adding a builtin for fetching index of type in type list.
While there are some easy implementations (like following), they are still not
very performant.

template <typename T>
constexpr auto uniqId()
{
    return __PRETTY_FUNCTION__;
}

template <typename U, unsigned N>
constexpr unsigned index_of_impl(U needle, const U (&haystack)[N])
{
    for (unsigned i = 0u; i != N; ++i)
    {
        if (haystack[i] == needle)
        {
            return i;
        }
    }
    return -1;
}

template <typename T, typename ...Ts>
constexpr auto index_of_v = index_of_impl(uniqId<T>, { uniqId<Ts>...});

using T1 = float;
using T2 = int;
struct A;
struct B;

auto c = index_of_v<A, T2, B, A, T1>;

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to m.cencora from comment #2)
> Please consider also adding a builtin for fetching index of type in type
> list.

I am already considering it and it's one of the reasons I don't like the name
"type pack element". That name isn't easily extensible to the reverse case.

I would prefer a pair of similar names involving "type at index" and "index of
type" or something like that. Or "index to type" and "tpe to index".

> While there are some easy implementations (like following), they are still
> not very performant.

The uses in the standard library also require an error if the type occurs more
than once, which yours doesn't check. I intend to add a built-in that supports
both cases with a boolean flag to say whether to fail if the type is repeated.

FWIW I think __find_uniq_type_in_pack() in libstdc++'s <bits/utility.h> scales
better than yours (and checks for uniqueness).

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #3)
> I would prefer a pair of similar names involving "type at index" and "index
> of type" or something like that. Or "index to type" and "tpe to index".

Another option I considered is to just use the same name and make the same
built-in support both cases. If the first argument is an integer, return a
type, if the first argument is a type, return an integer. But that's a bit
subtle, and is complicated by wanting the boolean flag for the type-to-index
case.

[Bug c++/100157] Support `__type_pack_element` like Clang

[m.cencora at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #5 from m.cencora at gmail dot com ---
Yeah, __is_same builtin beats custom unique-id comparisons, but it is available
only since gcc-10 so unavailable for me.

Recently I discovered this one (only works for unique types), and it is twice
as fast as __is_same in my scenarios (I guess mainly due to memoization):

template <typename T>
struct indexed_type
{
   unsigned idx;
};

template <typename ...Ts>
struct indexed_type_list : indexed_type<Ts>...
{
   constexpr indexed_type_list(unsigned i = 0)
     : indexed_type<Ts>{i++}...
   {}
};

template <typename ...Ts>
constexpr indexed_type_list<Ts...> indexed_type_list_instance;


template <typename T, typename ...Ts>
constexpr auto index_of =
static_cast<indexed_type<T>>(indexed_type_list_instance<Ts...>).idx;

Anyway, thanks for working on this topic!

[Bug c++/100157] Support `__type_pack_element` like Clang

[vittorio.romeo at outlook dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #6 from Vittorio Romeo <vittorio.romeo at outlook dot com> ---
Thank you, Jonathan, for looking into this. I feel like it might be worthwhile
to keep the same name as Clang for compatibility, or maybe talk to some Clang
developers and see if there can be an agreement on naming and design that works
for both compilers -- would be nice to have something that works for both GCC
and Clang in the same way.

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to m.cencora from comment #5)
> Yeah, __is_same builtin beats custom unique-id comparisons, but it is
> available only since gcc-10 so unavailable for me.

GCC has had __is_same_as since 6.1 though. Much later, __is_same was added as
another spelling for it (PR 92271).

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Vittorio Romeo from comment #6)
> worthwhile to keep the same name as Clang for compatibility,

No, that's not an option. Clang's is a built-in template, GCC's can't be (it
would require considerable internal reworking to support that).

That's also why we have __integer_pack(N)... instead of __make_integer_seq<>.

Since GCC's built-in has to use different syntax, it would be a disaster to use
the same name.

#if __has_builtin(__type_pack_element)
// now what? is it a template or a function?
#endif

[Bug c++/100157] Support `__type_pack_element` like Clang

[vittorio.romeo at outlook dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #9 from Vittorio Romeo <vittorio.romeo at outlook dot com> ---
(In reply to Jonathan Wakely from comment #8)
> (In reply to Vittorio Romeo from comment #6)
> > worthwhile to keep the same name as Clang for compatibility,
> 
> No, that's not an option. Clang's is a built-in template, GCC's can't be (it
> would require considerable internal reworking to support that).
> 
> That's also why we have __integer_pack(N)... instead of __make_integer_seq<>.
> 
> Since GCC's built-in has to use different syntax, it would be a disaster to
> use the same name.
> 
> #if __has_builtin(__type_pack_element)
> // now what? is it a template or a function?
> #endif

Got it, I didn't realize that they had to be wildly different. I guess that as
long as a library developer can wrap either under a portable macro, it should
be fine.

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
FWIW std::tuple_element_t<1000, tuple<pathologically large>> takes 97% less
memory and takes 80% less time with my patch. I just need to fix a problem with
debuginfo generation.

[Bug c++/100157] Support `__type_pack_element` like Clang

[pdimov at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

Peter Dimov <pdimov at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pdimov at gmail dot com

--- Comment #11 from Peter Dimov <pdimov at gmail dot com> ---
Just import mp11 wholesale and use mp_at_c and mp_find :-)

[Bug c++/100157] Support `__type_pack_element` like Clang

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

--- Comment #12 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:58b7dbf865b146a4e65dbda9be6df78f212c03b6

commit r14-92-g58b7dbf865b146a4e65dbda9be6df78f212c03b6
Author: Patrick Palka <ppalka@redhat.com>
Date:   Wed Apr 19 15:36:34 2023 -0400

    c++: Define built-in for std::tuple_element [PR100157]

    This adds a new built-in to replace the recursive class template
    instantiations done by traits such as std::tuple_element and
    std::variant_alternative.  The purpose is to select the Nth type from a
    list of types, e.g. __type_pack_element<1, char, int, float> is int.
    We implement it as a special kind of TRAIT_TYPE.

    For a pathological example tuple_element_t<1000, tuple<2000 types...>>
    the compilation time is reduced by more than 90% and the memory used by
    the compiler is reduced by 97%.  In realistic examples the gains will be
    much smaller, but still relevant.

    Unlike the other built-in traits, __type_pack_element uses template-id
    syntax instead of call syntax and is SFINAE-enabled, matching Clang's
    implementation.  And like the other built-in traits, it's not mangleable
    so we can't use it directly in function signatures.

    N.B. Clang seems to implement __type_pack_element as a first-class
    template that can e.g. be used as a template-template argument.  For
    simplicity we implement it in a more ad-hoc way.

    Co-authored-by: Jonathan Wakely <jwakely@redhat.com>

            PR c++/100157

    gcc/cp/ChangeLog:

            * cp-trait.def (TYPE_PACK_ELEMENT): Define.
            * cp-tree.h (finish_trait_type): Add complain parameter.
            * cxx-pretty-print.cc (pp_cxx_trait): Handle
            CPTK_TYPE_PACK_ELEMENT.
            * parser.cc (cp_parser_constant_expression): Document default
            arguments.
            (cp_parser_trait): Handle CPTK_TYPE_PACK_ELEMENT.  Pass
            tf_warning_or_error to finish_trait_type.
            * pt.cc (tsubst) <case TRAIT_TYPE>: Handle non-type first
            argument.  Pass complain to finish_trait_type.
            * semantics.cc (finish_type_pack_element): Define.
            (finish_trait_type): Add complain parameter.  Handle
            CPTK_TYPE_PACK_ELEMENT.
            * tree.cc (strip_typedefs): Handle non-type first argument.
            Pass tf_warning_or_error to finish_trait_type.
            * typeck.cc (structural_comptypes) <case TRAIT_TYPE>: Use
            cp_tree_equal instead of same_type_p for the first argument.

    libstdc++-v3/ChangeLog:

            * include/bits/utility.h (_Nth_type): Conditionally define in
            terms of __type_pack_element if available.
            * testsuite/20_util/tuple/element_access/get_neg.cc: Prune
            additional errors from the new built-in.

    gcc/testsuite/ChangeLog:

            * g++.dg/ext/type_pack_element1.C: New test.
            * g++.dg/ext/type_pack_element2.C: New test.
            * g++.dg/ext/type_pack_element3.C: New test.

[Bug c++/100157] Support `__type_pack_element` like Clang

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.0                        |13.2

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 13.1 is being released, retargeting bugs to GCC 13.2.

[Bug c++/100157] Support `__type_pack_element` like Clang

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100157

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|13.2                        |14.0

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Done for GCC 14