Sort all children and also sort adjacent children with the same name.

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. In order to follow the requirements of `Less`, we need to individually sort each subslice. PiperOrigin-RevId: 561254248
protocolbuffers · Aug 30, 2023 · c3c0a04 · c3c0a04
1 parent 0c31dbd
commit c3c0a04
Show file tree

Hide file tree

Showing 4 changed files with 82 additions and 25 deletions.
diff --git a/ast/ast.go b/ast/ast.go
@@ -75,7 +75,7 @@ type Node struct {
 
 // NodeLess is a sorting function that compares two *Nodes, possibly using the parent Node
 // for context, returning whether a is less than b.
-type NodeLess func(parent, a, b *Node) bool
+type NodeLess func(parent, a, b *Node, isWholeSlice bool) bool
 
 // ChainNodeLess combines two NodeLess functions that returns the first comparison if values are
 // not equal, else returns the second.
@@ -86,31 +86,38 @@ func ChainNodeLess(first, second NodeLess) NodeLess {
 	if second == nil {
 		return first
 	}
-	return func(parent, a, b *Node) bool {
-		if isALess := first(parent, a, b); isALess {
+	return func(parent, a, b *Node, isWholeSlice bool) bool {
+		if isALess := first(parent, a, b, isWholeSlice); isALess {
 			return true
 		}
-		if isBLess := first(parent, b, a); isBLess {
+		if isBLess := first(parent, b, a, isWholeSlice); isBLess {
 			return false
 		}
-		return second(parent, a, b)
+		return second(parent, a, b, isWholeSlice)
 	}
 }
 
-// SortableNodes returns a sort.Interface that sorts nodes by the given less function.
-func SortableNodes(ns []*Node, less NodeLess) sort.Interface {
-	return sortable{ /*parent=*/ nil, ns, less}
+// SortNodes sorts nodes by the given less function.
+func SortNodes(parent *Node, ns []*Node, less NodeLess) {
+	sort.Stable(sortableNodes(parent, ns, less, true /* isWholeSlice */))
+	end := 0
+	for begin := 0; begin < len(ns); begin = end {
+		for end = begin + 1; end < len(ns) && ns[begin].Name == ns[end].Name; end++ {
+		}
+		sort.Stable(sortableNodes(parent, ns[begin:end], less, false /* isWholeSlice */))
+	}
 }
 
-// SortableNodesWithParent returns a sort.Interface that sorts nodes by the given less function.
-func SortableNodesWithParent(parent *Node, ns []*Node, less NodeLess) sort.Interface {
-	return sortable{parent, ns, less}
+// sortableNodes returns a sort.Interface that sorts nodes by the given less function.
+func sortableNodes(parent *Node, ns []*Node, less NodeLess, isWholeSlice bool) sort.Interface {
+	return sortable{parent, ns, less, isWholeSlice}
 }
 
 type sortable struct {
-	parent *Node
-	ns     []*Node
-	less   NodeLess
+	parent       *Node
+	ns           []*Node
+	less         NodeLess
+	isWholeSlice bool
 }
 
 func (s sortable) Len() int {
@@ -125,17 +132,20 @@ func (s sortable) Less(i, j int) bool {
 	if s.less == nil {
 		return false
 	}
-	return s.less(s.parent, s.ns[i], s.ns[j])
+	return s.less(s.parent, s.ns[i], s.ns[j], s.isWholeSlice)
 }
 
 // ByFieldName is a NodeLess function that orders nodes by their field name.
-func ByFieldName(_, ni, nj *Node) bool {
+func ByFieldName(_, ni, nj *Node, isWholeSlice bool) bool {
 	return ni.Name < nj.Name
 }
 
 // ByFieldValue is a NodeLess function that orders adjacent scalar nodes with the same name by
 // their scalar value.
-func ByFieldValue(_, ni, nj *Node) bool {
+func ByFieldValue(_, ni, nj *Node, isWholeSlice bool) bool {
+	if isWholeSlice {
+		return false
+	}
 	if ni.Name != nj.Name || len(ni.Values) != 1 || len(nj.Values) != 1 {
 		return false
 	}
@@ -146,7 +156,10 @@ func ByFieldValue(_, ni, nj *Node) bool {
 // 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.
 func ByFieldSubfield(field, subfield string) NodeLess {
-	return func(_, ni, nj *Node) bool {
+	return func(_, ni, nj *Node, isWholeSlice bool) bool {
+		if isWholeSlice {
+			return false
+		}
 		if ni.Name != nj.Name {
 			return false
 		}

diff --git a/ast/ast_test.go b/ast/ast_test.go
@@ -1,7 +1,6 @@
 package ast_test
 
 import (
-	"sort"
 	"testing"
 
 	"github.com/google/go-cmp/cmp"
@@ -11,10 +10,10 @@ import (
 )
 
 func TestChainNodeLess(t *testing.T) {
-	byFirstChar := func(_, ni, nj *ast.Node) bool {
+	byFirstChar := func(_, ni, nj *ast.Node, isWholeSlice bool) bool {
 		return ni.Name[0] < nj.Name[0]
 	}
-	bySecondChar := func(_, ni, nj *ast.Node) bool {
+	bySecondChar := func(_, ni, nj *ast.Node, isWholeSlice bool) bool {
 		return ni.Name[1] < nj.Name[1]
 	}
 	tests := []struct {
@@ -54,7 +53,7 @@ func TestChainNodeLess(t *testing.T) {
 		for _, n := range names {
 			ns = append(ns, &ast.Node{Name: n})
 		}
-		sort.Stable(ast.SortableNodes(ns, less))
+		ast.SortNodes(nil /* parent */, ns, less)
 		rs := []string{}
 		for _, n := range ns {
 			rs = append(rs, n.Name)

diff --git a/parser/parser.go b/parser/parser.go
@@ -12,7 +12,6 @@ import (
 	"fmt"
 	"math"
 	"regexp"
-	"sort"
 	"strconv"
 	"strings"
 
@@ -1396,7 +1395,7 @@ func nodeSortFunction(c Config) NodeSortFunction {
 	}
 	if sorter != nil {
 		return func(parent *ast.Node, ns []*ast.Node) error {
-			sort.Stable(ast.SortableNodesWithParent(parent, ns, sorter))
+			ast.SortNodes(parent, ns, sorter)
 			if c.RequireFieldSortOrderToMatchAllFieldsInNode {
 				return unsortedFieldCollector.asError()
 			}
@@ -1431,7 +1430,10 @@ func ByFieldOrder(name string, fieldOrder []string, unsortedCollector UnsortedFi
 	for i, fieldName := range fieldOrder {
 		priorities[fieldName] = i + 1
 	}
-	return func(parent, ni, nj *ast.Node) bool {
+	return func(parent, ni, nj *ast.Node, isWholeSlice bool) bool {
+		if !isWholeSlice {
+			return false
+		}
 		if parent != nil && parent.Name != name {
 			return false
 		}

diff --git a/parser/parser_test.go b/parser/parser_test.go
@@ -1275,6 +1275,49 @@ presubmit: {
     prohibited_regexp: "UnsafeFunction"
   }
 }
+`}, {
+		name: "multiple groups of repeated fields",
+		in: `# txtpbfmt: sort_repeated_fields_by_content
+# txtpbfmt: sort_repeated_fields_by_subfield=id
+
+# field b
+field: "b"
+
+# field a
+field: "a"
+message: { id: "b" }
+message: { id: "a" }
+
+# new group
+
+# field b
+field: "b"
+
+# field a
+field: "a"
+message: { id: "b" }
+message: { id: "a" }
+`,
+		out: `# txtpbfmt: sort_repeated_fields_by_content
+# txtpbfmt: sort_repeated_fields_by_subfield=id
+
+# field a
+field: "a"
+
+# field b
+field: "b"
+message: { id: "a" }
+message: { id: "b" }
+
+# new group
+
+# field a
+field: "a"
+
+# field b
+field: "b"
+message: { id: "a" }
+message: { id: "b" }
 `}, {
 		name: "trailing comma / semicolon",
 		in: `dict: {