1/* Processing rules for constraints.
2 Copyright (C) 2013-2017 Free Software Foundation, Inc.
3 Contributed by Andrew Sutton (andrew.n.sutton@gmail.com)
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "timevar.h"
26#include "hash-set.h"
27#include "machmode.h"
28#include "vec.h"
29#include "double-int.h"
30#include "input.h"
31#include "alias.h"
32#include "symtab.h"
33#include "wide-int.h"
34#include "inchash.h"
35#include "tree.h"
36#include "stringpool.h"
37#include "attribs.h"
38#include "intl.h"
39#include "flags.h"
40#include "cp-tree.h"
41#include "c-family/c-common.h"
42#include "c-family/c-objc.h"
43#include "cp-objcp-common.h"
44#include "tree-inline.h"
45#include "decl.h"
46#include "toplev.h"
47#include "type-utils.h"
48
49/*---------------------------------------------------------------------------
50 Operations on constraints
51---------------------------------------------------------------------------*/
52
53/* Returns true if C is a constraint tree code. Note that ERROR_MARK
54 is a valid constraint. */
55
56static inline bool
57constraint_p (tree_code c)
58{
59 return ((PRED_CONSTR <= c && c <= DISJ_CONSTR)
60 || c == EXPR_PACK_EXPANSION
61 || c == ERROR_MARK);
62}
63
64/* Returns true if T is a constraint. Note that error_mark_node
65 is a valid constraint. */
66
67bool
68constraint_p (tree t)
69{
70 return constraint_p (TREE_CODE (t));
71}
72
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,
76
77 conjoin_constraints(a, NULL_TREE) == a
78
79 and
80
81 conjoin_constraints (NULL_TREE, a) == a
82
83 If both A and B are NULL_TREE, the result is also NULL_TREE. */
84
85tree
86conjoin_constraints (tree a, tree b)
87{
88 gcc_assert (a ? constraint_p (a) : true);
89 gcc_assert (b ? constraint_p (b) : true);
90 if (a)
91 return b ? build_nt (CONJ_CONSTR, a, b) : a;
92 else if (b)
93 return b;
94 else
95 return NULL_TREE;
96}
97
98/* Transform the vector of expressions in the T into a conjunction
99 of requirements. T must be a TREE_VEC. */
100
101tree
102conjoin_constraints (tree t)
103{
104 gcc_assert (TREE_CODE (t) == TREE_VEC);
105 tree r = NULL_TREE;
106 for (int i = 0; i < TREE_VEC_LENGTH (t); ++i)
107 r = conjoin_constraints (r, TREE_VEC_ELT (t, i));
108 return r;
109}
110
111/* Returns true if T is a call expression to a function
112 concept. */
113
114bool
115function_concept_check_p (tree t)
116{
117 gcc_assert (TREE_CODE (t) == CALL_EXPR);
118 tree fn = CALL_EXPR_FN (t);
119 if (fn != NULL_TREE
120 && TREE_CODE (fn) == TEMPLATE_ID_EXPR)
121 {
122 tree f1 = OVL_FIRST (TREE_OPERAND (fn, 0));
123 if (TREE_CODE (f1) == TEMPLATE_DECL
124 && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (f1)))
125 return true;
126 }
127 return false;
128}
129
130/* Returns true if any of the arguments in the template
131 argument list is a wildcard or wildcard pack. */
132
133bool
134contains_wildcard_p (tree args)
135{
136 for (int i = 0; i < TREE_VEC_LENGTH (args); ++i)
137 {
138 tree arg = TREE_VEC_ELT (args, i);
139 if (TREE_CODE (arg) == WILDCARD_DECL)
140 return true;
141 }
142 return false;
143}
144
145/* Build a new call expression, but don't actually generate a
146 new function call. We just want the tree, not the semantics. */
147
148inline tree
149build_call_check (tree id)
150{
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;
156 return call;
157}
158
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
162 declaration. */
163
164tree
165build_variable_check (tree id)
166{
167 gcc_assert (TREE_CODE (id) == TEMPLATE_ID_EXPR);
168 if (contains_wildcard_p (TREE_OPERAND (id, 1)))
169 return id;
170
171 ++processing_template_decl;
172 tree var = finish_template_variable (id);
173 --processing_template_decl;
174 return var;
175}
176
177/*---------------------------------------------------------------------------
178 Resolution of qualified concept names
179---------------------------------------------------------------------------*/
180
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'.
184
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
188 call. */
189
190// Given an overload set OVL, try to find a unique definition that can be
191// instantiated by the template arguments ARGS.
192//
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:
196//
197// f<T, U>()
198//
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.
202static tree
203resolve_constraint_check (tree ovl, tree args)
204{
205 int nerrs = 0;
206 tree cands = NULL_TREE;
207 for (lkp_iterator iter (ovl); iter; ++iter)
208 {
209 // Get the next template overload.
210 tree tmpl = *iter;
211 if (TREE_CODE (tmpl) != TEMPLATE_DECL)
212 continue;
213
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.
218 //
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))
223 continue;
224 if (!DECL_DECLARED_CONCEPT_P (fn))
225 continue;
226
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))
231 {
232 if (subst == error_mark_node)
233 ++nerrs;
234 else
235 cands = tree_cons (subst, fn, cands);
236 }
237 --processing_template_decl;
238 }
239
240 if (!cands)
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;
246
247 return cands;
248}
249
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.
253tree
254resolve_constraint_check (tree call)
255{
256 gcc_assert (TREE_CODE (call) == CALL_EXPR);
257
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)
266 return NULL_TREE;
267
268 // Get the overload set and template arguments and try to
269 // resolve the target.
270 tree ovl = TREE_OPERAND (target, 0);
271
272 /* This is a function call of a variable concept... ill-formed. */
273 if (TREE_CODE (ovl) == TEMPLATE_DECL)
274 {
275 error_at (location_of (call),
276 "function call of variable concept %qE", call);
277 return error_mark_node;
278 }
279
280 tree args = TREE_OPERAND (target, 1);
281 return resolve_constraint_check (ovl, args);
282}
283
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. */
288
289tree
290resolve_variable_concept_check (tree id)
291{
292 tree tmpl = TREE_OPERAND (id, 0);
293 tree args = TREE_OPERAND (id, 1);
294
295 if (!variable_concept_p (tmpl))
296 return NULL_TREE;
297
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)
306 {
307 tree decl = DECL_TEMPLATE_RESULT (tmpl);
308 return build_tree_list (result, decl);
309 }
310 else
311 return error_mark_node;
312}
313
314
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
321 false. */
322
323bool
324deduce_constrained_parameter (tree expr, tree& check, tree& proto)
325{
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);
331 else
332 gcc_unreachable ();
333
334 if (info && info != error_mark_node)
335 {
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);
341 return true;
342 }
343 check = proto = NULL_TREE;
344 return false;
345}
346
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.
350static tree
351deduce_concept_introduction (tree expr)
352{
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);
358 else
359 gcc_unreachable ();
360
361 if (info && info != error_mark_node)
362 return TREE_PURPOSE (info);
363 return NULL_TREE;
364}
365
366namespace {
367
368/*---------------------------------------------------------------------------
369 Constraint implication learning
370---------------------------------------------------------------------------*/
371
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.
375 For example:
376
377 template<typename T> concept bool C = ...;
378 template<typenaem T> concept bool D = C<T> && true;
379
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.
384
385 In rare cases, we may start with a logical equivalence. For example:
386
387 template<typename T> concept bool C = ...;
388 template<typename T> concept bool D = C<T>;
389
390 Here, we learn that C<T> implies D<T> and vice versa. */
391
392enum implication_context
393{
394 conjunction_cxt, /* C1 implies C2. */
395 disjunction_cxt, /* C2 implies C1. */
396 equivalence_cxt /* C1 implies C2, C2 implies C1. */
397};
398
399void learn_implications(tree, tree, implication_context);
400
401void
402learn_implication (tree parent, tree child, implication_context cxt)
403{
404 switch (cxt)
405 {
406 case conjunction_cxt:
407 save_subsumption_result (parent, child, true);
408 break;
409 case disjunction_cxt:
410 save_subsumption_result (child, parent, true);
411 break;
412 case equivalence_cxt:
413 save_subsumption_result (parent, child, true);
414 save_subsumption_result (child, parent, true);
415 break;
416 }
417}
418
419void
420learn_logical_operation (tree parent, tree constr, implication_context cxt)
421{
422 learn_implications (parent, TREE_OPERAND (constr, 0), cxt);
423 learn_implications (parent, TREE_OPERAND (constr, 1), cxt);
424}
425
426void
427learn_implications (tree parent, tree constr, implication_context cxt)
428{
429 switch (TREE_CODE (constr))
430 {
431 case CHECK_CONSTR:
432 return learn_implication (parent, constr, cxt);
433
434 case CONJ_CONSTR:
435 if (cxt == disjunction_cxt)
436 return;
437 return learn_logical_operation (parent, constr, cxt);
438
439 case DISJ_CONSTR:
440 if (cxt == conjunction_cxt)
441 return;
442 return learn_logical_operation (parent, constr, cxt);
443
444 default:
445 break;
446 }
447}
448
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. */
452
453void
454learn_implications (tree tmpl, tree args, tree constr)
455{
456 /* Don't memoize relations between non-dependent arguemnts. It's not
457 helpful. */
458 if (!uses_template_parms (args))
459 return;
460
461 /* Build a check constraint for the purpose of caching. */
462 tree parent = build_nt (CHECK_CONSTR, tmpl, args);
463
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);
472}
473
474/*---------------------------------------------------------------------------
475 Expansion of concept definitions
476---------------------------------------------------------------------------*/
477
478/* Returns the expression of a function concept. */
479
480tree
481get_returned_expression (tree fn)
482{
483 /* Extract the body of the function minus the return expression. */
484 tree body = DECL_SAVED_TREE (fn);
485 if (!body)
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;
491
492 return TREE_OPERAND (body, 0);
493}
494
495/* Returns the initializer of a variable concept. */
496
497tree
498get_variable_initializer (tree var)
499{
500 tree init = DECL_INITIAL (var);
501 if (!init)
502 return error_mark_node;
503 return init;
504}
505
506/* Returns the definition of a variable or function concept. */
507
508tree
509get_concept_definition (tree decl)
510{
511 if (VAR_P (decl))
512 return get_variable_initializer (decl);
513 else if (TREE_CODE (decl) == FUNCTION_DECL)
514 return get_returned_expression (decl);
515 gcc_unreachable ();
516}
517
518int expansion_level = 0;
519
520struct expanding_concept_sentinel
521{
522 expanding_concept_sentinel ()
523 {
524 ++expansion_level;
525 }
526
527 ~expanding_concept_sentinel()
528 {
529 --expansion_level;
530 }
531};
532
533
534} /* namespace */
535
536/* Returns true when a concept is being expanded. */
537
538bool
539expanding_concept()
540{
541 return expansion_level > 0;
542}
543
544/* Expand a concept declaration (not a template) and its arguments to
545 a constraint defined by the concept's initializer or definition. */
546
547tree
548expand_concept (tree decl, tree args)
549{
550 expanding_concept_sentinel sentinel;
551
552 if (TREE_CODE (decl) == TEMPLATE_DECL)
553 decl = DECL_TEMPLATE_RESULT (decl);
554 tree tmpl = DECL_TI_TEMPLATE (decl);
555
556 /* Check for a previous specialization. */
557 if (tree spec = get_concept_expansion (tmpl, args))
558 return spec;
559
560 /* Substitute the arguments to form a new definition expression. */
561 tree def = get_concept_definition (decl);
562
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;
568
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);
574}
575
576
577/*---------------------------------------------------------------------------
578 Stepwise normalization of expressions
579
580This set of functions will transform an expression into a constraint
581in a sequence of steps. Normalization does not not look into concept
582definitions.
583---------------------------------------------------------------------------*/
584
585/* Transform a logical-or or logical-and expression into either
586 a conjunction or disjunction. */
587
588tree
589normalize_logical_operation (tree t, tree_code c)
590{
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);
594}
595
596/* A simple requirement T introduces an expression constraint
597 for its expression. */
598
599inline tree
600normalize_simple_requirement (tree t)
601{
602 return build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0));
603}
604
605/* A type requirement T introduce a type constraint for its type. */
606
607inline tree
608normalize_type_requirement (tree t)
609{
610 return build_nt (TYPE_CONSTR, TREE_OPERAND (t, 0));
611}
612
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. */
620
621tree
622normalize_compound_requirement (tree t)
623{
624 tree expr = TREE_OPERAND (t, 0);
625 tree constr = build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0));
626
627 /* If a type is given, append an implicit conversion or
628 argument deduction constraint. */
629 if (tree type = TREE_OPERAND (t, 1))
630 {
631 tree type_constr;
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);
636 else
637 type_constr = build_nt (ICONV_CONSTR, expr, type);
638 constr = conjoin_constraints (constr, type_constr);
639 }
640
641 /* If noexcept is present, append an exception constraint. */
642 if (COMPOUND_REQ_NOEXCEPT_P (t))
643 {
644 tree except = build_nt (EXCEPT_CONSTR, expr);
645 constr = conjoin_constraints (constr, except);
646 }
647
648 return constr;
649}
650
651/* A nested requirement T introduces a conjunction of constraints
652 corresponding to its constraint-expression.
653
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. */
658
659inline tree
660normalize_nested_requirement (tree t)
661{
662 return normalize_expression (TREE_OPERAND (t, 0));
663}
664
665/* Transform a requirement T into one or more constraints. */
666
667tree
668normalize_requirement (tree t)
669{
670 switch (TREE_CODE (t))
671 {
672 case SIMPLE_REQ:
673 return normalize_simple_requirement (t);
674
675 case TYPE_REQ:
676 return normalize_type_requirement (t);
677
678 case COMPOUND_REQ:
679 return normalize_compound_requirement (t);
680
681 case NESTED_REQ:
682 return normalize_nested_requirement (t);
683
684 default:
685 gcc_unreachable ();
686 }
687 return error_mark_node;
688}
689
690/* Transform a sequence of requirements into a conjunction of
691 constraints. */
692
693tree
694normalize_requirements (tree t)
695{
696 tree result = NULL_TREE;
697 for (; t; t = TREE_CHAIN (t))
698 {
699 tree constr = normalize_requirement (TREE_VALUE (t));
700 result = conjoin_constraints (result, constr);
701 }
702 return result;
703}
704
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. */
708
709tree
710normalize_requires_expression (tree t)
711{
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);
715 else
716 return operand;
717}
718
719/* For a template-id referring to a variable concept, returns
720 a check constraint. Otherwise, returns a predicate constraint. */
721
722tree
723normalize_template_id_expression (tree t)
724{
725 if (tree info = resolve_variable_concept_check (t))
726 {
727 if (info == error_mark_node)
728 {
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;
733 }
734
735 tree decl = TREE_VALUE (info);
736 tree args = TREE_PURPOSE (info);
737 return build_nt (CHECK_CONSTR, decl, args);
738 }
739
740 /* Check that we didn't refer to a function concept like a variable. */
741 tree fn = OVL_FIRST (TREE_OPERAND (t, 0));
742 if (TREE_CODE (fn) == TEMPLATE_DECL
743 && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (fn)))
744 {
745 error_at (location_of (t),
746 "invalid reference to function concept %qD", fn);
747 return error_mark_node;
748 }
749
750 return build_nt (PRED_CONSTR, t);
751}
752
753/* For a call expression to a function concept, returns a check
754 constraint. Otherwise, returns a predicate constraint. */
755
756tree
757normalize_call_expression (tree t)
758{
759 /* Try to resolve this function call as a concept. If not, then
760 it can be returned as a predicate constraint. */
761 tree check = resolve_constraint_check (t);
762 if (!check)
763 return build_nt (PRED_CONSTR, t);
764 if (check == error_mark_node)
765 {
766 /* TODO: Improve diagnostics. We could report why the reference
767 is invalid. */
768 error ("invalid reference to concept %qE", t);
769 return error_mark_node;
770 }
771
772 tree fn = TREE_VALUE (check);
773 tree args = TREE_PURPOSE (check);
774 return build_nt (CHECK_CONSTR, fn, args);
775}
776
777/* If T is a call to an overloaded && or || operator, diagnose that
778 as a non-SFINAEable error. Returns true if an error is emitted.
779
780 TODO: It would be better to diagnose this at the point of definition,
781 if possible. Perhaps we should immediately do a first-pass normalization
782 of a concept definition to catch obvious non-dependent errors like
783 this. */
784
785bool
786check_for_logical_overloads (tree t)
787{
788 if (TREE_CODE (t) != CALL_EXPR)
789 return false;
790
791 tree fn = CALL_EXPR_FN (t);
792
793 /* For member calls, try extracting the function from the
794 component ref. */
795 if (TREE_CODE (fn) == COMPONENT_REF)
796 {
797 fn = TREE_OPERAND (fn, 1);
798 if (TREE_CODE (fn) == BASELINK)
799 fn = BASELINK_FUNCTIONS (fn);
800 }
801
802 if (TREE_CODE (fn) != FUNCTION_DECL)
803 return false;
804
805 if (DECL_OVERLOADED_OPERATOR_P (fn))
806 {
807 location_t loc = EXPR_LOC_OR_LOC (t, input_location);
808 error_at (loc, "constraint %qE, uses overloaded operator", t);
809 return true;
810 }
811
812 return false;
813}
814
815/* The normal form of an atom depends on the expression. The normal
816 form of a function call to a function concept is a check constraint
817 for that concept. The normal form of a reference to a variable
818 concept is a check constraint for that concept. Otherwise, the
819 constraint is a predicate constraint. */
820
821tree
822normalize_atom (tree t)
823{
824 /* We can get constraints pushed down through pack expansions, so
825 just return them. */
826 if (constraint_p (t))
827 return t;
828
829 tree type = TREE_TYPE (t);
830 if (!type || type_unknown_p (t) || TREE_CODE (type) == TEMPLATE_TYPE_PARM)
831 ;
832 else if (!dependent_type_p (type))
833 {
834 if (check_for_logical_overloads (t))
835 return error_mark_node;
836
837 type = cv_unqualified (type);
838 if (!same_type_p (type, boolean_type_node))
839 {
840 error ("predicate constraint %q+E does not have type %<bool%>", t);
841 return error_mark_node;
842 }
843 }
844
845 if (TREE_CODE (t) == TEMPLATE_ID_EXPR)
846 return normalize_template_id_expression (t);
847 if (TREE_CODE (t) == CALL_EXPR)
848 return normalize_call_expression (t);
849 return build_nt (PRED_CONSTR, t);
850}
851
852/* Push down the pack expansion EXP into the leaves of the constraint PAT. */
853
854tree
855push_down_pack_expansion (tree exp, tree pat)
856{
857 switch (TREE_CODE (pat))
858 {
859 case CONJ_CONSTR:
860 case DISJ_CONSTR:
861 {
862 pat = copy_node (pat);
863 TREE_OPERAND (pat, 0)
864 = push_down_pack_expansion (exp, TREE_OPERAND (pat, 0));
865 TREE_OPERAND (pat, 1)
866 = push_down_pack_expansion (exp, TREE_OPERAND (pat, 1));
867 return pat;
868 }
869 default:
870 {
871 exp = copy_node (exp);
872 SET_PACK_EXPANSION_PATTERN (exp, pat);
873 return exp;
874 }
875 }
876}
877
878/* Transform a pack expansion into a constraint. First we transform the
879 pattern of the pack expansion, then we push the pack expansion down into the
880 leaves of the constraint so that partial ordering will work. */
881
882tree
883normalize_pack_expansion (tree t)
884{
885 tree pat = normalize_expression (PACK_EXPANSION_PATTERN (t));
886 return push_down_pack_expansion (t, pat);
887}
888
889/* Transform an expression into a constraint. */
890
891tree
892normalize_any_expression (tree t)
893{
894 switch (TREE_CODE (t))
895 {
896 case TRUTH_ANDIF_EXPR:
897 return normalize_logical_operation (t, CONJ_CONSTR);
898
899 case TRUTH_ORIF_EXPR:
900 return normalize_logical_operation (t, DISJ_CONSTR);
901
902 case REQUIRES_EXPR:
903 return normalize_requires_expression (t);
904
905 case BIND_EXPR:
906 return normalize_expression (BIND_EXPR_BODY (t));
907
908 case EXPR_PACK_EXPANSION:
909 return normalize_pack_expansion (t);
910
911 default:
912 /* All other constraints are atomic. */
913 return normalize_atom (t);
914 }
915}
916
917/* Transform a statement into an expression. */
918tree
919normalize_any_statement (tree t)
920{
921 switch (TREE_CODE (t))
922 {
923 case RETURN_EXPR:
924 return normalize_expression (TREE_OPERAND (t, 0));
925 default:
926 gcc_unreachable ();
927 }
928 return error_mark_node;
929}
930
931/* Reduction rules for the declaration T. */
932
933tree
934normalize_any_declaration (tree t)
935{
936 switch (TREE_CODE (t))
937 {
938 case VAR_DECL:
939 return normalize_atom (t);
940 default:
941 gcc_unreachable ();
942 }
943 return error_mark_node;
944}
945
946/* Returns the normal form of a constraint expression. */
947
948tree
949normalize_expression (tree t)
950{
951 if (!t)
952 return NULL_TREE;
953
954 if (t == error_mark_node)
955 return error_mark_node;
956
957 switch (TREE_CODE_CLASS (TREE_CODE (t)))
958 {
959 case tcc_unary:
960 case tcc_binary:
961 case tcc_expression:
962 case tcc_vl_exp:
963 return normalize_any_expression (t);
964
965 case tcc_statement:
966 return normalize_any_statement (t);
967
968 case tcc_declaration:
969 return normalize_any_declaration (t);
970
971 case tcc_exceptional:
972 case tcc_constant:
973 case tcc_reference:
974 case tcc_comparison:
975 /* These are all atomic predicate constraints. */
976 return normalize_atom (t);
977
978 default:
979 /* Unhandled node kind. */
980 gcc_unreachable ();
981 }
982 return error_mark_node;
983}
984
985
986/*---------------------------------------------------------------------------
987 Constraint normalization
988---------------------------------------------------------------------------*/
989
990tree normalize_constraint (tree);
991
992/* The normal form of the disjunction T0 /\ T1 is the conjunction
993 of the normal form of T0 and the normal form of T1. */
994
995inline tree
996normalize_conjunction (tree t)
997{
998 tree t0 = normalize_constraint (TREE_OPERAND (t, 0));
999 tree t1 = normalize_constraint (TREE_OPERAND (t, 1));
1000 return build_nt (CONJ_CONSTR, t0, t1);
1001}
1002
1003/* The normal form of the disjunction T0 \/ T1 is the disjunction
1004 of the normal form of T0 and the normal form of T1. */
1005
1006inline tree
1007normalize_disjunction (tree t)
1008{
1009 tree t0 = normalize_constraint (TREE_OPERAND (t, 0));
1010 tree t1 = normalize_constraint (TREE_OPERAND (t, 1));
1011 return build_nt (DISJ_CONSTR, t0, t1);
1012}
1013
1014/* A predicate constraint is normalized in two stages. First all
1015 references specializations of concepts are replaced by their
1016 substituted definitions. Then, the resulting expression is
1017 transformed into a constraint by transforming && expressions
1018 into conjunctions and || into disjunctions. */
1019
1020tree
1021normalize_predicate_constraint (tree t)
1022{
1023 ++processing_template_decl;
1024 tree expr = PRED_CONSTR_EXPR (t);
1025 tree constr = normalize_expression (expr);
1026 --processing_template_decl;
1027 return constr;
1028}
1029
1030/* The normal form of a parameterized constraint is the normal
1031 form of its operand. */
1032
1033tree
1034normalize_parameterized_constraint (tree t)
1035{
1036 tree parms = PARM_CONSTR_PARMS (t);
1037 tree operand = normalize_constraint (PARM_CONSTR_OPERAND (t));
1038 return build_nt (PARM_CONSTR, parms, operand);
1039}
1040
1041/* Normalize the constraint T by reducing it so that it is
1042 comprised of only conjunctions and disjunctions of atomic
1043 constraints. */
1044
1045tree
1046normalize_constraint (tree t)
1047{
1048 if (!t)
1049 return NULL_TREE;
1050
1051 if (t == error_mark_node)
1052 return t;
1053
1054 switch (TREE_CODE (t))
1055 {
1056 case CONJ_CONSTR:
1057 return normalize_conjunction (t);
1058
1059 case DISJ_CONSTR:
1060 return normalize_disjunction (t);
1061
1062 case PRED_CONSTR:
1063 return normalize_predicate_constraint (t);
1064
1065 case PARM_CONSTR:
1066 return normalize_parameterized_constraint (t);
1067
1068 case EXPR_CONSTR:
1069 case TYPE_CONSTR:
1070 case ICONV_CONSTR:
1071 case DEDUCT_CONSTR:
1072 case EXCEPT_CONSTR:
1073 /* These constraints are defined to be atomic. */
1074 return t;
1075
1076 default:
1077 /* CONSTR was not a constraint. */
1078 gcc_unreachable();
1079 }
1080 return error_mark_node;
1081}
1082
1083
1084
1085// -------------------------------------------------------------------------- //
1086// Constraint Semantic Processing
1087//
1088// The following functions are called by the parser and substitution rules
1089// to create and evaluate constraint-related nodes.
1090
1091// The constraints associated with the current template parameters.
1092tree
1093current_template_constraints (void)
1094{
1095 if (!current_template_parms)
1096 return NULL_TREE;
1097 tree tmpl_constr = TEMPLATE_PARM_CONSTRAINTS (current_template_parms);
1098 return build_constraints (tmpl_constr, NULL_TREE);
1099}
1100
1101// If the recently parsed TYPE declares or defines a template or template
1102// specialization, get its corresponding constraints from the current
1103// template parameters and bind them to TYPE's declaration.
1104tree
1105associate_classtype_constraints (tree type)
1106{
1107 if (!type || type == error_mark_node || TREE_CODE (type) != RECORD_TYPE)
1108 return type;
1109
1110 // An explicit class template specialization has no template
1111 // parameters.
1112 if (!current_template_parms)
1113 return type;
1114
1115 if (CLASSTYPE_IS_TEMPLATE (type) || CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1116 {
1117 tree decl = TYPE_STUB_DECL (type);
1118 tree ci = current_template_constraints ();
1119
1120 // An implicitly instantiated member template declaration already
1121 // has associated constraints. If it is defined outside of its
1122 // class, then we need match these constraints against those of
1123 // original declaration.
1124 if (tree orig_ci = get_constraints (decl))
1125 {
1126 if (!equivalent_constraints (ci, orig_ci))
1127 {
1128 // FIXME: Improve diagnostics.
1129 error ("%qT does not match any declaration", type);
1130 return error_mark_node;
1131 }
1132 return type;
1133 }
1134 set_constraints (decl, ci);
1135 }
1136 return type;
1137}
1138
1139namespace {
1140
1141// Create an empty constraint info block.
1142inline tree_constraint_info*
1143build_constraint_info ()
1144{
1145 return (tree_constraint_info *)make_node (CONSTRAINT_INFO);
1146}
1147
1148} // namespace
1149
1150/* Build a constraint-info object that contains the associated constraints
1151 of a declaration. This also includes the declaration's template
1152 requirements (TREQS) and any trailing requirements for a function
1153 declarator (DREQS). Note that both TREQS and DREQS must be constraints.
1154
1155 If the declaration has neither template nor declaration requirements
1156 this returns NULL_TREE, indicating an unconstrained declaration. */
1157
1158tree
1159build_constraints (tree tmpl_reqs, tree decl_reqs)
1160{
1161 gcc_assert (tmpl_reqs ? constraint_p (tmpl_reqs) : true);
1162 gcc_assert (decl_reqs ? constraint_p (decl_reqs) : true);
1163
1164 if (!tmpl_reqs && !decl_reqs)
1165 return NULL_TREE;
1166
1167 tree_constraint_info* ci = build_constraint_info ();
1168 ci->template_reqs = tmpl_reqs;
1169 ci->declarator_reqs = decl_reqs;
1170 ci->associated_constr = conjoin_constraints (tmpl_reqs, decl_reqs);
1171
1172 return (tree)ci;
1173}
1174
1175namespace {
1176
1177/* Construct a sequence of template arguments by prepending
1178 ARG to REST. Either ARG or REST may be null. */
1179tree
1180build_concept_check_arguments (tree arg, tree rest)
1181{
1182 gcc_assert (rest ? TREE_CODE (rest) == TREE_VEC : true);
1183 tree args;
1184 if (arg)
1185 {
1186 int n = rest ? TREE_VEC_LENGTH (rest) : 0;
1187 args = make_tree_vec (n + 1);
1188 TREE_VEC_ELT (args, 0) = arg;
1189 if (rest)
1190 for (int i = 0; i < n; ++i)
1191 TREE_VEC_ELT (args, i + 1) = TREE_VEC_ELT (rest, i);
1192 int def = rest ? GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (rest) : 0;
1193 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args, def + 1);
1194 }
1195 else
1196 {
1197 gcc_assert (rest != NULL_TREE);
1198 args = rest;
1199 }
1200 return args;
1201}
1202
1203} // namespace
1204
1205/* Construct an expression that checks the concept given by
1206 TARGET. The TARGET must be:
1207
1208 - an OVERLOAD referring to one or more function concepts
1209 - a BASELINK referring to an overload set of the above, or
1210 - a TEMPLTATE_DECL referring to a variable concept.
1211
1212 ARG and REST are the explicit template arguments for the
1213 eventual concept check. */
1214tree
1215build_concept_check (tree target, tree arg, tree rest)
1216{
1217 tree args = build_concept_check_arguments (arg, rest);
1218 if (variable_template_p (target))
1219 return build_variable_check (lookup_template_variable (target, args));
1220 else
1221 return build_call_check (lookup_template_function (target, args));
1222}
1223
1224
1225/* Returns a TYPE_DECL that contains sufficient information to
1226 build a template parameter of the same kind as PROTO and
1227 constrained by the concept declaration CNC. Note that PROTO
1228 is the first template parameter of CNC.
1229
1230 If specified, ARGS provides additional arguments to the
1231 constraint check. */
1232tree
1233build_constrained_parameter (tree cnc, tree proto, tree args)
1234{
1235 tree name = DECL_NAME (cnc);
1236 tree type = TREE_TYPE (proto);
1237 tree decl = build_decl (input_location, TYPE_DECL, name, type);
1238 CONSTRAINED_PARM_PROTOTYPE (decl) = proto;
1239 CONSTRAINED_PARM_CONCEPT (decl) = cnc;
1240 CONSTRAINED_PARM_EXTRA_ARGS (decl) = args;
1241 return decl;
1242}
1243
1244/* Create a constraint expression for the given DECL that
1245 evaluates the requirements specified by CONSTR, a TYPE_DECL
1246 that contains all the information necessary to build the
1247 requirements (see finish_concept_name for the layout of
1248 that TYPE_DECL).
1249
1250 Note that the constraints are neither reduced nor decomposed.
1251 That is done only after the requires clause has been parsed
1252 (or not).
1253
1254 This will always return a CHECK_CONSTR. */
1255tree
1256finish_shorthand_constraint (tree decl, tree constr)
1257{
1258 /* No requirements means no constraints. */
1259 if (!constr)
1260 return NULL_TREE;
1261
1262 tree proto = CONSTRAINED_PARM_PROTOTYPE (constr);
1263 tree con = CONSTRAINED_PARM_CONCEPT (constr);
1264 tree args = CONSTRAINED_PARM_EXTRA_ARGS (constr);
1265
1266 /* If the parameter declaration is variadic, but the concept
1267 is not then we need to apply the concept to every element
1268 in the pack. */
1269 bool is_proto_pack = template_parameter_pack_p (proto);
1270 bool is_decl_pack = template_parameter_pack_p (decl);
1271 bool apply_to_all_p = is_decl_pack && !is_proto_pack;
1272
1273 /* Get the argument and overload used for the requirement
1274 and adjust it if we're going to expand later. */
1275 tree arg = template_parm_to_arg (build_tree_list (NULL_TREE, decl));
1276 if (apply_to_all_p)
1277 arg = PACK_EXPANSION_PATTERN (TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg), 0));
1278
1279 /* Build the concept check. If it the constraint needs to be
1280 applied to all elements of the parameter pack, then make
1281 the constraint an expansion. */
1282 tree tmpl = DECL_TI_TEMPLATE (con);
1283 tree check = VAR_P (con) ? tmpl : ovl_make (tmpl);
1284 check = build_concept_check (check, arg, args);
1285
1286 /* Make the check a pack expansion if needed.
1287
1288 FIXME: We should be making a fold expression. */
1289 if (apply_to_all_p)
1290 {
1291 check = make_pack_expansion (check);
1292 TREE_TYPE (check) = boolean_type_node;
1293 }
1294
1295 return normalize_expression (check);
1296}
1297
1298/* Returns a conjunction of shorthand requirements for the template
1299 parameter list PARMS. Note that the requirements are stored in
1300 the TYPE of each tree node. */
1301tree
1302get_shorthand_constraints (tree parms)
1303{
1304 tree result = NULL_TREE;
1305 parms = INNERMOST_TEMPLATE_PARMS (parms);
1306 for (int i = 0; i < TREE_VEC_LENGTH (parms); ++i)
1307 {
1308 tree parm = TREE_VEC_ELT (parms, i);
1309 tree constr = TEMPLATE_PARM_CONSTRAINTS (parm);
1310 result = conjoin_constraints (result, constr);
1311 }
1312 return result;
1313}
1314
1315// Returns and chains a new parameter for PARAMETER_LIST which will conform
1316// to the prototype given by SRC_PARM. The new parameter will have its
1317// identifier and location set according to IDENT and PARM_LOC respectively.
1318static tree
1319process_introduction_parm (tree parameter_list, tree src_parm)
1320{
1321 // If we have a pack, we should have a single pack argument which is the
1322 // placeholder we want to look at.
1323 bool is_parameter_pack = ARGUMENT_PACK_P (src_parm);
1324 if (is_parameter_pack)
1325 src_parm = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (src_parm), 0);
1326
1327 // At this point we should have a wildcard, but we want to
1328 // grab the associated decl from it. Also grab the stored
1329 // identifier and location that should be chained to it in
1330 // a PARM_DECL.
1331 gcc_assert (TREE_CODE (src_parm) == WILDCARD_DECL);
1332
1333 tree ident = DECL_NAME (src_parm);
1334 location_t parm_loc = DECL_SOURCE_LOCATION (src_parm);
1335
1336 // If we expect a pack and the deduced template is not a pack, or if the
1337 // template is using a pack and we didn't declare a pack, throw an error.
1338 if (is_parameter_pack != WILDCARD_PACK_P (src_parm))
1339 {
1340 error_at (parm_loc, "cannot match pack for introduced parameter");
1341 tree err_parm = build_tree_list (error_mark_node, error_mark_node);
1342 return chainon (parameter_list, err_parm);
1343 }
1344
1345 src_parm = TREE_TYPE (src_parm);
1346
1347 tree parm;
1348 bool is_non_type;
1349 if (TREE_CODE (src_parm) == TYPE_DECL)
1350 {
1351 is_non_type = false;
1352 parm = finish_template_type_parm (class_type_node, ident);
1353 }
1354 else if (TREE_CODE (src_parm) == TEMPLATE_DECL)
1355 {
1356 is_non_type = false;
1357 begin_template_parm_list ();
1358 current_template_parms = DECL_TEMPLATE_PARMS (src_parm);
1359 end_template_parm_list ();
1360 parm = finish_template_template_parm (class_type_node, ident);
1361 }
1362 else
1363 {
1364 is_non_type = true;
1365
1366 // Since we don't have a declarator, so we can copy the source
1367 // parameter and change the name and eventually the location.
1368 parm = copy_decl (src_parm);
1369 DECL_NAME (parm) = ident;
1370 }
1371
1372 // Wrap in a TREE_LIST for process_template_parm. Introductions do not
1373 // retain the defaults from the source template.
1374 parm = build_tree_list (NULL_TREE, parm);
1375
1376 return process_template_parm (parameter_list, parm_loc, parm,
1377 is_non_type, is_parameter_pack);
1378}
1379
1380/* Associates a constraint check to the current template based
1381 on the introduction parameters. INTRO_LIST must be a TREE_VEC
1382 of WILDCARD_DECLs containing a chained PARM_DECL which
1383 contains the identifier as well as the source location.
1384 TMPL_DECL is the decl for the concept being used. If we
1385 take a concept, C, this will form a check in the form of
1386 C<INTRO_LIST> filling in any extra arguments needed by the
1387 defaults deduced.
1388
1389 Returns NULL_TREE if no concept could be matched and
1390 error_mark_node if an error occurred when matching. */
1391tree
1392finish_template_introduction (tree tmpl_decl, tree intro_list)
1393{
1394 /* Deduce the concept check. */
1395 tree expr = build_concept_check (tmpl_decl, NULL_TREE, intro_list);
1396 if (expr == error_mark_node)
1397 return NULL_TREE;
1398
1399 tree parms = deduce_concept_introduction (expr);
1400 if (!parms)
1401 return NULL_TREE;
1402
1403 /* Build template parameter scope for introduction. */
1404 tree parm_list = NULL_TREE;
1405 begin_template_parm_list ();
1406 int nargs = MIN (TREE_VEC_LENGTH (parms), TREE_VEC_LENGTH (intro_list));
1407 for (int n = 0; n < nargs; ++n)
1408 parm_list = process_introduction_parm (parm_list, TREE_VEC_ELT (parms, n));
1409 parm_list = end_template_parm_list (parm_list);
1410 for (int i = 0; i < TREE_VEC_LENGTH (parm_list); ++i)
1411 if (TREE_VALUE (TREE_VEC_ELT (parm_list, i)) == error_mark_node)
1412 {
1413 end_template_decl ();
1414 return error_mark_node;
1415 }
1416
1417 /* Build a concept check for our constraint. */
1418 tree check_args = make_tree_vec (TREE_VEC_LENGTH (parms));
1419 int n = 0;
1420 for (; n < TREE_VEC_LENGTH (parm_list); ++n)
1421 {
1422 tree parm = TREE_VEC_ELT (parm_list, n);
1423 TREE_VEC_ELT (check_args, n) = template_parm_to_arg (parm);
1424 }
1425 SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (check_args, n);
1426
1427 /* If the template expects more parameters we should be able
1428 to use the defaults from our deduced concept. */
1429 for (; n < TREE_VEC_LENGTH (parms); ++n)
1430 TREE_VEC_ELT (check_args, n) = TREE_VEC_ELT (parms, n);
1431
1432 /* Associate the constraint. */
1433 tree check = build_concept_check (tmpl_decl, NULL_TREE, check_args);
1434 tree constr = normalize_expression (check);
1435 TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = constr;
1436
1437 return parm_list;
1438}
1439
1440
1441/* Given the predicate constraint T from a constrained-type-specifier, extract
1442 its TMPL and ARGS. FIXME why do we need two different forms of
1443 constrained-type-specifier? */
1444
1445void
1446placeholder_extract_concept_and_args (tree t, tree &tmpl, tree &args)
1447{
1448 if (TREE_CODE (t) == TYPE_DECL)
1449 {
1450 /* A constrained parameter. Build a constraint check
1451 based on the prototype parameter and then extract the
1452 arguments from that. */
1453 tree proto = CONSTRAINED_PARM_PROTOTYPE (t);
1454 tree check = finish_shorthand_constraint (proto, t);
1455 placeholder_extract_concept_and_args (check, tmpl, args);
1456 return;
1457 }
1458
1459 if (TREE_CODE (t) == CHECK_CONSTR)
1460 {
1461 tree decl = CHECK_CONSTR_CONCEPT (t);
1462 tmpl = DECL_TI_TEMPLATE (decl);
1463 args = CHECK_CONSTR_ARGS (t);
1464 return;
1465 }
1466
1467 gcc_unreachable ();
1468}
1469
1470/* Returns true iff the placeholders C1 and C2 are equivalent. C1
1471 and C2 can be either CHECK_CONSTR or TEMPLATE_TYPE_PARM. */
1472
1473bool
1474equivalent_placeholder_constraints (tree c1, tree c2)
1475{
1476 if (c1 && TREE_CODE (c1) == TEMPLATE_TYPE_PARM)
1477 /* A constrained auto. */
1478 c1 = PLACEHOLDER_TYPE_CONSTRAINTS (c1);
1479 if (c2 && TREE_CODE (c2) == TEMPLATE_TYPE_PARM)
1480 c2 = PLACEHOLDER_TYPE_CONSTRAINTS (c2);
1481
1482 if (c1 == c2)
1483 return true;
1484 if (!c1 || !c2)
1485 return false;
1486 if (c1 == error_mark_node || c2 == error_mark_node)
1487 /* We get here during satisfaction; when a deduction constraint
1488 fails, substitution can produce an error_mark_node for the
1489 placeholder constraints. */
1490 return false;
1491
1492 tree t1, t2, a1, a2;
1493 placeholder_extract_concept_and_args (c1, t1, a1);
1494 placeholder_extract_concept_and_args (c2, t2, a2);
1495
1496 if (t1 != t2)
1497 return false;
1498
1499 int len1 = TREE_VEC_LENGTH (a1);
1500 int len2 = TREE_VEC_LENGTH (a2);
1501 if (len1 != len2)
1502 return false;
1503
1504 /* Skip the first argument so we don't infinitely recurse.
1505 Also, they may differ in template parameter index. */
1506 for (int i = 1; i < len1; ++i)
1507 {
1508 tree t1 = TREE_VEC_ELT (a1, i);
1509 tree t2 = TREE_VEC_ELT (a2, i);
1510 if (!template_args_equal (t1, t2))
1511 return false;
1512 }
1513 return true;
1514}
1515
1516/* Return a hash value for the placeholder PRED_CONSTR C. */
1517
1518hashval_t
1519hash_placeholder_constraint (tree c)
1520{
1521 tree t, a;
1522 placeholder_extract_concept_and_args (c, t, a);
1523
1524 /* Like hash_tmpl_and_args, but skip the first argument. */
1525 hashval_t val = iterative_hash_object (DECL_UID (t), 0);
1526
1527 for (int i = TREE_VEC_LENGTH (a)-1; i > 0; --i)
1528 val = iterative_hash_template_arg (TREE_VEC_ELT (a, i), val);
1529
1530 return val;
1531}
1532
1533/*---------------------------------------------------------------------------
1534 Constraint substitution
1535---------------------------------------------------------------------------*/
1536
1537/* The following functions implement substitution rules for constraints.
1538 Substitution without checking constraints happens only in the
1539 instantiation of class templates. For example:
1540
1541 template<C1 T> struct S {
1542 void f(T) requires C2<T>;
1543 void g(T) requires T::value;
1544 };
1545
1546 S<int> s; // error instantiating S<int>::g(T)
1547
1548 When we instantiate S, we substitute into its member declarations,
1549 including their constraints. However, those constraints are not
1550 checked. Substituting int into C2<T> yields C2<int>, and substituting
1551 into T::value yields a substitution failure, making the program
1552 ill-formed.
1553
1554 Note that we only ever substitute into the associated constraints
1555 of a declaration. That is, substitution is defined only for predicate
1556 constraints and conjunctions. */
1557
1558/* Substitute into the predicate constraints. Returns error_mark_node
1559 if the substitution into the expression fails. */
1560tree
1561tsubst_predicate_constraint (tree t, tree args,
1562 tsubst_flags_t complain, tree in_decl)
1563{
1564 tree expr = PRED_CONSTR_EXPR (t);
1565 ++processing_template_decl;
1566 tree result = tsubst_expr (expr, args, complain, in_decl, false);
1567 --processing_template_decl;
1568 return build_nt (PRED_CONSTR, result);
1569}
1570
1571/* Substitute into a check constraint. */
1572
1573tree
1574tsubst_check_constraint (tree t, tree args,
1575 tsubst_flags_t complain, tree in_decl)
1576{
1577 tree decl = CHECK_CONSTR_CONCEPT (t);
1578 tree tmpl = DECL_TI_TEMPLATE (decl);
1579 tree targs = CHECK_CONSTR_ARGS (t);
1580
1581 /* Substitute through by building an template-id expression
1582 and then substituting into that. */
1583 tree expr = build_nt (TEMPLATE_ID_EXPR, tmpl, targs);
1584 ++processing_template_decl;
1585 tree result = tsubst_expr (expr, args, complain, in_decl, false);
1586 --processing_template_decl;
1587
1588 if (result == error_mark_node)
1589 return error_mark_node;
1590
1591 /* Extract the results and rebuild the check constraint. */
1592 decl = DECL_TEMPLATE_RESULT (TREE_OPERAND (result, 0));
1593 args = TREE_OPERAND (result, 1);
1594
1595 return build_nt (CHECK_CONSTR, decl, args);
1596}
1597
1598/* Substitute into the conjunction of constraints. Returns
1599 error_mark_node if substitution into either operand fails. */
1600
1601tree
1602tsubst_logical_operator (tree t, tree args,
1603 tsubst_flags_t complain, tree in_decl)
1604{
1605 tree t0 = TREE_OPERAND (t, 0);
1606 tree r0 = tsubst_constraint (t0, args, complain, in_decl);
1607 if (r0 == error_mark_node)
1608 return error_mark_node;
1609 tree t1 = TREE_OPERAND (t, 1);
1610 tree r1 = tsubst_constraint (t1, args, complain, in_decl);
1611 if (r1 == error_mark_node)
1612 return error_mark_node;
1613 return build_nt (TREE_CODE (t), r0, r1);
1614}
1615
1616namespace {
1617
1618/* Substitute ARGS into the expression constraint T. */
1619
1620tree
1621tsubst_expr_constr (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1622{
1623 cp_unevaluated guard;
1624 tree expr = EXPR_CONSTR_EXPR (t);
1625 tree ret = tsubst_expr (expr, args, complain, in_decl, false);
1626 if (ret == error_mark_node)
1627 return error_mark_node;
1628 return build_nt (EXPR_CONSTR, ret);
1629}
1630
1631/* Substitute ARGS into the type constraint T. */
1632
1633tree
1634tsubst_type_constr (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1635{
1636 tree type = TYPE_CONSTR_TYPE (t);
1637 tree ret = tsubst (type, args, complain, in_decl);
1638 if (ret == error_mark_node)
1639 return error_mark_node;
1640 return build_nt (TYPE_CONSTR, ret);
1641}
1642
1643/* Substitute ARGS into the implicit conversion constraint T. */
1644
1645tree
1646tsubst_implicit_conversion_constr (tree t, tree args, tsubst_flags_t complain,
1647 tree in_decl)
1648{
1649 cp_unevaluated guard;
1650 tree expr = ICONV_CONSTR_EXPR (t);
1651 tree type = ICONV_CONSTR_TYPE (t);
1652 tree new_expr = tsubst_expr (expr, args, complain, in_decl, false);
1653 if (new_expr == error_mark_node)
1654 return error_mark_node;
1655 tree new_type = tsubst (type, args, complain, in_decl);
1656 if (new_type == error_mark_node)
1657 return error_mark_node;
1658 return build_nt (ICONV_CONSTR, new_expr, new_type);
1659}
1660
1661/* Substitute ARGS into the argument deduction constraint T. */
1662
1663tree
1664tsubst_argument_deduction_constr (tree t, tree args, tsubst_flags_t complain,
1665 tree in_decl)
1666{
1667 cp_unevaluated guard;
1668 tree expr = DEDUCT_CONSTR_EXPR (t);
1669 tree pattern = DEDUCT_CONSTR_PATTERN (t);
1670 tree autos = DEDUCT_CONSTR_PLACEHOLDER(t);
1671 tree new_expr = tsubst_expr (expr, args, complain, in_decl, false);
1672 if (new_expr == error_mark_node)
1673 return error_mark_node;
1674 /* It seems like substituting through the pattern will not affect the
1675 placeholders. We should (?) be able to reuse the existing list
1676 without any problems. If not, then we probably want to create a
1677 new list of placeholders and then instantiate the pattern using
1678 those. */
1679 tree new_pattern = tsubst (pattern, args, complain, in_decl);
1680 if (new_pattern == error_mark_node)
1681 return error_mark_node;
1682 return build_nt (DEDUCT_CONSTR, new_expr, new_pattern, autos);
1683}
1684
1685/* Substitute ARGS into the exception constraint T. */
1686
1687tree
1688tsubst_exception_constr (tree t, tree args, tsubst_flags_t complain,
1689 tree in_decl)
1690{
1691 cp_unevaluated guard;
1692 tree expr = EXCEPT_CONSTR_EXPR (t);
1693 tree ret = tsubst_expr (expr, args, complain, in_decl, false);
1694 if (ret == error_mark_node)
1695 return error_mark_node;
1696 return build_nt (EXCEPT_CONSTR, ret);
1697}
1698
1699/* A subroutine of tsubst_constraint_variables. Register local
1700 specializations for each of parameter in PARMS and its
1701 corresponding substituted constraint variable in VARS.
1702 Returns VARS. */
1703
1704tree
1705declare_constraint_vars (tree parms, tree vars)
1706{
1707 tree s = vars;
1708 for (tree t = parms; t; t = DECL_CHAIN (t))
1709 {
1710 if (DECL_PACK_P (t))
1711 {
1712 tree pack = extract_fnparm_pack (t, &s);
1713 register_local_specialization (pack, t);
1714 }
1715 else
1716 {
1717 register_local_specialization (s, t);
1718 s = DECL_CHAIN (s);
1719 }
1720 }
1721 return vars;
1722}
1723
1724/* A subroutine of tsubst_parameterized_constraint. Substitute ARGS
1725 into the parameter list T, producing a sequence of constraint
1726 variables, declared in the current scope.
1727
1728 Note that the caller must establish a local specialization stack
1729 prior to calling this function since this substitution will
1730 declare the substituted parameters. */
1731
1732tree
1733tsubst_constraint_variables (tree t, tree args,
1734 tsubst_flags_t complain, tree in_decl)
1735{
1736 /* Clear cp_unevaluated_operand across tsubst so that we get a proper chain
1737 of PARM_DECLs. */
1738 int saved_unevaluated_operand = cp_unevaluated_operand;
1739 cp_unevaluated_operand = 0;
1740 tree vars = tsubst (t, args, complain, in_decl);
1741 cp_unevaluated_operand = saved_unevaluated_operand;
1742 if (vars == error_mark_node)
1743 return error_mark_node;
1744 return declare_constraint_vars (t, vars);
1745}
1746
1747/* Substitute ARGS into the parameterized constraint T. */
1748
1749tree
1750tsubst_parameterized_constraint (tree t, tree args,
1751 tsubst_flags_t complain, tree in_decl)
1752{
1753 local_specialization_stack stack;
1754 tree vars = tsubst_constraint_variables (PARM_CONSTR_PARMS (t),
1755 args, complain, in_decl);
1756 if (vars == error_mark_node)
1757 return error_mark_node;
1758 tree expr = tsubst_constraint (PARM_CONSTR_OPERAND (t), args,
1759 complain, in_decl);
1760 if (expr == error_mark_node)
1761 return error_mark_node;
1762 return build_nt (PARM_CONSTR, vars, expr);
1763}
1764
1765/* Substitute ARGS into the simple requirement T. Note that
1766 substitution may result in an ill-formed expression without
1767 causing the program to be ill-formed. In such cases, the
1768 requirement wraps an error_mark_node. */
1769
1770inline tree
1771tsubst_simple_requirement (tree t, tree args,
1772 tsubst_flags_t complain, tree in_decl)
1773{
1774 ++processing_template_decl;
1775 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1776 --processing_template_decl;
1777 return finish_simple_requirement (expr);
1778}
1779
1780/* Substitute ARGS into the type requirement T. Note that
1781 substitution may result in an ill-formed type without
1782 causing the program to be ill-formed. In such cases, the
1783 requirement wraps an error_mark_node. */
1784
1785inline tree
1786tsubst_type_requirement (tree t, tree args,
1787 tsubst_flags_t complain, tree in_decl)
1788{
1789 ++processing_template_decl;
1790 tree type = tsubst (TREE_OPERAND (t, 0), args, complain, in_decl);
1791 --processing_template_decl;
1792 return finish_type_requirement (type);
1793}
1794
1795/* Substitute args into the compound requirement T. If substituting
1796 into either the expression or the type fails, the corresponding
1797 operands in the resulting node will be error_mark_node. This
1798 preserves a requirement for the purpose of partial ordering, but
1799 it will never be satisfied. */
1800
1801tree
1802tsubst_compound_requirement (tree t, tree args,
1803 tsubst_flags_t complain, tree in_decl)
1804{
1805 ++processing_template_decl;
1806 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1807 tree type = tsubst (TREE_OPERAND (t, 1), args, complain, in_decl);
1808 --processing_template_decl;
1809 bool noexcept_p = COMPOUND_REQ_NOEXCEPT_P (t);
1810 return finish_compound_requirement (expr, type, noexcept_p);
1811}
1812
1813/* Substitute ARGS into the nested requirement T. */
1814
1815tree
1816tsubst_nested_requirement (tree t, tree args,
1817 tsubst_flags_t complain, tree in_decl)
1818{
1819 ++processing_template_decl;
1820 tree expr = tsubst_expr (TREE_OPERAND (t, 0), args, complain, in_decl, false);
1821 --processing_template_decl;
1822 return finish_nested_requirement (expr);
1823}
1824
1825/* Substitute ARGS into the requirement T. */
1826
1827inline tree
1828tsubst_requirement (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1829{
1830 switch (TREE_CODE (t))
1831 {
1832 case SIMPLE_REQ:
1833 return tsubst_simple_requirement (t, args, complain, in_decl);
1834 case TYPE_REQ:
1835 return tsubst_type_requirement (t, args, complain, in_decl);
1836 case COMPOUND_REQ:
1837 return tsubst_compound_requirement (t, args, complain, in_decl);
1838 case NESTED_REQ:
1839 return tsubst_nested_requirement (t, args, complain, in_decl);
1840 default:
1841 gcc_unreachable ();
1842 }
1843 return error_mark_node;
1844}
1845
1846/* Substitute ARGS into the list of requirements T. Note that
1847 substitution failures here result in ill-formed programs. */
1848
1849tree
1850tsubst_requirement_body (tree t, tree args,
1851 tsubst_flags_t complain, tree in_decl)
1852{
1853 tree r = NULL_TREE;
1854 while (t)
1855 {
1856 tree e = tsubst_requirement (TREE_VALUE (t), args, complain, in_decl);
1857 if (e == error_mark_node)
1858 return error_mark_node;
1859 r = tree_cons (NULL_TREE, e, r);
1860 t = TREE_CHAIN (t);
1861 }
1862 /* Ensure that the order of constraints is the same as the original. */
1863 return nreverse (r);
1864}
1865
1866} /* namespace */
1867
1868/* Substitute ARGS into the requires expression T. Note that this
1869 results in the re-declaration of local parameters when
1870 substituting through the parameter list. If either substitution
1871 fails, the program is ill-formed. */
1872
1873tree
1874tsubst_requires_expr (tree t, tree args,
1875 tsubst_flags_t complain, tree in_decl)
1876{
1877 local_specialization_stack stack;
1878
1879 tree parms = TREE_OPERAND (t, 0);
1880 if (parms)
1881 {
1882 parms = tsubst_constraint_variables (parms, args, complain, in_decl);
1883 if (parms == error_mark_node)
1884 return error_mark_node;
1885 }
1886
1887 tree reqs = TREE_OPERAND (t, 1);
1888 reqs = tsubst_requirement_body (reqs, args, complain, in_decl);
1889 if (reqs == error_mark_node)
1890 return error_mark_node;
1891
1892 return finish_requires_expr (parms, reqs);
1893}
1894
1895/* Substitute ARGS into the constraint information CI, producing a new
1896 constraint record. */
1897
1898tree
1899tsubst_constraint_info (tree t, tree args,
1900 tsubst_flags_t complain, tree in_decl)
1901{
1902 if (!t || t == error_mark_node || !check_constraint_info (t))
1903 return NULL_TREE;
1904
1905 tree tmpl_constr = NULL_TREE;
1906 if (tree r = CI_TEMPLATE_REQS (t))
1907 tmpl_constr = tsubst_constraint (r, args, complain, in_decl);
1908
1909 tree decl_constr = NULL_TREE;
1910 if (tree r = CI_DECLARATOR_REQS (t))
1911 decl_constr = tsubst_constraint (r, args, complain, in_decl);
1912
1913 return build_constraints (tmpl_constr, decl_constr);
1914}
1915
1916/* Substitute ARGS into the constraint T. */
1917
1918tree
1919tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1920{
1921 if (t == NULL_TREE)
1922 return t;
1923 switch (TREE_CODE (t))
1924 {
1925 case PRED_CONSTR:
1926 return tsubst_predicate_constraint (t, args, complain, in_decl);
1927 case CHECK_CONSTR:
1928 return tsubst_check_constraint (t, args, complain, in_decl);
1929 case CONJ_CONSTR:
1930 case DISJ_CONSTR:
1931 return tsubst_logical_operator (t, args, complain, in_decl);
1932 case PARM_CONSTR:
1933 return tsubst_parameterized_constraint (t, args, complain, in_decl);
1934 case EXPR_CONSTR:
1935 return tsubst_expr_constr (t, args, complain, in_decl);
1936 case TYPE_CONSTR:
1937 return tsubst_type_constr (t, args, complain, in_decl);
1938 case ICONV_CONSTR:
1939 return tsubst_implicit_conversion_constr (t, args, complain, in_decl);
1940 case DEDUCT_CONSTR:
1941 return tsubst_argument_deduction_constr (t, args, complain, in_decl);
1942 case EXCEPT_CONSTR:
1943 return tsubst_exception_constr (t, args, complain, in_decl);
1944 default:
1945 gcc_unreachable ();
1946 }
1947 return error_mark_node;
1948}
1949
1950/*---------------------------------------------------------------------------
1951 Constraint satisfaction
1952---------------------------------------------------------------------------*/
1953
1954/* The following functions determine if a constraint, when
1955 substituting template arguments, is satisfied. For convenience,
1956 satisfaction reduces a constraint to either true or false (and
1957 nothing else). */
1958
1959namespace {
1960
1961tree satisfy_constraint_1 (tree, tree, tsubst_flags_t, tree);
1962
1963/* Check the constraint pack expansion. */
1964
1965tree
1966satisfy_pack_expansion (tree t, tree args,
1967 tsubst_flags_t complain, tree in_decl)
1968{
1969 /* Get the vector of satisfaction results.
1970 gen_elem_of_pack_expansion_instantiation will check that each element of
1971 the expansion is satisfied. */
1972 tree exprs = tsubst_pack_expansion (t, args, complain, in_decl);
1973
1974 if (exprs == error_mark_node)
1975 return boolean_false_node;
1976
1977 /* TODO: It might be better to normalize each expanded term
1978 and evaluate them separately. That would provide better
1979 opportunities for diagnostics. */
1980 for (int i = 0; i < TREE_VEC_LENGTH (exprs); ++i)
1981 if (TREE_VEC_ELT (exprs, i) != boolean_true_node)
1982 return boolean_false_node;
1983 return boolean_true_node;
1984}
1985
1986/* A predicate constraint is satisfied if its expression evaluates
1987 to true. If substitution into that node fails, the constraint
1988 is not satisfied ([temp.constr.pred]).
1989
1990 Note that a predicate constraint is a constraint expression
1991 of type bool. If neither of those are true, the program is
1992 ill-formed; they are not SFINAE'able errors. */
1993
1994tree
1995satisfy_predicate_constraint (tree t, tree args,
1996 tsubst_flags_t complain, tree in_decl)
1997{
1998 tree expr = TREE_OPERAND (t, 0);
1999
2000 /* We should never have a naked pack expansion in a predicate constraint. */
2001 gcc_assert (TREE_CODE (expr) != EXPR_PACK_EXPANSION);
2002
2003 /* If substitution into the expression fails, the constraint
2004 is not satisfied. */
2005 expr = tsubst_expr (expr, args, complain, in_decl, false);
2006 if (expr == error_mark_node)
2007 return boolean_false_node;
2008
2009 /* A predicate constraint shall have type bool. In some
2010 cases, substitution gives us const-qualified bool, which
2011 is also acceptable. */
2012 tree type = cv_unqualified (TREE_TYPE (expr));
2013 if (!same_type_p (type, boolean_type_node))
2014 {
2015 error_at (EXPR_LOC_OR_LOC (expr, input_location),
2016 "constraint %qE does not have type %qT",
2017 expr, boolean_type_node);
2018 return boolean_false_node;
2019 }
2020
2021 return cxx_constant_value (expr);
2022}
2023
2024/* A concept check constraint like C<CARGS> is satisfied if substituting ARGS
2025 into CARGS succeeds and C is satisfied for the resulting arguments. */
2026
2027tree
2028satisfy_check_constraint (tree t, tree args,
2029 tsubst_flags_t complain, tree in_decl)
2030{
2031 tree decl = CHECK_CONSTR_CONCEPT (t);
2032 tree tmpl = DECL_TI_TEMPLATE (decl);
2033 tree cargs = CHECK_CONSTR_ARGS (t);
2034
2035 /* Instantiate the concept check arguments. */
2036 tree targs = tsubst (cargs, args, tf_none, NULL_TREE);
2037 if (targs == error_mark_node)
2038 return boolean_false_node;
2039
2040 /* Search for a previous value. */
2041 if (tree prev = lookup_concept_satisfaction (tmpl, targs))
2042 return prev;
2043
2044 /* Expand the concept; failure here implies non-satisfaction. */
2045 tree def = expand_concept (decl, targs);
2046 if (def == error_mark_node)
2047 return memoize_concept_satisfaction (tmpl, args, boolean_false_node);
2048
2049 /* Recursively satisfy the constraint. */
2050 tree result = satisfy_constraint_1 (def, targs, complain, in_decl);
2051 return memoize_concept_satisfaction (tmpl, targs, result);
2052}
2053
2054/* Check an expression constraint. The constraint is satisfied if
2055 substitution succeeds ([temp.constr.expr]).
2056
2057 Note that the expression is unevaluated. */
2058
2059tree
2060satisfy_expression_constraint (tree t, tree args,
2061 tsubst_flags_t complain, tree in_decl)
2062{
2063 cp_unevaluated guard;
2064 deferring_access_check_sentinel deferring;
2065
2066 tree expr = EXPR_CONSTR_EXPR (t);
2067 tree check = tsubst_expr (expr, args, complain, in_decl, false);
2068 if (check == error_mark_node)
2069 return boolean_false_node;
2070 if (!perform_deferred_access_checks (tf_none))
2071 return boolean_false_node;
2072 return boolean_true_node;
2073}
2074
2075/* Check a type constraint. The constraint is satisfied if
2076 substitution succeeds. */
2077
2078inline tree
2079satisfy_type_constraint (tree t, tree args,
2080 tsubst_flags_t complain, tree in_decl)
2081{
2082 deferring_access_check_sentinel deferring;
2083 tree type = TYPE_CONSTR_TYPE (t);
2084 gcc_assert (TYPE_P (type) || type == error_mark_node);
2085 tree check = tsubst (type, args, complain, in_decl);
2086 if (error_operand_p (check))
2087 return boolean_false_node;
2088 if (!perform_deferred_access_checks (complain))
2089 return boolean_false_node;
2090 return boolean_true_node;
2091}
2092
2093/* Check an implicit conversion constraint. */
2094
2095tree
2096satisfy_implicit_conversion_constraint (tree t, tree args,
2097 tsubst_flags_t complain, tree in_decl)
2098{
2099 /* Don't tsubst as if we're processing a template. If we try
2100 to we can end up generating template-like expressions
2101 (e.g., modop-exprs) that aren't properly typed. */
2102 tree expr =
2103 tsubst_expr (ICONV_CONSTR_EXPR (t), args, complain, in_decl, false);
2104 if (expr == error_mark_node)
2105 return boolean_false_node;
2106
2107 /* Get the transformed target type. */
2108 tree type = tsubst (ICONV_CONSTR_TYPE (t), args, complain, in_decl);
2109 if (type == error_mark_node)
2110 return boolean_false_node;
2111
2112 /* Attempt the conversion as a direct initialization
2113 of the form TYPE <unspecified> = EXPR. */
2114 tree conv =
2115 perform_direct_initialization_if_possible (type, expr, false, complain);
2116 if (conv == NULL_TREE || conv == error_mark_node)
2117 return boolean_false_node;
2118 else
2119 return boolean_true_node;
2120}
2121
2122/* Check an argument deduction constraint. */
2123
2124tree
2125satisfy_argument_deduction_constraint (tree t, tree args,
2126 tsubst_flags_t complain, tree in_decl)
2127{
2128 /* Substitute through the expression. */
2129 tree expr = DEDUCT_CONSTR_EXPR (t);
2130 tree init = tsubst_expr (expr, args, complain, in_decl, false);
2131 if (expr == error_mark_node)
2132 return boolean_false_node;
2133
2134 /* Perform auto or decltype(auto) deduction to get the result. */
2135 tree pattern = DEDUCT_CONSTR_PATTERN (t);
2136 tree placeholder = DEDUCT_CONSTR_PLACEHOLDER (t);
2137 tree constr = PLACEHOLDER_TYPE_CONSTRAINTS (placeholder);
2138 tree type_canonical = TYPE_CANONICAL (placeholder);
2139 PLACEHOLDER_TYPE_CONSTRAINTS (placeholder)
2140 = tsubst_constraint (constr, args, complain|tf_partial, in_decl);
2141 TYPE_CANONICAL (placeholder) = NULL_TREE;
2142 tree type = do_auto_deduction (pattern, init, placeholder,
2143 complain, adc_requirement);
2144 PLACEHOLDER_TYPE_CONSTRAINTS (placeholder) = constr;
2145 TYPE_CANONICAL (placeholder) = type_canonical;
2146 if (type == error_mark_node)
2147 return boolean_false_node;
2148
2149 return boolean_true_node;
2150}
2151
2152/* Check an exception constraint. An exception constraint for an
2153 expression e is satisfied when noexcept(e) is true. */
2154
2155tree
2156satisfy_exception_constraint (tree t, tree args,
2157 tsubst_flags_t complain, tree in_decl)
2158{
2159 tree expr = EXCEPT_CONSTR_EXPR (t);
2160 tree check = tsubst_expr (expr, args, complain, in_decl, false);
2161 if (check == error_mark_node)
2162 return boolean_false_node;
2163
2164 if (expr_noexcept_p (check, complain))
2165 return boolean_true_node;
2166 else
2167 return boolean_false_node;
2168}
2169
2170/* Check a parameterized constraint. */
2171
2172tree
2173satisfy_parameterized_constraint (tree t, tree args,
2174 tsubst_flags_t complain, tree in_decl)
2175{
2176 local_specialization_stack stack;
2177 tree parms = PARM_CONSTR_PARMS (t);
2178 tree vars = tsubst_constraint_variables (parms, args, complain, in_decl);
2179 if (vars == error_mark_node)
2180 return boolean_false_node;
2181 tree constr = PARM_CONSTR_OPERAND (t);
2182 return satisfy_constraint_1 (constr, args, complain, in_decl);
2183}
2184
2185/* Check that the conjunction of constraints is satisfied. Note
2186 that if left operand is not satisfied, the right operand
2187 is not checked.
2188
2189 FIXME: Check that this wouldn't result in a user-defined
2190 operator. Note that this error is partially diagnosed in
2191 satisfy_predicate_constraint. It would be nice to diagnose
2192 the overload, but I don't think it's strictly necessary. */
2193
2194tree
2195satisfy_conjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2196{
2197 tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl);
2198 if (t0 == boolean_false_node)
2199 return boolean_false_node;
2200 return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
2201}
2202
2203/* Check that the disjunction of constraints is satisfied. Note
2204 that if the left operand is satisfied, the right operand is not
2205 checked. */
2206
2207tree
2208satisfy_disjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2209{
2210 tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl);
2211 if (t0 == boolean_true_node)
2212 return boolean_true_node;
2213 return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
2214}
2215
2216/* Dispatch to an appropriate satisfaction routine depending on the
2217 tree code of T. */
2218
2219tree
2220satisfy_constraint_1 (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2221{
2222 gcc_assert (!processing_template_decl);
2223
2224 if (!t)
2225 return boolean_false_node;
2226
2227 if (t == error_mark_node)
2228 return boolean_false_node;
2229
2230 switch (TREE_CODE (t))
2231 {
2232 case PRED_CONSTR:
2233 return satisfy_predicate_constraint (t, args, complain, in_decl);
2234
2235 case CHECK_CONSTR:
2236 return satisfy_check_constraint (t, args, complain, in_decl);
2237
2238 case EXPR_CONSTR:
2239 return satisfy_expression_constraint (t, args, complain, in_decl);
2240
2241 case TYPE_CONSTR:
2242 return satisfy_type_constraint (t, args, complain, in_decl);
2243
2244 case ICONV_CONSTR:
2245 return satisfy_implicit_conversion_constraint (t, args, complain, in_decl);
2246
2247 case DEDUCT_CONSTR:
2248 return satisfy_argument_deduction_constraint (t, args, complain, in_decl);
2249
2250 case EXCEPT_CONSTR:
2251 return satisfy_exception_constraint (t, args, complain, in_decl);
2252
2253 case PARM_CONSTR:
2254 return satisfy_parameterized_constraint (t, args, complain, in_decl);
2255
2256 case CONJ_CONSTR:
2257 return satisfy_conjunction (t, args, complain, in_decl);
2258
2259 case DISJ_CONSTR:
2260 return satisfy_disjunction (t, args, complain, in_decl);
2261
2262 case EXPR_PACK_EXPANSION:
2263 return satisfy_pack_expansion (t, args, complain, in_decl);
2264
2265 default:
2266 gcc_unreachable ();
2267 }
2268 return boolean_false_node;
2269}
2270
2271/* Check that the constraint is satisfied, according to the rules
2272 for that constraint. Note that each satisfy_* function returns
2273 true or false, depending on whether it is satisfied or not. */
2274
2275tree
2276satisfy_constraint (tree t, tree args)
2277{
2278 auto_timevar time (TV_CONSTRAINT_SAT);
2279
2280 /* Turn off template processing. Constraint satisfaction only applies
2281 to non-dependent terms, so we want to ensure full checking here. */
2282 processing_template_decl_sentinel proc (true);
2283
2284 /* Avoid early exit in tsubst and tsubst_copy from null args; since earlier
2285 substitution was done with processing_template_decl forced on, there will
2286 be expressions that still need semantic processing, possibly buried in
2287 decltype or a template argument. */
2288 if (args == NULL_TREE)
2289 args = make_tree_vec (1);
2290
2291 return satisfy_constraint_1 (t, args, tf_none, NULL_TREE);
2292}
2293
2294/* Check the associated constraints in CI against the given
2295 ARGS, returning true when the constraints are satisfied
2296 and false otherwise. */
2297
2298tree
2299satisfy_associated_constraints (tree ci, tree args)
2300{
2301 /* If there are no constraints then this is trivially satisfied. */
2302 if (!ci)
2303 return boolean_true_node;
2304
2305 /* If any arguments depend on template parameters, we can't
2306 check constraints. */
2307 if (args && uses_template_parms (args))
2308 return boolean_true_node;
2309
2310 /* Check if we've seen a previous result. */
2311 if (tree prev = lookup_constraint_satisfaction (ci, args))
2312 return prev;
2313
2314 /* Actually test for satisfaction. */
2315 tree result = satisfy_constraint (CI_ASSOCIATED_CONSTRAINTS (ci), args);
2316 return memoize_constraint_satisfaction (ci, args, result);
2317}
2318
2319} /* namespace */
2320
2321/* Evaluate the given constraint, returning boolean_true_node
2322 if the constraint is satisfied and boolean_false_node
2323 otherwise. */
2324
2325tree
2326evaluate_constraints (tree constr, tree args)
2327{
2328 gcc_assert (constraint_p (constr));
2329 return satisfy_constraint (constr, args);
2330}
2331
2332/* Evaluate the function concept FN by substituting its own args
2333 into its definition and evaluating that as the result. Returns
2334 boolean_true_node if the constraints are satisfied and
2335 boolean_false_node otherwise. */
2336
2337tree
2338evaluate_function_concept (tree fn, tree args)
2339{
2340 tree constr = build_nt (CHECK_CONSTR, fn, args);
2341 return satisfy_constraint (constr, args);
2342}
2343
2344/* Evaluate the variable concept VAR by substituting its own args into
2345 its initializer and checking the resulting constraint. Returns
2346 boolean_true_node if the constraints are satisfied and
2347 boolean_false_node otherwise. */
2348
2349tree
2350evaluate_variable_concept (tree var, tree args)
2351{
2352 tree constr = build_nt (CHECK_CONSTR, var, args);
2353 return satisfy_constraint (constr, args);
2354}
2355
2356/* Evaluate the given expression as if it were a predicate
2357 constraint. Returns boolean_true_node if the constraint
2358 is satisfied and boolean_false_node otherwise. */
2359
2360tree
2361evaluate_constraint_expression (tree expr, tree args)
2362{
2363 tree constr = normalize_expression (expr);
2364 return satisfy_constraint (constr, args);
2365}
2366
2367/* Returns true if the DECL's constraints are satisfied.
2368 This is used in cases where a declaration is formed but
2369 before it is used (e.g., overload resolution). */
2370
2371bool
2372constraints_satisfied_p (tree decl)
2373{
2374 /* Get the constraints to check for satisfaction. This depends
2375 on whether we're looking at a template specialization or not. */
2376 tree ci;
2377 tree args = NULL_TREE;
2378 if (tree ti = DECL_TEMPLATE_INFO (decl))
2379 {
2380 tree tmpl = TI_TEMPLATE (ti);
2381 ci = get_constraints (tmpl);
2382 int depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2383 args = get_innermost_template_args (TI_ARGS (ti), depth);
2384 }
2385 else
2386 {
2387 ci = get_constraints (decl);
2388 }
2389
2390 tree eval = satisfy_associated_constraints (ci, args);
2391 return eval == boolean_true_node;
2392}
2393
2394/* Returns true if the constraints are satisfied by ARGS.
2395 Here, T can be either a constraint or a constrained
2396 declaration. */
2397
2398bool
2399constraints_satisfied_p (tree t, tree args)
2400{
2401 tree eval;
2402 if (constraint_p (t))
2403 eval = evaluate_constraints (t, args);
2404 else
2405 eval = satisfy_associated_constraints (get_constraints (t), args);
2406 return eval == boolean_true_node;
2407}
2408
2409namespace
2410{
2411
2412/* Normalize EXPR and determine if the resulting constraint is
2413 satisfied by ARGS. Returns true if and only if the constraint
2414 is satisfied. This is used extensively by diagnostics to
2415 determine causes for failure. */
2416
2417inline bool
2418constraint_expression_satisfied_p (tree expr, tree args)
2419{
2420 return evaluate_constraint_expression (expr, args) == boolean_true_node;
2421}
2422
2423} /* namespace */
2424
2425/*---------------------------------------------------------------------------
2426 Semantic analysis of requires-expressions
2427---------------------------------------------------------------------------*/
2428
2429/* Finish a requires expression for the given PARMS (possibly
2430 null) and the non-empty sequence of requirements. */
2431tree
2432finish_requires_expr (tree parms, tree reqs)
2433{
2434 /* Modify the declared parameters by removing their context
2435 so they don't refer to the enclosing scope and explicitly
2436 indicating that they are constraint variables. */
2437 for (tree parm = parms; parm; parm = DECL_CHAIN (parm))
2438 {
2439 DECL_CONTEXT (parm) = NULL_TREE;
2440 CONSTRAINT_VAR_P (parm) = true;
2441 }
2442
2443 /* Build the node. */
2444 tree r = build_min (REQUIRES_EXPR, boolean_type_node, parms, reqs);
2445 TREE_SIDE_EFFECTS (r) = false;
2446 TREE_CONSTANT (r) = true;
2447 return r;
2448}
2449
2450/* Construct a requirement for the validity of EXPR. */
2451tree
2452finish_simple_requirement (tree expr)
2453{
2454 return build_nt (SIMPLE_REQ, expr);
2455}
2456
2457/* Construct a requirement for the validity of TYPE. */
2458tree
2459finish_type_requirement (tree type)
2460{
2461 return build_nt (TYPE_REQ, type);
2462}
2463
2464/* Construct a requirement for the validity of EXPR, along with
2465 its properties. if TYPE is non-null, then it specifies either
2466 an implicit conversion or argument deduction constraint,
2467 depending on whether any placeholders occur in the type name.
2468 NOEXCEPT_P is true iff the noexcept keyword was specified. */
2469tree
2470finish_compound_requirement (tree expr, tree type, bool noexcept_p)
2471{
2472 tree req = build_nt (COMPOUND_REQ, expr, type);
2473 COMPOUND_REQ_NOEXCEPT_P (req) = noexcept_p;
2474 return req;
2475}
2476
2477/* Finish a nested requirement. */
2478tree
2479finish_nested_requirement (tree expr)
2480{
2481 return build_nt (NESTED_REQ, expr);
2482}
2483
2484// Check that FN satisfies the structural requirements of a
2485// function concept definition.
2486tree
2487check_function_concept (tree fn)
2488{
2489 // Check that the function is comprised of only a single
2490 // return statement.
2491 tree body = DECL_SAVED_TREE (fn);
2492 if (TREE_CODE (body) == BIND_EXPR)
2493 body = BIND_EXPR_BODY (body);
2494
2495 // Sometimes a function call results in the creation of clean up
2496 // points. Allow these to be preserved in the body of the
2497 // constraint, as we might actually need them for some constexpr
2498 // evaluations.
2499 if (TREE_CODE (body) == CLEANUP_POINT_EXPR)
2500 body = TREE_OPERAND (body, 0);
2501
2502 /* Check that the definition is written correctly. */
2503 if (TREE_CODE (body) != RETURN_EXPR)
2504 {
2505 location_t loc = DECL_SOURCE_LOCATION (fn);
2506 if (TREE_CODE (body) == STATEMENT_LIST && !STATEMENT_LIST_HEAD (body))
2507 {
2508 if (seen_error ())
2509 /* The definition was probably erroneous, not empty. */;
2510 else
2511 error_at (loc, "definition of concept %qD is empty", fn);
2512 }
2513 else
2514 error_at (loc, "definition of concept %qD has multiple statements", fn);
2515 }
2516
2517 return NULL_TREE;
2518}
2519
2520
2521// Check that a constrained friend declaration function declaration,
2522// FN, is admissible. This is the case only when the declaration depends
2523// on template parameters and does not declare a specialization.
2524void
2525check_constrained_friend (tree fn, tree reqs)
2526{
2527 if (fn == error_mark_node)
2528 return;
2529 gcc_assert (TREE_CODE (fn) == FUNCTION_DECL);
2530
2531 // If there are not constraints, this cannot be an error.
2532 if (!reqs)
2533 return;
2534
2535 // Constrained friend functions that don't depend on template
2536 // arguments are effectively meaningless.
2537 if (!uses_template_parms (TREE_TYPE (fn)))
2538 {
2539 error_at (location_of (fn),
2540 "constrained friend does not depend on template parameters");
2541 return;
2542 }
2543}
2544
2545/*---------------------------------------------------------------------------
2546 Equivalence of constraints
2547---------------------------------------------------------------------------*/
2548
2549/* Returns true when A and B are equivalent constraints. */
2550bool
2551equivalent_constraints (tree a, tree b)
2552{
2553 gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
2554 gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
2555 return cp_tree_equal (a, b);
2556}
2557
2558/* Returns true if the template declarations A and B have equivalent
2559 constraints. This is the case when A's constraints subsume B's and
2560 when B's also constrain A's. */
2561bool
2562equivalently_constrained (tree d1, tree d2)
2563{
2564 gcc_assert (TREE_CODE (d1) == TREE_CODE (d2));
2565 return equivalent_constraints (get_constraints (d1), get_constraints (d2));
2566}
2567
2568/*---------------------------------------------------------------------------
2569 Partial ordering of constraints
2570---------------------------------------------------------------------------*/
2571
2572/* Returns true when the the constraints in A subsume those in B. */
2573
2574bool
2575subsumes_constraints (tree a, tree b)
2576{
2577 gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
2578 gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
2579 return subsumes (a, b);
2580}
2581
2582/* Returns true when the the constraints in A subsume those in B, but
2583 the constraints in B do not subsume the constraints in A. */
2584
2585bool
2586strictly_subsumes (tree a, tree b)
2587{
2588 return subsumes (a, b) && !subsumes (b, a);
2589}
2590
2591/* Determines which of the declarations, A or B, is more constrained.
2592 That is, which declaration's constraints subsume but are not subsumed
2593 by the other's?
2594
2595 Returns 1 if A is more constrained than B, -1 if B is more constrained
2596 than A, and 0 otherwise. */
2597
2598int
2599more_constrained (tree d1, tree d2)
2600{
2601 tree c1 = get_constraints (d1);
2602 tree c2 = get_constraints (d2);
2603 int winner = 0;
2604 if (subsumes_constraints (c1, c2))
2605 ++winner;
2606 if (subsumes_constraints (c2, c1))
2607 --winner;
2608 return winner;
2609}
2610
2611/* Returns true if D1 is at least as constrained as D2. That is, the
2612 associated constraints of D1 subsume those of D2, or both declarations
2613 are unconstrained. */
2614
2615bool
2616at_least_as_constrained (tree d1, tree d2)
2617{
2618 tree c1 = get_constraints (d1);
2619 tree c2 = get_constraints (d2);
2620 return subsumes_constraints (c1, c2);
2621}
2622
2623
2624/*---------------------------------------------------------------------------
2625 Constraint diagnostics
2626
2627FIXME: Normalize expressions into constraints before evaluating them.
2628This should be the general pattern for all such diagnostics.
2629---------------------------------------------------------------------------*/
2630
2631/* The number of detailed constraint failures. */
2632
2633int constraint_errors = 0;
2634
2635/* Do not generate errors after diagnosing this number of constraint
2636 failures.
2637
2638 FIXME: This is a really arbitrary number. Provide better control of
2639 constraint diagnostics with a command line option. */
2640
2641int constraint_thresh = 20;
2642
2643
2644/* Returns true if we should elide the diagnostic for a constraint failure.
2645 This is the case when the number of errors has exceeded the pre-configured
2646 threshold. */
2647
2648inline bool
2649elide_constraint_failure_p ()
2650{
2651 bool ret = constraint_thresh <= constraint_errors;
2652 ++constraint_errors;
2653 return ret;
2654}
2655
2656/* Returns the number of undiagnosed errors. */
2657
2658inline int
2659undiagnosed_constraint_failures ()
2660{
2661 return constraint_errors - constraint_thresh;
2662}
2663
2664/* The diagnosis of constraints performs a combination of normalization
2665 and satisfaction testing. We recursively walk through the conjunction or
2666 disjunction of associated constraints, testing each sub-constraint in
2667 turn. */
2668
2669namespace {
2670
2671void diagnose_constraint (location_t, tree, tree, tree);
2672
2673/* Emit a specific diagnostics for a failed trait. */
2674
2675void
2676diagnose_trait_expression (location_t loc, tree, tree cur, tree args)
2677{
2678 if (constraint_expression_satisfied_p (cur, args))
2679 return;
2680 if (elide_constraint_failure_p())
2681 return;
2682
2683 tree expr = PRED_CONSTR_EXPR (cur);
2684 ++processing_template_decl;
2685 expr = tsubst_expr (expr, args, tf_none, NULL_TREE, false);
2686 --processing_template_decl;
2687
2688 tree t1 = TRAIT_EXPR_TYPE1 (expr);
2689 tree t2 = TRAIT_EXPR_TYPE2 (expr);
2690 switch (TRAIT_EXPR_KIND (expr))
2691 {
2692 case CPTK_HAS_NOTHROW_ASSIGN:
2693 inform (loc, " %qT is not nothrow copy assignable", t1);
2694 break;
2695 case CPTK_HAS_NOTHROW_CONSTRUCTOR:
2696 inform (loc, " %qT is not nothrow default constructible", t1);
2697 break;
2698 case CPTK_HAS_NOTHROW_COPY:
2699 inform (loc, " %qT is not nothrow copy constructible", t1);
2700 break;
2701 case CPTK_HAS_TRIVIAL_ASSIGN:
2702 inform (loc, " %qT is not trivially copy assignable", t1);
2703 break;
2704 case CPTK_HAS_TRIVIAL_CONSTRUCTOR:
2705 inform (loc, " %qT is not trivially default constructible", t1);
2706 break;
2707 case CPTK_HAS_TRIVIAL_COPY:
2708 inform (loc, " %qT is not trivially copy constructible", t1);
2709 break;
2710 case CPTK_HAS_TRIVIAL_DESTRUCTOR:
2711 inform (loc, " %qT is not trivially destructible", t1);
2712 break;
2713 case CPTK_HAS_VIRTUAL_DESTRUCTOR:
2714 inform (loc, " %qT does not have a virtual destructor", t1);
2715 break;
2716 case CPTK_IS_ABSTRACT:
2717 inform (loc, " %qT is not an abstract class", t1);
2718 break;
2719 case CPTK_IS_BASE_OF:
2720 inform (loc, " %qT is not a base of %qT", t1, t2);
2721 break;
2722 case CPTK_IS_CLASS:
2723 inform (loc, " %qT is not a class", t1);
2724 break;
2725 case CPTK_IS_EMPTY:
2726 inform (loc, " %qT is not an empty class", t1);
2727 break;
2728 case CPTK_IS_ENUM:
2729 inform (loc, " %qT is not an enum", t1);
2730 break;
2731 case CPTK_IS_FINAL:
2732 inform (loc, " %qT is not a final class", t1);
2733 break;
2734 case CPTK_IS_LITERAL_TYPE:
2735 inform (loc, " %qT is not a literal type", t1);
2736 break;
2737 case CPTK_IS_POD:
2738 inform (loc, " %qT is not a POD type", t1);
2739 break;
2740 case CPTK_IS_POLYMORPHIC:
2741 inform (loc, " %qT is not a polymorphic type", t1);
2742 break;
2743 case CPTK_IS_SAME_AS:
2744 inform (loc, " %qT is not the same as %qT", t1, t2);
2745 break;
2746 case CPTK_IS_STD_LAYOUT:
2747 inform (loc, " %qT is not an standard layout type", t1);
2748 break;
2749 case CPTK_IS_TRIVIAL:
2750 inform (loc, " %qT is not a trivial type", t1);
2751 break;
2752 case CPTK_IS_UNION:
2753 inform (loc, " %qT is not a union", t1);
2754 break;
2755 default:
2756 gcc_unreachable ();
2757 }
2758}
2759
2760/* Diagnose the expression of a predicate constraint. */
2761
2762void
2763diagnose_other_expression (location_t loc, tree, tree cur, tree args)
2764{
2765 if (constraint_expression_satisfied_p (cur, args))
2766 return;
2767 if (elide_constraint_failure_p())
2768 return;
2769 inform (loc, "%qE evaluated to false", cur);
2770}
2771
2772/* Do our best to infer meaning from predicates. */
2773
2774inline void
2775diagnose_predicate_constraint (location_t loc, tree orig, tree cur, tree args)
2776{
2777 if (TREE_CODE (PRED_CONSTR_EXPR (cur)) == TRAIT_EXPR)
2778 diagnose_trait_expression (loc, orig, cur, args);
2779 else
2780 diagnose_other_expression (loc, orig, cur, args);
2781}
2782
2783/* Diagnose a failed pack expansion, possibly containing constraints. */
2784
2785void
2786diagnose_pack_expansion (location_t loc, tree, tree cur, tree args)
2787{
2788 if (constraint_expression_satisfied_p (cur, args))
2789 return;
2790 if (elide_constraint_failure_p())
2791 return;
2792
2793 /* Make sure that we don't have naked packs that we don't expect. */
2794 if (!same_type_p (TREE_TYPE (cur), boolean_type_node))
2795 {
2796 inform (loc, "invalid pack expansion in constraint %qE", cur);
2797 return;
2798 }
2799
2800 inform (loc, "in the expansion of %qE", cur);
2801
2802 /* Get the vector of expanded arguments. Note that n must not
2803 be 0 since this constraint is not satisfied. */
2804 ++processing_template_decl;
2805 tree exprs = tsubst_pack_expansion (cur, args, tf_none, NULL_TREE);
2806 --processing_template_decl;
2807 if (exprs == error_mark_node)
2808 {
2809 /* TODO: This error message could be better. */
2810 inform (loc, " substitution failure occurred during expansion");
2811 return;
2812 }
2813
2814 /* Check each expanded constraint separately. */
2815 int n = TREE_VEC_LENGTH (exprs);
2816 for (int i = 0; i < n; ++i)
2817 {
2818 tree expr = TREE_VEC_ELT (exprs, i);
2819 if (!constraint_expression_satisfied_p (expr, args))
2820 inform (loc, " %qE was not satisfied", expr);
2821 }
2822}
2823
2824/* Diagnose a potentially unsatisfied concept check constraint DECL<CARGS>.
2825 Parameters are as for diagnose_constraint. */
2826
2827void
2828diagnose_check_constraint (location_t loc, tree orig, tree cur, tree args)
2829{
2830 if (constraints_satisfied_p (cur, args))
2831 return;
2832
2833 tree decl = CHECK_CONSTR_CONCEPT (cur);
2834 tree cargs = CHECK_CONSTR_ARGS (cur);
2835 tree tmpl = DECL_TI_TEMPLATE (decl);
2836 tree check = build_nt (CHECK_CONSTR, decl, cargs);
2837
2838 /* Instantiate the concept check arguments. */
2839 tree targs = tsubst (cargs, args, tf_none, NULL_TREE);
2840 if (targs == error_mark_node)
2841 {
2842 if (elide_constraint_failure_p ())
2843 return;
2844 inform (loc, "invalid use of the concept %qE", check);
2845 tsubst (cargs, args, tf_warning_or_error, NULL_TREE);
2846 return;
2847 }
2848
2849 tree sub = build_tree_list (tmpl, targs);
2850 /* Update to the expanded definitions. */
2851 cur = expand_concept (decl, targs);
2852 if (cur == error_mark_node)
2853 {
2854 if (elide_constraint_failure_p ())
2855 return;
2856 inform (loc, "in the expansion of concept %<%E %S%>", check, sub);
2857 cur = get_concept_definition (decl);
2858 tsubst_expr (cur, targs, tf_warning_or_error, NULL_TREE, false);
2859 return;
2860 }
2861
2862 orig = get_concept_definition (CHECK_CONSTR_CONCEPT (orig));
2863 orig = normalize_expression (orig);
2864
2865 location_t dloc = DECL_SOURCE_LOCATION (decl);
2866 inform (dloc, "within %qS", sub);
2867 diagnose_constraint (dloc, orig, cur, targs);
2868}
2869
2870/* Diagnose a potentially unsatisfied conjunction or disjunction. Parameters
2871 are as for diagnose_constraint. */
2872
2873void
2874diagnose_logical_constraint (location_t loc, tree orig, tree cur, tree args)
2875{
2876 tree t0 = TREE_OPERAND (cur, 0);
2877 tree t1 = TREE_OPERAND (cur, 1);
2878 if (!constraints_satisfied_p (t0, args))
2879 diagnose_constraint (loc, TREE_OPERAND (orig, 0), t0, args);
2880 else if (TREE_CODE (orig) == TRUTH_ORIF_EXPR)
2881 return;
2882 if (!constraints_satisfied_p (t1, args))
2883 diagnose_constraint (loc, TREE_OPERAND (orig, 1), t1, args);
2884}
2885
2886/* Diagnose a potential expression constraint failure. */
2887
2888void
2889diagnose_expression_constraint (location_t loc, tree orig, tree cur, tree args)
2890{
2891 if (constraints_satisfied_p (cur, args))
2892 return;
2893 if (elide_constraint_failure_p())
2894 return;
2895
2896 tree expr = EXPR_CONSTR_EXPR (orig);
2897 inform (loc, "the required expression %qE would be ill-formed", expr);
2898
2899 // TODO: We should have a flag that controls this substitution.
2900 // I'm finding it very useful for resolving concept check errors.
2901
2902 // inform (input_location, "==== BEGIN DUMP ====");
2903 // tsubst_expr (EXPR_CONSTR_EXPR (orig), args, tf_warning_or_error, NULL_TREE, false);
2904 // inform (input_location, "==== END DUMP ====");
2905}
2906
2907/* Diagnose a potentially failed type constraint. */
2908
2909void
2910diagnose_type_constraint (location_t loc, tree orig, tree cur, tree args)
2911{
2912 if (constraints_satisfied_p (cur, args))
2913 return;
2914 if (elide_constraint_failure_p())
2915 return;
2916
2917 tree type = TYPE_CONSTR_TYPE (orig);
2918 inform (loc, "the required type %qT would be ill-formed", type);
2919}
2920
2921/* Diagnose a potentially unsatisfied conversion constraint. */
2922
2923void
2924diagnose_implicit_conversion_constraint (location_t loc, tree orig, tree cur,
2925 tree args)
2926{
2927 if (constraints_satisfied_p (cur, args))
2928 return;
2929
2930 /* The expression and type will previously have been substituted into,
2931 and therefore may already be an error. Also, we will have already
2932 diagnosed substitution failures into an expression since this must be
2933 part of a compound requirement. */
2934 tree expr = ICONV_CONSTR_EXPR (cur);
2935 if (error_operand_p (expr))
2936 return;
2937
2938 /* Don't elide a previously diagnosed failure. */
2939 if (elide_constraint_failure_p())
2940 return;
2941
2942 tree type = ICONV_CONSTR_TYPE (cur);
2943 if (error_operand_p (type))
2944 {
2945 inform (loc, "substitution into type %qT failed",
2946 ICONV_CONSTR_TYPE (orig));
2947 return;
2948 }
2949
2950 inform(loc, "%qE is not implicitly convertible to %qT", expr, type);
2951}
2952
2953/* Diagnose an argument deduction constraint. */
2954
2955void
2956diagnose_argument_deduction_constraint (location_t loc, tree orig, tree cur,
2957 tree args)
2958{
2959 if (constraints_satisfied_p (cur, args))
2960 return;
2961
2962 /* The expression and type will previously have been substituted into,
2963 and therefore may already be an error. Also, we will have already
2964 diagnosed substution failures into an expression since this must be
2965 part of a compound requirement. */
2966 tree expr = DEDUCT_CONSTR_EXPR (cur);
2967 if (error_operand_p (expr))
2968 return;
2969
2970 /* Don't elide a previously diagnosed failure. */
2971 if (elide_constraint_failure_p ())
2972 return;
2973
2974 tree pattern = DEDUCT_CONSTR_PATTERN (cur);
2975 if (error_operand_p (pattern))
2976 {
2977 inform (loc, "substitution into type %qT failed",
2978 DEDUCT_CONSTR_PATTERN (orig));
2979 return;
2980 }
2981
2982 inform (loc, "unable to deduce placeholder type %qT from %qE",
2983 pattern, expr);
2984}
2985
2986/* Diagnose an exception constraint. */
2987
2988void
2989diagnose_exception_constraint (location_t loc, tree orig, tree cur, tree args)
2990{
2991 if (constraints_satisfied_p (cur, args))
2992 return;
2993 if (elide_constraint_failure_p ())
2994 return;
2995
2996 /* Rebuild a noexcept expression. */
2997 tree expr = EXCEPT_CONSTR_EXPR (cur);
2998 if (error_operand_p (expr))
2999 return;
3000
3001 inform (loc, "%qE evaluated to false", EXCEPT_CONSTR_EXPR (orig));
3002}
3003
3004/* Diagnose a potentially unsatisfied parameterized constraint. */
3005
3006void
3007diagnose_parameterized_constraint (location_t loc, tree orig, tree cur,
3008 tree args)
3009{
3010 if (constraints_satisfied_p (cur, args))
3011 return;
3012
3013 local_specialization_stack stack;
3014 tree parms = PARM_CONSTR_PARMS (cur);
3015 tree vars = tsubst_constraint_variables (parms, args, tf_warning_or_error,
3016 NULL_TREE);
3017 if (vars == error_mark_node)
3018 {
3019 if (elide_constraint_failure_p ())
3020 return;
3021
3022 /* TODO: Check which variable failed and use orig to diagnose
3023 that substitution error. */
3024 inform (loc, "failed to instantiate constraint variables");
3025 return;
3026 }
3027
3028 /* TODO: It would be better write these in a list. */
3029 while (vars)
3030 {
3031 inform (loc, " with %q#D", vars);
3032 vars = TREE_CHAIN (vars);
3033 }
3034 orig = PARM_CONSTR_OPERAND (orig);
3035 cur = PARM_CONSTR_OPERAND (cur);
3036 return diagnose_constraint (loc, orig, cur, args);
3037}
3038
3039/* Diagnose the constraint CUR for the given ARGS. This is only ever invoked
3040 on the associated constraints, so we can only have conjunctions of
3041 predicate constraints. The ORIGinal (dependent) constructs follow
3042 the current constraints to enable better diagnostics. Note that ORIG
3043 and CUR must be the same kinds of node, except when CUR is an error. */
3044
3045void
3046diagnose_constraint (location_t loc, tree orig, tree cur, tree args)
3047{
3048 switch (TREE_CODE (cur))
3049 {
3050 case EXPR_CONSTR:
3051 diagnose_expression_constraint (loc, orig, cur, args);
3052 break;
3053
3054 case TYPE_CONSTR:
3055 diagnose_type_constraint (loc, orig, cur, args);
3056 break;
3057
3058 case ICONV_CONSTR:
3059 diagnose_implicit_conversion_constraint (loc, orig, cur, args);
3060 break;
3061
3062 case DEDUCT_CONSTR:
3063 diagnose_argument_deduction_constraint (loc, orig, cur, args);
3064 break;
3065
3066 case EXCEPT_CONSTR:
3067 diagnose_exception_constraint (loc, orig, cur, args);
3068 break;
3069
3070 case CONJ_CONSTR:
3071 case DISJ_CONSTR:
3072 diagnose_logical_constraint (loc, orig, cur, args);
3073 break;
3074
3075 case PRED_CONSTR:
3076 diagnose_predicate_constraint (loc, orig, cur, args);
3077 break;
3078
3079 case PARM_CONSTR:
3080 diagnose_parameterized_constraint (loc, orig, cur, args);
3081 break;
3082
3083 case CHECK_CONSTR:
3084 diagnose_check_constraint (loc, orig, cur, args);
3085 break;
3086
3087 case EXPR_PACK_EXPANSION:
3088 diagnose_pack_expansion (loc, orig, cur, args);
3089 break;
3090
3091 case ERROR_MARK:
3092 /* TODO: Can we improve the diagnostic with the original? */
3093 inform (input_location, "ill-formed constraint");
3094 break;
3095
3096 default:
3097 gcc_unreachable ();
3098 break;
3099 }
3100}
3101
3102/* Diagnose the reason(s) why ARGS do not satisfy the constraints
3103 of declaration DECL. */
3104
3105void
3106diagnose_declaration_constraints (location_t loc, tree decl, tree args)
3107{
3108 inform (loc, " constraints not satisfied");
3109
3110 /* Constraints are attached to the template. */
3111 if (tree ti = DECL_TEMPLATE_INFO (decl))
3112 {
3113 decl = TI_TEMPLATE (ti);
3114 if (!args)
3115 args = TI_ARGS (ti);
3116 }
3117
3118 /* Recursively diagnose the associated constraints. */
3119 tree ci = get_constraints (decl);
3120 tree t = CI_ASSOCIATED_CONSTRAINTS (ci);
3121 diagnose_constraint (loc, t, t, args);
3122}
3123
3124} // namespace
3125
3126/* Emit diagnostics detailing the failure ARGS to satisfy the
3127 constraints of T. Here, T can be either a constraint
3128 or a declaration. */
3129
3130void
3131diagnose_constraints (location_t loc, tree t, tree args)
3132{
3133 constraint_errors = 0;
3134
3135 if (constraint_p (t))
3136 diagnose_constraint (loc, t, t, args);
3137 else if (DECL_P (t))
3138 diagnose_declaration_constraints (loc, t, args);
3139 else
3140 gcc_unreachable ();
3141
3142 /* Note the number of elided failures. */
3143 int n = undiagnosed_constraint_failures ();
3144 if (n > 0)
3145 inform (loc, "... and %d more constraint errors not shown", n);
3146}
3147