aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie/internal/fsnoder
diff options
context:
space:
mode:
Diffstat (limited to 'utils/merkletrie/internal/fsnoder')
-rw-r--r--utils/merkletrie/internal/fsnoder/dir.go140
-rw-r--r--utils/merkletrie/internal/fsnoder/dir_test.go364
-rw-r--r--utils/merkletrie/internal/fsnoder/doc.go50
-rw-r--r--utils/merkletrie/internal/fsnoder/file.go72
-rw-r--r--utils/merkletrie/internal/fsnoder/file_test.go67
-rw-r--r--utils/merkletrie/internal/fsnoder/new.go192
-rw-r--r--utils/merkletrie/internal/fsnoder/new_test.go337
7 files changed, 1222 insertions, 0 deletions
diff --git a/utils/merkletrie/internal/fsnoder/dir.go b/utils/merkletrie/internal/fsnoder/dir.go
new file mode 100644
index 0000000..1811de9
--- /dev/null
+++ b/utils/merkletrie/internal/fsnoder/dir.go
@@ -0,0 +1,140 @@
+package fsnoder
+
+import (
+ "bytes"
+ "fmt"
+ "hash/fnv"
+ "sort"
+ "strings"
+
+ "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// Dir values implement directory-like noders.
+type dir struct {
+ name string // relative
+ children []noder.Noder // sorted by name
+ hash []byte // memoized
+}
+
+type byName []noder.Noder
+
+func (a byName) Len() int { return len(a) }
+func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a byName) Less(i, j int) bool {
+ return strings.Compare(a[i].Name(), a[j].Name()) < 0
+}
+
+// copies the children slice, so nobody can modify the order of its
+// elements from the outside.
+func newDir(name string, children []noder.Noder) (*dir, error) {
+ cloned := make([]noder.Noder, len(children))
+ _ = copy(cloned, children)
+ sort.Sort(byName(cloned))
+
+ if hasChildrenWithNoName(cloned) {
+ return nil, fmt.Errorf("non-root inner nodes cannot have empty names")
+ }
+
+ if hasDuplicatedNames(cloned) {
+ return nil, fmt.Errorf("children cannot have duplicated names")
+ }
+
+ return &dir{
+ name: name,
+ children: cloned,
+ }, nil
+}
+
+func hasChildrenWithNoName(children []noder.Noder) bool {
+ for _, c := range children {
+ if c.Name() == "" {
+ return true
+ }
+ }
+
+ return false
+}
+
+func hasDuplicatedNames(children []noder.Noder) bool {
+ if len(children) < 2 {
+ return false
+ }
+
+ for i := 1; i < len(children); i++ {
+ if children[i].Name() == children[i-1].Name() {
+ return true
+ }
+ }
+
+ return false
+}
+
+func (d *dir) Hash() []byte {
+ if d.hash == nil {
+ d.calculateHash()
+ }
+
+ return d.hash
+}
+
+// hash is calculated as the hash of "dir " plus the concatenation, for
+// each child, of its name, a space and its hash. Children are sorted
+// alphabetically before calculating the hash, so the result is unique.
+func (d *dir) calculateHash() {
+ h := fnv.New64a()
+ h.Write([]byte("dir "))
+ for _, c := range d.children {
+ h.Write([]byte(c.Name()))
+ h.Write([]byte(" "))
+ h.Write(c.Hash())
+ }
+ d.hash = h.Sum([]byte{})
+}
+
+func (d *dir) Name() string {
+ return d.name
+}
+
+func (d *dir) IsDir() bool {
+ return true
+}
+
+// returns a copy so nobody can alter the order of its elements from the
+// outside.
+func (d *dir) Children() ([]noder.Noder, error) {
+ clon := make([]noder.Noder, len(d.children))
+ _ = copy(clon, d.children)
+ return clon, nil
+}
+
+func (d *dir) NumChildren() (int, error) {
+ return len(d.children), nil
+}
+
+const (
+ dirStartMark = '('
+ dirEndMark = ')'
+ dirElementSep = ' '
+)
+
+// The string generated by this method is unique for each tree, as the
+// children of each node are sorted alphabetically by name when
+// generating the string.
+func (d *dir) String() string {
+ var buf bytes.Buffer
+
+ buf.WriteString(d.name)
+ buf.WriteRune(dirStartMark)
+
+ for i, c := range d.children {
+ if i != 0 {
+ buf.WriteRune(dirElementSep)
+ }
+ buf.WriteString(c.String())
+ }
+
+ buf.WriteRune(dirEndMark)
+
+ return buf.String()
+}
diff --git a/utils/merkletrie/internal/fsnoder/dir_test.go b/utils/merkletrie/internal/fsnoder/dir_test.go
new file mode 100644
index 0000000..df5aacc
--- /dev/null
+++ b/utils/merkletrie/internal/fsnoder/dir_test.go
@@ -0,0 +1,364 @@
+package fsnoder
+
+import (
+ "reflect"
+ "sort"
+
+ "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+
+ . "gopkg.in/check.v1"
+)
+
+type DirSuite struct{}
+
+var _ = Suite(&DirSuite{})
+
+func (s *DirSuite) TestIsDir(c *C) {
+ noName, err := newDir("", nil)
+ c.Assert(err, IsNil)
+ c.Assert(noName.IsDir(), Equals, true)
+
+ empty, err := newDir("empty", nil)
+ c.Assert(err, IsNil)
+ c.Assert(empty.IsDir(), Equals, true)
+
+ root, err := newDir("foo", []noder.Noder{empty})
+ c.Assert(err, IsNil)
+ c.Assert(root.IsDir(), Equals, true)
+}
+
+func assertChildren(c *C, n noder.Noder, expected []noder.Noder) {
+ numChildren, err := n.NumChildren()
+ c.Assert(err, IsNil)
+ c.Assert(numChildren, Equals, len(expected))
+
+ children, err := n.Children()
+ c.Assert(err, IsNil)
+ c.Assert(children, sortedSliceEquals, expected)
+}
+
+type sortedSliceEqualsChecker struct {
+ *CheckerInfo
+}
+
+var sortedSliceEquals Checker = &sortedSliceEqualsChecker{
+ &CheckerInfo{
+ Name: "sortedSliceEquals",
+ Params: []string{"obtained", "expected"},
+ },
+}
+
+func (checker *sortedSliceEqualsChecker) Check(
+ params []interface{}, names []string) (result bool, error string) {
+ a, ok := params[0].([]noder.Noder)
+ if !ok {
+ return false, "first parameter must be a []noder.Noder"
+ }
+ b, ok := params[1].([]noder.Noder)
+ if !ok {
+ return false, "second parameter must be a []noder.Noder"
+ }
+ sort.Sort(byName(a))
+ sort.Sort(byName(b))
+
+ return reflect.DeepEqual(a, b), ""
+}
+
+func (s *DirSuite) TestNewDirectoryNoNameAndEmpty(c *C) {
+ root, err := newDir("", nil)
+ c.Assert(err, IsNil)
+
+ c.Assert(root.Hash(), DeepEquals,
+ []byte{0xca, 0x40, 0xf8, 0x67, 0x57, 0x8c, 0x32, 0x1c})
+ c.Assert(root.Name(), Equals, "")
+ assertChildren(c, root, noder.NoChildren)
+ c.Assert(root.String(), Equals, "()")
+}
+
+func (s *DirSuite) TestNewDirectoryEmpty(c *C) {
+ root, err := newDir("root", nil)
+ c.Assert(err, IsNil)
+
+ c.Assert(root.Hash(), DeepEquals,
+ []byte{0xca, 0x40, 0xf8, 0x67, 0x57, 0x8c, 0x32, 0x1c})
+ c.Assert(root.Name(), Equals, "root")
+ assertChildren(c, root, noder.NoChildren)
+ c.Assert(root.String(), Equals, "root()")
+}
+
+func (s *DirSuite) TestEmptyDirsHaveSameHash(c *C) {
+ d1, err := newDir("foo", nil)
+ c.Assert(err, IsNil)
+
+ d2, err := newDir("bar", nil)
+ c.Assert(err, IsNil)
+
+ c.Assert(d1.Hash(), DeepEquals, d2.Hash())
+}
+
+func (s *DirSuite) TestNewDirWithEmptyDir(c *C) {
+ empty, err := newDir("empty", nil)
+ c.Assert(err, IsNil)
+
+ root, err := newDir("", []noder.Noder{empty})
+ c.Assert(err, IsNil)
+
+ c.Assert(root.Hash(), DeepEquals,
+ []byte{0x39, 0x25, 0xa8, 0x99, 0x16, 0x47, 0x6a, 0x75})
+ c.Assert(root.Name(), Equals, "")
+ assertChildren(c, root, []noder.Noder{empty})
+ c.Assert(root.String(), Equals, "(empty())")
+}
+
+func (s *DirSuite) TestNewDirWithOneEmptyFile(c *C) {
+ empty, err := newFile("name", "")
+ c.Assert(err, IsNil)
+
+ root, err := newDir("", []noder.Noder{empty})
+ c.Assert(err, IsNil)
+ c.Assert(root.Hash(), DeepEquals,
+ []byte{0xd, 0x4e, 0x23, 0x1d, 0xf5, 0x2e, 0xfa, 0xc2})
+ c.Assert(root.Name(), Equals, "")
+ assertChildren(c, root, []noder.Noder{empty})
+ c.Assert(root.String(), Equals, "(name<>)")
+}
+
+func (s *DirSuite) TestNewDirWithOneFile(c *C) {
+ a, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+
+ root, err := newDir("", []noder.Noder{a})
+ c.Assert(err, IsNil)
+ c.Assert(root.Hash(), DeepEquals,
+ []byte{0x96, 0xab, 0x29, 0x54, 0x2, 0x9e, 0x89, 0x28})
+ c.Assert(root.Name(), Equals, "")
+ assertChildren(c, root, []noder.Noder{a})
+ c.Assert(root.String(), Equals, "(a<1>)")
+}
+
+func (s *DirSuite) TestDirsWithSameFileHaveSameHash(c *C) {
+ f1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ r1, err := newDir("", []noder.Noder{f1})
+ c.Assert(err, IsNil)
+
+ f2, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ r2, err := newDir("", []noder.Noder{f2})
+ c.Assert(err, IsNil)
+
+ c.Assert(r1.Hash(), DeepEquals, r2.Hash())
+}
+
+func (s *DirSuite) TestDirsWithDifferentFileContentHaveDifferentHash(c *C) {
+ f1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ r1, err := newDir("", []noder.Noder{f1})
+ c.Assert(err, IsNil)
+
+ f2, err := newFile("a", "2")
+ c.Assert(err, IsNil)
+ r2, err := newDir("", []noder.Noder{f2})
+ c.Assert(err, IsNil)
+
+ c.Assert(r1.Hash(), Not(DeepEquals), r2.Hash())
+}
+
+func (s *DirSuite) TestDirsWithDifferentFileNameHaveDifferentHash(c *C) {
+ f1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ r1, err := newDir("", []noder.Noder{f1})
+ c.Assert(err, IsNil)
+
+ f2, err := newFile("b", "1")
+ c.Assert(err, IsNil)
+ r2, err := newDir("", []noder.Noder{f2})
+ c.Assert(err, IsNil)
+
+ c.Assert(r1.Hash(), Not(DeepEquals), r2.Hash())
+}
+
+func (s *DirSuite) TestDirsWithDifferentFileHaveDifferentHash(c *C) {
+ f1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ r1, err := newDir("", []noder.Noder{f1})
+ c.Assert(err, IsNil)
+
+ f2, err := newFile("b", "2")
+ c.Assert(err, IsNil)
+ r2, err := newDir("", []noder.Noder{f2})
+ c.Assert(err, IsNil)
+
+ c.Assert(r1.Hash(), Not(DeepEquals), r2.Hash())
+}
+
+func (s *DirSuite) TestDirWithEmptyDirHasDifferentHashThanEmptyDir(c *C) {
+ f, err := newFile("a", "")
+ c.Assert(err, IsNil)
+ r1, err := newDir("", []noder.Noder{f})
+ c.Assert(err, IsNil)
+
+ d, err := newDir("a", nil)
+ c.Assert(err, IsNil)
+ r2, err := newDir("", []noder.Noder{d})
+ c.Assert(err, IsNil)
+
+ c.Assert(r1.Hash(), Not(DeepEquals), r2.Hash())
+}
+
+func (s *DirSuite) TestNewDirWithTwoFilesSameContent(c *C) {
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ b1, err := newFile("b", "1")
+ c.Assert(err, IsNil)
+
+ root, err := newDir("", []noder.Noder{a1, b1})
+ c.Assert(err, IsNil)
+
+ c.Assert(root.Hash(), DeepEquals,
+ []byte{0xc7, 0xc4, 0xbf, 0x70, 0x33, 0xb9, 0x57, 0xdb})
+ c.Assert(root.Name(), Equals, "")
+ assertChildren(c, root, []noder.Noder{b1, a1})
+ c.Assert(root.String(), Equals, "(a<1> b<1>)")
+}
+
+func (s *DirSuite) TestNewDirWithTwoFilesDifferentContent(c *C) {
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ b2, err := newFile("b", "2")
+ c.Assert(err, IsNil)
+
+ root, err := newDir("", []noder.Noder{a1, b2})
+ c.Assert(err, IsNil)
+
+ c.Assert(root.Hash(), DeepEquals,
+ []byte{0x94, 0x8a, 0x9d, 0x8f, 0x6d, 0x98, 0x34, 0x55})
+ c.Assert(root.Name(), Equals, "")
+ assertChildren(c, root, []noder.Noder{b2, a1})
+}
+
+func (s *DirSuite) TestCrazy(c *C) {
+ // ""
+ // |
+ // -------------------------
+ // | | | | |
+ // a1 B c1 d2 E
+ // | |
+ // ------------- E
+ // | | | | |
+ // A B X c1 E
+ // | |
+ // a1 e1
+ e1, err := newFile("e", "1")
+ c.Assert(err, IsNil)
+ E, err := newDir("e", []noder.Noder{e1})
+ c.Assert(err, IsNil)
+ E, err = newDir("e", []noder.Noder{E})
+ c.Assert(err, IsNil)
+ E, err = newDir("e", []noder.Noder{E})
+ c.Assert(err, IsNil)
+
+ A, err := newDir("a", nil)
+ c.Assert(err, IsNil)
+ B, err := newDir("b", nil)
+ c.Assert(err, IsNil)
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ X, err := newDir("x", []noder.Noder{a1})
+ c.Assert(err, IsNil)
+ c1, err := newFile("c", "1")
+ c.Assert(err, IsNil)
+ B, err = newDir("b", []noder.Noder{c1, B, X, A})
+ c.Assert(err, IsNil)
+
+ a1, err = newFile("a", "1")
+ c.Assert(err, IsNil)
+ c1, err = newFile("c", "1")
+ c.Assert(err, IsNil)
+ d2, err := newFile("d", "2")
+ c.Assert(err, IsNil)
+
+ root, err := newDir("", []noder.Noder{a1, d2, E, B, c1})
+ c.Assert(err, IsNil)
+
+ c.Assert(root.Hash(), DeepEquals,
+ []byte{0xc3, 0x72, 0x9d, 0xf1, 0xcc, 0xec, 0x6d, 0xbb})
+ c.Assert(root.Name(), Equals, "")
+ assertChildren(c, root, []noder.Noder{E, c1, B, a1, d2})
+ c.Assert(root.String(), Equals,
+ "(a<1> b(a() b() c<1> x(a<1>)) c<1> d<2> e(e(e(e<1>))))")
+}
+
+func (s *DirSuite) TestDirCannotHaveDirWithNoName(c *C) {
+ noName, err := newDir("", nil)
+ c.Assert(err, IsNil)
+
+ _, err = newDir("", []noder.Noder{noName})
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *DirSuite) TestDirCannotHaveDuplicatedFiles(c *C) {
+ f1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+
+ f2, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+
+ _, err = newDir("", []noder.Noder{f1, f2})
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *DirSuite) TestDirCannotHaveDuplicatedFileNames(c *C) {
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+
+ a2, err := newFile("a", "2")
+ c.Assert(err, IsNil)
+
+ _, err = newDir("", []noder.Noder{a1, a2})
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *DirSuite) TestDirCannotHaveDuplicatedDirNames(c *C) {
+ d1, err := newDir("a", nil)
+ c.Assert(err, IsNil)
+
+ d2, err := newDir("a", nil)
+ c.Assert(err, IsNil)
+
+ _, err = newDir("", []noder.Noder{d1, d2})
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *DirSuite) TestDirCannotHaveDirAndFileWithSameName(c *C) {
+ f, err := newFile("a", "")
+ c.Assert(err, IsNil)
+
+ d, err := newDir("a", nil)
+ c.Assert(err, IsNil)
+
+ _, err = newDir("", []noder.Noder{f, d})
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *DirSuite) TestUnsortedString(c *C) {
+ b, err := newDir("b", nil)
+ c.Assert(err, IsNil)
+
+ z, err := newDir("z", nil)
+ c.Assert(err, IsNil)
+
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+
+ c2, err := newFile("c", "2")
+ c.Assert(err, IsNil)
+
+ d3, err := newFile("d", "3")
+ c.Assert(err, IsNil)
+
+ d, err := newDir("d", []noder.Noder{c2, z, d3, a1, b})
+ c.Assert(err, IsNil)
+
+ c.Assert(d.String(), Equals, "d(a<1> b() c<2> d<3> z())")
+}
diff --git a/utils/merkletrie/internal/fsnoder/doc.go b/utils/merkletrie/internal/fsnoder/doc.go
new file mode 100644
index 0000000..86cae7c
--- /dev/null
+++ b/utils/merkletrie/internal/fsnoder/doc.go
@@ -0,0 +1,50 @@
+/*
+Package fsnoder allows to create merkletrie noders that resemble file
+systems, from human readable string descriptions. Its intended use is
+generating noders in tests in a readable way.
+
+For example:
+
+ root, _ = New("(a<1> b<2>, B(c<3> d()))")
+
+will create a noder as follows:
+
+ root - "root" is an unnamed dir containing "a", "b" and "B".
+ / | \ - "a" is a file containing the string "1".
+ / | \ - "b" is a file containing the string "2".
+ a b B - "B" is a directory containing "c" and "d".
+ / \ - "c" is a file containing the string "3".
+ c d - "D" is an empty directory.
+
+Files are expressed as:
+
+- a single letter for the name of the file.
+
+- a single number, between angle brackets, for the contents of the file.
+
+Directories are expressed as:
+
+- a single letter for the name of the directory.
+
+- its elements between parents, separated with spaces, in any order.
+
+- (optionally) the root directory can be unnamed, by skiping its name.
+
+Examples:
+
+- D(a<1> b<2>) : two files, "a" and "b", having "1" and "2" as their
+respective contents, inside a directory called "D".
+
+- A() : An empty directory called "A".
+
+- A(b<>) : An directory called "A", with an empty file inside called "b":
+
+- (b(c<1> d(e<2>)) f<>) : an unamed directory containing:
+
+ ├── b --> directory
+ │   ├── c --> file containing "1"
+ │   └── d --> directory
+ │   └── e --> file containing "2"
+ └── f --> empty file
+*/
+package fsnoder
diff --git a/utils/merkletrie/internal/fsnoder/file.go b/utils/merkletrie/internal/fsnoder/file.go
new file mode 100644
index 0000000..c975a60
--- /dev/null
+++ b/utils/merkletrie/internal/fsnoder/file.go
@@ -0,0 +1,72 @@
+package fsnoder
+
+import (
+ "bytes"
+ "fmt"
+ "hash/fnv"
+
+ "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// file values represent file-like noders in a merkle trie.
+type file struct {
+ name string // relative
+ contents string
+ hash []byte // memoized
+}
+
+// newFile returns a noder representing a file with the given contents.
+func newFile(name, contents string) (*file, error) {
+ if name == "" {
+ return nil, fmt.Errorf("files cannot have empty names")
+ }
+
+ return &file{
+ name: name,
+ contents: contents,
+ }, nil
+}
+
+// The hash of a file is just its contents.
+// Empty files will have the fnv64 basis offset as its hash.
+func (f *file) Hash() []byte {
+ if f.hash == nil {
+ h := fnv.New64a()
+ h.Write([]byte(f.contents)) // it nevers returns an error.
+ f.hash = h.Sum(nil)
+ }
+
+ return f.hash
+}
+
+func (f *file) Name() string {
+ return f.name
+}
+
+func (f *file) IsDir() bool {
+ return false
+}
+
+func (f *file) Children() ([]noder.Noder, error) {
+ return noder.NoChildren, nil
+}
+
+func (f *file) NumChildren() (int, error) {
+ return 0, nil
+}
+
+const (
+ fileStartMark = '<'
+ fileEndMark = '>'
+)
+
+// String returns a string formated as: name<contents>.
+func (f *file) String() string {
+ var buf bytes.Buffer
+ buf.WriteString(f.name)
+ buf.WriteRune(fileStartMark)
+ buf.WriteString(f.contents)
+ buf.WriteRune(fileEndMark)
+
+ return buf.String()
+}
diff --git a/utils/merkletrie/internal/fsnoder/file_test.go b/utils/merkletrie/internal/fsnoder/file_test.go
new file mode 100644
index 0000000..730ae7c
--- /dev/null
+++ b/utils/merkletrie/internal/fsnoder/file_test.go
@@ -0,0 +1,67 @@
+package fsnoder
+
+import (
+ "testing"
+
+ "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+
+ . "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type FileSuite struct{}
+
+var _ = Suite(&FileSuite{})
+
+var (
+ HashOfEmptyFile = []byte{0xcb, 0xf2, 0x9c, 0xe4, 0x84, 0x22, 0x23, 0x25} // fnv64 basis offset
+ HashOfContents = []byte{0xee, 0x7e, 0xf3, 0xd0, 0xc2, 0xb5, 0xef, 0x83} // hash of "contents"
+)
+
+func (s *FileSuite) TestNewFileEmpty(c *C) {
+ f, err := newFile("name", "")
+ c.Assert(err, IsNil)
+
+ c.Assert(f.Hash(), DeepEquals, HashOfEmptyFile)
+ c.Assert(f.Name(), Equals, "name")
+ c.Assert(f.IsDir(), Equals, false)
+ assertChildren(c, f, noder.NoChildren)
+ c.Assert(f.String(), Equals, "name<>")
+}
+
+func (s *FileSuite) TestNewFileWithContents(c *C) {
+ f, err := newFile("name", "contents")
+ c.Assert(err, IsNil)
+
+ c.Assert(f.Hash(), DeepEquals, HashOfContents)
+ c.Assert(f.Name(), Equals, "name")
+ c.Assert(f.IsDir(), Equals, false)
+ assertChildren(c, f, noder.NoChildren)
+ c.Assert(f.String(), Equals, "name<contents>")
+}
+
+func (s *FileSuite) TestNewfileErrorEmptyName(c *C) {
+ _, err := newFile("", "contents")
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *FileSuite) TestDifferentContentsHaveDifferentHash(c *C) {
+ f1, err := newFile("name", "contents")
+ c.Assert(err, IsNil)
+
+ f2, err := newFile("name", "foo")
+ c.Assert(err, IsNil)
+
+ c.Assert(f1.Hash(), Not(DeepEquals), f2.Hash())
+}
+
+func (s *FileSuite) TestSameContentsHaveSameHash(c *C) {
+ f1, err := newFile("name1", "contents")
+ c.Assert(err, IsNil)
+
+ f2, err := newFile("name2", "contents")
+ c.Assert(err, IsNil)
+
+ c.Assert(f1.Hash(), DeepEquals, f2.Hash())
+}
diff --git a/utils/merkletrie/internal/fsnoder/new.go b/utils/merkletrie/internal/fsnoder/new.go
new file mode 100644
index 0000000..3ea4733
--- /dev/null
+++ b/utils/merkletrie/internal/fsnoder/new.go
@@ -0,0 +1,192 @@
+package fsnoder
+
+import (
+ "bytes"
+ "fmt"
+ "io"
+
+ "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// New function creates a full merkle trie from the string description of
+// a filesystem tree. See examples of the string format in the package
+// description.
+func New(s string) (noder.Noder, error) {
+ return decodeDir([]byte(s), root)
+}
+
+const (
+ root = true
+ nonRoot = false
+)
+
+// Expected data: a fsnoder description, for example: A(foo bar qux ...).
+// When isRoot is true, unnamed dirs are supported, for example: (foo
+// bar qux ...)
+func decodeDir(data []byte, isRoot bool) (*dir, error) {
+ data = bytes.TrimSpace(data)
+ if len(data) == 0 {
+ return nil, io.EOF
+ }
+
+ // get the name of the dir (a single letter) and remove it from the
+ // data. In case the there is no name and isRoot is true, just use
+ // "" as the name.
+ var name string
+ if data[0] == dirStartMark {
+ if isRoot {
+ name = ""
+ } else {
+ return nil, fmt.Errorf("inner unnamed dirs not allowed: %s", data)
+ }
+ } else {
+ name = string(data[0])
+ data = data[1:]
+ }
+
+ // check that data is enclosed in parents and it is big enough and
+ // remove them.
+ if len(data) < 2 {
+ return nil, fmt.Errorf("malformed data: too short")
+ }
+ if data[0] != dirStartMark {
+ return nil, fmt.Errorf("malformed data: first %q not found",
+ dirStartMark)
+ }
+ if data[len(data)-1] != dirEndMark {
+ return nil, fmt.Errorf("malformed data: last %q not found",
+ dirEndMark)
+ }
+ data = data[1 : len(data)-1] // remove initial '(' and last ')'
+
+ children, err := decodeChildren(data)
+ if err != nil {
+ return nil, err
+ }
+
+ return newDir(name, children)
+}
+
+func isNumber(b byte) bool {
+ return '0' <= b && b <= '9'
+}
+
+func isLetter(b byte) bool {
+ return ('a' <= b && b <= 'z') || ('A' <= b && b <= 'Z')
+}
+
+func decodeChildren(data []byte) ([]noder.Noder, error) {
+ data = bytes.TrimSpace(data)
+ if len(data) == 0 {
+ return nil, nil
+ }
+
+ chunks := split(data)
+ ret := make([]noder.Noder, len(chunks))
+ var err error
+ for i, c := range chunks {
+ ret[i], err = decodeChild(c)
+ if err != nil {
+ return nil, fmt.Errorf("malformed element %d (%s): %s", i, c, err)
+ }
+ }
+
+ return ret, nil
+}
+
+// returns the description of the elements of a dir. It is just looking
+// for spaces if they are not part of inner dirs.
+func split(data []byte) [][]byte {
+ chunks := [][]byte{}
+
+ start := 0
+ dirDepth := 0
+ for i, b := range data {
+ switch b {
+ case dirStartMark:
+ dirDepth++
+ case dirEndMark:
+ dirDepth--
+ case dirElementSep:
+ if dirDepth == 0 {
+ chunks = append(chunks, data[start:i+1])
+ start = i + 1
+ }
+ }
+ }
+ chunks = append(chunks, data[start:])
+
+ return chunks
+}
+
+// A child can be a file or a dir.
+func decodeChild(data []byte) (noder.Noder, error) {
+ clean := bytes.TrimSpace(data)
+ if len(data) < 3 {
+ return nil, fmt.Errorf("element too short: %s", clean)
+ }
+
+ switch clean[1] {
+ case fileStartMark:
+ return decodeFile(clean)
+ case dirStartMark:
+ return decodeDir(clean, nonRoot)
+ default:
+ if clean[0] == dirStartMark {
+ return nil, fmt.Errorf("non-root unnamed dir are not allowed: %s",
+ clean)
+ }
+ return nil, fmt.Errorf("malformed dir element: %s", clean)
+ }
+}
+
+func decodeFile(data []byte) (noder.Noder, error) {
+ if len(data) == 3 {
+ return decodeEmptyFile(data)
+ }
+
+ if len(data) != 4 {
+ return nil, fmt.Errorf("length is not 4")
+ }
+ if !isLetter(data[0]) {
+ return nil, fmt.Errorf("name must be a letter")
+ }
+ if data[1] != '<' {
+ return nil, fmt.Errorf("wrong file start character")
+ }
+ if !isNumber(data[2]) {
+ return nil, fmt.Errorf("contents must be a number")
+ }
+ if data[3] != '>' {
+ return nil, fmt.Errorf("wrong file end character")
+ }
+
+ name := string(data[0])
+ contents := string(data[2])
+
+ return newFile(name, contents)
+}
+
+func decodeEmptyFile(data []byte) (noder.Noder, error) {
+ if len(data) != 3 {
+ return nil, fmt.Errorf("length is not 3: %s", data)
+ }
+ if !isLetter(data[0]) {
+ return nil, fmt.Errorf("name must be a letter: %s", data)
+ }
+ if data[1] != '<' {
+ return nil, fmt.Errorf("wrong file start character: %s", data)
+ }
+ if data[2] != '>' {
+ return nil, fmt.Errorf("wrong file end character: %s", data)
+ }
+
+ name := string(data[0])
+
+ return newFile(name, "")
+}
+
+// HashEqual returns if a and b have the same hash.
+func HashEqual(a, b noder.Hasher) bool {
+ return bytes.Equal(a.Hash(), b.Hash())
+}
diff --git a/utils/merkletrie/internal/fsnoder/new_test.go b/utils/merkletrie/internal/fsnoder/new_test.go
new file mode 100644
index 0000000..e473705
--- /dev/null
+++ b/utils/merkletrie/internal/fsnoder/new_test.go
@@ -0,0 +1,337 @@
+package fsnoder
+
+import (
+ "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+
+ . "gopkg.in/check.v1"
+)
+
+type FSNoderSuite struct{}
+
+var _ = Suite(&FSNoderSuite{})
+
+func check(c *C, input string, expected *dir) {
+ obtained, err := New(input)
+ c.Assert(err, IsNil, Commentf("input = %s", input))
+
+ comment := Commentf("\n input = %s\n"+
+ "expected = %s\nobtained = %s",
+ input, expected, obtained)
+ c.Assert(obtained.Hash(), DeepEquals, expected.Hash(), comment)
+}
+
+func (s *FSNoderSuite) TestNoDataFails(c *C) {
+ _, err := New("")
+ c.Assert(err, Not(IsNil))
+
+ _, err = New(" ") // SPC + TAB
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *FSNoderSuite) TestUnnamedRootFailsIfNotRoot(c *C) {
+ _, err := decodeDir([]byte("()"), false)
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *FSNoderSuite) TestUnnamedInnerFails(c *C) {
+ _, err := New("(())")
+ c.Assert(err, Not(IsNil))
+ _, err = New("((a<>))")
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *FSNoderSuite) TestMalformedInnerName(c *C) {
+ _, err := New("(ab<>)")
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *FSNoderSuite) TestMalformedFile(c *C) {
+ _, err := New("(a<12>)")
+ c.Assert(err, Not(IsNil))
+ _, err = New("(4<>)")
+ c.Assert(err, Not(IsNil))
+ _, err = New("(4<1>)")
+ c.Assert(err, Not(IsNil))
+ _, err = New("(4?1>)")
+ c.Assert(err, Not(IsNil))
+ _, err = New("(4<a>)")
+ c.Assert(err, Not(IsNil))
+ _, err = New("(4<a?)")
+ c.Assert(err, Not(IsNil))
+
+ _, err = decodeFile([]byte("a?1>"))
+ c.Assert(err, Not(IsNil))
+ _, err = decodeFile([]byte("a<a>"))
+ c.Assert(err, Not(IsNil))
+ _, err = decodeFile([]byte("a<1?"))
+ c.Assert(err, Not(IsNil))
+
+ _, err = decodeEmptyFile([]byte("a<1>"))
+ c.Assert(err, Not(IsNil))
+ _, err = decodeEmptyFile([]byte("a?>"))
+ c.Assert(err, Not(IsNil))
+ _, err = decodeEmptyFile([]byte("1<>"))
+ c.Assert(err, Not(IsNil))
+ _, err = decodeEmptyFile([]byte("a<?"))
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *FSNoderSuite) TestMalformedRootFails(c *C) {
+ _, err := New(")")
+ c.Assert(err, Not(IsNil))
+ _, err = New("(")
+ c.Assert(err, Not(IsNil))
+ _, err = New("(a<>")
+ c.Assert(err, Not(IsNil))
+ _, err = New("a<>")
+ c.Assert(err, Not(IsNil))
+}
+
+func (s *FSNoderSuite) TestUnnamedEmptyRoot(c *C) {
+ input := "()"
+
+ expected, err := newDir("", nil)
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestNamedEmptyRoot(c *C) {
+ input := "a()"
+
+ expected, err := newDir("a", nil)
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestEmptyFile(c *C) {
+ input := "(a<>)"
+
+ a1, err := newFile("a", "")
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{a1})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestNonEmptyFile(c *C) {
+ input := "(a<1>)"
+
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{a1})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestTwoFilesSameContents(c *C) {
+ input := "(b<1> a<1>)"
+
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ b1, err := newFile("b", "1")
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{a1, b1})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestTwoFilesDifferentContents(c *C) {
+ input := "(b<2> a<1>)"
+
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ b2, err := newFile("b", "2")
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{a1, b2})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestManyFiles(c *C) {
+ input := "(e<1> b<2> a<1> c<1> d<3> f<4>)"
+
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ b2, err := newFile("b", "2")
+ c.Assert(err, IsNil)
+ c1, err := newFile("c", "1")
+ c.Assert(err, IsNil)
+ d3, err := newFile("d", "3")
+ c.Assert(err, IsNil)
+ e1, err := newFile("e", "1")
+ c.Assert(err, IsNil)
+ f4, err := newFile("f", "4")
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{e1, b2, a1, c1, d3, f4})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestEmptyDir(c *C) {
+ input := "(A())"
+
+ A, err := newDir("A", nil)
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{A})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestDirWithEmtpyFile(c *C) {
+ input := "(A(a<>))"
+
+ a, err := newFile("a", "")
+ c.Assert(err, IsNil)
+ A, err := newDir("A", []noder.Noder{a})
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{A})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestDirWithEmtpyFileSameName(c *C) {
+ input := "(A(A<>))"
+
+ f, err := newFile("A", "")
+ c.Assert(err, IsNil)
+ A, err := newDir("A", []noder.Noder{f})
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{A})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestDirWithFile(c *C) {
+ input := "(A(a<1>))"
+
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ A, err := newDir("A", []noder.Noder{a1})
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{A})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestDirWithEmptyDirSameName(c *C) {
+ input := "(A(A()))"
+
+ A2, err := newDir("A", nil)
+ c.Assert(err, IsNil)
+ A1, err := newDir("A", []noder.Noder{A2})
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{A1})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestDirWithEmptyDir(c *C) {
+ input := "(A(B()))"
+
+ B, err := newDir("B", nil)
+ c.Assert(err, IsNil)
+ A, err := newDir("A", []noder.Noder{B})
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{A})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestDirWithTwoFiles(c *C) {
+ input := "(A(a<1> b<2>))"
+
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ b2, err := newFile("b", "2")
+ c.Assert(err, IsNil)
+ A, err := newDir("A", []noder.Noder{b2, a1})
+ c.Assert(err, IsNil)
+ expected, err := newDir("", []noder.Noder{A})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestCrazy(c *C) {
+ // ""
+ // |
+ // -------------------------
+ // | | | | |
+ // a1 B c1 d2 E
+ // | |
+ // ------------- E
+ // | | | | |
+ // A B X c1 E
+ // | |
+ // a1 e1
+ input := "(d<2> b(c<1> b() a() x(a<1>)) a<1> c<1> e(e(e(e<1>))))"
+
+ e1, err := newFile("e", "1")
+ c.Assert(err, IsNil)
+ E, err := newDir("e", []noder.Noder{e1})
+ c.Assert(err, IsNil)
+ E, err = newDir("e", []noder.Noder{E})
+ c.Assert(err, IsNil)
+ E, err = newDir("e", []noder.Noder{E})
+ c.Assert(err, IsNil)
+
+ A, err := newDir("a", nil)
+ c.Assert(err, IsNil)
+ B, err := newDir("b", nil)
+ c.Assert(err, IsNil)
+ a1, err := newFile("a", "1")
+ c.Assert(err, IsNil)
+ X, err := newDir("x", []noder.Noder{a1})
+ c.Assert(err, IsNil)
+ c1, err := newFile("c", "1")
+ c.Assert(err, IsNil)
+ B, err = newDir("b", []noder.Noder{c1, B, X, A})
+ c.Assert(err, IsNil)
+
+ a1, err = newFile("a", "1")
+ c.Assert(err, IsNil)
+ c1, err = newFile("c", "1")
+ c.Assert(err, IsNil)
+ d2, err := newFile("d", "2")
+ c.Assert(err, IsNil)
+
+ expected, err := newDir("", []noder.Noder{a1, d2, E, B, c1})
+ c.Assert(err, IsNil)
+
+ check(c, input, expected)
+}
+
+func (s *FSNoderSuite) TestHashEqual(c *C) {
+ input1 := "(A(a<1> b<2>))"
+ input2 := "(A(a<1> b<2>))"
+ input3 := "(A(a<> b<2>))"
+
+ t1, err := New(input1)
+ c.Assert(err, IsNil)
+ t2, err := New(input2)
+ c.Assert(err, IsNil)
+ t3, err := New(input3)
+ c.Assert(err, IsNil)
+
+ c.Assert(HashEqual(t1, t2), Equals, true)
+ c.Assert(HashEqual(t2, t1), Equals, true)
+
+ c.Assert(HashEqual(t2, t3), Equals, false)
+ c.Assert(HashEqual(t3, t2), Equals, false)
+
+ c.Assert(HashEqual(t3, t1), Equals, false)
+ c.Assert(HashEqual(t1, t3), Equals, false)
+}
generated by cgit (git 2.34.1) at 2024-09-20 17:30:56 +0000