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"
45 #include "tree-iterator.h"
48 #include "type-utils.h"
50 /*---------------------------------------------------------------------------
51 Operations on constraints
52 ---------------------------------------------------------------------------*/
54 /* Returns true if C is a constraint tree code. Note that ERROR_MARK
55 is a valid constraint. */
58 constraint_p (tree_code c)
60 return ((PRED_CONSTR <= c && c <= DISJ_CONSTR)
61 || c == EXPR_PACK_EXPANSION
65 /* Returns true if T is a constraint. Note that error_mark_node
66 is a valid constraint. */
71 return constraint_p (TREE_CODE (t));
74 /* Returns the conjunction of two constraints A and B. Note that
75 conjoining a non-null constraint with NULL_TREE is an identity
76 operation. That is, for non-null A,
78 conjoin_constraints(a, NULL_TREE) == a
82 conjoin_constraints (NULL_TREE, a) == a
84 If both A and B are NULL_TREE, the result is also NULL_TREE. */
87 conjoin_constraints (tree a, tree b)
89 gcc_assert (a ? constraint_p (a) : true);
90 gcc_assert (b ? constraint_p (b) : true);
92 return b ? build_nt (CONJ_CONSTR, a, b) : a;
99 /* Transform the vector of expressions in the T into a conjunction
100 of requirements. T must be a TREE_VEC. */
103 conjoin_constraints (tree t)
105 gcc_assert (TREE_CODE (t) == TREE_VEC);
107 for (int i = 0; i < TREE_VEC_LENGTH (t); ++i)
108 r = conjoin_constraints (r, TREE_VEC_ELT (t, i));
112 /* Returns true if T is a call expression to a function
116 function_concept_check_p (tree t)
118 gcc_assert (TREE_CODE (t) == CALL_EXPR);
119 tree fn = CALL_EXPR_FN (t);
120 if (TREE_CODE (fn) == TEMPLATE_ID_EXPR
121 && TREE_CODE (TREE_OPERAND (fn, 0)) == OVERLOAD)
123 tree f1 = get_first_fn (fn);
124 if (TREE_CODE (f1) == TEMPLATE_DECL
125 && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (f1)))
131 /* Returns true if any of the arguments in the template
132 argument list is a wildcard or wildcard pack. */
135 contains_wildcard_p (tree args)
137 for (int i = 0; i < TREE_VEC_LENGTH (args); ++i)
139 tree arg = TREE_VEC_ELT (args, i);
140 if (TREE_CODE (arg) == WILDCARD_DECL)
146 /* Build a new call expression, but don't actually generate a
147 new function call. We just want the tree, not the semantics. */
150 build_call_check (tree id)
152 ++processing_template_decl;
153 vec<tree, va_gc> *fargs = make_tree_vector();
154 tree call = finish_call_expr (id, &fargs, false, false, tf_none);
155 release_tree_vector (fargs);
156 --processing_template_decl;
160 /* Build an expression that will check a variable concept. If any
161 argument contains a wildcard, don't try to finish the variable
162 template because we can't substitute into a non-existent
166 build_variable_check (tree id)
168 gcc_assert (TREE_CODE (id) == TEMPLATE_ID_EXPR);
169 if (contains_wildcard_p (TREE_OPERAND (id, 1)))
172 ++processing_template_decl;
173 tree var = finish_template_variable (id);
174 --processing_template_decl;
178 /*---------------------------------------------------------------------------
179 Resolution of qualified concept names
180 ---------------------------------------------------------------------------*/
182 /* This facility is used to resolve constraint checks from
183 requirement expressions. A constraint check is a call to
184 a function template declared with the keyword 'concept'.
186 The result of resolution is a pair (a TREE_LIST) whose value
187 is the matched declaration, and whose purpose contains the
188 coerced template arguments that can be substituted into the
191 // Given an overload set OVL, try to find a unique definition that can be
192 // instantiated by the template arguments ARGS.
194 // This function is not called for arbitrary call expressions. In particular,
195 // the call expression must be written with explicit template arguments
196 // and no function arguments. For example:
200 // If a single match is found, this returns a TREE_LIST whose VALUE
201 // is the constraint function (not the template), and its PURPOSE is
202 // the complete set of arguments substituted into the parameter list.
204 resolve_constraint_check (tree ovl, tree args)
207 tree cands = NULL_TREE;
208 for (tree p = ovl; p != NULL_TREE; p = OVL_NEXT (p))
210 // Get the next template overload.
211 tree tmpl = OVL_CURRENT (p);
212 if (TREE_CODE (tmpl) != TEMPLATE_DECL)
215 // Don't try to deduce checks for non-concepts. We often
216 // end up trying to resolve constraints in functional casts
217 // as part of a postfix-expression. We can save time and
218 // headaches by not instantiating those declarations.
220 // NOTE: This masks a potential error, caused by instantiating
221 // non-deduced contexts using placeholder arguments.
222 tree fn = DECL_TEMPLATE_RESULT (tmpl);
223 if (DECL_ARGUMENTS (fn))
225 if (!DECL_DECLARED_CONCEPT_P (fn))
228 // Remember the candidate if we can deduce a substitution.
229 ++processing_template_decl;
230 tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl));
231 if (tree subst = coerce_template_parms (parms, args, tmpl))
233 if (subst == error_mark_node)
236 cands = tree_cons (subst, fn, cands);
238 --processing_template_decl;
242 /* We either had no candidates or failed deductions. */
243 return nerrs ? error_mark_node : NULL_TREE;
244 else if (TREE_CHAIN (cands))
245 /* There are multiple candidates. */
246 return error_mark_node;
251 // Determine if the the call expression CALL is a constraint check, and
252 // return the concept declaration and arguments being checked. If CALL
253 // does not denote a constraint check, return NULL.
255 resolve_constraint_check (tree call)
257 gcc_assert (TREE_CODE (call) == CALL_EXPR);
259 // A constraint check must be only a template-id expression. If
260 // it's a call to a base-link, its function(s) should be a
261 // template-id expression. If this is not a template-id, then it
262 // cannot be a concept-check.
263 tree target = CALL_EXPR_FN (call);
264 if (BASELINK_P (target))
265 target = BASELINK_FUNCTIONS (target);
266 if (TREE_CODE (target) != TEMPLATE_ID_EXPR)
269 // Get the overload set and template arguments and try to
270 // resolve the target.
271 tree ovl = TREE_OPERAND (target, 0);
273 /* This is a function call of a variable concept... ill-formed. */
274 if (TREE_CODE (ovl) == TEMPLATE_DECL)
276 error_at (location_of (call),
277 "function call of variable concept %qE", call);
278 return error_mark_node;
281 tree args = TREE_OPERAND (target, 1);
282 return resolve_constraint_check (ovl, args);
285 /* Returns a pair containing the checked variable concept
286 and its associated prototype parameter. The result
287 is a TREE_LIST whose TREE_VALUE is the variable concept
288 and whose TREE_PURPOSE is the prototype parameter. */
291 resolve_variable_concept_check (tree id)
293 tree tmpl = TREE_OPERAND (id, 0);
294 tree args = TREE_OPERAND (id, 1);
296 if (!variable_concept_p (tmpl))
299 /* Make sure that we have the right parameters before
300 assuming that it works. Note that failing to deduce
301 will result in diagnostics. */
302 tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl));
303 ++processing_template_decl;
304 tree result = coerce_template_parms (parms, args, tmpl);
305 --processing_template_decl;
306 if (result != error_mark_node)
308 tree decl = DECL_TEMPLATE_RESULT (tmpl);
309 return build_tree_list (result, decl);
312 return error_mark_node;
316 /* Given a call expression or template-id expression to
317 a concept EXPR possibly including a wildcard, deduce
318 the concept being checked and the prototype parameter.
319 Returns true if the constraint and prototype can be
320 deduced and false otherwise. Note that the CHECK and
321 PROTO arguments are set to NULL_TREE if this returns
325 deduce_constrained_parameter (tree expr, tree& check, tree& proto)
327 tree info = NULL_TREE;
328 if (TREE_CODE (expr) == TEMPLATE_ID_EXPR)
329 info = resolve_variable_concept_check (expr);
330 else if (TREE_CODE (expr) == CALL_EXPR)
331 info = resolve_constraint_check (expr);
335 if (info && info != error_mark_node)
337 check = TREE_VALUE (info);
338 tree arg = TREE_VEC_ELT (TREE_PURPOSE (info), 0);
339 if (ARGUMENT_PACK_P (arg))
340 arg = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg), 0);
341 proto = TREE_TYPE (arg);
344 check = proto = NULL_TREE;
348 // Given a call expression or template-id expression to a concept, EXPR,
349 // deduce the concept being checked and return the template arguments.
350 // Returns NULL_TREE if deduction fails.
352 deduce_concept_introduction (tree expr)
354 tree info = NULL_TREE;
355 if (TREE_CODE (expr) == TEMPLATE_ID_EXPR)
356 info = resolve_variable_concept_check (expr);
357 else if (TREE_CODE (expr) == CALL_EXPR)
358 info = resolve_constraint_check (expr);
362 if (info && info != error_mark_node)
363 return TREE_PURPOSE (info);
369 /*---------------------------------------------------------------------------
370 Constraint implication learning
371 ---------------------------------------------------------------------------*/
373 /* The implication context determines how we memoize concept checks.
374 Given two checks C1 and C2, the direction of implication depends
375 on whether we are learning implications of a conjunction or disjunction.
378 template<typename T> concept bool C = ...;
379 template<typenaem T> concept bool D = C<T> && true;
381 From this, we can learn that D<T> implies C<T>. We cannot learn,
382 without further testing, that C<T> does not imply D<T>. If, for
383 example, C<T> were defined as true, then these constraints would
384 be logically equivalent.
386 In rare cases, we may start with a logical equivalence. For example:
388 template<typename T> concept bool C = ...;
389 template<typename T> concept bool D = C<T>;
391 Here, we learn that C<T> implies D<T> and vice versa. */
393 enum implication_context
395 conjunction_cxt, /* C1 implies C2. */
396 disjunction_cxt, /* C2 implies C1. */
397 equivalence_cxt /* C1 implies C2, C2 implies C1. */
400 void learn_implications(tree, tree, implication_context);
403 learn_implication (tree parent, tree child, implication_context cxt)
407 case conjunction_cxt:
408 save_subsumption_result (parent, child, true);
410 case disjunction_cxt:
411 save_subsumption_result (child, parent, true);
413 case equivalence_cxt:
414 save_subsumption_result (parent, child, true);
415 save_subsumption_result (child, parent, true);
421 learn_logical_operation (tree parent, tree constr, implication_context cxt)
423 learn_implications (parent, TREE_OPERAND (constr, 0), cxt);
424 learn_implications (parent, TREE_OPERAND (constr, 1), cxt);
428 learn_implications (tree parent, tree constr, implication_context cxt)
430 switch (TREE_CODE (constr))
433 return learn_implication (parent, constr, cxt);
436 if (cxt == disjunction_cxt)
438 return learn_logical_operation (parent, constr, cxt);
441 if (cxt == conjunction_cxt)
443 return learn_logical_operation (parent, constr, cxt);
450 /* Quickly scan the top-level constraints of CONSTR to learn and
451 cache logical relations between concepts. The search does not
452 include conjunctions of disjunctions or vice versa. */
455 learn_implications (tree tmpl, tree args, tree constr)
457 /* Don't memoize relations between non-dependent arguemnts. It's not
459 if (!uses_template_parms (args))
462 /* Build a check constraint for the purpose of caching. */
463 tree parent = build_nt (CHECK_CONSTR, tmpl, args);
465 /* Start learning based on the kind of the top-level contraint. */
466 if (TREE_CODE (constr) == CONJ_CONSTR)
467 return learn_logical_operation (parent, constr, conjunction_cxt);
468 else if (TREE_CODE (constr) == DISJ_CONSTR)
469 return learn_logical_operation (parent, constr, disjunction_cxt);
470 else if (TREE_CODE (constr) == CHECK_CONSTR)
471 /* This is the rare concept alias case. */
472 return learn_implication (parent, constr, equivalence_cxt);
475 /*---------------------------------------------------------------------------
476 Expansion of concept definitions
477 ---------------------------------------------------------------------------*/
479 /* Returns the expression of a function concept. */
482 get_returned_expression (tree fn)
484 /* Extract the body of the function minus the return expression. */
485 tree body = DECL_SAVED_TREE (fn);
487 return error_mark_node;
488 if (TREE_CODE (body) == BIND_EXPR)
489 body = BIND_EXPR_BODY (body);
490 if (TREE_CODE (body) != RETURN_EXPR)
491 return error_mark_node;
493 return TREE_OPERAND (body, 0);
496 /* Returns the initializer of a variable concept. */
499 get_variable_initializer (tree var)
501 tree init = DECL_INITIAL (var);
503 return error_mark_node;
507 /* Returns the definition of a variable or function concept. */
510 get_concept_definition (tree decl)
512 if (TREE_CODE (decl) == VAR_DECL)
513 return get_variable_initializer (decl);
514 else if (TREE_CODE (decl) == FUNCTION_DECL)
515 return get_returned_expression (decl);
519 int expansion_level = 0;
521 struct expanding_concept_sentinel
523 expanding_concept_sentinel ()
528 ~expanding_concept_sentinel()
537 /* Returns true when a concept is being expanded. */
542 return expansion_level > 0;
545 /* Expand a concept declaration (not a template) and its arguments to
546 a constraint defined by the concept's initializer or definition. */
549 expand_concept (tree decl, tree args)
551 expanding_concept_sentinel sentinel;
553 if (TREE_CODE (decl) == TEMPLATE_DECL)
554 decl = DECL_TEMPLATE_RESULT (decl);
555 tree tmpl = DECL_TI_TEMPLATE (decl);
557 /* Check for a previous specialization. */
558 if (tree spec = get_concept_expansion (tmpl, args))
561 /* Substitute the arguments to form a new definition expression. */
562 tree def = get_concept_definition (decl);
564 ++processing_template_decl;
565 tree result = tsubst_expr (def, args, tf_none, NULL_TREE, true);
566 --processing_template_decl;
567 if (result == error_mark_node)
568 return error_mark_node;
570 /* And lastly, normalize it, check for implications, and save
571 the specialization for later. */
572 tree norm = normalize_expression (result);
573 learn_implications (tmpl, args, norm);
574 return save_concept_expansion (tmpl, args, norm);
578 /*---------------------------------------------------------------------------
579 Stepwise normalization of expressions
581 This set of functions will transform an expression into a constraint
582 in a sequence of steps. Normalization does not not look into concept
584 ---------------------------------------------------------------------------*/
586 /* Transform a logical-or or logical-and expression into either
587 a conjunction or disjunction. */
590 normalize_logical_operation (tree t, tree_code c)
592 tree t0 = normalize_expression (TREE_OPERAND (t, 0));
593 tree t1 = normalize_expression (TREE_OPERAND (t, 1));
594 return build_nt (c, t0, t1);
597 /* A simple requirement T introduces an expression constraint
598 for its expression. */
601 normalize_simple_requirement (tree t)
603 return build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0));
606 /* A type requirement T introduce a type constraint for its type. */
609 normalize_type_requirement (tree t)
611 return build_nt (TYPE_CONSTR, TREE_OPERAND (t, 0));
614 /* A compound requirement T introduces a conjunction of constraints
615 depending on its form. The conjunction always includes an
616 expression constraint for the expression of the requirement.
617 If a trailing return type was specified, the conjunction includes
618 either an implicit conversion constraint or an argument deduction
619 constraint. If the noexcept specifier is present, the conjunction
620 includes an exception constraint. */
623 normalize_compound_requirement (tree t)
625 tree expr = TREE_OPERAND (t, 0);
626 tree constr = build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0));
628 /* If a type is given, append an implicit conversion or
629 argument deduction constraint. */
630 if (tree type = TREE_OPERAND (t, 1))
633 /* TODO: We should be extracting a list of auto nodes
634 from type_uses_auto, not a single node */
635 if (tree placeholder = type_uses_auto (type))
636 type_constr = build_nt (DEDUCT_CONSTR, expr, type, placeholder);
638 type_constr = build_nt (ICONV_CONSTR, expr, type);
639 constr = conjoin_constraints (constr, type_constr);
642 /* If noexcept is present, append an exception constraint. */
643 if (COMPOUND_REQ_NOEXCEPT_P (t))
645 tree except = build_nt (EXCEPT_CONSTR, expr);
646 constr = conjoin_constraints (constr, except);
652 /* A nested requirement T introduces a conjunction of constraints
653 corresponding to its constraint-expression.
655 If the result of transforming T is error_mark_node, the resulting
656 constraint is a predicate constraint whose operand is also
657 error_mark_node. This preserves the constraint structure, but
658 will guarantee that the constraint is never satisfied. */
661 normalize_nested_requirement (tree t)
663 return normalize_expression (TREE_OPERAND (t, 0));
666 /* Transform a requirement T into one or more constraints. */
669 normalize_requirement (tree t)
671 switch (TREE_CODE (t))
674 return normalize_simple_requirement (t);
677 return normalize_type_requirement (t);
680 return normalize_compound_requirement (t);
683 return normalize_nested_requirement (t);
688 return error_mark_node;
691 /* Transform a sequence of requirements into a conjunction of
695 normalize_requirements (tree t)
697 tree result = NULL_TREE;
698 for (; t; t = TREE_CHAIN (t))
700 tree constr = normalize_requirement (TREE_VALUE (t));
701 result = conjoin_constraints (result, constr);
706 /* The normal form of a requires-expression is a parameterized
707 constraint having the same parameters and a conjunction of
708 constraints representing the normal form of requirements. */
711 normalize_requires_expression (tree t)
713 tree operand = normalize_requirements (TREE_OPERAND (t, 1));
714 if (tree parms = TREE_OPERAND (t, 0))
715 return build_nt (PARM_CONSTR, parms, operand);
720 /* For a template-id referring to a variable concept, returns
721 a check constraint. Otherwise, returns a predicate constraint. */
724 normalize_template_id_expression (tree t)
726 if (tree info = resolve_variable_concept_check (t))
728 if (info == error_mark_node)
730 /* We get this when the template arguments don't match
731 the variable concept. */
732 error ("invalid reference to concept %qE", t);
733 return error_mark_node;
736 tree decl = TREE_VALUE (info);
737 tree args = TREE_PURPOSE (info);
738 return build_nt (CHECK_CONSTR, decl, args);
741 /* Check that we didn't refer to a function concept like a variable. */
742 tree tmpl = TREE_OPERAND (t, 0);
743 if (TREE_CODE (tmpl) == OVERLOAD)
745 tree fn = OVL_FUNCTION (tmpl);
746 if (TREE_CODE (fn) == TEMPLATE_DECL
747 && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (fn)))
749 error_at (location_of (t),
750 "invalid reference to function concept %qD", fn);
751 return error_mark_node;
755 return build_nt (PRED_CONSTR, t);
758 /* For a call expression to a function concept, returns a check
759 constraint. Otherwise, returns a predicate constraint. */
762 normalize_call_expression (tree t)
764 /* Try to resolve this function call as a concept. If not, then
765 it can be returned as a predicate constraint. */
766 tree check = resolve_constraint_check (t);
768 return build_nt (PRED_CONSTR, t);
769 if (check == error_mark_node)
771 /* TODO: Improve diagnostics. We could report why the reference
773 error ("invalid reference to concept %qE", t);
774 return error_mark_node;
777 tree fn = TREE_VALUE (check);
778 tree args = TREE_PURPOSE (check);
779 return build_nt (CHECK_CONSTR, fn, args);
782 /* If T is a call to an overloaded && or || operator, diagnose that
783 as a non-SFINAEable error. Returns true if an error is emitted.
785 TODO: It would be better to diagnose this at the point of definition,
786 if possible. Perhaps we should immediately do a first-pass normalization
787 of a concept definition to catch obvious non-dependent errors like
791 check_for_logical_overloads (tree t)
793 if (TREE_CODE (t) != CALL_EXPR)
796 tree fn = CALL_EXPR_FN (t);
798 /* For member calls, try extracting the function from the
800 if (TREE_CODE (fn) == COMPONENT_REF)
802 fn = TREE_OPERAND (fn, 1);
803 if (TREE_CODE (fn) == BASELINK)
804 fn = BASELINK_FUNCTIONS (fn);
807 if (TREE_CODE (fn) != FUNCTION_DECL)
810 if (DECL_OVERLOADED_OPERATOR_P (fn))
812 location_t loc = EXPR_LOC_OR_LOC (t, input_location);
813 error_at (loc, "constraint %qE, uses overloaded operator", t);
820 /* The normal form of an atom depends on the expression. The normal
821 form of a function call to a function concept is a check constraint
822 for that concept. The normal form of a reference to a variable
823 concept is a check constraint for that concept. Otherwise, the
824 constraint is a predicate constraint. */
827 normalize_atom (tree t)
829 /* We can get constraints pushed down through pack expansions, so
831 if (constraint_p (t))
834 tree type = TREE_TYPE (t);
835 if (!type || type_unknown_p (t) || TREE_CODE (type) == TEMPLATE_TYPE_PARM)
837 else if (!dependent_type_p (type))
839 if (check_for_logical_overloads (t))
840 return error_mark_node;
842 type = cv_unqualified (type);
843 if (!same_type_p (type, boolean_type_node))
845 error ("predicate constraint %q+E does not have type %<bool%>", t);
846 return error_mark_node;
850 if (TREE_CODE (t) == TEMPLATE_ID_EXPR)
851 return normalize_template_id_expression (t);
852 if (TREE_CODE (t) == CALL_EXPR)
853 return normalize_call_expression (t);
854 return build_nt (PRED_CONSTR, t);
857 /* Push down the pack expansion EXP into the leaves of the constraint PAT. */
860 push_down_pack_expansion (tree exp, tree pat)
862 switch (TREE_CODE (pat))
867 pat = copy_node (pat);
868 TREE_OPERAND (pat, 0)
869 = push_down_pack_expansion (exp, TREE_OPERAND (pat, 0));
870 TREE_OPERAND (pat, 1)
871 = push_down_pack_expansion (exp, TREE_OPERAND (pat, 1));
876 exp = copy_node (exp);
877 SET_PACK_EXPANSION_PATTERN (exp, pat);
883 /* Transform a pack expansion into a constraint. First we transform the
884 pattern of the pack expansion, then we push the pack expansion down into the
885 leaves of the constraint so that partial ordering will work. */
888 normalize_pack_expansion (tree t)
890 tree pat = normalize_expression (PACK_EXPANSION_PATTERN (t));
891 return push_down_pack_expansion (t, pat);
894 /* Transform an expression into a constraint. */
897 normalize_any_expression (tree t)
899 switch (TREE_CODE (t))
901 case TRUTH_ANDIF_EXPR:
902 return normalize_logical_operation (t, CONJ_CONSTR);
904 case TRUTH_ORIF_EXPR:
905 return normalize_logical_operation (t, DISJ_CONSTR);
908 return normalize_requires_expression (t);
911 return normalize_expression (BIND_EXPR_BODY (t));
913 case EXPR_PACK_EXPANSION:
914 return normalize_pack_expansion (t);
917 /* All other constraints are atomic. */
918 return normalize_atom (t);
922 /* Transform a statement into an expression. */
924 normalize_any_statement (tree t)
926 switch (TREE_CODE (t))
929 return normalize_expression (TREE_OPERAND (t, 0));
933 return error_mark_node;
936 /* Reduction rules for the declaration T. */
939 normalize_any_declaration (tree t)
941 switch (TREE_CODE (t))
944 return normalize_atom (t);
948 return error_mark_node;
951 /* Returns the normal form of a constraint expression. */
954 normalize_expression (tree t)
959 if (t == error_mark_node)
960 return error_mark_node;
962 switch (TREE_CODE_CLASS (TREE_CODE (t)))
968 return normalize_any_expression (t);
971 return normalize_any_statement (t);
973 case tcc_declaration:
974 return normalize_any_declaration (t);
976 case tcc_exceptional:
980 /* These are all atomic predicate constraints. */
981 return normalize_atom (t);
984 /* Unhandled node kind. */
987 return error_mark_node;
991 /*---------------------------------------------------------------------------
992 Constraint normalization
993 ---------------------------------------------------------------------------*/
995 tree normalize_constraint (tree);
997 /* The normal form of the disjunction T0 /\ T1 is the conjunction
998 of the normal form of T0 and the normal form of T1. */
1001 normalize_conjunction (tree t)
1003 tree t0 = normalize_constraint (TREE_OPERAND (t, 0));
1004 tree t1 = normalize_constraint (TREE_OPERAND (t, 1));
1005 return build_nt (CONJ_CONSTR, t0, t1);
1008 /* The normal form of the disjunction T0 \/ T1 is the disjunction
1009 of the normal form of T0 and the normal form of T1. */
1012 normalize_disjunction (tree t)
1014 tree t0 = normalize_constraint (TREE_OPERAND (t, 0));
1015 tree t1 = normalize_constraint (TREE_OPERAND (t, 1));
1016 return build_nt (DISJ_CONSTR, t0, t1);
1019 /* A predicate constraint is normalized in two stages. First all
1020 references specializations of concepts are replaced by their
1021 substituted definitions. Then, the resulting expression is
1022 transformed into a constraint by transforming && expressions
1023 into conjunctions and || into disjunctions. */
1026 normalize_predicate_constraint (tree t)
1028 ++processing_template_decl;
1029 tree expr = PRED_CONSTR_EXPR (t);
1030 tree constr = normalize_expression (expr);
1031 --processing_template_decl;
1035 /* The normal form of a parameterized constraint is the normal
1036 form of its operand. */
1039 normalize_parameterized_constraint (tree t)
1041 tree parms = PARM_CONSTR_PARMS (t);
1042 tree operand = normalize_constraint (PARM_CONSTR_OPERAND (t));
1043 return build_nt (PARM_CONSTR, parms, operand);
1046 /* Normalize the constraint T by reducing it so that it is
1047 comprised of only conjunctions and disjunctions of atomic
1051 normalize_constraint (tree t)
1056 if (t == error_mark_node)
1059 switch (TREE_CODE (t))
1062 return normalize_conjunction (t);
1065 return normalize_disjunction (t);
1068 return normalize_predicate_constraint (t);
1071 return normalize_parameterized_constraint (t);
1078 /* These constraints are defined to be atomic. */
1082 /* CONSTR was not a constraint. */
1085 return error_mark_node;
1090 // -------------------------------------------------------------------------- //
1091 // Constraint Semantic Processing
1093 // The following functions are called by the parser and substitution rules
1094 // to create and evaluate constraint-related nodes.
1096 // The constraints associated with the current template parameters.
1098 current_template_constraints (void)
1100 if (!current_template_parms)
1102 tree tmpl_constr = TEMPLATE_PARM_CONSTRAINTS (current_template_parms);
1103 return build_constraints (tmpl_constr, NULL_TREE);
1106 // If the recently parsed TYPE declares or defines a template or template
1107 // specialization, get its corresponding constraints from the current
1108 // template parameters and bind them to TYPE's declaration.
1110 associate_classtype_constraints (tree type)
1112 if (!type || type == error_mark_node || TREE_CODE (type) != RECORD_TYPE)
1115 // An explicit class template specialization has no template
1117 if (!current_template_parms)
1120 if (CLASSTYPE_IS_TEMPLATE (type) || CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1122 tree decl = TYPE_STUB_DECL (type);
1123 tree ci = current_template_constraints ();
1125 // An implicitly instantiated member template declaration already
1126 // has associated constraints. If it is defined outside of its
1127 // class, then we need match these constraints against those of
1128 // original declaration.
1129 if (tree orig_ci = get_constraints (decl))
1131 if (!equivalent_constraints (ci, orig_ci))
1133 // FIXME: Improve diagnostics.
1134 error ("%qT does not match any declaration", type);
1135 return error_mark_node;
1139 set_constraints (decl, ci);
1146 // Create an empty constraint info block.
1147 inline tree_constraint_info*
1148 build_constraint_info ()
1150 return (tree_constraint_info *)make_node (CONSTRAINT_INFO);
1155 /* Build a constraint-info object that contains the associated constraints
1156 of a declaration. This also includes the declaration's template
1157 requirements (TREQS) and any trailing requirements for a function
1158 declarator (DREQS). Note that both TREQS and DREQS must be constraints.
1160 If the declaration has neither template nor declaration requirements
1161 this returns NULL_TREE, indicating an unconstrained declaration. */
1164 build_constraints (tree tmpl_reqs, tree decl_reqs)
1166 gcc_assert (tmpl_reqs ? constraint_p (tmpl_reqs) : true);
1167 gcc_assert (decl_reqs ? constraint_p (decl_reqs) : true);
1169 if (!tmpl_reqs && !decl_reqs)
1172 tree_constraint_info* ci = build_constraint_info ();
1173 ci->template_reqs = tmpl_reqs;
1174 ci->declarator_reqs = decl_reqs;
1175 ci->associated_constr = conjoin_constraints (tmpl_reqs, decl_reqs);
1182 /* Construct a sequence of template arguments by prepending
1183 ARG to REST. Either ARG or REST may be null. */
1185 build_concept_check_arguments (tree arg, tree rest)
1187 gcc_assert (rest ? TREE_CODE (rest) == TREE_VEC : true);
1191 int n = rest ? TREE_VEC_LENGTH (rest) : 0;
1192 args = make_tree_vec (n + 1);
1193 TREE_VEC_ELT (args, 0) = arg;
1195 for (int i = 0; i < n; ++i)
1196 TREE_VEC_ELT (args, i + 1) = TREE_VEC_ELT (rest, i);
1197 int def = rest ? GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (rest) : 0;
1198 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args, def + 1);
1202 gcc_assert (rest != NULL_TREE);
1210 /* Construct an expression that checks the concept given by
1211 TARGET. The TARGET must be:
1213 - an OVERLOAD referring to one or more function concepts
1214 - a BASELINK referring to an overload set of the above, or
1215 - a TEMPLTATE_DECL referring to a variable concept.
1217 ARG and REST are the explicit template arguments for the
1218 eventual concept check. */
1220 build_concept_check (tree target, tree arg, tree rest)
1222 tree args = build_concept_check_arguments (arg, rest);
1223 if (variable_template_p (target))
1224 return build_variable_check (lookup_template_variable (target, args));
1226 return build_call_check (lookup_template_function (target, args));
1230 /* Returns a TYPE_DECL that contains sufficient information to
1231 build a template parameter of the same kind as PROTO and
1232 constrained by the concept declaration CNC. Note that PROTO
1233 is the first template parameter of CNC.
1235 If specified, ARGS provides additional arguments to the
1236 constraint check. */
1238 build_constrained_parameter (tree cnc, tree proto, tree args)
1240 tree name = DECL_NAME (cnc);
1241 tree type = TREE_TYPE (proto);
1242 tree decl = build_decl (input_location, TYPE_DECL, name, type);
1243 CONSTRAINED_PARM_PROTOTYPE (decl) = proto;
1244 CONSTRAINED_PARM_CONCEPT (decl) = cnc;
1245 CONSTRAINED_PARM_EXTRA_ARGS (decl) = args;
1249 /* Create a constraint expression for the given DECL that
1250 evaluates the requirements specified by CONSTR, a TYPE_DECL
1251 that contains all the information necessary to build the
1252 requirements (see finish_concept_name for the layout of
1255 Note that the constraints are neither reduced nor decomposed.
1256 That is done only after the requires clause has been parsed
1259 This will always return a CHECK_CONSTR. */
1261 finish_shorthand_constraint (tree decl, tree constr)
1263 /* No requirements means no constraints. */
1267 tree proto = CONSTRAINED_PARM_PROTOTYPE (constr);
1268 tree con = CONSTRAINED_PARM_CONCEPT (constr);
1269 tree args = CONSTRAINED_PARM_EXTRA_ARGS (constr);
1271 /* If the parameter declaration is variadic, but the concept
1272 is not then we need to apply the concept to every element
1274 bool is_proto_pack = template_parameter_pack_p (proto);
1275 bool is_decl_pack = template_parameter_pack_p (decl);
1276 bool apply_to_all_p = is_decl_pack && !is_proto_pack;
1278 /* Get the argument and overload used for the requirement
1279 and adjust it if we're going to expand later. */
1280 tree arg = template_parm_to_arg (build_tree_list (NULL_TREE, decl));
1282 arg = PACK_EXPANSION_PATTERN (TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg), 0));
1284 /* Build the concept check. If it the constraint needs to be
1285 applied to all elements of the parameter pack, then make
1286 the constraint an expansion. */
1288 tree tmpl = DECL_TI_TEMPLATE (con);
1289 if (TREE_CODE (con) == VAR_DECL)
1291 check = build_concept_check (tmpl, arg, args);
1295 tree ovl = build_overload (tmpl, NULL_TREE);
1296 check = build_concept_check (ovl, arg, args);
1299 /* Make the check a pack expansion if needed.
1301 FIXME: We should be making a fold expression. */
1304 check = make_pack_expansion (check);
1305 TREE_TYPE (check) = boolean_type_node;
1308 return normalize_expression (check);
1311 /* Returns a conjunction of shorthand requirements for the template
1312 parameter list PARMS. Note that the requirements are stored in
1313 the TYPE of each tree node. */
1315 get_shorthand_constraints (tree parms)
1317 tree result = NULL_TREE;
1318 parms = INNERMOST_TEMPLATE_PARMS (parms);
1319 for (int i = 0; i < TREE_VEC_LENGTH (parms); ++i)
1321 tree parm = TREE_VEC_ELT (parms, i);
1322 tree constr = TEMPLATE_PARM_CONSTRAINTS (parm);
1323 result = conjoin_constraints (result, constr);
1328 // Returns and chains a new parameter for PARAMETER_LIST which will conform
1329 // to the prototype given by SRC_PARM. The new parameter will have its
1330 // identifier and location set according to IDENT and PARM_LOC respectively.
1332 process_introduction_parm (tree parameter_list, tree src_parm)
1334 // If we have a pack, we should have a single pack argument which is the
1335 // placeholder we want to look at.
1336 bool is_parameter_pack = ARGUMENT_PACK_P (src_parm);
1337 if (is_parameter_pack)
1338 src_parm = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (src_parm), 0);
1340 // At this point we should have a wildcard, but we want to
1341 // grab the associated decl from it. Also grab the stored
1342 // identifier and location that should be chained to it in
1344 gcc_assert (TREE_CODE (src_parm) == WILDCARD_DECL);
1346 tree ident = DECL_NAME (src_parm);
1347 location_t parm_loc = DECL_SOURCE_LOCATION (src_parm);
1349 // If we expect a pack and the deduced template is not a pack, or if the
1350 // template is using a pack and we didn't declare a pack, throw an error.
1351 if (is_parameter_pack != WILDCARD_PACK_P (src_parm))
1353 error_at (parm_loc, "cannot match pack for introduced parameter");
1354 tree err_parm = build_tree_list (error_mark_node, error_mark_node);
1355 return chainon (parameter_list, err_parm);
1358 src_parm = TREE_TYPE (src_parm);
1362 if (TREE_CODE (src_parm) == TYPE_DECL)
1364 is_non_type = false;
1365 parm = finish_template_type_parm (class_type_node, ident);
1367 else if (TREE_CODE (src_parm) == TEMPLATE_DECL)
1369 is_non_type = false;
1370 begin_template_parm_list ();
1371 current_template_parms = DECL_TEMPLATE_PARMS (src_parm);
1372 end_template_parm_list ();
1373 parm = finish_template_template_parm (class_type_node, ident);
1379 // Since we don't have a declarator, so we can copy the source
1380 // parameter and change the name and eventually the location.
1381 parm = copy_decl (src_parm);
1382 DECL_NAME (parm) = ident;
1385 // Wrap in a TREE_LIST for process_template_parm. Introductions do not
1386 // retain the defaults from the source template.
1387 parm = build_tree_list (NULL_TREE, parm);
1389 return process_template_parm (parameter_list, parm_loc, parm,
1390 is_non_type, is_parameter_pack);
1393 /* Associates a constraint check to the current template based
1394 on the introduction parameters. INTRO_LIST must be a TREE_VEC
1395 of WILDCARD_DECLs containing a chained PARM_DECL which
1396 contains the identifier as well as the source location.
1397 TMPL_DECL is the decl for the concept being used. If we
1398 take a concept, C, this will form a check in the form of
1399 C<INTRO_LIST> filling in any extra arguments needed by the
1402 Returns NULL_TREE if no concept could be matched and
1403 error_mark_node if an error occurred when matching. */
1405 finish_template_introduction (tree tmpl_decl, tree intro_list)
1407 /* Deduce the concept check. */
1408 tree expr = build_concept_check (tmpl_decl, NULL_TREE, intro_list);
1409 if (expr == error_mark_node)
1412 tree parms = deduce_concept_introduction (expr);
1416 /* Build template parameter scope for introduction. */
1417 tree parm_list = NULL_TREE;
1418 begin_template_parm_list ();
1419 int nargs = MIN (TREE_VEC_LENGTH (parms), TREE_VEC_LENGTH (intro_list));
1420 for (int n = 0; n < nargs; ++n)
1421 parm_list = process_introduction_parm (parm_list, TREE_VEC_ELT (parms, n));
1422 parm_list = end_template_parm_list (parm_list);
1423 for (int i = 0; i < TREE_VEC_LENGTH (parm_list); ++i)
1424 if (TREE_VALUE (TREE_VEC_ELT (parm_list, i)) == error_mark_node)
1426 end_template_decl ();
1427 return error_mark_node;
1430 /* Build a concept check for our constraint. */
1431 tree check_args = make_tree_vec (TREE_VEC_LENGTH (parms));
1433 for (; n < TREE_VEC_LENGTH (parm_list); ++n)
1435 tree parm = TREE_VEC_ELT (parm_list, n);
1436 TREE_VEC_ELT (check_args, n) = template_parm_to_arg (parm);
1438 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (check_args, n);
1440 /* If the template expects more parameters we should be able
1441 to use the defaults from our deduced concept. */
1442 for (; n < TREE_VEC_LENGTH (parms); ++n)
1443 TREE_VEC_ELT (check_args, n) = TREE_VEC_ELT (parms, n);
1445 /* Associate the constraint. */
1446 tree check = build_concept_check (tmpl_decl, NULL_TREE, check_args);
1447 tree constr = normalize_expression (check);
1448 TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = constr;
1454 /* Given the predicate constraint T from a constrained-type-specifier, extract
1455 its TMPL and ARGS. FIXME why do we need two different forms of
1456 constrained-type-specifier? */
1459 placeholder_extract_concept_and_args (tree t, tree &tmpl, tree &args)
1461 if (TREE_CODE (t) == TYPE_DECL)
1463 /* A constrained parameter. Build a constraint check
1464 based on the prototype parameter and then extract the
1465 arguments from that. */
1466 tree proto = CONSTRAINED_PARM_PROTOTYPE (t);
1467 tree check = finish_shorthand_constraint (proto, t);
1468 placeholder_extract_concept_and_args (check, tmpl, args);
1472 if (TREE_CODE (t) == CHECK_CONSTR)
1474 tree decl = CHECK_CONSTR_CONCEPT (t);
1475 tmpl = DECL_TI_TEMPLATE (decl);
1476 args = CHECK_CONSTR_ARGS (t);
1483 /* Returns true iff the placeholders C1 and C2 are equivalent. C1
1484 and C2 can be either CHECK_CONSTR or TEMPLATE_TYPE_PARM. */
1487 equivalent_placeholder_constraints (tree c1, tree c2)
1489 if (c1 && TREE_CODE (c1) == TEMPLATE_TYPE_PARM)
1490 /* A constrained auto. */
1491 c1 = PLACEHOLDER_TYPE_CONSTRAINTS (c1);
1492 if (c2 && TREE_CODE (c2) == TEMPLATE_TYPE_PARM)
1493 c2 = PLACEHOLDER_TYPE_CONSTRAINTS (c2);
1499 if (c1 == error_mark_node || c2 == error_mark_node)
1500 /* We get here during satisfaction; when a deduction constraint
1501 fails, substitution can produce an error_mark_node for the
1502 placeholder constraints. */
1505 tree t1, t2, a1, a2;
1506 placeholder_extract_concept_and_args (c1, t1, a1);
1507 placeholder_extract_concept_and_args (c2, t2, a2);
1512 int len1 = TREE_VEC_LENGTH (a1);
1513 int len2 = TREE_VEC_LENGTH (a2);
1517 /* Skip the first argument so we don't infinitely recurse.
1518 Also, they may differ in template parameter index. */
1519 for (int i = 1; i < len1; ++i)
1521 tree t1 = TREE_VEC_ELT (a1, i);
1522 tree t2 = TREE_VEC_ELT (a2, i);
1523 if (!template_args_equal (t1, t2))
1529 /* Return a hash value for the placeholder PRED_CONSTR C. */
1532 hash_placeholder_constraint (tree c)
1535 placeholder_extract_concept_and_args (c, t, a);
1537 /* Like hash_tmpl_and_args, but skip the first argument. */
1538 hashval_t val = iterative_hash_object (DECL_UID (t), 0);
1540 for (int i = TREE_VEC_LENGTH (a)-1; i > 0; --i)
1541 val = iterative_hash_template_arg (TREE_VEC_ELT (a, i), val);
1546 /*---------------------------------------------------------------------------
1547 Constraint substitution
1548 ---------------------------------------------------------------------------*/
1550 /* The following functions implement substitution rules for constraints.
1551 Substitution without checking constraints happens only in the
1552 instantiation of class templates. For example:
1554 template<C1 T> struct S {
1555 void f(T) requires C2<T>;
1556 void g(T) requires T::value;
1559 S<int> s; // error instantiating S<int>::g(T)
1561 When we instantiate S, we substitute into its member declarations,
1562 including their constraints. However, those constraints are not
1563 checked. Substituting int into C2<T> yields C2<int>, and substituting
1564 into T::value yields a substitution failure, making the program
1567 Note that we only ever substitute into the associated constraints
1568 of a declaration. That is, substitution is defined only for predicate
1569 constraints and conjunctions. */
1571 /* Substitute into the predicate constraints. Returns error_mark_node
1572 if the substitution into the expression fails. */
1574 tsubst_predicate_constraint (tree t, tree args,
1575 tsubst_flags_t complain, tree in_decl)
1577 tree expr = PRED_CONSTR_EXPR (t);
1578 ++processing_template_decl;
1579 tree result = tsubst_expr (expr, args, complain, in_decl, false);
1580 --processing_template_decl;
1581 return build_nt (PRED_CONSTR, result);
1584 /* Substitute into a check constraint. */
1587 tsubst_check_constraint (tree t, tree args,
1588 tsubst_flags_t complain, tree in_decl)
1590 tree decl = CHECK_CONSTR_CONCEPT (t);
1591 tree tmpl = DECL_TI_TEMPLATE (decl);
1592 tree targs = CHECK_CONSTR_ARGS (t);
1594 /* Substitute through by building an template-id expression
1595 and then substituting into that. */
1596 tree expr = build_nt(TEMPLATE_ID_EXPR, tmpl, targs);
1597 ++processing_template_decl;
1598 tree result = tsubst_expr (expr, args, complain, in_decl, false);
1599 --processing_template_decl;
1601 if (result == error_mark_node)
1602 return error_mark_node;
1604 /* Extract the results and rebuild the check constraint. */
1605 decl = DECL_TEMPLATE_RESULT (TREE_OPERAND (result, 0));
1606 args = TREE_OPERAND (result, 1);
1608 return build_nt (CHECK_CONSTR, decl, args);
1611 /* Substitute into the conjunction of constraints. Returns
1612 error_mark_node if substitution into either operand fails. */
1615 tsubst_logical_operator (tree t, tree args,
1616 tsubst_flags_t complain, tree in_decl)
1618 tree t0 = TREE_OPERAND (t, 0);
1619 tree r0 = tsubst_constraint (t0, args, complain, in_decl);
1620 if (r0 == error_mark_node)
1621 return error_mark_node;
1622 tree t1 = TREE_OPERAND (t, 1);
1623 tree r1 = tsubst_constraint (t1, args, complain, in_decl);
1624 if (r1 == error_mark_node)
1625 return error_mark_node;
1626 return build_nt (TREE_CODE (t), r0, r1);
1631 /* Substitute ARGS into the expression constraint T. */
1634 tsubst_expr_constr (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1636 cp_unevaluated guard;
1637 tree expr = EXPR_CONSTR_EXPR (t);
1638 tree ret = tsubst_expr (expr, args, complain, in_decl, false);
1639 if (ret == error_mark_node)
1640 return error_mark_node;
1641 return build_nt (EXPR_CONSTR, ret);
1644 /* Substitute ARGS into the type constraint T. */
1647 tsubst_type_constr (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1649 tree type = TYPE_CONSTR_TYPE (t);
1650 tree ret = tsubst (type, args, complain, in_decl);
1651 if (ret == error_mark_node)
1652 return error_mark_node;
1653 return build_nt (TYPE_CONSTR, ret);
1656 /* Substitute ARGS into the implicit conversion constraint T. */
1659 tsubst_implicit_conversion_constr (tree t, tree args, tsubst_flags_t complain,
1662 cp_unevaluated guard;
1663 tree expr = ICONV_CONSTR_EXPR (t);
1664 tree type = ICONV_CONSTR_TYPE (t);
1665 tree new_expr = tsubst_expr (expr, args, complain, in_decl, false);
1666 if (new_expr == error_mark_node)
1667 return error_mark_node;
1668 tree new_type = tsubst (type, args, complain, in_decl);
1669 if (new_type == error_mark_node)
1670 return error_mark_node;
1671 return build_nt (ICONV_CONSTR, new_expr, new_type);
1674 /* Substitute ARGS into the argument deduction constraint T. */
1677 tsubst_argument_deduction_constr (tree t, tree args, tsubst_flags_t complain,
1680 cp_unevaluated guard;
1681 tree expr = DEDUCT_CONSTR_EXPR (t);
1682 tree pattern = DEDUCT_CONSTR_PATTERN (t);
1683 tree autos = DEDUCT_CONSTR_PLACEHOLDER(t);
1684 tree new_expr = tsubst_expr (expr, args, complain, in_decl, false);
1685 if (new_expr == error_mark_node)
1686 return error_mark_node;
1687 /* It seems like substituting through the pattern will not affect the
1688 placeholders. We should (?) be able to reuse the existing list
1689 without any problems. If not, then we probably want to create a
1690 new list of placeholders and then instantiate the pattern using
1692 tree new_pattern = tsubst (pattern, args, complain, in_decl);
1693 if (new_pattern == error_mark_node)
1694 return error_mark_node;
1695 return build_nt (DEDUCT_CONSTR, new_expr, new_pattern, autos);
1698 /* Substitute ARGS into the exception constraint T. */
1701 tsubst_exception_constr (tree t, tree args, tsubst_flags_t complain,
1704 cp_unevaluated guard;
1705 tree expr = EXCEPT_CONSTR_EXPR (t);
1706 tree ret = tsubst_expr (expr, args, complain, in_decl, false);
1707 if (ret == error_mark_node)
1708 return error_mark_node;
1709 return build_nt (EXCEPT_CONSTR, ret);
1712 /* A subroutine of tsubst_constraint_variables. Register local
1713 specializations for each of parameter in PARMS and its
1714 corresponding substituted constraint variable in VARS.
1718 declare_constraint_vars (tree parms, tree vars)
1721 for (tree t = parms; t; t = DECL_CHAIN (t))
1723 if (DECL_PACK_P (t))
1725 tree pack = extract_fnparm_pack (t, &s);
1726 register_local_specialization (pack, t);
1730 register_local_specialization (s, t);
1737 /* A subroutine of tsubst_parameterized_constraint. Substitute ARGS
1738 into the parameter list T, producing a sequence of constraint
1739 variables, declared in the current scope.
1741 Note that the caller must establish a local specialization stack
1742 prior to calling this function since this substitution will
1743 declare the substituted parameters. */
1746 tsubst_constraint_variables (tree t, tree args,
1747 tsubst_flags_t complain, tree in_decl)
1749 /* Clear cp_unevaluated_operand across tsubst so that we get a proper chain
1751 int saved_unevaluated_operand = cp_unevaluated_operand;
1752 cp_unevaluated_operand = 0;
1753 tree vars = tsubst (t, args, complain, in_decl);
1754 cp_unevaluated_operand = saved_unevaluated_operand;
1755 if (vars == error_mark_node)
1756 return error_mark_node;
1757 return declare_constraint_vars (t, vars);
1760 /* Substitute ARGS into the parameterized constraint T. */
1763 tsubst_parameterized_constraint (tree t, tree args,
1764 tsubst_flags_t complain, tree in_decl)
1766 local_specialization_stack stack;
1767 tree vars = tsubst_constraint_variables (PARM_CONSTR_PARMS (t),
1768 args, complain, in_decl);
1769 if (vars == error_mark_node)
1770 return error_mark_node;
1771 tree expr = tsubst_constraint (PARM_CONSTR_OPERAND (t), args,
1773 if (expr == error_mark_node)
1774 return error_mark_node;
1775 return build_nt (PARM_CONSTR, vars, expr);
1778 /* Substitute ARGS into the simple requirement T. Note that
1779 substitution may result in an ill-formed expression without
1780 causing the program to be ill-formed. In such cases, the
1781 requirement wraps an error_mark_node. */
1784 tsubst_simple_requirement (tree t, tree args,
1785 tsubst_flags_t complain, tree in_decl)
1787 ++processing_template_decl;
1788 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1789 --processing_template_decl;
1790 return finish_simple_requirement (expr);
1793 /* Substitute ARGS into the type requirement T. Note that
1794 substitution may result in an ill-formed type without
1795 causing the program to be ill-formed. In such cases, the
1796 requirement wraps an error_mark_node. */
1799 tsubst_type_requirement (tree t, tree args,
1800 tsubst_flags_t complain, tree in_decl)
1802 ++processing_template_decl;
1803 tree type = tsubst (TREE_OPERAND (t, 0), args, complain, in_decl);
1804 --processing_template_decl;
1805 return finish_type_requirement (type);
1808 /* Substitute args into the compound requirement T. If substituting
1809 into either the expression or the type fails, the corresponding
1810 operands in the resulting node will be error_mark_node. This
1811 preserves a requirement for the purpose of partial ordering, but
1812 it will never be satisfied. */
1815 tsubst_compound_requirement (tree t, tree args,
1816 tsubst_flags_t complain, tree in_decl)
1818 ++processing_template_decl;
1819 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1820 tree type = tsubst (TREE_OPERAND (t, 1), args, complain, in_decl);
1821 --processing_template_decl;
1822 bool noexcept_p = COMPOUND_REQ_NOEXCEPT_P (t);
1823 return finish_compound_requirement (expr, type, noexcept_p);
1826 /* Substitute ARGS into the nested requirement T. */
1829 tsubst_nested_requirement (tree t, tree args,
1830 tsubst_flags_t complain, tree in_decl)
1832 ++processing_template_decl;
1833 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1834 --processing_template_decl;
1835 return finish_nested_requirement (expr);
1838 /* Substitute ARGS into the requirement T. */
1841 tsubst_requirement (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1843 switch (TREE_CODE (t))
1846 return tsubst_simple_requirement (t, args, complain, in_decl);
1848 return tsubst_type_requirement (t, args, complain, in_decl);
1850 return tsubst_compound_requirement (t, args, complain, in_decl);
1852 return tsubst_nested_requirement (t, args, complain, in_decl);
1856 return error_mark_node;
1859 /* Substitute ARGS into the list of requirements T. Note that
1860 substitution failures here result in ill-formed programs. */
1863 tsubst_requirement_body (tree t, tree args,
1864 tsubst_flags_t complain, tree in_decl)
1869 tree e = tsubst_requirement (TREE_VALUE (t), args, complain, in_decl);
1870 if (e == error_mark_node)
1871 return error_mark_node;
1872 r = tree_cons (NULL_TREE, e, r);
1875 /* Ensure that the order of constraints is the same as the original. */
1876 return nreverse (r);
1881 /* Substitute ARGS into the requires expression T. Note that this
1882 results in the re-declaration of local parameters when
1883 substituting through the parameter list. If either substitution
1884 fails, the program is ill-formed. */
1887 tsubst_requires_expr (tree t, tree args,
1888 tsubst_flags_t complain, tree in_decl)
1890 local_specialization_stack stack;
1892 tree parms = TREE_OPERAND (t, 0);
1895 parms = tsubst_constraint_variables (parms, args, complain, in_decl);
1896 if (parms == error_mark_node)
1897 return error_mark_node;
1900 tree reqs = TREE_OPERAND (t, 1);
1901 reqs = tsubst_requirement_body (reqs, args, complain, in_decl);
1902 if (reqs == error_mark_node)
1903 return error_mark_node;
1905 return finish_requires_expr (parms, reqs);
1908 /* Substitute ARGS into the constraint information CI, producing a new
1909 constraint record. */
1912 tsubst_constraint_info (tree t, tree args,
1913 tsubst_flags_t complain, tree in_decl)
1915 if (!t || t == error_mark_node || !check_constraint_info (t))
1918 tree tmpl_constr = NULL_TREE;
1919 if (tree r = CI_TEMPLATE_REQS (t))
1920 tmpl_constr = tsubst_constraint (r, args, complain, in_decl);
1922 tree decl_constr = NULL_TREE;
1923 if (tree r = CI_DECLARATOR_REQS (t))
1924 decl_constr = tsubst_constraint (r, args, complain, in_decl);
1926 return build_constraints (tmpl_constr, decl_constr);
1929 /* Substitute ARGS into the constraint T. */
1932 tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1936 switch (TREE_CODE (t))
1939 return tsubst_predicate_constraint (t, args, complain, in_decl);
1941 return tsubst_check_constraint (t, args, complain, in_decl);
1944 return tsubst_logical_operator (t, args, complain, in_decl);
1946 return tsubst_parameterized_constraint (t, args, complain, in_decl);
1948 return tsubst_expr_constr (t, args, complain, in_decl);
1950 return tsubst_type_constr (t, args, complain, in_decl);
1952 return tsubst_implicit_conversion_constr (t, args, complain, in_decl);
1954 return tsubst_argument_deduction_constr (t, args, complain, in_decl);
1956 return tsubst_exception_constr (t, args, complain, in_decl);
1960 return error_mark_node;
1963 /*---------------------------------------------------------------------------
1964 Constraint satisfaction
1965 ---------------------------------------------------------------------------*/
1967 /* The following functions determine if a constraint, when
1968 substituting template arguments, is satisfied. For convenience,
1969 satisfaction reduces a constraint to either true or false (and
1974 tree satisfy_constraint_1 (tree, tree, tsubst_flags_t, tree);
1976 /* Check the constraint pack expansion. */
1979 satisfy_pack_expansion (tree t, tree args,
1980 tsubst_flags_t complain, tree in_decl)
1982 /* Get the vector of satisfaction results.
1983 gen_elem_of_pack_expansion_instantiation will check that each element of
1984 the expansion is satisfied. */
1985 tree exprs = tsubst_pack_expansion (t, args, complain, in_decl);
1987 if (exprs == error_mark_node)
1988 return boolean_false_node;
1990 /* TODO: It might be better to normalize each expanded term
1991 and evaluate them separately. That would provide better
1992 opportunities for diagnostics. */
1993 for (int i = 0; i < TREE_VEC_LENGTH (exprs); ++i)
1994 if (TREE_VEC_ELT (exprs, i) != boolean_true_node)
1995 return boolean_false_node;
1996 return boolean_true_node;
1999 /* A predicate constraint is satisfied if its expression evaluates
2000 to true. If substitution into that node fails, the constraint
2001 is not satisfied ([temp.constr.pred]).
2003 Note that a predicate constraint is a constraint expression
2004 of type bool. If neither of those are true, the program is
2005 ill-formed; they are not SFINAE'able errors. */
2008 satisfy_predicate_constraint (tree t, tree args,
2009 tsubst_flags_t complain, tree in_decl)
2011 tree expr = TREE_OPERAND (t, 0);
2013 /* We should never have a naked pack expansion in a predicate constraint. */
2014 gcc_assert (TREE_CODE (expr) != EXPR_PACK_EXPANSION);
2016 /* If substitution into the expression fails, the constraint
2017 is not satisfied. */
2018 expr = tsubst_expr (expr, args, complain, in_decl, false);
2019 if (expr == error_mark_node)
2020 return boolean_false_node;
2022 /* A predicate constraint shall have type bool. In some
2023 cases, substitution gives us const-qualified bool, which
2024 is also acceptable. */
2025 tree type = cv_unqualified (TREE_TYPE (expr));
2026 if (!same_type_p (type, boolean_type_node))
2028 error_at (EXPR_LOC_OR_LOC (expr, input_location),
2029 "constraint %qE does not have type %qT",
2030 expr, boolean_type_node);
2031 return boolean_false_node;
2034 return cxx_constant_value (expr);
2037 /* A concept check constraint like C<CARGS> is satisfied if substituting ARGS
2038 into CARGS succeeds and C is satisfied for the resulting arguments. */
2041 satisfy_check_constraint (tree t, tree args,
2042 tsubst_flags_t complain, tree in_decl)
2044 tree decl = CHECK_CONSTR_CONCEPT (t);
2045 tree tmpl = DECL_TI_TEMPLATE (decl);
2046 tree cargs = CHECK_CONSTR_ARGS (t);
2048 /* Instantiate the concept check arguments. */
2049 tree targs = tsubst (cargs, args, tf_none, NULL_TREE);
2050 if (targs == error_mark_node)
2051 return boolean_false_node;
2053 /* Search for a previous value. */
2054 if (tree prev = lookup_concept_satisfaction (tmpl, targs))
2057 /* Expand the concept; failure here implies non-satisfaction. */
2058 tree def = expand_concept (decl, targs);
2059 if (def == error_mark_node)
2060 return memoize_concept_satisfaction (tmpl, args, boolean_false_node);
2062 /* Recursively satisfy the constraint. */
2063 tree result = satisfy_constraint_1 (def, targs, complain, in_decl);
2064 return memoize_concept_satisfaction (tmpl, targs, result);
2067 /* Check an expression constraint. The constraint is satisfied if
2068 substitution succeeds ([temp.constr.expr]).
2070 Note that the expression is unevaluated. */
2073 satisfy_expression_constraint (tree t, tree args,
2074 tsubst_flags_t complain, tree in_decl)
2076 cp_unevaluated guard;
2077 deferring_access_check_sentinel deferring;
2079 tree expr = EXPR_CONSTR_EXPR (t);
2080 tree check = tsubst_expr (expr, args, complain, in_decl, false);
2081 if (check == error_mark_node)
2082 return boolean_false_node;
2083 if (!perform_deferred_access_checks (tf_none))
2084 return boolean_false_node;
2085 return boolean_true_node;
2088 /* Check a type constraint. The constraint is satisfied if
2089 substitution succeeds. */
2092 satisfy_type_constraint (tree t, tree args,
2093 tsubst_flags_t complain, tree in_decl)
2095 deferring_access_check_sentinel deferring;
2096 tree type = TYPE_CONSTR_TYPE (t);
2097 gcc_assert (TYPE_P (type) || type == error_mark_node);
2098 tree check = tsubst (type, args, complain, in_decl);
2099 if (error_operand_p (check))
2100 return boolean_false_node;
2101 if (!perform_deferred_access_checks (complain))
2102 return boolean_false_node;
2103 return boolean_true_node;
2106 /* Check an implicit conversion constraint. */
2109 satisfy_implicit_conversion_constraint (tree t, tree args,
2110 tsubst_flags_t complain, tree in_decl)
2112 /* Don't tsubst as if we're processing a template. If we try
2113 to we can end up generating template-like expressions
2114 (e.g., modop-exprs) that aren't properly typed. */
2116 tsubst_expr (ICONV_CONSTR_EXPR (t), args, complain, in_decl, false);
2117 if (expr == error_mark_node)
2118 return boolean_false_node;
2120 /* Get the transformed target type. */
2121 tree type = tsubst (ICONV_CONSTR_TYPE (t), args, complain, in_decl);
2122 if (type == error_mark_node)
2123 return boolean_false_node;
2125 /* Attempt the conversion as a direct initialization
2126 of the form TYPE <unspecified> = EXPR. */
2128 perform_direct_initialization_if_possible (type, expr, false, complain);
2129 if (conv == NULL_TREE || conv == error_mark_node)
2130 return boolean_false_node;
2132 return boolean_true_node;
2135 /* Check an argument deduction constraint. */
2138 satisfy_argument_deduction_constraint (tree t, tree args,
2139 tsubst_flags_t complain, tree in_decl)
2141 /* Substitute through the expression. */
2142 tree expr = DEDUCT_CONSTR_EXPR (t);
2143 tree init = tsubst_expr (expr, args, complain, in_decl, false);
2144 if (expr == error_mark_node)
2145 return boolean_false_node;
2147 /* Perform auto or decltype(auto) deduction to get the result. */
2148 tree pattern = DEDUCT_CONSTR_PATTERN (t);
2149 tree placeholder = DEDUCT_CONSTR_PLACEHOLDER (t);
2150 tree constr = PLACEHOLDER_TYPE_CONSTRAINTS (placeholder);
2151 tree type_canonical = TYPE_CANONICAL (placeholder);
2152 PLACEHOLDER_TYPE_CONSTRAINTS (placeholder)
2153 = tsubst_constraint (constr, args, complain|tf_partial, in_decl);
2154 TYPE_CANONICAL (placeholder) = NULL_TREE;
2155 tree type = do_auto_deduction (pattern, init, placeholder,
2156 complain, adc_requirement);
2157 PLACEHOLDER_TYPE_CONSTRAINTS (placeholder) = constr;
2158 TYPE_CANONICAL (placeholder) = type_canonical;
2159 if (type == error_mark_node)
2160 return boolean_false_node;
2162 return boolean_true_node;
2165 /* Check an exception constraint. An exception constraint for an
2166 expression e is satisfied when noexcept(e) is true. */
2169 satisfy_exception_constraint (tree t, tree args,
2170 tsubst_flags_t complain, tree in_decl)
2172 tree expr = EXCEPT_CONSTR_EXPR (t);
2173 tree check = tsubst_expr (expr, args, complain, in_decl, false);
2174 if (check == error_mark_node)
2175 return boolean_false_node;
2177 if (expr_noexcept_p (check, complain))
2178 return boolean_true_node;
2180 return boolean_false_node;
2183 /* Check a parameterized constraint. */
2186 satisfy_parameterized_constraint (tree t, tree args,
2187 tsubst_flags_t complain, tree in_decl)
2189 local_specialization_stack stack;
2190 tree parms = PARM_CONSTR_PARMS (t);
2191 tree vars = tsubst_constraint_variables (parms, args, complain, in_decl);
2192 if (vars == error_mark_node)
2193 return boolean_false_node;
2194 tree constr = PARM_CONSTR_OPERAND (t);
2195 return satisfy_constraint_1 (constr, args, complain, in_decl);
2198 /* Check that the conjunction of constraints is satisfied. Note
2199 that if left operand is not satisfied, the right operand
2202 FIXME: Check that this wouldn't result in a user-defined
2203 operator. Note that this error is partially diagnosed in
2204 satisfy_predicate_constraint. It would be nice to diagnose
2205 the overload, but I don't think it's strictly necessary. */
2208 satisfy_conjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2210 tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl);
2211 if (t0 == boolean_false_node)
2212 return boolean_false_node;
2213 return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
2216 /* Check that the disjunction of constraints is satisfied. Note
2217 that if the left operand is satisfied, the right operand is not
2221 satisfy_disjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2223 tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl);
2224 if (t0 == boolean_true_node)
2225 return boolean_true_node;
2226 return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
2229 /* Dispatch to an appropriate satisfaction routine depending on the
2233 satisfy_constraint_1 (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2235 gcc_assert (!processing_template_decl);
2238 return boolean_false_node;
2240 if (t == error_mark_node)
2241 return boolean_false_node;
2243 switch (TREE_CODE (t))
2246 return satisfy_predicate_constraint (t, args, complain, in_decl);
2249 return satisfy_check_constraint (t, args, complain, in_decl);
2252 return satisfy_expression_constraint (t, args, complain, in_decl);
2255 return satisfy_type_constraint (t, args, complain, in_decl);
2258 return satisfy_implicit_conversion_constraint (t, args, complain, in_decl);
2261 return satisfy_argument_deduction_constraint (t, args, complain, in_decl);
2264 return satisfy_exception_constraint (t, args, complain, in_decl);
2267 return satisfy_parameterized_constraint (t, args, complain, in_decl);
2270 return satisfy_conjunction (t, args, complain, in_decl);
2273 return satisfy_disjunction (t, args, complain, in_decl);
2275 case EXPR_PACK_EXPANSION:
2276 return satisfy_pack_expansion (t, args, complain, in_decl);
2281 return boolean_false_node;
2284 /* Check that the constraint is satisfied, according to the rules
2285 for that constraint. Note that each satisfy_* function returns
2286 true or false, depending on whether it is satisfied or not. */
2289 satisfy_constraint (tree t, tree args)
2291 auto_timevar time (TV_CONSTRAINT_SAT);
2293 /* Turn off template processing. Constraint satisfaction only applies
2294 to non-dependent terms, so we want to ensure full checking here. */
2295 processing_template_decl_sentinel proc (true);
2297 /* Avoid early exit in tsubst and tsubst_copy from null args; since earlier
2298 substitution was done with processing_template_decl forced on, there will
2299 be expressions that still need semantic processing, possibly buried in
2300 decltype or a template argument. */
2301 if (args == NULL_TREE)
2302 args = make_tree_vec (1);
2304 return satisfy_constraint_1 (t, args, tf_none, NULL_TREE);
2307 /* Check the associated constraints in CI against the given
2308 ARGS, returning true when the constraints are satisfied
2309 and false otherwise. */
2312 satisfy_associated_constraints (tree ci, tree args)
2314 /* If there are no constraints then this is trivially satisfied. */
2316 return boolean_true_node;
2318 /* If any arguments depend on template parameters, we can't
2319 check constraints. */
2320 if (args && uses_template_parms (args))
2321 return boolean_true_node;
2323 /* Check if we've seen a previous result. */
2324 if (tree prev = lookup_constraint_satisfaction (ci, args))
2327 /* Actually test for satisfaction. */
2328 tree result = satisfy_constraint (CI_ASSOCIATED_CONSTRAINTS (ci), args);
2329 return memoize_constraint_satisfaction (ci, args, result);
2334 /* Evaluate the given constraint, returning boolean_true_node
2335 if the constraint is satisfied and boolean_false_node
2339 evaluate_constraints (tree constr, tree args)
2341 gcc_assert (constraint_p (constr));
2342 return satisfy_constraint (constr, args);
2345 /* Evaluate the function concept FN by substituting its own args
2346 into its definition and evaluating that as the result. Returns
2347 boolean_true_node if the constraints are satisfied and
2348 boolean_false_node otherwise. */
2351 evaluate_function_concept (tree fn, tree args)
2353 tree constr = build_nt (CHECK_CONSTR, fn, args);
2354 return satisfy_constraint (constr, args);
2357 /* Evaluate the variable concept VAR by substituting its own args into
2358 its initializer and checking the resulting constraint. Returns
2359 boolean_true_node if the constraints are satisfied and
2360 boolean_false_node otherwise. */
2363 evaluate_variable_concept (tree var, tree args)
2365 tree constr = build_nt (CHECK_CONSTR, var, args);
2366 return satisfy_constraint (constr, args);
2369 /* Evaluate the given expression as if it were a predicate
2370 constraint. Returns boolean_true_node if the constraint
2371 is satisfied and boolean_false_node otherwise. */
2374 evaluate_constraint_expression (tree expr, tree args)
2376 tree constr = normalize_expression (expr);
2377 return satisfy_constraint (constr, args);
2380 /* Returns true if the DECL's constraints are satisfied.
2381 This is used in cases where a declaration is formed but
2382 before it is used (e.g., overload resolution). */
2385 constraints_satisfied_p (tree decl)
2387 /* Get the constraints to check for satisfaction. This depends
2388 on whether we're looking at a template specialization or not. */
2390 tree args = NULL_TREE;
2391 if (tree ti = DECL_TEMPLATE_INFO (decl))
2393 ci = get_constraints (TI_TEMPLATE (ti));
2394 args = INNERMOST_TEMPLATE_ARGS (TI_ARGS (ti));
2398 ci = get_constraints (decl);
2401 tree eval = satisfy_associated_constraints (ci, args);
2402 return eval == boolean_true_node;
2405 /* Returns true if the constraints are satisfied by ARGS.
2406 Here, T can be either a constraint or a constrained
2410 constraints_satisfied_p (tree t, tree args)
2413 if (constraint_p (t))
2414 eval = evaluate_constraints (t, args);
2416 eval = satisfy_associated_constraints (get_constraints (t), args);
2417 return eval == boolean_true_node;
2423 /* Normalize EXPR and determine if the resulting constraint is
2424 satisfied by ARGS. Returns true if and only if the constraint
2425 is satisfied. This is used extensively by diagnostics to
2426 determine causes for failure. */
2429 constraint_expression_satisfied_p (tree expr, tree args)
2431 return evaluate_constraint_expression (expr, args) == boolean_true_node;
2436 /*---------------------------------------------------------------------------
2437 Semantic analysis of requires-expressions
2438 ---------------------------------------------------------------------------*/
2440 /* Finish a requires expression for the given PARMS (possibly
2441 null) and the non-empty sequence of requirements. */
2443 finish_requires_expr (tree parms, tree reqs)
2445 /* Modify the declared parameters by removing their context
2446 so they don't refer to the enclosing scope and explicitly
2447 indicating that they are constraint variables. */
2448 for (tree parm = parms; parm; parm = DECL_CHAIN (parm))
2450 DECL_CONTEXT (parm) = NULL_TREE;
2451 CONSTRAINT_VAR_P (parm) = true;
2454 /* Build the node. */
2455 tree r = build_min (REQUIRES_EXPR, boolean_type_node, parms, reqs);
2456 TREE_SIDE_EFFECTS (r) = false;
2457 TREE_CONSTANT (r) = true;
2461 /* Construct a requirement for the validity of EXPR. */
2463 finish_simple_requirement (tree expr)
2465 return build_nt (SIMPLE_REQ, expr);
2468 /* Construct a requirement for the validity of TYPE. */
2470 finish_type_requirement (tree type)
2472 return build_nt (TYPE_REQ, type);
2475 /* Construct a requirement for the validity of EXPR, along with
2476 its properties. if TYPE is non-null, then it specifies either
2477 an implicit conversion or argument deduction constraint,
2478 depending on whether any placeholders occur in the type name.
2479 NOEXCEPT_P is true iff the noexcept keyword was specified. */
2481 finish_compound_requirement (tree expr, tree type, bool noexcept_p)
2483 tree req = build_nt (COMPOUND_REQ, expr, type);
2484 COMPOUND_REQ_NOEXCEPT_P (req) = noexcept_p;
2488 /* Finish a nested requirement. */
2490 finish_nested_requirement (tree expr)
2492 return build_nt (NESTED_REQ, expr);
2495 // Check that FN satisfies the structural requirements of a
2496 // function concept definition.
2498 check_function_concept (tree fn)
2500 // Check that the function is comprised of only a single
2501 // return statement.
2502 tree body = DECL_SAVED_TREE (fn);
2503 if (TREE_CODE (body) == BIND_EXPR)
2504 body = BIND_EXPR_BODY (body);
2506 // Sometimes a function call results in the creation of clean up
2507 // points. Allow these to be preserved in the body of the
2508 // constraint, as we might actually need them for some constexpr
2510 if (TREE_CODE (body) == CLEANUP_POINT_EXPR)
2511 body = TREE_OPERAND (body, 0);
2513 // We need to cut the STATEMENT_LIST_END before the check.
2514 if (TREE_CODE (body) == STATEMENT_LIST &&
2515 TREE_CODE (STATEMENT_LIST_TAIL (body)->stmt) == STATEMENT_LIST_END)
2517 tree_stmt_iterator i = tsi_last (body);
2521 /* Check that the definition is written correctly. */
2522 if (TREE_CODE (body) != RETURN_EXPR)
2524 location_t loc = DECL_SOURCE_LOCATION (fn);
2525 if (TREE_CODE (body) == STATEMENT_LIST && !STATEMENT_LIST_HEAD (body))
2526 error_at (loc, "definition of concept %qD is empty", fn);
2528 error_at (loc, "definition of concept %qD has multiple statements", fn);
2535 // Check that a constrained friend declaration function declaration,
2536 // FN, is admissible. This is the case only when the declaration depends
2537 // on template parameters and does not declare a specialization.
2539 check_constrained_friend (tree fn, tree reqs)
2541 if (fn == error_mark_node)
2543 gcc_assert (TREE_CODE (fn) == FUNCTION_DECL);
2545 // If there are not constraints, this cannot be an error.
2549 // Constrained friend functions that don't depend on template
2550 // arguments are effectively meaningless.
2551 if (!uses_template_parms (TREE_TYPE (fn)))
2553 error_at (location_of (fn),
2554 "constrained friend does not depend on template parameters");
2559 /*---------------------------------------------------------------------------
2560 Equivalence of constraints
2561 ---------------------------------------------------------------------------*/
2563 /* Returns true when A and B are equivalent constraints. */
2565 equivalent_constraints (tree a, tree b)
2567 gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
2568 gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
2569 return cp_tree_equal (a, b);
2572 /* Returns true if the template declarations A and B have equivalent
2573 constraints. This is the case when A's constraints subsume B's and
2574 when B's also constrain A's. */
2576 equivalently_constrained (tree d1, tree d2)
2578 gcc_assert (TREE_CODE (d1) == TREE_CODE (d2));
2579 return equivalent_constraints (get_constraints (d1), get_constraints (d2));
2582 /*---------------------------------------------------------------------------
2583 Partial ordering of constraints
2584 ---------------------------------------------------------------------------*/
2586 /* Returns true when the the constraints in A subsume those in B. */
2589 subsumes_constraints (tree a, tree b)
2591 gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
2592 gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
2593 return subsumes (a, b);
2596 /* Returns true when the the constraints in A subsume those in B, but
2597 the constraints in B do not subsume the constraints in A. */
2600 strictly_subsumes (tree a, tree b)
2602 return subsumes (a, b) && !subsumes (b, a);
2605 /* Determines which of the declarations, A or B, is more constrained.
2606 That is, which declaration's constraints subsume but are not subsumed
2609 Returns 1 if A is more constrained than B, -1 if B is more constrained
2610 than A, and 0 otherwise. */
2613 more_constrained (tree d1, tree d2)
2615 tree c1 = get_constraints (d1);
2616 tree c2 = get_constraints (d2);
2618 if (subsumes_constraints (c1, c2))
2620 if (subsumes_constraints (c2, c1))
2625 /* Returns true if D1 is at least as constrained as D2. That is, the
2626 associated constraints of D1 subsume those of D2, or both declarations
2627 are unconstrained. */
2630 at_least_as_constrained (tree d1, tree d2)
2632 tree c1 = get_constraints (d1);
2633 tree c2 = get_constraints (d2);
2634 return subsumes_constraints (c1, c2);
2638 /*---------------------------------------------------------------------------
2639 Constraint diagnostics
2641 FIXME: Normalize expressions into constraints before evaluating them.
2642 This should be the general pattern for all such diagnostics.
2643 ---------------------------------------------------------------------------*/
2645 /* The number of detailed constraint failures. */
2647 int constraint_errors = 0;
2649 /* Do not generate errors after diagnosing this number of constraint
2652 FIXME: This is a really arbitrary number. Provide better control of
2653 constraint diagnostics with a command line option. */
2655 int constraint_thresh = 20;
2658 /* Returns true if we should elide the diagnostic for a constraint failure.
2659 This is the case when the number of errors has exceeded the pre-configured
2663 elide_constraint_failure_p ()
2665 bool ret = constraint_thresh <= constraint_errors;
2666 ++constraint_errors;
2670 /* Returns the number of undiagnosed errors. */
2673 undiagnosed_constraint_failures ()
2675 return constraint_errors - constraint_thresh;
2678 /* The diagnosis of constraints performs a combination of normalization
2679 and satisfaction testing. We recursively walk through the conjunction or
2680 disjunction of associated constraints, testing each sub-constraint in
2685 void diagnose_constraint (location_t, tree, tree, tree);
2687 /* Emit a specific diagnostics for a failed trait. */
2690 diagnose_trait_expression (location_t loc, tree, tree cur, tree args)
2692 if (constraint_expression_satisfied_p (cur, args))
2694 if (elide_constraint_failure_p())
2697 tree expr = PRED_CONSTR_EXPR (cur);
2698 ++processing_template_decl;
2699 expr = tsubst_expr (expr, args, tf_none, NULL_TREE, false);
2700 --processing_template_decl;
2702 tree t1 = TRAIT_EXPR_TYPE1 (expr);
2703 tree t2 = TRAIT_EXPR_TYPE2 (expr);
2704 switch (TRAIT_EXPR_KIND (expr))
2706 case CPTK_HAS_NOTHROW_ASSIGN:
2707 inform (loc, " %qT is not nothrow copy assignable", t1);
2709 case CPTK_HAS_NOTHROW_CONSTRUCTOR:
2710 inform (loc, " %qT is not nothrow default constructible", t1);
2712 case CPTK_HAS_NOTHROW_COPY:
2713 inform (loc, " %qT is not nothrow copy constructible", t1);
2715 case CPTK_HAS_TRIVIAL_ASSIGN:
2716 inform (loc, " %qT is not trivially copy assignable", t1);
2718 case CPTK_HAS_TRIVIAL_CONSTRUCTOR:
2719 inform (loc, " %qT is not trivially default constructible", t1);
2721 case CPTK_HAS_TRIVIAL_COPY:
2722 inform (loc, " %qT is not trivially copy constructible", t1);
2724 case CPTK_HAS_TRIVIAL_DESTRUCTOR:
2725 inform (loc, " %qT is not trivially destructible", t1);
2727 case CPTK_HAS_VIRTUAL_DESTRUCTOR:
2728 inform (loc, " %qT does not have a virtual destructor", t1);
2730 case CPTK_IS_ABSTRACT:
2731 inform (loc, " %qT is not an abstract class", t1);
2733 case CPTK_IS_BASE_OF:
2734 inform (loc, " %qT is not a base of %qT", t1, t2);
2737 inform (loc, " %qT is not a class", t1);
2740 inform (loc, " %qT is not an empty class", t1);
2743 inform (loc, " %qT is not an enum", t1);
2746 inform (loc, " %qT is not a final class", t1);
2748 case CPTK_IS_LITERAL_TYPE:
2749 inform (loc, " %qT is not a literal type", t1);
2752 inform (loc, " %qT is not a POD type", t1);
2754 case CPTK_IS_POLYMORPHIC:
2755 inform (loc, " %qT is not a polymorphic type", t1);
2757 case CPTK_IS_SAME_AS:
2758 inform (loc, " %qT is not the same as %qT", t1, t2);
2760 case CPTK_IS_STD_LAYOUT:
2761 inform (loc, " %qT is not an standard layout type", t1);
2763 case CPTK_IS_TRIVIAL:
2764 inform (loc, " %qT is not a trivial type", t1);
2767 inform (loc, " %qT is not a union", t1);
2774 /* Diagnose the expression of a predicate constraint. */
2777 diagnose_other_expression (location_t loc, tree, tree cur, tree args)
2779 if (constraint_expression_satisfied_p (cur, args))
2781 if (elide_constraint_failure_p())
2783 inform (loc, "%qE evaluated to false", cur);
2786 /* Do our best to infer meaning from predicates. */
2789 diagnose_predicate_constraint (location_t loc, tree orig, tree cur, tree args)
2791 if (TREE_CODE (PRED_CONSTR_EXPR (cur)) == TRAIT_EXPR)
2792 diagnose_trait_expression (loc, orig, cur, args);
2794 diagnose_other_expression (loc, orig, cur, args);
2797 /* Diagnose a failed pack expansion, possibly containing constraints. */
2800 diagnose_pack_expansion (location_t loc, tree, tree cur, tree args)
2802 if (constraint_expression_satisfied_p (cur, args))
2804 if (elide_constraint_failure_p())
2807 /* Make sure that we don't have naked packs that we don't expect. */
2808 if (!same_type_p (TREE_TYPE (cur), boolean_type_node))
2810 inform (loc, "invalid pack expansion in constraint %qE", cur);
2814 inform (loc, "in the expansion of %qE", cur);
2816 /* Get the vector of expanded arguments. Note that n must not
2817 be 0 since this constraint is not satisfied. */
2818 ++processing_template_decl;
2819 tree exprs = tsubst_pack_expansion (cur, args, tf_none, NULL_TREE);
2820 --processing_template_decl;
2821 if (exprs == error_mark_node)
2823 /* TODO: This error message could be better. */
2824 inform (loc, " substitution failure occurred during expansion");
2828 /* Check each expanded constraint separately. */
2829 int n = TREE_VEC_LENGTH (exprs);
2830 for (int i = 0; i < n; ++i)
2832 tree expr = TREE_VEC_ELT (exprs, i);
2833 if (!constraint_expression_satisfied_p (expr, args))
2834 inform (loc, " %qE was not satisfied", expr);
2838 /* Diagnose a potentially unsatisfied concept check constraint DECL<CARGS>.
2839 Parameters are as for diagnose_constraint. */
2842 diagnose_check_constraint (location_t loc, tree orig, tree cur, tree args)
2844 if (constraints_satisfied_p (cur, args))
2847 tree decl = CHECK_CONSTR_CONCEPT (cur);
2848 tree cargs = CHECK_CONSTR_ARGS (cur);
2849 tree tmpl = DECL_TI_TEMPLATE (decl);
2850 tree check = build_nt (CHECK_CONSTR, decl, cargs);
2852 /* Instantiate the concept check arguments. */
2853 tree targs = tsubst (cargs, args, tf_none, NULL_TREE);
2854 if (targs == error_mark_node)
2856 if (elide_constraint_failure_p ())
2858 inform (loc, "invalid use of the concept %qE", check);
2859 tsubst (cargs, args, tf_warning_or_error, NULL_TREE);
2863 tree sub = build_tree_list (tmpl, targs);
2864 /* Update to the expanded definitions. */
2865 cur = expand_concept (decl, targs);
2866 if (cur == error_mark_node)
2868 if (elide_constraint_failure_p ())
2870 inform (loc, "in the expansion of concept %qE %S", check, sub);
2871 cur = get_concept_definition (decl);
2872 tsubst_expr (cur, targs, tf_warning_or_error, NULL_TREE, false);
2876 orig = get_concept_definition (CHECK_CONSTR_CONCEPT (orig));
2877 orig = normalize_expression (orig);
2879 location_t dloc = DECL_SOURCE_LOCATION (decl);
2880 inform (dloc, "within %qS", sub);
2881 diagnose_constraint (dloc, orig, cur, targs);
2884 /* Diagnose a potentially unsatisfied conjunction or disjunction. Parameters
2885 are as for diagnose_constraint. */
2888 diagnose_logical_constraint (location_t loc, tree orig, tree cur, tree args)
2890 tree t0 = TREE_OPERAND (cur, 0);
2891 tree t1 = TREE_OPERAND (cur, 1);
2892 if (!constraints_satisfied_p (t0, args))
2893 diagnose_constraint (loc, TREE_OPERAND (orig, 0), t0, args);
2894 else if (TREE_CODE (orig) == TRUTH_ORIF_EXPR)
2896 if (!constraints_satisfied_p (t1, args))
2897 diagnose_constraint (loc, TREE_OPERAND (orig, 1), t1, args);
2900 /* Diagnose a potential expression constraint failure. */
2903 diagnose_expression_constraint (location_t loc, tree orig, tree cur, tree args)
2905 if (constraints_satisfied_p (cur, args))
2907 if (elide_constraint_failure_p())
2910 tree expr = EXPR_CONSTR_EXPR (orig);
2911 inform (loc, "the required expression %qE would be ill-formed", expr);
2913 // TODO: We should have a flag that controls this substitution.
2914 // I'm finding it very useful for resolving concept check errors.
2916 // inform (input_location, "==== BEGIN DUMP ====");
2917 // tsubst_expr (EXPR_CONSTR_EXPR (orig), args, tf_warning_or_error, NULL_TREE, false);
2918 // inform (input_location, "==== END DUMP ====");
2921 /* Diagnose a potentially failed type constraint. */
2924 diagnose_type_constraint (location_t loc, tree orig, tree cur, tree args)
2926 if (constraints_satisfied_p (cur, args))
2928 if (elide_constraint_failure_p())
2931 tree type = TYPE_CONSTR_TYPE (orig);
2932 inform (loc, "the required type %qT would be ill-formed", type);
2935 /* Diagnose a potentially unsatisfied conversion constraint. */
2938 diagnose_implicit_conversion_constraint (location_t loc, tree orig, tree cur,
2941 if (constraints_satisfied_p (cur, args))
2944 /* The expression and type will previously have been substituted into,
2945 and therefore may already be an error. Also, we will have already
2946 diagnosed substitution failures into an expression since this must be
2947 part of a compound requirement. */
2948 tree expr = ICONV_CONSTR_EXPR (cur);
2949 if (error_operand_p (expr))
2952 /* Don't elide a previously diagnosed failure. */
2953 if (elide_constraint_failure_p())
2956 tree type = ICONV_CONSTR_TYPE (cur);
2957 if (error_operand_p (type))
2959 inform (loc, "substitution into type %qT failed",
2960 ICONV_CONSTR_TYPE (orig));
2964 inform(loc, "%qE is not implicitly convertible to %qT", expr, type);
2967 /* Diagnose an argument deduction constraint. */
2970 diagnose_argument_deduction_constraint (location_t loc, tree orig, tree cur,
2973 if (constraints_satisfied_p (cur, args))
2976 /* The expression and type will previously have been substituted into,
2977 and therefore may already be an error. Also, we will have already
2978 diagnosed substution failures into an expression since this must be
2979 part of a compound requirement. */
2980 tree expr = DEDUCT_CONSTR_EXPR (cur);
2981 if (error_operand_p (expr))
2984 /* Don't elide a previously diagnosed failure. */
2985 if (elide_constraint_failure_p ())
2988 tree pattern = DEDUCT_CONSTR_PATTERN (cur);
2989 if (error_operand_p (pattern))
2991 inform (loc, "substitution into type %qT failed",
2992 DEDUCT_CONSTR_PATTERN (orig));
2996 inform (loc, "unable to deduce placeholder type %qT from %qE",
3000 /* Diagnose an exception constraint. */
3003 diagnose_exception_constraint (location_t loc, tree orig, tree cur, tree args)
3005 if (constraints_satisfied_p (cur, args))
3007 if (elide_constraint_failure_p ())
3010 /* Rebuild a noexcept expression. */
3011 tree expr = EXCEPT_CONSTR_EXPR (cur);
3012 if (error_operand_p (expr))
3015 inform (loc, "%qE evaluated to false", EXCEPT_CONSTR_EXPR (orig));
3018 /* Diagnose a potentially unsatisfied parameterized constraint. */
3021 diagnose_parameterized_constraint (location_t loc, tree orig, tree cur,
3024 if (constraints_satisfied_p (cur, args))
3027 local_specialization_stack stack;
3028 tree parms = PARM_CONSTR_PARMS (cur);
3029 tree vars = tsubst_constraint_variables (parms, args, tf_warning_or_error,
3031 if (vars == error_mark_node)
3033 if (elide_constraint_failure_p ())
3036 /* TODO: Check which variable failed and use orig to diagnose
3037 that substitution error. */
3038 inform (loc, "failed to instantiate constraint variables");
3042 /* TODO: It would be better write these in a list. */
3045 inform (loc, " with %q#D", vars);
3046 vars = TREE_CHAIN (vars);
3048 orig = PARM_CONSTR_OPERAND (orig);
3049 cur = PARM_CONSTR_OPERAND (cur);
3050 return diagnose_constraint (loc, orig, cur, args);
3053 /* Diagnose the constraint CUR for the given ARGS. This is only ever invoked
3054 on the associated constraints, so we can only have conjunctions of
3055 predicate constraints. The ORIGinal (dependent) constructs follow
3056 the current constraints to enable better diagnostics. Note that ORIG
3057 and CUR must be the same kinds of node, except when CUR is an error. */
3060 diagnose_constraint (location_t loc, tree orig, tree cur, tree args)
3062 switch (TREE_CODE (cur))
3065 diagnose_expression_constraint (loc, orig, cur, args);
3069 diagnose_type_constraint (loc, orig, cur, args);
3073 diagnose_implicit_conversion_constraint (loc, orig, cur, args);
3077 diagnose_argument_deduction_constraint (loc, orig, cur, args);
3081 diagnose_exception_constraint (loc, orig, cur, args);
3086 diagnose_logical_constraint (loc, orig, cur, args);
3090 diagnose_predicate_constraint (loc, orig, cur, args);
3094 diagnose_parameterized_constraint (loc, orig, cur, args);
3098 diagnose_check_constraint (loc, orig, cur, args);
3101 case EXPR_PACK_EXPANSION:
3102 diagnose_pack_expansion (loc, orig, cur, args);
3106 /* TODO: Can we improve the diagnostic with the original? */
3107 inform (input_location, "ill-formed constraint");
3116 /* Diagnose the reason(s) why ARGS do not satisfy the constraints
3117 of declaration DECL. */
3120 diagnose_declaration_constraints (location_t loc, tree decl, tree args)
3122 inform (loc, " constraints not satisfied");
3124 /* Constraints are attached to the template. */
3125 if (tree ti = DECL_TEMPLATE_INFO (decl))
3127 decl = TI_TEMPLATE (ti);
3129 args = TI_ARGS (ti);
3132 /* Recursively diagnose the associated constraints. */
3133 tree ci = get_constraints (decl);
3134 tree t = CI_ASSOCIATED_CONSTRAINTS (ci);
3135 diagnose_constraint (loc, t, t, args);
3140 /* Emit diagnostics detailing the failure ARGS to satisfy the
3141 constraints of T. Here, T can be either a constraint
3142 or a declaration. */
3145 diagnose_constraints (location_t loc, tree t, tree args)
3147 constraint_errors = 0;
3149 if (constraint_p (t))
3150 diagnose_constraint (loc, t, t, args);
3151 else if (DECL_P (t))
3152 diagnose_declaration_constraints (loc, t, args);
3156 /* Note the number of elided failures. */
3157 int n = undiagnosed_constraint_failures ();
3159 inform (loc, "... and %d more constraint errors not shown", n);