From patchwork Mon Apr 18 13:59:36 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Iain Sandoe X-Patchwork-Id: 53010 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 734DF385842E for ; Mon, 18 Apr 2022 14:00:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 734DF385842E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1650290459; bh=eUuBUCJ3vOMkXlA1MoWKjgaByVN+m7Gu3z0OOyqTtG0=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=ZOABSqfUnvLwHGCYswcqh/HzrvqB1h0lcfKK1uUu04BNJD8wwuT8HcUkdd2CTL+1T Z3BR8GuiRfMHgS0HCSZayJd4/X97k/hAwn15g+mNuWkYOx+XTPfUAnZfAYPTWYTVQD m4IC96snXlM5FWekB/HmhfXX/hCbXkCUW+QbJXV4= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wr1-x42a.google.com (mail-wr1-x42a.google.com [IPv6:2a00:1450:4864:20::42a]) by sourceware.org (Postfix) with ESMTPS id EE3D13858D28 for ; Mon, 18 Apr 2022 13:59:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EE3D13858D28 Received: by mail-wr1-x42a.google.com with SMTP id x18so10825025wrc.0 for ; Mon, 18 Apr 2022 06:59:47 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :mime-version:content-transfer-encoding; bh=eUuBUCJ3vOMkXlA1MoWKjgaByVN+m7Gu3z0OOyqTtG0=; b=IFLb3ezk4CORq2Au+cIaOw6rWpTes0Hsx06ixcI3J7iwj8jlvK6Ejj8PBXG6qpn6/P R8Ognwjaw8Gve+o7PYoUffPaTfHDbLIcEYaKjOLGy/uS2OzJJUosvPYfIX2Ns2qJKV/b EUs7/ky+Dz5a8E5O2HhO4T1uCFrj3250QzUOjV4fuf3pp04ImuMppYVxZK3huj26jnva 7xXPHClPuBSOxyunk7fqoJ1Tr9e+JGNaJWHHR0sjscg/EI8Sie4tB8bAoaBXJVp8m85E LN4CFoVZSW/zLV+n2pUjaEQbHj8fP4LdtpqQQhURd4+hzAnm3Gz26Pim2ApjNasxT94N FneA== X-Gm-Message-State: AOAM531gad2Oa2BYn4HS7VrsW4c0veQo1pyvQwEv7EZSeVTqusV/JRE/ 9D0gtvjKdUBQPAk8u2uWEdd14jMPt4Q= X-Google-Smtp-Source: ABdhPJzi7aVG3yM89XmuOGt5Aq49gIO4+BGF++qGnqKfg1JZnsQVsuvjYjFVaUC00zjE+DFCwzxrww== X-Received: by 2002:a5d:588c:0:b0:20a:9e33:8e5b with SMTP id n12-20020a5d588c000000b0020a9e338e5bmr2035153wrf.79.1650290385678; Mon, 18 Apr 2022 06:59:45 -0700 (PDT) Received: from localhost.localdomain (host81-138-1-83.in-addr.btopenworld.com. [81.138.1.83]) by smtp.gmail.com with ESMTPSA id o11-20020a05600c4fcb00b00391447f7fd4sm10605881wmq.24.2022.04.18.06.59.44 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 18 Apr 2022 06:59:45 -0700 (PDT) X-Google-Original-From: Iain Sandoe To: gcc-patches@gcc.gnu.org Subject: [PATCH] c++, coroutines: Avoid expanding within templates [PR103868] Date: Mon, 18 Apr 2022 14:59:36 +0100 Message-Id: <20220418135936.24757-1-iain@sandoe.co.uk> X-Mailer: git-send-email 2.24.3 (Apple Git-128) MIME-Version: 1.0 X-Spam-Status: No, score=-8.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Iain Sandoe via Gcc-patches From: Iain Sandoe Reply-To: iain@sandoe.co.uk Cc: Iain Sandoe , nathan@acm.org Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" From: Nathan Sidwell This is a forward-port of a patch by Nathan (against 10.x) which fixes an open PR. We are ICEing because we ended up tsubst_copying something that had already been tsubst, leading to an assert failure (mostly such repeated tsubsting is harmless). We had a non-dependent co_await in a non-dependent-type template fn, so we processed it at definition time, and then reprocessed at instantiation time. We fix this here by deferring substitution while processing templates. Additional observations (for a better future fix, in the GCC13 timescale): Exprs only have dependent type if at least one operand is dependent which was what the current code was intending to do. Coroutines have the additional wrinkle, that the current fn's type is an implicit operand. So, if the coroutine function's type is not dependent, and the operand is not dependent, we should determine the type of the co_await expression using the DEPENDENT_EXPR wrapper machinery. That allows us to determine the subexpression type, but leave its operand unchanged and then instantiate it later. Tested on x86_64-darwin (it does also fix the original testcase, but that is far too time-consuming for the testsuite). OK for master? / backports? (when?) thanks, Iain PR c++/103868 gcc/cp/ChangeLog: * coroutines.cc (finish_co_await_expr): Do not process non-dependent coroutine expressions at template definition time. (finish_co_yield_expr): Likewise. (finish_co_return_stmt): Likewise. gcc/testsuite/ChangeLog: * g++.dg/coroutines/pr103868.C: New test. Co-Authored-by: Iain Sandoe --- gcc/cp/coroutines.cc | 18 +- gcc/testsuite/g++.dg/coroutines/pr103868.C | 7390 ++++++++++++++++++++ 2 files changed, 7396 insertions(+), 12 deletions(-) create mode 100644 gcc/testsuite/g++.dg/coroutines/pr103868.C diff --git a/gcc/cp/coroutines.cc b/gcc/cp/coroutines.cc index cdf6503c4d3..a9ce6e050dd 100644 --- a/gcc/cp/coroutines.cc +++ b/gcc/cp/coroutines.cc @@ -1148,10 +1148,8 @@ finish_co_await_expr (location_t kw, tree expr) extraneous warnings during substitution. */ suppress_warning (current_function_decl, OPT_Wreturn_type); - /* If we don't know the promise type, we can't proceed, build the - co_await with the expression unchanged. */ - tree functype = TREE_TYPE (current_function_decl); - if (dependent_type_p (functype) || type_dependent_expression_p (expr)) + /* Defer processing when we have dependent types. */ + if (processing_template_decl) { tree aw_expr = build5_loc (kw, CO_AWAIT_EXPR, unknown_type_node, expr, NULL_TREE, NULL_TREE, NULL_TREE, @@ -1222,10 +1220,8 @@ finish_co_yield_expr (location_t kw, tree expr) extraneous warnings during substitution. */ suppress_warning (current_function_decl, OPT_Wreturn_type); - /* If we don't know the promise type, we can't proceed, build the - co_await with the expression unchanged. */ - tree functype = TREE_TYPE (current_function_decl); - if (dependent_type_p (functype) || type_dependent_expression_p (expr)) + /* Defer processing when we have dependent types. */ + if (processing_template_decl) return build2_loc (kw, CO_YIELD_EXPR, unknown_type_node, expr, NULL_TREE); if (!coro_promise_type_found_p (current_function_decl, kw)) @@ -1307,10 +1303,8 @@ finish_co_return_stmt (location_t kw, tree expr) && check_for_bare_parameter_packs (expr)) return error_mark_node; - /* If we don't know the promise type, we can't proceed, build the - co_return with the expression unchanged. */ - tree functype = TREE_TYPE (current_function_decl); - if (dependent_type_p (functype) || type_dependent_expression_p (expr)) + /* Defer processing when we have dependent types. */ + if (processing_template_decl) { /* co_return expressions are always void type, regardless of the expression type. */ diff --git a/gcc/testsuite/g++.dg/coroutines/pr103868.C b/gcc/testsuite/g++.dg/coroutines/pr103868.C new file mode 100644 index 00000000000..f7b7e3bad54 --- /dev/null +++ b/gcc/testsuite/g++.dg/coroutines/pr103868.C @@ -0,0 +1,7390 @@ +// { dg-do compile } +// { dg-additional-options "-fpreprocessed -std=gnu++20 -w -fconcepts" } +// The ICE is fixed, but the reduced testcase has excess errors: +// { dg-excess-errors {concept '__indirectly_readable_impl' has multiple template parameter lists} } +namespace std { +typedef decltype(nullptr) nullptr_t; +template struct char_traits; +} // namespace std +namespace doctest { +class String { +public: + String(const char *in); +}; +namespace assertType { +enum Enum { + is_warn = 1, + is_check = 2 * is_warn, + is_require = 2 * is_check, + is_normal = 2 * is_require, + is_throws = 2 * is_normal, + is_throws_as = 2 * is_throws, + is_throws_with = 2 * is_throws_as, + is_nothrow = 2 * is_throws_with, + is_false = 2 * is_nothrow, + is_unary = 2 * is_false, + is_eq = 2 * is_unary, + is_ne = 2 * is_eq, + is_lt = 2 * is_ne, + is_gt = 2 * is_lt, + is_ge = 2 * is_gt, + is_le = 2 * is_ge, + DT_WARN = is_normal | is_warn, + DT_CHECK = is_normal | is_check, + DT_REQUIRE = is_normal | is_require, + DT_WARN_FALSE = is_normal | is_false | is_warn, + DT_CHECK_FALSE = is_normal | is_false | is_check, + DT_REQUIRE_FALSE = is_normal | is_false | is_require, + DT_WARN_THROWS = is_throws | is_warn, + DT_CHECK_THROWS = is_throws | is_check, + DT_REQUIRE_THROWS = is_throws | is_require, + DT_WARN_THROWS_AS = is_throws_as | is_warn, + DT_CHECK_THROWS_AS = is_throws_as | is_check, + DT_REQUIRE_THROWS_AS = is_throws_as | is_require, + DT_WARN_THROWS_WITH = is_throws_with | is_warn, + DT_CHECK_THROWS_WITH = is_throws_with | is_check, + DT_REQUIRE_THROWS_WITH = is_throws_with | is_require, + DT_WARN_THROWS_WITH_AS = is_throws_with | is_throws_as | is_warn, + DT_CHECK_THROWS_WITH_AS = is_throws_with | is_throws_as | is_check, + DT_REQUIRE_THROWS_WITH_AS = is_throws_with | is_throws_as | is_require, + DT_WARN_NOTHROW = is_nothrow | is_warn, + DT_CHECK_NOTHROW = is_nothrow | is_check, + DT_REQUIRE_NOTHROW = is_nothrow | is_require, + DT_WARN_EQ = is_normal | is_eq | is_warn, + DT_CHECK_EQ = is_normal | is_eq | is_check, + DT_REQUIRE_EQ = is_normal | is_eq | is_require, + DT_WARN_NE = is_normal | is_ne | is_warn, + DT_CHECK_NE = is_normal | is_ne | is_check, + DT_REQUIRE_NE = is_normal | is_ne | is_require, + DT_WARN_GT = is_normal | is_gt | is_warn, + DT_CHECK_GT = is_normal | is_gt | is_check, + DT_REQUIRE_GT = is_normal | is_gt | is_require, + DT_WARN_LT = is_normal | is_lt | is_warn, + DT_CHECK_LT = is_normal | is_lt | is_check, + DT_REQUIRE_LT = is_normal | is_lt | is_require, + DT_WARN_GE = is_normal | is_ge | is_warn, + DT_CHECK_GE = is_normal | is_ge | is_check, + DT_REQUIRE_GE = is_normal | is_ge | is_require, + DT_WARN_LE = is_normal | is_le | is_warn, + DT_CHECK_LE = is_normal | is_le | is_check, + DT_REQUIRE_LE = is_normal | is_le | is_require, + DT_WARN_UNARY = is_normal | is_unary | is_warn, + DT_CHECK_UNARY = is_normal | is_unary | is_check, + DT_REQUIRE_UNARY = is_normal | is_unary | is_require, + DT_WARN_UNARY_FALSE = is_normal | is_false | is_unary | is_warn, + DT_CHECK_UNARY_FALSE = is_normal | is_false | is_unary | is_check, + DT_REQUIRE_UNARY_FALSE = is_normal | is_false | is_unary | is_require, +}; +} +struct AssertData {}; +namespace detail { +template auto declval() noexcept -> decltype(declval(0)); +namespace has_insertion_operator_impl {} +struct Subcase { + Subcase(const String &name, const char *file, int line); + operator bool() const; +}; +struct Result { + bool m_passed; +}; +template struct Expression_lhs {}; +struct ExpressionDecomposer {}; +struct ResultBuilder : public AssertData { + ResultBuilder(assertType::Enum at, const char *file, int line, + const char *expr, const char *exception_type = "", + const char *exception_string = ""); + bool log(); + void react() const; +}; +} // namespace detail +} // namespace doctest +namespace std { +typedef long unsigned int size_t; +typedef long int ptrdiff_t; +inline namespace __cxx11 __attribute__((__abi_tag__("cxx11"))) {} +template class allocator; +namespace __cxx11 { +template , + typename _Alloc = allocator<_CharT>> +class basic_string; +} +typedef basic_string string; +} // namespace std +typedef long unsigned int size_t; +typedef struct __mbstate_t; +namespace std { +template > +class basic_streambuf; +template > +class basic_iostream; +} // namespace std +extern "C++" { +namespace std { +class exception { +public: +}; +} // namespace std +} +extern "C++" { +namespace std { +class bad_cast : public exception { +public: +}; +} // namespace std +[[__nodiscard__]] inline void *operator new(std::size_t, void *__p) noexcept {} +namespace std { +namespace __exception_ptr { +class exception_ptr; +} +using __exception_ptr::exception_ptr; +namespace __exception_ptr { +class exception_ptr { +public: + exception_ptr(nullptr_t); +}; +} // namespace __exception_ptr +} // namespace std +} +namespace std __attribute__((__visibility__("default"))) { + template struct integral_constant { + static constexpr _Tp value = __v; + typedef _Tp value_type; + typedef integral_constant<_Tp, __v> type; + constexpr operator value_type() const noexcept { return value; } + }; + typedef integral_constant true_type; + typedef integral_constant false_type; + template using __bool_constant = integral_constant; + template using bool_constant = integral_constant; + template struct conditional; + template struct __type_identity { using type = _Type; }; + template struct __or_; + template + struct __or_<_B1, _B2> : public conditional<_B1::value, _B1, _B2>::type {}; + template + struct __or_<_B1, _B2, _B3, _Bn...> + : public conditional<_B1::value, _B1, __or_<_B2, _B3, _Bn...>>::type {}; + template struct __and_; + template + struct __and_<_B1, _B2> : public conditional<_B1::value, _B2, _B1>::type {}; + template + struct __and_<_B1, _B2, _B3, _Bn...> + : public conditional<_B1::value, __and_<_B2, _B3, _Bn...>, _B1>::type {}; + template + struct __not_ : public __bool_constant {}; + template + inline constexpr bool __and_v = __and_<_Bn...>::value; + template struct conjunction : __and_<_Bn...> {}; + template struct is_reference; + template struct is_function; + template struct is_void; + template struct __is_array_unknown_bounds; + template + constexpr true_type __is_complete_or_unbounded(__type_identity<_Tp>) { + return {}; + } + template + constexpr typename __or_, is_function<_NestedType>, + is_void<_NestedType>, + __is_array_unknown_bounds<_NestedType>>::type + __is_complete_or_unbounded(_TypeIdentity) { + return {}; + } + template struct __success_type { typedef _Tp type; }; + template struct remove_cv; + template using __remove_cv_t = typename remove_cv<_Tp>::type; + template struct is_const; + template struct __is_void_helper : public false_type {}; + template <> struct __is_void_helper : public true_type {}; + template + struct is_void : public __is_void_helper<__remove_cv_t<_Tp>>::type {}; + template struct __is_integral_helper : public false_type {}; + template <> struct __is_integral_helper : public true_type {}; + template <> struct __is_integral_helper : public true_type {}; + template + struct is_integral : public __is_integral_helper<__remove_cv_t<_Tp>>::type {}; + template struct __is_floating_point_helper : public false_type {}; + template + struct is_floating_point + : public __is_floating_point_helper<__remove_cv_t<_Tp>>::type {}; + template struct is_array : public false_type {}; + template + struct is_array<_Tp[_Size]> : public true_type {}; + template struct __is_pointer_helper : public false_type {}; + template + struct __is_pointer_helper<_Tp *> : public true_type {}; + template + struct is_pointer : public __is_pointer_helper<__remove_cv_t<_Tp>>::type {}; + template struct is_lvalue_reference : public false_type {}; + template struct is_rvalue_reference : public false_type {}; + template + struct __is_member_object_pointer_helper : public false_type {}; + template + struct is_member_object_pointer + : public __is_member_object_pointer_helper<__remove_cv_t<_Tp>>::type {}; + template + struct __is_member_function_pointer_helper : public false_type {}; + template + struct __is_member_function_pointer_helper<_Tp _Cp::*> + : public is_function<_Tp>::type {}; + template + struct is_member_function_pointer + : public __is_member_function_pointer_helper<__remove_cv_t<_Tp>>::type {}; + template + struct is_enum : public integral_constant {}; + template + struct is_union : public integral_constant {}; + template + struct is_class : public integral_constant {}; + template + struct is_function : public __bool_constant::value> {}; + template struct is_function<_Tp &> : public false_type {}; + template struct __is_null_pointer_helper : public false_type {}; + template + struct is_null_pointer + : public __is_null_pointer_helper<__remove_cv_t<_Tp>>::type { + } __attribute__((__deprecated__("use '" + "std::is_null_pointer" + "' instead"))); + template + struct is_reference + : public __or_, is_rvalue_reference<_Tp>>::type { + }; + template + struct is_arithmetic + : public __or_, is_floating_point<_Tp>>::type {}; + template + struct is_fundamental : public __or_, is_void<_Tp>, + is_null_pointer<_Tp>>::type {}; + template + struct is_object + : public __not_< + __or_, is_reference<_Tp>, is_void<_Tp>>>::type {}; + template struct is_member_pointer; + template + struct is_scalar + : public __or_, is_enum<_Tp>, is_pointer<_Tp>, + is_member_pointer<_Tp>, is_null_pointer<_Tp>>::type {}; + template + struct __is_member_pointer_helper : public false_type {}; + template + struct is_member_pointer + : public __is_member_pointer_helper<__remove_cv_t<_Tp>>::type {}; + template using __void_t = void; + template + struct __is_referenceable : public false_type {}; + template + struct __is_referenceable<_Tp, __void_t<_Tp &>> : public true_type {}; + template struct is_const : public false_type {}; + template struct is_const<_Tp const> : public true_type {}; + template struct is_volatile : public false_type {}; + template + struct is_trivial : public integral_constant { + static_assert( + std::__is_complete_or_unbounded(__type_identity<_Tp>{}), + "template argument must be a complete class or an unbounded array"); + }; + template + struct is_trivially_copyable + : public integral_constant { + static_assert( + std::__is_complete_or_unbounded(__type_identity<_Tp>{}), + "template argument must be a complete class or an unbounded array"); + }; + template + struct is_standard_layout + : public integral_constant {}; + template + struct is_empty : public integral_constant {}; + template ::value> + struct __is_signed_helper : public false_type {}; + template + struct is_signed : public __is_signed_helper<_Tp>::type {}; + template _Up __declval(int); + template auto declval() noexcept->decltype(__declval<_Tp>(0)); + template struct extent; + template struct remove_all_extents; + template + struct __is_array_known_bounds + : public integral_constant::value > 0)> {}; + template + struct __is_array_unknown_bounds + : public __and_, __not_>> {}; + struct __do_is_destructible_impl { + template ().~_Tp())> + static true_type __test(int); + }; + template + struct __is_destructible_impl : public __do_is_destructible_impl { + typedef decltype(__test<_Tp>(0)) type; + }; + template , __is_array_unknown_bounds<_Tp>, + is_function<_Tp>>::value, + bool = __or_, is_scalar<_Tp>>::value> + struct __is_destructible_safe; + template + struct __is_destructible_safe<_Tp, false, false> + : public __is_destructible_impl< + typename remove_all_extents<_Tp>::type>::type {}; + template + struct is_destructible : public __is_destructible_safe<_Tp>::type { + static_assert( + std::__is_complete_or_unbounded(__type_identity<_Tp>{}), + "template argument must be a complete class or an unbounded array"); + }; + struct __do_is_nt_destructible_impl { + template + static __bool_constant().~_Tp())> __test(int); + }; + template + struct __is_nt_destructible_impl : public __do_is_nt_destructible_impl { + typedef decltype(__test<_Tp>(0)) type; + }; + template , __is_array_unknown_bounds<_Tp>, + is_function<_Tp>>::value, + bool = __or_, is_scalar<_Tp>>::value> + struct __is_nt_destructible_safe; + template + struct __is_nt_destructible_safe<_Tp, false, false> + : public __is_nt_destructible_impl< + typename remove_all_extents<_Tp>::type>::type {}; + template + struct is_nothrow_destructible : public __is_nt_destructible_safe<_Tp>::type { + }; + template + struct __is_constructible_impl + : public __bool_constant<__is_constructible(_Tp, _Args...)> {}; + template + struct is_constructible : public __is_constructible_impl<_Tp, _Args...> {}; + template + struct is_default_constructible : public __is_constructible_impl<_Tp>::type { + }; + template ::value> + struct __is_copy_constructible_impl; + template + struct __is_copy_constructible_impl<_Tp, true> + : public __is_constructible_impl<_Tp, const _Tp &> {}; + template + struct is_copy_constructible : public __is_copy_constructible_impl<_Tp> {}; + template ::value> + struct __is_move_constructible_impl; + template + struct __is_move_constructible_impl<_Tp, true> + : public __is_constructible_impl<_Tp, _Tp &&> {}; + template + struct is_move_constructible : public __is_move_constructible_impl<_Tp> {}; + template + using __is_nothrow_constructible_impl = + __bool_constant<__is_nothrow_constructible(_Tp, _Args...)>; + template + struct is_nothrow_constructible + : public __is_nothrow_constructible_impl<_Tp, _Args...>::type {}; + template + struct is_nothrow_default_constructible + : public __bool_constant<__is_nothrow_constructible(_Tp)> {}; + template ::value> + struct __is_nothrow_copy_constructible_impl; + template + struct __is_nothrow_copy_constructible_impl<_Tp, true> + : public __is_nothrow_constructible_impl<_Tp, const _Tp &> {}; + template + struct is_nothrow_copy_constructible + : public __is_nothrow_copy_constructible_impl<_Tp>::type { + static_assert( + std::__is_complete_or_unbounded(__type_identity<_Tp>{}), + "template argument must be a complete class or an unbounded array"); + }; + template ::value> + struct __is_nothrow_move_constructible_impl; + template + struct is_nothrow_move_constructible + : public __is_nothrow_move_constructible_impl<_Tp>::type {}; + template + struct is_assignable : public __bool_constant<__is_assignable(_Tp, _Up)> {}; + template ::value> + struct __is_copy_assignable_impl; + template + struct __is_copy_assignable_impl<_Tp, true> + : public __bool_constant<__is_assignable(_Tp &, const _Tp &)> {}; + template + struct is_copy_assignable : public __is_copy_assignable_impl<_Tp>::type {}; + template ::value> + struct __is_move_assignable_impl; + template + struct __is_move_assignable_impl<_Tp, true> + : public __bool_constant<__is_assignable(_Tp &, _Tp &&)> {}; + template + struct is_move_assignable : public __is_move_assignable_impl<_Tp>::type {}; + template ::value> + struct __is_trivially_copy_constructible_impl; + template + struct __is_trivially_copy_constructible_impl<_Tp, true> + : public __and_<__is_copy_constructible_impl<_Tp>, + integral_constant> {}; + template + struct is_trivially_copy_constructible + : public __is_trivially_copy_constructible_impl<_Tp> {}; + template ::value> + struct __is_trivially_move_constructible_impl; + template + struct __is_trivially_move_constructible_impl<_Tp, true> + : public __and_<__is_move_constructible_impl<_Tp>, + integral_constant> {}; + template + struct is_trivially_move_constructible + : public __is_trivially_move_constructible_impl<_Tp> {}; + template ::value> + struct __is_trivially_copy_assignable_impl; + template + struct __is_trivially_copy_assignable_impl<_Tp, true> + : public __bool_constant<__is_trivially_assignable(_Tp &, const _Tp &)> { + }; + template + struct is_trivially_copy_assignable + : public __is_trivially_copy_assignable_impl<_Tp> {}; + template ::value> + struct __is_trivially_move_assignable_impl; + template + struct __is_trivially_move_assignable_impl<_Tp, true> + : public __bool_constant<__is_trivially_assignable(_Tp &, _Tp &&)> {}; + template + struct is_trivially_move_assignable + : public __is_trivially_move_assignable_impl<_Tp> {}; + template + struct is_trivially_destructible + : public __and_<__is_destructible_safe<_Tp>, + __bool_constant<__has_trivial_destructor(_Tp)>> {}; + template + struct alignment_of : public integral_constant { + static_assert( + std::__is_complete_or_unbounded(__type_identity<_Tp>{}), + "template argument must be a complete class or an unbounded array"); + }; + template + struct is_same : public integral_constant {}; + template + struct is_base_of + : public integral_constant {}; + template , is_function<_To>, is_array<_To>>::value> + struct __is_convertible_helper; + template + class __is_convertible_helper<_From, _To, false> { + template static void __test_aux(_To1) noexcept; + template (std::declval<_From1>()))> + static true_type __test(int); + + public: + typedef decltype(__test<_From, _To>(0)) type; + }; + template + struct is_convertible : public __is_convertible_helper<_From, _To>::type {}; + template , is_function<_To>, is_array<_To>>::value> + struct __is_nt_convertible_helper : is_void<_To> {}; + template + struct is_nothrow_convertible + : public __is_nt_convertible_helper<_From, _To>::type {}; + template struct remove_const { typedef _Tp type; }; + template struct remove_cv { using type = _Tp; }; + template struct remove_cv { using type = _Tp; }; + template struct add_const; + template + using remove_const_t = typename remove_const<_Tp>::type; + template using remove_cv_t = typename remove_cv<_Tp>::type; + template struct remove_reference { typedef _Tp type; }; + template struct remove_reference<_Tp &> { typedef _Tp type; }; + template struct remove_reference<_Tp &&> { typedef _Tp type; }; + template ::value> + struct __add_rvalue_reference_helper { + typedef _Tp type; + }; + template + struct add_rvalue_reference : public __add_rvalue_reference_helper<_Tp> {}; + template + using remove_reference_t = typename remove_reference<_Tp>::type; + template + using add_rvalue_reference_t = typename add_rvalue_reference<_Tp>::type; + template + struct __cv_selector; + template + struct __cv_selector<_Unqualified, false, false> { + typedef _Unqualified __type; + }; + template ::value, + bool _IsVol = is_volatile<_Qualified>::value> + class __match_cv_qualifiers { + typedef __cv_selector<_Unqualified, _IsConst, _IsVol> __match; + + public: + typedef typename __match::__type __type; + }; + template struct __make_unsigned { typedef _Tp __type; }; + template ::value, + bool _IsEnum = is_enum<_Tp>::value> + class __make_unsigned_selector; + template class __make_unsigned_selector<_Tp, true, false> { + using __unsigned_type = + typename __make_unsigned<__remove_cv_t<_Tp>>::__type; + + public: + using __type = typename __match_cv_qualifiers<_Tp, __unsigned_type>::__type; + }; + template struct make_unsigned { + typedef typename __make_unsigned_selector<_Tp>::__type type; + }; + template struct remove_all_extents { typedef _Tp type; }; + template + using remove_all_extents_t = typename remove_all_extents<_Tp>::type; + template ::value, + bool _IsFunction = is_function<_Up>::value> + struct __decay_selector; + template struct __decay_selector<_Up, false, false> { + typedef __remove_cv_t<_Up> __type; + }; + template class decay { + typedef typename remove_reference<_Tp>::type __remove_type; + + public: + typedef typename __decay_selector<__remove_type>::__type type; + }; + template using __decay_t = typename decay<_Tp>::type; + template struct enable_if {}; + template struct enable_if { typedef _Tp type; }; + template + using __enable_if_t = typename enable_if<_Cond, _Tp>::type; + template + using _Require = __enable_if_t<__and_<_Cond...>::value>; + template + struct conditional { + typedef _Iftrue type; + }; + template + struct conditional { + typedef _Iffalse type; + }; + template + using __remove_cvref_t = + typename remove_cv::type>::type; + template struct result_of; + struct __invoke_memfun_deref; + struct __invoke_other {}; + template + struct __result_of_success : __success_type<_Tp> { + using __invoke_type = _Tag; + }; + struct __result_of_memfun_ref_impl {}; + template + struct __result_of_memfun_ref : private __result_of_memfun_ref_impl {}; + struct __result_of_memfun_deref_impl { + template + static __result_of_success< + decltype(((*std::declval<_Tp1>()).* + std::declval<_Fp>())(std::declval<_Args>()...)), + __invoke_memfun_deref> + _S_test(int); + }; + template + struct __result_of_memfun_deref : private __result_of_memfun_deref_impl { + typedef decltype(_S_test<_MemPtr, _Arg, _Args...>(0)) type; + }; + template + struct __result_of_memfun; + template + struct __result_of_memfun<_Res _Class::*, _Arg, _Args...> { + typedef typename remove_reference<_Arg>::type _Argval; + typedef _Res _Class::*_MemPtr; + typedef typename conditional< + is_base_of<_Class, _Argval>::value, + __result_of_memfun_ref<_MemPtr, _Arg, _Args...>, + __result_of_memfun_deref<_MemPtr, _Arg, _Args...>>::type::type type; + }; + template > + struct __inv_unwrap { + using type = _Tp; + }; + template + struct __result_of_impl; + template + struct __result_of_impl + : public __result_of_memfun<__decay_t<_MemPtr>, + typename __inv_unwrap<_Arg>::type, _Args...> { + }; + struct __result_of_other_impl { + template + static __result_of_success< + decltype(std::declval<_Fn>()(std::declval<_Args>()...)), __invoke_other> + _S_test(int); + }; + template + struct __result_of_impl + : private __result_of_other_impl { + typedef decltype(_S_test<_Functor, _ArgTypes...>(0)) type; + }; + template + struct __invoke_result + : public __result_of_impl< + is_member_object_pointer< + typename remove_reference<_Functor>::type>::value, + is_member_function_pointer< + typename remove_reference<_Functor>::type>::value, + _Functor, _ArgTypes...>::type {}; + template + struct result_of<_Functor(_ArgTypes...)> + : public __invoke_result<_Functor, _ArgTypes...> {}; + template + using enable_if_t = typename enable_if<_Cond, _Tp>::type; + template + using conditional_t = typename conditional<_Cond, _Iftrue, _Iffalse>::type; + template class _Op, typename... _Args> + struct __detector { + using type = _Default; + }; + template class _Op, + typename... _Args> + using __detected_or = __detector<_Default, void, _Op, _Args...>; + template class _Op, + typename... _Args> + using __detected_or_t = typename __detected_or<_Default, _Op, _Args...>::type; + template class tuple; + template struct __is_tuple_like_impl : false_type {}; + template + struct __is_tuple_like + : public __is_tuple_like_impl<__remove_cvref_t<_Tp>>::type {}; + namespace __swappable_details { + struct __do_is_swappable_impl {}; + struct __do_is_nothrow_swappable_impl {}; + } // namespace __swappable_details + template + struct __is_swappable_impl + : public __swappable_details::__do_is_swappable_impl {}; + template + struct is_swappable : public __is_swappable_impl<_Tp>::type { + static_assert( + std::__is_complete_or_unbounded(__type_identity<_Tp>{}), + "template argument must be a complete class or an unbounded array"); + }; + template ::value, + typename = void> + struct __is_invocable_impl : false_type {}; + template + struct __is_invocable_impl<_Result, _Ret, true, + __void_t> : true_type {}; + template + struct __is_invocable_impl<_Result, _Ret, false, + __void_t> { + private: + static typename _Result::type _S_get(); + template static void _S_conv(_Tp); + template (_S_get()))> + static true_type _S_test(int); + + public: + using type = decltype(_S_test<_Ret>(1)); + }; + template + struct __is_invocable + : __is_invocable_impl<__invoke_result<_Fn, _ArgTypes...>, void>::type {}; + template + constexpr bool __call_is_nt(__invoke_other) { + return noexcept(std::declval<_Fn>()(std::declval<_Args>()...)); + } + template + struct __call_is_nothrow : __bool_constant( + typename _Result::__invoke_type{})> {}; + template + using __call_is_nothrow_ = + __call_is_nothrow<__invoke_result<_Fn, _Args...>, _Fn, _Args...>; + template + struct __is_nothrow_invocable + : __and_<__is_invocable<_Fn, _Args...>, + __call_is_nothrow_<_Fn, _Args...>>::type {}; + template + struct invoke_result : public __invoke_result<_Functor, _ArgTypes...> {}; + template + using invoke_result_t = typename invoke_result<_Fn, _Args...>::type; + template + struct is_invocable + : __is_invocable_impl<__invoke_result<_Fn, _ArgTypes...>, void>::type {}; + template + struct is_invocable_r + : __is_invocable_impl<__invoke_result<_Fn, _ArgTypes...>, _Ret>::type { + static_assert(std::__is_complete_or_unbounded(__type_identity<_Fn>{}), + "_Ret must be a complete class or an unbounded array"); + }; + template + struct is_nothrow_invocable + : __and_<__is_invocable_impl<__invoke_result<_Fn, _ArgTypes...>, void>, + __call_is_nothrow_<_Fn, _ArgTypes...>>::type {}; + template + struct __is_nt_invocable_impl : false_type {}; + template + struct is_nothrow_invocable_r + : __and_<__is_nt_invocable_impl<__invoke_result<_Fn, _ArgTypes...>, _Ret>, + __call_is_nothrow_<_Fn, _ArgTypes...>>::type { + static_assert(std::__is_complete_or_unbounded(__type_identity<_Fn>{}), + "_Fn must be a complete class or an unbounded array"); + static_assert( + (std::__is_complete_or_unbounded(__type_identity<_ArgTypes>{}) && ...), + "each argument type must be a complete class or an unbounded array"); + static_assert(std::__is_complete_or_unbounded(__type_identity<_Ret>{}), + "_Ret must be a complete class or an unbounded array"); + }; + template + inline constexpr bool is_invocable_v = is_invocable<_Fn, _Args...>::value; + template + inline constexpr bool is_nothrow_invocable_v = + is_nothrow_invocable<_Fn, _Args...>::value; + template + inline constexpr bool is_invocable_r_v = + is_invocable_r<_Ret, _Fn, _Args...>::value; + template + inline constexpr bool is_nothrow_invocable_r_v = + is_nothrow_invocable_r<_Ret, _Fn, _Args...>::value; + template inline constexpr bool is_void_v = is_void<_Tp>::value; + template + inline constexpr bool is_integral_v = is_integral<_Tp>::value; + template + inline constexpr bool is_lvalue_reference_v = is_lvalue_reference<_Tp>::value; + template + inline constexpr bool is_reference_v = is_reference<_Tp>::value; + template + inline constexpr bool is_object_v = is_object<_Tp>::value; + template + inline constexpr bool is_constructible_v = + is_constructible<_Tp, _Args...>::value; + template + inline constexpr bool is_default_constructible_v = + is_default_constructible<_Tp>::value; + template + inline constexpr bool is_copy_constructible_v = + is_copy_constructible<_Tp>::value; + template + inline constexpr bool is_move_constructible_v = + is_move_constructible<_Tp>::value; + template + inline constexpr bool is_copy_assignable_v = is_copy_assignable<_Tp>::value; + template + inline constexpr bool is_move_assignable_v = is_move_assignable<_Tp>::value; + template + inline constexpr bool is_trivially_copy_constructible_v = + is_trivially_copy_constructible<_Tp>::value; + template + inline constexpr bool is_trivially_move_constructible_v = + is_trivially_move_constructible<_Tp>::value; + template + inline constexpr bool is_trivially_copy_assignable_v = + is_trivially_copy_assignable<_Tp>::value; + template + inline constexpr bool is_trivially_move_assignable_v = + is_trivially_move_assignable<_Tp>::value; + template + inline constexpr bool is_trivially_destructible_v = + is_trivially_destructible<_Tp>::value; + template + inline constexpr bool is_nothrow_default_constructible_v = + is_nothrow_default_constructible<_Tp>::value; + template + inline constexpr bool is_nothrow_destructible_v = + is_nothrow_destructible<_Tp>::value; + template + inline constexpr bool is_same_v = __is_same(_Tp, _Up); + template + inline constexpr bool is_convertible_v = is_convertible<_From, _To>::value; + template + struct has_unique_object_representations + : bool_constant<__has_unique_object_representations( + remove_cv_t>)> {}; + template using remove_cvref_t = __remove_cvref_t<_Tp>; + constexpr inline bool is_constant_evaluated() noexcept { + return __builtin_is_constant_evaluated(); + } + template struct common_reference; + template + using common_reference_t = typename common_reference<_Tp...>::type; +} // namespace ) +namespace std __attribute__((__visibility__("default"))) { + template + [[__nodiscard__]] constexpr _Tp &&forward( + typename std::remove_reference<_Tp>::type & __t) noexcept { + return static_cast<_Tp &&>(__t); + } + template + [[__nodiscard__]] constexpr typename std::remove_reference<_Tp>::type &&move( + _Tp && __t) noexcept { + return static_cast::type &&>(__t); + }; + template + [[__nodiscard__]] inline constexpr _Tp *addressof(_Tp & __r) noexcept {} +} // namespace ) +extern "C++" { +namespace std __attribute__((__visibility__("default"))) { + template struct __is_integer { + enum { __value = 0 }; + }; + template struct iterator_traits; + template struct __is_nonvolatile_trivially_copyable; +} // namespace ) +} +namespace __gnu_cxx __attribute__((__visibility__("default"))) { + template + struct __is_integer_nonstrict : public std::__is_integer<_Tp> { + using std::__is_integer<_Tp>::__value; + enum { __width = __value ? sizeof(_Tp) * 8 : 0 }; + }; + template struct __numeric_traits_integer { + static const bool __is_signed = (_Value)(-1) < 0; + static const int __digits = + __is_integer_nonstrict<_Value>::__width - __is_signed; + }; + template using __int_traits = __numeric_traits_integer<_Tp>; +} // namespace ) +namespace std __attribute__((__visibility__("default"))) { + namespace __detail { + template + concept __same_as = std::is_same_v<_Tp, _Up>; + } + template + concept same_as = + __detail::__same_as<_Tp, _Up> && __detail::__same_as<_Up, _Tp>; + template + concept derived_from = + __is_base_of(_Base, _Derived) && + is_convertible_v; + template + concept convertible_to = is_convertible_v<_From, _To> && + requires(add_rvalue_reference_t<_From>(&__f)()) { + static_cast<_To>(__f()); + }; + template + concept common_reference_with = + same_as, common_reference_t<_Up, _Tp>> && + convertible_to<_Tp, common_reference_t<_Tp, _Up>> && + convertible_to<_Up, common_reference_t<_Tp, _Up>>; + namespace __detail { + template using __cref = const remove_reference_t<_Tp> &; + } + template + concept assignable_from = is_lvalue_reference_v<_Lhs> && + common_reference_with<__detail::__cref<_Lhs>, __detail::__cref<_Rhs>> && + requires(_Lhs __lhs, _Rhs && __rhs) { + { __lhs = static_cast<_Rhs &&>(__rhs) } -> same_as<_Lhs>; + }; + template + concept destructible = is_nothrow_destructible_v<_Tp>; + template + concept constructible_from = + destructible<_Tp> && is_constructible_v<_Tp, _Args...>; + template + concept default_initializable = constructible_from<_Tp> && requires { + _Tp{}; + }; + template + concept move_constructible = + constructible_from<_Tp, _Tp> && convertible_to<_Tp, _Tp>; + template + concept copy_constructible = + move_constructible<_Tp> && constructible_from<_Tp, _Tp &> && + convertible_to<_Tp &, _Tp> && constructible_from<_Tp, const _Tp &> && + convertible_to && constructible_from<_Tp, const _Tp> && + convertible_to; + namespace ranges { + namespace __cust_swap { + struct _Swap {}; + } // namespace __cust_swap + inline namespace __cust { + inline constexpr __cust_swap::_Swap swap; + } + } // namespace ranges + template + concept swappable = requires(_Tp & __a, _Tp & __b) { + ranges::swap(__a, __b); + }; + template + concept movable = is_object_v<_Tp> && move_constructible<_Tp> && + assignable_from<_Tp &, _Tp> && swappable<_Tp>; + template + concept copyable = copy_constructible<_Tp> && movable<_Tp> && + assignable_from<_Tp &, _Tp &> && assignable_from<_Tp &, const _Tp &> && + assignable_from<_Tp &, const _Tp>; + template + concept semiregular = copyable<_Tp> && default_initializable<_Tp>; + namespace __detail { + template + concept __boolean_testable_impl = convertible_to<_Tp, bool>; + template + concept __boolean_testable = + __boolean_testable_impl<_Tp> && requires(_Tp && __t) { + { !static_cast<_Tp &&>(__t) } -> __boolean_testable_impl; + }; + } // namespace __detail + namespace __detail { + template + concept __weakly_eq_cmp_with = requires(__detail::__cref<_Tp> __t, + __detail::__cref<_Up> __u) { + { __t == __u } -> __boolean_testable; + }; + } // namespace __detail + template + concept equality_comparable = __detail::__weakly_eq_cmp_with<_Tp, _Tp>; + namespace __detail { + template + concept __partially_ordered_with = + requires(const remove_reference_t<_Tp> &__t, + const remove_reference_t<_Up> &__u) { + { __t < __u } -> __boolean_testable; + }; + } // namespace __detail + template + concept regular = semiregular<_Tp> && equality_comparable<_Tp>; + template + concept invocable = is_invocable_v<_Fn, _Args...>; + namespace __cmp_cat {} + template class __pair_base; + template + struct pair : private __pair_base<_T1, _T2> {}; + template struct __replace_first_arg; + template