THRIFT-236. Structs should be serialized in a consistent order

2nd try at this issue. This time, we will use numeric field order ONLY for the serialization portion, instead of globally. This should make it much easier to produce the correctly ordered output in all cases. 

git-svn-id: https://svn.apache.org/repos/asf/incubator/thrift/trunk@764072 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/compiler/cpp/src/generate/t_cpp_generator.cc b/compiler/cpp/src/generate/t_cpp_generator.cc
index 00c813e..67a4bd4 100644
--- a/compiler/cpp/src/generate/t_cpp_generator.cc
+++ b/compiler/cpp/src/generate/t_cpp_generator.cc
@@ -870,7 +870,7 @@
     // T_STOP type, so we use the global void type, and special case it when
     // generating its typespec.
 
-    const vector<t_field*>& members = ((t_struct*)ttype)->get_members();
+    const vector<t_field*>& members = ((t_struct*)ttype)->get_sorted_members();
     vector<t_field*>::const_iterator m_iter;
     for (m_iter = members.begin(); m_iter != members.end(); ++m_iter) {
       generate_local_reflection(out, (**m_iter).get_type(), is_definition);
@@ -1112,7 +1112,7 @@
                                              t_struct* tstruct,
                                              bool pointers) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
@@ -1174,7 +1174,7 @@
                                                     t_struct* tstruct,
                                                     bool pointers) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
diff --git a/compiler/cpp/src/generate/t_csharp_generator.cc b/compiler/cpp/src/generate/t_csharp_generator.cc
index e6eff76..5a910ea 100644
--- a/compiler/cpp/src/generate/t_csharp_generator.cc
+++ b/compiler/cpp/src/generate/t_csharp_generator.cc
@@ -565,7 +565,7 @@
   indent_up();
 
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
@@ -625,7 +625,7 @@
   indent_up();
 
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
diff --git a/compiler/cpp/src/generate/t_hs_generator.cc b/compiler/cpp/src/generate/t_hs_generator.cc
index ee17839..c8fda77 100644
--- a/compiler/cpp/src/generate/t_hs_generator.cc
+++ b/compiler/cpp/src/generate/t_hs_generator.cc
@@ -571,7 +571,7 @@
 void t_hs_generator::generate_hs_struct_writer(ofstream& out,
                                                t_struct* tstruct) {
   string name = type_name(tstruct);
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
   string str = tmp("_str");
   string f = tmp("_f");
diff --git a/compiler/cpp/src/generate/t_java_generator.cc b/compiler/cpp/src/generate/t_java_generator.cc
index f709528..3ec816f 100644
--- a/compiler/cpp/src/generate/t_java_generator.cc
+++ b/compiler/cpp/src/generate/t_java_generator.cc
@@ -1081,7 +1081,7 @@
   indent_up();
 
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   // performs various checks (e.g. check that all required fields are set)
@@ -1146,7 +1146,7 @@
   indent_up();
 
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) << "oprot.writeStructBegin(STRUCT_DESC);" << endl;
diff --git a/compiler/cpp/src/generate/t_ocaml_generator.cc b/compiler/cpp/src/generate/t_ocaml_generator.cc
index 68d2c35..0405a04 100644
--- a/compiler/cpp/src/generate/t_ocaml_generator.cc
+++ b/compiler/cpp/src/generate/t_ocaml_generator.cc
@@ -670,7 +670,7 @@
 void t_ocaml_generator::generate_ocaml_struct_writer(ofstream& out,
                                                t_struct* tstruct) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
   string str = tmp("_str");
   string f = tmp("_f");
diff --git a/compiler/cpp/src/generate/t_perl_generator.cc b/compiler/cpp/src/generate/t_perl_generator.cc
index 9fbb92f..ca3210a 100644
--- a/compiler/cpp/src/generate/t_perl_generator.cc
+++ b/compiler/cpp/src/generate/t_perl_generator.cc
@@ -630,7 +630,7 @@
 void t_perl_generator::generate_perl_struct_writer(ofstream& out,
                                                    t_struct* tstruct) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   out << "sub write {" << endl;
