[gcc r13-4810] c++, tree: walk TREE_VEC (and VECTOR_CST) in natural order [PR101886]

[gcc r13-4810] c++, tree: walk TREE_VEC (and VECTOR_CST) in natural order [PR101886]

[Patrick Palka]

https://gcc.gnu.org/g:8aa045c97485d75e0b6eb1068464c0ddaa6beacb

commit r13-4810-g8aa045c97485d75e0b6eb1068464c0ddaa6beacb
Author: Patrick Palka <ppalka@redhat.com>
Date:   Tue Dec 20 17:02:37 2022 -0500

    c++, tree: walk TREE_VEC (and VECTOR_CST) in natural order [PR101886]
    
    Unfortunately the extract_autos_r fix in r13-4799-ga7c8036b26082d is
    derailed by the fact that walk_tree_1 currently walks the elements of a
    TREE_VEC in reverse, which means for A<auto, auto> in the below testcase
    extract_autos_r ends up adjusting the TEMPLATE_TYPE_IDX of the first
    auto instead of the second one, and the first auto is the canonical auto
    of level 2 (and index 0), so we rightfully trigger the sanity check
    added in that commit.
    
    It seems TREE_VEC and VECTOR_CST are the only trees we walk in reverse,
    and this has been the case since r21884 whence the original version of
    walk_tree_1 was introduced.  But that's arguably unnatural and not
    consistent with how we walk all other compound trees such as CONSTRUCTORs
    and EXPR_P trees in forward order.
    
    So this patch makes walk_tree_1 walk TREE_VEC (and VECTOR_CST) in
    forward order as well, which fixes the testcase.  Doing so revealed that
    keep_template_parm grows the list of found template parameters from the
    front, which previously compensated for the TREE_VEC behavior, so now we
    should grow it from the back.
    
            PR c++/101886
    
    gcc/cp/ChangeLog:
    
            * pt.cc (find_template_parameter_info::parm_list_tail):
            New data member.
            (keep_template_parm): Use parm_list_tail to append rather
            than prepend to parm_list.
    
    gcc/ChangeLog:
    
            * tree.cc (walk_tree_1) <case TREE_VEC>: Walk the elements
            in forward instead of reverse order.
            <case VECTOR_CST>: Likewise.
    
    gcc/testsuite/ChangeLog:
    
            * g++.dg/concepts/diagnostic12.C: Adjust expected order of
            template parameters within pretty printed parameter mapping.
            * g++.dg/concepts/auto6.C: New test.

Diff:
---
 gcc/cp/pt.cc                                 | 13 +++++++++----
 gcc/testsuite/g++.dg/concepts/auto6.C        | 14 ++++++++++++++
 gcc/testsuite/g++.dg/concepts/diagnostic12.C |  2 +-
 gcc/tree.cc                                  | 20 ++++++++++----------
 4 files changed, 34 insertions(+), 15 deletions(-)

diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
index 83da1ba1bf5..2d902988a43 100644
--- a/gcc/cp/pt.cc
+++ b/gcc/cp/pt.cc
@@ -10640,14 +10640,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)
-    : parm_list (NULL_TREE),
-      ctx_parms (ctx_parms),
+    : ctx_parms (ctx_parms),
       max_depth (TMPL_PARMS_DEPTH (ctx_parms))
   {}
 
   hash_set<tree> visited;
   hash_set<tree> parms;
-  tree parm_list;
+  tree parm_list = NULL_TREE;
+  tree *parm_list_tail = &parm_list;
   tree ctx_parms;
   int max_depth;
 };
@@ -10693,7 +10693,12 @@ keep_template_parm (tree t, void* data)
   if (TYPE_P (t))
     t = TYPE_MAIN_VARIANT (t);
   if (!ftpi->parms.add (t))
-    ftpi->parm_list = tree_cons (NULL_TREE, t, ftpi->parm_list);
+    {
+      /* Append T to PARM_LIST.  */
+      tree node = build_tree_list (NULL_TREE, t);
+      *ftpi->parm_list_tail = node;
+      ftpi->parm_list_tail = &TREE_CHAIN (node);
+    }
 
   /* Verify the parameter we found has a valid index.  */
   if (flag_checking)
diff --git a/gcc/testsuite/g++.dg/concepts/auto6.C b/gcc/testsuite/g++.dg/concepts/auto6.C
new file mode 100644
index 00000000000..1f6d72e54cc
--- /dev/null
+++ b/gcc/testsuite/g++.dg/concepts/auto6.C
@@ -0,0 +1,14 @@
+// PR c++/101886
+// { dg-do compile { target c++17_only } }
+// { dg-options "-fconcepts-ts" }
+
+template<typename, typename> struct A { };
+
+template<class T>
+void f() {
+  A<int, int> a;
+  A<auto, auto> b1 = a;
+  A<auto, auto> b2 = a;
+}
+
+template void f<int>();
diff --git a/gcc/testsuite/g++.dg/concepts/diagnostic12.C b/gcc/testsuite/g++.dg/concepts/diagnostic12.C
index 548ba9c1b3d..8086500760b 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 = \{\}; T = int" "" { target *-*-* } .-1 }
+// { dg-message "in requirements with .T t., .Args ... args. .with T = int; Args = \{\}" "" { target *-*-* } .-1 }
 
 static_assert(c1<int>); // { dg-error "failed" }
 
diff --git a/gcc/tree.cc b/gcc/tree.cc
index 0a51f9ddb4d..92199bb6503 100644
--- a/gcc/tree.cc
+++ b/gcc/tree.cc
@@ -11310,12 +11310,12 @@ walk_tree_1 (tree *tp, walk_tree_fn func, void *data,
 	if (len == 0)
 	  break;
 
-	/* Walk all elements but the first.  */
-	while (--len)
-	  WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
+	/* Walk all elements but the last.  */
+	for (int i = 0; i < len - 1; ++i)
+	  WALK_SUBTREE (TREE_VEC_ELT (*tp, i));
 
-	/* Now walk the first one as a tail call.  */
-	WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
+	/* Now walk the last one as a tail call.  */
+	WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, len - 1));
       }
 
     case VECTOR_CST:
@@ -11323,11 +11323,11 @@ walk_tree_1 (tree *tp, walk_tree_fn func, void *data,
 	unsigned len = vector_cst_encoded_nelts (*tp);
 	if (len == 0)
 	  break;
-	/* Walk all elements but the first.  */
-	while (--len)
-	  WALK_SUBTREE (VECTOR_CST_ENCODED_ELT (*tp, len));
-	/* Now walk the first one as a tail call.  */
-	WALK_SUBTREE_TAIL (VECTOR_CST_ENCODED_ELT (*tp, 0));
+	/* Walk all elements but the last.  */
+	for (unsigned i = 0; i < len - 1; ++i)
+	  WALK_SUBTREE (VECTOR_CST_ENCODED_ELT (*tp, i));
+	/* Now walk the last one as a tail call.  */
+	WALK_SUBTREE_TAIL (VECTOR_CST_ENCODED_ELT (*tp, len - 1));
       }
 
     case COMPLEX_CST: