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.

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)
+}