2 files changed, 255 insertions, 0 deletions
diff --git a/utils/merkletrie/filesystem/node.go b/utils/merkletrie/filesystem/node.go
new file mode 100644
index 0000000..847d71e
--- /dev/null
+++ b/utils/merkletrie/filesystem/node.go
@@ -0,0 +1,128 @@
+package filesystem
+
+import (
+	"bytes"
+	"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,
+}
+
+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 {
+	parent string
+	name   string
+	isDir  bool
+	info   billy.FileInfo
+	fs     billy.Filesystem
+}
+
+func NewRootNode(fs billy.Filesystem) (*Node, error) {
+	info, err := fs.Stat("/")
+	if err != nil && !os.IsNotExist(err) {
+		return nil, err
+	}
+
+	return &Node{fs: fs, info: info, isDir: true, name: ""}, nil
+}
+
+func (n *Node) String() string {
+	return filepath.Join(n.parent, n.name)
+}
+
+func (n *Node) Hash() []byte {
+	if n.IsDir() {
+		return nil
+	}
+
+	f, err := n.fs.Open(n.fullpath())
+	if err != nil {
+		panic(err)
+	}
+
+	h := plumbing.NewHasher(plumbing.BlobObject, n.info.Size())
+	if _, err := io.Copy(h, f); err != nil {
+		panic(err)
+	}
+
+	hash := h.Sum()
+	mode, err := filemode.NewFromOSFileMode(n.info.Mode())
+	if err != nil {
+		panic(err)
+	}
+
+	return append(hash[:], 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) {
+	files, err := n.readDir()
+
+	if err != nil {
+		return nil, err
+	}
+
+	path := n.fullpath()
+	var c []noder.Noder
+	for _, file := range files {
+		if _, ok := ignore[file.Name()]; ok {
+			continue
+		}
+
+		c = append(c, &Node{
+			fs:     n.fs,
+			parent: path,
+			info:   file,
+			name:   file.Name(),
+			isDir:  file.IsDir(),
+		})
+	}
+
+	return c, nil
+}
+
+func (n *Node) NumChildren() (int, error) {
+	files, err := n.readDir()
+	return len(files), err
+}
+
+func (n *Node) fullpath() string {
+	return filepath.Join(n.parent, n.name)
+}
+
+func (n *Node) readDir() ([]billy.FileInfo, error) {
+	if !n.IsDir() {
+		return nil, nil
+	}
+
+	l, err := n.fs.ReadDir(n.fullpath())
+	if err != nil && os.IsNotExist(err) {
+		return l, nil
+	}
+
+	return l, err
+}
diff --git a/utils/merkletrie/filesystem/node_test.go b/utils/merkletrie/filesystem/node_test.go
new file mode 100644
index 0000000..291af6b
--- /dev/null
+++ b/utils/merkletrie/filesystem/node_test.go
@@ -0,0 +1,127 @@
+package filesystem
+
+import (
+	"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"
+)
+
+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)
+
+	nodeA, err := NewRootNode(fsA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(fsB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, 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)
+
+	nodeA, err := NewRootNode(fsA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(fsB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, 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)
+
+	nodeA, err := NewRootNode(fsA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(fsB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, 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)
+
+	nodeA, err := NewRootNode(fsA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(fsB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, 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)
+
+	nodeA, err := NewRootNode(fsA)
+	c.Assert(err, IsNil)
+	nodeB, err := NewRootNode(fsB)
+	c.Assert(err, IsNil)
+
+	ch, err := merkletrie.DiffTree(nodeA, nodeB, 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
+}