4 files changed, 452 insertions, 0 deletions
diff --git a/utils/merkletrie/filesystem/node.go b/utils/merkletrie/filesystem/node.go
new file mode 100644
index 0000000..6c09d29
--- /dev/null
+++ b/utils/merkletrie/filesystem/node.go
@@ -0,0 +1,144 @@
+package filesystem
+
+import (
+	"io"
+	"os"
+	"path/filepath"
+
+	"gopkg.in/src-d/go-billy.v2"
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/filemode"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+var ignore = map[string]bool{
+	".git": true,
+}
+
+// The node represents a file or a directory in a billy.Filesystem. It
+// implements the interface noder.Noder of merkletrie package.
+//
+// This implementation implements a "standard" hash method being able to be
+// compared with any other noder.Noder implementation inside of go-git.
+type node struct {
+	fs billy.Filesystem
+
+	path     string
+	hash     []byte
+	children []noder.Noder
+	isDir    bool
+}
+
+// NewRootNode returns the root node based on a given billy.Filesystem
+func NewRootNode(fs billy.Filesystem) noder.Noder {
+	return &node{fs: fs, isDir: true}
+}
+
+// Hash the hash of a filesystem is the result of concatenating the computed
+// plumbing.Hash of the file as a Blob and its plumbing.FileMode; that way the
+// difftree algorithm will detect changes in the contents of files and also in
+// their mode.
+//
+// The hash of a directory is always a 24-bytes slice of zero values
+func (n *node) Hash() []byte {
+	return n.hash
+}
+
+func (n *node) Name() string {
+	return filepath.Base(n.path)
+}
+
+func (n *node) IsDir() bool {
+	return n.isDir
+}
+
+func (n *node) Children() ([]noder.Noder, error) {
+	if err := n.calculateChildren(); err != nil {
+		return nil, err
+	}
+
+	return n.children, nil
+}
+
+func (n *node) NumChildren() (int, error) {
+	if err := n.calculateChildren(); err != nil {
+		return -1, err
+	}
+
+	return len(n.children), nil
+}
+
+func (n *node) calculateChildren() error {
+	if len(n.children) != 0 {
+		return nil
+	}
+
+	files, err := n.fs.ReadDir(n.path)
+	if err != nil {
+		if os.IsNotExist(err) {
+			return nil
+		}
+
+		return nil
+	}
+
+	for _, file := range files {
+		if _, ok := ignore[file.Name()]; ok {
+			continue
+		}
+
+		c, err := n.newChildNode(file)
+		if err != nil {
+			return err
+		}
+
+		n.children = append(n.children, c)
+	}
+
+	return nil
+}
+
+func (n *node) newChildNode(file billy.FileInfo) (*node, error) {
+	path := filepath.Join(n.path, file.Name())
+	hash, err := n.calculateHash(path, file)
+	if err != nil {
+		return nil, err
+	}
+
+	return &node{
+		fs:    n.fs,
+		path:  path,
+		hash:  hash,
+		isDir: file.IsDir(),
+	}, nil
+}
+
+func (n *node) calculateHash(path string, file billy.FileInfo) ([]byte, error) {
+	if file.IsDir() {
+		return make([]byte, 24), nil
+	}
+
+	f, err := n.fs.Open(path)
+	if err != nil {
+		return nil, err
+	}
+
+	defer f.Close()
+
+	h := plumbing.NewHasher(plumbing.BlobObject, file.Size())
+	if _, err := io.Copy(h, f); err != nil {
+		return nil, err
+	}
+
+	mode, err := filemode.NewFromOSFileMode(file.Mode())
+	if err != nil {
+		return nil, err
+	}
+
+	hash := h.Sum()
+	return append(hash[:], mode.Bytes()...), nil
+}
+
+func (n *node) String() string {
+	return n.path
+}
diff --git a/utils/merkletrie/filesystem/node_test.go b/utils/merkletrie/filesystem/node_test.go
new file mode 100644
index 0000000..b7c124d
--- /dev/null
+++ b/utils/merkletrie/filesystem/node_test.go
@@ -0,0 +1,114 @@
+package filesystem
+
+import (
+	"bytes"
+	"io"
+	"os"
+	"testing"
+
+	. "gopkg.in/check.v1"
+	"gopkg.in/src-d/go-billy.v2"
+	"gopkg.in/src-d/go-billy.v2/memfs"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type NoderSuite struct{}
+
+var _ = Suite(&NoderSuite{})
+
+func (s *NoderSuite) TestDiff(c *C) {
+	fsA := memfs.New()
+	WriteFile(fsA, "foo", []byte("foo"), 0644)
+	WriteFile(fsA, "qux/bar", []byte("foo"), 0644)
+	WriteFile(fsA, "qux/qux", []byte("foo"), 0644)
+
+	fsB := memfs.New()
+	WriteFile(fsB, "foo", []byte("foo"), 0644)
+	WriteFile(fsB, "qux/bar", []byte("foo"), 0644)
+	WriteFile(fsB, "qux/qux", []byte("foo"), 0644)
+
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 0)
+}
+
+func (s *NoderSuite) TestDiffChangeContent(c *C) {
+	fsA := memfs.New()
+	WriteFile(fsA, "foo", []byte("foo"), 0644)
+	WriteFile(fsA, "qux/bar", []byte("foo"), 0644)
+	WriteFile(fsA, "qux/qux", []byte("foo"), 0644)
+
+	fsB := memfs.New()
+	WriteFile(fsB, "foo", []byte("foo"), 0644)
+	WriteFile(fsB, "qux/bar", []byte("bar"), 0644)
+	WriteFile(fsB, "qux/qux", []byte("foo"), 0644)
+
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 1)
+}
+
+func (s *NoderSuite) TestDiffChangeMissing(c *C) {
+	fsA := memfs.New()
+	WriteFile(fsA, "foo", []byte("foo"), 0644)
+
+	fsB := memfs.New()
+	WriteFile(fsB, "bar", []byte("bar"), 0644)
+
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 2)
+}
+
+func (s *NoderSuite) TestDiffChangeMode(c *C) {
+	fsA := memfs.New()
+	WriteFile(fsA, "foo", []byte("foo"), 0644)
+
+	fsB := memfs.New()
+	WriteFile(fsB, "foo", []byte("foo"), 0755)
+
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 1)
+}
+
+func (s *NoderSuite) TestDiffChangeModeNotRelevant(c *C) {
+	fsA := memfs.New()
+	WriteFile(fsA, "foo", []byte("foo"), 0644)
+
+	fsB := memfs.New()
+	WriteFile(fsB, "foo", []byte("foo"), 0655)
+
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 0)
+}
+
+func WriteFile(fs billy.Filesystem, filename string, data []byte, perm os.FileMode) error {
+	f, err := fs.OpenFile(filename, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, perm)
+	if err != nil {
+		return err
+	}
+
+	n, err := f.Write(data)
+	if err == nil && n < len(data) {
+		err = io.ErrShortWrite
+	}
+	if err1 := f.Close(); err == nil {
+		err = err1
+	}
+	return err
+}
+
+var empty = make([]byte, 24)
+
+func IsEquals(a, b noder.Hasher) bool {
+	if bytes.Equal(a.Hash(), empty) || bytes.Equal(b.Hash(), empty) {
+		return false
+	}
+
+	return bytes.Equal(a.Hash(), b.Hash())
+}
diff --git a/utils/merkletrie/index/node.go b/utils/merkletrie/index/node.go
new file mode 100644
index 0000000..2c72f6d
--- /dev/null
+++ b/utils/merkletrie/index/node.go
@@ -0,0 +1,86 @@
+package index
+
+import (
+	"path/filepath"
+	"strings"
+
+	"gopkg.in/src-d/go-git.v4/plumbing/format/index"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// The node represents a index.Entry or a directory inferred from the path
+// of all entries. It implements the interface noder.Noder of merkletrie
+// package.
+//
+// This implementation implements a "standard" hash method being able to be
+// compared with any other noder.Noder implementation inside of go-git
+type node struct {
+	path     string
+	entry    index.Entry
+	children []noder.Noder
+	isDir    bool
+}
+
+// NewRootNode returns the root node of a computed tree from a index.Index,
+func NewRootNode(idx *index.Index) noder.Noder {
+	const rootNode = ""
+
+	m := map[string]*node{rootNode: {isDir: true}}
+
+	for _, e := range idx.Entries {
+		parts := strings.Split(e.Name, string(filepath.Separator))
+
+		var path string
+		for _, part := range parts {
+			parent := path
+			path = filepath.Join(path, part)
+
+			if _, ok := m[path]; ok {
+				continue
+			}
+
+			n := &node{path: path}
+			if path == e.Name {
+				n.entry = e
+			} else {
+				n.isDir = true
+			}
+
+			m[n.path] = n
+			m[parent].children = append(m[parent].children, n)
+		}
+	}
+
+	return m[rootNode]
+}
+
+func (n *node) String() string {
+	return n.path
+}
+
+// Hash the hash of a filesystem is a 24-byte slice, is the result of
+// concatenating the computed plumbing.Hash of the file as a Blob and its
+// plumbing.FileMode; that way the difftree algorithm will detect changes in the
+// contents of files and also in their mode.
+//
+// If the node is computed and not based on a index.Entry the hash is equals
+// to a 24-bytes slices of zero values.
+func (n *node) Hash() []byte {
+	return append(n.entry.Hash[:], n.entry.Mode.Bytes()...)
+}
+
+func (n *node) Name() string {
+	return filepath.Base(n.path)
+}
+
+func (n *node) IsDir() bool {
+	return n.isDir
+}
+
+func (n *node) Children() ([]noder.Noder, error) {
+	return n.children, nil
+}
+
+func (n *node) NumChildren() (int, error) {
+	return len(n.children), nil
+}
diff --git a/utils/merkletrie/index/node_test.go b/utils/merkletrie/index/node_test.go
new file mode 100644
index 0000000..48aa35f
--- /dev/null
+++ b/utils/merkletrie/index/node_test.go
@@ -0,0 +1,108 @@
+package index
+
+import (
+	"bytes"
+	"testing"
+
+	. "gopkg.in/check.v1"
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/format/index"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type NoderSuite struct{}
+
+var _ = Suite(&NoderSuite{})
+
+func (s *NoderSuite) TestDiff(c *C) {
+	indexA := &index.Index{
+		Entries: []index.Entry{
+			{Name: "foo", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+			{Name: "bar/foo", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+			{Name: "bar/qux", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+			{Name: "bar/baz/foo", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+		},
+	}
+
+	indexB := &index.Index{
+		Entries: []index.Entry{
+			{Name: "foo", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+			{Name: "bar/foo", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+			{Name: "bar/qux", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+			{Name: "bar/baz/foo", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+		},
+	}
+
+	ch, err := merkletrie.DiffTree(NewRootNode(indexA), NewRootNode(indexB), isEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 0)
+}
+
+func (s *NoderSuite) TestDiffChange(c *C) {
+	indexA := &index.Index{
+		Entries: []index.Entry{
+			{Name: "bar/baz/bar", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+		},
+	}
+
+	indexB := &index.Index{
+		Entries: []index.Entry{
+			{Name: "bar/baz/foo", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+		},
+	}
+
+	ch, err := merkletrie.DiffTree(NewRootNode(indexA), NewRootNode(indexB), isEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 2)
+}
+
+func (s *NoderSuite) TestDiffDir(c *C) {
+	indexA := &index.Index{
+		Entries: []index.Entry{
+			{Name: "foo", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+		},
+	}
+
+	indexB := &index.Index{
+		Entries: []index.Entry{
+			{Name: "foo/bar", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+		},
+	}
+
+	ch, err := merkletrie.DiffTree(NewRootNode(indexA), NewRootNode(indexB), isEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 2)
+}
+
+func (s *NoderSuite) TestDiffSameRoot(c *C) {
+	indexA := &index.Index{
+		Entries: []index.Entry{
+			{Name: "foo.go", Hash: plumbing.NewHash("aab686eafeb1f44702738c8b0f24f2567c36da6d")},
+			{Name: "foo/bar", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+		},
+	}
+
+	indexB := &index.Index{
+		Entries: []index.Entry{
+			{Name: "foo/bar", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+			{Name: "foo.go", Hash: plumbing.NewHash("8ab686eafeb1f44702738c8b0f24f2567c36da6d")},
+		},
+	}
+
+	ch, err := merkletrie.DiffTree(NewRootNode(indexA), NewRootNode(indexB), isEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 1)
+}
+
+var empty = make([]byte, 24)
+
+func isEquals(a, b noder.Hasher) bool {
+	if bytes.Equal(a.Hash(), empty) || bytes.Equal(b.Hash(), empty) {
+		return false
+	}
+
+	return bytes.Equal(a.Hash(), b.Hash())
+}