-- >8 --
Subject: [PATCH] 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 <jwak...@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
CPTK_TYPE_PACK_ELEMENT.
* 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 TRAIT_TYPE_TYPE1.
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 TRAIT_TYPE_TYPE1.
libstdc++-v3/ChangeLog:
* include/bits/utility.h (_Nth_type): Conditionally define in
terms of __type_pack_element if available.
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.
---
gcc/cp/cp-trait.def | 1 +
gcc/cp/cp-tree.h | 2 +-
gcc/cp/cxx-pretty-print.cc | 17 +++++--
gcc/cp/parser.cc | 46 +++++++++++++++----
gcc/cp/pt.cc | 8 +++-
gcc/cp/semantics.cc | 39 +++++++++++++++-
gcc/cp/tree.cc | 10 ++--
gcc/cp/typeck.cc | 2 +-
gcc/testsuite/g++.dg/ext/type_pack_element1.C | 19 ++++++++
gcc/testsuite/g++.dg/ext/type_pack_element2.C | 14 ++++++
gcc/testsuite/g++.dg/ext/type_pack_element3.C | 22 +++++++++
libstdc++-v3/include/bits/utility.h | 6 +++
12 files changed, 165 insertions(+), 21 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/ext/type_pack_element1.C
create mode 100644 gcc/testsuite/g++.dg/ext/type_pack_element2.C
create mode 100644 gcc/testsuite/g++.dg/ext/type_pack_element3.C
diff --git a/gcc/cp/cp-trait.def b/gcc/cp/cp-trait.def
index 823899a26c5..63f6b101eeb 100644
--- a/gcc/cp/cp-trait.def
+++ b/gcc/cp/cp-trait.def
@@ -89,6 +89,7 @@ DEFTRAIT_TYPE (REMOVE_CV, "__remove_cv", 1)
DEFTRAIT_TYPE (REMOVE_REFERENCE, "__remove_reference", 1)
DEFTRAIT_TYPE (REMOVE_CVREF, "__remove_cvref", 1)
DEFTRAIT_TYPE (UNDERLYING_TYPE, "__underlying_type", 1)
+DEFTRAIT_TYPE (TYPE_PACK_ELEMENT, "__type_pack_element", -1)
/* These traits yield a type pack, not a type, and are represented by
cp_parser_trait as a special BASES tree instead of a TRAIT_TYPE tree.
*/
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 1f4967c2ba0..f3cc2c5874c 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -7764,7 +7764,7 @@ extern tree finish_decltype_type (tree,
bool, tsubst_flags_t);
extern tree fold_builtin_is_corresponding_member (location_t, int, tree
*);
extern tree fold_builtin_is_pointer_inverconvertible_with_class
(location_t, int, tree *);
extern tree finish_trait_expr (location_t, enum
cp_trait_kind, tree, tree);
-extern tree finish_trait_type (enum cp_trait_kind,
tree, tree);
+extern tree finish_trait_type (enum cp_trait_kind,
tree, tree, tsubst_flags_t);
extern tree build_lambda_expr (void);
extern tree build_lambda_object (tree);
extern tree begin_lambda_type (tree);
diff --git a/gcc/cp/cxx-pretty-print.cc b/gcc/cp/cxx-pretty-print.cc
index 8ca1b8f234a..07a0406e491 100644
--- a/gcc/cp/cxx-pretty-print.cc
+++ b/gcc/cp/cxx-pretty-print.cc
@@ -2625,8 +2625,16 @@ pp_cxx_trait (cxx_pretty_printer *pp, tree t)
#undef DEFTRAIT
}
- pp_cxx_left_paren (pp);
- pp->type_id (type1);
+ if (kind == CPTK_TYPE_PACK_ELEMENT)
+ {
+ pp_cxx_begin_template_argument_list (pp);
+ pp->expression (type1);
+ }
+ else
+ {
+ pp_cxx_left_paren (pp);
+ pp->type_id (type1);
+ }
if (type2)
{
if (TREE_CODE (type2) != TREE_LIST)
@@ -2641,7 +2649,10 @@ pp_cxx_trait (cxx_pretty_printer *pp, tree t)
pp->type_id (TREE_VALUE (arg));
}
}
- pp_cxx_right_paren (pp);
+ if (kind == CPTK_TYPE_PACK_ELEMENT)
+ pp_cxx_end_template_argument_list (pp);
+ else
+ pp_cxx_right_paren (pp);
}
// requires-clause:
diff --git a/gcc/cp/parser.cc b/gcc/cp/parser.cc
index 8b1658decba..0a88d83d955 100644
--- a/gcc/cp/parser.cc
+++ b/gcc/cp/parser.cc
@@ -10683,9 +10683,9 @@ cp_parser_expression (cp_parser* parser, cp_id_kind
* pidk,
static cp_expr
cp_parser_constant_expression (cp_parser* parser,
- int allow_non_constant_p,
- bool *non_constant_p,
- bool strict_p)
+ int allow_non_constant_p /* = 0 */,
+ bool *non_constant_p /* = NULL */,
+ bool strict_p /* = false */)
{
bool saved_integral_constant_expression_p;
bool saved_allow_non_integral_constant_expression_p;
@@ -10912,12 +10912,25 @@ cp_parser_trait (cp_parser* parser, enum rid
keyword)
cp_lexer_consume_token (parser->lexer);
matching_parens parens;
- parens.require_open (parser);
- {
- type_id_in_expr_sentinel s (parser);
- type1 = cp_parser_type_id (parser);
- }
+ /* Unlike the other built-in traits, __type_pack_element is unique in
that
+ it takes an expression as its first argument and it uses template-id
+ syntax instead of function call syntax (for compatibility with Clang).
+ We special case these properties of __type_pack_element here and
elsewhere.
+
+ TODO: Generalize the trait infrastructure so that __type_pack_element
+ is no longer a special case. */
+ if (kind == CPTK_TYPE_PACK_ELEMENT)
+ {
+ cp_parser_require (parser, CPP_LESS, RT_LESS);
+ type1 = cp_parser_constant_expression (parser);
+ }
+ else
+ {
+ parens.require_open (parser);
+ type_id_in_expr_sentinel s (parser);
+ type1 = cp_parser_type_id (parser);
+ }
if (type1 == error_mark_node)
return error_mark_node;
@@ -10953,7 +10966,20 @@ cp_parser_trait (cp_parser* parser, enum rid
keyword)
}
location_t finish_loc = cp_lexer_peek_token (parser->lexer)->location;
- parens.require_close (parser);
+ if (kind == CPTK_TYPE_PACK_ELEMENT)
+ {
+ /* As in cp_parser_enclosed_template_argument_list, a trailing
+ '>>' here is considered to be two separate '>' tokens. */
+ if (cp_lexer_next_token_is (parser->lexer, CPP_RSHIFT))
+ {
+ cp_token *token = cp_lexer_peek_token (parser->lexer);
+ token->type = CPP_GREATER;
+ }
+ else
+ cp_parser_require (parser, CPP_GREATER, RT_GREATER);
+ }
+ else
+ parens.require_close (parser);
/* Construct a location of the form:
__is_trivially_copyable(_Tp)
@@ -10971,7 +10997,7 @@ cp_parser_trait (cp_parser* parser, enum rid
keyword)
return cp_expr (finish_bases (type1, true), trait_loc);
default:
if (type)
- return finish_trait_type (kind, type1, type2);
+ return finish_trait_type (kind, type1, type2, tf_warning_or_error);
else
return finish_trait_expr (trait_loc, kind, type1, type2);
}
diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
index cbe5898b553..2e83970a252 100644
--- a/gcc/cp/pt.cc
+++ b/gcc/cp/pt.cc
@@ -16576,9 +16576,13 @@ tsubst (tree t, tree args, tsubst_flags_t complain,
tree in_decl)
case TRAIT_TYPE:
{
- tree type1 = tsubst (TRAIT_TYPE_TYPE1 (t), args, complain, in_decl);
+ tree type1 = TRAIT_TYPE_TYPE1 (t);
+ if (TRAIT_TYPE_KIND (t) != CPTK_TYPE_PACK_ELEMENT)
+ type1 = tsubst (type1, args, complain, in_decl);
+ else
+ type1 = tsubst_copy_and_build (type1, args, complain, in_decl);
tree type2 = tsubst (TRAIT_TYPE_TYPE2 (t), args, complain, in_decl);
- type = finish_trait_type (TRAIT_TYPE_KIND (t), type1, type2);
+ type = finish_trait_type (TRAIT_TYPE_KIND (t), type1, type2,
complain);
return cp_build_qualified_type (type,
cp_type_quals (t) | cp_type_quals
(type),
complain | tf_ignore_bad_quals);
diff --git a/gcc/cp/semantics.cc b/gcc/cp/semantics.cc
index ef5bf2430b1..af9edf59b3b 100644
--- a/gcc/cp/semantics.cc
+++ b/gcc/cp/semantics.cc
@@ -4457,6 +4457,36 @@ finish_underlying_type (tree type)
return underlying_type;
}
+/* Implement the __type_pack_element keyword: Return the type
+ at index IDX within TYPES. */
+
+static tree
+finish_type_pack_element (tree idx, tree types, tsubst_flags_t complain)
+{
+ idx = maybe_constant_value (idx);
+ if (TREE_CODE (idx) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (idx)))
+ {
+ if (complain & tf_error)
+ error ("%<__type_pack_element%> index is not an integral constant");
+ return error_mark_node;
+ }
+ HOST_WIDE_INT val = tree_to_shwi (idx);
+ if (val < 0)
+ {
+ if (complain & tf_error)
+ error ("%<__type_pack_element%> index is negative");
+ return error_mark_node;
+ }
+ tree result = chain_index (val, types);
+ if (!result)
+ {
+ if (complain & tf_error)
+ error ("%<__type_pack_element%> index is out of range");
+ return error_mark_node;
+ }
+ return TREE_VALUE (result);
+}
+
/* Implement the __direct_bases keyword: Return the direct base classes
of type. */
@@ -12213,7 +12243,8 @@ finish_trait_expr (location_t loc, cp_trait_kind
kind, tree type1, tree type2)
/* Process a trait type. */
tree
-finish_trait_type (cp_trait_kind kind, tree type1, tree type2)
+finish_trait_type (cp_trait_kind kind, tree type1, tree type2,
+ tsubst_flags_t complain)
{
if (type1 == error_mark_node
|| type2 == error_mark_node)
@@ -12237,17 +12268,23 @@ finish_trait_type (cp_trait_kind kind, tree type1,
tree type2)
{
case CPTK_UNDERLYING_TYPE:
return finish_underlying_type (type1);
+
case CPTK_REMOVE_CV:
return cv_unqualified (type1);
+
case CPTK_REMOVE_REFERENCE:
if (TYPE_REF_P (type1))
type1 = TREE_TYPE (type1);
return type1;
+
case CPTK_REMOVE_CVREF:
if (TYPE_REF_P (type1))
type1 = TREE_TYPE (type1);
return cv_unqualified (type1);
+ case CPTK_TYPE_PACK_ELEMENT:
+ return finish_type_pack_element (type1, type2, complain);
+
#define DEFTRAIT_EXPR(CODE, NAME, ARITY) \
case CPTK_##CODE:
#include "cp-trait.def"
diff --git a/gcc/cp/tree.cc b/gcc/cp/tree.cc
index faf01616f87..d834a0fd38b 100644
--- a/gcc/cp/tree.cc
+++ b/gcc/cp/tree.cc
@@ -1792,14 +1792,18 @@ strip_typedefs (tree t, bool *remove_attributes /* =
NULL */,
break;
case TRAIT_TYPE:
{
- tree type1 = strip_typedefs (TRAIT_TYPE_TYPE1 (t),
- remove_attributes, flags);
+ tree type1 = TRAIT_TYPE_TYPE1 (t);
+ if (TYPE_P (type1))
+ type1 = strip_typedefs (type1, remove_attributes, flags);
+ else
+ type1 = strip_typedefs_expr (type1, remove_attributes, flags);
tree type2 = strip_typedefs (TRAIT_TYPE_TYPE2 (t),
remove_attributes, flags);
if (type1 == TRAIT_TYPE_TYPE1 (t) && type2 == TRAIT_TYPE_TYPE2 (t))
result = NULL_TREE;
else
- result = finish_trait_type (TRAIT_TYPE_KIND (t), type1, type2);
+ result = finish_trait_type (TRAIT_TYPE_KIND (t), type1, type2,
+ tf_warning_or_error);
}
break;
case TYPE_PACK_EXPANSION:
diff --git a/gcc/cp/typeck.cc b/gcc/cp/typeck.cc
index 69b1268cfec..f5548737e4c 100644
--- a/gcc/cp/typeck.cc
+++ b/gcc/cp/typeck.cc
@@ -1632,7 +1632,7 @@ structural_comptypes (tree t1, tree t2, int strict)
case TRAIT_TYPE:
if (TRAIT_TYPE_KIND (t1) != TRAIT_TYPE_KIND (t2))
return false;
- if (!same_type_p (TRAIT_TYPE_TYPE1 (t1), TRAIT_TYPE_TYPE1 (t2))
+ if (!cp_tree_equal (TRAIT_TYPE_TYPE1 (t1), TRAIT_TYPE_TYPE1 (t2))
|| !cp_tree_equal (TRAIT_TYPE_TYPE2 (t1), TRAIT_TYPE_TYPE2 (t2)))
return false;
break;
diff --git a/gcc/testsuite/g++.dg/ext/type_pack_element1.C
b/gcc/testsuite/g++.dg/ext/type_pack_element1.C
new file mode 100644
index 00000000000..46858555502
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ext/type_pack_element1.C
@@ -0,0 +1,19 @@
+// { dg-do compile { target c++11 } }
+
+using ty0 = __type_pack_element<0, int>;
+using ty0 = __type_pack_element<0, int, char>;
+using ty0 = int;
+
+using ty1 = __type_pack_element<1, int, char>;
+using ty1 = __type_pack_element<(6 - 5) * 1, int, char>;
+using ty1 = char;
+
+template<int N, class... Ts>
+using __const_type_pack_element_t = const __type_pack_element<N, Ts...>;
+
+using ty2 = __const_type_pack_element_t<2, int, char, long>;
+using ty2 = const long;
+
+template<class T> struct A { };
+using ty3 = __type_pack_element<3, int, int, int, A<int>>;
+using ty3 = A<int>;
diff --git a/gcc/testsuite/g++.dg/ext/type_pack_element2.C
b/gcc/testsuite/g++.dg/ext/type_pack_element2.C
new file mode 100644
index 00000000000..363cfa92514
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ext/type_pack_element2.C
@@ -0,0 +1,14 @@
+// { dg-do compile { target c++11 } }
+
+int p;
+
+using type = __type_pack_element<&p, int>; // { dg-error "not an integral
constant" }
+using type = __type_pack_element<1, int>; // { dg-error "out of range" }
+using type = __type_pack_element<-1, int>; // { dg-error "negative" }
+using type = __type_pack_element<2, int, char>; // { dg-error "out of
range" }
+
+template<int N, class... Ts>
+using __type_pack_element_t = __type_pack_element<N, Ts...>;
+// { dg-error "out of range" "" { target *-*-* } .-1 }
+
+using type = __type_pack_element_t<3, int, char, long>; // { dg-message
"here" }
diff --git a/gcc/testsuite/g++.dg/ext/type_pack_element3.C
b/gcc/testsuite/g++.dg/ext/type_pack_element3.C
new file mode 100644
index 00000000000..269f84f464f
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ext/type_pack_element3.C
@@ -0,0 +1,22 @@
+// { dg-do compile { target c++11 } }
+
+template<class T, T N, class... Ts, class = __type_pack_element<N, Ts...>>
+constexpr int f(int) { return 1; }
+
+template<class T, T N, class... Ts>
+constexpr int f(...) { return 2; };
+
+int p;
+
+static_assert(f<int, 0, void, char>(0) == 1, "");
+static_assert(f<int, 1, void, char>(0) == 1, "");
+static_assert(f<int, 2, void, char>(0) == 2, "");
+static_assert(f<int*, &p, void, char>(0) == 2, "");
+
+template<class T, class U> struct A;
+template<class T> struct A<T, __type_pack_element<sizeof(T), void, long>> {
};
+template struct A<char, long>;
+
+template<class T, class U> struct B;
+template<class T> struct B<T, __type_pack_element<0, T, short>> { };
+template struct B<int, int>;
diff --git a/libstdc++-v3/include/bits/utility.h
b/libstdc++-v3/include/bits/utility.h
index 6a192e27836..5d524d33b4c 100644
--- a/libstdc++-v3/include/bits/utility.h
+++ b/libstdc++-v3/include/bits/utility.h
@@ -224,6 +224,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif // C++17
#endif // C++14
+#if __has_builtin(__type_pack_element)
+ template<size_t _Np, typename... _Types>
+ struct _Nth_type
+ { using type = __type_pack_element<_Np, _Types...>; };
+#else
template<size_t _Np, typename... _Types>
struct _Nth_type
{ };
@@ -262,6 +267,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
struct _Nth_type<1, _Tp0, _Tp1, _Tp2, _Rest...>
{ using type = _Tp1; };
#endif
+#endif
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
