c++: Nondeterministic concepts diagnostics [PR94830]

This patch makes the order in which template parameters appear in the
TREE_LIST returned by find_template_parameters deterministic between
runs.

The current nondeterminism is semantically harmless, but it has the
undesirable effect of causing some concepts diagnostics which print a
constraint's parameter mapping via pp_cxx_parameter_mapping to also be
nondeterministic, as in the testcases below.

gcc/cp/ChangeLog:

	PR c++/94830
	* pt.c (find_template_parameter_info::parm_list): New field.
	(keep_template_parm): Use the new field to build up the
	parameter list here instead of ...
	(find_template_parameters): ... here.  Return ftpi.parm_list.

gcc/testsuite/ChangeLog:

	PR c++/94830
	* g++.dg/concepts/diagnostics12.C: Clarify the dg-message now
	that the corresponding diagnostic is deterministic.
	* g++.dg/concepts/diagnostics13.C: New test.

5 files changed, 36 insertions, 8 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 41db16e..cbedbab 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,11 @@
+2020-04-29  Patrick Palka  <ppalka@redhat.com>
+
+	PR c++/94830
+	* pt.c (find_template_parameter_info::parm_list): New field.
+	(keep_template_parm): Use the new field to build up the
+	parameter list here instead of ...
+	(find_template_parameters): ... here.  Return ftpi.parm_list.
+
 2020-04-29  Jakub Jelinek  <jakub@redhat.com>
 
 	PR target/94707
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index ba22d9e..d28585e 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -10439,12 +10439,14 @@ for_each_template_parm (tree t, tree_fn_t fn, void* data,
 struct find_template_parameter_info
 {
   explicit find_template_parameter_info (tree ctx_parms)
-    : ctx_parms (ctx_parms),
+    : parm_list (NULL_TREE),
+      ctx_parms (ctx_parms),
       max_depth (TMPL_PARMS_DEPTH (ctx_parms))
   {}
 
   hash_set<tree> visited;
   hash_set<tree> parms;
+  tree parm_list;
   tree ctx_parms;
   int max_depth;
 };
@@ -10476,7 +10478,8 @@ keep_template_parm (tree t, void* data)
      T and const T. Adjust types to their unqualified versions.  */
   if (TYPE_P (t))
     t = TYPE_MAIN_VARIANT (t);
-  ftpi->parms.add (t);
+  if (!ftpi->parms.add (t))
+    ftpi->parm_list = tree_cons (NULL_TREE, t, ftpi->parm_list);
 
   return 0;
 }
@@ -10587,11 +10590,7 @@ find_template_parameters (tree t, tree ctx_parms)
   find_template_parameter_info ftpi (ctx_parms);
   for_each_template_parm (t, keep_template_parm, &ftpi, &ftpi.visited,
 			  /*include_nondeduced*/true, any_template_parm_r);
-  tree list = NULL_TREE;
-  for (hash_set<tree>::iterator iter = ftpi.parms.begin();
-       iter != ftpi.parms.end(); ++iter)
-    list = tree_cons (NULL_TREE, *iter, list);
-  return list;
+  return ftpi.parm_list;
 }
 
 /* Returns true if T depends on any template parameter.  */
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index b635ce1..0fce8fb 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2020-04-29  Patrick Palka  <ppalka@redhat.com>
+
+	PR c++/94830
+	* g++.dg/concepts/diagnostics12.C: Clarify the dg-message now
+	that the corresponding diagnostic is deterministic.
+	* g++.dg/concepts/diagnostics13.C: New test.
+
 2020-04-29  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR target/93654
diff --git a/gcc/testsuite/g++.dg/concepts/diagnostic12.C b/gcc/testsuite/g++.dg/concepts/diagnostic12.C
index a757342..548ba9c 100644
--- a/gcc/testsuite/g++.dg/concepts/diagnostic12.C
+++ b/gcc/testsuite/g++.dg/concepts/diagnostic12.C
@@ -3,7 +3,7 @@
 
 template<typename T, typename... Args>
   concept c1 = requires (T t, Args... args) { *t; };
-// { dg-message "in requirements with .T t., .Args ... args. .with.* Args = \{\}" "" { target *-*-* } .-1 }
+// { dg-message "in requirements with .T t., .Args ... args. .with Args = \{\}; T = int" "" { target *-*-* } .-1 }
 
 static_assert(c1<int>); // { dg-error "failed" }
 
diff --git a/gcc/testsuite/g++.dg/concepts/diagnostic13.C b/gcc/testsuite/g++.dg/concepts/diagnostic13.C
new file mode 100644
index 0000000..accd8a6
--- /dev/null
+++ b/gcc/testsuite/g++.dg/concepts/diagnostic13.C
@@ -0,0 +1,14 @@
+// PR c++/94830
+// { dg-do compile { target concepts } }
+
+template<typename T, typename R>
+  concept c = __is_same(T, R); // { dg-message "with T = int; R = char" }
+
+template<typename T, typename R>
+  requires c<T,R>
+void foo() { }
+
+void bar()
+{
+  foo<int, char>(); // { dg-error "unsatisfied constraints" }
+}