c++/modules: local type merging [PR99426]

One known missing piece in the modules implementation is merging of a
streamed-in local type (class or enum) with the corresponding in-TU
version of the local type.  This missing piece turns out to cause a
hard-to-reduce use-after-free GC issue due to the entity_ary not being
marked as a GC root (deliberately), and manifests as a serialization
error on stream-in as in PR99426 (see comment #6 for a reduction).  It's
also reproducible on trunk when running the xtreme-header tests without
-fno-module-lazy.

This patch implements this missing piece, making us merge such local
types according to their position within the containing function's
definition, analogous to how we merge FIELD_DECLs of a class according
to their index in the TYPE_FIELDS list.

	PR c++/99426

gcc/cp/ChangeLog:

	* module.cc (merge_kind::MK_local_type): New enumerator.
	(merge_kind_name): Update.
	(trees_out::chained_decls): Move BLOCK-specific handling
	of DECL_LOCAL_DECL_P decls to ...
	(trees_out::core_vals) <case BLOCK>: ... here.  Stream
	BLOCK_VARS manually.
	(trees_in::core_vals) <case BLOCK>: Stream BLOCK_VARS
	manually.  Handle deduplicated local types..
	(trees_out::key_local_type): Define.
	(trees_in::key_local_type): Define.
	(trees_out::get_merge_kind) <case FUNCTION_DECL>: Return
	MK_local_type for a local type.
	(trees_out::key_mergeable) <case FUNCTION_DECL>: Use
	key_local_type.
	(trees_in::key_mergeable) <case FUNCTION_DECL>: Likewise.
	(trees_in::is_matching_decl): Be flexible with type mismatches
	for local entities.
	(trees_in::register_duplicate): Also register the
	DECL_TEMPLATE_RESULT of a TEMPLATE_DECL as a duplicate.
	(depset_cmp): Return 0 for equal IDENTIFIER_HASH_VALUEs.

gcc/testsuite/ChangeLog:

	* g++.dg/modules/merge-17.h: New test.
	* g++.dg/modules/merge-17_a.H: New test.
	* g++.dg/modules/merge-17_b.C: New test.
	* g++.dg/modules/xtreme-header-7_a.H: New test.
	* g++.dg/modules/xtreme-header-7_b.C: New test.

Reviewed-by: Jason Merrill <jason@redhat.com>

6 files changed, 222 insertions, 31 deletions

diff --git a/gcc/cp/module.cc b/gcc/cp/module.cc
index ad1b6bf..9917a6a 100644
--- a/gcc/cp/module.cc
+++ b/gcc/cp/module.cc
@@ -2758,6 +2758,7 @@ enum merge_kind
 
   MK_enum,	/* Found by CTX, & 1stMemberNAME.  */
   MK_keyed,     /* Found by key & index.  */
+  MK_local_type, /* Found by CTX, index.  */
 
   MK_friend_spec,  /* Like named, but has a tmpl & args too.  */
   MK_local_friend, /* Found by CTX, index.  */
@@ -2784,7 +2785,7 @@ static char const *const merge_kind_name[MK_hwm] =
     "unique", "named", "field", "vtable",	/* 0...3  */
     "asbase", "partial", "enum", "attached",	/* 4...7  */
 
-    "friend spec", "local friend", NULL, NULL,  /* 8...11 */
+    "local type", "friend spec", "local friend", NULL,  /* 8...11 */
     NULL, NULL, NULL, NULL,
 
     "type spec", "type tmpl spec",	/* 16,17 type (template).  */
@@ -2913,6 +2914,7 @@ public:
   unsigned binfo_mergeable (tree *);
 
 private:
+  tree key_local_type (const merge_key&, tree, tree);
   uintptr_t *find_duplicate (tree existing);
   void register_duplicate (tree decl, tree existing);
   /* Mark as an already diagnosed bad duplicate.  */
@@ -3071,6 +3073,7 @@ public:
   void binfo_mergeable (tree binfo);
 
 private:
+  void key_local_type (merge_key&, tree, tree);
   bool decl_node (tree, walk_kind ref);
   void type_node (tree);
   void tree_value (tree);
@@ -4937,18 +4940,7 @@ void
 trees_out::chained_decls (tree decls)
 {
   for (; decls; decls = DECL_CHAIN (decls))
-    {
-      if (VAR_OR_FUNCTION_DECL_P (decls)
-	  && DECL_LOCAL_DECL_P (decls))
-	{
-	  /* Make sure this is the first encounter, and mark for
-	     walk-by-value.  */
-	  gcc_checking_assert (!TREE_VISITED (decls)
-			       && !DECL_TEMPLATE_INFO (decls));
-	  mark_by_value (decls);
-	}
-      tree_node (decls);
-    }
+    tree_node (decls);
   tree_node (NULL_TREE);
 }
 
@@ -6198,7 +6190,21 @@ trees_out::core_vals (tree t)
 
       /* DECL_LOCAL_DECL_P decls are first encountered here and
          streamed by value.  */
-      chained_decls (t->block.vars);
+      for (tree decls = t->block.vars; decls; decls = DECL_CHAIN (decls))
+	{
+	  if (VAR_OR_FUNCTION_DECL_P (decls)
+	      && DECL_LOCAL_DECL_P (decls))
+	    {
+	      /* Make sure this is the first encounter, and mark for
+		 walk-by-value.  */
+	      gcc_checking_assert (!TREE_VISITED (decls)
+				   && !DECL_TEMPLATE_INFO (decls));
+	      mark_by_value (decls);
+	    }
+	  tree_node (decls);
+	}
+      tree_node (NULL_TREE);
+
       /* nonlocalized_vars is a middle-end thing.  */
       WT (t->block.subblocks);
       WT (t->block.supercontext);
@@ -6712,7 +6718,29 @@ trees_in::core_vals (tree t)
     case BLOCK:
       t->block.locus = state->read_location (*this);
       t->block.end_locus = state->read_location (*this);
-      t->block.vars = chained_decls ();
+
+      for (tree *chain = &t->block.vars;;)
+	if (tree decl = tree_node ())
+	  {
+	    /* For a deduplicated local type or enumerator, chain the
+	       duplicate decl instead of the canonical in-TU decl.  Seeing
+	       a duplicate here means the containing function whose body
+	       we're streaming in is a duplicate too, so we'll end up
+	       discarding this BLOCK (and the rest of the duplicate function
+	       body) anyway.  */
+	    decl = maybe_duplicate (decl);
+
+	    if (!DECL_P (decl) || DECL_CHAIN (decl))
+	      {
+		set_overrun ();
+		break;
+	      }
+	    *chain = decl;
+	    chain = &DECL_CHAIN (decl);
+	  }
+	else
+	  break;
+
       /* nonlocalized_vars is middle-end.  */
       RT (t->block.subblocks);
       RT (t->block.supercontext);
@@ -10327,6 +10355,88 @@ trees_in::fn_parms_fini (int tag, tree fn, tree existing, bool is_defn)
     }
 }
 
