package merkletrie_test import ( "fmt" "io" "strings" "srcd.works/go-git.v4/utils/merkletrie" "srcd.works/go-git.v4/utils/merkletrie/internal/fsnoder" "srcd.works/go-git.v4/utils/merkletrie/noder" . "gopkg.in/check.v1" ) type IterSuite struct{} var _ = Suite(&IterSuite{}) // A test is a list of operations we want to perform on an iterator and // their expected results. // // The operations are expresed as a sequence of `n` and `s`, // representing the amount of next and step operations we want to call // on the iterator and their order. For example, an operations value of // "nns" means: call a `n`ext, then another `n`ext and finish with a // `s`tep. // // The expeced is the full path of the noders returned by the // operations, separated by spaces. // // For instance: // // t := test{ // operations: "ns", // expected: "a a/b" // } // // means: // // - the first iterator operation has to be Next, and it must return a // node called "a" with no ancestors. // // - the second operation has to be Step, and it must return a node // called "b" with a single ancestor called "a". type test struct { operations string expected string } // Runs a test on the provided iterator, checking that the names of the // returned values are correct. If not, the treeDescription value is // printed along with information about mismatch. func (t test) run(c *C, iter *merkletrie.Iter, treeDescription string, testNumber int) { expectedChunks := strings.Split(t.expected, " ") if t.expected == "" { expectedChunks = []string{} } if len(t.operations) < len(expectedChunks) { c.Fatalf("malformed test %d: not enough operations", testNumber) return } var obtained noder.Path var err error for i := range t.operations { comment := Commentf("\ntree: %q\ntest #%d (%q)\noperation #%d (%q)", treeDescription, testNumber, t.operations, i, t.operations[i]) switch t.operations[i] { case 'n': obtained, err = iter.Next() if err != io.EOF { c.Assert(err, IsNil) } case 's': obtained, err = iter.Step() if err != io.EOF { c.Assert(err, IsNil) } default: c.Fatalf("unknown operation at test %d, operation %d (%s)\n", testNumber, i, t.operations[i]) } if i >= len(expectedChunks) { c.Assert(err, Equals, io.EOF, comment) continue } c.Assert(err, IsNil, comment) c.Assert(obtained.String(), Equals, expectedChunks[i], comment) } } // A testsCollection value represents a tree and a collection of tests // we want to perfrom on iterators of that tree. // // Example: // // . // | // --------- // | | | // a b c // | // z // // var foo testCollection = { // tree: "(a<> b(z<>) c<>)" // tests: []test{ // {operations: "nns", expected: "a b b/z"}, // {operations: "nnn", expected: "a b c"}, // }, // } // // A new iterator will be build for each test. type testsCollection struct { tree string // a fsnoder description of a tree. tests []test // the collection of tests we want to run } // Executes all the tests in a testsCollection. func (tc testsCollection) run(c *C) { root, err := fsnoder.New(tc.tree) c.Assert(err, IsNil) for i, t := range tc.tests { iter, err := merkletrie.NewIter(root) c.Assert(err, IsNil) t.run(c, iter, root.String(), i) } } func (s *IterSuite) TestEmptyNamedDir(c *C) { tc := testsCollection{ tree: "A()", tests: []test{ {operations: "n", expected: ""}, {operations: "nn", expected: ""}, {operations: "nnn", expected: ""}, {operations: "nnns", expected: ""}, {operations: "nnnssnsnns", expected: ""}, {operations: "s", expected: ""}, {operations: "ss", expected: ""}, {operations: "sss", expected: ""}, {operations: "sssn", expected: ""}, {operations: "sssnnsnssn", expected: ""}, }, } tc.run(c) } func (s *IterSuite) TestEmptyUnnamedDir(c *C) { tc := testsCollection{ tree: "()", tests: []test{ {operations: "n", expected: ""}, {operations: "nn", expected: ""}, {operations: "nnn", expected: ""}, {operations: "nnns", expected: ""}, {operations: "nnnssnsnns", expected: ""}, {operations: "s", expected: ""}, {operations: "ss", expected: ""}, {operations: "sss", expected: ""}, {operations: "sssn", expected: ""}, {operations: "sssnnsnssn", expected: ""}, }, } tc.run(c) } func (s *IterSuite) TestOneFile(c *C) { tc := testsCollection{ tree: "(a<>)", tests: []test{ {operations: "n", expected: "a"}, {operations: "nn", expected: "a"}, {operations: "nnn", expected: "a"}, {operations: "nnns", expected: "a"}, {operations: "nnnssnsnns", expected: "a"}, {operations: "s", expected: "a"}, {operations: "ss", expected: "a"}, {operations: "sss", expected: "a"}, {operations: "sssn", expected: "a"}, {operations: "sssnnsnssn", expected: "a"}, }, } tc.run(c) } // root // / \ // a b func (s *IterSuite) TestTwoFiles(c *C) { tc := testsCollection{ tree: "(a<> b<>)", tests: []test{ {operations: "nnn", expected: "a b"}, {operations: "nns", expected: "a b"}, {operations: "nsn", expected: "a b"}, {operations: "nss", expected: "a b"}, {operations: "snn", expected: "a b"}, {operations: "sns", expected: "a b"}, {operations: "ssn", expected: "a b"}, {operations: "sss", expected: "a b"}, }, } tc.run(c) } // root // | // a // | // b func (s *IterSuite) TestDirWithFile(c *C) { tc := testsCollection{ tree: "(a(b<>))", tests: []test{ {operations: "nnn", expected: "a"}, {operations: "nns", expected: "a"}, {operations: "nsn", expected: "a a/b"}, {operations: "nss", expected: "a a/b"}, {operations: "snn", expected: "a"}, {operations: "sns", expected: "a"}, {operations: "ssn", expected: "a a/b"}, {operations: "sss", expected: "a a/b"}, }, } tc.run(c) } // root // /|\ // c a b func (s *IterSuite) TestThreeSiblings(c *C) { tc := testsCollection{ tree: "(c<> a<> b<>)", tests: []test{ {operations: "nnnn", expected: "a b c"}, {operations: "nnns", expected: "a b c"}, {operations: "nnsn", expected: "a b c"}, {operations: "nnss", expected: "a b c"}, {operations: "nsnn", expected: "a b c"}, {operations: "nsns", expected: "a b c"}, {operations: "nssn", expected: "a b c"}, {operations: "nsss", expected: "a b c"}, {operations: "snnn", expected: "a b c"}, {operations: "snns", expected: "a b c"}, {operations: "snsn", expected: "a b c"}, {operations: "snss", expected: "a b c"}, {operations: "ssnn", expected: "a b c"}, {operations: "ssns", expected: "a b c"}, {operations: "sssn", expected: "a b c"}, {operations: "ssss", expected: "a b c"}, }, } tc.run(c) } // root // | // b // | // c // | // a func (s *IterSuite) TestThreeVertical(c *C) { tc := testsCollection{ tree: "(b(c(a())))", tests: []test{ {operations: "nnnn", expected: "b"}, {operations: "nnns", expected: "b"}, {operations: "nnsn", expected: "b"}, {operations: "nnss", expected: "b"}, {operations: "nsnn", expected: "b b/c"}, {operations: "nsns", expected: "b b/c"}, {operations: "nssn", expected: "b b/c b/c/a"}, {operations: "nsss", expected: "b b/c b/c/a"}, {operations: "snnn", expected: "b"}, {operations: "snns", expected: "b"}, {operations: "snsn", expected: "b"}, {operations: "snss", expected: "b"}, {operations: "ssnn", expected: "b b/c"}, {operations: "ssns", expected: "b b/c"}, {operations: "sssn", expected: "b b/c b/c/a"}, {operations: "ssss", expected: "b b/c b/c/a"}, }, } tc.run(c) } // root // / \ // c a // | // b func (s *IterSuite) TestThreeMix1(c *C) { tc := testsCollection{ tree: "(c(b<>) a<>)", tests: []test{ {operations: "nnnn", expected: "a c"}, {operations: "nnns", expected: "a c"}, {operations: "nnsn", expected: "a c c/b"}, {operations: "nnss", expected: "a c c/b"}, {operations: "nsnn", expected: "a c"}, {operations: "nsns", expected: "a c"}, {operations: "nssn", expected: "a c c/b"}, {operations: "nsss", expected: "a c c/b"}, {operations: "snnn", expected: "a c"}, {operations: "snns", expected: "a c"}, {operations: "snsn", expected: "a c c/b"}, {operations: "snss", expected: "a c c/b"}, {operations: "ssnn", expected: "a c"}, {operations: "ssns", expected: "a c"}, {operations: "sssn", expected: "a c c/b"}, {operations: "ssss", expected: "a c c/b"}, }, } tc.run(c) } // root // / \ // b a // | // c func (s *IterSuite) TestThreeMix2(c *C) { tc := testsCollection{ tree: "(b() a(c<>))", tests: []test{ {operations: "nnnn", expected: "a b"}, {operations: "nnns", expected: "a b"}, {operations: "nnsn", expected: "a b"}, {operations: "nnss", expected: "a b"}, {operations: "nsnn", expected: "a a/c b"}, {operations: "nsns", expected: "a a/c b"}, {operations: "nssn", expected: "a a/c b"}, {operations: "nsss", expected: "a a/c b"}, {operations: "snnn", expected: "a b"}, {operations: "snns", expected: "a b"}, {operations: "snsn", expected: "a b"}, {operations: "snss", expected: "a b"}, {operations: "ssnn", expected: "a a/c b"}, {operations: "ssns", expected: "a a/c b"}, {operations: "sssn", expected: "a a/c b"}, {operations: "ssss", expected: "a a/c b"}, }, } tc.run(c) } // root // / | \ // / | ---- // f d h -------- // /\ / \ | // e a j b/ g // | / \ | // l n k icm // | // o // | // p/ func (s *IterSuite) TestCrazy(c *C) { tc := testsCollection{ tree: "(f(e(l<>) a(n(o(p())) k<>)) d<> h(j(i<> c<> m<>) b() g<>))", tests: []test{ {operations: "nnnnn", expected: "d f h"}, {operations: "nnnns", expected: "d f h"}, {operations: "nnnsn", expected: "d f h h/b h/g"}, {operations: "nnnss", expected: "d f h h/b h/g"}, {operations: "nnsnn", expected: "d f f/a f/e h"}, {operations: "nnsns", expected: "d f f/a f/e f/e/l"}, {operations: "nnssn", expected: "d f f/a f/a/k f/a/n"}, {operations: "nnsss", expected: "d f f/a f/a/k f/a/n"}, {operations: "nsnnn", expected: "d f h"}, {operations: "nsnns", expected: "d f h"}, {operations: "nsnsn", expected: "d f h h/b h/g"}, {operations: "nsnss", expected: "d f h h/b h/g"}, {operations: "nssnn", expected: "d f f/a f/e h"}, }, } tc.run(c) } // . // | // a // | // b // / \ // z h // / \ // d e // | // f func (s *IterSuite) TestNewIterFromPath(c *C) { tree, err := fsnoder.New("(a(b(z(d<> e(f<>)) h<>)))") c.Assert(err, IsNil) z := find(c, tree, "z") iter, err := merkletrie.NewIterFromPath(z) c.Assert(err, IsNil) n, err := iter.Next() c.Assert(err, IsNil) c.Assert(n.String(), Equals, "a/b/z/d") n, err = iter.Next() c.Assert(err, IsNil) c.Assert(n.String(), Equals, "a/b/z/e") n, err = iter.Step() c.Assert(err, IsNil) c.Assert(n.String(), Equals, "a/b/z/e/f") _, err = iter.Step() c.Assert(err, Equals, io.EOF) } func find(c *C, tree noder.Noder, name string) noder.Path { iter, err := merkletrie.NewIter(tree) c.Assert(err, IsNil) for { current, err := iter.Step() if err != io.EOF { c.Assert(err, IsNil) } else { c.Fatalf("node %s not found in tree %s", name, tree) } if current.Name() == name { return current } } } type errorNoder struct{} func (e *errorNoder) Name() string { return "" } func (e *errorNoder) String() string { return "" } func (e *errorNoder) Hash() []byte { return nil } func (e *errorNoder) IsDir() bool { return true } func (e *errorNoder) Children() ([]noder.Noder, error) { return nil, fmt.Errorf("mock error") } func (e *errorNoder) NumChildren() (int, error) { return 0, fmt.Errorf("mock error") } func (s *IterSuite) TestNewIterFailsOnChildrenErrors(c *C) { _, err := merkletrie.NewIter(&errorNoder{}) c.Assert(err, Not(IsNil)) }