C++ PATCH for c++/69261 (ICE with constexpr and arrays)

[Jason Merrill <jason at redhat dot com>]

In my fix for 67104 I knew that I wasn't handling RANGE_EXPRs, but 
thought that it wasn't necessary, and left an assert to make sure. 
Apparently I was wrong, so this patch implements the necessary range 
splitting when the constexpr code wants to store to a single element of 
a range.

Tested x86_64-pc-linux-gnu, applying to trunk.

commit b2e94d038fb4e0070761642dc36f605385a6307d
Author: Jason Merrill <jason@redhat.com>
Date:   Wed Jan 13 16:26:57 2016 -0500

    	PR c++/69261
    	* constexpr.c (find_array_ctor_elt): Handle splitting RANGE_EXPR.

diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 36a1e42..6ab4696 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -1725,14 +1725,57 @@ find_array_ctor_elt (tree ary, tree dindex, bool insert = false)
   while (begin != end)
     {
       unsigned HOST_WIDE_INT middle = (begin + end) / 2;
+      constructor_elt &elt = (*elts)[middle];
+      tree idx = elt.index;
 
-      int cmp = array_index_cmp (dindex, (*elts)[middle].index);
+      int cmp = array_index_cmp (dindex, idx);
       if (cmp < 0)
 	end = middle;
       else if (cmp > 0)
 	begin = middle + 1;
       else
-	return middle;
+	{
+	  if (insert && TREE_CODE (idx) == RANGE_EXPR)
+	    {
+	      /* We need to split the range.  */
+	      constructor_elt e;
+	      tree lo = TREE_OPERAND (idx, 0);
+	      tree hi = TREE_OPERAND (idx, 1);
+	      if (tree_int_cst_lt (lo, dindex))
+		{
+		  /* There are still some lower elts; shorten the range.  */
+		  tree new_hi = int_const_binop (MINUS_EXPR, dindex,
+						 size_one_node);
+		  if (tree_int_cst_equal (lo, new_hi))
+		    /* Only one element left, no longer a range.  */
+		    elt.index = lo;
+		  else
+		    TREE_OPERAND (idx, 1) = new_hi;
+		  /* Append the element we want to insert.  */
+		  ++middle;
+		  e.index = dindex;
+		  e.value = unshare_expr (elt.value);
+		  vec_safe_insert (CONSTRUCTOR_ELTS (ary), middle, e);
+		}
+	      else
+		/* No lower elts, the range elt is now ours.  */
+		elt.index = dindex;
+
+	      if (tree_int_cst_lt (dindex, hi))
+		{
+		  /* There are still some higher elts; append a range.  */
+		  tree new_lo = int_const_binop (PLUS_EXPR, dindex,
+						 size_one_node);
+		  if (tree_int_cst_equal (new_lo, hi))
+		    e.index = hi;
+		  else
+		    e.index = build2 (RANGE_EXPR, sizetype, new_lo, hi);
+		  e.value = unshare_expr (elt.value);
+		  vec_safe_insert (CONSTRUCTOR_ELTS (ary), middle+1, e);
+		}
+	    }
+	  return middle;
+	}
     }
 
   if (insert)
diff --git a/gcc/testsuite/g++.dg/cpp1y/constexpr-array2.C b/gcc/testsuite/g++.dg/cpp1y/constexpr-array2.C
new file mode 100644
index 0000000..71b3642
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1y/constexpr-array2.C
@@ -0,0 +1,63 @@
+// PR c++/69261
+// { dg-do run { target c++14 } }
+
+typedef __SIZE_TYPE__ size_t;
+
+template <size_t N>
+struct S
+{
+  constexpr S() = default;
+
+  template<size_t M>
+  constexpr S (char const (&d)[M]) : data { 0 }
+  {
+    static_assert (M <= N, "size!");
+    for (size_t i = 0; i != M; i++)
+      data[i] = d[i];
+  }
+  char data[N];
+};
+
+template <int N>
+constexpr S<N>
+s (char const (&d)[N])
+{
+  S<N> c {};
+  for (size_t i = 0; i != N; i++)
+    c.data[i] = d[i];
+  return c;
+}
+
+template <size_t N, size_t M>
+constexpr auto
+concat (S<N> const& s1, S<M> const& s2)
+{
+  S<N+M-1> s (s1.data);
+  for (size_t i = 0; i != M; i++)
+    s.data[N + i - 1] = s2.data[i];
+  return s;
+}
+
+template <size_t N, size_t M>
+constexpr auto
+concat (char const (&x)[N], char const (&y)[M])
+{
+  S<N+M-1> tmp { x };
+  for (size_t i = 0; i != M; i++)
+    tmp.data[N+i-1] = y[i];
+  return tmp;
+}
+
+int
+main ()
+{
+  auto constexpr s1 = s ("bla");
+  auto constexpr s2 = s ("blub");
+  S<8> constexpr s1s2 = concat (s1, s2);
+  auto constexpr c = concat ("bla", "blub");
+  if (__builtin_strcmp (s1.data, "bla")
+      || __builtin_strcmp (s2.data, "blub")
+      || __builtin_strcmp (s1s2.data, "blablub")
+      || __builtin_strcmp (c.data, "blablub"))
+    __builtin_abort ();
+}