1/* Processing rules for constraints. 2 Copyright (C) 2013-2022 Free Software Foundation, Inc. 3 Contributed by Andrew Sutton (andrew.n.sutton@gmail.com) 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "timevar.h" 26#include "hash-set.h" 27#include "machmode.h" 28#include "vec.h" 29#include "double-int.h" 30#include "input.h" 31#include "alias.h" 32#include "symtab.h" 33#include "wide-int.h" 34#include "inchash.h" 35#include "tree.h" 36#include "stringpool.h" 37#include "attribs.h" 38#include "intl.h" 39#include "flags.h" 40#include "cp-tree.h" 41#include "c-family/c-common.h" 42#include "c-family/c-objc.h" 43#include "cp-objcp-common.h" 44#include "tree-inline.h" 45#include "decl.h" 46#include "toplev.h" 47#include "type-utils.h" 48 49static tree satisfaction_value (tree t); 50 51/* When we're parsing or substuting a constraint expression, we have slightly 52 different expression semantics. In particular, we don't want to reduce a 53 concept-id to a satisfaction value. */ 54 55processing_constraint_expression_sentinel:: 56processing_constraint_expression_sentinel () 57{ 58 ++scope_chain->x_processing_constraint; 59} 60 61processing_constraint_expression_sentinel:: 62~processing_constraint_expression_sentinel () 63{ 64 --scope_chain->x_processing_constraint; 65} 66 67bool 68processing_constraint_expression_p () 69{ 70 return scope_chain->x_processing_constraint != 0; 71} 72 73/*--------------------------------------------------------------------------- 74 Constraint expressions 75---------------------------------------------------------------------------*/ 76 77/* Information provided to substitution. */ 78 79struct subst_info 80{ 81 subst_info (tsubst_flags_t cmp, tree in) 82 : complain (cmp), in_decl (in) 83 { } 84 85 /* True if we should not diagnose errors. */ 86 bool quiet() const 87 { 88 return complain == tf_none; 89 } 90 91 /* True if we should diagnose errors. */ 92 bool noisy() const 93 { 94 return !quiet (); 95 } 96 97 tsubst_flags_t complain; 98 tree in_decl; 99}; 100 101/* Provides additional context for satisfaction. 102 103 During satisfaction: 104 - The flag noisy() controls whether to diagnose ill-formed satisfaction, 105 such as the satisfaction value of an atom being non-bool or non-constant. 106 - The flag diagnose_unsatisfaction_p() controls whether to additionally 107 explain why a constraint is not satisfied. 108 - We enter satisfaction with noisy+unsat from diagnose_constraints. 109 - We enter satisfaction with noisy-unsat from the replay inside 110 constraint_satisfaction_value. 111 - We enter satisfaction quietly (both flags cleared) from 112 constraints_satisfied_p. 113 114 During evaluation of a requires-expression: 115 - The flag noisy() controls whether to diagnose ill-formed types and 116 expressions inside its requirements. 117 - The flag diagnose_unsatisfaction_p() controls whether to additionally 118 explain why the requires-expression evaluates to false. 119 - We enter tsubst_requires_expr with noisy+unsat from 120 diagnose_atomic_constraint and potentially from 121 satisfy_nondeclaration_constraints. 122 - We enter tsubst_requires_expr with noisy-unsat from 123 cp_parser_requires_expression when processing a requires-expression that 124 appears outside a template. 125 - We enter tsubst_requires_expr quietly (both flags cleared) when 126 substituting through a requires-expression as part of template 127 instantiation. */ 128 129struct sat_info : subst_info 130{ 131 sat_info (tsubst_flags_t cmp, tree in, bool diag_unsat = false) 132 : subst_info (cmp, in), diagnose_unsatisfaction (diag_unsat) 133 { 134 if (diagnose_unsatisfaction_p ()) 135 gcc_checking_assert (noisy ()); 136 } 137 138 /* True if we should diagnose the cause of satisfaction failure. 139 Implies noisy(). */ 140 bool 141 diagnose_unsatisfaction_p () const 142 { 143 return diagnose_unsatisfaction; 144 } 145 146 bool diagnose_unsatisfaction; 147}; 148 149static tree constraint_satisfaction_value (tree, tree, sat_info); 150 151/* True if T is known to be some type other than bool. Note that this 152 is false for dependent types and errors. */ 153 154static inline bool 155known_non_bool_p (tree t) 156{ 157 return (t && !WILDCARD_TYPE_P (t) && TREE_CODE (t) != BOOLEAN_TYPE); 158} 159 160static bool 161check_constraint_atom (cp_expr expr) 162{ 163 if (known_non_bool_p (TREE_TYPE (expr))) 164 { 165 error_at (expr.get_location (), 166 "constraint expression does not have type %<bool%>"); 167 return false; 168 } 169 170 /* Check that we're using function concepts correctly. */ 171 if (concept_check_p (expr)) 172 { 173 tree id = unpack_concept_check (expr); 174 tree tmpl = TREE_OPERAND (id, 0); 175 if (OVL_P (tmpl) && TREE_CODE (expr) == TEMPLATE_ID_EXPR) 176 { 177 error_at (EXPR_LOC_OR_LOC (expr, input_location), 178 "function concept must be called"); 179 return false; 180 } 181 } 182 183 return true; 184} 185 186static bool 187check_constraint_operands (location_t, cp_expr lhs, cp_expr rhs) 188{ 189 return check_constraint_atom (lhs) && check_constraint_atom (rhs); 190} 191 192/* Validate the semantic properties of the constraint expression. */ 193 194static cp_expr 195finish_constraint_binary_op (location_t loc, 196 tree_code code, 197 cp_expr lhs, 198 cp_expr rhs) 199{ 200 gcc_assert (processing_constraint_expression_p ()); 201 if (lhs == error_mark_node || rhs == error_mark_node) 202 return error_mark_node; 203 if (!check_constraint_operands (loc, lhs, rhs)) 204 return error_mark_node; 205 cp_expr expr 206 = build_min_nt_loc (loc, code, lhs.get_value (), rhs.get_value ()); 207 expr.set_range (lhs.get_start (), rhs.get_finish ()); 208 return expr; 209} 210 211cp_expr 212finish_constraint_or_expr (location_t loc, cp_expr lhs, cp_expr rhs) 213{ 214 return finish_constraint_binary_op (loc, TRUTH_ORIF_EXPR, lhs, rhs); 215} 216 217cp_expr 218finish_constraint_and_expr (location_t loc, cp_expr lhs, cp_expr rhs) 219{ 220 return finish_constraint_binary_op (loc, TRUTH_ANDIF_EXPR, lhs, rhs); 221} 222 223cp_expr 224finish_constraint_primary_expr (cp_expr expr) 225{ 226 if (expr == error_mark_node) 227 return error_mark_node; 228 if (!check_constraint_atom (expr)) 229 return cp_expr (error_mark_node, expr.get_location ()); 230 return expr; 231} 232 233/* Combine two constraint-expressions with a logical-and. */ 234 235tree 236combine_constraint_expressions (tree lhs, tree rhs) 237{ 238 processing_constraint_expression_sentinel pce; 239 if (!lhs) 240 return rhs; 241 if (!rhs) 242 return lhs; 243 return finish_constraint_and_expr (input_location, lhs, rhs); 244} 245 246/* Extract the template-id from a concept check. For standard and variable 247 checks, this is simply T. For function concept checks, this is the 248 called function. */ 249 250tree 251unpack_concept_check (tree t) 252{ 253 gcc_assert (concept_check_p (t)); 254 255 if (TREE_CODE (t) == CALL_EXPR) 256 t = CALL_EXPR_FN (t); 257 258 gcc_assert (TREE_CODE (t) == TEMPLATE_ID_EXPR); 259 return t; 260} 261 262/* Extract the TEMPLATE_DECL from a concept check. */ 263 264tree 265get_concept_check_template (tree t) 266{ 267 tree id = unpack_concept_check (t); 268 tree tmpl = TREE_OPERAND (id, 0); 269 if (OVL_P (tmpl)) 270 tmpl = OVL_FIRST (tmpl); 271 return tmpl; 272} 273 274/*--------------------------------------------------------------------------- 275 Resolution of qualified concept names 276---------------------------------------------------------------------------*/ 277 278/* This facility is used to resolve constraint checks from requirement 279 expressions. A constraint check is a call to a function template declared 280 with the keyword 'concept'. 281 282 The result of resolution is a pair (a TREE_LIST) whose value is the 283 matched declaration, and whose purpose contains the coerced template 284 arguments that can be substituted into the call. */ 285 286/* Given an overload set OVL, try to find a unique definition that can be 287 instantiated by the template arguments ARGS. 288 289 This function is not called for arbitrary call expressions. In particular, 290 the call expression must be written with explicit template arguments 291 and no function arguments. For example: 292 293 f<T, U>() 294 295 If a single match is found, this returns a TREE_LIST whose VALUE 296 is the constraint function (not the template), and its PURPOSE is 297 the complete set of arguments substituted into the parameter list. */ 298 299static tree 300resolve_function_concept_overload (tree ovl, tree args) 301{ 302 int nerrs = 0; 303 tree cands = NULL_TREE; 304 for (lkp_iterator iter (ovl); iter; ++iter) 305 { 306 tree tmpl = *iter; 307 if (TREE_CODE (tmpl) != TEMPLATE_DECL) 308 continue; 309 310 /* Don't try to deduce checks for non-concepts. We often end up trying 311 to resolve constraints in functional casts as part of a 312 postfix-expression. We can save time and headaches by not 313 instantiating those declarations. 314 315 NOTE: This masks a potential error, caused by instantiating 316 non-deduced contexts using placeholder arguments. */ 317 tree fn = DECL_TEMPLATE_RESULT (tmpl); 318 if (DECL_ARGUMENTS (fn)) 319 continue; 320 if (!DECL_DECLARED_CONCEPT_P (fn)) 321 continue; 322 323 /* Remember the candidate if we can deduce a substitution. */ 324 ++processing_template_decl; 325 tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl)); 326 if (tree subst = coerce_template_parms (parms, args, tmpl)) 327 { 328 if (subst == error_mark_node) 329 ++nerrs; 330 else 331 cands = tree_cons (subst, fn, cands); 332 } 333 --processing_template_decl; 334 } 335 336 if (!cands) 337 /* We either had no candidates or failed deductions. */ 338 return nerrs ? error_mark_node : NULL_TREE; 339 else if (TREE_CHAIN (cands)) 340 /* There are multiple candidates. */ 341 return error_mark_node; 342 343 return cands; 344} 345 346/* Determine if the call expression CALL is a constraint check, and 347 return the concept declaration and arguments being checked. If CALL 348 does not denote a constraint check, return NULL. */ 349 350tree 351resolve_function_concept_check (tree call) 352{ 353 gcc_assert (TREE_CODE (call) == CALL_EXPR); 354 355 /* A constraint check must be only a template-id expression. 356 If it's a call to a base-link, its function(s) should be a 357 template-id expression. If this is not a template-id, then 358 it cannot be a concept-check. */ 359 tree target = CALL_EXPR_FN (call); 360 if (BASELINK_P (target)) 361 target = BASELINK_FUNCTIONS (target); 362 if (TREE_CODE (target) != TEMPLATE_ID_EXPR) 363 return NULL_TREE; 364 365 /* Get the overload set and template arguments and try to 366 resolve the target. */ 367 tree ovl = TREE_OPERAND (target, 0); 368 369 /* This is a function call of a variable concept... ill-formed. */ 370 if (TREE_CODE (ovl) == TEMPLATE_DECL) 371 { 372 error_at (location_of (call), 373 "function call of variable concept %qE", call); 374 return error_mark_node; 375 } 376 377 tree args = TREE_OPERAND (target, 1); 378 return resolve_function_concept_overload (ovl, args); 379} 380 381/* Returns a pair containing the checked concept and its associated 382 prototype parameter. The result is a TREE_LIST whose TREE_VALUE 383 is the concept (non-template) and whose TREE_PURPOSE contains 384 the converted template arguments, including the deduced prototype 385 parameter (in position 0). */ 386 387tree 388resolve_concept_check (tree check) 389{ 390 gcc_assert (concept_check_p (check)); 391 tree id = unpack_concept_check (check); 392 tree tmpl = TREE_OPERAND (id, 0); 393 394 /* If this is an overloaded function concept, perform overload 395 resolution (this only happens when deducing prototype parameters 396 and template introductions). */ 397 if (TREE_CODE (tmpl) == OVERLOAD) 398 { 399 if (OVL_CHAIN (tmpl)) 400 return resolve_function_concept_check (check); 401 tmpl = OVL_FIRST (tmpl); 402 } 403 404 tree args = TREE_OPERAND (id, 1); 405 tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl)); 406 ++processing_template_decl; 407 tree result = coerce_template_parms (parms, args, tmpl); 408 --processing_template_decl; 409 if (result == error_mark_node) 410 return error_mark_node; 411 return build_tree_list (result, DECL_TEMPLATE_RESULT (tmpl)); 412} 413 414/* Given a call expression or template-id expression to a concept EXPR 415 possibly including a wildcard, deduce the concept being checked and 416 the prototype parameter. Returns true if the constraint and prototype 417 can be deduced and false otherwise. Note that the CHECK and PROTO 418 arguments are set to NULL_TREE if this returns false. */ 419 420bool 421deduce_constrained_parameter (tree expr, tree& check, tree& proto) 422{ 423 tree info = resolve_concept_check (expr); 424 if (info && info != error_mark_node) 425 { 426 check = TREE_VALUE (info); 427 tree arg = TREE_VEC_ELT (TREE_PURPOSE (info), 0); 428 if (ARGUMENT_PACK_P (arg)) 429 arg = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg), 0); 430 proto = TREE_TYPE (arg); 431 return true; 432 } 433 434 check = proto = NULL_TREE; 435 return false; 436} 437 438/* Given a call expression or template-id expression to a concept, EXPR, 439 deduce the concept being checked and return the template arguments. 440 Returns NULL_TREE if deduction fails. */ 441static tree 442deduce_concept_introduction (tree check) 443{ 444 tree info = resolve_concept_check (check); 445 if (info && info != error_mark_node) 446 return TREE_PURPOSE (info); 447 return NULL_TREE; 448} 449 450/* Build a constrained placeholder type where SPEC is a type-constraint. 451 SPEC can be anything were concept_definition_p is true. 452 453 Returns a pair whose FIRST is the concept being checked and whose 454 SECOND is the prototype parameter. */ 455 456tree_pair 457finish_type_constraints (tree spec, tree args, tsubst_flags_t complain) 458{ 459 gcc_assert (concept_definition_p (spec)); 460 461 /* Build an initial concept check. */ 462 tree check = build_type_constraint (spec, args, complain); 463 if (check == error_mark_node) 464 return std::make_pair (error_mark_node, NULL_TREE); 465 466 /* Extract the concept and prototype parameter from the check. */ 467 tree con; 468 tree proto; 469 if (!deduce_constrained_parameter (check, con, proto)) 470 return std::make_pair (error_mark_node, NULL_TREE); 471 472 return std::make_pair (con, proto); 473} 474 475/*--------------------------------------------------------------------------- 476 Expansion of concept definitions 477---------------------------------------------------------------------------*/ 478 479/* Returns the expression of a function concept. */ 480 481static tree 482get_returned_expression (tree fn) 483{ 484 /* Extract the body of the function minus the return expression. */ 485 tree body = DECL_SAVED_TREE (fn); 486 if (!body) 487 return error_mark_node; 488 if (TREE_CODE (body) == BIND_EXPR) 489 body = BIND_EXPR_BODY (body); 490 if (TREE_CODE (body) != RETURN_EXPR) 491 return error_mark_node; 492 493 return TREE_OPERAND (body, 0); 494} 495 496/* Returns the initializer of a variable concept. */ 497 498static tree 499get_variable_initializer (tree var) 500{ 501 tree init = DECL_INITIAL (var); 502 if (!init) 503 return error_mark_node; 504 if (BRACE_ENCLOSED_INITIALIZER_P (init) 505 && CONSTRUCTOR_NELTS (init) == 1) 506 init = CONSTRUCTOR_ELT (init, 0)->value; 507 return init; 508} 509 510/* Returns the definition of a variable or function concept. */ 511 512static tree 513get_concept_definition (tree decl) 514{ 515 if (TREE_CODE (decl) == OVERLOAD) 516 decl = OVL_FIRST (decl); 517 518 if (TREE_CODE (decl) == TEMPLATE_DECL) 519 decl = DECL_TEMPLATE_RESULT (decl); 520 521 if (TREE_CODE (decl) == CONCEPT_DECL) 522 return DECL_INITIAL (decl); 523 if (VAR_P (decl)) 524 return get_variable_initializer (decl); 525 if (TREE_CODE (decl) == FUNCTION_DECL) 526 return get_returned_expression (decl); 527 gcc_unreachable (); 528} 529 530/*--------------------------------------------------------------------------- 531 Normalization of expressions 532 533This set of functions will transform an expression into a constraint 534in a sequence of steps. 535---------------------------------------------------------------------------*/ 536 537void 538debug_parameter_mapping (tree map) 539{ 540 for (tree p = map; p; p = TREE_CHAIN (p)) 541 { 542 tree parm = TREE_VALUE (p); 543 tree arg = TREE_PURPOSE (p); 544 if (TYPE_P (parm)) 545 verbatim ("MAP %qD TO %qT", TEMPLATE_TYPE_DECL (parm), arg); 546 else 547 verbatim ("MAP %qD TO %qE", TEMPLATE_PARM_DECL (parm), arg); 548 // debug_tree (parm); 549 // debug_tree (arg); 550 } 551} 552 553void 554debug_argument_list (tree args) 555{ 556 for (int i = 0; i < TREE_VEC_LENGTH (args); ++i) 557 { 558 tree arg = TREE_VEC_ELT (args, i); 559 if (TYPE_P (arg)) 560 verbatim ("argument %qT", arg); 561 else 562 verbatim ("argument %qE", arg); 563 } 564} 565 566/* Associate each parameter in PARMS with its corresponding template 567 argument in ARGS. */ 568 569static tree 570map_arguments (tree parms, tree args) 571{ 572 for (tree p = parms; p; p = TREE_CHAIN (p)) 573 if (args) 574 { 575 int level; 576 int index; 577 template_parm_level_and_index (TREE_VALUE (p), &level, &index); 578 TREE_PURPOSE (p) = TMPL_ARG (args, level, index); 579 } 580 else 581 TREE_PURPOSE (p) = template_parm_to_arg (p); 582 583 return parms; 584} 585 586/* Build the parameter mapping for EXPR using ARGS, where CTX_PARMS 587 are the template parameters in scope for EXPR. */ 588 589static tree 590build_parameter_mapping (tree expr, tree args, tree ctx_parms) 591{ 592 tree parms = find_template_parameters (expr, ctx_parms); 593 tree map = map_arguments (parms, args); 594 return map; 595} 596 597/* True if the parameter mappings of two atomic constraints formed 598 from the same expression are equivalent. */ 599 600static bool 601parameter_mapping_equivalent_p (tree t1, tree t2) 602{ 603 tree map1 = ATOMIC_CONSTR_MAP (t1); 604 tree map2 = ATOMIC_CONSTR_MAP (t2); 605 while (map1 && map2) 606 { 607 gcc_checking_assert (TREE_VALUE (map1) == TREE_VALUE (map2)); 608 tree arg1 = TREE_PURPOSE (map1); 609 tree arg2 = TREE_PURPOSE (map2); 610 if (!template_args_equal (arg1, arg2)) 611 return false; 612 map1 = TREE_CHAIN (map1); 613 map2 = TREE_CHAIN (map2); 614 } 615 gcc_checking_assert (!map1 && !map2); 616 return true; 617} 618 619/* Provides additional context for normalization. */ 620 621struct norm_info : subst_info 622{ 623 explicit norm_info (tsubst_flags_t cmp) 624 : norm_info (NULL_TREE, cmp) 625 {} 626 627 /* Construct a top-level context for DECL. */ 628 629 norm_info (tree in_decl, tsubst_flags_t complain) 630 : subst_info (tf_warning_or_error | complain, in_decl) 631 { 632 if (in_decl) 633 { 634 initial_parms = DECL_TEMPLATE_PARMS (in_decl); 635 if (generate_diagnostics ()) 636 context = build_tree_list (NULL_TREE, in_decl); 637 } 638 else 639 initial_parms = current_template_parms; 640 } 641 642 bool generate_diagnostics() const 643 { 644 return complain & tf_norm; 645 } 646 647 void update_context(tree expr, tree args) 648 { 649 if (generate_diagnostics ()) 650 { 651 tree map = build_parameter_mapping (expr, args, ctx_parms ()); 652 context = tree_cons (map, expr, context); 653 } 654 in_decl = get_concept_check_template (expr); 655 } 656 657 /* Returns the template parameters that are in scope for the current 658 normalization context. */ 659 660 tree ctx_parms() 661 { 662 if (in_decl) 663 return DECL_TEMPLATE_PARMS (in_decl); 664 else 665 return initial_parms; 666 } 667 668 /* Provides information about the source of a constraint. This is a 669 TREE_LIST whose VALUE is either a concept check or a constrained 670 declaration. The PURPOSE, for concept checks is a parameter mapping 671 for that check. */ 672 673 tree context = NULL_TREE; 674 675 /* The declaration whose constraints we're normalizing. The targets 676 of the parameter mapping of each atom will be in terms of the 677 template parameters of ORIG_DECL. */ 678 679 tree initial_parms = NULL_TREE; 680}; 681 682static tree normalize_expression (tree, tree, norm_info); 683 684/* Transform a logical-or or logical-and expression into either 685 a conjunction or disjunction. */ 686 687static tree 688normalize_logical_operation (tree t, tree args, tree_code c, norm_info info) 689{ 690 tree t0 = normalize_expression (TREE_OPERAND (t, 0), args, info); 691 tree t1 = normalize_expression (TREE_OPERAND (t, 1), args, info); 692 693 /* Build a new info object for the constraint. */ 694 tree ci = info.generate_diagnostics() 695 ? build_tree_list (t, info.context) 696 : NULL_TREE; 697 698 return build2 (c, ci, t0, t1); 699} 700 701static tree 702normalize_concept_check (tree check, tree args, norm_info info) 703{ 704 tree id = unpack_concept_check (check); 705 tree tmpl = TREE_OPERAND (id, 0); 706 tree targs = TREE_OPERAND (id, 1); 707 708 /* A function concept is wrapped in an overload. */ 709 if (TREE_CODE (tmpl) == OVERLOAD) 710 { 711 /* TODO: Can we diagnose this error during parsing? */ 712 if (TREE_CODE (check) == TEMPLATE_ID_EXPR) 713 error_at (EXPR_LOC_OR_LOC (check, input_location), 714 "function concept must be called"); 715 tmpl = OVL_FIRST (tmpl); 716 } 717 718 /* Substitute through the arguments of the concept check. */ 719 if (args) 720 targs = tsubst_template_args (targs, args, info.complain, info.in_decl); 721 if (targs == error_mark_node) 722 return error_mark_node; 723 724 /* Build the substitution for the concept definition. */ 725 tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl)); 726 /* Turn on template processing; coercing non-type template arguments 727 will automatically assume they're non-dependent. */ 728 ++processing_template_decl; 729 tree subst = coerce_template_parms (parms, targs, tmpl); 730 --processing_template_decl; 731 if (subst == error_mark_node) 732 return error_mark_node; 733 734 /* The concept may have been ill-formed. */ 735 tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl)); 736 if (def == error_mark_node) 737 return error_mark_node; 738 739 info.update_context (check, args); 740 return normalize_expression (def, subst, info); 741} 742 743/* Used by normalize_atom to cache ATOMIC_CONSTRs. */ 744 745static GTY((deletable)) hash_table<atom_hasher> *atom_cache; 746 747/* The normal form of an atom depends on the expression. The normal 748 form of a function call to a function concept is a check constraint 749 for that concept. The normal form of a reference to a variable 750 concept is a check constraint for that concept. Otherwise, the 751 constraint is a predicate constraint. */ 752 753static tree 754normalize_atom (tree t, tree args, norm_info info) 755{ 756 /* Concept checks are not atomic. */ 757 if (concept_check_p (t)) 758 return normalize_concept_check (t, args, info); 759 760 /* Build the parameter mapping for the atom. */ 761 tree map = build_parameter_mapping (t, args, info.ctx_parms ()); 762 763 /* Build a new info object for the atom. */ 764 tree ci = build_tree_list (t, info.context); 765 766 tree atom = build1 (ATOMIC_CONSTR, ci, map); 767 768 /* Remember whether the expression of this atomic constraint belongs to 769 a concept definition by inspecting in_decl, which should always be set 770 in this case either by norm_info::update_context (when recursing into a 771 concept-id during normalization) or by normalize_concept_definition 772 (when starting out with a concept-id). */ 773 if (info.in_decl && concept_definition_p (info.in_decl)) 774 ATOMIC_CONSTR_EXPR_FROM_CONCEPT_P (atom) = true; 775 776 if (!info.generate_diagnostics ()) 777 { 778 /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal 779 later can cheaply compare two atoms using just pointer equality. */ 780 if (!atom_cache) 781 atom_cache = hash_table<atom_hasher>::create_ggc (31); 782 tree *slot = atom_cache->find_slot (atom, INSERT); 783 if (*slot) 784 return *slot; 785 786 /* Find all template parameters used in the targets of the parameter 787 mapping, and store a list of them in the TREE_TYPE of the mapping. 788 This list will be used by sat_hasher to determine the subset of 789 supplied template arguments that the satisfaction value of the atom 790 depends on. */ 791 if (map) 792 { 793 tree targets = make_tree_vec (list_length (map)); 794 int i = 0; 795 for (tree node = map; node; node = TREE_CHAIN (node)) 796 { 797 tree target = TREE_PURPOSE (node); 798 TREE_VEC_ELT (targets, i++) = target; 799 } 800 tree target_parms = find_template_parameters (targets, 801 info.initial_parms); 802 TREE_TYPE (map) = target_parms; 803 } 804 805 *slot = atom; 806 } 807 return atom; 808} 809 810/* Returns the normal form of an expression. */ 811 812static tree 813normalize_expression (tree t, tree args, norm_info info) 814{ 815 if (!t) 816 return NULL_TREE; 817 818 if (t == error_mark_node) 819 return error_mark_node; 820 821 switch (TREE_CODE (t)) 822 { 823 case TRUTH_ANDIF_EXPR: 824 return normalize_logical_operation (t, args, CONJ_CONSTR, info); 825 case TRUTH_ORIF_EXPR: 826 return normalize_logical_operation (t, args, DISJ_CONSTR, info); 827 default: 828 return normalize_atom (t, args, info); 829 } 830} 831 832/* Cache of the normalized form of constraints. Marked as deletable because it 833 can all be recalculated. */ 834static GTY((deletable)) hash_map<tree,tree> *normalized_map; 835 836static tree 837get_normalized_constraints (tree t, norm_info info) 838{ 839 auto_timevar time (TV_CONSTRAINT_NORM); 840 return normalize_expression (t, NULL_TREE, info); 841} 842 843/* Returns the normalized constraints from a constraint-info object 844 or NULL_TREE if the constraints are null. IN_DECL provides the 845 declaration to which the constraints belong. */ 846 847static tree 848get_normalized_constraints_from_info (tree ci, tree in_decl, bool diag = false) 849{ 850 if (ci == NULL_TREE) 851 return NULL_TREE; 852 853 /* Substitution errors during normalization are fatal. */ 854 ++processing_template_decl; 855 norm_info info (in_decl, diag ? tf_norm : tf_none); 856 tree t = get_normalized_constraints (CI_ASSOCIATED_CONSTRAINTS (ci), info); 857 --processing_template_decl; 858 859 return t; 860} 861 862/* Returns the normalized constraints for the declaration D. */ 863 864static tree 865get_normalized_constraints_from_decl (tree d, bool diag = false) 866{ 867 tree tmpl; 868 tree decl; 869 870 /* For inherited constructors, consider the original declaration; 871 it has the correct template information attached. */ 872 d = strip_inheriting_ctors (d); 873 874 if (regenerated_lambda_fn_p (d)) 875 { 876 /* If this lambda was regenerated, DECL_TEMPLATE_PARMS doesn't contain 877 all in-scope template parameters, but the lambda from which it was 878 ultimately regenerated does, so use that instead. */ 879 tree lambda = CLASSTYPE_LAMBDA_EXPR (DECL_CONTEXT (d)); 880 lambda = most_general_lambda (lambda); 881 d = lambda_function (lambda); 882 } 883 884 if (TREE_CODE (d) == TEMPLATE_DECL) 885 { 886 tmpl = d; 887 decl = DECL_TEMPLATE_RESULT (tmpl); 888 } 889 else 890 { 891 if (tree ti = DECL_TEMPLATE_INFO (d)) 892 tmpl = TI_TEMPLATE (ti); 893 else 894 tmpl = NULL_TREE; 895 decl = d; 896 } 897 898 /* Get the most general template for the declaration, and compute 899 arguments from that. This ensures that the arguments used for 900 normalization are always template parameters and not arguments 901 used for outer specializations. For example: 902 903 template<typename T> 904 struct S { 905 template<typename U> requires C<T, U> void f(U); 906 }; 907 908 S<int>::f(0); 909 910 When we normalize the requirements for S<int>::f, we want the 911 arguments to be {T, U}, not {int, U}. One reason for this is that 912 accepting the latter causes the template parameter level of U 913 to be reduced in a way that makes it overly difficult substitute 914 concrete arguments (i.e., eventually {int, int} during satisfaction. */ 915 if (tmpl) 916 { 917 if (DECL_LANG_SPECIFIC(tmpl) && !DECL_TEMPLATE_SPECIALIZATION (tmpl)) 918 tmpl = most_general_template (tmpl); 919 } 920 921 d = tmpl ? tmpl : decl; 922 923 /* If we're not diagnosing errors, use cached constraints, if any. */ 924 if (!diag) 925 if (tree *p = hash_map_safe_get (normalized_map, d)) 926 return *p; 927 928 tree norm = NULL_TREE; 929 if (tree ci = get_constraints (d)) 930 { 931 push_access_scope_guard pas (decl); 932 norm = get_normalized_constraints_from_info (ci, tmpl, diag); 933 } 934 935 if (!diag) 936 hash_map_safe_put<hm_ggc> (normalized_map, d, norm); 937 938 return norm; 939} 940 941/* Returns the normal form of TMPL's definition. */ 942 943static tree 944normalize_concept_definition (tree tmpl, bool diag = false) 945{ 946 if (!diag) 947 if (tree *p = hash_map_safe_get (normalized_map, tmpl)) 948 return *p; 949 950 gcc_assert (concept_definition_p (tmpl)); 951 if (OVL_P (tmpl)) 952 tmpl = OVL_FIRST (tmpl); 953 gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL); 954 tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl)); 955 ++processing_template_decl; 956 norm_info info (tmpl, diag ? tf_norm : tf_none); 957 tree norm = get_normalized_constraints (def, info); 958 --processing_template_decl; 959 960 if (!diag) 961 hash_map_safe_put<hm_ggc> (normalized_map, tmpl, norm); 962 963 return norm; 964} 965 966/* Normalize an EXPR as a constraint. */ 967 968static tree 969normalize_constraint_expression (tree expr, norm_info info) 970{ 971 if (!expr || expr == error_mark_node) 972 return expr; 973 974 if (!info.generate_diagnostics ()) 975 if (tree *p = hash_map_safe_get (normalized_map, expr)) 976 return *p; 977 978 ++processing_template_decl; 979 tree norm = get_normalized_constraints (expr, info); 980 --processing_template_decl; 981 982 if (!info.generate_diagnostics ()) 983 hash_map_safe_put<hm_ggc> (normalized_map, expr, norm); 984 985 return norm; 986} 987 988/* 17.4.1.2p2. Two constraints are identical if they are formed 989 from the same expression and the targets of the parameter mapping 990 are equivalent. */ 991 992bool 993atomic_constraints_identical_p (tree t1, tree t2) 994{ 995 gcc_assert (TREE_CODE (t1) == ATOMIC_CONSTR); 996 gcc_assert (TREE_CODE (t2) == ATOMIC_CONSTR); 997 998 if (ATOMIC_CONSTR_EXPR (t1) != ATOMIC_CONSTR_EXPR (t2)) 999 return false; 1000 1001 if (!parameter_mapping_equivalent_p (t1, t2)) 1002 return false; 1003 1004 return true; 1005} 1006 1007/* True if T1 and T2 are equivalent, meaning they have the same syntactic 1008 structure and all corresponding constraints are identical. */ 1009 1010bool 1011constraints_equivalent_p (tree t1, tree t2) 1012{ 1013 gcc_assert (CONSTR_P (t1)); 1014 gcc_assert (CONSTR_P (t2)); 1015 1016 if (TREE_CODE (t1) != TREE_CODE (t2)) 1017 return false; 1018 1019 switch (TREE_CODE (t1)) 1020 { 1021 case CONJ_CONSTR: 1022 case DISJ_CONSTR: 1023 if (!constraints_equivalent_p (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0))) 1024 return false; 1025 if (!constraints_equivalent_p (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1))) 1026 return false; 1027 break; 1028 case ATOMIC_CONSTR: 1029 if (!atomic_constraints_identical_p(t1, t2)) 1030 return false; 1031 break; 1032 default: 1033 gcc_unreachable (); 1034 } 1035 return true; 1036} 1037 1038/* Compute the hash value for T. */ 1039 1040hashval_t 1041hash_atomic_constraint (tree t) 1042{ 1043 gcc_assert (TREE_CODE (t) == ATOMIC_CONSTR); 1044 1045 /* Hash the identity of the expression. */ 1046 hashval_t val = htab_hash_pointer (ATOMIC_CONSTR_EXPR (t)); 1047 1048 /* Hash the targets of the parameter map. */ 1049 tree p = ATOMIC_CONSTR_MAP (t); 1050 while (p) 1051 { 1052 val = iterative_hash_template_arg (TREE_PURPOSE (p), val); 1053 p = TREE_CHAIN (p); 1054 } 1055 1056 return val; 1057} 1058 1059namespace inchash 1060{ 1061 1062static void 1063add_constraint (tree t, hash& h) 1064{ 1065 h.add_int(TREE_CODE (t)); 1066 switch (TREE_CODE (t)) 1067 { 1068 case CONJ_CONSTR: 1069 case DISJ_CONSTR: 1070 add_constraint (TREE_OPERAND (t, 0), h); 1071 add_constraint (TREE_OPERAND (t, 1), h); 1072 break; 1073 case ATOMIC_CONSTR: 1074 h.merge_hash (hash_atomic_constraint (t)); 1075 break; 1076 default: 1077 gcc_unreachable (); 1078 } 1079} 1080 1081} 1082 1083/* Computes a hash code for the constraint T. */ 1084 1085hashval_t 1086iterative_hash_constraint (tree t, hashval_t val) 1087{ 1088 gcc_assert (CONSTR_P (t)); 1089 inchash::hash h (val); 1090 inchash::add_constraint (t, h); 1091 return h.end (); 1092} 1093 1094// -------------------------------------------------------------------------- // 1095// Constraint Semantic Processing 1096// 1097// The following functions are called by the parser and substitution rules 1098// to create and evaluate constraint-related nodes. 1099 1100// The constraints associated with the current template parameters. 1101tree 1102current_template_constraints (void) 1103{ 1104 if (!current_template_parms) 1105 return NULL_TREE; 1106 tree tmpl_constr = TEMPLATE_PARMS_CONSTRAINTS (current_template_parms); 1107 return build_constraints (tmpl_constr, NULL_TREE); 1108} 1109 1110/* If the recently parsed TYPE declares or defines a template or 1111 template specialization, get its corresponding constraints from the 1112 current template parameters and bind them to TYPE's declaration. */ 1113 1114tree 1115associate_classtype_constraints (tree type) 1116{ 1117 if (!type || type == error_mark_node || !CLASS_TYPE_P (type)) 1118 return type; 1119 1120 /* An explicit class template specialization has no template parameters. */ 1121 if (!current_template_parms) 1122 return type; 1123 1124 if (CLASSTYPE_IS_TEMPLATE (type) || CLASSTYPE_TEMPLATE_SPECIALIZATION (type)) 1125 { 1126 tree decl = TYPE_STUB_DECL (type); 1127 tree ci = current_template_constraints (); 1128 1129 /* An implicitly instantiated member template declaration already 1130 has associated constraints. If it is defined outside of its 1131 class, then we need match these constraints against those of 1132 original declaration. */ 1133 if (tree orig_ci = get_constraints (decl)) 1134 { 1135 if (int extra_levels = (TMPL_PARMS_DEPTH (current_template_parms) 1136 - TMPL_ARGS_DEPTH (TYPE_TI_ARGS (type)))) 1137 { 1138 /* If there is a discrepancy between the current template depth 1139 and the template depth of the original declaration, then we 1140 must be redeclaring a class template as part of a friend 1141 declaration within another class template. Before matching 1142 constraints, we need to reduce the template parameter level 1143 within the current constraints via substitution. */ 1144 tree outer_gtargs = template_parms_to_args (current_template_parms); 1145 TREE_VEC_LENGTH (outer_gtargs) = extra_levels; 1146 ci = tsubst_constraint_info (ci, outer_gtargs, tf_none, NULL_TREE); 1147 } 1148 if (!equivalent_constraints (ci, orig_ci)) 1149 { 1150 error ("%qT does not match original declaration", type); 1151 tree tmpl = CLASSTYPE_TI_TEMPLATE (type); 1152 location_t loc = DECL_SOURCE_LOCATION (tmpl); 1153 inform (loc, "original template declaration here"); 1154 /* Fall through, so that we define the type anyway. */ 1155 } 1156 return type; 1157 } 1158 set_constraints (decl, ci); 1159 } 1160 return type; 1161} 1162 1163/* Create an empty constraint info block. */ 1164 1165static inline tree_constraint_info* 1166build_constraint_info () 1167{ 1168 return (tree_constraint_info *)make_node (CONSTRAINT_INFO); 1169} 1170 1171/* Build a constraint-info object that contains the associated constraints 1172 of a declaration. This also includes the declaration's template 1173 requirements (TREQS) and any trailing requirements for a function 1174 declarator (DREQS). Note that both TREQS and DREQS must be constraints. 1175 1176 If the declaration has neither template nor declaration requirements 1177 this returns NULL_TREE, indicating an unconstrained declaration. */ 1178 1179tree 1180build_constraints (tree tr, tree dr) 1181{ 1182 if (!tr && !dr) 1183 return NULL_TREE; 1184 1185 tree_constraint_info* ci = build_constraint_info (); 1186 ci->template_reqs = tr; 1187 ci->declarator_reqs = dr; 1188 ci->associated_constr = combine_constraint_expressions (tr, dr); 1189 1190 return (tree)ci; 1191} 1192 1193/* Add constraint RHS to the end of CONSTRAINT_INFO ci. */ 1194 1195tree 1196append_constraint (tree ci, tree rhs) 1197{ 1198 tree tr = ci ? CI_TEMPLATE_REQS (ci) : NULL_TREE; 1199 tree dr = ci ? CI_DECLARATOR_REQS (ci) : NULL_TREE; 1200 dr = combine_constraint_expressions (dr, rhs); 1201 if (ci) 1202 { 1203 CI_DECLARATOR_REQS (ci) = dr; 1204 tree ac = combine_constraint_expressions (tr, dr); 1205 CI_ASSOCIATED_CONSTRAINTS (ci) = ac; 1206 } 1207 else 1208 ci = build_constraints (tr, dr); 1209 return ci; 1210} 1211 1212/* A mapping from declarations to constraint information. */ 1213 1214static GTY ((cache)) decl_tree_cache_map *decl_constraints; 1215 1216/* Returns the template constraints of declaration T. If T is not 1217 constrained, return NULL_TREE. Note that T must be non-null. */ 1218 1219tree 1220get_constraints (const_tree t) 1221{ 1222 if (!flag_concepts) 1223 return NULL_TREE; 1224 if (!decl_constraints) 1225 return NULL_TREE; 1226 1227 gcc_assert (DECL_P (t)); 1228 if (TREE_CODE (t) == TEMPLATE_DECL) 1229 t = DECL_TEMPLATE_RESULT (t); 1230 tree* found = decl_constraints->get (CONST_CAST_TREE (t)); 1231 if (found) 1232 return *found; 1233 else 1234 return NULL_TREE; 1235} 1236 1237/* Associate the given constraint information CI with the declaration 1238 T. If T is a template, then the constraints are associated with 1239 its underlying declaration. Don't build associations if CI is 1240 NULL_TREE. */ 1241 1242void 1243set_constraints (tree t, tree ci) 1244{ 1245 if (!ci) 1246 return; 1247 gcc_assert (t && flag_concepts); 1248 if (TREE_CODE (t) == TEMPLATE_DECL) 1249 t = DECL_TEMPLATE_RESULT (t); 1250 bool found = hash_map_safe_put<hm_ggc> (decl_constraints, t, ci); 1251 gcc_assert (!found); 1252} 1253 1254/* Remove the associated constraints of the declaration T. */ 1255 1256void 1257remove_constraints (tree t) 1258{ 1259 gcc_checking_assert (DECL_P (t)); 1260 if (TREE_CODE (t) == TEMPLATE_DECL) 1261 t = DECL_TEMPLATE_RESULT (t); 1262 1263 if (decl_constraints) 1264 decl_constraints->remove (t); 1265} 1266 1267/* If DECL is a friend, substitute into REQS to produce requirements suitable 1268 for declaration matching. */ 1269 1270tree 1271maybe_substitute_reqs_for (tree reqs, const_tree decl) 1272{ 1273 if (reqs == NULL_TREE) 1274 return NULL_TREE; 1275 1276 decl = STRIP_TEMPLATE (decl); 1277 if (DECL_UNIQUE_FRIEND_P (decl) && DECL_TEMPLATE_INFO (decl)) 1278 { 1279 tree tmpl = DECL_TI_TEMPLATE (decl); 1280 tree outer_args = outer_template_args (tmpl); 1281 processing_template_decl_sentinel s; 1282 if (PRIMARY_TEMPLATE_P (tmpl) 1283 || uses_template_parms (outer_args)) 1284 ++processing_template_decl; 1285 reqs = tsubst_constraint (reqs, outer_args, 1286 tf_warning_or_error, NULL_TREE); 1287 } 1288 return reqs; 1289} 1290 1291/* Returns the trailing requires clause of the declarator of 1292 a template declaration T or NULL_TREE if none. */ 1293 1294tree 1295get_trailing_function_requirements (tree t) 1296{ 1297 tree ci = get_constraints (t); 1298 if (!ci) 1299 return NULL_TREE; 1300 return CI_DECLARATOR_REQS (ci); 1301} 1302 1303/* Construct a sequence of template arguments by prepending 1304 ARG to REST. Either ARG or REST may be null. */ 1305static tree 1306build_concept_check_arguments (tree arg, tree rest) 1307{ 1308 gcc_assert (rest ? TREE_CODE (rest) == TREE_VEC : true); 1309 tree args; 1310 if (arg) 1311 { 1312 int n = rest ? TREE_VEC_LENGTH (rest) : 0; 1313 args = make_tree_vec (n + 1); 1314 TREE_VEC_ELT (args, 0) = arg; 1315 if (rest) 1316 for (int i = 0; i < n; ++i) 1317 TREE_VEC_ELT (args, i + 1) = TREE_VEC_ELT (rest, i); 1318 int def = rest ? GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (rest) : 0; 1319 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args, def + 1); 1320 } 1321 else 1322 { 1323 args = rest; 1324 } 1325 return args; 1326} 1327 1328/* Builds an id-expression of the form `C<Args...>()` where C is a function 1329 concept. */ 1330 1331static tree 1332build_function_check (tree tmpl, tree args, tsubst_flags_t /*complain*/) 1333{ 1334 if (TREE_CODE (tmpl) == TEMPLATE_DECL) 1335 { 1336 /* If we just got a template, wrap it in an overload so it looks like any 1337 other template-id. */ 1338 tmpl = ovl_make (tmpl); 1339 TREE_TYPE (tmpl) = boolean_type_node; 1340 } 1341 1342 /* Perform function concept resolution now so we always have a single 1343 function of the overload set (even if we started with only one; the 1344 resolution function converts template arguments). Note that we still 1345 wrap this in an overload set so we don't upset other parts of the 1346 compiler that expect template-ids referring to function concepts 1347 to have an overload set. */ 1348 tree info = resolve_function_concept_overload (tmpl, args); 1349 if (info == error_mark_node) 1350 return error_mark_node; 1351 if (!info) 1352 { 1353 error ("no matching concepts for %qE", tmpl); 1354 return error_mark_node; 1355 } 1356 args = TREE_PURPOSE (info); 1357 tmpl = DECL_TI_TEMPLATE (TREE_VALUE (info)); 1358 1359 /* Rebuild the singleton overload set; mark the type bool. */ 1360 tmpl = ovl_make (tmpl, NULL_TREE); 1361 TREE_TYPE (tmpl) = boolean_type_node; 1362 1363 /* Build the id-expression around the overload set. */ 1364 tree id = build2 (TEMPLATE_ID_EXPR, boolean_type_node, tmpl, args); 1365 1366 /* Finally, build the call expression around the overload. */ 1367 ++processing_template_decl; 1368 vec<tree, va_gc> *fargs = make_tree_vector (); 1369 tree call = build_min_nt_call_vec (id, fargs); 1370 TREE_TYPE (call) = boolean_type_node; 1371 release_tree_vector (fargs); 1372 --processing_template_decl; 1373 1374 return call; 1375} 1376 1377/* Builds an id-expression of the form `C<Args...>` where C is a variable 1378 concept. */ 1379 1380static tree 1381build_variable_check (tree tmpl, tree args, tsubst_flags_t complain) 1382{ 1383 gcc_assert (variable_concept_p (tmpl)); 1384 gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL); 1385 tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl)); 1386 args = coerce_template_parms (parms, args, tmpl, complain); 1387 if (args == error_mark_node) 1388 return error_mark_node; 1389 return build2 (TEMPLATE_ID_EXPR, boolean_type_node, tmpl, args); 1390} 1391 1392/* Builds an id-expression of the form `C<Args...>` where C is a standard 1393 concept. */ 1394 1395static tree 1396build_standard_check (tree tmpl, tree args, tsubst_flags_t complain) 1397{ 1398 gcc_assert (standard_concept_p (tmpl)); 1399 gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL); 1400 tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl)); 1401 args = coerce_template_parms (parms, args, tmpl, complain); 1402 if (args == error_mark_node) 1403 return error_mark_node; 1404 return build2 (TEMPLATE_ID_EXPR, boolean_type_node, tmpl, args); 1405} 1406 1407/* Construct an expression that checks TARGET using ARGS. */ 1408 1409tree 1410build_concept_check (tree target, tree args, tsubst_flags_t complain) 1411{ 1412 return build_concept_check (target, NULL_TREE, args, complain); 1413} 1414 1415/* Construct an expression that checks the concept given by DECL. If 1416 concept_definition_p (DECL) is false, this returns null. */ 1417 1418tree 1419build_concept_check (tree decl, tree arg, tree rest, tsubst_flags_t complain) 1420{ 1421 tree args = build_concept_check_arguments (arg, rest); 1422 1423 if (standard_concept_p (decl)) 1424 return build_standard_check (decl, args, complain); 1425 if (variable_concept_p (decl)) 1426 return build_variable_check (decl, args, complain); 1427 if (function_concept_p (decl)) 1428 return build_function_check (decl, args, complain); 1429 1430 return error_mark_node; 1431} 1432 1433/* Build a template-id that can participate in a concept check. */ 1434 1435static tree 1436build_concept_id (tree decl, tree args) 1437{ 1438 tree check = build_concept_check (decl, args, tf_warning_or_error); 1439 if (check == error_mark_node) 1440 return error_mark_node; 1441 return unpack_concept_check (check); 1442} 1443 1444/* Build a template-id that can participate in a concept check, preserving 1445 the source location of the original template-id. */ 1446 1447tree 1448build_concept_id (tree expr) 1449{ 1450 gcc_assert (TREE_CODE (expr) == TEMPLATE_ID_EXPR); 1451 tree id = build_concept_id (TREE_OPERAND (expr, 0), TREE_OPERAND (expr, 1)); 1452 protected_set_expr_location (id, cp_expr_location (expr)); 1453 return id; 1454} 1455 1456/* Build as template-id with a placeholder that can be used as a 1457 type constraint. 1458 1459 Note that this will diagnose errors if the initial concept check 1460 cannot be built. */ 1461 1462tree 1463build_type_constraint (tree decl, tree args, tsubst_flags_t complain) 1464{ 1465 tree wildcard = build_nt (WILDCARD_DECL); 1466 ++processing_template_decl; 1467 tree check = build_concept_check (decl, wildcard, args, complain); 1468 --processing_template_decl; 1469 if (check == error_mark_node) 1470 return error_mark_node; 1471 return unpack_concept_check (check); 1472} 1473 1474/* Returns a TYPE_DECL that contains sufficient information to 1475 build a template parameter of the same kind as PROTO and 1476 constrained by the concept declaration CNC. Note that PROTO 1477 is the first template parameter of CNC. 1478 1479 If specified, ARGS provides additional arguments to the 1480 constraint check. */ 1481tree 1482build_constrained_parameter (tree cnc, tree proto, tree args) 1483{ 1484 tree name = DECL_NAME (cnc); 1485 tree type = TREE_TYPE (proto); 1486 tree decl = build_decl (input_location, TYPE_DECL, name, type); 1487 CONSTRAINED_PARM_PROTOTYPE (decl) = proto; 1488 CONSTRAINED_PARM_CONCEPT (decl) = cnc; 1489 CONSTRAINED_PARM_EXTRA_ARGS (decl) = args; 1490 return decl; 1491} 1492 1493/* Create a constraint expression for the given DECL that evaluates the 1494 requirements specified by CONSTR, a TYPE_DECL that contains all the 1495 information necessary to build the requirements (see finish_concept_name 1496 for the layout of that TYPE_DECL). 1497 1498 Note that the constraints are neither reduced nor decomposed. That is 1499 done only after the requires clause has been parsed (or not). */ 1500 1501tree 1502finish_shorthand_constraint (tree decl, tree constr) 1503{ 1504 /* No requirements means no constraints. */ 1505 if (!constr) 1506 return NULL_TREE; 1507 1508 if (error_operand_p (constr)) 1509 return NULL_TREE; 1510 1511 tree proto = CONSTRAINED_PARM_PROTOTYPE (constr); 1512 tree con = CONSTRAINED_PARM_CONCEPT (constr); 1513 tree args = CONSTRAINED_PARM_EXTRA_ARGS (constr); 1514 1515 /* The TS lets use shorthand to constrain a pack of arguments, but the 1516 standard does not. 1517 1518 For the TS, consider: 1519 1520 template<C... Ts> struct s; 1521 1522 If C is variadic (and because Ts is a pack), we associate the 1523 constraint C<Ts...>. In all other cases, we associate 1524 the constraint (C<Ts> && ...). 1525 1526 The standard behavior cannot be overridden by -fconcepts-ts. */ 1527 bool variadic_concept_p = template_parameter_pack_p (proto); 1528 bool declared_pack_p = template_parameter_pack_p (decl); 1529 bool apply_to_each_p = (cxx_dialect >= cxx20) ? true : !variadic_concept_p; 1530 1531 /* Get the argument and overload used for the requirement 1532 and adjust it if we're going to expand later. */ 1533 tree arg = template_parm_to_arg (decl); 1534 if (apply_to_each_p && declared_pack_p) 1535 arg = PACK_EXPANSION_PATTERN (TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg), 0)); 1536 1537 /* Build the concept constraint-expression. */ 1538 tree tmpl = DECL_TI_TEMPLATE (con); 1539 tree check = tmpl; 1540 if (TREE_CODE (con) == FUNCTION_DECL) 1541 check = ovl_make (tmpl); 1542 check = build_concept_check (check, arg, args, tf_warning_or_error); 1543 1544 /* Make the check a fold-expression if needed. */ 1545 if (apply_to_each_p && declared_pack_p) 1546 check = finish_left_unary_fold_expr (check, TRUTH_ANDIF_EXPR); 1547 1548 return check; 1549} 1550 1551/* Returns a conjunction of shorthand requirements for the template 1552 parameter list PARMS. Note that the requirements are stored in 1553 the TYPE of each tree node. */ 1554 1555tree 1556get_shorthand_constraints (tree parms) 1557{ 1558 tree result = NULL_TREE; 1559 parms = INNERMOST_TEMPLATE_PARMS (parms); 1560 for (int i = 0; i < TREE_VEC_LENGTH (parms); ++i) 1561 { 1562 tree parm = TREE_VEC_ELT (parms, i); 1563 tree constr = TEMPLATE_PARM_CONSTRAINTS (parm); 1564 result = combine_constraint_expressions (result, constr); 1565 } 1566 return result; 1567} 1568 1569/* Get the deduced wildcard from a DEDUCED placeholder. If the deduced 1570 wildcard is a pack, return the first argument of that pack. */ 1571 1572static tree 1573get_deduced_wildcard (tree wildcard) 1574{ 1575 if (ARGUMENT_PACK_P (wildcard)) 1576 wildcard = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (wildcard), 0); 1577 gcc_assert (TREE_CODE (wildcard) == WILDCARD_DECL); 1578 return wildcard; 1579} 1580 1581/* Returns the prototype parameter for the nth deduced wildcard. */ 1582 1583static tree 1584get_introduction_prototype (tree wildcards, int index) 1585{ 1586 return TREE_TYPE (get_deduced_wildcard (TREE_VEC_ELT (wildcards, index))); 1587} 1588 1589/* Introduce a type template parameter. */ 1590 1591static tree 1592introduce_type_template_parameter (tree wildcard, bool& non_type_p) 1593{ 1594 non_type_p = false; 1595 return finish_template_type_parm (class_type_node, DECL_NAME (wildcard)); 1596} 1597 1598/* Introduce a template template parameter. */ 1599 1600static tree 1601introduce_template_template_parameter (tree wildcard, bool& non_type_p) 1602{ 1603 non_type_p = false; 1604 begin_template_parm_list (); 1605 current_template_parms = DECL_TEMPLATE_PARMS (TREE_TYPE (wildcard)); 1606 end_template_parm_list (); 1607 return finish_template_template_parm (class_type_node, DECL_NAME (wildcard)); 1608} 1609 1610/* Introduce a template non-type parameter. */ 1611 1612static tree 1613introduce_nontype_template_parameter (tree wildcard, bool& non_type_p) 1614{ 1615 non_type_p = true; 1616 tree parm = copy_decl (TREE_TYPE (wildcard)); 1617 DECL_NAME (parm) = DECL_NAME (wildcard); 1618 return parm; 1619} 1620 1621/* Introduce a single template parameter. */ 1622 1623static tree 1624build_introduced_template_parameter (tree wildcard, bool& non_type_p) 1625{ 1626 tree proto = TREE_TYPE (wildcard); 1627 1628 tree parm; 1629 if (TREE_CODE (proto) == TYPE_DECL) 1630 parm = introduce_type_template_parameter (wildcard, non_type_p); 1631 else if (TREE_CODE (proto) == TEMPLATE_DECL) 1632 parm = introduce_template_template_parameter (wildcard, non_type_p); 1633 else 1634 parm = introduce_nontype_template_parameter (wildcard, non_type_p); 1635 1636 /* Wrap in a TREE_LIST for process_template_parm. Note that introduced 1637 parameters do not retain the defaults from the source parameter. */ 1638 return build_tree_list (NULL_TREE, parm); 1639} 1640 1641/* Introduce a single template parameter. */ 1642 1643static tree 1644introduce_template_parameter (tree parms, tree wildcard) 1645{ 1646 gcc_assert (!ARGUMENT_PACK_P (wildcard)); 1647 tree proto = TREE_TYPE (wildcard); 1648 location_t loc = DECL_SOURCE_LOCATION (wildcard); 1649 1650 /* Diagnose the case where we have C{...Args}. */ 1651 if (WILDCARD_PACK_P (wildcard)) 1652 { 1653 tree id = DECL_NAME (wildcard); 1654 error_at (loc, "%qE cannot be introduced with an ellipsis %<...%>", id); 1655 inform (DECL_SOURCE_LOCATION (proto), "prototype declared here"); 1656 } 1657 1658 bool non_type_p; 1659 tree parm = build_introduced_template_parameter (wildcard, non_type_p); 1660 return process_template_parm (parms, loc, parm, non_type_p, false); 1661} 1662 1663/* Introduce a template parameter pack. */ 1664 1665static tree 1666introduce_template_parameter_pack (tree parms, tree wildcard) 1667{ 1668 bool non_type_p; 1669 tree parm = build_introduced_template_parameter (wildcard, non_type_p); 1670 location_t loc = DECL_SOURCE_LOCATION (wildcard); 1671 return process_template_parm (parms, loc, parm, non_type_p, true); 1672} 1673 1674/* Introduce the nth template parameter. */ 1675 1676static tree 1677introduce_template_parameter (tree parms, tree wildcards, int& index) 1678{ 1679 tree deduced = TREE_VEC_ELT (wildcards, index++); 1680 return introduce_template_parameter (parms, deduced); 1681} 1682 1683/* Introduce either a template parameter pack or a list of template 1684 parameters. */ 1685 1686static tree 1687introduce_template_parameters (tree parms, tree wildcards, int& index) 1688{ 1689 /* If the prototype was a parameter, we better have deduced an 1690 argument pack, and that argument must be the last deduced value 1691 in the wildcard vector. */ 1692 tree deduced = TREE_VEC_ELT (wildcards, index++); 1693 gcc_assert (ARGUMENT_PACK_P (deduced)); 1694 gcc_assert (index == TREE_VEC_LENGTH (wildcards)); 1695 1696 /* Introduce each element in the pack. */ 1697 tree args = ARGUMENT_PACK_ARGS (deduced); 1698 for (int i = 0; i < TREE_VEC_LENGTH (args); ++i) 1699 { 1700 tree arg = TREE_VEC_ELT (args, i); 1701 if (WILDCARD_PACK_P (arg)) 1702 parms = introduce_template_parameter_pack (parms, arg); 1703 else 1704 parms = introduce_template_parameter (parms, arg); 1705 } 1706 1707 return parms; 1708} 1709 1710/* Builds the template parameter list PARMS by chaining introduced 1711 parameters from the WILDCARD vector. INDEX is the position of 1712 the current parameter. */ 1713 1714static tree 1715process_introduction_parms (tree parms, tree wildcards, int& index) 1716{ 1717 tree proto = get_introduction_prototype (wildcards, index); 1718 if (template_parameter_pack_p (proto)) 1719 return introduce_template_parameters (parms, wildcards, index); 1720 else 1721 return introduce_template_parameter (parms, wildcards, index); 1722} 1723 1724/* Ensure that all template parameters have been introduced for the concept 1725 named in CHECK. If not, emit a diagnostic. 1726 1727 Note that implicitly introducing a parameter with a default argument 1728 creates a case where a parameter is declared, but unnamed, making 1729 it unusable in the definition. */ 1730 1731static bool 1732check_introduction_list (tree intros, tree check) 1733{ 1734 check = unpack_concept_check (check); 1735 tree tmpl = TREE_OPERAND (check, 0); 1736 if (OVL_P (tmpl)) 1737 tmpl = OVL_FIRST (tmpl); 1738 1739 tree parms = DECL_INNERMOST_TEMPLATE_PARMS (tmpl); 1740 if (TREE_VEC_LENGTH (intros) < TREE_VEC_LENGTH (parms)) 1741 { 1742 error_at (input_location, "all template parameters of %qD must " 1743 "be introduced", tmpl); 1744 return false; 1745 } 1746 1747 return true; 1748} 1749 1750/* Associates a constraint check to the current template based on the 1751 introduction parameters. INTRO_LIST must be a TREE_VEC of WILDCARD_DECLs 1752 containing a chained PARM_DECL which contains the identifier as well as 1753 the source location. TMPL_DECL is the decl for the concept being used. 1754 If we take a concept, C, this will form a check in the form of 1755 C<INTRO_LIST> filling in any extra arguments needed by the defaults 1756 deduced. 1757 1758 Returns NULL_TREE if no concept could be matched and error_mark_node if 1759 an error occurred when matching. */ 1760 1761tree 1762finish_template_introduction (tree tmpl_decl, 1763 tree intro_list, 1764 location_t intro_loc) 1765{ 1766 /* Build a concept check to deduce the actual parameters. */ 1767 tree expr = build_concept_check (tmpl_decl, intro_list, tf_none); 1768 if (expr == error_mark_node) 1769 { 1770 error_at (intro_loc, "cannot deduce template parameters from " 1771 "introduction list"); 1772 return error_mark_node; 1773 } 1774 1775 if (!check_introduction_list (intro_list, expr)) 1776 return error_mark_node; 1777 1778 tree parms = deduce_concept_introduction (expr); 1779 if (!parms) 1780 return NULL_TREE; 1781 1782 /* Build template parameter scope for introduction. */ 1783 tree parm_list = NULL_TREE; 1784 begin_template_parm_list (); 1785 int nargs = MIN (TREE_VEC_LENGTH (parms), TREE_VEC_LENGTH (intro_list)); 1786 for (int n = 0; n < nargs; ) 1787 parm_list = process_introduction_parms (parm_list, parms, n); 1788 parm_list = end_template_parm_list (parm_list); 1789 1790 /* Update the number of arguments to reflect the number of deduced 1791 template parameter introductions. */ 1792 nargs = TREE_VEC_LENGTH (parm_list); 1793 1794 /* Determine if any errors occurred during matching. */ 1795 for (int i = 0; i < TREE_VEC_LENGTH (parm_list); ++i) 1796 if (TREE_VALUE (TREE_VEC_ELT (parm_list, i)) == error_mark_node) 1797 { 1798 end_template_decl (); 1799 return error_mark_node; 1800 } 1801 1802 /* Build a concept check for our constraint. */ 1803 tree check_args = make_tree_vec (nargs); 1804 int n = 0; 1805 for (; n < TREE_VEC_LENGTH (parm_list); ++n) 1806 { 1807 tree parm = TREE_VEC_ELT (parm_list, n); 1808 TREE_VEC_ELT (check_args, n) = template_parm_to_arg (parm); 1809 } 1810 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (check_args, n); 1811 1812 /* If the template expects more parameters we should be able 1813 to use the defaults from our deduced concept. */ 1814 for (; n < TREE_VEC_LENGTH (parms); ++n) 1815 TREE_VEC_ELT (check_args, n) = TREE_VEC_ELT (parms, n); 1816 1817 /* Associate the constraint. */ 1818 tree check = build_concept_check (tmpl_decl, 1819 check_args, 1820 tf_warning_or_error); 1821 TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = check; 1822 1823 return parm_list; 1824} 1825 1826 1827/* Given the concept check T from a constrained-type-specifier, extract 1828 its TMPL and ARGS. FIXME why do we need two different forms of 1829 constrained-type-specifier? */ 1830 1831void 1832placeholder_extract_concept_and_args (tree t, tree &tmpl, tree &args) 1833{ 1834 if (concept_check_p (t)) 1835 { 1836 t = unpack_concept_check (t); 1837 tmpl = TREE_OPERAND (t, 0); 1838 if (TREE_CODE (tmpl) == OVERLOAD) 1839 tmpl = OVL_FIRST (tmpl); 1840 args = TREE_OPERAND (t, 1); 1841 return; 1842 } 1843 1844 if (TREE_CODE (t) == TYPE_DECL) 1845 { 1846 /* A constrained parameter. Build a constraint check 1847 based on the prototype parameter and then extract the 1848 arguments from that. */ 1849 tree proto = CONSTRAINED_PARM_PROTOTYPE (t); 1850 tree check = finish_shorthand_constraint (proto, t); 1851 placeholder_extract_concept_and_args (check, tmpl, args); 1852 return; 1853 } 1854} 1855 1856/* Returns true iff the placeholders C1 and C2 are equivalent. C1 1857 and C2 can be either TEMPLATE_TYPE_PARM or template-ids. */ 1858 1859bool 1860equivalent_placeholder_constraints (tree c1, tree c2) 1861{ 1862 if (c1 && TREE_CODE (c1) == TEMPLATE_TYPE_PARM) 1863 /* A constrained auto. */ 1864 c1 = PLACEHOLDER_TYPE_CONSTRAINTS (c1); 1865 if (c2 && TREE_CODE (c2) == TEMPLATE_TYPE_PARM) 1866 c2 = PLACEHOLDER_TYPE_CONSTRAINTS (c2); 1867 1868 if (c1 == c2) 1869 return true; 1870 if (!c1 || !c2) 1871 return false; 1872 if (c1 == error_mark_node || c2 == error_mark_node) 1873 /* We get here during satisfaction; when a deduction constraint 1874 fails, substitution can produce an error_mark_node for the 1875 placeholder constraints. */ 1876 return false; 1877 1878 tree t1, t2, a1, a2; 1879 placeholder_extract_concept_and_args (c1, t1, a1); 1880 placeholder_extract_concept_and_args (c2, t2, a2); 1881 1882 if (t1 != t2) 1883 return false; 1884 1885 int len1 = TREE_VEC_LENGTH (a1); 1886 int len2 = TREE_VEC_LENGTH (a2); 1887 if (len1 != len2) 1888 return false; 1889 1890 /* Skip the first argument so we don't infinitely recurse. 1891 Also, they may differ in template parameter index. */ 1892 for (int i = 1; i < len1; ++i) 1893 { 1894 tree t1 = TREE_VEC_ELT (a1, i); 1895 tree t2 = TREE_VEC_ELT (a2, i); 1896 if (!template_args_equal (t1, t2)) 1897 return false; 1898 } 1899 return true; 1900} 1901 1902/* Return a hash value for the placeholder ATOMIC_CONSTR C. */ 1903 1904hashval_t 1905hash_placeholder_constraint (tree c) 1906{ 1907 tree t, a; 1908 placeholder_extract_concept_and_args (c, t, a); 1909 1910 /* Like hash_tmpl_and_args, but skip the first argument. */ 1911 hashval_t val = iterative_hash_object (DECL_UID (t), 0); 1912 1913 for (int i = TREE_VEC_LENGTH (a)-1; i > 0; --i) 1914 val = iterative_hash_template_arg (TREE_VEC_ELT (a, i), val); 1915 1916 return val; 1917} 1918 1919/* Substitute through the expression of a simple requirement or 1920 compound requirement. */ 1921 1922static tree 1923tsubst_valid_expression_requirement (tree t, tree args, sat_info info) 1924{ 1925 tree r = tsubst_expr (t, args, tf_none, info.in_decl, false); 1926 if (convert_to_void (r, ICV_STATEMENT, tf_none) != error_mark_node) 1927 return r; 1928 1929 if (info.diagnose_unsatisfaction_p ()) 1930 { 1931 location_t loc = cp_expr_loc_or_input_loc (t); 1932 if (diagnosing_failed_constraint::replay_errors_p ()) 1933 { 1934 inform (loc, "the required expression %qE is invalid, because", t); 1935 if (r == error_mark_node) 1936 tsubst_expr (t, args, info.complain, info.in_decl, false); 1937 else 1938 convert_to_void (r, ICV_STATEMENT, info.complain); 1939 } 1940 else 1941 inform (loc, "the required expression %qE is invalid", t); 1942 } 1943 else if (info.noisy ()) 1944 { 1945 r = tsubst_expr (t, args, info.complain, info.in_decl, false); 1946 convert_to_void (r, ICV_STATEMENT, info.complain); 1947 } 1948 1949 return error_mark_node; 1950} 1951 1952 1953/* Substitute through the simple requirement. */ 1954 1955static tree 1956tsubst_simple_requirement (tree t, tree args, sat_info info) 1957{ 1958 tree t0 = TREE_OPERAND (t, 0); 1959 tree expr = tsubst_valid_expression_requirement (t0, args, info); 1960 if (expr == error_mark_node) 1961 return error_mark_node; 1962 return boolean_true_node; 1963} 1964 1965/* Subroutine of tsubst_type_requirement that performs the actual substitution 1966 and diagnosing. Also used by tsubst_compound_requirement. */ 1967 1968static tree 1969tsubst_type_requirement_1 (tree t, tree args, sat_info info, location_t loc) 1970{ 1971 tree r = tsubst (t, args, tf_none, info.in_decl); 1972 if (r != error_mark_node) 1973 return r; 1974 1975 if (info.diagnose_unsatisfaction_p ()) 1976 { 1977 if (diagnosing_failed_constraint::replay_errors_p ()) 1978 { 1979 /* Replay the substitution error. */ 1980 inform (loc, "the required type %qT is invalid, because", t); 1981 tsubst (t, args, info.complain, info.in_decl); 1982 } 1983 else 1984 inform (loc, "the required type %qT is invalid", t); 1985 } 1986 else if (info.noisy ()) 1987 tsubst (t, args, info.complain, info.in_decl); 1988 1989 return error_mark_node; 1990} 1991 1992 1993/* Substitute through the type requirement. */ 1994 1995static tree 1996tsubst_type_requirement (tree t, tree args, sat_info info) 1997{ 1998 tree t0 = TREE_OPERAND (t, 0); 1999 tree type = tsubst_type_requirement_1 (t0, args, info, EXPR_LOCATION (t)); 2000 if (type == error_mark_node) 2001 return error_mark_node; 2002 return boolean_true_node; 2003} 2004 2005/* True if TYPE can be deduced from EXPR. */ 2006 2007static bool 2008type_deducible_p (tree expr, tree type, tree placeholder, tree args, 2009 subst_info info) 2010{ 2011 /* Make sure deduction is performed against ( EXPR ), so that 2012 references are preserved in the result. */ 2013 expr = force_paren_expr_uneval (expr); 2014 2015 tree deduced_type = do_auto_deduction (type, expr, placeholder, 2016 info.complain, adc_requirement, 2017 /*outer_targs=*/args); 2018 2019 return deduced_type != error_mark_node; 2020} 2021 2022/* True if EXPR can not be converted to TYPE. */ 2023 2024static bool 2025expression_convertible_p (tree expr, tree type, subst_info info) 2026{ 2027 tree conv = 2028 perform_direct_initialization_if_possible (type, expr, false, 2029 info.complain); 2030 if (conv == error_mark_node) 2031 return false; 2032 if (conv == NULL_TREE) 2033 { 2034 if (info.complain & tf_error) 2035 { 2036 location_t loc = EXPR_LOC_OR_LOC (expr, input_location); 2037 error_at (loc, "cannot convert %qE to %qT", expr, type); 2038 } 2039 return false; 2040 } 2041 return true; 2042} 2043 2044 2045/* Substitute through the compound requirement. */ 2046 2047static tree 2048tsubst_compound_requirement (tree t, tree args, sat_info info) 2049{ 2050 tree t0 = TREE_OPERAND (t, 0); 2051 tree t1 = TREE_OPERAND (t, 1); 2052 tree expr = tsubst_valid_expression_requirement (t0, args, info); 2053 if (expr == error_mark_node) 2054 return error_mark_node; 2055 2056 location_t loc = cp_expr_loc_or_input_loc (expr); 2057 2058 /* Check the noexcept condition. */ 2059 bool noexcept_p = COMPOUND_REQ_NOEXCEPT_P (t); 2060 if (noexcept_p && !expr_noexcept_p (expr, tf_none)) 2061 { 2062 if (info.diagnose_unsatisfaction_p ()) 2063 inform (loc, "%qE is not %<noexcept%>", expr); 2064 else 2065 return error_mark_node; 2066 } 2067 2068 /* Substitute through the type expression, if any. */ 2069 tree type = tsubst_type_requirement_1 (t1, args, info, EXPR_LOCATION (t)); 2070 if (type == error_mark_node) 2071 return error_mark_node; 2072 2073 subst_info quiet (tf_none, info.in_decl); 2074 2075 /* Check expression against the result type. */ 2076 if (type) 2077 { 2078 if (tree placeholder = type_uses_auto (type)) 2079 { 2080 if (!type_deducible_p (expr, type, placeholder, args, quiet)) 2081 { 2082 if (info.diagnose_unsatisfaction_p ()) 2083 { 2084 if (diagnosing_failed_constraint::replay_errors_p ()) 2085 { 2086 inform (loc, 2087 "%qE does not satisfy return-type-requirement, " 2088 "because", t0); 2089 /* Further explain the reason for the error. */ 2090 type_deducible_p (expr, type, placeholder, args, info); 2091 } 2092 else 2093 inform (loc, 2094 "%qE does not satisfy return-type-requirement", t0); 2095 } 2096 return error_mark_node; 2097 } 2098 } 2099 else if (!expression_convertible_p (expr, type, quiet)) 2100 { 2101 if (info.diagnose_unsatisfaction_p ()) 2102 { 2103 if (diagnosing_failed_constraint::replay_errors_p ()) 2104 { 2105 inform (loc, "cannot convert %qE to %qT because", t0, type); 2106 /* Further explain the reason for the error. */ 2107 expression_convertible_p (expr, type, info); 2108 } 2109 else 2110 inform (loc, "cannot convert %qE to %qT", t0, type); 2111 } 2112 return error_mark_node; 2113 } 2114 } 2115 2116 return boolean_true_node; 2117} 2118 2119/* Substitute through the nested requirement. */ 2120 2121static tree 2122tsubst_nested_requirement (tree t, tree args, sat_info info) 2123{ 2124 sat_info quiet (tf_none, info.in_decl); 2125 tree result = constraint_satisfaction_value (t, args, quiet); 2126 if (result == boolean_true_node) 2127 return boolean_true_node; 2128 2129 if (result == boolean_false_node 2130 && info.diagnose_unsatisfaction_p ()) 2131 { 2132 tree expr = TREE_OPERAND (t, 0); 2133 location_t loc = cp_expr_location (t); 2134 if (diagnosing_failed_constraint::replay_errors_p ()) 2135 { 2136 /* Replay the substitution error. */ 2137 inform (loc, "nested requirement %qE is not satisfied, because", expr); 2138 constraint_satisfaction_value (t, args, info); 2139 } 2140 else 2141 inform (loc, "nested requirement %qE is not satisfied", expr); 2142 } 2143 2144 return error_mark_node; 2145} 2146 2147/* Substitute ARGS into the requirement T. */ 2148 2149static tree 2150tsubst_requirement (tree t, tree args, sat_info info) 2151{ 2152 iloc_sentinel loc_s (cp_expr_location (t)); 2153 switch (TREE_CODE (t)) 2154 { 2155 case SIMPLE_REQ: 2156 return tsubst_simple_requirement (t, args, info); 2157 case TYPE_REQ: 2158 return tsubst_type_requirement (t, args, info); 2159 case COMPOUND_REQ: 2160 return tsubst_compound_requirement (t, args, info); 2161 case NESTED_REQ: 2162 return tsubst_nested_requirement (t, args, info); 2163 default: 2164 break; 2165 } 2166 gcc_unreachable (); 2167} 2168 2169static tree 2170declare_constraint_vars (tree parms, tree vars) 2171{ 2172 tree s = vars; 2173 for (tree t = parms; t; t = DECL_CHAIN (t)) 2174 { 2175 if (DECL_PACK_P (t)) 2176 { 2177 tree pack = extract_fnparm_pack (t, &s); 2178 register_local_specialization (pack, t); 2179 } 2180 else 2181 { 2182 register_local_specialization (s, t); 2183 s = DECL_CHAIN (s); 2184 } 2185 } 2186 return vars; 2187} 2188 2189/* Substitute through as if checking function parameter types. This 2190 will diagnose common parameter type errors. Returns error_mark_node 2191 if an error occurred. */ 2192 2193static tree 2194check_constraint_variables (tree t, tree args, subst_info info) 2195{ 2196 tree types = NULL_TREE; 2197 tree p = t; 2198 while (p && !VOID_TYPE_P (p)) 2199 { 2200 types = tree_cons (NULL_TREE, TREE_TYPE (p), types); 2201 p = TREE_CHAIN (p); 2202 } 2203 types = chainon (nreverse (types), void_list_node); 2204 return tsubst_function_parms (types, args, info.complain, info.in_decl); 2205} 2206 2207/* A subroutine of tsubst_parameterized_constraint. Substitute ARGS 2208 into the parameter list T, producing a sequence of constraint 2209 variables, declared in the current scope. 2210 2211 Note that the caller must establish a local specialization stack 2212 prior to calling this function since this substitution will 2213 declare the substituted parameters. */ 2214 2215static tree 2216tsubst_constraint_variables (tree t, tree args, subst_info info) 2217{ 2218 /* Perform a trial substitution to check for type errors. */ 2219 tree parms = check_constraint_variables (t, args, info); 2220 if (parms == error_mark_node) 2221 return error_mark_node; 2222 2223 /* Clear cp_unevaluated_operand across tsubst so that we get a proper chain 2224 of PARM_DECLs. */ 2225 int saved_unevaluated_operand = cp_unevaluated_operand; 2226 cp_unevaluated_operand = 0; 2227 tree vars = tsubst (t, args, info.complain, info.in_decl); 2228 cp_unevaluated_operand = saved_unevaluated_operand; 2229 if (vars == error_mark_node) 2230 return error_mark_node; 2231 return declare_constraint_vars (t, vars); 2232} 2233 2234/* Substitute ARGS into the requires-expression T. [8.4.7]p6. The 2235 substitution of template arguments into a requires-expression 2236 may result in the formation of invalid types or expressions 2237 in its requirements ... In such cases, the expression evaluates 2238 to false; it does not cause the program to be ill-formed. 2239 2240 When substituting through a REQUIRES_EXPR as part of template 2241 instantiation, we call this routine with info.quiet() true. 2242 2243 When evaluating a REQUIRES_EXPR that appears outside a template in 2244 cp_parser_requires_expression, we call this routine with 2245 info.noisy() true. 2246 2247 Finally, when diagnosing unsatisfaction from diagnose_atomic_constraint 2248 and when diagnosing a false REQUIRES_EXPR via diagnose_constraints, 2249 we call this routine with info.diagnose_unsatisfaction_p() true. */ 2250 2251static tree 2252tsubst_requires_expr (tree t, tree args, sat_info info) 2253{ 2254 local_specialization_stack stack (lss_copy); 2255 2256 /* We need to check access during the substitution. */ 2257 deferring_access_check_sentinel acs (dk_no_deferred); 2258 2259 /* A requires-expression is an unevaluated context. */ 2260 cp_unevaluated u; 2261 2262 args = add_extra_args (REQUIRES_EXPR_EXTRA_ARGS (t), args, 2263 info.complain, info.in_decl); 2264 if (processing_template_decl) 2265 { 2266 /* We're partially instantiating a generic lambda. Substituting into 2267 this requires-expression now may cause its requirements to get 2268 checked out of order, so instead just remember the template 2269 arguments and wait until we can substitute them all at once. */ 2270 t = copy_node (t); 2271 REQUIRES_EXPR_EXTRA_ARGS (t) = build_extra_args (t, args, info.complain); 2272 return t; 2273 } 2274 2275 if (tree parms = REQUIRES_EXPR_PARMS (t)) 2276 { 2277 parms = tsubst_constraint_variables (parms, args, info); 2278 if (parms == error_mark_node) 2279 return boolean_false_node; 2280 } 2281 2282 tree result = boolean_true_node; 2283 for (tree reqs = REQUIRES_EXPR_REQS (t); reqs; reqs = TREE_CHAIN (reqs)) 2284 { 2285 tree req = TREE_VALUE (reqs); 2286 if (tsubst_requirement (req, args, info) == error_mark_node) 2287 { 2288 result = boolean_false_node; 2289 if (info.diagnose_unsatisfaction_p ()) 2290 /* Keep going so that we diagnose all failed requirements. */; 2291 else 2292 break; 2293 } 2294 } 2295 return result; 2296} 2297 2298/* Public wrapper for the above. */ 2299 2300tree 2301tsubst_requires_expr (tree t, tree args, 2302 tsubst_flags_t complain, tree in_decl) 2303{ 2304 sat_info info (complain, in_decl); 2305 return tsubst_requires_expr (t, args, info); 2306} 2307 2308/* Substitute ARGS into the constraint information CI, producing a new 2309 constraint record. */ 2310 2311tree 2312tsubst_constraint_info (tree t, tree args, 2313 tsubst_flags_t complain, tree in_decl) 2314{ 2315 if (!t || t == error_mark_node || !check_constraint_info (t)) 2316 return NULL_TREE; 2317 2318 tree tr = tsubst_constraint (CI_TEMPLATE_REQS (t), args, complain, in_decl); 2319 tree dr = tsubst_constraint (CI_DECLARATOR_REQS (t), args, complain, in_decl); 2320 return build_constraints (tr, dr); 2321} 2322 2323/* Substitute through a parameter mapping, in order to get the actual 2324 arguments used to instantiate an atomic constraint. This may fail 2325 if the substitution into arguments produces something ill-formed. */ 2326 2327static tree 2328tsubst_parameter_mapping (tree map, tree args, subst_info info) 2329{ 2330 if (!map) 2331 return NULL_TREE; 2332 2333 tsubst_flags_t complain = info.complain; 2334 tree in_decl = info.in_decl; 2335 2336 tree result = NULL_TREE; 2337 for (tree p = map; p; p = TREE_CHAIN (p)) 2338 { 2339 if (p == error_mark_node) 2340 return error_mark_node; 2341 tree parm = TREE_VALUE (p); 2342 tree arg = TREE_PURPOSE (p); 2343 tree new_arg; 2344 if (ARGUMENT_PACK_P (arg)) 2345 new_arg = tsubst_argument_pack (arg, args, complain, in_decl); 2346 else 2347 { 2348 new_arg = tsubst_template_arg (arg, args, complain, in_decl); 2349 if (TYPE_P (new_arg)) 2350 new_arg = canonicalize_type_argument (new_arg, complain); 2351 } 2352 if (TREE_CODE (new_arg) == TYPE_ARGUMENT_PACK) 2353 { 2354 tree pack_args = ARGUMENT_PACK_ARGS (new_arg); 2355 for (int i = 0; i < TREE_VEC_LENGTH (pack_args); i++) 2356 { 2357 tree& pack_arg = TREE_VEC_ELT (pack_args, i); 2358 if (TYPE_P (pack_arg)) 2359 pack_arg = canonicalize_type_argument (pack_arg, complain); 2360 } 2361 } 2362 if (new_arg == error_mark_node) 2363 return error_mark_node; 2364 2365 result = tree_cons (new_arg, parm, result); 2366 } 2367 return nreverse (result); 2368} 2369 2370tree 2371tsubst_parameter_mapping (tree map, tree args, tsubst_flags_t complain, tree in_decl) 2372{ 2373 return tsubst_parameter_mapping (map, args, subst_info (complain, in_decl)); 2374} 2375 2376/*--------------------------------------------------------------------------- 2377 Constraint satisfaction 2378---------------------------------------------------------------------------*/ 2379 2380/* True if we are currently satisfying a constraint. */ 2381 2382static bool satisfying_constraint; 2383 2384/* A vector of incomplete types (and of declarations with undeduced return type), 2385 appended to by note_failed_type_completion_for_satisfaction. The 2386 satisfaction caches use this in order to keep track of "potentially unstable" 2387 satisfaction results. 2388 2389 Since references to entries in this vector are stored only in the 2390 GC-deletable sat_cache, it's safe to make this deletable as well. */ 2391 2392static GTY((deletable)) vec<tree, va_gc> *failed_type_completions; 2393 2394/* Called whenever a type completion (or return type deduction) failure occurs 2395 that definitely affects the meaning of the program, by e.g. inducing 2396 substitution failure. */ 2397 2398void 2399note_failed_type_completion_for_satisfaction (tree t) 2400{ 2401 if (satisfying_constraint) 2402 { 2403 gcc_checking_assert ((TYPE_P (t) && !COMPLETE_TYPE_P (t)) 2404 || (DECL_P (t) && undeduced_auto_decl (t))); 2405 vec_safe_push (failed_type_completions, t); 2406 } 2407} 2408 2409/* Returns true if the range [BEGIN, END) of elements within the 2410 failed_type_completions vector contains a complete type (or a 2411 declaration with a non-placeholder return type). */ 2412 2413static bool 2414some_type_complete_p (int begin, int end) 2415{ 2416 for (int i = begin; i < end; i++) 2417 { 2418 tree t = (*failed_type_completions)[i]; 2419 if (TYPE_P (t) && COMPLETE_TYPE_P (t)) 2420 return true; 2421 if (DECL_P (t) && !undeduced_auto_decl (t)) 2422 return true; 2423 } 2424 return false; 2425} 2426 2427/* Hash functions and data types for satisfaction cache entries. */ 2428 2429struct GTY((for_user)) sat_entry 2430{ 2431 /* The relevant ATOMIC_CONSTR. */ 2432 tree atom; 2433 2434 /* The relevant template arguments. */ 2435 tree args; 2436 2437 /* The result of satisfaction of ATOM+ARGS. 2438 This is either boolean_true_node, boolean_false_node or error_mark_node, 2439 where error_mark_node indicates ill-formed satisfaction. 2440 It's set to NULL_TREE while computing satisfaction of ATOM+ARGS for 2441 the first time. */ 2442 tree result; 2443 2444 /* The value of input_location when satisfaction of ATOM+ARGS was first 2445 performed. */ 2446 location_t location; 2447 2448 /* The range of elements appended to the failed_type_completions vector 2449 during computation of this satisfaction result, encoded as a begin/end 2450 pair of offsets. */ 2451 int ftc_begin, ftc_end; 2452 2453 /* True if we want to diagnose the above instability when it's detected. 2454 We don't always want to do so, in order to avoid emitting duplicate 2455 diagnostics in some cases. */ 2456 bool diagnose_instability; 2457 2458 /* True if we're in the middle of computing this satisfaction result. 2459 Used during both quiet and noisy satisfaction to detect self-recursive 2460 satisfaction. */ 2461 bool evaluating; 2462}; 2463 2464struct sat_hasher : ggc_ptr_hash<sat_entry> 2465{ 2466 static hashval_t hash (sat_entry *e) 2467 { 2468 if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->atom)) 2469 { 2470 /* Atoms with instantiated mappings are built during satisfaction. 2471 They live only inside the sat_cache, and we build one to query 2472 the cache with each time we instantiate a mapping. */ 2473 gcc_assert (!e->args); 2474 return hash_atomic_constraint (e->atom); 2475 } 2476 2477 /* Atoms with uninstantiated mappings are built during normalization. 2478 Since normalize_atom caches the atoms it returns, we can assume 2479 pointer-based identity for fast hashing and comparison. Even if this 2480 assumption is violated, that's okay, we'll just get a cache miss. */ 2481 hashval_t value = htab_hash_pointer (e->atom); 2482 2483 if (tree map = ATOMIC_CONSTR_MAP (e->atom)) 2484 /* Only the parameters that are used in the targets of the mapping 2485 affect the satisfaction value of the atom. So we consider only 2486 the arguments for these parameters, and ignore the rest. */ 2487 for (tree target_parms = TREE_TYPE (map); 2488 target_parms; 2489 target_parms = TREE_CHAIN (target_parms)) 2490 { 2491 int level, index; 2492 tree parm = TREE_VALUE (target_parms); 2493 template_parm_level_and_index (parm, &level, &index); 2494 tree arg = TMPL_ARG (e->args, level, index); 2495 value = iterative_hash_template_arg (arg, value); 2496 } 2497 return value; 2498 } 2499 2500 static bool equal (sat_entry *e1, sat_entry *e2) 2501 { 2502 if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom) 2503 != ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->atom)) 2504 return false; 2505 2506 /* See sat_hasher::hash. */ 2507 if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom)) 2508 { 2509 gcc_assert (!e1->args && !e2->args); 2510 return atomic_constraints_identical_p (e1->atom, e2->atom); 2511 } 2512 2513 if (e1->atom != e2->atom) 2514 return false; 2515 2516 if (tree map = ATOMIC_CONSTR_MAP (e1->atom)) 2517 for (tree target_parms = TREE_TYPE (map); 2518 target_parms; 2519 target_parms = TREE_CHAIN (target_parms)) 2520 { 2521 int level, index; 2522 tree parm = TREE_VALUE (target_parms); 2523 template_parm_level_and_index (parm, &level, &index); 2524 tree arg1 = TMPL_ARG (e1->args, level, index); 2525 tree arg2 = TMPL_ARG (e2->args, level, index); 2526 if (!template_args_equal (arg1, arg2)) 2527 return false; 2528 } 2529 return true; 2530 } 2531}; 2532 2533/* Cache the result of satisfy_atom. */ 2534static GTY((deletable)) hash_table<sat_hasher> *sat_cache; 2535 2536/* Cache the result of satisfy_declaration_constraints. */ 2537static GTY((deletable)) hash_map<tree, tree> *decl_satisfied_cache; 2538 2539/* A tool used by satisfy_atom to help manage satisfaction caching and to 2540 diagnose "unstable" satisfaction values. We insert into the cache only 2541 when performing satisfaction quietly. */ 2542 2543struct satisfaction_cache 2544{ 2545 satisfaction_cache (tree, tree, sat_info); 2546 tree get (); 2547 tree save (tree); 2548 2549 sat_entry *entry; 2550 sat_info info; 2551 int ftc_begin; 2552}; 2553 2554/* Constructor for the satisfaction_cache class. We're performing satisfaction 2555 of ATOM+ARGS according to INFO. */ 2556 2557satisfaction_cache 2558::satisfaction_cache (tree atom, tree args, sat_info info) 2559 : entry(nullptr), info(info), ftc_begin(-1) 2560{ 2561 if (!sat_cache) 2562 sat_cache = hash_table<sat_hasher>::create_ggc (31); 2563 2564 /* When noisy, we query the satisfaction cache in order to diagnose 2565 "unstable" satisfaction values. */ 2566 if (info.noisy ()) 2567 { 2568 /* When noisy, constraints have been re-normalized, and that breaks the 2569 pointer-based identity assumption of sat_cache (for atoms with 2570 uninstantiated mappings). So undo this re-normalization by looking in 2571 the atom_cache for the corresponding atom that was used during quiet 2572 satisfaction. */ 2573 if (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom)) 2574 { 2575 if (tree found = atom_cache->find (atom)) 2576 atom = found; 2577 else 2578 /* The lookup should always succeed, but if it fails then let's 2579 just leave 'entry' empty, effectively disabling the cache. */ 2580 return; 2581 } 2582 } 2583 2584 /* Look up or create the corresponding satisfaction entry. */ 2585 sat_entry elt; 2586 elt.atom = atom; 2587 elt.args = args; 2588 sat_entry **slot = sat_cache->find_slot (&elt, INSERT); 2589 if (*slot) 2590 entry = *slot; 2591 else if (info.quiet ()) 2592 { 2593 entry = ggc_alloc<sat_entry> (); 2594 entry->atom = atom; 2595 entry->args = args; 2596 entry->result = NULL_TREE; 2597 entry->location = input_location; 2598 entry->ftc_begin = entry->ftc_end = -1; 2599 entry->diagnose_instability = false; 2600 if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom)) 2601 /* We always want to diagnose instability of an atom with an 2602 instantiated parameter mapping. For atoms with an uninstantiated 2603 mapping, we set this flag (in satisfy_atom) only if substitution 2604 into its mapping previously failed. */ 2605 entry->diagnose_instability = true; 2606 entry->evaluating = false; 2607 *slot = entry; 2608 } 2609 else 2610 /* We shouldn't get here, but if we do, let's just leave 'entry' 2611 empty, effectively disabling the cache. */ 2612 return; 2613} 2614 2615/* Returns the cached satisfaction result if we have one and we're not 2616 recomputing the satisfaction result from scratch. Otherwise returns 2617 NULL_TREE. */ 2618 2619tree 2620satisfaction_cache::get () 2621{ 2622 if (!entry) 2623 return NULL_TREE; 2624 2625 if (entry->evaluating) 2626 { 2627 /* If we get here, it means satisfaction is self-recursive. */ 2628 gcc_checking_assert (!entry->result); 2629 if (info.noisy ()) 2630 error_at (EXPR_LOCATION (ATOMIC_CONSTR_EXPR (entry->atom)), 2631 "satisfaction of atomic constraint %qE depends on itself", 2632 entry->atom); 2633 return error_mark_node; 2634 } 2635 2636 /* This satisfaction result is "potentially unstable" if a type for which 2637 type completion failed during its earlier computation is now complete. */ 2638 bool maybe_unstable = some_type_complete_p (entry->ftc_begin, 2639 entry->ftc_end); 2640 2641 if (info.noisy () || maybe_unstable || !entry->result) 2642 { 2643 /* We're computing the satisfaction result from scratch. */ 2644 entry->evaluating = true; 2645 ftc_begin = vec_safe_length (failed_type_completions); 2646 return NULL_TREE; 2647 } 2648 else 2649 return entry->result; 2650} 2651 2652/* RESULT is the computed satisfaction result. If RESULT differs from the 2653 previously cached result, this routine issues an appropriate error. 2654 Otherwise, when evaluating quietly, updates the cache appropriately. */ 2655 2656tree 2657satisfaction_cache::save (tree result) 2658{ 2659 if (!entry) 2660 return result; 2661 2662 gcc_checking_assert (entry->evaluating); 2663 entry->evaluating = false; 2664 2665 if (entry->result && result != entry->result) 2666 { 2667 if (info.quiet ()) 2668 /* Return error_mark_node to force satisfaction to get replayed 2669 noisily. */ 2670 return error_mark_node; 2671 else 2672 { 2673 if (entry->diagnose_instability) 2674 { 2675 auto_diagnostic_group d; 2676 error_at (EXPR_LOCATION (ATOMIC_CONSTR_EXPR (entry->atom)), 2677 "satisfaction value of atomic constraint %qE changed " 2678 "from %qE to %qE", entry->atom, entry->result, result); 2679 inform (entry->location, 2680 "satisfaction value first evaluated to %qE from here", 2681 entry->result); 2682 } 2683 /* For sake of error recovery, allow this latest satisfaction result 2684 to prevail. */ 2685 entry->result = result; 2686 return result; 2687 } 2688 } 2689 2690 if (info.quiet ()) 2691 { 2692 entry->result = result; 2693 /* Store into this entry the list of relevant failed type completions 2694 that occurred during (re)computation of the satisfaction result. */ 2695 gcc_checking_assert (ftc_begin != -1); 2696 entry->ftc_begin = ftc_begin; 2697 entry->ftc_end = vec_safe_length (failed_type_completions); 2698 } 2699 2700 return result; 2701} 2702 2703/* Substitute ARGS into constraint-expression T during instantiation of 2704 a member of a class template. */ 2705 2706tree 2707tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl) 2708{ 2709 /* We also don't want to evaluate concept-checks when substituting the 2710 constraint-expressions of a declaration. */ 2711 processing_constraint_expression_sentinel s; 2712 cp_unevaluated u; 2713 tree expr = tsubst_expr (t, args, complain, in_decl, false); 2714 return expr; 2715} 2716 2717static tree satisfy_constraint_r (tree, tree, sat_info info); 2718 2719/* Compute the satisfaction of a conjunction. */ 2720 2721static tree 2722satisfy_conjunction (tree t, tree args, sat_info info) 2723{ 2724 tree lhs = satisfy_constraint_r (TREE_OPERAND (t, 0), args, info); 2725 if (lhs == error_mark_node || lhs == boolean_false_node) 2726 return lhs; 2727 return satisfy_constraint_r (TREE_OPERAND (t, 1), args, info); 2728} 2729 2730/* The current depth at which we're replaying an error during recursive 2731 diagnosis of a constraint satisfaction failure. */ 2732 2733static int current_constraint_diagnosis_depth; 2734 2735/* Whether CURRENT_CONSTRAINT_DIAGNOSIS_DEPTH has ever exceeded 2736 CONCEPTS_DIAGNOSTICS_MAX_DEPTH during recursive diagnosis of a constraint 2737 satisfaction error. */ 2738 2739static bool concepts_diagnostics_max_depth_exceeded_p; 2740 2741/* Recursive subroutine of collect_operands_of_disjunction. T is a normalized 2742 subexpression of a constraint (composed of CONJ_CONSTRs and DISJ_CONSTRs) 2743 and E is the corresponding unnormalized subexpression (composed of 2744 TRUTH_ANDIF_EXPRs and TRUTH_ORIF_EXPRs). */ 2745 2746static void 2747collect_operands_of_disjunction_r (tree t, tree e, 2748 auto_vec<tree_pair> *operands) 2749{ 2750 if (TREE_CODE (e) == TRUTH_ORIF_EXPR) 2751 { 2752 collect_operands_of_disjunction_r (TREE_OPERAND (t, 0), 2753 TREE_OPERAND (e, 0), operands); 2754 collect_operands_of_disjunction_r (TREE_OPERAND (t, 1), 2755 TREE_OPERAND (e, 1), operands); 2756 } 2757 else 2758 { 2759 tree_pair p = std::make_pair (t, e); 2760 operands->safe_push (p); 2761 } 2762} 2763 2764/* Recursively collect the normalized and unnormalized operands of the 2765 disjunction T and append them to OPERANDS in order. */ 2766 2767static void 2768collect_operands_of_disjunction (tree t, auto_vec<tree_pair> *operands) 2769{ 2770 collect_operands_of_disjunction_r (t, CONSTR_EXPR (t), operands); 2771} 2772 2773/* Compute the satisfaction of a disjunction. */ 2774 2775static tree 2776satisfy_disjunction (tree t, tree args, sat_info info) 2777{ 2778 /* Evaluate each operand with unsatisfaction diagnostics disabled. */ 2779 sat_info sub = info; 2780 sub.diagnose_unsatisfaction = false; 2781 2782 tree lhs = satisfy_constraint_r (TREE_OPERAND (t, 0), args, sub); 2783 if (lhs == boolean_true_node || lhs == error_mark_node) 2784 return lhs; 2785 2786 tree rhs = satisfy_constraint_r (TREE_OPERAND (t, 1), args, sub); 2787 if (rhs == boolean_true_node || rhs == error_mark_node) 2788 return rhs; 2789 2790 /* Both branches evaluated to false. Explain the satisfaction failure in 2791 each branch. */ 2792 if (info.diagnose_unsatisfaction_p ()) 2793 { 2794 diagnosing_failed_constraint failure (t, args, info.noisy ()); 2795 cp_expr disj_expr = CONSTR_EXPR (t); 2796 inform (disj_expr.get_location (), 2797 "no operand of the disjunction is satisfied"); 2798 if (diagnosing_failed_constraint::replay_errors_p ()) 2799 { 2800 /* Replay the error in each branch of the disjunction. */ 2801 auto_vec<tree_pair> operands; 2802 collect_operands_of_disjunction (t, &operands); 2803 for (unsigned i = 0; i < operands.length (); i++) 2804 { 2805 tree norm_op = operands[i].first; 2806 tree op = operands[i].second; 2807 location_t loc = make_location (cp_expr_location (op), 2808 disj_expr.get_start (), 2809 disj_expr.get_finish ()); 2810 inform (loc, "the operand %qE is unsatisfied because", op); 2811 satisfy_constraint_r (norm_op, args, info); 2812 } 2813 } 2814 } 2815 2816 return boolean_false_node; 2817} 2818 2819/* Ensures that T is a truth value and not (accidentally, as sometimes 2820 happens) an integer value. */ 2821 2822tree 2823satisfaction_value (tree t) 2824{ 2825 if (t == error_mark_node || t == boolean_true_node || t == boolean_false_node) 2826 return t; 2827 2828 gcc_assert (TREE_CODE (t) == INTEGER_CST 2829 && same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (t), 2830 boolean_type_node)); 2831 if (integer_zerop (t)) 2832 return boolean_false_node; 2833 else 2834 return boolean_true_node; 2835} 2836 2837/* Build a new template argument vector corresponding to the parameter 2838 mapping of the atomic constraint T, using arguments from ARGS. */ 2839 2840static tree 2841get_mapped_args (tree t, tree args) 2842{ 2843 tree map = ATOMIC_CONSTR_MAP (t); 2844 2845 /* No map, no arguments. */ 2846 if (!map) 2847 return NULL_TREE; 2848 2849 /* Determine the depth of the resulting argument vector. */ 2850 int depth; 2851 if (ATOMIC_CONSTR_EXPR_FROM_CONCEPT_P (t)) 2852 /* The expression of this atomic constraint comes from a concept definition, 2853 whose template depth is always one, so the resulting argument vector 2854 will also have depth one. */ 2855 depth = 1; 2856 else 2857 /* Otherwise, the expression of this atomic constraint comes from 2858 the context of the constrained entity, whose template depth is that 2859 of ARGS. */ 2860 depth = TMPL_ARGS_DEPTH (args); 2861 2862 /* Place each argument at its corresponding position in the argument 2863 list. Note that the list will be sparse (not all arguments supplied), 2864 but instantiation is guaranteed to only use the parameters in the 2865 mapping, so null arguments would never be used. */ 2866 auto_vec< vec<tree> > lists (depth); 2867 lists.quick_grow_cleared (depth); 2868 for (tree p = map; p; p = TREE_CHAIN (p)) 2869 { 2870 int level; 2871 int index; 2872 template_parm_level_and_index (TREE_VALUE (p), &level, &index); 2873 2874 /* Insert the argument into its corresponding position. */ 2875 vec<tree> &list = lists[level - 1]; 2876 if (index >= (int)list.length ()) 2877 list.safe_grow_cleared (index + 1, /*exact=*/false); 2878 list[index] = TREE_PURPOSE (p); 2879 } 2880 2881 /* Build the new argument list. */ 2882 args = make_tree_vec (lists.length ()); 2883 for (unsigned i = 0; i != lists.length (); ++i) 2884 { 2885 vec<tree> &list = lists[i]; 2886 tree level = make_tree_vec (list.length ()); 2887 for (unsigned j = 0; j < list.length(); ++j) 2888 TREE_VEC_ELT (level, j) = list[j]; 2889 SET_TMPL_ARGS_LEVEL (args, i + 1, level); 2890 list.release (); 2891 } 2892 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args, 0); 2893 2894 if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (args) 2895 && TMPL_ARGS_DEPTH (args) == 1) 2896 { 2897 /* Get rid of the redundant outer TREE_VEC. */ 2898 tree level = TMPL_ARGS_LEVEL (args, 1); 2899 ggc_free (args); 2900 args = level; 2901 } 2902 2903 return args; 2904} 2905 2906static void diagnose_atomic_constraint (tree, tree, tree, sat_info); 2907 2908/* Compute the satisfaction of an atomic constraint. */ 2909 2910static tree 2911satisfy_atom (tree t, tree args, sat_info info) 2912{ 2913 /* In case there is a diagnostic, we want to establish the context 2914 prior to printing errors. If no errors occur, this context is 2915 removed before returning. */ 2916 diagnosing_failed_constraint failure (t, args, info.noisy ()); 2917 2918 satisfaction_cache cache (t, args, info); 2919 if (tree r = cache.get ()) 2920 return r; 2921 2922 /* Perform substitution quietly. */ 2923 subst_info quiet (tf_none, NULL_TREE); 2924 2925 /* Instantiate the parameter mapping. */ 2926 tree map = tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, quiet); 2927 if (map == error_mark_node) 2928 { 2929 /* If instantiation of the parameter mapping fails, the constraint is 2930 not satisfied. Replay the substitution. */ 2931 if (info.diagnose_unsatisfaction_p ()) 2932 tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, info); 2933 if (info.quiet ()) 2934 /* Since instantiation of the parameter mapping failed, we 2935 want to diagnose potential instability of this satisfaction 2936 result. */ 2937 cache.entry->diagnose_instability = true; 2938 return cache.save (boolean_false_node); 2939 } 2940 2941 /* Now build a new atom using the instantiated mapping. We use 2942 this atom as a second key to the satisfaction cache, and we 2943 also pass it to diagnose_atomic_constraint so that diagnostics 2944 which refer to the atom display the instantiated mapping. */ 2945 t = copy_node (t); 2946 ATOMIC_CONSTR_MAP (t) = map; 2947 gcc_assert (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (t)); 2948 ATOMIC_CONSTR_MAP_INSTANTIATED_P (t) = true; 2949 satisfaction_cache inst_cache (t, /*args=*/NULL_TREE, info); 2950 if (tree r = inst_cache.get ()) 2951 { 2952 cache.entry->location = inst_cache.entry->location; 2953 return cache.save (r); 2954 } 2955 2956 /* Rebuild the argument vector from the parameter mapping. */ 2957 args = get_mapped_args (t, args); 2958 2959 /* Apply the parameter mapping (i.e., just substitute). */ 2960 tree expr = ATOMIC_CONSTR_EXPR (t); 2961 tree result = tsubst_expr (expr, args, quiet.complain, quiet.in_decl, false); 2962 if (result == error_mark_node) 2963 { 2964 /* If substitution results in an invalid type or expression, the constraint 2965 is not satisfied. Replay the substitution. */ 2966 if (info.diagnose_unsatisfaction_p ()) 2967 tsubst_expr (expr, args, info.complain, info.in_decl, false); 2968 return cache.save (inst_cache.save (boolean_false_node)); 2969 } 2970 2971 /* [17.4.1.2] ... lvalue-to-rvalue conversion is performed as necessary, 2972 and EXPR shall be a constant expression of type bool. */ 2973 result = force_rvalue (result, info.complain); 2974 if (result == error_mark_node) 2975 return cache.save (inst_cache.save (error_mark_node)); 2976 if (!same_type_p (TREE_TYPE (result), boolean_type_node)) 2977 { 2978 if (info.noisy ()) 2979 diagnose_atomic_constraint (t, args, result, info); 2980 return cache.save (inst_cache.save (error_mark_node)); 2981 } 2982 2983 /* Compute the value of the constraint. */ 2984 if (info.noisy ()) 2985 { 2986 iloc_sentinel ils (EXPR_LOCATION (result)); 2987 result = cxx_constant_value (result); 2988 } 2989 else 2990 { 2991 result = maybe_constant_value (result, NULL_TREE, 2992 /*manifestly_const_eval=*/true); 2993 if (!TREE_CONSTANT (result)) 2994 result = error_mark_node; 2995 } 2996 result = satisfaction_value (result); 2997 if (result == boolean_false_node && info.diagnose_unsatisfaction_p ()) 2998 diagnose_atomic_constraint (t, args, result, info); 2999 3000 return cache.save (inst_cache.save (result)); 3001} 3002 3003/* Determine if the normalized constraint T is satisfied. 3004 Returns boolean_true_node if the expression/constraint is 3005 satisfied, boolean_false_node if not, and error_mark_node 3006 if the there was an error evaluating the constraint. 3007 3008 The parameter mapping of atomic constraints is simply the 3009 set of template arguments that will be substituted into 3010 the expression, regardless of template parameters appearing 3011 withing. Whether a template argument is used in the atomic 3012 constraint only matters for subsumption. */ 3013 3014static tree 3015satisfy_constraint_r (tree t, tree args, sat_info info) 3016{ 3017 if (t == error_mark_node) 3018 return error_mark_node; 3019 3020 switch (TREE_CODE (t)) 3021 { 3022 case CONJ_CONSTR: 3023 return satisfy_conjunction (t, args, info); 3024 case DISJ_CONSTR: 3025 return satisfy_disjunction (t, args, info); 3026 case ATOMIC_CONSTR: 3027 return satisfy_atom (t, args, info); 3028 default: 3029 gcc_unreachable (); 3030 } 3031} 3032 3033/* Check that the normalized constraint T is satisfied for ARGS. */ 3034 3035static tree 3036satisfy_normalized_constraints (tree t, tree args, sat_info info) 3037{ 3038 auto_timevar time (TV_CONSTRAINT_SAT); 3039 3040 auto ovr = make_temp_override (satisfying_constraint, true); 3041 3042 /* Turn off template processing. Constraint satisfaction only applies 3043 to non-dependent terms, so we want to ensure full checking here. */ 3044 processing_template_decl_sentinel proc (true); 3045 3046 /* We need to check access during satisfaction. */ 3047 deferring_access_check_sentinel acs (dk_no_deferred); 3048 3049 /* Constraints are unevaluated operands. */ 3050 cp_unevaluated u; 3051 3052 return satisfy_constraint_r (t, args, info); 3053} 3054 3055/* Return the normal form of the constraints on the placeholder 'auto' 3056 type T. */ 3057 3058static tree 3059normalize_placeholder_type_constraints (tree t, bool diag) 3060{ 3061 gcc_assert (is_auto (t)); 3062 tree ci = PLACEHOLDER_TYPE_CONSTRAINTS_INFO (t); 3063 if (!ci) 3064 return NULL_TREE; 3065 3066 tree constr = TREE_VALUE (ci); 3067 /* The TREE_PURPOSE contains the set of template parameters that were in 3068 scope for this placeholder type; use them as the initial template 3069 parameters for normalization. */ 3070 tree initial_parms = TREE_PURPOSE (ci); 3071 3072 /* The 'auto' itself is used as the first argument in its own constraints, 3073 and its level is one greater than its template depth. So in order to 3074 capture all used template parameters, we need to add an extra level of 3075 template parameters to the context; a dummy level suffices. */ 3076 initial_parms 3077 = tree_cons (size_int (initial_parms 3078 ? TMPL_PARMS_DEPTH (initial_parms) + 1 : 1), 3079 make_tree_vec (0), initial_parms); 3080 3081 norm_info info (diag ? tf_norm : tf_none); 3082 info.initial_parms = initial_parms; 3083 return normalize_constraint_expression (constr, info); 3084} 3085 3086/* Evaluate the constraints of T using ARGS, returning a satisfaction value. 3087 Here, T can be a concept-id, nested-requirement, placeholder 'auto', or 3088 requires-expression. */ 3089 3090static tree 3091satisfy_nondeclaration_constraints (tree t, tree args, sat_info info) 3092{ 3093 if (t == error_mark_node) 3094 return error_mark_node; 3095 3096 /* Handle REQUIRES_EXPR directly, bypassing satisfaction. */ 3097 if (TREE_CODE (t) == REQUIRES_EXPR) 3098 { 3099 auto ovr = make_temp_override (current_constraint_diagnosis_depth); 3100 if (info.noisy ()) 3101 ++current_constraint_diagnosis_depth; 3102 return tsubst_requires_expr (t, args, info); 3103 } 3104 3105 /* Get the normalized constraints. */ 3106 tree norm; 3107 if (concept_check_p (t)) 3108 { 3109 gcc_assert (!args); 3110 tree id = unpack_concept_check (t); 3111 args = TREE_OPERAND (id, 1); 3112 tree tmpl = get_concept_check_template (id); 3113 norm = normalize_concept_definition (tmpl, info.noisy ()); 3114 } 3115 else if (TREE_CODE (t) == NESTED_REQ) 3116 { 3117 norm_info ninfo (info.noisy () ? tf_norm : tf_none); 3118 /* The TREE_TYPE contains the set of template parameters that were in 3119 scope for this nested requirement; use them as the initial template 3120 parameters for normalization. */ 3121 ninfo.initial_parms = TREE_TYPE (t); 3122 norm = normalize_constraint_expression (TREE_OPERAND (t, 0), ninfo); 3123 } 3124 else if (is_auto (t)) 3125 { 3126 norm = normalize_placeholder_type_constraints (t, info.noisy ()); 3127 if (!norm) 3128 return boolean_true_node; 3129 } 3130 else 3131 gcc_unreachable (); 3132 3133 /* Perform satisfaction. */ 3134 return satisfy_normalized_constraints (norm, args, info); 3135} 3136 3137/* Evaluate the associated constraints of the template specialization T 3138 according to INFO, returning a satisfaction value. */ 3139 3140static tree 3141satisfy_declaration_constraints (tree t, sat_info info) 3142{ 3143 gcc_assert (DECL_P (t) && TREE_CODE (t) != TEMPLATE_DECL); 3144 const tree saved_t = t; 3145 3146 /* For inherited constructors, consider the original declaration; 3147 it has the correct template information attached. */ 3148 t = strip_inheriting_ctors (t); 3149 tree inh_ctor_targs = NULL_TREE; 3150 if (t != saved_t) 3151 if (tree ti = DECL_TEMPLATE_INFO (saved_t)) 3152 /* The inherited constructor points to an instantiation of a constructor 3153 template; remember its template arguments. */ 3154 inh_ctor_targs = TI_ARGS (ti); 3155 3156 /* Update the declaration for diagnostics. */ 3157 info.in_decl = t; 3158 3159 if (info.quiet ()) 3160 if (tree *result = hash_map_safe_get (decl_satisfied_cache, saved_t)) 3161 return *result; 3162 3163 tree args = NULL_TREE; 3164 if (tree ti = DECL_TEMPLATE_INFO (t)) 3165 { 3166 /* The initial parameter mapping is the complete set of 3167 template arguments substituted into the declaration. */ 3168 args = TI_ARGS (ti); 3169 if (inh_ctor_targs) 3170 args = add_outermost_template_args (args, inh_ctor_targs); 3171 } 3172 3173 if (regenerated_lambda_fn_p (t)) 3174 { 3175 /* The TI_ARGS of a regenerated lambda contains only the innermost 3176 set of template arguments. Augment this with the outer template 3177 arguments that were used to regenerate the lambda. */ 3178 gcc_assert (!args || TMPL_ARGS_DEPTH (args) == 1); 3179 tree regen_args = lambda_regenerating_args (t); 3180 if (args) 3181 args = add_to_template_args (regen_args, args); 3182 else 3183 args = regen_args; 3184 } 3185 3186 /* If the innermost arguments are dependent, or if the outer arguments 3187 are dependent and are needed by the constraints, we can't check 3188 satisfaction yet so pretend they're satisfied for now. */ 3189 if (uses_template_parms (args) 3190 && ((DECL_TEMPLATE_INFO (t) 3191 && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (t)) 3192 && (TMPL_ARGS_DEPTH (args) == 1 3193 || uses_template_parms (INNERMOST_TEMPLATE_ARGS (args)))) 3194 || uses_outer_template_parms_in_constraints (t))) 3195 return boolean_true_node; 3196 3197 /* Get the normalized constraints. */ 3198 tree norm = get_normalized_constraints_from_decl (t, info.noisy ()); 3199 3200 unsigned ftc_count = vec_safe_length (failed_type_completions); 3201 3202 tree result = boolean_true_node; 3203 if (norm) 3204 { 3205 if (!push_tinst_level (t)) 3206 return result; 3207 push_to_top_level (); 3208 push_access_scope (t); 3209 result = satisfy_normalized_constraints (norm, args, info); 3210 pop_access_scope (t); 3211 pop_from_top_level (); 3212 pop_tinst_level (); 3213 } 3214 3215 /* True if this satisfaction is (heuristically) potentially unstable, i.e. 3216 if its result may depend on where in the program it was performed. */ 3217 bool maybe_unstable_satisfaction = false; 3218 if (ftc_count != vec_safe_length (failed_type_completions)) 3219 /* Type completion failure occurred during satisfaction. The satisfaction 3220 result may (or may not) materially depend on the completeness of a type, 3221 so we consider it potentially unstable. */ 3222 maybe_unstable_satisfaction = true; 3223 3224 if (maybe_unstable_satisfaction) 3225 /* Don't cache potentially unstable satisfaction, to allow satisfy_atom 3226 to check the stability the next time around. */; 3227 else if (info.quiet ()) 3228 hash_map_safe_put<hm_ggc> (decl_satisfied_cache, saved_t, result); 3229 3230 return result; 3231} 3232 3233/* Evaluate the associated constraints of the template T using ARGS as the 3234 innermost set of template arguments and according to INFO, returning a 3235 satisfaction value. */ 3236 3237static tree 3238satisfy_declaration_constraints (tree t, tree args, sat_info info) 3239{ 3240 /* Update the declaration for diagnostics. */ 3241 info.in_decl = t; 3242 3243 gcc_assert (TREE_CODE (t) == TEMPLATE_DECL); 3244 3245 if (regenerated_lambda_fn_p (t)) 3246 { 3247 /* As in the two-parameter version of this function. */ 3248 gcc_assert (TMPL_ARGS_DEPTH (args) == 1); 3249 tree lambda = CLASSTYPE_LAMBDA_EXPR (DECL_CONTEXT (t)); 3250 tree outer_args = TI_ARGS (LAMBDA_EXPR_REGEN_INFO (lambda)); 3251 args = add_to_template_args (outer_args, args); 3252 } 3253 else 3254 args = add_outermost_template_args (t, args); 3255 3256 /* If the innermost arguments are dependent, or if the outer arguments 3257 are dependent and are needed by the constraints, we can't check 3258 satisfaction yet so pretend they're satisfied for now. */ 3259 if (uses_template_parms (args) 3260 && (TMPL_ARGS_DEPTH (args) == 1 3261 || uses_template_parms (INNERMOST_TEMPLATE_ARGS (args)) 3262 || uses_outer_template_parms_in_constraints (t))) 3263 return boolean_true_node; 3264 3265 tree result = boolean_true_node; 3266 if (tree norm = get_normalized_constraints_from_decl (t, info.noisy ())) 3267 { 3268 if (!push_tinst_level (t, args)) 3269 return result; 3270 tree pattern = DECL_TEMPLATE_RESULT (t); 3271 push_to_top_level (); 3272 push_access_scope (pattern); 3273 result = satisfy_normalized_constraints (norm, args, info); 3274 pop_access_scope (pattern); 3275 pop_from_top_level (); 3276 pop_tinst_level (); 3277 } 3278 3279 return result; 3280} 3281 3282/* A wrapper around satisfy_declaration_constraints and 3283 satisfy_nondeclaration_constraints which additionally replays 3284 quiet ill-formed satisfaction noisily, so that ill-formed 3285 satisfaction always gets diagnosed. */ 3286 3287static tree 3288constraint_satisfaction_value (tree t, tree args, sat_info info) 3289{ 3290 tree r; 3291 if (DECL_P (t)) 3292 { 3293 if (args) 3294 r = satisfy_declaration_constraints (t, args, info); 3295 else 3296 r = satisfy_declaration_constraints (t, info); 3297 } 3298 else 3299 r = satisfy_nondeclaration_constraints (t, args, info); 3300 if (r == error_mark_node && info.quiet () 3301 && !(DECL_P (t) && warning_suppressed_p (t))) 3302 { 3303 /* Replay the error noisily. */ 3304 sat_info noisy (tf_warning_or_error, info.in_decl); 3305 constraint_satisfaction_value (t, args, noisy); 3306 if (DECL_P (t) && !args) 3307 /* Avoid giving these errors again. */ 3308 suppress_warning (t); 3309 } 3310 return r; 3311} 3312 3313/* True iff the result of satisfying T using ARGS is BOOLEAN_TRUE_NODE 3314 and false otherwise, even in the case of errors. 3315 3316 Here, T can be: 3317 - a template declaration 3318 - a template specialization (in which case ARGS must be empty) 3319 - a concept-id (in which case ARGS must be empty) 3320 - a nested-requirement 3321 - a placeholder 'auto' 3322 - a requires-expression. */ 3323 3324bool 3325constraints_satisfied_p (tree t, tree args/*= NULL_TREE */) 3326{ 3327 if (!flag_concepts) 3328 return true; 3329 3330 sat_info quiet (tf_none, NULL_TREE); 3331 return constraint_satisfaction_value (t, args, quiet) == boolean_true_node; 3332} 3333 3334/* Evaluate a concept check of the form C<ARGS>. This is only used for the 3335 evaluation of template-ids as id-expressions. */ 3336 3337tree 3338evaluate_concept_check (tree check) 3339{ 3340 if (check == error_mark_node) 3341 return error_mark_node; 3342 3343 gcc_assert (concept_check_p (check)); 3344 3345 /* Check for satisfaction without diagnostics. */ 3346 sat_info quiet (tf_none, NULL_TREE); 3347 return constraint_satisfaction_value (check, /*args=*/NULL_TREE, quiet); 3348} 3349 3350/* Evaluate the requires-expression T, returning either boolean_true_node 3351 or boolean_false_node. This is used during folding and constexpr 3352 evaluation. */ 3353 3354tree 3355evaluate_requires_expr (tree t) 3356{ 3357 gcc_assert (TREE_CODE (t) == REQUIRES_EXPR); 3358 sat_info quiet (tf_none, NULL_TREE); 3359 return constraint_satisfaction_value (t, /*args=*/NULL_TREE, quiet); 3360} 3361 3362/*--------------------------------------------------------------------------- 3363 Semantic analysis of requires-expressions 3364---------------------------------------------------------------------------*/ 3365 3366/* Finish a requires expression for the given PARMS (possibly 3367 null) and the non-empty sequence of requirements. */ 3368 3369tree 3370finish_requires_expr (location_t loc, tree parms, tree reqs) 3371{ 3372 /* Build the node. */ 3373 tree r = build_min (REQUIRES_EXPR, boolean_type_node, parms, reqs, NULL_TREE); 3374 TREE_SIDE_EFFECTS (r) = false; 3375 TREE_CONSTANT (r) = true; 3376 SET_EXPR_LOCATION (r, loc); 3377 return r; 3378} 3379 3380/* Construct a requirement for the validity of EXPR. */ 3381 3382tree 3383finish_simple_requirement (location_t loc, tree expr) 3384{ 3385 tree r = build_nt (SIMPLE_REQ, expr); 3386 SET_EXPR_LOCATION (r, loc); 3387 return r; 3388} 3389 3390/* Construct a requirement for the validity of TYPE. */ 3391 3392tree 3393finish_type_requirement (location_t loc, tree type) 3394{ 3395 tree r = build_nt (TYPE_REQ, type); 3396 SET_EXPR_LOCATION (r, loc); 3397 return r; 3398} 3399 3400/* Construct a requirement for the validity of EXPR, along with 3401 its properties. if TYPE is non-null, then it specifies either 3402 an implicit conversion or argument deduction constraint, 3403 depending on whether any placeholders occur in the type name. 3404 NOEXCEPT_P is true iff the noexcept keyword was specified. */ 3405 3406tree 3407finish_compound_requirement (location_t loc, tree expr, tree type, bool noexcept_p) 3408{ 3409 tree req = build_nt (COMPOUND_REQ, expr, type); 3410 SET_EXPR_LOCATION (req, loc); 3411 COMPOUND_REQ_NOEXCEPT_P (req) = noexcept_p; 3412 return req; 3413} 3414 3415/* Finish a nested requirement. */ 3416 3417tree 3418finish_nested_requirement (location_t loc, tree expr) 3419{ 3420 /* Build the requirement, saving the set of in-scope template 3421 parameters as its type. */ 3422 tree r = build1 (NESTED_REQ, current_template_parms, expr); 3423 SET_EXPR_LOCATION (r, loc); 3424 return r; 3425} 3426 3427/* Check that FN satisfies the structural requirements of a 3428 function concept definition. */ 3429tree 3430check_function_concept (tree fn) 3431{ 3432 /* Check that the function is comprised of only a return statement. */ 3433 tree body = DECL_SAVED_TREE (fn); 3434 if (TREE_CODE (body) == BIND_EXPR) 3435 body = BIND_EXPR_BODY (body); 3436 3437 /* Sometimes a function call results in the creation of clean up 3438 points. Allow these to be preserved in the body of the 3439 constraint, as we might actually need them for some constexpr 3440 evaluations. */ 3441 if (TREE_CODE (body) == CLEANUP_POINT_EXPR) 3442 body = TREE_OPERAND (body, 0); 3443 3444 /* Check that the definition is written correctly. */ 3445 if (TREE_CODE (body) != RETURN_EXPR) 3446 { 3447 location_t loc = DECL_SOURCE_LOCATION (fn); 3448 if (TREE_CODE (body) == STATEMENT_LIST && !STATEMENT_LIST_HEAD (body)) 3449 { 3450 if (seen_error ()) 3451 /* The definition was probably erroneous, not empty. */; 3452 else 3453 error_at (loc, "definition of concept %qD is empty", fn); 3454 } 3455 else 3456 error_at (loc, "definition of concept %qD has multiple statements", fn); 3457 } 3458 3459 return NULL_TREE; 3460} 3461 3462/*--------------------------------------------------------------------------- 3463 Equivalence of constraints 3464---------------------------------------------------------------------------*/ 3465 3466/* Returns true when A and B are equivalent constraints. */ 3467bool 3468equivalent_constraints (tree a, tree b) 3469{ 3470 gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO); 3471 gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO); 3472 return cp_tree_equal (a, b); 3473} 3474 3475/* Returns true if the template declarations A and B have equivalent 3476 constraints. This is the case when A's constraints subsume B's and 3477 when B's also constrain A's. */ 3478bool 3479equivalently_constrained (tree d1, tree d2) 3480{ 3481 gcc_assert (TREE_CODE (d1) == TREE_CODE (d2)); 3482 return equivalent_constraints (get_constraints (d1), get_constraints (d2)); 3483} 3484 3485/*--------------------------------------------------------------------------- 3486 Partial ordering of constraints 3487---------------------------------------------------------------------------*/ 3488 3489/* Returns true when the constraints in CI strictly subsume 3490 the associated constraints of TMPL. */ 3491 3492bool 3493strictly_subsumes (tree ci, tree tmpl) 3494{ 3495 tree n1 = get_normalized_constraints_from_info (ci, NULL_TREE); 3496 tree n2 = get_normalized_constraints_from_decl (tmpl); 3497 3498 return subsumes (n1, n2) && !subsumes (n2, n1); 3499} 3500 3501/* Returns true when the constraints in CI subsume the 3502 associated constraints of TMPL. */ 3503 3504bool 3505weakly_subsumes (tree ci, tree tmpl) 3506{ 3507 tree n1 = get_normalized_constraints_from_info (ci, NULL_TREE); 3508 tree n2 = get_normalized_constraints_from_decl (tmpl); 3509 3510 return subsumes (n1, n2); 3511} 3512 3513/* Determines which of the declarations, A or B, is more constrained. 3514 That is, which declaration's constraints subsume but are not subsumed 3515 by the other's? 3516 3517 Returns 1 if D1 is more constrained than D2, -1 if D2 is more constrained 3518 than D1, and 0 otherwise. */ 3519 3520int 3521more_constrained (tree d1, tree d2) 3522{ 3523 tree n1 = get_normalized_constraints_from_decl (d1); 3524 tree n2 = get_normalized_constraints_from_decl (d2); 3525 3526 int winner = 0; 3527 if (subsumes (n1, n2)) 3528 ++winner; 3529 if (subsumes (n2, n1)) 3530 --winner; 3531 return winner; 3532} 3533 3534/* Return whether D1 is at least as constrained as D2. */ 3535 3536bool 3537at_least_as_constrained (tree d1, tree d2) 3538{ 3539 tree n1 = get_normalized_constraints_from_decl (d1); 3540 tree n2 = get_normalized_constraints_from_decl (d2); 3541 3542 return subsumes (n1, n2); 3543} 3544 3545/*--------------------------------------------------------------------------- 3546 Constraint diagnostics 3547---------------------------------------------------------------------------*/ 3548 3549/* Returns the best location to diagnose a constraint error. */ 3550 3551static location_t 3552get_constraint_error_location (tree t) 3553{ 3554 if (location_t loc = cp_expr_location (t)) 3555 return loc; 3556 3557 /* If we have a specific location give it. */ 3558 tree expr = CONSTR_EXPR (t); 3559 if (location_t loc = cp_expr_location (expr)) 3560 return loc; 3561 3562 /* If the constraint is normalized from a requires-clause, give 3563 the location as that of the constrained declaration. */ 3564 tree cxt = CONSTR_CONTEXT (t); 3565 tree src = cxt ? TREE_VALUE (cxt) : NULL_TREE; 3566 if (!src) 3567 /* TODO: This only happens for constrained non-template declarations. */ 3568 ; 3569 else if (DECL_P (src)) 3570 return DECL_SOURCE_LOCATION (src); 3571 /* Otherwise, give the location as the defining concept. */ 3572 else if (concept_check_p (src)) 3573 { 3574 tree id = unpack_concept_check (src); 3575 tree tmpl = TREE_OPERAND (id, 0); 3576 if (OVL_P (tmpl)) 3577 tmpl = OVL_FIRST (tmpl); 3578 return DECL_SOURCE_LOCATION (tmpl); 3579 } 3580 3581 return input_location; 3582} 3583 3584/* Emit a diagnostic for a failed trait. */ 3585 3586static void 3587diagnose_trait_expr (tree expr, tree args) 3588{ 3589 location_t loc = cp_expr_location (expr); 3590 3591 /* Build a "fake" version of the instantiated trait, so we can 3592 get the instantiated types from result. */ 3593 ++processing_template_decl; 3594 expr = tsubst_expr (expr, args, tf_none, NULL_TREE, false); 3595 --processing_template_decl; 3596 3597 tree t1 = TRAIT_EXPR_TYPE1 (expr); 3598 tree t2 = TRAIT_EXPR_TYPE2 (expr); 3599 switch (TRAIT_EXPR_KIND (expr)) 3600 { 3601 case CPTK_HAS_NOTHROW_ASSIGN: 3602 inform (loc, " %qT is not %<nothrow%> copy assignable", t1); 3603 break; 3604 case CPTK_HAS_NOTHROW_CONSTRUCTOR: 3605 inform (loc, " %qT is not %<nothrow%> default constructible", t1); 3606 break; 3607 case CPTK_HAS_NOTHROW_COPY: 3608 inform (loc, " %qT is not %<nothrow%> copy constructible", t1); 3609 break; 3610 case CPTK_HAS_TRIVIAL_ASSIGN: 3611 inform (loc, " %qT is not trivially copy assignable", t1); 3612 break; 3613 case CPTK_HAS_TRIVIAL_CONSTRUCTOR: 3614 inform (loc, " %qT is not trivially default constructible", t1); 3615 break; 3616 case CPTK_HAS_TRIVIAL_COPY: 3617 inform (loc, " %qT is not trivially copy constructible", t1); 3618 break; 3619 case CPTK_HAS_TRIVIAL_DESTRUCTOR: 3620 inform (loc, " %qT is not trivially destructible", t1); 3621 break; 3622 case CPTK_HAS_VIRTUAL_DESTRUCTOR: 3623 inform (loc, " %qT does not have a virtual destructor", t1); 3624 break; 3625 case CPTK_IS_ABSTRACT: 3626 inform (loc, " %qT is not an abstract class", t1); 3627 break; 3628 case CPTK_IS_BASE_OF: 3629 inform (loc, " %qT is not a base of %qT", t1, t2); 3630 break; 3631 case CPTK_IS_CLASS: 3632 inform (loc, " %qT is not a class", t1); 3633 break; 3634 case CPTK_IS_EMPTY: 3635 inform (loc, " %qT is not an empty class", t1); 3636 break; 3637 case CPTK_IS_ENUM: 3638 inform (loc, " %qT is not an enum", t1); 3639 break; 3640 case CPTK_IS_FINAL: 3641 inform (loc, " %qT is not a final class", t1); 3642 break; 3643 case CPTK_IS_LAYOUT_COMPATIBLE: 3644 inform (loc, " %qT is not layout compatible with %qT", t1, t2); 3645 break; 3646 case CPTK_IS_LITERAL_TYPE: 3647 inform (loc, " %qT is not a literal type", t1); 3648 break; 3649 case CPTK_IS_POINTER_INTERCONVERTIBLE_BASE_OF: 3650 inform (loc, " %qT is not pointer-interconvertible base of %qT", 3651 t1, t2); 3652 break; 3653 case CPTK_IS_POD: 3654 inform (loc, " %qT is not a POD type", t1); 3655 break; 3656 case CPTK_IS_POLYMORPHIC: 3657 inform (loc, " %qT is not a polymorphic type", t1); 3658 break; 3659 case CPTK_IS_SAME_AS: 3660 inform (loc, " %qT is not the same as %qT", t1, t2); 3661 break; 3662 case CPTK_IS_STD_LAYOUT: 3663 inform (loc, " %qT is not an standard layout type", t1); 3664 break; 3665 case CPTK_IS_TRIVIAL: 3666 inform (loc, " %qT is not a trivial type", t1); 3667 break; 3668 case CPTK_IS_UNION: 3669 inform (loc, " %qT is not a union", t1); 3670 break; 3671 case CPTK_IS_AGGREGATE: 3672 inform (loc, " %qT is not an aggregate", t1); 3673 break; 3674 case CPTK_IS_TRIVIALLY_COPYABLE: 3675 inform (loc, " %qT is not trivially copyable", t1); 3676 break; 3677 case CPTK_IS_ASSIGNABLE: 3678 inform (loc, " %qT is not assignable from %qT", t1, t2); 3679 break; 3680 case CPTK_IS_TRIVIALLY_ASSIGNABLE: 3681 inform (loc, " %qT is not trivially assignable from %qT", t1, t2); 3682 break; 3683 case CPTK_IS_NOTHROW_ASSIGNABLE: 3684 inform (loc, " %qT is not %<nothrow%> assignable from %qT", t1, t2); 3685 break; 3686 case CPTK_IS_CONSTRUCTIBLE: 3687 if (!t2) 3688 inform (loc, " %qT is not default constructible", t1); 3689 else 3690 inform (loc, " %qT is not constructible from %qE", t1, t2); 3691 break; 3692 case CPTK_IS_TRIVIALLY_CONSTRUCTIBLE: 3693 if (!t2) 3694 inform (loc, " %qT is not trivially default constructible", t1); 3695 else 3696 inform (loc, " %qT is not trivially constructible from %qE", t1, t2); 3697 break; 3698 case CPTK_IS_NOTHROW_CONSTRUCTIBLE: 3699 if (!t2) 3700 inform (loc, " %qT is not %<nothrow%> default constructible", t1); 3701 else 3702 inform (loc, " %qT is not %<nothrow%> constructible from %qE", t1, t2); 3703 break; 3704 case CPTK_HAS_UNIQUE_OBJ_REPRESENTATIONS: 3705 inform (loc, " %qT does not have unique object representations", t1); 3706 break; 3707 case CPTK_BASES: 3708 case CPTK_DIRECT_BASES: 3709 case CPTK_UNDERLYING_TYPE: 3710 /* We shouldn't see these non-expression traits. */ 3711 gcc_unreachable (); 3712 /* We deliberately omit the default case so that when adding a new 3713 trait we'll get reminded (by way of a warning) to handle it here. */ 3714 } 3715} 3716 3717/* Diagnose a substitution failure in the atomic constraint T using ARGS. */ 3718 3719static void 3720diagnose_atomic_constraint (tree t, tree args, tree result, sat_info info) 3721{ 3722 /* If the constraint is already ill-formed, we've previously diagnosed 3723 the reason. We should still say why the constraints aren't satisfied. */ 3724 if (t == error_mark_node) 3725 { 3726 location_t loc; 3727 if (info.in_decl) 3728 loc = DECL_SOURCE_LOCATION (info.in_decl); 3729 else 3730 loc = input_location; 3731 inform (loc, "invalid constraints"); 3732 return; 3733 } 3734 3735 location_t loc = get_constraint_error_location (t); 3736 iloc_sentinel loc_s (loc); 3737 3738 /* Generate better diagnostics for certain kinds of expressions. */ 3739 tree expr = ATOMIC_CONSTR_EXPR (t); 3740 STRIP_ANY_LOCATION_WRAPPER (expr); 3741 switch (TREE_CODE (expr)) 3742 { 3743 case TRAIT_EXPR: 3744 diagnose_trait_expr (expr, args); 3745 break; 3746 case REQUIRES_EXPR: 3747 gcc_checking_assert (info.diagnose_unsatisfaction_p ()); 3748 /* Clear in_decl before replaying the substitution to avoid emitting 3749 seemingly unhelpful "in declaration ..." notes that follow some 3750 substitution failure error messages. */ 3751 info.in_decl = NULL_TREE; 3752 tsubst_requires_expr (expr, args, info); 3753 break; 3754 default: 3755 if (!same_type_p (TREE_TYPE (result), boolean_type_node)) 3756 error_at (loc, "constraint %qE has type %qT, not %<bool%>", 3757 t, TREE_TYPE (result)); 3758 else 3759 inform (loc, "the expression %qE evaluated to %<false%>", t); 3760 } 3761} 3762 3763GTY(()) tree current_failed_constraint; 3764 3765diagnosing_failed_constraint:: 3766diagnosing_failed_constraint (tree t, tree args, bool diag) 3767 : diagnosing_error (diag) 3768{ 3769 if (diagnosing_error) 3770 { 3771 current_failed_constraint 3772 = tree_cons (args, t, current_failed_constraint); 3773 ++current_constraint_diagnosis_depth; 3774 } 3775} 3776 3777diagnosing_failed_constraint:: 3778~diagnosing_failed_constraint () 3779{ 3780 if (diagnosing_error) 3781 { 3782 --current_constraint_diagnosis_depth; 3783 if (current_failed_constraint) 3784 current_failed_constraint = TREE_CHAIN (current_failed_constraint); 3785 } 3786 3787} 3788 3789/* Whether we are allowed to replay an error that underlies a constraint failure 3790 at the current diagnosis depth. */ 3791 3792bool 3793diagnosing_failed_constraint::replay_errors_p () 3794{ 3795 if (current_constraint_diagnosis_depth >= concepts_diagnostics_max_depth) 3796 { 3797 concepts_diagnostics_max_depth_exceeded_p = true; 3798 return false; 3799 } 3800 else 3801 return true; 3802} 3803 3804/* Emit diagnostics detailing the failure ARGS to satisfy the constraints 3805 of T. Here, T and ARGS are as in constraints_satisfied_p. */ 3806 3807void 3808diagnose_constraints (location_t loc, tree t, tree args) 3809{ 3810 inform (loc, "constraints not satisfied"); 3811 3812 if (concepts_diagnostics_max_depth == 0) 3813 return; 3814 3815 /* Replay satisfaction, but diagnose unsatisfaction. */ 3816 sat_info noisy (tf_warning_or_error, NULL_TREE, /*diag_unsat=*/true); 3817 constraint_satisfaction_value (t, args, noisy); 3818 3819 static bool suggested_p; 3820 if (concepts_diagnostics_max_depth_exceeded_p 3821 && current_constraint_diagnosis_depth == 0 3822 && !suggested_p) 3823 { 3824 inform (UNKNOWN_LOCATION, 3825 "set %qs to at least %d for more detail", 3826 "-fconcepts-diagnostics-depth=", 3827 concepts_diagnostics_max_depth + 1); 3828 suggested_p = true; 3829 } 3830} 3831 3832#include "gt-cp-constraint.h" 3833