Make sort_repeated_fields_by_subfield transitive and stable.

https://pkg.go.dev/sort#Interface says: > Less must describe a transitive ordering: > - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well. > - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well. The previous implementation tried to sort only adjacent fields, but this meant it didn't follow the requirements of `Less`. This made the sorting unstable for inputs like the attached bug. The new implementation makes the order transitive and stable. The next change will fix `sort_repeated_fields_by_content` which has the same problem. PiperOrigin-RevId: 561255014
protocolbuffers · Aug 30, 2023 · d15414b · d15414b
1 parent c3c0a04
commit d15414b
Showing 1 changed file with 15 additions and 9 deletions.
diff --git a/ast/ast.go b/ast/ast.go
@@ -152,6 +152,15 @@ func ByFieldValue(_, ni, nj *Node, isWholeSlice bool) bool {
 	return ni.Values[0].Value < nj.Values[0].Value
 }
 
+func getChildValueByFieldSubfield(field, subfield string, n *Node) *Value {
+	if field != "" {
+		if n.Name != field {
+			return nil
+		}
+	}
+	return n.getChildValue(subfield)
+}
+
 // ByFieldSubfield returns a NodeLess function that orders adjacent message nodes with the given
 // field name by the given subfield name value. If no field name is provided, it compares the
 // subfields of any adjacent nodes with matching names.
@@ -160,18 +169,15 @@ func ByFieldSubfield(field, subfield string) NodeLess {
 		if isWholeSlice {
 			return false
 		}
-		if ni.Name != nj.Name {
-			return false
-		}
-		if field != "" && ni.Name != field {
-			return false
+		vi := getChildValueByFieldSubfield(field, subfield, ni)
+		vj := getChildValueByFieldSubfield(field, subfield, nj)
+		if vi == nil {
+			return vj != nil
 		}
-		niChildValue := ni.getChildValue(subfield)
-		njChildValue := nj.getChildValue(subfield)
-		if niChildValue == nil || njChildValue == nil {
+		if vj == nil {
 			return false
 		}
-		return niChildValue.Value < njChildValue.Value
+		return vi.Value < vj.Value
 	}
 }