add C# deterministic serialization (#13160)

https://github.com/protocolbuffers/protobuf/issues/12881

@jskeet  review please :-) as this is my first contrib to protobuf, any design / performance feedback is very sought after

Closes #13160

COPYBARA_INTEGRATE_REVIEW=https://github.com/protocolbuffers/protobuf/pull/13160 from fmg-lydonchandra:feature/12881_cs_serialization_deterministic ab7e01b8049ec98b78eb9fb6e04e8fe30ecd9a33
PiperOrigin-RevId: 568448399

csharp/src/Google.Protobuf/Collections/MapField.cs

diff --git a/csharp/src/Google.Protobuf/Collections/MapField.cs b/csharp/src/Google.Protobuf/Collections/MapField.cs
index f0be958..722cc92 100644
--- a/csharp/src/Google.Protobuf/Collections/MapField.cs
+++ b/csharp/src/Google.Protobuf/Collections/MapField.cs
@@ -327,7 +327,7 @@
         /// Returns a hash code for this instance.
         /// </summary>
         /// <returns>
-        /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table. 
+        /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table.
         /// </returns>
         public override int GetHashCode()
         {
@@ -432,7 +432,13 @@
             WriteContext.Initialize(output, out WriteContext ctx);
             try
             {
-                WriteTo(ref ctx, codec);
+                IEnumerable<KeyValuePair<TKey, TValue>> listToWrite = list;
+
+                if (output.Deterministic)
+                {
+                    listToWrite = GetSortedListCopy(list);
+                }
+                WriteTo(ref ctx, codec, listToWrite);
             }
             finally
             {
@@ -440,6 +446,23 @@
             }
         }
 
+        internal IEnumerable<KeyValuePair<TKey, TValue>> GetSortedListCopy(IEnumerable<KeyValuePair<TKey, TValue>> listToSort)
+        {
+            // We can't sort the list in place, as that would invalidate the linked list.
+            // Instead, we create a new list, sort that, and then write it out.
+            var listToWrite = new List<KeyValuePair<TKey, TValue>>(listToSort);
+            listToWrite.Sort((pair1, pair2) =>
+            {
+                if (typeof(TKey) == typeof(string))
+                {
+                    // Use Ordinal, otherwise Comparer<string>.Default uses StringComparer.CurrentCulture
+                    return StringComparer.Ordinal.Compare(pair1.Key.ToString(), pair2.Key.ToString());
+                }
+                return Comparer<TKey>.Default.Compare(pair1.Key, pair2.Key);
+            });
+            return listToWrite;
+        }
+
         /// <summary>
         /// Writes the contents of this map to the given write context, using the specified codec
         /// to encode each entry.
@@ -449,7 +472,18 @@
         [SecuritySafeCritical]
         public void WriteTo(ref WriteContext ctx, Codec codec)
         {
-            foreach (var entry in list)
+            IEnumerable<KeyValuePair<TKey, TValue>> listToWrite = list;
+            if (ctx.state.CodedOutputStream?.Deterministic ?? false)
+            {
+                listToWrite = GetSortedListCopy(list);
+            }
+            WriteTo(ref ctx, codec, listToWrite);
+        }
+
+        [SecuritySafeCritical]
+        private void WriteTo(ref WriteContext ctx, Codec codec, IEnumerable<KeyValuePair<TKey, TValue>> listKvp)
+        {
+            foreach (var entry in listKvp)
             {
                 ctx.WriteTag(codec.MapTag);
 
@@ -631,7 +665,7 @@
                 this.containsCheck = containsCheck;
             }
 
-            public int Count => parent.Count; 
+            public int Count => parent.Count;
 
             public bool IsReadOnly => true;