plumbing: object, check entry order in (*Tree).Encode, export TreeEntrySorter

2 files changed, 55 insertions, 0 deletions

diff --git a/plumbing/object/tree.go b/plumbing/object/tree.go
index 7fe773d..0fd0e51 100644
--- a/plumbing/object/tree.go
+++ b/plumbing/object/tree.go
@@ -7,6 +7,7 @@ import (
 	"io"
 	"path"
 	"path/filepath"
+	"sort"
 	"strings"
 
 	"github.com/go-git/go-git/v5/plumbing"
@@ -27,6 +28,7 @@ var (
 	ErrFileNotFound      = errors.New("file not found")
 	ErrDirectoryNotFound = errors.New("directory not found")
 	ErrEntryNotFound     = errors.New("entry not found")
+	ErrEntriesNotSorted  = errors.New("entries in tree are not sorted")
 )
 
 // Tree is basically like a directory - it references a bunch of other trees
@@ -270,6 +272,28 @@ func (t *Tree) Decode(o plumbing.EncodedObject) (err error) {
 	return nil
 }
 
+type TreeEntrySorter []TreeEntry
+
+func (s TreeEntrySorter) Len() int {
+	return len(s)
+}
+
+func (s TreeEntrySorter) Less(i, j int) bool {
+	name1 := s[i].Name
+	name2 := s[j].Name
+	if s[i].Mode == filemode.Dir {
+		name1 += "/"
+	}
+	if s[j].Mode == filemode.Dir {
+		name2 += "/"
+	}
+	return name1 < name2
+}
+
+func (s TreeEntrySorter) Swap(i, j int) {
+	s[i], s[j] = s[j], s[i]
+}
+
 // Encode transforms a Tree into a plumbing.EncodedObject.
 func (t *Tree) Encode(o plumbing.EncodedObject) (err error) {
 	o.SetType(plumbing.TreeObject)
@@ -279,6 +303,11 @@ func (t *Tree) Encode(o plumbing.EncodedObject) (err error) {
 	}
 
 	defer ioutil.CheckClose(w, &err)
+
+	if !sort.IsSorted(TreeEntrySorter(t.Entries)) {
+		return ErrEntriesNotSorted
+	}
+
 	for _, entry := range t.Entries {
 		if strings.IndexByte(entry.Name, 0) != -1 {
 			return fmt.Errorf("malformed filename %q", entry.Name)
diff --git a/plumbing/object/tree_test.go b/plumbing/object/tree_test.go
index bb5fc7a..feb058a 100644
--- a/plumbing/object/tree_test.go
+++ b/plumbing/object/tree_test.go
@@ -4,6 +4,7 @@ import (
 	"context"
 	"errors"
 	"io"
+	"sort"
 	"testing"
 
 	fixtures "github.com/go-git/go-git-fixtures/v4"
@@ -220,6 +221,30 @@ func (o *SortReadCloser) Read(p []byte) (int, error) {
 	return nw, nil
 }
 
+func (s *TreeSuite) TestTreeEntriesSorted(c *C) {
+	tree := &Tree{
+		Entries: []TreeEntry{
+			{"foo", filemode.Empty, plumbing.NewHash("b029517f6300c2da0f4b651b8642506cd6aaf45d")},
+			{"bar", filemode.Empty, plumbing.NewHash("c029517f6300c2da0f4b651b8642506cd6aaf45d")},
+			{"baz", filemode.Empty, plumbing.NewHash("d029517f6300c2da0f4b651b8642506cd6aaf45d")},
+		},
+	}
+
+	{
+		c.Assert(sort.IsSorted(TreeEntrySorter(tree.Entries)), Equals, false)
+		obj := &plumbing.MemoryObject{}
+		err := tree.Encode(obj)
+		c.Assert(err, Equals, ErrEntriesNotSorted)
+	}
+
+	{
+		sort.Sort(TreeEntrySorter(tree.Entries))
+		obj := &plumbing.MemoryObject{}
+		err := tree.Encode(obj)
+		c.Assert(err, IsNil)
+	}
+}
+
 func (s *TreeSuite) TestTreeDecodeEncodeIdempotent(c *C) {
 	trees := []*Tree{
 		{
@@ -231,6 +256,7 @@ func (s *TreeSuite) TestTreeDecodeEncodeIdempotent(c *C) {
 		},
 	}
 	for _, tree := range trees {
+		sort.Sort(TreeEntrySorter(tree.Entries))
 		obj := &plumbing.MemoryObject{}
 		err := tree.Encode(obj)
 		c.Assert(err, IsNil)