rebase master

5 files changed, 1036 insertions, 0 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/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
+}