1 /* Processing rules for constraints.
2    Copyright (C) 2013-2018 Free Software Foundation, Inc.
3    Contributed by Andrew Sutton (andrew.n.sutton@gmail.com)
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11 
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16 
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20 
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "timevar.h"
26 #include "hash-set.h"
27 #include "machmode.h"
28 #include "vec.h"
29 #include "double-int.h"
30 #include "input.h"
31 #include "alias.h"
32 #include "symtab.h"
33 #include "wide-int.h"
34 #include "inchash.h"
35 #include "tree.h"
36 #include "stringpool.h"
37 #include "attribs.h"
38 #include "intl.h"
39 #include "flags.h"
40 #include "cp-tree.h"
41 #include "c-family/c-common.h"
42 #include "c-family/c-objc.h"
43 #include "cp-objcp-common.h"
44 #include "tree-inline.h"
45 #include "decl.h"
46 #include "toplev.h"
47 #include "type-utils.h"
48 
49 /*---------------------------------------------------------------------------
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 
56 static inline bool
constraint_p(tree_code c)57 constraint_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 
67 bool
constraint_p(tree t)68 constraint_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 
85 tree
conjoin_constraints(tree a,tree b)86 conjoin_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 
101 tree
conjoin_constraints(tree t)102 conjoin_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 
114 bool
function_concept_check_p(tree t)115 function_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 
133 bool
contains_wildcard_p(tree args)134 contains_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 
148 inline tree
build_call_check(tree id)149 build_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 
164 tree
build_variable_check(tree id)165 build_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.
202 static tree
resolve_constraint_check(tree ovl,tree args)203 resolve_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.
253 tree
resolve_constraint_check(tree call)254 resolve_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 
289 tree
resolve_variable_concept_check(tree id)290 resolve_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 
323 bool
deduce_constrained_parameter(tree expr,tree & check,tree & proto)324 deduce_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.
350 static tree
deduce_concept_introduction(tree expr)351 deduce_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 
366 namespace {
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 
392 enum 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 
399 void learn_implications(tree, tree, implication_context);
400 
401 void
learn_implication(tree parent,tree child,implication_context cxt)402 learn_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 
419 void
learn_logical_operation(tree parent,tree constr,implication_context cxt)420 learn_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 
426 void
learn_implications(tree parent,tree constr,implication_context cxt)427 learn_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 
453 void
learn_implications(tree tmpl,tree args,tree constr)454 learn_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 
480 tree
get_returned_expression(tree fn)481 get_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 
497 tree
get_variable_initializer(tree var)498 get_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 
508 tree
get_concept_definition(tree decl)509 get_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 
518 int expansion_level = 0;
519 
520 struct expanding_concept_sentinel
521 {
expanding_concept_sentinel__anonddff6ee50111::expanding_concept_sentinel522   expanding_concept_sentinel ()
523   {
524     ++expansion_level;
525   }
526 
~expanding_concept_sentinel__anonddff6ee50111::expanding_concept_sentinel527   ~expanding_concept_sentinel()
528   {
529     --expansion_level;
530   }
531 };
532 
533 
534 } /* namespace */
535 
536 /* Returns true when a concept is being expanded.  */
537 
538 bool
expanding_concept()539 expanding_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 
547 tree
expand_concept(tree decl,tree args)548 expand_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 
580 This set of functions will transform an expression into a constraint
581 in a sequence of steps. Normalization does not not look into concept
582 definitions.
583 ---------------------------------------------------------------------------*/
584 
585 /* Transform a logical-or or logical-and expression into either
586    a conjunction or disjunction. */
587 
588 tree
normalize_logical_operation(tree t,tree_code c)589 normalize_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 
599 inline tree
normalize_simple_requirement(tree t)600 normalize_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 
607 inline tree
normalize_type_requirement(tree t)608 normalize_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 
621 tree
normalize_compound_requirement(tree t)622 normalize_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 
659 inline tree
normalize_nested_requirement(tree t)660 normalize_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 
667 tree
normalize_requirement(tree t)668 normalize_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 
693 tree
normalize_requirements(tree t)694 normalize_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 
709 tree
normalize_requires_expression(tree t)710 normalize_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 
722 tree
normalize_template_id_expression(tree t)723 normalize_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 
756 tree
normalize_call_expression(tree t)757 normalize_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 
785 bool
check_for_logical_overloads(tree t)786 check_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 
821 tree
normalize_atom(tree t)822 normalize_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 
854 tree
push_down_pack_expansion(tree exp,tree pat)855 push_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 
882 tree
normalize_pack_expansion(tree t)883 normalize_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 
891 tree
normalize_any_expression(tree t)892 normalize_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.  */
918 tree
normalize_any_statement(tree t)919 normalize_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 
933 tree
normalize_any_declaration(tree t)934 normalize_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 
948 tree
normalize_expression(tree t)949 normalize_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 
990 tree 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 
995 inline tree
normalize_conjunction(tree t)996 normalize_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 
1006 inline tree
normalize_disjunction(tree t)1007 normalize_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 
1020 tree
normalize_predicate_constraint(tree t)1021 normalize_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 
1033 tree
normalize_parameterized_constraint(tree t)1034 normalize_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 
1045 tree
normalize_constraint(tree t)1046 normalize_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.
1092 tree
current_template_constraints(void)1093 current_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.
1104 tree
associate_classtype_constraints(tree type)1105 associate_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 
1139 namespace {
1140 
1141 // Create an empty constraint info block.
1142 inline tree_constraint_info*
build_constraint_info()1143 build_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 
1158 tree
build_constraints(tree tmpl_reqs,tree decl_reqs)1159 build_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 
1175 namespace {
1176 
1177 /* Construct a sequence of template arguments by prepending
1178    ARG to REST. Either ARG or REST may be null. */
1179 tree
build_concept_check_arguments(tree arg,tree rest)1180 build_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. */
1214 tree
build_concept_check(tree target,tree arg,tree rest)1215 build_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.  */
1232 tree
build_constrained_parameter(tree cnc,tree proto,tree args)1233 build_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. */
1255 tree
finish_shorthand_constraint(tree decl,tree constr)1256 finish_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. */
1301 tree
get_shorthand_constraints(tree parms)1302 get_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.
1318 static tree
process_introduction_parm(tree parameter_list,tree src_parm)1319 process_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.  */
1391 tree
finish_template_introduction(tree tmpl_decl,tree intro_list)1392 finish_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 
1445 void
placeholder_extract_concept_and_args(tree t,tree & tmpl,tree & args)1446 placeholder_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 
1473 bool
equivalent_placeholder_constraints(tree c1,tree c2)1474 equivalent_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 
1518 hashval_t
hash_placeholder_constraint(tree c)1519 hash_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. */
1560 tree
tsubst_predicate_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)1561 tsubst_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 
1573 tree
tsubst_check_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)1574 tsubst_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 
1601 tree
tsubst_logical_operator(tree t,tree args,tsubst_flags_t complain,tree in_decl)1602 tsubst_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 
1616 namespace {
1617 
1618 /* Substitute ARGS into the expression constraint T.  */
1619 
1620 tree
tsubst_expr_constr(tree t,tree args,tsubst_flags_t complain,tree in_decl)1621 tsubst_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 
1633 tree
tsubst_type_constr(tree t,tree args,tsubst_flags_t complain,tree in_decl)1634 tsubst_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 
1645 tree
tsubst_implicit_conversion_constr(tree t,tree args,tsubst_flags_t complain,tree in_decl)1646 tsubst_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 
1663 tree
tsubst_argument_deduction_constr(tree t,tree args,tsubst_flags_t complain,tree in_decl)1664 tsubst_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 
1687 tree
tsubst_exception_constr(tree t,tree args,tsubst_flags_t complain,tree in_decl)1688 tsubst_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 
1704 tree
declare_constraint_vars(tree parms,tree vars)1705 declare_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 
1732 tree
tsubst_constraint_variables(tree t,tree args,tsubst_flags_t complain,tree in_decl)1733 tsubst_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 
1749 tree
tsubst_parameterized_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)1750 tsubst_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 
1770 inline tree
tsubst_simple_requirement(tree t,tree args,tsubst_flags_t complain,tree in_decl)1771 tsubst_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 
1785 inline tree
tsubst_type_requirement(tree t,tree args,tsubst_flags_t complain,tree in_decl)1786 tsubst_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 
1801 tree
tsubst_compound_requirement(tree t,tree args,tsubst_flags_t complain,tree in_decl)1802 tsubst_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 
1815 tree
tsubst_nested_requirement(tree t,tree args,tsubst_flags_t complain,tree in_decl)1816 tsubst_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 
1827 inline tree
tsubst_requirement(tree t,tree args,tsubst_flags_t complain,tree in_decl)1828 tsubst_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 
1849 tree
tsubst_requirement_body(tree t,tree args,tsubst_flags_t complain,tree in_decl)1850 tsubst_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 
1873 tree
tsubst_requires_expr(tree t,tree args,tsubst_flags_t complain,tree in_decl)1874 tsubst_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 
1898 tree
tsubst_constraint_info(tree t,tree args,tsubst_flags_t complain,tree in_decl)1899 tsubst_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 
1918 tree
tsubst_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)1919 tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl)
1920 {
1921   if (t == NULL_TREE || t == error_mark_node)
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 
1959 namespace {
1960 
1961 tree satisfy_constraint_1 (tree, tree, tsubst_flags_t, tree);
1962 
1963 /* Check the constraint pack expansion.  */
1964 
1965 tree
satisfy_pack_expansion(tree t,tree args,tsubst_flags_t complain,tree in_decl)1966 satisfy_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 
1994 tree
satisfy_predicate_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)1995 satisfy_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 
2027 tree
satisfy_check_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)2028 satisfy_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 
2059 tree
satisfy_expression_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)2060 satisfy_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 
2078 inline tree
satisfy_type_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)2079 satisfy_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 
2095 tree
satisfy_implicit_conversion_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)2096 satisfy_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 
2124 tree
satisfy_argument_deduction_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)2125 satisfy_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 
2155 tree
satisfy_exception_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)2156 satisfy_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 
2172 tree
satisfy_parameterized_constraint(tree t,tree args,tsubst_flags_t complain,tree in_decl)2173 satisfy_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 
2194 tree
satisfy_conjunction(tree t,tree args,tsubst_flags_t complain,tree in_decl)2195 satisfy_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 
2207 tree
satisfy_disjunction(tree t,tree args,tsubst_flags_t complain,tree in_decl)2208 satisfy_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 
2219 tree
satisfy_constraint_1(tree t,tree args,tsubst_flags_t complain,tree in_decl)2220 satisfy_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 
2275 tree
satisfy_constraint(tree t,tree args)2276 satisfy_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 
2298 tree
satisfy_associated_constraints(tree ci,tree args)2299 satisfy_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 
2325 tree
evaluate_constraints(tree constr,tree args)2326 evaluate_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 
2337 tree
evaluate_function_concept(tree fn,tree args)2338 evaluate_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 
2349 tree
evaluate_variable_concept(tree var,tree args)2350 evaluate_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 
2360 tree
evaluate_constraint_expression(tree expr,tree args)2361 evaluate_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 
2371 bool
constraints_satisfied_p(tree decl)2372 constraints_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 
2398 bool
constraints_satisfied_p(tree t,tree args)2399 constraints_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 
2409 namespace
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 
2417 inline bool
constraint_expression_satisfied_p(tree expr,tree args)2418 constraint_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. */
2431 tree
finish_requires_expr(tree parms,tree reqs)2432 finish_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. */
2451 tree
finish_simple_requirement(tree expr)2452 finish_simple_requirement (tree expr)
2453 {
2454   return build_nt (SIMPLE_REQ, expr);
2455 }
2456 
2457 /* Construct a requirement for the validity of TYPE. */
2458 tree
finish_type_requirement(tree type)2459 finish_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. */
2469 tree
finish_compound_requirement(tree expr,tree type,bool noexcept_p)2470 finish_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. */
2478 tree
finish_nested_requirement(tree expr)2479 finish_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.
2486 tree
check_function_concept(tree fn)2487 check_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.
2524 void
check_constrained_friend(tree fn,tree reqs)2525 check_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.  */
2550 bool
equivalent_constraints(tree a,tree b)2551 equivalent_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.  */
2561 bool
equivalently_constrained(tree d1,tree d2)2562 equivalently_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 
2574 bool
subsumes_constraints(tree a,tree b)2575 subsumes_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 
2585 bool
strictly_subsumes(tree a,tree b)2586 strictly_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 
2598 int
more_constrained(tree d1,tree d2)2599 more_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 
2615 bool
at_least_as_constrained(tree d1,tree d2)2616 at_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 
2627 FIXME: Normalize expressions into constraints before evaluating them.
2628 This should be the general pattern for all such diagnostics.
2629 ---------------------------------------------------------------------------*/
2630 
2631 /* The number of detailed constraint failures.  */
2632 
2633 int 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 
2641 int 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 
2648 inline bool
elide_constraint_failure_p()2649 elide_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 
2658 inline int
undiagnosed_constraint_failures()2659 undiagnosed_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 
2669 namespace {
2670 
2671 void diagnose_constraint (location_t, tree, tree, tree);
2672 
2673 /* Emit a specific diagnostics for a failed trait.  */
2674 
2675 void
diagnose_trait_expression(location_t loc,tree,tree cur,tree args)2676 diagnose_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 
2762 void
diagnose_other_expression(location_t loc,tree,tree cur,tree args)2763 diagnose_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 
2774 inline void
diagnose_predicate_constraint(location_t loc,tree orig,tree cur,tree args)2775 diagnose_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 
2785 void
diagnose_pack_expansion(location_t loc,tree,tree cur,tree args)2786 diagnose_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 
2827 void
diagnose_check_constraint(location_t loc,tree orig,tree cur,tree args)2828 diagnose_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 
2873 void
diagnose_logical_constraint(location_t loc,tree orig,tree cur,tree args)2874 diagnose_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 
2888 void
diagnose_expression_constraint(location_t loc,tree orig,tree cur,tree args)2889 diagnose_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 
2909 void
diagnose_type_constraint(location_t loc,tree orig,tree cur,tree args)2910 diagnose_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 
2923 void
diagnose_implicit_conversion_constraint(location_t loc,tree orig,tree cur,tree args)2924 diagnose_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 
2955 void
diagnose_argument_deduction_constraint(location_t loc,tree orig,tree cur,tree args)2956 diagnose_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 
2988 void
diagnose_exception_constraint(location_t loc,tree orig,tree cur,tree args)2989 diagnose_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 
3006 void
diagnose_parameterized_constraint(location_t loc,tree orig,tree cur,tree args)3007 diagnose_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 
3045 void
diagnose_constraint(location_t loc,tree orig,tree cur,tree args)3046 diagnose_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 
3105 void
diagnose_declaration_constraints(location_t loc,tree decl,tree args)3106 diagnose_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 
3130 void
diagnose_constraints(location_t loc,tree t,tree args)3131 diagnose_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