c++: Fix constexpr evaluation of self-modifying CONSTRUCTORs [PR94219]

This PR reveals that cxx_eval_bare_aggregate and cxx_eval_store_expression do
not anticipate that a constructor element's initializer could mutate the
underlying CONSTRUCTOR.  Evaluation of the initializer could add new elements to
the underlying CONSTRUCTOR, thereby potentially invalidating any pointers to
or assumptions about the CONSTRUCTOR's elements, and so these routines should be
prepared for that.

To fix this problem, this patch makes cxx_eval_bare_aggregate and
cxx_eval_store_expression recompute the constructor_elt pointers through which
we're assigning, after it evaluates the initializer.  Care is taken to to not
slow down the common case where the initializer does not modify the underlying
CONSTRUCTOR.

gcc/cp/ChangeLog:

	PR c++/94219
	PR c++/94205
	* constexpr.c (get_or_insert_ctor_field): Split out (while adding
	support for VECTOR_TYPEs, and optimizations for the common case)
	from ...
	(cxx_eval_store_expression): ... here.  Rename local variable
	'changed_active_union_member_p' to 'activated_union_member_p'.  Record
	the sequence of indexes into 'indexes' that yields the subobject we're
	assigning to.  Record the integer offsets of the constructor indexes
	we're assigning through into 'index_pos_hints'.  After evaluating the
	initializer of the store expression, recompute 'valp' using 'indexes'
	and using 'index_pos_hints' as hints.
	(cxx_eval_bare_aggregate): Tweak comments.  Use get_or_insert_ctor_field
	to recompute the constructor_elt pointer we're assigning through after
	evaluating each initializer.

gcc/testsuite/ChangeLog:

	PR c++/94219
	PR c++/94205
	* g++.dg/cpp1y/constexpr-nsdmi3.C: New test.
	* g++.dg/cpp1y/constexpr-nsdmi4.C: New test.
	* g++.dg/cpp1y/constexpr-nsdmi5.C: New test.
	* g++.dg/cpp1z/lambda-this5.C: New test.

7 files changed, 253 insertions, 97 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 860d5d3..011da37 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,21 @@
+2020-04-04  Patrick Palka  <ppalka@redhat.com>
+
+	PR c++/94219
+	PR c++/94205
+	* constexpr.c (get_or_insert_ctor_field): Split out (while adding
+	support for VECTOR_TYPEs, and optimizations for the common case)
+	from ...
+	(cxx_eval_store_expression): ... here.  Rename local variable
+	'changed_active_union_member_p' to 'activated_union_member_p'.  Record
+	the sequence of indexes into 'indexes' that yields the subobject we're
+	assigning to.  Record the integer offsets of the constructor indexes
+	we're assigning through into 'index_pos_hints'.  After evaluating the
+	initializer of the store expression, recompute 'valp' using 'indexes'
+	and using 'index_pos_hints' as hints.
+	(cxx_eval_bare_aggregate): Tweak comments.  Use get_or_insert_ctor_field
+	to recompute the constructor_elt pointer we're assigning through after
+	evaluating each initializer.
+
 2020-04-04  Jason Merrill  <jason@redhat.com>
 
 	PR c++/67825
diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 8c693ea8..8fa1f53 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -3151,6 +3151,95 @@ find_array_ctor_elt (tree ary, tree dindex, bool insert)
   return -1;
 }
 
