merkletrie: filesystem and index speedup and documentation

2 files changed, 106 insertions, 103 deletions

diff --git a/utils/merkletrie/filesystem/node.go b/utils/merkletrie/filesystem/node.go
index 847d71e..6c09d29 100644
--- a/utils/merkletrie/filesystem/node.go
+++ b/utils/merkletrie/filesystem/node.go
@@ -1,7 +1,6 @@
 package filesystem
 
 import (
-	"bytes"
 	"io"
 	"os"
 	"path/filepath"
@@ -16,113 +15,130 @@ 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
-	}
+// 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
+}
 
-	return bytes.Equal(a.Hash(), b.Hash())
+func (n *node) Name() string {
+	return filepath.Base(n.path)
 }
 
-type Node struct {
-	parent string
-	name   string
-	isDir  bool
-	info   billy.FileInfo
-	fs     billy.Filesystem
+func (n *node) IsDir() bool {
+	return n.isDir
 }
 
-func NewRootNode(fs billy.Filesystem) (*Node, error) {
-	info, err := fs.Stat("/")
-	if err != nil && !os.IsNotExist(err) {
+func (n *node) Children() ([]noder.Noder, error) {
+	if err := n.calculateChildren(); err != nil {
 		return nil, err
 	}
 
-	return &Node{fs: fs, info: info, isDir: true, name: ""}, nil
+	return n.children, nil
 }
 
-func (n *Node) String() string {
-	return filepath.Join(n.parent, n.name)
+func (n *node) NumChildren() (int, error) {
+	if err := n.calculateChildren(); err != nil {
+		return -1, err
+	}
+
+	return len(n.children), nil
 }
 
-func (n *Node) Hash() []byte {
-	if n.IsDir() {
+func (n *node) calculateChildren() error {
+	if len(n.children) != 0 {
 		return nil
 	}
 
-	f, err := n.fs.Open(n.fullpath())
+	files, err := n.fs.ReadDir(n.path)
 	if err != nil {
-		panic(err)
-	}
+		if os.IsNotExist(err) {
+			return nil
+		}
 
-	h := plumbing.NewHasher(plumbing.BlobObject, n.info.Size())
-	if _, err := io.Copy(h, f); err != nil {
-		panic(err)
+		return nil
 	}
 
-	hash := h.Sum()
-	mode, err := filemode.NewFromOSFileMode(n.info.Mode())
-	if err != nil {
-		panic(err)
-	}
+	for _, file := range files {
+		if _, ok := ignore[file.Name()]; ok {
+			continue
+		}
 
-	return append(hash[:], mode.Bytes()...)
-}
+		c, err := n.newChildNode(file)
+		if err != nil {
+			return err
+		}
 
-func (n *Node) Name() string {
-	return n.name
-}
+		n.children = append(n.children, c)
+	}
 
-func (n *Node) IsDir() bool {
-	return n.isDir
+	return nil
 }
 
-func (n *Node) Children() ([]noder.Noder, error) {
-	files, err := n.readDir()
-
+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
 	}
 
-	path := n.fullpath()
-	var c []noder.Noder
-	for _, file := range files {
-		if _, ok := ignore[file.Name()]; ok {
-			continue
-		}
+	return &node{
+		fs:    n.fs,
+		path:  path,
+		hash:  hash,
+		isDir: file.IsDir(),
+	}, nil
+}
 
-		c = append(c, &Node{
-			fs:     n.fs,
-			parent: path,
-			info:   file,
-			name:   file.Name(),
-			isDir:  file.IsDir(),
-		})
+func (n *node) calculateHash(path string, file billy.FileInfo) ([]byte, error) {
+	if file.IsDir() {
+		return make([]byte, 24), nil
 	}
 
-	return c, nil
-}
-
-func (n *Node) NumChildren() (int, error) {
-	files, err := n.readDir()
-	return len(files), err
-}
+	f, err := n.fs.Open(path)
+	if err != nil {
+		return nil, err
+	}
 
-func (n *Node) fullpath() string {
-	return filepath.Join(n.parent, n.name)
-}
+	defer f.Close()
 
-func (n *Node) readDir() ([]billy.FileInfo, error) {
-	if !n.IsDir() {
-		return nil, nil
+	h := plumbing.NewHasher(plumbing.BlobObject, file.Size())
+	if _, err := io.Copy(h, f); err != nil {
+		return nil, err
 	}
 
-	l, err := n.fs.ReadDir(n.fullpath())
-	if err != nil && os.IsNotExist(err) {
-		return l, nil
+	mode, err := filemode.NewFromOSFileMode(file.Mode())
+	if err != nil {
+		return nil, err
 	}
 
-	return l, 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
index 291af6b..b7c124d 100644
--- a/utils/merkletrie/filesystem/node_test.go
+++ b/utils/merkletrie/filesystem/node_test.go
@@ -1,6 +1,7 @@
 package filesystem
 
 import (
+	"bytes"
 	"io"
 	"os"
 	"testing"
@@ -9,6 +10,7 @@ import (
 	"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) }
@@ -28,12 +30,7 @@ func (s *NoderSuite) TestDiff(c *C) {
 	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)
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
 	c.Assert(err, IsNil)
 	c.Assert(ch, HasLen, 0)
 }
@@ -49,12 +46,7 @@ func (s *NoderSuite) TestDiffChangeContent(c *C) {
 	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)
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
 	c.Assert(err, IsNil)
 	c.Assert(ch, HasLen, 1)
 }
@@ -66,12 +58,7 @@ func (s *NoderSuite) TestDiffChangeMissing(c *C) {
 	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)
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
 	c.Assert(err, IsNil)
 	c.Assert(ch, HasLen, 2)
 }
@@ -83,12 +70,7 @@ func (s *NoderSuite) TestDiffChangeMode(c *C) {
 	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)
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
 	c.Assert(err, IsNil)
 	c.Assert(ch, HasLen, 1)
 }
@@ -100,12 +82,7 @@ func (s *NoderSuite) TestDiffChangeModeNotRelevant(c *C) {
 	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)
+	ch, err := merkletrie.DiffTree(NewRootNode(fsA), NewRootNode(fsB), IsEquals)
 	c.Assert(err, IsNil)
 	c.Assert(ch, HasLen, 0)
 }
@@ -125,3 +102,13 @@ func WriteFile(fs billy.Filesystem, filename string, data []byte, perm os.FileMo
 	}
 	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())
+}