aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie
diff options
context:
space:
mode:
Diffstat (limited to 'utils/merkletrie')
-rw-r--r--utils/merkletrie/filesystem/node.go128
-rw-r--r--utils/merkletrie/filesystem/node_test.go127
-rw-r--r--utils/merkletrie/index/node.go113
-rw-r--r--utils/merkletrie/index/node_test.go116
4 files changed, 484 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
+}
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)
+}
generated by cgit (git 2.34.1) at 2024-10-27 17:12:58 +0000