Repository: apple/swift-protobuf (swift)

Issue:
Deterministic JSON serialization for `map` types
## Problem

It's not currently possible to deterministically produce JSON data for types that include Protobuf `map` fields since the keys in those maps are not sorted. For example:

```swift
for _ in 0..<10 {
    var message = Some_Message.with { message in
        message.other = [
            "aaa": "abc",
            "111": "abc",
            "eee": "baz",
            "bbb": "baz",
            "ccc": "baz",
            "ddd": "baz",
        ]
    }
    message.other["0new"] = "abc"
    print(String(data: try message.jsonUTF8Data(), encoding: .utf8)!)
}
```

Outputs:

```
{"other":{"ddd":"baz","ccc":"baz","eee":"baz","111":"abc","0new":"abc","aaa":"abc","bbb":"baz"}}
{"other":{"111":"abc","bbb":"baz","ddd":"baz","0new":"abc","aaa":"abc","ccc":"baz","eee":"baz"}}
{"other":{"ddd":"baz","ccc":"baz","eee":"baz","111":"abc","0new":"abc","aaa":"abc","bbb":"baz"}}
{"other":{"111":"abc","bbb":"baz","ddd":"baz","0new":"abc","aaa":"abc","ccc":"baz","eee":"baz"}}
{"other":{"ddd":"baz","ccc":"baz","eee":"baz","111":"abc","0new":"abc","aaa":"abc","bbb":"baz"}}
{"other":{"111":"abc","bbb":"baz","ddd":"baz","0new":"abc","aaa":"abc","ccc":"baz","eee":"baz"}}
{"other":{"ddd":"baz","ccc":"baz","eee":"baz","111":"abc","0new":"abc","aaa":"abc","bbb":"baz"}}
{"other":{"111":"abc","bbb":"baz","ddd":"baz","0new":"abc","aaa":"abc","ccc":"baz","eee":"baz"}}
{"other":{"ddd":"baz","ccc":"baz","eee":"baz","111":"abc","0new":"abc","aaa":"abc","bbb":"baz"}}
{"other":{"111":"abc","bbb":"baz","ddd":"baz","0new":"abc","aaa":"abc","ccc":"baz","eee":"baz"}}
```

## Use case