+/* Encode into KEY the position of the local type (class or enum)
+   declaration DECL within FN.  The position is encoded as the
+   index of the innermost BLOCK (numbered in BFS order) along with
+   the index within its BLOCK_VARS list.  */
+
+void
+trees_out::key_local_type (merge_key& key, tree decl, tree fn)
+{
+  auto_vec<tree, 4> blocks;
+  blocks.quick_push (DECL_INITIAL (fn));
+  unsigned block_ix = 0;
+  while (block_ix != blocks.length ())
+    {
+      tree block = blocks[block_ix];
+      unsigned decl_ix = 0;
+      for (tree var = BLOCK_VARS (block); var; var = DECL_CHAIN (var))
+	{
+	  if (TREE_CODE (var) != TYPE_DECL)
+	    continue;
+	  if (var == decl)
+	    {
+	      key.index = (block_ix << 10) | decl_ix;
+	      return;
+	    }
+	  ++decl_ix;
+	}
+      for (tree sub = BLOCK_SUBBLOCKS (block); sub; sub = BLOCK_CHAIN (sub))
+	blocks.safe_push (sub);
+      ++block_ix;
+    }
+
+  /* Not-found value.  */
+  key.index = 1023;
+}
+
+/* Look up the local type corresponding at the position encoded by
+   KEY within FN and named NAME.  */
+
+tree
+trees_in::key_local_type (const merge_key& key, tree fn, tree name)
+{
+  if (!DECL_INITIAL (fn))
+    return NULL_TREE;
+
+  const unsigned block_pos = key.index >> 10;
+  const unsigned decl_pos = key.index & 1023;
+
+  if (decl_pos == 1023)
+    return NULL_TREE;
+
+  auto_vec<tree, 4> blocks;
+  blocks.quick_push (DECL_INITIAL (fn));
+  unsigned block_ix = 0;
+  while (block_ix != blocks.length ())
+    {
+      tree block = blocks[block_ix];
+      if (block_ix == block_pos)
+	{
+	  unsigned decl_ix = 0;
+	  for (tree var = BLOCK_VARS (block); var; var = DECL_CHAIN (var))
+	    {
+	      if (TREE_CODE (var) != TYPE_DECL)
+		continue;
+	      /* Prefer using the identifier as the key for more robustness
+		 to ODR violations, except for anonymous types since their
+		 compiler-generated identifiers aren't stable.  */
+	      if (IDENTIFIER_ANON_P (name)
+		  ? decl_ix == decl_pos
+		  : DECL_NAME (var) == name)
+		return var;
+	      ++decl_ix;
+	    }
+	  return NULL_TREE;
+	}
+      for (tree sub = BLOCK_SUBBLOCKS (block); sub; sub = BLOCK_CHAIN (sub))
+	blocks.safe_push (sub);
+      ++block_ix;
+    }
+
+  return NULL_TREE;
+}
+
 /* DEP is the depset of some decl we're streaming by value.  Determine
    the merging behaviour.  */
 
