Go patch committed: Sort array constructors by index

[Ian Lance Taylor]

This patch to the Go frontend sorts array constructors by index.  That
is what the middle-end expects.  Bootstrapped and ran Go testsuite on
x86_64-unknown-linux-gnu.  Committed to mainline and 4.7 branch.

Ian


diff -r b4118d35075b go/expressions.cc
--- a/go/expressions.cc	Tue May 15 12:58:54 2012 -0700
+++ b/go/expressions.cc	Tue May 15 15:28:14 2012 -0700
@@ -11794,8 +11794,7 @@
       if (this->indexes() == NULL)
 	max_index = this->vals()->size() - 1;
       else
-	max_index = *std::max_element(this->indexes()->begin(),
-				      this->indexes()->end());
+	max_index = this->indexes()->back();
       tree max_tree = size_int(max_index);
       tree constructor_type = build_array_type(element_type_tree,
 					       build_index_type(max_tree));
@@ -12546,6 +12545,17 @@
   return ret;
 }
 
+// Used to sort an index/value array.
+
+class Index_value_compare
+{
+ public:
+  bool
+  operator()(const std::pair<unsigned long, Expression*>& a,
+	     const std::pair<unsigned long, Expression*>& b)
+  { return a.first < b.first; }
+};
+
 // Lower an array composite literal.
 
 Expression*
@@ -12557,6 +12567,7 @@
 
   std::vector<unsigned long>* indexes = new std::vector<unsigned long>;
   indexes->reserve(this->vals_->size());
+  bool indexes_out_of_order = false;
   Expression_list* vals = new Expression_list();
   vals->reserve(this->vals_->size());
   unsigned long index = 0;
@@ -12627,6 +12638,9 @@
 	      return Expression::make_error(location);
 	    }
 
+	  if (!indexes->empty() && index < indexes->back())
+	    indexes_out_of_order = true;
+
 	  indexes->push_back(index);
 	}
 
@@ -12641,6 +12655,34 @@
       indexes = NULL;
     }
 
+  if (indexes_out_of_order)
+    {
+      typedef std::vector<std::pair<unsigned long, Expression*> > V;
+
+      V v;
+      v.reserve(indexes->size());
+      std::vector<unsigned long>::const_iterator pi = indexes->begin();
+      for (Expression_list::const_iterator pe = vals->begin();
+	   pe != vals->end();
+	   ++pe, ++pi)
+	v.push_back(std::make_pair(*pi, *pe));
+
+      std::sort(v.begin(), v.end(), Index_value_compare());
+
+      delete indexes;
+      delete vals;
+      indexes = new std::vector<unsigned long>();
+      indexes->reserve(v.size());
+      vals = new Expression_list();
+      vals->reserve(v.size());
+
+      for (V::const_iterator p = v.begin(); p != v.end(); ++p)
+	{
+	  indexes->push_back(p->first);
+	  vals->push_back(p->second);
+	}
+    }
+
   return this->make_array(type, indexes, vals);
 }
 
@@ -12661,7 +12703,9 @@
       size_t size;
       if (vals == NULL)
 	size = 0;
-      else if (indexes == NULL)
+      else if (indexes != NULL)
+	size = indexes->back() + 1;
+      else
 	{
 	  size = vals->size();
 	  Integer_type* it = Type::lookup_integer_type("int")->integer_type();
@@ -12672,11 +12716,6 @@
 	      return Expression::make_error(location);
 	    }
 	}
-      else
-	{
-	  size = *std::max_element(indexes->begin(), indexes->end());
-	  ++size;
-	}
 
       mpz_t vlen;
       mpz_init_set_ui(vlen, size);
@@ -12704,8 +12743,7 @@
 	    }
 	  else
 	    {
-	      unsigned long max = *std::max_element(indexes->begin(),
-						    indexes->end());
+	      unsigned long max = indexes->back();
 	      if (max >= val)
 		{
 		  error_at(location,