constraint.cc source code [gcc/cp/constraint.cc]

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