@@ -10446,17 +10556,10 @@ trees_out::get_merge_kind (tree decl, depset *dep)
 	    gcc_unreachable ();
 
 	  case FUNCTION_DECL:
-	    // FIXME: This can occur for (a) voldemorty TYPE_DECLS
-	    // (which are returned from a function), or (b)
-	    // block-scope class definitions in template functions.
-	    // These are as unique as the containing function.  While
-	    // on read-back we can discover if the CTX was a
-	    // duplicate, we don't have a mechanism to get from the
-	    // existing CTX to the existing version of this decl.
 	    gcc_checking_assert
 	      (DECL_IMPLICIT_TYPEDEF_P (STRIP_TEMPLATE (decl)));
 
-	    mk = MK_unique;
+	    mk = MK_local_type;
 	    break;
 
 	  case RECORD_TYPE:
@@ -10758,6 +10861,10 @@ trees_out::key_mergeable (int tag, merge_kind mk, tree decl, tree inner,
 	  }
 	  break;
 
+	case MK_local_type:
+	  key_local_type (key, STRIP_TEMPLATE (decl), container);
+	  break;
+
 	case MK_enum:
 	  {
 	    /* Anonymous enums are located by their first identifier,
@@ -11114,11 +11221,10 @@ trees_in::key_mergeable (int tag, merge_kind mk, tree decl, tree inner,
 	    break;
 
 	  case FUNCTION_DECL:
-	    // FIXME: What about a voldemort? how do we find what it
-	    // duplicates? Do we have to number vmorts relative to
-	    // their containing function?  But how would that work
-	    // when matching an in-TU declaration?
-	    kind = "unique";
+	    gcc_checking_assert (mk == MK_local_type);
+	    existing = key_local_type (key, container, name);
+	    if (existing && inner != decl)
+	      existing = TYPE_TI_TEMPLATE (TREE_TYPE (existing));
 	    break;
 
 	  case TYPE_DECL:
@@ -11371,6 +11477,11 @@ trees_in::is_matching_decl (tree existing, tree decl, bool is_typedef)
 	/* Just like duplicate_decls, presum the user knows what
 	   they're doing in overriding a builtin.   */
 	TREE_TYPE (existing) = TREE_TYPE (decl);
+      else if (decl_function_context (decl))
+	/* The type of a mergeable local entity (such as a function scope
+	   capturing lambda's closure type fields) can depend on an
+	   unmergeable local entity (such as a local variable), so type
+	   equality isn't feasible in general for local entities.  */;
       else
 	{
 	  // FIXME:QOI Might be template specialization from a module,
@@ -11620,6 +11731,13 @@ trees_in::register_duplicate (tree decl, tree existing)
   uintptr_t &slot = duplicates->get_or_insert (existing, &existed);
   gcc_checking_assert (!existed);
   slot = reinterpret_cast<uintptr_t> (decl);
+
+  if (TREE_CODE (decl) == TEMPLATE_DECL)
+    /* Also register the DECL_TEMPLATE_RESULT as a duplicate so
+       that passing decl's _RESULT to maybe_duplicate naturally
+       gives us existing's _RESULT back.  */
+    register_duplicate (DECL_TEMPLATE_RESULT (decl),
+			DECL_TEMPLATE_RESULT (existing));
 }
 
 /* We've read a definition of MAYBE_EXISTING.  If not a duplicate,
@@ -13643,9 +13761,9 @@ depset_cmp (const void *a_, const void *b_)
     {
       /* Both are bindings.  Order by identifier hash.  */
       gcc_checking_assert (a->get_name () != b->get_name ());
-      return (IDENTIFIER_HASH_VALUE (a->get_name ())
-	      < IDENTIFIER_HASH_VALUE (b->get_name ())
-	      ? -1 : +1);
+      hashval_t ah = IDENTIFIER_HASH_VALUE (a->get_name ());
+      hashval_t bh = IDENTIFIER_HASH_VALUE (b->get_name ());
+      return (ah == bh ? 0 : ah < bh ? -1 : +1);
     }
 
   /* They are the same decl.  This can happen with two using decls
diff --git a/gcc/testsuite/g++.dg/modules/merge-17.h b/gcc/testsuite/g++.dg/modules/merge-17.h
new file mode 100644
index 0000000..5ce52ce
--- /dev/null
+++ b/gcc/testsuite/g++.dg/modules/merge-17.h
@@ -0,0 +1,58 @@
+// PR c++/99426
+
+inline auto f() {
+  struct A { int m = 42; };
+  return A{};
+}
+
+template<class T>
+auto ft() {
+  decltype(+T()) x;
+  return [&x] { };
+}
+
+inline auto g() {
+  enum E { e };
+  return e;
+}
+
+template<class T>
+auto gt() {
+  enum E : T { e };
+  return e;
+}
+
+inline auto h0() {
+  struct { int m; } a0;
+  struct { char n; } a1;
+  return a0;
+}
+
+inline auto h1() {
+  struct { int m; } a0;
+  struct { char n; } a1;
+  return a1;
+}
+
+template<class T>
+inline auto h0t() {
+  struct { int m; } a0;
+  struct { char n; } a1;
+  return a0;
+}
+
+template<class T>
+inline auto h1t() {
+  struct { int m; } a0;
+  struct { char n; } a1;
+  return a1;
+}
+
+using ty1 = decltype(f());
+using ty2 = decltype(ft<int>());
+using ty3 = decltype(g());
+using ty4 = decltype(gt<int>());
+using ty5 = decltype(h0());
+using ty6 = decltype(h0t<int>());
+using ty7 = decltype(h1());
+using ty8 = decltype(h1t<int>());
diff --git a/gcc/testsuite/g++.dg/modules/merge-17_a.H b/gcc/testsuite/g++.dg/modules/merge-17_a.H
new file mode 100644
index 0000000..0440cd7
--- /dev/null
+++ b/gcc/testsuite/g++.dg/modules/merge-17_a.H
@@ -0,0 +1,3 @@
+// { dg-additional-options "-fmodule-header" }
+// { dg-module-cmi {} }
+#include "merge-17.h"
diff --git a/gcc/testsuite/g++.dg/modules/merge-17_b.C b/gcc/testsuite/g++.dg/modules/merge-17_b.C
new file mode 100644
index 0000000..4315b99
--- /dev/null
+++ b/gcc/testsuite/g++.dg/modules/merge-17_b.C
@@ -0,0 +1,3 @@
+// { dg-additional-options "-fmodules-ts -fno-module-lazy" }
+#include "merge-17.h"
+import "merge-17_a.H";
diff --git a/gcc/testsuite/g++.dg/modules/xtreme-header-7_a.H b/gcc/testsuite/g++.dg/modules/xtreme-header-7_a.H
new file mode 100644
index 0000000..bf7859f
--- /dev/null
+++ b/gcc/testsuite/g++.dg/modules/xtreme-header-7_a.H
@@ -0,0 +1,4 @@
+// { dg-additional-options -fmodule-header }
+
+// { dg-module-cmi {} }
+#include "xtreme-header.h"
diff --git a/gcc/testsuite/g++.dg/modules/xtreme-header-7_b.C b/gcc/testsuite/g++.dg/modules/xtreme-header-7_b.C
new file mode 100644
index 0000000..3992a24
--- /dev/null
+++ b/gcc/testsuite/g++.dg/modules/xtreme-header-7_b.C
@@ -0,0 +1,5 @@
+// A version of xtreme-header_b.C that doesn't use -fno-module-lazy.
+// { dg-additional-options -fmodules-ts }
+
+#include "xtreme-header.h"
+import "xtreme-header-7_a.H";