diff --git a/compiler/cpp/src/generate/t_php_generator.cc b/compiler/cpp/src/generate/t_php_generator.cc
index fcd00b4..436a632 100644
--- a/compiler/cpp/src/generate/t_php_generator.cc
+++ b/compiler/cpp/src/generate/t_php_generator.cc
@@ -811,7 +811,7 @@
 void t_php_generator::generate_php_struct_writer(ofstream& out,
                                                  t_struct* tstruct) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   if (binary_inline_) {
diff --git a/compiler/cpp/src/generate/t_py_generator.cc b/compiler/cpp/src/generate/t_py_generator.cc
index d63fec7..5db7f8b 100644
--- a/compiler/cpp/src/generate/t_py_generator.cc
+++ b/compiler/cpp/src/generate/t_py_generator.cc
@@ -521,19 +521,6 @@
 }
 
 /**
- * Comparator to sort fields in ascending order by key.
- * Make this a functor instead of a function to help GCC inline it.
- * The arguments are (const) references to const pointers to const t_fields.
- * Unfortunately, we cannot declare it within the function.  Boo!
- * http://www.open-std.org/jtc1/sc22/open/n2356/ (paragraph 9).
- */
-struct FieldKeyCompare {
-  bool operator()(t_field const * const & a, t_field const * const & b) {
-    return a->get_key() < b->get_key();
-  }
-};
-
-/**
  * Generates a struct definition for a thrift data type.
  *
  * @param tstruct The struct definition
@@ -545,8 +532,6 @@
 
   const vector<t_field*>& members = tstruct->get_members();
   vector<t_field*>::const_iterator m_iter;
-  vector<t_field*> sorted_members(members);
-  std::sort(sorted_members.begin(), sorted_members.end(), FieldKeyCompare());
 
   out <<
     "class " << tstruct->get_name();
@@ -586,12 +571,12 @@
   // for structures with no members.
   // TODO(dreiss): Test encoding of structs where some inner structs
   // don't have thrift_spec.
-  if (sorted_members.empty() || (sorted_members[0]->get_key() >= 0)) {
+  if (members.empty() || (members[0]->get_key() >= 0)) {
     indent(out) << "thrift_spec = (" << endl;
     indent_up();
 
     int sorted_keys_pos = 0;
-    for (m_iter = sorted_members.begin(); m_iter != sorted_members.end(); ++m_iter) {
+    for (m_iter = members.begin(); m_iter != members.end(); ++m_iter) {
 
       for (; sorted_keys_pos != (*m_iter)->get_key(); sorted_keys_pos++) {
         indent(out) << "None, # " << sorted_keys_pos << endl;
@@ -772,7 +757,7 @@
 void t_py_generator::generate_py_struct_writer(ofstream& out,
                                                t_struct* tstruct) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
diff --git a/compiler/cpp/src/generate/t_st_generator.cc b/compiler/cpp/src/generate/t_st_generator.cc
index db01165..3600a3b 100644
--- a/compiler/cpp/src/generate/t_st_generator.cc
+++ b/compiler/cpp/src/generate/t_st_generator.cc
@@ -693,7 +693,7 @@
 
 string t_st_generator::struct_writer(t_struct *tstruct, string sname) {
   std::ostringstream out;
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator fld_iter;
 
   out << "[oprot writeStructBegin: " <<
diff --git a/compiler/cpp/src/parse/t_field.h b/compiler/cpp/src/parse/t_field.h
index 51cfcb0..67a2125 100644
--- a/compiler/cpp/src/parse/t_field.h
+++ b/compiler/cpp/src/parse/t_field.h
@@ -122,6 +122,18 @@
       type_->get_fingerprint_material();
   }
 
+  /**
+   * Comparator to sort fields in ascending order by key.
+   * Make this a functor instead of a function to help GCC inline it.
+   * The arguments are (const) references to const pointers to const t_fields.
+   */
+  struct key_compare {
+    bool operator()(t_field const * const & a, t_field const * const & b) {
+      return a->get_key() < b->get_key();
+    }
+  };
+
+
  private:
   t_type* type_;
   std::string name_;
diff --git a/compiler/cpp/src/parse/t_struct.h b/compiler/cpp/src/parse/t_struct.h
index a18b131..7980f80 100644
--- a/compiler/cpp/src/parse/t_struct.h
+++ b/compiler/cpp/src/parse/t_struct.h
@@ -20,7 +20,9 @@
 #ifndef T_STRUCT_H
 #define T_STRUCT_H
 
