search

protocolbuffers / txtpbfmt

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

Make `sort_repeated_fields_by_content` transitive and stable. #102

Closed copybara-service[bot] closed 10 months ago

copybara-service[bot] commented 10 months ago

Make sort_repeated_fields_by_content 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 parser.ByFieldOrder which has the same problem.