From b5da4e98571b02dc106de4f9b2cb2a298489f1b1 Mon Sep 17 00:00:00 2001 From: Alberto Cortés Date: Wed, 22 Feb 2017 16:45:46 +0100 Subject: Fix issue 275 (edited) (#276) Fix #275 . It was not possible to write a test for this issue as the original fsnoder didn't support filenames with length > 1. Therefore this patch has 3 commits: add support for long filenames in fsnoder. add a test case for the issue using the new long filenames from step 1. fix the issue by comparing paths level by level instead of lexigographically over the whole path. --- utils/merkletrie/difftree.go | 3 +- utils/merkletrie/difftree_test.go | 10 ++ utils/merkletrie/internal/fsnoder/doc.go | 6 +- utils/merkletrie/internal/fsnoder/new.go | 131 +++++++++++----------- utils/merkletrie/internal/fsnoder/new_test.go | 43 +++++--- utils/merkletrie/noder/noder_test.go | 8 +- utils/merkletrie/noder/path.go | 31 +++++- utils/merkletrie/noder/path_test.go | 151 ++++++++++++++++++++++++++ 8 files changed, 302 insertions(+), 81 deletions(-) create mode 100644 utils/merkletrie/noder/path_test.go (limited to 'utils/merkletrie') 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))" + + 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) +} -- cgit