When sending [Connect Unary GET requests](https://connectrpc.com/docs/protocol#unary-get-request), the serialized payload passed in the URL's query parameters must be deterministic in order to properly enable effective caching. Related: https://github.com/connectrpc/connect-swift/issues/196

## Proposal

Add a `useDeterministicOrdering: Bool = false` field to `JSONEncodingOptions` (similar to what [Protobuf for Go has](https://pkg.go.dev/github.com/golang/protobuf/proto#Buffer.SetDeterministic)) which, when set, causes `JSONEncodingVisitor.visitMapField(...)` to sort keys before iterating through and serializing them.

Pull request description:
Adds an option to ensure that JSON serialization is deterministic when serializing Protobuf `map` fields. This should be the only type that needs to be sorted, since individual fields are serialized in order by the generated code that invokes `try visitor.visit(...)` for each field.

In order to avoid the overhead of sorting for the default case, there are no changes to the existing serialization strategy when this setting is disabled.

This new option is similar to what [Protobuf provides in Go](https://pkg.go.dev/github.com/golang/protobuf/proto#Buffer.SetDeterministic), and the docstring added in this PR matches that.

Resolves https://github.com/apple/swift-protobuf/issues/1477

Patch:
diff --git a/Sources/SwiftProtobuf/JSONEncodingOptions.swift b/Sources/SwiftProtobuf/JSONEncodingOptions.swift
index 78cf5a370..124e730eb 100644
--- a/Sources/SwiftProtobuf/JSONEncodingOptions.swift
+++ b/Sources/SwiftProtobuf/JSONEncodingOptions.swift
@@ -27,5 +27,19 @@ public struct JSONEncodingOptions: Sendable {
   /// By default they are converted to JSON(lowerCamelCase) names.
   public var preserveProtoFieldNames: Bool = false
 
+  /// Whether to use deterministic ordering when serializing.
+  ///
+  /// Note that the deterministic serialization is NOT canonical across languages. 
+  /// It is NOT guaranteed to remain stable over time. It is unstable across 
+  /// different builds with schema changes due to unknown fields. Users who need
+  /// canonical serialization (e.g., persistent storage in a canonical form,
+  /// fingerprinting, etc.) should define their own canonicalization specification
+  /// and implement their own serializer rather than relying on this API.
+  ///
+  /// If deterministic serialization is requested, map entries will be sorted
+  /// by keys in lexographical order. This is an implementation detail
+  /// and subject to change.
+  public var useDeterministicOrdering: Bool = false
+
   public init() {}
 }
diff --git a/Sources/SwiftProtobuf/JSONEncodingVisitor.swift b/Sources/SwiftProtobuf/JSONEncodingVisitor.swift
index fccbca4ed..db51d22e7 100644
--- a/Sources/SwiftProtobuf/JSONEncodingVisitor.swift
+++ b/Sources/SwiftProtobuf/JSONEncodingVisitor.swift
@@ -358,39 +358,49 @@ internal struct JSONEncodingVisitor: Visitor {
   // Packed fields are handled the same as non-packed fields, so JSON just
   // relies on the default implementations in Visitor.swift
 
-
-
   mutating func visitMapField<KeyType, ValueType: MapValueType>(fieldType: _ProtobufMap<KeyType, ValueType>.Type, value: _ProtobufMap<KeyType, ValueType>.BaseType, fieldNumber: Int) throws {
-    try startField(for: fieldNumber)
-    encoder.append(text: "{")
-    var mapVisitor = JSONMapEncodingVisitor(encoder: JSONEncoder(), options: options)
-    for (k,v) in value {
-        try KeyType.visitSingular(value: k, fieldNumber: 1, with: &mapVisitor)
-        try ValueType.visitSingular(value: v, fieldNumber: 2, with: &mapVisitor)
+    try iterateAndEncode(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
+      (visitor: inout JSONMapEncodingVisitor, key, value) throws -> () in
+      try KeyType.visitSingular(value: key, fieldNumber: 1, with: &visitor)
+      try ValueType.visitSingular(value: value, fieldNumber: 2, with: &visitor)
     }
-    encoder.append(utf8Bytes: mapVisitor.bytesResult)
-    encoder.append(text: "}")
   }
 
   mutating func visitMapField<KeyType, ValueType>(fieldType: _ProtobufEnumMap<KeyType, ValueType>.Type, value: _ProtobufEnumMap<KeyType, ValueType>.BaseType, fieldNumber: Int) throws  where ValueType.RawValue == Int {
-    try startField(for: fieldNumber)
-    encoder.append(text: "{")
-    var mapVisitor = JSONMapEncodingVisitor(encoder: JSONEncoder(), options: options)
-    for (k, v) in value {
-      try KeyType.visitSingular(value: k, fieldNumber: 1, with: &mapVisitor)
-      try mapVisitor.visitSingularEnumField(value: v, fieldNumber: 2)
+    try iterateAndEncode(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
+      (visitor: inout JSONMapEncodingVisitor, key, value) throws -> () in
+      try KeyType.visitSingular(value: key, fieldNumber: 1, with: &visitor)
+      try visitor.visitSingularEnumField(value: value, fieldNumber: 2)
     }
-    encoder.append(utf8Bytes: mapVisitor.bytesResult)
-    encoder.append(text: "}")
   }
 
   mutating func visitMapField<KeyType, ValueType>(fieldType: _ProtobufMessageMap<KeyType, ValueType>.Type, value: _ProtobufMessageMap<KeyType, ValueType>.BaseType, fieldNumber: Int) throws {
+    try iterateAndEncode(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
+      (visitor: inout JSONMapEncodingVisitor, key, value) throws -> () in
+      try KeyType.visitSingular(value: key, fieldNumber: 1, with: &visitor)
+      try visitor.visitSingularMessageField(value: value, fieldNumber: 2)
+    }
+  }
+
+  /// Helper to encapsulate the common structure of iterating over a map
+  /// and encoding the keys and values.
+  private mutating func iterateAndEncode<K, V>(
+    map: Dictionary<K, V>,
+    fieldNumber: Int,
+    isOrderedBefore: (K, K) -> Bool,
+    encode: (inout JSONMapEncodingVisitor, K, V) throws -> ()
+  ) throws {
     try startField(for: fieldNumber)
     encoder.append(text: "{")
     var mapVisitor = JSONMapEncodingVisitor(encoder: JSONEncoder(), options: options)
-    for (k,v) in value {
-        try KeyType.visitSingular(value: k, fieldNumber: 1, with: &mapVisitor)
-        try mapVisitor.visitSingularMessageField(value: v, fieldNumber: 2)
+    if options.useDeterministicOrdering {
+      for (k,v) in map.sorted(by: { isOrderedBefore( $0.0, $1.0) }) {
+        try encode(&mapVisitor, k, v)
+      }
+    } else {
+      for (k,v) in map {
+        try encode(&mapVisitor, k, v)
+      }
     }
     encoder.append(utf8Bytes: mapVisitor.bytesResult)
     encoder.append(text: "}")
diff --git a/Sources/SwiftProtobuf/TextFormatEncodingVisitor.swift b/Sources/SwiftProtobuf/TextFormatEncodingVisitor.swift
index 51705b89c..a82580727 100644
--- a/Sources/SwiftProtobuf/TextFormatEncodingVisitor.swift
+++ b/Sources/SwiftProtobuf/TextFormatEncodingVisitor.swift
@@ -503,16 +503,16 @@ internal struct TextFormatEncodingVisitor: Visitor {
   // fields (including proto3's default use of packed) without
   // introducing the baggage of a separate option.
 
-  private mutating func _visitPacked<T>(
-    value: [T], fieldNumber: Int,
+  private mutating func iterateAndEncode<T>(
+    packedValue: [T], fieldNumber: Int,
     encode: (T, inout TextFormatEncoder) -> ()
   ) throws {
-      assert(!value.isEmpty)
+      assert(!packedValue.isEmpty)
       emitFieldName(lookingUp: fieldNumber)
       encoder.startRegularField()
       var firstItem = true
       encoder.startArray()
-      for v in value {
+      for v in packedValue {
           if !firstItem {
               encoder.arraySeparator()
           }
@@ -524,42 +524,42 @@ internal struct TextFormatEncodingVisitor: Visitor {
   }
 
   mutating func visitPackedFloatField(value: [Float], fieldNumber: Int) throws {
-    try _visitPacked(value: value, fieldNumber: fieldNumber) {
+    try iterateAndEncode(packedValue: value, fieldNumber: fieldNumber) {
       (v: Float, encoder: inout TextFormatEncoder) in
       encoder.putFloatValue(value: v)
     }
   }
 
   mutating func visitPackedDoubleField(value: [Double], fieldNumber: Int) throws {
-    try _visitPacked(value: value, fieldNumber: fieldNumber) {
+    try iterateAndEncode(packedValue: value, fieldNumber: fieldNumber) {
       (v: Double, encoder: inout TextFormatEncoder) in
       encoder.putDoubleValue(value: v)
     }
   }
 
   mutating func visitPackedInt32Field(value: [Int32], fieldNumber: Int) throws {
-    try _visitPacked(value: value, fieldNumber: fieldNumber) {
+    try iterateAndEncode(packedValue: value, fieldNumber: fieldNumber) {
       (v: Int32, encoder: inout TextFormatEncoder) in
       encoder.putInt64(value: Int64(v))
     }
   }
 
   mutating func visitPackedInt64Field(value: [Int64], fieldNumber: Int) throws {
-    try _visitPacked(value: value, fieldNumber: fieldNumber) {
+    try iterateAndEncode(packedValue: value, fieldNumber: fieldNumber) {
       (v: Int64, encoder: inout TextFormatEncoder) in
       encoder.putInt64(value: v)
     }
   }
 
   mutating func visitPackedUInt32Field(value: [UInt32], fieldNumber: Int) throws {
-    try _visitPacked(value: value, fieldNumber: fieldNumber) {
+    try iterateAndEncode(packedValue: value, fieldNumber: fieldNumber) {
       (v: UInt32, encoder: inout TextFormatEncoder) in
       encoder.putUInt64(value: UInt64(v))
     }
   }
 
   mutating func visitPackedUInt64Field(value: [UInt64], fieldNumber: Int) throws {
-    try _visitPacked(value: value, fieldNumber: fieldNumber) {
+    try iterateAndEncode(packedValue: value, fieldNumber: fieldNumber) {
       (v: UInt64, encoder: inout TextFormatEncoder) in
       encoder.putUInt64(value: v)
     }
@@ -590,14 +590,14 @@ internal struct TextFormatEncodingVisitor: Visitor {
   }
 
   mutating func visitPackedBoolField(value: [Bool], fieldNumber: Int) throws {
-    try _visitPacked(value: value, fieldNumber: fieldNumber) {
+    try iterateAndEncode(packedValue: value, fieldNumber: fieldNumber) {
       (v: Bool, encoder: inout TextFormatEncoder) in
       encoder.putBoolValue(value: v)
     }
   }
 
   mutating func visitPackedEnumField<E: Enum>(value: [E], fieldNumber: Int) throws {
-    try _visitPacked(value: value, fieldNumber: fieldNumber) {
+    try iterateAndEncode(packedValue: value, fieldNumber: fieldNumber) {
       (v: E, encoder: inout TextFormatEncoder) in
       encoder.putEnumValue(value: v)
     }
@@ -605,11 +605,11 @@ internal struct TextFormatEncodingVisitor: Visitor {
 
   /// Helper to encapsulate the common structure of iterating over a map
   /// and encoding the keys and values.
-  private mutating func _visitMap<K, V>(
+  private mutating func iterateAndEncode<K, V>(
     map: Dictionary<K, V>,
     fieldNumber: Int,
     isOrderedBefore: (K, K) -> Bool,
-    coder: (inout TextFormatEncodingVisitor, K, V) throws -> ()
+    encode: (inout TextFormatEncodingVisitor, K, V) throws -> ()
   ) throws {
       // Cache old visitor configuration
       let oldNameMap = self.nameMap
@@ -625,7 +625,7 @@ internal struct TextFormatEncodingVisitor: Visitor {
           self.nameResolver = mapNameResolver
           self.extensions = nil
 
-          try coder(&self, k, v)
+          try encode(&self, k, v)
 
           // Restore configuration before resuming containing message
           self.extensions = oldExtensions
@@ -641,7 +641,7 @@ internal struct TextFormatEncodingVisitor: Visitor {
     value: _ProtobufMap<KeyType, ValueType>.BaseType,
     fieldNumber: Int
   ) throws {
-      try _visitMap(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
+      try iterateAndEncode(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
           (visitor: inout TextFormatEncodingVisitor, key, value) throws -> () in
           try KeyType.visitSingular(value: key, fieldNumber: 1, with: &visitor)
           try ValueType.visitSingular(value: value, fieldNumber: 2, with: &visitor)
@@ -653,7 +653,7 @@ internal struct TextFormatEncodingVisitor: Visitor {
     value: _ProtobufEnumMap<KeyType, ValueType>.BaseType,
     fieldNumber: Int
   ) throws where ValueType.RawValue == Int {
-      try _visitMap(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
+      try iterateAndEncode(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
           (visitor: inout TextFormatEncodingVisitor, key, value) throws -> () in
           try KeyType.visitSingular(value: key, fieldNumber: 1, with: &visitor)
           try visitor.visitSingularEnumField(value: value, fieldNumber: 2)
@@ -665,7 +665,7 @@ internal struct TextFormatEncodingVisitor: Visitor {
     value: _ProtobufMessageMap<KeyType, ValueType>.BaseType,
     fieldNumber: Int
   ) throws {
-      try _visitMap(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
+      try iterateAndEncode(map: value, fieldNumber: fieldNumber, isOrderedBefore: KeyType._lessThan) {
           (visitor: inout TextFormatEncodingVisitor, key, value) throws -> () in
           try KeyType.visitSingular(value: key, fieldNumber: 1, with: &visitor)
           try visitor.visitSingularMessageField(value: value, fieldNumber: 2)


Test patch:
diff --git a/Tests/SwiftProtobufTests/Test_JSONEncodingOptions.swift b/Tests/SwiftProtobufTests/Test_JSONEncodingOptions.swift
index f6f2d1270..a6d426ee0 100644
--- a/Tests/SwiftProtobufTests/Test_JSONEncodingOptions.swift
+++ b/Tests/SwiftProtobufTests/Test_JSONEncodingOptions.swift
@@ -272,4 +272,48 @@ class Test_JSONEncodingOptions: XCTestCase {
     XCTAssertEqual(try msg7.jsonString(options: protoNames),
                    "{\"@type\":\"type.googleapis.com/swift_proto_testing.TestAllTypes\",\"optional_nested_enum\":\"NEG\"}")
   }
+
+  func testUseDeterministicOrdering() {
+    var options = JSONEncodingOptions()
+    options.useDeterministicOrdering = true
+
+    let stringMap = SwiftProtoTesting_Message3.with {
+      $0.mapStringString = [
+        "b": "B",
+        "a": "A",
+        "0": "0",
+        "UPPER": "v",
+        "x": "X",
+      ]
+    }
+    XCTAssertEqual(
+      try stringMap.jsonString(options: options),
+      "{\"mapStringString\":{\"0\":\"0\",\"UPPER\":\"v\",\"a\":\"A\",\"b\":\"B\",\"x\":\"X\"}}"
+    )
+
+    let messageMap = SwiftProtoTesting_Message3.with {
+      $0.mapInt32Message = [
+        5: .with { $0.optionalSint32 = 5 },
+        1: .with { $0.optionalSint32 = 1 },
+        3: .with { $0.optionalSint32 = 3 },
+      ]
+    }
+    XCTAssertEqual(
+      try messageMap.jsonString(options: options),
+      "{\"mapInt32Message\":{\"1\":{\"optionalSint32\":1},\"3\":{\"optionalSint32\":3},\"5\":{\"optionalSint32\":5}}}"
+    )
+
+    let enumMap = SwiftProtoTesting_Message3.with {
+      $0.mapInt32Enum = [
+        5: .foo,
+        3: .bar,
+        0: .baz,
+        1: .extra3,
+      ]
+    }
+    XCTAssertEqual(
+      try enumMap.jsonString(options: options),
+      "{\"mapInt32Enum\":{\"0\":\"BAZ\",\"1\":\"EXTRA_3\",\"3\":\"BAR\",\"5\":\"FOO\"}}"
+    )
+  }
 }