+/* Return a pointer to the constructor_elt of CTOR which matches INDEX.  If no
+   matching constructor_elt exists, then add one to CTOR.
+
+   As an optimization, if POS_HINT is non-negative then it is used as a guess
+   for the (integer) index of the matching constructor_elt within CTOR.  */
+
+static constructor_elt *
+get_or_insert_ctor_field (tree ctor, tree index, int pos_hint)
+{
+  /* Check the hint first.  */
+  if (pos_hint >= 0 && (unsigned)pos_hint < CONSTRUCTOR_NELTS (ctor)
+      && CONSTRUCTOR_ELT (ctor, pos_hint)->index == index)
+    return CONSTRUCTOR_ELT (ctor, pos_hint);
+
+  tree type = TREE_TYPE (ctor);
+  if (TREE_CODE (type) == VECTOR_TYPE && index == NULL_TREE)
+    {
+      CONSTRUCTOR_APPEND_ELT (CONSTRUCTOR_ELTS (ctor), index, NULL_TREE);
+      return &CONSTRUCTOR_ELTS (ctor)->last();
+    }
+  else if (TREE_CODE (type) == ARRAY_TYPE || TREE_CODE (type) == VECTOR_TYPE)
+    {
+      HOST_WIDE_INT i = find_array_ctor_elt (ctor, index, /*insert*/true);
+      gcc_assert (i >= 0);
+      constructor_elt *cep = CONSTRUCTOR_ELT (ctor, i);
+      gcc_assert (cep->index == NULL_TREE
+		  || TREE_CODE (cep->index) != RANGE_EXPR);
+      return cep;
+    }
+  else
+    {
+      gcc_assert (TREE_CODE (index) == FIELD_DECL);
+
+      /* We must keep the CONSTRUCTOR's ELTS in FIELD order.
+	 Usually we meet initializers in that order, but it is
+	 possible for base types to be placed not in program
+	 order.  */
+      tree fields = TYPE_FIELDS (DECL_CONTEXT (index));
+      unsigned HOST_WIDE_INT idx = 0;
+      constructor_elt *cep = NULL;
+
+      /* Check if we're changing the active member of a union.  */
+      if (TREE_CODE (type) == UNION_TYPE && CONSTRUCTOR_NELTS (ctor)
+	  && CONSTRUCTOR_ELT (ctor, 0)->index != index)
+	vec_safe_truncate (CONSTRUCTOR_ELTS (ctor), 0);
+      /* If the bit offset of INDEX is larger than that of the last
+	 constructor_elt, then we can just immediately append a new
+	 constructor_elt to the end of CTOR.  */
+      else if (CONSTRUCTOR_NELTS (ctor)
+	       && tree_int_cst_compare (bit_position (index),
+					bit_position (CONSTRUCTOR_ELTS (ctor)
+						      ->last().index)) > 0)
+	{
+	  idx = CONSTRUCTOR_NELTS (ctor);
+	  goto insert;
+	}
+
+      /* Otherwise, we need to iterate over CTOR to find or insert INDEX
+	 appropriately.  */
+
+      for (; vec_safe_iterate (CONSTRUCTOR_ELTS (ctor), idx, &cep);
+	   idx++, fields = DECL_CHAIN (fields))
+	{
+	  if (index == cep->index)
+	    goto found;
+
+	  /* The field we're initializing must be on the field
+	     list.  Look to see if it is present before the
+	     field the current ELT initializes.  */
+	  for (; fields != cep->index; fields = DECL_CHAIN (fields))
+	    if (index == fields)
+	      goto insert;
+	}
+      /* We fell off the end of the CONSTRUCTOR, so insert a new
+	 entry at the end.  */
+
+    insert:
+      {
+	constructor_elt ce = { index, NULL_TREE };
+
+	vec_safe_insert (CONSTRUCTOR_ELTS (ctor), idx, ce);
+	cep = CONSTRUCTOR_ELT (ctor, idx);
+      }
+    found:;
+
+      return cep;
+    }
+}
+
 /* Under the control of CTX, issue a detailed diagnostic for
    an out-of-bounds subscript INDEX into the expression ARRAY.  */
 
