difftree for git.Trees (#273)

Last PR to fix #82:

This PR modifies the difftree package itself. The old version extracted the files in both trees and compare them by hand. The new version turn the trees into merkletrie.Noders and call the merkletrie.Difftree function on them.

How to review this PR:

treenoder.go: defines the treeNoder type that wraps a git.Tree and implements merkletrie.Noder.
change.go: defines the type of the output of a difftree operation. The type is the same as before, but I have moved it into its own file to keep the package organized. The old package defines the Action type too (insert, delete, modify), now, we reuse merkletrie.Action and it is no longer a field, but a method.
change_adaptor.go: defines functions to turn merkletrie.Changes into difftree.Changes.
difftree.go: before this patch this file holds all the logic to do a difftree, now it just turns the git.Trees into treeNoders, call merkletrie.difftree on them, and turns the resulting merkletrie.Changes into difftree.Changes.
The only interesting piece of code here is that noders don't have the concept of mode (file permissions). The treenoder type codifies git.Tree modes into the merkletrie.Noder hash, so changes in the mode of a file are detected as modifications, just as the original git diff-tree command does.

1 files changed, 300 insertions, 0 deletions

diff --git a/plumbing/difftree/change_test.go b/plumbing/difftree/change_test.go
new file mode 100644
index 0000000..cda4ff9
--- /dev/null
+++ b/plumbing/difftree/change_test.go
@@ -0,0 +1,300 @@
+package difftree
+
+import (
+	"os"
+	"sort"
+
+	"srcd.works/go-git.v4/plumbing"
+	"srcd.works/go-git.v4/plumbing/object"
+	"srcd.works/go-git.v4/plumbing/storer"
+	"srcd.works/go-git.v4/storage/filesystem"
+	"srcd.works/go-git.v4/utils/merkletrie"
+
+	fixtures "github.com/src-d/go-git-fixtures"
+	. "gopkg.in/check.v1"
+)
+
+type ChangeSuite struct {
+	fixtures.Suite
+	Storer  storer.EncodedObjectStorer
+	Fixture *fixtures.Fixture
+}
+
+func (s *ChangeSuite) SetUpSuite(c *C) {
+	s.Suite.SetUpSuite(c)
+	s.Fixture = fixtures.ByURL("https://github.com/src-d/go-git.git").
+		ByTag(".git").One()
+	sto, err := filesystem.NewStorage(s.Fixture.DotGit())
+	c.Assert(err, IsNil)
+	s.Storer = sto
+}
+
+func (s *ChangeSuite) tree(c *C, h plumbing.Hash) *object.Tree {
+	t, err := object.GetTree(s.Storer, h)
+	c.Assert(err, IsNil)
+	return t
+}
+
+var _ = Suite(&ChangeSuite{})
+
+func (s *ChangeSuite) TestInsert(c *C) {
+	// Commit a5078b19f08f63e7948abd0a5e2fb7d319d3a565 of the go-git
+	// fixture inserted "examples/clone/main.go".
+	//
+	// On that commit, the "examples/clone" tree is
+	//     6efca3ff41cab651332f9ebc0c96bb26be809615
+	//
+	// and the "examples/colone/main.go" is
+	//     f95dc8f7923add1a8b9f72ecb1e8db1402de601a
+
+	path := "examples/clone/main.go"
+	name := "main.go"
+	mode := os.FileMode(100644)
+	blob := plumbing.NewHash("f95dc8f7923add1a8b9f72ecb1e8db1402de601a")
+	tree := plumbing.NewHash("6efca3ff41cab651332f9ebc0c96bb26be809615")
+
+	change := &Change{
+		From: empty,
+		To: ChangeEntry{
+			Name: path,
+			Tree: s.tree(c, tree),
+			TreeEntry: object.TreeEntry{
+				Name: name,
+				Mode: mode,
+				Hash: blob,
+			},
+		},
+	}
+
+	action, err := change.Action()
+	c.Assert(err, IsNil)
+	c.Assert(action, Equals, merkletrie.Insert)
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+	c.Assert(from, IsNil)
+	c.Assert(to.Name, Equals, name)
+	c.Assert(to.Blob.Hash, Equals, blob)
+
+	str := change.String()
+	c.Assert(str, Equals, "<Action: Insert, Path: examples/clone/main.go>")
+}
+
+func (s *ChangeSuite) TestDelete(c *C) {
+	// Commit f6011d65d57c2a866e231fc21a39cb618f86f9ea of the go-git
+	// fixture deleted "utils/difftree/difftree.go".
+	//
+	// The parent of that commit is
+	//     9b4a386db3d98a4362516a00ef3d04d4698c9bcd.
+	//
+	// On that parent commit, the "utils/difftree" tree is
+	//     f3d11566401ce4b0808aab9dd6fad3d5abf1481a.
+	//
+	// and the "utils/difftree/difftree.go" is
+	//     e2cb9a5719daf634d45a063112b4044ee81da13ea.
+
+	path := "utils/difftree/difftree.go"
+	name := "difftree.go"
+	mode := os.FileMode(100644)
+	blob := plumbing.NewHash("e2cb9a5719daf634d45a063112b4044ee81da13e")
+	tree := plumbing.NewHash("f3d11566401ce4b0808aab9dd6fad3d5abf1481a")
+
+	change := &Change{
+		From: ChangeEntry{
+			Name: path,
+			Tree: s.tree(c, tree),
+			TreeEntry: object.TreeEntry{
+				Name: name,
+				Mode: mode,
+				Hash: blob,
+			},
+		},
+		To: empty,
+	}
+
+	action, err := change.Action()
+	c.Assert(err, IsNil)
+	c.Assert(action, Equals, merkletrie.Delete)
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+	c.Assert(to, IsNil)
+	c.Assert(from.Name, Equals, name)
+	c.Assert(from.Blob.Hash, Equals, blob)
+
+	str := change.String()
+	c.Assert(str, Equals, "<Action: Delete, Path: utils/difftree/difftree.go>")
+}
+
+func (s *ChangeSuite) TestModify(c *C) {
+	// Commit 7beaad711378a4daafccc2c04bc46d36df2a0fd1 of the go-git
+	// fixture modified "examples/latest/latest.go".
+	// the "examples/latest" tree is
+	//     b1f01b730b855c82431918cb338ad47ed558999b.
+	// and "examples/latest/latest.go" is blob
+	//     05f583ace3a9a078d8150905a53a4d82567f125f.
+	//
+	// The parent of that commit is
+	//     337148ef6d751477796922ac127b416b8478fcc4.
+	// the "examples/latest" tree is
+	//     8b0af31d2544acb5c4f3816a602f11418cbd126e.
+	// and "examples/latest/latest.go" is blob
+	//     de927fad935d172929aacf20e71f3bf0b91dd6f9.
+
+	path := "utils/difftree/difftree.go"
+	name := "difftree.go"
+	mode := os.FileMode(100644)
+	fromBlob := plumbing.NewHash("05f583ace3a9a078d8150905a53a4d82567f125f")
+	fromTree := plumbing.NewHash("b1f01b730b855c82431918cb338ad47ed558999b")
+	toBlob := plumbing.NewHash("de927fad935d172929aacf20e71f3bf0b91dd6f9")
+	toTree := plumbing.NewHash("8b0af31d2544acb5c4f3816a602f11418cbd126e")
+
+	change := &Change{
+		From: ChangeEntry{
+			Name: path,
+			Tree: s.tree(c, fromTree),
+			TreeEntry: object.TreeEntry{
+				Name: name,
+				Mode: mode,
+				Hash: fromBlob,
+			},
+		},
+		To: ChangeEntry{
+			Name: path,
+			Tree: s.tree(c, toTree),
+			TreeEntry: object.TreeEntry{
+				Name: name,
+				Mode: mode,
+				Hash: toBlob,
+			},
+		},
+	}
+
+	action, err := change.Action()
+	c.Assert(err, IsNil)
+	c.Assert(action, Equals, merkletrie.Modify)
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+
+	c.Assert(from.Name, Equals, name)
+	c.Assert(from.Blob.Hash, Equals, fromBlob)
+	c.Assert(to.Name, Equals, name)
+	c.Assert(to.Blob.Hash, Equals, toBlob)
+
+	str := change.String()
+	c.Assert(str, Equals, "<Action: Modify, Path: utils/difftree/difftree.go>")
+}
+
+func (s *ChangeSuite) TestEmptyChangeFails(c *C) {
+	change := &Change{}
+
+	_, err := change.Action()
+	c.Assert(err, ErrorMatches, "malformed.*")
+
+	_, _, err = change.Files()
+	c.Assert(err, ErrorMatches, "malformed.*")
+
+	str := change.String()
+	c.Assert(str, Equals, "malformed change")
+}
+
+func (s *ChangeSuite) TestErrorsFindingChildsAreDetected(c *C) {
+	// Commit 7beaad711378a4daafccc2c04bc46d36df2a0fd1 of the go-git
+	// fixture modified "examples/latest/latest.go".
+	// the "examples/latest" tree is
+	//     b1f01b730b855c82431918cb338ad47ed558999b.
+	// and "examples/latest/latest.go" is blob
+	//     05f583ace3a9a078d8150905a53a4d82567f125f.
+	//
+	// The parent of that commit is
+	//     337148ef6d751477796922ac127b416b8478fcc4.
+	// the "examples/latest" tree is
+	//     8b0af31d2544acb5c4f3816a602f11418cbd126e.
+	// and "examples/latest/latest.go" is blob
+	//     de927fad935d172929aacf20e71f3bf0b91dd6f9.
+
+	path := "utils/difftree/difftree.go"
+	name := "difftree.go"
+	mode := os.FileMode(100644)
+	fromBlob := plumbing.NewHash("aaaa") // does not exists
+	fromTree := plumbing.NewHash("b1f01b730b855c82431918cb338ad47ed558999b")
+	toBlob := plumbing.NewHash("bbbb") // does not exists
+	toTree := plumbing.NewHash("8b0af31d2544acb5c4f3816a602f11418cbd126e")
+
+	change := &Change{
+		From: ChangeEntry{
+			Name: path,
+			Tree: s.tree(c, fromTree),
+			TreeEntry: object.TreeEntry{
+				Name: name,
+				Mode: mode,
+				Hash: fromBlob,
+			},
+		},
+		To: ChangeEntry{},
+	}
+
+	_, _, err := change.Files()
+	c.Assert(err, ErrorMatches, "object not found")
+
+	change = &Change{
+		From: empty,
+		To: ChangeEntry{
+			Name: path,
+			Tree: s.tree(c, toTree),
+			TreeEntry: object.TreeEntry{
+				Name: name,
+				Mode: mode,
+				Hash: toBlob,
+			},
+		},
+	}
+
+	_, _, err = change.Files()
+	c.Assert(err, ErrorMatches, "object not found")
+}
+
+func (s *ChangeSuite) TestChangesString(c *C) {
+	expected := "[]"
+	changes := Changes{}
+	obtained := changes.String()
+	c.Assert(obtained, Equals, expected)
+
+	expected = "[<Action: Modify, Path: bla>]"
+	changes = make([]*Change, 1)
+	changes[0] = &Change{}
+	changes[0].From.Name = "bla"
+	changes[0].To.Name = "bla"
+
+	obtained = changes.String()
+	c.Assert(obtained, Equals, expected)
+
+	expected = "[<Action: Modify, Path: bla>, <Action: Delete, Path: foo/bar>]"
+	changes = make([]*Change, 2)
+	changes[0] = &Change{}
+	changes[0].From.Name = "bla"
+	changes[0].To.Name = "bla"
+	changes[1] = &Change{}
+	changes[1].From.Name = "foo/bar"
+	obtained = changes.String()
+	c.Assert(obtained, Equals, expected)
+}
+
+func (s *ChangeSuite) TestChangesSort(c *C) {
+	changes := make(Changes, 3)
+	changes[0] = &Change{}
+	changes[0].From.Name = "z"
+	changes[0].To.Name = "z"
+	changes[1] = &Change{}
+	changes[1].From.Name = "b/b"
+	changes[2] = &Change{}
+	changes[2].To.Name = "b/a"
+
+	expected := "[<Action: Insert, Path: b/a>, " +
+		"<Action: Delete, Path: b/b>, " +
+		"<Action: Modify, Path: z>]"
+
+	sort.Sort(changes)
+	c.Assert(changes.String(), Equals, expected)
+}