1 /* Processing rules for constraints.
2 Copyright (C) 2013-2016 Free Software Foundation, Inc.
3 Contributed by Andrew Sutton (andrew.n.sutton@gmail.com)
5 This file is part of GCC.
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)
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.
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/>. */
23 #include "coretypes.h"
29 #include "double-int.h"
36 #include "stringpool.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"
47 #include "type-utils.h"
49 /*---------------------------------------------------------------------------
50 Operations on constraints
51 ---------------------------------------------------------------------------*/
53 /* Returns true if C is a constraint tree code. Note that ERROR_MARK
54 is a valid constraint. */
57 constraint_p (tree_code c)
59 return ((PRED_CONSTR <= c && c <= DISJ_CONSTR)
60 || c == EXPR_PACK_EXPANSION
64 /* Returns true if T is a constraint. Note that error_mark_node
65 is a valid constraint. */
70 return constraint_p (TREE_CODE (t));
73 /* Returns the conjunction of two constraints A and B. Note that
74 conjoining a non-null constraint with NULL_TREE is an identity
75 operation. That is, for non-null A,
77 conjoin_constraints(a, NULL_TREE) == a
81 conjoin_constraints (NULL_TREE, a) == a
83 If both A and B are NULL_TREE, the result is also NULL_TREE. */
86 conjoin_constraints (tree a, tree b)
88 gcc_assert (a ? constraint_p (a) : true);
89 gcc_assert (b ? constraint_p (b) : true);
91 return b ? build_nt (CONJ_CONSTR, a, b) : a;
98 /* Transform the vector of expressions in the T into a conjunction
99 of requirements. T must be a TREE_VEC. */
102 conjoin_constraints (tree t)
104 gcc_assert (TREE_CODE (t) == TREE_VEC);
106 for (int i = 0; i < TREE_VEC_LENGTH (t); ++i)
107 r = conjoin_constraints (r, TREE_VEC_ELT (t, i));
111 /* Returns true if T is a call expression to a function
115 function_concept_check_p (tree t)
117 gcc_assert (TREE_CODE (t) == CALL_EXPR);
118 tree fn = CALL_EXPR_FN (t);
119 if (TREE_CODE (fn) == TEMPLATE_ID_EXPR
120 && TREE_CODE (TREE_OPERAND (fn, 0)) == OVERLOAD)
122 tree f1 = get_first_fn (fn);
123 if (TREE_CODE (f1) == TEMPLATE_DECL
124 && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (f1)))
130 /* Returns true if any of the arguments in the template
131 argument list is a wildcard or wildcard pack. */
134 contains_wildcard_p (tree args)
136 for (int i = 0; i < TREE_VEC_LENGTH (args); ++i)
138 tree arg = TREE_VEC_ELT (args, i);
139 if (TREE_CODE (arg) == WILDCARD_DECL)
145 /* Build a new call expression, but don't actually generate a
146 new function call. We just want the tree, not the semantics. */
149 build_call_check (tree id)
151 ++processing_template_decl;
152 vec<tree, va_gc> *fargs = make_tree_vector();
153 tree call = finish_call_expr (id, &fargs, false, false, tf_none);
154 release_tree_vector (fargs);
155 --processing_template_decl;
159 /* Build an expression that will check a variable concept. If any
160 argument contains a wildcard, don't try to finish the variable
161 template because we can't substitute into a non-existent
165 build_variable_check (tree id)
167 gcc_assert (TREE_CODE (id) == TEMPLATE_ID_EXPR);
168 if (contains_wildcard_p (TREE_OPERAND (id, 1)))
171 ++processing_template_decl;
172 tree var = finish_template_variable (id);
173 --processing_template_decl;
177 /*---------------------------------------------------------------------------
178 Resolution of qualified concept names
179 ---------------------------------------------------------------------------*/
181 /* This facility is used to resolve constraint checks from
182 requirement expressions. A constraint check is a call to
183 a function template declared with the keyword 'concept'.
185 The result of resolution is a pair (a TREE_LIST) whose value
186 is the matched declaration, and whose purpose contains the
187 coerced template arguments that can be substituted into the
190 // Given an overload set OVL, try to find a unique definition that can be
191 // instantiated by the template arguments ARGS.
193 // This function is not called for arbitrary call expressions. In particular,
194 // the call expression must be written with explicit template arguments
195 // and no function arguments. For example:
199 // If a single match is found, this returns a TREE_LIST whose VALUE
200 // is the constraint function (not the template), and its PURPOSE is
201 // the complete set of arguments substituted into the parameter list.
203 resolve_constraint_check (tree ovl, tree args)
206 tree cands = NULL_TREE;
207 for (tree p = ovl; p != NULL_TREE; p = OVL_NEXT (p))
209 // Get the next template overload.
210 tree tmpl = OVL_CURRENT (p);
211 if (TREE_CODE (tmpl) != TEMPLATE_DECL)
214 // Don't try to deduce checks for non-concepts. We often
215 // end up trying to resolve constraints in functional casts
216 // as part of a postfix-expression. We can save time and
217 // headaches by not instantiating those declarations.
219 // NOTE: This masks a potential error, caused by instantiating
220 // non-deduced contexts using placeholder arguments.
221 tree fn = DECL_TEMPLATE_RESULT (tmpl);
222 if (DECL_ARGUMENTS (fn))
224 if (!DECL_DECLARED_CONCEPT_P (fn))
227 // Remember the candidate if we can deduce a substitution.
228 ++processing_template_decl;
229 tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl));
230 if (tree subst = coerce_template_parms (parms, args, tmpl))
232 if (subst == error_mark_node)
235 cands = tree_cons (subst, fn, cands);
237 --processing_template_decl;
241 /* We either had no candidates or failed deductions. */
242 return nerrs ? error_mark_node : NULL_TREE;
243 else if (TREE_CHAIN (cands))
244 /* There are multiple candidates. */
245 return error_mark_node;
250 // Determine if the the call expression CALL is a constraint check, and
251 // return the concept declaration and arguments being checked. If CALL
252 // does not denote a constraint check, return NULL.
254 resolve_constraint_check (tree call)
256 gcc_assert (TREE_CODE (call) == CALL_EXPR);
258 // A constraint check must be only a template-id expression. If
259 // it's a call to a base-link, its function(s) should be a
260 // template-id expression. If this is not a template-id, then it
261 // cannot be a concept-check.
262 tree target = CALL_EXPR_FN (call);
263 if (BASELINK_P (target))
264 target = BASELINK_FUNCTIONS (target);
265 if (TREE_CODE (target) != TEMPLATE_ID_EXPR)
268 // Get the overload set and template arguments and try to
269 // resolve the target.
270 tree ovl = TREE_OPERAND (target, 0);
272 /* This is a function call of a variable concept... ill-formed. */
273 if (TREE_CODE (ovl) == TEMPLATE_DECL)
275 error_at (location_of (call),
276 "function call of variable concept %qE", call);
277 return error_mark_node;
280 tree args = TREE_OPERAND (target, 1);
281 return resolve_constraint_check (ovl, args);
284 /* Returns a pair containing the checked variable concept
285 and its associated prototype parameter. The result
286 is a TREE_LIST whose TREE_VALUE is the variable concept
287 and whose TREE_PURPOSE is the prototype parameter. */
290 resolve_variable_concept_check (tree id)
292 tree tmpl = TREE_OPERAND (id, 0);
293 tree args = TREE_OPERAND (id, 1);
295 if (!variable_concept_p (tmpl))
298 /* Make sure that we have the right parameters before
299 assuming that it works. Note that failing to deduce
300 will result in diagnostics. */
301 tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl));
302 ++processing_template_decl;
303 tree result = coerce_template_parms (parms, args, tmpl);
304 --processing_template_decl;
305 if (result != error_mark_node)
307 tree decl = DECL_TEMPLATE_RESULT (tmpl);
308 return build_tree_list (result, decl);
311 return error_mark_node;
315 /* Given a call expression or template-id expression to
316 a concept EXPR possibly including a wildcard, deduce
317 the concept being checked and the prototype parameter.
318 Returns true if the constraint and prototype can be
319 deduced and false otherwise. Note that the CHECK and
320 PROTO arguments are set to NULL_TREE if this returns
324 deduce_constrained_parameter (tree expr, tree& check, tree& proto)
326 tree info = NULL_TREE;
327 if (TREE_CODE (expr) == TEMPLATE_ID_EXPR)
328 info = resolve_variable_concept_check (expr);
329 else if (TREE_CODE (expr) == CALL_EXPR)
330 info = resolve_constraint_check (expr);
334 if (info && info != error_mark_node)
336 check = TREE_VALUE (info);
337 tree arg = TREE_VEC_ELT (TREE_PURPOSE (info), 0);
338 if (ARGUMENT_PACK_P (arg))
339 arg = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg), 0);
340 proto = TREE_TYPE (arg);
343 check = proto = NULL_TREE;
347 // Given a call expression or template-id expression to a concept, EXPR,
348 // deduce the concept being checked and return the template arguments.
349 // Returns NULL_TREE if deduction fails.
351 deduce_concept_introduction (tree expr)
353 tree info = NULL_TREE;
354 if (TREE_CODE (expr) == TEMPLATE_ID_EXPR)
355 info = resolve_variable_concept_check (expr);
356 else if (TREE_CODE (expr) == CALL_EXPR)
357 info = resolve_constraint_check (expr);
361 if (info && info != error_mark_node)
362 return TREE_PURPOSE (info);
368 /*---------------------------------------------------------------------------
369 Constraint implication learning
370 ---------------------------------------------------------------------------*/
372 /* The implication context determines how we memoize concept checks.
373 Given two checks C1 and C2, the direction of implication depends
374 on whether we are learning implications of a conjunction or disjunction.
377 template<typename T> concept bool C = ...;
378 template<typenaem T> concept bool D = C<T> && true;
380 From this, we can learn that D<T> implies C<T>. We cannot learn,
381 without further testing, that C<T> does not imply D<T>. If, for
382 example, C<T> were defined as true, then these constraints would
383 be logically equivalent.
385 In rare cases, we may start with a logical equivalence. For example:
387 template<typename T> concept bool C = ...;
388 template<typename T> concept bool D = C<T>;
390 Here, we learn that C<T> implies D<T> and vice versa. */
392 enum implication_context
394 conjunction_cxt, /* C1 implies C2. */
395 disjunction_cxt, /* C2 implies C1. */
396 equivalence_cxt /* C1 implies C2, C2 implies C1. */
399 void learn_implications(tree, tree, implication_context);
402 learn_implication (tree parent, tree child, implication_context cxt)
406 case conjunction_cxt:
407 save_subsumption_result (parent, child, true);
409 case disjunction_cxt:
410 save_subsumption_result (child, parent, true);
412 case equivalence_cxt:
413 save_subsumption_result (parent, child, true);
414 save_subsumption_result (child, parent, true);
420 learn_logical_operation (tree parent, tree constr, implication_context cxt)
422 learn_implications (parent, TREE_OPERAND (constr, 0), cxt);
423 learn_implications (parent, TREE_OPERAND (constr, 1), cxt);
427 learn_implications (tree parent, tree constr, implication_context cxt)
429 switch (TREE_CODE (constr))
432 return learn_implication (parent, constr, cxt);
435 if (cxt == disjunction_cxt)
437 return learn_logical_operation (parent, constr, cxt);
440 if (cxt == conjunction_cxt)
442 return learn_logical_operation (parent, constr, cxt);
449 /* Quickly scan the top-level constraints of CONSTR to learn and
450 cache logical relations between concepts. The search does not
451 include conjunctions of disjunctions or vice versa. */
454 learn_implications (tree tmpl, tree args, tree constr)
456 /* Don't memoize relations between non-dependent arguemnts. It's not
458 if (!uses_template_parms (args))
461 /* Build a check constraint for the purpose of caching. */
462 tree parent = build_nt (CHECK_CONSTR, tmpl, args);
464 /* Start learning based on the kind of the top-level contraint. */
465 if (TREE_CODE (constr) == CONJ_CONSTR)
466 return learn_logical_operation (parent, constr, conjunction_cxt);
467 else if (TREE_CODE (constr) == DISJ_CONSTR)
468 return learn_logical_operation (parent, constr, disjunction_cxt);
469 else if (TREE_CODE (constr) == CHECK_CONSTR)
470 /* This is the rare concept alias case. */
471 return learn_implication (parent, constr, equivalence_cxt);
474 /*---------------------------------------------------------------------------
475 Expansion of concept definitions
476 ---------------------------------------------------------------------------*/
478 /* Returns the expression of a function concept. */
481 get_returned_expression (tree fn)
483 /* Extract the body of the function minus the return expression. */
484 tree body = DECL_SAVED_TREE (fn);
486 return error_mark_node;
487 if (TREE_CODE (body) == BIND_EXPR)
488 body = BIND_EXPR_BODY (body);
489 if (TREE_CODE (body) != RETURN_EXPR)
490 return error_mark_node;
492 return TREE_OPERAND (body, 0);
495 /* Returns the initializer of a variable concept. */
498 get_variable_initializer (tree var)
500 tree init = DECL_INITIAL (var);
502 return error_mark_node;
506 /* Returns the definition of a variable or function concept. */
509 get_concept_definition (tree decl)
511 if (TREE_CODE (decl) == VAR_DECL)
512 return get_variable_initializer (decl);
513 else if (TREE_CODE (decl) == FUNCTION_DECL)
514 return get_returned_expression (decl);
518 int expansion_level = 0;
520 struct expanding_concept_sentinel
522 expanding_concept_sentinel ()
527 ~expanding_concept_sentinel()
536 /* Returns true when a concept is being expanded. */
541 return expansion_level > 0;
544 /* Expand a concept declaration (not a template) and its arguments to
545 a constraint defined by the concept's initializer or definition. */
548 expand_concept (tree decl, tree args)
550 expanding_concept_sentinel sentinel;
552 if (TREE_CODE (decl) == TEMPLATE_DECL)
553 decl = DECL_TEMPLATE_RESULT (decl);
554 tree tmpl = DECL_TI_TEMPLATE (decl);
556 /* Check for a previous specialization. */
557 if (tree spec = get_concept_expansion (tmpl, args))
560 /* Substitute the arguments to form a new definition expression. */
561 tree def = get_concept_definition (decl);
563 ++processing_template_decl;
564 tree result = tsubst_expr (def, args, tf_none, NULL_TREE, true);
565 --processing_template_decl;
566 if (result == error_mark_node)
567 return error_mark_node;
569 /* And lastly, normalize it, check for implications, and save
570 the specialization for later. */
571 tree norm = normalize_expression (result);
572 learn_implications (tmpl, args, norm);
573 return save_concept_expansion (tmpl, args, norm);
577 /*---------------------------------------------------------------------------
578 Stepwise normalization of expressions
580 This set of functions will transform an expression into a constraint
581 in a sequence of steps. Normalization does not not look into concept
583 ---------------------------------------------------------------------------*/
585 /* Transform a logical-or or logical-and expression into either
586 a conjunction or disjunction. */
589 normalize_logical_operation (tree t, tree_code c)
591 tree t0 = normalize_expression (TREE_OPERAND (t, 0));
592 tree t1 = normalize_expression (TREE_OPERAND (t, 1));
593 return build_nt (c, t0, t1);
596 /* A simple requirement T introduces an expression constraint
597 for its expression. */
600 normalize_simple_requirement (tree t)
602 return build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0));
605 /* A type requirement T introduce a type constraint for its type. */
608 normalize_type_requirement (tree t)
610 return build_nt (TYPE_CONSTR, TREE_OPERAND (t, 0));
613 /* A compound requirement T introduces a conjunction of constraints
614 depending on its form. The conjunction always includes an
615 expression constraint for the expression of the requirement.
616 If a trailing return type was specified, the conjunction includes
617 either an implicit conversion constraint or an argument deduction
618 constraint. If the noexcept specifier is present, the conjunction
619 includes an exception constraint. */
622 normalize_compound_requirement (tree t)
624 tree expr = TREE_OPERAND (t, 0);
625 tree constr = build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0));
627 /* If a type is given, append an implicit conversion or
628 argument deduction constraint. */
629 if (tree type = TREE_OPERAND (t, 1))
632 /* TODO: We should be extracting a list of auto nodes
633 from type_uses_auto, not a single node */
634 if (tree placeholder = type_uses_auto (type))
635 type_constr = build_nt (DEDUCT_CONSTR, expr, type, placeholder);
637 type_constr = build_nt (ICONV_CONSTR, expr, type);
638 constr = conjoin_constraints (constr, type_constr);
641 /* If noexcept is present, append an exception constraint. */
642 if (COMPOUND_REQ_NOEXCEPT_P (t))
644 tree except = build_nt (EXCEPT_CONSTR, expr);
645 constr = conjoin_constraints (constr, except);
651 /* A nested requirement T introduces a conjunction of constraints
652 corresponding to its constraint-expression.
654 If the result of transforming T is error_mark_node, the resulting
655 constraint is a predicate constraint whose operand is also
656 error_mark_node. This preserves the constraint structure, but
657 will guarantee that the constraint is never satisfied. */
660 normalize_nested_requirement (tree t)
662 return normalize_expression (TREE_OPERAND (t, 0));
665 /* Transform a requirement T into one or more constraints. */
668 normalize_requirement (tree t)
670 switch (TREE_CODE (t))
673 return normalize_simple_requirement (t);
676 return normalize_type_requirement (t);
679 return normalize_compound_requirement (t);
682 return normalize_nested_requirement (t);
687 return error_mark_node;
690 /* Transform a sequence of requirements into a conjunction of
694 normalize_requirements (tree t)
696 tree result = NULL_TREE;
697 for (; t; t = TREE_CHAIN (t))
699 tree constr = normalize_requirement (TREE_VALUE (t));
700 result = conjoin_constraints (result, constr);
705 /* The normal form of a requires-expression is a parameterized
706 constraint having the same parameters and a conjunction of
707 constraints representing the normal form of requirements. */
710 normalize_requires_expression (tree t)
712 tree operand = normalize_requirements (TREE_OPERAND (t, 1));
713 if (tree parms = TREE_OPERAND (t, 0))
714 return build_nt (PARM_CONSTR, parms, operand);
719 /* For a template-id referring to a variable concept, returns
720 a check constraint. Otherwise, returns a predicate constraint. */
723 normalize_template_id_expression (tree t)
725 if (tree info = resolve_variable_concept_check (t))
727 if (info == error_mark_node)
729 /* We get this when the template arguments don't match
730 the variable concept. */
731 error ("invalid reference to concept %qE", t);
732 return error_mark_node;
735 tree decl = TREE_VALUE (info);
736 tree args = TREE_PURPOSE (info);
737 return build_nt (CHECK_CONSTR, decl, args);
740 /* Check that we didn't refer to a function concept like a variable. */
741 tree tmpl = TREE_OPERAND (t, 0);
742 if (TREE_CODE (tmpl) == OVERLOAD)
744 tree fn = OVL_FUNCTION (tmpl);
745 if (TREE_CODE (fn) == TEMPLATE_DECL
746 && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (fn)))
748 error_at (location_of (t),
749 "invalid reference to function concept %qD", fn);
750 return error_mark_node;
754 return build_nt (PRED_CONSTR, t);
757 /* For a call expression to a function concept, returns a check
758 constraint. Otherwise, returns a predicate constraint. */
761 normalize_call_expression (tree t)
763 /* Try to resolve this function call as a concept. If not, then
764 it can be returned as a predicate constraint. */
765 tree check = resolve_constraint_check (t);
767 return build_nt (PRED_CONSTR, t);
768 if (check == error_mark_node)
770 /* TODO: Improve diagnostics. We could report why the reference
772 error ("invalid reference to concept %qE", t);
773 return error_mark_node;
776 tree fn = TREE_VALUE (check);
777 tree args = TREE_PURPOSE (check);
778 return build_nt (CHECK_CONSTR, fn, args);
781 /* If T is a call to an overloaded && or || operator, diagnose that
782 as a non-SFINAEable error. Returns true if an error is emitted.
784 TODO: It would be better to diagnose this at the point of definition,
785 if possible. Perhaps we should immediately do a first-pass normalization
786 of a concept definition to catch obvious non-dependent errors like
790 check_for_logical_overloads (tree t)
792 if (TREE_CODE (t) != CALL_EXPR)
795 tree fn = CALL_EXPR_FN (t);
797 /* For member calls, try extracting the function from the
799 if (TREE_CODE (fn) == COMPONENT_REF)
801 fn = TREE_OPERAND (fn, 1);
802 if (TREE_CODE (fn) == BASELINK)
803 fn = BASELINK_FUNCTIONS (fn);
806 if (TREE_CODE (fn) != FUNCTION_DECL)
809 if (DECL_OVERLOADED_OPERATOR_P (fn))
811 location_t loc = EXPR_LOC_OR_LOC (t, input_location);
812 error_at (loc, "constraint %qE, uses overloaded operator", t);
819 /* The normal form of an atom depends on the expression. The normal
820 form of a function call to a function concept is a check constraint
821 for that concept. The normal form of a reference to a variable
822 concept is a check constraint for that concept. Otherwise, the
823 constraint is a predicate constraint. */
826 normalize_atom (tree t)
828 /* We can get constraints pushed down through pack expansions, so
830 if (constraint_p (t))
833 tree type = TREE_TYPE (t);
834 if (!type || type_unknown_p (t) || TREE_CODE (type) == TEMPLATE_TYPE_PARM)
836 else if (!dependent_type_p (type))
838 if (check_for_logical_overloads (t))
839 return error_mark_node;
841 type = cv_unqualified (type);
842 if (!same_type_p (type, boolean_type_node))
844 error ("predicate constraint %q+E does not have type %<bool%>", t);
845 return error_mark_node;
849 if (TREE_CODE (t) == TEMPLATE_ID_EXPR)
850 return normalize_template_id_expression (t);
851 if (TREE_CODE (t) == CALL_EXPR)
852 return normalize_call_expression (t);
853 return build_nt (PRED_CONSTR, t);
856 /* Push down the pack expansion EXP into the leaves of the constraint PAT. */
859 push_down_pack_expansion (tree exp, tree pat)
861 switch (TREE_CODE (pat))
866 pat = copy_node (pat);
867 TREE_OPERAND (pat, 0)
868 = push_down_pack_expansion (exp, TREE_OPERAND (pat, 0));
869 TREE_OPERAND (pat, 1)
870 = push_down_pack_expansion (exp, TREE_OPERAND (pat, 1));
875 exp = copy_node (exp);
876 SET_PACK_EXPANSION_PATTERN (exp, pat);
882 /* Transform a pack expansion into a constraint. First we transform the
883 pattern of the pack expansion, then we push the pack expansion down into the
884 leaves of the constraint so that partial ordering will work. */
887 normalize_pack_expansion (tree t)
889 tree pat = normalize_expression (PACK_EXPANSION_PATTERN (t));
890 return push_down_pack_expansion (t, pat);
893 /* Transform an expression into a constraint. */
896 normalize_any_expression (tree t)
898 switch (TREE_CODE (t))
900 case TRUTH_ANDIF_EXPR:
901 return normalize_logical_operation (t, CONJ_CONSTR);
903 case TRUTH_ORIF_EXPR:
904 return normalize_logical_operation (t, DISJ_CONSTR);
907 return normalize_requires_expression (t);
910 return normalize_expression (BIND_EXPR_BODY (t));
912 case EXPR_PACK_EXPANSION:
913 return normalize_pack_expansion (t);
916 /* All other constraints are atomic. */
917 return normalize_atom (t);
921 /* Transform a statement into an expression. */
923 normalize_any_statement (tree t)
925 switch (TREE_CODE (t))
928 return normalize_expression (TREE_OPERAND (t, 0));
932 return error_mark_node;
935 /* Reduction rules for the declaration T. */
938 normalize_any_declaration (tree t)
940 switch (TREE_CODE (t))
943 return normalize_atom (t);
947 return error_mark_node;
950 /* Returns the normal form of a constraint expression. */
953 normalize_expression (tree t)
958 if (t == error_mark_node)
959 return error_mark_node;
961 switch (TREE_CODE_CLASS (TREE_CODE (t)))
967 return normalize_any_expression (t);
970 return normalize_any_statement (t);
972 case tcc_declaration:
973 return normalize_any_declaration (t);
975 case tcc_exceptional:
979 /* These are all atomic predicate constraints. */
980 return normalize_atom (t);
983 /* Unhandled node kind. */
986 return error_mark_node;
990 /*---------------------------------------------------------------------------
991 Constraint normalization
992 ---------------------------------------------------------------------------*/
994 tree normalize_constraint (tree);
996 /* The normal form of the disjunction T0 /\ T1 is the conjunction
997 of the normal form of T0 and the normal form of T1. */
1000 normalize_conjunction (tree t)
1002 tree t0 = normalize_constraint (TREE_OPERAND (t, 0));
1003 tree t1 = normalize_constraint (TREE_OPERAND (t, 1));
1004 return build_nt (CONJ_CONSTR, t0, t1);
1007 /* The normal form of the disjunction T0 \/ T1 is the disjunction
1008 of the normal form of T0 and the normal form of T1. */
1011 normalize_disjunction (tree t)
1013 tree t0 = normalize_constraint (TREE_OPERAND (t, 0));
1014 tree t1 = normalize_constraint (TREE_OPERAND (t, 1));
1015 return build_nt (DISJ_CONSTR, t0, t1);
1018 /* A predicate constraint is normalized in two stages. First all
1019 references specializations of concepts are replaced by their
1020 substituted definitions. Then, the resulting expression is
1021 transformed into a constraint by transforming && expressions
1022 into conjunctions and || into disjunctions. */
1025 normalize_predicate_constraint (tree t)
1027 ++processing_template_decl;
1028 tree expr = PRED_CONSTR_EXPR (t);
1029 tree constr = normalize_expression (expr);
1030 --processing_template_decl;
1034 /* The normal form of a parameterized constraint is the normal
1035 form of its operand. */
1038 normalize_parameterized_constraint (tree t)
1040 tree parms = PARM_CONSTR_PARMS (t);
1041 tree operand = normalize_constraint (PARM_CONSTR_OPERAND (t));
1042 return build_nt (PARM_CONSTR, parms, operand);
1045 /* Normalize the constraint T by reducing it so that it is
1046 comprised of only conjunctions and disjunctions of atomic
1050 normalize_constraint (tree t)
1055 if (t == error_mark_node)
1058 switch (TREE_CODE (t))
1061 return normalize_conjunction (t);
1064 return normalize_disjunction (t);
1067 return normalize_predicate_constraint (t);
1070 return normalize_parameterized_constraint (t);
1077 /* These constraints are defined to be atomic. */
1081 /* CONSTR was not a constraint. */
1084 return error_mark_node;
1089 // -------------------------------------------------------------------------- //
1090 // Constraint Semantic Processing
1092 // The following functions are called by the parser and substitution rules
1093 // to create and evaluate constraint-related nodes.
1095 // The constraints associated with the current template parameters.
1097 current_template_constraints (void)
1099 if (!current_template_parms)
1101 tree tmpl_constr = TEMPLATE_PARM_CONSTRAINTS (current_template_parms);
1102 return build_constraints (tmpl_constr, NULL_TREE);
1105 // If the recently parsed TYPE declares or defines a template or template
1106 // specialization, get its corresponding constraints from the current
1107 // template parameters and bind them to TYPE's declaration.
1109 associate_classtype_constraints (tree type)
1111 if (!type || type == error_mark_node || TREE_CODE (type) != RECORD_TYPE)
1114 // An explicit class template specialization has no template
1116 if (!current_template_parms)
1119 if (CLASSTYPE_IS_TEMPLATE (type) || CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1121 tree decl = TYPE_STUB_DECL (type);
1122 tree ci = current_template_constraints ();
1124 // An implicitly instantiated member template declaration already
1125 // has associated constraints. If it is defined outside of its
1126 // class, then we need match these constraints against those of
1127 // original declaration.
1128 if (tree orig_ci = get_constraints (decl))
1130 if (!equivalent_constraints (ci, orig_ci))
1132 // FIXME: Improve diagnostics.
1133 error ("%qT does not match any declaration", type);
1134 return error_mark_node;
1138 set_constraints (decl, ci);
1145 // Create an empty constraint info block.
1146 inline tree_constraint_info*
1147 build_constraint_info ()
1149 return (tree_constraint_info *)make_node (CONSTRAINT_INFO);
1154 /* Build a constraint-info object that contains the associated constraints
1155 of a declaration. This also includes the declaration's template
1156 requirements (TREQS) and any trailing requirements for a function
1157 declarator (DREQS). Note that both TREQS and DREQS must be constraints.
1159 If the declaration has neither template nor declaration requirements
1160 this returns NULL_TREE, indicating an unconstrained declaration. */
1163 build_constraints (tree tmpl_reqs, tree decl_reqs)
1165 gcc_assert (tmpl_reqs ? constraint_p (tmpl_reqs) : true);
1166 gcc_assert (decl_reqs ? constraint_p (decl_reqs) : true);
1168 if (!tmpl_reqs && !decl_reqs)
1171 tree_constraint_info* ci = build_constraint_info ();
1172 ci->template_reqs = tmpl_reqs;
1173 ci->declarator_reqs = decl_reqs;
1174 ci->associated_constr = conjoin_constraints (tmpl_reqs, decl_reqs);
1181 /* Construct a sequence of template arguments by prepending
1182 ARG to REST. Either ARG or REST may be null. */
1184 build_concept_check_arguments (tree arg, tree rest)
1186 gcc_assert (rest ? TREE_CODE (rest) == TREE_VEC : true);
1190 int n = rest ? TREE_VEC_LENGTH (rest) : 0;
1191 args = make_tree_vec (n + 1);
1192 TREE_VEC_ELT (args, 0) = arg;
1194 for (int i = 0; i < n; ++i)
1195 TREE_VEC_ELT (args, i + 1) = TREE_VEC_ELT (rest, i);
1196 int def = rest ? GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (rest) : 0;
1197 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args, def + 1);
1201 gcc_assert (rest != NULL_TREE);
1209 /* Construct an expression that checks the concept given by
1210 TARGET. The TARGET must be:
1212 - an OVERLOAD referring to one or more function concepts
1213 - a BASELINK referring to an overload set of the above, or
1214 - a TEMPLTATE_DECL referring to a variable concept.
1216 ARG and REST are the explicit template arguments for the
1217 eventual concept check. */
1219 build_concept_check (tree target, tree arg, tree rest)
1221 tree args = build_concept_check_arguments (arg, rest);
1222 if (variable_template_p (target))
1223 return build_variable_check (lookup_template_variable (target, args));
1225 return build_call_check (lookup_template_function (target, args));
1229 /* Returns a TYPE_DECL that contains sufficient information to
1230 build a template parameter of the same kind as PROTO and
1231 constrained by the concept declaration CNC. Note that PROTO
1232 is the first template parameter of CNC.
1234 If specified, ARGS provides additional arguments to the
1235 constraint check. */
1237 build_constrained_parameter (tree cnc, tree proto, tree args)
1239 tree name = DECL_NAME (cnc);
1240 tree type = TREE_TYPE (proto);
1241 tree decl = build_decl (input_location, TYPE_DECL, name, type);
1242 CONSTRAINED_PARM_PROTOTYPE (decl) = proto;
1243 CONSTRAINED_PARM_CONCEPT (decl) = cnc;
1244 CONSTRAINED_PARM_EXTRA_ARGS (decl) = args;
1248 /* Create a constraint expression for the given DECL that
1249 evaluates the requirements specified by CONSTR, a TYPE_DECL
1250 that contains all the information necessary to build the
1251 requirements (see finish_concept_name for the layout of
1254 Note that the constraints are neither reduced nor decomposed.
1255 That is done only after the requires clause has been parsed
1258 This will always return a CHECK_CONSTR. */
1260 finish_shorthand_constraint (tree decl, tree constr)
1262 /* No requirements means no constraints. */
1266 tree proto = CONSTRAINED_PARM_PROTOTYPE (constr);
1267 tree con = CONSTRAINED_PARM_CONCEPT (constr);
1268 tree args = CONSTRAINED_PARM_EXTRA_ARGS (constr);
1270 /* If the parameter declaration is variadic, but the concept
1271 is not then we need to apply the concept to every element
1273 bool is_proto_pack = template_parameter_pack_p (proto);
1274 bool is_decl_pack = template_parameter_pack_p (decl);
1275 bool apply_to_all_p = is_decl_pack && !is_proto_pack;
1277 /* Get the argument and overload used for the requirement
1278 and adjust it if we're going to expand later. */
1279 tree arg = template_parm_to_arg (build_tree_list (NULL_TREE, decl));
1281 arg = PACK_EXPANSION_PATTERN (TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg), 0));
1283 /* Build the concept check. If it the constraint needs to be
1284 applied to all elements of the parameter pack, then make
1285 the constraint an expansion. */
1287 tree tmpl = DECL_TI_TEMPLATE (con);
1288 if (TREE_CODE (con) == VAR_DECL)
1290 check = build_concept_check (tmpl, arg, args);
1294 tree ovl = build_overload (tmpl, NULL_TREE);
1295 check = build_concept_check (ovl, arg, args);
1298 /* Make the check a pack expansion if needed.
1300 FIXME: We should be making a fold expression. */
1303 check = make_pack_expansion (check);
1304 TREE_TYPE (check) = boolean_type_node;
1307 return normalize_expression (check);
1310 /* Returns a conjunction of shorthand requirements for the template
1311 parameter list PARMS. Note that the requirements are stored in
1312 the TYPE of each tree node. */
1314 get_shorthand_constraints (tree parms)
1316 tree result = NULL_TREE;
1317 parms = INNERMOST_TEMPLATE_PARMS (parms);
1318 for (int i = 0; i < TREE_VEC_LENGTH (parms); ++i)
1320 tree parm = TREE_VEC_ELT (parms, i);
1321 tree constr = TEMPLATE_PARM_CONSTRAINTS (parm);
1322 result = conjoin_constraints (result, constr);
1327 // Returns and chains a new parameter for PARAMETER_LIST which will conform
1328 // to the prototype given by SRC_PARM. The new parameter will have its
1329 // identifier and location set according to IDENT and PARM_LOC respectively.
1331 process_introduction_parm (tree parameter_list, tree src_parm)
1333 // If we have a pack, we should have a single pack argument which is the
1334 // placeholder we want to look at.
1335 bool is_parameter_pack = ARGUMENT_PACK_P (src_parm);
1336 if (is_parameter_pack)
1337 src_parm = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (src_parm), 0);
1339 // At this point we should have a wildcard, but we want to
1340 // grab the associated decl from it. Also grab the stored
1341 // identifier and location that should be chained to it in
1343 gcc_assert (TREE_CODE (src_parm) == WILDCARD_DECL);
1345 tree ident = DECL_NAME (src_parm);
1346 location_t parm_loc = DECL_SOURCE_LOCATION (src_parm);
1348 // If we expect a pack and the deduced template is not a pack, or if the
1349 // template is using a pack and we didn't declare a pack, throw an error.
1350 if (is_parameter_pack != WILDCARD_PACK_P (src_parm))
1352 error_at (parm_loc, "cannot match pack for introduced parameter");
1353 tree err_parm = build_tree_list (error_mark_node, error_mark_node);
1354 return chainon (parameter_list, err_parm);
1357 src_parm = TREE_TYPE (src_parm);
1361 if (TREE_CODE (src_parm) == TYPE_DECL)
1363 is_non_type = false;
1364 parm = finish_template_type_parm (class_type_node, ident);
1366 else if (TREE_CODE (src_parm) == TEMPLATE_DECL)
1368 is_non_type = false;
1369 begin_template_parm_list ();
1370 current_template_parms = DECL_TEMPLATE_PARMS (src_parm);
1371 end_template_parm_list ();
1372 parm = finish_template_template_parm (class_type_node, ident);
1378 // Since we don't have a declarator, so we can copy the source
1379 // parameter and change the name and eventually the location.
1380 parm = copy_decl (src_parm);
1381 DECL_NAME (parm) = ident;
1384 // Wrap in a TREE_LIST for process_template_parm. Introductions do not
1385 // retain the defaults from the source template.
1386 parm = build_tree_list (NULL_TREE, parm);
1388 return process_template_parm (parameter_list, parm_loc, parm,
1389 is_non_type, is_parameter_pack);
1392 /* Associates a constraint check to the current template based
1393 on the introduction parameters. INTRO_LIST must be a TREE_VEC
1394 of WILDCARD_DECLs containing a chained PARM_DECL which
1395 contains the identifier as well as the source location.
1396 TMPL_DECL is the decl for the concept being used. If we
1397 take a concept, C, this will form a check in the form of
1398 C<INTRO_LIST> filling in any extra arguments needed by the
1401 Returns NULL_TREE if no concept could be matched and
1402 error_mark_node if an error occurred when matching. */
1404 finish_template_introduction (tree tmpl_decl, tree intro_list)
1406 /* Deduce the concept check. */
1407 tree expr = build_concept_check (tmpl_decl, NULL_TREE, intro_list);
1408 if (expr == error_mark_node)
1411 tree parms = deduce_concept_introduction (expr);
1415 /* Build template parameter scope for introduction. */
1416 tree parm_list = NULL_TREE;
1417 begin_template_parm_list ();
1418 int nargs = MIN (TREE_VEC_LENGTH (parms), TREE_VEC_LENGTH (intro_list));
1419 for (int n = 0; n < nargs; ++n)
1420 parm_list = process_introduction_parm (parm_list, TREE_VEC_ELT (parms, n));
1421 parm_list = end_template_parm_list (parm_list);
1422 for (int i = 0; i < TREE_VEC_LENGTH (parm_list); ++i)
1423 if (TREE_VALUE (TREE_VEC_ELT (parm_list, i)) == error_mark_node)
1425 end_template_decl ();
1426 return error_mark_node;
1429 /* Build a concept check for our constraint. */
1430 tree check_args = make_tree_vec (TREE_VEC_LENGTH (parms));
1432 for (; n < TREE_VEC_LENGTH (parm_list); ++n)
1434 tree parm = TREE_VEC_ELT (parm_list, n);
1435 TREE_VEC_ELT (check_args, n) = template_parm_to_arg (parm);
1437 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (check_args, n);
1439 /* If the template expects more parameters we should be able
1440 to use the defaults from our deduced concept. */
1441 for (; n < TREE_VEC_LENGTH (parms); ++n)
1442 TREE_VEC_ELT (check_args, n) = TREE_VEC_ELT (parms, n);
1444 /* Associate the constraint. */
1445 tree check = build_concept_check (tmpl_decl, NULL_TREE, check_args);
1446 tree constr = normalize_expression (check);
1447 TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = constr;
1453 /* Given the predicate constraint T from a constrained-type-specifier, extract
1454 its TMPL and ARGS. FIXME why do we need two different forms of
1455 constrained-type-specifier? */
1458 placeholder_extract_concept_and_args (tree t, tree &tmpl, tree &args)
1460 if (TREE_CODE (t) == TYPE_DECL)
1462 /* A constrained parameter. Build a constraint check
1463 based on the prototype parameter and then extract the
1464 arguments from that. */
1465 tree proto = CONSTRAINED_PARM_PROTOTYPE (t);
1466 tree check = finish_shorthand_constraint (proto, t);
1467 placeholder_extract_concept_and_args (check, tmpl, args);
1471 if (TREE_CODE (t) == CHECK_CONSTR)
1473 tree decl = CHECK_CONSTR_CONCEPT (t);
1474 tmpl = DECL_TI_TEMPLATE (decl);
1475 args = CHECK_CONSTR_ARGS (t);
1482 /* Returns true iff the placeholders C1 and C2 are equivalent. C1
1483 and C2 can be either CHECK_CONSTR or TEMPLATE_TYPE_PARM. */
1486 equivalent_placeholder_constraints (tree c1, tree c2)
1488 if (c1 && TREE_CODE (c1) == TEMPLATE_TYPE_PARM)
1489 /* A constrained auto. */
1490 c1 = PLACEHOLDER_TYPE_CONSTRAINTS (c1);
1491 if (c2 && TREE_CODE (c2) == TEMPLATE_TYPE_PARM)
1492 c2 = PLACEHOLDER_TYPE_CONSTRAINTS (c2);
1498 if (c1 == error_mark_node || c2 == error_mark_node)
1499 /* We get here during satisfaction; when a deduction constraint
1500 fails, substitution can produce an error_mark_node for the
1501 placeholder constraints. */
1504 tree t1, t2, a1, a2;
1505 placeholder_extract_concept_and_args (c1, t1, a1);
1506 placeholder_extract_concept_and_args (c2, t2, a2);
1511 int len1 = TREE_VEC_LENGTH (a1);
1512 int len2 = TREE_VEC_LENGTH (a2);
1516 /* Skip the first argument so we don't infinitely recurse.
1517 Also, they may differ in template parameter index. */
1518 for (int i = 1; i < len1; ++i)
1520 tree t1 = TREE_VEC_ELT (a1, i);
1521 tree t2 = TREE_VEC_ELT (a2, i);
1522 if (!template_args_equal (t1, t2))
1528 /* Return a hash value for the placeholder PRED_CONSTR C. */
1531 hash_placeholder_constraint (tree c)
1534 placeholder_extract_concept_and_args (c, t, a);
1536 /* Like hash_tmpl_and_args, but skip the first argument. */
1537 hashval_t val = iterative_hash_object (DECL_UID (t), 0);
1539 for (int i = TREE_VEC_LENGTH (a)-1; i > 0; --i)
1540 val = iterative_hash_template_arg (TREE_VEC_ELT (a, i), val);
1545 /*---------------------------------------------------------------------------
1546 Constraint substitution
1547 ---------------------------------------------------------------------------*/
1549 /* The following functions implement substitution rules for constraints.
1550 Substitution without checking constraints happens only in the
1551 instantiation of class templates. For example:
1553 template<C1 T> struct S {
1554 void f(T) requires C2<T>;
1555 void g(T) requires T::value;
1558 S<int> s; // error instantiating S<int>::g(T)
1560 When we instantiate S, we substitute into its member declarations,
1561 including their constraints. However, those constraints are not
1562 checked. Substituting int into C2<T> yields C2<int>, and substituting
1563 into T::value yields a substitution failure, making the program
1566 Note that we only ever substitute into the associated constraints
1567 of a declaration. That is, substitution is defined only for predicate
1568 constraints and conjunctions. */
1570 /* Substitute into the predicate constraints. Returns error_mark_node
1571 if the substitution into the expression fails. */
1573 tsubst_predicate_constraint (tree t, tree args,
1574 tsubst_flags_t complain, tree in_decl)
1576 tree expr = PRED_CONSTR_EXPR (t);
1577 ++processing_template_decl;
1578 tree result = tsubst_expr (expr, args, complain, in_decl, false);
1579 --processing_template_decl;
1580 return build_nt (PRED_CONSTR, result);
1583 /* Substitute into a check constraint. */
1586 tsubst_check_constraint (tree t, tree args,
1587 tsubst_flags_t complain, tree in_decl)
1589 tree decl = CHECK_CONSTR_CONCEPT (t);
1590 tree tmpl = DECL_TI_TEMPLATE (decl);
1591 tree targs = CHECK_CONSTR_ARGS (t);
1593 /* Substitute through by building an template-id expression
1594 and then substituting into that. */
1595 tree expr = build_nt(TEMPLATE_ID_EXPR, tmpl, targs);
1596 ++processing_template_decl;
1597 tree result = tsubst_expr (expr, args, complain, in_decl, false);
1598 --processing_template_decl;
1600 if (result == error_mark_node)
1601 return error_mark_node;
1603 /* Extract the results and rebuild the check constraint. */
1604 decl = DECL_TEMPLATE_RESULT (TREE_OPERAND (result, 0));
1605 args = TREE_OPERAND (result, 1);
1607 return build_nt (CHECK_CONSTR, decl, args);
1610 /* Substitute into the conjunction of constraints. Returns
1611 error_mark_node if substitution into either operand fails. */
1614 tsubst_logical_operator (tree t, tree args,
1615 tsubst_flags_t complain, tree in_decl)
1617 tree t0 = TREE_OPERAND (t, 0);
1618 tree r0 = tsubst_constraint (t0, args, complain, in_decl);
1619 if (r0 == error_mark_node)
1620 return error_mark_node;
1621 tree t1 = TREE_OPERAND (t, 1);
1622 tree r1 = tsubst_constraint (t1, args, complain, in_decl);
1623 if (r1 == error_mark_node)
1624 return error_mark_node;
1625 return build_nt (TREE_CODE (t), r0, r1);
1630 /* Substitute ARGS into the expression constraint T. */
1633 tsubst_expr_constr (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1635 cp_unevaluated guard;
1636 tree expr = EXPR_CONSTR_EXPR (t);
1637 tree ret = tsubst_expr (expr, args, complain, in_decl, false);
1638 if (ret == error_mark_node)
1639 return error_mark_node;
1640 return build_nt (EXPR_CONSTR, ret);
1643 /* Substitute ARGS into the type constraint T. */
1646 tsubst_type_constr (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1648 tree type = TYPE_CONSTR_TYPE (t);
1649 tree ret = tsubst (type, args, complain, in_decl);
1650 if (ret == error_mark_node)
1651 return error_mark_node;
1652 return build_nt (TYPE_CONSTR, ret);
1655 /* Substitute ARGS into the implicit conversion constraint T. */
1658 tsubst_implicit_conversion_constr (tree t, tree args, tsubst_flags_t complain,
1661 cp_unevaluated guard;
1662 tree expr = ICONV_CONSTR_EXPR (t);
1663 tree type = ICONV_CONSTR_TYPE (t);
1664 tree new_expr = tsubst_expr (expr, args, complain, in_decl, false);
1665 if (new_expr == error_mark_node)
1666 return error_mark_node;
1667 tree new_type = tsubst (type, args, complain, in_decl);
1668 if (new_type == error_mark_node)
1669 return error_mark_node;
1670 return build_nt (ICONV_CONSTR, new_expr, new_type);
1673 /* Substitute ARGS into the argument deduction constraint T. */
1676 tsubst_argument_deduction_constr (tree t, tree args, tsubst_flags_t complain,
1679 cp_unevaluated guard;
1680 tree expr = DEDUCT_CONSTR_EXPR (t);
1681 tree pattern = DEDUCT_CONSTR_PATTERN (t);
1682 tree autos = DEDUCT_CONSTR_PLACEHOLDER(t);
1683 tree new_expr = tsubst_expr (expr, args, complain, in_decl, false);
1684 if (new_expr == error_mark_node)
1685 return error_mark_node;
1686 /* It seems like substituting through the pattern will not affect the
1687 placeholders. We should (?) be able to reuse the existing list
1688 without any problems. If not, then we probably want to create a
1689 new list of placeholders and then instantiate the pattern using
1691 tree new_pattern = tsubst (pattern, args, complain, in_decl);
1692 if (new_pattern == error_mark_node)
1693 return error_mark_node;
1694 return build_nt (DEDUCT_CONSTR, new_expr, new_pattern, autos);
1697 /* Substitute ARGS into the exception constraint T. */
1700 tsubst_exception_constr (tree t, tree args, tsubst_flags_t complain,
1703 cp_unevaluated guard;
1704 tree expr = EXCEPT_CONSTR_EXPR (t);
1705 tree ret = tsubst_expr (expr, args, complain, in_decl, false);
1706 if (ret == error_mark_node)
1707 return error_mark_node;
1708 return build_nt (EXCEPT_CONSTR, ret);
1711 /* A subroutine of tsubst_constraint_variables. Register local
1712 specializations for each of parameter in PARMS and its
1713 corresponding substituted constraint variable in VARS.
1717 declare_constraint_vars (tree parms, tree vars)
1720 for (tree t = parms; t; t = DECL_CHAIN (t))
1722 if (DECL_PACK_P (t))
1724 tree pack = extract_fnparm_pack (t, &s);
1725 register_local_specialization (pack, t);
1729 register_local_specialization (s, t);
1736 /* A subroutine of tsubst_parameterized_constraint. Substitute ARGS
1737 into the parameter list T, producing a sequence of constraint
1738 variables, declared in the current scope.
1740 Note that the caller must establish a local specialization stack
1741 prior to calling this function since this substitution will
1742 declare the substituted parameters. */
1745 tsubst_constraint_variables (tree t, tree args,
1746 tsubst_flags_t complain, tree in_decl)
1748 /* Clear cp_unevaluated_operand across tsubst so that we get a proper chain
1750 int saved_unevaluated_operand = cp_unevaluated_operand;
1751 cp_unevaluated_operand = 0;
1752 tree vars = tsubst (t, args, complain, in_decl);
1753 cp_unevaluated_operand = saved_unevaluated_operand;
1754 if (vars == error_mark_node)
1755 return error_mark_node;
1756 return declare_constraint_vars (t, vars);
1759 /* Substitute ARGS into the parameterized constraint T. */
1762 tsubst_parameterized_constraint (tree t, tree args,
1763 tsubst_flags_t complain, tree in_decl)
1765 local_specialization_stack stack;
1766 tree vars = tsubst_constraint_variables (PARM_CONSTR_PARMS (t),
1767 args, complain, in_decl);
1768 if (vars == error_mark_node)
1769 return error_mark_node;
1770 tree expr = tsubst_constraint (PARM_CONSTR_OPERAND (t), args,
1772 if (expr == error_mark_node)
1773 return error_mark_node;
1774 return build_nt (PARM_CONSTR, vars, expr);
1777 /* Substitute ARGS into the simple requirement T. Note that
1778 substitution may result in an ill-formed expression without
1779 causing the program to be ill-formed. In such cases, the
1780 requirement wraps an error_mark_node. */
1783 tsubst_simple_requirement (tree t, tree args,
1784 tsubst_flags_t complain, tree in_decl)
1786 ++processing_template_decl;
1787 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1788 --processing_template_decl;
1789 return finish_simple_requirement (expr);
1792 /* Substitute ARGS into the type requirement T. Note that
1793 substitution may result in an ill-formed type without
1794 causing the program to be ill-formed. In such cases, the
1795 requirement wraps an error_mark_node. */
1798 tsubst_type_requirement (tree t, tree args,
1799 tsubst_flags_t complain, tree in_decl)
1801 ++processing_template_decl;
1802 tree type = tsubst (TREE_OPERAND (t, 0), args, complain, in_decl);
1803 --processing_template_decl;
1804 return finish_type_requirement (type);
1807 /* Substitute args into the compound requirement T. If substituting
1808 into either the expression or the type fails, the corresponding
1809 operands in the resulting node will be error_mark_node. This
1810 preserves a requirement for the purpose of partial ordering, but
1811 it will never be satisfied. */
1814 tsubst_compound_requirement (tree t, tree args,
1815 tsubst_flags_t complain, tree in_decl)
1817 ++processing_template_decl;
1818 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1819 tree type = tsubst (TREE_OPERAND (t, 1), args, complain, in_decl);
1820 --processing_template_decl;
1821 bool noexcept_p = COMPOUND_REQ_NOEXCEPT_P (t);
1822 return finish_compound_requirement (expr, type, noexcept_p);
1825 /* Substitute ARGS into the nested requirement T. */
1828 tsubst_nested_requirement (tree t, tree args,
1829 tsubst_flags_t complain, tree in_decl)
1831 ++processing_template_decl;
1832 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1833 --processing_template_decl;
1834 return finish_nested_requirement (expr);
1837 /* Substitute ARGS into the requirement T. */
1840 tsubst_requirement (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1842 switch (TREE_CODE (t))
1845 return tsubst_simple_requirement (t, args, complain, in_decl);
1847 return tsubst_type_requirement (t, args, complain, in_decl);
1849 return tsubst_compound_requirement (t, args, complain, in_decl);
1851 return tsubst_nested_requirement (t, args, complain, in_decl);
1855 return error_mark_node;
1858 /* Substitute ARGS into the list of requirements T. Note that
1859 substitution failures here result in ill-formed programs. */
1862 tsubst_requirement_body (tree t, tree args,
1863 tsubst_flags_t complain, tree in_decl)
1868 tree e = tsubst_requirement (TREE_VALUE (t), args, complain, in_decl);
1869 if (e == error_mark_node)
1870 return error_mark_node;
1871 r = tree_cons (NULL_TREE, e, r);
1874 /* Ensure that the order of constraints is the same as the original. */
1875 return nreverse (r);
1880 /* Substitute ARGS into the requires expression T. Note that this
1881 results in the re-declaration of local parameters when
1882 substituting through the parameter list. If either substitution
1883 fails, the program is ill-formed. */
1886 tsubst_requires_expr (tree t, tree args,
1887 tsubst_flags_t complain, tree in_decl)
1889 local_specialization_stack stack;
1891 tree parms = TREE_OPERAND (t, 0);
1894 parms = tsubst_constraint_variables (parms, args, complain, in_decl);
1895 if (parms == error_mark_node)
1896 return error_mark_node;
1899 tree reqs = TREE_OPERAND (t, 1);
1900 reqs = tsubst_requirement_body (reqs, args, complain, in_decl);
1901 if (reqs == error_mark_node)
1902 return error_mark_node;
1904 return finish_requires_expr (parms, reqs);
1907 /* Substitute ARGS into the constraint information CI, producing a new
1908 constraint record. */
1911 tsubst_constraint_info (tree t, tree args,
1912 tsubst_flags_t complain, tree in_decl)
1914 if (!t || t == error_mark_node || !check_constraint_info (t))
1917 tree tmpl_constr = NULL_TREE;
1918 if (tree r = CI_TEMPLATE_REQS (t))
1919 tmpl_constr = tsubst_constraint (r, args, complain, in_decl);
1921 tree decl_constr = NULL_TREE;
1922 if (tree r = CI_DECLARATOR_REQS (t))
1923 decl_constr = tsubst_constraint (r, args, complain, in_decl);
1925 return build_constraints (tmpl_constr, decl_constr);
1928 /* Substitute ARGS into the constraint T. */
1931 tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1935 switch (TREE_CODE (t))
1938 return tsubst_predicate_constraint (t, args, complain, in_decl);
1940 return tsubst_check_constraint (t, args, complain, in_decl);
1943 return tsubst_logical_operator (t, args, complain, in_decl);
1945 return tsubst_parameterized_constraint (t, args, complain, in_decl);
1947 return tsubst_expr_constr (t, args, complain, in_decl);
1949 return tsubst_type_constr (t, args, complain, in_decl);
1951 return tsubst_implicit_conversion_constr (t, args, complain, in_decl);
1953 return tsubst_argument_deduction_constr (t, args, complain, in_decl);
1955 return tsubst_exception_constr (t, args, complain, in_decl);
1959 return error_mark_node;
1962 /*---------------------------------------------------------------------------
1963 Constraint satisfaction
1964 ---------------------------------------------------------------------------*/
1966 /* The following functions determine if a constraint, when
1967 substituting template arguments, is satisfied. For convenience,
1968 satisfaction reduces a constraint to either true or false (and
1973 tree satisfy_constraint_1 (tree, tree, tsubst_flags_t, tree);
1975 /* Check the constraint pack expansion. */
1978 satisfy_pack_expansion (tree t, tree args,
1979 tsubst_flags_t complain, tree in_decl)
1981 /* Get the vector of satisfaction results.
1982 gen_elem_of_pack_expansion_instantiation will check that each element of
1983 the expansion is satisfied. */
1984 tree exprs = tsubst_pack_expansion (t, args, complain, in_decl);
1986 if (exprs == error_mark_node)
1987 return boolean_false_node;
1989 /* TODO: It might be better to normalize each expanded term
1990 and evaluate them separately. That would provide better
1991 opportunities for diagnostics. */
1992 for (int i = 0; i < TREE_VEC_LENGTH (exprs); ++i)
1993 if (TREE_VEC_ELT (exprs, i) != boolean_true_node)
1994 return boolean_false_node;
1995 return boolean_true_node;
1998 /* A predicate constraint is satisfied if its expression evaluates
1999 to true. If substitution into that node fails, the constraint
2000 is not satisfied ([temp.constr.pred]).
2002 Note that a predicate constraint is a constraint expression
2003 of type bool. If neither of those are true, the program is
2004 ill-formed; they are not SFINAE'able errors. */
2007 satisfy_predicate_constraint (tree t, tree args,
2008 tsubst_flags_t complain, tree in_decl)
2010 tree expr = TREE_OPERAND (t, 0);
2012 /* We should never have a naked pack expansion in a predicate constraint. */
2013 gcc_assert (TREE_CODE (expr) != EXPR_PACK_EXPANSION);
2015 /* If substitution into the expression fails, the constraint
2016 is not satisfied. */
2017 expr = tsubst_expr (expr, args, complain, in_decl, false);
2018 if (expr == error_mark_node)
2019 return boolean_false_node;
2021 /* A predicate constraint shall have type bool. In some
2022 cases, substitution gives us const-qualified bool, which
2023 is also acceptable. */
2024 tree type = cv_unqualified (TREE_TYPE (expr));
2025 if (!same_type_p (type, boolean_type_node))
2027 error_at (EXPR_LOC_OR_LOC (expr, input_location),
2028 "constraint %qE does not have type %qT",
2029 expr, boolean_type_node);
2030 return boolean_false_node;
2033 return cxx_constant_value (expr);
2036 /* A concept check constraint like C<CARGS> is satisfied if substituting ARGS
2037 into CARGS succeeds and C is satisfied for the resulting arguments. */
2040 satisfy_check_constraint (tree t, tree args,
2041 tsubst_flags_t complain, tree in_decl)
2043 tree decl = CHECK_CONSTR_CONCEPT (t);
2044 tree tmpl = DECL_TI_TEMPLATE (decl);
2045 tree cargs = CHECK_CONSTR_ARGS (t);
2047 /* Instantiate the concept check arguments. */
2048 tree targs = tsubst (cargs, args, tf_none, NULL_TREE);
2049 if (targs == error_mark_node)
2050 return boolean_false_node;
2052 /* Search for a previous value. */
2053 if (tree prev = lookup_concept_satisfaction (tmpl, targs))
2056 /* Expand the concept; failure here implies non-satisfaction. */
2057 tree def = expand_concept (decl, targs);
2058 if (def == error_mark_node)
2059 return memoize_concept_satisfaction (tmpl, args, boolean_false_node);
2061 /* Recursively satisfy the constraint. */
2062 tree result = satisfy_constraint_1 (def, targs, complain, in_decl);
2063 return memoize_concept_satisfaction (tmpl, targs, result);
2066 /* Check an expression constraint. The constraint is satisfied if
2067 substitution succeeds ([temp.constr.expr]).
2069 Note that the expression is unevaluated. */
2072 satisfy_expression_constraint (tree t, tree args,
2073 tsubst_flags_t complain, tree in_decl)
2075 cp_unevaluated guard;
2076 deferring_access_check_sentinel deferring;
2078 tree expr = EXPR_CONSTR_EXPR (t);
2079 tree check = tsubst_expr (expr, args, complain, in_decl, false);
2080 if (check == error_mark_node)
2081 return boolean_false_node;
2082 if (!perform_deferred_access_checks (tf_none))
2083 return boolean_false_node;
2084 return boolean_true_node;
2087 /* Check a type constraint. The constraint is satisfied if
2088 substitution succeeds. */
2091 satisfy_type_constraint (tree t, tree args,
2092 tsubst_flags_t complain, tree in_decl)
2094 deferring_access_check_sentinel deferring;
2095 tree type = TYPE_CONSTR_TYPE (t);
2096 gcc_assert (TYPE_P (type) || type == error_mark_node);
2097 tree check = tsubst (type, args, complain, in_decl);
2098 if (error_operand_p (check))
2099 return boolean_false_node;
2100 if (!perform_deferred_access_checks (complain))
2101 return boolean_false_node;
2102 return boolean_true_node;
2105 /* Check an implicit conversion constraint. */
2108 satisfy_implicit_conversion_constraint (tree t, tree args,
2109 tsubst_flags_t complain, tree in_decl)
2111 /* Don't tsubst as if we're processing a template. If we try
2112 to we can end up generating template-like expressions
2113 (e.g., modop-exprs) that aren't properly typed. */
2115 tsubst_expr (ICONV_CONSTR_EXPR (t), args, complain, in_decl, false);
2116 if (expr == error_mark_node)
2117 return boolean_false_node;
2119 /* Get the transformed target type. */
2120 tree type = tsubst (ICONV_CONSTR_TYPE (t), args, complain, in_decl);
2121 if (type == error_mark_node)
2122 return boolean_false_node;
2124 /* Attempt the conversion as a direct initialization
2125 of the form TYPE <unspecified> = EXPR. */
2127 perform_direct_initialization_if_possible (type, expr, false, complain);
2128 if (conv == NULL_TREE || conv == error_mark_node)
2129 return boolean_false_node;
2131 return boolean_true_node;
2134 /* Check an argument deduction constraint. */
2137 satisfy_argument_deduction_constraint (tree t, tree args,
2138 tsubst_flags_t complain, tree in_decl)
2140 /* Substitute through the expression. */
2141 tree expr = DEDUCT_CONSTR_EXPR (t);
2142 tree init = tsubst_expr (expr, args, complain, in_decl, false);
2143 if (expr == error_mark_node)
2144 return boolean_false_node;
2146 /* Perform auto or decltype(auto) deduction to get the result. */
2147 tree pattern = DEDUCT_CONSTR_PATTERN (t);
2148 tree placeholder = DEDUCT_CONSTR_PLACEHOLDER (t);
2149 tree constr = PLACEHOLDER_TYPE_CONSTRAINTS (placeholder);
2150 tree type_canonical = TYPE_CANONICAL (placeholder);
2151 PLACEHOLDER_TYPE_CONSTRAINTS (placeholder)
2152 = tsubst_constraint (constr, args, complain|tf_partial, in_decl);
2153 TYPE_CANONICAL (placeholder) = NULL_TREE;
2154 tree type = do_auto_deduction (pattern, init, placeholder,
2155 complain, adc_requirement);
2156 PLACEHOLDER_TYPE_CONSTRAINTS (placeholder) = constr;
2157 TYPE_CANONICAL (placeholder) = type_canonical;
2158 if (type == error_mark_node)
2159 return boolean_false_node;
2161 return boolean_true_node;
2164 /* Check an exception constraint. An exception constraint for an
2165 expression e is satisfied when noexcept(e) is true. */
2168 satisfy_exception_constraint (tree t, tree args,
2169 tsubst_flags_t complain, tree in_decl)
2171 tree expr = EXCEPT_CONSTR_EXPR (t);
2172 tree check = tsubst_expr (expr, args, complain, in_decl, false);
2173 if (check == error_mark_node)
2174 return boolean_false_node;
2176 if (expr_noexcept_p (check, complain))
2177 return boolean_true_node;
2179 return boolean_false_node;
2182 /* Check a parameterized constraint. */
2185 satisfy_parameterized_constraint (tree t, tree args,
2186 tsubst_flags_t complain, tree in_decl)
2188 local_specialization_stack stack;
2189 tree parms = PARM_CONSTR_PARMS (t);
2190 tree vars = tsubst_constraint_variables (parms, args, complain, in_decl);
2191 if (vars == error_mark_node)
2192 return boolean_false_node;
2193 tree constr = PARM_CONSTR_OPERAND (t);
2194 return satisfy_constraint_1 (constr, args, complain, in_decl);
2197 /* Check that the conjunction of constraints is satisfied. Note
2198 that if left operand is not satisfied, the right operand
2201 FIXME: Check that this wouldn't result in a user-defined
2202 operator. Note that this error is partially diagnosed in
2203 satisfy_predicate_constraint. It would be nice to diagnose
2204 the overload, but I don't think it's strictly necessary. */
2207 satisfy_conjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2209 tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl);
2210 if (t0 == boolean_false_node)
2211 return boolean_false_node;
2212 return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
2215 /* Check that the disjunction of constraints is satisfied. Note
2216 that if the left operand is satisfied, the right operand is not
2220 satisfy_disjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2222 tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl);
2223 if (t0 == boolean_true_node)
2224 return boolean_true_node;
2225 return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
2228 /* Dispatch to an appropriate satisfaction routine depending on the
2232 satisfy_constraint_1 (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2234 gcc_assert (!processing_template_decl);
2237 return boolean_false_node;
2239 if (t == error_mark_node)
2240 return boolean_false_node;
2242 switch (TREE_CODE (t))
2245 return satisfy_predicate_constraint (t, args, complain, in_decl);
2248 return satisfy_check_constraint (t, args, complain, in_decl);
2251 return satisfy_expression_constraint (t, args, complain, in_decl);
2254 return satisfy_type_constraint (t, args, complain, in_decl);
2257 return satisfy_implicit_conversion_constraint (t, args, complain, in_decl);
2260 return satisfy_argument_deduction_constraint (t, args, complain, in_decl);
2263 return satisfy_exception_constraint (t, args, complain, in_decl);
2266 return satisfy_parameterized_constraint (t, args, complain, in_decl);
2269 return satisfy_conjunction (t, args, complain, in_decl);
2272 return satisfy_disjunction (t, args, complain, in_decl);
2274 case EXPR_PACK_EXPANSION:
2275 return satisfy_pack_expansion (t, args, complain, in_decl);
2280 return boolean_false_node;
2283 /* Check that the constraint is satisfied, according to the rules
2284 for that constraint. Note that each satisfy_* function returns
2285 true or false, depending on whether it is satisfied or not. */
2288 satisfy_constraint (tree t, tree args)
2290 auto_timevar time (TV_CONSTRAINT_SAT);
2292 /* Turn off template processing. Constraint satisfaction only applies
2293 to non-dependent terms, so we want to ensure full checking here. */
2294 processing_template_decl_sentinel proc (true);
2296 /* Avoid early exit in tsubst and tsubst_copy from null args; since earlier
2297 substitution was done with processing_template_decl forced on, there will
2298 be expressions that still need semantic processing, possibly buried in
2299 decltype or a template argument. */
2300 if (args == NULL_TREE)
2301 args = make_tree_vec (1);
2303 return satisfy_constraint_1 (t, args, tf_none, NULL_TREE);
2306 /* Check the associated constraints in CI against the given
2307 ARGS, returning true when the constraints are satisfied
2308 and false otherwise. */
2311 satisfy_associated_constraints (tree ci, tree args)
2313 /* If there are no constraints then this is trivially satisfied. */
2315 return boolean_true_node;
2317 /* If any arguments depend on template parameters, we can't
2318 check constraints. */
2319 if (args && uses_template_parms (args))
2320 return boolean_true_node;
2322 /* Check if we've seen a previous result. */
2323 if (tree prev = lookup_constraint_satisfaction (ci, args))
2326 /* Actually test for satisfaction. */
2327 tree result = satisfy_constraint (CI_ASSOCIATED_CONSTRAINTS (ci), args);
2328 return memoize_constraint_satisfaction (ci, args, result);
2333 /* Evaluate the given constraint, returning boolean_true_node
2334 if the constraint is satisfied and boolean_false_node
2338 evaluate_constraints (tree constr, tree args)
2340 gcc_assert (constraint_p (constr));
2341 return satisfy_constraint (constr, args);
2344 /* Evaluate the function concept FN by substituting its own args
2345 into its definition and evaluating that as the result. Returns
2346 boolean_true_node if the constraints are satisfied and
2347 boolean_false_node otherwise. */
2350 evaluate_function_concept (tree fn, tree args)
2352 tree constr = build_nt (CHECK_CONSTR, fn, args);
2353 return satisfy_constraint (constr, args);
2356 /* Evaluate the variable concept VAR by substituting its own args into
2357 its initializer and checking the resulting constraint. Returns
2358 boolean_true_node if the constraints are satisfied and
2359 boolean_false_node otherwise. */
2362 evaluate_variable_concept (tree var, tree args)
2364 tree constr = build_nt (CHECK_CONSTR, var, args);
2365 return satisfy_constraint (constr, args);
2368 /* Evaluate the given expression as if it were a predicate
2369 constraint. Returns boolean_true_node if the constraint
2370 is satisfied and boolean_false_node otherwise. */
2373 evaluate_constraint_expression (tree expr, tree args)
2375 tree constr = normalize_expression (expr);
2376 return satisfy_constraint (constr, args);
2379 /* Returns true if the DECL's constraints are satisfied.
2380 This is used in cases where a declaration is formed but
2381 before it is used (e.g., overload resolution). */
2384 constraints_satisfied_p (tree decl)
2386 /* Get the constraints to check for satisfaction. This depends
2387 on whether we're looking at a template specialization or not. */
2389 tree args = NULL_TREE;
2390 if (tree ti = DECL_TEMPLATE_INFO (decl))
2392 ci = get_constraints (TI_TEMPLATE (ti));
2393 args = INNERMOST_TEMPLATE_ARGS (TI_ARGS (ti));
2397 ci = get_constraints (decl);
2400 tree eval = satisfy_associated_constraints (ci, args);
2401 return eval == boolean_true_node;
2404 /* Returns true if the constraints are satisfied by ARGS.
2405 Here, T can be either a constraint or a constrained
2409 constraints_satisfied_p (tree t, tree args)
2412 if (constraint_p (t))
2413 eval = evaluate_constraints (t, args);
2415 eval = satisfy_associated_constraints (get_constraints (t), args);
2416 return eval == boolean_true_node;
2422 /* Normalize EXPR and determine if the resulting constraint is
2423 satisfied by ARGS. Returns true if and only if the constraint
2424 is satisfied. This is used extensively by diagnostics to
2425 determine causes for failure. */
2428 constraint_expression_satisfied_p (tree expr, tree args)
2430 return evaluate_constraint_expression (expr, args) == boolean_true_node;
2435 /*---------------------------------------------------------------------------
2436 Semantic analysis of requires-expressions
2437 ---------------------------------------------------------------------------*/
2439 /* Finish a requires expression for the given PARMS (possibly
2440 null) and the non-empty sequence of requirements. */
2442 finish_requires_expr (tree parms, tree reqs)
2444 /* Modify the declared parameters by removing their context
2445 so they don't refer to the enclosing scope and explicitly
2446 indicating that they are constraint variables. */
2447 for (tree parm = parms; parm; parm = DECL_CHAIN (parm))
2449 DECL_CONTEXT (parm) = NULL_TREE;
2450 CONSTRAINT_VAR_P (parm) = true;
2453 /* Build the node. */
2454 tree r = build_min (REQUIRES_EXPR, boolean_type_node, parms, reqs);
2455 TREE_SIDE_EFFECTS (r) = false;
2456 TREE_CONSTANT (r) = true;
2460 /* Construct a requirement for the validity of EXPR. */
2462 finish_simple_requirement (tree expr)
2464 return build_nt (SIMPLE_REQ, expr);
2467 /* Construct a requirement for the validity of TYPE. */
2469 finish_type_requirement (tree type)
2471 return build_nt (TYPE_REQ, type);
2474 /* Construct a requirement for the validity of EXPR, along with
2475 its properties. if TYPE is non-null, then it specifies either
2476 an implicit conversion or argument deduction constraint,
2477 depending on whether any placeholders occur in the type name.
2478 NOEXCEPT_P is true iff the noexcept keyword was specified. */
2480 finish_compound_requirement (tree expr, tree type, bool noexcept_p)
2482 tree req = build_nt (COMPOUND_REQ, expr, type);
2483 COMPOUND_REQ_NOEXCEPT_P (req) = noexcept_p;
2487 /* Finish a nested requirement. */
2489 finish_nested_requirement (tree expr)
2491 return build_nt (NESTED_REQ, expr);
2494 // Check that FN satisfies the structural requirements of a
2495 // function concept definition.
2497 check_function_concept (tree fn)
2499 // Check that the function is comprised of only a single
2500 // return statement.
2501 tree body = DECL_SAVED_TREE (fn);
2502 if (TREE_CODE (body) == BIND_EXPR)
2503 body = BIND_EXPR_BODY (body);
2505 // Sometimes a function call results in the creation of clean up
2506 // points. Allow these to be preserved in the body of the
2507 // constraint, as we might actually need them for some constexpr
2509 if (TREE_CODE (body) == CLEANUP_POINT_EXPR)
2510 body = TREE_OPERAND (body, 0);
2512 /* Check that the definition is written correctly. */
2513 if (TREE_CODE (body) != RETURN_EXPR)
2515 location_t loc = DECL_SOURCE_LOCATION (fn);
2516 if (TREE_CODE (body) == STATEMENT_LIST && !STATEMENT_LIST_HEAD (body))
2517 error_at (loc, "definition of concept %qD is empty", fn);
2519 error_at (loc, "definition of concept %qD has multiple statements", fn);
2526 // Check that a constrained friend declaration function declaration,
2527 // FN, is admissible. This is the case only when the declaration depends
2528 // on template parameters and does not declare a specialization.
2530 check_constrained_friend (tree fn, tree reqs)
2532 if (fn == error_mark_node)
2534 gcc_assert (TREE_CODE (fn) == FUNCTION_DECL);
2536 // If there are not constraints, this cannot be an error.
2540 // Constrained friend functions that don't depend on template
2541 // arguments are effectively meaningless.
2542 if (!uses_template_parms (TREE_TYPE (fn)))
2544 error_at (location_of (fn),
2545 "constrained friend does not depend on template parameters");
2550 /*---------------------------------------------------------------------------
2551 Equivalence of constraints
2552 ---------------------------------------------------------------------------*/
2554 /* Returns true when A and B are equivalent constraints. */
2556 equivalent_constraints (tree a, tree b)
2558 gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
2559 gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
2560 return cp_tree_equal (a, b);
2563 /* Returns true if the template declarations A and B have equivalent
2564 constraints. This is the case when A's constraints subsume B's and
2565 when B's also constrain A's. */
2567 equivalently_constrained (tree d1, tree d2)
2569 gcc_assert (TREE_CODE (d1) == TREE_CODE (d2));
2570 return equivalent_constraints (get_constraints (d1), get_constraints (d2));
2573 /*---------------------------------------------------------------------------
2574 Partial ordering of constraints
2575 ---------------------------------------------------------------------------*/
2577 /* Returns true when the the constraints in A subsume those in B. */
2580 subsumes_constraints (tree a, tree b)
2582 gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
2583 gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
2584 return subsumes (a, b);
2587 /* Returns true when the the constraints in A subsume those in B, but
2588 the constraints in B do not subsume the constraints in A. */
2591 strictly_subsumes (tree a, tree b)
2593 return subsumes (a, b) && !subsumes (b, a);
2596 /* Determines which of the declarations, A or B, is more constrained.
2597 That is, which declaration's constraints subsume but are not subsumed
2600 Returns 1 if A is more constrained than B, -1 if B is more constrained
2601 than A, and 0 otherwise. */
2604 more_constrained (tree d1, tree d2)
2606 tree c1 = get_constraints (d1);
2607 tree c2 = get_constraints (d2);
2609 if (subsumes_constraints (c1, c2))
2611 if (subsumes_constraints (c2, c1))
2616 /* Returns true if D1 is at least as constrained as D2. That is, the
2617 associated constraints of D1 subsume those of D2, or both declarations
2618 are unconstrained. */
2621 at_least_as_constrained (tree d1, tree d2)
2623 tree c1 = get_constraints (d1);
2624 tree c2 = get_constraints (d2);
2625 return subsumes_constraints (c1, c2);
2629 /*---------------------------------------------------------------------------
2630 Constraint diagnostics
2632 FIXME: Normalize expressions into constraints before evaluating them.
2633 This should be the general pattern for all such diagnostics.
2634 ---------------------------------------------------------------------------*/
2636 /* The number of detailed constraint failures. */
2638 int constraint_errors = 0;
2640 /* Do not generate errors after diagnosing this number of constraint
2643 FIXME: This is a really arbitrary number. Provide better control of
2644 constraint diagnostics with a command line option. */
2646 int constraint_thresh = 20;
2649 /* Returns true if we should elide the diagnostic for a constraint failure.
2650 This is the case when the number of errors has exceeded the pre-configured
2654 elide_constraint_failure_p ()
2656 bool ret = constraint_thresh <= constraint_errors;
2657 ++constraint_errors;
2661 /* Returns the number of undiagnosed errors. */
2664 undiagnosed_constraint_failures ()
2666 return constraint_errors - constraint_thresh;
2669 /* The diagnosis of constraints performs a combination of normalization
2670 and satisfaction testing. We recursively walk through the conjunction or
2671 disjunction of associated constraints, testing each sub-constraint in
2676 void diagnose_constraint (location_t, tree, tree, tree);
2678 /* Emit a specific diagnostics for a failed trait. */
2681 diagnose_trait_expression (location_t loc, tree, tree cur, tree args)
2683 if (constraint_expression_satisfied_p (cur, args))
2685 if (elide_constraint_failure_p())
2688 tree expr = PRED_CONSTR_EXPR (cur);
2689 ++processing_template_decl;
2690 expr = tsubst_expr (expr, args, tf_none, NULL_TREE, false);
2691 --processing_template_decl;
2693 tree t1 = TRAIT_EXPR_TYPE1 (expr);
2694 tree t2 = TRAIT_EXPR_TYPE2 (expr);
2695 switch (TRAIT_EXPR_KIND (expr))
2697 case CPTK_HAS_NOTHROW_ASSIGN:
2698 inform (loc, " %qT is not nothrow copy assignable", t1);
2700 case CPTK_HAS_NOTHROW_CONSTRUCTOR:
2701 inform (loc, " %qT is not nothrow default constructible", t1);
2703 case CPTK_HAS_NOTHROW_COPY:
2704 inform (loc, " %qT is not nothrow copy constructible", t1);
2706 case CPTK_HAS_TRIVIAL_ASSIGN:
2707 inform (loc, " %qT is not trivially copy assignable", t1);
2709 case CPTK_HAS_TRIVIAL_CONSTRUCTOR:
2710 inform (loc, " %qT is not trivially default constructible", t1);
2712 case CPTK_HAS_TRIVIAL_COPY:
2713 inform (loc, " %qT is not trivially copy constructible", t1);
2715 case CPTK_HAS_TRIVIAL_DESTRUCTOR:
2716 inform (loc, " %qT is not trivially destructible", t1);
2718 case CPTK_HAS_VIRTUAL_DESTRUCTOR:
2719 inform (loc, " %qT does not have a virtual destructor", t1);
2721 case CPTK_IS_ABSTRACT:
2722 inform (loc, " %qT is not an abstract class", t1);
2724 case CPTK_IS_BASE_OF:
2725 inform (loc, " %qT is not a base of %qT", t1, t2);
2728 inform (loc, " %qT is not a class", t1);
2731 inform (loc, " %qT is not an empty class", t1);
2734 inform (loc, " %qT is not an enum", t1);
2737 inform (loc, " %qT is not a final class", t1);
2739 case CPTK_IS_LITERAL_TYPE:
2740 inform (loc, " %qT is not a literal type", t1);
2743 inform (loc, " %qT is not a POD type", t1);
2745 case CPTK_IS_POLYMORPHIC:
2746 inform (loc, " %qT is not a polymorphic type", t1);
2748 case CPTK_IS_SAME_AS:
2749 inform (loc, " %qT is not the same as %qT", t1, t2);
2751 case CPTK_IS_STD_LAYOUT:
2752 inform (loc, " %qT is not an standard layout type", t1);
2754 case CPTK_IS_TRIVIAL:
2755 inform (loc, " %qT is not a trivial type", t1);
2758 inform (loc, " %qT is not a union", t1);
2765 /* Diagnose the expression of a predicate constraint. */
2768 diagnose_other_expression (location_t loc, tree, tree cur, tree args)
2770 if (constraint_expression_satisfied_p (cur, args))
2772 if (elide_constraint_failure_p())
2774 inform (loc, "%qE evaluated to false", cur);
2777 /* Do our best to infer meaning from predicates. */
2780 diagnose_predicate_constraint (location_t loc, tree orig, tree cur, tree args)
2782 if (TREE_CODE (PRED_CONSTR_EXPR (cur)) == TRAIT_EXPR)
2783 diagnose_trait_expression (loc, orig, cur, args);
2785 diagnose_other_expression (loc, orig, cur, args);
2788 /* Diagnose a failed pack expansion, possibly containing constraints. */
2791 diagnose_pack_expansion (location_t loc, tree, tree cur, tree args)
2793 if (constraint_expression_satisfied_p (cur, args))
2795 if (elide_constraint_failure_p())
2798 /* Make sure that we don't have naked packs that we don't expect. */
2799 if (!same_type_p (TREE_TYPE (cur), boolean_type_node))
2801 inform (loc, "invalid pack expansion in constraint %qE", cur);
2805 inform (loc, "in the expansion of %qE", cur);
2807 /* Get the vector of expanded arguments. Note that n must not
2808 be 0 since this constraint is not satisfied. */
2809 ++processing_template_decl;
2810 tree exprs = tsubst_pack_expansion (cur, args, tf_none, NULL_TREE);
2811 --processing_template_decl;
2812 if (exprs == error_mark_node)
2814 /* TODO: This error message could be better. */
2815 inform (loc, " substitution failure occurred during expansion");
2819 /* Check each expanded constraint separately. */
2820 int n = TREE_VEC_LENGTH (exprs);
2821 for (int i = 0; i < n; ++i)
2823 tree expr = TREE_VEC_ELT (exprs, i);
2824 if (!constraint_expression_satisfied_p (expr, args))
2825 inform (loc, " %qE was not satisfied", expr);
2829 /* Diagnose a potentially unsatisfied concept check constraint DECL<CARGS>.
2830 Parameters are as for diagnose_constraint. */
2833 diagnose_check_constraint (location_t loc, tree orig, tree cur, tree args)
2835 if (constraints_satisfied_p (cur, args))
2838 tree decl = CHECK_CONSTR_CONCEPT (cur);
2839 tree cargs = CHECK_CONSTR_ARGS (cur);
2840 tree tmpl = DECL_TI_TEMPLATE (decl);
2841 tree check = build_nt (CHECK_CONSTR, decl, cargs);
2843 /* Instantiate the concept check arguments. */
2844 tree targs = tsubst (cargs, args, tf_none, NULL_TREE);
2845 if (targs == error_mark_node)
2847 if (elide_constraint_failure_p ())
2849 inform (loc, "invalid use of the concept %qE", check);
2850 tsubst (cargs, args, tf_warning_or_error, NULL_TREE);
2854 tree sub = build_tree_list (tmpl, targs);
2855 /* Update to the expanded definitions. */
2856 cur = expand_concept (decl, targs);
2857 if (cur == error_mark_node)
2859 if (elide_constraint_failure_p ())
2861 inform (loc, "in the expansion of concept %qE %S", check, sub);
2862 cur = get_concept_definition (decl);
2863 tsubst_expr (cur, targs, tf_warning_or_error, NULL_TREE, false);
2867 orig = get_concept_definition (CHECK_CONSTR_CONCEPT (orig));
2868 orig = normalize_expression (orig);
2870 location_t dloc = DECL_SOURCE_LOCATION (decl);
2871 inform (dloc, "within %qS", sub);
2872 diagnose_constraint (dloc, orig, cur, targs);
2875 /* Diagnose a potentially unsatisfied conjunction or disjunction. Parameters
2876 are as for diagnose_constraint. */
2879 diagnose_logical_constraint (location_t loc, tree orig, tree cur, tree args)
2881 tree t0 = TREE_OPERAND (cur, 0);
2882 tree t1 = TREE_OPERAND (cur, 1);
2883 if (!constraints_satisfied_p (t0, args))
2884 diagnose_constraint (loc, TREE_OPERAND (orig, 0), t0, args);
2885 else if (TREE_CODE (orig) == TRUTH_ORIF_EXPR)
2887 if (!constraints_satisfied_p (t1, args))
2888 diagnose_constraint (loc, TREE_OPERAND (orig, 1), t1, args);
2891 /* Diagnose a potential expression constraint failure. */
2894 diagnose_expression_constraint (location_t loc, tree orig, tree cur, tree args)
2896 if (constraints_satisfied_p (cur, args))
2898 if (elide_constraint_failure_p())
2901 tree expr = EXPR_CONSTR_EXPR (orig);
2902 inform (loc, "the required expression %qE would be ill-formed", expr);
2904 // TODO: We should have a flag that controls this substitution.
2905 // I'm finding it very useful for resolving concept check errors.
2907 // inform (input_location, "==== BEGIN DUMP ====");
2908 // tsubst_expr (EXPR_CONSTR_EXPR (orig), args, tf_warning_or_error, NULL_TREE, false);
2909 // inform (input_location, "==== END DUMP ====");
2912 /* Diagnose a potentially failed type constraint. */
2915 diagnose_type_constraint (location_t loc, tree orig, tree cur, tree args)
2917 if (constraints_satisfied_p (cur, args))
2919 if (elide_constraint_failure_p())
2922 tree type = TYPE_CONSTR_TYPE (orig);
2923 inform (loc, "the required type %qT would be ill-formed", type);
2926 /* Diagnose a potentially unsatisfied conversion constraint. */
2929 diagnose_implicit_conversion_constraint (location_t loc, tree orig, tree cur,
2932 if (constraints_satisfied_p (cur, args))
2935 /* The expression and type will previously have been substituted into,
2936 and therefore may already be an error. Also, we will have already
2937 diagnosed substitution failures into an expression since this must be
2938 part of a compound requirement. */
2939 tree expr = ICONV_CONSTR_EXPR (cur);
2940 if (error_operand_p (expr))
2943 /* Don't elide a previously diagnosed failure. */
2944 if (elide_constraint_failure_p())
2947 tree type = ICONV_CONSTR_TYPE (cur);
2948 if (error_operand_p (type))
2950 inform (loc, "substitution into type %qT failed",
2951 ICONV_CONSTR_TYPE (orig));
2955 inform(loc, "%qE is not implicitly convertible to %qT", expr, type);
2958 /* Diagnose an argument deduction constraint. */
2961 diagnose_argument_deduction_constraint (location_t loc, tree orig, tree cur,
2964 if (constraints_satisfied_p (cur, args))
2967 /* The expression and type will previously have been substituted into,
2968 and therefore may already be an error. Also, we will have already
2969 diagnosed substution failures into an expression since this must be
2970 part of a compound requirement. */
2971 tree expr = DEDUCT_CONSTR_EXPR (cur);
2972 if (error_operand_p (expr))
2975 /* Don't elide a previously diagnosed failure. */
2976 if (elide_constraint_failure_p ())
2979 tree pattern = DEDUCT_CONSTR_PATTERN (cur);
2980 if (error_operand_p (pattern))
2982 inform (loc, "substitution into type %qT failed",
2983 DEDUCT_CONSTR_PATTERN (orig));
2987 inform (loc, "unable to deduce placeholder type %qT from %qE",
2991 /* Diagnose an exception constraint. */
2994 diagnose_exception_constraint (location_t loc, tree orig, tree cur, tree args)
2996 if (constraints_satisfied_p (cur, args))
2998 if (elide_constraint_failure_p ())
3001 /* Rebuild a noexcept expression. */
3002 tree expr = EXCEPT_CONSTR_EXPR (cur);
3003 if (error_operand_p (expr))
3006 inform (loc, "%qE evaluated to false", EXCEPT_CONSTR_EXPR (orig));
3009 /* Diagnose a potentially unsatisfied parameterized constraint. */
3012 diagnose_parameterized_constraint (location_t loc, tree orig, tree cur,
3015 if (constraints_satisfied_p (cur, args))
3018 local_specialization_stack stack;
3019 tree parms = PARM_CONSTR_PARMS (cur);
3020 tree vars = tsubst_constraint_variables (parms, args, tf_warning_or_error,
3022 if (vars == error_mark_node)
3024 if (elide_constraint_failure_p ())
3027 /* TODO: Check which variable failed and use orig to diagnose
3028 that substitution error. */
3029 inform (loc, "failed to instantiate constraint variables");
3033 /* TODO: It would be better write these in a list. */
3036 inform (loc, " with %q#D", vars);
3037 vars = TREE_CHAIN (vars);
3039 orig = PARM_CONSTR_OPERAND (orig);
3040 cur = PARM_CONSTR_OPERAND (cur);
3041 return diagnose_constraint (loc, orig, cur, args);
3044 /* Diagnose the constraint CUR for the given ARGS. This is only ever invoked
3045 on the associated constraints, so we can only have conjunctions of
3046 predicate constraints. The ORIGinal (dependent) constructs follow
3047 the current constraints to enable better diagnostics. Note that ORIG
3048 and CUR must be the same kinds of node, except when CUR is an error. */
3051 diagnose_constraint (location_t loc, tree orig, tree cur, tree args)
3053 switch (TREE_CODE (cur))
3056 diagnose_expression_constraint (loc, orig, cur, args);
3060 diagnose_type_constraint (loc, orig, cur, args);
3064 diagnose_implicit_conversion_constraint (loc, orig, cur, args);
3068 diagnose_argument_deduction_constraint (loc, orig, cur, args);
3072 diagnose_exception_constraint (loc, orig, cur, args);
3077 diagnose_logical_constraint (loc, orig, cur, args);
3081 diagnose_predicate_constraint (loc, orig, cur, args);
3085 diagnose_parameterized_constraint (loc, orig, cur, args);
3089 diagnose_check_constraint (loc, orig, cur, args);
3092 case EXPR_PACK_EXPANSION:
3093 diagnose_pack_expansion (loc, orig, cur, args);
3097 /* TODO: Can we improve the diagnostic with the original? */
3098 inform (input_location, "ill-formed constraint");
3107 /* Diagnose the reason(s) why ARGS do not satisfy the constraints
3108 of declaration DECL. */
3111 diagnose_declaration_constraints (location_t loc, tree decl, tree args)
3113 inform (loc, " constraints not satisfied");
3115 /* Constraints are attached to the template. */
3116 if (tree ti = DECL_TEMPLATE_INFO (decl))
3118 decl = TI_TEMPLATE (ti);
3120 args = TI_ARGS (ti);
3123 /* Recursively diagnose the associated constraints. */
3124 tree ci = get_constraints (decl);
3125 tree t = CI_ASSOCIATED_CONSTRAINTS (ci);
3126 diagnose_constraint (loc, t, t, args);
3131 /* Emit diagnostics detailing the failure ARGS to satisfy the
3132 constraints of T. Here, T can be either a constraint
3133 or a declaration. */
3136 diagnose_constraints (location_t loc, tree t, tree args)
3138 constraint_errors = 0;
3140 if (constraint_p (t))
3141 diagnose_constraint (loc, t, t, args);
3142 else if (DECL_P (t))
3143 diagnose_declaration_constraints (loc, t, args);
3147 /* Note the number of elided failures. */
3148 int n = undiagnosed_constraint_failures ();
3150 inform (loc, "... and %d more constraint errors not shown", n);