@@ -3760,14 +3849,18 @@ cxx_eval_bare_aggregate (const constexpr_ctx *ctx, tree t,
     {
       tree orig_value = value;
       init_subob_ctx (ctx, new_ctx, index, value);
+      int pos_hint = -1;
       if (new_ctx.ctor != ctx->ctor)
-	/* If we built a new CONSTRUCTOR, attach it now so that other
-	   initializers can refer to it.  */
-	CONSTRUCTOR_APPEND_ELT (*p, index, new_ctx.ctor);
+	{
+	  /* If we built a new CONSTRUCTOR, attach it now so that other
+	     initializers can refer to it.  */
+	  CONSTRUCTOR_APPEND_ELT (*p, index, new_ctx.ctor);
+	  pos_hint = vec_safe_length (*p) - 1;
+	}
       else if (TREE_CODE (type) == UNION_TYPE)
-	/* Otherwise if we're constructing a union, set the active union member
-	   anyway so that we can later detect if the initializer attempts to
-	   activate another member.  */
+	/* Otherwise if we're constructing a non-aggregate union member, set
+	   the active union member now so that we can later detect and diagnose
+	   if its initializer attempts to activate another member.  */
 	CONSTRUCTOR_APPEND_ELT (*p, index, NULL_TREE);
       tree elt = cxx_eval_constant_expression (&new_ctx, value,
 					       lval,
@@ -3804,18 +3897,18 @@ cxx_eval_bare_aggregate (const constexpr_ctx *ctx, tree t,
 	{
 	  if (TREE_CODE (type) == UNION_TYPE
 	      && (*p)->last().index != index)
-	    /* The initializer may have erroneously changed the active union
-	       member that we're initializing.  */
+	    /* The initializer erroneously changed the active union member that
+	       we're initializing.  */
 	    gcc_assert (*non_constant_p);
-	  else if (new_ctx.ctor != ctx->ctor
-		   || TREE_CODE (type) == UNION_TYPE)
+	  else
 	    {
-	      /* We appended this element above; update the value.  */
-	      gcc_assert ((*p)->last().index == index);
-	      (*p)->last().value = elt;
+	      /* The initializer might have mutated the underlying CONSTRUCTOR,
+		 so recompute the location of the target constructer_elt.  */
+	      constructor_elt *cep
+		= get_or_insert_ctor_field (ctx->ctor, index, pos_hint);
+	      cep->value = elt;
 	    }
-	  else
-	    CONSTRUCTOR_APPEND_ELT (*p, index, elt);
+
 	  /* Adding or replacing an element might change the ctor's flags.  */
 	  TREE_CONSTANT (ctx->ctor) = constant_p;
 	  TREE_SIDE_EFFECTS (ctx->ctor) = side_effects_p;
@@ -4590,8 +4683,9 @@ cxx_eval_store_expression (const constexpr_ctx *ctx, tree t,
   type = TREE_TYPE (object);
   bool no_zero_init = true;
 
-  releasing_vec ctors;
-  bool changed_active_union_member_p = false;
+  releasing_vec ctors, indexes;
+  auto_vec<int> index_pos_hints;
+  bool activated_union_member_p = false;
   while (!refs->is_empty ())
     {
       if (*valp == NULL_TREE)
@@ -4632,94 +4726,49 @@ cxx_eval_store_expression (const constexpr_ctx *ctx, tree t,
 	 subobjects will also be zero-initialized.  */
       no_zero_init = CONSTRUCTOR_NO_CLEARING (*valp);
 
-      vec_safe_push (ctors, *valp);
-
       enum tree_code code = TREE_CODE (type);
       type = refs->pop();
       tree index = refs->pop();
 
-      constructor_elt *cep = NULL;
-      if (code == ARRAY_TYPE)
+      if (code == UNION_TYPE && CONSTRUCTOR_NELTS (*valp)
+	  && CONSTRUCTOR_ELT (*valp, 0)->index != index)
 	{
-	  HOST_WIDE_INT i
-	    = find_array_ctor_elt (*valp, index, /*insert*/true);
-	  gcc_assert (i >= 0);
-	  cep = CONSTRUCTOR_ELT (*valp, i);
-	  gcc_assert (cep->index == NULL_TREE
-		      || TREE_CODE (cep->index) != RANGE_EXPR);
-	}
-      else
-	{
-	  gcc_assert (TREE_CODE (index) == FIELD_DECL);
-
-	  /* We must keep the CONSTRUCTOR's ELTS in FIELD order.
-	     Usually we meet initializers in that order, but it is
-	     possible for base types to be placed not in program
-	     order.  */
-	  tree fields = TYPE_FIELDS (DECL_CONTEXT (index));
-	  unsigned HOST_WIDE_INT idx;
-
-	  if (code == UNION_TYPE && CONSTRUCTOR_NELTS (*valp)
-	      && CONSTRUCTOR_ELT (*valp, 0)->index != index)
+	  if (cxx_dialect < cxx2a)
 	    {
-	      if (cxx_dialect < cxx2a)
-		{
-		  if (!ctx->quiet)
-		    error_at (cp_expr_loc_or_input_loc (t),
-			      "change of the active member of a union "
-			      "from %qD to %qD",
-			      CONSTRUCTOR_ELT (*valp, 0)->index,
-			      index);
-		  *non_constant_p = true;
-		}
-	      else if (TREE_CODE (t) == MODIFY_EXPR
-		       && CONSTRUCTOR_NO_CLEARING (*valp))
-		{
-		  /* Diagnose changing the active union member while the union
-		     is in the process of being initialized.  */
-		  if (!ctx->quiet)
-		    error_at (cp_expr_loc_or_input_loc (t),
-			      "change of the active member of a union "
-			      "from %qD to %qD during initialization",
-			      CONSTRUCTOR_ELT (*valp, 0)->index,
-			      index);
-		  *non_constant_p = true;
-		}
-	      /* Changing active member.  */
-	      vec_safe_truncate (CONSTRUCTOR_ELTS (*valp), 0);
-	      no_zero_init = true;
+	      if (!ctx->quiet)
+		error_at (cp_expr_loc_or_input_loc (t),
+			  "change of the active member of a union "
+			  "from %qD to %qD",
+			  CONSTRUCTOR_ELT (*valp, 0)->index,
+			  index);
+	      *non_constant_p = true;
 	    }
-
-	  for (idx = 0;
-	       vec_safe_iterate (CONSTRUCTOR_ELTS (*valp), idx, &cep);
-	       idx++, fields = DECL_CHAIN (fields))
+	  else if (TREE_CODE (t) == MODIFY_EXPR
+		   && CONSTRUCTOR_NO_CLEARING (*valp))
 	    {
-	      if (index == cep->index)
-		goto found;
-
-	      /* The field we're initializing must be on the field
-		 list.  Look to see if it is present before the
-		 field the current ELT initializes.  */
-	      for (; fields != cep->index; fields = DECL_CHAIN (fields))
-		if (index == fields)
-		  goto insert;
+	      /* Diagnose changing the active union member while the union
+		 is in the process of being initialized.  */
+	      if (!ctx->quiet)
+		error_at (cp_expr_loc_or_input_loc (t),
+			  "change of the active member of a union "
+			  "from %qD to %qD during initialization",
+			  CONSTRUCTOR_ELT (*valp, 0)->index,
+			  index);
+	      *non_constant_p = true;
 	    }
+	  no_zero_init = true;
+	}
 
-	  /* We fell off the end of the CONSTRUCTOR, so insert a new
-	     entry at the end.  */
-	insert:
-	  {
-	    constructor_elt ce = { index, NULL_TREE };
+      vec_safe_push (ctors, *valp);
+      vec_safe_push (indexes, index);
 
-	    vec_safe_insert (CONSTRUCTOR_ELTS (*valp), idx, ce);
-	    cep = CONSTRUCTOR_ELT (*valp, idx);
+      constructor_elt *cep
+	= get_or_insert_ctor_field (*valp, index, /*pos_hint=*/-1);
+      index_pos_hints.safe_push (cep - CONSTRUCTOR_ELTS (*valp)->begin());
+
+      if (code == UNION_TYPE)
+	activated_union_member_p = true;
 
-	    if (code == UNION_TYPE)
-	      /* Record that we've changed an active union member.  */
-	      changed_active_union_member_p = true;
-	  }
-	found:;
-	}
       valp = &cep->value;
     }
 
@@ -4800,9 +4849,16 @@ cxx_eval_store_expression (const constexpr_ctx *ctx, tree t,
 	  init = tinit;
       init = cxx_eval_constant_expression (&new_ctx, init, false,
 					   non_constant_p, overflow_p);
-      if (ctors->is_empty())
-	/* The hash table might have moved since the get earlier.  */
-	valp = ctx->global->values.get (object);
+      /* The hash table might have moved since the get earlier, and the
+	 initializer might have mutated the underlying CONSTRUCTORs, so we must
+	 recompute VALP. */
+      valp = ctx->global->values.get (object);
+      for (unsigned i = 0; i < vec_safe_length (indexes); i++)
+	{
+	  constructor_elt *cep
+	    = get_or_insert_ctor_field (*valp, indexes[i], index_pos_hints[i]);
+	  valp = &cep->value;
+	}
     }
 
   /* Don't share a CONSTRUCTOR that might be changed later.  */
@@ -4847,7 +4903,7 @@ cxx_eval_store_expression (const constexpr_ctx *ctx, tree t,
   unsigned i;
   bool c = TREE_CONSTANT (init);
   bool s = TREE_SIDE_EFFECTS (init);
-  if (!c || s || changed_active_union_member_p)
+  if (!c || s || activated_union_member_p)
     FOR_EACH_VEC_ELT (*ctors, i, elt)
       {
 	if (!c)
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 36eb4ba..dedde9f 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,12 @@
+2020-04-04  Patrick Palka  <ppalka@redhat.com>
+
+	PR c++/94219
+	PR c++/94205
+	* g++.dg/cpp1y/constexpr-nsdmi3.C: New test.
+	* g++.dg/cpp1y/constexpr-nsdmi4.C: New test.
+	* g++.dg/cpp1y/constexpr-nsdmi5.C: New test.
+	* g++.dg/cpp1z/lambda-this5.C: New test.
+
 2020-04-04  Jan Hubicka  <hubicka@ucw.cz>
 
 	PR ipa/93940
diff --git a/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi3.C b/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi3.C
new file mode 100644
index 0000000..0f91e93
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi3.C
@@ -0,0 +1,19 @@
+// PR c++/94205
+// { dg-do compile { target c++14 } }
+
+struct S
+{
+  struct A
+  {
+    S *p;
+    constexpr A(S* p): p(p) {}
+    constexpr operator int() { p->a = 5; return 6; }
+  };
+  int a = A(this);
+};
+
+
+constexpr S s = {};
+
+#define SA(X) static_assert((X),#X)
+SA(s.a == 6);
diff --git a/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi4.C b/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi4.C
new file mode 100644
index 0000000..0ceef1b
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi4.C
@@ -0,0 +1,21 @@
+// PR c++/94219
+// { dg-do compile { target c++14 } }
+
+struct A { long x; };
+
+struct U;
+constexpr A foo(U *up);
+
+struct U {
+  A a = foo(this); int y;
+};
+
+constexpr A foo(U *up) {
+  up->y = 11;
+  return {42};
+}
+
+extern constexpr U u = {};
+
+static_assert(u.y == 11, "");
+static_assert(u.a.x == 42, "");
diff --git a/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi5.C b/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi5.C
new file mode 100644
index 0000000..59e7a10
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1y/constexpr-nsdmi5.C
@@ -0,0 +1,22 @@
+// PR c++/94219
+// { dg-do compile { target c++14 } }
+
+struct A { long x; };
+
+struct U;
+constexpr A foo(U *up);
+
+struct U {
+  U() = default;
+  int y; A a = foo(this);
+};
+
+constexpr A foo(U *up) {
+  up->y = 11;
+  return {42};
+}
+
+extern constexpr U u = {};
+
+static_assert(u.y == 11, "");
+static_assert(u.a.x == 42, "");
diff --git a/gcc/testsuite/g++.dg/cpp1z/lambda-this5.C b/gcc/testsuite/g++.dg/cpp1z/lambda-this5.C
new file mode 100644
index 0000000..c6d44d7
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1z/lambda-this5.C
@@ -0,0 +1,11 @@
+// PR c++/94205
+// { dg-do compile { target c++17 } }
+
+struct S
+{
+  int a = [this] { this->a = 5; return 6; } ();
+};
+
+constexpr S s = {};
+
+static_assert(s.a == 6);