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