aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie
diff options
context:
space:
mode:
Diffstat (limited to 'utils/merkletrie')
-rw-r--r--utils/merkletrie/difftree.go3
-rw-r--r--utils/merkletrie/difftree_test.go10
-rw-r--r--utils/merkletrie/internal/fsnoder/doc.go6
-rw-r--r--utils/merkletrie/internal/fsnoder/new.go131
-rw-r--r--utils/merkletrie/internal/fsnoder/new_test.go43
-rw-r--r--utils/merkletrie/noder/noder_test.go8
-rw-r--r--utils/merkletrie/noder/path.go31
-rw-r--r--utils/merkletrie/noder/path_test.go151
8 files changed, 302 insertions, 81 deletions
diff --git a/utils/merkletrie/difftree.go b/utils/merkletrie/difftree.go
index 1a626cd..7bea55f 100644
--- a/utils/merkletrie/difftree.go
+++ b/utils/merkletrie/difftree.go
@@ -249,7 +249,6 @@ package merkletrie
import (
"fmt"
- "strings"
"srcd.works/go-git.v4/utils/merkletrie/noder"
)
@@ -302,7 +301,7 @@ func diffNodes(changes *Changes, ii *doubleIter) error {
var err error
// compare their full paths as strings
- switch strings.Compare(from.String(), to.String()) {
+ switch from.Compare(to) {
case -1:
if err = changes.AddRecursiveDelete(from); err != nil {
return err
diff --git a/utils/merkletrie/difftree_test.go b/utils/merkletrie/difftree_test.go
index 6a193af..c3fb4f1 100644
--- a/utils/merkletrie/difftree_test.go
+++ b/utils/merkletrie/difftree_test.go
@@ -427,3 +427,13 @@ func (s *DiffTreeSuite) TestSameNames(c *C) {
},
})
}
+
+func (s *DiffTreeSuite) TestIssue275(c *C) {
+ do(c, []diffTreeTest{
+ {
+ "(a(b(c.go<1>) b.go<2>))",
+ "(a(b(c.go<1> d.go<3>) b.go<2>))",
+ "+a/b/d.go",
+ },
+ })
+}
diff --git a/utils/merkletrie/internal/fsnoder/doc.go b/utils/merkletrie/internal/fsnoder/doc.go
index 86cae7c..3f55b5f 100644
--- a/utils/merkletrie/internal/fsnoder/doc.go
+++ b/utils/merkletrie/internal/fsnoder/doc.go
@@ -18,13 +18,15 @@ will create a noder as follows:
Files are expressed as:
-- a single letter for the name of the file.
+- one or more letters and dots for the name of the file
- a single number, between angle brackets, for the contents of the file.
+- examples: a<1>, foo.go<2>.
+
Directories are expressed as:
-- a single letter for the name of the directory.
+- one or more letters for the name of the directory.
- its elements between parents, separated with spaces, in any order.
diff --git a/utils/merkletrie/internal/fsnoder/new.go b/utils/merkletrie/internal/fsnoder/new.go
index ebeb378..f3c6ae9 100644
--- a/utils/merkletrie/internal/fsnoder/new.go
+++ b/utils/merkletrie/internal/fsnoder/new.go
@@ -29,30 +29,24 @@ func decodeDir(data []byte, isRoot bool) (*dir, error) {
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.
+ // get the name of the dir 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 {
+ switch end := bytes.IndexRune(data, dirStartMark); end {
+ case -1:
+ return nil, fmt.Errorf("%c not found")
+ case 0:
if isRoot {
name = ""
} else {
return nil, fmt.Errorf("inner unnamed dirs not allowed: %s", data)
}
- } else {
- name = string(data[0])
- data = data[1:]
+ default:
+ name = string(data[0:end])
+ data = data[end:]
}
- // 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)
- }
+ // check data ends with the dirEndMark
if data[len(data)-1] != dirEndMark {
return nil, fmt.Errorf("malformed data: last %q not found",
dirEndMark)
@@ -67,11 +61,11 @@ func decodeDir(data []byte, isRoot bool) (*dir, error) {
return newDir(name, children)
}
-func isNumber(b byte) bool {
+func isNumber(b rune) bool {
return '0' <= b && b <= '9'
}
-func isLetter(b byte) bool {
+func isLetter(b rune) bool {
return ('a' <= b && b <= 'z') || ('A' <= b && b <= 'Z')
}
@@ -126,64 +120,77 @@ func decodeChild(data []byte) (noder.Noder, error) {
return nil, fmt.Errorf("element too short: %s", clean)
}
- switch clean[1] {
- case fileStartMark:
+ fileNameEnd := bytes.IndexRune(data, fileStartMark)
+ dirNameEnd := bytes.IndexRune(data, dirStartMark)
+ switch {
+ case fileNameEnd == -1 && dirNameEnd == -1:
+ return nil, fmt.Errorf(
+ "malformed child, no file or dir start mark found")
+ case fileNameEnd == -1:
+ return decodeDir(clean, nonRoot)
+ case dirNameEnd == -1:
return decodeFile(clean)
- case dirStartMark:
+ case dirNameEnd < fileNameEnd:
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)
+ case dirNameEnd > fileNameEnd:
+ return decodeFile(clean)
}
+
+ return nil, fmt.Errorf("unreachable")
}
func decodeFile(data []byte) (noder.Noder, error) {
- if len(data) == 3 {
- return decodeEmptyFile(data)
+ nameEnd := bytes.IndexRune(data, fileStartMark)
+ if nameEnd == -1 {
+ return nil, fmt.Errorf("malformed file, no %c found", fileStartMark)
+ }
+ contentStart := nameEnd + 1
+ contentEnd := bytes.IndexRune(data, fileEndMark)
+ if contentEnd == -1 {
+ return nil, fmt.Errorf("malformed file, no %c found", fileEndMark)
+ }
+
+ switch {
+ case nameEnd > contentEnd:
+ return nil, fmt.Errorf("malformed file, found %c before %c",
+ fileEndMark, fileStartMark)
+ case contentStart == contentEnd:
+ name := string(data[:nameEnd])
+ if !validFileName(name) {
+ return nil, fmt.Errorf("invalid file name")
+ }
+ return newFile(name, "")
+ default:
+ name := string(data[:nameEnd])
+ if !validFileName(name) {
+ return nil, fmt.Errorf("invalid file name")
+ }
+ contents := string(data[contentStart:contentEnd])
+ if !validFileContents(contents) {
+ return nil, fmt.Errorf("invalid file contents")
+ }
+ return newFile(name, contents)
}
+}
- 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")
+func validFileName(s string) bool {
+ for _, c := range s {
+ if !isLetter(c) && c != '.' {
+ return false
+ }
}
- name := string(data[0])
- contents := string(data[2])
-
- return newFile(name, contents)
+ return true
}
-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)
+func validFileContents(s string) bool {
+ for _, c := range s {
+ if !isNumber(c) {
+ return false
+ }
}
- name := string(data[0])
-
- return newFile(name, "")
+ return true
}
// HashEqual returns if a and b have the same hash.
diff --git a/utils/merkletrie/internal/fsnoder/new_test.go b/utils/merkletrie/internal/fsnoder/new_test.go
index 3e209a9..20f028b 100644
--- a/utils/merkletrie/internal/fsnoder/new_test.go
+++ b/utils/merkletrie/internal/fsnoder/new_test.go
@@ -40,15 +40,8 @@ func (s *FSNoderSuite) TestUnnamedInnerFails(c *C) {
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<>)")
+ _, err := New("(4<>)")
c.Assert(err, Not(IsNil))
_, err = New("(4<1>)")
c.Assert(err, Not(IsNil))
@@ -66,13 +59,11 @@ func (s *FSNoderSuite) TestMalformedFile(c *C) {
_, err = decodeFile([]byte("a<1?"))
c.Assert(err, Not(IsNil))
- _, err = decodeEmptyFile([]byte("a<1>"))
+ _, err = decodeFile([]byte("a?>"))
c.Assert(err, Not(IsNil))
- _, err = decodeEmptyFile([]byte("a?>"))
+ _, err = decodeFile([]byte("1<>"))
c.Assert(err, Not(IsNil))
- _, err = decodeEmptyFile([]byte("1<>"))
- c.Assert(err, Not(IsNil))
- _, err = decodeEmptyFile([]byte("a<?"))
+ _, err = decodeFile([]byte("a<?"))
c.Assert(err, Not(IsNil))
}
@@ -211,6 +202,32 @@ func (s *FSNoderSuite) TestDirWithEmtpyFileSameName(c *C) {
check(c, input, expected)
}
+func (s *FSNoderSuite) TestDirWithFileLongContents(c *C) {
+ input := "(A(a<12>))"
+
+ a1, err := newFile("a", "12")
+ 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) TestDirWithFileLongName(c *C) {
+ input := "(A(abc<12>))"
+
+ a1, err := newFile("abc", "12")
+ 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) TestDirWithFile(c *C) {
input := "(A(a<1>))"
diff --git a/utils/merkletrie/noder/noder_test.go b/utils/merkletrie/noder/noder_test.go
index 14bef4a..5e014fe 100644
--- a/utils/merkletrie/noder/noder_test.go
+++ b/utils/merkletrie/noder/noder_test.go
@@ -1,6 +1,12 @@
package noder
-import . "gopkg.in/check.v1"
+import (
+ "testing"
+
+ . "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
type NoderSuite struct{}
diff --git a/utils/merkletrie/noder/path.go b/utils/merkletrie/noder/path.go
index c992f7e..85742db 100644
--- a/utils/merkletrie/noder/path.go
+++ b/utils/merkletrie/noder/path.go
@@ -1,6 +1,9 @@
package noder
-import "bytes"
+import (
+ "bytes"
+ "strings"
+)
// Path values represent a noder and its ancestors. The root goes first
// and the actual final noder the path is refering to will be the last.
@@ -57,3 +60,29 @@ func (p Path) Children() ([]Noder, error) {
func (p Path) NumChildren() (int, error) {
return p.Last().NumChildren()
}
+
+// Compare returns -1, 0 or 1 if the path p is smaller, equal or bigger
+// than other, in "directory order"; for example:
+//
+// "a" < "b"
+// "a/b/c/d/z" < "b"
+// "a/b/a" > "a/b"
+func (p Path) Compare(other Path) int {
+ i := 0
+ for {
+ switch {
+ case len(other) == len(p) && i == len(p):
+ return 0
+ case i == len(other):
+ return 1
+ case i == len(p):
+ return -1
+ default:
+ cmp := strings.Compare(p[i].Name(), other[i].Name())
+ if cmp != 0 {
+ return cmp
+ }
+ }
+ i++
+ }
+}
diff --git a/utils/merkletrie/noder/path_test.go b/utils/merkletrie/noder/path_test.go
new file mode 100644
index 0000000..44e3c3c
--- /dev/null
+++ b/utils/merkletrie/noder/path_test.go
@@ -0,0 +1,151 @@
+package noder
+
+import . "gopkg.in/check.v1"
+
+type PathSuite struct{}
+
+var _ = Suite(&PathSuite{})
+
+func (s *PathSuite) TestShortFile(c *C) {
+ f := &noderMock{
+ name: "1",
+ isDir: false,
+ }
+ p := Path([]Noder{f})
+ c.Assert(p.String(), Equals, "1")
+}
+
+func (s *PathSuite) TestShortDir(c *C) {
+ d := &noderMock{
+ name: "1",
+ isDir: true,
+ children: NoChildren,
+ }
+ p := Path([]Noder{d})
+ c.Assert(p.String(), Equals, "1")
+}
+
+func (s *PathSuite) TestLongFile(c *C) {
+ n3 := &noderMock{
+ name: "3",
+ isDir: false,
+ }
+ n2 := &noderMock{
+ name: "2",
+ isDir: true,
+ children: []Noder{n3},
+ }
+ n1 := &noderMock{
+ name: "1",
+ isDir: true,
+ children: []Noder{n2},
+ }
+ p := Path([]Noder{n1, n2, n3})
+ c.Assert(p.String(), Equals, "1/2/3")
+}
+
+func (s *PathSuite) TestLongDir(c *C) {
+ n3 := &noderMock{
+ name: "3",
+ isDir: true,
+ children: NoChildren,
+ }
+ n2 := &noderMock{
+ name: "2",
+ isDir: true,
+ children: []Noder{n3},
+ }
+ n1 := &noderMock{
+ name: "1",
+ isDir: true,
+ children: []Noder{n2},
+ }
+ p := Path([]Noder{n1, n2, n3})
+ c.Assert(p.String(), Equals, "1/2/3")
+}
+
+func (s *PathSuite) TestCompareDepth1(c *C) {
+ p1 := Path([]Noder{&noderMock{name: "a"}})
+ p2 := Path([]Noder{&noderMock{name: "b"}})
+ c.Assert(p1.Compare(p2), Equals, -1)
+ c.Assert(p2.Compare(p1), Equals, 1)
+
+ p1 = Path([]Noder{&noderMock{name: "a"}})
+ p2 = Path([]Noder{&noderMock{name: "a"}})
+ c.Assert(p1.Compare(p2), Equals, 0)
+ c.Assert(p2.Compare(p1), Equals, 0)
+
+ p1 = Path([]Noder{&noderMock{name: "a.go"}})
+ p2 = Path([]Noder{&noderMock{name: "a"}})
+ c.Assert(p1.Compare(p2), Equals, 1)
+ c.Assert(p2.Compare(p1), Equals, -1)
+}
+
+func (s *PathSuite) TestCompareDepth2(c *C) {
+ p1 := Path([]Noder{
+ &noderMock{name: "a"},
+ &noderMock{name: "b"},
+ })
+ p2 := Path([]Noder{
+ &noderMock{name: "b"},
+ &noderMock{name: "a"},
+ })
+ c.Assert(p1.Compare(p2), Equals, -1)
+ c.Assert(p2.Compare(p1), Equals, 1)
+
+ p1 = Path([]Noder{
+ &noderMock{name: "a"},
+ &noderMock{name: "b"},
+ })
+ p2 = Path([]Noder{
+ &noderMock{name: "a"},
+ &noderMock{name: "b"},
+ })
+ c.Assert(p1.Compare(p2), Equals, 0)
+ c.Assert(p2.Compare(p1), Equals, 0)
+
+ p1 = Path([]Noder{
+ &noderMock{name: "a"},
+ &noderMock{name: "b"},
+ })
+ p2 = Path([]Noder{
+ &noderMock{name: "a"},
+ &noderMock{name: "a"},
+ })
+ c.Assert(p1.Compare(p2), Equals, 1)
+ c.Assert(p2.Compare(p1), Equals, -1)
+}
+
+func (s *PathSuite) TestCompareMixedDepths(c *C) {
+ p1 := Path([]Noder{
+ &noderMock{name: "a"},
+ &noderMock{name: "b"},
+ })
+ p2 := Path([]Noder{&noderMock{name: "b"}})
+ c.Assert(p1.Compare(p2), Equals, -1)
+ c.Assert(p2.Compare(p1), Equals, 1)
+
+ p1 = Path([]Noder{
+ &noderMock{name: "b"},
+ &noderMock{name: "b"},
+ })
+ p2 = Path([]Noder{&noderMock{name: "b"}})
+ c.Assert(p1.Compare(p2), Equals, 1)
+ c.Assert(p2.Compare(p1), Equals, -1)
+
+ p1 = Path([]Noder{&noderMock{name: "a.go"}})
+ p2 = Path([]Noder{
+ &noderMock{name: "a"},
+ &noderMock{name: "a.go"},
+ })
+ c.Assert(p1.Compare(p2), Equals, 1)
+ c.Assert(p2.Compare(p1), Equals, -1)
+
+ p1 = Path([]Noder{&noderMock{name: "b.go"}})
+ p2 = Path([]Noder{
+ &noderMock{name: "a"},
+ &noderMock{name: "a.go"},
+ })
+ c.Assert(p1.Compare(p2), Equals, 1)
+ c.Assert(p2.Compare(p1), Equals, -1)
+}
generated by cgit (git 2.34.1) at 2024-11-10 17:07:09 +0000