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.

7 files changed, 1269 insertions, 536 deletions

diff --git a/plumbing/difftree/change.go b/plumbing/difftree/change.go
new file mode 100644
index 0000000..c636577
--- /dev/null
+++ b/plumbing/difftree/change.go
@@ -0,0 +1,121 @@
+package difftree
+
+import (
+	"bytes"
+	"fmt"
+	"strings"
+
+	"srcd.works/go-git.v4/plumbing/object"
+	"srcd.works/go-git.v4/utils/merkletrie"
+)
+
+// Change values represent a detected change between two git trees.  For
+// modifications, From is the original status of the node and To is its
+// final status.  For insertions, From is the zero value and for
+// deletions To is the zero value.
+type Change struct {
+	From ChangeEntry
+	To   ChangeEntry
+}
+
+var empty = ChangeEntry{}
+
+// Action returns the kind of action represented by the change, an
+// insertion, a deletion or a modification.
+func (c *Change) Action() (merkletrie.Action, error) {
+	if c.From == empty && c.To == empty {
+		return merkletrie.Action(0),
+			fmt.Errorf("malformed change: empty from and to")
+	}
+	if c.From == empty {
+		return merkletrie.Insert, nil
+	}
+	if c.To == empty {
+		return merkletrie.Delete, nil
+	}
+
+	return merkletrie.Modify, nil
+}
+
+// Files return the files before and after a change.
+// For insertions from will be nil. For deletions to will be nil.
+func (c *Change) Files() (from, to *object.File, err error) {
+	action, err := c.Action()
+	if err != nil {
+		return
+	}
+
+	if action == merkletrie.Insert || action == merkletrie.Modify {
+		to, err = c.To.Tree.TreeEntryFile(&c.To.TreeEntry)
+		if err != nil {
+			return
+		}
+	}
+
+	if action == merkletrie.Delete || action == merkletrie.Modify {
+		from, err = c.From.Tree.TreeEntryFile(&c.From.TreeEntry)
+		if err != nil {
+			return
+		}
+	}
+
+	return
+}
+
+func (c *Change) String() string {
+	action, err := c.Action()
+	if err != nil {
+		return fmt.Sprintf("malformed change")
+	}
+
+	return fmt.Sprintf("<Action: %s, Path: %s>", action, c.name())
+}
+
+func (c *Change) name() string {
+	if c.From != empty {
+		return c.From.Name
+	}
+
+	return c.To.Name
+}
+
+// ChangeEntry values represent a node that has suffered a change.
+type ChangeEntry struct {
+	// Full path of the node using "/" as separator.
+	Name string
+	// Parent tree of the node that has changed.
+	Tree *object.Tree
+	// The entry of the node.
+	TreeEntry object.TreeEntry
+}
+
+// Changes represents a collection of changes between two git trees.
+// Implements sort.Interface lexicographically over the path of the
+// changed files.
+type Changes []*Change
+
+func (c Changes) Len() int {
+	return len(c)
+}
+
+func (c Changes) Swap(i, j int) {
+	c[i], c[j] = c[j], c[i]
+}
+
+func (c Changes) Less(i, j int) bool {
+	return strings.Compare(c[i].name(), c[j].name()) < 0
+}
+
+func (c Changes) String() string {
+	var buffer bytes.Buffer
+	buffer.WriteString("[")
+	comma := ""
+	for _, v := range c {
+		buffer.WriteString(comma)
+		buffer.WriteString(v.String())
+		comma = ", "
+	}
+	buffer.WriteString("]")
+
+	return buffer.String()
+}
diff --git a/plumbing/difftree/change_adaptor.go b/plumbing/difftree/change_adaptor.go
new file mode 100644
index 0000000..edc20b3
--- /dev/null
+++ b/plumbing/difftree/change_adaptor.go
@@ -0,0 +1,61 @@
+package difftree
+
+// The folowing functions transform changes types form the merkletrie
+// package to changes types from this package.
+
+import (
+	"fmt"
+
+	"srcd.works/go-git.v4/plumbing/object"
+	"srcd.works/go-git.v4/utils/merkletrie"
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+func newChange(c merkletrie.Change) (*Change, error) {
+	ret := &Change{}
+
+	var err error
+	if ret.From, err = newChangeEntry(c.From); err != nil {
+		return nil, fmt.Errorf("From field: ", err)
+	}
+
+	if ret.To, err = newChangeEntry(c.To); err != nil {
+		return nil, fmt.Errorf("To field: ", err)
+	}
+
+	return ret, nil
+}
+
+func newChangeEntry(p noder.Path) (ChangeEntry, error) {
+	if p == nil {
+		return empty, nil
+	}
+
+	asTreeNoder, ok := p.Last().(*treeNoder)
+	if !ok {
+		return ChangeEntry{}, fmt.Errorf("cannot transform non-TreeNoders")
+	}
+
+	return ChangeEntry{
+		Name: p.String(),
+		Tree: asTreeNoder.parent,
+		TreeEntry: object.TreeEntry{
+			Name: asTreeNoder.name,
+			Mode: asTreeNoder.mode,
+			Hash: asTreeNoder.hash,
+		},
+	}, nil
+}
+
+func newChanges(src merkletrie.Changes) (Changes, error) {
+	ret := make(Changes, len(src))
+	var err error
+	for i, e := range src {
+		ret[i], err = newChange(e)
+		if err != nil {
+			return nil, fmt.Errorf("change #%d: %s", err)
+		}
+	}
+
+	return ret, nil
+}
diff --git a/plumbing/difftree/change_adaptor_test.go b/plumbing/difftree/change_adaptor_test.go
new file mode 100644
index 0000000..2ce2c54
--- /dev/null
+++ b/plumbing/difftree/change_adaptor_test.go
@@ -0,0 +1,413 @@
+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"
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
+
+	"github.com/src-d/go-git-fixtures"
+	. "gopkg.in/check.v1"
+)
+
+type ChangeAdaptorSuite struct {
+	fixtures.Suite
+	Storer  storer.EncodedObjectStorer
+	Fixture *fixtures.Fixture
+}
+
+func (s *ChangeAdaptorSuite) SetUpSuite(c *C) {
+	s.Suite.SetUpSuite(c)
+	s.Fixture = fixtures.Basic().One()
+	sto, err := filesystem.NewStorage(s.Fixture.DotGit())
+	c.Assert(err, IsNil)
+	s.Storer = sto
+}
+
+func (s *ChangeAdaptorSuite) tree(c *C, h plumbing.Hash) *object.Tree {
+	t, err := object.GetTree(s.Storer, h)
+	c.Assert(err, IsNil)
+	return t
+}
+
+var _ = Suite(&ChangeAdaptorSuite{})
+
+// utility function to build Noders from a tree and an tree entry.
+func newNoder(t *object.Tree, e object.TreeEntry) noder.Noder {
+	return &treeNoder{
+		parent: t,
+		name:   e.Name,
+		mode:   e.Mode,
+		hash:   e.Hash,
+	}
+}
+
+// utility function to build Paths
+func newPath(nn ...noder.Noder) noder.Path { return noder.Path(nn) }
+
+func (s *ChangeAdaptorSuite) TestTreeNoderHashHasMode(c *C) {
+	hash := plumbing.NewHash("aaaa")
+	mode := object.FileMode
+
+	treeNoder := &treeNoder{
+		hash: hash,
+		mode: mode,
+	}
+
+	expected := []byte{
+		0xaa, 0xaa, 0x00, 0x00, // original hash is aaaa and 16 zeros
+		0x00, 0x00, 0x00, 0x00,
+		0x00, 0x00, 0x00, 0x00,
+		0x00, 0x00, 0x00, 0x00,
+		0x00, 0x00, 0x00, 0x00,
+		0xa4, 0x81, 0x00, 0x00, // object.FileMode in little endian
+	}
+
+	c.Assert(treeNoder.Hash(), DeepEquals, expected)
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangeInsert(c *C) {
+	tree := &object.Tree{}
+	entry := object.TreeEntry{
+		Name: "name",
+		Mode: os.FileMode(42),
+		Hash: plumbing.NewHash("aaaaa"),
+	}
+	path := newPath(newNoder(tree, entry))
+
+	expectedTo, err := newChangeEntry(path)
+	c.Assert(err, IsNil)
+
+	src := merkletrie.Change{
+		From: nil,
+		To:   path,
+	}
+
+	obtained, err := newChange(src)
+	c.Assert(err, IsNil)
+	action, err := obtained.Action()
+	c.Assert(err, IsNil)
+	c.Assert(action, Equals, merkletrie.Insert)
+	c.Assert(obtained.From, Equals, ChangeEntry{})
+	c.Assert(obtained.To, Equals, expectedTo)
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangeDelete(c *C) {
+	tree := &object.Tree{}
+	entry := object.TreeEntry{
+		Name: "name",
+		Mode: os.FileMode(42),
+		Hash: plumbing.NewHash("aaaaa"),
+	}
+	path := newPath(newNoder(tree, entry))
+
+	expectedFrom, err := newChangeEntry(path)
+	c.Assert(err, IsNil)
+
+	src := merkletrie.Change{
+		From: path,
+		To:   nil,
+	}
+
+	obtained, err := newChange(src)
+	c.Assert(err, IsNil)
+	action, err := obtained.Action()
+	c.Assert(err, IsNil)
+	c.Assert(action, Equals, merkletrie.Delete)
+	c.Assert(obtained.From, Equals, expectedFrom)
+	c.Assert(obtained.To, Equals, ChangeEntry{})
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangeModify(c *C) {
+	treeA := &object.Tree{}
+	entryA := object.TreeEntry{
+		Name: "name",
+		Mode: os.FileMode(42),
+		Hash: plumbing.NewHash("aaaaa"),
+	}
+	pathA := newPath(newNoder(treeA, entryA))
+	expectedFrom, err := newChangeEntry(pathA)
+	c.Assert(err, IsNil)
+
+	treeB := &object.Tree{}
+	entryB := object.TreeEntry{
+		Name: "name",
+		Mode: os.FileMode(42),
+		Hash: plumbing.NewHash("bbbb"),
+	}
+	pathB := newPath(newNoder(treeB, entryB))
+	expectedTo, err := newChangeEntry(pathB)
+	c.Assert(err, IsNil)
+
+	src := merkletrie.Change{
+		From: pathA,
+		To:   pathB,
+	}
+
+	obtained, err := newChange(src)
+	c.Assert(err, IsNil)
+	action, err := obtained.Action()
+	c.Assert(err, IsNil)
+	c.Assert(action, Equals, merkletrie.Modify)
+	c.Assert(obtained.From, Equals, expectedFrom)
+	c.Assert(obtained.To, Equals, expectedTo)
+}
+
+func (s *ChangeAdaptorSuite) TestEmptyChangeFails(c *C) {
+	change := &Change{
+		From: empty,
+		To:   empty,
+	}
+	_, err := change.Action()
+	c.Assert(err, ErrorMatches, "malformed change.*")
+
+	_, _, err = change.Files()
+	c.Assert(err, ErrorMatches, "malformed change.*")
+
+	str := change.String()
+	c.Assert(str, Equals, "malformed change")
+}
+
+type noderMock struct{ noder.Noder }
+
+func (s *ChangeAdaptorSuite) TestNewChangeFailsWithChangesFromOtherNoders(c *C) {
+	src := merkletrie.Change{
+		From: newPath(noderMock{}),
+		To:   nil,
+	}
+	_, err := newChange(src)
+	c.Assert(err, Not(IsNil))
+
+	src = merkletrie.Change{
+		From: nil,
+		To:   newPath(noderMock{}),
+	}
+	_, err = newChange(src)
+	c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestChangeStringFrom(c *C) {
+	expected := "<Action: Delete, Path: foo>"
+	change := Change{}
+	change.From.Name = "foo"
+
+	obtained := change.String()
+	c.Assert(obtained, Equals, expected)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeStringTo(c *C) {
+	expected := "<Action: Insert, Path: foo>"
+	change := Change{}
+	change.To.Name = "foo"
+
+	obtained := change.String()
+	c.Assert(obtained, Equals, expected)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesInsert(c *C) {
+	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+	change := Change{}
+	change.To.Name = "json/long.json"
+	change.To.Tree = tree
+	change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+	c.Assert(from, IsNil)
+	c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesInsertNotFound(c *C) {
+	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+	change := Change{}
+	change.To.Name = "json/long.json"
+	change.To.Tree = tree
+	// there is no object for this hash
+	change.To.TreeEntry.Hash = plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
+
+	_, _, err := change.Files()
+	c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesDelete(c *C) {
+	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+	change := Change{}
+	change.From.Name = "json/long.json"
+	change.From.Tree = tree
+	change.From.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+	c.Assert(to, IsNil)
+	c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesDeleteNotFound(c *C) {
+	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+	change := Change{}
+	change.From.Name = "json/long.json"
+	change.From.Tree = tree
+	// there is no object for this hash
+	change.From.TreeEntry.Hash = plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
+
+	_, _, err := change.Files()
+	c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestChangeFilesModify(c *C) {
+	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+	change := Change{}
+	change.To.Name = "json/long.json"
+	change.To.Tree = tree
+	change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+	change.From.Name = "json/long.json"
+	change.From.Tree = tree
+	change.From.TreeEntry.Hash = plumbing.NewHash("9a48f23120e880dfbe41f7c9b7b708e9ee62a492")
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+	c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
+	c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeEntryFailsWithOtherNoders(c *C) {
+	path := noder.Path{noderMock{}}
+	_, err := newChangeEntry(path)
+	c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestChangeEntryFromNilIsZero(c *C) {
+	obtained, err := newChangeEntry(nil)
+	c.Assert(err, IsNil)
+	c.Assert(obtained, Equals, ChangeEntry{})
+}
+
+func (s *ChangeAdaptorSuite) TestChangeEntryFromSortPath(c *C) {
+	tree := &object.Tree{}
+	entry := object.TreeEntry{
+		Name: "name",
+		Mode: os.FileMode(42),
+		Hash: plumbing.NewHash("aaaaa"),
+	}
+	path := newPath(newNoder(tree, entry))
+
+	obtained, err := newChangeEntry(path)
+	c.Assert(err, IsNil)
+
+	c.Assert(obtained.Name, Equals, entry.Name)
+	c.Assert(obtained.Tree, Equals, tree)
+	c.Assert(obtained.TreeEntry, DeepEquals, entry)
+}
+
+func (s *ChangeAdaptorSuite) TestChangeEntryFromLongPath(c *C) {
+	treeA := &object.Tree{}
+	entryA := object.TreeEntry{
+		Name: "nameA",
+		Mode: os.FileMode(42),
+		Hash: plumbing.NewHash("aaaa"),
+	}
+
+	treeB := &object.Tree{}
+	entryB := object.TreeEntry{
+		Name: "nameB",
+		Mode: os.FileMode(24),
+		Hash: plumbing.NewHash("bbbb"),
+	}
+
+	path := newPath(
+		newNoder(treeA, entryA),
+		newNoder(treeB, entryB),
+	)
+
+	obtained, err := newChangeEntry(path)
+	c.Assert(err, IsNil)
+
+	c.Assert(obtained.Name, Equals, entryA.Name+"/"+entryB.Name)
+	c.Assert(obtained.Tree, Equals, treeB)
+	c.Assert(obtained.TreeEntry, Equals, entryB)
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangesEmpty(c *C) {
+	expected := "[]"
+	changes, err := newChanges(nil)
+	c.Assert(err, IsNil)
+	obtained := changes.String()
+	c.Assert(obtained, Equals, expected)
+
+	expected = "[]"
+	changes, err = newChanges(merkletrie.Changes{})
+	c.Assert(err, IsNil)
+	obtained = changes.String()
+	c.Assert(obtained, Equals, expected)
+}
+
+func (s *ChangeAdaptorSuite) TestNewChanges(c *C) {
+	treeA := &object.Tree{}
+	entryA := object.TreeEntry{Name: "nameA"}
+	pathA := newPath(newNoder(treeA, entryA))
+	changeA := merkletrie.Change{
+		From: nil,
+		To:   pathA,
+	}
+
+	treeB := &object.Tree{}
+	entryB := object.TreeEntry{Name: "nameB"}
+	pathB := newPath(newNoder(treeB, entryB))
+	changeB := merkletrie.Change{
+		From: pathB,
+		To:   nil,
+	}
+	src := merkletrie.Changes{changeA, changeB}
+
+	changes, err := newChanges(src)
+	c.Assert(err, IsNil)
+	c.Assert(len(changes), Equals, 2)
+	action, err := changes[0].Action()
+	c.Assert(err, IsNil)
+	c.Assert(action, Equals, merkletrie.Insert)
+	c.Assert(changes[0].To.Name, Equals, "nameA")
+	action, err = changes[1].Action()
+	c.Assert(err, IsNil)
+	c.Assert(action, Equals, merkletrie.Delete)
+	c.Assert(changes[1].From.Name, Equals, "nameB")
+}
+
+func (s *ChangeAdaptorSuite) TestNewChangesFailsWithOtherNoders(c *C) {
+	change := merkletrie.Change{
+		From: nil,
+		To:   newPath(noderMock{}),
+	}
+	src := merkletrie.Changes{change}
+
+	_, err := newChanges(src)
+	c.Assert(err, Not(IsNil))
+}
+
+func (s *ChangeAdaptorSuite) TestSortChanges(c *C) {
+	c1 := &Change{}
+	c1.To.Name = "1"
+
+	c2 := &Change{}
+	c2.From.Name = "2"
+	c2.To.Name = "2"
+
+	c3 := &Change{}
+	c3.From.Name = "3"
+
+	changes := Changes{c3, c1, c2}
+	sort.Sort(changes)
+
+	c.Assert(changes[0].String(), Equals, "<Action: Insert, Path: 1>")
+	c.Assert(changes[1].String(), Equals, "<Action: Modify, Path: 2>")
+	c.Assert(changes[2].String(), Equals, "<Action: Delete, Path: 3>")
+}
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)
+}
diff --git a/plumbing/difftree/difftree.go b/plumbing/difftree/difftree.go
index 869f496..76c5f27 100644
--- a/plumbing/difftree/difftree.go
+++ b/plumbing/difftree/difftree.go
@@ -2,252 +2,24 @@ package difftree
 
 import (
 	"bytes"
-	"fmt"
-	"io"
-	"sort"
-	"strings"
 
-	"srcd.works/go-git.v4/plumbing"
 	"srcd.works/go-git.v4/plumbing/object"
+	"srcd.works/go-git.v4/utils/merkletrie"
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
 )
 
-type Action int
-
-func (a Action) String() string {
-	switch a {
-	case Insert:
-		return "Insert"
-	case Delete:
-		return "Delete"
-	case Modify:
-		return "Modify"
-	default:
-		panic(fmt.Sprintf("unsupported action: %d", a))
-	}
-}
-
-const (
-	Insert Action = iota
-	Delete
-	Modify
-)
-
-type Change struct {
-	Action
-	From ChangeEntry
-	To   ChangeEntry
-}
-
-type ChangeEntry struct {
-	Name      string
-	Tree      *object.Tree
-	TreeEntry object.TreeEntry
-}
-
-func (c *Change) Files() (from, to *object.File, err error) {
-	if c.Action == Insert || c.Action == Modify {
-		to, err = c.To.Tree.TreeEntryFile(&c.To.TreeEntry)
-		if err != nil {
-			return
-		}
-
-	}
-
-	if c.Action == Delete || c.Action == Modify {
-		from, err = c.From.Tree.TreeEntryFile(&c.From.TreeEntry)
-		if err != nil {
-			return
-		}
-	}
-
-	return
-}
-
-func (c *Change) String() string {
-	return fmt.Sprintf("<Action: %s, Path: %s>", c.Action, c.name())
-}
-
-func (c *Change) name() string {
-	if c.From.Name != "" {
-		return c.From.Name
-	}
-
-	return c.To.Name
-}
-
-type Changes []*Change
-
-func newEmpty() Changes {
-	return make([]*Change, 0, 0)
-}
-
 func DiffTree(a, b *object.Tree) ([]*Change, error) {
-	if a == b {
-		return newEmpty(), nil
-	}
-
-	if a == nil || b == nil {
-		return newWithEmpty(a, b)
-	}
-
-	return newDiffTree(a, b)
-}
-
-func (c Changes) Len() int {
-	return len(c)
-}
-
-func (c Changes) Swap(i, j int) {
-	c[i], c[j] = c[j], c[i]
-}
-
-func (c Changes) Less(i, j int) bool {
-	return strings.Compare(c[i].name(), c[j].name()) < 0
-}
-
-func (c Changes) String() string {
-	var buffer bytes.Buffer
-	buffer.WriteString("[")
-	comma := ""
-	for _, v := range c {
-		buffer.WriteString(comma)
-		buffer.WriteString(v.String())
-		comma = ", "
-	}
-	buffer.WriteString("]")
-
-	return buffer.String()
-}
-
-func newWithEmpty(a, b *object.Tree) (Changes, error) {
-	changes := newEmpty()
-
-	var action Action
-	var tree *object.Tree
-	if a == nil {
-		action = Insert
-		tree = b
-	} else {
-		action = Delete
-		tree = a
-	}
-
-	w := object.NewTreeWalker(tree, true)
-	defer w.Close()
-
-	for {
-		path, entry, err := w.Next()
-		if err == io.EOF {
-			break
-		} else if err != nil {
-			return nil, fmt.Errorf("cannot get next file: %s", err)
-		}
-
-		if entry.Mode.IsDir() {
-			continue
-		}
-
-		c := &Change{Action: action}
-
-		if action == Insert {
-			c.To.Name = path
-			c.To.TreeEntry = entry
-			c.To.Tree = tree
-		} else {
-			c.From.Name = path
-			c.From.TreeEntry = entry
-			c.From.Tree = tree
-		}
-
-		changes = append(changes, c)
-	}
-
-	return changes, nil
-}
-
-// FIXME: this is very inefficient, but correct.
-// The proper way to do this is to implement a diff-tree algorithm,
-// while taking advantage of the tree hashes to avoid traversing
-// subtrees when the hash is equal in both inputs.
-func newDiffTree(a, b *object.Tree) ([]*Change, error) {
-	var result []*Change
-
-	aChanges, err := newWithEmpty(a, nil)
-	if err != nil {
-		return nil, fmt.Errorf("cannot create nil-diff of source tree: %s", err)
-	}
-	sort.Sort(aChanges)
+	from := newTreeNoder(a)
+	to := newTreeNoder(b)
 
-	bChanges, err := newWithEmpty(nil, b)
-	if err != nil {
-		return nil, fmt.Errorf("cannot create nil-diff of destination tree: %s", err)
-	}
-	sort.Sort(bChanges)
-
-	for len(aChanges) > 0 && len(bChanges) > 0 {
-		switch comp := strings.Compare(aChanges[0].name(), bChanges[0].name()); {
-		case comp == 0: // append as "Modify" or ignore if not changed
-			modified, err := hasChange(a, b, aChanges[0].name())
-			if err != nil {
-				return nil, err
-			}
-
-			if modified {
-				c := mergeInsertAndDeleteIntoModify(aChanges[0], bChanges[0])
-				result = append(result, c)
-			}
-
-			aChanges = aChanges[1:]
-			bChanges = bChanges[1:]
-		case comp < 0: // delete first a change
-			result = append(result, aChanges[0])
-			aChanges = aChanges[1:]
-		case comp > 0: // insert first b change
-			result = append(result, bChanges[0])
-			bChanges = bChanges[1:]
-		}
+	hashEqual := func(a, b noder.Hasher) bool {
+		return bytes.Equal(a.Hash(), b.Hash())
 	}
 
-	// append all remaining changes in aChanges, if any, as deletes
-	// append all remaining changes in bChanges, if any, as inserts
-	result = append(result, aChanges...)
-	result = append(result, bChanges...)
-
-	return result, nil
-}
-
-func mergeInsertAndDeleteIntoModify(a, b *Change) *Change {
-	c := &Change{Action: Modify}
-	c.From.Name = a.From.Name
-	c.From.Tree = a.From.Tree
-	c.From.TreeEntry = a.From.TreeEntry
-	c.To.Name = b.To.Name
-	c.To.Tree = b.To.Tree
-	c.To.TreeEntry = b.To.TreeEntry
-
-	return c
-}
-
-func hasChange(a, b *object.Tree, path string) (bool, error) {
-	ha, err := hash(a, path)
-	if err != nil {
-		return false, err
-	}
-
-	hb, err := hash(b, path)
-	if err != nil {
-		return false, err
-	}
-
-	return ha != hb, nil
-}
-
-func hash(tree *object.Tree, path string) (plumbing.Hash, error) {
-	file, err := tree.File(path)
+	merkletrieChanges, err := merkletrie.DiffTree(from, to, hashEqual)
 	if err != nil {
-		var empty plumbing.Hash
-		return empty, fmt.Errorf("cannot find file %s in tree: %s", path, err)
+		return nil, err
 	}
 
-	return file.Hash, nil
+	return newChanges(merkletrieChanges)
 }
diff --git a/plumbing/difftree/difftree_test.go b/plumbing/difftree/difftree_test.go
index 7679d0f..e2519b3 100644
--- a/plumbing/difftree/difftree_test.go
+++ b/plumbing/difftree/difftree_test.go
@@ -4,14 +4,15 @@ import (
 	"sort"
 	"testing"
 
-	"github.com/src-d/go-git-fixtures"
 	"srcd.works/go-git.v4/plumbing"
 	"srcd.works/go-git.v4/plumbing/format/packfile"
 	"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/storage/memory"
+	"srcd.works/go-git.v4/utils/merkletrie"
 
+	"github.com/src-d/go-git-fixtures"
 	. "gopkg.in/check.v1"
 )
 
@@ -33,12 +34,6 @@ func (s *DiffTreeSuite) SetUpSuite(c *C) {
 	s.cache = make(map[string]storer.EncodedObjectStorer)
 }
 
-func (s *DiffTreeSuite) tree(c *C, h plumbing.Hash) *object.Tree {
-	t, err := object.GetTree(s.Storer, h)
-	c.Assert(err, IsNil)
-	return t
-}
-
 func (s *DiffTreeSuite) commitFromStorer(c *C, sto storer.EncodedObjectStorer,
 	h plumbing.Hash) *object.Commit {
 
@@ -76,108 +71,48 @@ func (s *DiffTreeSuite) storageFromPackfile(f *fixtures.Fixture) storer.EncodedO
 
 var _ = Suite(&DiffTreeSuite{})
 
-func (s *DiffTreeSuite) TestActionString(c *C) {
-	expected := "Insert"
-	action := Insert
-	obtained := action.String()
-	c.Assert(obtained, Equals, expected)
-
-	expected = "Delete"
-	action = Delete
-	obtained = action.String()
-	c.Assert(obtained, Equals, expected)
-
-	expected = "Modify"
-	action = Modify
-	obtained = action.String()
-	c.Assert(obtained, Equals, expected)
-
-	action = 37
-	c.Assert(func() { _ = action.String() },
-		PanicMatches, "unsupported action: 37")
-}
-
-func (s *DiffTreeSuite) TestChangeFilesInsert(c *C) {
-	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
-
-	change := &Change{Action: Insert}
-	change.To.Name = "json/long.json"
-	change.To.Tree = tree
-	change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
-
-	from, to, err := change.Files()
-	c.Assert(err, IsNil)
-	c.Assert(from, IsNil)
-	c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
-}
-
-func (s *DiffTreeSuite) TestChangeFilesDelete(c *C) {
-	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
-
-	change := &Change{Action: Delete}
-	change.From.Name = "json/long.json"
-	change.From.Tree = tree
-	change.From.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
-
-	from, to, err := change.Files()
-	c.Assert(err, IsNil)
-	c.Assert(to, IsNil)
-	c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
-}
-
-func (s *DiffTreeSuite) TestChangeFilesModify(c *C) {
-	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
-
-	change := &Change{Action: Modify}
-	change.To.Name = "json/long.json"
-	change.To.Tree = tree
-	change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
-	change.From.Name = "json/long.json"
-	change.From.Tree = tree
-	change.From.TreeEntry.Hash = plumbing.NewHash("9a48f23120e880dfbe41f7c9b7b708e9ee62a492")
-
-	from, to, err := change.Files()
-	c.Assert(err, IsNil)
-	c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
-	c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
+type expectChange struct {
+	Action merkletrie.Action
+	Name   string
 }
 
-func (s *DiffTreeSuite) TestChangeString(c *C) {
-	expected := "<Action: Insert, Path: foo>"
-	change := &Change{Action: Insert}
-	change.From.Name = "foo"
-
-	obtained := change.String()
-	c.Assert(obtained, Equals, expected)
+func assertChanges(a Changes, c *C) {
+	for _, changes := range a {
+		action, err := changes.Action()
+		c.Assert(err, IsNil)
+		switch action {
+		case merkletrie.Insert:
+			c.Assert(changes.From.Tree, IsNil)
+			c.Assert(changes.To.Tree, NotNil)
+		case merkletrie.Delete:
+			c.Assert(changes.From.Tree, NotNil)
+			c.Assert(changes.To.Tree, IsNil)
+		case merkletrie.Modify:
+			c.Assert(changes.From.Tree, NotNil)
+			c.Assert(changes.To.Tree, NotNil)
+		default:
+			c.Fatalf("unknown action: %d", action)
+		}
+	}
 }
 
-func (s *DiffTreeSuite) TestChangesString(c *C) {
-	expected := "[]"
-	changes := newEmpty()
-	obtained := changes.String()
-	c.Assert(obtained, Equals, expected)
-
-	expected = "[<Action: Modify, Path: bla>]"
-	changes = make([]*Change, 1)
-	changes[0] = &Change{Action: Modify}
-	changes[0].From.Name = "bla"
+func equalChanges(a Changes, b []expectChange, c *C) bool {
+	if len(a) != len(b) {
+		return false
+	}
 
-	obtained = changes.String()
-	c.Assert(obtained, Equals, expected)
+	sort.Sort(a)
 
-	expected = "[<Action: Modify, Path: bla>, <Action: Insert, Path: foo/bar>]"
-	changes = make([]*Change, 2)
-	changes[0] = &Change{Action: Modify}
-	changes[0].From.Name = "bla"
-	changes[1] = &Change{Action: Insert}
-	changes[1].From.Name = "foo/bar"
-	obtained = changes.String()
-	c.Assert(obtained, Equals, expected)
-}
+	for i, va := range a {
+		vb := b[i]
+		action, err := va.Action()
+		c.Assert(err, IsNil)
+		if action != vb.Action || va.name() != vb.Name {
+			return false
+		}
+	}
 
-type expectChange struct {
-	Action Action
-	Name   string
+	return true
 }
 
 func (s *DiffTreeSuite) TestDiffTree(c *C) {
@@ -186,186 +121,209 @@ func (s *DiffTreeSuite) TestDiffTree(c *C) {
 		commit1    string         // the commit of the first tree
 		commit2    string         // the commit of the second tree
 		expected   []expectChange // the expected list of []changeExpect
-	}{{
-		"https://github.com/dezfowler/LiteMock.git",
-		"",
-		"",
-		[]expectChange{},
-	}, {
-		"https://github.com/dezfowler/LiteMock.git",
-		"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
-		"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
-		[]expectChange{},
-	}, {
-		"https://github.com/dezfowler/LiteMock.git",
-		"",
-		"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
-		[]expectChange{
-			{Action: Insert, Name: "README"},
+	}{
+		{
+			"https://github.com/dezfowler/LiteMock.git",
+			"",
+			"",
+			[]expectChange{},
+		},
+		{
+			"https://github.com/dezfowler/LiteMock.git",
+			"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+			"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+			[]expectChange{},
+		},
+		{
+			"https://github.com/dezfowler/LiteMock.git",
+			"",
+			"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+			[]expectChange{
+				{Action: merkletrie.Insert, Name: "README"},
+			},
 		},
-	}, {
-		"https://github.com/dezfowler/LiteMock.git",
-		"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
-		"",
-		[]expectChange{
-			{Action: Delete, Name: "README"},
+		{
+			"https://github.com/dezfowler/LiteMock.git",
+			"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+			"",
+			[]expectChange{
+				{Action: merkletrie.Delete, Name: "README"},
+			},
 		},
-	}, {
-		"https://github.com/githubtraining/example-branches.git",
-		"",
-		"f0eb272cc8f77803478c6748103a1450aa1abd37",
-		[]expectChange{
-			{Action: Insert, Name: "README.md"},
+		{
+			"https://github.com/githubtraining/example-branches.git",
+			"",
+			"f0eb272cc8f77803478c6748103a1450aa1abd37",
+			[]expectChange{
+				{Action: merkletrie.Insert, Name: "README.md"},
+			},
 		},
-	}, {
-		"https://github.com/githubtraining/example-branches.git",
-		"f0eb272cc8f77803478c6748103a1450aa1abd37",
-		"",
-		[]expectChange{
-			{Action: Delete, Name: "README.md"},
+		{
+			"https://github.com/githubtraining/example-branches.git",
+			"f0eb272cc8f77803478c6748103a1450aa1abd37",
+			"",
+			[]expectChange{
+				{Action: merkletrie.Delete, Name: "README.md"},
+			},
 		},
-	}, {
-		"https://github.com/githubtraining/example-branches.git",
-		"f0eb272cc8f77803478c6748103a1450aa1abd37",
-		"f0eb272cc8f77803478c6748103a1450aa1abd37",
-		[]expectChange{},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"",
-		"9608eed92b3839b06ebf72d5043da547de10ce85",
-		[]expectChange{
-			{Action: Insert, Name: "README"},
-			{Action: Insert, Name: "gem_builder.rb"},
-			{Action: Insert, Name: "gem_eval.rb"},
+		{
+			"https://github.com/githubtraining/example-branches.git",
+			"f0eb272cc8f77803478c6748103a1450aa1abd37",
+			"f0eb272cc8f77803478c6748103a1450aa1abd37",
+			[]expectChange{},
 		},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"9608eed92b3839b06ebf72d5043da547de10ce85",
-		"",
-		[]expectChange{
-			{Action: Delete, Name: "README"},
-			{Action: Delete, Name: "gem_builder.rb"},
-			{Action: Delete, Name: "gem_eval.rb"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"",
+			"9608eed92b3839b06ebf72d5043da547de10ce85",
+			[]expectChange{
+				{Action: merkletrie.Insert, Name: "README"},
+				{Action: merkletrie.Insert, Name: "gem_builder.rb"},
+				{Action: merkletrie.Insert, Name: "gem_eval.rb"},
+			},
 		},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"9608eed92b3839b06ebf72d5043da547de10ce85",
-		"9608eed92b3839b06ebf72d5043da547de10ce85",
-		[]expectChange{},
-	}, {
-		"https://github.com/toqueteos/ts3.git",
-		"",
-		"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
-		[]expectChange{
-			{Action: Insert, Name: "README.markdown"},
-			{Action: Insert, Name: "examples/bot.go"},
-			{Action: Insert, Name: "examples/raw_shell.go"},
-			{Action: Insert, Name: "helpers.go"},
-			{Action: Insert, Name: "ts3.go"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"9608eed92b3839b06ebf72d5043da547de10ce85",
+			"",
+			[]expectChange{
+				{Action: merkletrie.Delete, Name: "README"},
+				{Action: merkletrie.Delete, Name: "gem_builder.rb"},
+				{Action: merkletrie.Delete, Name: "gem_eval.rb"},
+			},
 		},
-	}, {
-		"https://github.com/toqueteos/ts3.git",
-		"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
-		"",
-		[]expectChange{
-			{Action: Delete, Name: "README.markdown"},
-			{Action: Delete, Name: "examples/bot.go"},
-			{Action: Delete, Name: "examples/raw_shell.go"},
-			{Action: Delete, Name: "helpers.go"},
-			{Action: Delete, Name: "ts3.go"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"9608eed92b3839b06ebf72d5043da547de10ce85",
+			"9608eed92b3839b06ebf72d5043da547de10ce85",
+			[]expectChange{},
 		},
-	}, {
-		"https://github.com/toqueteos/ts3.git",
-		"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
-		"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
-		[]expectChange{},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"9608eed92b3839b06ebf72d5043da547de10ce85",
-		"6c41e05a17e19805879689414026eb4e279f7de0",
-		[]expectChange{
-			{Action: Modify, Name: "gem_eval.rb"},
+		{
+			"https://github.com/toqueteos/ts3.git",
+			"",
+			"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+			[]expectChange{
+				{Action: merkletrie.Insert, Name: "README.markdown"},
+				{Action: merkletrie.Insert, Name: "examples/bot.go"},
+				{Action: merkletrie.Insert, Name: "examples/raw_shell.go"},
+				{Action: merkletrie.Insert, Name: "helpers.go"},
+				{Action: merkletrie.Insert, Name: "ts3.go"},
+			},
 		},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"6c41e05a17e19805879689414026eb4e279f7de0",
-		"89be3aac2f178719c12953cc9eaa23441f8d9371",
-		[]expectChange{
-			{Action: Modify, Name: "gem_eval.rb"},
-			{Action: Insert, Name: "gem_eval_test.rb"},
-			{Action: Insert, Name: "security.rb"},
-			{Action: Insert, Name: "security_test.rb"},
+		{
+			"https://github.com/toqueteos/ts3.git",
+			"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+			"",
+			[]expectChange{
+				{Action: merkletrie.Delete, Name: "README.markdown"},
+				{Action: merkletrie.Delete, Name: "examples/bot.go"},
+				{Action: merkletrie.Delete, Name: "examples/raw_shell.go"},
+				{Action: merkletrie.Delete, Name: "helpers.go"},
+				{Action: merkletrie.Delete, Name: "ts3.go"},
+			},
 		},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"89be3aac2f178719c12953cc9eaa23441f8d9371",
-		"597240b7da22d03ad555328f15abc480b820acc0",
-		[]expectChange{
-			{Action: Modify, Name: "gem_eval.rb"},
+		{
+			"https://github.com/toqueteos/ts3.git",
+			"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+			"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+			[]expectChange{},
 		},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"597240b7da22d03ad555328f15abc480b820acc0",
-		"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
-		[]expectChange{
-			{Action: Modify, Name: "gem_eval.rb"},
-			{Action: Modify, Name: "gem_eval_test.rb"},
-			{Action: Insert, Name: "lazy_dir.rb"},
-			{Action: Insert, Name: "lazy_dir_test.rb"},
-			{Action: Modify, Name: "security.rb"},
-			{Action: Modify, Name: "security_test.rb"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"9608eed92b3839b06ebf72d5043da547de10ce85",
+			"6c41e05a17e19805879689414026eb4e279f7de0",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "gem_eval.rb"},
+			},
 		},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
-		"597240b7da22d03ad555328f15abc480b820acc0",
-		[]expectChange{
-			{Action: Modify, Name: "gem_eval.rb"},
-			{Action: Modify, Name: "gem_eval_test.rb"},
-			{Action: Delete, Name: "lazy_dir.rb"},
-			{Action: Delete, Name: "lazy_dir_test.rb"},
-			{Action: Modify, Name: "security.rb"},
-			{Action: Modify, Name: "security_test.rb"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"6c41e05a17e19805879689414026eb4e279f7de0",
+			"89be3aac2f178719c12953cc9eaa23441f8d9371",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "gem_eval.rb"},
+				{Action: merkletrie.Insert, Name: "gem_eval_test.rb"},
+				{Action: merkletrie.Insert, Name: "security.rb"},
+				{Action: merkletrie.Insert, Name: "security_test.rb"},
+			},
 		},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
-		"ca9fd470bacb6262eb4ca23ee48bb2f43711c1ff",
-		[]expectChange{
-			{Action: Modify, Name: "gem_eval.rb"},
-			{Action: Modify, Name: "security.rb"},
-			{Action: Modify, Name: "security_test.rb"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"89be3aac2f178719c12953cc9eaa23441f8d9371",
+			"597240b7da22d03ad555328f15abc480b820acc0",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "gem_eval.rb"},
+			},
 		},
-	}, {
-		"https://github.com/github/gem-builder.git",
-		"fe3c86745f887c23a0d38c85cfd87ca957312f86",
-		"b7e3f636febf7a0cd3ab473b6d30081786d2c5b6",
-		[]expectChange{
-			{Action: Modify, Name: "gem_eval.rb"},
-			{Action: Modify, Name: "gem_eval_test.rb"},
-			{Action: Insert, Name: "git_mock"},
-			{Action: Modify, Name: "lazy_dir.rb"},
-			{Action: Modify, Name: "lazy_dir_test.rb"},
-			{Action: Modify, Name: "security.rb"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"597240b7da22d03ad555328f15abc480b820acc0",
+			"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "gem_eval.rb"},
+				{Action: merkletrie.Modify, Name: "gem_eval_test.rb"},
+				{Action: merkletrie.Insert, Name: "lazy_dir.rb"},
+				{Action: merkletrie.Insert, Name: "lazy_dir_test.rb"},
+				{Action: merkletrie.Modify, Name: "security.rb"},
+				{Action: merkletrie.Modify, Name: "security_test.rb"},
+			},
 		},
-	}, {
-		"https://github.com/rumpkernel/rumprun-xen.git",
-		"1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
-		"51d8515578ea0c88cc8fc1a057903675cf1fc16c",
-		[]expectChange{
-			{Action: Modify, Name: "Makefile"},
-			{Action: Modify, Name: "netbsd_init.c"},
-			{Action: Modify, Name: "rumphyper_stubs.c"},
-			{Action: Delete, Name: "sysproxy.c"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+			"597240b7da22d03ad555328f15abc480b820acc0",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "gem_eval.rb"},
+				{Action: merkletrie.Modify, Name: "gem_eval_test.rb"},
+				{Action: merkletrie.Delete, Name: "lazy_dir.rb"},
+				{Action: merkletrie.Delete, Name: "lazy_dir_test.rb"},
+				{Action: merkletrie.Modify, Name: "security.rb"},
+				{Action: merkletrie.Modify, Name: "security_test.rb"},
+			},
 		},
-	}, {
-		"https://github.com/rumpkernel/rumprun-xen.git",
-		"1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
-		"e13e678f7ee9badd01b120889e0ec5fdc8ae3802",
-		[]expectChange{
-			{Action: Modify, Name: "app-tools/rumprun"},
+		{
+			"https://github.com/github/gem-builder.git",
+			"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+			"ca9fd470bacb6262eb4ca23ee48bb2f43711c1ff",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "gem_eval.rb"},
+				{Action: merkletrie.Modify, Name: "security.rb"},
+				{Action: merkletrie.Modify, Name: "security_test.rb"},
+			},
 		},
-	}} {
+		{
+			"https://github.com/github/gem-builder.git",
+			"fe3c86745f887c23a0d38c85cfd87ca957312f86",
+			"b7e3f636febf7a0cd3ab473b6d30081786d2c5b6",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "gem_eval.rb"},
+				{Action: merkletrie.Modify, Name: "gem_eval_test.rb"},
+				{Action: merkletrie.Insert, Name: "git_mock"},
+				{Action: merkletrie.Modify, Name: "lazy_dir.rb"},
+				{Action: merkletrie.Modify, Name: "lazy_dir_test.rb"},
+				{Action: merkletrie.Modify, Name: "security.rb"},
+			},
+		},
+		{
+			"https://github.com/rumpkernel/rumprun-xen.git",
+			"1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
+			"51d8515578ea0c88cc8fc1a057903675cf1fc16c",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "Makefile"},
+				{Action: merkletrie.Modify, Name: "netbsd_init.c"},
+				{Action: merkletrie.Modify, Name: "rumphyper_stubs.c"},
+				{Action: merkletrie.Delete, Name: "sysproxy.c"},
+			},
+		},
+		{
+			"https://github.com/rumpkernel/rumprun-xen.git",
+			"1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
+			"e13e678f7ee9badd01b120889e0ec5fdc8ae3802",
+			[]expectChange{
+				{Action: merkletrie.Modify, Name: "app-tools/rumprun"},
+			},
+		},
+	} {
 		f := fixtures.ByURL(t.repository).One()
 		sto := s.storageFromPackfile(f)
 
@@ -388,43 +346,10 @@ func (s *DiffTreeSuite) TestDiffTree(c *C) {
 		obtained, err := DiffTree(tree1, tree2)
 		c.Assert(err, IsNil,
 			Commentf("subtest %d: unable to calculate difftree: %s", i, err))
-		c.Assert(equalChanges(obtained, t.expected), Equals, true,
+		c.Assert(equalChanges(obtained, t.expected, c), Equals, true,
 			Commentf("subtest:%d\nrepo=%s\ncommit1=%s\ncommit2=%s\nexpected=%s\nobtained=%s",
 				i, t.repository, t.commit1, t.commit2, t.expected, obtained))
 
 		assertChanges(obtained, c)
 	}
 }
-
-func assertChanges(a Changes, c *C) {
-	for _, changes := range a {
-		switch changes.Action {
-		case Insert:
-			c.Assert(changes.From.Tree, IsNil)
-			c.Assert(changes.To.Tree, NotNil)
-		case Delete:
-			c.Assert(changes.From.Tree, NotNil)
-			c.Assert(changes.To.Tree, IsNil)
-		case Modify:
-			c.Assert(changes.From.Tree, NotNil)
-			c.Assert(changes.To.Tree, NotNil)
-		}
-	}
-}
-
-func equalChanges(a Changes, b []expectChange) bool {
-	if len(a) != len(b) {
-		return false
-	}
-
-	sort.Sort(a)
-
-	for i, va := range a {
-		vb := b[i]
-		if va.Action != vb.Action || va.name() != vb.Name {
-			return false
-		}
-	}
-
-	return true
-}
diff --git a/plumbing/difftree/treenoder.go b/plumbing/difftree/treenoder.go
new file mode 100644
index 0000000..c0ed948
--- /dev/null
+++ b/plumbing/difftree/treenoder.go
@@ -0,0 +1,141 @@
+package difftree
+
+// A treenoder is a helper type that wraps git trees into merkletrie
+// noders.
+//
+// As a merkletrie noder doesn't understand the concept of modes (e.g.
+// file permissions), the treenoder includes the mode of the git tree in
+// the hash, so changes in the modes will be detected as modifications
+// to the file contents by the merkletrie difftree algorithm.  This is
+// consistent with how the "git diff-tree" command works.
+import (
+	"encoding/binary"
+	"io"
+	"os"
+
+	"srcd.works/go-git.v4/plumbing"
+	"srcd.works/go-git.v4/plumbing/object"
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+type treeNoder struct {
+	parent   *object.Tree // the root node is its own parent
+	name     string       // empty string for the root node
+	mode     os.FileMode
+	hash     plumbing.Hash
+	children []noder.Noder // memoized
+}
+
+func newTreeNoder(t *object.Tree) *treeNoder {
+	if t == nil {
+		return &treeNoder{}
+	}
+
+	return &treeNoder{
+		parent: t,
+		name:   "",
+		mode:   os.ModeDir,
+		hash:   t.Hash,
+	}
+}
+
+func (t *treeNoder) isRoot() bool {
+	return t.name == ""
+}
+
+func (t *treeNoder) String() string {
+	return "treeNoder <" + t.name + ">"
+}
+
+func (t *treeNoder) Hash() []byte {
+	return append(t.hash[:], modeToBytes(t.mode)...)
+}
+
+// mode in little endian (endianess is an arbitrary decission).
+func modeToBytes(m os.FileMode) []byte {
+	ret := make([]byte, 4)
+	binary.LittleEndian.PutUint32(ret, uint32(m))
+	return ret
+}
+
+func (t *treeNoder) Name() string {
+	return t.name
+}
+
+func (t *treeNoder) IsDir() bool {
+	return t.mode.IsDir()
+}
+
+// Children will return the children of a treenoder as treenoders,
+// building them from the children of the wrapped git tree.
+func (t *treeNoder) Children() ([]noder.Noder, error) {
+	if !t.mode.IsDir() {
+		return noder.NoChildren, nil
+	}
+
+	// children are memoized for efficiency
+	if t.children != nil {
+		return t.children, nil
+	}
+
+	// the parent of the returned children will be ourself as a tree if
+	// we are a not the root treenoder.  The root is special as it
+	// is is own parent.
+	parent := t.parent
+	if !t.isRoot() {
+		var err error
+		if parent, err = t.parent.Tree(t.name); err != nil {
+			return nil, err
+		}
+	}
+
+	return transformChildren(parent)
+}
+
+// Returns the children of a tree as treenoders.
+// Efficiency is key here.
+func transformChildren(t *object.Tree) ([]noder.Noder, error) {
+	var err error
+	var e object.TreeEntry
+
+	// there will be more tree entries than children in the tree,
+	// due to submodules and empty directories, but I think it is still
+	// worth it to pre-allocate the whole array now, even if sometimes
+	// is bigger than needed.
+	ret := make([]noder.Noder, 0, len(t.Entries))
+
+	walker := object.NewTreeWalker(t, false) // don't recurse
+	// don't defer walker.Close() for efficiency reasons.
+	for {
+		_, e, err = walker.Next()
+		if err == io.EOF {
+			break
+		}
+		if err != nil {
+			walker.Close()
+			return nil, err
+		}
+
+		ret = append(ret, &treeNoder{
+			parent: t,
+			name:   e.Name,
+			mode:   e.Mode,
+			hash:   e.Hash,
+		})
+	}
+	walker.Close()
+
+	return ret, nil
+}
+
+// len(t.tree.Entries) != the number of elements walked by treewalker
+// for some reason because of empty directories, submodules, etc, so we
+// have to walk here.
+func (t *treeNoder) NumChildren() (int, error) {
+	children, err := t.Children()
+	if err != nil {
+		return 0, err
+	}
+
+	return len(children), nil
+}