+#include <algorithm>
 #include <vector>
+#include <utility>
 #include <string>
 
 #include "t_type.h"
@@ -36,6 +38,8 @@
  */
 class t_struct : public t_type {
  public:
+  typedef std::vector<t_field*> members_type;
+
   t_struct(t_program* program) :
     t_type(program),
     is_xception_(false),
@@ -62,14 +66,28 @@
     return xsd_all_;
   }
 
-  void append(t_field* elem) {
+  bool append(t_field* elem) {
     members_.push_back(elem);
+
+    typedef members_type::iterator iter_type;
+    std::pair<iter_type, iter_type> bounds = std::equal_range(
+            members_in_id_order_.begin(), members_in_id_order_.end(), elem, t_field::key_compare()
+        );
+    if (bounds.first != bounds.second) {
+      return false;
+    }
+    members_in_id_order_.insert(bounds.second, elem);
+    return true;
   }
 
-  const std::vector<t_field*>& get_members() {
+  const members_type& get_members() {
     return members_;
   }
 
+  const members_type& get_sorted_members() {
+    return members_in_id_order_;
+  }
+
   bool is_struct() const {
     return !is_xception_;
   }
@@ -80,8 +98,8 @@
 
   virtual std::string get_fingerprint_material() const {
     std::string rv = "{";
-    std::vector<t_field*>::const_iterator m_iter;
-    for (m_iter = members_.begin(); m_iter != members_.end(); ++m_iter) {
+    members_type::const_iterator m_iter;
+    for (m_iter = members_in_id_order_.begin(); m_iter != members_in_id_order_.end(); ++m_iter) {
       rv += (*m_iter)->get_fingerprint_material();
       rv += ";";
     }
@@ -91,26 +109,16 @@
 
   virtual void generate_fingerprint() {
     t_type::generate_fingerprint();
-    std::vector<t_field*>::const_iterator m_iter;
-    for (m_iter = members_.begin(); m_iter != members_.end(); ++m_iter) {
+    members_type::const_iterator m_iter;
+    for (m_iter = members_in_id_order_.begin(); m_iter != members_in_id_order_.end(); ++m_iter) {
       (*m_iter)->get_type()->generate_fingerprint();
     }
   }
 
-  bool validate_field(t_field* field) {
-    int key = field->get_key();
-    std::vector<t_field*>::const_iterator m_iter;
-    for (m_iter = members_.begin(); m_iter != members_.end(); ++m_iter) {
-      if ((*m_iter)->get_key() == key) {
-        return false;
-      }
-    }
-    return true;
-  }
-
  private:
 
-  std::vector<t_field*> members_;
+  members_type members_;
+  members_type members_in_id_order_;
   bool is_xception_;
 
   bool xsd_all_;
diff --git a/compiler/cpp/src/thrifty.yy b/compiler/cpp/src/thrifty.yy
index 2c16ca0..bf5408e 100644
--- a/compiler/cpp/src/thrifty.yy
+++ b/compiler/cpp/src/thrifty.yy
@@ -830,11 +830,10 @@
     {
       pdebug("FieldList -> FieldList , Field");
       $$ = $1;
-      if (!($$->validate_field($2))) {
+      if (!($$->append($2))) {
         yyerror("Field identifier %d for \"%s\" has already been used", $2->get_key(), $2->get_name().c_str());
         exit(1);
       }
-      $$->append($2);
     }
 |
     {
diff --git a/test/DebugProtoTest.thrift b/test/DebugProtoTest.thrift
index 12c4613..d3d2580 100644
--- a/test/DebugProtoTest.thrift
+++ b/test/DebugProtoTest.thrift
@@ -240,3 +240,14 @@
   4: map<list<i32>,set<map<i32,string>>> b4;
 }
 
+
+struct ReverseOrderStruct {
+  4: string first;
+  3: i16 second;
+  2: i32 third;
+  1: i64 fourth;
+}
+
+service ReverseOrderService {
+  void myMethod(4: string first, 3: i16 second, 2: i32 third, 1: i64 fourth);
+}
\ No newline at end of file