aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie/internal/fsnoder
diff options
context:
space:
mode:
authorAlberto Cortés <alcortesm@gmail.com>2017-02-22 16:45:46 +0100
committerGitHub <noreply@github.com>2017-02-22 16:45:46 +0100
commitb5da4e98571b02dc106de4f9b2cb2a298489f1b1 (patch)
tree26f44140f9bf4dc5291e0b88c9f4f91354afffad /utils/merkletrie/internal/fsnoder
parenta79bc09bdc6517e0dc9cc5f7936cf6312c3c1db3 (diff)
downloadgo-git-b5da4e98571b02dc106de4f9b2cb2a298489f1b1.tar.gz
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.
Diffstat (limited to 'utils/merkletrie/internal/fsnoder')
-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
3 files changed, 103 insertions, 77 deletions
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>))"