1	/* Processing rules for constraints.
2	Copyright (C) 2013-2023 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 (t: 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 (expr: lhs) && check_constraint_atom (expr: 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 (start: lhs.get_start (), finish: 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, code: 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, code: 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 (loc: 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, tf_none))
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 (t: 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 (call: 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, tf_none);
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 (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 (expr: check, check&: con, proto))
470	return std::make_pair (error_mark_node, NULL_TREE);
471
472	return std::make_pair (x&: con, y&: 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 (var: decl);
525	if (TREE_CODE (decl) == FUNCTION_DECL)
526	return get_returned_expression (fn: 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: ctx_parms ());
652	context = tree_cons (map, expr, context);
653	}
654	in_decl = get_concept_check_template (t: 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	/* Data types and hash functions for caching the normal form of a concept-id.
702	This essentially memoizes calls to normalize_concept_check. */
703
704	struct GTY((for_user)) norm_entry
705	{
706	/* The CONCEPT_DECL of the concept-id. */
707	tree tmpl;
708	/* The arguments of the concept-id. */
709	tree args;
710	/* The normal form of the concept-id. */
711	tree norm;
712	};
713
714	struct norm_hasher : ggc_ptr_hash<norm_entry>
715	{
716	static hashval_t hash (norm_entry *e)
717	{
718	++comparing_specializations;
719	hashval_t val = iterative_hash_template_arg (arg: e->tmpl, val: 0);
720	val = iterative_hash_template_arg (arg: e->args, val);
721	--comparing_specializations;
722	return val;
723	}
724
725	static bool equal (norm_entry *e1, norm_entry *e2)
726	{
727	++comparing_specializations;
728	bool eq = e1->tmpl == e2->tmpl
729	&& template_args_equal (e1->args, e2->args);
730	--comparing_specializations;
731	return eq;
732	}
733	};
734
735	static GTY((deletable)) hash_table<norm_hasher> *norm_cache;
736
737	/* Normalize the concept check CHECK where ARGS are the
738	arguments to be substituted into CHECK's arguments. */
739
740	static tree
741	normalize_concept_check (tree check, tree args, norm_info info)
742	{
743	tree id = unpack_concept_check (t: check);
744	tree tmpl = TREE_OPERAND (id, 0);
745	tree targs = TREE_OPERAND (id, 1);
746
747	/* A function concept is wrapped in an overload. */
748	if (TREE_CODE (tmpl) == OVERLOAD)
749	{
750	/* TODO: Can we diagnose this error during parsing? */
751	if (TREE_CODE (check) == TEMPLATE_ID_EXPR)
752	error_at (EXPR_LOC_OR_LOC (check, input_location),
753	"function concept must be called");
754	tmpl = OVL_FIRST (tmpl);
755	}
756
757	/* Substitute through the arguments of the concept check. */
758	if (args)
759	targs = tsubst_template_args (targs, args, info.complain, info.in_decl);
760	if (targs == error_mark_node)
761	return error_mark_node;
762	if (template_args_equal (targs, generic_targs_for (tmpl)))
763	/* Canonicalize generic arguments as NULL_TREE, as an optimization. */
764	targs = NULL_TREE;
765
766	/* Build the substitution for the concept definition. */
767	tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl));
768	if (targs && args)
769	/* As an optimization, coerce the arguments only if necessary
770	(i.e. if they were substituted). */
771	targs = coerce_template_parms (parms, targs, tmpl, tf_none);
772	if (targs == error_mark_node)
773	return error_mark_node;
774
775	if (!norm_cache)
776	norm_cache = hash_table<norm_hasher>::create_ggc (n: 31);
777	norm_entry *entry = nullptr;
778	if (!info.generate_diagnostics ())
779	{
780	/* Cache the normal form of the substituted concept-id (when not
781	diagnosing). */
782	norm_entry elt = {.tmpl: tmpl, .args: targs, NULL_TREE};
783	norm_entry **slot = norm_cache->find_slot (value: &elt, insert: INSERT);
784	if (*slot)
785	return (*slot)->norm;
786	entry = ggc_alloc<norm_entry> ();
787	*entry = elt;
788	*slot = entry;
789	}
790
791	tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl));
792	info.update_context (expr: check, args);
793	tree norm = normalize_expression (def, targs, info);
794	if (entry)
795	entry->norm = norm;
796	return norm;
797	}
798
799	/* Used by normalize_atom to cache ATOMIC_CONSTRs. */
800
801	static GTY((deletable)) hash_table<atom_hasher> *atom_cache;
802
803	/* The normal form of an atom depends on the expression. The normal
804	form of a function call to a function concept is a check constraint
805	for that concept. The normal form of a reference to a variable
806	concept is a check constraint for that concept. Otherwise, the
807	constraint is a predicate constraint. */
808
809	static tree
810	normalize_atom (tree t, tree args, norm_info info)
811	{
812	/* Concept checks are not atomic. */
813	if (concept_check_p (t))
814	return normalize_concept_check (check: t, args, info);
815
816	/* Build the parameter mapping for the atom. */
817	tree map = build_parameter_mapping (expr: t, args, ctx_parms: info.ctx_parms ());
818
819	/* Build a new info object for the atom. */
820	tree ci = build_tree_list (t, info.context);
821
822	tree atom = build1 (ATOMIC_CONSTR, ci, map);
823
824	/* Remember whether the expression of this atomic constraint belongs to
825	a concept definition by inspecting in_decl, which should always be set
826	in this case either by norm_info::update_context (when recursing into a
827	concept-id during normalization) or by normalize_concept_definition
828	(when starting out with a concept-id). */
829	if (info.in_decl && concept_definition_p (t: info.in_decl))
830	ATOMIC_CONSTR_EXPR_FROM_CONCEPT_P (atom) = true;
831
832	if (!info.generate_diagnostics ())
833	{
834	/* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal
835	later can cheaply compare two atoms using just pointer equality. */
836	if (!atom_cache)
837	atom_cache = hash_table<atom_hasher>::create_ggc (n: 31);
838	tree *slot = atom_cache->find_slot (value: atom, insert: INSERT);
839	if (*slot)
840	return *slot;
841
842	/* Find all template parameters used in the targets of the parameter
843	mapping, and store a list of them in the TREE_TYPE of the mapping.
844	This list will be used by sat_hasher to determine the subset of
845	supplied template arguments that the satisfaction value of the atom
846	depends on. */
847	if (map)
848	{
849	tree targets = make_tree_vec (list_length (map));
850	int i = 0;
851	for (tree node = map; node; node = TREE_CHAIN (node))
852	{
853	tree target = TREE_PURPOSE (node);
854	TREE_VEC_ELT (targets, i++) = target;
855	}
856	tree target_parms = find_template_parameters (targets,
857	info.initial_parms);
858	TREE_TYPE (map) = target_parms;
859	}
860
861	*slot = atom;
862	}
863	return atom;
864	}
865
866	/* Returns the normal form of an expression. */
867
868	static tree
869	normalize_expression (tree t, tree args, norm_info info)
870	{
871	if (!t)
872	return NULL_TREE;
873
874	if (t == error_mark_node)
875	return error_mark_node;
876
877	switch (TREE_CODE (t))
878	{
879	case TRUTH_ANDIF_EXPR:
880	return normalize_logical_operation (t, args, c: CONJ_CONSTR, info);
881	case TRUTH_ORIF_EXPR:
882	return normalize_logical_operation (t, args, c: DISJ_CONSTR, info);
883	default:
884	return normalize_atom (t, args, info);
885	}
886	}
887
888	/* Cache of the normalized form of constraints. Marked as deletable because it
889	can all be recalculated. */
890	static GTY((deletable)) hash_map<tree,tree> *normalized_map;
891
892	static tree
893	get_normalized_constraints (tree t, norm_info info)
894	{
895	auto_timevar time (TV_CONSTRAINT_NORM);
896	return normalize_expression (t, NULL_TREE, info);
897	}
898
899	/* Returns the normalized constraints from a constraint-info object
900	or NULL_TREE if the constraints are null. IN_DECL provides the
901	declaration to which the constraints belong. */
902
903	static tree
904	get_normalized_constraints_from_info (tree ci, tree in_decl, bool diag = false)
905	{
906	if (ci == NULL_TREE)
907	return NULL_TREE;
908
909	/* Substitution errors during normalization are fatal. */
910	++processing_template_decl;
911	norm_info info (in_decl, diag ? tf_norm : tf_none);
912	tree t = get_normalized_constraints (CI_ASSOCIATED_CONSTRAINTS (ci), info);
913	--processing_template_decl;
914
915	return t;
916	}
917
918	/* Returns the normalized constraints for the declaration D. */
919
920	static tree
921	get_normalized_constraints_from_decl (tree d, bool diag = false)
922	{
923	tree tmpl;
924	tree decl;
925
926	/* For inherited constructors, consider the original declaration;
927	it has the correct template information attached. */
928	d = strip_inheriting_ctors (d);
929
930	if (regenerated_lambda_fn_p (d))
931	{
932	/* If this lambda was regenerated, DECL_TEMPLATE_PARMS doesn't contain
933	all in-scope template parameters, but the lambda from which it was
934	ultimately regenerated does, so use that instead. */
935	tree lambda = CLASSTYPE_LAMBDA_EXPR (DECL_CONTEXT (d));
936	lambda = most_general_lambda (lambda);
937	d = lambda_function (lambda);
938	}
939
940	if (TREE_CODE (d) == TEMPLATE_DECL)
941	{
942	tmpl = d;
943	decl = DECL_TEMPLATE_RESULT (tmpl);
944	}
945	else
946	{
947	if (tree ti = DECL_TEMPLATE_INFO (d))
948	tmpl = TI_TEMPLATE (ti);
949	else
950	tmpl = NULL_TREE;
951	decl = d;
952	}
953
954	/* Get the most general template for the declaration, and compute
955	arguments from that. This ensures that the arguments used for
956	normalization are always template parameters and not arguments
957	used for outer specializations. For example:
958
959	template<typename T>
960	struct S {
961	template<typename U> requires C<T, U> void f(U);
962	};
963
964	S<int>::f(0);
965
966	When we normalize the requirements for S<int>::f, we want the
967	arguments to be {T, U}, not {int, U}. One reason for this is that
968	accepting the latter causes the template parameter level of U
969	to be reduced in a way that makes it overly difficult substitute
970	concrete arguments (i.e., eventually {int, int} during satisfaction. */
971	if (tmpl)
972	{
973	if (DECL_LANG_SPECIFIC(tmpl) && !DECL_TEMPLATE_SPECIALIZATION (tmpl))
974	tmpl = most_general_template (tmpl);
975	}
976
977	d = tmpl ? tmpl : decl;
978
979	/* If we're not diagnosing errors, use cached constraints, if any. */
980	if (!diag)
981	if (tree *p = hash_map_safe_get (h: normalized_map, k: d))
982	return *p;
983
984	tree norm = NULL_TREE;
985	if (tree ci = get_constraints (d))
986	{
987	push_access_scope_guard pas (decl);
988	norm = get_normalized_constraints_from_info (ci, in_decl: tmpl, diag);
989	}
990
991	if (!diag)
992	hash_map_safe_put<hm_ggc> (h&: normalized_map, k: d, v: norm);
993
994	return norm;
995	}
996
997	/* Returns the normal form of TMPL's definition. */
998
999	static tree
1000	normalize_concept_definition (tree tmpl, bool diag)
1001	{
1002	if (!norm_cache)
1003	norm_cache = hash_table<norm_hasher>::create_ggc (n: 31);
1004	norm_entry entry = {.tmpl: tmpl, NULL_TREE, NULL_TREE};
1005
1006	if (!diag)
1007	if (norm_entry *found = norm_cache->find (value: &entry))
1008	return found->norm;
1009
1010	gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
1011	tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl));
1012	++processing_template_decl;
1013	norm_info info (tmpl, diag ? tf_norm : tf_none);
1014	tree norm = get_normalized_constraints (t: def, info);
1015	--processing_template_decl;
1016
1017	if (!diag)
1018	{
1019	norm_entry **slot = norm_cache->find_slot (value: &entry, insert: INSERT);
1020	entry.norm = norm;
1021	*slot = ggc_alloc<norm_entry> ();
1022	**slot = entry;
1023	}
1024
1025	return norm;
1026	}
1027
1028	/* Normalize an EXPR as a constraint. */
1029
1030	static tree
1031	normalize_constraint_expression (tree expr, norm_info info)
1032	{
1033	if (!expr || expr == error_mark_node)
1034	return expr;
1035
1036	if (!info.generate_diagnostics ())
1037	if (tree *p = hash_map_safe_get (h: normalized_map, k: expr))
1038	return *p;
1039
1040	++processing_template_decl;
1041	tree norm = get_normalized_constraints (t: expr, info);
1042	--processing_template_decl;
1043
1044	if (!info.generate_diagnostics ())
1045	hash_map_safe_put<hm_ggc> (h&: normalized_map, k: expr, v: norm);
1046
1047	return norm;
1048	}
1049
1050	/* 17.4.1.2p2. Two constraints are identical if they are formed
1051	from the same expression and the targets of the parameter mapping
1052	are equivalent. */
1053
1054	bool
1055	atomic_constraints_identical_p (tree t1, tree t2)
1056	{
1057	gcc_assert (TREE_CODE (t1) == ATOMIC_CONSTR);
1058	gcc_assert (TREE_CODE (t2) == ATOMIC_CONSTR);
1059
1060	if (ATOMIC_CONSTR_EXPR (t1) != ATOMIC_CONSTR_EXPR (t2))
1061	return false;
1062
1063	if (!parameter_mapping_equivalent_p (t1, t2))
1064	return false;
1065
1066	return true;
1067	}
1068
1069	/* True if T1 and T2 are equivalent, meaning they have the same syntactic
1070	structure and all corresponding constraints are identical. */
1071
1072	bool
1073	constraints_equivalent_p (tree t1, tree t2)
1074	{
1075	gcc_assert (CONSTR_P (t1));
1076	gcc_assert (CONSTR_P (t2));
1077
1078	if (TREE_CODE (t1) != TREE_CODE (t2))
1079	return false;
1080
1081	switch (TREE_CODE (t1))
1082	{
1083	case CONJ_CONSTR:
1084	case DISJ_CONSTR:
1085	if (!constraints_equivalent_p (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1086	return false;
1087	if (!constraints_equivalent_p (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1)))
1088	return false;
1089	break;
1090	case ATOMIC_CONSTR:
1091	if (!atomic_constraints_identical_p(t1, t2))
1092	return false;
1093	break;
1094	default:
1095	gcc_unreachable ();
1096	}
1097	return true;
1098	}
1099
1100	/* Compute the hash value for T. */
1101
1102	hashval_t
1103	hash_atomic_constraint (tree t)
1104	{
1105	gcc_assert (TREE_CODE (t) == ATOMIC_CONSTR);
1106
1107	/* Hash the identity of the expression. */
1108	hashval_t val = htab_hash_pointer (ATOMIC_CONSTR_EXPR (t));
1109
1110	/* Hash the targets of the parameter map. */
1111	tree p = ATOMIC_CONSTR_MAP (t);
1112	while (p)
1113	{
1114	val = iterative_hash_template_arg (TREE_PURPOSE (p), val);
1115	p = TREE_CHAIN (p);
1116	}
1117
1118	return val;
1119	}
1120
1121	namespace inchash
1122	{
1123
1124	static void
1125	add_constraint (tree t, hash& h)
1126	{
1127	h.add_int(TREE_CODE (t));
1128	switch (TREE_CODE (t))
1129	{
1130	case CONJ_CONSTR:
1131	case DISJ_CONSTR:
1132	add_constraint (TREE_OPERAND (t, 0), h);
1133	add_constraint (TREE_OPERAND (t, 1), h);
1134	break;
1135	case ATOMIC_CONSTR:
1136	h.merge_hash (other: hash_atomic_constraint (t));
1137	break;
1138	default:
1139	gcc_unreachable ();
1140	}
1141	}
1142
1143	}
1144
1145	/* Computes a hash code for the constraint T. */
1146
1147	hashval_t
1148	iterative_hash_constraint (tree t, hashval_t val)
1149	{
1150	gcc_assert (CONSTR_P (t));
1151	inchash::hash h (val);
1152	inchash::add_constraint (t, h);
1153	return h.end ();
1154	}
1155
1156	// -------------------------------------------------------------------------- //
1157	// Constraint Semantic Processing
1158	//
1159	// The following functions are called by the parser and substitution rules
1160	// to create and evaluate constraint-related nodes.
1161
1162	// The constraints associated with the current template parameters.
1163	tree
1164	current_template_constraints (void)
1165	{
1166	if (!current_template_parms)
1167	return NULL_TREE;
1168	tree tmpl_constr = TEMPLATE_PARMS_CONSTRAINTS (current_template_parms);
1169	return build_constraints (tmpl_constr, NULL_TREE);
1170	}
1171
1172	/* If the recently parsed TYPE declares or defines a template or
1173	template specialization, get its corresponding constraints from the
1174	current template parameters and bind them to TYPE's declaration. */
1175
1176	tree
1177	associate_classtype_constraints (tree type)
1178	{
1179	if (!type || type == error_mark_node || !CLASS_TYPE_P (type))
1180	return type;
1181
1182	/* An explicit class template specialization has no template parameters. */
1183	if (!current_template_parms)
1184	return type;
1185
1186	if (CLASSTYPE_IS_TEMPLATE (type) || CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1187	{
1188	tree decl = TYPE_STUB_DECL (type);
1189	tree ci = current_template_constraints ();
1190
1191	/* An implicitly instantiated member template declaration already
1192	has associated constraints. If it is defined outside of its
1193	class, then we need match these constraints against those of
1194	original declaration. */
1195	if (tree orig_ci = get_constraints (decl))
1196	{
1197	if (int extra_levels = (TMPL_PARMS_DEPTH (current_template_parms)
1198	- TMPL_ARGS_DEPTH (TYPE_TI_ARGS (type))))
1199	{
1200	/* If there is a discrepancy between the current template depth
1201	and the template depth of the original declaration, then we
1202	must be redeclaring a class template as part of a friend
1203	declaration within another class template. Before matching
1204	constraints, we need to reduce the template parameter level
1205	within the current constraints via substitution. */
1206	tree outer_gtargs = template_parms_to_args (current_template_parms);
1207	TREE_VEC_LENGTH (outer_gtargs) = extra_levels;
1208	ci = tsubst_constraint_info (ci, outer_gtargs, tf_none, NULL_TREE);
1209	}
1210	if (!equivalent_constraints (ci, orig_ci))
1211	{
1212	error ("%qT does not match original declaration", type);
1213	tree tmpl = CLASSTYPE_TI_TEMPLATE (type);
1214	location_t loc = DECL_SOURCE_LOCATION (tmpl);
1215	inform (loc, "original template declaration here");
1216	/* Fall through, so that we define the type anyway. */
1217	}
1218	return type;
1219	}
1220	set_constraints (decl, ci);
1221	}
1222	return type;
1223	}
1224
1225	/* Create an empty constraint info block. */
1226
1227	static inline tree_constraint_info*
1228	build_constraint_info ()
1229	{
1230	return (tree_constraint_info *)make_node (CONSTRAINT_INFO);
1231	}
1232
1233	/* Build a constraint-info object that contains the associated constraints
1234	of a declaration. This also includes the declaration's template
1235	requirements (TREQS) and any trailing requirements for a function
1236	declarator (DREQS). Note that both TREQS and DREQS must be constraints.
1237
1238	If the declaration has neither template nor declaration requirements
1239	this returns NULL_TREE, indicating an unconstrained declaration. */
1240
1241	tree
1242	build_constraints (tree tr, tree dr)
1243	{
1244	if (!tr && !dr)
1245	return NULL_TREE;
1246
1247	tree_constraint_info* ci = build_constraint_info ();
1248	ci->template_reqs = tr;
1249	ci->declarator_reqs = dr;
1250	ci->associated_constr = combine_constraint_expressions (lhs: tr, rhs: dr);
1251
1252	return (tree)ci;
1253	}
1254
1255	/* Add constraint RHS to the end of CONSTRAINT_INFO ci. */
1256
1257	tree
1258	append_constraint (tree ci, tree rhs)
1259	{
1260	tree tr = ci ? CI_TEMPLATE_REQS (ci) : NULL_TREE;
1261	tree dr = ci ? CI_DECLARATOR_REQS (ci) : NULL_TREE;
1262	dr = combine_constraint_expressions (lhs: dr, rhs);
1263	if (ci)
1264	{
1265	CI_DECLARATOR_REQS (ci) = dr;
1266	tree ac = combine_constraint_expressions (lhs: tr, rhs: dr);
1267	CI_ASSOCIATED_CONSTRAINTS (ci) = ac;
1268	}
1269	else
1270	ci = build_constraints (tr, dr);
1271	return ci;
1272	}
1273
1274	/* A mapping from declarations to constraint information. */
1275
1276	static GTY ((cache)) decl_tree_cache_map *decl_constraints;
1277
1278	/* Returns the template constraints of declaration T. If T is not
1279	constrained, return NULL_TREE. Note that T must be non-null. */
1280
1281	tree
1282	get_constraints (const_tree t)
1283	{
1284	if (!flag_concepts)
1285	return NULL_TREE;
1286	if (!decl_constraints)
1287	return NULL_TREE;
1288
1289	gcc_assert (DECL_P (t));
1290	if (TREE_CODE (t) == TEMPLATE_DECL)
1291	t = DECL_TEMPLATE_RESULT (t);
1292	tree* found = decl_constraints->get (CONST_CAST_TREE (t));
1293	if (found)
1294	return *found;
1295	else
1296	return NULL_TREE;
1297	}
1298
1299	/* Associate the given constraint information CI with the declaration
1300	T. If T is a template, then the constraints are associated with
1301	its underlying declaration. Don't build associations if CI is
1302	NULL_TREE. */
1303
1304	void
1305	set_constraints (tree t, tree ci)
1306	{
1307	if (!ci)
1308	return;
1309	gcc_assert (t && flag_concepts);
1310	if (TREE_CODE (t) == TEMPLATE_DECL)
1311	t = DECL_TEMPLATE_RESULT (t);
1312	bool found = hash_map_safe_put<hm_ggc> (h&: decl_constraints, k: t, v: ci);
1313	gcc_assert (!found);
1314	}
1315
1316	/* Remove the associated constraints of the declaration T. */
1317
1318	void
1319	remove_constraints (tree t)
1320	{
1321	gcc_checking_assert (DECL_P (t));
1322	if (TREE_CODE (t) == TEMPLATE_DECL)
1323	t = DECL_TEMPLATE_RESULT (t);
1324
1325	if (decl_constraints)
1326	decl_constraints->remove (k: t);
1327	}
1328
1329	/* If DECL is a friend, substitute into REQS to produce requirements suitable
1330	for declaration matching. */
1331
1332	tree
1333	maybe_substitute_reqs_for (tree reqs, const_tree decl)
1334	{
1335	if (reqs == NULL_TREE)
1336	return NULL_TREE;
1337
1338	decl = STRIP_TEMPLATE (decl);
1339	if (DECL_UNIQUE_FRIEND_P (decl) && DECL_TEMPLATE_INFO (decl))
1340	{
1341	tree tmpl = DECL_TI_TEMPLATE (decl);
1342	tree outer_args = outer_template_args (decl);
1343	processing_template_decl_sentinel s;
1344	if (PRIMARY_TEMPLATE_P (tmpl)
1345	|| uses_template_parms (outer_args))
1346	++processing_template_decl;
1347	reqs = tsubst_constraint (reqs, outer_args,
1348	tf_warning_or_error, NULL_TREE);
1349	}
1350	return reqs;
1351	}
1352
1353	/* Returns the trailing requires clause of the declarator of
1354	a template declaration T or NULL_TREE if none. */
1355
1356	tree
1357	get_trailing_function_requirements (tree t)
1358	{
1359	tree ci = get_constraints (t);
1360	if (!ci)
1361	return NULL_TREE;
1362	return CI_DECLARATOR_REQS (ci);
1363	}
1364
1365	/* Construct a sequence of template arguments by prepending
1366	ARG to REST. Either ARG or REST may be null. */
1367	static tree
1368	build_concept_check_arguments (tree arg, tree rest)
1369	{
1370	gcc_assert (rest ? TREE_CODE (rest) == TREE_VEC : true);
1371	tree args;
1372	if (arg)
1373	{
1374	int n = rest ? TREE_VEC_LENGTH (rest) : 0;
1375	args = make_tree_vec (n + 1);
1376	TREE_VEC_ELT (args, 0) = arg;
1377	if (rest)
1378	for (int i = 0; i < n; ++i)
1379	TREE_VEC_ELT (args, i + 1) = TREE_VEC_ELT (rest, i);
1380	int def = rest ? GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (rest) : 0;
1381	SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args, def + 1);
1382	}
1383	else
1384	{
1385	args = rest;
1386	}
1387	return args;
1388	}
1389
1390	/* Builds an id-expression of the form `C<Args...>()` where C is a function
1391	concept. */
1392
1393	static tree
1394	build_function_check (tree tmpl, tree args, tsubst_flags_t /*complain*/)
1395	{
1396	if (TREE_CODE (tmpl) == TEMPLATE_DECL)
1397	{
1398	/* If we just got a template, wrap it in an overload so it looks like any
1399	other template-id. */
1400	tmpl = ovl_make (fn: tmpl);
1401	TREE_TYPE (tmpl) = boolean_type_node;
1402	}
1403
1404	/* Perform function concept resolution now so we always have a single
1405	function of the overload set (even if we started with only one; the
1406	resolution function converts template arguments). Note that we still
1407	wrap this in an overload set so we don't upset other parts of the
1408	compiler that expect template-ids referring to function concepts
1409	to have an overload set. */
1410	tree info = resolve_function_concept_overload (ovl: tmpl, args);
1411	if (info == error_mark_node)
1412	return error_mark_node;
1413	if (!info)
1414	{
1415	error ("no matching concepts for %qE", tmpl);
1416	return error_mark_node;
1417	}
1418	args = TREE_PURPOSE (info);
1419	tmpl = DECL_TI_TEMPLATE (TREE_VALUE (info));
1420
1421	/* Rebuild the singleton overload set; mark the type bool. */
1422	tmpl = ovl_make (fn: tmpl, NULL_TREE);
1423	TREE_TYPE (tmpl) = boolean_type_node;
1424
1425	/* Build the id-expression around the overload set. */
1426	tree id = build2 (TEMPLATE_ID_EXPR, boolean_type_node, tmpl, args);
1427
1428	/* Finally, build the call expression around the overload. */
1429	++processing_template_decl;
1430	vec<tree, va_gc> *fargs = make_tree_vector ();
1431	tree call = build_min_nt_call_vec (id, fargs);
1432	TREE_TYPE (call) = boolean_type_node;
1433	release_tree_vector (fargs);
1434	--processing_template_decl;
1435
1436	return call;
1437	}
1438
1439	/* Builds an id-expression of the form `C<Args...>` where C is a variable
1440	concept. */
1441
1442	static tree
1443	build_variable_check (tree tmpl, tree args, tsubst_flags_t complain)
1444	{
1445	gcc_assert (variable_concept_p (tmpl));
1446	gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
1447	tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl));
1448	args = coerce_template_parms (parms, args, tmpl, complain);
1449	if (args == error_mark_node)
1450	return error_mark_node;
1451	return build2 (TEMPLATE_ID_EXPR, boolean_type_node, tmpl, args);
1452	}
1453
1454	/* Builds an id-expression of the form `C<Args...>` where C is a standard
1455	concept. */
1456
1457	static tree
1458	build_standard_check (tree tmpl, tree args, tsubst_flags_t complain)
1459	{
1460	gcc_assert (standard_concept_p (tmpl));
1461	gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
1462	if (TREE_DEPRECATED (DECL_TEMPLATE_RESULT (tmpl)))
1463	warn_deprecated_use (DECL_TEMPLATE_RESULT (tmpl), NULL_TREE);
1464	tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl));
1465	args = coerce_template_parms (parms, args, tmpl, complain);
1466	if (args == error_mark_node)
1467	return error_mark_node;
1468	return build2 (TEMPLATE_ID_EXPR, boolean_type_node, tmpl, args);
1469	}
1470
1471	/* Construct an expression that checks TARGET using ARGS. */
1472
1473	tree
1474	build_concept_check (tree target, tree args, tsubst_flags_t complain)
1475	{
1476	return build_concept_check (target, NULL_TREE, args, complain);
1477	}
1478
1479	/* Construct an expression that checks the concept given by DECL. If
1480	concept_definition_p (DECL) is false, this returns null. */
1481
1482	tree
1483	build_concept_check (tree decl, tree arg, tree rest, tsubst_flags_t complain)
1484	{
1485	tree args = build_concept_check_arguments (arg, rest);
1486
1487	if (standard_concept_p (t: decl))
1488	return build_standard_check (tmpl: decl, args, complain);
1489	if (variable_concept_p (t: decl))
1490	return build_variable_check (tmpl: decl, args, complain);
1491	if (function_concept_p (t: decl))
1492	return build_function_check (tmpl: decl, args, complain);
1493
1494	return error_mark_node;
1495	}
1496
1497	/* Build a template-id that can participate in a concept check. */
1498
1499	static tree
1500	build_concept_id (tree decl, tree args)
1501	{
1502	tree check = build_concept_check (target: decl, args, complain: tf_warning_or_error);
1503	if (check == error_mark_node)
1504	return error_mark_node;
1505	return unpack_concept_check (t: check);
1506	}
1507
1508	/* Build a template-id that can participate in a concept check, preserving
1509	the source location of the original template-id. */
1510
1511	tree
1512	build_concept_id (tree expr)
1513	{
1514	gcc_assert (TREE_CODE (expr) == TEMPLATE_ID_EXPR);
1515	tree id = build_concept_id (TREE_OPERAND (expr, 0), TREE_OPERAND (expr, 1));
1516	protected_set_expr_location (id, cp_expr_location (t_: expr));
1517	return id;
1518	}
1519
1520	/* Build as template-id with a placeholder that can be used as a
1521	type constraint.
1522
1523	Note that this will diagnose errors if the initial concept check
1524	cannot be built. */
1525
1526	tree
1527	build_type_constraint (tree decl, tree args, tsubst_flags_t complain)
1528	{
1529	tree wildcard = build_nt (WILDCARD_DECL);
1530	++processing_template_decl;
1531	tree check = build_concept_check (decl, arg: wildcard, rest: args, complain);
1532	--processing_template_decl;
1533	if (check == error_mark_node)
1534	return error_mark_node;
1535	return unpack_concept_check (t: check);
1536	}
1537
1538	/* Returns a TYPE_DECL that contains sufficient information to
1539	build a template parameter of the same kind as PROTO and
1540	constrained by the concept declaration CNC. Note that PROTO
1541	is the first template parameter of CNC.
1542
1543	If specified, ARGS provides additional arguments to the
1544	constraint check. */
1545	tree
1546	build_constrained_parameter (tree cnc, tree proto, tree args)
1547	{
1548	tree name = DECL_NAME (cnc);
1549	tree type = TREE_TYPE (proto);
1550	tree decl = build_decl (input_location, TYPE_DECL, name, type);
1551	CONSTRAINED_PARM_PROTOTYPE (decl) = proto;
1552	CONSTRAINED_PARM_CONCEPT (decl) = cnc;
1553	CONSTRAINED_PARM_EXTRA_ARGS (decl) = args;
1554	return decl;
1555	}
1556
1557	/* Create a constraint expression for the given DECL that evaluates the
1558	requirements specified by CONSTR, a TYPE_DECL that contains all the
1559	information necessary to build the requirements (see finish_concept_name
1560	for the layout of that TYPE_DECL).
1561
1562	Note that the constraints are neither reduced nor decomposed. That is
1563	done only after the requires clause has been parsed (or not). */
1564
1565	tree
1566	finish_shorthand_constraint (tree decl, tree constr)
1567	{
1568	/* No requirements means no constraints. */
1569	if (!constr)
1570	return NULL_TREE;
1571
1572	if (error_operand_p (t: constr))
1573	return NULL_TREE;
1574
1575	tree proto = CONSTRAINED_PARM_PROTOTYPE (constr);
1576	tree con = CONSTRAINED_PARM_CONCEPT (constr);
1577	tree args = CONSTRAINED_PARM_EXTRA_ARGS (constr);
1578
1579	/* The TS lets use shorthand to constrain a pack of arguments, but the
1580	standard does not.
1581
1582	For the TS, consider:
1583
1584	template<C... Ts> struct s;
1585
1586	If C is variadic (and because Ts is a pack), we associate the
1587	constraint C<Ts...>. In all other cases, we associate
1588	the constraint (C<Ts> && ...).
1589
1590	The standard behavior cannot be overridden by -fconcepts-ts. */
1591	bool variadic_concept_p = template_parameter_pack_p (proto);
1592	bool declared_pack_p = template_parameter_pack_p (decl);
1593	bool apply_to_each_p = (cxx_dialect >= cxx20) ? true : !variadic_concept_p;
1594
1595	/* Get the argument and overload used for the requirement
1596	and adjust it if we're going to expand later. */
1597	tree arg = template_parm_to_arg (decl);
1598	if (apply_to_each_p && declared_pack_p)
1599	arg = PACK_EXPANSION_PATTERN (TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg), 0));
1600
1601	/* Build the concept constraint-expression. */
1602	tree tmpl = DECL_TI_TEMPLATE (con);
1603	tree check = tmpl;
1604	if (TREE_CODE (con) == FUNCTION_DECL)
1605	check = ovl_make (fn: tmpl);
1606	check = build_concept_check (decl: check, arg, rest: args, complain: tf_warning_or_error);
1607
1608	/* Make the check a fold-expression if needed. */
1609	if (apply_to_each_p && declared_pack_p)
1610	check = finish_left_unary_fold_expr (DECL_SOURCE_LOCATION (decl),
1611	check, TRUTH_ANDIF_EXPR);
1612
1613	return check;
1614	}
1615
1616	/* Returns a conjunction of shorthand requirements for the template
1617	parameter list PARMS. Note that the requirements are stored in
1618	the TYPE of each tree node. */
1619
1620	tree
1621	get_shorthand_constraints (tree parms)
1622	{
1623	tree result = NULL_TREE;
1624	parms = INNERMOST_TEMPLATE_PARMS (parms);
1625	for (int i = 0; i < TREE_VEC_LENGTH (parms); ++i)
1626	{
1627	tree parm = TREE_VEC_ELT (parms, i);
1628	tree constr = TEMPLATE_PARM_CONSTRAINTS (parm);
1629	result = combine_constraint_expressions (lhs: result, rhs: constr);
1630	}
1631	return result;
1632	}
1633
1634	/* Get the deduced wildcard from a DEDUCED placeholder. If the deduced
1635	wildcard is a pack, return the first argument of that pack. */
1636
1637	static tree
1638	get_deduced_wildcard (tree wildcard)
1639	{
1640	if (ARGUMENT_PACK_P (wildcard))
1641	wildcard = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (wildcard), 0);
1642	gcc_assert (TREE_CODE (wildcard) == WILDCARD_DECL);
1643	return wildcard;
1644	}
1645
1646	/* Returns the prototype parameter for the nth deduced wildcard. */
1647
1648	static tree
1649	get_introduction_prototype (tree wildcards, int index)
1650	{
1651	return TREE_TYPE (get_deduced_wildcard (TREE_VEC_ELT (wildcards, index)));
1652	}
1653
1654	/* Introduce a type template parameter. */
1655
1656	static tree
1657	introduce_type_template_parameter (tree wildcard, bool& non_type_p)
1658	{
1659	non_type_p = false;
1660	return finish_template_type_parm (class_type_node, DECL_NAME (wildcard));
1661	}
1662
1663	/* Introduce a template template parameter. */
1664
1665	static tree
1666	introduce_template_template_parameter (tree wildcard, bool& non_type_p)
1667	{
1668	non_type_p = false;
1669	begin_template_parm_list ();
1670	current_template_parms = DECL_TEMPLATE_PARMS (TREE_TYPE (wildcard));
1671	end_template_parm_list ();
1672	return finish_template_template_parm (class_type_node, DECL_NAME (wildcard));
1673	}
1674
1675	/* Introduce a template non-type parameter. */
1676
1677	static tree
1678	introduce_nontype_template_parameter (tree wildcard, bool& non_type_p)
1679	{
1680	non_type_p = true;
1681	tree parm = copy_decl (TREE_TYPE (wildcard));
1682	DECL_NAME (parm) = DECL_NAME (wildcard);
1683	return parm;
1684	}
1685
1686	/* Introduce a single template parameter. */
1687
1688	static tree
1689	build_introduced_template_parameter (tree wildcard, bool& non_type_p)
1690	{
1691	tree proto = TREE_TYPE (wildcard);
1692
1693	tree parm;
1694	if (TREE_CODE (proto) == TYPE_DECL)
1695	parm = introduce_type_template_parameter (wildcard, non_type_p);
1696	else if (TREE_CODE (proto) == TEMPLATE_DECL)
1697	parm = introduce_template_template_parameter (wildcard, non_type_p);
1698	else
1699	parm = introduce_nontype_template_parameter (wildcard, non_type_p);
1700
1701	/* Wrap in a TREE_LIST for process_template_parm. Note that introduced
1702	parameters do not retain the defaults from the source parameter. */
1703	return build_tree_list (NULL_TREE, parm);
1704	}
1705
1706	/* Introduce a single template parameter. */
1707
1708	static tree
1709	introduce_template_parameter (tree parms, tree wildcard)
1710	{
1711	gcc_assert (!ARGUMENT_PACK_P (wildcard));
1712	tree proto = TREE_TYPE (wildcard);
1713	location_t loc = DECL_SOURCE_LOCATION (wildcard);
1714
1715	/* Diagnose the case where we have C{...Args}. */
1716	if (WILDCARD_PACK_P (wildcard))
1717	{
1718	tree id = DECL_NAME (wildcard);
1719	error_at (loc, "%qE cannot be introduced with an ellipsis %<...%>", id);
1720	inform (DECL_SOURCE_LOCATION (proto), "prototype declared here");
1721	}
1722
1723	bool non_type_p;
1724	tree parm = build_introduced_template_parameter (wildcard, non_type_p);
1725	return process_template_parm (parms, loc, parm, non_type_p, false);
1726	}
1727
1728	/* Introduce a template parameter pack. */
1729
1730	static tree
1731	introduce_template_parameter_pack (tree parms, tree wildcard)
1732	{
1733	bool non_type_p;
1734	tree parm = build_introduced_template_parameter (wildcard, non_type_p);
1735	location_t loc = DECL_SOURCE_LOCATION (wildcard);
1736	return process_template_parm (parms, loc, parm, non_type_p, true);
1737	}
1738
1739	/* Introduce the nth template parameter. */
1740
1741	static tree
1742	introduce_template_parameter (tree parms, tree wildcards, int& index)
1743	{
1744	tree deduced = TREE_VEC_ELT (wildcards, index++);
1745	return introduce_template_parameter (parms, wildcard: deduced);
1746	}
1747
1748	/* Introduce either a template parameter pack or a list of template
1749	parameters. */
1750
1751	static tree
1752	introduce_template_parameters (tree parms, tree wildcards, int& index)
1753	{
1754	/* If the prototype was a parameter, we better have deduced an
1755	argument pack, and that argument must be the last deduced value
1756	in the wildcard vector. */
1757	tree deduced = TREE_VEC_ELT (wildcards, index++);
1758	gcc_assert (ARGUMENT_PACK_P (deduced));
1759	gcc_assert (index == TREE_VEC_LENGTH (wildcards));
1760
1761	/* Introduce each element in the pack. */
1762	tree args = ARGUMENT_PACK_ARGS (deduced);
1763	for (int i = 0; i < TREE_VEC_LENGTH (args); ++i)
1764	{
1765	tree arg = TREE_VEC_ELT (args, i);
1766	if (WILDCARD_PACK_P (arg))
1767	parms = introduce_template_parameter_pack (parms, wildcard: arg);
1768	else
1769	parms = introduce_template_parameter (parms, wildcard: arg);
1770	}
1771
1772	return parms;
1773	}
1774
1775	/* Builds the template parameter list PARMS by chaining introduced
1776	parameters from the WILDCARD vector. INDEX is the position of
1777	the current parameter. */
1778
1779	static tree
1780	process_introduction_parms (tree parms, tree wildcards, int& index)
1781	{
1782	tree proto = get_introduction_prototype (wildcards, index);
1783	if (template_parameter_pack_p (proto))
1784	return introduce_template_parameters (parms, wildcards, index);
1785	else
1786	return introduce_template_parameter (parms, wildcards, index);
1787	}
1788
1789	/* Ensure that all template parameters have been introduced for the concept
1790	named in CHECK. If not, emit a diagnostic.
1791
1792	Note that implicitly introducing a parameter with a default argument
1793	creates a case where a parameter is declared, but unnamed, making
1794	it unusable in the definition. */
1795
1796	static bool
1797	check_introduction_list (tree intros, tree check)
1798	{
1799	check = unpack_concept_check (t: check);
1800	tree tmpl = TREE_OPERAND (check, 0);
1801	if (OVL_P (tmpl))
1802	tmpl = OVL_FIRST (tmpl);
1803
1804	tree parms = DECL_INNERMOST_TEMPLATE_PARMS (tmpl);
1805	if (TREE_VEC_LENGTH (intros) < TREE_VEC_LENGTH (parms))
1806	{
1807	error_at (input_location, "all template parameters of %qD must "
1808	"be introduced", tmpl);
1809	return false;
1810	}
1811
1812	return true;
1813	}
1814
1815	/* Associates a constraint check to the current template based on the
1816	introduction parameters. INTRO_LIST must be a TREE_VEC of WILDCARD_DECLs
1817	containing a chained PARM_DECL which contains the identifier as well as
1818	the source location. TMPL_DECL is the decl for the concept being used.
1819	If we take a concept, C, this will form a check in the form of
1820	C<INTRO_LIST> filling in any extra arguments needed by the defaults
1821	deduced.
1822
1823	Returns NULL_TREE if no concept could be matched and error_mark_node if
1824	an error occurred when matching. */
1825
1826	tree
1827	finish_template_introduction (tree tmpl_decl,
1828	tree intro_list,
1829	location_t intro_loc)
1830	{
1831	/* Build a concept check to deduce the actual parameters. */
1832	tree expr = build_concept_check (target: tmpl_decl, args: intro_list, complain: tf_none);
1833	if (expr == error_mark_node)
1834	{
1835	error_at (intro_loc, "cannot deduce template parameters from "
1836	"introduction list");
1837	return error_mark_node;
1838	}
1839
1840	if (!check_introduction_list (intros: intro_list, check: expr))
1841	return error_mark_node;
1842
1843	tree parms = deduce_concept_introduction (check: expr);
1844	if (!parms)
1845	return NULL_TREE;
1846
1847	/* Build template parameter scope for introduction. */
1848	tree parm_list = NULL_TREE;
1849	begin_template_parm_list ();
1850	int nargs = MIN (TREE_VEC_LENGTH (parms), TREE_VEC_LENGTH (intro_list));
1851	for (int n = 0; n < nargs; )
1852	parm_list = process_introduction_parms (parms: parm_list, wildcards: parms, index&: n);
1853	parm_list = end_template_parm_list (parm_list);
1854
1855	/* Update the number of arguments to reflect the number of deduced
1856	template parameter introductions. */
1857	nargs = TREE_VEC_LENGTH (parm_list);
1858
1859	/* Determine if any errors occurred during matching. */
1860	for (int i = 0; i < TREE_VEC_LENGTH (parm_list); ++i)
1861	if (TREE_VALUE (TREE_VEC_ELT (parm_list, i)) == error_mark_node)
1862	{
1863	end_template_decl ();
1864	return error_mark_node;
1865	}
1866
1867	/* Build a concept check for our constraint. */
1868	tree check_args = make_tree_vec (nargs);
1869	int n = 0;
1870	for (; n < TREE_VEC_LENGTH (parm_list); ++n)
1871	{
1872	tree parm = TREE_VEC_ELT (parm_list, n);
1873	TREE_VEC_ELT (check_args, n) = template_parm_to_arg (parm);
1874	}
1875	SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (check_args, n);
1876
1877	/* If the template expects more parameters we should be able
1878	to use the defaults from our deduced concept. */
1879	for (; n < TREE_VEC_LENGTH (parms); ++n)
1880	TREE_VEC_ELT (check_args, n) = TREE_VEC_ELT (parms, n);
1881
1882	/* Associate the constraint. */
1883	tree check = build_concept_check (target: tmpl_decl,
1884	args: check_args,
1885	complain: tf_warning_or_error);
1886	TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = check;
1887
1888	return parm_list;
1889	}
1890
1891
1892	/* Given the concept check T from a constrained-type-specifier, extract
1893	its TMPL and ARGS. FIXME why do we need two different forms of
1894	constrained-type-specifier? */
1895
1896	void
1897	placeholder_extract_concept_and_args (tree t, tree &tmpl, tree &args)
1898	{
1899	if (concept_check_p (t))
1900	{
1901	t = unpack_concept_check (t);
1902	tmpl = TREE_OPERAND (t, 0);
1903	if (TREE_CODE (tmpl) == OVERLOAD)
1904	tmpl = OVL_FIRST (tmpl);
1905	args = TREE_OPERAND (t, 1);
1906	return;
1907	}
1908
1909	if (TREE_CODE (t) == TYPE_DECL)
1910	{
1911	/* A constrained parameter. Build a constraint check
1912	based on the prototype parameter and then extract the
1913	arguments from that. */
1914	tree proto = CONSTRAINED_PARM_PROTOTYPE (t);
1915	tree check = finish_shorthand_constraint (decl: proto, constr: t);
1916	placeholder_extract_concept_and_args (t: check, tmpl, args);
1917	return;
1918	}
1919	}
1920
1921	/* Returns true iff the placeholders C1 and C2 are equivalent. C1
1922	and C2 can be either TEMPLATE_TYPE_PARM or template-ids. */
1923
1924	bool
1925	equivalent_placeholder_constraints (tree c1, tree c2)
1926	{
1927	if (c1 && TREE_CODE (c1) == TEMPLATE_TYPE_PARM)
1928	/* A constrained auto. */
1929	c1 = PLACEHOLDER_TYPE_CONSTRAINTS (c1);
1930	if (c2 && TREE_CODE (c2) == TEMPLATE_TYPE_PARM)
1931	c2 = PLACEHOLDER_TYPE_CONSTRAINTS (c2);
1932
1933	if (c1 == c2)
1934	return true;
1935	if (!c1 || !c2)
1936	return false;
1937	if (c1 == error_mark_node || c2 == error_mark_node)
1938	/* We get here during satisfaction; when a deduction constraint
1939	fails, substitution can produce an error_mark_node for the
1940	placeholder constraints. */
1941	return false;
1942
1943	tree t1, t2, a1, a2;
1944	placeholder_extract_concept_and_args (t: c1, tmpl&: t1, args&: a1);
1945	placeholder_extract_concept_and_args (t: c2, tmpl&: t2, args&: a2);
1946
1947	if (t1 != t2)
1948	return false;
1949
1950	int len1 = TREE_VEC_LENGTH (a1);
1951	int len2 = TREE_VEC_LENGTH (a2);
1952	if (len1 != len2)
1953	return false;
1954
1955	/* Skip the first argument so we don't infinitely recurse.
1956	Also, they may differ in template parameter index. */
1957	for (int i = 1; i < len1; ++i)
1958	{
1959	tree t1 = TREE_VEC_ELT (a1, i);
1960	tree t2 = TREE_VEC_ELT (a2, i);
1961	if (!template_args_equal (t1, t2))
1962	return false;
1963	}
1964	return true;
1965	}
1966
1967	/* Return a hash value for the placeholder ATOMIC_CONSTR C. */
1968
1969	hashval_t
1970	hash_placeholder_constraint (tree c)
1971	{
1972	tree t, a;
1973	placeholder_extract_concept_and_args (t: c, tmpl&: t, args&: a);
1974
1975	/* Like hash_tmpl_and_args, but skip the first argument. */
1976	hashval_t val = iterative_hash_object (DECL_UID (t), 0);
1977
1978	for (int i = TREE_VEC_LENGTH (a)-1; i > 0; --i)
1979	val = iterative_hash_template_arg (TREE_VEC_ELT (a, i), val);
1980
1981	return val;
1982	}
1983
1984	/* Substitute through the expression of a simple requirement or
1985	compound requirement. */
1986
1987	static tree
1988	tsubst_valid_expression_requirement (tree t, tree args, sat_info info)
1989	{
1990	tree r = tsubst_expr (t, args, tf_none, info.in_decl);
1991	if (convert_to_void (r, ICV_STATEMENT, tf_none) != error_mark_node)
1992	return r;
1993
1994	if (info.diagnose_unsatisfaction_p ())
1995	{
1996	location_t loc = cp_expr_loc_or_input_loc (t);
1997	if (diagnosing_failed_constraint::replay_errors_p ())
1998	{
1999	inform (loc, "the required expression %qE is invalid, because", t);
2000	if (r == error_mark_node)
2001	tsubst_expr (t, args, info.complain, info.in_decl);
2002	else
2003	convert_to_void (r, ICV_STATEMENT, info.complain);
2004	}
2005	else
2006	inform (loc, "the required expression %qE is invalid", t);
2007	}
2008	else if (info.noisy ())
2009	{
2010	r = tsubst_expr (t, args, info.complain, info.in_decl);
2011	convert_to_void (r, ICV_STATEMENT, info.complain);
2012	}
2013
2014	return error_mark_node;
2015	}
2016
2017
2018	/* Substitute through the simple requirement. */
2019
2020	static tree
2021	tsubst_simple_requirement (tree t, tree args, sat_info info)
2022	{
2023	tree t0 = TREE_OPERAND (t, 0);
2024	tree expr = tsubst_valid_expression_requirement (t: t0, args, info);
2025	if (expr == error_mark_node)
2026	return error_mark_node;
2027	return boolean_true_node;
2028	}
2029
2030	/* Subroutine of tsubst_type_requirement that performs the actual substitution
2031	and diagnosing. Also used by tsubst_compound_requirement. */
2032
2033	static tree
2034	tsubst_type_requirement_1 (tree t, tree args, sat_info info, location_t loc)
2035	{
2036	tree r = tsubst (t, args, tf_none, info.in_decl);
2037	if (r != error_mark_node)
2038	return r;
2039
2040	if (info.diagnose_unsatisfaction_p ())
2041	{
2042	if (diagnosing_failed_constraint::replay_errors_p ())
2043	{
2044	/* Replay the substitution error. */
2045	inform (loc, "the required type %qT is invalid, because", t);
2046	tsubst (t, args, info.complain, info.in_decl);
2047	}
2048	else
2049	inform (loc, "the required type %qT is invalid", t);
2050	}
2051	else if (info.noisy ())
2052	tsubst (t, args, info.complain, info.in_decl);
2053
2054	return error_mark_node;
2055	}
2056
2057
2058	/* Substitute through the type requirement. */
2059
2060	static tree
2061	tsubst_type_requirement (tree t, tree args, sat_info info)
2062	{
2063	tree t0 = TREE_OPERAND (t, 0);
2064	tree type = tsubst_type_requirement_1 (t: t0, args, info, EXPR_LOCATION (t));
2065	if (type == error_mark_node)
2066	return error_mark_node;
2067	return boolean_true_node;
2068	}
2069
2070	/* True if TYPE can be deduced from EXPR. */
2071
2072	static bool
2073	type_deducible_p (tree expr, tree type, tree placeholder, tree args,
2074	subst_info info)
2075	{
2076	/* Make sure deduction is performed against ( EXPR ), so that
2077	references are preserved in the result. */
2078	expr = force_paren_expr_uneval (t: expr);
2079
2080	tree deduced_type = do_auto_deduction (type, expr, placeholder,
2081	info.complain, adc_requirement,
2082	/*outer_targs=*/args);
2083
2084	return deduced_type != error_mark_node;
2085	}
2086
2087	/* True if EXPR can not be converted to TYPE. */
2088
2089	static bool
2090	expression_convertible_p (tree expr, tree type, subst_info info)
2091	{
2092	tree conv =
2093	perform_direct_initialization_if_possible (type, expr, false,
2094	info.complain);
2095	if (conv == error_mark_node)
2096	return false;
2097	if (conv == NULL_TREE)
2098	{
2099	if (info.complain & tf_error)
2100	{
2101	location_t loc = EXPR_LOC_OR_LOC (expr, input_location);
2102	error_at (loc, "cannot convert %qE to %qT", expr, type);
2103	}
2104	return false;
2105	}
2106	return true;
2107	}
2108
2109
2110	/* Substitute through the compound requirement. */
2111
2112	static tree
2113	tsubst_compound_requirement (tree t, tree args, sat_info info)
2114	{
2115	tree t0 = TREE_OPERAND (t, 0);
2116	tree t1 = TREE_OPERAND (t, 1);
2117	tree expr = tsubst_valid_expression_requirement (t: t0, args, info);
2118	if (expr == error_mark_node)
2119	return error_mark_node;
2120
2121	location_t loc = cp_expr_loc_or_input_loc (t: expr);
2122
2123	/* Check the noexcept condition. */
2124	bool noexcept_p = COMPOUND_REQ_NOEXCEPT_P (t);
2125	if (noexcept_p && !expr_noexcept_p (expr, tf_none))
2126	{
2127	if (info.diagnose_unsatisfaction_p ())
2128	inform (loc, "%qE is not %<noexcept%>", expr);
2129	else
2130	return error_mark_node;
2131	}
2132
2133	/* Substitute through the type expression, if any. */
2134	tree type = tsubst_type_requirement_1 (t: t1, args, info, EXPR_LOCATION (t));
2135	if (type == error_mark_node)
2136	return error_mark_node;
2137
2138	subst_info quiet (tf_none, info.in_decl);
2139
2140	/* Check expression against the result type. */
2141	if (type)
2142	{
2143	if (tree placeholder = type_uses_auto (type))
2144	{
2145	if (!type_deducible_p (expr, type, placeholder, args, info: quiet))
2146	{
2147	if (info.diagnose_unsatisfaction_p ())
2148	{
2149	if (diagnosing_failed_constraint::replay_errors_p ())
2150	{
2151	inform (loc,
2152	"%qE does not satisfy return-type-requirement, "
2153	"because", t0);
2154	/* Further explain the reason for the error. */
2155	type_deducible_p (expr, type, placeholder, args, info);
2156	}
2157	else
2158	inform (loc,
2159	"%qE does not satisfy return-type-requirement", t0);
2160	}
2161	return error_mark_node;
2162	}
2163	}
2164	else if (!expression_convertible_p (expr, type, info: quiet))
2165	{
2166	if (info.diagnose_unsatisfaction_p ())
2167	{
2168	if (diagnosing_failed_constraint::replay_errors_p ())
2169	{
2170	inform (loc, "cannot convert %qE to %qT because", t0, type);
2171	/* Further explain the reason for the error. */
2172	expression_convertible_p (expr, type, info);
2173	}
2174	else
2175	inform (loc, "cannot convert %qE to %qT", t0, type);
2176	}
2177	return error_mark_node;
2178	}
2179	}
2180
2181	return boolean_true_node;
2182	}
2183
2184	/* Substitute through the nested requirement. */
2185
2186	static tree
2187	tsubst_nested_requirement (tree t, tree args, sat_info info)
2188	{
2189	sat_info quiet (tf_none, info.in_decl);
2190	tree result = constraint_satisfaction_value (t, args, quiet);
2191	if (result == boolean_true_node)
2192	return boolean_true_node;
2193
2194	if (result == boolean_false_node
2195	&& info.diagnose_unsatisfaction_p ())
2196	{
2197	tree expr = TREE_OPERAND (t, 0);
2198	location_t loc = cp_expr_location (t_: t);
2199	if (diagnosing_failed_constraint::replay_errors_p ())
2200	{
2201	/* Replay the substitution error. */
2202	inform (loc, "nested requirement %qE is not satisfied, because", expr);
2203	constraint_satisfaction_value (t, args, info);
2204	}
2205	else
2206	inform (loc, "nested requirement %qE is not satisfied", expr);
2207	}
2208
2209	return error_mark_node;
2210	}
2211
2212	/* Substitute ARGS into the requirement T. */
2213
2214	static tree
2215	tsubst_requirement (tree t, tree args, sat_info info)
2216	{
2217	iloc_sentinel loc_s (cp_expr_location (t_: t));
2218	switch (TREE_CODE (t))
2219	{
2220	case SIMPLE_REQ:
2221	return tsubst_simple_requirement (t, args, info);
2222	case TYPE_REQ:
2223	return tsubst_type_requirement (t, args, info);
2224	case COMPOUND_REQ:
2225	return tsubst_compound_requirement (t, args, info);
2226	case NESTED_REQ:
2227	return tsubst_nested_requirement (t, args, info);
2228	default:
2229	break;
2230	}
2231	gcc_unreachable ();
2232	}
2233
2234	static tree
2235	declare_constraint_vars (tree parms, tree vars)
2236	{
2237	tree s = vars;
2238	for (tree t = parms; t; t = DECL_CHAIN (t))
2239	{
2240	if (DECL_PACK_P (t))
2241	{
2242	tree pack = extract_fnparm_pack (t, &s);
2243	register_local_specialization (pack, t);
2244	}
2245	else
2246	{
2247	register_local_specialization (s, t);
2248	s = DECL_CHAIN (s);
2249	}
2250	}
2251	return vars;
2252	}
2253
2254	/* Substitute through as if checking function parameter types. This
2255	will diagnose common parameter type errors. Returns error_mark_node
2256	if an error occurred. */
2257
2258	static tree
2259	check_constraint_variables (tree t, tree args, subst_info info)
2260	{
2261	tree types = NULL_TREE;
2262	tree p = t;
2263	while (p && !VOID_TYPE_P (p))
2264	{
2265	types = tree_cons (NULL_TREE, TREE_TYPE (p), types);
2266	p = TREE_CHAIN (p);
2267	}
2268	types = chainon (nreverse (types), void_list_node);
2269	return tsubst_function_parms (types, args, info.complain, info.in_decl);
2270	}
2271
2272	/* A subroutine of tsubst_parameterized_constraint. Substitute ARGS
2273	into the parameter list T, producing a sequence of constraint
2274	variables, declared in the current scope.
2275
2276	Note that the caller must establish a local specialization stack
2277	prior to calling this function since this substitution will
2278	declare the substituted parameters. */
2279
2280	static tree
2281	tsubst_constraint_variables (tree t, tree args, subst_info info)
2282	{
2283	/* Perform a trial substitution to check for type errors. */
2284	tree parms = check_constraint_variables (t, args, info);
2285	if (parms == error_mark_node)
2286	return error_mark_node;
2287
2288	/* Clear cp_unevaluated_operand across tsubst so that we get a proper chain
2289	of PARM_DECLs. */
2290	int saved_unevaluated_operand = cp_unevaluated_operand;
2291	cp_unevaluated_operand = 0;
2292	tree vars = tsubst (t, args, info.complain, info.in_decl);
2293	cp_unevaluated_operand = saved_unevaluated_operand;
2294	if (vars == error_mark_node)
2295	return error_mark_node;
2296	return declare_constraint_vars (parms: t, vars);
2297	}
2298
2299	/* Substitute ARGS into the requires-expression T. [8.4.7]p6. The
2300	substitution of template arguments into a requires-expression
2301	may result in the formation of invalid types or expressions
2302	in its requirements ... In such cases, the expression evaluates
2303	to false; it does not cause the program to be ill-formed.
2304
2305	When substituting through a REQUIRES_EXPR as part of template
2306	instantiation, we call this routine with info.quiet() true.
2307
2308	When evaluating a REQUIRES_EXPR that appears outside a template in
2309	cp_parser_requires_expression, we call this routine with
2310	info.noisy() true.
2311
2312	Finally, when diagnosing unsatisfaction from diagnose_atomic_constraint
2313	and when diagnosing a false REQUIRES_EXPR via diagnose_constraints,
2314	we call this routine with info.diagnose_unsatisfaction_p() true. */
2315
2316	static tree
2317	tsubst_requires_expr (tree t, tree args, sat_info info)
2318	{
2319	local_specialization_stack stack (lss_copy);
2320
2321	/* We need to check access during the substitution. */
2322	deferring_access_check_sentinel acs (dk_no_deferred);
2323
2324	/* A requires-expression is an unevaluated context. */
2325	cp_unevaluated u;
2326
2327	args = add_extra_args (REQUIRES_EXPR_EXTRA_ARGS (t), args,
2328	info.complain, info.in_decl);
2329	if (processing_template_decl)
2330	{
2331	/* We're partially instantiating a generic lambda. Substituting into
2332	this requires-expression now may cause its requirements to get
2333	checked out of order, so instead just remember the template
2334	arguments and wait until we can substitute them all at once. */
2335	t = copy_node (t);
2336	REQUIRES_EXPR_EXTRA_ARGS (t) = build_extra_args (t, args, info.complain);
2337	return t;
2338	}
2339
2340	if (tree parms = REQUIRES_EXPR_PARMS (t))
2341	{
2342	parms = tsubst_constraint_variables (t: parms, args, info);
2343	if (parms == error_mark_node)
2344	return boolean_false_node;
2345	}
2346
2347	tree result = boolean_true_node;
2348	for (tree reqs = REQUIRES_EXPR_REQS (t); reqs; reqs = TREE_CHAIN (reqs))
2349	{
2350	tree req = TREE_VALUE (reqs);
2351	if (tsubst_requirement (t: req, args, info) == error_mark_node)
2352	{
2353	result = boolean_false_node;
2354	if (info.diagnose_unsatisfaction_p ())
2355	/* Keep going so that we diagnose all failed requirements. */;
2356	else
2357	break;
2358	}
2359	}
2360	return result;
2361	}
2362
2363	/* Public wrapper for the above. */
2364
2365	tree
2366	tsubst_requires_expr (tree t, tree args,
2367	tsubst_flags_t complain, tree in_decl)
2368	{
2369	sat_info info (complain, in_decl);
2370	return tsubst_requires_expr (t, args, info);
2371	}
2372
2373	/* Substitute ARGS into the constraint information CI, producing a new
2374	constraint record. */
2375
2376	tree
2377	tsubst_constraint_info (tree t, tree args,
2378	tsubst_flags_t complain, tree in_decl)
2379	{
2380	if (!t || t == error_mark_node || !check_constraint_info (t))
2381	return NULL_TREE;
2382
2383	tree tr = tsubst_constraint (CI_TEMPLATE_REQS (t), args, complain, in_decl);
2384	tree dr = tsubst_constraint (CI_DECLARATOR_REQS (t), args, complain, in_decl);
2385	return build_constraints (tr, dr);
2386	}
2387
2388	/* Substitute through a parameter mapping, in order to get the actual
2389	arguments used to instantiate an atomic constraint. This may fail
2390	if the substitution into arguments produces something ill-formed. */
2391
2392	static tree
2393	tsubst_parameter_mapping (tree map, tree args, subst_info info)
2394	{
2395	if (!map)
2396	return NULL_TREE;
2397
2398	tsubst_flags_t complain = info.complain;
2399	tree in_decl = info.in_decl;
2400
2401	tree result = NULL_TREE;
2402	for (tree p = map; p; p = TREE_CHAIN (p))
2403	{
2404	if (p == error_mark_node)
2405	return error_mark_node;
2406	tree parm = TREE_VALUE (p);
2407	tree arg = TREE_PURPOSE (p);
2408	tree new_arg;
2409	if (ARGUMENT_PACK_P (arg))
2410	new_arg = tsubst_argument_pack (arg, args, complain, in_decl);
2411	else
2412	{
2413	new_arg = tsubst_template_arg (arg, args, complain, in_decl);
2414	if (TYPE_P (new_arg))
2415	new_arg = canonicalize_type_argument (new_arg, complain);
2416	}
2417	if (TREE_CODE (new_arg) == TYPE_ARGUMENT_PACK)
2418	{
2419	tree pack_args = ARGUMENT_PACK_ARGS (new_arg);
2420	for (tree& pack_arg : tree_vec_range (pack_args))
2421	if (TYPE_P (pack_arg))
2422	pack_arg = canonicalize_type_argument (pack_arg, complain);
2423	}
2424	if (new_arg == error_mark_node)
2425	return error_mark_node;
2426
2427	result = tree_cons (new_arg, parm, result);
2428	}
2429	return nreverse (result);
2430	}
2431
2432	tree
2433	tsubst_parameter_mapping (tree map, tree args, tsubst_flags_t complain, tree in_decl)
2434	{
2435	return tsubst_parameter_mapping (map, args, info: subst_info (complain, in_decl));
2436	}
2437
2438	/*---------------------------------------------------------------------------
2439	Constraint satisfaction
2440	---------------------------------------------------------------------------*/
2441
2442	/* True if we are currently satisfying a constraint. */
2443
2444	static bool satisfying_constraint;
2445
2446	/* A vector of incomplete types (and of declarations with undeduced return type),
2447	appended to by note_failed_type_completion_for_satisfaction. The
2448	satisfaction caches use this in order to keep track of "potentially unstable"
2449	satisfaction results.
2450
2451	Since references to entries in this vector are stored only in the
2452	GC-deletable sat_cache, it's safe to make this deletable as well. */
2453
2454	static GTY((deletable)) vec<tree, va_gc> *failed_type_completions;
2455
2456	/* Called whenever a type completion (or return type deduction) failure occurs
2457	that definitely affects the meaning of the program, by e.g. inducing
2458	substitution failure. */
2459
2460	void
2461	note_failed_type_completion_for_satisfaction (tree t)
2462	{
2463	if (satisfying_constraint)
2464	{
2465	gcc_checking_assert ((TYPE_P (t) && !COMPLETE_TYPE_P (t))
2466	|| (DECL_P (t) && undeduced_auto_decl (t)));
2467	vec_safe_push (v&: failed_type_completions, obj: t);
2468	}
2469	}
2470
2471	/* Returns true if the range [BEGIN, END) of elements within the
2472	failed_type_completions vector contains a complete type (or a
2473	declaration with a non-placeholder return type). */
2474
2475	static bool
2476	some_type_complete_p (int begin, int end)
2477	{
2478	for (int i = begin; i < end; i++)
2479	{
2480	tree t = (*failed_type_completions)[i];
2481	if (TYPE_P (t) && COMPLETE_TYPE_P (t))
2482	return true;
2483	if (DECL_P (t) && !undeduced_auto_decl (t))
2484	return true;
2485	}
2486	return false;
2487	}
2488
2489	/* Hash functions and data types for satisfaction cache entries. */
2490
2491	struct GTY((for_user)) sat_entry
2492	{
2493	/* The relevant ATOMIC_CONSTR. */
2494	tree atom;
2495
2496	/* The relevant template arguments. */
2497	tree args;
2498
2499	/* The result of satisfaction of ATOM+ARGS.
2500	This is either boolean_true_node, boolean_false_node or error_mark_node,
2501	where error_mark_node indicates ill-formed satisfaction.
2502	It's set to NULL_TREE while computing satisfaction of ATOM+ARGS for
2503	the first time. */
2504	tree result;
2505
2506	/* The value of input_location when satisfaction of ATOM+ARGS was first
2507	performed. */
2508	location_t location;
2509
2510	/* The range of elements appended to the failed_type_completions vector
2511	during computation of this satisfaction result, encoded as a begin/end
2512	pair of offsets. */
2513	int ftc_begin, ftc_end;
2514
2515	/* True if we want to diagnose the above instability when it's detected.
2516	We don't always want to do so, in order to avoid emitting duplicate
2517	diagnostics in some cases. */
2518	bool diagnose_instability;
2519
2520	/* True if we're in the middle of computing this satisfaction result.
2521	Used during both quiet and noisy satisfaction to detect self-recursive
2522	satisfaction. */
2523	bool evaluating;
2524	};
2525
2526	struct sat_hasher : ggc_ptr_hash<sat_entry>
2527	{
2528	static hashval_t hash (sat_entry *e)
2529	{
2530	auto cso = make_temp_override (var&: comparing_specializations);
2531	++comparing_specializations;
2532
2533	if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->atom))
2534	{
2535	/* Atoms with instantiated mappings are built during satisfaction.
2536	They live only inside the sat_cache, and we build one to query
2537	the cache with each time we instantiate a mapping. */
2538	gcc_assert (!e->args);
2539	return hash_atomic_constraint (t: e->atom);
2540	}
2541
2542	/* Atoms with uninstantiated mappings are built during normalization.
2543	Since normalize_atom caches the atoms it returns, we can assume
2544	pointer-based identity for fast hashing and comparison. Even if this
2545	assumption is violated, that's okay, we'll just get a cache miss. */
2546	hashval_t value = htab_hash_pointer (e->atom);
2547
2548	if (tree map = ATOMIC_CONSTR_MAP (e->atom))
2549	/* Only the parameters that are used in the targets of the mapping
2550	affect the satisfaction value of the atom. So we consider only
2551	the arguments for these parameters, and ignore the rest. */
2552	for (tree target_parms = TREE_TYPE (map);
2553	target_parms;
2554	target_parms = TREE_CHAIN (target_parms))
2555	{
2556	int level, index;
2557	tree parm = TREE_VALUE (target_parms);
2558	template_parm_level_and_index (parm, &level, &index);
2559	tree arg = TMPL_ARG (e->args, level, index);
2560	value = iterative_hash_template_arg (arg, val: value);
2561	}
2562	return value;
2563	}
2564
2565	static bool equal (sat_entry *e1, sat_entry *e2)
2566	{
2567	auto cso = make_temp_override (var&: comparing_specializations);
2568	++comparing_specializations;
2569
2570	if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom)
2571	!= ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->atom))
2572	return false;
2573
2574	/* See sat_hasher::hash. */
2575	if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom))
2576	{
2577	gcc_assert (!e1->args && !e2->args);
2578	return atomic_constraints_identical_p (t1: e1->atom, t2: e2->atom);
2579	}
2580
2581	if (e1->atom != e2->atom)
2582	return false;
2583
2584	if (tree map = ATOMIC_CONSTR_MAP (e1->atom))
2585	for (tree target_parms = TREE_TYPE (map);
2586	target_parms;
2587	target_parms = TREE_CHAIN (target_parms))
2588	{
2589	int level, index;
2590	tree parm = TREE_VALUE (target_parms);
2591	template_parm_level_and_index (parm, &level, &index);
2592	tree arg1 = TMPL_ARG (e1->args, level, index);
2593	tree arg2 = TMPL_ARG (e2->args, level, index);
2594	if (!template_args_equal (arg1, arg2))
2595	return false;
2596	}
2597	return true;
2598	}
2599	};
2600
2601	/* Cache the result of satisfy_atom. */
2602	static GTY((deletable)) hash_table<sat_hasher> *sat_cache;
2603
2604	/* Cache the result of satisfy_declaration_constraints. */
2605	static GTY((deletable)) hash_map<tree, tree> *decl_satisfied_cache;
2606
2607	/* A tool used by satisfy_atom to help manage satisfaction caching and to
2608	diagnose "unstable" satisfaction values. We insert into the cache only
2609	when performing satisfaction quietly. */
2610
2611	struct satisfaction_cache
2612	{
2613	satisfaction_cache (tree, tree, sat_info);
2614	tree get ();
2615	tree save (tree);
2616
2617	sat_entry *entry;
2618	sat_info info;
2619	int ftc_begin;
2620	};
2621
2622	/* Constructor for the satisfaction_cache class. We're performing satisfaction
2623	of ATOM+ARGS according to INFO. */
2624
2625	satisfaction_cache
2626	::satisfaction_cache (tree atom, tree args, sat_info info)
2627	: entry(nullptr), info(info), ftc_begin(-1)
2628	{
2629	if (!sat_cache)
2630	sat_cache = hash_table<sat_hasher>::create_ggc (n: 31);
2631
2632	/* When noisy, we query the satisfaction cache in order to diagnose
2633	"unstable" satisfaction values. */
2634	if (info.noisy ())
2635	{
2636	/* When noisy, constraints have been re-normalized, and that breaks the
2637	pointer-based identity assumption of sat_cache (for atoms with
2638	uninstantiated mappings). So undo this re-normalization by looking in
2639	the atom_cache for the corresponding atom that was used during quiet
2640	satisfaction. */
2641	if (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom))
2642	{
2643	if (tree found = atom_cache->find (value: atom))
2644	atom = found;
2645	else
2646	/* The lookup should always succeed, but if it fails then let's
2647	just leave 'entry' empty, effectively disabling the cache. */
2648	return;
2649	}
2650	}
2651
2652	/* Look up or create the corresponding satisfaction entry. */
2653	sat_entry elt;
2654	elt.atom = atom;
2655	elt.args = args;
2656	sat_entry **slot = sat_cache->find_slot (value: &elt, insert: INSERT);
2657	if (*slot)
2658	entry = *slot;
2659	else if (info.quiet ())
2660	{
2661	entry = ggc_alloc<sat_entry> ();
2662	entry->atom = atom;
2663	entry->args = args;
2664	entry->result = NULL_TREE;
2665	entry->location = input_location;
2666	entry->ftc_begin = entry->ftc_end = -1;
2667	entry->diagnose_instability = false;
2668	if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom))
2669	/* We always want to diagnose instability of an atom with an
2670	instantiated parameter mapping. For atoms with an uninstantiated
2671	mapping, we set this flag (in satisfy_atom) only if substitution
2672	into its mapping previously failed. */
2673	entry->diagnose_instability = true;
2674	entry->evaluating = false;
2675	*slot = entry;
2676	}
2677	else
2678	{
2679	/* We're evaluating this atom for the first time, and doing so noisily.
2680	This shouldn't happen outside of error recovery situations involving
2681	unstable satisfaction. Let's just leave 'entry' empty, effectively
2682	disabling the cache, and remove the empty slot. */
2683	gcc_checking_assert (seen_error ());
2684	/* Appease hash_table::check_complete_insertion. */
2685	*slot = ggc_alloc<sat_entry> ();
2686	sat_cache->clear_slot (slot);
2687	}
2688	}
2689
2690	/* Returns the cached satisfaction result if we have one and we're not
2691	recomputing the satisfaction result from scratch. Otherwise returns
2692	NULL_TREE. */
2693
2694	tree
2695	satisfaction_cache::get ()
2696	{
2697	if (!entry)
2698	return NULL_TREE;
2699
2700	if (entry->evaluating)
2701	{
2702	/* If we get here, it means satisfaction is self-recursive. */
2703	gcc_checking_assert (!entry->result || seen_error ());
2704	if (info.noisy ())
2705	error_at (EXPR_LOCATION (ATOMIC_CONSTR_EXPR (entry->atom)),
2706	"satisfaction of atomic constraint %qE depends on itself",
2707	entry->atom);
2708	return error_mark_node;
2709	}
2710
2711	/* This satisfaction result is "potentially unstable" if a type for which
2712	type completion failed during its earlier computation is now complete. */
2713	bool maybe_unstable = some_type_complete_p (begin: entry->ftc_begin,
2714	end: entry->ftc_end);
2715
2716	if (info.noisy () || maybe_unstable || !entry->result)
2717	{
2718	/* We're computing the satisfaction result from scratch. */
2719	entry->evaluating = true;
2720	ftc_begin = vec_safe_length (v: failed_type_completions);
2721	return NULL_TREE;
2722	}
2723	else
2724	return entry->result;
2725	}
2726
2727	/* RESULT is the computed satisfaction result. If RESULT differs from the
2728	previously cached result, this routine issues an appropriate error.
2729	Otherwise, when evaluating quietly, updates the cache appropriately. */
2730
2731	tree
2732	satisfaction_cache::save (tree result)
2733	{
2734	if (!entry)
2735	return result;
2736
2737	gcc_checking_assert (entry->evaluating);
2738	entry->evaluating = false;
2739
2740	if (entry->result && result != entry->result)
2741	{
2742	if (info.quiet ())
2743	/* Return error_mark_node to force satisfaction to get replayed
2744	noisily. */
2745	return error_mark_node;
2746	else
2747	{
2748	if (entry->diagnose_instability)
2749	{
2750	auto_diagnostic_group d;
2751	error_at (EXPR_LOCATION (ATOMIC_CONSTR_EXPR (entry->atom)),
2752	"satisfaction value of atomic constraint %qE changed "
2753	"from %qE to %qE", entry->atom, entry->result, result);
2754	inform (entry->location,
2755	"satisfaction value first evaluated to %qE from here",
2756	entry->result);
2757	}
2758	/* For sake of error recovery, allow this latest satisfaction result
2759	to prevail. */
2760	entry->result = result;
2761	return result;
2762	}
2763	}
2764
2765	if (info.quiet ())
2766	{
2767	entry->result = result;
2768	/* Store into this entry the list of relevant failed type completions
2769	that occurred during (re)computation of the satisfaction result. */
2770	gcc_checking_assert (ftc_begin != -1);
2771	entry->ftc_begin = ftc_begin;
2772	entry->ftc_end = vec_safe_length (v: failed_type_completions);
2773	}
2774
2775	return result;
2776	}
2777
2778	/* Substitute ARGS into constraint-expression T during instantiation of
2779	a member of a class template. */
2780
2781	tree
2782	tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl)
2783	{
2784	/* We also don't want to evaluate concept-checks when substituting the
2785	constraint-expressions of a declaration. */
2786	processing_constraint_expression_sentinel s;
2787	cp_unevaluated u;
2788	tree expr = tsubst_expr (t, args, complain, in_decl);
2789	return expr;
2790	}
2791
2792	static tree satisfy_constraint_r (tree, tree, sat_info info);
2793
2794	/* Compute the satisfaction of a conjunction. */
2795
2796	static tree
2797	satisfy_conjunction (tree t, tree args, sat_info info)
2798	{
2799	tree lhs = satisfy_constraint_r (TREE_OPERAND (t, 0), args, info);
2800	if (lhs == error_mark_node || lhs == boolean_false_node)
2801	return lhs;
2802	return satisfy_constraint_r (TREE_OPERAND (t, 1), args, info);
2803	}
2804
2805	/* The current depth at which we're replaying an error during recursive
2806	diagnosis of a constraint satisfaction failure. */
2807
2808	static int current_constraint_diagnosis_depth;
2809
2810	/* Whether CURRENT_CONSTRAINT_DIAGNOSIS_DEPTH has ever exceeded
2811	CONCEPTS_DIAGNOSTICS_MAX_DEPTH during recursive diagnosis of a constraint
2812	satisfaction error. */
2813
2814	static bool concepts_diagnostics_max_depth_exceeded_p;
2815
2816	/* Recursive subroutine of collect_operands_of_disjunction. T is a normalized
2817	subexpression of a constraint (composed of CONJ_CONSTRs and DISJ_CONSTRs)
2818	and E is the corresponding unnormalized subexpression (composed of
2819	TRUTH_ANDIF_EXPRs and TRUTH_ORIF_EXPRs). */
2820
2821	static void
2822	collect_operands_of_disjunction_r (tree t, tree e,
2823	auto_vec<tree_pair> *operands)
2824	{
2825	if (TREE_CODE (e) == TRUTH_ORIF_EXPR)
2826	{
2827	collect_operands_of_disjunction_r (TREE_OPERAND (t, 0),
2828	TREE_OPERAND (e, 0), operands);
2829	collect_operands_of_disjunction_r (TREE_OPERAND (t, 1),
2830	TREE_OPERAND (e, 1), operands);
2831	}
2832	else
2833	{
2834	tree_pair p = std::make_pair (x&: t, y&: e);
2835	operands->safe_push (obj: p);
2836	}
2837	}
2838
2839	/* Recursively collect the normalized and unnormalized operands of the
2840	disjunction T and append them to OPERANDS in order. */
2841
2842	static void
2843	collect_operands_of_disjunction (tree t, auto_vec<tree_pair> *operands)
2844	{
2845	collect_operands_of_disjunction_r (t, CONSTR_EXPR (t), operands);
2846	}
2847
2848	/* Compute the satisfaction of a disjunction. */
2849
2850	static tree
2851	satisfy_disjunction (tree t, tree args, sat_info info)
2852	{
2853	/* Evaluate each operand with unsatisfaction diagnostics disabled. */
2854	sat_info sub = info;
2855	sub.diagnose_unsatisfaction = false;
2856
2857	tree lhs = satisfy_constraint_r (TREE_OPERAND (t, 0), args, info: sub);
2858	if (lhs == boolean_true_node || lhs == error_mark_node)
2859	return lhs;
2860
2861	tree rhs = satisfy_constraint_r (TREE_OPERAND (t, 1), args, info: sub);
2862	if (rhs == boolean_true_node || rhs == error_mark_node)
2863	return rhs;
2864
2865	/* Both branches evaluated to false. Explain the satisfaction failure in
2866	each branch. */
2867	if (info.diagnose_unsatisfaction_p ())
2868	{
2869	diagnosing_failed_constraint failure (t, args, info.noisy ());
2870	cp_expr disj_expr = CONSTR_EXPR (t);
2871	inform (disj_expr.get_location (),
2872	"no operand of the disjunction is satisfied");
2873	if (diagnosing_failed_constraint::replay_errors_p ())
2874	{
2875	/* Replay the error in each branch of the disjunction. */
2876	auto_vec<tree_pair> operands;
2877	collect_operands_of_disjunction (t, operands: &operands);
2878	for (unsigned i = 0; i < operands.length (); i++)
2879	{
2880	tree norm_op = operands[i].first;
2881	tree op = operands[i].second;
2882	location_t loc = make_location (caret: cp_expr_location (t_: op),
2883	start: disj_expr.get_start (),
2884	finish: disj_expr.get_finish ());
2885	inform (loc, "the operand %qE is unsatisfied because", op);
2886	satisfy_constraint_r (norm_op, args, info);
2887	}
2888	}
2889	}
2890
2891	return boolean_false_node;
2892	}
2893
2894	/* Ensures that T is a truth value and not (accidentally, as sometimes
2895	happens) an integer value. */
2896
2897	tree
2898	satisfaction_value (tree t)
2899	{
2900	if (t == error_mark_node || t == boolean_true_node || t == boolean_false_node)
2901	return t;
2902
2903	gcc_assert (TREE_CODE (t) == INTEGER_CST
2904	&& same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (t),
2905	boolean_type_node));
2906	if (integer_zerop (t))
2907	return boolean_false_node;
2908	else
2909	return boolean_true_node;
2910	}
2911
2912	/* Build a new template argument vector corresponding to the parameter
2913	mapping of the atomic constraint T, using arguments from ARGS. */
2914
2915	static tree
2916	get_mapped_args (tree t, tree args)
2917	{
2918	tree map = ATOMIC_CONSTR_MAP (t);
2919
2920	/* No map, no arguments. */
2921	if (!map)
2922	return NULL_TREE;
2923
2924	/* Determine the depth of the resulting argument vector. */
2925	int depth;
2926	if (ATOMIC_CONSTR_EXPR_FROM_CONCEPT_P (t))
2927	/* The expression of this atomic constraint comes from a concept definition,
2928	whose template depth is always one, so the resulting argument vector
2929	will also have depth one. */
2930	depth = 1;
2931	else
2932	/* Otherwise, the expression of this atomic constraint comes from
2933	the context of the constrained entity, whose template depth is that
2934	of ARGS. */
2935	depth = TMPL_ARGS_DEPTH (args);
2936
2937	/* Place each argument at its corresponding position in the argument
2938	list. Note that the list will be sparse (not all arguments supplied),
2939	but instantiation is guaranteed to only use the parameters in the
2940	mapping, so null arguments would never be used. */
2941	auto_vec< vec<tree> > lists (depth);
2942	lists.quick_grow_cleared (len: depth);
2943	for (tree p = map; p; p = TREE_CHAIN (p))
2944	{
2945	int level;
2946	int index;
2947	template_parm_level_and_index (TREE_VALUE (p), &level, &index);
2948
2949	/* Insert the argument into its corresponding position. */
2950	vec<tree> &list = lists[level - 1];
2951	if (index >= (int)list.length ())
2952	list.safe_grow_cleared (len: index + 1, /*exact=*/false);
2953	list[index] = TREE_PURPOSE (p);
2954	}
2955
2956	/* Build the new argument list. */
2957	args = make_tree_vec (lists.length ());
2958	for (unsigned i = 0; i != lists.length (); ++i)
2959	{
2960	vec<tree> &list = lists[i];
2961	tree level = make_tree_vec (list.length ());
2962	for (unsigned j = 0; j < list.length(); ++j)
2963	TREE_VEC_ELT (level, j) = list[j];
2964	SET_TMPL_ARGS_LEVEL (args, i + 1, level);
2965	list.release ();
2966	}
2967	SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args, 0);
2968
2969	if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (args)
2970	&& TMPL_ARGS_DEPTH (args) == 1)
2971	{
2972	/* Get rid of the redundant outer TREE_VEC. */
2973	tree level = TMPL_ARGS_LEVEL (args, 1);
2974	ggc_free (args);
2975	args = level;
2976	}
2977
2978	return args;
2979	}
2980
2981	static void diagnose_atomic_constraint (tree, tree, tree, sat_info);
2982
2983	/* Compute the satisfaction of an atomic constraint. */
2984
2985	static tree
2986	satisfy_atom (tree t, tree args, sat_info info)
2987	{
2988	/* In case there is a diagnostic, we want to establish the context
2989	prior to printing errors. If no errors occur, this context is
2990	removed before returning. */
2991	diagnosing_failed_constraint failure (t, args, info.noisy ());
2992
2993	satisfaction_cache cache (t, args, info);
2994	if (tree r = cache.get ())
2995	return r;
2996
2997	/* Perform substitution quietly. */
2998	subst_info quiet (tf_none, NULL_TREE);
2999
3000	/* Instantiate the parameter mapping. */
3001	tree map = tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, info: quiet);
3002	if (map == error_mark_node)
3003	{
3004	/* If instantiation of the parameter mapping fails, the constraint is
3005	not satisfied. Replay the substitution. */
3006	if (info.diagnose_unsatisfaction_p ())
3007	tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, info);
3008	if (info.quiet ())
3009	/* Since instantiation of the parameter mapping failed, we
3010	want to diagnose potential instability of this satisfaction
3011	result. */
3012	cache.entry->diagnose_instability = true;
3013	return cache.save (boolean_false_node);
3014	}
3015
3016	/* Now build a new atom using the instantiated mapping. We use
3017	this atom as a second key to the satisfaction cache, and we
3018	also pass it to diagnose_atomic_constraint so that diagnostics
3019	which refer to the atom display the instantiated mapping. */
3020	t = copy_node (t);
3021	ATOMIC_CONSTR_MAP (t) = map;
3022	gcc_assert (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (t));
3023	ATOMIC_CONSTR_MAP_INSTANTIATED_P (t) = true;
3024	satisfaction_cache inst_cache (t, /*args=*/NULL_TREE, info);
3025	if (tree r = inst_cache.get ())
3026	{
3027	cache.entry->location = inst_cache.entry->location;
3028	return cache.save (result: r);
3029	}
3030
3031	/* Rebuild the argument vector from the parameter mapping. */
3032	args = get_mapped_args (t, args);
3033
3034	/* Apply the parameter mapping (i.e., just substitute). */
3035	tree expr = ATOMIC_CONSTR_EXPR (t);
3036	tree result = tsubst_expr (expr, args, quiet.complain, quiet.in_decl);
3037	if (result == error_mark_node)
3038	{
3039	/* If substitution results in an invalid type or expression, the constraint
3040	is not satisfied. Replay the substitution. */
3041	if (info.diagnose_unsatisfaction_p ())
3042	tsubst_expr (expr, args, info.complain, info.in_decl);
3043	return cache.save (result: inst_cache.save (boolean_false_node));
3044	}
3045
3046	/* [17.4.1.2] ... lvalue-to-rvalue conversion is performed as necessary,
3047	and EXPR shall be a constant expression of type bool. */
3048	result = force_rvalue (result, info.complain);
3049	if (result == error_mark_node)
3050	return cache.save (result: inst_cache.save (error_mark_node));
3051	if (!same_type_p (TREE_TYPE (result), boolean_type_node))
3052	{
3053	if (info.noisy ())
3054	diagnose_atomic_constraint (t, args, result, info);
3055	return cache.save (result: inst_cache.save (error_mark_node));
3056	}
3057
3058	/* Compute the value of the constraint. */
3059	if (info.noisy ())
3060	{
3061	iloc_sentinel ils (EXPR_LOCATION (result));
3062	result = cxx_constant_value (result);
3063	}
3064	else
3065	{
3066	result = maybe_constant_value (result, NULL_TREE, mce_true);
3067	if (!TREE_CONSTANT (result))
3068	result = error_mark_node;
3069	}
3070	result = satisfaction_value (t: result);
3071	if (result == boolean_false_node && info.diagnose_unsatisfaction_p ())
3072	diagnose_atomic_constraint (t, args, result, info);
3073
3074	return cache.save (result: inst_cache.save (result));
3075	}
3076
3077	/* Determine if the normalized constraint T is satisfied.
3078	Returns boolean_true_node if the expression/constraint is
3079	satisfied, boolean_false_node if not, and error_mark_node
3080	if the there was an error evaluating the constraint.
3081
3082	The parameter mapping of atomic constraints is simply the
3083	set of template arguments that will be substituted into
3084	the expression, regardless of template parameters appearing
3085	withing. Whether a template argument is used in the atomic
3086	constraint only matters for subsumption. */
3087
3088	static tree
3089	satisfy_constraint_r (tree t, tree args, sat_info info)
3090	{
3091	if (t == error_mark_node)
3092	return error_mark_node;
3093
3094	switch (TREE_CODE (t))
3095	{
3096	case CONJ_CONSTR:
3097	return satisfy_conjunction (t, args, info);
3098	case DISJ_CONSTR:
3099	return satisfy_disjunction (t, args, info);
3100	case ATOMIC_CONSTR:
3101	return satisfy_atom (t, args, info);
3102	default:
3103	gcc_unreachable ();
3104	}
3105	}
3106
3107	/* Check that the normalized constraint T is satisfied for ARGS. */
3108
3109	static tree
3110	satisfy_normalized_constraints (tree t, tree args, sat_info info)
3111	{
3112	auto_timevar time (TV_CONSTRAINT_SAT);
3113
3114	auto ovr = make_temp_override (var&: satisfying_constraint, overrider: true);
3115
3116	/* Turn off template processing. Constraint satisfaction only applies
3117	to non-dependent terms, so we want to ensure full checking here. */
3118	processing_template_decl_sentinel proc (true);
3119
3120	/* We need to check access during satisfaction. */
3121	deferring_access_check_sentinel acs (dk_no_deferred);
3122
3123	/* Constraints are unevaluated operands. */
3124	cp_unevaluated u;
3125
3126	return satisfy_constraint_r (t, args, info);
3127	}
3128
3129	/* Return the normal form of the constraints on the placeholder 'auto'
3130	type T. */
3131
3132	static tree
3133	normalize_placeholder_type_constraints (tree t, bool diag)
3134	{
3135	gcc_assert (is_auto (t));
3136	tree ci = PLACEHOLDER_TYPE_CONSTRAINTS_INFO (t);
3137	if (!ci)
3138	return NULL_TREE;
3139
3140	tree constr = TREE_VALUE (ci);
3141	/* The TREE_PURPOSE contains the set of template parameters that were in
3142	scope for this placeholder type; use them as the initial template
3143	parameters for normalization. */
3144	tree initial_parms = TREE_PURPOSE (ci);
3145
3146	/* The 'auto' itself is used as the first argument in its own constraints,
3147	and its level is one greater than its template depth. So in order to
3148	capture all used template parameters, we need to add an extra level of
3149	template parameters to the context; a dummy level suffices. */
3150	initial_parms
3151	= tree_cons (size_int (initial_parms
3152	? TMPL_PARMS_DEPTH (initial_parms) + 1 : 1),
3153	make_tree_vec (0), initial_parms);
3154
3155	norm_info info (diag ? tf_norm : tf_none);
3156	info.initial_parms = initial_parms;
3157	return normalize_constraint_expression (expr: constr, info);
3158	}
3159
3160	/* Evaluate the constraints of T using ARGS, returning a satisfaction value.
3161	Here, T can be a concept-id, nested-requirement, placeholder 'auto', or
3162	requires-expression. */
3163
3164	static tree
3165	satisfy_nondeclaration_constraints (tree t, tree args, sat_info info)
3166	{
3167	if (t == error_mark_node)
3168	return error_mark_node;
3169
3170	/* Handle REQUIRES_EXPR directly, bypassing satisfaction. */
3171	if (TREE_CODE (t) == REQUIRES_EXPR)
3172	{
3173	auto ovr = make_temp_override (var&: current_constraint_diagnosis_depth);
3174	if (info.noisy ())
3175	++current_constraint_diagnosis_depth;
3176	return tsubst_requires_expr (t, args, info);
3177	}
3178
3179	/* Get the normalized constraints. */
3180	tree norm;
3181	if (concept_check_p (t))
3182	{
3183	gcc_assert (!args);
3184	tree id = unpack_concept_check (t);
3185	args = TREE_OPERAND (id, 1);
3186	tree tmpl = get_concept_check_template (t: id);
3187	norm = normalize_concept_definition (tmpl, diag: info.noisy ());
3188	}
3189	else if (TREE_CODE (t) == NESTED_REQ)
3190	{
3191	norm_info ninfo (info.noisy () ? tf_norm : tf_none);
3192	/* The TREE_TYPE contains the set of template parameters that were in
3193	scope for this nested requirement; use them as the initial template
3194	parameters for normalization. */
3195	ninfo.initial_parms = TREE_TYPE (t);
3196	norm = normalize_constraint_expression (TREE_OPERAND (t, 0), info: ninfo);
3197	}
3198	else if (is_auto (t))
3199	{
3200	norm = normalize_placeholder_type_constraints (t, diag: info.noisy ());
3201	if (!norm)
3202	return boolean_true_node;
3203	}
3204	else
3205	gcc_unreachable ();
3206
3207	/* Perform satisfaction. */
3208	return satisfy_normalized_constraints (t: norm, args, info);
3209	}
3210
3211	/* Evaluate the associated constraints of the template specialization T
3212	according to INFO, returning a satisfaction value. */
3213
3214	static tree
3215	satisfy_declaration_constraints (tree t, sat_info info)
3216	{
3217	gcc_assert (DECL_P (t) && TREE_CODE (t) != TEMPLATE_DECL);
3218	const tree saved_t = t;
3219
3220	/* For inherited constructors, consider the original declaration;
3221	it has the correct template information attached. */
3222	t = strip_inheriting_ctors (t);
3223	tree inh_ctor_targs = NULL_TREE;
3224	if (t != saved_t)
3225	if (tree ti = DECL_TEMPLATE_INFO (saved_t))
3226	/* The inherited constructor points to an instantiation of a constructor
3227	template; remember its template arguments. */
3228	inh_ctor_targs = TI_ARGS (ti);
3229
3230	/* Update the declaration for diagnostics. */
3231	info.in_decl = t;
3232
3233	if (info.quiet ())
3234	if (tree *result = hash_map_safe_get (h: decl_satisfied_cache, k: saved_t))
3235	return *result;
3236
3237	tree args = NULL_TREE;
3238	if (tree ti = DECL_TEMPLATE_INFO (t))
3239	{
3240	/* The initial parameter mapping is the complete set of
3241	template arguments substituted into the declaration. */
3242	args = TI_ARGS (ti);
3243	if (inh_ctor_targs)
3244	args = add_outermost_template_args (args, inh_ctor_targs);
3245	}
3246
3247	if (regenerated_lambda_fn_p (t))
3248	{
3249	/* The TI_ARGS of a regenerated lambda contains only the innermost
3250	set of template arguments. Augment this with the outer template
3251	arguments that were used to regenerate the lambda. */
3252	gcc_assert (!args || TMPL_ARGS_DEPTH (args) == 1);
3253	tree regen_args = lambda_regenerating_args (t);
3254	if (args)
3255	args = add_to_template_args (regen_args, args);
3256	else
3257	args = regen_args;
3258	}
3259
3260	/* If the innermost arguments are dependent, or if the outer arguments
3261	are dependent and are needed by the constraints, we can't check
3262	satisfaction yet so pretend they're satisfied for now. */
3263	if (uses_template_parms (args)
3264	&& ((DECL_TEMPLATE_INFO (t)
3265	&& PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (t))
3266	&& (TMPL_ARGS_DEPTH (args) == 1
3267	|| uses_template_parms (INNERMOST_TEMPLATE_ARGS (args))))
3268	|| uses_outer_template_parms_in_constraints (t)))
3269	return boolean_true_node;
3270
3271	/* Get the normalized constraints. */
3272	tree norm = get_normalized_constraints_from_decl (d: t, diag: info.noisy ());
3273
3274	unsigned ftc_count = vec_safe_length (v: failed_type_completions);
3275
3276	tree result = boolean_true_node;
3277	if (norm)
3278	{
3279	if (!push_tinst_level (t))
3280	return result;
3281	push_to_top_level ();
3282	push_access_scope (t);
3283	result = satisfy_normalized_constraints (t: norm, args, info);
3284	pop_access_scope (t);
3285	pop_from_top_level ();
3286	pop_tinst_level ();
3287	}
3288
3289	/* True if this satisfaction is (heuristically) potentially unstable, i.e.
3290	if its result may depend on where in the program it was performed. */
3291	bool maybe_unstable_satisfaction = false;
3292	if (ftc_count != vec_safe_length (v: failed_type_completions))
3293	/* Type completion failure occurred during satisfaction. The satisfaction
3294	result may (or may not) materially depend on the completeness of a type,
3295	so we consider it potentially unstable. */
3296	maybe_unstable_satisfaction = true;
3297
3298	if (maybe_unstable_satisfaction)
3299	/* Don't cache potentially unstable satisfaction, to allow satisfy_atom
3300	to check the stability the next time around. */;
3301	else if (info.quiet ())
3302	hash_map_safe_put<hm_ggc> (h&: decl_satisfied_cache, k: saved_t, v: result);
3303
3304	return result;
3305	}
3306
3307	/* Evaluate the associated constraints of the template T using ARGS as the
3308	innermost set of template arguments and according to INFO, returning a
3309	satisfaction value. */
3310
3311	static tree
3312	satisfy_declaration_constraints (tree t, tree args, sat_info info)
3313	{
3314	/* Update the declaration for diagnostics. */
3315	info.in_decl = t;
3316
3317	gcc_assert (TREE_CODE (t) == TEMPLATE_DECL);
3318
3319	if (regenerated_lambda_fn_p (t))
3320	{
3321	/* As in the two-parameter version of this function. */
3322	gcc_assert (TMPL_ARGS_DEPTH (args) == 1);
3323	tree lambda = CLASSTYPE_LAMBDA_EXPR (DECL_CONTEXT (t));
3324	tree outer_args = TI_ARGS (LAMBDA_EXPR_REGEN_INFO (lambda));
3325	args = add_to_template_args (outer_args, args);
3326	}
3327	else
3328	args = add_outermost_template_args (t, args);
3329
3330	/* If the innermost arguments are dependent, or if the outer arguments
3331	are dependent and are needed by the constraints, we can't check
3332	satisfaction yet so pretend they're satisfied for now. */
3333	if (uses_template_parms (args)
3334	&& (TMPL_ARGS_DEPTH (args) == 1
3335	|| uses_template_parms (INNERMOST_TEMPLATE_ARGS (args))
3336	|| uses_outer_template_parms_in_constraints (t)))
3337	return boolean_true_node;
3338
3339	tree result = boolean_true_node;
3340	if (tree norm = get_normalized_constraints_from_decl (d: t, diag: info.noisy ()))
3341	{
3342	if (!push_tinst_level (t, args))
3343	return result;
3344	tree pattern = DECL_TEMPLATE_RESULT (t);
3345	push_to_top_level ();
3346	push_access_scope (pattern);
3347	result = satisfy_normalized_constraints (t: norm, args, info);
3348	pop_access_scope (pattern);
3349	pop_from_top_level ();
3350	pop_tinst_level ();
3351	}
3352
3353	return result;
3354	}
3355
3356	/* A wrapper around satisfy_declaration_constraints and
3357	satisfy_nondeclaration_constraints which additionally replays
3358	quiet ill-formed satisfaction noisily, so that ill-formed
3359	satisfaction always gets diagnosed. */
3360
3361	static tree
3362	constraint_satisfaction_value (tree t, tree args, sat_info info)
3363	{
3364	tree r;
3365	if (DECL_P (t))
3366	{
3367	if (args)
3368	r = satisfy_declaration_constraints (t, args, info);
3369	else
3370	r = satisfy_declaration_constraints (t, info);
3371	}
3372	else
3373	r = satisfy_nondeclaration_constraints (t, args, info);
3374	if (r == error_mark_node && info.quiet ()
3375	&& !(DECL_P (t) && warning_suppressed_p (t)))
3376	{
3377	/* Replay the error noisily. */
3378	sat_info noisy (tf_warning_or_error, info.in_decl);
3379	constraint_satisfaction_value (t, args, info: noisy);
3380	if (DECL_P (t) && !args)
3381	/* Avoid giving these errors again. */
3382	suppress_warning (t);
3383	}
3384	return r;
3385	}
3386
3387	/* True iff the result of satisfying T using ARGS is BOOLEAN_TRUE_NODE
3388	and false otherwise, even in the case of errors.
3389
3390	Here, T can be:
3391	- a template declaration
3392	- a template specialization (in which case ARGS must be empty)
3393	- a concept-id (in which case ARGS must be empty)
3394	- a nested-requirement
3395	- a placeholder 'auto'
3396	- a requires-expression. */
3397
3398	bool
3399	constraints_satisfied_p (tree t, tree args/*= NULL_TREE */)
3400	{
3401	if (!flag_concepts)
3402	return true;
3403
3404	sat_info quiet (tf_none, NULL_TREE);
3405	return constraint_satisfaction_value (t, args, info: quiet) == boolean_true_node;
3406	}
3407
3408	/* Evaluate a concept check of the form C<ARGS>. This is only used for the
3409	evaluation of template-ids as id-expressions. */
3410
3411	tree
3412	evaluate_concept_check (tree check)
3413	{
3414	if (check == error_mark_node)
3415	return error_mark_node;
3416
3417	gcc_assert (concept_check_p (check));
3418
3419	/* Check for satisfaction without diagnostics. */
3420	sat_info quiet (tf_none, NULL_TREE);
3421	return constraint_satisfaction_value (t: check, /*args=*/NULL_TREE, info: quiet);
3422	}
3423
3424	/* Evaluate the requires-expression T, returning either boolean_true_node
3425	or boolean_false_node. This is used during folding and constexpr
3426	evaluation. */
3427
3428	tree
3429	evaluate_requires_expr (tree t)
3430	{
3431	gcc_assert (TREE_CODE (t) == REQUIRES_EXPR);
3432	sat_info quiet (tf_none, NULL_TREE);
3433	return constraint_satisfaction_value (t, /*args=*/NULL_TREE, info: quiet);
3434	}
3435
3436	/*---------------------------------------------------------------------------
3437	Semantic analysis of requires-expressions
3438	---------------------------------------------------------------------------*/
3439
3440	/* Finish a requires expression for the given PARMS (possibly
3441	null) and the non-empty sequence of requirements. */
3442
3443	tree
3444	finish_requires_expr (location_t loc, tree parms, tree reqs)
3445	{
3446	/* Build the node. */
3447	tree r = build_min (REQUIRES_EXPR, boolean_type_node, parms, reqs, NULL_TREE);
3448	TREE_SIDE_EFFECTS (r) = false;
3449	TREE_CONSTANT (r) = true;
3450	SET_EXPR_LOCATION (r, loc);
3451	return r;
3452	}
3453
3454	/* Construct a requirement for the validity of EXPR. */
3455
3456	tree
3457	finish_simple_requirement (location_t loc, tree expr)
3458	{
3459	tree r = build_nt (SIMPLE_REQ, expr);
3460	SET_EXPR_LOCATION (r, loc);
3461	return r;
3462	}
3463
3464	/* Construct a requirement for the validity of TYPE. */
3465
3466	tree
3467	finish_type_requirement (location_t loc, tree type)
3468	{
3469	tree r = build_nt (TYPE_REQ, type);
3470	SET_EXPR_LOCATION (r, loc);
3471	return r;
3472	}
3473
3474	/* Construct a requirement for the validity of EXPR, along with
3475	its properties. if TYPE is non-null, then it specifies either
3476	an implicit conversion or argument deduction constraint,
3477	depending on whether any placeholders occur in the type name.
3478	NOEXCEPT_P is true iff the noexcept keyword was specified. */
3479
3480	tree
3481	finish_compound_requirement (location_t loc, tree expr, tree type, bool noexcept_p)
3482	{
3483	tree req = build_nt (COMPOUND_REQ, expr, type);
3484	SET_EXPR_LOCATION (req, loc);
3485	COMPOUND_REQ_NOEXCEPT_P (req) = noexcept_p;
3486	return req;
3487	}
3488
3489	/* Finish a nested requirement. */
3490
3491	tree
3492	finish_nested_requirement (location_t loc, tree expr)
3493	{
3494	/* Build the requirement, saving the set of in-scope template
3495	parameters as its type. */
3496	tree r = build1 (NESTED_REQ, current_template_parms, expr);
3497	SET_EXPR_LOCATION (r, loc);
3498	return r;
3499	}
3500
3501	/* Check that FN satisfies the structural requirements of a
3502	function concept definition. */
3503	tree
3504	check_function_concept (tree fn)
3505	{
3506	/* Check that the function is comprised of only a return statement. */
3507	tree body = DECL_SAVED_TREE (fn);
3508	if (TREE_CODE (body) == BIND_EXPR)
3509	body = BIND_EXPR_BODY (body);
3510
3511	/* Sometimes a function call results in the creation of clean up
3512	points. Allow these to be preserved in the body of the
3513	constraint, as we might actually need them for some constexpr
3514	evaluations. */
3515	if (TREE_CODE (body) == CLEANUP_POINT_EXPR)
3516	body = TREE_OPERAND (body, 0);
3517
3518	/* Check that the definition is written correctly. */
3519	if (TREE_CODE (body) != RETURN_EXPR)
3520	{
3521	location_t loc = DECL_SOURCE_LOCATION (fn);
3522	if (TREE_CODE (body) == STATEMENT_LIST && !STATEMENT_LIST_HEAD (body))
3523	{
3524	if (seen_error ())
3525	/* The definition was probably erroneous, not empty. */;
3526	else
3527	error_at (loc, "definition of concept %qD is empty", fn);
3528	}
3529	else
3530	error_at (loc, "definition of concept %qD has multiple statements", fn);
3531	}
3532
3533	return NULL_TREE;
3534	}
3535
3536	/*---------------------------------------------------------------------------
3537	Equivalence of constraints
3538	---------------------------------------------------------------------------*/
3539
3540	/* Returns true when A and B are equivalent constraints. */
3541	bool
3542	equivalent_constraints (tree a, tree b)
3543	{
3544	gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
3545	gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
3546	return cp_tree_equal (a, b);
3547	}
3548
3549	/* Returns true if the template declarations A and B have equivalent
3550	constraints. This is the case when A's constraints subsume B's and
3551	when B's also constrain A's. */
3552	bool
3553	equivalently_constrained (tree d1, tree d2)
3554	{
3555	gcc_assert (TREE_CODE (d1) == TREE_CODE (d2));
3556	return equivalent_constraints (a: get_constraints (t: d1), b: get_constraints (t: d2));
3557	}
3558
3559	/*---------------------------------------------------------------------------
3560	Partial ordering of constraints
3561	---------------------------------------------------------------------------*/
3562
3563	/* Returns true when the constraints in CI strictly subsume
3564	the associated constraints of TMPL. */
3565
3566	bool
3567	strictly_subsumes (tree ci, tree tmpl)
3568	{
3569	tree n1 = get_normalized_constraints_from_info (ci, NULL_TREE);
3570	tree n2 = get_normalized_constraints_from_decl (d: tmpl);
3571
3572	return subsumes (n1, n2) && !subsumes (n2, n1);
3573	}
3574
3575	/* Returns true when the constraints in CI subsume the
3576	associated constraints of TMPL. */
3577
3578	bool
3579	weakly_subsumes (tree ci, tree tmpl)
3580	{
3581	tree n1 = get_normalized_constraints_from_info (ci, NULL_TREE);
3582	tree n2 = get_normalized_constraints_from_decl (d: tmpl);
3583
3584	return subsumes (n1, n2);
3585	}
3586
3587	/* Determines which of the declarations, A or B, is more constrained.
3588	That is, which declaration's constraints subsume but are not subsumed
3589	by the other's?
3590
3591	Returns 1 if D1 is more constrained than D2, -1 if D2 is more constrained
3592	than D1, and 0 otherwise. */
3593
3594	int
3595	more_constrained (tree d1, tree d2)
3596	{
3597	tree n1 = get_normalized_constraints_from_decl (d: d1);
3598	tree n2 = get_normalized_constraints_from_decl (d: d2);
3599
3600	int winner = 0;
3601	if (subsumes (n1, n2))
3602	++winner;
3603	if (subsumes (n2, n1))
3604	--winner;
3605	return winner;
3606	}
3607
3608	/* Return whether D1 is at least as constrained as D2. */
3609
3610	bool
3611	at_least_as_constrained (tree d1, tree d2)
3612	{
3613	tree n1 = get_normalized_constraints_from_decl (d: d1);
3614	tree n2 = get_normalized_constraints_from_decl (d: d2);
3615
3616	return subsumes (n1, n2);
3617	}
3618
3619	/*---------------------------------------------------------------------------
3620	Constraint diagnostics
3621	---------------------------------------------------------------------------*/
3622
3623	/* Returns the best location to diagnose a constraint error. */
3624
3625	static location_t
3626	get_constraint_error_location (tree t)
3627	{
3628	if (location_t loc = cp_expr_location (t_: t))
3629	return loc;
3630
3631	/* If we have a specific location give it. */
3632	tree expr = CONSTR_EXPR (t);
3633	if (location_t loc = cp_expr_location (t_: expr))
3634	return loc;
3635
3636	/* If the constraint is normalized from a requires-clause, give
3637	the location as that of the constrained declaration. */
3638	tree cxt = CONSTR_CONTEXT (t);
3639	tree src = cxt ? TREE_VALUE (cxt) : NULL_TREE;
3640	if (!src)
3641	/* TODO: This only happens for constrained non-template declarations. */
3642	;
3643	else if (DECL_P (src))
3644	return DECL_SOURCE_LOCATION (src);
3645	/* Otherwise, give the location as the defining concept. */
3646	else if (concept_check_p (t: src))
3647	{
3648	tree id = unpack_concept_check (t: src);
3649	tree tmpl = TREE_OPERAND (id, 0);
3650	if (OVL_P (tmpl))
3651	tmpl = OVL_FIRST (tmpl);
3652	return DECL_SOURCE_LOCATION (tmpl);
3653	}
3654
3655	return input_location;
3656	}
3657
3658	/* Emit a diagnostic for a failed trait. */
3659
3660	static void
3661	diagnose_trait_expr (tree expr, tree args)
3662	{
3663	location_t loc = cp_expr_location (t_: expr);
3664
3665	/* Build a "fake" version of the instantiated trait, so we can
3666	get the instantiated types from result. */
3667	++processing_template_decl;
3668	expr = tsubst_expr (expr, args, tf_none, NULL_TREE);
3669	--processing_template_decl;
3670
3671	tree t1 = TRAIT_EXPR_TYPE1 (expr);
3672	tree t2 = TRAIT_EXPR_TYPE2 (expr);
3673	if (t2 && TREE_CODE (t2) == TREE_VEC)
3674	{
3675	/* Convert the TREE_VEC of arguments into a TREE_LIST, since we can't
3676	directly print a TREE_VEC but we can a TREE_LIST via the E format
3677	specifier. */
3678	tree list = NULL_TREE;
3679	for (tree t : tree_vec_range (t2))
3680	list = tree_cons (NULL_TREE, t, list);
3681	t2 = nreverse (list);
3682	}
3683	switch (TRAIT_EXPR_KIND (expr))
3684	{
3685	case CPTK_HAS_NOTHROW_ASSIGN:
3686	inform (loc, " %qT is not nothrow copy assignable", t1);
3687	break;
3688	case CPTK_HAS_NOTHROW_CONSTRUCTOR:
3689	inform (loc, " %qT is not nothrow default constructible", t1);
3690	break;
3691	case CPTK_HAS_NOTHROW_COPY:
3692	inform (loc, " %qT is not nothrow copy constructible", t1);
3693	break;
3694	case CPTK_HAS_TRIVIAL_ASSIGN:
3695	inform (loc, " %qT is not trivially copy assignable", t1);
3696	break;
3697	case CPTK_HAS_TRIVIAL_CONSTRUCTOR:
3698	inform (loc, " %qT is not trivially default constructible", t1);
3699	break;
3700	case CPTK_HAS_TRIVIAL_COPY:
3701	inform (loc, " %qT is not trivially copy constructible", t1);
3702	break;
3703	case CPTK_HAS_TRIVIAL_DESTRUCTOR:
3704	inform (loc, " %qT is not trivially destructible", t1);
3705	break;
3706	case CPTK_HAS_VIRTUAL_DESTRUCTOR:
3707	inform (loc, " %qT does not have a virtual destructor", t1);
3708	break;
3709	case CPTK_IS_ABSTRACT:
3710	inform (loc, " %qT is not an abstract class", t1);
3711	break;
3712	case CPTK_IS_BASE_OF:
3713	inform (loc, " %qT is not a base of %qT", t1, t2);
3714	break;
3715	case CPTK_IS_CLASS:
3716	inform (loc, " %qT is not a class", t1);
3717	break;
3718	case CPTK_IS_EMPTY:
3719	inform (loc, " %qT is not an empty class", t1);
3720	break;
3721	case CPTK_IS_ENUM:
3722	inform (loc, " %qT is not an enum", t1);
3723	break;
3724	case CPTK_IS_FINAL:
3725	inform (loc, " %qT is not a final class", t1);
3726	break;
3727	case CPTK_IS_LAYOUT_COMPATIBLE:
3728	inform (loc, " %qT is not layout compatible with %qT", t1, t2);
3729	break;
3730	case CPTK_IS_LITERAL_TYPE:
3731	inform (loc, " %qT is not a literal type", t1);
3732	break;
3733	case CPTK_IS_POINTER_INTERCONVERTIBLE_BASE_OF:
3734	inform (loc, " %qT is not pointer-interconvertible base of %qT",
3735	t1, t2);
3736	break;
3737	case CPTK_IS_POD:
3738	inform (loc, " %qT is not a POD type", t1);
3739	break;
3740	case CPTK_IS_POLYMORPHIC:
3741	inform (loc, " %qT is not a polymorphic type", t1);
3742	break;
3743	case CPTK_IS_SAME:
3744	inform (loc, " %qT is not the same as %qT", t1, t2);
3745	break;
3746	case CPTK_IS_STD_LAYOUT:
3747	inform (loc, " %qT is not an standard layout type", t1);
3748	break;
3749	case CPTK_IS_TRIVIAL:
3750	inform (loc, " %qT is not a trivial type", t1);
3751	break;
3752	case CPTK_IS_UNION:
3753	inform (loc, " %qT is not a union", t1);
3754	break;
3755	case CPTK_IS_AGGREGATE:
3756	inform (loc, " %qT is not an aggregate", t1);
3757	break;
3758	case CPTK_IS_TRIVIALLY_COPYABLE:
3759	inform (loc, " %qT is not trivially copyable", t1);
3760	break;
3761	case CPTK_IS_ASSIGNABLE:
3762	inform (loc, " %qT is not assignable from %qT", t1, t2);
3763	break;
3764	case CPTK_IS_TRIVIALLY_ASSIGNABLE:
3765	inform (loc, " %qT is not trivially assignable from %qT", t1, t2);
3766	break;
3767	case CPTK_IS_NOTHROW_ASSIGNABLE:
3768	inform (loc, " %qT is not nothrow assignable from %qT", t1, t2);
3769	break;
3770	case CPTK_IS_CONSTRUCTIBLE:
3771	if (!t2)
3772	inform (loc, " %qT is not default constructible", t1);
3773	else
3774	inform (loc, " %qT is not constructible from %qE", t1, t2);
3775	break;
3776	case CPTK_IS_TRIVIALLY_CONSTRUCTIBLE:
3777	if (!t2)
3778	inform (loc, " %qT is not trivially default constructible", t1);
3779	else
3780	inform (loc, " %qT is not trivially constructible from %qE", t1, t2);
3781	break;
3782	case CPTK_IS_NOTHROW_CONSTRUCTIBLE:
3783	if (!t2)
3784	inform (loc, " %qT is not nothrow default constructible", t1);
3785	else
3786	inform (loc, " %qT is not nothrow constructible from %qE", t1, t2);
3787	break;
3788	case CPTK_HAS_UNIQUE_OBJ_REPRESENTATIONS:
3789	inform (loc, " %qT does not have unique object representations", t1);
3790	break;
3791	case CPTK_IS_CONVERTIBLE:
3792	inform (loc, " %qT is not convertible from %qE", t2, t1);
3793	break;
3794	case CPTK_IS_NOTHROW_CONVERTIBLE:
3795	inform (loc, " %qT is not nothrow convertible from %qE", t2, t1);
3796	break;
3797	case CPTK_REF_CONSTRUCTS_FROM_TEMPORARY:
3798	inform (loc, " %qT is not a reference that binds to a temporary "
3799	"object of type %qT (direct-initialization)", t1, t2);
3800	break;
3801	case CPTK_REF_CONVERTS_FROM_TEMPORARY:
3802	inform (loc, " %qT is not a reference that binds to a temporary "
3803	"object of type %qT (copy-initialization)", t1, t2);
3804	break;
3805	case CPTK_IS_DEDUCIBLE:
3806	inform (loc, " %qD is not deducible from %qT", t1, t2);
3807	break;
3808	#define DEFTRAIT_TYPE(CODE, NAME, ARITY) \
3809	case CPTK_##CODE:
3810	#include "cp-trait.def"
3811	#undef DEFTRAIT_TYPE
3812	/* Type-yielding traits aren't expressions. */
3813	gcc_unreachable ();
3814	/* We deliberately omit the default case so that when adding a new
3815	trait we'll get reminded (by way of a warning) to handle it here. */
3816	}
3817	}
3818
3819	/* Diagnose a substitution failure in the atomic constraint T using ARGS. */
3820
3821	static void
3822	diagnose_atomic_constraint (tree t, tree args, tree result, sat_info info)
3823	{
3824	/* If the constraint is already ill-formed, we've previously diagnosed
3825	the reason. We should still say why the constraints aren't satisfied. */
3826	if (t == error_mark_node)
3827	{
3828	location_t loc;
3829	if (info.in_decl)
3830	loc = DECL_SOURCE_LOCATION (info.in_decl);
3831	else
3832	loc = input_location;
3833	inform (loc, "invalid constraints");
3834	return;
3835	}
3836
3837	location_t loc = get_constraint_error_location (t);
3838	iloc_sentinel loc_s (loc);
3839
3840	/* Generate better diagnostics for certain kinds of expressions. */
3841	tree expr = ATOMIC_CONSTR_EXPR (t);
3842	STRIP_ANY_LOCATION_WRAPPER (expr);
3843	switch (TREE_CODE (expr))
3844	{
3845	case TRAIT_EXPR:
3846	diagnose_trait_expr (expr, args);
3847	break;
3848	case REQUIRES_EXPR:
3849	gcc_checking_assert (info.diagnose_unsatisfaction_p ());
3850	/* Clear in_decl before replaying the substitution to avoid emitting
3851	seemingly unhelpful "in declaration ..." notes that follow some
3852	substitution failure error messages. */
3853	info.in_decl = NULL_TREE;
3854	tsubst_requires_expr (t: expr, args, info);
3855	break;
3856	default:
3857	if (!same_type_p (TREE_TYPE (result), boolean_type_node))
3858	error_at (loc, "constraint %qE has type %qT, not %<bool%>",
3859	t, TREE_TYPE (result));
3860	else
3861	inform (loc, "the expression %qE evaluated to %<false%>", t);
3862	}
3863	}
3864
3865	GTY(()) tree current_failed_constraint;
3866
3867	diagnosing_failed_constraint::
3868	diagnosing_failed_constraint (tree t, tree args, bool diag)
3869	: diagnosing_error (diag)
3870	{
3871	if (diagnosing_error)
3872	{
3873	current_failed_constraint
3874	= tree_cons (args, t, current_failed_constraint);
3875	++current_constraint_diagnosis_depth;
3876	}
3877	}
3878
3879	diagnosing_failed_constraint::
3880	~diagnosing_failed_constraint ()
3881	{
3882	if (diagnosing_error)
3883	{
3884	--current_constraint_diagnosis_depth;
3885	if (current_failed_constraint)
3886	current_failed_constraint = TREE_CHAIN (current_failed_constraint);
3887	}
3888
3889	}
3890
3891	/* Whether we are allowed to replay an error that underlies a constraint failure
3892	at the current diagnosis depth. */
3893
3894	bool
3895	diagnosing_failed_constraint::replay_errors_p ()
3896	{
3897	if (current_constraint_diagnosis_depth >= concepts_diagnostics_max_depth)
3898	{
3899	concepts_diagnostics_max_depth_exceeded_p = true;
3900	return false;
3901	}
3902	else
3903	return true;
3904	}
3905
3906	/* Emit diagnostics detailing the failure ARGS to satisfy the constraints
3907	of T. Here, T and ARGS are as in constraints_satisfied_p. */
3908
3909	void
3910	diagnose_constraints (location_t loc, tree t, tree args)
3911	{
3912	inform (loc, "constraints not satisfied");
3913
3914	if (concepts_diagnostics_max_depth == 0)
3915	return;
3916
3917	/* Replay satisfaction, but diagnose unsatisfaction. */
3918	sat_info noisy (tf_warning_or_error, NULL_TREE, /*diag_unsat=*/true);
3919	constraint_satisfaction_value (t, args, info: noisy);
3920
3921	static bool suggested_p;
3922	if (concepts_diagnostics_max_depth_exceeded_p
3923	&& current_constraint_diagnosis_depth == 0
3924	&& !suggested_p)
3925	{
3926	inform (UNKNOWN_LOCATION,
3927	"set %qs to at least %d for more detail",
3928	"-fconcepts-diagnostics-depth=",
3929	concepts_diagnostics_max_depth + 1);
3930	suggested_p = true;
3931	}
3932	}
3933
3934	#include "gt-cp-constraint.h"
3935