search

protocolbuffers / txtpbfmt

txtpbfmt parses, edits and formats text proto files in a way that preserves comments.
Apache License 2.0
99 stars 19 forks source link

Make `sort_repeated_fields_by_subfield` transitive and stable. #101

Closed copybara-service[bot] closed 1 year ago

copybara-service[bot] commented 1 year ago

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.