2 files changed, 229 insertions, 0 deletions
diff --git a/utils/merkletrie/index/node.go b/utils/merkletrie/index/node.go
new file mode 100644
index 0000000..7972f7f
--- /dev/null
+++ b/utils/merkletrie/index/node.go
@@ -0,0 +1,113 @@
+package index
+
+import (
+	"bytes"
+	"path/filepath"
+
+	"strings"
+
+	"gopkg.in/src-d/go-git.v4/plumbing/format/index"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+func IsEquals(a, b noder.Hasher) bool {
+	pathA := a.(noder.Path)
+	pathB := b.(noder.Path)
+	if pathA[len(pathA)-1].IsDir() || pathB[len(pathB)-1].IsDir() {
+		return false
+	}
+
+	return bytes.Equal(a.Hash(), b.Hash())
+}
+
+type Node struct {
+	index  *index.Index
+	parent string
+	name   string
+	entry  index.Entry
+	isDir  bool
+}
+
+func NewRootNode(idx *index.Index) (*Node, error) {
+	return &Node{index: idx, isDir: true}, nil
+}
+
+func (n *Node) String() string {
+	return n.fullpath()
+}
+
+func (n *Node) Hash() []byte {
+	if n.IsDir() {
+		return nil
+	}
+
+	return append(n.entry.Hash[:], n.entry.Mode.Bytes()...)
+}
+
+func (n *Node) Name() string {
+	return n.name
+}
+
+func (n *Node) IsDir() bool {
+	return n.isDir
+}
+
+func (n *Node) Children() ([]noder.Noder, error) {
+	path := n.fullpath()
+	dirs := make(map[string]bool)
+
+	var c []noder.Noder
+	for _, e := range n.index.Entries {
+		if e.Name == path {
+			continue
+		}
+
+		prefix := path
+		if prefix != "" {
+			prefix += "/"
+		}
+
+		if !strings.HasPrefix(e.Name, prefix) {
+			continue
+		}
+
+		name := e.Name[len(path):]
+		if len(name) != 0 && name[0] == '/' {
+			name = name[1:]
+		}
+
+		parts := strings.Split(name, "/")
+		if len(parts) > 1 {
+			dirs[parts[0]] = true
+			continue
+		}
+
+		c = append(c, &Node{
+			index:  n.index,
+			parent: path,
+			name:   name,
+			entry:  e,
+		})
+	}
+
+	for dir := range dirs {
+		c = append(c, &Node{
+			index:  n.index,
+			parent: path,
+			name:   dir,
+			isDir:  true,
+		})
+
+	}
+
+	return c, nil
+}
+
+func (n *Node) NumChildren() (int, error) {
+	files, err := n.Children()
+	return len(files), err
+}
+
+func (n *Node) fullpath() string {
+	return filepath.Join(n.parent, n.name)
+}
diff --git a/utils/merkletrie/index/node_test.go b/utils/merkletrie/index/node_test.go
new file mode 100644
index 0000000..0ee0884
--- /dev/null
+++ b/utils/merkletrie/index/node_test.go
@@ -0,0 +1,116 @@
+package index
+
+import (
+	"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"
+)
+
+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")},
+		},
+	}
+
+	nodeA, err := NewRootNode(indexA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(indexB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, 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")},
+		},
+	}
+
+	nodeA, err := NewRootNode(indexA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(indexB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, 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")},
+		},
+	}
+
+	nodeA, err := NewRootNode(indexA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(indexB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, 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")},
+		},
+	}
+
+	nodeA, err := NewRootNode(indexA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(indexB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, IsEquals)
+	c.Assert(err, IsNil)
+	c.Assert(ch, HasLen, 1)
+}